論文の概要: Algorithmic Capture, Computational Complexity, and Inductive Bias of Infinite Transformers
- arxiv url: http://arxiv.org/abs/2603.11161v1
- Date: Wed, 11 Mar 2026 18:00:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-13 14:46:25.552487
- Title: Algorithmic Capture, Computational Complexity, and Inductive Bias of Infinite Transformers
- Title（参考訳）: 無限変圧器のアルゴリズム捕捉, 計算複雑度, 誘導バイアス
- Authors: Orit Davidovich, Zohar Ringel,
- Abstract要約: 我々は、アルゴリズムキャプチャー(すなわち、アルゴリズムをグラッキングする)を、制御可能なエラーと最小限のサンプル適応で任意の問題サイズに一般化するニューラルネットワークの能力として定義する。
汎用表現性にもかかわらず、変換器は効率の良い多項式時間ヒューリスティックスキーム(EPTHS)クラス内の低複素性アルゴリズムに対して帰納的バイアスを有することを示す。
- 参考スコア（独自算出の注目度）: 6.073192384885002
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We formally define Algorithmic Capture (i.e., ``grokking'' an algorithm) as the ability of a neural network to generalize to arbitrary problem sizes ($T$) with controllable error and minimal sample adaptation, distinguishing true algorithmic learning from statistical interpolation. By analyzing infinite-width transformers in both the lazy and rich regimes, we derive upper bounds on the inference-time computational complexity of the functions these networks can learn. We show that despite their universal expressivity, transformers possess an inductive bias towards low-complexity algorithms within the Efficient Polynomial Time Heuristic Scheme (EPTHS) class. This bias effectively prevents them from capturing higher-complexity algorithms, while allowing success on simpler tasks like search, copy, and sort.
- Abstract（参考訳）: 我々は、アルゴリズムキャプチャ(アルゴリズムの「グロッキング」)を、制御可能なエラーと最小限のサンプル適応で任意の問題サイズ(T$)に一般化するニューラルネットワークの能力として定義し、真のアルゴリズム学習と統計的補間を区別する。
遅延状態とリッチ状態の両方において無限幅変換器を解析することにより、これらのネットワークが学習できる関数の推論時計算複雑性の上限を導出する。
汎用表現性にもかかわらず、変換器は効率の良い多項式時間ヒューリスティックスキーム(EPTHS)クラス内の低複素性アルゴリズムに対して帰納的バイアスを有することを示す。
このバイアスは、検索、コピー、ソートといった単純なタスクで成功しながら、より複雑なアルゴリズムのキャプチャを効果的に妨げます。
関連論文リスト
- Halving the Cost of Quantum Algorithms with Randomization [0.138120109831448]
量子信号処理(QSP)は、線形演算子の変換を実装するための体系的なフレームワークを提供する。
近年の研究では、量子チャネルへのユニタリゲートを促進する技術であるランダム化コンパイルが開発されている。
提案アルゴリズムは, 平均進化が対象関数に収束するように戦略的に選択されたランダム化の確率的混合を実装し, 誤差は等価個体よりも2次的に小さい。
論文 参考訳（メタデータ） (2024-09-05T17:56:51Z) - Understanding Transformer Reasoning Capabilities via Graph Algorithms [25.08208816144745]
我々は、トランスフォーマースケーリングレギュレーションがアルゴリズムの様々なクラスを完璧に解けるかを検討する。
その結果、トランスフォーマーは多くのグラフ推論タスクで優れており、特殊なグラフニューラルネットワークよりも優れています。
論文 参考訳（メタデータ） (2024-05-28T18:31:14Z) - Transformers Implement Functional Gradient Descent to Learn Non-Linear Functions In Context [44.949726166566236]
非線形変換器は自然に関数空間の勾配降下を実装することを学習する。
また、非線形活性化の最適選択は、学習すべき関数のクラスに自然に依存していることも示している。
論文 参考訳（メタデータ） (2023-12-11T17:05:25Z) - The Clock and the Pizza: Two Stories in Mechanistic Explanation of
Neural Networks [59.26515696183751]
ニューラルネットワークにおけるアルゴリズム発見は、時としてより複雑であることを示す。
単純な学習問題でさえ、驚くほど多様なソリューションを許容できることが示されています。
論文 参考訳（メタデータ） (2023-06-30T17:59:13Z) - Statistically Meaningful Approximation: a Case Study on Approximating
Turing Machines with Transformers [50.85524803885483]
本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。
回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
論文 参考訳（メタデータ） (2021-07-28T04:28:55Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Investigating the Scalability and Biological Plausibility of the
Activation Relaxation Algorithm [62.997667081978825]
アクティベーション・リラクシエーション(AR)アルゴリズムは、誤りアルゴリズムのバックプロパゲーションを近似するためのシンプルでロバストなアプローチを提供する。
このアルゴリズムは、学習可能な後方重みセットを導入することにより、さらに単純化され、生物学的に検証可能であることを示す。
また、元のARアルゴリズム(凍結フィードフォワードパス)の別の生物学的に信じられない仮定が、パフォーマンスを損なうことなく緩和できるかどうかについても検討する。
論文 参考訳（メタデータ） (2020-10-13T08:02:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。