論文の概要: Log-Precision Transformers are Constant-Depth Uniform Threshold Circuits
- arxiv url: http://arxiv.org/abs/2207.00729v1
- Date: Sat, 2 Jul 2022 03:49:34 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-05 15:07:39.570421
- Title: Log-Precision Transformers are Constant-Depth Uniform Threshold Circuits
- Title(参考訳): 対数精度変換器は一様一様閾値回路である
- Authors: William Merrill and Ashish Sabharwal
- Abstract要約: 入力長の対数精度を持つ変圧器ニューラルネットワークは、一定深さの均一しきい値回路でシミュレートできることを示す。
このような変換器は$mathsfTC0$でのみ形式言語を認識する。
- 参考スコア(独自算出の注目度): 29.716269397142973
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove that transformer neural networks with logarithmic precision in the
input length (and where the feedforward subnetworks are computable using linear
space in their input length) can be simulated by constant-depth uniform
threshold circuits. Thus, such transformers only recognize formal languages in
$\mathsf{TC}^0$, the class of languages defined by constant-depth, poly-size
threshold circuits. This demonstrates a connection between a practical claim in
NLP and a theoretical conjecture in computational complexity theory: "attention
is all you need" (Vaswani et al., 2017), i.e., transformers are capable of all
efficient computation, only if all efficiently computable problems can be
solved with log space, i.e., $\mathsf L = \mathsf P$. We also construct a
transformer that can evaluate any constant-depth threshold circuit on any
input, proving that transformers can follow instructions that are representable
in $\mathsf{TC}^0$.
- Abstract(参考訳): 入力長の対数精度(およびフィードフォワードサブネットが入力長の線形空間で計算可能である場合)を持つ変圧器ニューラルネットワークは、一定深さの均一しきい値回路でシミュレート可能であることを証明した。
したがって、そのような変換器は、定数深度多値しきい値回路で定義される言語のクラスである$\mathsf{TC}^0$の形式言語しか認識しない。
これは NLP の実践的主張と、計算複雑性理論における理論的予想の関連性を示している: "attention is all you need" (Vaswani et al., 2017)、すなわち、トランスフォーマーは全ての効率的な計算が可能であり、全ての効率的な計算可能問題がログ空間で解ける場合、すなわち$\mathsf L = \mathsf P$である。
また、任意の入力に対して一定深さのしきい値回路を評価する変換器を構築し、$\mathsf{tc}^0$ で表現可能な命令に変換器が従うことを証明します。
関連論文リスト
- Chain of Thought Empowers Transformers to Solve Inherently Serial
Problems [62.91077241315318]
思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。
この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
論文 参考訳(メタデータ) (2024-02-20T10:11:03Z) - Transformers, parallel computation, and logarithmic depth [33.659870765923884]
我々は,一定数の自己注意層が,大規模並列計算の通信ラウンドを効率よくシミュレートし,シミュレートできることを示す。
論文 参考訳(メタデータ) (2024-02-14T15:54:55Z) - Towards Understanding Inductive Bias in Transformers: A View From
Infinity [10.117509279024041]
変換器は、列空間のより置換対称関数に偏りがちである。
対称群の表現論は定量的な解析的予測に利用できることを示す。
我々は、WikiTextデータセットは、実際に置換対称性の程度を持っていると主張している。
論文 参考訳(メタデータ) (2024-02-07T19:00:01Z) - The Expressive Power of Transformers with Chain of Thought [35.25166532364007]
実際には、トランスフォーマーの推論は、答える前に中間トークン列を生成および条件にすることで改善することができる。
答えはYESであるが、増加量は中間生成量に大きく依存する。
また, 線形ステップでは, コンテクストに敏感な言語に変換器デコーダを配置し, 解解時間問題のクラスを正確に認識させる。
論文 参考訳(メタデータ) (2023-10-11T22:35:18Z) - RWKV: Reinventing RNNs for the Transformer Era [54.716108899349614]
本稿では,変換器の効率的な並列化学習とRNNの効率的な推論を組み合わせた新しいモデルアーキテクチャを提案する。
モデルを最大14億のパラメータにスケールし、トレーニングされたRNNの中では最大で、同じサイズのTransformerと同等のRWKVのパフォーマンスを実現しています。
論文 参考訳(メタデータ) (2023-05-22T13:57:41Z) - Transformers Learn Shortcuts to Automata [52.015990420075944]
低深度変換器は任意の有限状態オートマトンを計算できる。
我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。
さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
論文 参考訳(メタデータ) (2022-10-19T17:45:48Z) - Your Transformer May Not be as Powerful as You Expect [88.11364619182773]
連続列列列関数を近似できるかどうかに関して, RPE ベースの変換器のパワーを数学的に解析する。
RPEをベースとしたトランスフォーマーでは,ニューラルネットワークの深さや幅がどんなに深くても近似できない連続列列列列関数が存在することを示す。
我々は,その条件を満たす,Universal RPE-based (URPE) Attentionと呼ばれる新しいアテンションモジュールを開発する。
論文 参考訳(メタデータ) (2022-05-26T14:51:30Z) - On the Power of Saturated Transformers: A View from Circuit Complexity [87.20342701232869]
飽和変圧器はハードアテンション変圧器の限界を超越していることを示す。
硬度から飽和度へのジャンプは、変換器の有効回路深さを$O(log n)$の係数で増加させると解釈できる。
論文 参考訳(メタデータ) (2021-06-30T17:09:47Z) - Stable, Fast and Accurate: Kernelized Attention with Relative Positional
Encoding [63.539333383965726]
相対的位置符号化(RPE)を用いた変換器の注意計算を高速化する新しい手法を提案する。
相対的な位置符号化がToeplitz行列を形成するという観測に基づいて、Fast Fourier Transform (FFT) を用いて、RPEによるカーネル化された注意を効率的に計算できることを数学的に示す。
論文 参考訳(メタデータ) (2021-06-23T17:51:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。