論文の概要: Quantifying The Limits of AI Reasoning: Systematic Neural Network Representations of Algorithms
- arxiv url: http://arxiv.org/abs/2508.18526v2
- Date: Tue, 16 Sep 2025 14:10:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-17 17:50:52.619795
- Title: Quantifying The Limits of AI Reasoning: Systematic Neural Network Representations of Algorithms
- Title（参考訳）: AI推論の限界の定量化:アルゴリズムの体系的ニューラルネットワーク表現
- Authors: Anastasis Kratsios, Dennis Zvigelsky, Bradd Hart,
- Abstract要約: 基本的に任意の回路をフィードフォワードニューラルネットワーク(NN)に変換するシステムメタアルゴリズムを提案する。
あらゆるデジタルコンピュータ上で、我々の構成は回路を正確にエミュレートしている ― 近似がなく、丸めず、モジュラーなオーバーフローも含まない ― ニューラルネットワークの範囲を超えて推論タスクが存在しないことを実証している。
- 参考スコア（独自算出の注目度）: 10.292476979020522
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A main open question in contemporary AI research is quantifying the forms of reasoning neural networks can perform when perfectly trained. This paper answers this by interpreting reasoning tasks as circuit emulation, where the gates define the type of reasoning; e.g. Boolean gates for predicate logic, tropical circuits for dynamic programming, arithmetic and analytic gates for symbolic mathematical representation, and hybrids thereof for deeper reasoning; e.g. higher-order logic. We present a systematic meta-algorithm that converts essentially any circuit into a feedforward neural network (NN) with ReLU activations by iteratively replacing each gate with a canonical ReLU MLP emulator. We show that, on any digital computer, our construction emulates the circuit exactly--no approximation, no rounding, modular overflow included--demonstrating that no reasoning task lies beyond the reach of neural networks. The number of neurons in the resulting network (parametric complexity) scales with the circuit's complexity, and the network's computational graph (structure) mirrors that of the emulated circuit. This formalizes the folklore that NNs networks trade algorithmic run-time (circuit runtime) for space complexity (number of neurons). We derive a range of applications of our main result, from emulating shortest-path algorithms on graphs with cubic--size NNs, to simulating stopped Turing machines with roughly quadratically--large NNs, and even the emulation of randomized Boolean circuits. Lastly, we demonstrate that our result is strictly more powerful than a classical universal approximation theorem: any universal function approximator can be encoded as a circuit and directly emulated by a NN.
- Abstract（参考訳）: 現代のAI研究における大きな疑問は、ニューラルネットワークが完全に訓練されたときに実行できる推論の形式を定量化することである。
本稿では,論理学の述語論理に対するブールゲート,動的プログラミングのための熱帯回路,記号数学的表現のための算術と解析ゲート,より深い推論のためのハイブリッド,高階論理など,論理学のタイプを定義した回路エミュレーションとして推論タスクを解釈することで,この問題に対処する。
本稿では,基本的に任意の回路をReLU活性化を伴うフィードフォワードニューラルネットワーク(NN)に変換し,各ゲートを標準のReLU MLPエミュレータで反復的に置き換えるシステムメタアルゴリズムを提案する。
あらゆるデジタルコンピュータ上で、我々の構成は回路を正確にエミュレートしている ― 近似がなく、丸めず、モジュラーなオーバーフローも含まない ― ニューラルネットワークの範囲を超えて推論タスクが存在しないことを実証している。
結果として生じるネットワーク内のニューロンの数(パラメトリックの複雑さ)は回路の複雑さとスケールし、ネットワークの計算グラフ(構造)はエミュレートされた回路を反映する。
これはNNネットワークが空間複雑性(ニューロン数)に対してアルゴリズム的な実行時間(回路ランタイム)を交換するという民間伝承を定式化したものである。
提案手法は,3次元NNを用いたグラフ上でのショートパスアルゴリズムのエミュレーションから,約2次NNによる停止チューリングマシンのシミュレート,ランダム化ブール回路のエミュレーションに至るまで,主要な結果の幅広い応用を導出する。
最後に、我々の結果は古典的普遍近似定理よりも厳密に強力であることを示し、任意の普遍関数近似子は回路として符号化され、NNによって直接エミュレートされる。
関連論文リスト
- Compressed Computation: Dense Circuits in a Toy Model of the Universal-AND Problem [0.0]
ニューラルネットワークは重ね合わせが可能で、次元よりも多くの特徴を表現できる。
最近の研究は、記憶ではなく計算の類似概念を考察し、理論的構成を提案している。
本研究は,すべての$mchoose 2$対のスパース入力の ANDを演算するUniversal-AND問題に対する玩具モデルについて検討する。
論文 参考訳（メタデータ） (2025-07-13T22:18:15Z) - Challenges and opportunities in the supervised learning of quantum
circuit outputs [0.0]
ディープニューラルネットワークは、関連するランダム量子回路の出力特性を予測できることが証明されている。
変動量子アルゴリズムでよく使用される回路の出力期待値を予測するために,ニューラルネットワークがどの程度の精度で学習できるかを検討する。
論文 参考訳（メタデータ） (2024-02-07T16:10:13Z) - Transformers Learn Shortcuts to Automata [52.015990420075944]
低深度変換器は任意の有限状態オートマトンを計算できる。
我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。
さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
論文 参考訳（メタデータ） (2022-10-19T17:45:48Z) - Pretraining Graph Neural Networks for few-shot Analog Circuit Modeling
and Design [68.1682448368636]
本稿では、新しい未知のトポロジや未知の予測タスクに適応可能な回路表現を学習するための教師付き事前学習手法を提案する。
異なる回路の変動位相構造に対処するため、各回路をグラフとして記述し、グラフニューラルネットワーク(GNN)を用いてノード埋め込みを学習する。
出力ノード電圧の予測における事前学習GNNは、新しい未知のトポロジや新しい回路レベル特性の予測に適応可能な学習表現を促進することができることを示す。
論文 参考訳（メタデータ） (2022-03-29T21:18:47Z) - Statistically Meaningful Approximation: a Case Study on Approximating
Turing Machines with Transformers [50.85524803885483]
本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。
回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
論文 参考訳（メタデータ） (2021-07-28T04:28:55Z) - A quantum algorithm for training wide and deep classical neural networks [72.2614468437919]
勾配勾配勾配による古典的トレーサビリティに寄与する条件は、量子線形系を効率的に解くために必要な条件と一致することを示す。
MNIST画像データセットがそのような条件を満たすことを数値的に示す。
我々は、プールを用いた畳み込みニューラルネットワークのトレーニングに$O(log n)$の実証的証拠を提供する。
論文 参考訳（メタデータ） (2021-07-19T23:41:03Z) - PAC-learning gains of Turing machines over circuits and neural networks [1.4502611532302039]
私達は最低記述の長さの原則を持って来ることができるサンプル効率の潜在的な利益を研究します。
我々はチューリングマシンを用いて普遍的なモデルと回路を表現する。
回路の複雑さと密接性における古典的オープン問題との密接な関係を浮き彫りにする。
論文 参考訳（メタデータ） (2021-03-23T17:03:10Z) - Artificial Neural Networks generated by Low Discrepancy Sequences [59.51653996175648]
我々は、高密度ネットワークグラフ上のランダムウォーキングとして、人工ニューラルネットワークを生成する。
このようなネットワークはスクラッチからスパースを訓練することができ、高密度ネットワークをトレーニングし、その後圧縮する高価な手順を避けることができる。
我々は,低差分シーケンスで生成された人工ニューラルネットワークが,より低い計算複雑性で,密度の高いニューラルネットワークの到達範囲内で精度を達成できることを実証した。
論文 参考訳（メタデータ） (2021-03-05T08:45:43Z) - Lowering the T-depth of Quantum Circuits By Reducing the Multiplicative
Depth Of Logic Networks [1.4902915966744057]
本稿では,論理ネットワークにおける乗算深度を低減するために,プログラミングに基づく論理合成アルゴリズムについて述べる。
我々のアルゴリズムは暗号や量子コンピューティングに応用されており、乗法深さの減少は対応する量子回路のより低いT$-depthへと直接変換される。
論文 参考訳（メタデータ） (2020-06-06T11:08:06Z) - LogicNets: Co-Designed Neural Networks and Circuits for
Extreme-Throughput Applications [6.9276012494882835]
本稿では,高効率FPGA実装に直接マップするニューラルネットワークトポロジを設計する新しい手法を提案する。
その結果,低ビット化と疎結合化の両立により,論理深度が小さく,LUTコストが低い高速回路が実現された。
論文 参考訳（メタデータ） (2020-04-06T22:15:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。