論文の概要: Most Likely Sequence Generation for $n$-Grams, Transformers, HMMs, and Markov Chains, by Using Rollout Algorithms
- arxiv url: http://arxiv.org/abs/2403.15465v1
- Date: Tue, 19 Mar 2024 19:58:46 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-26 22:41:56.482381
- Title: Most Likely Sequence Generation for $n$-Grams, Transformers, HMMs, and Markov Chains, by Using Rollout Algorithms
- Title（参考訳）: ロールアウトアルゴリズムによる$n$-Grams, Transformer, HMMs, Markov Chainsの配列生成
- Authors: Yuchao Li, Dimitri Bertsekas,
- Abstract要約: 本稿では,ChatGPTの基盤となるような$n$-gram構造を持つ変換器について考察する。
変換器は、単語列を生成するために使用できる次の単語確率を提供する。
これらの確率に基づいて,確率の高い単語列の計算方法を検討する。
- 参考スコア（独自算出の注目度）: 3.014160809522789
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper we consider a transformer with an $n$-gram structure, such as the one underlying ChatGPT. The transformer provides next word probabilities, which can be used to generate word sequences. We consider methods for computing word sequences that are highly likely, based on these probabilities. Computing the optimal (i.e., most likely) word sequence starting with a given initial state is an intractable problem, so we propose methods to compute highly likely sequences of $N$ words in time that is a low order polynomial in $N$ and in the vocabulary size of the $n$-gram. These methods are based on the rollout approach from approximate dynamic programming, a form of single policy iteration, which can improve the performance of any given heuristic policy. In our case we use a greedy heuristic that generates as next word one that has the highest probability. We show with analysis, examples, and computational experimentation that our methods are capable of generating highly likely sequences with a modest increase in computation over the greedy heuristic. While our analysis and experiments are focused on Markov chains of the type arising in transformer and ChatGPT-like models, our methods apply to general finite-state Markov chains, and related inference applications of Hidden Markov Models (HMM), where Viterbi decoding is used extensively.
- Abstract（参考訳）: 本稿では,ChatGPTの基盤となるような$n$-gram構造を持つ変圧器について考察する。
変換器は、単語列を生成するために使用できる次の単語確率を提供する。
これらの確率に基づいて,確率の高い単語列の計算方法を検討する。
与えられた初期状態から始まる最適な(最も可能性が高い)単語列を計算することは難解な問題であり、我々は$N$の低次多項式で$n$-gramのボキャブラリサイズである時間に$N$の単語列を計算する方法を提案する。
これらの手法は、任意のヒューリスティックポリシーの性能を向上させることができる単一のポリシーイテレーションの形式である、近似動的プログラミングからのロールアウトアプローチに基づいている。
私たちの場合、最も高い確率を持つ次の単語を生成する欲求的ヒューリスティックを使用します。
解析, 実例, 計算実験により, 本手法は, 強欲なヒューリスティックよりも計算量がわずかに増加し, 高い確率の列を生成することができることを示した。
解析と実験は変換器やChatGPTのようなモデルで生じる型のマルコフ連鎖に焦点が当てられているが、本手法は一般的な有限状態マルコフ連鎖や、ビタビ復号法が広く用いられるHMM(Hidden Markov Models)の関連する推論応用に適用できる。
関連論文リスト
- QWO: Speeding Up Permutation-Based Causal Discovery in LiGAMs [20.661343069864888]
QWO は与えられた置換に対して$mathcalGpi$ の計算効率を大幅に向上させる新しい手法である。
QWOは、最先端のBICベースの手法と比較して、$O(n2)$$$(n$は変数の数)のスピードアップがあり、非常にスケーラブルである。
論文 参考訳（メタデータ） (2024-10-30T16:10:46Z) - GEC-DePenD: Non-Autoregressive Grammatical Error Correction with
Decoupled Permutation and Decoding [52.14832976759585]
文法的誤り訂正(GEC)は、通常自己回帰的なシーケンス・ツー・シーケンスモデルで解決される重要なNLPタスクである。
本稿では, アーキテクチャを置換ネットワークに分離する, GEC に対する非自己回帰的アプローチを提案する。
GECの既知の非自己回帰手法よりもネットワークが向上することを示す。
論文 参考訳（メタデータ） (2023-11-14T14:24:36Z) - Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances [42.16343861129583]
オンライン学習アルゴリズムでは、シーケンス長が増加するにつれて、全体のコストが最高の$omega$に近づくように、一連のインスタンスに対してパラメータを選択できることが示される。
我々の研究は、高精度線形システム解法の最初の学習理論処理と、データ駆動型科学計算のエンドツーエンド保証を提供する。
論文 参考訳（メタデータ） (2023-10-03T17:51:42Z) - Transformers Learn Shortcuts to Automata [52.015990420075944]
低深度変換器は任意の有限状態オートマトンを計算できる。
我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。
さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
論文 参考訳（メタデータ） (2022-10-19T17:45:48Z) - Efficient and robust high-dimensional sparse logistic regression via
nonlinear primal-dual hybrid gradient algorithms [0.0]
弾性ネットペナルティによって正規化されるロジスティック回帰問題に対する解を確実に計算する反復アルゴリズムを提案する。
この結果は、一階最適化法に対して$O(min(m2n,mn2)log (1/epsilon))$の既知の複雑性境界を改善する。
論文 参考訳（メタデータ） (2021-11-30T14:16:48Z) - Recurrently Predicting Hypergraphs [30.092688729343678]
問題は、$n$要素の集合に対して$mathcalO(2n)$でスケーリング可能なマルチウェイ関係(ハイパーエッジ)の数から生じる。
そこで本研究では,提案手法の初期推定を反復的に精算することにより,入射行列を予測する再帰型ハイパーグラフニューラルネットワークを提案する。
論文 参考訳（メタデータ） (2021-06-26T01:12:41Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Determinantal Beam Search [75.84501052642361]
ビームサーチは、ニューラルシーケンスモデルをデコードするためのゴーツー戦略である。
複数のソリューションを要求するユースケースでは、多様あるいは代表的なセットがしばしば望まれる。
ビームサーチを一連の部分決定問題として繰り返し行うことにより、アルゴリズムを多種多様なサブセット選択プロセスに変換することができる。
論文 参考訳（メタデータ） (2021-06-14T13:01:46Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z) - $O(n)$ Connections are Expressive Enough: Universal Approximability of
Sparse Transformers [71.31712741938837]
注意層ごとに$O(n)$接続しか持たないスパース変換器は、$n2$接続を持つ高密度モデルと同じ関数クラスを近似できることを示す。
また、標準NLPタスクにおいて、異なるパターン・レベルの違いを比較検討する。
論文 参考訳（メタデータ） (2020-06-08T18:30:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。