論文の概要: HyperAid: Denoising in hyperbolic spaces for tree-fitting and
hierarchical clustering
- arxiv url: http://arxiv.org/abs/2205.09721v1
- Date: Thu, 19 May 2022 17:33:16 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-20 15:28:36.969804
- Title: HyperAid: Denoising in hyperbolic spaces for tree-fitting and
hierarchical clustering
- Title（参考訳）: HyperAid: ツリーフィッティングと階層クラスタリングのための双曲空間のDenoising
- Authors: Eli Chien, Puoya Tabaghi, Olgica Milenkovic
- Abstract要約: 双曲空間におけるツリーメトリック・デノイング(HyperAid)に対する新しいアプローチを提案する。
Gromovの$delta$ hyperbolicity($delta$ hyperbolicity)の観点から評価すると、元のデータをツリーのようなデータに変換する。
我々はHyperAidを非負のエッジウェイトを強制するためのスキームに統合する。
- 参考スコア（独自算出の注目度）: 36.738414547278154
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The problem of fitting distances by tree-metrics has received significant
attention in the theoretical computer science and machine learning communities
alike, due to many applications in natural language processing, phylogeny,
cancer genomics and a myriad of problem areas that involve hierarchical
clustering. Despite the existence of several provably exact algorithms for
tree-metric fitting of data that inherently obeys tree-metric constraints, much
less is known about how to best fit tree-metrics for data whose structure
moderately (or substantially) differs from a tree. For such noisy data, most
available algorithms perform poorly and often produce negative edge weights in
representative trees. Furthermore, it is currently not known how to choose the
most suitable approximation objective for noisy fitting. Our contributions are
as follows. First, we propose a new approach to tree-metric denoising
(HyperAid) in hyperbolic spaces which transforms the original data into data
that is ``more'' tree-like, when evaluated in terms of Gromov's $\delta$
hyperbolicity. Second, we perform an ablation study involving two choices for
the approximation objective, $\ell_p$ norms and the Dasgupta loss. Third, we
integrate HyperAid with schemes for enforcing nonnegative edge-weights. As a
result, the HyperAid platform outperforms all other existing methods in the
literature, including Neighbor Joining (NJ), TreeRep and T-REX, both on
synthetic and real-world data. Synthetic data is represented by edge-augmented
trees and shortest-distance metrics while the real-world datasets include Zoo,
Iris, Glass, Segmentation and SpamBase; on these datasets, the average
improvement with respect to NJ is $125.94\%$.
- Abstract（参考訳）: 木量測定による適合距離の問題は、自然言語処理、系統学、癌ゲノム学、階層的クラスタリングを含む無数の問題領域に多くの応用があるため、理論的コンピュータ科学や機械学習のコミュニティでも注目されている。
ツリーメトリック制約に本質的に従属するデータのツリーメトリックフィッティングに関する実証可能なアルゴリズムはいくつか存在するが、構造が木と適度に(あるいは実質的に)異なるデータに対してツリーメトリックを最適に適合させる方法については、あまり知られていない。
このようなノイズの多いデータに対して、ほとんどのアルゴリズムは性能が悪く、しばしば代表木に負のエッジ重みを生じる。
また、現在、ノイズフィッティングの最も適した近似目標を選定する方法は分かっていない。
私たちの貢献は以下の通りです。
まず、Gromov の $\delta$ hyperbolicity の観点から評価すると、元のデータを `more'' 木のようなデータに変換するハイパーボリック空間におけるツリーメトリック・デノーミング(HyperAid)の新しいアプローチを提案する。
第2に,近似目標に対する2つの選択,$\ell_p$ノルム,Dasgupta損失に関するアブレーション研究を行った。
第三に、HyperAidと非負のエッジウェイトを強制するスキームを統合する。
その結果、HyperAidプラットフォームは、NJ(Neighbor Joining)、TreeRep、T-REXといった、合成データと実世界のデータの両方において、他の既存の手法よりも優れています。
合成データはエッジ表示木と最短距離メトリクスで表現され、現実世界のデータセットにはzoo, iris, glass, segmentation, spambaseがある。
関連論文リスト
- Fast unsupervised ground metric learning with tree-Wasserstein distance [14.235762519615175]
教師なしの地上距離学習アプローチが導入されました
木にサンプルや特徴を埋め込むことでWSV法を強化し,木-ワッサーシュタイン距離(TWD)を計算することを提案する。
我々は、このアルゴリズムが最もよく知られた方法よりも完全なWSVアプローチの近似に収束し、$mathcalO(n3)$複雑さを持つことを理論的かつ経験的に実証する。
論文 参考訳（メタデータ） (2024-11-11T23:21:01Z) - Fitting trees to $\ell_1$-hyperbolic distances [4.220336689294244]
植物遺伝学的解析において,樹冠形成は重要な要素である。
本研究では, 木組込み問題について, 双曲性ベクトルと木組込み誤差の関係について検討する。
論文 参考訳（メタデータ） (2024-09-02T07:38:32Z) - Revisiting Evaluation Metrics for Semantic Segmentation: Optimization
and Evaluation of Fine-grained Intersection over Union [113.20223082664681]
そこで本研究では,mIoUsの微細化と,それに対応する最悪の指標を提案する。
これらのきめ細かいメトリクスは、大きなオブジェクトに対するバイアスの低減、よりリッチな統計情報、モデルとデータセット監査に関する貴重な洞察を提供する。
ベンチマークでは,1つの測定値に基づかないことの必要性を強調し,微細なmIoUsが大きな物体への偏りを減少させることを確認した。
論文 参考訳（メタデータ） (2023-10-30T03:45:15Z) - Tight and fast generalization error bound of graph embedding in metric
space [54.279425319381374]
非ユークリッド計量空間へのグラフ埋め込みは、既存の有界よりもはるかに少ない訓練データを持つユークリッド空間におけるグラフ埋め込みよりも優れていることを示す。
我々の新しい上限は、既存の上限よりもかなり強く速く、最大で$R$と$O(frac1S)$に指数関数できる。
論文 参考訳（メタデータ） (2023-05-13T17:29:18Z) - Optimal Sparse Regression Trees [24.03491277969824]
本研究は,確率的最適スパース回帰木の構築に対する動的プログラミングとバウンドのアプローチを提案する。
ラベル集合上の1次元におけるk平均クラスタリングアルゴリズムの最適解に基づいて、新しい下界を利用する。
論文 参考訳（メタデータ） (2022-11-28T00:43:21Z) - Active-LATHE: An Active Learning Algorithm for Boosting the Error
Exponent for Learning Homogeneous Ising Trees [75.93186954061943]
我々は、$rho$が少なくとも0.8$である場合に、エラー指数を少なくとも40%向上させるアルゴリズムを設計し、分析する。
我々の分析は、グラフの一部により多くのデータを割り当てるために、微小だが検出可能なサンプルの統計的変動を巧みに活用することに基づいている。
論文 参考訳（メタデータ） (2021-10-27T10:45:21Z) - Decentralized Learning of Tree-Structured Gaussian Graphical Models from
Noisy Data [1.52292571922932]
本稿では,木構造ガウス図形モデル(GGM)の雑音データからの分散学習について検討する。
GGMは遺伝子制御ネットワークやソーシャルネットワークのような複雑なネットワークをモデル化するために広く利用されている。
提案した分散学習では,木構造GGMの推定にChow-Liuアルゴリズムを用いる。
論文 参考訳（メタデータ） (2021-09-22T10:41:18Z) - Highly Scalable and Provably Accurate Classification in Poincare Balls [40.82908295137667]
我々は、スケーラブルで単純な双曲型線形分類器を証明可能な性能保証で学習するための統一的なフレームワークを構築した。
提案手法は,新しい双曲型および二階型パーセプトロンアルゴリズムと,双曲型サポートベクトルマシン分類器の効率的かつ高精度な凸最適化設定を含む。
数百万の点からなる合成データセットと、シングルセルRNA-seq式測定、CIFAR10、Fashion-MNIST、mini-ImageNetのような複雑な実世界のデータセットの性能評価を行う。
論文 参考訳（メタデータ） (2021-09-08T16:59:39Z) - Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。
A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。
実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文 参考訳（メタデータ） (2021-04-14T18:15:27Z) - Forest R-CNN: Large-Vocabulary Long-Tailed Object Detection and Instance
Segmentation [75.93960390191262]
我々は、オブジェクトカテゴリ間の関係に関する事前知識を利用して、きめ細かいクラスを粗い親クラスにクラスタリングする。
そこで本研究では,NMS再サンプリング法を提案する。
提案手法はフォレストR-CNNと呼ばれ,ほとんどのオブジェクト認識モデルに適用可能なプラグイン・アンド・プレイモジュールとして機能する。
論文 参考訳（メタデータ） (2020-08-13T03:52:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。