論文の概要: Efficient Solvers for Partial Gromov-Wasserstein
- arxiv url: http://arxiv.org/abs/2402.03664v1
- Date: Tue, 6 Feb 2024 03:36:05 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-07 17:00:03.394993
- Title: Efficient Solvers for Partial Gromov-Wasserstein
- Title(参考訳): 部分グロモフ・ワッサーシュタインの効率的な解法
- Authors: Yikun Bai, Rocio Diaz Martin, Hengrong Du, Ashkan Shahbazi, and Soheil
Kolouri
- Abstract要約: 部分グロモフ=ワッサーシュタイン問題(英語版)(PGW)は、潜在的に異なる距離空間に存在する不等質量との比較を容易にする。
本稿では, PGW問題をGromov-Wasserstein問題の変種に変換できることを示す。
- 参考スコア(独自算出の注目度): 8.23887869467319
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The partial Gromov-Wasserstein (PGW) problem facilitates the comparison of
measures with unequal masses residing in potentially distinct metric spaces,
thereby enabling unbalanced and partial matching across these spaces. In this
paper, we demonstrate that the PGW problem can be transformed into a variant of
the Gromov-Wasserstein problem, akin to the conversion of the partial optimal
transport problem into an optimal transport problem. This transformation leads
to two new solvers, mathematically and computationally equivalent, based on the
Frank-Wolfe algorithm, that provide efficient solutions to the PGW problem. We
further establish that the PGW problem constitutes a metric for metric measure
spaces. Finally, we validate the effectiveness of our proposed solvers in terms
of computation time and performance on shape-matching and positive-unlabeled
learning problems, comparing them against existing baselines.
- Abstract(参考訳): 部分グロモフ=ワッサーシュタイン問題(英語版)(PGW)は、潜在的に異なる距離空間に存在する不等質量との測度の比較を容易にするため、これらの空間間の不均衡および部分的マッチングを可能にする。
本稿では, PGW問題をGromov-Wasserstein問題の変種に変換できることを示す。
この変換は、フランク・ウルフアルゴリズムに基づく数学的および計算的に等価な2つの新しい解法につながり、pgw問題の効率的な解を与える。
さらに、PGW問題は計量測度空間の計量を構成することを確かめる。
最後に,提案する解法の有効性を,既存のベースラインと比較し,形状マッチングおよび正ラベル学習問題における計算時間と性能の観点から検証した。
関連論文リスト
- Globally solving the Gromov-Wasserstein problem for point clouds in low
dimensional Euclidean spaces [5.534626267734822]
本稿では,低次元空間における2つの点間のGromov-Wasserstein問題を計算するための枠組みを提案する。
これは、AIと機械学習における一般的な問題である2つの構成または形状の類似性を定量化するために使用できる。
論文 参考訳(メタデータ) (2023-07-18T08:20:56Z) - A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein
in Graph Data [37.89640056739607]
本稿では,Gromov-Wasserstein (GW) 距離の近似解を提供する単一ループアルゴリズムであるBregman Alternating Projected Gradient (BAPG) を提案する。
本稿では,カップリングマップの実現可能性においていくつかの妥協点があるにもかかわらず,精度と計算効率のバランスをとる新しい緩和手法を提案する。
論文 参考訳(メタデータ) (2023-03-12T07:23:16Z) - Neural Gromov-Wasserstein Optimal Transport [82.05269165407427]
本稿では,Gromov-Wasserstein (GW) Optimal Transport (OT) 問題を内部積コストで解くためのスケーラブルなニューラルネットワーク手法を提案する。
提案手法では,ニューラルネットワークとミニバッチ最適化を用いて,既存の手法の限界を克服する。
論文 参考訳(メタデータ) (2023-03-10T15:21:12Z) - Unbalanced penalization: A new approach to encode inequality constraints
of combinatorial problems for quantum optimization algorithms [58.720142291102135]
余分なスラック変数を必要としない代替手法を提案する。
我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。
この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
論文 参考訳(メタデータ) (2022-11-25T06:05:18Z) - On the Convergence of Projected Alternating Maximization for Equitable
and Optimal Transport [36.97843660480747]
本稿では,多くの応用例を有する等価・最適輸送(EOT)問題について検討する。
離散分布の場合、EOT問題は線形プログラム(LP)として定式化できる。
このLPは一般解法では禁止的に大きいため、Scetbon etal citescetbonequitable はエントロピー正則化を加えることによって問題を摂動することを示唆している。
彼らは、エントロピー正規化EOTの双対を解くための予測交互化アルゴリズム(PAM)を提案した。
論文 参考訳(メタデータ) (2021-09-29T04:32:06Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳(メタデータ) (2021-06-08T15:54:44Z) - Quantized Gromov-Wasserstein [10.592277756185046]
Quantized Gromov Wasserstein(qGW)は、部品を基本的なオブジェクトとして扱い、問題の理論上の上限の階層に収まるメトリクスです。
最適なgwマッチングを近似するアルゴリズムを開発し,アルゴリズムによる高速化とメモリ複雑性の低減を実現する。
我々は、最先端の状況を超えて、既存の文献よりも桁違いに大きいスケールでGWマッチングを適用することができる。
論文 参考訳(メタデータ) (2021-04-05T17:03:20Z) - Projection Robust Wasserstein Barycenter [36.97843660480747]
ワッサースタイン・バリセンターの 近似は 次元の呪いのため 数値的に困難です
本稿では,次元の呪いを緩和するプロジェクションロバストなワッサーシュタインバリセンタ(PRWB)を提案する。
論文 参考訳(メタデータ) (2021-02-05T19:23:35Z) - Boosting Data Reduction for the Maximum Weight Independent Set Problem
Using Increasing Transformations [59.84561168501493]
最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。
驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。
提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
論文 参考訳(メタデータ) (2020-08-12T08:52:50Z) - Joint Wasserstein Distribution Matching [89.86721884036021]
JDM問題(Joint Distribution matching)は、2つのドメインの関節分布を一致させるために双方向マッピングを学習することを目的としており、多くの機械学習およびコンピュータビジョンアプリケーションで発生している。
2つの領域における関節分布のワッサーシュタイン距離を最小化することにより、JDM問題に対処することを提案する。
そこで我々は,難解な問題を簡単な最適化問題に還元する重要な定理を提案し,その解法を開発した。
論文 参考訳(メタデータ) (2020-03-01T03:39:00Z) - Fast and Robust Comparison of Probability Measures in Heterogeneous
Spaces [62.35667646858558]
本稿では, アンカー・エナジー (AE) とアンカー・ワッサースタイン (AW) 距離を紹介する。
我々の主な貢献は、素案実装が立方体となる対数四重項時間でAEを正確に計算するスイープラインアルゴリズムを提案することである。
AE と AW は,一般的な GW 近似の計算コストのごく一部において,様々な実験環境において良好に動作することを示す。
論文 参考訳(メタデータ) (2020-02-05T03:09:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。