用神经网络精确模拟概率有限自动机，可训练且可解释。
Symbolic Feedforward Networks for Probabilistic Finite Automata: Exact Simulation and Learnability
- 用向量和矩阵表示状态与转移，通过矩阵乘法实现概率传播。
- 在序列数据上训练后能完全复现真实自动机的行为。
- 适合对可解释性要求高的机器学习研究者使用。
我们提出一种形式化且可构造的理论，证明概率有限自动机（PFAs）可被符号前馈神经网络精确模拟。该架构将状态分布表示为向量，转移表示为随机矩阵，通过矩阵-向量乘积实现概率状态传播，无需递归即可并行、可解释且可微分地模拟PFA动态。我们形式化定义了概率子集构造、ε-闭包及分层符号计算下的精确模拟，并证明了PFAs与特定神经网络类之间的等价性。进一步表明，这些符号模拟器不仅表达能力强，且具备可学习性：在带标签序列数据上使用标准梯度下降优化后，能恢复真实PFAs的精确行为。这一可学习性（命题5.1）是本文核心。结果在严格的代数框架下统一了概率自动机理论与神经结构，弥合了符号计算与深度学习之间的鸿沟。
原文摘要 · Abstract (English)
We present a formal and constructive theory showing that probabilistic finite automata (PFAs) can be exactly simulated using symbolic feedforward neural networks. Our architecture represents state distributions as vectors and transitions as stochastic matrices, enabling probabilistic state propagation via matrix-vector products. This yields a parallel, interpretable, and differentiable simulation of PFA dynamics using soft updates-without recurrence. We formally characterize probabilistic subset construction, $\varepsilon$-closure, and exact simulation via layered symbolic computation, and prove equivalence between PFAs and specific classes of neural networks. We further show that these symbolic simulators are not only expressive but learnable: trained with standard gradient descent-based optimization on labeled sequence data, they recover the exact behavior of ground-truth PFAs. This learnability, formalized in Proposition 5.1, is the crux of this work. Our results unify probabilistic automata theory with neural architectures under a rigorous algebraic framework, bridging the gap between symbolic computation and deep learning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。