論文の概要: Relative Entropy-Regularized Optimal Transport on a Graph: a new
algorithm and an experimental comparison
- arxiv url: http://arxiv.org/abs/2108.10004v1
- Date: Mon, 23 Aug 2021 08:25:51 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-24 15:36:21.627153
- Title: Relative Entropy-Regularized Optimal Transport on a Graph: a new
algorithm and an experimental comparison
- Title(参考訳): グラフ上の相対エントロピー規則化された最適輸送:新しいアルゴリズムと実験的比較
- Authors: Sylvain Courtain, Guillaume Guex, Ilkka Kivimaki and Marco Saerens
- Abstract要約: 本研究は,ランダム化された最短経路形式におけるグラフ問題に対する最適輸送を解くための,新しい相対エントロピー正規化アルゴリズムについて検討する。
この新たな定式化の主な利点は、エッジフローキャパシティの制約に容易に対応できるという事実である。
結果として得られる最適ルーティングポリシー、すなわち各ノードのエッジに従う確率分布はマルコビアンであり、入力と出力を所定の限界確率に制限することで計算される。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Following [21, 23], the present work investigates a new relative
entropy-regularized algorithm for solving the optimal transport on a graph
problem within the randomized shortest paths formalism. More precisely, a unit
flow is injected into a set of input nodes and collected from a set of output
nodes while minimizing the expected transportation cost together with a paths
relative entropy regularization term, providing a randomized routing policy.
The main advantage of this new formulation is the fact that it can easily
accommodate edge flow capacity constraints which commonly occur in real-world
problems. The resulting optimal routing policy, i.e., the probability
distribution of following an edge in each node, is Markovian and is computed by
constraining the input and output flows to the prescribed marginal
probabilities thanks to a variant of the algorithm developed in [8]. Besides,
experimental comparisons with other recently developed techniques show that the
distance measure between nodes derived from the introduced model provides
competitive results on semi-supervised classification tasks.
- Abstract(参考訳): 本研究は, [21, 23] に続いて, ランダム化最短経路形式におけるグラフ問題の最適トランスポートを解くための, 新しい相対エントロピー正規化アルゴリズムについて検討する。
より正確には、単位フローを入力ノードの集合に注入し、期待輸送コストをパス相対エントロピー正規化項とともに最小化し、ランダム化されたルーティングポリシーを提供する。
この新しい定式化の主な利点は、実世界の問題でよく発生するエッジフローのキャパシティの制約に容易に対応できることである。
結果として得られる最適ルーティングポリシー、すなわち、各ノードのエッジに従う確率分布はマルコビアンであり、[8]で開発されたアルゴリズムの変種により入力と出力が所定の限界確率に制限されることで計算される。
さらに,最近開発された他の手法との比較により,導入したモデルから導出したノード間の距離測定により,半教師付き分類タスクにおいて競合する結果が得られた。
関連論文リスト
- Dynamical Measure Transport and Neural PDE Solvers for Sampling [77.38204731939273]
本研究では, 対象物へのトラクタブル密度関数の移動として, 確率密度からサンプリングする作業に取り組む。
物理インフォームドニューラルネットワーク(PINN)を用いて各偏微分方程式(PDE)の解を近似する。
PINNはシミュレーションと離散化のない最適化を可能にし、非常に効率的に訓練することができる。
論文 参考訳(メタデータ) (2024-07-10T17:39:50Z) - Distributed Markov Chain Monte Carlo Sampling based on the Alternating
Direction Method of Multipliers [143.6249073384419]
本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。
我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。
シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
論文 参考訳(メタデータ) (2024-01-29T02:08:40Z) - Flow-based Distributionally Robust Optimization [23.232731771848883]
We present a framework, called $textttFlowDRO$, for solve flow-based distributionally robust optimization (DRO) problem with Wasserstein uncertainty set。
我々は、連続した最悪のケース分布(Last Favorable Distribution, LFD)とそれからのサンプルを見つけることを目指している。
本稿では、逆学習、分布論的に堅牢な仮説テスト、およびデータ駆動型分布摂動差分プライバシーの新しいメカニズムを実証する。
論文 参考訳(メタデータ) (2023-10-30T03:53:31Z) - Robust empirical risk minimization via Newton's method [9.797319790710711]
実験的リスク最小化のためのニュートン法の新しい変種について検討した。
目的関数の勾配と Hessian は、ロバストな推定器に置き換えられる。
また,共役勾配法に基づくニュートン方向のロバストな解を求めるアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-01-30T18:54:54Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳(メタデータ) (2023-01-30T15:46:39Z) - Learning Optimal Transport Between two Empirical Distributions with
Normalizing Flows [12.91637880428221]
本稿では、ニューラルネットワークの柔軟性を活用して、最適輸送マップを近似的に学習することを提案する。
我々は、このOT問題の解を近似するために、非可逆ニューラルネットワークの特定の例、すなわち正規化フローが利用できることを示した。
論文 参考訳(メタデータ) (2022-07-04T08:08:47Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳(メタデータ) (2021-06-08T15:54:44Z) - Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical
Solution [8.465228064780748]
2つの点でサポートされる離散確率測度の間のWasserstein距離の計算が既に#P-hardであることを証明します。
目的関数が最も悪質な外乱分布で滑らかになる分布的に頑健な双対最適輸送問題を導入する。
双対目的関数の平滑化は主目的関数の正則化と等価であることを示す。
論文 参考訳(メタデータ) (2021-03-10T18:53:59Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳(メタデータ) (2020-10-23T09:12:47Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。
この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。
古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文 参考訳(メタデータ) (2020-07-01T18:43:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。