68 Chapter 2. 统计语言建模基础肖桐朱靖波

2.4 预测与搜索

给定模型结构，统计语言模型的使用可以分为两个阶段：

• 训练（Training）：从训练数据上估计出语言模型的参数。

• 预测（Prediction）：用训练好的语言模型对新输入的句子进行概率评估，或者

生成新的句子。

模型训练的内容已经在前文进行了介绍，这里重点讨论语言模型的预测。实际

上，预测是统计自然语言处理中的常用概念。比如，深度学习中的推断（Inference）、

统计机器翻译中的解码（Decoding）本质上都是预测。具体到语言建模的问题上，预

测通常对应两类问题：

• 预测输入句子的可能性。比如，有如下两个句子：

The boy caught the cat.

The caught boy the cat.

可以利用语言模型对其进行打分，即计算句子的生成概率，之后把语言模型的

得分作为判断句子合理性的依据。显然，在这个例子中，第一句的语言模型得

分更高，因此句子也更加合理。

• 预测可能生成的单词或者单词序列。比如，对于如下的例子

The boy caught

下划线的部分是缺失的内容，现在要将缺失的部分生成出来。理论上，所有可

能的单词串都可以构成缺失部分的内容。这时可以使用语言模型得到所有可能

词串构成句子的概率，之后找到概率最高的词串填入下划线处。

从词序列建模的角度看，这两类预测问题本质上是一样的。因为，它们都在使

用语言模型对词序列进行概率评估。但是，从实现上看，词序列的生成问题更难。因

为，它不仅要对所有可能的词序列进行打分，同时要“找到”最好的词序列。由于潜

在的词序列不计其数，因此这个“找”最优词序列的过程并不简单。

实际上，生成最优词序列的问题也是自然语言处理中的一大类问题

——

序列生

成（Sequence Generation）。机器翻译就是一个非常典型的序列生成任务：在机器翻

译任务中，需要根据源语言词序列生成与之相对应的目标语言词序列。但是语言模

型本身并不能“制造”单词序列的。因此，严格地说，序列生成任务的本质并非让语

言模型凭空“生成”序列，而是使用语言模型在所有候选的单词序列中“找出”最佳

序列。这个过程对应着经典的搜索问题（Search Problem）。下面将着重介绍序列生成

任务背后的建模方法，以及在序列生成任务里常用的搜索技术。

2.4 预测与搜索 69

2.4.1 搜索问题的建模

基于语言模型的序列生成任务可以被定义为：在无数任意排列的单词序列中找

到概率最高的序列。这里单词序列 w = w

...w

的语言模型得分 P (w) 度量了这

个序列的合理性和流畅性。在序列生成任务中，基于语言模型的搜索问题可以被描

述为：

ˆw = arg max

w∈χ

P (w) (2.42)

这里 arg 即 argument（参数），argmax

f(x) 表示返回使 f(x) 达到最大的 x。argmax

w∈χ

P (w) 表示找到使语言模型得分 P (w) 达到最大的单词序列 w。χ 是搜索问题的解空

间，它是所有可能的单词序列 w 的集合。 ˆw 可以被看做该搜索问题中的“最优解”，

即概率最大的单词序列。

在序列生成任务中，最简单的策略就是对词表中的单词进行任意组合，通过这

种枚举的方式得到全部可能的序列。但是，很多时候待生成序列的长度是无法预先

知道的。比如，机器翻译中目标语言序列的长度是任意的。那么怎样判断一个序列

何时完成了生成过程呢？这里借用现代人类书写中文和英文的过程：句子的生成首

先从一片空白开始，然后从左到右逐词生成，除了第一个单词，所有单词的生成都

依赖于前面已经生成的单词。为了方便计算机实现，通常定义单词序列从一个特殊

的符号 <sos> 后开始生成。同样地，一个单词序列的结束也用一个特殊的符号 <eos>

来表示。

对于一个序列 <sos> I agree <eos>，图2.12展示语言模型视角下该序列的生成

过程。该过程通过在序列的末尾不断附加词表中的单词来逐渐扩展序列，直到这段

序列结束。这种生成单词序列的过程被称作自左向右生成（Left-to-Right Generation）。

注意，这种序列生成策略与 n-gram 的思想天然契合，因为 n-gram 语言模型中，每个

词的生成概率依赖前面（左侧）若干词，因此 n-gram 语言模型也是一种自左向右的

计算模型。

在这种序列生成策略的基础上，实现搜索通常有两种方法

——

深度优先遍历和

宽度优先遍历

[47]

。在深度优先遍历中，每次从词表中选择一个单词（可重复），然后

从左至右地生成序列，直到 <eos> 被选择，此时一个完整的单词序列被生成出来。然

后从 <eos> 回退到上一个单词，选择之前词表中未被选择到的候选单词代替 <eos>，

并继续挑选下一个单词直到 <eos> 被选到，如果上一个单词的所有可能都被枚举过，

那么回退到上上一个单词继续枚举，直到回退到 <sos>，这时候枚举结束。在宽度优

先遍历中，每次不是只选择一个单词，而是枚举所有单词。

有一个简单的例子。假设词表只含两个单词 {a, b}，从 <sos> 开始枚举所有候选，

有三种可能：

{<sos> a,<sos> b,<sos> <eos>}

70 Chapter 2. 统计语言建模基础肖桐朱靖波

<sos>

Step1:

Step2:

Step3:

Step4:

agree

<eos>

图 2.12 序列生成过程

其中可以划分成长度为 0 的完整的单词序列集合 {<sos> <eos>} 和长度为 1 的未结束

的单词序列片段集合 {<sos> a,<sos> b}，然后下一步对未结束的单词序列枚举词表

中的所有单词，可以生成：

{<sos> a a,<sos> a b,<sos> a <eos>,<sos> b a, <sos> b b, <sos> b <eos>}

此时可以划分出长度为 1 的完整单词序列集合 {<sos> a <eos>, <sos> b <sos>}，

以及长度为 2 的未结束单词序列片段集合 {<sos> a a, <sos> a b, <sos> b a, <sos> b b}。

以此类推，继续生成未结束序列，直到单词序列的长度达到所允许的最大长度。

对于这两种搜索算法，通常可以从以下四个方面评价：

• 完备性：当问题有解时，使用该策略能否找到问题的解。

• 最优性：搜索策略能否找到最优解。

• 时间复杂度：找到最优解需要多长时间。

• 空间复杂度：执行策略需要多少内存。

当任务对单词序列长度没有限制时，上述两种方法枚举出的单词序列也是无穷

无尽的。因此这两种枚举策略并不具备完备性而且会导致枚举过程无法停止。由于

日常生活中通常不会见到特别长的句子，因此可以通过限制单词序列的最大长度来

避免这个问题。一旦单词序列的最大长度被确定，以上两种枚举策略就可以在一定

时间内枚举出所有可能的单词序列，因而一定可以找到最优的单词序列，即具备最

优性。

此时上述生成策略虽然可以满足完备性和最优性，但其仍然算不上是优秀的生

成策略，因为这两种算法在时间复杂度和空间复杂度上的表现很差，如表2.4所示。其

2.4 预测与搜索 71

表 2.4 枚举的两种实现方式比较

时间复杂度空间复杂度

深度优先 O((|V |+ 1)

m−1

) O(m)

宽度优先 O((|V |+ 1)

m−1

) O((|V |+ 1)

)

中 |V | 为词表大小，m 为序列长度。值得注意的是，在之前的遍历过程中，除了在序

列开头一定会挑选 <sos> 之外，其他位置每次可挑选的单词并不只有词表中的单词，

还有结束符号 <eos>，因此实际上生成过程中每个位置的单词候选数量为 |V |+ 1。

那么是否有比枚举策略更高效的方法呢？答案是肯定的。一种直观的方法是将

搜索的过程表示成树型结构，称为解空间树。它包含了搜索过程中可生成的全部序

列。该树的根节点恒为 <sos>，代表序列均从 <sos> 开始。该树结构中非叶子节点的

兄弟节点有 |V |+ 1 个，由词表和结束符号 <eos> 构成。从图2.13可以看到，对于一

个最大长度为 4 的序列的搜索过程，生成某个单词序列的过程实际上就是访问解空

间树中从根节点 <sos> 开始一直到叶子节点 <eos> 结束的某条路径，而这条的路径

上节点按顺序组成了一段独特的单词序列。此时对所有可能单词序列的枚举就变成

了对解空间树的遍历。并且枚举的过程与语言模型打分的过程也是一致的，每枚举

一个词 i 也就是在图2.13选择 w

一列的一个节点，语言模型就可以为当前的树节点

给出一个分值，即 P (w

...w

i−1

)。对于 n-gram 语言模型，这个分值可以表

示为 P (w

...w

i−1

) = P (w

i−n+1

...w

i−1

)

词表

agree

特殊符号

<sos>

<eos>

<sos>

agree

<eos>

agree

<eos>

agree

<eos>

图 2.13 对有限长序列进行枚举搜索时的解空间树

从这个角度来看，在树的遍历中，可以很自然地引入语言模型打分：在解空间树

中引入节点的权重

——

将当前节点 i 的得分重设为语言模型打分 log P (w

...

72 Chapter 2. 统计语言建模基础肖桐朱靖波

i−1

)，其中 w

...w

i−1

是该节点的全部祖先。与先前不同的是，由于在使用语言

模型打分时，词的概率通常小于 1，因此句子很长时概率会非常小，容易造成浮点误

差, 所以这里使用概率的对数形式 logP (w

...w

i−1

) 代替 P (w

...w

i−1

)。

此时对于图中一条包含 <eos> 的完整序列来说，它的最终得分 score(·) 可以被定义

为：

score(w

...w

) = log P (w

...w

)

i=1

log P (w

...w

i−1

) (2.43)

通常，score(·) 也被称作模型得分（Model Score）。如图2.14所示，可知红线所示

单词序列“<sos> I agree <eos>”的模型得分为：

score(<sos> I agree <eos>)

= log P (<sos>) + log P (I|<sos>) + log P (agree|<sos> I) + log P (<sos>|<sos> I agree)

= 0 −0.5 −0.2 −0.8

= −1.5 (2.44)

词表

agree

特殊符号

<sos>

<eos>

<sos>

生成顺序:

agree

-0.4

-0.5

<eos>

-2.2

agree

-0.2

-1.8

<eos>

-1.3

agree

-1.5

-2.0

<eos>

-1.3

<eos>

-0.9

<eos>

-0.8

<eos>

-1.4

<eos>

-0.1

图 2.14 通过语言模型对解空间树打分

这样，语言模型的打分与解空间树的遍历就融合在一起了。于是，序列生成任务

可以被重新描述为：寻找所有单词序列组成的解空间树中权重总和最大的一条路径。

在这个定义下，前面提到的两种枚举词序列的方法就是经典的深度优先搜索（Depth-

first Search）和宽度优先搜索（Breadth-first Search）的雏形

[48, 49]

。在后面的内容中，从

2.4 预测与搜索 73

遍历解空间树的角度出发，可以对这些原始的搜索策略的效率进行优化。

2.4.2 经典搜索

人工智能领域有很多经典的搜索策略，这里将对无信息搜索和启发性搜索进行

简要介绍。

1. 无信息搜索

在解空间树中，在每次对一个节点进行扩展的时候，可以借助语言模型计算当

前节点的权重。因此很自然的一个想法是：使用权重信息可以帮助系统更快地找到

合适的解。

在深度优先搜索中，每次总是先挑选一个单词，等枚举完当前单词全部子节点

构成的序列后，才会选择下一个兄弟节点继续进行搜索。但是在挑选过程中先枚举

词表中的哪个词是未定义的，也就是先选择哪个兄弟节点进行搜索是随机的。既然

最终目标是寻找权重之和最大的路径，那么可以优先挑选分数较高的单词进行枚举。

如图2.15所示，红色线表示了第一次搜索的路径。在路径长度有限的情况下，权重和

最大的路径上每个节点的权重也会比较大，先尝试分数较大的单词可以让系统更快

地找到最优解，这是对深度优先搜索的一个自然的扩展。

词表

agree

特殊符号

<sos>

<eos>

<sos>

生成顺序:

agree

-0.4

-0.5

<eos>

-2.2

agree

-0.2

-1.8

<eos>

-1.3

agree

-1.5

-2.0

<eos>

-1.3

<eos>

-0.9

<eos>

-0.8

<eos>

-1.4

<eos>

-0.1

图 2.15 深度优先搜索扩展方法实例

类似的思想也可以应用于宽度优先搜索，由于宽度优先搜索每次都选择了所有

的单词，因此简单使用节点的权重来选择单词是不可行的。重新回顾宽度优先搜索

的过程：它维护了一个未结束单词序列的集合，每次扩展单词序列后根据长度往集

合里面加入单词序列。而搜索问题关心的是单词序列的得分而非其长度。因此可以

在搜索过程中维护未结束的单词序列集合里每个单词序列的得分，然后优先扩展该

74 Chapter 2. 统计语言建模基础肖桐朱靖波

集合中得分最高的单词序列，使得扩展过程中未结束的单词序列集合包含的单词序

列分数逐渐变高。如图2.16所示，由于“<sos> I”在图右侧的 5 条路径中分数最高，

因此下一步将要扩展 w

一列“I”节点后的全部后继。图中绿色节点表示下一步将

要扩展的节点。普通宽度优先搜索中，扩展后生成的单词序列长度相同，但是分数

却参差不齐。而改造后的宽度优先搜索则不同，它会优先生成得分较高的单词序列，

这种宽度优先搜索也叫做一致代价搜索（Uniform-cost Search）

[50]

。

词表

agree

特殊符号

<sos>

<eos>

<sos>

agree

-0.4

-0.5

<eos>

-2.2

agree

<eos>

agree

-1.5

-2.0

<eos>

-1.3

score(<sos> I) = -0.5

score(<sos> agree I) = -2.4

score(<sos> agree agree) = -1.9

score(<sos> agree <eos>) = -1.7

score(<sos> <eos>) = -2.2

图 2.16 一致代价搜索实例

上面描述的两个改进后的搜索方法属于无信息搜索（Uninformed Search）

[51]

，因

为它们依赖的信息仍然来源于问题本身而不是问题以外。改进后的方法虽然有机会

更早地找到分数最高的单词序列（也就是最优解）。但是由于没有一个通用的办法来

判断当前找到的解是否为最优解，这种策略不会在找到最优解后自动停止，因此最

终仍然需要枚举所有可能的单词序列，寻找最优解需要的时间复杂度没有产生任何

改变。尽管如此，如果只是需要一个相对好的解而不是最优解，改进后的搜索策略

仍然是比原始的枚举策略更优秀的算法。

此外，由于搜索过程中将语言模型的打分作为搜索树的节点权重，另一种改进

思路是：能否借助语言模型的特殊性质来对搜索树进行剪枝（Pruning），从而避免在

搜索空间中访问一些不可能产生比当前解更好的结果的区域，提高搜索策略在实际

运用当中的效率。简单来说，剪枝是一种可以缩小搜索空间的手段，比如，在搜索的

过程中，动态的“丢弃”一些搜索路径，从而减少搜索的总代价。剪枝的程度在一定

范围内影响了搜索系统的效率，剪枝越多搜索效率越高，一般找到最优解的可能性

也越低；反之，搜索效率越低，但是找到最优解的可能性越大。在本章后面即将介绍

的贪婪搜索和束搜索都可以被看作是剪枝方法的一种特例。

2.4 预测与搜索 75

2. 启发式搜索

在搜索问题中，一个单词序列的生成可以分为两部分：已生成部分和未生成部

分。既然最终目标是使得一个完整的单词序列得分最高，那么关注未生成部分的得

分也许能为搜索策略的改进提供思路。

但是，问题在于未生成部分来自搜索树中未被搜索过的区域，因此也无法直接计

算其得分。既然仅依赖于问题本身的信息无法得到未生成部分的得分，那么是否可以

通过一些外部信息来估计未生成部分的得分呢？在前面所提到的剪枝技术中，借助

语言模型的特性可以使得搜索变得高效。与其类似，利用语言模型的其他特性也可以

实现对未生成部分得分的估计。这个对未生成部分得分的估计通常被称为启发式函数

（Heuristic Function）。在扩展假设过程中，可以优先挑选当前得分 log P (w

...w

)

和启发式函数值 h(w

...w

) 最大的候选进行扩展，从而大大提高搜索的效率。这

时，模型得分可以被定义为：

score(w

...w

) = log P (w

...w

) + h(w

...w

) (2.45)

这种基于启发式函数的一致代价搜索通常也被称为 A

∗

搜索或启发式搜索（Heuris-

tic Search）

[52]

。通常可以把启发式函数看成是计算当前状态跟最优解的距离的一种

方法，并把关于最优解的一些性质的猜测放到启发式函数里。比如，在序列生成中，

一般认为最优序列应该在某个特定的长度附近，那么就可以把启发式函数定义成该

长度与当前单词序列长度的差值。这样，在搜索过程中，启发式函数会引导搜索优

先生成当前得分高且序列长度接近预设长度的单词序列。

2.4.3 局部搜索

由于全局搜索策略要遍历整个解空间，所以它的时间、空间复杂度一般都比较

高。在对于完备性与最优性要求不那么严格的搜索问题上，可以使用非经典搜索策

略。非经典搜索涵盖的内容非常广泛，其中包括局部搜索

[53]

、连续空间搜索

[54]

、信念

状态搜索

[55]

和实时搜索

[56]

等等。局部搜索是非经典搜索里的一个重要方面，局部搜

索策略不必遍历完整的解空间，因此降低了时间、空间复杂度，但是这也导致可能

会丢失最优解甚至找不到解，所以局部搜索都是不完备的而且非最优的。但是，在

自然语言处理中，很多问题由于搜索空间过大无法使用全局搜索，因此使用局部搜

索是非常普遍的。

1. 贪婪搜索

贪婪搜索（Greedy Search）基于一种思想：当一个问题可以拆分为多个子问题时，

如果一直选择子问题的最优解就能得到原问题的最优解，那么就可以不必遍历原始

的解空间，而是使用这种“贪婪”的策略进行搜索。基于这种思想，它每次都优先挑

选得分最高的词进行扩展，这一点与改进过的深度优先搜索类似。但是它们的区别

在于，贪婪搜索在搜索到一个完整的序列，也就是搜索到 <eos> 即停止，而改进的深

76 Chapter 2. 统计语言建模基础肖桐朱靖波

度优先搜索会遍历整个解空间。因此贪婪搜索非常高效，其时间和空间复杂度仅为

O(m)，这里 m 为单词序列的长度。

由于贪婪搜索并没有遍历整个解空间，所以该方法不保证一定能找到最优解。比

如对于如图2.17所示的一个搜索结构，贪婪搜索将选择红线所示的序列，该序列的最

终得分是-1.7。但是，对比图2.15可以发现，在另一条路径上有得分更高的序列“<sos>

I agree <eos>”，它的得分为-1.5。此时贪婪搜索并没有找到最优解，由于贪婪搜索选

择的单词是当前步骤得分最高的，但是最后生成的单词序列的得分取决于它未生成

部分的得分。因此当得分最高的单词的子树中未生成部分的得分远远小于其他子树

时，贪婪搜索提供的解的质量会非常差。同样的问题可以出现在使用贪婪搜索的任

意时刻。但是，即使是这样，凭借其简单的思想以及在真实问题上的效果，贪婪搜索

在很多场景中仍然得到了深入应用。

词表

agree

特殊符号

<sos>

<eos>

<sos>

生成顺序:

agree

-0.4

-0.5

<eos>

-2.2

agree

-1.5

-2.0

<eos>

-1.3

图 2.17 贪婪搜索实例

2. 束搜索

贪婪搜索会产生质量比较差的解是由于当前单词的错误选择造成的。既然每次

只挑选一个单词可能会产生错误，那么可以通过同时考虑更多候选单词来缓解这个

问题，也就是对于一个位置，可以同时将其扩展到若干个节点。这样就扩大了搜索

的范围，进而使得优质解被找到的概率增大。

常见的做法是每一次生成新单词的时候都挑选得分最高的前 B 个单词，然后扩

展这 B 个单词的 T 个孩子节点，得到 BT 条新路径，最后保留其中得分最高的 B 条

路径。从另外一个角度理解，它相当于比贪婪搜索看到了更多的路径，因而它更有

可能找到好的解。这个方法通常被称为束搜索（Beam Search）。图2.18展示了一个束

大小为 3 的例子，其中束大小代表每次选择单词时保留的词数。比起贪婪搜索，束

搜索在实际表现中非常优秀，它的时间、空间复杂度仅为贪婪搜索的常数倍，也就

2.4 预测与搜索 77

是 O(Bm)。

词表

There

Here

one

appple

特殊符号

<sos>

<eos>

<sos>

-1.4

one

-0.6

Here

-0.3

There

-0.2

-2.2

apple

-2.6

<eos>

-7.2

-0.1

<eos>

-0.6

-2.4

one

-2.6

Here

-2.9

apple

-3.2

There

-4.1

-0.1

…

<-0.7

剪枝

图 2.18 束搜索实例

束搜索也有很多的改进版本。回忆一下，在无信息搜索策略中可以使用剪枝技

术来提升搜索的效率。而实际上，束搜索本身也是一种剪枝方法。因此有时也把束

搜索称作束剪枝（Beam Pruning）。在这里有很多其它的剪枝策略可供选择，例如可

以只保留与当前最佳路径得分相差在 θ 之内的路径，也就是进行搜索时只保留得分

差距在一定范围内的路径，这种方法也被称作直方图剪枝（Histogram Pruning）。

对于语言模型来说，当多个路径中最高得分比当前搜索到的最好的解的得分低

时，可以立刻停止搜索。因为此时序列越长语言模型得分 logP (w

...w

) 会越

低，继续扩展这些路径不会产生更好的结果。这个技术通常也被称为最佳停止条件

（Optimal Stopping Criteria）。类似的思想也被用于机器翻译等任务

[57, 58]

。

总的来说，虽然局部搜索没有遍历完整的解空间，使得这类方法无法保证找到

最优解。但是，局部搜索算法大大降低了搜索过程的时间、空间复杂度。因此在语言

模型生成和机器翻译的解码过程中常常使用局部搜索算法。在第七章、第十章中还

将介绍这些算法的具体应用。