基于最大熵短語重排序模型的特征抽取算法改進(jìn)

孫 萌，姚建民，呂雅娟，姜文斌，劉 群

(1. 中國科學(xué)院 計(jì)算技術(shù)研究所 智能信息處理重點(diǎn)實(shí)驗(yàn)室, 北京 100190;2. 蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 江蘇 蘇州 215006)

1 引言

基于短語的統(tǒng)計(jì)機(jī)器翻譯是當(dāng)前機(jī)器翻譯主流方法之一，翻譯的基本單元從詞過渡到短語，使得連續(xù)的詞串在翻譯過程中作為一個(gè)整體進(jìn)行處理，解決了詞的上下文依賴問題。翻譯的時(shí)候?qū)⑤斎氲木渥优c短語詞典進(jìn)行匹配，選擇最好的短語劃分，同時(shí)將得到的短語譯文重新排序，得到最優(yōu)的譯文。

其中，短語層次上重排序是基于短語機(jī)器翻譯的一個(gè)重要研究問題。

許多系統(tǒng)(如Pharaoh*http://www.isi.edu/licensed-sw/pharaoh/, 絲路*http://www.nlp.org.cn/project/project.php?proj_id=14) 采用扭曲模型概率調(diào)整目標(biāo)語言短語之間的次序，每個(gè)目標(biāo)短語的扭曲概率可以根據(jù)當(dāng)前目標(biāo)短語的源語言短語的起始位置與前一個(gè)目標(biāo)短語的源語言短語最后位置之間的距離計(jì)算。顯然這種簡單的基于懲罰長度的策略[1]會(huì)影響短語重排序模型的正確率。將句法知識(shí)引入機(jī)器翻譯系統(tǒng)，可以有效地改進(jìn)重排序的正確率[2-3]。其中Wu[4]提出的括號(hào)轉(zhuǎn)錄文法在機(jī)器翻譯領(lǐng)域也得到了廣泛的應(yīng)用。但是由于括號(hào)轉(zhuǎn)錄文法并沒有包含語言知識(shí)，因而不能很好地預(yù)測(cè)兩個(gè)相鄰目標(biāo)短語的組合次序。Xiong et al.[5]在括號(hào)轉(zhuǎn)錄文法的基礎(chǔ)上利用雙語短語的邊界單詞作為特征進(jìn)行最大熵訓(xùn)練得到重排序模型，并通過計(jì)算相鄰雙語短語的特征獲得在保序和逆序下的概率，可以更好地預(yù)測(cè)相鄰短語之間的次序，從而有效地改善了翻譯系統(tǒng)的翻譯結(jié)果。

通過觀察基于最大熵短語重排序模型進(jìn)行最大熵訓(xùn)練的特征，發(fā)現(xiàn)保序短語實(shí)例特征的數(shù)量遠(yuǎn)大于逆序短語實(shí)例特征的數(shù)量，這是因?yàn)闈h語和英語的語序大致相同。利用最大熵實(shí)現(xiàn)短語的重排序也可以視為一個(gè)分類問題，即“保序類”和“逆序類”，而用以訓(xùn)練分類器的特征數(shù)據(jù)存在數(shù)據(jù)不平衡問題，將有可能影響分類器的實(shí)際分類效果。例如，選擇FBIS作為訓(xùn)練語料，基線特征抽取系統(tǒng)從中抽取 4 839 390條特征實(shí)例，其中保序特征實(shí)例占 82.7%，而逆序特征實(shí)例僅占17.3%。以所有特征實(shí)例中的10萬句子作為對(duì)重排序模型的開放式測(cè)試集，剩余數(shù)據(jù)作為最大熵訓(xùn)練集，測(cè)試結(jié)果顯示此重排序模型對(duì)保序特征的判斷準(zhǔn)確率97.55%，而對(duì)逆序特征的判斷準(zhǔn)確率僅為72.03%。另外，基于括號(hào)轉(zhuǎn)錄文法假設(shè)源語言端短語相鄰則目標(biāo)語言短語也相鄰，但是在實(shí)際的漢英句對(duì)中存在源語言短語相鄰而目標(biāo)語言短語不相鄰的情況。針對(duì)以上情況，本文從保序?qū)嵗x取策略、引入組合特征以及加入新的短語次序三個(gè)方面改進(jìn)最大熵的特征抽取算法，以提高重排序模型的判斷準(zhǔn)確率，最終達(dá)到提高翻譯質(zhì)量的效果。

2 基于最大熵短語重排序模型的統(tǒng)計(jì)機(jī)器翻譯

Wu[4]提出了一種基于括號(hào)轉(zhuǎn)錄文法的統(tǒng)計(jì)翻譯模型。簡化的括號(hào)轉(zhuǎn)錄文法僅包含以下兩種規(guī)則：

其中Rl為詞匯規(guī)則，表示將源語言短語x翻譯為目標(biāo)語言短語y。Rm為合并規(guī)則，源語言短語和目標(biāo)語言短語的順序可以表示為保序和逆序兩種。在短語調(diào)序過程中，可以為合并規(guī)則中的兩種不同順序設(shè)置先驗(yàn)的保序和逆序概率，這種方法忽略了不同源語言—目標(biāo)語言短語對(duì)之間的差異性。

Xiong et al.[5]對(duì)以上括號(hào)轉(zhuǎn)錄文法模型的調(diào)序模型進(jìn)行了改進(jìn)，提出了一個(gè)基于最大熵的括號(hào)轉(zhuǎn)錄文法的短語調(diào)序模型，即運(yùn)用最大熵模型進(jìn)行短語的調(diào)序：

其中，h為特征函數(shù)，θ為特征權(quán)重，o的取值為保序或逆序，并且選取短語的尾詞作為最大熵模型訓(xùn)練的特征。實(shí)驗(yàn)表明基于最大熵括號(hào)轉(zhuǎn)錄文法的短語調(diào)序模型的性能明顯優(yōu)于傳統(tǒng)的基于扭曲的短語調(diào)序模型和基于括號(hào)轉(zhuǎn)錄語法的調(diào)序模型。但是，從實(shí)驗(yàn)可以看出，保序?qū)嵗臄?shù)量要遠(yuǎn)高于逆序?qū)嵗臄?shù)量，可能會(huì)影響最大熵模型的性能。本文從重排序?qū)嵗槿∷惴ê吞卣鬟x擇兩方面切入，旨在解決最大熵訓(xùn)練數(shù)據(jù)不平衡問題。在實(shí)驗(yàn)中，將以采用基于最大熵調(diào)序模型的統(tǒng)計(jì)機(jī)器翻譯系統(tǒng)Bruin[5]作為基線系統(tǒng)。

3 改進(jìn)的重排序?qū)嵗槿∷惴?/h2>

本文改進(jìn)了最大熵短語重排序系統(tǒng)中重排序?qū)嵗某槿∷惴?，在?shí)現(xiàn)上更加靈活簡潔并且易于擴(kuò)展，可以滿足實(shí)驗(yàn)中不同的抽取策略。

重排序?qū)嵗槿∷惴ǖ妮斎胧且粋€(gè)經(jīng)過GIZA++*http://code.google.com/p/giza-pp/雙向?qū)R的詞語對(duì)齊矩陣，輸出是保序短語實(shí)例和逆序短語實(shí)例。

抽取算法首先遍歷源語言端所有連續(xù)單詞序列，并抽取與此連續(xù)序列相對(duì)齊的目標(biāo)語言最大跨度。然后過濾不滿足對(duì)齊一致性的目標(biāo)語言單詞序列與源語言單詞序列，即依次反向掃描目標(biāo)語言的跨度，檢查其對(duì)應(yīng)的源語言跨度是否在原連續(xù)單詞序列范圍內(nèi)。最后，按照給定的不同抽取策略，抽取出重排序?qū)嵗?/p>

3.1 變量定義

介紹重排序?qū)嵗槿∷惴ㄖ?，首先定義與算法相關(guān)的變量。

(1)alignset

存放源語言到目標(biāo)語言所有的對(duì)齊矩陣。

(2)straightset

存放目標(biāo)語言短語保序次序?qū)嵗募稀?/p>

(3)invertedset

存放目標(biāo)語言短語逆序次序?qū)嵗募稀?/p>

(4)elseset

存放源語言短語相鄰目標(biāo)語言短語不相鄰的實(shí)例。

(5)src_span[i,j]

源語言從i到j(luò)的連續(xù)單詞序列。

(6)span[i,j]

記錄源語言i到j(luò)的連續(xù)單詞序列以及對(duì)應(yīng)目標(biāo)語言的連續(xù)單詞序列。

3.2 算法實(shí)現(xiàn)

本算法首先獲得任意源語言src_span[i,j]對(duì)應(yīng)的最大對(duì)齊矩陣 span[i,j]，然后過濾不合法的span[i,j]。最后對(duì)重排序?qū)嵗M(jìn)行分類以及抽取實(shí)例特征。具體步驟見算法1。

算法1改進(jìn)的重排序?qū)嵗槿∷惴?/p>

1.Input: 雙語詞對(duì)齊矩陣A

2.Initial(alignset，straightset，invertedset，elseset)；

3.Foreach(src_span[i,j]∈s)do

4. 獲取src_span[i,j]所對(duì)應(yīng)的目標(biāo)語言的對(duì)齊矩陣span[i,j]，同時(shí)將span[i,j]存入alignset中；

5. End for

6. Foreach(span[i,j]inalignset)

7. 檢查span[i,j]的對(duì)齊一致性，刪除不一致的span[i,j]；

8. End for

9. Foreach(span[i,j]inalignset)

10. Foreach(i≤mid

11. if (span[i,mid],span[mid+1,j]滿足保序規(guī)則Si)

12.straightset.push_back(span[i,j]);

13. else if(span[i,mid],span[mid+1,j]滿足逆序規(guī)則Ii)

14.invertedset.push_back(span[i,j]);

15. else

16.elseset.push_back(span[i,j]);

17. End for

18. End for

算法第9行到17行，描述的是改進(jìn)的抽取實(shí)例算法的框架，基于此框架可以方便制定各種抽取規(guī)則。其中第10行對(duì)抽取出來的雙語詞對(duì)齊矩陣，檢查是否可以將其拆分成兩個(gè)相鄰雙語短語對(duì)，并判斷拆分后的相鄰雙語短語對(duì)的組合順序。第16行，本算法引入了一個(gè)新的分類，即不相鄰雙語短語對(duì)。

3.3 重排序?qū)嵗x擇策略

基線系統(tǒng)采用了簡單的方法控制重排序?qū)嵗臄?shù)量，即在保序?qū)嵗袃H保留最小塊，對(duì)于逆序?qū)嵗齼H保留最大塊。顯然，這樣會(huì)損失一些短語邊界特征，并且保序?qū)嵗臄?shù)量依然遠(yuǎn)超逆序?qū)嵗臄?shù)量。這種特征數(shù)據(jù)的不平衡會(huì)影響最大熵重排序模型的判斷準(zhǔn)確率，特別是對(duì)逆序?qū)嵗卣鞯呐袛唷Ｒ?0萬條實(shí)例進(jìn)行開放式測(cè)試，其中逆序?qū)嵗龜?shù)量為 17 286，對(duì)逆序?qū)嵗臏y(cè)試精度僅為72.03%。本文在3.1節(jié)提出的算法框架下，對(duì)重排序?qū)嵗x擇策略依次進(jìn)行以下3點(diǎn)嘗試：

1) 為了解決最大熵訓(xùn)練過程中特征數(shù)據(jù)的不平衡，最為直接的想法即是采取一定的選擇策略直接限制保序?qū)嵗臄?shù)量。相比基線系統(tǒng)選擇保序?qū)嵗凶钚K，本文采用隨機(jī)算法選擇保序?qū)嵗龜?shù)量，避免了前種方法可能導(dǎo)致的長短語邊界特征的缺失。

2) 在雙語句子中會(huì)出現(xiàn)源語言短語相鄰而目標(biāo)語言短語不相鄰現(xiàn)象，針對(duì)這種情況，本文在1的基礎(chǔ)上增加一個(gè)新分類，從一定程度上減輕特征數(shù)據(jù)的不平衡。抽取出來的實(shí)例，如果不屬于保序和逆序類，即可將此實(shí)例歸為一類。

3) 由于giza++對(duì)齊結(jié)果存在錯(cuò)誤對(duì)齊，對(duì)實(shí)例擴(kuò)展未對(duì)齊詞會(huì)提高短語特征抽取的召回率。這里定義保序、逆序規(guī)則Si、Ii，i={0,1}；其中當(dāng)i=0，表示未對(duì)抽取實(shí)例進(jìn)行未對(duì)齊詞擴(kuò)展；i=1，表示對(duì)抽取實(shí)例進(jìn)行未對(duì)齊詞擴(kuò)展。

4 特征抽取

從重排序?qū)嵗谐槿√卣?，以進(jìn)行最大熵訓(xùn)練。重排序?qū)嵗梢杂?b1,b2>表示，其中b=，c代表源語言短語，e代表目標(biāo)語言短語，b1和b2表示相鄰或者不相鄰短語。這里用c.h表示源語言短語的首單詞，c.t表示源語言短語的尾單詞，對(duì)于目標(biāo)短語e也采用同樣的定義。

基線系統(tǒng)考慮到特征抽取的規(guī)模，僅利用重排序?qū)嵗械奈苍~。在特征抽取實(shí)驗(yàn)中，除了以上四條尾詞特征，增加首詞特征和組合特征。

表1 重排序?qū)嵗奶卣?/p>

由于漢語和英語語法結(jié)構(gòu)的不同，在漢語標(biāo)點(diǎn)符號(hào)前后的短語或子句， 其對(duì)應(yīng)的英語翻譯有可能將此短語或子句逆序組合表達(dá)。基線系統(tǒng)的解碼方法是，如果在重排序窗口中搜索到標(biāo)點(diǎn)符號(hào)，則此窗口將不做逆序操作。此方法對(duì)于對(duì)稱符號(hào)，譬如“《》”“{}”是相當(dāng)有效。但對(duì)“，”并不能以此簡單判斷。本文在增加重排序?qū)嵗自~特征和組合特征的基礎(chǔ)之上，添加標(biāo)點(diǎn)符號(hào)特征，以進(jìn)行最大熵訓(xùn)練。

5 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)中語言模型采用N-gram 統(tǒng)計(jì)語言模型, 使用 LDC*http://www.ldc.upenn.edu/發(fā)布的GigaWord 新華社部分作為訓(xùn)練英語語言模型的單語語料；采用統(tǒng)計(jì)機(jī)器翻譯領(lǐng)域公認(rèn)的成熟開源語言模型訓(xùn)練工具SRILM進(jìn)行N-gram 語言模型的訓(xùn)練。實(shí)驗(yàn)采用規(guī)模為518M的四元語言模型。

基于重排序?qū)嵗槿∷惴?，我們?cè)O(shè)計(jì)了7個(gè)對(duì)比實(shí)驗(yàn)，以對(duì)比不同特征抽取策略對(duì)最大熵訓(xùn)練的影響以及對(duì)最終翻譯結(jié)果得分BLEU值的影響。選擇FBIS作為訓(xùn)練語料，抽取短語表以及重排序?qū)嵗?，其中語料規(guī)模大約為23.9萬句對(duì)。以NIST MT 02作為實(shí)驗(yàn)的開發(fā)集，NIST MT 05作為測(cè)試集。

5.1 特征抽取策略對(duì)重排序結(jié)果的影響

選擇重排序?qū)嵗卣鲾?shù)據(jù)中的10萬條記錄作為最大熵重排序模型的開放測(cè)試集，表2顯示了從訓(xùn)練數(shù)據(jù)中抽取的重排序?qū)嵗囊?guī)模、排序分類、各分類所占比例、測(cè)試精度和抽取的特征。其中，測(cè)試精度為最大熵分類器正確判斷樣本的數(shù)量與測(cè)試集樣本總數(shù)量的比值。

其中，實(shí)驗(yàn)1是基線系統(tǒng)，沒有對(duì)保序?qū)嵗臄?shù)量進(jìn)行限制，實(shí)驗(yàn)2～7限制保序?qū)嵗龜?shù)量是逆序數(shù)量的2倍；實(shí)驗(yàn)2～4抽取實(shí)例時(shí)沒有對(duì)未對(duì)齊詞進(jìn)行擴(kuò)展，而實(shí)驗(yàn)5～7均進(jìn)行未對(duì)齊詞擴(kuò)展；實(shí)驗(yàn)4、5增加一個(gè)新的分類。

由于不同實(shí)驗(yàn)需要的特征不一致，所以只能確定測(cè)試集的數(shù)量，而不能確保測(cè)試集的內(nèi)容的一致性，因此不能簡單的將最大熵重排序模型的測(cè)試精度高低反映為翻譯性能的高低，但仍然可以將最大熵重排序模型的測(cè)試精度作為一個(gè)參考指標(biāo)。

表2 重排序?qū)嵗囊?guī)模、排序分類、測(cè)試精度和抽取的特征

從表2中可以看出，實(shí)驗(yàn)1的測(cè)試精度達(dá)到最高值93.9% ，實(shí)驗(yàn)2由于限制了保序?qū)嵗臄?shù)量，使得抽取出來的實(shí)例總量與實(shí)驗(yàn)1相比下降70%，導(dǎo)致最大熵訓(xùn)練的數(shù)據(jù)量不充足，因此測(cè)試精度僅有86.5%?？紤]到在實(shí)例數(shù)量減少的情況下，需要增加單個(gè)實(shí)例產(chǎn)生的特征數(shù)據(jù)量，所以在試驗(yàn)3中，對(duì)實(shí)例繼續(xù)加入首詞特征和組合特征，測(cè)試精度達(dá)到92.8%。但是源語言短語相鄰，并不表明目標(biāo)語言短語相鄰，于是實(shí)驗(yàn)4引入第三類別，即目標(biāo)語言短語不相鄰的情況。實(shí)驗(yàn)4的測(cè)試精度卻下降至76.9%，這是因?yàn)樾略龅囊粋€(gè)分類也增加了最大熵重排序模型判斷的不確定性。實(shí)驗(yàn)5在實(shí)驗(yàn)4的基礎(chǔ)上，擴(kuò)展未對(duì)齊詞，以增加實(shí)例的數(shù)量，但是實(shí)驗(yàn)結(jié)果比實(shí)驗(yàn)4略低。實(shí)驗(yàn)4和實(shí)驗(yàn)5均是在實(shí)驗(yàn)3的基礎(chǔ)上，引入第三類而導(dǎo)致測(cè)試精度有較大下降，從一定程度上說明第三類的引入不會(huì)提高最大熵模型判斷準(zhǔn)確率。因此，本文設(shè)計(jì)實(shí)驗(yàn)6，在實(shí)驗(yàn)3的基礎(chǔ)上擴(kuò)展未對(duì)齊詞；實(shí)驗(yàn)7，在實(shí)驗(yàn)6的基礎(chǔ)上引入標(biāo)點(diǎn)符號(hào)特征。這兩組實(shí)驗(yàn)的測(cè)試精度僅比實(shí)驗(yàn)1略低。

本文更關(guān)注特征抽取策略對(duì)于最大熵模型判斷逆序?qū)嵗恼_率，圖1顯示最大熵重排序模型對(duì)測(cè)試集中保序子集(Mono)和逆序子集(Invert)的測(cè)試精度。

圖1 保序子集和逆序子集的測(cè)試精度

對(duì)測(cè)試集中的保序?qū)嵗蛹M(jìn)行測(cè)試，除了實(shí)驗(yàn)4、5因引入新分類而導(dǎo)致對(duì)保序特征判斷的不確定性增大，實(shí)驗(yàn)2、3、6、7與實(shí)驗(yàn)1的測(cè)試精度相差不超過4%。觀察測(cè)試集中的逆序?qū)嵗蛹臏y(cè)試結(jié)果，實(shí)驗(yàn)2因?yàn)槟嫘蛱卣鞯挠?xùn)練數(shù)據(jù)量較少，以致于對(duì)逆序?qū)嵗蛹臏y(cè)試精度較低，而實(shí)驗(yàn)3、4、5、6、7均比實(shí)驗(yàn)1在逆序?qū)嵗蛹木雀?。其中，?shí)驗(yàn)6、7的測(cè)試精度比實(shí)驗(yàn)1高達(dá)16%。

從以上實(shí)驗(yàn)數(shù)據(jù)可以看出，本文提出的最大熵重排序模型特征抽取算法解決了由于特征數(shù)據(jù)不平衡導(dǎo)致最大熵模型對(duì)逆序特征判斷不準(zhǔn)確的情況。

5.2 翻譯結(jié)果對(duì)比

在NIST MT 05上測(cè)試大小寫敏感的BLEU值，圖2顯示7組用不同特征數(shù)據(jù)訓(xùn)練出來的最大熵重排序模型對(duì)最終翻譯效果的影響。

圖2 不同最大熵重排序模型對(duì)BLEU值影響

基線系統(tǒng)實(shí)驗(yàn)1的BLEU值為0.228 3。從上圖可以看到，除了實(shí)驗(yàn)2因特征訓(xùn)練數(shù)據(jù)過少以致最大熵重排序模型在翻譯過程中性能有較大下降，實(shí)驗(yàn)3、4、5、6均基于實(shí)驗(yàn)2添加特征信息，并且在限制保序?qū)嵗龜?shù)量的同時(shí)重排序模型的性能均比基線系統(tǒng)高，其中實(shí)驗(yàn)4因引入“不相鄰”分類翻譯性能有所下降但是BLEU值仍高于基線系統(tǒng)，實(shí)驗(yàn)7加入標(biāo)點(diǎn)特征，翻譯的BLEU值達(dá)到最高值0.234 8。本文提出的重排序?qū)嵗槿∫约疤卣鞒槿∷惴ǎㄟ^限制保序?qū)嵗龜?shù)目和增加特征數(shù)量，可以顯著提高重排序模型的性能從而提高翻譯質(zhì)量。

6 總結(jié)以及下一步工作

本文提出一種新的重排序?qū)嵗槿∷惴?，并在此基礎(chǔ)上加入新的特征，取得較好翻譯效果。首先，通過限制保序?qū)嵗臄?shù)目直接解決最大熵訓(xùn)練過程中的數(shù)據(jù)不平衡問題，由于特征信息過少而導(dǎo)致翻譯性能下降。在此基礎(chǔ)上，增加首詞特征、組合特征翻譯性能得到提高。其次，引入第三類短語組合順序，即保序逆序之外的不相鄰情況，雖然BLEU值有所下降但仍然高于基線系統(tǒng)。最后，本文在實(shí)驗(yàn)中嘗試擴(kuò)展對(duì)齊短語中的未對(duì)齊詞，增加重排序?qū)嵗卣鲾?shù)據(jù)量，翻譯性能達(dá)到最好。

下一步工作我們將繼續(xù)研究重排序?qū)嵗卣鲗?duì)翻譯性能的影響，重點(diǎn)在于融合句法知識(shí)特征，希望可以進(jìn)一步提高翻譯性能。此外，我們將深入探索基于括號(hào)轉(zhuǎn)錄語法框架下解碼器的改進(jìn)，以致可以處理源語言短語相鄰而目標(biāo)語言短語不相鄰的情況。

[1] 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, Americas, 2004: 115-124.

[2] Kenji Yamada and Kevin Knight.. A Syntax-based Statistical Translation Model[C]//Proceedings of ACL, Toulouse, France, 2001: 523-530.

[3] David Chiang. A Hierarchical Phrase-based Model for Statistical Machine Translation[C]//Proceedings of ACL, Ann Arbor, Michigan, 2005: 263-270.

[4] Dekai Wu. Stochastic Inversion Transduction Grammars and Bilingual Parsing of Parallel Corpora[J]. Computational Linguistics,1997, 23:377-403.

[5] Deyi Xiong, Qun Liu, and Shouxun Lin. Maximum Entropy Based Phrase Reordering Model for Statistical Machine Translation[C]//Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, Sydney, Australia, 2006: 521-528.