使用依存丛林的统计机器翻译方法

摘要

本发明涉及有效处理多个依存树的依存丛林，该依存丛林使用多个依存树来进行基于树的统计机器翻译。本发明的方法使用依存丛林来生成翻译规则和依存性语言模型，并且在将源语言文本转换为目标语言文本时应用所生成的翻译规则和依存性语言模型，从而提高翻译能力。

说明书

技术领域

本发明涉及一种使用依存丛林(dependency forest)的统计机器翻译方法，尤其 涉及一种使用依存丛林的统计机器翻译方法，其通过以下操作可以提高翻译能力：针 对双语语料库进行依存性分析以生成多个依存树，组合所生成的多个依存树以生成依 存丛林，使用该依存丛林来生成翻译规则和依存语言模型，然后在将源语言文本转换 为目标语言文本时，应用所生成的翻译规则和依存语言模型。

背景技术

图1示出了一句英文“He saw a boy with a telescope”的依存树。如图1所示，箭头 从子节点指向父节点。父节点常常代表子节点的头。例如，图1中“saw”是“he”的头。 由于依存树不需要句子的短语结构分析，所以依存树与短语结构分析相比，复杂度相 对较低。2008年沈(Shen)等人提出了一种串到依存性(string-to-dependency)的翻 译模型，将串转换为依存树。该串到依存性的翻译模型将源语言串转换为目标语言的 依存树，它有两个重要特征。第一个特征是，串到依存性翻译模型规则应当在目标语 言侧具有合式(well-formed)依存结构。该合式的依存结构允许有效的动态编程，并 且保持了很多有用的非组成性规则。该合式的依存结构可包括固定结构或浮动结构。 在固定结构中，所有子节点构成完整的依存树。浮动结构由具有公共头的同级节点构 成，而头本身是非特定的，或者是浮动的。例如，图2的(a)和(b)示出了两个固 定结构，图2的(c)示出了浮动结构。

图1例示了训练实例，其包括英文依存树、中文翻译和词排布(word arrangement)。 给出了一句英文，以方便地辨识英文词和中文词之间的对应关系。从一对对齐的串依 存性(string-dependency)中提取串依存性规则，类似于提取SCFG，仅仅目标语言 侧是合式的结构。例如，可能如下所述的提取与词对齐相对应的串依存性规则。

with((a)telescope)→dai wangyuanjing de

进一步地，通过将更小的规则“(a)telescope→wangyuanjing”替换为如下的非终 止符，可以获得具有一个非终止符的规则：

with(X₁)→dai X₁ de

这里，“X”表示非终止符，下标“1”表示源语言和目标语言的非终止符之间的对应 关系。

2008年沈等人介绍了一种依存性语言模型。借助该依存性语言模型，很好地描 述了目标句子的生成，因为该依存性语言模型直接建模了一句话的语义结构。与现有 技术中的元语法(n-gram)语言模型相比，反映了依存性的语言模型更擅长捕获词(例 如，图1中的“saw”……“with”)之间的非本地的依存性。当给出依存树时，依存性 语言模型概率成为定义在头词与其依存词之间的三个子模型的乘积。

例如，图1中的树概率可以如下计算：

概率＝P_T(saw)

×P_L(he|saw-as-head)

×P_R(boy|saw-as-head)

×P_R(with|boy，saw-as-head)

×P_L(a|boy-as-head)

×P_R(telescope|with-as-head)

×P_L(a|telescope-as-head)

这里，P_T(x)表示作为依存树的根节点的词x的概率。P_L和P_R分别表示右边和左 边分别的生成概率。

最近的一种依存性剖析器(parser)具有很高的性能(英文91％，中文87％)，但 是这种依存性剖析器对于统计机器翻译来说还不够。因为串到树(string-to-tree)系 统要依靠最好的树来进行参数评估，所以规则表和依存性语言模型的质量会受到剖析 出错的影响，从而出现翻译错误。

发明内容

技术问题

提出本发明是用来解决上述问题，并试图通过利用一个全新的依存丛林的概念来 提高规则表和依存性语言模型的质量，其中依存丛林是通过组合多个依存树，而非一 个最佳依存树而生成的。

另外，本发明试图通过应用利用依存丛林而生成的规则表和依存性语言模型来提 高翻译能力。

技术方案

依照本发明的第一方面，一种生成翻译规则的方法包括利用通过组合多个依存树 而生成的依存丛林来提取翻译规则。

依照本发明的第二方面，一种生成翻译规则的方法包括以下步骤：对于双语语料 库进行依存性分析；通过该依存性分析生成依存树，并且通过组合多个依存树来生成 依存丛林；针对该依存丛林内的每个节点搜索多个合式结构；以及当所述多个合式结 构中的依存结构对应于词对齐时，提取翻译规则。

依照本发明的第三方面，一种统计机器翻译方法包括利用翻译规则和依存性语言 模型来翻译源语言，该翻译规则和依存性语言模型是从通过组合多个依存树而生成的 依存丛林生成的。

依照本发明的第四方面，一种用于生成翻译规则的设备包括：通过对双语语料库 进行依存性分析来生成依存树，并且通过组合多个依存树来生成依存丛林的装置；针 对依存丛林中的每个节点搜索多个合式结构的装置；以及当所述多个合式结构内的依 存结构对应于词对齐时，提取翻译规则的装置。

依照本发明的第五方面，一种统计机器翻译设备包括：依存性剖析器，其通过对 双语语料库的的源句和目标句进行依存性分析来生成依存树，并且通过组合多个依存 树来生成该源句和目标句的依存丛林；翻译规则提取器，其利用依存丛林来提取翻译 规则；语言模型训练器，其利用目标句的依存丛林来生成依存性语言模型；以及解码 器，其通过应用翻译规则和依存性语言模型，将源句文本转换为目标句文本。

有益效果

因此，本发明的效果在于，通过根据依存丛林来生成规则表和依存性语言模型并 利用该规则表和依存性语言模型来进行翻译，相比于使用一个最佳依存树的翻译方法 而言，大大提高了串依存性翻译的能力，而所述依存丛林是通过组合多个依存树而生 成的。

附图说明

图1例示了训练示例，该示例包括英文句、中文翻译和词对齐的依存树。

图2例示了合式依存结构中的固定结构和浮动结构。

图3例示了英文句中的两个依存树。

图4例示了紧密示出两个依存树的依存丛林。

图5例示了依据本发明的统计机器翻译设备。

具体实施方式

以下将参照附图，详细描述本发明的示例性实施方式。通过以下的详细描述，将 清楚地理解本发明的配置及其可操作性的影响。

在详细介绍本发明之前，应当注意，附图中任何可能位置上的相同的参考数字对 应于相同的部件，并且当所知晓的配置可能使得本发明主旨引起不必要歧义时，详细 描述将被忽略。

本发明在基于树形结构的统计机器翻译构架中的训练步骤期间，使用源句串和对 应目标句的多个依存树。本发明建议了一种压缩形式的依存树，也被称为依存丛林， 以便有效地处理多个依存树。该依存丛林具有超图结构，就像一打包的丛林。基于超 图的依存丛林被安排在源句串中。通过检查一个目标短语是否是来自串到丛林 (string-to-forest)对齐语料库的合式结构，来提取多个翻译规则。在依存丛林中，每 个节点都是一个词。为每个节点添加一个区间(span)以区分该节点。这些节点在依 存丛林中通过超边(hyperedge)而连接起来。在依存树中，一条边从依存节点 (dependant)指向该依存节点的头，但是超边将所有具有公共头的依存节点进行打包。

规则提取算法以从下向上(bottom-up)的方式搜索每个节点的合式结构。该算 法保持了每个节点的k个最佳(k-best)合式结构。头的合式结构可从该头的依存节 点配置得来。

在依存丛林中，每个节点的k个最佳固定和浮动结构可通过操作其依存节点的固 定结构来获得。然后，当依存结构对应于词安排时，串依存性对应规则被提取。

依存丛林

图3的(a)和(b)例示了图1的英文句示例的两个依存树。介词短语“with a  telescope”可依赖于“saw”或“boy”。图4例示了一个依存丛林，其中通过共享公共节点 和边而紧密显示了两个依存树。

在该依存丛林中，每个节点是一个词。为了区分节点，为每个节点添加了区间。 例如，“a”的区间是(2，2)。因为“a”是该句中的第三个词。由于第四个词“boy”控制 了节点a_2，2，所以第四个词“boy”可以由boy_2，3表示。这里应当注意，要考虑“boy”的位 置。类似地，图3的(b)中的词“boy”可以表示为boy_2，6。在该依存丛林中，节点通 过超边而连接起来。在依存树中，边缘仅仅从依存节点朝向依存节点的头，但是超边 将所有具有公共头的依存节点打包。

例如，图4中的超边e1意味着，he_0，0，boy_2，3，和with_4，6是saw_0，6的从左边到右 边的依存节点。

e1：<(he_0，0，boy_2，3，with_4，6)，saw_0，6>

依存丛林形式上可由<V，E>对来表示。这里，V表示节点集合，E表示超边集合。 每个节点属于V(v∈V)，在包含n个词的句子w0：n-1＝w0…wn-1中，以w_i，j的形式 表示。w_i，j指示了对应于w_i，j的节点控制了除其本身以外的从位置i到位置j的子字符 串。每个超边属于E(e∈E)，由<tail(e)，head(e)>对来表示。head(e)属于V，如 head(head(e)∈V)，而tail(e)也属于V，如head(tail(e)∈V)的依存节点。

依存丛林具有一个超图结构，就像打包的丛林。然而，打包的丛林将对应于每个 超边的PCFG规则概率当做权重，依存丛林具有应用了该权重的超图。这是因为依存 性剖析器为依存树的每个边而不是依存丛林的超边，输出一个正或负分。例如，图3 的(a)中，边he→saw，boy→saw，和with→saw的分数分别是13，22和-12。

为了给每个超边分配概率，可以利用对应边的分数来首先获取超边的正数。

$c\left(e\right)=\exp \left(\frac{{\Sigma }_{v\in \mathrm{tails}\left(e\right)}s(v,\mathrm{head}\left(e\right))}{\left|\mathrm{tails}\left(e\right)\right|}\right)$

这里，C(e)表示超边e的计数，head(e)表示头，tail(e)表示头的依存节点集合，v 表示一个依存节点，s(v，head(e))表示v中的一边到head(e)的分数。例如，图4中， 超边e1的计数如下。

$c\left(e_1\right)=\exp \left(\frac{13+22-12}{3}\right)$

进一步地，超边的概率p(e)可通过对具有相同头的所有超边之间的计数进行归一 化而获得，所述所有超边是从训练语料库收集来的。

$p\left(e\right)=\frac{c\left(e\right)}{{\Sigma }_{e^{\prime }:\mathrm{head}\left(e^{\prime }\right)=\mathrm{head}\left(e\right)}c\left(e^{\prime }\right)}$

于是，可能获取一个加权的依存丛林，其中每个超边都具有一个概率。

基于丛林的规则提取

在基于树的规则提取中，一对语言(或双语习语)的对应于词排布的所有短语被 首先列出，然后检查对于目标短语的依存结构是否为合式结构。然而，由于目标短语 的合式结构在该算法中指数地增加，所以该算法不适用于丛林情景。

最近发展的、用以根据一个最佳树来提取树到串(tree-to-string)规则的GHKM 算法，已被成功扩充到该打包的丛林上去(2008年，Mi和Huang)。该算法区分了最 小单元规则和复合规则。虽然有指数数量的复合规则，但是提取自每个节点的最小规 则的数量在一定程度上受到了限制。因此，可能通过组合最小规则而获得出色的复合 规则。

然而，GHKM算法不能被用于从依存丛林中提取串依存规则。因为虽然该算法 要求在规则中存在完整的子树，但是固定或浮动依存结构都不能保证包括头的所有依 存节点。例如，图2的(c)的浮动结构事实上包括两个树。

关于以上，依据本发明的算法以从下向上的方式搜索每个节点的合式结构。该算 法保持每个节点的k个最佳合式结构，头的合式结构可从该头的依存节点的合式结构 中配置得来。例如，由于图4中，将telescope_5，6作为根的固定结构是(a)telescope， 所以将节点with_4，6作为根的固定结构可通过将节点with_4，6的依存节点的固定结构添 加至该节点而获得。图2的(b)例示了依据此结果的结构。

类似地，可以通过将依存节点boy_2，3的固定结构与with_4，6的固定结构进行连接， 来获得节点saw_0，6的浮动结构。图2的(c)例示了依据此结果的结构。

因此，节点的具有最高概率的k个固定和浮动结构可通过操作该依存丛林中的依 存节点的固定结构来获得。然后，当依存结构对应于词安排时，串依存性规则可以被 提取。

将讨论一种评估从节点提取的合式结构的方法。依据2008年Mi和Huang的文 档，分数计数被分配给每个合式结构。当给出了树碎片t时，借助内部-外部算法来计 算后验概率。

$\mathrm{\alpha \beta }\left(t\right)=\alpha \left(\mathrm{root}\left(t\right)\right)\times \underset{e\in t}{\Pi }p\left(e\right)\times \underset{v\in \mathrm{leaves}\left(t\right)}{\Pi }\beta \left(v\right)$

这里，root(t)表示树的根，e表示边，leaves(t)表示树的树叶(组件)集，α(·)表 示外部概率，β(·)表示内部概率。

例如，图4中，将boy_2，6作为根的子树具有下一个后验概率。

α(boy_2，6)×p(e₄)×p(e₅)×p(e₆)×β(a_2，2)×β(a_5，5)

然后，子树t的分数频率如下所示。

$c\left(t\right)=\frac{\mathrm{\alpha \beta }\left(t\right)}{\mathrm{\alpha \beta }\left(\mathrm{TOP}\right)}$

这里，TOP表示丛林的根节点。

当合式结构是非组分(non-constituent)时，使用包括合式结构的最小树碎片的 分数计数来近似分数计数。最后，可利用合式结构的分数计数来计算目标语言侧的具 有合式结构的规则的相对频率。

$\Phi \left(r\right|\mathrm{lhs}\left(r\right))=\frac{c\left(r\right)}{{\Sigma }_{r^{\prime }:\mathrm{lhs}\left(r^{\prime }\right)=\mathrm{lhs}\left(r\right)}c\left(r^{\prime }\right)}$

$\Phi \left(r\right|\mathrm{rhs}\left(r\right))=\frac{c\left(r\right)}{{\Sigma }_{r^{\prime }:\mathrm{rhs}\left(r^{\prime }\right)=\mathrm{rhs}\left(r\right)}c\left(r^{\prime }\right)}$

基于丛林的依存性语言模型训练

为了从依存丛林中训练出依存性语言模型，应该收集所有的头及其依存节点。该 收集可通过列出所有超边而容易地实现。类似地，每个超边e的后验概率被使用内部 -外部算法来计算。

$\mathrm{\alpha \beta }\left(e\right)=\alpha \left(\mathrm{head}\left(e\right)\right)\times p\left(e\right)\times \underset{v\in \mathrm{tails}\left(e\right)}{\Pi }\beta \left(v\right)$

例如，图4中的超边e2的后验概率计算如下。

αβ(e₂)＝α(saw_0，6)×p(e₂)×β(he_0，0)×β(boy_2，6)

于是，可以获得超边e的分数频率。

$c\left(e\right)=\frac{\mathrm{\alpha \beta }\left(e\right)}{\mathrm{\alpha \beta }\left(\mathrm{TOP}\right)}$

在每个元语法(例如，“boy-as-head a”)中，超边的包括元语法自身的相同分数 频率被分配。

表1示出了BLEU分数，以及针对中文-英文测试集的平均解码时间。

[表1]

规则 DepLM NIST2004 NIST2005 NIST2006 时间 树 树 32.99 29.55 30.10 18.6 树 丛林 33.55^*30.12^*30.88^*23.3 丛林 树 33.43^*30.10^*30.55^*20.9 丛林 丛林 34.37^**30.90^**31.51^**27.7

在表1中，第一翻译系统(基本翻译系统)使用由一个最佳依存树训练得到的依 存性语言模型和规则表，并且剩余的翻译系统将依存丛林应用到依存性语言模型和规 则表的至少一个中。^*或^**表示与基本翻译系统比起来更有意义的能力。

首先，对中文-英文评估集进行实验。表1示出了该测试集的BLEU分数。第一 列“规则”指示了串依存规则是由一个最佳依存树还是由该依存丛林训练得到。类似 地，第二列“DepLM”还区分了训练依存性语言模型的两种源语言。

基本翻译系统使用训练自一个最佳依存树的依存性语言模型和规则表。在本发明 的示例性实施方式中，通过增加获取自依存丛林的规则表和依存性语言模型，在 BLEU点从+1.3到+1.4的范围内，串依存性翻译得到了统一并且有意义的改善。进一 步地，即使使用训练自依存丛林的规则表和依存性语言模型，解码时间也稍微增加。

表2示出了韩文-中文测试集的BLEU分数。为了检查本发明的涉及一对不同语 言的效率，进行针对韩文-中文的翻译实验。训练语料库包括大约8.2M的韩语词和大 约7.3M的中文词。使用中文句来训练一个5元的依存性语言模型，和一个3元的依 存性语言模型。发展及测试集都包括具有单个参考的1006个句。表2示出了该测试 集的BLEU分数。同样，可以看到，依据本发明的基于丛林的方法与基本翻译相比， 取得了重大的进步。

[表2]

规则 DepLM NIST2004 树 树 32.99 树 丛林 33.55^*丛林 树 33.43^*丛林 丛林 34.37^**

图5例示了依据本发明示例性实施方式的一种统计机器翻译设备的内部配置。统 计机器翻译设备主要包括训练部和解码部。

在训练部的操作的简要描述中，依存性剖析器首先对双语语料库的源句和目标句 执行短语剖析。依据依存性分析，生成源句和目标句的依存树。依存性剖析器通过组 合多个所生成的依存树，来生成每个源句和目标句的依存丛林。

翻译规则提取器利用该依存丛林来生成翻译规则，并将所生成的翻译规则存储在 翻译规则表中。进一步地，依存性语言模型训练器利用针对目标句的依存丛林来生成 依存性语言模型，并将所生成的依存性语言模型存储在语言模型数据库(DLM)中。

在解码部的操作的简要描述中，源语言文本(或输入)被输入给解码器，该解码 器利用该翻译规则和依存性语言模型来生成目标语言文本(或输出)。该解码器可利 用从依存丛林生成的翻译规则和依存性语言模型来提高翻译能力。

同时，本发明还可以使用依存丛林来生成翻译规则并使用软件程序中的翻译规则 来实现该机器翻译方法，并通过将该程序记录在预定的计算机可读存储媒介中，而在 各种再现设备上应用该程序。该各种再现设备可以是PC、笔记本、便携式终端，以 及诸如此类。

例如，记录媒介可以是硬盘、闪存、RAM、ROM等各种再现设备的内部装置， 或者是光盘，例如CD-R或CD-RW、微型闪存卡、智能卡、记忆棒、多媒体卡等各 种再现设备的外部装置。

本发明详述的示例性实施方式并不限制本发明。本发明的范围应当由附带的权利 要求来解释，并且本发明的与其相等的范围内的所有技术应当解释为包括在本发明的 范围中。

工业实用性

本发明可广泛用于统计机器翻译领域，因为本发明可以通过分析双语语料库的依 存性来生成多个依存树，组合多个所生成的依存树来生成依存丛林，使用依存丛林来 生成翻译规则和依存性语言模型，然后在源语言文本转换为目标语言文本时，使用所 生成的翻译规则和依存性语言模型，从而提高翻译能力。