論文の概要: Fast unsupervised ground metric learning with tree-Wasserstein distance

• arxiv url: http://arxiv.org/abs/2411.07432v1
• Date: Mon, 11 Nov 2024 23:21:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-13 13:20:52.732180
• Title: Fast unsupervised ground metric learning with tree-Wasserstein distance
• Title（参考訳）: 木-ワッサーシュタイン距離を用いた高速非教師付き地上距離学習
• Authors: Kira M. Düsterwald, Samo Hromadka, Makoto Yamada,
• Abstract要約: 教師なしの地上距離学習アプローチが導入されました 木にサンプルや特徴を埋め込むことでWSV法を強化し,木-ワッサーシュタイン距離(TWD)を計算することを提案する。 我々は、このアルゴリズムが最もよく知られた方法よりも完全なWSVアプローチの近似に収束し、$mathcalO(n3)$複雑さを持つことを理論的かつ経験的に実証する。
• 参考スコア（独自算出の注目度）: 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 datasets are unlabelled, unsupervised ground metric learning approaches have been introduced. One recent, promising option uses Wasserstein singular vectors (WSV), which emerge when computing optimal transport distances between features and samples simultaneously. While WSV is effective, it has complexity $\mathcal{O}(n^5)$, which is prohibitively expensive in some applications. 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 full WSV approach than the best known alternatives, and does so with $\mathcal{O}(n^3)$ 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, 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 low-compute application.
• Abstract（参考訳）: クラスタリングのような教師なしの手法のパフォーマンスは、特徴間の距離メートル法や基底メートル法の選択に依存する。 一般的に、地上のメトリクスはヒューリスティックスで決定されるか、あるいは教師付きアルゴリズムで学習される。 しかし、多くのデータセットは遅延しないため、教師なしの地上メトリック学習アプローチが導入されている。 最近ではワッサーシュタイン特異ベクトル (WSV) が使われており、特徴量とサンプル間の最適な輸送距離を同時に計算する際に現れる。 WSV は有効であるが、複雑さは $\mathcal{O}(n^5)$ であり、一部のアプリケーションでは極めて高価である。 本稿では,木にサンプルや特徴を埋め込んで,木-ワッサーシュタイン距離(TWD)を計算することで,WSV法の拡張を提案する。 我々は、このアルゴリズムが最もよく知られた方法よりも完全なWSVアプローチの近似に収束し、$\mathcal{O}(n^3)$複雑さを持つことを示した。 さらに、木形状が近似の豊かさをエッジウェイトの数まで制約しないため、初期木構造が柔軟に選択できることを証明した。 この証明は,木パラメータ基底集合を高速かつ再帰的に計算するアルゴリズムを提案する。 最後に、ツリーWSVアルゴリズムを複数の単一セルRNAシークエンシングゲノミクスデータセットに適用し、教師なしセル型クラスタリング問題に対するスケーラビリティと有用性を実証する。 これらの結果は、WSVの低ランク近似としてTWDを用いた教師なしの地上計量学習を、広範に低計算応用の可能性を秘めている。

関連論文リスト

• Optimal estimation of Gaussian (poly)trees [25.02920605955238]
  分布学習(KL距離)と構造学習(正確な回復)の両問題を考察する。 最初のアプローチはChow-Liuアルゴリズムに基づいており、最適な木構造分布を効率的に学習する。 第2のアプローチは、制約に基づく構造学習のための条件付き独立試験器として部分相関を用いたポリツリーに対するPCアルゴリズムの修正である。
  論文  参考訳（メタデータ） (2024-02-09T12:58:36Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• 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)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Learning Binary Decision Trees by Argmin Differentiation [34.9154848754842]
  ダウンストリームタスクのためにデータを分割するバイナリ決定木を学びます。 離散パラメータの混合整数プログラムを緩和する。 我々は、前方と後方のパスを効率的に計算するアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2020-10-09T15:11:28Z)
• A Practical Index Structure Supporting Fr\'echet Proximity Queries Among Trajectories [1.9335262420787858]
  我々は、計算コストの高いメトリクスの下で、レンジと近隣クエリに$k$のスケーラブルなアプローチを提案する。 計量指標のクラスタリングに基づいて,軌跡数に線形な木構造を求める。 本研究では,多種多様な合成および実世界のデータセットに関する広範な実験により,本手法の有効性と有効性について分析する。
  論文  参考訳（メタデータ） (2020-05-28T04:12:43Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。