（计算机应用技术专业论文）基于论坛数据的问答挖掘.pdf

摘要 论坛中含有大量有价值的、由用户讨论生成的数据，从中可挖掘出大量的问 答数据，而这些数据可进一步用于改善问答系统的性能、扩充聊天机器人的知识 库等。 本文研究从论坛中挖掘问答数据的信息抽取方法，包括两个重点内容：一是 问题检测，二是答案检测。本文提出了基于标记序列模式的分类方法从论坛数据 中检测问题，这种方法在不失准确率的前提下，能大大提高召回率。基于图的排 序算法在信息检索领域的应用非常成功，本文受其启发，提出了基于图的迭代方 法为抽取出的问题寻找答案。在建立备选答案之间的加权有向图时，综合考虑了 多个因素，如备选答案之间的相关性、问题和答案的距离、答案作者的权威度等， 并将它们线性组合作为边的权重。在图的迭代中采用了两种方法，分别为有初始 值的迭代和无初始值的迭代。同时，提出了多种与已有的信息检索的模型结合使 用的方法。 在小规模人工标注的论坛数据上的实验结果表明，问题检测阶段的准确率和 召回率均明显优于任何已有的算法，答案检测阶段的m i m 、m a p 等各项指标也 均优于其它的算法。之后，又在大规模的论坛数据上做了实验，抽样检验结果证 明了本文方法在大规模论坛数据上同样具有有效性。 关键词：论坛数据问答挖掘信息抽取标记序列模式基于图的排序 a b s t r a c t 0 1 1 l i r l ef o n l m sc o n t a i l lah u g ea n u n to fv a l l b l eu s e rg e n e r a t e dc o n t e n tf b m w l l i c hw ec o u l dm i l l em a n yu s e m lq u e s t i o n a n s w e rp a i r s f o re x 锄p l e ，t h e yc o u l db e u s e dt o 曲p r o v et l l ep e o 皿a 1 1 c eo fq u e s t i o n a i l s w e 血gs y s t e m ，锄da u 舯e n tt h e k n o w l e d g eb a s eo f d l a t b o t h lt l l i st h e s i s ，w ea d d r e s st 1 1 ep r o b l e mo fm i m i 培q u e s t i o n a n s w e rp a i r sf r o m f o r u m sw i t han e wi 1 1 f o n n a t i o ne x 仃a c t i o nm e t h o dw 1 1 i c hc o n s i s t so ft w oc t i c a lp a r t s ： q u e s t i o nd 嗽t i o na n d 锄s w e rd e t e c t i o n w ep r o p o s e al s p ( l a b e l e ds e q u e 而a l p a t t 锄s ) b a s e dc l a s s i f i c a t i o nm e t h o dt od e t e c tq u e s t i o l l si i laf 0 舢lt l l r e a d t l l i s m e t h o db e h a v e sf a i r l yw e ub o mi i lp r e c i s i o na i l dr e c a l l t h e 鲫h b a s e dr a l l k n g m e t h o d sh a v es h o w nt 0b ee 侬斌i v ei i l 砌 o m a t i o nr e t r i e v a l h l s p i r e db ym e s e m e t h o d s ，w ep r o p o s ea 孕印h - b a s e dp r o p a g a t i o nm e t h o d t od e t e c ta n s w e r sf o r q u e s t i o n si nt 1 1 es 锄et h r e a d w e b u i l daw e i g h t e dd i r e c t e d 蓼a p ht od e n o t et h e r e l a t i o n s h i po fm ec a r l d i d a t ea n g w e r s t h ew e i g h tf o re d g e i sc 唧u t e db ya1 i i l e a r i 1 1 t e 叩o l a t i o no fm a i l yf a c t o r si n c l u d i i 冯s 岫i l 撕t ) ，o f m ec a n d i d a t ea 1 1 s w e r s ，d i s t a i l c e o fa n s w e r 自o mq u e s t i o na u t h o r i 够o ft 1 1 ec a i l d i d a t ea l l s w e r sa u m o r t bp r o p a g a t e a u t h o r i 以w eh a v e 似。印p r o a c h e s ：p r o p a g a t i o nw i m a n dw i m o u t 谳t i a ls c o r e w e a l s ot r yd i f i e r e n t 印p r o a c h e st oi 1 1 t e 鲈a t eo u rm e 廿1 0 d sw i t ht l l e 瓜m o d e l s l o t so f 唧e r i r n e m sa r ec a 耐e do u to ns m a l ls c a l ef o m md a t a ，w l l i c hi s 锄o t a t e d b vh a i l d s t h er e s u l t ss h o wt h a to u rq u e s t i o nd 烈e c t i o nm e 吐1 0 d i ss u p e r i o rt 0p r e s 饥t m e t h o d sb o t hi np r e c i s i o na r l dr e c a u ，a 1 1 da l s op r o v et h a to u r a r l s w e rd e t e c t i o nm e m o d o u t p e 南m so t h e r si na l lt h em e a s u r e si n c l u d i l l g 加迥锄dm 艘t h 吼w e a p l ) l y t h e s em e t l l o d st or a wl a 玛es c a l ef o m md a t a ，锄dt h es a n 叩l i i l gi i l v e s t i g a t i o nr e s u l t s h o w st h a tt h e s et e c l l i l i q u e sa r ev e r yp r o m i s i n g k e yw o r d s ：f o n 】md a t a ，q am i n i n g ，i 1 1 f o n t l a t i o ne x 仃a c t i o i l ，l a b e l e ds e q u e i l t i a l p a t t e m s ，g r a p hb a s e dr a n b n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：王摩 签字日期： 如暑年石月午日 学位论文版权使用授权书 本学位论文作者完全了解丞鲞盘堂有关保留、使用学位论文的规定。 特授权岙鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： l 龙二 导师签名： _ o 、7 ，、_ - ， 签字日期：咖召年舌月钎日 7 呵确 乒7 签字日期：御艿年月午日 第一章绪论 1 1 问题的提出及背景 第一章绪论 论坛为用户提供了一个在线讨论的场所，其讨论的内容覆盖各个领域，如运 动、旅游、爱好等等。论坛中包含大量由用户编辑的数据，如何将这些宝贵的数 据加以提取利用是一个非常有意义的问题。 本文主要讲述如何从论坛中抽取问答数据。许多论坛中都包含问答形式的知 识，本文调查了4 0 个论坛后发现其中绝大多数都包含问答形式的知识。从论坛 中挖掘问答数据有很多应用，如：问答数据是建立问答系统中不可或缺的部分， 基于问答数据，可以提供更加有效的服务；可以由搜索引擎提供给用户，提高搜 索体验；以问答形式进行论坛管理应该是一种很自然的方式，包括查询、归档等； 问答数据还可以用来扩充聊天机器人的知识库【l 】等。 虽然论坛数据中包含的问答价值巨大，但是先前并没有人做这方面的工作。 论坛中，每个主题一般都包含一个主贴和若干个回复，主贴一般都包含若干个问 题，而回复则可能包含了前面问题的答案和一些新的问题。 本文提出了一种新的方法从论坛中检测问答数据，其中包括两个环节：问题 检测和答案检测。 1 1 1 问题检测 这部分的目标是找出一个主题下的所有问题。乍看上去，这个任务非常简单， 可是实际上要把它解决好却非常困难。论坛中的问题经常以非常不正式的形式提 出。本文调查过1 0 0 0 个问题，发现仅仅依靠基于类似于问号、疑问词等简单规 则的方法是不够的，约有3 0 的问题不以问号结尾，而以问号结尾的句子中，有 9 并不是问题。 本文提出了一种基于分类的技术来检测问题，而用于分类的特征则是程序自 动提取出来的。 1 1 2 答案检测 这部分是指给定一个问题，找出它的正确答案，其目标是在同一个主题中找 到答案所在的段落。 第一章绪论 答案检测也是相当困难的。首先，多个问题和答案会因为并行讨论而交织在 一起，回复关系变得非常不清晰；其次，一篇帖子可能包含多个问题的答案，同 时一个问题也可能有多篇回复。 一个比较直接的方法是把它当作经典的信息检索来对待【2 】【3 】，这样每个答案 可以看作是一个文档，而问题则可以看作是查询。接下来就可以应用各种排序算 法，例如余弦相似度及类似于查询似然度、k l 散度等的多种语言模型来对答案 进行排序。但是，这些方法都没有考虑到备选答案之间的关系，也没有考虑到论 坛中特有的一些结构信息，例如备选答案和问题之间的距离等。 为了在建模时将备选答案之间的关系以及论坛特有的数据考虑进去，本文提 出了一种基于图模型的方法来检测答案。首先将答案之间的关系转化为一张图， 其中用到了三个因子：如果一个备选答案是正确答案，另一个备选答案是否为正 确答案的概率；问题和答案之间的距离；备选答案作者的权威性。然后对于每一 个备选答案，由排序算法来计算出其为正确答案的初始概率。为了得到其为正确 答案的最终概率，本文提出了两种方法：第一种是在最后一步将初始概率集成到 最终结果中来，第二种则将其集成到迭代的过程当中。 1 2 本文主要工作 本文主要做了如下工作： ( 1 ) 提出了从论坛中提取问答数据的方法，未见已有文献做过这方面的工 作。 ( 2 ) 使用了一种基于分类的方法来检测问题，而用于分类的特征则是程序 自动提取的。 ( 3 ) 提出了一种无监督的基于图的方法来检测答案。当训练数据存在时， 本文的方法可以很容易地与分类的方法集成。例如，基于图的迭代方 法的结果可以作为分类的特征。 ( 4 ) 在不同的数据上做了大量的实验，与其他研究者的工作相比，本文用 于实验的数据规模大得多。实验结果表明，在问题检测中，本文的方 法要明显优于基于规则的方法；在答案检测中，本文基于图的方法要 优于包括分类的方法 1 删在内的其它方法。 1 3 论文的结构 绪论部分概要性地描述了本文的研究背景，要解决的问题、其意义及本文的 2 第一章绪论 主要工作。接下来的相关工作部分，对问答挖掘方面的研究现状及相关技术作了 介绍。再接下来针对从论坛中挖掘问答数据的两个环节，分别介绍了问题检测的 算法和答案检测的算法。然后是实验部分，这部分通过大量的实验来验证本文提 出的问答挖掘的算法。最后总结与展望部分，总结了本文的主要工作，并对下一 步工作的方向和内容作了展望。 第二章相关工作 2 1 知识获取 第二章相关工作 在论坛知识获取方面有一些相关研究【1 】【4 【5 1 ，其中与本文的工作比较接近的是 为聊天机器人的知识库抽取“输入一回复”数据【4 】。但是问答数据并不同于“输 入一回复”数据，这主要体现在以下两个方面： 第一，在“输入一回复”数据中，每个主题的标题被当作输入数据，而本文 则从每个主题中抽取多个问题。 第二，在“输入一回复”数据中，同一个主题下所有回复帖子的内容都被整 合到一起作为一个整体的回复，但是在问答数据中一个回复的帖子可能包含多个 问题的答案。 另外，现有的研究中用到了一个分类器来区分帖子是否为回复，其中用于分 类的特征为词汇特征和一些结构信息特征【4 】，而本文基于图的迭代方法是无监督 的。 在知识获取方面，有一些研究者利用一个讨论机器人来回答学生的问题【5 】， 该机器人可以利用余弦相似度来计算学生的查询与存档的回复之间的相关性，然 后把最佳结果返回给学生；另外在一些研究中发现，可以利用讨论的结构信息来 检测讨论的重点话题【6 】；也有些研究者将因特网中继聊天( m c ) 的聊天记录来 聚类到不同的话题下【4 】，然后利用分类器来识别消息的回复，其中用于分类的特 征包括消息中词汇的个数、共同的词汇的个数等。 本文将其研究中用于分类的方法【l j 【4 j 移植到本文的实验中，但是实验结果显 示，本文的基于图的迭代方法比这种分类的方法效果要好。 2 2 电子邮件中的问答挖掘 。另外个相关的研究是从电子邮件中抽取问答数据7 1 ，其中利用基于分类的 方法 8 1 来检测疑问句，并且利用备选答案的词汇特征和一些电子邮件相关的特征 来为各选答案分类。 4 第二章相关工作 在问题检测阶段，从s w i t c h b o 6 汰d 语料1 中根据d m s l 标记选取了5 0 0 0 个正例和5 0 0 0 个负例；然后选取了前五个词的记性标注、后五个词的记性标注、 句子的长度、最有代表性的l o o 个记性标记二元组【9 等特征用作分类器的训练数 据；然后再利用黜p p e r 【j 作为分类器来训练分类模型；最后利用3 0 0 个陈述句和 3 0 0 个疑问句来测试分类结果。 在答案检测阶段，用于分类的特征有问题和答案中词汇的个数、问题和答案 的相似度、距离等一般特征，还有备选答案出现在邮件中的位置等结构信息特征 和一些基于其它备选答案的特征等。 作为对比，本文利用自动抽取的序列模式特征来检测问题，然后利用了无监 督的基于图的迭代方法来确定最佳答案。 在实际的数据中，标注最佳答案相对于标注问题要困难得多，所以，本文的 方法代价要比他们的方法小得多。 2 3t r e c 自l9 9 9 年文本信息检索会议( t e x tr e t r i e v a lc o n f e 嘣l c e ，t r e c ) 增加了问答系 统任务( q u e s 石o n a j l s w e 血gt r a c k ) 以来，针对t i 也c 做的研究越来越多。t r e c 上提供了简单陈述性问题、列表问题和定义问题等几类问题及大量的答案文本 库，要求参与者从文本库中提取出相应问题的答案【1 1 1 【1 2 】。 目前，有大量针对t i 也c 做的研列1 3 】【1 4 】【1 5 】。但是由于问题形式相对有限， 当问题被分析之后，答案的形式也就可以确定 1 6 】 1 7 】了。 相比之下，本文致力于从论坛的同一个主题中找到问题的答案。极端的情况 下，自动抽取出的问题相当复杂 18 1 ，获得与之相应的答案形式非常困难。 不过，从论坛中挖掘问答时可以利用论坛相关的一些信息来提高答案检测的 准确度，例如问题和答案之间的距离，作者的权威度等。 2 4c q a 和f a q 检索 c q a 检索1 9 1 和f a q 检索【2 0 】【2 l 】 2 2 1 与本文研究的侧重点不同，前者更侧重对于 用户给定的问题，找到与之相似的问题 2 3 1 然后连同答案一起返回给用户。 这些工作利用查询扩展( q u e d re x p a i l s i o n ) 【2 0 1 和机器翻译模型1 3 】【1 4 】 1 5 1 来跨 越问题和答案之间的词汇鸿沟( l e x i c a lc h 踟) 。 h t t p ：， 厂、w l o 幽酣u 门i i l 鲥u r a f s k y w s 9 7 第二章相关工作 2 4 1 词汇鸿沟 在信息检索领域，传统的方法都非常强调查询与结果之间在词汇上的相似 性：在词汇的分布上与查询越相近，其相关性就越高。用户一般也都认同这种方 法，所以在查询时，使用的关键词一般都是在他们预期返回的结果中要出现的。 但是，在问答系统中情况却不同。因为问题和答案所使用的词汇可能是不同 的，而且，很多情况下无法预料答案中应该出现的词汇。例如问题、枷e r e sag o o d p l a c et og e td m c r 的答案可能为g r 。e n sr e s t a u r a n th a s 伊e a t 捌i t a s 。 更一般的情况为，问题经常含有一些和答案不同但是相关的词汇，例如问题 中包含“w h e r e ，则答案中经常会出现“n e a r ”、“a d i a c 咖和“s 仃e e t 等。 这种情况便是词汇鸿沟，问题在鸿沟的一侧，答案在另一侧。两侧所使用的 词汇类似却又不完全相同，传统的计算相关性的方法对于这种情况无能为力。 2 4 2 查询扩展 查询扩展是一种针对词汇鸿沟现象提出的比较有效的改善方法。首先，找到 问题和答案之间词汇的映射关系，例如咖一6 e 螂p 、s f 纪一办印、 r 蚴，z 尼一向d g 怡等，然后再把映射到的词汇加入到查询中。 首先，在一个训练集上利用互信息( m u n l a lh 1 ：f o m a t i o n ) 来计算查询和答案 之间词汇的映射关系。互信息的计算方法如式2 1 ： ，0 ，v ) = 日0 0 以) ) 一p g g ) j v c p 口l “q ) ) 一p 亿芒g ) j v p 口i “萑g ) ) ( 2 1 ) 其中，w g 是一个二值函数，p o 口i “g ) 表示纵；目的情况下v n 的条件 概率。 日( ) 表示熵，计算方法如式2 2 ： 日0 ) = p l o g ：0 ) 一( 1 一p ) l o g ：( 1 一p ) ( 2 2 ) 由上述公式，对于问题中一个词汇，可以得到与之最相关的答案中的若干个 词汇，这些词汇就可以用作查询扩展。 2 5 迭代模型 类似于p a g e r a i l l ( 【2 4 1 和h i t s 2 5 1 的基于图的方法在搜索引擎中获得了巨大的成 第二章相关工作 功。p a g e r a l 出利用网页之间的链接关系来建立图，而另外一些研究则利用了文 档之间隐含的联系来建立刚2 6 】 2 7 】【2 8 1 。 与本文的抽取答案研究最相似的是l e x i i l l ( 【2 6 】。l e x 黜m k 利用备选答案之间 的余弦相似度来建立一张无向图。 2 5 1 p a g e r a n k 和h i t s 基于超链分析的思想，s e 玛e yb 血和l a n 了p a g e 在1 9 9 8 年提出了p a g e r a l l l 【 算法，同年j e 讪e 玛提出了h i t s 算法。这些算法已经开始在实际的系统中应 用，并且取得了良好的效果。 传统情报检索理论中的引文分析方法是确定学术文献权威性的重要方法之 一，即根据引文的数量来确定文献的权威性。p a g e r a n k 把引文分析思想借鉴到 网络文档重要性的计算中来，利用网络自身的超链接结构给所有的网页确定一个 重要性的等级数。当从网页a 链接到网页b 时，就认为“网页a 投了网页b 一 票”，增加了网页b 的重要性。最后根据网页的得票数评定其重要性，以此来帮 助实现排序算法的优化，而这个重要性的量化指标就是p a g e r a i l l ( 值。 h i t s 算法也认为网页的重要性应该依赖于用户提出的查询请求，而且对每 一个网页应该将其a u t h o r i t y 权重和h u b 权重分开来考虑，通过分析页面之间的超 链接结构，可以发现以下两种类型的页面：中心网页( h u b ) 和权威网页( a u t h o r i 够) 。 其中，中心网页是一个指向权威页的超链接集合的网页，而权威网页则是一个被 多个中心网页指向的网页。h i t s 算法发现，在很多情况下，同一主题下的权威 网页之间并不存在相互的链接，其间通常都是通过中心网页发生关联的。h i t s 算法描述了权威网页和中心网页之间的一种依赖关系：一个好的中心网页应该指 向很多好的权威性网页，而一个好的权威性网页应该被很多好的中心性网页所指 向。 2 5 2l e x r a n k 第一步，建立无向图。每个备选答案成为图中的一个节点，如果两个备选答 案之间的余弦相似度大于某个阈值，则这两个节点之间建立一条边，边的权值则 为其余弦相似度。这里阈值被设为0 1 5 。 第二步，计算备选答案与问题之间的相关性。 逆文档频率( i i l v e r s ed o c 啪锄tf r e q u e n c y ) 简记为i d f ，其计算方法如式2 3 ： ( 2 3 ) 一n ， 文 o = 矾 第二章相关工作 其中，是备选答案的数量，矾是指包含w 的备选答案的数量。而备选答 案与问题的相关性【2 9 】如式2 4 ： ，p 如i g ) = l o 妣。+ 1 ) l 。g 帆，。+ 1 ) 蛾 ( 2 4 ) w e q 其中，矾。是指备选答案口中w 出现的频率。 第三步，利用无向图进行迭代。 迭代公式如式2 5 ： p 脚鑫+ ( 1 d 凄荔p ( v i 粤) 协5 ， 其中，矗为参数，s f 以，y ) 指边上的权值，其计算方法如式2 6 ： 耕商篇铀 协6 ， 当迭代收敛时，结果即为最终相关性。 注意，上述的计算过程中，备选答案和问题都是经过预处理的。预处理包括 取词干和去除停用词。 2 6l s p 本文使用的问题检测算法受到了错误语句识别 3 0 】和比较旬式识别3 1 1 中l s p ( l a b e l e ds e q u e n t i a lp a n e n l ) 的启发。 在这些工作中，利用自动挖掘的l s p 来检测语法、句法错误以及比较句式。 受其启发，本文利用其来检测给定的语句是否为问题。 2 7 分类模型 本文中有大量实验应用到了分类模型。 分类技术在很多领域都有应用，例如文献检索和搜索引擎中的自动文本分类 第二章相关工作 技术；安全领域有基于分类技术的入侵检测等等。机器学习、专家系统、统计学 和神经网络等领域的研究人员已经提出了许多具体的分类预测方法。 下面对本文的实验用到的几种分类方法做下简要介绍： 2 7 1s v m s 以即支持向量机( s u p p o r tv e c t o rm a c h i i l e ) ，由v a p n i l 【等人于1 9 9 5 年提 出，具有相对优良的性能指标。该方法是建立在统计学习理论基础上的机器学习 方法。通过学习算法，s v m 可以自动寻找出那些对分类有较好区分能力的支持 向量，由此构造出的分类器可以最大化不同分类之间的间隔，因而有较好的适应 能力和较高的准确率。该方法只需要由各类域的边界样本的类别来决定最后的分 类结果。 支持向量机的目的在于寻找一个超平面，该超平面可以将训练集中的数据分 开，且与类域边界的沿垂直于该超平面方向的距离最大，故s v m 法亦被称为最 大边缘( m a x i 瑚l 蛐m 哪；i 1 1 ) 算法。待分样本集中的大部分样本不是支持向量，移去 或者减少这些样本对分类结果没有影响，s v m 法对小样本情况下的自动分类有 着较好的分类结果。 本文中答案检测部分基于分类的实验都是采用s v m 作为分类器的，具体使 用的分类工具有s l i g h t l 和l i b s 讧2 。 2 7 2 决策树 决策树是被广泛使用的归纳学习方法之一。决策树是用样本的属性作为根节 点，用属性的取值作为分支的树结构。它是利用信息论原理对大量样本的属性进 行分析和归纳产生的，其根节点是所有样本中信息量最大的属性，中间节点是以 该节点为根的子树所包含的样本子集中信息量最大的属性，叶节点是样本的类别 值。 决策树用于对新样本的分类，即通过决策树对新样本属性值的测试，从树的 根节点开始，按照样本属性的取值，逐渐沿着决策树向下，直到树的叶节点，该 叶节点表示的类别就是新样本的类别。 决策树方法是数据挖掘中非常有效的分类方法，它排除噪音的强壮性以及学 习反义表达的能力使其更适合于文本分类。 本文中问题检测部分的实验是采用r 口p e r 【1o 】来分类的。i ，p e r 算法是一 1 h t t p ：s n i i g h t j o a c h i m s o 吲 2h t t p ：帅帆c s i e n t u e d u t 、v ， 白l “l i b s 州 9 第二章相关工作 种基于正负实例集合的规则学习算法，采用的是重复增量裁减机制。这种重复增 量裁减机制可以减小规则过度拟合的可能性，提高规则的准确度，但在特征集比 较大的情况下，计算代价也很大。 2 8 本章小结 本章简要介绍了问答挖掘相关的技术及研究现状，这些研究是本文将要介绍 的方法的基础，同时，本章中也简要比较了其研究与本文方法的差异。 l o 第三章问题检测算法 第三章问题检测算法 要从论坛的数据中检测问题，只是利用问号、疑问词等规则是不够的。举例 来说，据本文分析，3 0 的问题并不以问号来结尾，而以问号结尾的句子中有9 并不是问题。这是因为： 问题可以以陈述句的方式来提出，例如：“i 锄w o n d e 血gw h e r eic a nb u y c h e 印a i l dg o o dc l o 锄n g 血b e i j m g ”。 非常简短的非正式的表达不应该被看作是问题，例如：“r e a l l y ? ”。 因为网络上数据不规范，论坛中提出的问题结尾的问号经常被省略。 为了弥补基于规则的方法的不足，本文提出了一种基于分类的方法：首先， 从问题与非问题的句子中提取出l s p ，然后将这些l s p 用作分类器的特征来分 类。l s p 在句法错误检测中是一种非常有效的手段，而本文的实验结果证明，用 这种方法来检测问题也非常有效。 接下来本章将会介绍什么是l s p 以及如何在问题检测中使用。 3 1l s p l s p ( l a b e l e ds e q u e n t i a lp a t t e m ) 可以记为l 厶酪专c ，其中，三e 舀是一个序列， 而c 则是分类标签。l s p 有几个比较重要的概念，为包含、支持度和置信度。下 面分别介绍这几个概念。 3 1 1 包含 把一系列元素的集合记为，分类标签的集合记为三，d 为序列的集合，其 中每个序列都是由，中的元素组成。 假设两个序列分别为： s 1 = ( 口1 ，口。) ，s 2 = ( 6 l ，吃) ， 。如果存在整数“，乙对于所有的1 ，m ，口，= 岛，满足： 1 f l f 2 碰伍l x ) = o 第四章答案检测算法 通常情况下，豇伍l y ) 碰( y l x ) 由于k l 散度实际上指出的是两个模型之间的差异，所以本文用将其换算为 两个模型之间的相似度，计算方法如公式4 6 ： s f 聊似。 4 1 4 基于分类的重排序 忆) 2 雨如 c 上文中提到，有的研究者利用基于分类的方法从论坛中抽取知识。虽然不是 抽取问题和答案，但是本文也可以利用其中使用的方法。在这些研究工作中，分 类的特征包括一些内容特征( 如输入和回复共同包含的关键词数量等) 和结构特 征( 如回复作者是否为主贴作者) 。 本文可以从问答对中抽取类似的特征，然后训练分类器，而分类器返回的结 果则可以用于为备选答案排序。 需要注意的是，基于分类的方法需要训练数据，而训练数据一般情况下是不 容易得到的。 以上描述的方法都没有利用到备选答案之间的联系，然而在论坛中，备选答 案并不是孤立存在的。下文将介绍如何使用基于图的方法把备选答案之间的联系 加以利用。 4 2 基于图的迭代方法 在网络检索领域，基于图的方法已经被证明是非常有效的，但是在问答抽取 方面，这种方法应用得并不广泛。直觉上，如果一个备选答案与一个正确答案有 非常高的相关性，那么即使其本身与问题的相关性不高，它也有可能是正确答案。 本节先介绍如何建立备选答案之间的加权有向图，然后再介绍计算备选答案 相关性的具体方法。 4 2 1 建图 给定一个问题g ，其备选答案的集合为彳。，则可以得到一个加权有向图 妒，e ) ，其中y 是节点的集合，而e 则代表了所有的边，每条边“一v 上的权值 由函数面，v ) 给出。这样，每个备选答案可以映射为图中的一个节点，而问题关 键在于如何确定边集e 。 1 9 第四章答案检测算法 给定两个备选答案口。和订。，本文利用k l 散度模型碰k 。i 口窖) 来计算边 露。专罐。是否存在以及权重。 利用k l 散度模型的理由如下： 考虑问题g 的两个备选答案口1 和口2 ，其中口l ：w o r l dh o t e l i sg o o db u t ip r e 衙 c 咖h o t e l ，口2 ：w o r l dh o t e lh a s av e 巧9 0 0 dr e s t a 啊a m 。如果日2 是正确答案的话， 那么口。也有可能是，反之则不然。因为在q 中，w o r l dh o t e l 和c e 砷yh o t e l 都有 考虑，而口，则不然，其只考虑到w o r l dh o t e l 。由于l 江散度本身具有非对称的属 性，所以能更好地反映这种非对称的情况，而余弦相似度等算法对这种情况则无 能为力。 接下来本文介绍两个定义，g e i l e r a t o r 和。脚r i n g ： 给定两个备选答案吒和，如果五翻比一个预置的阈值秒大，则有 一条边从口。指向以g ，本文称口g 是口。的g e l l e r a t o r ，而口。是口g 的。脚血1 9 。 根据以上定义，可以确定口。指向口。的边是否存在，同理，口。指向口。的边也 可以由此来确定。 以上定义中，参数目的值取了一个经验值，经过大量的实验证明，乡值的改 变对实验结果的影响很小。 在这个加权有向图中，允许自身到自身的边的存在。也就是说，一个备选答 案可以是自身的g e i l e r a t o r 和。鲫r i n g 。这一点，在计算边的权重以及节点的权 威度时还起到了平滑因子的作用。需要注意的是，一个备选答案可能是多个其它 备选答案的g e l l e r a 【o r ，同时，一个备选答案也可能没有g e i l e r a t o r 。在最极端的情 况下，一个图可能除了自身到自身的边之外，不存在其它边，在这种情况下，迭 代不再进行。 确定节点和边集之后，接下来的问题就是如何计算每条边的权重。一个最显 而易见的方法是仍旧利用k l 散度模型。为了达到更好的效果，本文另外考虑了 如下两个因子： 首先，一个回帖距离问题所在的帖子越远，则其中包含正确答案的可能性就 越小。这很容易理解，因为在论坛中，讨论的话题经常自然而然地转移，所以， 距离越远，可能讨论的话题越不相关。所以在建立这张有向图时，本文将备选答 案到问题的距离考虑进来，记为d ( 曰，口) 。 其次，每个论坛中，都有一些比较权威的用户为大家回答问题，他们的回复 包含正确答案的可能性比较大。有些论坛提供了用户的级别信息，而另外一些则 没有。为了统一标准，本文利用该用户发的主贴数量和回复的帖子数量来估算其 权威度，如公式4 7 所示： 2 0 第四章答案检测算法 删舶伽鬻 7 ， 其中，表示论坛中所有的作者。 给定两个备选答案口。和，边专口g 上的权值由这三个因子的线性组合确 定，这三个因子分别为：碰g 。i 口g ) 、d q ，口) 和口“肪d 砸) 。 以。一口s ) = ( 1 一丑一如) 南+ 五赤+ 枷砌。如g ) c 本算法需要对每条边的权值进行正规化，这类似于p a g e r a n k 算法中正规化 的方法。给定备选答案口。以及所有备选答案的集合彳，假设口。所有的g e i l e r a t o r 的集合为吒，则正规化的方法如公式4 - 9 ： 吨鹄一静刊赫 c 其中，旯作为平滑因子引入，其值设为0 o l 。 如果一个备选答案有多个g e i l e r a t o r ，则其指向每个g e n e r a t o r 的权值将依据上 式进行正规化。接下来本文用一个例子来说明这个过程。考虑图4 1 所示的情况： 口d l 图4 1 备选答案示意图 备选答案口。l 有三个g e i l e r a t o r ，分别为a g l 、口9 2 和自身。则边口。l 一口g l 经过 正规化之后的权值如公式4 1 0 所示： 2 l 第四章答案检测算法 以一j = 五卤+ ( 1 五) 而再磁暑鲁而习c 枷， 其余各边上的权值的计算方法与公式4 1 0 类似。 4 2 2 计算相关性 本文使用了两种方法将前面介绍的几种相关性的计算方法集成到基于图的 迭代模型中来。 第一种方法为无初始值的迭代。对于每个备选答案，都可以根据前面介绍的 方法来计算一个初始的相关性，同时本文还将计算其权威度。权威度用来调节问 题与备选答案最终相关性，也就是说备选答案的权威度与相关性的乘积作为最终 的相关性，如公式4 1 1 ： p r ( gl 口) = 口“f 五d ，f 巧q ) j r p ( g ，以) ( 4 1 1 ) 其中，j 砘，口) 是初始的相关性，而口甜胁d 砸) 的意义在于揭示了备选答 案口在图中的重要性。 接下来介绍如何计算备选答案口的权威度。 对于备选答案口。，其初始权威度计算方法如公式4 1 2 所示： 口“砌。一如；) = ，z 以。专) ( 4 1 2 ) 4 。e c 如果口。的权威度比较低，则作为它的g e t l e r a t o r 的口占也不会高。直觉上，如 果某个答案所有的。仃s p 她都不重要，那么它本身也不会太重要。需要注意的 是，这个结论反过来并不一定成立，也就是说，一个备选答案比较重要，并不意 味着它所有的。脚r i r 哆也都很重要。这可以如下递归定义来表示： 删砌州如g ) = ，z 以。一) 口“加洲砸。) 。 ( 4 1 3 ) e c 权威度迭代的过程一定会收敛。因为每条边上的权值经过正规化后，与一个 非周期不可约的马尔可夫链相对应，所以无论初始值是多少，最后都会收敛到一 个稳定的分布上。 第四章答案检测算法 第二种方法为有初始值的迭代。与第一种方法不同，这种方法将问题与备选 答案之间的初始相关性加入到了迭代的过程中。给定一个问题g 和备选答案集合 c 。，则备选答案口，口c 。的相关性由公式4 1 4 迭代计算： 嘲访五+ ( 1 力泛以m 刊毗l 4 埘， 其中，引入参数兄的作用是为了平衡公式中口及其。脚血g 的值对最终结果 的影响。 与第一种方法相同，迭代一定会收敛。因为从每个备选答案发出的边的权值 之和为1 ，所以可以当作转移概率对待。 4 3 与其它方法的集成 基于图的迭代方法很容易与其它方法集成。例如，可以利用其它计算相关性 的方法来代替l 也散度模型；当有训练数据可用时，迭代方法可以与分类模型结 合；可以由基于大量数据得到的互信息来改善所应用的各种信息检索的方法，从 而提高答案检测的准确度。 需要说明的是，以上提到的各种方法并不是孤立的，可以多种方法集成到一 起使用。 4 3 1 与其它m 模型集成 虽然在上文中阐述相关性的计算方法时一直是以k l 散度模型为例，但这并 不表示不能使用其它计算方法。例如，可以利用余弦相似度来计算，也可以利用 查询似然度模型来计算。在实验中，本文确实也使用了不同的方法来计算相关性 作为对比。在本文的实验部分，对比了应用不同的计算方法产生的结果。 4 3 2 与分类模型集成 当训练数据可用时，基于图的迭代模型很容易与分类模型结合使用。这里， 有两种结合使用的方法。 第一种，迭代模型返回的问题与备选答案的相关性可以作为分类模型的特征 来使用，而分类模型返回的预测结果则可以用来对备选答案重新排序。这样，备 选答案之间的信息在分类模型中就得到了利用。 第二种，首先依据其它特征( 如问题和答案之间的距离、作者的权威度等) 第四章答案检测算法 进行分类。因为预测的结果一般都是或者可以转化为备选答案是正确答案的概 率，所以，这个值可以当作初始相关性应用到迭代模型中去。 4 3 3 互信息 问题和答案经常使用不同的表述方式，例如砌y _ 6 9 “s g 。本文从大量的 问答对里，抽取了问题和答案之间的互信息。也就是说，问题的每个词汇，都有 若干个答案中的词汇以一定的相关性与其相关。在计算问题和答案的相关性时， 可以先利用互信息将问题扩展，将互信息中排名较高的词汇加入问题，然后再利 用上述方法计算相关性。 4 4 本章小结 本章重点描述了答案检测的算法。首先对一些广泛应用在信息检索领域中的 方法进行了简要的介绍。然后重点描述了基于图的迭代方法，这种方法分为两个 步骤：建立加权有向图和计算相关性。最后介绍了如何与其它方法结合使用以进 一步改善性能。 第五章实验 第五章实验 本章中介绍数据、实验方法以及问题检测和答案检测的实验结果。 5 1 数据 5 1 1 数据来源 本文中选择了三个不同大小的论坛作为数据的来源。分别为： 从h p a d v i s o r l 论坛抓取了1 2 1 2 1 5 3 个主题。 从l o n e l y p l a l l e t 2 论坛抓取了8 6 7 7 2 个主题。 从b o o t s r a l l 3 论坛抓取了2 5 2 9 8 个主题。 5 1 2 问题检测数据 从秭p a d v i s o r 论坛的数据中，随机抽取了6 5 0 个主题作为问题检测的数据。 这6 5 0 个主题，每个都包含至少两篇帖子，平均每个包含4 4 6 篇。忽略只包含 一篇帖子的主题的理由很简单，因为问题和答案不可能在同一篇帖子中。 接下来由两名数据标注人员对主题中的问题以及它们的答案进行标注。两份 标注中，被标注为问题的语句的k a p p a 统计量4 为0 9 6 。具体数据如表5 1 所示： 表5 1标注数据中问题的一致性 标注a 不是问题是问题 不是问题 1 0 4 0 06 6 标注b 是问题 4 9 1 7 7 8 l h f t p ：w w 喇p a d v i s o r c o m 2h t t p ：、删w - l o n e l y p l a n c t c o i l l ， 3 h t i p ：w w w b o o t s n a l l c o m 4k a p p a 统计量是一个可以反映一致性大小的数值，一般认为o 8 1 以上即为高度吻合 2 5 第五章实验 在此标注数据的基础上，生成了其交集和并集，分别以q 一蕊纪r 和 q 冗历f o 行表示。所谓交集是指，一个语句只有在两份标注数据中都被标注成问 题，它才是问题，否则只是普通语句；而并集是指，一个语句只要在一份标注数 据中被标注为问题，它就是问题。 5 1 3 答案检测数据 在答案检测部分的实验中，共使用了五组数据。 首先，从标注的6 5 0 个主题中产生了两份数据，分别为其交集和并集，以 么一砀幼和么砌f 鲫表示。注意，此处的交集和并集是在相同问题的基础做 的计算，也就是说，对于q 一劢纪，中的问题，一个备选答案只有在两份标注数 据中都是正确答案，它在交集中才是正确的；而只要在一份标注数据中为正确答 案，在并集中就是正确的。 此外，本文从h p a d v i s o r 、l o n e l y p l a n e t 和b o o t s r u u l 中分别随机选取了lo o 个主题来做实验。这样，本文就又得到了另外三组数据，分别以么一乃功2 、 么一幻孢e f v 和么一肋d 豳来表示。 两份标注数据中，被标为正确答案的语句的k 印p a 统计量为o 6 9 。具体数据 如表5 2 ： 表5 - 2 标注数据中答案的一致性 标注a 不是正确答案是正确答案 不是正确答案8 0 7 56 6 8 标注b 是正确答案 8 5 92 6 9 1 另外，因为答案检测中，上下文信息对于结果会产生影响，所以，本文上下 文的k a p p a 统计量也一并给出，其值为0 7 4 。具体数据如表5 3 ： 表