基于决策树和马尔可夫链的问答对自动提取
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于决策树和马尔可夫链的问答对自动提取范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
(中国科学技术大学 电子工程与信息科学系，安徽 合肥 230027)
摘 要：问答系统能用准确、简洁的答案回答用户用自然语言提出的问题，很明显系统中问答对的规模是影响问答系统最终性能的主要因素。为了提高问答对的规模、充分利用互联网资源，本文提出了一种基于决策树和马尔科夫链的在互联网上自动抽取问答对的算法。先根据网页中的HTML标记把网页表示成一棵DOM树；然后利用树中每个节点的结构和文字信息，抽取相应的特征；最后将得到的节点特征通过由决策树和一阶马尔可夫链结合得出的分类模型进行分类。试验结果表明准确率达到了90.398％，召回率达到了86.032％。对大量网页抽取的结果表明该分类模型能够适应对各种各样的网页的抽取。
关键词：人工智能；模式识别；信息抽取；DOM树；决策树；马尔可夫链
中图分类号：TP391 文献标识码：A
1 概述
伴随着互联网的迅速发展，理论上人类所需要的大部分知识都可能存在于互联网的某些网页上，但如何快速有效的从庞大的网络中检索出用户所需要的信息，已经成为了互联网应用中一个倍受大家关注的技术难题，自动问答系统、个性化搜索、社区搜索、搜索结果自动归类等相关技术和服务的提出，都是面向这样技术难题开展的卓有成效的研究路线。本文是面向基于问答对库的自动问答系统的需要，开展互联网上问答对的自动抽取研究。
自动问答系统是一种支持用户以自然语言方式给出自己问题(或需要搜索的知识)的答案搜索系统，同时反馈给用户更直接、更精简的答案。例如当用户希望了解“哪个国家是最大的内陆国”时，用户可以直接将上述自然语言的句子输入自动问答系统，则系统将直接给出答案：“哈萨克斯坦”，而不需要再从通用搜索引擎上搜索“内陆国最大”得到的大量网页链接中去找寻真正的答案。基于大规模问答对库的自动问答系统是问答系统中比较简单和有效的技术路线，此种技术对用户输入的问题，从预先保存好的大规模已经回答过的问题中寻找最为合适的，并将其答案部分直接反馈给用户，所以对答案生成和问题理解技术相对来说依赖得比较少。
问答对的规模是影响基于问答对的自动问答系统最终性能的主要因素，因此如何搜集大规模高质量的问答对是一项具有实际意义和研究价值的科研课题。现实中，互联网上已经积累了非常大规模的问答对，这些问答对大多以FAQ页面或者某些类似于BBS的网站上一问多答方式存在，如图1所示的是一个典型的包含多个问答对的FAQ页面。如果能自动收集起来这些问答对，将对基于问答对的自动问答系统提供非常有利的支撑。然而互联网上的问答对只是面向网页浏览用户而设计和书写的，一般仅仅是以HTML甚至简单文本方式存储，书写格式更是没有统一的规范，因此如何从这些不规范的问答对网页中，抽取出格式化的问答对，是一个比较典型的信息抽取问题，也是一个比较有挑战的问题。我们在网上搜集了500个网页(为了得到更多的问答对，这里的网页通过在商用搜索引擎上搜索关键字“FAQ”获得的)，经过统计，明显带有表征问题对的关键字(如：“问”、“答”)的问答对只有651对，只占全部2113个问答对的30.81％。本文计划聚焦这一问答对抽取问题，提出一种基于决策树和马尔科夫链的自动抽取算法。实验结果表明，我们的方法效果显著，准确率达到了98.97％。就我们的调研范围，目前还没有此方面的研究成果发表。
2 相关工作
一般来说，在信息抽取领域主要存在两种信息抽取的方法：基于规则的方法和基于机器学习的方法。由于互联网网页的格式不统一，基于规则的方法存在规则不易构造且普适性很难保证等问题，因此目前的研究更多采用基于机器学习方法进行信息抽取[1～4]。在本文中我们也采用了基于机器学习的方法进行问答对的自动抽取研究。
互联网上信息抽取领域前人已经做了很多研究：比如新闻信息的提取[4]；文献[5]提出了一种在网页中提取标题的方法，本文在特征选择上部分借鉴了文献[5]的方法；文献[6]给出了一种采用统计方法结合受限自然语言理解技术的模糊关键词集合提取方法。
3 基于决策树的分类模型
本文将采用机器学习和马尔可夫链相结合的方法进行问答对抽取工作。本方法适用于互联网上大多数的网页。主要分为两步来完成：训练和抽取。在训练过程中我们首先把HTML文件转变为DOM树的形式，然后针对DOM树中每一个有内容的叶子节点提取特征，通过C4.5决策树算法建立分类模型。具体各部分工作如下：
3.1建立网页的DOM树
由于HTML的“标记”只是告诉浏览器如何显示所定义的信息，故由HTML语言所表述的Web页面不适合由机器处理。当前主要采用DOM树来进行信息抽取[2,7,8]。
预处理的目标是将新闻网页的HTML脚本转化为只包含有意义信息的树状结构。具体步骤如下：
(1)删除新闻网页HTML脚本中的与正文抽取不相关的信息，如注释、Java代码等；
(2)建立树状结构。网页的HTML脚本本身是嵌套的，因此我们可以比较容易的根据HTML的脚本建立成对应的树状结构(即DOM树)，并将所有的文字信息挂接在叶子节点，同时把HTML的转义字符都变换为正常的字符，如“& 1t；”变换为“
(3)合并段落。我们通过观察发现，问答对的问题或答案本身部分一般都不会跨越网页的段落，因此我们的实验以段落为最小决策单元。这里的段落指网页中在同一行内显示．而未被、(h1>等HTML分段指示标记分隔开的文字片段。但是因为一个段落中有时会因为包含一些字体约束标记等HTML标记而在建立树状结构时被拆分成了多个叶子节点，因此我们需要进行段落合并处理，使得每个叶子对应一个段落。合并段落就是把所有中间没有段落边界标记的相邻叶子节点合并为一个节点。依据HTML的标记定义，通过分析网页在浏览器中的显示与该页面的源代码的对应关系，可以发现下列的标记是分段指示标记
3.2分类模型建立
DOM树建立之后，本文以DOM树上每一个叶子节点作为问答对的问题或答案的候选，于是文本的研究目标就具体化为一个典型的分类决策问题， 决策每个叶子节点是三种类别中的哪一种，三种类别分别是：问题部分、答案部分以及什么都不是(以下分别记为Q，A和N三个类别)。本文计划引入机器学习的方法来建立这样分类器。
基于机器学习的分类器构建一般被称为训练阶段，一般需要经过三个阶段：训练数据标注、特。征提取和分类器训练。本文的训练阶段具体操作如下：
(1)收集了一批网页，并生成对应的DOM树，并在专门研发的标注工具支持下，人工标注了每个叶子节点分别是Q、A和N三类别中的哪一类，完成用于训练的标注网页集构建；
(2)对于这些DOM树中的每一个节点，本文提取多维特征组成的一个特征向量，并与人工标记的类别组合在一起形成一个训练例子，所有这些样例就组成了训练数据文件；
(3)基于训练数据文件，完成分类器训练。有多种机器算法可以从这些训练数据中训练得到分类模型，本文采用了其中的一种，决策树算法，具体的本文采用了C4.5算法，具体算法参见文献[9]。通过C4.5算法的训练程序，我们可以训练得到一棵分类决策树。
当我们需要对一个新网页进行问答对抽取时，这一问题可以同理转换为新网页所对应的DOM树每个叶子节点分别是哪个类别，这一阶段一般被称为决策或测试阶段。这一阶段具体操作如下：对每个叶子节点提取一个同训练阶段一样的特征向量，然后把这一向量输入到训练过程得到的分类决策树进行判决，以得到这一叶子节点分别属于Q、A及N三个类别的决策概率；最后把决策概率最大的类作为判断结果输出。
与大部分机器学习算法相似，对于C4.5算法来说最重要的是特征的选择，特征能否反映分类问题的本质，决定了整个分类器构建的成败。
3.3特征的选择
在3.2小节中提到的，要想利用分类模型算法得到很好的分类效果，关键就是找到能够反映分类问题本质的特征。本文中，针对问答对抽取的分类问题，本文最多一共尝试提取了71维的特征，但考虑到效率和特征对于判断结果的影响，最终我们选择了其中的31维特征，实验表明这31维特征能够很好的从所有的DOM树的叶子节点中区分出问题部分以及答案部分。
在特征的提取过程中，本文主要考虑了以下信息和结构特征，具体31维特征定义如表1所示。
(1)网页的纯文本信息；
网页的结构、格式信息，如当前节点文字的颜色、字体信息，链接信息以及相邻节点是否有相同结构，即两个节点的XPath中是否仅仅差别一个索引号，如图2中选中的“Q第五大区(电信一上海)…”节点与其上下并排的几个节点就都属于具有相同结构的节点，简称同构节点。XPath的具体定义参见文献[10]；
(2)全局信息，利用了BhnI等的研究工作，在文献[11]中BhnI利用在归纳学习过程中加入了上下文规则较大幅度的提高了查准率。
4 问答对的抽取
4.1 基于决策树方式的缺陷
基于决策树的问答对抽取算法实现了对每个DOM树叶子节点的类别判决，但整个判决过程中假设各个节点的类别决策之间相互独立。然而这一假设显然不成立，因为，在一个网页中比较Q、A和N之间存在一定的顺序关系，如A之前一般必须有Q，而Q之后往往也会有A，同时由于一般而言问题极少跨越多个段落(即Q后一般不接Q)，而答案部分则比较容易因为内容较长而分割成多个段落(因此会有多个A连续出现的情况)。因此为了修正决策树的独立决策的不当，这些不同的概率特性可以很好。为了克服仅仅基于决策树的问答对自动抽取技术的缺陷，同时考虑到上述类别之间的相互关系可以用马尔科夫链来描述，因此本文加入了一阶马尔可夫链模型对决策树的决策结果进行修正。
4.2 利用一阶马尔可夫链修正结果的方法
这里假设训练集内的每个标注页面都可以按其DOM树叶子节点的类别表示为一个Q、A和N三个字母组成的长串，则我们可以从这些长串中统计得到三个类别之间的3*3的转移矩阵，
这种方法的实验结果与没有加入马尔科夫链修正的结果相比效果不但没有上升，反而下降比较明显。通过分析发现，这是由于在大部分网页中问答对存在的数目与所有的节点数目相比要少的多，这使得求出的条件概率中T(N|N)特别大，在(2)式中占主导地位，结果很容易就把所有的节点被判为N类。
针对这一问题，我们通过大量的观察统计，发现了这样的一条规律：一般情况下答案(问题)有多行时所对应的叶子节点会集中在一个相同的父节点之下，这为我们的研究指明了方向，本文正是利用当前节点与其前一节点是否具有相同结构这一信息来对我们3*3转移概率矩阵T(d|f)进行了修正：
实验表明，同构这一限制使得大部分的N节点被排除在分母的统计之中，实现了Q、A和N三种类别之间的有效平衡。
4.3对整个网页的所有判断结果进行问答对的选择
当我们根据上面的决策和修正算法得到叶子节点所对应的类别序列(c1,…ci，…，cL)*之后，我们将按Q、A顺序出现的相隔最近的一对Q、A定义并抽取为一个问答对，这是由于一般情况下答案都会紧跟在所回答的问题的后面，这样做在最后的选择结果中过滤掉了分类结果不能构成问答对的节点，如比所有Q都先出现的A或是比所有A都后出现的Q。
4.4面向准确率的问答对取舍
为了能把抽取到的问答对应用到实际的自动问答系统中，问答对抽取必须保证有一个很高的准确率，因此为了进一步提高抽取的准确率，我们对上一小节得到的问答对我们采用基于以下简单规则的取舍操作：
(1)删除最后的问答对，这是由于往往最后一个问答对可能会存在多余的信息；
(2)当一个网页的问答对数目小于两个时，忽略抽取结果；
(3)当答案为多段时，为了得到的答案很完整，当答案的段数大于3时，舍弃这个问答对。
这样操作之后，将在舍弃一部分问答对的基础上，较明显的提高抽取出的问答对的准确率。我们提出这一面向准确率的抽取方法是考虑到互联网的网页规模庞大，因此在一个网页中漏掉的信息很可能可以在其他网页中找到。
5 实验结果
5.1 评测指标
为了对比不同问答对自动抽取的效果，本文采用准确率(Precision)、召回率(Recall)及F1－Score指标来进行抽取性能的评价。这里我们记A为人工判断为问答对的集合，B为机器自动抽取得到问答对的集合。这里我们定义当且仅当机器抽取的问答对的Q和A都与人工标注的Q和A完全一致时，才认为此问答对被正确的抽取。准确率、召回率及F1-Score定义如下：
F1-Score是准确率与召回率结合起来进行评判的方法，更能够客观的反映实验模型的效果。
5.2数据集
为了实验本文提出的基于决策树和马尔科夫链的问答对自动抽取技术，本文数据集为以“FAQ”为关键词利用Google中文搜索引擎搜索得到前500个网页(2005年9月收集)。我们对这500个网页转化为DOM树并基于自行研发的标注工具在DOM树上标注出所有的Q和A类型的叶子节点，形成了标注网页集。统计表明，此500个网页的标注集上，人工一共标注了2113个问答对。
鉴于本文建设的数据集规模较小以及问答对标注工作量较大，因此本文采用4-Fold的交叉集测试方法[12]进行试验。
5.3 实验结果
这里我们采用的基线系统是“带有表征问题对的关键字的方法”，具体是指通过规则的方式，将带有表征问答对的关键的问答对抽取出来的方法。如表2所示，与基线系统相比，只用决策树的方法可以大幅度提升抽取效果，F1-Score绝对提升幅度达到34.71％。同时，基于决策树和一阶马尔可夫链相结合的方法可以进一步提高问答对抽取性能，相比决策树方法提升幅度达到6.34％。
同时面向准确率的问答对取舍方法在保证召回率达到50.21％的前提下准确率更是提高到了98.97％，完全可以达到实际应用的需要。
为了验证本文抽取算法的实际有效性，本文通过将“电脑”、“影视”、“饮食”、“医疗”、“计算机”等分类型词汇(从百度知道的分类列表中获得)和关键字“FAQ”进行组合后送入搜索引擎搜索，共收集得到18万的网页。我们将我们的算法在这18万网页上也进行了实验，并最终抽取出12万高质量的问答对，这一实验充分说明了我们方法的有效性。
6 结论
面向基于大规模问答对库的自动问答系统研究需求，本文提出了一种基于决策树和一阶马尔可夫链相结合的互联网上问答对的自动抽取算法。通过在500个网页中2113个问答对的抽取实验表明，本文提出的这种方法的准确率和召回率可以分别达到90.40％和86.03％，F1-Score比基线系统绝对提升了41.05％。同时为了把抽取到的问答对应用到实际，我们还以基本保证召回率的前提下，进一步提升准确率到98.97％，完全满足了实际系统的需要。
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文”