短语统计机器翻译的句法调序模型.doc

第1期薛永增等：短语统计机器翻译的句法调序模型15短语统计机器翻译的句法调序模型薛永增，李生，赵铁军，杨沐昀(哈尔滨工业大学 语言语音教育部-微软重点实验室, 黑龙江 哈尔滨 150001）照片尺寸为20mm*30mm；最好不用红色背景摘 要：为了处理统计机器翻译中的长距离调序，在基于短语的统计翻译模型的基础上提出了句法调序模型。该模型按照短语切分来分割句法树结构，从而能够避免短语和句法结构的不一致性。在该模型中依据短语对齐和短语内词对齐确定句法树部分结构的调序顺序，依据各个节点上的调序概率计算子结构的调序概率，作为对数线性模型的特征函数。该模型的实验结果比经典的短语统计翻译模型的BLEU评分有明显提高。结果表明句法调序模型对于基于短语的统计机器翻译是有效的，能够较好地将句法知识和短语翻译过程结合起来。关键词：人工智能；统计翻译模型；句法调序；短语中图分类号：TP391.2 文献标识码：A 文章编号：1000-436X(2008)01-0007-08Syntax-based reordering model for phrasal statistical machine translationXUE Yong-zeng, LI Sheng, ZHAO Tie-jun, YANG Mu-yun(MOE-MS Key Laboratory of Natural Language Processing and Speech, Harbin Institute of Technology, Harbin 150001, China)Abstract: To deal with the long-distance reordering, a linguistically syntax-based reordering model was presented for phrasal statistical machine translation. In this model, the syntax structure was decomposed according to the phrase segmentation to avoid the inconsistence between phrase and syntax. The reordering sequence of the sub-structures of a parse tree was decided by the word and phrase alignments. The reordering probability of the sub-structure was calculated on the reordering probabilities of the inside nodes, which was defined as a feature function of the log-linear statistical translation model. Experimental results show that the BLEU scores of the translation results were significantly improved compared with a conventional statistical phrase-based model. Therefore, it is effective to introduce the linguistic syntax for phrase reordering. The presented reordering model is able to efficiently incorporate the syntax into the translation process of phrases. Key words: artificial intelligence; statistical translation model; syntax-based reordering; phrase1 引言收稿日期：2007-04-13；修回日期：2007-10-20基金项目：国家高技术研究发展计划（“863”计划）基金资助项目(2006AA010108, 2006AA01Z150)Foundation Item: The National High Technology Research and Development Program of China(863 Program) (2006AA010108, 2006AA01Z150)近年来，基于短语和句法的统计翻译模型成为了国内外机器翻译领域的研究热点之一13。调序是其中的一个关键问题。由于机器翻译中不受限调序是一个NP难题4,5，而n元文法语言模型又不足以解决翻译中的调序问题6，因此在统计机器翻译中引入单独的调序模型是必要的。目前短语统计机器翻译中的调序模型可以分为两大类：一类是非层次化的短语调序模型，包括不利用词汇信息的简单移位模型和扁平(flat)调序模型79，以及各种词汇化的短语调序模型1012；另一类是层次化的短语调序模型5,1316，这类模型基于树状的句法层次结构，逐层进行调序。由于句法层次结构能够涵盖从大到小不同范围的短语，因此句法层次结构的引入有助于解决统计机器翻译中长距离调序难题。句法层次结构可以分成两类：一类是语言学的句法结构，这类句法结构符合语言学家预先定义的语法规范，例如句法分析树就属于这一类句法结构；另一类是非语言学的句法结构，这类句法结构并不遵从语言学的语法规范，通常按照翻译上的需要自动构建出来，例如反向转换文法就属于这一类句法结构。基于句法结构的短语调序方法可以分为两类：一类是将短语的调序直接固定在模板上1316，另一类则是通过建立短语和短语之间的调序模型实现调序5。在前一类模型中，语言学和非语言学的句法模型都取得了成功，而在后一类模型中，目前主要是采用非语言学的句法结构，而较少引入语言学的句法树结构特别是源语言句法树来构建调序模型。引入语言学的句法结构的困难是很多情况下按照双语互译关系抽取的短语和句法树结构并不一致，因此难以将短语调序关系和句法树各个层次上的调序关系结合起来。短语和句法树结构的不一致主要在于2点：一是边界不一致，即抽取出来的短语边界并不是某一个层次上句法树结构的边界，而是跨越了句法树结构的边界或者未能达到句法树结构边界；二是层次不一致，也就是句法树不同层次上的短语的译文互有交叉(crossing)。图1给出了不一致的一个例子。在这个例子中，短语互译对“呢 ？?”就和汉语的句法树结构边界不一致，短语互译对“你 怎么how do you”和句法树结构之间也存在边界不一致，同时，“你”的译文和VP节点“怎么 吃”的译文又有交叉，因此还存在层次不一致。正是由于上述不一致性的存在，采用基于一致性假设的树-串统计翻译模型概率作特征时并没有明显的性能提升17。原因在于文献17完全采用树-串统计翻译模型来重新刻画双语句子的对齐关系，而不是仅仅将问题局限在调序上，这样为了满足一致性假设，对于交叉的现象就会采用错误的对齐方式来刻画，从而影响翻译概率，因此效果不明显。图1 短语和句法树结构的不一致性消除不一致性可以采用2种方法：依照句法结构来抽取短语互译对，或者按照短语互译对的需要重新构造一种基于句法的结构。已有研究表明前一种方法由于短语互译对的抽取受到限制，其翻译性能反而有一定程度的下降7。因此本文采用后一种思路，即按照翻译过程中短语的切分来刻画句法树上的调序关系，也就是依据短语的切分方式来考察句法树相应部分的调序。本文提出了一种基于语言学句法结构的短语统计翻译调序模型，该模型依照短语切分方式来考察句法树相应部分的调序关系，将短语调序关系和句法树各个层次上节点的调序结合起来，从而能够克服短语和句法树结构不一致带来的困难。通过词对齐确定节点调序，然后计算短语对应的句法结构的调序概率，并将调序概率作为对数线性模型中的一个特征，从而将句法特征融入短语翻译模型中。实验结果表明采用本文方法能够明显提高译文的BLEU评分，说明句法的引入能够比较有效地处理调序问题。本文组织如下：首先介绍模型基本框架以及相关定义，然后是模型参数训练过程，最后给出实验结果和结束语。2 句法调序模型2.1 基本概念句法分析树是一个图结构T=(V,E)，其中，V是句法分析树上的所有节点的集合，E是句法分析树的边的集合。边可以表示为序偶(v,w)，其中v,w是句法树上的节点，且v是w的父节点。为了能够得到和短语一致的句法结构，需要将句法树进一步分解。本文中将句法树分解为一种伪句法结构，定义如下：定义1（伪句法结构）句法分析树的一个子集=(V,E)称为伪句法结构，当且仅当满足如下条件：1) ，；2) ，若，则；3) 若且，则；4) 若，则其父节点。图2给出了将句法树分解为伪句法结构的一个示例。用类似句法树的表示方法来表示伪句法结构，不同的是引入标记X来表示伪句法结构相对于完整句法结构缺少的部分。例如图2中的4个伪句法结构可以分别表示为： TOPr 这个 X； TOPX r 你 VPr 怎么 X X； TOPX VPX vg 吃 X； TOPX y 呢 wj ？。图2 句法分析树分解为伪句法结构示例从伪句法结构的定义可知，整个句法分析树也是一个伪句法结构。定义2 （连续性）如果对于伪句法结构=(V, E) 的任何一个节点v的所有子节点w1,wt，都不存在这样一个子节点wi(1it)，满足，并且(1ji1, i+1kt)，使得，则称该伪句法结构是连续的，否则是间断的。连续伪句法结构的叶节点对应单词组成的词序列是连续短语，间断伪句法结构叶节点对应单词组成的词序列(包括标记X)是类似文献13那样的层次短语模板。这样，短语和伪句法结构间就可以建立一一对应关系，任何一个伪句法结构都有相对应的短语，任何一个短语都有相对应的伪句法结构。定义3 （划分）伪句法结构形成的集族D=, (,1iK)称为句法树T=(V, E)的一个划分，当且仅当下列条件成立：1) ，；2) 设(1iK)为叶节点集合，则(1iK, 1jK)，有。图2中的4个伪句法结构即构成了句法树的一个划分。划分给出了句法树分解为多个伪句法结构的一种分解方式。在本文中，限定一个划分仅包含连续的伪句法结构。2个伪句法结构=(V1,E1)和=(V2,E2)可以合并为伪句法结构=(V,E)，其中， 。反之，如果一个伪句法结构含有2个以上的叶节点，也可以进一步分解为多个伪句法结构。2.2 模型定义设源语言的句法树为T1m=T1Tm，目标语言句子为e1n=e1en，引入隐变量D来表示将句法树分解为伪句法结构的划分，假设所有的划分都有相同的概率，则翻译模型为(1)其中，是源语言的伪句法结构序列，是目标语言的短语序列。对于采用线性对数模型来计算，即(2)本文中定义4类特征函数：翻译模型概率特征、语言模型概率特征、调序模型概率特征和罚分。翻译模型概率即是伪句法结构对应的源语言短语翻译为目标语言短语的翻译概率，包括短语翻译概率、反向短语翻译概率、词汇翻译概率、反向词汇翻译概率4种翻译概率特征；语言模型为三元文法模型；罚分包括句长罚分和短语长度罚分，这些特征函数的定义和文献7中的定义相同，在此不赘述。调序概率特征包括全局短语调序概率特征和局部短语调序概率特征。设源语言伪句法结构的调序概率分别为p1, p2, pK，全局短语调序概率特征函数定义为(3)局部短语调序概率特征函数定义为(4)其中，是对应于目标语句子中第i个短语的源语言伪句法结构的第一个叶节点的位置，是对应于目标语句子中第i1个短语的源语言伪句法结构的最后一个叶节点的位置，是一个预先定义的常数。3 调序概率的计算3.1 节点调序概率首先，对于子节点数不大于1的节点，其调序概率恒为1。其余节点的调序可以分成2种情况：一种是所有子节点都重新排序，称为完全调序，另一种是一部分子节点重新排序，另一部分子节点顺序未定，称为部分调序，相应的概率分别称为完全调序概率和部分调序概率。当一个节点的所有子节点都在伪句法结构中时，就可以推算完全调序概率，而当只有一部分子节点在伪句法结构中时，由当前的伪句法结构就只能推算部分调序概率。例如图1中伪句法结构“TOPr这个 r你VPr怎么 vg吃X”的节点VP的调序为r-vg是完全调序，而节点TOP的调序为r-VP-r就是部分调序。完全调序概率的计算较为简单，可以在词对齐的基础上采用相对频率进行估计。设节点的子节点总数为t，调序后子节点顺序为=,，则完全调序概率计算如下(5)其中，是节点的调序特征，P是所有节点全排列组成的集合，N()表示相应调序在训练集中出现的次数。部分调序概率也就是一部分子节点的顺序已确定，而其他子节点的顺序未确定时的概率，可以通过完全调序概率来计算。设部分调序涉及的子节点数为k，新的子节点顺序为,，则部分调序概率计算如下：(6)其中，P是节点集合,中所有节点全排列组成的集合。显然，有= 成立。节点的调序概率是在模型训练过程中计算的，如果节点的子节点数为t，则需要计算t!个完全调序概率和个部分调序概率（表示t中任取i个的排列数），当t很大时显然计算量过大。本文中，仅仅计算t4的情况，对于其余情况则所有完全调序概率假设为均匀分布，即1/ t!，相应的k个子节点的部分调序概率为。3.2 伪句法结构调序概率设伪句法结构中节点的调序概率分别为p1, p2,pn，则伪句法结构的全局短语调序概率可以表示为(7)如果节点的所有子节点都在中，则pi是完全调序概率，如果只有k个子节点在中，则pi是这k个子节点的部分调序概率。当2个伪句法结构=(V1,E1)和=(V2,E2)合并为另一个伪句法结构=(V,E)时，并不需要重新计算所有节点的调序概率，而只需重新计算合并后调序发生变化的节点的概率增益，也就是集合中的节点的概率增益：(8)其中，是节点在伪句法结构中的调序概率，和分别是在和中的调序概率。因为调序是同一节点下不同子节点顺序的重新排列，相对于和节点交集中的节点，合并后的结构可能包含更多的子节点，从而调序概率需要重新计算，而对于其他节点则不会有调序顺序变化，因此不必再算。伪句法结构的全局短语调序概率计算如下：(9)此时全局短语调序特征为(10)节点的调序特征可以有多种选择方式，本文中分别考察以下几组特征：1) 标号特征：即子节点短语/词性标号序列，相应的全局短语调序概率记为；2) 词汇特征：即子节点中心词序列（中心词的确定方法类似于文献18），相应的全局短语调序概率记为；3) 词汇/标号混合特征：即将子节点的中心词和标号合在一起作为特征序列，相应的全局短语调序概率记为。4 模型训练通过上面的一系列过程，伪句法结构的翻译可以分为伪句法结构各个节点的调序和相应短语的翻译2个独立的部分。模型训练主要包括：节点完全调序概率的估计、短语互译对的抽取和相应翻译概率的估计，这些估计都是在词对齐的基础上进行的，其结果即构成相应的特征函数。特征函数的权重采用最小错误率训练(MERT, minimum error rate training)进行调整。2个句子间的词对齐可以看成是一组对齐点(i,j)组成的集合，其中i，j分别是源语言和目标语言句子中相对应的词的位置。本文中采用IBM模型4分别从源语言到目标语言和目标语言到源语言2个方向上进行词对齐，按照不同参数训练的需要选择不同的方式将2个方向上的对齐进行重新组合。4.1 节点完全调序概率的估计估计节点完全调序概率的关键是基于训练语料上的词对齐结果确定子节点的调序顺序。为了便于处理，首先将2个方向上的词对齐重新组合为一对一的词对齐，本文中考虑了如下2种方法：1) intersect，即取2个对齐的交集作为新的对齐；2) diag-and，在2个对齐交集的基础上，进一步考察2个对齐并集中的对齐点(i,j)，如果交集中包含邻接对角对齐点(i1, j1)、(i1, j+1)、(i+1, j1)、(i+1,j+1)并且交集中不含有其他对齐点(i,j)或者(i,j)，则将(i,j)加入到新的对齐中。在一对一词对齐的基础上采用下面的算法确定节点的调序顺序：算法1 调序顺序获取算法输入：源语言句法树T，一对一对齐A；输出：节点及其调序顺序集合R=(,)；Step1 后根遍历句法树T，对每一个节点。Step2 标记的译文在目标语言中的位置j：若为叶节点且在A中有对齐点(i,ai)，则j=ai；若为叶节点但在A中无对齐点，设的先导节点在A中的对齐点为(i,ai)，则令j=ai+，(01)；若为非叶节点，设子节点中核心节点位置为ai，则j=ai。Step3 将的子节点按照目标语言中的位置从小到大重新排列，得到。Step4 。Step5 输出R。确定节点的调序顺序后，即可按照式(5)得出完全调序概率，进而通过式(6)计算部分调序概率。4.2 短语互译对抽取与打分本文的短语抽取方法和文献7类似，即在词对齐的基础上抽取与词对齐相一致的短语互译对。不同的是本文中短语和词对齐的一致性约束定义为短语对中任何词在没有和短语对内的词对齐的情况下都不能与短语对之外的词对齐，并且短语对中存在已对齐的词。图3给出了本文定义下一致和不一致的例子。图3 短语对与词对齐的一致和不一致就本文和文献72种抽取方式来看，文献7的抽取方式更为严格，但是其短语抽取方法也容易受到词对齐错误的影响；而本文中的抽取方法则能够在一定程度上避免这一影响，同时由于能够抽取到较短的短语互译对，对于短语调序是有益的。短语打分仍然采用文献7中的方法。为了在解码过程中确定调序顺序，需要在抽取出来的短语互译对中标出词对齐。对于抽取出来的每一个短语互译对，采用IBM模型1在源语言到目标语言和目标语言到源语言两个方向上进行词对齐，然后分别采用与句子词对齐重组相同的方法（intersect或diag-and）得到最终的词对齐结果。图4给出了图1中各个短语互译对内的词对齐结果示例。图4 短语互译对内的词对齐5 系统实现与实验结果5.1 解码翻译过程：根据抽取到的短语互译对中的源语言短语对输入句子进行划分。首先，随机选择一个伪句法结构，给出该伪句法结构对应短语的译文作为译文句子中的第一个短语，并计算相应的得分；然后从剩下的伪句法结构中再随机选取一个伪句法结构，给出对应的短语译文作为译文句子中的后继短语，并计算该伪句法结构和前一个伪句法结构合并后的相应得分；重复上述过程直到整个句法树的伪句法结构都翻译出来为止。其中，节点调序顺序通过短语互译对内的词对齐来确定。解码算法采用类似文献19的基于多栈的集束搜索策略。以输入句子中被覆盖的词数来区分各栈。对每一个栈采用合并相同假设、阈值剪枝和直方图剪枝的剪枝策略。5.2 实验结果实验采用IWSLT2004数据集合，其中训练集为2万汉英双语句对，开发集为506句汉语句子，测试集为500句汉语句子，开发集和测试集每句对应16个参考译文。汉语句法分析采用基于中心词驱动模型的两级汉语句法分析方法18，在句法分析过程中，对语料重新进行了分词，并按照句法分析的需要对部分汉语和英语词进行了合并。语言模型采用3元文法模型。对译文进行了后处理，去掉了除“”以外的所有标点，并且合并了类似“I ll”的缩略情况。采用Pharaoh系统19作为对比，最终翻译结果采用BLEU自动评价方法20评价。首先，考察了不同的调序特征对翻译结果的影响。分别采用标号特征、词汇特征和词汇/标号混合特征，以及同时采用标号、词汇2组特征作为调序特征，应用diag-and方法来生成一对一的词对齐进行训练和解码，并与Pharaoh系统进行比较，实验结果如表1所示。可以看出，引入句法调序模型后BLEU评分比Pharaoh系统有所提高。其中采用词汇特征翻译结果明显好于其他翻译结果。采用词汇/标号混合特征由于在一定程度上受到数据稀疏的影响，结果最低。同时采用2组特征后翻译结果对比于仅采用标号特征略有提高，但是仍然低于仅采用词汇特征的结果。这表明词汇化特征的引入在很大程度上加强了调序模型的区分度。而标号特征的影响相对较小，和词汇特征同时作用时甚至造成了负面影响。表1 应用不同调序特征时的翻译结果评价(BLEU)调序特征翻译结果评价Pharaoh0.4025标号特征0.4252词汇特征0.4422混合特征0.4236标号+词汇特征0.4259下面考察词对齐重组方式对最终翻译结果的影响。分别用intersect和diag-and方法来生成一对一的词对齐，用于确定调序顺序，然后采用词汇作为句法调序特征进行调序，实验结果如表2所示。两种重组方式中diag-and方法好于intersect方法。这是由于前者能够得到更多的对齐点，说明对齐点的覆盖率比精确率更有利于对调序的估计。表2 应用不同词对齐重组方式时的翻译结果评价(BLEU)对齐重组方式翻译结果评价intersect0.4266diag-and0.4422为了进一步考察句法调序模型的有效性，分析了引入句法调序模型前后的翻译结果在调序上的变化情况。在此将每一句的调序结果分成3种情形：正确、错误和不确定，结果如表3所示。表3引入句法前后调序结果对比系统调序结果正确不确定错误引入句法调序前30552143引入句法调序后3386498可以看出，采用句法调序模型后调序错误有所降低，这进一步说明语言学句法信息有助于全局调序。表4给出了句法调序前后对比的一个实例。可以看出，在引入句法结构之前，局部调序仅仅将短语“在这里”和“画一下”交换了顺序，而没有考虑到“地图”和“画一下”这2个句子成分间的依赖关系，造成了翻译错误；引入句法结构之后，调序时能够正确处理节点PP和同层的节点VO及其子节点BVP和ng 地图间的顺序关系，翻译结果基本正确。这说明句法结构有助于确定句子中各个成分的相互顺序关系，避免局部调序造成的顺序混乱。表4句法调序对比实例类别实例原文请在这里画一下地图句法结构TOPVOvg 请 VOPPp 在 r 这里 VOBVPvg 画 m 一下 ng 地图 wj 。调序前译文please draw me on this map调序后译文please draw a map here please参考译文please draw a map here6 结束语本文提出了基于句法的短语统计翻译调序模型。在句法分析树的基础上定义了伪句法结构，并通过伪句法结构建立了调序模型。伪句法结构能够和源语言句子的任意短语切分方式相对应，因此短语抽取不受句法结构约束，并且该模型对于翻译过程中的短语交叉现象不敏感，能够较好地和翻译过程相结合。通过句法调序模型，显著提高了翻译质量，表明引入语言学句法结构对于统计机器翻译调序是有效的。应该看到采用子节点全排列的调序方法受数据稀疏影响仍然较大，特别是对于子节点数过多的情况仍然难以有效处理。在今后工作中，我们拟采用引入大规模训练数据，引入子节点间的跳转概率的方法加以解决。参考文献:1刘群. 统计机器翻译综述J. 中文信息学报. 2003，17(4): 1-12.LIU Q. Survey on statistical machine translationJ. Journal of Chinese Information Processing, 2003, 17(4): 1-12.2KNIGHT K, MARCU D. Machine translation in the year 2004A. Proceedings of the 2005 IEEE. International Conference on Acoustics, Speech, and Signal Processing (ICASSP)C. Philadelphia, PA, USA, 2005.965-968.3徐波, 史晓东, 刘群等. 2005统计机器翻译研讨班研究报告J. 中文信息学报, 2006 ,20(5): 1-9.XU B, SHI X D, LIU Q, et al. Current statistical machine translation research in China(2005)J. Journal of Chinese Information Processing, 2006, 20(5): 1-9.4KNIGHT K. Decoding complexity in word-replacement translation modelsJ. Computational Linguistics, 1999, 25(4): 607-615.5XIONG D, LIU Q, LIN S. Maximum entropy based phrase reordering model for statistical machine translationA. Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational LinguisticsC.Sydney, Australia, 2006.521-528.6AL-ONAIZAN Y, PAPINENI K. Distortion models for statistical machine translationA. Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational LinguisticsC. Sydney, Australia, 2006. 529-536.7KOEHN P, OCH F, MARCU D. Statistical phrase-based translationA. Proceedings of the Conference on Human Language Technology C. Edmonton, Canada, 2003. 127-133.8KUMAR S, BYRNE W. Local phrase reordering models for statistical machine translationA. Proceedings of the Human Language Technology Conference on Empirical Methods in Natural Language ProcessingC. Vancouver, Canada, 2005. 161-168.9CHENG W, ZHAO J, LIU F, et al. The co-chunk processing method for Chinese-English spoken-language translationJ. Journal of Chinese Language and Computing, 2004, 14(1): 31-40.10TILLMAN C. A unigram orientation model for statistical machine translationA. Human Language Technology Conference of the North American Chapter of the Association for Computational LinguisticsC. Boston, Massachusetts, USA, 2004. 101-104.11TILLMAN C, ZHANG T. A localized prediction model for statistical machine translationA. Proceedings of the 43rd Annual Meeting of the ACLC. Ann Arbor, 2005.557-564.12NAGATA M, SAITO K, YAMAMOTO K, et al. A clustered global phrase reordering model for statistical machine translationA. Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational LinguisticsC. Sydney, Australia, 2006. 713-720.13CHIANG D. A hierarchical phrase-based model for statistical machine translationA. Proceedings of 43rd Annual Meeting of the Association of Computational LinguisticsC. Michigan, USA, 2005. 263-270.14LIU Y, LIU Q, LIN S. Tree-to-string alignment template for statistical machine translationA. Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational LinguisticsC. Sydney, Australia, 2006. 609-616.15MARCU D, WANG W, ECHIHABI A, et al. SPMT: statistical machine translation with syntactified target language phrasesA. Proceedings of the 2006 Conference on Empirica