引入集成学习的最大熵短语调序模型

何钟豪，苏劲松，史晓东，陈毅东，黄研洲

(1. 厦门大学 智能科学与技术系, 福建 厦门 361005；2. 厦门大学 软件学院, 福建 厦门 361005)

1 引言

机器翻译中，在不同的语言或者同一语言内部的不同方言之间，存在着非单调性对应，从而导致源语言和目标语言之间的短语顺序不同，这就是调序问题[1]。由于这种问题普遍存在，并且会对机器翻译的效果产生重要影响，如果处理不当，会导致翻译错误，所以调序问题在机器翻译中是一个非常重要的问题。

针对这个问题，很多学者进行了深入的研究，建立了许多模型。在这一系列模型当中，括号转录语法模型[2](Bracket Transduction Grammar，BTG)所使用的括号转录文法较为简单，而且对双语翻译现象具有很高的覆盖率，适合于机器翻译建模。因此，括号转录语法模型近年来引起了研究者们的广泛关注。而本文的研究工作就是在括号转录语法模型的基础上展开的。

括号转录文法当中包含有两条短语规则用于调整短语间的顺序，但是在解决调序问题时仍然存在局限性： 由于没有包含短语的具体内容信息，对于两个相邻的短语块组合在一起时是否需要调序，无法进行很好的判断与处理[3]。对此，熊提出了基于最大熵的括号转录语法(Maximum Entropy Based BTG，MEBTG)模型[4]。该模型在BTG翻译模型的基础上引入一个最大熵调序模型，通过将相邻短语块合并时是否需要调序看成是一个分类问题，构建了一个最大熵分类器，并融合入多种特征，较好地解决了BTG模型无法有效处理调序的问题。但是，基于最大熵的括号转录语法模型的发展仍未成熟，在翻译过程中还存在一些不足，其中较为显著的一个问题是： 在用于抽取调序实例(reordering example)的实际双语语料中，同序(翻译过程中相邻短语块在源语言和目标语言的顺序保持一致即为同序)的短语实例数量远大于逆序(翻译过程中相邻短语块在源语言和目标语言的顺序相反即为逆序)的短语实例数量，这会导致在MEBTG模型中抽取得到的调序实例存在各类样本分布不均匀的情况，容易造成由此训练产生的最大熵分类器的分类效果出现偏差，影响最终机器翻译的质量。

针对这个问题，本文在使用调序实例训练最大熵分类器的过程中，引入了集成学习(Ensemble Learning)的方法，以解决调序实例中存在的数据不平衡问题。集成学习方法是根据样本训练出多个具有差异性的分类器协同工作来完成分类任务，对于减小分类误差问题能够提供有效的帮助。该方法在自然语言处理的许多研究领域都得到广泛应用。受到这些成功应用的启发，我们相信集成学习方法能够较好地解决MEBTG模型中存在的调序实例样本分布不均匀的问题，进而提高翻译系统的性能。实验表明，本文的方法能有效提高MEBTG模型的翻译质量。

本文其他部分安排如下： 第2节介绍相关工作；第3节介绍基于最大熵的括号转录语法模型；第4节介绍引入集成学习方法的调序模型；第5节给出实验结果及分析；第6节给出相关结论以及未来的研究方向。

2 相关工作

括号转录语法模型来源于吴[2]提出的反向转录语法(Inversion Transduction Grammar，ITG)模型的简化模型，该模型以其简洁和易于建立统计模型而广泛应用于自然语言处理的各个领域， 如词对齐和统计机器翻译等[1]。括号转录语法模型在对短语进行调序时，给每个短语分配了一个固定的基于语言对的调序概率，能够有效降低短语调序的搜索空间。但是，该模型对于两个相邻的短语块组合在一起时是否需要调序，仍然无法进行很好的判断与处理，该问题近年来成为了研究者们的研究热点，后续的许多研究也是针对该问题进行的改进。熊等人[4]针对BTG模型不能很好的解决短语的调序问题提出了MEBTG模型，该模型将短语是否需要调序看成是一个分类问题，采用最大熵分类器来对该问题进行建模。该模型考虑了翻译短语所包含的边界词信息，因此能够较好地解决BTG模型的短语调序问题。之后熊等人[5]在基于BTG模型的基础上加入了一个基于语言学标注的调序模型，在调序模型中加入了句法信息等语言学知识以帮助调序。张等人[6]在基于BTG模型的基础上，使用卷积树核方法在源端的句法树中提取出结构化的句法特征，并将其与其他线性特征融合入对数线性模型当中来提高调序模型的预测能力。苏等人[7]提出了一个基于依存的BTG模型，该模型在词法规则中融合入了目标端的依存信息，并使用两个不同的最大熵模型来决定最后的调序问题。

与上面所提到工作在机器翻译模型中引入句法信息的思路不同，陈等人[8]对于BTG模型中的最大熵调序模型进行了改进，在训练最大熵分类器时，不仅使用了调序实例，同样加入了从对齐平行语料中获得的词性标注，词语类别等特征以提高最大熵分类器的性能。同样从特征入手，孙等人[9]针对最大熵训练时特征数据不平衡的问题进行了深入研究，对最大熵短语调序实例特征的抽取算法进行了改进，从而能够抽取出更多准确的短语调序信息，特别是逆序短语的特征信息，并通过限制同序实例的数目，解决最大熵训练过程中的数据不平衡问题，在此基础上，又增加了首词特征、组合特征等特征提高了系统翻译的性能。而本文的工作与其不同之处在于，本文还是按原始的算法抽取出调序实例以及特征。再在训练基于最大熵的调序模型的过程中引入集成学习的方法，对得到的调序实例进行重采样以构成平衡数据集，以此来解决最大熵训练时特征数据不平衡的问题。由于本文只考虑对于调序实例使用集成学习的方法，所以仍然使用在MEBTG模型中使用的边界词特征。

3 MEBTG模型介绍

3.1 翻译规则

由吴[2]提出的BTG模型中共有下面三条语法规则：

翻译时，将源语言句子分割成短语序列进行处理，首先用词汇规则(3)将源语言规则x翻译成目标语言规则y，之后使用短语规则(1)和(2)，(1)表示的是同序规则， (2)表示的是逆序规则。这两条短语规则分别表示两个相邻的小短语块A1和A2在组合成一个大短语块的情况下，翻译时是否要交换位置。不断使用这两条规则就可以将连续的短语序列合并成一个句子。

3.2 基于最大熵的调序模型

MEBTG模型是在BTG模型的基础上引入了一个基于最大熵的调序模型，通过将短语调序问题看成是一个两个类别的分类问题，构建了一个最大熵分类器并融入了合适的特征，从而更好地判断相邻短语块合并时是否需要调序。

首先在相邻块A1和A2之间定义一个统一的调序模型框架，如式(1)所示。

其中o为A1和A2的顺序，同序(straight)或者逆序(inverted)，Ω为调序分数。

在此框架下，A1和A2的位置就有两种可能性： 同序或者逆序。MEBTG模型中使用了基于最大熵的调序模型来预测两个短语块的顺序，对于A1和A2位置的最大熵分数可用式(2)计算：

其中hi∈{0,1}为特征函数，θi为相应特征的权重。

3.3 调序实例与特征

调序实例用于训练最大熵调序模型，因此抽取得到的调序实例的质量好坏,直接影响到调序模型对短语顺序预测的准确度。在调序实例的抽取方面本文参考了基于最大熵调序模型当中的抽取算法[1]。

由于短语的边界单词对预测相邻块语序的信息增益率(Information Gain Ratio， IGR)和整个短语的非常接近。这说明短语的边界单词能够保留整个短语调序的信息[1]。所以对于从调序实例中提取出的最大熵分类器所要用到的特征，本文使用尾词特征(短语中的最后一个单词)。本文使用的四个特征分别为：

(1) 源语言端相邻两个短语块的尾词ct1和ct2；

(2) 目标语言端相邻两个短语块的尾词et1和et2。

表1展示了我们从训练语料中抽取出来的调序实例的样本以及相应的尾词特征。

表1 调序实例样本与特征

注： 表中straight表示实例顺序为同序，inverted表示实例顺序为逆序。cp1和cp2分别表示源语言端的两个相邻短语块，ct1和ct2分别表示源语言端短语块对应的尾词特征，ep1和ep2分别表示目标语言端的两个相邻的短语块，et1和et2分别表示目标语言端短语块对应的尾词特征。

4 引入集成学习的调序模型

4.1 集成学习方法

正如上文所述，从实际双语语料抽取出的调序实例中，存在数据不平衡的情况。而用这样的样本去训练分类器，再对短语间的顺序进行分类就属于不平衡的分类问题。当传统的机器学习方法应对这些不平衡分类问题时，往往出现分类器性能下降，得到的分类器具有很大的偏向性[10]。最常见的表现是少类样本(样本数较少的一类样本)的识别率远低于多类样本(样本数较多的一类样本)，这样会导致本属于少类的样本往往被错分到多类，导致最后的分类结果出现偏差。而用这样的分类器去参与机器翻译的建模，容易导致模型在预测相邻短语块合并的位置顺序时产生错误，从而导致句子的翻译错误，影响机器翻译系统最终的翻译质量。

目前对于处理上述数据不平衡问题主要采用两类策略： 一是改变训练集样本的分布，降低数据不平衡程度，主要包括重采样方法；二是针对非平衡类数据特点构造新算法或改造现有算法，主要包括集成学习方法、代价敏感学习方法等[11]。

第一类策略中的重采样方法是目前主流的针对数据不平衡的分类方法中应用较多的方法。该方法又可以分为两类： 欠采样(under-sampling)方法以及过采样(over-sampling)方法[12]。其中，过采样方法通过复制已有或人工合成的方式引入额外的样本，延长了分类器的训练时间，容易出现过度拟合的问题。而欠采样方法是通过减少多类样本使得两类样本数达到平衡，忽略了大部分潜在的有用的多类样本，因此可能会降低分类器的性能。

第二类策略中，代价敏感学习方法能够对错分的少类样本做出更大的惩罚，显著提高少类的分类准确率。但是该方法的缺点是，在多数实际情况中很难对错分的代价给出一个准确的估计，这使得整体的性能提升得不到保证。而集成学习方法在训练阶段通过在多个子训练集上自主选择合适的训练算法来生成独立的子分类器，因此能从不同的算法中选择最佳的子分类器并将它们的预测结果合并，使最终的分类器具有较高的性能[13]。目前，集成学习方法也被广泛应用到各个领域当中。因此，本文引入了集成学习的方法来解决MEBTG模型中存在的调序实例样本分布不均匀的问题。

集成学习方法包含三个重要的因素： 采样策略、分类器训练方法以及分类器集成方法。首先通过采样获得合适的样本，其次根据得到的样本训练出多个分类器协同工作来完成分类任务。这些分类器具有一定的互补功能，对于减小分类误差能够提供有效的帮助。例如，Bagging[14]就是一个比较成功的集成学习算法。它通过对训练样本采用有放回随机采样技术(Bootstrap采样[14])，训练出多个具有差异性的分类器。然后，采用多数投票规则等融合方法，将每个基分类器独自产生的分类结果，融合形成最终的集成分类结果。在本文引入集成学习的方法中，我们使用重采样方法来获得集成个体间的差异性。

下文将具体介绍本文所采用的采样方法以及多分类器融合方法。

4.2 引入集成学习方法的调序模型

本文参考了Bagging的思想，对从语料中抽取出来的调序实例进行了无放回和有放回的欠采样两种方法。

其中无放回欠采样方法的实现步骤如下： 首先从所有的同序实例中，随机抽取与逆序实例数量相同的同序实例集a1，与逆序实例集构成一个平衡数据集S1；其次从排除了a1的同序实例中，随机抽取与逆序实例数量相同的同序实例集a2，构成一个平衡数据集S2；依此类推，一共构造出N个平衡数据集S1，...，SN。最后将这N个平衡数据集作为训练样本，使用最大熵工具训练出N个最大熵分类器。这里N的大小是由同序实例的数量与逆序实例的数量的比值决定的。

而有放回欠采样方法的实现步骤与无放回欠采样方法的实现步骤大致相同，具体如下： 首先从所有的同序实例中，随机抽取与逆序实例数量相同的同序实例集b1，与逆序实例集构成一个平衡数据集T1；其次从所有的同序实例中，另外随机抽取与逆序实例数量相同的同序实例集b2，构成一个平衡数据集T2；依此类推，同样构造出N个平衡数据集T1...TN。最后将这N个平衡数据集作为训练样本，使用最大熵工具训练出N个最大熵分类器。这里N的值与无放回欠采样方法中的N的值相同。

有放回欠采样方法与无放回欠采样方法的差别在于： 用于抽取平衡数据集中同序实例集的原始同序实例，在无放回方法中其数目是不断减少的，确保抽取到的每个同序实例集中不会有重复样本，以增加训练得到的分类器之间的差异性；而有放回方法中实例数目是固定不变的，抽取得到的同序实例集中可能存在重复样本。

对于上述集成学习方法得到的N个最大熵分类器，我们采用了两种分类器融合方法对其结果进行融合。第一种方法是简单融合法，我们将各分类器的分类结果作为单独的特征，加入到对数线性模型当中，再用最小错误率训练方法[15]给每个特征赋予一定的权重；第二种方法是性能加权投票法[16]。在集成学习中，常用的分类器集成方法是最大投票法，最大投票法是一种简单的分类器融合方法，由基分类器先对样本进行判断得出自己的分类结果，对自己所预测的类投一票，最后得票最多的类就是融合学习算法最终的预测结果。而性能加权投票法是在最大投票法基础上的改进，通过给每个基分类器的分类结果加上一个权重，从而让不同基分类器的分类性能得以体现。如式(3)所示。

其中，oj表示的是由第i个分类器确定的两个相邻短语块A1和A2之间的顺序： 同序或者逆序。fi表示的是第i个分类器，λi表示的是分类器fi的加权系数，o表示的是N个分类器融合后得到相邻短语块A1和A2之间的最终顺序。

最终的短语调序结果需要综合考虑这N个分类器的分类结果。这样可以改善传统MEBTG模型中由于只使用一个分类器而产生的分类偏差问题，对于短语顺序的预测能够提供更好的帮助。

5 实验

5.1 实验设置

本文的实验中，基线系统(Baseline)使用了基于短语的MEBTG翻译模型。该模型使用了基于对数线性模型[17]的统计机器翻译框架，依据此框架，本文一共采用了8个特征作为对数线性模型的特征函数，分别是：

(1) 源短语到目标短语的翻译概率；

(2) 目标短语到源短语的翻译概率；

(3) 源短语到目标短语的词汇化权重；

(4) 目标短语到源短语的词汇化权重；

(5) 语言模型；

(6) 词惩罚；

(7) 短语惩罚；

(8) 最大熵调序模型分数。

本文实验中使用的训练语料为包含FBIS语料以及LDC语料中英国国会议事录部分的语料，训练语料中一共包含约98万的平行句对。从训练语料当中抽取出的调序实例中，同序实例的数量约为980万个，逆序实例的数量约为230万个。我们从中分别随机抽取出100万个同序实例以及20万个逆序实例，用于测试最大熵分类器的准确率，而剩下的1 090万个实例用于训练最大熵分类器。为了使所有的逆序实例都能在分类过程中发挥作用，我们根据同序实例与逆序实例数量的比例来确定基分类器的数量，因此，本文在引入集成学习方法的实验中，一共训练得到4个最大熵基分类器。开发集使用的是NIST MT 2002的测试集，测试集使用的是NIST MT 2005的测试集。对于本文在翻译模型中使用到的其他工具，语言模型使用SRILM工具*http://www.speech.sri.com/projects/srilm/根据Gigaword语料训练出的四元语言模型。词语对齐工具采用的是GIZA++[18]。本文采用了张乐开发的训练工具包*http://homepages.inf.ed.ac.uk/s0450736/maxent_toolkit.html作为训练调序实例的最大熵分类器的工具包。对于实验结果，我们采用大小写不敏感的BLEU[19]来评价翻译质量，并且对不同方法的翻译结果进行显著性测试[20]。表2展示了我们所用的实验数据。

注： 其中‘K’表示的是单位“千”，‘M’表示的是单位“百万”。

为了对比本文引入集成学习方法的实验优劣，本文同样采用另外几种重采样方法单独做了几个对比实验，实验方法如下：

(1) 随机过采样： 以多类样本数量为参照，在少类样本中通过过采样方法随机选择样本，使得少类样本数与多类样本数达到平衡，并训练出一个最大熵分类器；

(2) 简单过采样： 以多类样本数量为参照，直接不断复制所有少类样本，使得少类样本数与多类样本数达到平衡，并训练出一个最大熵分类器；

(3) 随机欠采样： 以少类样本数量为参照，在多类样本中使用欠采样方法随机选择样本，采样得到一个多类样本的子集，使得多类样本数与少类样本数达到平衡，并训练出一个最大熵分类器。

表3展示了通过使用不同重采样方法训练得到的最大熵分类器，对于前文提到的100万个同序实例以及20万个逆序实例的分类准确率。可以看出，原始不平衡数据训练得到的分类器，对于同序实例的分类准确率较高，而对于逆序实例的分类准确率要低于其他方法，这是由于不平衡数据中，多类样本要远多于少类样本，因此在分类过程中容易导致少类被错分到多类，从而降低了少类样本的分类准确率。随机欠采样由于抛弃了大量可能对分类产生帮助的多类样本，因此训练得到的分类器准确率要小于两种过采样的方法。而对于集成学习方法中获得的4个分类器，由于都是使用欠采样方法获得的，因此分类准确率同样低于过采样的方法。

表3 不同采样方法的分类器准确率

注： 其中单分类器方法只包含一个分类器，对应一个准确率；集成学习方法包含有4个分类器，对应4个准确率；“同序”表示的是分类器对同序实例的分类准确率，“逆序”表示的是分类器对逆序实例的分类准确率。

5.2 实验结果

通过表4的实验结果我们可以看出，对于采用的所有采样方法，实验结果相对于Baseline都有一定的提升。由于Baseline的分类器对于逆序实例的分类准确率较低，因此实验结果均低于本文所使用的其他的方法。而随机过采样方法跟随机欠采样方法的分类性能差异不大，而且均使用单分类器的方法，提升效果不明显。由于随机欠采样的方法只是从多类样本中选择部分样本，使得大量未选中的多类样本在后面的分类过程中未能发挥作用，从而丢失了很多可能对分类有帮助的样本。而随机过采样的方法也只是随机的复制少类样本，并没有增加额外的信息，所以对分类的性能不会产生很大的帮助，不能从本质上解决少类样本的稀缺性和数据表示的不充分性。

表4 不同采样方法的实验结果

注： “简单”表示采用的是简单融合法，“投票”表示采用的是性能加权投票法。实验结果中“*”和“**”系统相比基线系统翻译质量具有显著提升(显著水平p<0.05和p<0.01)。

本文使用的集成学习方法能够对实验结果有较为显著的提高，虽然每个分类器的准确率均低于过采样方法的分类器准确率，但是由于集成分类器综合考虑了多分类器的结果，因此能够有效减少分类误差，提高机器翻译质量。对比有放回方法和无放回方法，由于有放回方法在采样过程中会丢失许多训练样本，因此分类准确率不如无放回的方法，最后的实验效果也弱于无放回的方法。对于本文使用的两种分类器集成方法，性能加权投票法在考虑了各个分类器分类结果的基础上，还充分考虑了各个分类器的分类性能，而由于本文实验中各个分类器之间性能差异不大，因此该方法相对于简单地将所有分类结果单独作为特征方法的提升效果不明显。

从表4中可以看出，本文使用的方法最多相比基线系统提高了近1.0的BLEU值，可见本文使用的集成学习方法对于MEBTG模型在解决短语调序的问题上，能够提供有效的帮助。

6 结论与未来工作

本文针对MEBTG模型中用于最大熵分类器训练的调序实例的数据分布不平衡的问题，引入了集成学习多分类器融合的方法。实验结果表明，这个方法能够有效提高机器翻译的质量，特别是其中通过性能加权投票融合的无放回欠采样的方法，能够比基线系统提升近1.0的BLEU值。比较研究还发现，对于传统的过采样和欠采样的方法，该方法都有明显的优势。

在未来的研究工作中，我们会研究如何更好地使用其他学习算法层面的策略，包括代价敏感学习和特征选择方法等来解决数据不平衡的分类问题，同样，我们也会考虑用更进一步的融合方法，例如贝叶斯融合法、基于D-S证据理论的整合方式等来融合训练出的多分类器的分类结果。同时，不平衡数据分类问题中，特征的选择方式也有异于传统的特征选择方式，如何更有效的选择合适的特征来提高分类的效果，也是我们下一步研究的方向。

[1] 熊德意.基于括号转录语法和依存语法的统计机器翻译研究[D].北京： 中国科学院计算技术研究所，2007.

[2] Dekai Wu. Stochastic Inversion Transduction Grammars and Bilingual Parsing of Parallel Corpora[J]. Computational linguistics，1997，25(6)： 377-403.

[3] 刘群. 基于句法的统计机器翻译模型与方法. 中文信息学报. 2011, 25(6): 63-71.

[4] Deyi Xiong，Qun Liu， Shouxun Lin. Maximum Entropy Based Phrase Reordering Model for Statistical Machine Translation[C]//Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics，Sydney, Australia，2006： 521-528.

[5] Deyi Xiong，Min Zhang，Aiti Aw. A linguistically annotated reordering model for BTG-based statistical machine translation[C]//Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics on Human Language Technologies，Columbus，Ohio，USA，2008： 149-152

[6] Min Zhang，Haizhou Li. Tree kernel-based SVM with structured syntactic knowledge for BTG-based phrase reordering[C]//Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing，Suntec，Singapore，2009： 698-707.

[7] Jinsong Su，Yang Liu，Haitao Mi. Dependency-based bracketing transduction grammar for statistical machine translation[C]//Proceedings of the 23rd International Conference on Computational Linguistics，Beijing，China，2010: 1185-1193.

[8] Hanbin Chen，Jiancheng Wu， Jason S Chang. Learning bilingual linguistic reordering model for statistical machine translation[C]//Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics，Boulder Colorado，USA，2009： 254-262.

[9] 孙萌，姚建民，吕雅娟，等. 基于最大熵短语调序模型的特征抽取算法改进[J]. 中文信息学报，2011，25(2)： 78-82.

[10] Shoushan Li，Guodong Zhou，Zhongqing Wang. Imbalanced Sentiment Classification[C]//Proceedings of the 20th ACM international conference on information and knowledge management，Glasgow，Scotland，UK，2011： 2469-2472.

[11] 叶志飞，文益民，吕宝粮. 不平衡分类问题研究综述[J]. 智能系统学报，2009，4(2)： 148-156.

[12] Zhongqing Wang，Shoushan Li，Guodong Zhou. Imbalanced Sentiment Classification with Multi-Strategy Ensemble Learning[C]//Proceedings of the International Conference on Asian Language Processing，Penang，Malaysia，2011： 131-134.

[13] 钱洪波，贺广南. 非平衡类数据分类概述[J]. 计算机工程与科学，2010，32(5)： 85-88.

[14] Leo Breiman. Bagging Predictors[J], Machine Learning，1996a，24： 123-140.

[15] Franz Josef Och. Minimum Error Rate Training in Statistical Machine Translation[C]//Proceedings of the 41rd Annual Meeting of the Association for Computational Linguistics，Sapporo，Japan，2003： 160-167.

[16] 张仰森，郭江. 动态自适应加权的多分类器融合词义消歧模型[J]. 中文信息学报，2012，26(1)： 3-8.

[17] Franz Josef Och，Hermann Ney. Discriminative training and maximum entropy models for statistical machine translation[C]//Proceedings of the 40th Annual Meeting of the Association forComputational Linguistics，Philadelphia，2002： 295-302.

[18] Franz Josef Och，Hermann Ney.Improved statisticalalignment models[C]//Proceedings of the 38th Annual Meeting of the Association for Computational Linguistics，Hong Kong，2000： 440-447.

[19] Kishore Papineni，SalimRoukos，Todd Ward. BLEU: a Method for Automatic Evaluation of Machine Translation[C]//Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics，Philadelphia，2002： 311-318.

[20] Ying Zhang，Stephan Vogel，Alex Waibel. Interpreting BLEU/NIST Scores: How Much Improvement Do We Need to Havea Better System?[C]//Proceedings of The International Conference on Language Resources and Evaluation，Lisbon，Portugal，2004： 2051-2054.