論文の概要: Adaptive Sampled Softmax with Inverted Multi-Index: Methods, Theory and Applications

• arxiv url: http://arxiv.org/abs/2501.08563v1
• Date: Wed, 15 Jan 2025 04:09:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-16 15:52:06.720865
• Title: Adaptive Sampled Softmax with Inverted Multi-Index: Methods, Theory and Applications
• Title（参考訳）: 逆多重インデックスを用いた適応サンプリングソフトマックス:方法、理論、応用
• Authors: Jin Chen, Jin Zhang, Xu huang, Yi Yang, Defu Lian, Enhong Chen,
• Abstract要約: MIDX-Samplerは、逆多重インデックスアプローチに基づく新しい適応型サンプリング戦略である。 本手法は, サンプリングバイアス, 勾配バイアス, 収束速度, 一般化誤差境界などの重要な問題に対処するため, 厳密な理論的解析によって裏付けられている。
• 参考スコア（独自算出の注目度）: 79.53938312089308
• License:
• Abstract: The softmax function is a cornerstone of multi-class classification, integral to a wide range of machine learning applications, from large-scale retrieval and ranking models to advanced large language models. However, its computational cost grows linearly with the number of classes, which becomes prohibitively expensive in scenarios with millions or even billions of classes. The sampled softmax, which relies on self-normalized importance sampling, has emerged as a powerful alternative, significantly reducing computational complexity. Yet, its estimator remains unbiased only when the sampling distribution matches the true softmax distribution. To improve both approximation accuracy and sampling efficiency, we propose the MIDX Sampler, a novel adaptive sampling strategy based on an inverted multi-index approach. Concretely, we decompose the softmax probability into several multinomial probabilities, each associated with a specific set of codewords and the last associated with the residual score of queries, thus reducing time complexity to the number of codewords instead of the number of classes. To further boost efficiency, we replace the query-specific residual probability with a simple uniform distribution, simplifying the computation while retaining high performance. Our method is backed by rigorous theoretical analysis, addressing key concerns such as sampling bias, gradient bias, convergence rates, and generalization error bounds. The results demonstrate that a smaller divergence from the ideal softmax distribution leads to faster convergence and improved generalization. Extensive experiments on large-scale language models, sequential recommenders, and extreme multi-class classification tasks confirm that the MIDX-Sampler delivers superior effectiveness and efficiency compared to existing approaches.
• Abstract（参考訳）: ソフトマックス関数は、大規模検索やランキングモデルから高度な大規模言語モデルまで、幅広い機械学習アプリケーションに不可欠なマルチクラス分類の基盤である。 しかし、その計算コストはクラスの数とともに直線的に増加し、数百万から数十億のクラスを持つシナリオでは違法に高価になる。 自己正規化された重要度サンプリングに依存するサンプルソフトマックスは、計算複雑性を著しく低減する強力な代替手段として登場した。 しかし、サンプリング分布が真のソフトマックス分布と一致する場合のみ、その推定器は非バイアスのままである。 近似精度とサンプリング効率の両方を改善するために,逆多重インデックスアプローチに基づく新しい適応型サンプリング手法であるMIDXサプラーを提案する。 具体的には、ソフトマックス確率を複数の多項確率に分解し、それぞれが特定のコードワードのセットに関連付けられ、最後にはクエリの残余スコアに関連付けられ、クラス数ではなくコードワードの数に時間的複雑さを減少させる。 さらに効率を高めるために,クエリ固有残差確率を一様分布に置き換え,高い性能を維持しながら計算を簡素化する。 本手法は, サンプリングバイアス, 勾配バイアス, 収束速度, 一般化誤差境界などの重要な問題に対処するため, 厳密な理論的解析によって裏付けられている。 その結果、理想的なソフトマックス分布からの発散がより早く収束し、一般化が向上することを示した。 MIDX-Samplerは,大規模言語モデル,シーケンシャルレコメンデータ,および極端な多クラス分類タスクにおいて,既存の手法に比べて優れた効率性と効率性を提供することを確認した。

関連論文リスト

• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Federated Conditional Stochastic Optimization [110.513884892319]
  条件付き最適化は、不変学習タスク、AUPRC、AMLなど、幅広い機械学習タスクで見られる。 本稿では,分散フェデレーション学習のためのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-04T01:47:37Z)
• To Softmax, or not to Softmax: that is the question when applying Active Learning for Transformer Models [24.43410365335306]
  ラベル付きデータセットを取得するための人的労力を減らすためのよく知られたテクニックは、textitActive Learning (AL)である。 本稿では,7つのデータセットに対して8つの選択肢を比較する。 ほとんどのメソッドは真に不確実なサンプル(外れ値)を特定するのに長けており、ラベル付けによってパフォーマンスが低下する。
  論文  参考訳（メタデータ） (2022-10-06T15:51:39Z)
• Fast Variational AutoEncoder with Inverted Multi-Index for Collaborative Filtering [59.349057602266]
  変分オートエンコーダ (VAE) は, 協調フィルタリングの非線形手法として拡張されている。 内積に基づくソフトマックス確率を逆多重インデックスに基づいて分解する。 FastVAEはサンプリング品質と効率の両面で最先端のベースラインを上回っます。
  論文  参考訳（メタデータ） (2021-09-13T08:31:59Z)
• Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization [85.84019017587477]
  分散的ロバストな教師付き学習は、現実世界のアプリケーションのための信頼性の高い機械学習システムを構築するための重要なパラダイムとして登場している。 Wasserstein DRSLを解くための既存のアルゴリズムは、複雑なサブプロブレムを解くか、勾配を利用するのに失敗する。 我々はmin-max最適化のレンズを通してwaserstein drslを再検討し、スケーラブルで効率的に実装可能な超勾配アルゴリズムを導出する。
  論文  参考訳（メタデータ） (2021-04-27T16:56:09Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)

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

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