論文の概要: Transformers Learn Shortcuts to Automata

• arxiv url: http://arxiv.org/abs/2210.10749v2
• Date: Tue, 2 May 2023 14:16:15 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-03 17:44:23.064457
• Title: Transformers Learn Shortcuts to Automata
• Title（参考訳）: トランスフォーマーはショートカットからオートマタを学ぶ
• Authors: Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, Cyril Zhang
• Abstract要約: 低深度変換器は任意の有限状態オートマトンを計算できる。 我々は,$O(log 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 learned by these shallow and non-recurrent models? We find that a low-depth Transformer can represent the computations of any finite-state automaton (thus, any bounded-memory algorithm), by hierarchically reparameterizing its recurrent dynamics. Our theoretical results characterize shortcut solutions, whereby a Transformer with $o(T)$ layers can exactly replicate the computation of an automaton on an input sequence of length $T$. We find that polynomial-sized $O(\log T)$-depth solutions always exist; furthermore, $O(1)$-depth simulators are surprisingly common, and can be understood using tools from Krohn-Rhodes theory and circuit complexity. 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シミュレータは驚くほど一般的であり、Krohn-Rhodes理論や回路複雑性のツールを使って理解することができる。 実験では,多種多様なオートマトンをシミュレートするために変圧器を訓練して合成実験を行い,標準訓練で近道解を学習できることを示す。 我々は,これらの解の脆性をさらに調査し,潜在的な緩和策を提案する。

関連論文リスト

• 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)
• Simulating Weighted Automata over Sequences and Trees with Transformers [5.078561931628571]
  DFAを仮定するモデルのクラスである重み付き有限オートマトン (WFAs) と重み付き木オートマトン (WTA) をシミュレートできることを示す。 我々はこれらの主張を正式に証明し、ターゲットオートマタの状態数の関数として必要とされる変換器モデルのサイズについて上限を与える。
  論文  参考訳（メタデータ） (2024-03-12T21:54:34Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。 この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
  論文  参考訳（メタデータ） (2024-02-20T10:11:03Z)
• The Parallelism Tradeoff: Limitations of Log-Precision Transformers [29.716269397142973]
  入力トークン数における算術精度が対数的である変換器は、定数深さの対数空間一様しきい値回路でシミュレートできることを示す。 これは、複雑性理論の既知の結果を用いた変圧器のパワーに関する洞察を与える。
  論文  参考訳（メタデータ） (2022-07-02T03:49:34Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。 回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
  論文  参考訳（メタデータ） (2021-07-28T04:28:55Z)
• $O(n)$ Connections are Expressive Enough: Universal Approximability of Sparse Transformers [71.31712741938837]
  注意層ごとに$O(n)$接続しか持たないスパース変換器は、$n2$接続を持つ高密度モデルと同じ関数クラスを近似できることを示す。 また、標準NLPタスクにおいて、異なるパターン・レベルの違いを比較検討する。
  論文  参考訳（メタデータ） (2020-06-08T18:30:12Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。