基于CRF的中文命名实体识别方法研究

《基于CRF的中文命名实体识别方法研究》由会员分享，可在线阅读，更多相关《基于CRF的中文命名实体识别方法研究（59页珍藏版）》请在装配图网上搜索。

1、图书分类号UDC注-1271TP391.1密级非密硕士学位论文基于 CRF 的中文命名实体识别方法研究王峰指导教师（姓名、职称）申请学位级别专业名称王召巴 教授工学硕士检测技术与自动化装置论文提交日期论文答辩日期学位授予日期年年年月月月日日日论文评阅人答辩委员会主席注 1：注明国际十进分类法 UDC的分类年月日原 创 性 声 明本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下，独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人承担。论文作者签名

2、：日期：关于学位论文使用权的说明本人完全了解中北大学有关保管、使用学位论文的规定，其中包括：学校有权保管、并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或其它复制手段复制并保存学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交流为目的，复制赠送和交换学位论文；学校可以公布学位论文的全部或部分内容（保密学位论文在解密后遵守此规定）。签名：日期：导师签名：日期：中北大学学位论文基于 CRF 的中文命名实体识别方法研究摘要作为文本信息中的基本信息元素，命名实体是正确理解文本的基础。命名实体识别就是将文本信息中规定的实体识别出来，它在自然语言处理中是一项基础性的工作，在信息抽取，

3、机器翻译，自动问答等领域有着广泛的应用。本文以中科院网络科技监测平台建设为背景，采用条件随机域模型（CRF），研究中文命名实体的识别方法。本文通过分析目前命名实体识别的研究现状，详细阐述了近些年来国内外命名实体识别的评测活动；在分析了马尔克夫模型和最大熵模型的基础上，确立了基于条件随机场模型的研究方案。本文在条件随机场的预处理中，以字的方式作为输入标准，从字的角度来切割文本，以获得更多文本信息的上下文特征；在模型训练中，对不同的模板对文本进行了识别，得到了一个相对较为优化的训练模板，并在训练语料中加入词性的外部特征，通过实验表明，该方法可以弥补训练规模的不足，在一定程度上提高了实体的识别效果。

4、本文针对中科院网络科技监测平台建设的要求，利用 SIGHAN2006 MSRA 的语料库，通过对不同模板的测试，采用模式学习方法对不同词的粒度实体进行识别，自动识别出语料中的命名实体；通过对测试语料的识别，获得实体识别的详细信息，并与正确的人工标记结果进行比较，结果说明了采用 CRF 进行命名实体识别可以取得了不错的识别效果。论文的研究成果为日后实现监测平台准确的进行实体识别打下基础。关键词：条件随机场 命名实体 特征模板 标注集中北大学学位论文Research on Chinese Named Entity Recognition Based onCRFAbstractNamed Entit

5、y Recognition is to recognize specific entities in text. As the basicinformation unit of text, Named Entity is essential to the correct understanding of a text.Named Entity Recognition (NER) is a basic task in natural language processing research,which is widely used in machine translation, informat

6、ion extraction, automaticsummarization and so on. So how to identify named entity has great theoretical andpractical significance.In this paper, firstly, it investigated and summarized the current status of the NameEntity Recognition. And then, it introduced the evaluation strategy for NER, whichana

7、lyzed the current method of the Name Entity Recognition.Detailed description of the conditional random field model, conditional random field isa statistical machine learning methods, it has good performance in labeling and fragmentingthe sequence. Training in the model, we added the part of speech a

8、s the externalcharacteristics of training data.The results show that the training corpus in the externalfeatures can make up for lack of training scale, to a certain extent, improved the entityrecognition.In this article, SIGHAN 2006 MSRA were our corpus. From our research, we couldtest template and

9、 word size from the Named Entity Recognition experience. Through thepattern learning style, it could recognize the named entity in the corpus. We could compareto the result with the true training corpus, which had been manually labeled. As a result, wecould gain the result of the experience to analy

10、ze the validity and feasibility of the model.Finally, from the result of the experiments ,the NER using CRF is feasible. Andsome comments about future works are made.中北大学学位论文Keywords: Conditional Random Field; Named Entity Recognition; CharacteristicTemplate; Tag-Set中北大学学位论文目录1. 绪论1.1 本文的研究背景 . 11.2

11、 命名实体的定义 . 31.3 国内外现状 . 31.4 命名实体识别的评测方法 . 51.5 研究的意义 . 61.6 组织结构 . 82. 相关模型的算法2.1 隐马尔科夫模型 . 102.1.12.1.22.1.32.1.4离散马尔科夫过程. 10隐马尔科夫模型. 10隐马尔科夫模型的基本问题 . 12隐马尔科夫模型的局限性 . 162.2 最大熵模型 . 162.2.12.2.22.2.32.2.4最大熵模型的描述. 16最大熵模型的约束条件 . 17最大熵模型求解. 18最大熵模型总结. 192.3 条件随机场概率模型的形式 . 192.4 模型参数估计 . 212.5 本章小结 .

12、 223. 命名实体识别的思路和方法3.1 命名实体识别的难点 . 23I中北大学学位论文3.2 命名实体识别的主要方法 . 253.3 命名实体识别方法结构的设计 . 273.4 本章小结 . 294. 基于CRF的命名实体识别模型关键问题的解决方案4.1 标记偏置问题 . 314.2 特征的选择 . 334.3 特征模板的定义 . 344.4 文本预处理 . 364.5 本章小结 . 375. CRF实验过程及结果分析5.1 CRF模型实体识别流程 . 385.2 CRF 实验过程及结果. 395.2.15.2.25.2.35.35.4实验环境 . 39不同模板的实现结果分析 . 39加入

13、词性标记实现的结果分析 . 42实验分析. 44本章小结. 45结语. 46参考文献 . 48攻读硕士学位期间发表的论文 . 54致谢 . 55II中北大学学位论文第一章绪论在信息高速发展的今天，人们需要将大量的非结构化的信息数据转换成为结构化的信息数据，才能有效地发现信息之间的内在的结构联系，从而为更进一步的知识体系的服务和拓展做准备。因此，怎样才能从非结构化的信息中抽取出真实世界中存在的具体或抽象的实体，来说明结构化的信息数据是值得深入研究和探讨的课题。本文通过吸取和借鉴国内外在信息抽取方面已取得的相关研究的成果，阐述了在非结构化文本中自动识别实体名的思路及相关技术的方法。本章主要是从命名

14、实体的研究背景入手，阐述了本文研究的目标及意义，并且简明的介绍了研究的过程、思路和组织的结构。1.1 本文研究的背景命名实体识别技术属于信息抽取技术的范畴，并且随着信息抽取技术进步而不断的向前发展。在当今时代，随着计算机的普及以及万维网的迅猛发展，大量的信息仅仅靠纸制的形式已经完全不能满足人们的需求，于是大量的信息被制成电子文档的形式出现在人们的面前或者存放在相关数据库中。在欧洲，很多机构正在致力于此项工作 的 研 究 ， 如 欧 洲 科 学 技 术 与 卓 越 描 绘 （ Mapping of Excellent in Science andTechnology，ME）1一直把机构的科研人员

15、的数量、科研项目、科研水平等作为机构的结构数据进行研究。还有一些类似的前沿研究也取得了不错的研究成果，如研究趋势探测（Emerging Trend Detection ，ETD）2，研究领域描绘（Mapping of ResearchSpecialty）3等。他们获得这些信息的途径主要是通过数据库。但是这类科研要素的获取量比较有限，而且揭示的也只是以文档的外部特征为主，而大量的非结构化的文本内的众多的语义信息未能得到利用。因此，如何从如此巨大的网络信息和科技信息中获取用户需要的信息（知识）是人工智能和Internet研究的一个主题，而其中关键的环节之一就是如何从非结构化的数字文本中自动识别结构

16、化的信息数据。为了从不同的信息源中获取用户不同层次和粒度的信息，于上个世纪的八十年代兴起，着力于解决非结构化数据中结构化信息的识别，人们发明了各种不同的信息获1中北大学学位论文取技术，得到数据间的关联关系，正是在这种背景下产生了信息抽取（InformationExtraction，IE）4。总而言之，随着信息化的发展，旨在发现信息中隐含语义知识，集成，抽取数据资源中语义信息的IE抽取技术得到了更广泛的应用和研究。而命名实体识别（Name Entity Recognition，NER）是信息抽取中非常重要且不可或缺的一步。此外，近些年有许多研究者在NER的研究方面己经进行了许多的研究和实验，并取

17、得了一些卓有成效的成绩，而他们对于该问题的兴趣源于该问题的广阔的应用领域和吸引力5,6。其中，作为这些研究中非常重要且必不可少的关键技术之一的命名实体识别技术，越来越受到人们的重视和关注，迄今为止它己发展成一个相对较为独立的研究领域。这些研究为本论文提供了一定的理论和实践的指导。在国际上，早在 1987 年就由美国国防高级研究计划委员会（the Defense AdvancedResearch projects Agency，DARPA)资助的消息理解系列会议（Message UnderstandingConference，MUC ），这个会议从开始于 1987 年，在长达十年的时间中总共举办

18、了七届7会议。其中在 1995 年 9 月举行的第六届MUC会议中，正式的引入了命名实体评测任务8,9。在MUC的会议中命名实体被定义为：人们感兴趣的特定的专有名词和特定的数量词10。在 1997 年的MUC会议中命名实体任务的定义中，命名实体识别被指明包括了三个具体的任务：时间表示语、实体名、数量表达式的识别。其中实体名包括： 地名、人名、机构名；时间表示语包括：时间短语和日期短语；数字表示语包括：比例值和货币短语。在有关命名实体识别的最新的研究中，许多学者又根据不同的研究需求和应用实践又再次扩大了名实体的范围。在MUC之后，从 2000 年至今，特别是经受了“911”之后的美国，出于对国土

19、安全和国际恐怖主义的极度担忧的考虑，美国国家标准技术局11（NIST）开始资助了一系列的“自动内容抽取” ACE）评测会议。先后文本理解会议（Document UnderstandingConference ,DUC），自动内容抽取会议（Automatic Content Extraction，ACE）等信息抽取领域的国际评测会议，自动抽取新闻语料中出现的实体、关系、事件等内容作为了这些研究会议的主要目标。与同期的MUC相比较，目前的ACE评测主要采用基于误报（标准答案中没有而系统输出中有）为基础的一套评测体系和漏报（在标准答案中有而系统输出中却没有），并且对系统是否具有跨文档处理能力进行评测

20、，而并不会针对某个特定的领域或场景。也在继续着命名实体的识别评测，并提供了相应的评测任2（中北大学学位论文务。在中文命名实体方面，我国对于这方面在不断地加大研究的力度，国家 863 命名实体识别评测小组研究并制定了2004 年度命名实体识别评测大纲121 大纲12，这个大纲详细地介绍了命名实体主要的评测任务:“命名实体的任务由三个子任务组成(命名实体、时间表达式、数字表达式)。被标注的表达式为命名实体(组织、人、地点)、时间(日期、时间)及数量。”1.2 命名实体的定义命名实体（Named Entity ，NE）作为一篇文章中的基本元素，包含了文章的许多内容，往往是正确理解这篇文章的基础，在不

21、能阅读全文的情况下，命名实体识别可以作为一种快速了解该文章主要内容最为快捷的途径。就定义方面，狭义上说，命名实体是指现实世界中抽象或具体的实体，如人、组织、地点、公司等。通常用唯一的标识符（专有名词）表示，如人名、组织名、地点名、公司名等。广义上说，命名实体还可以包含数量、时间表达式等。总之，对命名实体而言，可以视具体的情况而定。而命名实体识别（Name Entity Recognition，NER）是指识别出文本中特定的实体。它对于中文信息处理来说是一项很有价值技术。1.3 国内外现状在国际上对于英文命名实体识别的研究比较早，而且在英文命名实体识别方面也取得了很大的成就，其中在MUC会议上的

22、测试的F(评测度量的标准)值最优秀的可以达到 95%左右。Borthwick13在针对英文和日文的命名实体识别中利用了基于最大嫡模型（Maximum Entropy）的方法；Kiyotaka Uchimoto和Qing Ma在IREX竞赛中采用基于最大熵的转移规则的命名实体方法14。Roth实现了一个基于半指导的NE识别系统15则主要借助了句法分析信息帮助NE识别的条件。作者将NE识别问题细分为NE边界划分和NE分类两个不同的过程。第一阶段中从cnostiutneyc和dPenedneyc句法树中抽取候选NE实体并识别而获得训练语料主要是利用了句法分析信息帮助NE识别的条件。在第二阶段，作者则

23、用EM算法进行参数的迭代计算和贝叶斯模型分类器进行分类。在利用3中北大学学位论文ACE语料训练和测试中，证明了constituency和dependency句法约束对NE分析器训练和抽取都是很有必要和可行的。Andrew McCallum对最大嫡马尔科夫模型和隐马尔科夫模型在英文名实体识别中的情况16进行了比较，并阐述了在文本处理中的隐马尔科夫模型的具体应用，隐马尔科夫模型作为一种有限的概率状态模型，其中包括两种参数:某一特定状态的观察概率(发射概率)和状态转移概率。欧盟与 2008 第七框架计划项目OKKAM，就旨在探索一系列与实体相关的技术，为将互联网转换为以实体为节点的网络提供基础，其中

24、就涉及了实体名称的规范问题；美国OCKC积极地与Illions大学17，马里兰州大学开展合作，解决命名实体的识别和排岐问题，为构建规范文档提供基础支撑；保加利亚的OntoText18公司在构建KIM语义知识库时也重点关注了实体名称问题；与国外大规模的开展的实体识别项目相比。目前，中文实体识别的研究才开始不久，与英文实体相比，汉语命名实体的识别任务要复杂得多，主要表现在：汉语文本没有类似英语文本中空格之类的显示标示词边界的标示符，分词和命名实体相互影响。因此，在中文命名实体识别方面也将面临着更大挑战和难度。新加坡大学提出的中文NE的识别方法19 主要是基于多重主体结构推理模型。中文命名实体的识别

25、过程被分成了两个阶段。第一阶段它会使用NE的推理模型和贪心算法来提取文档中所有的待选命名实体并进行评价。接着对于命名实体过程中概率最大的过程作为一个多重主体协商问题来处理。这种方法能对很多复杂NE的识别，在准确率上有很大幅度的提高，但系统的迭代过程太多，计算量很大，导致运行效率不高，运行时间很长。Yu20的识别系统利用语义标记、词性标注和命名实体列表等信息，构建了一个包含基于语言学识别模块和基于上下文识别模块识别系统。经过测试，系统的F值可以达 86.38%。但是由于对语言学的过度依赖性的特点，系统的可移植性不强。谭鸿业通过基于转换的方法来识别地名21，取得不过的效果；李建华22利用了基于名用

26、词和中文姓氏统计统计概率的方法对人名进行识别；黄德根则通过统计的方法来识别人名23；俞鸿魁等24通过构造如前缀、后缀、特征词等常用的机构名识别特征，利用不同角色标注，借助多层隐马尔可夫模型的工具，并由此对组织机构名的进行了测试并取得了不错的效果；吴雪军等25对两个标注器利用已标注好的组织机构名语料4中北大学学位论文进行了学习，并构造了两个不同的分类器分别由机构名上下文特征信和组织机构名的内部结构特征信息组成，最后从大规模未标注语料中利用两个标注器进行上下文特征信息和内部特征学习，从而取得机构名特征构造机构名识别知识库，并成功的将co-training机器学习方法应用到组织机构名的识别当中。zh

27、ou26构建了模型系统是基于层叠条件随机场模型(CCRFs)。在本系统中，通过以观察值为条件的低层条件随机场模型为基础，用于一些基本命名实体的判别，当把最终结果传递给高层模型时，高层模型的输入变量将会包含数据和来自低层模型的识别观察值，这样就低层观察值为高层条件随机场模型提供了有效的决策支持，提高了复杂机构名的识别正确率，最后采用约束的forward-backward算法对识别结果进行可信度测试。通过在人民日报语料库上测试的结果F值达到了 92.89%。而后来诞生一种新的模型，条件随机场（Conditional Random Field，CRF）27在命名实体识别方面也取得了不错的效果。CRF

28、是一种以马尔科夫模型为基础的模型的统计方法，它着眼于字的角度，很好的利用了词以及词性的上下文信息的特征，很好利用了外部的特征，因为从字的角度出发理论上可以很好的避免碎片化的形成。而且从字角度出发来发现句子中词的特征，也更加符合中文以字为基础的特征，并且马尔科夫模型很好的解决了隐型马尔科夫模型和最大熵模型存在的一些缺点，如标记偏置等。而在自然语言处理领域马尔科夫模型也得到了很好的应用，如在英文的分词标注、英文短语名词的识别等领域都取得了较好的效果。与国际上的CRF学术研究相比，国内对于CRF模型方面的研究还比较少。1.4 命名实体识别的评测方法主要有两个评价指标来衡量命名实体识别的系统性能:准确

29、率和召回率。准确率是系统正确识别的结果占所有识别结果的比例，召回率是系统正确识别的结果占所有正确结果的比例。两者的计算公式如下：准确率（P）=系统中正确标记的NE个数系统找到的NE总数5（1.1）中北大学学位论文召回率（R）=系统中正确标记的NE个数文档中的NE总数（1.2）准确率是指抽取的信息中正确抽取的比例；召回率则是指正确抽取的信息占应抽取信息的比例。当比较两个不同信息抽取系统的性能时，一般使用这两个指标的综合值：F 度量，即F =（1.3）在上式中：P 为精度；R 为召回率； 为对精度的偏重量。其中， 决定了 R 和P 的重要程度。若 =1，则将 R 和 P 视为同等作用；若 =2，则

30、将 R 的重要度视为 P的 2 倍；若 =0.5，则将 P 的重要度视为 R 的两倍。一般取 =1，本文中后期的评测都将取 =1。在中文命名实体方面，BAKEOFF-328-30提供的命名实体评测分为简体文本和中文文本两类，简体语料有微软亚洲研究院（MSRC）和LDC（Linguistic Data Consortium）提供，繁体语料由香港城市大学（CITYU）提供，评测分为Open Track和Closed Track两种类型，共有 16 个系统参加了BAKEOFF-3 的命名实体识别的测试，表 1 提供了 6个测试类别最好的测试性能指标。表 1.1BAKEOFF-3 命名实体识别六个评测

31、任务中性能最好测试指标数据来源MSRC（简）LDC（简）CITYU（繁）测试类别ClosedOpenClosedOpenClosedOpenP0.89940.92200.80260.76160.91430.8692R0.84200.90180.72650.66210.86760.7496F0.86510.91180.76270.70840.89030.80516（ 2 +1） *P*R( 2 * P ) + R中北大学学位论文1.5 研究意义通过对背景以及国内外现状的介绍，可以发现从海量的数据中获取识别出中文命名实体，以满足对于知识数据挖掘的需求，为自然语言处理的其他方面提供知识支持，是整个

32、IE 抽取的基础。具体而言，该研究主要有以下几方面的重要意义。（1）信息检索(Information Retrieval):命名实体是文本中信息中的主要载体，准确的分析和抽取文本中的命名实体，能够更准确的检索到相应的文档信息，从而使得信息检索的结果更加准确。（2）开放域问答（Open-Domain Question Answering）：在许多开放域问答系统中，在很多情况下需要得到信息数据中的某个机构，地点，时间等具体的问题，而普通分词结果是很难满足要求的，而只能返回到原文档信息进行人工获取。而命名实体识别就能够很好的帮助开放域问答客服这种困难，他对文本中的这些实体信息进行了识别，使得系统能够

33、获取更准确的答案。（3）机器翻译（Machine Translation）：在机器翻译时，由于主要是通过词语对齐来进行翻译，在遇到机构名、地名等实体时，因此导致翻译的结果常常出现偏差，甚至有可能出现错误。但是通过加入实体识别之后，这样就能使机器翻译的时候的英汉对照能够达到短语级别，从而使翻译的语句更通顺，从而避免错误。（4）按照MUC-7 的规定，在自然语言处理中，信息抽取过程主要包含 3 个不同的层次（由易到难）的任务：模板元素（Template Element ,TE）任务，模板元素主要的任务就是指提取文本中相关的命名实体，主要包括机构名，地名，人名的识别；模板关系（Template Re

34、lation，TR）任务，是指提取命名实体之间的各种关系，脚本模板（Scenario Template, ST）任务，提取出事件模型，包括事件中的各个属性，关系和实体13。而命名实体识别时上面所说的TE的关键技术，是整个信息抽取的基础，其准确率直接影响了接下来进行的TR和ST任务的质量。本文以中科院网络科技监测平台建设课题为研究背景，在整个平台的建设中，命名实体识别作为自然语言处理的一个基础性工作在整个信息抽取占据着举足轻重的位置，它对于文本数据的知识获取，它是展开其他工作的基础，对于信息处理平台的构建，信息资源的检索以及整合等研究产生了深远的影响。因此，本文的研究任务大致7中北大学学位论文的

35、可以分为以下 3 点：（1）对中文命名实体识别的各种方法进行研究，对比找出最优或较优的方法进行实验，为今后进行进一步中文命名实体识别研究做好理论基础的准备。（2）由于条件随机场作为目前学术界公认较优的机器学习方法之一，本研究将使用条件随机场模型去尝试着解决中文命名实体识别中存在的问题，通过构建一个基于条件随机场模型的识别系统，根据模型的训练和测试各方面的因素对系统进行设计和调优，最终完成一个能够识别中文命名实体的命名实体识别系统。1.6 组织结构本论文旨在探索自动，准确的识别非结构化文本信息中的人名，机构名和地名的技术研究方法，针对一些关键的问题提出适当的解决方案，并且通过相应的实验来验证该方

36、法的有效性和可行性。因此，就本论文需要解决的问题，笔者在这里确定了几个需要突破的关键环节。研究的原因研究的现状理论的基础及关键问题解决实验和分析研究是什么？以及展开这个研究的原因该研究的相关理论和技术方法有哪些?研究的难点在哪里？研究主要解决方案模型有哪些？具体的理论基础是什么？研究选择的模型的理论及模型的设计流程提出总体设计方案，验证其可行性和有效性研究背景，问题，意义和目标探讨研究的现状，明确研究的难点分析模型理论基础，比较模型性能选择最佳技术方法及解决关键问题对语料库进行实验，进行实验分析图 1.1 文本研究思路与以上的研究思路相对应，本论文内容也主要是按照以上五个部分组织，详细阐述了研

37、究的思路和过程，以下将根据这个思路介绍进行编写。8中北大学学位论文第一章 ，绪论。介绍命名实体的研究背景，介绍了国内外的研究现状以及命名实体的相关概念，并且阐述了本文研究的目标及意义。将本文的研究思路和组织结构的形式简要的描述。第二章，相关模型的算法。本章主要介绍了现在比较常用的两种统计模型的算法：隐性马尔科夫模型，最大熵模型，条件随机场模型。隐性马尔科夫模型，最大熵模型，条件随机场模型是目前最常用的解决命名实体识别的三种模型方法，为后文的条件随机场模型的关键问题的解决方案和设计方案的提出打下理论基础。第三章，命名实体识别的思路和方法。本章节简述了中文命名实体识别时的难点，并就研究领域比较主流

38、的解决方法做了介绍，并提出自己对于本模型的设计思想，最后结合了 L-BFGS 的算法对 CRF 模型的模式学习流程的方式进行了解释。第四章，基于 CRF 的命名实体识别模型关键问题的解决方案。针对条件随机场模型，介绍了模型创建时的关键问题解决方案。阐述了特征类型，标注等方面的知识，并对于条件随机场的优点做了一定的描述。第五章，实验过程及结果分析。本章以第三、四章的理论和实践为基础。选取有效的模板，对实验结果进行了统计分析和计算，论证了条件随机场模型对中文命名实体识别的可行性。总结本论文的主要工作，研究成果，对实验中不足之处提出了改进意见，并对后续性的研究工作进行了展望。9中北大学学位论文第二章

39、 相关模型的算法在本文中将以统计的方法为主，对中文命名实体进行了识别研究。本章主要介绍了隐形马尔科夫模型、向前算法、Viterbi 解码算法、最大熵模型，比较了这几个模型之间的优缺点，这样有助于更好的理解模型，对日后的命名实体工作进行扩展打下坚实的理论基础。2.1 隐马尔科夫模型隐性马尔科夫模型的基本理论形成于上世纪 60 年代末期和 70 年代初期，是建立在俄国有机化学家 Markovnikov 提出的马尔科夫模型的基础上提出的。其数学本质是一个随机过程，在若干年之后重新受到欢迎。主要是基于它内在丰富的数学理论结构。因此在描述隐性马尔科夫定理之前，先简单介绍一下离散马尔科夫定理。2.1.1

40、离散马尔科夫过程设 Q 表示随机过程qt , t T 的状态空间，S1, S2 , S3.Sn 表示有 N 个不同的随机过程的状态， ai j 表示状态 Si到S j 的转移概率。当随机过程满足：Pqt = Si | qt 1 = S j , qt 2 = Sk ,. = Pqt = Si | qt 1 = S j （2.1）这个就是马尔科夫或无后效性指当前状态只依赖于过去有限的已出现状态历史，即过程“将来”的情况与“过去”的情况是无关的。可以用转移状态 ai j 来表示aij = Pqt = Si | q t 1 = S j （2.2）2.1.2 隐马尔科夫模型隐马尔科夫模型31是一个双重马

41、尔科夫随机过程，它是一个隐含的随机过程，这个序列本身对于观察者是不可见的，但是它可通过一个可见序列得到这个隐含的序列的概率，这其中就包括了状态转移概率的马尔科夫链和输出观测值的随机过程。由于其状态是不确定或不可见的，只有通过观测序列的随机过程才能表现出来，因此而称之为“隐”马尔科夫模型，即HMM。它包含隐马尔科夫模型主要有 5 个因素组成：10中北大学学位论文（1）N，表示马尔科夫模型的状态数。模型中的各个状态之间是相互连结的，任何状态能从其他状态到达， S表示模型中的状态 S1, S2 , S3.Sn 的集合， qt 表示qt , t T 的状态空间。（2）O，表示每个状态的观察值，M 为每

42、个状态对应的可能观察符号，即输出可观察的字符个数。观察值对应于模型系统的实际输出，记这些观察值为：V = v1, v2 ,.vm。（3） A = aij ，状态转移概率矩阵，其中 aij = P(qt = Si | q t 1 = S j ) ，1 i, j N 。 aij表示从状态 i 转移 j 的概率。当状态 Si 经过一步到达 S j 时， aij 满足： aij 0, i, j ;且 aij = 1, i 。（4） B = b j (k ) ，观察值概率分布矩阵，其中 b j (k ) 表示在状态下，t 时刻满足的概率，即 b j (k ) = P （在 t 时刻出现 vk | qt

43、= si ）， 1 j N ,1 k M 。 b j (k ) 满足：b j (k ) 0, j, k ；且 b j (k ) = 1, j 。k（5） = i，初始状态分布矢量，其中 i = P(q1 = Si ),1 i N ，即在t=1 时刻处于状态Si的概率。 i 满足： i = 1。i首先从最简单的离散 Markov 过程入手，可以发现，一个 HMM 是一组有限的状态，Markov 随机过程具有如下的性质：在任意时刻，从当前状态转移到下一个状态的概率与当前状态之前的那些状态没有关系，以下是一个 HMM 的组成示意图。马尔科夫q1, q2 , q3.状态序列随机过程o1, o2 , o

44、3.观察值图 2.1 HMM 组成示意图11中北大学学位论文所以，这里可以用 = ( A, B, ) 来表示一组完整的隐性马尔科夫模型。给定 = ( A, B, ) ，观察序列 O = O1O2O3.Ot 可以由下列的步骤产生：（1） 根据初始状态概率分布令 = i ，选择一个初始状态 q1 = si ；（2） 设 t=1；（3） 根据状态 Si 的输出 bi (k ) ,输出Ot=Vk 。（4） 根据状态转移概率分布 aij ，转移到新的状态、（5） 设 t=t+1。如果 tT，重复（3）（4），否则结束。2.1.3 隐形马尔科夫模型的基本问题1 预测问题如何从观测序列 O = O1O2O3

45、.Ot 以及隐形马尔科夫模型 = ( A, B, ) 快速的计算出观测序列的概率 p(O | ) 是首相要解决的问题。对于一个观测序列来说最简单的方法就是观察序列长度为T，从而枚举观察序列O所有可能的输出状态。假设状态数为N，那么就会导致计算量为 2T*NT，这种方法会耗费大量的资源，因此不可行。目前主要采用forward-backward的方法解决优化此类问题。首先，这里定义在时间t时刻的输出字符是 O = O1O2O3.Ot 并且位于状态Si的概率是 a(i) = P(O1O2 .Ot , qt = si | ) ，先前算法主要是通过前一状态的值以及概率分布计算Ni =1察到序列 O =

46、O1O2O3.Ot 的概率。其次马尔科夫存在 3 个假设：（1） t 时刻的状态只依赖于 t-1 时刻的状态；（2） t 时刻所生成的值只依赖于 t 时刻的状态；（3） 状态与具体的时间无关；根据以上条件，这里可以用动态规划推导出向前变量 at (i) ，即该算法通过将时间t+1 的向前变量表示为在时间 t 时刻向前变量 at (1), at (2),., at ( N ) 值递归的方式的出来，向前算法的推导步骤如下：12出后一状态的值，从而求得 ( | )p o 。其中 ( | ) ( )Tp o a = i 表示的是所有状态 下观tq中北大学学位论文（1） 初始化：（2） 归纳计算：Ni

47、=1O , qa1 (i) = ibia j (t + 1) = P(O1O2 .Ot +1, qt +1 = s j | )N(t )ai =1（2.3）（2.4）= P(o | )aijb j (Ot +1 )由以上可知forward算法统计 P(O | ) 的算法复杂度时，需要得到每个 ai ( j) 的和，而1 j N ,1 t T ，所以复杂度为N2*T，远小于直接计算所用的复杂度。同理根据forward的算法，可以很轻松的推导出backward的。同样，这里假设在时间t状态为st的条件下，变量 t (i) 为：t (i) = P(Ot +1Ot + 2 .OT | qt = si , )通过递归可以得到：Nj =1综上所述，以上可以用一个图示更好的解释以上算法模型：13（2.5）（2.6）= P(O1 2 .Ot t = si , qt +1 = s j | )P(Ot +1 | qt +1 = s j , )= ai ij b j (Ot +1 )中北大学学位论文S1S2S3。a1ia2ia3ia2iai2ai3aiN。S1S2S3SNat1(j)