计 算 机 工 程 第 37 卷 第20期 Computer Engineering V ol.37 No.20 文章编号：文章编号：1000—3428(2011)20—0178—02 ·人工智能及识别技术·人工智能及识别技术· 2011年10月 October 2011 文献标识码：文献标识码：A 中图分类号：中图分类号：TP311基于改进基于改进HMM的文本信息抽取模型文本信息抽取模型 梁吉光，梁吉光，田俊华，田俊华，姜 杰 (南京师范大学教育科学学院，南京 210000) 摘 要：提出一种基于改进隐马尔可夫模型(HMM)的文本信息抽取模型。给出一个新假设，使用绝对平滑算法对模型参数进行平滑，利用Viterbi算法对观察值序列进行正序和逆序解码，基于N-Gram模型对2次解码结果进行对比消歧，得到较准确的状态序列。实验结果表 明，该信息抽取模型能提高信息抽取的准确率。 关键词：关键词：隐马尔可夫模型；绝对平滑；观察值；信息抽取；引文信息 Text Information Extraction Model Based on Improved HMM LIANG Ji-guang, TIAN Jun-hua, JIANG Jie (Educational Science College, Nanjing Normal University, Nanjing 210000, China) 【Abstract】This paper proposes a text information extraction model based on improved Hidden Markov Model(HMM). It gives a new assumption of observation emission. And the absolute smoothing algorithm is used to smooth the parameters of the model. The model recovers the most-likely state sequence of the observation sequence and the reverse observation sequence with the Viterbi algorithm. It compares the results with each other based on N-Gram model, and outputs a more accurate result for the state sequence. Experimental results indicate that this model has effectively improved precision. 【Key words】Hidden Markov Model(HMM); absolute smoothing; observation; information extraction; citation information DOI: 10.3969/j.issn.1000-3428.2011.20.061 1 概述 面对海量的信息资源，如何快速有效地将所需信息抽取出来并转化为结构化数据，已成为当前研究的热点。自动文本信息抽取是文本信息处理的一个重要环节[1]。该技术通过自动手段抽取并过滤无关信息，把文本中包含的有价值信息以适当的结构形式集成在一起。 隐马尔可夫模型[2-6](Hidden Markov Model, HMM)是一种重要的文本信息抽取方法，由于其易于建立、适应性强等特点而备受研究者的关注。文献[2]利用基于最大熵的HMM提高抽取准确率；文献[3]基于符号特征提取，改善了HMM性能；文献[4]结合分块提高抽取性能；文献[5]应用二阶 HMM抽取论文头部信息，并取得不错的识别效果；文献[6]提出一种乘积隐马尔可夫模型。传统HMM模型及其衍生模型虽然具有很好的抽取效果，但它们的共同点是只考虑某时刻的转移概率与发射概率对历史状态的依赖性，即前向依 赖。本文提出一种基于改进HMM的文本信息抽取模型，给出新的假设，考虑了状态的后向依赖性。 2 隐马尔可隐马尔可夫模型简介夫模型简介 HMM模型可以看作是能够随机进行状态转移并输出符号的有限状态自动机。隐马尔可夫过程是一个双重随机过 程，由马尔可夫链和一般随机过程2个部分组成，如图1所示。其中，马尔可夫链不能直接观察到，通过状态转移概率矩阵描述；一般随机过程描述状态与观察序列间的关系，由符号输出概率矩阵来定义。 第37卷 第20期 梁吉光，田俊华，姜 杰：基于改进 HMM 的文本信息抽取模型 179 出路径，因此，直接用最大似然法来估计模型参数，A、B、Π计算公式不变，BB计算如下： bMij(k)=Emission(i,j,k)/∑Emission(i,j,t) t=1其中，Emission(i,j,k)是指在训练样本中状态Si与Sj为前后状态，Si输出符号Vk的次数。 3.3 参数平滑 在使用最大似然法估计参数时，由于训练样本的不完 整，有可能导致零概率事件和稀疏矩阵的出现，为此需要进行平滑处理，本文采用绝对平滑算法。定义折扣系数如下： D1=[Sum(N1)+Sum(N2)]/Num(Nn>2) D2=[Sum(N1)+Sum(N2)]/Num(N0) 其中，N1表示在训练样本中出现一次的样本；Sum(N1)表示这些样本的所占的比例；Num(N1)表示这些样本出现的总次数。在平滑过程中，对于出现次数大于2次的事件减去D1，零概率事件加上D2，从而保证∑P=1。 3.4 可行性分析 如图2所示，对于传统的HMM模型，观察值的输出概率仅依赖于模型当前的状态；对于改进的HMM模型，t时刻的观察值输出概率依赖于t、t+1时刻的状态。 O1O2O3O4…S11S2S3S4 (a)传统HMM (b)改进的HMM 图2 传统HMM与改进的改进的HMM 以抽取引文信息为例，假设待抽取的样本中，有一样本经分块[4]后得到观察值序列“黄铠，徐志伟|可扩展并行技术结构与编程|北京|机械工业出版社|2000”。其中，O2=“可扩展并行技术结构与编程”，对应的是一本书名，即状态Book。现假设O1已被标注为状态Author，分析比较传统HMM和改进HMM模型在解码时对信息的识别能力。 在应用传统HMM模型时： P(q2=Title)=P(q2=Title|q1=Author)P(O2|q2=Title) P(q2=Book)=P(q2=Book|q1=Author)P(O2|q2=Book) 由状态转化概率知，由状态Author转化到Title的概率比转化到Book的概率要大得多，而O2作为Title和Book输出的概率几乎是相等的，即O2被作为状态Title的输出，这显然是一个错误的抽取结果。 在应用改进HMM模型时： P(q2=Title)=P(q2=Title|q1=Author)× P(O 2|q2=Title,q3=City)P(q2=Book)=P(q2=Book|q1=Author)× P(O2|q2=Book,q 3=City)由转移矩阵可知，“Title, City”作为连续状态出现的概率为0，P(q2=Title)=0，即可判断O2的状态为Book。 由此可知，改进后的模型能使事件的发生概率更为细 化，状态标注更加准确。 4 基于改进HMM的文本信息抽取文本信息抽取模型信息抽取模型 本文以中文引文作为处理对象，对引文中的标题、作者、期刊名称等文本信息段进行信息抽取，抽取系统处理过程如图3所示。 图3 抽取系统处理过程 4.1 改进的Viterbi算法 HMM模型参数确定后，则通过Viterbi解码算法可从给定观察值序列的所对应的可能状态序列中，选择概率最大的作为最佳状态序列。由于改进的模型中多了一个参数，因此修改Viterbi算法如下： Viterbi变量为： δt(i)(j)=maxP(q,qt=Si,qt+1=Sj,O|λ) q1,q2,...,qt−1Viterbi具体算法描述如下： (1)初始化：δ1(i)(j)=πibij(O1)aijbj(O2)j,1≤i≤N； (2)递归：δt+1(i)(j)=[maxδt(k)(i)aki]bij(O)b1j(O≤k≤Nt+1t+2)； (3)终止：P*=1max[δ≤i,j≤NT(i)(j)]。 4.2 逆序Viterbi解码 对于观察值序列O=(O1,O2,⋅⋅⋅,OT)，用Viterbi算法解码时，P(qi+1|q1,q2,⋅⋅⋅,qi)=P(qi+1|qi)，即O2的状态由O1的标识状态决定。 而对于另一观察值序列O'=(OT,OT−1,⋅⋅⋅,O1)，t+1时刻的状态qt+1由时刻t的状态qt所决定，即O1的状态由O2的状态标注决定。至此，可将对观察值序列O'=(OT,OT−1,⋅⋅⋅,O1)的解码过程理解为：对于观察值序列O=(O1,O2,⋅⋅⋅,OT)，t时刻的状态qt由时刻t+1的状态qt+1所决定，即P(qi|q1,⋅⋅⋅qi,qi+1)= P(qi|qi+1)，这体现了后向依赖性。 4.3 消歧模型 通过正序和逆序Viterbi算法对观察值序列进行解码。然后，对2种解码序列进行比对，抽取其中含有解码歧义部分及其前N(N≤3)个状态，将没有解码歧义的状态暂时过滤。然后通过N-Gram模型进行歧义消除。 N-Gram模型是一种考虑上下文语境的统计语言模型[7]，通常被用于词性标注。应用于状态解码中可描述为：对于给定的状态序列S=(S1,S2,⋅⋅⋅,Si,⋅⋅⋅,SN)，这个序列出现的概率 可表示为P(S)=P(S1),P(S2|S1),⋅⋅⋅,P(SN|S1S2⋅⋅⋅SN−1)。 对于给定的观察值序列，在经过正序和逆序Viterbi解码后可得到2个状态序列S=(S''1,S2,⋅⋅⋅,SN)和S'=(S1,S2,⋅⋅⋅, S'⋅⋅⋅,S'k,N)，此时Si与S'k所对应的观察值一致，其中，i+k−1=N。如果经过状态比对后发现Si与S'k不等价，则提取 Si及其前的n(n=min(i, k))个状态和S'k及其后的n个状态组成状态序列TS和TS'。而后利用N-Gram模型求得P(TS)与 (下转第182页)