涂兆鵬，劉 群，林守勛

(中國科學院 計算技術研究所 智能信息處理重點實驗室，北京 100190)

1 前言

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

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

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

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

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

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

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

2 短語的調序

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

這兩個短語間的調序關系，便是短語的調序。

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

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

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

(3)

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

打擊 犯罪 的 成果

(4)

犯罪→crime

(5)

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

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

3 層次短語模型

3.1 介紹

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

X→〈γ,α,～〉

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

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

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

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

走私→smuggling

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

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

(6)

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

這樣，層次短語便可以很好地表示短語(1)和(2)間的調序。當遇到詞組(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 存在的問題

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

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

4 長距離調序

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

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

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

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

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

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

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

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

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

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

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

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

4.2 規(guī)則快速匹配

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

受Lopez工作的啟發(fā)[10]，我們使用前綴樹結構存儲規(guī)則，并構建詞圖表示候選規(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 實驗

5.1 數(shù)據(jù)準備

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

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

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

5.2 結果

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

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

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

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

6 總結與展望

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

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