7.6 最小错误率训练 217
7.6 最小错误率训练
除了特征设计，统计机器翻译也需要找到每个特征所对应的最优权重 λ
i
。这也
就是机器学习中所说的模型训练问题。不过，需要指出的是，统计机器翻译关于模型
训练的定义与传统机器学习稍有不同。在统计机器翻译中，短语抽取和翻译概率的
估计被看作是模型训练（Model Training），也就是说这里的模型训练是指特征函数的
学习；而特征权重的训练，一般被称作权重调优（Weight Tuning），而这个过程才真
正对应了传统机器学习（如分类任务）中的模型训练过程。在本章中，如果没有特殊
说明，权重调优就是指特征权重的学习，模型训练是指短语抽取和特征函数的学习。
想要得到最优的特征权重，最简单的方法是枚举所有特征权重可能的取值，然
后评价每组权重所对应的翻译性能，最后选择最优的特征权重作为调优的结果。但
是特征权重是一个实数值，因此可以考虑把实数权重进行量化，即把权重看作是在
固定间隔上的取值，比如，每隔
0.01
取值。即使是这样，同时枚举多个特征的权重
也是非常耗时的工作，当特征数量增多时这种方法的效率仍然很低。
这里介绍一种更加高效的特征权重调优方法
——
最小错误率训练（Minimum
Error Rate Training，MERT）。最小错误率训练是统计机器翻译发展中代表性工作，也
是机器翻译领域原创的重要技术方法之一
[234]
。最小错误率训练假设：翻译结果相对
于标准答案的错误是可度量的，进而可以通过降低错误数量的方式来找到最优的特
征权重。假设有样本集合 S = {(s
[1]
,r
[1]
),...,(s
[N]
,r
[N]
)}，s
[i]
为样本中第 i 个源语言
句子，r
[i]
为相应的参考译文。注意，r
[i]
可以包含多个参考译文。S 通常被称为调优
集合（Tuning Set）。对于 S 中的每个源语句子 s
[i]
，机器翻译模型会解码出 n-best 推
导
ˆ
d
[i]
= {
ˆ
d
[i]
j
}，其中
ˆ
d
[i]
j
表示对于源语言句子 s
[i]
得到的第 j 个最好的推导。{
ˆ
d
[i]
j
} 可
以被定义如下：
{
ˆ
d
[i]
j
} = argmax
{d
[i]
j
}
M
X
i=1
λ
i
·h
i
(d,t
[i]
,s
[i]
) (7.17)
对于每个样本都可以得到 n-best 推导集合，整个数据集上的推导集合被记为
ˆ
D
=
{
ˆ
d
[1]
,...,
ˆ
d
[N]
}
。进一步，令所有样本的参考译文集合为
R
=
{
r
[1]
,...,r
[N]
}
。最小
错误率训练的目标就是降低
ˆ
D 相对于 R 的错误。也就是，通过调整不同特征的权重
λ = {λ
i
}，让错误率最小，形式化描述为：
ˆ
λ = arg min
λ
Error(
ˆ
D,R) (7.18)
其中，Error(·) 是错误率函数。Error(·) 的定义方式有很多，一般来说 Error(·) 会与机器
翻译的评价指标相关，例如，词错误率 (WER)、位置错误率 (PER)、BLEU 值、NIST 值
等都可以用于 Error(·) 的定义。这里使用 1−BLEU 作为错误率函数，即 Error(
ˆ
D,R) =
218 Chapter 7. 基于短语的模型 肖桐 朱靖波
1 −BLEU(
ˆ
D,R)。则公式(7.18)可改写为：
ˆ
λ = arg min
λ
(1 −BLEU(
ˆ
D,R))
= argmax
λ
BLEU(
ˆ
D,R) (7.19)
需要注意的是，BLEU 本身是一个不可微分函数。因此，无法使用梯度下降等方
法对式(7.19)进行求解。那么如何能快速得到最优解？这里会使用一种特殊的优化方
法，称作线搜索（Line Search），它是 Powell 搜索的一种形式
[278]
。这种方法也构成
了最小错误率训练的核心。
首先，重新看一下特征权重的搜索空间。按照前面的介绍，如果要进行暴力搜
索，需要把特征权重的取值按小的间隔进行划分。这样，所有特征权重的取值可以
用图7.20的网格来表示。
0.01
0.00
0.02
.
.
.
1.00
λ
1
λ
2
...
λ
M−1
λ
M
M 个特征函数
V 种
取值
(a) 搜索空间
0.01
0.00
0.02
.
.
.
1.00
λ
1
λ
2
...
λ
M−1
λ
M
← path:
w
1
= 0.01
w
2
= 0.02
.
.
.
w
M
= 1.00
(b) 一条搜索路径
0.01
0.00
0.02
.
.
.
1.00
λ
1
λ
2
...
λ
M−1
λ
M
M
V
种组合
(c) 多条搜索路径
图 7.20 特征权重的搜索空间表示
其中横坐标为所有的 M 个特征函数，纵坐标为权重可能的取值。假设每个特征
都有 V 种取值，那么遍历所有特征权重取值的组合有 M
V
种。每组 λ = {λ
i
} 的取值
实际上就是一个贯穿所有特征权重的折线，如图7.20中间蓝线所展示的路径。当然，
可以通过枚举得到很多这样的折线（图7.20右）。假设计算 BLEU 的时间开销为 B，
那么遍历所有的路径的时间复杂度为 O( M
V
·B)，由于 V 可能很大，而且 B 往往也
无法忽略，因此这种计算方式的时间成本是极高的。如果考虑对每一组特征权重都
需要重新解码得到 n-best 译文，那么基于这种简单枚举的方法是无法使用的。
对全搜索的一种改进是使用局部搜索。循环处理每个特征，每一次只调整一个
特征权重的值，找到使 BLEU 达到最大的权重。反复执行该过程，直到模型达到稳
定状态（例如 BLEU 不再降低）。
图7.21左侧展示了这种方法。其中蓝色部分为固定的权重，相应的虚线部分为当
前权重所有可能的取值，这样搜索一个特征权重的时间复杂度为 O(V ·B)。而整个
算法的时间复杂度为 O(L ·V ·B)，其中 L 为循环访问特征的总次数。这种方法也被
称作格搜索（Grid Search）。
格搜索的问题在于，每个特征都要访问 V 个点，且不说 V 个点无法对连续的特
7.6 最小错误率训练 219
0.01
0.00
0.02
.
.
.
1.00
λ
1
λ
2
...
λ
M−1
λ
M
固定的权重
有效取值点
无效取值点
0.01
0.00
0.02
.
.
.
1.00
λ
1
λ
2
...
λ
M−1
λ
M
图 7.21 格搜索（左侧：所有点都访问（蓝色）；右侧：避开无效点（绿色））
征权重进行表示，里面也会存在大量的无用访问。也就是说，这 V 个点中绝大多数
点根本“不可能”成为最优的权重。可以把这样的点称为无效取值点。
能否避开这些无效的权重取值点呢？再重新看一下优化的目标 BLEU。实际上，
当一个特征权重发生变化时，BLEU 的变化只会出现在系统 1-best 译文发生变化的
时候。那么，可以只关注使 1-best 译文发生变化的取值点，因为其他的取值点都不会
使优化的目标函数产生变化。这也就构成了线搜索的思想。
假设对于每个输入的句子，翻译模型生成了两个推导 d = {d
1
,d
2
}，每个推导 d
的得分 score(d) 可以表示成关于第 i 个特征的权重 λ
i
的线性函数：
score(d) =
X
k=1
λ
k
·h
k
(d)
= h
i
(d) ·λ
i
+
X
k̸=i
λ
k
·h
k
(d)
= a ·λ
i
+ b (7.20)
这里，a = h
i
(d) 是直线的斜率，b =
P
M
k̸=i
λ
k
·h
k
(d) 是截距。有了关于权重 λ
i
的
直线表示，可以将 d
1
和 d
2
分别画成两条直线，如图7.22所示。在两条直线交叉点的
左侧，d
2
是最优的翻译结果；在交叉点右侧，d
1
是最优的翻译结果。也就是说，只
需知道交叉点左侧和右侧谁的 BLEU 值高，λ
i
的最优值就应该落在相应的范围，比
如，这个例子中交叉点右侧（即 d
2
）所对应的 BLEU 值更高，因此最优特征权重
ˆ
λ
i
应该在交叉点右侧（λ
x
∼ λ
i
任意取值都可以）。
这样，最优权重搜索的问题就被转化为找到最优推导 BLEU 值发生变化的点的
问题。理论上，对于 n-best 翻译，交叉点计算最多需要
n(n−1)
2
次。由于 n 一般不会
过大，这个时间成本完全是可以接受的。此外，在实现时还有一些技巧，比如，并
不需要在每个交叉点处对整个数据集进行 BLEU 计算，可以只对 BLEU 产生变化的
部分（比如 n-gram 匹配的数量）进行调整，因此搜索的整体效率会进一步得到提高。
相比于格搜索，线搜索可以确保在单个特征维度上的最优值，同时保证搜索的效率。
220 Chapter 7. 基于短语的模型 肖桐 朱靖波
d
1
d
2
score
0
λ
x
λ
i
0
λ
x
λ
i
ˆ
d = d
1
ˆ
d = d
2
BLEU
挑选
ˆ
λ
i
图 7.22 推导得分关于权重的函数（左）以及对应的 BLEU 值变化（右）
还有一些经验性的技巧用来完善基于线搜索的 MERT。例如：
• 随机生成特征权重的起始点。
• 搜索中，给权重加入一些微小的扰动，避免陷入局部最优。
• 随机选择特征优化的顺序。
• 使用先验知识来指导 MERT（对权重的取值范围进行约束）。
• 使用多轮迭代训练，最终对权重进行平均。
最小错误率训练最大的优点在于可以用于目标函数不可微、甚至不连续的情况。
对于优化线性模型，最小错误率训练是一种很好的选择。但是，也有研究发现，直
接使用最小错误率训练无法处理特征数量过多的情况。比如，用最小错误率训练优
化 10000 个稀疏特征的权重时，优化效果可能会不理想，而且收敛速度慢。这时也
可以考虑使用在线学习等技术对大量特征的权重进行调优，比较有代表性的方法包
括 MIRA
[279]
和 PRO
[280]
。由于篇幅所限，这里不对这些方法做深入讨论，感兴趣的读
者可以参考7.8节的内容，对相关文献进行查阅。