汉语词与句子切分技术及机器翻译评估方法探讨14884.docx

分类类号 密级级UDC 编号中国科学学院研究究生院硕士学位位论文汉语词与与句子切切分技术术及机器器翻译评评估方法法研究 刘丁丁 指导教师师 宗宗成庆 研究员员 博士士 中国国科学院院自动化化研究所所 申请学位位级别 工学硕硕士 学学科专业业名称 模式识识别与智智能系统统 论论文提交交日期 20004年66月 论论文答辩辩日期 20004年年6月 培培养单位位 中国国科学院院自动化化研究所所 学位授予予单位 中中国科学学院研究究生院 答辩委委员会主主席Approaches to Chinese Word Analysis, Utterance Segmentation and Automatic Evaluation of Machine TranslationDissserttatiion Subbmitttedd tooInsttituute of Auttomaatioon, ChiinesseAccadeemy off Sccienncessin pparttiall fuulfiillmmentt off thhe rrequuireemenntsfor thee deegreee oofMastter of EnggineeeriingbyDinggLiuu(Pattterrn RRecoogniitioon aand Inttellligeencee Syysteem)Dissserttatiion Suppervvisoor: Proofesssorr Chhenggqinng ZZongg独创性声声明本人声明明所成交交的论文文是我个个人在导导师指导导下进行行的研究究工作及及取得的的研究成成果。尽尽我所知知，除了了文中特特别加以以标注和和致谢的的地方外外，论文文中不包包含其他他人已经发表表或撰写写过的研研究成果果。与我我一同工工作的同同志对本本研究所所做的任任何贡献献均已在在论文中中作了明明确地说说明并表表示了谢谢意。签名：_导导师签名名：_ 日 期：_关于论文文使用授授权的说说明本人完全全了解中中国科学学院自动动化研究究所有关关保留、使使用学位位论文的的规定，即即：中国国科学院院自动化化研究所所有权保保留送交交论文的的复印件件，允许许论文被被查阅和和借阅；可以公公布论文文的全部部或部分分内容，可可以采用用影印、缩缩印或其其他复制制手段保保存论文文。（保密的的论文在在解密后应应遵守此此规定）签名：_导导师签名名：_ 日 期：_摘要本论文以以统计模模型为基基础，在参考考了大量量前人工工作的基基础上，对汉语词法分析、口语句子切分和机器翻译评估进行了较为深入的探讨和研究。汉语词法分析是大部分中文处理的第一步，其重要性不言而喻；句子切分是语音翻译中连接语音识别和文本翻译的桥梁，无论语音识别和文本翻译单独的效果有多么好，这座桥没搭好，综合的性能依然无法提高；机器翻译的自动评估是构建机器翻译系统中很重要的辅助工作，其可以加速翻译系统的开发速度，缩短其开发周期。简言之，这三方面同属于自然语言处理的基础的研究领域，其效果直接影响到高层应用的水平。在词法分分析上，我们们利用隐隐马尔可可夫模型型（HMMM）提提出了一一种融和和了分词词、词性性标注和和命名实实体识别别的一体体化词法法分析方方法。最初我我们用基基于类别别的HMMM，其其优点是是对词的的覆盖面面广，系系统开销销小；缺缺点是不不能精确确地预测测词的出出现概率率。为了了提升模模型的准准确率，我我们引入入基于词词汇的HHMM，并并将两者者有机地地结合，并用一个“词到字”的概率平滑方法对基于词的HMM进行平滑。实验结果显示，我们的混合模型由于综合考虑到了字、词、词性以及命名实体的知识，在切分的准确率和召回率上都明显优于单纯基于类别或者基于词的HMM。此外在分词系统的实现上，我们借助对通用分词系统APCWS的整体框架和各功能模块的介绍，讨论了如何有效地存储和加载数据等一些技术细节问题。在口语句句子切分分上，我们提提出了基于双双向N元元模型和和最大熵熵模型的的句子切切分算法法，这种种算法由由于通过过最大熵熵有机地地将正、逆逆向N元元切分结结合起来来，综合合考虑到到了切分分点左、右右的上下下文，从从而得到到了很好好的切分分效果。我我们在中、英英文语料料上训练我我们的模模型并作作测试，结果显显示其在性能能上明显显优于基基本的正正向N元元切分。在在此基础础上，我我们分析析并对比比了各模型型的切分分结果，从从而验证证了我们们当初对于于模型的的预计：其一方面面保存了正向NN元算法法的正确切切分，一一方面用用逆向NN元算法法有效地地避免了了正向算算法的错错误切分分。在机器翻翻译的自动评评估上，我我们首先先介绍了了两种常常用的基基于参考考译文的的评估算算法BLLEU和和NISST，然然后给出出了一种种基于NN元模型型的句子子流畅度度评估方方法E33。这种种方法不不需要借借助任何何参考译译文，它它通过区区别地对对待句子子中不同同的词的的转移概概率，达达到了很很好的评评估效果果。综上所述述，本文针针对汉语语词法分分析、口口语句子子切分和和机器翻翻译评估提提出了以以统计模模型为基基础的创创新方法法，它们们不仅仅仅在科学学方法上上有重要要的参考考价值，对于实际应用中也有重要意义。ABSTTRACCTThiss thhesiis ppropposeed oour novvel staatissticcal appproaachees oon CChinnesee woord anaalyssis, uttterrancce ssegmmenttatiion andd auutommatiic eevalluattionn off maachiine traansllatiion (MTT).WWordd annalyysiss iss thhe ffirsst sstepp for mosst aappllicaatioon bbaseed oon CChinnesee laanguuagee teechnnoloogiees; uttteraancee seegmeentaatioon iis tthe briidgee whhichh coonneectss sppeecch rrecoogniitioon aand texxt ttrannslaatioon iin aa sppeecch ttrannslaatioon ssysttem; auutommatiic eevalluattionn off maachiine traansllatiion (MTT) ssysttem cann sppeedd thhe rreseaarchh annd ddeveeloppmennt oof aa MTT syysteem, redducee itts ddeveeloppingg coost. Inn shhortt, tthe thrree asppectts aall bellongg too thhe bbasiic rreseearcch aareaa off Naaturral Lannguaage Proocesssinng (NLPP) aand havve ssignnifiicannt mmeanningg too maany impporttantt apppliicattionns ssuchh ass teext traansllatiion,speeechh trransslattionn annd sso oon.InChhineese worrd aanallysiis, we proopossed a nnoveel uuniffiedd appprooachh baasedd onn HMMM, whiich effficiienttly commbinne wwordd seegmeentaatioon, Parrt oof SSpeeech (POOS) taggginng aand Nammed Enttityy (NNE) reccognnitiion. Ouur ffirsst mmodeel iis aa cllasss-baasedd HMMM. So aas tto iincrreasse iits acccuraacy, wee inntrooducce iintoo thhe wwordd-baasedd HMMM aand commbinne iit wwithh thhe cclasss-bbaseed HHMM. Att laast we useed aa “wordd-too-chharaacteer” smmootthinng mmethhod forr prrediictiing thee prrobaabillityy off thhosee woordss whhichh doont ooccuur iin tthe traainiing sett. TThe expperiimenntall reesullts shoow tthatt ouur ccombbineed mmodeel, by commpreehennsivvelyy coonsiiderringg thhe iinfoormaatioon oof CChinnesee chharaacteers, woordss, PPOS andd NEE, aachiieveed mmuchh beetteer pperfformmancce iin tthe preecissionn annd rrecaall of thee Chhineese worrd ssegmmenttatiion. Baasedd onn thhe kknowwleddge of oour commbinned moddel, wee deescrribeed tthe dettaills iin iimpllemeentiing thee geenerral worrd ssegmmenttatiion sysstemm APPCWSS. WWe ddisccusssed somme ttechhniccal proobleems in thee daata savvingg annd lloaddingg, aand desscriibedd ouur mmoduuless off knnowlledgge mmanaagemmentt annd wwordd laattiice connstrructtionn.In uutteerannce seggmenntattionn, tthiss paaperr prropoosedd a novvel appproaach whiich wass baasedd onn a bi-dirrecttionnal N-ggramm moodell annd MMaxiimizzed Enttroppy mmodeel. Thiis nnoveel mmethhod, whhichh efffecctivvelyy coombiiness thhe nnormmal andd reeverrse N-ggramm allgorrithhm, is ablle tto mmakee usse oof bboth thee leeft andd riightt coonteext of thee caandiidatte ssitee annd aachiieveed vveryy goood perrforrmannce in uttteraancee seegmeentaatioon. We connducctedd exxperrimeentss booth in Chiinesse aand in Engglissh. Thee reesullts shoowedd thhe eeffeect of ourr noovell meethood wwas mucch bbettter thaan tthe norrmall N-gramm allgorrithhm. Theen bby aanallyziing thee exxperrimeentaal rresuultss, wwe ffounnd tthe reaasonn whhy oour novvel metthodd acchieevedd beetteer rresuultss: iit oon oone hannd rretaaineed tthe corrrecct ssegmmenttatiion of thee noormaal NN-grram alggoriithmm, oon tthe othher hannd aavoiidedd thhe iincoorreect seggmenntattion by makkingg usse oof rreveersee N-graam aalgooritthm.In aautoomattic evaaluaatioon oof MMT ssysttemss, wwe ffirsst iintrroduucedd twwo cclasssicc meethoods on auttomaaticc evvaluuatiion whiich relliedd onn reeferrencce ttrannslaatioons. Thhen we proopossed ourr noovell seenteencee flluenncy evaaluaatioon mmethhod bassed oon NN-grram moddel. Thhis metthodd, ccallled as E3, dooesnnt nneedd anny rrefeerennce traansllatiionss annd aachiieveed vveryy weell evaaluaatioon pperfformmancce bby ddisccrimminaatelly uuse thee diiffeerennt ttrannsmiissiion proobabbiliitiees oof wwordds iin tthe evaaluaatinng ssenttencce. In ssummmariizattionn, tthiss thhesiis ppropposeed nnoveel aapprroacchess foor tthe thrree bassic ressearrchees iin NNLP: Chhineese worrd aanallysiis, uttteraancee seegmeentaatioon aand auttomaaticc evvaluuatiion of MT sysstemms. We bellievve tthe oriiginnal ideeas in theem nnot onlly hhavee immporrtannt rrefeerennce vallue forr ottherr reeseaarchhes, bbut alsso ccan be useed tto iimprrovee thhe pperfformmancce oof NNLP apppliccatiionss.目录第一章绪绪言1第二章统统计语言言模型332.1 N元模模型32.1.1 NN元模型型定义332.1.2参数数估计442.2 隐马尔尔可夫模模型82.2.1 定定义82.2.2 和和HMMM相关联联的三个个问题992.3 最大熵熵模型1132.3.1 介介绍1332.3.2 定定义1552.3.3 参参数训练练172.4 小结200第三章基基于隐马马尔可夫夫模型的的一体化化中文分分词方法法213.1 相关工工作2113.2 基于类类别的隐隐马尔可可夫分词词框架2233.2.1 词词的定义义243.2.2 基基于类别别的隐马马尔可夫夫模型2243.2.3词的生成成模型2263.2.4 基基于类别别的隐马马尔可夫夫模型的的小结2293.3 对于基基于类别别的隐马马尔可夫夫模型的的改进2293.3.1 基基于类别别和基于于词的隐隐马尔可可夫模型型的合并并303.3.2 “词到字字”的平滑滑方法3313.4实实验3223.4.1 训训练和测测试语料料323.4.2 各各模型的的测试结结果323.4.3错误分分析3443.5 通用分分词系统统APCCWS实实现介绍绍353.5.1 AAPCWWS系统统框架3353.5.2 AAPCWWS的数数据装载载以及知知识管理理363.5.3 AAPCWWS的切分模模块4003.6 小结455第四章基基于双向向N元模型型和最大大熵模型型的句子子切分4464.1 相关工工作4774.2 最大熵熵平衡的的双向NN元切分分算法5504.2.1 正正向N元切分分算法5504.2.2 逆逆向N元切分分算法5514.2.3 双双向N元切分分算法5524.2.4 基基于最大大熵模型型的切分分算法5534.2.5最大熵熵平衡的的双向N元切分分算法5544.3 实验5664.3.1 训训练和测测试语料料564.3.2 实实验结果果564.3.3 结结果分析析584.4 小结599第五章机机器翻译译自动评评估方法法研究6605.1 相关工工作6005.2 基于参参考译文文的评估估方法6625.2.1 BBLEUU (BBiliinguual Evaaluaatioon UUndeersttudyy)算法法625.2.2 NIIST算算法6335.2.3改进的的NISST算法法645.3基基于统计计的句子子流畅度度评估方方法6555.3.1 基基于N元模型型的句子子流畅度度评估6655.3.2 实实验6885.4 小结722第六章结结论733参考文献献75附录1：本论文文的研究究工作得得到如下下项目资资助811附录2：攻读硕硕士学位位期间发发表的论论文811致谢822第一章 绪言近十几年年来，随随着计算算机硬件件设备的的飞速发发展，其其单位存存储和计计算成本本大幅度度降低，使一些基于大规模搜索和迭代的复杂算法能够在PC上广泛地实现和应用；而随着行业信息化的普及和网络资源的迅猛膨胀，可用语料资源也大为丰富，这一切给基于大规模语料库的统计自然语言处理提供了所需的硬件和软件环境。统计自然然语言处处理以数数学模型型和大规规模语料料库为基基础，其其核心思想是是建立数数学模型型以表述述某一种种语言现现象，然然后在大大规模语语料库中中对那种种模型进进行训练练，使其其满足已已经获知知的经验验知识，然然后用训训练好的的模型对对于未知知的现象象进行预预测。几几乎所有有基于统统计的方方法都可可以归结结到上述述的框架架中去。相相比传统统的基于于规则的的自然语语言处理理，统计计方法有有如下好好处。第一， 它不依赖赖于人主主观的先先验知识识，这也是是本文认认为统计计方法最最重要的的优点。大大规模语语料库实实际上和和规则一一样，都都是一种种知识的的表征形形式。不不同的是是语料库库相比规规则而言言，有更更强的独独立性和和客观性性。大家家知道，规规则往往往是针对对某一特特定的应应用，由由某方面面的专家家按照一一定的形形式所书书写的指指导原则则，它是专专家在自自己的经经验基础础上对语语言现象象的一种种总结，具具有很强强的主观观性。往往不不同的专专家所书书写的规规则会有有不同，甚甚至同一一位专家家在不同同时候所所写规则则也会有有出入，而而随着规规则的不不断增加加，新旧旧规则之之间会产产生矛盾盾，当规规则的数数目达到到一定程度以后后往往就就不可能能再增加加新的规规则了。而而语料库库很简单单，任何何一篇电电子文档档都可以以成为一一个小的的语料库库，即使使对于那那些经过过人工处处理后的的熟语料料，由于于大家是是在一定定规范地地约束下下进行的的，那些些规范相相对而言言都是比比较简单单和机械械的规范范，所以以人的主主观影响响会小得得多，即即使在某某些个别别的词或或句上出出现矛盾盾，也不不会对整整体造成成很大影影响。第二， 统计方法法相比基基于规则则的方法法有更强强的鲁棒棒性。规规则的方方法是离离散的，一一条规则则只能总总结有限限数目的的语言现现象；而而统计模模型是连连续的，它可以以对全部部的现象象进行描描述。规则是是人对于于经验知知识的一一种抽象象，这种种抽象是是零散的的，它并并不保证证所有的的规则的的总和可可以描述述全部的的语言现现象，所所以每遇遇到一个个不能处处理的实实例，我我们必须须增加新新的规则则以满足足需求。而而统计模模型所依依赖的语语料库虽虽然也是是离散的的，语料料库中包包含的现现象也只只是全部部现象的的一个真真子集，但但由于我我们是用用严密的的数学模模型来对对现象进进行的抽抽象和归归纳，它它就可以以保证训训练出的的模型适适用于所所有的实实例，从从而保证证了强的的鲁棒性性。当然，不同同的统计计模型对对现象描描述的准准确程度度是不一一样的。第三， 统计方法法将知识识和算法法分离。前文已已提过，规规则往往往是由某某方面的的专家针针对某一一特定的的应用所所书写的的指导原原则，而而同一个个语料库库可以为为多种算算法、多多种应用用服务，它它是很独独立的知知识库。这这样语料料库的建建立和完完善可以以和算法法的设计计并行，不仅节节省了人人力物力力，也给给一些标标准化测测试提供供了基础础。另外外这项优优点给基基于统计计方法的的系统的的维护和和更新带带来了很很大的方方便。随随着应用用的扩展展，我们们往往要要考虑到到新的语语言现象象，这时时基于统统计方法法的系统统只需要要用更大大的语料料库重新新训练一一下模型型就可以以了，而而基于规规则的方方法则需需要增加加大量的规规则，而而如上文文以前提提过的，这这并非一一件容易易的事情情。正是由于于这些优点点，统计计方法在在近十年年来得到到了飞速速发展，它逐步取代传统基于规则的方法，成为自然语言处理领域的主流技术。在中文处处理方面面，统计计方法已已经有很很多成功功的应用用，如词词性标注注、音字转转化及拼音输输入等，但但由于汉汉语本身身的复杂杂性和灵灵活性，有有很多问问题依然然尚待解解决。本本文试图图以统计计模型为为基础，研研究汉语语自动分分词、分句及机机器翻译译自动评评估的解解决方法法。分词词是大部部分中文文处理系系统的第第一步，其其重要性性不言而而喻；句句子切分分是语音音翻译中中连接语语音识别别和文本本翻译的的桥梁；而机器器翻译的的自动评评估可以以提高一个个机器翻译译系统的的开发速速度和节节约其成成本。简简言之，这三类问题同属于中文信息处理领域的基础研究课题，它们的效果直接关系到其他高层应用，所以我们的研究不仅仅在科学方法上有重要的参考价值，对于实际应用也有重要意义。后面的的章节是是这样安安排的：第二章章介绍三三种常用用的统计计模型，这这是本文文所提出出的方法法的理论论基础；第三章章介绍基基于隐马马尔可夫夫模型的的一体化化汉语分分词方法法；第四四章介绍绍基于NN元模型型和最大大熵模型型的句子子切分方方法；第第五章介介绍基于于N元模模型的句句子流畅畅度评估估方法；第六章章对全文文进行总总结。第二章统计语语言模型型本论文的的所有工作作均是基基于统计计方法，因因此在本本章里，我我们将介介绍一些些常用的的统计模模型。其其构成了了我们的的方法的的理论支支撑。统计模型型是一种种抽象的的数学模模型，用用来对事事物进行行一种近近似的描描述，它它首先假假设某类类现象满满足一种种模型，然然后用已已知的现现象实例例对模型型进行训训练，以以得到模模型的相相关参数数，然后后用这个个训练过过的模型型来预测测未知的的现象。对对于自然然语言处处理而言言，最常常用的有有N元模模型、隐隐马尔可可夫模型型、最大大熵模型型等。2.1NN元模型型2.1.1 NN元模型型定义N元模型型是自然然语言处处理中最最常用的的一种数数学模型型。它的的定义如如下。图1：NN元模型型的定义义假设序列w1w2wm是一个N阶马尔可夫链，那么某一元素wi出现的概率只和其前面N-1个元素相关，即：（1）如果我们们假设语语言也满满足马尔尔可夫性性，那么么某一个个词在某某个句子子中的出出现概率率就可以以用公式式(1)进行计计算，进进而一个个句子的的概率可可以计算算为：(2)一般N越越大，模模型越精精确，但但所用参参数和所所需要的的训练集集也越大大（如果果训练集集不够大大将导致致严重的的数据稀稀疏问题题）。假假设词汇汇量为1100K（实实用中文文系统的的词汇量量），下下表给出出了不同同的N元元模型的的参数形形式以及及所用的的参数数数目。表1：NN元模型型实例及及参数个个数模型参数参数个数数0-grramp(w)=1/|V|11-grram(uniigraam)p(w)1e52-grram(biggramm)p(wii|wi-1)1e1003-grram(triigraam)p(wii|wi-2 wwi-11)1e1554-grram(tettraggramm)p(wii| wwi-33 wi-22 wi-1)1e200在实际运运用中，考考虑到训训练所需需的语料料规模，N一般般取3，也也就是所所谓的TTriggramm。2.1.2参数数估计2.1.2.11最大似似然估计计虽然我们们已经介介绍了NN元模型型的基本本概念，但但要真正正使用它它，还需需要进行参参数估计计这一步步，也就就是将表表1中的的那些参参数计算算出来。以Trigram为例，用最大似然估计计算参数的公式为：(33)其中coountt(wii,wj)表示wi,wj在训练练语料中中同现的的次数。最大似似然估计计可以计计算出训训练语料料中出现现过的NN元组对对应的TTriggramm参数，但但如果我我们碰到到没有出出现过的的N元组组怎么办办呢？最最简单的的办法是是认为那那些参数数为0，但这样做会导致系统的适应能力很低，一旦碰到未出现过的N元组，系统就基本上处理不了。为了解决决这一问问题，LLaplacce提出出了一种种简单机机制，就就是给每个N元元组，无无论其有有无在训训练语料料中出现现，都加加上1。如下图图所示。图2：LLapllacee法则PLap(w1,wn)=count(w1 ,wn)+1/(C+B)C: 训练集中N元组出现的总次数B: N元参数的总个数Lapllacee法则可可以粗略略解决“0次数数”问题，但但它将所所有未出出现的NN元组都都赋予出出现次数数1是不不符合语语言模型型的实际际情况的的，因为为很多词词的组合合（N元元组）其其实根本就不不存在。Liddstoone在在Lapplacce的基基础上又又做了一一点改进进，他给给所有NN元组加加上的不不是整数数1，而而是一个个待确定定的小数数。如下下图所示示。图3：LLidsstonne法则则PLid(w1,wn)=count(w1 ,wn)+B/(C+B)C: 训练集中N元组出现的总次数B: N元参数的总个数:待确定的小数是一个个小于11的小数数，可以以在通过如下方方式训练练得到：将训练练语料分分为2部部分A和和B，首首先用AA对N元元模型进进行训练练，然后后对B进进行预测测，调节节直到1，使得对对B的预预测达到到最佳；然后用用B作训训练，AA作测试试，调节节直到2, 使得得对A的的预测达达到最佳佳；最终的的值为1和2的算术术平均值值。2.1.2.22参数平平滑Lapplacce和LLidsstonne法则则仅仅是是对“0次数数”问题的的一个粗粗糙的解解决方式式，它们都无无法针对对不同的的N元组组做出不同同的预测测，我们们需要更更为细致致的参数数平滑算算法来帮帮助我们们进行参参数估计计。从机理上上划分，目目前的参参数平滑滑算法可可以分为为折扣法法（Disccounttingg）、回退法法（Backk-offf）和和插值法法（Innterrpollatiion）。在这里我们只介绍其中的回退法。回退法是是最常用用的一种种平滑算算法，它它的基本本思想是是当高阶阶参数不不存在时时，回退退到低阶阶参数，当当然，为为了保证证每一阶参数数的总和和要为11，对于于那些存存在的参参数要进进行一些些减弱。我们以以Moddifiied Kneeserr-Neey SSmooothiing为为例来介介绍回退退法，这这种平滑滑方法被被认为是是对于NN元模型型最有效效的平滑滑算法之之一，也也是本文文所实现现的系统统中所实实用的方方法。Moddifiied Kneeserr-Neey SSmooothiing算算法见图图4。从图4中中我们可可以看出出，对于于已经存存在的NN元组，Modified Kneser-Ney Smoothing根据他们出现的次数给出不同的消减，对于不存在的N元组，它根据一定的比例回退到低阶参数，而低阶参数的计算和高阶类似，可以回退到更低阶。值得注意的是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时，就不会出现很高的概率，从而避免了这种误导。图4：MModiifieed KKnesser-Neyy Smmootthinng其中： nx为次数为x的n元组的个数2.2隐隐马尔可可夫模型型2.2.1 定定义隐马尔可可夫模型型（Hiiddeen MMarkkov Moddel）是是自然语语言处理理和语音音识别中中又一非非常常用用的数学学模型，它于20世纪60年代末被Baum提出，在70年代处被CMU的Baker第一次用于语音识别，其后慢慢流行开来并被用于自然语言处理的一些领域中。它假设在观测现象的背后有一系列隐藏的状态，观测序列是由这些隐藏状态序列所生成，其定义如下图所示。图5：隐隐马尔可可夫模型型隐马尔可夫模型可表示为一个五元组： (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)：初始状态分布和隐马尔尔可夫模模型相伴伴随的一一般有三三项假设设：马尔可可夫假设设、不动动性假设设和输出出独立性性假设。马尔可可夫假设设是假设设状态序序列满足足一阶马马尔可夫夫性，即即某一状状态序列列出现的的概率只只和它前前面一个个状态相相关，这这点和二二元模型型是一致致的；不动性性是状态态的转移移和时间间无关；独独立性是是某一观观测现象象只和当当前状态态相关。如果我们用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 和和HMMM相关联联的三个个问题和N元模模型一样样，在给给出了定定义之后后，我们们自然想想到如何何去训练练和使用用它。一一般而言言，和隐隐马尔可可夫模型型相关的的有三个个经典问问题：评评估问题题，解码码问题和和学习问问题。以下我我们将分分别介绍绍。2.2.2.11评估问题题（前向算法）评估问题题是给定模模型，求某一一观测序列O1,.,OOT的概率率。为了简简化这个个问题，我我们首先先假设观观测序列列是由状状态Q=q1,qT生成的的，在这这个假设设下，观观测序列列的概率率为：（44）而给定，状态态序列QQ=q11,qT的概率为为：（5）由于我们们并不知知道观测测序列是是由哪一一种状态态序列所所生成，我我们必须须考虑所所有的情情况，也也就是：（6）公式6给给出了计计算观测测序列的的方法，但但从公式式中我们们可以看看出，其其时间复复杂度很很高，假假设状态态空间长长度为NN，q11,qT有NT种可能能组合，而而总的时时间复杂杂度将为为