論文の概要: Hierarchical Refinement: Optimal Transport to Infinity and Beyond
- arxiv url: http://arxiv.org/abs/2503.03025v1
- Date: Tue, 04 Mar 2025 22:00:12 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-06 15:51:41.937489
- Title: Hierarchical Refinement: Optimal Transport to Infinity and Beyond
- Title（参考訳）: 階層的リファインメント--インフィニティと超越への最適輸送
- Authors: Peter Halmos, Julian Gold, Xinhao Liu, Benjamin J. Raphael,
- Abstract要約: 最適なトランスポート(OT)は、最小コストの対応を通じてデータセットを整列する原則的な方法として、機械学習において大きな成功を収めている。
シンクホーンは点数において2次空間の複雑さを持ち、拡張性はより大きなデータセットに制限される。
低ランクOTサブプロブレムを用いてデータセットのマルチスケールパーティションを動的に構築するアルゴリズムを導出する。
- 参考スコア（独自算出の注目度）: 1.8749305679160366
- License:
- Abstract: Optimal transport (OT) has enjoyed great success in machine-learning as a principled way to align datasets via a least-cost correspondence. This success was driven in large part by the runtime efficiency of the Sinkhorn algorithm [Cuturi 2013], which computes a coupling between points from two datasets. However, Sinkhorn has quadratic space complexity in the number of points, limiting the scalability to larger datasets. Low-rank OT achieves linear-space complexity, but by definition, cannot compute a one-to-one correspondence between points. When the optimal transport problem is an assignment problem between datasets then the optimal mapping, known as the Monge map, is guaranteed to be a bijection. In this setting, we show that the factors of an optimal low-rank coupling co-cluster each point with its image under the Monge map. We leverage this invariant to derive an algorithm, Hierarchical Refinement (HiRef), that dynamically constructs a multiscale partition of a dataset using low-rank OT subproblems, culminating in a bijective coupling. Hierarchical Refinement uses linear space and has log-linear runtime, retaining the space advantage of low-rank OT while overcoming its limited resolution. We demonstrate the advantages of Hierarchical Refinement on several datasets, including ones containing over a million points, scaling full-rank OT to problems previously beyond Sinkhorn's reach.
- Abstract（参考訳）: 最適なトランスポート(OT)は、最小コストの対応を通じてデータセットを整列する原則的な方法として、機械学習において大きな成功を収めている。
この成功は、主にSinkhornアルゴリズム(Cuturi 2013)の実行効率によって引き起こされた。
しかし、シンクホーンは点数において2次空間の複雑さを持ち、拡張性はより大きなデータセットに制限される。
低ランクOTは線型空間複雑性を実現するが、定義上は点間の1対1対応を計算することはできない。
最適な輸送問題がデータセット間の代入問題である場合、最適なマッピングはMonge mapと呼ばれ、ビジェクションであることが保証される。
この設定では,モンジュ写像の下の画像と各点の最適低ランクカップリングコクラスタの因子が一致することを示す。
我々はこの不変量を利用して、低ランクOTサブプロブレムを用いてデータセットのマルチスケールパーティションを動的に構築するアルゴリズムHierarchical Refinement (HiRef) を導出した。
Hierarchical Refinementは線形空間を使用し、ログ線形ランタイムを持ち、低ランクOTの空間優位性を保ちながら、その限られた解像度を克服する。
我々は、100万以上のポイントを含むデータセットを含む複数のデータセットで階層的リファインメントの利点を示し、Sinkhornの範囲を超える問題にフルランクOTをスケールする。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Linearized Wasserstein dimensionality reduction with approximation
guarantees [65.16758672591365]
LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。
我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。
また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
論文 参考訳（メタデータ） (2023-02-14T22:12:16Z) - Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via
GDPA Linearization [59.87663954467815]
アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。
本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。
実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
論文 参考訳（メタデータ） (2021-09-10T07:01:15Z) - Fast and Scalable Optimal Transport for Brain Tractograms [4.610968512889579]
線形メモリフットプリント上での正規化最適輸送問題を解くための新しいマルチスケールアルゴリズムを提案する。
本手法は, ファイバー束やトラック密度マップとしてモデル化された脳幹図に対して有効性を示す。
論文 参考訳（メタデータ） (2021-07-05T13:28:41Z) - ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering
using Nearest-Neighbor Chain [6.824747267214373]
本稿では並列階層クラスタリング(HAC)アルゴリズムを設計するためのParChainフレームワークを提案する。
従来の並列HACアルゴリズムと比較して、我々の新しいアルゴリズムは線形メモリしか必要とせず、大規模データセットにスケーラブルである。
我々のアルゴリズムは、既存のアルゴリズムでは処理できない数千万のポイントでデータセットのサイズにスケールすることができる。
論文 参考訳（メタデータ） (2021-06-08T23:13:27Z) - Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and
Costs [45.87981728307819]
異種空間に居住する関連するデータセットを比較して整列する能力は、機械学習においてますます重要な役割を担っている。
グロモフ・ワッサーシュタイン (Gromov-Wasserstein, GW) 形式主義はこの問題に対処するのに役立つ。
論文 参考訳（メタデータ） (2021-06-02T12:50:56Z) - Random Features for the Neural Tangent Kernel [57.132634274795066]
完全接続型ReLUネットワークのニューラルタンジェントカーネル(NTK)の効率的な特徴マップ構築を提案する。
得られた特徴の次元は、理論と実践の両方で比較誤差境界を達成するために、他のベースライン特徴マップ構造よりもはるかに小さいことを示しています。
論文 参考訳（メタデータ） (2021-04-03T09:08:12Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - A Study of Performance of Optimal Transport [16.847501106437534]
本稿では,ネットワークの単純化と拡張パスに基づくアルゴリズムが,数値行列スケーリング法より一貫して優れていることを示す。
古典的なKuhn-Munkresアルゴリズムを改良した新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-05-03T20:37:05Z) - Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。
我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
論文 参考訳（メタデータ） (2020-04-23T05:00:21Z) - Efficient and Robust Shape Correspondence via Sparsity-Enforced
Quadratic Assignment [16.03666555216332]
そこで我々は,新しい局所的なペアワイズ記述子を導入し,その結果の2次代入を解くための,シンプルで効果的な反復法を開発した。
我々のペアワイズ記述子は、ラプラス・ベルトラミ微分作用素の有限要素近似の剛性と質量反復行列に基づいている。
我々は,大規模データセット,パッチ,ポイントクラウド上での手法の効率性,品質,汎用性を示すために,様々な実験を行った。
論文 参考訳（メタデータ） (2020-03-19T10:56:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。