信息检索多样化排序算法研究综述

刘兴林

信息检索中用户的多样化需求促进了多样化排序问题的提出，当前国内外多样化排序研究的成果主要分为隐式多样化排序和显式多样化排序，而在用户潜在意图未知的前提下，如何根据用户提交的查询词对信息检索结果文档进行排序，从而最大化程度上满足用户需求，是多样化排序问题研究的核心问题和难点。文章通过对国内外多样化排序研究成果进行分析，归纳了当前多样化排序研究中所存在的一些不足，并指出了在多样化排序领域中可以进行研究的一些方向，特别是多样化排序理论体系的完善和多样化排序系统的构建。

概述

信息检索的主要目的是对信息表示、存储与组织，使用户更容易获得所需要或者感兴趣的信息。信息检索的多样化排序问题对信息检索系统提出了更高的要求。为了满足用户的多样化需求，信息检索系统不能只是简单地根据结果文档与用户输入的查询词之间的相关度来对文档进行排序，必须更深层次地挖掘用户潜在的信息需求，在结果列表靠前的位置中尽可能地提供满足用户各种需求的检索结果。

目前用于分析结果与查询的相关性技术主要有两类：基于内容的相关度计算和链接分析。基于内容的相关度计算属于传统信息检索领域的分析方法，多采用向量空间模型、概述模型等方法来逐一计算结果文档与用户查询的相关度。面链接分析则是针对互联网文档富含超链接的特点，通过对链接进行分析获得高质量的结果文档，包括著名的Google 搜索引擎所采用的PageRank 算法和Kleinberg 提出的HITS 算法等。排序学习方法是近几年才兴起的一类排序方法，它的本质是利用机器学习的思想来解决信息检索系统中如何对检索结果进行排序的问题，它利用机器学习整合大量特征的优势，同时把大量的基于内容相关性的特征和链接结构信息的特征融入到排序模型中，通过对大量样本数据的学习，能取得较好的排序效果。

排序方法是互联网信息检索的核心，在传统的信息检索研究中，有一个重要的排序原则，称为概率排序原则，即：

定义1-1：概率排序原则。如果一个检索系统返回给提交查询的用户的结果列表是根据文档对于用户有用的概率从高到低进行排序的，当这些概率的估计尽可能的正确时，那么这个检索系统的总体效率对用户来说是最高的。

然而概率排序原则有一个重要的假设，就是相关度独立假设，即不同文档与查询的相关度之间是相互独立，互不影响的。但在现实的搜索情境中，这个假设往往并不成立，在用户搜索过程中，用户对于文档的相关度判断会受到他已经浏览过的文档的影响。

用户在进行信息检索时都是抱有一定的意图的，需要信息检索系统返回一定的文档以满足用户的意图。这种意图可以表示在查询多义情况下的各种解释，也可以表示同一个解释下不同方面的信息。本文把意图定义为用户查询需求中的最小基本单位，而与之对应的，可以满足用户意图的信息集合，则定义为信息面（facet）。在此基础上，对多样化排序问题进行形式化。

问题1-1：多样化排序问题。给定用户查询q，对应的理想的用户查询意图集合为I={c1，c2，…，cm}，侯选文档集合D={d1，d2，…，dn}，每个文档都可能满足一定的用户需求。假设用户只浏览检索结果列表的前k 个文档，多样化排序问题的目标就是最大化从集合D 中选择一个不大于k 的文档子集Ds，使得Ds 中至少有一个文档可以满足用户的意图的概率，即

其中，p（d|q，ci）表示文档d 满足查询词所蕴含的意图ci 的概率。需要说明的是，虽然在现实信息检索过程中，用户看到的结果是列表，是与位置相关的，但由于本文假设了用户会浏览前k 个文档，因此文档集合与文档列表的意义就没有差别了。

多样化排序是一个NP 难问题。如果用户潜在意图集合已知，各文档所能满足的用户意图的程序可以进行估算，那么，多样化排序问题可以用简单的贪心近似算法进行求解。

但对于一个信息检索系统来说，不仅用户输入查询词所蕴含的意图是难以判断的，就连一个查询所可能蕴含的意图集合也是不容易估计的，这就为解决多样化问题带来了困难。在用户潜在意图集合未知的情况下，如何根据用户提交的查询词对结果文档进行排序，以最大化用户的满意度，成为了多样化排序问题研究的核心问题和难点。

国内外研究现状

现有的多样化排序研究工作分别从不同的角度对多样化问题进行剖析和解决。以是否对查询词所蕴含的用户意图进行建模作为区分，现有的研究工作主要可以分为两大类，分别是隐式多样化排序方法和显式多样化排序方法。较早的研究工作都是隐式多样化排序方法居多，这类方法不直接对查询词所蕴含的用户意图进行建模，而是基于一定的假设估计文档在信息蕴含上的差异，通过文档之间的相似度比较，或选择文档进行词空间覆盖等思路达到多样化排序的目的。而显式多样化排序方法则是近几年才兴起的一类研究方法，这类方法直接把多样化排序建立在用户意图已知的基础上，显式地利用了用户意图的存在，通过探索文档与用户意图的相关性，作为实现多样化排序的基础。

基于文档相似度比较的隐式多样化排序方法是最早涉及多样化排序问题的研究工作。顾名思义，这类排序方法把实现多样化的目标建立在文档之间的相似度比较的基础之上，其主要假设是相似的文档往往蕴含的信息面是相似的，也就是说它们所能满足的用户意图也是类似的。用户在浏览搜索结果的过程中，如果用户已经浏览过的文档无法满足用户的需求，那么与这些文档相似的文档能够满足用户意图的可能性就大降低了。因此，该类方法基于文档之间的相似度，在给文档进行排序时，通过降低与已排序文档相似度较高的未排序文档的排序位置来达到多样化的目的。这类方法的关键就在于如何通过对未排序文档和已排序文档集合的相似度进行合理的比较，以增加结果列表中靠前位置上的文档的多样性。

与基于文档相似度比较的多样化排序方法把分析的重点放在文档层面上不同，基于词空间覆盖的隐式多样化排序方法从更细的层面—词的角度入手，它们用词空间来表示与查询词相关、能满足用户不同意图的信息集合。由此，多样化排序问题就演化成了如何选择限定大小的文档子集对词空间进行覆盖以满足用户各种潜在意图的问题。这类方法认为，由于文档数量受限，因此不同的词被覆盖的重要性是不同的，要最大化对各种信息面的覆盖，必须选择文档尽可能多覆盖那些重要的词。于是它们在对词的重要性进行估计的基础这，可以根据与词之间的关系，通过选择文档子集最大化对加权词空间的覆盖，实现多样化排序。

与上面两种隐式多样化排序方法不同，显式多样化排序方法都是假设存在（或者可以获取）查询词所蕴含的用户意图集合，在此基础上，采用各种方法综合考虑文档与各种潜在意图的相关度以及各种潜在意图的重要性，通过选择文档子集优化相应的目标函数实现多样化排序。这类方法的关键点有两个：一个是如何挖掘（估计）查询词所蕴含的用户意图集合；另一个则是如何利用潜在意图集合的信息，对文档排序以满足用户的多样化需求。现有的显式多样化方法主要包括两类方法：一类是离线的方法，即先从查询词或者候选文档集合的内容估计用户的潜在意图集合，然后通过各种排序算法提供确定的多样化文档子集给用户；另一类则是在线的方法，根据用户的点击反馈在线学习用户的潜在意图，动态调整文档排序，在与用户的不断交互中实现多样化排序。

隐式多样化排序方法研究现状

最早的多样化排序的工作是Carbonell 等人在1998年提出的MMR 方法，即最大边际相关度（Maximal Marginal Relevance）方法。他们首次提出把文档与查询词的相关度和文档的信息新颖度结合起来对文档进行排序，在保持文档与用户查询相关性的同时，可以减少由于只根据与查询词的相关度进行排序而可能造成的文档信息的冗余。他们定义一个文档的边际相关度为文档的查询相关度与信息新颖度的纯属组合，两者用一个参数进行调优。其中文档的信息新颖度由该文档与已排序文档的最大相似度决定，相似度越大，新颖度越小。在对文档进行排序时，迭代选择边际相关度最大的文档可以在一定程度上减少文档的信息冗余。MMR 方法的提出对于多样化排序的研究有着重要的意义，后续的许多工作也是基于MMR 这种多样化排序策略的。

把MMR 排序策略与统计语言模型结合起来，Zhai 等人提出了多种多样化方法。他们利用统计语言模型，对结果文档的查询相关度和新颖度进行建模，提出敢基于K-L Divergence 和混合主题模型的六种文档新颖度计算方法，并在基础上结合相关度排序方法进行多样化，以解决他们提出的了主题检索问题。

与子主题检索不同，Zhang 等提出在进行多样化排序进既要考虑文档的多样性，也要考虑文档的信息丰富程度。多样性衡量的是一个文档集合所包含的不同的主题数，而信息丰富程度则衡量的是一个文档所包含的不同的主题数。在此基础上，他们提出了一种多样化排序方法Affinity Ranking，首先根据文档之间的相似度构建有向关系图，用类似Pagerank 的方法在图上计算文档的信息丰富程序；接着在对文档进行排序时，根据文档与已排序文档的相似性对文档的信息丰富程度值做一个惩罚因子，从而把信息丰富程序和多样性结合起来对文档进行排序。

类似地，Goldberg 等人也提出了一种通过用文档之间的相似度构建加权图，以利用文档之间的相似度比较促进多样化的算法Grasshopper。不同的是，他们把文档集中性（与信息丰富程度类似）、多样性和用户偏好三种因素统一起来考虑，利用具有成熟理论基础的吸收马尔可夫阴随机游走（Absorbing Markov Random Walks）框架，提出了一种基于MMR 策略的多样化算法。该算法首先根据马尔可夫链的随机游走选择第一个文档，然后通过把已排序文档设置为吸收态，根据吸收马尔可夫链的特性拉低与已排序文档相似的文档的排序位置，从而达到多样化的目的。

Gollapudi 等人在他们所提出的公理化框架下，提出了三个多样化排序的优化目标函数，并对三个目标函数进行了公理化分析。三个目标函数都是把文档与查询的相关度函数以及文档之间的距离函数融合在一起进行优化，他们把其中的两个目标函数还原为设备分置（Facility Dispersion）的组合优化问题，利用现有的两种贪心近似优化算法分别进行解决。此外，他们还强调文档间的距离函数是多样化方法的关键，因此他们采用了两种新的距离函数，分别是基于最小哈希的语义距离和基于分类树的类别距离。

除了从文档级别的角度进行多样化排序之外，还有一类隐式多样化排序方法是从词的角度入手，通过最大化词空间覆盖的方法达到多样化的目的。Swaminathan 等人首先从词的角度入手，提出了Essential Pages 方法以减少文档列表的信息冗余。他们定义关键页面（Essential Pages）为最大化与查询相关的信息覆盖度的文档（页面）子集合。为了优化关键页面的选择，他们提出了一个基于SFFS 算法的文档选择算法，通过最大化所选择的结果文档子集的联合覆盖值来实现文档列表的多样化。类似地，Yue 等人也是通过选择文档最大化加权词空间覆盖的方式实现多样化排序的，但他们提出的多样化排序方法SVMdiv 是基于监督式机器学习中的结构化SVM 框架的，好处是可以利用丰富的特征，通过训练得到多样化排序模型。他们提出了以最小化加权子主题代价作为优化的代价函数，并且根据词出现频率、位置等设计了多项特征，在训练时最小化经验风险以学习得到最终的多样化排序函数。

除了词之外，Lad 等人提出一种更为抽象的概念——信息块（Information Nugget）对信息空间进行定义。他们提出多样化问题可以看作是期望全局效用（Expected Global Utility）的最大化问题。该目标函数的定义具备几种特性：它可以同时衡量文档的相关性和新颖性；它更注重排序位置靠前端的文档；它可以衡量多种不同程度的冗余。而期望全局效用是定义在信息块的基础之上的，他们在文章中用词和命名实体表示信息块，通过用户反馈在线学习信息块的权重，通过贪心算法迭代选择文档对目标函数进行寻优，以获得多样化排序。

此外，Chen 和Karger 还提出用概率的方法解决多样化问题。他们假设侯选排序文档根据查询词可以分为相关文档和不相关文档，而且它们服从不同的概念分布，为了实现多样化排序，他们提出的目标函数是最大化在排序列表前n 个文档中找到至少k 个相关概率，并基于EMP 原则（Experted Metric Principle）设计了一个贪心算法进行优化。当k 为1 时，在算法对文档进行选择的每一次迭代中，算法总是假设前面已排序文档与查询词是不相关的，在此条件下，选择与查询相关概率最大的文档作为下一个排序文档。

显式多样化排序方法研究现状

与隐式多样化排序方法不同，显式多样化排序方法都是假设存在（或者可以获取）查询词所蕴含的用户意图集合，在此基础上，通过对各个文档与各种潜在意图之间的相关度进行建模，最终根据相应的目标函数选择文档集合以满足各种不同的用户意图。为了更好地进行多样化排序，显式多样化方法需要尽可能正确地挖掘潜在的用户意图，现有的显式多样化方法主要采用两类方法：一类是从查询词或者侯选文档集合本身的内容进行挖掘，另一类则是根据用户的点击反馈进行在线学习。

Agrawal 等人试图在已知查询和文档的类别信息的情况下，提出把最大化平均用户在排序结果列表的前k 个文档中找到至少一个相关文档的概率作为多样化方法优化的目标函数，并提出了一个贪心算法IA-Select 进行求解，从而达到多样化的目的。他们选择开放式分类目录搜索系统（Open Directory Project）上的分类目录作为基准类别信息，查询词的类别分布采用文献中的算法来获取，而文档的类别，即文档与各种用户意图的相关度，则用Rocchio 分类器进行估计。

Carterette等人针对他们提出的信息面主题检索问题，提出了一个概率模型，通过最大化排序文档对各种信息面覆盖率实现排序结果的多样化。模型包括了三部分：首先是通过基于LDA 和相关度模型的主题模型对信息面进行估计，然后估计文档与信息面的相关程度，最后通过最大化文档子集中至少有一个文档包含信息面的概率来获得多样化的效果。

Santos 等人则提出了一个用于多样化排序的概率框架xQuad。在该框架中，他们首先挖掘查询词所蕴含的子查询（Sub-query，即各种潜在意图），根据文档与子查询的相关度估计文档间的相似度，然后根据四个因素进行多样化。这四个因素包括子查询的重要性、文档对子查询的覆盖程度、文档的新颖程度和文档的查询相关度。其中，文档的新颖度是通过文档与尚未覆盖得很好的子查询的相关度来确定的。而具体到对于子查询的挖掘工作，在文献中，他们先利用k-means 算法对文档进行聚类，再通过查询扩展模型从每一类的文档中选取最有代表性的词集作为子查询；而在文献中，他们则是提取现有搜索引擎所提供的相应查询词的相关查询和查询建议作为子查询。

前面几种方法都是从查询词或者文档集合中挖掘用户的潜在意图，而Radlinski 等人则通过用户的点击来确定用户对文档的需求。他们提出了一种在线多样化排序方法，根据用户的点击反馈，动态调整模型，从而不断地更新排序列表，以满足用户的各种需求。这种方法的好处是把对潜在意图的估计完全交给了用户，这样既可以准确地估计用户的意图，也能适应用户的意图的动态变化。不过，该方法需要与用户进行一定的交互之后才能获得对用户意图的较好的估计，而在这之前，该方法的多样化效果不会太好。

多样化排序问题分析

总的来说，随着众多学者对互联网信息检索的多样化排序问题的研究，该问题的本质和关键问题也逐步被揭开面纱。现有的研究工作中包含了不少突破性的成果，但目前还存在着一些问题，总结起来，有以下几点：

（1）对多样化排序方法的研究居多，而相应的理论分析则较少，尤其是对隐式多样化的排序方法的分析。

（2）现有的基于词空间覆盖的隐式多样化排序方法中，在选择文档对词空间进行覆盖时，都是独立地考虑词被覆盖的重要性，没有考虑词与词之间的关系以及由此引申出来的词的边际效应，这样的排序结果可能会存在一定的信息面冗余。

（3）现有的离线显式多样化排序方法从系统的角度对用户查询的潜在意图集合进行估计，其准确性和完整性还有待进一步提高，且由于提供的是比较固定的排序列表，无法适应用户的意图迁移。

（4）现有的在线显式多样化排序方法虽然可以通过与用户的交互获得对用户意图的较为准确的估计，但现有方法的收敛速度较慢，早期难以满足用户的需求。

研究方向和热点

（1）探索更合理更有效的多样化排序方法。分别从隐式多样化排序方法的关键问题——如何挖掘文档的信息面覆盖差异性、显式多样化排序方法的关键问题——如何估计用户潜在总图集合入手，解决现有排序方法所存在的问题，提出更好的多样化排序方法。

（2）建立并完善多样化排序问题的理论体系。当前的多样化排序研究工作以方法的研究居多，而相应的理论分析则较缺乏，尤其缺少对隐式多样化排序方法的分析。

（3）构建简单实用的多样化排序检索系统。多样化排序研究主要基于互联网信息检索，因此，多样化方法既要考虑效果，又要考虑运行效率，构建一个实用的多样化排序系统，更具有现实意义。