胡 莎，竇志成，文繼榮

(1. 西南大學(xué) 計算機與信息科學(xué)學(xué)院,重慶 400715;2. 中國人民大學(xué) 信息學(xué)院，北京 100086;3. 大數(shù)據(jù)管理與分析方法研究北京市重點實驗室，北京 100086)

論子話題粒度對搜索結(jié)果多樣化算法的影響

胡 莎1，竇志成2,3，文繼榮2,3

(1. 西南大學(xué) 計算機與信息科學(xué)學(xué)院,重慶 400715;2. 中國人民大學(xué) 信息學(xué)院，北京 100086;3. 大數(shù)據(jù)管理與分析方法研究北京市重點實驗室，北京 100086)

隨著生活節(jié)奏的加快，用戶習(xí)慣將簡短的查詢提交給搜索引擎，并希望搜索引擎能體貼地將自己需要的結(jié)果返回在靠前的結(jié)果中。面對大量有歧義的或者意義廣泛的查詢，搜索引擎努力地識別用戶意圖，并試圖用有限的結(jié)果取悅更多的用戶。為了解決這個問題，搜索結(jié)果多樣化技術(shù)應(yīng)運而生，其任務(wù)是是對搜索結(jié)果進行重排序，在有限的搜索結(jié)果中滿足盡可能多的用戶意圖。該文重點關(guān)注多樣化算法中子話題的粒度問題。利用傳統(tǒng)方法生成了不同粒度的子話題，并比較了使用不同粒度的子話題對搜索結(jié)果多樣化算法的影響。實驗結(jié)果表明，經(jīng)典多樣化算法使用細粒度的子話題時表現(xiàn)更好。

搜索結(jié)果多樣化；查詢意圖；子話題

Abstract: The search result diversification re-ranks search results to cover as many user intents as possible in the top ranks. Most intent-aware diversification algorithms use subtopics to diversify results. Focuses on the granularity of subtopics, this paper investigates the performance of diversification algorithms by using subtopics with different granularities. Experimental results show that state-of-the-art diversification algorithms work better by using fine-grained subtopics.

Key words: search result diversification, query intents, subtopics

1 引言

隨著互聯(lián)網(wǎng)信息的快速膨脹，輸入一個查詢詞，搜索引擎通常會找到大量的相關(guān)文檔。為了盡快找到目標(biāo)文檔，用戶都希望自己需要的文檔排在盡量靠前的位置。研究發(fā)現(xiàn)[1-3]，當(dāng)輸入同一個查詢詞時，不同用戶可能在查找不同的內(nèi)容。例如，查詢“人大”，用戶可能是要查“中國人民大學(xué)”，也可能是要查“全國人民代表大會”。即使搜索引擎能確定用戶是找中國人民大學(xué)的相關(guān)信息，也有很多不同的查找方向，如“人民大學(xué)最近新聞”“人民大學(xué)招生信息”“人民大學(xué)信息學(xué)院”等。如何在有限的結(jié)果中滿足盡可能多的用戶需求，是近年信息檢索的熱點。

為了解決上述問題，兩個密切相關(guān)的研究方向受到了研究者們的關(guān)注: 子話題挖掘技術(shù)，即根據(jù)查詢挖掘用戶的實際需求；搜索結(jié)果多樣化技術(shù)，即在有限的結(jié)果中覆蓋盡可能多的用戶需求。一些信息檢索機構(gòu)也組織了該方向相關(guān)的競賽或評測任務(wù)，并公開了數(shù)據(jù)集和評價標(biāo)注，如TREC Web Track的Diversity task*TREC: http: //plg.uwaterloo.ca/～trecweb/2012.html和NTCIR的IntentIMine task*NTCIR IMine: http: //www.thuir.org/imine/。

在大部分的搜索結(jié)果多樣化研究中，用戶的查詢意圖被組織成一個子話題集合，其中每一個子話題代表一個用戶意圖。不同的算法可能采取不同的方式來獲取子話題，如用查詢的分類作為子話題[4-5]，將搜索引擎的查詢推薦作為子話題[6-7]，或者從文檔內(nèi)容中抽取短語或詞組聚類生成子話題[8-9]。

本文主要關(guān)注子話題的粒度問題。我 們 發(fā) 現(xiàn)，

通過某些傳統(tǒng)的子話題生成方法，可生成不同粒度的子話題。一個簡單的例子是利用Google suggestions生成子話題。傳統(tǒng)的做法是將查詢輸入Google，抽取其提供的query suggestions作為該查詢的子話題，我們稱之為粗粒度的子話題。同理，我們將每個子話題分別輸入Google并收集其query suggestions，得到子話題的子話題集合，稱之為細粒度的子話題。表1展示了對于NTCIR的查詢“三毛”(id=13)在Google上取得的粗粒度子話題T1和細粒度子話題T2。

表1 基于Google Suggestions生成的查詢“三毛”的粗粒度子話題和細粒度子話題

本文進一步研究了子話題粒度和多樣化算法的關(guān)系，發(fā)現(xiàn)使用不同粒度的子話題，對于多樣化算法的表現(xiàn)有直接影響。以表1為例，假設(shè)文檔d1和d2與子話題“三毛流浪記電影”相關(guān)，文檔d3和子話題“三毛流浪記電視劇”相關(guān)，一個理想的多樣化排序為d1→d3→d2。當(dāng)采用粗粒度子話題時，多樣化算法在選擇第二個位置的文檔時無法區(qū)分d2和d3(均與粗粒度子話題“三毛流浪記”相關(guān))，可能輸出結(jié)果d1→d2→d3。此時用細粒度子話題能更好地判斷多樣性。在另一方面，假設(shè)新增文檔d4和子話題“三毛作品集下載”相關(guān)，一個理想排序為d1→d4→d3→d2。使用細粒度子話題的多樣化算法，在選擇第二個位置的文檔時無法區(qū)分d4和d3(不知d3和已選擇的d1都與粗粒度子話題“三毛流浪記”相關(guān))，可能輸出結(jié)果d1→d3→d4→d2。此時使用粗粒度子話題，算法輸出的排序為d1→d4→d2→d3，避免在第二個位置出錯，其結(jié)果的多樣性更佳。顯然，為多樣化算法選擇合適粒度的子話題，能直接改善多樣化的效果。

然而，現(xiàn)有的多樣化算法通常直接使用基于某種方法生成的子話題，沒有深入考慮子話題粒度對多樣化的影響。同時，大多數(shù)子話題生成技術(shù)重點關(guān)注子話題是否能準(zhǔn)確覆蓋盡可能多的重要用戶意圖，并未考慮把這些子話題的粒度應(yīng)用到多樣化過程中的影響。因此，研究不同粒度的子話題在多樣化算法中的作用，為多樣化算法尋找合適粒度的子話題，對基于子話題的搜索結(jié)果多樣化技術(shù)的研究非常重要。

基于以上考慮，本文研究了使用不同粒度的子話題對搜索結(jié)果多樣化算法的影響。本文分析了常用子話題的粒度，試圖為不同的多樣化算法找到更適合的子話題粒度，以提升算法的多樣化效果。具體地講，本文利用Google suggestions，生成了三類不同粒度的子話題，即前面介紹的粗粒度子話題和細粒度子話題，以及更細粒度的微粒度子話題。由于本文的重點不是提出新算法，而是為多樣化算法尋找最佳子話題粒度。于是，我們選擇了兩個經(jīng)典的搜索結(jié)果多樣化算法xQuAD和PM2，并在NTCIR數(shù)據(jù)上比較了不同粒度子話題對于兩個多樣化算法的影響。從NTCIR數(shù)據(jù)上得到的實驗結(jié)果表明，與傳統(tǒng)的粗粒度子話題相比，使用細粒度的子話題，能直接改善xQuAD和PM2的結(jié)果,而使用更進一步的微粒度子話題，在不同的多樣性算法上表現(xiàn)并不穩(wěn)定。因此，使用細粒度的子話題，是一個更好的選擇。

2 相關(guān)工作

早期的搜索結(jié)果多樣化研究，通過文檔的相似度來含蓄地表現(xiàn)搜索結(jié)果的多樣性。Carbonell和Goldstein在1998年提出MMR算法(maximal marginal relevance)[10]，通過文檔內(nèi)容的余弦相似性計算文檔間的相似度，是早期最有影響力的搜索結(jié)果多樣化工作之一。在文檔的排序過程中，MMR權(quán)衡文檔的相關(guān)性和新穎性，試圖選擇與查詢詞相關(guān)度較高，并且與已選擇文檔冗余度較低的文檔。受此啟發(fā)，研究者們提出了各種文檔相似度的估算方法來實現(xiàn)搜索結(jié)果多樣性。例如，用Kullback-Leibler divergence來比較文檔內(nèi)容[11]，利用吸收馬爾可夫鏈的隨機游走模型對文檔句子排序[12]，基于文檔鏈接結(jié)構(gòu)判斷文檔間的關(guān)系[13]。以上研究研究工作認(rèn)為，相似的文檔會覆蓋相似的子話題，但他們并沒有明確考慮到底哪些子話題被覆蓋。

基于用戶意圖(子話題)的多樣化研究，是近年來比較流行的方法，明確地通過文檔對子話題的覆蓋情況來描述搜索結(jié)果的多樣化程度。IA-Select[4]認(rèn)為文檔和查詢都可能包含多個子話題，并利用ODP分類*ODP: http: //www.dmoz.org/，獲取查詢和文檔類別相關(guān)的子話題(category)。xQuAD[6]采用貪心算法來選擇最大化覆蓋查詢子話題的文檔。RxQuAD[5]提出了基于查詢子話題相關(guān)性的計算方法。PM2[7]將搜索結(jié)果多樣化劃分為兩個步驟: 首先找到最需要被覆蓋的子話題，然后選擇與該子話題最相關(guān)的文檔。Dang和Croft[9]討論了單詞形式的子話題的多樣化算法。Raman等人[14]通過分析后續(xù)查詢來判斷子話題和查詢的關(guān)系。Yu和Ren[15]將搜索結(jié)果多樣化模擬為子話題的0～1背包問題。Liang等人[16]利用主題模型來尋找潛在的子話題。在另一方面，研究者們還試圖利用各種外部資源來生成不同類別的子話題，以促進搜索結(jié)果多樣化。例如，根據(jù)文檔的點擊次數(shù)判斷其所屬子話題[17]，或者結(jié)合不同來源的數(shù)據(jù)來生成子話題[18-19]。以上的搜索結(jié)果多樣化研究，主要利用各種不同的子話題來實現(xiàn)多樣化算法，而我們的工作，重點在于比較不同粒度的子話題對于多樣化算法的影響。

此外，研究者們也試圖利用機器學(xué)習(xí)的相關(guān)技術(shù)來多樣化搜索結(jié)果，如結(jié)構(gòu)化SVMs模型[20]和RLTR模型[21]。本文只關(guān)注使用子話題的多樣化算法。

和本文相關(guān)的另一類工作，是子話題挖掘技術(shù)[22-25]。盡管這些研究的目的不同，但他們都能生成合理的基于查詢或搜索結(jié)果的子話題。注意，由于本文的重點是討論子話題粒度，為了避免子話題挖掘算法的優(yōu)劣對于子話題粒度的影響，本文選取了一個多樣化算法,使用較多的子話題生成方法，即通過Google Suggestions獲取子話題[6-7,9]。

3 基于子話題的搜索結(jié)果多樣化算法

3.1xQuAD算法

xQuAD是主題新穎性模型(topic novelty model)的代表算法。該類模型起源于經(jīng)典MMR算法[10]，其核心思想是在排序中平衡文檔相關(guān)性和新穎性。即在每次選擇最佳文檔d*時，不僅考慮待選文檔d∈R/S和查詢q的相關(guān)性，還考慮文檔d相對于已選擇文檔集S在查詢q上體現(xiàn)的新穎性。其形式化定義如式(1)所示。

(1)

式(1)中，P(d|q)是待選文檔與查詢的相關(guān)性，Φ(d,S|q)是待選文檔d與已選擇文檔集S在查詢q上不相關(guān)的概率，即該文檔的新穎性。參數(shù)λ∈[0,1]控制相關(guān)性與新穎性的重要程度。當(dāng)λ=0.5時，算法認(rèn)為文檔的相關(guān)性和新穎性在排序中同樣重要；若λ>0.5，算法優(yōu)先選擇新穎性高的文檔；若λ<0.5，算法傾向選擇相關(guān)性高的文檔。注意，在選擇第一個文檔時，已選擇文檔集為空(S=?)，文檔新穎性相同時，算法只考慮文檔相關(guān)性，選擇一個最相關(guān)的文檔排在最前面。這是大部分現(xiàn)有多樣化算法普遍采用的方法。

本文選取的xQuAD算法，由Santos等人[6]在2010年提出，通過子話題的覆蓋程度計算文檔的新穎性。具體而言，算法首先統(tǒng)計每個子話題t被已選擇文檔集S覆蓋的情況，然后計算待選文檔d和子話題之間的相關(guān)程度。若文檔和未被覆蓋的子話題相關(guān)程度越高，則該文檔的新穎性越高；若文檔只和已經(jīng)被覆蓋的子話題相關(guān)，即使相關(guān)程度非常高，但其新穎性也很低，因為此文檔的內(nèi)容(子話題)已經(jīng)被前期選出的文檔集S覆蓋了。如式(2)所示。

(2)

綜上所述，xQuAD算法利用文檔在子話題中的覆蓋情況，計算文檔間的相關(guān)程度。該算法認(rèn)為，如果兩個文檔對子話題的覆蓋情況越相似，那么這兩個文檔就相關(guān)。然而，我們發(fā)現(xiàn)，對于相同的文檔，使用不同粒度的子話題，xQuAD得到文檔相關(guān)性可能完全不同。繼續(xù)以表1中的子話題為例，假設(shè)文檔d1和d2與細粒度子話題“三毛流浪記電影”相關(guān)，文檔d3和細粒度子話題“三毛流浪記電視劇”相關(guān)，文檔d4和細粒度子話題“三毛作品集下載”相關(guān)。

任務(wù)(1) 尋找與d1最相關(guān)的文檔: 使用粗粒度子話題的xQuAD認(rèn)為d1、d2和d3都與子話題“三毛流浪記”相關(guān)，判斷d2和d3都是和d1最相關(guān)的文檔；使用細粒度子話題的xQuAD發(fā)現(xiàn)只有d1和d2屬于相同子話題，判斷只有d2才是與d1最相關(guān)的文檔。顯然，在任務(wù)(1)中，使用細粒度子話題的xQuAD獲勝。

任務(wù)(2) 尋找與d1最不相關(guān)的文檔。使用細粒度子話題的xQuAD認(rèn)為d3和d4都與d1的子話題不同，判斷d3和d4都是和d1最不相關(guān)的文檔；使用粗粒度子話題的xQuAD發(fā)現(xiàn)只有d4和d1屬于不同子話題，判斷d4才是與d1最不相關(guān)的文檔。于是，在任務(wù)(2)中，使用粗粒度子話題的xQuAD獲勝。因此，xQuAD對于使用不同粒度子話題是較為敏感的，故本文選用該算法，來測試使用不同粒度子話題對搜索結(jié)果多樣化的影響。

3.2 PM2算法

PM2是關(guān)注主題比例的模型(topic proportionality model)。該類模型認(rèn)為，一個多樣化的搜索結(jié)果，其文檔包含的子話題分布應(yīng)該滿足某種比例。因此，在每次選擇最佳文檔d*時，應(yīng)該優(yōu)先選擇最能改善當(dāng)前子話題分布的文檔。

由Dang和Croft在2012年提出的PM2[7]算法，是主題比例模型的代表算法。該算法將最佳文檔的選擇過程劃分為兩個步驟: 首先基于已選擇文檔的子話題分布情況，選擇最需要改善的子話題為最佳子話題t*；然后選擇與該子話題盡可能相關(guān)，并且與其他子話題比較相關(guān)的文檔，作為當(dāng)前的最佳文檔d*。

在確定子話題的分布比例時，PM2算法參考了新西蘭官方選舉時采用的Sainte-Lagu?模型*Sainte-Lagu?: http: //www.elections.org.nz/voting/mmp/sainte-lague.html。該模型根據(jù)黨派收到的選票數(shù)量來確定黨派的席位比例，認(rèn)為如果一個黨派收到的票數(shù)越多，目前已有席位越少，則該黨派是目前最需要增加席位的黨派。同理，子話題的重要性越高，被已選擇文檔占用的席位越少，則該子話題越需要改善。在選擇最佳子話題時，PM2根據(jù)子話題ti在查詢中的權(quán)重P(ti|q)，和該子話題ti在已選擇文檔S中占用的席位si(seat)，計算該子話題ti目前需要改善的份額qti(quotient)。具體公式如下:

(3)

其中，

(4)

(5)

綜上所述，PM2算法利用子話題的占用比例選擇最優(yōu)子話題，并通過最優(yōu)子話題影響最優(yōu)文檔的選擇。我們發(fā)現(xiàn)，由于不同粒度子話題本身存在一定差異，使用不同粒度子話題，PM2得到的子話題占有比例很可能不同，選出的最優(yōu)子話題肯定不同，最終找到的最優(yōu)文檔差別可能更大。繼續(xù)考慮3.1節(jié)中的例子，假設(shè)所有子話題的初始比例為均勻分布，已選擇的文檔為d1,與細粒度子話題“三毛流浪記電影”相關(guān)，需要PM2選則下一個最佳文檔。使用粗粒度子話題的PM2認(rèn)為，已被占有的子話題是“三毛流浪記”，下次的文檔應(yīng)該從“三毛作品”中選，于是選擇了文檔d4(和細粒度子話題“三毛作品集下載”相關(guān))。使用細粒度子話題的PM2認(rèn)為，已被占有的子話題是“三毛流浪記電影”，子話題“三毛流浪記電視劇”并未被占用，于是選擇了文檔d3。由于PM2算法本身對子話題的依賴性較強，對于不同粒度的子話題也非常敏感。本文選擇在此算法上比較不同粒度的子話題，希望找到一個更合適的子話題粒度，使該算法的表現(xiàn)更穩(wěn)定。

4 實驗

4.1 不同粒度子話題的生成 本文使用Google搜索引擎提供的query suggestions生成子話題[6-7]。在每次抽取query suggestions前，我們清空緩存，以避免Google的個性化推薦功能的影響。

對于每個查詢，我們將該查詢輸入Google并抽取其query suggestions作為子話題T1，稱之為粗粒度子話題。隨后，我們把T1中的每個子話題依次輸入Google，將取得的query suggestions合并為子話題集T2，稱之為細粒度子話題。同理，將T2中的子話題輸入Google并合并其query suggestions作為子話題集T3，稱之為微粒度子話題。我們發(fā)現(xiàn)，有時Google對于某些子話題并沒有提供query suggestions。即該子話題已經(jīng)是最細粒度了。此時，我們將該子話題直接加入下一個子話題集合中，以保證兩個子話題集合的意義一致性。

若繼續(xù)重復(fù)此過程，我們可以繼續(xù)獲得更細粒度的子話題，在本文中，我們只討論以上三種粒度的子話題。對于每個查詢，我們得到了三個不同粒度的子話題集T1、T2和T3。為了和前人的工作保持一致，我們假設(shè)，每個子話題集合中的子話題重要性都是均勻分布的。

4.2 實驗設(shè)計

4.2.1 數(shù)據(jù)集 實驗使用信息檢索競賽NTCIR-11中的IMine task提供的公開數(shù)據(jù)。我們使用其中文部分，包含32個有歧義或?qū)挿旱闹形牟樵?，以及官方提供的來自SogouT2008*SogouT2008: http: //www.sogou.com/labs/dl/t-e.html的初始搜索結(jié)果。注意，在NTCIR數(shù)據(jù)中，對每個查詢，提供兩層多樣性相關(guān)標(biāo)注: 基于粗粒度子話題的相關(guān)評價，基于細粒度子話題的相關(guān)評價。

4.2.2 評價標(biāo)準(zhǔn)

實驗使用TREC Web Track官方推薦的三個評價標(biāo)準(zhǔn)ERR-IA[26]，α-NDCG[27]和NRBP[28]，以及NTCIR IMine task提供的官方評價標(biāo)準(zhǔn)D#-measures[29]。實驗中，所有評價標(biāo)準(zhǔn)的相關(guān)參數(shù)均采用官方默認(rèn)值。實驗比較了@5，@10和@20的結(jié)果，發(fā)現(xiàn)其結(jié)果相似。為了節(jié)省空間，本文僅報告@20的評價結(jié)果。

4.2.3 實驗算法

未多樣化的基準(zhǔn)結(jié)果(baseline)，傳統(tǒng)多樣化算法MMR[10]，經(jīng)典多樣化算法xQuAD和PM2。其中，MMR通過比較文檔內(nèi)容的冗余來判斷新穎性，和子話題無關(guān)，在實驗中作為基準(zhǔn)算法參與比較。傳統(tǒng)的xQuAD和PM2算法，使用Google suggestions作為子話題(同4.4節(jié)中粗粒度子話題T1)。本文通過Google suggestions提供了三種不同粒度的子話題T1、T2和T3，并將其分別應(yīng)用于上述兩個算法中。我們用xQuAD1、xQuAD2和xQuAD3分別代表使用T1、T2和T3作為子話題的xQuAD算法。同理，我們得到PM21、PM22和PM23。此外，受子話題生成方法影響，本文中粒度較小的子話題包含更多數(shù)量的子話題。為了避免子話題數(shù)量對算法的影響，我們定義了合并子話題T12=T1∪T2和T123=T1∪T2∪T3，并分別將其應(yīng)用到算法，記為xQuAD12、PM212、xQuAD123和PM2123。注意，MMR、xQuAD和PM2各有一個可調(diào)參數(shù)λ，我們用交叉驗證分別為各個算法調(diào)參數(shù)。

4.3 子話題粒度對多樣性的影響

本節(jié)討論使用不同粒度的子話題對xQuAD和PM2的影響。實驗發(fā)現(xiàn)，傳統(tǒng)xQuAD和PM2在前50個文檔時表現(xiàn)最佳，故本節(jié)只比較對前50個文檔進行多樣化的結(jié)果，更多的文檔數(shù)量的結(jié)果將在下節(jié)中討論。表2展示了所有算法在NTCIR數(shù)據(jù)中的評價結(jié)果，包括基于粗粒度用戶意圖的評價和基于細粒度用戶意圖的評價。

表2 基于不同粒度子話題的算法在NTCIR數(shù)據(jù)中的結(jié)果

注: xQuAD和PM2在每個評價標(biāo)準(zhǔn)上的最佳結(jié)果，用黑體表示。

實驗結(jié)果顯示，在PM2相關(guān)算法中，PM23在所有評價標(biāo)準(zhǔn)上都取得了最好的結(jié)果。在ERR-IA，α-NDCG和NRBP上，PM2相關(guān)算法的表現(xiàn)保持一致，即使用微粒度子話題的PM23表現(xiàn)最好，細粒度子話題的PM22其次，傳統(tǒng)的粗粒度子話題PM21表現(xiàn)最差。具體地，在基于粗粒度的ERR-IA，α-NDCG和NRBP上，PM23比PM21提升了1%；在基于細粒度的α-NDCG和NRBP上，PM23比PM22提升了1%。同時，在所有評價標(biāo)準(zhǔn)的結(jié)果中，PM212比PM22低，PM2123比PM23低，說明引入更多的子話題不能直接改善PM2的結(jié)果。因此，PM23的優(yōu)勢是來源于其子話題的粒度。以上結(jié)果表明，當(dāng)使用不同粒度的子話題時，子話題粒度越小，PM2的表現(xiàn)越好，并在使用微粒度子話題時達到最佳。

導(dǎo)致該現(xiàn)象的一個可能的原因是，使用微粒度子話題能幫助PM2模型更好地選擇最佳子話題。假設(shè)兩個極細粒度子話題t1,1,1和t1,1,2來自細粒度子話題t1,1，細粒度子話題t1,1和t1,2來自粗粒度子話題t1，文檔d1和d2與t1,1,1相關(guān)，文檔d3與t1,1,2相關(guān)，文檔d4與t1,2,1相關(guān)。對上述四個文檔進行排序時，PM21認(rèn)為只存在一個子話題t1，所有文檔均與其相關(guān)，輸出結(jié)果可能為d1→d2→d3→d4。PM22認(rèn)為存在兩個子話題t1,1和t1,2，其中t1,1相關(guān)文檔為d1、d2、d3，t1,2的相關(guān)文檔為d4，最佳子話題的選擇順序可能為t1,1→t1,2→t1,1→t1,1，可能輸出結(jié)果d1→d4→d2→d3。PM23認(rèn)為存在三個子話題t1,1,1、t1,1,2、t1,2,1，最佳子話題的選擇順序為t1,1,1→t1,2,1→t1,1,2→t1,1,1，可能輸出結(jié)果d1→d4→d3→d2。根據(jù)多樣性定義，應(yīng)將冗余文檔(此處為d2)排在較后的位置，而PM21、PM22、PM23分別將d2排在第2、3、4位，則PM23輸出排序的多樣性最佳。于是，子話題的粒度越細，PM2模型越能更好地識別文檔在更小粒度上的冗余情況，從而提高結(jié)果多樣性。

在另一方面，xQuAD的實驗結(jié)果顯示，xQuAD2在所有評價標(biāo)準(zhǔn)上的結(jié)果均為最佳。此外，當(dāng)使用不同粒度的用戶意圖對評價算法時，xQuAD1和xQuAD3的表現(xiàn)不同: 對基于粗粒度用戶意圖的評價標(biāo)準(zhǔn)ERR-IA，α-NDCG和D#-nDCG，采用粗粒度子話題的xQuAD1較好，極細粒度的xQuAD3較差；對基于細粒度用戶意圖的所有評價標(biāo)準(zhǔn)，采用微粒度子話題的xQuAD3較好, 粗粒度子話題的xQuAD1較差。同時，xQuAD12和xQuAD123表現(xiàn)較弱，說明xQuAD的表現(xiàn)與子話題的數(shù)量沒有明顯關(guān)系。上述結(jié)果說明，使用不同粒度子話題的xQuAD，對于評價時選用的真實用戶意圖的粒度較為敏感: 當(dāng)使用粗粒度的用戶意圖做評價時，xQuAD應(yīng)使用較粗粒度的子話題T1或T2，避免使用微粒度的T3；當(dāng)使用細粒度的用戶意圖做評價時，xQuAD應(yīng)使用較細粒度的子話題T2或T3，避免使用粗粒度的T1。在本文的三類粒度子話題中，子話題T2的粒度居中，其對應(yīng)的xQuAD算法在兩種用戶意圖的評價中均取得了最佳的表現(xiàn)，是風(fēng)險最小的子話題粒度。

上述現(xiàn)象的一個可能的原因是，xQuAD算法利用了文檔對子話題的覆蓋情況來估算文檔多樣性，而子話題粒度大小對于文檔的覆蓋情況有直接影響。假設(shè)文檔d1與子話題t1,1,1和t2,1,1相關(guān)，文檔d2與子話題t1,1,1和t1,2,1相關(guān)，文檔d3與子話題t1,1,1和t1,1,2相關(guān)，比較上述文檔的多樣性: 使用粗粒度子話題的xQuAD1認(rèn)為，d1覆蓋了兩個子話題t1和t2，d2和d3只覆蓋了一個子話題t1，則文檔多樣性排序為d1>d2=d3；使用細粒度子話題的xQuAD2認(rèn)為，d1覆蓋了兩個子話題t1,1和t2,1，d2覆蓋了兩個子話題t1,1和t1,2，d3只覆蓋了一個子話題t1,1，則文檔多樣性排序為d1=d2>d3；使用微粒度子話題的xQuAD3認(rèn)為d1、d2、d3都覆蓋了兩個不同的子話題，其多樣性相同d1=d2=d3。顯然，當(dāng)真實用戶意圖的粒度較粗時，無法分辨極細粒度，用戶認(rèn)為t1,1,1和t1,1,2相同，判斷d3只與一個子話題相關(guān)，此時xQuAD3不適用；當(dāng)真實用戶意圖的粒度較細時，細粒度的區(qū)分變得重要，用戶認(rèn)為t1,1,1和t1,2,1不同，判斷d2與兩個不同子話題相關(guān)，此時xQuAD1不適用。而對于xQuAD2，面對粗粒度用戶意圖時能正確判斷d3，面對細粒度用戶意圖時能正確判斷d2，綜合表現(xiàn)最佳。于是，使用細粒度的子話題，能幫助xQuAD模型更合理地估算文檔對子話題的覆蓋情況，在兩種用戶意圖下均能穩(wěn)定地判斷文檔多樣性，從而提高結(jié)果多樣性。

4.4 文檔數(shù)量對不同粒度子話題算法的影響

本節(jié)討論算法在對不同數(shù)量的文檔進行多樣化時的表現(xiàn)，研究文檔數(shù)量對使用不同粒度子話題算法的影響。實驗比較了NTCIR數(shù)據(jù)上所有評價標(biāo)準(zhǔn)的結(jié)果，發(fā)現(xiàn)其結(jié)果類似，故本文只報告基于粗粒度用戶意圖的ERR-IA的評價結(jié)果。圖1展示了使用不同粒度子話題的xQuAD和PM2對不同數(shù)量的文檔進行多樣化的結(jié)果。

圖1 xQuAD和PM2在對不同數(shù)量的文檔進行多樣化時的ERR-IA結(jié)果對比

實驗結(jié)果顯示，xQuAD和PM2在50個文檔上表現(xiàn)最好，該結(jié)論與前人工作[7]一致。對于xQuAD相關(guān)算法，雖然其在不同文檔集中的表現(xiàn)不穩(wěn)定，但當(dāng)文檔數(shù)量相同時，表現(xiàn)最佳的都是使用細粒度子話題的xQuAD2，并且參與多樣化的文檔越多，xQuAD2相對于xQuAD1的優(yōu)勢越大。一個潛在原因是，細粒度子話題的部分新增內(nèi)容與原查詢的相關(guān)程度較低，沒有出現(xiàn)在靠前的文檔中，只有當(dāng)參與文檔的數(shù)量夠大時，才逐漸有新增內(nèi)容的相關(guān)文檔被找到。于是，使用細粒度子話題的xQuAD，在文檔數(shù)量增加時，能找到更多新穎的文檔。

與之不同的是，PM2的相關(guān)算法和文檔數(shù)量的關(guān)系較為穩(wěn)定，隨著文檔數(shù)量的增加，其表現(xiàn)遞減。當(dāng)文檔數(shù)量相同時，不同粒度的子話題在PM2上表現(xiàn)并不穩(wěn)定: 在50個文檔和100個文檔的數(shù)據(jù)上,PM23表現(xiàn)最好，PM22次之；在150個文檔和200個文檔的數(shù)據(jù)上,PM22表現(xiàn)最佳。由于在50個文檔中PM23相對于PM22的優(yōu)勢并不明顯，因此，對PM2，使用細粒度的子話題是一個更安全的選擇。

5 總結(jié)

本文關(guān)注搜索結(jié)果多樣化算法中的子話題粒度問題，利用Google suggestions生成了三種不同粒度的子話題，分別稱之為粗粒度子話題、細粒度子話題和微粒度子話題，其中粗粒度子話題為傳統(tǒng)多樣化算法經(jīng)常使用的子話題。本文將三種子話題運用到經(jīng)典的搜索結(jié)果多樣化算法xQuAD和PM2中，比較了不同粒度的子話題對搜索結(jié)果多樣化算法的影響。從NTCIR數(shù)據(jù)上得到的實驗結(jié)果表明，使用細粒度的子話題的多樣性算法，比用粗粒度子話題時表現(xiàn)好，比用微粒度子話題時穩(wěn)定。

[1] Bernard J Jansen, Amanda Spink, Tefko Saracevic. Real life, real users, and real needs: a study and analysis of user queries on the web[J]. Information Processing & Management, 2000,36(2): 207-227.

[2] Dou Z, Song R, Wen J R. A large-scale evaluation and analysis of personalized search strategies[C]//Proceedings of WWW, 2007: 581-590.

[3] Ruihua Song, Zhenxiao Luo, Jianyun Nie, et al. Identification of ambiguous queries in web search[J]. IPM, 2009: 45(2).

[4] Rakesh Agrawal,Sreenivas Gollapudi, Alan Halverson, et al. Diversifying search results[C]//Proceedings of WSDM, 2009.

[5] Saul Vargas, Pablo Castells, DavidVallet. Explicit relevance models in intent-oriented information retrieval diversification[C]//Proceedings of SIGIR, 2012: 75-84.

[6] Rodrygo L T Santos, Craig Macdonald, Iadh Ounis. Exploiting query reformulations for web search result diversification[C]//Proceedings of WWW, 2010: 881-890.

[7] Van Dang, W Bruce Croft. Diversity by proportionality: an election-based approach to search result diversification[C]//Proceedings of SIGIR, 2012: 65-74.

[8] BenCarterette, Praveen Chandar. Probabilistic models of ranking novel documents for faceted topic retrieval[C]//Proceedings of CIKM, Hong Kong, China, 2009: 1287-1296.

[9] Van Dang, W. Bruce Croft. Term level search result diversification[C]//Proceedings of SIGIR, 2013: 603-612.

[10] Jaime Carbonell, Jade Goldstein. The use of MMR, diversity-based reranking for reordering documents and producing summaries[C]//Proceedings of SIGIR, 1998.

[11] Chengxiang Zhai, John Lafferty. A risk minimization framework for information retrieval[J]. IPM, 2006: 42(1): 31-55.

[12] Xiaojin Zhu, Andrew Goldberg, Jurgen Van Gael, et al. Improving diversity in ranking using absorbing random walks[C]//Proceedings of HLT-NAACL, 2007.

[13] Benyu Zhang, Hua Li, Yi Liu, et al. Improving web search results using anity graph[C]//Proceedings of SIGIR, 2005: 504-511.

[14] Karthik Raman, Paul N Bennett, Kevyn Collins-Thompson. Toward whole-session relevance: exploring intrinsic diversity in web search[C]//Proceedings of SIGIR, 2013.

[15] Hai-Tao Yu, Fuji Ren. Search result diversification via filling up multiple knap-sacks[C]//Proceedings of CIKM, Shanghai, China, 2014: 609-618.

[16] Shangsong Liang, Zhaochun Ren, Maarten de Rijke. Fusion helps diversification[C]//Proceedings of SIGIR, 2014: 303-312.

[17] FilipRadlinski, Robert Kleinberg, Thorsten Joachims. Learning diverse rankings with multi-armed bandits[C]//Proceedings of ICML, 2008.

[18] Zhicheng Dou, Sha Hu, Kun Chen, et al. Multi- dimensional search result diversification[C]//Proceedings of WSDM, Hong Kong, China, 2011: 475-484.

[19] Jiyin He, Vera Hollink, Arjen de Vries. Combining implicit and explicit topic representations for result diversification[C]//Proceedings of SIGIR, 2012: 851-860.

[20] Yisong Yue, Thorsten Joachims. Predicting diverse subsets using structural svms[C]//Proceedings of ICML, 2008.

[21] Yadong Zhu, Yanyan Lan, Jiafeng Guo, et al. Learning for search result diversification[C]//Proceedings of SIGIR, 2014: 293-302.

[22] Dawn Lawrie, W. Bruce Croft, Arnold Rosenberg. Finding topic words for hierarchical summarization[C]//Proceedings of SIGIR, New Orleans, Louisiana, USA, 2001: 349-357.

[23] Zhicheng Dou, Sha Hu, Yulong Luo, et al. Finding dimensions for queries[C]//Proceedings of CIKM, 2011.

[24] Yunhua Hu, Yanan Qian, Hang Li, et al. Mining query subtopics from search log data[C]//Proceedings of SIGIR, Portland, Ore-gon, USA, 2012: 305-314.

[25] Shoaib Jameel, Wai Lam. An unsupervised topic segmentation model incorporating word order[C]//Proceedings of SIGIR, Dublin, Ireland, 2013: 203-212.

[26] Olivier Chapelle, Donald Metlzer, Ya Zhang, et al. Expected reciprocal rank for graded relevance[C]//Proceedings of CIKM, Hong Kong, China, 2009: 621-630.

[27] Charles L A Clarke,Maheedhar Kolla, Gordon V Cormack, et al. Novelty and diversity in information retrieval evaluation[C]//Proceedings of SIGIR, 2008: 659-666.

[28] Charles L Clarke,Maheedhar Kolla, Olga Vechtomova. An eectiveness measure for ambiguous and underspecified queries[C]//Proceedings of ICTIR, 2009.

[29] Tetsuya Sakai, Ruihua Song. Evaluating diversified search results using per-intent graded relevance[C]//Proceedings of SIGIR, Beijing, China, 2011: 1043-1052.

胡莎(1985—)，博士，講師，主要研究領(lǐng)域為互聯(lián)網(wǎng)大數(shù)據(jù)信息檢索，語言本處理，大數(shù)據(jù)分析和數(shù)據(jù)挖掘。

E-mail: husha@swu.edu.cn

竇志成(1980—),博士，副教授、博士生導(dǎo)師。主要研究領(lǐng)域為信息檢索、自然語言處理、大數(shù)據(jù)分析和深度學(xué)習(xí)。

E-mail: dou@ruc.edu.cn

文繼榮(1972—),博士，教授，主要研究領(lǐng)域為大數(shù)據(jù)管理和分析、信息檢索、數(shù)據(jù)挖掘和機器學(xué)習(xí)。

E-mail: jrwen@ruc.edu.cn

The Impact of Various Grained Subtopics on Search Result Diversification

HU Sha1, DOU Zhicheng2,3, WEN Jirong2,3

(1. College of Computer & Information Science, Southwest University, Chongqing 400715, China;2. Information of School, Renmin University of China, Beijing 100086, China;3. Beijing Key Laboratory of Big Data Management and Analysis Methods, Beijing 100086, China)

1003-0077(2017)04-0165-09

TP311

A

2015-10-12 定稿日期: 2016-03-25

國家重點基礎(chǔ)研究發(fā)展計劃/973計劃(2014CB340403);國家自然科學(xué)基金(61502501)