論文の概要: Decoding Game: On Minimax Optimality of Heuristic Text Generation Strategies
- arxiv url: http://arxiv.org/abs/2410.03968v1
- Date: Fri, 4 Oct 2024 23:18:27 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-02 15:00:17.104373
- Title: Decoding Game: On Minimax Optimality of Heuristic Text Generation Strategies
- Title（参考訳）: デコードゲーム:ヒューリスティックテキスト生成戦略の最小最適性について
- Authors: Sijin Chen, Omar Hagrass, Jason M. Klusowski,
- Abstract要約: 我々は,テキスト生成をストラテジストとネイチャーの2プレイヤーゼロサムゲームとして再定義する,包括的な理論的枠組みであるデコードゲームを提案する。
逆数自然は可能性に対して暗黙の正則化を課し、トラルニケーション正規化法は、この正則化の下での最適戦略の第一次近似である。
- 参考スコア（独自算出の注目度）: 7.641996822987559
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Decoding strategies play a pivotal role in text generation for modern language models, yet a puzzling gap divides theory and practice. Surprisingly, strategies that should intuitively be optimal, such as Maximum a Posteriori (MAP), often perform poorly in practice. Meanwhile, popular heuristic approaches like Top-$k$ and Nucleus sampling, which employ truncation and normalization of the conditional next-token probabilities, have achieved great empirical success but lack theoretical justifications. In this paper, we propose Decoding Game, a comprehensive theoretical framework which reimagines text generation as a two-player zero-sum game between Strategist, who seeks to produce text credible in the true distribution, and Nature, who distorts the true distribution adversarially. After discussing the decomposibility of multi-step generation, we derive the optimal strategy in closed form for one-step Decoding Game. It is shown that the adversarial Nature imposes an implicit regularization on likelihood maximization, and truncation-normalization methods are first-order approximations to the optimal strategy under this regularization. Additionally, by generalizing the objective and parameters of Decoding Game, near-optimal strategies encompass diverse methods such as greedy search, temperature scaling, and hybrids thereof. Numerical experiments are conducted to complement our theoretical analysis.
- Abstract（参考訳）: 復号化戦略は現代言語モデルにおけるテキスト生成において重要な役割を担っているが、ファズリングのギャップは理論と実践を分ける。
意外なことに、例えばMAP(Maximum a Posteriori)のような直感的に最適であるべき戦略は、実際は不十分であることが多い。
一方、Top-k$やNucleus sampleのような一般的なヒューリスティックなアプローチでは、条件付き次トーケン確率のトランケーションと正規化が採用されているが、理論的な正当性を欠いている。
本稿では,テキスト生成を真の分布に信頼性のあるテキストを生成しようとするストラテジストと,真の分布を逆向きに歪曲するNatureの2プレイヤーゼロサムゲームとして再定義する,包括的な理論フレームワークであるDecoding Gameを提案する。
マルチステップ生成の可逆性を議論した後、ワンステップ復号ゲームにおける閉形式の最適戦略を導出する。
逆数自然は極大化に対して暗黙の正則化を課し、トランケーション正規化法は、この正則化の下での最適戦略に対する一階近似である。
さらに,デコードゲームの目的とパラメータを一般化することにより,グリーディ探索,温度スケーリング,ハイブリッドなどの多種多様な手法を準最適に扱う。
理論的解析を補完する数値実験を行った。
関連論文リスト
- e-COP : Episodic Constrained Optimization of Policies [12.854752753529151]
本稿では,制約付き強化学習(RL)のための第1ポリシー最適化アルゴリズムを提案する。
提案アルゴリズムは, エピソード設定に適応したSoTA (non-episodic) アルゴリズムと類似あるいは良好な性能を示す。
論文 参考訳（メタデータ） (2024-06-13T20:12:09Z) - Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer [52.09480867526656]
人間の嗜好を学習する際の分布変化と不確実性の一形態として,不一致の原因を同定する。
過度な最適化を緩和するために、まず、逆選択された報酬モデルに最適なポリシーを選択する理論アルゴリズムを提案する。
報奨モデルとそれに対応する最適ポリシーの等価性を用いて、優先最適化損失と教師付き学習損失を組み合わせた単純な目的を特徴とする。
論文 参考訳（メタデータ） (2024-05-26T05:38:50Z) - Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint [56.74058752955209]
本稿では,RLHFによる強化学習を用いた生成モデルのアライメント過程について検討する。
まず、オフラインPPOやオフラインDPOのような既存の一般的な手法の主な課題を、環境の戦略的探索に欠如していると認識する。
有限サンプル理論保証を用いた効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-18T18:58:42Z) - Stackelberg Batch Policy Learning [3.5426153040167754]
バッチ強化学習(RL)は、徹底的な探索を欠いた固定されたデータのバッチから学習するタスクを定義する。
ログ化された経験から値関数モデルクラスを校正する最悪ケース最適化アルゴリズムが,バッチRLの有望なパラダイムとして登場した。
そこで我々は,新たな勾配に基づく学習アルゴリズムStackelbergLearnerを提案する。
論文 参考訳（メタデータ） (2023-09-28T06:18:34Z) - Sampling-based Reactive Synthesis for Nondeterministic Hybrid Systems [20.0212772540119]
本稿では,非決定論的ハイブリッドシステムのためのサンプリング型戦略合成アルゴリズムを提案する。
我々は,ハイブリッドシステムの進化を,非決定主義が敵対的プレイヤーである2人プレイヤゲームとしてモデル化する。
目的は、敵プレイヤーのあらゆる可能な動きの下でゴールの満足度を保証する、勝利戦略 - 反応性(ロバスト)戦略を合成することである。
論文 参考訳（メタデータ） (2023-04-14T00:45:16Z) - Fictitious Play with Maximin Initialization [1.7132914341329848]
架空のプレイは、マルチプレイヤーゲームにおけるナッシュ均衡戦略のための最も正確なスケーラブルなアルゴリズムである。
本研究では,初期戦略の度合いを考慮すれば,架空の遊びの平衡近似誤差を著しく低減できることを示す。
論文 参考訳（メタデータ） (2022-03-21T07:34:20Z) - Universal Online Convex Optimization Meets Second-order Bounds [74.0120666722487]
ユニバーサルオンライン凸最適化のための簡単な戦略を提案する。
主要なアイデアは、オリジナルのオンライン機能を処理するための専門家のセットを構築し、線形化された損失に対してメタアルゴリズムをデプロイすることである。
このようにして、私たちはブラックボックスの専門家として、既成のオンライン問題解決者をプラグインして、問題依存の後悔の限界を提供することができます。
論文 参考訳（メタデータ） (2021-05-08T11:43:49Z) - Portfolio Search and Optimization for General Strategy Game-Playing [58.896302717975445]
ローリングホライズン進化アルゴリズムに基づく最適化とアクション選択のための新しいアルゴリズムを提案する。
エージェントのパラメータとポートフォリオセットの最適化について,N-tuple Bandit Evolutionary Algorithmを用いて検討する。
エージェントの性能分析により,提案手法はすべてのゲームモードによく一般化し,他のポートフォリオ手法よりも優れることが示された。
論文 参考訳（メタデータ） (2021-04-21T09:28:28Z) - On the Impossibility of Convergence of Mixed Strategies with No Regret
Learning [10.515544361834241]
最適無後悔学習戦略の一般クラスから得られる混合戦略の収束特性について検討する。
各ステップに設定された情報を相手の実演の実証平均とする戦略のクラスを考察する。
論文 参考訳（メタデータ） (2020-12-03T18:02:40Z) - Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies
in Extensive-Form Zero-Sum Games [123.76716667704625]
我々は,不完全情報ゼロサム拡張形式ゲームにおいて,対戦相手と対決する2人の選手のチームにとって最適な戦略を見つけることの課題に焦点をあてる。
この設定では、チームができる最善のことは、ゲーム開始時の関節(つまり相関した)確率分布から潜在的にランダム化された戦略(プレイヤー1人)のプロファイルをサンプリングすることである。
各プロファイルにランダム化されるのはチームメンバーの1人だけであるプロファイルのみを用いることで、そのような最適な分布を計算するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-09-21T17:51:57Z) - Beyond UCB: Optimal and Efficient Contextual Bandits with Regression
Oracles [112.89548995091182]
我々は、文脈的帯域幅からオンライン回帰への、初めての普遍的で最適な削減を提供する。
我々のアルゴリズムは、実現可能性以上の分布仮定は必要とせず、コンテキストが逆選択された場合でも機能する。
論文 参考訳（メタデータ） (2020-02-12T11:33:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。