論文の概要: Transformers Learn Shortcuts to Automata
- arxiv url: http://arxiv.org/abs/2210.10749v1
- Date: Wed, 19 Oct 2022 17:45:48 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-20 13:53:33.787545
- Title: Transformers Learn Shortcuts to Automata
- Title(参考訳): トランスフォーマーはショートカットからオートマタを学ぶ
- Authors: Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, Cyril
Zhang
- Abstract要約: ここでは,$o(T)$層のみを持つ浅層トランスフォーマーが,長さ$T$の入力シーケンス上でのオートマトン計算を再現可能であることを示す。
さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
- 参考スコア(独自算出の注目度): 52.015990420075944
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Algorithmic reasoning requires capabilities which are most naturally
understood through recurrent models of computation, like the Turing machine.
However, Transformer models, while lacking recurrence, are able to perform such
reasoning using far fewer layers than the number of reasoning steps. This
raises the question: what solutions are these shallow and non-recurrent models
finding? We investigate this question in the setting of learning automata,
discrete dynamical systems naturally suited to recurrent modeling and
expressing algorithmic tasks. Our theoretical results completely characterize
shortcut solutions, whereby a shallow Transformer with only $o(T)$ layers can
exactly replicate the computation of an automaton on an input sequence of
length $T$. By representing automata using the algebraic structure of their
underlying transformation semigroups, we obtain $O(\log T)$-depth simulators
for all automata and $O(1)$-depth simulators for all automata whose associated
groups are solvable. Empirically, we perform synthetic experiments by training
Transformers to simulate a wide variety of automata, and show that shortcut
solutions can be learned via standard training. We further investigate the
brittleness of these solutions and propose potential mitigations.
- Abstract(参考訳): アルゴリズム推論はチューリングマシンのような計算の繰り返しモデルによって最も自然に理解される能力を必要とする。
しかし、トランスフォーマーモデルは再帰を欠くものの、推論ステップの数よりもはるかに少ない層でそのような推論を行うことができる。
この浅さと非リカレントモデルには何の解決策があるのか?
学習オートマトンの設定において,再帰的モデリングやアルゴリズム的タスクの表現に適した離散力学系について検討する。
我々の理論的結果はショートカットの解を完全に特徴付けており、浅いトランスフォーマーは$o(T)$層しか持たず、長さ$T$の入力シーケンスでオートマトンを正確に再現することができる。
基底となる変換半群の代数構造を用いてオートマトンを表現することにより、すべてのオートマトンに対して$O(\log T)$-depthシミュレータと、関連する群が可解であるすべてのオートマトンに対して$O(1)$-depthシミュレータを得る。
実験では,多種多様なオートマトンをシミュレートするために変圧器を訓練して合成実験を行い,標準訓練で近道解を学習できることを示す。
我々は,これらの解の脆性をさらに調査し,潜在的な緩和策を提案する。
関連論文リスト
- Chain of Thought Empowers Transformers to Solve Inherently Serial
Problems [62.91077241315318]
思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。
この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
論文 参考訳(メタデータ) (2024-02-20T10:11:03Z) - Softmax-free Linear Transformers [101.01493387683898]
視覚変換器(ViT)は、視覚知覚タスクの最先端を推し進めている。
既存の手法は理論的に欠陥があるか、視覚認識に経験的に効果がないかのいずれかである。
我々はSoftmax-Free Transformers (SOFT) のファミリーを提案する。
論文 参考訳(メタデータ) (2022-07-05T03:08:27Z) - The Parallelism Tradeoff: Limitations of Log-Precision Transformers [29.716269397142973]
入力トークン数における算術精度が対数的である変換器は、定数深さの対数空間一様しきい値回路でシミュレートできることを示す。
これは、複雑性理論の既知の結果を用いた変圧器のパワーに関する洞察を与える。
論文 参考訳(メタデータ) (2022-07-02T03:49:34Z) - Mixability made efficient: Fast online multiclass logistic regression [68.8204255655161]
我々は、混合性は最適な後悔を伴うアルゴリズムを得るための強力なツールであることを示した。
結果として得られる手法は、しばしば計算の複雑さに悩まされ、実用性が低下した。
論文 参考訳(メタデータ) (2021-10-08T08:22:05Z) - Statistically Meaningful Approximation: a Case Study on Approximating
Turing Machines with Transformers [50.85524803885483]
本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。
回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
論文 参考訳(メタデータ) (2021-07-28T04:28:55Z) - Sub-Linear Memory: How to Make Performers SLiM [38.068090269482425]
vanilla Transformerは、入力長$L$の関数としてシリアル時間とメモリで$O(L2)$を必要とする。
最近の研究は、連続計算に$o(l)$でしかスケールしない様々な線形自己アテンション機構を提案している。
計算の柔軟性は顕著であり, サブリニアメモリを用いた近似をすることなく, 前方および後方の伝播を行うことができる。
論文 参考訳(メタデータ) (2020-12-21T13:56:04Z) - $O(n)$ Connections are Expressive Enough: Universal Approximability of
Sparse Transformers [71.31712741938837]
注意層ごとに$O(n)$接続しか持たないスパース変換器は、$n2$接続を持つ高密度モデルと同じ関数クラスを近似できることを示す。
また、標準NLPタスクにおいて、異なるパターン・レベルの違いを比較検討する。
論文 参考訳(メタデータ) (2020-06-08T18:30:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。