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

• arxiv url: http://arxiv.org/abs/2406.06467v1
• Date: Mon, 10 Jun 2024 17:05:12 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-11 12:49:35.613179
• Title: How Far Can Transformers Reason? The Locality Barrier and Inductive Scratchpad
• Title（参考訳）: 変圧器はどこまで原因があるのか? : 局所バリアとインダクティブスクラッチパッド
• Authors: Emmanuel Abbe, Samy Bengio, Aryo Lotfi, Colin Sandon, Omid Saremi,
• Abstract要約: 近年の研究では、トランスフォーマーは表現性の観点からチューリング完全であることが示されているが、これは学習可能性の目的に対処するものではない。 本稿では,弱い学習が正規変換器で効率的に達成可能な場合の「分布局所性」の概念を提唱する。
• 参考スコア（独自算出の注目度）: 23.410228115201285
• License: http://creativecommons.org/licenses/by/4.0/
• 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 'distribution locality' to capture when weak learning is efficiently achievable by regular Transformers, where the locality measures the least number of tokens required in addition to the tokens histogram to correlate nontrivially with the target. As shown experimentally and theoretically under additional assumptions, distributions with high locality cannot be learned efficiently. In particular, syllogisms cannot be composed on long chains. Furthermore, we show that (i) an agnostic scratchpad cannot help to break the locality barrier, (ii) an educated scratchpad can help if it breaks the locality at each step, (iii) a notion of 'inductive scratchpad' can both break the locality and improve the out-of-distribution generalization, e.g., generalizing to almost double input size for some arithmetic tasks.
• Abstract（参考訳）: トランスフォーマーは、確立したシロジズムを構成することによって、新しいシロジズムを予測することができるか? より一般的に、そのようなモデルによって、どのようなターゲットをスクラッチから学べるか? 近年の研究では、トランスフォーマーは表現性の観点からチューリング完全であることが示されているが、これは学習可能性の目的に対処するものではない。 本稿では, 正規変圧器が弱学習を効率的に達成できる場合の「分布局所性」の概念を提唱し, トークンヒストグラムに加えて, トークンの最小数を測定することで, ターゲットと非自明に相関する。 追加の仮定の下で実験的に理論的に示されるように、高い局所性を持つ分布は効率的には学べない。 特に、シロジズムは長い鎖では構成できない。 さらには (i)不可知のスクラッチパッドは、局所障壁を壊すのに役立ちません。 (二)各段階の局地性を損なう際には、教養のあるスクラッチパッドが役立ちます。 (三)「帰納的スクラッチパッド」という概念は、局所性を破り、分配外一般化(例えば、算術的なタスクのほぼ倍の入力サイズに一般化する)を改善することができる。

関連論文リスト

• 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)

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

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