信息檢索多樣化排序算法研究綜述

劉興林

信息檢索中用戶的多樣化需求促進了多樣化排序問題的提出，當前國內外多樣化排序研究的成果主要分為隱式多樣化排序和顯式多樣化排序，而在用戶潛在意圖未知的前提下，如何根據用戶提交的查詢詞對信息檢索結果文檔進行排序，從而最大化程度上滿足用戶需求，是多樣化排序問題研究的核心問題和難點。文章通過對國內外多樣化排序研究成果進行分析，歸納了當前多樣化排序研究中所存在的一些不足，并指出了在多樣化排序領域中可以進行研究的一些方向，特別是多樣化排序理論體系的完善和多樣化排序系統的構建。

概述

信息檢索的主要目的是對信息表示、存儲與組織，使用戶更容易獲得所需要或者感興趣的信息。信息檢索的多樣化排序問題對信息檢索系統提出了更高的要求。為了滿足用戶的多樣化需求，信息檢索系統不能只是簡單地根據結果文檔與用戶輸入的查詢詞之間的相關度來對文檔進行排序，必須更深層次地挖掘用戶潛在的信息需求，在結果列表靠前的位置中盡可能地提供滿足用戶各種需求的檢索結果。

目前用于分析結果與查詢的相關性技術主要有兩類：基于內容的相關度計算和鏈接分析。基于內容的相關度計算屬于傳統信息檢索領域的分析方法，多采用向量空間模型、概述模型等方法來逐一計算結果文檔與用戶查詢的相關度。面鏈接分析則是針對互聯網文檔富含超鏈接的特點，通過對鏈接進行分析獲得高質量的結果文檔，包括著名的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）構建簡單實用的多樣化排序檢索系統。多樣化排序研究主要基于互聯網信息檢索，因此，多樣化方法既要考慮效果，又要考慮運行效率，構建一個實用的多樣化排序系統，更具有現實意義。