CS224n笔记（三）

发表于 | 分类于 | 阅读数 次
字数统计: 3.6k 字 | 阅读时长 ≈ 13 分钟

Dependency parsing

语言学的两种观点

如何描述语法有两种主流观点：1.短语结构文法(也叫上下文无关文法)，英语术语是：Constituency=phrase structure grammar=context-free grammars(CFG).简单来说，是把词按照结构组成句子。
上下文无关文法可以定义为四元组【T,N,S,R】,其中T表示终结符的集合(即词的集合)，N表示非终结符的集合(即文法标注和词性标记的集合)，S表示充当句法树根节点的特殊非终结符，而R表示文法规则的集合，其中每条文法规则可以表示为Ni-r,这里的r表示由非终结符与终结符组成的一个序列(允许为空)。

Phrase_structure
这种短语语法用固定数量的rule分解句子为短语和单词、分噱短语为更短的短语或单词…..

一个取自WSJ(卫生巾)语料库的短语结构树示例：
Phrase_structure_1
2.另一种是依存结构，用单词之间的依存关系来表达语法。如果一个单词修饰另一个单词，则称该单词依赖于另一个单词。
一个由HanLP输出的依存句法树如下：
Phrase_structure_2

歧义(Ambiguity)

通过句法树可以表达歧义，一个确定的句法树对应句子中的一个确定解读，比如对介词短语依附
Ambiguity_1
from space这个介词短语到底依附谁？不同的答案导致对句子不同的理解。

依附歧义（Attachment ambiguities）

很难确定如何把一个短语（介词短语、状语短语、分词短语、不定式）依附到其他成分上去，是依附他前面的成分么？？实际证明并不是。如下：
Ambiguity_2
每个括号中都是一个短语，他依附的对象各不相同。对于n个短语来讲，组成的树形结构有$C_n=(2n)!/[(n+1)!n!]$这是Catalan数，指数级增长，常用于树形结构的计数问题。

标注集的崛起

虽然上下文无关文法中的语法集很容易写，无非是有限数量的规则，但人工费时费力标注的树库却茁壮成长了起来。
树库示例：
tree_1
人们偏好树库多于规则的原因：

  • 1.树库虽然标注难度高，但每一份劳动都可被复用(可以用于词性标注命名实体识别等任务),然而每个人的编写的规则都不同，因为每个人都对语法规则有不同的理解
  • 2.依存树库使用了真实的覆盖面广的数据，而人们写规则时只是依靠对英语语法的直觉判断
  • 3.可以给出很多概率分布信息
  • 树库还可以用来评估我们构建的系统

依存文法与依存结构

这课用的都是依存句法树，而不是短语结构树。这并不是随机选择，而实由于前者的优势。90年代99%的都是短语结构树，但后来人们发现依存句法树标注简单，准确率高，所以近年基本上就是依存句法树的天下了。

不标注依存弧lable(标签)的依存句法树就是短语结构树的一种：
tree_2
一旦标注上了，两者就不同了：
tree_3
这里箭头的尾部都是head(被修饰的主题)，箭头指向的是dependent(修饰词)。

一些细节

人们画依存句法树的弧的方式不同，这门课是head指向dependent,有些则相反
每个句子都有一个虚根，代表句子之外的开始，这样句子中的每个单词都有自己的依附对象。

句法分析可用的特征

  • 1.双词汇亲和，比如discussion与issues
  • 2.词语间距，因为一般相邻的词语才具有依存关系
  • 3.中间词语，如果中间词语是动词或标点，则两边的词语不太可能有依存
  • 4.词语配价，一个词语最多有几个依赖者

    依存句法分析

    生成一个依存树的几个约束条件：
  • 1.ROOT只能被一个词依赖
  • 无环
    箭头画在单词上方，这里有嵌套结构，还有交叉。出现了交叉就是non-projective的
    tree_4
    是否可以将一个依存句法树还原为句子，答案是否定的。
    文献中的依存句法分析方法有：
  • 1.Dynamic programming:估计是找出以head结尾的字串对应最可能的句法树
  • Graph algorithms:最小生成树
  • Constraint Satisfaction:估计是在某个图上逐步删除不符合要求的边直到成为一棵树
  • “Transition-based parsing” or “deterministic dependency parsing”
    主流方法，基于贪心决策动作拼装句法树

补充基本概念

  • 依存树
    依存树是满足以下约束的有向图
    1.有一个指定的根节点，没有传入它的弧
    2.除了根节点外，每个顶点都有一个传入弧，从根节点到每个顶点有一条唯一的路径
    • 投射性（projective）：
      如果从头部到句子中的每个单词之间都有一条路径，则从头部到依赖方的弧线被称为有投射性的。
      如果组成依赖树的所有弧都是投射性的，则称该依赖树具有投射性。
      如果依赖树可以在没有交叉边的情况下绘制，则依赖树是可投射的

下面介绍两类基本的Dependency Parsing算法

Transition Based Method

transition-based 依存语法依赖于定义可能的转换的状态机，以创建从输入句到依存句法树的映射。学习问题是创建一个可以根据转换历史来预测状态机中的下一个转换的模型。分析问题是使用在学习问题中得到的模型对输入句子构建一个最优的转换序列

arc standard transition system

这个转换系统是一个状态机，它由这些状态之间的状态和转换组成。该模型引发了从一些初始状态到多个终点状态之一的转换序列。
状态： 对任意句子S=$w_0w_1…w_n$,一个状态可以描述为一个三元组c=$(\sigma,β,A)$:

  • 1.来自S的单词$w_i$的堆栈
  • 2.来自S的单词$w_i$的缓冲区β
  • 3.一组形式为$(w_i,r,w_j)$的依存弧，其中$w_i,w_j$是来自S,和r描述依存关系。
    因此，对于任意句子S=$w_0w_1…w_n$,
  • 1.一个形式为$([w_0]_ \sigma,[w_1…w_n]_ β,\varnothing)$的处事状态$c_0$(现在只有ROOT在堆$\sigma$中，没有被选择的单词都在缓冲期β中)

  • 2.一个形式为$(\sigma,[]_ β,A)$的终点状态
    转移:在状态之间有三种不同类型的转移

  • Leftarc
    堆栈顶部的单词与其直接下面的单词之间存在依赖头的关系；从堆栈中移除较低的单词

  • Rightarc
    在堆栈上的第二个单词和顶部的单词之间建立一个依赖头的关系；删除堆栈顶部的单词；
  • Shift
    从输入缓冲区的前面移除单词并将其推到堆栈上。

arc eager transition sysetm

  • Leftarc
    在输入缓冲区前面的单词和堆栈顶部的单词之间声明一个依赖头的关系；弹出堆栈。
  • Rightarc
    在堆栈顶部的单词和输入缓冲区前面的单词之间声明一个依赖头的关系；将输入缓冲区前面的单词移到堆栈上。
  • Shift
    从输入缓冲区的前面移除单词并将其推到堆栈上。
  • Reduce
    弹出堆栈

    基于Greedy的算法框架

    1
    2
    3
    4
    5
    6
    function DependencyParse(words) returns dependency tree
        state <——{[root],[words],[]};  初始化设置
        while state not final
            t <—— ORACLE(state) ; 选择一个变化操作
            state <——APPLY(t,state) ; 应用该操作创造新状态
        return state

ORACLE的学习

上面提到的ORACLE应该是我们学习到的分类器，可以用SVM,多类逻辑回归等。

样例

arc_standard_transition
arc_eager_transition

arc standard vs. arc eager

  • 1.arc standard中的transition操作只会给stack顶部的元素添加依赖关系，而且一旦添加了head-dependent的依赖关系之后，dependent元素会从stack中移除，从而后续不能再添加与该元素有关的依存关系。
  • 2.所以在arc standard的体系中，一个词在它的所有dependent被发现之前，是不可以被指定head的。这种限制会导致由 parse tree 构造训练样本的时候需要多做一些考虑。另外，如果一个词越是要等很长时间才能指定head，那么就越有可能会出错。
  • 3.arc-eager 是 arc-standard 的一个替代，它对LEFTARC，RIGHTARC操作进行了些许修改，同时增加新的REDUCE操作。这种体系可以为一个词尽早的指定head。

    Transition Based method 的优缺点

    1. efficiency，基本上只要扫一遍sentence，整个过程会产生 2*len(sentence) 个 transitions.
  1. transition Based的方法很灵活，我们可以切换新的transition system而不改变整个算法流程和底层的parsing 算法。我们可以有用于各种各样的处理不同问题的transition system，比如做POS，做non-projective 依存分析，语义角色标注等等。
  2. 在greedy的算法中，当oracle给出错误的transition之后，是没有回退并尝试新的transition的。另外最后只返回一个确定的 transition sequences.
  3. 基本的transition based的方法只能产生projective trees

    Graph Based method

    利用了有向加权图的maximum spanning tree(MST)算法

    样例

    graph-method

    模型训练

    使用基于推断的学习结合了感知器学习法则。我们先用初始的权重 parse a sentence,如果 parse tree不正确,会做权重更新.找到incorrect parse中出现而在reference parse的不出现的feature,以一定学习率降低这些feature相应的权重。

    Graph Based method 的优缺点

  4. graph based的方法可以产生 non-projective trees
  5. 经验上来说，transition based的方法在依存关系比较短的时候有很高的正确率，但随着head和dependent之间的距离增大，它的准确率会显著下降。相比之下，transition based的方法使用了greedy local decisions，而Graph Based的方法尝试通过给整棵树打分来避免这种情况。

    基于神经网络的依存句法分析（Neural Dependency Parsing）

    《A Fast and Accurate Dependency Parser using Neural Networks》
    虽然有很多深度学习模型应用在依存语法上，这部分特别 侧重于基于贪心和基于转移的神经网络依存语法分析器。
    为什么需要神经网络句法分析器？？
    传统特征表示稀疏、不完全、计算代价大(SVM之类的线性分类器本身是很快的，而传统的parser的95%时间都花在拼装查询特征上)。神经网络依存语法分析器性能和效果比较好。

我们将要描述的模型采用前一部分中所讲述的arc standard transition system进行转换。最终模型的目标是预测从一些初始状态c到一个终点状态的转换序列，在模型中依存语法树被编码的。由于模型是贪心的，它基于从当前的状态c=$(\sigma,β,A)$提取特征，然后尝试一次正确地预测一次转移T∈{SHIFT，Leftarc,Rightarc}。

特征选择：根据该模型所需地复杂性，定义神经网络地输入是有灵活性地。对给定句子S地特征包含一些子集：

  1. $S_{word}$:在堆$\sigma$的顶部和缓冲区β的S中一些单词的词向量(和它们的依存).
  2. $S_{tag}$：在S中一些单词的词性标注(POS)。词性标注是由一个离散集合组成：P={NN,NNP,NNS,DT,JJ,….}
  3. $S_{label}$：在S中一些单词的依存标签。依存标签是由一个依存关系的离散集合组成：L={amod,tmod,nsubj,csubj,dobj,….}。
    对每种特征类型，我们都有一个对应的特征的one-hot编码映射到一个d维的稠密的向量表示的嵌入矩阵。$S_{word}$的完全嵌入矩阵是$E^w∈R^{d×N_w}$,其中$N_w$是字典/词汇表的大小。相应地，POS和依存标签地嵌入矩阵分别为$E^t∈R^{d×N_t}$和$E^l∈R^{d×N_l}$,其中$N_t$和$N_l$分别为不同词性标注和依存标签地个数。最后，定义从每组特征中选出地元素的数量分别为$n_{word},n_{tag},n_{label}$。
    example
    注意我们使用一个特殊的NULL表示不存在的元素：当堆和缓冲区为空或者还没有指定依存关系时。对一个给定句子例子，我们按照上述方法选择单词、词性标注和依存标签，从嵌入矩阵$E^w,E^t,E^l$中提取它们对应的稠密的特征的表示，然后将这些向量连接起来作为输入$[x^w,x^t,x^l]$。在训练时，我们反向传播到稠密的向量表示，以及后面各层的参数。

神经网络模型

这个神经网络包含一个输入层$[x^w,x^t,x^l]$,一个隐藏层，以及具有交叉熵损失函数的最终softmax层。我们可以在隐藏层中定义单个权值矩阵，与$[x^w,x^t,x^l]$进行运算，我们可以使用三个权值矩阵$[W_1^w,W_1^t,W_1^l]$,每个矩阵对应着相应的输入类型。如下图所示，然后我们应用一个非线性函数和再使用一个仿射层$[W_2]$，使得对于可能的转移次数(输出维度)，有相同数量的softmax概率。
Neural_network
注意上图中，使用的非线性函数是f(x)=$x^3$

未来的工作

-------------本文结束感谢您的阅读-------------

本文标题:CS224n笔记（三）

文章作者:Yif Du

发布时间:2018年11月22日 - 15:11

最后更新:2018年11月27日 - 20:11

原始链接:http://yifdu.github.io/2018/11/22/CS224n笔记（三）/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。