論文の概要: Orlicz-Sobolev Transport for Unbalanced Measures on a Graph

• arxiv url: http://arxiv.org/abs/2502.00739v1
• Date: Sun, 02 Feb 2025 10:16:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-05 15:04:07.568707
• Title: Orlicz-Sobolev Transport for Unbalanced Measures on a Graph
• Title（参考訳）: グラフ上の不均衡対策のためのオルリッツ・ソボレフ輸送
• Authors: Tam Le, Truyen Nguyen, Hideitsu Hino, Kenji Fukumizu,
• Abstract要約: グラフ上の非負測度に対するエントロピー部分輸送(EPT)を考える。 グラフ上の不均衡測度に対してOrlicz-EPTという幾何構造を持つ新しいEPTを開発する。 特に、グラフベースのOrlicz-Sobolev空間のデュアルEPT定式化と幾何構造を利用して、Orlicz-Sobolevトランスポート(OST)を提案する新しい正規化を導出する。
• 参考スコア（独自算出の注目度）: 26.28795508071077
• License:
• Abstract: Moving beyond $L^p$ geometric structure, Orlicz-Wasserstein (OW) leverages a specific class of convex functions for Orlicz geometric structure. While OW remarkably helps to advance certain machine learning approaches, it has a high computational complexity due to its two-level optimization formula. Recently, Le et al. (2024) exploits graph structure to propose generalized Sobolev transport (GST), i.e., a scalable variant for OW. However, GST assumes that input measures have the same mass. Unlike optimal transport (OT), it is nontrivial to incorporate a mass constraint to extend GST for measures on a graph, possibly having different total mass. In this work, we propose to take a step back by considering the entropy partial transport (EPT) for nonnegative measures on a graph. By leveraging Caffarelli & McCann (2010)'s observations, EPT can be reformulated as a standard complete OT between two corresponding balanced measures. Consequently, we develop a novel EPT with Orlicz geometric structure, namely Orlicz-EPT, for unbalanced measures on a graph. Especially, by exploiting the dual EPT formulation and geometric structures of the graph-based Orlicz-Sobolev space, we derive a novel regularization to propose Orlicz-Sobolev transport (OST). The resulting distance can be efficiently computed by simply solving a univariate optimization problem, unlike the high-computational two-level optimization problem for Orlicz-EPT. Additionally, we derive geometric structures for the OST and draw its relations to other transport distances. We empirically show that OST is several-order faster than Orlicz-EPT. We further illustrate preliminary evidences on the advantages of OST for document classification, and several tasks in topological data analysis.
• Abstract（参考訳）: L^p$ 幾何構造を超えて、Orlicz-Wasserstein (OW) はOrlicz 幾何構造に対する特定の凸函数のクラスを利用する。 OWは、特定の機械学習アプローチを著しく前進させるのに役立つが、2レベル最適化の公式のため、計算の複雑さが高い。 最近、Le et al (2024) はグラフ構造を利用して一般化ソボレフ輸送(GST)、すなわちOWのスケーラブルな変種を提案する。 しかし、GSTは入力測度が同じ質量であると仮定する。 最適輸送(OT)とは異なり、グラフ上の測度に対してGSTを拡張するために質量制約を組み込むのは自明ではない。 本研究では、グラフ上の非負の測度に対するエントロピー部分輸送(EPT)を考慮し、一歩後退することを提案する。 Caffarelli & McCann (2010) の観測を利用して、EPT は対応する2つの平衡測度の間の標準完全 OT として再構成することができる。 そこで我々はOrlicz-EPTという幾何構造を持つ新しいEPTを開発した。 特に、グラフベースのOrlicz-Sobolev空間の双対 EPT の定式化と幾何構造を利用して、Orlicz-Sobolev transport (OST) を提案する新しい正規化を導出する。 結果として得られる距離は、Orlicz-EPTの高計算量2レベル最適化問題とは異なり、単変量最適化問題を解くことで効率よく計算できる。 さらに、OSTの幾何学的構造を導出し、他の輸送距離との関係を導出する。 我々はOSTがOrlicz-EPTより数桁高速であることを示す。 さらに、文書分類におけるOSTの利点に関する予備的証拠と、トポロジカルデータ解析におけるいくつかの課題について述べる。

関連論文リスト

• All You Need is Resistance: On the Equivalence of Effective Resistance and Certain Optimal Transport Problems on Graphs [48.84819106277247]
  我々は、グラフ上の効果的な抵抗と最適輸送は、最大$p$を選択するまで、一つと同じものとして理解されるべきであると主張する。 最適停止時間とグラフ上のランダムウォーク,グラフソボレフ空間,ベナモ・ブレニエ型式に対する2ドルベックマン距離の明示的な接続を示す。 本稿では、ワッサーシュタイン距離が計算ボトルネックを引き起こす可能性のあるこれらの指標のさらなる利用法を提案する。
  論文  参考訳（メタデータ） (2024-04-23T17:50:52Z)
• Generalized Sobolev Transport for Probability Measures on a Graph [26.64899319099165]
  グラフ距離空間上での測度に対する最適輸送(OT)問題について検討する。 我々は、Orlicz構造に対する特定の凸関数のクラスを活用し、一般化されたソボレフ輸送(GST)を提案する。 我々は GST が Orlicz-Wasserstein (OW) よりも数次高速であることを示す。
  論文  参考訳（メタデータ） (2024-02-07T01:49:03Z)
• Tempered Calculus for ML: Application to Hyperbolic Model Embedding [70.61101116794549]
  MLで使用されるほとんどの数学的歪みは、本質的に自然界において積分的である。 本稿では,これらの歪みを改善するための基礎的理論とツールを公表し,機械学習の要件に対処する。 我々は、最近MLで注目を集めた問題、すなわち、ハイパーボリック埋め込みを「チープ」で正確なエンコーディングで適用する方法を示す。
  論文  参考訳（メタデータ） (2024-02-06T17:21:06Z)
• Scalable Unbalanced Sobolev Transport for Measures on a Graph [23.99177001129992]
  最適輸送(OT)は確率測度を比較する強力なツールである。 OT にはいくつかの欠点がある: (i) 同じ質量を持つために必要な入力測度、(ii)高い計算複雑性、(iii)不確定性。 Le et al. (2022) は、支持体上のグラフ構造を利用して、同じ総質量のグラフ上の測度に対して、最近ソボレフ輸送を提案した。 提案した不均衡なソボレフ輸送は高速計算のための閉形式式を許容し,また負の定式であることを示す。
  論文  参考訳（メタデータ） (2023-02-24T07:35:38Z)
• Markovian Sliced Wasserstein Distances: Beyond Independent Projections [51.80527230603978]
  我々は、射影方向にマルコフ構造を課す新しいSW距離の族、Markovian sliced Wasserstein (MSW) 距離を導入する。 フロー,色移動,深部生成モデルなどの様々な応用において,従来のSW変種との距離を比較し,MSWの良好な性能を示す。
  論文  参考訳（メタデータ） (2023-01-10T01:58:15Z)
• Multi-task Learning of Order-Consistent Causal Graphs [59.9575145128345]
  我々は、$K関連ガウス非巡回グラフ(DAG)の発見問題を考える。 マルチタスク学習環境下では, 線形構造方程式モデルを学習するためのMLE ($l_1/l$-regularized maximum chance estimator) を提案する。 理論的には、関係するタスクにまたがるデータを活用することで、因果順序を復元する際のサンプルの複雑さをより高めることができることを示す。
  論文  参考訳（メタデータ） (2021-11-03T22:10:18Z)
• On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity [11.280177531118206]
  我々は,少なくとも$n$のサポートを持つ離散的(アンバランスな)測度間のマルチマルジナル部分最適輸送(POT)問題について検討した。 まず、コストテンソルの新たな拡張を通じて、マルチマルジナルな最適輸送問題の観点から、マルチマルジナルPOT問題の2つの等価形式が得られることを証明した。 我々は、ApproxMPOTアルゴリズムが、$tildemathcalO(m3(n+1)m/ varの計算複雑性上界を持つマルチマルジナルPOT問題の最適値を近似できることを実証した。
  論文  参考訳（メタデータ） (2021-08-18T06:46:59Z)
• Entropy Partial Transport with Tree Metrics: Theory and Practice [5.025654873456756]
  我々は,質量の異なる木上の非負測度に対するtextitentropy partial transport (ept)問題を考える。 高速計算と負の確定性を認める新しい EPT 規則化を提案する。 我々は、正規化が効果的な近似をもたらすことを実証的に証明する。
  論文  参考訳（メタデータ） (2021-01-24T17:04:24Z)
• On Projection Robust Optimal Transport: Sample Complexity and Model Misspecification [101.0377583883137]
  射影ロバスト(PR)OTは、2つの測度の間のOTコストを最大化するために、射影可能な$k$次元部分空間を選択する。 私たちの最初の貢献は、PRワッサーシュタイン距離のいくつかの基本的な統計的性質を確立することである。 次に、部分空間を最適化するのではなく平均化することにより、PRW距離の代替として積分PRワッサーシュタイン距離(IPRW)を提案する。
  論文  参考訳（メタデータ） (2020-06-22T14:35:33Z)
• Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces [62.35667646858558]
  本稿では, アンカー・エナジー (AE) とアンカー・ワッサースタイン (AW) 距離を紹介する。 我々の主な貢献は、素案実装が立方体となる対数四重項時間でAEを正確に計算するスイープラインアルゴリズムを提案することである。 AE と AW は,一般的な GW 近似の計算コストのごく一部において,様々な実験環境において良好に動作することを示す。
  論文  参考訳（メタデータ） (2020-02-05T03:09:23Z)

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

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