（计算机应用技术专业论文）排序学习中基于直接优化信息检索评价准则算法的理论分析.pdf

l i i i ii ii ii i i i iiiii1 1 1 1iil y 18 16 8 2 8 u n i v e r s i t yo fs c i e n c ea n dt e c h n o l o g yo fc h i n a ad i s s e r t a t i o nf o rp h d sd e g r e e t h e o r e t i c a la n a l y s i so nd ir e c t o p t i m i z a t i o no fi n f o r m a t i o n r e t r i e v a lm e a s ur e sinl e a r nin gt o r ank a u t h o r sn a m e ：y i nh e s p e c i a l i t y ：c o m p u t e ra p p l i c a t i o n st e c h n o l o g y s u !：hiys h u m 5 u p e r v s o r a l t vs h u m ： f i n i s h e dt i m e ： a p r i l3 0 t h ，2 0 10 中国科学技术大学学位论文原创性声明 本人声明所星交的学位论文，是本人在导师指导下进行研宄工作所取得的成果 除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过的研 究成果与我一同工作的同志对本研究所做的贡献均己在论文中作了明确的说明 一八 作者签名：么当i 鸳 签字日期： 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥有 学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文 的复印件和电子版，允许论文被查阅和借阅可以将学位论文编入中国学位论文 全文数据库 等有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文本人提交的电子文档的内容和纸质论文的内容相一致 保密的学位论文在解密后也遵守此规定 o 么开 作者签名； 签字日期： 导师签名： 旷巳向 吁 年 一 力一 芷一 骼4 迎 一4 一 摘要 摘要 随着互联网技术的迅速发展，互联网上的信息量也以惊人的速度不断地膨 胀，从海量的互联网信息中准确快捷的获取所需信息也变得日益困难。搜索引 擎的出现正是为了使人们能够从海量的互联网信息中快速和便捷地获取所需信 息。搜索引擎背后的关键技术是网页排序算法。如何设计一个有效的网页排序 算法是信息检索领域中十分重要和流行的课题。近年来，将机器学习方法引入 排序学习获得了很大成功，吸引了越来越多研究人员的注意。 在排序学习领域中，直接优化信息检索评价准则算法已经成为一个重要分 支。由于信息检索评价准则( 例如m a p 和n d c g ) 的不连续和不可导性导致其 难以优化。直接优化信息检索评价准则算法的核心思想是通过优化一个与信息 检索评价准则近似的替代函数达到优化信息检索评价准则的目的。我们称此替 代函数为替代评价准则。 直接优化信息检索评价准则算法的一个关键性基础问题是一对替代评价准 则的优化是否能保证对相应的信息检索评价准则的优化? 这个问题的解答，将 直接决定直接优化信息检索评价准则算法的理论正确性。因为。如果对替代评 价准则的优化不能保证对相应的信息检索评价准则的优化，那么直接优化信息 检索评价准则算法将无法从理论上保证能够获得一个性能良好的排序模型。然 而目前并无任何工作对这个问题有深入的理论研究，故而研究人员对直接优化 信息检索评价准则的理论性质并不了解。 本论文以直接优化信息检索评价准则算法的一个关键性基础问题( 对替代 评价准则的优化是否能保证对相应的信息检索评价准则的优化) 为主线，以探 索直接优化信息检索评价准则算法的理论性质为目标，创新性的提出了直接性 和趋势相关性两个概念，用于以衡量替代评价准则与相应的信息检索评价准 则之间的关系。并以直接性和趋势相关性为分析工具，获得了主流的直接优化 信息检索评价准则算法中替代评价准则的理论性质。最后通过在公共基准数据 集l e t o r 上对各个直接优化信息检索评价准则算法的实验验证了本文所得的理 论分析结果，说明了用直接性和趋势相关性来衡量替代评价准则与相应的信息 检索评价准则之间关系的科学性和正确性。 本论文首先提出直接性和趋势相关性两个概念以衡量替代评价准则与相应 的信息检索评价准则的关系。我们从理论上证明了，如果一个替代评价准 则，相对于一个信息检索评价准则而言，具有任意大的直接性，或者任意 强的趋势相关性，则对此替代评价准则的优化能保证对相应的信息检索评 i 摘要 价准则的优化。 在理论研究结论的基础上，我们分析了主流的直接优化信息检索评价准 则算法的直接性和趋势相关性。通过理论分析，证明 s o f t r a n k d c g ， a p p r o x r a n k m a p ，a p p r o x r a n k n d g g 中所优化的替代评价准则，在合适的 参数设置下( 例如，令s o f t r a n k n d c g 中参数o s _ 0 以及a p p r o x r a n k m a p 和a p p r o x r a n k j v d c g 中参数aoo o ) ，对任意数据分布都能具有任意 大的直接性和任意强的趋势相关性。证明y s v m m a 户，d o r m 伙船， p e r m u r a n k m a p ，s v m d c g 所优化的替代评价准则在某类数据分布上 不能具有任意大的直接性和任意强的趋势相关性。因此，我们得到 了s o f t r a n k n d c c ， a p p r o x r a n k 7 a p ，a p p r o x r a n k d e g 相比于s v m m a p ， d o r m n d c g ，p e r m u r a n k m 月尸，s v m 册g 具备更好的理论性质，因而能 获得更好的排序性能的结论。 最后通过在公共基准数据集l e t o r 上的实验研究，我们验证了对主流直接 优化信息检索评价准则算法所优化的替代评价准则的直接性和趋势相关性 的理论研究结果，说明了用直接性和趋势相关性衡量替代评价准则与相应 的信息检索评价准则直接关系的科学性和正确性。 关键词：信息检索，排序学习，直接优化，直接性，趋势相关性 a b s t r a c t a sw o r l dw i d ew e bg r o w sr a p i d l y , i th a sb e c o m et h eb i g g e s ts o u r c eo fi n f o r m a - t i o nf o rp e o p l e a sar e s u l t ，i ta l s ob e c o m e sm o r ea n dm o r ed i f f i c u l tf o rp e o p l et og e t w h a tt h e yw a n tf r o mt h eh u g ev o l u m eo fi n f o r m a t i o ni nw o r l dw i d ew e b n o t i c i n g t h i s ，s e a r c he n g i n e sh a v eb e e np r o p o s e dt op r o v i d ep e o p l ea c o n v e n i e n tw a yt or e t r i e v e t h ew a n t e di n f o r m a t i o nf r o mw o r l dw i d ew e b t h ek e yf a c t o ro ft h es e a r c he n g i n e s i sar a n k i n gm o d e lt h a tr e t u r n sar a n k e dd o c u m e n tl i s tt ot h ep e o p l eb a s e do nas u b m i t t e dq u e r y h o wt od e s i g nag o o dr a n k i n gm o d e li sav e r yi m p o r t a n ta n dp o p u l a r t o p i ci nt h ea r e ao fi n f o r m a t i o nr e t r i e v a l ( i r ) r e c e n t l y , l e a r n i n gt or a n k ，w h i c ha p p l i e s m a c h i n el e a m i n gt e c h n i q u e st oi r ，h a sa t t r a c t e dm o r ea n dm o l ea t t e n t i o n sb e c a u s eo f i t ss u c c e s s f u l n e s s d i r e c to p t i m i z a t i o no fi re v a l u a t i o nm e a s u r e sh a sb e c o m ea ni m p o r t a n tb r a n c h o fl e a r n i n gt or a n kf o ri r s i n c ei re v a l u a t i o nm e a s u r e sa r ed i f f i c u l tt oo p t i m i z ed u e t ot h e i rn o n c o n t i n u i t ya n dn o n d i f f e r e n t i a b i l i t y , m o s td i r e c to p t i m i z a t i o nm e t h o d s 叩 t i m i z es o m es u r r o g a t ef u n c t i o n si n s t e a d ，w h i c hw ec a l ls u r r o g a t em e a s u r e s a c r i t i c a l i s s u er e g a r d i n gt h e s em e t h o d si sw h e t h e rt h eo p t i m i z a t i o no ft h es u r r o g a t em e a s u r e s c a nr e a l l yl e a dt ot h eo p t i m i z a t i o no ft h eo r i g i n a li re v a l u a t i o nm e a s u r e s a sf a ra sw e k n o w t h e r en or e l a t e dw o r kt h a th a v et r i e dt oa n s w e rt h i sc r i t i c a li s s u e t h e r e f o r e ，t h e t h e o r e t i c a lp r o p e r t i e so ft h ed i r e c to p t i m i z a t i o nm e t h o d sa r es t i l lu n c l e a rt ot h ep e o p l e i nt h i st h e s i s ，w ep e r f o r mf o r m a la n a l y s i so nt h i si s s u e w ef i r s tp r o p o s et w o c o n c e p t sn a m e d “d i r e c t n e s s a n d “t e n d e n c yc o r r e l a t i o n t od e s c r i b et h er e l a t i o n s h i p b e t w e e nas u r r o g a t em e a s u r ea n di t sc o r r e s p o n d i n gi re v a l u a t i o nm e a s u r e b a s e do n t h e s et w oc o n c e p t s ，w et h e na n a l y z et h es u r r o g a t em e a s u r e so p t i m i z e di na n u m b e ro f p o p u l a rd i r e c to p t i m i z a t i o nm e t h o d s o u rt h e o r e t i c a lf i n d i n g sc a ne x p l a i nt h ee x p e r t 。 m e n t a lr e s u l t so b s e r v e do np u b l i cb e n c h m a r kd a t a s e t s w ef i r s tp r o p o s et w oc o n c e p t sn a m e d “d i r e c t n e s s ”a n d “t e n d e n c yc o r r e l a t i o n ”t o d e s c r i b et h er e l a t i o n s h i pb e t w e e nas u r r o g a t em e a s u r ea n di t sc o r r e s p o n d i n gi r e v a l u a t i o nm e a s u r e w es h o wt h a tw h e nas u r r o g a t e m e a s u r eh a sa r b i t r a r i l yl a r g e d i r e c t n e s so ra r b i t r a r i l ys t r o n gt e n d e n c yc o r r e l a t i o nt oa ni re v a l u a t i o nm e a s u r e ， t h eo p t i m i z a t i o no fi tw i l ll e a dt ot h ee f f e c t i v eo p t i m i z a t i o no ft h eo r i g i n a li r e v a l u a t i o nm e a s u r e i i i 兰生羔墨! 里 w r et h e na n a l y z eb o t ht h ed i r e c t n e s sa n d t h et e n d e n c yc o r r e l a t i o no ft h es u r r o g a t e m e a s u r e so p t i m i z e di nan u m b e ro fd i r e c to p t i m i z a t i o nm e t h o d s w ep r o v et h a t t h es u r r o g a t em e a s u r e si ns o f t r a n k n d c g 。a p p r o x r a n k ma p a n da p p r o x r a n k n o c a c a nh a v ea r b i t r a r i l yl a r g ed i r e c t n e s sa n da r b i t r a r i l ys t r o n gt e n d e n c yc o r r e l a t i o n w i t ht h eo r i g i n a li re v a l u a t i o nm e a s u r e s ，r e g a r d l e s so ft h ed a t ad i s t r i b u t i o n ， w h e n s o m ep a r a m e t e r sa r ea p p r o p r i a t e l ys e t h o w e v e r , t h es u r r o g a t e m e a s u r e si n s v m f a p ，d o r m d c g ，p e m u r a n k m p ，a n ds v m n d c gc a n n o th a v ea r b i t r a r - i l yl a r g ed i r e c t n e s sa n da r b i t r a r i l ys t r o n gt e n d e n c yc o r r e l a t i o nw i t ht h e o r i g i n a li r e v a l u a t i o nm e a s u r e so nc e r t a i nd i s t r i b u t i o n so fd a t a t h e r e f o r es o f t r a n k d c g a p p r o x r a n k m 肚，a n da p p r o x r a n k d c ga r et h e o r e t i c a l l ys o u n d e rt h a ns v m m a p ， d o r m d c g ，p e r m u r a n k ，a p ，a n ds v m j d g g ，a n da lee x p e c t e dt or s u l ci n b e t t e rr a n k i n gp e r f o r m a n c e s w ep e r f o r me x p e r i m e n t so np u b l i cb e n c h m a r kd a t a s e t sa n dv a l i d a t eo u rt h e o r e t i c a la n a l y s i so nt h ep o p u l a rd i r e c to p t i m i z a t i o nm e t h o d s t h i si n d i c a t e st h e c o r r e c t n e s st ou s e “d i r e c t n e s s a n d “t e n d e n c yc o r r e l a t i o n ”t od e s c r i b et h er e l a t i o n s h i pb e t w e e nas u r r o g a t em e a s u r ea n di t sc o r r e s p o n d i n gi re v a l u a t i o nm e a s u r e k e y w o r d s ：i n f o r m a t i o nr e t r i e v a l ，l e a r n i n gt or a n k ，d i r e c to p t i m i z a t i o n ，d i r e c t n e s s ， t e n d e n c yc o r r e l a t i o n i v 目录 目录 摘要i a b s t r a c t i i i 目录v 第1 章绪论1 1 1 引言1 1 2 本文的研究背景l 1 2 1 信息检索1 1 2 2 排序学习2 1 2 3 基于直接优化信息检索评价准则的排序学习算法2 1 3 本文的动机及研究内容3 1 4 本文的创新和贡献3 1 5 本文的章节安排4 第2 章相关工作7 2 1 引言7 2 2 信息检索排序学习的算法框架7 2 3 主流信息检索排序学习算法介绍9 2 3 1基于单文档的排序学习算法 9 2 3 2 基于文档对的排序学习算法1 0 2 3 3 基于文档列的排序学习算法1 2 2 3 4 主流排序学习算法小结1 4 2 4 主流信息检索评价准则介绍1 5 2 4 。l查准率( p r e c i s i o n ) 和查全率( r e c a l l ) 1 5 2 4 2 平均查准率的均值( m a p ) 1 5 2 4 3n d c g ( n o r m a l i z e dd i s c o u n t e dc u m u l a t i v eg a i n ) 16 2 5 本章小结1 6 第3 章直接优化信息检索评价准则的排序学习算法1 9 3 1 引言1 9 3 2 主流直接优化信息检索评价准则排序学习算法简介1 9 3 2 1s v m m 尸2 0 3 2 2d o r m d 2 i v 目录 3 2 3p e r m u r a n k m a p 2 1 3 2 4s o f t r a n k n d c c 2 2 3 2 5s v m n d 6 g 2 3 3 2 6 a p p r o x r a n k m a 尸和a p p r o x r a n k d c g 2 3 3 3 本章小结2 4 第4 章直接性2 5 4 1 引言2 5 4 2 直接性2 5 4 2 1 直接性定义2 5 4 2 2 直接性的理论性质2 6 4 3s o f t r a n k n d c g 和s v m n d c g 的直接性分析2 8 4 3 1s o f t r a n k d c g 2 9 4 3 2s v m n d c g 3 3 4 3 3 总结及讨论3 5 4 4 实验结果3 6 4 4 1 数据集3 6 4 4 2s o f t r a n k n d c g 和s v m m a p 的直接性3 8 4 4 3直接性和优化复杂度的折中3 8 4 4 4 直接性和排序性能的关系4 0 4 5 本章小结4 3 第5 章趋势相关性4 5 5 1 引言4 5 5 2 趋势相关性4 5 5 2 1趋势相关性的定义4 5 5 2 2 趋势相关性的理论性质4 7 5 3 主流直接优化信息检索评价准则算法的趋势相关性分析4 9 5 3 1s o f t r a n k n o c c 4 9 5 3 2 a p p r o x r a n k 。 p ；j f t l a p p r o x r a n k d c g 5l 5 3 3s v m m a p ，d o r m d c g ，p e r m u r a n k m a p ，s v m n d 5 2 5 3 4 总结及讨论5 8 5 4 实验结果5 9 5 4 1 数据集5 9 5 4 2 直接优化信息检索评价准则算法的趋势相关性5 9 v l 目录 5 4 3 趋势相关性和优化复杂度的折中 5 4 4 趋势相关性和排序性能的关系 5 4 5 总结 5 5 本章小结 第6 章总结和展望 6 1 总结 6 2 展望 参考文献 致谢 在读期间发表的学术论文与取得的研究成果 v i i o 3 5 6 l l 2 3 9 1 贷酌刀 死记乃侈趴 表格 表格 2 1 主流排序学习算法小结1 4 3 1 主流直接优化信息检索评价准则算法中的替代评价准则2 4 4 1测试集上的排序性能4 2 5 1 主流直接优化信息检索评价准则算法的趋势相关性 5 2 不同算法在o h s u m e d ，t d 2 0 0 3 ，t d 2 0 0 4 上e 的值 5 3 以m a p 衡量的训练性能 5 4 以n d c g 5 衡量的训练性能 5 5 以n d c g 1 0 衡量的训练性能 5 6 以m a p 衡量的测试性能 5 7以n d c g 5 衡量的测试性能 5 8 以n d c g 1 0 衡量的测试性能 i x 9 4 5 6 7 8 9 5 6 6 6 6 6 6 6 插图 插图 4 1 人造数据集的数据分布图 4 2 s o f l r a n k d c g 的i m 一府i 柱状图 3 7 3 9 4 3 s v m d c g 的f m 一嘲i 柱状图4 0 4 4 随机初始对嘲的影响4 l 4 5 o h s u m e d 数据集上s o f t r a n k d e g 的排序性能4 2 5 1 趋势相关性示例4 6 5 2 a p p r o x r a n k m p 在o h s u m e d 和t d 2 0 0 3 上的训练性能6 2 第1 章绪论 第1 章绪论 1 1 引言 信息检索( i n f o r m a t i o nr e t r i e v a l ，i r ) 研究如何表达、存储、组织和访问信 息【i 2 】。近年来，随着社会信息化程度的快速提高，互联网日益普及。信息的总 量以惊人的速度不断地膨胀，迫切需要更有效的理论和方法来处理如此海量的 信息。信息检索适应了这一要求并成为当前信息处理领域中的研究热点。 检索模型，即排序算法，是信息检索中一个重要组成部分。在检索模型的 发展历史中，布尔模型、向量空间模型、概率模型、统计语言模型、基于链接 结构的检索算法等先后被提出。近年来，基于机器学习的检索算法由于其良好 的应用效果，受到越来越多的重视，已经成为检索模型领域中的一个新的热 点。 本文研究排序学习中的一个重要分支，即直接优化信息检索评价准则 ( d i r e c to p t i m i z a t i o no f i n f o r m a t i o nr e t r i e v a le v a l u a t i o nm e a s u r e ) 算法。 1 2 本文的研究背景 1 2 1 信息检索 当今社会，信息技术飞速发展，人类所积累的信息成指数增长。随着信息 爆炸时代的到来，如何有效的获取自己所需要的信息已经成为一个迫需解决的 问题。而信息检索技术适应了这一要求并成为当前信息处理领域中的研究热点。 目前，随着信息检索技术的发展和成熟，它逐渐成为人们从海量信息中快速便 捷获取有效信息的最主要手段。 上个世纪9 0 年代以来互联网的飞速发展，搜索引擎的广泛应用，使人们对 信息检索技术的重要性有了一个全新的认识，相应的，学术界和产业界对信息 检索的研究也掀起了一个新的高潮1 3 - 5 。 信息检索模型是影响一个检索系统的性能最关键的一个因素。经过几十年 的发展，一些有效的信息检索模型陆续提出并逐渐应用到实际系统中。其中 影响比较大的检索模型包括：布尔逻辑模型1 6 - 8 1 、向量空间模型1 9 t o 、概率模 型l i t - i t 、语言模型l t 8 - 2 0 、链接分析算法【2 i 2 2 】以及新近提出来的基于机器学习的 检索算法1 2 0 2 3 - 2 6 1 。 l 第1 章绪论 1 2 2 排序学习 近年来，机器学习技术被逐渐应用到信息检索领域，取得了良好的效果， 并且成为了当前对信息检索模型研究的热点问题1 2 5 ，弘3 1 1 。将机器学习技术应用 到信息检索中的排序问题被称作信息检索排序学习问题。 传统的二值分类问题的学习算法首先被应用到信息检索中，查询q 和 文档d 组成的二元组被看成两个类别：“相关”( 正例) 与“不相关”( 负例) 。 n a l l a p a t i 3 0 l 于2 0 0 4 年提出了用支持向量机( s u p p o r tv e c t o rm a c h i n e s ，s v m ) 和 最大熵( m a x i m u me n t r o p y ，m e ) 模型来对文档排序；g a o 等1 2 8 1 和b u r g e s 等【2 5 1 也 分别提出利用相关的文档和不相关文档构成的有序对训练排序模型，并且分别 提出了用感知机和神经网络模型进行优化：h e b f i c h 等把排序问题归结成为在有 序对空间上的二值分类问题并且用支持向量机进行优化求解1 3 2 1 ；j o a c h i m s 把这 种基于有序对的学习方法应用到搜索引擎上，利用点击序列( c l i c k t h r o u g h ) 数据 提高搜索引擎的性能1 3 3 】；f r e u n d 等提出用b o o s t i n g 的方法对相关程度不同的两 个文档构成的文档对进行分类 2 6 1 。 1 2 - 3 基于直接优化信息检索评价准则的排序学习算法 排序学习问题一经提出后就受到了广泛关注，各种改进的方法或者模型被 陆续提出。近年来，随着深入研究，排序学习领域的研究人员注意到传统的排 序学习算法中所采用的损失函数，包括基于单个文档的损失函数，基于文档对 的损失函数，和基于文档列的损失函数，与用来评价排序算法优劣的信息检索 评价准则( 例如m a p 和n d c g ) 存在很大差异。进而产生如下疑问，即对传统 损失函数最优化的排序模型能否保证对信息检索评价准则的最优化? 这个问题 将决定各种排序学习算法的理论正确性。因为，如果对这些损失函数的优化不 能保证对信息检索评价准则的优化，那么由此而得到的排序模型将无法从理论 上保证能够获得良好的排序性能。 据目前所知，仅c o s s o c k 等人提出的算法1 3 4 】被证明具有良好的理论性质。该 工作的作者指出其提出的基于单个文档的损失函数最优化的排序模型能保证对 信息检索评价准则的最优化。但是对于其余的传统排序学习算法，并无类似的 理论结论。注意到这个问题，研究人员提出了一类新的排序学习算法分支，即 直接优化信息检索评价准则的排序学习算法。该类算法的核心思想是采用与信 息检索评价准则，如m a p 和n d c g ，高度相似的函数做为损失函数，并通过优 化这样的损失函数得到最终的排序模型。相比于传统的排序学习算法，直接优 化信息检索评价准则的排序学习算法优化的损失函数更接近于信息检索评价准 则，故而直接优化信息检索评价准则的排序学习算法更容易保证对信息检索评 2 第l 章绪论 价准则的最优化。意识到该类算法的此种优点，直接优化信息检索评价准则的 排序算法吸引了越来越多的研究人员的注意，进而成为排序学习算法中的一条 重要分支。 1 3 本文的动机及研究内容 直接优化信息检索评价准则算法的核心思想是采用与信息检索评价准则 ( j t f l m a p 和n d c g ) 高度相关的函数做为损失函数，并通过优化此类损失函数得 到最终的排序模型。相比于传统的排序学习算法，直接优化信息检索评价准则 的排序学习算法优化的损失函数更接近于信息检索评价准则，故而直接优化信 息检索评价准则的排序学习算法更容易保证对信息检索评价准则的最优化。 基于直接优化信息检索评价准则的检索模型的提出是为了保证更容易对信 息检索评价准则的最优化。而事实上，该类算法与传统的排序学习算法一样， 也面临着一个关键性的基础问题，即对其所采用的损失函数的优化是否能保证 对相应的信息检索评价准则的优化? 这个问题的解答，将直接决定直接优化信 息检索评价准则算法的理论正确性。因为，如果对其所采用的损失函数的优化 不能保证对相应的信息检索评价准则的优化，那么直接优化信息检索评价准则 算法将无法从理论上保证能够获得一个性能良好的排序模型。然而目前并无任 何工作对这个问题有深入的理论研究，故而研究人员对直接优化信息检索评价 准则的理论性质并不了解。 另一方面，在实际应用中，研究人员发现，部分基于直接优化信息检索评 价准则的检索模型在特定的数据集上并不能获得良好的排序性能，其性能还不 如某些传统的排序学习检索模型。 基于以上两点原因，本文将以上文提到的直接优化信息检索评价准则算法 的一个关键性基础问题为主线，以探索直接优化信息检索评价准则算法的理论 性质为目标，将对主流的基于直接优化信息检索评价准则的检索模型进行深入 的理论研究，以获得对此类模型理论性质的深刻认识。 1 4 本文的创新和贡献 本文对信息检索排序学习问题中的重要分支，基于直接优化信息检索评价 准则的检索模型，进行了深入的理论研究。本文研究工作的主要创新和贡献在 于： 本论文首次提出直接性和趋势相关性两个概念以衡量替代评价准则与相应 的信息检索评价准则的关系。具体地，通过直接性和趋势相关性，可以刻 3 第l 章 绪论 画替代评价准则与相应的信息检索评价准则的近似程度。 本文从理论上证明了，如果一个替代评价准则，相对于一个信息检索评价 准则而言，具有任意大的直接性，或者任意强的趋势相关性，则对此替代 评价准则的优化能保证对相应的信息检索评价准则的优化。 本文以提出的直接性和趋势相关性为分析工具，对主流的直接优化信息检 索评价准则算法的直接性和趋势相关性进行深入的理论分析和研究。 一证明1 i s o f t r a n k d c g ，a p p r o x r a n k 舯，a p p r o x r a n k d c g 中所优化 的替代评价准，在合适的参数设置下( 例如，令s o f t r a n k d c g 中参 数口sj0 以及a p p r o x r a n k m p7 b a p p r o x r a n k d c g 中参数q - o o ) ， 对任意数据分布都能具有任意大的直接性和任意强的趋势相关性。 一证明了s v m 肘以p ，d o r m n d c g ，p e r m u r a n k m a 尸，s v m d c g 所优化 的替代评价准则在某类数据分布上不能具有任意大的直接性和任意强 的趋势相关性。 因此，我们得到- fs o f t r a n k n d c o ，a p p r o x r a n k 。a p ，a p p r o x r a n k d d g 相 比于s v m m a p ，d o r m d c g ，p e r m u r a n k m a p ，s v m n d c g 具备更好的理 论性质，因而能获得更好的排序性能的结论。 最后通过在公共基准数据集l e t o r 上的实验研究，我们验证了对主流直接 优化信息检索评价准则算法所优化的替代评价准则的直接性和趋势相关性 的理论研究结果，说明了用直接性和趋势相关性衡量替代评价准则与相应 的信息检索评价准则直接关系的科学性和正确性。 1 5 本文的章节安排 本文一共分为6 章，各个章节内容和结构安排如下： 第l 章绪论，概括介绍信息检索中检索模型的研究现状，以及本文的研究背 景、内容和目标。 第2 章综述相关工作，包括主流的排序学习算法以及常用的信息检索评价准 则。 第3 章详细介绍主流的基于直接优化信息检索评价准则算法。 第4 章提出了直接性的概念以描述替代评价准则和对应的信息检索评价准 则的关系。证明了如果一个替代评价准则，相对于一个信息检索评价准则而言。 具有任意大的直接性则对此替代评价准则的优化能保证对对应的信息检索评 价准则的优化。基于该理论结论，我们对主流直接优化信息检索评价准则算法 4 第l 章绪论 所优化替代评价准则的直接性进行理论分析和研究。最后通过在人造数据集和 公共基准数据集l e t o r 上的实验结果，验证了所得的关于替代评价准则直接性 的理论分析结果。 第5 章提出了趋势相关性这个概念以描述替代评价准则和对应的信息检索 评价准则的关系。证明了如果一个替代评价准则，相对于一个信息检索评价准 则而言，具有任意强的趋势相关性，则对此替代评价准则的优化能保证对对应 的信息检索评价准则的优化。我们对主流直接优化信息检索评价准则算法所优 化替代评价准则的趋势相关性进行理论分析和研究。最后通过在公共基准数据 集l e t o r 上的实验结果，验证了所得的关于替代评价准则直接性的理论分析结 果。 第6 章对本文的工作进行了总结，并对进一步的研究进行了展望。 5 第2 章相关工作 第2 章相关工作 2 1引言 本文的研究对象是直接优化信息检索评价准则的算法。这类算法是排序学 习问题的一个重要分支。近年来，随着研究人员对排序学习问题的深入研究， 众多排序学习算法被陆续提出并在实际应用中取得巨大成功。本章将对现有排 序学习问题做详细介绍。 在本章的2 2 节将首先介绍信息检索排序学习的算法框架。然后，在本 章的2 3 节对主流的排序学习算法进行了简单介绍。最后，在本章的2 4 节对 信息检索的评价指标做一个简单的介绍，包括常用的信息检索指标如查 准率( p r e c i s i o n ) 、查全率( r e c a l l ) 、平均查准率的均值( m e a na v e r a g ep r e c i s i o n m a p ) 以及n d c g ( n o r m a l i z e dd i s c o u n t e dc u m u l a t i v eg a i n ) 。 2 2 信息检索排序学习的算法框架 近年来，基于机器学习的信息检索模型逐渐受到研究者们的重视并且在 实际应用中取得了良好的效果，成为信息检索模型研究领域中新的研究热 点 2 4 - 3 0 , 3 2 - 3 3 1 。本节将介绍排序学习的算法框架。 排序学习算法通常包含训练和测试两个步骤。在训练阶段，排序学习算法 通过机器学习方法在训练集合上得到一个排序模型。在测试阶段，使用信息检 索评价准则评价所得排序模型在测试集合上的排序性能。下面我们将分别对训 练阶段和测试阶段做详细介绍。 首先我们介绍训练阶段。在训练阶段，一般会给定查询集合 q = q ( ，q ( m ) 其中每一个查询q ( ) 与一个文档集合 d o = 硝，d 瓣) 以及一个对应于文档的标注集合 = ，嘲) 相关联，其中，b 代表文档集合d 【) 的大小，母表示d ( ) 中第歹个文档，西【o ，l l 】是c 巧。的相关性标注( 一般规定，越大表示与g ( ) 越相关) 。对于每一个查 7 第2 章相关工作 询文档对( g ( 1 ，d 3 ( i ) ) ，可以构造个特征向量 考= ( 口( 们，) 冗n 本文中，在不引起歧义的情况下，我们有时也用考表示文档集合d ( ) 中第j 个文 档，相应的，文档集合也可表示为 x