論文の概要: Neural Networks as Universal Finite-State Machines: A Constructive Deterministic Finite Automaton Theory

• arxiv url: http://arxiv.org/abs/2505.11694v2
• Date: Wed, 28 May 2025 21:39:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-30 18:14:07.414351
• Title: Neural Networks as Universal Finite-State Machines: A Constructive Deterministic Finite Automaton Theory
• Title（参考訳）: 普遍有限状態マシンとしてのニューラルネットワーク:構成的決定論的有限オートマトン理論
• Authors: Sahil Rajesh Dhayalkar,
• Abstract要約: 我々は、ユニバーサル有限状態マシン(N-FSM)としてフィードフォワードニューラルネットワークを確立する。 我々の結果は、有限深度ReLUとしきい値ネットワークが決定論的有限オートマトン(DFAs)を正確にシミュレートできることを証明している。 固定深度フィードフォワードネットワークは、メモリを必要とする非正規言語を認識できない。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a complete theoretical and empirical framework establishing feedforward neural networks as universal finite-state machines (N-FSMs). Our results prove that finite-depth ReLU and threshold networks can exactly simulate deterministic finite automata (DFAs) by unrolling state transitions into depth-wise neural layers, with formal characterizations of required depth, width, and state compression. We demonstrate that DFA transitions are linearly separable, binary threshold activations allow exponential compression, and Myhill-Nerode equivalence classes can be embedded into continuous latent spaces while preserving separability. We also formalize the expressivity boundary: fixed-depth feedforward networks cannot recognize non-regular languages requiring unbounded memory. Unlike prior heuristic or probing-based studies, we provide constructive proofs and design explicit DFA-unrolled neural architectures that empirically validate every claim. Our results bridge deep learning, automata theory, and neural-symbolic computation, offering a rigorous blueprint for how discrete symbolic processes can be realized in continuous neural systems.
• Abstract（参考訳）: 我々は、フィードフォワードニューラルネットワークを普遍有限状態機械(N-FSM)として確立する完全理論的かつ実証的な枠組みを提案する。 その結果, 有限深度ReLUとしきい値ネットワークは, 必要な深さ, 幅, 状態圧縮の形式的特徴を伴って, 状態遷移を奥行き神経層に展開することにより, 決定論的有限オートマトン (DFAs) を正確にシミュレートできることが証明された。 DFA遷移は線形分離可能であり、二項しきい値のアクティベーションは指数圧縮を可能にし、マイヒル・ネロード同値類は分離性を維持しつつ連続潜在空間に埋め込むことができる。 固定深度フィードフォワードネットワークは、非有界メモリを必要とする非正規言語を認識できない。 従来のヒューリスティックあるいは探索に基づく研究とは異なり、我々はすべてのクレームを実証的に検証する、建設的証明と明示的なDFAアンロールニューラルネットワークアーキテクチャを設計する。 我々の結果は、ディープラーニング、オートマトン理論、およびニューラルシンボリック計算を橋渡しし、連続神経系において離散的なシンボリックプロセスがどのように実現されるかの厳密な青写真を提供する。

関連論文リスト

• Global Convergence and Rich Feature Learning in $L$-Layer Infinite-Width Neural Networks under $μ$P Parametrization [66.03821840425539]
  本稿では, テンソル勾配プログラム(SGD)フレームワークを用いた$L$層ニューラルネットワークのトレーニング力学について検討する。 SGDにより、これらのネットワークが初期値から大きく逸脱する線形独立な特徴を学習できることを示す。 このリッチな特徴空間は、関連するデータ情報をキャプチャし、トレーニングプロセスの収束点が世界最小であることを保証する。
  論文  参考訳（メタデータ） (2025-03-12T17:33:13Z)
• Discovering Chunks in Neural Embeddings for Interpretability [53.80157905839065]
  本稿では, チャンキングの原理を応用して, 人工神経集団活動の解釈を提案する。 まず、この概念を正則性を持つ人工シーケンスを訓練したリカレントニューラルネットワーク(RNN)で実証する。 我々は、これらの状態に対する摂動が関連する概念を活性化または阻害すると共に、入力における概念に対応する同様の繰り返し埋め込み状態を特定する。
  論文  参考訳（メタデータ） (2025-02-03T20:30:46Z)
• Universal Scaling Laws of Absorbing Phase Transitions in Artificial Deep Neural Networks [0.8932296777085644]
  信号伝播ダイナミクスの位相境界付近で動作する従来の人工深層ニューラルネットワークは、カオスのエッジとしても知られ、位相遷移を吸収する普遍的なスケーリング法則を示す。 我々は、伝搬力学の完全な決定論的性質を利用して、ニューラルネットワークの信号崩壊と吸収状態の類似を解明する。
  論文  参考訳（メタデータ） (2023-07-05T13:39:02Z)
• Universal Approximation and the Topological Neural Network [0.0]
  トポロジカルニューラルネットワーク(TNN)は、通常の有限次元空間の代わりにチコノフ位相空間からデータを取得する。 また、ボレル測度をデータとする分布ニューラルネットワーク(DNN)も導入する。
  論文  参考訳（メタデータ） (2023-05-26T05:28:10Z)
• Rank Diminishing in Deep Neural Networks [71.03777954670323]
  ニューラルネットワークのランクは、層をまたがる情報を測定する。 これは機械学習の幅広い領域にまたがる重要な構造条件の例である。 しかし、ニューラルネットワークでは、低ランク構造を生み出す固有のメカニズムはあいまいで不明瞭である。
  論文  参考訳（メタデータ） (2022-06-13T12:03:32Z)
• NN-EUCLID: deep-learning hyperelasticity without stress data [0.0]
  本稿では,物理一貫性のあるディープニューラルネットワークを用いた超弾性法則の教師なし学習手法を提案する。 応力-ひずみを仮定する教師付き学習とは対照的に,本手法は実測可能な全弾性場変位と大域的力可用性データのみを用いる。
  論文  参考訳（メタデータ） (2022-05-04T13:54:54Z)
• Machines of finite depth: towards a formalization of neural networks [0.0]
  人工ニューラルネットワークとそのアーキテクチャを、一般的な数学的構築の特定の例、すなわち有限深さの機械として形式的に記述できる統一的なフレームワークを提供する。 我々は、この主張を理論的に、実用的に、いくつかの古典的アーキテクチャを一般化する統一的な実装、すなわち、リッチなショートカット構造を持つ高密度、畳み込み、反復的なニューラルネットワーク、およびそれぞれのバックプロパゲーションルールによって証明する。
  論文  参考訳（メタデータ） (2022-04-27T09:17:15Z)
• Quasi-orthogonality and intrinsic dimensions as measures of learning and generalisation [55.80128181112308]
  ニューラルネットワークの特徴空間の次元性と準直交性は、ネットワークの性能差別と共同して機能する可能性があることを示す。 本研究は, ネットワークの最終的な性能と, ランダムに初期化された特徴空間の特性との関係を示唆する。
  論文  参考訳（メタデータ） (2022-03-30T21:47:32Z)
• Connecting Weighted Automata, Tensor Networks and Recurrent Neural Networks through Spectral Learning [58.14930566993063]
  我々は、形式言語と言語学からの重み付き有限オートマトン(WFA)、機械学習で使用されるリカレントニューラルネットワーク、テンソルネットワークの3つのモデル間の接続を提示する。 本稿では,連続ベクトル入力の列上に定義された線形2-RNNに対する最初の証明可能な学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-19T15:28:00Z)
• A Chain Graph Interpretation of Real-World Neural Networks [58.78692706974121]
  本稿では,NNを連鎖グラフ(CG)、フィードフォワードを近似推論手法として識別する別の解釈を提案する。 CG解釈は、確率的グラフィカルモデルのリッチな理論的枠組みの中で、各NNコンポーネントの性質を規定する。 我々は,CG解釈が様々なNN技術に対する新しい理論的支援と洞察を提供することを示す具体例を実例で示す。
  論文  参考訳（メタデータ） (2020-06-30T14:46:08Z)
• Scalable Partial Explainability in Neural Networks via Flexible Activation Functions [13.71739091287644]
  ディープニューラルネットワーク(NN)によって与えられる高次元の特徴と決定は、そのメカニズムを公開するために新しいアルゴリズムと方法を必要とする。 現在の最先端のNN解釈手法は、NN構造や操作自体よりも、NN出力と入力との直接的な関係に重点を置いている。 本稿では,スケーラブルなトポロジの下でのアクティベーション関数(AF)の役割を象徴的に説明することにより,部分的に説明可能な学習モデルを実現する。
  論文  参考訳（メタデータ） (2020-06-10T20:30:15Z)

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

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