信息檢索導論第七章

1、第七章一個完整搜索系統(tǒng)中的評分計算一個完整搜索系統(tǒng)中的評分計算前情回顧7.1 快速評分及排序精確Top K檢索 加速辦法1、加快每個余弦相似度的計算檢索排序就是找查詢的K近鄰，一般而言，在高維空間下，計算余弦相似度沒有很高效的方法，但是如果查詢很短，是有一定辦法加速計算的，而且普通的索引能夠支持這種快速計算。查詢詞項無權重，相當于假設每個查詢詞項都出現(xiàn)1次，于是，不需要對查詢向量進行歸一化，進而可以對上一講給出的余弦相似度計算算法進行輕微的簡化。2、不對所有文檔的評分結(jié)果排序而直接選出TOP K 篇文檔檢索時，通常只需要返回前K條結(jié)果，可以對所有的文檔評分后排序，選出前K個結(jié)果，但是這個排序過

2、程可以避免，令 J = 具有非零余弦相似度值的文檔數(shù)目從J中選K個最大的。（堆法N中選K） 1 19 13 15 20 2 3 4 5 6 7 8 3、能否不需要計算N篇文檔的得分提前終止計算到目前為止的倒排記錄表都按照docID排序，接下來將采用與查詢無關的另外一種反映結(jié)果好壞程度的指標(靜態(tài)質(zhì)量)。例如: 頁面d的PageRank g(d), 就是度量有多少好頁面指向d的一種指標 (參考第 21章)于是可以將文檔按照PageRank排序 g(d1) g(d2) g(d3) . . .將PageRank和余弦相似度線性組合得到文檔的最后得分 net-score(q, d) = g(d) +

3、cos(q, d)假設: (i) g 0, 1; (ii) 檢索算法按照d1,d2,，依次計算(為文檔為單位的計算，document-at-a-time)，當前處理的文檔的 g(d) 1.2由于后續(xù)文檔的得分不可能超過1.1 ( cos(q,d) 1 )所以，我們已經(jīng)得到了top K結(jié)果，不需要再進行后續(xù)計算 精確TOP K檢索仍然無法避免大量文檔參與計算一個自然而言的問題就是能否盡量減少參與計算文檔數(shù)目，即使不能完全保證正確性也在所不惜。即采用這種方法得到的top K雖然接近但是并非真正的top K-非精確top K檢索。 檢索是為了得到與查詢匹配的結(jié)果，該結(jié)果要讓用戶滿意，余弦相似度是刻畫

4、用戶滿意度的一種方法，非精確top K的結(jié)果如果和精確top K的結(jié)果相似度相差不大，應該也能讓用戶滿意。減少參與計算的文檔數(shù)目的一些方法，包括下面兩個步驟： 找一個文檔集合A，它包含了參與最后競爭的候選文檔，其中K|A|N，A不必包含前K篇得分最高的文檔，但它要包括很多和前K篇文檔得分相近的文檔。 返回A中得分最高的K篇文檔小結(jié)方法一：索引去除一般檢索方法中，通常只考慮至少包含一個查詢詞項的文檔，可以進一步拓展這種思路。一、只考慮那些包含高idf查詢詞項的文檔對于查詢 catcher in the rye，僅考慮包含catcher和rye的文檔的得分。 文檔當中的in 和 the不會顯著改變

5、得分,因此也不會改變得分順序優(yōu)點:低idf詞項會對應很多文檔，這些文檔會排除在集合A之外二、只考慮那些包含多個查詢詞項的文檔(比如達到一定比例，3個詞項至少出現(xiàn)2個，4個中至少出現(xiàn)3個等等)對于多詞項查詢而言，只需要計算包含其中大部分詞項的文檔比如，至少4中含3這相當于賦予了一種所謂軟合取(soft conjunction)的語義 (早期Google使用了這種語義)指的是在對一個包含多個詞項的查詢進行檢索時，檢索中的文檔中只要出現(xiàn)大部分查詢詞項即可，并不要求出現(xiàn)全部查詢詞項 方法二：勝者表對每個詞項t，預先計算出其倒排記錄表中權重最高的r篇文檔，如果采用tf-idf機制，即tf最高的r篇注意：

6、r 比如在索引建立時就已經(jīng)設定，詞項t所對應的tf值最高的r篇文檔構成t的勝者表。 因此，有可能 r K檢索時，僅計算某些詞項的勝者表中包含的文檔集合的并集 從這個集合中選出top K作為最終的top K方法三：靜態(tài)質(zhì)量得分排序方式我們希望排名靠前的文檔不僅相關度高(relevant) ，而且權威度也大(authoritative)相關度常常采用余弦相似度得分來衡量而權威度往往是一個與查詢無關的量，是文檔本身的屬性權威度示例：Wikipedia在所有網(wǎng)站上的重要性、某些權威報紙上的文章、論文的引用量、被 diggs, Y!buzzes或del.icio.us等網(wǎng)站的標注量、Pagerank 權

7、威度計算為每篇文檔賦予一個與查詢無關的(query-independent ) 0,1之間的值，記為g(d) 同前面一樣，最終文檔排名基于g(d)和相關度的線性組合。 net-score(q,d) = g(d) + cosine(q,d)查找net-score最高的top K文檔首先按照g(d)從高到低將倒排記錄表進行排序(p96)該排序?qū)λ械古庞涗洷矶际且恢碌?只與文檔本身有關)因此，可以并行遍歷不同查詢詞項的倒排記錄表來 進行倒排記錄表的合并 及余弦相似度的計算利用g(d)排序的優(yōu)點這種排序下，高分文檔更可能在倒排記錄表遍歷的前期出現(xiàn)在時間受限的應用當中 (比如，任意搜索需要在50ms內(nèi)

8、返回結(jié)果), 上述方式可以提前結(jié)束倒排記錄表的遍歷將g(d)排序和勝者表相結(jié)合對每個詞項維護一張勝者表，該表中放置了r篇g(d) + tf-idftd 值最高的文檔檢索時只對勝者表進行處理高端表(High list)和低端表(Low list)對每個詞項，維護兩個倒排記錄表 ，分別成為高端表和低端表 比如可以將高端表看成勝者表遍歷倒排記錄表時，僅僅先遍歷高端表 如果返回結(jié)果數(shù)目超過K，那么直接選擇前K篇文檔返回 否則，繼續(xù)遍歷低端表，從中補足剩下的文檔數(shù)目上述思路可以直接基于詞項權重，不需要全局量g(d)實際上，相當于將整個索引分層方法四：影響度(Impact)排序一、以文檔為單位（docum

9、ent-at-a-time）的評分方法 按照docID排序和按照PageRank排序都與詞項本身無關(即兩者都是文檔的固有屬性)，因此倒排記錄表使用統(tǒng)一的排序方式。 上述計算余弦相似度的方法可以采用以文檔為單位的處理方式。 即在開始計算文檔di+1 的得分之前，先得到文檔di 的得分。二、以詞項為單位(term-at-a-time)的評分方法 最簡單的情況：對第一個查詢詞項，對它的倒排記錄表進行完整處理,對每個碰到的docID設立一個累加器,然后，對第二個查詢詞項的倒排記錄表進行完整處理,如此循環(huán)往復。具體思路：將詞項t對應的所有文檔按d按照tftd值降序排列降低用于累加得分的文檔數(shù)目的做法提

10、前結(jié)束法 遍歷倒排記錄表時，可以在如下情況之一發(fā)生時停止：（1）遍歷了固定的文檔數(shù)目r（2）wft,d 低于某個預定的閾值 2. 將詞項按照idf排序?qū)τ诙嘣~項組成的查詢，按照idf從大到小掃描詞項在此過程中，會不斷更新文檔的得分(即本詞項的貢獻)，如果文檔得分基本不變的話，停止方法五： 簇剪枝(Cluster pruning)隨機選 N 篇文檔作為先導者對于其他文檔，計算和它最近的先導者 這些文檔依附在先導者上面，稱為追隨者(follower) 這樣一個先導者平均大約有 N 個追隨者查詢處理過程查詢處理過程給定查詢 Q, 找離它最近的先導者L從L及其追隨者集合中找到前K個與Q最接近的文檔返回

11、采取隨機抽樣的原因采取隨機抽樣的原因速度快先導者能夠反映數(shù)據(jù)的分布情況一般化變形（一般化變形（p97p97）每個追隨者可以附著在b1 (比如3)個最近的先導者上對于查詢，可以尋找最近的b2 (比如4)個先導者及其追隨者7.2信息檢索系統(tǒng)的組成層次型索引 基本思路: 建立多層索引，每層對應索引詞項的重要性 查詢處理過程中，從最高層索引開始 如果最高層索引已經(jīng)返回至少k (比如, k = 100)個結(jié)果，那么停止處理并將結(jié)果返回給用戶 如果結(jié)果 k 篇文檔，那么從下一層繼續(xù)處理，直至索引用完或者返回至少k 個結(jié)果為止 page83查詢詞項的鄰近性 對于檢索中的查詢，特別是Web上的自由文本查詢來說

12、，用戶往往希望返回的文檔中與大部分或者全部查詢詞項之間的距離比較近，因為這表明返回文檔中具有聚焦用戶查詢意圖的文本。 考慮一個由兩個或者多個查詢詞項構成的查詢t1, t2, . . . , tk。令文檔d中包含所有查詢詞項的最小窗口大小為，其取值為窗口內(nèi)詞的個數(shù)。例如，假設某篇文檔僅僅包含一個句子The quality of mercy is not strained，那么查詢strained mercy 在此文檔中的最小窗口大小是4。直觀上講，的值越小，文檔d和查詢匹配程度更高。如果文檔中不包含所有的查詢詞項，那么此時可以將設成一個非常大的數(shù)字。在計算時，還可以考慮各種可能的策略變化，比如在

13、以單詞個數(shù)來計算窗口寬度時，可以不考慮停用詞的數(shù)目。查詢分析及文檔評分函數(shù)的設計rising interest rates 之類的查詢，如何處理？依賴于用戶數(shù)量、查詢分布及文檔集本身。通常情況下，會有一個查詢分析器（query parser）將用戶輸入的關鍵詞轉(zhuǎn)換成帶操作符的查詢，該查詢能夠基于底層的索引結(jié)構進行處理。有時，這種處理過程可能需要基于底層索引結(jié)果對多個查詢進行處理，比如，查詢分析器可能會產(chǎn)生如下的一系列查詢。1. 將用戶輸入的查詢字符串看成一個短語查詢。利用向量空間模型求解，此時輸入查詢向量是以rising interest rates 為基的1 維向量。2. 如果包含短語rising interest rates 的文檔數(shù)目少于10 篇，那么會將原始查詢看成rising interest 和interest rates 兩個查詢短語，同樣通過向量空間方法來計算。3. 如果結(jié)果仍然少于10 個，那么重新利用向量空間模型求解，這時候認為3 個查詢詞項之間是互相獨立的。7.3向量空間模型對各種查詢操作的支持向量空間模型支持自由文本查詢，這與前面的布爾查詢、通配符查