論文の概要: Sparsity-Constrained Optimal Transport

• arxiv url: http://arxiv.org/abs/2209.15466v2
• Date: Fri, 14 Apr 2023 13:24:43 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-17 16:53:29.106100
• Title: Sparsity-Constrained Optimal Transport
• Title（参考訳）: 空間制約による最適輸送
• Authors: Tianlin Liu, Joan Puigcerver, Mathieu Blondel
• Abstract要約: 正規化された最適輸送は、ニューラルネットワークの損失層やマッチング層として、ますます利用されている。 本稿では,交通計画に明示的な基数制約を課したOTに対する新しいアプローチを提案する。 本手法は,非正規化OT($k$の場合)と二次正規化OT($k$が十分に大きい場合)の中間地盤と考えることができる。
• 参考スコア（独自算出の注目度）: 27.76137474217754
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Regularized optimal transport (OT) is now increasingly used as a loss or as a matching layer in neural networks. Entropy-regularized OT can be computed using the Sinkhorn algorithm but it leads to fully-dense transportation plans, meaning that all sources are (fractionally) matched with all targets. To address this issue, several works have investigated quadratic regularization instead. This regularization preserves sparsity and leads to unconstrained and smooth (semi) dual objectives, that can be solved with off-the-shelf gradient methods. Unfortunately, quadratic regularization does not give direct control over the cardinality (number of nonzeros) of the transportation plan. We propose in this paper a new approach for OT with explicit cardinality constraints on the transportation plan. Our work is motivated by an application to sparse mixture of experts, where OT can be used to match input tokens such as image patches with expert models such as neural networks. Cardinality constraints ensure that at most $k$ tokens are matched with an expert, which is crucial for computational performance reasons. Despite the nonconvexity of cardinality constraints, we show that the corresponding (semi) dual problems are tractable and can be solved with first-order gradient methods. Our method can be thought as a middle ground between unregularized OT (recovered in the limit case $k=1$) and quadratically-regularized OT (recovered when $k$ is large enough). The smoothness of the objectives increases as $k$ increases, giving rise to a trade-off between convergence speed and sparsity of the optimal plan.
• Abstract（参考訳）: 正規化された最適輸送(OT)は、ニューラルネットワークの損失層やマッチング層としてますます利用されている。 エントロピー正規化otはシンクホーンアルゴリズムで計算できるが、完全な輸送計画につながり、すべてのソースが(理論上は)すべてのターゲットと一致している。 この問題に対処するため、いくつかの作品が代わりに二次正則化を研究している。 この正規化はスパーシリティを保ち、非拘束的で滑らかな(半)双対目的へとつながり、既成の勾配法で解ける。 残念なことに、二次正規化は輸送計画の基数(非ゼロ数)を直接制御するものではない。 本稿では,交通計画の基数制約を明示したOTに対する新しいアプローチを提案する。 我々の研究は、画像パッチのような入力トークンとニューラルネットワークのようなエキスパートモデルとのマッチングにOTを使用する、専門家のまばらな混合のアプリケーションによって動機付けられています。 濃度制約は、最大で$k$トークンが専門家と一致していることを保証する。 濃度制約の非凸性にもかかわらず、対応する(セミ)双対問題は扱いやすく、一階勾配法で解くことができる。 本手法は,非正規化OT(極限の場合$k=1$)と二次正規化OT($k$が十分大きいときに回収される)の中間地盤とみなすことができる。 目標の滑らかさは、$k$が増加するにつれて増加し、収束速度と最適計画の間隔の間のトレードオフを引き起こす。

関連論文リスト

• Semi-Discrete Optimal Transport: Nearly Minimax Estimation With Stochastic Gradient Descent and Adaptive Entropic Regularization [38.67914746910537]
  我々は,ラゲールセル推定と密度支持推定の類似性を用いて,OTマップに対して$mathcalO(t-1)$の低いバウンダリレートを証明した。 所望の速さをほぼ達成するために,サンプル数に応じて減少するエントロピー正規化スキームを設計する。
  論文  参考訳（メタデータ） (2024-05-23T11:46:03Z)
• Anchor Space Optimal Transport: Accelerating Batch Processing of Multiple OT Problems [13.846014191157405]
  本稿では、アンカー空間最適輸送(ASOT)問題として指定された翻訳OT問題を提案する。 提案したASOT問題に対しては、分布を共有アンカー点空間にマッピングし、潜在的な共通特性を学習する。 提案したASOTに基づいて、元のOT問題に対するワッサーシュタイン距離誤差は、地価誤差によって有界であることが証明された。
  論文  参考訳（メタデータ） (2023-10-24T18:55:12Z)
• OT-Net: A Reusable Neural Optimal Transport Solver [26.153287448650126]
  新たな再利用可能なニューラルOTソルバOT-Netを提示する。 OT-Netは、ニューラルネットワークを介してブレニエの高さ表現を学び、そのポテンシャルを得る。 その後、ポテンシャルの勾配を計算することでOTマップを得た。
  論文  参考訳（メタデータ） (2023-06-14T04:11:38Z)
• Unbalanced Low-rank Optimal Transport Solvers [38.79369155558385]
  線形OT問題とFused-Gromov-Wasserstein一般化のための拡張を実装するアルゴリズムを提案する。 本研究の目的は, これら2つの系統を融合して, 汎用・スカラー・アンバランス・低ランクOTソルバの約束を実現することである。
  論文  参考訳（メタデータ） (2023-05-31T10:39:51Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Robust computation of optimal transport by $\beta$-potential regularization [79.24513412588745]
  最適輸送(OT)は、確率分布間の差を測定する機械学習分野で広く使われているツールである。 我々は、いわゆる$beta$-divergenceに付随するベータポテンシャル項でOTを正規化することを提案する。 提案アルゴリズムで計算した輸送行列は,外乱が存在する場合でも確率分布を頑健に推定するのに役立つことを実験的に実証した。
  論文  参考訳（メタデータ） (2022-12-26T18:37:28Z)
• Taming Hyperparameter Tuning in Continuous Normalizing Flows Using the JKO Scheme [60.79981399724534]
  正規化フロー (NF) は、選択された確率分布を正規分布に変換する写像である。 OTベースのCNFを$alpha$をチューニングすることなく解くアルゴリズムであるJKO-Flowを提案する。
  論文  参考訳（メタデータ） (2022-11-30T05:53:21Z)
• Kantorovich Strikes Back! Wasserstein GANs are not Optimal Transport? [138.1080446991979]
  Wasserstein Generative Adversarial Networks (WGANs) は、最適輸送(OT)理論とカントロビッチ双対性に基づく一般的な生成モデルである。 WGANの成功にもかかわらず、基礎となるOT双対解器が、発生器の更新に必要なOTコスト(Wasserstein-1 距離、$mathbbW_1$)とOT勾配をどの程度よく近似するかは、まだ不明である。 我々は1-Lipschitz関数を構築し、それらを光モノトン輸送計画の構築に用いる。この戦略は、解析的に知られたOT計画、OTコスト、OTと連続ベンチマーク分布のペアを生成する。
  論文  参考訳（メタデータ） (2022-06-15T19:07:46Z)
• Low-rank Optimal Transport: Approximation, Statistics and Debiasing [51.50788603386766]
  フロゼットボン2021ローランで提唱された低ランク最適輸送(LOT)アプローチ LOTは興味のある性質と比較した場合、エントロピー正則化の正当な候補と見なされる。 本稿では,これらの領域のそれぞれを対象とし,計算OTにおける低ランクアプローチの影響を補強する。
  論文  参考訳（メタデータ） (2022-05-24T20:51:37Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)
• Regularized Optimal Transport is Ground Cost Adversarial [34.81915836064636]
  最適輸送問題の正則化は, 地価逆数と解釈できることを示す。 これにより、地上空間上のロバストな異性度測度にアクセスでき、他のアプリケーションで使用することができる。
  論文  参考訳（メタデータ） (2020-02-10T17:28:35Z)

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

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