漢語(yǔ)詞與句子切分技術(shù)及機(jī)器翻譯評(píng)估方法探討(doc 94頁(yè)).doc

1、 分類(lèi)號(hào) 密級(jí) UDC 編號(hào) 中國(guó)科學(xué)院研究生院碩士學(xué)位論文 漢語(yǔ)詞與句子切分技術(shù)及機(jī)器翻譯評(píng)估方法研究 劉丁 指導(dǎo)教師 宗成慶 研究員 博士 中國(guó)科學(xué)院自動(dòng)化研究所 申請(qǐng)學(xué)位級(jí)別 工學(xué)碩士 學(xué)科專(zhuān)業(yè)名稱(chēng) 模式識(shí)別與智能系統(tǒng) 論文提交日期 2004年6月 論文答辯日期 2004年6月 培養(yǎng)單位 中國(guó)科學(xué)院自動(dòng)化研究所 學(xué)位授予單位 中國(guó)科學(xué)院研究生院 答辯委員會(huì)主席 Approaches to Chinese Word Analysis, Utterance Segmentation and Automatic Evaluation of Machine TranslationDisserta

2、tion Submitted toInstitute of Automation, Chinese Academy of Sciencesin partial fulfillment of the requirementsfor the degree ofMaster of EngineeringbyDing Liu(Pattern Recognition and Intelligence System)Dissertation Supervisor: Professor Chengqing Zong獨(dú)創(chuàng)性聲明本人聲明所成交的論文是我個(gè)人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。盡我所知，除

3、了文中特別加以標(biāo)注和致謝的地方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫(xiě)過(guò)的研究成果。與我一同工作的同志對(duì)本研究所做的任何貢獻(xiàn)均已在論文中作了明確地說(shuō)明并表示了謝意。簽名：_導(dǎo)師簽名：_ 日 期：_關(guān)于論文使用授權(quán)的說(shuō)明本人完全了解中國(guó)科學(xué)院自動(dòng)化研究所有關(guān)保留、使用學(xué)位論文的規(guī)定，即：中國(guó)科學(xué)院自動(dòng)化研究所有權(quán)保留送交論文的復(fù)印件，允許論文被查閱和借閱；可以公布論文的全部或部分內(nèi)容，可以采用影印、縮印或其他復(fù)制手段保存論文。（保密的論文在解密后應(yīng)遵守此規(guī)定）簽名：_導(dǎo)師簽名：_ 日 期：_摘要本論文以統(tǒng)計(jì)模型為基礎(chǔ)，在參考了大量前人工作的基礎(chǔ)上，對(duì)漢語(yǔ)詞法分析、口語(yǔ)句子切分和機(jī)器翻譯評(píng)估進(jìn)行了較為

4、深入的探討和研究。漢語(yǔ)詞法分析是大部分中文處理的第一步，其重要性不言而喻；句子切分是語(yǔ)音翻譯中連接語(yǔ)音識(shí)別和文本翻譯的橋梁，無(wú)論語(yǔ)音識(shí)別和文本翻譯單獨(dú)的效果有多么好，這座橋沒(méi)搭好，綜合的性能依然無(wú)法提高；機(jī)器翻譯的自動(dòng)評(píng)估是構(gòu)建機(jī)器翻譯系統(tǒng)中很重要的輔助工作，其可以加速翻譯系統(tǒng)的開(kāi)發(fā)速度，縮短其開(kāi)發(fā)周期。簡(jiǎn)言之，這三方面同屬于自然語(yǔ)言處理的基礎(chǔ)的研究領(lǐng)域，其效果直接影響到高層應(yīng)用的水平。在詞法分析上，我們利用隱馬爾可夫模型（HMM）提出了一種融和了分詞、詞性標(biāo)注和命名實(shí)體識(shí)別的一體化詞法分析方法。最初我們用基于類(lèi)別的HMM，其優(yōu)點(diǎn)是對(duì)詞的覆蓋面廣，系統(tǒng)開(kāi)銷(xiāo)小；缺點(diǎn)是不能精確地預(yù)測(cè)詞的出現(xiàn)概率。

5、為了提升模型的準(zhǔn)確率，我們引入基于詞匯的HMM，并將兩者有機(jī)地結(jié)合，并用一個(gè)“詞到字”的概率平滑方法對(duì)基于詞的HMM進(jìn)行平滑。實(shí)驗(yàn)結(jié)果顯示，我們的混合模型由于綜合考慮到了字、詞、詞性以及命名實(shí)體的知識(shí)，在切分的準(zhǔn)確率和召回率上都明顯優(yōu)于單純基于類(lèi)別或者基于詞的HMM。此外在分詞系統(tǒng)的實(shí)現(xiàn)上，我們借助對(duì)通用分詞系統(tǒng)APCWS的整體框架和各功能模塊的介紹，討論了如何有效地存儲(chǔ)和加載數(shù)據(jù)等一些技術(shù)細(xì)節(jié)問(wèn)題。在口語(yǔ)句子切分上，我們提出了基于雙向N元模型和最大熵模型的句子切分算法，這種算法由于通過(guò)最大熵有機(jī)地將正、逆向N元切分結(jié)合起來(lái)，綜合考慮到了切分點(diǎn)左、右的上下文，從而得到了很好的切分效果。我們?cè)谥?/p>

6、、英文語(yǔ)料上訓(xùn)練我們的模型并作測(cè)試，結(jié)果顯示其在性能上明顯優(yōu)于基本的正向N元切分。在此基礎(chǔ)上，我們分析并對(duì)比了各模型的切分結(jié)果，從而驗(yàn)證了我們當(dāng)初對(duì)于模型的預(yù)計(jì)：其一方面保存了正向N元算法的正確切分，一方面用逆向N元算法有效地避免了正向算法的錯(cuò)誤切分。在機(jī)器翻譯的自動(dòng)評(píng)估上，我們首先介紹了兩種常用的基于參考譯文的評(píng)估算法BLEU和NIST，然后給出了一種基于N元模型的句子流暢度評(píng)估方法E3。這種方法不需要借助任何參考譯文，它通過(guò)區(qū)別地對(duì)待句子中不同的詞的轉(zhuǎn)移概率，達(dá)到了很好的評(píng)估效果。綜上所述，本文針對(duì)漢語(yǔ)詞法分析、口語(yǔ)句子切分和機(jī)器翻譯評(píng)估提出了以統(tǒng)計(jì)模型為基礎(chǔ)的創(chuàng)新方法，它們不僅僅在科學(xué)方

7、法上有重要的參考價(jià)值，對(duì)于實(shí)際應(yīng)用中也有重要意義。ABSTRACTThis thesis proposed our novel statistical approaches on Chinese word analysis, utterance segmentation and automatic evaluation of machine translation (MT). Word analysis is the first step for most application based on Chinese language technologies; utterance segment

8、ation is the bridge which connects speech recognition and text translation in a speech translation system; automatic evaluation of machine translation (MT) system can speed the research and development of a MT system, reduce its developing cost. In short, the three aspects all belong to the basic re

9、search area of Natural Language Processing (NLP) and have significant meaning to many important applications such as text translation, speech translation and so on.In Chinese word analysis, we proposed a novel unified approach based on HMM, which efficiently combine word segmentation, Part of Speech

10、 (POS) tagging and Named Entity (NE) recognition. Our first model is a class-based HMM. So as to increase its accuracy, we introduce into the word-based HMM and combine it with the class-based HMM. At last we used a “word-to-character” smoothing method for predicting the probability of those words w

11、hich dont occur in the training set. The experimental results show that our combined model, by comprehensively considering the information of Chinese characters, words, POS and NE, achieved much better performance in the precision and recall of the Chinese word segmentation. Based on the knowledge o

12、f our combined model, we described the details in implementing the general word segmentation system APCWS. We discussed some technical problems in the data saving and loading, and described our modules of knowledge management and word lattice construction.In utterance segmentation, this paper propos

13、ed a novel approach which was based on a bi-directional N-gram model and Maximized Entropy model. This novel method, which effectively combines the normal and reverse N-gram algorithm, is able to make use of both the left and right context of the candidate site and achieved very good performance in

14、utterance segmentation. We conducted experiments both in Chinese and in English. The results showed the effect of our novel method was much better than the normal N-gram algorithm. Then by analyzing the experimental results, we found the reason why our novel method achieved better results: it on one

15、 hand retained the correct segmentation of the normal N-gram algorithm, on the other hand avoided the incorrect segmentation by making use of reverse N-gram algorithm.In automatic evaluation of MT systems, we first introduced two classic methods on automatic evaluation which relied on reference tran

16、slations. Then we proposed our novel sentence fluency evaluation method based on N-gram model. This method, called as E3, doesnt need any reference translations and achieved very well evaluation performance by discriminately use the different transmission probabilities of words in the evaluating sen

17、tence. In summarization, this thesis proposed novel approaches for the three basic researches in NLP: Chinese word analysis, utterance segmentation and automatic evaluation of MT systems. We believe the original ideas in them not only have important reference value for other researches, but also can

18、 be used to improve the performance of NLP applications.目錄第一章 緒言1第二章 統(tǒng)計(jì)語(yǔ)言模型32.1 N元模型32.1.1 N元模型定義32.1.2參數(shù)估計(jì)42.2 隱馬爾可夫模型82.2.1 定義82.2.2 和HMM相關(guān)聯(lián)的三個(gè)問(wèn)題92.3 最大熵模型132.3.1 介紹132.3.2 定義152.3.3 參數(shù)訓(xùn)練172.4 小結(jié)20第三章 基于隱馬爾可夫模型的一體化中文分詞方法213.1 相關(guān)工作213.2 基于類(lèi)別的隱馬爾可夫分詞框架233.2.1 詞的定義243.2.2 基于類(lèi)別的隱馬爾可夫模型243.2.3詞的生成模型263

19、.2.4 基于類(lèi)別的隱馬爾可夫模型的小結(jié)293.3 對(duì)于基于類(lèi)別的隱馬爾可夫模型的改進(jìn)293.3.1 基于類(lèi)別和基于詞的隱馬爾可夫模型的合并303.3.2 “詞到字”的平滑方法313.4 實(shí)驗(yàn)323.4.1 訓(xùn)練和測(cè)試語(yǔ)料323.4.2 各模型的測(cè)試結(jié)果323.4.3 錯(cuò)誤分析343.5 通用分詞系統(tǒng)APCWS實(shí)現(xiàn)介紹353.5.1 APCWS系統(tǒng)框架353.5.2 APCWS的數(shù)據(jù)裝載以及知識(shí)管理363.5.3 APCWS的切分模塊403.6 小結(jié)45第四章 基于雙向N元模型和最大熵模型的句子切分464.1 相關(guān)工作474.2 最大熵平衡的雙向N元切分算法504.2.1 正向N元切分算法50

20、4.2.2 逆向N元切分算法514.2.3 雙向N元切分算法524.2.4 基于最大熵模型的切分算法534.2.5 最大熵平衡的雙向N元切分算法544.3 實(shí)驗(yàn)564.3.1 訓(xùn)練和測(cè)試語(yǔ)料564.3.2 實(shí)驗(yàn)結(jié)果564.3.3 結(jié)果分析584.4 小結(jié)59第五章 機(jī)器翻譯自動(dòng)評(píng)估方法研究605.1 相關(guān)工作605.2 基于參考譯文的評(píng)估方法625.2.1 BLEU (Bilingual Evaluation Understudy)算法625.2.2 NIST算法635.2.3 改進(jìn)的NIST算法645.3 基于統(tǒng)計(jì)的句子流暢度評(píng)估方法655.3.1 基于N元模型的句子流暢度評(píng)估655.3.2

21、 實(shí)驗(yàn)685.4 小結(jié)72第六章 結(jié)論73參考文獻(xiàn)75附錄1：本論文的研究工作得到如下項(xiàng)目資助81附錄2：攻讀碩士學(xué)位期間發(fā)表的論文81致謝82第一章 緒言近十幾年來(lái)，隨著計(jì)算機(jī)硬件設(shè)備的飛速發(fā)展，其單位存儲(chǔ)和計(jì)算成本大幅度降低，使一些基于大規(guī)模搜索和迭代的復(fù)雜算法能夠在PC上廣泛地實(shí)現(xiàn)和應(yīng)用；而隨著行業(yè)信息化的普及和網(wǎng)絡(luò)資源的迅猛膨脹，可用語(yǔ)料資源也大為豐富，這一切給基于大規(guī)模語(yǔ)料庫(kù)的統(tǒng)計(jì)自然語(yǔ)言處理提供了所需的硬件和軟件環(huán)境。統(tǒng)計(jì)自然語(yǔ)言處理以數(shù)學(xué)模型和大規(guī)模語(yǔ)料庫(kù)為基礎(chǔ)，其核心思想是建立數(shù)學(xué)模型以表述某一種語(yǔ)言現(xiàn)象，然后在大規(guī)模語(yǔ)料庫(kù)中對(duì)那種模型進(jìn)行訓(xùn)練，使其滿(mǎn)足已經(jīng)獲知的經(jīng)驗(yàn)知識(shí)，然后

22、用訓(xùn)練好的模型對(duì)于未知的現(xiàn)象進(jìn)行預(yù)測(cè)。幾乎所有基于統(tǒng)計(jì)的方法都可以歸結(jié)到上述的框架中去。相比傳統(tǒng)的基于規(guī)則的自然語(yǔ)言處理，統(tǒng)計(jì)方法有如下好處。第一， 它不依賴(lài)于人主觀的先驗(yàn)知識(shí)，這也是本文認(rèn)為統(tǒng)計(jì)方法最重要的優(yōu)點(diǎn)。大規(guī)模語(yǔ)料庫(kù)實(shí)際上和規(guī)則一樣，都是一種知識(shí)的表征形式。不同的是語(yǔ)料庫(kù)相比規(guī)則而言，有更強(qiáng)的獨(dú)立性和客觀性。大家知道，規(guī)則往往是針對(duì)某一特定的應(yīng)用，由某方面的專(zhuān)家按照一定的形式所書(shū)寫(xiě)的指導(dǎo)原則，它是專(zhuān)家在自己的經(jīng)驗(yàn)基礎(chǔ)上對(duì)語(yǔ)言現(xiàn)象的一種總結(jié)，具有很強(qiáng)的主觀性。往往不同的專(zhuān)家所書(shū)寫(xiě)的規(guī)則會(huì)有不同，甚至同一位專(zhuān)家在不同時(shí)候所寫(xiě)規(guī)則也會(huì)有出入，而隨著規(guī)則的不斷增加，新舊規(guī)則之間會(huì)產(chǎn)生矛盾，當(dāng)

23、規(guī)則的數(shù)目達(dá)到一定程度以后往往就不可能再增加新的規(guī)則了。而語(yǔ)料庫(kù)很簡(jiǎn)單，任何一篇電子文檔都可以成為一個(gè)小的語(yǔ)料庫(kù)，即使對(duì)于那些經(jīng)過(guò)人工處理后的熟語(yǔ)料，由于大家是在一定規(guī)范地約束下進(jìn)行的，那些規(guī)范相對(duì)而言都是比較簡(jiǎn)單和機(jī)械的規(guī)范，所以人的主觀影響會(huì)小得多，即使在某些個(gè)別的詞或句上出現(xiàn)矛盾，也不會(huì)對(duì)整體造成很大影響。第二， 統(tǒng)計(jì)方法相比基于規(guī)則的方法有更強(qiáng)的魯棒性。規(guī)則的方法是離散的，一條規(guī)則只能總結(jié)有限數(shù)目的語(yǔ)言現(xiàn)象；而統(tǒng)計(jì)模型是連續(xù)的，它可以對(duì)全部的現(xiàn)象進(jìn)行描述。規(guī)則是人對(duì)于經(jīng)驗(yàn)知識(shí)的一種抽象，這種抽象是零散的，它并不保證所有的規(guī)則的總和可以描述全部的語(yǔ)言現(xiàn)象，所以每遇到一個(gè)不能處理的實(shí)例，我

24、們必須增加新的規(guī)則以滿(mǎn)足需求。而統(tǒng)計(jì)模型所依賴(lài)的語(yǔ)料庫(kù)雖然也是離散的，語(yǔ)料庫(kù)中包含的現(xiàn)象也只是全部現(xiàn)象的一個(gè)真子集，但由于我們是用嚴(yán)密的數(shù)學(xué)模型來(lái)對(duì)現(xiàn)象進(jìn)行的抽象和歸納，它就可以保證訓(xùn)練出的模型適用于所有的實(shí)例，從而保證了強(qiáng)的魯棒性。當(dāng)然，不同的統(tǒng)計(jì)模型對(duì)現(xiàn)象描述的準(zhǔn)確程度是不一樣的。第三， 統(tǒng)計(jì)方法將知識(shí)和算法分離。前文已提過(guò)，規(guī)則往往是由某方面的專(zhuān)家針對(duì)某一特定的應(yīng)用所書(shū)寫(xiě)的指導(dǎo)原則，而同一個(gè)語(yǔ)料庫(kù)可以為多種算法、多種應(yīng)用服務(wù)，它是很獨(dú)立的知識(shí)庫(kù)。這樣語(yǔ)料庫(kù)的建立和完善可以和算法的設(shè)計(jì)并行，不僅節(jié)省了人力物力，也給一些標(biāo)準(zhǔn)化測(cè)試提供了基礎(chǔ)。另外這項(xiàng)優(yōu)點(diǎn)給基于統(tǒng)計(jì)方法的系統(tǒng)的維護(hù)和更新帶來(lái)了

25、很大的方便。隨著應(yīng)用的擴(kuò)展，我們往往要考慮到新的語(yǔ)言現(xiàn)象，這時(shí)基于統(tǒng)計(jì)方法的系統(tǒng)只需要用更大的語(yǔ)料庫(kù)重新訓(xùn)練一下模型就可以了，而基于規(guī)則的方法則需要增加大量的規(guī)則，而如上文以前提過(guò)的，這并非一件容易的事情。正是由于這些優(yōu)點(diǎn)，統(tǒng)計(jì)方法在近十年來(lái)得到了飛速發(fā)展，它逐步取代傳統(tǒng)基于規(guī)則的方法，成為自然語(yǔ)言處理領(lǐng)域的主流技術(shù)。在中文處理方面，統(tǒng)計(jì)方法已經(jīng)有很多成功的應(yīng)用，如詞性標(biāo)注、音字轉(zhuǎn)化及拼音輸入等，但由于漢語(yǔ)本身的復(fù)雜性和靈活性，有很多問(wèn)題依然尚待解決。本文試圖以統(tǒng)計(jì)模型為基礎(chǔ)，研究漢語(yǔ)自動(dòng)分詞、分句及機(jī)器翻譯自動(dòng)評(píng)估的解決方法。分詞是大部分中文處理系統(tǒng)的第一步，其重要性不言而喻；句子切分是語(yǔ)音

26、翻譯中連接語(yǔ)音識(shí)別和文本翻譯的橋梁；而機(jī)器翻譯的自動(dòng)評(píng)估可以提高一個(gè)機(jī)器翻譯系統(tǒng)的開(kāi)發(fā)速度和節(jié)約其成本。簡(jiǎn)言之，這三類(lèi)問(wèn)題同屬于中文信息處理領(lǐng)域的基礎(chǔ)研究課題，它們的效果直接關(guān)系到其他高層應(yīng)用，所以我們的研究不僅僅在科學(xué)方法上有重要的參考價(jià)值，對(duì)于實(shí)際應(yīng)用也有重要意義。后面的章節(jié)是這樣安排的：第二章介紹三種常用的統(tǒng)計(jì)模型，這是本文所提出的方法的理論基礎(chǔ)；第三章介紹基于隱馬爾可夫模型的一體化漢語(yǔ)分詞方法；第四章介紹基于N元模型和最大熵模型的句子切分方法；第五章介紹基于N元模型的句子流暢度評(píng)估方法；第六章對(duì)全文進(jìn)行總結(jié)。第二章統(tǒng)計(jì)語(yǔ)言模型本論文的所有工作均是基于統(tǒng)計(jì)方法，因此在本章里，我們將介紹一

27、些常用的統(tǒng)計(jì)模型。其構(gòu)成了我們的方法的理論支撐。統(tǒng)計(jì)模型是一種抽象的數(shù)學(xué)模型，用來(lái)對(duì)事物進(jìn)行一種近似的描述，它首先假設(shè)某類(lèi)現(xiàn)象滿(mǎn)足一種模型，然后用已知的現(xiàn)象實(shí)例對(duì)模型進(jìn)行訓(xùn)練，以得到模型的相關(guān)參數(shù)，然后用這個(gè)訓(xùn)練過(guò)的模型來(lái)預(yù)測(cè)未知的現(xiàn)象。對(duì)于自然語(yǔ)言處理而言，最常用的有N元模型、隱馬爾可夫模型、最大熵模型等。2.1 N元模型2.1.1 N元模型定義N元模型是自然語(yǔ)言處理中最常用的一種數(shù)學(xué)模型。它的定義如下。圖1：N元模型的定義假設(shè)序列w1w2wm是一個(gè)N階馬爾可夫鏈，那么某一元素wi出現(xiàn)的概率只和其前面N-1個(gè)元素相關(guān)，即：（1）如果我們假設(shè)語(yǔ)言也滿(mǎn)足馬爾可夫性，那么某一個(gè)詞在某個(gè)句子中的出現(xiàn)

28、概率就可以用公式(1)進(jìn)行計(jì)算，進(jìn)而一個(gè)句子的概率可以計(jì)算為：(2)一般N越大，模型越精確，但所用參數(shù)和所需要的訓(xùn)練集也越大（如果訓(xùn)練集不夠大將導(dǎo)致嚴(yán)重的數(shù)據(jù)稀疏問(wèn)題）。假設(shè)詞匯量為100K（實(shí)用中文系統(tǒng)的詞匯量），下表給出了不同的N元模型的參數(shù)形式以及所用的參數(shù)數(shù)目。表1：N元模型實(shí)例及參數(shù)個(gè)數(shù)模型參數(shù)參數(shù)個(gè)數(shù)0-gramp(w)=1/|V|11-gram(unigram)p(w)1e52-gram(bigram)p(wi|wi-1)1e103-gram(trigram)p(wi|wi-2 wi-1)1e154-gram(tetragram)p(wi| wi-3 wi-2 wi-1)1e20

29、在實(shí)際運(yùn)用中，考慮到訓(xùn)練所需的語(yǔ)料規(guī)模，N一般取3，也就是所謂的Trigram。2.1.2參數(shù)估計(jì)2.1.2.1最大似然估計(jì)雖然我們已經(jīng)介紹了N元模型的基本概念，但要真正使用它，還需要進(jìn)行參數(shù)估計(jì)這一步，也就是將表1中的那些參數(shù)計(jì)算出來(lái)。以Trigram為例，用最大似然估計(jì)計(jì)算參數(shù)的公式為：(3)其中count(wi,wj)表示wi,wj在訓(xùn)練語(yǔ)料中同現(xiàn)的次數(shù)。最大似然估計(jì)可以計(jì)算出訓(xùn)練語(yǔ)料中出現(xiàn)過(guò)的N元組對(duì)應(yīng)的Trigram參數(shù)，但如果我們碰到?jīng)]有出現(xiàn)過(guò)的N元組怎么辦呢？最簡(jiǎn)單的辦法是認(rèn)為那些參數(shù)為0，但這樣做會(huì)導(dǎo)致系統(tǒng)的適應(yīng)能力很低，一旦碰到未出現(xiàn)過(guò)的N元組，系統(tǒng)就基本上處理不了。為了解決

30、這一問(wèn)題，Laplace提出了一種簡(jiǎn)單機(jī)制，就是給每個(gè)N元組，無(wú)論其有無(wú)在訓(xùn)練語(yǔ)料中出現(xiàn)，都加上1。如下圖所示。圖2：Laplace法則PLap(w1,wn)=count(w1 ,wn)+1/(C+B)C: 訓(xùn)練集中N元組出現(xiàn)的總次數(shù)B: N元參數(shù)的總個(gè)數(shù)Laplace法則可以粗略解決“0次數(shù)”問(wèn)題，但它將所有未出現(xiàn)的N元組都賦予出現(xiàn)次數(shù)1是不符合語(yǔ)言模型的實(shí)際情況的，因?yàn)楹芏嘣~的組合（N元組）其實(shí)根本就不存在。Lidstone在Laplace的基礎(chǔ)上又做了一點(diǎn)改進(jìn)，他給所有N元組加上的不是整數(shù)1，而是一個(gè)待確定的小數(shù)。如下圖所示。圖3：Lidstone法則PLid(w1,wn)=count(

31、w1 ,wn)+B/(C+B)C: 訓(xùn)練集中N元組出現(xiàn)的總次數(shù)B: N元參數(shù)的總個(gè)數(shù):待確定的小數(shù)是一個(gè)小于1的小數(shù)，可以在通過(guò)如下方式訓(xùn)練得到：將訓(xùn)練語(yǔ)料分為2部分A和B，首先用A對(duì)N元模型進(jìn)行訓(xùn)練，然后對(duì)B進(jìn)行預(yù)測(cè)，調(diào)節(jié)直到1，使得對(duì)B的預(yù)測(cè)達(dá)到最佳；然后用B作訓(xùn)練，A作測(cè)試，調(diào)節(jié)直到2, 使得對(duì)A的預(yù)測(cè)達(dá)到最佳；最終的值為1和2的算術(shù)平均值。2.1.2.2參數(shù)平滑Laplace和Lidstone法則僅僅是對(duì)“0次數(shù)”問(wèn)題的一個(gè)粗糙的解決方式，它們都無(wú)法針對(duì)不同的N元組做出不同的預(yù)測(cè)，我們需要更為細(xì)致的參數(shù)平滑算法來(lái)幫助我們進(jìn)行參數(shù)估計(jì)。從機(jī)理上劃分，目前的參數(shù)平滑算法可以分為折扣法（Di

32、scounting）、回退法（Back-off）和插值法（Interpolation）。在這里我們只介紹其中的回退法?；赝朔ㄊ亲畛Ｓ玫囊环N平滑算法，它的基本思想是當(dāng)高階參數(shù)不存在時(shí)，回退到低階參數(shù)，當(dāng)然，為了保證每一階參數(shù)的總和要為1，對(duì)于那些存在的參數(shù)要進(jìn)行一些減弱。我們以Modified Kneser-Ney Smoothing為例來(lái)介紹回退法，這種平滑方法被認(rèn)為是對(duì)于N元模型最有效的平滑算法之一，也是本文所實(shí)現(xiàn)的系統(tǒng)中所實(shí)用的方法。Modified Kneser-Ney Smoothing算法見(jiàn)圖4。從圖4中我們可以看出，對(duì)于已經(jīng)存在的N元組，Modified Kneser-Ney Sm

33、oothing根據(jù)他們出現(xiàn)的次數(shù)給出不同的消減，對(duì)于不存在的N元組，它根據(jù)一定的比例回退到低階參數(shù)，而低階參數(shù)的計(jì)算和高階類(lèi)似，可以回退到更低階。值得注意的是Modified Kneser-Ney Smoothing對(duì)于一元參數(shù)的計(jì)算方法，它沒(méi)有使用語(yǔ)料中的絕對(duì)統(tǒng)計(jì)數(shù)目，而是用和它相鄰的不同的一元組的數(shù)目，這樣可以避免如下的錯(cuò)誤回退發(fā)生：假設(shè)詞組AB在語(yǔ)料中出現(xiàn)的頻度很高，但是對(duì)于B而言，它只出現(xiàn)在A的后面，也就是p(B|A)=1，這樣如果統(tǒng)計(jì)B的出現(xiàn)頻度，是很高的，而當(dāng)我們計(jì)算某個(gè)p(B|C)時(shí)，顯然語(yǔ)料中找不到CB這個(gè)詞組，因而回退到p(B)，而p(B)的值是很大的，這樣就形成了一種誤導(dǎo)。

34、而如果我們用B左邊出現(xiàn)的不同詞的個(gè)數(shù)作為一元概率的統(tǒng)計(jì)基礎(chǔ)，那么B左邊只有A這一個(gè)詞，個(gè)數(shù)為1，當(dāng)我們?cè)倩赝说紹時(shí)，就不會(huì)出現(xiàn)很高的概率，從而避免了這種誤導(dǎo)。圖4：Modified Kneser-Ney Smoothing其中： nx為次數(shù)為x的n元組的個(gè)數(shù)2.2 隱馬爾可夫模型2.2.1 定義隱馬爾可夫模型（Hidden Markov Model）是自然語(yǔ)言處理和語(yǔ)音識(shí)別中又一非常常用的數(shù)學(xué)模型，它于20世紀(jì)60年代末被Baum提出，在70年代處被CMU的Baker第一次用于語(yǔ)音識(shí)別，其后慢慢流行開(kāi)來(lái)并被用于自然語(yǔ)言處理的一些領(lǐng)域中。它假設(shè)在觀測(cè)現(xiàn)象的背后有一系列隱藏的狀態(tài)，觀測(cè)序列是由這些

35、隱藏狀態(tài)序列所生成，其定義如下圖所示。圖5：隱馬爾可夫模型隱馬爾可夫模型可表示為一個(gè)五元組： (x , o, A, B, )其中： x = q1,., qn：隱狀態(tài)的有限集合 o = o1,.,om：觀測(cè)現(xiàn)象的有限集合 A = aij，aij = p(Xt+1 = qj |Xt = qi)：轉(zhuǎn)移概率 B = bik，bik = p(Ot = ok | Xt = qi)：輸出概率 = i， i = p(X1 = qi)：初始狀態(tài)分布和隱馬爾可夫模型相伴隨的一般有三項(xiàng)假設(shè)：馬爾可夫假設(shè)、不動(dòng)性假設(shè)和輸出獨(dú)立性假設(shè)。馬爾可夫假設(shè)是假設(shè)狀態(tài)序列滿(mǎn)足一階馬爾可夫性，即某一狀態(tài)序列出現(xiàn)的概率只和它前面一個(gè)

36、狀態(tài)相關(guān)，這點(diǎn)和二元模型是一致的；不動(dòng)性是狀態(tài)的轉(zhuǎn)移和時(shí)間無(wú)關(guān)；獨(dú)立性是某一觀測(cè)現(xiàn)象只和當(dāng)前狀態(tài)相關(guān)。如果我們用O1 ,O2,OT表示觀測(cè)序列，X1 ,X2,XT表示狀態(tài)序列，這三項(xiàng)假設(shè)可以用下圖表示。圖6：隱馬爾可夫假設(shè)馬爾可夫假設(shè)： p(Xi|Xi-1X1) = p(Xi|Xi-1)不動(dòng)性假設(shè)： p(Xi+1|Xi) = p(Xj+1|Xj)，對(duì)任意i,j成立輸出獨(dú)立性假設(shè)： p(O1,.,OT | X1,.,XT) = p(Ot | Xt) 2.2.2 和HMM相關(guān)聯(lián)的三個(gè)問(wèn)題和N元模型一樣，在給出了定義之后，我們自然想到如何去訓(xùn)練和使用它。一般而言，和隱馬爾可夫模型相關(guān)的有三個(gè)經(jīng)典問(wèn)題

37、：評(píng)估問(wèn)題，解碼問(wèn)題和學(xué)習(xí)問(wèn)題。以下我們將分別介紹。2.2.2.1評(píng)估問(wèn)題（前向算法）評(píng)估問(wèn)題是給定模型，求某一觀測(cè)序列O1,.,OT的概率。為了簡(jiǎn)化這個(gè)問(wèn)題，我們首先假設(shè)觀測(cè)序列是由狀態(tài)Q=q1,qT生成的，在這個(gè)假設(shè)下，觀測(cè)序列的概率為：（4）而給定，狀態(tài)序列Q=q1,qT的概率為：（5）由于我們并不知道觀測(cè)序列是由哪一種狀態(tài)序列所生成，我們必須考慮所有的情況，也就是：（6）公式6給出了計(jì)算觀測(cè)序列的方法，但從公式中我們可以看出，其時(shí)間復(fù)雜度很高，假設(shè)狀態(tài)空間長(zhǎng)度為N，q1,qT有NT種可能組合，而總的時(shí)間復(fù)雜度將為：指數(shù)級(jí)復(fù)雜度的算法在實(shí)際應(yīng)用中一般是無(wú)法實(shí)現(xiàn)的。為此我們引入動(dòng)態(tài)規(guī)劃來(lái)縮

38、減計(jì)算量，由于HMM中的狀態(tài)的轉(zhuǎn)移概率只和其前一狀態(tài)相關(guān)，這給我們的計(jì)算帶來(lái)了很大好處。我們定義前向變量it為：給定模型，在t時(shí)刻狀態(tài)為Si的部分觀測(cè)序O1Ot的概率。用公式表述如下：（7）基于it，kt+1可以計(jì)算為：（8）這是一個(gè)迭代公式，其初始值為：（9）而我們最終所要得到的結(jié)果為：（10）而對(duì)于公式10的迭代計(jì)算，在每一個(gè)觀測(cè)值我們要考慮所有N個(gè)狀態(tài)，對(duì)于每個(gè)狀態(tài)我們需要考慮其前面N個(gè)狀態(tài)，那么總的時(shí)間復(fù)雜度為N*N*T=N2*T，大大小于先前的NT*2T，這個(gè)復(fù)雜度是可以實(shí)現(xiàn)的。2.2.2.2解碼問(wèn)題（韋特比算法）解碼問(wèn)題就是給定，模型和觀測(cè)序列，找到最可能的狀態(tài)序列。這個(gè)問(wèn)題也是H

39、MM在大多數(shù)實(shí)際應(yīng)用中的運(yùn)作方式。比如對(duì)于詞性標(biāo)注，我們把詞看作觀測(cè)序列，詞性看作狀態(tài)序列，標(biāo)注的過(guò)程就是找到最可能的狀態(tài)序列的過(guò)程。對(duì)于解碼問(wèn)題的精確數(shù)學(xué)描述如下：（11）事實(shí)上解碼問(wèn)題和評(píng)估問(wèn)題很相似，評(píng)估是計(jì)算所有可能的狀態(tài)序列產(chǎn)生的觀測(cè)序列的概率的總和，而解碼則是從這些狀態(tài)序列中挑出最有可能的，也就是概率最大的。和評(píng)估問(wèn)題類(lèi)似，如果我們遍歷所有可能的狀態(tài)序列，計(jì)算的時(shí)間復(fù)雜度會(huì)很高，我們同樣采用動(dòng)態(tài)規(guī)劃來(lái)解決解碼問(wèn)題。我們定義it為t時(shí)刻到達(dá)狀態(tài)i的最優(yōu)路徑（狀態(tài)序列）：（12）這樣在t+1時(shí)刻到達(dá)狀態(tài)k的最優(yōu)路徑為：（13）對(duì)于每個(gè)狀態(tài)，我們通過(guò)公式13選擇其最優(yōu)的前一狀態(tài)并記錄下來(lái)

40、，一直到最末的狀態(tài)T，然后遍歷T的各個(gè)狀態(tài)，選擇最優(yōu)的一個(gè)，最后通過(guò)各狀態(tài)的前驅(qū)得到完整的最優(yōu)路徑，也就是狀態(tài)序列。這個(gè)過(guò)程可以用下圖表示。圖7：韋特比搜索初始化：1= i = N迭代向前：1= k = N ; 2= t = T結(jié)束：2.2.2.3學(xué)習(xí)問(wèn)題（前向后向算法）學(xué)習(xí)問(wèn)題也就是訓(xùn)練問(wèn)題，即給定觀測(cè)序列，找到最優(yōu)的，使觀測(cè)序列的概率也就是P(O|)最大。這個(gè)問(wèn)題是三個(gè)問(wèn)題中最難的一個(gè)，一般我們用前向后向算法（EM算法在HMM參數(shù)估計(jì)上的應(yīng)用）來(lái)預(yù)測(cè)。包含三方面，初始概率分布、狀態(tài)間轉(zhuǎn)移概率、和狀態(tài)到觀測(cè)值的生成概率。我們首先來(lái)考慮如何計(jì)算這三種參數(shù)的期望值。首先我們引入后向變量jt：給定

41、t時(shí)刻的狀態(tài)Sj和模型，部分觀測(cè)序列Ot+1 Ot+2 OT的概率。（15）我們定義t(i,j)為：給定觀測(cè)序列和模型，在時(shí)間t為狀態(tài)Si，在時(shí)間t+1為狀態(tài)Sj的概率：（14）帶入前向和后向變量，t(i,j)可表示為：（15）那么在時(shí)刻t狀態(tài)為Si的概率rit為：（16）從而狀態(tài)Si的期望次數(shù)為：（17）從狀態(tài)Si轉(zhuǎn)移到Si的期望次數(shù)為：（18）從公式17、18，我們可以給出HMM各參數(shù)的期望值，然后修正后的模型參數(shù)又可以用來(lái)計(jì)算狀態(tài)的期望次數(shù)以及狀態(tài)轉(zhuǎn)移的期望次數(shù)，如此循環(huán)，直到收斂，也就是我們所要求的最優(yōu)參數(shù)。算法如圖8所示。圖8：前向后向算法初始化：給設(shè)置初始值，1=i,j=N; 1=

42、k=T迭代：循環(huán)進(jìn)行下面的迭代直到收斂。1 用公式15和16計(jì)算t(i,j)和rit的值，1=i,j=N; 1=t=1-A (for all A 0)帶入35式，我們得到：（36）由上式可以看出，只要我們能找到使A(|)0，那么新的模型相對(duì)于舊的就是一個(gè)改進(jìn)，為了讓模型盡快收斂，我們尋找使A(|)最大的。注意到如果將目前的A(|)以i為變量微分并令之為0，我們得到的等式中包含12,n，這樣我們?nèi)詿o(wú)法簡(jiǎn)單地計(jì)算出i。如果我們能把exp中的其他換出來(lái)，就可以比較方便的對(duì)A(|)進(jìn)行微分。為此我們將36式改寫(xiě)為：（37）其中f#(x,y)為：（38）也就是 (x,y)所滿(mǎn)足的特征函數(shù)的個(gè)數(shù)，由于：我

43、們可以把看作一個(gè)隨機(jī)變量的分布，而exp為一個(gè)凸函數(shù)，那么應(yīng)用Jensen不等式：E(exp(x)=exp(E(x)，我們得到：（39）現(xiàn)在我們將B(|)微分，就得到最終我們要求的等式：（40）上面方程的解即為我們所求的i。如果對(duì)于所有的(x,y) f#(x,y)為定值，我們可以方便的求得i，否則，我們需要借助一些求根方法如牛頓法來(lái)解方程40?；谏厦娴慕忉?zhuān)覀兘o出訓(xùn)練最大熵參數(shù)的迭代算法(Improved Iterative Scaling): IIS Algorithm1. 給出12n的初值2. 循環(huán)下列兩項(xiàng)操作直到收斂解方程i +=i2.4 小結(jié)本章詳細(xì)介紹了自然語(yǔ)言處理中常用的三種統(tǒng)

44、計(jì)模型：N元模型、隱馬爾可夫模型和最大熵模型。這些模型是基于大規(guī)模語(yǔ)料庫(kù)的統(tǒng)計(jì)自然語(yǔ)言處理的理論基礎(chǔ)。N元模型是對(duì)語(yǔ)言本質(zhì)的一種描述，是目前為止語(yǔ)音識(shí)別中最有效的語(yǔ)言模型；隱馬爾可夫模型是自然語(yǔ)言處理和語(yǔ)音識(shí)別中應(yīng)用最為廣泛的模型，在很多領(lǐng)域得到了成功的應(yīng)用；最大熵模型是功能很強(qiáng)大、很有前景的一種統(tǒng)計(jì)模型，它可以有效地綜合多種特征，但其使用也最為靈活和復(fù)雜。如何有效地運(yùn)用和融和這些模型是統(tǒng)計(jì)自然語(yǔ)言處理要解決的問(wèn)題之一，也是本文試圖在中文分詞、分句和機(jī)器翻譯評(píng)估這三項(xiàng)的實(shí)際應(yīng)用中探索的問(wèn)題。第三章 基于隱馬爾可夫模型的一體化中文分詞方法本章將詳細(xì)介紹我們所實(shí)現(xiàn)的通用分詞系統(tǒng)APCWS的理論基礎(chǔ)

45、和實(shí)現(xiàn)細(xì)節(jié)。如第一章的概述部分已經(jīng)介紹的，作為分詞中緊密關(guān)聯(lián)的兩方面，詞語(yǔ)邊界消歧和未登陸詞識(shí)別常常在一個(gè)一體化的模型中加以實(shí)現(xiàn)，但是詞性標(biāo)注卻很少被包含在那些一體化系統(tǒng)里。一般而言未登陸詞識(shí)別包含兩步：確定新詞邊界和判斷新詞的詞性，后者實(shí)際上就是對(duì)新詞的詞性標(biāo)注，所以我們沒(méi)有理由只對(duì)新詞進(jìn)行標(biāo)注而不標(biāo)注那些詞典中已有的詞。事實(shí)上，詞性標(biāo)注對(duì)于分詞也是有促進(jìn)的高山等，2001?；谏厦孢@些考慮，我們以隱馬爾可夫模型為基礎(chǔ)實(shí)現(xiàn)了一個(gè)包含了分詞、詞性標(biāo)注和新詞識(shí)別這三者的一體化分詞系統(tǒng)，我們期望它能帶來(lái)更好的效果。我們的一體化分詞中所使用的隱馬爾可夫模型最初是基于類(lèi)別的，也就是以詞性間的轉(zhuǎn)移概率為

46、狀態(tài)的轉(zhuǎn)移概率，這樣做可以有較高的召回率，但是在準(zhǔn)確率方面不如基于詞的隱馬爾可夫模型。于是我們將基于類(lèi)別的和基于詞的模型合并起來(lái)，形成一個(gè)混合的模型。在此基礎(chǔ)上，我們又提出 “詞到字”的概率平滑方法并將其使用在混合模型中。這一系列改進(jìn)都起到了很好的效果，最終將我們系統(tǒng)的性能提升到了很可觀的高度。本章將詳細(xì)介紹整個(gè)系統(tǒng)的理論框架以及實(shí)現(xiàn)細(xì)節(jié)，具體安排如下：第一小節(jié)介紹國(guó)內(nèi)外相關(guān)工作；第二小節(jié)介紹系統(tǒng)所使用的基于類(lèi)別的隱馬爾可夫模型；第三小節(jié)介紹兩種模型的合并以及“詞到字”的平滑方法；第四小節(jié)介紹實(shí)驗(yàn)結(jié)果；第五小節(jié)介紹系統(tǒng)的構(gòu)架和實(shí)現(xiàn)；第六小節(jié)是本章的小結(jié)。3.1 相關(guān)工作自動(dòng)分詞作為中文處理的重要初始化步驟，一直受到國(guó)內(nèi)外學(xué)者的關(guān)注，也是大家頗為頭疼的問(wèn)題之一。不像英語(yǔ)等字母文字，漢語(yǔ)書(shū)面語(yǔ)的詞和詞之間沒(méi)有間隔，這樣在進(jìn)行漢語(yǔ)的機(jī)器翻譯、語(yǔ)音合成等及檢索等應(yīng)用時(shí)，就必須先分詞。而對(duì)于分詞來(lái)說(shuō)，主要有兩個(gè)問(wèn)題需要解決：詞語(yǔ)邊界的歧義問(wèn)題和未登陸詞