《Ordered Neurons：Integrating Tree Structures into Recurrent Neural Networks》阅读笔记

Conference from: ICLR 2019

Paper link: [OpenReview] [PDF]

本文拟解决的问题

自然语言具有显著的层级结构特征，小的语言单元（例如短语）被嵌套包含在大的语言单元（例如从句）中，这样的层级结构往往能够通过类似一棵树的形式（语法分析树）来表示出来，如下图：
自然语言的层级结构

作者认为人类的大脑也能隐式地捕捉到自然语言的这种内在特征，原因在于小孩子在习得语言的时候并没有被提供标注了的语法树。这一发现启发了作者，是否能通过一些方式使得神经网络模型也能隐式学习到这种自然语言的内在层级结构特征。

问题的意义

从实际的角度出发，把自然语言的树形结构集成到神经网络语言模型中有如下几个好处：

能够获取自然语言不同层级上的抽象表示
能够帮助建模不同语言成分之间的关系，同时能帮助解决长效依赖问题（通过在梯度反传的时候提供shortcuts）
能够帮助模型有一个更好的归纳偏向（inductive bias），提高模型的泛化能力，使之能够用更少的数据达到相同水平

本文提出的模型

其中包含的直觉

语法分析示意图

给定一个tokens构成的序列 $S=(x_1, ..., x_T)$ ，以及与之对应的语法分析树，如图(a)，其中NP为名词性短语，VP为动词性短语，模型的目标就是通过给定的序列去推断句子内在的树形结构。对于LSTM而言，每个时间步 $t$ 的输出 $h_t$ ，理想情况下应该包含结点 $x_t$ 到分析树树根 $S$ 路径上的所有信息。如图©，给出了在 $t$ 时刻涉及 $x_t$ 的所有语言成分，这些语言成分就是应该（在理想情况下）全部被包含在 $h_t$ 之中的。

所以一个直观的想法就是：可以使用隐层状态中的一组神经元去代表分析树中的某一个句子成分。然而尽管隐层向量的的维度是固定的，但从叶子结点到根结点的路径中的每个句子成分可能会随句子和时间步的不同，其长度有所变化。所以一个比较好的方法就是让模型动态地把固定的隐层状态分配给分析树路径中的每一个结点（句子成分）。

本文提出了Ordered Neurons，一种能让模型的不同神经元学习不同的时间跨度的信息的诱导偏向。在其中，排序较高的神经元（在分析树中更靠近根节点一边的）偏向于学习到长期或是全局的信息；而排序较低的神经元（在分析树中更靠近叶子节点一边的）偏向于学习到短期或是局部的信息。

实现Ordered Neurons的方式就是：每当擦除或更新一个high-ranking的神经元的信息，必须同时擦除或更新一个low-ranking神经元的信息。换句话说，就是low-ranking的神经元总是要比high-ranking的神经元更新得更频繁，而这个更新的优先级（即神经元的顺序）就是作为模型结构的一部分，是预先定义好的。

具体实现（数学公式）

本论文提出了一个新的RNN单元，叫做ON-LSTM(Ordered Neurons LSTM)：

常规LSTM的部分公式

以上的部分是和常规的LSTM一模一样的。而不一样的部分就在于cell state的计算方法，传统的LSTM是： $c_t = f_t * c_{t-1} + i_t * \hat{c_t}$ 。其中遗忘门 $f_t$ 和输入门 $i_t$ 分别用来控制细胞状态 $c_t$ 的擦除和写入。由于这些门对于每个神经元都是单独计算的，所以传统的LSTM很难去建模神经元之间的句子层级信息。

新的激活函数：cumax()

为了保证更新频率的顺序，论文提出了一种激活函数：

$\hat{g}=cumax(...)=cumsum(softmax(...))\tag{6}$

其中cumsum是累加求和（即对softmax的结果求前缀和）。后面将说明 $\hat{g}$ 可以视作是二进制门 $g=(0, ..., 0, 1, ..., 1)$ 的平均期望形式。这里的二进制门把细胞状态分成两段：包含0的一段和包含1的一段，由此就可以保证对神经元的擦除或更新是有序的。

引入确定的随机变量 $d$ 来表示 $g$ 中的第一个1的位置，那么有：

$p(d)=softmax(...)\tag{7}$

这样就能计算出 $g$ 中的第 $k$ 个元素是1的概率：

$p(g_{k}=1)=p(d\leq k)=\sum_{i\leq k}{p(d=i)}\tag{8}$

理想情况下， $g$ 应该就是一个确定的二进制门，但是由于离散随机的运算没法计算梯度，就只能在实际中采用它的期望版本，也就是softmax后的的累加和了。由于 $g_k$ 是二进制的，因此累加softmax的前 $k$ 项的结果就等同于 $\Bbb{E}[g_k]$ ，因此就有 $\hat{g}=\Bbb{E}[g]$ 。

基于cumax的细胞状态更新方法

基于cumax函数，用于控制不同句子成分的遗忘门和输入门如下：
用于控制句子不同成分的遗忘门和输入门

其中的遗忘门 $\tilde{f_t}$ 是从0到1单调递增的，而输入门 $\tilde{i_t}$ 则是从1到0单调递减的。这两者作为一个更高层次的控制门（论文中称为“master gates”），用来控制细胞状态的更新操作。

下面是基于新的控制门的细胞状态更新规则：

其原理说明如下：

假设遗忘门 $\tilde{f_t}=(0, ..., 0, 1, ..., 1)$ ，其分界点为 $d_t^f$ ，那么给定公式(12)和(14)，前一个时间步的细胞状态 $c_{t-1}$ 的前 $d_t^f$ 个神经元会完全被擦除，这个操作的含义就相当于关闭当前的某个句子成分。一个较大的 $d_t^f$ 就相当于关闭high-level的句子成分，反之同理，一个较小的 $d_t^f$ 表示一个low-level的句子成分被关闭，而高层次的信息则会为之后的信息处理保留。
假设输入门 $\tilde{i_t}=(1, ..., 1, 0, ..., 0)$ ，其分界点为 $d_t^i$ ，那么给定公式(13)和(14)，一个较大的 $d_t^i$ 意味着当前的输入 $x_t$ 包含了长期的信息，需要被放到high-level的神经元中保留若干个时间步；反之，一个较小的 $d_t^i$ 意味着当前的输入 $x_t$ 只包含了局部的信息，会在之后的时间步中很快被擦除。
遗忘门和输入门的乘积 $w_t$ 代表了 $\tilde{f_t}$ 和 $\tilde{i_t}$ 中的重叠部分，只要这个重叠部分存在，对应的这一段神经元就会同时需要保留上一个时间步的信息并添加当前时间步输入 $x_t$ 中的新信息，这一部分就会采用标准的LSTM更新方法进行更新（如上面图©中的 $x_3$ ）。

一个汇总的表格如下：

$\tilde{f_t}[k]$ 的取值	$\tilde{i_t}[k]$ 的取值	第 $k$ 个神经元的最终更新公式	备注说明
0	0	$c_t[k] = 0 * c_{t-1}[k] + 0 * \hat{c_t}[k] = 0$	遗忘掉之前的信息，同时也不需要编码新信息
0	1	$c_t[k] = 0 * c_{t-1}[k] + 1 * \hat{c_t}[k] = \hat{c_t}[k]$	遗忘掉之前的信息，编码新信息
1	0	$c_t[k] = 1 * c_{t-1}[k] + 0 * \hat{c_t}[k] = c_{t-1}[k]$	保留之前信息，无需编码新信息
1	1	$c_t[k] = f_t * c_{t-1}[k] + i_t * \hat{c_t}[k]$	同时需要保留之前信息和编码新信息（重叠部分）

当然上面的解释是采用二进制门 $g$ 的解释，但实际中会采用期望 $\hat{g}$ 。

考虑到上述的控制门 $\tilde{f_t}$ 和 $\tilde{i_t}$ 是粗粒度的（控制的是句子成分中的层级结构，其深度不会很深），因此不需要细粒度的参数。所以实际中，计算 $\tilde{f_t}$ 和 $\tilde{i_t}$ 的参数采用的目标维度为 $D_m=\frac{D}{C}$ ，其中 $D$ 是隐层状态维度， $C$ 是一个常数。总共的 $D$ 个神经元会被分成 $\frac{D}{C}$ 组，每组 $C$ 个神经元。在运算之前，会通过将 $\tilde{f_t}$ 和 $\tilde{i_t}$ 的每一个元素重复 $C$ 次来获得一个 $D$ 维的向量。

实验

作者在四个任务上进行了实验：语言模型、无监督的句子成分分析、针对性的句法评估、逻辑推理。

语言模型

在Penn TreeBank（PTB）数据集上进行实验。为了公平比较，这里采用了和另一个模型AWD-LSTM相似的超参设定、正则化和优化方法。使用的模型为三层ON-LSTM结构，隐层1150，词向量维度400。对于高层次的控制门（master gates）而言，选取的常数 $C$ 为10，其维度为1150/10=115。对于模型的不同部分（中间的输出），分别施加了不同dropout概率(0.5, 0.3, 0.45, 0.1)，模型权重有0.45的dropout概率。其结果如下图：
语言模型实验结果
其中比ON-LSTM取得更优效果的AWD-LSTM也是研究通过改变RNN的softmax层去提升效果的工作。

无监督的句子成分分析

这个任务的目标是让模型去预测给定句子的句子结构（语法树），然后和专家标注的进行比较。使用的数据集为WSJ10和WSJ测试集。WSJ10是从WSJ数据集选出来的长度（包含词语个数）小于等于10的句子，并去除了标点符号和空元素。而WSJ测试集包含不同长度的句子（没有上面的限制条件）。

这一任务就直接使用上一任务训练的（在验证集上表现最优的）语言模型来做。预测方法：每个句子的一开始都将对应的RNN隐层向量初始化为0向量，然后依次将每一个词语喂入输入层。在每一个时间步 $t$ ，都通过如下公式估计 $d_t^f$ ，直觉上的理解就是每个时间步关闭的句子成分相对来说位于哪个层级：
通过遗忘门推断每个时间步的分割点
其中的 $p_f$ 就是各个分割位置的概率分布， $D_m$ 为隐层向量维度。给定关闭的位置 $\hat{d_i^f}$ ，就可以使用自上而下贪心分析算法（From一篇引文《Neural language modeling by jointly learning syntax and lexicon》）来与监督预测句子成分的结构。具体方法为：首先对 $\{\hat{d_t^f}\}$ 排序，然后对于排在第一位的 $\hat{d_t^f}$ ，将句子划分为 $((x_{<i}), (x_i, (x_{>i})))$ ，随后递归对 $(x_{<i})$ 和 $(x_{>i})$ 执行一样的过程，直到只剩一个词语。

实验结果如下图：
无监督句子成分分析实验结果
可以看到语言模型的第二层在WSJ测试集上获得了最优的效果，而第一层和第三层则不如第二层效果好。作者的推断是第一层和第三层分别与输入层和输出层相连，因此可能需要更加注重捕获、处理语言模型相关的本地信息，因此可能相对忽视了学习更加抽象的树形句子结构（有review指出这里的解释有点牵强，示意作者去做实验，例如在只包含两层的语言模型上的表现会怎样等）。

下图（包含在原文的附录中）给出了更多的基于ON-LSTM训练的语言模型的第二层导出的句子成分结构推断图（左），并与标注的ground truth（右）进行了比较。
更多的句子结构推断的例子

针对性的句法评估（Targeted Syntactic Evaluation）

这一任务是在2018年的一篇论文中提出的一组数据集，用于评估语言模型在三种不同的对句法结构敏感的情形下的表现。这三种情形分别是：主谓一致（subject-verb agreement）、反射回指（reflexive anaphora，后文的代词映射到前文中的实体）、否定项（negative polarity items）。

这个数据集包含在上述情形下的各种positive-negative pairs，positive指符合语法的，negative指不符合语法的，用来测试语言模型对此的辨别度（期望语言模型对符合语法的句子给出较高的概率）。实验结果如下图：
针对性的句法评估实验结果
总体上标准LSTM在short-term的任务上有好一些的表现，而ON-LSTM在long-term任务上表现更好一些。

逻辑推理

这一任务中的句子包含6个词语（即命题p1, p2, …, p6）和三个逻辑关系：与或非。例如一个句子可能是：“(p1 or (not p2)) and (p3 or (not p4))”。任务要求判定两个给定句子的逻辑关系（等价、蕴含、独立等，共7种可能的关系）。

作者在标准LSTM和ON-LSTM上分别进行了试验。模型结构为：两个句子经过一个RNN编码器，获取其最后的隐层向量 $(h_1, h_2)$ 作为句子编码。然后将 $(h_1, h_2, h_1 * h_2, abs(h_1 - h_2))$ 的拼接作为特征输入一个前馈神经网络分类器，包含7个类别。实验中RNN包含400个单元，单层，输入维度128。两个模型都在长度少于6的句子上进行训练，然后在最多包含长度12句子的测试集上进行测试，结果如下图：
逻辑推理实验结果
其中Tree-LSTM能在此数据集上获取更好的性能，是因为它提供了句子的树形结构（ground truth）作为输入。

总结和思考

这篇论文确实是写得非常棒，无论是背后的直觉性的想法还是所做的实验，抑或是对相关工作的全面的总结，拿到ICLR2019的最佳论文确实是实至名归。提出的ON-LSTM和cumax确实有让人眼前一亮的感觉，论文中阐述的对公式的直觉性解释也让人感觉十分合理，且逻辑清晰、简洁明了。

此前我也有过类似的动机：即目前对自然语言的层级结构都是人为划分的，词语、句子、段落、篇章等等，能否设计一种结构能优雅地去自动处理这样的层级结构呢。而这篇论文就提出了一种自适应的方法去做这个事情，虽然有一些限制，但是也能提供很多启发。

一些想法：

这篇论文既使用了原本LSTM的控制门，又使用了新的主控制门，这两者能否简化、合并成一组控制门呢？
这篇论文处理层级结构的方式还是和我预想的不太一样，在于：ON-LSTM对于不同长短的句子，编码后的向量维度都是相同的，能否让编码的size动起来呢？当处理较短的句子（或者low-level的句子成分）时，编码长度较小，因为其包含较少的信息；而处理较长的句子（或者high-level的句子成分）时，编码长度会自动结合low-level的句子成分的编码并进行扩充。
这篇论文相当于只是引入了一个累加的softmax操作就对神经元进行了排序（可以理解为：为模型引入了人类直觉引导的结构上的先验知识），确实是相当优雅，也启发我之后想问题的时候可以往这个方向去想（如何引入结构上的先验知识），并且确实是存在类似这种简洁的引入方式的。（一些简单的规律往往会被忽视，这是以后需要去关注的）
对应上面的(2)：能否结合ELMo去想这个问题？一个直觉性的常识是：任何的句子片段（乃至任何的与时间有关的序列），无论多长（词语、短语、句子、段落等等），当它单独存在时和它位于某上下文语境之中的表义往往会有区别。ELMo仅仅做了词语级别的上下文相关表示，那么能否将其扩展到任意的级别？（可以考虑下本文的自适应方法）
这篇论文提出的ordered + 自适应的方法应该是相当具有启发性的，总感觉这个思路可以迁移到更多的地方（如(3)中所说的结构上的先验知识），可能会对模型的可解释性有所帮助，比如：自适应地对输入排个序（识别出有用的和无用的输入，输入中各个部分的相关性等）、对模型参数排序（自适应scale模型）、对各个网络层的输出排个序（权重高的表示和权重低的表示、各个部分的相关性等）？甚至可以把网络弄得很大很大，甚至无限大，让模型自适应去判断该用哪些参数，计算复杂度太高的话那就采用一个概率，自适应地控制计算复杂度，参考基于概率的贝叶斯网络。（这里纯粹瞎想）
能否将上面的几条(2, 4)、(5)和此前的想法结合一下？也就是自适应地识别哪些该深挖（学习、提取出共有的部分），具体见OneNote笔记。
对Multi-head attention中的head排序呢？或者能否在ordered neurons中引入相互的attention机制？
和Memory Networks结合一下呢？层层索引本来就是压缩信息的很好的一个手段，能否将这种逐层索引的方法和这篇论文的排序思路结合一下？比如某一个知识，我并不需要真正知道这个知识，我只要知道在哪里能找到它（比如维基百科）可以了，那么我就能花费一点点的时间去学习。类似虚拟内存。
和对抗结合一下呢？这里不同排序的神经元也储存了不同的信息呀？