我们证明了RNN能够准确地实现有界深度的堆栈，以最优的效率捕获人类语言的构建块，这一结果证明了RNN可以准确地实现有界深度的堆栈。
2015年，安德烈·卡帕西发表了一篇关于递归神经网络不合理有效性的博客文章，现在已经很有名了。1在这篇文章中，他分享了他对RNN的经验效用和学习行为感到的一些惊奇。为了总结这种奇妙的感觉，卡帕西强调：
我们将训练RNN逐个字符生成文本，并思考这样一个问题：“这怎么可能？”
重读卡帕西最近的博客文章，即使是在大型预先培训的变压器的时代，我仍然发现中等大小的RNN对于学习高度结构化的输出空间的有效性很有趣。例如，Andrej展示了一个针对Wikipedia培训的RNN的样本，它不仅学习生成相对语法的英语，而且学习生成Wikipedia的文章结构甚至有效的XML代码。
在这篇博客文章中，我们描述了理解卡帕西问题的最新进展--这怎么可能呢？
从经验上看，RNN在学习语言语法方面非常有效！一方面，要真正处理总体上的层次结构，有必要模拟堆栈中的推送和弹出元素，这是语法分析中的基本操作。另一方面，人们对RNN持健康的怀疑态度；他们可能只是像n元语法模型那样统计可能(长)的单词序列，并由于单词嵌入而分享一些统计强度。
那么，到底是哪一个呢？RNN的模糊隐藏状态似乎不适合堆栈一样的行为，已经建立了许多模型来弥补这一点，从LSTM的有序神经元变体(沈等人，2019年)到用显式外部堆栈扩展的RNN(Joulin和Mikolov，2015)。甚至已经证明，RNN一般不能识别层次化语言(Merrill等人，2020)！堆栈的情况看起来并不乐观，这有助于我们澄清这个问题是如何可能的：RNN中类似堆栈的行为在现实环境中是可能的吗？
我们为这个问题增加了一个洞察力：在处理自然语言时，我们可以限制堆栈上需要存储的最大数量的东西。一旦你假设了这一点，我们非常惊讶地证明了以下内容的正式版本：
RNN可以如此高效地将它们的隐藏状态转换为有限容量的堆栈，以至于它们可以使用渐近最优的少量隐藏存储单元来生成一种有界的层次化语言。
我们证明了RNN可以做到这一点，而不是说他们学会了这样做。然而，我们的证明包括RNN可以实现有界深度堆栈的显式机制，事实上，我们还为只使用其门的LSTM提供了一个单独的、更有效的机制。
我们的结果改变了我对RNN的看法。RNN确实不能实现任意深度的堆栈(就像下推自动机一样)。它们的内存是有限的，所以它们是有限状态机)。但是，它们可以将隐藏状态转换为堆栈结构的内存，这意味着它们可以处理一些(有界的，层次化的！)。语言的效率比人们在学习有限状态机时想象的要高得多。我们认为，这意味着乔姆斯基层次不是我们应该用来描述神经模型表达能力的(唯一)东西；即使在最简单的(有限状态)制度下，这些网络的记忆结构也很有趣。我们希望我们的证明和构造能帮助人们思考和分析RNN行为，并启发神经体系结构的未来改进。
本文基于论文《RNNS可以生成具有最佳内存的有限层次化语言》，发表于EMNLP 2020，与Michael Hahn、Surya Ganguli、Percy Leung和Chris Manning联合发表。
理论tl；dr：我们引入了DYCK-((k，m))，这是一种嵌套深度至多为(M)的k型方括号语言，并证明了RNN可以在O(m\log k)个隐含单元中生成这些语言，比已有的使用O(k^{m/2})的结构有了指数的改进，我们还证明了这是紧的，使用o(m\log k)是不可能的。
我们将从自然语言处理的第二个最有趣的部分开始：语言2。在人类语言中，单词的发音顺序很重要[需要引用]。但它们的顺序并不能即刻提供整个故事；人类语言中有丰富的结构，它控制着单词和短语的意义是如何组成的，从而形成更多语言的意义。由于语言中的等级依赖，语言的线性(即，给定的)顺序的不足是显而易见的。例如，考虑一下下面的句子：
在这里，例外的仍然是厨师，而不是商店，这表明(厨师，是)关系不是基于线性顺序。我们可以或多或少地继续玩这个游戏，只要我们愿意：
英语中的主谓一致关系，如(chef，is)，是语言等级性质的一个很好的例子。更普遍的是，语言的句子等级关系是以句法注释的形式描述的，通常是以树的形式，如下面的短语3：
这两个树为短语自然语言处理提供了两种截然不同的解释。在最左边的树中，语言和处理首先结合在一起。然后，语言处理与自然结合。所以，语言处理是以其自然性为特征的。这是对自然语言的有意解读吗？我认为，不是。在最右边的树中，我们有自然与语言的结合。然后自然语言和处理结合在一起，这意味着我们正在处理一种叫做自然语言的东西。这更像是一种语言。
语法的一种常见形式是上下文无关文法，对于自然语言和像XML这样的语言都是如此。上面给出的短语自然语言处理(Natural Language Processing)的例子是非正式的，但这里有一个完整的例子4：
树上的标签非常有用，但我们不会深入讨论它们的含义。要查看这种结构和堆栈之间的联系，请考虑对树进行预排序遍历。
(s(np(Dt The)(NN个孩子))(VP(Vbd Ate)(np(Dt The)(nn个蛋糕)(PP(Jj With)(np(Dt A)(np(Dt A)(nn勺子)。
当然，处理真实语言的一个关键困难是没有提供内部节点(如(S)；这就是为什么解析对于自然语言来说并不是微不足道的。但是，即使可以访问这些内部节点，人们也需要能够从内部节点推送和弹出值。)当然，处理真实语言的一个关键困难是没有提供内部节点(如(S)；这就是为什么解析对于自然语言来说并不是微不足道的。但是，即使访问这些内部节点，也需要能够从内部节点推送和弹出值)。当然，处理真实语言的一个关键困难是没有提供内部节点(如(S)；这就是为什么解析对于自然语言来说并不是微不足道的。但是，即使访问这些内部节点，也需要能够从内部节点推送和弹出值。一般来说，这是正确的，对于RNN的特殊情况也是如此。
那么，如果解析自然语言需要一个堆栈，那么RNN在做什么呢？粗略地说，RNN可以被认为是应用了两种策略中的一种(或某种组合)：
表面统计：通过汇总大量统计数据，了解一些单词(如“the”)如何出现在不同的单词(名词)组之前，以及哪些名词可能会“吃掉”等等，网络可能只是学习了一个软版本的n元语法语言模型，在单词之间共享统计强度，并允许相对较大的n。
类似堆栈的行为：通过模拟堆栈，RNN可能会“以正确的方式”处理语言，将单词或抽象元素作为观察到的标记进行推送和弹出，并实现对句子的隐式解析。
很可能，事实既不是表面的统计故事，也不是确切的堆栈行为故事。然而，我们在这项工作中能够展示的是，RNN能够准确地模拟有限容量的堆栈，并且我们提供了它们提供该行为的可学习参数的清晰、准确的规范。不仅如此，它们执行的堆栈模拟在很大程度上也是尽可能高效的(作为模拟特定大小的堆栈所需的隐藏单元的数量的函数)，所以这样的行为不仅仅是。这是RNN能够最有效地表达的一组功能。我们希望这些见解能够指导RNN未来的实证分析，以及建模工作。
神经网络的计算能力在很大程度上取决于人们对某些“实现细节”的假设。例如，您可能听说过RNN是图灵完全的！5另一方面，最近的研究表明RNN没有能力识别最简单的需要堆栈的语言。6个。
这些工作的不同之处在于它们对如何使用RNN所做的假设。如果你用无限的位数表示RNN的每个隐藏单元，并允许它读取整个输入(句子)，然后根据需要将其展开尽可能长的时间，那么你就会得到图灵完成的结果。然而，这并不能反映RNN在实践中是如何使用的。如果你用随输入长度对数缩放的位数来表示RNN的每个隐藏单元，并且每个输入符号只展开RNN一次，那么结果就是RNN。但是，如果你用不限数量的位来表示RNN的每个隐藏单元，并且允许它读取整个输入(句子)，然后根据需要展开RNN，那么你就得到了图灵完成的结果。然而，这并不能反映RNN在实践中是如何使用的。
在我们的工作中，我们考虑了一种更有约束的设置：我们假设RNN中的每个隐藏单元都具有一个由有限位数指定的值--该值不会随着序列长度或语言复杂性的任何度量而增长。正如我们将展示的那样，这对我们可以研究的RNN的属性类型有非常有趣的影响！
危险：非常理论性的段落最后，你会看到我们提到大多数早期的工作是评估RNN的识别语言的能力。这是正式的语言演讲；语言是词汇表\(\Sigma\)中的一组字符串\(\Mathcal{L}\subseteq\Sigma^*\)。为了识别任何字符串的语言\(\Mathcal{L}\)，RNN可以读取\(\Sigma^*\)中的整个字符串，并在最后对该字符串是否属于\(\Mathcal{L}\)做出二元判定。在这项工作中，RNN可以读取\(\Mathcal{L}\)中的整个字符串，并在最后产生关于该字符串是否属于\(\Mathcal{L})的二元决策。在这项工作中，我们将RNN称为生成一种语言\(\Mathcal{L}\)。这是我们强加的一个新要求，以使理论设置更像RNN在实践中的使用方式：逐个令牌预测输出令牌！实际上，这强制了一个约束，即RNN的隐藏状态在每个时间步都是可读的；如果你对细节感兴趣，可以看看报纸。
在这一节中，我们将介绍我们将要使用的语言：Dyck-\((k，m)\)。我们从Dyck-\(k\)开始，这是一种嵌套良好的\(k\)型方括号语言。类似于语言中的层次结构，如下例所示，突出了中心嵌入子句中主语和动词之间的关系：
事实上，尽管Dyck-(k\)很简单，但在很大程度上，它是一种典型的层次化语言。回想那些上下文无关的语言，比如那些可以由选区文法描述的语言，结果发现Dyck-(k\)是所有这些语言的核心，这在Chomsky-Schützenberger定理中得到了形式化。
我们讨论的层次结构和堆栈之间的联系在Dyck-\(k\)中是直接的：在看到类型为\(i\)的左方括号时，必须将该方括号的内存推入堆栈；在看到相应的类型为\(i\)的右方括号时，它将被弹出。
但考虑到这位立法者所写的碎片化法律，从上面的例子来看，这不是有点…吗？难读？如果你花一秒钟的时间，你就会发现记者正在询问的是一名制定法律的立法者，而这些法律是判决的主题。但考虑一下下面的句子：
我觉得这一句更容易读懂。部分原因是第一句有嵌套在中间的子句，这需要你保持大量的记忆，以了解主语和动词是如何配对的。第二句没有那么深入；在看到之前，你必须在周围保留一段时间的法律，但你只需要在周围保留两项(法律，立法者)，然后你就可以看到书面的内容，这样可以让立法者在某种程度上不那么精确地记忆。
这种中心嵌入深度与解析句子所需的堆栈深度之间存在联系。7实际上，你需要多少内存才能理解其中的含义。你只有那么多的工作记忆，当他们测试你的极限时，事情就很难理解了。Dyck-\(k\)可以任意深度嵌套，但人类语言的深度很少超过中心嵌入深度3.8。
因此，我们没有研究RNN生成Dyck-\(k\)的能力，而是对方括号堆栈的最大深度设置了一个界限，称之为\(M)，并称之为Dyck-((k，m)\)。如果您是Chomsky层次结构(规则语言、上下文无关、上下文敏感、递归可枚举)的粉丝，这意味着Dyck-((k，m)\)是一种规则语言，因此可以通过有限的。如下面的Dyck-\((2，2)\)示例所示：
在我们的有限精度设置下，众所周知，对于任何正则语言，都可以采用最小确定性有限状态机，并使用有限精度将其编码到RNN中。因此，一开始，我们为什么要提出关于RNN及其生成Dyck-\((k，m)\)能力的新理论问题似乎令人困惑。
这是因为在RNN中使用这些DFA编码，我们在RNN中需要大约(k^{m+1})个隐藏单元才能生成Dyck-((k，m)\)。这是很多的；考虑一下\(k=100{，}000\)作为词汇表大小，\(m=3\)作为堆栈深度；我们将需要\(100{，}000^4=10^{20})个隐藏单元！
为了便于解释，我们现在将讨论如何在RNN中构建有界堆栈，首先是一个扩展模型，它可以做流行的RNN做不到的事情。我们的扩展模型是二阶RNN，它可以根据您看到的输入从递归矩阵\(W_x\)中进行选择。
考虑使用\(Km\)维向量对最多\(m\)个元素的堆栈进行编码，每个元素的维度为\(k\)：
将每种\(K)种可能的支架类型看作是由一个\(k\)个热向量表示的。我们希望堆栈的顶部位于插槽\(1\)中。因此，当我们推送一个元素时，我们会将其直接写入插槽\(1\)。无论插槽\(1\)中的内容是什么，我们都希望从插槽\(1\)移出以腾出空间，这可以使用一个矩阵\(W_{\text{Push}}\)来完成，如下所示：
请注意，如果堆栈上已有\(m\)个元素，则最后一个元素将从隐藏状态移位。接下来，如果我们希望从堆栈中弹出顶部元素，使用单独的矩阵\(W_{\Text{POP}}\)可以很容易地完成此操作，如下所示：
这适用于我们的二阶RNN，因为如果我们看到左方括号，我们可以选择应用\(W_{\text{ush}}\)来在顶部为其腾出空间，如果我们看到右方括号，我们可以选择应用\(W_{\text{op}}\)来忽略其相应的左方括号。
为什么这不适用于人们在实践中使用的简单RNN？因为它只有一个\(W\)矩阵，而LSTM也是如此。所以我们需要更聪明一些。
我们将通过使用一个多2个空间的因子，即2mk维，来解决只有一个W矩阵这一事实。
这对应于可以存储堆栈的两个\(Mk)大小的位置。我们将其中一个称为\(h_{\text{POP}}\)，另一个称为\(h_{\text{Push}}\)，表示我们在应用弹出时写入堆栈，在应用推送时写入堆栈。无论在哪个位置不写入堆栈，我们都将确保为空(即等于0)。
有了这些保证，我们可以使用单个\(W\)矩阵同时读取\(h_{\text{op}}\)和\(h_{\text{ush}}\)。通过堆叠\(W_{\text{ush}}\)和\(W_{\text{op}}\)矩阵，我们可以做到这一点，并使用相同的矩阵同时写入\(h_{\text{op}}\)和\(h_{\text{op}}\)。
因此，查看\(wh\)，我们已经从\(h_{\text{op}}\)和\(h_{\text{ush}}\)中读取并写入这两个数据。但我们不想同时写入这两个数据；我们只需要与我们实际看到的输入相对应的\(h_{\text{POP}}\)或\(h_{\text{Push}}\)中的一个。为此，我们使用\(Ux_t\)术语。实际上，当\(x_t\)是左方括号时，\(Ux_t\)会将一个非常负值添加到\(h_{\text{op}}\)中，当x_t是右方括号时，\(Ux_t\)执行相同的操作，但对于\(h_{\text{Push}}\)。因此，对于\(Wh+Ux_t\)，我们确保只写入\(h_{\text{op}}\)或\(h_{\text{ush}}\)中的一个，并且
这就对了！它需要额外的内存系数-\(2\)，但这正是从RNN中的有限深度堆栈推送或弹出的一种方式。
LSTM的提出是为了改进学习，解决RNN的零梯度问题。另外，我们在工作中考虑的是表现力，而不是学习，所以我们研究了LSTM中额外的门控函数是否能让它们更有效地实现堆栈。
我们发现，是的，虽然我们需要\(2mk\)来使用简单RNN实现我们的堆栈，但是我们需要\(mk\)(就像对于二阶RNN一样)来实现LSTM，这是一个两倍的改进。有趣的是，我们用来证明这一点的机制完全独立于我们在简单RNN中使用的推/弹组件；相反，它完全依赖于LSTM的门。
构造工作的确切机制有点复杂，所以我们在这里勾勒出主要思想。让我们从一个LSTM内存在处理序列时如何工作的示例开始。
从图中可以清楚地看出，我们的LSTM堆栈的顶部并不总是插槽1，就像在简单的RNN构造中那样。相反，堆栈的顶部始终是距离插槽1最远的非空槽，堆栈的底部是插槽1。当前堆栈上的所有托架都存储在单元状态\(c_t\)中，但只有堆栈的顶部元素被允许通过输出门进入隐藏状态\(h_t\)。这在上图中显示为灰色阴影状态。
回想一下LSTM等式，如果愿意也可以跳过它们，记住LSTM有一个输入门、一个输出门、一个遗忘门和一个新的单元候选：
$$i_t=\sigma(W_ih_{t-1}+U_ix_t+b_i)$o=\sigma(W_oh_{t-1}+U_ox_t+b_o)$f_t=\sigma(W_fh_{t-1}+U_fx_t+b_f)$\tilde{c}_t=\text{tanh}(W_{。}}x_t+b_{\tilde{c}})$c_t=i_t\cot\tilde{c}_t+f_t\cot c_{t-1}$h_{t}=o_t\cot\text{tanh}(C_T)$$。
直观地，输入门确定将哪些新内容(来自{c}t\)添加到存储单元\(c_t\)，以及将哪些旧内容(来自\(c_{t-1}))复制到存储单元\(c_t\)。输出门\(o_t\)确定哪些信息从单元\(c_t\)流向隐藏状态\(h_t\)。
让我们来看看每个门如何对我们在示例中看到的内存管理做出贡献。我们将讨论每个门在两种堆栈操作(Push和Pop)下的行为。
为了实现推送，新的单元候选单元\(\tilde{c}_t\)的工作是尝试向堆栈顶部写入左方括号。这有点困难，因为正如我们所说的，应该写入新的堆栈顶部的位置可能在存储器的任何\(m\)个槽上。因此，新的单元候选单元，通过\(U_{\tilde{c}_t}x_t\)实际上尝试将\(x_t\)指定的方括号的标识写入所有m个堆栈槽。这之所以有效，是因为新的候选单元格依赖于\(1\)仅用于应写入新元素的堆栈槽的\(1\)输入门，以及\(0\)其他位置的输入门，因此所有其他槽都不受影响。
.