模糊匹配在樹到串翻譯模型中的應(yīng)用

熊 皓,劉 洋,劉 群

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

1 導(dǎo)論

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

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

為了減輕句法分析錯(cuò)誤對(duì)翻譯性能的影響，一種可行的方法是在源端使用句法分析森林來替代單棵最優(yōu)句法樹[13-14]。上述文獻(xiàn)也表明使用森林技術(shù)可以在很大程度上提高翻譯的質(zhì)量。但是不管是使用單棵句法分析樹還是使用森林，以往的工作都是將規(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ī)則是無法匹配的。從上面這個(gè)例子可以看出，使用完全的字符串匹配技術(shù)將潛在地減小可匹配的規(guī)則數(shù)量，特別對(duì)于一些節(jié)點(diǎn)數(shù)目比較大的規(guī)則來說，能夠成功匹配的規(guī)則數(shù)量將非常稀少。

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

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

2 樹到串翻譯模型

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

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

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

表1 規(guī)則表

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

3 模糊匹配

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

3.1 卷積樹核

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

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

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è)懲罰因子，用來降低子樹規(guī)模對(duì)C(n1,n2)大小的影響。

3.2 規(guī)則匹配

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

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

但是通過分析我們發(fā)現(xiàn)，子樹a和子樹b的翻譯僅由葉子節(jié)點(diǎn)“juxing”，“l(fā)e”，“NPB”和“NP”的翻譯譯文組成，而與中間節(jié)點(diǎn)“VV”和“AS”無關(guān)?；谶@個(gè)直覺，我們忽略子樹的中間結(jié)構(gòu)，僅考察子樹的葉子節(jié)點(diǎn)是否相似，并且對(duì)于非終結(jié)符節(jié)點(diǎn)進(jìn)行泛化處理。例如圖2中子樹a和子樹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中的兩棵子樹。

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

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

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

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

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

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

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

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

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

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

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

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

測(cè)試集05 (BLEU)樹模型精確匹配(Baseline)28.76樹模型模糊匹配 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值的顯著提升。提升的很大原因在于樹到串翻譯模型的源端是句法樹，而在目前句法分析準(zhǔn)確率不高的情況下，傳統(tǒng)的精確匹配方法無法減輕句法分析錯(cuò)誤對(duì)規(guī)則無法匹配造成的影響。

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

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

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

在未來的工作中我們將繼續(xù)測(cè)試模糊匹配技術(shù)在樹到樹翻譯模型中的效果，相比于樹到串模型，樹到樹模型目前的翻譯效果仍然有很大潛力需要挖掘，因此我們希望通過使用模糊匹配技術(shù)來增加可用規(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.