最適輸送のためのプッシュ-リラベルベース加算近似【JST・京大機械翻訳】

Lahn Nathaniel; Raghvendra Sharath; Zhang Kaiyi

プレプリント

J-GLOBAL ID：202202207802198092 整理番号：22P0300382

最適輸送のためのプッシュ-リラベルベース加算近似【JST・京大機械翻訳】

A Push-Relabel Based Additive Approximation for Optimal Transport

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (3件)： , ,
資料名：
発行年： 2022年03月07日プレプリントサーバーでの情報更新日： 2022年03月07日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

最適輸送は,分布間の類似性を測定するための一般的な距離メトリックである。最適輸送を計算するための正確なアルゴリズムは遅く,近似数値ソルバ(例えば,Sinkorn法)の開発を動機づけた。OT距離のε近似を見つけるために,新しく非常に簡単な組合せ手法を導入した。著者らのアルゴリズムは,OT距離を計算するためのO(n ̄2/ε ̄2)の近最適実行時間を達成して,割り当て問題の特殊ケースのために,実行時間はO(n ̄2/ε)に改善した。このアルゴリズムは,最小コストフロー問題のためのプッシュ-ラベルフレームワークに基づいている。他のコンビナトリアルアプローチ(Lahn,MulchananiおよびRaghvendra,NeurIPS 2019)と異なり,高速並列実装を持たない,著者らのアルゴリズムは,O(logn/ε ̄2)の並列実行時間を有する。興味深いことに,Sinkornアルゴリズムとは異なり,この方法はまた,OT問題の2重定式化の近似バージョンに対する解と同様にコンパクトな輸送計画を容易に提供し,その両方は機械学習において多数の応用を持つ。割当て問題のために,GPU並列性を利用する実装と同様にCPU実装の両方を提供した。実験により,提案アルゴリズムは,CPUおよびGPU実装に関して,特に高精度でマッチングを計算する一方で,Sinkornアルゴリズムよりも高速であることを示した。【JST・京大機械翻訳】

, , , , , , , , , , ,
, , , , 【Automatic Indexing@JST】

グラフ理論基礎 , 計算理論

, , ,

前のページに戻る