沈世奇，劉 洋，孫茂松

（清華大學 計算機科學與技術(shù)系 智能技術(shù)與系統(tǒng)國家重點實驗室，北京100084）

1 引言

詞語對齊旨在計算平行文本中詞語之間的對應(yīng)關(guān)系。例如，給定一個中文句子和一個英文句子①該例句及詞語對齊源自（Liu et al，2010）

中國建筑業(yè)對外開放呈現(xiàn)新格局。

The opening of China's construction industry to the outside presents a new str ucture.

圖1 詞語對齊示例

圖1 給出了這兩個句子的詞語對齊。由于中文詞“中國”與英文詞“China”互相翻譯，兩者之間存在一條連線顯示對應(yīng)關(guān)系。需要指出的是，中文詞與英文詞并不完全是一一對應(yīng)，例如，中文詞“建筑業(yè)”對應(yīng)兩個英文詞“constr uction industr y”。更復雜的情況是一個中文詞對應(yīng)到若干個非連續(xù)的英文詞，例如，“對外開放”對應(yīng)英文詞“opening...to the outside”。因此，由于自然語言的多樣性和復雜性，發(fā)現(xiàn)不同語言之間的詞語對應(yīng)關(guān)系是一個非常具有挑戰(zhàn)性的問題。

詞語對齊最早是作為機器翻譯的中間結(jié)果由Br own et al.提出［1]。由于詞語對齊能夠為不同自然語言在詞語層建立關(guān)聯(lián)，它在機器翻譯、機器輔助翻譯、詞義消歧和雙語詞典構(gòu)建等多項自然語言處理任務(wù)中起著關(guān)鍵的作用。例如，在統(tǒng)計機器翻譯中，無論是基于短語的方法［2]、基于層次短語的方法［3]還是基于句法的方法［4]，往往都依賴于詞語對齊進行規(guī)則抽取，因而詞語對齊的質(zhì)量對機器翻譯譯文的質(zhì)量具有重要的影響。

詞語對齊模型大致可分為生成式模型和判別式模型兩大類。生成式模型［1，5－6]為詞語對齊設(shè)計生成故事（generative story 其優(yōu)點在于不需要標注數(shù)據(jù)進行訓練，很容易應(yīng)用于各個領(lǐng)域，其缺點在于模型難以擴展。判別式模型［7－10]將各種知識源作為特征函數(shù)加入到模型中，易于擴展，其主要缺點在于依賴于標注數(shù)據(jù)。在訓練算法方面，生成式模型主要使用EM算法［1]實現(xiàn)無監(jiān)督學習，而判別式模型可以使用最小錯誤率訓練算法［11]實現(xiàn)直接優(yōu)化評價指標，大幅提高對齊質(zhì)量。Dyer et al.［12]最近提出了判別式模型的無監(jiān)督訓練，實現(xiàn)了判別式模型與無監(jiān)督學習的優(yōu)勢互補。

然而，盡管詞語對齊在建模和訓練算法方面取得了較大的進展，多數(shù)搜索算法仍然面臨著搜索錯誤嚴重的問題。給定一個源語言句子fJ1和一個目標語言句子eI1，可能的詞語對齊結(jié)果數(shù)量是2J×I。對于以IBM模型［1]為代表的生成模型而言，雖然簡單的模型1和模型2可以精準計算Viterbi對齊，但是對于更復雜的模型3、4、5只能使用爬山法計算近似解［1，13]。對于以線性模型［10]為代表的判別式模型而言，往往也只能使用柱搜索算法來計算近似解。

圖2給出了文獻［10]所提出的柱搜索算法的搜索空間，該算法以空對齊為起點，不斷添加連線直至模型分數(shù)無法增加為止。由于詞語對齊中連線之間存在錯綜復雜的依賴關(guān)系，無論是爬山法還是柱搜索算法都面臨著嚴重的搜索錯誤問題。最近，Riesa和 Marcu［14]將立方體剪枝［3]引入詞語對齊，但本質(zhì)上仍然只能計算近似解。因此，搜索算法已經(jīng)成為制約詞語對齊質(zhì)量的瓶頸問題。

圖2 詞語對齊的搜索空間

近年來，對偶分解（dual decomposition被廣泛應(yīng)用于句法分析［15]和機器翻譯［16]等自然語言處理任務(wù)來實現(xiàn)精準求解（exact decoding），均取得了良好的效果。為了緩解詞語對齊所面臨的搜索錯誤問題，本文提出一種基于對偶分解的詞語對齊搜索算法，其基本思想是將復雜的問題分解為兩個相對簡單的子問題，迭代求解直至收斂。由于對偶分解能夠確保求解的收斂性和最優(yōu)性［17]，我們的方法在2005年度863計劃詞語對齊評測數(shù)據(jù)集上顯著超過IBM模型的爬山法［1]與判別式模型的柱搜索算法［10]，對齊錯誤率分別降低4.4% 和1.1%。

2 基于對偶分解的詞語對齊搜索算法

對偶分解的基本思想是將一個復雜的問題分解為兩個相對簡單的子問題，之后對兩個子問題進行分別求解，通過一個數(shù)據(jù)結(jié)構(gòu)記錄兩者的差異之處并利用該數(shù)據(jù)結(jié)構(gòu)試圖使兩個子問題的解趨于一致。當算法經(jīng)過多輪迭代收斂（即兩個子問題得出相同的解）時，該解為最優(yōu)解。

圖3給出了基于對偶分解的詞語對齊搜索算法的一個示例。給定中文句子“呈現(xiàn) 新 格局 ?！焙陀⑽木渥印皃resent a new str ucture.”，假設(shè)我們將一個詞語對齊模型拆成兩個子模型進行分別求解，并定義函數(shù)u （j，i）來記錄兩個子模型的解的差異之處。初始狀態(tài)對于任意的i和j，u （j，i）均設(shè)為0。圖3（a）顯示了兩個子問題的解，上面是子問題一的解，下面是子問題二的解?？梢园l(fā)現(xiàn)，兩個解存在差異：子問題一的連線 （2，2）與子問題二的連線 （2，1）不一致，即子問題一將“新”與“a”連線而子問題二將“呈現(xiàn)”與“a”相連。因此，算法更新u函數(shù)，將u （2 ，2）設(shè)為－1，將u（2，1）設(shè)為1，試圖使兩個子問題的解趨向一致（如圖3（b）所示）。再次進行求解，兩個子問題的解達成一致，獲得最終解（如圖3（c）所示）。這也說明了對偶分解的方法得到的解3（c）能夠優(yōu)于子問題的解3（a）的原因。

圖3 基于對偶分解的詞語對齊算法示例

更形式化地，給定源語言句子fJ1和目標語言句子eI1，基于對偶分解的詞語對齊的搜索算法的目標如式（1）所示。

其中，Y和Z分別是兩個詞語對齊的解集合，y和z分別是其中的一個解，f （y）對應(yīng)子問題一的模型，g（z）對應(yīng)子問題二的模型，y j，（i）＝1表示子問題一將fj與ei連在一起，0則表示沒有相連。因此，對偶分解的目標是計算兩個子問題達成一致的最優(yōu)解。

對偶分解將按照子問題一和子問題二進行分別求解。子問題一的優(yōu)化目標如式（3）所示。

子問題二的優(yōu)化目標如式（4）所示。

圖4給出了基于對偶分解的詞語對齊搜索算法。算法的輸入是源語言句子和目標語言句子（第1行）。首先初始化懲罰函數(shù)u （j，i），全部設(shè)為0（第2行）。之后進入迭代求解（第3行），分別對子問題一（第4行）和子問題二（第5行）進行求解。如果滿足收斂條件，即兩個子問題生成完全相同的對齊，則返回最優(yōu)解（第6至7行），否則更新懲罰函數(shù)（第9行）進入下一輪迭代。如若超過最大迭代次數(shù)仍然沒有收斂，則選取迭代過程中子問題的最優(yōu)解作為最后的結(jié)果。其中，αk是第k輪迭代的更新比率，用來控制算法收斂的速度。Rush和Collins［18]證明當αk滿足以下條件時

圖4 基于對偶分解的詞語對齊搜索算法

并且

對偶分解算法能確保評價函數(shù)收斂。

3 實驗

本文的訓練集是中英24萬句對的政府新聞類雙語語料庫，開發(fā)集和測試集是2005年度863計劃詞語對齊評測數(shù)據(jù)集，開發(fā)集包含502句對，測試集包含505句對。我們所使用的評價指標是由Och和 Ney［13]的對齊錯誤率 （Align ment Err or Rate，AER），對齊錯誤率越低表示對齊質(zhì)量越高。

我們與以下兩個系統(tǒng)進行對比：

（1）GIZA＋＋：IBM 模型［1]，采用EM 算法進行參數(shù)訓練，爬山法進行搜索，由Och和Ney［13]實現(xiàn)。

（2）Vigne：Liu et al.［10]提出的判別式詞語對齊方法，采用最小錯誤率訓練算法［11]進行參數(shù)訓練，柱搜索算法進行搜索。

我們首先使用GIZA＋＋的默認設(shè)置進行雙向訓練，得到中英和英中兩個方向的IBM模型4的對齊結(jié)果以及模型參數(shù)。Vigne主要采用GIZA＋＋輸出的IBM模型參數(shù)作為主要特征，具體為文獻［10]提出的9個特征，利用最小錯誤率訓練［11]在開發(fā)集上優(yōu)化特征權(quán)重，在測試集上采用柱搜索算法獲得最優(yōu)對齊結(jié)果。我們的詞語對齊系統(tǒng)在建模和訓練算法上與Vigne完全一致，只是在搜索算法上采用對偶分解法。

3.1 與傳統(tǒng)搜索算法的對比

表1給出了我們的系統(tǒng)與GIZA＋＋和Vigne的對比結(jié)果。GIZA＋＋產(chǎn)生四種對齊結(jié)果：

（1）中英：以中文為源語言，英文為目標語言，使用IBM模型4；

（2）英中：以英文為源語言，中文為目標語言，使用IBM模型4；

（3）交集：兩個方向?qū)R結(jié)果的交集；（4）并集：兩個方向?qū)R結(jié)果的并集。

其中，GIZA＋＋的交集取得了四種設(shè)置中最好的結(jié)果23.9。判別式詞語對齊系統(tǒng)Vigne取得的對齊錯誤率是20.8，顯著超過了GIZA＋＋。而我們的對偶分解算法取得了最好的對齊錯誤率19.7，超過GIZA＋＋4.4個百分點，Vigne1.1個百分點。我們采用了Koehn［19]提出的顯著性檢驗方法驗證上述差別在統(tǒng)計上是顯著的（p＝0.05），從而驗證了對偶分解算法確實有效減少了搜索錯誤。

在搜索效率上，GIZA＋＋作為一個無監(jiān)督的方法，需要對較大的數(shù)據(jù)進行整體的處理，并不能對單句進行詞對齊，與Vigne和我們的方法很難比較。

而我們使用的對偶分解采用的是迭代的方法，每一輪迭代都需要對兩個子問題分別搜索，所以在時間上要慢于Vigne時間復雜度隨著迭代次數(shù)的增長而增長。

表1 GIZA＋＋、Vigne與我們的方法的對比結(jié)果

3.2 迭代更新比率αk對收斂率和對齊錯誤率的影響

Rush和Collins［18]指出迭代更新比率αk將對對偶分解的迭代是否收斂產(chǎn)生重要影響。因此，我們通過實驗研究迭代更新比率對收斂率的影響。所謂收斂率，是指待對齊文本中達到收斂的句子比例。例如，如果對偶分解算法在100個句子中的90個句子達到收斂，則收斂率為90%。我們設(shè)定最大迭代次數(shù)K為100，當?shù)^100次后我們認為該句子在本方法下不收斂。表2給出了不同的迭代更新比率及相應(yīng)的收斂率和對齊錯誤率。其中，k為迭代次數(shù)，t是一個整數(shù)，其值為在迭代過程中對偶分解的評價函數(shù)增長的次數(shù)。由于1／t（＋1）和1／k滿足式（5）和（6），它們對應(yīng)的收斂率均超過96% 并取得較低的AER。與之相反，常數(shù)型的更新比率（如0.1、0.01和0.001）則對應(yīng)較低的收斂率和較高的AER。因此，更新比率對于收斂率和AER具有重要的影響①需要指出的是，在實際過程中，我們發(fā)現(xiàn)對于較長的句子無法實現(xiàn)＄100＼%＄的收斂率，原因在于收斂性與最優(yōu)性的約束條件并不完全一致。但即使對偶分解算法無法通過收斂獲得最優(yōu)解，也可以計算出較好的次優(yōu)解。。

表2 迭代更新比率αk對結(jié)果的影響

3.3 句子長度對收斂率的影響

對于詞語對齊問題來說，句子的長度直接影響了算法的復雜性。直觀來看，句子越短，詞語對齊所需要的搜索空間越小。反之，句子越長，搜索空間越大。我們設(shè)置不同的迭代收斂比率αk，觀察對偶分解算法在不同長度的句子上的收斂率。圖5給出了在αk＝0.1、總收斂率為0.6040的條件下，句子的收斂比率隨句子長度變化的關(guān)系圖?？梢钥闯?，對偶分解算法的收斂率隨著句子長度的增長大致是呈現(xiàn)下降趨勢。也就是說，由于句子長度的增長而增大的搜索空間會使得算法收斂率下降。

圖5 句子長度對收斂率的影響

3.4 收斂與不收斂數(shù)據(jù)集上對偶分解與柱搜索的比較

表3給出了收斂數(shù)據(jù)集和不收斂數(shù)據(jù)集上對偶分解算法與柱搜索算法的比較情況。我們發(fā)現(xiàn)無論是在收斂數(shù)據(jù)集上還是在非收斂數(shù)據(jù)集上，對偶分解算法都取得了比柱搜索算法更好的結(jié)果，進一步證明對偶分解算法能有效地提高對齊質(zhì)量①值得注意的是，在收斂數(shù)據(jù)集和非收斂數(shù)據(jù)集上對齊錯誤率有較大的差異，收斂數(shù)據(jù)集上的對齊錯誤率明顯較優(yōu)，原因在于對偶分解能夠在相對簡單的句子上收斂，故根據(jù)收斂性就會將數(shù)據(jù)集劃分為“較難”和“較易”的兩部分。。

表3 收斂和不收斂數(shù)據(jù)集上對偶分解與柱搜索的比較

3.5 對偶分解與子模型的比較

在實驗中，我們采用的子模型一是線性模型，采用Liu et al.［10]提出的9個特征，與Vigne的特征一致，子模型二也是線性模型，采用Liu et al.［10]提出的6個特征。表4給出了對偶分解算法與其使用的兩個子模型各自的對齊錯誤率。我們觀察到與兩個子模型相比，對偶分解方法取得了更優(yōu)的結(jié)果，這也進一步說明對偶分解算法的確能夠在子模型的基礎(chǔ)上減少搜索錯誤，降低對齊錯誤率。

表4 對偶分解與子模型的對齊錯誤率比較

4 相關(guān)工作

Koo et al.［19]首次將對偶分解應(yīng)用于自然語言處理領(lǐng)域，他們在句法分析上驗證了對偶分解算法的有效 性。Rush 和 Collins［17]與 Chang 和 Collins［16]則分別將對偶分解算法引入基于句法和基于短語的機器翻譯中，有效減少了搜索錯誤。De Nero和Macherey［20]首次將對偶分解引入詞語對齊，但他們的重點是模型融合，我們則側(cè)重擴展判別式模型的搜索算法。Martins et al.［21]進一步將對偶分解擴展為可以處理若干個子問題。

除了對偶分解，整數(shù)線性規(guī)劃（Integer Linear Pr ogra mming）是另一項被廣泛應(yīng)用的優(yōu)化技術(shù)。Ravi和Knight［22]將整數(shù)線性規(guī)劃首次應(yīng)用于詞語對齊，為GIZA＋＋設(shè)計了精準搜索算法。

綜合利用多個結(jié)果來改善結(jié)果的方法有模型融合和系統(tǒng)融合，但是對偶分解本質(zhì)上是一種最優(yōu)化搜索算法，它可以被用于系統(tǒng)融合：不是將原問題分成兩個子問題，而是分成多個子問題。

5 結(jié)論

本文提出了一種基于對偶分解的詞語對齊搜索算法，通過子問題迭代分別求解直至收斂于最優(yōu)解。我們的方法在2005年度863計劃詞語對齊評測數(shù)據(jù)集上顯著超過生成式模型的爬山法和判別式模型的柱搜索算法。未來我們將深入研究提高長句收斂率的方法，希望能進一步減少詞語對齊的搜索錯誤。

［1]Peter F Brown，Vincent J Della Pietra，Stephen A Della Pietra，et al.The mathematics of statistical machine translation：parameter estimation［J].Computational Linguistics，1993，19（2）：263－311.

［2]Philipp Koehn，F(xiàn)ranz J Och，Daniel Marcu.Statistical phrase－based translation［C]／／Pr oceedings of HLTNAACL，Ed monton，Canada，May.2003：127－133.

［3]David Chiang. Hierarchical phrase－based translation［J].Computational Linguistics，2007，33（2）：201－228.

［4]Michel Galley，Jonathan Graehl，Kevin Knight.Scalable inference and training of contextrich syntactic translation models［C]／／Proceedings of COLINGACL，Sydney，Australia，July.2006：961－968.

［5]Stephan Vogel，Her mann Ney，Christoph Till mann.Hmm－based word align ment in statistical translation［C]／／Proceedings of t he 16th conference on Co mputational linguistics—Volu me 2，COLING'96，Stroudsburg，PA，USA.Association f or Computational Linguistics.1996：836－841.

［6]Percy Liang Ben Taskar Dan Klein.Align ment by agreement［C]／／Proceedings of the main conference on Human Language Technology Conference of the North American Chapter of the Association of Co mputational Linguistics， HLT－NAACL'06， Str oudsbur g， PA，USA. Association for Co mputational Linguistics.2006：104－111.

［7]Yang Liu，Qun Liu，Shouxun Lin.Loglinear models for wor d align ment［C]／／Proceedings of the 43r d Annual Meeting on Association f or Computational Linguistics，ACL'05，Stroudsburg，PA，USA.Association for Computational Linguistics.2005：459－466.

［8]Robert C Moore.A discriminative framework f or bilingual wor d align ment［C]／／Proceedings of the Conference on Hu man Language Technology and Empirical Methods in Natural Language Processing，HLT'05，Stroudsburg，PA，USA.Association f or Computational Linguistics.2005：81－88.

［9]Phil Blunso m，Trevor Cohn.Discri minative wor d align ment with conditional random fields［C]／／Proceedings of the 21st Inter national Conference on Co mputational Linguistics and the 44th Annual Meeting of the Association for Computational Linguistics，ACL－44，Stroudsburg，PA，USA.Association f or Co mputational Linguistics.2006：65－72.

［10]Yang Liu，Qun Liu，Shouxun Lin.Discri minative word align ment by linear modeling［J].Computational Linguistics，2010：36（3）：303－339.

［11]Franz Josef Och.Mini mu m error rate training in statistical machine translation［C]／／Proceedings of the 41st Annual Meeting on Association f or Co mputational Linguistics—Volume 1，ACL'03，Stroudsburg，PA，USA.Association f or Computational Linguistics.2003：160－167.

［12]Chris Dyer，Jonat han H Clar k，Alon Lavie，et al.Unsupervised word align ment with ar bitrary feat ures［C]／／Proceedings of the 49th Annual Meeting of the Association f or Computational Linguistics：Human Language Technologies，Portland，Oregon，USA，June.Association f or Co mputational Linguistics.2011：409－419.

［13]Franz Josef Och，Her mann Ney.A systematic comparison of various statistical alignment models［J].Co mput.Linguist.，2003，29（1）：19－51，March.

［14]Jason Riesa，Daniel Marcu.Hierarchical search f or wor d align ment［C]／／Pr oceedings of t he 48th Annual Meeting of the Association f or Computational Lin－guistics ACL'10 Stroudsburg PA USA.Association f or Computational Linguistics.2010：157－166.

［15]Terry Koo，Alexander M Rush，Michael Collins，et al.Dual deco mposition f or parsing wit h non－projective head auto mata［C]／／Proceedings of t he 2010 Conference on Empirical Methods in Natural Language Processing，EMNLP'10，Stroudsburg，PA，USA.Association for Computational Linguistics.2010：1288－1298.

［16]Yin－Wen Chang，Michael Collins.Exact decoding of phrase－based translation models through lagrangian relaxation［C]／／Proceedings of the Conference on Empirical Methods in Natural Language Processing，EMNLP'11，Stroudsburg，PA，USA.Association f or Co mputational Linguistics.2011：26－37.

［17]Alexander M Rush，Michael Collins.Exact decoding of syntactic translation models through lagrangian relaxation［C]／／Proceedings of the 49th Annual Meeting of the Association f or Co mputational Linguistics：Hu man Language Technologies—Volu me 1，HLT'11，Stroudsburg，PA，USA.Association f or Co mputational Linguistics.2011：72－82.

［18]Alexander Rush，Michael Collins.A tutorial on lagrangian relaxation and dual deco mposition f or nlp［J].Jour nal of Artificial Intellegience Research.2012.

［19]Philipp Koehn.Statistical significance tests for machine translation evaluation［C]／／Dekang Lin and Dekai Wu，editors，Proceedings of EMNLP，Barcelona，Spain，July.Association for Co mputational Linguistics.2004：388－395.

［20]John De Nero，Klaus Macherey.Model－based aligner combination using dual decomposition［C]／／Proceedings of the 49th Annual Meeting of the Association f or Co mputational Linguistics：Hu man Language Technologies，Portland，Oregon，USA，June.Association f or Computational Linguistics.2011：420－429.

［21]Andre Martins，Noah Smith，Mario Figueiredo，et al.Dual deco mposition with many overlapping co mponents［C]／／Pr oceedings of the 2011 Conference on Empirical Methods in Natural Language Processing，Edinburgh，Scotland，UK，July.Association f or Co mputational Linguistics.2011：238－249.

［22]Sujith Ravi，Kevin Knight.Does giza＋＋make search errors？［J].Computational Linguistics，2010，36（3）.