論文の概要: Attention Learning is Needed to Efficiently Learn Parity Function

• arxiv url: http://arxiv.org/abs/2502.07553v1
• Date: Tue, 11 Feb 2025 13:41:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-12 14:06:52.937120
• Title: Attention Learning is Needed to Efficiently Learn Parity Function
• Title（参考訳）: ペアリティ関数を効果的に学習するには注意学習が必要である
• Authors: Yaomengxi Han, Debarghya Ghoshdastidar,
• Abstract要約: 我々は$k$-parity問題で変換器を解析する。 我々は変換器が$O(k)$パラメータしか必要とせず、FFNNが必要とする理論的な下界を超えることを証明した。
• 参考スコア（独自算出の注目度）: 6.944372188747803
• License:
• Abstract: Transformers, with their attention mechanisms, have emerged as the state-of-the-art architectures of sequential modeling and empirically outperform feed-forward neural networks (FFNNs) across many fields, such as natural language processing and computer vision. However, their generalization ability, particularly for low-sensitivity functions, remains less studied. We bridge this gap by analyzing transformers on the $k$-parity problem. Daniely and Malach (NeurIPS 2020) show that FFNNs with one hidden layer and $O(nk^7 \log k)$ parameters can learn $k$-parity, where the input length $n$ is typically much larger than $k$. In this paper, we prove that FFNNs require at least $\Omega(n)$ parameters to learn $k$-parity, while transformers require only $O(k)$ parameters, surpassing the theoretical lower bound needed by FFNNs. We further prove that this parameter efficiency cannot be achieved with fixed attention heads. Our work establishes transformers as theoretically superior to FFNNs in learning parity function, showing how their attention mechanisms enable parameter-efficient generalization in functions with low sensitivity.
• Abstract（参考訳）: トランスフォーマーは、その注意機構とともに、シーケンシャルモデリングの最先端アーキテクチャとして現れ、自然言語処理やコンピュータビジョンなど、多くの分野にわたるフィードフォワードニューラルネットワーク(FFNN)を経験的に上回っている。 しかし、その一般化能力、特に低感度関数については、まだ研究されていない。 このギャップを$k$-parity問題で変換器を解析することで埋める。 Daniely and Malach (NeurIPS 2020) は、FFNNが1つの隠された層を持ち、$O(nk^7 \log k)$パラメータは$k$-parityを学習できることを示した。 本稿では、FFNNが$k$-parityを学ぶのに少なくとも$\Omega(n)$パラメータを必要とするのに対し、トランスフォーマーは$O(k)$パラメータしか必要とせず、FFNNが必要とする理論的下界を超えることを証明する。 さらに、このパラメータ効率は、固定された注目ヘッドでは達成できないことを証明した。 我々の研究は、パリティ関数の学習におけるFFNNよりも理論的に優れているトランスフォーマーを確立し、その注意機構が低感度関数におけるパラメータ効率の一般化を可能にしていることを示す。

関連論文リスト

• Optimal Memorization Capacity of Transformers [32.01426831450348]
  変換器は$tildeO(sqrtN)$パラメータでラベルを記憶でき、$N$の入力シーケンスは$n$である。 また、シーケンス・ツー・シーケンス設定における記憶能力を分析し、$tildeO(sqrtnN)$パラメータが十分であるだけでなく、ハードマックスを持つ変換器にも必要であることを示す。
  論文  参考訳（メタデータ） (2024-09-26T09:36:47Z)
• Unveiling Induction Heads: Provable Training Dynamics and Feature Learning in Transformers [54.20763128054692]
  我々は,2層変換器が$n$-gramのマルコフ連鎖データ上でICLを実行するためにどのように訓練されているかを検討する。 クロスエントロピー ICL 損失に対する勾配流が極限モデルに収束することを証明する。
  論文  参考訳（メタデータ） (2024-09-09T18:10:26Z)
• Aligning Transformers with Weisfeiler-Leman [5.0452971570315235]
  グラフニューラルネットワークアーキテクチャは、理論的によく理解された表現力を提供する$k$-WL階層と一致している。 我々は,ラプラシアンPEやSPEなどの確立した位置符号化の研究を可能にする理論的枠組みを開発する。 我々は,大規模PCQM4Mv2データセットを用いてトランスフォーマーの評価を行い,最先端のPCQM4Mv2と競合する予測性能を示した。
  論文  参考訳（メタデータ） (2024-06-05T11:06:33Z)
• p-Laplacian Transformer [7.2541371193810384]
  グラフと画像信号処理をルーツとする$p$-Laplacian正規化は、これらのデータに対する正規化効果を制御するパラメータ$p$を導入している。 まず、自己注意機構が最小のラプラシアン正規化を得ることを示す。 次に、新しい変圧器のクラス、すなわち$p$-Laplacian Transformer (p-LaT)を提案する。
  論文  参考訳（メタデータ） (2023-11-06T16:25:56Z)
• Sparse Universal Transformer [64.78045820484299]
  Universal Transformer (UT) はTransformerの変種であり、それらの層にまたがるパラメータを共有する。 本稿では,スパース・ミキチャー・オブ・エキスパート(SMoE)と新しいスティック・ブレーキング・ベースの動的停止機構を利用するスパース・ユニバーサル・トランスフォーマー(SUT)を提案する。
  論文  参考訳（メタデータ） (2023-10-11T00:38:57Z)
• Transformers as Support Vector Machines [54.642793677472724]
  自己アテンションの最適化幾何と厳密なSVM問題との間には,形式的等価性を確立する。 勾配降下に最適化された1層変圧器の暗黙バイアスを特徴付ける。 これらの発見は、最適なトークンを分離し選択するSVMの階層としてのトランスフォーマーの解釈を刺激していると信じている。
  論文  参考訳（メタデータ） (2023-08-31T17:57:50Z)
• Parameterization of Cross-Token Relations with Relative Positional Encoding for Vision MLP [52.25478388220691]
  視覚多層パーセプトロン(MLP)はコンピュータビジョンタスクにおいて有望な性能を示す。 トークンミキシングレイヤを使用して、トランスフォーマーが使用するマルチヘッド自己保持機構とは対照的に、クロストークンインタラクションをキャプチャする。 トークン混合のためのクロストークン関係を効率的に符号化する新しい位置空間ゲーティングユニット(PoSGU)を提案する。
  論文  参考訳（メタデータ） (2022-07-15T04:18:06Z)
• Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding [63.539333383965726]
  相対的位置符号化(RPE)を用いた変換器の注意計算を高速化する新しい手法を提案する。 相対的な位置符号化がToeplitz行列を形成するという観測に基づいて、Fast Fourier Transform (FFT) を用いて、RPEによるカーネル化された注意を効率的に計算できることを数学的に示す。
  論文  参考訳（メタデータ） (2021-06-23T17:51:26Z)
• NullaNet Tiny: Ultra-low-latency DNN Inference Through Fixed-function Combinational Logic [4.119948826527649]
  フィールドプログラマブルゲートアレイ(FPGA)ベースのアクセラレータは、グラフィックス処理ユニット/中央処理ユニットベースのプラットフォームを置き換える深刻な競争相手として注目を集めています。 本稿では,資源とエネルギー効率,超低遅延FPGAベースニューラルネットワークアクセラレータ構築のためのフレームワークであるNullaNet Tinyを提案する。
  論文  参考訳（メタデータ） (2021-04-07T00:16:39Z)
• $O(n)$ Connections are Expressive Enough: Universal Approximability of Sparse Transformers [71.31712741938837]
  注意層ごとに$O(n)$接続しか持たないスパース変換器は、$n2$接続を持つ高密度モデルと同じ関数クラスを近似できることを示す。 また、標準NLPタスクにおいて、異なるパターン・レベルの違いを比較検討する。
  論文  参考訳（メタデータ） (2020-06-08T18:30:12Z)

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

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