放牧代码和思想
专注自然语言处理、机器学习算法
    This thing called love. Know I would've. Thrown it all away. Wouldn't hesitate.

依存句法分析在深度学习中的应用

目录

hankcs.com 2019-10-13 at 5.02.45 PM.png hankcs.com 2019-10-13 at 12.22.39 PM.pnghankcs.com 2019-10-13 at 1.15.50 PM.pnghankcs.com 2019-10-13 at 1.50.26 PM.pnghankcs.com 2019-10-13 at 1.58.19 PM.pnghankcs.com 2019-10-13 at 4.19.14 PM.pnghankcs.com 2019-10-13 at 2.10.30 PM.pnghankcs.com 2019-10-13 at 2.32.43 PM.pnghankcs.com 2019-10-13 at 2.26.48 PM.png句法分析是一项核心的NLP任务,目标是获取句子的主谓宾等句法结构。下级应用时,给定依存句法树,传统时代利用规则提取句法树的特征;在深度学习时代,如何提取树的向量表示?本文调研了7种常用模型,涵盖Tree RNN、DCNN和GCN等。

Tree RNN

最著名的方法当属TreeRNN(Tai et al. (2015)),它有Child-Sum以及N-ary两种变形。

Child-Sum

当子节点数量不定且无序时,比如依存句法分析树,适用这种模型。如下图底部所示:

hankcs.com 2019-10-13 at 12.22.39 PM.png

将子节点应用常规RNN更新函数后得到的隐藏状态\(h_k\)求和,作为父节点的隐藏状态\(h_j\),也就是: \[
{\tilde h_j} = \sum_{k \in C\left( j \right)} {{h_k}}
\]

N-ary

当子节点最多为\(N\)时,比如binarized后的短语结构树,可使用N-ary模型。如下图所示:

hankcs.com 2019-10-13 at 1.15.50 PM.png

子节点的隐藏状态\(h_2\)\(h_3\)并不直接求和作为父节点的\(h_j\),而是在每个门的更新表达式中求和子节点的对应变量\(h_k\)\(c_k\)。也就是: \[
\begin{align}
i_j &=\sigma \left( W^{(i)} x_j + \sum_{\ell=1}^N U^{(i)}_\ell h_{j\ell} + b^{(i)} \right), \label{eq:nary-treelstm-first}\\
f_{jk} &= \sigma\left( W^{(f)} x_j + \sum_{\ell=1}^N U^{(f)}_{k\ell} h_{j\ell} + b^{(f)} \right), \label{eq:nary-treelstm-f}\\
o_j &= \sigma \left( W^{(o)} x_j + \sum_{\ell=1}^N U^{(o)}_\ell h_{j\ell}  + b^{(o)} \right), \\
u_j &= \tanh\left( W^{(u)} x_j + \sum_{\ell=1}^N U^{(u)}_\ell h_{j\ell}  + b^{(u)} \right), \\
c_j &= i_j \odot u_j + \sum_{\ell=1}^N f_{j\ell} \odot c_{j\ell}, \\
h_j &= o_j \odot \tanh(c_j), \label{eq:nary-treelstm-last}
\end{align}
\]

当没有子节点时,这种机制退化为标准的链式RNN。

试验

在SST上的结果显示,短语结构树提高了2.5个点。

hankcs.com 2019-10-13 at 1.25.34 PM.png

DCNNs

线性拼接

一般NLP中的CNN在线性拼接的ngram形式的序列向量上进行一维卷积:

\begin{equation}\label{eq:seq_con}
   \widetilde{ \bf x}_{i,j} =    {\bf x}_i \oplus   {\bf x}_{i+1}\oplus \cdots \oplus  {\bf x}_{i+j}
\end{equation}

DCNNs (Dependency-based CNN) (Ma et al. (2015))做了2种简单的改进,即基于路径和基于兄弟节点,如下图所示:

hankcs.com 2019-10-13 at 1.50.26 PM.png

基于路径

将ngram拼接方式改为由叶节点到根节点的路径拼接: \[
\begin{equation}\label{eq:tree_con}
    {\bf x}_{i,k} =   {\bf x}_{i} \oplus   {\bf x}_{p(i)}\oplus \cdots \oplus  {\bf x}_{p^{k-1}(i)}
\end{equation}
\]
其中,\(p\)是取父节点操作,\(p^k(i)\) 返回单词\(i\)的第\(k\)个祖先,约定根节点的\(k\)值最大,由如下公式递归定义: \[
\begin{equation}\label{eq:parent_def}
p^k(i)= \begin{cases}
p(p^{k-1}(i)) & \text{if} \quad k>0 \\
i             & \text{if} \quad k=0  \\
\end{cases}
\end{equation}
\]

基于兄弟

也就是将兄弟节点拼接起来做卷积,有时候也将父节点拼接起来。如上图右侧所示。

混合模型

线性、祖先、兄弟各有各的好处,一个综合的方法是将它们产生的feature map都拼接起来,作为最终的句子表示。 \[
\hat{\bf c} = [\underbrace{\hat{c}_a^{(1)}, …, \hat{c}_a^{(N_a)}}_\text{ancestors};
              \underbrace{\hat{c}_s^{(1)}, …, \hat{c}_s^{(N_s)}}_\text{siblings};
              \underbrace{\hat{c}^{(1)}, …, \hat{c}^{(N)}}_\text{sequential}]
\]

试验

在SST上相较于SOTA CNN方法取得了\(+1.0\)的进步。

hankcs.com 2019-10-13 at 1.56.53 PM.png

在TREC数据集上,作者还列举了一些CNN判断错误的而DCNN判断正确的问句。

hankcs.com 2019-10-13 at 1.58.19 PM.png

最短路径

一般的用法是将依存句法树中主体S和客体O之间的最短路径编码。

SDP-LSTM

比如SDP-LSTM(Xu et al. (2015)),将最短路径上的单词按顺序用LSTM过一遍:

hankcs.com 2019-10-13 at 2.26.48 PM.png

BRCNN

另一个经典的BRCNN(Cai et al. (2016)),也是SemEval 2010 Task 8上非端到端的SOTA,则更加简单粗暴,那就是将用BiLSTM将最短路径正反过两遍,上层用CNN提取片段结构。如下图所示:

hankcs.com 2019-10-13 at 2.32.43 PM.png

注意这里的BiLSTM与常规的不同,它有一个方向是在依存关系标签上运行的。

DepNN

文章开头两作分别是RNN和CNN建模树形结构的早期代表作,ADP和DepNN(Liu et al. (2015))则进一步探索了如何利用依存信息进行关系抽取。

ADP

但作者认为最短路径上的节点的子树也很有用,应该合并起来考虑,也就是所谓的ADP(augmented dependency path),如下图所示。

hankcs.com 2019-10-13 at 2.10.30 PM.png

这两个句子的SPO最短路径(加粗)是类似的,然而子树是不一样的,这便于模型发现S与O的不同关系。

DepNN

Dependency-Based Neural Networks (DepNN)是这种思路的实现,它利用RNN(空间递归神经网络)提取子树特征,利用CNN提取最短路径的特征,得到最终的ADP表示。如下图所示:

hankcs.com 2019-10-13 at 2.18.29 PM.png

试验

在SemEval-2010上取得了\(+0.6\)的进步。

hankcs.com 2019-10-13 at 2.19.31 PM.png

值得一提的是,重度特征工程的SVM也能拿到\(82.2\)的分数,只比DepNN少\(1.4\)

GCN

最短路径一定是最好的吗?有时候,一些很关键的虚词(否定词)不一定在两个实体的最短路径上,比如:

hankcs.com 2019-10-13 at 3.57.05 PM.png

所以作者提出要考虑一些路径之外的词语,所使用的模型就是GCN

Graph Convolutional Networks

GCN是一种编码图数据的网络结构,给定一张\(n\)个节点的有向图,可以将其表示为邻接矩阵\(\bf A\),其中\(A_{ij}=1\)表示存在从\(i\)\(j\)的边。在\(L\)层的GCN中,记第\(l\)层节点\(i\)的输入为\(h_i^{(l-1)}\),输出为\(h_i^{(l)}\)。那么,图卷积操作定义如下: \[
\begin{align}
   h_i^{(l)} = \sigma\big( \sum_{j=1}^n A_{ij} W^{(l)}{h}_j^{(l-1)} + b^{(l)} \big),
   \label{eqn:conv}
\end{align}
\]
 

\(A_{ij}\)只在邻接节点处等于\(1\),所以图卷积实际上是让节点从邻接节点处获取总结性的信息。

依存句法树上的GCN

虽然树是图的子集,但这并不意味可以不动脑筋地将GCN应用于依存句法树。因为每个节点的出度相差巨大,最终导致它们的向量的长度相差巨大。同时,分类器会偏向于注意那些出度大的节点。另外,由于树中节点不连接到自己,所以\(h^{(l-1)}_i\)中的信息不会传递到\(h^{(l)}_i\)

为了解决这两个问题,作者提出先自加一个单位矩阵引入自我连接环,然后再归一化一下。也即是: \[
\begin{align}
   h_i^{(l)} =& \sigma\big( \sum_{j=1}^n \tilde{A}_{ij} W^{(l)}{h}_j^{(l-1)} / d_i + b^{(l)} \big),\label{eqn:gcn_final}
\end{align}
\]
其中,\(\tilde{\bf A}=\bf{A} + {\bf I}\)\(d_i=\sum_{j=1}^n \tilde{A}_{ij}\)\(i\)的出度。GCN在无标签句法树上的架构如下所示:

hankcs.com 2019-10-13 at 4.19.14 PM.png

值得一提的是,作者发现在关系抽取中,将句法树视作无向图效果最好。

Contextualized GCN

上述GCN中的词向量没有上下文信息,另外句法树可能导致误差传播。作者提出了C-GCN,先将词向量过一遍BiLSTM提取一下上下文信息再作为\(\bf h^{(0)}\)输入网络。为了减小误差传播带来的影响,作者提出保留最短路径上每个节点\(K\)条边以内的子树。作者的试验显示\(K=1\)的效果最好,此时Figure 1里面的红色“not”被保留下来了。

试验

hankcs.com 2019-10-13 at 4.36.12 PM.png

在SemEval上的效果比前面介绍的DepNN、SDP-LSTM要好,比BRCNN差一些。奇怪的是作者没有引用BRCNN,猜测可能是用的额外特征不一样之类的原因。

soft pruning

迄今为止所有子树的获取都是基于预定义的规则,或者是保留所有,或者取深度\(K\)Guo et al. (2019) 提出了能够soft pruning的AGGCN。AGGCN利用self-attention机制计算多头attention,attention矩阵的计算方法如下:  \[\begin{equation}
\mathbf{\tilde{A}^{(t)}} = softmax(\frac{Q\mathbf{W}_{i}^{Q} \times (K\mathbf{W}_{i}^{K})^{T}}{\sqrt{d}})V
\end{equation}\]
 其中,\(Q\)\(K\) 都是上一层的表示 \(\mathbf{h}^{(l-1)}\)。用这些\(\mathbf{\tilde{A}}\)代替\(\mathbf{{A}}\)就可实现soft pruning了。这个机制的效果如下所示:

hankcs.com 2019-10-13 at 5.02.45 PM.png

总结

各种网络结构都往树形数据上应用了一番,唯独缺少Transformer。听说Transformer已经能够自行捕捉语法结构信息,不知道能不能将这个提取能力以某种结构改动的方式强化一下,说不定会是篇好paper。

References

Rui Cai, Xiaodong Zhang, and Houfeng Wang. 2016. Bidirectional recurrent convolutional neural network for relation classification. In Proceedings of the 54th annual meeting of the association for computational linguistics (volume 1: Long papers), pages 756–765, Berlin, Germany, August. Association for Computational Linguistics.

Zhijiang Guo, Yan Zhang, and Wei Lu. 2019. Attention guided graph convolutional networks for relation extraction. In Proceedings of the 57th annual meeting of the association for computational linguistics, pages 241–251, Florence, Italy, July. Association for Computational Linguistics.

Yang Liu, Furu Wei, Sujian Li, Heng Ji, Ming Zhou, and Houfeng Wang. 2015. A dependency-based neural network for relation classification. In Proceedings of the 53rd annual meeting of the association for computational linguistics and the 7th international joint conference on natural language processing (volume 2: Short papers), pages 285–290, Beijing, China, July. Association for Computational Linguistics.

Mingbo Ma, Liang Huang, Bowen Zhou, and Bing Xiang. 2015. Dependency-based convolutional neural networks for sentence embedding. In Proceedings of the 53rd annual meeting of the association for computational linguistics and the 7th international joint conference on natural language processing (volume 2: Short papers), pages 174–179, Beijing, China, July. Association for Computational Linguistics.

Kai Sheng Tai, Richard Socher, and Christopher D. Manning. 2015. Improved semantic representations from tree-structured long short-term memory networks. In Proceedings of the 53rd annual meeting of the association for computational linguistics and the 7th international joint conference on natural language processing (volume 1: Long papers), pages 1556–1566, Beijing, China, July. Association for Computational Linguistics.

Yan Xu, Lili Mou, Ge Li, Yunchuan Chen, Hao Peng, and Zhi Jin. 2015. Classifying relations via long short term memory networks along shortest dependency paths. In Proceedings of the 2015 conference on empirical methods in natural language processing, pages 1785–1794, Lisbon, Portugal, September. Association for Computational Linguistics.

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » 依存句法分析在深度学习中的应用

我的作品

HanLP自然语言处理包《自然语言处理入门》