模式学习在QA系统中的有效实现.pdf
计算机研究与发展ISSN 100021239CN 1121777TPJournal of Computer Research and Development43(3):449455,2006 收稿日期:2004-12-27;修回日期:2005-05-17 基金项目:国家自然科学基金项目(60435020);上海市科技攻关计划基金项目(035115028)模式学习在QA系统中的有效实现杜永萍1,2黄萱菁1吴立德11(复旦大学计算机科学与工程系 上海 200433)2(北京工业大学计算机学院 北京 100022)(dypzdj yahoo1com1cn)Effectively Implementing a Pattern Learning Method in the Question AnsweringSystemDu Yongping1,2,Huang Xuanjing1,and Wu Lide11(Department of Computer Science and Engineering,Fudan University,Shanghai200433)2(Institute of Computer Science,Beijing University of Technology,Beijing100022)AbstractOpen domain question answering(QA)represents a challenge of natural language processing,aiming at returning exact answers in response to natural language questions1A novel pattern learningmethod for QA is developed1The key idea is to get answers using answer patterns learned from the Web1Although many other QA systems use the pattern based method,the method in this paper is implementedautomatically and it can handle the problems other systems fail,such as the weakness of pattern restrictionand so on1The experiment result on the TREC data indicates that the method is effective1It solves not on2ly the questions relying on simple patterns,but also the questions that need complex patterns for answer ex2traction1The question number of the latter is about 80%in the question set of the TREC1Key wordsquestion answering;pattern learning;answer extraction摘 要 开放领域的问题回答(question answering)是自然语言处理领域中具有挑战性的研究方向1 提出了一种基于模式学习实现问题回答的方法,核心思想是利用机器学习方法得到的答案模式获取问题答案1 该方法优势在于:模式学习完全自动化实现;解决了目前普遍存在的模式约束性弱及答案缺乏语义类型限制等缺陷1 在TREC测试集上的实验结果表明,它不但解决了简单模式所覆盖的问题集,同时也解决了需要较强约束性模式进行答案抽取的问题集,而后者的问题数目在TREC测试问题集中占约80%1关键词 问题回答;模式学习;答案抽取中图法分类号 TP3911 引 言面向开放领域的问题回答(question answering,QA)这一自然语言处理研究领域中具有挑战性的研究方向已经受到广泛关注,由美国国家标准技术局(National Institute of Standards and Technology,NIST)和国防部高级研究计划局(Defence AdvancedResearch Projects Agency,DARPA)组织召开的一年一度的文本检索会议(text retrieval conference,TREC)设立了问题回答这一项子任务,对问题回答系统进行科学的评测,该会议已经成为文本检索领域最具有权威性的评测会议1通常意义下的文本检索输入的查询是关键词,返回相关文本,而问题回答输入的查询是自然语言描述的问题,要求返回问题的精确答案1 国内,中科院计算所研究开发的人物关系问答系统1,引入逻辑推理机制,使系统具有依据一定的策略进行推理的能力,但限定于人物关系的问答1一个完整的问题回答系统包含3个主要组成模块1 第1模块是问题分析,它决定答案类型并且生成查询;第2模块是检索,根据第1模块输出的查询在文档集上搜索,返回相关文档或片段,这些文档或片段可能包含了答案;第3模块是答案抽取,分析第2模块返回的文档或片段并且抽取出问题的精确答案1问题回答区别于通常意义下文本检索的关键在于答案抽取模块,该模块可以采用不同策略实现,如:逻辑推理2,利用WordNet等 外 部 知 识 资源3,4、模式匹配57等1 由于答案在语料中表达形式灵活,给准确识别带来很大难度,采取模式匹配是一种有效方法1模式在信息抽取(information extraction)中具有普遍应用,大部分IE系统也都要获取对应抽取信息的模式,如基于结构化数据的WHISK、半结构化语料 的RAPIER、自 由 文 本 的AUTOSLOG和CRYSTAL等8,91 但IE系统在获取模式时都需要进行语料标注工作,这项巨大的工程也是模式创建的瓶颈1InsightSoft6开发的问题回答系统在TREC评测中取得了好成绩,它拥有数量庞大的模式,这些模式由语义块(semantic block)组合而成,具有较高的准确率,但需要耗费巨大的人力资源1 目前,也有其他的问题回答系统实现了自动学习简单模式并用于问题回答,如:ISI5和新加坡国立大学7,但这些简单模式存在以下两大缺陷:(1)模式的组成成分中只能够包含问题中的一个元素(词或短语),导致约束性较差1 对于一些比较长的复杂问题,在进行模式匹配抽取答案时,需要多个问题元素出现在侯选答案句中进行约束,而这是简单模式所无法覆盖的1(2)模式匹配得到的答案缺乏语义信息限制1问题:“Where are the Rocky Mountains located?”片段:“in imitation of the Rocky Mountainsin the background,continues to lie”模式:“theNA M EinANSW ER,”模式中的“NA M E”代表问题元素“the RockyMountains”,模式匹配将在片段中抽取到答案“thebackground”,但该问题答案类型为“LOCATION”,该答案不满足这一限制1本文将介绍利用Web资源学习不同问题类型的答案模式,实现问题回答系统中的答案抽取1 值得指出的是,本文提出的方法既解决了上述缺陷,又不需要人工参与,并且取得了满意的结果1 本文的第2节介绍问题分析;第3节介绍对于不同的问题类型自动学习其答案模式的算法;第4节介绍问题回答系统中基于模式匹配实现答案抽取;第5节介绍利用TREC问题集对该方法做性能分析和评价12 问题分析不同的问题回答系统采用不同的问题分类体系,基于疑问词或基于答案类型等1 本文提出一种新的基于答案类型和问题结构的问题分类体系,同时融入了问题的语义信息和结构信息1211 问题元素(Q Tag)我们对问题定义了一套标记集合QTag如表1所示,它们构成了问题的不同元素1Table 1Symbol Set of Question Element表1 问题元素标记集Q TagDefinitionExampleQ FocusKey word of the questionWhat country is the holy city of Mecca located in?Q NameEntity(Q LCN Q PRN)Name entity of the questionWhat country is the holy city of Mecca located in?Q Verb(Q BeVerb Q DoVerb)Main verb of the questionWhat country is the holy city of Mecca located in?Q BNPNoun phrase of the questionWhat country is the holy city of Mecca located in?054计算机研究与发展 2006,43(3)Q Tag集合包含4类标记Q Focus,Q Name2Entity,Q Verb及Q BN P1 其中,Q NameEntity包含Q L CN(地名),Q PRN(人名)等多种实体名;Q BN P包含问题中除QFocus和Q NameEntity已经标识之外的名词短语1212 问题分类在介绍问题分类之前首先介绍两个概念:问题模式和答案类型1(1)问题模式将问题中每个不同的元素用其对应的QTag标记替换,即生成问题模式(Q Pattern)1问题:What country is the holy city of Mecca lo2cated in?问题模式:WhatQFocusisQ BN PofQL CN Q DoVerbin?(2)答案类型在我们的问题回答系统中采用的答案类型分类体系如表2所示:Table 2Answer Type Concept表2 答案类型分类体系Answer TypeAnswer TypeLCNMNYPRNABBRORGBNPNUMMANNERDATREASONPCTQUOTATION 如下所示为基于问题模式和答案类型进行问题分类的实例1 目前我们的问题库(TREC的2393个问题)包含了483种问题类型1问题类型:LCNWhatQ BeVerb Q FocusinQ L CN?问题:What is the oldest national park in theU1S1?What is the most populous city in the UnitedStates?3 模式学习及评价我们针对每个不同的问题分类类型学习其答案模式,即答案可能出现的上下文,以实现问题回答中的答案抽取1 模式学习与评价流程如图1所示1下面结合示例解释算法描述,Q Tag,Answer作溪模式学习的训练样例,A nswer为TREC在官方网站上公布的正确答案1问题类型:LCNWhatQ BeVerb Q FocusinQ L CN?问题:What is the oldest national park in theU1S1?Q Tag:Q BeVerb=“is”,Q Focus=“the oldest na2tional park”,Q L CN=“the U1S1”A nswer:“Yellowstone”Fig11Architecture of pattern learning and evaluation1图1 模式学习与评价流程图311 模式学习模式学习算法:(1)构造查询1 查询由两部分组成:“QTag+A nswer”(QTag不包含Q BeVerb),示例问题的查询为“the oldest national park”+“the U1S1”+“Yellowstone”1(2)检索1 提交查询给搜索引擎Google,保存返回结果的前100个片段1(3)片段选取1100个片段中,满足如下两个约束条件的片段将用做模式抽取1约束1:包含答案(此例为“Yellowstone”)1约束2:包含出现在答案前后的各10个词1154杜永萍等:模式学习在QA系统中的有效实现(4)模式抽取1 标记替代(泛化操作)1泛化1:将出现在片段中的各问题元素用相应的Q Tag标记替换1泛化2:答案用标记 A 替换1包含Q Tag和 A 的最短片段将作为我们的答案模式1 例:片段:“Established in 1872,Yellowstone isthe oldest National Park in the U1S1 ”答案模式:“,AQ BeVerb QFocusinQL CN”312 模式评价学习到的答案模式并非全部完全可靠,也可能会抽取出错误答案1 因而,我们有必要对这些模式做一评价以提高问题回答系统总体性能1答案模式是针对不同的问题分类类型而学习的,同样,我们也根据问题类型对它们分别进行评价1评价采用数据挖掘中的指标:可信率(Conf idence)1评价算法:(1)随机选取属于某问题类型C的k个问题Qi(i=1,k),重复步骤(2)(3)1(2)将由问题Qi的Q Tag构成的查询提交给Google,返回的前100个片段中包含问题答案的片段构成片段库Si,库中片段数目为n(n100)1(3)利用该问题类型的答案模式库中的每个模式p在Si中进行匹配,统计模式被匹配的次数m和其中匹配抽取到正确答案的次数c(cm),计算Ci(p)=cm1(4)该问题类型的答案模式库中每个模式p的可信率为Conf idence(p)=ki=1Ci(p)k1 可信率越高的模式抽取到正确答案的可靠性越高,而低可信率的模式则不能保证其正确性1 表3列举出了部分问题类型的答案模式与其相应的可信率1 我们学习到的答案模式其有效性在于模式中可以包含多个问题元素,如“A,QFocusinQL CN”包含两个问题元素“Q Focus”和“Q L CN”1包含越多问题元素的模式具有较强的约束性,匹配抽取到的答案也具有更高的可靠性1 若只允许模式中包含一个问题元素,首先其可靠性不能保证;其次,对于较复杂问题很难确定惟一的一个包含该问题信息的问题元素用做模式学习1Table 3Sample of Answer Patterns表3 答案模式示例Question TypeAnswer PatternConfidenceLCNWhatQ BeVerb Q FocusinQ LCN?(Sample question:What is the largest city in Ger2many?),AQ BeVerb Q FocusinQ LCNA,Q FocusinQ LCNofA 1Q LCNsQ Focus Q FocusinQ LCN,A0195018401610159DATWhen didQ LCN Q DoVerb Q BNP?(Sample question:When did Hawaii become astate?)Q LCN Q DoVerb Q BNPinA 1Q DoVerb Q BNPinA,Q LCNinA,Q LCN Q DoVerb Q BNPA,Q LCN Q DoVerb Q BNP0191018201730145Fig12Architecture of answer extraction1图2 答案抽取模块流程4 答案抽取我们所学习到的答案模式是为了在问题回答系统中实现答案抽取,图2描述了对于给定问题的答案抽取过程1(示例问题:What is the most populouscity in the United States?)考虑到Web上的海量信息,我们选择G oogle作为问题回答系统的搜索引擎1254计算机研究与发展 2006,43(3)M1:识别问题的Q Tag标记并生成问题模式Q Pattern1Q Tag:Q BeVerb=“is”;Q Focus=“the most pop2ulous city”;Q L CN=“the United States”Q Pattern:WhatQ BeVerb Q FocusinQ L CN?M2:依据问题的Q Pattern和答案类型确定问题分类,在已经学习到的模式库中选择该问题类型相应的所有答案模式1问题类型:LCNWhatQ BeVerb Q FocusinQ L CN?答案模式:,AQ BeVerb Q FocusinQ LCN1(Confidence=0195)A,Q FocusinQ L CN(Conf idence=0184)M3:替换答案模式中的每个QTag标记为对应的问题元素1答案模式:,Ais the most populous city in the UnitedStates(Conf idence=0195)A,the most populous city in the UnitedStates(Conf idence=0184)M4:对于每个经过例化后的答案模式和搜索引擎返回的片段,与标记 A 匹配的词串被挑选为侯选答案并记录相应答案模式的可信率1片段:“in New York City,it is the mostpopulous city in the United States1答案模式:,Ais the most populous city in theUnited States(Conf idence=0195)侯选答案:it片段:New York,the most populous city in theUnited States with 8 million people答案模式:A,the most populous city in theUnited States(Conf idence=0184)侯选答案:New YorkM5:利用实体名识别器排除不满足答案类型的侯选答案1 该模块解决了答案语义类型限制问题1如上抽取到的侯选答案“it”不满足该问题的答案类型“LCN”(地名)这一限制,被排除1M6:依据答案模式的可信率对侯选答案进行排序,最高分值的侯选答案“New York”将作为该问题的最终答案1 侯选答案CandidateA nsweri的分值计算:Score(CandidateA nsweri)=mj=1Conf idencej,其中,m为模式匹配抽取到该侯选答案的模式数目,Conf idencej为模式相应的可信率15 性能分析TREC在评测结束后会在网站公布问题的答案,我们利用TREC提供的问题集与答案做了几组实验测试该方法的性能1Table 4Experiment Data表4 实验数据Test DataTraining DataTREC8TREC9 TREC10 TREC11TREC9TREC8 TREC10 TREC11TREC10TREC8 TREC9 TREC11TREC11TREC8 TREC9 TREC10ISI采用TREC10的问题集测试学习到模式的性能,主要针对BIRTHYEAR,INVENTOR等问题类型,我们同样也学习了相应的模式1 表5列出二者的测试结果比较1 性能指标为TREC采用的MRR10(mean reciprocal rank)值,评测中允许问题回答系统对每个问题返回前5个答案,若正确答案出现在第1位,则该问题得分为1;若正确答案出现在第2位,则得分12,以此类推1 系统最终得分MRR值为所有问题的平均MRR值得分1从表5的测试结果可以看出,我们的系统所取得的MRR微平均值为0150,高于ISI1 表5中的问题类型所对应的问题只含有一个问题元素(除去核心动词外)1ISI不能解决包含多个问题元素的问题类型,如表3问题类型,而这些问题类型也是常见的1本文方法优势在于,可以学习到这类问题类型的答案模式1我们将模式匹配的方法用于表4列出的不同测试问题集,并考察了答案排序模块对系统性能的影响1 对于一些问题,系统不能返回正确答案,归因于尽管系统找到了正确答案,但侯选答案的排序模块没能将正确答案排在前面1 我们分析了答案排序模块返回不同数目的答案时系统的性能,并按疑问词类型分组,实验结果如图3所示,图3(a)(b)(c)(d)分别为以TREC8,TREC9,TREC10,TREC11为测试数据的实验结果1354杜永萍等:模式学习在QA系统中的有效实现Table 5Performance Comparison with ISI表5 与ISI性能比较Question Type(ISI)Question Type(FD)Number of QuestionsMRR(ISI)MRR(FD)BIRTHYEARDATWhen;What year;What datebeQ PRNborn?801690167DISCOVERER PRNWhoQ DoVerb Q BNP1?(Q DoVerb=discovered)401880183DEFINITIONDESCWhatQ BeVerb Q Focus?10201390141LOCATIONLCNWhereQ BeVerb Q LCN?1601860182INVENTOR PRNWhoQ DoVerb Q BNP1?(Q DoVerb=invented)60158017Micro2avg MRR13601490150Fig13Performance impact of candidate answer ranking1(a)Experiment result on TREC8;(b)Experiment result onTREC9;(c)Experiment result on TREC10;and(d)Experiment result on TREC111图3 答案排序模块对系统性能影响1(a)TREC8实验结果;(b)TREC9实验结果;(c)TREC10实验结果;(4)TREC11实验结果 由图3可以得到如下结论:(1)大多数正确答案包含在排序模块返回的前10个侯选答案中,并且系统性能与只返回第1个侯选答案时有较大提高,这一现象表明我们的答案排序模块还有待进一步改进,应综合考虑多种相关因素1(2)4组实验结果有一个共同现象:疑问词为where和when类型的问题准确率较高,疑问词为what类型的问题准确率较低1 疑问词为what类型的问题其答案类型不易确定,且答案上下文的表达方式变化多样,学习到的模式覆盖率不高,降低了准确率1参加TREC的各单位实现问题回答采取了不同策略,如深层知识推理机制1或耗费巨大人力资源构建模式6等,本文方法简单有效,实验结果在TREC11中的排名位于前1316 结论与展望本文提出了一种模式学习方法来实现问题回答中的答案抽取,解决了其他采用模式匹配策略的问题回答系统中存在的模式约束性弱及答案缺乏语义类型限制等缺陷1 实验结果表明该方法是简单而有效的1 特别是具有高可信率的模式可以可靠地找到问题的答案1采用模式匹配策略的问题回答系统,其性能很大程度上取决于所学习到模式的数量及其质量1 目前,我们学习到的模式数量还很有限,从而限制了问题回答系统的性能1 今后,我们将从两方面展开工作:利用已经学习到的高可信率模式实现查询扩展,提高搜索阶段性能1 扩大实验规模获取更多有效模式1参考文献1Wang Shuxi,Liu Qun,Bai Shuo1An expert system about humanrelationship question answering1Journal of Guangxi Normal Uni2versity(Natural Science),2003,21(1):3136(in Chinese)(王树西,刘群,白硕1 一个人物关系问答的专家系统1 广西师范大学学报(自然科学版)12003,21(1):3136)2D1Moldovan,S1Harabagiu,R1Girju,et al1LCC tools for454计算机研究与发展 2006,43(3)question answering1The TREC211 Conf1,NIST,Gaithersburg,MD,20023J1Prager,J1Chu2Carroll1Use of WordNet hypernyms for an2sweringwhat2isquestions1TheTREC210Conf1,NIST,Gaithersburg,MD,20014E1H1Hovy,U1Hermjakob,C12Y1Lin1The use of externalknowledge in factoid QA1The TREC210 Conf1,NIST,Gaithers2burg,MD,20015D1Ravichandran,E1Hovy1Learning surface text patterns for aquestion answering system1The 40th Annual Meetingof the Asso2ciation for Computational Linguistics(ACL22002),Philadelphia,PA,USA,20026M1M1Soubbotin,S1M1Soubbotin1Patterns of potential an2swer expressions as clues to the right answer1The TREC210Conf1,NIST,Gaithersburg,MD,20017Dell Zhang,Wee Sun Lee1Web based pattern mining and match2ing approach to question answering1The TREC211 Conf1,NIST,Gaithersburg,MD,20028Ellen Riloff1Automatically generating extraction patternsfrom un2tagged text1The 13th National Conf1,Artificial Intelligence(AAAI296),Portland,Oregon,19969Stephen Soderland1Learning information extraction rules for semi2structured and free text1Machine Learning,1999,34(123):23327210E1Voorhees1Overview of the question answering track1TheTREC210 Conf1,NIST,Gathersburg,MD,20011157165Du Yongping,born in 19771Ph1D1Hermain research interests include informationextraction and natural language processing1杜永萍,1977年生,博士,主要研究方向为信息抽取和自然语言处理1Huang Xuanjing,born in 19721Associateprofessor1Her main research interests in2clude information retrieval and natural lan2guage processing1黄萱菁,1972年生,副教授,主要研究方向为信息检索和自然语言处理1Wu Lide,born in 19371Professor and Ph1D1supervisor1His main research interestsinclude natural language processing,patternrecognition and computer vision1吴立德,1937年生,教授,博士生导师,主要研究方向为自然语言处理、模式识别和计算机视觉1Research BackgroundOpen domain question answering(QA)represents an advanced application of natural language processing1The Text RetrievalConference(TREC)Question Answering Track provides a large2scale evaluation for open domain question answering systems1We in2troduce a method for learning answer patternsfor QA from the Web1The approach is based on the assumption that strings containinganswers can be matched by certain structural formulas(answer patterns)1All of the patterns are evaluated by the concepts of confi2dence and support,which are borrowed from data mining1Answer patterns with higher confidence lead to choosing the answer withgreater reliability1The experimental result on the test data of TREC indicates the effectivenessof our method1Our work is supportedby the National Natural Science Foundation of China under grant No160435020 and the Shanghai Scientific and Technological Project(035115028)1554杜永萍等:模式学习在QA系统中的有效实现
