检索结果多样化研究综述，本文主要内容关键词为：，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
doi：10.3772/j.issn.1000-0135.2015.007.012 1 引言 传统信息检索系统的目的是尽可能多地返回与查询相关的文档，其中基于概率排序原则(Probability Rank Principle，PRP)的排序方法能够满足这种需求。然而随着网络信息的爆炸式增长，不可避免地会有许多相似的文档，甚至有些文档完全是另外一些文档的副本[1]。在这种环境下，不考虑文档间相似性的传统概率排序算法，可能为检索系统返回一个高度冗余的查询结果列表。在现实的网络检索情境中，用户输入的查询词一般都较短，但往往有着不同的需求；同时考虑到一种极端情况：结果列表是高度冗余的，即第一页的结果列表中的结果都是相似的，如果第一个结果无法满足用户的信息需求，那么结果列表中排在前面的所有结果都将无法满足用户的信息需求。这种情况下，就需要检索系统能够返回一个多样化的结果列表，降低检索结果的冗余，即实现检索结果多样化(Retrieval Diversification)，以更好地满足用户多样化的信息需求。 近年来，一些检索国际会议如SIGIR、ECIR和TREC等都有关于检索结果多样化的文章，TREC还专门设置了检索结果多样化的测评任务，集中就检索结果多样化的方法和评价进行探讨。本文在对用户检索多样化需求进行分析的基础上，探讨了检索多样化的定义，并进而对检索结果多样化研究的方法和评价指标做了介绍。 2 检索结果多样化的定义 多样化的思想最早来源于1964年Goffman[2-7]提出的“一个文档的相关性也应该由该文档与之前文档的相关性来决定”。1982年Boyce[9]对该思想进行了重新阐述，认为最相关的文档应该是专指的、新颖的。1998年Carbonell等[1]首次提出了一种检索结果多样化方法，使系统能够返回一个多样化的结果列表，尽可能避免排在前面的文档没有一个能够满足用户需求的情况。对于检索结果多样化的定义，Drosou等[10]进行了以下总结，分别从内容(Content-based)、新颖性(Novelty-based)以及覆盖度(Coverage-based)三个角度对检索结果多样化进行了概念界定： (1)基于内容的定义将结果多样化看做是返回的结果列表中的文档之间，在内容上具有不相似性，其中，文档之间的不相似度越高，那么结果列表的多样化程度也就越高。许多隐式的结果多样化方法都是从该角度进行研究以实现结果的多样化。基于该定义的多样化方法已经被应用于实现推荐系统中推荐内容的多样化[11]。 (2)新颖性的概念比较接近于多样性，有学者[6]对新颖性和多样性进行了区别，新颖性就是解决结果列表的冗余问题，而多样性就是解决查询歧义的问题。基于新颖性的一类结果多样化定义是指所返回的当前文档相对于之前的文档来说，要含有新的信息。许多学者基于此定义的思想对多样化方法进行了探索，如Carbonell[1]、Zhai[12]等。 (3)基于覆盖度的定义从一个新的角度，即文档对查询不同解释或者方面的覆盖来考虑结果的多样化。结果列表好的文档对查询的不同主题覆盖的越高，那么该结果列表的多样化程度就越高。越来越多的学者基于该类定义提出了许多结果多样化的方法，如xQuAD[13]。 图1从覆盖度的视角展示了传统信息检索结果与多样化信息检索结果的差异。图1(a)为传统信息检索的结果，结果列表中的文档只是覆盖了查询的非常流行(popular)的子主题，一旦第一条结果不满足用户需求，其他结果也无法满足；图1(b)为多样化信息检索的结果，其不同文档覆盖了查询的多个不同的子主题，若第一条结果无法满足用户需求，其他覆盖查询不同子主题的结果仍可能会满足用户需求，这将大大降低检索结果无法满足用户不同需求的风险。
图1 传统信息检索结果与多样化信息检索结果差异 此外，Radlinski等[2]还从需求的角度将多样化分为外在的多样化(Extrinsic Diversity)和内在的多样化(Intrinsic Diversity)。其中，外在的多样化是指信息需求具有不确定性，需要检索结果的多样化来降低这种不确定性可能带来的无法满足用户信息需求的风险，这种不确定性主要来自于查询自身的歧义和用户的不确定性。而内在的多样化是指多样化是信息需求的一部分，即用户的某些信息需求需要多样化的信息来满足。 其中，造成外在多样化的原因其一是查询词本身的歧义[3]。查询词往往有不同的解释(interpretations)，如“土豆”，既可指一种蔬菜，又可指中国的一个视频网站。因此要考虑返回多样化的结果来覆盖查询的不同解释，以满足不同用户的不同需求。一些学者也通过实验研究证明了现实检索中用户提交的很多查询是有歧义的。如Song等[4]在2009年基于真实的查询日志数据，用人工标注和机器学习的方法分析了用户提交的含有歧义的查询的比例，研究发现用户提交的查询中16%的查询词都是含有歧义的；Sp
rck-Jones等[5]也研究发现不同查询的歧义程度也不同。其二是指用户的不确定性。即使查询是确切，没有歧义的，查询也往往含有不同的方面(aspects)。如“糖尿病”这个查询，可能包含糖尿病的百科解释、好的治疗糖尿病的医院以及治疗糖尿病专家等不同的方面，对于医生和患者这样不同的用户群体，他们的需求可能是不同的，在无法明确用户群体的前提下，提供多样化的检索结果能够满足更多用户的多样化信息需求。 如上文所述，内在多样化需求需要多样化的信息来满足[2]，这些需求主要有：①仅有一条结果无法满足用户的信息需求；②用户希望得到不同的观点，例如对于某个产品的不同的评价，或者对于某个政治问题的不同的评论；③用户希望从不同的结果中做选择，例如搜索“戴尔电脑价格”时，用户希望可以从不同的供应商得到不同的价格信息，以此做出选择；④需要了解关于某个主题的综述；⑤需要不同来源的不同结果来验证某个信息需求问题的正确性。Clarke等[6]认为在这种需求下，多样化就是返回更多新颖的(novelty)信息来满足用户的信息需求。 虽然目前多数学者是基于解决查询歧义的需求而提出的实现多样化的方法。但是基于以上的外在的和内在的信息需求，都要求通过检索结果的多样化来满足用户的这些信息需求。检索结果的多样化可以更好的及最大可能的满足用户的这两类需求。Clough等[7]研究证明，通过检索结果的多样化至少可以改善9.5%～16.2%的查询的检索结果。 无论从哪个角度对检索结果多样化进行定义，其从根本上都可以形式化为：给定一个查询q，要返回一个多样化的结果集合R(q)，R(q)中的文档既与q有较大的相关性，又有较小的冗余度并且能够覆盖q的不同方面。结果多样化的目的就是要降低用户无法获得相关信息的风险，尽可能保证结果列表中有满足用户需求的记录。 3 实现检索结果多样化的方法 目前普遍认可的检索结果多样化方法的分类将其分为隐式(implicit)多样化排序方法和显式(explicit)多样化排序方法两类[13]。本文也将从这两类方法对目前的多样化的方法进行介绍和评述。 3.1 隐式多样化排序方法 隐式多样化排序方法从文档本身的角度来判断文档之间的不相似度，不停的迭代来发现既与查询相关又与已被排序的文档不相似的文档。 在前人思想的基础上，Carbonell等[1]1998年时提出来一种经典的实现结果多样化的方法MM(Maximal Marginal Relevance)。他们首次提出把文档与查询的相关度和文档信息的新颖度结合起来对文档进行排序，在保持文档与查询相关性的同时，可以减少由于只根据与查询的相关度进行排序而可能造成的文档信息的冗余。模型中定义了一个文档的边际相关度为文档的查询相关度与信息新颖度的线性组合，两者用一个参数进行调优。其中文档的信息新颖度由该文档与已排序文档的相似度决定，即相似度越大，新颖度越小。在对文档进行排序时，迭代选择边际相关度最大的文档可以在一定程度上减少文档的信息冗余。具体公式见公式(1)。
隐式的多样化方法大多都是基于MMR模型进行改进的，不同之处是对于文档间相似度的计算。例如，Carbonell等[1]基于内容的相似度计算方法，将检索到的文档表示成向量，进而计算向量之间的距离来表示文档的相似度；Zhai等[14]通过语言模型框架来对相关性和新颖性进行建模；Zhang等[15]提出一种根据文档内容构建图的方法，增加结果列表的信息丰富度以及多样化程度；Zhu等[16]提出了一种基于吸收马尔可夫链(absorbing Markov chain)的随机游走的算法，将已排序的项定义为吸收态，降低包含与已排序项相同的文档的重要程度；Kaptein等[17]提出一种运用一个长度为n个文档的滑动窗口，采取自上而下过滤的方法来实现检索结果的多样化。窗口内的文档之间的多样化指标通过文档中包含新词的个数或者链接的相关关系来判断；Kharazmi等[18]仅利用文档检索值(retrieval score)之间的差距来表征文档与文档之间内容上的差异。 也有学者在丰富原有查询结果后运用MMR方法进行结果的多样化，如张语晨等[19]首先构建子查询，用构建好的子查询进行检索从而丰富检索结果，再用MMR方法进行重排序，最终得到一个多样化的检索结果。 还有部分学者借鉴其他学科的相关理论，将其运用到检索结果多样化的排序中来。其中Wang等[20]将经济学的现代投资组合理论引入到检索模型中来，认为检索中的排序与经济环境中投资行为的假设相似，都面临一定的不确定风险，期望达到最优的结果，而且各个投资最后产生的效益是相互影响的，这也类似于多样化排序中要考虑已排序文档与待排序文档之间的相似度。所以他们在现代投资组合理论的启发下，在传统的PRP基础上，线性综合了文档与查询的相关性，以及文档之间的相似性。但是他们考虑的不是待排序文档与之前一个已排序文档之间的相关性，而是考虑了与之前所有文档之间的相关性，与MMR相比取得了很好的效果；此外，Zuccon等[21]借鉴了运筹学(Operations Research)的设施选址问题(Facility Location Analysis)。他们认为之前的许多方法都是把top-k文档看做是类似于军火库等危险设施，需要将它们之间的距离设置的越远才能在某一处发生事故时，将可能危及其他设施的风险降到最低。而他们将top-k中的每一篇文档看作是一个个类似于医院的好设施(facility)，用户往往会选择最近的设施，这些设施距离用户越近越好。将这些设施设置在每个地区的中心位置，就能保证距离每个用户较近的位置会有一个设施。在此思想的基础上，就可以把排在前k位的文档看做是所有与查询相关的信息的简单总结，用户从这k篇文档中总会找到自己需要的信息。同时新颖性和多样性将会得到提高。所以相应的模型就是给出一个包含前k篇文档的原始结果集R的子集S，迭代的判断S中的某一篇文档d与其他文档之间的距离f(s)是否大于S外的一篇文档d’与S中除d外的文档之间的距离f(s’)，若f(s)＞f(s’)，则文档d将被文档d’取代。直到结果集S不再改变为止。实验也通过ERR-IA等评价指标证明该方法的有效性；陈飞等[22]对网页链接分析算法HITS进行分析后发现，算法中的Authority与Hub在评价文档可能满足用户多样性需求方面的特性，并且利用这样的特性，提出了新的文档重排序方法以实现查询结果的多样化。 以上的方法都是基于MMR的思想上提出的改进方法，并分别通过实验验证了这些方法的有效性。其中，方法[20、21、22]考虑将其他学科的相关理论运用到多样化的检索中，从而给相关研究带来了启发。然而这些方法仅考虑文档在内容上的相似性，并尽可能返回内容上不相似的结果，但并没有从查询的角度出发，去考虑用户真正的多样化需求是什么。尽管这些文档在内容上是多样化的，但是并不能很好地满足用户的多样化需求。所以，学者开始研究如何从查询角度出发，显式的运用与查询相关的子主题(sub-topic)来实现检索结果的多样化，即显式多样化排序方法。 3.2 显式多样化排序方法 显式多样化排序方法是指显式的考虑与查询相关的不同解释和不同方面，返回能够覆盖与查询相关的不同子主题的文档来实现检索结果的多样化。该类方法也是基于MMR思想改进的方法。这类方法主要由两个步骤实现：①抽取查询相关的子主题；②利用子主题对文档进行多样化排序。 3.2.1 子主题抽取方法 Wang等[23]于2013年对子主题挖掘的方法进行了总结研究。内部抽取方法主要有：①聚类的方法；②主题分类的方法；③概念标签方法。外部抽取方法主要有：①基于本体的方法；②查询日志的方法；③基于关联搜索的方法。 上述提及的内部抽取和外部抽取方法是He等[24]根据抽取来源的不同将子主题抽取归纳为内部抽取和外部抽取(表1)。 子主题的抽取结果直接关系到最终的多样化结果的好坏。目前学者对子主题的抽取来源和抽取方法都进行了研究和总结。然而针对不同的来源是否有相应的最佳抽取方法；当抽取来源较多时，是否需要考虑各个来源的重要程度；如何更好地整合抽取自不同来源的子主题；如何实时感知查询的不同子主题随时间变化其重要程度的改变等，都是需要进一步研究的问题。 3.2.2 显式多样化排序模型 利用子主题对文档进行多样化排序比较有代表性的是Santos等[13]提出的xQuAD模型和Dang等[37]提出的PM2模型。 (1)xQuAD模型 Santos等[13]在Jones等[5]的启发下认为模糊查询词的不同解释同时也表示可能的用户需求，所以他们提出来一种xQuAD(explicit query aspect diversification)的模型框架，为每一个模糊查询构建一个含有多个子主题的集合，其中每一个子主题都表示了原始查询的一个可能的潜在信息需求。他们通过以下4个方面来实现检索结果的多样化：①子主题的重要性。即获取的子主题与原始查询的相关程度。②文档对子主题的覆盖度。即文档与各个子主题之间的相关性。③文档的新颖性。通过文档与尚未被已排序文档覆盖的子主题的相关性来确定。④文档的相关性。即文档与原始查询的相关性。具体见公式(2)：
其中，Q表示查询q的子主题
的集合，S表示重排序后的结果集合。λ是相关性和新颖性的调节参数。
实验表明，xQuAD框架模型是目前比较好的一个显式多样化排序方法，在2010年的TREC评测会议上也取得了最好的多样化效果。Santos在之后的研究[38，39]中也对xQuAD方法进行了改进和完善。 Santos等[38]还提出了一种自动根据查询的不同歧义程度，选择不同的调节参数值来达到最佳的检索效果。关于平衡相关性和多样性的调节参数，之前的方法[1，12，20，28]中都是通过一些查询的训练得出一个最优的参数值。但是他们认为考虑到每个查询歧义程度的不同，其多样化的策略也不同，参数也应该不同。所以，Santos提出一种有监督的方法，对查询进行最优的参数标注，然后根据特征集和已被标注的查询得到回归模型，再运用模型来预测每一个“看不见”(unseen)的查询的最优调整参数。将参数加入每个不同的xQuAD模型的计算中，从而达到更优的多样化结果。 进一步的，Santos等[39]认为，即使相同的子主题，不同的用户也会有不同的查询主题。因此它们将子主题分别标注为不同的用户意图，如事务类、导航类和信息类，并进而获取与查询相关的用户意图集合，并考虑文档对这些用户意图的覆盖程度来实现检索结果的多样化。 林古立等[40]从结果文档中抽取关键词，根据关键词的共现性以及关键词对文档的描述能力，计算出结果文档的信息面新颖度，结合新颖度和相关度对文档进行重新排序。进一步从基于信息空间覆盖的角度人手，提出了一种新的基于关键词的多样化排序原型KED，实现检索结果的多样化[41]。 (2)PM2模型 该方法认为结果列表中返回的覆盖某一主题的文档数和该主题在各查询相关主题中的流行度(重要程度)成正比。比如说，对于查询“java”来说，传统的排序方法返回的结果中，有90%的文档是和java这种编程语言相关的，10%的文档是与java这个小岛相关的。那么如返回前十个文档，则最好应该有9个文档是与java这种编程语言相关的，1篇文档是与java岛相关的。 PM2模型是针对竞争政党之间分配席位(seat allocation problem)问题而产生的。但是与现实中的政党席位分配不同的是，在检索结果多样化中，需要考虑以下两个问题：①某一篇文档可能包含多个不同的主题；②选择一个与某一主题相关的文档，尽管该主题已经有足够的文档已经被选择，不会比选择一个与查询不相关的文档产生更坏的结果。 因此，该方法主要通过以下两个步骤实现：①先运用Sainte-Lague公式[42]，选出将要为某一个位置分配的与查询相关的某一个主题
；②根据文档与该主题的相关性以及与其他主题的相关性来选出最合适的被分配到该位置的文档。第二部分的计算详见公式(3)：
其中，qt是quotient的缩写，
表示某一主题i的重要程度，P(d|t)表示文档与某一主题的相关性的概率假设，λ是文档与当前主题的相关性以及该文档与其他主题的相关性的调优参数。 Dang等[43]认为抽取某个主题的相关子主题是当前比较困难的课题。为解决该问题，他们首先提出一种假设，如果一个文档相对另外一个主题来说与主题A更相关的话，那么该文档也与和主题A相关的词汇更相关。于是他们在假设的基础上提出一种基于词级别的多样化方法，即运用简单的贪心算法自动从待排序的相关文档中获取与主题相关的词汇集合，分别在xQuAD和PM这两种框架模型上进行了实验，以此验证这种方法的有效性，其实验结果表明这种考虑主题词的方法要优于考虑完整的子主题的方法，同时也证明了PM方法的优越性。 与PM方法思想相似的，高景斌在其硕士毕业论文[44]中提出了一种基于子意图识别的检索结果多样化方法。首先从搜索引擎中获取子意图集合，并计算他们的权重关系。接着用显式和隐式结合的方法对文档进行重排序，以此来实现结果的多样化。 除以上两种目前最有代表性的方法外，许多学者也从其他角度提出了多样化的方法。如Carterette等[45]提出主题分面检索(faceted topic retrieval)的概念，即假设某一个查询有唯一一个明确的解释，但是对于该解释又包含不同的方面，主题方面检索的目的就是要能够返回尽可能少的文档来覆盖尽可能多的不同方面，实现检索结果的多样化；Radlinski等[46]对前100条结果进行重排序来实现检索结果的多样化。通过分析来自流行的搜索引擎中的某一段时期内的查询日志，发现与查询相关的词，进行查询重构。利用查询重构后的查询进行检索获取总量为100的文档，运用Teevan等[47]提出的相关反馈(relevance-feedback)的方法进行重排序，得到多样化的结果；Yin等[29]提出一种基于知识集和用户日志构建查询相关子主题的模型来生成多样化的检索结果。从查询日志和知识集中挖掘相关子主题，计算其权值。并将这些子主题作为查询利用BM25进行检索，将子主题权值以及BM25值进行线性结合来对各个子主题检索到的所有文档进行重排序，来得到多样化的结果；Bi等[48]将搜索引擎检索到的文档运用K-Means算法进行聚类，每一个类簇表示一个子主题，再根据文档对子主题的覆盖程度运用Zhai等[12]提出的贪心算法对文档进行重排序，聚类越大的子主题，返回的相关的文档数越多。 此外，还有一部分学者从机器学习的角度对检索结果多样化进行了研究。如Radlinski等[49]提出一种在线学习的方法RBA(Ranked Bandit Algorithm)，可以直接根据用户的点击行为学习生成一个多样化的检索结果。 马千里等[50]在RBA算法的基础上，利用文档之间的相似性，提出了一个基于聚类和用户点击的在线多样化排序算法CRBA(Cluster-Based Ranked Bandit Algorithm)。与RBA不同的是他们首先对候选文档进行主题聚类，再根据用户在线反馈进行重排序。 4 评价指标 传统的信息检索的评价方法主要关注于对相关性的评价，然而在结果多样化的问题中，除了要考虑文档与查询的相关性，同时还要从多样性的角度来对多样化的结果列表进行评价。Turpin等[51]指出查全率、查准率、MAP、DCG等这些传统的评价指标并不一定与用户的满意度是相关的。一个很重要的原因可能是考虑极端的情况返回更多的相似文档会提高MAP值，这种情况下，检索结果列表是高度冗余的，对用户来说并不是最佳的结果列表。 所以，许多研究者在传统的多样化评价指标的基础上，进行了拓展来评价多样化的检索结果。Chandar等[52]主要考虑以下4个方面来对检索效果进行评价：①找到相关文档的能力；②对相关文档进行排序的能力；③满足多样化需求的能力；④对文档进行排序满足多样化需求的能力。针对①和③的评价指标主要有查全率和查准率，以及多样化评价中的关于子主题的查全率和查准率的评价。本文将介绍三种同时评价查询系统的多样化能力和排序能力的指标，分别为：MAP-IA，α-DCG，和ERR-IA。这三种指标也是TREC中评测多样化任务(diversity task)的官方评测指标。 (1)MAP-IA 该指标是Agrawal等[27]提出的基于用户意图的评价指标，是对传统的MAP方法的拓展，单独的计算每个子主题用户意图的MAP值，然后计算子主题的加权平均值。计算公式如下：
该指标是由Clark等[6]提出的对DCG进行拓展的一种评价方法，该方法奖励含有新发现的子主题文档的α-nDCG值，惩罚包含已有子主题文档的α-nDCG值。其中α是一个惩罚子主题冗余的变量因子。该方法被用于2009年的TREC中对diversity task的评价。 (3)ERR-IA 该指标是由Chapelle等[53]提出的一种评价指标。在该指标中，根据与排在某一文档之前的文档的相关性来评价该文档。与MAP-IA相似的是，也是单独的计算每个子主题的ERR值，然后计算子主题的加权平均值。 还有许多学者根据自己提出的多样化模型，在传统的评价方法上进行拓展，有针对性地对检索结果的多样化进行评价。如Agrawal等[27]提出的NDCG-IA，MRR-IA等评价方法。 5 总结 本文在对用户检索多样化需求进行分析的基础上，探讨了检索多样化的定义，并进而对检索结果多样化研究的方法和评价指标做了介绍。近几年来学者主要关注多样化的方法和结果列表多样性与相关性的平衡。但关于如何更好地平衡在不同检索环境下结果的相关性和多样性；对于不同歧义程度的不同查询，如何考虑检索结果不同的多样化程度，仍需要进一步研究。 当前实现检索结果多样化的方法大多都是基于对原始查询的检索结果的重排序，但是当原始查询的结果中相关文档较少，甚至没有与查询相关的某一子主题相关的文档，那么此时这类方法的多样化的效率就比较低。未来研究可以考虑如何通过输入原始查询不进行重排序即可实现检索结果的多样化。此外，检索结果的多样化已经被应用于许多不同的信息系统，如专家检索系统、推荐系统、新浪的微博搜索等，但这些应用是否在现实情境下提升了检索效果，改善了用户体验，也是值得进一步探索的问题。
标签：用户研究论文; 用户需求论文; 主题模型论文; 需求文档论文;
