关注公众号【算法码上来】，每日算法干货马上就来！
论文地址
PaLM: A Hybrid Parser and Language Model
介绍
本文介绍了如何将一个句法分析器融入到神经网络语言模型中，这样在利用了句法信息增强语言模型效果的同时，还可以去掉句法上的监督信号，用来无监督地生成句法树。
其实将句法信息加入到语言模型中地思想之前就有了，比如PRPN（Shen et al.）和ON-LSTM（Shen et al.）。而本文提出了一种新的融入句法信息的方法，相比于之前的两个模型，主要有如下优点：
- 更加符合直觉、更加轻巧，不需要很复杂的解码算法。
- 在LSTM中加入的attention信息可以用句法信息来监督，可解释性更强，可以和语言模型联合训练。
- 如果没有句法信息监督也不要紧，模型可以无监督预测出句法树。
模型
span attention
模型中的attention是怎么做的呢？在 $t$ 时刻，模型关注以 $t - 1$ 结尾的所有 span 。但是为了减少运算量，这里只考虑最短的 $m$ 个 span ，也就是 $\{[i, t - 1]\}_{i = t - m}^{t - 1}$ 。
首先采用普通的 RNN 来获得 $t$ 时刻的隐层表示 $h_t$，然后采用双向 WFSA-RRNN （Peng et al.）进一步得到表示， WFSA-RRNN 的单元更新公式如下：
$$
\begin{aligned}
f_t &= \sigma(W_f h_t) \\
u_t &= (1 - f_t) \odot \tanh(W_u h_t) \\
c_t &= f_t \odot c_{t-1} + u_t
\end{aligned}
$$
然后 span $[i, j]$ 的表示 $c_{i, j}$ 可以计算为：
$$
c_{i, j} = c_j - c_{i-1}\odot_{k=i}^{j}f_k
$$
这个式子其实是从下面这个式子推算而来的：
$$
c_{i, j} = u_j + \sum_{k=i}^{j-1}{u_k \odot_{l=k+1}^{j}f_l}
$$
具体计算过程就不在这里看了，详见论文附录，其实就是用的 WSFA-RRNN 的单元更新公式化简得到的。
注意上面向量都省略了前向箭头！
下面就是计算所有 span 表示的算法伪代码：
可以看出复杂度还是挺高的，但是可以用 GPU 并行加速。
然后就是计算attention了。
首先令 $g([i, j])$ 为向量 $c_{ij}$前后向拼接得到，表示 span [i, j] 的最终向量表示。
那么在 $t + 1$ 时刻，上下文向量 $a_{t + 1}$ 可以表示为：
$$
\begin{aligned}
a_{t+1} &= \sum_{i=0}^{m-1}{w_{t,i}g([t-i,t])} \\
w_{t,i} &= \frac{\exp{s_{t,i}}}{\sum_{j=0}^{m-1}{\exp{s_{t,j}}}}
\end{aligned}
$$
其中 $s_{t, i}$ 定义为：
$$
s_{t,i} = \text{MLP}(h_{t+1};g([t-i, t]))
$$
最后拼接 $h_{t+1}$ 和 $a_{t+1}$ 作为最后的隐层输出。
总结一下，计算步骤是这样的：
- 首先用一个标准的RNN计算得到隐层表示 $h_t$ 。
- 然后将 $h_t$ 输入到一层的双向 WSFA-RRNN 中，得到表示 $c_t$ ，并且用上述算法进一步得到 span 的表示。
- 最后对所有以 $t$ 结尾的 span 表示加权求和，得到下一时刻的隐层表示，并预测下一个单词。
生成句法树
这就和以往自顶向下解码句法树的算法一样了，对于 span $[i, j]$，寻找使得右儿子得分最高的 split $k$ 即可：
$$
k = \text{argmax}_{k \in \{0,\ldots,m-1\}}s_{j,k}
$$
而如果是有监督的话，对于每个位置 $t$ ，都会预测一个 attention $w_t$，并且有一个 gold 的左边界 $y_t$。
注意这里的 $y_t$ 不一定是 one-hot 的，因为在一棵句法树中，一个右端点可能对应着很多不同的左端点。
最终的损失函数为：
$$
\mathcal{L} = \mathcal{L}_{\text{LM}}+\frac{\lambda}{N}\sum_{t=1}^{N}{\mathcal{H}(y_t, w_t)}
$$
而这里的句法树监督其实可以用现成的 parser ，或者直接用左右二叉树之类的就行了，主要目的是为了提升语言模型性能。
下图就是一个简单的例子：
实验
这是一篇短文，所以实验就很简单了。
首先是PTB上的语言模型困惑度：
然后是WikiText2上的语言模型困惑度：
两个实验都可以看出加了句法树监督的语言模型效果更好，而无监督隐式的语言模型效果也还可以。注意这里的AWD-LSTM指的是之前提出的一种LSTM变体（Merity et al.）。看得出来这些模型参数量其实没多大差别，而如果句法信息乱加监督（比如用右二叉树），效果反而会变差。
接着是无监督句法分析的效果：
可以发现效果还是很差的，只比随机的二叉树好了那么一丢丢。比之前的 PRPN 差许多，和 DIROA 相比就更不用谈了（Drozdov et al.）。这也说明了对语言模型有用的句法信息可能并不符合 PTB 句法树结构。
最后还分析了左结合多还是右结合多：
可以看出，基本全部都是右结合，也就是attention基本都聚焦在了 span 的最左边的单词。具体原因作者也不知道，留着未来探索。
后记
其实这篇短文和我 ACL 的工作挺像的，着实让我惊了一身冷汗（希望 ACL 能中，加油！）。
不过这篇还是有些小瑕疵的，比如最大考虑长度 $m$ ，这个值在语言模型的训练时用到了，但是分析无监督句法树的时候就去掉限制了，其实会影响无监督句法分析性能的。不过也不要紧，毕竟本文任务不是做句法分析。
再比如算 attention 是要对所有分数做归一化的，但是句法分析又采用了没有归一化的得分来解码，原因是因为一个右边界对应着多个左边界，所以不能用 attention 解码。但其实这个 attention 在做有监督句法信息的时候， gold 的就不是归一化的，也就是非 one-hot 的。总之这里做的挺粗糙的，也没有设计的很优雅。
