基于决策树和马尔科夫链的互联网应答系统

基于决策树和马尔科夫链的互联网应答系统

1自动答对系统实验数据集和自动抽样问题随着互联网的快速发展，人们所需要的大部分知识都可以存在于互联网的一些网站上，但如何快速有效地检索用户需要的信息，已成为互联网应用中一个众所周知的技术问题。自动问答系统、个性化搜索、社区搜索、搜索结果自动排序是解决这些技术问题的有效研究方法。本文是面向基于问答对库的自动问答系统的需要,开展互联网上问答对的自动抽取研究。自动问答系统是一种支持用户以自然语言方式给出自己问题(或需要搜索的知识)的答案搜索系统,同时反馈给用户更直接、更精简的答案。例如当用户希望了解“哪个国家是最大的内陆国”时,用户可以直接将上述自然语言的句子输入自动问答系统,则系统将直接给出答案:“哈萨克斯坦”,而不需要再从通用搜索引擎上搜索“内陆国最大”得到的大量网页链接中去找寻真正的答案。基于大规模问答对库的自动问答系统是问答系统中比较简单和有效的技术路线,此种技术对用户输入的问题,从预先保存好的大规模已经回答过的问题中寻找最为合适的,并将其答案部分直接反馈给用户,所以对答案生成和问题理解技术相对来说依赖得比较少。问答对的规模是影响基于问答对的自动问答系统最终性能的主要因素,因此如何搜集大规模高质量的问答对是一项具有实际意义和研究价值的科研课题。现实中,互联网上已经积累了非常大规模的问答对,这些问答对大多以FAQ页面或者某些类似于BBS的网站上一问多答方式存在,如图1所示的是一个典型的包含多个问答对的FAQ页面。如果能自动收集起来这些问答对,将对基于问答对的自动问答系统提供非常有利的支撑。然而互联网上的问答对只是面向网页浏览用户而设计和书写的,一般仅仅是以HTML甚至简单文本方式存储,书写格式更是没有统一的规范,因此如何从这些不规范的问答对网页中,抽取出格式化的问答对,是一个比较典型的信息抽取问题,也是一个比较有挑战的问题。我们在网上搜集了500个网页(为了得到更多的问答对,这里的网页通过在商用搜索引擎上搜索关键字“FAQ”获得的),经过统计,明显带有表征问题对的关键字(如:“问”、“答”)的问答对只有651对,只占全部2113个问答对的30.81%。本文计划聚焦这一问答对抽取问题,提出一种基于决策树和马尔科夫链的自动抽取算法。实验结果表明,我们的方法效果显著,准确率达到了98.97%。就我们的调研范围,目前还没有此方面的研究成果发表。2基于机器学习的信息抽样研究一般来说,在信息抽取领域主要存在两种信息抽取的方法:基于规则的方法和基于机器学习的方法。由于互联网网页的格式不统一,基于规则的方法存在规则不易构造且普适性很难保证等问题,因此目前的研究更多采用基于机器学习方法进行信息抽取。在本文中我们也采用了基于机器学习的方法进行问答对的自动抽取研究。互联网上信息抽取领域前人已经做了很多研究:比如新闻信息的提取;文献提出了一种在网页中提取标题的方法,本文在特征选择上部分借鉴了文献的方法;文献给出了一种采用统计方法结合受限自然语言理解技术的模糊关键词集合提取方法。3基于多媒体文件学习的时代分类方法本文将采用机器学习和马尔可夫链相结合的方法进行问答对抽取工作。本方法适用于互联网上大多数的网页。主要分为两步来完成:训练和抽取。在训练过程中我们首先把HTML文件转变为DOM树的形式,然后针对DOM树中每一个有内容的叶子节点提取特征,通过C4.5决策树算法建立分类模型。具体各部分工作如下:3.1树状结构的建立由于HTML的“标记”只是告诉浏览器如何显示所定义的信息,故由HTML语言所表述的Web页面不适合由机器处理。当前主要采用DOM树来进行信息抽取。预处理的目标是将新闻网页的HTML脚本转化为只包含有意义信息的树状结构。具体步骤如下:(1)删除新闻网页HTML脚本中的与正文抽取不相关的信息,如注释、Java代码等;(2)建立树状结构。网页的HTML脚本本身是嵌套的,因此我们可以比较容易的根据HTML的脚本建立成对应的树状结构(即DOM树),并将所有的文字信息挂接在叶子节点,同时把HTML的转义字符都变换为正常的字符,如“<”变换为“<”,“&”变换为“&”等,并删除所有不包含任何文字的叶子节点;(3)合并段落。我们通过观察发现,问答对的问题或答案本身部分一般都不会跨越网页的段落,因此我们的实验以段落为最小决策单元。这里的段落指网页中在同一行内显示,而未被〈p〉、〈br〉、〈h1〉等HTML分段指示标记分隔开的文字片段。但是因为一个段落中有时会因为包含一些字体约束标记等HTML标记而在建立树状结构时被拆分成了多个叶子节点,因此我们需要进行段落合并处理,使得每个叶子对应一个段落。合并段落就是把所有中间没有段落边界标记的相邻叶子节点合并为一个节点。依据HTML的标记定义,通过分析网页在浏览器中的显示与该页面的源代码的对应关系,可以发现下列的标记是分段指示标记:〈P〉、〈BR〉、〈H1〉、〈H2〉、〈H3〉、〈H4〉、〈H5〉、〈H6〉、〈TABLE〉、〈TR〉、〈HR〉、〈DIV〉和〈CENTER〉,而源HTML脚本中的回车符则是可以忽略的。我们定义预处理完成后的树状结构为DOM树,图2给出了图1所示网页对应的DOM树(局部)。3.2学习阶段和算法DOM树建立之后,本文以DOM树上每一个叶子节点作为问答对的问题或答案的候选,于是文本的研究目标就具体化为一个典型的分类决策问题,决策每个叶子节点是三种类别中的哪一种,三种类别分别是:问题部分、答案部分以及什么都不是(以下分别记为Q,A和N三个类别)。本文计划引入机器学习的方法来建立这样分类器。基于机器学习的分类器构建一般被称为训练阶段,一般需要经过三个阶段:训练数据标注、特征提取和分类器训练。本文的训练阶段具体操作如下:(1)收集了一批网页,并生成对应的DOM树,并在专门研发的标注工具支持下,人工标注了每个叶子节点分别是Q、A和N三类别中的哪一类,完成用于训练的标注网页集构建;(2)对于这些DOM树中的每一个节点,本文提取多维特征组成的一个特征向量,并与人工标记的类别组合在一起形成一个训练例子,所有这些样例就组成了训练数据文件;(3)基于训练数据文件,完成分类器训练。有多种机器算法可以从这些训练数据中训练得到分类模型,本文采用了其中的一种,决策树算法,具体的本文采用了C4.5算法,具体算法参见文献。通过C4.5算法的训练程序,我们可以训练得到一棵分类决策树。当我们需要对一个新网页进行问答对抽取时,这一问题可以同理转换为新网页所对应的DOM树每个叶子节点分别是哪个类别,这一阶段一般被称为决策或测试阶段。这一阶段具体操作如下:对每个叶子节点提取一个同训练阶段一样的特征向量,然后把这一向量输入到训练过程得到的分类决策树进行判决,以得到这一叶子节点分别属于Q、A及N三个类别的决策概率;最后把决策概率最大的类作为判断结果输出。与大部分机器学习算法相似,对于C4.5算法来说最重要的是特征的选择,特征能否反映分类问题的本质,决定了整个分类器构建的成败。3.3特征的提取过程在3.2小节中提到的,要想利用分类模型算法得到很好的分类效果,关键就是找到能够反映分类问题本质的特征。本文中,针对问答对抽取的分类问题,本文最多一共尝试提取了71维的特征,但考虑到效率和特征对于判断结果的影响,最终我们选择了其中的31维特征,实验表明这31维特征能够很好的从所有的DOM树的叶子节点中区分出问题部分以及答案部分。在特征的提取过程中,本文主要考虑了以下信息和结构特征,具体31维特征定义如表1所示。(1)网页的纯文本信息;网页的结构、格式信息,如当前节点文字的颜色、字体信息,链接信息以及相邻节点是否有相同结构,即两个节点的XPath中是否仅仅差别一个索引号,如图2中选中的“Q第五大区(电信—上海)…”节点与其上下并排的几个节点就都属于具有相同结构的节点,简称同构节点。XPath的具体定义参见文献;(2)全局信息,利用了BhnI等的研究工作,在文献中BhnI利用在归纳学习过程中加入了上下文规则较大幅度的提高了查准率。4问答和提取4.1q、a和n之间的关系基于决策树的问答对抽取算法实现了对每个DOM树叶子节点的类别判决,但整个判决过程中假设各个节点的类别决策之间相互独立。然而这一假设显然不成立,因为,在一个网页中比较Q、A和N之间存在一定的顺序关系,如A之前一般必须有Q,而Q之后往往也会有A,同时由于一般而言问题极少跨越多个段落(即Q后一般不接Q),而答案部分则比较容易因为内容较长而分割成多个段落(因此会有多个A连续出现的情况)。因此为了修正决策树的独立决策的不当,这些不同的概率特性可以很好。为了克服仅仅基于决策树的问答对自动抽取技术的缺陷,同时考虑到上述类别之间的相互关系可以用马尔科夫链来描述,因此本文加入了一阶马尔可夫链模型对决策树的决策结果进行修正。4.2基于动态规划的viterbi算法这里假设训练集内的每个标注页面都可以按其DOM树叶子节点的类别表示为一个Q、A和N三个字母组成的长串,则我们可以从这些长串中统计得到三个类别之间的3*3的转移矩阵,记为T(d|c),其中c,d∈{Q,A,N},且:T(d|c)=Count(cd)Count(c)(1)Τ(d|c)=Count(cd)Count(c)(1)公式(1)中,Count(cd)表示类别c后紧接着出现类别d的次数,Count(c)表示类别c出现的次数。因此假设对于一个新的网页所对应DOM树,假设叶子节点个数为L个,则基于决策树的方法可以得到这L个叶子节点作为每一个类别的概率P(xi=ci),1≤i≤L,ci∈{Q,A,N}。考虑到各个节点类别判决结果之间的相互关系,本文采用基于动态规划的Viterbi算法从3L种可能的判决结果中搜索出一条最佳的路径(记为(c1,…,ci,…,cL)*,ci∈{Q,A,N}),使得该路径满足:(c1,c2,⋯,cL)∗=argmax(c1,c2,⋯,cL)∏i=1LT(ci|ci−1)×P(xi=ci)(2)(c1,c2,⋯,cL)*=argmax(c1,c2,⋯,cL)∏i=1LΤ(ci|ci-1)×Ρ(xi=ci)(2)这种方法的实验结果与没有加入马尔科夫链修正的结果相比效果不但没有上升,反而下降比较明显。通过分析发现,这是由于在大部分网页中问答对存在的数目与所有的节点数目相比要少的多,这使得求出的条件概率中T(N|N)特别大,在(2)式中占主导地位,结果很容易就把所有的节点被判为N类。针对这一问题,我们通过大量的观察统计,发现了这样的一条规律:一般情况下答案(问题)有多行时所对应的叶子节点会集中在一个相同的父节点之下,这为我们的研究指明了方向,本文正是利用当前节点与其前一节点是否具有相同结构这一信息来对我们3*3转移概率矩阵T(d|c)进行了修正:(1)定义T′(d|c)为:T′(d|c)=Count(cd)Count(c),c与d同构(3)Τ′(d|c)=Count(cd)Count(c),c与d同构(3)(2)决策时,但前后节点同构时,采用T′(d|c)作为转移概率,否则仍采用T(d|c)。实验表明,同构这一限制使得大部分的N节点被排除在分母的统计之中,实现了Q、A和N三种类别之间的有效平衡。4.3q、a定义的抽样当我们根据上面的决策和修正算法得到叶子节点所对应的类别序列(c1,…,ci,…,cL)*之后,我们将按Q、A顺序出现的相隔最近的一对Q、A定义并抽取为一个问答对,这是由于一般情况下答案都会紧跟在所回答的问题的后面,这样做在最后的选择结果中过滤掉了分类结果不能构成问答对的节点,如比所有Q都先出现的A或是比所有A都后出现的Q。4.4简化答对的操作为了能把抽取到的问答对应用到实际的自动问答系统中,问答对抽取必须保证有一个很高的准确率,因此为了进一步提高抽取的准确率,我们对上一小节得到的问答对我们采用基于以下简单规则的取舍操作:(1)删除最后的问答对,这是由于往往最后一个问答对可能会存在多余的信息;(2)当一个网页的问答对数目小于两个时,忽略抽取结果;(3)当答案为多段时,为了得到的答案很完整,当答案的段数大于3时,舍弃这个问答对。这样操作之后,将在舍弃一部分问答对的基础上,较明显的提高抽取出的问答对的准确率。我们提出这一面向准确率的抽取方法是考虑到互联网的网页规模庞大,因此在一个网页中漏掉的信息很可能可以在其他网页中找到。5结果5.1q和a都与q和a一致时为了对比不同问答对自动抽取的效果,本文采用准确率(Precision)、召回率(Recall)及F1-Score指标来进行抽取性能的评价。这里我们记A为人工判断为问答对的集合,B为机器自动抽取得到问答对的集合。这里我们定义当且仅当机器抽取的问答对的Q和A都与人工标注的Q和A完全一致时,才认为此问答对被正确的抽取。准确率、召回率及F1-Score定义如下:Precision=∥A∩B∥|B|×100%Recall=∥A∩B∥|B|×100%(4)F1−Score=2*Precision*RecallPrecision+Recall(5)Ρrecision=∥A∩B∥|B|×100%Recall=∥A∩B∥|B|×100%(4)F1-Score=2*Ρrecision*RecallΡrecision+Recall(5)F1-Score是准确率与召回率结合起来进行评判的方法,更能够客观的反映实验模型的效果。5.2规范标注网页集为了实验本文提出的基于决策树和马尔科夫链的问答对自动抽取技术,本文数据集为以“FAQ”为关键词利用Google中文搜索引擎搜索得到前500个网页(2005年9月收集)。我们对这500个网页转化为DOM树并基于自行研发的标注工具在DOM树上标注出所有的Q和A类型的叶子节点,形成了标注网页集。统计表明,此500个网页的标注集上,人工一共标注了2113个问答对。鉴于本文建设的数据集规模较小以及问答对标注工作量较大,因此本文采用4-Fold的交叉