肖 桐，李天寧，陳如山，朱靖波，王會珍

(東北大學 自然語言處理實驗室，遼寧 沈陽 110004)

1 引言

詞對齊是統(tǒng)計機器翻譯的重要組成部分[1]。通常情況下高質(zhì)量的詞對齊結(jié)果可以帶來統(tǒng)計機器翻譯系統(tǒng)翻譯性能的提高[2-3]?，F(xiàn)在大多數(shù)統(tǒng)計機器翻譯系統(tǒng)都是利用IBM models[4]來進行詞對齊。但是在IBM models中一個源語言單詞最多只允許對應一個目標語單詞。因此IBM models生成的詞對齊一般也被稱作非對稱的詞對齊。為了獲得對稱的詞對齊，需要利用IBM models得到源語言→目標語言(正向)和目標語言→源語言(反向)雙向?qū)R的結(jié)果，之后在雙向?qū)R的基礎上自動得到對稱的詞對齊結(jié)果。在這個過程中，一個關(guān)鍵的問題就是解決雙向?qū)R的不一致性。圖1展示了一個在真實數(shù)據(jù)中由IBM models生成的雙向詞對齊的實例。在這個實例中，源語言單詞“歐盟”和目標語單詞“Europe”在正反雙向詞對齊中均被對應上，于是我們稱雙向詞對齊在“歐盟”和“Europe”之間的對齊上是相交的或一致的。相反，“歐盟”和“Union”在反向詞對齊中被對應上，而在正向詞對齊中卻沒有被對應上。這時我們稱雙向詞對齊在“歐盟”和“Union”之間的對齊上是有歧義的或不一致的。對于這種情況，我們需要判斷“歐盟”和“Union”是否在最終的詞對齊結(jié)果中被對齊。在本文中，我們稱片斷對(“歐盟”, “Europe Union”)有相交型歧義，而(“歐盟”, “Europe Union”)被稱為相交型歧義塊。

圖1 正反雙向詞對齊實例

通常情況下，不一致的詞對齊是頻繁出現(xiàn)的(比如在我們的漢英翻譯實驗中有超過50%的詞對齊鏈接在雙向詞對齊中是不一致的)，因此提高相交型歧義塊中的詞對齊的準確率將會有助于最終詞對齊準確率的提高。對于這個問題，現(xiàn)在廣泛采用的解決辦法是，利用啟發(fā)信息來判斷有歧義的對齊的正確性[1-2]。但是由于這個方法只考慮了錨點(比如：雙向?qū)R的交集部分)和對齊點的相對位置信息，它更適用于翻譯順序相對一致的語言對，如：法語英語。而在語序差異極大的語言之間，經(jīng)常會出現(xiàn)翻譯的遠距離調(diào)序現(xiàn)象，比如：漢語英語之間的遠距離調(diào)續(xù)。這時僅使用啟發(fā)信息并不能得到很好的對齊結(jié)果。針對這個問題，本文提出了一個對相交型歧義塊進行重新對齊的方法。它使用了翻譯概率，扭曲度概率和產(chǎn)出率概率等多個特征共同作用來得到對稱化的詞對齊結(jié)果。此外，本文還對這個方法進行了改進，使它能夠利用大規(guī)模單語語料得到更好的詞對齊結(jié)果。

為了檢驗本文提出的方法的有效性，我們把它應用到基于短語的統(tǒng)計機器翻譯系統(tǒng)中。在漢英翻譯任務上的實驗結(jié)果表明，本文提出方法要優(yōu)于現(xiàn)在廣泛使用的基于啟發(fā)信息的方法。此外，我們的實驗結(jié)果還表明使用單語語料有助于進一步提高詞對齊的性能。

2 問題描述

2.1 詞對齊形式化描述

假設f=f1f2…fJ和e=e1e2…eI分別表示源語和目標語詞序列，其中J和I表示序列長度。f和e之間的詞對齊可以表示為一個函數(shù)a:J×I?(0,1)，對于任意(j,i) (1≤j≤J∧1≤i≤I)有：當fj和ei之間有對齊關(guān)系，a(j,i)=1；否則a(j,i)=0。在本文中我們稱a(j,i)為對齊函數(shù)。對于任意一個(j,i)，如果a(j,i)=1，我們稱(j,i)為一個對齊鏈接。如果有兩個對齊函數(shù)a1和a2滿足對任意的(j,i)，都有a1(j,i)≤a2(j,i)，我們稱a1?a2*這里我們借用了集合的飽含關(guān)系的表示方法。這里我們把一個對齊函數(shù)中滿足a(j, i)=1的所有(j, i)看成一個集合。?？紤]詞對齊的方向，我們使用af→e(j,i)表示從f到e的詞對齊函數(shù)(正向詞對齊)，ae→f(j,i)表示從e到f的詞對齊函數(shù)(反向詞對齊)。在此基礎上，我們定義正反雙向詞對齊的并集為aunion，它滿足aunion(j,i)= 1 iffaf→e(j,i) = 1∨ae→f(j,i)=1；正反雙向詞對齊的交集為ainter，它滿足ainter(j,i)=1 iffaf→e(j,i)=1∧ae→f(j,i)=1。

2.2 相交型歧義塊定義

在給出相交型歧義塊的定義之前，我們先給出塊(block)的定義。假設fj1…fj2和ei1…ei2分別是f和e中的兩個詞序列，aunion為(f,e)之間正反雙向詞對齊的并集，如果

(1)

我們稱序偶(fj1…fj2,ei1…ei2)是一個翻譯對或塊，并把它表示成B(fj1…fj2,ei1…ei2)。這個定義意味著(fj1…fj2,ei1…ei2)中沒有詞被對齊到(fj1…fj2,ei1…ei2)以外?？梢钥闯鲞@個定義本質(zhì)上與基于短語的統(tǒng)計機器翻譯[1]中的短語對的定義是一致的。

給定正反雙向詞對齊af→e，ae→f和一個塊B(fj1…fj2,ei1…ei2)，如果有一個(j,i) (j1≤j≤j2∧i1≤i≤i2)滿足af→e(j,i)=1∧ae→f(j,i)=1，我們稱af→e(j,i)和ae→f(j,i)在(j,i)上是相交的或一致的。如果af→e(j,i)≠ae→f(j,i)，我們稱fj和ei之間的對齊鏈接有(相交型)歧義。如果B(fj1…fj2,ei1…ei2)包含歧義鏈接，而且B(fj1…fj2,ei1…ei2)中沒有其他塊包含歧義鏈接，我們就稱B(fj1…fj2,ei1…ei2)為相交型歧義塊(Overlapping Ambiguous Block，OAB)，并把它記為OAB(fj1…fj2,ei1…ei2)。實際上，OAB的定義保證了任意一個OAB不能嵌套地包含其他OAB，而且與其他任何OAB都不相交。例如，在圖1中所示的對齊實例中包含兩個OAB：OAB(“歐盟”,“Europe Union”)和OAB(“盧森堡市”, “Luxembourg”)。

2.3 重對齊

在本文中，重對齊是指根據(jù)正反雙向詞對齊的結(jié)果重新對雙語句對進行對齊，以得到完整的對稱化的詞對齊結(jié)果。顯然，對于雙語句對中的非OAB的部分來說重對齊是比較簡單的，因為我們只需把雙向詞對齊的交集部分作為最終的對齊結(jié)果即可。而對于OAB來說，重對齊任務要難得多，因為我們要對其中的每個歧義鏈接進行消歧。而本文的工作也正是集中在對OAB的重對齊任務上。在這個任務中有如下兩個問題需要解決：

a) 給定雙語句對(f,e)和它們之間的正反雙向詞對齊結(jié)果，如何得到所有的OAB。

b) 如何定義OAB上最優(yōu)的詞對齊，如何高效地搜索最優(yōu)詞對齊。

我們把第一個問題稱作相交歧義塊識別問題，把第二個問題稱作OAB的重對齊問題。

3 相交歧義塊識別

根據(jù)OAB的定義，我們給出了一個能夠得到所有OAB的OAB快速識別算法。

輸入: 雙語句對(f, e)和正反雙向詞對齊結(jié)果af→e和ae→f輸出: (f, e)包含的所有OABStep1: 得到所有歧義鏈接,把它們保存在ambilink[0…l]中Step2: fork=0 to l-1 do if Checked(f[ambilink[k].j]) do next FSegStart=FSegEnd=ambilink[k].j ESegStart=ESegEnd=ambilink[k].i FoundOABFlag=false while notFoundOABFlagdo Step2.1: 根據(jù)ae→f,ESegStart,ESegEnd和e更新FSegStart和FSegEnd Step2.2: 根據(jù)af→e,FSegStart,FSegEnd和f更新ESegStart和ESegEnd Step2.3: 如果無更新,把FoundOABFlag設為true 把B(FSegStart, FSegEnd, ESegStart, ESegEnd)存入OABList 把f[FSegStart...FSegEnd] 標記為“checked”Step3: fori=0 to OABList.length-1 do if OABList[i]沒有被OABList中的其他元素覆蓋do輸出OABList[i]

這個算法的核心思想是，根據(jù)每個歧義鏈接進行擴展，直到得到包含它的OAB。算法中的Step2.1和Step2.2實際上就是對當前得到的含有歧義鏈接的塊進行判斷，如果在這個塊的外部仍有歧義鏈接對應到塊中的某些詞(源語詞或者目標語詞)就更新塊的范圍使其包含這個歧義鏈接。當這個塊無法被更新時，表示得到OAB，退出循環(huán)。這個算法的時間復雜度為Θ(I·J)。相比最直接的遍歷方法(時間復雜度為Θ(I2·J2))，它具有更高的運行效率。

4 重對齊模型

4.1 模型1

首先，為了簡化OAB的重對齊問題，我們假設：

a)OAB中的詞對齊是上下文無關(guān)的。對于一個OAB，其他OAB不會影響它的對齊結(jié)果。

b)OAB中的詞對齊 與雙向詞對齊的并集aunion是兼容的，即a?aunion。

根據(jù)這兩個假設，我們定義OAB(fj1…fj2,ei1…ei2)上最優(yōu)的詞對齊為：

abest=arg maxa?aunionScore(a,OAB)

(2)

其中Score(a,OAB)是一個函數(shù)用來評價對齊a的好壞程度。由于直接在整體上對OAB中的詞對齊進行評價是比較困難的，我們把Score(a,OAB)定義為如下形式：

(3)

其中{factor1(a,OAB),…,factorK(a,OAB)}表示影響詞對齊的各個因素的集合。沿用經(jīng)典的IBM models[4]的思路，本文定義了三個影響OAB中的詞對齊的因素，它們是：翻譯概率(Translation Equivalent Probabilities)，扭曲度概率(Distortion Probabilities)和產(chǎn)出率概率(Fertility Probabilities)。于是我們得到，

(4)

其中，

(5)

(6)

(7)

這里Score(link(a,OAB))表示整個詞對齊所對應的翻譯概率， 表示fj和ei互為翻譯的聯(lián)合概率。Score(fertility(a,OAB))表示OAB生成一定數(shù)量鏈接的概率，這里n(φw|w)表示一個單詞w對應φw條鏈接的概率。Score(distortion(a,OAB))表示詞對齊所對應的整體調(diào)序概率，這里d(j,i)表示源語言第j個詞與目標語上第i個詞之間有鏈接的概率。

對于模型的參數(shù)估計，我們直接使用IBM model 3得到n(φw|w)的估計。而對于t(fj,ei)，我們在訓練語料的aunion上，使用極大似然估計(Maximum Likelihood Estimation, MLE)的方法對其進行估計，即：t(fj,ei)=count(fj和ei之間有鏈接)/count(fj和ei共現(xiàn))。對于d(j,i)，我們采用了一個簡單的估計方法(或者說定義)，d(j,i)=α|i-I·j/J|。這里|i-I·j/J|表示在對齊矩陣中(j,i)與對角線的相對距離，距離越遠表示調(diào)序的程度越大。α<1.0是調(diào)解因子，在本文中我們通過實驗的方法得到α的最優(yōu)值0.9。

4.2 模型2

在語言的使用中，我們常常會用多個連續(xù)的詞來表達一個概念，比如漢語和英語中的名詞短語。如果一個連續(xù)的詞序列頻繁地共現(xiàn)，那它們很有可能在集中描述一個概念，在對齊中被作為一個單元的可能性就越大。比如，如果源語言句子中的某個詞序列中的每個詞都對應到目標語句子的相同部分，這個詞序列就很有可能構(gòu)成一個對齊單元。如果我們能很好的度量一個詞或詞序列表達同一個概念的可能性大小，那么這個信息就可以幫助我們得到更好的詞對齊結(jié)果?；谶@個想法，我們在模型1的基礎上引進了一個新的單語特征，用它來度量在對齊中每個對齊單元的好壞程度。定義如下：

(8)

其中，

(9)

這里a(w)表示所有與w有對齊關(guān)系的詞的集合，|a(w)|表示與w有對齊關(guān)系的詞的數(shù)量。m(a(w))是對a(w)作為一個對齊單元可靠性的度量。本文中，我們把m(a(w))定義為(以m(a(fj))作為實例，對于m(a(ei))可以同理推得)，

(10)

這里Pr(ek)和Pr(ep…eq)表示ek和ep…eq在單語(目標語)中出現(xiàn)的概率，它們可以直接通過MLE方法在單語語料上進行估計。

4.3 搜索

對于一個OAB，如果它包含l個aunion的鏈接，那么搜索最優(yōu)對齊的搜索空間為2l。對于大部分OAB來說，l都是一個比較小的值，這時我們可以直接使用全搜索的方法來得到abest。而對于l比較大的情況(l≥lmax)，我們使用了一個基于棧的解碼器來搜索abest。它聯(lián)合使用了翻譯概率和扭曲度概率作為啟發(fā)函數(shù)來對abest進行搜索。這里lmax是一個閾值，我們用它來限定需要剪枝處理的鏈接數(shù)的下限。

此外，還可以利用ainter來進一步縮小搜索空間。通常ainter包含的都是準確的詞對齊，因此可以把它作為對齊錨點。這樣，在提高搜索效率的同時，可能會進一步提高性能。利用ainter作為錨點后搜索空間可以被進一步限制在ainter?a?aunion范圍內(nèi)。

5 實驗

5.1 測試方法及實驗用數(shù)據(jù)

我們把本文提出的方法應用到實際的漢英統(tǒng)計機器翻譯系統(tǒng)中來驗證它的有效性，并使用大小寫不敏感的BLUE4做為翻譯質(zhì)量的評價指標。

實驗所使用的訓練和測試數(shù)據(jù)是SSMT2007官方提供漢英機器翻譯任務用數(shù)據(jù)，包括：訓練語料約80萬句對，開發(fā)集500句(每句4個參考譯文)，測試集1 002句(每句4個參考譯文)。在使用前，我們首先用東北大學自然語言處理實驗室所開發(fā)的中文分詞工具*http://www.nlplab.com/對中文句子進行分詞，并用一個基于規(guī)則的tokenizer對英文句子進行切分，此外我們還去掉了英文單詞的大小寫信息。我們使用了部分LDC提供的語料作為訓練重對齊模型2所使用的源語和目標語的單語語料，包括大約180萬句的中文和180萬句英文單語語料。

5.2 基準系統(tǒng)

本文采用基于短語的統(tǒng)計機器翻譯系統(tǒng)moses*http://www.statmt.org/moses/作為實驗的基準系統(tǒng)。其中，我們用基于IBM models的GIZA++*http://www.fjoch.com/GIZA++.html獲得了正反雙向詞對齊結(jié)果。為了對比本文提出的方法，我們采用了三種基于啟發(fā)信息的詞對齊對稱化方法“intersection”，“union”和“refined”作為從正反雙向詞對齊獲得對稱的詞對齊的baseline方法[2]。這里“intersection”“union”和“refined”分別是指：雙向?qū)R的交集，雙向?qū)R的并集，在雙向?qū)R的交集的基礎上利用啟發(fā)信息進行擴展并考慮對齊矩陣中對角線位置的信息這三種方法*“refined”方法是moses工具包所使用的缺省方法。它也被稱作“intersect-diag-grow”方法。。此外我們利用SRLIM工具在實驗用的英文單語語料上訓練了5-gram語言模型。對于短語抽取和decoder，我們都使用了moses工具包所提供的程序，并采用缺省設置。此外，我們使用了最小錯誤率訓練來對參數(shù)進行優(yōu)化。

5.3 Baseline vs.重對齊

在進行重對齊之前，我們首先進行了雙向詞對齊，之后識別出了訓練語料中所有的OAB。表1給出了相關(guān)的統(tǒng)計信息?？梢钥闯?，平均每個句對包含大約1.65個OAB。這表明OAB在漢—英機器翻譯中的詞對齊任務中是很常見的。此外我們在實驗中還發(fā)現(xiàn)絕大多數(shù)的OAB(>80%)包含的鏈接數(shù)小于等于15。因此，在隨后的所有實驗中我們均設置lmax=15來對包含鏈接數(shù)大于15的搜索進行剪枝。

在識別OAB之后我們分別利用本文提出的重對齊模型1和模型2進行了重對齊，并把得到的對齊結(jié)果用于基準統(tǒng)計機器翻譯系統(tǒng)中。在實驗中，我們并沒有利用錨點ainter對搜索進行剪枝。實驗結(jié)果如表2所示?？梢钥闯鲈谌NBaseline方法中，“refined”方法取得了最好的性能，其次是“union”方法。不過，“intersection”方法卻取得了比前兩種方法差很多的性能。這主要是由于，“intersection”方法會產(chǎn)生非常稀疏的對齊結(jié)果，這會導致短語表中噪聲的增加，并最終降低翻譯質(zhì)量。相比Baseline方法，本文提出的方法得到了更高的BLUE值。重對齊模型1和模型2比最高的Baseline方法分別高出0.59和0.68個點。這說明了本文提出的方法的有效性。此外，模型2比模型1取得了更好的性能，這也說明了使用單語語料也可以進一步改善詞對齊的質(zhì)量，并間接提高統(tǒng)計機器翻譯系統(tǒng)的性能。

表1 詞對齊統(tǒng)計信息

表2 Baseline及重對齊模型性能

表3 使用錨點信息后的性能

5.4 錨點信息的使用

根據(jù)4.3節(jié)的論述，我們可以使用ainter作為錨點來縮小搜索空間。表3給出了模型1和模型2使用錨點信息后的翻譯性能。有趣的是，對于模型1，錨點信息的使用帶來了翻譯性能的進一步提高，相比5.3節(jié)的實驗結(jié)果又提高了0.09個點。而模型2在使用錨點信息之后翻譯性能卻下降了0.02個點。這個實驗結(jié)果說明，在OAB中，模型的最優(yōu)解abest不一定總包含ainter。雖然在整體上ainter中的對齊準確率較高，但它并不一定能帶來OAB重對齊性能的提高。

5.6 單語語料規(guī)模大小對性能的影響

在最后一組實驗中，我們對單語語料規(guī)模大小對重對齊模型2的性能的影響進行了研究。我們分別用20%，40%，60%，80%和100%的單語語料訓練，得到了模型2的對齊結(jié)果。除了在40%時性能略有下降外，翻譯性能基本上是隨著單語語料數(shù)量的增大而提高。但最大的提高只有0.2個點。這說明雖然我們可以利用單語語料來提高模型2的性能，但性能提高的幅度有限。我們還發(fā)現(xiàn)，當單語語料規(guī)模達到一定大小后(比如實驗用單語語料的80%)翻譯性能趨于平穩(wěn)。這表明，在我們的方法中，單純地增大單語語料規(guī)模并不能有效地提高翻譯翻譯準確性。

6 相關(guān)工作

Koehn等人[1]以及Och和Ney[2]研究了利用雙向非對稱的詞對齊得到對稱的詞對齊的方法。在他們的方法中，首先把正反雙向詞對齊的交集部分固定，之后利用啟發(fā)信息來擴展固定部分。但是這種基于啟發(fā)信息的方法更傾向于含有局部調(diào)序的對齊，而對于語序相差很大的語言間的對齊的性能并不是很好。Liang等人[5]提出了一種利用最大化正反雙向?qū)R的一致部分的似然概率的方法來得到更好的詞對齊結(jié)果。與Liang等人工作不同，我們的工作集中在正反雙向?qū)R不一致的部分。也就是說我們更關(guān)心重新對齊那些正反雙向訓練下IBM modes不能達成一致的對齊。

還有其他一些工作主要集中在利用判別模型來進行詞對齊[6-9]。他們把詞對齊轉(zhuǎn)化為有指導或半指導的分類任務，并利用多個特征共同作用得到對齊結(jié)果。不過，這些方法均需要人工標注的詞對齊的訓練語料，訓練數(shù)據(jù)的構(gòu)造代價比較昂貴。

此外，本文工作與其他相關(guān)工作的另一個重要不同是，我們提出的重對齊方法可以利用單語語料來進一步提高性能。而這個問題在以前的工作中并沒有被很好地討論過。

7 討論

在模型的參數(shù)估計方面，本文分別對不同的參數(shù)采用了不同的估計方法。這么做的好處在于方法簡單，而且系統(tǒng)易于實現(xiàn)。實際上，也可以考慮利用EM等無指導的學習方法，來最大化詞對齊在整個訓練集上的似然概率(可以把目標函數(shù)看做詞對齊的可能性的度量)，同時得到更好的參數(shù)估計結(jié)果。

此外，在本文提出的模型中，我們使用了多個特征得分的乘積(或者說是log線形加)的形式來表示一個詞對齊的得分。但是這些特征的權(quán)重都是相等的(都為1)。實際上，也可以通過調(diào)整特征的權(quán)重使模型取得更好的性能。不過，我們需要使用少量帶有人工標注詞對齊的開發(fā)集來優(yōu)化這些權(quán)重。

8 結(jié)論及未來工作

本文提出了一種重對齊方法，它在IBM models生成正反雙向詞對齊的基礎上，對雙向?qū)R有歧義的部分進行重新對齊，最終得到完整的對稱的詞對齊結(jié)果。此外，這個方法可以利用單語語料來進一步改進詞對齊結(jié)果，不過性能提高的幅度有限。相比在統(tǒng)計機器翻譯中廣泛使用的基于啟發(fā)信息的詞對齊對稱化方法，文本提出方法可以使統(tǒng)計機器翻譯系統(tǒng)得到更高的翻譯準確率。在以后的工作中，我們會對重對齊模型的參數(shù)估計和模型最優(yōu)解的搜索等問題做進一步研究。

[1] Philipp Koehn, Franz Josef Och ,and Daniel Marcu. Statistical Phrase-Based Translation [C]//Proc. of HLT/NAACL2003. 2003: 48-54.

[2] Franz Josef Och and Hermann Ney. A systematic comparison of various statistical alignment models [J]. Computational Linguistics, 2003, 29(1):19-51.

[3] Alexander Fraer and Daniel Marcu. Measuring word alignment quality for statistical machine translation [R]. Technical Report ISI-TR-616. ISI/University of Southern California, 2006.

[4] Peter F. Brown, Stephen A. Della Piatra, Vincent J. Della Pietra, and R. L. Mercer. The mathematics of statistical machine translation: Parameter estimation [J]. Computational Linguistics. 1993, 19(2):263-311.

[5] Percy Liang, Ben Taskar, and Dan Klein. Alignment by agreement [C]//Proc. of HLT/NAACL2006. 2006: 104-111.

[6] Yang Liu, Qun Liu, and Shouxin Lin. Log-linear models for word alignment [C]//Proc. of ACL2005. 2005: 459-466.

[7] Alexander Fraer and Daniel Marcu. Semi-Supervised Training for Statistical Word Alignment [C]//Proc. of ACL2006. 2006: 769-776.

[8] Abraham Ittycheriah and Salim Roukos. A maximum entropoy word aligner for Arabic-English machine translation [C]//Proc. of HLT/EMNLP2005. 2005: 89-96.

[9] Ben Taskar, Simon Lacoste-Julien, and Dan Klein. A discriminative matching approach to word alignment [C]//Proc. of HLT/EMNLP2005. 2005: 73-80.