論文の概要: 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（参考訳）: 無限変圧器のアルゴリズム捕捉, 計算複雑度, 誘導バイアス
- 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)クラス内の低複素性アルゴリズムに対して帰納的バイアスを有することを示す。
このバイアスは、検索、コピー、ソートといった単純なタスクで成功しながら、より複雑なアルゴリズムのキャプチャを効果的に妨げます。
関連論文リスト
- Discovering Algorithms with Computational Language Processing [0.7062238472483737]
本稿では,トークンとして表現された操作列を概念化し,アルゴリズム発見を自動化するフレームワークを提案する。
これらの計算トークンは文法を用いてチェーン化され、より洗練された手続きの形成を可能にする。
我々のアンサンブルであるモンテカルロ木探索(MCTS)は、強化学習(RL)によって導かれ、トークン連鎖を探索し、新しいトークンの作成を促進する。
論文 参考訳（メタデータ） (2025-07-03T21:45:17Z) - Transformers Meet In-Context Learning: A Universal Approximation Theory [25.513848079509653]
我々は、変換器が文脈内学習を実現する方法を理解するために、普遍近似理論を開発する。
関数の一般的なクラスに対して、いくつかのノイズの多いインコンテキストの例に基づいて予測できる変換器を構築する方法を示す。
論文 参考訳（メタデータ） (2025-06-05T16:12:51Z) - 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) - Transformers as Statisticians: Provable In-Context Learning with
In-Context Algorithm Selection [88.23337313766353]
この研究はまず、変換器がICLを実行するための包括的な統計理論を提供する。
コンテクストにおいて、トランスフォーマーは、幅広い種類の標準機械学習アルゴリズムを実装可能であることを示す。
エンフィングル変換器は、異なるベースICLアルゴリズムを適応的に選択することができる。
論文 参考訳（メタデータ） (2023-06-07T17:59:31Z) - Low-complexity Approximate Convolutional Neural Networks [1.7368964547487395]
本稿では,学習された畳み込みニューラルネットワーク(ConvNet)の計算複雑性を最小化する手法を提案する。
この考え方は、与えられたConvNetのすべての要素を計算複雑性を極端に削減できる効率的な近似で近似することである。
このような低複雑さ構造は、低消費電力で効率的なハードウェア設計の道を開く。
論文 参考訳（メタデータ） (2022-07-29T21:59:29Z) - 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) - Activation Relaxation: A Local Dynamical Approximation to
Backpropagation in the Brain [62.997667081978825]
活性化緩和(AR)は、バックプロパゲーション勾配を力学系の平衡点として構成することで動機付けられる。
我々のアルゴリズムは、正しいバックプロパゲーション勾配に迅速かつ堅牢に収束し、単一のタイプの計算単位しか必要とせず、任意の計算グラフで操作できる。
論文 参考訳（メタデータ） (2020-09-11T11:56:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。