論文の概要: Neural Networks as Universal Finite-State Machines: A Constructive ReLU Simulation Framework for NFAs
- arxiv url: http://arxiv.org/abs/2505.24110v1
- Date: Fri, 30 May 2025 01:18:35 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-02 19:47:52.721893
- Title: Neural Networks as Universal Finite-State Machines: A Constructive ReLU Simulation Framework for NFAs
- Title（参考訳）: 汎用有限状態マシンとしてのニューラルネットワーク:NFAのための構成型ReLUシミュレーションフレームワーク
- Authors: Sahil Rajesh Dhayalkar,
- Abstract要約: ReLUアクティベーションは非決定論的分岐、サブセット構成、および$epsilon$-クロージャを数学的に正確にシミュレートする。
この研究は、標準ディープラーニングアーキテクチャにおけるNFAの証明可能な完全なシンボルシミュレーションを初めて提供する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We present a formal and constructive framework establishing the equivalence between nondeterministic finite automata (NFAs) and standard feedforward ReLU neural networks. By encoding automaton states as binary vectors and transitions as sparse linear layers, we show that ReLU activations simulate nondeterministic branching, subset construction, and $\epsilon$-closures in a mathematically precise manner. Our core theoretical results prove that a three-layer ReLU network of width $\mathcal{O}(n)$ can exactly recognize any regular language accepted by an $n$-state NFA-without recurrence, memory, or approximation. Furthermore, we show that gradient descent over structure-preserving networks preserves symbolic semantics and acceptance behavior. Extensive experiments across multiple validation tasks-including parallel path tracking, symbolic subset construction, $\epsilon$-closure convergence, acceptance classification, structural training invariants, and functional equivalence-achieve perfect or near-perfect empirical alignment with ground-truth automata. This work provides the first provably complete symbolic simulation of NFAs within standard deep learning architectures, uniting automata theory with neural computation through ReLU dynamics.
- Abstract（参考訳）: 非決定論的有限オートマトン(NFA)と標準フィードフォワードReLUニューラルネットワークの等価性を確立するための形式的,建設的な枠組みを提案する。
オートマトン状態を二項ベクトルとして符号化し、疎線型層として遷移することにより、ReLU活性化が非決定的分岐、部分集合構成、および$\epsilon$-クロージャを数学的に正確にシミュレートすることを示す。
我々の中核的な理論的結果は、$\mathcal{O}(n)$の3層ReLUネットワークが、再帰、記憶、近似なしに$n$状態のNFAで受け入れられる正規言語を正確に認識できることを証明している。
さらに, 構造保存ネットワークに対する勾配勾配は, 象徴的意味論と受容行動を保存することを示す。
並列経路追跡、シンボリックサブセット構成、$\epsilon$-closureコンバージェンス、受け入れ分類、構造的訓練不変量、機能的同値化の完全あるいはほぼ完全な実験的アライメントを含む複数の検証タスクにわたる広範な実験。
この研究は、標準ディープラーニングアーキテクチャにおけるNFAの証明可能な完全なシンボリックシミュレーションを初めて提供し、ReLUダイナミクスを通じてオートマトン理論とニューラル計算を結合した。
関連論文リスト
- Neural Networks as Universal Finite-State Machines: A Constructive Deterministic Finite Automaton Theory [0.0]
我々は、ユニバーサル有限状態マシン(N-FSM)としてフィードフォワードニューラルネットワークを確立する。
我々の結果は、有限深度ReLUとしきい値ネットワークが決定論的有限オートマトン(DFAs)を正確にシミュレートできることを証明している。
固定深度フィードフォワードネットワークは、メモリを必要とする非正規言語を認識できない。
論文 参考訳（メタデータ） (2025-05-16T21:01:34Z) - Deriving Equivalent Symbol-Based Decision Models from Feedforward Neural Networks [0.0]
急速な採用にもかかわらず、AIシステムの不透明さは、信頼と受け入れに重大な課題をもたらす。
この研究は、フィードフォワードニューラルネットワーク(FNN)から決定木などのシンボルモデルの導出に焦点を当てている。
論文 参考訳（メタデータ） (2025-04-16T19:22:53Z) - Enhancing lattice kinetic schemes for fluid dynamics with Lattice-Equivariant Neural Networks [79.16635054977068]
我々はLattice-Equivariant Neural Networks (LENNs)と呼ばれる新しい同変ニューラルネットワークのクラスを提案する。
我々の手法は、ニューラルネットワークに基づく代理モデルLattice Boltzmann衝突作用素の学習を目的とした、最近導入されたフレームワーク内で開発されている。
本研究は,実世界のシミュレーションにおける機械学習強化Lattice Boltzmann CFDの実用化に向けて展開する。
論文 参考訳（メタデータ） (2024-05-22T17:23:15Z) - Lipschitz constant estimation for general neural network architectures using control tools [0.05120567378386613]
本稿では,半定値プログラミングを用いた一般ニューラルネットワークアーキテクチャのリプシッツ定数の推定について述べる。
我々はニューラルネットワークを時間変動力学系と解釈し、そこでは、$k$th層は、時間で$k$の力学に対応する。
論文 参考訳（メタデータ） (2024-05-02T09:38:16Z) - From NeurODEs to AutoencODEs: a mean-field control framework for
width-varying Neural Networks [68.8204255655161]
本稿では,動的に駆動する制御フィールドをベースとした,AutoencODEと呼ばれる新しいタイプの連続時間制御システムを提案する。
損失関数が局所凸な領域では,多くのアーキテクチャが復元可能であることを示す。
論文 参考訳（メタデータ） (2023-07-05T13:26:17Z) - Set-based Neural Network Encoding Without Weight Tying [91.37161634310819]
本稿では,ネットワーク特性予測のためのニューラルネットワーク重み符号化手法を提案する。
我々のアプローチは、混合アーキテクチャのモデル動物園でニューラルネットワークを符号化することができる。
ニューラルネットワークのプロパティ予測には,クロスデータセットとクロスアーキテクチャという,2つの新しいタスクを導入する。
論文 参考訳（メタデータ） (2023-05-26T04:34:28Z) - Asymmetric Certified Robustness via Feature-Convex Neural Networks [11.605936648692543]
ICNNを敵ネットワークに一般化できることを示す。
実験により、ネットワークはどの競争ベースラインよりもはるかに効率的であることが示されている。
論文 参考訳（メタデータ） (2023-02-03T19:17:28Z) - Symbolic Distillation for Learned TCP Congestion Control [70.27367981153299]
TCP渋滞制御は、深層強化学習(RL)アプローチで大きな成功を収めた。
ブラックボックスポリシーは解釈可能性と信頼性に欠けており、しばしば従来のTCPデータパスの外で運用する必要がある。
本稿では,まず深部RLエージェントを訓練し,次にNNポリシーをホワイトボックスの軽量なルールに蒸留する,両世界の長所を達成するための新しい2段階のソリューションを提案する。
論文 参考訳（メタデータ） (2022-10-24T00:58:16Z) - Signal Processing for Implicit Neural Representations [80.38097216996164]
Inlicit Neural Representation (INR)は、マルチ層パーセプトロンを介して連続したマルチメディアデータを符号化する。
既存の作業は、その離散化されたインスタンスの処理を通じて、そのような連続的な表現を操作する。
本稿では,INSP-Netと呼ばれる暗黙的ニューラル信号処理ネットワークを提案する。
論文 参考訳（メタデータ） (2022-10-17T06:29:07Z) - Robust Training and Verification of Implicit Neural Networks: A
Non-Euclidean Contractive Approach [64.23331120621118]
本稿では,暗黙的ニューラルネットワークのトレーニングとロバスト性検証のための理論的および計算的枠組みを提案する。
組込みネットワークを導入し、組込みネットワークを用いて、元のネットワークの到達可能な集合の超近似として$ell_infty$-normボックスを提供することを示す。
MNISTデータセット上で暗黙的なニューラルネットワークをトレーニングするためにアルゴリズムを適用し、我々のモデルの堅牢性と、文献における既存のアプローチを通じてトレーニングされたモデルを比較する。
論文 参考訳（メタデータ） (2022-08-08T03:13:24Z) - On the Effective Number of Linear Regions in Shallow Univariate ReLU
Networks: Convergence Guarantees and Implicit Bias [50.84569563188485]
我々は、ラベルが$r$のニューロンを持つターゲットネットワークの符号によって決定されるとき、勾配流が方向収束することを示す。
我々の結果は、標本サイズによらず、幅が$tildemathcalO(r)$である、緩やかなオーバーパラメータ化をすでに維持しているかもしれない。
論文 参考訳（メタデータ） (2022-05-18T16:57:10Z) - Modeling Structure with Undirected Neural Networks [20.506232306308977]
任意の順序で実行できる計算を指定するためのフレキシブルなフレームワークである、非指向型ニューラルネットワークを提案する。
さまざまなタスクにおいて、非構造的かつ構造化された非指向型ニューラルアーキテクチャの有効性を実証する。
論文 参考訳（メタデータ） (2022-02-08T10:06:51Z) - Integrating Regular Expressions with Neural Networks via DFA [40.09868407372605]
より優れたパフォーマンスを実現するハイブリッドモデルを構築するためには、ルール知識をニューラルネットワークに統合することが非常に重要です。
具体的には、人間設計規則は正規表現(res)として定式化される。
本稿では、MDFAを中間モデルとして用いて、一致したREパターンを各入力文のルールベースの特徴として捉えることを提案する。
論文 参考訳（メタデータ） (2021-09-07T05:48:51Z) - FF-NSL: Feed-Forward Neural-Symbolic Learner [70.978007919101]
本稿では,Feed-Forward Neural-Symbolic Learner (FF-NSL) と呼ばれるニューラルシンボリック学習フレームワークを紹介する。
FF-NSLは、ラベル付き非構造化データから解釈可能な仮説を学習するために、Answer Setセマンティクスに基づく最先端のICPシステムとニューラルネットワークを統合する。
論文 参考訳（メタデータ） (2021-06-24T15:38:34Z) - Connecting Weighted Automata, Tensor Networks and Recurrent Neural
Networks through Spectral Learning [58.14930566993063]
我々は、形式言語と言語学からの重み付き有限オートマトン(WFA)、機械学習で使用されるリカレントニューラルネットワーク、テンソルネットワークの3つのモデル間の接続を提示する。
本稿では,連続ベクトル入力の列上に定義された線形2-RNNに対する最初の証明可能な学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-19T15:28:00Z) - Provably Efficient Neural Estimation of Structural Equation Model: An
Adversarial Approach [144.21892195917758]
一般化構造方程式モデル(SEM)のクラスにおける推定について検討する。
線形作用素方程式をmin-maxゲームとして定式化し、ニューラルネットワーク(NN)でパラメータ化し、勾配勾配を用いてニューラルネットワークのパラメータを学習する。
提案手法は,サンプル分割を必要とせず,確固とした収束性を持つNNをベースとしたSEMの抽出可能な推定手順を初めて提供する。
論文 参考訳（メタデータ） (2020-07-02T17:55:47Z) - Investigating the Compositional Structure Of Deep Neural Networks [1.8899300124593645]
本稿では,一方向線形活性化関数の構成構造に基づく新しい理論的枠組みを提案する。
予測ラベルと予測に使用する特定の(線形)変換の両方に関して、入力データのインスタンスを特徴付けることができる。
MNISTデータセットの予備テストでは、ニューラルネットワークの内部表現における類似性に関して、入力インスタンスをグループ化することが可能である。
論文 参考訳（メタデータ） (2020-02-17T14:16:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。