Neural Networks as Universal Finite-State Machines: A Constructive Deterministic Finite Automaton Theory
Sahil Rajesh Dhayalkar
我们提出了一个完整的理论和经验框架,将前馈神经网络作为通用的有限状态机器(N-FSM)。 我们的结果证明,有限深度的ReLU和阈值网络可以通过将状态过渡到深度神经层来精确模拟确定性有限自动机(DFA),具有所需的深度,宽度和状态压缩的正式特征。 我们证明DFA过渡是线性可分离的,二进制阈值激活允许指数压缩,Myhill-Nereode等效类可以嵌入到连续的潜在空间中,同时保持可分离性。 我们还将表达式边界形式化:固定深度前馈网络无法识别需要无边界内存的不规则语言。 与以前的基于指导或探索性的研究不同,我们提供了建设性的证明,并设计了明确的DFA未滚动的神经架构,这些架构在经验上验证了每一项主张。 我们的结果将深度学习、自动机理论和神经符号计算联系起来,为如何在连续的神经系统中实现离散符号过程提供了严格的蓝图。
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 allo...