論文の概要: Learning Linear Attention in Polynomial Time

• arxiv url: http://arxiv.org/abs/2410.10101v1
• Date: Fri, 18 Oct 2024 17:15:09 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-30 03:04:18.092789
• Title: Learning Linear Attention in Polynomial Time
• Title（参考訳）: 多項式時間における線形注意の学習
• Authors: Morris Yau, Ekin Akyurek, Jiayuan Mao, Joshua B. Tenenbaum, Stefanie Jegelka, Jacob Andreas,
• Abstract要約: 線形注意を持つ単層変圧器の学習性に関する最初の結果を提供する。 線形アテンションは RKHS で適切に定義された線形予測器とみなすことができる。 我々は,すべての経験的リスクが線形変換器と同等のトレーニングデータセットを効率的に識別する方法を示す。
• 参考スコア（独自算出の注目度）: 109.68110633996412
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Previous research has explored the computational expressivity of Transformer models in simulating Boolean circuits or Turing machines. However, the learnability of these simulators from observational data has remained an open question. Our study addresses this gap by providing the first polynomial-time learnability results (specifically strong, agnostic PAC learning) for single-layer Transformers with linear attention. We show that linear attention may be viewed as a linear predictor in a suitably defined RKHS. As a consequence, the problem of learning any linear transformer may be converted into the problem of learning an ordinary linear predictor in an expanded feature space, and any such predictor may be converted back into a multiheaded linear transformer. Moving to generalization, we show how to efficiently identify training datasets for which every empirical risk minimizer is equivalent (up to trivial symmetries) to the linear Transformer that generated the data, thereby guaranteeing the learned model will correctly generalize across all inputs. Finally, we provide examples of computations expressible via linear attention and therefore polynomial-time learnable, including associative memories, finite automata, and a class of Universal Turing Machine (UTMs) with polynomially bounded computation histories. We empirically validate our theoretical findings on three tasks: learning random linear attention networks, key--value associations, and learning to execute finite automata. Our findings bridge a critical gap between theoretical expressivity and learnability of Transformers, and show that flexible and general models of computation are efficiently learnable.
• Abstract（参考訳）: 従来、ブール回路やチューリングマシンを模擬するトランスフォーマーモデルの計算表現性について研究されてきた。 しかし,これらのシミュレータの観測データからの学習性には疑問が残る。 本研究は,線形注意を持つ単層トランスフォーマーに対して,最初の多項式時間学習性(特に強い,無依存なPAC学習)を提供することにより,このギャップに対処する。 線形アテンションは RKHS で適切に定義された線形予測器とみなすことができる。 その結果、任意の線形変圧器を学習する問題は、拡張された特徴空間において通常の線形変圧器を学習する問題に変換でき、そのような予測器をマルチヘッド線形変圧器に変換することができる。 一般化に移行して、データを生成する線形変換器に対して、すべての経験的リスク最小化器が等価(自明な対称性まで)なトレーニングデータセットを効率的に識別する方法を示し、学習モデルが全ての入力に対して正しく一般化されることを保証する。 最後に,線形注意で表現可能な計算の例として,連想記憶,有限オートマトン,多項式境界計算履歴を持つUniversal Turing Machine (UTM) のクラスについて述べる。 ランダムな線形アテンションネットワークの学習,キー値アソシエーションの学習,有限オートマトン実行の学習という3つの課題に関する理論的知見を実証的に検証した。 本研究は,トランスフォーマーの理論的表現性と学習性の間に重要なギャップを埋め,フレキシブルで汎用的な計算モデルが効率的に学習可能であることを示す。

関連論文リスト

• Can Looped Transformers Learn to Implement Multi-step Gradient Descent for In-context Learning? [69.4145579827826]
  収束ランドスケープの勾配非性アルゴリズムにもかかわらず、回帰損失に高速な流れを示す。 この設定における多層トランスの理論的解析はこれが初めてである。
  論文  参考訳（メタデータ） (2024-10-10T18:29:05Z)
• Learning Linear Dynamics from Bilinear Observations [8.238163867581848]
  本稿では,線形状態遷移と双線形観測を併用した部分的に観察された力学系の実現について考察する。 プロセスと測定ノイズの非常に穏やかな仮定の下で、未知の力学行列を学習するための有限時間解析を提供する。
  論文  参考訳（メタデータ） (2024-09-24T23:11:47Z)
• Minimum-Norm Interpolation Under Covariate Shift [14.863831433459902]
  高次元線形回帰に関する非分布研究は、テキシトベニンオーバーフィッティング(textitbenign overfitting)として知られる現象の同定につながった。 本稿では,移動学習環境における線形補間器の非漸近的過剰リスク境界を初めて証明する。
  論文  参考訳（メタデータ） (2024-03-31T01:41:57Z)
• In-Context Convergence of Transformers [63.04956160537308]
  勾配降下法により訓練したソフトマックスアテンションを有する一層変圧器の学習力学について検討した。 不均衡な特徴を持つデータに対しては、学習力学が段階的に収束する過程をとることを示す。
  論文  参考訳（メタデータ） (2023-10-08T17:55:33Z)
• Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection [88.23337313766353]
  この研究はまず、変換器がICLを実行するための包括的な統計理論を提供する。 コンテクストにおいて、トランスフォーマーは、幅広い種類の標準機械学習アルゴリズムを実装可能であることを示す。 エンフィングル変換器は、異なるベースICLアルゴリズムを適応的に選択することができる。
  論文  参考訳（メタデータ） (2023-06-07T17:59:31Z)
• Learning Functional Transduction [9.926231893220063]
  そこで本研究では,トランスダクティブ回帰の原理を勾配降下によりメタ学習し,より効率的なインコンテキスト・ニューラル近似器を構築できることを示す。 我々は、データが少ない外部要因の影響を受け、複雑な物理システムをモデル化するためのメタ学習型トランスダクティブアプローチの利点を実証する。
  論文  参考訳（メタデータ） (2023-02-01T09:14:28Z)
• Transformers as Algorithms: Generalization and Implicit Model Selection in In-context Learning [23.677503557659705]
  In-context Learning (ICL) は、トランスフォーマーモデルが一連の例で動作し、オンザフライで推論を行うプロンプトの一種である。 我々は,このトランスモデルを学習アルゴリズムとして扱い,推論時別のターゲットアルゴリズムを実装するためのトレーニングを通じて専門化することができる。 変換器は適応学習アルゴリズムとして機能し、異なる仮説クラス間でモデル選択を行うことができることを示す。
  論文  参考訳（メタデータ） (2023-01-17T18:31:12Z)
• What learning algorithm is in-context learning? Investigations with linear models [87.91612418166464]
  本稿では,トランスフォーマーに基づくインコンテキスト学習者が標準学習アルゴリズムを暗黙的に実装する仮説について検討する。 訓練された文脈内学習者は、勾配降下、隆起回帰、および正確な最小二乗回帰によって計算された予測値と密に一致していることを示す。 文脈内学習者がこれらの予測器とアルゴリズム的特徴を共有するという予備的証拠。
  論文  参考訳（メタデータ） (2022-11-28T18:59:51Z)
• Masked Language Modeling for Proteins via Linearly Scalable Long-Context Transformers [42.93754828584075]
  我々は、高速注意Via Orthogonal Random機能(FAVOR)に基づく新しいトランスフォーマーアーキテクチャPerformerを提案する。 我々の機構は、列内のトークンの数で2次ではなく2次的にスケールし、四次空間の複雑さが特徴であり、スパーシティパターンの先行を含まない。 これは強い理論的保証を与える:注意行列の偏りのない推定と一様収束である。
  論文  参考訳（メタデータ） (2020-06-05T17:09:16Z)
• Provable Meta-Learning of Linear Representations [114.656572506859]
  我々は、複数の関連するタスクから共通の機能の集合を学習し、その知識を新しい未知のタスクに転送する、という2つの課題に対処する、高速でサンプル効率のアルゴリズムを提供する。 また、これらの線形特徴を学習する際のサンプルの複雑さに関する情報理論の下限も提供する。
  論文  参考訳（メタデータ） (2020-02-26T18:21:34Z)

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

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