基于加权二部图的汉日词对齐

摘 要：高效的自动词对齐技术是词对齐语料库建设的关键所在。当前很多词对齐方法存在以下不足：未登录词问题、灵活翻译问题和全局最优匹配问题。针对以上不足，该文提出加权二部图最大匹配词对齐模型，利用二部图为双语句对建模，利用词形、语义、词性和共现等信息计算单词间的相似度，利用加权二部图最大匹配获得最终对齐结果。在汉日词语对齐上的实验表明，该方法在一定程度上解决了以上三点不足，F-Score为80％，优于GI-ZA＋＋的72％。

关键词：计算机应用；中文信息处理；词对齐；二部图；匹配

中图分类号：TP391　文献标识码：A

1　引　言

语料库的单词级对齐，也称词对齐，就是在双语句对中把每个单词和它的译文建立对应关系。这对充分发掘语料库的功能起着十分重要的作用，是获取翻译模板，构造概率词典和语义消歧中的关键技术。

现有的词对齐方法，主要可分为两大类：统计方法和语言学方法。统计方法又称为基于语料库的方法，利用从语料库中获得的信息进行词对齐。语言学方法又称为基于知识的方法，利用各种语言学资源分析单词间的相关性。涉及汉语的词对齐研究主要针对汉英之间，利用词典和统计相结合的方法进行词对齐；研究了在训练语料库规模较小的情况下，充分利用现有资源，改良词对齐结果针对汉英词对齐特点，考察了不同的词对关联度量在汉英词对抽取工作中的表现；利用集合论的方法进行英汉词对齐。

这些现有的方法中，以下几点不足对词对齐的结果存在负面影响，它们分别是：未登录词问题、灵活翻译问题和全局最优匹配问题。未登录词问题：在真实文本中存在着大量的未登录词。现有的词对齐技术一般都用统计方法解决此问题。数据稀疏导致这些方法的效果很差；灵活翻译问题：自然语言的翻译是很灵活的，双语字典的有限性和自然语言的灵活性是一对无法避免的矛盾；全局最优匹配问题：很多现有的词对齐技术在匹配时只能达到局部最优，无法获得全局最优解。

针对以上三点不足，本文提出一种基于加权二部图最大匹配的词对齐模型。在此模型中，利用加权二部图为双语句对建模，利用词形、语义、词性和共现等信息计算单词间的相似度，利用加权二部图最大匹配获得最终的对齐结果。

2 词对齐模型

本文提出的词对齐模型，利用加权二部图为要进行词对齐的双语句对建模，用加权二部图中的节点表示双语句对中的单词；节点之间的权重为单词之间的相似度，该相似度利用词形相似度(Morphology Similarity-SimM)、语义相似度(SemanticSimalatity-SimS)、词性相似度(Part of Speech Similarity-SimP)和共现度(Co-occurrence-Cooc)等信息计算；利用加权二部图最大匹配获得最终的对齐结果。

2．1　建　模

在本文的词对齐模型中，句子用单词的集合来表示。中文句子和日文句子分别表示成集合C＝{c1，c2，…，cm}和集合J＝{j1，J2，…，Jn}。双语句对用加权二部图G＝(V，E)表示。其中y＝CUJ是二部图中节点的集合，E＝{ehk|l≤h≤m，l≤k≤n}是连接各节点的边的集合。

上下两组节点分别表示中文单词和日文单词。ehk表示连接节点中文单词ch和日文单词了jk的边，是带权重的边，其权重为汉语单词ch和日语单词了jk间的相似度。相似度的计算方法在下一小节中给出。

2．2 相似度计算

在这一小节中，利用词形相似度、语义距离、词性和共现等信息计算中文单词和日文单词之间的相似度。

Sim(c，j)表示中文单词c和日文单词j的相似度，按如下公式计算：

双语字典是计算双语单词间相似度的最直接最可靠的工具。SimD(c，j)用来衡量中文单词C和日文单词j的字典相似度。当‘和了在双语字典中互译时SimD(c，j)＝1；否则SireD(c，j)＝0。当SimD(c，j)＝0时，我们就需要利用其他信息来计算相似度，如：词形相似度(SimM)、语义距离(SimS)、词性(SimP)和共现信息(Cooc)，各项具体的计算方法如下：

a)词形相似度(SimM)

日文汉字是由中文汉字演变而来，它们在字形上有很高的相似度。统计显示，超过一半的日文单词包含日文汉字，28％的日文单词全部由日文汉字组成。因此，我们认为中文单词和日文单词在字形层面的相似度可以发挥重要的作用。中文字符集(包括简体和繁体)和日文字符集包含很多相同的字符。我们就利用这些相同的字符建立中文单词和日文单词之间的相似关系。

我们假设，如果一个中文单词和一个日文单词包含相同的字符，那么他们趋向于互译。为了验证这个假设，分别利用汉日双语字典和汉日双语词对齐语料库设计了两个实验。

我们使用的双语字典包含43 072个词条，通过检查我们发现，有15970个词条的汉语部分和日语部分之间包含相同的字符，占总数的37％。

另外，针对词对齐语料库，我们设计了如下实验。在互为译文的双语句对中，我们计算任意中文单词ck和日文单词jk的Dice系数(以字符为单位计算)；在整个语料库中统计结果；检验“ch和jk是否对齐”与“ch和jk之间的Dice系数是否大于0”的统计相关性。表1是相关的统计结果。

相关系数r＝0.64的结果，说明了“ck和jk是否对齐”与“ch和jk之间的Dice系数是否大于0”相关的显著性。

以上两个实验验证了“如果一个中文单词和一个日文单词包含相同的字符，那么他们趋向于互译”的假设。因此，我们引入词形相似度SimM(c，j)，用于计算中文单词c和日文单词j之间的相似度：

其中，字符串c*是将中文单词c转换为繁体字串的结果。在考虑简体汉字的同时，我们将繁体汉字作为一个中介，建立简体汉字和日文汉字之间的联系。公式(3)用类似Dice系数的形式，同时利用简体汉字和繁体汉字信息。

b)语义相似度(SimS)

SimS(c，j)从语义距离角度衡量中文单词c和日文单词j之间的相似度，计算方法如下：

其中，Dict(c)为中文单词c在双语字典中的日 文译词的集合，Distance(e，j)是Dict(c)中的某个日文译词e与曰文单词j之间的语义距离。目前有多种计算语义距离的方法，可以任选一种方法归一化后应用于SimS(c，j)的计算。

c)词性(SimP)

SimP(c，j)从词性角度衡量中文单词c和日文单词j之间的相似度，计算方法如下：

Cooc(c，j)利用共现信息衡量中文单词c和日文单词j之间的相似度。有多种共现模型可用来计算Cooc(c，j)，如：X2、Dice系数等。

2．3 匹配

在上一小节中，我们计算了任意一对中文单词和日文单词之间的相似度Sim(c，j)，相当于获得了二部图中每条边的权重。接下来，我们提出两个匹配方法，用来获得最终的对齐结果。

定义1：二部图G＝(CUJ，E)的一个匹配M，是G中边的集合E的子集，且M中的任何两条边在G中都不相邻(即没有共同的节点)。用M(G)表示二部图G的匹配。

定义2：二部图G的最大权重匹配MWM，是G的所有匹配中，边的权重之和最大的匹配。用MMax(G)表示二部图G的最大权重匹配。

在本文的模型中，词对齐可看作是获取二部图最大权重匹配(MWM)。匹配方法如下：

匹配方法A.1：对于待对齐的用加权二部图G＝(CUJ，E)表示的汉日双语句对，去除边的集合E中所有权重小于θA的边。θA是一个经验阈值，用于过滤统计噪声。得到的新的边的集合用E*＝{ehk|ehk∈E，whk≥θA}表示。用E*构造新的二部图G*＝(CUJ，E*)。根据公式(6)计算二部图G*的最大权重匹配MMAX(G*)(可用Hungarian Algorithm实现)。MMAX(G*)即为最终的对齐结果。

根据二部图匹配的定义，任何两条边都没有共同的节点，这使得匹配方法A.1的结果限制在1-1类型的对齐范围内。由于在真实文本中存在一定比例的m-n型词对齐，我们对匹配方法A.1进行了扩展。通过分析对齐的内部结构，我们提出了匹配方法A.2。可解决一部分m-n对齐问题，并可以提高召回率。

匹配方法A.2：对于待对齐的用二部图G＝(CUJ，E)表示的汉日双语句对，首先利用对齐方法A.1获取MMAX(G*)；然后根据公式(7)获取MM(G)：

MM(G)＝{ehk|ehk∈E，SimM(ch，jk)≥θM}(7)

MM(G)是E的子集，它包含E中所有词形相似度(SimM)不小于阈值θM的边。根据2.2小节的分析，MM(G)中所包含的边有非常高的可信度。我们将这些边作为最终的对齐结果的一部分。相似地，我们根据和公式(8)获取MS(G)：

MS(G)＝{ehk|ehk∈E，Sims(ch，jk)≥θS} (8)

最后，根据公式(9)获取MA.2(G)：

MA.2(G)＝MMax(G*)U MM(G)UMS(G)　(9)

在公式(9)中，构成并集的每个子集中的边都有着很高的可信度，并且它们是从不同的角度去挖掘中文单词和日文单词之间的相似性。因此，匹配方法A.2所做的扩展，可以以很小的降低准确率的代价，大幅度提高召回率。我们把MA.2(G)中的边作为最终的对齐结果输出。

4 实验结果及分析

4．1 实验设计

在实验中，我们使用了汉日句对齐双语语料库、汉日双语字典和EDR语义字典等资源。

我们从汉日句对齐双语语料库中随机抽取了100个句对，作为测试集；剩余部分作为训练集(约15000个句对)。语料的平均长度为33．2个词，共包含511 326个单词，不同的词形共24 304个。

为了评价本文提出的词对齐模型，我们构造了7个词对齐系统(WA_la，b，c，d，e and WA_2a，b)和三个比照系统(Baselinel，Baseline2 and GIZA＋＋)。

Baselinel只使用双语词典信息(SireD)进行词对齐；WA_1a、WA_1b和WA_1c是在Baselinel的基础上，分别引入了3.2节中介绍的利用词形相似度(SimM)、语义相似度(SimS)和词性相似度(SimP)信息进行词对齐；WA_1d只利用共现度信息(Cooc)进行词对齐，用X2计算共现度；WA_1e则引入了本文提出的所有相似度计算方法。在实验1中，我们对比以上系统，以评估本文的相似度计算方法。

Baseline2、WA_2a和WA_2b采用了本文的全部相似度计算方法，它们的不同之处在于所采用的匹配策略不同。Baseline2采用了CompetitiveLinking匹配方法；WA_2a and WA_2b分别使用了3.3节中提出的匹配方法A.1和匹配方法A.2。在实验2中，我们对比以上系统，以评估本文的匹配方法。同时，我们也将性能最好的系统WA_2b与GIZA＋＋作比较，对本文的模型进行整体评价。

我们人工编写了标准答案，评估各个系统的召回率、准确率和F-Score。

4．2 实验结果和分析

表3给出了实验1的结果：

通过表3，我们发现WA_1a系统的F-Score达到0.69，远高于Baselinel的0.54。这是由于我们引入了词形相似度(SimM)，使很多未登录词被正确对齐。由于汉语和日语共享很多字符，人们在进行汉日之间的翻译时，倾向于使用字形相同的汉语和日语的字符，特别是翻译命名实体时，这种倾向更加明显。SimM可以发现几乎所有的有字形层面上的关联的汉日翻译对，因此引入SimM后，对齐的召回率大幅度提高。

我们同时发现，WA_1b系统的F-Score达到 0.58，比Baselinel的0.54略有提高。这是由于我们引入了语义相似度(SimS)。对于真实文本，各个单词的翻译并不局限于字典的义项，使用双语字典只能对齐一小部分单词，因此Baselinel的召回率仅有0.38。而引入了语义相似度SimS后，WA_1b系统可以利用同义词信息，对齐一些翻译灵活的汉日翻译对。

WA_lc系统的F-Score达到0.58．WA_1d系统的F-Score达到0.69，分别反映了利用词性相似度(SimP)和利用共现信息对词对齐性能的改善。

WA_1e系统引入了本文提出的所有相似度计算方法，它的F-Score达到了0.80，比Baselinel提高了26％，充分验证了本文的相似度计算方法的有效性。

表4给出了实验2的结果，通过表4，我们发现WA_2b系统的F-score比Baseline2提高了3％，这是由于我们在WA_2b系统中引入了本文的二部图最大权重匹配，获得了全局最优解。

Baseline2的匹配方法为Competitive Linking，采用“best-first”的搜索策略。这种方法只能得到局部最优解，由此造成对齐准确率下降。下面以来源于真实语料的一个句对为例说明。该句对为：“亚军/被/美国/人/夺得”“yメダル/ば/アメリカ/人/に/取ち/れる/た”。表5列出了经本文第2.2节所述方法进行相似度计算的部分结果。(注：日文中的助词“は”和“に”不参加计算。)

在表5中，按着Baseline2的匹配方法Competitive Linking，按单词之间的相似度从大到小选择了下列链接作为对齐：“美国-ァメリカ”、“人-人”、“被-れる”、“夺得-yメタル”、“亚军-に”。在这个结果中，“夺得-yメタル(银牌)”、“亚军-に(日文时态助词)”这两个对齐是错误的。该错误是由于Baseline2的匹配方法的缺陷造成的。Baseline2的匹配方法从大到小依次选择链接，没有考虑全局信息；如果一个链接被错误的选择，会对以后的处理造成影响，无法补救。而使用本文提出的匹配方法，得到的是全局最优解。在上例中，相似度加和最大的“亚军-yメタル”、“被-れる”、“美国-アメリカ”、“人-人”、“夺得-取る”被选为最终的对齐结果。因此，使用了这种匹配方法的WA_2b系统的实验结果优于Baseline2系统。

通过表4，我们还发现WA_2b系统的F-score高于WA_2a系统(提高了6％)。这是由于我们对WA_2a系统使用的匹配方法A.1进行了改进，设计了匹配方法A.2。匹配方法A.1只能获取1-1的对齐，无法召回m-n对齐。我们扩展了A.1，联合MMAX(G*)、MM(G)和MS(G)得到匹配方法A.2。通过实验1我们已经知道MM(G)和MS(G)的准确率都是非常高的，并且它们是从不同的角度去挖掘中文单词和日文单词之间的相似性。因此，A.2对匹配方法的扩展，以极小的代价(准确率降低3％)极大地提升了召回率(提高12％)。

通过实验结果我们发现，在所有参加比对的1。个系统中，WA_2b系统的性能是最高的。它的FScore达到80％，高于词对齐任务的通常的比对系统GIZA＋＋的72％的结果。WA_2b系统集成了本文提出的所有词对齐技术，这样的实验结果也有力地证明了本文方法的有效性。

5 结　论

本文提出加权二部图最大匹配词对齐模型。该模型利用二部图为双语句对建模，利用词形、语义、词性和共现等信息计算单词间的相似度，利用加权二部图最大匹配获得最终对齐结果。实验表明，该方法在一定程度上解决了当前很多词对齐方法存在的未登录词问题、灵活翻译问题和全局最优匹配问题等不足。在所有参加比对的10个词对齐系统中，集成了本文提出的全部词对齐技术的系统的FScore达到80％，高于词对齐任务的通常的比对系统GIZA＋＋的72％的结果。这些实验结果有力地证明了本文方法的有效性。

本文提出的词对齐方法，是我们探索词对齐问题的一系列努力的第一步。为了进一步提高性能，特别是提高对m-n类型的词对齐的处理能力，在以后的研究中，本方法可进行如下改进：引入新的衡量单词间相似度的特征(如语音学特征等)、改进匹配方法以适应m-n型对齐(如对公式(7)、(8)、(9)增加限制条件等。