信息提取(Information Extraction)_2d conditional random fields for web information e

参考资料：Web Information Extraction

信息提取(IE)

信息提取(IE)的目标是将文本信息转化为结构化信息，起初用于定位自然语言文档中的特定信息，属于自然语言处理的一个子领域。

随着网页文本信息的急剧增长，越来越多的人投入到信息提取(IE)领域的研究。

网页文本信息的非结构化特征和无序性，一般只能采用全文检索的方式查找。但是网页中充斥着大量的无关信息，比如广告和无关链接以及其他内容，有用信息和无用信息混杂在一起，给网页信息的检索问题带来极大的困难。

IR与IE

提起IE，不得不提的另一个跟信息处理相关的领域就是信息检索(Information Retrieve)，二者有什么关系呢？

一般来说，IR的目标是从特定集合中获取相关的文档；IE的目标是从文档中获取相关的信息。

因此两个领域的技术相辅相成，共同用于文本信息处理。

信息提取(IE)发展历史

• 20世纪90年代初，人们开始关注信息提取(information extration)相关研究。
• 之后信息提取算法方面取得很大进展，自动识别命名实体(人名、组织名等)方面取得巨大进步。
• 随着Web的出现和繁荣，IE研究人员逐渐将兴趣转移到Web网页信息提取的研究上。其中比较知名的项目是卡耐基梅隆大学自动学习和发现中心的Web挖掘项目，他们采用机器学习算法，目标是通过训练自动地从Web中提取信息。
• Web IE领域涌现出许多算法和模型，比如基于知识工程的专家模型，基于概率图模型的马尔科夫模型、条件随机场，基于页面差异的数据挖掘模型，基于视觉的页面分割模型，基于分类的提取模型，等等。

IE评价体系：

IE技术的评价体系来自于标准的信息检索(IR)体系的召回率(recall)和准确率(precision).

召回率(recall): 是提取出来的信息与所有信息的比。

准确率(precision)：是提取出的信息中正确的数量与全部数量的比。

我们的目标是提高两项子表，但通常情况下，recall越高，precision就比较低，反之，precision越高，recall就比较低，二则之间需要做一个权衡。

通常，我们经常采用的另一个度量就是F值，它的计算公式如下：

$F=\frac{({\beta }^2+1)PR}{\beta P+R}$

其中参数$\beta$表示recall和precision的重要性比率。

IE系统分类

IE系统主要有分为两大类，分别是专家系统类和自动学习类。

早期的研究主要集中在专家系统类。通过人工构造的规则来提取信息。缺点是需要大量的人力的投入，并且有时候领域内的知识获取构成了瓶颈。

自动学习类是算法的优点是不需要领域知识，日渐称为研究的主流，缺点是监督类或半监督类的学习算法，需要足够的训练数据。

自动学习类IE基本过程

通常，IE技术的第一步要做的就是将网页进行预处理，将半结构化的网页信息按照一定的模型表示成学习算法容易处理的结构化模型。

根据我们所采用的学习算法，通常会有相应的预处理过程。

IE算法

常见的监督类学习算法有马尔科夫模型，贝叶斯网络，条件随机场等等；非监督类的算法有基于语法归纳，词频统计，树形结构比较等数据挖掘类算法；另外还有一些模型通过建模将提取问题转化为分类问题，分类问题是机器学习算法的经典问题，有众多的的算法可以使用，经常使用的的分类算法有SVM，神经网络，树形模型等等。

各类学习算法各有优点，基于概率图模型和数据挖掘类的算法，适合于网页的模式比较明显、格式化比较强的情况。基于分类算法的模型能更好的利用网页的视觉方面的特征，有助于提高算法的泛化能力。

经典模型

下面列举一些有代表性的IE模型

1.基于正则文法推导的模型

信息抽取问题相当于推导页面的文法，通常是正则文法，然后通过推导出的正则文法来抽取文本中的信息。

文法推导问题是一个比较经典，研究比较成熟的问题，同时也是一个比较困难的问题；因为首先，只有正例的情况下文法是不能被正确识别的，其次，即使正反例都存在的情况下，目前也没有高效的学习算法。这两方面的困难限制了传统的文法推导技术在信息提取领域的应用。

这里举一个例子，$RoadRunne{r}^{[1]}$系统通过推导union-free正则文法来解决提取问题.

2.基于模板推导的模型

这类模型将web页面的产生过程看成存储在数据库中的结构化的数据，按照模板规定的schema进行序列化的结果，如下图：

如此信息提取问题则可以通过模板推导的方法解决。这类算法的主要区别也在于如果获取模板的信息。

早期的系统人工提供模板的信息，后来出现了一些系统可以从人工标记的数据中，学习到模板的信息。也还有系统通过比较同一个模板产生的页面之间的相似和差异，挖掘出模板的信息，比如论文【2】所采用的方法：

3.基于页面结构比较的模型

以上的文法推导和模板推导的模型，都是将web页面作为文本信息进行处理，其实web页面并不是纯粹无结构化的文本信息，而是半结构化的，例如dom树结构。

我们来介绍一个基于页面结构的$模{型}^3$，通过比较页面之间树形结构的差异，来实现信息提取。

系统采用的度量标准是：

Tree Edit Distance：将树TA转化为TB的最少操作的数量，定义为TA,TB之间的编辑距离。

信息提起的过程如下：

4.基于视觉特征的模型

此$模{型}^4$首先基于视觉特征，将页面转化为视觉区域树，然后定位包含目标信息的局域，最后从目标区域提取信息。

视觉区域的划分使用$VIP{S}^5$算法。

提取方法可以使用启发式规则：

或则使用分类算法：

5.条件随机场模型

以上的模型没有考虑到视觉块之间的相对位置关系，加入相对位置特征，条件随机场可以很好的建模这类模式。

Web页面的信息提取，也就是定位页面特定信息的位置，当然也可以看成是对页面中信息的类型进行标注，这些信息的类型是有是下文关系的，如上图，名称，头像，详细介绍等类型信息的位置是相关的，他们之间的相对位置具有一定的模式。

对这种序列关系的建模的一个很好的模型就是条件随机场。

X表示我们观察到的信息，Y表示信息的类别（名称，头像，介绍，价格等等）.一般序列标注的问题中，用到的是链式条件随机场，此$模{型}^6$中采用的是2D条件随机场，因为网页中信息的标注问题天生是个二维的序列标注问题。

6.广义隐马尔科夫模型(GHMM)

在信息提取领域，隐藏马尔科夫模型(HMM)已经广泛的应用在命名实体识别等问题中。web文档作为一个整体，与一般的纯文本文档相比，其实是缺少整体的语法结构的。如果将HMM直接应用在web文本信息处理中是不太合适的。

$模{型}^7$提出两个一个方法将HMM应用到了web信息提取中。

对于以上的网页，首先基于视觉特征将其转化为视觉块树。

然后在在视觉块的粒度上进行标注，从而将HMM应用到了网页信息的提取。

参考论文：

1.CRESCENZI V， MECCA G， MERIALDO P.RoadRunner: towards automatic data extraction from large Web sites[C] //Proc of the 27th International Conference on Very Large Data Bases.San Francisco: Morgan Kaufmann， 2001: 109 118.

2.ARASU A， GARCIA MOLINA H.Extracting structured data from Web pages[ C] //Proc of ACM SIGMOD International Conference on Management of Data.New York:ACM Press， 2003: 337 348.

3.REIS D C， GOLGHER P B， SILVA A S，et al.Automatic Web news extraction using tree edit distance[C] //Proc of the 13th International Conference on World Wide Web.New York:ACM Press， 2004: 502 511 .

4.LIU Wei， MENG Xiao feng， MENG Wei yi.Vision based Web data records extraction[C] //Proc of the 9th SIGMOD International Work
shop on Web and Databases.2006:2025

5.CAI Deng， YU Shi peng， WEN Ji rong，et al.VIPS: a vision based page segmentation algorithm， MSR TR 2003 79[R].Redmond:Microsoft Corp， 2003

6.[34] ZHU Jun， NIE Zai qing， WEN Ji rong， et al.2D conditional random fields for Web information extraction[C] //Proc of the 22nd Interna tional Conference on Machine.New York: ACM Press， 2005:1044 1051.

7.ZHONG Ping， CHEN Jin lin.A generalized hidden Markov model approach for Web information extraction [ C ] //Proc of IEEE /WIC / ACM International Conference on Web Intelligence.2006:709 718.