第23章 用于通讯的自然语言

第23章 用于通讯的自然语言

本章中我们看看人们彼此之间如何通过自然语言进行交流以及计算机 Agent 如何加入到会话中。

通讯（Communication）是一种通过产生和感知信号（signs）而形成的有目的的信息交换，这些信号取自由约定信号组成的共享系统。大多数动物用信号表示重要消息：这里有食物、附近有捕食动物、前进、后退、求偶。在一个部分可观察的世界里，通讯可以帮助Agent取得成功，因为Agent能够通过通讯获得由其他Agent观察到或推断出的信息。人类是所有物种中最健谈的，如果Agent要对人类有所帮助的话，它们需要学习使用语言。本章我们来考虑用于通讯的语言模型。试图深度理解会话的模型，比那些旨在进行垃圾分类的简单模型更加复杂。本章首先介绍句子的短语结构语法模型，然后将语义加入模型，再将其用于机器翻译和语音识别。

23.1 短语结构语法

第22章提到的n元语言模型是基于单词序列的。这些模型的最大问题是数据稀疏（data sparsity）——对于一个包含 $ 10^5 $个单词的词汇表，将有 $ 10^{15} $个三元概率需要估计，所以，即使语料库有上万亿个单词，也不能提供可靠的评估。我们可以通过推广（generalization）的方法来解决稀疏问题。举例来说，“black dog”比“dog black”出现得更频繁，相似的，我们推广成：英语中形容词倾向于出现在名词之前（相反，在法语中形容词倾向于出现在名词之后：“chien noir”出现得更频繁）。当然，总会有例外的情况，“galore”形容词，它跟在它所修饰的名词的后面。尽管有特例，词法范畴（lexical category，也称为词类，part of speech），如名词或形容词，是一种有效的推广方法。但是，如果我们将词类组合成句法范畴（syntactic category，也称句法单位），如名词短语或动词短语，并将这些句法范畴构成句子的短语结构（phrase structure）树，每个嵌套短语都表示为一个范畴，模型就会更加有效。

一直有很多基于短语结构思想的有竞争力的语言模型。我们将介绍一个比较流行的模型：概率上下文无关文法（probabilistic context-free grammar）或者PCFG $ ^{1} $。文法（grammar）是一个规则的集合，它将语言定义为一个允许的词串集合。“概率”意味着文法给每个字符串分配一个概率。下面是一个PCFG规则：

$$ \begin{array}{l l l}{{V P}}&{\to}&{{V e r b}[0.70]}\\ {{}}&{\mid}&{{V P~N P~[0.30]}}\\ \end{array} $$

其中，VP（verb phrase，动词短语）和 NP（noun phrase，名词短语）是非终结符（non-terminal

symbols）。文法也用到真正的单词，即终结符（terminal symbols）。上面的规则表示，动词短语单独由动词组成的概率为 0.70，由一个 VP 后面跟上一个 NP 组成的概率为 0.30。附录 B 讲述了非概率的上下文无关文法。

现在我们针对一个小的英语片段定义文法，这个英语片段适用于 Agent 在探索 wumpus 世界时进行相互交流。我们称之为 $ \varepsilon_{0} $ 语言。在后续章节里，我们将改进 $ \varepsilon_{0} $ 使其更接近于真实英语。要为英语设计一个完整的语法是非常困难的，因为就算是两个人也不会在有效英语的构成上达成一致。

生成能力

可以根据生成能力（generative capacity）对文法形式进行分类，生成能力是指文法所能表示的语言集合。乔姆斯基（Chomsky，1957）根据重写规则的形式的不同定义了4类文法形式。这些文法类别构成了一个层次结构，其中每一类都除了能描述较低能力类所能描述的所有语言以外，还可以描述一些其他语言。下面我们列出这个层次结构，从描述能力最强的类型开始：

递归可枚举（Recursively enumerable）文法使用无约束的规则：重写规则的左右两侧都可以包含任意数量的终结符和非终结符，如 $ A B C \rightarrow D E $。这类文法的表达能力与图灵机相同。

上卜又有天又法（Context-sensitive grammar）只要求重与规则的右部包含的符号数目不少于左部符号的数目。“上下文有关”这个名称来自这样的事实：以规则 $ AXB \rightarrow AYB $ 为例，它的意思是说，如果 X 出现在前有 A 后有 B 的上下文中，那么可以将其重写为 Y。上下文有关文法能够表示 $ a^nb^nc $（表示 n 个 a、n 个 b 和 n 个 c 组成的序列，a、b 和 c 的数目相同）这类语言。

上下文无关文法（Context-free grammar，简称 CFG）中，每个重写规则的左部只有一个单独的非终结符。因此，每条规则允许在任何上下文中将该非终结符重写为规则的右部。尽管现在广泛接受的观点是至少某些自然语言包含了非上下文无关的成分（Pullum，1991），但 CFG 仍广泛用于自然语言和程序设计语言的语法。上下文无关文法能够表示 $ a''b'' $ 这类语言，但不能表示 $ a''b''c'' $。

正则文法（Regular grammar）是约束最强的一类。它的每条重写规则的左部是一个单独的非终结符，右部是一个终结符、后面跟着一个可有可无的非终结符。正则文法的表达能力与有限状态自动机相同。这类文法不太适合程序设计语言，因为它们不能表示诸如对称的括号串这类结构（ $ a^n b^n $）语言的一个变种）。它们能表示的最接近的语言就是 $ a^* b^* $，即由任意数量的 $ a $后面跟着任意数量的 $ b $组成的一个序列。

尽管在层次体系中等级越高的文法表达能力越强，但是处理它们的算法的效率也越低。直到20世纪80年代，语言学家一直把注意力集中在上下文无关和上下文有关语言上。从那时开始，由于需要对上百万字节甚至上十亿字节的在线文本进行非常快速的处理，哪怕分析是不完整的也可接受，因此，正则文法重新激起了研究兴趣。正如Fernando Pereira指出的那样：“随着年纪的越来越大，我研究的乔姆斯基文法层次也越来越低”。读者可以可以比较阅读Pereira和Warren（1980）以及Mohri、Pereira和Riley（2002）（注：这三位作者现在都在为谷歌的大型文本语料库工作）这篇文章，就可以理解Fernando Pereira说的意思了。

23.1.1 $ \varepsilon_{0} $ 的词典

首先我们定义一个词典（lexicon），或者说合法的词语列表。这些词语按照一种字典使用者熟悉的词法范畴（lexical categories）进行分类：指示事物的名词、代词、名字，指示事件的动词，修饰名词的形容词，修饰动词的副词，以及功能词：冠词（比如 the）、介词（in）和连词（and）。图 23.1 描述了一个小型的 $ \varepsilon_{0} $ 语言的词典。

Noun → stench [0.05] | breeze [0.10] | wunpus [0.15] | pits [0.05] |

Verb → is [0.10] | feel [0.10] | smells [0.10] | stinks [0.05] |

Adjective → right [0.10] | dead [0.05] | smelly [0.02] | breezy [0.02] |

Adverb → here [0.05] | ahead [0.05] | nearby [0.02] |

Pronoun → me [0.10] | you [0.03] | I [0.10] | it [0.10] |

RelPro → that [0.40] | which [0.15] | who [0.20] | whom [0.02] |

Name → John [0.01] | Mary [0.01] | Boston [0.01] |

Article → the [0.40] | a [0.30] | an [0.10] | every [0.05] |

Prep → to [0.20] | in [0.10] | on [0.05] | near [0.10] |

Conj → and [0.50] | or [0.10] | but [0.20] | yet [0.02] |

Digit → 0 [0.20] | 1 [0.20] | 2 [0.20] | 3 [0.20] | 4 [0.20]

每个以“…”结尾的范畴说明在这个范畴中还有其他词语。对于名词、名字、动词、形容词和副词而言，即便从原则上说，将它们全部列出也是不可行的。不仅是因为每类中有成千上万的词语，而且经常还有新词加入——如iPod或者biodiesel。这5个范畴被称为开放类（open class）。对于代词、关系代词、冠词、介词以及连词这些范畴，我们努力就能够完全列举出这些词语。这些范畴被称为封闭类（closed class），它们只包含少量词语（十来个或更多）。封闭类经过几个世纪才发生变化，而不是几个月。比如，词语“thee”和“thou”在17世纪是被普遍使用的代词，到了19世纪这种趋势才减弱，而今天仅仅在诗歌和某些地区方言中才能见到。

23.1.2 $ \varepsilon_{0} $ 的语法

下一步则是将单词组合成短语。图 23.2 描述了 $ \varepsilon_{0} $ 的语法，6 个句法范畴的规则，并且为每条重写规则都提供了一个例子 $ ^{1} $。图 23.3 描述了句子 “Every wumpus smells.” 的分析树（parse tree）。分析树给出了一各构造性的证明：该单词串的确是符合 $ \varepsilon_{0} $ 规则的句子。 $ \varepsilon_{0} $ 语法能够生成很多英语语句，如：

John is in the pit

The wumpus that stinks is in 22

Mary is in Boston and the wumpus is near 32

不幸的是，该语法会过生成（overgenerate）：也就是说，它可以生成不符合语法的语句，比如“Me go Boston”和“I smell pits wumpus John.”同时它也可能欠生成（undergenerates）：它会拒绝很多英语中的语句，比如“I think the wumpus is smelly.”下面我们将看到如何学习获得更好的语法，现在我们暂时把注意力集中在运用现有语法我们能做些什么。

23.2 句法分析

句法分析（Parsing）是按照语法规则分析单词串从而得到其短语结构的过程。图23.4说明了我们可以从S符号开始，自顶向下搜索并构造以单词作为叶子结点的树，或者我们也可以从单词出发，自底向上搜索并构造树直到顶端S。然而，自顶向下和自底向上句法分析方法都可能比较低效，二者都会对搜索空间中的某些区域做重复工作而浪费时间，而

这些区域可能并不能引向成功的分析。考虑以下两个语句：

尽管它们的前10个单词都是相同的，但是这两个句子却有截然不同的句法分析结果，因为第一句是一个命令句，而第二句是一个疑问句。从左到右的句法分析算法将不得不猜测第一个单词到底是命令句还是疑问句的组成部分，直到处理到第十一个单词 take 或 taken 时，算法才能够确定到底哪个猜测是正确的。当算法猜测错误时，它必须一直回溯到第一个单词，并在另一种解释下重新分析整个句子。

为了这种导致低效率的问题，我们可以使用动态规划方法：每次分析子串时，就将结果存储起来，将来再碰到就无需重新分析了。例如，一旦我们发现“the students in section 2 of Computer Science 101”是一个名词短语，我们可以将结果记录在一种被称为图（chart）的数据结构中。做这种工作的算法被称为图分析器（chart parser）。因为我们使用的是上下文无关文法，因此在搜索空间中，我们在某一分支的上下文中对任何短语的分析，也可以在其他分支中适用。图分析器有很多种类，我们介绍的是一种自底而上的方法，被称为CYK算法（CYK algorithm），该算法以其发明者命名：John Cocke，Daniel Younger和Tadeo Kasami。

图 23.5 描述了 CYK 算法。注意，算法要求文法的所有规则都符合下面两种形式之一：词法规则的形式是 $ X \rightarrow \text{word} $，而句法规则的形式是 $ X \rightarrow YZ $。这种文法形式被称为 Chomsky 范式（Chomsky Normal Form），虽然看上去是受限的，其实不然：任何上下文无关语法的都可以被自动转换为 Chomsky 范式。习题 23.8 可以引导你思考这个转换过程。

CYK 算法中表 P 占用的空间为 $ O(n^2m) $，其中 n 是句子中单词的数目，m 是文法中非终结符的数目，其时间花费为 $ O(n^3m) $。（由于 m 对于某一具体语法而言是常量，通常也被描述为 $ O(n^3) $）虽然对于限制更加严格的文法可以找到更快的算法，但对于一般的上下文无关语法而言，已经没有比 CYK 更好的算法。事实上，让一个算法在 $ O(n^3) $ 的时间内完成分析，也是件很技巧的工作，因为一个句子可能会有指数级数目的分析树。考虑如下句子：

Fall leaves fall and spring leaves spring.

function CYK-parse(words, grammar) returns P, a table of probabilities

N ← LENGTH(words)

M ← the number of nonterminal symbols in grammar

P ← an array of size [M, N, N], initially all 0

/* Insert lexical rules for each word */

for i = 1 to N do

for each rule of form (X → words[p]) do

P[X, i, 1] ← p

/* Combine first and second parts of right-hand sides of rules, from short to long */

for length = 2 to N do

for start = 1 to N − length + 1 do

for len1 = 1 to N − 1 do

len2 ← length − len1

for each rule of the form (X → Y Z [p]) do

P[X, start, length] ← MAX[P[X, start, length],

P[Y, start, len1] × P[Z, start + len1, len2] × p)

end

end

end

end

return P

图 23.5 CYK 句法分析算法。给定一个单词串，算法将找出整个串及其所有子串的最可能的推导。算法的返回值是整个表 P，其中数组 $ P[X, start, len] $ 表示的是从位置 start 开始、长度为 len 的子串构成范畴 X 的最可能概率。如果在该子串不能构成 X，那么概率为 0

这句话有歧义，因为句中的每一个单词（除了 and）都既可作名词又可作动词，同时“fall”和“spring”还可以作形容词。（例如，“Fall leaves fall”的一个意思是“秋天抛弃了秋天”。）按照 $ \varepsilon_{0} $这句话有四种分析结果：

[S [S [NP Fall leaves] fall] and [S [NP spring leaves] spring]

[S [S [NP Fall leaves] fall] and [S spring [VP leaves spring]]

[S [S Fall [VP leaves fall]] and [S [NP spring leaves] spring]

[S [S Fall [VP leaves fall]] and [S spring [VP leaves spring]]

如果一个子句包含有 $c$ 个双歧义词，我们就会得出 $2^c$ 种不同的途径去挑选这个句子的解释$^1$。那么 CYK 算法是如何在 $O(c^3)$ 的时间内处理 $2^c$ 个的分析树的？答案是该算法并没有检查所有的分析树；它所做的只是计算可能性最大的树的概率。这些子树都表示在表 $P$ 中，并且通过少量的工作我们就可以将他们全部枚举出来（在指数时间内），但 CYK 算法的美妙之处就在于我们不必枚举出他们，除非我们需要这么做。

在实践中，我们通常只对最好的分析结果感兴趣，而不是所有的分析结果。可以将 CYK 算法看成是定义了按照“运用文法规则”这一操作而得到的完全状态空间，因而可以利用 $ A^{*} $ 算法实现只搜索空间的某一部分。空间中的每一个状态都是一个项目列表（单词或句法范畴），如自底向上分析表（图 23.4）中所示。起始状态是一个单词序列，而目标状态是一个项目 S。每个状态的代价为按照当前已使用规则的概率而计算得到的概率的倒数，也有许多启发式方法可用来估计到目标的剩余距离。最佳的启发式是通过机器学习从句子语料库上获取。利用 $ A^{*} $ 算法我们没必要搜索整个状态空间，而且我们也能确保我们首先找到的分析结果就是可能性最大的分析。

23.2.1 学习 PCFG 的概率

一个 PCFG 包含许多规则，每条规则附有一个概率。这暗示着，从数据中学习文法可能比知识工程方法更好。如果具备大量的经过正确分析的句子，通常称为树库（treebank），学习 PCFG 的任务就会变得极其简单了。宾州树库（Penn Treebank, Marcus 等 1993）最有名，它包括三百万词语料，利用自动工具外加一些人工工作，进行了词类和分析树结构标注。表 23.6 所展示的就是一个宾州树库中的带标记的树。

给定一个树库语料，我们就能够通过计数（和平滑）建立 PCFG。在上面的例子中，形如[S[NP…][VP…]]的结点有两个。我们可以统计一下语料库中所有以S为根的子树数目。如果在100 000个S结点中有60 000个是这种形式，那么我们就可以建立如下规则：

$ S \rightarrow NP VP [0.60] $

如果没有树库可用、而只有未经分析且无标记的原始句子该怎么办？此时仍然有可能从这样的语料库中学到文法，但难度也更大。首先，我们实际上有两个问题：学习文法规则的结构和学习每条规则相关的概率。（我们在学习贝叶斯网络时也有这样的区分）。我们假设词法和句法范畴名已经给出。（即使没有，我们也可以假设有范畴 $ X_1, \cdots, X_n $，然后通过交叉验证选出 $ n $ 的最优值）。之后，我们可以假设文法包含了所有可能的 $ (X \to Y \text{Z}) $ 或 $ (X \to \text{word}) $ 的规则，尽管其中有许多规则的概率为 0 或者接近 0。

就像在学习 HMM 时一样，我们可以采用最大期望（EM）方法。要学习的参数是规则的概率，我们从随机或统一的初始值开始。而隐变量是分析树：我们还不知道词序列 $ w_i \cdots w_j $ 是否由规则 $ (X \rightarrow \cdots) $ 产生。E 步骤估计每条规则产生每个子序列的概率。然后，M 规则估计每条规则的概率。整个计算过程以动态规划的方式实现，所采用的是向内向外算法（inside-outside algorithm），类似于 HMM 的前向后向算法。

向内向外算法令人不可思议的地方在于能够从未经句法分析的文本中诱导出文法。但它也存在许多缺点。首先，诱导出的文法产生的句法分析结果往往难以理解，不能令语言学家满意。这使得把很难把手工知识和自动诱导出的知识结合起来。其次，该算法速度很慢：复杂度是 $ O(n^3m^3) $，其中 $ n $ 是句子中的词数， $ m $ 是文法非终结符的数目。第三，概率赋值的空间很大，陷入局部极大点是经常遇到的严重问题。模拟退火等其他方法可以得到更接近全局最大点的结果，代价也更大。Lari 和 Young（1990）指出向内向外算法“面对实际问题的计算代价很难应付”。

然而，如果我们愿意打破只从未分析文本中学习这一限制，还是可以有所进步的。一种方法是从原型中学习：给出一些种子规则，类似 $ \varepsilon_{0} $规则。以此为基础，更复杂的规则学起来就更容易，这样得到的文法用于英语分析时，整体的召回率和准确率大约是80%（Haghighi and Klein，2006）。另外一种方法是利用树库，除了直接从括号标记中学习PCFG规则之外，也学习不在树库中的规则。例如，图23.6中的树就没有区分NP和NP-SBJ之间的差别。后者是用于代词“she”，而前者用余代词“her”。在23.6节我们会深入探讨这个问题，而现在我们可以说有很多有效的方法可以去分裂一个范畴，就像NP——文法诱导系统会利用树库、并自动分裂范畴，这样做比那些坚持用原始范畴集合的方法要好（Petrov and Klein，2007c）。自动学习文法的错误率仍然比手动建立的文法高50%，但差距正在减小。

[ { S [NP-SBJ-2 Her eyes]

[VP were

[VP glazed

[NP *-2]

[SBAR-ADV as if

[S [NP-SBJ she]

[VP did n't

[VP [VP hear [NP *-1]]

or

[VP [ADVP even] see [NP*-1]]

[NP-1 him]]]]]]]]]]

23.2.2 比较上下文无关法和马尔科夫模型

PCFG 的问题在于它们是上下文无关的。也就意味着 $ P(\text{eat a banana}) $ 和 $ P(\text{eat a bandanna}) $ 之间的差别仅仅取决于 $ P(Noun \rightarrow "banana") $ 和 $ P(Noun \rightarrow "bandanna)) $ 之间的差异，而不依赖于 "eat" 和相应宾语之间的关系。（在英语中，banana 是香蕉，bandanna 是大手帕，译者注）利用 2 阶或更高阶的马尔科夫模型，当给定一个足够大的语料库时，就会知道 "eat a banana" 的可能性更大。我们可以将 PCFG 和马尔科夫模型结合起来以达到最佳。估算句子概率最简单的方法是取两种模型分别计算出的概率的几何平均数。然后我们就知道从文法和词法的角度上看 "eat a banana" 都是可能的。但这种方法依然无法从句子 "eat a slightly aging but still palatable banana" 中找出 "eat" 和 "banana" 之间的关系，因为在这里关系的距离超过了两个单词。增加马尔科夫模型的阶数也不能更精确地获取关系，要做到这点，可以利用词汇化的 PCFG（lexicalized PCFG），这种方法将会在下节介绍。

PCFG 的另一个问题是它们对于短句子有着强烈的偏置。在 Wall Street Journal 这样的语料库中，句子的平均长度是 25 个单词。但是，PCFG 通常会赋予短句子很高的概率，例如 “He slept，” 然而在杂志中我们更容易看到 “It has been reported by a reliable source that the allegation that he slept is credible.” 这样的长句。看上去杂志中的短语确实不是上下文无关的，相反，作者会对于句子有一个预期长度，并把这个长度作为他书写句子的全局的软约束。这些在 PCFG 中很难被反映出来。

23.3 扩展文法和语义解释

在本节中，我们可以看到如何扩展上下文无关文法——也就是说，例如，不是每一个NP都独立于上下文，相反，某些NP更可能出现在某种上下文中，而其他NP则可能出现在其他上下文中。

23.3.1 词汇化的 PCFG

为了得到动词“eat”与名词“banana”之间的关系以及名词“banana”与“bandanna”的对比，我们可以使用词汇化的PCFG（lexicalized PCFG），其中规则的概率依赖于分析树中单词之间的关系，而不仅仅是句子中单词之间的邻接关系。当然，我们无法得到依赖于树中所有单词的概率，这是因为我们没有足够的训练数据去估算所有这些概率。下面我们介绍一个有用的概念：短语的头（head）——短语中最重要的单词。这样，“eat”就是VP“eat a banana”的头，“banana”是NP“a banana”的头。我们用概念VP(v)表示一个VP范畴的短语，该短语的头词是v。我们说范畴VP用头变量v进行了扩展（augmented）。这里是一个描述动词-宾语关系的扩展文法：

}$$ \begin{aligned}&VP(v)\rightarrow Verb(v)NP(n)&\quad&[P_{1}(v,n)]\\&VP(v)\rightarrow Verb(v)&\quad&[P_{2}(v)]\\&NP(n)\rightarrow Article(a)Adj s(j)Noun(n)&\quad&[P_{3}(n,a)]\\&Noun(banana)\rightarrow banana&\quad&[p_{n}]\\&\cdots&&\cdots\end{aligned} $$

这里 $ P_1(v, n) $ 的概率取决于头词 v 和 n。如果 v 是 “eat”、n 是 “banana”，我们给出的概率会相对高一些，如果 n 是 “bandanna” 就会比较低。注意，由于我们仅考虑头，“eat a banana” 与 “eat a rancid banana” 之间的差别就不会被这些概率所体现。这种方法的另一个问题在于，在一个具有 20 000 个名词和 5000 个动词的词汇表中， $ P_1 $ 有一亿个概率要估算。这些概率中只有一小部分可从语料库中得到，另一些可通过平滑获得（见 22.1.2 节）。例如我们预测 $ P_1(v, n) $ 时，如果 $ (v, n) $ 对很少见（或从未见过），则可以回退到仅依赖于 v 的模型。这种与宾语无关的概率依然十分有效，它们可以区分出到 “eat” 这类及物动词和 “sleep” 这类不及物动词之间的区别，前者的 $ P_1 $ 较高、 $ P_2 $ 较低，而后者正好相反。从树库中学习这些概率是非常可行的。

23.3.2 扩展文法规则的形式定义

由于扩展规则复杂，我们将通过说明扩展规则是如何被翻译成逻辑句子的方式，给出其形式定义。句子可采用确定子句（definite clause）的形式，因此这种规则被称为确定子句文法（definite clause grammar），即DCG。我们以一条规则为例，这条规则取自NP的词汇化的文法，加上了新的标记：

$$ NP(n)\rightarrow\quad Article(a)\quad Adjs(j)\quad Noun(n)\quad\{Compatible(j,n)\} $$

这里新增了标记 {constraint}，以表示对于某些变量的逻辑约束，只有当这些约束为真时规则才有效。这里的谓词 Compatible(j, n) 意味着检验形容词 j 和名词 n 是否是相容的。它可以被定义为一组断言，如 Compatible(black, dog) 等。我们可以将该文法规则转换成一个确定子句，通过：（1）交换左部和右部的顺序，（2）用逻辑与将所有成分和约束连接起来，（3）在每个成分的自变量列表中添加一个变量 $ s_i $，以表示各成分覆盖的单词序列，（4）在树的根的自变量列表中添加一个条目 $ Append(s_1, \cdots) $，以表示词之间的联系。这样我们得

到了：

$$ \begin{aligned}Article(a,s_{1})\land Adjs(j,s_{2})&\land Noun(n,s_{3})\land Compatible(j,n)\\\Rightarrow&NP(n,\quad Append(s_{1},s_{2},s_{3}))\end{aligned} $$

该确定子句的意义是，如果谓词 Article 对于头词 a 和词串 $ s_{1} $ 为真，Adjs 对于头词 j 和词串 $ s_{2} $ 为真，Noun 对于头词 n 和词串 $ s_{3} $ 为真，并且 j 和 n 是相容的，则谓词 NP 在头词 n 和 $ s_{1} $、 $ s_{2} $ 和 $ s_{3} $ 的连接结果上为真。

上述 DCG 翻译没有考虑概率，但我们还可以将概率放进来：为每个率成分增加了一个表示该成分的概率的变量，根对应的变量的值为其所有构成成分的概率乘积再乘上规则的概率。

这种将文法规则翻译成确定子句的方法，使得我们可以按照逻辑推理的方式来讨论句法分析，也使得运用多种不同方法进行语言或者字串的推理成为可能。例如，这意味着我们可以通过正向链做自底向上的分析、通过反向链做自顶向下的分析。事实上，利用DCG分析自然语言是Prolog逻辑程序设计语言最早的应用（和动机）之一。有时候，也可以将这一过程倒过来，这样语言生成（language generation）就和分析一样了。例如，参见图23.10，逻辑程序可以运用确定子句规则对语义形式Loves(John，Mary)进行演绎：

$$ S\left({L o v e s}({J o h n},{M a r y}),\quad{[J o n h},{l o v e s},{M a r y}]\right) $$

这只是个玩具般的例子，严谨的语言生成系统除了 DCG 规则本身所提供的功能外，还需要在过程上加入更多的控制。

23.3.3 格一致性和主语-动词一致性

在 23.1 节中我们看到了 $ \varepsilon_0 $ 语言的简单文法是过生成的，产生了诸如“Me smell a stench”的错误语句。为了避免此类问题，我们的文法必须要知道“me”在作为一个句子的主语时不是一个有效的 NP。语言学家说代词“I”是主格（subjective case），而“me”是宾格（objective case） $ ^1 $。我们可以通过把 NP 分为两类来说明这一点，NPs 和 NPo，分别代表主格的和宾格的名词短语。我们同样需要把代词分为两类 $ Pronoun_S $（其中包括“I”）和 $ Pronoun_O $（其中包括“me”）。图 23.7 的上半部分说明了描述格一致性（case agreement）的文法，我们把这种语言称为 $ \varepsilon_I $ 语言。注意，所有的 NP 规则都被复制了，一部分描述 $ NPs $ 另一部分描述 $ NP_O $。

不幸的是，$\varepsilon_1$ 规则依然是过生成的。英语要求句子中主语和动词在人称和数量上保持主语-动词一致性（subject-verb agreement）。例如，如果“I”是主语，则“I smell”是符合语法的，但“I smells”不是。如果“it”是主语，我们会得到相反的结果。在英语中，一致性的差别是细微的：大多数的动词有一种针对第三人称单数主语（he，she，或者 it）的形式，对于其他人称和数的组合则有另一种形式。只有一个例外：动词“to be”有三种形式，“I am/you are/he is”因此，按照一种差别（格的差别）可把 NP 分为两种形式，而按照另一种差别（人称和数量）可把 NP 分为三种形式，而且如果我们再发现其他的差别，按照 $\varepsilon_1$ 的方法，我们会得到指数级的带下标的 NP 的形式。扩展是一个更好的途径：他们

$\mathcal{E}_{1}$:

$\mathcal{S} \rightarrow NP_{S} VP \mid \cdots$

$NP_{S} \rightarrow Pronoun_{S} | Name | Noun | \cdots$

$NP_{O} \rightarrow Pronoun_{O} | Name | Noun | \cdots$

$VP \rightarrow VP NP_{O} \mid \cdots$

$PP \rightarrow Prep NP_{O}$

$Pronoun_{S} \rightarrow I| you| he| she| it \cdots$

$Pronoun_{O} \rightarrow me| you| him| her| it \cdots$

$\cdots$

$\mathcal{E}_{2}$:

$\mathcal{S}(head) \rightarrow NP(Sbj, pn, h) VP(pn, head) \mid \cdots$

$NP(c, pn, head) \rightarrow Pronoun(c, pn, head) | Noun(c, pn, head) \mid \cdots$

$VP(pn, head) \rightarrow VP(pn, head) NP(Obj, p, h) \mid \cdots$

$PP(head) \rightarrow Prep(head) NP(Obj, pn, h)$

$Pronoun(Sbj, IS, I) \rightarrow I$

$Pronoun(Sbj, IP, we) \rightarrow we$

$Pronoun(Obj, IS, me) \rightarrow me$

$Pronoun(Obj, 3P, them) \rightarrow them$

在一条规则中描述指数级的形式。

在图 23.7 的下半部分，我们可以看到语言 $ \varepsilon_2 $ 的（部分）扩展语法，它包括了格一致、主语-宾语一致和头词。我们只有一个 NP 范畴，但是 NP(c, pn, head)包含了三个扩展：c 是一个表示格的参数、pn 是一个表示人称和数量的参数，而 head 是一个代表短语头词的参数。其他的范畴同样是通过头和其他参数进行了扩展，让我们仔细考虑其中的一条规则：

$$ S(head)\rightarrow NP(Sbj,pn,h)\quad VP(pn,head) $$

这条规则从右至左看是很容易理解的：当一个 NP 和一个 VP 连接起来构成一个 S，但只有当 NP 拥有主格(Sbj)、且 NP 和 VP 在人称和数量(pn)上是一致时成立。如果条件成立，我们则得到一个 S，它的头与 VP 的头相同。注意到哑变量 h 所表示的 NP 的头，并没有出现在 S 的扩展中。 $ \varepsilon_{2} $ 的词法规则包含了变量的值，同样最好从右至左读。例如，规则：

$$ Pronoun(S b j,1S,\mathbf{I})\to\mathbf{I} $$

说明 “I” 可以被解释为一个主格代词，第一人称单数，头是 “I”。为简单起见，我们省略了这些规则的概率，但是扩展确实可以和概率一起工作。扩展也可以和自动学习机制一起工作。Petrov 和 Klein（2007c）介绍了学习算法是如何自动将 NP 分成 $ NP_{S} $ 和 $ NP_{O} $ 的。

23.3.4 语义解释

为了说明如何给文法增加语义，我们从一个比英语更简单的例子开始：算术表达式的语义。表23.8给出了一个算术表达式文法，其中每一条规则都作了扩展，用一个变量来描述短语的语义解释。像“3”这类数字的语义就是数字本身。而像“3+4”这样的表达式的语义是指将运算符“+”作用于短语“3”和短语“4”的语义之上。这些规则都遵循合成语义（compositional semantics）原则——一个短语的语义是它的子短语的语义的函数。图23.9

显示了该文法下的表达式 $ 3+(4\div2) $ 的分析树。分析树的根是 $ \text{Exp}(5) $，表示一个语义解释为 5 的表达式。

现在我们来考虑英语语义，或至少是 $ \varepsilon_{0} $语言的语义。我们首先要确定给规则附加哪种语义表示。考虑最简单的例句“John loves Mary”。其中，NP“John”应该以逻辑项John作为自己的语义解释，整个句子则应该以逻辑语句Loves(John, Mary)作为其解释。这样看起来就清楚多了。而复杂的部分是VP“loves Mary”。该短语的语义解释既不是一个逻辑项，也不是一个完整的逻辑语句。直观地说，“loves Mary”是一种描述，可用于某个特定人或其他人。（在当前情况下，它被用于描述John。）这意味着“loves Mary”是一个谓词（predicate），当与表示某个人的项（这个人是爱的行为主体）相结合时，就会产生一个完整的逻辑语句。通过 $ \lambda $-记号，我们可以将“loves Mary”表示为谓词

$$ \lambda x\quad L o v e s(x,M a r y)。 $$

现在我们需要一条规则来说明“一个具有 obj 语义的 NP 后面跟随一个具有 pred 语义的 VP，将形成一个句子，该语句的语义就是将 pred 应用于 obj 的结果”：

$$ S(p r e d(o b j))\to N P(o b j)\quad V P(p r e d) $$

这条规则告诉我们“John loves Mary”的语义解释是

$$ (\lambda x\quad L o v e s(x,M a r y))(J o h n) $$

这与 Loves(John, Mary)是等价的。

根据我们到目前为止所采取的方法，可以很直接地描述其余的语义。因为 VP 已被表示为谓词，所以将动词也表示为谓词也是一个好主意。动词“loves”表示为 $ \lambda y \lambda x $ Loves(x, y)，

对于该谓词，如果给定了参数 Mary，则得到谓词 $ \lambda x $ Loves(x, Mary)。最后我们得到文法如图 23.10 所示，图 23.11 给出了分析树。虽然我们也可以很容易地为 $ \varepsilon_2 $ 语言添加语义，但我们仍选择 $ \varepsilon_0 $ 语言，这样读者在同一时间只需关注一类语义扩展。

手工为文法增加语义扩展很费力而且易出错。因此，有多个项目是从例子中学习语义扩展。CHILL（Zelle and Mooney，1996）是一个采取诱导逻辑编程（inductive logic programming，ILP）的程序，它可以从例子中学习文法以及特定的分析器。其目标领域是利用自然语言进行数据库查询。训练的例子包括单词串对和相应的语义形式组成的对——例如：

CHILL 的任务是试图学习与例子一致的谓词 Parse(words, semantics)，并希望能推广到其他的例子。直接应用 ILP 来学习该谓词效果很差：诱导出的分析器只有 20% 的准确率。幸运的是，ILP 的学习器可以通过增加知识来提高。在这种情况下，大多数的谓词 Parse 被定义为一个逻辑程序，CHILL 的工作就是诱导出控制规则以指导分析器挑选分析结果。通过增加这些背景知识，在各种数据库查询中，CHILL 可以通过学习达到 70% 至 85% 的准确率。

23.3.5 复杂成分

真实的英语的语法是极其复杂的。我们简要地给出一些例子。

时间和时态（Time and tense）：假设我们希望表示出“John loves Mary”和“John loved Mary”之间的区别。英语通过动词的时态（过去时、现在时和将来时）来表明某个事件的相对时间。12.3 节介绍的事件演算符号是一种表示事件时间的好选择，在事件演算中我们有：

$$ \begin{aligned}&John~loves~Mary:\;E_{1}\in~Loves(John,Mary)\;\land~During(Now,Extent(E_{1}))\\&John~loved~Mary:\;E_{2}\in~Loves(John,Mary)\land After(Now,Extent(E_{2}))\\ \end{aligned} $$

这提示我们对于单词 “loves” 和 “loved” 的词汇规则应该是：

$$ {V e r b}(\lambda y\,\lambda x\,e\in{L o v e s}(x,y)\land{D u r i n g}({N o w},e))\to\mathbf{\mathbf{\ell}} o v e s $$

$$ {V e r b}(\lambda y\,\lambda x\,e\in{L o v e s}(x,y)\land{A f t e r}({N o w},e))\to\mathrm{\boldmath~l o v e d~} $$

除了这些改变之外，文法中其余的部分均保持不变，这是一个好消息；这一点提示我们，如果我们能够很容易地添加一些类似动词时态的复合成分（尽管我们只是触及了描述时间和时态的完整文法的皮毛），那么我们就走对路了。我们在第12.3.1节讨论知识表示时，区分了过程和离散时间之间的差别，实际上在语言使用中也得到了反映。我们可以说“John slept a lot last night”，因为“睡觉”（Sleeping）是一个过程范畴，但如果说“John found a unicorn a lot last night”就有点奇怪了，因为“找到”（Finding）是一个离散事件范畴。一个文法应该反映这样一个事实，用副词短语“a lot”修饰离散事件应该是低概率的。

量词（Quantification）：考虑句子“Every agent feels a breeze.”这句话在 $ e_{0} $语言下只有一种句法分析结果，但实际上是有歧义的。优选的意义应该是“对于每一个Agent（agent）都存在一阵该Agent能感觉到的微风”，但另一个可接受的意义是“有一阵微风所有的Agent都感觉得到” $ ^{1} $。这两种解释可以表示如下：

$$ \forall a\;a\in{A g e n t s}\Rightarrow\exists b\;b\in{B r e e z e z e s}\land\exists e\;e\in{F e e l}(a,b)\land{D u r i n g}({N o w},e); $$

$$ \exists b\;b\in B{b e e z e s}\;\forall a\;a\in A{g e n t s}\Rightarrow\exists e\;e\in F{e e l}(a,b)\land D{u r i n g}(N o w,e). $$

在标准的量词限定方法中，文法定义的并非真正的逻辑语义语句，而是一种准逻辑形式（quasi-logical form），该形式可以通过分析过程之外的算法转化为逻辑语句。这些算法会采取一些优先规则选择一种量词辖域——这些优先规则并不需要在文法中直接反映。

语用（Pragmatics）：我们已经介绍了 Agent 如何感知一个单词串并应用文法得到一组可能的语义解释。现在，我们将讨论增加关于当前场景的上下文依赖信息来完成解释。需要语用信息的最明显的例子是确定索引词（indexical）的意义，索引词是一些直接涉及当前场景的短语。例如，在语句 “I am in Boston today” 中，“I” 和 “today” 都是索引词。单词 “I” 可能表示一个口若悬河的说话者，但是如何确定这些话的意义则和听者相关——这些因素并不属于文法的某一部分，而是一个语用问题，需要利用当前场景的上下文来解释这些话。

语用的另一部分是解释说话者的意图。说话者的动作可以被认为是一个说话行为（speech act），需要由听者辨认这是一种什么类型的行为——提问、陈述、承诺、警告、命令等等。类似“go to 22”这样的命令句暗指听者去行动。命令句可由 VP 构成，而主语可省略、暗指听者。我们需要区分命令和陈述，所以我们对 S 规则进行了修改，包含了说话行为的类型：

$$ \begin{aligned}&S(Statement(Speaker,pred(obj)))\rightarrow NP(obj)VP(pred)\\&S(Command(Speaker,pred(Hearer)))\rightarrow VP(pred)\\ \end{aligned} $$

长距离依赖（Long-distance dependencies）：疑问句又引入了一种新的语法复杂性。在“Who did the agent tell you to give the gold to?”中，最后一个单词“to”应该被分析为[PP to ⊆]，其中“⊆”表示 NP 的空缺或标记（trace），句中的第一个词“who”与缺失的 NP 对应。我们采取一种复杂的扩展系统，确保缺失的 NP 与对应的单词能正确匹配，并禁止在

错误的地方出现空缺。例如，不允许空缺出现在 NP 连词结构的一个分支中：“What did he play [NP Dungeons and 📷]” 是不合语法的。但允许在 VP 连词结构的两个分支中出现相同的空缺：“What did you [VP[VP smell 📷] and [VP shoot an arrow at 📷]]?”

歧义（Ambiguity）：在某些情况下，听者能够发现话语中存在着歧义。这里有一些从报纸标题中摘录的例子：

Squad helps dog bite victim.

Police begin campaign to run down jaywalkers.

Helicopter powered by human flies.

Once-sagging cloth diaper industry saved by full dumps.

Portable toilet bombed; police have nothing to go on.

Teacher strikes idle kids.

Include your children when baking cookies.

Hospitals are sued by 7 foot doctors.

Milk drinkers are turning to powder.

Safety experts say school bus passengers should be belted.

但是，大多数时候我们听到的语言似乎是没有歧义的。因此，在20世纪60年代，当研究人员开始使用计算机对语言进行分析的时候，他们非常吃惊地发现，几乎每句话都有很强的歧义，即使对于母语是该种语言的说话者来说，很多解释也不是显而易见的。一个使用大型文法和词典的系统，对于一个非常普通的句子也可能找到上千种解释。词汇歧义（Lexical ambiguity），即一个单词有多种含义，很常见。如，“back”可以是副词（go back）、形容词（back door）、名词（the back of the room）或动词（back up your files）。“Jack”可以是名字、名词（纸牌名、抛接子游戏、航海用的旗子、一种鱼、插座或千斤顶）或动词（顶起汽车、用灯捕鱼、用力击打棒球）。句法歧义（Syntactic ambiguity）涉及到有多种解释的短语：“I smelled a wumpus in 2,2”有两种分析：一种解释中介词短语“in 2,2”修饰名词，另一种解释中它修饰动词。句法歧义会导致语义歧义（semantic ambiguity），因为其中一种分析意味着wumpus（怪兽）出现在（2,2）的位置，另一种则意味着在（2,2）的位置有臭气。在这种情况下，采用错误的解释会对Agent造成致命的错误。

最后，在字面意义和比喻意义之间也会存在歧义。在诗歌中言语的修辞非常重要，不过在日常用语中也令人惊讶地普遍。借喻（metonymy）是用一种事物代表另一种事物的修辞手法。当我们听到“Chrysler announced a new model（克莱斯勒公司公布了一种新车型）”时，我们并不会将其解释为公司能说话，相反，我们明白是代表该公司的发言人宣布了这个公告。借喻使用很广，而且听者经常能下意识地进行解释。不幸的是，我们所写出的文法很难做到这么机灵。为了正确地处理借喻的语义，我们需要引入全新层次的歧义。我们通过为语句中的每个短语的语义解释提供两个对象来实现这一目标：一个是短语在字面上指代的对象（Chrysler），另一个是借喻所指代的对象（即发言人）。那么，我们可以说在此二者之间存在某种关系。在我们当前的文法中，“Chrysler announced”被解释成

$$ x=\mathrm{Chrysler}\land e\in\mathrm{Announce}(x)\land\mathrm{After}(Now,\mathrm{Extent}(e)) $$

我们需要把它变成

$$ x=Chrysler\land e\in Announce(m)\land After(Now,Extent(e))\land Metonymy(m,x) $$

上式的意思是一个等同于 Chrysler 的实体 x，和另一个发布了公告的实体 m，这二者之间存在借喻关系。下一个步骤是确定能够发生何种类型的借喻关系。最简单的情况是不存在借喻——字面对象 x 和借喻对象 m 是相同的：

$$ \forall m,x\ (m=x)\Rightarrow Metonymy(m,x) $$

在 Chrysler 这个例子中，一种合理的推广是一个组织可以用来代表其发言人：

$$ \forall~m,x\quad x\in{O r g a n i z a t i o n s}\land{S p o k e s p e r s o n}(m,x){\Rightarrow}{M e t o n y m y}(m,x) $$

借喻还包括用作者指代作品（如：I read Shakespeare），或者是更一般的是用生产者指代产品（如：I drive a Honda），以及用部分指代整体（如：The Red Sox need a strong arm）（“红袜队需要一只强壮的臂膀”，这里用“臂膀”指代了球员——译者注）。某些类似“The ham sandwich on Table 4 wants another beer”（“四号桌火腿三明治想再要一杯啤酒”，这里用顾客所点的食物指代顾客本人——译者注）这样借代的例子比较奇特，需要参考具体场景才能解释。

隐喻（metaphor）是另一种修辞方法，用字面上是某种含义的短语通过类比的方式暗示不同的含义。因此，隐喻也可以看作是一种借喻，只是这里的关系是某种相似性。

消歧（disambiguation）是从话语中还原出最可能的含义的过程。从某种意义上说，我们已经有了解决这个问题的框架：每一条规则都有一个与其相关的概率，因此一个解释的概率就是那些导出该解释的规则的概率的乘积。不幸的是，这种概率反映的是那些短语在训练语法的语料库中有多常见，因此反映出的是一般的知识，而不是在当前情景下的具体知识。为了正确地消歧，我们需要结合四个模型：

（1）世界模型（world model）：一个命题在世界中发生的可能性。按照我们已知道的世界知识，当说话者说“I'm dead”时，更可能意味着“我有大麻烦了”而不是“我的生命已经结束，但我仍旧可以说话”。

（2）构思模型（mental model）：说话者具有向听者传递某一特定事实的意图的可能性。这一方法结合了多种模型：说话者相信什么、说话者相信听者相信什么，等等。例如，当一个政客说，“I am not a crook”时，世界模型或许会赋予“该政客没有犯罪”这一命题50%的概率，而将99.999%的概率赋予命题“我不是个牧羊人的曲柄杖”。无论怎样，我们选择第一种解释，因为这是最有可能的要表达的东西。

（3）语言模型（language model）：在说话者已有传达某个特定事实的意图的情况下，他选择某个特定单词串的可能性。

（4）声学模型（acoustic model）：在说话者已经选择了一个给定的单词串的情况下，生成一个特定的语音序列的可能性。23.5节将介绍语音识别。

23.4 机器翻译

机器翻译是把文本从一种自然语言（源语言）自动翻译成另一种语言（目标语言）。机器翻译是人们最早设想的计算机应用领域之一（Weaver，1949），但广泛应用这项技术是近十年的事。下面是本书第一页中的一段话：

AI is one of the newest fields in science and engineering. Work started in earnest soon after World War II, and the name itself was coined in 1956. Along with

molecular biology, AI is regularly cited as the "field I would most like to be in" by scientists in other disciplines.

下面是通过在线工具 Google Translate 将其从英语翻译为丹麦语的结果：

AI er en af de nyeste områder inden for videnskab og teknik. Arbejde startede for alvor lige efter Anden Verdenskrig, og navnet i sig selv var opfundet i 1956. Sammen med molekyläer biologi, er AI jaøvnligt nævnt som "feltet Jeg ville de fleste gerne være i" af forskere i andre discipliner.

考虑那些不懂丹麦语的人，下面给出的是将丹麦语重新翻译回英语的结果。与原文不同的单词用斜体字标出：

AI is one of the newest fields of science and engineering. Work began in earnest just after the Second World War, and the name itself was invented in 1956. Together with molecular biology, AI is frequently mentioned as “field I would most like to be in” by researchers in other disciplines.

这些不同都是合理的释义，例如 regularly cited 变为 frequently mentioned。唯一真正的错误是丢失了冠词 the，文中用符号 └ 表示。这是典型的精确：在这两句话中，有一句包含了一个母语说话人不会犯的错误，但原文的意思还是被清晰传递了。

历史上有三种主要的机器翻译应用。粗糙翻译（Rough translation），如在线服务免费提供的功能，能给出外语语句或文档中的“要点”，但包含一些错误。编辑前翻译（Pre-edited translation），用于一些公司制作多语言文档和销售材料。源文本是用受限语言编写的，所以可以比较容易地进行自动翻译，通常这些翻译的结果会经过人工编辑修正其中的错误。源语言受限翻译（Restricted-source translation），其工作过程是全自动的，但只适用于高度模式化的语言，例如天气报告。

在完全一般的情况下，由于需要对文本的深层次理解，因而翻译非常困难。即使对于非常简单的文本而言——哪怕“文本”只包含一个词语——也是困难的。考虑出现在某个商店门上的单词“open” $ ^{1} $。它传达的意思是当时该商店可以接待顾客。现在考虑出现在某个新近建好的商店外的横幅上的单词“open”。它意味着该商店现在开始日常运营，但是，即使晚上商店关门后而没有拆除该横幅，看到它的人也不会被误导。这两个标志用了相同的词语却表达了不同的含义。类似的情况在德国，门上标记会用“offen”，而横幅上的标记则是“Neu Eröffnet”。

问题在于不同的语言对于世界的分类是不同的。例如，法语单词中的“doux”涵盖的意义广泛，近似于对应英语单词“soft”、“sweet”以及“gentle”等。类似地，英语单词“hard”差不多涵盖了德语单词“hart”（身体对抗的，残酷的）的所有用法以及单词“schwierig”（困难的）的部分用法。因此，表示句子的含义对翻译而言比对单一语言理解更困难。英语分析系统可以使用类似Open(x)的谓词，但是对于翻译，其表示语言必须进行更多的区分，

也许要用 $ Open_{1}(x) $ 表示“Offen”的含义，而 $ Open_{2}(x) $ 表示“Neu Eröffnet”的含义。对于一组语言，能够进行所有必要区分的表示语言被称为中间语言（interlingua）。

翻译者（人或机器）通常需要去理解源文本所描述的实际情景而不仅仅是理解一个个独立的单词。例如，要把英语单词“him”翻译成韩语，一个必须要做出的选择是判断是谦语还是敬语，这个选择取决于说话者和“him”所指代的人之间的社会关系。在日语中，敬语是关系词，因此在做选择时应考虑到说话者、指代者和听者三者之间的社会关系。翻译者（人或机器都是如此）有时发现很难做出选择。如另一个例子，要把“The baseball hit the window. It broke.”翻译成法语，我们要为“it”选择阴性的“elle”或者阳性的“il”作为其翻译，因此我们必须确定“it”指代的是 baseball 还是 window。为了得到正确的翻译结果，我们既要懂语言，还需要懂物理。

有时根本无法得到让人完全满意的翻译。例如，一首意大利爱情诗人用阳性词“il sole”（太阳）和阴性词“la luna”分别代表一对情侣，当把它翻译成德语时就需修改，因为德语中这两者的阴性正好相反，而如果在翻译目标语言中的二者阴阳性相同，还需要进一步的修改。 $ ^{1} $

23.4.1 机器翻译系统

所有机器翻译系统都必须对源语言和目标语言建模，但不同的系统使用的模型也不一样。一些系统尝试对源文本进行完整分析，得到中间语言知识表示，再从这种表示中生成目标语言的句子。这样做很困难，因为其中包含了三个未解决的问题：为所有事物构建一个完全的知识表示；将语言分析成该表示；从该表示中生成句子。

其他系统是基于转换模型（transfer model）的。这类系统有一个翻译规则（或实例）数据库，一旦规则（或实例）获得匹配，就可直接翻译。转换可以发生在词法、句法以及语义层次上。例如，一条严格的句法规则可将英语的Adjective Noun映射为法语的Noun Adjective。一条混合了句法和词法的规则可将法语的[ $ S_1 $ “et puis” $ S_2 $]映射为英语的[ $ S_1 $ “and then” $ S_2 $]。图23.12图解了各种转换点。

图 23.12 Vauquois 三角形：机器翻译系统中各种选择的示意图（Vauquois，1968）。我们从位于顶部的英语文本开始。基于中间语言的系统沿着实线前进，首先对英语进行句法分析形成句法形式，然后转换为语义表示和中间语言表示，再生成法语的语义、句法及词汇形式。基于转换的系统可以利用虚线作为捷径。不同的系统在不同的点进行转换；有些系统可以在多点进行转换

23.4.2 统计机器翻译

现在我们已经认识到了翻译任务是多么复杂，因此，我们也不会感到惊奇，最成功的机器翻译系统是用大量文本语料库的统计信息来训练概率模型而建立起来的。这种方法并不需要一个复杂的中间语言概念本体，不需要手工建立源语言和目标语言的语法，也不需要人工标记的树库。它所需要的只是数据——翻译实例，从这些翻译实例中可以学习得到翻译模型。例如，为了把一个英语句子(e)翻译成法语(f)，我们选择使f*值最大的字符串：

$$ f^{*}=\operatorname{argmax}P(f|e)=\operatorname{argmax}P(e|f)P(f) $$

其中因子 $ P(f) $ 是为目标语言法语所建的语言模型（language model），它表示一个给定的句子有多大可能性在法语中出现。 $ P(e|f) $ 是翻译模型（translation model），它表示一个英语句子有多大可能性是给定的法语句子的译文。类似， $ P(f|e) $ 是从英语到法语的翻译模型。

我们应该直接使用 $ P(f|e) $、还是应用贝叶斯公式使用 $ P(e|f)P(f) $ 呢？在医学等诊断（diagnostic）应用中，按照因果关系方向为领域建模要更简单：使用 $ P $(症状|疾病)而不是 $ P $(疾病|症状)。但对于翻译来说，两个方向同样简单。最初的统计机器翻译工作是使用了贝叶斯规则——部分是因为研究者已经有了很好的语言模型 $ P(f) $，想利用好它；部分是因为这个方法源自语音识别的背景，语音识别也是一个诊断问题。我们在本章中也将采取这一方法，但我们注意到在最近统计机器翻译的工作中经常直接对 $ P(f|e) $ 进行优化，使用更复杂的模型，考虑了很多从语言模型中提取的特征。

语言模型 $ P(f) $ 可以考虑图 23.12 右半部分的任意层，但最简单最常用的方法是从法语语料库中建立一个 n 元语法模型，就像我们之前所看到的。这样处理只能捕获法语句子的部分的、局部的信息，但对于粗略的翻译也通常够用了。 $ ^{1} $

翻译模型是从双语语料库中学习得到的，双语语料库是一个平行文本集合，由一个个英语/法语对组成。现在，如果我们有个无限大的语料库，那么翻译一个句子就只是一项查找任务了：如果我们在语料库中找到了该英语句子，我们就只要返回对应的法语句子就可以了。但是我们的资源肯定是有限的，需要翻译的句子大多数也都是新的。然而，这些句子可以视为由我们之前见过的短语构造而成（即使有些短语只有一个单词）。例如，在本书中，常见短语包括“in this exercise we will,”（在这个练习中我们将——译者注），“size of the state space”（状态空间的大小——译者注），“as a function of the（作为……的一个函数——译者注）”，以及“notes at the end of the chapter”（本章结尾的注释——译者注）。当我们要把新的英语句子“In this exercise we will compute the size of the state space as a function of the number of actions”翻译成法语时，我们应当可以将句子分割成若干短语，在英语语料库（本书）中找到这些短语，再找到对应的法语短语（从本书的法语版中找），然后再按照法语的意义将这些法语短语依次拼接起来。也就是说，给定一个英语源句子e，要找到它的法语翻译句子f，可按照三个步骤进行：

（1）将英语句子分割成短语 $ e_{1}, \cdots, e_{n} $

（2）对于每个短语 $ e_i $，选择与其对应的法语短语 $ f_i $。我们用标记 $ P(f_i | e_i) $ 表示短语 $ f_i $ 是短语 $ e_i $ 的翻译的概率。

（3）为短语 $ f_1, \cdots, f_n $ 选择一个排列，我们用一种略显复杂的方法来描述该排列，但采用的一种简单的概率分布：对于每个 $ f_i $，我们选择一个扭曲度变量（distortion） $ d_i $，表示 $ f_i $ 相对于 $ f_{i-1} $ 移动的单词数目，正数代表向右移动，负数代表向左移动，零表示 $ f_i $ 恰好在 $ f_{i-1} $ 之后。

图 23.13 展示了一个例子的过程。在图的顶部，句子“There is a smelly wumpus sleeping in 22”（2,2 处有一只难闻的怪兽正在睡觉）被分割成了五个短语 $ e_1, \cdots, e_5 $。每个短语都被翻译成了相应的短语 $ f_i $，并且排列成 $ f_1 $、 $ f_3 $、 $ f_4 $、 $ f_2 $、 $ f_5 $ 的顺序。我们用扭曲度变量 $ d_i $ 来描述排列， $ d_i $ 的定义是：

$$ d_{i}=\mathrm{S T A R T}(f_{i})-\mathrm{E N D}(f_{i-1})-1 $$

其中 $ \operatorname{START}(f_i) $ 是法语句子中短语 $ f_i $ 的第一个单词在句中的序号，而 $ \operatorname{END}(f_{i-1}) $ 是短语 $ f_{i-1} $ 中最后一个单词的序号。在图 23.13 中我们发现 $ f_5 $ “à 22” 紧跟在 $ f_4 $ “qui dort” 之后，因此 $ d_5=0 $。然而短语 $ f_2 $ 在 $ f_1 $ 右侧移动了一个单词，因此 $ d_2=1 $。作为特例 $ d_1=0 $，这是因为 $ f_1 $ 从位置 1 开始，而 $ \operatorname{END}(f_0) $ 定义为 0（虽然 $ f_0 $ 不存在）。

在定义了扭曲度变量 $ d_i $ 之后，我们可以定义扭曲度的概率分布 $ \mathbf{P}(d_i) $，注意到句子的长度被限定为 $ n $，我们有 $ |d_i| \leq n $，从而完全概率分布 $ \mathbf{P}(d_i) $ 只包含 $ 2n+1 $ 个元素，比全排列的数目 $ n! $ 要小得多。这就是我们采取了这种特别的方法来定义排列的原因。当然，这是一种相当弱的扭曲度模型。扭曲度并非在表达当我们把英语翻译成法语时形容词通常会改变位置出现在名词的后面这种事实，这类事实是由法语的语言模型 $ P(f) $ 来表示的。扭曲的概率完全独立于短语中的单词——它只依赖于整数值 $ d_i $。这种概率分布提供了排列变化的整体描述，例如，考虑 $ P(d=2) $ 与 $ P(d=0) $，表达的是扭曲度为 2 的可能性与扭曲度为 0 的可能性。

现在我们可以把所有这些放在一起工作了：我们可以定义 $ P(f, d|e) $，表示扭曲度为 d 的短语序列 f 是短语序列 e 翻译的概率。我们假设短语的翻译和扭曲度相互独立，因此可以得到下述表达式：

$$ P(f,d\mid e)=\prod_{i}P(f_{i}\mid e_{i})P(d_{i}) $$

上式给出了一种根据候选译文 f 和扭曲度 d 计算 $ P(f, d|e) $ 概率方法。但我们不能通过枚举所有的句子来找到最佳的 f 和 d，在语料库中，一个英语短语可能会对应上百个法语短语，因此会有 $ 100^{5} $ 种三元短语组合翻译，同时每一种组合翻译还有 51 种不同的排列方式。我们必须找到更好的解决方法。在寻找接近最大可能的翻译问题上，将带启发式的局部柱状搜索用于概率估计已经被证明是有效的。

现在就只剩下学习短语概率和扭曲度概率这两个问题了。我们仅给出工作过程的概貌，细节部分可以看本章末的注释。

（1）找到平行文本：首先，搜集双语平行语料库。例如，Hansard $ ^{1} $记录了议会的辩论。加拿大、香港以及其他国家和地区建立了双语的 Hansard，欧盟以 11 种语言发布其官方文件，而联合国也发布多种语言版本的文件。双语语料也可从网上获得，一些网站也通过平行的 URL 发布平行的内容，例如，/en/表示英语页面而/fr/对应法语页面。领先水平的统计翻译系统是在数百万单词的平行文本以及数十亿单词的单语言文本的上进行训练。

（2）分割句子：翻译的单位是句子，因此我们必须把语料分割为句子。句号是很强的句子结尾的标志，但考虑一下“Dr. J. R. Smith of Rodeo Dr. paid \$29.99 on 9.9.09”，其中只有最后一个句号表示句子结束。一种确定句号是否表示句子结束的方法，是根据句号附近单词及其词性特征训练一个模型，该方法的准确率可达到98%。

（3）句子对齐：对于英语语料中的每个句子，找出法语料中与之对应的句子。通常，英语句子和法语句子是1:1对应的，但在有些时候也有变化：某种语言的一个句子可以被分割，从而形成2:1对应，或者两个句子的顺序相互交换，从而导致2:2对应。当仅考虑句子的长度时（即短句应该和短句对齐），对齐这些句子是可能的（1:1,1:2,2:2等），利一种维特比算法（Viterbi algorithm）的变种可以达到99%的准确度。如果使用两种语言的公共标志话，比如数字、日期、专有名词以及我们从双语词典中获得的无歧义的单词，可以实现更好的对齐效果。例如，在第三个英语句子和第四个法语句子中都含有“1989”，而附近的句子中没有，就很好地说明这两个句子是应该对齐的。

（4）短语对齐：在一个句子中，短语的对齐过程与句子对齐的过程类似，但需要迭代改进。开始时，我们没法知道“qui dort”应该与“sleeping”对齐，但我们可以通过经验的累积来发现该对齐。在我们所见过的所有例子中“qui dort”和“sleeping”同时出现的频率较高，而且在对齐的句子中没有哪个词比“qui dort”更频繁地与“sleeping”同时出现。短语对齐的语料可以为我们提供短语级概率（在适当的平滑之后）。

（5）获取扭曲度：一旦我们有了对齐的短语，我们就可以确定扭曲度的概率了。针对每个距离 $ d=0,\pm1,\pm2,\cdots $，简单计算其发生的频率，并应用平滑。

（6）利用 EM 改善估计（EM 期望最大化——译者注）：使用期望最大化方法来提高对 $ P(f|e) $ 和 $ P(d) $ 值的估计。在步骤 E 中，我们根据当前参数的值计算出最佳的对齐方式，然后在步骤 M 中更新估计值，这个过程反复迭代直到收敛。

23.5 语音识别

语音识别（Speech recognition）的任务是根据给定的声学信号来辨识说话人所说的单词序列。它已经成为人工智能的主流应用之一——每天有数百万人通过与语音识别系统交互来完成语音邮件系统导航、用手机进行网上搜索以及其他的应用。在需要不通过手而进行操作的场合，如操作一台机器，语音就是一个很有吸引力的手段。

语音识别很困难，因为说话者所发出的声音模糊不清，并且有很多噪音。有一个著名的例子，如果说得很快，短语“recognize speech”和“wreck a nice beach”几乎是相同的。这个简单的例子就反映了造成语音难题的诸多因素。首先，分割（segmentation）：书写英语单词时，单词之间存在空格，但在快速说话时在，“wreck a nice”中就没有停顿了，而这种停顿可用来区分它是多个单词构成的短语还是单个词“recognize”；第二，协同发音（coarticulation）：当说得快时，单词“nice”结尾的音“s”和单词“beach”开头的音“b”连起来，听起来就像“sp”；还有一个没有在这个例子中表现出来的问题就是同音词（homophones）——类似“to”、“too”和“two”这样的单词具有相同的发音，但它们的意义是不同的。

我们可以把语音识别看作是一个最相似序列解释问题。就像我们在第15.2节中所看到的，给定一个观察序列 $ e_{1:t} $，计算出一个最相似的状态变量串 $ x_{1:t} $。在这里，状态变量是单词，观察值是声音。更准确地说，观察值是从声音信号中抽取的特征向量。通常，可以借助贝叶斯公式来计算最相似序列：

$$ \arg\max\limits_{word_{1:t}}P(word_{1:t}\mid sound_{1:t})=\arg\max\limits_{word_{k:t}}P(sound_{1:t}\mid word_{1:t})P(word_{1:t}) $$

其中 $ P(sound_{1:t}|word_{1:t}) $ 是声学模型（acoustic model）。它描述了单词的发音——“ceiling”（天花板）开头是一个“c”（咝）音，和“sealing”（密封）的发音相同。 $ P(word_{1:t}) $ 被称为语言模型（language model），它描述了每句话的先验概率——例如，“ceiling fan”（吊扇）出现的概率是序列“sealing fan”（密封扇）的 500 多倍。

这种方法由 Claude Shannon（1948）命名为噪声信道模型（noisy channel model）。他描述了一种情况，原始消息（我们例子中的单词 word）通过一个噪声信道（例如电话线）传到另一端，我们接收到的是受到干扰的消息（我们例子中的声音 sound）。Shannon 指出，无论信道中的噪声有多大，只要我们对原始消息进行编码时采用了足够冗余的方法，还原的消息就能做到错误足够小。信道噪声模型已经被应用于语音识别、机器翻译、拼写纠错以及其他任务中。

一旦我们定义了声学模型和语言模型，我们就可以使用维特比算法（参见15.2.3节）解决最相似单词串问题。大多数语音识别系统都使用马尔科夫假设的语言模型——当前的状态 $ Word_{t} $只取决于之前的固定数目的n个状态——而 $ Word_{t} $为一个取值来自有限集合的随机变量，这使其成为隐马尔科夫模型（HMM）。因此，语音识别成为HMM方法学的一个简单应用，如同在15.3节描述的一样——它很简单，只要我们定义了声学和语言模型。下面我们介绍这些模型。

23.5.1 声学模型

声波的在空气中传播时，其压力呈周期性变化。当这些声波撞击到麦克风的振膜时，膜的前后震动就产生了电流。模拟信号到数字信号的转换器按照采样率（sampling rate）所确定的离散间隔测量电流的强度，而电流强度近似对应着声波的振幅。语音的频率一般在100Hz（每秒100个周期）到1000Hz之间，典型的采样率为8kHz。（CD和mp3文件的采样率是44.1kHz）。每次采样的测量精度取决于量化因子（quantization factor）；典型的语音识别系统使用8到12比特（二进制位）。这意味着一套使用8比特量化和8kHz采样率的

低端系统，每分钟语音就需要大约0.5M字节的存储空间。

由于我们只需要判断所说的单词是什么，而不是如何精确地表示它们，因此我们没必要保存所有的信息。只要能区分开不同的话语声音就够了。语言学家定义了大约100种话语声音，或称为音节（phones），这些音节可以组合成已知的所有人类语言中的所有词汇。粗略地讲，音节是与单个元音或者辅音字母相对应的发音，但也有一些复杂情况：诸如“th”和“ng”之类的字母组合也产生单个音节，而且有些字母在不同的上下文中会产生不同的音节（例如，单词rat和rate中的字母a）。图23.14列出了英语中使用的所有音节，并提供了每个音节的例子）。音素（phoneme）是对于使用某种特定语言的话人具有独特意义的最小发音单位。例如，对于说英语的人来说，单词“stick”中的“t”和单词“tick”中的“t”非常相似的，是同一个音素。但是在泰语中它们的区别是明显的，因此被当作两个音素。为了表示所有的英语发音，我们需要一种方法能表示不同的音素，但不需要区分声音中那些非音素的变化：声音大或是小，快或是慢，男声或是女声等。

首先，我们发现，虽然语音中的音频可能达到几千赫兹，但信号内容的变化却不那么频繁，变化的频率最多不超过100Hz。因此，语音系统将时间切片上的信号特性概括为“帧”（frame）。一个长度为10毫秒的帧（即，对于8kHz的采样率而言，这对应于80个样本）就已经足够短了，很少有短时现象会被忽略。帧之间可以重叠，这样就能确保不会漏掉出现在帧边界上的信号。

每一帧都表示为一个特征向量。从语音信号中选出特征就如同在听交响乐时说：“这里法国号演奏响亮，小提琴则演奏轻柔。”下面我们简要介绍一个典型系统的特征。首先，我们使用傅里叶变换确定大约一打频率的声音总能量。然后，我们计算Mel频率倒谱系数（mel frequency cepstral coefficient，MFCC），或者每一个频率的MFCC。同时我们也计算每帧的总能量。这样得到了13个特征，对于每个特征我们再计算出当前帧与前一帧的差别，以及这些差别的变化，这样一共得到39个特征。这些特征都是取连续值，使它们适合HMM模

型的最简单方法是将这些值离散化。（另一种可能的方法是拓展HMM模型，使其接受连续混合高斯模型。）图23.15展示了从原始声音到带有离散特征的帧序列的转换过程。

我们已经看到了如何从原始音频信号转换成一系列观察值，$\mathbf{e}_t$。现在我们需要描述 HMM 中的（观察不到的）状态，并且定义转移模型 $\mathbf{P}(\mathbf{X}_d|\mathbf{X}_{t-1})$ 和感知模型 $\mathbf{P}(\mathbf{E}_d|\mathbf{X}_t)$。转移模型可以被分解为两层：单词和音节。我们将从底层开始：音节模型（phone model）把一个音节描述为三种状态：开始、中间和结束。例如，音节[t]有一个不发声的起始，然后在中间是一个小爆破，结尾处（通常）发出嘶嘶声。图 23.16 展示了音节[m]的例子。注意，在通常的说话中，平均一个音节持续 50～100 毫秒，即 5～10 帧。在这个持续过程中，自循环的变化是允许的。通过进行许多次自循环（尤其是在中间状态），我们可以表现出一长串“mmmmmmmmmmmm”声音。绕过自循环则产生一个短“m”声音。

在图 23.17 中，音节模型被串起来形成一个单词的发音模型（pronunciation model）。根据文献 Gershwin（1937），你会将其读作[t ow m e y t ow]，而我会把它读作[t ow m a a t ow]。图 23.17（a）显示了针对方言变化的转移模型。其中的每一个圆圈表示一个类似图 23.16 中的音节模型。

除了方言变化，单词还可以有协同发音（coarticulation）变化。例如，发[t]这个音节时舌头是在口腔上部，而发[ow]音时舌头是在口腔底部。当说得快时，舌头没有时间到达[ow]的位置，这时我们发出的是[tah]音而非[tow]。图23.17（b）给出了“tomato”的模型，其中考虑到了协同发音的影响。更复杂的音节模型还考虑到了音节的上下文影响。

这样可能会对一个单词的发音造成实质上的变化。“because”最常见的发音是[b i y k a h z]，但这仅仅占所使用情况的四分之一左右。另外四分之一（大概）的情形将第一个元音替换为[iːx]、[ɪh]或[aːx]，其余的情形会将第二个元音替换为[aːx]或[aːa]，将最后一个[z]替换为[zːh]或[s]，或者完全丢弃“be”，只剩下“cuz”。

23.5.2 语言模型

对于一般目的的语音识别而言，语言模型可以是从书面句子的文本语料中学习得到的n元模型。但是，口语和书面语相比有不同的特点，因此最好能有一个口语的转录文本语料库。对于特定任务的语音识别而言，训练语料库也应该是与特定任务相关的：如要构建航班预定系统，可利用历史电话的转录文本记录。如果有和特定任务相关的词汇表也会有所帮助，例如所有机场和可供服务的城市的清单、以及所有的航班号等。

在语音用户界面的设计中，部分工作是要求用户的说话受限于一个候选集合，因此语音识别器可以用一个更紧凑的概率分布进行处理。例如，用户问“您想去哪个城市？”，利用高度约束的语言模型可以得到回答，而问“我可以怎么帮您？”则无法得到回答。

23.5.3 构建语音识别器

语音识别系统的质量依赖于它的各部分的质量——这些组成部分包括语言模型、单词发音模型、音节模型以及用于从声学信号中提取频谱（spectral）特征的信号处理算法。我们已经讨论过如何从书面文本语料中构造语言模型，而把关于信号处理的细节留给了其他教科书。现在还剩下发音和音节模型。关于发音模型的结构——如图23.17所示的tomato模型——通常是手工构建的。现在对于英语和很多其他语言，已经可有了很多大型语音词典，尽管它们的精确度良莠不齐。三状态音节模型的结构对于所有的音节都是一样的，如

图 23.16 所示。现在就剩下概率了。

与以往一样，我们将从语料库中获取概率，只不过这次用的是语音语料库。最常见的语料库是包括每个句子的语音信号和对应的单词文本。从这样的语料库中构建模型比构建文本的n元模型更困难，因为我们必须构建一个隐马尔科夫模型——每个单词的音节序列和每帧的音节状态都是隐含变量。在早期的语音识别中，通过耗费人力的声谱图人工标注提供隐含变量。近期的系统使用期望最大化方法自动提供缺少的数据。想法很简单：给定一个HMM和一个观测序列，我们可以使用15.2节和15.3节中的平滑算法计算出每个时间步上的每个状态的概率，并通过一个简单的扩展，得到相继时间步上的状态-状态对的概率。可以把这些概率看作不确定标记。根据这些不确定标记，我们能够估计出新的转移概率和感知概率，并重复EM（期望最大化）过程。该方法能够保证在每次迭代中不断提高模型和数据之间的吻合度，并且通常收敛到一个比最初的手工标注所提供的参数值好得多的结果。

最准确的系统会为每一个说话者训练出不同的模型，因此也可以捕获方言之间、男声和女声之间以及其他各种变化。这种训练可能要求与说话者交互若干个小时，因此应用最广泛的系统并不会建立说话者特定的模型。

系统的准确性取决于多种因素。首先，信号质量有影响：一个在隔音房中、方向对准固定嘴巴的、高质量的麦克风的效果要比来自行驶中开着收音机的汽车、通过电话线传输的廉价麦克风的效果要好得多。词汇表的规模也有影响：使用11个单词的词汇表（1～9加上“oh”和“zero”）识别数字串时，错误率低于0.5%，如识别有2000单词量的新闻故事时，错误率上升到了10%，而对于一个包含64 000个单词的语料库，错误率则达到了20%。具体任务也有影响：当系统试图去完成一个特定的任务——如预定航班或者给出餐馆方向——对于这些任务，就算单词错误率在10%甚至以上，通常也可以取得满意的效果。

23.6 本章小结

自然语言理解是 AI 最重要的子领域之一。不同于 AI 的其他领域，自然语言理解需要针对真实人类行为的经验性研究——这些又显得复杂而又有趣。

形式语言理论以及短语结构(phrase structure)文法(特别是上下文无关(context-free)文法)在处理自然语言的某些方面是有用的工具。概率上下文无关文法（PCFG）的形式体系已被广泛应用。

使用 CYK 算法这类图分析器（chart parser）分析上下文无关语言的句子，可以在 $ O(n^3) $ 的时间内处理，这需要文法规则采用乔姆斯基范式（Chomsky Normal Form）。

树库（treebank）可以用于学习文法。也可以从未分析的句子语料库中学习得到文法，但这并不是很成功。

词汇化 PCFG（lexicalized PCFG）可以表达出一些单词之间更普遍的联系。

对文法进行扩展（augment）以解决主语-动词一致性和代词格这类问题也很方便。确定子句文法（Definite clause grammar，DCG）是一种扩展形式体系。利用DCG，分析和语义解释（甚至生成）都可以通过逻辑推理完成。

语义解释（Semantic interpretation）也可以通过扩展文法来处理。

● 歧义（Ambiguity）是自然语言理解中一个十分重要的问题，大多数句子都有多种可能的解释，但通常只有一种是最贴切的。消歧依赖于关于世界的知识、关于当前环境的知识以及关于语言的知识。

• 机器翻译（Machine translation）系统已经采用了一系列的技术进行实现，从完全的句法和语义分析到基于短语频率的统计技术。当前统计模型最受欢迎也做得最成功。

语音识别（Speech recognition）系统基本上也是基于统计原则的。尽管还不够完美，语音系统仍然受到欢迎，也很有用。

总的来说，机器翻译和语音识别是自然语言技术中两个重大成功。这些模型表现良好的原因之一是有了语料库——翻译和语音这两项任务都是人们每天经常进行的。相反，类似句子分析等任务就不那么成功，部分由于没有经过分析的大规模语料库，部分由于分析本身并不那么有用。

参考文献与历史注释

像语义网一样，上下文无关文法（也称为短语结构文法）是一项技术的重复发明，该技术首先被印度文法家（尤其是 Panini，大约公元前 350 年）用于研究印度法典中的梵语（Ingerman，1967）。诺姆·乔姆斯基（1956）重新使用该技术，用于英语句法分析，而约翰·巴克斯也独立地将该技术用于 Algol-58 句法的分析。Peter Naur 扩展了巴克斯的符号系统，现在 BNF 中的 “N” 就是指 Naur，BNF 原本代表的是 “巴克斯范式”（Backus Normal Form）中的 “Normal”（Backus，1996）。Knuth（1968）定义了一种被称为属性文法（attribute grammar）的扩展文法，该文法对程序设计语言非常有用。Colmerauer（1975）引入了确定子句文法，Pereira 和 Shieber（1987）对其进行了发展和推广。

Booth（1969）和 Salomaa（1969）研究了概率上下文无关文法（Probabilistic context-free grammars）。Charniak（1993）、Manning 和 Schütze（1999）、Jurafsky 和 Martin（2008）介绍了其它 PCFG 相关算法。Baker（1979）介绍了通过向内向外算法来学习 PCFG，Lari 和 Young（1990）则描述了它的用途和局限性。Stolcke 和 Omohundro（1994）说明了如何通过合并贝叶斯模型来学习文法规则。Haghighi 和 Klein（2006）描述了基于原型的学习系统。

词汇化的 PCFG（Lexicalized PCFGs）（Charniak，1997；Hwa，1998）结合了 PCFG 与 n 元模型的优点。Collins（1999）描述了通过头特征进行词汇化的 PCFG 句法分析。Petrov 和 Klein（2007a）介绍了在不进行词法扩展的情况下，通过从带通用范畴的树库中学习特定句法范畴来实现词汇化的优点；例如，可以从含有范畴 NP 的树库中学习出 $ NP_{O} $ 与 $ NPs $ 等更具体的范畴。

不论是在“纯粹的”语言学还是在计算语言学中，都有很多研究尝试写出自然语言的形式文法。已有一些关于英语的很全面但是非形式化的文法（Quirk等，1985；McCawley，1988；Huddleston和Pullum，2002）。从20世纪80年代中期开始，词典的信息更多、文法的信息更少已成为一种趋势。词汇功能文法（Lexical-functional grammar），即LFG（Bresnan，

1982)，是第一个重要的高度词汇化的文法形式化体系。如果我们把词汇化推到极致，我们最终就得到只有两条语法规则的范畴文法（Clark 和 Curran，2004），或只包含单词间关系而没有句法范畴的依存文法（Smith 和 Eisner，2008；Kübler 等，2009）。Sleator 和 Temperley（1993）描述了一个依存关系句法分析器。Paskin（2001）指出依存文法比 PCFG 更容易学习。

第一个计算机实现的句法分析算法是由 Yngve（1955）给出的。在 20 世纪 60 年代晚期一些高效的算法逐步发展起来，之后走了一些弯路（Kasami，1965；Younger，1967；Earley，1970；Graham 等，1980）。Maxwell 和 Kaplan（1993）证明了增强的图分析法能够在一般情况下有效。Church 和 Patil（1982）研究了句法歧义的消解问题。Klein 和 Manning（2003）描述了 A*句法分析，Pauls 和 Klein（2009）将它扩展为 K 最佳 A*句法分析，该方法产生 K 个最好的分析结果，而不是单一的结果。

现在最好的句法分析器包括：Petrov 和 Klein（2007b）的分析器在华尔街日报语料上的准确率达到 90.6%；Charniak 和 Johnson（2005）的分析器的准确率达到 92.0%；Koo 等人（2008）的分析器在宾州树库上的准确率达到 93.2%。这些数字没有直接的可比性，该领域有一些批评指出，这些研究只集中在几个挑选过的语料库上，可能过于拟合这些语料了。

自然语言的形式语义解释起源于哲学和形式逻辑，特别是 Alfred Tarski（1935）在形式语言的语义方面的工作。Bar-Hillel（1954）首先考虑了语用问题，并提出了用形式逻辑来处理语用的思想。例如，他把 C.S. Peirce（1902）的术语 indexical（索引词）引入到语言学中。Richard Montague 的文章 “English as a formal language”（1970）可以视为关于语言的逻辑分析的一个宣言，但是 Dowty 等的著作（1991）以及 Portner 和 Partee 的著作（2002）的可读性更好。

第一个用于解决实际任务的 NLP 系统很可能就是 BASEBALL 问答系统（Green 等，1961），该系统能够处理有关棒球统计数据库的问题。这之后不久，Woods（1973）研制了 LUNAR 系统，用于回答有关通过阿波罗计划从月球带回来的岩石的问题。Roger Schank 和他的学生构建了一系列完成语言理解任务的程序（Schank 和 Abelson，1977；Schank 和 Riesbeck，1981）。语义解释现在的方法通常假设从语法到语义的映射可以从例子中学习得到（Zelle 和 Mooney，1996；Zettlemoyer 和 Collins，2005）。

Hobbs 等人（1993）描述了语义解释方面的一个量化的非概率框架结构。更多最近的研究都遵循显式的概率框架（Charniak and Goldman，1992；Wu，1993；Franz，1996）。在语言学中，最优化理论（Kager，1999）是建立在这样的思想基础上的：在语法中构建软约束，给予解释一个自然的排序（类似于概率分布），而不是让语法以相同的序生成所有概率。Norvig（1988）讨论了考虑多个同时出现的解释的问题，而不是固定采用唯一的最大似然率解释。文艺评论家们（Empson，1953；Hobbs，1990）则提出了“歧义应该被消解还是应该被保留”的疑问。

Nunberg（1979）勾画了一个有关转喻的形式化模型。Lakoff 和 Johnson（1980）则致力于英语中常见暗喻的分析和编目研究。Martin（1990）和 Gibbs（2006）为暗喻解释提供了一种计算模型。

文法归纳（grammar induction）的第一个重要成果是负面的：Gold（1967）证明了在

给定一个来自某上下文无关文法的字符串集合的情况下，可靠地学习到正确的文法是不可能的。很多著名的语言学家，如乔姆斯基（1957）和Pinker（2003），根据Gold的结果认为必定存在一个先天的、每个小孩从出生开始就拥有普通语法（universal grammar）。所谓的刺激贫乏观点认为学习CFG时小孩并没有足够的输入，因此它们必须已经“知道”了文法，所做的只不过是调整某些参数而已。尽管很多乔姆斯基学派的语言学家一直支持这个观点，某些其他的语言学家（Pullum，1996；Elman等人，1997）和大部分计算机科学家却抛弃了该观点。早在1969年，Horning就指出在PAC学习的意义上学习一种概率的上下文无关文法是可能的。从那时起，涌现出许多仅从正例中进行学习的令人信服的实验，诸如Mooney（1999）的ILP研究、Muggleton和DeRaedt（1994）的研究、Nevill-Manning和Witten（1997）的序列学习、Schütze（1995）出色的博士论文以及de Marcken（1996）的研究等。现在有每年一届的文法推理国际会议（ICGI）。学习其他文法形式也是可能的，如正规语言（Denis，2001）以及有限状态自动机（Parekh和Honavar，2001）。Abney（2007）是一本介绍半监督学习语言模型的教材。

Wordnet（Fellbaum，2001）是一个公开的字典，包含大约100 000个单词和短语，这些单词和短语按照词性进行分类，并通过同义、反义以及部分整体等语义关系联系起来。Penn 树库（Marcus 等，1993）提供了300万词英文语料的分析树。Charniak（1996）、Klein 和 Manning（2001）讨论了用树库文法进行句法分析。英国国家语料库（Leech 等，2001）包含大约1亿单词，而万维网则包含超过万亿的单词；（Brants 等，2007）描述了超过两万亿词的Web语料上的n元模型。

在 20 世纪 30 年代，Petr Troyanskii 为一台“翻译机器”申请了专利，但是当时还没有计算机来实现他的思想。1947 年 3 月，洛克菲勒基金的 Warren Weaver 致信 Norbert Wiener，提出机器翻译也许是可能的。借鉴密码学和信息论的工作，Weaver 写道：“当我看到一篇俄语文章时，我对自己说：‘这实际是用英语写的，但是它用了一些奇怪的符号进行编码。我现在就进行解码。’”在接下来的十年间，大家都试图用这种方法进行解码。IBM 在 1954 年展示了一个初级系统。Bar-Hillel（1960）描述了这个时期的热潮。然而，美国政府随后宣布（ALPAC，1966）“实用的机器翻译还没有直接的或可预期的前景”。然而，有限的工作仍在继续开展，从 20 世纪 80 年代开始，计算机的能力大大提高，ALPAC 的观点不再正确。

本章描述的基本的统计方法是基于 IBM 工作组的早期工作（Brown 等，1988，1993）以及 ISI 和谷歌研究小组的近期工作（Och 和 Ney，2004；Zollmann 等，2008）。Koehn（2009）介绍统计机器翻译的教科书、Kevin Knight（1999）的简短教程都很有影响力。早期的句子切分的研究工作是由 Palmer 和 Hearst（1994）完成的。Och 和 Ney（2003）以及 Moore（2005）讨论了双语句子的对齐问题。

语音识别的历史可以追溯到20世纪20年代的Radio Rex，一只语音控制的玩具狗。听到单词“Rex！”（或其他足够响亮的单词）时，Rex就会跳出它的狗窝。一些更为严肃的工作开始于二战之后。AT&T Bell实验室构造了一个系统，该系统通过声学特征的简单模式匹配进行独立数字的识别（Davis等，1952）。从1971年开始，美国国防部的国防高级研究计划局（DARPA）资助了四个为期五年的竞争性项目，以开发高性能的语音识别系统。优胜者是CMU的HARPY系统（Lowerre和Reddy，1980），它是唯一一个满足在1000词

汇上准确率达到90%的系统。HARPY的最终版本源自CMU的研究生James Baker（1975）构建的名为DRAGON的系统；DRAGON首先将HMM用于语音处理。几乎同时，IBM的Jelinek（1976）开发了另外一个基于HMM的系统。最近几年的研究表现出稳步前进、大数据集和模型、在更真实的语音任务开展激烈竞争等特点。1997年，Bill Gates预测，“五年后，PC机将面目全非，因为语音将进入交互界面”。虽然预言没有实现，但是在2008年，他又预测“未来五年，微软希望更多的互联网搜索将通过语音完成，而不是通过敲击键盘完成”。历史将会告诉我们他这次是否正确。

语音识别方面有很多好的教科书（Rabiner 和 Juang，1993；Jelinek，1997；Gold 和 Morgan，2000；Huang 等，2001）。本章讲述的内容基于 Kay、Gawron 和 Norvig（1994）的综述以及 Jurafsky 和 Martin（2008）的教科书。语音识别方面的研究工作发表在 Computer Speech and Language, Speech Communications, IEEE Transactions on Acoustics, Speech, and Signal Processing, DARPA 的语音和自然语言处理研讨会，以及 Eurospeech、ICSLP 和 ASRU 会议上。

Ken Church（2004）表明，自然语言的研究是在以数据为中心（经验主义）与以理论为中心（理性主义）之间循环。语言学家 John Firth（1957）预测“你可以通过一个词周围的词知道它的意思”。尽管当时没有现在的计算能力，20世纪40年代和50年代早期的语言学研究在很大程度上还是依赖于词频。后来诺姆（乔姆斯基，1956）指出了有限状态模型的局限性，激发了句法理论研究的兴趣而不再关注频率计数。这种方法占统治地位长达20年，直到经验主义依靠统计语音识别的成功工作而重新兴起（Jelinek，1976）。现在，大部分工作都接受统计框架，但主要兴趣是在构建考虑了高级模型的统计模型上，如句法树和语义关系，而不只是单词序列。

语言处理应用方面的工作发表在两年一度的应用自然语言处理会议（Applied Natural Language Processing conference，ANLP）、自然语言处理的经验主义方法会议（conference on Empirical Methods in Natural Language Processing，EMNLP）和 Natural Language Engineering 期刊上。更加广泛的自然语言处理工作发表在 Computational Linguistics 期刊、ACL 以及 COLING 会议上。

习题

23.1 阅读一遍下面的短文并加以理解，尽可能地记下其中的内容。后面会有一个测试：

The procedure is actually quite simple. First you arrange things into different groups. Of course, one pile may be sufficient depending on how much there is to do. If you have to go somewhere else due to lack of facilities that is the next step, otherwise you are pretty well set. It is important not to overdo things. That is, it is better to do too few things at once than too many. In the short run this may not seem important but complications can easily arise. A mistake is expensive as well. At first the whole procedure will seem complicated. Soon, however, it will become just another facet of life. It is difficult to foresee any end to the necessity for this.

task in the immediate future, but then one can never tell. After the procedure is completed one arranges the material into different groups again. Then they can be put into their appropriate places. Eventually they will be used once more and the whole cycle will have to be repeated. However, this is part of life.

23.2 HMM 文法本质上是一个标准的 HMM，其状态变量 $ N $（非终结符，取值包括 Det、Adjective、Noun 等），其观察变量是 $ W $（单词，如 duck 等）。HMM 模型包括起始概率 $ \mathbf{P}(N_0) $、转移模型 $ \mathbf{P}(N_{t+1} | N_t) $、感知模块 $ \mathbf{P}((W_t | N_t) $。请说明任何 HMM 文法都可以改写成 PCFG。[提示：首先考虑如何利用 PCFG 表示句子符号的规则来表示 HMM 文法的起始概率。考虑具体的 HMM 会有所帮助，比如取 $ A $、 $ B $ 代表 $ N $，取 $ x $、 $ y $ 代表 $ W $。]

23.3 考虑下面描述简单动词短语的 PCFG:

0.1 : VP → Verb

0.2 : VP → Copula Adjective

0.5 : VP → Verb the Noun

0.2 : VP → VP Adverb

0.5 : Verb → is

0.5 : Verb → shoots

0.8 : Copula → is

0.2 : Copula → seems

0.5 : Adjective → unwell

0.5 : Adjective → well

0.5 : Adverb → well

0.5 : Adverb → badly

0.6 : Noun → duck

0.4 : Noun → well

a. 下面那一项作为 VP 的概率不为 0? (i) shoots the duck well well well (ii) seems the well well (iii) shoots the unwell well badly

b. 产生“is well well”的概率是多少?

c. (b) 中的短语的歧义是哪种类型?

d. 给定任意 PCFG，能否计算它生成恰好由 10 个单词组成的字符串的概率？

23.4 概述 Java 语言（或者任何其他你熟悉的计算机语言）与英语的主要区别，评价二者的“理解”问题。首先可以考虑下面几个方面：文法、句法、语义、语用、组合性、上下文依赖性、词汇歧义、句法歧义、指代发现（包括代词）、背景知识以及“理解”首先意味着什么。

23.5 本题考虑非常简单语言的文法。

a. 写出语言 $ a^{n}b^{n} $ 的上下文无关文法。

b. 写出回文语言（即所有字符串的后半部分是前半部分的逆）的上下文无关文法。

c. 写出复制语言（即所有字符串的后半部分与前半部分相同）的上下文有关文法。

23.6 考虑句子 “Someone walked slowly to the supermarket” 以及由下列单词构成的词典：

Pronoun→someone Verb→walked

Adv→slowly Prep→to

Article→the Noun→supermarket

下面3个文法中哪个与该词典结合能够产生上述句子？画出相应的句法分析树。

(A): (B): (C):

$ S \rightarrow NP\ VP $ $ S \rightarrow NP\ VP $ $ S \rightarrow NP\ VP $

NP $ \rightarrow $ Pronoun NP $ \rightarrow $ Pronoun NP $ \rightarrow $ Pronoun

NP $ \rightarrow $ Article Noun NP $ \rightarrow $ Noun NP $ \rightarrow $ Article NP

VP $ \rightarrow $ VP PP NP $ \rightarrow $ Article NP VP $ \rightarrow $ Verb Adv

VP $ \rightarrow $ VP Adv Adv VP $ \rightarrow $ Verb Vmod Adv $ \rightarrow $ Adv Adv

VP $ \rightarrow $ Verb Vmod Adv $ \rightarrow $ PP

PP $ \rightarrow $ Prep NP Vmod $ \rightarrow $ Adv PP $ \rightarrow $ Prep NP

NP $ \rightarrow $ Noun Adv $ \rightarrow $ PP NP $ \rightarrow $ Noun PP $ \rightarrow $ Prep NP

对上述每个文法，分别写出由其生成的3个英语句子和3个非法英语句子。每个句子应该有明显的不同，至少包括6个单词，而且应该包括一些新的词条（由你定义）。对每个文法给出改进建议，以避免生成非法的英语句子。

23.7 搜集一些时间表达的例子，比如 “two o'clock”、“midnight” 以及 “12:46” 等，再想出一些不符合语法的例子，例如 “thirteen o'clock” 以及 “half past two fifteen” 等。写出描述时间语言的文法。

23.8 在本题中，你需要将 $ \varepsilon_{0} $ 变成乔姆斯基范式（CNF）。有五个步骤：（a）添加一个新的开始符，（b）消除 $ \varepsilon $ 规则，（c）消除规则右边的多个单词，（d）消除 $ (X \to Y) $ 形式的规则，（e）将右边较长的规则转换成二元规则。

a. 起始符 S 只能出现在 CNF 的左侧。引入新的符号 $ S' $，添加一条形如 $ S' \to S $ 的新规则。

b. 空字符串 $ \varepsilon $ 不能出现在 CNF 的右侧。 $ \varepsilon_{0} $ 没有涉及 $ \varepsilon $ 的规则，所以这不是问题。

c. 单词只能出现在形如 $ (X \to \text{word}) $的规则的右边。引入新符号 $ W' $，将形如 $ (X \to \cdots \text{word} \cdots) $的规则替换成 $ (X \to \cdots W' \cdots) $和 $ (W' \to \text{word}) $。

d. CNF 不允许形如 $ (X \to Y) $ 的规则；规则的形式必须为 $ (X \to Y Z) $ 或 $ (X \to \text{word}) $。任何形如 $ (X \to Y) $ 的规则都可以根据每条 $ (Y \to \cdots) $ 规则改造成 $ (X \to \cdots) $ 形式，其中 $ (\cdots) $ 代表一个或多个符号。

e. 将形如 $ (X \to Y Z \cdots) $的规则替换成两条规则 $ (X \to Y Z' $) $和 $ (Z' \to Z \cdots) $，其中 $ Z' $是新符号。$

给出上述过程的每一步以及最终的规则集合。

23.9 使用 DCG 标记，为一个类似 $ \varepsilon_{1} $ 的语言编写一个文法，该语言要求句子的主语和动词之间保持一致性，不会生成类似 “I smells the wumpus” 的句子。

23.10 考虑下面的 PCFG:

$ S \rightarrow NP\ VP[1.0] $

$$ NP\to Noun[0.6]~|~Pronoun[0.4] $$

VP → Verb NP[0.8] | Modal Verb[0.2]

Noun → $ \mathbf{can}[0.1] $ | $ \mathbf{fish}[0.3] $ | $ \cdots $

Pronoun → $ \mathbf{I}[0.4] $ | $ \cdots $

Verb → $ \mathbf{can}[0.01] $ | $ \mathbf{fish}[0.1] $ | $ \cdots $

Modal → $ \mathbf{can}[0.3] $ | $ \cdots $

在该文法下，句子“I can fish”有两棵句法分析树。针对这句话，给出这两棵分析树，以及它们的先验概率和条件概率。

23.11 扩展的上下文无关文法可以表示一般上下文无关文法不能表示的语言。给出语言 $ a^n b^n c^n $ 的增强上下文无关文法。增强变量的取值为 1 和 SUCCESSOR(n)，其中 $ n $ 是一个值。描述该语言的句子的规则是 $ S(n) \to A(n) B(n) C(n) $。

给出 $ A $、 $ B $ 和 $ C $ 的规则。

23.12 扩展 $ \varepsilon_{l} $的语法，使其能够处理冠词-名词的一致性。也就是说，确保“agents”和“an agent”是一个NP，而“agent”和“an agents”不是。

23.13 考虑下列句子（来自纽约时报，2008年7月28日）。

Banks struggling to recover from multibillion-dollar loans on real estate are curtailing loans to American businesses, depriving even healthy companies of money for expansion and hiring.

a. 句子中哪些词是有词法歧义的？

b. 在句子中找出两处有句法歧义的地方（句子中的句法歧义多于两处）。

c. 给出句子中的一个隐喻例子。

d. 你能发现语义歧义吗？

23.14 不要回看习题 23.1，回答下列问题：

a. 习题 23.1 中提到的 4 个步骤是什么？

b. 其中被剔除的步骤是什么？

c. 文中提到的 “the material” 是什么？

d. 什么样的错误的代价很高？

e. 做得太少还是做得太多更好？为什么？

23.15 选择 5 个句子，将它们提交给在线翻译服务器。将它们从英语翻译成另一种语言，再翻译成英语。根据是否合乎语法和保持意义对结果句子进行评价。重复上述过程，第二轮迭代是得到更坏的结果还是相同的结果？中间语言的选择对结果的质量有影响吗？如果你懂得一门外语，看一看翻译成该语言的一段话。统计和描述产生的错误，并推测为什么会出现这些错误。

23.16 图23.13中句子的 $ D_{i} $值的总和为0。这对每个翻译对都是这样吗？证明该结论或给出反例。

23.17 （改编自 Knight（1999））机器翻译模型假设，在短语翻译模型挑选出短语、扭曲模型改变顺序之后，语言模型可以整理所有的组合。本题研究这个假设是否明智。试

着将下列语句按正确的词语顺序排列：

a. have, programming, a, seen, never, I, language, better

c. is the, communication, exchange of, intentional, information brought, by, about, the production, perception of, and signs, from, drawn, a, of, system, signs, conventional, shared

d. created, that, we hold these, to be, all men, truths, are, equal, self-evident

你能完成哪些语句的正确排列？你需要利用何种知识？在训练语料库上训练一个二元模型，用该模型从测试语料中找到某些句子的概率最高的组合。报告该模型的准确率。

23.18 针对输出序列 $ [C_{1}, C_{2}, C_{3}, C_{4}, C_{5}, C_{6}, C_{7}] $，计算图 23.16 中的 HMM 的最可能路径，并给出概率值。

23.19 我们忘记说明习题 23.1 中的短文的标题是 “洗衣服”。重新阅读短文，并回答习题 23.14 中的问题。你这次是否做得好一些？Bransford 和 Johnson（1973）把这篇短文用于一个控制实验，发现标题有显著的帮助作用。你从中得到了哪些有关语言和记忆工作的信息？