論文の概要: Differentiable Top-k Operator with Optimal Transport
- arxiv url: http://arxiv.org/abs/2002.06504v2
- Date: Tue, 18 Feb 2020 18:56:09 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-31 17:41:21.549944
- Title: Differentiable Top-k Operator with Optimal Transport
- Title（参考訳）: 最適輸送を用いた微分可能トップk演算子
- Authors: Yujia Xie, Hanjun Dai, Minshuo Chen, Bo Dai, Tuo Zhao, Hongyuan Zha,
Wei Wei, Tomas Pfister
- Abstract要約: SOFTトップk演算子は、エントロピック最適輸送(EOT)問題の解として、トップk演算の出力を近似する。
提案した演算子をk-アネレスト近傍およびビーム探索アルゴリズムに適用し,性能向上を示す。
- 参考スコア（独自算出の注目度）: 135.36099648554054
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The top-k operation, i.e., finding the k largest or smallest elements from a
collection of scores, is an important model component, which is widely used in
information retrieval, machine learning, and data mining. However, if the top-k
operation is implemented in an algorithmic way, e.g., using bubble algorithm,
the resulting model cannot be trained in an end-to-end way using prevalent
gradient descent algorithms. This is because these implementations typically
involve swapping indices, whose gradient cannot be computed. Moreover, the
corresponding mapping from the input scores to the indicator vector of whether
this element belongs to the top-k set is essentially discontinuous. To address
the issue, we propose a smoothed approximation, namely the SOFT (Scalable
Optimal transport-based diFferenTiable) top-k operator. Specifically, our SOFT
top-k operator approximates the output of the top-k operation as the solution
of an Entropic Optimal Transport (EOT) problem. The gradient of the SOFT
operator can then be efficiently approximated based on the optimality
conditions of EOT problem. We apply the proposed operator to the k-nearest
neighbors and beam search algorithms, and demonstrate improved performance.
- Abstract（参考訳）: トップk演算、すなわちスコアの集合からkの最大または最小の要素を見つけることは重要なモデル要素であり、情報検索、機械学習、データマイニングに広く使われている。
しかし、トップk演算が例えばバブルアルゴリズムを用いてアルゴリズム的に実装されている場合、得られるモデルは、一般的な勾配降下アルゴリズムを用いてエンドツーエンドで訓練することはできない。
これは、これらの実装は通常、勾配を計算できないインデックスのスワップを含むためである。
さらに、入力スコアからその要素がトップk集合に属するかどうかのインジケータベクトルへの対応するマッピングは本質的に不連続である。
そこで本研究では, SOFT (Scalable Optimal transport-based diFferenTiable) top-k operator というスムーズな近似法を提案する。
具体的には、私たちのSOFTトップk演算子は、エントロピー最適輸送(EOT)問題の解として、トップk演算の出力を近似する。
これにより、EOT問題の最適条件に基づいて、SOFT演算子の勾配を効率的に近似することができる。
提案した演算子をk-アネレスト近傍およびビーム探索アルゴリズムに適用し,性能向上を示す。
関連論文リスト
- Practical First-Order Bayesian Optimization Algorithms [0.0]
本稿では,勾配GPからの情報を効率よく活用して,ゼロ勾配の潜在的な問合せ点を同定する,実用的なFOBOアルゴリズムのクラスを提案する。
提案アルゴリズムの性能をいくつかのテスト関数で検証し,提案アルゴリズムが最先端のFOBOアルゴリズムより優れていることを示す。
論文 参考訳（メタデータ） (2023-06-19T10:05:41Z) - Fast, Differentiable and Sparse Top-k: a Convex Analysis Perspective [21.6146047576295]
トップk演算子はスパースベクトルを返し、非ゼロ値は入力の k 最大の値に対応する。
我々はトップk作用素を、置換の凸包であるペルムタヘドロン上の線形プログラムとみなす。
私たちのフレームワークは既存のフレームワークよりもはるかに汎用的であり、例えば、大まかに値を選択するトップk演算子を表現できる。
論文 参考訳（メタデータ） (2023-02-02T21:32:13Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Entropic Neural Optimal Transport via Diffusion Processes [105.34822201378763]
本稿では,連続確率分布間のエントロピー最適輸送(EOT)計画を計算するための新しいアルゴリズムを提案する。
提案アルゴリズムは,シュリンガーブリッジ問題(Schr"odinger Bridge problem)として知られるEOTの動的バージョンのサドル点再構成に基づく。
大規模EOTの従来の手法とは対照的に,我々のアルゴリズムはエンドツーエンドであり,単一の学習ステップで構成されている。
論文 参考訳（メタデータ） (2022-11-02T14:35:13Z) - Bayesian Optimization over Permutation Spaces [30.650753803587794]
BOPS (Permutation Spaces) に対する2つのアルゴリズムの提案と評価を行った。
BOPS-Tの性能を理論的に解析し,その後悔がサブリニアに増加することを示す。
複数の合成および実世界のベンチマーク実験により、BOPS-TとBOPS-Hは、空間に対する最先端のBOアルゴリズムよりも優れた性能を示した。
論文 参考訳（メタデータ） (2021-12-02T08:20:50Z) - An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm
for First-order and Zeroth-order Optimization [111.24899593052851]
条件勾配アルゴリズム(Frank-Wolfeアルゴリズムとも呼ばれる)は、最近、機械学習コミュニティで人気を取り戻している。
ARCSは、ゼロ階最適化において凸問題を解く最初のゼロ階条件勾配スライディング型アルゴリズムである。
1次最適化では、ARCSの収束結果は、勾配クエリのオラクルの数で、従来のアルゴリズムよりも大幅に優れていた。
論文 参考訳（メタデータ） (2021-09-18T07:08:11Z) - Bayesian Algorithm Execution: Estimating Computable Properties of
Black-box Functions Using Mutual Information [78.78486761923855]
多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。
本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。
これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
論文 参考訳（メタデータ） (2021-04-19T17:22:11Z) - Efficient Optimal Transport Algorithm by Accelerated Gradient descent [20.614477547939845]
本稿では,ネステロフの平滑化手法に基づく効率と精度をさらに向上させる新しいアルゴリズムを提案する。
提案手法は,同じパラメータでより高速な収束と精度を実現する。
論文 参考訳（メタデータ） (2021-04-12T20:23:29Z) - Efficient Nonnegative Tensor Factorization via Saturating Coordinate
Descent [16.466065626950424]
本稿では,要素選択手法を用いた高速かつ効率的なNTFアルゴリズムを提案する。
経験的解析により,提案アルゴリズムはテンソルサイズ,密度,ランクの点でスケーラブルであることがわかった。
論文 参考訳（メタデータ） (2020-03-07T12:51:52Z) - Variance Reduction with Sparse Gradients [82.41780420431205]
SVRGやSpiderBoostのような分散還元法では、大きなバッチ勾配と小さなバッチ勾配が混在している。
我々は、新しい空間演算子:ランダムトップk演算子を導入する。
我々のアルゴリズムは、画像分類、自然言語処理、スパース行列分解など様々なタスクにおいて、一貫してSpiderBoostより優れています。
論文 参考訳（メタデータ） (2020-01-27T08:23:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。