论文笔记：Recurrent Neural Network Grammars

1.简介

“Recurrent Neural Network Grammars” 发表与NAACL 2016，这篇论文中提出了 RNNG 模型，在之后也有很多工作基于此，像URNNG（Unsupervised RNNG）和融合RNNG的NMT等。论文中首先介绍了RNNG的判别模型，然后进行了改动，定义了生成模型，然后又介绍了RNNG作为语言模型的效果。

2.定义基础

RNNG来源于统计自然语言处理中的CFG（Context-Free Grammar）文法以及它的衍生PCFG等，这一点从它的定义中就可以看出来。在论文的第二节，RNNG定义为一个三元组

(

)

(N, \Sigma, \Theta)

$(N, Σ, Θ)$ ,这很像CFG的定义，只不过CFG中定义了规则集合，例如

→

NP\rightarrow MP\space NP

$N P \to M P N P$ 之类的，在RNNG中，把这些都包含在RNN网络中，使用的时候会动态生成。

3.Top-Down句法生成方法

首先，论文中所使用的句法分析方法是基于转移的。（transition-based），除此之外，还有基于动态规划的（chart-based）以及自顶向下贪心的（greedy top-down）以及使用序列的（sequence to sequence）的。
对于 transition-based 的模型，句法生成的方式有三种：

Top-Down 自顶向下
Bottom-Up 自底向上
In-Order 中序遍历的

在这篇论文中，使用的 Top-Down的方式，其实自顶向下和自底向上的方式区别还是很明显的，在选择上有一个很明显的区别就是自顶向下方式很适合不确定分支数的树结构数据，因为在合并的时候只需要合并父节点就可以了，但是自底向上的方式一般都会选择二叉化的数据，因为合并父节点的时候如果不确定当前节点有几个子节点，那么栈里的数据就不知道取出几个。

4.Top-Down的句法分析和生成

4.1 判别式模型

论文中判别式的模型跟之前的很多工作一致描述的已经很清楚了。这里注意 transition-based 的句法分析方式一般都会维护几个数据结构：

句法树栈（Stack）：用来保存局部或者整体的句法树
字符序列（Buffer）：用来保存终结符单词序列
还有一些动作，例如这里就定义了NT(X)，Shift 和 Reduce，不同的系统可能会有不同的定义，这个地方注意虽然像是一个集合，但是本文中或者后来的很多论文中都是也是使用一个栈来保存动作序列的（在本文中就是使用Stack-LSTM的方式保存动作历史的）。

这一部分在 Figure 1-2 中做了介绍。

4.2 生成式模型

在论文中3.2一节中对判别式模型进行了改进使之成为生成式模型，其实无非就是将原来保存输入序列的buffer换成了生成的buffer，shift操作换成了gen。

5 生成模型

这部分详细描述上面的生成式模型中生成步骤是如何进行的，也就是如何通过神经网络的方式来得到下一个动作和单词。最重要的部分就是 4.1 小节（Syntactic Composition Fuction），这一部分从前面的过程可以看出应该会有两部分，首先生成下一时刻的动作，然后再选择生成的单词，Figure 5描述了动作如何生成，在这里，使用了三个 Stack-LSTM来保存三部分（保存句法树的栈，输出序列和动作历史）信息，那么下一时刻的动作也就是取决于这三个LSTM的状态的结合，然后经过一个神经网络计算得到，也就是第4节一开始的公式部分。
（另外，关于Stack-LSTM可以参考“Transition-Based Dependency Parsing with Stack Long Short-Term Memory”，也是本文作者写的）
有了下一个时刻的动作，接下来要解决的就是单词的生成了，这样的工作一般都会使用一个softmax网络来处理，论文中针对这部分进行了一些优化，使用的是分层softmax的方式，也就是使用了两步softmax，首先得到种类，然后在从种类中得到最大概率的单词，用这种方式降低复杂度。