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

• arxiv url: http://arxiv.org/abs/2505.24110v3
• Date: Mon, 04 Aug 2025 04:35:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-05 14:07:56.97215
• Title: Neural Networks as Universal Finite-State Machines: A Constructive Feedforward Simulation Framework for NFAs
• Title（参考訳）: Universal Finite-State Machinesとしてのニューラルネットワーク:NFAのための構成的フィードフォワードシミュレーションフレームワーク
• Authors: Sahil Rajesh Dhayalkar,
• Abstract要約: この研究は、象徴的オートマトン理論と現代のニューラルアーキテクチャの新たなブリッジを確立する。 フィードフォワードネットワークは正確で、解釈可能で、訓練可能なシンボル計算を行うことができることを示す。
• 参考スコア（独自算出の注目度）: 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 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 matrix transformations, and nondeterministic branching-including $\varepsilon$-closures-as compositions of shared thresholded updates. We prove that every regular language can be recognized exactly by a depth-unrolled feedforward network with shared parameters, independent of input length. Our construction yields not only formal equivalence between NFAs and neural networks, but also practical trainability: we demonstrate that these 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（参考訳）: 標準フィードフォワードニューラルネットワークを用いた非決定論的有限オートマトン(NFA)の形式的・構成的シミュレーションフレームワークを提案する。 再帰的アーキテクチャやポストホック抽出法に依存する従来の手法とは異なり、我々の定式化では、オートマトン状態を二進ベクトル、スパース行列変換としての遷移、および共有しきい値更新の合成としての$\varepsilon$-closuresを含む非決定的分岐を象徴的に符号化している。 入力長に依存しない共有パラメータを持つディープアンロールフィードフォワードネットワークにより、すべての正規言語を正確に認識できることを実証する。 我々の構築は、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)
• 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)

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

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