一种基于依存连贯性约束的双语词语自动对齐方法

摘要

本发明公开了一种基于依存连贯性约束的双语词对齐方法。该方法首先对训练句子对进行依存句法分析。在训练阶段，利用训练句子对和依存句法树，训练基于源语言端和目标语言端依存连贯性约束的词对齐模型。在测试阶段，利用基于源语言端和目标语言端依存连贯性约束的词对齐模型为测试句子对产生满足源语言端和目标语言端依存连贯性约束的词对齐结果，并将这两个词对齐结果进行合并，产生一个兼顾准确率和召回率的满足双语依存连贯性约束的词对齐结果。本发明相对于现有技术得到的词对齐错误率较低。

说明书

技术领域

本发明属于自然语言处理领域，特别涉及统计机器翻译和双语词语自 动对齐的方法。

背景技术

词对齐，顾名思义，就是标识出两种语言的对译句子之间以词语为单 位的翻译对应关系。词对齐是统计机器翻译的重要组成部分，它是基于短 语的翻译模型抽取短语表和调序规则的基础，甚至是基于句法的翻译模型 中抽取句法翻译规则的基础。通常情况下，词对齐的质量直接影响着统计 机器翻译系统的翻译质量。

词对齐的方法大体可分为两类：启发式方法和统计方法。启发式方法 通过计算词语之间的同现测度函数值来判断词语是否对齐，统计方法则通 过建立数学模型来描述双语词语的对齐关系。研究表明，统计方法的词对 齐质量要优于启发式方法，因此近些年来统计方法成为词对齐研究的热 点。

统计词对齐模型又可以进一步划分为生成式模型和判别式模型。在过 去的超过15年的时间中，以IBM的5个词对齐模型以及HMM词对齐模 型为代表的生成式模型依然是应用最为广泛的词对齐模型。其原因是：根 据这几个模型开发的GIZA++工具包被广泛的使用，以及其在大规模翻译 任务上不可比拟的鲁棒性。尽管如此，词对齐的质量依然不能满足统计机 器翻译系统的需求，特别是在差异比较大的两种语言上，比如汉语到英语 的对齐。研究人员相信限制生成式模型的词对齐质量的主要原因是：它们 仅仅使用了双语平行语料进行模型的训练，而没有考虑任何语言学方面的 知识。因此，近些年来，研究人员建立了许多融入语言学信息的判别式词 对齐模型，并采用手工标注的词对齐语料对模型进行有监督训练。众所周 知，判别式模型需要大量的手工标注语料进行模型参数的优化训练。然而 手工标注双语词语对齐语料是一项十分枯燥且非常困难的工作，而且在绝 大多数语种上还不存在大规模的手工标注词对齐语料，因此目前的判别式 词对齐模型都是在规模很小的手工标注语料(小于1000个句子对)上训 练的，这使得训练得到的词对齐模型在大规模翻译任务上的适应性很差。 虽然参考文献【C.Dyer，J.Clark，A.Lavie and N.A.Smith，2011. Unsupervised word alignment with arbitrary features.In ACL′11，pages 409-419.】提出了一种通过无监督的方式进行判别式模型训练的方法，但 是该方法在训练阶段需要耗费大量的时间，因此其可处理的数据规模非常 有限。

另外一种提高词对齐质量的方法是将句法信息融入到一个生成式词 对齐模型当中，然后利用无监督的方式进行模型的训练。这样既可以将句 法信息融入到词对齐模型中，又不需要手工标注的词对齐语料进行模型的 训练。句法连贯性认为：被源语言端句法树上的子树所控制的短语，在翻 译到目标语言端时也趋向于挨在一起。参考文献【Heidi J.Fox，2002. Phrasal cohesion and statistical machine translation.In EMNLP′02，pages 304-311】通过统计一个手工标注词对齐语料中源语言端句法子树对齐到目 标语言端时的交叉数目来研究句法连贯性，实验结果显示源语言端依存句 法树的子树在对齐到目标端时出现交叉的情况较少。因此如果利用依存连 贯性来约束双语词对齐的过程，将会有益于提高词对齐的质量。

发明内容

(一)要解决的技术问题

本发明所要解决的技术问题是生成式词对齐模型没有融入句法信息 以及训练判别式词对齐模型需要手工标注的词对齐语料的问题。

(二)技术方案

为了解决上述技术问题，本发明将依存句法树的信息融入到词对齐模 型中，利用依存连贯性来约束词对齐的过程，然后利用大规模的双语平行 语料(而不是小规模的人工标注语料)进行模型的训练。

具体来说，本发明提供一种基于依存连贯性约束的双语词对齐方法， 该方法根据一个双语训练集产生一个词对齐模型，利用该词对齐模型对测 试句子对进行词对齐，生成一个词对齐结果，其中所述双语训练集包括多 个训练句子对，所述每个训练句子对包括语义相互对应的一个源语言句子 和一个目标语言句子；该方法训练一个基于源语言端和目标语言端依存连 贯性约束的词对齐模型，并利用该词对齐模型产生关于该测试句子对的满 足源语言端和目标语言端依存连贯性约束的词对齐结果，并将这两个词对 齐结果进行合并，产生一个满足双语依存连贯性约束的词对齐结果。

根据本发明的一个具体实施方式，该方法包括如下步骤：步骤S1、对 所述双语训练集中的每个训练句子对的源语言句子和目标语言句子进行 依存句法分析，得到源语言端的依存句法树和目标语言端的依存句法树； 步骤S2、利用所述双语训练集中的训练句子对和源语言端的依存句法树， 训练一个基于源语言端依存连贯性约束的词对齐模型；利用双语训练集中 的训练句子对和目标语言端的依存句法树，训练一个基于目标语言端依存 连贯性约束的词对齐模型；步骤S3、首先，利用所述基于源语言端依存连 贯性约束的词对齐模型为所述测试句子对产生一个符合源语言端依存连 贯性约束的词对齐结果；然后，利用所述基于目标语言端依存连贯性约束 的词对齐模型为所述测试句子对产生一个符合目标语言端依存连贯性约 束的词对齐结果；最后，将这两个词对齐结果进行合并，产生一个满足双 语依存连贯性约束的词对齐结果。

根据本发明的一个具体实施方式，在步骤S1中，当所述双语训练集 的源语言或目标语言是汉语时，在进行依存句法分析之前对训练句子对中 的汉语句子进行分词。

根据本发明的一个具体实施方式，步骤S2中的依存连贯性约束包括以 下两类：中心词连贯性约束：用来约束源语言端的依存节点f_j在目标语言 端的对齐位置a_j，使得以f_j在依存树上的孩子节点为根节点的依存子树 (通过词对齐)映射到目标端的范围尽量不与a_j产生交叉；依存子树连贯性 约束：用来约束源语言端的依存节点f_j在目标语言端的对齐位置a_j，使 得以f_j在依存树上的兄妹节点为根节点的依存子树(通过词对齐)映射到 目标语言端的范围尽量不与以f_j为根节点的依存子树(通过词对齐)映射 到目标语言端的范围产生交叉。

根据本发明的一个具体实施方式，在步骤S2中，训练一个基于源语 言端或目标语言端依存连贯性约束的词对齐模型的步骤包括：步骤S21、 为所述双语训练集中的每个训练句子对产生一个初始的词对齐结果；步骤 S22、利用当前的词对齐结果和源语言端或目标语言端依存句法树，估计 基于源语言端或目标语言端依存连贯性约束的词对齐模型的参数；步骤 S23、利用当前的词对齐模型参数重新为所述双语训练集中的每个训练句 子对产生一个满足源语言端或目标语言端依存连贯性约束的词对齐结果； 步骤S24、转到步骤S22，反复迭代多次，直到满足停机条件为止；步骤 S25、输出最终的基于源语言端或目标语言端依存连贯性约束的词对齐模 型。

根据本发明的一个具体实施方式，在步骤S22中，基于源语言端或目 标语言端依存连贯性约束的词对齐模型的参数包括：给定源语言端句子及 其依存句法树的条件下，生成词对齐序列和目标语言端句子的条件概率。

根据本发明的一个具体实施方式，所述条件概率为

$p(e_1^I,a_1^J|f_1^J,T_F)=p_l\left(I\right|J)\underset{f_j\in T_F}{\Pi }{p}_d\left(a_j\right|a_{j-1},I,T_F)p_t\left(e_{a_j}\right|f_j),$

其中，表示源语言端J个单词组成的句子(单词序 列)；T_F表示的依存句法树；f_j∈T_F表示源语言端句子中的一个单词， 同时也是依存结构树中的一个节点；表示目标语言端I个 单词组成的句子(单词序列)；为源语言端句子对齐到 目标语言端句子的词对齐序列，其中a_j为一个词对位j→i＝a_j，表示 源语言端第j个词f_j对齐到目标语言端第i(i＝a_j)个词e_i；

p_l(I|J)为长度概率，表示源语言端句长J生成目标语言端句长I的 概率；p_d(a_j|a_j-1，I，T_F)为调序概率，表示给定前一个源语言端单词f_j-1的 对位a_j-1以及源语言端依存句法树T_F的条件下，源语言端单词f_j对齐到 目标语言端a_j位置上的概率；表示翻译概率，表示源语言端单 词f_j翻译为目标语言端单词的概率。

根据本发明的一个具体实施方式，调序概率为

p_d(a_j|a_j-1，I，T_F)＝p_wd(a_j|a_j-1，I)p_hc(a_j|T_F)p_mc(a_j|T_F)

其中，

p_wd(a_j|a_j-1，I)表示词语距离概率，用来约束源语言端单词f_j的对齐 点a_j，使得其前面单词f_j-1的对齐点a_j-1与a_j的距离尽量较小；

p_hc(a_j|T_F)表示中心词连贯性概率，用来约束源语言端单词f_j的对 齐点a_j，使得以f_j在依存句法树T_F上的孩子节点为根节点的依存子树 (通过词对齐)映射到目标语言端的范围尽量不与a_j产生交叉；

p_mc(a_j|T_F)表示依存子树连贯性概率，用来约束源语言端单词f_j的对 齐点a_j，使得以f_j在依存句法树T_F上的兄妹节点为根节点的依存子树(通 过词对齐)映射到目标语言端的范围尽量不与以f_j为根节点的依存子 树(通过词对齐)映射到目标语言端的范围产生交叉。

根据本发明的一个具体实施方式，所述词语距离概率p_wd通过对位之 间的距离(a_j-a_j-1)来估计，即

$p_{\mathrm{wd}}\left(i\right|i^{\prime },I)=\frac{c(i-i^{\prime })}{\underset{i^{\prime \prime }}{\Sigma }c(i^{\prime \prime }-i^{\prime })}$

其中，c(·)表示词语距离的统计计数。我们将所有的词语距离划分为 11份，分别为c(≤-5)，c(-4)，...，c(4)，c(≥5)。

根据本发明的一个具体实施方式，所述中心词连贯性概率p_hc定义为： 以f_h在依存句法树T_F上的孩子节点Children(f_h)为根节点的依存子树(通 过词对齐)映射到目标语言端的范围与a_h交叉情况的概率乘积：

其中，f_c∈Children(f_h)表示fh在依存句法树T_F上的一个孩子节点；和分别表示f_h和f_c对齐到的目标端单词；表 示以f_c为根节点的依存子树映射到目标端的范围与a_h的交叉情况，可以 为“交叉”或者“连贯”之一；p_h表示给定f_h，f_c，的条件下，为“连 贯”或者“交叉”的概率。

根据本发明的一个具体实施方式，所述依存子树连贯性概率p_mc定义 为：以f_m(在依存句法树T_F上)的兄妹节点Siblings(f_m)为根节点的依存子 树(通过词对齐)映射到目标端的范围与以f_m根节点的依存子树(通过 词对齐)映射到目标端的范围交叉情况的概率乘积：

其中，f_s∈Siblings(f_m)表示f_m在依存句法树T_F上的一个兄妹节点； 和分别表示f_m和f_s对齐到的目标端单词；表示分别以f_m和f_s为根节点的依存子树映射到目标端的范围的交叉情 况，可以为“交叉”或者“连贯”之一；p_m表示给定f_m，f_s，的条件下， 为“连贯”或者“交叉”的概率。

根据本发明的一个具体实施方式，在步骤S23中，所述的利用词对齐 模型为训练句子对产生一个满足源语言端或目标语言端依存连贯性约束 的词对齐结果的具体步骤为：按照自底向上的顺序对源语言端或目标语言 端依存句法树中的每个节点进行遍历，并对其中的每个依存节点执行如下 两个步骤：步骤231、针对当前的依存节点，根据依存连贯性约束计算其 对齐到目标语言端或源语言端每个词语的概率；步骤232、根据步骤231 计算的词对齐概率，利用吉布斯采样的方式为当前节点采样一个词语对齐 位置。

根据本发明的一个具体实施方式，在步骤231中针对当前的依存节点 f_j，根据依存连贯性约束计算其对齐到目标语言端或源语言端每个位置 a_j的概率：

$p\left(a_j\right|a_1^{t+1},...,a_{j-1}^{t+1},a_{j+1}^t,...,a_J^t,f_1^J,e_1^I,T_F)=\frac{p(e_1^I,a_1^J|f_1^J,T_F)}{\underset{a_j}{\Sigma }p(e_1^I,a_1^J|f_1^J,T_F)};$

在步骤232中根据上式计算的对齐到目标语言端或源语言端每个词 语的概率，利用吉布斯采样的方式为当前节点f_j采样一个词语对齐位置

$a_j^{t+1}~p\left(a_j\right|a_1^{t+1},...,a_{j-1}^{t+1},a_{j+1}^t,...,a_J^t,f_1^J,e_1^I,T_F).$

根据本发明的一个具体实施方式，在所述步骤S24中，“停机条件” 为整个双语训练集的似然变化不大于一个阈值，或者迭代次数到达一个阈 值。

根据本发明的一个具体实施方式，在步骤S3中，利用基于源语言端 或目标语言端依存连贯性约束的词对齐模型为测试句子对产生一个符合 源语言端或目标语言端依存连贯性约束的词对齐结果的步骤为：按照自底 向上的顺序对源语言端或目标语言端依存句法树中的每个节点进行遍历， 并对其中的每个依存节点执行如下两个步骤：步骤S231、针对当前的依存 节点，根据依存连贯性约束计算其对齐到目标语言端(或源语言端)每个 词语的概率；步骤S232、根据步骤S231计算的词对齐概率，利用吉布斯 采样的方式为当前节点采样一个词语对齐位置。

根据本发明的一个具体实施方式，在步骤S231中针对当前的依存节 点f_j，根据依存连贯性约束计算其对齐到目标语言端或源语言端每个位置 a_j的概率：

$p\left(a_j\right|a_1^{t+1},...,a_{j-1}^{t+1},a_{j+1}^t,...,a_J^t,f_1^J,e_1^I,T_F)=\frac{p(e_1^I,a_1^J|f_1^J,T_F)}{\underset{a_j}{\Sigma }p(e_1^I,a_1^J|f_1^J,T_F)};$

在步骤S232中根据上式计算的对齐到目标语言端或源语言端每个词 语的概率，利用吉布斯采样的方式为当前节点f_j采样一个词语对齐位置

$a_j^{t+1}~p\left(a_j\right|a_1^{t+1},...,a_{j-1}^{t+1},a_{j+1}^t,...,a_J^t,f_1^J,e_1^I,T_F).$

根据本发明的一个具体实施方式，在步骤S3中将两个词对齐结果进 行合并的步骤包括：

步骤S31、计算该两组词对齐的交集A_intersection＝A₁∩A₂，其中A₁、 A₂分别为该两个词对齐结果；

步骤S32、计算该两组词对齐的并集A_union＝A₁∪A₂；

步骤S33、将所述交集A_intersection中的所有词对齐点添加到词对齐集合 A中，即A＝A_intersection，然后，不断地对并集A_union中的每个词对齐点进 行迭代，判断是否将该词对齐点添加到该词对齐集合A中，其中判断的依 据是：如果该词对齐点不在所述集合A中，但与其相邻的对齐点存在于A 中，则将该词对齐点添加到所述集合A中。

(三)有益效果

本发明是使用概率进行评估，对于满足依存连贯性的词对齐候选给予 较高的概率，而破坏了依存连贯性的词对齐候选给予较低的概率，最后选 择一个全局概率较高的词对齐作为最终结果，这样既使得词对齐结果有着 较好的连贯性，又在一定程度上允许少量的破坏连贯性的现象出现，这更 符合真实的词对齐情况。

本发明的训练过程不需要手工标注的双语词对齐语料，而仅仅使用双 语平行语料以及双语句子的依存句法树即可，这些数据相对手工标注语料 来讲是很容易获得的。

附图说明

图1是一个汉语-英语句子对词对齐的实例。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚明自，以下结合具体实 施例，并参照附图，对本发明作进一步的详细说明。

本发明的基于依存连贯性约束的双语词对齐方法是根据一个双语训 练集产生一个词对齐模型，并利用该词对齐模型对测试句子对进行词对 齐。双语训练集包括多个训练句子对，每个训练句子对包括语义相互对应 的一个源语言句子和一个目标语言句子。

本发明的基本思想是利用依存连贯性来约束词对齐的过程，以便很好 地控制每个词语对齐到另外一端的范围，减少冗余，从而提高词对齐质量。 具体来说，本发明训练一个基于源语言端和目标语言端依存连贯性约束的 词对齐模型，并利用该词对齐模型产生关于该测试句子对的满足源语言端 和目标语言端依存连贯性约束的词对齐结果，并将这两个词对齐结果进行 合并，产生一个满足双语依存连贯性约束的词对齐结果。例如，图1给出 了一个汉英词对齐的实例，其中给出了汉语端的依存句法树，黑色格子表 示正确的词对齐。对于汉语词语“有”，我们给出了两个词对齐点，其中 “R”表示正确的词对齐点，“W”表示错误的词对齐点。假设现在要为汉 语词语“有”寻找一个英语端的对齐点。如果不考虑任何句法信息，“有” 可以对齐到英语端15个词语中的任何一个。但是，如果考虑依存连贯性约 束，许多对齐位置将受到限制。例如，对齐的位置为“W”的概率应该较 小，因为此时以“有”为根节点的依存子树映射到英语端的范围为[3，14]， 这与“有”的中心词“之一”映射到英语端的范围[3，4]产生了交叉，破坏 了中心词连贯性约束；相反，当对齐位置为“R”时，以“有”为根节点 的依存子树映射到英语端的范围是[8，14]，这与[3，4]不交叉，完全符合中心 词连贯性约束。

下面我们以汉-英平行句子对作为实施例来详细阐述本发明的原理与 实现方法。

步骤S1、对双语训练集中的每个训练句子对的源语言句子和目标语言 句子进行依存句法分析，得到源语言端的依存句法树和目标语言端的依存 句法树。

如果源语言或目标语言是汉语，则需要在进行依存句法分析之前对训 练句子对中的汉语句子进行分词。如果源语言或目标语言中不包含汉语， 则不需要进行分词。对汉语进行分词的方法有很多种。在本发明的实施例 中，我们用中文分词工具ICTCLAS对汉语进行分词。ICTCLAS中文分词工 具是一个常用的开源中文分词工具，其可以在以下网址免费下载：

http://ictclas.org/ictclas_download.asp。

依存句法分析的方法有多种。在本发明的实施例中，我们使用Berkeley 句法分析器对双语句子进行句法分析，然后将得到的短语结构树通过文献 【Zhiguo Wang and Chengqing Zong，2010.Phrase Structure Parsing with  Dependency Structure.In Coling 2010.】和文献【Zhiguo Wang and Chengqing  Zong，2011.Parse Reranking Based on Higher-Order Lexical Dependencies.In  IJCNLP′11.】所述的方法转化为依存句法树。Berkeley句法分析器是一种 常用的开源句法分析工具，而且是当前最好的句法分析器之一。Berkeley 句法分析器可以从以下的网址免费下载：

http://code.google.com/p/berkeleyparser/。

步骤S2、训练阶段。首先利用双语训练集中的训练句子对和源语言端 的依存句法树，训练一个基于源语言端依存连贯性约束的词对齐模型；然 后，利用双语训练集中的训练句子对和目标语言端的依存句法树，训练一 个基于目标语言端依存连贯性约束的词对齐模型。具体来说，步骤S2的 训练步骤包括：

步骤S21、为双语训练集中的每个训练句子对产生一个初始的词对齐 结果；

步骤S22、利用当前的词对齐结果和源语言端或目标语言端的依存句 法树，估计基于源语言端或目标语言端依存连贯性约束的词对齐模型的参 数；

步骤S23、利用当前的词对齐模型参数重新为所述双语训练集中的每 个训练句子对产生一个满足源语言端或目标语言端依存连贯性约束的词 对齐结果；

步骤S24、转到步骤S22，反复迭代多次，直到满足停机条件为止；

步骤S25、输出最终的基于源语言端或目标语言端依存连贯性约束的 词对齐模型。

根据本发明，步骤S2中的依存连贯性约束包括以下两类：

1)中心词连贯性约束：用来约束源语言端的依存节点f_j在目标语言 端的对齐位置a_j，使得以f_j在依存树上的孩子节点为根节点的依存子树 (通过词对齐)映射到目标端的范围尽量不与a_j产生交叉。

2)依存子树连贯性约束：用来约束源语言端的依存节点f_j在目标语 言端的对齐位置a_j，使得以f_j在依存树上的兄妹节点为根节点的依存子 树(通过词对齐)映射到目标语言端的范围尽量不与以f_j为根节点的依存 子树(通过词对齐)映射到目标语言端的范围产生交叉。

在本实施例中，针对所述步骤S22中基于源语言端或目标语言端依存 连贯性约束的词对齐模型，我们给出如下参数的定义：

给定源语言端句子及其依存结构树T_F的条件下，生成词对齐序列 和目标语言端句子的条件概率为：

$p(e_1^I,a_1^J|f_1^J,T_F)=p_l\left(I\right|J)\underset{f_j\in T_F}{\Pi }{p}_d\left(a_j\right|a_{j-1},I,T_F)p_t\left(e_{a_j}\right|f_j)---\left(1\right)$

其中，表示源语言端J个单词组成的句子(单词序 列)；T_F表示的依存结构树；f_j∈T_F表示源语言端句子中的一个单词， 同时也是依存结构树中的一个节点；表示目标语言端I个 单词组成的句子(单词序列)；为源语言端句子对齐到 目标语言端句子的词对齐序列，其中a_j为一个词对位j→i＝a_j，表示 源语言端第j个词f_j对齐到目标语言端第i(i＝a_j)个词e_i。

式中p_l(I|J)为长度概率，表示源语言端句长J生成目标语言端句长 I的概率；p_d(a_j|a_j-1，I，T_F)为调序概率，表示给定前一个源语言端单词 f_j-1的对位a_j-1以及源语言端依存句法树T_F的条件下，源语言端单词f_j对齐到目标语言端a_j位置上的概率；表示翻译概率，表示源语 言端单词f_j翻译为目标语言端单词的概率。

针对式(1)中的调序概率p_d，可以将其进一步分解为下式：

p_d(a_j|a_j-1，I，T_F)＝p_wd(a_j|a_j-1，I)p_hc(a_j|T_F)p_mc(a_j|T_F)    (2)

其中，

p_wd(a_j|a_j-1，I)表示词语距离概率，用来约束源语言端单词f_j的对 齐点a_j，使得其前面单词f_j-1的对齐点a_j-1与a_j的距离尽量较小；

p_hc(a_j|T_F)表示中心词连贯性概率，用来约束源语言端单词f_j的对 齐点a_j，使得以f_j在依存句法树T_F上的孩子节点为根节点的依存子树(通 过词对齐)映射到目标语言端的范围尽量不与a_j产生交叉；

p_mc(a_j|T_F)表示依存子树连贯性概率，用来约束源语言端单词f_j的对 齐点a_j，使得以f_j在依存句法树T_F上的兄妹节点为根节点的依存子树(通 过词对齐)映射到目标语言端的范围尽量不与以f_j为根节点的依存子 树(通过词对齐)映射到目标语言端的范围产生交叉。

词语距离概率p_wd的出发点是源语言端挨在一起的单词在翻译到目标 语言端时也趋向于挨在一起，因此词语距离概率通过对位之间的距离 (a_j-a_j-1)来估计。

$p_{\mathrm{wd}}\left(i\right|i^{\prime },I)=\frac{c(i-i^{\prime })}{\underset{i^{\prime \prime }}{\Sigma }c(i^{\prime \prime }-i^{\prime })}---\left(3\right)$

其中，c(·)表示词语距离的统计计数。我们将所有的词语距离划分为 11份，即c(≤-5)，c(-4)，...，c(4)，c(≥5)。

中心词连贯性概率p_hc定义为：以f_h在依存句法树T_F上的孩子节点 Children(f_h)为根节点的依存子树(通过词对齐)映射到目标语言端的范 围与a_h交叉情况的概率乘积：

其中，f_c∈Children(f_h)表示f_h在依存句法树T_F上的一个孩子节点；和分别表示f_h和f_c对齐到的目标端单词；表 示以f_c为根节点的依存子树映射到目标端的范围与a_h的交叉情况，可以 为“交叉”或者“连贯”之一；p_h表示给定f_h，f_c，的条件下，为“连 贯”或者“交叉”的概率。

依存子树连贯性概率p_mc定义为：以f_m(在依存句法树T_F上)的兄妹节 点Siblings(f_m)为根节点的依存子树(通过词对齐)映射到目标端的范围 与以f_m根节点的依存子树(通过词对齐)映射到目标端的范围交叉情况 的概率乘积：

其中，f_s∈Siblings(f_m)表示f_m在依存句法树T_F上的一个兄妹节点；和分别表示f_m和f_s对齐到的目标端单词；表 示分别以f_m和f_s为根节点的依存子树映射到目标端的范围的交叉情况， 可以为“交叉”或者“连贯”之一；p_m表示给定f_m，f_s，的条件下，为“连贯”或者“交叉”的概率。

步骤S2所述的基于源语言端或目标语言端依存连贯性约束的词对齐 模型的参数训练过程，我们假设pl服从均匀分布，p_t，p_wd，p_h和p_m服 从多项式分布：

p_t(e|f)～Multi(t_f)

p_wd(i|i′，I)～Multi(wd_i-i′)

其中，t_f表示源语言端单词f翻译为目标语言端每个单词e的概率；wd_i-i′表示词语距离为i-i′的概率；表示给定上下文信息的条件下，中心词 “连贯”和“交叉”的概率；示给定上下文信息的条件下，依存子树之间 “连贯”和“交叉”的概率。

模型参数按照步骤S21到步骤S25的过程进行迭代训练。其中，步骤S21 的初始词对齐结果采用HMM词对齐模型分析得到。步骤S22中利用训练集 当前的词对齐结果统计参数计数n_f、n_i-i′、和进而估计模型参 数。这里我们为这四组参数设置狄利克雷先验：

t_f|n_f，α_f～Dir(n_f+α_f)

wd_i-i′|n_i-i′，α_i-i′～Dir(n_i-i′+α_i-i′)

$h_{{\xi }_h}|n_{{\xi }_h},{\alpha }_{{\xi }_h}~\mathrm{Dir}(n_{{\xi }_h}+{\alpha }_{{\xi }_h})$

$m_{{\xi }_m}|n_{{\xi }_m},{\alpha }_{{\xi }_m}~\mathrm{Dir}(n_{{\xi }_m}+{\alpha }_{{\xi }_m})---\left(7\right)$

步骤S23所述的利用词对齐模型为训练句子对产生一个满足源语言端 或目标语言端依存连贯性约束的词对齐结果的具体步骤为：按照自底向上 的顺序对源语言端或目标语言端依存句法树中的每个节点进行遍历，并对 其中的每个依存节点执行如下两个步骤：

步骤231、针对当前的依存节点，根据依存连贯性约束计算其对齐到 目标语言端(或源语言端)每个词语的概率；

步骤232、根据步骤231计算的词对齐概率，利用吉布斯采样的方式 为当前节点采样一个词语对齐位置。

具体来说，步骤231针对当前的依存节点f_j，根据依存连贯性约束计 算其对齐到目标语言端或源语言端每个位置a_j的概率：

$p\left(a_j\right|a_1^{t+1},...,a_{j-1}^{t+1},a_{j+1}^t,...,a_J^t,f_1^J,e_1^I,T_F)=\frac{p(e_1^I,a_1^J|f_1^J,T_F)}{\underset{a_j}{\Sigma }p(e_1^I,a_1^J|f_1^J,T_F)}---\left(8\right)$

步骤232根据式(8)计算的对齐到目标语言端或源语言端每个词语的 概率，利用吉布斯采样的方式为当前节点fj采样一个词语对齐位置

$a_j^{t+1}~p\left(a_j\right|a_1^{t+1},...,a_{j-1}^{t+1},a_{j+1}^t,...,a_J^t,f_1^J,e_1^I,T_F)---\left(9\right)$

步骤S24中的“停机条件”可以是整个双语训练集的似然变化不大于 一个阈值，或者迭代次数到达一个阈值。在本发明的该实施例中，设定为 最大迭代次数为12次。当迭代次数小于12次时，如果整个训练集的似然变 化小于1E-6则停止迭代；否则当迭代次数大于12次时停止迭代。

步骤S3、测试阶段。首先利用基于源语言端依存连贯性约束的词对齐 模型为测试句子对产生一个符合源语言端依存连贯性约束的词对齐结果； 然后，利用基于目标语言端依存连贯性约束的词对齐模型为测试句子对产 生一个符合目标语言端依存连贯性约束的词对齐结果；最后，将这两个词 对齐结果进行合并，产生一个兼顾准确率和召回率的满足双语依存连贯性 约束的词对齐结果。

步骤S3中利用基于源语言端依存连贯性约束的词对齐模型为测试句 子对产生一个符合源语言端依存连贯性约束的词对齐结果，以及利用基于 目标语言端依存连贯性约束的词对齐模型为测试句子对产生一个符合目 标语言端依存连贯性约束的词对齐结果，其具体步骤与步骤S23相类似， 即按照自底向上的顺序对源语言端或目标语言端依存句法树中的每个节 点进行遍历，并对其每个依存节点执行步骤S231和步骤S232。

步骤S3中基于依存连贯性约束的词对齐模型最多只允许一个单词与 依存句法树上的一个节点对齐，这势必会影响词对齐的召回率(recall)， 例如在图1中，“之一”节点应该与两个英语单词“one of”对齐，但利用该模 型分析的词对齐结果，仅仅允许一个单词与“之一”对齐。针对该问题，分 别利用基于源语言端依存连贯性约束的词对齐模型和基于目标语言端依 存连贯性约束的词对齐模型，对测试句子生成两个分别符合源语言依存连 贯性约束的词对齐结果A₁和符合目标语言依存连贯性约束的词对齐结果 A₂，最后将两个词对齐结果进行合并。合并的步骤为：

步骤S31：计算两组词对齐的交集A_intersection＝A₁∩A₂。这样得到的词 对齐的准确率(Precision)最高，但召回率却很低；

步骤S32：计算两组词对齐的并集A_union＝A₁∪A₂。这样得到的词对齐 的召回率最高，但准确率却很低；

步骤S33：首先，将交集A_intersection中的所有词对齐点添加到词对齐集 合A中，即A＝A_intersection。然后，不断地对并集A_union中的每个词对齐点(i， j)进行迭代，判断是否应该将(i，j)添加到词对齐集合中A。判断的依据是： 如果对齐点(i，j)不在A中，但与其相邻的对齐点(i-1，j)，(i+1，j)，(i，j-1)， (i，j+1)，(i-1，j-1)，(i-1，j+1)，(i+1，j-1)或(i+1，j+1)存在于A中，则将(i，j) 添加到A中，即A＝A∪{(i，j)}。最后，A便是一个兼顾准确率和召回率 的满足双语依存连贯性约束的词对齐结果。

下面通过对根据上述实施例的方法进行实验来检验本发明的可行性 及所能取得的预期技术效果。

实验中，使用FBIS中英平行语料库作为双语训练集，其中包含235,669 个中英句子对(训练句子对)；采用一个手工标注的词对齐语料作为测试 集，其中包含504个中英句子对(测试句子对)。手工标注的语料中含有两 种类型的词对齐点，分别是：确定型词对齐点S(sure)和可能型词对齐点 P(possible)。确定型词对齐点S是可能型词对齐点P的子集。我们采用词 对齐错误率(AER)来评价词对齐的质量，假设词对齐系统输出的词对齐 点用A表示，则AER可以定义为：

$\mathrm{AER}(S,P,A)=1-\frac{|A\cap S|+|A\cap P|}{A\cap S}$

很显然，AER越小表示词对齐质量越高。此外，根据文献【Heidi J.Fox，2002. Phrasal cohesion and statistical machine translation.In EMNLP′02，pages 304-311.】，我们还采用另外两个指标来评价词对齐的依存连贯性，它们分 别为中心词交叉百分比(HCP)和依存子树交叉百分比(MCP)。显然， HCP和MCP越小表示词对齐的依存连贯性越好。

为了进一步验证发明中所述词对齐方法对机器翻译的影响，我们还使 用开源的基于短语的统计翻译系统Moses【P.Koehn，H.Hoang，A.Birch，C. Callison-Burch，M.Federico，N.Bertoldi，B.Cowan，W.Shen，C.Moran and R. Zens，2007.Moses：Open source toolkit for statistical machine translation.In  ACL′07，Demonstration Session，pages 177-180.】进行机器翻译的实验。我 们使用国际机器翻译评测(NIST MT Evaluation)中从2003年至2005年的 所有测试集MT03-MT05作为开发集和测试集，其中MT03作为我们的开发 集，用来优化各个翻译特征的权重，MT04和MT05作为测试集。在目标语 言模型的训练中，我们采用开源的SRILM语言模型训练工具【A.Stolcke， 2002.SRILM-an extensible language modeling toolkit.In IC SLP′02.】。除了用 双语训练数据的目标语言部分外，还加入了英语Gigaword语料中Xinhua部 分约181，1000,000个单词，最终训练了一个5元语法的语言模型。我们 使用大小写不敏感的BLEU-4【Papineni，Kishore.，Roukos，Salim，Ward， Todd，and Zhu Wei-Jing.2002.BLEU：a method for automatic evaluation of  machine translation.In Proc.of ACL.】作为机器翻译质量的评测指标。

附表1给出了不同的词对齐模型在测试集上的词对齐结果。其中，ch-en 表示基于汉语依存连贯性约束的词对齐结果，en-ch表示基于英语依存连贯 性约束的词对齐结果；AER表示词对齐错误率，HCP表示中心词交叉百分 比，MCP表示依存子树交叉百分比；wd表示不使用依存连贯性约束的词对 齐结果，wd-hc表示仅使用中心词连贯性约束的词对齐结果，wd-mc表示仅 使用依存子树连贯性约束的词对齐结果，wd-hc-mc表示同时使用中心词连 贯性约束和依存子树连贯性约束的词对齐结果，IBM4表示GIZA++中IBM 模型4的词对齐结果，Gold-Standard表示手工标注语料的词对齐结果。

从附表1可以看出：1)当采用中心词连贯性约束wd-hc时，词对齐错 误率AER的值比起不使用任何连贯性约束wd时有所下降；2)当采用依存 子树连贯性约束wd-mc时，词对齐错误率AER的值比起不使用任何连贯性 约束wd时也有所下降；3)当既采用中心词连贯性约束又采用依存子树连 贯性约束wd-hc-mc时，词对齐错误率AER有了大幅的下降。这证明了中心 词连贯性约束和依存子树连贯性约束对词对齐质量的提高十分有帮助。另 外，从附表1中我们还可以发现，中心词连贯性约束对降低HCP很有帮助， 依存子树连贯性约束对降低MCP很有帮助，而同时采用中心词连贯性约束 和依存子树连贯性约束时输出的词对齐结果既具有最好的AER，又获得了 较好的HCP和MCP。

在附表1中我们还与目前应用的最为广泛的IBM模型4做了比较。可以 看到，我们的系统在各个指标上都大大优于IBM4。另外还可以看到，由 wd-hc-mc输出的词对齐结果的HCP和MCP与手工标注的语料十分接近，这 进一步证明了本发明的有效性和合理性。

附表2中列出机器翻译实验的相关结果。其中IBM4表示通过GIZA++ 中IBM模型4输出的词对齐结果训练的机器翻译模型的翻译结果，wd-hc-mc 表示通过本发明输出的词对齐结果训练的机器翻译模型的翻译结果。从中 可以看到，本发明输出的词对齐结果对机器翻译质量有较大的提高，其中 在MT04测试集上提高了0.82个BLEU值。

总之，实验结果表明本发明的基于依存连贯性约束的双语词语自动对 齐方法对提高词对齐质量很有效，同时利用本发明输出的词对齐结果进行 机器翻译模型的训练也可以大幅提高机器翻译的质量。

附表1：词对齐结果比较。

附表2：机器翻译结果比较。

  MT04   MT05   IBM4   31.09   28.97   wd-hc-mc   31.91   29.49

由于本发明的方法不是针对两种特定的语言而提出的，所以本发明的 方法具有普遍的适用性。本发明虽然只在汉语和英语两种语言上进行了实 验，但本发明同时也适用于其它语言对，如日语和汉语、阿拉伯语和英语。

综上所述，本发明并不是将破坏了依存连贯性的词对齐候选直接进行 删除，而是使用概率进行评估：对于满足依存连贯性的词对齐候选给予较 高的概率，而破坏了依存连贯性的词对齐候选给予较低的概率，最后选择 一个全局概率较高的词对齐作为最终结果。这样既使得词对齐结果有着较 好的连贯性，又在一定程度上允许少量的破坏连贯性的现象出现，这更符 合真实的词对齐情况。另外，本发明的训练过程不需要手工标注的双语词 对齐语料，而仅仅使用双语平行语料以及双语句子的依存句法树即可，这 些数据相对手工标注语料来讲是很容易获得的。在汉语-英语词对齐任务上 进行的实验显示：本发明得到的词对齐错误率较GIZA++工具包中的IBM 模型4降低了6个百分点。在国际机器翻译评测(NIST MT Evaluation) 中英任务上进行的机器翻译的实验显示：利用本发明得到的词对齐结果训 练得到的机器翻译模型比利用IBM模型4得到的词对齐结果训练的模型 提高了0.8个BLEU值。

以上所述的具体实施例，对本发明的目的、技术方案和有益效果进行 了进一步详细说明，应理解的是，以上所述仅为本发明的具体实施例而已， 并不用于限制本发明，凡在本发明的精神和原则之内，所做的任何修改、 等同替换、改进等，均应包含在本发明的保护范围之内。