146 Chapter 5. 基于词的机器翻译建模 肖桐 朱靖波
5.2 一个简单实例
本节首先对比人工翻译和机器翻译流程的异同点，从中归纳出实现机器翻译过
程的两个主要步骤：训练和解码。之后，会从学习翻译知识和运用翻译知识两个方
面描述如何构建一个简单的机器翻译系统。
5.2.1 翻译的流程
1. 人工翻译流程
当人翻译一个句子时，首先会快速地分析出句子的（单词）构成，然后根据以往
的知识，得到每个词可能的翻译，最后利用对目标语的理解拼出来一个译文。尽管
这个过程并不是严格来自心理学或者脑科学的相关结论，但至少可以帮助我们理解
人在翻译时的思考方式。
我
对
你
感到
满意
待翻译句子（已经分词）:
1
1
1
2
2
2
3
ϕ
4
4
5
5
5
1
5
2 3
翻空
选择最佳单词翻译，调整词序，得到完美的结果
学习到的
单词翻译
运用知识
生成译文
图 人工翻译的过程
图展示了人在翻译“我对你感到满意”时可能会思考的内容
。具体来说，
有如下两方面内容：
翻译知识的学习：对于输入的源语言句子，首先需要知道每个单词可能的翻译有
什么，这些翻译被称为翻译候选（ ）。比如，汉语单词“对”
可能的译文有“”、“”和“”等。对于人来说，可以通过阅读、背诵、
做题或者老师教等途径获得翻译知识，这些知识就包含了源语言与目标语言单
词之间的对应关系。通常，也把这个过程称之为学习过程。
运用知识生成译文：当翻译一个从未见过的句子时，可以运用学习到的翻译知
识，得到新的句子中每个单词的译文，并处理常见的单词搭配、主谓一致等问
题，比如，英语中“”后面常常使用介词“”构成搭配。基于这些
知识可以快速生成译文。
这里用斜杠表示单词之间的分隔。
5.2 一个简单实例 147
当然，每个人进行翻译时所使用的方法和技巧都不相同，所谓人工翻译也没有
固定的流程。但是，可以确定的是，人在进行翻译时也需要“学习”和“运用”翻译
知识。对翻译知识“学习”和“运用”的好与坏，直接决定了人工翻译结果的质量。
2. 机器翻译流程
人进行翻译的过程比较容易理解，那计算机是如何完成翻译的呢？虽然人工智
能这个概念显得很神奇，但是计算机远没有人那么智能，有时甚至还很“笨”。一方
面，它没有能力像人一样，在教室里和老师一起学习语言知识；另一方面，即使能列
举出每个单词的候选译文，但是还是不知道这些译文是怎么拼装成句的，甚至不知
道哪些译文是对的。为了更加直观地理解机器在翻译时要解决的挑战，可以将问题
归纳如下：
如何让计算机获得每个单词的译文，然后将这些单词的译文拼装成句？
如果可以形成整句的译文，如何让计算机知道不同译文的好坏？
对于第一个问题，可以给计算机一个翻译词典，这样计算机可以发挥计算方面
的优势，尽可能多地把翻译结果拼装出来。比如，可以把每个翻译结果看作是对单
词翻译的拼装，这可以被形象地比作贯穿多个单词的一条路径，计算机所做的就是
尽可能多地生成这样的路径。图中蓝色和红色的折线就分别表示了两条不同的译
文选择路径，区别在于“满意”和“对”的翻译候选是不一样的，蓝色折线选择的是
“”和“”，而红色折线是“”和“”。换句话说，不同的译文对应
不同的路径（即使词序不同也会对应不同的路径）。
对于第二个问题，尽管机器能够找到很多译文选择路径，但它并不知道哪些路
径是好的。说地再直白一些，简单地枚举路径实际上就是一个体力活，没有太多的
智能。因此计算机还需要再聪明一些，运用它的能够“掌握”的知识判断翻译结果
的好与坏。这一步是最具挑战的，当然也有很多思路来解决这个问题。在统计机器
翻译中，这个问题被定义为：设计一种统计模型，它可以给每个译文一个可能性，而
这个可能性越高表明译文越接近人工翻译。
如图所示，每个单词翻译候选的右侧黑色框里的数字就是单词的翻译概率，
使用这些单词的翻译概率，可以得到整句译文的概率（用符号 P 表示）。这样，就用
概率化的模型描述了每个翻译候选的可能性。基于这些翻译候选的可能性，机器翻
译系统可以对所有的翻译路径进行打分，比如，图中第一条路径的分数为 ，
第二条是 ，以此类推。最后，系统可以选择分数最高的路径作为源语言句子的
最终译文。
3. 人工翻译 vs 机器翻译
人在翻译时的决策是非常确定并且快速的，但计算机处理这个问题时却充满了
概率化的思想。当然它们也有类似的地方。首先，计算机使用统计模型的目的是把
翻译知识变得可计算，并把这些“知识”储存在模型参数中，这个模型和人类大脑的
148 Chapter 5. 基于词的机器翻译建模 肖桐 朱靖波
我
对
你
感到
满意
待翻译句子 (已经分词):
1
1
1
2
2
2
3
ϕ
4
4
5
5
5
P =0.4
P =0.2
P =0.4
P =0.4
P =0.3
P =0.3
P =1
P =0.5
P =0.5
P =0.5
P =0.4
P =0.1
1
5
2 3
1
5
2 3
1
5
3 2
P =0.4 P =0.4 P =0.3 P =1
P =0.4 P =0.1 P =0.4 P =1
P =0.4 P =0.1 P =1 P =0.4
所有翻译单元都是概率化的
P 概率
翻译就是一条
译文选择路径
不同的译文对
应不同的路径
单词翻译的词
序也可能不同
可能的翻译路
径非常多
从双语数
据中自动
学习词典
（训练）
利用概率
化的词典
进行翻译
（解码）
率给每个译文赋予一个模型得分
系统综合单词概率和语言模型概
选择得分
最高的译文
图 机器翻译的过程
把单词的译文进行拼装，并找到最优的拼装路径
作用是类似的
；其次，计算机对统计模型进行训练相当于人类对知识的学习，二者
都可以被看作是理解、加工知识的过程；再有，计算机使用学习到的模型对新句子
进行翻译的过程相当于人运用知识的过程。在统计机器翻译中，模型学习的过程被
称为训练，目的是从双语平行数据中自动学习翻译“知识”；而使用模型处理新句子
的过程是一个典型的预测过程，也被称为解码或推断。图的右侧标注在翻译过程
中训练和解码的作用。最终，统计机器翻译的核心由三部分构成
建模、训练和
解码。本章后续内容会围绕这三个问题展开讨论。
5.2.2 统计机器翻译的基本框架
为了对统计机器翻译有一个直观的认识，下面将介绍如何构建一个非常简单的
统计机器翻译系统，其中涉及到的很多思想来自 模型。这里，仍然使用数据驱
动的统计建模方法。图展示了统计机器翻译的主要流程，包括两个步骤：
训练：从双语平行数据中学习翻译模型，记为 P (t|s)，其中 s 表示源语言句子，
t 表示目标语句子。P (t|s) 表示把 s 翻译为 t 的概率。简言之，这一步需要从大
量的双语平行数据中学习到 P (t|s) 的准确表达。
这里并不是要把统计模型等同于生物学或者认知科学上的人脑，这里是指它们处理翻译问题时发
挥的作用类似。
5.2 一个简单实例 149
解码：当面对一个新的句子时，需要使用学习到的模型进行预测。预测可以被视
为一个搜索和计算的过程，也就是，尽可能搜索更多的翻译结果，然后用训练
好的模型对每个翻译结果进行打分，最后选择得分最高的翻译结果作为输出。
1: 这是数据 ↔
2: 小心！↔
3: 你是谁 ↔
双语平行数据
P (t|s)
翻译模型
训练
解码
机器翻译引擎
对任意句子进行翻译
图 简单的统计机器翻译流程
接下来，本节将介绍统计机器翻译模型训练和解码的方法。在模型学习中，会
分两小节进行描述
单词级翻译和句子级翻译。实现单词级翻译是实现句子级翻
译的基础。换言之，句子级翻译的统计模型是建立在单词翻译之上的。在小节
将介绍一个高效的搜索算法，其中也使用到了剪枝和启发式搜索的思想。
5.2.3 单词级翻译模型
1. 什么是单词翻译概率？
单词翻译概率描述的是一个源语言单词与目标语言译文构成正确翻译的可能性，
这个概率越高表明单词翻译越可靠。使用单词翻译概率，可以帮助机器翻译系统解
决翻译时的“择词”问题，即选择什么样的目标语译文是合适的。当人在翻译某个
单词时，可以利用积累的知识，快速得到它的高质量候选译文。
以汉译英为例，当翻译“我”这个单词时，可能直接会想到用“”、“”或
“”作为它的译文，而几乎不会选择“”、“”等含义相差太远的译文。
这是为什么呢？如果从统计学的角度来看，无论是何种语料，包括教材、新闻、小
说等，绝大部分情况下“我”都翻译成了“”、“”等，几乎不会看到我被翻译成
“”或“”的情况。可以说“我”翻译成“”、“”等属于高频事件，而
翻译成“”、“”等属于低频或小概率事件。因此人在翻译时也是选择在统
计意义上概率更大的译文，这也间接反映出统计模型可以在一定程度上描述人的翻
译习惯和模式。
表展示了汉语到英语的单词翻译实例及相应的翻译概率。可以看到，“我”翻
译成“”的概率最高，为 。这是符合人类对翻译的认知的。此外，这种概率化的
模型避免了非 即 的判断，所有的译文都是可能的，只是概率不同。这也使得统
计模型可以覆盖更多的翻译现象，甚至捕捉到一些人所忽略的情况。
2. 如何从双语平行数据中进行学习？
假设有一定数量的双语对照的平行数据，是否可以从中自动获得两种语言单词
之间的翻译概率呢？回忆一下第二章中的掷骰子游戏，其中使用了相对频次估计方
法来自动获得骰子不同面出现概率的估计值。其中，重复投掷骰子很多次，然后统
计“”到“”各面出现的次数，再除以投掷的总次数，最后得到它们出现的概率的
150 Chapter 5. 基于词的机器翻译建模 肖桐 朱靖波
表 汉译英单词翻译概率
源语言 目标语言 翻译概率
我
极大似然估计。这里，可以使用类似的方式计算单词翻译概率。但是，现在有的是句
子一级对齐的数据，并不知道两种语言之间单词的对应关系。也就是，要从句子级
对齐的平行数据中学习单词之间对齐的概率。这里，需要使用稍微“复杂”一些的
模型来描述这个问题。
令 X 和 Y 分别表示源语言和目标语言的词汇表。对于任意源语言单词 x ∈ X，
所有的目标语单词 y ∈ Y 都可能是它的译文。给定一个互译的句对 (s, t)，可以把
P
(
x
↔
y
;
s,t
)
定义为：在观测到
(
s,t
)
的前提下
x
和
y
互译的概率。其中
x
是属于句
子 s 中的词，而 y 是属于句子 t 中的词。P (x ↔ y;s,t) 的计算公式描述如下：
P (x ↔ y;s,t) ≡ P (x, y;s,t)
=
c(x,y; s,t)
P
x
′
,y
′
c(x
′
,y
′
;s, t)
其中，≡ 表示定义式。分子 c (x, y;s,t) 表示 x 和 y 在句对 (s,t) 中共现的总次数 分
母
P
x
′
,y
′
c(x
′
,y
′
; s,t) 表示任意的源语言单词 x
′
和任意的目标语言单词 y
′
在 (s,t) 共
同出现的总次数。
看一个具体的例子，如例所示，有一个汉英互译的句对 (s,t)。
实例 5.1 一个汉英互译的句对
s 机器 翻译 就 是 用 计算机 来 生成 翻译 的 过程
t
假设，x =“翻译”，y =“”，现在要计算 x 和 y 共现的总次数。“翻译”
和“”分别在 s 和 t 中出现了 次，因此 c(“翻译”,“”;s, t) 等
于 。而对于
P
x
′
,y
′
c(x
′
,y
′
;s, t)，因为 x
′
和 y
′
分别表示的是 s 和 t 中的任意词，所以
P
x
′
,y
′
c(x
′
,y
′
;s, t) 表示所有单词对的数量
即 s 的词数乘以 t 的词数。最后，“翻
5.2 一个简单实例 151
译”和“”的单词翻译概率为：
P (翻译,;s, t) =
c(翻译,;s, t)
P
x
′
,y
′
c(x
′
,y
′
;s, t)
=
4
|s|×|t|
=
4
121
这里运算 |·| 表示句子长度。类似的，可以得到“机器”和“”、“机器”和
“”的单词翻译概率：
P (机器,;s, t) =
2
121
P (机器,;s,t) =
0
121
注意，由于“”没有出现在数据中，因此 P (机器, ;s,t) = 0。这时，可以使用
第二章介绍的平滑算法赋予它一个非零的值，以保证在后续的步骤中整个翻译模型
不会出现零概率的情况。
3. 如何从大量的双语平行数据中进行学习？
如果有更多的句子，上面的方法同样适用。假设，有 K 个互译句对 {(s
[1]
,t
[1]
)
(s
[K]
,t
[K]
)}。仍然可以使用基于相对频次的方法估计翻译概率 P (x,y)，具体方法如
下
P (x,y) =
P
K
k=1
c(x,y; s
[k]
,t
[k]
)
P
K
k=1
P
x
′
,y
′
c(x
′
,y
′
;s
[k]
,t
[k]
)
与公式相比，公式的分子、分母都多了一项累加符号
P
K
k=1
·，它表示遍
历语料库中所有的句对。换句话说，当计算词的共现次数时，需要对每个句对上的
计数结果进行累加。从统计学习的角度，使用更大规模的数据进行参数估计可以提
高结果的可靠性。计算单词的翻译概率也是一样，在小规模的数据上看，很多翻译
现象的特征并不突出，但是当使用的数据量增加到一定程度，翻译的规律会很明显
的体现出来。
举个例子，实例展示了一个由两个句对构成的平行语料库。
实例 5.2 两个汉英互译的句对
s
[1]
机器 翻译 就 是 用 计算机 来 生成 翻译 的 过程
t
[1]
s
[2]
那 人工 翻译 呢
t
[2]
152 Chapter 5. 基于词的机器翻译建模 肖桐 朱靖波
其中，s
[1]
和 s
[2]
分别表示第一个句对和第二个句对的源语言句子，t
[1]
和 t
[2]
表示对
应的目标语言句子。于是，“翻译”和“”的翻译概率为
P (翻译, ) =
c(翻译,; s
[1]
,t
[1]
) + c(翻译,; s
[2]
,t
[2]
)
P
x
′
,y
′
c(x
′
,y
′
;s
[1]
,t
[1]
) +
P
x
′
,y
′
c(x
′
,y
′
;s
[2]
,t
[2]
)
=
4 + 1
|s
[1]
|×|t
[1]
|+ |s
[2]
|×|t
[2]
|
=
4 + 1
11 ×11 + 5 ×7
=
5
156
公式所展示的计算过程很简单，分子是两个句对中“翻译”和“”
共现次数的累计，分母是两个句对的源语言单词和目标语言单词的组合数的累加。显
然，这个方法也很容易推广到处理更多句子的情况。
5.2.4 句子级翻译模型
下面继续回答如何获取句子级翻译概率的问题，即：对于源语言句子 s 和目标
语言句子 t，计算 P (t|s) 。这也是整个句子级翻译模型的核心，一方面需要从数据中
学习这个模型的参数，另一方面，对于新输入的句子，需要使用这个模型得到最佳
的译文。下面介绍句子级翻译的建模方法。
1. 基础模型
计算句子级翻译概率并不简单。因为自然语言非常灵活，任何数据无法覆盖足
够多的句子，因此，无法像公式一样直接用简单计数的方式对句子的翻译概率进
行估计。这里，采用一个退而求其次的方法：找到一个函数 g(s,t) ≥ 0 来模拟翻译概
率对译文的可能性进行估计。可以定义一个新的函数 g(s,t)，令其满足：给定 s，翻
译结果 t 出现的可能性越大，g(s,t) 的值越大；t 出现的可能性越小，g(s,t) 的值越
小。换句话说，g(s,t) 和翻译概率 P (t| s ) 呈正相关。如果存在这样的函数 g(s,t)，可
以利用 g(s, t) 近似表示 P (t|s)，如下：
P (t|s) ≡
g(s, t)
P
t
′
g(s, t
′
)
公式相当于在函数 g(·) 上做了归一化，这样等式右端的结果具有一些概率
的属性，比如，0 ≤
g(s,t)
P
t
′
g(s,t
′
)
≤ 1。具体来说，对于源语言句子 s，枚举其所有的翻译
结果，并把所对应的函数 g(·) 相加作为分母，而分子是某个翻译结果 t 所对应的 g(·)
的值。
上述过程初步建立了句子级翻译模型，并没有直接求 P (t|s)，而是把问题转化
到对 g(·) 的设计和计算上。但是，面临着两个新的问题：
如何定义函数 g(s,t)？即，在知道单词翻译概率的前提下，如何计算 g(s,t)；
5.2 一个简单实例 153
公式中分母
P
seqt
′
g(s, t
′
) 需要累加所有翻译结果的 g(s,t
′
)，但枚举所有 t
′
是不现实的。
当然，这里最核心的问题还是函数 g(s,t) 的定义。而第二个问题其实不需要解
决，因为机器翻译只关注于可能性最大的翻译结果，即 g(s,t) 的计算结果最大时对
应的译文。这个问题会在后面进行讨论。
回到设计 g ( s, t) 的问题上。这里，采用“大题小作”的方法，这个方法在第二章
已经进行了充分的介绍。具体来说，直接建模句子之间的对应比较困难，但可以利
用单词之间的对应来描述句子之间的对应关系。这就用到了小节所介绍的单词
翻译概率。
首先引入一个非常重要的概念
词对齐（ ），它是统计机器翻
译中最核心的概念之一。词对齐描述了平行句对中单词之间的对应关系，它体现了
一种观点：本质上句子之间的对应是由单词之间的对应表示的。当然，这个观点在
神经机器翻译或者其他模型中可能会有不同的理解，但是翻译句子的过程中考虑词
级的对应关系是符合人类对语言的认知的。
图 展示了一个汉英互译句对 s 和 t 及其词对齐关系，单词的右下标数字表示
了该词在句中的位置，而虚线表示的是句子 s 和 t 中的词对齐关系。比如，“满意”
的右下标数字 表示在句子 s 中处于第 个位置，“”的右下标数字 表示
在句子 t 中处于第 个位置，“满意”和“”之间的虚线表示两个单词之间是
对齐的。为方便描述，用二元组 (j,i) 来描述词对齐，它表示源语言句子的第 j 个单
词对应目标语言句子的第 i 个单词，即单词 s
j
和 t
i
对应。通常，也会把 (j,i) 称作一
条词对齐连接（ ）。图 中共有 条虚线，表示有 组单词之间
的词对齐连接。可以把这些词对齐连接构成的集合作为词对齐的一种表示，记为 A，
即 A = {(1,1),(2,4),(3,5) , (4, 2)(5, 3)}。
我
1
对
2
你
3
感到
4
满意
5
s =
1
2
3
4
5
t =
图 汉英互译句对及词对齐连接（蓝色虚线）
对于句对 (s,t)，假设可以得到最优词对齐
b
A，于是可以使用单词翻译概率计算
g(s, t)，如下
g(s, t) =
Y
(j,i)∈
b
A
P (s
j
,t
i
)
其中 g(s,t) 被定义为句子 s 中的单词和句子 t 中的单词的翻译概率的乘积，并且这
两个单词之间必须有词对齐连接。P (s
j
,t
i
) 表示具有词对齐连接的源语言单词 s
j
和
目标语言单词 t
i
的单词翻译概率。以图中的句对为例，其中“我”与“”、“对”
154 Chapter 5. 基于词的机器翻译建模 肖桐 朱靖波
与“”、“你”与“”等相互对应，可以把它们的翻译概率相乘得到 g(s, t) 的
计算结果，如下：
g(s, t) = P (我) ×P (对) ×P (你) ×
P (感到 ) ×P (满意)
显然，如果每个词对齐连接所对应的翻译概率变大，那么整个句子翻译的得分
也会提高。也就是说，词对齐越准确，翻译模型的打分越高，s 和 t 之间存在翻译关
系的可能性越大。
2. 生成流畅的译文
公式定义的 g(s,t) 存在的问题是没有考虑词序信息。这里用一个简单的例
子说明这个问题。如图所示，源语言句子“我对你感到满意”有两个翻译结果，第
一个翻译结果是“ ”，第二个是“ ”。虽然
这两个译文包含的目标语单词是一样的，但词序存在很大差异。比如，它们都选择了
“”作为源语单词“满意”的译文，但是在第一个翻译结果中“”处
于第 个位置，而第二个结果中处于最后的位置。显然第一个翻译结果更符合英语
的表达习惯，翻译的质量更高。遗憾的是，对于有明显差异的两个译文，公式计
算得到的函数 g(·) 的得分却是一样的。
源语言句子“我对你感到满意”的不同翻译结果
Q
(j,i)∈
ˆ
A
P (s
j
,t
i
)
我
1
对
2
你
3
感到
4
满意
5
s =
1
2
3
4
5
t
′
=
我
1
对
2
你
3
感到
4
满意
5
s
=
1
2
3
4
5
t
′′
=
图 同一个源语言句子的不同译文所对应的 g(·) 得分
如何在 g(s, t) 引入词序信息呢？理想情况下，函数 g(s,t) 对符合自然语言表达习
惯的翻译结果给出更高的分数，对于不符合的或不通顺的句子给出更低的分数。这
里很自然想到使用语言模型，因为语言模型可以度量一个句子出现的可能性。流畅
的句子语言模型得分越高，反之越低。
这里可以使用第二章介绍的 n 语言模型，它也是统计机器翻译中确保流畅
翻译结果的重要手段之一。n 语言模型用概率化方法描述了句子的生成过程。
5.2 一个简单实例 155
以 语言模型为例，可以使用如下公式计算一个词串的概率：
P
(t) = P
(t
1
...t
l
)
= P (t
1
) ×P (t
2
|t
1
) ×P (t
3
|t
2
) ×... ×P (t
l
|t
l−1
)
其中，t = {t
1
...t
l
}表示由 l 个单词组成的句子，P
(t) 表示语言模型给句子 t 的打分。具
体而言，P
(t) 被定义为 P(t
i
|t
i−1
)(i = 1,2,...,l ) 的连乘
，其中 P (t
i
|t
i−1
)(i = 1,2,...,l )
表示前面一个单词为 t
i−1
时，当前单词为 t
i
的概率。语言模型的训练方法可以参看
第二章相关内容。
回到建模问题上来。既然语言模型可以帮助系统度量每个译文的流畅度，那么
可以使用它对翻译进行打分。一种简单的方法是把语言模型 P
(t) 和公式中的
g(s, t) 相乘，这样就得到了一个新的 g(s,t) ，它同时考虑了翻译准确性（
Q
j,i∈
b
A
P (s
j
,t
i
)）
和流畅度（P
(t)）
g(s, t) ≡
Y
j,i∈
b
A
P (s
j
,t
i
) ×P
(t)
如图所示，语言模型 P
(t) 分别给 t
′
和 t 赋予 和 的概率，这表
明句子 t
′
更符合英文的表达，这与期望是相吻合的。它们再分别乘以
Q
j,i∈
b
A
P (s
j
,t
i
)
的值，就得到公式定义的函数 g(·) 的得分。显然句子 t
′
的分数更高。至此，完
成了对函数 g(s,t) 的一个简单定义，把它带入公式就得到了同时考虑准确性和
流畅性的句子级统计翻译模型。
源语言句子“我对你感到满意”的不同翻译结果
Q
(j,i)∈
ˆ
A
P (s
j
,t
i
) ×P
(t)
我
1
对
2
你
3
感到
4
满意
5
s =
1
2
3
4
5
t
′
=
×
我
1
对
2
你
3
感到
4
满意
5
s =
1
2
3
4
5
t
′′
=
×
图 同一个源语言句子的不同译文所对应的语言模型得分和翻译模型得分
5.2.5 解码
解码是指在得到翻译模型后，对于新输入的句子生成最佳译文的过程。具体来
说，当给定任意的源语言句子 s，解码系统要找到翻译概率最大的目标语译文
ˆ
t。这
为了确保数学表达的准确性，本书中定义 P (t
1
|t
0
) ≡ P (t
1
)
156 Chapter 5. 基于词的机器翻译建模 肖桐 朱靖波
个过程可以被形式化描述为：
b
t = argmax
t
P (t|s)
其中 argmax
t
P (t|s) 表示找到使 P (t|s) 达到最大时的译文 t。结合小节中关于
P (t|s) 的定义，把公式带入公式得到：
b
t = argmax
t
g(s, t)
P
t
′
g(s,t
′
)
在公式中，可以发现
P
t
′
g(s,t
′
)
是一个关于 s 的函数，当给定源语句 s 时，
它是一个常数，而且 g(·) ≥0，因此
P
t
′
g(s,t
′
)
不影响对
b
t 的求解，也不需要计算。基
于此，公式可以被化简为：
b
t = argmax
t
g(s, t)
公式定义了解码的目标，剩下的问题是实现 argmax，以快速准确地找到
最佳译文
b
t。但是，简单遍历所有可能的译文并计算 g(s, t) 的值是不可行的，因为
所有潜在译文构成的搜索空间是十分巨大的。为了理解机器翻译的搜索空间的规模，
假设源语言句子 s 有 m 个词，每个词有 n 个可能的翻译候选。如果从左到右一步步
翻译每个源语言单词，那么简单的顺序翻译会有 n
m
种组合。如果进一步考虑目标语
单词的任意调序，每一种对翻译候选进行选择的结果又会对应 m! 种不同的排序。因
此，源语句子 s 至少有 n
m
·m! 个不同的译文。
n
m
·m! 是什么样的概念呢？如表所示，当 m 和 n 分别为 和 时，译文只
有 个，不算多。但是当 m 和 n 分别为 和 时，即源语言句子的长度 ，每
个词有 个候选译文，系统会面对 2.4329 ×10
38
个不同的译文，这几乎是不可计算
的。
表 机器翻译搜索空间大小的示例
句子长度 m 单词翻译候选数量 n 译文数量 n
m
·m!
×10
38
×10
47
已经有工作证明机器翻译问题是 难的
。对于如此巨大的搜索空间，需要
一种十分高效的搜索算法才能实现机器翻译的解码。在第二章已经介绍一些常用的
5.2 一个简单实例 157
搜索方法。这里使用一种贪婪的搜索方法实现机器翻译的解码。它把解码分成若干
步骤，每步只翻译一个单词，并保留当前“最好”的结果，直至所有源语言单词都被
翻译完毕。
我
对
你
感到
满意
输入 待翻译句子（已经分词）
π
π
π
π π
ϕ
best.translation =
ϕ
best.j = −1
i = 1,j = 1
g(s, t)
翻译结果
h 存放临时翻译结果
h = ϕ
我
对
你
感到
满意
输入 待翻译句子（已经分词）
π
π
π
π π
ϕ
best.translation =
ϕ
best.j = −1
i = 1,j = 1
g(s, t)
翻译结果
h 存放临时翻译结果
if used[j] = false then
我
对
你
感到
满意
输入 待翻译句子（已经分词）
π
π
π
π π
ϕ
best.translation =
ϕ
best.j = −1
i = 1,j = 2
g(s, t)
翻译结果
h 存放临时翻译结果
h = h ∪(best, π[j])
我
对
你
感到
满意
输入 待翻译句子（已经分词）
π
π
π
π π
ϕ
best.translation =
best.j = 1
i = 1,j = 5
g(s, t)
翻译结果
h 存放临时翻译结果
best = (h)
←
图 贪婪的机器翻译解码过程实例
图给出了贪婪解码算法的伪代码。其中 π 保存所有源语单词的候选译文，π[ j]
表示第 j 个源语单词的翻译候选的集合，best 保存当前最好的翻译结果，h 保存当前
步生成的所有译文候选。算法的主体有两层循环，在内层循环中如果第 j 个源语单词
没有被翻译过，则用 best 和它的候选译文 π[j] 生成新的翻译，再存于 h 中，即操作
h = h ∪(best,π[j])。外层循环再从 h 中选择得分最高的结果存于 best 中，即操作
best = (h)；同时标记相应的源语言单词状态为已翻译，即 used[best.j] =
true。
158 Chapter 5. 基于词的机器翻译建模 肖桐 朱靖波
Function s
π =s
best = ϕ
for i [1, m] do
h = ϕ
foreach j [1, m] do
if used[j] = false then
h = h∪(best, π[j])
best = (h)
used[best.j] = true
return best.translatoin
输出 找的最佳译文
输入 源语句子 s = s
1
...s
m
获取每个单词
的翻译候选
m
n n n n n
best 用于保存当前最好的翻译结果
h 用于保存每步生成的所有译文候选
a,b 返回
a 和 b 的所有组合
a
1
a
2
×
b
1
b
2
=
a
1
b
1
a
1
b
2
a
2
b
1
a
2
b
2
保留得分最高的结果
←
记录已经翻译过
的源语单词
m
图 贪婪的机器翻译解码算法的伪代码
该算法的核心在于，系统一直维护一个当前最好的结果，之后每一步考虑扩展
这个结果的所有可能，并计算模型得分，然后再保留扩展后的最好结果。注意，在每
一步中，只有排名第一的结果才会被保留，其他结果都会被丢弃。这也体现了贪婪
的思想。显然这个方法不能保证搜索到全局最优的结果，但是由于每次扩展只考虑
一个最好的结果，因此该方法速度很快。图给出了算法执行过程的简单示例。当
然，机器翻译的解码方法有很多，这里仅仅使用简单的贪婪搜索方法来解决机器翻
译的解码问题，在后续章节会对更加优秀的解码方法进行介绍。
