基于对偶分解的词语对齐搜索算法

沈世奇,刘洋,孙茂松(智能技术与系统国家重点实验室;清华信息科学与技术国家实验室;清华大学计算机系,北京100084)摘要:词语对齐旨在计算平行文本中词语之间的对应关系,对机器翻译、双语词典构造等多项自然语言处理任务都具有重要的影响.
虽然近年来词语对齐在建模和训练算法方面取得了显著的进展,但搜索算法往往都采用简单的贪心策略,面临着搜索错误较大的问题.
本文提出了一种基于对偶分解的词语对齐搜索算法,将复杂问题分解为两个相对简单的子问题,迭代求解直至收敛于最优解.
由于对偶分解能够保证求解的收敛性和最优性,本文提出的搜索算法在2005年度863计划词语对齐评测数据集上显著超过GIZA++和判别式词语对齐系统,对齐错误率分别降低4.
2%和1.
1%.
关键词:词语对齐;判别式模型;搜索算法;对偶分解SearchforDiscriminativeWordAlignmentviaDualDecompositionShiqiShen,YangLiuandMaosongSun(DepartmentofComputerScienceandTechnology,StateKeyLabonIntelligentTechnologyandSystems,TsinghuaUniversity,Beijing100084,China)Abstract:Wordalignmentaimstocalculatethecorrespondingrelationshipbetweenthewordsinparalleltexts.
Ithasimportantinfluenceonmachinetranslation,bilingualdictionaryconstructionandmanyothernaturallanguageprocessingtasks.
Althoughinrecentyearsthewordalignmenthasmadesignificantprogressinmodelingandtrainingalgorithm,itssearchalgorithmoftenusessimplygreedystrategiesandfacestheproblemoflargesearcherrors.
Thispaperproposedawordalignmentsearchalgorithmbasedondualdecomposition,makingacomplexproblemintotworelativelysimplesub-problemsanditerativelysolvingituntilconvergencetotheoptimalsolution.
Forthedualdecompositioncanensuretheconvergenceandoptimalityofsolutions,thisalgorithmsignificantlyexceedsGUZA++anddiscriminantwordalignmentsystemonalignmenterrorrateswhentestingonthe863Projectswordalignmentevaluationdatasetof2005.
Alignmenterrorrateisdecreasedby4.
2%and1.
1%respectively.
Keywords:wordalignment;discriminativemodel;SearchAlgorithm;dualdecomposition1引言词语对齐旨在计算平行文本中词语之间的对应关系.
例如,给定一个中文句子和一个英文句子1中国建筑业对外开放呈现新格局.
TheOpeningofChina'sconstructionindustrytotheoutsidepresentsanewstructure.
收稿日期:定稿日期:基金项目:863计划项目(批准号:2012AA011102和2011AA01A207);媒体与网络技术教育部-微软重点实验室项目(编号20123000007)作者简介:沈世奇(1990—),男,博士生,主要研究方向为统计机器翻译;刘洋(1979—),男,副研究员,主要研究方向为机器翻译、自然语言处理;孙茂松(1962—),男,教授,主要研究方向为自然语言处理.
1该例句及词语对齐源自(Liuetal.
,2010)图1:词语对齐示例图1给出了这两个句子的词语对齐.
由于中文词"中国"与英文词"China"互相翻译,两者之间存在一条连线显示对应关系.
需要指出的是,中文词与英文词并不完全是一一对应,如中文词"建筑业"对应两个英文词"constructionindustry".
更复杂的情况是一个中文词对应到若干个非连续的英文词,如"对外开放"对应英文词"opening.
.
.
totheoutside".
因此,由于自然语言的多样性和复杂性,发现不同语言之间的词语对应关系是一个非常具有挑战性的问题.
词语对齐最早是作为机器翻译的中间结果由[2]Brownetal.
(1993)提出.
由于词语对齐能够为不同自然语言在词语层建立关联,它在机器翻译、机器辅助翻译、词义消歧和双语词典构建等多项自然语言处理任务中起着关键的作用.
例如,在统计机器翻译中,无论是基于短语的方法[8](Koehnetal.
,2003)、基于层次短语的方法[4](Chiang,2007)还是基于句法的方法[7](Galleyetal.
,2006),往往都依赖于词语对齐进行规则抽取,因而词语对齐的质量对机器翻译译文的质量具有重要的影响.
词语对齐模型大致可分为生成式模型和判别式模型两大类.
生成式模型([2]Brownetal.
,1993;[22]Vogeletal.
,1996;[11]Liangetal.
,2006)为词语对齐设计生成故事(generativestory(,其优点在于不需要标注数据进行训练,很容易应用于各个领域,其缺点在于模型难以扩展.

判别式模型([12]Liuetal.
,2005;[15]Moore,2005;[1]BlunsomandCohn,2006;[13]Liuetal.
,2010)将各种知识源作为特征函数加入到模型中,易于扩展,其主要缺点在于依赖于标注数据.
在训练算法方面,生成式模型主要使用EM算法[2](Brownetal.
,1993)实现无监督学习,而判别式模型可以使用最小错误率训练算法[17](Och,2003)实现直接优化评价指标,大幅提高对齐质量.
[6]Dyeretal.
(2011)最近提出了判别式模型的无监督训练,实现了判别式模型与无监督学习的优势互补.
然而,尽管词语对齐在建模和训练算法方面取得了较大的进展,多数搜索算法仍然面临着搜索错误严重的问题.
给定一个源语言句子和一个目标语言句子,可能的词语对齐结果数量是.
对于以IBM模型[2](Brownetal.
,1993)为代表的生成模型而言,虽然简单的模型1和模型2可以精准计算Viterbi对齐,但是对于更复杂的模型3、4、5只能使用爬山法计算近似解([2]Brownetal.
,1993;[16]OchandNey,2003).
对于以线性模型[13](Liuetal.
,2010)为代表的判别式模型而言,往往也只能使用柱搜索算法来计算近似解.

图2:词语对齐的搜索空间,此图源自[13](Liuetal.
,2010).
对于长度分别为J和I的平行句对,可能的词语对齐数量是图2给出了[13]Liuetal.
(2010)所提出的柱搜索算法的搜索空间,该算法以空对齐为起点,不断添加连线直至模型分数无法增加为止.
由于词语对齐中连线之间存在错综复杂的依赖关系,无论是爬山法还是柱搜索算法都面临着严重的搜索错误问题.
最近,[19]RiesaandMarcu(2010)将立方体剪枝[4](Chiang,2007)引入词语对齐,但本质上仍然只能计算近似解.
因此,搜索算法已经成为制约词语对齐质量的瓶颈问题.
近年来,对偶分解(dualdecomposition)被广泛应用于句法分析[10](Kooetal.
,2010)和机器翻译[3](ChangandCollins,2011)等自然语言处理任务来实现精准求解(exactdecoding),均取得了良好的效果.
为了缓解词语对齐所面临的搜索错误问题,本文提出一种基于对偶分解的词语对齐搜索算法,其基本思想是将复杂的问题分解为两个相对简单的子问题,迭代求解直至收敛.
由于对偶分解能够确保求解的收敛性和最优性[20](RushandCollins,2011),我们的方法在2005年度863计划词语对齐评测数据集上显著超过IBM模型的爬山法[2](Brownetal.
,1993)与判别式模型的柱搜索算法[13](Liuetal.
,2010),对齐错误率分别降低4.
4%和1.
1%.
2基于对偶分解的词语对齐搜索算法对偶分解的基本思想是将一个复杂的问题分解为两个相对简单的子问题,之后对两个子问题进行分别求解,通过一个数据结构记录两者的差异之处并利用该数据结构试图使两个子问题的解趋于一致.
当算法经过多轮迭代收敛(即两个子问题得出相同的解)时,该解为最优解.
图3给出了基于对偶分解的词语对齐搜索算法的一个示例.
给定中文句子"呈现新格局.
"和英文句子"presentanewstructure.
",假设我们将一个词语对齐模型拆成两个子模型进行分别求解,并定义函数来记录两个子模型的解的差异之处.
初始状态对于任意的和,均设为0.
图3(a)显示了两个子问题的解,上面是子问题一的解,下面是子问题二的解.
可以发现,两个解存在差异:子问题一的连线与子问题二的连线不一致,即子问题一将"新"与"a"连线而子问题二将"呈现"与"a"相连.
因此,算法更新函数,将设为-1,将设为1,试图使两个子问题的解趋向一致(如图3(b)所示).
再次进行求解,两个子问题的解达成一致,获得最终解(如图3(c)所示).
这也说明了对偶分解的方法得到的解3(c)能够优于子问题的解3(a)的原因.
图3:基于对偶分解的词语对齐算法示例.
对偶分解将一个复杂问题分解为两个子问题,分别求解并使用惩罚函数记录两个解的差异之处,使得两个子问题的解趋近一致,最终收敛于最优解.
更形式化地,给定源语言句子和目标语言句子,基于对偶分解的词语对齐的搜索算法的目标是⑴同时满足对任意⑵其中,和分别是两个词语对齐的解集合,和分别是其中的一个解,对应子问题一的模型,对应子问题二的模型,表示子问题一将与连在一起,则表示没有相连.
因此,对偶分解的目标是计算两个子问题达成一致的最优解.

对偶分解将按照子问题一和子问题二进行分别求解.
子问题一的优化目标是⑶子问题二的优化目标是⑷图4给出了基于对偶分解的词语对齐搜索算法.
算法的输入是源语言句子和目标语言句子(第1行).
首先初始化惩罚函数,全部设为(第2行).
之后进入迭代求解(第3行),分别对子问题一(第4行)和子问题二(第5行)进行求解.
如果满足收敛条件,即两个子问题生成完全相同的对齐,则返回最优解(第6至7行),否则更新惩罚函数(第9行)进入下一轮迭代.
如若超过最大迭代次数仍然没有收敛,则选取迭代过程中子问题的最优解作为最后的结果.
其中,是第轮迭代的更新比率,用来控制算法收敛的速度.
[21]RushandCollins(2012)明当满足以下条件时图4:基于对偶分解的词语对齐搜索算法.
⑸并且⑹对偶分解算法能确保评价函数收敛.
3实验本文的训练集是中英24万句对的政府新闻类双语语料库,开发集和测试集是2005年度863计划词语对齐评测数据集,开发集包含502句对,测试集包含505句对.
我们所使用的评价指标是由[16]OchandNey(2003)的对齐错误率(AlignmentErrorRate,简称AER),对齐错误率越低表示对齐质量越高.
我们与以下两个系统进行对比:1.
GIZA++:IBM模型[2](Brownetal.
,1993),采用EM算法进行参数训练,爬山法进行搜索,由[16]OchandNey(2003)实现.
2.
Vigne:[13]Liuetal.
(2010)提出的判别式词语对齐方法,采用最小错误率训练算法[17](Och,2003)进行参数训练,柱搜索算法进行搜索.
我们首先使用GIZA++的默认设置进行双向训练,得到中英和英中两个方向的IBM模型4的对齐结果以及模型参数.
Vigne主要采用GIZA++输出的IBM模型参数作为主要特征,具体为[13](Liuetal.
2010)提出的9个特征,利用最小错误率训练(Och,2003)在开发集上优化特征权重,在测试集上采用柱搜索算法获得最优对齐结果.
我们的词语对齐系统在建模和训练算法上与Vigne完全一致,只是在搜索算法上采用对偶分解法.
表1:GIZA++、Vigne与我们的方法的对比结果.
对齐错误率AER越低表示对齐质量越高.
我们采用了[9]Koehn(2004)提出的显著性检验方法验证我们的系统与GIZA++和Vigne的差别在统计上是显著的(p=0.
05).
0.
10.
010.
001收敛率0.
96440.
96630.
60400.
90690.
7525总体AER0.
19950.
19930.
20480.
20220.
2036表2:迭代更新比率对结果的影响3.
1与传统搜索算法的对比表1给出了我们的系统与GIZA++和Vigne的对比结果.
GIZA++产生四种对齐结果:1.
中英:以中文为源语言,英文为目标语言,使用IBM模型4;2.
英中:以英文为源语言,中文为目标语言,使用IBM模型4;3.
交集:两个方向对齐结果的交集;4.
并集:两个方向对齐结果的并集.
其中,GIZA++的交集取得了四种设置中最好的结果23.
9.
判别式词语对齐系统Vigne取得的对齐错误率是20.
8,显著超过了GIZA++.
而我们的对偶分解算法取得了最好的对齐错误率19.
7,超过GIZA++4.
4个百分点,Vigne1.
1个百分点.
我们采用了[9]Koehn(2004)提出的显著性检验方法验证上述差别在统计上是显著的(p=0.
05),从而验证了对偶分解算法确实有效减少了搜索错误.
在搜索效率上,GIZA++作为一个无监督的方法,需要对较大的数据进行整体的处理,并不能对单句进行词对齐,与Vigne和我们的方法很难比较.
而我们使用的对偶分解采用的是迭代的方法,每一轮迭代都需要对两个子问题分别搜索,所以在时间上要慢于Vigne,时间复杂度随着迭代次数的增长而增长.
3.
2迭代更新比率对收敛率和对齐错误率的影响系统模型训练搜索设置AERGIZA++IBM模型4EM爬山法中英24.
4英中25.
3交集23.
9并集29.
1Vigne线性判别式模型最小错误率训练柱搜索20.
8我们的工作线性判别式模型最小错误率训练对偶分解19.
7[21]RushandCollins(2012)指出迭代更新比率将对对偶分解的迭代是否收敛产生重要影响.
因此,我们通过实验研究迭代更新比率对收敛率的影响.
所谓收敛率,是指待对齐文本中达到收敛的句子比例.
例如,如果对偶分解算法在100个句子中的90个句子达到收敛,则收敛率为90%.
我们设定最大迭代次数K为100,当迭代超过100次后我们认为该句子在本方法下不收敛.
表2给出了不同的迭代更新比率及相应的收敛率和对齐错误率.

其中,k为迭代次数,t是一个整数,其值为在迭代过程中对偶分解的评价函数增长的次数.
由于和满足公式(5)和(6),它们对应的收敛率均超过96%并取得较低的AER.
与之相反,常数型的更新比率(如0.
1、0.
01和0.
001)则对应较低的收敛率和较高的AER.
因此,更新比率对于收敛率和AER具有重要的影响2.
3.
3句子长度对收敛率的影响图5:句子长度对收敛率的影响.
横坐标是句子长度,纵坐标是收敛率.
对于词语对齐问题来说,句子的长度直接影响了算法的复杂性.
直观来看,句子越短,词语对齐所需要的搜索空间越小.
反之,句子越长,搜索空间越大.
我们设置不同的迭代收敛比率,观察对偶分解算法在不同长度的句子上的收敛率.
图5给出了在、总收敛率为0.
6040的条件下,句子的收敛比率岁句子长度变化的关系图.
可以看出,对偶分解算法的收敛率随着句子长度的增长大致是呈现下降趋势.
也就是说,由于句子长度的增长而增大的搜索空间会使得算法收敛率下降.
3.
4收敛与不收敛数据集上对偶分解与柱搜索的比较表3给出了收敛数据集和不收敛数据集上对偶分解算法与柱搜索算法的比较情况.