依存结构与依存分析笔记 (CS224N-3)

依存结构

与编译器中的解析树类似，NLP中的解析树是用于分析句子的句法结构。使用的结构主要有两种类型——短语结构和依存结构。短语结构文法使用短语结构语法将词组织成嵌套成分。后面的内容会展开对它做更详细的说明。我们现在关注依存语法。

句子的依存结构展示了单词依赖于另外一个单词 (修饰或者是参数)。词与词之间的二元非对称关系称为依存关系，描述为从head (被修饰的主题) 用箭头指向dependent (修饰语)。一般这些依存关系形成树结构，他们通常用语法关系的名称 (主体，介词宾语，同位语等)。

CFG：Context-Free Grammers（上下文无关语法）

依存语法

(1)依存语法是给定一个输入句子S，分析句子的句法依存结构的任务。依存句法的输出是一棵依存语法树，其中输入句子的单词是通过依存关系的方式连接。

正式一点定义，依存语法问题就是创建一个输入句子的单词 \(S=w_0w_1\dots w_n\) (其中\(w_0\)是 ROOT) 到它的依存语法树的映射图G。最近几年提出了很多以依存句法为基础的的变体，包括基于神经网络的方法，我们将会在后面介绍。

我们通常会添加一个假ROOT，这样每个单词都恰好依赖于一个其他节点

(2)依存语法中的子问题

确切地说，在依存语法中有两个子问题：
①学习：给定用依赖语法图标注的句子的训练集D，创建一个可以用于解析新句子的解析模型M
②分析：给定分析模型M和句子S，根据M得到S的最优依存语法图

「学习」问题是创建一个可以根据转移历史来预测状态机中的下一个转换的模型。

「分析」问题是使用在学习问题中得到的模型对输入句子构建一个最优的转移序列。

依存分析

(1)通过为每个单词选择它所依赖的其他单词（包括ROOT）来分析句子，这通常有一些限制：
①只有一个单词依赖于ROOT
②不希望循环A→ B、 B→ A
③这使依赖关系成为一棵树
④箭头是否可以交叉（非投影）

投射解析：当单词按线性顺序排列时，不存在交叉依赖弧

(2)依存分析方法

①依存分析的方法有：Dynamic programming、Graph algorithms、Constraint Satisafaction、Transition-based parsing

②Transition-based parsing：Transition-based 依存语法依赖于定义可能转换的状态机，以创建从输入句到依存句法树的映射。

Greedy Deterministic Transition-Based Parsing

(1)状态：对任意句子 \(S=w_0w_1\dots w_n\) ，一个状态可以描述为一个三元组 \(c=(\sigma,\beta,A)\)

(σ是S中单词的堆，β是S中单词的缓冲区， A是依存弧集合，对于一组形式为 \((w_i,r,w_j)\) 的依存弧，其中r是二者的依存关系)

(2)转移：在状态之间有三种不同类型的转移

①SHIFT：移除在缓冲区的第一个单词，然后将其放在堆的顶部 (前提条件：缓冲区不能为空)
②Left-Arc：向依存弧集合A中加入一个依存弧 \((w_i,r,w_j)\) ，其中\(w_i\)是堆顶的第二个单词，\(w_j\)是堆顶部的单词，从堆中移除\(w_i\)（前提条件：堆必须包含两个单词以及\(w_i\)不是 ROOT ）
③Right-Arc：向依存弧集合A中加入一个依存弧 \((w_i,r,w_j)\) ，其中\(w_i\)是堆顶的第二个单词，\(w_j\)是堆顶部的单词，从堆中移除\(w_j\)（前提条件：堆必须包含两个单词）

每个动作都由判别分类器（例如softmax分类器）对每个合法动作进行预测

神经依存解析器

定义神经网络的输入是灵活的。对给定句子 \(S\)的特征包含一些子集：

① \(S_{word}\) ：在堆σ的顶部和缓冲区β的S中一些单词的词向量 (和它们的依存)
② \(S_{tag}\) ：在S中一些单词的词性标注 ( POS )。词性标注是由一个离散集合组成： \(P={NN,NNP,NNS,DT,JJ,\dots}\)
③ \(S_{label}\) ：在S中一些单词的依存标签。依存标签是由一个依存关系的离散集合组成： \(L={amod,tmod,nsubj,csubj,dobj}\)

对每种特征类型，我们都有一个对应的将特征的 one-hot 编码映射到一个d维的稠密的向量表示的嵌入矩阵。

来源链接：https://www.cnblogs.com/mianmaner/p/18760039