論文の概要: 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$ で表現可能な命令に変換器が従うことを証明します。
関連論文リスト
- Can Looped Transformers Learn to Implement Multi-step Gradient Descent for In-context Learning? [69.4145579827826]
収束ランドスケープの勾配非性アルゴリズムにもかかわらず、回帰損失に高速な流れを示す。
この設定における多層トランスの理論的解析はこれが初めてである。
論文 参考訳（メタデータ） (2024-10-10T18:29:05Z) - Can Transformers Learn $n$-gram Language Models? [77.35809823602307]
2種類のランダムな$n$-gram LMを学習するトランスフォーマーの能力について検討する。
例えば、$n$-gram LMに対する古典的な推定手法として、add-$lambda$ smoothing outperform transformerがある。
論文 参考訳（メタデータ） (2024-10-03T21:21:02Z) - Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Time [17.086679273053853]
本研究では,新しい高速近似法により,ほぼ線形時間で勾配を計算することができることを示す。
勾配の効率を改善することで、この作業がより効果的なトレーニングと長期コンテキスト言語モデルのデプロイを促進することを期待する。
論文 参考訳（メタデータ） (2024-08-23T17:16:43Z) - Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。
この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
論文 参考訳（メタデータ） (2024-02-20T10:11:03Z) - Transformers, parallel computation, and logarithmic depth [33.659870765923884]
我々は,一定数の自己注意層が,大規模並列計算の通信ラウンドを効率よくシミュレートし,シミュレートできることを示す。
論文 参考訳（メタデータ） (2024-02-14T15:54:55Z) - The Expressive Power of Transformers with Chain of Thought [29.839710738657203]
実際には、トランスフォーマーは「思考の連鎖」や「スクラッチパッド」を使用することで改善できる。
答えは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) - On the Power of Saturated Transformers: A View from Circuit Complexity [87.20342701232869]
飽和変圧器はハードアテンション変圧器の限界を超越していることを示す。
硬度から飽和度へのジャンプは、変換器の有効回路深さを$O(log n)$の係数で増加させると解釈できる。
論文 参考訳（メタデータ） (2021-06-30T17:09:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。