对数线性翻译模型的判别式训练综述
2013-04-29 00:44:03刘乐茂赵铁军
智能计算机与应用 2013年6期
刘乐茂 赵铁军
摘要：目前几乎所有的统计机器翻译系统都采用对数线性模型建模. 判别式训练是基于对数线性翻译系统的一个重要组成部分，其任务就是优化对数线性模型的参数。到现在为止，有很多判别式训练方法可以用来训练翻译模型权重。从似然函数、错误率函数和可扩展方法三个方面，系统地阐述并分析了这些训练方法，旨在让更多的研究者更好地了解判别式训练方法的发展现状、为判别式训练的进一步发展起到推动作用。同时，还就判别式训练提出了两个值得进一步探讨的问题。
关键词：统计机器翻译； 对数线性模型； 判别式训练
中图分类号：TP391.2 文献标识码：A文章编号：2095-2163（2013）06-0014-04
0引言
统计方法[1]已经成为机器翻译建模的主流方法，特别在Och和Ney[2]提出了基于对数线性模型的统计机器翻译模型之后。目前，几乎所有的统计机器翻译系统都处于对数线性模型框架的支持和限定之下。与产生式的翻译模型[1]相比，对数线性翻译模型不需要考虑翻译的生成过程，可直接采用判别式的统计模型建模；其最大优点在于，能够允许加入任意的翻译特征。因而，可将翻译的问题转化为特征工程的问题，这就为翻译系统的研究和设计带来很大的便利。
假设f是一个源语言句子，e为其一个可能的翻译。形式上，基于对数线性（最大熵）的翻译模型[2]，可以表述如下：
P（e|f：W）=exp（∑iWi·hi（f，e））∑e′exp（∑iWi·hi（f，e′））（1）
其中，e′是f所有可能的一个翻译；h1是双语对（f，e）的特征，其取值为实数；W=
（f；W）=argmaxeP（e|f：W）=argmaxe∑iWi·hi（f，e）（2）
上式也称为最大后验解码原则。那么如何事先确定这个参数W呢？其准则又是什么呢？这就是判别式训练的问题。具体来说，判别式训练的任务是，给定一个开发集，优化得到一个合理的参数W，使得这个参数在测试时性能良好。
机器翻译任务本身固有的一些特点，比如翻译模型中的隐含变量和结构化的搜索空间等等，导致翻译模型的参数估计存在很多困难。不过，经过数十年的发展历程，大批研究者相继提出了许多训练方法，这些方法极大地推动了统计机器翻译的进展。但是，据研究所知，目前还没有工作就这些方法进行系统地阐述与介绍。本文中，将系统地回顾这些方法，同时就这些方法的优缺点进行分析与讨论，旨在使更多的研究者能够深入了解判别式训练方法的发展现状、为判别式训练的进一步发展起到基础性地引领作用。
1基于似然函数的训练方法
首先，为行文约定一些记号：设（f，e）为一个双语对，其中f为源语言，e是其一个翻译。给定开发集{fs，cs，rs}Ss=1，其中fs是开发集中的源语言句子，cs是fs的一个候选翻译集合，rs是fs的参考译文集，其中每个元素记为rks，k=1，…，Ls，Ls为rs中元素的个数。
既然是估计概率模型的参数，就必然不能缺少极大似然估计，因为这是概率模型参数估计的典型方法。事实上，在文献[2]提出最大熵翻译模型的框架时，其中采用的参数学习方法就是极大似然估计法。自然地，{fs，cs，rs}Ss=1上的对数似然函数的定义如下式：
∑Ss=11Ls∑Lsk=1logP（rks|fs；W）（3）
然而，由于某些rks是不可达的，这样，无法计算其所对应的似然函数。Och 和Ney[2]采用如下的方法来近似上述似然函数，即从fs可达的那些翻译中，比如对fs进行k-best解码得到的译文集cs都是可达的，从中选取若干个与参考译文集最相似的译文（依据句子级别的BLEU，定义相似度），作为伪参考译文，这些伪参考译文集记为eks，为方便起见，假设参考译文集亦含有Ls个元素。那么基于伪参考译文集的似然函数为：
∑Ss=11Ls∑Lsk=1logP（eks|fs；W）（4）
最小化公式（4）的一个难点是候选翻译的指数级空间，而精确地计算公式（1）中的归一化因子也很困难，因此，需要借助于合理的近似策略。 Och 和Ney[2]采用的方法是使解码器输出k-best候选翻译集cs，并在cs上近似地计算归一化因子。其后就是典型的优化问题，通用优化方法都可以实现公式（4）的优化，比如梯度法，共轭梯度、拟牛顿法（LBFGS）等等，Och 和Ney[2]采用了GIS算法。
需要注意的是，由于似然函数是严格凸函数，最大似然估计方法可以为公式 （4）找到全局最优解。尽管如此，这种方法在实际的翻译任务中效果并不好，目前几乎已经不再采用。然而，这种利用k-best候选翻译来代替整个翻译候选空间的思想，对后续的参数学习算法起着十分重要的作用。更具体地说，其后许多著名的参数学习算法都嵌入在这种框架之内，所不同的只是，这些算法采用的优化目标各不相同而已。
2基于错误率的训练方法
极大似然估计的一个缺点是，没有直接利用翻译的评价度量比如BLEU[3]，来作为优化的目标函数，导致了优化目标同翻译评价度量之间的关系不太紧密、一致。
为此，Och 在2003年提出了最小错误率训练（简记，MERT）的方法[4]，其想法是，直接利用翻译评价度量作为优化的目标函数，以期能够得到最优的参数，使得在开发集上该参数得到的翻译结果的BLEU 值最高。MERT是机器翻译参数估计方法中最通用、最成功和最受欢迎的算法。在每届翻译评测中，几乎所有的翻译系统都采用MERT进行参数估计。形式上，MERT试图解决如下的优化问题：
minWE{rs，（fs；W）}Ss=1（5）
其中，（fs；W）表示在翻译候选集cs中，根据权重W，按照最大解码原则公式（2）而得到的一个翻译。在式（5）中，E是一个篇章级的翻译评价度量，表示翻译文档 {（fs；W）}Ss=1在参考译文{rs}Ss=1下的评价得分，比如篇章级的BLEU；其他的记号如前所述。公式（5）的目标函数称为错误率函数。由于公式（5）中的错误率函数不可导，甚至不连续，因而，一般的梯度方法并不适用，有效地求解公式（5）存在困难。
本质上说，MERT是一种特殊的Powell算法，可启发式地选择坐标向量作为搜索方向。该算法的思路是，每次都选用所有坐标向量作为搜索方向，然后沿着每个搜索方向进行线搜索（line search）得到一个点；比较所有坐标方向上的线搜索得到的点的目标函数值，选择目标函数值最小的点作为下次迭代的起点；上述两个步骤反复下去，直至算法收敛。MERT的最大贡献在于，能够在多项式的时间内执行精确的线搜索（exact line search），也即是，在给定的方向上能够找到该方向使目标函数值最小的点。MERT的精确线搜索可以解释如下。假设开发集中仅仅含有一个句子，并假设当前的搜索方向是第j个坐标方向，公式（5）关于参数Wj是分段线性函数，而且函数至多有Ls个线性的片段。这样，遍历这个分段线性函数就可以找到最小值点Wmaxj。对于开发集含有多个句子的情况，只需要组合多个分段线性函数，算法的思想也与其类似。值得注意的是，虽然MERT在线搜索时，可以找到全局最优的点，但是整个算法不能保证必定收敛到全局最小点。相似地，Zhao等[5]提出了另外一种非梯度的方法-单纯型法最小化公式（5）。
由于公式（5）中的目标函数是非凸的，导致上述方法不可避免地陷入到局部最优的境地。原始的MERT算法没有考虑局部最优的问题，这样，如何避免性能不好的局部最优点就自然成为一个重要的研究课题。Moore和Quirk[6]在MERT中引入了随机初始点的策略以避开性能不好的局部最优点。具体来说，就是在MERT迭代过程中，定义了两种随机方法，这两种方法不同之处在于产生随机初始点的方式不同。第一种方法是随机初始化，是按照均匀分布产生多个初始点，对每个初始点都运行一遍MERT，就可以得到多个局部最优点，再比较这几个局部点对应的BLEU值，选择BLEU值最高的那个局部最优点。第二种方法是随机行走，是在上次选择的局部点的基础上，引入标准的高斯噪声，抽样出一个处于局部点周围的初始点，并运行MERT得到另外一个局部最优点，再比较新旧两个局部对应的BLEU值，以决定是否接受新的局部最优点。Galley和Quirk[7]则利用组合优化的方法，寻找到公式（5）的全局最优解。其主要思想同MERT中的精确线搜索相似，不同于MERT中精确线搜索的地方就在于求解一个一维的分段线性函数，并计算一个多维的分段线性函数。换句话说，该方法不是按照某一个坐标向量计算公式（5），而是对所有的方向计算公式（5），同时将多变量的优化公式（5）转化成一个线性规划问题。详细做法是，将各独立句子的k-best翻译列表中的每个候选翻译的特征向量都对应于一个多维欧式空间中的点，再利用线性规划的方法计算k-best翻译列表对应的集合的最小凸包，并根据所得到最小凸包就可以求得公式（5）的解；其次，将每个句子的最小凸包进行组合，就可以得到公式（5）中对应的分段线性的目标函数（关于参数W），遍历这个分段线性函数可以找到最优的解。这个方法的最大贡献是，方法表明了公式（5）可以找到全局最优解，但是，其算法复杂度却是指数级的，因此，不宜推广到规模很大的开发集上。
如前所述，公式（5）中的错误率函数是分段线性的，具有许多局部最小值的区域。由于错误率函数的形状错综复杂，高峰和低谷的分布异常不均匀。这样导致的结果是，对于不同的开发集，所对应的错误率函数的最小值区域并不具有一致性。因此，即使是找到了公式（5）的（局部）最小值点，公式（5）的最小值点附近区域的其他点的错误率函数值也有可能会达到很高。如此，该最小值点的推广能力未必是最好的。为了避免这种情况的发生，许多研究者为MERT提出了正则的方法，以避免找到推广能力不好的（局部）最优点。Smith和eisner[8]采用光滑的函数来逼近错误率函数，以减少错误率函数的“尖锐点”现象。通过使用一个期望风险函数来取代公式（5）中的目标函数：
minWExpectation（W；l）=minW∑Ss=1∑e∈csl（e）P（e|fs；W）（6）
其中，l（e）表示与参考译文相比e具有的损失值， 和公式（5）中E的意义一样，不同的只是，这是定义在句子级别而已。公式（6）也即MBR的最小风险准则。值得注意的是，公式（6）是连续可微的，是公式（5）的“光滑逼近”。同Smith和Eisner采用光滑逼近的技术实现正则不同，Cer等[9]采用了离散正则的方法。其主要思想是，在评价某一个权重向量时，不仅考虑这个向量所在的线性区域（因为公式（5）中的目标函数是分片线性的）对应的BLEU值，而且考虑这个区域附近的k个其他线性区域的BLEU得分情况。对于每个线性区域的目标BLEU值，则提出了两种组合方法。一种是max， 定义了每个线性区的BLEU值为该区域的k个附近区域的BLEU值最高值。另一种方法是average， 则将这个线性区域的BLEU值定义为k个附近区域BLEU值的平均值。
3可扩展的训练方法
参数估计方法的可扩展性是一个重要的研究问题，也是近几年的一个研究热点。其中的原因是，对数线性模型的一大优点就是可以很灵活地增加特征，而且，现有的研究表明[10]，增加大量的特征有利于提高翻译的性能。为此，MERT就面临着一个重要的问题，其可扩展性不好。需要强调的是，这里的可扩展性是指，在翻译模型的特征不断增加时，MERT的性能会下降；而并不是指MERT在算法效率上的可扩展问题。比如，Chiang等[10]的实验表明，MERT在翻译模型的维数小于30时，性能很好；维数大于50时，性能将变得不好。其中一个可能的原因是，公式（5）的错误率函数是非凸的，随着维数的增加，陷入局部最优的可能性也就越大。为此，许多研究者在这方面提出了具有可扩展性的参数估计方法。Liang等[11]基于感知器的在线学习算法，提出了一种可以优化大量特征的翻译模型。算法的主要思路是：对于源语言fs的参考译文rs和候选译文e′s，那么权重就应该满足：P（rs|fs；W）>P（e′s|fs；W）， 即，W·h（rs，fs）>W·h（e′s fs）。在此，可以使用感知器更新公式：
W←W+h（rs， fs）-h（e′s， fs）（7）
由于参考译文rs可能会不可达，文中提出3种权重更新策略：激进的更新，局部的更新和混合更新方法。激进的更新仅对于参考译文能可达句子，按照公式（7）更新权重；而对于那些参考译本不可达的句子，直接不予考虑更新。局部更新的对象是对所有的句子都进行更新，其做法是使解码器输出k-best候选翻译，将k-best翻译中BLEU 分最高的翻译代替公式（7）中的rs，其他的翻译代替e′s，按照公式（7）更新k-1次。组合的更新方法结合前两种更新方式：如果参考译文可达，执行鲁莽的更新；否则，执行局部更新。相似地，Tillmann和Zhang[12]采用随机梯度的在线更新算法学习大规模特征的翻译模型权重。
Watanabe等[13]以及Chiang等[10]提出了基于大边缘融合松弛（MIRA）算法[14]的翻译模型参数估计方法。同Liang及Tillmann和Zhang的方法一样，这也是一个在线的学习。设当前迭代的权重为Wt；解码器为更新权重由开发集中挑选的句子集{ftk}Bk=1，其中，B为批量大小（Batch size）。那么，更新后的权重Wt+1为如下二次优化问题的解：
其中，λ为大于0的正则系数，O tk（Θtk）为性能较好（不好）的翻译集，r tk为ftk的参考译文集，l（ek，e′k，rtk）为根据rtk评价ek和e′k的句子级BLEU之差。如何挑选O tk（Θtk）对翻译的性能具有一定的影响，Watanabe等[13]以及Chiang等[10]从k-best 翻译列表或者超图中选择句子级BLEU最高（最低）的前几个候选翻译构成O tk（Θtk）。公式（8）对应的二次优化问题可以使用SMO[15]进行求解。MIRA算法的一个缺点是，需要设定很多参数，比如λ和O tk（Θtk）选择所必需的一些参数。不同于上述对MIRA采取在线的更新算法，Cherry和Foster[16]提出了一个批处理的MIRA训练算法。该算法与MERT一样，对开发集中的所有句子，执行一次二次优化。另外，Hopkins和May[17]将翻译模型的参数学习问题看做是排序问题，然后将其转化成了普通的分类问题，并采用开源的分类器实现算法。算法实现简单，而且实验表明也十分有效，同时，还具有很好的可扩展性。受该算法启发，Watanabe[18]提出了一个基于排序的在线学习算法。相似地，文献Bazrafshan等[19]将翻译模型的参数学习问题转化成了一个线性回归问题。同基于排序的二值分类问题相比，这一方法不但获得了更好的翻译性能，而且还具有更好的收敛速度。
4结束语
判别式训练是基于对数线性的统计机器翻译中最重要的一个组成部分。本文在充分调研和深入分析的基础上，对现有的所有主流的训练方法进行了综述。本文主要从似然函数、错误率函数和可扩展的方法三个方面，阐述并分析了各个训练方法的优缺点。判别式训练方法的研究至今只有数十年，而且统计机器翻译本身具有诸多的复杂性制约，目前还有许多问题有待于更深一步的研究和探讨。基于目前关于判别式训练的研究经验，本文在最后提出一些未来值得进一步挖掘的研究问题，希望对这方面的研究者在未来的研究中有所启发，进而为判别式训练的进一步发展乃至统计机器翻译的发展起到推动作用。
首先，对于结构化学习问题，在精确的解码框架下，其判别式训练有着良好的理论基础[20]。然而在机器翻译中，翻译模型通常会包含全局的特征比如语言模型，动态规划的技术则无法采用，因此精确解码是不可能的，往往采用基于柱状搜索的非精确解码方法。非精确解码导致的后果是，算法的收敛性很难得到保证，实际上，现有的判别式训练算法是否能够收敛？需要经过多少次解码迭代才能收敛？这都没有获得理论上的保证。黄亮等[21]指出，当非精确解码满足一定的条件时，收敛性就能够得到保证。因此，可否将现有的解码方式进行适当的修改，以满足黄亮等提出的关于非精确解码的条件？或者可否重新探索满足新的收敛条件和新的解码方式。
其次，对于判别式训练而言，其最终目标是，对于优化得到的权重而言，翻译度量最好翻译对应的模型得分，要大于其他候选翻译的模型得分。由于翻译评价度量不能定义在翻译单元上，而翻译的解码却需要按照翻译单元进行扩展，这就使得训练时几乎不能找到质量最好的翻译。因而，在实践中，机器翻译在训练的过程中，仅仅考虑翻译模型得分最好的k-best候选翻译，而后又在k-best翻译候选中考虑质量最好的翻译。由于k-best仅仅是指数级别翻译空间中一个粗糙的近似，这种近似会影响到判别式训练的效果。那么如何在解码搜索中同时兼顾考虑翻译评价度量就是一个重要的问题。
参考文献：
[1]BROWN P F， PIETRA V J D， PIETRA S A D， et al. The mathematics of statistical machine translation： parameter estimation. comput. Linguist. 1993，19：263–311.
[2]OCH F J， NEY H. Discriminative training and maximum entropy models for statistical machine translation[C]//Proc. of ACL. PA， USA， 2002：295–302.
[3]PAPINENI K， ROUKOS S， WARD T， et al. Bleu： a method for automatic evaluation of machine translation[C]//Proc. of ACL. Philadelphia， Pennsylvania， USA， 2002：311–318.
[4]OCH F J. Minimum error rate training in statistical machine translation[C]//Proc. of ACL. Sapporo， Japan， 2003：160–167.
[5]ZHAO B， CHEN S. A simplex armijo downhill algorithm for optimizing statistical machine translation decoding parameters[C]//Proc. of NAACL. Stroudsburg， PA， USA， 2009：21–24.
[6]MOORE R C， QUIRK C. Random restarts in minimum error rate training for statistical machine translation[C]//Proc. of COLing. Stroudsburg， PA， USA， 2008：585–592.
[7]GALLEY M， QUIRK C. Optimal search for minimum error rate training[C]//Proc. of EMNLP. Edinburgh， Scotland， UK.， 2011：38–49.
[8]SMITH D A， EISNER J. Minimum risk annealing for training log-linear models[C]//Proc. of COLING-ACL. Sydney， Australia， 2006：787–794.
[9]CER D， JURAFSKY D， MANNING C D. Regularization and search for minimum error rate training[C]//Proc. of the Third Workshop on SMT， 2008.
[10]CHIANG D， MARTON Y， RESNIK P. Online large-margin training of syntactic and structural translation features[C]//Proc. of EMNLP，2008.
[11]LIANG P， BOUCHARD-C^OT^E A， KLEIN D， et al. An end-to-end discriminative approach to machine translation[C]// Proc. of ACL. Sydney，Australia， 2006：761–768.
[12]TILLMANN C， ZHANG T. A discriminative global training algorithm for statistical Mt[C]//Proc. of ACL. Stroudsburg， PA， USA， 2006：721–728.
[13]WATANABE T， SUZUKI J， TSUKADA H， et al. Online large-margin training for statistical machine translation[C]//Proc. of EMNLP-CoNLL. Prague， Czech Republic， 2007：764–773.
[14]CRAMMER K， SINGER Y. Ultraconservative online algorithms for multiclass problems[J]. Mach. Learn. Res， 2003， 3：951–991.
[15]PLATT J. Fast training of Support vector machines using sequential minimal optimization. SCHOELKOPF B， BURGES C， SMOLA A， （Editors） Advances in Kernel Methods - Support Vector Learning， MIT Press， 1998.
[16]CHERRY C， FOSTER G. Batch tuning strategies for Statistical Machine Translation[C]//Proc. of NAACL. Montrieal， Canada， 2012： 427–436.
[17]HOPKINS M， MAY J. Tuning as ranking[C]//Proc. of EMNLP. Edinburgh， Scotland， UK.， 2011：1352–1362.
[18]WATANABE T. Optimized online rank learning for machine translation[C]//Proc. of NAACL. Montrieal， Canada， 2012：253–262.
[19]BAZRAFSHAN M， CHUNG T， GILDEA D. Tuning as linear regression[C]//Proc. of NAACL. Montreal， Canada， 2012：543–547.
[20]COLLINS M. Discriminative training methods for Hidden Markov Models： theory and experiments with Perceptron Algorithms[C]//Proc. of EMNLP， 2002.
[21]HUANG L， FAYONG S， GUO Y. Structured perceptron with inexact search[C]//Proc. of NAACL. Montrieal， Canada， 2012：142–151.
[14]AKAGI T， SUGENO M. Fuzzy identification of systems and its application to modeling and control[J]. IEEE Transactions on Systems， Man， and， Cybernetics， 1985，15（1）： 116-132.
[15]黄福员. 金融风险预警的MPSO-FNN模型构建与应用[J]. 计算机工程与应用，2009，45（14）：210-212.
[16]ALTMAN E I， MARCO G， VARETTO F. Corporate distress diagnosis： comparisons using linear discriminant Ana analysis and neural networks[J]. Journal of Banking and Finance， 1994， 18： 505-529.
[17]李志辉， 李萌. 我国商业银行信用风险识别模型及其实证研究[J]. 经济科学， 2005（5）： 61-71.
[18]财政部统计评价司. 企业绩效评价问答[M]. 北京：经济科学出版社， 1999.
[19]章彰. 解读巴塞尔新资本协议[M]. 北京： 中国经济出版社， 2005.
