利用句法短语改善统计机器翻译性能

2015-04-21孙水华黄德根

中文信息学报 2015年2期

关键词：源语言目标语言搜索算法

孙水华，丁鹏，黄德根

(1. 大连理工大学计算机科学与技术学院，辽宁大连 116024；2. 福建工程学院信息科学与工程学院，福建福州 350118)

利用句法短语改善统计机器翻译性能

孙水华1，2，丁鹏1，黄德根1

(1. 大连理工大学计算机科学与技术学院，辽宁大连 116024；2. 福建工程学院信息科学与工程学院，福建福州 350118)

短语表是基于短语的统计机器翻译系统的一个核心组成部分，基于启发式方法抽取到的短语表受单词对齐错误和未对齐词的影响严重，同时抽取到的短语也并非句法意义上的短语。该文提出一种基于EM(Expectation-maximization)算法的双语句法短语抽取方法来抽取双语句法短语，此方法可以通过不断迭代的方式使各参数值达到最优。通过加入双语句法短语、增加新特征、重新训练三种不同的方法，将获得的双语句法短语与基于短语的统计机器翻译方法结合以提高统计机器翻译系统的性能。结果表明：三种方法都不同程度提高了译文的BLEU(BiLingual Evaluation Understudy)值，其中增加新特征方法提高了0.64个点。

统计机器翻译；EM算法；双语句法短语

1 引言

自P Koehn 等提出从基于词的对位中启发式学习短语翻译对[1]的方法以来，基于短语的统计机器翻译方法受到广泛关注，性能也不断提高。基于短语的统计机器翻译方法利用相邻词组合成的短语作为基本单位，在训练阶段获得短语表，在解码阶段利用短语表来获得候选翻译。但是短语表中的短语并非句法意义上的短语，不能充分利用语言的句法信息，而且基于启发式的短语抽取方法是以词对齐为基础来抽取短语对，词对齐错误和大量的词语对空[2]引进大量的无效短语使短语表变得很大。为此，研究者又提出基于句法的统计机器翻译方法，以源语言句法树或是目标语言句法树作为训练语料，形成了树到串[3]、串到树[4]、树到树[5]等机器翻译方法。基于句法的统计机器翻译方法抽取到的短语是句法意义上的短语，句法分析错误会大大影响抽取到的句法短语的质量,进而影响译文的质量，同时基于句法的统计机器翻译方法严格要求抽取句法意义上的短语，然而并不是所有的非句法短语都是无效的，所以这种严格的要求会损失掉一部分有益于机器翻译的非句法短语。

鉴于以上基于短语的统计机器翻译和基于句法的统计机器翻译的不足，本文提出利用双语句法短语来提高机器翻译性能。该方法克服了基于短语统计机器翻译方法未利用句法语言知识的不足，同时受语言句法分析准确率影响较小，且不需像基于句法统计机器翻译方法对于句法短语要求那么严格。在基于短语的统计机器翻译中利用了双语句法短语所蕴含的语言学知识来提高译文质量。

句法短语即句法意义上的短语，如名词短语，介词短语等。双语句法短语是从源语言和目标语言句法树中抽取的句法短语对。国内外不少学者对双语句法短语的对齐做了研究，刘冬明等[6]提出将低频短语和高频短语分开处理，并利用人工编写句法规则的方法来对齐名词短语；Imamura[7]提出一种双语句法短语结构对齐的方法，但时间复杂度太高，当句子太长时这种方法是不切实际的；刘群[8]提出一种双语短语结构对齐的搜索算法，但模型较为简单，在句法短语对齐过程中仅考虑了词语对齐，对齐过程中的参数值需人工调整，很难找到一个最优化的参数值。受此双语短语结构对齐搜索算法的启发，本文提出一种基于EM算法的双语句法短语对齐算法，不仅考虑了词语对齐，还考虑了句法短语标记对齐，通过不断迭代的过程使各参数值达到最优。

基于短语的统计机器翻译方法有简单实用的特点，很多学者都对其提出改进方法： Xu Jinxin[9]提出利用监督的方法来提高词对齐的准确率，但实验结果表明词对齐准确率的提高对于最后机器翻译BLEU值的提高效果较小，当加大训练语料时这种效果几乎可以忽略不计；何彦青等[10]引入“松弛尺度”标准来抽取短语表，保证更多源短语找到目标短语；Chen Boxing[11]在计算短语表中双语短语的各个特征时加入平滑技术，利用平滑过的短语表来

提高机器翻译性能。本文提出利用双语句法短语来提高机器翻译性能的方法，通过加入双语句法短语、增加新特征、重新训练三种不同的方法将双语句法短语融合到一个基于短语的机器翻译系统NiuTrans[12]中,取得了较好地效果。

2 双语句法短语的抽取

双语句法短语抽取通过双语短语结构对齐搜索算法得到对齐的双语短语，然后利用EM迭代算法获得新的参数值，利用新的参数值通过双语短语结构对齐搜索算法可以得到新的对齐双语短语。这种不断迭代的过程是收敛的，最终可以获得最优的参数值和对齐的双语短语。

2.1 双语短语结构对齐搜索算法

双语短语结构对齐搜索算法的输入是源语言和目标语言句子句法分析树，输出是两棵树中对齐的双语句法短语。整个短语结构对齐采用自底向上的柱形搜索算法,在源语言结构树上，自底向上计算源语言树结构中每个节点的最佳的N个局部对齐，每个节点上都保留最佳的N个局部对齐结果，即局部对齐列表。图1给出了几个源语言节点的局部对齐结构,局部对齐的逻辑结构如下：

Define LocalAlignment {

string SrcnodeSign; //源语言句子片段句法标记

pair TarnodeRange; //目标语言句子片段范围(i,j)，起始位置i，结束位置j

string TarnodeSign; //目标语言句子片段句法标记

double Score; //局部对齐评分

LocalAlignment*Children; //孩子节点局部对齐

}

图1 局部对齐结构示意图

(1)(2)(3)(4)SrcnodeSign：M(200)SrcnodeSign：M(多)SrcnodeSign：Q(名)SrcnodeSign：B(中外)TarnodeRange：(3，3)TarnodeRange：(1，1)TarnodeRange：(-1，-1)TarnodeRange：(4，4)TarnodeSign：CDTarnodeSign：JJRTarnodeSign：NULLTarnodeSign：JJScore：1．0Score：1．0Score：1．0Score：0．05Children：Empty(5)Children：Empty(6)Children：Empty(7)Children：Empty(8)SrcnodeSign：B(中外)SrcnodeSign：N(记者)SrcnodeSign：MCP(200多)SrcnodeSign：NP(中外记者)TarnodeRange：(6，6)TarnodeRange：(7，7)TarnodeRange：(1，3)TarnodeRange：(4，7)TarnodeSign：JJTarnodeSign：NNSTarnodeSign：QPTarnodeSign：NULLScore：0．03Score：0．8Score：．．．Score：．．．Children：EmptyChildren：EmptyChildren：(1)(2)Children：(4)(6)(9)(10)(11)(12)SrcnodeSign：NP(中外记者)SrcnodeSign：MP(200多名)SrcnodeSign：NP(200多名中外记者)SrcnodeSign：NP(200多名中外记者)TarnodeRange：(6，7)TarnodeRange：(1，3)TarnodeRange：(1，7)TarnodeRange：(1，7)TarnodeSign：NULLTarnodeSign：NULLTarnodeSign：NPTarnodeSign：NPScore：．．．Score：．．．Score：．．．Score：．．．Children：(5)(6)Children：(3)(7)Children：(8)(10)Children：(9)(10)图1(续)

图2给出了双语短语结构对齐搜索算法。该算法可以分为两步： (1)初始化叶子节点局部对齐列表；(2)自底向上对非叶节点进行局部对齐的归并(Merge Local Alignment)。

图2 双语短语结构对齐搜索算法

初始化叶子节点局部对齐时为每个源语言单词和对应的目标单词构造一个局部对齐，如图1所示，“中外”对应两个目标词，故有两个局部对齐(4)、(5)。同时为每个源语言单词增加一个TarnodeSign为NULL的局部对齐，为在局部对齐归并过程中过滤掉词对齐错误。局部对齐的评分由词语翻译概率和句法标记对齐概率求和得到(见图2 算法第5步)。

非叶节点的局部对齐归并过程即从该节点的所有孩子节点中选取局部对齐进行归并，直至所有的局部对齐组合都已被选取。若子节点局部对齐的目标范围重叠，则重新选取，否则进行归并。如图1所示，局部对齐(11)、(12)是由不同的子节点局部对齐归并得来。

归并过程中，归并所得局部对齐的TarnodeRange的左边界为子节点局部对齐的TarnodeRange左边界的最小值，右边界为子节点局部对齐的TarnodeRange的右边界的最大值。(见图2算法中归并子函数第9步)。寻找覆盖TarnodeRange的最小目标语言节点，TarnodeSign设为该节点的句法标记，如果该节点覆盖的范围与当前局部对齐的TarnodeRange不完全重合，则增加一个TarnodeSign为NULL的局部对齐。当前局部对齐得分(Score)由子节点局部对齐得分与句法标记对齐概率求和得到(见图2算法中归并子函数第13、17步)。

当自底向上对源语言树结构中所有非叶节点都执行局部对齐归并操作之后，根节点局部对齐列表中得分最高的局部对齐即为最优短语结构对齐。

2.2 基于EM算法的短语结构对齐

短语结构对齐搜索算法在归并的过程中可以过滤掉部分错误的词语对齐，好的词语对齐又可以促使短语结构对齐搜索算法得到更好的双语句法短语。故利用EM迭代算法，通过迭代使得词语对齐和句法标记对齐的准确率不断提高，从而得到更好的双语句法短语。

受IBM模型[13]方法的启发，本文利用生成式方法来计算词语对齐概率和句法标记对齐概率。一对双语句子的翻译概率为：

(1)

S为源语言句子，T为目标语言句子，A为短语结构对齐，a为词对齐。

在已知短语结构对齐A和词语对齐a的情况下：

(2)

其中ssign为源语言句法短语标记，tsign是对应的目标语言句法短语标记；sw是源语言单词，tw是对应的目标语言单词；spos是源语言单词位置，tpos是对应的目标语言单词位置；m是源语言句子的句法短语数，n是源语言单词数。

我们的目的是要知道所有的词翻译概率p(tw|sw)、句法标记对齐概率p(tsign|sisign)、对位概率p(tpos|spos)，使得句子的翻译概率P(T|S)最大，并且满足以下三个条件：

(1) ∑tsignp(tsign|ssign) =1；

(2) ∑tposp(tpos|spos) =1；

(3) ∑twp(tw|sw) =1

为求限定条件下P(T|S)的最大值，引入拉格朗日乘法因子λ、μ、ν，并求以下公式的极大值。

(3)

根据求极大值条件,辅助函数h关于λ、μ、ν、p的偏导数应等于零。式(3)对p(tw|sw)的偏导数为：

(4)

其中δ是Kronecker函数，当它的两个参数相同时值为1，否则值为0。由偏导数为0得：

(5)

因在实际应用中，训练数据是大规模翻译句对。同时将λsw替换可得：

(6)

其中N为训练语料的双语句对数，c(sw)代表单词sw在源语言句子S中出现的次数。

同理可求得句法标记对齐概率和对位概率：

p(tpos|spos) =

(7)

p(tsign|ssign) =

(8)

其中c(spos,tpos)为位置对齐次数，c(ssign,tsign)是句法标记对齐次数，c(ssign)是句法标记ssign在源语言句子句法树中出现的次数。

(1) 初始化三个概率 p(tsign|ssign),p(tw|sw),p(tpos|spos)；

(2) 应用双语短语结构对齐搜索算法求最优双语句法短语对齐；

(3) 利用步骤2求得的最优双语句法短语对齐和公式(6)、(7)、(8)重新求三个概率；

(4) 利用式(1)求P(T|S)，若P(T|S)变化很小，则停止迭代，否则跳到步骤2。

初始化p(tsign|ssign)时假设任一源语言句法标记与所有目标语言句法标记对齐的概率相等，初始的p(tw|sw)和p(tpos|spos)可用GIZA++训练双语语料获得。

当EM算法迭代结束时，源语言句法树的根节点的局部对齐列表中，存储了N个最优对齐。选出得分最高的对齐，并依据此对齐从根节点开始遍历相对应的子节点局部对齐。最终可以抽取出所有的双语句法短语。

3 基于双语句法短语的统计翻译模型

本文提出三种方法，将双语句法短语应用到基于短语的统计机器翻译系统中，探究利用双语句法短语改进基于短语机器翻译系统性能的方法和效果。

3.1 扩展训练语料规模后的重训练模型

短语表是基于短语的统计机器翻译系统中的一个核心组成部分，然而在利用启发式方法抽取短语表的过程中，由于词对齐错误和词扩展[14]；会引进错误短语对。基于启发式方法的缺点，本文提出将抽取到的双语句法短语作为双语句对，加入到训练语料中，利用NiuTrans翻译系统重新训练模型，获取短语表。双语句法短语是高质量的双语短语，这样可以增加高质量的短语对的共现次数，从而提高词语对齐的准确率和抽取的短语表的质量。我们用“Baseline+retrain”来代表这种方法。

3.2 加入句法短语特征的训练模型

Lopez 和Resnik[15]提出挖掘更好的特征可以提高机器翻译的质量，受此启发，本文增加一个句法短语特征到短语表中，若短语表中的短语为句法意义上的短语，则其句法短语特征为“是”，否则其句法特征为“否”。考虑到抽取到的双语句法短语是高质量的短语对，这个特征可以使得机器翻译系统在解码时选择更好的候选短语对。

NiuTrans系统利用对数线性模型框架，因此新增加的特征可以很容易地融合到模型中。

权重可以利用最小错误率训练算法在开发集上训练得到。我们用“Baseline+feature”来代表这种方法。

3.3 加入双语句法短语的训练模型

由于传统的基于词对齐的启发式短语抽取方法会出现词对齐错误和词对空问题，进而导致丢掉很多双语句法短语。为此，本文在用启发式方法抽取完短语表后，将抽取的双语句法短语加入到短语表中，这样可以弥补一部分由启发式短语抽取方法丢掉的短语对。将双语句法短语加入到短语表后，计算短语表中的短语对的四个翻译特征： (1)短语翻译概率；(2)反向短语翻译概率；(3)词典权重；(4)反向词典权重。在解码阶段利用新得到的短语表来匹配源语言句子的各个短语。我们用“Baseline+newphrase”来代表这种方法。

4 实验

实验采用了NiuTrans提供的数据集。语料的源语言为汉语，目标语言为英语。

从表1中可以看出英语句子要比汉语句子平均长8个词，且汉英句子都较长，特别是英语句子平均长度达到了33个词，这给句法分析带来了难度。利用基于EM迭代的短语抽取算法抽从训练语料的双语句法树中抽取出1 173 616对双语句法短语。

表1 实验语料的规模

实验利用东北大学开发的NiuTrans系统作为Baseline系统。NiuTrans系统目前支持基于短语和基于句法的统计机器翻译方法，我们用到了基于短语的统计机器翻译模块。Baseline系统使用如下几个特征： (1)短语翻译概率；(2)反向短语翻译概率；(3)词典权重；(4)反向词典权重；(5)语言模型特征；(6)目标语言词数特征，此特征是为了清除N元语言模型喜欢较短翻译的偏见。为了排除调序因素的影响，Baseline系统未考虑短语调序特征。

表2是将双语句法短语应用于基于短语的统计机器翻译系统NiuTrans后的翻译结果。从表2中我们可以看到，这三种方法都提高了机器翻译系统的性能。其中Baseline+feature方法提高的最多，提高了0.64个点的BLEU值。Baseline+newphrase方法提高了0.41个点的BLEU值。Baseline+retrain方法提高了0.23个点的BLEU值。

表2 应用双语句法短语后的机器翻译结果

这三种方法的基本想法都是引进对基于短语的统计机器翻译系统有用的双语句法短语，来提高机器翻译系统的性能。

Baseline+retrain方法，将双语句法短语加入到训练语料，然而在重新训练时仍使用启发式的短语抽取方法，这些双语句法短语对在重新训练时未能被全部抽取出来，所以Baseline+retrain的方法的效果并不显著。

Baseline+newphrase方法将抽取到的双语句法短语直接加入短语表中，充分利用了抽取到的双语句法短语，效果较好。但抽取到的双语句法短语的数量，相对于利用启发式方法抽取到的短语表中短语对的数量来说，规模较小。故在将双语句法短语加入到短语表中重新计算各短语对的特征值时，由于双语句法短语规模较小而使得非句法短语的得分较高。

Baseline+feature方法在将抽取到的双语句法短语加入到短语表的同时，新加入了一个特征来指示短语对是否是新加入的双语句法短语。这保证了在解码时优先选择双语句法短语，所以效果较好。

图3给出了一个抽取双语句法短语的实例，其中包含经过句法分析后的双语句子的句法分析树，双语句子的词对齐，以及抽取到的双语句法短语。

由于双语句法短语较多，我们手工抽样检查了抽取到的双语句法短语，我们发现存在的错误主要由以下几种原因引起：

句法分析错误,如图3所示，因句法分析错误将汉语句子中的“。”放在句法树中错误的位置，导致抽取的最后三对句法短语都错误的包含了“。”。

未对齐词，如图3所示，“the world”和“the people of the world”都对齐到了“世人”，显然这是由于the、people、 of、三个词都对空，且“the world”和“the people of the world”的句法标记都是NP,无法根据句法标记的偏向性进行选择。

在抽取双语句法短语的过程中，过滤掉了错误的对齐。如图3所示，单词“gained”错误的对齐到单词“许多”，然而在抽取到的双语句法短语“gained

the attention of the people of the world |||令世人瞩目”中过滤掉了此错误对齐，这将有利于在统计词语对齐次数并计算翻译概率时提高词语对齐的准确率。

5 结论

本文提出一种双语短语结构对齐搜索算法与EM算法迭代相结合的方法，来抽取双语句法短语，并通过加入双语句法短语、增加新特征、重新训练三种不同的方法将抽取到的双语句法短语应用到基于短语的统计机器翻译系统中。这种方法克服了基于短语统计机器翻译方法未利用句法语言知识的不足，同时受语言句法分析准确率影响较小，且不像基于句法统计机器翻译对于句法短语要求那么严格。在基于短语的统计机器翻译中利用了双语句法短语所蕴含的语言学知识来提高译文质量。结果表明，译文的BLEU得分都得到不同程度的提高。

双语短语结构对齐搜索算法与EM算法迭代相结合的方法受句法分析错误的影响，会引进一部分非句法短语，如果可以有效地过滤掉这部分短语，机器翻译性能会得到进一步提高。另外，本文提出的三种双语句法短语与基于短语的统计机器翻译系统相结合的方法还是比较简单的，下一步可以考虑利用双语句法短语更多的特征。除了将双语句法短语应用到基于短语的统计机器翻译系统中，可以考虑将双语句法短语应用到基于层次短语的统计机器翻译系统中，来提高机器翻译的性能。

[1] Koehn P, Och F J, Marcu D. Statistical Phrase-based Translation[C]//Proceedings of the Human Language Technology and North American Association for Computational Linguistics Conference.Edmonton,Alberta.2003:127-133.

[2] Hailong Cao, Andrew Finch， Eiichiro Sumita. Syntactic Constraints on Phrase Extraction for Phrase-Based Machine Translation[C]//Proceedings of SSST-4, Fourth Workshop on Syntax and Structure in Statistical Translation, COLING 2010.Beijing.2010:28-33.

[3] Yang Liu, Qun liu, Shouxun Lin. Tree-to-String Alignment Template for Statistical Machine Translation[C]//Proceedings of the 21st International Conference on Computational Linguistics and the 44th Annual Meeting of the Association for Computational Linguistics. Stroudsburg, PA, USA.2006:609-616.

[4] Yamada K, Knight K.A Syntax-Based Statistical Translation Model [C]//Proceedings of the 39thAnnual Meeting of the Association for Computational Linguistics. Toulouse,France.2001:523-530.

[5] Quirk C, Menezes A,Herry C. Dependency Treelet Translation: Syntactically Information Phrasal SMT[C]//Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics. Ann Arbor.2005:271-279.

[6] 刘冬明,赵军,杨尔弘. 汉英双语语料库中名词短语的自动对应[J]. 中文信息学报， 2003，17(5)：6-12.

[7] Imamura K. Hierarchical phrase alignment harmonized with parsing[C]//Proceedings of Six Natural Language Processing Pacific Rim Symposium.Tokyo.2001:377-384.

[8] 刘群. 汉英机器翻译若干关键技术研究[M].清华大学出版社.2008.

[9] Jinxi Xu, Jinying Chen. How Much Can We Gain from Supervised Word Alignment?[C]//Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics. Portland, Oregon.2011:165-169.

[10] 何彦青,周玉,宗成庆,王霞. 基于“松弛尺度”的短语翻译对抽取方法[J]. 中文信息学报，2007，21(5)：91-95.

[11] Boxing Chen, Roland Kuhn, George Foster, et al. Unpacking and Transforming Feature Functions: New Ways to Smooth Phrase Tables[C]//Proceedings of the MT Summit ⅩⅢ: the Thirteenth Machine Translation Summit. Xiamen, China.2011： 269-275.

[12] Tong Xiao, Jingbo Zhu, Hao Zhang, et al. NiuTrans: An Open Source Toolkit for Phrase-based and Syntax-based Machine Translation[C]//Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics. Jeju Island,Korea.2012.

[13] Peter F. Brown, Stephen A. Della Pietra etc. The mathematics of statistical machine translation: parameter estimation[J]. Computational Linguistics，1993: 263-309.

[14] Franz Josef Och. Statistical Machine Translation: From Single-Word Models to Alignment Templates[D]. Ph.d. thesis, Computer Science Department, RWTH Aachen, Germany.2002.

[15] Adam Lopez and Philip Resnik. Word-based alignment, phrase-based translation: What’s the link?[C]//Proceedings of the 7th conference of the association for machine translation in the Americas： visions for the future of machine translation. Cambridge, Massachusetts, USA .2006:90-99.

An Improved Syntactic Phrase Extraction Approach for Statistical Machine Translation

SUN Shuihua1,2,DING Peng1,HUANG Degen1

(1. School of Computer Science and Technology, Dalian University of Technology，Dalian, Liaoning 116024, China; 2. College of Information and Engineering, Fujian Uniuersity of Technology, Fuzhou, Fujian 350118, China)

The phrase table lies at the core of a phrase-based statistical machine translation system. The extracted phrase table based on heuristic methods is affected by incorrect word alignments, the unaligned words, and the absence of syntactic information. This paper presents a bilingual syntactic phrases extraction method based on the Expectation-maximization algorithm，which can optimize all parameters by iteratiions. Three techniques are examined to integrate bilingual syntactic phrases to the phrase-based machine translation system: direct augmentation of bilingual phrass，adding new features and re-training. Experiments show that all the three methods improve the BLEU score to varying degrees，with the top increase of 0.64 BLEU score by adding new features.

statistical machine translation; Expectation-maximization algorithm; bilingual syntactic phrases

孙水华(1962—)，博士研究生，副教授，主要研究领域为机器翻译、文本知识挖掘。E⁃mail：sunh@mail．dlut．edu．cn丁鹏(1987—)，硕士，主要研究领域为机器翻译、计算语言学。E⁃mail：15092170184@163．com黄德根(1965—)，博士，教授，博士生导师，主要研究领域为机器翻译、多语言文本信息抽取、文本知识挖掘。E⁃mail：huangdg@dlut．edu．cn

1003-0077(2015)02-0095-08

2013-01-27 定稿日期： 2013-05-21

跨语言信息检索中的机器翻译研究(61173100, 61173101, 61272375)

TP391