論文の概要: Bisimulation Metrics are Optimal Transport Distances, and Can be Computed Efficiently

• arxiv url: http://arxiv.org/abs/2406.04056v1
• Date: Thu, 6 Jun 2024 13:25:14 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-07 14:49:58.815925
• Title: Bisimulation Metrics are Optimal Transport Distances, and Can be Computed Efficiently
• Title（参考訳）: Bisimulation Metrics is Optimal Transport Distances and can Computediently
• Authors: Sergio Calo, Anders Jonsson, Gergely Neu, Ludovic Schwartz, Javier Segovia,
• Abstract要約: マルコフ連鎖間の最適な輸送距離を定式化するための新しい枠組みを提案する。 関節分布の全空間における最適輸送距離を計算することは、線形プログラムの解法として等価に定式化できることを示す。
• 参考スコア（独自算出の注目度）: 14.262270388108112
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a new framework for formulating optimal transport distances between Markov chains. Previously known formulations studied couplings between the entire joint distribution induced by the chains, and derived solutions via a reduction to dynamic programming (DP) in an appropriately defined Markov decision process. This formulation has, however, not led to particularly efficient algorithms so far, since computing the associated DP operators requires fully solving a static optimal transport problem, and these operators need to be applied numerous times during the overall optimization process. In this work, we develop an alternative perspective by considering couplings between a flattened version of the joint distributions that we call discounted occupancy couplings, and show that calculating optimal transport distances in the full space of joint distributions can be equivalently formulated as solving a linear program (LP) in this reduced space. This LP formulation allows us to port several algorithmic ideas from other areas of optimal transport theory. In particular, our formulation makes it possible to introduce an appropriate notion of entropy regularization into the optimization problem, which in turn enables us to directly calculate optimal transport distances via a Sinkhorn-like method we call Sinkhorn Value Iteration (SVI). We show both theoretically and empirically that this method converges quickly to an optimal coupling, essentially at the same computational cost of running vanilla Sinkhorn in each pair of states. Along the way, we point out that our optimal transport distance exactly matches the common notion of bisimulation metrics between Markov chains, and thus our results also apply to computing such metrics, and in fact our algorithm turns out to be significantly more efficient than the best known methods developed so far for this purpose.
• Abstract（参考訳）: マルコフ連鎖間の最適な輸送距離を定式化するための新しい枠組みを提案する。 これまで知られていた定式化は、連鎖によって誘導される結合分布全体と、適切に定義されたマルコフ決定過程における動的プログラミング(DP)への還元による導出解の間の結合を研究していた。 しかし、この定式化は、関連するDP演算子を計算する際には、静的な最適輸送問題を完全に解決する必要があるため、これまでは特に効率的なアルゴリズムを導いていない。 本研究では, 分割占有結合と呼ばれる関節分布の平坦化バージョン間の結合を考慮し, この縮小された空間における線形プログラム(LP)の解法として, 関節分布の全空間における最適輸送距離を等価に定式化できることを示す。 このLP定式化により、最適輸送理論の他の領域からいくつかのアルゴリズム的アイデアを移植することができる。 具体的には,最適化問題にエントロピー正規化の適切な概念を導入し,Sinkhorn Value Iteration (SVI) と呼ぶSinkhornライクな手法を用いて,最適な輸送距離を直接計算することができる。 本手法は,バニラ・シンクホーンを各状態に走らせるのと同じ計算コストで,最適結合に迅速に収束することを示す。 その過程で, 最適輸送距離はマルコフ連鎖間のバイシミュレーション指標の共通概念と正確に一致していることが指摘され, 結果もそのような指標の計算に適用され, 実際, この目的のために開発した最もよく知られた手法よりもはるかに効率的であることが判明した。

関連論文リスト

• Dynamical Measure Transport and Neural PDE Solvers for Sampling [77.38204731939273]
  本研究では, 対象物へのトラクタブル密度関数の移動として, 確率密度からサンプリングする作業に取り組む。 物理インフォームドニューラルネットワーク(PINN)を用いて各偏微分方程式(PDE)の解を近似する。 PINNはシミュレーションと離散化のない最適化を可能にし、非常に効率的に訓練することができる。
  論文  参考訳（メタデータ） (2024-07-10T17:39:50Z)
• A Sinkhorn-type Algorithm for Constrained Optimal Transport [14.935188572016635]
  この研究は、等式制約と不等式制約を組み合わせた一般的なOT問題に焦点をあてる。 対応するエントロピー正規化の定式化を導出し、理論的保証によって支持される制約付きOT問題に対してシンクホーン型アルゴリズムを導入する。 全体として、この研究は、エントロピー最適輸送の最近の理論的および数値的な進歩と制約されたケースを体系的に組み合わせ、実践者は複雑なシナリオにおいて近似的な輸送計画を引き出すことができる。
  論文  参考訳（メタデータ） (2024-03-08T05:01:43Z)
• OTClean: Data Cleaning for Conditional Independence Violations using Optimal Transport [51.6416022358349]
  sysは、条件付き独立性(CI)制約下でのデータ修復に最適な輸送理論を利用するフレームワークである。 我々はSinkhornの行列スケーリングアルゴリズムにインスパイアされた反復アルゴリズムを開発し、高次元および大規模データを効率的に処理する。
  論文  参考訳（メタデータ） (2024-03-04T18:23:55Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。 我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。 シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
  論文  参考訳（メタデータ） (2024-01-29T02:08:40Z)
• Optimal Transport with Tempered Exponential Measures [33.07787452859956]
  間接測度正規化を伴う指数族を一般化することは、非常に便利な中核となる。 我々の定式化は、不均衡な最適輸送問題設定に自然に適合する。
  論文  参考訳（メタデータ） (2023-09-07T20:53:23Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。 これらの問題に対する新規で簡単な最適化法を開発した。 結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2021-09-23T17:38:24Z)
• Improving Approximate Optimal Transport Distances using Quantization [23.319746583489763]
  最適な輸送は、確率測度を幾何学的に比較する機械学習の一般的なツールである。 OTの線形プログラミングアルゴリズムは入力の規模を3倍にスケールし、大局的にOTを非現実的にする。 安価なサンプルアクセスで測定値間のOT距離を推定するために, 量子化ステップを用いた実用的アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-02-25T08:45:06Z)
• FedSplit: An algorithmic framework for fast federated optimization [40.42352500741025]
  本稿では,分散凸最小化を付加構造で解くアルゴリズムのクラスであるFedSplitを紹介する。 これらの手法は, 中間局所量の不正確な計算に対して, 確実に堅牢であることを示す。
  論文  参考訳（メタデータ） (2020-05-11T16:30:09Z)

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

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