（计算机软件与理论专业论文）基于语言模型的网页排序问题研究.pdf

南开大学学位论文使用授权书 l i i i l lliltlilti i l l l l l l l l l l l l l l l l l li ll11i t l l y 18 14 2 11 根据南开大学关于研究生学位论文收藏和利用管理办法，我校的博士、硕士学位获 得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范围内的学位论文使用权，即：( 1 ) 学位获得者必须按规定提交学位论文( 包 括纸质印刷本及电子版) ，学校可以采用影印、缩印或其他复制手段保存研究生学位论文， 并编入南开大学博硕士学位论文全文数据库；( 2 ) 为教学和科研目的，学校可以将公开 的学位论文作为资料在图书馆等场所提供校内师生阅读，在校园网上提供论文目录检索、文 摘以及论文全文浏览、下载等免费信息服务；( 3 ) 根据教育部有关规定，南开大学向教育部 指定单位提交公开的学位论文：( 4 ) 学位论文作者授权学校向中国科技信息研究所和中国学 术期刊( 光盘) 电子出版社提交规定范围的学位论文及其电子版并收入相应学位论文数据库， 通过其相关网站对外进行信息服务。同时本人保留在其他媒体发表论文的权利。 非公开学位论文，保密期限内不向外提交和提供服务，解密后提交和服务同公开论文。 论文电子版提交至校图书馆网站：h t t p ：2 0 2 1 1 3 2 0 1 6 1 ：8 0 0 1 i n d e x h u n 。 本人承诺：本人的学位论文是在南开大学学习期间创作完成的作品，并已通过论文答辩； 提交的学位论文电子版与纸质本论文的内容一致，如因不同造成不良后果由本人自负。 本人同意遵守上述规定。本授权书签署一式两份，由研究生院和图书馆留存。 作者暨授权人签字：扬波 2 0 1 0 年5 月2 4 口t - - 4r ，j ，1 南开大学研究生学位论文作者信息 论文题目基于语言模型的网页排序问题研究 姓名杨波学号 2 1 2 0 0 7 0 3 6 0 答辩日期 2 0 1 0 年5 月2 2 日 论文类别 博士口学历硕士刁硕士专业学位口高校教师口 同等学力硕士口 院 系 骶软件学院 专业 计算机软件与理论 联系电话 1 3 8 2 1 5 0 3 5 5 0e m a i ls t r u o o l e v b o m a i l c o r n 通信地址( 邮编) ：天津市南开区南开大学西区公寓3 3 - 4 0 3 ( 3 0 0 0 7 1 ) 备注：无是否批准为非公开论文 否 注；本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写( 一式两份) 签字后交校图书馆， 非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 。擎褂皇茸礤珥素士汤非基t 审鬲箪投毒￥妊掣俐彰茸歌哥毒妊妤非髫 纬固辫蕈兽专恶( ；： 鲤单一) 皇藓晕勤甲。茸融珥毒驹千班、千蕈i 肇鲥明壬群群雏茸娶斗砰斟宰：嚣 c 、 z 茸砚妊妤非紧戳珊显瞽 ：瑕母 ，、，一 ：( 晰甲) 弭可i 手掣甄 毗胪“固和助咿 n m u 县卑当独 珊9 桫坳心钾! 而牟 r 列哆似游 鲻鎏黝 口千逾华杂岛刨口嘶磷珥掣口珥杀环牟千、亟周千逾鲻杀口千斟。暗椠茸砚 眩咖匆o 睨 瞵目挺最o o 乏o 似，飞鲁秦 溯卿 零辅 罾桫可色i 钐僻些翻今师獬# 钎争髟 目嚣茸砚 冒署晕勘萃拱珥毒鬲草地毒￥拦阜 目孔皆匆o o z ：右焉y 砰群磊岩勘 。晕禺髫锋囤咄捌甭延擅甲辑丝￥一兽焉锋砰群章。犁群娶丁皋聚晕刨y 卓 。酉目y 章甲酱g 翟业帮采回生囡晦磋一母掣明茸现章雪殇与狲壬印茸拱砑嘉朝聋蕾 。挺嚣茸拱罂娶目冀罾勘朝稻毕勤阿刨睁筐杀杀￥拦掣翠瞽茸砚珥杀朝y 章：祟凄y 卓 。u n q x o p u ! 1 1 0 0 8 ：1 9 i 0 z i i 。乙0 u ：如q ：辚幽勘皓圈群互莓鬻硝士胃覃拱 。覃识拦抒刨暂砷哇革暂g 罨磷暂那讯群哇覃鬻将掣业掣刮瞪毋哿茸观珥杀妊哥非 。胜砰朝茸砚擎髯辫颧砚并翠禺哿y 卓轴刨。暂殂肾署身檠惭胚彝豳￥胖并取觐 犁辫骤茸拱珥杀翠醉y 劲# 硎士审茸理覃砚砑杀明圈燮犁群革瞢礴到帚士审( 平柴) 性酶半 杀国串唑蚶琶拉冒署馨性国七b 叫珥杂碎群某勤茸拱碍杀( 哥) 3 茸砚珥赤朝拦影萃鬻再责举群 僻晕磷叫杀￥妊掣举群￥晕峰革辚馨诽( ) o 暂砷冒署颦丐翕碡生、甄腱茸弓茸观谣询辫 茸、率弭咨目茸砚艳篱丁豳圉弭翠罄豳雨蛳e i d 辫静静鳕瞬岛勘沣囤翠僻矮紧勤茸砚码杀朝 拦哥琳伯且弭秦明目掘性哇杀辚鬃( z ) o 窜辫嫌茸号茸砚砑杀千瓷科杀￥妊掣y 蝣冀 茸砚珥素雨琶扭型哿硝圭滞暂融首疆由黪、由缮甘当询乜珥杀( 硎士审涩卓踏由驾掳辨 回) 茸砚珥杀革酐犁群斟磁哂岩含； 罪砑杀( i ) ：曲碑茸珊茸拱码索脚甲国鹫犁群翟碑勤是 翠阜啡杀￥妊单。犁群蟊昌朝茸唑哇逖劲茸拱珂杀雨延掘￥阜杀￥妊单辫上弓毕y 章 。狲士审珂醉谣章彗狮茸识珥素明y 章萆瞥杀￥妊掣掣蝥瞬岩勘 罪码杀千进、千捌朝辫棰餮峰蕊暑目唑哇撵劲茸旗珥杀雨始擅士￥杀￥妊单群群 沣砰狲茸觋茸观码秦杀￥妊单 l 夏人一 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行研究工作所 取得的研究成果。除文中已经注明引用的内容外，本学位论文的研究成果不包 含任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所 涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本 学位论文原创性声明的法律责任由本人承担。 学位论文作者签名：扬波2 0 1 0 年5 月2 4 日 非公开学位论文标注说明 根据南开大学有关规定，非公开学位论文须经指导教师同意、作者本人申 请和相关部门批准方能标注。未经批准的均为公开学位论文，公开学位论文本 说明为空白。 论文题目 申请密级 口限制( 2 年)口秘密( 1 0 年)口机密( 2 0 年) 保密期限2 0 年月 日至2 0 年月 日 审批表编号批准日期2 0年月日 限制2 年( 最长2 年，可少于2 年) 秘密1 0 年( 最长5 年，可少于5 年) 机密2 0 年( 最长1 0 年，可少于1 0 年) 摘要 摘要 排序问题是信息检索领域的核心问题，多年来一直是信息检索领域研究的 热点。w e b 是当今最大的非结构化数据集合，如何排序w e b 文档必然成为了信 息检索领域研究的焦点所在。而语言模型建立在完善的统计理论基础之上，可 以采用统计学方法便捷的进行模型参数估计，同时能够很好的适用于各种复杂 的检索问题。作为处理网页检索问题的性能最好的非监督方法之一，在引入到 信息检索领域之后，就得到了大量学者的重视和研究。近些年来，基于语言模 型的方法逐渐形成了一套完整的检索模型体系。经典语言模型在处理网页排序 问题时，存在着对查询单词之间的关联考虑不足、进行未见词平滑时对数据的 层次没有加以更好的利用以及对于文档先验概率的忽视三个方面的问题。本文 由语言模型中文档查询似然概率、未见词平滑算法和文档先验概率这三个方面 入手，探讨了其中的一些改进。 本文由基于贝叶斯风险最小化理论得出的相似性公式为出发点，以查询产生 每个单词及元组的概率不同为假设，提出了考虑查询单词之间多个元组共同出 现的概率分布的方法建立查询模型。并且，在此模型基础之上，提出了基于多 元组的文档查询相似度算法。同时，考虑了算法实现的可能性和可用性，给出 了一个切合实际的算法，并且用实验验证了算法的有效性。本文在实验结果中， 分析了该算法的引入所带来性能提升的主要原因，总结了该算法本身的优劣。 同时，本文探讨了互联网数据本身的结构特性和层次特征，即互联网本身是 由文档、目录、站点、整个互联网这四个层次逐层组成的有机结构。本文在此 基础上，提出了一种基于这四个层次数据来进行语言模型中未见词平滑的算法。 同时，本文考虑了多层次算法实现细节和数据结构相关内容，并且用实验验证 了多层平滑算法由于加入了更多的层级信息，给平滑带来了一定程度的性能提 升。 与以往的工作不同，本文将文档的先验概率视为语言模型非常重要的一部 分，本文通过探讨多种文档先验概率知识和文档相关性之间的相关关系来说明， 很多与文档和查询内容无关的先验知识可以用于排序之中。同时，本文尝试了 使用朴素贝叶斯方法来进行多种先验知识的融合，并对这种融合后的语言模型 的性能进行了实验验证，结果表明语言模型的整体性能获得了很大的提升。 i 摘要 关键词：信息检索网页排序语言模型平滑算法 a b s t r a c t a b s t r a c t r a n k i n gp r o b l e mi se s s e n t i a li nt h ef i e l do fw e bp a g er e t r i e v a la n dh a sb e e na h o tr e s e a r c ht o p i co fi n f o r m a t i o nr e t r i e v a l l a n g u a g em o d e l ，a so n eo ft h eb e s t u n s u p e r v i s e dm e t h o d sd e a l i n gw i t ht h ep r o b l e m ，h a sg o r e nag r e a td e a lo fa t t e n t i o n a n dr e s e a r c hs c h o l a r ss i n c ei t si n t r o d u c t i o ni n t ot h i sf i e l d i nr e c e n ty e a r s ，ac o m p l e t e l a n g u a g em o d e l i n gr e t r i e v a ls y s t e mi sf o r m e dg r a d u a l l y s i n c et r a d i t i o n a lm o d e l s d o e sn o tc o n s i d e rt h er e l a t i o n s h i pb e t w e e nq u e r yw o r d s ，t h eh i e r a r c h yo ft h ew e ba n d d o e sn o tp u ta l le m p h a s i so ft h ep r i o rk n o w l e d g e ，w eu s eam o r er e a l i s t i cq u e r y m o d e l i n gt oe s t i m a t et h es i m i l a r i t yb e t w e e nt h ed o c u m e n ta n dq u e r y , a n de x p l o i ta m u l t i p l eh i e r a r c h yd a t as t r u c t u r et os m o o t h i n g a l s o ，w et r yt oc o m b i n em o r et h a n o n ek i n do f p r i o rk n o w l e d g e o fd o c u m e n tr e l e v a n c ei n t oo u rm o d e lt om a k eab e t t e r p e r f o r m a n c e b a s e do nt h e o r yo fb a y e sr i s km i n i m i z a t i o n ，an e wq u e r ym o d e l i n gm e t h o di s p r o p o s e d i nt h i sm o d e l ，q u e r yw o r d sa r cd i v i d e di n t og r a m sw i t hd i f f e r e n ts i z e ，a n d w ea s s i g nd i f f e r e n tg r a mw i t hd i f f e r e n tw e i g h t w i t ht h i sq u e r ym o d e l ，w ep r o p o s ea n e wd o c u m e n tq u e r yl i k e l i h o o dm e t h o d as e to fc o m p u t e ra l g o r i t h m sa n dd a t a s t r u c t u r ei sd e s i g n e dt om a k eo u rp r o p o s e da l g o r i t h ma f f o r d a b l e w er u ns e v e r a l e x p e r i m e n t st oe x a m i n et h ee f f e c to f o u rp r o p o s e da l g o r i t h m i nt h i sp a p e r , t h ec h a r a c t e r i s t i c so ft h ei n t e r n e td a t aa r ee x p l o i t e dt oc r e a t ean e w m u l t i - l a y e rd a t a - b a s e ds m o o t h i n gm e t h o d t h em o s ts i g n i f i c a n td i f f e r e n c eb e t w e e n t h i sm e t h o da n dt h ec l a s s i c a lw a y si st h a tt h el a t e ro n l yd i v i d e dt h ed a t as e ti n t ot w o l a y e r s ，o n ee n di st h ec u r r e n td o c u m e n ta n d t h eo t h e re n di st h ew h o l ed a t as e t b u ti n o u rm e t h o d ，w ed e s i g na4l a y e rw a yt os m o o t ha nu n s e e nw o r d a l s o ，s e v e r a l e x p e r i m e n t sa r ed e s i g n e da n d r u nt ov e r i 哆t h ee f f e c t i v e n e s so ft h i sm e t h o d w h i l em o s to fp r e v i o u sw o r kj u s ti g n o r e dt h ep r i o rk n o w l e d g eo fd o c u m e n t r e l e v a n c ew h i c hi si n d e p e n d e n to nt h ec o n t e n to fc e r t a i nd o c u m e n t ，w eu s ea s y s t e m a t i c a lw a y t oe x a m i n et h ei m p a c to fs e v e nk i n d so fm a i np r i o rk n o w l e d g e a n d an a i v eb a y e sm e t h o di sc h o s e nt oc o m b i n et h e s ek i n d so fk n o w l e d g et or a i s et h e p e r f o r m a n c eo fo u rs y s t e m i i i a b s 仃a c t f i n a l l yw ec o m b i n eo u rn e wp r o p o s e dd o c u m e n tq u e r yl i k e l i h o o dm o d e l w i t h p r i o rk n o w l e d g ee s t i m a t i o n a n dg e ta ni m p r o v e dl a n g u a g em o d e l w i t hs o m e e x p e r i m e n t so nt h r e et r e ct a s k g o vd a t a s e t ，i ti sp r o v e dt h a to u rm e t h o db r i n g s m u c hr a i s eo ft h er e t r i e v a lp e r f o r m a n c et ol a n g u a g em o d e l i n gw a y k e yw o r d s ：i n f o r m a t i o nr e t r i e v a l ，w e bp a g er a n k i n g ，l a n g u a g em o d e l ，s m o o t h i n g a l g o r i t h m s i v 目录 目录 摘要i a b s t r a c t i i i 第一章绪论l 1 1 引言l 1 2 研究现状2 1 2 1 信息检索中的排序模型2 1 2 2 语言模型3 1 3 本文主要研究内容3 1 3 1 基于多元组的文档查询相似度算法研究4 1 3 2 基于互联网多层次特性的平滑算法研究4 1 3 3 基于朴素贝叶斯的文档先验概率估计5 1 4 本文组织结构5 第二章相关工作综述6 2 1 信息检索6 2 1 1 布尔逻辑模型6 2 1 2 向量空间模型7 2 1 3 概率检索模型8 2 1 4 统计语言模型9 2 1 5 基于监督学习方法的排序模型。1 0 2 2 统计语言模型详述l2 2 2 1 信息检索中的语言模型1 4 2 3 信息检索评价指标1 7 2 3 1m a p 1 7 2 3 2i n d c g l8 第三章基于互联网特性的文档查询相似度估计2 0 3 1 引言2 0 v 目录 3 2 基于多元组的文档查询相似度算法2 0 3 2 1 查询模型2 0 3 2 2 基于多元组的文档查询相似度算法2 4 3 3 基于多元组的文档查询相似度算法性能分析2 6 3 3 1 实验平台简介2 6 3 3 2 实验结果及分析2 8 3 4 基于互联网多层次特性的平滑算法3 2 3 4 1 多层次平滑的意义及模型。3 2 3 4 2 多层次数据存储结构及构建算法。3 3 3 4 3 基于互联网多层次特性的平滑算法。3 4 3 5 基于互联网多层次特性的平滑算法实验与分析3 5 3 5 1 实验设置3 5 3 5 2 实验结果及分析3 6 3 6 基于互联网特性的文档查询相似度算法实验及分析3 9 第四章基于朴素贝叶斯的文档先验概率估计。4 l 4 1 引言4l 4 2 文档结构知识与相关性4 l 4 2 1u r l 深度4 2 4 2 2 文档长度。4 3 4 2 3l n l i n k s 和o u t l i n k s 4 5 4 2 4p a g e r a n k 、h i t sa u t h o r i t y h u b 4 6 4 3 文档先验知识融合4 8 4 4 实验及分析4 9 4 4 1 原始文档查询相似度数据4 9 4 4 2 实验及结果分析5 0 第五章结束语5 2 5 1 本文工作总结5 2 5 2 未来工作展望5 3 参考文献5 5 v i 目录 致谢5 8 v i i 第章绪论 第一章绪论 1 1 引言 随着互联网规模的不断扩大，它已经成为了全球最大、最广泛使用的信息 库。同时，越来越多的人开始使用互联网，据统计全球2 0 0 8 年底已经有1 0 亿 网民。并且，随着w e b2 0 时代的到来，越来越多的网民不只停留在浏览信息的 阶段，他们也开始创造信息。这样，网络给我们带来了纷繁复杂、多种多样的 信息。那么，如何有效检索这些海量数据获取用户感兴趣的信息成为当前重要 的研究课题。信息检索正是解决上述问题的关键技术。众多的网络搜索引擎如 g o o g l e ，百度等，应用信息检索技术，帮助人们快速访问网络信息。 w e b 信息检索是指从大量网页集合中找出与用户给定查询相关的网页子集， 是处理海量文本的重要手段。w e b 信息检索，基本的过程包括：爬取互联嘲中 的网页、对网页进行索引、根据用户请求返回相关的文档。由于信息量巨大， w e b 页面繁多，检索系统检索出的相关文档数量相当的多，为便于用户尽快地 获得最相关的文档，大多数检索系统都把检索结果以其与用户提交的查询的相 关程度来进行排序后返回给用户。因此，如何准确、高效地为检索出的文档进 行排序己成为信息检索研究的核心问题之一。 搜索引擎中检索系统的网页排序主要任务是将和用户输入的查询最相关的 网页以最高优先级展现给用户，为了完成这个任务，研究人员提出了各种检索 系统排序模型。这包括，布尔模型、向量空间模型、概率检索模型和统计语言 模型。当然，还有最近几年提出的基于监督学习方法的各种排序学习模型。监 督模型方法，使用的特征数据基本都来自非监督方法，其中也包括了大量来自 语言模型方法提供的特征。 而语言模型本身基于完善的统计学理论基础之上，模型参数可以使用统计 学习的方法进行估计，这使得语言模型参数估计很便捷。同时，以往的研究显 示，语言模型在实验上能够带来高于其他的非监督模型算法的性能。同时语 言模型的结构使其能够很好的适用于各种复杂的检索问题。所以，本文着眼于 基于语言模型的非监督方法的网页排序问题研究。 第一章绪论 1 2 研究现状 本文的工作基于信息检索领域和统计语言模型领域已有的很多关于信息检 索，统计语言模型的相关研究成果。在本节中，将对这些相关的研究成果做简 单介绍。 1 2 1 信息检索中的排序模型 自从信息检索模型被提出以来，排序问题就一直是信息检索中的核心问题 之一。为了解决排序问题，研究人员提出了各种模型。按照模型提出的时间顺 序，包括布尔逻辑模型【2 2 】【2 3 】、向量空间模型【9 1 【2 9 1 、概率检索模型【1 0 j 【3 i 】、统计语 言模型【1 】以及基于监督学习方法的排序学习模型。 布尔模型将一个文档组织成以关键词或者主题词为标识的倒排文本。倒排 文本以倒排索引的形式呈现，索引的键值就是关键词，索引的对象值是唯一标 示文档的i d 。以倒排索引为基础，布尔模型在处理用户查询的时候，对于查询 中的每个单词，使用倒排索引查找相应的单词，然后将结果进行逻辑操作，得 到最后的返回列表。布尔模型是一种相当原始的检索方法，返回文档的排序手 段也很单一。 向量空间模型是目前广泛应用于各个工业信息检索系统中的一个模型。其 基本思路是：在信息检索中，文档或者查询的基本其所包含的词( 检索单元) 来表述的，可以定义由检索单元组成的向量来描述每一篇文档和每一条检索， 再通过计算文档与查询之间的相关程度来判断文档与查询是否相关，与某一特 定的查询的相关程度越高的文档被认为是与该查询越相关的文档。对于向量空 间检索模型，需要定义向量来描述文档和检索的含义。通常的做法是，以所有 包含在文档和查询中的检索单元为检索空间，将文档和查询以向量的形式表示 出来。 概率检索模型( p r o b a b i l i s t i cr e t r i e v a lm o d e l ) 是另一种普遍使用的信息检索 模型，它应用文档与查询相关的概率来计算文档与查询的相似度。通常利用 检索单元作为线索，通过统计得到每个检索单元在相关的文档集( 对应于某查 询) 中出现和不出现的概率以及其在与该查询不相关的文档集中出现和不出现 的概率，最终，利用这些概率值，计算文档与查询的相似度。这类模型的典型 代表就是b m 2 5 算法。 2 第章绪论 1 2 2 语言模型 语言模型最初出现在语音识别和机器翻译领域，通过统计大规模数据集中 语音和单词出现的条件概率，来建立一个模型，用于预测在给定语音模式下， 下一个语音单词。 在1 9 9 8 年，由p o n t e 和c r 0 1 f t i l 】首次将语言模型方法引入到信息检索领域。 由于语言模型本身在语音识别和机器翻译相关领域已经有多年的发展经验，在 其被引入到信息检索领域之后，迅速掀起了一波利用语言模型处理信息检索问 题的热潮。语言模型用于信息检索，主要关注三个问题：查询模型、文档模型 以及如何建立这两个模型之间关系作为排序值的方法。由这三点出发，研究人 员提出了许多不同的语言模型来处理信息检索中的排序问题。随着研究不断的 深入，使用语言模型来处理信息检索问题获得了越来越好的性能，也受到了更 多学者的青睐。近些年，用语言模型处理信息检索问题，变的越来越成熟。 其中，在平滑方法上，信息检索中的语言模型借鉴了大部分来自语音识别 中的平滑方法。其中，s t a n l e y 和j o s h u a 在其论文【2 7 l 中论述了大部分来自语音识 别领域的平滑方法及其实验中的性能表现。z h a i t 4 1 在其工作中详细阐述了广泛应 用于信息检索的语言模型中的3 种简单平滑方法并提出了一种综合了简单平 滑方法的两阶段平滑算法。 在模型构建方面，最初的语言模型1 1 将p ( dig ) 作为文档排序的主要手段。 然而，这种方式对于语言模型本身的反馈机制兼容性不是很好。z h a i 在其论文j 中提出了一种基于b a y e s 风险最小化的统一模型。该模型将以往的多种语言模型 方法都视为其在一定假设条件下形成的特例。同时，提出了一种新的基于模型 距离进行文档排序的方案。该方案下，文档反馈机制自然融入到语言模型之中， 对模型的性能带来了很大的提升。 1 3 本文主要研究内容 本文针对经典语言模型中，对查询模型多个单词元组间关系考虑不足、平 滑算法中对数据层次考虑不足、对文档先验信息利用不足这三个问题，开展研 究。从真实的互联网数据出发，揭示经典方法中可以改进的地方。同时，在理 论上提出基于多元组的文档查询相似度算法、基于互联网多层次特性的平滑算 法。同时，本文还探讨了以上两种算法的实现方式和效率问题。之后，本文在 3 第一章绪论 新提出的两种算法基础之上，利用互联网结构特性引入的多种文档相关先验概 率，尝试用朴素b a y e s 方法融合多种先验概率，利用改进后的语言模型进行了网 页排序实验，验证了模型的性能。 1 3 1 基于多元组的文档一查询相似度算法研究 传统查询模型，将查询中所有单词等概率对待，而本文则认为查询单词并 不是等概率的，同时是相互关联的。通过重新建立不等概率的查询模型来更好 的理解用户查询，以提升检索性能。 在计算方式上，一元组算法是统计语言模型的基本算法，传统算法中，将 元组独立考虑，分别统计，然后进行综合。而基于多元组的文档查询相似度算 法，在传统算法的基础上对元组之间的关系加以考虑，将连续元组的权重适当 提高，从而获得更准确的文档模型估计。 将多重元组纳入考虑，随之带来的就是计算上的巨大负担。传统语言模型 在线计算文档模型的时候，能够利用倒排索引非常快速的获得结果。但是，考 虑多元组之后，速度必然会有很大下降。本文在提出算法之后，还对算法的高 效实现提出了相应的解答方法。 为了验证本文提出的算法，本文在l e m u d l 6 】的基础上，实现了相应的算法， 并且在t r e cw e b 数据集之上进行了实验。分别使用t r e c 的3 个任务来对比 经典语言模型。对结果进行了研究和分析。 1 3 2 基于互联网多层次特性的平滑算法研究 未见词的平滑是维持语言模型性能稳定的关键之处，以往的平滑算法，将 平滑分为两个层次进行，即当前文档和整个数据集。当前文档中的未见词，使 用整个实验数据集进行平滑。这样的状况下，带来的副作用是，对于未见词较 多的查询，其排序性能有所下降。 鉴于互联网是由人为组织起来的网络，其中任何一个页面它所在的目录和 网站都有其人为分类的因素在起作用。本文利用这一特点，引入页面所在的目 录和站点本身的词汇信息来进行为见词平滑。 本文在提出算法之后，同时设计了如何存储这一平滑算法所需要的多层数 据的结构，并且进行了大规模真实网络数据实验。实验显示该算法本身具有 很好的平滑性能。 4 第一章绪论 1 3 3 基于朴素贝叶斯的文档先验概率估计 除了对于传统的语言模型研究热点文档查询相似度p ( qi 力的改进，本文对 于文档先验概率p ( d ) 的估计也进行了研究。文档先验概率的估计，与用户查询 无关，本文将考虑多种可能影响排序的先验知识信息。并尝试利用n a i v eb a y e s 方法，结合多种不同的结构特征对p ( d ) 进行估计。 1 4 本文组织结构 本文共分为五章，各章节内容和结构安排如下：第一章是绪论，概括介绍 本文的研究背景、研究内容和研究目标。第二章综述相关工作，介绍信息检索， 排序模型和统计语言模型。对信息检索，排序模型、统计语言模型现有算法进 行综述，作为后续章节工作的基础。第三章详细介绍文档- 查询相似度算法和平 滑算法，并在此基础上引入了基于多元组的文档查询相似度算法和基于互联网 多层次特性的平滑算法。描述了基于多元组的文档查询相似度算法和基于互联 网多层次特性的平滑算法以及如何高效实现这两种算法。第四章基于第三章提 出的新的算法，对经典语言模型没有加以利用的文档结构信息加以整合利用， 尝试使用朴素贝叶斯方法融合几种主要的先验知识到语言模型之中，形成基于 互联网特性改进的语言模型，并对模型的性能进行了分析。在第五章，对本文 的工作进行了总结与展望，总结本文工作，并展望下一步的研究工作。 5 第二章相关工作综述 第二章相关工作综述 本文的研究得益于统计学习领域和信息检索领域的相关研究成果，本章详 细介绍与本文相关的研究工作和成果，包括信息检索模型、统计语言模型，作 为后续章节研究工作的基础。 2 1 信息检索 信息检索是指从大量非结构化、半结构化的文档集合中找出与用户给定查 询最相关的文档集合，是处理大规模海量文本的重要方法。目前，随着互联网 的普及，网页这种非结构化文档的检索问题，已经成为信息检索研究最典型的 应用领域。 一个文档检索的基本过程基本包括如下三个步骤：第一，用户可以将自己 的查询输入到检索系统中；随后，检索系统对用户的查询进行分析，通过适当 的算法，在已经建立了的索引文档集中进行检索，获得与用户查询最相关的文 档子集；最后，检索系统为用户提供与其查询相关的文档集。通常，检索系统 将所提供的相关文档集按照与用户查询的相关程度进行排序，最相关的文档排 在最前面。 按照对文档排序方式和计算文档相关程度的方式的不同，信息检索方法可 以分为以下五类经典模型：布尔逻辑模型、向量空间模型、概率统计模型、统 计语言模型、基于有监督学习的检索模型等，以下将分别介绍这些检索模型。 2 1 1 布尔逻辑模型 布尔逻辑模型删2 3 1 ( b o o l e a nm o d e l ) 建立在集合论和布尔代数基础之上， 是一种比较简单的检索模型。在经典布尔逻辑模型中，文档被表示成单词的集 合。每个单词在每篇文档中只有两个值0 和l ，其中0 表示该单词未出现在该 文档中；“l ”表示该单词在该文档中出现。 在布尔逻辑模型中，用户查询使用布尔表达式的形式来进行描述，支持逻 辑与( a n d ) 、或( o r ) 和非( n o t ) 操作。文档集中满足该布尔表达式逻辑 关系的文档才被认为是相关的，否则检索系统认为该文档为不相关的文档。 经典布尔逻辑模型存在着一些缺陷，主要包括：检索系统不能提供相关度 6 第二章相关，t 作综述 的排名；没有提供单词的权重信息，检索系统无法区分文档中不同的单词对相 关性的贡献；对于相关性的二值判定过于严格等。 为解决布尔逻辑模型的诸多问题，研究者们提出了扩展布尔模型( e x t e n d e d b o o l e a nm o d e l ) 。在该模型中，文档和查询的相关度不再是简单的相关于不相关 的却别，而变成了区间【0 ，l 】中的一个实数，这给文档按照相关度排序提供了可能 性。 2 1 2 向量空间模型 向量空间模型9 1 啪1 ( v e c t o rs p a c em o d e l ) 是信息检索工业中广泛使用的一种 检索模型。按照向量空间模型的定义，文档或者查询的基本含义都是通过其所 包含的单词( 检索单元) 来表述的。每一个用户查询和文档都是通过由检索单 元组成的向量来描述的，之后利用向量之间的相关性指标来计算文档与查询之 间的相关程度，从而判断文档与查询是否相关与相关程度。与某一特定的查询 的相关程度越高者被认为是与该查询越相关的文档。对于向量空间检索模型， 需要定义向量来描述文档和检索的含义。通常的做法是，以所有包含在文档和 查询中的检索单元为检索空间，将文档和查询以向量的形式表示出来。 向量空间检索模型通常使用基于文档集合的统计频率的权值，也被称为 t f i d f 权值。 i f i d f 权值由两部分组成，一部分为检索单元在文档中出现的频 率( t e r mf r e q u e n c y , t f ) ，另一部分为文档频率的反转( i n v e r s ed o c u m e n tf r e q u e n c y , i d f ) ，通常，对于一个给定的检索单元t f i d f 权值是t f 与i d f 的乘积。 假设检索系统中各个因素定义如下： 破文档集合中文档的总个数。 册：整个检索空间q 的大小。 a f ：在整个文档集合中，包含检索单元t j 的文档的个数( 妒。 呖：检索单元哆在文档西中出现的次数( 驴。 则文档频率的反转定义如公式( 2 1 ) 。 ，o 、 ，炉1 0 芳i q j ) 对于某一个给定的文档，用m 个元素组成描述当前文档的向量，该向量分 别对应着文档中出现的m 个检索单元。每一个元素的权值根据其所对应的检索 7 第二章相关工作综述 单元在文档中出现的频率以及该检索单元在整个文档集中出现的频率两项因素 共同决定，其计算方法如公式( 2 2 ) 。 w j = t , j f ( 2 2 ) 使用公式( 2 2 ) 中的劬，作为向量中各元素的权值，对前面所述的向量进行进 一步调整，最终得到一个能够更精确地描述文档和查询内容的向量。对于向量 空问模型，不仅需要确定如何定义向量来描述文档和查询的含义，还需要选择 某种向量相似度计算方法来计算文档与查询的相关程度，并且进行相关性排序。 在数学上，任何一种能够判断出描述文档与查询的各个向量方向的接近程 度的各种计算方法都可以用来作为文档与查询相关程度的判断依据。故，我们 可以考虑利用向量夹角的余弦值作为文档与查询相关程度的计算方法。如前所 述，在检索空间q 中，定义文档d 和查询q 的相似度( s i m i l a r i t y c o e f f i c i e n t ，s c ) 如公式( 2 3 ) 。 s c ( q ，d ) = 肘 屹 j i i ( 2 3 ) 其中，和是对该文档对应当前查询词的0 - 1 的描述。当检索单元出 现在文档d 中时，嘞。，为l ，否则为0 ；当检索单元l 出现在查询q 中时，为 l ，否则为0 。和都采用t f i d f 权值。 2 1 3 概率检索模型 概率检索模型n 州3 1 3 ( p r o b a b i l i s t i cr e t r i e v a lm o d e l ) 也是一种非常普遍使用的 信息检索算法，该模型通过使用某种方法来计算查询与文档相关的概率来进行 相关性排序。具体来讲，利用检索单元作为线索，通过统计得到每个检索单元 在相关的文档集( 对应于某查询) 中出现和不出现的概率以及其在与该查询不 相关的文档集中出现和不出现的概率，最终，利用这些概率值，计算文档与查 询的相似度。 b m 2 5 算法是概率检索模型的经典算法，由r o b e r s t o n o l1 9 9 4 年在t r e c 3 上提出。该算法中，对查询q 中的每一个检索单元q ，一共有三个权值u ，y ，形 与之相关，如公式( 2 4 ) 。 8 第二苹相关丁作综述 u ：掣 ( 2 4 ) 岛+ 缈 其中，屯是由用户指定的参数，沙是检索单元鸱在q 中出现的频率q t f 。 矿= 踹1 - b b ( 2 5 ) 七( +d 髟 其中，k 和b 是用户指定的参数，是检索单元q 在d 中出现的频率ml 是正则化之后的文档长度，是将原始文档长度除以文档集合中平均的文档长度 之后得到的结果。 w - - l o 揣颤警嵩) ( 2 6 ， 其中，n 表示文档集合中文档的总数；r 表示与查询q 相关的文档总数；n 表示含有检索单：g c o , 的文档总数；r 表示与q 相关的文档中，含有检索单元q 的 文档数。 在b m 2 5 公式中，查询q 和文档d 的相关程度分值可以表示为公式( 2 7 ) 。 s qg 孕u f ( 2 7 ) 在该算法的基础之上，r o b e r t s o n 3 l 】等提出了一种简单的基于b m 2 5 的改进， 改进算法能够同时计算具有多个域的文档和查询的相似度，克服了b m 2 5 在这 方面的不足。 2 1 4 统计语言模型 统计语言模型( l a n g u a g em o d e l ) 近些年来在信息检索领域取得了令人瞩目 的效果。p o n t e 和c r o f t l l 】在s l g i r1 9 9 8 会议上发表了一篇名为al a n g u a g e m o d e l i n ga p p r o a c ht oi n f o r m a t i o nr e t r i e v a l ”的论文，将统计语言模型引入到信息 检索领域，由此开创了一个新的研究课题：统计语言模型在信息检索中的应用。 在那之后，很多研究人员不断加入到该课题的研究工作中来，取得了丰硕的研 究成果。许多实验结果显示，基于统计语言模型的方法在检索性能上普遍优于 以前采用的向量空间模型方法。 在该模型中，给定某个查询q ，检索出的文档d 按照后验概率p ( d i q ) 来 排序，将文档视为由用户查询产生的模型。根据贝叶斯公式可( 2 8 ) 。 第二章相关t 作综述 尸( d iq 弦尸( z ) ) p ( q i( 2 8 ) 利用语言模型进行信息检索的基本过程如下，对每一篇文档均建立一个模 型，计算每一个模型产生某主题( 查询) 的概率值( 相当于其他模型中文档- 查 询相似度) ，之后，计算该文档的静态相关概率尸( d ) ，最后对这些概率值进行 排序，返回排序