各队5v5排队时间统计贴（更新到12月20日 18/58） ... 冰风岗 Ture Windfury 暗影议会 Rank A 阿尔萨斯 Joan of Arc ...
基于1个网页-
行列式的秩
更多收起网络短语
Ranka (爛柯) or Lankeshan ji, or Rotten Axe Handle in English, is a Chinese legend similar to that of Rip Van Winkle, although it predates it by at least a 1000 years.
The exact date of origin of the legend is unknown.
以上来源于:
Domain names that contain keywords within them rank a lot higher than domains without keywords.
含有关键字眼的域名比没有关键字的域名排名靠前。
Conducted every decade since 1939, the study asks participants to rank a list of 18 characteristics they would want in a partner on a scale ranging from "irrelevant" to "essential."
该研究自1939年起每十年开展一次，主要让研究对象对18个择偶标准按照“无关紧要”到“非常重要”的标准进行排序。
Barkley's studio cohorts ridiculed him, wondering how he could rank a team that has yet to win a single title ahead of the three-peating Shaq and Kobe squad.
因此在我们分析湖人之前，我们先看看这三支球队，看看他们除了夺得总冠军外需要做到些什么才能超越他们的前辈。
You are no longer a captive but wear the metal of great rank among their people.
VOA: special.
A gentleman had class, rank, and status, and you better recognize it.
有一定阶级,地位,等级,还要被人认可
For a driver, for instance, when I ask you to rank how good you are as a driver, what people often do is they think--they say, "I'm better than average," but what they do is they focus on one aspect of their driving.
例如，拿司机来说，当我叫人们给自己的开车技术打个分时，人们通常会认为，“我比一般人好”,但其实他们只看到了开车的一个方面。
Meanwhile, the Pentiums rank a touch higher with 3MB of L3 cache, HD graphics and processors that clock at 2.5GHz on the low end to 3.2GHz on the high end.
In compiling this list, we concluded that the best way to rank a coach relative to his peers is not to do so based on the number of wins and loses alone, but instead on how much a coach wins and losses as compared to the resources he has.
Nontando Vena is a Vodacom promoter who spends a lot of time at a taxi rank in a township called Soshanguve, north of Johannesburg.
$firstVoiceSent
- 来自原声例句
请问您想要如何调整此模块？
感谢您的反馈，我们会尽快进行适当修改！
请问您想要如何调整此模块？
感谢您的反馈，我们会尽快进行适当修改！Interactions Rank&挖掘用户的社交图谱
PageRank是Google十年前提出的一种网页评级方法，也是Google用来衡量一个网站质量好坏的重要因素。利用PageRank，Google不断地改善搜索结果的排序，打造出目前最受欢迎的搜索引擎。相继搜索业的蓬勃发展，互联网领域又出现了一只新秀——社会网络(SNS)。如今，Facebook几乎代表了SNS的领航者。在F8大会上，来自Facebook的工程师介绍了关于news feed的算法，称之为Edge rank。Edge rank考虑了SNS网站用户之间的交互行为和交互的时效性，从而计算新鲜事出现权重，达到优化新鲜事排序、以及改变仅按时间排序的现状的目的。Edge rank算法的好坏还需要时间来验证。
Interactions Rank是Google的科学家最新提出的一种基于用户交互的社交图谱分析算法【1】，它定义用户与好友圈子之间的交互类别，并对不同的交互行为进行打分，找出与用户最亲密的好友圈子。
在Interactions Rank算法框架下，社交图谱用带权值的有向图来表示。图的节点代表用户，图的边代表用户之间的交互关系。考虑到用户之间的交互有主动和被动之分，图的边定义为带方向的，并且不同的方向有不同的权重。
从上面的计算公式中可以看出，Interactions Rank主要考虑了以下三方面的因素：
交互频率：用户与好友圈的交互频率越高，代表该好友圈相对用户的权重越大。
交互的时效性：好友圈的权重随着时间不断变化。
交互的方向：用户主动与好友交互要比被动交互对Interactions Rank产生的影响大。
总之，Interactions Rank从用户的一组交互数据中计算而来，其中和分别表示好友圈子对该用户和该用户对好友圈子发起的互动行为。是当前时间，是发生交互行为的时间戳。可以调节时间因素对Interactions Rank的影响大小，可见，时间对Interactions Rank的影响是呈指数型衰减的。
好友推荐是SNS网站帮助用户拓展人脉关系的有效途径，Interactions Rank为好友推荐提供了很好的依据。推荐引擎需要分析用户的社交关系，找到用户最可能认识的人。在拓展用户的好友圈子中，Interactions Rank作为重要因素来衡量与用户发生交互的人之间的相关度，相关度越高，被推荐的概率越大。
Interactions Rank的方法已被Google的电子邮件服务用来为用户推荐可能的收件人。当用户撰写一封电子邮件，在填写收件人名单时，推荐引擎会根据当前填写的名单为邮件撰写人推荐更多的收件人。其原理就是基于 Interactions Rank，对已填写的收件人群组进行扩充。该方法还被用来对用户的收件人列表进行纠错，对拼写错误的收件人地址提供修改建议。
【1】, Maayan Roth, Tzvika Barenholz, Assaf Ben-David, David Deutscher, Guy Flysher, Avinatan Hassidim, llan Horn, Ari Leichtberg, Naty Leiser, Yossi Matias, Ron Merom, International Conference on Machine Learning (ICML), 2011.
InfoQ相关内容：
文章：社会化推荐在人人网的应用
作者简介：张叶银，毕业于中科院自动化所，目前担任人人网Social Graph算法工程师，主要负责Social Graph算法的研发，感兴趣的方向主要有大规模数据挖掘机器学习的应用及社会化计算。
Copyright (C) , All Rights Reserved.
版权所有 闽ICP备号
processed in 0.040 (s). 12 q(s)君，已阅读到文档的结尾了呢~~
基于p-rank的rdf有向图的分布式存储
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
基于p-rank的rdf有向图的分布式存储
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer--144.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口 上传我的文档
 下载
 收藏
桥梁工程专业工程师，硕士学历，擅长桥梁设计，结构有限元分析，岩土分析计算。
 下载此文档
正在努力加载中...
改进LeaderRank算法的意见领袖挖掘
下载积分：350
内容提示：改进LeaderRank算法的意见领袖挖掘
文档格式：PDF|
浏览次数：22|
上传日期： 04:45:32|
文档星级：
全文阅读已结束，如果下载本文需要使用
 350 积分
下载此文档
该用户还上传了这些文档
改进LeaderRank算法的意见领袖挖掘
官方公共微信当前位置： >>
基于内容的图像搜索重排序研究
中国科学技术大学 博士学位论文 基于内容的图像搜索重排序研究 姓名：田新梅 申请学位级别：博士 专业：信号与信息处理 指导教师：吴秀清
中国科学技术大学博士学位论文摘要摘要随着瓦联网技术和网络共享服务的发展，网络上的视频／图像数据呈几何级 数增
长。为了满足大量用户的搜索需求，建立快速有效的视频／图像搜索系统成 为迫切需要解决的问题。为了借鉴文本搜索中的成熟技术并满足搜索对高效性的 要求，目前大多数的商业搜索引擎（Ｂｉｎｇ，Ｇｏｏｇｌｅ，Ｙａｈｏｏ，Ｂａｉｄｕ等）对视频和图像 的搜索主要是通过索引其相关的文本信息。由于这些文本信息不足以全面充分地 描述视频／图像中富的视觉内容，基于文本的视频／图像搜索结果不尽如人意。重 排序被提出在基于文本的搜索结果基础上，通过加入视频／图像视觉信息、用户 反馈等知识改进搜索结果。 目前的重排序方法已经取得了一定进展，然而由于低层特征和高层语义概念 之间的语义鸿沟的存在，视频／图像搜索罩排序中还有很多问题需要研究。本论 文首先提出了无监督的贝叶斯重排序算法，接着分析了将重排序应用到实际系统 中的几个关键问题，最后提出了有用广反馈情况下的半监督丰动重排序方法和基 于结构学习的有监督主题多样化重排序方法。本文埘基。Ｊ：内容的重排序方法进行 了深入研究，主要ｊＩ：作和创新之处归纳为以卜几点： １．本文在分析视觉信息和文本信息在重排序中的本质作用基础上，从贝叶斯 角度将这两种信息分别看作是先验和似然提出了贝叶斯重排序。贝叶斯重 排序是一个通用的重排序框架，很多现有重排序算法都可以统一到该框架 下。针对现有算法对视觉信息和文本信息的描述中存在的问题，分别提出 了局部学习正则化模型和基于点对的偏好强度重排序距离。在标准数据集 上的人量实验验证了本文提出的方法的有效性。 ２．重排序研究的最终日的是成功地将其应用到实际的搜索系统中有效提高基 于文本的视频／图像搜索结果。本文从多方面探讨将重排序应用到实际的 图像搜索系统中的关键问题，对这些问题的讨论不仅对于将来重排序的实 际应用有重要意义，对我们进一步的研究工作也有指导意义。本文从算法、 特征表达、计算复杂度等方血提炼了六个关键问题，并从三个常用的商、Ｉｋ 搜索引擎中搜集了一个网络图像数据集，在该数据集上进行了大量的实验， 通过对这些实验结果的分析和总结，给出了这八个问题的答案。．Ｉ．中国科学技术大学博士学位论文摘要３．无髓督的重排序为所有的用户返回一样的查询结果，因此不能满足不同用 户的刁ｉ同搜索需求，尤其是在用户的查询词指代不明的情况下。研究表明 相关反馈是解决这一问题的有效途径，但是现有的基于用户交互的重排序 方法不能很好地从用户反馈中准确学习用户的搜索意图。为了解决这一问 题，本文提出了半监督的主动重排序方法，该方法首先通过人机交互获得 用户的标注信息，在此基础上利用子空间学习算法区分与用户查询相关和 不相关的图像。在学习用户的真正搜索意图过程中，为了减少用户的标注 量提出了一种基于结构信息的样本主动选择方案；为了学习反映与用户查 询相‘关的图像予空『开Ｊ提出了一种局部一整体区分式了空问学习算法。在人工 数据集和网络图像搜索数据集上的实验表明本文提出的主动重排序方法可 以有效学习用户的搜索意图，返回满足用户需求的结果。 ４．在图像搜索中，用户希望返回的结果同时具有高相关性和高丰题覆盖性。 主题多样化重排序受到越来越多的重视，但足现有的多样化重排序方法受 到两方面的限制。首先，这些方法对相关性和多样性的优化是分两步进行 的，凶此得不到联合最优的结果：另一方而这些方法普遍使用视觉多样性 来近似丰题多样性，由于语义鸿沟的存在，这一方法很难得到好的结果。针 对这些问题，本文提出了联合优化相关性和主题多样性的主题多样化重排 序。该方法在结构学习框架下设计了一组特征来描述排序结果的相关性和 多样性，然后利用用户标注信息，从一组训练数据中学习得到主题多样化 重排序模型。利用该模型，可以对未标沣的查询进行预测得到高相关性和 高主题多样性的重排序结果。在网络图像搜索数据集上的实验表明本文提 出的方法可以同时提高相关性和主题多样性。关键词：图像搜索，基于内容的重排序，贝叶斯重排序，视觉一致性，排序距离， 主动重排序，主动样本选择，子窄问学习，主题多样化重排序，相关性重排序，结 构学习中国科学技术大学博士学位论文英文摘要ＡｂｓｔｒａｃｔＷｉｔｈｔｈｅ ｒａｐｉｄ ｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ｒｅｃｏｒｄｉｎｇ ａｎｄ ｓｔｏｒａｇｅ ｄｅｖｉｃｅｓ，ａｓ ｗｅｌｌ ａｓ ｔｈｅｓｉｇｎｉｆｉｃａｎｔ ｉｍｐｒｏｖｅｍｅｎｔ ｏｆ ｔｒａｎｓｍｉｓｓｉｏｎ ａｎｄ ｃｏｍｐｒｅｓｓｉｏｎ ｔｅｃｈｎｉｑｕｅｓ，ｔｈｅ ａｍｏｕｎｔ ｏｆ ｍｕｌｔｉｍｅｄｉａｄａｔａ（ｅ．ｇ．，ｉｍａｇｅ，ｖｉｄｅｏａｎｄａｕｄｉｏ）ｏｎＩｎｔｅｒｎｅｔ ｉｎｃｒｅａｓｅｓ ｅｘｐｌｏｓｉｖｅｌｙａｎｄｔｈｅｖｉｄｅｏ／ｉｍａｇｅ－ｓｈａｒｉｎｇｗｅｂｓｉｔｅｓ ｂｅｃｏｍｅ ｍｏｒｅ ａｎｄ ｍｏｒｅ ｐｏｐｕｌａｒ．Ｅｆｆｉｃｉｅｎｔａｒｅａｎｄ ｅｉｆｅｃｔｉｖｅ ｍｕｌｔｉｍｅｄｉａ ｓｅａｒｃｈ ｔｏｏｌｓ ｒｅｑｕｉｒｅｍｅｎｔ ｏｆ ｈｉｇｈ ｅｆｆｉｃｉｅｎｃｙｅｓｓｅｎｔｉａｌ ｆｏｒＷｅｂｓｕｒｆｉｎｇ．ＤＨｅ ｔｏ ｔｈｅａｎｄｔｈｅ ｌｅｖｅｒａｇｅ ｏｆ ｓｕｃｃｅｓｓｆｕｌ ｔｅｃｈｎｉｑｕｅｓ ａｌｒｅａｄｙ ｄｅ－ ｆｒｅｑｕｅｎｔｌｙ－ｅｍｐｌｏｙｅｄ ｉｍａｇｅ ｓｅａｒｃｈ ｅｎｇｉｎｅｓ，ｅ．ｇ．ｖｅｌｏｐｅｄ ｉｎ ｔｅｘｔ ｓｅａｒｃｈ，ｍｏｓｔ ｏｆｏｕｒＢｉｎｇ，Ｇｏｏｇｌｅ，Ｙａｈｏｏ ａｎｄ Ｂａｉｄｕ，ａｒｅ ｉｍｐｌｅｍｅｎｔｅｄ ｂｙ ｉｎｄｅｘｉｎｇ ａｎｄ ｓｅａｒｃｈｉｎｇ ｔｈｅ ｉｍａｇｅｓ’ａｓｓｏｃｉａｔｅｄ ｔｅｘｔｕａｌ ｉｎｆｏｒｍａｔｉｏｎ，ｅ．ｇ．，ｉｍａｇｅ ｆｉｌｅ ｎａｍｅｓ，ＵＲＬｓ，ｓｕｒｒｏｕｎｄｉｎｇｔｅｘｔｓ ａｎｄＳＯｏｎ．Ｈｏｗｅｖｅｒ，ｔｈｉｓ ｔｅｘｔ－ｂａｓｅｄ ｉｍａｇｅ ｓｅａｒｃｈ ｒｅｓｕｌｔ ｉｓ ｎｏｔ ｓａｔｉｓｆａｃｔｏｒｙｂｅｃａｕｓｅ ｔｈａｔ ｔｈｅ ｔｅｘｔｕａｌ ｉｎｆｏｒｍａｔｉｏｎ ｉｓ ｎｏｔ ｔｈｅ ｅｓｓｅｎｔｉａｌ ｄｅｓｃｒｉｐｔｉｏｎ ｏｆ ｉｍａｇｅ’Ｓ ｒｉｃｈ ｃｏｎｔｅｎｔ．Ｒｅｒａｎｋｉｎｇ ｉｓ ｔｈｅｎ ｐｒｏｐｏｓｅｄ ｔｏ ｒｅｆｉｎｅ ｔｈｉｓ ｔｅｘｔ―ｂａｓｅｄ ｓｅａｒｃｈ ｒｅｓｕｌｔ ｂｙ ｉｎｃｏｒｐｏｒａｔｉｎｇ ｉｍａｇｅｓ’ｖｉｓｕａｌ ｉｎｆｏｒｍａｔｉｏｎ，ｕｓｅｒ ｆｅｅｄｂａｃｋ Ａｌｔｈｏｕｇｈａｒｅ ａａｎｄｏｔｈｅｒ ｉｎｆｏｒｍａｔｉｏｎ．ｌｏｔ ｏｆ ｗｏｒｋｓ ｈａｖｅ ｂｅｅｎ ｄｏｎｅｏｎｉｍａｇｅ ｓｅａｒｃｈ ｒｅｒａｎｋｉｎｇ，ｔｈｅｒｅｓｔｉｌｌ ｍａｎｙ ｐｒｏｂｌｅｍｓ ｎｅｅｄ ｔｏ ｂｅ ｓｏｌｖｅｄ，ｄｕｅ ｔｏ ｔｈｅ ｓｅｍａｎｔｉｃ ｇａｐ ｂｅｔｗｅｅｎ ｌｏｗ－ｌｅｖｅｌ ｖｉｓｕａｌ ｆｅａｔｕｒｅｓ ａｎｄ ｈｉｇｈ－ｌｅｖｅｌｐｒｏｐｏｓｅａｎｓｅｍａｎｔｉｃ ｒｅｒａｎｋｉｎｇｃｏｎｃｅｐｔｓ．Ｉｎ ｔｈｉｓ ｔｈｅｓｉｓ，ｗｅ ｆｉｒｓｔ ｍｅｔｈｏｄ，ａｎｄ ｔｈｅｎ ｄｉｓｔｉｌｌ ｓｉｘ ｍｏｓｔａｕｎｓｕｐｅｒｖｉｓｅｄ Ｂａｙｅｓｉａｎｉｍｐｏｒｔａｎｔ ｐｒｏｂｌｅｍｓ ｗｈｉｃｈ ｓｈｏｕｌｄ ｂｅ ｃａｒｅｆｕｌｌｙ ｃｏｎｓｉｄｅｒｅｄ ｉｎ ｓｙｓｔｅｍ，ｆｉｎａｌｌｙ ｐｒｏｐｏｓｅｄ ｓｅｍｉ?ｓｕｐｅｒｖｉｓｅｄ ａｃｔｉｖｅｐｒａｃｔｉｃａｌｕｓｅｒｒｅｒａｎｋｉｎｇｒｅｒａｎｋｉｎｇｗｉｔｈｆｅｅｄｂａｃｋ ａｎｄｓｔｒｕｃｔｕｒａｌ ｌｅａｒｎｉｎｇ ｂａｓｅｄ ｓｕｐｅｒｖｉｓｅｄ ｔｏｐｉｃ－ａｗａｒｅ ｒｅｒａｎｋｉｎｇ ｍｅｔｈｏｄ．Ｔｈｉｓ ｔｈｅｓｉｓ ｃｏｎｄｕｃｔｓａｄｅｅｐ ｒｅｓｅａｒｃｈｏｎｒｅｒａｎｋｉｎｇ ａｎｄ ｏｂｔａｉｎｓ ｔｈｅ ｆｏｌｌｏｗｉｎｇ ａｃｈｉｅｖｅｍｅｎｔｓ：１．Ｂｙ ｍｌａｌｙｚｉｎｇ ｔｈｅ ｉｎｔｒｉｎｓｉｃ ｒｏｌｅｓ ｏｆ ｔｈｅ ｔｅｘｔｕａｌａｎｄｖｉｓｕａｌ ｉｎｆｏｒｍａｔｉｏｎ ｉｎｃｕｅｓ ａｒｅｒｅｒａｎｋｉｎｇ，ｗｅ ｐｒｏｐｏｓｅ Ｂａｙｅｓｉａｎ ｒｅｒａｎｋｉｎｇ ｉｎ ｗｈｉｃｈ ｔｈｅ ｔｗｏｍｏｄ―ｅｌｅｄ ａｓ ａｓ ｐｒｉｏｒ ａｎｄ ｌｉｋｅｌｉｈｏｏｄ ｒｅｓｐｅｃｔｉｖｅｌｙ ｆｒｏｍ ｐｒｏｂａｂｉｌｉｓｔｉｃ ｐｅｒｓｐｅｃｔｉｖｅ． Ｂａｙｅｓｉａｎ ｒｅｒａｎｋｉｎｇ ｉｓａｎｇｅｎｅｒａｌ ｆｒａｍｅｗｏｒｋ ａｎｄｃａｎｕｎｉｆｙ ｓｅｖｅｒａｌ ｅｘｉｓｔｉｎｇｒｅｒａｎｋｉｎｇ ｍｅｔｈｏｄｓ．Ｔｏ ｗｅｌｌ ｍｏｄｅｌ ｔｈｅ ｔｅｘｔｕａｌ ａｎｄ ｖｉｓｕａｌ ｉｎｆｏｒｍａｔｉｏｎ ｉｎＢａｙｅｓｉａｎ ｒｅｒａｎｋｉｎｇｆｒａｍｅｗｏｒｋ．ｗｅ ａｌｓｏ ｐｒｏｐｏｓｅ ｔｏａｕｓｅ ａｌｏｃａｌ ｌｅａｒｎｉｎｇ ｒｅｇｕ－ｌａｒｉｚｅｒ ｔｏ ｍｏｄｅｌ ｖｉｓｕａｌ ｃｏｎｓｉｓｔｅｎｃｙ ａｎｄｐａｉｒ－ｗｉｓｅ ｐｒｅｆｅｒｅｎｃｅ ｓｔｒｅｎｇｔｈ ｒａｌｌｋ―ｏｎｉｎｇ ｄｉｓｔｍｉｃｅ ｒｅｓｐｅｃｔｉｖｅｌｙ．Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔｓ ｃｏｎｄｕｃｔｅｄｂｅｎｃｈｍａｒｋ ｄａｔａｓｅｔｓ．．ＩＩＩ．．ｈａｖｅ ｄｅｍｏｎｓｔｒａｔｅｄ ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ Ｂａｙｅｓｉａｎ ｒｅｒａｎｋｉｎｇ ｍｅｔｈｏｄ． ２?Ｔｏ ｉｎｃｏｒｐｏｒａｔｅ ｒｅｒａｎｋｉｎｇ ｔｅｃｈｎｉｑｕｅ ｉｎｔｏ ｐｒａｃｔｉｃａｌ ｉｍａｇｅ ｓｅａｒｃｈ ｓｙｓｔｅｍ，ｔｈｅｒｅａｌｅｓｅｖｅｒａｌ ｉｓｓｕｅｓ ｗｈｉｃｈ ｗｉｌｌ ｇｒｅａｔｌｙ ｉｎｆｌｕｅｎｃｅ ｔｈｅ ｒｅｒａｎｋｉｎｇ ｐｅｒｆｏｒｍａｎｃｅ．ｂｅｓｉｄｅｓ ｔｈｅ ｒｅｒａｎｋｉｎｇ ａｌｇｏｒｉｔｈｍ ｄｅｓｉｇｎ．Ｔｈｉｓ ｔｈｅｓｉｓ ｄｉｓｔｉｌｌｓ ｓｉｘ ｍｏｓｔ ｉｍｐｏｒ．ｔａｎｃｅ ｐｒｏｂｌｅｍｓ ｗｈｉｃｈ ｓｈｏｕｌｄ ｂｅ ｃａｒｅｆｕｌｌｙｃｏｎｓｉｄｅｒｅｄ ｉｎａｐｒａｃｔｉｃａｌ ｒｅｒａｎｋｉｎｇｓｙｓｔｅｍ?ｔｈｅ ｓｉｘ ａｓｐｅｃｔｓ ｉｎｃｌｕｄｅ ａｌｇｏｒｉｔｈｍ ｓｅｌｅｃｔｉｏｎ，ｅｆｆｅｃｔｉｖｅ ｖｉｓｕａｌ ｆｅａｔｕｒｅ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ，ｅｆｆｉｃｉｅｎｔ ｆｅａｔｕｒｅ ｅｘｔｒａｃｔｉｏｎ，ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｓｔ，ｔｈｅｃｈａｒ瓣ｔｅｒｉｓｔｉｃｓ ｏｆ ｔｈｅ ｔｅｘｔ―ｂａｓｅｄ ｒｅｒａｎｋｉｎｇ，ａｎｄ ｔｈｅ ｕｔｉｌｉｚａｔｉｏｎ ｏｆ ｔｈｅ ｔｅｘｔ．ｂａｓｅｄｓｅａｒｃｈ ｒｅｓｕｌｔｓ．Ｔｈｅｉｒ ｅｆｆｅｃｔｓｌｙｚｅｄ ｂａｓｅｄｏｎｔｏ ｔｈｅ ｒｅｓｕｌｔｉｎｇ ｒｅｒａｎｋｉｎｇ ｐｅｒｆｏｒｍａｎｃｅ ａｒｅ ａｎ舡Ｏｉｌ ａｃｏｍｐｒｅｈｅｎｓｉｖｅ ｅｘｐｅｒｉｍｅｎｔｓｄａｔａｓｅｔ ｃｏｌｌｅｃｔｅｄ ｆｒｏｍ ｔｈｒｅｅ ｂｅｌｉｅｖｅ ｔｈａｔ ｔｈｅｓｅｍｏｓｔ ｆｒｅｑｕｅｎｔｌｙ。ｕｓｅｄ ｃｏｍｍｅｒｃｉａｌ ｉｍａｇｅ ｓｅａｒｃｈｅｎｇｉｎｅｓ．Ｗｅａｎａｌｙｓｉｓ ａｎｄ ｉｎｓｉｇｈｔｆｕｌ ｆｉｎｄｉｎｇｓ ｗｉｌｌ ｐｒｏｖｉｄｅ ｕｓｅｆｕｌ ｇｕｉｄｅｌｉｎｅｓ ｆｏｒ ｔｈｅ ｐｒａｃｔｉｃａｌ ａｐｐｌｉｃａｔｉｏｎ ａｎｄ ｆｕｒｔｈｅｒ ｒｅｓｅａｒｃｈｏｎＷｅｂｉｍａｇｅ ｓｅａｒｃｈ ｒｅｒａＩｌｋｉｎｇ． ｓｅａｒｃｈ ｉｎｔｅｌｌｔｉｏｎｓ３?ｕｎｓｕｐｅｒｖｉｓｅｄ ｒｅｒａｎｋｉｎｇ ｍｅｔｈｏｄｓ ｆａｉｌ ｔｏ ｃａｐｔｕｒｅ ｔｈｅｕｓｅｒ’Ｓｗｈｅｎ ｔｈｅ ｑｕｅｒｙ ｔｅｒｍ ｉｓ ａｍｂｉｇｕｏｕｓ．Ｒｅｌｅｖａｎｃｅ ｆｅｅｄｂａｃｋ ｈａｓ ｂｅｅｎ ｐｒｏｖｅｎ ｔｏ ｂｅａｎｅｆｆｅｃｔｉｖｅ ｗａｙ ｔｏ ｓｏｌｖｅ ｔｈｉｓ ｐｒｏｂｌｅｍ．Ｈｏｗｅｖｅｒ，ｃｕｒｒｅｎｔ ｗＤｒｋｕｓｅｒｏｎｒｅｒａＩｌｋ．１ｎｇ ｗｉｔｈｉｎｔｅｒａｃｔｉｏｎｃａｎｎｏｔｌｅａｒｎ ｔｈｅｕｓｅｒ’ｓｉｎｔｅｎｔｉｏｎ ｐｒｅｃｉｓｅｌｙ．Ｔｈｉｓｔｈｅｓｉｓ ｐｒｏｐｏｓｅｓ ｓｅｍｉ。ｓｕｐｅｒｖｉｓｅｄ ａｃｔｉｖｅ ｒｅｒａｎｋｉｎｇ ｍｅｔｈｏｄｓ ｔｏ ｌｅａｒｎ ｌｌｓｅ’ｓ ｉｎ． ｔｅｎｔｉｏｎ ｍｏｒｅ ｅｘｔｅｎｓｉｖｅｌｙ ａｎｄ ｃｏｍｐｌｅｔｅｌｙ．Ｔｈｉｓ ｍｅｔｈｏｄ ｆｒｓｔ ｏｂｔａｉｎ ｔｈｅｕｓｅｒ＇ｓｌａｂｅｌｉｎｇ ｉｎｆｏｒｍａｔｉｏｎ ｂｙ ｉｎｔｅｒａｃｔｉｎｇ ｗｉｔｈ ｕｓｅｒｓ，ａｎｄ ｔｈｅｎ ｌｅａｎｌ ｔｈｅ ｔｅｎｔｉｏｎｕｓｅｒ，ｓｉｎ－ｂｙｄｉｓｔｉｎｇｕｉｓｈｉｎｇ ｒｅｌｅｖａｎｔ ｉｍａｇｅｓ ｆｒｏｍ ｉｒｒｅｌｅｖａｎｔａｏｎｅｓｖｉａ ｓｕｂｓｐａｃｅｌｅａｒｎｉｎｇ．Ｆｕｒｔｈｅｒｍｏｒｅ，ｔｈｉｓ ｔｈｅｓｉｓ ｐｒｏｐｏｓｅｓｓｔｒｕｃｔｕｒａｌ ｉｎｆｏｒｍａｔｉｏｌｌ ｂａｓｅｄａｓａｍｐｌｅ ｓｅｌｅｃｔｉｏｎ ｓｔｒａｔｅｇｙ ｔｏ ｒｅｄｕｃｅ ｔｈｅ ｌａｂｅｌｉｎｇ ｅｆｆｏｒｔｓ ａｎｄｎｏｖｅｉｌｏｃ“ｕｓｅｒ＇ｓｇｌｏｂａｌ ｄｉｓｃｒｉｍｉｎａｔｉｖｅ ｄｉｍｅｎｓｉｏｎ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｔｏ ｌｏｃａｌｉｚｅ ｔｈｅ ｉｎｔｅｎｔｉｏｎ ｉｎ ｔｈｅ ｖｉｓｕａｌ ｆｅａｔｕｒｅ ｓｐａｃｅ．Ｅｘｐｅｒｉｍｅｎｔｓ ｃｏｎｄｕｃｔｅｄ ｔｈｅｔｉｃ ｄａｔａｓｅｔｓ ａｎｄｏｎｂｏｔｈ ｓｙｎ－Ｗｅｂｉｍａｇｅ ｓｅａｒｃｈ ｄａｔａｓｅｔ ｄｅｍｏｎｓｔｒａｔｅ ｔｈｅ ｅｆｆｅｃｔｉｖｅＩｌｅｓｓｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｃｔｉｖｅ ｒｅｒａｎｋｉｎｇ ｍｅｔｈｏｄ． ４?Ｉｎ ｉｍａｇｅ ｓｅａｒｃｈ，ｔｈｅ ｄｅｓｉｒｅｄ ｒｅｓｕｌｔ ｓｈｏｕｌｄ ｓａｔｉｓｆｙ ｂｏｔｈ ｈｉｇｈ ｒｅｌｅｖａｎｃｅ ａｎｄ ｈｉｇｈ ｔｏｐｉｃ ｄｉｖｅｒｓｉｔｙ．Ｔｏｐｉｃ ｄｉｖｅｒｓｅ ｒｅｒｍｌｋｉｎｇ ｈａｓ ｄｒａｗｎ ｉｎｃｒｅａｓｉｎｇ ａｔｔｅｎｔｉｏｎｓ． Ｈｏｗｅｖｅｒ，ｅｘｉｓｔｉｎｇ ｄｉｖｅｒｓｉｆｉｅｄ ｒｅｒｍｌｋｉｎｇ ｌｎｅｔｈｏｄｓ ｓｕｆｆｅｒ ｆｒｏ，ｎ ｔｗｏ ｐｒｏｂｌｅＩｎｓ． 一ＩＶ．中国科学技术大学博士学位论文英文摘要Ｆｉｒｓｔ．ｔｈｅ ｍａｘｉｍｉｚａｔｉｏｎ ｏｆ ｄｉｖｅｒｓｉｔｙ ａｎｄ ｒｅｌｅｖａｎｃｅ ｉｓ ｐｅｒｆｏｒｍｅｄ ｉｎ ｔｗｏ－ｓｔｅｐ， ｗｈｉｃｈ ｔｙｐｉｃａｌｌｙ ｗｉｌｌ ｎｏｔ ａｃｈｉｅｖｅ ｔｈｅｊｏｉｎｔ ｏｐｔｉｍｕｍ．Ｓｅｃｏｎｄ，ｖｉｓｕａｌｄｉｖｅｒｓｉｆｉｃａ－ｔｉｏｎ．ｗｈｉｃｈ ｉｓ ｕｓｅｄ ｉｎ ｄｉｖｅｒｓｉｆｉｅｄ ｒｅｒａｎｋｉｎｇ，ｕｓｕａｌｌｙ ｃａｎｎｏｔ ｗｅｌｌ ａｐｐｒｏｘｉｍａｔｅ ｔｈｅ ｔｏｐｉｃ ｄｉｖｅｒｓｉｔｙ ｄｕｅ ｔｏ ｔｈｅ ｓｅｍａｎｔｉｃ ｇａｐ．Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｗｅ ｐｒｏｐｏｓｅ ｔｏｐｉｃ。ａｗａｒｅ ｒｅｒａｎｋｉｎｇ ｗｈｉｃｈｊｏｉｎｔｌｙ ｍａｘｉｍｉｚｅｓｔｈｅ ｒｅｌｅｖａｎｃｅ ａｎｄ ｔｏｐｉｃ ｄｉｖｅｒｓｉｔｙ．ａｒｅＴｈｒｏｕｇｈａｓｔｒｕｃｔｕｒｅｄ ｌｅａｒｎｉｎｇ ｆｒａｍｅｗｏｒｋ，ｔｈｅ ｒｅｌｅｖａｎｃｅ ａｎｄ ｄｉｖｅｒｓｉｔｙａｍｏｄｅｌｅｄ ｂｙｓｅｔ ｏｆ ｃａｒｅｆｕｌｌｙ ｄｅｓｉｇｎｅｄｆｅａｔｕｒｅｓ，ａｎｄ ｔｈｅｎ ｌｅａｒｎｅｄ ｆｒｏｍ ｈｕ?ｏｎ ａｍａｎ ｌａｂｅｌｅｄ ｔｒａｉｎｉｎｇ ｓａｍｐｌｅｓ．Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔｓ ｃｏｎｄｕｃｔｅｄｗｅｂ ｉｍａｇｅｓｅａｒｃｈ ｄａｔａｓｅｔ ｄｅｍｏｎｓｔｒａｔｅ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈｏｄ ｎｏｔ ｏｎｌｙ ｉｍｐｒｏｖｅｓ ｔｈｅ ｄｉｖｅｒｓｉｆｉｅｄ ｒｅｒａｎｋｉｎｇ ｍｅｔｈｏｄｓ ｂｕｔ ａｌｓｏ ｔｏｐｉｃ ｃｏｖｅｒａｇｅ ｃｏｍｐａｒｅｄ ｗｉｔｈ ｅｘｉｓｔｉｎｇ ｉｍｐｒｏｖｅｓ ｔｈｅ ｒｅｌｅｖａｎｃｅｃｏｍｐａｒｅｄｗｉｔｈｒｅｌｅｖａｎｃｅ－ｂａｓｅｄｒｅｒａｎｋｉｎｇ ｍｅｔｈｏｄｓ．ＫｅｙＷｏｒｄｓ：ｉｍａｇｅ ｓｅａｒｃｈ，ｃｏｎｔｅｎｔ―ｂａｓｅｄｒｅｒａｎｋｉｎｇ，Ｂａｙｅｓｉａｎ ｒｅｒａｎｋｉｎｇ，ｖｉｓｕａｌｃｏｎｓｉｓｔｅｎｃｙ，ｒａｎｋｉｎｇ ｄｉｓｔａｎｃｅ，ａｃｔｉｖｅ ｒｅｒａｎｋｉｎｇ，ａｃｔｉｖｅ ｓａｍｐｌｅ ｓｅｌｅｃｔｉｏｎ，ｓｕｂｓｐａｃｅ ｌｅａｒｎｉｎｇ，ｔｏｐｉｃ―ａｗａｒｅ ｒｅｒａｎｋｉｎｇ，ｒｅｌｅｖａｎｔ ｒｅｒａｎｋｉｎｇ，ｓｔｒｕｃｔｕｒａｌ ｌｅａｒｎｉｎｇ―Ｖ．中国科学技术大学博上学位论文插图目录插图目录１．１以赉询“ＶＲＩ！ｇｏｇｈ”为倒示意相关性霞排序和。ｉ－：ａｉ镬排序的区别……………．４１．２ｐｑ种４ｉ¨霞排序办案的力÷意吲，包括媾十线性组台的、基于聚类的、綦ｊ二分类的＿＝｝｝Ｉ皋’Ｉ：图的……．：…………………………………………………８２．１２．２冈像搜索霞排序的’般框架ｌ科…………………………………………．．１５，＇稠Ｊ哥之间Ｉ的栅Ｊ弘即离的阁校，魁表，Ｊ÷……………………………………．１９于｜｜＝Ｊ一列＆的条件先验【！｜Ⅲｉ则化ＪｌｉｉＶ．Ｊｌ刳模型农，ｊ÷……………………………１９２．３２．，Ｉ珠ｆ Ｊ＿的｛１｝Ｊ：≯韪ｉ离ｆｉ，Ｊｌ纠｝蚝叶９‘丧，ｊｉ…………………………………………２３ ２．５ ２．６２．７ ２．８强Ｊ．ｊｊ．ｉ×０Ｉ＇ｔ．＇ＪＭ．吩跆Ｉ曙的旧税Ｊ删农，Ｊ：………………………………………２４ＰＨｉｒ，Ｌｔ）（?ａｌ币ｌｌ文小搜索和：ＴＲＥＣ＼ｉＩＤ ２００５．２００７ｔ｛Ｉ Ｊ（７２个给ｉｆ｛Ｊ Ｉ：的ＡＰ．……．．３１Ｐａｉｌ，一Ｌｏ（?ａｌ｛ｆ４ｊ刚Ｋ卜＋的。史验效粜｝｜｜｛线．…………………………………．３３ Ｐ｝ｌｉｌ?．Ｉ。ｏｃａｌｎ：小旧ｒ－Ｉ＇－的。芡０台放Ｊ粜曲线……………………………………３４３．１一ｉ个搜索ｒｊＩ警的艾彳ｘｊ『墅象结粜（Ｂａ∽１ｉｌ”）以及他仃ｊ通过ｉＦ｛｜｝序之后蹬论．Ｉ：能 够ｆｌｊ剑的血：Ｉ；＾ｆ＾（Ｍａｘ）…………………………………………………．３８３．２以，ｔ洵”Ｐａｕｄａ”乃侈１ｉ兜ｌＵｊｔ耵｛扎Ｊ≯－｜ｔ的｛吧觉，‘，：［’Ｉ＋ｌ－Ｉ《；设……………………．．３８３．３ ３．１ ３．５ ３．６３．７ｒｒ嘲“Ｐａｎｄａ“ｌ｛Ｊ．ｐｑ个年ｌＩ必。ｒ｛：葛级（内，，；扣０Ｉ冬｛像………………………………４４ ｉ个搜索０ｌ ７绛呻０史小搜韶结粜…………………………………………４５ ＬｉⅥ、搜索?ｊＩ够ｌ‘。（ｊ神ｔ乒：排Ｊ－｝强法（Ｉ＇，ｊＭＮＤＣＧ比较．………………………．．４７ Ｊ古ｊ‘点州Ｖ，Ｊ４１１＋Ｊｊ二捌ｉ离（１）ｎｉｌ―ｗｉｓ（、）’ｊ臻ＦｔＬｆ门十１｝序翻ｉ＾？，ｉ（ｐｏｉｎｔ．一ｗｉｓ（?）的｝｜匕较……４７一：ｌ－ｑ＇ＩｒＩ』！Ｉｊ化的ｒ阱｜｝停放慢比较…………………………………………．．４８ＰａｎＬ（）（．ｎｌ干¨Ｖ沁Ｉ；ｌｌｌｌ；川ｋ的｝Ｉ。ｉ氍比较…………………………．．．………．．４９３．８ ３．９：｛．１ｆ）－Ｉ、¨｝锄ｌ卜ｆＩ：ＪＭＮＤ（１Ｇ胁。，比较…………………………………………５０个｛坐索０ｌ！皆ｌ：．１ｊＩＩＪ ｒＩｉｊ！｝Ｉｊ：；笨嫂｜、ｆ门ｉｎ｛｜ｌ Ｊ＿】ｉ｝。‘ｉ峰！ｌ匕较．…………………．５ｌ３．１１个¨币州Ｊ］二；利蔓Ｉ、¨。Ｉｉ－¨Ｉ，ｊ托糖…………………………………………．．５２一ＸＩ―中国科学技术大学博士学位论文插图目录３．１２ｉ个搜索引擎的晕排序结粜ＭＮＤＣＧ的比较……………………………．．５３３．１３缩略图特征和原；ｃｆｉ图像特｛：【｝！的重排序效果比较……………………………５４ ３．１４利Ｊ＝ｆ！ｌ了文本搜索巾排序信息的Ｐｏｉｎｔ．Ｌｏｃａｌ乖ｌＰａｉｒ―Ｌｏｃａｌ方法优ｊ：１：使用文 本搜索｛｛｝序信息的Ｌｏｃａｌ。饥。方法………………………………………．５４ｉ．１ ４．２ ４．３１．４ ．ｊ．５以食洵“ｆ（Ⅸ”为例的．卜动雨排序村ｆ柴……………………………………．．６１ 样奉代表住，Ｊ÷意图……………………………………………………．．６３夼询“Ｈｎｉｍａｌ”的棚天ｌ矧像………………………………………………．６６川ｊ‘Ｊｉ窄ｆｕＪ学爿叫：意｜｛ｆ：ｆ的３维人．‘Ｉ：数抓集………………………………．．６９人．Ｊ．：数捌集㈧，Ｊ．｝：功哦ｆｌｌ－Ｊ：≯。史验结果……………………………………．７４ 小Ｉｒｉ］３－幼样本选择旅ｆＩｌ｝｝的ＳｌＡＰ比较……………………………………．．７５１：Ｈ降维方‘＂｝Ｊ：ｆＦ／ＭＡＩ＇比较………………………………………………７７。１．６，１．７ ４．８ １．９ ，Ｉ．１（ＪＳＭＩ。．Ｐ（’Ａ’丈验纪粜……………………………………………………７８企咖“（：ｆｔＯｌ’ｇ‘－Ⅵ＋．Ｂｕｓｈ”的．ｔＦ摊ｊ≯前后结果对比…………………………．．７８ Ａ哟”ｚｆ，１）ｌａ“１１＇，Ｊ币：排睁前后结粜×ｌ比……………………………………．．７９５．１ ５．２务粕ｆ，的分脎ｔ－趁｝ｌｌｉ卡；：ｆ，Ｊ：意图……………………………………………８９ｒｔ泐”ａｐｌ＇ｌ（、”ｎｊＪ分坯ｌ：越标｝｝．…………………………………………．．９３ ＤＰｐ＝２…寸，｛ｉ狴彩ｆｒ化曩州侉１私Ｃ它ｉ曩排宁可法的纷粜比较．（ａ）（１））（（’）分 别钠毓Ｊ７ＮＤ（’Ｇ、ＮＣＴ（’平ｌｌＬｏｓｓ…………………………………………９５５．３５．Ｊ“ｊ Ｄｆ―ｐ＝１０Ｈ、Ｊ‘的｛ｔ题多样化ｊＥ排ｆ≯（’Ｉ＇ＡＲ（，ｒａｎｋ）（Ｑ’爻骀结粜以硬义本搜索的绲粜，（：Ｉ）（ｈ）（（?）分５１）ＩＪ衡馈』，ＮＤＣＧ、Ｎ（’Ｔ（’／｝：ｉｌＬｏｓｓ……………………．．９６５．５“１ Ｄ，，，，＝５ｉｔ＇］的ｉｉ题多样化帚扑Ｊ｝；（ＴＡＲｃｒａｎｋ）的’戈验纠ｉ架以及殳本搜索的纠ｉ粜．（｝Ｉ）（ＩＪ）（（‘）分）ｊ《槐！进Ｊ，ＮＤＣＧ，ＮＣＴ（、耵ＩＬｒ）ｓｓ………………………．．９６５．６每个备哟征支本搜索纠ｉ粜（Ｔｅｘｔ）和｝：题彩十丫化ｉ矗｛：｛｝＝Ｊ弘（ＴＡＲ纠‘ａｎｋ）Ｉ： 的ＮＤ（、（：千｜ｌＮＣＴ（、……………………………………………………．．９７５．７≯｝计Ⅱ“ｔｍｌ）ｙ”、“］）ａｌｌｌｌａｌｌ”羽】ｔ‘Ｃａｌｌｌｅｒａ”ｎ艾本搜索｝１１ｉ泶（１１，ｘｔ）取ｆ，ｎ～ＲｆＴａｕｋＩＲ｛ｔｔ Ｊ）＇－ＪｇＩ＇?ｌｎ，』毛‘；肄：。｝?｛｛ｌ：ｎ：Ｉｎ５ｆｏｎ０降Ｉ像的埘【匕………………………………．９８．ＸＩＩ．中国科学技术大学博士学位论文表格目录表格目录２．１ ２．２ ２．３ ２．４排序距离的简单示例数据………………………………………………．２３ １Ｊ！ＩＩＩ斯最排序桃架Ｉ、．八种力法的ＭＡＰ比较………………………………．３０Ｐａｉｒ．Ｌｏｔ?ａｌ与廷它霞排序算；Ｊ，ｆ１％ＩＡＰ［ｇ较………………………………．３１小同哥设置策略的ＭＡＰ比较……………………………………………．３３３．１ ３。２ ３．３ｉ个搜索０ｌ擎符｜，｜返｜『ｌＪＩ矧像的干｜１天?ｒ＃等级分佰……………………………４４Ｌｉｖｅ｝二缚个Ａ询蚁优的况觉特ｉｌ｝！…………………………………………５０３个搜索引擎ｉ矗排序ｄ订订的ＮＤＣＧ ｃ４．｜１）比较………………………………．５３５．１ＴＡＲ（崔ａｎｋ‘ｊ艾小于小索结粜（Ｔｅｘｔ）【匕较…………………………………．．９８．。ＸＩＩＩ．．中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。作者签名：亟貉筮签字日期：丝＆聱墨盛垒旦中国科学技术大学学位论文授权使用声明作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论义被查阅和借阅，可以将学位论义编入《中围学 位论文伞文数据库》等有关数据库进行检索，町以采用影印、缩印或扫描等复制 手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一 致。 保衔的学位论文在解密后也遵守此规定。回／丢开作者签名： 签字日期：口保密（＿年）亟施搐一．．塑＆竿！墨垒鱼导师签名：签字日期：扣２壁拿』目生垒中国科学技术大学博士学位论文第一章绪论第一章１．１绪论图像搜索重排序的研究背景和意义近年来，随着视频／图像获取存储设备、以及压缩传输技术的发展，多媒 体数据急剧增加。同时随着计算机和网络技术的快速发展，网络资源特别是 视频、数字图像的数目大幅增长；互联网技术的进一步普及和发展，使得这 些海量数据在世界范围内的共享成为可能。每天有数以万计的视频／图像数 据上传到网络上。与此Ｉ＿Ｊ时，人们已经越来越习惯于在Ｉｎｔｅｒｎｅｔ上查找各种信 息，包括文本、图像、视频和音频等。视频／图像共享网站也越来越流行，例 如Ｆｌｉｃｋｒ、Ｙｏｕｔｕｂｅ等。Ｙｏｕｔｕｂｅ、Ｔｕｄｏｕ和Ｙｏｕｋｕ网站上有数以亿计的视频，每天 有很多用户在这些网站上搜索和观看视频。据报道，Ｙｏｕｔｕｂｅ上每天的视频观看 次数多于十亿。 很多搜索引擎致力于开发快速有效的视频／图像搜索系统以满足人量用户搜 索需求。目前，Ｇｏｏｇｌｅ、Ｂｉｎｇ、Ｙａｈｏｏ等常用的商业搜索引擎已经能较好地解决 海量文本的搜索问题。借助于文本搜索巾的成熟技术，目前的视频和图像搜索 主要也是通过索引和搜索其相关的文本信息，例如视频／图像所在网页的周同文 字，视频的语音记录、字幕，视频／图像标题，通．Ｈｊ资源定位符（ＵＲＬ，也称网页地 址１等等。对于大规模的图像集，基于文本的搜索快速高效。但是，“一幅图像胜 过千言万语”，有限的文本信息不足以全面充分地描述图像丰富的视觉内容，因 此基于文＝耷：的搜索结果４ｉ尽如人意，在搜索引擎返回的结果中，一些４ｉ相关或者 相关度低的图像经常被排在搜索结果的前几位［１１。图像和其文本信息之间的误匹 配会造成?‘些不相关的图像错误地被返同；由于仅依赖于义－奉信息无法区分图像 的相关程度，所以一些相关性较低的图像被返回给用户。除此之外，目前最好的 自动语音识别（ａｕｔｏｍａｔｉｃｓｐｅｅｃｈｒｅｃｏｇｎｉｔｉｏｎ，ＡＳＲ）［２】，视频文本检澳．１Ｊ（ｖｉｄｅｏｔｅｘｔｄｅｔｅｃｔｉｏｎ）和机器翻译（ｍａｃｈｉｎｅ ｔｒａｎｓｌａｔｉｏｎ，ＭＴ）Ｍ技术的准确率不高，通过这些 方法提取的文本信息噪声人，可靠性不高。 为了解决基于文本的视频和图像搜索存在的缺点，基丁内容的自动标 注（ａｕｔｏｍａｔｉｃ ａｎｎｏｔａｔｉｏｎ）［．１一Ｈ１被提出通过语义标注得到更加准确和全．血的图像 文本信息捕述。但是在大规模图像数据集上目前的自动标注方法无论是在准确性 上还是语义规模上都远达不剑实用的标准。另外一个可能的解决办法是基于内容．１。中国科学技术大学博上学位论文１．２国内外研究现状、技术难点以及存在的问题的视频和图像搜索（ｃｏｎｔｅｎｔ―ｂａｓｅｄ ｉｍａｇｅ／ｖｉｄｅｏ ｒｅｔｒｉｅｖａｌ，ＣＢＩ／ＶＲ）［９１。该方法完全不用文本描述信息，只依赖于图像视觉信息，比如颜色，纹理，边缘等。不幸的 是，在ＣＢＩ／ＶＲ系统中要求用户提供查询样例图像，但是在Ｗ．ｅｂ图像搜索中，用户 更习惯于用关键词搜索，对于用户来说大多数情况下样例图像很难获得。同时， 由于底层视觉特征和高层语义概念之间的语义鸿沟（ｓｅｍａｎｔｉｃ ｇａｐ）［１０］的存在，仅仅依靠内容的搜索方法【１１】已经被证明不能得到很好的搜索结果。综上所述，基于文本的和基于内容的搜索各有优缺点。如何解决他们各自存 在的问题同时并利用他们各自的优点？一个比较好的解决方案是先用基于文本的 搜索方法快速从人规模的数据库中返回一个初始的查询结果，然后在小规模的初 始查询结果数据集上充分利用图像的内容信息米得到一个更好的结果。视频／图 像重排序就是这样一个利用视觉信息改进初始查询结果的过程。重排序能有效提 高提高视频／图像搜索结果，重排序研究对建立快速有效查询系统有蕈要意义。１．２国内外研究现状、技术难点以及存在的问题近年来提出了很多重排序算法，本节将从多个角度全面地总结视频／图像搜 索重排序的发展和研究现状。１．２．１节从重排序目标不｜一的角度将重排序算法分 为两人类；１．２．２节按照重排序巾应用的特征类型的不同分别介绍了三类重排序算 法；１．２．３节从重排序中应用的基础算法的角度进行总结：１．２．１节讨论近期出现的 引入用户相关反馈的重排序方法。 １．２．１重排序目标以及效果衡量准则 存视频／图像搜索中，重排序的基本目标是得到一个让片ｊ户满意的搜索结果。 一个好的搜索结果中返回的样本应该同时满足两个条件，即与查询的相关性和图 像的主题多样性。按照重排序目标侧重点的不同，现有的重排序算法可以分为两 大类：基于相关性的重排序和多样性重排序。相关性重排序的目标是将相关样本 排到前而返回给用户，但是忽略了样本之间的关系。与相关性重排序不ｌ一，多样 性重排序的目标是提高返Ｉ口Ｉ图像的多样性，以避免信息冗余的重复图像给用户带 来的问题。 １．２．１．１．基于相关性的重排序 在重排序研究的早期阶段，绝大多数的工作都足以提高搜索结果的相关性为目的【１ ２一ｌ－】。我们称这类方法为基于相关性的重排序，或简称为相关性重排序。．２．中国科学技术大学博士学位论文第一章绪论这类方法通常有两个基本假设，即视觉一致性假设和排序一致性假设。视觉一致 性假设是指视觉相似的图像很可能其排序分数也比较接近，冈此应该排在相近的 位置。排序一致性是指最初的基于文本的搜索结果尽管有噪声但是反映了从文本 角度的信息，因此应该保留其中的有用部分。此外，在文本搜索结果中，排在前 面的图像与排在靠后位置的图像相比，与杏洵相关的概率更高。利用文本搜索结 果的这?。性质，基于伪相关反馈的重排序被提出，将在１．２．３节中讨论。 在相关性重排序中，衡量其重排序效果的标准也是独立考虑返回结果中 的每个图像的相关性。经常使用的衡景标准主要有两个，一个是非内插的平均 查准率ｎｏｎ―ｉｎｔｅｒｐｏｌａｔｅｄ ａｖｅｒａｇｅｄ ｐｒｅｃｉｓｉｏｎ，ＡＰ）［３】，另一个是ＮＤｃＧ（ｎｏｒｍａｌｉｚｅｄｄｉｓｃｏｕｎｔｅｄ ｃｕｍｕｌａｔｅｄｇａｉｎ）［］（ｊ１。ＡＰ计算搜索结果中当每个相关样本ｍ现时的查准率然后求均值，搜索结果中位于第ｋ个返Ｉ口Ｉ图像处的ＡＰ值计算如Ｆ１ｋＡＰ＠ｋ＝軎∑加（ｉ）木ｒｅｌ（ｉ）］，厶１百（１－１）其中ｐ（ｉ）是搜索结果中前ｉ个图像的查准率，定义为前ｉ个图像中与查询相关的图 像的比例：ｒｅ２（ｉ）是一个＿值函数，如果第ｉ个图像与查询相关则ｒｅｌ（ｉ）＝１，否 贝Ｕｒｅｌ（ｉ）＝０；Ｚ１是归一化常数，以保证理论最好的排序中ＡＰ＠ｋ＝Ｉ。 当图像的相关性等级只有两级（相关或者／１ｉ相关）的时候，ＡＰ是一个很好的 衡罩标准。但是当相关性等级高于两级的时候，ＡＰ就不再适用了，在这种情况 下，ＮＤＣＧ被广泛用于信息检索领域以衡量排序效果。搜索结果中位于第七个返 回图像处的ＮＤＣＧ值计算如下＋ＮＤＣＧ＠ｋ＝軎Ｆ？，（２“一１）／ｌ０９２（１＋ｚ）， 厶２一｝一１与ＡＰ中类似，保证最优排序中ＮＤＣＧ＠后＝１。（１．２）其中ｔ；是搜索结果中排在第ｉ位的图像的相关性等级；历是归一化常数，其作用相关性重排序中存在的问题是，每幅图像跟查询的相关性是独立考虑的，图 像与图像之间的关系被忽略了。一个返回很多相关但是重复图像的结果，虽然其 相关性很高（用ＡＰ或者ＮＤＣＧ衡量），但是提供给用户的信息很少。不幸的是，南 丁．十Ｈ关性重排序中的视觉一致性假设，重排序结果中经常出现冗余的重复或者非 常相似的图像。．３．中围科学技术人学博Ｊ．学位论文１．２幽内外研兜现状、技术雕点以及存枉朐问题１．２１２多样化重排序如『在［Ｊ＿】中讨论的那样，用户希望返川的搜索结果，方面每幅图像的丰【Ｉ关性都很高，另一方而这些罔像涵盖尽可能多的主题，为了解决相关性重捧序－ｐ的 问题，多样化重排序被提出用于返Ｉ旦｜覆盖丰富主题的结果咀满足用户的不同需 求。近几年，多样化重排序引起了越来越多的重视。图】ｌ给出了相天性重捧序和 多样化重排序的区别。后者不仅要提高相关性，而且同时要求排存日＂面的图像可 以代表查询Ｉ贞的不同方面，丑ｕ主题多样性。媛冈羹盈墨釜鬣■曼 雹翟麓。， ｊ一翮，¨谶ｆ目｛ｆ２４－∞月％F＊ ｍ）Ⅻ＊ｎｍ＊”Fｍ ㈦￥目目ｗ∞＃＃ｍ＊＊Ｊ十F＊图１．１以Ａ询…ｇｏｇｈｌ为恻示意扣戈性重排序和－题乖排序的区刺。如ｌⅫ（ａ）柙（ｂ）所示一甚于史奉的挫索结粜平兀栩戈性币排序结果中都返回了（近似）乖复的罔儆，例如（ａ）－ｌＪ帕两 隔“ｓｔａｌＴｙ ｎｉｇｈｔ”和（ｂ）中的婀幅“ｓｌｌ Ｊ ｘｆｌｏｗｅｒ，罔（ｃ】给卅了我们奶单得到的ｔ磁多样化结粜 无蕾复的、ａ”ｇｏｇｈ名画。在［?、１巾，通过利川罔像附带的文本信息（标签、图像标题平Ⅱ周围文字描述等）ｔ借助已有的文本搜索多样化晕排序力法建立了一个榆索模趔以返回涵盖多种图像的搜索结果。在…】中，首先利川图像标沣信息计算仃意两幅图像之间的主题覆盖关系．然后将这种主题覆盖关系作为连接概率，采用类似 十ＰａｇｅＲｍｌｋ㈨】的方法得到每幅图像的土题半富度（ｔｏｐｉｃ ｒｉｃｌｍｅＲｓ）．最后顺序选取手题丰富度最大井与已经选择的图像４ｉ相似的图像作为结果返回。在卜Ｉ伸，首先通过聚类算法将图像分成若干类，然后通过从每个聚类中选取一个最具有代 表性图像的方法来得到丰题多样的结果。Ｙａｒｌｇｅｔａｌ『２划首先进行基于相关性的重排序来得到每幅图像的柑关性分数，然后顺序选择既相关叉与已经选择的罔像 不相似的图像作为结果返州。 由丁重排序目标的不同，在帕关性重排序中的ＡＰ和ＮＤＣＧ不能冉用丁衡量多 样性重排序的结果。需要寻找桐应ｎ勺评价标准，可以同时衡量相关性和主题多样中国科学技术大学博士学位论文第一章绪论性两个方面。一个常用的衡量是在ＩｍａｇｅＣＬＥＦ中提出的基于查准率（Ｐ＠ｋ）和聚类 查全率（ｃｌｕｓｔｅｒｉｎｇ ｒｅｃａｌｌ，Ｃｎ＠ｋ）ｔ筝／准则［２剀。这里认为每一个聚类代表一个主题。 聚类查全率的定义是：ＣＲ＠ｋ：―ｃｌｕｓｔｅ―ｒｓ（ｋ）．（１－３）ｔＣ其ｄＰｃｌｕｓｔｅｒｓ（ｋ）是指返回的前ｋ幅图像覆盖的聚类个数，ｔｃ是指所有图像的总聚类个数。最终的衡晕标准定义为ｐ＠ｋ和ＣＲ＠ｋ的Ｆ―Ｓｃｏｒｅ，即ｆ＠ｋ－－２篇．（１－４）这种衡芾标准用查准率来度晕相关性、聚类查全率度景主题多样性。这种标 准尽管已经比较合理，但是在两个方面考虑的不是十分精确。第‘个方面是没有 考虑到实际数据中图像的分层结构特点，而足简单地把图像划分到位于同一层次 的不同聚类里。另一个方面是，在用于衡量相关性的查准率中没有区分不同样本 的排序位置的重要性。我们期望能够找到更为精确的衡量标准可以解决上而的问题。除了上而介绍的Ｆ―ｓｃｏｒｅ，还有其它一些多样性衡量方法，例如在【】ＩＪ】中提出 的多样性分数。但是，该方法需要提供图像的标注词，在大多数情况下图像没有 这一额外信息。此外，用户调查是衡量用户对多样性重排序结果满意度的最直接 方式，但是该方法耗时Ｋ＝而且需要很多的人力劳动。 １．２．２重排序中使用的特征类型 按照使用的特征种类升ｉ同，重排序方法可以分为三类，即基于文本信息的、 基Ｊ：高层视觉特征的，和基ｊ：底层视觉特征的。 １．２．２．１．基于文本信息的重排序 尽管绝大多数的重排序方法都是通过引入视觉信息以提高初始的基于文本 的图像搜索结果，但是仍然有少数重排序工作是通过进一步挖掘跟图像相关的 文本信息来实现重排序。ｗ．一Ｈ．Ｌｉｎｅｔａ１．ｐ ｌ】利用搜索引擎返同图像所在页面的ＨＴＭＬ文件建立相关性模犁，在发掘这些文件文本信息基础．卜改进相关性模 型，最后图像按照该模型估计得到的相关性概率重新排列。文献『ｌ ｓ】中的多样化 重排序方法也是利用图像的文本信息，例如标签、图像标题和捕述等，建立语言 模型以得剑主题多样化的结果。一５一中国科学技术大学博上学位论文１．２国内外研究现状、技术难点以及存在的问题基于文本信息的方法将图像重排序转化为一般的文本搜索重排序以利用在 文本搜索重排序中已有的技术。这类方法的缺点是忽略了最为根本的图像内容信 息。因此，在基于文本的图像搜索中存在的问题在这里依然得不到解决。为了克 服文＝奉＝特征造成的问题，很多重排序方法借助其他类型的特征，例如视觉特征， 与文本特征互相补充，以改进搜索结果。 １．２．２．２．基于高层视觉特征的重排序 这一类重排序方法利Ｈｊ高层的视觉特征，例如概念检测（标注），人脸检测等。 在这类方法中最常使用的高层视觉特征是概念检测，其过程可以大致分为三个步 骤。首先，通过分析文本查询词从一组预先给定的概念集中寻找与其相关的若干 个概念。然后，通过使用概念检测模型得到这些相关概念在每幅图像中的分数， 即某概念在该图像中卜ｈ现的概率。最后，利用在．卜一步中得到的概念检测分数使用不同的模型，例如向量模型、文献ｆ．２ｑ中的语言模型和义献【２（以中的ＬｉｓｔＮｅｔ等，进行重排序。对于预先给定的概念集，很多基丁概念检测的重排序方法『２５，２６１ 都是使用ＬＳＣＯＭ（１ａｒｇｅ－ｓｃａｌｅｃｏｎｃｅｐｔ ｏｎｔｏｌｏｇｙ ｆｏｒｍｕｌｔｉｍｅｄｉａ）［２７］提供的４４９个视觉概念集。从概念集中挑选与查询十甘关的概念即查询扩展（ｑｕｅｒｙ ｅｘｐａｎｓｉｏｎｌ，是 这类重排序方法巾的关键问题，Ａ．Ｎａｔｓｅｖｅｔａ１．在文献ｆ＿１巾对重排序巾的查询扩展进行了总结。在该文中将垒询扩展分为两大类：基于文本的和基于视觉概念 的；每一类中的方法又进一步分为特定语言的、特定数据库的和特定查询统计的 方法，细节可以参考文献Ｆ１。 这类方法对于部分特定查询较为有效，例如人脸检测对于与人相关 酐Ｊ（ｐｅｒｓｏｎ－ｒｅｌａｔｅｄ）金询非常有效。但是，这类方法受概念集规模和现有的概 念检测模型的精度的限制。 １．２．２．３．基于底层视觉特征的重排序 尽管高层视觉特征可以在‘定程度上提高重排序的效果，但是概念检测在人 规模数据集上的广度和准确度都远远达不到实用标准。为了避免在概念检测步骤 中的误差累积，很多方法直接在底层视觉特征空间进行重排序。经常使用的底层 特征可以分为两大类：全局特征和局部特征。 全局特征将每‘‘幅图像作为＋个整体来描述其内容。在重排序中常用的全局特征包括基丁．颜色的，例如颜色矩ｆ２诛基丁．边缘的，例如边缘方向直方图陋卜３｜１． 和基于纹理的，如小波纹理ｍ，：州；基于形状的，例女ＨＧＩＳＴ特征…１等。不同种一６一中国科学技术大学博上学位论文第一章绪论类的特征从不同的角度描述图像内容，通常将多种特征融合以得到较好的效果。 一般有两种特征融合方式，即前期融合和后期融合。前期融合一般是将多种特 征连接成一个大的特征向量，然后用于重排序。例如，Ｘ．Ｔｉａｎｅｔａ１．ｆ３５１用４２８维 ａ１．［２１】分别利的全局特征描述每幅图像的视觉内容，这４２８维特征由２２５维的颜色矩特征、７５维 的边缘方向直方图特狂和１２８维的小波特征组成。Ｒ．Ｈ．Ｌｅｕｋｅｎｅｔ用人种特征来度量任意两幅图像的相似度，然后线性加权得到最终的相似度，在 此基础上对图像进行聚类。后期融合一般是先利用各种特征独立地进行重排序， 然后对重排序结果进行融合。在１．２．３节中将要介绍的基于线性组合的重排序方 法『－，：｛（＿；１就属于对多种特征进行后期融合这一类。 局部特征与全局特征不同，它将图像看作是由一些局部区域块组成的集合。ＢＯＶＷ（Ｂａｇ－ｏｆ－ｖｉｓｕａｌ－ｗｏｒｄｓ）［３７］足一种常用的图像局部特征表达模犁。该模型首先从图像中检测得到。些感兴趣区域点（ｉｎｔｅｒｅｓｔ ｐｏｉｎｔ）并通过各种描述子（ｄｅｓｃｒｉｐｔｏｒｓ）［：；ｓ］得到对这些点的局部捕述；然后对数据集中所有图像的局部描述向量进行聚类，将每个聚类中心作为。‘个码字（ｖｉｓｕａｌ ｗｏｒｄ），码书（ｃｏｄｅ ｂｏｏｋ）定义为所有码字的集合；最后将每幅图像中的局部捕述向量与码书进行匹 配，得剑一个统计码书中各码字在该幅图中的出现频率的直方图。常用的感兴趣区域点检测算法有：Ｈａｒｒｉｓ－Ａｆｆｉｎｅ［３９一ｌ １】、Ｈｅｓｓｉａｎ―Ａｆｆｉｎｅ［；１９，１（）】、ＤＯＧ（ＤｉｆｆｅｒｅｎｃｅｏｆＧａｕｓｓｉａｎ）［４２―１ｊ１、ＳＵＲＦ［１９］等；常用的局部描述子有：ＳＩＦＴ（ｓｃａｌｅ－ｉｎｖａｒｉａｎｔｔｒａｎｓｆｏｒｍ）『４ １１、ＧＬＯＨ（ｇｒａｄｉｅｎｔｌｏｃａｔｉｏｎ―ｏｒｉｅｎｔａｔｉｏｎｆｅａｔｕｒｅｈｉｓｔｏｇｒａｍ）【５２】等。Ｙ． ｔｒａｎｓｆｏｒｍ）作为描述Ｊｉｎｇ ａｎｄ Ｓ．Ｂａｌｕｊａｆ１：；１用著名的ＳＩＦＴ（ｓｃａｌｅ－ｉｎｖａｒｉａｎｔｆｅａｔｕｒｅ子对感兴趣区域点提取特征，通过两幅图像之间的感兴趣区域点匹配来衡量图像 之间的相似性。Ｙ．Ｌｉｕｅｔａ１．ｆ１ １１从多个搜索引擎的返回图像中提取ＳＩＦＴ局部特征为每个查询寻找最优代表性的码宇。 全局特征和局部特征分别从不同的角度来描述图像的内容，Ｌ．Ｗａｎｇｅｔ ａ１．ｆ州联合使用局部和全局特征进行重排序，取得了比单独使用局部特征或者全局 特征更好的效果。 １．２．３重排序的方案 在重排序方法发展的早期阶段，通常使用简单的线性组合方案将从多种线索得到的搜索结果进行融合：随后提出了一些更有效的工具进行重排序，例如【＝；ｆｑ中 ＮＳＶＭ［Ｊｌ，，１７１、ｐ｝】中ｆｉ向ＬｉｓｔＮｅｔ、【１２】中的信息瓶颈原理（ｉＩｌｆｏｌ－ＩＩｌａｔｉｏＩｌ一７．ｂｏｔｔｌｅｎｅｃｋ中国科学技术大学博士学位论文１．２国内外研究现状、技术难点以及存在的问题ｐｒｉｎｃｉｐｌｅ）、【１３】中的ＰａｇｅＲａＩｌｋ等。根据重排序中利用的算法种类不同，重排序方法可以大致分为四类，即基于线性组合的、基于聚类的、基于分类的和基于图的， 如图１．２中所示。基于线性组合的基丁聚类的基于分类的基于Ｉ荽ｌ的，～、，－＿－－。●。＿－●。－，●●，．－．．。＿－●●●。＿＿．－－．－－－。＿。－－－●●●－●●●●。一＿。－．‘●＿。‘●‘－－‘●－。．．一－．．ｐ．．．－－－＿－－＿．－－‘●。●。●，‘●‘●．＿＿．＾－－．－．－‘，，，，图１．２四种／ｆｉ同重排序方案的乃÷意图，包括基丁．线性组合的、基丁．聚类的、基丁．分类的和 基丁．图的．１．２．３．１．基于线性组合的重排序 线性组合的方法是把从不同特征得到多个搜索结果进行融合的最为直接的 方式。在这类方法中，一般首先分别利用单个特征得到每个图像的排序分数，然 后将从不同特征得到的排序分数进行平均作为该图像最终的排序分数，将图像 按照其排序分数降序排列即可得到最终排序结果。例女¨Ｒ．Ｙａｎｅｔａ１．ｆ３６］从多模特征（颜色、纹理、文本）分别搜索跟查询相关的视频帧，然后将从不Ｉ―Ｊ特征得到 的相关性分数转化为后验概率，通过后验概率的加权组合得剑最终的相关性分数。Ｘ．Ｌｉｅｔａ１．【．２５】在概念检测空间使用两种著名的文本检索模型即向量模型和 ａ１．【７１也利用线性组合的方式米融合从语言模型，来改进基于文本的图像搜索结果；然后，将重排序结果与初始结果线 性加权作为最终结果返回。Ａ．Ｎａｔｓｅｖ 多模特征得到的搜索结果。 在这类方法里，线性组合系数对重排序结果影响很大。在大多数情况下，由ｅｔ于对每个查询没有训练数据来决定组合系数，因此一‘般都是经验设置的。在『７１中考虑到不同种类的特征对不同查询的有效性，提出用杏询十耳关的线性组合系数进 行加权以得到更好的重排序结果。．８．中国科学技术大学博士学位论文第一章绪论１．２．３．２．基于聚类的重排序 查询相关的样本通常视觉相似性比较高，基于这一观察聚类的方法被提出用 于重排序。利用各种聚类算法，这类重排序方法将视觉相似的图像聚集在一起。在【１２】中，根据初始的查询结果，每一个图像被赋给一个伪相关分数；然后信息 瓶颈［１ｓｌ方法被用米去寻找一个最优的聚类结果使得聚类和相关分数之问的互信息最人：最后按照聚类的条件概率和图像的密度（通过ＫＤＥ估计得到）对初始查 询结果重排序。这种方法在某些查询项中取得了较好的结果，但是其有效性局 限于初始查询结果巾具有较高重复性的查询项。聚类个数是该方法巾的关键参数，在【１２】中经验地设置该参数以保证每个聚类大概包含２５幅图像。Ｆ．Ｊｉｎｇｅｔ ａ１．ｎｌＪ】首先对网络文本搜索和图像搜索结果进行聚类得到跟查询相关的一些聚类名称，然后将这些聚类名称分别作为查询词提交到图像搜索引擎中，将返回的图像 作为每一类的重排序结果。Ｒ．Ｈ．Ｌｅｕｋｅｎｅｔａ１．【２１】提出了三种启发式聚类方法将初始的搜索结果按照视觉相似性进行聚类。 基于聚类的重排序方法适用于文本搜索结果返回的图像重复性比较高的金 询。对于返回结果图像种类比较多，没有显著主题的查询，该方法对搜索效果的 提高不是很明显。除此之外，自动确定合适的聚类数目还在研究中，目前还没有 很好的解决办法。 １．２．３．３．基于分类的重排序 基于分类的重排序方法将重排序问题转化成‘个二分类问题，即区分与查询 相关和不相关的两类样本。这类方法一般包含三个步骤：１）从初始的查询结果中 挑选?‘些伪止例和伪负例：２）利用挑选出来的样例，训练＋‘个分类器；３）依据分 类器对各个图像的预测值（相关性分数）来进行重排序。在第一步中借鉴文本搜索 中的伪相关反馈（ｐｓｅｕｄｏｒｅｌｅｖａｌｍｅｆｅｅｄｂａｃｋ，ＰＲＦ）方法瞄ｆ）】，初始查询结果中排在前几位的图像一般被用水做为伪正例，当查询样例图像可以获取的情况下，也可以直接将查询图像作为萨例［＝ｊｆ；］：基于数据库巾跟查询相关的图像只占很少一部分的假设，伪负例的获取通常是通过从数据库中随机采样得到。在第二步中，经常采用的分类器有ＳＶＭ［３６】、ｂｏｏｓｔｉｎｇ［５ ｌ】和Ｒａｎｋｉｎｇ ＳＶＭ［５２１等。‘尽管上面介绍的分类器被证明在很多应用中效果不错，但是为了可靠估计 模型参数需要有允足的训练样本来保证模型的效果。在图像搜索重排序中，通 过ＰＲＦ挑选出来的训练样本数目有限而且噪声人（基于文本的图像搜索结果准确一９．中国科学技术大学博上学位论文１．２国内外研究现状、技术难点以及存在的问题率不高造成的），因此限制了此类方法在实际中的应用。 １．２．３．４．基于图的重排序 在基于图的视频／图像重排序方法中『１３，１５，５翻，通过把图像当作节点，把这 些相似的节点连接起来得到一个图。图像之间的相似性被用来作为这些节点之问 的连接权重；然后通过相关分数在图中各边上的不断传播实现重排序。Ｗ．Ｈ．Ｈｓｕｅｔａ１．【５：朝将重排序看作是在图上随机游走（ｒａｎｄｏｍ ｗａｌｋ）的过程。随机游走过程的稳定概率被当作图像的最终相关分数，按照相关分数的大小对图像进行重排 序。Ｙ．ＪｉｎｇａｎｄＳ．Ｂａｌｕｊａ［１３】将著名的Ｐａｇｅｒａｎｋ［２［）］算法应用于图像搜索域，提出了ＶｉｓｕＭＲａｎｋ重排序算法。ＶｉｓｕａｌＲａｎｋ将图像看做文本、图像之问的视觉相似 性看做是概率超链接（ｈｙｐｅｒｌｉｎｋ），在此基础上运用ＰａｇｅＲａｎｋ算法进行霞排序。Ｘ．Ｔｉａｎ ｅｔａ１．【１ｊ１提出了基十图的重排序方法的一般框架，从贝叶斯角度将重排序问题转化成给最优化问题。文献【５：｛］和文献【１３】中的方法都可以统一到该框架下。基’ｊ：图的方法充分利用了图像的分布信息和结构信息，这些信息反映在图的构建 中，因此如何构建合适的图模型是这类方法的关键，在以后的研究中应该仔细探讨。１．２．４重排序中的相关反馈 目前大多数的重排序方法都是无监督的。当用户查询词指代不明确的时候， 无监督的重排序结果往往不能满足用户的不同需求。因此有必要在重排序中引 入相关反馈，以明确用户的特定搜索意图，返回符合用户需求的结果。近年来卅 现了‘。些这方面的重排序：［作。Ｊ．Ｃｕｉｅｔａ１．…］提出了ＩｎｔｅｎｔＳｅａｒｃｈ模型，该模型允许用户从初始的搜索结果中挑选一幅图像作为正例，然后通过计算其它图像 与这幅图像的相似性进行重排序。但是南于语义鸿沟的存在，很多情况。卜．很难 用一幅图像完整表达用户的搜索意图，尤其在搜索意图比较复杂的情况下。Ｘ．Ｔｉａｎ ｅｔａ１．［３＿】提出了主动重排序，该方法通过与用户交互不断地学习用户的 Ｍ．一Ｓ．Ｃｈｅｎ∞ｓ】提出了针对图像日标检索问题真实搜索意图。ＩｎｔｅｎｔＳｅａｒｃｈ可以看作是用户只标注一幅相火图像情况下的简化 的主动重排序。Ｊ．Ｈ．Ｈｓｉａｏａｎｄ的ｉｎｔｅｎｔｉｏｎ―ｆｏｃｕｓｅｄ主动重排序方法。该方法通过在相关反馈过程中加入用户搜 索意图区域的确认避免背景＇－３ｌ入的噪声。 这些主动重排序方法都足基于显示的反馈（ｅｘｐｌｉｃｉｔ ｆｅｅｄｂａｃｋｌ，在用户交互无 法获得的情况卜．，可以考虑隐式反馈（ｉｍｐｌｉｃｉｔ ｆｅｅｄｂａｃｋ）进行重排序。与显示反馈一１０．中国科学技术大学博士学位论文第一章绪论相比，隐式反馈尽管噪声大但是仍然可以提供一定量的有用信息。例如，很多研究［５６】已经表明从日志文件中搜集得到的ｃｌｉｃｋｔｈｒｏｕ曲（一种典型的隐式反馈）数据在信息检索中的有效性。既然隐式反馈一方面对提高重排序效果有用另一方面又 可以以低成本大量获取，因此值得考虑将各种隐式用户反馈引入重排序中。１．３本文的研究动机及内容上一节中从多个角度总结分析了现有的各种重排序方法，尽管这些方法已经 取得了一定的进展，目前该领域仍然有许多有价值的问题值得研究。本文－丰要考 虑从以下几个方而对视频／图像搜索重排序进行研究： ?重排序巾两种基本信息的本质作用：重排序町以看作是利用视觉信息从含 有噪声的搜索结果中恢复真实的搜索结果，文本和视觉是重排序中的两种 基本信息。关于文本信息，是指初始的基于文本的图像搜索结果是重排序 的基础，虽然含有一定的噪声，但是同时也反映了从文本角度得到的排序 信息，因此需要保留这部分有用信息同时去除噪声。关于视觉信息，重排序 方法中的一个基本假设是视觉一致性假设，即视觉相似的样本其与查询的 相关性很可能也比较接近，因此应该排在邻近的位置．卜。视觉一致性假设 可以看作是我们经验的先验知识，而义奉信息作为重排序的基础实际可以 看作是重排序的似然。通过分析这两种信息在重排序中的本质作用，可以 更好地理解重排序问题，并在此基础上提出有效的重排序算法。 ?重排序运用到实际系统中的笑键问题：重排序研究的最终目的是成功地将 其应用到实际的搜索系统中，有效提高基于文本的视频／图像搜索结果。当 将重排序技术应用到实际中时，重排序算法，尽管很重要，但是并不是我们 唯一需要考虑的问题。除了算法本身，还需要考虑其它重要影响因素，例如 有效的视觉特征表达，计算复杂度，搜索引擎自身搜索技术对晕排序的影 响等等。分析和研究这些影响因素，对重排序的实际应用和进一步的研究 工作都有指导意义。 ?与用户交互的主动重排序：如在１．２．】节中的讨论，在杏洵词不明确的情况 下，通过引入用户相关反馈对于明确得知用户的特定搜索意图，在此基础 上冉进行重排序可以得到让用户满意的结果。但是，现有的基丁用户交互的方法中，ＩｎｔｅｎｔＳｅａｒｃｈ一】】南于只允许用户标注一幅相关图像，在很多情一】１一中国科学技术犬学博士学位论文１．４本文的结构安排和创新点况下，一幅图像不足以准确描述用户的特定搜索意图；文献［ｔ５５】中的方法主要是针对日标检索，不具有普适性。因此，有必要提出一个可以广泛应用的 基于用户交互的主动重排序框架，在该框架下可以准确地学习用户的搜索 意图，并利用子空间学习算法得到用户搜索意图在特征空间中的准确表示， 然后在学到的子空间中进行重排序有效提高搜索效果。 ?同时优化相关性和主题多样性的重排序：由１．２．１节中的分析可以看出主 题多样化霞排序越米越受到重视。但是现有的多样化重排序方法受到两方 面的限制。首先，这些方法对相关性和多样性的优化是分两步进行的，因此 得／１ｉ到联合最优的结果；另一方面这些方法普遍使用视觉多样性来近似主 题多样性，由于语义鸿沟的存在，这一方法很难得到好的结果。同时优化相 关性和主题多样性，并采用更合理的方式来描述主题多样性，可以有效提 高主题多样化重排序的效果。除此之外，如在１．２．１．２．节中讨论的那样，现有 的丰题多样性重排序评价准则也不够精确，我们需要寻找新的可以准确反 映排序结果中相关性和主题多样性的评价标准。 ?重排序学习（１ｅａｒｎｉｎｇｔｏｒｅｒａｎｋ）：日静的重排序算法大多都是为每一个查询单独建立重排序模型。这一方法的缺点是：１．耗时大，对每一查询都要 重新建以模型：２．由于缺乏每个查询各自的训练数据很难确定模型参数。受 文奉搜索中的排序学习（１ｅａｒｎｉｎｇ 重排序学习（１ｅａｒｎｉｎｇｔｏ ｔｏｒａｎｋ）的启发，我们是＝含可以类似地进行ｒｅｒａｎｋ）？这样就可以从一组已标注的训练查询集中学习得到一个通用的重排序模型，利用该模型可以对新的未标注查询进行 重排序，而不需要为每个杏洵确定不同的参数。但是建立这样的重排序模 型并非易事，其关键是要寻找，‘组特征用以描述不同排序结果的性质。１．４本文的结构安排和创新点基于１．２节和Ｊ．：｛节中的讨论，本文对其中的几个问题进行了深入分析和细致 研究。本文的结构安排和创新点如下： 第１章巾，首先阐述了视频／图像搜索重排序的研究背景和意义；接下来详细 调研鼋排序方法的国内外研究现状，进一步分析季排序的技术难点以及存在的问 题，然后给出了本文的研究动机和内容，最后是本文的结构安排和创新点。 第２章中通过分析视觉信息和文本信息在重排序中的不同作用，将视觉一致．】２．中国科学技术大学博上学位论文第一章绪论性假设和排序一致性假设分别作为先验和似然，在贝叶斯框架下将基于内容的重 排序转化成全局最优化问题，称为贝叶斯重排序。贝叶斯重排序通过最大化视觉 相似图像的排序分数同时最小化重排序前后样本的排序变化来得到最优的重排 序结果。贝叶斯重排序是一个普适性的方法，很多现有的算法可以统一到该框架 下。同时，针对现有的方法中对视觉一致性和排序一致性的描述存在的问题，本 章还提出了一种基于局部学习的视觉－。致性描述方法和‘’种基于点对的排序一 致性计算方法。在标准数据集．Ｌ的大量实验验证了贝叶斯重排序框架以及新提出 的两种一致性描述方法的有效性。 第：；章中探讨将重排序应用于实际图像搜索系统巾时的六个关键问题。这六 个问题包括：重排序算法选择、有效的视觉特征表达、计算复杂度、高效的特征 抽取、重排序与搜索引擎的关系，和文本搜索结果在重排序中的作用。为了寻找 这些问题的答案，从二个常用的商业搜索引擎中搜集了一个刚络图像数据集，并 在该数据集卜进行了大黄的实验，通过对实验结果的分析和总结，给ｍ了这六个 问题的答案。 第ｌ章讨论当用户查询项指代不明的情况卜．，如何对义本搜索结果进行重排 序以返回满足用户特定搜索意图的结果。解决这一『口Ｊ题的关键是确定用户的搜索 意图。本章提出了基于人机交互的主动重排序方法，该方法首先通过人机交互获 得用户的标注信息，在此基础上利用予空问学习算法Ｉ又：分与用户查询相火和不相 关的图像。在学习用户的真正搜索意图过程巾，为了减少用户的标沣量提出了一 种基于结构信息的样本主动选择方案；为了学习反映与用户查询相火的图像子空 问提出了一种局部一整体区分式子宁间学习算法。在人工数据集和网络图像数据 集上进行了大量的实验，实验结果验证了本章提出的主动晕排序方法的有效性。 第一章讨论在无法得知用户特定搜索需求的情况卜．，如何通过重排序返回一 个主题多样化的排序结果以最大可能地满足不同的搜索需求。针对现有的多样化 重排序的局限性，提出了联合优化相关性和丰题多样性的丰题多样化重排序。该 方法在结构学≥Ｊ框架下设计了一组特征来捕述排序结果的相关性和多样性，然后 利用用户标注信息，通过从一组训练数据中学习得剑主题多样化重排序模型。利 用该模型，可以对未标注的查询进行预测得到高相火性和高主题多样性的重排序 结果。在网络图像搜索数据集上的实验表明木章巾提出的方法可以同时提高文本 搜索结果的相火性和主题多样性。 第（ｉ章对全文工作进行了总结，探讨重排序的研究新方向。一１３．中国科学技术人学博上学位论文第■章贝叶斯重排序第二章贝叶斯重排序近年来，重排序被提出在基于文本的搜索结果基础上，通过加入图像视觉 信息对其改进图像搜索结粜。图２ Ｌ给出了视频／图像视觉重排序的一般性框架 躅。首先，通过索引文本信息快速返回得到文本搜索结果，然后通过挖掘这些返 回图像的桃觉信息得到更好的排序结粜。如图２ ｌ所示．当用户提交一个文本查 询“Ｐｍｌｄａ＂。后．基于文本的搜索引擎按照图像相应的文本信息与查询词之间的相 关性对数据库中的图像进，仃排序，返回一个基于文本的搜索结果（图２ １（ａ））。可以 看到，基十文本的搜索经常返回一些“不一致”的结果．即视觉上非常相似的图像 分散在查询结果中的小同地方，中间出现一些小相关的图像。例如，图２ １ｆａｌ中的 闰像１．２．４。６，７和９都是杳询相关而且视觉ｒ都很相似。面图像３，５．８辟ｌ这些相关图像都不相似。把视觉相似的图像排在相近的位置是比较台理的同时也符台人类的感知行为。可以利用相关嘲像的视觉敛性模式来对基下文本的结果进行 重新排序，将不卡【Ｊ关晌图像３，５，８放到后面而将其他的相关图像排到前面来，扭ｌ 罔２ ｆ（ｂ）所示。通过挖掘罔像视觉模式来对文本搜索返回阿像进行重新捧列的过程称之为基于内容的图像搜索重排序．简称视觉重排序。＿｝‰皤髫Ⅲ口骊囵昏。？露龉嗣吨，鞫茹¨銎雹鬣醴妊！｜ｉ；。燃。皂：兹。糌器纂黥然徽凝蕊缎矬鬣星萼＂“““槲戈的幽像。然后承排序过程被，｜ｊ于利卅划像的视觉信息来改进文本搜索结果。视觉重排序可以看作是利用视觉信息从含有噪声的搜索结果中恢复真实的 搜索结果．也就足从文本和视觉两方而的线索来改进搜索结果。关ｒ文本信息， 这黾是指最初的文术搜索结果为重排序提供了一个良好的基础。虽然这个排序含－１５一中国科学技术大学博士学位论文２．１贝叶斯霞排序有一定的噪声，但是它包含了文本信息对排序的作用，所以需要保留这部分信息 中的有用成分同时去除噪声。关于视觉信息，我们引入了视觉一致性约束，即让视觉相似的样本（视频ＩｌｌｌＪｌ／ｌ奎ｔ像）排在临近的位置；反之，视觉上不相似的样本不应该排在一起。重排序就是文本搜索结果和视觉一致性这两者之间的平衡。值得 注意的，虽然没有明确地表明，大部分视觉重排序方法ｆ１２，５３，５７１都足基于这一 基本假设的。 本章在贝叶斯框架下从概率的角度来描述如何利用文本和视觉信息进行重 排序。其中，反映重排序结果和文本结果之间关系的排序一致性约束可以看做是 似然；而视觉相似样本的排序一致性约束可以做为条件先验。在贝叶斯框架下， 晕排序可以表达成最大化条件先验和似然的乘积，因此称该方法为贝叶斯章排序。２．１贝叶斯重排序在介绍贝叶斯重排序之前，先定义一些在本文中常用的术语。 定义２．１ 排序分数列表（ｒａｎｋｉｎｇｓｃｏｒｅｖｅｃｔｏｒ，简称分数列表），＇＝ｐ１，ｒ２，…，ｒⅣ】Ｔ是与样本集合疋＝｛ｚ１，茁２，…，ＸＮ｝Ｅ Ｋ的关于排序分数的向量，其中ｎ是样奉翰的排序分数，排序分数越大表示该样本与查询词的相关 性越高。定义２．２排序列表２是对集合Ｚ中的样本按照其排序分数的降序排列。，重排序可以看作是从初始的排序列袭到目标排序列表的ｒ一个映射。为了计算 简便性，通常用排序分数列表来代替排序列表，因此本文将重排序函数定义在分 数列表上。 定义２．３ 重排序函数定义为 ，＇＝ｆ（Ｘ，于），（２－１）其中哥＝【ｆ１，恐，…，讯】Ｔ是基于文本的搜索返回的分数列表。将样本按照重排序函数进行排列的过程称之为重排序。 通过将重排序定义在分数列表而非排序列表上，将获得更好的灵活性和适应性【１２，ｊ：；】。对于初始分数列表无法获得的情况，例如在对Ｇｏ０９１ｅ图像搜索结果进．１６．中国科学技术大学博上学位论文第二章贝叶斯霞排序行重排序中瞄８】我们只知道返回图像的排序位置而无法得知其具体的排序分数，初始分数列表哥可以根据样本的初始排序来设置，在２．６节中将详细介绍。 重排序中的关键问题是如何得到最优的重排序函数（２一１）．本文从概率的角度 来考虑重排序问题，并通过贝叶斯分析得到最优重排序函数。把ｒ看做一个随机 变量，重排序叮以认为是在给定初始排序结果于和样本视觉信息石的情况下最 有可能得到的分数列表的过程。从概率的角度而言，重排序是给定样本集疋和 初始排序分数列表哥情况下，得到具有最大后验概率的最优ｒ’，即ｒ＋＝ａｒｇｍａｘｐ（ｒｌＸ，于）．（２－２）根据贝叶斯公式，后验概率与条件先验概率和似然的乘积成正比，即ｐ（ｒｌＸ，哥）。（ｐ（ｒｌｘ）×ｐ（ｅｌＸ，ｒ），（２－３）其中ｐ（ｒｌｘ）是给定样本视觉信息条件下分数列表的条件先验。例如，一个将视 觉相似的图像分散地排列在彳ｉ同位置的分数列表，其条件先验较小。ｐ（ｅｌＸ，，．）是似然项，反映了在给定初始分数列表哥的情况下最优列表为ｒ的概率。在后面 的章节中，我们将看到似然项可以通过一个衡量重排序前后两个分数列表哥和 ｒ的不一敛性，称之为“排序距离”的项来估计。 在大多数的视频／图像搜索系统中，于是利用文本信息得到的，与图像的视 觉内容无关。因此，在给定目标分数列表哥情况下视觉信息疋与哥的条件独ｊ移性 假设是成立的，即 ｐ（ｅ，光ｌｒ）＝ｐ（ｅｌｒ）Ｘ ｐ（ｚＩｒ）． 由此可得，ｐ（ｅｌｘ，７．）＝ｐ（哥Ｉ，．）．将式（２．１）代入式（２一：ｊ）中，可得到（２－４）．ｐ（ｒｌＸ，哥）。（ｐ（ｒｌｘ）Ｘ ｐ（于Ｉｒ）．（２－５）将（２一．２）中的后验概率用（２一Ｉ）代替，重排序即可以表示成最大化条件先验与似然 函数的乘积，因此称该方法为贝叶斯重排序。一１７一中国科学技术大学博士学位论文２．１贝叶斯重排序定义２．４贝叶斯重排序是指按照如下函数进行重排序的过程ｆ（Ｘ，于）＝ａｒｇ ｍａｘ ｐ（ｒｌｘ）×ｐ（于Ｉｒ）， 其中于是初始的排序分数列表，疋是文本搜索返回的初始结果中的样本。（２－６）在贝叶斯重排序函数中需要定义如何估计条件先验和似然函数。下面将详细 介绍这两项。 ２．１．１条件先验 在视觉重排序中，视觉一致性假设要求视觉相似的图像的排序分数应该接 近。这一先验知识可以通过贝叶斯重排序公式中的先验项来表达。具体来讲，我 们将条件先验描述为ｐ（ｒｌＸ）＝万１ 厶ｌ１ 厶１ｅｘｐ（一∑。蛾（’．，ｚ）） ―ｔ（２－７）＝÷ｅｘｐ（－Ｒｅｇ（ｒ，疋）），其中，Ｚ１＝∑，．ｅｘｐ（－∑ｔ识（，．，爿））是归一化系数，也（，．，疋）是定义在样本Ｘｉ上的能量函数用于衡量在其周闱小区域上的视觉一致性。所有样本上的能量之和’记为正则化项Ｒｅｇ（ｒ，疋）＝∑；也（ｒ，疋）。在２．２节中将给出关于咖（，＇，疋）的详细讨论。２．１．２似然正如前文中给出的讨论，基于文＿奉的搜索结果是重排序的基础，所以重排序 后的结果应该适当保留此文本信息中的有用部分。这一知识被用于捕述贝叶斯重 排序函数中的似然项，即１ｐ（于Ｉｒ）＝手ｅｘｐ（一ｃ×Ｄｉｓｔ（ｒ，于）），４２（２－８）其中，易＝∑予ｅｘｐ（一Ｃ×Ｄｉｓｔ（ｒ，于））是归一化常数，Ｃ是尺度函数，Ｄｉｓｔ（ｒ，于）是用于度量两个分数列表的不一致性的排序距离。排序距离的图模型如图２．２所 示，我们将在２．３节对其进行详细介绍。得到式（２―７）和式（２―８）后，式（２一ｎ）中的贝叶斯重排序公式等价于最小化如‘卜．的能量函数，Ｅ（ｒ）＝Ｒｅｇ（ｒ，爿）＋Ｃ×Ｄｉｓｔ（ｒ，于）．一】８．（２－９）中国科学技术大学博士学位论文第二：章贝叶斯雹排序Ｉ＾…?巧…电－ ●Ｄｉｓｔ（ｒ，亍）Ｏ‘Ｏ???ｏ…ｏ 吒Ｉ‰图２．２ｒ和哥之间的排序距离的图模型表示．式（２―９）右边的两项分别对应（２―７）中的条件先验和（２一一）中的似然，参数ｃ用于调整两项的作用。在随后的两节中，我们将对这荫项分别进行讨论。２．２视觉一致性正则化 在止则化项Ｒｅｇ（ｒ，疋）中，许多方法都可以用于构建能量函数也（ｒ，ｚ）。在视觉一致性假设下，在半监督学习分类和视频标注中被广泛使用的正则化，例女１］Ｌａｐｌａｃｉａｎ正则化【５１月和Ｎｏｒｍａｌｉｚｅｄ斯重排序。ＬａｐｌａｃｉａｎｉＦ则化【ｆｊ（）】，可以直接用于贝叶如图２．：｛所示，在这两种ｉＦ则化中用样本作为节点构建了图９，两个样本的相 似度作为连接该两样本的边的权重。具体水将，连接样本ｚｉ和ｚｊ的边上的权重Ｗｉｊ通过高斯核Ｗｉｊ＝ｅｘｐ（－学）计算得到，其中口是尺度函数。图２．３ 排序列表的条什先验即ＩＦ则化项的图模型表示。以样本为节点构建图９，眄个样本 的相似度作为连接陔两样本的边的权晕。２．２．１ＬａｐｌａｃｉａｎＪＥ贝ｌＪ化在Ｌａｐｌａｃｉａｎｌｇ贝．１Ｊ化中，能量函数也（，＇，石）定义为似ｒ㈣＝丢∑ｊ ｗｉｊ（ｎ一咿．（２－１０）陔函数从点对（ｐａｉｒ－ｗｉｓｅ）的角度近似ｆ占计ｚｉ的视觉一致性，即累加样木ｚ∥艮其每一１９．中国科学技术大学博士学位论文２．２视觉一致性正则化个邻近样本点≈的加权排序分数差作为该点的视觉一致性。以式（二ｌｏ）作为能量 函数，Ｌ印ｌａｃｉａｎ正则化可以表示为ＲｅｇＬａｐ（ｒ，ｚ）＝∑；砂ｔ（ｔ．，ｚ）＝∑。（去∑，％（ｎ一勺）２）＝ｒＴＬｒ，（２－１１）其中Ｌ＝Ｄ―ｗ是Ｌ印ｌａｃｉａＩｌ矩阵，Ｗ＝№巧ＩＮ×Ｎ Ｄ＝ｄｉａｇ（ｄ）是以ｄ＝【ｄｌ，ｄ２，‘…，ｄＮ］Ｔ为对角线元素的对角阵，ｄｉ＝∑Ｊ％ａ２．２．２ ＮｏｒｍａｌｉｚｅｄＬａｐｌａｃｉａｎｔ贝．１］化Ｎｏｒｍａｌｉｚｅｄ ＬａｐｌａｃａｉｎＩＴ贝ＪＪ化中，也（ｒ，石）的形式与式（２一ｌＯ）类似，不同的是对排序分数做了归一化处理，即地石）２互１－吲而７＂ｉ一黄）２．我ｆｆｊ．－］以得到归一化的ＬａｐｌａｃｉａｎｊＦ则化（２．１２）ＲｅｇＮＬ印（，．，疋）＝∑。如（ｒ，彤）＝∑；（三∑，叫巧（击一素）２）＝ｒＴＬｎｒ，（２．１３）其中Ｌ。＝Ｉ―Ｄ－１／２ＷＤ－１／２，Ｊ是单位矩阵。Ｗ和Ｄ与在Ｌａｐｌａｃｉａｎ矩阵中的定义一致。从式（２―１《））和式（２一１２）巾可以看Ｌａｐｌａｃｉａｎ和ＮｏｒｍａｌｉｚｅｄＬａｐｌａｃｉａｎｉＥ Ｄ！ｌＪ化都是通过计算样本与其邻近样本点对之问的排序分数差异米近似估计排序一致性 的，没有充分考虑样本分布的结构信息。ｊＦ如我们将要在下节巾讨论的，局部学 习正则化将排序分数估计转化为没有任何肩发式假设的学习问题，充分考虑了样 本分布的结构信息。 ２．２．３局部学习正则化 满足视觉一致性假设条件的分数列表ｒ应该具有如下的性质：样本ｚ；和其 附近区域的样本的排序分数在图乡上成该足够平滑。平滑性是定义在整个局部区一２０．中国科学技术大学博士学位论文第＿章贝叶斯重排序域，而不是分别定义在每个邻近点上的。但是从式（２一１０）和式（２一１２）可以看出，在 ＲｅｇＬａｐ和ＲｅｇＮＬａｐ中，仅考虑了样本ｚ｛与其每个邻近样本直接的单个一致性，忽 略了这些邻近样本集中的整体一致性。 为了更好地描述视觉一致性，本节提出从局部学习的角度来考虑这个问 题。给定周围样本及这些样本的排序分数，对于一个足够光滑的图结构（ｇｒａｐｈ ｔｏｐｏｌｏｇｙ），那么中心样本点的排序分数可以很好地由其周围样本的排序分数预测 出来。从这个角度出发，我们可以从机器学习的角度来衡量排序分数一致性。具 体而言，对于样本劫，首先从其周围样本中通过机器学习的方法得到其理想的一 致性排序分数唬。然后通过约束目标排序分数ｎ与豌接近来保证一致性。接下来 将详细介绍基于局部学习的视觉一致性描述模型。对于每个样本Ｘｉ，先从其周同样本集Ⅳ（ｚｔ）＝｛（ｚ”ｒ；。’），翟，中习得到一个局部模犁Ｏｉ（．），其中ｍ是其周围样本的个数。根据模型吼（．）可以得到对中心样本 点的排序分数预测值，然后能量函数蛾（ｆ．，Ｚ）可以定义为该局部模型对中心样本 排序分数的预测误差，即砂ｉ（ｒ，疋）＝（ｎ一仇（ｚｔ））２．根据．卜式得到相应的局部学爿正则化Ｒｅｇｋｃａｌ（ｒ，＂＝∑；帅，ｎ＝∑。ｒｉ咱（戤））２．（２－１４）局部模型Ｏｉ（．）的任务是准确地从周幽样本巾预测出ｚ。的排序分数。很多方法可以用于建立该局部模型，在文献［ｆｉｌ】中采用了简单的线性模型。由于网络视频／图像数据的复杂性，线件模型很难取得很好的效果。为了解决这个问题．我们 利用核技巧的优势提出了局部核模型。这里局部学习明显是一个回归问题，冈此 本文采用易于实现的著名核岭回归（ｋｅｒｎｅｌｒｉｄｇｅｒｅｇｒｅｓｓｉｏｎ）模型【ｆ；２】ｏ在核岭回归中，利用核映射砂（．）将原始空间样本石映射到无限高维的核空间厂，即≯：ｚ∈ｚＨ圣（ｚ）∈厂，然后Ⅳ（ｚｉ）和其相应的排序分数向量 Ｏｉ（ｚ）＝ＷＴ矽（ｚ）．（２―１５），．（‘）＝以”】Ｔ的关系表示为其 ，Ｔ 七 价 函 数 是ｍ∑㈦ｐ（ｒ）一 协似《殂Ｏ２＋ 入加２（２―１６）一．中国科学技术大学博士学位论文２．３排序距离其中入是均衡模型复杂度和｛Ｊｌｌ练误差的参数。 将式（２―１６）对加求偏导然后置零，可以得到伽＝圣ｔ（圣●圣ｔ＋入Ｊ）一１，．（钉，其中圣ｉ表示矩阵眵（ｚ｛‘’）】Ｔ。将伽代入式（２―１５）中，可以得到局部核岭【口ｌ归模型ｏｉ（?）对样本ｚｔ的排序分数预测值：ｏｉ（ｘ１）＝ｔｔ，Ｔ≯（兢）＝ｋＴ（ＡＩ＋Ｋ）一１ｒ（‘）＝砑ｒ（ｎ，（２―１７）其中砑＝庇Ｔ（ＡＪ＋Ｋ）～，向量五。中第歹个元素ｂ＝≯（ｚｔ）Ｔ≯（ｚ，’）＝后（规，ｚ岁’），矩阵Ｋ巾第（ｍ，扎）个元素‰＝妒（ｚ船）Ｔ妒（ｚｇ’）＝七（ｚ黝，ｚｇ’）。值得注意的是，在核方法中只需要定义核函数七（?）而不需要显式地定义≯（?）。本章中采用高斯核作为核函数。将式（２一１７）代入式（２一ｌ、１）中可以得到局部学习正则化，Ｒｅｇ测（ｔ．，ｚ）＝∑。（ｎ－－Ｏｉ（ａｇｔ））２＝∑。（ｐ舒叫２＝Ｔ，ＴＲＬｏｃａｌ’．（２―１８）其中ＲＬ。ｃａＩ＝（Ｉ―Ｂ）Ｔ（Ｊ―Ｂ）－Ｐｅ．局Ｎ学习正则化矩阵。在矩阵Ｂ＝【ｂｏ］ｇｘⅣ中， 如果ｑ∈Ⅳ（ｚ｛），那么６ｕ等于其对应的屈，反之％＝０。２．３排序距离本节将分析现有排序距离中存在的问题，进一步提出‘种新的点对（ｐａｉｒ－ ｗｉｓｅ）排．序距离。为了清晰地阐述这个Ｉ’口Ｊ题，￥文以－Ｎｇ单数据为例进行说明，如表２．１所示。在这个例子中，总共有５个样本点，即｛ｚｌ，ｚ２，ｚ３，ｚ４，ｚ５）；四组不 同的分数列表，即｛，’ｏ，ｒ１，ｒ２，ｒ３｝。对每个分数列表，将这５个样本按照排序分数降序排列即可得到相应的四组排序列表，ｆｏ＝（２ｌ，ｚ２，ｚ３，ｚ４，ｚ５），Ｚ１＝（ｚ５，ｚ４，ｚ３，ｚ２，ｚ１），１２＝（ｚ１，ｚ５，ｚ４，ｚ３，ｚ２），．２２．中国科学技术大学博士学位论文第ｊ：章贝口｝．斯重排序表２．１排序距离的简单示例数据． 样本ｒ０ ｒｌ ｒ２ ｒ３ＸｌＸ２Ｘ３Ｚ４Ｘ５１．００．９ ０．７ ０．７ ０．４０．８ ０．８ ０．８ ０．３０．７ ０．９ ０．９ Ｏ．２Ｏ．６ １．０ １．Ｏ０．１０．６ １．５ ０．５ｚ３＝（ｚ１，Ｘ２，Ｘ３，ｚ４，ｚ５）．为了衡量两个排序分数列表之间的距离，最直接的想法是将每个列表作为一个“实例（ｉｎｓｔａｎｃｅ）”，然后像在排序学习（１ｅａｒｎｉｎｇｔｏｒａｎｋ）中那样利用基于列表的方法来衡量排序距离。在ｆ（ｊ：纠巾提出了一种基于列表的排序距离计算方法，其定 义为两个列表的排序分布的交叉熵。但是，由于对于Ⅳ个样本来说所有可能的排 序方式是０（Ⅳ！），所以该方法计算复杂度过高，我们需要寻求其它简单而有效的 方法来计算排序距离。 ２．３．１基于点的排序距离 衡量排序距离的最简单直接的方法是基于点的方法（ｐｏｉｎｔ―ｗｉｓｅ），即计算每个 样本在这两个排序中排序分数的差值，然后将其总和作为排序距离，即ＤｉｓｔＰ０ｉＩｌｔ（ｒ，于）＝∑；眠蟊）＝∑ｉ（旷栌（２―１９）图２．，ｌ给出了基于点的排序距离的图模型表乃÷。在随机}