2002-12-6,統計機器翻譯簡介,劉群liuqun,2002-12-6,統計機器翻譯方法的特點,利用語料庫作為知識來源區別于規則方法：無需人工編寫規則建立完整的統計模型區別于實例方法或模板方法：必須為整個翻譯過程建立統計模型,2002-12-6,統計機器翻譯的分類,基于平行概率語法的統計機器翻譯模型基于信源信道思想的統計機器翻譯模型IBM的PeterBrown等人首先提出目前影響最大幾乎成為統計機器翻譯的同義詞基于最大熵的統計機器翻譯模型源于基于特征的自然語言理解Och提出，獲ACL2002最佳論文,2002-12-6,統計機器翻譯的優缺點,優點無需人工編寫規則，利用語料庫直接訓練得到機器翻譯系統；（但可以使用語言資源）系統開發周期短；魯棒性好；譯文質量好；缺點時空開銷大；數據稀疏問題嚴重；對語料庫依賴性強；算法研究不成熟。,2002-12-6,基于平行概率語法的統計機器翻譯模型,基本思想兩種語言建立一套平行的語法規則，規則一一對應兩套規則服從同樣的概率分布句法分析的過程決定了生成的過程主要模型Alshawi的基于HeadTransducer的MT模型吳德愷的InverseTransductionGrammar（ITG）Takeda的Pattern-basedCFGforMT,2002-12-6,HeadTransducerMT(1),HeadTransducer（中心詞轉錄機）是一種DefiniteStateAutomata（有限狀態自動機）與一般的有限狀態識別器的區別：每一條邊上不僅有輸入，而且有輸出；不是從左至右輸入，而是從中心詞往兩邊輸入,2002-12-6,HeadTransducerMT(2),a:a,0:0,0:0,b:b,a:a,-1:+1,b:b,-1:+1,例子：一個可以將任何a，b組成的串倒置的HeadTransducer,2002-12-6,HeadTransducerMT(3),所有的語言知識（詞典、規則）都表現為HeadTransducer；HeadTransducer可以嵌套：一個HeadTransducer的邊是另一個的識別結果；純統計的訓練方法；對齊的結果是依存樹：不使用詞性和短語類標記；Chart句法分析器。,2002-12-6,InversionTransductionGrammar(1),比賽星期三開始。ThegamewillstartonWednesday。,2002-12-6,InversionTransductionGrammar(2),規則形式：ABCAAx/y產生源語言和目標語言串分別為：BCBC：詞序相同BCCB：詞序交換xy：詞典,2002-12-6,Pattern-basedCFGforMT(1),每個翻譯模板由一個源語言上下文無關規則和一個目標語言上下文無關規則（這兩個規則稱為翻譯模板的骨架），以及對這兩個規則的中心詞約束和鏈接約束構成；舉例：S:2NP:1歲:MP:2了S:beNP:1beyear:NP:2old,2002-12-6,Pattern-basedCFGforMT(2),中心詞約束：對于上下文無關語法規則中右部（子結點）的每個非終結符，可以指定其中心詞；對于規則左部（父結點）的非終結符，可以直接指定其中心詞，也可以通過使用相同的序號規定其中心詞等于其右部的某個非終結符的中心詞；鏈接約束：源語言骨架和目標語言骨架的非終結符子結點通過使用相同的序號建立對應關系，具有對應關系的非終結符互為翻譯。,2002-12-6,信源信道模型,假設目標語言文本T是由一段源語言文本S經過某種奇怪的編碼得到的，那么翻譯的目標就是要將T還原成S，這也就是就是一個解碼的過程。注意，源語言S是噪聲信道的輸入語言，目標語言T是噪聲信道的輸出語言，與整個機器翻譯系統的源語言和目標語言剛好相反。,2002-12-6,統計機器翻譯基本方程式,P.Brown稱上式為統計機器翻譯基本方程式語言模型：P(S)翻譯模型：P(T|S)語言模型反映“S像一個句子”的程度：流利度翻譯模型反映“T像S”的程度：忠實度聯合使用兩個模型效果好于單獨使用翻譯模型，因為后者容易導致一些不好的譯文。,2002-12-6,語言模型與翻譯模型,考慮漢語動詞“打”的翻譯：有幾十種對應的英語詞譯文：打人，打飯，打魚，打毛衣，打獵，打草稿，如果直接采用翻譯模型，就需要根據上下文建立復雜的上下文條件概率模型如果采用信源信道思想，只要建立簡單的翻譯模型，可以同樣達到目標詞語選擇的效果：翻譯模型：不考慮上下文，只考慮單詞之間的翻譯概率語言模型：根據單詞之間的同現選擇最好的譯文詞,2002-12-6,統計機器翻譯的三個問題,三個問題：語言模型P(S)的參數估計翻譯模型P(T|S)的參數估計解碼（搜索）算法,2002-12-6,語言模型,把一種語言理解成是產生一個句子的隨機事件語言模型反映的是一個句子在一種語言中出現的概率語言模型N元語法P(S)=p(s0)*p(s1|s0)*p(Sn|Sn-1Sn-N)鏈語法：可以處理長距離依賴PCFG（要使用句法標記）,2002-12-6,引入隱含變量：對齊A,翻譯模型與對齊,P(T|S)的計算轉化為P(T,A|S)的估計對齊：建立源語言句子和目標語言句子的詞與詞之間的對應關系,2002-12-6,IBMModel,對P(T,A|S)的估計IBMModel1僅考慮詞對詞的互譯概率IBMModel2加入了詞的位置變化的概率IBMModel3加入了一個詞翻譯成多個詞的概率IBMModel4IBMModel5,2002-12-6,IBMModel3,對于句子中每一個英語單詞e，選擇一個產出率，其概率為n(|e)；對于所有單詞的產出率求和得到m-prime；按照下面的方式構造一個新的英語單詞串：刪除產出率為0的單詞，復制產出率為1的單詞，復制兩遍產出率為2的單詞，依此類推；在這m-prime個單詞的每一個后面，決定是否插入一個空單詞NULL，插入和不插入的概率分別為p1和p0；0為插入的空單詞NULL的個數。設m為目前的總單詞數：m-prime+0；根據概率表t(f|e)，將每一個單詞e替換為外文單詞f；對于不是由空單詞NULL產生的每一個外語單詞，根據概率表d(j|i,l,m)，賦予一個位置。這里j是法語單詞在法語串中的位置，i是產生當前這個法語單詞的對應英語單詞在英語句子中的位置，l是英語串的長度，m是法語串的長度；如果任何一個目標語言位置被多重登錄（含有一個以上單詞），則返回失敗；給空單詞NULL產生的單詞賦予一個目標語言位置。這些位置必須是空位置（沒有被占用）。任何一個賦值都被認為是等概率的，概率值為1/0。最后，讀出法語串，其概率為上述每一步概率的乘積。,2002-12-6,翻譯模型的參數訓練,ViterbiTraining（對比：EMTraining）給定初始參數；用已有的參數求最好（Viterbi）的對齊；用得到的對齊重新計算參數；回到第二步，直到收斂為止。IBMModel1：存在全局最優IBMModel25：不存在全局最優，初始值取上一個模型訓練的結果,2002-12-6,統計機器翻譯的解碼,借鑒語音識別的搜索算法：堆棧搜索參數空間極大，搜索不能總是保證最優從錯誤類型看，只有兩種：模型錯誤：概率最大的句子不是正確的句子搜索錯誤：沒有找到概率最大的句子后一類錯誤只占總錯誤數的5%（IBM）搜索問題不是瓶頸,2002-12-6,IBM公司的Candide系統1,基于統計的機器翻譯方法分析轉換生成中間表示是線性的分析和生成都是可逆的分析（預處理）：1.短語切分2.專名與數詞檢測3.大小寫與拼寫校正4.形態分析5.語言的歸一化,2002-12-6,IBM公司的Candide系統2,轉換（解碼）：基于統計的機器翻譯解碼分為兩個階段：第一階段：使用粗糙模型的堆棧搜索輸出140個評分最高的譯文語言模型：三元語法翻譯模型：EM算法第二階段：使用精細模型的擾動搜索對第一階段的輸出結果先擴充，再重新評分語言模型：鏈語法翻譯模型：最大熵方法,2002-12-6,IBM公司的Candide系統3,ARPA的測試結果：,2002-12-6,JHU的1999年夏季研討班,由來IBM的實驗引起了廣泛的興趣IBM的實驗很難重復：工作量太大目的構造一個統計機器翻譯工具（EGYPT）并使它對于研究者來說是可用的（免費傳播）；在研討班上用這個工具集構造一個捷克語英語的機器翻譯系統；進行基準評價：主觀和客觀；通過使用形態和句法轉錄機改進基準測試的結果；在研討班最后，在一天之內構造一個新語對的翻譯器。JHU夏季研討班大大促進了統計機器翻譯的研究,2002-12-6,EGYPT工具包,EGYPT的模塊GIZA：這個模塊用于從雙語語料庫中抽取統計知識（參數訓練）Decoder：解碼器，用于執行具體的翻譯過程（在信源信道模型中，“翻譯”就是“解碼”）Cairo：整個翻譯系統的可視化界面，用于管理所有的參數、查看雙語語料庫對齊的過程和翻譯模型的解碼過程Whittle：語料庫預處理工具EGYPT可在網上免費下載，成為SMT的基準,2002-12-6,EGYPT工具包的性能,“當解碼器的原形系統在研討班上完成時，我們很高興并驚異于其速度和性能。1990年代早期在IBM公司舉行的DARPA機器翻譯評價時，我們曾經預計只有很短（10個詞左右）的句子才可以用統計方法進行解碼，即使那樣，每個句子的解碼時間也可能是幾個小時。在早期IBM的工作過去將近10年后，摩爾定律、更好的編譯器以及更加充足的內存和硬盤空間幫助我們構造了一個能夠在幾秒鐘之內對25個單詞的句子進行解碼的系統。為了確保成功，我們在搜索中使用了相當嚴格的閾值和約束，如下所述。但是,解碼器相當有效這個事實為這個方向未來的工作預示了很好的前景，并肯定了IBM的工作的初衷，即強調概率模型比效率更重要。”引自JHU統計機器翻譯研討班的技術報告,2002-12-6,對IBM方法的改進,IBM方法的問題不考慮結構：能否適用于句法結構差別較大的語言？數據稀疏問題嚴重后續的改進工作王野翊的改進Yamada和Knight的改進Och等人的改進,2002-12-6,王野翊的改進(1),背景：德英口語翻譯系統語法結構差異較大數據稀疏（訓練數據有限）改進：兩個層次的對齊模型粗對齊：短語之間的對齊細對齊：短語內詞的對齊,2002-12-6,王野翊的改進(2),文法推導詞語聚類：基于互信息的方法短語歸并規則學習優點機器翻譯的正確率提高：錯誤率降低了11%提高了整個系統的效率：搜索空間更小緩解了因口語數據缺乏導致的數據稀疏問題,2002-12-6,Yamada和Knight的改進(1),基于語法的翻譯模型（Syntax-basedTM）：輸入是源語言句法樹輸出是目標語言句子翻譯的過程：每個內部結點的子結點隨機地重新排列：排列概率在每一個結點的左邊或右邊隨機插入一個單詞左、右插入和不插入的概率取決于父結點和當前結點標記插入哪個詞的概率只與被插入詞有關，與位置無關對于每一個葉結點進行翻譯：詞對詞的翻譯概率輸出譯文句子,2002-12-6,Yamada和Knight的改進(2),2002-12-6,Yamada和Knight的改進(3),2002-12-6,Yamada和Knight的改進(4),2002-12-6,Yamada和Knight的改進(5),訓練英日詞典例句2121對，平均句長日9.7和英6.9詞匯量：英語3463，日語3983，大部分詞只出現一次BrillsPOSTagger和CollinsParser用中心詞詞性標記取得短語標記壓扁句法樹：中心詞相同的句法子樹合并EM訓練20遍迭代：IBMModel5用20遍迭代,2002-12-6,Yamada和Knight的改進(6),困惑度Perplexity：OurModel：15.70IBMModel：9.84(Over-fitting),結果,2002-12-6,Och等人的改進(1),著名語音翻譯系統VerbMobil的一個模塊對IBM方法的改進基于類的模型：詞語自動聚類：各400個類語言模型：基于類的五元語法，回退法平滑翻譯模型：基于對齊模板的方法短語層次對齊詞語層次對齊短語劃分：動態規劃,2002-12-6,Och等人的改進(2),對齊模板,2002-12-6,基于最大熵的統計機器翻譯模型(1),Och等人提出，思想來源于Papineni提出的基于特征的自然語言理解方法不使用信源信道思想，直接使用統計翻譯模型，因此是一種直接翻譯模型是一個比信源信道模型更具一般性的模型，信源信道模型是其一個特例與一般最大熵方法的區別：使用連續量作為特征,2002-12-6,基于最大熵的統計機器翻譯模型(2),假設e、f是機器翻譯的目標語言和源語言句子，h1(e,f),hM(e,f)分別是e、f上的M個特征，1,M是與這些特征分別對應的M個參數，那么直接翻譯概率可以用以下公式模擬：,2002-12-6,基于最大熵的統計機器翻譯模型(3),對于給定的f，其最佳譯文e可以用以下公式表示：,2002-12-6,基于最大熵的統計機器翻譯模型(4),取以下特征和參數時等價于信源信道模型：僅使用兩個特征h1(e,f)=logp(e)h2(e,f)=logp(f|e)121,2002-12-6,基于最大熵的統計機器翻譯模型(5),參數訓練,最優化后驗概率準則：區別性訓練這個判斷準則是凸的，存在全局最優考慮多個參考譯文：,2002-12-6,基于最大熵的統計機器翻譯模型(6),Och等人的實驗(1)：方案首先將信源信道模型中的翻譯模型換成反向的翻譯模型，簡化了搜索算法，但翻譯系統的性能并沒有下降；調整參數1和2，系統性能有了較大提高；再依次引入其他一些特征，系統性能又有了更大的提高。,2002-12-6,基于最大熵的統計機器翻譯模型(7),Och等人的實驗(2)：其他特征句子長度特征(WP)：對于產生的每一個目標語言單詞進行懲罰；附件的語言模型特征(CLM)：一個基于類的語言模型特征；詞典特征(MX)：計算給定的輸入輸出句子中有多少詞典中存在的共現詞對。,2002-12-6,基于最大熵的統計機器翻譯模型(8),Och等人的實驗(2)：實驗結果,2002-12-6,基于最大熵的統計機器翻譯模型(9),經典的信源信道模型只有在理想的情況下才能達到最優，對于簡化的語言模型和翻譯模型，取不同的參數值實際效果更好；最大熵方法大大擴充了統計機器翻譯的思路；特征的選擇更加靈活。,2002-12-6,統計機器翻譯的應用,傳統機器翻譯的應用領域跨語言檢索聶建云使用IBMModel1進行CLIR機器翻譯系統的快速開發針對未知語言快速開發,2002-12-6,總結,IBM當年的工作是有一定超前性的雖然很多人懷疑統計方法在機器翻譯中能否取得成功，但現在這已不再是問題基于平行語法的機器翻譯方法總體上不成功基于最大熵的方法為統計機器翻譯方法開辟了一個新天地,2002-12-6,我的工作設想,采用基于最大熵的統計機器翻譯模型；提出基于模板的統計翻譯模型：句法樹對齊抽取翻譯模板基于模板翻譯模型其它特征漢語詞法分析漢語句法分析,2002-12-6,參考文獻(1),Al-Onaizan1999YaserAl-Onaizan,JanCurin,MichaelJahr,KevinKnight,JohnLafferty,DanMelamed,Franz-JosefOch,DavidPurdy,NoahA.SmithandDavidYarowsky(1999).StatisticalMachineTranslation:FinalReport,JohnsHopkinsUniversity1999SummerWorkshoponLanguageEngineering,CenterforSpeechandLanguageProcessing,Baltimore,MD.Alshawi1998Alshawi,H.,Bangalore,S.andDouglas,S.AutomaticAcquisitionofHierarchicaltransductionmodelsformachinetranslation,Proc.36thConf.AssociationofComputationalLinguistics,Montreal,Canada,1998.Berger1994Berger,A.,P.Brown,S.DellaPietra,V.DellaPietra,J.Gillett,J.Lafferty,R.Mercer,H.Printz,LUres,TheCandideSystemforMachineTranslation,ProceedingsoftheDARPAWorkshoponHumanLanguageTechnology(HLT)Berger1996A.L.Berger,S.A.DellaPietra,andV.J.DellaPietra.Amaximumentropyapproachtonaturallanguageprocessing.ComputationalLinguistics,22(1):39-72,March1996.Brown1990PeterF.Brown,JohnCocke,StephenA.DellaPietra,VincentJ.DellaPietra,FredrickJelinek,JohnD.Lafferty,RobertL.Mercer,PaulS.Roossin,AStatisticalApproachtoMachineTranslation,ComputationalLinguistics,1990,2002-12-6,參考文獻(2),Brown1993Peter.F.Brown,StephenA.DellaPietra,VincentJ.DellaPietra,RobertL.Mercer,TheMathematicsofStatisticalMachineTranslation:ParameterEstimation,ComputationalLinguistics,Vol19,No.2,1993Ker1997SueJ.Ker,JasonS.Chang,AClass-basedApproachtoWordAlignment,ComputationalLinguistics,Vol.23,No.2,Page313-343,1997Knight1999KevinKnight,AStatisticalMachineTranslationTutorialWorkbook.unpublished,preparedinconnectionwiththeJHUsummerworkshop,August1999.(availableat/ws99/projects/mt/wkbk.rtf).Och1998FranzJosefOchandHansWeber.Improvingstatisticalnaturallanguagetranslationwithcategoriesandrules.InProc.Ofthe35thAnnualConf.oftheAssociationforComputationalLinguisticsandthe17thInt.Conf.onComputationalLinguistics,pages985-989,Montreal,Canada,August1998.Och1999F.J.Och,C.Tillmann,andH.Ney.Improvedalignmentmodelsforstatisticalmachinetranslation.InProc.oftheJointSIGDATConf.OnEmpiricalMethodsinNaturalLanguageProcessingandVeryLargeCorpora,pages20-28,UniversityofMaryland,CollegePark,MD,June1999.,2002-12-6,參考文獻(3),Och2001FranzJosefOch,HermannNey.WhatCanMachineTranslationLearnfromSpeechRecognition?In:proceedingsofMT2001Workshop:TowardsaRoadMapforMT,pp.26-31,SantiagodeCompostela,Spain,September2001.Och2002FranzJosefOch,HermannNey,DiscriminativeTrainingandMaximumEntropyModelsforStatisticalMachineTranslation,ACL2002Papineni1997K.A.Papineni,S.Roukos,andR.T.Ward.1997.Feature-basedlanguageunderstanding.InEuropeanConf.onSpeechCommunicationandTechnology,pages1435-1438,Rhodes,Greece,September.Papineni1998K.A.Papineni,S.Roukos,andR.T.Ward.1998.Maximumlikelihoodanddiscriminativetrainingofdirecttranslationmodels.InProc.Int.Conf.onAcoustics,Speech,andSignalProcessing