劉穎，姜巍

（清華大學中文系，北京100084）

1 引言

統(tǒng)計機器翻譯由IBM的Brown等人于1990年提出，1993年他們提出了基于詞對齊的五個復雜度遞增的模型—IBM模型1至5［1］。IBM統(tǒng)計機器翻譯都是以詞為基本的翻譯單位，詞的對齊與詞語翻譯概率和對齊概率有關(guān)。IBM模型1假設對齊概率是平均對齊，即與源語言句子的長度成反比。IBM模型2假設對齊概率與源語言、目標語言的句子長度以及源語言位置和目標語言位置相關(guān)。IBM模型3和4考慮了空源語言詞、繁殖率和扭曲模型。IBM的重新排序模型很少利用上下文，更沒有利用句法結(jié)構(gòu)，許多人嘗試把句法信息結(jié)合進翻譯模型中來改進這個模型［2］。Vogel提出基于隱馬爾克夫模型（簡稱HMM）的統(tǒng)計翻譯，利用HMM進行的對齊概率依賴于前一個詞所對齊的詞在目標語言句子的位置［3］。即源語言的兩個詞位置越近，它們的目標詞在目標語言句子的位置也越近。Och系統(tǒng)比較了IBM模型和HMM［4］，在此基礎(chǔ)之上發(fā)布了詞語對齊軟件Giza＋＋①http：／／www.fjoch.com／GIZA＋＋.html，Giza＋＋實現(xiàn)了IBM模型1至模型5和HMM詞語對齊，目前已成為多數(shù)統(tǒng)計機器翻譯系統(tǒng)的基本模塊。詞對齊是統(tǒng)計機器翻譯的基礎(chǔ)，詞對齊的質(zhì)量影響統(tǒng)計機器翻譯的質(zhì)量。

Lopez對基本隱馬爾科夫模型進行改進，提出基于目標語言串距離和依存樹距離的HMM［5］。這個模型不僅取決于兩個對齊位置在目標語言串上的距離，而且取決于這兩個對齊位置在目標語言依存樹上的距離。實驗結(jié)果表明，基于依存樹距離的HMM在詞語對齊訓練中召回率較高，錯誤率較低。Cherry利用目標語言的依存樹對逆轉(zhuǎn)換語法進行約束，以提高詞語對齊的質(zhì)量［6］。國內(nèi)對詞語對齊也進行了許多研究和探索，取得了較好的成績［7－10］。

由于漢語與英語互為翻譯的詞之間存在一對多、多對一、一對空和空對一等情況，同時漢語和英語在表達時間、地點、介紹已知信息和未知信息、對句子中的某些信息進行強調(diào)等方面都存在語序上的不同，使得從大規(guī)模雙語語料庫中對詞進行對齊時，漢語和英語的詞的順序不再完全保持。

基本HMM中詞的對齊與兩個詞的翻譯概率和兩個詞對齊的目標語言詞的串距離有關(guān)系。當漢語和英語互譯詞的順序改變，兩個詞的翻譯概率又比較小時，基本HMM可能給出錯誤的詞語對齊結(jié)果。本文提出改進的HMM，將兩個對齊位置的目標語言短語結(jié)構(gòu)樹距離作為特征引入到詞語對齊模型中，使得詞的對齊不僅與兩個詞的翻譯概率、兩個詞對齊的目標語言詞的串距離有關(guān)，而且與兩個詞對齊的目標語言詞的短語結(jié)構(gòu)樹距離有關(guān)。改進的HMM與基本HMM詞對齊一樣存在全局最優(yōu)詞語對齊，可以在多項式時間內(nèi)找到最優(yōu)的詞語對齊［6］。

2 模型

1）基本HMM

式（1）為HMM基本形式，p（aj｜aj－1，I）稱為對齊概率，p（fj｜eaj）稱為翻譯概率。這個模型是Vogel在1996年提出來的，對齊概率依賴于兩個對齊位置的串距離aj－aj－1［3］。Och改進了這個模型，對齊概率取決于目標語言串兩個對齊位置的串距離aj－aj－1和自動確定的詞類C（eaj－1）。而在文獻［5］中，對齊概率不僅取決于目標語言串兩個對齊位置的串距離aj－aj－1，而且取決于目標語言串兩個對齊位置在依存樹中的距離。

2）改進的HMM

改進的HMM對基本HMM的對齊概率p（aj｜aj－1，I）進行了改進，但翻譯概率p（fj｜eaj）與基本HMM相同。

改進的HMM的對齊概率p（aj｜aj－1，I）與源語言串上的兩個詞在目標語言串兩個對齊位置之間的串距離和短語結(jié)構(gòu)樹距離有關(guān)。二者分別作為一個特征，見式（3）。

式（3）中，i＝aj表示第j個源語言詞與第i個目標語言詞對齊。k＝aj－1表示第j－1個源語言詞與第k個目標語言詞對齊。c（i－k）表示兩個源語言詞對齊的兩個目標語言詞的串距離，c（i－k）的定義和運算與基本HMM相同［3］。λ1＋λ2＝1。t（i，k）表示兩個源語言詞j－1和j對齊的目標語言詞在目標語言短語結(jié)構(gòu)樹的距離。分母是歸一化因子。

下面用實例給出如何計算兩個詞之間短語結(jié)構(gòu)樹距離。

圖1中，從節(jié)點“oriented”到節(jié)點“the”的短語結(jié)構(gòu)樹距離t（5，1）定義如下：

圖1 “The jobs are carrer oriented”短語結(jié)構(gòu)樹

從oriented到the的短語結(jié)構(gòu)樹距離為從oriented到the的操作概率的乘積。每個操作的相應概率定義如下。

（1）POP操作概率：依賴于當前節(jié)點的父節(jié)點類型NodeType和當前節(jié)點在兄弟節(jié)點中的索引NodeIndex。記為PopScore［NodeType］［NodeIndex］。

（2）PUSH操作概率：依賴于當前節(jié)點的類型NodeType和當前節(jié)點的孩子節(jié)點在所有孩子節(jié)點中的索引NodeIndex。記為PushScore［NodeType］［NodeIndex］。

引入父節(jié)點類型的原因在于：統(tǒng)計訓練語料（斯坦福句法分析器處理結(jié)果）中子樹根節(jié)點類型的出現(xiàn)頻率，發(fā)現(xiàn)S，SBAR，NP，VP和PP的出現(xiàn)頻率較高。其中，S為一般性陳述句標記，SBAR為由引導詞引導的從句，NP為名詞短語，VP為動詞短語，PP為介詞短語。據(jù)此將父節(jié)點類型（Node－Type）分為5種：S和SBAR（記為1），NP（記為2），VP（記為3），PP（記為4）和其他短語（記為5）。

本文將當前節(jié)點在兄弟節(jié)點中的索引分為兩類，最右索引（記為1）及其他索引（記為2）。通過實驗發(fā)現(xiàn)，對于父節(jié)點與兄弟節(jié)點分類，可以降低時空消耗，緩解數(shù)據(jù)稀疏問題，同時保證二者結(jié)果相近。

前向—后向算法初始化時，每個操作概率采用最大頻率似然估計法來估計。即：

f（a→b）表示父節(jié)點類型為a、孩子索引為b在樹庫中共出現(xiàn)的次數(shù)。通過上述模型，可以通過短語結(jié)構(gòu)樹Te計算任意兩個位置在短語樹上的距離。該模型主要是為了解決子樹邊界的詞語對齊和句法約束相沖突的問題。

3 前向—后向算法

本文采用前向—后向算法來訓練參數(shù)。首先通過初始參數(shù)計算雙語互譯和對齊概率，然后根據(jù)計算過程中發(fā)生的狀態(tài)轉(zhuǎn)移和生成的符號信息更新參數(shù)，在保證新參數(shù)優(yōu)于原參數(shù)情況下進行更新，即新的模型參數(shù)應該可以更好的解釋雙語互譯和對齊。前向—后向算法利用前向變量和后向變量可以直接進行最大化，其基本假設是在這輪計算過程中出現(xiàn)頻率高的狀態(tài)轉(zhuǎn)移和生成的符號應獲得更高的概率。

對改進的HMM，前向變量和后向變量的定義如下：

前向變量記為αi（j），記錄源語言第j個詞對應目標語言位置i的總概率。根據(jù)動態(tài)規(guī)劃算法αi（j）可以通過下列過程計算：

其中πi表示目標語言位置i的初始概率；bioj表示目標語言第i個位置詞ei生成oj的概率，即翻譯概率，bioj＝p（oj｜ei）。aik表示在源語言第j個詞對應目標語言位置i的情況下，源語言第j＋1個詞對應目標語言位置k的對齊概率。即aik＝p（aj＋1｜aj，I）。

后向變量記為βi（j），記錄源語言第j個詞對應目標語言位置i時，剩余子串的對齊概率之和。βi（j）同樣可以利用動態(tài)規(guī)劃算法計算，見式（8）。

T表示源語言最后一個詞。ξik（j）表示給定雙語互譯句對的情況下，源語言第j個詞對應目標語言第i個位置并且源語言第j＋1個詞對應目標語言第k個位置的概率，稱為詞語對齊的邊后驗概率。用前向變量和后向變量表示為式（9）。

根據(jù)以上定義，更新本文HMM對齊概率的公式為式（10）。

如果，oj＝wk，σ（oj，wk）＝1，否則，σ（oj，wk）＝0。

然后利用前向后向算法進行雙語互譯和對齊概率的計算。

前向后向算法：

①初始化。雙語詞互譯概率來自漢英雙語詞典。

② 根據(jù)雙語句對創(chuàng)建所有可能的狀態(tài)轉(zhuǎn)移矩陣。對于所有兩兩狀態(tài)轉(zhuǎn)移，計算其狀態(tài)轉(zhuǎn)移概率。然后根據(jù)式（3）計算雙語初始對齊概率，λ1＝λ2＝0.5。

③根據(jù)式（7）和式（8）計算這個階段的前向變量和后向變量。

④根據(jù)式（9），利用前向變量和后向變量計算詞語對齊的邊后驗概率。

⑤根據(jù)式（10）更新HMM的對齊概率，根據(jù)式（11）更新HMM的翻譯概率。

⑥重復步驟2，直到模型參數(shù)變化小于某個閾值或者達到指定迭代次數(shù)。

在本文實驗中，設置該閾值為0.001，在初始值如上設置的情況下，一般15輪至20輪迭代可以達到收斂。

4 實驗、結(jié)果和分析

1）實驗數(shù)據(jù)

實驗采用雙語平行訓練語料，語料大部分是從互聯(lián)網(wǎng)抓取后經(jīng)過后處理獲得，此外包括哈爾濱工業(yè)大學的10萬平行雙語句對，整個訓練集包含50萬平行雙語句對，漢語平均句長15.01，英語平均句長13.84。本文計算BLEU值的測試語料是單獨準備的500句漢英互譯句對；計算詞語對齊質(zhì)量的測試語料是經(jīng)過人工標注詞語對齊結(jié)果的500句漢英互譯句對。訓練語料和測試語料需要經(jīng)過分詞和大小寫轉(zhuǎn)化的預處理。

2）開源工具

實驗中采用的自動分詞軟件是斯坦福分詞工具2008版；采用的句法分析器是斯坦福句法分析器2007版，標注集為賓州樹庫標注集，采用賓州樹庫來統(tǒng)計短語結(jié)構(gòu)樹距離。采用的語言模型工具為Srilm1.5.5版［11］和LDC免費Web－1TB三元語言模型語料。機器翻譯自動評測工具采用了NIST的mt－evaluation1.1版①http：／／www.nist.gov／speech／tools／，利用BLEU－四元語言模型評測［12］。

實驗中采用了兩種詞語對齊模塊，一個是Giza＋＋模塊，一個是改進的HMM詞語對齊模塊，這兩個模塊的輸入輸出格式相同。輸入是雙語平行語料，輸出是Giza＋＋格式的雙向最優(yōu)詞語對齊結(jié)果。

3）實驗及結(jié)果分析

實驗1 用實例來分析改進HMM對不同位置目標詞概率的影響。根據(jù)改進HMM，在給定前一個對齊位置的條件下，可以計算下一個對齊位置的概率。

圖2給出漢語與英語的詞對齊和英語的短語結(jié)構(gòu)樹。圖3是在給定“減輕”的對齊位置為“relieve”，計算“對”的不同對齊位置的概率信息，橫坐標中的0表示“relieve”節(jié)點，其他橫坐標為其他節(jié)點相對于“relieve”的串的距離，縱坐標為對齊到該節(jié)點的概率?？梢钥闯鰧τ谡_的對齊位置“on”節(jié)點3，改進的HMM給出更高的得分。從效果看，改進的HMM對概率分布函數(shù)進行了平滑，即源語言串上相近的兩個詞在目標語言較遠的對齊位置的概率增加了。

圖2 英語短語結(jié)構(gòu)樹及詞匯對齊

圖3 “對”的不同對齊位置概率

實驗2 根據(jù)對齊錯誤率AER比較HMM和改進的HMM的詞語對齊質(zhì)量；詞語對齊結(jié)果的評測采用準確率P，召回率R和對齊錯誤率AER［13］。

其中A為各個模型給出的測試集的詞對齊集，G為測試集的正確詞對齊集。

表1給出了兩種詞語對齊模型的評測結(jié)果。從表1中可看出，改進HMM的詞對齊準確率較高，詞對齊錯誤率較小。從基本HMM到改進HMM，詞對齊的準確率有所增加，召回率有所降低，詞對齊錯誤率有所降低。這說明短語結(jié)構(gòu)樹距離對于提高詞語對齊質(zhì)量，降低詞對齊錯誤率確實有幫助。但同時，考慮短語結(jié)構(gòu)樹距離的HMM使得詞語對齊召回率降低。

表1 兩種詞語對齊模型的評測結(jié)果

實驗3 比較兩種詞語對齊結(jié)果對統(tǒng)計機器翻譯系統(tǒng)BLEU值的影響。實驗結(jié)果見表2。

表2 兩種詞語對齊模型對翻譯系統(tǒng)的影響

從基本HMM到改進的HMM，參考集、測試集和平均值的BLEU值都增加了，這說明從基本HMM到改進的HMM，統(tǒng)計機器翻譯質(zhì)量有所提高。改進的HMM與基本HMM相比，確實說明短語結(jié)構(gòu)樹距離對提高機器翻譯質(zhì)量有幫助。

5 結(jié)論

對于雙語的詞語對齊，本文提出了改進的HMM。改進的HMM把源語言詞在目標語言的對齊位置的串距離和短語結(jié)構(gòu)樹距離融合起來進行詞語對齊。實驗結(jié)果表明，改進的HMM可以減少句法和詞語對齊沖突，提高對齊準確率，降低對齊錯誤率，從而提高機器翻譯質(zhì)量。

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

［2］ Heidi J Fox.Phrasal cohesion and statistical machine translation［C］／／Proceedings of the 2002Conference on Empirical Methods in Natural Language Processing，Philadelphia，USA，2002：304－311.

［3］ Stephan Vogel，Hermann Ney，Christoph Tillmann.HMM－based word alignment in statistical translation［C］／／Proceedings of the 16th International Conference on Computational Linguistics Proceedings，1996：836－841.

［4］ Franz Josef Och，Hermann Ney.A systematic comparison of various statistical alignment models［J］.Computational Linguistics，2003，29（1）：19－51.

［5］ Adam Lopez，Philip Resnik.Improved HMM alignment models for languages with scarce resources［C］／／Proceedings of ACL－2005：Workshop on Building and Using Parallel Texts—Data－driven machine translation and beyond.University of Michigan，Ann Arbor，2005：83－86.

［6］ Colin Cherry，Dekang Lin.Soft syntactic constraints for word alignment through discriminative training［C］／／Proceedings of the Coling／ACL 2006Main Conference Poster Sessions，Sydney，2006：105－112.

［7］ Yang Liu，Qun LIU，Shouxun LIN，Log－linear Models for Word Alignment［C］／／Proceedings of the 43rd Annual Meeting of Association of Computational Linguistics，Michigan，2005：25－30.

［8］ 常寶寶.基于統(tǒng)計的翻譯等價詞對抽取研究［J］.計算機學報，2003，（5）：616－621.

［9］ 趙紅梅，劉群，等，漢英詞語對齊規(guī)范，中文信息學報，2009，23（3）：65－87。

［10］ 肖桐，李天寧，陳如山，等.面向統(tǒng)計機器翻譯的重對齊方法研究，中文信息學報，2010，24（1）：110－116.

［11］ Andreas Stolcke.SRILM—An Extensible Language Modeling Toolkit［C］／／Proceedings of International Conference on Spoken Language Processing.Denver，Colorado，2002.

［12］ Kishore Papineni，Salim Roukos，Todd Ward，et al.BLEU：a method for automatic evaluation of machine translation［C］／／Proceedings of the 40th Annual meeting of the Association for Computational Linguistics，Philadelphia，2002：311－318.

［13］ D Gildea.Loosely tree－based alignment for machine translation［C］／／Proceedings of the 41st Annual Meeting of Acl，2003：80－87.