論文の概要: Fast unsupervised ground metric learning with tree-Wasserstein distance
- arxiv url: http://arxiv.org/abs/2411.07432v2
- Date: Fri, 10 Jan 2025 12:33:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-13 15:24:14.128824
- Title: Fast unsupervised ground metric learning with tree-Wasserstein distance
- Title（参考訳）: 木-ワッサーシュタイン距離を用いた高速非教師付き地上距離学習
- Authors: Kira M. Düsterwald, Samo Hromadka, Makoto Yamada,
- Abstract要約: 教師なしの地上距離学習アプローチが導入されました
一つの有望な選択肢はワッサーシュタイン特異ベクトル(WSV)であり、特徴量とサンプルの間の最適な輸送距離を同時に計算する際に現れる。
木にサンプルや特徴を埋め込むことでWSV法を強化し,木-ワッサーシュタイン距離(TWD)を計算することを提案する。
- 参考スコア（独自算出の注目度）: 14.235762519615175
- License:
- Abstract: The performance of unsupervised methods such as clustering depends on the choice of distance metric between features, or ground metric. Commonly, ground metrics are decided with heuristics or learned via supervised algorithms. However, since many interesting datasets are unlabelled, unsupervised ground metric learning approaches have been introduced. One promising option employs Wasserstein singular vectors (WSVs), which emerge when computing optimal transport distances between features and samples simultaneously. WSVs are effective, but can be prohibitively computationally expensive in some applications: $\mathcal{O}(n^2m^2(n \log(n) + m \log(m))$ for $n$ samples and $m$ features. In this work, we propose to augment the WSV method by embedding samples and features on trees, on which we compute the tree-Wasserstein distance (TWD). We demonstrate theoretically and empirically that the algorithm converges to a better approximation of the standard WSV approach than the best known alternatives, and does so with $\mathcal{O}(n^3+m^3+mn)$ complexity. In addition, we prove that the initial tree structure can be chosen flexibly, since tree geometry does not constrain the richness of the approximation up to the number of edge weights. This proof suggests a fast and recursive algorithm for computing the tree parameter basis set, which we find crucial to realising the efficiency gains at scale. Finally, we employ the tree-WSV algorithm to several single-cell RNA sequencing genomics datasets, demonstrating its scalability and utility for unsupervised cell-type clustering problems. These results poise unsupervised ground metric learning with TWD as a low-rank approximation of WSV with the potential for widespread application.
- Abstract（参考訳）: クラスタリングのような教師なしの手法のパフォーマンスは、特徴間の距離メートル法や基底メートル法の選択に依存する。
一般的に、地上のメトリクスはヒューリスティックスで決定されるか、あるいは教師付きアルゴリズムで学習される。
しかし、多くの興味深いデータセットが損なわれていないため、教師なしの地上メトリック学習アプローチが導入されている。
一つの有望な選択肢はワッサーシュタイン特異ベクトル(WSV)であり、特徴量とサンプルの間の最適な輸送距離を同時に計算する際に現れる。
WSVは有効であるが、いくつかのアプリケーションでは計算コストが禁じられる: $\mathcal{O}(n^2m^2(n \log)
(n) + m \log
(m))$$$n$サンプルと$m$機能。
本稿では,木にサンプルや特徴を埋め込んで,木-ワッサーシュタイン距離(TWD)を計算することで,WSV法の拡張を提案する。
我々は、このアルゴリズムが最もよく知られた方法よりも標準的なWSVアプローチの近似に収束し、$$\mathcal{O}(n^3+m^3+mn)$複雑さを持つことを示した。
さらに、木形状が近似の豊かさをエッジウェイトの数まで制約しないため、初期木構造が柔軟に選択できることを証明した。
この証明は,木パラメータ基底集合を高速かつ再帰的に計算するアルゴリズムを提案する。
最後に、ツリーWSVアルゴリズムを複数の単一セルRNAシークエンシングゲノミクスデータセットに適用し、教師なしセル型クラスタリング問題に対するスケーラビリティと有用性を実証する。
これらの結果は、WSVの低ランク近似としてTWDを用いた教師なし地上計量学習を広範に適用する可能性を秘めている。
関連論文リスト
- Approximate Tree Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees [7.2092555743847155]
任意の距離空間における$n$ポイントの最小スパンニングツリー(MST)を見つけることは、階層的クラスタリングや他の多くのMLタスクの基本的なプリミティブである。
まず,(1)実践的手法を用いて不連結成分の森を発見し,(2)森林の不連結成分を分布木に接続するためのエッジの小さな重み集合を見出した。
2番目のステップを最適に解くには、まだ$Omega(n2)$時間が必要ですが、サブクワッドラティックな2.62近似アルゴリズムを提供しています。
論文 参考訳（メタデータ） (2025-02-18T16:13:46Z) - Coupled Hierarchical Structure Learning using Tree-Wasserstein Distance [12.2853783834605]
木-ワッサーシュタイン距離(TWD)を用いた階層構造学習手法を提案する。
提案手法は,TWDのサンプルと特徴を共同で計算し,その潜在階層を木として表現する。
この反復的な手順が収束し, 木質を実証的に向上させることを示す。
論文 参考訳（メタデータ） (2025-01-07T08:54:42Z) - Linearized Wasserstein dimensionality reduction with approximation
guarantees [65.16758672591365]
LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。
我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。
また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
論文 参考訳（メタデータ） (2023-02-14T22:12:16Z) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。
第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文 参考訳（メタデータ） (2023-02-02T08:33:36Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Unbiased and Efficient Sampling of Dependency Trees [0.0]
ほとんどのツリーバンクは、すべての有効な依存ツリーがROOTノードから出てくる単一のエッジを持つ必要がある。
Zmigrodらは最近、単一ルート依存ツリーの分布から置き換えることなくサンプリングするアルゴリズムを提案している。
我々は、Wilson-RCを置換したサンプリングアルゴリズムが実際にバイアスを受けていることを示す。
論文 参考訳（メタデータ） (2022-05-25T09:57:28Z) - Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。
A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。
実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文 参考訳（メタデータ） (2021-04-14T18:15:27Z) - Learning Binary Decision Trees by Argmin Differentiation [34.9154848754842]
ダウンストリームタスクのためにデータを分割するバイナリ決定木を学びます。
離散パラメータの混合整数プログラムを緩和する。
我々は、前方と後方のパスを効率的に計算するアルゴリズムを考案した。
論文 参考訳（メタデータ） (2020-10-09T15:11:28Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z) - Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。
一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。
我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-02-28T04:21:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。