機(jī)器翻譯原理與方法講義(03)基于詞的統(tǒng)計(jì)機(jī)器翻譯方法

1、機(jī)器翻譯原理與方法第三講 基于詞的統(tǒng)計(jì)機(jī)器翻譯方法中國科學(xué)院計(jì)算技術(shù)研究所2008-2009年度秋季課程劉群中國科學(xué)院計(jì)算技術(shù)研究所機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法2內(nèi)容提要 為翻譯建立概率模型 ibm的信源信道模型 語言模型 n元語法模型 翻譯模型 ibm模型1-5 詞語對(duì)齊算法 解碼算法 candide系統(tǒng) egypt工具包與giza+ 機(jī)器翻譯自動(dòng)評(píng)價(jià)機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法3為翻譯建立概率模型 假設(shè)任意一個(gè)英語句子e和一個(gè)法語句子 f，我們定義f翻譯成e的概率為：pr( |)e f其歸一化條件為：pr( |)1=ee f 于是將 f 翻譯成 e 的問題就變成

2、求解問題：=argmaxpr( |)eee f機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法4內(nèi)容提要 為翻譯建立概率模型 ibm的信源信道模型 語言模型 n元語法模型 翻譯模型 ibm模型1-5 詞語對(duì)齊算法 解碼算法 candide系統(tǒng) egypt工具包與giza+ 機(jī)器翻譯自動(dòng)評(píng)價(jià)機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法5信源信道模型 (1) 信源信道模型又稱噪聲信道模型，是由ibm公司的peter f. brown等人于1990年提出來的：peter f. brown, john cocke, stephen a. della pietra, vincent j. della pietr

3、a, fredrick jelinek, john d. lafferty, robert l. mercer, paul s. roossin, a statistical approach to machine translation, computational linguistics,1990機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法6信源信道模型 (2) 假設(shè)我們看到的源語言文本f f是由一段目標(biāo)語言文本e經(jīng)過某種奇怪的編碼得到的，那么翻譯的目標(biāo)就是要將f f還原成e e，這也就是就是一個(gè)解碼的過程。 注意，在信源信道模型中： 噪聲信道的源語言是翻譯的目標(biāo)語言 噪聲信道的目標(biāo)語言是翻

4、譯的源語言這與整個(gè)機(jī)器翻譯系統(tǒng)翻譯方向的剛好相反ep（e）p（fe）f機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法7統(tǒng)計(jì)機(jī)器翻譯基本方程式 p.brown稱上式為統(tǒng)計(jì)機(jī)器翻譯基本方程式 語言模型：p(e) 翻譯模型：p(f|e) 語言模型反映“ e像一個(gè)句子”的程度：流利度 翻譯模型反映“f像e”的程度：忠實(shí)度 聯(lián)合使用兩個(gè)模型效果好于單獨(dú)使用翻譯模型，因?yàn)楹笳呷菀讓?dǎo)致一些不好的譯文。)e|f()e(maxargeepp=機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法8語言模型與翻譯模型 考慮漢語動(dòng)詞“打”的翻譯：有幾十種對(duì)應(yīng)的英語詞譯文：打人，打飯，打魚，打毛衣，打獵，打草稿， 如果直接采用翻譯模

5、型，就需要根據(jù)上下文建立復(fù)雜的上下文條件概率模型 如果采用信源信道思想，只要建立簡單的翻譯模型，可以同樣達(dá)到目標(biāo)詞語選擇的效果： 翻譯模型：不考慮上下文，只考慮單詞之間的翻譯概率 語言模型：根據(jù)單詞之間的同現(xiàn)選擇最好的譯文詞機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法9統(tǒng)計(jì)機(jī)器翻譯的三個(gè)問題 三個(gè)問題： 語言模型p(e)的建模和參數(shù)估計(jì) 翻譯模型p(f|e)的建模和參數(shù)估計(jì) 解碼（搜索）算法機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法10內(nèi)容提要 為翻譯建立概率模型 ibm的信源信道模型 語言模型 n元語法模型 翻譯模型 ibm模型1-5 詞語對(duì)齊算法 解碼算法 candide系統(tǒng) egypt工具

6、包與giza+ 機(jī)器翻譯自動(dòng)評(píng)價(jià)機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法11語言模型 統(tǒng)計(jì)語言模型把一種語言理解成是產(chǎn)生一個(gè)句子的隨機(jī)事件。在統(tǒng)計(jì)語言模型看來，對(duì)于一種語言，任何一個(gè)句子都是可以接受的，只是接受的可能性（概率）不同 語言模型給出任何一個(gè)句子的出現(xiàn)概率：pr(e=e1e2en)歸一化條件：epr(e)=1 統(tǒng)計(jì)語言模型實(shí)際上就是一個(gè)概率分布，它給出了一種語言中所有可能的句子的出現(xiàn)概率機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法12語言模型的類型 理論上，單詞串的任何一種概率分布，都是一個(gè)語言模型。 實(shí)際上，n元語法模型是最簡單也是最常見的語言模型。 n元語法模型由于沒有考慮任何語

7、言內(nèi)部的結(jié)構(gòu)信息，顯然不是理想的語言模型。 其他語言模型： 隱馬爾科夫模型（hmm）（加入詞性標(biāo)記信息） 概率上下文無關(guān)語法（pcfg）（加入短語結(jié)構(gòu)信息） 概率鏈語法（probabilistic link grammar）（加入鏈語法的結(jié)構(gòu)信息） 目前為止，其他形式的語言模型效果都不如n元語法模型 統(tǒng)計(jì)機(jī)器翻譯研究中開始有人嘗試基于句法的語言模型機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法13n元語法模型概念辨析 n元語法模型：n-gram model。 所謂n-gram，指的是由n個(gè)詞組成的串，可以稱為“n元組”，或“n元詞串”。 基于n-gram建立的語言模型，稱為“n元語法模型(n-gr

8、am model)”。 gram不是grammar的簡寫。在英文中，并沒有n-grammar的說法。 在在漢語中，單獨(dú)說“n元語法”的時(shí)候，有時(shí)指“n元組(n-gram)”，有時(shí)指“n元語法模型(n-gram model)”，請(qǐng)注意根據(jù)上下文加以辨別。機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法14n元語法模型定義 n元語法模型（n-gram model）=+=niininiiniiiwwwwpwwwwpwp11211121).|().|()( 假設(shè)：單詞wi出現(xiàn)的概率只與其前面的n-1個(gè)單詞有關(guān)機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法15n元語法模型舉例 n=1時(shí)：一元語法模型 相當(dāng)于詞頻表

9、，給出所有詞出現(xiàn)的頻率 n=2時(shí)：二元語法模型 相當(dāng)于一個(gè)轉(zhuǎn)移矩陣，給出每一個(gè)詞后面出現(xiàn)另一個(gè)詞的概率 n=3時(shí)：三元語法模型 相當(dāng)于一個(gè)三維轉(zhuǎn)移矩陣，給出每一個(gè)詞對(duì)兒后面出現(xiàn)另一個(gè)詞的概率 在自然語言處理中，n元語法模型可以在漢字層面，也可以在單詞層面，還可以在概念層面機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法16二元語法模型圖示p(t-i-p) = p(x1= t)p(x2= i|x1= t)p(x3= p|x2= i)= 1.00.30.6= 0.18機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法17袋子模型 bag model (1) 將一個(gè)英語句子中所有的單詞放入一個(gè)袋子中 用n元語法模

10、型試圖將其還原 對(duì)于這些單詞的任何一種排列順序根據(jù)n元語法模型計(jì)算其出現(xiàn)概率 取概率最大的排列方式機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法18袋子模型 bag model (2) 實(shí)驗(yàn)：取38個(gè)長度小于11個(gè)單詞的英語句子，實(shí)驗(yàn)結(jié)果如下：機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法19內(nèi)容提要 為翻譯建立概率模型 ibm的信源信道模型 語言模型 n元語法模型 翻譯模型 ibm模型1-5 詞語對(duì)齊算法 解碼算法 candide系統(tǒng) egypt工具包與giza+ 機(jī)器翻譯自動(dòng)評(píng)價(jià)機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法20翻譯模型 翻譯模型p(f|e)反映的是一個(gè)源語言句子e翻譯成一個(gè)目標(biāo)語言句

11、子f的概率 由于源語言句子和目標(biāo)語言句子幾乎不可能在語料庫中出現(xiàn)過，因此這個(gè)概率無法直接從語料庫統(tǒng)計(jì)得到，必須分解成詞語翻譯的概率和句子結(jié)構(gòu)（或者順序）翻譯的概率機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法21 翻譯模型的計(jì)算，需要引入隱含變量：對(duì)齊a：翻譯模型與對(duì)齊=app)e|a, f()e|f( 翻譯概率p(f|e)的計(jì)算轉(zhuǎn)化為對(duì)齊概率p(f,a|e)的估計(jì) 對(duì)齊：建立源語言句子和目標(biāo)語言句子的詞與詞之間的對(duì)應(yīng)關(guān)系和句子結(jié)構(gòu)之間的對(duì)應(yīng)關(guān)系機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法22詞語對(duì)齊的表示 (1)中國十四個(gè)邊境開放城市經(jīng)濟(jì)建設(shè)成就顯著chinas14openboardcitiesm

12、arkedeconomicachievement1234567891,2335468997?圖形表示? 連線? 矩陣（見下頁）?數(shù)字表示? 給每個(gè)目標(biāo)語言單詞標(biāo)記其所有對(duì)應(yīng)的源語言單詞機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法23詞語對(duì)齊的表示 (2)achievementeconomicmarkedcitiesboardopen14schina中國十四個(gè)邊境開放城市經(jīng)濟(jì)建設(shè)成就顯著機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法24ibm model 對(duì)p(f,a|e)的估計(jì) ibm model 1僅考慮詞對(duì)詞的互譯概率 ibm model 2加入了詞的位置變化的概率 ibm model 3加入了

13、一個(gè)詞翻譯成多個(gè)詞的概率 ibm model 4 ibm model 5機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法25ibm model 1 & 2 推導(dǎo)方式 (1)ibm模型1&2的推導(dǎo)過程：1. 猜測(cè)目標(biāo)語言句子長度；2. 從左至右，對(duì)于每個(gè)目標(biāo)語言單詞：首先猜測(cè)該單詞由哪一個(gè)源語言單詞翻譯而來；再猜測(cè)該單詞應(yīng)該翻譯成什么目標(biāo)語言詞。am2i1我一a3student4學(xué)生個(gè)是源語言句子e：目標(biāo)語言句子f：詞語對(duì)齊a：12334機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法26ibm model 1 & 2 推導(dǎo)方式 (2)e,|pr()e,|pr()e|pr()e|a,

14、 fpr(11111111mfafmfaamjjmjjjjj=注意：在ibm model中，詞語對(duì)齊只考慮了源語言到目標(biāo)語言的單向一對(duì)多形式，不考慮多對(duì)一和多對(duì)多的形式。假設(shè)翻譯的目標(biāo)語言句子為:mmffff?211f=假設(shè)翻譯的源語言句子為:lleeee?211e=假設(shè)詞語對(duì)齊表示為:, 0, 1,a211lamiaaaaimm?=那么詞語對(duì)齊的概率可以表示為:機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法27ibm model 1 的推導(dǎo) (1)假設(shè)所有翻譯長度都是等概率的：=)e|pr(m假設(shè)詞語對(duì)齊只與源語言長度有關(guān)，與其他因素?zé)o關(guān)：11)e,|pr(1111+=lmfaajjj假設(shè)目標(biāo)詞

15、語的選擇只與其對(duì)應(yīng)的源語言詞語有關(guān)，與其他因素?zé)o關(guān)：)|()e,|pr(111jajjjjeftmfaf=機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法28ibm model 1 的推導(dǎo)(2)=+=mjajmjeftl1)|() 1()e|a, fpr(那么對(duì)齊概率可以表示為:對(duì)所有可能的對(duì)齊求和，那么翻譯概率就可以表示為: =+=lalamjajmmjeftl111a1)|() 1()e|af,pr()e|fpr(?這就是ibm model 1的翻譯模型公式翻譯模型公式。也就是說，給定參數(shù)t(f|e)，我們就可以計(jì)算出句子e翻譯成句子f的概率。機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法29ibm

16、 model 1 的參數(shù)求解(1) 在ibm model 1中，是個(gè)常數(shù)，無關(guān)緊要，起重要作用的就是單詞翻譯概率分布：)|(eft 這個(gè)單詞翻譯概率分布表現(xiàn)為一個(gè)翻譯概率表，這個(gè)表給出了每一個(gè)源語言單詞翻譯成任何一個(gè)目標(biāo)語言單詞的概率，并且這個(gè)概率滿足歸一性約束條件：1)|(=feft機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法30ibm model 1 的參數(shù)求解(2) 根據(jù)最大似然估計(jì)，我們希望得到一組概率分布，使得我們的訓(xùn)練語料庫出現(xiàn)的概率最大。 也就是說，給定訓(xùn)練語料庫e和f，我們要求解一個(gè)概率分布t(f|e)，使得翻譯概率pr(f|e)最大。 這是一個(gè)受約束的極值問題，約束條件即是t(

17、f|e)的歸一性條件。 為了求解這個(gè)問題，我們需要引入拉格朗日乘子，構(gòu)造一個(gè)輔助函數(shù)，將上述受約束的極值問題轉(zhuǎn)換成一個(gè)不受約束的極值問題。機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法31ibm model 1 的參數(shù)求解(3) 引入拉格朗日乘子e，構(gòu)造輔助函數(shù)如下： +=efelalamjajmefteftlthmj) 1)|()|() 1(),(1111? 將上述函數(shù)對(duì)t(f|e)求導(dǎo)得到：1111(|)( , )( ,) ( ,)(| )(1)t(| )kjmmkallkjaemaat feh tf fe et f elf e=+ ?機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法32ibm mo

18、del 1 的參數(shù)求解(4) 令上式為0，我們得到： =+=lalamkakajmemkjefteeffleft11111)|(),(),() 1()|(? 我們看到，這個(gè)公式的左邊和右邊都出現(xiàn)了t(f|e) 我們無法直接用這個(gè)公式從給定的語料庫(f|e)中計(jì)算出t(f|e) 我們可以將這個(gè)公式看成是一個(gè)迭代公式迭代公式，給定一個(gè)初值t(f|e)，利用這個(gè)公式反復(fù)迭代，最后可以收斂到一個(gè)穩(wěn)定的t(f|e)值，這就是em算法。機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法33ibm model 1 的參數(shù)求解(5) 上述迭代公式代入ibm model 1的翻譯模型公式翻譯模型公式，我們得到：=mja

19、jejeeffeft1a1),(),(e)|apr(f,)|(對(duì)齊a中e連接到f的次數(shù) 定義在e和f的所有可能的對(duì)齊a下e和f連接數(shù)的均值為：a1(| ;f,e)pr(a|f,e)( ,) ( ,)jmjajc f ef fe e=機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法34ibm model 1 的參數(shù)求解(6)a1a1pr(f,a|e)(| ;f,e)( ,) ( ,)pr(f|e)pr(f,a|e)( ,) ( ,)pr(f|e)jjmjajmjajc f ef fe ef fe e= 我們有： 將c(f|e;f,e)代入迭代公式迭代公式，并將pr(f|e)并入?yún)?shù)e，我們得到新的迭代

20、公式新的迭代公式：)e, f;|()|(1efcefte=機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法35ibm model 1 的參數(shù)求解(7) 這個(gè)新的迭代公式可以理解為： 一旦我們得到了一組參數(shù)t(f|e)，我們就可以計(jì)算所有的詞語對(duì)齊的概率pr(f,a|e)； 有了每個(gè)詞語對(duì)齊的概率pr(f,a|e)，我們就可以計(jì)算新的t(f|e)的值，就是所有的出現(xiàn)詞語鏈接(e,f)的詞語對(duì)齊概率之和，并對(duì)e進(jìn)行歸一化。 這個(gè)迭代算法就是一個(gè)經(jīng)典的em算法。機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法36ibm model 1 的參數(shù)求解(8) 通常，訓(xùn)練語料庫(f|e)是由一系列句子對(duì)組成的：=see

21、fceft)e,f;|()|(s)(s)1 因此實(shí)際計(jì)算時(shí)我們采用以下公式：)e,f( ,),e,(f ),e,f(s)(s)(2)(2)(1)(1)? 這里e僅僅起到一個(gè)歸一化因子的作用。機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法37ibm model 1 的化簡(1) 前面ibm model 1的翻譯模型公式為： 這個(gè)公式實(shí)際上可以進(jìn)一步簡化。(1)ml + 其復(fù)雜度太高： =+=lalamjajmmjeftl111a1)|() 1()e|af,pr()e|fpr(?因?yàn)椋?=mjliijlalamjajefteftmj11111)|()|(1?機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法3

22、8ibm model 1 的化簡(2) 所以翻譯模型公式就可以簡化為:=+=mjliijmeftl11a)|() 1()e|af,pr()e|fpr(=+=liimjjleeffeftefteftefc110),(),()|()|()|()e, f;|(? 而c(f|e;f,e)也可以簡化為：ml + 其復(fù)雜度減少為：機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法39ibm model 2 的推導(dǎo) (1)假設(shè)詞語對(duì)齊只與源語言長度、目標(biāo)語言的長度和兩個(gè)詞的位置有關(guān)，與其他因素?zé)o關(guān)：),|()e,|pr(1111lmjaamfaajjjj=歸一化條件為：1),|(0=lilmjia機(jī)器翻譯原理與方法

23、講義(02)機(jī)器翻譯方法40ibm model 2 的推導(dǎo) (2)經(jīng)過推導(dǎo)我們可以得到：=lalamjjajmjlmjaaeft0011),|()|()e|fpr(?經(jīng)過化簡我們可以得到ibm model 2翻譯模型：=mjlijajlmjaaeftj10),|()|()e|fpr(機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法41ibm model 2 的參數(shù)求解 (1)e, f;|()|(1efcefte=同樣通過引入拉格朗日乘子推導(dǎo)可以得到：)e, f;,|(),|(1lmjiclmjiajml=+=mjlilijlmjlaeftlmjaefteefflmjiaeftefc100),|()|

24、(),|0()|(),(),(),|()|()e, f;|(?),|()|(),|0()|(),|()|()e, f;,|(0lmjlaeftlmjaeftlmjiaeftlmjicljjij+=?機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法42ibm model 2 的參數(shù)求解 (2) 考慮到訓(xùn)練語料庫(f|e)是由一系列句子對(duì)組成的：=seefceft)e,f;|()|(s)(s)1 因此實(shí)際計(jì)算時(shí)我們采用以下公式：)e,f( ,),e,(f ),e,f(s)(s)(2)(2)(1)(1)? 這里e和jml僅僅起到歸一化因子的作用。=sjmllmjiclmjia)e,f;,|(),|(s)(

25、s)1機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法43ibm model 3 & 4 & 5 推導(dǎo)方式 (1) f11e1e2e3e4e5e6e71122101f21f31f32f41f42f61f71f1f2f3f4f5f6f7f8繁殖概率繁殖概率翻譯概率調(diào)序概率翻譯概率調(diào)序概率機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法44ibm model 3 & 4 & 5 推導(dǎo)方式 (2)1. 首先根據(jù)源語言詞語的繁殖概率，確定每個(gè)源語言詞翻譯成多少個(gè)目標(biāo)語言詞；2. 根據(jù)每個(gè)源語言詞語的目標(biāo)語言詞數(shù)，將每個(gè)源語言詞復(fù)制若干次；3. 將復(fù)制后得到的每個(gè)源語言詞，根據(jù)翻譯概

26、率，翻譯成一個(gè)目標(biāo)語言詞；4. 根據(jù)調(diào)序概率，將翻譯得到的目標(biāo)語言詞重新調(diào)整順序，得到目標(biāo)語言句子。機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法45ibm model 3 的推導(dǎo)對(duì)于句子中每一個(gè)英語單詞e，選擇一個(gè)產(chǎn)出率，其概率為n(|e)；對(duì)于所有單詞的產(chǎn)出率求和得到m-prime；按照下面的方式構(gòu)造一個(gè)新的英語單詞串：刪除產(chǎn)出率為0的單詞，復(fù)制產(chǎn)出率為1的單詞，復(fù)制兩遍產(chǎn)出率為2的單詞，依此類推；在這m-prime個(gè)單詞的每一個(gè)后面，決定是否插入一個(gè)空單詞null，插入和不插入的概率分別為p1和p0；0為插入的空單詞null的個(gè)數(shù)。設(shè)m為目前的總單詞數(shù)：m-prime+0；根據(jù)概率表t(f|

27、e)，將每一個(gè)單詞e替換為外文單詞f；對(duì)于不是由空單詞null產(chǎn)生的每一個(gè)外語單詞，根據(jù)概率表d(j|i,l,m)，賦予一個(gè)位置。這里j是法語單詞在法語串中的位置，i是產(chǎn)生當(dāng)前這個(gè)法語單詞的對(duì)應(yīng)英語單詞在英語句子中的位置，l是英語串的長度，m是法語串的長度；如果任何一個(gè)目標(biāo)語言位置被多重登錄（含有一個(gè)以上單詞），則返回失?。唤o空單詞null產(chǎn)生的單詞賦予一個(gè)目標(biāo)語言位置。這些位置必須是空位置（沒有被占用）。任何一個(gè)賦值都被認(rèn)為是等概率的，概率值為1/0。最后，讀出法語串，其概率為上述每一步概率的乘積。機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法46ibm模型的參數(shù)訓(xùn)練(1)：em算法 em參數(shù)訓(xùn)

28、練算法是經(jīng)典的無指導(dǎo)學(xué)習(xí)的算法：1. 給定初始參數(shù)；2. e步驟：用已有的參數(shù)計(jì)算每一個(gè)句子對(duì)的所有可能的對(duì)齊的概率；3. m步驟：用得到的所有對(duì)齊的概率重新計(jì)算參數(shù)；4. 重復(fù)執(zhí)行e步驟和m步驟，直到收斂。 由于em算法的e步驟需要窮盡所有可能的對(duì)齊，通常這會(huì)帶來極大的計(jì)算量，除非我們可以對(duì)計(jì)算公式進(jìn)行化簡（就像前面ibm model 1所做的那樣），否則這種計(jì)算量通常是不可承受的。機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法47ibm模型的參數(shù)訓(xùn)練(2)：viterbi訓(xùn)練 viterbi參數(shù)訓(xùn)練算法：1. 給定初始參數(shù)；2. 用已有的參數(shù)求概率最大（viterbi）的詞語對(duì)齊；3. 用得到

29、的概率最大的詞語對(duì)齊重新計(jì)算參數(shù)；4. 回到第二步，直到收斂為止。 在對(duì)參數(shù)計(jì)算公式無法化簡的情況下，采用viterbi參數(shù)訓(xùn)練算法是一種可行的做法，這種算法通?？梢匝杆偈諗康揭粋€(gè)可以接受的結(jié)果。機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法48ibm模型的參數(shù)訓(xùn)練 (3) ibm model 1 任何初始值均可達(dá)到全局最優(yōu) ibm model 25： 存在大量局部最優(yōu)，任意給定的初值很容易導(dǎo)致局部最優(yōu)，而無法到達(dá)全局最優(yōu)的結(jié)果 ibm的訓(xùn)練策略： 依次訓(xùn)練ibm model 1-5 對(duì)于與上一級(jí)模型相同的參數(shù)初始值，直接取上一個(gè)模型訓(xùn)練的結(jié)果； 對(duì)于新增加的參數(shù)，取任意初始值。機(jī)器翻譯原理與方法

30、講義(02)機(jī)器翻譯方法49ibm模型的參數(shù)訓(xùn)練 (4) 由于ibm model 1和2存在簡化的迭代公式，實(shí)際上在em算法迭代是并不用真的去計(jì)算所有的對(duì)齊，而是可以利用迭代公式直接計(jì)算下一次的參數(shù)； 由于ibm model 3、4、5的翻譯模型公式無法化簡，理論上應(yīng)該進(jìn)行em迭代。由于實(shí)際上由于計(jì)算所有詞語對(duì)齊的代價(jià)太大，通常采用viterbi訓(xùn)練，每次e步驟只生成最好的一個(gè)或者若干個(gè)對(duì)齊。機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法50ibm model 1的em訓(xùn)練示例 (0)我們用一個(gè)簡單的例子來演示em訓(xùn)練的過程 假設(shè)有兩個(gè)句子對(duì)：(a b|x y) 和 (a y) 先假設(shè)所有詞語翻譯

31、概率平均分布p(f|e)：pr(a|x)1/2pr(a|y)1/2pr(b|y)1/2pr(b|x)1/2我們這里為方便起見，對(duì)ibm model 1做了簡化： 只考慮詞語一對(duì)一的情況，不考慮詞語一對(duì)多或者對(duì)齊到空的情況； 對(duì)齊概率計(jì)算的時(shí)候，忽略了詞語長度和詞語對(duì)齊概率，僅考慮詞語翻譯概率。機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法51ibm model 1的em訓(xùn)練示例(1e)對(duì)所有可能的對(duì)齊計(jì)算p(f,a|e)對(duì)p(f,a|e)歸一化得到p(a|f,e)2142/41)e, f|a(=p121/21)e, f|a(=p2142/41)e, f|a(=pabxyabxyay412121)e

32、|a, f(=p412121)e|a, f(=p21)e|a, f(=p機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法52ibm model 1的em訓(xùn)練示例(1m)計(jì)算c(f|e)重新計(jì)算pr(f|e)21)|(=xac23121)|(=+=yac21)|(=xbc21)|(=ybc21)2121/(21)|pr(=+=xa43)2123/(23)|pr(=+=ya21)2121/(21)|pr(=+=xb41)2123/(21)|pr(=+=yb機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法53ibm model 1的em訓(xùn)練示例(2e)對(duì)所有可能的對(duì)齊計(jì)算p(f,a|e)對(duì)p(f,a|e)歸一化

33、得到p(a|f,e)4184/81)e, f|a(=p143/43)e, f|a(=p4384/83)e, f|a(=pabxyabxyay814121)e|a, f(=p834321)e|a, f(=p43)e|a, f(=p機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法54ibm model 1的em訓(xùn)練示例(2m)計(jì)算c(f|e)重新計(jì)算pr(f|e)41)|(=xac47143)|(=+=yac43)|(=xbc41)|(=ybc41)4341/(41)|pr(=+=xa87)4147/(47)|pr(=+=ya43)4341/(43)|pr(=+=xb81)4147/(41)|pr(=+

34、=yb機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法55ibm model 1的em訓(xùn)練示例(n)1.00. 0)e, f|a(=p1)e, f|a(=p9.99. 0)e, f|a(=pabxyabxyay1.00. 0)|pr(=xa9.99. 0)|pr(=ya9.99. 0)|pr(=xb1.00. 0)|pr(=yb機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法56統(tǒng)計(jì)機(jī)器翻譯的解碼 給定f，求e，使得p(e)*p(f|e)最大 解碼問題實(shí)際上是一個(gè)搜索問題，搜索空間巨大，不能保證總能找到全局最優(yōu)，但通常一些局部最優(yōu)也是可以接受的 如果考慮所有的詞語對(duì)齊可能性，那么這個(gè)問題是一個(gè)np完全問題

35、 knight 99 經(jīng)典的算法： 單調(diào)解碼（不調(diào)整詞序） 堆棧搜索 貪婪算法 機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法57內(nèi)容提要 為翻譯建立概率模型 ibm的信源信道模型 語言模型 n元語法模型 翻譯模型 ibm模型1-5 詞語對(duì)齊算法（略） 解碼算法 candide系統(tǒng) egypt工具包與giza+ 機(jī)器翻譯自動(dòng)評(píng)價(jià)機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法58內(nèi)容提要 為翻譯建立概率模型 ibm的信源信道模型 語言模型 n元語法模型 翻譯模型 ibm模型1-5 詞語對(duì)齊算法 解碼算法 candide系統(tǒng) egypt工具包與giza+ 機(jī)器翻譯自動(dòng)評(píng)價(jià)機(jī)器翻譯原理與方法講義(02)機(jī)器

36、翻譯方法59堆棧搜索解碼算法 (1) brown et al us patent #5,477,4511stenglishword2ndenglishword3rdenglishword4thenglishwordstartendeach partial translation hypothesis contains: - last english word chosen + source words covered by it- next-to-last english word chosen- entire coverage vector (so far) of source senten

37、ce- language model and translation model scores (so far)all sourcewordscoveredjelinek 69; och, ueffing, and ney, 01機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法601stenglishword2ndenglishword3rdenglishword4thenglishwordstartendeach partial translation hypothesis contains: - last english word chosen + source words covered by

38、 it- next-to-last english word chosen- entire coverage vector (so far) of source sentence- language model and translation model scores (so far)all sourcewordscoveredbest predecessorlinkjelinek 69; och, ueffing, and ney, 01堆棧搜索解碼算法 (2) brown et al us patent #5,477,451機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法61內(nèi)容提要 為翻譯建立

39、概率模型 ibm的信源信道模型 語言模型 n元語法模型 翻譯模型 ibm模型1-5 詞語對(duì)齊算法 解碼算法 candide系統(tǒng) egypt工具包與giza+ 機(jī)器翻譯自動(dòng)評(píng)價(jià)機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法62ibm公司的candide系統(tǒng)(1) 基于統(tǒng)計(jì)的機(jī)器翻譯方法 分析轉(zhuǎn)換生成 中間表示是線性的 分析和生成都是可逆的 分析（預(yù)處理）：1.短語切分 2.專名與數(shù)詞檢測(cè)3.大小寫與拼寫校正4.形態(tài)分析 5.語言的歸一化機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法63ibm公司的candide系統(tǒng)(2) 轉(zhuǎn)換（解碼）：基于統(tǒng)計(jì)的機(jī)器翻譯 解碼分為兩個(gè)階段： 第一階段：使用粗糙模型的堆棧

40、搜索 輸出140個(gè)評(píng)分最高的譯文 語言模型：三元語法 翻譯模型：em trained ibm model 5 第二階段：使用精細(xì)模型的擾動(dòng)搜索 對(duì)第一階段的輸出結(jié)果先擴(kuò)充，再重新評(píng)分 語言模型：鏈語法 翻譯模型：最大熵翻譯模型（選擇譯文詞）機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法64ibm公司的candide系統(tǒng)(3) arpa的測(cè)試結(jié)果 ：fluencyfluencyadequacyadequacytime ratiotime ratio199219921993199319921992199319931992199219931993systransystran.466.466.540.54

41、0.686.686.743.743candidecandide.511.511.580.580.575.575.670.670transmantransman.819.819.838.838.837.837.850.850.688.688.625.625manualmanual.833.833.840.840機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法65內(nèi)容提要 為翻譯建立概率模型 ibm的信源信道模型 語言模型 n元語法模型 翻譯模型 ibm模型1-5 詞語對(duì)齊算法 解碼算法 candide系統(tǒng) egypt工具包與giza+ 機(jī)器翻譯自動(dòng)評(píng)價(jià)機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法66jh

42、u的1999年夏季研討班 由來 ibm的實(shí)驗(yàn)引起了廣泛的興趣 ibm的實(shí)驗(yàn)很難重復(fù)：工作量太大 目的 構(gòu)造一個(gè)統(tǒng)計(jì)機(jī)器翻譯工具（egypt）并使它對(duì)于研究者來說是可用的（免費(fèi)傳播）； 在研討班上用這個(gè)工具集構(gòu)造一個(gè)捷克語英語的機(jī)器翻譯系統(tǒng)； 進(jìn)行基準(zhǔn)評(píng)價(jià)：主觀和客觀； 通過使用形態(tài)和句法轉(zhuǎn)錄機(jī)改進(jìn)基準(zhǔn)測(cè)試的結(jié)果； 在研討班最后，在一天之內(nèi)構(gòu)造一個(gè)新語對(duì)的翻譯器。 jhu夏季研討班大大促進(jìn)了統(tǒng)計(jì)機(jī)器翻譯的研究機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法67egypt工具包 egypt的模塊1.giza：這個(gè)模塊用于從雙語語料庫中抽取統(tǒng)計(jì)知識(shí)（參數(shù)訓(xùn)練）2.decoder：解碼器，用于執(zhí)行具體的翻譯

43、過程（在信源信道模型中，“翻譯”就是“解碼”）3.cairo：整個(gè)翻譯系統(tǒng)的可視化界面，用于管理所有的參數(shù)、查看雙語語料庫對(duì)齊的過程和翻譯模型的解碼過程4.whittle：語料庫預(yù)處理工具 egypt可在網(wǎng)上免費(fèi)下載，成為smt的基準(zhǔn)機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法68egypt工具包的性能“當(dāng)解碼器的原形系統(tǒng)在研討班上完成時(shí)，我們很高興并驚異于其速度和性能。1990年代早期在ibm公司舉行的darpa機(jī)器翻譯評(píng)價(jià)時(shí)，我們?cè)?jīng)預(yù)計(jì)只有很短（10個(gè)詞左右）的句子才可以用統(tǒng)計(jì)方法進(jìn)行解碼，即使那樣，每個(gè)句子的解碼時(shí)間也可能是幾個(gè)小時(shí)。在早期ibm的工作過去將近10年后，摩爾定律、更好的編

44、譯器以及更加充足的內(nèi)存和硬盤空間幫助我們構(gòu)造了一個(gè)能夠在幾秒鐘之內(nèi)對(duì)25個(gè)單詞的句子進(jìn)行解碼的系統(tǒng)。為了確保成功，我們?cè)谒阉髦惺褂昧讼喈?dāng)嚴(yán)格的閾值和約束，如下所述。但是,解碼器相當(dāng)有效這個(gè)事實(shí)為這個(gè)方向未來的工作預(yù)示了很好的前景，并肯定了ibm的工作的初衷，即強(qiáng)調(diào)概率模型比效率更重要?！币詊hu統(tǒng)計(jì)機(jī)器翻譯研討班的技術(shù)報(bào)告機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法69內(nèi)容提要 為翻譯建立概率模型 ibm的信源信道模型 語言模型 n元語法模型 翻譯模型 ibm模型1-5 詞語對(duì)齊算法 解碼算法 candide系統(tǒng) egypt工具包與giza+ 機(jī)器翻譯自動(dòng)評(píng)價(jià)機(jī)器翻譯原理與方法講義(02)機(jī)器

45、翻譯方法70機(jī)器翻譯的評(píng)價(jià) 常見的人工評(píng)價(jià)指標(biāo) 忠實(shí)度和流利度 可理解率 自動(dòng)評(píng)價(jià)的重要意義 反復(fù)使用無需成本 為通過頻繁的實(shí)驗(yàn)提高系統(tǒng)性能提供了基本的保證機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法71基于測(cè)試點(diǎn)的機(jī)器翻譯自動(dòng)評(píng)價(jià) 北大俞士汶于1990年代初期提出 模仿人類的標(biāo)準(zhǔn)化考試的方法，對(duì)每個(gè)題目（源文句子）設(shè)置若干個(gè)測(cè)試點(diǎn) 每個(gè)測(cè)試點(diǎn)只考察一個(gè)問題（比如漢語分詞、詞語譯文選擇等） 判斷測(cè)試點(diǎn)是否被正確翻譯，完全通過字符串匹配，每個(gè)測(cè)試點(diǎn)可以有多種候選的正確答案 是國際上最早出現(xiàn)的機(jī)器翻譯自動(dòng)評(píng)價(jià)方法之一 缺點(diǎn)是題庫的構(gòu)造成本很高，需要對(duì)機(jī)器翻譯有相當(dāng)了解的專家機(jī)器翻譯原理與方法講義(0

46、2)機(jī)器翻譯方法72基于編輯距離的機(jī)器翻譯自動(dòng)評(píng)價(jià) 編輯距離：edit distance，又稱levenshteindistance，用于計(jì)算兩個(gè)字符串之間的距離 編輯距離的含義，是指通過插入、刪除、替換等編輯操作，將一個(gè)字符串變成另外一個(gè)字符串時(shí)，所需要的編輯操作的次數(shù) 常見的基于編輯距離的評(píng)價(jià)指標(biāo)： wer，per，mwer，mper 缺點(diǎn)：對(duì)詞序問題沒有好的處理方法機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法73基于n元語法的機(jī)器翻譯自動(dòng)評(píng)價(jià) 基本思想 對(duì)于每個(gè)源文句子，由多位翻譯人員提供人工翻譯的結(jié)果 將機(jī)器翻譯的結(jié)果與這多個(gè)人工翻譯的結(jié)果進(jìn)行比較，越相似的句子，評(píng)價(jià)越高 這種比較按照一

47、元語法、二元語法、三元語法、分別進(jìn)行，然后進(jìn)行評(píng)價(jià) 常見的評(píng)價(jià)指標(biāo) bleu：各層語法的結(jié)果進(jìn)行幾何平均 nist：各層語法的結(jié)果進(jìn)行算術(shù)平均，同時(shí)考慮信息增益機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法74機(jī)器翻譯自動(dòng)評(píng)價(jià)：例子考慮例子：candidate 1: it is a guide to action which ensures that the military always obeys the command of the partycandidate 2: it is to insure the troops forever hearing the activity guideb

48、ook that party directreference 1: it is a guide to action that ensures that the military will forever heed party commandsreference 2: it is the guiding principle which guarantees the military forces always being under the command of the partyreference 3: it is the practical guide for the army to hee

49、d the directions of the party候選譯文更好？機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法75簡單計(jì)數(shù)方法 計(jì)算候選譯文中n-gram在參考譯文中出現(xiàn)的次數(shù)，除以該候選譯文n-gram總數(shù)，也就是n-gram的正確率。 舉例來說，對(duì)于unigram，也就是計(jì)算候選譯文中的所有詞語中，在參考譯文中出現(xiàn)的詞語數(shù)，除以候選譯文的詞語總數(shù)，就是unigram的正確率。機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法76改進(jìn)的計(jì)數(shù)方法 (1)考慮例子： candidate: the the the the the the the reference 1: the cat is on t

50、he mat. reference 2: there is a cat on the mat.在這個(gè)例子中，如果采用簡單計(jì)數(shù)方法，候選譯文的unigram正確率將是100%，顯然是不合理的改進(jìn)的計(jì)數(shù)方法：對(duì)于同一個(gè)詞的多次出現(xiàn)，其匹配次數(shù)最多只能等于在同一個(gè)參考譯文中該詞出現(xiàn)最多的次數(shù)跟進(jìn)改進(jìn)的計(jì)數(shù)方法，這個(gè)例子中the在參考譯文的同一個(gè)句子中最多出現(xiàn)兩次，因此候選譯文的unigram正確率只有2/7。機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法77改進(jìn)的計(jì)數(shù)方法 (2)再看前面的例子：candidate 1: it is a guide to action which ensures that

51、 the military always obeys the command of the partycandidate 2: it is to insure the troops forever hearing the activity guidebook that party directreference 1: it is a guide to action that ensures that the military will forever heed party commandsreference 2: it is the guiding principle which guaran

52、tees the military forces always being under the command of the partyreference 3: it is the practical guide for the army to heed the directions of the party?candidate 1的bigram正確率達(dá)到了10/17?而candidate 2的bigram正確率只有 1/13.機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法78與忠實(shí)度和流利度的關(guān)系 修改后的n-gram正確率可以認(rèn)為在一定程度上反映了譯文質(zhì)量的兩個(gè)重要方面： 一元語法unigra

53、m正確率主要體現(xiàn)了詞語是否翻譯正確，這反映了譯文忠實(shí)度 二元語法bigram以上的ngram正確率主要體現(xiàn)了詞語的排列順序是否正確，這反映了譯文的流利度機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法79n-gram正確率的計(jì)算公式()()clipccandidates n gram cccandidates n gramccountngrampncount ngram=count(n-gram)是n-gram在某個(gè)候選譯文中的出現(xiàn)次數(shù)countclip(n-gram)是n-gram在某個(gè)候選譯文中出現(xiàn)的次數(shù)，按照同一個(gè)參考譯文中出現(xiàn)最多次數(shù)剪切后的次數(shù)機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法80

54、新問題：召回率問題 (1)考慮這個(gè)例子：candidate1:of thereference1: it is a guide to action that ensures that the military will forever heed party commandsreference2: it is the guiding principle which guarantees the military forces always being under the command of the partyreference3: it is the practical guide for the army to heed the directions of the party 按照上面公式計(jì)算的bigram正確率將是100%，不合理 是召回率太低引起的嗎？機(jī)器翻譯原理與方法講義(02)機(jī)器翻譯方法81新問題：召回率問題