論文の概要: How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpad

• arxiv url: http://arxiv.org/abs/2406.06467v3
• Date: Fri, 01 Nov 2024 17:45:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-05 14:45:16.501342
• Title: How Far Can Transformers Reason? The Globality Barrier and Inductive Scratchpad
• Title（参考訳）: トランスフォーマーはどの程度の理由があるのか? グローバルシティバリアとインダクティブスクラッチパッド
• Authors: Emmanuel Abbe, Samy Bengio, Aryo Lotfi, Colin Sandon, Omid Saremi,
• Abstract要約: 近年の研究では、トランスフォーマーは表現性の観点からチューリング完全であることが示されているが、これは学習可能性の目的に対処するものではない。 本稿では,正規変換器が学習の弱さを効果的に達成できる場合,目標分布の「グローバル度」の概念を推し進める。 ここでは,グローバル性の高い分布を効率的に学習できないという仮定を実験的に理論的に追加して示す。
• 参考スコア（独自算出の注目度）: 23.410228115201285
• License:
• Abstract: Can Transformers predict new syllogisms by composing established ones? More generally, what type of targets can be learned by such models from scratch? Recent works show that Transformers can be Turing-complete in terms of expressivity, but this does not address the learnability objective. This paper puts forward the notion of 'globality degree' of a target distribution to capture when weak learning is efficiently achievable by regular Transformers. This measure shows a contrast with the expressivity results of Transformers captured by $TC^0/TC^1$ classes (further studied here), since the globality relates to correlations with the more limited $NC^0$ class. We show here experimentally and theoretically under additional assumptions that distributions with high globality cannot be learned efficiently. In particular, syllogisms cannot be composed on long chains. Further, we develop scratchpad techniques and show that: (i) agnostic scratchpads cannot break the globality barrier, (ii) educated scratchpads can break the globality with intermediate steps, although not all such scratchpads can generalize out-of-distribution (OOD), (iii) a notion of 'inductive scratchpad', that composes the prior information more efficiently, can both break the globality barrier and improve the OOD generalization. In particular, some of our inductive scratchpads can achieve length generalizations of up to $6\times$ for some arithmetic tasks depending on the input formatting.
• Abstract（参考訳）: トランスフォーマーは、確立したシロジズムを構成することによって、新しいシロジズムを予測することができるか? より一般的に、そのようなモデルによって、どのようなターゲットをスクラッチから学べるか? 近年の研究では、トランスフォーマーは表現性の観点からチューリング完全であることが示されているが、これは学習可能性の目的に対処するものではない。 本稿では,正規変換器が学習の弱さを効果的に達成できる場合,目標分布の「グローバル度」の概念を推し進める。 この尺度は、より制限された$NC^0$クラスと相関関係にあるため、TC^0/TC^1$クラスによってキャプチャされた変換器の表現性結果とは対照的である。 ここでは,グローバル性の高い分布を効率的に学習できないという仮定を実験的に理論的に追加して示す。 特に、シロジズムは長い鎖では構成できない。 さらに、スクラッチパッド技術を開発し、次のように示す。 一 グローバル性障壁を破ることができないこと。 (II) 教育を受けたスクラッチパッドは、中間ステップでグローバル性を破ることができるが、こうしたスクラッチパッドはすべて、アウト・オブ・ディストリビューション(OOD)を一般化できるわけではない。 三 先行情報をより効率的に構成する「誘導スクラッチパッド」の概念は、グローバル性障壁を破り、OOD一般化を改善することができる。 特に、インダクティブスクラッチパッドのいくつかは、入力フォーマットによっては最大6\times$の計算処理を実現できる。

関連論文リスト

• On the Role of Depth and Looping for In-Context Learning with Task Diversity [69.4145579827826]
  多様なタスクを伴う線形回帰のための文脈内学習について検討する。 We show that multilayer Transformer is not robust to even distributional shifts as $O(e-L)$ in Wasserstein distance。
  論文  参考訳（メタデータ） (2024-10-29T03:27:56Z)
• 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)
• Unveiling Induction Heads: Provable Training Dynamics and Feature Learning in Transformers [54.20763128054692]
  我々は,2層変換器が$n$-gramのマルコフ連鎖データ上でICLを実行するためにどのように訓練されているかを検討する。 クロスエントロピー ICL 損失に対する勾配流が極限モデルに収束することを証明する。
  論文  参考訳（メタデータ） (2024-09-09T18:10:26Z)
• In-Context Learning with Representations: Contextual Generalization of Trained Transformers [66.78052387054593]
  In-context Learning (ICL) は、事前訓練された大規模言語モデルの能力を指し、推論中にいくつか例を挙げると、新しいタスクを学習できる。 本稿では,非線形回帰タスクのレンズによる勾配降下による変圧器のトレーニングダイナミクスについて検討する。
  論文  参考訳（メタデータ） (2024-08-19T16:47:46Z)
• Aligning Transformers with Weisfeiler-Leman [5.0452971570315235]
  グラフニューラルネットワークアーキテクチャは、理論的によく理解された表現力を提供する$k$-WL階層と一致している。 我々は,ラプラシアンPEやSPEなどの確立した位置符号化の研究を可能にする理論的枠組みを開発する。 我々は,大規模PCQM4Mv2データセットを用いてトランスフォーマーの評価を行い,最先端のPCQM4Mv2と競合する予測性能を示した。
  論文  参考訳（メタデータ） (2024-06-05T11:06:33Z)
• Grokked Transformers are Implicit Reasoners: A Mechanistic Journey to the Edge of Generalization [22.033370572209744]
  我々は、トランスフォーマーがパラメトリック知識よりも暗黙的に推論できるかどうかを研究する。 我々は2つの代表的な推論タイプ、構成と比較に焦点を当てる。 トランスフォーマーは暗黙の推論を学習できるが、それはグルーキングでしか学べない。
  論文  参考訳（メタデータ） (2024-05-23T21:42:19Z)
• Transformers Can Represent $n$-gram Language Models [56.06361029539347]
  本稿では,言語モデルの単純かつ歴史的なクラスであるトランスフォーマーLMと$n$-gram LMの関係に注目した。 ハードまたはスパースアテンション機構を用いたトランスフォーマーLMは,任意の$n$-gram LMを正確に表現できることを示す。
  論文  参考訳（メタデータ） (2024-04-23T12:51:37Z)
• How Powerful are Decoder-Only Transformer Neural Models? [0.0]
  GPT-xで採用されている基礎技術のチューリング完全性に対処する最初の研究である。 単語埋め込みの空間性/圧縮性はチューリング完全性を維持する上で重要な考慮事項であることを示す。
  論文  参考訳（メタデータ） (2023-05-26T15:35:43Z)

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

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