論文の概要: The Expressive Power of Transformers with Chain of Thought
- arxiv url: http://arxiv.org/abs/2310.07923v3
- Date: Wed, 18 Oct 2023 02:38:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-19 12:48:42.907329
- Title: The Expressive Power of Transformers with Chain of Thought
- Title(参考訳): 思考の連鎖を持つ変圧器の表現力
- Authors: William Merrill and Ashish Sabharwal
- Abstract要約: 実際には、トランスフォーマーの推論は、答える前に中間トークン列を生成および条件にすることで改善することができる。
答えはYESであるが、増加量は中間生成量に大きく依存する。
また, 線形ステップでは, コンテクストに敏感な言語に変換器デコーダを配置し, 解解時間問題のクラスを正確に認識させる。
- 参考スコア(独自算出の注目度): 35.25166532364007
- 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 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 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つのノードが接続されているかどうかの確認や有限状態マシンのシミュレートなど、驚くほど単純な推論の問題が特定されている。
しかし、実際には、トランスフォーマーの推論は「思考の連鎖」または「スクラッチパッド」、すなわち答えの前に中間トークン列の生成と条件を使用することによって改善することができる。
このような中間生成はデコーダのみのトランスフォーマーの計算能力を根本的に拡張するのでしょうか?
答えはイエスであるが、増加量は中間世代の量に大きく依存する。
例えば、対数的な数の復号ステップ(w.r.t. 入力長)を持つ復号器デコーダが標準変圧器の限界をわずかに押し上げるのに対して、線形数の復号器デコーダは、すべての正規言語を認識する明確な新しい能力(標準的な複雑性予想の下で)を付加する。
また, 線形ステップは, トランスフォーマーデコーダを文脈に敏感な言語に保持し, 多項式ステップは多項式時間可解問題のクラスを正確に認識する。
本研究の結果は, トランスフォーマーの思考チェーンの長さが, その推論能力に与える影響を理解するための, 微妙な枠組みを提供する。
関連論文リスト
- Transformers are Expressive, But Are They Expressive Enough for
Regression? [43.123290672073814]
我々は変換器が連続関数を確実に近似するのに苦労し、分割的に一定間隔の近似に頼っていることを論じる。
我々の貢献には、関数近似におけるトランスフォーマーの極限の根元を示す理論的解析と、その限界を検証するための広範な実験が含まれる。
論文 参考訳(メタデータ) (2024-02-23T18:12:53Z) - On the Expressive Power of a Variant of the Looped Transformer [83.30272757948829]
我々はアルゴリズム能力でトランスフォーマーを強化するために、AlgoFormerと呼ばれる新しいトランスフォーマーブロックを設計する。
提案したAlgoFormerは、同じ数のパラメータを使用する場合、アルゴリズム表現においてはるかに高い精度を達成することができる。
いくつかの理論的および実証的な結果は、設計されたトランスフォーマーが、人間設計のアルゴリズムよりも賢い可能性があることを示している。
論文 参考訳(メタデータ) (2024-02-21T07:07:54Z) - Chain of Thought Empowers Transformers to Solve Inherently Serial
Problems [62.91077241315318]
思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。
この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
論文 参考訳(メタデータ) (2024-02-20T10:11:03Z) - An Introduction to Transformers [23.915718146956355]
Transformerは、有用なシーケンスやデータポイントのセットを学ぶために使用できるニューラルネットワークコンポーネントである。
本稿では,トランスアーキテクチャの数学的,正確,直感的,クリーンな記述を目指す。
論文 参考訳(メタデータ) (2023-04-20T14:54:19Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。