信息檢索與web搜索課件 08學(xué)習(xí)資料

信息檢索與Web搜索

第8講完整搜索系統(tǒng)中的評分計算Scoresinacompletesearchsystem授課人：高曙明

*改編自“現(xiàn)代信息檢索”網(wǎng)上公開課件（/~wangbin）*改編自“現(xiàn)代信息檢索”網(wǎng)上公開課件（/~wangbin）排序的重要性不排序的問題用戶只希望看到一些而不是成千上萬的結(jié)果很難構(gòu)造能夠有效產(chǎn)生所需結(jié)果的查詢即使是專家也很難排序能夠?qū)⒊汕先f條結(jié)果縮減至幾條結(jié)果，因此非常重要實際上，大部分用戶只看1到3條結(jié)果222排序的重要性基于用戶行為數(shù)據(jù)的排序重要性分析摘要閱讀(Viewingabstracts):用戶更可能閱讀前幾頁(1,2,3,4)的結(jié)果的摘要點擊(Clicking):點擊的分布甚至更有偏向性一半情況下，用戶點擊排名最高的頁面即使排名最高的頁面不相關(guān)，仍有30%的用戶會點擊結(jié)論：正確排序相當(dāng)重要，排對最高的頁面非常重要33快速評分及排序必要性：高維向量的余弦相似度計算具有相當(dāng)計算量查詢反饋需要實時可行性：返回與查詢最相關(guān)的前K篇文檔即可排序本身不需要精確計算余弦相似度64精確topK檢索及其加速辦法目標(biāo)：從文檔集的所有文檔中快速找出K個與查詢最相關(guān)的文檔加速策略：加快每個余弦相似度的計算不對所有文檔的評分結(jié)果排序而直接選出TopK篇文檔一個簡單的加速方法：通過忽略查詢向量的權(quán)重和歸一化來提高余弦計算速度

5余弦快速計算算法6基于堆的前K個結(jié)果快速選出基本思路：基于堆選出前K個結(jié)果，避免對所有的文檔按照評分排序堆：二叉樹的一種，每個節(jié)點上的值>子節(jié)點上的值(MaxHeap)堆構(gòu)建：需要2J次操作基于堆選出前K個結(jié)果：每個結(jié)果需要2logJ步如果J=1M,K=100,那么代價大概是全部排序代價的10%7

堆構(gòu)建樣例(篩選shift法-摘自網(wǎng)上課件)7，10，13，15，4，20，19，8（數(shù)據(jù)個數(shù)n=8）8910基于堆選出TopK(4)1112131415提前終止計算對每篇文檔定義一個與查詢無關(guān)的靜態(tài)質(zhì)量得分g(d)，并將文檔按照靜態(tài)質(zhì)量得分排序：g(d1)>g(d2)>g(d3)>...將靜態(tài)得分和余弦相似度線性組合得到文檔的最后得分net-score(q,d)=g(d)+cos(q,d)終止計算條件當(dāng)目前找到的topK的得分中最小的都大于g(d)+1.1時，不再對排在后面的文檔進(jìn)行計算

1616提前終止計算舉例假設(shè):(i)g→[0,1];(ii)檢索算法按照d1,d2,…，依次計算(為文檔為單位的計算，document-at-a-time)，當(dāng)前處理的文檔的g(d)<0.1；(iii)而目前找到的topK的得分中最小的都>1.2由于后續(xù)文檔的得分不可能超過1.1(cos(q,d)<1)所以，既然已經(jīng)得到了topK結(jié)果，不需要再進(jìn)行后續(xù)計算1717精確topK檢索的問題仍然無法避免大量文檔參與計算一個自然而然的考慮是：能否盡量減少參與計算文檔數(shù)目，即使不能完全保證正確性也在所不惜。即采用這種方法得到的topK雖然接近但是并非真正的topK非精確topK檢索1818非精確topK檢索及其加速目標(biāo)：從文檔集的所有文檔中快速找出K個能夠滿足用戶需求的文檔一般思路：基于啟發(fā)式策略找一個文檔集合A，K<|A|<<N，利用A中的topK結(jié)果代替整個文檔集的topK結(jié)果即給定查詢后，A是整個文檔集上近似剪枝得到的結(jié)果不僅適用于余弦相似度得分，也適用于其他相似度計算方法1919加速方法一：索引去除啟發(fā)式策略：對于包含多個詞項的查詢，通過只考慮查詢中的部分詞項來減少需要處理的文檔集具體方法只考慮那些包含高idf查詢詞項的文檔只考慮那些包含多個查詢詞項的文檔問題：候選結(jié)果文檔數(shù)目少于K20僅考慮高idf詞項對于查詢catcherintheryeA集由catcher和rye的倒排記錄中的所有文檔組成直覺：文檔當(dāng)中的in和the不會顯著改變得分因此也不會改變得分順序優(yōu)點:低idf詞項會對應(yīng)很多文檔，這些文檔會排除在集合A之外21僅考慮包含多個詞項的文檔A集由包含查詢中大部分查詢詞項的文檔構(gòu)成比如，至少4中含3這相當(dāng)于賦予了一種所謂軟合取(softconjunction)的語義上述A集很容易通過倒排記錄表合并算法確定如何實現(xiàn)?22索引去除舉例（4中含3）BrutusCaesarCalpurnia235813214816326412816Antony4816326412832888161616323232僅對文檔8、16和32進(jìn)行計算23加速方法二：勝者表啟發(fā)式策略：對每個詞項，預(yù)先計算出其倒排記錄表中權(quán)重最高的r篇文檔，以它們?yōu)榛A(chǔ)生成A集這r篇文檔稱為t的勝者表(Championlist)也稱為優(yōu)勝表(fancylist)或高分文檔(topdocs)具體方法：采用tf-idf機制，取tf最高的r篇文檔A集為所有查詢詞項的勝者表中包含的文檔集合的并集r可以在索引建立時就已經(jīng)設(shè)定，有可能r<K24課堂思考勝者表方式和前面的索引去除方式有什么關(guān)聯(lián)？如何融合它們？如何在一個倒排索引當(dāng)中實現(xiàn)勝者表？提醒：勝者表與docID大小無關(guān)25加速方法三：靜態(tài)得分排序方式啟發(fā)式策略：與勝者表相同特點：采用全局勝者表，包含g(d)+tf-idf

得分最高的r篇文檔g(d)：文檔的靜態(tài)質(zhì)量得分，與查詢無關(guān)，用以反映文檔的權(quán)威度，[0,1]之間的值權(quán)威度示例Wikipedia在所有網(wǎng)站上的重要性某些權(quán)威報紙上的文章高引用的論文…26基于net-score的TopK文檔檢索為每篇文檔賦予一個與查詢無關(guān)的(query-independent)[0,1]之間的值，記為g(d)對每個詞項，建立其全局勝者表給定查詢后，采用net-score(q,d)=g(d)+cosine(q,d)

對所有全局勝者表的并集中的文檔計算其最后得分，返回net-score最高的topK文檔27利用g(d)排序的優(yōu)點首先按照g(d)從高到低將倒排記錄表進(jìn)行排序該排序?qū)λ械古庞涗洷矶际且恢碌?只與文檔本身有關(guān))這種排序下，高分文檔更可能在倒排記錄表遍歷的前期出現(xiàn)在時間受限的應(yīng)用當(dāng)中(比如，任意搜索需要在50ms內(nèi)返回結(jié)果),上述方式可以提前結(jié)束倒排記錄表的遍歷28加速方法四：影響度排序啟發(fā)式策略：只對影響度大的文檔進(jìn)行處理對倒排記錄表中的文檔按照影響度進(jìn)行排序，比如按照tft,d值的降序排序，排序與查詢相關(guān)不必專門維護(hù)勝者表如果只想對wft,d

足夠高的文檔進(jìn)行計算，那么就可以將文檔按照wft,d排序需要注意的是：這種做法下，倒排記錄表的排序并不是一致的(排序指標(biāo)和查詢相關(guān))那么如何實現(xiàn)topK的檢索?29減少文檔數(shù)目的具體方法提前結(jié)束遍歷遍歷倒排表時，可以在如下情況之一發(fā)生時停止：遍歷了固定的文檔數(shù)目rwft,d低于某個預(yù)定的閾值對查詢詞項按照idf降序處理對于多詞項組成的查詢，按照idf從大到小掃描詞項在此過程中，會不斷更新文檔的得分(即本詞項的貢獻(xiàn))，如果文檔得分基本不變的話，停止30加速方法五：簇剪枝啟發(fā)式策略：基于聚類剪枝產(chǎn)生A集具體方法隨機選

N篇文檔作為先導(dǎo)者對于其他文檔，計算和它最近的先導(dǎo)者這些文檔依附在先導(dǎo)者上面，稱為追隨者這樣一個先導(dǎo)者平均大約有

N個追隨者給定查詢Q,找離它最近的先導(dǎo)者L從L及其追隨者中找到前K個與Q最接近的文檔返回Sec.7.1.631簇剪枝示意圖QueryLeaderFollower32一般化的簇剪枝方法每個追隨者可以附著在b1(比如3)個最近的先導(dǎo)者上對于查詢，可以尋找最近的b2(比如4)個先導(dǎo)者及其追隨者作用：保證找到前K篇文檔33課堂思考為了找到最近的先導(dǎo)者，需要計算多少次余弦相似度？為什么第一步中采用

N個先導(dǎo)者？常數(shù)b1,b2會對結(jié)果有什么影響？設(shè)計一個例子，上述方法可能會失敗，比如返回的K篇文檔中少了一篇真正的topK文檔3435以文檔為單位的處理按照docID排序和按照PageRank排序都與詞項本身無關(guān)(即兩者都是文檔的固有屬性)，因此在全局這種序都是一致的余弦相似度計算方法可以采用以文檔為單位(document-at-a-time)的處理方式即在開始計算文檔di+1的得分之前，先得到文檔di

的得分另一種方式:以詞項為單位(term-at-a-time)的處理3536以詞項為單位的處理最簡單的情況：對第一個查詢詞項，對它的倒排記錄表進(jìn)行完整處理對每個碰到的docID設(shè)立一個累加器然后，對第二個查詢詞項的倒排記錄表進(jìn)行完整處理...如此循環(huán)往復(fù)363737以詞項為單位的處理38上述算法的改進(jìn)對于Web來說(200億頁面),在內(nèi)存中放置包含所有頁面的累加器數(shù)組是不可能的因此，僅對那些出現(xiàn)在查詢詞項倒排記錄表中的文檔建立累加器這相當(dāng)于，對那些得分為0的文檔不設(shè)定累加器(即那些不包含任何查詢詞項的文檔)3839累加器設(shè)定舉例查詢:[BrutusCaesar]:僅為文檔1,5,7,13,17,83,87設(shè)立累加器不為文檔8,40,85設(shè)立累加器3940完整的搜索系統(tǒng)示意圖4041多層次索引基本思路建立多層索引，每層關(guān)于索引詞項具有不同的重要程度查詢處理過程中，從最高層索引開始如果最高層索引已經(jīng)返回至少k個結(jié)果，那么停止處理并將結(jié)果返回給用戶如果結(jié)果<k篇文檔，那么從下一層繼續(xù)處理，直至索引用完或者返回至少k個結(jié)果為止例子：兩層的系統(tǒng)第1層:所有標(biāo)題的索引；第2層:文檔剩余部分的索引標(biāo)題中包含查詢詞的頁面相對于正文包含查詢詞的頁面而言，排名更應(yīng)該靠前4142多層次索引的例子4243搜索系統(tǒng)組成部分(已介紹)文檔預(yù)處理(語言及其他處理)位置信息索引多層次索引拼寫校正k-gram索引(針對通配查詢和拼寫校正)文檔評分以詞項為單位的處理方式4344搜索系統(tǒng)組成部分(未介紹)文檔緩存(cache):用它來生成文檔摘要(snippet)域索引：按照不同的域進(jìn)行索引，如文檔正文，文檔中所有高亮的文本，錨文本、元數(shù)據(jù)字段中的文本等等鄰近式排序(如,查詢詞項彼此靠近的文檔的得分應(yīng)該高于查詢詞項距離較遠(yuǎn)的文檔)基于機器學(xué)習(xí)的排序函數(shù)：確定權(quán)重參數(shù)查詢分析器4445查詢分析將用戶輸入的“自由文本查詢”轉(zhuǎn)換成帶操作符的查詢，以提高查詢效果舉例：risinginterestrates整體作為短語查詢分為2個詞的短語查詢作為3個獨立詞查詢4546VSM對各種查詢操作的支持向量空間模型一般只支持自由文本查詢布爾、通配符、短語等查詢操作增強了查詢表達(dá)力對布爾查詢的支持：很難，尚無好的解決方法對通配符查詢的支持：先將通配符詞項轉(zhuǎn)化成一組查詢詞項，再用VSM對短語查詢的支持：實現(xiàn)基于位置索引的短語查詢，很難，無法計算權(quán)重4647參考資料《信息檢索導(dǎo)論》第6、7章/irHowGoogletweaksitsrankingfunctio