論文の概要: Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descent

• arxiv url: http://arxiv.org/abs/2504.04702v1
• Date: Mon, 07 Apr 2025 03:08:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-08 14:13:15.715196
• Title: Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descent
• Title（参考訳）: グラディエント老化によるブール論理学習における言語モデルの確率的失敗
• Authors: Bo Chen, Zhenmei Shi, Zhao Song, Jiahao Zhang,
• Abstract要約: 勾配法を用いて学習すると,トランスフォーマーが真に単純な多数関数を学習できるかどうかを検討する。 我々の分析は、$mathrmpoly(d)$グラデーションクエリ後も、Transformerモデルの一般化誤差は依然としてかなり大きいことを証明している。
• 参考スコア（独自算出の注目度）: 15.291830857281015
• License:
• Abstract: Recent advancements in Transformer-based architectures have led to impressive breakthroughs in natural language processing tasks, with models such as GPT-4, Claude, and Gemini demonstrating human-level reasoning abilities. However, despite their high performance, concerns remain about the inherent limitations of these models, especially when it comes to learning basic logical functions. While complexity-theoretic analyses indicate that Transformers can represent simple logic functions (e.g., $\mathsf{AND}$, $\mathsf{OR}$, and majority gates) by its nature of belonging to the $\mathsf{TC}^0$ class, these results assume ideal parameter settings and do not account for the constraints imposed by gradient descent-based training methods. In this work, we investigate whether Transformers can truly learn simple majority functions when trained using gradient-based methods. We focus on a simplified variant of the Transformer architecture and consider both $n=\mathrm{poly}(d)$ and $n=\exp(\Omega(d))$ number of training samples, where each sample is a $d$-size binary string paired with the output of a basic majority function. Our analysis demonstrates that even after $\mathrm{poly}(d)$ gradient queries, the generalization error of the Transformer model still remains substantially large, growing exponentially with $d$. This work highlights fundamental optimization challenges in training Transformers for the simplest logical reasoning tasks and provides new insights into their theoretical limitations.
• Abstract（参考訳）: トランスフォーマーベースのアーキテクチャの最近の進歩は、GPT-4、Claude、Geminiといったモデルが人間のレベルの推論能力を示すなど、自然言語処理タスクにおいて驚くべきブレークスルーをもたらしている。 しかし、高い性能にもかかわらず、これらのモデルの本質的な制限、特に基本的な論理関数の学習に関して懸念が残る。 複雑性理論分析は、Transformerが単純な論理関数(例えば、$\mathsf{AND}$, $\mathsf{OR}$, and majority gates)を、$\mathsf{TC}^0$クラスに属する性質で表現できることを示しているが、これらの結果は理想的なパラメータ設定を仮定し、勾配勾配に基づくトレーニングメソッドによって課される制約を考慮しない。 本研究では,変圧器が勾配法を用いて訓練された場合,単純な多数関数を真に学習できるかどうかを考察する。 我々は Transformer アーキテクチャの簡易版に焦点をあて,$n=\mathrm{poly}(d)$ と $n=\exp(\Omega(d))$ のトレーニングサンプル数を考える。 我々の分析は、$\mathrm{poly}(d)$グラデーションクエリ後も、Transformerモデルの一般化誤差は依然としてかなり大きく、$d$で指数関数的に増加することを示した。 この研究は、最も単純な論理的推論タスクのためにトランスフォーマーを訓練する際の基本的な最適化課題を強調し、理論上の制約に対する新たな洞察を提供する。

関連論文リスト

• Circuit Complexity Bounds for RoPE-based Transformer Architecture [25.2590541420499]
  経験的証拠は、$mathsfRoPE$ベースのTransformerアーキテクチャは、従来のTransformerモデルよりも優れた一般化能力を示していることを示している。 我々は、$mathsfTC0 = mathsfNC1$, a $mathsfRoPE$-based Transformer with $mathrmpoly(n)$-precision, $O(1)$ layer, hidden dimension $d leq O(n)$が算術式評価問題を解くことができないことを示す。
  論文  参考訳（メタデータ） (2024-11-12T07:24:41Z)
• 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 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)
• Learning on Transformers is Provable Low-Rank and Sparse: A One-layer Analysis [63.66763657191476]
  低ランク計算としての効率的な数値学習と推論アルゴリズムはトランスフォーマーに基づく適応学習に優れた性能を持つことを示す。 我々は、等級モデルが適応性を改善しながら一般化にどのように影響するかを分析する。 適切なマグニチュードベースのテストは,テストパフォーマンスに多少依存している,と結論付けています。
  論文  参考訳（メタデータ） (2024-06-24T23:00:58Z)
• Towards a Theoretical Understanding of the 'Reversal Curse' via Training Dynamics [45.69328374321502]
  自動回帰型大言語モデル(LLM)は、多くの複雑な推論タスクを解くのに優れた能力を示す。 LLM は、2つの文が意味的に同一であっても、推論中に '$B get A$' と結論付けることができない。 2つの自己回帰モデルに対する勾配降下のトレーニング力学を用いて、理論的に逆の呪いを解析する。
  論文  参考訳（メタデータ） (2024-05-07T21:03:51Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。 この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
  論文  参考訳（メタデータ） (2024-02-20T10:11:03Z)
• How do Transformers perform In-Context Autoregressive Learning? [76.18489638049545]
  簡単な次のトークン予測タスクでTransformerモデルをトレーニングする。 トレーニングされたTransformerが、まず$W$ in-contextを学習し、次に予測マッピングを適用することで、次のトークンを予測する方法を示す。
  論文  参考訳（メタデータ） (2024-02-08T16:24:44Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  低深度変換器は任意の有限状態オートマトンを計算できる。 我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。 さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
  論文  参考訳（メタデータ） (2022-10-19T17:45:48Z)

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

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