涂兆鵬,劉 群,林守勛
(中國(guó)科學(xué)院 計(jì)算技術(shù)研究所 智能信息處理重點(diǎn)實(shí)驗(yàn)室,北京 100190)
過(guò)去十年,我們見證了機(jī)器翻譯領(lǐng)域的快速發(fā)展。短語(yǔ)模型[1-2]通過(guò)使用短語(yǔ)翻譯替代字翻譯來(lái)提高翻譯質(zhì)量,句法模型[3-5]通過(guò)加入句法信息進(jìn)一步提高翻譯質(zhì)量。兩類模型各有優(yōu)缺點(diǎn),具體如表1所示。
層次短語(yǔ)模型[6]使用上下文無(wú)關(guān)語(yǔ)法規(guī)則來(lái)綜合基于短語(yǔ)模型和基于句法模型的優(yōu)勢(shì),能夠很好地刻畫短語(yǔ)內(nèi)部和短語(yǔ)間的調(diào)序,并且不依賴于句法分析。Chiang表明使用層次短語(yǔ)模型可以比當(dāng)前最好的短語(yǔ)模型高出1到3個(gè)BLEU點(diǎn)[6]。
表1 短語(yǔ)模型和句法模型的優(yōu)勢(shì)和不足
層次短語(yǔ)模型通過(guò)層次規(guī)則來(lái)表示短語(yǔ)間的調(diào)序。由于層次規(guī)則是從初始規(guī)則中泛化而來(lái)的,如果要抽取隱含長(zhǎng)距離調(diào)序信息的規(guī)則,則必須先抽取長(zhǎng)跨度的初始短語(yǔ)。這將會(huì)生成巨大的規(guī)則表,從而導(dǎo)致極大的解碼系統(tǒng)內(nèi)存和時(shí)間消耗。為了避免這個(gè)問(wèn)題,Chiang限制了初始短語(yǔ)的最大跨度的閾值[6]。但是,這樣會(huì)削弱模型的長(zhǎng)距離調(diào)序能力,因?yàn)橐?guī)則無(wú)法表示跨度大于閾值的短語(yǔ)間的長(zhǎng)距離調(diào)序。
依存樹能在一定程序上反映調(diào)序信息。Quirk et al.在源端使用依存樹以訓(xùn)練一個(gè)調(diào)序模型[7];Shen et al.通過(guò)引入依存語(yǔ)言模型來(lái)刻畫目標(biāo)端依存結(jié)構(gòu)中的長(zhǎng)距離詞之間的關(guān)系[8];Ding and Palmer使用依存樹上定義的概率同步依存插入語(yǔ)法[9]。
受上述工作的啟發(fā),我們提出了一個(gè)基本但有效的方法以在層次短語(yǔ)模型上抽取長(zhǎng)距離調(diào)序規(guī)則。首先,我們對(duì)訓(xùn)練語(yǔ)料的源端進(jìn)行依存分析。然后,我們抽取源端為一棵完整依存子樹或幾棵完整依存子樹集合的長(zhǎng)距離調(diào)序規(guī)則。實(shí)驗(yàn)表明,我們的方法可以得到0.74個(gè)BLEU點(diǎn)的提高,并且規(guī)則表數(shù)量增加不大。
剩余的章節(jié)安排如下:第2節(jié),先簡(jiǎn)單介紹短語(yǔ)的調(diào)序及分析為什么短語(yǔ)模型在短語(yǔ)的調(diào)序方面表現(xiàn)較差;第3節(jié),介紹層次短語(yǔ)模型,并分析它的優(yōu)勢(shì)和存在的問(wèn)題;第4節(jié),描述如何利用依存限制抽取長(zhǎng)距離調(diào)序規(guī)則,以解決層次短語(yǔ)存在的問(wèn)題。為了解決由此帶來(lái)的解碼速度過(guò)慢的問(wèn)題,提出了利用前綴樹快速匹配規(guī)則的方法;第5節(jié),展示實(shí)驗(yàn)結(jié)果及分析;最后一節(jié),給出總結(jié)和展望。
圖1中給出了一個(gè)中文句子,它對(duì)應(yīng)的英文翻譯和句對(duì)間的對(duì)齊。我們可以從中抽取如下短語(yǔ):
這兩個(gè)短語(yǔ)間的調(diào)序關(guān)系,便是短語(yǔ)的調(diào)序。
圖1 一個(gè)中文句子,它的英文翻譯和它們之間的對(duì)齊
短語(yǔ)模型可以很好地刻畫短語(yǔ)內(nèi)部的調(diào)序信息,但是對(duì)于短語(yǔ)間的長(zhǎng)距離調(diào)序,短語(yǔ)模型表現(xiàn)較差。比如為了表示短語(yǔ)(1)和(2)的調(diào)序,短語(yǔ)模型可以抽取短語(yǔ)(3),通過(guò)短語(yǔ)內(nèi)部的調(diào)序,來(lái)刻畫短語(yǔ)(1)和(2)間的長(zhǎng)距離調(diào)序。
打擊 走私 的 成果→results of the crackdown on smuggling
(3)
但是Koehn et al.發(fā)現(xiàn)當(dāng)短語(yǔ)長(zhǎng)度超過(guò)3的時(shí)候,對(duì)于系統(tǒng)的性能提高便有限,表明訓(xùn)練語(yǔ)料可能由于數(shù)據(jù)稀疏問(wèn)題所以無(wú)法學(xué)到更長(zhǎng)的規(guī)則[1]。比如解碼時(shí)如果遇到下面這個(gè)詞組,由于訓(xùn)練語(yǔ)料中沒有出現(xiàn)過(guò)該詞組,我們便無(wú)法找到相應(yīng)的短語(yǔ),這便是數(shù)據(jù)稀疏問(wèn)題。對(duì)于這個(gè)詞組,短語(yǔ)模型只能分別翻譯里面的各個(gè)短語(yǔ)“打擊”,“犯罪”和“的 成果”,
打擊 犯罪 的 成果
(4)
犯罪→crime
(5)
調(diào)用短語(yǔ)(1),(2)和(5),再將之順序拼接起來(lái),得到翻譯“the crackdown on crime results of”而無(wú)法利用訓(xùn)練語(yǔ)料中短語(yǔ)(1)和(2)的調(diào)序信息。所以,短語(yǔ)模型對(duì)短語(yǔ)間的長(zhǎng)距離調(diào)序能力表現(xiàn)較差。
為了解決這一問(wèn)題,Chiang使用包含變量的層次短語(yǔ)規(guī)則來(lái)刻畫短語(yǔ)間的調(diào)序[6]。
層次短語(yǔ)模型是基于上下文無(wú)關(guān)語(yǔ)法的[6]。正式地,層次短語(yǔ)模型的規(guī)則可以定義如下:
X→〈γ,α,~〉
其中,X是非終結(jié)符,γ和α是源端和目標(biāo)端的字符串 (由終結(jié)符和非終結(jié)符組成),~表示γ和α之間非終結(jié)符間的對(duì)齊。
層次短語(yǔ)模型的規(guī)則抽取可以分為兩步。首先,抽取滿足對(duì)齊一致性[2]的初始短語(yǔ);然后,將初始短語(yǔ)中的子短語(yǔ)替換為非終結(jié)符得到層次短語(yǔ)。比如對(duì)于圖1中所示的對(duì)齊句對(duì),我們可以首先抽取一個(gè)滿足對(duì)齊一致性的初始短語(yǔ):
打擊 走私 的 成果→results of the crackdown on smuggling
然后我們可以通過(guò)將子初始短語(yǔ)
走私→smuggling
替換為非終結(jié)符得到一條包含一個(gè)非終結(jié)符的規(guī)則:
打擊X1的 成果→results of the crackdown onX1
(6)
這里X表示非終結(jié)符,下標(biāo)表示源端和目標(biāo)端中非終結(jié)符的聯(lián)系。
這樣,層次短語(yǔ)便可以很好地表示短語(yǔ)(1)和(2)間的調(diào)序。當(dāng)遇到詞組(3)時(shí),我們可以通過(guò)短語(yǔ)(5)和層次短語(yǔ)(6)來(lái)翻譯,具體過(guò)程如下:
打擊X1的 成果→ results of the crackdown onX1
打擊 犯罪 的 成果→results of the crackdown on crime
另外,層次短語(yǔ)包含了兩條黏合規(guī)則:
S→〈S1X2,S1X2〉
S→〈X1,X1〉
(7)
粘合規(guī)則是用來(lái)將一系列部分翻譯順序拼接起來(lái)。
層次短語(yǔ)是通過(guò)將初始短語(yǔ)中的子短語(yǔ)替換成非終結(jié)符而得到的,這會(huì)產(chǎn)生極大的規(guī)則表。為了避免規(guī)則表規(guī)模過(guò)大,Chiang 限制初始短語(yǔ)的長(zhǎng)度最多不能超過(guò)L個(gè)詞[6]。但這樣,對(duì)于長(zhǎng)度超過(guò)L的初始短語(yǔ),我們無(wú)法從中生成層次短語(yǔ)。那么層次短語(yǔ)模型就無(wú)法表示長(zhǎng)度超過(guò)L的初始短語(yǔ)中的調(diào)序信息。
層次短語(yǔ)模型無(wú)法刻畫長(zhǎng)度超過(guò)L的兩個(gè)短語(yǔ)間的調(diào)序,也就是長(zhǎng)距離調(diào)序能力。下面我們將會(huì)給出長(zhǎng)距離調(diào)序的定義,并提出一個(gè)解決方案。
長(zhǎng)距離調(diào)序是指距離較長(zhǎng)的兩個(gè)短語(yǔ)間的調(diào)序,在本文中特指距離超過(guò)Chiang規(guī)定的最大長(zhǎng)度L[6]的兩個(gè)短語(yǔ)間的調(diào)序。
使用傳統(tǒng)的規(guī)則抽取方法抽取長(zhǎng)距離調(diào)序規(guī)則將會(huì)生成極大的規(guī)則表,從而影響翻譯速度及所占內(nèi)存。我們認(rèn)為一個(gè)可能的原因是對(duì)齊一致性的約束較弱。對(duì)于長(zhǎng)度超過(guò)L的初始短語(yǔ),里面會(huì)包含很多滿足對(duì)齊一致性的子短語(yǔ),從而生成指數(shù)級(jí)的長(zhǎng)距離調(diào)序規(guī)則。
一個(gè)解決方法是在抽取長(zhǎng)距離調(diào)序規(guī)則時(shí),對(duì)于子短語(yǔ)加入更強(qiáng)的限制,以減少滿足條件的子短語(yǔ),從而減少抽取的長(zhǎng)距離調(diào)序規(guī)則。為了解決這一問(wèn)題,我們?cè)诔槿¢L(zhǎng)距離調(diào)序規(guī)則時(shí)加入依存限制,以抽取數(shù)量可以接受的高質(zhì)量長(zhǎng)距離調(diào)序規(guī)則。
圖2顯示了一個(gè)中文句子 “中國(guó) 今天 公布 了 去年 打擊 走私 的 成果” 的依存樹。箭頭由子節(jié)點(diǎn)指向它的父節(jié)點(diǎn),或稱為頭節(jié)點(diǎn)。比如在圖2中,“公布”是“中國(guó)”的父節(jié)點(diǎn)或頭節(jié)點(diǎn)。依存樹可以反映詞語(yǔ)間,尤其是較長(zhǎng)距離的詞語(yǔ)間的關(guān)系[7-9]。比如圖2中,“成果”直接依存于“公布”。此外,我們觀察到同時(shí)滿足對(duì)齊一致性和依存結(jié)構(gòu)完整性的初始短語(yǔ)是一個(gè)非常好的整體。比如從圖2抽取的初始短語(yǔ) (去年 打擊 走私 的 成果,last year’s of the crackdown on smuggling)。
為此,我們限定長(zhǎng)距離調(diào)序規(guī)則的源端必須是完整的依存結(jié)構(gòu)。完整的依存結(jié)構(gòu)是指一棵或多棵完整依存子樹的集合。參考Shen et al.中對(duì)依存結(jié)構(gòu)的定義[8],我們對(duì)其嚴(yán)格定義如下:
定義1:對(duì)于一個(gè)句子S=w1w2…wn,d1d2…dn表示每個(gè)詞的頭節(jié)點(diǎn)(父節(jié)點(diǎn)),對(duì)于根節(jié)點(diǎn)wi,我們定義di=0。一個(gè)依存結(jié)構(gòu)di…dj是頭節(jié)點(diǎn)集合H的完整依存結(jié)構(gòu),當(dāng)且僅當(dāng)
圖3給出了兩個(gè)完整依存結(jié)構(gòu)的例子,(a)和(b)的頭節(jié)點(diǎn)集合分別是 (中國(guó), 今天)和(成果)。我們可以發(fā)現(xiàn)(a)和(b)同樣滿足對(duì)齊一致性。
假設(shè)層次短語(yǔ)模型傳統(tǒng)算法中初始短語(yǔ)的最大跨度L為7(論文中為10,這里為敘述方便作此假設(shè)),則對(duì)于跨度為9的源端“中國(guó) 去年 公布 了 去年 打擊 走私 的 成果”,傳統(tǒng)抽取算法無(wú)法處理。而我們可以通過(guò)將同時(shí)滿足對(duì)齊一致性和完整依存結(jié)構(gòu)限制的圖3中(a)和(b)結(jié)構(gòu)泛化成非終結(jié)符得到長(zhǎng)距離調(diào)序規(guī)則 (X1公布 了X2,X1announcedX2)。
由于長(zhǎng)距離調(diào)序規(guī)則覆蓋的詞語(yǔ)較多,我們可以抽取包含多個(gè)終結(jié)符的規(guī)則。我們使用LDDR_n表示包含n個(gè)非終結(jié)符的長(zhǎng)距離調(diào)序規(guī)則。此外,為了將長(zhǎng)距離調(diào)序規(guī)則和普通規(guī)則區(qū)分開來(lái),我們?cè)诮獯a時(shí)加入一個(gè)新的特征:長(zhǎng)距離規(guī)則計(jì)數(shù),計(jì)算解碼時(shí)用到的長(zhǎng)距離調(diào)序規(guī)則的數(shù)量,與普通規(guī)則計(jì)數(shù)相對(duì)應(yīng)。
圖2 一個(gè)中文依存樹,它的英文翻譯和它們之間的對(duì)齊(為了更清楚地表示中英文之間的聯(lián)系,我們同樣給出了中文句子)
圖3 完整依存結(jié)構(gòu)的示例((a)和(b)的頭節(jié)點(diǎn)集合分別是 (中國(guó), 今天)和(成果))
層次短語(yǔ)模型使用自底向上的CKY算法來(lái)生成推導(dǎo)。對(duì)于一個(gè)長(zhǎng)度為l的跨度,傳統(tǒng)的規(guī)則匹配算法是枚舉出所有可能的候選規(guī)則,然后在規(guī)則表中查找。假設(shè)每條規(guī)則最多含有m個(gè)非終結(jié)符,則將會(huì)有O(l2m)個(gè)候選規(guī)則。對(duì)于l>10的跨度,枚舉所有候選規(guī)則是非常耗時(shí)的。
受Lopez工作的啟發(fā)[10],我們使用前綴樹結(jié)構(gòu)存儲(chǔ)規(guī)則,并構(gòu)建詞圖表示候選規(guī)則。如圖4所示,對(duì)于輸入abcd,所有的候選規(guī)則只能以a或變量X起始。我們首先查找所有以a起始的候選規(guī)則,在規(guī)則表中我們找到了以a開始的規(guī)則;起始為a的候選規(guī)則后面只能接b或變量X,然后我們?cè)谝?guī)則表中發(fā)現(xiàn)以a起始的規(guī)則后面只有接b的規(guī)則,所以所有aX起始的候選規(guī)則均不存在于規(guī)則表中。
圖4 前綴樹規(guī)則表和詞組候選規(guī)則(每條曲線箭頭表示一個(gè)變量)
我們使用FBIS語(yǔ)料 (約240K句對(duì))作為訓(xùn)練語(yǔ)料,并使用移進(jìn)—?dú)w約的依存分析器[11]對(duì)源端進(jìn)行依存分析。為了得到更好的依存分析結(jié)果,我們過(guò)濾源句子超過(guò)40的句對(duì),則剩下的句對(duì)數(shù)為190K。我們?cè)谟?xùn)練數(shù)據(jù)上運(yùn)行GIZA++[12]以生成對(duì)齊句對(duì)。我們使用SRI工具[13]在新華語(yǔ)料的GIGAWORD部分訓(xùn)練一個(gè)四元的語(yǔ)言模型,訓(xùn)練中采用改進(jìn)的Kneser-Ney平滑方法[14]。
所有的實(shí)驗(yàn)均是在漢-英測(cè)試集上執(zhí)行的。我們用最小錯(cuò)誤率訓(xùn)練[15]方法在NIST 2002數(shù)據(jù)集上調(diào)參,并在NIST 2005數(shù)據(jù)集上測(cè)試。使用大小寫不敏感的BLEU[16]測(cè)試翻譯質(zhì)量。
我們使用修改的層次短語(yǔ)模型來(lái)完成翻譯,在層次短語(yǔ)模型上加入了一個(gè)新的特征——長(zhǎng)距離調(diào)序規(guī)則計(jì)數(shù),以將之和普通規(guī)則區(qū)分開。當(dāng)跨度小于10時(shí),我們使用傳統(tǒng)抽取算法抽取規(guī)則;當(dāng)大于10時(shí),我們使用3.1節(jié)所定義的方法抽取長(zhǎng)距離調(diào)序規(guī)則。
表1列出了規(guī)則表大小和BLEU值。我們可以發(fā)現(xiàn)新增的長(zhǎng)距離調(diào)序規(guī)則的數(shù)量是可以接受的 (<10%)。當(dāng)長(zhǎng)距離調(diào)序規(guī)則所含的最大非終結(jié)符數(shù)目增加時(shí),規(guī)則數(shù)量增加并不明顯。一個(gè)可能的原因是僅有較少的初始短語(yǔ)同時(shí)滿足對(duì)齊一致性和完整依存結(jié)構(gòu)兩個(gè)限制。我們發(fā)現(xiàn)使用長(zhǎng)距離調(diào)序規(guī)則可以得到0.74個(gè)BLEU點(diǎn)的提高。
表2 規(guī)則表大小和BLEU值。
表3 不同規(guī)則匹配方法的平均時(shí)間 (秒/句)。
NIST05測(cè)試集包含1 082個(gè)句子,平均長(zhǎng)度為28個(gè)單詞。規(guī)則表包含1.7M的普通規(guī)則和190K的長(zhǎng)距離調(diào)序規(guī)則。表3顯示了不同規(guī)則匹配方法消耗的時(shí)間。我們發(fā)現(xiàn)傳統(tǒng)規(guī)則匹配方法的大部分時(shí)間花在枚舉規(guī)則上。由于使用了長(zhǎng)距離調(diào)序規(guī)則,傳統(tǒng)方法需要枚舉整個(gè)句子所有的候選規(guī)則,所以候選規(guī)則數(shù)量極其多。這也導(dǎo)致規(guī)則匹配所需時(shí)間稍長(zhǎng)。而當(dāng)我們使用快速匹配方法時(shí),基本上不用花費(fèi)時(shí)間構(gòu)造詞圖,而規(guī)則匹配的時(shí)間也僅需要0.15秒/句,較之傳統(tǒng)方法極大的減少了時(shí)間。這是由于我們?cè)诳焖倨ヅ鋾r(shí)采用動(dòng)態(tài)規(guī)則的方法,匹配過(guò)程舍棄了大部分不可能存在于規(guī)則表的候選規(guī)則。
本文提出了一個(gè)基本但有效的方法抽取長(zhǎng)距離調(diào)序規(guī)則,利用依存限制減少子短語(yǔ)的數(shù)量,以抽取數(shù)量可以接受的長(zhǎng)距離調(diào)序規(guī)則。相應(yīng)地,我們?cè)O(shè)計(jì)了新的規(guī)則匹配算法以快速匹配長(zhǎng)距離調(diào)序規(guī)則。實(shí)驗(yàn)表明使用我們的方法可以在生成較少數(shù)量長(zhǎng)距離調(diào)序規(guī)則的情況下,得到0.74個(gè)BLEU點(diǎn)的提高。
盡管如此,我們的方法仍然依賴于詞語(yǔ)對(duì)齊和依存分析。將來(lái)我們會(huì)設(shè)計(jì)新的算法以減輕對(duì)詞語(yǔ)對(duì)齊和依存分析的依賴,比如,使用對(duì)齊矩陣[17]和依存森林[18]。
[1] Philipp Koehn, Franz Joseph Och, and Daniel Marcu. Statistical phrase-based translation [C]//Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology, 2003:48-54.
[2] Franz Joseph Och and Hermann Ney. The alignment template approach to statistical machine translation [J]. Computational Linguistics, 2004, MIT Press, Volume 30: 417-449.
[3] Yang Liu, Qun Liu, and Shouxun Lin. Tree-to-string alignment template for statistical machine translation [C]//Proceedings of the 44th Annual Meeting of the Association for Computational Linguistics, 2006:609-616.
[4] Liang Huang, Kevin Knight, and Aravind Joshi. Statistical syntax-directed translation with extended domain of locality [C]//Proceedings of the Workshop on Computationally Hard Problems and Joint Inference in Speech and Language Processing, 2006: 66-73.
[5] Michel Galley, Jonathan Graehl, Kevin Knight, Daniel Marcu, Steve DeNeefe, Wei Wang, and Ignacio Thayer. Scalable inference and training of context-rich syntactic translation models [C]//Proceedings of the 44th Annual Meeting of the Association for Computational Linguistics, 2006:961-968.
[6] David Chiang. Hierarchical phrase-based translation [J]. Computational Linguistics, 2007, MIT Press, Volume 33: 201-228.
[7] Chris Quirk, Arul Menezes, and Colin Cherry. Dependency treelet translation: syntactically informed phrasal SMT [C]//Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, 2005:271-279.
[8] Libin Shen, Jinxi Xuand, and Ralph Weischedel. A new string-to-dependency machine translation algorithm with a target dependency language model [C]//46th Annual Meeting of the Association for Computational Linguistics,2008: 577-585.
[9] Yuan Ding and Martha Palmer. Machine translation using probabilistic synchronous dependency insertion grammars [C]//Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, 2005: 541-548.
[10] Adam Lopez. Hierarchical phrase-based translation with suffix arrays [C]//Proceedings of the 2007 Conference on Empirical Methods in Natural Language Processing , 2007: 976-985.
[11] Liang Huang, Wenbin Jiang, and Qun Liu. Bilingually-constrained (monolingual) shift-reduce parsing [C]//Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, 2009:1222-1231.
[12] Franz Joseph Och and Hermann Ney. Improved statistical alignment models [C]//Proceedings of the 38th Annual Meeting on Association for Computational Linguistics, 2000: 440-447.
[13] Andreas Stolcke. Srilm - an extensible language modeling toolkit [C]//Proceedings of Seventh International Conference on Spoken Language Processing, 2002: 901-904.
[14] Reinhard Kneser and Hermann Ney. Improved backing-off for m-gram language modeling [C]//Proceedings of Acoustics, Speech, and Signal, 1995: 181-184.
[15] Franz Joseph Och and Hermann Ney. Discriminative training and maximum entropy models for statistical machine translation [C]//Proceedings of 40th Annual Meeting of the Association for Computational Linguistics, 2002: 295-302.
[16] Kishore Papineni, Salim Roukos, Todd Ward, and WeiJing Zhu. Bleu: a method for automatic evaluation of machine translation [C]//Proceedings of 40th Annual Meeting of the Association for Computational Linguistics, 2002: 311-318.
[17] Yang Liu, Tian Xia, Xinyan Xiao, and Qun Liu. Weighted alignment matrices for statistical machine translation [C]//Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, 2009: 1017-1026.
[18] Zhaopeng Tu, Yang Liu, Young-Sook Hwang, Liu, Qun Liu and Shouxun Lin. Dependency Forest for Statistical Machine Translation [C]//Proceedings of the 23rd International Conference on Computational Linguistics, 2010: 1092-1100.