答案搜索引擎提交

Vol.
16,No.
82005JournalofSoftware软件学报1000-9825/2005/16(08)1407基于最大熵模型的QA系统置信度评分算法游斓+,周雅倩,黄萱菁,吴立德(复旦大学计算机科学与工程系,上海200433)AMaximumEntropyModelBasedConfidenceScoringAlgorithmforQAYOULan+,ZHOUYa-Qian,HUANGXuan-Jing,WULi-De(DepartmentofComputerScienceandEngineering,FudanUniversity,Shanghai200433,China)+Correspondingauthor:Phn:+86-21-65642830ext315,E-mail:lan_you@fudan.
edu.
cn,http://www.
fudan.
edu.
cnReceived2004-02-25;Accepted2004-07-06YouL,ZhouYQ,HuangXJ,WuLD.
AmaximumentropymodelbasedconfidencescoringalgorithmforQA.
JournalofSoftware,2005,16(8):14071414.
DOI:10.
1360/jos161407Abstract:Confidencescoredescribeshowconfidentaquestion-answeringsystemisaboutitsresponse.
ThispaperpresentsaMaximumEntropyModelbasedalgorithmwhichusesseveralfactorstotrainanMEmodel,andthentheMEmodelisusedtocalculatetheconfidenceofotherquestions.
EfficiencyofthismethodhasbeenprovedbytheTREC11'sQAevaluation,wheretheperformanceofthesystemhasbeenimproveddramaticallyafterconfidenceranking.
Keywords:naturallanguageprocessing;informationretrieval;question-answeringsystem;maximumentropymodel;confidencescore摘要:置信度指的是一个问题回答系统(QA系统)对其所作回答的自信程度.
描述了一种基于最大熵模型的算法.
首先,从训练语料中提取若干因素来训练最大熵模型;然后应用训练好的模型在测试集上计算置信度.
在2002年度的文本检索会议(TREC)中,QA系统用该算法计算每个问题答案的置信度,并依此排序,获得了显著的成绩.

关键词:自然语言处理;信息检索;问答系统;最大熵模型;置信度中图法分类号:TP301文献标识码:A如何从堆积如山的电子文档中获取自己感兴趣的部分,迄今为止,最常用的工具便是搜索引擎.
一般来说,人们在使用搜索引擎检索文档时,总会在带着一些问题,比如某人想知道犹他州的国家公园是什么(WhatistheNationalParkinUtah),他也许就会向搜索引擎提交"UtahNationalPark"这样的查询.
然而传统的搜索引擎进行的只是文档检索的工作,并非真正的信息检索.
人们仍然要在搜索引擎返回的相关文档中寻找问题的答案.

问题回答(QA)任务的目的就是要为问题找到确切的答案.
用户可以用自然语言向一个问题回答系统(QASupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.
60435020(国家自然科学基金);KeyProjectofShanghaiScienceandTechnologyCommitteeofChinaunderGrantNo.
035115028(上海市科委重点项目)作者简介:游斓(1979-),女,上海人,硕士生,主要研究领域为自然语言处理,信息检索;周雅倩(1976-),女,博士生,主要研究领域为自然语言处理,信息检索;黄萱菁(1972-),女,博士,副教授,主要研究领域为自然语言处理,信息检索;吴立德(1937-),男,教授,博士生导师,主要研究领域为自然语言处理,信息检索,视频检索.
1408JournalofSoftware软件学报2005,16(8)系统)提问,系统将会在庞大的语料库中找到关于这个问题的若干个答案,然后给所有的答案打分,并将最好的那个答案反馈给用户.
图1用一个具体的例子描述了QA任务.
用户向QA系统提问:WhatistheNationalParkinUtah系统在语料库中搜索到答案Zion,并返回给用户.
QuestionWhatistheNationalParkinUtahAnswerZionFreetextcorpusFig.
1DescriptionofQAtask图1QA任务的描述通常情况下,QA系统往往会根据答案的确切程度来给它们打分,较好的答案将被赋予较高的分数.
但这个分数仅仅告诉用户,对一个特定的问题来说,哪个答案会更好一些.
然而用户更想知道的是,在输入的一系列问题中,系统对哪些回答的正确性更有把握一些.
这就要求QA系统还应该能够了解其所作回答的正确程度.
因此,为了衡量QA系统的这种能力,TREC2002首次引进了"置信度"标准[1].
"置信度"也就是QA系统对其所作回答的自信程度.
在TREC2002的QA任务中,许多系统仅使用答案类型作为考量的因素,以确定对不同问题答案的置信度[2].
也有一些系统就直接使用了答案评分的结果[3].
但用这两种方法算出的置信度往往不够精确.
一个较好的置信度评分算法应该综合考虑系统处理各种不同类型问题的能力,以及在处理过程中系统所涉及的各项参数,当然也包括了前面提到的答案分数.
在TREC2002中,也有一些系统考虑到了这一点,但是这些系统只是用经验公式来综合计算所有的因素.
排名前10位的单位中只有BNN使用经验公式来综合问题回答过程中涉及的各项因素,从而得到置信度分数[4].
他们考虑了以下3个因素:问题中的动词、答案上下文与问题的匹配情况以及问题类型,并对这3个因素赋予相同的权重.
而在我们的系统中,仅答案评分一项就已经涵盖了所有这3个因素.
为了更加精确地计算置信度,我们使用了一种基于最大熵模型的算法,综合了答案分数和问题类型在内的若干因素,并在实验中取得了令人满意的效果.
本文第1节主要介绍基于最大熵模型的置信度评分算法,其中第1.
1节描述了最大熵模型的原理,第1.
2节详细分析我们提出的算法.
第2节主要介绍实验的设计并分析实验结果.
最后是对我们工作的一个小结.

1置信度评分算法1.
1最大熵模型1.
1.
1基本原理建立最大熵模型的基本思想是为所有已知的因素建立模型,而把所有未知的因素排除在外[5].
也就是说,要找到这样一个概率分布,它满足所有已知的事实,且不受任何未知因素的影响.

QA系统在处理一个特定问题的过程中会涉及各种因素,假设X就是一个由这些因素构成的向量,变量y的值反映了答案的正确性,y=1表示答案正确,y=0表示答案错误.
概率p(y|X)是指系统对某个问题给出答案正确或错误的可能性.
这个概率可以用上述思想来估计.
最大熵模型要求p(y|X)在满足一定约束的条件下,必须使得下面定义的熵取得最大值:游斓等:基于最大熵模型的QA系统置信度评分算法1409∑=yXXypXyppH,log,这里的约束条件实际上就是指所有已知的事实,一般可以用以下的方式来表述:=else0,conditioncertainsatisfies),(if,1),(yXyXfi,i=1,2,3,…,n,称fi(X,y)为最大熵模型的特征,n为所有特征的总数.
可以看到,这些特征描述了向量X与答案正确性y之间的联系.
概率p(y|X)必须满足上述特征的约束,由此可以定义一个受限的概率分布族为:={p(y|X):Ep{fi}={fpE~i},1≤i≤n},其中,Ep{fi}=∑yXiXypXpyXf,)|()(),(,~~)|()(),(}{,~XypXpyXffEyXiip∑=,)(~Xp和)|(~Xyp都是在训练数据中观测到的经验分布.
现在的问题就是要在受限的概率分布族中找到一个具有最大熵的分布,即()=*∑∈yXXypXypXypXpXyp,)|()|(log)|()(~maxarg)|(,可以求出上式的解为[5]=*∑iiiyXfXZXyp),(exp)(1)|(λ,∑∑=yiiiyXfXZ),(exp)(λ,其中λi是每个特征的权重.
1.
1.
2建立最大熵模型在我们的方法中,向量X由系统处理问题的过程中提取出的各种因素组成,由于最大熵模型要求X的各个分量取离散值,我们首先要把原本取连续值的因素离散化.
X描述了我们的系统是如何获得答案的,而y则描述了答案的正确性.
因此,p(y=1|X)就表示在特定因素向量为X的情况下答案正确的概率,这也正是我们期望知道的系统对答案的置信度.
因为y只有0和1两种取值,我们可以用下式来计算置信度:==*=∑iiiXfXZXypconfidence)1,(exp)(1)|1(λ,+=∑∑iiiiiiXfXfXZ)0,(exp)1,(exp)(λλ.
这里,我们只选择在训练数据中出现次数大于3的特征,以避免过拟合现象,然后使用IIS来计算特征参数.
1.
2问题回答过程因素1.
2.
1FDUQA系统介绍为了更好地说明在本算法中用到的各种因素,先简要介绍我们的QA系统.
系统的输入是一系列基于事实的问题,经过处理以后,系统输出这些问题的答案.
并且,所有的答案将按系统对其"置信度"从高到低排序.
类似于大多数QA系统,我们的系统主要由4个模块组成:预处理和索引模块(离线模块)、问题分析模块、检索模块以及答案抽取模块(具体流程如图2所示).
在分析问题和抽取答案时,系统会用到一个知识库,该知识库包含了约80个问题类型.
每个问题类型又由3个部分组成:问题模板、答案类型模板(又称内部模板)和上下文模板(又称外部模板).
问题模板是指问题出现的1410JournalofSoftware软件学报2005,16(8)形式,答案类型模板是指该类问题的答案可能是何种类型(如时间、地名等),上下文模板是指答案可能出现的上下文的形式.
为了获得一定的召回率和较高的准确率,系统将问题的答案同时限定在内部和外部模板中.
目标文本与模板之间的匹配存在两种方式:宽松的或严格的.
无论是答案类型模板还是上下文模板的匹配都可以是这两种方式中的任意一种,但不允许两者同时以宽松的方式匹配.
抽取答案的时候,第1步先采用严格的答案类型和上下文模板匹配方式.
如果这样无法取得答案,第2步再改用宽松的匹配方式,即是内外两个模板一松一严.
如果第1步就能找到答案,就不进行第2步了.
我们把上下文模板中的每一项,包括答案本身都看作是一个概念.
系统首先在目标句子中定位所有的概念,然后尝试匹配模板,如果在第1或第2步匹配成功,就将答案抽取出来.
KnowledgebaseAnswerextractionRetrievalQuestionprocessingCandidateanswersAnswersVotingConfidencescoringAnswerextractionAnswertypeandcontexttemplateKeyconceptQuestionanalysisQuestionIntegrationCandidatesentencesBoolretrievalCorpusFig.
2FlowchartoftheonlinepartofFDUQAsystem图2FDUQA系统在线部分流程图图3是FDUQA系统处理问题过程的一个具体例子.
在这个例子里,输入的问题是WhatistheNationalParkinUtah首先分析问题,确定问题的类型为"WhatVERB_BE1NP1inNP2",这里的VERB_BE是指be动词,NP指名词词组.
从知识库中找到这个问题的上下文模板和答案类型.
这个问题的答案类型应该是名词词组(NP),它的第1个上下文模板表明答案可能出现在:Utah'sAnswerNationalPark.
其中Answer就是答案所在.
然后在问题中提取出查询词NationalPark和Utah,并从语料库中检索出所有可能包含答案的句子,再从中抽取答案.
比如有这样一个句子"…Alightning-sparkedfireinUtah'sZionNationalParkspreadoutofcontrolto1,100acresTuesday.
.
.
"这个句子正好符合第1个上下文模板,Zion又是一个NP,符合答案类型.
于是Zion就被抽取出来作为问题的答案.
当然,在检索出来的句子群中可能会有多个句子符合模板匹配,这样就会找到不只一个候选答案.
最后我们采取一种投票机制来找到最佳的答案.
每个答案出现的次数就是它的票数,将票数最高的作为最佳答案.
限于篇幅,有关FDUQA系统的详细情况在此不一一说明.
详情可参阅文献[6].
1.
2.
2因素为计算置信度,我们考虑了系统处理问题过程中的4个因素:答案评分对于每一个问题,系统都可能会找到若干个答案.
如何比较这些答案的好坏这就要从以下3个方面为答案打分:上下文模板(contexttemplate).
对于某一类型的问题来说,其答案可能出现在不同的上下文中.
在某些上下文模板中,答案出现的可能性相对较大,这类上下文模板就会获得较高的分数.

游斓等:基于最大熵模型的QA系统置信度评分算法1411VotingBestanswerAnswers…Templatematching&answerextractionAnswer:"Zion"Asentencecontaininganswer:"…Alightning-sparkedfireinUtah'sZionNationalParkspreadoutofcontrolto1,100acresTuesday.
.
.
"ContextTemplate:AnswerType:1.
NP2;'s;A;NP1;NP2.
NP2;A;NP1;3.
NP2;'s;NP1;VERB_BE1;A4.
…Query:"NationalPark,Utah"QuestionType:"WhatVERB_BE1NP1inNP2"Question:"WhatistheNationalParkinUtah"SentencescontainingqueryFig.
3Anexampleofquestionprocessing图3问题处理过程实例答案类型模板(answertype).
一个问题可以有不同类型的答案,比如以Who开头的问题,答案类型可以是人名,也可以是组织名.
而以人名作为答案的可能性要更大些,所以前一个答案类型模板的分数会比后一个要高.

查询词匹配(keywordsmatching).
答案所在的句子可能并没有匹配所有的查询词.
然而,查询词匹配得越多,答案就越好.
因此这个分数表示了答案所在的句子与查询词的匹配程度.

一个答案的分数也就是关于这3个分数的函数:S=fφ(contexttemplate,answertype,keywordsmatching),从上式我们可以看出,答案的分数要视具体的问题而定,因此不能直接用来衡量置信度.

步数在上一小节里,我们知道答案抽取的过程可以分为两步.
在第1步找不到答案的情况下再进行第2步.
由于第1步抽取使用的是严格的模板匹配,所以一步抽取出来的答案要比两步抽取出来的更为可靠.
基于此,答案抽取的步数在一定程度上会影响到答案的正确性.
最佳票数在投票机制中,每个答案出现的次数就是它的票数.
一个答案出现得越多就越可能是正确答案.
而作为最后输出的最佳答案,它的票数在衡量置信度的时候也具有一定的意义.
最佳得票率然而,有时候最佳票数的多少并不能很好地说明问题.
比如:对于问题1,系统只找到了1个答案,并且这个答案在语料库中出现了2次.
也就是说,这个答案就是最佳答案,且最佳票数为2.
对于问题2,系统共找到了3个答案(A,B,C),其中答案A出现了2次,而答案B和C各出现了1次.
那么答案A就是问题2的最佳答案,且最佳票数也为2.
虽然这两个问题的答案都具有同样的最佳票数,但显然问题1的答案正确度更高一些.
为了能够对这类情况进行处理,我们定义了最佳得票率为最佳票数与所有答案的总票数的比,并把它也作为计算置信度时考虑的因素之一.
2实验2.
1实验环境我们使用TREC10的语料和问题作为训练数据.
TREC10的QA任务共有500个问题.
对每个问题,我们从系统的处理过程中获取了上述4个因素,然后以此来训练最大熵模型.
1412JournalofSoftware软件学报2005,16(8)另外,实验用的测试数据是TREC11的500个问题.
在这500个问题中,FDUQA系统答对了124道题.
我们对每个问题的答案估计系统对它的置信度,并按照置信度从高到低排序输出的答案.
我们希望在使用了基于最大熵模型的置信度评分算法后,可以将正确的答案尽可能地排在前面.
2.
2TREC11QA任务的评估方式在实验中,我们使用与TREC11的QA任务相同的评估方式.
TREC11定义了一种叫做"置信度权重分数(confidence-weightedscore)"的量度标准.
它类似于文本检索中的平均精度指标.
具体表达式如下:500____#5001∑=÷=iiiquestiontoupcorrectoreweightedscconfidence,其中#correct_up_to_question_i是指从第1个问题到第i个问题的i个问题中系统答对的问题数.
可以看到,置信度权重分数在0~1之间变化,并且其最大值受问题回答准确率的约束.
只有当所有的答案都正确时,该分数才为1.
而对于一定的准确率来说,正确的答案排得越是靠前,该分数就越高.
2.
3基准方法方法1.
直接按照问题的编号排序输出答案.
这种方法完全不考虑问题本身以及系统处理该问题的过程.

下面介绍的两种方法分别都被其他参加TREC2002的QA系统使用过,为了与基于最大熵模型的算法作比较,我们将这两种方法作为实验中的另外两种基准方法.
方法2.
以问题类型作为排序的依据.
我们将问题分成6种类型:where,when/whatyear,what/which,who,how,以及其他.
对每种问题类型,我们就系统对TREC10的500道问题的回答情况作了统计(见表1).
Table1Precisionofdifferentquestiontypes表1不同类型问题的回答准确率Questiontypewherewhen/whatyearwhowhat/whichOtherHowPricision0.
6920.
4100.
3400.
1680.
1540表1中,各种问题类型按回答准确率从高到低排列.
在测试集上,为了将尽可能多的正确答案排在前面,我们也用与表1相同的顺序来排序输出答案.
对于同一类型问题的答案则按问题编号排序.
也就是说,系统对一个问题答案的置信度就相当于这个问题类型在训练集上的回答准确率.
很容易理解的是,假如系统对某几类问题回答的准确率特别高,这种方法必定会取得不错的结果.
方法3.
直接用答案评分来排序输出答案,将分数高的答案排在前面.
这个方法将系统对答案的置信度的高低等同于答案评分的高低.
但是正如前文中所述,答案评分应该是置信度所考虑的一个因素.
仅以此来衡量系统对答案的置信度是有所偏颇的.
表2是系统处理两个不同的when问题时所涉及的各项因素的值.
如果仅将答案评分作为答案的置信度,那么第1题答案的置信度应该高些.
但实际上第1题答错了,而答案评分较低的第2题却答对了.
第1题的最佳答案的评分只能说明它在这道题的所有251个答案中是最好的,不能光凭此来断定它的置信度会比第2题的答案要高.
从表2也可以很直观地看到,如果再综合考虑其他3项因素,就不难得出第2题答案置信度较高的结论.
Table2Anexampleofthevaluesoffactors表2具体问题中各项因素的值QuestionBestanswerCorrectlyansweredAnswerscoreStepNumberofvotesBestvoteratioWhenwasthetelegraphinvented1827Wrong5.
0233/251=0.
012WhenwastheOklahomaCitybombing1995Correct4.
013434/34=1.
02.
4实验结果2.
4.
1基于最大熵模型算法的结果我们使用基于最大熵模型算法来计算答案的置信度,然后以此对所有答案排序,从而得到置信度权重分数为0.
434.
图4描述了用置信度排序后输出答案的分布情况.
横坐标是答案个数n,纵坐标是前n个答案的准确率.
游斓等:基于最大熵模型的QA系统置信度评分算法1413从图中可以看到,前8个答案的准确率为1,也就是说,前8个答案都是正确的.
而前100个答案的准确率为0.
64,说明前100个答案中有64个正确答案.
相对于总共124个正确答案,有一半以上的正确答案排在了所有答案的前1/5中.
1Precisionoftopnquestions'answers0.
90.
80.
70.
60.
50.
40.
30.
20.
10n151101151201251301351401451Fig.
4DistributionofanswerswhenusingME-basedalgorithm图4采用基于最大熵模型算法的输出答案的分布从图中可以看到,前8个答案的准确率为1,也就是说,前8个答案都是正确的.
而前100个答案的准确率为0.
64,说明前100个答案中有64个正确答案.
相对于总共124个正确答案,有一半以上的正确答案排在了所有答案的前1/5中.
2.
4.
2结果比较下面比较3种基准方法和基于最大熵模型算法的结果.
表3显示了这几种方法的置信度权重分数.

Table3Comparisonofdifferentalgorithms表3基于最大熵模型算法和基准算法的比较AlgorithmConfidence-WeightedscoreMethod10.
234Method20.
261Method30.
367ME-Basedalgorithm0.
434从表3我们可以看到,用最大熵模型计算出来的置信度显然优于3种基准方法.
图5描述了各基准方法输出答案的分布与基于最大熵模型算法的比较.
其中横轴与纵轴的意义与图4相同.
图中用粗实线表示采用最大熵模型算法的结果(prec_conf),细实线表示基准方法3的结果(prec_score),粗虚线表示基准方法2的结果(prec_qtype),细虚线表示基准方法1的结果(prec_qid).
Precisionoftopnquestions'answers11.
11101201301401nprec_scoreprec_qidprec_qtypeprec_conf0.
90.
80.
70.
60.
50.
40.
30.
20.
10Fig.
5Distributionofanswerswhenusingdifferentalgorithms图5各种方法的输出答案分布的比较可以看到,由于基准方法1没有考虑任何影响答案置信度的因素,而只是按问题编号输出答案,因此在它的1414JournalofSoftware软件学报2005,16(8)结果中,前18个答案都是错的,即前18个答案的准确率为0.
在第32个答案以后,准确率总在0.
2~0.
3之间浮动.
这是因为我们的系统在TREC11的500个问题上的精度是0.
248.
可见正确答案在所有答案中的分布基本上是均匀的.
这显然不是我们想要的结果,我们希望将正确的答案尽可能地往前排.