评估方法研究——中科院自动化所 硕士论文-导师宗成庆37958.docx

《评估方法研究——中科院自动化所 硕士论文-导师宗成庆37958.docx》由会员分享，可在线阅读，更多相关《评估方法研究——中科院自动化所 硕士论文-导师宗成庆37958.docx（157页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 分类号 密级 UDC 编号 中国科学院研究究生院硕士学位论文 汉语词与句句子切分技术术及机器翻译译评估方法研研究 刘丁 指导教师师 宗成庆庆 研究员 博士 中国科学学院自动化研研究所 申请学位位级别 工学学硕士 学科专业业名称 模式式识别与智能能系统 论文提交交日期 20004年6月月 论文答辩辩日期 22004年66月 培养单位位 中国科学院院自动化研究究所 学位授予予单位 中中国科学院研研究生院 答辩委员员会主席 Approaches to Chinese Word Analysis, Utterance Segmentation and Automatic Evaluation of

2、Machine TranslationDisserttationn Submmittedd toInstituute off Autoomatioon, Chinnese Acadeemy of SScienccesin parttial ffulfilllmentt of tthe reequireementssfor thee degrree offMaster of EnngineeeringbyDing Liiu(Patterrn Reccognittion aand Inntelliigencee Systtem)Disserttationn Supeervisoor: Prrofe

3、sssor Chhengqiing ZoongI独创性声明本人声明所成交交的论文是我我个人在导师师指导下进行行的研究工作作及取得的研研究成果。尽尽我所知，除除了文中特别别加以标注和和致谢的地方方外，论文中中不包含其他他人已经发表表或撰写过的的研究成果。与与我一同工作作的同志对本本研究所做的的任何贡献均均已在论文中中作了明确地地说明并表示示了谢意。签名：_导导师签名：_ 日 期：_关于论文使用授授权的说明本人完全了解中中国科学院自自动化研究所所有关保留、使使用学位论文文的规定，即即：中国科学学院自动化研研究所有权保保留送交论文文的复印件，允允许论文被查查阅和借阅；可以公布论论文的全部或或部分内容

4、，可可以采用影印印、缩印或其其他复制手段段保存论文。（保密的论文在在解密后应遵遵守此规定）签名：_导导师签名：_ 日 期：_摘要本论文以统计计模型为基础础，在参考了大大量前人工作作的基础上，对汉语词法分析、口语句子切分和机器翻译评估进行了较为深入的探讨和研究。汉语词法分析是大部分中文处理的第一步，其重要性不言而喻；句子切分是语音翻译中连接语音识别和文本翻译的桥梁，无论语音识别和文本翻译单独的效果有多么好，这座桥没搭好，综合的性能依然无法提高；机器翻译的自动评估是构建机器翻译系统中很重要的辅助工作，其可以加速翻译系统的开发速度，缩短其开发周期。简言之，这三方面同属于自然语言处理的基础的研究领域，

5、其效果直接影响到高层应用的水平。在词法分析上，我我们利用隐马马尔可夫模型型（HMM）提提出了一种融融和了分词、词词性标注和命命名实体识别别的一体化词词法分析方法法。最初我们用用基于类别的的HMM，其其优点是对词词的覆盖面广广，系统开销销小；缺点是是不能精确地地预测词的出出现概率。为为了提升模型型的准确率，我我们引入基于于词汇的HMMM，并将两两者有机地结结合，并用一个“词到字”的概率平滑滑方法对基于于词的HMMM进行平滑。实验结果显显示，我们的的混合模型由由于综合考虑虑到了字、词、词性性以及命名实实体的知识，在在切分的准确确率和召回率率上都明显优优于单纯基于于类别或者基基于词的HMMM。此外在

6、在分词系统的的实现上，我我们借助对通通用分词系统APPCWS的整体框架和和各功能模块块的介绍，讨讨论了如何有有效地存储和和加载数据等等一些技术细节问题。在口语句子切分分上，我们提出了基于双向NN元模型和最大熵模型型的句子切分分算法，这种种算法由于通通过最大熵有机地地将正、逆向向N元切分结结合起来，综综合考虑到了了切分点左、右右的上下文，从从而得到了很很好的切分效效果。我们在在中、英文语语料上训练我们的的模型并作测测试，结果显显示其在性能上明明显优于基本本的正向N元元切分。在此此基础上，我我们分析并对对比了各模型的切分分结果，从而而验证了我们们当初对于模型型的预计：其其一方面保存了正向N元算算法

7、的正确切分，一一方面用逆向N元算算法有效地避避免了正向算算法的错误切切分。在机器翻译的自自动评估上，我我们首先介绍了两两种常用的基基于参考译文文的评估算法法BLEU和和NIST，然后给出了一种基于N元模型的句子流畅度评估方法E3。这种方法不需要借助任何参考译文，它通过区别地对待句子中不同的词的转移概率，达到了很好的评估效果。综上所述，本文文针对汉语词词法分析、口口语句子切分分和机器翻译译评估提出了了以统计模型型为基础的创创新方法，它它们不仅仅在在科学方法上上有重要的参参考价值，对对于实际应用中也有重要意义义。IABSTRACCTThis thhesis propoosed oour noove

8、l sstatissticall apprroachees on Chineese woord annalysiis, uttterannce seegmenttationn and autommatic evaluuationn of mmachinne traanslattion (MT). Word analyysis iis thee firsst steep forr mostt appllicatiion baased oon Chiinese languuage ttechnoologiees; uttterannce seegmenttationn is tthe brridg

9、e whichh connnects speecch reccognittion aand teext trranslaation in a speecch traanslattion ssystemm; auttomatiic evaaluatiion off machhine ttransllationn (MT) systtem caan speeed thhe ressearchh and devellopmennt of a MT systeem, reeduce its ddevelooping cost. In sshort, the threee aspeects aall b

10、eelong to thhe bassic reesearcch areea of Naturral Laanguagge Proocessiing (NNLP) aand haave siignifiicant meaniing too manyy impoortantt appllicatiions ssuch aas texxt traanslattion, speecch traanslattion aand soo on.In Chinnese wword aanalyssis, wwe prooposedd a noovel uunifieed appproachh baseed

11、on HMM, whichh effiicienttly coombinee wordd segmmentattion, Part of Sppeech (POS) taggging aand Naamed EEntityy (NE) recoognitiion. OOur fiirst mmodel is a classs-baseed HMMM. So as too incrrease its aaccuraacy, wwe inttroducce intto thee wordd-baseed HMMM and combiine itt withh the classs-baseed H

12、MMM. At last we ussed a “word-to-chharactter” smooothingg methhod foor preedictiing thhe proobabillity oof thoose woords wwhich dont occcur inn the trainning sset. TThe exxperimmentall resuults sshow tthat oour coombineed moddel, bby commpreheensiveely coonsideering the iinformmationn of CChinesse c

13、haaracteers, wwords, POS and NNE, acchieveed mucch bettter pperforrmancee in tthe prrecisiion annd reccall oof thee Chinnese wword ssegmenntatioon. Baased oon thee knowwledgee of oour coombineed moddel, wwe desscribeed thee detaails iin impplemennting the ggeneraal worrd seggmentaation systeem APCCW

14、S. WWe disscusseed somme tecchnicaal prooblemss in tthe daata saaving and lloadinng, annd desscribeed ourr moduules oof knoowledgge mannagemeent annd worrd latttice consttructiion.In utteerancee segmmentattion, this paperr propposed a novvel appproacch whiich waas bassed onn a bii-direectionnal N-gr

15、am modell and MMaximiized EEntroppy moddel. Thiss noveel metthod, whichh effeectiveely coombinees thee normmal annd revverse N-graam alggorithhm, iss ablee to mmake uuse off bothh the left and rright conteext off the candiidate site and aachievved veery goood peerformmance in uttterannce seegmenttat

16、ionn. We conduucted experrimentts botth in Chineese annd in Engliish. TThe reesultss showwed thhe efffect oof ourr noveel metthod wwas muuch beetter than the nnormall N-grram allgoritthm. TThen bby anaalyzinng thee expeerimenntal rresultts, wee founnd thee reasson whhy ourr noveel metthod aachievved

17、 beetter resullts: iit on one hhand rretainned thhe corrrect segmeentatiion off the normaal N-ggram aalgoriithm, on thhe othher haand avvoidedd the incorrrect segmeentatiion byy makiing usse of reverrse N-gram algorrithm.In autoomaticc evalluatioon of MT syystemss, we firstt intrroduceed twoo classs

18、ic mmethodds on autommatic evaluuationn whicch rellied oon refferencce traanslattions. Thenn we ppropossed ouur novvel seentencce fluuency evaluuationn methhod baased oon N-ggram mmodel. Thiss methhod, ccalledd as EE3, dooesnt neeed anyy refeerencee trannslatiions aand acchieveed verry welll evaalua

19、tiion peerformmance by diiscrimminateely usse thee diffferentt trannsmisssion pprobabbilitiies off wordds in the eevaluaating senteence. In summmarizaation, thiss thessis prroposeed novvel appproacches ffor thhe thrree baasic rresearrches in NLLP: Chhinesee wordd anallysis, utteerancee segmmentattio

20、n aand auutomattic evvaluattion oof MT systeems. WWe bellieve the ooriginnal iddeas iin theem nott onlyy havee impoortantt refeerencee valuue forr otheer ressearchhes, bbut allso caan be used to immprovee the perfoormancce of NLP aappliccationns.目录IV第一章 绪言1第二章 统计语语言模型32.1 N元模模型32.1.1 NN元模型定义义32.1.2参

21、数数估计42.2 隐马尔尔可夫模型82.2.1 定定义82.2.2 和和HMM相关联联的三个问题题92.3 最大熵熵模型132.3.1 介介绍132.3.2 定定义152.3.3 参参数训练172.4 小结20第三章 基于隐隐马尔可夫模模型的一体化化中文分词方方法213.1 相关工工作213.2 基于类类别的隐马尔尔可夫分词框框架233.2.1 词词的定义243.2.2 基基于类别的隐隐马尔可夫模模型243.2.3词的的生成模型263.2.4 基基于类别的隐隐马尔可夫模模型的小结293.3 对于基基于类别的隐隐马尔可夫模模型的改进293.3.1 基基于类别和基基于词的隐马马尔可夫模型型的合并3

22、03.3.2 “词到字”的平滑方法法313.4 实验323.4.1 训训练和测试语语料323.4.2 各各模型的测试试结果323.4.3 错错误分析343.5 通用分分词系统APPCWS实现现介绍353.5.1 AAPCWS系系统框架353.5.2 AAPCWS的的数据装载以以及知识管理理363.5.3 AAPCWS的的切分模块403.6 小结45第四章 基于双双向N元模型和最最大熵模型的的句子切分464.1 相关工工作474.2 最大熵熵平衡的双向向N元切分算法法504.2.1 正正向N元切分算法法504.2.2 逆逆向N元切分算法法514.2.3 双双向N元切分算法法524.2.4 基基于

23、最大熵模模型的切分算算法534.2.5 最最大熵平衡的的双向N元切分算法法544.3 实验564.3.1 训训练和测试语语料564.3.2 实实验结果564.3.3 结结果分析584.4 小结59第五章 机器翻翻译自动评估估方法研究605.1 相关工工作605.2 基于参参考译文的评评估方法625.2.1 BBLEU (Bilinngual Evaluuationn Undeerstuddy)算法625.2.2 NNIST算法法635.2.3 改改进的NISST算法645.3 基于统统计的句子流流畅度评估方方法655.3.1 基基于N元模型的句句子流畅度评评估655.3.2 实实验685.4

24、小结72第六章 结论73参考文献755附录1：本论文文的研究工作作得到如下项项目资助81附录2：攻读硕硕士学位期间间发表的论文文81致谢82第一章 绪言第一章 绪言近十几年来，随随着计算机硬件设设备的飞速发发展，其单位位存储和计算算成本大幅度度降低，使一一些基于大规规模搜索和迭代的复杂算法能够在PPC上广泛地地实现和应用用；而随着行行业信息化的的普及和网络络资源的迅猛猛膨胀，可用用语料资源也也大为丰富，这一切给基于大规模语料库的统计自然语言处理提供了所需的硬件和软件环境。统计自然语言处处理以数学模模型和大规模模语料库为基基础，其核心心思想是建立立数学模型以以表述某一种种语言现象，然然后在大规模

25、模语料库中对对那种模型进进行训练，使使其满足已经经获知的经验验知识，然后后用训练好的的模型对于未未知的现象进进行预测。几几乎所有基于于统计的方法法都可以归结结到上述的框框架中去。相相比传统的基基于规则的自自然语言处理理，统计方法法有如下好处处。第一， 它不依赖于人主主观的先验知知识，这也是本文文认为统计方方法最重要的的优点。大规规模语料库实实际上和规则则一样，都是是一种知识的的表征形式。不不同的是语料料库相比规则则而言，有更更强的独立性性和客观性。大大家知道，规规则往往是针针对某一特定定的应用，由由某方面的专专家按照一定定的形式所书书写的指导原原则，它是专专家在自己的的经验基础上上对语言现象象

26、的一种总结结，具有很强强的主观性。往往不同的的专家所书写写的规则会有有不同，甚至至同一位专家家在不同时候候所写规则也也会有出入，而而随着规则的的不断增加，新新旧规则之间会会产生矛盾，当当规则的数目目达到一定程程度以后往往往就不可能再再增加新的规规则了。而语语料库很简单单，任何一篇篇电子文档都都可以成为一一个小的语料料库，即使对对于那些经过过人工处理后后的熟语料，由由于大家是在在一定规范地地约束下进行行的，那些规规范相对而言言都是比较简简单和机械的的规范，所以以人的主观影影响会小得多多，即使在某某些个别的词词或句上出现现矛盾，也不不会对整体造造成很大影响响。第二， 统计方法相比基基于规则的方方法

27、有更强的的鲁棒性。规规则的方法是是离散的，一一条规则只能能总结有限数数目的语言现现象；而统计计模型是连续续的，它可以对全全部的现象进进行描述。规则是人对对于经验知识识的一种抽象象，这种抽象象是零散的，它它并不保证所所有的规则的的总和可以描描述全部的语语言现象，所所以每遇到一一个不能处理理的实例，我我们必须增加加新的规则以以满足需求。而而统计模型所所依赖的语料料库虽然也是是离散的，语语料库中包含含的现象也只只是全部现象象的一个真子子集，但由于于我们是用严严密的数学模模型来对现象象进行的抽象象和归纳，它它就可以保证证训练出的模模型适用于所所有的实例，从从而保证了强强的鲁棒性。当当然，不同的的统计模

28、型对对现象描述的的准确程度是是不一样的。第三， 统计方法将知识识和算法分离离。前文已提过过，规则往往往是由某方面面的专家针对对某一特定的的应用所书写写的指导原则则，而同一个个语料库可以以为多种算法法、多种应用用服务，它是是很独立的知知识库。这样样语料库的建建立和完善可可以和算法的的设计并行，不仅节省了人力物力，也给一些标准化测试提供了基础。另外这项优点给基于统计方法的系统的维护和更新带来了很大的方便。随着应用的扩展，我们往往要考虑到新的语言现象，这时基于统计方法的系统只需要用更大的语料库重新训练一下模型就可以了，而基于规则的方法则需要增加大量的规则，而如上文以前提过的，这并非一件容易的事情。正

29、是由于这些优优点，统计方方法在近十年年来得到了飞飞速发展，它它逐步取代传传统基于规则则的方法，成成为自然语言言处理领域的的主流技术。在中文处理方面面，统计方法法已经有很多多成功的应用用，如词性标标注、音字转化及拼音输入等，但但由于汉语本本身的复杂性性和灵活性，有有很多问题依依然尚待解决决。本文试图图以统计模型型为基础，研研究汉语自动动分词、分句及机器翻翻译自动评估估的解决方法法。分词是大大部分中文处处理系统的第第一步，其重重要性不言而而喻；句子切切分是语音翻翻译中连接语语音识别和文文本翻译的桥桥梁；而机器器翻译的自动动评估可以提提高一个机器器翻译系统的的开发速度和和节约其成本本。简言之，这三三

30、类问题同属属于中文信息息处理领域的的基础研究课题，它们的效果直直接关系到其其他高层应用，所以以我们的研究究不仅仅在科科学方法上有有重要的参考考价值，对于于实际应用也有重要要意义。后面的章节是是这样安排的的：第二章介介绍三种常用用的统计模型型，这是本文文所提出的方法法的理论基础础；第三章介介绍基于隐马马尔可夫模型型的一体化汉汉语分词方法法；第四章介介绍基于N元元模型和最大大熵模型的句句子切分方法法；第五章介介绍基于N元元模型的句子子流畅度评估估方法；第六六章对全文进进行总结。- 83 -第二章 统计语言模型第二章统计语语言模型本论文的所有工工作均是基于于统计方法，因因此在本章里里，我们将介介绍一

31、些常用用的统计模型型。其构成了了我们的方法法的理论支撑撑。统计模型是一种种抽象的数学学模型，用来来对事物进行行一种近似的的描述，它首首先假设某类类现象满足一一种模型，然然后用已知的的现象实例对对模型进行训训练，以得到到模型的相关关参数，然后后用这个训练练过的模型来来预测未知的的现象。对于于自然语言处处理而言，最最常用的有NN元模型、隐隐马尔可夫模模型、最大熵熵模型等。2.1 N元模模型2.1.1 NN元模型定义义N元模型是自自然语言处理理中最常用的的一种数学模模型。它的定定义如下。图1：N元模型型的定义假设序列w1w2wm是一个N阶马尔可夫链，那么某一元素wi出现的概率只和其前面N-1个元素相

32、关，即：（1）如果我们假设设语言也满足足马尔可夫性性，那么某一一个词在某个个句子中的出出现概率就可可以用公式(1)进行计算，进进而一个句子子的概率可以以计算为：(2)一般N越大，模模型越精确，但但所用参数和和所需要的训训练集也越大大（如果训练练集不够大将将导致严重的的数据稀疏问问题）。假设设词汇量为1100K（实用中中文系统的词词汇量），下下表给出了不不同的N元模模型的参数形形式以及所用用的参数数目目。表1：N元模型型实例及参数数个数模型参数参数个数0-gramp(w)=1/|V|11-gram(unigrram)p(w)1e52-gram(bigraam)p(wi|wii-1)1e103-g

33、ram(trigrram)p(wi|wii-2 wi-1)1e154-gram(tetraagram)p(wi| wwi-3 wi-2 wi-1)1e20在实际运用中，考考虑到训练所所需的语料规规模，N一般取33，也就是所所谓的Triigram。2.1.2参数数估计2.1.2.11最大似然估估计虽然我们已经介介绍了N元模模型的基本概概念，但要真真正使用它，还还需要进行参参数估计这一步，也就就是将表1中中的那些参数数计算出来。以Trigram为例，用最大似然估计计算参数的公式为：(3)其中countt(wi,wj)表示wi,wj在训练语料料中同现的次次数。最大似然估计计可以计算出出训练语料中中出

34、现过的NN元组对应的的Trigrram参数，但但如果我们碰碰到没有出现现过的N元组组怎么办呢？最简单的办办法是认为那那些参数为00，但这样做做会导致系统统的适应能力力很低，一旦旦碰到未出现现过的N元组组，系统就基基本上处理不不了。为了解决这一一问题，Laaplacee提出了一种种简单机制，就是给每个N元组，无论其有无在训练语料中出现，都加上1。如下图所示。图2：Lapllace法则则PLap(w1,wn)=count(w1 ,wn)+1/(C+B)C: 训练集中N元组出现的总次数B: N元参数的总个数Laplacce法则可以以粗略解决“0次数”问题，但它它将所有未出出现的N元组组都赋予出现现次

35、数1是不不符合语言模模型的实际情情况的，因为为很多词的组组合（N元组组）其实根本就不存在在。Lidstoone在Laaplacee的基础上又又做了一点改改进，他给所所有N元组加加上的不是整整数1，而是是一个待确定定的小数。如下图所所示。图3：Lidsstone法法则PLid(w1,wn)=count(w1 ,wn)+B/(C+B)C: 训练集中N元组出现的总次数B: N元参数的总个数:待确定的小数是一个小于11的小数，可可以在通过如下方方式训练得到到：将训练语语料分为2部部分A和B，首首先用A对NN元模型进行行训练，然后后对B进行预预测，调节直到1，使得对B的的预测达到最最佳；然后用用B作训练

36、，AA作测试，调调节直到2, 使得对AA的预测达到到最佳；最终的值为为1和2的算术平均均值。2.1.2.22参数平滑Laplacce和Liddstonee法则仅仅是是对“0次数”问题的一个个粗糙的解决决方式，它们都无法针针对不同的NN元组做出不同的预预测，我们需需要更为细致致的参数平滑滑算法来帮助助我们进行参参数估计。从机理上划分分，目前的参参数平滑算法法可以分为折扣扣法（Discouuntingg）、回退法（Back-ooff）和插插值法（Innterpoolatioon）。在这这里我们只介介绍其中的回回退法。回退法是最常常用的一种平平滑算法，它它的基本思想想是当高阶参参数不存在时时，回退到

37、低低阶参数，当当然，为了保保证每一阶参参数的总和要要为1，对于于那些存在的的参数要进行行一些减弱。我们以Moddifiedd Knesser-Neey Smooothinng为例来介介绍回退法，这这种平滑方法法被认为是对对于N元模型型最有效的平平滑算法之一一，也是本文文所实现的系系统中所实用用的方法。Modiffied KKneserr-Ney Smootthing算算法见图4。从图4中我们可可以看出，对对于已经存在在的N元组，Modified Kneser-Ney Smoothing根据他们出现的次数给出不同的消减，对于不存在的N元组，它根据一定的比例回退到低阶参数，而低阶参数的计算和高阶类

38、似，可以回退到更低阶。值得注意的是Modified Kneser-Ney Smoothing对于一元参数的计算方法，它没有使用语料中的绝对统计数目，而是用和它相邻的不同的一元组的数目，这样可以避免如下的错误回退发生：假设词组AB在语料中出现的频度很高，但是对于B而言，它只出现在A的后面，也就是p(B|A)=1，这样如果统计B的出现频度，是很高的，而当我们计算某个p(B|C)时，显然语料中找不到CB这个词组，因而回退到p(B)，而p(B)的值是很大的，这样就形成了一种误导。而如果我们用B左边出现的不同词的个数作为一元概率的统计基础，那么B左边只有A这一个词，个数为1，当我们再回退到B时，就不会出

39、现很高的概率，从而避免了这种误导。图4：Modiified Kneseer-Neyy Smooothingg其中： nx为次数为x的n元组的个数2.2 隐马尔尔可夫模型2.2.1 定定义隐马尔可夫模模型（Hiddden MMarkovv Modeel）是自然然语言处理和和语音识别中中又一非常常常用的数学模模型，它于220世纪600年代末被BBaum提出出，在70年年代处被CMMU的Bakker第一次次用于语音识识别，其后慢慢慢流行开来来并被用于自然语语言处理的一一些领域中。它假设在观测测现象的背后后有一系列隐隐藏的状态，观测序列是是由这些隐藏状状态序列所生生成，其定义义如下图所示示。图5：隐马

40、尔可可夫模型隐马尔可夫模型可表示为一个五元组： (x , o, A, B, )其中： x = q1,., qn：隐状态的有限集合 o = o1,.,om：观测现象的有限集合 A = aij，aij = p(Xt+1 = qj |Xt = qi)：转移概率 B = bik，bik = p(Ot = ok | Xt = qi)：输出概率 = i， i = p(X1 = qi)：初始状态分布和隐马尔可夫夫模型相伴随随的一般有三三项假设：马尔可夫假假设、不动性性假设和输出出独立性假设设。马尔可夫假假设是假设状状态序列满足足一阶马尔可可夫性，即某某一状态序列列出现的概率率只和它前面面一个状态相相关，这点

41、和和二元模型是是一致的；不动性是状状态的转移和和时间无关；独立性性是某一观测测现象只和当当前状态相关关。如果我们们用O1 ,O2,OT表示观测序列列，X1 ,X2,XT表示状态序列列，这三项假设设可以用下图图表示。图6：隐马尔可可夫假设马尔可夫假设： p(Xi|Xi-1X1) = p(Xi|Xi-1)不动性假设： p(Xi+1|Xi) = p(Xj+1|Xj)，对任意i,j成立输出独立性假设： p(O1,.,OT | X1,.,XT) = p(Ot | Xt) 2.2.2 和和HMM相关关联的三个问问题和N元模型一样样，在给出了了定义之后，我我们自然想到到如何去训练练和使用它。一一般而言，和和

42、隐马尔可夫夫模型相关的的有三个经典典问题：评估估问题，解码码问题和学习习问题。以下下我们将分别别介绍。2.2.2.11评估问题（前向算法）评估问题是给给定模型，求某一观测序列O1,.,OT的概率。为了简化这这个问题，我我们首先假设设观测序列是由状态态Q=q1,qT生成的，在在这个假设下下，观测序列列的概率为：（4）而给定，状态态序列Q=qq1,qT的概率为：（5）由于我们并不知知道观测序列列是由哪一种种状态序列所所生成，我们们必须考虑所所有的情况，也也就是：（6）公式6给出了计计算观测序列列的方法，但但从公式中我我们可以看出出，其时间复复杂度很高，假假设状态空间间长度为N，qq1,qT有NT种

43、可能组合合，而总的时时间复杂度将将为：指数级复杂度的的算法在实际际应用中一般般是无法实现现的。为此我我们引入动态态规划来缩减减计算量，由由于HMM中中的状态的转转移概率只和和其前一状态态相关，这给给我们的计算算带来了很大大好处。我们们定义前向变变量it为：给定模型型，在t时刻状状态为Si的部分观测序O1Ot的概率。用公公式表述如下下：（7）基于it，kt+1可以计计算为：（8）这是一个迭代公公式，其初始始值为：（9）而我们最终所要要得到的结果果为：（110）而对于公式100的迭代计算算，在每一个个观测值我们们要考虑所有有N个状态，对对于每个状态态我们需要考考虑其前面NN个状态，那那么总的时间间

44、复杂度为NN*N*T=N2*T，大大大小于先前的的NT*2T，这这个复杂度是是可以实现的的。2.2.2.22解码问题（韦特比比算法）解码问题就是是给定，模型型和观测序列列，找到最可可能的状态序序列。这个问问题也是HMM在大大多数实际应用中的运作方式。比比如对于词性性标注，我们们把词看作观观测序列，词词性看作状态态序列，标注注的过程就是是找到最可能能的状态序列列的过程。对对于解码问题题的精确数学学描述如下：（11）事实上解码问问题和评估问问题很相似，评评估是计算所所有可能的状态序列产生生的观测序列的的概率的总和和，而解码则则是从这些状状态序列中挑挑出最有可能的的，也就是概概率最大的。和评估问题类类似，如果我我们遍历所有有可能的状态态序列，计算算的时间复杂杂度会很高，我我们同样采用用动态规划来来解决解码问问题。我们定定义it为t时刻到到达状态i的的最优路径（状状态序列）：（12）这样在t+1时时刻到达状态态k的最优路路径为：