論文の概要: Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers
- arxiv url: http://arxiv.org/abs/2404.04393v1
- Date: Fri, 5 Apr 2024 20:36:30 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-09 21:28:03.999126
- Title: Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers
- Title（参考訳）: Counting Like Transformer: 時間数論理をSoftmax Transformerにコンパイルする
- Authors: Andy Yang, David Chiang,
- Abstract要約: 時間カウントロジックの $textbfK_textt$[#] と RASP の $textbfC-RASP$ を紹介します。
それらが互いに等価であることを示し、これらが共に、将来のマスキング型ソフトアテンショントランスの形式的表現性に最もよく知られた下界であることを示す。
- 参考スコア（独自算出の注目度）: 8.908747084128397
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Deriving formal bounds on the expressivity of transformers, as well as studying transformers that are constructed to implement known algorithms, are both effective methods for better understanding the computational power of transformers. Towards both ends, we introduce the temporal counting logic $\textbf{K}_\text{t}$[#] alongside the RASP variant $\textbf{C-RASP}$. We show they are equivalent to each other, and that together they are the best-known lower bound on the formal expressivity of future-masked soft attention transformers with unbounded input size. We prove this by showing all $\textbf{K}_\text{t}$[#] formulas can be compiled into these transformers. As a case study, we demonstrate on paper how to use $\textbf{C-RASP}$ to construct simple transformer language models that, using greedy decoding, can only generate sentences that have given properties formally specified in $\textbf{K}_\text{t}$[#].
- Abstract（参考訳）: 変圧器の表現性に関する形式的境界の導出と、既知のアルゴリズムを実装するために構築された変圧器の研究はどちらも、変圧器の計算能力をよりよく理解するための効果的な方法である。
両端に向かって、時空カウントロジック $\textbf{K}_\text{t}$[#] と RASP の変種 $\textbf{C-RASP}$ を紹介します。
それらが互いに等価であることを示し、それらが共に、有界な入力サイズを持つ将来のマスキング型ソフトアテンショントランスの形式的表現性に最もよく知られた下界であることを示す。
すべての$\textbf{K}_\text{t}$[#]式をこれらの変換子にコンパイルできることを示す。
ケーススタディとして、greedyデコーディングを使用して、$\textbf{K}_\text{t}$[#]で正式に指定されたプロパティを持つ文しか生成できない、単純なトランスフォーマー言語モデルを構築するために、$\textbf{C-RASP}$を使用する方法を示す。
関連論文リスト
- Extracting Finite State Machines from Transformers [0.3069335774032178]
機械的解釈可能性の観点から正規言語で訓練された変圧器の訓練可能性について検討する。
有限個の記号が状態を決定するとき, 変圧器の訓練性に対して, より強い下界を経験的に見出す。
機械的な洞察により、1層トランスフォーマーが優れた長さの一般化で学習できる正規言語を特徴付けることができる。
論文 参考訳（メタデータ） (2024-10-08T13:43:50Z) - Transformers learn variable-order Markov chains in-context [10.210508887119643]
可変次マルコフ連鎖(VOMC)のICLを,データ圧縮の一形態として言語モデルを用いて検討する。
そこで本研究では, 2層変圧器は変圧器のICL性能に適合することを示した。
論文 参考訳（メタデータ） (2024-10-07T21:04:53Z) - 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) - Higher-Order Transformer Derivative Estimates for Explicit Pathwise Learning Guarantees [9.305677878388664]
本稿では, 変圧器モデルに対するすべての順序の高階微分を正確に推定することにより, 文献のギャップを埋める。
我々は,注目ヘッド数,各変圧器ブロックの深さと幅,正規化層数の観点から,すべての定数の完全明示的な推定値を得る。
実世界のトランスフォーマーは、1つのマルコフ過程の軌道のサンプルから$O(operatornamepolylog(N/sqrtN)$で学習することができる。
論文 参考訳（メタデータ） (2024-05-26T13:19:32Z) - Transformers are Expressive, But Are They Expressive Enough for Regression? [38.369337945109855]
この結果から,トランスフォーマーはスムーズな関数を確実に近似するのに苦労し,分割的に一定間隔の近似に頼っていることがわかった。
これらの課題に光を当てることで、トランスフォーマーの能力に関する洗練された理解を提唱する。
論文 参考訳（メタデータ） (2024-02-23T18:12:53Z) - AlgoFormer: An Efficient Transformer Framework with Algorithmic Structures [80.28359222380733]
アルゴリズム機能を備えたトランスフォーマーを実現するために,AlgoFormerと呼ばれる新しいトランスフォーマーフレームワークを設計する。
特に、人間の設計した学習アルゴリズムの構造に触発されて、我々のトランスフォーマーフレームワークは、タスク前処理に責任を持つ事前変換器で構成されています。
いくつかの理論的および実証的な結果は、設計されたトランスフォーマーがアルゴリズム表現と学習を行う可能性があることを示すために提示される。
論文 参考訳（メタデータ） (2024-02-21T07:07:54Z) - Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。
この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
論文 参考訳（メタデータ） (2024-02-20T10:11:03Z) - Learning Transformer Programs [78.9509560355733]
設計によって機械的に解釈可能なトランスフォーマーの訓練手順を導入する。
人書きプログラムをTransformerにコンパイルする代わりに、勾配に基づく最適化を用いてトレーニングできる改良されたTransformerを設計する。
Transformer Programsは適切なソリューションを自動的に見つけ、同等のサイズの標準のTransformerと同等に動作する。
論文 参考訳（メタデータ） (2023-06-01T20:27:01Z) - On the Power of Saturated Transformers: A View from Circuit Complexity [87.20342701232869]
飽和変圧器はハードアテンション変圧器の限界を超越していることを示す。
硬度から飽和度へのジャンプは、変換器の有効回路深さを$O(log n)$の係数で増加させると解釈できる。
論文 参考訳（メタデータ） (2021-06-30T17:09:47Z) - Scalable Transformers for Neural Machine Translation [86.4530299266897]
トランスフォーマーは、そのキャパシティとシーケンス生成の並列トレーニングのため、ニューラルネットワーク翻訳(NMT)で広く採用されている。
本稿では,異なるスケールのサブトランスフォーマーを自然に含み,パラメータを共有できる,スケーラブルなトランスフォーマーを提案する。
スケーラブルトランスフォーマーのトレーニングの難しさに対処する3段階のトレーニングスキームが提案されている。
論文 参考訳（メタデータ） (2021-06-04T04:04:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。