張亞軍

(昌吉學(xué)院計(jì)算機(jī)工程系 新疆 昌吉 831100)

1 引言

隨著現(xiàn)代計(jì)算機(jī)科學(xué)技術(shù)的快速發(fā)展，人類渴望利用機(jī)器翻譯而達(dá)到突破語言障礙的愿望已經(jīng)初步實(shí)現(xiàn)了。在機(jī)器翻譯的發(fā)展過程中，由于語料庫的研究的興起，尤其是對(duì)雙語語料庫(或稱平行語料庫)的研究，使得基于短語的統(tǒng)計(jì)機(jī)器翻譯(statistical machine translation以下簡稱SMT)[1][2][3]得到越來越多專家的重視和研究。SMT以平行語料庫(parallel corpora)為主要知識(shí)源，基于統(tǒng)計(jì)的方法來實(shí)現(xiàn)機(jī)器翻譯過程。當(dāng)輸入待翻譯的句子S后，主要處理順序如下：對(duì)S分詞，切分短語，短語對(duì)齊(即在平行語料庫搜索相應(yīng)語料)，進(jìn)行比較、適當(dāng)取舍、調(diào)整排序，選取與S最接近的目標(biāo)句子T。

快速準(zhǔn)確地構(gòu)建基于短語統(tǒng)計(jì)的漢語—維吾爾語機(jī)器翻譯系統(tǒng)是目前領(lǐng)域內(nèi)研究的主要方向，其中漢維解碼器的研究工作已經(jīng)成為構(gòu)建機(jī)器翻譯系統(tǒng)解決的首要問題。統(tǒng)計(jì)機(jī)器翻譯最初采用的是基于詞的逐詞翻譯方法[4]，該方法對(duì)多個(gè)詞語之間上下文關(guān)系反映較差。后來研究基于短語的方法，該方法將源句子切分為多個(gè)短語并進(jìn)行短語間的相互翻譯。本文主要研究漢維解碼器的算法設(shè)計(jì)。

2 特征選取

信源信道模型是統(tǒng)計(jì)機(jī)器翻譯研究中最初采用的主要模型之一，它是一種生成模型。語言模型和翻譯模型的好壞對(duì)模型翻譯質(zhì)量的高低具有決定性的作用。經(jīng)過不斷地改進(jìn)發(fā)展，逐漸演變?yōu)閷?duì)數(shù)線性模型。對(duì)數(shù)線性模型與信源信道模型不同之處在于：對(duì)數(shù)線性模型屬于判別模型，它比信道信源模型更具有一般性，信源信道模型可以作為對(duì)數(shù)線性模型的一個(gè)特例。在對(duì)數(shù)線性模型方法中，特征模型可以方便的加載到模型中來。

假設(shè)u、c是機(jī)器翻譯的目標(biāo)語言和源語言句子，h1(u,c), …, hM(u,c)分別是u和c上的M個(gè)特征，λ1, …,λM是與這些特征分別對(duì)應(yīng)的M個(gè)參數(shù)(特征權(quán)重因子)，那么直接翻譯概率可以用以下公式模擬：

P(u|c)≈Pλ1…λm(u|c)

其中假設(shè)Z(c)是一個(gè)標(biāo)準(zhǔn)常量， 此時(shí)翻譯過程轉(zhuǎn)換如下：

翻譯譯文由解碼算法通過搜索具有各個(gè)特征模型的最大加權(quán)評(píng)分值的目標(biāo)語言句子而最終得出。性能較高的解碼算法將得到翻譯速度和質(zhì)量都比較高的目標(biāo)語言句子。

2.1 維吾爾語模型

目標(biāo)語言模型主要用來評(píng)價(jià)翻譯譯文的質(zhì)量。本文加入張亞軍等人研究的基于N-gram的維吾爾n-gram語言模型(N=3)[5]，則

2.2 扭曲模型

在對(duì)源語言句子進(jìn)行短語翻譯時(shí)，涉及到短語翻譯的位置重排問題，在此選用扭曲模型考慮短語重排的代價(jià)(即扭曲度，用d表示)。

di表示翻譯過程中源語言句子短語的位置扭曲幅度。di 的大小為翻譯時(shí)第i個(gè)源短語的第一詞語的位置與i-1個(gè)源短語最后一個(gè)詞語位置的差值加1。

2.3 詞語補(bǔ)償(懲罰)模型

詞語懲罰模型主要是為了防止目標(biāo)語言T的句子過長(短語數(shù)I限制在10≤I≤20)，而對(duì)短的目標(biāo)語言T所進(jìn)行的補(bǔ)償。詞語懲罰模型可表示如下：

Pr(u)=exp(I) I代表目標(biāo)語言的句子長度。

3 解碼器算法的設(shè)計(jì)

在該漢維解碼器的解碼設(shè)計(jì)過程中，采用柱式搜索算法進(jìn)行搜索，柱式搜索算法屬于動(dòng)態(tài)規(guī)劃的一種算法。該算法主要策略是在有限的全局空間內(nèi)有效進(jìn)行搜索，使得解碼速度在精度上都取得一個(gè)折中方案。

3.1 核心算法

柱搜索(Beam Search)算法思想：在一個(gè)搜索過程中盡可能的擴(kuò)展出所有的翻譯選項(xiàng)，直到翻譯完成為止。柱搜索的思想實(shí)質(zhì)上是動(dòng)態(tài)規(guī)劃思想的一種應(yīng)用。這種翻譯狀態(tài)稱作假設(shè)，每一個(gè)翻譯結(jié)果即代表一種假設(shè)。表1中列出假設(shè)包含的主要信息說明。

表1 翻譯假設(shè)包含的主要信息說明

將需要翻譯的漢語短語序列設(shè)置到相應(yīng)的棧中，生成新的假設(shè)。翻譯相同漢語短語個(gè)數(shù)存放到相應(yīng)的假設(shè)站中。隨后對(duì)假設(shè)棧依次擴(kuò)展，到漢語短語翻譯完成位置結(jié)束。對(duì)漢語句子中短語數(shù)為K的解碼算法描述如下：

(1)對(duì)漢語句子S進(jìn)行分析；

(2)翻譯備選項(xiàng)列表的構(gòu)建；

(3)未來評(píng)分表；

(4)初始化假設(shè)棧HpStack；

(5)生成初始假設(shè)加入到假設(shè)棧HpStack [0]中；

(6)遍歷搜索假設(shè)棧HpStack[i](0≤i≤k-1，以下i相同)，遍歷假設(shè)棧中所有的Hp；

(7)在Hp中搜索(2)中構(gòu)建的表，擴(kuò)展一次即可生成一個(gè)NewHp；

(8)計(jì)算Prob值，newHp翻譯的漢語短語依次加入到棧HpStack中；

(9)從HpStack[K]中的分值最高的假設(shè)作為出發(fā)點(diǎn)，依次回退，直至結(jié)束，即可得到一條路徑，路徑上的所有點(diǎn)組合得到一個(gè)譯文。

在(1)中首先從譯模型搜索出漢語句子的所有可能的翻譯短語對(duì)，目的是為了避免在進(jìn)行假設(shè)擴(kuò)展的后的重復(fù)搜索。

(8)中計(jì)算假設(shè)的Prob值，要計(jì)算假設(shè)當(dāng)前的各個(gè)加權(quán)值，另外還需要加上通過搜索(3)生成的未來評(píng)分表估計(jì)的假設(shè)未來評(píng)分[6]，這樣總概率就能很方便的反映出假設(shè)的質(zhì)量如何。

3.2 構(gòu)建翻譯備選項(xiàng)列表

擴(kuò)展次數(shù)是由翻譯備選項(xiàng)列表的數(shù)目決定的(數(shù)目越多，次數(shù)越多)。因此減少假設(shè)擴(kuò)展的次數(shù)提高翻譯速度可以對(duì)翻譯備選列表進(jìn)行裁減。對(duì)翻譯備選項(xiàng)列表的大小進(jìn)行限制以及通過對(duì)翻譯選項(xiàng)評(píng)分閥值的設(shè)定，即可達(dá)到對(duì)評(píng)分值較差的翻譯備選項(xiàng)進(jìn)行裁減的目的。

記錄短語互譯信息表是通過翻譯備選項(xiàng)列表實(shí)現(xiàn)的，此表主要包括維吾爾/漢語短語、翻譯評(píng)分值、維吾爾短語的N-gram模型評(píng)分值信息。備選項(xiàng)表的構(gòu)建，不只需要收集到翻譯模型中維吾爾語/漢語言句子或者短語之間對(duì)應(yīng)的互譯信息，而且要計(jì)算它們的模型評(píng)分值。

另外，在解碼的過程中對(duì)棧中狀態(tài)進(jìn)行剪枝，搜索過程中棧中狀態(tài)的個(gè)數(shù)是固定的(見表2)，選擇評(píng)分較好的狀態(tài)進(jìn)行下一步擴(kuò)展，評(píng)分效果不理想的節(jié)點(diǎn)，作為評(píng)分效果較好節(jié)點(diǎn)的一個(gè)分支，并入該節(jié)點(diǎn)下。這種方法通常稱為剪枝策略，優(yōu)點(diǎn)就是可以降低節(jié)點(diǎn)數(shù)，同時(shí)有沒有刪除評(píng)分效果的不理想的節(jié)點(diǎn)，盡可能的保留原始信息。

4 試驗(yàn)結(jié)果

實(shí)驗(yàn)使用新疆大學(xué)多語種實(shí)驗(yàn)室提供的20000句對(duì)的漢維雙語語料庫為基礎(chǔ)。以維吾爾語為目標(biāo)語言訓(xùn)練3-gram的維吾爾語語言模型和漢維短語翻譯模型。選用200句長度為10到20個(gè)詞語的漢語句子作為測試輸入數(shù)據(jù)的對(duì)比實(shí)驗(yàn)。

表2 試驗(yàn)結(jié)果對(duì)比

由表2可以看出，在固定棧設(shè)定為200時(shí)，解碼處理速度比較慢且錯(cuò)誤率比較大。固定棧設(shè)置的越大，則解碼處理速度加快，并且解碼算法的錯(cuò)誤率也在隨之下降。但并不是固定棧設(shè)置越多越好，隨著棧的繼續(xù)增加，搜索算法將會(huì)占用大量的時(shí)間，處理整體效果沒有明顯加強(qiáng)，并且對(duì)計(jì)算機(jī)的硬件性能要求較高。

5 總結(jié)

漢維解碼器的研究是漢維機(jī)器翻譯研究的關(guān)鍵。在漢維翻譯解碼過程將遇到龐大的搜索空間，評(píng)價(jià)漢維解碼器的重要指標(biāo)之一就是如何快速解碼。本文講述搜索解碼算法設(shè)計(jì)與實(shí)現(xiàn)了漢維解碼算法的實(shí)驗(yàn)。下一步主要研究漢維解碼算法的全局優(yōu)化問題，使得算法在效率上得以提升。

參考文獻(xiàn):

[1]OCH F J，NEY H．Discriminative training and maximum entropy models for statistical machine translation[C].Proceedings of the40th Annual Meeting of the Association for Computational Lingu istics(ACL).Philadelphia,PA:[s.n],2002:295—302．

[2]http://www.iccs.inf.ed.ac.uk/～pkoehn/publications/phrase2003.pdf．

[3] Wang Ye-yi，Warble．Decoding algorithm in statistical machine translation [C].Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics，Madrid，Spain，1997.

[4] 聶進(jìn). 一個(gè)基于JAVA的堆棧式自然語言翻譯解碼器[J]. 計(jì)算機(jī)工程與應(yīng)用,2005，(4):105-108.

[5] 張亞軍，吐爾根·依布拉音.漢語—維吾爾語句子級(jí)對(duì)齊系統(tǒng)分析及其實(shí)現(xiàn)[J].中國科技縱橫,2010，(6).

[6] KOEHN P．Pharaoh：A beam search decoder for phrase—based statistical machine translation models[C].Proceedings of the Association of Machine Translation in the Americas(AMTA-2004).