對數線性翻譯模型的判別式訓練綜述
2013-04-29 00:44:03劉樂茂趙鐵軍
智能計算機與應用 2013年6期
劉樂茂 趙鐵軍
摘要：目前幾乎所有的統(tǒng)計機器翻譯系統(tǒng)都采用對數線性模型建模. 判別式訓練是基于對數線性翻譯系統(tǒng)的一個重要組成部分，其任務就是優(yōu)化對數線性模型的參數。到現在為止，有很多判別式訓練方法可以用來訓練翻譯模型權重。從似然函數、錯誤率函數和可擴展方法三個方面，系統(tǒng)地闡述并分析了這些訓練方法，旨在讓更多的研究者更好地了解判別式訓練方法的發(fā)展現狀、為判別式訓練的進一步發(fā)展起到推動作用。同時，還就判別式訓練提出了兩個值得進一步探討的問題。
關鍵詞：統(tǒng)計機器翻譯； 對數線性模型； 判別式訓練
中圖分類號：TP391.2 文獻標識碼：A文章編號：2095-2163（2013）06-0014-04
0引言
統(tǒng)計方法[1]已經成為機器翻譯建模的主流方法，特別在Och和Ney[2]提出了基于對數線性模型的統(tǒng)計機器翻譯模型之后。目前，幾乎所有的統(tǒng)計機器翻譯系統(tǒng)都處于對數線性模型框架的支持和限定之下。與產生式的翻譯模型[1]相比，對數線性翻譯模型不需要考慮翻譯的生成過程，可直接采用判別式的統(tǒng)計模型建模；其最大優(yōu)點在于，能夠允許加入任意的翻譯特征。因而，可將翻譯的問題轉化為特征工程的問題，這就為翻譯系統(tǒng)的研究和設計帶來很大的便利。
假設f是一個源語言句子，e為其一個可能的翻譯。形式上，基于對數線性（最大熵）的翻譯模型[2]，可以表述如下：
P（e|f：W）=exp（∑iWi·hi（f，e））∑e′exp（∑iWi·hi（f，e′））（1）
其中，e′是f所有可能的一個翻譯；h1是雙語對（f，e）的特征，其取值為實數；W=
（f；W）=argmaxeP（e|f：W）=argmaxe∑iWi·hi（f，e）（2）
上式也稱為最大后驗解碼原則。那么如何事先確定這個參數W呢？其準則又是什么呢？這就是判別式訓練的問題。具體來說，判別式訓練的任務是，給定一個開發(fā)集，優(yōu)化得到一個合理的參數W，使得這個參數在測試時性能良好。
機器翻譯任務本身固有的一些特點，比如翻譯模型中的隱含變量和結構化的搜索空間等等，導致翻譯模型的參數估計存在很多困難。不過，經過數十年的發(fā)展歷程，大批研究者相繼提出了許多訓練方法，這些方法極大地推動了統(tǒng)計機器翻譯的進展。但是，據研究所知，目前還沒有工作就這些方法進行系統(tǒng)地闡述與介紹。本文中，將系統(tǒng)地回顧這些方法，同時就這些方法的優(yōu)缺點進行分析與討論，旨在使更多的研究者能夠深入了解判別式訓練方法的發(fā)展現狀、為判別式訓練的進一步發(fā)展起到基礎性地引領作用。
1基于似然函數的訓練方法
首先，為行文約定一些記號：設（f，e）為一個雙語對，其中f為源語言，e是其一個翻譯。給定開發(fā)集{fs，cs，rs}Ss=1，其中fs是開發(fā)集中的源語言句子，cs是fs的一個候選翻譯集合，rs是fs的參考譯文集，其中每個元素記為rks，k=1，…，Ls，Ls為rs中元素的個數。
既然是估計概率模型的參數，就必然不能缺少極大似然估計，因為這是概率模型參數估計的典型方法。事實上，在文獻[2]提出最大熵翻譯模型的框架時，其中采用的參數學習方法就是極大似然估計法。自然地，{fs，cs，rs}Ss=1上的對數似然函數的定義如下式：
∑Ss=11Ls∑Lsk=1logP（rks|fs；W）（3）
然而，由于某些rks是不可達的，這樣，無法計算其所對應的似然函數。Och 和Ney[2]采用如下的方法來近似上述似然函數，即從fs可達的那些翻譯中，比如對fs進行k-best解碼得到的譯文集cs都是可達的，從中選取若干個與參考譯文集最相似的譯文（依據句子級別的BLEU，定義相似度），作為偽參考譯文，這些偽參考譯文集記為eks，為方便起見，假設參考譯文集亦含有Ls個元素。那么基于偽參考譯文集的似然函數為：
∑Ss=11Ls∑Lsk=1logP（eks|fs；W）（4）
最小化公式（4）的一個難點是候選翻譯的指數級空間，而精確地計算公式（1）中的歸一化因子也很困難，因此，需要借助于合理的近似策略。 Och 和Ney[2]采用的方法是使解碼器輸出k-best候選翻譯集cs，并在cs上近似地計算歸一化因子。其后就是典型的優(yōu)化問題，通用優(yōu)化方法都可以實現公式（4）的優(yōu)化，比如梯度法，共軛梯度、擬牛頓法（LBFGS）等等，Och 和Ney[2]采用了GIS算法。
需要注意的是，由于似然函數是嚴格凸函數，最大似然估計方法可以為公式 （4）找到全局最優(yōu)解。盡管如此，這種方法在實際的翻譯任務中效果并不好，目前幾乎已經不再采用。然而，這種利用k-best候選翻譯來代替整個翻譯候選空間的思想，對后續(xù)的參數學習算法起著十分重要的作用。更具體地說，其后許多著名的參數學習算法都嵌入在這種框架之內，所不同的只是，這些算法采用的優(yōu)化目標各不相同而已。
2基于錯誤率的訓練方法
極大似然估計的一個缺點是，沒有直接利用翻譯的評價度量比如BLEU[3]，來作為優(yōu)化的目標函數，導致了優(yōu)化目標同翻譯評價度量之間的關系不太緊密、一致。
為此，Och 在2003年提出了最小錯誤率訓練（簡記，MERT）的方法[4]，其想法是，直接利用翻譯評價度量作為優(yōu)化的目標函數，以期能夠得到最優(yōu)的參數，使得在開發(fā)集上該參數得到的翻譯結果的BLEU 值最高。MERT是機器翻譯參數估計方法中最通用、最成功和最受歡迎的算法。在每屆翻譯評測中，幾乎所有的翻譯系統(tǒng)都采用MERT進行參數估計。形式上，MERT試圖解決如下的優(yōu)化問題：
minWE{rs，（fs；W）}Ss=1（5）
其中，（fs；W）表示在翻譯候選集cs中，根據權重W，按照最大解碼原則公式（2）而得到的一個翻譯。在式（5）中，E是一個篇章級的翻譯評價度量，表示翻譯文檔 {（fs；W）}Ss=1在參考譯文{rs}Ss=1下的評價得分，比如篇章級的BLEU；其他的記號如前所述。公式（5）的目標函數稱為錯誤率函數。由于公式（5）中的錯誤率函數不可導，甚至不連續(xù)，因而，一般的梯度方法并不適用，有效地求解公式（5）存在困難。
本質上說，MERT是一種特殊的Powell算法，可啟發(fā)式地選擇坐標向量作為搜索方向。該算法的思路是，每次都選用所有坐標向量作為搜索方向，然后沿著每個搜索方向進行線搜索（line search）得到一個點；比較所有坐標方向上的線搜索得到的點的目標函數值，選擇目標函數值最小的點作為下次迭代的起點；上述兩個步驟反復下去，直至算法收斂。MERT的最大貢獻在于，能夠在多項式的時間內執(zhí)行精確的線搜索（exact line search），也即是，在給定的方向上能夠找到該方向使目標函數值最小的點。MERT的精確線搜索可以解釋如下。假設開發(fā)集中僅僅含有一個句子，并假設當前的搜索方向是第j個坐標方向，公式（5）關于參數Wj是分段線性函數，而且函數至多有Ls個線性的片段。這樣，遍歷這個分段線性函數就可以找到最小值點Wmaxj。對于開發(fā)集含有多個句子的情況，只需要組合多個分段線性函數，算法的思想也與其類似。值得注意的是，雖然MERT在線搜索時，可以找到全局最優(yōu)的點，但是整個算法不能保證必定收斂到全局最小點。相似地，Zhao等[5]提出了另外一種非梯度的方法-單純型法最小化公式（5）。
由于公式（5）中的目標函數是非凸的，導致上述方法不可避免地陷入到局部最優(yōu)的境地。原始的MERT算法沒有考慮局部最優(yōu)的問題，這樣，如何避免性能不好的局部最優(yōu)點就自然成為一個重要的研究課題。Moore和Quirk[6]在MERT中引入了隨機初始點的策略以避開性能不好的局部最優(yōu)點。具體來說，就是在MERT迭代過程中，定義了兩種隨機方法，這兩種方法不同之處在于產生隨機初始點的方式不同。第一種方法是隨機初始化，是按照均勻分布產生多個初始點，對每個初始點都運行一遍MERT，就可以得到多個局部最優(yōu)點，再比較這幾個局部點對應的BLEU值，選擇BLEU值最高的那個局部最優(yōu)點。第二種方法是隨機行走，是在上次選擇的局部點的基礎上，引入標準的高斯噪聲，抽樣出一個處于局部點周圍的初始點，并運行MERT得到另外一個局部最優(yōu)點，再比較新舊兩個局部對應的BLEU值，以決定是否接受新的局部最優(yōu)點。Galley和Quirk[7]則利用組合優(yōu)化的方法，尋找到公式（5）的全局最優(yōu)解。其主要思想同MERT中的精確線搜索相似，不同于MERT中精確線搜索的地方就在于求解一個一維的分段線性函數，并計算一個多維的分段線性函數。換句話說，該方法不是按照某一個坐標向量計算公式（5），而是對所有的方向計算公式（5），同時將多變量的優(yōu)化公式（5）轉化成一個線性規(guī)劃問題。詳細做法是，將各獨立句子的k-best翻譯列表中的每個候選翻譯的特征向量都對應于一個多維歐式空間中的點，再利用線性規(guī)劃的方法計算k-best翻譯列表對應的集合的最小凸包，并根據所得到最小凸包就可以求得公式（5）的解；其次，將每個句子的最小凸包進行組合，就可以得到公式（5）中對應的分段線性的目標函數（關于參數W），遍歷這個分段線性函數可以找到最優(yōu)的解。這個方法的最大貢獻是，方法表明了公式（5）可以找到全局最優(yōu)解，但是，其算法復雜度卻是指數級的，因此，不宜推廣到規(guī)模很大的開發(fā)集上。
如前所述，公式（5）中的錯誤率函數是分段線性的，具有許多局部最小值的區(qū)域。由于錯誤率函數的形狀錯綜復雜，高峰和低谷的分布異常不均勻。這樣導致的結果是，對于不同的開發(fā)集，所對應的錯誤率函數的最小值區(qū)域并不具有一致性。因此，即使是找到了公式（5）的（局部）最小值點，公式（5）的最小值點附近區(qū)域的其他點的錯誤率函數值也有可能會達到很高。如此，該最小值點的推廣能力未必是最好的。為了避免這種情況的發(fā)生，許多研究者為MERT提出了正則的方法，以避免找到推廣能力不好的（局部）最優(yōu)點。Smith和eisner[8]采用光滑的函數來逼近錯誤率函數，以減少錯誤率函數的“尖銳點”現象。通過使用一個期望風險函數來取代公式（5）中的目標函數：
minWExpectation（W；l）=minW∑Ss=1∑e∈csl（e）P（e|fs；W）（6）
其中，l（e）表示與參考譯文相比e具有的損失值， 和公式（5）中E的意義一樣，不同的只是，這是定義在句子級別而已。公式（6）也即MBR的最小風險準則。值得注意的是，公式（6）是連續(xù)可微的，是公式（5）的“光滑逼近”。同Smith和Eisner采用光滑逼近的技術實現正則不同，Cer等[9]采用了離散正則的方法。其主要思想是，在評價某一個權重向量時，不僅考慮這個向量所在的線性區(qū)域（因為公式（5）中的目標函數是分片線性的）對應的BLEU值，而且考慮這個區(qū)域附近的k個其他線性區(qū)域的BLEU得分情況。對于每個線性區(qū)域的目標BLEU值，則提出了兩種組合方法。一種是max， 定義了每個線性區(qū)的BLEU值為該區(qū)域的k個附近區(qū)域的BLEU值最高值。另一種方法是average， 則將這個線性區(qū)域的BLEU值定義為k個附近區(qū)域BLEU值的平均值。
3可擴展的訓練方法
參數估計方法的可擴展性是一個重要的研究問題，也是近幾年的一個研究熱點。其中的原因是，對數線性模型的一大優(yōu)點就是可以很靈活地增加特征，而且，現有的研究表明[10]，增加大量的特征有利于提高翻譯的性能。為此，MERT就面臨著一個重要的問題，其可擴展性不好。需要強調的是，這里的可擴展性是指，在翻譯模型的特征不斷增加時，MERT的性能會下降；而并不是指MERT在算法效率上的可擴展問題。比如，Chiang等[10]的實驗表明，MERT在翻譯模型的維數小于30時，性能很好；維數大于50時，性能將變得不好。其中一個可能的原因是，公式（5）的錯誤率函數是非凸的，隨著維數的增加，陷入局部最優(yōu)的可能性也就越大。為此，許多研究者在這方面提出了具有可擴展性的參數估計方法。Liang等[11]基于感知器的在線學習算法，提出了一種可以優(yōu)化大量特征的翻譯模型。算法的主要思路是：對于源語言fs的參考譯文rs和候選譯文e′s，那么權重就應該滿足：P（rs|fs；W）>P（e′s|fs；W）， 即，W·h（rs，fs）>W·h（e′s fs）。在此，可以使用感知器更新公式：
W←W+h（rs， fs）-h（e′s， fs）（7）
由于參考譯文rs可能會不可達，文中提出3種權重更新策略：激進的更新，局部的更新和混合更新方法。激進的更新僅對于參考譯文能可達句子，按照公式（7）更新權重；而對于那些參考譯本不可達的句子，直接不予考慮更新。局部更新的對象是對所有的句子都進行更新，其做法是使解碼器輸出k-best候選翻譯，將k-best翻譯中BLEU 分最高的翻譯代替公式（7）中的rs，其他的翻譯代替e′s，按照公式（7）更新k-1次。組合的更新方法結合前兩種更新方式：如果參考譯文可達，執(zhí)行魯莽的更新；否則，執(zhí)行局部更新。相似地，Tillmann和Zhang[12]采用隨機梯度的在線更新算法學習大規(guī)模特征的翻譯模型權重。
Watanabe等[13]以及Chiang等[10]提出了基于大邊緣融合松弛（MIRA）算法[14]的翻譯模型參數估計方法。同Liang及Tillmann和Zhang的方法一樣，這也是一個在線的學習。設當前迭代的權重為Wt；解碼器為更新權重由開發(fā)集中挑選的句子集{ftk}Bk=1，其中，B為批量大?。˙atch size）。那么，更新后的權重Wt+1為如下二次優(yōu)化問題的解：
其中，λ為大于0的正則系數，O tk（Θtk）為性能較好（不好）的翻譯集，r tk為ftk的參考譯文集，l（ek，e′k，rtk）為根據rtk評價ek和e′k的句子級BLEU之差。如何挑選O tk（Θtk）對翻譯的性能具有一定的影響，Watanabe等[13]以及Chiang等[10]從k-best 翻譯列表或者超圖中選擇句子級BLEU最高（最低）的前幾個候選翻譯構成O tk（Θtk）。公式（8）對應的二次優(yōu)化問題可以使用SMO[15]進行求解。MIRA算法的一個缺點是，需要設定很多參數，比如λ和O tk（Θtk）選擇所必需的一些參數。不同于上述對MIRA采取在線的更新算法，Cherry和Foster[16]提出了一個批處理的MIRA訓練算法。該算法與MERT一樣，對開發(fā)集中的所有句子，執(zhí)行一次二次優(yōu)化。另外，Hopkins和May[17]將翻譯模型的參數學習問題看做是排序問題，然后將其轉化成了普通的分類問題，并采用開源的分類器實現算法。算法實現簡單，而且實驗表明也十分有效，同時，還具有很好的可擴展性。受該算法啟發(fā)，Watanabe[18]提出了一個基于排序的在線學習算法。相似地，文獻Bazrafshan等[19]將翻譯模型的參數學習問題轉化成了一個線性回歸問題。同基于排序的二值分類問題相比，這一方法不但獲得了更好的翻譯性能，而且還具有更好的收斂速度。
4結束語
判別式訓練是基于對數線性的統(tǒng)計機器翻譯中最重要的一個組成部分。本文在充分調研和深入分析的基礎上，對現有的所有主流的訓練方法進行了綜述。本文主要從似然函數、錯誤率函數和可擴展的方法三個方面，闡述并分析了各個訓練方法的優(yōu)缺點。判別式訓練方法的研究至今只有數十年，而且統(tǒng)計機器翻譯本身具有諸多的復雜性制約，目前還有許多問題有待于更深一步的研究和探討?；谀壳瓣P于判別式訓練的研究經驗，本文在最后提出一些未來值得進一步挖掘的研究問題，希望對這方面的研究者在未來的研究中有所啟發(fā)，進而為判別式訓練的進一步發(fā)展乃至統(tǒng)計機器翻譯的發(fā)展起到推動作用。
首先，對于結構化學習問題，在精確的解碼框架下，其判別式訓練有著良好的理論基礎[20]。然而在機器翻譯中，翻譯模型通常會包含全局的特征比如語言模型，動態(tài)規(guī)劃的技術則無法采用，因此精確解碼是不可能的，往往采用基于柱狀搜索的非精確解碼方法。非精確解碼導致的后果是，算法的收斂性很難得到保證，實際上，現有的判別式訓練算法是否能夠收斂？需要經過多少次解碼迭代才能收斂？這都沒有獲得理論上的保證。黃亮等[21]指出，當非精確解碼滿足一定的條件時，收斂性就能夠得到保證。因此，可否將現有的解碼方式進行適當的修改，以滿足黃亮等提出的關于非精確解碼的條件？或者可否重新探索滿足新的收斂條件和新的解碼方式。
其次，對于判別式訓練而言，其最終目標是，對于優(yōu)化得到的權重而言，翻譯度量最好翻譯對應的模型得分，要大于其他候選翻譯的模型得分。由于翻譯評價度量不能定義在翻譯單元上，而翻譯的解碼卻需要按照翻譯單元進行擴展，這就使得訓練時幾乎不能找到質量最好的翻譯。因而，在實踐中，機器翻譯在訓練的過程中，僅僅考慮翻譯模型得分最好的k-best候選翻譯，而后又在k-best翻譯候選中考慮質量最好的翻譯。由于k-best僅僅是指數級別翻譯空間中一個粗糙的近似，這種近似會影響到判別式訓練的效果。那么如何在解碼搜索中同時兼顧考慮翻譯評價度量就是一個重要的問題。
參考文獻：
[1]BROWN P F， PIETRA V J D， PIETRA S A D， et al. The mathematics of statistical machine translation： parameter estimation. comput. Linguist. 1993，19：263–311.
[2]OCH F J， NEY H. Discriminative training and maximum entropy models for statistical machine translation[C]//Proc. of ACL. PA， USA， 2002：295–302.
[3]PAPINENI K， ROUKOS S， WARD T， et al. Bleu： a method for automatic evaluation of machine translation[C]//Proc. of ACL. Philadelphia， Pennsylvania， USA， 2002：311–318.
[4]OCH F J. Minimum error rate training in statistical machine translation[C]//Proc. of ACL. Sapporo， Japan， 2003：160–167.
[5]ZHAO B， CHEN S. A simplex armijo downhill algorithm for optimizing statistical machine translation decoding parameters[C]//Proc. of NAACL. Stroudsburg， PA， USA， 2009：21–24.
[6]MOORE R C， QUIRK C. Random restarts in minimum error rate training for statistical machine translation[C]//Proc. of COLing. Stroudsburg， PA， USA， 2008：585–592.
[7]GALLEY M， QUIRK C. Optimal search for minimum error rate training[C]//Proc. of EMNLP. Edinburgh， Scotland， UK.， 2011：38–49.
[8]SMITH D A， EISNER J. Minimum risk annealing for training log-linear models[C]//Proc. of COLING-ACL. Sydney， Australia， 2006：787–794.
[9]CER D， JURAFSKY D， MANNING C D. Regularization and search for minimum error rate training[C]//Proc. of the Third Workshop on SMT， 2008.
[10]CHIANG D， MARTON Y， RESNIK P. Online large-margin training of syntactic and structural translation features[C]//Proc. of EMNLP，2008.
[11]LIANG P， BOUCHARD-C^OT^E A， KLEIN D， et al. An end-to-end discriminative approach to machine translation[C]// Proc. of ACL. Sydney，Australia， 2006：761–768.
[12]TILLMANN C， ZHANG T. A discriminative global training algorithm for statistical Mt[C]//Proc. of ACL. Stroudsburg， PA， USA， 2006：721–728.
[13]WATANABE T， SUZUKI J， TSUKADA H， et al. Online large-margin training for statistical machine translation[C]//Proc. of EMNLP-CoNLL. Prague， Czech Republic， 2007：764–773.
[14]CRAMMER K， SINGER Y. Ultraconservative online algorithms for multiclass problems[J]. Mach. Learn. Res， 2003， 3：951–991.
[15]PLATT J. Fast training of Support vector machines using sequential minimal optimization. SCHOELKOPF B， BURGES C， SMOLA A， （Editors） Advances in Kernel Methods - Support Vector Learning， MIT Press， 1998.
[16]CHERRY C， FOSTER G. Batch tuning strategies for Statistical Machine Translation[C]//Proc. of NAACL. Montrieal， Canada， 2012： 427–436.
[17]HOPKINS M， MAY J. Tuning as ranking[C]//Proc. of EMNLP. Edinburgh， Scotland， UK.， 2011：1352–1362.
[18]WATANABE T. Optimized online rank learning for machine translation[C]//Proc. of NAACL. Montrieal， Canada， 2012：253–262.
[19]BAZRAFSHAN M， CHUNG T， GILDEA D. Tuning as linear regression[C]//Proc. of NAACL. Montreal， Canada， 2012：543–547.
[20]COLLINS M. Discriminative training methods for Hidden Markov Models： theory and experiments with Perceptron Algorithms[C]//Proc. of EMNLP， 2002.
[21]HUANG L， FAYONG S， GUO Y. Structured perceptron with inexact search[C]//Proc. of NAACL. Montrieal， Canada， 2012：142–151.
[14]AKAGI T， SUGENO M. Fuzzy identification of systems and its application to modeling and control[J]. IEEE Transactions on Systems， Man， and， Cybernetics， 1985，15（1）： 116-132.
[15]黃福員. 金融風險預警的MPSO-FNN模型構建與應用[J]. 計算機工程與應用，2009，45（14）：210-212.
[16]ALTMAN E I， MARCO G， VARETTO F. Corporate distress diagnosis： comparisons using linear discriminant Ana analysis and neural networks[J]. Journal of Banking and Finance， 1994， 18： 505-529.
[17]李志輝， 李萌. 我國商業(yè)銀行信用風險識別模型及其實證研究[J]. 經濟科學， 2005（5）： 61-71.
[18]財政部統(tǒng)計評價司. 企業(yè)績效評價問答[M]. 北京：經濟科學出版社， 1999.
[19]章彰. 解讀巴塞爾新資本協議[M]. 北京： 中國經濟出版社， 2005.
