8. 分析句子结构

前面的章节重点关注词:如何识别它们,分析它们的结构,分配给他们词汇类别,以及获得它们的含义。我们还看到了如何识别词序列或n-grams中的模式。然而,这些方法只触碰到支配句子的复杂约束的表面。我们需要一种方法处理自然语言中显著的歧义。我们还需要能够应对这样一个事实,句子有无限的可能,而我们只能写有限的程序来分析其结构和发现它们的含义。

本章的目的是要回答下列问题:

  1. 我们如何使用形式化语法来描述无限的句子集合的结构?
  2. 我们如何使用句法树来表示句子结构?
  3. 语法分析器如何分析一个句子并自动构建句法树?

一路上,我们将覆盖英语句法的基础,并看到句子含义有系统化的一面,只要我们确定了句子结构,将更容易捕捉。

1 一些语法困境

1.1 语言数据和无限可能性

前面的章节中已经为你讲述了如何处理和分析的文本语料库,我们一直强调处理大量的每天都在增加的电子语言数据是NLP的挑战。让我们更加细致的思考这些数据,做一个思想上的实验,我们有一个巨大的语料库,包括在过去50年中英文表达或写成的一切。我们称这个语料库为“现代英语”合理吗?有许多为什么我们的回答可能是否定的的原因。回想一下,在3中,我们让你搜索网络查找the of模式的实例。虽然很容易在网上找到包含这个词序列的例子,例如New man at the of IMG (见http://www.telegraph.co.uk/sport/2387900/New-man-at-the-of-IMG.html),说英语的人会说大多数这样的例子是错误的,因此它们根本不是英语。

因此,我们可以说,“现代英语”并不等同于我们想象中的语料库中的非常大的词序列的集合。说英语的人可以判断这些序列,并将拒绝其中一些不合语法的。

同样,组成一个新的句子,并让说话者认为它是非常好的英语是很容易的。例如,句子有一个有趣的属性,它们可以嵌入更大的句子中。考虑下面的句子:

(1)

a.Usain Bolt broke the 100m record

b.The Jamaica Observer reported that Usain Bolt broke the 100m record

c.Andre said The Jamaica Observer reported that Usain Bolt broke the 100m record

d.I think Andre said the Jamaica Observer reported that Usain Bolt broke the 100m record

如果我们用符号S表示整个句子,我们会看到像这样的模式Andre said S以及I think S。这些模板可以得到一个句子,并构建一个更大的句子。还有其他的我们可以使用的模板,如S but SS when S。稍微动点儿心思,我们就可以使用这些模板构建一些很长的句子。这里有一个令人印象深刻的例子,来自A.A. Milne 的《小熊维尼的故事》,In which Piglet is Entirely Surrounded by Water

[You can imagine Piglet's joy when at last the ship came in sight of him.] In after-years he liked to think that he had been in Very Great Danger during the Terrible Flood, but the only danger he had really been in was the last half-hour of his imprisonment, when Owl, who had just flown up, sat on a branch of his tree to comfort him, and told him a very long story about an aunt who had once laid a seagull's egg by mistake, and the story went on and on, rather like this sentence, until Piglet who was listening out of his window without much hope, went to sleep quietly and naturally, slipping slowly out of the window towards the water until he was only hanging on by his toes, at which moment, luckily, a sudden loud squawk from Owl, which was really part of the story, being what his aunt said, woke the Piglet up and just gave him time to jerk himself back into safety and say, "How interesting, and did she?" when — well, you can imagine his joy when at last he saw the good ship, Brain of Pooh (Captain, C. Robin; 1st Mate, P. Bear) coming over the sea to rescue him...

这个长句子其实结构很简单,以S but S when S开始。从这个例子我们可以看到,语言提供给我们的结构,看上去可以无限扩展句子。这也是惊人的,我们能理解我们从来没有听说过的任意长度的句子:并不难假造一个全新的句子,一个在语言的历史上可能从来没有使用过的句子,而所有说这种语言的人都能理解它。

文法的目的是给出一个明确的语言描述。而我们思考语法的方式与我们认为这是一种语言紧密联系在一起。可以观察到的言语和书面文本是否是一个大却有限的集合?具有语法的句子是否有一些更抽象的东西,如隐性知识这样的,有能力的说话者能理解的?或者是两者的某种组合?我们不会在这个问题上采取立场,而是将介绍主要的方法。

在这一章中,我们将采取“生成语法”的形式化框架,其中一种“语言”被认为是所有合乎语法的句子的巨大集合,一个语法是一个形式化符号,可用于“产生“这个集合的成员。文法使用SS and S形式的递归产生式,我们将在3探讨。10.中,我们会将其扩展到从它的组成部分的意思自动建立一个句子的意思。

1.2 普遍存在的歧义

一个众所周知的关于歧义例子如(2)所示,来自Groucho Marx的电影,Animal Crackers (1930):

(2)While hunting in Africa, I shot an elephant in my pajamas. How he got into my pajamas, I don't know.

让我们仔细看看短语中的歧义:I shot an elephant in my pajamas首先,我们需要定义一个简单的文法。

>>> groucho_grammar = nltk.CFG.fromstring("""
... S -> NP VP
... PP -> P NP
... NP -> Det N | Det N PP | 'I'
... VP -> V NP | VP PP
... Det -> 'an' | 'my'
... N -> 'elephant' | 'pajamas'
... V -> 'shot'
... P -> 'in'
... """)

这个文法允许以两种方式分析句子,取决于介词短语in my pajamas是描述大象还是枪击事件。

>>> sent = ['I', 'shot', 'an', 'elephant', 'in', 'my', 'pajamas']
>>> parser = nltk.ChartParser(groucho_grammar)
>>> for tree in parser.parse(sent):
...     print(tree)
...
(S
  (NP I)
  (VP
    (VP (V shot) (NP (Det an) (N elephant)))
    (PP (P in) (NP (Det my) (N pajamas)))))
(S
  (NP I)
  (VP
    (V shot)
    (NP (Det an) (N elephant) (PP (P in) (NP (Det my) (N pajamas))))))

程序产生两个括号括起的结构,我们可以用树来表示它们,如(3b)所示:

(3)

a.tree_images/ch08-tree-1.png

b.tree_images/ch08-tree-2.png

请注意,相关的所有词的含义是没有歧义的;例如shot不会在第一句话中表示使用枪的动作,而在第二句中表示使用相机。

注意

轮到你来:思考下面的句子,看看你是否能想出两种完全不同的解释:Fighting animals could be dangerous.Visiting relatives can be tiresome.个别词是否有歧义?如果没有,造成歧义的原因是什么?

本章介绍语法和分析,以形式化可计算的方法调查和建模我们一直在讨论的语言现象。正如我们所看到的,词序列中符合语法规则的和不符合语法规则的模式相对于短语结构和依赖是可以被理解的。我们可以开发使用语法和分析的这些结构的形式化模型。与以前一样,一个重要的动机是自然语言理解当我们能可靠地识别一个文本所包含的语言结构时,我们从中可以获得多少文本的含义?一个程序通读了一个文本,它能否足够“理解”它,来回答一些简单的关于“发生了什么事”或“谁对谁做了什么”的问题?还像以前一样,我们将开发简单的程序来处理已注释的语料库,并执行有用的任务。

2 句法的用处是什么?

2.1 超越n-grams

2.中我们给出了一个如何使用二元中的频率信息生成文本的例子,生成短的词序列看上去似乎完全可以接受,但一长就迅速退化成无稽之谈。下面是另一对例子,我们通过计算儿童故事The Adventures of Buster Brownhttp://www.gutenberg.org/files/22816/22816.txt)的文本中的bigrams:

(4)

a.He roared with me the pail slip down his back

b.The worst part and clumsy looking for whoever heard light

你凭感觉能知道,这些序列是“词沙拉”,但你可能会发现很难确定它们错在哪里。学习语法的一个好处是,它提供了一个概念框架和词汇表能拼凑出这些直觉。让我们来仔细看看序列the worst part and clumsy looking这看起来像一个并列结构,两个短语通过并列连词如andbutor连结在一起。下面是连词的词法功能的一个非正式(并且简单)的描述:

并列结构:

如果v1v2都是语法类型X的短语,那么v1v2也是X类型的短语。

这里有几个例子。首先,两个NP(名词短语)连结在一起组成一个NP,其次,两个AP(形容词短语)连结在一起组成一个AP

(5)

a.The book's ending was (NP the worst part and the best part) for me.

b.On land they are (AP slow and clumsy looking).

我们不能做的是连结一个NP和一个AP,这就是为什么the worst part and clumsy looking不合语法的原因。在我们形式化这些想法之前,我们需要了解成分结构的概念。

成分结构基于对词与其他词结合在一起形成单元的观察。一个词序列形成这样一个单元的证据是它是可替代的——也就是说,在一个符合语法规则的句子中的词序列可以被一个更小的序列替代而不会导致句子不符合语法规则。为了澄清这个想法,思考下面的句子:

(6)The little bear saw the fine fat trout in the brook.

事实上,我们可以代替HeThe little bear,这表明后者是一个单元。相比之下,我们不能以同样的方式代替little bear saw

(7)

a.He saw the fine fat trout in the brook.

b.*The he the fine fat trout in the brook.

2.1中,我们系统地用较短的序列替代较长的序列,并使其依然符合语法规则。事实上,形成一个单元的每个序列可以被一个单独的词替换,我们最终只有两个元素。

../images/ic_diagram.png

图 2.1词序列的替代:从最上面一排开始,我们替换特定的单词序列(如the brook)替换为单个词(如it);重复这一过程,我们得到符合语法规则的两个词的句子。

2.2中,我们为我们在前面的图上看到的词增加了语法类别标签。标签NPVPPP分别表示名词短语动词短语介词短语

../images/ic_diagram_labeled.png

图 2.2:词序列的替换,附加语法分类:此图再现了2.1并给名词短语(NP),动词短语(VP),介词短语(PP)以及名词性词(Nom)添加了相应的语法分类。

如果我们现在从最上面的行剥离出词汇,增加一个S节点,翻转图,最终我们得到一个标准的短语结构树,如(8)中所示。此树的每个节点(包括词)被称为一个成分S直接成分NPVP

(8)tree_images/ch08-tree-3.png

正如我们在下一节将看到的,一个指定的语法如何将句子细分成它的直接成分,以及如何将这些进一步细分,直到到达单独词汇层面。

注意

正如我们在1中所看到的,句子可以有任意的长度。因此,短语结构树可以有任意深度我们在4中看到的级联词块分析器只能产生有限深度的结构,所以词块划分方法在这里并不适用。

3 上下文无关语法

3.1 一个简单的语法

首先,让我们看一个简单的上下文无关语法。按照惯例,第一条生产式的左端是语法的开始符号,通常是S,所有符合语法规则的树都必须有这个符号作为它们的根标签。在NLTK中,上下文无关语法定义在nltk.grammar模块。3.1中,我们定义一个语法,并显示如何分析一个简单的符合语法的句子。

grammar1 = nltk.CFG.fromstring("""
  S -> NP VP
  VP -> V NP | V NP PP
  PP -> P NP
  V -> "saw" | "ate" | "walked"
  NP -> "John" | "Mary" | "Bob" | Det N | Det N PP
  Det -> "a" | "an" | "the" | "my"
  N -> "man" | "dog" | "cat" | "telescope" | "park"
  P -> "in" | "on" | "by" | "with"
  """)
>>> sent = "Mary saw Bob".split()
>>> rd_parser = nltk.RecursiveDescentParser(grammar1)
>>> for tree in rd_parser.parse(sent):
...      print(tree)
(S (NP Mary) (VP (V saw) (NP Bob)))

例 3.1 (code_cfg1.py)图 3.1:一个简单的上下文无关语法

3.1中的语法包含涉及各种句法类型的产生式,如在3.1中所列出的。

表 3.1

句法类型

符号含义示例
S句子the man walked
NP名词短语a dog
VP动词短语saw a park
PP介词短语with a telescope
Det限定词the
N名词dog
V动词walked
P介词in

产生式如VP -> V NP | V NP PP右侧脱节了,中间显示|,这是两个产生式VP -> V NPVP -> V NP PP的缩写。

../images/parse_rdparsewindow.png

图 3.2递归下降分析器演示:在这个递归下降分析器生长出解析树和它匹配输入的词时,此工具可以让你观看它的操作。

注意

轮到你来:尝试开发一个你自己的简单语法,使用递归下降解析应用程序nltk.app.rdparser(),如3.2所示。它自带一个已经加载的简单语法,但你可以随意编辑它(使用Edit菜单)。修改这个语法和将要解析的句子,然后使用autostep按钮运行这个解析器。

如果我们使用3.1显示的语法分析句子The dog saw a man in the park,我们会得到两棵树,类似与我们在(3b)中看到的:

(9)

a.tree_images/ch08-tree-4.png

b.tree_images/ch08-tree-5.png

由于这句话的两棵树都符合我们的语法规则,这句话被称为结构上有歧义这个歧义问题被称为介词短语附着歧义,正如我们在本章前面看到的。正如你可能还记得,这是一个附着歧义,因为PP in the park需要附着在树中两个位置中的一个:要么是VP的孩子(子节点)要么是NP的孩子(子节点)。PP附着在VP上,合适的解释是看到公园里发生的事情。然而,如果PP附着在NP上,意思就是在公园里的一个人,看到(狗)的主语可能已经坐在公寓的阳台上俯瞰公园。

3.2 编写你自己的文法

如果你有兴趣尝试写上下文无关语法CFG,你会发现在一个文本文件mygrammar.cfg中创建和编辑你的语法会很有帮助。然后,你可以加载它到NLTK 中,并按如下方式用它进行分析:

>>> grammar1 = nltk.data.load('file:mygrammar.cfg')
>>> sent = "Mary saw Bob".split()
>>> rd_parser = nltk.RecursiveDescentParser(grammar1)
>>> for tree in rd_parser.parse(sent):
...      print(tree)

确保你的文件名后缀为.cfg,并且字符串'file:mygrammar.cfg'中间没有空格符。如果命令print(tree)没有产生任何输出,这可能是因为你的句子sent并不符合你的语法。在这种情况下,可以将分析器的跟踪设置打开:rd_parser = nltk.RecursiveDescentParser(grammar1, trace=2)你还可以查看当前使用的语法中的产生式,使用命令for p in grammar1.productions(): print(p)

当你编写CFG在NLTK中分析时,你不能将语法类型与词汇项目一起写在同一个产生式的右侧。因此,产生式PP -> 'of' NP是不允许的。另外,你不得在产生式右侧仿制多个词的词汇项。因此,不能写成NP -> 'New York',而要写成类似NP -> 'New_York'这样的。

3.3 句法结构中的递归

一个语法被认为是递归的,如果语法类型出现在产生式左侧也出现在右侧,如3.3所示。产生式Nom -> Adj Nom(其中Nom是名词性的类别)包含Nom类型的直接递归,而S上的间接递归来自于两个产生式的组合S -> NP VPVP -> V S

grammar2 = nltk.CFG.fromstring("""
  S  -> NP VP
  NP -> Det Nom | PropN
  Nom -> Adj Nom | N
  VP -> V Adj | V NP | V S | V NP PP
  PP -> P NP
  PropN -> 'Buster' | 'Chatterer' | 'Joe'
  Det -> 'the' | 'a'
  N -> 'bear' | 'squirrel' | 'tree' | 'fish' | 'log'
  Adj  -> 'angry' | 'frightened' |  'little' | 'tall'
  V ->  'chased'  | 'saw' | 'said' | 'thought' | 'was' | 'put'
  P -> 'on'
  """)

例 3.3 (code_cfg2.py)图 3.3:一个递归的上下文无关语法

要看递归如何从这个语法产生,思考下面的树。(10a)包括嵌套的名词短语,而(10b)包含嵌套的句子。

(10)

a.tree_images/ch08-tree-6.png

b.tree_images/ch08-tree-7.png

我们在这里只演示了两个层次的递归,递归深度是没有限制的。你可以尝试分析更深层次嵌套结构的句子。请注意,RecursiveDescentParser是无法处理形如X -> X Y左递归产生式;我们将在4谈及这个。

4 上下文无关语法分析

分析器根据语法产生式处理输入的句子,并建立一个或多个符合语法的组成结构。语法是一个格式良好的声明规范——它实际上只是一个字符串,而不是程序。分析器是语法的解释程序。它搜索符合语法的所有树的空间找出一棵边缘有所需句子的树。

分析器允许使用一组测试句子评估一个语法,帮助语言学家发现在他们的语法分析中存在的错误。分析器可以作为心理语言处理模型,帮助解释人类处理某些句法结构的困难。许多自然语言应用程序都在某种程度涉及语法分析;例如:我们会期望自然语言问答系统对提交的问题首先进行语法分析。

在本节中,我们将看到两个简单的分析算法,一种自上而下的方法称为递归下降分析,一种自下而上的方法称为移进-归约分析。我们也将看到一些更复杂的算法,一种带自下而上过滤的自上而下的方法称为左角落分析;一种动态规划技术称为图表分析。

4.1 递归下降分析

一种最简单的分析器将一个语法作为如何将一个高层次的目标分解成几个低层次的子目标的规范来解释。顶层的目标是找到一个SSNP VP生产式允许分析器替换这个目标为两个子目标:找到一个NP,然后找到一个VP每个这些子目标都可以再次被子目标的子目标替代,使用左侧有NPVP的产生式。最终,这种扩张过程达到子目标,如:找到词telescope这样的子目标可以直接与输入序列比较,如果下一个单词匹配就取得成功。如果没有匹配,分析器必须备份,并尝试其它选择。

递归下降分析器在上述过程中建立分析树。带着最初的目标(找到一个S),创建S根节点。随着上述过程使用文法的产生式递归扩展,分析树不断向下延伸(故名为递归下降)。我们可以在图形化示范nltk.app.rdparser()中看到这个过程。执行此分析器的六个阶段,如4.1所示。

../images/rdparser1-6.png

图 4.1:递归下降分析器的六个阶段:分析器以一颗包含节点S的树开始;每个阶段它会查询文法来找到一个可以用于扩大树的产生式;当遇到一个词汇产生式时,将它的词与输入比较;发现一个完整的分析树后,分析器会回溯寻找更多的分析树。

在这个过程中,分析器往往被迫在多种可能的产生式中选择。例如,从第3步到第4步,它试图找到左侧有N的产生式。第一个是Nman当这不起作用时就回溯,按顺序尝试其他左侧有N的产生式,直到它得到Ndog,与输入句子中的下一个词相匹配。一段时间以后,如第5步所示,它发现了一个完整的分析树。这是一个涵盖了整个句子的树,没有任何悬着的边。发现了分析树后我们可以让分析器寻找其它额外的分析树。它会再次回溯和探索选择其它产生式,以免漏掉任何一个产生分析树的情况。

NLTK提供一个递归下降分析器:

>>> rd_parser = nltk.RecursiveDescentParser(grammar1)
>>> sent = 'Mary saw a dog'.split()
>>> for tree in rd_parser.parse(sent):
...     print(tree)
(S (NP Mary) (VP (V saw) (NP (Det a) (N dog))))

注意

RecursiveDescentParser()接受一个可选的参数trace如果trace大于零,则分析器将报告它解析一个文本的步骤。

递归下降分析有三个主要的缺点。首先,左递归产生式,如NP -> NP PP会进入死循环。第二,分析器浪费了很多时间处理不符合输入句子的词和结构。第三,回溯过程中可能会丢弃分析过的成分,它们将需要在之后再次重建。例如,从VP -> V NP上回溯将放弃为NP创建的子树。如果分析器之后处理VP -> V NP PP,那么NP子树必须重新创建。

递归下降分析是一种自上而下分析自上而下分析器在检查输入之前先使用文法预测输入将是什么!然而,由于输入对分析器一直是可用的,从一开始就考虑输入的句子会是更明智的做法。这种方法被称为自下而上分析,在下一节中我们将看到一个例子。

4.2 移进-归约分析

一种简单的自下而上分析器是移进-归约分析器与所有自下而上的分析器一样,移进-归约分析器尝试找到对应文法生产式右侧的词和短语的序列,用左侧的替换它们,直到整个句子归约为一个S

移位-规约分析器反复将下一个输入词推到堆栈(4.1);这是移位操作。如果堆栈上的前n项,匹配一些产生式的右侧的n个项目,那么就把它们弹出栈,并把产生式左边的项目压入栈。这种替换前n项为一项的操作就是规约操作。此操作只适用于堆栈的顶部;规约栈中的项目必须在后面的项目被压入栈之前做。当所有的输入都使用过,堆栈中只剩余一个项目,也就是一颗分析树作为它的根的S节点时,分析器完成。移位-规约分析器通过上述过程建立一颗分析树。每次弹出堆栈n个项目,它就将它们组合成部分的分析树,然后将这压回推栈。我们可以使用图形化示范nltk.app.srparser()看到移位-规约分析算法步骤。执行此分析器的六个阶段,如4.2所示。

../images/srparser1-6.png

图 4.2:移进-归约分析器的六个阶段:分析器一开始把输入的第一个词转移到堆栈;一旦堆栈顶端的项目与一个文法产生式的右侧匹配,就可以将它们用那个产生式的左侧替换;当所有输入都被使用过且堆栈中只有剩余一个项目S时,分析成功。

NLTK中提供ShiftReduceParser(),移进-归约分析器的一个简单的实现。这个分析器不执行任何回溯,所以它不能保证一定能找到一个文本的解析,即使确实存在一个这样的解析。此外,它最多只会找到一个解析,即使有多个解析存在。我们可以提供一个可选的trace参数,控制分析器报告它分析一个文本的步骤的繁琐程度。

>>> sr_parser = nltk.ShiftReduceParser(grammar1)
>>> sent = 'Mary saw a dog'.split()
>>> for tree in sr_parser.parse(sent):
...     print(tree)
  (S (NP Mary) (VP (V saw) (NP (Det a) (N dog))))

注意

轮到你来: 以跟踪模式运行上述分析器,看看序列的移进和规约操作,使用sr_parse = nltk.ShiftReduceParser(grammar1, trace=2)

移进-规约分析器可能会到达一个死胡同,而不能找到任何解析,即使输入的句子是符合语法的。这种情况发生时,没有剩余的输入,而堆栈包含不能被规约到一个S的项目。问题出现的原因是较早前做出的选择不能被分析器撤销(虽然图形演示中用户可以撤消它们的选择)。分析器可以做两种选择:(a)当有多种规约可能时选择哪个规约(b)当移进和规约都可以时选择哪个动作。

移进-规约分析器可以改进执行策略来解决这些冲突。例如,它可以通过只有在不能规约时才移进,解决移进-规约冲突;它可以通过优先执行规约操作,解决规约-规约冲突;它可以从堆栈移除更多的项目。(一个通用的移进-规约分析器,是一个“超前LR 分析器”,普遍使用在编程语言编译器中。)

移进-规约分析器相比递归下降分析器的好处是,它们只建立与输入中的词对应的结构。此外,每个结构它们只建立一次,例如NP(Det(the), N(man))只建立和压入栈一次,不管以后VP -> V NP PP规约或者NP -> NP PP规约会不会用到。

4.3 左角落分析器

递归下降分析器的问题之一是当它遇到一个左递归产生式时,会进入无限循环。这是因为它盲目应用文法产生式而不考虑实际输入的句子。左角落分析器是我们已经看到的自下而上与自上而下方法的混合体。

语法grammar1允许我们对John saw Mary生成下面的分析:

(11)tree_images/ch08-tree-8.png

回忆一下,语法(在3.3中定义)具有以下生成式用于扩展NP

(12)

a.NP -> Det N

b.NP -> Det N PP

c.NP -> "John" | "Mary" | "Bob"

假设我们让你先看树(11),然后决定哪一个NP生成式是你想首先应用的递归下降分析器——很明显,(12c)是正确的选择!你如何知道应用(12a)(12b)将是毫无意义的?因为这两个生成式都不会得到第一个单词为John的序列。也就是说,我们很容易得出一个成功的John saw Mary解析中,分析器必须扩展NP的方式是NP得到序列John α。更概括地讲,我们说B类别是以A if A ⇒* B α为根的树的左角落

(13)tree_images/ch08-tree-9.png

左角落分析器是一个带自下而上过滤的自上而下的分析器。不像普通的递归下降分析器,它不会陷入左递归产生式的陷井。在开始工作之前,左角落分析器预处理上下文无关语法建立一个表,其中每行包含两个单元,第一个存放非终结符,第二个存放那个非终结符可能的左角落的集合。4.1根据grammar2的文法演示了这一点。

表 4.1

grammar2中的左角落

类别左角落(终结符之前)
SNP
NPDet, PropN
VPV
PPP

分析器每次考虑产生式时,它会检查下一个输入词是否与左角落表格中至少一种非终结符的类别相容。

4.4 符合语句规则的子串表

上面讨论的简单的分析器在完整性和效率上都有限制。为了弥补这些,我们将运用动态规划算法设计技术分析问题。正如我们在4.7中所看到的,动态规划存储中间结果,并在适当的时候重用它们,能显著提高效率。这种技术可以应用到句法分析,使我们能够存储分析任务的部分解决方案,然后在必要的时候查找它们,直到达到最终解决方案。这种分析方法被称为图表分析我们在本节中介绍它的主要思想;更多的实施细节请看网上提供的本章的材料。

动态规划使我们能够只建立一次PP in my pajamas第一次我们建立时就把它存入一个表格中,然后在我们需要作为对象NP或更高的VP的组成部分用到它时我们就查找表格。这个表格被称为符合语法规则的子串表或简称为WFST。(术语“子串”指一个句子中的连续的词序列。)我们将展示如何自下而上的构建WFST,以便系统地记录已经找到的句法成分。

让我们设置我们的输入为句子(2)指定WFST的跨度的数值让人联想起Python的分片符号(3.2)。这种数据结构的另一种方式如4.3所示,一个称为图表的数据结构。

../images/chart_positions1.png

图 4.3:图表数据结构:词是线性图结构的边上的标签。

在WFST中,我们通过填充三角矩阵中的单元记录词的位置:纵轴表示一个子串的起始位置,而横轴表示结束位置(从而shot将出现在坐标(1, 2)的单元中)。为了简化这个演示,我们将假定每个词有一个独特的词汇类别,我们将在矩阵中存储词汇类别(不是词)。所以单元(1, 2)将包含条目V。更一般的,如果我们输入的字符串是a0a1 ... an,我们的文法包含一个形为Aai的产生式,那么我们把A添加到单元(i, `i`+1)。

System Message: WARNING/2 (ch08.rst2, line 900); backlink

Inline interpreted text or phrase reference start-string without end-string.

所以,对于text中的每个词,我们可以在我们的语法中查找它所属的类别。

>>> text = ['I', 'shot', 'an', 'elephant', 'in', 'my', 'pajamas']
>>> groucho_grammar.productions(rhs=text[1])
[V -> 'shot']

对于我们的WFST,我们用Python中的列表的咧表创建一个(n-1) × (n-1)的矩阵,在4.4中的函数init_wfst()中用每个标识符的词汇类型初始化它。我们还定义一个实用的函数display()来为我们精美的输出WFST。正如预期的那样,V在(1, 2)单元中。

def init_wfst(tokens, grammar):
    numtokens = len(tokens)
    wfst = [[None for i in range(numtokens+1)] for j in range(numtokens+1)]
    for i in range(numtokens):
        productions = grammar.productions(rhs=tokens[i])
        wfst[i][i+1] = productions[0].lhs()
    return wfst

def complete_wfst(wfst, tokens, grammar, trace=False):
    index = dict((p.rhs(), p.lhs()) for p in grammar.productions())
    numtokens = len(tokens)
    for span in range(2, numtokens+1):
        for start in range(numtokens+1-span):
            end = start + span
            for mid in range(start+1, end):
                nt1, nt2 = wfst[start][mid], wfst[mid][end]
                if nt1 and nt2 and (nt1,nt2) in index:
                    wfst[start][end] = index[(nt1,nt2)]
                    if trace:
                        print("[%s] %3s [%s] %3s [%s] ==> [%s] %3s [%s]" % \
                        (start, nt1, mid, nt2, end, start, index[(nt1,nt2)], end))
    return wfst

def display(wfst, tokens):
    print('\nWFST ' + ' '.join(("%-4d" % i) for i in range(1, len(wfst))))
    for i in range(len(wfst)-1):
        print("%d   " % i, end=" ")
        for j in range(1, len(wfst)):
            print("%-4s" % (wfst[i][j] or '.'), end=" ")
        print()
>>> tokens = "I shot an elephant in my pajamas".split()
>>> wfst0 = init_wfst(tokens, groucho_grammar)
>>> display(wfst0, tokens)
WFST 1    2    3    4    5    6    7
0    NP   .    .    .    .    .    .
1    .    V    .    .    .    .    .
2    .    .    Det  .    .    .    .
3    .    .    .    N    .    .    .
4    .    .    .    .    P    .    .
5    .    .    .    .    .    Det  .
6    .    .    .    .    .    .    N
>>> wfst1 = complete_wfst(wfst0, tokens, groucho_grammar)
>>> display(wfst1, tokens)
WFST 1    2    3    4    5    6    7
0    NP   .    .    S    .    .    S
1    .    V    .    VP   .    .    VP
2    .    .    Det  NP   .    .    .
3    .    .    .    N    .    .    .
4    .    .    .    .    P    .    PP
5    .    .    .    .    .    Det  NP
6    .    .    .    .    .    .    N

例 4.4 (code_wfst.py)图 4.4:使用符合语句规则的子串表的接收器

回到我们的表格表示,假设对于词an我们有Det在(2, 3)单元,对以词elephantN在(3, 4)单元,对于an elephant我们应该在(2, 4)放入什么?我们需要找到一个形如ADet N的产生式。查询了文法,我们知道我们可以输入(0, 2)单元的NP

更一般的,我们可以在(i, j)输入A,如果有一个产生式AB C,并且我们在(i, k)中找到非终结符B,在(k, j)中找到非终结符C4.4中的程序使用此规则完成WFST。通过调用函数complete_wfst()时设置 traceTrue,我们看到了显示WFST正在被创建的跟踪输出:

>>> wfst1 = complete_wfst(wfst0, tokens, groucho_grammar, trace=True)
[2] Det [3]   N [4] ==> [2]  NP [4]
[5] Det [6]   N [7] ==> [5]  NP [7]
[1]   V [2]  NP [4] ==> [1]  VP [4]
[4]   P [5]  NP [7] ==> [4]  PP [7]
[0]  NP [1]  VP [4] ==> [0]   S [4]
[1]  VP [4]  PP [7] ==> [1]  VP [7]
[0]  NP [1]  VP [7] ==> [0]   S [7]

例如,由于我们在wfst[2][3]找到Det,在wfst[3][4]找到N,我们可以添加NPwfst[2][4]

注意

为了帮助我们更简便地通过产生式的右侧检索产生式,我们为语法创建一个索引。这是空间-时间权衡的一个例子:我们对语法做反向查找,每次我们想要通过右侧查找产生式时不必遍历整个产生式列表。

../images/chart_positions2.png

图 4.5:图数据结构:图中额外的边表示非终结符。

我们得出结论,只要我们已经在(0, 7)单元构建了一个S节点,表明我们已经找到了一个涵盖了整个输入的句子,我们就为整个输入字符串找到了一个解析。最后的WFST状态如4.5所示。

请注意,在这里我们没有使用任何内置的分析函数。我们已经从零开始实现了一个完整的初级图表分析器!

WFST有几个缺点。首先,正如你可以看到的,WFST本身不是一个分析树,所以该技术严格地说是认识到一个句子被一个语法承认,而不是分析它。其次,它要求每个非词汇语法生产式是二元的虽然可以将任意的CFG转换为这种形式,我们宁愿使用这种方法时没有这样的规定。第三,作为一个自下而上的语法,它潜在的存在浪费,它会在不符合文法的地方提出成分。

最后,WFST并不能表示句子中的结构歧义(如两个动词短语的读取)。(1, 7)单元中的VP实际上被输入了两次,一次是读取V NP,一次是读取VP PP这是不同的假设,第二个会覆盖第一个(虽然如此,这并不重要,因为左侧是相同的。)图表分析器使用稍微更丰富的数据结构和一些有趣的算法来解决这些问题(详细情况参见本章末尾的进一步阅读一节)。

注意

轮到你来:尝试交互式图表分析器应用程序nltk.app.chartparser()

5 依存关系和依存文法

短语结构文法是关于词和词序列如何结合起来形成句子成分的。一个独特的和互补的方式,依存语法,集中关注的是词与其他词之间的关系依存关系是一个中心词与它的依赖之间的二元对称关系。一个句子的中心词通常是动词,所有其他词要么依赖于中心词,要么依赖路径与它联通。

一个句子的中心词通常是动词,所有其他词要么依赖于中心词,要么依赖路径与它联通。5.1显示一个依存关系图,箭头从中心词指出它们的依赖。

../images/depgraph0.png

图 5.1:依存结构:箭头从中心词指向它们的依赖;标签表示依赖的语法功能如:主语、宾语或修饰语。

5.1中的弧加了依赖与它的中心词之间的语法功能标签。例如,Ishot(这是整个句子的中心词)的SBJ(主语),in是一个NMODelephant的名词修饰语)。与短语结构语法相比,依存语法可以作为一种依存关系直接用来表示语法功能。

下面是NLTK为依存语法编码的一种方式——注意它只能捕捉依存关系信息,不能指定依存关系类型:

>>> groucho_dep_grammar = nltk.DependencyGrammar.fromstring("""
... 'shot' -> 'I' | 'elephant' | 'in'
... 'elephant' -> 'an' | 'in'
... 'in' -> 'pajamas'
... 'pajamas' -> 'my'
... """)
>>> print(groucho_dep_grammar)
Dependency grammar with 7 productions
  'shot' -> 'I'
  'shot' -> 'elephant'
  'shot' -> 'in'
  'elephant' -> 'an'
  'elephant' -> 'in'
  'in' -> 'pajamas'
  'pajamas' -> 'my'

依存关系图是一个投影,当所有的词都按线性顺序书写,边可以在词上绘制而不会交叉。这等于是说一个词及其所有后代依赖(依赖及其依赖的依赖,等等)在句子中形成一个连续的词序列。5.1是一个投影,我们可以使用投影依存关系分析器分析很多英语句子。下面的例子演示groucho_dep_grammar如何提供了一种替代的方法来捕捉附着歧义,我们之前在研究短语结构语法中遇到的。

>>> pdp = nltk.ProjectiveDependencyParser(groucho_dep_grammar)
>>> sent = 'I shot an elephant in my pajamas'.split()
>>> trees = pdp.parse(sent)
>>> for tree in trees:
...     print(tree)
(shot I (elephant an (in (pajamas my))))
(shot I (elephant an) (in (pajamas my)))

这些括号括起来的依存关系结构也可以显示为树,依赖被作为它们的中心词的孩子。

(14)tree_images/ch08-tree-10.pngtree_images/ch08-tree-11.png

在比英语具有更多灵活的词序的语言中,非投影的依存关系也更常见。

在一个成分C中决定哪个是中心词H,哪个是依赖D,已经提出了很多不同的标准。最重要的有以下几种:

  1. H决定类型C的分布;或者,C的外部句法属性取决于H
  2. H定义C的语义类型。
  3. H必须有,而D是可选的。
  4. H选择D并且决定它是必须有的还是可选的。
  5. D的形态由H决定(如agreement或case government)。

当我们在一个短语结构文法中说一个PP的直接成分是PNP时,我们隐含了中心词/依赖之间的区别。介词短语是一个短语,它的中心词是一个介词;此外,NPP的依赖。同样的区别在我们已经讨论过的其它类型的短语结构语法中也存在。这里要注意的关键点是,虽然短语结构语法看上去似乎与依存关系语法非常不同,它们隐含着依存关系。虽然CFG 会直接捕获依存关系,最近的语言框架已越来越多地采用这两种方法的结合的形式。

5.1 配价与词汇

让我们来仔细看看动词和它们的依赖。3.3中的语法正确生成了类似(15d)的例子。

(15)

a.The squirrel was frightened.

b.Chatterer saw the bear.

c.Chatterer thought Buster was angry.

d.Joe put the fish on the log.

这些句子对应下面的产生式:

表 5.1

VP 产生式和它们的中心词汇

VP -> V Adjwas
VP -> V NPsaw
VP -> V Sthought
VP -> V NP PPput

也就是说,was可以与跟在其后的形容词一起出现,saw可以与跟在其后的NP一起出现,thought可以与跟在其后的S一起出现,put可以与跟在其后的NPPP一起出现。依赖Adj, NP, PPS通常被称为各自动词的补语,什么动词可以和什么补语一起出现具有很强的约束。对比(15d)(16d)中的词序列是不符合语法规则的:

(16)

a.*The squirrel was Buster was angry.

b.*Chatterer saw frightened.

c.*Chatterer thought the bear.

d.*Joe put on the log.

注意

稍微用点儿想象力就可以设计一个上下文,在那里动词和补语的不寻常的组合可以解释的通。然而,我们假设上面的例子在中性语境是可以解释的。

在依存文法的传统中,在5.1中的动词被认为具有不同的配价配价限制不仅适用于动词,也适用于其他类的中心词。

基于短语结构语法的框架内,已经提出了各种技术排除(16d)中不合语法的例子。在CFG中,我们需要一些限制语法产生式的方式,使得扩展了VP后动词与它们正确的补一同出现。我们可以通过将动词划分成更多“子类别”做到这个,每个子类别与一组不同的补语关联。例如,及物动词,如chasedsaw,需要后面跟NP对象补语;它们是NP大类别的子类别如果我们为及物动词引入一个新的类别标签,叫做TV(Transitive Verb),那么我们可以在下面的产生式中使用它:

VP -> TV NP
TV -> 'chased' | 'saw'

现在*Joe thought the bear被排除了,因为我们没有列出thought是一个TV,但Chatterer saw the bear仍然是允许的。5.2提供了更多动词子类别标签的例子。

表 5.2

动词子类别

符号含义示例
IVintransitive verbbarked
TVtransitive verbsaw a man
DatVdative verbgave a dog to a man
SVsentential verbsaid that a dog barked

配价是一个词项的属性,我们将在9.进一步讨论它。

补语往往与修饰语对照,虽然两者都是依存关系的类别。介词短语、形容词和副词通常充当修饰语。与补充不同修饰语是可选的,经常可以进行迭代,不会像补语那样被中心词选择。例如,副词really在所有(17d)中的句子中都可以被添加为修饰语:

(17)

a.The squirrel really was frightened.

b.Chatterer really saw the bear.

c.Chatterer really thought Buster was angry.

d.Joe really put the fish on the log.

PP附着的结构歧义,我们已经在短语结构和依存文法中说过了,语义上对应修饰语的范围上的模糊。

5.2 扩大规模

到目前为止,我们只考虑了“玩具语法”,演示分析的关键环节的少量的语法。但有一个明显的问题就是这种做法是否可以扩大到覆盖自然语言的大型语料库。手工构建这样的一套产生式有多么困难?一般情况下,答案是:非常困难即使我们允许自己使用各种形式化的工具,它们可以提供语法产生式更简洁的表示,保持对覆盖一种语言的主要成分所需要的众多产生式之间的复杂的相互作用的控制,仍然是极其困难的。换句话说,很难将语法模块化,每部分语法可以独立开发。反过来这意味着,在一个语言学家团队中分配编写语法的任务是很困难的。另一个困难是当语法扩展到包括更加广泛的成分时,适用于任何一个句子的分析的数量也相应增加。换句话说,歧义随着覆盖而增加。

尽管存在这些问题,一些大的合作项目在为几种语言开发基于规则的语法上已取得了积极的和令人印象深刻的结果。例如,词汇功能语法(LFG)Pargram 项目、中心词驱动短语结构文法(HPSG)LinGO 矩阵框架和词汇化树邻接语法XTAG项目。

6 语法开发

分析器根据短语结构语法在句子上建立树。现在,我们上面给出的所有例子只涉及玩具语法包含少数的产生式。如果我们尝试扩大这种方法的规模来处理现实的语言语料库会发生什么?在本节中,我们将看到如何访问树库,并看看开发广泛覆盖的语法的挑战。

6.1 树库和语法

corpus模块定义了treebank语料的阅读器,其中包含了宾州树库语料的10%的样本。

>>> from nltk.corpus import treebank
>>> t = treebank.parsed_sents('wsj_0001.mrg')[0]
>>> print(t)
(S
  (NP-SBJ
    (NP (NNP Pierre) (NNP Vinken))
    (, ,)
    (ADJP (NP (CD 61) (NNS years)) (JJ old))
    (, ,))
  (VP
    (MD will)
    (VP
      (VB join)
      (NP (DT the) (NN board))
      (PP-CLR
        (IN as)
        (NP (DT a) (JJ nonexecutive) (NN director)))
      (NP-TMP (NNP Nov.) (CD 29))))
  (. .))

我们可以利用这些数据来帮助开发一个语法。例如,6.1中的程序使用一个简单的过滤器找出带句子补语的动词。假设我们已经有一个形如VP -> Vs S的产生式,这个信息使我们能够识别那些包括在Vs的扩张中的特别的动词。

def filter(tree):
    child_nodes = [child.label() for child in tree
                   if isinstance(child, nltk.Tree)]
    return  (tree.label() == 'VP') and ('S' in child_nodes)
>>> from nltk.corpus import treebank
>>> [subtree for tree in treebank.parsed_sents()
...          for subtree in tree.subtrees(filter)]
 [Tree('VP', [Tree('VBN', ['named']), Tree('S', [Tree('NP-SBJ', ...]), ...]), ...]

例 6.1 (code_sentential_complement.py)图 6.1:搜索树库找出句子的补语

PP附着语料库nltk.corpus.ppattach是另一个有关特别动词配价的信息源。在这里,我们演示挖掘这个语料库的技术。它找出具有固定的介词和名词的介词短语对,其中介词短语附着到VP还是NP,由选择的动词决定。

>>> from collections import defaultdict
>>> entries = nltk.corpus.ppattach.attachments('training')
>>> table = defaultdict(lambda: defaultdict(set))
>>> for entry in entries:
...     key = entry.noun1 + '-' + entry.prep + '-' + entry.noun2
...     table[key][entry.attachment].add(entry.verb)
...
>>> for key in sorted(table):
...     if len(table[key]) > 1:
...         print(key, 'N:', sorted(table[key]['N']), 'V:', sorted(table[key]['V']))

这个程序的输出行中我们发现offer-from-group N: ['rejected'] V: ['received'],这表示received期望一个单独的PP附着到VPrejected不是的。和以前一样,我们可以使用此信息来帮助构建语法。

NLTK语料库收集了来自PE08跨框架跨领域分析器评估共享任务的数据。一个更大的文法集合已准备好用于比较不同的分析器,它可以通过下载large_grammars包获得(如python -m nltk.downloader large_grammars)。

NLTK语料库也收集了中央研究院树库语料,包括10,000句已分析的句子,来自现代汉语中央研究院平衡语料库让我们加载并显示这个语料库中的一棵树。

>>> nltk.corpus.sinica_treebank.parsed_sents()[3450].draw()               
../images/sinica-tree.png

6.2 有害的歧义

不幸的是,随着文法覆盖范围的增加和输入句子长度的增长,分析树的数量也迅速增长。事实上,它以天文数字的速度增长。

让我们在一个简单的例子帮助下来探讨这个问题。fish既是名词又是动词。我们可以造这样的句子fish fish fish,意思是fish like to fish for other fish(用police尝试一下,如果你喜欢更有意思的东西。)下面是“fish”句子的玩具文法。

>>> grammar = nltk.CFG.fromstring("""
... S -> NP V NP
... NP -> NP Sbar
... Sbar -> NP V
... NP -> 'fish'
... V -> 'fish'
... """)

现在,我们可以尝试分析一个较长的句子,fish fish fish fish fish,其中一个意思是:“fish that other fish fish are in the habit of fishing fish themselves”。我们使用NLTK的图表分析器,它在本章前面介绍过。这句话有两种读法。

>>> tokens = ["fish"] * 5
>>> cp = nltk.ChartParser(grammar)
>>> for tree in cp.parse(tokens):
...     print(tree)
(S (NP fish) (V fish) (NP (NP fish) (Sbar (NP fish) (V fish))))
(S (NP (NP fish) (Sbar (NP fish) (V fish))) (V fish) (NP fish))

随着句子长度增加到(3,5,7,...),我们得到的分析树的数量是:1; 2; 5; 14; 42; 132; 429; 1,430; 4,862; 16,796; 58,786; 208,012; ….(这是Catalan数,我们在4的练习中见过)。最后一个是句子长度为23的分析树的数目,这是宾州树库WSJ部分的句子的平均长度。对于一个长度为50的句子有超过1012的解析,这只是Piglet 句子长度的一半(1),这些句子小孩可以毫不费力的处理。没有实际的自然语言处理系统可以为一个句子构建数以百万计的树,并根据上下文选择一个合适的。很显然,人也不会这样做!

请注意,这个问题不是只在我们选择的例子中存在。(Church & Patil, 1982)指出PP附着句法歧义在像(18)这样的句子中也是按Catalan数的比例增长。

(18)Put the block in the box on the table.

这么多的结构歧义;词汇歧义又如何?只要我们试图建立一个广泛覆盖的语法,我们就被迫使词汇条目对它们的词性高度含糊。在玩具语法中,a只是一个限定词,dog只是一个名词,而runs只是一个动词。然而,在覆盖广泛的文法中,a也是一个名词(如part a),dog 也是一个动词(意思是密切跟踪),而runs也是一个名词(如ski runs)。事实上,所有的词都可以作为名字被提及:例如the verb 'ate' is spelled with three letters;在讲话中,我们不需要使用引号。此外,大多数名词都可以动词化因此,一个覆盖广泛的文法分析器将对歧义不堪重负。即使是完全的胡言乱语往往也是符合语法的,例如the a are of I正如(Klavans & Resnik, 1996)已经指出的,这不是一个“词沙拉”而是一个符号语法的名词短语,其中are是个名词,意思是一公顷(或100 平方米)的百分之一,而aI是名词指定坐标,如6.2所示。

../images/are.png

图 6.2:"The a are of I":27 个围场的示意图,每一个的大小是一个are,并用坐标确定;左上角的单元格是the a "are" of column I(after Abney)。

即使这句话是不可能的,它仍是符合语法的,广泛覆盖的分析器应该能够为它建造一个分析树。同样,看上去没有歧义的句子,例如John saw Mary,结果却有我们没有想到的其它的读法(正如Abney 解释的)。这种歧义是不可避免的,导致在分析看似平淡无奇的句子时可怕的低效。概率分析提供了解决这些问题的方法,它使我们能够以来自语料库的证据为基础对歧义句的解析进行排名

6.3 加权语法

正如我们刚才看到的,处理歧义是开发广泛覆盖的分析器的主要挑战。图表分析器提高了计算一个句子的多个分析的效率,但它们仍然因可能的分析的数量过多而不堪重负。加权语法和概率分析算法为这些问题提供了一个有效的解决方案。

在讲这些之前,我们需要理解为什么符合语法的概念可能是有倾向性的思考动词give这个动词既需要一个直接宾语(被给予的东西)也需要一个间接宾语(收件人)。这些补语可以按任何顺序出现,如(19)所示。在“介词格”的形式(19a)中,直接宾语先出现,然后是包含间接宾语单独介词短语。

(19)

a.Kim gave a bone to the dog

b.Kim gave the dog a bone

在“双宾语”的形式(19b)中,间接宾语先出现,然后是直接宾语。在这种情况下,两种顺序都是可以接受的。然而,如果间接宾语是代词,人们强烈偏好双宾语结构:

(20)

a.Kim gives the heebie-jeebies to me (*prepositional dative)

b.Kim gives me the heebie-jeebies (double object)

使用宾州树库样本,我们可以检查包含give的所有介词格和双宾语结构的实例,如6.3所示。

def give(t):
    return t.label() == 'VP' and len(t) > 2 and t[1].label() == 'NP'\
           and (t[2].label() == 'PP-DTV' or t[2].label() == 'NP')\
           and ('give' in t[0].leaves() or 'gave' in t[0].leaves())
def sent(t):
    return ' '.join(token for token in t.leaves() if token[0] not in '*-0')
def print_node(t, width):
        output = "%s %s: %s / %s: %s" %\
            (sent(t[0]), t[1].label(), sent(t[1]), t[2].label(), sent(t[2]))
        if len(output) > width:
            output = output[:width] + "..."
        print(output)
>>> for tree in nltk.corpus.treebank.parsed_sents():
...     for t in tree.subtrees(give):
...         print_node(t, 72)
gave NP: the chefs / NP: a standing ovation
give NP: advertisers / NP: discounts for maintaining or increasing ad sp...
give NP: it / PP-DTV: to the politicians
gave NP: them / NP: similar help
give NP: them / NP:
give NP: only French history questions / PP-DTV: to students in a Europe...
give NP: federal judges / NP: a raise
give NP: consumers / NP: the straight scoop on the U.S. waste crisis
gave NP: Mitsui / NP: access to a high-tech medical product
give NP: Mitsubishi / NP: a window on the U.S. glass industry
give NP: much thought / PP-DTV: to the rates she was receiving , nor to ...
give NP: your Foster Savings Institution / NP: the gift of hope and free...
give NP: market operators / NP: the authority to suspend trading in futu...
gave NP: quick approval / PP-DTV: to $ 3.18 billion in supplemental appr...
give NP: the Transportation Department / NP: up to 50 days to review any...
give NP: the president / NP: such power
give NP: me / NP: the heebie-jeebies
give NP: holders / NP: the right , but not the obligation , to buy a cal...
gave NP: Mr. Thomas / NP: only a `` qualified '' rating , rather than ``...
give NP: the president / NP: line-item veto power

例 6.3 (code_give.py)图 6.3:宾州树库样本中Give和Gave的用法

我们可以观察到一种强烈的倾向就是最短的补语最先出现。然而,这并没有解释类似give NP: federal judges / NP: a raise的形式,其中有生性起了重要作用。事实上,根据(Bresnan & Hay, 2006)的调查,存在大量的影响因素。这些偏好可以用加权语法来表示。

概率上下文无关语法(或PCFG)是一种上下文无关语法,它的每一个产生式关联一个概率。它会产生与相应的上下文无关语法相同的文本解析,并给每个解析分配一个概率。PCFG产生的一个解析的概率仅仅是它用到的产生式的概率的乘积。

最简单的方法定义一个PCFG 是从一个加权产生式序列组成的特殊格式的字符串加载它,其中权值出现在括号里,如6.4所示。

grammar = nltk.PCFG.fromstring("""
    S    -> NP VP              [1.0]
    VP   -> TV NP              [0.4]
    VP   -> IV                 [0.3]
    VP   -> DatV NP NP         [0.3]
    TV   -> 'saw'              [1.0]
    IV   -> 'ate'              [1.0]
    DatV -> 'gave'             [1.0]
    NP   -> 'telescopes'       [0.8]
    NP   -> 'Jack'             [0.2]
    """)
>>> print(grammar)
Grammar with 9 productions (start state = S)
    S -> NP VP [1.0]
    VP -> TV NP [0.4]
    VP -> IV [0.3]
    VP -> DatV NP NP [0.3]
    TV -> 'saw' [1.0]
    IV -> 'ate' [1.0]
    DatV -> 'gave' [1.0]
    NP -> 'telescopes' [0.8]
    NP -> 'Jack' [0.2]

例 6.4 (code_pcfg1.py)图 6.4:定义一个概率上下文无关文法(PCFG)

有时可以很方便的将多个产生式组合成一行,如VP -> TV NP [0.4] | IV [0.3] | DatV NP NP [0.3]为了确保由文法生成的树能形成概率分布,PCFG语法强加了约束,产生式所有给定的左侧的概率之和必须为1。6.4中的语法符合这个约束:对S只有一个产生式,它的概率是1.0;对于VP,0.4+0.3+0.3=1.0;对于NP,0.8+0.2=1.0。parse()返回的分析树包含概率:

>>> viterbi_parser = nltk.ViterbiParser(grammar)
>>> for tree in viterbi_parser.parse(['Jack', 'saw', 'telescopes']):
...     print(tree)
(S (NP Jack) (VP (TV saw) (NP telescopes))) (p=0.064)

现在,分析树被分配了概率,一个给定的句子可能有数量庞大的可能的解析就不再是问题。分析器将负责寻找最有可能的解析。

7 小结

8 深入阅读

本章的附加材料发布在http://nltk.org/,包括网络上免费提供的资源的链接。关于使用NLTK分析的更多的例子,请看在http://nltk.org/howto上的分析HOWTO。

有许多关于句法的入门书籍。(O'Grady et al, 2004)是一个语言学概论,而(Radford, 1988)以容易接受的方式介绍转换语法,推荐其中的无限制依赖结构的转换文法。在形式语言学中最广泛使用的术语是生成语法,虽然它与生成并没有关系(Chomsky, 1965)X-bar句法来自于(Jacobs & Rosenbaum, 1970),并在(Jackendoff, 1977)得到更深的拓展(The primes we use replace Chomsky's typographically more demanding horizontal bars)。

(Burton-Roberts, 1997)是一本面向实践的关于如何分析英语成分的教科书,包含广泛的例子和练习。(Huddleston & Pullum, 2002)提供了一份最新的英语句法现象的综合分析。

(Jurafsky & Martin, 2008)的第12章讲述英语的形式文法;13.1-3节讲述简单的分析算法和歧义处理技术;第14章讲述统计分析;第16章讲述乔姆斯基层次和自然语言的形式复杂性。(Levin, 1993)根据它们的句法属性,将英语动词划分成更细的类。

有几个正在进行的建立大规模的基于规则的语法的项目,如LFG Pargram 项目http://www2.parc.com/istl/groups/nltt/pargram/,HPSG LinGO 矩阵框架http://www.delph-in.net/matrix/以及XTAG 项目http://www.cis.upenn.edu/~xtag/

9 练习

  1. ☼ 你能想出符合语法的却可能之前从来没有被说出的句子吗?(与伙伴轮流进行。)这告诉你关于人类语言的什么?

  2. ☼ 回想一下Strunk和White的禁止在句子开头使用however表示“although”的意思。在网上搜索句子开头使用的however这个成分使用的有多广泛?

  3. ☼ 思考句子Kim arrived or Dana left and everyone cheered用括号的形式表示andor的相对范围。产生这两种解释对应的树结构。

  4. Tree类实现了各种其他有用的方法。请看Tree帮助文档查阅更多细节(如导入Tree类,然后输入help(Tree))。

  5. ☼ 在本练习中,你将手动构造一些分析树。

    1. 编写代码产生两棵树,对应短语old men and women的不同读法
    2. 将本章中表示的任一一颗树编码为加标签的括号括起的形式,使用nltk.Tree()检查它是否符合语法。使用draw()显示树。
    3. 如(a) 中那样,为The woman saw a man last Thursday画一棵树。
  6. ☼ 写一个递归函数,遍历一颗树,返回树的深度,一颗只有一个节点的树的深度应为0。(提示:子树的深度是其子女的最大深度加1。)

  7. ☼ 分析A.A. Milne 关于Piglet 的句子,为它包含的所有句子画下划线,然后用S替换这些(如第一句话变为S when:lx` S)。为这种“压缩”的句子画一个树形结构。用于建立这样一个长句的主要的句法结构是什么?

  8. ☼ 在递归下降分析器的演示中,通过选择Edit菜单上的Edit Text改变实验句子。

  9. grammar1中的语法能被用来描述长度超过20 词的句子吗?

  10. ☼ 使用图形化图表分析器接口,尝试不同的规则调用策略做实验。拿出你自己的可以使用图形界面手动执行的策略。描述步骤,并报告它的任何效率的提高(例如用结果图表示大小)。这些改进取决于语法结构吗?你觉得一个更聪明的规则调用策略能显著提升性能吗?

  11. ☼ 对于一个你已经见过的或一个你自己设计的CFG,用笔和纸手动跟踪递归下降分析器和移位-规约分析器的执行。

  12. ☼ 我们已经看到图表分析器增加边而从来不从图表中删除的边。为什么?

  13. ☼ 思考词序列:Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalohttp://en.wikipedia.org/wiki/Buffalo_buffalo_Buffalo_buffalo_buffalo_buffalo_Buffalo_buffalo解释的,这是一个语法正确的句子。思考此维基百科页面上表示的树形图,写一个合适的语法。正常情况下是小写,模拟听到这句话时听者会遇到的问题。你能为这句话找到其他的解析吗?当句子变长时分析树的数量如何增长?(这些句子的更多的例子可以在http://en.wikipedia.org/wiki/List_of_homophonous_phrases找到。)

  14. ◑ 你可以通过选择Edit 菜单上的Edit Grammar修改递归下降分析器演示程序。改变第二次扩充产生式,即NP -> Det N PPNP -> NP PP使用Step按钮,尝试建立一个分析树。发生了什么?

  15. ◑ 扩展grammar2中的语法,将产生式中的介词扩展为不及物的,及物的和需要PP补语的。基于这些产生式,使用前面练习中的方法为句子Lee ran away home画一棵树。

  16. ◑ 挑选一些常用动词,完成以下任务:

    1. 写一个程序在PP附着语料库nltk.corpus.ppattach找到那些动词。找出任何这样的情况,相同的动词有两种不同的附着,其中第一个是名词,或者第二个是名词,或者介词保持不变(正如我们在2句法歧义中讨论过的)。
    2. 制定CFG语法产生式涵盖其中一些情况。
  17. ◑ 写一个程序,比较自上而下的图表分析器与递归下降分析器的效率(4)。使用相同的语法和输入的句子。使用timeit模块比较它们的性能(见4.7,如何做到这一点的一个例子)。

  18. 比较自上而下、自下而上和左角落分析器的性能,使用相同的语法和3个符合语法的测试句子。使用timeit记录每个分析器在同一个句子上花费的时间。写一个函数,在这三句话上运行这三个分析器,输出3×3格的时间,以及行和列的总计。讨论你的发现。

  19. ◑ 阅读“garden path”的句子。一个分析器的计算工作与人类处理这些句子的困难性有什么关系?http://en.wikipedia.org/wiki/Garden_path_sentence

  20. ◑ 若要在一个窗口比较多个树,我们可以使用draw_trees()方法。定义一些树,尝试一下:

    >>> from nltk.draw.tree import draw_trees
    >>> draw_trees(tree1, tree2, tree3)                    
  21. ◑ 使用树中的位置,列出宾州树库前100个句子的主语;为了使结果更容易查看,限制从高度最高为2的子树提取主语。

  22. ◑ 查看PP附着语料库,尝试提出一些影响PP附着的因素。

  23. ◑ 在本节中,我们说过简单的用术语n-grams不能描述所有语言学规律。思考下面的句子,尤其是短语in his turn的位置。这是基于n-grams 的方法的一个问题吗?

    What was more, the in his turn somewhat youngish Nikolay Parfenovich also turned out to be the only person in the entire world to acquire a sincere liking to our "discriminated-against" public procurator. (Dostoevsky: The Brothers Karamazov)

  24. ◑ 编写一个递归函数产生嵌套的括号括起的形式的一棵树,显示去掉叶节点之后的子树的非终结符。于是上面的关于Pierre Vinken 的例子会产生:[[[NNP NNP]NP , [ADJP [CD NNS]NP JJ]ADJP ,]NP-SBJ MD [VB [DT NN]NP [IN [DT JJ NN]NP]PP-CLR [NNP CD]NP-TMP]VP .]S。连续的类别应用空格分隔。

  25. ◑ 从古登堡工程下载一些电子图书。写一个程序扫描这些文本中任何极长的句子。你能找到的最长的句子是什么?这么长的句子的句法结构是什么?

  26. ◑ 修改函数init_wfst()complete_wfst(),使WFST中每个单元的内容是一组非终端符而不是一个单独的非终结符。

  27. ◑ 思考4.4中的算法。你能解释为什么分析上下文无关语法是与n3成正比的,其中n是输入句子的长度。

  28. ◑ 处理宾州树库语料库样本nltk.corpus.treebank中的每棵树,在Tree.productions()的帮助下提取产生式。丢弃只出现一次的产生式。具有相同的左侧和类似的右侧的产生式可以被折叠,产生一个等价的却更紧凑的规则集。编写代码输出一个紧凑的语法。

  29. ★ 英语中定义句子S的主语的一种常见的方法是作为S 的名词短语孩子VP兄弟写一个函数,以一句话的树为参数,返回句子主语对应的子树。如果传递给这个函数的树的根节点不是S或它缺少一个主语,应该怎么做?

  30. ★ 写一个函数,以一个语法(如3.1定义的语法)为参数,返回由这个语法随机产生的一个句子。(使用grammar.start()找出语法的开始符号;grammar.productions(lhs)得到具有指定左侧的语法的产生式的列表;production.rhs()得到一个产生式的右侧。)

  31. ★ 使用回溯实现移位-规约分析器的一个版本,使它找出一个句子所有可能的解析,它可以被称为“递归上升分析器”。咨询维基百科关于回溯的条目http://en.wikipedia.org/wiki/Backtracking

  32. ★ 正如我们在7.中所看到的,可以将词块表示成它们的词块标签。当我们为包含gave的句子做这个的时候,我们发现如以下模式:

    gave NP
    gave up NP in NP
    gave NP up
    gave NP NP
    gave NP to NP
    
    1. 使用这种方法学习一个感兴趣的动词的互补模式,编写合适的语法产生式。(此任务有时也被称为词汇获取。)
    2. 识别一些英语动词的近同义词,如来自本章前面的例子dumped/filled/loaded使用词块划分方法研究这些动词的互补模式。创建一个语法覆盖这些情况。这些动词可以自由的取代对方,或者有什么限制吗?讨论你的发现。
  33. ★ 开发一种基于递归下降分析器的左角落分析器,从ParseI继承。

  34. ★ 扩展NLTK 中的移位-规约分析器使其包含回溯,这样就能保障找到所有存在的解析(也就是说,它是完整的)。

  35. ★ 修改函数init_wfst()complete_wfst(),当一个非终结符添加到WFST中的单元时,它包括一个它所派生的单元的记录。实现一个函数,将一个分析树的WFST转换成这种形式。

关于本文档...

针对NLTK 3.0 作出更新。本章来自于Natural Language Processing with PythonSteven Bird, Ewan KleinEdward Loper,Copyright © 2014 作者所有。本章依据Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 United States License [http://creativecommons.org/licenses/by-nc-nd/3.0/us/] 条款,与自然语言工具包 [http://nltk.org/] 3.0 版一起发行。

本文档构建于星期三 2015 年 7 月 1 日 12:30:05 AEST