Artificial neural networks (ANNs) with recurrence and self-attention have
been shown to be Turing-complete (TC). However, existing work has shown that
these ANNs require multiple turns or unbounded computation time, even with
unbounded precision in weights, in order to recognize TC grammars. However,
under constraints such as fixed or bounded precision neurons and time, ANNs
without memory are shown to struggle to recognize even context-free languages.
In this work, we extend the theoretical foundation for the $2^{nd}$-order
recurrent network ($2^{nd}$ RNN) and prove there exists a class of a $2^{nd}$
RNN that is Turing-complete with bounded time. This model is capable of
directly encoding a transition table into its recurrent weights, enabling
bounded time computation and is interpretable by design. We also demonstrate
that $2$nd order RNNs, without memory, under bounded weights and time
constraints, outperform modern-day models such as vanilla RNNs and gated
recurrent units in recognizing regular grammars. We provide an upper bound and
a stability analysis on the maximum number of neurons required by $2$nd order
RNNs to recognize any class of regular grammar. Extensive experiments on the
Tomita grammars support our findings, demonstrating the importance of tensor
connections in crafting computationally efficient RNNs. Finally, we show
$2^{nd}$ order RNNs are also interpretable by extraction and can extract state
machines with higher success rates as compared to first-order RNNs. Our results
extend the theoretical foundations of RNNs and offer promising avenues for
future explainable AI research.

这项研究通过扩展第二阶循环神经网络的理论基础，证明存在一类有界时间的第二阶循环神经网络，具备图灵完备性，可以直接将转移表编码到其循环权重中，实现有界时间计算，并通过设计可解释。同时，该研究还展示了在有界权重和时间约束下，没有记忆的第二阶循环神经网络在识别正则语法方面优于传统的循环神经网络和门控循环单元等现代模型，并提供了识别任何一类正则语法所需的最大神经元数量的上界和稳定性分析。大量关于 Tomita 语法的实验证实了研究结果，并展示了采用第二阶循环神经网络进行解释和提取状态机时的成功率较一阶循环神经网络更高。这些结果拓展了循环神经网络的理论基础，并为未来可解释人工智能的研究提供了有希望的方向。

关于二阶递归神经网络的计算复杂性和形式层次的研究

On the Computational Complexity and Formal Hierarchy of Second Order  Recurrent Neural Networks

Various forms of regularization in learning tasks strive for different
notions of simplicity. This paper presents a spectral regularization technique,
which attaches a unique inductive bias to sequence modeling based on an
intuitive concept of simplicity defined in the Chomsky hierarchy. From
fundamental connections between Hankel matrices and regular grammars, we
propose to use the trace norm of the Hankel matrix, the tightest convex
relaxation of its rank, as the spectral regularizer. To cope with the fact that
the Hankel matrix is bi-infinite, we propose an unbiased stochastic estimator
for its trace norm. Ultimately, we demonstrate experimental results on Tomita
grammars, which exhibit the potential benefits of spectral regularization and
validate the proposed stochastic estimator.

本文介绍了一种基于 Chomsky 层次的直观简洁性概念，利用 Hankel 矩阵的跟踪范数作为频谱正则化器的高级模型，并提出了一种偏袒随机估计器以应对 Hankel 矩阵是双无限的事实，最终证明了频谱正则化在 Tomita 语法上的潜在优势以及提议的随机估计器的有效性。

光谱正则化：序列建模的归纳偏置

Spectral Regularization: an Inductive Bias for Sequence Modeling

Understanding recurrent networks through rule extraction has a long history.
This has taken on new interests due to the need for interpreting or verifying
neural networks. One basic form for representing stateful rules is
deterministic finite automata (DFA). Previous research shows that extracting
DFAs from trained second-order recurrent networks is not only possible but also
relatively stable. Recently, several new types of recurrent networks with more
complicated architectures have been introduced. These handle challenging
learning tasks usually involving sequential data. However, it remains an open
problem whether DFAs can be adequately extracted from these models.
Specifically, it is not clear how DFA extraction will be affected when applied
to different recurrent networks trained on data sets with different levels of
complexity. Here, we investigate DFA extraction on several widely adopted
recurrent networks that are trained to learn a set of seven regular Tomita
grammars. We first formally analyze the complexity of Tomita grammars and
categorize these grammars according to that complexity. Then we empirically
evaluate different recurrent networks for their performance of DFA extraction
on all Tomita grammars. Our experiments show that for most recurrent networks,
their extraction performance decreases as the complexity of the underlying
grammar increases. On grammars of lower complexity, most recurrent networks
obtain desirable extraction performance. As for grammars with the highest level
of complexity, while several complicated models fail with only certain
recurrent networks having satisfactory extraction performance.

本研究旨在探讨不同复杂度的 Tomita 文法上，从常用的循环神经网络中提取确定有限状态自动机的性能表现。研究结果表明，随着底层文法复杂度的提高，大多数循环神经网络的提取性能逐渐降低。

递归神经网络规则提取的比较研究

A Comparative Study of Rule Extraction for Recurrent Neural Networks

Rule extraction from black-box models is critical in domains that require
model validation before implementation, as can be the case in credit scoring
and medical diagnosis. Though already a challenging problem in statistical
learning in general, the difficulty is even greater when highly non-linear,
recursive models, such as recurrent neural networks (RNNs), are fit to data.
Here, we study the extraction of rules from second-order recurrent neural
networks trained to recognize the Tomita grammars. We show that production
rules can be stably extracted from trained RNNs and that in certain cases the
rules outperform the trained RNNs.

研究从训练过的 RNN 中提取规则的方法，结果表明在适当的情况下生产规则的效果优于训练过的 RNN。