（计算机软件与理论专业论文）信息检索中基于图的半监督排序学习问题研究.pdf

摘要 摘要 随着网络技术的迅速发展和互联网规模的不断扩大，互联网成了全球晟大、 最广泛使用的信息库，如何有效检索这些海量信息成为当前重要的研究课题， 因而信息检索技术越来越受到人们的重视。信息检索是指从大量的实例集合中 查找到与给定的查询( q u e r y ) 相关的信息子集，是处理海量信息的重要手段。目前 绝大多数的信息检索系统中，其检索出来的信息( 如文档) 都以排序的方式返回给 用户。因此，如何高效地对信息进行排序成为信息检索研究的核心问题之一。 传统的排序学习方法包括无监督学习和监督学习方法。无监督学习是基于 经验估计的，对搜索结果有一定的盲目性，效果不是很好。监督学习需要大量 的人工标注样本，而标注样本是一项耗时长、难度大且代价昂贵的工作。与此 同时，无标注样本数量巨多、获取简单且廉价，如何利用无标注样本辅助学习， 也成为一个重要的研究课题。除此之外，传统的排序学习方法以相似度为基础， 只关注局部信息，使得一些相似度不高却高度相关的实例排名靠后，从而影响 了排序性能。为解决上述问题，本文将基于图的半监督学习应用到信息检索中， 实现了基于图的半监督排序学习。 已有基于图的半监督排序方法只把查询作为标注信息，从某种程度上说并 没有合理利用标注信息，因而本文从合理利用标注信息入手，结合图中的流形 结构，分析得出处于同一流形结构中节点间的影响程度要大于处于不同流形结 构中节点间的影响程度。基于以上分析本文提出并实现了基于权重调节的半监 督图排序算法，并成功应用于文档检索中。 为了更有效的利用同一实例的多种表现形式，使得在克服单图学习缺陷的 同时提高排序性能，本文还将基于图的半监督排序学习扩展到多视图学习中， 提出了两种不同的多图融合方法一图融合算法和结果融合算法，文中还结合损 失函数从理论上对两种算法进行了比较分析，并将它们成功应用到论文检索中。 关键词：信息检索排序学习半监督学习图学习多图融合 a b s t r a c t a b s 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 i r ( i n f o r m a t i o n r e t r i e v a l ) i sd e s i g n e df o rt h ep u r p o s e ，w h i c hs e a r c h e si n f o r m a t i o nf r o mi n s t a n c e ss e t a c c o r d i n g t ot h es u b m i t t e dq u e r y i ti sa l s oa ni m p o r t a n ta p p r o a c hf o rp r o c e s s i n gl a r g e v o l u m ei n f o r m a t i o n a tp r e s e n t ，m o s ti rs y s t e m sr a n kt h er e t r i e v e di n f o r m a t i o n ( e g ， d o c u m e n t s ) b e f o r ep r e s e n t i n gt h e mt ou s e r t h u s ，h o wt or a n ki n f o r m a t i o ne f f e c t i v e l y a n d e f f i c i e n t l yb e c o m e s o n eo ft h ek e y p r o b l e m si ni r t r a d i t i o n a lr a n k i n gm e t h o d si n c l u d eu n s u p e r v i s e da n ds u p e r v i s e dl e a r n i n g m e t h o d s ，b a s e do ne x p e r i e n c e ，u n s u p e r v i s e dl e a r n i n gh a sac e r t a i nd e g r e eo f b l i n d n e s st or e t r i e v a l e dr e s u l t s ，t h u st h ep e r f o r m a n c ei sn o tg o o d s u p e r v i s e dl e a m i n g r e q u i r e s a l a r g e a m o u n t o fl a b e l e di n s t a n c e s ，a n d l a b e l i n g i n s t a n c e si s t i m e - c o n s u m i n g ，d i f f i c u l ta n dc o s t l y , m e a n w h i l et h e r ea r el a r g ev o l u m eo fu n l a b e l e d d a t a ，w h i c ha r ee a s i e ra n dc h e a p e rt oa c c e s s b e s i d e s ，t h et r a d i t i o n a lr a n k i n gm e t h o d s i sb a s e do ns i m i l a r i t yb e t w e e ns a m p l e sa n dc o n c e r n so n l yl o c a li n f o r m a t i o n ，m a k i n g s o m eh i 曲r e l e v a n ti n s t a n c e sr a n kl o w e r , t h o s ea f f e c tt h ep e r f o r m a n c eo ft h er a n k i n g t oa d d r e s st h ea b o v ep r o b l e m s ，s e m i s u p e r v i s e dg r a p hl e a r n i n gi sa p p l i e dt o i n f o r m a t i o nr e t r i e v a li nt h i sd i s s e r t a t i o n e x i s t i n gs e m i - s u p e r v i s e dg r a p hr a n k i n gm e t h o do n l yt a k e sq u e r i e sa sl a b e l e d d a t a , t os o m ee x t e n ti td o e s n tm a k ef u l lu s eo ft h el a b e l e di n f o r m a t i o n a c c o r d i n gt o t h ea n a l y s i so ft h em a n i f o l ds t r u c t u r e ，i ti sd r a w nt h a t ：t h ei m p a c tb e t w e e nn o d e si n t h es a m em a n i f o l ds t r u c t u r ei s g r e a t e rt h a nt h o s ei nd i f f e r e n to n e s b a s e do nt h e a b o v ec o n c l u s i o n s ，t h er e - w e i g h t e dm e t h o df o rs e m i s u p e r v i s e dg r a p hr a n k i n gi s p r o p o s e da sw e l la ss u c c e s s f u l l ya p p l i e di nd o c u m e n t r e t r i e v a l i no r d e rt o e f f e c t i v e l yu s em u l t i p l ea t t r i b u t e so fs a m ei n s t a n c et oi m p r o v et h e r a n k i n gp e r f o r m a n c ea sw e l la so v e r c o m et h es h o r t c o m i n g so fs i n g l e v i e wl e a r n i n g 。 s e m i - s u p e r v i s e dg r a p hr a n k i n gi se x t e n d e dt om u l t i v i e wl e a r n i n gi nt h i sd i s s e r t a t i o n ， t w og r a p h - b a s e dm u l t i - v i e w l e a r n i n g m e t h o d sn a m e d r e s u l t - p r o p a g a t i o n a n d a b s t r a c t m u l t i - g r a p hp r o p a g a t i o na r ep r o p o s e d w ea l s oa n a l y z et h et w om e t h o d sw i t ht h el o s s f u n c t i o n , a p p l yt h e mt or e t r i e v a lo fp a p e r s 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 ，l e a n i n gt or a n k ，s e m i s u p e r v i s e dl e a r n i n g ， g r a p hl e a r n i n g ，m u l t i p l eg r a p hp r o p a g a t i o n n 1 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 训舍研 砷年“日 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 籼并警磊f 荆e t m 年( ，月f 。 本授权书。 指导教师签名：学位论文作者签名： 解密时间： 年月日 各密级的最长保密年限及书写格式规定如下： 第一章绪论 第一章绪论 1 1 引言 随着社会信息化程度的迅速提高，因特网的日益普及，数字图书馆和各种 各样的电子信息载体的不断涌现，使得信息的总量以惊人的速度不断地膨胀， 据统计，数字化信息每1 8 个月就翻一群1 1 ，迫切需要更有效的理论和方法来处 理与日俱增的信息。信息检索适应了这一要求，并成为当前信息处理研究领域 中的重要课题。 信息检索是指从大量的文档集合中查找到与给定的查询( q u e r y ) 相关的信息 子集，包括信息的表示存储、检索和排序 2 1 。检索模型的选取对信息检索的结果 有重要的影响。上世纪七十年代开始，人们开始将机器学习方法与信息检索结 合起来，包括以布尔模型、向量空间模型、概率模型等为代表的无监督学习以 及以排序支持向量机、a d a r a n k 、a d a b o o s t 、l i s t n e t 等为代表的监督学习都取得 了一定的成果。近年来，基于图理论的p a g e r a n k 在搜索引擎g o o g l e 上取得了 重大成功，使得基于图的学习成为新的研究热点。传统的无监督学习由于对解 空间的搜索带有一定的盲目性，因而检索结果在一定程度上精确度不高；监督 学习需要大量的标注数据，一方面人力、财力或其它的一些原因，使得标注代 价比较大，另一方面，数据每天都在上亿级的增长，标注速度远远跟不上数据 更新的速度，这使得监督学习得到的模型具有滞后性；而未标注数据相对来说 容易收集，在这种情况下，同时使用未标注数据和已标注数据的半监督学习就 成为了热门的研究领域，越来越受到研究者的重视和青睐。本文的研究重点是 与图相关的半监督排序问题。 1 2 研究背景 1 2 1 信息检索 随着互联网上信息的同益增多，人们越来越依赖搜索引擎来寻找所需信息。 搜索引擎以一定的策略在互联网中搜集、发现信息，对信息进行理解、提取、 组织和处理，并为用户提供检索服务，从而起到信息导航的目的。搜索服务是 所有互联网用户中使用最多的服务之一，根据中国互联网络信息中一l , ( c h i n a 第一章绪论 i n t e m e tn e t w o r ki n f o r m a t i o nc e n t e r ，c n n i c ) 最新的第2 3 次中国互联网络发展 状况统计报告显示，截至2 0 0 8 年1 2 月3 1 日，我国网民数量已经达到2 9 8 亿，其中有6 8 o ( 超过2 0 2 亿) 的网民经常使用搜索引擎，比2 0 0 7 年底增长 了5 1 0 0 万人【3 】。随着人们对搜索服务的日益依赖，搜索引擎市场将是一个巨大 的潜在市场，而搜索引擎技术的核心是信息检索。 影响信息检索性能的最关键因素是检索模型，包括文档和查询条件的表示 方法、文档评价和查询相关性的匹配策略、查询结果的排序方法和用户进行相 关反馈的机制等。机器学习技术的发展，使得研究者们开始从机器学习的角度 来研究检索模型，一些有效的信息检索模型陆续提出并逐渐应用到相关的系统 中。其中影响比较大的检索模型包括：布尔逻辑模型 4 】、向量空间模型4 1 、概率 检索模型【4 】、统计语言模型【4 1 、以及基于监督学习的检索模型【4 】o 最初，检索系统借用数据库系统的查询方法，采用布尔逻辑模型5 】【6 】，使用 语词的布尔逻辑组合作为查询条件，从文档数据库中检索出满足查询条件的对 象。然而布尔逻辑模型起源于数据库管理系统，所以只能查找结构化、精确的 数据信息，不能很好地解决无结构的信息检索，也不能实现查询条件与候选对 象的部分匹配。s a l t o n 等人在2 0 世纪6 0 年代末提出了向量空间模型【7 】，使用 由语词构成的向量来表示对象与查询条件中的信息，并研制了基于向量空间模 型的s m a r t 实验检索系统【8 】。r o b e r s o n 和s p a r c k 在1 9 7 6 年提出经典概率模 型 9 】，即通过估计检索系统中文档与用户查询条件的相关概率对文档集合进行排 序，基于以上原理，研究者们还研制了二值独立检索模型( b i n a r yi n d e p e n d e n t r e t r i e v a l ，b i r ) 1 0 】、双泊松模型( 2 p o i s s o nm o d e l ) 1 1 j 、b m 2 5 检索模型以及改进 的b m 2 5 模型【l2 1 。语言模型研究本身最初是利用统计技术计算词汇间的依赖关 系，以帮助语音识别系统提高识别率。在1 9 9 8 年，p o n t e 和c r o f t 首次提出了 将统计语言模型和信息检索相结合的新的思路【l 引。p o n t e 和c r o f t 当初提出的语 言模型检索方法现在经常被称为“查询条件生成的概率模型”，该模型大体的研 究思路是：首先估计每篇文档的词汇概率分布，然后计算从这个分布抽样得到 查询条件的概率，并按照查询条件的生成概率来对文档进行排序。 基于监督学习的检索模型依据人工标注的数据集训练排序模型，用特征向 量表示对象d 和查询q 组成的二元组。c o o p e r t l 4 】和g e y l l 5 】分别在1 9 9 2 年和 1 9 9 4 年提出使用l o g i s t i cr e g r e s s i o n 模型对有待查询的文档进行排序，其检索出 的文档按照l o g i s t i cr e g r e s s i o n 的输出概率值进行排序；n a l l a p a t i 1 6 】于2 0 0 4 年 2 第一章绪论 提出了用支持向量机( s u p p o i tv e c t o rm a c h i n e s ，s v m ) 和最大熵( m a x i m u m e n t r o p y ，m e ) 模型来对文档进行排序；g a o 和b u r g e s 也分别提出利用相关的文 档和不相关文档构成的有序对训练排序模型，并且分别提出了用感知机和神经 网络模型进行优化，取得了良好的效果【l7 j 驯；h e b r i c h 等研究者系统的研究了基 于有序对的排序方法，把排序问题归结成为在有序对空间上的二值分类问题并 且用支持向量机进行优化求解u 9 ；j o a c h i m s 把这种基于有序对的学习方法应用 到搜索引擎上，利用点击序y u ( c l i c k t h r o u g h ) 数据提高搜索引擎的性能【2 0 】。这个 算法被集成到了其开发的s v m l i g h t 工具包【z l j 中，称为排序支持向量机( r a n k i n g s v m ) 。 传统的布尔逻辑模型【5 】【6 】、向量空间模型【7 】【8 1 、概率检索模型1 0 】 1 l 】、统计语 言模型【l3 】等是基于无监督学习的，包含较多的参数，属于依赖经验设计的模型， 对搜索目标有一定的盲目性，因而效果不是很理想；基于监督学习的检索模型 尽管比传统的检索模型有更强的跨领域性和适应性，但监督学习需要大量的标 注数据，而获取标注数据的代价比较大；另外大量的未标注数据相对容易获得 且能更好的代表数据分布，因此能同时利用少量标注数据和大量未标注数据的 半监督学习开始引起了研究者的关注。 1 2 2 半监督学习 半监督学习的研究起步相对较晚，可能是因为在当时的主流机器学习技术 ( 例如前馈神经网络) 中考虑未标记示例相对比较困难。随着统计学习技术的 不断发展，以及利用未标记示例这一需求的日渐强烈，半监督学习才在近年来 逐渐成为一个研究热点2 2 】【2 3 】【2 4 1 。半监督学习研究主要关注当训练数据的部分信 息缺失的情况下，如何获得具有良好性能和推广能力的学习机器，这里的信息 缺失涵盖数据的类别标签缺失或者存在噪声，数据的部分特征维缺失等多种情 况，本文主要关注的是标签缺失的情况。与其他的模型相比，半监督学习检索 模型有它先天的优势。首先，半监督学习跟监督学习一样以统计机器学习为基 础，比无监督的经验式估计模型有优势；其次，半监督学习检索模型关注信息 缺失的方式使得它比其他类型的检索模型具有更强的适应性和跨领域检索能 力。 在半监督学习中有两个常用的基本假设，即聚类假设( c l u s t e ra s s u m p t i o n ) 和流形假设( m a n i f o l da s s u m p t i o n ) 【2 2 】 2 3 】。聚类假设是指处在相同聚类( c l u s t e r ) 第一章绪论 或者同一结构中的示例有较大的可能性拥有相同的标记。根据聚类假设，决策 边界就应该尽量通过数据较为稀疏的地方，在这一假设下，大量未标记示例的 作用就是帮助探明示例空间中数据分布的稠密和稀疏区域，从而指导学习算法 对利用有标记示例学习到的决策边界进行调整，使其尽量通过数据分布的稀疏 区域，着眼于整体特性。流形假设是指处于一个很小的局部邻域内的示例具有 相似的性质，因此，其标记也应该相似。这一假设反映了决策函数的局部平滑 性。和聚类假设着眼整体特性不同，流形假设主要考虑模型的局部特性。在该 假设下，大量未标记示例的作用就是让数据空间变得更加稠密，从而有助于更 加准确地刻画局部区域的特性，使得决策函数能够更好地进行数据拟合。各种 半监督学习算法的本质区别在于实现两个基本假设的程度。 根据半监督学习算法的工作方式，可以大致将现有的半监督学习算法分为 四种，自训练、生成式模型、协同训练和基于图正则化框架的半监督学习算法。 自训练( s e l f - t r a i n i n g ) 本质上利用了聚类假设，明显的缺点是对一个数据样本的 标注错误在重复训练过程中会被加强；生成式模型( g e n e r a t i v em o d e l ) 2 2 】是最 早直接利用聚类假设的算法，缺点是如果模型族过小或者标注数据不足以描述 数据集的类条件分布时，效果会非常差：协同训练( c o t r a i n i n g ) 【2 5 】算法属于多 视图学习( m u l t i v i e wl e a r n i n g ) 的特例，是自训练的一种扩展，此类算法隐含 地利用了聚类假设，它们使用两个或多个学习器，在学习过程中，这些学习器 挑选若干个置信度高的未标记示例进行相互标记，从而使得模型得以更新，协 同训练从很大程度上可以看做是一种框架，可以与具体的学习器相结合。基于 图正则化框架的半监督学习算法 2 6 】 2 7 】 2 8 】 2 9 】 3 0 】除了利用聚类假设外，还直接或间 接地利用了流形假设，它们通常先根据训练例及某种相似度度量建立一个图， 图中结点对应了( 有标记或未标记) 示例，边为示例间的相似度，然后，定义 所需优化的目标函数并使用决策函数在图上的光滑性作为正则化项来求取最优 模型参数。基于图的半监督学习的检索模型把文档和查询统一看做图中的节点， 且节点的特征没有限制，这种表达方式使得用户可以更加方便自然的综合利用 各种相关信息( 如超文本的链接分析数据、点击过程数据、文档元数据等) ，以 提高检索性能。 本文所研究的课题属于半监督学习领域的检索模型。 4 第一章绪论 1 2 3 基于图的半监督学习 监督学习算法都只关注局部假设，即距离相近或者给定特征相似的样本间 有相同的标注。而很多在同一流形结构上的样本，本来具有相同标注的样本， 但因其距离相差较远或给定的特征相似程度不高，传统的监督学习算法就无法 正确给出其标注。相比半监督学习其他算法，基于图的半监督学习方法以其充 分利用局部和关注同一流形结构的全局假设逐渐引起了研究者的关注，并在蛋 白质排序、文本分类、图像识别、视频识别等领域已经取得了不错的成果，如 j z h u 【27 】使用高斯随机场以及谐波函数来进行半监督学习，他们首先基于训练例 建立一个图，图中每个结点就是一个( 有标记或未标记) 示例，然后求解根据 流形假设定义的能量函数的最优值，从而获得对未标记示例的最优标记；d z h o u 在根据示例相似性建立图之后，让示例的标记信息不断向图中的邻近示例传播， 直到达到全局稳定状态 3 0 】【3 5 】：j h e 3 1 1 等人将该思想成功运用到图像识别中； w e s t o n 3 3 】【3 4 1 等人将此思想运用到蛋白质识另i j 中，j l i u 等人运用到v i d o er e s e a r c h ， 通过构建图结构利用v i d o e 的链接和语音信息进行排序【3 2 】。 1 3 本文主要内容 1 3 1 本文研究动因 传统的学习算法都只关注局部信息，即只有距离相近或者给定特征相似的 样本间才有相同的标注。而很多在同一流形结构上的样本，本具有相同的标注， 但因距离相差较远或给定特征下相似度不高，传统的学习算法就赋予了不同的 标注，导致了学习错误。因而，如何挖掘数据间潜在的流形结构信息辅助学习 是本文所要研究的第一个问题。 目前，所有的主流排序学习方法都是基于有监督学习的方法，需要大量的 人工标注样本。然而，标注样本是一项耗时长、难度大，而且代价昂贵的工作。 例如在蛋白质同源检测中，一个蛋白质结构的标注就会花费专家几个月的时间； 计算机辅助医学图像分析中，如果要求医学专家把医学图像中的病灶都标识出 来，则往往是不现实的。而另一方面，随着数据收集和存储技术的飞速发展， 收集大量未标记的( u n l a b e l e d ) 示例已相当容易，例如，d n a 序列可以在蛋白 质数据库中取得，医学图像随时可从医院获取。如果只使用少量的有标记示例， 第一章绪论 利用它们所训练出的学习系统往往很难具有强泛化能力；另一方面，如果仅使 用少量“昂贵的有标记示例而不利用大量“廉价的”未标记示例，也是对数 据资源的极大的浪费。因此，在有标记示例较少时，如何利用少量的标记示例 和大量的未标记示例来改善排序性能是半监督学习的目标，是本文所要研究的 第二个学习问题。 在真实世界中，我们发现同一个实例根据特征选取的不同可以表示为不同 的向量，或者不同的图，甚至是向量和图的混合。而在以往的很多机器学习方 法中，数据都是表示为一个向量或者单个图。而单个向量或者单个图上的排序 却存在一系列的问题。如何利用同一实例的多种表现形式以解决单视图出现的 问题并提高排序性能，这是本文所要研究的第三个问题。 1 3 2 本文主要工作及目标 本文研究的主题是基于图的半监督排序问题，从传统排序学习算法只关注 局部信息的缺陷引出利用全局流形结构的图排序问题；通过利用不同流形结构 上数据间的影响程度不同，将基于权重调节的半监督学习引入到图排序问题中； 从单视图学习存在缺陷以及现实世界中同一实例存在多种表现形式的本质出发 将多视图学习引入到图排序问题中，其中多视图学习也是半监督学习的一种。 具体来说，本文的研究工作包括以下几个方面： 一基于相似度的图排序学习 传统的排序学习算法如o k a p i 系统的b m 2 5 算法，监督学习里面的 r a n k b o o s t 、r a n k n e t 等关注的都是局部信息，即对象与查询问的距离信息或者 相似度等信息，也就是说只有当对象与查询的距离足够近或者相似度足够高的 情况下，才有可能被排在前面。而实际中我们发现，有些对象与查询问的距离 并不近，相似度也不高，但它们却是与查询高度相关的。举例来说，在网页检 索中，尽管有些网页间文本内容的相似程度并不高，但由于链接关系使得它们 处于同一个流形结构中，此时网页间的相关程度也会比较高，但传统的排序学 习算法无法解决此类问题。为了更有效的挖掘数据潜在的流形结构信息，本文 提出基于相似度的图排序学习算法，利用节点间内容上的相似关系进行建图， 并为节点间提供转移概率，使得图中的每个节点都根据它邻居节点的概率分布 来更新自己的概率分布，并且和该节点越相似的邻居节点对它概率分布的影响 6 第一章绪论 权值越大，这样相似节点就趋于相似的概率分布。该传播过程迭代执行，直到 节点的概率分布收敛到一个定值。本文在第三章将详细介绍图排序的若干问题。 二基于权重调节的半监督图排序学习 半监督学习的聚类假设相同簇上的节点具有较高的相似性，也就是说处在 同一结构上的节点间的影响程度应该大于处在不同结构上的节点间的影响程 度，而在一般的传递过程中，这种影响程度被认为是均等的。如果我们能够利 用节点间的“同一结构”信息重构图结构，更改相似度矩阵，使得处在同一结 构中的节点间影响程度大于不同结构中的节点间影响程度，即节点的排序值以 较高的概率传递给该节点，则该节点也会有较高的排序值。本文的第三章对此 将做详细阐述。 三基于多图融合的排序学习 在以往的很多机器学习方法中，数据都是表示为一个向量或者单个图。而 在真实世界中我们发现同一个实例根据特征选取的不同可以表示为不同的向 量，或者不同的图，甚至是向量和图的混合。一个比较典型的例子就是网页分 类，既可以根据网页本身包含的信息对网页进行正确分类，也可以利用链接到 该网页的超链接所包含的信息来进行正确分类，在论文引用系统中也有类似的 关系。在互联网上，基于链接的图排序应用已十分广泛，具有代表性的是p a g e r a n k 和1 l i t s ，它们将网页之间的影响通过图上的路径进行传递，直到达到稳定状态。 但是，排在最前面的几篇文档中总会有与用户查询不相关的文档出现。这种错 误发生的主要原因是p a g er a n k 反映的是网页间的链接关系，而一些垃圾链接或 者无效链接的引入使得作弊的可能性大大增强，即一些原本无关的网页也可能 被排在前面。而基于文本内容进行排序的算法一般只关注局部信息，即只有内 容上距离相近的网页才会被排在前面，而一些虽然距离较远也相关的文本却被 排在后面。 为了解决单视图学习带来的问题，我们将多视图学习引入到图排序中以综 合利用各种有效信息提高排序性能，根据前提条件以及融合时间的不同提出凉 种不同的图融合算法，并对它们进行分析，以找到适应某种情况下的最佳算法。 在第四章中将对此进行详细描述。 7 第一苹绪论 1 4 本文的组织结构 本文共分为六章，各章节内容和结构安排如下： 第一章是绪论，概括介绍本文的研究背景、研究内容和研究目标。 第二章综述相关工作，介绍排序学习，半监督学习和图学习。对半监督学 习和图学习等领域现有算法进行综述，作为后续章节工作的基础。 第三章详细介绍基于图的半监督排序方法，给出算法流程和收敛性证明， 并在此基础上提出基于权重更改的半监督图排序方法。 第四章将基于图的半监督排序方法与多视图学习相结合引出两种多图融合 方法一结果融合和图融合算法，给出算法的流程并结合损失函数对算法进行比 较分析。 第五章将把本文提出的有关算法应用于信息检索以检验算法的有效性。 第六章是总结与展望，总结本文的工作，并展望下一步的研究工作。 第二章相关工作综述 第二章相关工作综述 本文的研究基于半监督学习，排序学习和图学习中的相关研究成果，因此 本章将简要介绍与本文相关的研究工作和成果，包括半监督学习相关算法、排 序学习、基于图的半监督学习以及信息检索评价指标等。 半监督学习是本文的一个研究基础，本章的2 1 节将对半监督学习的相关算 法给出介绍，并重点介绍多视图学习，为后续的将多视图与图排序结合做准备。 排序学习是机器学习领域的新问题，也是信息检索的关键技术，2 2 节将对 一般的排序学习加以阐述，给出排序学习的损失函数。 基于图的学习可以看作半监督学习的一种，因而也称为基于图的半监督学 习，它是本文的另一个研究基础，2 3 节对基于图的半监督学习在分类和数字识 别中的研究成果做了阐述，并指出已有的将基于图的半监督学习应用到排序学 习上的尝试并未真正意义上利用到有价值的标注信息，进而引出本文的研究目 标。 在信息检索的研究工作中，检索性能的评价是一个非常重要的问题，它是 衡量各种排序方法好坏的量化指标。2 4 节将对信息检索的评价指标做一个简单 的介绍，包括常用的信息检索指标如平均查准率的均值( m e a na v e r a g e p r e c i s i o n , m a p ) l 4 j 和n d c g ( n o r m a l i z c dd i s c o u n t e dc u m u l a t i v eg a i n ) t j 。 2 1 半监督学习 半监督学习的主要思想是利用大量的无标注数据学习出数据的内在结构或 规律，在此基础上用少量的已标注数据进行指导，试图得到更好的效果。比起 无监督学习，这些学习方法使用一些己标注数据来指导学习，可以提高算法的 精确度，同时降低了在监督学习中对昂贵已标注数据的需求量。因为半监督学 习使用少量人力却能得到很高的精确度，所以在理论和实践上都很受关注。 在介绍具体的半监督学习技术之前，有必要先探讨一下为什么可以利用未 标记示例来改善学习性能。关于这个问题，有不少研究者给出了解释。例如， d j m i l l e r 和h s u y a r 3 6 】从数据分布估计的角度给出了一个直观的分析。他们 假设所有数据服从于某个由个高斯分布混合而成的分布，即 9 第二章相关工作综述 ( 2 - 1 ) 其中：口，= 1 为混合系数，0 = 舅) 为参数。实例数据可由特征向量来表示，如 第f 个数据可以由特征向量焉来表示，第f 个高斯分布可以由m 表示，这样标注就 可视为由选定的混合成分班和特征向量玉以概率飑i 玉，砚，) 决定的随机变 量。根据最大化后验概率可以得到数据在上述条件下的最优标注即： 庇( 功= a r g m a ) 艺，讹= k l m l = j , x i ) 尸( 砚= j l x _ f ) ( 2 - 2 ) 其中p ( m f = jx f ) = o t ，f ( x ，l 嘭) ：。o l ，f ( x ，l 岛) 。 这样，学习目标就变成了利用训练样例来估计p ( c ，= klm ，= ，x ，) 和 p ( m ，= jx ，) ，这两项中的第一项与类别标记有关，而第二项并不依赖于示例的 标记，因此，如果有大量的未标记示例可用，则意味着能够用于估计第二项的 示例数显著增多，这会使得第二项的估计变得更加准确，从而导致式( 2 2 ) 更加 准确，也就是说，学习器的泛化能力得以提高。实际上，只要能够合理建立未 标记示例分布和学习目标之间的联系，就可以利用未标记示例来辅助提高学习 性能。 我们按照设计思想和研究思路，将不同的半监督学习算法分成了五类：生成 模型、自训练、直推式、多视图学习、基于图的半监督学习。需要说明的是， 这样的划分只是为了方便理解半监督算法，实际上不同类别之间可以有重合。 2 1 1 生成模型 生成模型( g e n e r a t i v em o d e l s ) e 2 2 】可能是晟早的半监督学习方法。该模型认为， 不同类别的数据是由不同的、可区分的“源 产生，即数据的类条件概率是可 区分的混合分布。如果能够通过大量的未标注数据准确的估计出不同数据源的 分布参数，并利用标注信息指定类别，则半监督学习很容易实现该方法。具体 来说假设数据属于两个类别，未标记示例属于每个类别的概率视为一组缺失参 数表示的高斯分布，假设全部的数据都来自这个混合模型，模型根据大量的未 1 0 第二章相关工作综述 标注数据，通过常用的模型估计算法e m ( e x p e c t a t i o n m a x i m i z a t i o n ) ( 2 2 进行标记 估计和模型参数估计，从而把混合分布识别出来，只要每个分布有一个已标注 样本就可以估计该混合模型。生成模型已经被成功地应用到文本分类中 3 6 1 ，并 且此方法比只在己标注数据样本上学习时效果更好。此类算法可以看成是在少 量有标记示例周围进行聚类，是早期直接采用聚类假设的做法。该方法的缺点 是，如果模型族过小不足以描述数据的类条件分布时，效果会非常差。而且， e m 算法常常只需要很少的循环就会给未标注样本非常确定的概率标签。这使得 在后面的循环中，大量的未标注样本的作用掩盖了标注样本的作用。 2 1 2 自训练 自训练( s e l f - t r a i n i n g ) 【2 2 】也叫自学习或者自标注，是半监督学习常用到的 技术。在自训练中首先使用监督学习方法，用少量的已标注数据来训练分类器， 接着用该分类器对未标注数据分类。然后把预测的信度较大的未标注数据连同 它们的预测标注一起加到训练集中。分类器再重新训练，并且重复该过程。分 类器使用自己的预测来指导学习，这个过程在一些研究中也被称作自指导 ( s e l f - t e a c h i n g ) ，或者步步为营( b o o t s t r a p p i n g ) 。 可以想象到，对一个数据样本的分类错误在重复训练过程中可能会被加强， 这是自训练方法的一个缺点。但由于该方法比较简单并且易于理解，所以仍被 广泛的应用。自训练已经被应用到一些自然语言处理问题中3 7 】【3 8 1 。y a r o w s k y _ 3 8 】 把自训练方法应用到语义自动消歧问题( w o r ds e l i s ed i s a m b i g u a t i o n ) 中，例如： 在给定的背景下预测单词“p l a n t ”的意思是“植物”还是“工厂 。 2 1 3 直推学习 直推学习【3 9 】【4 0 1 假定未标记示例就是测试例，即学习的目的就是在这些未标 记示例上取得最佳泛化能力。换句话说，归纳学习考虑的是一个“开放世界”，即 在进行学习时并不知道要预测的示例是什么，而直推学习考虑的则是一个“封闭 世界”，在学习时已经知道了需要预测哪些示例。实际上，直推学习这一思路直 接来源于统计学习理【3 9 】，并被一些学者认为是统计学习理论对机器学习思想的 最重要的贡献。其出发点是不要通过解一个困难的问题来解决一个相对简单的 问题。vv a p n i k 认为，经典的归纳学习假设期望学得一个在整个示例分布上具 有低错误率的决策函数，这实际上把问题复杂化了，因为在很多情况下，人们 第二章相关- t 作综述 并不关心决策函数在整个示例分布上性能怎么样，而只是期望在给定的要预测 的示例上达到最好的性能。后者比前者简单，因此，在学习过程中可以显式地 考虑测试例，从而更容易地达到目的。 直推学习是一种不依赖于推广性思想的经验推理，它建立一种直接从已知 样本出发对特定的未知样本进行识别的方法和原则。由于其是从特殊到特殊的 推理，难以直接进行客观验证。因此，直到现在才开始得到人们研究的重视， 但它已经在一些领域中( 例如生物基因选择 3 4 】，数字识b i je 3 3 1 ) 取得了初步结果， 甚至表现出了比传统归纳更好的性能。 2 1 4 多视图学习 在现实世界中很多数据是存在天然分割的，即数据的某些属性能够在某种 角度上描绘数据的某种特征，而这些属性不是唯一的。例如网页数据中的b o d y 部分和h y p e d i n k 部分，视频数据中的视频部分和声音部分等等。传统算法在数 据的特征集上学习，并没有将数据集属性的天然可分割性考虑进来，而只利用 单个属性进行学习可能带来不可避免的错误，如只利用网页的h y p e r l i n k 部分进 行排序，就无法阻止垃圾链接对排序的影响。如果多个属性子集之间满足：第 一，每个属性集都足以描述该问题，也就是说，如果训练例足够，在每个属性 集上都足以学得一个强学习器；第二，在给定标记时，每个属性集都条件独立 于另一个属性集，那么有可能利用这种属性子集的天然划分设计出一类特殊的 半监督算法，从而达到减少标注量、缩小目标函数搜索空间和提高学习准确率 的目的，这种学习就称为多视图学习( m u l t i v i e wl e a r n i n g ) t 4 1 1 。 针对多视图问题，有一系列协同学习算法( c o l e a r n i n g a l g o r i t h m ) 被提出， 其中最为典型的就是b l u m & m i t c h e l l 2 5 】所提出的c o t r a i n i n g 算法。该算法最 初在各个属性子集上仅使用标注数据分别训练学习器，然后用这些学习器对未 标注数据进行识别，并从中挑出“最可信的样本，加入到训练集中。然后， 每个学习器就使用原有的训练样本加上其它分类器新添加的样本进行识别。这 个过程循环进行，直到全部未标注数据被识别完毕。很显然，c o t r a i n i n g 是自 训练在多视图情况下的自然推广，并且协同训练( c o t r a i n i n g ) 方法能克服自训练 中错误加强的缺点。在a b l u m 和t m i t c h e l l 提出最早的协同训练算法后，很多 研究者对其进行了研究并取得了很多进展，使得协同训练成为半监督学习中最 重要的风范( p a r a d i g m ) 之一，而不再只是一个算法。例如c o e m 1 3 】和 1 2 第二章相关工作综述 c o b o o s t 1 4 】。与c o t r a i n i n g 不同的是，c o e m 在每次循环中，通过e m 算法得 到未标注数据的含噪声的概率标签，并循环到稳定。而c o b o o s t 则是引入了 b o o s t i n g 的集成学习的方法，即优化目标是使得学习器在不同视图上给出不一致 标签的数目最少。 国外已经有人把多视图方法运用到文本分类、英语基本名词短语识别、英 语专名识别等研究上，而且取得了很不错的效果，甚至超过了传统的监督学习 方法，如d y a r o w s k y 3 8 1 在研究词义消歧时，通过同时使用词的局部上下文以及 词在文档其他部分出现时的含义这两部分信息，有效减少了对人工标注数据的 需求量；e r i l o f f 和r j o n e s 【4 2 j 在对名词短语进行地理位置