利用依存限制抽取長距離調(diào)序規(guī)則

涂兆鵬，劉 群，林守勛

(中國科學(xué)院 計(jì)算技術(shù)研究所 智能信息處理重點(diǎn)實(shí)驗(yàn)室，北京 100190)

1 前言

過去十年，我們見證了機(jī)器翻譯領(lǐng)域的快速發(fā)展。短語模型[1-2]通過使用短語翻譯替代字翻譯來提高翻譯質(zhì)量，句法模型[3-5]通過加入句法信息進(jìn)一步提高翻譯質(zhì)量。兩類模型各有優(yōu)缺點(diǎn)，具體如表1所示。

層次短語模型[6]使用上下文無關(guān)語法規(guī)則來綜合基于短語模型和基于句法模型的優(yōu)勢，能夠很好地刻畫短語內(nèi)部和短語間的調(diào)序，并且不依賴于句法分析。Chiang表明使用層次短語模型可以比當(dāng)前最好的短語模型高出1到3個BLEU點(diǎn)[6]。

表1 短語模型和句法模型的優(yōu)勢和不足

層次短語模型通過層次規(guī)則來表示短語間的調(diào)序。由于層次規(guī)則是從初始規(guī)則中泛化而來的，如果要抽取隱含長距離調(diào)序信息的規(guī)則，則必須先抽取長跨度的初始短語。這將會生成巨大的規(guī)則表，從而導(dǎo)致極大的解碼系統(tǒng)內(nèi)存和時間消耗。為了避免這個問題，Chiang限制了初始短語的最大跨度的閾值[6]。但是，這樣會削弱模型的長距離調(diào)序能力，因?yàn)橐?guī)則無法表示跨度大于閾值的短語間的長距離調(diào)序。

依存樹能在一定程序上反映調(diào)序信息。Quirk et al.在源端使用依存樹以訓(xùn)練一個調(diào)序模型[7]；Shen et al.通過引入依存語言模型來刻畫目標(biāo)端依存結(jié)構(gòu)中的長距離詞之間的關(guān)系[8]；Ding and Palmer使用依存樹上定義的概率同步依存插入語法[9]。

受上述工作的啟發(fā)，我們提出了一個基本但有效的方法以在層次短語模型上抽取長距離調(diào)序規(guī)則。首先，我們對訓(xùn)練語料的源端進(jìn)行依存分析。然后，我們抽取源端為一棵完整依存子樹或幾棵完整依存子樹集合的長距離調(diào)序規(guī)則。實(shí)驗(yàn)表明，我們的方法可以得到0.74個BLEU點(diǎn)的提高，并且規(guī)則表數(shù)量增加不大。

剩余的章節(jié)安排如下：第2節(jié)，先簡單介紹短語的調(diào)序及分析為什么短語模型在短語的調(diào)序方面表現(xiàn)較差；第3節(jié)，介紹層次短語模型，并分析它的優(yōu)勢和存在的問題；第4節(jié)，描述如何利用依存限制抽取長距離調(diào)序規(guī)則，以解決層次短語存在的問題。為了解決由此帶來的解碼速度過慢的問題，提出了利用前綴樹快速匹配規(guī)則的方法；第5節(jié)，展示實(shí)驗(yàn)結(jié)果及分析；最后一節(jié)，給出總結(jié)和展望。

2 短語的調(diào)序

圖1中給出了一個中文句子，它對應(yīng)的英文翻譯和句對間的對齊。我們可以從中抽取如下短語：

這兩個短語間的調(diào)序關(guān)系，便是短語的調(diào)序。

圖1 一個中文句子，它的英文翻譯和它們之間的對齊

短語模型可以很好地刻畫短語內(nèi)部的調(diào)序信息，但是對于短語間的長距離調(diào)序，短語模型表現(xiàn)較差。比如為了表示短語(1)和(2)的調(diào)序，短語模型可以抽取短語(3)，通過短語內(nèi)部的調(diào)序，來刻畫短語(1)和(2)間的長距離調(diào)序。

打擊 走私 的 成果→results of the crackdown on smuggling

(3)

但是Koehn et al.發(fā)現(xiàn)當(dāng)短語長度超過3的時候，對于系統(tǒng)的性能提高便有限，表明訓(xùn)練語料可能由于數(shù)據(jù)稀疏問題所以無法學(xué)到更長的規(guī)則[1]。比如解碼時如果遇到下面這個詞組，由于訓(xùn)練語料中沒有出現(xiàn)過該詞組，我們便無法找到相應(yīng)的短語，這便是數(shù)據(jù)稀疏問題。對于這個詞組，短語模型只能分別翻譯里面的各個短語“打擊”，“犯罪”和“的 成果”，

打擊 犯罪 的 成果

(4)

犯罪→crime

(5)

調(diào)用短語(1),(2)和(5)，再將之順序拼接起來，得到翻譯“the crackdown on crime results of”而無法利用訓(xùn)練語料中短語(1)和(2)的調(diào)序信息。所以，短語模型對短語間的長距離調(diào)序能力表現(xiàn)較差。

為了解決這一問題，Chiang使用包含變量的層次短語規(guī)則來刻畫短語間的調(diào)序[6]。

3 層次短語模型

3.1 介紹

層次短語模型是基于上下文無關(guān)語法的[6]。正式地，層次短語模型的規(guī)則可以定義如下：

X→〈γ,α,～〉

其中，X是非終結(jié)符，γ和α是源端和目標(biāo)端的字符串 (由終結(jié)符和非終結(jié)符組成)，～表示γ和α之間非終結(jié)符間的對齊。

層次短語模型的規(guī)則抽取可以分為兩步。首先，抽取滿足對齊一致性[2]的初始短語；然后，將初始短語中的子短語替換為非終結(jié)符得到層次短語。比如對于圖1中所示的對齊句對，我們可以首先抽取一個滿足對齊一致性的初始短語：

打擊 走私 的 成果→results of the crackdown on smuggling

然后我們可以通過將子初始短語

走私→smuggling

替換為非終結(jié)符得到一條包含一個非終結(jié)符的規(guī)則：

打擊X1的 成果→results of the crackdown onX1

(6)

這里X表示非終結(jié)符，下標(biāo)表示源端和目標(biāo)端中非終結(jié)符的聯(lián)系。

這樣，層次短語便可以很好地表示短語(1)和(2)間的調(diào)序。當(dāng)遇到詞組(3)時，我們可以通過短語(5)和層次短語(6)來翻譯，具體過程如下：

打擊X1的 成果→ results of the crackdown onX1

打擊 犯罪 的 成果→results of the crackdown on crime

另外，層次短語包含了兩條黏合規(guī)則：

S→〈S1X2,S1X2〉

S→〈X1,X1〉

(7)

粘合規(guī)則是用來將一系列部分翻譯順序拼接起來。

3.2 存在的問題

層次短語是通過將初始短語中的子短語替換成非終結(jié)符而得到的，這會產(chǎn)生極大的規(guī)則表。為了避免規(guī)則表規(guī)模過大，Chiang 限制初始短語的長度最多不能超過L個詞[6]。但這樣，對于長度超過L的初始短語，我們無法從中生成層次短語。那么層次短語模型就無法表示長度超過L的初始短語中的調(diào)序信息。

層次短語模型無法刻畫長度超過L的兩個短語間的調(diào)序，也就是長距離調(diào)序能力。下面我們將會給出長距離調(diào)序的定義，并提出一個解決方案。

4 長距離調(diào)序

長距離調(diào)序是指距離較長的兩個短語間的調(diào)序，在本文中特指距離超過Chiang規(guī)定的最大長度L[6]的兩個短語間的調(diào)序。

4.1 利用依存限制抽取長距離調(diào)序規(guī)則

使用傳統(tǒng)的規(guī)則抽取方法抽取長距離調(diào)序規(guī)則將會生成極大的規(guī)則表，從而影響翻譯速度及所占內(nèi)存。我們認(rèn)為一個可能的原因是對齊一致性的約束較弱。對于長度超過L的初始短語，里面會包含很多滿足對齊一致性的子短語，從而生成指數(shù)級的長距離調(diào)序規(guī)則。

一個解決方法是在抽取長距離調(diào)序規(guī)則時，對于子短語加入更強(qiáng)的限制，以減少滿足條件的子短語，從而減少抽取的長距離調(diào)序規(guī)則。為了解決這一問題，我們在抽取長距離調(diào)序規(guī)則時加入依存限制，以抽取數(shù)量可以接受的高質(zhì)量長距離調(diào)序規(guī)則。

圖2顯示了一個中文句子 “中國 今天 公布 了 去年 打擊 走私 的 成果” 的依存樹。箭頭由子節(jié)點(diǎn)指向它的父節(jié)點(diǎn)，或稱為頭節(jié)點(diǎn)。比如在圖2中，“公布”是“中國”的父節(jié)點(diǎn)或頭節(jié)點(diǎn)。依存樹可以反映詞語間，尤其是較長距離的詞語間的關(guān)系[7-9]。比如圖2中，“成果”直接依存于“公布”。此外，我們觀察到同時滿足對齊一致性和依存結(jié)構(gòu)完整性的初始短語是一個非常好的整體。比如從圖2抽取的初始短語 (去年 打擊 走私 的 成果，last year’s of the crackdown on smuggling)。

為此，我們限定長距離調(diào)序規(guī)則的源端必須是完整的依存結(jié)構(gòu)。完整的依存結(jié)構(gòu)是指一棵或多棵完整依存子樹的集合。參考Shen et al.中對依存結(jié)構(gòu)的定義[8]，我們對其嚴(yán)格定義如下：

定義1：對于一個句子S=w1w2…wn，d1d2…dn表示每個詞的頭節(jié)點(diǎn)(父節(jié)點(diǎn))，對于根節(jié)點(diǎn)wi，我們定義di=0。一個依存結(jié)構(gòu)di…dj是頭節(jié)點(diǎn)集合H的完整依存結(jié)構(gòu)，當(dāng)且僅當(dāng)

圖3給出了兩個完整依存結(jié)構(gòu)的例子，(a)和(b)的頭節(jié)點(diǎn)集合分別是 (中國, 今天)和(成果)。我們可以發(fā)現(xiàn)(a)和(b)同樣滿足對齊一致性。

假設(shè)層次短語模型傳統(tǒng)算法中初始短語的最大跨度L為7(論文中為10，這里為敘述方便作此假設(shè))，則對于跨度為9的源端“中國 去年 公布 了 去年 打擊 走私 的 成果”，傳統(tǒng)抽取算法無法處理。而我們可以通過將同時滿足對齊一致性和完整依存結(jié)構(gòu)限制的圖3中(a)和(b)結(jié)構(gòu)泛化成非終結(jié)符得到長距離調(diào)序規(guī)則 (X1公布 了X2,X1announcedX2)。

由于長距離調(diào)序規(guī)則覆蓋的詞語較多，我們可以抽取包含多個終結(jié)符的規(guī)則。我們使用LDDR_n表示包含n個非終結(jié)符的長距離調(diào)序規(guī)則。此外，為了將長距離調(diào)序規(guī)則和普通規(guī)則區(qū)分開來，我們在解碼時加入一個新的特征：長距離規(guī)則計(jì)數(shù)，計(jì)算解碼時用到的長距離調(diào)序規(guī)則的數(shù)量，與普通規(guī)則計(jì)數(shù)相對應(yīng)。

圖2 一個中文依存樹，它的英文翻譯和它們之間的對齊(為了更清楚地表示中英文之間的聯(lián)系，我們同樣給出了中文句子)

圖3 完整依存結(jié)構(gòu)的示例((a)和(b)的頭節(jié)點(diǎn)集合分別是 (中國, 今天)和(成果))

4.2 規(guī)則快速匹配

層次短語模型使用自底向上的CKY算法來生成推導(dǎo)。對于一個長度為l的跨度，傳統(tǒng)的規(guī)則匹配算法是枚舉出所有可能的候選規(guī)則，然后在規(guī)則表中查找。假設(shè)每條規(guī)則最多含有m個非終結(jié)符，則將會有O(l2m)個候選規(guī)則。對于l>10的跨度，枚舉所有候選規(guī)則是非常耗時的。

受Lopez工作的啟發(fā)[10]，我們使用前綴樹結(jié)構(gòu)存儲規(guī)則，并構(gòu)建詞圖表示候選規(guī)則。如圖4所示，對于輸入abcd,所有的候選規(guī)則只能以a或變量X起始。我們首先查找所有以a起始的候選規(guī)則，在規(guī)則表中我們找到了以a開始的規(guī)則；起始為a的候選規(guī)則后面只能接b或變量X，然后我們在規(guī)則表中發(fā)現(xiàn)以a起始的規(guī)則后面只有接b的規(guī)則，所以所有aX起始的候選規(guī)則均不存在于規(guī)則表中。

圖4 前綴樹規(guī)則表和詞組候選規(guī)則(每條曲線箭頭表示一個變量)

5 實(shí)驗(yàn)

5.1 數(shù)據(jù)準(zhǔn)備

我們使用FBIS語料 (約240K句對)作為訓(xùn)練語料，并使用移進(jìn)—?dú)w約的依存分析器[11]對源端進(jìn)行依存分析。為了得到更好的依存分析結(jié)果，我們過濾源句子超過40的句對，則剩下的句對數(shù)為190K。我們在訓(xùn)練數(shù)據(jù)上運(yùn)行GIZA++[12]以生成對齊句對。我們使用SRI工具[13]在新華語料的GIGAWORD部分訓(xùn)練一個四元的語言模型，訓(xùn)練中采用改進(jìn)的Kneser-Ney平滑方法[14]。

所有的實(shí)驗(yàn)均是在漢-英測試集上執(zhí)行的。我們用最小錯誤率訓(xùn)練[15]方法在NIST 2002數(shù)據(jù)集上調(diào)參，并在NIST 2005數(shù)據(jù)集上測試。使用大小寫不敏感的BLEU[16]測試翻譯質(zhì)量。

我們使用修改的層次短語模型來完成翻譯，在層次短語模型上加入了一個新的特征——長距離調(diào)序規(guī)則計(jì)數(shù)，以將之和普通規(guī)則區(qū)分開。當(dāng)跨度小于10時，我們使用傳統(tǒng)抽取算法抽取規(guī)則；當(dāng)大于10時，我們使用3.1節(jié)所定義的方法抽取長距離調(diào)序規(guī)則。

5.2 結(jié)果

表1列出了規(guī)則表大小和BLEU值。我們可以發(fā)現(xiàn)新增的長距離調(diào)序規(guī)則的數(shù)量是可以接受的 (<10%)。當(dāng)長距離調(diào)序規(guī)則所含的最大非終結(jié)符數(shù)目增加時，規(guī)則數(shù)量增加并不明顯。一個可能的原因是僅有較少的初始短語同時滿足對齊一致性和完整依存結(jié)構(gòu)兩個限制。我們發(fā)現(xiàn)使用長距離調(diào)序規(guī)則可以得到0.74個BLEU點(diǎn)的提高。

表2 規(guī)則表大小和BLEU值。

表3 不同規(guī)則匹配方法的平均時間 (秒/句)。

NIST05測試集包含1 082個句子，平均長度為28個單詞。規(guī)則表包含1.7M的普通規(guī)則和190K的長距離調(diào)序規(guī)則。表3顯示了不同規(guī)則匹配方法消耗的時間。我們發(fā)現(xiàn)傳統(tǒng)規(guī)則匹配方法的大部分時間花在枚舉規(guī)則上。由于使用了長距離調(diào)序規(guī)則，傳統(tǒng)方法需要枚舉整個句子所有的候選規(guī)則，所以候選規(guī)則數(shù)量極其多。這也導(dǎo)致規(guī)則匹配所需時間稍長。而當(dāng)我們使用快速匹配方法時，基本上不用花費(fèi)時間構(gòu)造詞圖，而規(guī)則匹配的時間也僅需要0.15秒/句，較之傳統(tǒng)方法極大的減少了時間。這是由于我們在快速匹配時采用動態(tài)規(guī)則的方法，匹配過程舍棄了大部分不可能存在于規(guī)則表的候選規(guī)則。

6 總結(jié)與展望

本文提出了一個基本但有效的方法抽取長距離調(diào)序規(guī)則，利用依存限制減少子短語的數(shù)量，以抽取數(shù)量可以接受的長距離調(diào)序規(guī)則。相應(yīng)地，我們設(shè)計(jì)了新的規(guī)則匹配算法以快速匹配長距離調(diào)序規(guī)則。實(shí)驗(yàn)表明使用我們的方法可以在生成較少數(shù)量長距離調(diào)序規(guī)則的情況下，得到0.74個BLEU點(diǎn)的提高。

盡管如此，我們的方法仍然依賴于詞語對齊和依存分析。將來我們會設(shè)計(jì)新的算法以減輕對詞語對齊和依存分析的依賴，比如，使用對齊矩陣[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.