基于虚拟上下文的统计机器翻译短语表的过滤

殷 乐，张玉洁，徐金安

（北京交通大学 计算机学院，北京100044）

1 引言

目前层次短语模型是统计机器翻译（SMT）中性能最好的模型之一［1－5］，它可以有效提高翻译质量。但是由于该模型允许在短语中存在变量，造成短语表的规模急剧增大，解码的时间和空间消耗剧增。为了缓解这一问题，本文提出一种基于虚拟上下文的SMT短语表过滤方法，可以有效过滤短语表中冗余的短语对，减少解码在时间和空间上的过度消耗。

为了描述我们在短语表过滤上的工作，先简单介绍基于短语的SMT中相关的内容。短语表是SMT中基本的翻译知识，包含大量的短语对，每个短语对由源语言短语和目标语言短语组成。在构建基于短语的统计机器翻译系统时，需要从平行语料中自动抽取出短语表［6］，并利用目标语言的单语语料库训练目标语言模型。这个构建模型的过程通常称为训练。在翻译时，一个源语言句子首先被分割为短语序列，然后通过短语表，每个短语被翻译成目标语言的短语，最后这些目标语言的短语被重新组合生成一个目标语言句子。这个翻译的过程通常被称作解码，解码的模块被称作解码器。解码器会从候选译文中选取拥有最大概率的译文作为最后的输出。

对于一个源语言句子fJ1＝f1…fj…fJ，一个目标语言句子eI1＝e1…ei…eI，F J Och和 H Ney［7］提出基于最大熵的SMT模型如式（1）所示。

其中，hm（eI1，fJ1）是特征函数（m＝1，2，3，...M），λm是特征函数的权重。因为式（1）中的分母在解码过程中是常数，最优的译文可以通过式（2）选出。

译文的得分可以通过式（3）计算得到。

解码的任务是寻找拥有最大概率的译文，解码已经被证明是一个NP完全问题［8］。一个大规模的短语表将会造成解码在时间和空间上的过度消耗，并且影响机器翻译系统的实际应用。特别是将这样一个SMT系统移植到如PDA一类的移动终端时，几乎是不可能的。

为了解决这个问题，许多研究人员提出了多种过滤短语表的方法，主要集中于两类短语对，即错误的短语对和冗余的短语对。为了过滤短语表中错误的短语对，研究人员提出一种使用对数似然比的过滤方法［9］和使用依存结构限制目标短语数量的方法［10］。为了过滤短语表中冗余的短语对，研究人员则提出一种过滤单调组合短语对的方法［11］和一种使用对数线性模型过滤组合短语对的方法［12］。

本文中我们提出一种基于虚拟上下文的过滤方法，目标是过滤掉解码过程中几乎不会被使用的短语对。文中将这种短语对看作是冗余短语对。我们主要集中在两种冗余短语对：同源短语对（ISP）和复合短语对（CPP）。同源短语对指的是那些源语言相同而目标语言不同的短语对。这种短语对意味着同一个源语言短语有多个对应的目标短语，多的情况下会有几十甚至上百个，这种情况下一般会含有冗余短语对。复合短语对是指短语对的源语言短语可以由几个子短语组成，并且在短语表中存在以这些子短语作为源语言短语的短语对。这意味着一个复合短语对可以被几个子短语对替换，出现这种情况时，这些复合短语对中可能含有冗余的短语对。

针对上述的冗余短语对，我们设计实现了短语表过滤器，其处理流程大致如下：首先，过滤器使用对数线性模型计算短语对的得分；然后，过滤器使用虚拟上下文对短语对进行重排序；最后删除掉排名低的短语对。

文章其他部分组织如下，第2节详细描述基于虚拟上下文的过滤方法；第3节介绍我们的实验和评价结果；最后给出我们的结论。

2 短语表过滤算法

这一节介绍使用对数线性模型对短语对进行排序的过程，然后详细描述基于虚拟上下文的重排序算法和过滤冗余短语对的策略。

2.1 排序

为了找出几乎不会被解码器使用到的短语对，我们使用和解码器同样的算法评价短语对。我们使用对数线性模型计算短语对的得分，使用的特征包括：翻译概率、词汇化概率、反向翻译概率、反向词汇化概率和语言模型。选用这五个特征的理由是短语对的质量和这些特征密切相关。这些特征的权重通过开发集的数据训练得到。

过滤器对短语对排序的过程如下。

1）选择拥有相同源语言的短语对作为一个集合，用Si表示；

2）按照式（3）计算Si中每个短语对的得分，得分最高的短语对表示为SHi，其他短语对表示为SOi，它们的得分分别为Score（SHi）和Score（SOi）。

2.2 基于虚拟上下文的重排序

通常来说，解码器会选择SHi，而不是SOi。可是SOi在某些情况下会被解码器选择。出现这种情况的原因可以解释如下。在上文的利用式（3）的计算中，计算语言模型的得分的过程和解码器的计算过程并不完全相同，因为解码器会使用已生成的译文作为上下文信息计算语言模型。可是，在短语表过滤阶段，没有实际生成的译文供过滤器作为上下文计算。

由此，解码器会因为已生成的译文给SOi一个比SHi高的得分，导致过滤器和解码器的排序结果不同。为了弥补这一点，我们在过滤器中引入虚拟上下文来计算语言模型并对短语对进行重排序。这种策略可以保证，在重排序后低位短语对在实际解码中基本不会被使用，过滤掉这些短语不会影响翻译质量。

进一步描述，解码器中已经生成的译文作为上下文信息在语言模型特征上会产生一个增量，表示为ΔContext。如果解码器选择SOi而不选择SHi，是因为SOi的增量大于SHi，即当式（4）成立时，解码器会选择SOi。

在式（4）中，ΔContext（SOi）和 ΔContext（SHi）是SOi和SHi分别通过上下文在语言模型特征上获得的增量。

基于以上的考虑，我们设计了一种极端分配上下文的重排序策略，即分配给SOi最佳上下文使其获得最大增量，而分配给SHi最差上下文使其获得最小增量。在这种策略中，如果重排序后，SOi的排名依然低于SHi，那么可以说SOi就很难被解码器选用。这种策略可以简单表示为SOi与最佳上下文对决（vs）SHi与最差上下文。

为此，我们引入虚拟上下文模拟SHi的上下文，使得ΔContext（SHi）在语言模型上获得最低的得分，同理使用虚拟上下文模拟SOi的上下文，使得ΔContext（SOi）在语言模型上获得最高的得分。分别标记它们为 minΔContext（SHi）和 maxΔContext（SOi）。然后，依据新得分重新排序短语对。如果Score（SHi）＋minΔContext（SHi）＞Score（SOi）＋ maxΔContext（SOi），这意味着解码时，在任何上下文的情况下，SOi都很难被解码器使用到。

短语表的过滤算法如下。

1）对于一个目标语言短语W1W2……Wk，W1和 Wk是短语的边界。如果Wx1Wx2在2元语言模型中存在并且δ（Wx2，W1）＝1，则把Wx1作为目标语言短语的虚拟上下文；如果Wx1Wx2在语言模型中存在并且δ（Wk，Wx2）＝1，则把 Wx2作为目标语言短语的虚拟上下文。δ（x，y）是克罗内克函数，当x＝y时，δ（x，y）＝1，否则δ（x，y）＝0。除此之外，我们同样考虑了短语中包含变量的情况。给定一个目标语言短语 W1……Wm－1X Wm……Wk，X是一个变量。Wm－1和 Wm也是短语的边界。如果Wx1Wx2在语言模型中存在并且δ（Wm－1，Wx1）＝1，则把Wx2也作为目标短语的虚拟上下文；如果Wx1 Wx2在语言模型中存在并且δ（Wx2，Wm）＝1，则把Wx1也作为目标短语的虚拟上下文；

2）计算minΔContext（SHi）：在语言模型中分配一个上下文使得SHi获得最小得分增量；

3）计算Si中的其他短语对的 maxΔContext（SOi）：在语言模型中分配一个上下文使得SOi获得最大得分增量；

4）依据获得增量的新得分，对Si中的短语对进行重排序；

5）过滤掉排名低于SHi的短语对。

在这种极端上下文对比的情况下，排名低于SHi的短语对在其他上下文情况下也不会获得更大增量，因此只能排在SHi的后面。这意味着在其他情况下，解码器也不会跳过SHi而选择排名低于SHi的短语对。由此，过滤掉这些短语，译文的质量不会受影响而下降。

下面描述对复合短语对（CPP）的过滤。复合短语对意味着它的源语言短语可以被分解成多个子短语，同时这些子短语的短语对在短语表中存在，我们称这些短语对为子短语对。和同源短语的过滤算法一样，这里也引入了虚拟上下文。过滤算法如下。

1）计算复合短语对的得分：根据式（3）先计算一个基础得分，并在语言模型中分配一个上下文使得复合短语对的得分增量最大，二者相加作为复合短语对的得分。

2）计算子短语对的得分：根据式（3）先计算一个基础得分，并在语言模型中分配一个上下文使得子短语对的得分增量最小，二者相加作为子短语对的得分。

3）过滤：如果子短语对的得分之和大于复合短语对的得分，过滤掉复合短语对。

在文献［11－12］的方法中，他们的方法要求短语对（s1s2→t1t2）可以被过滤的一个前提是短语表中存在短语对s1→t1和s2→t2，即短语对（s1s2→t1t2）是单调组合的短语对［11］。我们过滤复合短语对（CPP）的方法和他们的方法不同，我们定义的复合短语对（s1s2→t1t2），我们只要求在短语表中同时存在源语言短语是s1和s2的短语对。

与前面过滤掉的同源短语对的道理相同，在这种极端上下文对比的情况下，复合短语对的得分低于子短语对的得分。这意味着在其他上下文的情况下，解码器只会选择子短语对，而不会选择被过滤掉的复合短语对。因此，在过滤掉复合短语对后，翻译质量不会受影响而下降。

3 实验

3.1 实验设置

为了验证本文的方法，我们使用一个基于层次短语解码器，在NTCIR－9数据上进行了中英方向的实验。NTCIR－9中英数据的训练集中有一百万句对，测试集和开发集分别有两千句对。

我们在训练集上运行GIZA＋＋［13］得到双向的单词对齐信息，并使用启发式的方法“grow－diag－final”［1］改善单词对齐结果；利用单词对齐信息，自动抽取短语表［6］。然后借助工具SRI language model［14］获得语言模型；通过在开发集上使用最小错误率训练法［15］得到特征的权重。在评测译文的质量时，我们使用 BLEU［16］。

3.2 实验结果

考虑实验的便捷性，我们首先选出源语言短语在测试句子中出现的短语对，作为准备过滤的短语表。

然后我们使用第2节介绍的方法，过滤ISP和CPP。表1是过滤前后短语表大小和翻译质量的变化。其中，第1列是过滤的方法（Filtering way），包括ISP、CPP和ISP＆CPP，None（baseline）是过滤前的情况。第2列是翻译质量（BLEU）。第3列是短语表消耗的内存大小（PTS）。第4列是短语表中短语对的数量（NUM）。第5列是过滤后剩余短语对的数量占原短语表的百分比（Reminder）。在过滤ISP后，剩余的短语对数量是原来数量的52.42%，同时BLEU值上升0.000 6。在过滤掉CPP后，剩余的短语对数量是原来数量的73.03%，同时BLEU值上升0.000 5。在过滤掉ISP和CPP后，剩余的短语对数量仅占原来数量的47.01%，同时BLEU同样上升0.000 5。实验结果显示同时过滤ISP和CPP时，效果最好。

表1 过滤前后短语表大小和翻译质量的变化

为了进一步压缩短语表中的大小，我们考虑在ISP过滤中只保留重排序后排名较高的几个短语对（表2）。

表2 ISP过滤中保留前5位（TOP 1～5）的情况下，短语表大小和翻译质量的变化

表2的结果显示，保留ISP排名前五位的短语对获得了最好的实验结果。在过滤掉短语表中大约70%的短语对后，BLEU值仅下降0.000 6。该实验结果也显示，保留越少的ISP短语对，BLEU值下降的越快。在我们的实验中，保留排名前五的ISP短语对获得了最好的效果，既极大压缩了短语表的规模又没有给翻译质量带来太大的影响。实验证明这种方法在实际应用中是有意义的。

在过滤的过程中我们计算短语的虚拟上下文最大与最小增量，由于在解码时，一些n－gram在训练的语言模型中没有出现，它们的得分是无法预知的。通常在测试集上，会利用回退和简单平滑的方法处理这些n－gram。但是我们无法枚举所有n－gram，这可能会造成本文方法计算的虚拟上下文最大与最小增量出现错误。因为我们不能得到系统在实际运行时，解码器中生成译文的情况，所以我们只针对测试集参考译文计算了2－gram的稀疏情况。结果如表3所示。

表3 译文2－gram在语言模型中的稀疏情况

由此可见，在2－gram的情况下，稀疏的情况的百分比只有11.53%。在大部分情况下，我们的方法计算出的结果应该是正确的。

4 结论

在这篇文章中，我们提出一种基于虚拟上下文的过滤短语表的方法，通过引入虚拟上下文计算短语对在语言模型特征上获得的最大和最小增量，并设计了对短语对进行重排序的过滤策略。实验结果显示，这种方法可以过滤掉短语表53%的短语对，同时没有造成翻译质量的下降。在保留重排序后前五名的短语对时，这种方法可以过滤掉70%的短语对，同时BLEU值仅有0.000 6的极微小的下降。实验证明这种方法可以有效过滤掉短语表中冗余的短语对，极大压缩短语表的规模。

在以后的工作中，我们将尝试融合其他信息进一步提升这种方法的有效性。

［1］Philipp Koehn，Och F J，Marcu D.Statistical Phrase－Based Translation［C］／／Proceedings of the 2003Human Language Technology Conference of the North A－merican Chapter of the Association for Computational Linguistics，2003：127－133.

［2］R Zens，F J Och，H Ney.Phrase－Based Statistical Machine Translation［C］／／Proceedings of M.Jarke，J.Koehler，G.Lakemeyer（Eds.）：KI－2002：Advances in artificial intelligence.25.Annual German Conference on AI，KI 2002，2002：18－32.

［3］Philipp Koehn.Pharaoh：a beam search decoder for phrase－based statistical machine translation models［C］／／Proceedings of the Sixth Conference of the Association for Machine Translation in the Americas，2004：115－124.

［4］D Chiang.A hierarchical phrase－based model for statistical machine translation［C］／／Proceedings of ACL 2005，2005：263－270.

［5］D Chiang.Hierarchical phrase－based translation［C］／／Proceedings of Computational Linguistics，2007，33（2）：201－228.

［6］F J Och，H Ney.The alignment template approach to statistical machine translation［J］.Computational Linguistics，2004，30（4）：417－449.

［7］F J Och，H Ney.Discriminative training and maximum entropy models for statistical machine translation［C］／／Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics （ACL），Philadelphia，PA，July 2002.

［8］K Knight.Decoding complexity in word replacement translation models［C］／／Proceedings of Computational Linguistics，1999，25（4）.

［9］Wu Hua，Haifeng Wang.Comparative Study of Word Alignment Heurist Based SMT［C］／／Proceedings of Machine Translation Summit XI，2007：507－514.

［10］L Shen，J Xu，R Weischedel.A new string－to－dependency machine translation algorithm with a target dependency language model ［C］／／Proceedings of ACL－08：HLT，Columbus，Ohio，2008：577－585.

［11］Z He，Y Meng，Y Lj，et al.Reducing SMT rule table with monolingual key phrase［C］／／Proceedings of the ACL－IJCNLP 2009Conference，Singapore，2009：121－124.

［12］Seung－Wook Lee，Dongdong Zhang，Mu Li，et al.Translation model size reduction for hierarchical phrase－based statistical machinetranslation［C］／／Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics（Volume 2：Short Papers），Jeju Island，2012：291－295.

［13］F J Och，H Ney.Improved statistical alignment models［C］／／Proceedings of the 38th Annual Meeting of the Association for Computational Linguistics，Korea，2000：440－447.

［14］A Stolcke.Srilm －an extensible language modeling toolkit［C］／／Proceedings of the International Conference on Spoken language Processing，volume 2，2002：901－904.

［15］F J Och.Minimum error rate training in statistical machine translation［C］／／Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics，2003：160－167.

［16］K Papineni，S Roukos，T Ward，et al.Bleu：a method for automatic evaluation of machine translation［C］／／Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics，2002：311－318.