《統(tǒng)計(jì)自然語言處理與信息檢索》信息檢索5-查詢擴(kuò)展

1、信息檢索信息檢索第五講第五講 相關(guān)反饋和查詢擴(kuò)展相關(guān)反饋和查詢擴(kuò)展提綱 問題背景 相關(guān)反饋顯式相關(guān)反饋隱式相關(guān)反饋偽相關(guān)反饋 查詢擴(kuò)展基于人工詞典基于自動(dòng)構(gòu)建詞典基于查詢?nèi)罩疽?、背景：為什么要進(jìn)行相關(guān)反饋和查詢擴(kuò)展？ 用戶有明確的查詢目的，但是用戶不知道如何構(gòu)造好的查詢，因此，初始查詢往往不能很好地表達(dá)其查詢需求 用戶沒有經(jīng)驗(yàn) 查詢的表達(dá)方式很多 對(duì)檢索系統(tǒng)不熟悉 對(duì)目標(biāo)文檔分布不熟悉 用戶不知道要具體查詢什么，需要查看結(jié)果以后才逐漸細(xì)化 4搜索中提高召回率的方法 本講的主題：兩種提高召回率的方法相關(guān)反饋及查詢擴(kuò)展 考慮查詢q: aircraft . . . 某篇文檔 d 包含“plane”,

2、 但是不包含 “aircraft” 顯然對(duì)于查詢q，一個(gè)簡(jiǎn)單的IR系統(tǒng)不會(huì)返回文檔d，即使d是和q最相關(guān)的文檔 我們?cè)噲D改變這種做法： 也就是說，我們會(huì)返回不包含查詢?cè)~項(xiàng)的相關(guān)文檔。45關(guān)于召回率Recall 本講當(dāng)中會(huì)放松召回率的定義，即(在前幾頁)給用戶返回更多的相關(guān)文檔 這可能實(shí)際上會(huì)降低召回率，比如，將jaguar擴(kuò)展為jaguar(美洲虎；一種汽車品牌)+panthera(豹屬) 可能會(huì)去掉一些相關(guān)的文檔，但是可能增加前幾頁返回給用戶的相關(guān)文檔數(shù)56提高召回率的方法 局部(local)方法: 對(duì)用戶查詢進(jìn)行局部的即時(shí)的分析 主要的局部方法: 相關(guān)反饋(relevance feedba

3、ck) 第一部分 全局(Global)方法: 進(jìn)行一次性的全局分析(比如分析整個(gè)文檔集)來產(chǎn)生同/近義詞詞典 利用該詞典進(jìn)行查詢擴(kuò)展(query expansion ) 第二部分67二、相關(guān)反饋 用戶提交一個(gè)(簡(jiǎn)短的)查詢 搜索引擎返回一系列文檔 用戶將部分返回文檔標(biāo)記為相關(guān)的，將部分文檔標(biāo)記為不相關(guān)的 搜索引擎根據(jù)標(biāo)記結(jié)果計(jì)算得到信息需求的一個(gè)新查詢表示。當(dāng)然我們希望該表示好于初始的查詢表示 搜索引擎對(duì)新查詢進(jìn)行處理，返回新結(jié)果 新結(jié)果可望（理想上說）有更高的召回率7基本思想基本思想相關(guān)反饋分類 用戶相關(guān)反饋或顯式相關(guān)反饋(User Feedback or Explicit Feedback

4、): 用戶顯式參加交互過程 隱式相關(guān)反饋(Implicit Feedback)：系統(tǒng)跟蹤用戶的行為來推測(cè)返回文檔的相關(guān)性，從而進(jìn)行反饋。 偽相關(guān)反饋或盲相關(guān)反饋(Pseudo Feedback or Blind Feedback)：沒有用戶參與，系統(tǒng)直接假設(shè)返回文檔的前k篇是相關(guān)的，然后進(jìn)行反饋。89相關(guān)反饋 相關(guān)反饋可以循環(huán)若干次 不僅僅局限于文檔910圖片檢索時(shí)的反饋1011初始查詢的結(jié)果1112用戶反饋: 選擇相關(guān)結(jié)果1213相關(guān)反饋后再次檢索的結(jié)果1314 相關(guān)反饋中的核心概念：質(zhì)心質(zhì)心是一系列點(diǎn)的中心前面我們將文檔表示成高維空間中的點(diǎn)因此，我們可以采用如下方式計(jì)算文檔的質(zhì)心 其中D是

5、一個(gè)文檔集合， 是文檔d的的向量表示1415 質(zhì)心的例子1516 Rocchio算法是向量空間模型中相關(guān)反饋的實(shí)現(xiàn)方式 Rocchio算法選擇使下式最大的查詢 Dr : 相關(guān)文檔集; Dnr : 不相關(guān)文檔集 上述公式的意圖是 將相關(guān)文檔和不相關(guān)文檔分得最開的向量。 可以將上式改寫為:16Rocchio算法 17Rocchio算法17 最優(yōu)查詢向量為： 即將相關(guān)文檔的質(zhì)心移動(dòng)一個(gè)量，該量為相關(guān)文檔質(zhì)心和不相關(guān)文檔的差異量18課堂練習(xí): 計(jì)算Rocchio向量 圓形點(diǎn): 相關(guān)文檔, 叉叉點(diǎn): 不相關(guān)文檔1819Rocchio算法圖示 : 相關(guān)文檔的質(zhì)心1920Rocchio算法圖示 不能將相關(guān)/

6、不相關(guān)文檔分開2021Rocchio算法圖示 不相關(guān)文檔的質(zhì)心2122Rocchio算法圖示2223Rocchio 算法圖示 - 差異向量2324Rocchio算法圖示 加上差異向量 2425Rocchio算法圖示 得到2526Rocchio算法圖示 能夠?qū)⑾嚓P(guān)/不相關(guān)文檔完美地分開2627Rocchio算法圖示 能夠?qū)⑾嚓P(guān)/不相關(guān)文檔完美地分開2728Rocchio 1971 算法 (SMART系統(tǒng)使用)qm: 修改后的查詢; q0: 原始查詢; Dr 、Dnr : 已知的相關(guān)和不相關(guān)文檔集合；, , : 權(quán)重 新查詢向相關(guān)文檔靠攏而遠(yuǎn)離非相關(guān)文檔 vs. / 設(shè)置中的折中: 如果判定的文檔

7、數(shù)目很多，那么 /可以考慮設(shè)置得大一些 一旦計(jì)算后出現(xiàn)負(fù)權(quán)重，那么將負(fù)權(quán)重都設(shè)為0 在向量空間模型中，權(quán)重為負(fù)是沒有意義的。28實(shí)際中使用的公式:29正(Positive)反饋 vs. 負(fù)(Negative)反饋 正反饋價(jià)值往往大于負(fù)反饋 比如，可以通過設(shè)置 來給正反饋更大的權(quán)重 很多系統(tǒng)甚至只允許正反饋，即=02930相關(guān)反饋中的假設(shè) 什么時(shí)候相關(guān)反饋能否提高召回率？ 假設(shè) A1: 對(duì)于某初始查詢，用戶知道在文檔集中使用哪些詞項(xiàng)來表達(dá) 假設(shè)A2: 相關(guān)文檔中出現(xiàn)的詞項(xiàng)類似 (因此，可以基于相關(guān)反饋，從一篇相關(guān)文檔跳到另一篇相關(guān)文檔) 或者: 所有文檔都緊密聚集在某個(gè)prototype周圍 或

8、者: 有多個(gè)不同的prototype, 但是它們之間的用詞具有顯著的重合率 相關(guān)文檔和不相關(guān)文檔之間的相似度很低3031假設(shè)A1不成立的情況 假設(shè) A1: 對(duì)于某初始查詢，用戶知道在文檔集中使用哪些詞項(xiàng)來表達(dá) 不成立的情況：用戶的詞匯表和文檔集的詞匯表不匹配 例子： cosmonaut / astronaut3132假設(shè)A2不成立的情況 假設(shè)A2: 相關(guān)文檔中出現(xiàn)的詞項(xiàng)類似 假設(shè)不成立的查詢例子： contradictory government policies 互相矛盾的政府政策 一些相關(guān)的文檔集合，但是文檔集合彼此之間并不相似 文檔集合1：煙草種植者的補(bǔ)貼 vs. 禁煙運(yùn)動(dòng) 文檔集合2：

9、對(duì)發(fā)展中國(guó)家的幫助 vs. 發(fā)展中國(guó)家進(jìn)口商品的高關(guān)稅 有關(guān)煙草文檔的相關(guān)反饋并不會(huì)對(duì)發(fā)展中國(guó)家的文檔有所幫助3233相關(guān)反饋的評(píng)價(jià) 選擇上一講中的某個(gè)評(píng)價(jià)指標(biāo)，比如 P10 計(jì)算原始查詢q0 檢索結(jié)果的P10指標(biāo) 計(jì)算修改后查詢q1檢索結(jié)果的P10指標(biāo) 大部分情況下q1 的檢索結(jié)果精度會(huì)顯著高于q0! 上述評(píng)價(jià)過程是否公平？3334相關(guān)反饋的評(píng)價(jià) 公平的評(píng)價(jià)過程一定要基于存留文檔集(residual collection): 用戶沒有判斷的文檔集 研究表明采用，采用這種方式進(jìn)行評(píng)價(jià)，相關(guān)反饋是比較成功的一種方法 經(jīng)驗(yàn)而言，一輪相關(guān)反饋往往非常有用，相對(duì)一輪相關(guān)反饋，兩輪相關(guān)反饋效果的提高有限

10、。3435相關(guān)反饋的評(píng)價(jià) 公平的評(píng)價(jià)過程一定要基于存留文檔集(residual collection): 用戶沒有判斷的文檔集 研究表明采用，采用這種方式進(jìn)行評(píng)價(jià)，相關(guān)反饋是比較成功的一種方法 經(jīng)驗(yàn)而言，一輪相關(guān)反饋往往非常有用，相對(duì)一輪相關(guān)反饋，兩輪相關(guān)反饋效果的提高有限。3536有關(guān)評(píng)價(jià)的提醒 相關(guān)反饋有效性的正確評(píng)價(jià)，必須要和其他需要花費(fèi)同樣時(shí)間的方法進(jìn)行比較 并沒有清晰的證據(jù)表明，相關(guān)反饋是用戶實(shí)踐中使用的最佳方法 相關(guān)反饋的一種替代方法: 用戶修改并重新提交新的查詢 用戶更傾向于修改和重新提交查詢而不是判斷文檔的相關(guān)性3637課堂提問 搜索引擎是否使用相關(guān)反饋? 為什么?3738相關(guān)

11、反饋存在的問題 相關(guān)反饋開銷很大 相關(guān)反饋生成的新查詢往往很長(zhǎng) 長(zhǎng)查詢的處理開銷很大 用戶不愿意提供顯式的相關(guān)反饋 Excite搜索引擎曾經(jīng)提供完整的相關(guān)反饋功能，但是后來廢棄了這一功能3839隱式相關(guān)反饋 通過觀察用戶對(duì)當(dāng)前檢索結(jié)果采取的行為來給出對(duì)檢索結(jié)果的相關(guān)性判定。 判定不一定很準(zhǔn)確，但是省卻了用戶的顯式參與過程。 對(duì)用戶非當(dāng)前檢索行為或非檢索相關(guān)行為的分析也可以用于提高檢索的效果，這些是個(gè)性化信息檢索(Personalized IR)的主要研究?jī)?nèi)容，并非本節(jié)的主要內(nèi)容。40用戶行為種類 鼠標(biāo)鍵盤動(dòng)作：點(diǎn)擊鏈接、加入收藏夾、拷貝粘貼、停留、翻頁等等 用戶眼球動(dòng)作Eye tracking

12、可以跟蹤用戶的眼球動(dòng)作拉近、拉遠(yuǎn)、瞟、凝視、往某個(gè)方向轉(zhuǎn)41點(diǎn)擊行為(Click through behavior)FIELDVALUEUser ID1162742023015Time stamp06/Nov/2006:00:01:35Query terms嫁給警察的理由URLhttp:/ number1Rank7Anchor text姑娘們，你們?cè)敢饧藿o警察嗎？慈溪社區(qū)42眼球動(dòng)作(通過鼠標(biāo)軌跡模擬)43關(guān)于Eye tracking44隱式相關(guān)反饋小結(jié) 優(yōu)點(diǎn)：不需要用戶顯式參與，減輕用戶負(fù)擔(dān)用戶行為某種程度上反映用戶的興趣，具有可行性 缺點(diǎn)：對(duì)行為分析有較高要求準(zhǔn)確度不一定能保證某些情況下需

13、要增加額外設(shè)備45偽相關(guān)反饋(Pseudo-relevance feedback) 偽相關(guān)反饋對(duì)于真實(shí)相關(guān)反饋的人工部分進(jìn)行自動(dòng)化 偽相關(guān)反饋算法 對(duì)于用戶查詢返回有序的檢索結(jié)果 假定前 k 篇文檔是相關(guān)的 進(jìn)行相關(guān)反饋 (如 Rocchio) 平均上效果不錯(cuò) 但是對(duì)于某些查詢而言可能結(jié)果很差 幾次循環(huán)之后可能會(huì)導(dǎo)致查詢漂移(query drift)4546TREC4上的偽相關(guān)反饋實(shí)驗(yàn) 比較了兩種長(zhǎng)度歸一化機(jī)制 (L vs. l) 以及反饋不反饋后的結(jié)果 (PsRF). 實(shí)驗(yàn)中的偽相關(guān)反饋方法對(duì)查詢只增加了20個(gè)詞項(xiàng) (Rocchio將增加更多的詞項(xiàng)) 上述結(jié)果表明，偽相關(guān)反饋在平均意義上說是

14、有效的方法46檢索方法相關(guān)文檔數(shù)目lnc.ltc3210lnc.ltc-PsRF3634Lnu.ltu3709Lnu.ltu-PsRF4350 使用Cornell大學(xué)的SMART系統(tǒng) 50個(gè)查詢，每個(gè)查詢基于前100個(gè)結(jié)果進(jìn)行反饋47偽相關(guān)反饋小結(jié) 優(yōu)點(diǎn)：不用考慮用戶的因素，處理簡(jiǎn)單很多實(shí)驗(yàn)也取得了較好效果 缺點(diǎn)：沒有通過用戶判斷，所以準(zhǔn)確率難以保證不是所有的查詢都會(huì)提高效果相關(guān)反饋新查詢?cè)~的選擇 基于局部聚類(local clustering)的方法 基于局部上下文分析(local context analysis, LCA)的方法 基于局部聚類的方法 利用局部文檔對(duì)term進(jìn)行聚類，即將相

15、關(guān)的term聚在一起，聚類的結(jié)果稱為一個(gè)個(gè)簇(cluster)，接著利用簇中的相關(guān)term對(duì)查詢 q 進(jìn)行擴(kuò)展。 關(guān)鍵：定義term之間的相似度，不同的相似度定義得到不同的簇。 三種簇定義： 關(guān)聯(lián)簇Association clusters 度量簇Metric clusters 標(biāo)量簇Scalar clusters 關(guān)聯(lián)簇(1),( ,)( ,)u vujvjjcf t df t d關(guān)聯(lián)簇(2)基于簇的查詢擴(kuò)展基于局部上下文分析的方法 局部聚類的缺點(diǎn)：計(jì)算的是 q 中每個(gè) term和所有 term 之間的相似度，而不是計(jì)算 q 和所有 term 的相似度。 LCA 的思想：在局部文檔中計(jì)算出和查

16、詢 q 最相近的 term 進(jìn)行擴(kuò)展。LCA的三個(gè)步驟 第一步，將所有文檔都進(jìn)行分段(比如300字節(jié)一段)，并將每個(gè)段落看成檢索對(duì)象，用原始查詢 q 檢索，返回和 q 最相似的 n 個(gè)段落 第二步，計(jì)算這 n 個(gè)段落中的每個(gè)概念c(通常就是term)和 q 的相似度sim(q,c) 第三步，選擇sim值最高的 m個(gè)概念加入到原始查詢中。其中加入的概念的權(quán)重為1-0.9*i/m，i為其在m個(gè)概念中的排序序號(hào)。原始查詢的term的權(quán)重設(shè)置為一個(gè)較大的值，比如2。q和c的相似度計(jì)算LCA的使用 是用于平滑的常數(shù)，常常取近的值。 sim(q,c)可以看成是利用TF*IDF進(jìn)行相似度計(jì)算的一個(gè)變種。 L

17、CA在不同的文檔集合上表現(xiàn)的效果不一致，因此，常常要在使用前做相應(yīng)調(diào)整(調(diào)整公式)。 57三、查詢擴(kuò)展(Query expansion) 查詢擴(kuò)展是另一種提高召回率的方法 我們使用 “全局查詢擴(kuò)展” 來指那些 “查詢重構(gòu)(query reformulation)的全局方法” 在全局查詢擴(kuò)展中，查詢基于一些全局的資源進(jìn)行修改，這些資源是與查詢無關(guān)的 主要使用的信息: 同義詞或近義詞 同義詞或近義詞詞典(thesaurus) 兩種同(近)義詞詞典構(gòu)建方法：人工構(gòu)建和自動(dòng)構(gòu)建57實(shí)例GoogleBaidu60查詢擴(kuò)展的類型 人工構(gòu)建的同(近)義詞詞典 (人工編輯人員維護(hù)的詞典，如 PubMed) 自

18、動(dòng)導(dǎo)出的同(近)義詞詞典 (比如，基于詞語的共現(xiàn)統(tǒng)計(jì)信息) 基于查詢?nèi)罩就诰虺龅牟樵兊葍r(jià)類 (Web上很普遍)6061基于同(近)義詞詞典的查詢擴(kuò)展 對(duì)查詢中的每個(gè)詞項(xiàng)t, 將詞典中與t語義相關(guān)的詞擴(kuò)充到查詢中 例子: HOSPITAL MEDICAL 通常會(huì)提高召回率 可能會(huì)顯著降低正確率，特別是對(duì)那些有歧義的詞項(xiàng) INTEREST RATE INTEREST RATE FASCINATE 廣泛應(yīng)用于特定領(lǐng)域(如科學(xué)、工程領(lǐng)域)的搜索引擎中 創(chuàng)建并持續(xù)維護(hù)人工詞典的開銷非常大6162同(近)義詞詞典的自動(dòng)構(gòu)建 通過分析文檔集中的詞項(xiàng)分布來自動(dòng)生成同(近)義詞詞典 基本的想法是計(jì)算詞語之間的相

19、似度 定義 1: 如果兩個(gè)詞各自的上下文共現(xiàn)詞類似，那么它們類似 “car” “motorcycle” ，因?yàn)樗鼈兌寂c “road”、“gas” 及 “l(fā)icense”之類的詞共現(xiàn)，因此它們類似 定義 2: 兩個(gè)詞，如果它們同某些一樣的詞具有某種給定的語法關(guān)系的話，那么它們類似 可以harvest, peel, eat, prepare apples 和pears, 因此 apples 和pears肯定彼此類似62基于詞典的查詢擴(kuò)展 首先還是定義term之間的相似度，不過這種相似度計(jì)算中沒有使用共現(xiàn)頻率。設(shè)N為所有文檔數(shù)目，t為整個(gè)文檔集中的term數(shù)目，tj為文檔dj中的不同term數(shù)目，則

20、可以定義所謂文檔dj的逆term頻率itfj（可以和逆文檔頻率idf進(jìn)行類比）logjjtitftTerm之間的相似度計(jì)算(1) 對(duì)于所有N篇文檔，考慮其矩陣表示 每個(gè)wi,j表示的是ki,dj對(duì)應(yīng)的權(quán)重 fi,j為term ki在文檔dj中的頻度,221,0.50.5max ()0.50.5max ()i jjji ji jNi jjiji jfitffwfitffTerm之間的相似度計(jì)算(2) 將上述矩陣的第i行看成term ki的一個(gè)向量表示 計(jì)算term ku和kv之間的相似度，可以采用內(nèi)積計(jì)算方法，至此，可以得到term相似度矩陣。其中的u行v列為：ik,ju vuvu jv jdckkww 查詢q和term之間的相似度計(jì)算 將q向量化，將q看成一篇文檔，對(duì)于q中