HMM和CRFs在信息抽取应用中的比较研究，本文主要内容关键词为：信息论文,HMM论文,CRFs论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
【分类号】TP311
1 引言
随着网络技术的发展普及，人类信息正在逐渐数字化、电子化。到20世纪80年代末出现了“信息爆炸”现象，人们逐渐被“淹没”在信息数据的“海洋”中。如何迅速地从海量信息中获取有用知识，如何充分提高信息利用率，如何解决“信息爆炸”和“知识匮乏”的矛盾，所有这些都是在“海量信息为特征的信息时代”提出的新课题。信息抽取技术是解决上述问题的有效方法。
信息抽取技术一般被分解为5个层次[1]：
(1)命名实体(Named Entity)识别，主要是人名、地名、机构名、产品名等名词性条目，以及日期、时间、数字、邮件地址、货币等专有名词的有效识别和分类；
(2)模板要素(Template Element)识别，即应用模板规则的方法搜索和识别命名实体相关信息，此时处理的通常是一元关系；
(3)模板关系(Template Relation)抽取，即应用模板搜索和抽取实体与实体之间的关系，处理的通常是二元关系；
(4)同指关系(Co-reference)替换，实现指代消解，即解决文本中的代词指称问题；
(5)情节模板(Scenario Template)，即根据应用目标定义任务框架，用于特定领域的信息识别和组织。
信息抽取分为显性知识的抽取和隐性知识的挖掘。显性知识抽取是指基于规则或基于统计的方式[2]实现命名实体及其相关信息的抽取；隐性知识的挖掘则是采用数据挖掘(Data Mining)技术，从文本中提取实体和实体之间隐藏的具有一定可信度的关系。基于统计的方法是指学习经过标注的语料库，获得语言学规律知识，采用一定的统计算法，识别满足指定阈值的命名实体[2]。隐马尔可夫模型(Hidden Markov Model,HMM)[3]和条件随机场(Conditional Random Fields,CRFs)[4]是信息抽取技术中两种常用的概率统计模型，可以有效解决信息抽取中序列标注或对象分类问题。本文试图对HMM和CRFs进行全面剖析，从数学理论、开放性实验以及实践应用中比较两者差异，为选择合理的概率统计模型实现具体的信息抽取工作提供参考依据。
2 HMM和CRFs的理论模型
2.1 隐马尔可夫模型
隐马尔可夫模型是指支持为观察序列从状态集合中选择具有最大可能性(最大概率)状态序列过程的模型。为此引入条件概率P(T|W)，表示词串W在状态串T下的概率，则HMM的目的即为求使P(T|W)值最大的T，记为[5]：
T'=arg＃maxP(T|W)(1)
对P(T|W)使用条件概率公式，根据贝叶斯(Bayes)公式对其进行化简，然后根据HMM独立性假设和二元语义关系，公式(1)最终可化简为：
其中，词语特定状态下概率和状态之间转移概率可以近似地从大规模语料库中统计估算：
于是公式(2)即可以转化为：
HMM算法比较成熟，再加上易于训练等特点被广泛应用于自然语言处理领域。然而又因为HMM是生成模型，尚存在诸多问题：
(1)它没有直接对条件概率P(T|W)建模，而是采用联合概率P(T,W)代替，认为观察值由状态生成；
(2)HMM独立性假设认为当前观察值仅与当前状态相关，忽略了其与之前状态和之前观察值之间的相关性；
(3)仅以生成状态和当前观察值作为决定特征，不易融合各种特征和长距离依赖关系。
HMM上述缺点导致其并不是最适合用于解决序列标注问题的概率统计模型。
2.2 条件随机场
条件随机场(CRFs)是一种典型的序列标注判别模型，是在给定观察序列的条件下，计算整个观察序列状态标记的联合条件概率分布的无向图模型。根据最大熵原理[6]和无向图理论，CRFs的形式可以用一个联合条件概率分布P(T|W)来表示，定义为[7]：
其中，
，使得
。在CRFs中，特征被分为两类：
(1)关于位置为i的观察序列w和状态标记t的状态特征g[,j]；
(2)关于观察序列w中位置为i-1和i的状态标记t的转移特征f[,j]。
特征权重λ[,j]和μ[,j]则可以采用感知机(Perceptron)或GIS(Generalized Iterative Scaling)、IIS(Improved Iterative Scaling)等迭代算法，通过对已知事实进行训练估算出来。
对比HMM，CRFs的特点主要表现在：
(1)公式(6)较之公式(5)其数学模型复杂度明显增大；
(2)与HMM仅集成了2个指定特征，参数训练仅需统计3个频次值相比，CRFs能够在同一个模型中无限制集成不同特征，特别是可加入远距离约束，更能揭示语言学特征，但CRFs集成多种特征生成成千上万个特征函数，导致其权重训练的计算量也是相当大的；
(3)CRFs采用联合条件概率P(T|W)建模，避免了HMM的独立性假设和二元假设，从数学建模角度而言，CRFs较之HMM具有更可靠更合理的数学推导；
(4)CRFs保留了HMM中的之前标记的状态对当前状态标记的影响，使特征的选择更为合理；
(5)HMM是有向图模型，通过Viterbi算法搜索到当前对象为止的最佳路径，不考虑之后对象及其标记概率，而CRFs则采用无向图模型，是对整个标记序列求解联合概率，在整个序列范围内归一化，较HMM具有更合理的数学理论基础，同时也避免了因求解局部观察值概率所带来的标记偏置(Label Bias)[6,8]问题。
根据上述分析，笔者认为，CRFs较HMM更适合于解决序列标注或对象分类问题。下面笔者通过这两种模型在人名实体抽取中具体应用的比较，来进一步验证上述分析。
3 基于HMM的词角色标注人名实体识别
3.1 模型定义
基于HMM的词角色标注人名实体识别模型(Model for Person-Name Recognition Based on Word Role Labeling Using HMM,HMM_WRL_PnR)如图1所示。基本思路是：首先根据训练语料中出现人名的构成规则，定义其构成角色；根据公式(3)和(4)从训练语料中统计词语在特定角色下出现的次数、特定角色的出现次数以及任意两角色之间的相邻次数等计算量；然后采用基于词典的正向最大匹配算法来实现测试文本粗分以形成词观察序列，应用之前从训练语料中获得的统计量，计算观察序列中词语特定状态下概率和状态之间的转移概率，采用Viterbi算法为观察序列搜索最佳角色路径(概率和最大)，获得HMM角色链；最后通过对HMM角色链进行角色拆分后，基于人名模式匹配从词串观察序列中抽取出符合指定模式的人名实体。
下面以“本报合肥1月3日电记者刘杰报道”为例，来说明HMM_WRL_PnR的处理过程。首先对句子进行文本粗分，形成词串序列“本报合肥1月3日电记者刘杰报道”。
3.2 模式化人名识别
图1 基于HMM的词角色标注人名实体识别模型(HMM_WRL_PnR)
如图1所示，根据HMM_WRL_PnR实现中文文本中的人名实体识别，主要有3项工作：
(1)角色定义。考察中文语料中的人名构成，发现中文人名在结构上具有一定的规律：
①中国人名一般最多由4个字(姓+姓+名+名)组成；
②中国人名的组合模式在数量上具有有限性；
③中文人名的前后临界词对人名具有一定的提示作用；
④音译外来人名在翻译用字上具有一定的重复性。
根据上述规律，可以总结出HMM_WRL_PnR中的词角色集合，如表1所示：
(2)角色词典生成算法。根据公式(5)，需要对训练语料库进行统计，总结中文人名的一般语法规律，以便使用这些统计数据估算观察词串的最佳角色链。需要统计的数据包括：各词担任各角色的次数，各角色在训练语料中出现的总次数，以及角色集合中任意两角色之间顺序相邻次数。具体过程如图2所示：
图2 人名角色学习过程
最后统计生成〈词语，角色〉有序对，得到3个人名识别词典：统计词语w[,i]作为t[,i]角色出现的次数，C(w[,i],t[,i])作为词语角色词典；累计所有不同角色的出现次数C(t[,i])作为角色词典；以及统计任意两角色有序相邻的次数C(t[,i-1],t[,i])作为角色转移词典。
(3)模式匹配算法，人名角色模式匹配的实现。前文根据特殊到一般的归纳法，从大规模语料中发现中国人名的一般语法特征；此后即可采用一般到特殊的演绎推理法，认为遵循上述语法特征的角色组合即为中国人名，具体步骤如下：
①应用Viterbi算法，计算经过粗分获得的中文词串相对应的最佳(概率最大或公式(6)的值最小)角色串(HMM链)[5]，如前例的HMM链为“AAAAAAAAABEA”；
②U和V角色是人名角色和一般角色的组合，需要将组合角色及与其对应的词串词wi断裂；
③根据人名角色定义，认为HMM链中任何匹配BBCD，BBE，BBZ，BBG，BCD，BXD，BE，BG，BZ，CD，FB，XD，Y，Z，B，W等角色模式其对应的词语组合即为人名。
4 基于CRFs的字角色标注人名实体识别
4.1 模型定义
根据公式(6)，要计算观察值条件下状态值的联合概率分布，需要构造特征函数并计算其权重。基于CRFs实现序列标注，关键在于解决4个问题：观察值的设定；状态值的定义；特征函数的选择；权重的训练。
基于CRFs的字角色标注人名实体识别模型(Model fOr Person-Name Recognition Based on Character Role Labeling Using CRFs,CRFs_CRL_PnR)如图3所示，基本思路是：首先，对中文文本进行原子切分；其次，基于“字”原始序列衍生观察序列，根据观察序列的取值建立针对人名识别的上下文特征模板，并按模板规则从训练语料中提取特征函数；再根据训练语料中出现的人名构成规则，定义其构成角色集合；利用训练语料中的观察序列和角色序列，基于CRFs训练提取的特征函数的权重以构建用于人名识别的CRFs字角色标注模型，通过调整观察值取值、特征模板个数以及角色集合定义来调节特征函数及其权重以实现最合理的建模；根据建立的模型，计算测试语料中每一个(组)观察值在其上下文环境中被识别为某种角色的联合可信度，并选择可信度最大的角色类别作为观察值的角色标注；最后根据人名实体的角色组合从原始观察序列中抽取出符合指定模式的人名实体。
根据人名识别过程，上述4个关键问题就转化为：
(1)以“字”为单位观察序列组的衍生；
(2)中文“字”角色集合的定义；
(3)根据观察值排列规则，选择一定的观察值组合作为特征函数；
(4)根据训练语料选择特征函数并计算其权重系数。
图3 基于CRFs的字角色标注人名实体识别模型(CRFs_CRL_PnR)
4.2 人名角色的定义
根据3.2节所总结的中文人名构成规则，结合考虑此处对中文单“字”进行角色标注，可以总结出如表2所示的角色(R)集合。
通过对中文字角色的定义，笔者将语料中出现的所有文字对象，包括中英文字符分成12种角色，CRFs_CRL_PnR的关键在于训练语料中的词性标注到角色标注的转化过程以及对训练语料中单字对象标注角色的CRFs学习。
4.3 特征函数生成及其参数训练
(1)观察序列的衍生。以原子单字(C)作为观察序列表现出来的能够表征其人名角色特点的信息很少，需要考虑从原始单字观察序列中衍生出其它观察序列以表现更多的特征。笔者从音译人名用字特征(F)、姓氏特征(S)、前(P)后(Q)临界字特征、前(B)后(E)缀特征以及词位特征(W)5个角度来考虑扩展观察序列，组成观察序列组。
(2)特征模板的选择。仅通过当前对象的观察值组所反映的特征信息毕竟有限，有必要加入其上下文信息来强化特征。本文拟采用局部上下文信息来约束当前对象。局部上下文信息是指以当前观察对象为中心，向前或向后连续选取一定字长范围的上下文信息作为当前对象的特征信息，这个局部连续范围称为字长窗口[9]。如果将观察值组看作是一种横向多元特征，那么字长窗口就提供了一种纵向上下文多元约束。根据观察序列组以及局部上下文信息的特征约束，CRFs_CRL_PnR选择合适的观察序列组合和一定字长的上下文窗口(本文采用3字长窗口)，建立了如表3所示的特征模板(Feature Template)[10]。表中C表示当前字，F表示音译人名用字特征，S表示姓氏特征，P表示前临界字特征，Q表示后临界字特征，W(4)表示4词位标注特征，R表示标注角色特征，n表示字长窗口位移取值。
(3)特征函数生成。根据表3所示的特征模板，结合CRFs状态特征函数(公式(7))以及转移特征函数(公式(8))的定义，可以从观察序列和角色标注序列组中生成成千上万个候选特征函数，可从中选取一定数量的高频特征函数用于人名角色标注。本文选取的特征函数出现次数(即特征函数频次阈值，记为f)在10次以上。
(4)特征函数权重参数训练。笔者使用了CRF++-0.49工具包[11]来实现特征函数权重参数的训练。CRF++提供了两个工具：
①crf_learn用于从观察标注序列组中基于特征模板生成CRFs特征函数，并根据用户提供的阈值选择高频特征函数，之后通过LBFGS非线性规划算法对特征函数权重参数进行训练，建立CRFs模型；
②crf_test使用建立的CRFs模型对输入的仅有观察序列组的测试语料进行角色标注。
4.4 基于角色模式的人名实体提取
经过CRF++的角色解码标注，可以获得测试语料中每一个“字”对象的最佳角色。根据表1所列的人名角色，结合中文人名的一般构成规律，笔者认为BB、BCD、BE、BG、BBCD、BBE、BBG、XXCD、XXE、XXG、CD、E、FB、FXX、FBB、W…W等角色组合模式可以构成人名实体。图4描述了基于角色组合模式实现人名实体抽取的算法过程。
图4 基于角色组合模式从“字”序列和标注序列中抽取人名实体
图5 HMM_WRL_PnR和CRFs_CRL_PnR在人名实体识别开放性测试中的实验比较
5 CRFs和HMM的实验比较
CRFs和HMM虽然都是根据观察序列特征进行序列标注，但依据的数学原理、建模的过程以及产生的结果都不相同。基于两种模型依赖的数学基础，笔者认为CRFs避免了HMM由于理论缺陷所必然存在的问题，较HMM更适合解决序列标注问题；但HMM较之CRFs则数学理论简单，集成特征少，因而训练时间短。为了验证理论探讨获得的结论，笔者对两者在人名识别中的应用(HMM_WRL_PnR和CRFs_CRL_PnR)进行了开放性测试和新闻人物抽取应用两个实验，以探讨其差异。笔者拟统计以下数据作为测评指标：
被识别的人名个数(N[,reconum])
准确率(P)=N[,truenum]/N[,reconum]×100%
被正确识别的人名个数(N[,truenum])
召回率(R)=N[,truenum]/N[,totlenum]×100%
训练时间(T[,ltime])
F－值＝(β[2]+1)×P×R/(β[2]×P+R)=2×P×R/(P+R)(P权重β取1，即认为P和R同等重要)
5.1 开放性测试
本次实验采用的训练和测试语料来自《人民日报》1998年1月份经过标注的中文语料库，以1月份前24天共15767句语料作为训练集，后7天共3717句的语料作为测试集(共有中文人名3132个)。使用HMM_WRL_PnR和CRFs_CRL_PnR分别进行中文人名抽取，结果如图5所示。
实验表明，CRFs模型在识别准确率上明显优于HMM；两者召回率相差不多，尽管CRFs比HMM仅高出2个多百分点，结果使得在F值比较中，CRFs比HMM高出了近10个百分点；HMM在N[reconum]一项上比CRFs高，说明前者比后者更善于发现人名实体，但这也严重牺牲了该模型的识别准确率；此外，实验对模型的训练时间也进行了比较，发现HMM中3个词典的生成仅需约30分钟，而CRFs则需要花费23个小时进行参数训练，进一步证明CRFs的模型复杂度远高于HMM。
5.2 新闻人物抽取应用
使用网页下载工具对南京大学小百合BBS进行信息采集，笔者获得其中历史(History)版自创版以来到2007年9月的所有主题标题，然后使用经过训练(训练数据均来自《人民日报》1998年1月份经过标注的中文语料库)的HMM_WRL_PnR和CRFs_CRL_PnR分别对主题标题进行自动人名抽取，获得这段时间内History版所涉及的焦点人物。
图6 History版中讨论次数达到10次的焦点人物
如图6所示，HMM_WRL_PnR正确识别人名中讨论次数达到10次的共有27人，共计665人次；而CRFs_CRL_PnR正确识别人名中讨论次数达到10次的有24人，共计663人次；CRFs在这次比较中稍处下风。根据此次应用，笔者认为：
(1)两者识别的人名均在3字以下，而在开发性测试中涉及一定数量的国外音译人名(长度在3字以上)，经过比较可知，HMM对多于4字以上人名的识别能力较弱，CRFs_CRL_PnR中音译人名用字特征(F)的加入使得其识别外国人名的能力有明显的提高；
(2)本次应用仅统计讨论次数较多的人名，多集中于几个著名焦点人物，识别的人名数少于30人，在这种情况下，CRFs_CRl_PnR优势并不明显；
(3)HMM_WRL_PnR识别了部分CRFs_CRL_PnR没能识别的人名，表明HMM_WRL_PnR在人名召回方面具有一定优势，开放性测试中HMM_WRL_PnR的N[,reconum]值较高(虽然R值偏低)也说明了这个问题；
(4)CRFs_CRL_PnR低召回率的一个很重要的原因在于断句不充分，在HMM_WRL_PnR中，遇到阿拉伯数字或英文字符即断句，而在CRFs_CRL_PnR中，以训练语料中一行作为一个句子进行训练，对于测试文本也是以一个主题标题作为一个句子，没有合理断句，导致使用CRFs_CRl_PnR识别的人名中经常含有标点符号或英文字符，进一步实验表明，当使用合理短句进行训练时，建立的模型较之长句训练可以较大程度地提高人名识别的召回率；
(5)从识别效果来看，两次实验抽取获得的人名都是中外历史上著名的人物，这符合History版以历史人物或历史事件作为论题的宗旨，可见上述两个模型都已经达到实用标准。
6 结语
本文从数学理论模型基础和人名实体抽取应用等方面对HMM和CRFs进行了比较研究。认为HMM的数学复杂度低于CRFs，特征训练时间也远低于CRFs；但是在人名实体抽取应用的准确率、召回率、F—值以及正确识别数等各项测评指标上都远远落后于CRFs。本文在数学理论上和实践应用中都证明了CRFs由于合理的数学理论、严密的数学推理使其比HMM更适合用于序列标注或对象分类等信息抽取应用中。此外，本文提出了基于角色标注的人名实体抽取方法，认为无论基于HMM还是基于CRFs训练，其在人名实体抽取中的应用效果都已经达到了实用的水平(开放性实验F—值超过了80%)。
笔者通过本文的研究，提出概率统计模型可以广泛应用于信息抽取的各个层次中，包括命名实体的抽取、非结构化文本的主题词抽取，甚至于实体之间关系的判别、代词指代对象的判别等等，应用的关键在于标注集合的定义以及观察序列的生成。因此，今后的讨论重点可以放在进一步提高CRFs_CRL_PnR的人名识别召回率、基于统计的实体关系识别、代词指代对象识别等机器学习研究中，以作为网络舆情分析系统、竞争情报系统研究、本体概念及关系自动抽取、文本语义分析、本体自动化构建等研究的基础。
收稿日期：2007-10-11
收修改稿日期：2007-10-24
标签：hmm论文; 特征函数论文; 统计模型论文; 概率计算论文; 序列模式论文; 测试模型论文; 特征选择论文; 生成函数论文; 数学论文;