CS224N学习笔记（六）—— 句法分析

2018-11-14 本文已影响2人 DataArk

写在前面的话：CS224N的第四课和第五课分别是word窗口分类、神经网络和反向传播的知识，但是第四课前半部分内容其实蛮乱的，我个人准备后面在这部分的更新换成对传统的一些机器算法在NLP上的应用上的学习。后面的神经网络和反向早就学过了，所以也就跳过了，后面总结神经网络的时候一起总结。

一、语言学的两种观点

如何描述语法，有两种主流观点，其中一种是短语结构文法，也就是上下文无关文法，英文术语是：Constituency = phrase structure grammar = context-free grammars (CFGs)：

另一种是依存结构，用单词之间的依存关系来表达语法。如果一个单词修饰另一个单词，则称该单词依赖于另一个单词：

这部分和歧义的内容具体可以看之前的笔记：python自然语言处理学习笔记(八)

二、依存句法分析

目前的句法分析已经从句法结构分析转向依存句法分析，一是因为通用数据集Treebank（Universal Dependencies treebanks）的发展，虽然该数据集的标注较为复杂，但是其标注结果可以用作多种任务（命名体识别或词性标注）且作为不同任务的评估数据，因而得到越来越多的应用；二是句法结构分析的语法集是由固定的语法集组成，较为固定和呆板；三是依存句法分析树标注简单且parser准确率高。

依存语法的结构没有非终结点，词与词之间直接发生依存关系，构成一个依存对，其中一个是核心词，也叫支配词，另一个叫修饰词，也叫从属词。

依存关系用一个有向弧表示，叫做依存弧。依存弧的方向为由从属词指向支配词。

依存句法通过分析语言单位内成分之间的依存关系解释其句法结构，主张句子中核心动词是支配其他成分的中心成分。而它本身却不受其他任何成分的支配，所有受支配成分都以某种关系从属于支配者。

五个条件：

一个句子中只有一个成分是独立的
句子的其他成分都从属于某一成分
任何一个成分都不能依存于两个或两个以上的成分
如果成分A直接从属成分B，而成分C在句子中位于A和B之间，那么，成分C或者从属于A，或者从属于B，或者从属于A和B之间的某一成分
中心成分左右两边的其他成分相互不发生关系

数据驱动的依存句法分析方法主要可以分为两种，一种是基于图的方法（Graph Based），一种是基于转移（Transition Based）的方法。

基于图的方法的句法分析算法主要有自顶向下（Top Down），自底向上（Bottom Up），最大生成树（Spanning Tree）的方法

基于转移的依存句法分析算法主要有基于栈（Stack Based）的和基于列表（List Based）的。其中基于栈的又分为arc-standard算法和arc-eager算法。当然除了这些方法外还有一些其他的方法，例如将两种主要方法进行融合的

目前主流的算法是基于转换的依存句法分析，基于转移的方法将依存树的构成过程建模为一个动作序列，将依存分析问题转化为寻找最优动作序列的问题，下面介绍下arc-standard算法，之后的神经网络就是按这个算法的套路来的。

arc-standard算法

一次分析任务C = (s, b, A)由一个Stack栈，一个buffer缓冲区，一系列依存弧A构成。初始化s里面只包含一个root元素即根元素，s1代表栈顶元素，s2表示栈顶第二个元素。b是一个队列，里面包含了要解析的一句话的序列，A为空。

一条依存弧有两个信息：动作类型+依存关系名称l。l视依存句法语料库中使用了哪些依存关系label而定，在arc-standard系统中，一共有如下三种动作：

LEFT-ARC(l)：添加一条s1 -> s2的依存边，名称为l，并且将s2从栈中删除
RIGHT-ARC(l)：添加一条s2 -> s1的依存边，名称为l，并且将s1从栈中删除
SHIFT：将b1出队，压入栈，亦即不建立依存关系，只转移句法分析的焦点，即新的左焦点词是原来的右焦点词，依此类推

举个例子：

如图所示，初始化时Buffer里面有一句话： He has good control 。首先执行SHIFT变换，再执行SHIFT变换，这时栈顶前两个词汇构成了依存关系，He依存于has，同时依存关系是nsubj即名词性主语，这时将从属词He从栈中移除，在A中添加依存弧。然后继续执行SHIFT变换，如此往复。最后当Buffer为空和stack只有ROOT时结束。这时的A就包含了对应一句话的依存关系。

那么模型接下来的工作就是寻找一个分类器，当给定一个Configuration (当前的Stack，Buffer，依存弧）时预测下一步transition的类别。

三、神经网络的依存句法分析器

虽然神经网络依存句法分析器的性能比基于搜索的解析器略差，但是它的计算效率非常高，因为传统方法会花大量的时间在拼装查询特征。

如上面提到的，cs224n里的神经网络的依存句法分析器是按照arc-standard算法改进而来，其实具体就是原来一个Configuration的东西本来需要做跟多特征工程来得到特征，现在只要直接转化成词向量输入到神经网络里就好，模型结构如下：

模型包括输入层，隐含层和softmax层。隐含层的激活函数比较特殊，使用cube激活函数也就是取3次方。

首先模型使用了 word embeddings，将one-hot编码转为词向量，不仅word，对应单词的词性和依存关系标签也被映射为向量，同样有自己的embeddings矩阵。根据论文中分别选择18、18、12个元素作为 $x^w，x^t，x^l$ 的值。

$x^w$ 的组成：

栈和缓冲区的前3个单词：s1, s2, s3, b1, b2, b3
堆栈顶部两个单词的第一个和第二个最左/最右边的子项，也就是依赖于该单词的单词，如果没有就是NULL：lc1(si), rc1(si), lc2(si), rc2(si), i = 1, 2
堆栈顶部两个单词的最左边或最左边节点的最左边或最左边节点（孩子的孩子）lc1(lc1(si)), rc1(rc1(si)), i = 1, 2

$x^t$ ：选择 $x^w$ 中18个词的对应词性作为输入值