基于转换的神经网络依存句法分析器

依存句法分析是自然语言处理中一个关键的问题，一是判断给定的句子是否合乎语法，再是为合乎语法的句子给出句法结构。为了准确做出句子的依存关系，不少学者提出了一些方法，如基于图的方法，基于转换的方法等。

基于转换的依存句法分析

Yamada和Matsumoto提出了使用SVM来训练基于转换的依存分析算法。他们根据三种分析行为（shift, right, left）对输入的句子进行从左到右顺序构建一颗依存树，他们的算法属于自底向上（bottom-up）的分析算法。分析器算法分为两步：
1. 使用目标节点周围上下文信息估计合适的分析行为
2. 依据所执行的行为构建一个依存树
分析算法的核心就是提取目标结点的上下文信息，并依据模型估计最可能的分析行为（在训练模型时是由标注的依存树给出分析行为，在预测的时候是学习的模型给出）。
为了提取特征，Yamada使用一个三元组(p,k,v)来表示一个特征，p表示距离目标节点的位置，k为特征类型，v为特征的值。对于特征类型和特征值他给出了一个表格。然后对应特征和分析行为（shift, right, left）进行训练。由于是多分类任务，Yamada使用了O vs.O的训练方法，并给出了一些评价分析器的标准：

Nivre总结了两种基于转换的依存分析方法，一种是arc-standard parsing，另一种是arc-eager parsing。前一种是标准的自下而上的方法，如Yamada提出的方法；后一种是结合了自底而上和自上而下（top-down）的方法，这个方法是只要head和其依赖存在，就向依存图中添加弧，即使这个依赖的依赖还没有添加弧。

arc-standard parsing

对于一个单词序列W=w1⋯wn，我们认为wi<wj，即单词wi在单词wj的前面，wi→wj表示从wi到wj有一个弧，A为(wi,wj)弧的集合。arc-standard parsing的构造由一个三元组<S,I,A>构成。S是一个栈，I是一个输入序列，是一个列表，A是依存图的弧关系。给定一个输入字符串W，分析器的初始化为<nil,W,∅>，最后终结为<S,nil,A>。
那么，arc-standard分析器的策略有三种：
1. left-reduce转换，它通过一个左向的弧wj→wi把栈顶最上的两个元素wi和wj联系起来，并抛出wi。
2. right-reduce转换，它通过右向弧wi→wj把栈顶最上的两个元素wi和wj联系起来，并抛出wj。
3. shift转换，把I中的下一个输入wj压进栈。

left-reduce和 right-reduce的约束就是一个词只能有一个依赖，即wi→wj⋀wk→wj⇒wi=wk。而shift的约束就是输入列表中不能为空。
整个过程由下图表示：

arc-eager parsing

arc-eager算法的转换过程如下：
1. left-arc转换，从下一个输入wj到栈顶的元素wi加一个弧wj→wi并把栈顶的元素wi抛出。
2. right-arc转换，从栈顶的元素wi像下一个输入wj添加一个弧wi→wj，并把wj压进栈中。
3. reduce转换，是抛出栈顶元素。
4. shift转换，是把下一个输入元素wj压进栈。
left-arc，right-arc和shift与arc-standard中的约束一样，而 reduce的约束是栈顶的元素已经有了一个head。具体表示如下图：

基于转换的神经网络依存分析器

由于很多的依存分析器基于很多的稀疏特征，他们的推广性较差，并且计算代价大，Chen和Manning提出了基于转换的神经网络依存分析，它使用了少量的密集特征，计算迅速，并且attachment scores有所提升。
他们使用的转换方法是arc-standard方法，前面已经叙述过。由下面的一张图展示依存分析转换的过程，其中，第三张图的每一行就是一个configuration：

不过，这里面我有一点不懂的是，它是怎么把栈顶第二个元素抛出而不影响栈顶第一个元素的，比如在上图的第三张图中，第5行的转换为SHIFT，栈为[ROOT has good control]，经过LEFT-ARC(amod)转换后，怎么把good抛出的（计算机中，如果是栈的话，抛出栈顶第二个元素那么肯定把栈顶第一个元素已经抛出了，为什么control还在栈中呢？是不是把它又压进栈了呢，不清楚）。
这个神经网络分析器其实只有三层结构，输入层，隐含层和输出层。下图展示了分析器的层级结构：

输入层是词向量，词性标注向量和弧标签向量的拼接层；隐含层使用了一个三次方的非线性函数；输出层就是一个softmax层。其实重点在这个输入层怎么表示。
首先对于词向量，对于每一个词，使用d维的向量ewi∈Rd来表示，整个词向量矩阵表示为Ew∈Rd×Nw，其中，Nw为字典大小。同样的，词性标注和弧标签也由一个d维的向量表示eti,elj∈Rd，对应的词性标注和弧标签向量矩阵分别为Et∈Rd×Nt,El∈Rd×Nl，其中，Nt,Nl分别为词性标注和弧标签的个数。
用Sw,St,Sl分别代表从单词，词性标注和弧标签抽取的集合，每一个configuration都有一个Sw,St,Sl。例如，在上图的configuration中，词性标注集合St={lc1(s2).t,s2.t,rc1(s2).t,s1.t}，从左到右意思为栈顶第二个元素左子结点的词性、栈顶第二个元素的词性、栈顶第二个元素右子结点的词性、栈顶第一个元素的词性，则它们分别为PRP、VBZ、NULL、JJ，用NULL表示不存在。一般来说，最多使用目标词的子结点的子结点就够了，即lci(lci(s2)).t，再深的没见过。
这样我们得到了Sw,St,Sl，这里面只是一个个的单词、词性及标签，并不是它们的向量表示。用nw,nt,nl分别表示选择每种类型元素的个数，则xw=[eww1;eww2;⋯;ewwnw]，其中，Sw={w1,⋯,wnw}，类似地可以得到xt,xl。即把[xw,xt,xl]代入输入层。
从输入层到隐藏层使用三次方**函数:

其隐层单元个数为dh，Ww1∈Rdh×(d⋅nw)，Wt1∈Rdh×(d⋅nt)，Wl1∈Rdh×(d⋅nl)，b1∈Rdh为偏置。
softmax层输出多元概率p=softmax(W2h)，其中，W2∈R|T|×dh，|T|为转换类型的个数。

参数初始化及训练

首先从训练句子和“黄金分析树”中产生训练集为{(ci,ti)}mi=1，ci为configuration，ti∈T为转换。
目标函数为交叉熵损失函数加上L2正则化：

其中，θ为{Ww1,Wt1,Wl1,b1,W2,Ew,Et,El}的参数集。
初始化：用预训练的词向量(使用word2vec)初始化Ew，也可以进行随机初始化，用在(-0.01,0.01)内的数随机初始化Et,El
优化：使用min-batched AdaGrad，dropout(0.5)
预测：首先从configuration c中抽取对应的词向量，词性标注向量和类别标签向量，然后计算隐藏层h(c)∈Rd，在softmax输出时，找到最大概率的转换：

然后再执行转换c→t(c)，直至把整个句子转换完。
Weiss等人在Chen的基础上又增加了一层隐含层和一层感知机层，并且这两层隐含层和softmax层与感知机层都有连接，如下图：

此网络结构在Chen的基础上准确度提高了大约1%。具体可以参考他们的文章Structured Training for Neural Network Transition-Based Parsing

【Hiroyasu Yamada, Yuji Matsumoto】STATISTICAL DEPENDENCY ANALYSIS WITH SUPPORT VECTOR MACHINES
【Joakim Nivre】Inductive Dependency Parsing
【Joakim Nivre】Incrementality in Deterministic Dependency Parsing
【Danqi Chen, Christopher D. Manning】A Fast and Accurate Dependency Parser using Neural Networks
【David Weiss, Chris Alberti, Michael Collins, Slav Petrov】Structured Training for Neural Network Transition-Based Parsing