《网络信息检索》课件第12章.ppt

1、第12章 Web信息抽取与问答系统第12章 Web信息抽取与问答系统 12.1 信息抽取概述 12.2 Web信息抽取 12.3 问答系统 12.4 小结思考题第12章 Web信息抽取与问答系统12.1 信息抽取概述信息抽取概述信息抽取系统的主要功能是从文本中抽取出特定的事实信息(factual information)。例如可从公司产品主页提取产品名、价格、发布时间、产品性能等。通常，被抽取出来的信息以结构化的形式描述，可以供用户查询以及进一步分析利用，例如可以进行不同网站的产品价格对比等。信息抽取最初的目标是从自然语言文档中找到特定的信息，是自然语言处理领域特别有用的一个子领域。信息抽取系

2、统既能处理含有表格信息的结构化文本，又能处理自由式文本(如新闻报道)。IE系统的关键组成部分是一系列的抽取规则或模式，其作用是确定需要抽取的信息1。下面通过一个实例进行说明。第12章 Web信息抽取与问答系统如果要从文本中抽取运动会相关的信息，有一段文本如下：“1896年，雅典举行第一届奥运会，古代奥运会的复兴吸引了来自14个国家的选手参赛，最大的代表团来自希腊、德国、法国和英国。1896年4月6日，美国的詹姆斯康诺利赢得三级跳远的金牌，成为1500多年来首位奥运冠军，获胜者获得了一枚银质奖章和一个橄榄枝”。从这段文本信息中，抽取的奥运相关信息可以汇成表12-1。第12章 Web信息抽取与问答

3、系统这是一个典型的信息抽取实例，输入是一段文本，输出是格式化的文本，格式化了的文本展示了最重要或用户关心的信息。以上例子可以看出，信息抽取与信息检索密切相关，但两者之间也存在着巨大的差异，主要表现在三个方面：(1)两者功能不同。信息检索系统主要是从大量的文档集合中找到与用户需求相关的文档列表；而信息抽取系统则旨在从文本中直接获得用户感兴趣的事实信息。第12章 Web信息抽取与问答系统(2)处理技术不同。信息检索系统通常利用统计及关键词匹配等技术，把文本看成词的集合(bags of words)，不需要对文本进行深入分析理解；而信息抽取往往要借助自然语言处理技术，通过对文本中的句子以及篇章进行分

4、析处理后才能完成。(3)适用领域不同。由于采用的技术不同，信息检索系统通常是与领域无关的，而信息抽取系统则是和领域相关的，只能抽取系统预先设定好的有限种类的事实信息。另一方面，信息检索与信息抽取又是互补的：为了处理海量文本，信息抽取通常以信息检索系统(如文本过滤)的输出作为输入；而信息抽取技术又可以用来提高信息检索系统的性能。二者的结合能够更好地服务于用户的信息处理需求。第12章 Web信息抽取与问答系统12.1.1 信息抽取的发展信息抽取的发展信息检索已是一个较成熟的学科，其历史与文档数据库的历史一样长。但自动信息抽取技术则是近十年来发展起来的。从自然语言文本中获取结构化信息的研究最早开始于

5、20世纪60年代中期，这被看做是信息抽取技术的初始研究，它以两个长期的、研究性的自然语言处理项目为代表：美国纽约大学开展的Linguistic String项目和耶鲁大学的FRUMP系统。前者关注从医疗报告和记录中抽取信息格式，这就是模板(template)；后者关注故事理解，或从新闻报道中抽取某领域或场景信息。第12章 Web信息抽取与问答系统20世纪80年代，很多学者开始研究信息抽取技术，促使信息抽取技术发展的一个主要推动力来自消息理解会议MUC(Message Understanding Conference)2，从1987年到1998年，MUC共举办了七届，由美国国防高级研究计划委员会

6、发起和资助。MUC会议主要为设计信息抽取系统的人提供评测比较的任务描述、测试集、手工标注的结果场景等，它包括以下任务：(1)命名实体NE(Named Entities)：提取文本中相关的命名实体，包括人名、地名、机构/公司名称、有意义的数字表示等，例如：姚明、邓亚萍、北京奥组委等。(2)实体关系ER(Entity Relations)：提取命名实体之间的各种关系(事实)，例如：邓亚萍是北京奥组委的雇员。第12章 Web信息抽取与问答系统(3)模板场景(Template Scenario/Event Structures)：提取指定的事件，包括参加这些事件中的各个实体、属性及其中的关系，如北京奥

7、运会、时间、地点、运动员等。(4)共指(Coreference/Identity descriptions)：代词、名词的共指分析，即不同的实体表达了相通的含义。(5)模板合并(Template Merger)：把相同的事件合并为一个。从1999年开始，除了强大的应用需求，推动信息抽取技术发展的另一种会议是由美国标准局主持的自动内容抽取(Automatic Content Extraction，ACE)3，它仍然关注评测，包括两大任务：一是实体识别和跟踪，二是关系识别和描述。第12章 Web信息抽取与问答系统近年来，随着Web上信息的快速增长，基于Web文档的信息抽取开始受到研究人员的广泛关注

8、。比如卡耐基-梅隆大学的“Web挖掘(Mining the World Wide Web)”项目4。该项目的目标是通过自动地从Web中提取事实，来创建大型的、结构化的数据库，采用的主要技术是研究机器学习算法，通过训练，自动提取出有用的信息。第12章 Web信息抽取与问答系统12.1.2 信息抽取的评价指标信息抽取的评价指标信息抽取技术的评测主要还是采用经典的信息检索评价指标来定量评价，即查全率(Recall)和查准率(Precision)，但其内涵做了相应的改变。查全率可粗略地看成是正确抽取出的信息占抽取出的信息量的比例，而查准率是抽取出的信息中正确的信息量所占的比例。具体定义如下：查准率：o

9、ducedanswers_pr#swerscorrect_an#P查全率：ctsible_corretotal_poss#swerscorrect_an#R(12-1)(12-12)第12章 Web信息抽取与问答系统 综合评价指标：RPPRF22)1(12-3)这里，#correct_answers是指抽取出的结果中正确的信息条数，#answers_produced是指抽取到的信息条数，#total_possible_ corrects是指测试样本中的正确的信息条数。F是一个综合评价指标，越大，查全率对F的影响越大，一般取=1，这时P和R有同等的权重。第12章 Web信息抽取与问答系统12.2

10、 Web信息抽取信息抽取 根据处理对象的不同，信息抽取的对象可以是自由文本、半结构化文本和结构化文本等。当信息抽取针对的对象是Web信息时，称为Web信息抽取，Web信息是一种半结构化文本。对结构化文本的信息抽取相对容易。而针对自由文本和半结构化文本就复杂得多，针对自由文本的信息抽取通常使用自然语言处理技巧，抽取规则主要建立在词或词类间句法关系的基础上。本章关注的是Web信息，它是一种介于自由文本和结构化文本之间的数据，没有严格的格式，有时候也没有语法。用自然语言处理技巧对这样的文本并不一定有效，用来处理结构化文本的简单的规则处理方法也不一定有效。第12章 Web信息抽取与问答系统Web信息抽

11、取的主要目标是网页。网页中通常有自由文本，也有带标签的文本，即具有一定的结构，这种半结构化形式的文档为信息抽取过程同时带来便利和挑战。便利之处在于：由于HTML、XML等语言有着一定的语法规则，这些规则会给信息抽取过程带来启发；挑战在于：自然语言文本与各种标记混杂在一起增加了文档的复杂度。因此，尽管传统的信息抽取技术为Web信息抽取提供了重要基础，但它并不完全适合于从Web文档中提取信息。第12章 Web信息抽取与问答系统按照MUC会议建立的术语，信息抽取最终的输出结果称为模板，模板中的域称为槽(Slot)，而把信息抽取过程中使用的匹配规则称为模式(Pattern)，要提取的特定事件或关系称为

12、一个场景(Scenario)，而领域(Domain)的概念更宽一些，通常一个领域可以包含多个场景，比如在IT并购领域的新闻中，可能包含微软收购雅虎、中国电信重组联通等不同的场景。信息抽取的最终目的是从文档集合中提取出相关的信息，即得到模板，而一个信息抽取系统的核心构件是一组抽取模式(Extraction Patterns)或者抽取规则(Extraction Rules)，用于从每篇文档中抽取满足模板中的内容，抽取的过程实际上就是模板填充的过程。抽取规则可以人工制定，但大多数情况下由机器学习算法自动生成。第12章 Web信息抽取与问答系统实现Web信息抽取的程序又称为Wrapper，Wrappe

13、r可接受针对特定信息源的查询请求，并从该信息源中找出相关的网页，然后把需要的信息提取出来返回给用户。它由一系列的抽取规则以及应用这些规则的计算机程序代码组成。通常，一个Wrapper只能处理一种特定的信息源。从几个不同信息源中抽取信息，需要一系列的Wrapper程序库。Wrapper的运行速度应该很快，因为它们要在线处理用户的提问，还要能应付网络经常变化、运行欠稳定的特点。比如网络连接失败、文档格式混乱、格式变化等。第12章 Web信息抽取与问答系统12.2.1 基于关键字的基于关键字的Web信息抽取信息抽取根据Web信息发布的表现形式，建立一系列启发式规则；作信息抽取时，首先匹配关键字，再根

14、据预先定制好的规则，抽取相关的信息。能否抽取出满意的信息，关键是规则的制定，以下是一些常见的规则：(1)如果关键字出现在一个超链接的标签里，则超链接指向的页面内容为抽取的结果信息，如关键字为“蝶泳金牌”，新浪网上有个超链接，其标签为“刘子歌破纪录夺女200米蝶泳金牌”，其后的URL指向的页面就是抽取到的“蝶泳金牌”对应的结果信息。(2)若关键字出现在标题中，则抽取结果信息是跟在它后面的文本，直到出现下一个标题；如果关键字出现在最后一个标题，则抽取结果信息是跟在它后面的文本直到出现一个空行。第12章 Web信息抽取与问答系统(3)若关键字出现在项目(item)中或列表中，则抽取结果信息为紧跟在后

15、面的且直到下一个LI或表尾之间的文本。(4)若关键字是表(table)中的一个域，则对于纵向排列的表来说，抽取结果信息是位于关键字右边的域，而对于横向排列的表来说，抽取结果信息则是位于关键字下边的域。第12章 Web信息抽取与问答系统12.2.2 基于模式的基于模式的Web信息抽取信息抽取模式可以理解为字符串。基于模式的Web信息抽取的基本思想类似5.2.2的模式匹配：首先定义一个模式，然后在Web页面中搜索，找到跟模式匹配的字符串，然后抽取出所需要的信息。第12章 Web信息抽取与问答系统举一个实例来说明：有一个Web页面：“北京时间8月19日，北京奥运会男子3米跳板跳水决赛在国家游泳中心水

16、立方拉开战幕，这也是本次奥运会产生的第6枚跳水金牌。在此前决出的5枚金牌中，中国跳水梦之队大包大揽豪取全部五金，此役秦凯、何冲这对一稳一难的两位中国选手联袂冲金，最终何冲不负众望以572.90分摘得金牌，加拿大神童德斯帕蒂以536.90分夺银，秦凯以530.10分的成绩获得铜牌，中国跳水队连续四届获得了这枚男子三米板单人金牌，这也是中国军团在本次奥运会中夺得的第43金”。现在，要从这个Web页面中抽取出金牌得主，设计一个模式为：得金牌/人名，其中人名是一个变量，而得金牌则是一个字符串，然后在这个页面中搜寻“得金牌”这个字串，再把这个字串前面的人名作为抽取结果。在这个例子中，结果定位在“何冲不负

17、众望以572.90分摘得金牌”子句中，得到抽取结果：金牌得主“何冲”。第12章 Web信息抽取与问答系统事实上，要得到准确的抽取结果，模式的设计至关重要，可能需要比较复杂的模式。模式可以使用布尔操作进行连接，也可以在模式中使用通配符。比如仍然针对上述的这个Web页面，要求抽取出金牌得主、银牌得主、铜牌得主以及各自的分数。设计出这样的模式得金牌/人名*得银牌/人名*得铜牌/人名*分/数字or夺金/人名*夺银/人名*夺铜/人名*分/数字；最后抽取结果如表12-2所示。第12章 Web信息抽取与问答系统第12章 Web信息抽取与问答系统从布尔运算符or之前的模式可以抽取得到表中第2、4行的结果，而使

18、用布尔运算符or之后的模式可以抽取得到表中第3行的结果。隐马尔可夫模型(Hidden Markov Models，HMM)是最近几年在信息抽取中应用最广泛的提取模式表达模型5。HMM是一种随机的有限状态自动机，已成功应用于语音识别、手写体识别等领域。HMM最近几年被引入到信息抽取中，已经得到了成功的应用。HMM有非常适合自然语言处理的统计基础，对于新数据的处理有良好的鲁棒性，并且有成熟的学习算法，可应用在信息提取上。第12章 Web信息抽取与问答系统 对于HMM，有三个基本问题：(1)识别问题：给定一个输出序列和模型，模型可能创建的序列概率是什么？(2)序列问题：给定一个输出序列和模型，什么最

19、可能的状态序列可以创建输出序列？(3)训练问题：给定一个输出序列和拓扑结构，怎样调整模型参数，包括状态转移和输出的概率分布，使模型创建的输出序列具有最大概率？第12章 Web信息抽取与问答系统在信息提取中，涉及后两个问题。“序列问题”即是由模型对样本进行识别的过程，而“训练问题”正是各种基于HMM的信息提取所要解决的问题。最初的HMM构造是通过观察样本手工构造。或者一个状态对应一个域，或用几个状态对应一个域，然后通过对概率的调整来获得较好的效果。现在的HMM构造一般是采用自动构造。如在随机优化方法中，通过不断搜索可能的HMM结构，使之达到最好的提取效果；通过对句子成分的分析(如名词、名词短语等

20、)构造HMM等。这些方法都应用于“稀疏型”提取任务，即待提取文本中含有大量的无关信息。第12章 Web信息抽取与问答系统基于HMM的信息提取算法的优点是充分利用统计学的理论，对于新数据的适应性强，并且训练耗时短。其缺点是需要大量的训练数据，并且还缺乏通用的模型构造方法。在信息提取中，HMM用状态对应提取域，状态的词表对应每个域出现的符号，用状态之间的转换对应各个域之间的位置关系。最初的HMM构造是通过观察样本手工构造。或者一个状态对应一个域，或用几个状态对应一个域，然后通过对概率的调整来获得较好的效果。下面介绍一种基于隐马尔可夫模型的信息提取算法11。该算法利用文法推断中的Inferring

21、Transducer算法提取文本的符号特征，并利用状态合并途径生成隐马尔可夫模型的拓扑结构和利用最大似然方法学习隐马尔可夫模型的概率分布，最后采用修改的Viterbi算法进行识别。第12章 Web信息抽取与问答系统 一个HMM由以下几部分构成：(1)N=模型中的状态数；(2)M=模型中的输出符号数；(3)S=s1，s2，sN，模型中的状态；(4)A=aij，aij=P(sj at t+1|si at t)，状态转移的概率分布；(5)B=bj(k)，bj(k)=P(vk at t|sj at t)，在状态sj输出的符号概率分布，其中vk是输出符号集；(6)i，i=P(si at t=0)，初始状

22、态分布。第12章 Web信息抽取与问答系统用HMM来解决信息提取的一般途径是：每个域(提取的每个语义项)对应一个或多个状态，原始文本中的符号作为状态的输出符号，如果模型给定，那么信息提取过程就是搜索最可能创建符号序列的状态序列。这个问题可以由Viterbi算法7解决。由于HMM有成熟的学习算法和坚实的统计基础，所以在信息提取中是一种成功的模型。图12-1是一个用于信息提取的简单HMM。与有限状态自动机相对应的是各种类型的形式文法。也可以用各种形式文法(如上下文无关文法、正则文法等)来表示提取知识。第12章 Web信息抽取与问答系统图12-1 一个用于引文信息提取的简单HMM6第12章 Web信

23、息抽取与问答系统1.状态类型确定状态类型确定 简单的HMM每个状态对应一个域，这种模型可根据域个数自动生成，其特点是实现简单，但不能很好地刻画每个域内部的特征。一般而言，每个域都具有一定的线索，如年代由两位或四位数字组成，而形如“B.Obama”的字符串肯定是代表人名。“B”、“.”和“Obama”这样的被非数字字母符号隔开的字符串称之为token。可以仅仅根据这些token的形式而无需了解其内容就得出这是一个人名的结论。如果能把这些形式特征提取出来，把得到的每一个特征对应HMM的一个状态类型，这样就能刻画出域内部的特征。如“B.Obama”的符号特征是“B”+“.”+“capitalized

24、”。第12章 Web信息抽取与问答系统符号特征提取的方法有很多，例如可以借助于文法推断中的Inferring Transducers算法8。该算法用于域的文法模型构造，它将原始的域字符串转换成抽象的特征串，以便控制字母表的规模。算法自动学习待识别域内token的合理的抽象特征。算法的基本思路是：对每一个域，正例为域包含的token，反例为样本中包含的其他token。算法的目的是“贪心地(greedily)”将特征逐步添加到决策列表(decision list)中。选择特征的标准是该特征能够最好地区分正例和反例。每添加一个特征，从训练样本中删去已被该特征覆盖的正例，直到样本中的正例数小于某个预定

25、值。第12章 Web信息抽取与问答系统算法的输入包括标注好的训练样本和一个预定义的特征列表，输出是对应每个域。算法说明：(1)positivefeathashj和anyfeathash是映射表，分别记录每个特征在剩余样本第j个域的token上为真的次数和在所有的token上为真的次数。(2)函数fieldtokenuncoveredcount()计算未被决策表中特征覆盖的剩余样本第j个域的token数目。(3)函数anytokenuncoveredcount()计算未被决策表中特征覆盖的剩余样本所有token的数目。(4)函数do-positive-accounting()计算每个特征对剩余样

26、本第j个域的token为真的次数。第12章 Web信息抽取与问答系统(5)函数do-any-accounting()计算每个特征对剩余样本所有token为真的次数。(6)特征选择标准是使Gain(w)最大的特征w，由函数findbestfv()完成每一步的特征搜索。(12-4)mnnmfwww/)Gain(式中：n是保留在样本中的所有的token数目；fw是匹配w的正例token的数目；nw是匹配w的所有token的数目，取m=3。Inferring Transducers算法描述如下：第12章 Web信息抽取与问答系统第12章 Web信息抽取与问答系统【例例12-1】对下框给出的训练样本，生

27、成一个用于token特征产生的决策列表。beginlabel2/label.authorR.Agrawal/authorandauthorR.Srikant/author.titleMining sequential patterns/title.In Proc.of Int.Conf.on conferenceData Engineering/conference,Tasipei,Taiwan,Mar.year1995/year.End 预定义的特征列表如表12-3所示。得到的对应于“作者(author)”的决策列表如表12-4所示。第12章 Web信息抽取与问答系统第12章 Web信息抽取

28、与问答系统第12章 Web信息抽取与问答系统通过Inferring Transducers算法，可以确定每个域的内部状态类型，对于两个域之间的token，由于这些token是域之间分界的重要线索，例如“Aiken，Alexander，and Alexandru Nicolau”中含有3个作者名，3个人名之间的分界标记是“，”、“，”和“and”，所以保留它们的原始形式，用一个状态类型“word”表示。第12章 Web信息抽取与问答系统2 结构学习结构学习通过Inferring Transducers算法，确定了HMM中的状态类型后，可以使用以下状态合并方法生成HMM：(1)对剩余样本a的tok

29、en串，找到决策列表中第1个匹配的特征，将a转换成特征串a。(2)对a中的每个特征，生成一个状态结点，状态结点对应3项：label=域标签；type=特征；词表=a中对应的token，并根据a中特征的出现顺序，生成状态转换弧。对于现有模型中的任何两个状态结点sa，sb考查是否满足以下条件：sa.type=sb.type，sa.label=sb.label。第12章 Web信息抽取与问答系统 对应sa，sb，存在两条入弧或出弧e1、e2，对e1的另一个顶点se1和e2的另一个顶点se2有se1.type=se2.type，se1.label=se2.label。(3)如果满足这两个条件，则将sa

30、和sb合并。(4)重复步骤(1)、(2)和(3)，直到处理完所有的样本。在HMM结构确定的前提下，模型需要确定的参数有状态转换概率A和每个状态的符号概率分布B。由于在HMM中，对每个样本都存在一条唯一的路径，可以直接用“最大似然”方法来计算A和B：(12-5)MrjrjkjNjijijijkba11emitemit)(transitiontransition第12章 Web信息抽取与问答系统其中，transitionij是状态i到状态j的转换次数，emitjk是在状态j发出第k个符号的次数。为了避免训练数据不完整带来的“零概率”问题，需要对概率进行平滑。传统的概率平滑方法是拉普拉斯(Lapla

31、ce)平滑，但据分析绝对折旧(absolute discounting)方法更适合信息提取问题。对于bj(k)可以这样处理：(1)样本中每个出现符号的概率=bj(k)x；(2)每个未出现符号的概率=mjx/(mmj)；mj是状态j中出现的符号数，m是词表大小，x=1/(mj+m)。对于aij采取相同的处理方式。对于“状态合并”途径生成的HMM，A和B可以在合并过程中得到。第12章 Web信息抽取与问答系统3 信息识别信息识别 基于HMM的信息提取过程可以等同于：给定HMM和符号序列，寻找能使产生该符号序列的概率最大的状态序列，解决这个问题最经典的方法是viterbi算法7-8，如下所示：假设输

32、入的符号序列为o1，o2，oT，V+(i)是在状态i已经发出o1，o2，oT，的最大概率，Q+(i)是使V+(i)最大的t1时刻状态。(1)初始化：对 1iN，如果 si.type对于o1为真，则(12-6)0)()()(111iQobivii第12章 Web信息抽取与问答系统否则v1(j)=0(12-7)(2)递推计算：对1iN，2sT，如果si.type对于os为真，则(12-8)(maxarg)()()(max)(1111rvaiQobrvaivsriNrssisriNrs否则vs(i)=0 (12-9)(3)终态：(12-10)(maxarg)1(1*rvaqTTrNrT第12章 We

33、b信息抽取与问答系统其中，状态T+1表示结束状态。(4)回溯得到最优状态序列：对 t=T1，T2，1q*t=Qt+1(q*t+1)(12-11)q*1，q*2，q*T即为所求的状态序列。HMM对于密集型信息提取(要提取的域在位置上很靠近，并且无关文本较少)是一种合适的模型。因此该方法应用在引文信息的提取方面比较成功，这是因为引文信息从本质上讲是一种半结构化的文本，它的各个语义项的出现顺序有一定规律，而且各项之间有一些线索，而HMM的状态转移概率aij和符号发出概率bj(k)能表达这种规律，同时有viterbi算法根据aij和bj(k)进行识别，所以能够取得较好的效果。第12章 Web信息抽取与

34、问答系统12.2.3 基于样本的基于样本的Web信息抽取信息抽取基于样本的信息提取方法基于这样的假设，待抽取的Web页面具有相同或相似的结构和风格。抽取的基本思想是这样的：用户根据自己的信息需求，提供一个样本，描述这个样本中的目标信息，然后告诉系统，照葫芦画瓢，系统据此进行信息抽取，得到结果。例如，某书城发布的图书信息，具有同一的风格，选取一个样本如12-2所示，现在要从中抽取书名、作者、出版社、ISBN号、价格、折扣等信息，这些信息在Web页面中都有固定的位置和标记，把这些信息输入给系统，系统就可以从类似的页面中抽取出相应的信息，图12-3就是一个待抽取的Web页面。第12章 Web信息抽取

35、与问答系统图12-2 指定样本实例第12章 Web信息抽取与问答系统图12-3 待抽取的Web页面第12章 Web信息抽取与问答系统由于网页的结构复杂，包含各种相关链接、广告链接信息，因此在进行Web信息抽取之前，还必须去除与主题无关的噪声板块，可以采用第4章介绍的基于模板的网页去噪的方法去除噪声，从而提取主题块。在获得主题块后，可以进一步提取块内信息，下面介绍一种基于XML路径XPath9的信息抽取方法。主题数据块(Data Block)是指一个包含了用户想提取的所有提取项信息的网页区域。图12-4为某书城的数据页面，由4个数据块组成，每一个数据块包含一本书的信息。第12章 Web信息抽取与

36、问答系统图12-4 某书城的数据页面第12章 Web信息抽取与问答系统图12-5是一棵DOM树，其中T11、T12、T13是提取项，而B1是包含了这些提取项的数据块。P1、P2分别是从根节点到达两个数据块B1、B2的路径。通过观察，可以知道：一个数据块中的所有提取项总是具有相同的DOM父节点，而根节点到达不同的数据块的路径(XPath)是相似的。第12章 Web信息抽取与问答系统图12-5 DOM树、数据块、提取项示例第12章 Web信息抽取与问答系统基于XPath比较的数据块抽取规则生成算法的主要思想是通过对比数据块内两个不同的提取项对应的XPath，通过XPath的正向最长公共子串(For

37、ward Longest Common Sequence，FLCS)取出它们的公共部分得出一个数据块对应的XPath：P1。然后重复以上过程，得到另外一个数据块对应的XPath：P2。接下来通过对比P1和P2的下标得到所有数据块对应的XPath。一般来说，不同数据块之间XPath的HTML标记是相同的，不同的只是标记的下标，我们在匹配两个块的XPath时，使用通配符“*”来替代所有不同的下标，即可得到对应所有块的XPath：P，即数据块抽取规则R。根据R可以得到所有数据块的块内文字信息。第12章 Web信息抽取与问答系统【例例12-2】对图12-4的网页进行数据抽取。在这里每一本书的信息就是一

38、个数据块，包括名称、出版社、作者、价格、折扣、描述等提取项。对第一个数据块分别选取了“秋海棠”、“四十年代中国言情小说畅销纪录”两个提取项，得到如下对应的XPath：根据FLCS算法可得：第一个数据块对应的XPath为P1：/html1/body1/table5/tr5/td1/table1/tr1/td2同样，对第二个数据块分别选取了“凌叔华的文与画”、“去在自己所见及的一个世界里”两个提取项。可以得到：第12章 Web信息抽取与问答系统因此，第二个数据块对应的XPath为P2：/html1/body1/table5/tr6/td1/table1/tr1/td2对比P1、P2的下标序列，可以

39、得到第四个下标不同，将它替换成“*”可以得到所有块对应的XPath：/html1/body1/table5/tr*/td1/table1/tr1/td2 一般来说，数据密集型网站都是通过动态网页来展示后台数据库的数据，这些网站的网页基本上都是由一个或几个模板生成的。因此，对一个页面进行分析得到的抽取规则，可以应用于同一个模板的所有页面。第12章 Web信息抽取与问答系统12.3 问答系统问答系统问答系统和根据关键词检索并返回相关文档集合的传统搜索引擎有着根本的区别，问答系统的目标是精确回答用户用自然语言提出的问题，更强调精确性。问答系统既能够让用户用自然语言句子提问，又能够为用户返回一个简洁、

40、准确的答案，而不是一些相关的网页，这与普通搜索引擎有显著的不同，它能够更好地满足用户的检索需求，更准确地找出用户所需的答案。目前问答系统的研究大致可以分三类：基于常问问题集的问答系统、基于百科知识的问答系统以及开放域的问答系统10。也有人将问答系统分为基于知识库的问答系统、问答式检索系统和基于自由文本的问答系统。第12章 Web信息抽取与问答系统自动问答系统可以分为受限领域问答系统、开放领域问答系统和常见问题集(Frequently Asked Question)系统3种。受限领域问答系统仅仅关注某一个特殊领域，比如某个公司或医药领域的相关知识。因此可以将所有该领域的知识或者本体全部输入问答系

41、统中，以便用于分析问题或者答案来源，而答案来源则可以完全是结构化数据以简化处理。例如1961年Green在IBM7090平台上实现的用于回答关于美国棒球联盟问题的BASEBALL11系统是最早的自动问答系统之一，BASEBALL系统是一个受限领域的系统，该系统仅能回答一个棒球赛季的相关数据的问题。该领域的知识输入问答系统的完整性极大地影响了受限领域问答系统的性能。而且领域的内容会随着时间而发生变化，需要不断地更新问答系统的知识库。常见问题集系统是受限领域问答系统的特例，提供常用问题的问句-答案对。为了开发FAQ系统，开发人员必须在特定领域内搜集尽可能多的问句-答案对。很明显，FAQ集合越大，性

42、能越好，而现有的FAQ集一般是人工建立起来的，所以代价昂贵。开放领域的问答系统针对自然语言提出的问题从大规模文档集合中或从网络Web上提取答案。第12章 Web信息抽取与问答系统问答系统的起源可以追溯到“人工智能之父”图灵提出的“图灵测试”：一台电脑A和一个人B作为被测试者，观察者与被测试者之间是隔离的，然后观察者提出一系列问题，A和B分别回答，如果观察者能够根据回答区分出哪个是机器哪个是人，那么电脑A就没有通过图灵测试；反之，如果观察者不能够分辨出哪个是机器哪个是人，则电脑A就通过了图灵测试，并被认为具有人类的智慧。图灵还预言，总有一天，机器会具有人类的智能。1997年，计算机“深蓝”战胜国

43、际象棋世界冠军卡斯帕罗夫，电脑第一次战胜了人脑，也被誉为图灵预言的验证。第12章 Web信息抽取与问答系统Turing实验提出：如果计算机能够像人一样与人对话，就可以认为计算机有智能。研究者们为了探索语言理解技术，纷纷研究自然语言问答系统。从而使问答系统在19世纪80年代的自然语言处理领域风行一时。但由于当时的条件限制，所有的实验都是在非常受限的领域，甚至是固定段落上进行的，所以自动问答一直被限制为特殊领域的专家系统。此后，由于大规模文本处理技术的兴起，问答系统的研究受到了冷落。文本检索会议(TREC)在1999年的TREC会议(http:/tree.nist.gov/)上引入了对问答系统(Q

44、uestion Answering Track)12的评测后，基于自然语言的问答系统研究逐渐成为自然语言处理和信息检索领域中热门的研究。第12章 Web信息抽取与问答系统在TREC的支持下，面向大规模文本的英语书面通用QA系统的研究取得了很大的进展，涌现出了许多优秀的系统。Kupiec等人的MURAX13系统使用百科全书作为知识库，用以回答一般性的知识问题，他采用了基于统计与语言学知识相结合的技术，通过布尔搜索引擎和句法分析器从百科全书中抽取问题的答案。FAQFinder14则通过预先收集“问答对”并采用基于向量的搜索引擎来从相关的问答对文件中抽取答案。AskJeeves()公司是国际上第一个

45、提供自然语言问句接口的网络商业服务商，它的做法是人工收集大量的自然语言问句以及相应的URL链接，提取问句的问题模板并进行人工或者半自动的分类。第12章 Web信息抽取与问答系统麻省理工学院人工智能实验室的Start(http:/start.csail.mit.edu)15-16于1993年发布，是第一个基于Web的自动问答系统，可以回答一些有关地理、历史、文化、科技、娱乐等方面的简单问题。Start系统使用主体关系对象三元组的形式存放系统知识以及回答问题，采用基于知识库和信息检索的混合模式。如果用户查询在它的知识库中可以找到，则直接反馈；如果没有，则通过搜索引擎检索并处理后以相关段落形式反馈给

46、用户。第12章 Web信息抽取与问答系统密歇根大学的AnswerBus(http:/answerbus.coli.unisaarland.de)17是一个面向开放领域的问答系统，它接受自然语言的提问，从Web中提取问题可能的答案(一个或多个)，其特点是能支持多种语言提问方式。它不仅可以回答英语的问题，还可以回答法语、西班牙语、德语、意大利语和葡萄牙语的问题。不管是哪种问答系统，都会用到一些技术，如信息抽取、信息检索、自然语言处理技术等。我们这里主要关注面向Web的开放领域的问答系统。开放领域的问答系统是一个新兴的研究领域，它针对自然语言提出的问题从大规模文档集合中提取答案，其体系结构一般包括三

47、个主要部分:第12章 Web信息抽取与问答系统(1)问题处理部分：对用户用自然语言提出的问题进行预处理，包括词法、句法、语义等方面的分析，得到用户查询的关键词、查询句的关注焦点和用户问题所属类型。(2)信息检索部分：通过传统信息检索技术获得答案可能所在的文档，并对文档进行排序。(3)答案抽取部分：对信息检索得到的候选文档进行词法、句法、语义等方面的分析，并根据查询问题所属类别，抽取出答案，返回给用户。一个典型的开放领域的自动问答系统的结构如图12-6所示。第12章 Web信息抽取与问答系统图12-6 基于搜索引擎的开放领域问答系统的结构示意图第12章 Web信息抽取与问答系统上述自动问答系统的

48、工作流程如下所述：(1)用户通过人机交互接口提交自然语言问题；(2)该请求被自然语言分析器(Natural Language Parser)处理，构造问题短语的结构树；(3)该树被送到问题分类器(Classifier)，确定答案的类型；(4)查询解析器(Query Formulator)将问题转化为一组搜索引擎的查询表达式，被并行地提交给搜索引擎，搜索引擎获取相关结果网页；(5)从这些结果网页中，采用答案抽取(Answer Extraction)技术提取相关片断，称为摘要(Summaries)，并产生一系列可能的候选答案；第12章 Web信息抽取与问答系统(6)答案选取器(Answer Sel

49、ector)将候选答案进行排序，并将排序结果呈现给用户。上述过程可以归纳成三个核心模块：问题分析、信息检索和答案抽取。(1)问题分析。对于用户提交的问题，首先要对问题进行分析，要理解用户要问的是什么。比如，用户输入自然语言表达的问题“西藏有境内哪些山峰？”首先进行自然语言处理，包括中文分词，然后对问题进行分类，可知这是一个询问中国身份的自然地理条件类的问题。问题的分析一般包括自然语言处理、问题的分类、关键词的提取和关键词扩展等；如果是中文，还需要进行中文分词处理。第12章 Web信息抽取与问答系统(2)信息检索。通过问题分析而得到的关键词集，进行查询表达，提交给信息检索模块或搜索引擎，查找可能

50、包含问题答案的页面或文档。(3)答案抽取。信息检索模块返回的通常是一堆可能包含答案的网页。答案抽取模块从这些相关网页中找出相关的答案片段，一句话，或者是一段话，提交给用户。答案抽取是问答系统非常关键的一部分，也是难度较大的一部分，如果答案抽取模块不能准确地把正确答案抽取出来，将直接影响整个问答系统的准确性。第12章 Web信息抽取与问答系统有些问答系统除了上述三个部分之外还包括一个常问问题(FAQ)库，把用户经常问的问题及其答案保存起来。有了FAQ 库之后，用户问的问题首先和FAQ中的问题进行比对，即相似度计算，如果找到相同或相似的问题，就可以直接把FAQ 库中这个问题的答案返回。这样，对于用