論文の概要: Neural Networks as Universal Finite-State Machines: A Constructive ReLU Simulation Framework for NFAs

• arxiv url: http://arxiv.org/abs/2505.24110v2
• Date: Wed, 30 Jul 2025 06:52:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-31 14:05:51.171166
• Title: Neural Networks as Universal Finite-State Machines: A Constructive ReLU Simulation Framework for NFAs
• Title（参考訳）: 汎用有限状態マシンとしてのニューラルネットワーク:NFAのための構成型ReLUシミュレーションフレームワーク
• Authors: Sahil Rajesh Dhayalkar,
• Abstract要約: 本稿では,標準フィードフォワードReLUニューラルネットワークを用いた非決定論的有限オートマトン(NFA)の形式的,建設的なシミュレーションフレームワークを提案する。 我々の定式化は、双対ベクトルとしてのオートマトン状態、スパース線形変換としての遷移、非決定論的分岐を象徴的にエンコードする。 入力長に依存しない共有パラメータを持つReLUネットワークにより、すべての正規言語を正確に認識できることを実証する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a formal and constructive simulation framework for nondeterministic finite automata (NFAs) using standard feedforward ReLU neural networks. Unlike prior approaches that rely on recurrent architectures or post hoc extraction methods, our formulation symbolically encodes automaton states as binary vectors, transitions as sparse linear transformations, and nondeterministic branching - including {\epsilon}-closures - as compositions of shared ReLU layers. We prove that every regular language can be recognized exactly by a depth-unrolled ReLU network with shared parameters, independent of input length. Our construction yields not only formal equivalence between NFAs and ReLU networks, but also practical trainability: we demonstrate that the networks can learn NFA acceptance behavior through gradient descent using standard supervised data. Extensive experiments validate all theoretical results, achieving perfect or near-perfect agreement on acceptance, state propagation, and closure dynamics. This work establishes a new bridge between symbolic automata theory and modern neural architectures, showing that feedforward networks can perform precise, interpretable, and trainable symbolic computation.
• Abstract（参考訳）: 本稿では,標準フィードフォワードReLUニューラルネットワークを用いた非決定論的有限オートマトン(NFA)の形式的,建設的なシミュレーションフレームワークを提案する。 リカレントアーキテクチャやポストホック抽出法に依存する従来のアプローチとは異なり、我々の定式化では、オートマトン状態を二進ベクトル、スパース線形変換としての遷移、および非決定論的分岐を共有ReLU層の合成として表す。 入力長に依存しない共有パラメータを持つReLUネットワークにより、すべての正規言語を正確に認識できることを実証する。 我々は,NFAとReLUのネットワーク間の形式的等価性だけでなく,ネットワークが標準教師付きデータを用いて勾配勾配からNFA受容挙動を学習できることを実証した。 包括的な実験は全ての理論結果を検証し、受容、状態伝播、閉包力学に関する完全なあるいはほぼ完全な合意を達成した。 この研究は、シンボリックオートマトン理論と現代のニューラルアーキテクチャの新たなブリッジを確立し、フィードフォワードネットワークが正確で解釈可能で訓練可能なシンボリック計算を実行できることを示した。

関連論文リスト

• Neural Networks as Universal Finite-State Machines: A Constructive Deterministic Finite Automaton Theory [0.0]
  我々は、ユニバーサル有限状態マシン(N-FSM)としてフィードフォワードニューラルネットワークを確立する。 我々の結果は、有限深度ReLUとしきい値ネットワークが決定論的有限オートマトン(DFAs)を正確にシミュレートできることを証明している。 固定深度フィードフォワードネットワークは、メモリを必要とする非正規言語を認識できない。
  論文  参考訳（メタデータ） (2025-05-16T21:01:34Z)
• 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)
• Asymmetric Certified Robustness via Feature-Convex Neural Networks [11.605936648692543]
  ICNNを敵ネットワークに一般化できることを示す。 実験により、ネットワークはどの競争ベースラインよりもはるかに効率的であることが示されている。
  論文  参考訳（メタデータ） (2023-02-03T19:17:28Z)
• 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)
• 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)

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

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