熊 皓,劉 洋,劉 群

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

1 導(dǎo)論

最近幾年來(lái)，基于樹(shù)的翻譯模型受到了越來(lái)越多的關(guān)注，并且在近幾年的NIST翻譯評(píng)測(cè)中取得了不錯(cuò)的成績(jī)。根據(jù)輸入的不同，基于樹(shù)的模型可以分為以下兩類：串輸入模型[1-4]和樹(shù)輸入模型[5-6]。串輸入模型使用上下文同步文法對(duì)輸入的文本串同時(shí)進(jìn)行句法分析和翻譯；而樹(shù)輸入模型則直接將輸入的句法樹(shù)轉(zhuǎn)換成目標(biāo)翻譯或者目標(biāo)句法樹(shù)。

樹(shù)輸入的模型主要包括樹(shù)到串翻譯模型[7-8]和樹(shù)到樹(shù)翻譯模型[9-11]。這兩種模型都將解碼部分分為兩個(gè)步驟：句法分析和翻譯。首先使用句法分析器將輸入的源文本串分析成一棵句法分析樹(shù)，然后利用解碼器將句法樹(shù)轉(zhuǎn)換成目標(biāo)翻譯。然而對(duì)于某些語(yǔ)言來(lái)說(shuō)，比如中文，句法分析的準(zhǔn)確率遠(yuǎn)沒(méi)有達(dá)到令人滿意的結(jié)果。因此，解碼器的性能不可避免的要受句法分析錯(cuò)誤的影響[12]。

為了減輕句法分析錯(cuò)誤對(duì)翻譯性能的影響，一種可行的方法是在源端使用句法分析森林來(lái)替代單棵最優(yōu)句法樹(shù)[13-14]。上述文獻(xiàn)也表明使用森林技術(shù)可以在很大程度上提高翻譯的質(zhì)量。但是不管是使用單棵句法分析樹(shù)還是使用森林，以往的工作都是將規(guī)則表示為文本串，然后使用字符串匹配技術(shù)從規(guī)則表中搜索可用的規(guī)則。但是有些規(guī)則所含的節(jié)點(diǎn)數(shù)目非常多，如果使用字符串匹配技術(shù)進(jìn)行完全匹配，從規(guī)則表中很難找到可用的規(guī)則。例如，對(duì)于如下兩條規(guī)則：

( NP-B ( NR (中國(guó))NN(打擊) NN (走私) NN (工作) NN (會(huì)議) )

( NP-B ( NR (中國(guó))VV(打擊) NN (走私) NN (工作) NN (會(huì)議) )

由于句法分析的錯(cuò)誤，第二條規(guī)則中“打擊”的詞性被標(biāo)注成了“VV”，按照字符串匹配算法，這兩條規(guī)則是無(wú)法匹配的。從上面這個(gè)例子可以看出，使用完全的字符串匹配技術(shù)將潛在地減小可匹配的規(guī)則數(shù)量，特別對(duì)于一些節(jié)點(diǎn)數(shù)目比較大的規(guī)則來(lái)說(shuō)，能夠成功匹配的規(guī)則數(shù)量將非常稀少。

因此本文提出了一種基于樹(shù)核的模糊匹配技術(shù)，我們將一條規(guī)則表示成一個(gè)特征向量，通過(guò)卷積樹(shù)核[15]來(lái)計(jì)算不同規(guī)則之間的相似度。由于規(guī)則表中規(guī)則數(shù)量巨大，完全計(jì)算所有規(guī)則之間的相似度是不可行的，因此我們首先通過(guò)一些限制生成一個(gè)候選規(guī)則集合，然后在集合內(nèi)部通過(guò)卷積樹(shù)核計(jì)算相似度。在NIST 2005漢英翻譯的實(shí)驗(yàn)表明，使用模糊匹配技術(shù)顯著的提高了1.3個(gè)BLEU值，并且在森林模型中使用模糊匹配技術(shù)仍然取得了0.7個(gè)BLEU值的提升。

本文將在第2節(jié)簡(jiǎn)要介紹樹(shù)到串翻譯模型，然后在第3節(jié)介紹卷積樹(shù)核以及本文提出的模糊匹配技術(shù)，在第4節(jié)本文將給出所有的實(shí)驗(yàn)結(jié)果，最后在第5節(jié)將對(duì)本文進(jìn)行總結(jié)。

2 樹(shù)到串翻譯模型

樹(shù)到串翻譯模型[7-8]將翻譯過(guò)程分成兩個(gè)步驟：句法分析和翻譯。假定源語(yǔ)言是中文，目標(biāo)語(yǔ)言是英文，圖1給出了一個(gè)樹(shù)到串翻譯模型中常見(jiàn)的例子，其中包括源句法分析樹(shù)，目標(biāo)串以及源端和目標(biāo)端文本串之間的對(duì)齊信息。

圖1 樹(shù)到串翻譯模型中的常見(jiàn)例子，其中包括源句法分析樹(shù)，目標(biāo)串以及源端和目標(biāo)端之間的對(duì)齊信息

使用GHKM算法[16]，我們可以從圖1中的對(duì)齊結(jié)構(gòu)中抽取出樹(shù)到串翻譯規(guī)則。表1給出了圖1例子中抽取出的規(guī)則樣例。其中規(guī)則的左半部分表示的是一棵樹(shù)片段(x表示非終結(jié)符)；右半部分是對(duì)應(yīng)的翻譯信息。由于樹(shù)到串規(guī)則包含了豐富的層次信息，因此其表達(dá)能力也強(qiáng)于同步上下文文法。

表1 規(guī)則表

在以往相關(guān)的工作中，表1中的規(guī)則(4)和規(guī)則(7)是兩條完全不同的規(guī)則，因?yàn)樗麄兊淖蟀氩糠植荒芡耆ヅ洹５俏覀兛梢园l(fā)現(xiàn)他們表達(dá)的翻譯信息是相同的，都是將源端的詞匯化節(jié)點(diǎn)“shalong” 翻譯成目標(biāo)端的“Sharon”。因此我們提出了一種模糊匹配技術(shù)，我們只考察規(guī)則中的邊緣節(jié)點(diǎn)(規(guī)則中的葉子節(jié)點(diǎn))相同的規(guī)則，然后使用樹(shù)核計(jì)算規(guī)則之間的相似度并作為一個(gè)判別特征加入到判別模型中去。在下面一節(jié)中我們將詳細(xì)介紹基于樹(shù)核的模糊匹配技術(shù)。

3 模糊匹配

在我們的系統(tǒng)中，一條規(guī)則不再表示成字符串，而是將其視為一個(gè)結(jié)構(gòu)體，然后計(jì)算不同規(guī)則之間的相似度。為了計(jì)算相似度我們引入了卷積樹(shù)核技術(shù)。本節(jié)我們首先簡(jiǎn)要介紹卷積樹(shù)核的基本概念，然后介紹如何將卷積樹(shù)核技術(shù)引入到模糊匹配模型中。

3.1 卷積樹(shù)核

不同于樹(shù)結(jié)構(gòu)的字符串表示形式，卷積樹(shù)核[15]通過(guò)特征向量來(lái)表示不同的句法樹(shù)。一般來(lái)說(shuō)，一棵句法樹(shù)t可以使用特征向量f來(lái)表示，f具有如下形式：f(t)=(…,sti(t),…)，其中sti(t)表示的是句法樹(shù)t中第ith棵子樹(shù)出現(xiàn)的次數(shù)。由于一棵句法樹(shù)中的子樹(shù)個(gè)數(shù)有可能非常多，直接枚舉是不可能的，因此Collins and Duffy 提出了使用卷積樹(shù)核來(lái)高效計(jì)算高維向量點(diǎn)積的方法[15]：

其中N1和N2分別是句法樹(shù)t1和t2的節(jié)點(diǎn)集合，Ii(n)表示句法樹(shù)的子樹(shù)是否以n作為根節(jié)點(diǎn)，是則為1，反之為0；C(n1,n2)表示兩棵句法樹(shù)中分別以n1和n2作為根節(jié)點(diǎn)的子樹(shù)個(gè)數(shù)。并且C(n1,n2)可以通過(guò)下面的定義在多項(xiàng)式時(shí)間內(nèi)計(jì)算出來(lái)：

1) 如果節(jié)點(diǎn)n1和n2的推導(dǎo)不同，則C(n1,n2)=0；

2) 如果節(jié)點(diǎn)n1和n2為葉子節(jié)點(diǎn)并且具有相同的標(biāo)簽，則C(n1,n2)=λ；

3) 如果節(jié)點(diǎn)n1和n2的推導(dǎo)相同并且n1和n2不是葉子節(jié)點(diǎn)，則

其中nc(n1)表示節(jié)點(diǎn)n1包含的推導(dǎo)中子節(jié)點(diǎn)個(gè)數(shù)，由于節(jié)點(diǎn)n1和n2的推導(dǎo)相同，所以nc(n1)=nc(n2)，此外ch(n1,j)表示n1包含的推導(dǎo)中第j個(gè)子節(jié)點(diǎn)。λ(0≤λ≤1)是一個(gè)懲罰因子，用來(lái)降低子樹(shù)規(guī)模對(duì)C(n1,n2)大小的影響。

3.2 規(guī)則匹配

在以往的方法中，規(guī)則必須通過(guò)精確匹配來(lái)選取，以圖2為例，假定圖中表示的是輸入句法樹(shù)中的兩棵不同子樹(shù)片段。通過(guò)規(guī)則匹配，我們發(fā)現(xiàn)表1中的規(guī)則(5)可以用來(lái)生成子樹(shù)a的翻譯，而子樹(shù)b無(wú)法從表1的規(guī)則表中找到合適的翻譯，因?yàn)楸?包含的所有規(guī)則表中沒(méi)有任何一條規(guī)則的左半部分包含子樹(shù)片段 “VPB(VV(juxing) AS(le) x1:NP)”。

圖2 樹(shù)到串翻譯模型中輸入句法樹(shù)中的兩棵子樹(shù)片段及其在模糊匹配模型中的表示形式

但是通過(guò)分析我們發(fā)現(xiàn)，子樹(shù)a和子樹(shù)b的翻譯僅由葉子節(jié)點(diǎn)“juxing”，“l(fā)e”，“NPB”和“NP”的翻譯譯文組成，而與中間節(jié)點(diǎn)“VV”和“AS”無(wú)關(guān)?；谶@個(gè)直覺(jué)，我們忽略子樹(shù)的中間結(jié)構(gòu)，僅考察子樹(shù)的葉子節(jié)點(diǎn)是否相似，并且對(duì)于非終結(jié)符節(jié)點(diǎn)進(jìn)行泛化處理。例如圖2中子樹(shù)a和子樹(shù)b的“NBP”和“NP”節(jié)點(diǎn)都泛化為名詞詞性“NNx”。同樣地，對(duì)于規(guī)則表中的規(guī)則，我們匹配時(shí)也僅考慮規(guī)則中的葉子節(jié)點(diǎn)，以表1中的規(guī)則(5)為例，其對(duì)應(yīng)的葉子節(jié)點(diǎn)為“juxing”，“l(fā)e”和“NP”，由于“NP”為非終結(jié)符名詞節(jié)點(diǎn)，我們將其泛化為“NNx”。因此規(guī)則(5)在模糊匹配的定義下適用于圖2中的兩棵子樹(shù)。

然而對(duì)于規(guī)則表中的規(guī)則來(lái)說(shuō)，我們只考察葉子節(jié)點(diǎn)是否相似，而忽略中間節(jié)點(diǎn)的不同。但是對(duì)于一條和源端子樹(shù)完全匹配的規(guī)則來(lái)說(shuō)，規(guī)則的可信度要高于不完全匹配的規(guī)則。因此對(duì)于不同的匹配規(guī)則，我們使用上一小節(jié)介紹的卷積樹(shù)核來(lái)計(jì)算輸入子樹(shù)片段和規(guī)則表中規(guī)則之間的相似度，并在解碼時(shí)將相似度作為一個(gè)特征引入到對(duì)數(shù)線性模型中去，通過(guò)最小錯(cuò)誤率訓(xùn)練來(lái)訓(xùn)練出合適的權(quán)重。在實(shí)驗(yàn)中我們也發(fā)現(xiàn)模糊匹配的權(quán)重為正值，也就意味著越相似的規(guī)則對(duì)BLEU值貢獻(xiàn)越大。

此外由于計(jì)算樹(shù)核相似度需要耗費(fèi)一定的計(jì)算時(shí)間，而對(duì)于解碼器來(lái)說(shuō)性能是很重要的。因此為了提高解碼時(shí)的運(yùn)行速度，我們將規(guī)則表中葉子節(jié)點(diǎn)相同的規(guī)則形成一個(gè)小集合，并且利用樹(shù)核公式預(yù)先計(jì)算出集合內(nèi)規(guī)則之間的相似度，這樣在解碼時(shí)就可以快速獲取子樹(shù)和匹配規(guī)則之間的相似度，省去了在線計(jì)算樹(shù)核的時(shí)間。

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

4.1 實(shí)驗(yàn)設(shè)置

我們選用FBIS語(yǔ)料(共239 416平行句對(duì))作為訓(xùn)練集，利用SRI語(yǔ)言模型工具包[17]，并且使用Kneser-Ney 平滑[18]技術(shù)在GigaXinHua上面訓(xùn)練了一個(gè)四元語(yǔ)言模型。

對(duì)于源端的漢語(yǔ)句子，我們使用中文句法分析器[19]生成了對(duì)應(yīng)的中文句法樹(shù)。此外我們選用NIST2002 漢英測(cè)試集作為實(shí)驗(yàn)的開(kāi)發(fā)集，NIST2005漢英測(cè)試集作為測(cè)試集，使用大小寫不敏感的BLEU4作為實(shí)驗(yàn)衡量標(biāo)準(zhǔn)。

4.2 實(shí)驗(yàn)結(jié)果

由于使用了模糊匹配，對(duì)于源端的句法樹(shù)來(lái)說(shuō)，可候選的規(guī)則數(shù)量相比于精確匹配增加12%左右，表2列出了精確匹配和模糊匹配對(duì)應(yīng)的候選規(guī)則數(shù)量。

表2 精確匹配和模糊匹配模型過(guò)濾后規(guī)則表大小

我們?cè)陂_(kāi)發(fā)集中對(duì)3.1節(jié)中相似度公式中的懲罰因子λ進(jìn)行插值計(jì)算，圖3給出了開(kāi)發(fā)集BLEU值受λ值的影響，從圖中可以看出當(dāng)λ=0.8時(shí)我們?nèi)〉昧俗顑?yōu)的BLEU值，但是可以看出樹(shù)核函數(shù)的計(jì)算方法對(duì)最后的性能影響并不是很大，主要原因是在對(duì)數(shù)線性模型中，規(guī)則的選取取決于多個(gè)特征的判別作用。相對(duì)于翻譯概率以及詞匯化概率來(lái)說(shuō)，相似度特征的作用并不是很大。但是從表3、表4中我們發(fā)現(xiàn)僅考慮葉子節(jié)點(diǎn)的匹配策略對(duì)于BLEU的提升很有效。

圖3 不同的λ值對(duì)開(kāi)發(fā)集BLEU值的影響

表3樹(shù)模型和森林模型在測(cè)試集上的對(duì)比實(shí)驗(yàn)結(jié)果

測(cè)試集05 (BLEU)樹(shù)模型精確匹配(Baseline)28.76樹(shù)模型模糊匹配 30.06++(p<0.01)森林模型精確匹配(Baseline)30.7森林模型模糊匹配 31.4++(p<0.05)

最后我們測(cè)試了模糊匹配在測(cè)試集上面的效果，表3給出了對(duì)比實(shí)驗(yàn)結(jié)果。從表3中我們可以發(fā)現(xiàn)模糊匹配相對(duì)于精確匹配取得了1.3個(gè)BLEU值的顯著提升。提升的很大原因在于樹(shù)到串翻譯模型的源端是句法樹(shù)，而在目前句法分析準(zhǔn)確率不高的情況下，傳統(tǒng)的精確匹配方法無(wú)法減輕句法分析錯(cuò)誤對(duì)規(guī)則無(wú)法匹配造成的影響。

此外，我們?cè)诨谏值臉?shù)到串模型[13]中引入了模糊匹配技術(shù)，從表3中可以看出基于模糊匹配的技術(shù)仍然取得了0.7個(gè)BLEU值的提升。從表3對(duì)比結(jié)果中我們可以發(fā)現(xiàn)使用模糊匹配技術(shù)能夠顯著的提高機(jī)器翻譯的性能。

5 結(jié)論與未來(lái)工作

本文提出了一種基于樹(shù)核的規(guī)則模糊匹配技術(shù)，在NIST05的測(cè)試集合上的實(shí)驗(yàn)結(jié)果表明：相比于傳統(tǒng)的精確匹配方法，使用模糊匹配技術(shù)顯著的提高了1.3個(gè)BLEU值；此外，在基于森林的翻譯模型上使用模糊匹配技術(shù)，我們?nèi)匀蝗〉昧?.7個(gè)BLEU值的提升。

在未來(lái)的工作中我們將繼續(xù)測(cè)試模糊匹配技術(shù)在樹(shù)到樹(shù)翻譯模型中的效果，相比于樹(shù)到串模型，樹(shù)到樹(shù)模型目前的翻譯效果仍然有很大潛力需要挖掘，因此我們希望通過(guò)使用模糊匹配技術(shù)來(lái)增加可用規(guī)則表大小，進(jìn)而提高翻譯的質(zhì)量。

[1] David Chiang.A hierarchical phrase-based model for statistical machine translation[C]//Association for Computational Linguistics.Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics.Michigan State, USA:ACL Publication Chairs,2005:263-270.

[2] Dekai Wu.Stochastic inversion transduction grammars and bilingual parsing of parallel corpora[J].Computational Linguistics,1997,23:377-403.

[3] Michel Galley, Jonathan Graehl, Kevin Knight, Daniel Marcu, Steve DeNeefe, Wei Wang, Ignacio Thayer.Scalable inference and training of context-rich syntactic translation models[C]//Association for Computational Linguistics.Proceedings of the 44rd Annual Meeting on Association for Computational Linguistics.Sydney, Australia:ACL Publication Chairs,2006:961-968.

[4] Daniel Marcu, Wei Wang, Abdessamad Echihabi, Kevin Knight.SPMT: Statistical machine translation with syntactified target language phrases[C]//Association for Computational Linguistics.Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing.Sydney, Australia:ACL Publication Chairs,2006:44-52.

[5] Dekang Lin.A path-based transfer model for machine translation[C]//Association for Computational Linguistics.Proceedings of the 20th international conference on Computational Linguistics.Geneva, Switzerland:ACL Publication Chairs,2004:625-633.

[6] Yuan Ding and Martha Palmer.Machine translation using probabilistic synchronous dependency insertion grammars[C]//Association for Computational Linguistics.Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics.Michigan State, USA:ACL Publication Chairs,2005:541-548.

[7] Yang Liu, Qun Liu, and Shouxun Lin.Tree-to-string alignment template for statistical machine translation[C]//Association for Computational Linguistics.Proceedings of the 44th Annual Meeting on Association for Computational Linguistics.Sydney, Australia:ACL Publication Chairs,2006:609-617.

[8] Liang Huang, Kevin Knight, Aravind Joshi.A syntax-directed translator with extended domain of locality[C]//Association for Computational Linguistics.Proceedings of the Workshop on Computationally Hard Problems and Joint Inference in Speech and Language Processing.New York, USA:ACL Publication Chairs,2005:1-8.

[9] Jason Eisne.Learning non-isomorphic tree mappings for machine translation[C]//Association for Computational Linguistics.Proceedings of the 41st Annual Meeting on Association for Computational Linguistics.Sapporo, Japan:ACL Publication Chairs,2003:205-208.

[10] Brooke Cowan.A discriminative model for tree-to-tree translation[C]//Association for Computational Linguistics.Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing.Sydney, Australia:ACL Publication Chairs,2006:232-241.

[11] Min Zhang, Hongfei Jiang, Aiti Aw, Haizhou Li, Chew Lim Tan, Sheng Li. A tree sequence alignment-based tree-to-tree translation model[C]//Association for Computational Linguistics.Proceedings of the 46th Annual Meeting on Association for Computational Linguistics.Oho, USA:ACL Publication Chairs,2008:559-567.

[12] Quirk and Corston-Oliver.The impact of parse quality on syntactically-informed statistical machine translation[C]//Association for Computational Linguistics.Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing.Sydney, Australia:ACL Publication Chairs,2006:62-69.

[13] Haitao Mi, Liang Huang, and Qun Liu.Forest-based translation[C]//Association for Computational Linguistics.Proceedings of the 46th Annual Meeting on Association for Computational Linguistics.Oho, USA:ACL Publication Chairs,2008:192-199.

[14] Yang Liu, Yajuan Lv, and Qun Liu[C]//Association for Computational Linguistics.Proceedings of the 47th Annual Meeting on Association for Computational Linguistics.Suntec, Singapore:ACL Publication Chairs,2009:558-566.

[15] Michael Collins and Nigel Duffy.Convolution kernels for natural language[C]//Advances in neural information processing systems.Fifteen Annual Conference on Neural Information Processing Systems.British Columbia, Canada:NIPS Publication Chairs,2001:625-632.

[16] Michel Galley, Mark Hopkins, Kevin Knight, Daniel Marcu.What is in a translation rule?[C]//Association for Computational Linguistics.Proceedings of the 2nd Human Language Technologies and North American Association for Computational Linguistics annual meetings.USA:ACL Publication Chairs,2004:273-280.

[17] Andreas Stolcke. Srilm—an extensible language modeling toolkit[C]//ICSLP.Proceedings of the Seventh International Conference on Spoken Language Processing.Denver, Colorado, USA:ICSLP Publication Chairs,2002:901-904.

[18] Stanley Chen and Joshua Goodman.An empirical study of smoothing techniques for language modeling[C]//Association for Computational Linguistics.Proceedings of the 34th Annual Meeting on Association for Computational Linguistics.California, USA:ACL Publication Chairs,1996:310-318.

[19] Deyi Xiong, Shuanglong Li, Qun Liu, Shouxun Lin, Yueliang Qian.Parsing the penn Chinese treebank with semantic knowledge[C]//Association for Computational Linguistics.Proceedings of the Natural Language Processing-IJCNLP 2005.USA:Springer,2005:70-81.