斯坦福CS224n-lecture06- 依存分析

句法分析是自然语言处理中的关键底层技术之一，其基本任务是确定句子的句法结构或者句子中词汇之间的依存关系。

句法分析分为句法结构分析（syntactic structure parsing）和依存关系分析(dependency parsing)。以获取整个句子的句法结构或者完全短语结构为目的的句法分析，被称为成分结构分析（constituent structure parsing）或者短语结构分析（phrase structure parsing）；另外一种是以获取局部成分为目的的句法分析，被称为依存分析（dependency parsing），本节中主要介绍后者。

本节中还介绍了一种基于神经网络句法分析器，并解释了优点在哪里，在assignment2中需要完成这样一个分析器。

一、语言学的两种观点

目前有两种主流观点：一是短语结构语法（Constituency），用某种规则分解句子为短语和单词、分解短语为更短的短语或单词。另一种就是此次的主要内容，依存结构，用单词之间的依存关系来表示语法，这也是高中时语文和英语中学的语法。如果一个单词修饰另一个单词，则称该单词依赖于另一个单词。

二、依存分析

用依存句法可以做的是，通过找到句子当中每一个词所依赖的部分，来描述句子结构，如果一个词修饰另一个词，那么它就依赖那个词。例如 barking dog 中的 barking 依赖 dog，因为 barking 修饰 dog，large barking dog 中 large 也修饰 dog 那么large 依赖 dog ，dog by the door 中 by the door 也依赖 dog ，我们就可以在词之间添加依存关系。通过箭头来表示它们之间的依存关系。

而在语义含糊的句子，我们就可以分析句子的依存关系，消除歧义，比如?这个例子：

这个句子有两种可能性，主题词是study ，就是科学家在研究，这是关于study的一个论证，科学家是主语，whales被研究，也是study的一个论证，不同的是如何看待 from space ，到底是修饰 study 还是修饰 whales 。这篇文章讲的是科学家可以使用卫星来追踪鲸鱼的行动。所以 from space 是用来修饰 study 的，第一个是正确的。句子的语义模糊性可以认为是，以依存结构来看是什么修饰什么的问题。

依附歧义

很难确定如何把一个短语（介词短语、状语短语、分词短语、不定式）依附到其他成分上去

看?的例子，董事会每月例会上通过了多伦多皇家信托以每股27美元的收购。句子有主语动词宾语，方括号里都是介词短语，那么这些介词短语都修饰什么呢？ by royal trustco ltd. 修饰 acquisition, of toronto 修饰的是公司 royal trustco ltd ,也是修饰的是紧靠其前面的部分，而 $27 a share 修饰的是 acquisition，at its monthly meeting 修饰 approved ，修饰的是通过的时间，跳过前面的部分。以最后一个节次短语为基准，这个句子的歧义可能性个数仍然可以是通过一个指数函数得出，所有这些序列的个数称为catalan数，这个在理论计算机科学中，cs228课程

每个括号中都是一个短语，它们依附的对象各不相同。对于n个短语来讲，组成的树形结构有Cn=(2n)! / (n+1)!n! 。这是Catalan数，指数级增长，常用于树形结构的计数问题。

标注数据集

完整的语言学以树库的形式标注数据，将句子的句法结构描述为依存关系图，1990年就开始，来建立这种标注型树库。从机器学习角度来讲，用标注好的数据，可以使用分类器训练模型然后得到好的结果。在机器学习领域，依存树可以合理解释句子结构，建立一个可见的，有标注的依存树，可以得到好的结果。

依存树库的优势:

可以被重复使用，在依存树的基础上，在自然语言处理中有很多的应用，语音标记和解析等。

人们书写的规则不同，树库数据覆盖面广，是一个完整语法的句子，可以做为量化语言学的分析。

在概率和机器学习上，不仅能给出所有可能性及其各自的频率，也能给出不同可能性同时发生的概率，所有重要的概率分布信息。

可以用来评估你构建的任何系统，因为这给了标准的数据，可以用这些数据来评估我们建立的各种工具的好坏。

什么是依存语法和依存机构呢？

bills on ports and immigration were submitted by Senator Brownback, Republican of Kansas.

怎么判断哪个词依赖哪个词，依存表示词之间的关系，信息来源：

• 双单词关联：比如issues→the
• 依存距离：依存词和中心词的距离，大部分时候是相邻的两个词
• 中间元素：一般依存关系之间不太可能会出现动词或者标点
• 中心词的价：一般，中心词的左边/右边有多少个依存。

怎么做依存分析：把句子每个词都提取出来，判断这些词的或者root的依赖词是什么，根据约束关系，就能生成依存树。

约束条件：

1、ROOT只能被一个词依赖。

2、无环 （每个连接弧是单向的）

投射性的(projective)，投影依存树，把它投射到一个平面上，然后得到一个嵌套关系，其中箭头没有交叉的部分。

非投射性（non-projective），非嵌套关系，箭头有交叉。

依存分析方法：

这里介绍的是判别句法分析，考虑每个词的依赖项时有点贪心，希望有一个机器学习的分类方法。

基于转移的依存句法分析

基于转移的依存句法分析法使用一系列由初始到终止的状态（State或Configuration）表示句法分析的过程 ，一个状态由栈（Stack）、缓存（Buffer）以及部分已分析好的依存弧构成，其中栈用于存储已经过分析的词，缓存表示待分析的词。

初始状态下，栈中仅含有一个根节点（Root），缓存中存储句子中全部的词。一个状态经过一个转移动作（Action）变为一个新的状态，转移动作共有移进（Shift）、左归约（Left-Reduce）、右归约（Right-Reduce）三种。其中移进动作将缓存中第一个词压入栈中；左规约在栈顶的两个词之间产生一条左指向依存弧，同时将栈顶第二个词下栈；右规约在栈顶的两个词之间产生一条右指向依存弧，同时将栈顶词下栈。

可证明，经过一系列转移动作，最终能够达到终止状态，即栈中仅含有一个根节点，缓存为空，此时恰好构成一颗完整的依存树，并完成对一个句子的依存句法分析过程。