論文の概要: Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers

• arxiv url: http://arxiv.org/abs/2107.13163v1
• Date: Wed, 28 Jul 2021 04:28:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2021-07-29 14:07:03.690436
• Title: Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers
• Title（参考訳）: 統計的に有意義な近似:変圧器付きチューリングマシンのケーススタディ
• Abstract要約: ニューラルネットワークアーキテクチャを理論的に研究する一般的なレンズは、近似可能な関数を分析することである。 本研究では,統計的に有意な近似の形式的定義を提案する。
• 参考スコア（独自算出の注目度）: 64.83204488699468
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A common lens to theoretically study neural net architectures is to analyze the functions they can approximate. However, the constructions from approximation theory often have unrealistic aspects, for example, reliance on infinite precision to memorize target function values, which make these results potentially less meaningful. To address these issues, this work proposes a formal definition of statistically meaningful approximation which requires the approximating network to exhibit good statistical learnability. We present case studies on statistically meaningful approximation for two classes of functions: boolean circuits and Turing machines. We show that overparameterized feedforward neural nets can statistically meaningfully approximate boolean circuits with sample complexity depending only polynomially on the circuit size, not the size of the approximating network. In addition, we show that transformers can statistically meaningfully approximate Turing machines with computation time bounded by $T$, requiring sample complexity polynomial in the alphabet size, state space size, and $\log (T)$. Our analysis introduces new tools for generalization bounds that provide much tighter sample complexity guarantees than the typical VC-dimension or norm-based bounds, which may be of independent interest.
• Abstract（参考訳）: ニューラルネットワークアーキテクチャを理論的に研究する一般的なレンズは、近似可能な関数を分析することである。 しかし、近似理論による構成はしばしば非現実的な側面を持ち、例えば、ターゲット関数の値を記憶するために無限の精度に依存するため、これらの結果は潜在的に意味を示さない。 これらの問題に対処するため,本研究では,統計的に有意な近似の形式的定義を提案する。 本稿では,ブール回路とチューリング機械の2種類の関数に対する統計的に有意な近似のケーススタディを提案する。 過パラメータ化されたフィードフォワードニューラルネットワークは、近似ネットワークのサイズではなく、回路サイズに多項式のみ依存するサンプル複雑性を持つブール回路を統計的に有意義に近似することができる。 さらに、変換器は、T$で有界な計算時間を持つチューリングマシンを統計的に近似することができ、アルファベットサイズ、状態空間サイズ、および$\log (T)$でサンプル複雑性多項式を必要とすることを示す。 我々の分析では、典型的なVC次元や標準ベース境界よりもはるかに厳密なサンプル複雑性保証を提供する一般化境界のための新しいツールを導入している。

関連論文リスト

• All you need is SAMPAT [4.978871870250063]
  解釈可能性(interpretability)は、実験データを分析しながら洞察を引き出す上で重要である。 連続的かつ至るところで微分可能な関数を確実に学習できる3層ニューラルネットワーク、SAMPATを提案する。 合成およびベンチマークデータセットの実験は、SAMPATがより単純な表現で競合性能を得ることを示している。
  論文  参考訳（メタデータ） (2026-07-10T09:31:01Z)
• Algorithmic Foundations of Deep Learning: Complexity-Theoretic Rates and a Characterization of Universal Approximation [15.78691543310587]
  ニューラルネットワークはフレキシブルな基底関数として、また計算のモデルとして見なされるべきであることを示す。 自然並列化条件を満たす任意の定義可能なNNモデルは、非アフィン非線形性を含む場合に限り、普遍近似であることを示す。 提案理論の範囲は,連続関数に対する普遍近似保証,ベソフ類に対する最小最適近似保証,正則関数に対する対数誤差複雑性,およびニュートン・ラフソン根探索や電力計算のような数値アルゴリズムをエミュレートできることを示す。
  論文  参考訳（メタデータ） (2026-06-25T07:34:20Z)
• Learning High-Dimensional Parity Functions with Product Networks using Gradient Descent [1.6802038598427533]
  高次元パリティ関数は、機械学習、暗号、エラー訂正に不可欠である。 標準的なニューラルネットワークアーキテクチャは、通常指数的なサンプル複雑性を必要とする。 コンパクトな製品ベースのニューラルアーキテクチャとデータスパシティを組み合わせることで、効率の良いパリティ学習が可能になることを示す。 この研究は、自動プロトコル発見に適用されるニューラル演算、構造化推論、バイナリニューラルネットワーク、マシンラーニングの新たな可能性を開く。
  論文  参考訳（メタデータ） (2026-05-27T15:26:16Z)
• Quantifying The Limits of AI Reasoning: Systematic Neural Network Representations of Algorithms [10.292476979020522]
  基本的に任意の回路をフィードフォワードニューラルネットワーク(NN)に変換するシステムメタアルゴリズムを提案する。 あらゆるデジタルコンピュータ上で、我々の構成は回路を正確にエミュレートしている ― 近似がなく、丸めず、モジュラーなオーバーフローも含まない ― ニューラルネットワークの範囲を超えて推論タスクが存在しないことを実証している。
  論文  参考訳（メタデータ） (2025-08-25T21:55:37Z)
• Transformers Meet In-Context Learning: A Universal Approximation Theory [25.513848079509653]
  我々は、変換器が文脈内学習を実現する方法を理解するために、普遍近似理論を開発する。 関数の一般的なクラスに対して、いくつかのノイズの多いインコンテキストの例に基づいて予測できる変換器を構築する方法を示す。
  論文  参考訳（メタデータ） (2025-06-05T16:12:51Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Universal Neural Functionals [67.80283995795985]
  多くの現代の機械学習タスクでは、ウェイトスペース機能を処理することが難しい問題である。 最近の研究は、単純なフィードフォワードネットワークの置換対称性に同値な有望な重み空間モデルを開発した。 本研究は,任意の重み空間に対する置換同変モデルを自動的に構築するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-07T20:12:27Z)
• Auto-Regressive Next-Token Predictors are Universal Learners [17.416520406390415]
  線形次トーケン予測器のような単純なモデルでさえ、チューリングマシンによって効率的に計算される任意の関数を近似することができることを示す。 また、線形ネットワークや浅層多層パーセプトロン(MLP)のような単純な次世代予測器が、テキスト生成や算術タスクにおいて非自明な性能を示すことを示す。
  論文  参考訳（メタデータ） (2023-09-13T14:15:03Z)
• Neural approximation of Wasserstein distance via a universal architecture for symmetric and factorwise group invariant functions [6.994580267603235]
  まず,SFGI関数を近似する汎用ニューラルネットワークアーキテクチャを提案する。 本論文の主な貢献は、この一般的なニューラルネットワークとスケッチのアイデアを組み合わせて、特定かつ効率的なニューラルネットワークを開発することである。 我々の研究は、対称関数の普遍近似を伴う幾何学的問題に対するスケッチのアイデアの興味深い統合を提供する。
  論文  参考訳（メタデータ） (2023-08-01T04:11:19Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  低深度変換器は任意の有限状態オートマトンを計算できる。 我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。 さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
  論文  参考訳（メタデータ） (2022-10-19T17:45:48Z)
• A Simple and General Debiased Machine Learning Theorem with Finite Sample Guarantees [4.55274575362193]
  我々は、あらゆる機械学習アルゴリズムのグローバルまたはローカル機能を含む、漸近的不偏性機械学習定理を提供する。 この結果は、アナリストが現代の学習理論の速度を従来の統計的推論に翻訳するために使用できる、単純な条件のセットで決定される。
  論文  参考訳（メタデータ） (2021-05-31T17:57:02Z)
• PAC-learning gains of Turing machines over circuits and neural networks [1.4502611532302039]
  私達は最低記述の長さの原則を持って来ることができるサンプル効率の潜在的な利益を研究します。 我々はチューリングマシンを用いて普遍的なモデルと回路を表現する。 回路の複雑さと密接性における古典的オープン問題との密接な関係を浮き彫りにする。
  論文  参考訳（メタデータ） (2021-03-23T17:03:10Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。 この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。 我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
  論文  参考訳（メタデータ） (2020-06-21T15:32:21Z)

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

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