CN101398815B - 一种机器翻译方法 - Google Patents

Abstract

本发明提供一种机器翻译方法，包括以下步骤：步骤1)分析源语言串，得到源语言串的共享压缩句法森林；步骤2)根据已知的源语言与目标语言之间的翻译规则集合，对句法森林进行匹配，得到共享压缩翻译森林；步骤3)利用搜索算法遍历所述翻译森林生成最终翻译结果。本发明利用共享压缩森林来指导翻译，能够从大量的树中搜索翻译结果，远远超过了单独使用N-best树的搜索空间。在223万平行双语语料数据集上，与使用30-best树解码的模型相比，本发明的翻译速度快1.4倍、翻译性能高1.7个BLEU点。

Description

一种机器翻译方法 

技术领域

本发明属于自然语言处理技术领域，具体地说，本发明涉及一种基于树的统计机器翻译技术领域。 

背景技术

基于句法的统计机器翻译模型已经成为当前主流的翻译方法，按照输入的不同，可以分为基于串的模型和基于树的模型(基于树的模型可参考Yang Liu，Qun Liu，and Shouxun Lin.2006.Tree-tostring alignment template for statistical machinetranslation.In Proceedings of COLING-ACL，pages 609-616，Sydney，Australia，July.和Liang Huang，Kevin Knight，and Aravind Joshi.2006.Statistical syntax-directed translation with extended domain of locality.In Proceedings of AMTA.)。与基于串的模型相比，基于树的模型以句法树作为输入，优点是：解码速度快、模型简洁、不需要二叉化；然而该模型有一个缺陷：只使用单棵句法树来指导翻译，由于基于句法的模型对句法分析性能很敏感，导致句法分析错误会引入错误的翻译。一种简单的方法是使用N-best树，对每棵树都解码，最后输出概率最高的翻译结果，但这种方法搜索空间有限，并且不能共享不同树相同的节点，导致许多节点要重复解码，既浪费空间又消耗时间。同时，这种基于树的统计机器翻译系统由于只使用单棵句法树指导翻译，往往会出现翻译错误率过高的问题。 

发明内容

本发明的目的是克服现有技术的不足，结合共享压缩森林技术，提出一种能够提高翻译性能，降低翻译时间和存储空间消耗的机器翻译方法。 

为实现上述发明目的，本发明提供的机器翻译方法，包括以下步骤： 

步骤1)分析源语言串，得到源语言串的共享压缩句法森林； 

步骤2)根据已知的源语言与目标语言之间的翻译规则集合，对句法森林进行匹配，得到共享压缩翻译森林；所述共享压缩翻译森林是一个图G＝(节点集合V，翻译超边集合E)。其中，节点是具有句法意义的节点； 翻译超边是一个三元组：(翻译规则，头节点，尾节点集合)，翻译规则描述了源语言与目标语言对齐关系。共享压缩翻译森林表示了源语言到目标语言的推导过程。 

步骤3)利用搜索算法遍历所述翻译森林生成最终翻译结果。 

上述技术方案中，所述步骤1)中，还包括对所述共享压缩句法森林进行剪枝处理；所述步骤2)中，进行匹配的所述句法森林是经过剪枝处理后的共享压缩句法森林。 

上述技术方案中，所述剪枝处理的方法是：对于共享压缩句法森林中的每个节点v，计算Viterbi向内概率负对数β(v)、向外概率负对数α(v)；对于每个句法超边e_p依次计算 

$\mathrm{\α\β}\left(e_p\right)=\mathrm{\α}\left(\mathrm{Head}\left(e_p\right)\right)+\underset{v_i\∈\mathrm{Tails}\left(e_p\right)}{\mathrm{\Σ}}\mathrm{\β}\left(v_i\right)$

δ(e_p)＝αβ(e_p)-β(TOP) 

如果δ(e_p)小于预先设定的阈值t，则保留超边e_p，否则删除； 

其中Head(e_p)表示超边e_p的头节点，Tails(e_p)表示超边e_p的尾节点集合，β(TOP)为1-best句法树概率之负对数值。 

上述技术方案中，所述步骤1)中，通过句法分析器对源语言串进行分析，所述句法分析器是Charniak parser、Bikel Parser、Stanford parser、Collins Parser或MuskCpars句法分析器。 

上述技术方案中，所述步骤2)中，所述源语言与目标语言之间的翻译规则集合中的翻译规则从包含三元组的语料库中抽取得出，所述三元组是源语言树或串，目标语言串或树以及源语言与目标语言间的词语对齐方式。 

上述技术方案中，所述翻译规则采用GHKM算法进行抽取。 

上述技术方案中，所述步骤3)中，遍历句法分析森林中的每个节点，使用枚举的方式对翻译规则集合和句法森林进行匹配，得到每个节点的翻译超边和与其相应的首尾节点，从而组成翻译森林。 

本发明具有如下技术效果： 

本发明利用共享压缩森林来指导翻译，能够从大量的树中搜索翻译结果，远远超过了单独使用N-best树的搜索空间。在223万平行双语语料数据集上，与使用30-best树解码的模型相比，本发明的翻译速度快1.4倍、 翻译性能高1.7个BLEU点。 

附图说明

以下，结合附图来详细说明本发明的实施例，其中： 

图1为本发明提供的基于共享压缩森林机器翻译方法总体技术方案的实现流程图； 

图2为三元组实例；三元组包括源语言树，目标语言串，源语言与目标语言间的词语对齐； 

图3为翻译规则实例； 

图4为共享压缩句法森林实例； 

图5为共享压缩翻译森林实例。 

具体实施方式

如图1所示，图1为本发明提供的基于共享压缩森林的机器翻译解码方法总体技术方案的实现流程图，该方法包括以下步骤： 

步骤101)、利用句法分析器分析源语言串并输出共享压缩句法森林； 

句法分析的主要任务是将输入的源语言串分析出相应的句法树。可用的短语树句法分析器：Charniak parser、Bikel Parser、Stanford parser、Collins Parser、MuskCpars；句法分析器不仅要输出1-best树，而且要输出整个共享压缩森林，即：最终生成根节点的所有可能的句法分析树组成的共享压缩森林。本实施例中，采用的是MuskCpar分析器可参考Deyi Xiong，Shuanglong Li，Qun Liu，Shouxun Lin，Yueliang Qian.2005.Parsing the Penn Chinese Treebank withSemantic Knowledge.In Proceedings of IJCNLP05，Jeju Island，Korea.。图4给出了一个句法森林实例：节点IP_0，6表示该节点标记为IP，跨度为0到6；超边e_p1表示一个语法规则：IP_0，6(NPB_0，1VP_1，6)；对于每个超边，用Head(e_p1)表示头节点：Head(e_p1)＝IP_0，6，Tails(e_p1)表示尾节点集合：Tails(e_p1)＝{NPB_0，1，VP_1，6}。一个或多个相互连接的超边形成句法分析子树片段。句法分析器要输出共享句法分析森林，具体实施方案：从根节点开始递归输出所有节点和相应的句法分析超边。这些节点与超边组成共享压缩句法森林。 

步骤102)、利用剪枝算法生成剪枝后共享压缩句法森林； 

步骤101输出的整个共享压缩森林含有大量概率很低的垃圾超边和节 点，需利用剪枝算法进行缩减，具体剪枝算法如下： 

首先，对于共享压缩句法森林中的每个节点v，计算Viterbi向内概率负对数β(v)、向外概率负对数α(v)；再对于每个句法超边e_p依次计算 

$\mathrm{\α\β}\left(e_p\right)=\mathrm{\α}\left(\mathrm{Head}\left(e_p\right)\right)+\underset{v_i\∈\mathrm{Tails}\left(e_p\right)}{\mathrm{\Σ}}\mathrm{\β}\left(v_i\right)$

δ(e_p)＝αβ(e_p)-β(TOP) 

其中β(TOP)为1-best句法树概率之负对数值，如果δ(e_p)小于预先设定的阈值t，则保留超边e_p，否则删除。最终将留下的超边和与之相关的节点组成剪枝后的共享压缩句法森林。该方法的特点是对每一条句法超边进行Viterbi向内向外概率计算，而不是对每一个节点进行计算，这样能剪掉更多的垃圾超边，使得剪枝处理更加有效。本步骤中向内概率负对数β(v)、向外概率负对数α(v)的计算方法可参考Charniak，Eugene.1993.Statistical LanguageLearning，MIT Press.Cambridge，Massachusetts. 

步骤103)、根据源语言与目标语言之间的翻译规则集合，对句法森林进行匹配，得到共享压缩翻译森林。 

以共享压缩句法森林与翻译规则集合 

作为输入，利用转换算法生成翻译森林。其中，共享压缩句法森林为步骤102)的输出；翻译规则集合 

可通过以下现有技术得到：主要是从三元组(源语言树或串，目标语言串或树，源语言与目标语言的词语对齐)中抽取相应的翻译规则，使用GHKM算法抽取。GHKM算法可参考Michel Galley，Mark Hopkins，Kevin Knight，and Daniel Marcu.2004.What’sin a translation rule？In Proceedings of the Human Language Technology Conference/North AmericanChapter of the Association forComputational Linguistics(HLT/NAACL). 

图2给出了一个实例(源语言为汉语、目标语言为英语)，利用GHKM算法可以抽出翻译规则。表1中是部分抽出的翻译规则： 

r₁＝VPB(VV(juxing)AS(le)x₀：NPB)→held a x₀

翻译译规r1的左部LHS(r1)为一个树结构，如图3所示，规则尾节点集合Tails(r1)＝{NPB}；表示当源语言端树结构为VPB(VV(juxing)AS(le)NPB)，且NPB节点的翻译结果为“meeting”时，VPB覆盖部分的翻译结果：held a meeting。 

表1 

Translation rule 

r₁    VPB(VV(jǔxing)AS(le)x₁：NPB)→held a x₁

r₂    NPB(x₁：NR)→x₁

r₃    NR(Bùshi)→Bush 

r₄    CC(yǔ)→with 

...    ... 

本实施例中，通过枚举的方式对翻译规则集合和句法森林进行匹配。 

具体方法如下： 

按照先续顺序遍历句法分析森林中的每个节点v， 

在对每一个以v为根节点的句法分析超边e进行如下操作： 

1、在翻译规则集合 

中，查找所有以v的句法标记为根节点且能够覆盖e表示的语法规则的翻译规则 

即：e表示的语法规则为LHS(r)的子树片段(子树片段是指森林或树中连续节点、边组成的子图)； 

2、对每一个翻译规则r的LHS(r)，按照先续遍历LHS(r)每个节点并从v节点开始匹配，先查看LHS(r)的根节点是否与v节点一致，再查看孩子节点是否一致，如果一致则继续匹配下一个孩子节点，直到LHS(r)被遍历完，如果不一致，则返回匹配失败信息。如果匹配成功则生成一个翻译超边e；翻译超边是一个三元组：(翻译规则，头节点，尾节点集合)。例：当搜索到图4中的IP_0，6节点时，翻译规则r₅：IP(x₁：NPB x₂：VP)→x₁x₂与子树片段：IP_0，6(NPB_0，1VP_1，6)完全匹配，即：所有规则左部树结构(IP(NPB VP))与子树片段(IP(NPB VP))树结构及对应节点句法标记都相同，则生成翻译超边e₁＝(r₅，IP_0，6，{NPB_0，1，VP_1，6})。翻译超边与翻译规则对应关系可参考表2。 

3、如果2中所有匹配都失败，将根据以v为根节点的所有句法超边生成相应的缺省翻译超边。如：如果VPB_3，6没有可用翻译规则，则根据句法超边e_p2＝P_3，6(VV_3，4AS_4，5NPB_5，6)生成相应的翻译超边e_t1＝(P_3，6 (x₁：VV_3，4x₂：AS_4，5x₃：NPB_5，6)→x₁x₂x₃，IP_3，6，{VV_3，4AS_4，5NPB_5，6})，即我们认为该翻译超边进行顺序翻译。 

遍历句法分析森林中的每个节点后，得到每个节点的翻译超边和与其相应的首尾节点，从而组成翻译森林(如图5所示)。 

表2 

translation hyperedge       translation rule 

e₁                    r₅    IP(x₁：NPB x₂：VP)→x₁ x₂

e₂                    r₆    IP(x₁：NP x₂：VPB)→x₁ x₂

e₃                    r₉    VP(PP(P(yǔ)x₁：NPB)VPB(VV(jǔxing)AS(le)x₂：NPB))→held x₂ with x₁

e₄                    r₇    VP(PP(P(yǔ)x₁：NPB)x₂：VPB)→x₂ with x₁

e₅                    r₈    NP(x₁：NPB CC(yǔ)x₂：NPB)→x₁ and x₂

e₆                    r₁    VPB(VV(jǔxing)AS(le)x₁：NPB)→held a x₁

步骤104)、利用柱状解码算法遍历压缩森林并生成最终翻译结果。 

以步骤103输出的共享压缩翻译森林作为输入，利用搜索算法生成最终的翻译结果，具体过程如下： 

按照后续遍历顺序，自底向上对于共享压缩翻译森林中的每个节点v，对所有的Head(e_t)＝v的翻译超边e_t，生成相应的翻译假设，再根据柱状图，按照预先设定的阈值剪枝，即：与最高翻译假设得分差值超过某一个设定值则会被剪掉。最终输出翻译假设得分最高的翻译结果。柱状图解码算法以及该解码算法中涉及到的翻译假设得分和柱状图等概念可以参考Philipp Koehn.2004.Pharaoh：a beam search decoder for phrase-based statistical machine translation models.InProceedings of AMTA，pages 115-124. 

最后所应说明的是，以上仅用以说明本发明理论原理和技术方案而非限制。本领域的普通技术人员应当理解，对本发明的技术方案进行修改或者等同替换，都不脱离本发明技术方案的精神和范围，其均应涵盖在本发明的权利要求范围当中。 

Claims (6)

1.一种机器翻译方法，包括以下步骤：

步骤1)分析源语言串，得到源语言串的共享压缩句法森林，对所述共享压缩句法森林进行剪枝处理；

步骤2)根据已知的源语言与目标语言之间的翻译规则集合，使用枚举的方式对剪枝处理后的共享压缩句法森林进行匹配，得到共享压缩翻译森林；

步骤3)利用搜索算法遍历所述共享压缩翻译森林生成最终翻译结果。

所述步骤1)中，所述剪枝处理的方法是：对于共享压缩句法森林中的每个节点v，计算Viterbi向内概率负对数β(v)、向外概率负对数α(v)；对于每个句法超边e_p依次计算

$\mathrm{\α\β}\left(e_p\right)=\mathrm{\α}\left(\mathrm{Head}\left(e_p\right)\right)+\underset{v_i\∈\mathrm{Tails}\left(e_p\right)}{\mathrm{\Σ}}\mathrm{\β}\left(v_i\right)$

δ(e_p)＝αβ(e_p)-β(TOP)

如果δ(e_p)小于预先设定的阈值t，则保留超边e_p，否则删除；

其中Head(e_p)表示超边e_p的头节点，Tails(e_p)表示超边e_p的尾节点集合，β(TOP)为1-best句法树概率之负对数值。

2.根据权利要求1所述的机器翻译方法，其特征在于，所述步骤1)中，通过句法分析器对源语言串进行分析，所述句法分析器是Charniakparser、Bikel Parser、Stanford parser、Collins Parser或MuskCpars句法分析器。

3.根据权利要求1所述的机器翻译方法，其特征在于，所述步骤2)中，所述源语言与目标语言之间的翻译规则集合中的翻译规则从包含三元组的语料库中抽取得出，所述三元组是源语言树或串，目标语言串或树以及源语言与目标语言间的词语对齐方式。

4.根据权利要求3所述的机器翻译方法，其特征在于，所述翻译规则采用GHKM算法进行抽取。

5.根据权利要求3所述的机器翻译方法，其特征在于，所述步骤2)中，遍历共享压缩句法森林中的每个节点，使用枚举的方式对翻译规则集合和共享压缩句法森林进行匹配，得到每个节点的翻译超边和与其相应的首尾节点，从而组成共享压缩翻译森林。

6.根据权利要求1所述的机器翻译方法，其特征在于，所述步骤2)中，所述共享压缩翻译森林是一个图G＝(节点集合V，翻译超边集合E)，其中，所述节点是具有句法意义的节点；所述翻译超边是一个三元组：翻译规则，头节点，尾节点集合；翻译规则描述了源语言与目标语言对齐关系。

Images