漢英統(tǒng)計機器翻譯中Ａ^＊搜索算法研究與實現(xiàn)

摘要：分析了基于IBM Model 4的A*搜索算法和啟發(fā)函數(shù)，由于僅靠啟發(fā)函數(shù)難以找到最優(yōu)譯文，因此在搜索中采用了部分寬度搜索，以擴大搜索的范圍。將該算法應用于漢英統(tǒng)計機器翻譯中，實驗結果表明改進后的算法獲得了較好的翻譯質量和效率。

關鍵詞：統(tǒng)計機器翻譯； IBM模型； IBM Model 4； A*搜索算法； 啟發(fā)函數(shù)； 漢英機器翻譯

中圖法分類號：TP391．2； H085文獻標識碼：A

文章編號：1001－3695(2007)01－0020－05

1引言

當前機器翻譯的研究方法主要有基于規(guī)則的方法、基于統(tǒng)計的方法和基于實例的方法等，而基于統(tǒng)計的方法日益成為機器翻譯研究的熱點。基于統(tǒng)計的機器翻譯方法大體上分為以下三類：①基于平行概率語法的統(tǒng)計機器翻譯方法；②基于信源信道模型的統(tǒng)計機器翻譯方法，這種方法是由IBM公司的Peter F. Brown等人在1990年初提出的[1]，這也是目前最有影響的統(tǒng)計機器翻譯方法；③德國Och等人提出了基于最大熵的統(tǒng)計機器翻譯方法[2]，這種方法是比信源信道模型更一般化的一種模型。IBM公司提出了五種復雜程度遞增的數(shù)學模型[1，3]，簡稱為IBM Model 1~5。模型1僅考慮詞與詞互譯的概率；模型2考慮了單詞在翻譯過程中位置的變化；模型3考慮了一個單詞翻譯成多個單詞的情形，引入了繁殖概率；模型4在對齊時不僅僅考慮詞的位置變化，還考慮了該位置上的單詞（基于類的模型，自動將源語言和目標語言單詞劃分到若干類中）；模型5是對模型4的修正，消除了模型4中的缺陷（Deficiency），避免對一些不可能出現(xiàn)的對齊給出非零的概率。

搜索算法是統(tǒng)計機器翻譯的一個重要組成部分，它直接影響著翻譯的質量和效率。這方面研究頗受關注，出現(xiàn)了許多基于不同翻譯模型的解碼算法，如Wu，Tillman 和Wang， Waibel[4]所描述的算法是基于二元語言模型的，這些模型比較簡單，涉及的數(shù)據(jù)量也比較小；1998年Garc 和 Niessen 等人提出了基于 IBM2 Model DP算法[5]。基于IBM Model 4的解碼算法出現(xiàn)在德國，共有四種實現(xiàn)方法：①Berger等人描述過的堆棧法；②貪心搜索方法（Greedy Search）[6]，以近似解決為基礎，重復提高第一次粗略的解決方法；③基于動態(tài)規(guī)劃的柱搜索解碼算法[7]，這個方法利用了貨郎擔方法；④采用A*搜索算法[8]，使用了各種啟發(fā)式策略。

在A*搜索算法的研究中，Wang和Waibel提出了基于IBM2 Translation Model 的A*算法，Och等人提出了多個基于IBM Model 4的啟發(fā)函數(shù)[8]。本文基于IBM Model 4進行了漢英機器翻譯的研究，對Och的A*算法進行了研究和改進：在擴展節(jié)點時，不僅僅在啟發(fā)節(jié)點進行擴展，也在其他節(jié)點進行擴展，即進行部分的寬度搜索，這樣可以避免去掉那些啟發(fā)值不好但更合理的假設。將此改進算法應用到漢英翻譯系統(tǒng)中，實驗結果顯示改進后A*算法在系統(tǒng)中獲得了較好的翻譯結果和搜索效率。

2統(tǒng)計機器翻譯系統(tǒng)

目前一般所說的統(tǒng)計機器翻譯方法是指基于信源信道模型的統(tǒng)計機器翻譯方法。信源信道模型將翻譯問題看成是從噪聲通道中還原信號的過程，它可以這樣描述：將一個給定源語言文本(單詞序列)fJ1=f1…fj…fJ翻譯成一個目標語言文本(單詞序列)eI1=e1…ei…eI，就是要在所有可能的目標語言文本中找到概率值最高的目標語言文本作為最終的翻譯文本。其中，I是目標語言文本的長度，J是源語言文本的長度。由式（1），根據(jù)Bayes定律，得到式(2)。

其中，Pr(eI1)是目標語言文本eI1出現(xiàn)的概率，稱為目標語言的語言模型；Pr(fJ1|eI1)是由目標語言文本eI1翻譯成fJ1的概率，稱為翻譯模型。語言模型只與目標語言相關，與源語言無關，反映的是一個句子在目標語言中出現(xiàn)的可能性，實際上就是該句子在句法語義等方面的合理程度；而翻譯模型與源語言和目標語言均有關，反映的是兩個句子互為翻譯的可能性。

在這個模型下，統(tǒng)計機器翻譯要解決三個問題：語言模型Pr(eI1)的參數(shù)估計；翻譯模型Pr(fJ1|eI1)的參數(shù)估計；構建解碼搜索算法以尋找最優(yōu)譯文。因此，構建統(tǒng)計機器翻譯系統(tǒng)時，首先要通過訓練語料構建好語言模型和翻譯模型，然后在兩者的基礎上構建解碼器（搜索算法），輸入的源語言文本通過解碼器（搜索算法）利用翻譯模型和語言模型被翻譯成目標語言文本。以漢英翻譯系統(tǒng)為例，整個架構如圖1所示。

我們基于IBM Model 4進行漢英統(tǒng)計機器翻譯的研究。采用Model 4主要有兩個原因：①與其他對齊模型相比，模型4的對齊效果較好[12]；②在目標語言中對扭曲率的依賴可以在搜索過程中集成n元語言模型，而對于HMM模型來說，這點就比較困難[8]。

2．1IBM Model 4

IBM 翻譯模型是“詞—詞”的，即描述源語言單詞和目標語言單詞之間的對應關系。模型4將統(tǒng)計對齊模型分為五個模型，詳細情況可以參考文獻[1，3]。 

(1)語模型t(f |e)是將目標單詞e翻譯成f的概率。一個源語言單詞f可能翻譯成NULL單詞，NULL用e0表示。

(2)扭曲模型P=1(j-j′|C(fj)，E)是兩個連續(xù)目標單詞對應源單詞的位置差異為 j-j′翻譯的概率，如兩個連續(xù)目標單詞ei-1，ei。ei-1 所對應的源語言單詞的位置為 j′，ei所對應的源語言單詞的位置為 j，差異為 j- j′，C(fj)是源語言單詞 fj 的類，E是兩個連續(xù)目標單詞第一個詞ei-1的單詞類。

(3)扭曲模型P>1(j-j′|C(fj))是源單詞對應同一個目標單詞的位置差異 j-j′ 的概率。如果目標單詞ei的繁殖率大于1，它所對應的第一個源語言單詞位置為 j′；第二個目標單詞位置為 j， 位置差異為 j-j′；若第三個目標單詞的位置為 j″ ，位置差異為 j″-j 。

(4)繁殖模型n (|e)是單詞e與個源語言單詞對齊的概率。一個目標單詞e可能與= 0，1，2或更多個源語言單詞對齊。 

(5)空單詞繁殖模型P(0 |e0 )是0 個單詞沒有對齊的概率，即源語言單詞與空單詞(e0)對齊的概率。

2．2A*搜索算法的原理

對于統(tǒng)計機器翻譯而言，搜索算法是一個非常重要的問題。因為搜索空間一般都是隨著源語言句子長度的大小呈指數(shù)增長的，要在多項式時間內找到全局最優(yōu)解是不可能的。為了在盡可能短的時間內找到一個可接受的譯文，必須采用各種啟發(fā)式搜索策略。 

A*搜索算法是在一個給定的初始節(jié)點到一個給定的終止節(jié)點（或者經(jīng)過一個給定的終止節(jié)點）之間尋找路徑。它采用了啟發(fā)函數(shù)來估計最佳路徑經(jīng)過那個節(jié)點時的值來為節(jié)點進行排隊，然后按照估計值的順序來訪問節(jié)點。A*搜索也可以是最優(yōu)搜索（Bestfirst Search），A*搜索算法因為總是能夠保證找到最短的路徑，所以稱為可訪問的（Admissible）。如果啟發(fā)函數(shù)總是等于零，從不高估，則A*算法實際上是在執(zhí)行 Dijkstra的算法。

基本的A*搜索算法[9，10]可以概括描述如下：

(1)使用一個空假設初始化優(yōu)先級隊列。

(2)從優(yōu)先級隊列中取出最高的假設。

(3)如果這個假設是全局假設，輸出假設并中止。

(4)產(chǎn)生這個假設的所有擴展，并推入這個隊列中。

(5)轉（2）。

所謂啟發(fā)函數(shù)估計了部分假設所要完成的概率，則該函數(shù)被稱為可允許的，是指它不會低估概率。這樣，可容許的啟發(fā)函數(shù)總是優(yōu)化的。

3翻譯模型和語言模型的構建

出于現(xiàn)實效率的考慮，我們對短句的漢英翻譯進行了研究。用于建模的語料為55 839句對，主要是會話語料和體育類語料，90%以上的句子語法規(guī)范(Wellformed)。之所以使用特定的語料訓練是因為訓練相似的（主要是指詞匯相似和語法相似）語料所產(chǎn)生的有效數(shù)據(jù)比較集中，可以減少數(shù)據(jù)稀疏問題的影響。訓練前，首先對漢語語料進行分詞，英語語料中的標點符號要用空格分開。使用的知識庫還包括一個220 232單詞的漢英字典，涉及的英語單詞有129 787個，漢語詞有145 084個。漢語語料中，每個句子所包含的詞個數(shù)（分詞后）平均為7．892 26個；英語語料中，每個句子所包含的單詞個數(shù)平均為7.141 1個。漢語語料中，包含詞個數(shù)在10以下（包括10）的句子共有49 364個，約占88.4%；英語語料中，包含單詞個數(shù)在10以下（包括10）的句子為45 861個，占82.2%。句子包含的詞個數(shù)分布如圖2所示。

以上漢語語料和英語語料用于訓練翻譯模型。因為我們使用了Model 4，需要計算漢語和英語的詞類，先用MKCLS生成詞類；再使用GIZA++（約翰霍普金斯大學的統(tǒng)計機器翻譯1999夏季研討班開發(fā)的一個統(tǒng)計機器翻譯工具集EGYPT，其中包含了一個從雙語語料抽取統(tǒng)計知識的工具GIZA，GIZA++是其改進版）

訓練這些語料，得到Model 4的參數(shù)（這里的詞類是表示一個詞在語料中的分類，可根據(jù)需要設定），如表1所示。

表1翻譯模型的參數(shù)信息和規(guī)模

表2語言模型的參數(shù)和規(guī)模

4A*搜索算法在統(tǒng)計機器翻譯中的設計與實現(xiàn)

在統(tǒng)計機器翻譯中，路徑的評分標準變?yōu)槿∽畲笾担@是由統(tǒng)計機器翻譯的性質確定的，即取概率最大的節(jié)點。不管標準如何，基本的方法是一樣的。如果句子包含的詞個數(shù)超過10，A*的效率并不高[8]，這也是我們將研究對象限定在短句上的原因。在我們的實驗語料中，就句子包含詞的個數(shù)分布而言，短句占了大多數(shù)。通過前面我們對語料的分析可以得知，不管是漢語還是英語，含有10個詞以下（漢語指分詞后）的句子占了絕對多數(shù)。所以，我們在實驗中采用A*搜索算法是可行的。

4．1搜索圖的構建

在統(tǒng)計機器翻譯中，搜索算法從左至右構造譯文，當源語言的單詞位置均被覆蓋后，搜索終止。搜索時生成的部分翻譯（假設）存儲在一個或多個隊列中（區(qū)分的標準可根據(jù)需要制定）。我們的搜索算法中主要存有兩個隊列：還要進行擴展的隊列，標記為Open；不再進行擴展的隊列，標記為Closed。搜索空間可以構造為一個搜索圖，這個搜索圖包括初始節(jié)點、中間節(jié)點（部分假設）和目標節(jié)點（完全假設）。在我們的算法中，每個節(jié)點（假設）n至少包含以下信息：

(1)目標語言中的前置單詞u，v；

(2)前一個已翻譯源單詞的位置k′；

(3)一個標記，用來表明該節(jié)點所在隊列是在Open或是Closed；

(4)節(jié)點的祖先（Ancestor）；

(5)分值函數(shù)， G(n)+H(n)；

(6)為了直接判斷搜索是否終止，加入C(n)，表示已覆蓋的源語言單詞的集合，在漢英翻譯中是指已處理漢語詞的集合；

(7)已覆蓋的源語言單詞對應的英語翻譯。

每個節(jié)點包括目標語言的前綴單詞（已產(chǎn)生的部分英語翻譯）和相應的對齊關系（已覆蓋的漢語詞和對應的英語翻譯之間的關系）。每個節(jié)點通過處理下一個漢語詞來擴展到下一個節(jié)點，每次擴展都會帶來分值的變化。基于IBM Model 4時，分值需要考慮詞匯的翻譯率、繁殖率和扭曲率等，此外還要考慮語言模型分值的變化。

4．2對節(jié)點評分

每個節(jié)點就是某個時刻對翻譯的假設H，H可以這樣描述：

4．3基于啟發(fā)式函數(shù)的A*算法的搜索過程

下面以漢英翻譯為例來描述搜索過程。搜索的目標是為一個給定的漢語句子（分詞后）f1， f2，…， fJ ，其中J是該句子詞的數(shù)目，尋找一個較為合適的英語譯文。

(2)為每個漢語詞按照啟發(fā)函數(shù)計算初始分值，如式（5）所示。

這兩步在搜索中也可以實現(xiàn)，不過每次都要計算會耗費很多時間，所以可以預先計算好。

4．3．2搜索步驟

A*算法搜索的步驟如下：①按照分值大小擴展最優(yōu)節(jié)點，這個分值包括前綴分值和啟發(fā)分值。②不考慮啟發(fā)分值，按照前綴分值的大小去擴展其他節(jié)點。

有時候某個假設的啟發(fā)分值很高，但這并不意味著能得到最好的翻譯。因此我們可以不考慮啟發(fā)分值，按照前綴分值去擴展其他節(jié)點，這樣有些節(jié)點可能因為啟發(fā)分值低但卻是更好的假設而不會被漏掉。

擴展時，我們不但擴展分值最優(yōu)的節(jié)點，也擴展搜索圖中同一層次的節(jié)點，即它們所覆蓋的漢語詞的個數(shù)與最優(yōu)節(jié)點相同。通過進行部分的寬度搜索，可以找到更好的假設，第5．3節(jié)的實驗結果說明了該方法的效果。搜索算法如下：

前一個已翻譯的漢語詞的位置設為k′=0 ; C(n)={j}; ancestor=NULL;

按照式（3）計算前綴分值gH，按照式（5）和式（6）計算啟發(fā)函數(shù)值hH， fH=gH+hH

所有的假設按分值fH由大到小排序

（3）搜索終止

通過后面的實驗，步驟②中的d選取五個比較合適。在搜索的過程中假設數(shù)目增加很快，但實際中，假設的數(shù)目必須有所限制，一般是不超過一百萬個[8]，我們使用1 000個（數(shù)目越多翻譯質量越好，不過效率卻無法忍受）。如果達到限定的假設數(shù)目仍未找到目標節(jié)點，此時可以重新從起點搜索，但是這種做法會使得效率很低，也可能重復以前的搜索路徑。為提高搜索效率，我們不再重新從起點搜索，而是從|C(n)|最大的假設繼續(xù)搜索（限定的假設數(shù)目重新設為1 000）。盡管可能導致錯誤，但是卻提高了搜索效率，這是可容許的。在搜索過程中，如果兩個假設的語言模型和翻譯模型相同，就可以將兩個假設合并，保留分值較高的假設，去掉分值較低的假設，以加速搜索的進程。

5實驗及分析

我們通過實驗對算法進行了驗證。對實驗結果評判是通過人工來完成的，評測的標準是：翻譯的結果是否能夠傳達原文的意思，關鍵詞是否譯了出來，結構是否正確。

涉及的參數(shù)表示如下：L為假設隊列的最大長度，c是每個漢語詞的反向翻譯率最大值的倍數(shù)，n是每個漢語詞的候選英語單詞的最大數(shù)目，d是增加的擴展節(jié)點數(shù)目。

5．1實驗1

我們選出了500句語法規(guī)范的漢語，平均詞數(shù)目為6.3個，測試在通常的情況下，假設隊列中可以接受的最大假設數(shù)目對翻譯效果的影響。測試數(shù)據(jù)如表3所示（c=0．25，n=10，d=5）。

表3假設對列的大小L對翻譯的影響

我們采用的啟發(fā)函數(shù)可以保證高估剩余的耗費[5]。通常假設的數(shù)目增加得非常快，如果允許假設存在的數(shù)目越多，那么就越有可能按照啟發(fā)方向去尋找，避免錯誤的翻譯，但是所用的時間也會越長。因此必須兼顧效率和質量，我們看到當L=1 000是較為合理的設置。

5．2實驗2

在漢英翻譯中，我們?yōu)槊總€漢語單詞選擇候選英語單詞時，要設定參數(shù)的大小。我們測試了5 000句語法規(guī)范的漢語句子，平均包含的單詞個數(shù)為6.7個，實驗結果如表4、表5所示(L=1 000，d=5)。

表4n=20時，c的大小對翻譯的影響

表5n=10時，c的大小對翻譯的影響

在漢英翻譯中，一個漢語詞fj可能被表達成多種英語譯文ei， i=1， 2， …， i。i可能大于10，但是在漢語英語中這種情況并不多見，選取10個就足夠了。c太小會帶來很多錯誤的候選單詞，這些單詞可能對后面的翻譯造成干擾；c太大又會漏掉很多可能正確的單詞，影響譯文意義的表達。我們發(fā)現(xiàn)在c=0．25，n=10時翻譯的質量和效率相對而言較令人滿意。

5．3實驗3

漢語和英語是差別較大的語言，雖然通過實驗2我們可以對每個漢語單詞過濾掉大多數(shù)完全錯誤的翻譯，但其他差異（如位置扭曲）僅靠啟發(fā)函數(shù)并不能夠很好地解決，所以我們增加了擴展的節(jié)點，使系統(tǒng)有充分的選擇。選取的語料同實驗2，實驗結果如表6所示（L=1 000，c=0.25，n=10）。

表6增加擴展的節(jié)點數(shù)d對翻譯的影響

有些假設的啟發(fā)分值很高，但是按照這個方向搜索得到的翻譯并不好。例如得到的某個翻譯中，單詞翻譯的正確率可能比較高，但單詞之間的順序卻與期望的情況相差很遠。之所以會這樣，是因為我們采用的啟發(fā)函數(shù)總是高估剩余的耗費[5]，如對扭曲的情況，我們總是估計扭曲程度最大時的情況，事實上有時并沒有這么大的扭曲，所以按照這個方向搜索下去，得到的翻譯可能與正確的結果相差甚遠。因此我們在進行擴展時，不但擴展最優(yōu)節(jié)點，也根據(jù)前綴分值去擴展其他的節(jié)點，讓搜索有更多的選擇，這樣會緩解上述情況的出現(xiàn)。如果擴展的節(jié)點過多，會使搜索的時間延長；過少又可能會漏掉更好的假設。我們看到在限制的假設數(shù)目為1 000的情況下，擴展五個節(jié)點是一個比較合適的選擇。

6結論

我們對一個基于IBM Model 4的A*搜索算法進行了研究和改進，并將改進后的算法用到了漢英機器翻譯中。在實驗中，我們發(fā)現(xiàn)統(tǒng)計機器翻譯因為考慮到了單詞之間的關系(如翻譯率、繁殖率、扭曲率、目標語言單詞之間的關系等)，尋找目標單詞的正確率是比較高的。由于僅靠啟發(fā)式搜索可能會漏掉更好的譯文，因此我們在進行A*搜索的同時也進行了部分的寬度搜索，實驗證明翻譯的質量和效率相對更令人滿意。

通過實驗我們認識到，統(tǒng)計機器翻譯對語料庫的依賴性比較大，時空耗費非常大，在搜索中對于單詞重組耗費的時間比較多。雖然漢語和英語的差別非常大，但不是所有對應的單詞均存在位置的差異，所以還有很多優(yōu)化工作可以做。此外，單詞-單詞的模型并不能夠滿足漢英翻譯的要求，耗費的時間也比較長。所以使用某些規(guī)則或短語一級的對齊模型能達到更好的結果，這也是我們今后研究的方向。

參考文獻：

［1］Peter F Brown， John Cocke， Stephen A Della Pietra， et al. A Statistical Approach to Machine Translation [J]. Computational Linguistics，1990，16(2):7985.

［2］Franz Josef Och， Hermann Ney. Discriminative Training and Maximum Entropy Models for Statistical Machine Translation [C]. Proc. of ACL，2002.

［3］F Brown， S A Della Pietra， et al. The Mathematics of Statistical Machine Translation： Parameter Estimation[J]. Computational Linguistics， 1993，19(2)：263311.

［4］YeYi Wang， Alex Waibel.Decoding Algorithm in Statistical Machine Translation[C]. Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics， 1997.

［5］Niessen， Sonja， Stefan Vogel， et al. A DPbased Search Algorithm for Statistical Machine Translation[C]. Proceedings of the 36th Annual Conference of the Association for Computational Linguistics and the 17th International Conference on Computational Linguistics (ACL/COLING)，1998.960967.

［6］U Germann.Greedy Decoding for Statistical Machine Translation in Almost Linear Time[C].Edmonton:Proceedings of HLTNAACL，2003.

［7］Christoph Tillmann， Hermann Ney. Word Reordering and a Dynamic Programming Beam Search Algorithm for Statistical Machine Translation[J].Computational Linguistics， 2003，29(1):97133.

［8］Franz Josef Och， Nicola Ueffing， et al. An Efficient A* Search Algorithm for Statistical Machine Translation[C]. Toulouse: Proceedings of the DataDriven Machine Translation Workshop， the 39th Annual Meeting of the Association for Computational Linguistics (ACL)， 2001.5562.

［9］N Nilsson. ProblemSolving Methods in Artificial Intelligence[M]. New York: McGrawHill，1971.

［10］P E Hart， N J Nilsson， B Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths[J]. IEEE Transactions on Systems Science and Cybernetics， 1968，SSC4(2):100107.

［11］Franz Josef Och， Christoph Tillmann， et al. Improved Alignment Models for Statistical Machine Translation[C]. Proceedings of the Joint Conference on Empirical Methods in Natural Language Processing and Very Large Corpora (EMNLP/VLC)，1999.2028.

［12］Franz Josef Och， Hermann Ney. Statistical Machine Translation： From SingleWord Models to Alignment Templates[D]. RWTH Aachen，2002.

作者簡介：

魏瑾（1975），女，四川人，碩士研究生；王挺，教授，博導，主要研究方向為自然語言處理；周會平，副教授，主要研究方向為自然語言處理。

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文