目录
15.0 前言15.1 依存关系15.2 依存形式主义15.2.1 投射性 15.3 依存树库15.4 基于转移的依存分析15.4.1 创建一个 Oracle15.4.2 基于转移的分析的高级方法 15.5 基于图的依存分析15.5.1 句法分析15.5.2 特征与训练15.5.3 图分析的高级问题 15.6 评价 Evaluation15.7 总结文献和历史说明15.0 前言
前三章的重点是上下文无关语法和它们在自动生成基于成分表示中的应用。这里我们介绍另外一个形式主义语法，叫做依存语法，在当代语言处理中十分重要。在这类形式主义中，短语成分以及短语结构规则起不到直接的作用。取而代之的是，一个句子的句法结构，通过句子中的词语（或者词根）以及词语间相联系的一套有向二元语法关系描述。
下面的示意图，描述的就是依存方式的分析，使用的是标准的图形方法，这是社区常用的依存分析方法。
上图中词语之间的关系由词语间带方向的、有标记的弧来表示。我们称之为类型化的依存结构（typed dependency structure），因为这些标签来自于一个固定的语法关系清单。结构中包含一个 root 节点，显式地标注了树的根节点，也就是整个结构的中心词语。
上面的句子，我们在12章中做过它的短语结构分析。注意，依存分析没有与短语成分或词汇范畴相应的节点。依存分析的内部结构只包含词语之间的的有向关系。这些关系直接对重要的信息进行编码，这些信息在更复杂的短语结构分析中往往是隐藏的。例如，在依存结构中，动词 prefer 的论元与 prefer 直接连接；在短语结构树中，论元与主要动词的联系就远多了。同样， flight 的修饰语 morning 和 Denver，在依存结构中，也是直接和 flight 连接。
依存语法的一个主要优势是能够处理形态丰富并且词序相对自由的语言。例如，捷克语的词序比英语的词序灵活得多；一个语法上的宾语可以出现在地点状语的前面或者后面。对于语法树中可能出现此类副词短语的每个可能位置，短语结构语法都需要一个单独的规则。在依存句法中，只用一种连接类型，来表示这种特定的状语关系。因此，依存语法的方法不考虑词序信息，只表示对于句法分析有用的信息。
另外一个使用基于依存方法的实际动机是，这种中心词依赖关系能够一定程度上反映出谓词与其论元的语义关系，这使得这种关系在共指消解、回答问题、信息提取等应用中非常有用。
基于成分的分析方法也能提供这样的信息，但是通常需要通过第12章中我们讨论过的一些方法，比如中心词查找规则，从树中提取出来。
在后面的章节中，我们将更具体地探讨依存分析中的各种关系，当然还有这些依存结构的形式基础。然后我们将继续讨论用于自动生成这些结构的主流算法。最后，我们将讨论如何评估这些依存分析器，还有它们在语言处理应用中的使用方法。
15.1 依存关系
语法关系传统语言学意义上的语法关系为构成这些依存结构的二元关系提供了基础。这些关系中的论元包含一个核心词（head）、一个依存词（dependent）。我们在第12和14章中将成分结构的时候讨论过核心词。那时候，一个成分的核心词或者说中心词，是这个大成分的具有中心组织地位的词语（比如动词短语中的动词）。这个成分中的其他词语，直接或者间接地成为了中心词的依附词。在基于依存的方法中，核心词与直接依附于它的相连，绕过成分结构，这使得这种 核心词-依存词关系更加地明确。
语法功能除了表示出 核心词-依存词 这样的词对，依存语法进一步对这些语法关系或者说语法功能进行分类，根据是核心词的依存词所扮演的角色。例如主语、直接宾语、间接宾语这些我们熟悉的概念，都是处在这些关系中。在英语中，这些概念与其句中位置、成分类型密切相关，因此他们在短语结构树种显得有些多余。不过在更加灵活的语言中，这些语法关系所直接承载的信息就会很重要，因为基于短语的成分句法帮不上忙了。
通用依存关系毫不奇怪，语言学家已经发展了关系分类法，其范围远远超出了熟悉的主语和宾语概念。尽管理论之间存在很大的差异，但由于存在足够的共通性，因此现在有可能努力开发可用于计算的标准。通用依存项目提供了一套依存关系的清单，它是基于语言学的、能用于计算的、并且跨语言适用的。图15.2 是此项工作的一个子集，图15.3 为这些关系提供了例句。
我们不讨论通用依存关系方案中的全部关系，不过核心的常用关系可以分为两个集合：从句关系，描述关于谓语（通常是一个动词）的句法角色；修饰关系，将词语对核心词的修饰关系进行了分类。
再以下面句子为例：
从句关系 NSUBJ 和 DOBJ 指明了谓语 cancel 的主语和直接宾语，NMOD、DET、CASE 指明名词 flights 和 Houston 的修饰语。
15.2 依存形式主义
通常来看，依存结构简单来说就是有向图。也就是说，结构 G = ( V , A ) G=(V,A) G=(V,A) 包括顶点的集合 V V V ，以及有向的顶点对集合 A A A，我们称之为弧。
一般我们把顶点的集合 V V V 对应于定句子的词语集合。不过，其中也包含标点符号，或者在处理形态复杂的语言时，顶点的集合也包括词干和词缀。集合 A A A 捕获了集合 V V V 中元素的核心词-依存词对以及语法功能关系。
依存结构的其他约束条件在语法和形式上。比如各结构必须是相连的，有确定的根节点，图是无回路且扁平的。与本章讨论的分析方法关系最密切的是关于分析树的常见且可计算的一些制约条件。也就是，依存树是满足下列条件的有向图：
有一个确定的根节点，并且根节点没有入弧，入度为零。除去根节点，每一个定点只有一个入弧。从根节点到 V V V 中的任何一个顶点，只有一条路径。
总的来说，以上条件保证了每个词有一个核心词，保证了依存结构是联通的，而且只有一个根节点，从这个根节点出发，可以到达句子中的任何一个单词。
15.2.1 投射性
投射性是附加的另一个条件，它来源于 input 的词序，与12章中我们讨论的人类语言中的上下文无关特性密切相关。从核心词到依存词有一个弧，这个弧的区间内有多个词语，如果核心词到其间任意的一个词都有一条路径，我们就说这个弧具有投射性。如果一个依存树所有的弧都是投射性的，那么我们就说这个依存树也是投射性的。目前我们讨论过的依存树都是投射性的。不过，仍然存在合理的结构但是它的依存树没有投射性，尤其是在那些语序相对灵活的语言中。看下面例子：
在上面的例子中，从 flight 到它的修饰成分 was 的弧就是一个非投射性的，因为从 flight 到弧内部的词语 this 或 morning 并不存在路径。如图所示，投射性或非投射性可以直接从分析树中看出来。如果一个依存树中没有交叉的弧，那它就是投射性的。上面的图，从flight 到 was 的弧没有办法不与 canceled 到morning 的弧交叉。
我们之所以关注投射性，原因有两个。第一，使用最广泛的英语依存树库是使用核心词查找规则，从短语结构树库中自动生成的（第12章）。通过这种方法生成的树一定是投射性的，因为他们是由上下文无关语法生成的。
第二，使用最广泛的分析系列算法存在计算缺陷。即将在15.4中讨论的基于转移的方法只能产生投射性的树，所有任何非投射性的句子都必然包含一些错误。因为存在这样的缺陷，我们将在15.5中介绍更灵活的基于图的分析方法。
15.3 依存树库
与基于成分的方法一样，树库在依存分析其的发展和评价中具有重要作用。依存树库的构建方法与12章中介绍的方法类似——由人工标注者直接通过语料库构建依存结构，或者使用自动分析器来进行初步分析，然后人工进行校正。我们还可以使用一个确定性过程，将现存的成分树库，通过应用核心词规则，转变为依存树。
多数情况下，直接标注的依存树库多用为形态丰富的语言，比如捷克语、印地语、芬兰语，其中捷克语的布拉格依存树库是最有名的一个。主流的英语依存树库大多是利用现存的资源建立的，如宾州树库中的华尔街日报部分。最近的 OntoNotes 项目，使用这种方法将文本从传统新闻，扩展到电话对话、博客、广播、脱口秀等，语言包括英语、汉语、阿拉伯语。
从成分结构到依存结构的转换过程有两个子任务：识别结构中所有的核心词-依存词关系；识别这些关系的正确类别。第一个任务以来核心词规则，它最早是用于词汇化概率分析器。下面是一个简单有效的算法，来自于 Xia and Palmer（2001）：
Mark the head child of each node in a phrase structure, using the appropriate head rules.In the dependency structure, make the head of each non-head child depend on the head of the head-child.
如果一个短语结构分析含有语法关系、功能标签等额外信息，正如宾州树库中的例子，这些标签就可以标注在生成的树的弧上。
这种提取方法的主要缺陷是受限于原始成分树中的信息。其中最大的问题包括不能将形态信息和短语结构树整合起来，不能轻松表示非投影性的结构，大部分名词短语缺乏内部结构，这在多数树库语法的扁平规则中有所体现。由于这些原因，除了英语，多数依存树库都是直接使用人工标注建立的。
15.4 基于转移的依存分析
shift-reduce parsing我们第一种进行依存分析的方法来源于一种基于堆栈的方法，叫做 移进—规约分析shift-reduce parsing，最初是开发用于分析编程语言的。这个经典方法非常简单且优雅，使用上下文无关语法，一个堆栈，还有一组用于分析的句子。输入符号持续地移进到堆栈中，栈顶的两个元素根据右侧的语言规则进行配对；如果配对成功，配对后的元素就由非终结符替代（reduced）from the left-hand side of the rule being matched. 如果将这种方法应用于依存分析，我们放弃对语法的显式使用，并更改 reduce 操作，我们不给分析树添加非终结符号，而是给词语和其中心词加上依存关系。更具体来说，reduce 动作被两个其他动作代替：声明栈顶单词与其下面单词的核心词-依存词关系，或者反过来。图15.5对这种分析器的基本操作进行了说明。
基于转移的分析中有一个关键的概念叫做 配置 （configuration），它包含一个堆栈（stack），一个 input 单词或符号的缓存器（buffer），一套表示依存树的关系。给定这个框架，分析过程就是在配置空间中进行的一系列转换。这个过程的目标是找到最终配置，最后所有单词都被考虑了，并且合成了一棵适当的依存树。
要实施这样的搜索，我们要定义一套转换操作，操作一个配置产生新的配置。有了这些设定，我们就可以把分析器的操作看做是在配置空间内的搜索过程，目的是找到从开始状态到目标状态的一系列转移。在开始时我们创建一个初始配置，初始配置中的堆栈内只有ROOT节点，词语列表初始化为句子中的单词或者是进行了词形还原的字符，还有一个初始为空的关系集合来储存后续的句法分析。在最终配置中，堆栈和词表必须清空，关系集合表示出最终的分析结果。
在标准的转移分析方法中，用于产生新配置的各操作符是极其简单的，并且对应于人从左向右检查单词创建依存树的直观动作（actions）：
把当前单词指定为前面某单词的核心词，把前面某单词指定为当前单词的核心词，或者对当前单词暂不做任何处理，暂把它存储起来，稍后再做处理。
为了使这些 actions 更加精确，我们创建三个转移操作符，对栈顶的两个元素进行操作：
LEFTARC：声明顶部单词与栈内第二个单词是核心词-依存词关系；并移除栈内第二个单词。RIGHTARC：声明栈内第二个单词与顶部单词是核心词-依存词关系；并移除顶部单词。SHIFT：把缓存器中最前面的单词推到堆栈中。
这一组特定的操作符实现了基于转移的句法分析，也被称作 弧标方法（arc standard approach）。这个方法有两个显著特征：转移操作符只声明堆栈顶部两个元素的关系，而一个词找到它的核心词后，就会被移出堆栈，也就不能再进行后续分析。后面我们会看到，还存在其他转移系统，能够进行其他的分析方式，不过弧标方法仍然是非常有效并易于实现的。
为保证合理地使用这些操作符，我们需要给他们的使用加一些前提条件。第一，因为 ROOT 节点不能有入弧，我们规定当ROOT是堆栈内第二个元素时，LEFTARC不能使用。第二，LEFTARC和RIGHTARC这两个 reduce 操作符，都必须在栈内有两个或以上元素时才能使用。有了这些转移操作符和前提条件，基于转移的句法分析器就非常简单了。下图是基本的算法：
在每一步，分析器会向预言机（oracle）询查，oracle根据当前的配置提供一个准确的转移操作符。然后分析器将这个操作符应用于当前的配置，随后产生一个新配置。当句子中所有的单词都已经处理，并且堆栈内只剩 ROOT 节点一个元素，整个分析过程就结束了。
基于转移的句法分析器其效率从算法上可以明显看出来。复杂度是线性的，决定于句子的长度，因为它就是一个从句子左侧到右侧的遍历过程。更具体来说，每个单词都是先被移进堆栈，然后被移除。
注意，与12章和13章中动态规划和基于搜索的方法不同，这个方法是一个简单的贪心算法——oracle 为每一步只提供一个指示，分析器运行这个指示，不存在其他的选择，也没有回溯，并且最后只返回一个句法分析结果。
下面的例子展示了分析器的转移过程的操作，生成了一个分析结果：
我们具体来看一下第2步的配置状态，在 me 被推入到堆栈后。
正确的操作是 RIGHTARC ，把 book 指定为 me 的核心词，然后把 me 从堆栈中删除，最后得到下一个配置。
在使用 SHIFT 和 LEFTARC 进行了一系列操作之后，第6步的配置变成了下面这样：
在这里，所有的单词已经全都推入到了堆栈中，剩下要做的就是用合适的 reduce 操作了。在当前配置中，我们须使用 LEFTARC 产生下面一个新配置：
这个时候，句子的分析就变成了下面的结构了：
在生成转移序列的过程中，需要注意几个重要的事情：第一，生成的转移序列并不是唯一合理的句法分析。一般来说，生成同样的结果可能不止一条路径，如果句子还存在歧义，可能还会通过不同的转移序列，产生不同的但是合理的句法分析。
第二，在句法分析时我们假设 oracle 在每一步提供的操作都是正确的——然而这个假设在实践中是不太现实的。结果就是，这个算法本质上是贪心的，错误的指示将导致错误的分析，原因是分析器是没有机会回溯并且得到其他的指示的。在15.4.2这一节，我们将介绍一些技术，使基于转移的方法能够充分地对空间进行个搜索。
第三，为了简单起见，我们没有给例子加上依存关系的标签。要产生带标签的分析树，我们可以为 LEFTARC 和 RIHGTARC 加上依存标签这一参数，比如 LEFTARC(NSUBJ) 或者 RIGHTARC(DOBJ)。同样，我们也可以扩展原来只含有 3 个操作符的集合，把依存关系集合中的每个关系都加上 LEFTARC 和 RIGHTARC，再加入一个 SHIFT 操作符就成了。当然，这样使得 oracle 的工作难度增加了，因为它现在需要从更大的操作符集合中进行选择。
15.4.1 创建一个 Oracle
基于转移的SOTA系统是使用有监督的机器学习方法来训练一个分类器，作为 oracle 来使用。给合适的训练数据，这些方法将学到一个函数，这个函数将配置映射为转移操作符。
和其他有监督的机器学习方法一样，我们需要得到合适的训练数据，还需要提取有用的特征以用于决策。训练数据来源于含有依存树的树库。特征包含很多第8章词性标注用到的特征以及第14章中统计分析模型用到的特征。
生成训练数据
我们回顾一下 oracle 来充分理解学习问题。oracle 输入的是一个配置，返回的是一个转移操作符。因此，要训练一个分类器，我们需要成对的配置和转移操作符。不幸的是，树库内是句子与相应分析树成对，所以不能直接提供我们想要的。
为了生成所需的训练数据，我们将巧妙地采用基于oracle的分析算法。我们将训练句子连同其在树库中对应的参考句法分析喂给我们的 oracle。为了生成训练实例，我们将模拟解析器的操作，方法是通过运行算法，依靠一个新的训练 oracle 为后续的配置提供正确的转移操作符。
想要看这到底怎么做的，我们先来回顾一下分析器的操作。它以一个默认的初始化配置开始，其中堆栈中只有一个 ROOT，input 列表就是单词列表，关系集合是空的。操作符 LEFTARC 和 RIGHTARC 持续将栈顶两个词的关系添加到关系集合中，为给定的句子积累起所有关系。由于每一个训练句子都有一个最佳的参考分析，我们就知道哪些依存关系对于给定句子是合理的。因此，当分析器逐步进行配置更新时，我们可以使用参考分析来指导操作符的选择。
更准确来说，给定一个参考分析和一个配置，训练 oracle 的过程如下：
选择 LEFTARC，如果给定参考分析和当前配置的情况下，它能产生一个正确的核心词-依存词关系，
否则，选择 RIGHTARC，如果（1）在给定参考分析的情况下，能产生一个正确的核心词-依存词关系，（2）在栈顶的所有依存词都已经被指定（在栈顶不能产生向左的箭头），
否则，选择 SHIFT。
选择 RIHGTARC 操作符需要有限制条件，以确保某个单词在所有依附它的词都被找出前，不会从堆栈中删除，否则没法进一步处理。
更正式地说，在训练期间， oracle 是可以获取下面的信息的：
当前的配置，包括堆栈 S 和依存关系集合 R c R_c Rc
一个参考分析，包括顶点集合 V V V 和 依存关系集合 R p R_p Rp
有了这些信息，oracle 将进行如下的转移操作：
LEFTARC( r ): if ( S 1 r S 2 ) ∈ R p (S_1 r S_2) \in R_p (S1rS2)∈Rp
#选择LEFTARC，如果堆栈S内的第一个元素到第二个元素的依存关系是在 R p R_p Rp里的。
LEFTARC( r ): if ( S 1 r S 2 ) ∈ R p (S_1 r S_2) \in R_p (S1rS2)∈Rp and ∀ r ′ , w s . t . ( S 1 r ′ w ) ∈ R p \forall r',w\;s.t.(S_1r'w)\in R_p ∀r′,ws.t.(S1r′w)∈Rp then ( S 1 r ′ w ) ∈ R p (S_1r'w)\in R_p (S1r′w)∈Rp
#选择RIGHTARC，如果堆栈S内的第二个元素到第一个元素的依存关系在 R p R_p Rp中，并且所有以 S 1 S_1 S1为核心词的关系都已经在 R c R_c Rc中了，
SHIFT：otherwise
#以上条件都不符合时，选择SHIFT，
我们逐步来看一下下面这个例子的处理步骤：
第一步，这时是初始配置，不能使用LEFTARC，因为（root <— book）不再参考答案中；RIGHTARC 倒是可以创建（root—> book）这个合法的关系，但是此时book还没有找到它的依存词，所以我们必须等等，这样我们只能在这一步选择 SHIFT 了。随后的两步也是同样的情况。到了第三步，就可以选择 LEFTARC 来连接 the 和它的核心词。
现在来看第四步的情况，
这里我们可能会想在 book 和 flight 之间指定依存关系，这个关系也确实在参考分析中。但是如果我们这样做，flight 就会从堆栈中删除，我们就不能建立后续的 Houston 和 flight 的关系了。还好我们设定了使用 RIGHTARC 的前提条件，这样我们再一次选择 SHIFT 作为处理方式。后续的过程逐步完成了所有操作符的选择。
概括一下，我们通过参考树库中的依存树，模拟了分析器的操作，生成了由 配置-转移对组成的训练实例。
在我们处理每个训练实例时，我们可以确定地记录分析器的每一个操作，也就创建了我们需要的训练集。
特征
生成合适的训练实例后（配置-转移对 configuration-transition pairs），我们需要从配置中提取有用的特征，以训练分类器。用来训练基于转移的系统的特征根据不同语言、语域、分类器而不同。例如，形态句法特征诸如主语或者直接宾语等格标记，根据处理的语言不同，而有不同的重要性。基本的特征，比如词类标记、部分分析等在训练各种语言的依存分析器时，都挺有用。词语形态、词根、词性都是强大的特征，当然还有核心词、核心词的依存关系等。
在基于转移的分析框架中，这些特征需要从配置中提取出来，以组成训练数据。还记得配置包含三个元素：堆栈stack，缓存器buffer，当前关系集合。原则上，这些元素的任何或全部属性都能作为训练的特征。不过，为了避免稀疏性，提升范化能力，最好将训练算法集中到分析构成中对于决策最有用的方面。因此，对于转移分析特征的提取，重点在于栈顶词、缓存器前端词、以及与这些词相关的依存关系。
通过把简单的特征，比如词形或者词性，与一个配置的具体位置结合起来，我们可以使用特征模版（feature template）这一概念，在进行情感分析、词形标记时我们了解过。特征模版可以帮我们从训练集中自动生成大量的具体特征。看一个例子，下面是一个配置的特征模版：
在以上例子中，每个特征都表示为 location.property 的形式，s 表示堆栈，b 表示缓存器，r 表示关系集合。处在每个 location 上的 property 有 w 表示词形，l 表示词根，t 表示词性。例如，栈顶词的词形这一特征可以表示为 s 1 . w s_1.w s1.w，缓存器前端单词的词性可以表示为 b 1 . t b_1.t b1.t。我们还可以把特征堆叠起来，成为一个更具体的有用特征。比如，特征 s 1 . w t s_1.wt s1.wt 表示栈顶词语的词形和词性堆叠起来。最后，op 代表当前训练实例的转移操作符。（也就是，这个训练实例的标签）
下面是训练 oracle 时的一个中间配置状态，我们使用简单的单元素特征模版来看一下：
这里正确的转移是 SHIFT 。将我们的特征模版应用于当前配置，将实例化为以下特征：
鉴于转移操作的是堆栈顶上的两个元素，由在这两个位置的词语的属性结合起来的特征会更有用。例如，特征 s 1 . t ∘ s 2 . t s_1.t \circ s_2.t s1.t∘s2.t 把栈顶两个词的词性标签堆叠起来。 < s 1 . t ∘ s 2 . t = N N S V B D , o p = s h i f t > <s_1.t \circ s_2.t=NNSVBD,op=shift> <s1.t∘s2.t=NNSVBD,op=shift>那么，既然两个属性更有用，那么三个或者更多属性将更好。下图给出了常用特征模版的一个 baseline。
注意，有一些特征使用的是动态特征——比如在分析过程中前面步骤预测出的核心词以及依存关系，与之相对的是 input 的一些统计特征。
学习（learning）
多年以来，训练基于转移的依存分析器主要使用多项式回归和支持向量机，这两种方法都可以有效利用上一节中介绍的大量稀疏特征。近来，神经网络，或者说深度学习，已经成功地应用到基于转移的分析当中。这些方法不再需要复杂的、手工编制的特征，尤其非常有效地克服了与训练分析器相关的数据稀疏性问题，
15.4.2 基于转移的分析的高级方法
通过解决该方法中的一些最明显缺陷，可以有多重方式来提升基础的基于转移的方法的性能。
其他转移系统
上面介绍的以弧为标准的转移系统只是很多系统中的一个。另一个常用的系统叫做 arc eager 转移系统。叫做 arc eager 的原因是相比于 arc standard 方法，它能更快地找到向右的关系。我们通过下面的例子回顾一下 arc standard 方法。
看一下 book 和 flight 的依存关系。上图中， arc-standard 方法将在第8步得到这个关系，虽然事实上 book 和 flight 早在第4步就一起出现在堆栈中了。不能再早期得到这个关系的原因是后置名词性修饰语 through Houston 的出现。在 arc-standard 方法中，依存词一旦找到自己的核心词，就会被移出堆栈。如果 flight 在第4步就找到 book 作为它的核心词，flight 就被移出堆栈，flight 就不能被 后面的 Houston 作为核心词找到了。
虽然在这个例子中，这个延迟并没有导致什么问题，但是一般来说一个词找到核心词的时间越久，就越容易出差错。 arg-eager 系统就允许词语尽快找到自己的核心词，早于后续它的依存词出现之前。我们通过对 LEFTARC 和 RIGHTARC 做小小的改变，并加入一个新的 REDUCE 操作符，就可以实现这个方法。
LEFTARC：声明缓存器 buffer 的最前端词与堆栈 stack 的最顶端词是核心词-依存词关系；然后从堆栈中删除。
RIHGTARC：声明堆栈 stack 的最顶端词与缓存器 buffer 的最前端词是核心词-依存词关系；把 buffer 的最前端词转移（shift）到 stack 中。
SHIFT：把缓存器 buffer 的最前端词推入到堆栈中。
REDUCE：删除堆栈中词。
LEFTARC 和 RIGHTARC 作用于堆栈顶端词和缓存器前段词，而不是arc-standard方法中的堆栈顶端的两个词。现在 RIGHTARC 操作符是将依存词从 buffer 移动到堆栈stack，而不是从堆栈移除，这样它就可以作为后续词语的核心词了。新的 REDUCE 操作符是删除堆栈中的最顶元素。这些改变共同作用，允许一个词 eagerly（很快地）找到自己的核心词，而后仍然留在堆栈中成为后续依存词的核心词。下图说明了这个例子新的决策过程。
除了对 arc-eager 转移系统进行了说明，这个例子还展示出基于转移的方法具有相当的实力和灵活性。我们能够使用新的转移系统，而不需要对底层的分析算法做任何改变。这种灵活性使各种各样的转移系统得到了发展，用以解决句法和语义不同方面的问题，比如：标注词性、生成非投射性的依存结构、标注语义角色、对多语言文本进行分析。
集束搜索（Beam Search）
基于转移的方法其较高的计算效率源于以下事实：它仅对句子进行一次遍历，贪婪地作出决策而不考虑其他选择。当然，这也是它的最大缺陷的由来——就是一旦作出决策，它就无法撤销，即使句子后续有充分的证据证明它是错的。另一个方法是系统地检索其他决策序列，从中选择最好的一个。这种检索的关键在于如何管理大量的潜在序列。集束搜索将广度优先搜索策略和启发式过滤器结合起来，对搜索边界进行剪枝，使选择处在一个固定大小的集束宽度内。
为将集束搜索应用到基于转移的分析，我们要详细看一下图15.6的算法。每次迭代我们不再选择单一的转移操作符，而是将所有可用的操作符用到流程（agenda）上的每一个状态，然后给生成的每个配置打分。然后我们根据空间的大小限制，把这些新的配置添加到搜索边界。只要流程数量在给定的集束宽度内，我们就可以一直把配置添加流程内。一旦流程达到最大限度，我们就只添加比最差配置要好的新配置（同时移除最差的元素，以保证在集束宽度内）。最后，为了确保我们在agenda上找到最好的配置，我们要使用 while 循环一直到最终状态。
与使用贪心算法相比，集束搜索方法需要更加详细的打分方式。我们假设用有监督的机器学习来训练分类器作为 oracle，它能根据从当前配置提取的特征选择最佳的转移操作符。不管采用哪种具体的学习方法，这个选择可被视为 给所有可能的转移操作打分，然后选出其中最佳。 T ^ = a r g m a x S c o r e ( t , c ) \hat T = argmaxScore(t,c) T^=argmaxScore(t,c)
通过集束搜索，我们现在可以在序列决策空间中搜索了，一个配置的分数取决于它的全部历史。具体来说，我们可以将新配置的分数定义为它前一个配置的分数加上那个产生这个新配置的操作符的分数。 C o n f i g S c o r e ( c 0 ) = 0.0 ConfigScore(c_0)=0.0 ConfigScore(c0)=0.0 C o n f i g S c o r e ( c i ) = C o n f i g S c o r e ( c i − 1 ) + S c o r e ( t i , c i − 1 ) ConfigScore(c_i)=ConfigScore(c_{i-1})+Score(t_i,c_{i-1}) ConfigScore(ci)=ConfigScore(ci−1)+Score(ti,ci−1)这个分数将用在流程过滤以及选择最终答案。基于转移的句法分析其集束搜索版本的算法如下：
15.5 基于图的依存分析
基于图的依存句法分析是通过搜索树的空间，为给定句子找到一棵或多棵具有最大分数的树。这个方法将搜索空间编码为有向图并使用图论的方法在空间中搜索最佳解决方案。更正式来说，给定句子 S，我们将在空间 g s g_s gs 中寻找最佳的依存树， g s g_s gs 是这个句子所有可能的树的空间，我们在其中找分数最大的树。 T ^ ( S ) = a r g m a x s c o r e ( t , S ) t ∈ g s \hat T(S )=\underset{t\in g_s}{argmaxscore(t,S)} T^(S)=t∈gsargmaxscore(t,S)正如我们在第14章看到的概率上下文无关分析，一棵树的总得分可以看做树各部分得分的函数。这一节的重点是弧分解（edge-factored）方法，一棵树的分数取决于其所有边界的分数。 s c o r e ( t , S ) = ∑ e ∈ t s c o r e ( e ) score(t,S)=\sum_{e\in t}score(e) score(t,S)=e∈t∑score(e)使用基于图的方法有几个原因。第一，与基于转移的方法不同，这个方法可以产生非投射性的树。尽管在英语中投射性不是一个大问题，但是对世界其他语言仍然是个问题。第二个原因是分析的正确率，尤其是在远距离依存的情况下。实践表明，基于转移的方法在短距离依存关系识别上有较高准确率，但是随着核心词与依存词之间的距离逐渐增大，准确率明显下降。基于图的方法避免了这个问题，它是给整棵树打分，而不是依靠贪心的局部决策。
下一部分，我们将研究加权有向图中最大生成树算法（maximum spanning tree MST）。然后讨论用于给树打分的特征，以及用来训练打分模型的方法。
15.5.1 句法分析
这里介绍的方法是使用一个高效的贪心算法在有向图中搜索最佳的生成树。给定一个句子，它首先构建一个全连接的、带权重的、有向图，顶点是输入的词语，有向边表示所有可能的核心词-中心词关系。额外添加一个 ROOT 节点并指向每一个词语。图中的权重表示每个可能的核心词-依存词关系的分数，由数据训练出的模型提供。有了这些权重，这个图中从ROOT开始的最大生成树就是这个句子的最佳依存分析了。下面是 Book that flight 的有向图，最大生成树对应的是图中蓝色的句法分析。为便于说明，我们这里关注不带标签的依存分析。在 15.5.3 我们讨论带标签的基于图的方法。
在介绍算法之前，有必要想一想有向图及其生成树的两个直觉。第一个直觉来自于一个事实，就是生成树中的每一个顶点都只有一个入弧。因此，生成树中每一个连接的部分也都只有一个入弧。第二个直觉是弧上分数的绝对的值对于找到最大生成树不是关键要素。真正有用的是进入每个顶点的弧上的相对权重。如果每个弧上的值减掉一个常数，这对找到最大生成树没有任何影响，因为每个可能的生成树都是减掉了一个同样的数。
算法的第一步非常简单。对于图中的每一个顶点，选出分数最高的入弧。如果这些弧的集合能够生成一棵树，那么大功告成。形式化来说，给定一个全连通图 G = ( V , E ) G=(V,E) G=(V,E) ，一个子图 T = ( V , F ) T=(V, F) T=(V,F) 如果没有环路且每个顶点（除了root以外）都只有一个入弧，那么它就是一个生成树。如果通过贪心选择过程生成了这样一棵树，那它就是最佳的生成树。
可惜这个方法不总能生成树，因为选出的弧的集合可能包含回路。还好，有一种简单的方法可以消除贪心选择过程生成的回路。Chu（1965）和Edmonds（1967）分别独立地发现了一个方法，就是先使用贪心选择，跟着是一个优雅的反复清理阶段来消除回路。
清理阶段先调整图中权重，从每个顶点所有入弧的分数上都减其中最大的那个分数值。这就是之前我们提到的直觉发挥作用的地方。我们调整了弧上的值，使得回路中弧上权重与任何可能的生成树的权重无关。从一个顶点的每个入弧上都减去其中有最大权重的弧的值，使得在贪心选择阶段选择出的所有弧（包括回路中涉及到的所有弧）的权重为零。
调整权重之后，算法选择一个回路然后回路坍缩为一个新的节点，以此创建一个新的图。进入和离开这个回路的两个弧现在变成了这个坍缩节点的入弧和出弧。没有接触到这个回路的弧被保留，回路内的弧被丢弃。
现在，如果我们已经知道这个新图的最大生成树，我们就有足够的信息来消除环路了。最大生成树中指向坍缩节点的弧可以告诉我们哪个边需要删除以消除环路。那么我们如何找到这个新图的最大生成树呢？我们可以将算法重新应用到这个新图上，结果产生一颗生成树或者一个带回路的图。如果生成了带回路的图，这个算法一直这样持续下去。递归结束后，我们展开坍缩的顶点，恢复回路中的顶点和弧，但要删除的那个弧除外。
综合起来，最大生成树算法包含弧的贪心选择，弧权重的重新计分，以及递归的清理阶段。完整算法如图15.13.
图15.14 以 book that flight 为例展示了算法的步骤。第一行说明了弧的贪心选择，其中蓝色的被选出来（对应算法中的集合 F）。结果是在 that 和 flight 之间产生了一个回路。右侧的图显示了减去每个节点入弧最大值后的权重。
第二行，that 和 flight 的回路坍缩为一个节点，然后根据调整后的权重进行递归。在这一步，贪心选择返回了一颗生成树，root 和 book 相连，book 和 坍缩的节点相连。把节点展开，我们可以看到这个弧对应于原图中 book 到 flight 的弧。它反过来告诉我们哪一个弧需要被删除以消除回路。
在任意的有向图中，这个版本的 CLE 算法在时间上的复杂度为 O(mn)，其中 m 是弧的数量，n 是节点的数量。由于这个算法应用在一个全连通的图上，那么 m = n2 使得时间复杂度变为 O(n3)。Gabow（1986）展示了一个更为高效的实现方法，使复杂度降为 O(m+nlogn)。
15.5.2 特征与训练
给定一个句子 S，一棵分析树 T，弧分解分析模型把树的分数分解为组成这棵树的弧的分数之和。 s c o r e ( S , T ) = ∑ e ∈ T s c o r e ( S , e ) score(S,T)=\sum_{e \in T}score(S,e) score(S,T)=e∈T∑score(S,e)然后，每个弧的分数可以分解为特征的加权值 s c o r e ( S , e ) = ∑ i = 1 N w i f i ( S , e ) score(S,e)=\sum_{i=1}^Nw_if_i(S,e) score(S,e)=i=1∑Nwifi(S,e)或更简洁 s c o r e ( S , e ) = w ⋅ f score(S,e)=w \cdot f score(S,e)=w⋅f
有了这些公式，训练分析器还面临两个问题：识别相关特征以及找到给特征打分的权重。
用于训练弧分解模型的特征与训练基于转移的分析器特征类似。这不足为奇，因为在这两种情况下，我们都是试图获取核心词与依存词的单一关系信息。总结之前的讨论，常用的特征包括：
核心词与依存词的词形，词根，词性；词语前后或者之间的语境派生出的相关特征；词嵌入；依存关系本身；关系的方向（向左或向右）；核心词和依存词之间的距离。
与基于转移的方法一样，预选特征进行组合也是常用的做法。
有了一组特征，我们下一步就是学习与每个特征相关的权重。与之前讨论过的很多学习问题不同，这里我们不是训练一个模型来将训练数据与标签或者分析操作匹配。我们要的是训练一个模型，它可以给正确的分析树高分，给错误的分析树低分。对于这个问题的一个有效框架是使用基于推断的学习（inference-based learning），结合感知机的学习方法。在这个框架中，我们随机初始化权重对训练集中的句子进行分析（也就是进行推断）。如果分析结果与训练数据中相应的分析树匹配，我们就不用调整权重。否则，如果我们发现错误分析中的特征在参考分析中没有，我们会根据学习率一点点降低他们的权重。我们对训练集中的每个句子都如此操作，直到权重收敛。
多语言分析中的 SOTA 算法是基于循环神经网络的。（Zeman ）
15.5.3 图分析的高级问题
15.6 评价 Evaluation
正如短语结构分析，评价依存分析器也是通过看其在测试集上的表现。一个明显的指标是准确匹配率 （exact match，EM）——正确分析的句子数量。不过这个指标标价糟糕，因为大多数句子会被判定为分析错误。这个指标粒度不足以指导开发过程。我们的指标需要足够敏感，以判断是否有实际的改进。
因此，最常用的评价方法是带标签的和不带标签的依存正确率。带标签的依存表示找到一个单词正确的核心词以及标记了正确的依存关系。不带标签的依存只是找到单词的核心词，忽略依存关系。给定一个系统输出和一个参考分析，正确率就是正确找到核心词和依存关系的词语在所有输入单词中的比例。这些指标一般是带标签的依存分数(LSA) 和 不带标签的依存分数（UAS）。最后，我们可以使用标签正确分（LS），。。。。。
我们看下面的例子，看一下参考分析和系统输出的分析，
Book me the flight through Houston.
系统正确找到6个依存关系中的4个，得到 LAS 为 2/3。不过，在2个错误的关系中，其中 book 和 flight 只是标记错了，所有系统的 UAS 为 5/6。
除了依存分数，我们可能也会对系统在特定依存关系上的表现感兴趣，例如 NSUBJ。这里我们可以使用准确率和召回率（第八章中介绍过），来测量被系统标为 NSUBJ 的关系有多大比例是正确的（准确率），被系统识别出的 NSUBJ 关系与其在开发集中实际的数量之比（召回率）。我们可以使用一个矩阵来追踪每种依存关系与其他种类混淆的频率。
15.7 总结
本章介绍了依存语法与依存分析。下面是本章的重点：
在基于依存的句法中，句子的结构描述为一套词语间的二元关系。更大的成分概念并没有直接编码进依存分析中。依存结构中的关系是句子中词语间的核心词-依存词关系。依存分析提供的信息可以直接用于下游的语言处理任务，包括信息提取，语义分析和问答。基于转移的分析系统使用贪心的基于栈的算法来创建依存结构。基于图的方法是使用图论中的最大生成树方法来创建依存结构。基于转移的方法和基于图的方法都是通过受监督的机器学习技术开发的。树库提供训练系统所需的数据。依存树库可以直接通过人工标注建立，或者从短语结构树库自动转换。依存分析器的评价指标是带标签和不带标签的准确分数，通过开发集和测试集得到。
文献和历史说明
基于依存的语法比近年的短语结构或者成分语法早得多，而后者多年来一直是理论和计算语言学关注的重点。它根源于古希腊和印度的语言学。依存语法的当代理论极大地借鉴了 Tesniere(1959)的工作。影响最大的依存语法框架有 Meaning-Text Theory, 词语法（Hudson，1984），Functional Generative Description （Sgall，1986）。这些框架在很多方面有所不同，比如对形态、句法、意义、语用等有不同的程度和方式的处理，对多层表示的使用，以及对依存关系的分类等。
使用依存语法进行自动分析是被 RAND 公司的 DAVID Hays 通过机器翻译首次引入到计算语言学。依存分析的工作与成分分析的工作并驾齐驱，并且明确使用了语法来指导分析过程。之后，依存分析的计算工作在接下来的几十年中仍断断续续。在此期间，英文依存分析器的主要实现有 Link Grammar（1993）, Constraint Grammar（1995）, MINIPAR（）。
依存分析在90年代后期开始复兴，出现了大型的依存树库，以及本章介绍的数据驱动方法。Eisner(1996) 开发了一个高效的动态规划方法进行依存分析，基于来自 宾州树库的bilexical grammar。Covingto（2001）引入了基于当前转移方法的逐词确定方法。Yamada（）和kudo（2002）引入了shift-reduce范式，使用有监督的机器学习，利用支持向量机进行依存分析。
Nivre() 定义了现代的、确定的、基于转移的方法来进行依存分析。其后续的工作分析了众多转移系统的性能、训练方法、以及处理非投射性语言的方法。
基于图的最大生成树方法来自于 McDonald（）。
用于训练和评价英文分析器的最早数据来源于 WSJ 宾州树库（Marcus，1993）。与概率分析一起投入使用的查找规则，促进了自动从短语分析中提取依存分析。（xia and palmer,2001）
长期运行的布拉格依存树库项目（1998），是直接对语料库进行多层的形态、句法、语义标注的最重要工作。当前该库的容量为150万词。（）
通用依存（UD，）是一个旨在为跨语言的树库提供标注框架的项目，目标是促进全球语言的分析器开发。在这项工作之下，已经有30多种语言的树库进行了标注，并且格式统一。UD标注方案是在多个独立工作上发展而来的，包括斯坦福依存分析、谷歌通用词性标注、以及语间形态句法标注（Zeman，）。在UD框架的推动下，已经有30多种语言的大规模高质量书库建成。（Nivre，）
多年来，自然语言学习大会（CoNLL）进行了一系列有影响力的依存分析任务。近年来的评价关注分析器的鲁棒性，比如分析形态丰富的语言、非规范化的语言，如社交媒体、消息、口语。Choi（）展示了10个分析器的性能分析，使用了多个指标，以及强大的分析器评价工具 DEPENDABLE.
