（计算机应用技术专业论文）信息检索中与查询相关的排序学习问题研究.pdf

摘要 摘要 近年来，互联网已成为全球最大、最广泛使用的信息库，如何有效检索其 中的海量信息成为当前重要的研究课题，因此信息检索技术越来越受到人们的 重视。用户将表示自己需求的查询提交给信息检索系统后，系统将对检索到的 信息根据与查询相关度的大小进行排序。近年来，基于机器学习理论的有监督 排序学习方法的信息检索模型成为了信息检索领域中的研究热点。这种模型使 用排序学习方法在训练数据上学习到一个排序特性，并依此特性作为排序模型， 实现对目标的排序预测。 但是，我们发现使用排序学习方法来解决信息检索中的排序问题时，仍然 存在一些需要解决的问题。大多数排序学习方法要求其数据应满足独立同分布 假设，但在信息检索中，这个假设并不能被很好地满足。在信息检索中，针对 某一个查询，信息检索系统会先从文档库中检索出与这个查询字面上有关联的 文档集合，然后再对其进行排序。所以，信息检索排序问题中需要排序的样本 是由查询与其包含的检索文档共同组成的查询文档对，这种样本的生成是依赖 于查询的，它的特征和其所属的查询之间是相关的，这种相关性导致了不同的 查询所包含样本的分布之间存在差异。但传统的排序学习方法不能很好地应对 这种查询间的差异性问题，从而导致了其在信息检索应用中的局限性。 针对此问题，本文提出一类新的排序学习模型与查询相关的排序学习 模型。在此模型中，我们认为查询之间具有排序差异性，不同查询具有不同的 排序特性。为了对这种差异进行量化，我们提出“查询排序差异度 的概念来 描述不同查询所对应的排序特性之间的差异程度。在此基础上，我们提出与查 询相关的排序学习目标：在模型学习时，针对训练集中查询所对应的不同排序 特性，生成具有不同排序特性的多个排序器模型，并提出集成排序学习方法， 实现使用多个排序器对一个目标查询进行预测；在排序预测时，针对待预测的 查询，以集成排序模型为基础，生成近似于其排序特性的排序模型进行预测。 为了达到这个目标，我们分别从两个方面开展研究，即排序模型学习和排序预 测。 针对传统排序学习方法对查询排序差异表达能力不足的问题，本文提出与 摘要 查询相关的排序模型学习方法，即针对训练集中包含的不同的排序特性，构造 与之对应的多排序器模型，并提出相应的集成排序学习方法。信息检索的训练 集会包含多个查询，而这些查询所对应的排序特性是有差别的。因此，我们对 这些查询在排序特性上的差异进行分析，提出了两种排序差异度的计算方法， 分别是基于分布的查询排序差异度，以及基于决策函数的查询排序差异度。然 后，基于这两种差异度，我们提出了相应的多排序器训练方法，和基于多排序 器的“与查询相关集成排序学习方法 。通过理论和实验表明，基于集成学习 的排序方法可以有效提高模型的泛化性能，同时也为与查询相关的排序预测提 供了基础。 随后，我们进一步提出了与查询相关的排序预测方法，即针对待预测的查 询，生成近似于其排序特性的排序模型进行预测。要想达到这个目的，就必须 对待预测查询的排序特性进行考量，但由于待预测的查询不包含标注数据，所 以很难对它的排序特性进行直接估计，因此我们提出样本特征空间上的“排序 差异尺度学习方法，使用机器学习的方法对查询问排序特性的差异进行差异 度尺度学习。基于排序差异尺度，我们首先使用k 近邻的方法在线学习适合于待 预测查询的排序模型，但这种方法由于时间复杂度比较高，所以不适合一些信 息检索应用的要求。由此，我们又提出了基于动态集成的排序学习方法，它是 以前文提出的与查询相关的集成排序学习方法为基础，通过计算待预测查询与 排序器之间的排序差异尺度，来实现集成权重的动态生成，从而实现了与查询 相关排序学习问题的最终目标。 我们分别使用模拟数据集以及两个真实的信息检索数据集对提出的方法进 行实验验证。结果表明，在信息检索中，与查询相关的排序学习方法可以有效 地应对这种具有查询排序差异的排序问题，与传统的排序学习方法相比，其排 序性能得到了明显的提高。 关键词：信息检索排序学习与查询相关集成学习尺度学习 i i a b s t r a c t a bs t r a c t a st h ew o r l dw i d ew e bg r o w sr a p i d l yt ob e c o m et h el a r g e s ta n dt h em o s t p o p u l a rs o u r c eo fr e a d i l ya v a i l a b l ei n f o r m a t i o n ，i ti si n c r e a s i n g l yi m p o r t a n tt ob e a w a r eo ft h ew a y st oa c c e s st h el a r g ev o l u m eo fi n f o r m a t i o n u s e r ss u b m i tt h e i r q u e r i e st ot h ei n f o r m a t i o nr e t r i e v a l ( i r ) s y s t e m s ，a n dt h es y s t e m w i l lr a n kt h e i n f o r m a t i o no b j e c t si na c c o r d a n c ew i t ht h e i rr e l e v a n c ew i t ht h eq u e r y i nr e c e n ty e a r s ， l e a r n i n g t or a n ka p p r o a c hi so n eo ft h eh o t t e s tr e s e a r c ht o p i c si ni 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 ki sac l a s so fs u p e r v i s e dl e a m i n gm e t h o d sb a s e do nt h et h e o r i e so f m a c h i n el e a r n i n g ，i tu s e st h el a b e l e dd a t at ot r a i nar a n k i n gm o d e la n dp r e d i c tt h en e w d a t ab yt h et r a i n e dm o d e l h o w e v e r , t h e r eh a v es o m ep r o b l e m sw h e nt h el e a r n i n gt or a n km e t h o d sa p p l i e d i ni 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 ki sb a s e do nt h et h e o r i e so fm a c h i n el e a r n i n g ， o nt h eb a c ko fi t ss u c c e s st h ea s s u m p t i o ne x i s t s ，w h i c hi s “t h et r a i n i n gd a t a s e ta n d b e i n gp r e d i c t e dd a t a s e ts h o u l db eg e n e r a t e df r o mt h ei n d e p e n d e n ta n di d e n t i c a l d i s t r i b u t i o n h o w e v e r , t h ea s s u m p t i o ni sn o ts a t i s f i e di ni ra p p l i c a t i o n s t h er a n k i n g i n s t a n c ei ni rc o n s i s t e do fq u e r ya n d i t sr e t r i e v e dd o c u m e n t ，i ti sc a l l e d q u e r y d o c u m e n tp a i ri n s t a n c e ，a n dt h e s ei n s t a n c ea r er e l e v a n tw i t ht h eq u e r y t h r o u g h t h ea n a l y s i so ft h ed a t a s e ti ni r ，w ec a nf i n dt h a tt h e r ei ss om u c hd i f f e r e n c eb e t w e e n t h ed i s t r i b u t i o n so ft w oq u e r i e s m o r e o v e rt h er a n k i n gc h a r a c t e r so fq u e r i e sa r e d i f f e r e n tt o o ar a n k i n gm o d e lg o o df i tf o raq u e r yc a nn o tb ee f f e c t i v ef o ra n o t h e r t h ep r o b l e mc a na l s ob ef o u n di np r a c t i c ea p p l i c a t i o n , d i f f e r e n tq u e r i e sw i l lh a v e d i f f e r e n tr a n k i n gd i s c i p l i n e t h et r a d i t i o nl e a r n i n gt or a n km e t h o d sc a l ln o td e a lw i t h t h en o n - i d e n t i c a ld i s t r i b u t i o ni ni r t h e r e f o r e ，t h i st h e s i sp r o p o s e san e wr a n k i n gm o d e l ，q u e r y - d e p e n d e n tr a n k i n g m o d e lt od e a lt h ep r o b l e mo fr a n k i n gd i v e r s i t y i nt r a i n i n g ，q u e r y d e p e n d e n tr a n k i n g c o n s t r u c t sm u l t i p l er a n k e r st of i tt h ed i v e r s er a n k i n gc h a r a c t e r si nt r a i n i n gs e t i n p r e d i c t i n g ，q u e r y - d e p e n d e n tr a n k i n gc a nd y n a m i c a l l yg e n e r a t et h ep r o p e rr a n k i n g m o d e lf o rt h ed i v e r s ep r e d i c t e dq u e r y i i l a b s t r a c t i ni n f o r m a t i o nr e t r i e v a l ，t h et r a i n i n gs e tc o n c l u d e sas e to fq u e r i e sw h i c hh a v e d i f f e r e n tr a n k i n gc h a r a c t e r s s ow em u s tt r a i nt h ep r o p e rr a n k e r st of i tt h e s ed i v e r s e r a n k i n gc h a r a c t e r s ，w ec a l lt h e s et r a i n i n gm e t h o d sa sq u e r y - d e p e n d e n tt r a i n i n g t o d e s c r i b et h er a n k i n gc h a r a c t e rd i f f e r e n c eb e t w e e nt w oq u e r i e s ，w ep r o p o s et h e c o n c e p to fq u e r yr a n k i n gd i s s i m i l a r i t y u s i n gi t ，w ec a ne v a l u a t et h ed i v e r s i t yo f r a n k i n gc h a r a c t e r sb e t w e e nt w oq u e r i e si nt r a i m n gs e t ，a n dp a r t i t i o nt h e mi n t os e v e r a l g r o u p s m u l t i p l er a n k e r sc a nb et r a i n e df r o mt h e s eg r o u p sw h i c hc a nr e p r e s e n t r a n k i n gc h a r a c t e r s i nt r a i n i n gs e t t h e n ，w ep r o p o s eq u e r y - d e p e n d e n te n s e m b l e r a n k i n gm e t h o db a s e do nt h e s er a n k e r s b yp r o v i n ga n de x p e r i m e n t s ，i ti st e s t i f i e d t h a tq u e r y - d e p e n d e n te n s e m b l er a n k i n gm e t h o dc a l li m p r o v et h ep e r f o r m a n c eo f t r a d i t i o n a ll e a r n i n gt or a n k i n gm e t h o d si ni r b e s i d e st r a i n i n gm o d e l s ，w ea l s on e e dt og e n e r a t ep r o p e rr a n k i n gm o d e lt o p r e d i c tt h en e wq u e r y , w ec a l li t a sq u e r y d e p e n d e n tp r e d i c t i n g t oi m p l e m e n t , w e m u s t m e a s u r et h ed i s s i m i l a r i t yo f r a n k i n gc h a r a c t e r sb e t w e e nt h ep r e d i c t e dq u e r ya n d l a b e l e dq u e r y , s ow ep r o p o s et h em e t r i cl e a r n i n gm e t h o dt ol e a r nt h eq u e r yr a n k i n g d i s s i m i l a r i t yb yo n l yu s i n gi n s t a n c ef e a t u r e t h e n ，w ep r o p o s ekn e a r e s tq u e r y n e i g h b o rm e t h o da n dd y n a m i ce n s e m b l er a n k i n gm e t h o dt og e n e r a t es p e c i f i cr a n k i n g m o d e lf o rs p e c i f i cq u e r yd y n a m i c a l l y a tl a s t ，w ea p p l yo u rm e t h o d si nt w oi ra p p l i c a t i o n ，d o c u m e n tr e t r i e v a la n dw e b s e a r c h ，a n dt h ee x p e r i m e n tr e s u l t ss h o wt h a to u rm e t h o d sa r eb e t t e rt h a nt r a d i t i o n a l m e t h o d s 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 ，q u e r yd e p e n d e n t ，e n s e m b l e l e a r n i n g ，m e t r i cl e a r n i n g i v 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：苍霸、 加。各年i 乙月r 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：苍葫、 凇o3 年p 月re l 第一章绪论 1 1 引言 第一章绪论 信息检索这个术语1 9 4 8 年由c a l v i nn m o o e r s 提出 3 5 】【8 9 1 ，最初是指从文档 集合中返回满足用户需求的相关信息的过程。随着研究的不断深入，信息检索 逐渐被完善成- - i - j 关于信息的获取( a c q u i s i t o n ) 、表示( r e p r e s e n t a t i o n ) 、存储 ( s t o r a g e ) 、组织( o r g a n i z a t i o n ) 和访问( a c c e s s ) 的学i 可【1 0 7 】【1 0 5 1 。从最初的图 书馆文献，到计算机上的电子信息库，再发展到现在蕴含在互联网中的庞大信 息源，人类所面对的信息数量越来越巨大，类型越来越多样，所以怎样有效地 对海量的信息进行检索，从中找到我们所需要的内容，成为了当前最重要的研 究课题之一。 当用户进行检索时，系统会从信息库中检索出大量与用户查询相关的文档， 然后以文档与用户需求的相关程度为对象，将这些相关文档进行排序，由高到 低的将结果反馈给用户【3 7 】。如何正确评估文档与查询的相关度是信息检索中的 ” 核心问题，这些计算相关度的方法和框架被称为信息检索模型。从最早最简单 的布尔模型开始，很多经典的信息检索模型被相继提出，比如向量空间模型、 概率模型、统计语言模型等。上世纪9 0 年代，随着机器学习技术与统计学习理 论的成熟，基于有监督学习的排序学习信息检索模型成为信息检索领域和机器 学习领域中一个新的研究热点。这类模型使用机器学习中的排序学习方法，从 人工标记的数据中学习到潜在的知识，构造符合数据潜在规律的排序模型，用 以对未知的查询进行排序预测。这类方法从根本上改变了传统检索模型中靠经 验和直观假设来构建检索模型的局面，所以在性能上和适用性上，它都要明显 优于传统的检索模型，越来越多的信息检索应用已经开始使用这类方法作为其 检索核心。 但是，由于这项技术提出和发展的时间并不长，这类模型中也存在着很多 需要解决的问题，这些问题直接影响了排序学习检索模型在实际应用中的性能。 因此，本文将针对排序学习方法应用在信息检索模型中所遇到的有关问题进行 深入研究。 第一章绪论 1 2 基于排序学习的信息检索 1 2 1 信息检索模型 随着社会信息化的不断普及，电子信息的数量正以惊人的速度不断增长着， 有统计表示全世界每年生产1 到2 e b ( 等于2 6 0 b y t e ) 信息，相当于地球上每人 生产2 5 0 m b 的信息，而其中9 9 以上的信息都是电子信息。而且，随着互联网 的飞速发展，网络上出现的信息也同样在成倍的增长。面对蕴含着如此巨量数 据的信息库，必然会产生一个问题，“怎样快速、准确、全面地获取自己所需要 的信息? 。不可否认，即便我们已经拥有计算能力超强的计算机，这仍是一个 很难解决的问题。信息检索技术即是针对这些问题所产生的一门学问，它的内 容包括对信息的表示、存储、组织以及访问，其首要的目标是构造一个信息检 索系统能够找到“最符合用户需求的信息 。信息检索的基本模型可以用图1 1 描述。 图1 1 信息检索基本模型 用户根据其需求归纳成一个查询字符串提交给信息检索系统，信息检索系 统在文档集中检索出与其相关的文档子集，再按照文档与查询的相关性进行排 序并返回给用户。在这个模型中，信息检索系统的工作可以分为两个部分，一 2 第一章绪论 是在信息库中找到与用户需求相关的信息，即检索( r e t r i e v a l ) 任务，二是对这 些检索到的信息进行相关性排序，即排序( r a n k i n g ) 任务。对于检索任务来说， 它的目标是快速、准确地从庞大的信息库中提取出与查询相关的信息，它主要 涉及了信息的存储，信息的索引方式等等技术问题，但这些并不是本文的研究 方向。本文所研究的问题集中在信息检索中的排序任务，即从信息库中检索到 文档之后，怎样将这些文档以一个排序序列的方式回馈给用户，这个序列的顺 序反映了检索文档与用户查询之间相关程度的高低，与查询紧密相关的文档排 在前面，不紧密或者无关的排在后面。在信息检索中，计算查询与文档之间相 关度的模型和方法被称为信息检索模型。 最早的信息检索模型是布尔逻辑模型。它将用户的查询转化为布尔表达式， 并使用这个表达式对文档进行精确匹配。这种方式源自于传统的数据库查询方 法，简单且实用，对于结构化的数据有很好的运行效率。但是，这种检索方式 只能判断出文档和查询是否相关，而不能对其相关程度进行更细致的估计，所 以这种模型并不能满足更高级的检索需求。此后，研究人员开始不断提出新的 方法，以期望能对文档与查询的相关程度进行定量描述。 向量空间模型是2 0 世纪6 0 年代提出的检索模型，它将文档与查询所出现 单词的频率作为向量中的一维，从而将文档和查询转化为一个由单词频率组成 的向量。对这些向量进行相似性比较，比如向量的余弦等，用这些相似度指标 来评价文档和查询之间的匹配程度。除此之外，研究人员又相继提出了基于概 率的概率检索模型，以及基于统计的语言模型检索模型。 但从本质上来看，这些传统的检索模型都可以描述为，基于查询所包含词 语( t e r m ) 的统计特征，比如词频( t e r mf r e q u e n c y , t f ) 、文档频率( d o c u m e n t f r e q u e n c y , d f ) ，文档长度( d o c u m e n tl e n g t h ，d 1 ) 等，根据经验或者基于某些概率 假设，建立相关度的计算公式。因此，这些经验性的方法都存在着一定的局限 性。 随着2 0 世纪9 0 年代机器学习理论和统计学习理论的不断成熟，有监督的 排序学习方法逐渐引起了信息检索领域的重视。从问题模型角度来说，信息检 索中的查询与文档的相关性排序问题与监督学习中的排序学习所要解决的排序 问题极其相似，所以很多排序学习方法被用来解决信息检索中的相关性排序问 题。使用排序学习方法的检索模型可以这样描述：首先，给定一组查询以及它 们的相关文档，由专家对文档与其对应查询的相关程度进行标记，标记内容一 3 第一章绪论 般为“相关 、“半相关、“不相关”等评价相关程度的等级标记；然后，使用 排序学习方法在这些已标记的训练数据上学习得到排序模型；最后对于一个新 的查询，使用已经训练好的排序模型对其相关文档进行排序预测。 排序学习方法可以在信息检索中的人工标注数据上学习到用于查询排序预 测的排序模型，从根本上改变了传统方法中靠经验和直观假设来构建模型的局 面。因此，基于监督学习的检索模型及其相关的排序学习方法逐渐成为信息检 索领域和机器学习领域中新的研究热点。 1 2 2 排序学习 排序学习( l e a r n i n gt or a n k ) 是机器学习中的一类新问题，旨在为一组目标 对象按照某个规律确定一个等级顺序。排序学习在很多领域中有着非常广泛的 应用，比如在信息检索中，信息需要按照与其查询的相关程度进行排序；在协 同过滤中，产品需要按照受欢迎的程度进行排序，等等。 排序学习的学习任务可以描述为，对于训练样本 i ，y ) ，其中元为样本向量， y 为人工标记的排序等级，那么排序学习就是要找到一个排序决策函数 乃( 功：xhy 使得，对于弘，x 2 x 有 h。(五xl，)-h。(砭x2；耋羔二芰 排序学习模型与机器学习中的分类和回归问题有着很多的相似之处，排序 和分类的相同之处在于它们的预测目标都是离散的、不连续的；排序与回归问 题的相同之处在于它们的预测目标都是有序的。因此在排序学习问题提出的初 期，很多研究人员直接将排序问题看作分类或回归问题进行解决，由此也出现 了一批基于分类的和基于回归的排序学习方法。 随着排序学习研究的不断深入，排序学习中的方法也逐渐丰富。目前形成 的排序学习的框架可以描述为：基于机器学习中的统计学习理论，构建描述排 序损失的决策损失函数，并使用优化方法求出在训练数据上的损失最小的排序 模型。这类方法又被称为基于顺序回归的学习方法。根据排序损失构造的基础 不同，基于顺序回归的排序学习方法可以分成三类：基于数据点的方法、基于 数据对的方法和基于数据列表的方法。很多传统的机器学习方法已经被引入到 排序学习方法中，比如使用感知机的p r a n k 排序学习算澍2 6 】，使用神经网络的 4 第一章绪论 r a n k n e t 排序学习算法【16 1 ，使用b o o s t i n g 的r a n k b o o s t 排序学习算法【3 2 】，使用 s v m 的r a n k s v m 排序学习算法【4 5 1 等。 虽然排序学习是解决排序问题的通用模型，但是在信息检索模型中出现的 排序问题却存在其特殊性，本文将针对信息检索中特有的排序问题，提出专门 应用信息检索中的排序学习方法。 1 3 本文动因信息检索中的查询排序差异问题 机器学习方法中有一个重要的前提假设，那就是“独立同分布假设刀 ( i n d e p e n d e n ta n di d e n t i c a ld i s t r i b u t i o n , i i d ) 。这个假设是指，所有样本数据包括 训练集和测试集，必须是以同一个分布独立生成的。对于训练集巩和测试集d 体 来说，它们的分布应该是相同的，即p ( i 挣，y 打id 什) = p ( i 殆，y 死id 死) 。只有满 足独立同分布假设，在训练集上学习得到的模型才具有泛化性。但，在信息检 索中，这种独立同分布假设并不能总得到满足。 信息检索中的排序学习模型可以描述如下：对于一个查询，由检索系统初 步检索出的与其在词语上有关联的文档集合，将每一个查询和检索文档集合中 的每一个文档组成的“查询文档对”作为排序样本，并使用特征提取方法在每 一个查询文档对样本上提取其特征向量，在本文中我们将这些对应于某个查询 所检索出的文档所生成的样本集合，简称为该查询所包含的样本集合。在训练 排序模型时，给定一组查询，人工对这些查询所包含的样本进行标注，其标注 内容为查询文档对所包含的查询和文档的相关性等级。基于这些标记样本，使 用排序学习方法训练得到一个排序模型。在对用户查询进行检索时，对用户查 询所包含的查询文档对样本集合，使用已训练好的排序模型对其进行预测，完 成对用户查询所包含样本的排序。 从这个模型中我们发现，信息检索中的数据是在查询的基础生成的，每个 查询都包含一个查询文档对样本集合，那么在这样的数据上使用排序学习方法 就需要满足一个假设，即所有查询( 包括出现在训练集中的以及出现在预测过 程中的) 包含的查询文档对样本都是独立同分布的。但从信息检索的排序问题 出发，只有同一个查询所包含的样本之间才存在有序的关系，不同查询的样本 之间并没有排序的意义，这就说明信息检索问题中所有查询的样本并不一定都 是同分布的。我们对信息检索的数据集进行了分析，结果发现真实数据中确实 5 第一章绪论 存在这种查询间的非同分布问题，因此排序学习方法应用在信息检索中就会受 到这种非同分布数据的影响。 出现在信息检索中的非同分布问题主要体现在以下几个方面。首先，不同 查询所包含样本的特征向量分布不同，即p ( xq ，) p ( xg ，) 。而且，不同查询 所包含样本的排序目标变量的分布也不同，即p ( yq ，) p ( yq ，) 。这两种分布 差异都可以归类于数据集选取时发生偏差而造成的非同分布。如果只有这种类 型的非同分布问题，那么就可以使用已有的基于非同分布数据的学习方法进行 解决，比如通过计算训练集合与测试集合之间分布的差异，来对训练数据进行 权重设置或者进行重抽样。但我们经过进一步的分析，发现信息检索中的非同 分布问题并不止于此，它的情况要异于一般的非同分布问题。 这种信息检索非同分布问题的特殊性体现在，不同查询间排序目标变量对 样本特征向量的条件分布不同( 后文中简称为目标变量条件分布) ，即 p ( yi 工，q ，) p ( yx ，g ，) ，这种非同分布对排序学习的影响是巨大的。排序学习 是基于机器学习理论建立的，机器学习的主要任务就是在给定训练集分布 p ( y 什，y 什) 以及样本分布尸( 露) 上，对蕴含在数据中的潜在分布p ( yx ) 进行学 习，并得到一个最贴近实际p ( yx ) 的预测模型，从而才能对未知样本x 预测出 正确的目标输出。所以，如果排序学习中的训练集和待预测的样本在目标变量 条件分布上不相同的话，那么在训练集上学习得到的排序模型将不能对待预测样 本进行正确地预测。而且，由于不同的查询所对应的目标变量条件分布不同， 它们对应的最优排序模型也不会相同，也就是说对于不同的查询，其包含的样 本会有不同的排序特性，在某个查询上得到最优结果的排序模型却不适合对另 一个查询进行预测。这种由查询包含样本分布差异所引起的查询对应排序模型 的差异，是信息检索所特有的问题，本文将这种差异问题称为查询排序差异问 题。 由于查询排序差异问题的存在，传统的排序学习方法在信息检索中的使用 会存在很大的局限性。首先，训练集中包含的查询与待预测的查询存在差异性， 所以学习得到的模型在待预测查询上不具有泛化性。而且，传统方法训练得到 的单一的排序模型也不能满足具有不同排序特性的查询的预测需要。因此，针 对信息检索中的存在查询排序差异性问题，我们提出与查询相关的排序学习模 型，其目标是对于每一个待预测的查询，生成最适合于该查询的排序模型进行 预测，从而提高排序学习信息检索模型的性能。 6 第一章绪论 1 4 本文主要研究内容及目标 本文研究的主题是信息检索中的排序学习问题。由上文可知，基于排序学 习的信息检索模型比传统的检索模型具有很大的优势，但由于这种排序学习与 信息检索相结合的研究并没有完全展开，所以这其中存在很多问题需要解决。 本文针对信息检索中查询排序差异问题，指出传统排序学习在这种数据条 件下应用的局限性，由此提出针对此类特殊数据的排序学习问题与查询相 关的排序学习问题，研究该问题的解决思路和方法。总的来说，本文基本遵循 以发现问题、抽象问题、解决问题、具体实现的思路来构建本文工作。 本文研究的主要内容包括： ( 1 ) 针对信息检索中存在的查询排序差异性问题，提出与查询相关的排序 学习模型。本文将会对信息检索中，查询包含样本的非同分布问题进行分析， 指出其对现有的各类排序学习方法的影响，并将这种特殊的非同分布问题定义 为查询排序差异问题。基于此特殊的排序学习问题，本文构建与查询相关的排 序学习问题模型，并提出解决思路：首先，对于信息检索中存在的查询排序差 异问题，对查询间排序特性的差异进行量化，得到能够描述其差异程度的查询 排序差异度；以查询排序差异度为基础，训练得到能够表达不同排序特性的多 排序器模型，并提出基于多个排序器的集成排序学习方法；在进行预测时，对 于不同的待预测查询，以集成排序模型为基础，生成近似于其排序特性的排序 模型进行预测。 ( 2 ) 提出与查询相关的排序模型学习方法，即针对训练集中的查询排序差 异问题，得到与其对应的具有不同排序特性的多排序器模型。在信息检索中的 训练集中会包含多个查询，这些查询具有不同的排序特性，因此传统排序学习 方法所生成的单一的排序模型不能表达训练集中存在的不同的排序特性。针对 此问题，我们提出能够描述训练集中查询间排序特性差异程度的排序差异度， 并以此为标准找出训练集中具有相似排序特性的查询集合。基于这些查询集合， 可以生成多个子排序器，它们有效地对训练集所包含的排序特性进行表达。 然后，基于得到的多个排序器，我们提出了“与查询相关的集成排序学习 模型”。这种方法采用集成学习的模型框架，实现使用多个排序器对同一个目标 进行预测。通过理论证明和实验进行分析可知，使用这种基于多排序器的集成 排序学习方法比传统的排序学习方法具有更高的泛化性能。同时，这种多排序 7 第一章绪论 器模型也为与查询相关的排序预测方法的实现提供了模型基础。 ( 3 ) 提出与查询相关的排序预测方法，其目标是在对新的用户查询进行预 测时，能够生成适合其排序特性的排序模型。由于查询具有排序差异性，所以 对于待预测的查询，只有使用具有与其相近排序特性的排序模型进行预测才能 得到正确的预测结果。这就需要对待预测的查询进行排序差异的评估，但是前 面提出的基于标记查询的排序差异度并不能应用在没有标记数据的待预测查询 上。基于此问题，本文提出基于特征空间的排序差异尺度学习方法，即通过机 器学习的方法在特征空间上学习到能够近似描述查询间排序差异的差异度尺 度。 利用学习到的排序差异尺度，就可以对待预测查询与已标注查询之间的排 序差异进行度量，实现与查询相关的排序预测方法。本文提出了两种排序预测 方法，首先我们提出基于k 近邻的排序学习方法，它以排序差异尺度为基础， 从训练集中找到与待预测查询最接近的查询作为训练集，并得到相应的排序模 型进行预测。但是这种方法是在线学习方法，其时间复杂度比较高，所以不能 满足信息检索实际应用的需要。因此，我们又提出基于动态集成的排序学习方 法，它以与查询相关的集成排序学习方法为基础，通过计算待预测查询与子排 序器之间的排序差异尺度，来实现集成权重的动态生成，从而得到接近于待预 测查询排序特性的集成排序模型。 ( 4 ) 最后，本文将实现完整的与查询相关的排序学习方法，并在模拟数据 和信息检索数据集中进行实验，验证与查询相关排序学习方法的性能。 1 5 本文章节安排 本文一共分六章，各个章节内容和结构安排如下： 第一章绪论概括介绍了本文的研究背景，即信息检索模型和排序学习方法， 并对本文的研究动机和主要内容进行概括的介绍。 第二章综述相关工作，对本文涉及到的已有的相关工作加以介绍。首先， 对排序学习问题进行综述，并将现有的研究思路进行分类，介绍其中经典的学 习方法。然后，对本文的问题来源信息检索模型进行介绍，包括信息检索 的经典检索模型，以及常用的信息检索系统的性能评估方法。最后针对现有的 应用于信息检索中的排序学习方法介绍，特别是对它们所提出的信息检索中特 8 第一章绪论 有的问题进行了介绍。 第三章首先提出信息检索中存在的非同分布问题，针对此问题对机器学习 中的独立同分布假设，以及现有的针对非同分布数据的学习模型和方法进行介 绍。在此基础上，对信息检索中查询问所体现的非同分布现象进行分析，指出 其对传统排序学习方法的影响。通过这一系列分析，提出信息检索中非同分布 问题的特殊性，即不同的查询具有不同的排序特性，我们称其为查询排序差异 问题。在这种具有排序差异的数据上，一般的排序学习方法存在很大的局限性， 由此我们提出与查询相关的排序问题模型，及其解决思路。 第四章集中讨论与查询相关的排序学习模型中的排序模型学习方法，其目 的是得到对应于训练集中所包含的不同排序特性的多排序器模型。为此，我们 首先提出能描述查询间排序特性差异程度的查询排序差异度。使用该差异度， 就可将训练集中的查询按照其排序特性的差异进行分组，从而训练出多个具有 不同排序特性的排序模型。在此基础上，提出基于多排序器的靠与查询相关的 集成排序学习方法”，并从理论证明和实验两个角度得出，这种与查询相关的集 成排序方法可以有效提高排序模型的泛化性能。 第五章集中讨论与查询相关的排序学习模型中的排序预测方法，其目标是 针对不同的带预测查询，生成适合于它排序特性的排序模型进行预测。想要找 到与待预测查询具有同样排序特性的排序模型，就必须对预测查询的排序差异 度进行度量，但是第四章中提出的差异度并不能应用在不包含标记数据的待预 测查询上。因此，我们提出使用尺度学习的方法在样本特征空间中学习到能够 描述查询排序差异程度的查询排序差异尺度。应用此尺度，提出相应的在线和 离线的排序预测方法，并在真实的信息检索数据集中对其进行了验证。 第六章即最后一章，总结本文工作，并对下一步的研究工作进行展望。 9 第二章相关工作 2 1 引言 第二章相关工作 本文的研究得益于排序学习领域和信息检索领域的相关研究成果，本章详 细介绍与本文相关的研究工作和成果，包括排序学习的模型和方法，信息检索 中的信息检索模型、评价指标，以及针对信息检索模型提出的排序学习方法。 本章的安排如下：在2 2 节中，针对本文所集中研究的排序学习问题进行介 绍，包括排序学习的问题模型，排序学习方法的发展过程。然后针对排序学习 中的基于顺序回归的学习方法进行着重介绍，按照损失函数构建对象的不同， 我们将其分为三类进行介绍，分别是基于数据点的、基于数据对的、基于数据 列表的排序学习方法，并对其中的经典算法进行介绍。 随后针对信息检索的相关工作进行介绍，这是本文研究工作的问题背景。 首先在2 3 节中对传统的信息检索模型进行介绍，包括布尔检索模型( b o o l e a n m o d e l ) 、向量空间模型( v e c t o rs p a c em o d e l ，v s m ) 、概率模型( p r o b a b i l i s t i cm o d e l ) 和统计语言检索模型( l a n g u a g em o d e l sf o ri n f o r m a t i o nr e t r i e v a l ) 。然后在2 4 节中。 对信息检索中所用到的排序评估指标进行介绍，包括查准率( p r e c i s i o n ) 、召回率 ( r e c a l l ) 、平均查准率的均值( m e a na v