鄔艷艷，周新科

(江蘇大學(xué) 計(jì)算機(jī)科學(xué)與通信工程學(xué)院，江蘇 鎮(zhèn)江 212013)

?

信息檢索結(jié)果隱式多樣化排序方法研究

鄔艷艷，周新科

(江蘇大學(xué) 計(jì)算機(jī)科學(xué)與通信工程學(xué)院，江蘇 鎮(zhèn)江 212013)

針對(duì)信息檢索隱式多樣化算法展開研究。介紹了檢索結(jié)果重排序中的最大邊際相關(guān)度(MMR)算法、相對(duì)熵(KL)算法、現(xiàn)代投資組合理論(MPT)3個(gè)隱式多樣化算法，采用此3個(gè)算法對(duì)所選的已排序的文檔數(shù)據(jù)集進(jìn)行重排，通過對(duì)排序結(jié)果進(jìn)行評(píng)價(jià)來對(duì)比三者的性能。得出隱式多樣化方法中當(dāng)相關(guān)性和多樣性以一定比例的線性組合時(shí)，會(huì)使最終的檢索結(jié)果在一些評(píng)價(jià)指標(biāo)上相對(duì)于原始結(jié)果有所提高。

隱式多樣化；信息檢索；線性組合；MMR；KL

隨著互聯(lián)網(wǎng)的發(fā)展，在海量信息日益增加的背景下，信息檢索系統(tǒng)在有限的空間中呈現(xiàn)多樣化的檢索結(jié)果，提高用戶的使用體驗(yàn)已變得日趨重要。由此，信息檢索多樣化的問題受到了廣泛關(guān)注。在使用信息檢索系統(tǒng)時(shí)，用戶通常不明確自身要搜索的確切內(nèi)容，其會(huì)對(duì)一方面感興趣，也可能想了解另一方面的信息。對(duì)于用戶給定的查詢，需要信息檢索系統(tǒng)給出的檢索結(jié)果多種多樣以滿足用戶對(duì)信息的需求，因此信息檢索系統(tǒng)如何能夠檢索出相關(guān)性高以及多樣化的信息成了檢索系統(tǒng)最重要的研究方向。結(jié)果多樣化在早期的信息檢索工作中[1-2]其重要性已被確認(rèn)，其基本前提是一組文檔不僅取決于其成員的單獨(dú)相關(guān)性，而且也取決于它們是如何彼此關(guān)聯(lián)的。理想情況下，文檔集應(yīng)適當(dāng)考慮整體用戶群體的利益[3]。目前多樣化結(jié)果的工作充其量只是隱性使用主題的查詢或文件，而多樣化發(fā)生是通過相似性函數(shù)或條件相關(guān)分布的方式定義文件[4-6]，或通過用戶反饋[7-8]。同樣，多樣化技術(shù)[9-12]試圖通過反復(fù)選擇先前未被選擇進(jìn)去的文件形式形成多樣的排名列表，也就是說其是在調(diào)和排序列表每個(gè)位置的新奇性即多樣性。信息檢索結(jié)果多樣化主要分為隱式多樣化和顯示多樣化。文中主要是對(duì)3個(gè)經(jīng)典的隱式多樣化的研究和分析。MMR是一種隱式的貪心算法[13]，由Carbonell和Goldstein提出。初始時(shí)結(jié)果為空，然后每次往結(jié)果中放入一個(gè)文檔，并使得放進(jìn)的文檔對(duì)于當(dāng)前MMR利益最大化。Zhai等提出了另一種隱式的貪心算法[14]。也是初始時(shí)結(jié)果為空，然后每次往結(jié)果中放入一個(gè)文檔，只是所基于的計(jì)算式子有所不同?，F(xiàn)代投資組合理論(Modern Portfolio Theory)在1952年首次由美國經(jīng)濟(jì)學(xué)家馬考維茨(Markowitz)提出并做了諸多的研究工作。在這項(xiàng)理論中，投資的回報(bào)被看作是一個(gè)隨機(jī)變量，通過對(duì)該隨機(jī)變量進(jìn)行均值-方差分析，提出投資組合的優(yōu)化可通過分散投資來得到。隨后Wang和Zhu發(fā)現(xiàn)可將該方法應(yīng)用于支持結(jié)果多樣化的信息檢索[3]。同樣是為每一個(gè)文檔計(jì)算分?jǐn)?shù)，分值大者依次放到結(jié)果中。這3個(gè)結(jié)果：

(1)需要計(jì)算文檔與查詢的相關(guān)性，這可由一般的支持相關(guān)性的排名算法來完成；

(2)需要計(jì)算兩個(gè)文檔之間的相似性，這可由多種方法計(jì)算?？偹悸肥俏臋n在相關(guān)排名算法計(jì)算出其得分與已選文檔和待選文檔相關(guān)度值之間的線性組合，將選取使得最終結(jié)果最大的待選文檔到已排序序列中，并重復(fù)此步驟直到選取需要數(shù)量的文檔為止，以此來重排所有文檔。本文主要對(duì)這3個(gè)方法進(jìn)行了實(shí)現(xiàn)與比較。

1　算法思想及原理

1.1MMR

MMR(Maximal Marginal Relevance)即最大邊際相關(guān)度算法,其使用λ∈(0,1)之間的值線性組合相關(guān)性和新奇性，其把文檔與查詢?cè)~的相關(guān)度和文檔的信息新穎度結(jié)合起來對(duì)文檔進(jìn)行排序。在保持文檔與用戶查詢相關(guān)性的同時(shí)，可減少由于只根據(jù)與查詢?cè)~的相關(guān)進(jìn)行排序而可能造成的文檔信息的冗余。一個(gè)文檔的邊際相關(guān)度為文檔的查詢相關(guān)度與信息新穎度的線性組合，兩者用一個(gè)參數(shù)進(jìn)行調(diào)優(yōu)。其中文檔的信息新穎度由該文檔與已排序文檔的最大相似度決定，即相似度越大，新穎度越小。在對(duì)文檔進(jìn)行排序時(shí)，迭代選擇邊際相關(guān)度最大的文檔可在一定程度上減少文檔的信息冗余

(1)

其中，C是文檔集合；Q是查詢，R=IR(C,Q,θ)是一個(gè)檢索系統(tǒng)檢索出來的文檔列表，給定C和Q還有臨界值 ，低于此臨界值將不檢索文檔(θ表示匹配度或者匹配的文檔個(gè)數(shù)),本實(shí)驗(yàn)中θ表示匹配的文檔個(gè)數(shù)為480。S是R中已被選取的文檔的子集，RS表示差集即是R中還未被選取的文檔。Sim1是用在文檔檢索中和在文檔與查詢間的相關(guān)性排序的相似性矩陣。Sim2也是一個(gè)矩陣表示已被選取的文檔j和待選取的文檔i兩個(gè)文檔的相似度，本實(shí)驗(yàn)中求兩個(gè)文檔相似度的方法是根據(jù)兩個(gè)文檔單詞的交集個(gè)數(shù)比上兩個(gè)文檔單詞的總個(gè)數(shù)減去其單詞的交集個(gè)數(shù)，所得到的就是兩個(gè)文檔的相似度。當(dāng)λ=0時(shí)，計(jì)算的是已排序文檔R中的最大多樣化排序，當(dāng)λ=1時(shí)計(jì)算的是標(biāo)準(zhǔn)的相關(guān)性排序。 經(jīng)過Jaime Carbonell研究表明，一個(gè)特別有效的檢索策略:為了解在查詢區(qū)域的信息空間，應(yīng)該以一個(gè)小的λ值開始(λ=0.3)進(jìn)行計(jì)算檢索，為聚焦于最重要的部分使用改進(jìn)的查詢(可能是通過相關(guān)反饋)和大的λ值(λ=0.7)。

1.2KL

KL(Kullback-Leibler divergence)即相對(duì)熵算法,對(duì)于離散隨機(jī)變量的概率分布P和Q,KL散度的公式為

(2)

該算法(2)得到的是概率P和Q對(duì)數(shù)差異的平均值，其中平均值是通過使用概率P得到的。KL方法計(jì)算多樣性的公式為

(3)

其中，1≤ρ≤10，若ρ<1意味著較大的相關(guān)性值對(duì)應(yīng)于更大相關(guān)性和新奇性組合的值，隨著ρ值得變大，整個(gè)公式更依賴于相關(guān)性，當(dāng)ρ=10時(shí)，KL的公式幾乎全靠相關(guān)性主宰。p(q|di)是查詢與文檔的相關(guān)性i和j是indri結(jié)果中每個(gè)查詢中文檔的位置，其中j已被選取

(4)

計(jì)算方法是待選取的文檔di與已選取的文檔dj的概率分布的距離；di(k)代表查詢?cè)~k在文檔di中所占的的比率；dj(k)代表查詢?cè)~k在文檔dj中所占的比率。

1.3MPT

MPT(Modern Portfolio Theory)即現(xiàn)代投資組合理論，研究的是在信息檢索中基于不確定性的文檔排序，不但是單個(gè)選取相關(guān)文檔而且是選取相關(guān)文檔的正確組合。在選取相關(guān)文檔的正確組合時(shí)，基于其預(yù)計(jì)的全部相關(guān)性和多樣性生成一定量文檔的排序列表。其計(jì)算式為

(5)

式(5)可化簡為

(6)

2　實(shí)驗(yàn)設(shè)置與實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)使用TREC會(huì)議中網(wǎng)頁跟蹤模塊提供的ClueWeb09的B級(jí)數(shù)據(jù)集和2009～2012其4年中Web檢索任務(wù)采用的4組查詢。TREC是近年來信息檢索系統(tǒng)評(píng)價(jià)方面最主要的活動(dòng)。TREC由美國政府資助，首次于1992開始舉辦，其后每年舉辦一次 ，迄今已成功舉辦22屆。每年會(huì)議提供50個(gè)查詢，4年共有200個(gè)查詢。實(shí)驗(yàn)采用Indri檢索系統(tǒng)對(duì)ClueWeb09B進(jìn)行搜索，獲得初始檢索文檔結(jié)果得分以及相應(yīng)的文檔排名。為得到更好的結(jié)果，又對(duì)Indri系統(tǒng)處理得到的結(jié)果進(jìn)行了垃圾處理和規(guī)范化評(píng)分結(jié)果。然后對(duì)規(guī)范后的結(jié)果分別用MMR，KL，MPT這3種隱式多樣化算法進(jìn)行處理，得到文檔最終排序結(jié)果。

圖1是隱式多樣化方法MMR的實(shí)現(xiàn)評(píng)價(jià)結(jié)果隨λ值變化的變化情況。從圖中可看出，當(dāng)λ值為0.7時(shí)，對(duì)其評(píng)價(jià)的各個(gè)評(píng)價(jià)指標(biāo)值相對(duì)較好。由圖1還可知，當(dāng)λ值接近于1時(shí)對(duì)MMR進(jìn)行的評(píng)價(jià)指標(biāo)結(jié)果的值較高，表明在排序中新奇性占的比例越小得到的排序結(jié)果越好。

圖1　MMR方法的評(píng)價(jià)結(jié)果值隨λ值的變化

圖2是參數(shù)ρ取不同的值MPT方法性能的變化情況。從圖2中可看出，當(dāng)ρ值為-2時(shí)，各評(píng)價(jià)指標(biāo)的結(jié)果相對(duì)較高。還可看出ρ為負(fù)值時(shí)，表示待選取文檔與之前選取的文檔相關(guān)性越大，等到的最終排序結(jié)果越好。

圖2　MPT方法的評(píng)價(jià)結(jié)果值隨ρ的變化

圖3是KL隱式多樣化方法隨b值其性能的變化情況，從圖3中可看出，當(dāng)b值為8時(shí)得到的各個(gè)評(píng)價(jià)指標(biāo)結(jié)果值相對(duì)較高。

圖3　KL方法的評(píng)價(jià)結(jié)果值隨b的變化

對(duì)最后排序結(jié)果進(jìn)行評(píng)價(jià)，實(shí)驗(yàn)采用4個(gè)多樣化評(píng)價(jià)指標(biāo)，分別是ERR-IA@K，a-nDCG@K,MAP-IA,P-IA@20,其中K取20，這幾個(gè)評(píng)價(jià)指標(biāo)實(shí)在Ndeval中使用的，所取最后結(jié)果為4年的平均值。K取值20是TREC中普遍使用的一個(gè)典型值。

表1　3種隱式多樣化方法評(píng)價(jià)結(jié)果

注：表1中的所有結(jié)果進(jìn)行了逐對(duì)的T雙側(cè)檢驗(yàn)。a表示當(dāng)前方法與初始總查詢結(jié)果比較有較顯著差異(sig<0.05),b表示當(dāng)前方法與初始子查詢?nèi)诤辖Y(jié)果比較有顯著差異(sig<0.05)。

表1中是MMR、KL和MPT的3個(gè)隱式多樣化方法在最佳狀態(tài)下的性能評(píng)價(jià)結(jié)果。其中亦列入了初始檢索結(jié)果的性能以方便比較。實(shí)驗(yàn)結(jié)果表明，3個(gè)隱式方法在ERR-IA@20和alpha-nDCG@20這兩個(gè)評(píng)價(jià)指標(biāo)比原始評(píng)價(jià)結(jié)果有所提高，且KL是唯一一個(gè)在MAP-IA和P-IA@20這兩個(gè)評(píng)價(jià)指標(biāo)上高于原始評(píng)價(jià)結(jié)果的方法，在MAP-IA上提高了2.27%，在P-IA@20上提高了5.0%。MPT方法在ERR-IA@20評(píng)價(jià)指標(biāo)上表現(xiàn)相對(duì)較好，其比原始結(jié)果高了2.55%。KL在alpha-nDCG@20評(píng)價(jià)指標(biāo)上表現(xiàn)相對(duì)較好，其比原始結(jié)果高了1.93%。相對(duì)于MPT和KL這兩個(gè)方法MMR在這4個(gè)評(píng)價(jià)指標(biāo)上都是最差的。由研究可知，ERR-IA@20和alpha-nDCG@20主要偏向于新穎性的計(jì)算，MAP-IA和P-IA@20偏向于子主題的覆蓋率的計(jì)算。對(duì)于研究的3個(gè)隱式多樣化方法MMR、KL和MPT計(jì)算出新的排序結(jié)果的評(píng)價(jià)，其中ERR-IA@20和alpha-nDCG@20這個(gè)評(píng)價(jià)指標(biāo)要高于原始評(píng)價(jià)結(jié)果，而在MAP-IA和P-IA@20這兩個(gè)評(píng)價(jià)指標(biāo)上MMR和MPT隱式多樣化方法的重排結(jié)果低于原始結(jié)果。因?yàn)镋RR-IA@20和alpha-nDCG@20主要偏向于新穎性的計(jì)算，選用的隱式多樣化方法側(cè)重于提高新穎性，而在MAP-IA和P-IA@20這兩個(gè)評(píng)價(jià)指標(biāo)即子主題覆蓋率和精度上表現(xiàn)并不理想。

3　結(jié)束語

隱式多樣化是基于一定的假設(shè)，刻畫不同的文檔信息面蘊(yùn)含上的差異，在此基礎(chǔ)上選擇具有差異性的文檔子集實(shí)現(xiàn)多樣化，通過降低與已排序文檔的排序位置來達(dá)到多樣化的目的。在對(duì)3個(gè)隱式多樣化算法的研究中得出當(dāng)其新穎性部分占據(jù)很小的比例時(shí)，對(duì)結(jié)果的重排得到的性能才會(huì)改觀。在對(duì)文檔進(jìn)行排序時(shí)，迭代選擇邊際相關(guān)度最大的文檔可在一定程度上減少文檔的信息冗余，亦表明在對(duì)數(shù)據(jù)集進(jìn)行查詢時(shí)相關(guān)性是主導(dǎo)因素。在未來的工作中需要對(duì)相關(guān)性和冗余性做進(jìn)一步的研究，可使用到合成的數(shù)據(jù)來控制冗余程度等因素。這3個(gè)隱式多樣化方法的一個(gè)重大缺陷是相關(guān)性和新奇性獨(dú)立處理。其結(jié)果是，沒有直接衡量包含在一個(gè)新文檔中的新信息的相關(guān)性。因此，可得到擁有信息的冗余文檔，然而擁有不相關(guān)的信息的文檔排序可能會(huì)高。

[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-),男，碩士研究生。研究方向：信息檢索數(shù)據(jù)融合。

TP391.3

A

1007-7820(2016)08-106-04