统计自然语言处理-句法分析

句法分析(syntactic parsing)是自然语言处理中的关键技术之一,其基本任务是确定句子的句法结构(syntactic structure)或句子中词汇之间的依存关系。一般来说,句法分析并不是一个自然语言处理任务的最终目标,但是,它往往是实现最终目标的重要环节,甚至是关键环节。因此,在自然语言处理研究中,句法分析始终是众多专家关注的核心问题之一,围绕这一问题人们不断提出各种新的理论和方法。

句法分析分为句法结构分析(syntactic structure parsing)和依存关系分析(dependency parsing)两种。句法结构分析又可称为成分结构分析(constituent structure parsing)或短语结构分析(phrase structure parsing)。以获取整个句子的句法结构为目的的句法分析称为完全句法分析(full syntactic parsing)或者完全短语结构分析(full phrase structure parsing)(有时简称full parsing),而以获得局部成分(如基本名词短语(base NP))为目的的句法分析称为局部分析(partial parsing)或称浅层分析(shallow parsing)。依存关系分析又称依存句法分析或依存结构分析,简称依存分析。

本章首先简要介绍句法结构分析的相关内容,然后详细介绍统计句法结构分析的基本方法和几个典型的短语结构分析器(phrase structure parser),再次介绍汉语长句句法分析和浅层句法分析的相关工作,最后介绍依存关系分析方法。

句法结构分析概述

基本概念

句法结构分析是指对输入的单词序列(一般为句子)判断其构成是否合乎给定的语法,分析出合乎语法的句子的句法结构。句法结构一般用树状数据结构表示,通常称为句法分析树(syntactic parsing tree),简称分析树(parsing tree)。完成这种分析过程的程序模块称为句法结构分析器(syntactic parser),通常简称为分析器(parser)。

一般而言,句法结构分析的任务有三个:①判断输入的字符串是否属于某种语言;②消除输入句子中词法和结构等方面的歧义;③分析输入句子的内部结构,如成分构成、上下文关系等。如果一个句子有多种结构表示,句法分析器应该分析出该句子最有可能的结构。有时人们也将句法结构分析称为语言或句子识别。由于在实际应用过程中,通常系统都已经知道或者默认了被分析的句子属于哪一种语言,因此,一般不考虑任务①,而着重考虑任务②和③的处理问题。
如果有一词典已经对英语单词the,can,hold,water标注了如下词性信息:

the:art(冠词);

can:n,aux,v(n、v分别表示名词和动词,下同;aux表示助动词);

hold:v

water:n,v

给定如下句法规则:
$$
S \to NP \quad VP \\
NP \to art \quad n \\
NP \to aux \quad VP \\
VP \to v \quad NP
$$
句子The can can hold the water的分析树如图8-1所示。
句法分析树示例
在绪论中已经指出,词法歧义和结构歧义等各种类型的歧义在自然语言中普遍存在,而句法结构歧义的识别和消解是句法分析面临的主要困难。
一般来说,构造一个句法分析器需要考虑两部分工作:一部分是语法的形式化表示和词条信息描述问题。形式化的语法规则构成了规则库,词条信息(包括词性、动词的配价和中心词信息等)由词典或相关词表提供,规则库与词典或相关词表构成了句法分析的知识库;另一部分工作是分析算法的设计。

语法形式化

语法形式化(grammar formalism)属于句法理论研究的范畴。目前在自然语言处理中广泛使用的是上下文无关文法(CFG)和基于约束的文法(constraint-based grammar)的简单形式,后者又称为合一语法(unification grammar)。关于CFG,我们已经在第3章介绍有关形式语言与自动机时有过比较详细的描述,这里不再赘述。合一文法目前已经形成了在自然语言处理中被广泛采用的一种形式化表示类型。尤其是当有关研究宣称,与扩展的转移网络(augmented transition networks,ATNs)等早期框架相比,从语法工程和语法可重用性(reusability)的前景来看,基于约束的形式化方法具有更多的优越性以后,这种形式化方法得到了更广泛的应用[Samuelsson and Wiren,2000]。

常用的基于约束的语法有:

(1)功能合一语法(functional unification grammar,FUG)[Kay,1984];

(2)树链接语法(tree-adjoining grammar,TAG)[Joshi et al.,1975];

(3)词汇功能语法(lexical-functional grammar,LFG)[Bresnan,1982];

(4)广义的短语结构语法(generalized phrase structure grammar,GPSG)[Gazdar et al.,1985];

(5)中心语驱动的短语结构语法(head-driven phrase structure grammar,HPSG)[Pollard and Sag,1994]。

关于这些语法的详细介绍,有兴趣的读者可以参考相关文献。

基本方法

简单地讲,句法结构分析方法可以分为基于规则的分析方法和基于统计的分析方法两大类。基于规则的句法结构分析方法的基本思路是,由人工组织语法规则,建立语法知识库,通过条件约束和检查来实现句法结构歧义的消除[Allen,1995]。在过去的几十年里,人们先后提出了若干有影响力的句法分析算法,诸如:CYK分析算法(Cocke-Younger-Kasami parsing)[Kasami,1965;Younger,1967]、欧雷分析算法(Earley parsing)[Earley,1970]、线图分析算法(chart parsing)[Kay,1980;Allen,1995]、移进-规约算法(shift-reduction parsing)[Aho and Ullman,1972]、GLR分析算法(generalized LR parsing)[Tomita,1985]和左角分析算法(left-corner parsing) 〔1〕,等等。人们对这些算法做了大量的改进工作,并将其应用于自然语言处理的相关研究和开发任务,例如:机器翻译、树库标注等很多方面。由于国内外很多专著都对这些句法分析算法进行了详细阐述,诸如文献[Tomita,1985;1991]、[Allen,1995]、[冯志伟,1996]、[赵铁军等,2001]、[刘颖,2002]等,因此,我们不再重复介绍这些算法,有兴趣的读者可以参阅相关专著或论文。
根据句法分析树形成方向的区别,人们通常将这些分析方法划分为三种类型:自顶向下(top-down)的分析方法、自底向上(bottom-up)的分析方法和两者相结合的分析方法。自顶向下分析算法实现的是规则推导的过程,分析树从根结点开始不断生长,最后形成分析句子的叶结点。而自底向上分析算法的实现过程恰好相反,它是从句子符号串开始,执行不断归约的过程,最后形成根结点。有些方法本身是确定的,例如,CYK算法、Earley算法、移进-规约算法和GLR算法等,都属于自底向上的分析算法,而有些方法既可以采用自底向上的方法实现,也可以采用自顶向下的方法实现,如线图分析算法。当然,线图分析算法还可以实现自底向上和自顶向下相结合的分析方法[刘颖,2002]。吴安迪(1993)认为,左角分析算法是一种较好的top-down方法和bottom-up方法相结合的算法,由于这种算法既可以避免纯粹的自顶向下分析算法穷尽式扩展非终结符结点、难以充分利用输入句子中词汇提供的信息指导推导过程的弱点,也可以避免纯粹的自底向上算法盲目归约当前结点寻找父结点、有时导致“误入歧途”的不足,因而,这种方法在道理上最接近人实现句法分析的过程,最具有心理语言学价值。

基于规则的句法结构分析方法的主要优点是,分析算法可以利用手工编写的语法规则分析出输入句子所有可能的句法结构;对于特定的领域和目的,利用手工编写的有针对性的规则能够较好地处理输入句子中的部分歧义和一些超语法(extra-grammatical)现象。

但是,规则分析方法也存在一些缺陷:①对于一个中等长度的输入句子来说,要利用大覆盖度的语法规则分析出所有可能的句子结构是非常困难的,分析过程的复杂性往往使程序无法实现;②即使能够分析出句子所有可能的结构,也难以在巨大的句法分析结果集合中实现有效的消歧,并选择出最有可能的分析结果;③手工编写的规则一般带有一定的主观性,对于实际应用系统来说,往往难以覆盖大领域的所有复杂语言;④手工编写规则本身是一件大工作量的复杂劳动,而且编写的规则对特定的领域有密切的相关性,不利于句法分析系统向其他领域移植[Carroll,2000]。

Samuelsson and Wiren (2000)认为,基于规则的句法分析算法之所以能够成功地运用于计算机程序设计语言的编译器中,而面对自然语言的句法解析任务始终难以摆脱困境,其主要原因在于:一方面是形式化文法的生成能力问题。程序设计语言中使用的只是严格限制的上下文无关文法(CFG)的子类(subclass),而自然语言处理中所使用文法的表达能力更强,这种强大的表达能力在下面例句中十分明显地体现出来:

(1)Who did you give the book to _ ?

(2)Who do you think that you gave the book to _?

(3)Who do you think that he suspects that you gave the book to _?

在这三个例句中,疑问代词“who”可以作为“give”的间接宾语替换“_”位置。实际上,在句子(1)的两端之间可以嵌入任意多个描述成分,就像例句(2)和例句(3)一样,这种宾语与动词“give”的依存关系并没有距离的限制。尽管这种语言现象可以通过受限的形式化方法来描述[Gazdar et al.,1985],但实际上,许多自然语言处理系统中所使用的形式化描述方法远远超过了上下文无关文法的表达能力。这样,形式化文法过于强大的表达能力使句法分析算法面临更多复杂的可能派生的句法结构。

另一方面,在自然语言句子中存在更多、更复杂的结构歧义。在分析句子的每一步,句法分析器都可能有几种可能的候选规则和可执行的分析操作。如果歧义只存在于局部,句法分析器还可以通过简单的上下文分析对歧义进行消解,如下面的两个例句:

(1)Who has seen John?

(2)Who has John seen?

如果我们假定句法分析器按照从左到右的分析顺序执行,当句法分析算法遇到第三个词“seen”或“John”时,“Who”作直接宾语还是作主语的歧义自然就消失了。但是,如果歧义是全局的,那么歧义消解就不是一件简单的事情了。正如我们在绪论中指出的,随着英语句子中介词短语组合个数的增加,介词引起的歧义结构的复杂程度不断加深,这个组合个数即为开塔兰数(Catalan numbers)。

另外,自然语言的句法解析方法与程序设计语言的句法分析方法的区别还在于,自然语言处理中的句法分析器的先验知识的覆盖程度永远是有限的,句法分析器总是可能遇到未曾学习过的新的语言现象,而这一点对于程序设计语言来说是不可能的。人们在使用程序设计语言的时候,一切表达方式都必须服从机器的要求,是一个人服从机器的过程,这个过程是从语言的无限集到有限集的映射过程。而在自然语言处理中则恰恰相反,自然语言处理实现的是机器追踪和服从人的语言、从语言的有限集到无限集推演的过程。
M.Tomita(1991)认为,句法分析算法之所以在实际应用中常常会遇到难以克服的障碍,其实际性能离真正实用化要求还有相当的距离,其主要原因在于在语言学理论和实际的自然语言应用之间存在着巨大的差距,我们所缺少的正是弥补这个差距的桥梁,而这些桥梁就是有效的解析算法、语言知识工程、语言学理论或形式化方法的实现方法以及随机的(概率的)处理方法。

鉴于基于规则的句法分析方法存在诸多局限性,20世纪80年代中期研究者们开始探索统计句法分析方法。目前研究较多的统计句法分析方法是语法驱动的(grammar-driven),其基本思想是由生成语法(generative grammar)定义被分析的语言及其分析出的类别,在训练数据中观察到的各种语言现象的分布以统计数据的方式与语法规则一起编码。在句法分析的过程中,当遇到歧义情况时,统计数据用于对多种分析结果的排序或选择。

基于概率上下文无关文法(probabilistic (或stochastic)context-free grammar, PCFG或SCFG)的短语结构分析方法可以说是目前最成功的语法驱动的统计句法分析方法。该方法采用的模型主要包括词汇化的概率模型(lexicalized probabilistic model)和非词汇化的概率模型(unlexicalized probabilistic model)两种。表8-1列出了目前具有代表性的5个开源的短语结构分析器。
表8-1常用短语结构分析器
各句法分析器发布的网站地址为:

(1)Collins Parser:http://people.csail.mit.edu/mcollins/code.html

(2)Bikel Parser:http://www.cis.upenn.edu/~dbikel/software.html#stat-parser

(3)Charniak Parser:http://www.cs.brown.edu/people/ec/#software

(4)Berkeley Parser:http://nlp.cs.berkeley.edu/Main.html#Parsing

(5)Stanford Parser:http://nlp.stanford.edu/downloads/lex-parser.shtml

其中,Stanford Parser具备将短语结构树转换为依存关系树的功能。

在下面的几节里将对基本的基于PCFG的句法分析方法和Collins Parser、Berkeley Parser两个典型的句法分析器做详细介绍

基于PCFG的基本分析方法

PCFG

基于概率上下文无关文法的句法分析方法自20世纪80年代提出以来,受到了众多学者的关注。由于这种方法既有规则方法的特点,又运用了概率信息,因此,可以认为是规则方法与统计方法的紧密结合。尤其在最近几年,随着统计方法研究的不断升温和统计方法必须与规则方法相结合的观点得到普遍认同,基于PCFG的句法分析方法研究备受关注。
PCFG是CFG的扩展,PCFG的规则表示形式为:A→α p,其中A为非终结符,p为A推导出α的概率,即p=P(A→α),该概率分布必须满足如下条件:
$$
\sum_{\alpha}p(A \to \alpha) =1
$$
也就是说,相同左部的产生式概率分布满足归一化条件。
PCFG例子语法
PCFG例子语法树
在基于PCFG的句法分析模型中,假设满足以下三个条件:

①位置不变性(place invariance):子树的概率不依赖于该子树所管辖的单词在句子中的位置;

②上下文无关性(context-free):子树的概率不依赖于子树控制范围以外的单词;

③祖先无关性(ancestor-free):子树的概率不依赖于推导出子树的祖先结点。
于是,图8-2中两棵子树的概率分别为
$$
\begin{aligned} P\left(t_{1}\right) &=1.0 \times 0.2 \times 0.65 \times 1.0 \times 0.4 \times 0.06 \times 1.0 \times 1.0 \times 0.16 \\ &=0.0004992 \\ P\left(t_{2}\right) &=1.0 \times 0.2 \times 0.35 \times 0.65 \times 1.0 \times 0.06 \times 1.0 \times 1.0 \times 0.16 \\ &=0.0004368 \end{aligned}
$$
与HMM类似,PCFG也有三个基本问题:

①给定一个句子W=w1w2…wn和文法G,如何快速计算概率P(W|G)?

②给定一个句子W=w1w2…wn和文法G,如何选择该句子的最佳结构?即选择句法结构树t使其具有最大概率:$\arg\max_t P(t|W,G)$;

③给定PCFG G和句子W=w1w2…wn,如何调节G的概率参数,使句子的概率最大?即求解$\arg\max_{GP}(W|G)$

为了便于描述解决这三个问题的算法,我们在这里只考虑文法具有乔姆斯基范式(Chomsky normal form,CNF)的情况,即文法规则只有以下两种形式:

① A→α; α为终结符号;

② A→BC; B、C为非终结符号。

任意给定一个CFG,都可以将其转换为CNF文法。假定文法符合CNF形式并不影响下面将要介绍的算法的适用性。这些算法只作适当的修改,便可用于其他形式的上下文无关文法。

针对PCFG的三个基本问题,下面分别给出求解算法。
参考书籍第8章第2小结