Institute of Computer Science of the Czech Academy of Sciences, P.O. Box 5, 18207 Prague 8, Czech Republic.
Neural Netw. 2020 Aug;128:199-215. doi: 10.1016/j.neunet.2020.05.006. Epub 2020 May 11.
In order to refine the analysis of the computational power of discrete-time recurrent neural networks (NNs) between the binary-state NNs which are equivalent to finite automata (level 3 in the Chomsky hierarchy), and the analog-state NNs with rational weights which are Turing-complete (Chomsky level 0), we study an intermediate model αANN of a binary-state NN that is extended with α≥0 extra analog-state neurons. For rational weights, we establish an analog neuron hierarchy 0ANNs ⊂ 1ANNs ⊂ 2ANNs ⊆ 3ANNs and separate its first two levels. In particular, 0ANNs coincide with the binary-state NNs (Chomsky level 3) being a proper subset of 1ANNs which accept at most context-sensitive languages (Chomsky level 1) including some non-context-free ones (above Chomsky level 2). We prove that the deterministic (context-free) language L={01∣n≥1} cannot be recognized by any 1ANN even with real weights. In contrast, we show that deterministic pushdown automata accepting deterministic languages can be simulated by 2ANNs with rational weights, which thus constitute a proper superset of 1ANNs. Finally, we prove that the analog neuron hierarchy collapses to 3ANNs by showing that any Turing machine can be simulated by a 3ANN having rational weights, with linear-time overhead.
为了细化对离散时间递归神经网络（NN）的计算能力的分析，将等效于有限自动机（乔姆斯基层次结构的第 3 级）的二进制状态 NN 与具有有理权重的模拟状态 NN 进行区分，这些 NN 是图灵完备的（乔姆斯基第 0 级）。我们研究了一个二进制状态 NN 的中间模型αANN，它扩展了α≥0个额外的模拟状态神经元。对于有理权重，我们建立了一个模拟神经元层次结构 0ANNs ⊂ 1ANNs ⊂ 2ANNs ⊆ 3ANNs，并将其前两个级别分开。特别是，0ANNs 与二进制状态 NN（乔姆斯基第 3 级）重合，是接受最多上下文敏感语言（乔姆斯基第 1 级）的 1ANNs 的真子集，包括一些非上下文无关语言（高于乔姆斯基第 2 级）。我们证明了确定性（上下文无关）语言 L={01∣n≥1} 不能被任何 1ANN 识别，即使使用实权重也是如此。相比之下，我们表明接受确定性语言的确定性下推自动机可以通过具有有理权重的 2ANNs 来模拟，因此，2ANNs 构成了 1ANNs 的真超集。最后，我们通过证明任何图灵机都可以通过具有有理权重的 3ANN 模拟，并且具有线性时间开销，从而表明模拟神经元层次结构崩溃到 3ANNs。
