殷 樂，張玉潔，徐金安

（北京交通大學(xué) 計算機學(xué)院，北京100044）

1 引言

目前層次短語模型是統(tǒng)計機器翻譯（SMT）中性能最好的模型之一［1－5］，它可以有效提高翻譯質(zhì)量。但是由于該模型允許在短語中存在變量，造成短語表的規(guī)模急劇增大，解碼的時間和空間消耗劇增。為了緩解這一問題，本文提出一種基于虛擬上下文的SMT短語表過濾方法，可以有效過濾短語表中冗余的短語對，減少解碼在時間和空間上的過度消耗。

為了描述我們在短語表過濾上的工作，先簡單介紹基于短語的SMT中相關(guān)的內(nèi)容。短語表是SMT中基本的翻譯知識，包含大量的短語對，每個短語對由源語言短語和目標(biāo)語言短語組成。在構(gòu)建基于短語的統(tǒng)計機器翻譯系統(tǒng)時，需要從平行語料中自動抽取出短語表［6］，并利用目標(biāo)語言的單語語料庫訓(xùn)練目標(biāo)語言模型。這個構(gòu)建模型的過程通常稱為訓(xùn)練。在翻譯時，一個源語言句子首先被分割為短語序列，然后通過短語表，每個短語被翻譯成目標(biāo)語言的短語，最后這些目標(biāo)語言的短語被重新組合生成一個目標(biāo)語言句子。這個翻譯的過程通常被稱作解碼，解碼的模塊被稱作解碼器。解碼器會從候選譯文中選取擁有最大概率的譯文作為最后的輸出。

對于一個源語言句子fJ1＝f1…fj…fJ，一個目標(biāo)語言句子eI1＝e1…ei…eI，F(xiàn) J Och和 H Ney［7］提出基于最大熵的SMT模型如式（1）所示。

其中，hm（eI1，fJ1）是特征函數(shù)（m＝1，2，3，...M），λm是特征函數(shù)的權(quán)重。因為式（1）中的分母在解碼過程中是常數(shù)，最優(yōu)的譯文可以通過式（2）選出。

譯文的得分可以通過式（3）計算得到。

解碼的任務(wù)是尋找擁有最大概率的譯文，解碼已經(jīng)被證明是一個NP完全問題［8］。一個大規(guī)模的短語表將會造成解碼在時間和空間上的過度消耗，并且影響機器翻譯系統(tǒng)的實際應(yīng)用。特別是將這樣一個SMT系統(tǒng)移植到如PDA一類的移動終端時，幾乎是不可能的。

為了解決這個問題，許多研究人員提出了多種過濾短語表的方法，主要集中于兩類短語對，即錯誤的短語對和冗余的短語對。為了過濾短語表中錯誤的短語對，研究人員提出一種使用對數(shù)似然比的過濾方法［9］和使用依存結(jié)構(gòu)限制目標(biāo)短語數(shù)量的方法［10］。為了過濾短語表中冗余的短語對，研究人員則提出一種過濾單調(diào)組合短語對的方法［11］和一種使用對數(shù)線性模型過濾組合短語對的方法［12］。

本文中我們提出一種基于虛擬上下文的過濾方法，目標(biāo)是過濾掉解碼過程中幾乎不會被使用的短語對。文中將這種短語對看作是冗余短語對。我們主要集中在兩種冗余短語對：同源短語對（ISP）和復(fù)合短語對（CPP）。同源短語對指的是那些源語言相同而目標(biāo)語言不同的短語對。這種短語對意味著同一個源語言短語有多個對應(yīng)的目標(biāo)短語，多的情況下會有幾十甚至上百個，這種情況下一般會含有冗余短語對。復(fù)合短語對是指短語對的源語言短語可以由幾個子短語組成，并且在短語表中存在以這些子短語作為源語言短語的短語對。這意味著一個復(fù)合短語對可以被幾個子短語對替換，出現(xiàn)這種情況時，這些復(fù)合短語對中可能含有冗余的短語對。

針對上述的冗余短語對，我們設(shè)計實現(xiàn)了短語表過濾器，其處理流程大致如下：首先，過濾器使用對數(shù)線性模型計算短語對的得分；然后，過濾器使用虛擬上下文對短語對進(jìn)行重排序；最后刪除掉排名低的短語對。

文章其他部分組織如下，第2節(jié)詳細(xì)描述基于虛擬上下文的過濾方法；第3節(jié)介紹我們的實驗和評價結(jié)果；最后給出我們的結(jié)論。

2 短語表過濾算法

這一節(jié)介紹使用對數(shù)線性模型對短語對進(jìn)行排序的過程，然后詳細(xì)描述基于虛擬上下文的重排序算法和過濾冗余短語對的策略。

2.1 排序

為了找出幾乎不會被解碼器使用到的短語對，我們使用和解碼器同樣的算法評價短語對。我們使用對數(shù)線性模型計算短語對的得分，使用的特征包括：翻譯概率、詞匯化概率、反向翻譯概率、反向詞匯化概率和語言模型。選用這五個特征的理由是短語對的質(zhì)量和這些特征密切相關(guān)。這些特征的權(quán)重通過開發(fā)集的數(shù)據(jù)訓(xùn)練得到。

過濾器對短語對排序的過程如下。

1）選擇擁有相同源語言的短語對作為一個集合，用Si表示；

2）按照式（3）計算Si中每個短語對的得分，得分最高的短語對表示為SHi，其他短語對表示為SOi，它們的得分分別為Score（SHi）和Score（SOi）。

2.2 基于虛擬上下文的重排序

通常來說，解碼器會選擇SHi，而不是SOi。可是SOi在某些情況下會被解碼器選擇。出現(xiàn)這種情況的原因可以解釋如下。在上文的利用式（3）的計算中，計算語言模型的得分的過程和解碼器的計算過程并不完全相同，因為解碼器會使用已生成的譯文作為上下文信息計算語言模型?？墒?，在短語表過濾階段，沒有實際生成的譯文供過濾器作為上下文計算。

由此，解碼器會因為已生成的譯文給SOi一個比SHi高的得分，導(dǎo)致過濾器和解碼器的排序結(jié)果不同。為了彌補這一點，我們在過濾器中引入虛擬上下文來計算語言模型并對短語對進(jìn)行重排序。這種策略可以保證，在重排序后低位短語對在實際解碼中基本不會被使用，過濾掉這些短語不會影響翻譯質(zhì)量。

進(jìn)一步描述，解碼器中已經(jīng)生成的譯文作為上下文信息在語言模型特征上會產(chǎn)生一個增量，表示為ΔContext。如果解碼器選擇SOi而不選擇SHi，是因為SOi的增量大于SHi，即當(dāng)式（4）成立時，解碼器會選擇SOi。

在式（4）中，ΔContext（SOi）和 ΔContext（SHi）是SOi和SHi分別通過上下文在語言模型特征上獲得的增量。

基于以上的考慮，我們設(shè)計了一種極端分配上下文的重排序策略，即分配給SOi最佳上下文使其獲得最大增量，而分配給SHi最差上下文使其獲得最小增量。在這種策略中，如果重排序后，SOi的排名依然低于SHi，那么可以說SOi就很難被解碼器選用。這種策略可以簡單表示為SOi與最佳上下文對決（vs）SHi與最差上下文。

為此，我們引入虛擬上下文模擬SHi的上下文，使得ΔContext（SHi）在語言模型上獲得最低的得分，同理使用虛擬上下文模擬SOi的上下文，使得ΔContext（SOi）在語言模型上獲得最高的得分。分別標(biāo)記它們?yōu)?minΔContext（SHi）和 maxΔContext（SOi）。然后，依據(jù)新得分重新排序短語對。如果Score（SHi）＋minΔContext（SHi）＞Score（SOi）＋ maxΔContext（SOi），這意味著解碼時，在任何上下文的情況下，SOi都很難被解碼器使用到。

短語表的過濾算法如下。

1）對于一個目標(biāo)語言短語W1W2……Wk，W1和 Wk是短語的邊界。如果Wx1Wx2在2元語言模型中存在并且δ（Wx2，W1）＝1，則把Wx1作為目標(biāo)語言短語的虛擬上下文；如果Wx1Wx2在語言模型中存在并且δ（Wk，Wx2）＝1，則把 Wx2作為目標(biāo)語言短語的虛擬上下文。δ（x，y）是克羅內(nèi)克函數(shù)，當(dāng)x＝y(tǒng)時，δ（x，y）＝1，否則δ（x，y）＝0。除此之外，我們同樣考慮了短語中包含變量的情況。給定一個目標(biāo)語言短語 W1……Wm－1X Wm……Wk，X是一個變量。Wm－1和 Wm也是短語的邊界。如果Wx1Wx2在語言模型中存在并且δ（Wm－1，Wx1）＝1，則把Wx2也作為目標(biāo)短語的虛擬上下文；如果Wx1 Wx2在語言模型中存在并且δ（Wx2，Wm）＝1，則把Wx1也作為目標(biāo)短語的虛擬上下文；

2）計算minΔContext（SHi）：在語言模型中分配一個上下文使得SHi獲得最小得分增量；

3）計算Si中的其他短語對的 maxΔContext（SOi）：在語言模型中分配一個上下文使得SOi獲得最大得分增量；

4）依據(jù)獲得增量的新得分，對Si中的短語對進(jìn)行重排序；

5）過濾掉排名低于SHi的短語對。

在這種極端上下文對比的情況下，排名低于SHi的短語對在其他上下文情況下也不會獲得更大增量，因此只能排在SHi的后面。這意味著在其他情況下，解碼器也不會跳過SHi而選擇排名低于SHi的短語對。由此，過濾掉這些短語，譯文的質(zhì)量不會受影響而下降。

下面描述對復(fù)合短語對（CPP）的過濾。復(fù)合短語對意味著它的源語言短語可以被分解成多個子短語，同時這些子短語的短語對在短語表中存在，我們稱這些短語對為子短語對。和同源短語的過濾算法一樣，這里也引入了虛擬上下文。過濾算法如下。

1）計算復(fù)合短語對的得分：根據(jù)式（3）先計算一個基礎(chǔ)得分，并在語言模型中分配一個上下文使得復(fù)合短語對的得分增量最大，二者相加作為復(fù)合短語對的得分。

2）計算子短語對的得分：根據(jù)式（3）先計算一個基礎(chǔ)得分，并在語言模型中分配一個上下文使得子短語對的得分增量最小，二者相加作為子短語對的得分。

3）過濾：如果子短語對的得分之和大于復(fù)合短語對的得分，過濾掉復(fù)合短語對。

在文獻(xiàn)［11－12］的方法中，他們的方法要求短語對（s1s2→t1t2）可以被過濾的一個前提是短語表中存在短語對s1→t1和s2→t2，即短語對（s1s2→t1t2）是單調(diào)組合的短語對［11］。我們過濾復(fù)合短語對（CPP）的方法和他們的方法不同，我們定義的復(fù)合短語對（s1s2→t1t2），我們只要求在短語表中同時存在源語言短語是s1和s2的短語對。

與前面過濾掉的同源短語對的道理相同，在這種極端上下文對比的情況下，復(fù)合短語對的得分低于子短語對的得分。這意味著在其他上下文的情況下，解碼器只會選擇子短語對，而不會選擇被過濾掉的復(fù)合短語對。因此，在過濾掉復(fù)合短語對后，翻譯質(zhì)量不會受影響而下降。

3 實驗

3.1 實驗設(shè)置

為了驗證本文的方法，我們使用一個基于層次短語解碼器，在NTCIR－9數(shù)據(jù)上進(jìn)行了中英方向的實驗。NTCIR－9中英數(shù)據(jù)的訓(xùn)練集中有一百萬句對，測試集和開發(fā)集分別有兩千句對。

我們在訓(xùn)練集上運行GIZA＋＋［13］得到雙向的單詞對齊信息，并使用啟發(fā)式的方法“grow－diag－final”［1］改善單詞對齊結(jié)果；利用單詞對齊信息，自動抽取短語表［6］。然后借助工具SRI language model［14］獲得語言模型；通過在開發(fā)集上使用最小錯誤率訓(xùn)練法［15］得到特征的權(quán)重。在評測譯文的質(zhì)量時，我們使用 BLEU［16］。

3.2 實驗結(jié)果

考慮實驗的便捷性，我們首先選出源語言短語在測試句子中出現(xiàn)的短語對，作為準(zhǔn)備過濾的短語表。

然后我們使用第2節(jié)介紹的方法，過濾ISP和CPP。表1是過濾前后短語表大小和翻譯質(zhì)量的變化。其中，第1列是過濾的方法（Filtering way），包括ISP、CPP和ISP＆CPP，None（baseline）是過濾前的情況。第2列是翻譯質(zhì)量（BLEU）。第3列是短語表消耗的內(nèi)存大?。≒TS）。第4列是短語表中短語對的數(shù)量（NUM）。第5列是過濾后剩余短語對的數(shù)量占原短語表的百分比（Reminder）。在過濾ISP后，剩余的短語對數(shù)量是原來數(shù)量的52.42%，同時BLEU值上升0.000 6。在過濾掉CPP后，剩余的短語對數(shù)量是原來數(shù)量的73.03%，同時BLEU值上升0.000 5。在過濾掉ISP和CPP后，剩余的短語對數(shù)量僅占原來數(shù)量的47.01%，同時BLEU同樣上升0.000 5。實驗結(jié)果顯示同時過濾ISP和CPP時，效果最好。

表1 過濾前后短語表大小和翻譯質(zhì)量的變化

為了進(jìn)一步壓縮短語表中的大小，我們考慮在ISP過濾中只保留重排序后排名較高的幾個短語對（表2）。

表2 ISP過濾中保留前5位（TOP 1～5）的情況下，短語表大小和翻譯質(zhì)量的變化

表2的結(jié)果顯示，保留ISP排名前五位的短語對獲得了最好的實驗結(jié)果。在過濾掉短語表中大約70%的短語對后，BLEU值僅下降0.000 6。該實驗結(jié)果也顯示，保留越少的ISP短語對，BLEU值下降的越快。在我們的實驗中，保留排名前五的ISP短語對獲得了最好的效果，既極大壓縮了短語表的規(guī)模又沒有給翻譯質(zhì)量帶來太大的影響。實驗證明這種方法在實際應(yīng)用中是有意義的。

在過濾的過程中我們計算短語的虛擬上下文最大與最小增量，由于在解碼時，一些n－gram在訓(xùn)練的語言模型中沒有出現(xiàn)，它們的得分是無法預(yù)知的。通常在測試集上，會利用回退和簡單平滑的方法處理這些n－gram。但是我們無法枚舉所有n－gram，這可能會造成本文方法計算的虛擬上下文最大與最小增量出現(xiàn)錯誤。因為我們不能得到系統(tǒng)在實際運行時，解碼器中生成譯文的情況，所以我們只針對測試集參考譯文計算了2－gram的稀疏情況。結(jié)果如表3所示。

表3 譯文2－gram在語言模型中的稀疏情況

由此可見，在2－gram的情況下，稀疏的情況的百分比只有11.53%。在大部分情況下，我們的方法計算出的結(jié)果應(yīng)該是正確的。

4 結(jié)論

在這篇文章中，我們提出一種基于虛擬上下文的過濾短語表的方法，通過引入虛擬上下文計算短語對在語言模型特征上獲得的最大和最小增量，并設(shè)計了對短語對進(jìn)行重排序的過濾策略。實驗結(jié)果顯示，這種方法可以過濾掉短語表53%的短語對，同時沒有造成翻譯質(zhì)量的下降。在保留重排序后前五名的短語對時，這種方法可以過濾掉70%的短語對，同時BLEU值僅有0.000 6的極微小的下降。實驗證明這種方法可以有效過濾掉短語表中冗余的短語對，極大壓縮短語表的規(guī)模。

在以后的工作中，我們將嘗試融合其他信息進(jìn)一步提升這種方法的有效性。

［1］Philipp Koehn，Och F J，Marcu D.Statistical Phrase－Based Translation［C］／／Proceedings of the 2003Human Language Technology Conference of the North A－merican Chapter of the Association for Computational Linguistics，2003：127－133.

［2］R Zens，F(xiàn) J Och，H Ney.Phrase－Based Statistical Machine Translation［C］／／Proceedings of M.Jarke，J.Koehler，G.Lakemeyer（Eds.）：KI－2002：Advances in artificial intelligence.25.Annual German Conference on AI，KI 2002，2002：18－32.

［3］Philipp Koehn.Pharaoh：a beam search decoder for phrase－based statistical machine translation models［C］／／Proceedings of the Sixth Conference of the Association for Machine Translation in the Americas，2004：115－124.

［4］D Chiang.A hierarchical phrase－based model for statistical machine translation［C］／／Proceedings of ACL 2005，2005：263－270.

［5］D Chiang.Hierarchical phrase－based translation［C］／／Proceedings of Computational Linguistics，2007，33（2）：201－228.

［6］F J Och，H Ney.The alignment template approach to statistical machine translation［J］.Computational Linguistics，2004，30（4）：417－449.

［7］F J Och，H Ney.Discriminative training and maximum entropy models for statistical machine translation［C］／／Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics （ACL），Philadelphia，PA，July 2002.

［8］K Knight.Decoding complexity in word replacement translation models［C］／／Proceedings of Computational Linguistics，1999，25（4）.

［9］Wu Hua，Haifeng Wang.Comparative Study of Word Alignment Heurist Based SMT［C］／／Proceedings of Machine Translation Summit XI，2007：507－514.

［10］L Shen，J Xu，R Weischedel.A new string－to－dependency machine translation algorithm with a target dependency language model ［C］／／Proceedings of ACL－08：HLT，Columbus，Ohio，2008：577－585.

［11］Z He，Y Meng，Y Lj，et al.Reducing SMT rule table with monolingual key phrase［C］／／Proceedings of the ACL－IJCNLP 2009Conference，Singapore，2009：121－124.

［12］Seung－Wook Lee，Dongdong Zhang，Mu Li，et al.Translation model size reduction for hierarchical phrase－based statistical machinetranslation［C］／／Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics（Volume 2：Short Papers），Jeju Island，2012：291－295.

［13］F J Och，H Ney.Improved statistical alignment models［C］／／Proceedings of the 38th Annual Meeting of the Association for Computational Linguistics，Korea，2000：440－447.

［14］A Stolcke.Srilm －an extensible language modeling toolkit［C］／／Proceedings of the International Conference on Spoken language Processing，volume 2，2002：901－904.

［15］F J Och.Minimum error rate training in statistical machine translation［C］／／Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics，2003：160－167.

［16］K Papineni，S Roukos，T 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，2002：311－318.