（计算机应用技术专业论文）自动答疑系统中问题定位方法的研究.pdf

东南大学硕士学位论文 摘要 自动问答系统自二十世纪中期出现以来一直处于快速发展之中，成为计算机领域内的研究热 点。问题定位是问答系统中关键技术之一，目前大多数问答系统采用为答案库建立索引的方式来 实现问题定位，达到缩小查找范围的目的。然而这些方法都存在一定的问题。本文针对远程教育 特定领域的自动答疑系统，提出了利用模糊自适应谐振映射神经网络( f u z z ya r t m a p ) 以及支 持向量机( s v m ) 的方法解决问题定位。重点研究和分析问题的特征表示以及问题的定位方法。 论文首先介绍了自动问答系统的发展过程、一般体系结构、常用技术和定位方法的研究现状； 重点研究了答案库的结构设计和预处理、问题的特征以及面向高维空间的特征变换，并结合f u z z y a r t m a p 和s v m 两个分类算法分析了基于特征表示与变换的问题定位方法；最后，给出了原型 的设计与实现，并对实验的性能进行了分析，验证了论文技术的可行性。 关键词：问答系统、 定位方法、分类、s v m 、f u z z y a r t m a p 壅堕查兰茎主兰垡鲨塞 a b s t r a c t q as y s t e mh a sb e e nd e v e l o p i n gr a p i d l yf r o mt h em i do f 2 0 t hc e n t u r y , a n dh a sb e c o m et h eh o t s p o to f r e s e a r c hi nc o m p u t e rs c i e n c ea r e a l o c a l i z a t i o ni so n eo f k e yt e c h n i q u ei nq as y s t e m m o s tq as y s t e m s c r e a t ei n d e xf o ra $ 1 s w e r s c o l l e c t i o nt or e d u c es e a r c h i n gr a i l g ea n dl o c a l i z e ，h o w e v e rt h e s em e t h o d sh a v e c e r t a i nw e a k n e s s e s a i m i n ga tq as y s t e mi 1 1r e m o t ee d u c a t i o nb a c k g r o u n d 。t h i sp a p e rp r o p o s e s8n e w m e t h o du s i n gf u z z ya r t m a pm a ds v mt os o l y el o c a l i z a t i o n 砸sp a p e r sb a c k g r o u n di sb a s e do na c e r t a i ns u b i e c tq as y s t e m , a n df o c u s e s0 1 1q u e s t i o nf e a t u r er e p r e s e n t a t i o na n dq u e s t i o n si o c a l i z a t i o n t h i sp a o e rf i r s t l yi n g o d u c e st h ed e v e l o p m e n t a r c h i t e c t u r ea n dt e c h n i q u e so fq as y s t e ma n dt h e s t a t u so f1 0 c a l i z a t i o n s e c o n d l yf o c u s e so nt h ep r e t r e a t m e n to ff 1 1 1 s w e r s c o l l e c t i o n ，q u e s t i o n s f e a t u r e r e p r e s e n t a t i o na n df e a t u r et r a n s f o r m a t i o nt oh i g hd i m e n s i o ns p a c e 。t h i r d l y , a n a l y s e st h e1 0 c a l i z a f i 0 1 1 m e t h o do fq u e s b 0 1 1 sw i t hs 、，ma n df u z z ya r i m a p ：a tl a s t , d e s i g n sa n di m p l e m e n t sa l lp r o t o t y p e a n ds i n a l y s e st h ep e r f o r m a n c et 。v e r i f yt h ef e a s i b i i i t yo f a r i t h m e r i cp r o p o s e db y 也i sp a p e r k e y w o r d s ：q as y s t e m ，l o c a l i z a t i o n ，t a x o n o m y ，s v m ，f u z z ya r t m a p i l 东南大学学位论文独创性声明 本人声明所是交的学位论文是我个入在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含力获褥东南大学或其它教育机构 的学位或证书丽使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明弗表示了谢意。 研究生签名：盖控娅日期：怂五：3 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文豹复印 孛霸电子文档，可以采用影印、维印或英链复潮手段傈存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 捂刊登) 授权东褒大学磅究生貌办理。 磷究生签名：蛰栏延 导师签名：霞期：翌z ：立 第一章引言 1 1 研究背景与现状 1 1 1 问答系统的历史背景和现状 第一章引言 计算机领域内最早的问答系统构想可以追溯到1 9 5 0 年著名的英国数学家图灵在其发表的论 文( c o m p u t i n gm a c h i n e r ya n di n t e l l i g e n e e 中提出的“机器智能”概念。该论文中提出了通过自 然语言问答的方式来判断机器是否具有智能的实验方法，这种被称为“图灵测试”的方法也是最 早的问答系统模型。从此以后，问答系统不断发展。早期较著名的系统有1 9 6 1 年b g r e e n 等在美 国林肯实验室为美国橄榄球季候赛设计的b a s e b a l l 系统，该系统把关于橄榄球比赛的相关数 据存在底层数据库中；通过对用户的问题进行语言学的分析后产生查询检索底层的结构数据库， 回答用户的有关问题。基于同样原理构建的问答系统还有1 9 6 3 年r l i n d s a y 在美国卡内基技术学 院设计的s a d s a m 系统，以及1 9 7 3 年w o o d s 等开发的u n a r 系统等。这些早期的问答系统都 是面向某个受限领域，其主要局限性在于它的底层是一个受限领域的结构化数据库，而不是开放 领域的结构文本库，这种基本架构由于其扩展时面临的复杂程度较高而制约了问答系统的发展。 此后的问答系统逐渐转向以文本库为基础。最早的在线文本检索系统是1 9 6 6 年r f s i n o n s ， j f b u r g e r 和r e l o n g 设计的p r o t o s y n t h e x i 系统，它是以文本信息的存贮和检索方式进 行工作的。至今，文本检索系统仍然被不断地改进和发展。特别是i n t e r n e t 的普及为问答系统的 研究注入了新的活力，1 9 9 3 年诞生了第一个面向i n t e r n e t 的自然语言问答系统s t a r t ，它能够回 答针对虹t 信息实验室的地理学知识的用户提问。s t a r t 内部将知识库中的信息组织成“主体一 关系一对象”的三元组，然后和经过语义分析后的用户问题相匹配，系统本身没有知识的扩充， 要想回答多领域的问题必须维护一个较大的知识库。该系统回答问题能力有限且精确度不高。同 年j u l i a nk u p i e c 等设计了i d u p a x 问答系统，该系统使用百科全书作为知识库来回答一般性的知 识问题。它采用了统计与语言学知识相结合的技术，通过布尔搜索引擎和句法分析器从百科全书 中抽取问题的答案。国际上第一个提供自然语言问句接口的网络商业服务商是a s k j e e v e s 公司， 通过手工收集大量的自然语言问句以及相应的u r l 链接，提取问句的问题模板( 问题类型) 并进 行分类。该系统的精确度并不高，但却因其方便易用而广受欢迎。 最近几年，网络和信息技术的快速发展和人们希望更快地获取信息的愿望促进了自动问答技 术的发展。越来越多的公司和科研院所投入到自动问答技术的研究，比如微软和i b m 等著名的跨 国公司。在每年一度的文献信息检索( 7 x e c ) 会议，问答系统成为最受关注的主题之一。越来越多 的大学和科研机构参与了t r e c 会议的q u e s t i o n - a n s w e r i n g t r a c k 。在2 0 0 0 年1 0 月召开的a c l 2 0 0 0 国际计算语言学学术会议上，有一个专题讨论会，题目是“o p e n - d o m a i nq u e s t i o na n s w e r 。 目前，国外已经开发出一些相对成熟的问答系统。麻省理工( m i n 开发出一个问答系统s t a r t ( s y n t a c t i ca n a l y s i su s i n gr e v e r s i b l et r a n s f o r m a t i o n ) ，从1 9 9 3 开始发布在i n t e m e t 上，网址为 h r p ：w w w a i m i t e d u p r o j e c t s i n f o l t t d ，可以回答一些有关地理、历史、文化、科技、娱乐等方面地 简单问题。国内研究机构也正关注这个热点问题，如哈尔滨工业大学的开放式自动问答系统，北 京语言大学的问答系统以及中国科学院计算所的n k i ( n m i o nk n o w l e d g eh 】舶s n l 】c t i 鹏) 问答系统。 n k i 问答系统囊括了人物知识库、国家知识库，朝代帝王知识库，中国少数民族知识库、药膳知 识库、中医疾病知识库、中医证型知识库、计算机知识库、体育知识库，人们可以询问以上领域 的基本问题，如“周恩来是什么人? ”、“毛里求斯讲什么语言? ”，系统可以给出简单的答案。 目前，该系统的知识库正在进一步扩充，测试的网址h t t p ：w w w n k i n e t c n u s e rh a n d b o o k h t m 衰南大学磺圭孥靛论文 。i 2 蠲答系统鬻蠲静静炎 上带介绍了问答系统的历熙背景，目前研究的问答系统主要可以分为：蒸于知识库的问答系 统、自然语言界面的专家系统、基于传统i r ( + i e ) 的问答系统 ( 1 ) 基于知识库的闯答系统 蒸鼍：知识瘁鲸闯答系统龟撬c y c , n k i ( 璐) ，n k i ( c h i n a ) 等，鞋狐i ( c h i n a ) 为铡+ n k i ( n a t i o n a l k n o w l e d g ei n f r a s t r u c t u r e ) 燕令巍大戆、胃共享瓣知识群僖，免辩磅、教学、簿警帮舞识鬏务 等摄供有效的基霭| l 。它不仅集戒了各学科静公共知谖，蔼且融入了各学辩专家静令夫知识。溅i 闯答系统包括1 6 个学科领域知识，可以对国家地理知识库，城市天气预报知识库、人物知识库等 2 3 个库的知识进行查询。用户可以通过自由的自然谮甯的提问方式获取所需鼹的知识，输入形式 可以多样化。基于知识库的问答系统都是把相关知识预先存于知识库中，为了得到满意的结果， 必须其番尽可能完备的知识库，在知识库的建立与维护中，会用到知识袭糸、机器学习的一些相 关技术。 ( 2 ) 鑫然语言赛覆盼专家蘩统 专家系统是疆营雾撬瓷王舞、羁翅专家知谈汉及翔谖箍理等技本、毽瓣奄求簿鞫题静翔谖装 统，惹人工智能应用研究的熏疆领域之一。自然语誊界蕊豹专家系统可以巍为一个瓣答系统。农 专家系统的人机接口模块中，将用户输入的自然语崔转换为系统可接受的内部形式，将系统的输 出转换为人可理解的外部形式，这样整个专家系统就和问答系统一样以自然语亩的方式进行人机 交互，恻答用户提出的问题。中科院王树西开发的人物关系问答系统就燕一个这样的问答系 统，它允许用户通过自然语宙对红楼梦中的人物芙系进行询问。专家系统的开发工具较多、 技术鞍成熬，并且答案也魄较攘确。但是，太部分专家系统推理方法单调、瞬定，只能做演绎攘 瑾，举嶷罄雾谈燕琏戆力。势菇，专家系统黪舞识鬻梦重不是，鑫象获歉麴滚戆力差，存在知谈 获驳熬凝颈蠲题。所爨，鼙翦专家系统篷逶角范髫j # 常有隈。 ( 3 ) 基于传统i r ( + i e ) 的婀答系统 参加t r e cq at r a c k 评测的问答系统多是基于传统i r ( + i e ) 的问答系统。一般来讲，信息检 索( i r ) 是根据用户的查询而对相关文本的检索过程，宦之所以和问答系统密切相关，是因为在问 答系统中，为得到相关答案，阁户也会构造查询进行梭索。但是，所不同的熄，检索只能返回整 个文本，丽不能把闯答系统所疆求的答案返回给用户，最后，还需要用户程这些返回的文本中去 避一疹零找垂己掰器要鳃答案。涟答系统率也常常燃到继患抽取( i e ) 技术。1 9 9 9 年，r o h i n i 鼢珀馘i 秘霉e il i 在。支持鞫答系统貔售惠掏取8 孛漭鳃了阉答系统孛绉纛撼取( i e ) 豹馒爝， 并指如；信息抽取串，如鸯名赛体识剐常常是闯昝系统闯题类型处理中不w 藏缺的组成部分；强 健的裔然语言分析器为问答系统处理用户所提出的闷联提供了一个结构化的慕础；非受限领域的 信息抽取，如多重关系和般搴件的抽取等，有望纷问答系统带来一个新的突破。问答系统是一 项综古性科学，涉及到计算语甯学、机器学习、信息科学和人工智能学等很多领域的相关技术， 其核心魑自然语言理解技术。 誉论是英文翘答系统述燕审文阕答系统，帮毒誉舞鑫然语言处理。鲶壤耀户提出的阉每、绞 索穗荚文本和段落跌及麴取签寨辩，都要臻蘩垂然语塞整理援零。豫了上嚣漤到戆售惠硷索帮毽 患麴数辨，闫答系统霞塌劐戆巍然语言处理技术还包攒：关键字与模式疆联技术、自动摘要技术、 词法分析技术、句法分析技术、语义分析技术等等。 1 1 3 问答系统的发展方向 夔饕嚣个相美矮域豹发蓑及专家韬对翊答系统鹣荧注，趣答系统也誉麟发震帮成熬，箕寒采 爱袋方秘主要有羧下蔻焘： 斑用领域进一步扩麓。 问昝系统的应用越来越广泛，如远程答疑系统、自动帮助系统、网络资源访问系统、在线肖 科垒书聚统等，而且未来的问答系统应该能够处理多语言的数据并且能够使用多媒体资源。 提供个性化问答服务。 目黼的问答系统只能回替独立的基于事实的问题，然愿不同的用户可能希望问答系统具有不 同的动能。有的用户可能希攮阔昝系统够提供实辩交嚣筹且暴读的答案；蠢的震户希望阀磐系 2 茎二茎薹l 塞 统绘镌 】提供一些售惠匏鹜豢懿识，最好按照时窝藏媲瘫将这些蔼惠缓织熬j l 乏；还有一些赣域豹 初学者鼹希望问答系统给出的镣案是针对他们自己的联解水平的 问题类型广泛化。 问麟类型趋于更广泛，不樽是传统的事实问题，而是更复杂的形式，如：列举、归纳和解释。 多语吉问簪系统也会出现，这样用户可以用自己的母语发问，而系统从多语甯文本中检索并且提 交绘用户符合他们母语盼答察。这就要求多语言信息梭索和机器翻译领域的藏丈突破t 答寨形式的扩震。 携交绘用户逶合匏答案麓翘答系缓孛最大匏建患之。当我不鹫合遣貔答案或搜簧互摇矛纛 豹善懿瓣，系统必须要处理遮髓情况。所 ：盂提交答寨将是今后研究的一个鬟骚方商，主要取决予 文本概括的能力。而且未来的问答系统将不只局限予文本处理领域，它将包括多种媒体t 如语音、 图像等，撮后系统将把答案以邂当形式提交给终端用户。 寝示形式的改进。 问替系统将来的研究会偏黛于交互式检索、答案袭示和概括、对话式界顾和人机交互等方砸。 以人类习惯的方式从互联网上获取信息始终是人们逡戡敬耳标，面自然语嵩阏答系统的出现使这 个爨檬鸯7 实现懿霹襞。毽憝，阏答系统是一顼鬟攘较大匏系统工程，涉及刹鑫然语害处理技零， 绕诗诗舞语言技本、妇 i 袭示、天辊交互、多媒俸鲶疆秘智能学习系统等诲多壤域，它熬发曩也 必将取决于这些相关领域的发麟 1 1 4 娥程教育的答疑模式 餐凝、解惑作失教育瀵动审的一个必不可少的嚣簧，也是挺毫教学簇黛，宪善远程教学系统 孛戆一令嚣寒毒矮熬缓或部分。在基于g 醴懿鑫圭掌藩式远程教学； ：壤孛，分毒各遗豹学生、老 师不聪霈簧蟊对面建进行教攀活动。这样，远程教学谨提供了一些便稍魏黼封，也提出了一个阉 题：如何使传统韵答疑活动檬逡程教学系统中褥】| ；实现。目前在网络教育中广泛使用的答疑模式 有如下几种方式： ( 1 ) e m a i l 答疑：这是一种异步答疑方式，e l a i l 是一种i n t e r n e t 上广泛使用的交流方式。 不论悬个人之间，个人与公司之问，还是公司之间的交往都可以通过这种方式避行交流。e - m a i t 用于学生与学生之闻，学生譬老孵之闻的学习讨论向粒鳃答是可取的办法。儇其主要不足之处是 无法绦诞帮聪蛙。 ( 2 ) b b s 答疆：g 醛( b u l l e t i nb o a r ds y s t e m ) - - 电子毒告拦系统遣怒i n t e r n e t 矮户广泛使 用豹一种讨论方式，在班塔上注册成为合法用户，藏埘以发表鑫己的建议，躐者发出需要帮助豹 问题，也可以根据别人发的帖子给予回复，这是一种有用的异步答疑方式，箕不足之处时缺乏即 时性羊口组织性。 ( 3 ) 在线答疑方式：这与聊天室以及一些聊天工舆( 如：腾讯的q q ，m i c r o s o f t 的k s n 等等) 类 似。这种聊天或答疑需要参与的双方同时在线，在网络教育中，老师可以定期上线，给学生进 亍 孵答，瓣学生进行指导，其不照也是缺乏知识的有散缀织性，答疑的时间襻隈。 谯同一篇文档中频繁出现的特征项应该具有较商的权重，因此榆索系统常使用频率因子 矿( t e r mf r e q u e n c y ) 进行特征项赋权，使用高频特征项进行查询可以提高系统的查全率 6 燕：章挺燕萋罐妇袈奔蹲 稷傻用频率霹子著枣麓耱琏襞统翁囊谗褴耱，摄裹壹垒事霹会影晦捻索系统瓣豢擦事。 骝瑟震要 l 天一个鸯垒邦交搂繁食蠢芙熬因子，辆大不霹交搂之阉麴熬分发。魏聚姆薤 矮在集合孛较多熬交糖串窿壤，粼鞠癍戆交糖熊嚣予i d f ( i n v e r s e d o c u m e n t 淑镁h 鞠e 茹 癜渡较大。在文档惑数辩n 静壤念串，鲡莱惫禽荣特薤瑷豹交挡数为越，戴文搦集因子 是4 ：= i o g ( n 弘) 。较簿鲍蠢谶褒选式通常题含毙够穆一些特寇文糖等文糍纂念串其 它文爨嚣纂嚣亲黪特鬣磺，这静耱薤矮苓坟在攀令支整中要骞较褰斡掇壤频率，遣要在 蘩令文挡集舍审较少瓣交橙串爨鬻。耱凝攀翻予和文挡集因子耪豢旒霹娃囊域藏嚣静， 这就是文本检索模型中最常鲻髓张一i d f 赋权因子。 ( 3 ) 文档匹配 文档的匹配，涉及到向鲞空闻模型中的努一个概念是相似度( s i m i l a r i t y ) ! l l ：相似度s i m ( d i 。 n 2 ) 用予度量两个文档d l 和d 2 乏阔的内释耀关程度。嬲文档被表示为文档空蚓的向爨，就可以利 瑁囊熏之阑的题毒计算公式寐袭零交搂鞫的提觳嶷。常用的距离有向量的海积距凑，冀诗箨鲡公 式( 2 2 ) 掰示： # g 妇( 琏，绣) * 。麓 ( 2 。2 ) 觯 域容藏疆离，鲡公式( 3 。2 麟零： 矗 乞毽。锄 s h n ( 琏，鹋* ( 袅3 ) 翻擞空间模型在布尔检紫模激的蒸础上，增加丁燕键词的权值，邋过哭键词的粳德，运用向 璧的内积威余弦距离方法计辣义档相芙魔，这样不仅提高了检索的性能，而臌可以按照相嫩的 大小对梭索的结果进行排序，因此许多新的检索方法就悬建立在向量空间模测的基础上。 2 。2 挨方法 主蠹零来，受统诗学葛遴谚冀麓惫变挎两爨税( s u p p o r tv e c t o rm a c h i n e ，s 镪鞴w 熬鼹耨磷究 成果熬嶷震，一耱 缓往楚瑾技零羧爨数方法或卷说蒸手攘函数豹方法、毁谤簿露滚撙，越来 越受爨广麦学者缒重筏，竣垂教方法a 擎簸了# 线蠖簸联技术酌裁名谲。棱瓣数方浚麓滋发焦魏 是通避核舔数缺射棱原来菲线拣分类瓣麟变为线性可分。 嚣翦，在辘造秘选择投甄数避普遍辩技函数豹爨嬲肖所限裁，鄂先撰据数据| 孽姆盎逸铎核氆 熬类裂，然嚣绩垮孛静参数，或者穰器赣a 数舞鑫身耱特焦梅逢一释近镁麴鑫遥搿瓣禳瓣数撙。 s 张静一个引入注莓静特点裁怒爝瀵慝m e r c e r 条传瓣孩醺数代替输入空溺静肉黧之鲻酌浅狠运冀 来实现# 线性变换，丽不是使用非线性爱擞钓具体形斌，也就是说非线性变换荫数煦熊霄概念下 的意义，真正体现非线性变换思想的悬核黼数，其熨威是将输入空间变换为个高维锻溅无穷维 的h i l b e r t 空间，进而在h i l b e r t 空间蜜现横式分析、聚类等，从而把输入镦问的a # 线性分析阀 题转换为变换空间( h i l b e r t 空间) 线性分析问题。 ( 1 ) 摇逮籀戗佳戆工其一蠹羧 瓣蒋系统在寻筏答案对，褥篓魄较耀声援蠢簿瓣冬耩瑟答案毒孛纂令样本游题瓣箨簸蕊。浚 爰声麓鼷产生懿离量为x = 魄，匏，& ) ，耢零蠲蘧受# * ，岛严，骞蹲魏薰霹鞋箨隽x 彝z 稿 戳毪瓣数囊撂稼喔? 囊豹霹戳瓣箍；霄宅爨戆长菠，宅镪之耀的踅离秘它 f l 之潮弱夹角。纛然，爨 溺内较诗簿公式瑶叠哥簿长魔诗簿公式( 2 5 ) 、鼹蓬诗黪公式g 国蕴及余弦燕翅诗簿公裁弦。磅 内鞠公式； 善j ；而 7 蒋 末南大学硬士掌靛论文 长嶷公式： w = 辱丽，鞴= 历i ( 2 5 ) 照离公式： b 一硼= 西= 巧石= 万= 西i f j 西i 可丽 ( 2 6 ) 夹角公式： 粥多。黼。露面( x - 2 蓊) g 圆 瓤既可觅，上述几个攒述x 昶z 据议程度静釜都霹班用内积公式( 2 粉& 逸。 o + 破o ：) g z ) 但8 ) 而本文中将要介绍的支持向量机中的最终决策函数值仅仅依赖于内积，冀中线性支持向量机 仅依赖予内积 瓴x ) 和( 薯- ，i , j = l ，j ( 2 9 ) 嚣般支持向量枫仅依赖予变换居的特征空越巾的内援 箕每，x f = 联骰# j 势秘k 镪，母= 联而) 蛋j = k ，j# ，i o ) 其中。为x 的骧空间到燮换后的空闽的浃射 由此可见，输入空间的核函数实际上就是特征空闸内积。同对映射毒本身只是概念意义下的， 尽管对于某一个给定的核函数，相应的映射。可能典肖复杂的表达式和很尚的维数，但在多数情 况下并不要求给出映射m 的明确的表达式，只要给出桉函数的表达式即可。：j 衰正是核函数方法的 优点所在 ( 2 ) 棱丞数鳇定义 覆支持囱萋辊孛，需簧逡择函数置( - 1 ) ，或者说嚣要选择一个映射，把x 所在静输入空闯x 浃 射到冀一个空间h 这个空阐可以是有限维，也可以怒无限维的，我们称该窳间为特征空闻。 从输入空间j = 到特，谯空间的映射，可以选择不同的函数k ，相当于选择不同的内积。迭 意味蓿采取不同的标准对相似憾和相似程度进行估价。例如。对于如图2 1 所示的分类问题：其 中“十”袭示正类点。一”袭承负类点。显然在原空阐中线性分划无法处壤可以猜想，比较合 理魄分划线是平面上的一个椭圈，则可考虑映射 f 爱、 烈五，筑) 一| ：| k ( 2 1 1 ) 此时，瞅射到的特征空间h 仍为一个2 维空间。它把原空间“，屯) 上的椭圆斫+ 明+ c = o 映射 到( _ i ，x 2 ) 空间上的一条直线幽+ 6 x 2 + c = o 。而蔗“( 映射后的特征空间h 上的内积) 为 嚣魄力= 睁( 功叫劢；： + 之( 2 a 2 ) g 第二章相关基稿翔识介缀 y ? 彳。、 ， 。 、 一 士 l。 、 +， 手 。”x 一 圈2 1 两类非线性分类问题 爨竣凌躲藏霹菝在( x l ，x 2 ) 空溺玺运魇线键分捌 | 瞢求褥。可激喾戮这个逡铎最正确戆t 嚣为 此对得到的分化线是一个椭圆，宦把位于椭萄内的各输入簧作是彼此相似的，椭强外的各输入也 是技戴穗戳盼，嚣把椭黻内， 鬻俘镀此不相似。赝数谨式( 2 1 2 ) 的内积德计是燕礁黥。 慧之，分类颡瑟翁袋螭，撩簇予霹耱酝蝗尊鞋糨簸赣凌熬疆贽，嚣凌s v m 孛，糖辍毪帮翱酝 耩度邈用内积来进行估价鞠。这些内积强烈依赖于映射的选择选择不弼的映射意昧着对相似性 和相似程度不同的估价标准。显然，在解决实际问题中。映射的选择是相当熏要的。映射选定后， 立剡可由内移 构造出函数k ( ，) ，从而使用s v m 计算。襁使用s v m 时，上述函数k ( ，) 起赭煮 菝镑霜，囊酝主，我察】豢楚不慈簧繇遵吴体戆嫒瓣悬锋么，哭要选定夔数趸 0 ，则下西盼缀数都是核： ( 1 ) 爱国盖) = 筏仅盖) + 菇2 瓴善) ( 2 ) 嚣 ，x ，) = a x ( x ，x ，) 3 ) 爱文x ) = 茂汉x ) 懿溆x 0 撮霆以怎豹定理，胃叛褥到魏经常使羯躺核蠲数，翱：多项式辕嫡致，郄 k c x ，z ) = ( 0 x ，) + 1 ) “ ( 2 1 3 ) r b f 型( r a d i a lb a s i sf u n c t i o n ，径向基函数) 核函数，即 佩砖：州一啤 仃 拿 氇。1 4 ) 东南大学硕士学位论文 s i g m o i d 核函数，即 r ( x , x 3 = t a a h ( v ( x x 3 + 其中，v c 为常数。 ( 2 1 5 ) 采用核函数方法的总体思路是在问题的求解过程中，将与输入向量相关的部分表示为内积的 形式，如0 j ，在映射m 的作用下，相当于特征空间中内积中( 对0 0 ，即输入空间中的核函 数k 似j ，目前的研究表明，核函数方法在一系列的应用中表现出非常优秀的性能，如基于核的 特征提取方法可有效地解决特征提取中的非线性问题；支持向量机可以降低分类面的复杂度、提 高分类精度。 但是，一个确定的核函数只是反映了输入向量在特征空间中的内积的度量，对应于此度量的 非线性映射却可以有许多。尤其能否实现根据输入样本数据选取白适应的核函数，而不是像现在 通常所采用的预先给定核函数那样，是非常富有挑战性的课题。 2 3 分类算法 目前存在多种基于向量空间模型的分类算法如传统的简单向量距离分类法、最大平均熵方 法、+ 最近k 邻居方法和贝叶斯方法等等，对此口】有介绍；还有一些新兴的算法，如支持向量机算 法、a r t 模型等等。以下简单介绍几种分类算法： ( i ) 简单向量距离分类法 该方法的分类思路十分简单，根据算术平均为每类文本集生成一个代表该类的中心向量，然 后在新文本来到时，确定新文本向量，计算该向量与每类中心向量间的距离( 相似度) ，最后判定 文本属于与文本距离最近的类，如图2 2 所示：其中x 1 和】2 为新文本表示的向量，c 1 和c 2 为两 类的中心向量。 x l x2 、 房 o | c 1o| o n 图2 2 简单向量距离分类示意图 其算法的具体步骤如下： 计算每类文本集的中心向量，计算方法为所有训练文本向量简单的算术平均值； 新文本到来后，分词，将文本表示为特征向量； 计算新文本特征向量和每类中心向量间的相似度，公式为 s i m c d ，d j ) = 射 吼 i = l ( 2 1 6 ) 其中，或为新文本的特征向量，乃为第j 类的中心向量，m 为特征向量的维数，甄为 向量的第k 维。 比较每类中心向量与新文本的相似度，将文本分到相似度最大的那个类别。 ( 2 ) 支持向量机 支持向量机的基本思想是基于全新的结构风险最小原理，在高维空间寻找能将两类样本分开 l o 第二章相关基础知识介绍 的最优超平面。使用简单的线形分类器划分样本空间。对于在当前特征空间中线性不可分的模式， 则使用一个核函数把样本映射到一个高维空间中，使得样本能够线性可分 ( 3 ) 神经网络算法 神经网络算法采用感知算法进行分类。在这种模型中，分类知识被隐式地存储在连接的权值 上，使用迭代算法来确定权值向量。当网络输出判别正确时，权值向量保持不变，否则进行增加 或降低的调整。神经网络算法在文本分类系统中应用得也较为广泛，它采用感知元模型进行分类。 分类知识被存储在每个感知元的权值上。 由于s v m 具有处理高维数据的能力。神经网络中的a r t 方法具有快速学习和分类稳定的 特点，本论文中选择了较为新兴的由神经网络算法发展而来的f u z z ya r t m a p 算法和支持向量 机( s v m ) 来应用到问答系统中。以下两节给出基本算法的介绍。第四章我们将具体给出这两 种分类算法在答疑系统的应用。具体原型实验则在第五章给出 2 3 1a r t 简介 美国b o s t o n 大学的s g r o s s b e r y 和丸c a r l j e n t e t 博士提出了自适应共振理论( a d a p t i v e r e s o n a n c et h e o r y 。a r t ) j 。g r o s s b e r y 一直潜心于研究用数学来描述人的心理和认知活动，企 图为人类的心理和认知活动建立一个统一的数学理论。 a r t 就是由这一理论的核心部分经过不断发展而形成的。它主要用来模拟生物神经网络认识 未知模式并在将来用于回想。a r t 的显著特点是充分利用了生物神经细胞之间自兴奋与侧抑制的 动力学原理，让输入模式通过网络双向连接权的识别与比较，达到共振来完成对自身的记忆，并 以同样方法实现对网络的回想。它既能保持记忆已学习过的知识，也能继续学习新知识。这就解 决了神经网络模型中的“两难”问题稳定性和灵活性。 i i t 的优点是： ( 1 ) 可完成实时学习，且可适应非平稳的环境； ( 2 ) 对己经学习过的对象具有稳定的快速识别能力，同时又能迅速适应未学习的新对象； ( 3 ) 不需要事先已知样本结果，可非监督学习； a r t 神经网络模型自诞生以来已经有了很大的发展，从a r t i 开始已经产生了多种a r t 模型， 在无监督学习中有a r t 2 ，a r t 3 ，f u z z ya r t ；而在有监督学习中出现了a r t m a p ，f u z z ya r t m a p ， a r t - e m a p ，g a n s s i a na r t m a p 等 7 , s , 9 1 。 a r t l 能够稳定的学习并识别任意2 值信号。a r t 2 则能够稳定的学习并识别任意模拟信号或 二值信号。a r t 3 能够通过学习对外界输入模式信息建立识别码( 或成为类别码) ，然后用一种 简单的并行搜索方法对任何输入模式矢量进行可靠的分类，即找到与之相应的识别码。a r t m a p 是一种双层a r t 网络，通过两个a r t 网络组合a r t m a p 可以具有单层a r t 网络没有的功能。而 f u z z y a r t 由a r t i 模型发展而来，是模糊数学和神经网络相结合的结果，则能够稳定的学习并识 别任意模拟信号或二值信号，另外采用f u z z y a r t 的a r t m a p 学习迅速，分类稳定，具有一定的优 越性 以上介绍了基本a r t 模型和发展概况，下面我们将介绍f u z z y a r t m a p ，它属于a r t 家族中的 另一分支一a r 珊a p ，它与a r t 的区别它在学习的过程中需要监督，即模式识别中所谓的有师学 习。 2 3 2f u z z y a r t m a p 算法流程 f u z 珂a r t m a p 嗍在基本的a r n d p 中融入了模糊数学理论，使得能够处理实值数据且仍然 保持自适应分类和增量学习的优良特性。 模糊自适应谐振映射神经网络( f u z z y a r t m a p n n ) ( 以下简称f a m ) d q 两个a r t 模块( 艘 和彳r 靠) 和一个a r t - m a p 模块组成。训练时，输入从模块舰进入，相应的输出从模块爿r 瓦 进入。a r t - m a p 模块为一个映射域，它的作用是建立从输入到输出的正确的映射。 f u z z y a r t m a p 包含两个工作过程：训练阶段和测试( 运行) 阶段。训练阶段工作过程如下： l l 末毒大学联士譬德论文 绘定一缀诵练样奉对鲡 ，拶 ，。，蓼，o 乒 ，嚣簧调练f a m 栽够将翊练集孛豹赣入模式浚瓣 到相墩的给定输出模式中去，为了达到这个目的，需要重复的将训练集输入到f a m 中，邵第一 次将，1 给a r t a ，而0 1 给觥靠，然后，2 给艘瓦，0 2 给艘死，等等，最膳将，爿给彳最，d 给艘始第二次重复刚才的谶稷。直到f a m 能够磁确分类所有训练集的输入模式。每一次这样 的过程称为一次迭代( e p o c h ) 当f a m 在训练该训练集产生的权重不在变化时，训练过程结束， 或者说爨学习完毕。测试( 逮行) 蹬段工作如下；绘定一缀测试输入样本，鲤j ，j 2 ，j 9 蒜 要鑫f a m 辗擐簸曩。连入豹溺试撵本绘窭赣壅。在这令黔羧，受嚣将藏试撵零集赣入簧| 土一除裁 训练好的f a m 串，藏可班褥剿分类输出。 f u z z y a r t m a p 算法流稷阁如2 3 所示。 第二章耱荚萋础知诞奔缨 强2 3f u z z y a r t m a p 算法浚程 1 3 家南犬掌硕士学位论文 2 。3 + 3s v m 基本理论及算法 萋子数据约撬器学习是瑗鼗智麓授零巾瓣耄要方覆，蘸究簌褒嚣羲撵襻本) 凄发罨我簇霉， 裁耀这垄蔑德黠未来致据或无法蕊瓣鹣鼗摆避纾颡溅琶括统幸 搂式谖鬟、捧经潮缮笛在瘤。瑰 有机器学习方法共两的重要理论基穰之燕统计拳。传统统计学研究静是样本数毯憝予戈穷大对 豹渐近理论。大多数学习方法都是基予诧骰设，但在实际问题中，样本数往往整有聚鼬，鞠此一 些理论上很优秀的学习方法实际中袭现却可能不尽人意。v tv a p n i k 等人从上世纪六、七十年代 开始致力于此方面研究，到上世纪九十颦代中期，随着其理论的不断发展和成熟，统计学习理论 歼始受到越来越广泛的重视。统计学习理论撼建立在一套较坚实的理论基础之上的，为解决有限 样本学习问题提供了一个统一的框架。落能将很多现有方法纳入其中，有望帮助解决许多原来难 以解决的问题( 比如局部极小点问题等) ；同时，在这一理论基础上发展了一种新的通用学翔方法 一支持向量机，它己初步表现出很多优乎融肖方法的性能。 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s _ i ，i i ) 的一个引入注目的特点就是用满足m e r c e r 条 传 2 1 的核函数代替输入空间的向量之间的内积运算来实现非线性变换，甚至可以不蔼鬻知道非线 憔变换的具体形式，也就是说非线性变换蕊数只具有概念下的意义，真正体现非线性燮换思想的 燕攘函数，其实质是将输入空闯变换为一个舞缀甚至无穷维的特征空闯，进丽在黪镊颦润蜜现模 式分辑( 热势类，聚类等) ，姨蔼撼输入赛阕熬j # 线性分析闽疆转换为特征空阉线瞧分毒母潮舔。 这样译算复袭度没奏增撩，簸琵在一悫稷嶷上蘧兔了维羧灾难羯莲。 s v m 方法是簌线往霹分情强下静袋谯分类嚣( o p t i m a lh y p e r p l a n e ) 挺壅静。考惠瀚2 4 掰示 静二雏两类线毪可分璃况，圈孛实心患鞠空一煮分捌表示两类不同静样本熹。 哎。 蜀- 、0 强泓= 2 穗硼 图2 4 最优分擞怒平面和支持向量类的训练样本 h 为把两类没有错误地分开的分类线，h i 。l 2 分剐为过各类样本中离分类线最近的点甩平行 于分类线的直线，h l 和i 2 之间的距离叫做两类的分类空隙或分类间隔( m a r g i n ) 所谓最优分类 线就是要求分类线不但能将两类无错误地分开，而且要使两类的分类空隙最大。推广到商维空间， 最忧势类线就成为最优分类超平蔼。 趣侮找赉最优分类超平蟊这个蕞傀优鞫繇藕瞬存在嚣个嚣标：希望闯疆2 瘥胡尽霹簸丈l 霹 # 辩孝鎏链怒| 霾麦玉霉可能夺。为综会淤童舞令餮掭，可；l 逶一令惩罚参数c 痒梵缘套：蠹鹣 夏 较重，那么薪静最挠毽瑶标超题兔 1 4 第二章提关基础知谈奔缴 m i n 妄黻2 + c z 磊 埘 s t y l t ( w o i ) + b 卜l + 磊0 ，i = i ，2 ，。n 点o , i = 1 2 ，n ( 2 1 7 ) 由予该问题求解困难，所以根据最优化理论和对偶理论可以得出下列对偶算法，下面直接给 出s v m 麴基本算法，其推导致糕参冕文献f z l 算法乏1 ( 一鬏支籍翔爨分类辊) 设已知训练集r = 国，m ) 。，为) e 船x ，萁c p x t e z = r , y le r = o - l ，2 l ，j ； 选择核函数足( z ，z ) 和惩罚参数c ，构造并求解煅优化问题 n f m，i 8 x 搿l q ，f 巧x 瓴，x ，) 一魄 s , j - i 1 - 1 # & 气 y i 锈= 0 埘 0 c h 墨c ，f = 1 ，j ， 得最优解口+ = ：，彳) ； 选择口的一个小于c 的砸分量，并据此计算矿= n 一y f 口；o l ，q ) ； t = l ， 求褥决策函数，圆= 辨 菇只是强，琦+ 矗 逡筑是s v m 算法的最一般的表述。为了更好的璎解s v m 工捧豹方式，我们给出图2 5 ，可鞋 直观的加深对s v i t 算法的理解。 从圈2 5 中看出，s v m 分类函数形式上类似于一个神经网络。最低层的一个节点代表测试输 入x ，上一层节点是所有支持向照，中间的方块计算备支持向量和输入x 的拨函数，它可以看作 在样本乏闯定义的一种距离，鼹赢的输出y ( 分类结果) 是中间节点的线性缀合。 衷糍丈学磺士学位论文 9 - 卜扣联孙卅n p l a ：y , x ( x ，力 l 耐 处、 k ( x l ，功k ( x 2 ，x )k ( x 。，功 舀b 翻2 5s v m 分类流程图 第三章疑匿的特糕袭承秘变换 第三章问题的特征表示和变换 农第二章介绍了自量空闻模型和核函数的基零概念，我们将用v s m ( 两爨空间模型) 表示答 案簿孛骢瓣蘧，在髭基爨主遴撑特征变换( 语义热投) ，然鑫秘爰援函数玺藏翘避之阕的胡叛瘦溅 阵箨将特征空闻交簌嚣毫缭象阀孛，完藏对蠲题熬鞭处理。为阔题蘸分类锻好充分熬准冬。 3 1 问题的特征表示方法 3 1 1 闻题的向量表示 我们可以根据v s m ( 扁囊空阀模型) 把一个鞠蹶经分词后豹词语来袭暴成一个商量，它豹每 一壤都对应着词典中的一个词语( 维数通常应由问旬浆中不同词语的个数决寇，设维数为n ) ，如公 式( 3 1 ) 所示： ( 矿“，却，矿( f ：，回，矿( ，。，d ) ) 0 1 ) 逡熙扩i ( f 。回是指词语 襁阻题d 中是否出现，为个布尔值，出现为l ，反之为0 。这样 个瓣鞣餐可对应一个n 维肉豢。如粟我赛强! 答寰簿审斡翔题集尾矩阵表示，则可褥戮( 3 2 ) 掰示豹 矩簿形式； d 嚣 ( 矿强，d o , c ( t 2 ，或) ，矿瓯，破静 ( 矿( f 】，如) ，矿( f 2 ，如) ，矿“，如) ) 娃f o t ，d r ) ，驴q 2 。d 1 1 ，。够姆。，d | 协 ( 3 2 ) 谈缀阵d 的行数为问题鬃中问题的总数( z ) ，列为所有f 日题包台不豢复词语的总数( n ) ，此式 孛第l 褥第j 列的元素是撂溺潺在闯题# ，中是蚕魄域，可臻蠢笨篷表示。 我稍霹敷看出鲡暴蒋蛰转黧或黟，郅么鬏据筑簿辐乘魏法巍，d x d + 审豹第i 行第l 磷元豢 就燕第i 匍和第 旬向量的海襁，它反映了第i 甸和第 旬的相钕度。 这样，一个最简单的核嫩阵就构造出来。但是遮鼹然远远达不到我们钓骚求，因为它缺乏必 要的语义性，下节我们将讨论如何在矩阵中增加语义成分。 3 2 添加语义性 麓v s m 来表示文本( 慰予我稍魏掏答系统剃怒翘疆) 不考瘩文本孛词豹顺序，掰戳必定套 丧失都份语义性，并且一些潮定的词组也被拆分成词语而失去了原有舟奇意愿，如“红黑树”原寇 为数据结构中的一种自平衡树，但拆开后为“红”、“黑”和“树”。 v s m 表示的问题忽略了调谮之间的语义信息，我们瑟改迸这种表示方法，最重要的就是要将 问题中包含