信息检索结果隐式多样化排序方法研究

邬艳艳，周新科

(江苏大学 计算机科学与通信工程学院，江苏 镇江 212013)



信息检索结果隐式多样化排序方法研究

邬艳艳，周新科

(江苏大学 计算机科学与通信工程学院，江苏 镇江 212013)

针对信息检索隐式多样化算法展开研究。介绍了检索结果重排序中的最大边际相关度(MMR)算法、相对熵(KL)算法、现代投资组合理论(MPT)3个隐式多样化算法，采用此3个算法对所选的已排序的文档数据集进行重排，通过对排序结果进行评价来对比三者的性能。得出隐式多样化方法中当相关性和多样性以一定比例的线性组合时，会使最终的检索结果在一些评价指标上相对于原始结果有所提高。

隐式多样化；信息检索；线性组合；MMR；KL

随着互联网的发展，在海量信息日益增加的背景下，信息检索系统在有限的空间中呈现多样化的检索结果，提高用户的使用体验已变得日趋重要。由此，信息检索多样化的问题受到了广泛关注。在使用信息检索系统时，用户通常不明确自身要搜索的确切内容，其会对一方面感兴趣，也可能想了解另一方面的信息。对于用户给定的查询，需要信息检索系统给出的检索结果多种多样以满足用户对信息的需求，因此信息检索系统如何能够检索出相关性高以及多样化的信息成了检索系统最重要的研究方向。结果多样化在早期的信息检索工作中[1-2]其重要性已被确认，其基本前提是一组文档不仅取决于其成员的单独相关性，而且也取决于它们是如何彼此关联的。理想情况下，文档集应适当考虑整体用户群体的利益[3]。目前多样化结果的工作充其量只是隐性使用主题的查询或文件，而多样化发生是通过相似性函数或条件相关分布的方式定义文件[4-6]，或通过用户反馈[7-8]。同样，多样化技术[9-12]试图通过反复选择先前未被选择进去的文件形式形成多样的排名列表，也就是说其是在调和排序列表每个位置的新奇性即多样性。信息检索结果多样化主要分为隐式多样化和显示多样化。文中主要是对3个经典的隐式多样化的研究和分析。MMR是一种隐式的贪心算法[13]，由Carbonell和Goldstein提出。初始时结果为空，然后每次往结果中放入一个文档，并使得放进的文档对于当前MMR利益最大化。Zhai等提出了另一种隐式的贪心算法[14]。也是初始时结果为空，然后每次往结果中放入一个文档，只是所基于的计算式子有所不同。现代投资组合理论(Modern Portfolio Theory)在1952年首次由美国经济学家马考维茨(Markowitz)提出并做了诸多的研究工作。在这项理论中，投资的回报被看作是一个随机变量，通过对该随机变量进行均值-方差分析，提出投资组合的优化可通过分散投资来得到。随后Wang和Zhu发现可将该方法应用于支持结果多样化的信息检索[3]。同样是为每一个文档计算分数，分值大者依次放到结果中。这3个结果：

(1)需要计算文档与查询的相关性，这可由一般的支持相关性的排名算法来完成；

(2)需要计算两个文档之间的相似性，这可由多种方法计算。总思路是文档在相关排名算法计算出其得分与已选文档和待选文档相关度值之间的线性组合，将选取使得最终结果最大的待选文档到已排序序列中，并重复此步骤直到选取需要数量的文档为止，以此来重排所有文档。本文主要对这3个方法进行了实现与比较。

1　算法思想及原理

1.1MMR

MMR(Maximal Marginal Relevance)即最大边际相关度算法,其使用λ∈(0,1)之间的值线性组合相关性和新奇性，其把文档与查询词的相关度和文档的信息新颖度结合起来对文档进行排序。在保持文档与用户查询相关性的同时，可减少由于只根据与查询词的相关进行排序而可能造成的文档信息的冗余。一个文档的边际相关度为文档的查询相关度与信息新颖度的线性组合，两者用一个参数进行调优。其中文档的信息新颖度由该文档与已排序文档的最大相似度决定，即相似度越大，新颖度越小。在对文档进行排序时，迭代选择边际相关度最大的文档可在一定程度上减少文档的信息冗余

(1)

其中，C是文档集合；Q是查询，R=IR(C,Q,θ)是一个检索系统检索出来的文档列表，给定C和Q还有临界值 ，低于此临界值将不检索文档(θ表示匹配度或者匹配的文档个数),本实验中θ表示匹配的文档个数为480。S是R中已被选取的文档的子集，RS表示差集即是R中还未被选取的文档。Sim1是用在文档检索中和在文档与查询间的相关性排序的相似性矩阵。Sim2也是一个矩阵表示已被选取的文档j和待选取的文档i两个文档的相似度，本实验中求两个文档相似度的方法是根据两个文档单词的交集个数比上两个文档单词的总个数减去其单词的交集个数，所得到的就是两个文档的相似度。当λ=0时，计算的是已排序文档R中的最大多样化排序，当λ=1时计算的是标准的相关性排序。 经过Jaime Carbonell研究表明，一个特别有效的检索策略:为了解在查询区域的信息空间，应该以一个小的λ值开始(λ=0.3)进行计算检索，为聚焦于最重要的部分使用改进的查询(可能是通过相关反馈)和大的λ值(λ=0.7)。

1.2KL

KL(Kullback-Leibler divergence)即相对熵算法,对于离散随机变量的概率分布P和Q,KL散度的公式为

(2)

该算法(2)得到的是概率P和Q对数差异的平均值，其中平均值是通过使用概率P得到的。KL方法计算多样性的公式为

(3)

其中，1≤ρ≤10，若ρ<1意味着较大的相关性值对应于更大相关性和新奇性组合的值，随着ρ值得变大，整个公式更依赖于相关性，当ρ=10时，KL的公式几乎全靠相关性主宰。p(q|di)是查询与文档的相关性i和j是indri结果中每个查询中文档的位置，其中j已被选取

(4)

计算方法是待选取的文档di与已选取的文档dj的概率分布的距离；di(k)代表查询词k在文档di中所占的的比率；dj(k)代表查询词k在文档dj中所占的比率。

1.3MPT

MPT(Modern Portfolio Theory)即现代投资组合理论，研究的是在信息检索中基于不确定性的文档排序，不但是单个选取相关文档而且是选取相关文档的正确组合。在选取相关文档的正确组合时，基于其预计的全部相关性和多样性生成一定量文档的排序列表。其计算式为

(5)

式(5)可化简为

(6)

2　实验设置与实验结果

实验使用TREC会议中网页跟踪模块提供的ClueWeb09的B级数据集和2009～2012其4年中Web检索任务采用的4组查询。TREC是近年来信息检索系统评价方面最主要的活动。TREC由美国政府资助，首次于1992开始举办，其后每年举办一次 ，迄今已成功举办22届。每年会议提供50个查询，4年共有200个查询。实验采用Indri检索系统对ClueWeb09B进行搜索，获得初始检索文档结果得分以及相应的文档排名。为得到更好的结果，又对Indri系统处理得到的结果进行了垃圾处理和规范化评分结果。然后对规范后的结果分别用MMR，KL，MPT这3种隐式多样化算法进行处理，得到文档最终排序结果。

图1是隐式多样化方法MMR的实现评价结果随λ值变化的变化情况。从图中可看出，当λ值为0.7时，对其评价的各个评价指标值相对较好。由图1还可知，当λ值接近于1时对MMR进行的评价指标结果的值较高，表明在排序中新奇性占的比例越小得到的排序结果越好。

图1　MMR方法的评价结果值随λ值的变化

图2是参数ρ取不同的值MPT方法性能的变化情况。从图2中可看出，当ρ值为-2时，各评价指标的结果相对较高。还可看出ρ为负值时，表示待选取文档与之前选取的文档相关性越大，等到的最终排序结果越好。

图2　MPT方法的评价结果值随ρ的变化

图3是KL隐式多样化方法随b值其性能的变化情况，从图3中可看出，当b值为8时得到的各个评价指标结果值相对较高。

图3　KL方法的评价结果值随b的变化

对最后排序结果进行评价，实验采用4个多样化评价指标，分别是ERR-IA@K，a-nDCG@K,MAP-IA,P-IA@20,其中K取20，这几个评价指标实在Ndeval中使用的，所取最后结果为4年的平均值。K取值20是TREC中普遍使用的一个典型值。

表1　3种隐式多样化方法评价结果

注：表1中的所有结果进行了逐对的T双侧检验。a表示当前方法与初始总查询结果比较有较显著差异(sig<0.05),b表示当前方法与初始子查询融合结果比较有显著差异(sig<0.05)。

表1中是MMR、KL和MPT的3个隐式多样化方法在最佳状态下的性能评价结果。其中亦列入了初始检索结果的性能以方便比较。实验结果表明，3个隐式方法在ERR-IA@20和alpha-nDCG@20这两个评价指标比原始评价结果有所提高，且KL是唯一一个在MAP-IA和P-IA@20这两个评价指标上高于原始评价结果的方法，在MAP-IA上提高了2.27%，在P-IA@20上提高了5.0%。MPT方法在ERR-IA@20评价指标上表现相对较好，其比原始结果高了2.55%。KL在alpha-nDCG@20评价指标上表现相对较好，其比原始结果高了1.93%。相对于MPT和KL这两个方法MMR在这4个评价指标上都是最差的。由研究可知，ERR-IA@20和alpha-nDCG@20主要偏向于新颖性的计算，MAP-IA和P-IA@20偏向于子主题的覆盖率的计算。对于研究的3个隐式多样化方法MMR、KL和MPT计算出新的排序结果的评价，其中ERR-IA@20和alpha-nDCG@20这个评价指标要高于原始评价结果，而在MAP-IA和P-IA@20这两个评价指标上MMR和MPT隐式多样化方法的重排结果低于原始结果。因为ERR-IA@20和alpha-nDCG@20主要偏向于新颖性的计算，选用的隐式多样化方法侧重于提高新颖性，而在MAP-IA和P-IA@20这两个评价指标即子主题覆盖率和精度上表现并不理想。

3　结束语

隐式多样化是基于一定的假设，刻画不同的文档信息面蕴含上的差异，在此基础上选择具有差异性的文档子集实现多样化，通过降低与已排序文档的排序位置来达到多样化的目的。在对3个隐式多样化算法的研究中得出当其新颖性部分占据很小的比例时，对结果的重排得到的性能才会改观。在对文档进行排序时，迭代选择边际相关度最大的文档可在一定程度上减少文档的信息冗余，亦表明在对数据集进行查询时相关性是主导因素。在未来的工作中需要对相关性和冗余性做进一步的研究，可使用到合成的数据来控制冗余程度等因素。这3个隐式多样化方法的一个重大缺陷是相关性和新奇性独立处理。其结果是，没有直接衡量包含在一个新文档中的新信息的相关性。因此，可得到拥有信息的冗余文档，然而拥有不相关的信息的文档排序可能会高。

[1]Boyce B.Beyond topicality:A two stage view of relevance and the retrieval process[J].Information Processing & Management,1982,18(3):105-109.

[2]Goffman W.A searching procedure for information retrieval[J].Information Storage & Retrieval,1964,2(64):73-78.

[3]Charles L A Clarke,Maheedhar Kolla, Gordon V Cormack, et al. Novelty and diversity in information retrieval evaluation[C].Singapore:The 31st Annual International ACM SIGIR,2008.

[4]Zhai C,Jamie Callan.Risk minimization and language modeling in text retrieval[J]. Acm Sigir Forum,2002,36(2):100-101.

[5]Carbonell J,Goldstein J.The use of MMR, diversity-based reranking for reordering documents and producing summaries[C]. Beijing: Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval:ACM, 1998.

[6]Chen H,Karger D R.Less is more: probabilistic models for retrieving fewer relevant documents[C].Taipei: Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval:ACM,2006.

[7]Radlinski F,Kleinberg R,Joachims T.Learning diverse rankings with multi-armed bandits[C].Helsinki,Finland: Appearing in Proceedings of the 25th International Conference on Machine Learning,ICML,2008.

[8]Bookstein A.Information retrieval: A sequential learning process[J].Journal of the American Society for Information Science,1983,34(5):331-342.

[9]Agrawal R,Gollapudi S,Halverson A,et al. Diversifying search results[C].Barcelona, Spain: WSDM’ 09 ACM, 2009.

[10] Carterette B,Chandar P. Probabilistic models of ranking novel documents for faceted topic retrieval[C].Hong Kong: CIKM’ 09,ACM,2009.

[11] Santos R L T,Macdonald C,Ounis I.Exploiting query reformulations for web search result diversification[C].Mianyang: Proceedings of the 19th International Conference on World Wide Web:ACM,2010.

[12] Wang J,Zhu J.Portfolio theory of information retrieval[C].Chengdu: Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval:ACM,2009.

[13] Xu Y,Yin H.Novelty and topicality in interactive information retrieval[J].Journal of the American Society for Information Science & Technology,2008,59(2):201-215.

[14] Zhai C X,Cohen W W,Lafferty J.Beyond independent relevance: methods and evaluation metrics for subtopic retrieval[C].Xi’an:Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Informaion Retrieval:ACM,2003.

Research and Analysis on the Implicit Diversification Ranking Method for Information Retrieval

WU Yanyan，ZHOU Xinke

(School of Computer Science and Communication Engineering,Jiangsu University, Zhenjiang 212013, China)

Research on implicit diversification algorithm for information retrieval. On this basis, the documents are diversified. In this paper, first we introduce the maximum marginal relevance (MMR) method, Kullback-Leibler divergence (KL) method and modern portfolio theory (MPT), then use these three methods to re-rank data sets, and then evaluate and compare the performance of the three methods. Finally, it is concluded that the implicit diversification methods can improve the performance compare with the original results when the correlation and diversity in a certain percentage of linear combination .

implicit diversification; information retrieval; linear combination; MMR; KL

10.16180/j.cnki.issn1007-7820.2016.08.031

2015-12-04

邬艳艳(1989-),女，硕士研究生。研究方向：信息检索。周新科 (1990-),男，硕士研究生。研究方向：信息检索数据融合。

TP391.3

A

1007-7820(2016)08-106-04