論文の概要: The Expressive Power of Transformers with Chain of Thought

• arxiv url: http://arxiv.org/abs/2310.07923v4
• Date: Wed, 20 Mar 2024 17:55:48 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-21 22:27:37.289997
• Title: The Expressive Power of Transformers with Chain of Thought
• Title（参考訳）: 思考の連鎖を持つ変圧器の表現力
• Authors: William Merrill, Ashish Sabharwal,
• Abstract要約: 実際には「思考の連鎖」や「スクラッチパッド」を使用することで、トランスフォーマーの推論を改善することができる。 答えは「イエス」だが、増加量は中間生成量に大きく依存する。 また, 線形ステップでは, コンテクストに敏感な言語に変換器デコーダを配置することが示唆された。
• 参考スコア（独自算出の注目度）: 29.839710738657203
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent theoretical work has identified surprisingly simple reasoning problems, such as checking if two nodes in a graph are connected or simulating finite-state machines, that are provably unsolvable by standard transformers that answer immediately after reading their input. However, in practice, transformers' reasoning can be improved by allowing them to use a "chain of thought" or "scratchpad", i.e., generate and condition on a sequence of intermediate tokens before answering. Motivated by this, we ask: Does such intermediate generation fundamentally extend the computational power of a decoder-only transformer? We show that the answer is yes, but the amount of increase depends crucially on the amount of intermediate generation. For instance, we find that transformer decoders with a logarithmic number of decoding steps (w.r.t. the input length) push the limits of standard transformers only slightly, while a linear number of decoding steps, assuming a slight generalization to standard pre-norm, adds a clear new ability (under standard complexity conjectures): recognizing all regular languages. Our results also imply that linear steps keep transformer decoders within context-sensitive languages, and polynomial steps with generalized pre-norm make them recognize exactly the class of polynomial-time solvable problems -- the first exact characterization of a type of transformers in terms of standard complexity classes. Together, our results provide a nuanced framework for understanding how the length of a transformer's chain of thought or scratchpad impacts its reasoning power.
• Abstract（参考訳）: 最近の理論的研究は、グラフ内の2つのノードが接続されているか、あるいは有限状態マシンをシミュレートしているかどうかなど、驚くほど単純な推論問題を特定している。 しかし、実際には、トランスフォーマーの推論は「思考の連鎖」または「スクラッチパッド」、すなわち答えの前に中間トークン列の生成と条件を使用することによって改善することができる。 このような中間世代はデコーダのみの変換器の計算力を根本的に拡張するのか? 答えはYESであるが、増加量は中間生成量に大きく依存する。 例えば、対数的な数の復号ステップ(w.r.t. 入力長)を持つ復号器デコーダが標準変圧器の限界をわずかに押し上げるのに対して、線形な復号器デコーダは標準ノルムへのわずかな一般化を仮定して、明確な新しい能力(標準複雑性予想の下で)を加え、全ての正規言語を認識する。 また、線形ステップはコンテクストに敏感な言語内にトランスフォーマーデコーダを置き、一般化されたプレノルムを持つ多項式ステップは多項式時間解決可能問題のクラスを正確に認識する。 本研究の結果は, トランスフォーマーの思考列の長さが, 思考列の長さやスクラッチパッドの長さが, その推論能力に与える影響を理解するための, 微妙な枠組みを提供する。

関連論文リスト

• Extracting Finite State Machines from Transformers [0.3069335774032178]
  機械的解釈可能性の観点から正規言語で訓練された変圧器の訓練可能性について検討する。 有限個の記号が状態を決定するとき, 変圧器の訓練性に対して, より強い下界を経験的に見出す。 機械的な洞察により、1層トランスフォーマーが優れた長さの一般化で学習できる正規言語を特徴付けることができる。
  論文  参考訳（メタデータ） (2024-10-08T13:43:50Z)
• Transformers are Efficient Compilers, Provably [11.459397066286822]
  トランスフォーマーベースの大規模言語モデル(LLM)は、幅広い言語関連タスクにおいて驚くほど堅牢なパフォーマンスを示している。 本稿では,表現力の観点から,トランスフォーマーをコンパイラとして用いることの正式な調査に向けて第一歩を踏み出す。 代表言語であるMini-Huskyを導入し、現代のC言語の特徴をカプセル化する。
  論文  参考訳（メタデータ） (2024-10-07T20:31:13Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。 この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
  論文  参考訳（メタデータ） (2024-02-20T10:11:03Z)
• Transformers Can Achieve Length Generalization But Not Robustly [76.06308648699357]
  長さ一般化の成功は,データ形式や位置エンコーディングのタイプと密接に関連していることを示す。 標準変換器が入力長の2.5倍のシーケンス長に外挿できることを初めて示す。
  論文  参考訳（メタデータ） (2024-02-14T18:18:29Z)
• Deep Transformers without Shortcuts: Modifying Self-attention for Faithful Signal Propagation [105.22961467028234]
  ディープニューラルネットワーク(DNN)のトレーニングにおいて,スキップ接続と正規化レイヤはユビキタスである Deep Kernel Shapingのような最近のアプローチは、それらへの依存を減らすために進歩しました。 しかし、これらのアプローチは変換器に存在する自己注意層とは相容れない。
  論文  参考訳（メタデータ） (2023-02-20T21:26:25Z)
• A Logic for Expressing Log-Precision Transformers [35.25166532364007]
  本稿では,任意の対数精度変換器を一階述語論理文として等価に表現できることを示す。 これは、最も厳密な既知の上界であり、対数精度変換器の論理的特徴である。
  論文  参考訳（メタデータ） (2022-10-06T04:18:09Z)
• The Parallelism Tradeoff: Limitations of Log-Precision Transformers [29.716269397142973]
  入力トークン数における算術精度が対数的である変換器は、定数深さの対数空間一様しきい値回路でシミュレートできることを示す。 これは、複雑性理論の既知の結果を用いた変圧器のパワーに関する洞察を与える。
  論文  参考訳（メタデータ） (2022-07-02T03:49:34Z)
• Error Correction Code Transformer [92.10654749898927]
  本稿では,トランスフォーマーアーキテクチャを任意のブロック長で線形符号のソフトデコードに拡張することを提案する。 我々は,各チャネルの出力次元を高次元に符号化し,個別に処理すべきビット情報のより良い表現を行う。 提案手法は、トランスフォーマーの極端なパワーと柔軟性を示し、既存の最先端のニューラルデコーダを、その時間的複雑さのごく一部で大きなマージンで上回る。
  論文  参考訳（メタデータ） (2022-03-27T15:25:58Z)
• On the Power of Saturated Transformers: A View from Circuit Complexity [87.20342701232869]
  飽和変圧器はハードアテンション変圧器の限界を超越していることを示す。 硬度から飽和度へのジャンプは、変換器の有効回路深さを$O(log n)$の係数で増加させると解釈できる。
  論文  参考訳（メタデータ） (2021-06-30T17:09:47Z)
• Thinking Like Transformers [64.96770952820691]
  本稿では,プログラミング言語の形式で変換器エンコーダの計算モデルを提案する。 RASPは、トランスフォーマーによって確実に学習できるタスクの解決策をプログラムするのにどのように使えるかを示す。 ヒストグラム、ソート、ダイク言語のためのRASPプログラムを提供する。
  論文  参考訳（メタデータ） (2021-06-13T13:04:46Z)

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

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