論文の概要: Learning Compositional Functions with Transformers from Easy-to-Hard Data

• arxiv url: http://arxiv.org/abs/2505.23683v1
• Date: Thu, 29 May 2025 17:22:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-30 18:14:08.032153
• Title: Learning Compositional Functions with Transformers from Easy-to-Hard Data
• Title（参考訳）: 簡単なハードデータから変換器による合成関数の学習
• Authors: Zixuan Wang, Eshaan Nichani, Alberto Bietti, Alex Damian, Daniel Hsu, Jason D. Lee, Denny Wu,
• Abstract要約: 我々は、$k$入力置換と$k$隠れ置換のインターリーブ構成を計算しなければならない$k$フォールド合成タスクの学習可能性について検討する。 この関数クラスは、$O(log k)$-depth変換器への勾配降下により、実行時とサンプルを$k$で効率的に学習できることを示す。
• 参考スコア（独自算出の注目度）: 63.96562216704653
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Transformer-based language models have demonstrated impressive capabilities across a range of complex reasoning tasks. Prior theoretical work exploring the expressive power of transformers has shown that they can efficiently perform multi-step reasoning tasks involving parallelizable computations. However, the learnability of such constructions, particularly the conditions on the data distribution that enable efficient learning via gradient-based optimization, remains an open question. Towards answering this question, in this work we study the learnability of the $k$-fold composition task, which requires computing an interleaved composition of $k$ input permutations and $k$ hidden permutations, and can be expressed by a transformer with $O(\log k)$ layers. On the negative front, we prove a Statistical Query (SQ) lower bound showing that any SQ learner that makes only polynomially-many queries to an SQ oracle for the $k$-fold composition task distribution must have sample size exponential in $k$, thus establishing a statistical-computational gap. On the other hand, we show that this function class can be efficiently learned, with runtime and sample complexity polynomial in $k$, by gradient descent on an $O(\log k)$-depth transformer via two different curriculum learning strategies: one in which data consists of $k'$-fold composition functions with $k' \le k$ presented in increasing difficulty, and another in which all such data is presented simultaneously. Our work sheds light on the necessity and sufficiency of having both easy and hard examples in the data distribution for transformers to learn complex compositional tasks.
• Abstract（参考訳）: トランスフォーマーベースの言語モデルは、様々な複雑な推論タスクで印象的な機能を示している。 変圧器の表現力を探る以前の理論的研究は、並列化可能な計算を含む多段階推論タスクを効率的に実行できることを示してきた。 しかし、そのような構成の学習性、特に勾配に基づく最適化による効率的な学習を可能にするデータ分布の条件は未解決のままである。 この問題に対処するために、本研究では、$k$の入力置換と$k$の隠れ置換のインターリーブ構成を計算し、$O(\log k)$層で変換器で表現できる$k$の合成タスクの学習可能性について研究する。 負の面では、$k$の合成タスク分布に対してSQオラクルに対して多項式的に多くのクエリしか生成しないSQ学習者は、サンプルサイズを$k$で指数関数化して統計的計算ギャップを確立する必要があることを示す。 一方、この関数クラスは、実行時およびサンプル複雑性多項式を$k$で効率よく学習でき、2つの異なるカリキュラム学習戦略により、$O(\log k)$-depth変換器への勾配降下により、2つの異なるカリキュラム学習戦略が示される。 我々の研究は、トランスフォーマーが複雑な構成タスクを学ぶために、データ配布において簡単かつ難しい例を持つことの必要性と十分性に光を当てています。

関連論文リスト

• Learning the symmetric group: large from small [44.99833362998488]
  置換予測を訓練したトランスフォーマーニューラルネットは、100%近い精度で対称群$S_25$に一般化できることを示す。 可変語長を管理するためのキーツールとしてアイデンティティ拡張を採用し、隣接する転置のトレーニングには分割ウィンドウを用いる。
  論文  参考訳（メタデータ） (2025-02-18T10:28:25Z)
• Sampling Foundational Transformer: A Theoretical Perspective [12.7600763629179]
  本稿では,複数のデータモダリティを扱える基本サンプリング変換器(SFT)を提案する。 SFTは多くのベンチマークで競合する結果を得たが、他の非常に特殊なモデルに比べて推論が速い。
  論文  参考訳（メタデータ） (2024-08-11T16:53:09Z)
• The Balanced-Pairwise-Affinities Feature Transform [2.3020018305241337]
  BPA機能変換は、入力項目のセットの機能をアップグレードして、下流のマッチングや関連するタスクのグループ化を容易にするように設計されている。 特定の min- Cost-max-flow の分数マッチング問題は、効率的、微分可能、同変、パラメータレス、確率論的に解釈可能な変換をもたらす。 経験的には、この変換はその使用において非常に効果的で柔軟性があり、様々なタスクやトレーニングスキームにおいて挿入されるネットワークを継続的に改善する。
  論文  参考訳（メタデータ） (2024-06-25T14:28:05Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Theoretical Understanding of In-Context Learning in Shallow Transformers with Unstructured Data [21.242708937367865]
  大規模言語モデル(LLM)は、文脈内学習(ICL)を通じて推論段階で概念を学習できる強力なモデルである。 本稿では,トランスアーキテクチャにおける各コンポーネントの役割を考察し,アーキテクチャの成功を説明する理論的理解を提供する。
  論文  参考訳（メタデータ） (2024-02-01T16:39:45Z)
• What Dense Graph Do You Need for Self-Attention? [73.82686008622596]
  我々はハイパーキューブにおけるトークンインタラクションをモデル化し、バニラ変換器と同等あるいはそれ以上の結果を示すスパーストランスフォーマーHypercube Transformerを提案する。 様々なシーケンス長を必要とするタスクの実験は、グラフ関数の検証をうまく行いました。
  論文  参考訳（メタデータ） (2022-05-27T14:36:55Z)
• On the Theory of Transfer Learning: The Importance of Task Diversity [114.656572506859]
  一般的な関数クラス$mathcalF circ MathcalH$において、$f_j circ h$という形の関数によってパラメータ化される$t+1$タスクを考える。 多様なトレーニングタスクに対して、最初の$t$のトレーニングタスク間で共有表現を学ぶのに必要なサンプルの複雑さが、$C(mathcalH) + t C(mathcalF)$であることを示す。
  論文  参考訳（メタデータ） (2020-06-20T20:33:59Z)
• $O(n)$ Connections are Expressive Enough: Universal Approximability of Sparse Transformers [71.31712741938837]
  注意層ごとに$O(n)$接続しか持たないスパース変換器は、$n2$接続を持つ高密度モデルと同じ関数クラスを近似できることを示す。 また、標準NLPタスクにおいて、異なるパターン・レベルの違いを比較検討する。
  論文  参考訳（メタデータ） (2020-06-08T18:30:12Z)

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

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