CS224N学习笔记（五）依存句法分析_transition-based dependency parsing (arc standard)

Lecture 5: Dependency Parsing

对于句法结构分析，主要有两种方式：Constituency Parsing（成分句法分析）与Dependency Parsing（依存句法分析）。本节课的句法分析以英文为例，其他语言也有类似的结构。

Syntactic Structure: Consistency and Dependency

Constituency Parsing

Constituency Parsing称为成分句法分析，主要思想是通过短语语法来不断的将词语整理成嵌套的组成成分，又被称为context-free grammers，简写为CFG。

成分句法分析的主要步骤为：

• 先对每个词做词性分析part of speech（POS）
• 然后再将其组成短语
• 再将短语不断递归构成更大的短语

举例来说，如图所示，进行如下处理：

首先进行词性判别（POS）

• Det 指的是 Determiner，在语言学中的称为限定词
• N 指的是Noun，即名词
• Adj指的是Adjectives，即形容词
• P指的是Prepositions，即介词

the是限定词，用Det(Determiner)表示，cuddly是形容词，用Adj(Adjective)代表，cat和door是名词，用N(Noun)表示, by是介词，用P(Preposition)表示。

然后依据语法关系对这些词语进行组合

• 由Det、Adj、N组合形成了一个名词短语NP（Noun Phrase，在语言学中的含义为名词短语）
• 由P、NP组合形成了一个介词短语PP（PP 指的是Prepositional Phrase，在语言学中的含义为介词短语）

the cuddly cat构成名词短语NP，这里由Det(the)+Adj(cuddly)+N(cat)构成，by the door构成介词短语PP，这里由P(by)+NP(the door)构成。

之后可以继续递归的组合下去

• 比如由NP和PP又组成了新的NP

整个短语the cuddly cat by the door 是NP，由NP（the cuddly cat）+ PP(by the door)构成。

Dependency Structure

Dependency Parsing不是使用各种类型的短语，而是直接通过单词与其他的单词关系表示句子的结构，显示哪些单词依赖于(修饰或是其参数)哪些其他单词。

如图所示，

• look 是整个句子的根源（也即root依赖于look），
• look 依赖于 crate （或者说 crate 是 look 的依赖）
• in, the, large 都是 crate 的依赖
• in the kitchen 是 crate的修饰
• in, the 都是 kitchen 的依赖
• by the door 是 crate 的依赖
  

那么我们为什么需要句子结构呢？

• 为了能够正确地解释语言，我们需要理解句子结构
• 人类通过将单词组合成更大的单元来传达复杂的意思，从而交流复杂的思想
• 我们需要知道什么与什么相关联
• 除非我们知道哪些词是其他词的参数或修饰词，否则我们无法弄清楚句子是什么意思

Dependency Grammar and Treebanks

Dependency Structure展示了词语之前的依赖关系,通常用箭头表示其依存关系，有时也会在箭头上标出其具体的语法关系，如是主语还是宾语关系等。

Dependency Structure有两种表现形式，一种是直接在句子上标出依存关系箭头及语法关系，如：

另一种是将其做成树状机构（Dependency Tree Graph）

• 箭头通常标记(type)为语法关系的名称(主题、介词对象、apposition等)。

• 依赖关系标签的系统，例如 universal dependency 通用依赖

• 箭头连接头部(head)(调速器,上级,regent)和一个依赖(修饰词,下级,下属)

  • A → 依赖于 A 的事情

• 通常,依赖关系形成一棵树(单头 无环 连接图)
  

• 人们对箭头指向的方式不一致：有些人把箭头朝一个方向画；有人是反过来的

  • Tesnière 从头开始指向依赖，本课使用此种方式

• 通常添加一个伪根（root）指向整个句子的头部，这样每个单词都精确地依赖于另一个节点

Dependency Parsing可以看做是给定输入句子 [公式] （其中 [公式] 常常是fake ROOT，使得句子中每一个词都依赖于另一个节点）构建对应的Dependency Tree Graph的任务。

构建这个树一个有效的方法是Transition-based Dependency Parsing。

Transition-based dependency parsing

• 贪婪判别依赖解析器 greedy discriminative dependency parser 的一种简单形式
• 解析器执行一系列自底向上的操作大致类似于shift-reduce解析器中的“shift”或“reduce”，但“reduce”操作专门用于创建头在左或右的依赖项
• 解析器如下：
  • 栈 σ 以 ROOT 符号开始，由若干 $w_i$ 组成。
  • 缓存 β 以输入序列开始，由若干 $w_i$ 组成。
  • 一个依存弧的集合 A ，一开始为空。
  • 每条边的形式是 ($w_i$, r, $w_j$) ，其中 r 描述了节点的依存关系一组操作。
  • 最终目标是 σ=[ROOT],β=ϕ ，A 包含了所有的依存弧。

state之间的transition有三类：

• SHIFT：将buffer中的第一个词移出并放到stack上。
• LEFT-ARC：将$(w_i,r,w_j)$加入边的集合 A ，其中$w_i$是stack上的次顶层的词，$w_j$是stack上的最顶层的词。
• RIGHT-ARC:将$(w_i,r,w_j)$加入边的集合 A ，其中$w_i$是stack上的次顶层的词，$w_j$是stack上的最顶层的词。

我们不断的进行上述三类操作，直到从初始态达到最终态。

在每个状态下如何选择哪种操作呢？当我们考虑到LEFT-ARC与RIGHT-ARC各有|R|（|R|为r 的类的个数）种类，我们可以将其看做是class数为 2|R|+1 的分类问题，可以用SVM等传统机器学习方法解决。

对于这个任务的评估，我们有metric，一个是LAS（labeled attachment score）即只有arc的箭头方向以及语法关系均正确时才算正确，以及UAS（unlabeled attachment score）即只要arc的箭头方向正确即可。

示例如下：

图中，在评价UAS时可以看到，只有第三行的5->3预测错误为4->3，所以UAS=80%；而在评价LAS时，由于第3行箭头预测错误、第4,5行标签预测错误。所以LAS=40%。

Neural dependency parsing

传统的Transition-based Dependency Parsing对feature engineering要求较高，我们可以用神经网络来减少human labor。

• 将每个单词表示为一个d维稠密向量（如词向量）
• 相似的单词应该有相近的向量
• part-of-speech tags 词性标签(POS)和 dependency labels 依赖标签也表示为d维向量
• 较小的离散集也表现出许多语义上的相似性。
• NNS(复数名词)应该接近NN(单数名词)
• num(数值修饰语)应该接近amod(形容词修饰语)。

对于Neural Dependency Parser，其输入特征通常包含三种：

• stack和buffer中的单词及其dependent word。
• 单词的Part-of-Speech tag。
• 描述语法关系的arc label。

我们根据堆栈/缓冲区位置提取一组token：

我们将其转换为embedding vector并将它们联结起来作为输入层，再经过若干非线性的隐藏层，最后加入softmax layer得到每个class的概率。

利用这样简单的前馈神经网络，可以减少feature engineering并提高准确度。

参考

1. CS224N笔记(五)：Dependency Parsing, link
2. 05 Linguistic Structure Dependency Parsing, link