基于改进的隐马尔可夫模型在网页信息抽取中的研究与应用
2017-02-27双哲孙蕾
双 哲 孙 蕾
(华东师范大学计算机科学技术系 上海 200241)
基于改进的隐马尔可夫模型在网页信息抽取中的研究与应用
双 哲 孙 蕾
(华东师范大学计算机科学技术系 上海 200241)
信息抽取是从大量的数据中准确、快速地获取目标信息，提高信息的利用率。考虑网页数据的特点，提出一种适用于网页信息抽取改进的隐马尔科夫模型(HMM)，即结合最大熵模型(ME)在特征知识表示方面的优势，在HMM模型中加入后向依赖，利用发射单元特征来调整模型参数。改进后的HMM状态转移概率和观察输出概率不仅依赖于模型的当前状态值，而且可以以模型的前向状态值和后向特征值加以修正。实验结果表明，使用改进后的HMM模型应用到网页信息抽取中，可以有效地提高网页信息抽取的质量。
隐马尔可夫模型 最大熵模型 网页信息抽取
0 引 言
随着互联网技术及应用的不断成熟与深入，面对日益增多的海量网页信息，人们需要一种自动化工具来帮助人们从中快速发现真正需要的信息，并将这些信息自动分类、提取，使其有益于信息后续的检查比较及自动处理，由此需要相应成熟的网页信息抽取技术从搜索引擎得到的结果网页中抽取目标信息。网页数据和传统的自由文本数据相比具有半结构化、更新快、形式多样等特点。目前涉及这一热点研究课题的相关方法和技术有：(1) 基于包装器生成技术适用于格式固定的网页，但在移植及维护上较困难[1]；(2) 基于NLP的信息抽取方法适用于纯文本的抽取任务，但网页数据被标签分割无法直接使用；(3) 基于本体的信息抽取方法需要较大的成本构造本体[2-3]；(4) 基于DOM树的技术基于网页本身的结构，其适用于相似结构的网页，包括DSE算法[4]和MDR算法[5]；(5) 大量网页可通过读取后台数据库填充到统一模板生成，从而形成了基于模板的抽取技术，但其使用范围有限[6]。文中所研究与改进的基于隐马尔可夫模型(HMM)的网页信息抽取模型，具有易于建立、不需要大规模词典和规则集、移植性好、投入成本较少等显著优势。然而，目前该类模型还存在着其信息抽取的准确率及效率有待进一步改进和完善的不足，其中已有的工作成果和进展，如文献[7-9]应用HMM抽取论文头部信息，用shrinkage改进模型概率估计，并用随机优化技术动态选择模型结构；文献[10]在网页中以语义块作为抽取单元，并利用投票机制优化发射概率分布；文献[11-12]在网页中选择功能内容块(即逻辑内容相关联的块被组织在一起)抽取单元，结合VIPS和DOM等技术识别并抽取一个目标块；文献[13]提出的MEMM将文本词汇本身包含的特征信息结合到马尔科夫模型中，但MEMM只是考虑了抽象特征，并未对文本词汇进行统计；文献[14-16]提出并验证了在很多应用中二阶模型的有效性，若为了提高模型的描述能力而单纯增加模型阶数，参数空间会成指数增长，而容易引发数据稀疏等问题。
在此，提出改进的HMM用于网页数据的有效抽取，即将抽取信息的模型扩展为二阶且同时考虑文本上下文特征信息，利用最大熵模型(ME)在特征知识表示方面的优势，在HMM模型中加入后向依赖，利用发射单元特征来调整模型参数。改进后的HMM状态转移概率和观察输出概率不仅依赖于模型的当前状态值，而且拟进一步地利用模型的前向状态值和后向特征值加以修正完善。从而解决了在以往的HMM中没有考虑抽取对象的上下文特征和文本词汇本身包含的特征信息等问题。
1 基于改进的HMM的网页信息抽取的工作流程概述
隐马尔可夫模型(HMM)是信息抽取的重要方法之一，文中针对HMM不足，结合网页数据的特征，提出了改进的HMM用于网页信息抽取。改进后的HMM充分考虑了抽取对象的上下文特征和文本词汇本身包含的特征信息，修正了模型的转移概率和发射概率(即在模型训练阶段利用最大熵原理优化了模型参数；在模型解码阶段让改进的viterbi算法更有效地完成信息抽取)。文中所研讨的网页信息抽取的主要方法和技术流程如图1所示，其中：(1) 数据预处理：依据所处理数据的特征，将数据划分为分组序列；(2) 初始化模型：确定模型的状态集和模型的拓扑结构；(3) 模型训练：在训练集中使用ML算法[15]和与最大熵相关的GIS算法[13]来训练获取模型的参数；(4) 完成信息抽取：采用改进的viterbi算法求最佳状态标记序列，结合标注结果以结构化形式存入数据库表中。
图1 基于HMM信息抽取主要执行过程
2 基于改进的HMM 的网页信息抽取的功能剖析
2.1 网页数据准备
2.1.1 数据预处理
网页信息抽取预处理就是依据所处理数据的特征选取基本抽取单元。网页中数据被HTML标签、分隔符等元素分割成一个个的语义块[10]，使得属于同一个状态的内容将以很大的概率组织在同一个语义块内，文中保留了HTML标签和分隔符是为了更易于将逻辑相关的内容组织在一起以形成语义块分组。文中采用语义块分组作为观察序列的基本抽取单元，如此同类别的数据被组织在一起，明显比以单个单词为抽取单元的效率更高。所以文中基于文献[10]语义块分组的思想对网页数据进行预处理，形成分组序列。并将数据预处理后的格式设定为：原始序列Raw、特征序列Type、状态序列State[17]。
2.1.2 网页信息抽取模型状态集的改进描述
值得说明的是：为了对预处理后的分组序列标注相对应的状态序列state，需要构造相对应的状态集，而状态集的选择对最终抽取结果具有重要的影响。在构造一个基于HMM的网页信息抽取模型时，首先要确定模型的结构，即应该包含多少个状态及各个状态之间如何转换，一个理想的初始模型是一个状态对应一个标记类型，且任意两个状态间可以相互转移。但是从文献[7]的结论中我们得知这种方式并不是最优的，而一个标记类型定义多个状态又会增加模型复杂度。另外若两个单词以相同的频率出现在同一个状态内，目前一般的做法是让这两个单词具有相同的重要程度，但是这种做法却忽略了一个重要的信息，那就是在同一个状态内多个单词具有顺序或前后关系。在此，为每一个标记类型定义两个状态：开始状态(start)和剩余状态(rest)。如论文的“title”标记，就包括：title.s和title.r。这种结构十分适合网页数据的特点，如“地址”标签addr.s之后就会是具体的地址addr.r。在此提出的模型中除了包含正常状态外，还包含一些特殊的状态标记如start、end。
2.2 信息抽取模型的训练阶段
模型训练阶段，在完全标记的样本集中给定了观察序列O和其相对应的状态序列Q，为了确定释放该观察序列的模型λ且使该观察序列的释放概率P(O|λ)最大，通常采用最大似然估计(ML)算法中相关的统计公式[15]训练获取HMM的参数集。
传统HMM是能随机状态转移并输出符号的有限状态自动机[7]如图2(a)，其包括观察层和隐藏层，观察层是待识别的观察序列，隐藏层即状态序列是一个马尔可夫过程。文中利用最大熵模型(ME)在特征知识表示方面的优势，考虑被抽取对象上下文特征信息且同时增加模型阶数以增加模型的描述能力后，在模型中加入了前向、后向依赖。改进的HMM主要扩展了两个假设条件：(1) 改进的HMM在t时刻的状态不仅由t-2和t-1时刻的状态决定，且由t和t+1时刻观察序列所具有的特征决定；(2) 在t时刻输出观察值的概率不仅依赖于t时刻所处的状态而且依赖于t-1时刻的状态。
图2 HMM模型的改进
在利用被抽取对象特征方面，最大熵原理提供一种方法，可以集成各种特征与规则到一个统一的框架下。如文献[13]提出的MEMM是一个指数模型，其将被抽取对象的抽象特征作为输入，并在马尔科夫状态转移的基础上选择下一个状态，其结构接近于有穷状态自动机如图2(b)。加入特征集合后影响了状态之间的关联，因而需用状态转移概率矩阵和特征-状态转移概率矩阵来描述新的状态之间的关联。从观察序列相邻两项中提取数据特征，即t和t+1时刻相邻两项观察所具有的特征部分决定了t时刻所处的状态，以此可以从观察序列中得到模型对后向数据特征的依赖，如图2(c)所示。在现实应用中可根据具体的应用领域而构造不同的特征集合，如在论文头部信息抽取中是否大写字母开头、是否含有人名或人名缩写、是否是数字、是否含有@或email等。
改进的HMM与传统的HMM训练获取参数集对比如表1所示。
需要特别说明的是：
(1)
其中，r=∑k[λ×aijk+ (1-λ)×∑f(Cf,k× ff,k((ot,ot + 1),st))]为归一化参数；引用文献[13,18]中论述的最大熵原理在NLP各分支应用中的公式，在此在给定的特征集上定义一个二值函数如下式：
fi,j((ot,ot+1),st)=
(2)
接着，基于最大熵思想及上述定义，在改进后的HMM中需要构造一个特征-状态转移的概率矩阵，即式(1)中参数C就是利用最大熵原理从观察值序列的特征中获取的特征-状态转移概率矩阵C={Ci,j}NF×NS，其中元素Ci,j就是从特征i到状态j的概率，满足条件：∑jCi,j= 1，其中NF是特征的个数，NS是状态的个数。在训练阶段对各个观察序列进行特征提取，在完全标记的训练数据中每个观察特征都对应一个状态，因此可以利用改进的GIS算法统计获取特征-状态转移概率矩阵，算法过程如图3所示。
图3 利用改进的GIS算法求特征-状态概率转移矩阵方法流程
2) 在使用最大熵原理统计被抽取对象的特征信息方面，相比于MEMM没有统计词汇本身信息[13]，但在改进后的模型中使用符号输出概率矩阵统计词汇本身信息，且改进后的模型t时刻的观察值依赖于t-1和t时刻的状态如式(2)所示。
2.3 完成信息抽取阶段
为了完成信息抽取需要解决的是解码问题，即给定训练得到的模型参数λ和观察值序列O，求与观察值序列对应且使得P(Q|O,λ)最大的最佳状态序列Q，通常采用的是viterbi算法。
定义δt(i,j)为t时刻沿路径q1,q2,…,qt-1,qt(qt-1=si,qt=sj)释放部分观察值序列O1,O2,…,Ot的最大释放概率式如(3)：
δt(i,j)=maxP(q1,q2,…,qt-1=Si,qt=
Sj,O1O2,…,Ot,Ot+1|λ)
(3)
通过推导可得t+1时刻路径的最大概率如式(4)：
(4)
另外，定义一个用于存储回溯路径的数组变量如式(5):
(5)
求最佳状态序列的改进Viterbi算法主要实现步骤如下：
(1) 初始化：δ1(i)=πibi(Oi),Ψ1(i)=0
δ2(i,j)=πiaijbi(o1)bij(o2),Ψ2(i,j)=0
(2) 递归： /*模型的改进应用于此处*/
where(1≤j,k≤N&&2≤t≤T-1)：
1≤i,j,k≤N,2≤t≤T-1
(3) 终结：
(4) 回溯求最佳路径：
2.4 针对模型进一步优化的改进建议
1) 针对实际应用过程中，从训练语料中学习模型的参数时经常需要面对训练数据不足的情况，而使用最大似然(ML)估计模型参数时将会出现参数概率为零的情况。为避免出现上述情况使用参数平滑处理。主要的平滑技术包括：利用频率信息进行平滑的Good-Turing；使用低阶模型和高阶模型的线性组合的线性插值平滑；回退低阶模型近似求解的katz`s回退式平滑[8]。文中依据上述三种平滑思想，结合文献[16]中提及的Back-off shrinkage思想，进一步改进平滑技术以适应将HMM应用到网页信息抽取中，文中统计在全局中数据出现的次数融入平滑公式中，对状态转移与观察值输出概率进行平滑处理。如状态转移概率P(Si→Sj→Sk)=λ1P(Si→Sj→Sk)+λ2Pglobal(Si∪Sj∪Sk)其中，Pglobal(si∪sj∪sk)是三者在整个训练集中出现的概率；对观察值发射概率P(Vm|Si→Sj)=λ1P(Vm|Si→Sj)+λ2Pglobal(Vm)其中，Pglobal(Vm)是Vm在整个训练集中出现的概率。
2) 如何解决在测试阶段出现了而在训练阶段没有遇到的单词的发射概率，这就是OOV(outofvocabulary)问题。文中我们将使用较有效的最小频率法：让fmin表示最小频率，词汇表中单词在训练数据集上的发射频率都不会小于fmin，其他的单词如果他们的频率小于fmin，就会将他们标记为
3 实验结果与分析
实验一是模型有效性的验证，选择改进后的HMM与一阶HMM(基本抽取单元分别选择单词和语义块)、二阶HMM，在语料库DBLP[19]和CORA[20]上的对比结果。文中选择F1参数衡量信息抽取模型的质量，F1参数综合了准确率和召回率的结果，F1参数越大说明模型的质量越好，实验结果如图4所示。由实验结果可知在考虑了前向和后向依赖的情况下各个状态的抽取质量均有提升，而Author、Data、Email等项由于较为明显的特征信息可以取得明显的效果。而某些数据项由于并非频繁出现或特征不明显而使得结果并没有较大的改善。试验中还比对了采用语义块后的效果，由于减少了将单个单词错误地分到其他状态的概率，而抽取结果有明显提升。
图4 模型抽取结果质量对比
图5 网页数据集上抽取结果对比
4 结 语
作为NLP的重要分支，信息抽取相对信息检索更深层次的数据挖掘，在海量信息的时代其研究价值越来越受到重视。文中结合最大熵原理利用数据特征信息改进HMM，在改进后的HMM中有效地考虑了模型前向依赖和后向依赖。结合网页数据特征，提出基于改进的HMM的网页信息抽取模型，对网页数据进行信息抽取，有效地适应了网页结构的变化、充分地利用了网页的半结构化信息。通过对比实验，验证了改进后的HMM方法可以有效地实现了针对网页数据的信息抽取，且具有更好的性能。后续研究可以着眼于：将改进后的模型应用到元数据的抽取，自动学习模型的结构，利用主动学习技术减少对标记样本的依赖，从而可以实现模型的自动化构造。
[1]CrescenziV,MeccaG,MerialdoP.RoadRunner:towardsautomaticdataextractionfromlargewebsites[C]//Proceedingsofthe27thInternationalConferenceonVeryLargeDataBases,2001:109-118.
[2]GutierrezF,DouD,FickasS,etal.Ahybridontology-basedinformationextractionsystem[J].JournalofInformationScience,2015:1-23.
[3]ZhangN,ChenH,WangY,etal.Odaies:ontology-drivenadaptivewebinformationextractionsystem[C]//IntelligentAgentTechnology,IEEE/WICInternationalConferenceon.IEEEComputerSociety,2003:454.
[4]WangJ,LochovskyFH.Data-richsectionextractionfromHTMLpages[C]//ProceedingsoftheThirdInternationalConferenceonWebInformationSystemsEngineering.IEEEComputerSociety,2002:313-322.
[5]LiuB,GrossmanR,ZhaiY.Miningdatarecordsinwebpages[C]//9thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMinig.ACMPress,2003:601-606.
[6] 杨少华,林海略,韩燕波.针对模板生成网页的一种数据自动抽取方法[J].软件学报,2008,19(2):209-223.
[7]SeymoreK,McCallumA,RosenfeldR.LearninghiddenMarkovmodelstructureforinformationextraction[C]//AAAIWorkshoponMachineLearningforInformationExtraction,1999:37-42.
[8]FreitagD,McCallumAK.InformationextractionwithHMMsandshrinkage[C]//AAAIWorkshoponMachineLearningforInformationExtraction,1999:31-36.
[9]FreitagD,McCallumA.InformationextractionwithHMMstructureslearnedbystochasticoptimization[C]//ProceedingsoftheSeventeenthNationalConferenceonArtificialIntelligenceandTwelfthConferenceonInnovativeApplicationsofArtificialIntelligence,2000:584-589.
[10]LaiJ,LiuQ,LiuY.WebinformationextractionbasedonhiddenMarkovmodel[C]//ComputerSupportedCooperativeWorkinDesign(CSCWD),2010 14thInternationalConferenceon.IEEE,2010:234-238.
[11]ZhongP,ChenJ.AgeneralizedhiddenMarkovmodelapproachforwebinformationextraction[C]//WebIntelligence,2006IEEE/WIC/ACMInternationalConferenceon.IEEEComputerSociety,2006:709-718.
[12]ChenJ,ZhongP,CookT.DetectingwebcontentfunctionusinggeneralizedhiddenMarkovmodel[C]//Proceedingsofthe5thInternationalConferenceonMachineLearningandApplications.IEEEComputerSociety,2006:279-284.
[13]McCallumA,FreitagD,PereiraFCN.MaximumentropyMarkovmodelsforinformationextractionandsegmentation[C]//ProceedingsoftheSeventeenthInternationalConferenceonMachineLearning,2000:591-598.
[14]MariJF,HatonJP,KriouileA.Automaticwordrecognitionbasedonsecond-orderhiddenMarkovmodels[J].IEEETransactionsonSpeech&AudioProcessing,1997,5(1):22-25.
[15]DuS,ChenT,ZengX,etal.Trainingsecond-orderhiddenMarkovmodelswithmultipleobservationsequences[C]//Proceedingsofthe2009InternationalForumonComputerScience-TechnologyandApplications.IEEEComputerSociety,2009:25-29.
[16]OjokohB,ZhangM,TangJ.AtrigramhiddenMarkovmodelformetadataextractionfromheterogeneousreferences[J].InformationSciences,2011,181(9):1538-1551.
[17]GengJ,YangJ.AUTOBIB:automaticextractionofbibliographicinformationontheweb[C]//ProceedingsoftheInternationalDatabaseEngineeringandApplicationsSymposium.IEEE,2004:193-204.
[18]BergerAL,PietraVJD,PietraSAD.Amaximumentropyapproachtonaturallanguageprocessing[J].ComputationalLinguistics,1996,22(1):39-71.
[19]DBLP:ComputerScienceBibliography[OL].http://dblp.uni-trier.de/.
[20]CORA[DS/OL].http://www.cs.umass.edu/～mccallum/data/.
[21]SmallSG,MedskerL.Reviewofinformationextractiontechnologiesandapplications[J].NeuralComputingandApplications,2014,25(3):533-548.
[22] 郭喜跃,何婷婷.信息抽取研究综述[J].计算机科学,2015,42(2):14-17,38.
[23] 李荣,冯丽萍,王鸿斌.基于改进遗传退火HMM的Web信息抽取研究[J].计算机应用与软件,2014,31(4):40-44.
[24] 陈钊,张冬梅.Web信息抽取技术综述[J].计算机应用研究,2010,27(12):4401-4405.
RESEARCH AND APPLICATION FOR WEB INFORMATION EXTRACTION BASED ON IMPROVED HIDDEN MARKOV MODEL
Shuang Zhe Sun Lei
(DepartmentofComputerScienceandTechnology,EastChinaNormalUniversity,Shanghai200241,China)
The task of information extraction is to obtain the objective information precisely and quickly from a large scale of data and improve the utilization of information. According to the characteristics of web data, an improved hidden Markov model (HMM) for web information extraction is proposed, which means combining the advantage of maximum entropy (ME) model in the representation of feature knowledge. The backward dependency assumption in the HMM is added and the model parameters are adjusted by using the characteristic of the emission unit. The state transition probability and the output probability of the improved HMM are not only dependent on the current state of the model, but also be corrected by the forward and backward state values of the historical state of the model. The experimental results show that applying the improved HMM model to web information extraction can effectively improve the quality of web information extraction.
Hidden markov model Maximum entropy model Web information extraction
2016-01-29。国家自然科学基金项目(61502170)。双哲，硕士生，主研领域：数据挖掘，信息抽取。孙蕾，副教授。
TP3
A
10.3969/j.issn.1000-386x.2017.02.007
