《概率檢索模型》ppt課件

1、Introduction to Information Retrieval 現(xiàn)代信息檢索現(xiàn)代信息檢索中科院研究生院2011年秋季課程現(xiàn)代信息檢索 更新時間： Modern Information Retrieval授課人：王斌http:/ introduction to Information retrieval”網(wǎng)上公開的課件，地址 /IR-book/第11講 概率檢索模型Probabilistic Information Retrieval12021/11/07.提綱2上一講及向量空間模型回想根本概率統(tǒng)計知識Logistic回歸模型BIM模型BM

2、25模型.提綱3上一講及向量空間模型回想根本概率統(tǒng)計知識Logistic回歸模型BIM模型BM25模型.現(xiàn)代信息檢索 4構(gòu)造化檢索(Structured retrieval) 根本配置： 構(gòu)造化或非構(gòu)造化查詢+構(gòu)造化文檔結(jié)構(gòu)化檢索的應(yīng)用場景數(shù)字圖書館、專利數(shù)據(jù)庫、博客、包含已標(biāo)注命名實體（如人名、地名）的文本例子 數(shù)字圖書館: give me a full-length article on fast fourier transforms 專利: give me patens whose claims mention RSA public key encryption and that cit

3、e US patent 4,405,829 實體標(biāo)記文本: give me articles about sightseeing tours of the Vatican and the Coliseum4.現(xiàn)代信息檢索 5XML 文檔5.現(xiàn)代信息檢索 6挑戰(zhàn)1: 前往文檔的一部分 XML檢索中，用戶希望前往文檔的一部分即 XML元素，而不像非構(gòu)造化檢索那樣往往前往整個文檔上述情況下，用戶能夠在查找 場(scene)但是，另一個沒有詳細指定前往節(jié)點的查詢Macbeth，應(yīng)該前往劇本的稱號而不是某個子單位 處理方法: 構(gòu)造化文檔檢索原理(structured document retrieval

4、 principle)例子如果在莎士比亞全集中查找Macbeths castle，那么到底應(yīng)該返回場（scene）、幕（act）還是整個劇本呢？6.現(xiàn)代信息檢索 7構(gòu)造化文檔檢索原理上述原理睬引發(fā)這樣一種檢索戰(zhàn)略，即前往包含信息需求的最小單位但是，要在算法上實現(xiàn)這種原理是非常困難的。比如查詢： title:Macbeth， 整個劇本的標(biāo)題Maccbeth以及第一幕第六場的標(biāo)題Macbeths castle都是包含匹配詞項Macbeth的較好的命中結(jié)果。然而在這個例子中，劇本的標(biāo)題這個位于更高層的節(jié)點作為答案卻更適宜確定查詢應(yīng)對的正確層次是非常困難的。結(jié)構(gòu)化文檔檢索原理選擇最合適的文檔部分:系統(tǒng)

5、應(yīng)該總是檢索出回答查詢的最明確最具體的文檔部分7.挑戰(zhàn)2: 如何確定文檔的索引單位8 IR索引和排名中的中心概念：文檔單位或索引單位在非構(gòu)造化檢索中，適宜的文檔單位往往比較明顯，如PC上的文檔、郵件、Web上的網(wǎng)頁等等而在構(gòu)造化檢索中，卻有定義索引單位的一系列不同的方法將節(jié)點分組，構(gòu)成多個互不重疊的偽文檔pseudodocument )索引最大元素，然后自頂向下(top down)后處置索引葉節(jié)點，然后自底向上(bottom up)進展后處置擴展對一切元素建立索引.現(xiàn)代信息檢索 挑戰(zhàn)3：元素嵌套針對元素嵌套所呵斥的冗余性，普遍的做法是對前往元素進展限制。這些限制戰(zhàn)略包括： 這些限制戰(zhàn)略包括：忽

6、略一切的小元素忽略用戶不會閱讀的一切元素類型這需求記錄當(dāng)前XML檢索系統(tǒng)的運轉(zhuǎn)日志信息忽略通常被評價者斷定為不相關(guān)性的元素類型假設(shè)有相關(guān)性斷定的話 只保管系統(tǒng)設(shè)計人員或圖書館員認定為有用的檢索結(jié)果所對應(yīng)的元素類型在大部分上述方法中，結(jié)果集中依然包含嵌套元素。9.現(xiàn)代信息檢索 基于詞匯化子樹表示的向量空間模型目的: 對向量空間中的每一維都同時思索單詞及其在XML樹中的位置信息做法: 將XML文檔映射成詞匯化子樹BookTitleAuthorBillGatesMicrosoftAuthorBillGatesMicrosoftBillGatesTitleMicrosoftAuthorGatesAut

7、horBillBookTitleMicrosoft. . . Book10.現(xiàn)代信息檢索 INEX(Initiative for the Evaluation of XML retrieval)INEX: XML檢索研討中的首要評測平臺，它經(jīng)過協(xié)作產(chǎn)生參考文檔集、查詢集及相關(guān)性判別。在每年一度的INEX會議上，研討人員展現(xiàn)并討論交流各自的研討結(jié)果。INEX 2002文檔集包含大約12000篇來自IEEE期刊的文章。(自2006 年開場，INEX運用英文Wikipedia這個更大的庫)文檔的相關(guān)性斷定主要經(jīng)過人工判別來完成INEX 2002 文檔集統(tǒng)計信息文檔集統(tǒng)計信息12,107文檔數(shù)目494

8、 MB規(guī)模19952002文章發(fā)表年份1,532平均每篇文檔中的XML節(jié)點個數(shù)6.9平均每個節(jié)點的深度30CAS主題的數(shù)目30CO 主題的數(shù)目11. 現(xiàn)代信息檢索向量空間模型 文檔表示成向量 查詢也表示成向量 計算兩個向量之間的類似度：余弦類似度、內(nèi)積類似度等等 在向量表示中的詞項權(quán)重計算方法主要是tf-idf公式，實踐思索tf、idf及文檔長度3個要素12.現(xiàn)代信息檢索 13tf-idf權(quán)重計算的三要素13. 現(xiàn)代信息檢索14向量空間模型的優(yōu)缺陷 優(yōu)點： 簡約直觀，可以運用到很多其他領(lǐng)域(文本分類、生物信息學(xué))。 支持部分匹配和近似匹配，結(jié)果可以排序 檢索效果不錯 缺陷： 實際上不夠：基于直

9、覺的閱歷性公式 標(biāo)引項之間的獨立性假設(shè)與實踐不符：實踐上，term的出現(xiàn)之間是有關(guān)系的，不是完全獨立的。如：“王勵勤 “乒乓球的出現(xiàn)不是獨立的。. 現(xiàn)代信息檢索本講內(nèi)容 概率根底知識 基于概率實際的檢索模型 Logistic回歸模型 二值獨立概率模型 BIM：不思索詞項頻率和文檔長度 思索詞項頻率和文檔長度的BM25模型15.提綱16上一講及向量空間模型回想根本概率統(tǒng)計知識Logistic回歸模型BIM模型BM25模型.現(xiàn)代信息檢索 概率 vs. 統(tǒng)計概率概率統(tǒng)計統(tǒng)計necessity概率是統(tǒng)計的實際根底統(tǒng)計是概率的實踐運用典型問題： 知某數(shù)據(jù)總體滿足某分布，抽樣得到某數(shù)據(jù)的概率是多少？典型問

10、題：知某抽樣數(shù)據(jù)(或總體分布)，判別總體的分布(或分布參數(shù)) 是多少？. 現(xiàn)代信息檢索概率統(tǒng)計初步 隨機實驗與隨機事件 概率和條件概率 乘法公式、全概率公式、貝葉斯公式 隨機變量 隨機變量的分布18. 現(xiàn)代信息檢索隨機實驗和隨機事件 隨機實驗：可在一樣條件下反復(fù)進展；實驗?zāi)軌蚪Y(jié)果不止一個，但能確定一切的能夠結(jié)果；一次實驗之前無法確定詳細是哪種結(jié)果出現(xiàn)。 擲一顆骰子，思索能夠出現(xiàn)的點數(shù) 隨機事件：隨機實驗中能夠出現(xiàn)或能夠不出現(xiàn)的情況叫“隨機事件 擲一顆骰子，4點朝上19. 現(xiàn)代信息檢索概率和條件概率 概率：直觀上來看，事件A的概率是指事件A發(fā)生的能夠性，記為P(A) 擲一顆骰子，出現(xiàn)6點的概率為

11、多少？ 條件概率：知事件A發(fā)生的條件下，事件B發(fā)生的概率稱為A條件下B的條件概率，記作P(B|A) 30顆紅球和40顆黑球放在一塊，請問第一次抽取為紅球的情況下第二次抽取黑球的概率？20. 現(xiàn)代信息檢索乘法公式、全概率公式和貝葉斯公式1( )() (|)niiiP BP A P B A21 乘法公式： P(AB)P(A)P(B|A) P(A1A2An)P(A1)P(A2|A1).P(An|A1An1) 全概率公式：A1A2An是整個樣本空間的一個劃分 貝葉斯公式： A1A2An是整個樣本空間的一個劃分1() (|)(|),(1,., )() (|)jjjniiiP A P B AP ABjnP

12、 A P B A. 現(xiàn)代信息檢索22事件的獨立性 兩事件獨立：事件A、B，假設(shè)P(AB)=P(A)P(B)，那么稱A 、B獨立 三事件獨立：事件A B C，假設(shè)滿足P(AB)=P(A)P(B), P(AC)=P(A)P(C),P(BC)=P(B)P(C), P(ABC)=P(A)P(B)P(C)，那么稱A、B、C獨立 多事件獨立：兩兩獨立、三三獨立、四四獨立. 現(xiàn)代信息檢索隨機變量 隨機變量：假設(shè)隨機實驗的各種能夠的結(jié)果都能用一個 變量的取值或范圍來表示，那么稱這個變量為隨機變量，常用X、Y、Z來表示 (離散型隨機變量)：擲一顆骰子，能夠出現(xiàn)的點數(shù)X (能夠取值1、2、3、4、5、6) (延續(xù)

13、型隨機變量)：北京地域的溫度(-1545)23.現(xiàn)代信息檢索 各種分布關(guān)系圖二值二值分布分布多值多值多項多項分布分布n元貝努元貝努利分布利分布二項二項分布分布分布n重貝努利實驗k次朝上的概率硬幣朝上或朝下X=0 或者1骰子某個面朝上X=0,1,2,3n 重實驗，X1=x1, X2=x2,n次不同硬幣n重貝努利實驗. 現(xiàn)代信息檢索貝努利 瑞士數(shù)學(xué)家家族，產(chǎn)生過11位數(shù)學(xué)家 雅可比貝努利(Jacob Bernoulli) : 1654-1705 積分“integral這一術(shù)語即由他首創(chuàng) 貝努利實驗、貝努利分布25. 現(xiàn)代信息檢索26概率檢索模型 檢索系統(tǒng)中，給定查詢，計算每個文檔的相關(guān)度 檢索系統(tǒng)

14、對用戶查詢的了解是非確定的(uncertain)，對前往結(jié)果的猜測也是非確定的 而概率實際為非確定推理提供了堅實的實際根底 概率檢索模型可以計算文檔和查詢相關(guān)的能夠性. 現(xiàn)代信息檢索概率檢索模型 概率檢索模型是經(jīng)過概率的方法將查詢和文檔聯(lián)絡(luò)起來 定義3個隨機變量R、Q、D：相關(guān)度R=0,1，查詢Q=q1,q2,，文檔D=d1,d2,，那么可以經(jīng)過計算條件概率P(R=1|Q=q,D=d)來度量文檔和查詢的相關(guān)度。 概率模型包括一系列模型，如Logistic Regression(回歸)模型及最經(jīng)典的二值獨立概率模型BIM、BM25模型等等(還有貝葉斯網(wǎng)絡(luò)模型)。 1998出現(xiàn)的基于統(tǒng)計言語建模的

15、信息檢索模型本質(zhì)上也是概率模型的一種。27. 現(xiàn)代信息檢索概率排序原理(PRP) 簡單地說：假設(shè)文檔按照與查詢的相關(guān)概率大小前往，那么該前往結(jié)果是一切能夠獲得結(jié)果中效果最好的。 嚴(yán)厲地說：假設(shè)文檔按照與查詢的相關(guān)概率大小前往，而這些相關(guān)概率又可以基于知數(shù)據(jù)進展盡能夠準(zhǔn)確的估計，那么該前往結(jié)果是一切基于知數(shù)據(jù)獲得的能夠的結(jié)果中效果最好的。28. 現(xiàn)代信息檢索幾種概率檢索模型 基于Logistic回歸的檢索模型 經(jīng)典的二值獨立概率模型BIM 經(jīng)典的BM25模型 (BestMatch25) 貝葉斯網(wǎng)絡(luò)模型：本講義不引見，請參考有關(guān)文獻。 基于言語建模的檢索模型：1998年興起，研討界的熱點。下一講引

16、見。29.提綱30上一講及向量空間模型回想根本概率統(tǒng)計知識Logistic回歸模型BIM模型BM25模型. 現(xiàn)代信息檢索回歸(Regression)0iiiyx31 回歸分析：回歸分析是處置變量之間相關(guān)關(guān)系的一種工具，回歸的結(jié)果可以用于預(yù)測或者分類 一元線性回歸：根據(jù)觀測點，擬合出一條直線，使得某種損失 (如離差平方和)最小 多元線性回歸：xy1x( ,)iix y( ,)iix yyabx. 現(xiàn)代信息檢索Logistic 回歸()1( )11xxxeyf xee 32 Logistic回歸是一種非線性回歸 Logistic (也叫Sigmoid)函數(shù)(S型曲線)： Logistic回歸可以轉(zhuǎn)

17、化成線性回歸來實現(xiàn), ln11xyyexyy y1.0 x=0=1. 現(xiàn)代信息檢索Logistic 回歸IR模型0log( ,)1iiiPf Q DP33 根本思想：為了求Q和D相關(guān)的概率P(R=1|Q,D)，經(jīng)過定義多個特征函數(shù)fi(Q,D)，以為P(R=1|Q,D)是這些函數(shù)的組合。 Cooper等人提出一種做法*：定義log(P/(1-P)為多個特征函數(shù)的線性組合。那么P是一個Logistic函數(shù)，即：0(,)11i iifQ DPe*William S. Cooper , Fredric C. Gey , Daniel P. Dabney, Probabilistic retrieva

18、l based on staged logistic regression, Proceedings of ACM SIGIR92, p.198-210, June 21-24, 1992, Copenhagen, Denmark . 現(xiàn)代信息檢索34 特征函數(shù)fi的選擇MXnnNIDFIDFMXDLXDAFMXQLXQAFMXjjjjjttMtMtMtloglog1log1log1615413211. 現(xiàn)代信息檢索Logistic 回歸IR模型(續(xù))0635 求解和運用過程： 經(jīng)過訓(xùn)練集合擬和得到相應(yīng)系數(shù) ，對于新的文檔，代入公式計算得到概率P Learning to Rank中Pointw

19、ise方法中的一種 判別式(discriminate)模型 優(yōu)缺陷： 優(yōu)點：直接引入數(shù)學(xué)工具，方式簡約。 缺陷：特征選擇非常困難，實驗中效果普通。.提綱36上一講及向量空間模型回想根本概率統(tǒng)計知識Logistic回歸模型BIM模型BM25模型. 現(xiàn)代信息檢索二值獨立概率模型BIM( , )(|) ( )(|)( )( )P A BP B A P AP A BP BP B37 二值獨立概率模型(Binary Independence Model，簡稱BIM)：倫敦城市大學(xué)Robertson及劍橋大學(xué)Sparck Jones 1970年代提出，代表系統(tǒng)OKAPI Bayes公式 BIM模型經(jīng)過Ba

20、yes公式對所求條件概率P(R=1|Q,D)展開進展計算。BIM是一種生成式(generative)模型 對于同一Q，P(R=1|Q,D)可以簡記為P(R=1|D). 現(xiàn)代信息檢索BIM模型(續(xù))(1|)(|1) (1)/()loglog(0|)(|0) (0)/()(|1)log(|0)P RDP D RP RP DP RDP D RP RP DP D RP D R38 對每個Q定義排序(Ranking)函數(shù)RSV(Q,D)： 其中，P(D|R=1)、P(D|R=0)分別表示在相關(guān)和不相關(guān)情況下生成文檔D的概率。Ranking函數(shù)顯然是隨著P(R=1|D)的增長而增長。對同一Q是常量，對排序

21、不起作用. 現(xiàn)代信息檢索文檔是怎樣生成的？ 類比： 鋼鐵是怎樣煉成的？ 博士是怎樣讀成的？ . 概率的觀念： 詞項滿足某個總體分布，然后從該總體分布中抽樣，將抽樣出的詞項連在一同，組成文檔 對于P(D|R=1)或者P(D|R=0)，可以以為R=1或0的文檔的詞項滿足某個總體分布，然后抽樣生成D39. 現(xiàn)代信息檢索兩種常用的文檔生成的總體分布 多元貝努利分布(Multi-variate Bernoulli distribution) 詞項詞典大小為M，M個不規(guī)那么硬幣分別對應(yīng)M個詞項，第i個硬幣朝上的概率為pi 假設(shè)M=4(四個詞項分別為 I you can fly)，p1=0.7, p2=0.

22、4, p3=0.1, p4=0.05 那么： P(I can fly fly)=0.7*(1-0.4)*0.1*0.05 多項式分布(Multinomial distribution) 詞項大小為M，某個不規(guī)那么骰子共有M個面，每個面對應(yīng)一個詞項(假設(shè)每次拋擲必有某個面穩(wěn)定朝上或下)，第i個面朝上的概率為pi 假定M=4 (四個詞項分別為 I you can fly)，p1=0.4, p2=0.3, p3=0.2, p4=0.1 那么：P(I can fly fly)=0.4*0.2*0.1*0.140. 現(xiàn)代信息檢索BIM中P(D|R=1)或P(D|R=0)的計算 類比：M次獨立實驗 (多元

23、貝努利模型) 假想詞項空間中有M個詞項，相當(dāng)于有M個不規(guī)那么硬幣，第i個硬幣對應(yīng)詞項 i，正面寫著“出現(xiàn)ti，反面寫著“不出現(xiàn)ti，獨立地拋這M個硬幣，然后記錄下每個硬幣朝上的面對應(yīng)的詞項便組成文檔D。 因此，求P(D|R)就是拋這個M個硬幣得到D的概率。假設(shè)拋不同硬幣之間是獨立的(獨立性假設(shè))，并且不思索ti出現(xiàn)的次數(shù)，只思索ti要么出現(xiàn)要么不出現(xiàn)(二值)。同時，也不思索拋硬幣的次序(詞袋模型) P(D|R=1)和P(D|R=0)相當(dāng)于有兩組硬幣，因此需求求解2M個概率參數(shù)41. 現(xiàn)代信息檢索BIM模型公式的推導(dǎo)1(|1)( |1)( |1)(1), 1, =0iiiiiiitDtDeeii

24、iiitP D RP tRP tRppif tD then eelse e 421(|0)( |0)( |0)(1), 1, =0iiiiiiitDtDeeiiiiitP D RP tRP tRqqif tD then eelse e ijijtDtDtt( |1)( |0)iiiipP tRqP tR將D看成 ，于是 注：P(ti|R=1)表示在相關(guān)情況下，ti出如今文檔中的概率(也就是說某個、或者某幾個P(ti|R=1)可以為1)，留意：不是在相關(guān)文檔集合中出現(xiàn)的概率，因此一切P(ti|R=1)的總和不為1。這個可以和前面拋硬幣的過程對照一下就明白了。. 現(xiàn)代信息檢索一個例子詞項信息檢索教

25、材教程課件R=1時的概率pi0.320.15R=0時的概率qi50.330.1043 查詢?yōu)椋盒畔?檢索 教程 一切詞項的在相關(guān)、不相關(guān)情況下的概率pi、qi分別為 : 文檔D1： 檢索 課件 那么： P(D|R=1)=(1-0.8)*0.9*(1-0.3)*(1-0.32)*0.15 P(D|R=0)= (1-0.3)*0.1*(1-0.35)*(1-0.33)*0.10 P(D|R=1)/P(D|R=0)=4.216. 現(xiàn)代信息檢索BIM模型公式的推導(dǎo)111(1)1(|1)logloglog(|0)(1)1111log(1)loglogloglog111

26、liiiiiiiiiiieeeeiitDDiieetDDiiiitDDiiiiiiiiitDDtDDiiiiiippppP D RP D Rqqqqpppppeeeeqqqqqe /(1)/(1)/(1)/(1)oglogloglog/(1)/(1)/(1)/(1)/(1)log/(1)iiiiiiiiiiiiiitDDtDtQDtQ tDiiiiiiiiiitQDiippppppppqqqqqqqqppqq 44繼續(xù)推導(dǎo)，去掉公式中的只依賴查詢Q的常數(shù)項，得一切出如今文檔D(ei=1)中的詞項的某個屬性值之和。再假定對于不出如今Q中的詞項，有pi=qi，那么得到一切出如今QD中的詞項的屬性值

27、之和ti在D中權(quán)重0或1ti在Q中權(quán)重，只與Q相關(guān)最原始的BIM模型的計算公式，其中最關(guān)鍵是pi、qi的計算！類似于向量內(nèi)積計算假設(shè)對不屬于Q的term, pi=qi， 那么此項為零常數(shù)QDtBIMiiW. 現(xiàn)代信息檢索pi qi參數(shù)的計算ri (35)ni- ri (165)Ri-ri (65)N-Ri-ni+ri (235)45350.351001650.413400iiiiiiirpRnrqNR0.5iiiiiiirpRnrqNR相關(guān) Ri (100) 不相關(guān) N-Ri (400)包含ti ni (200)不包含ti N-ni (300)引入平滑因子其中，N、ni分別是

28、總文檔以及包含ti的文檔數(shù)目。Ri、ri分別是相關(guān)文檔及相關(guān)文檔中包含ti的文檔數(shù)目。括號中列舉的數(shù)值是給出的一個總文檔數(shù)目為500的計算例子。那么：理想情況下，可以將整個文檔集合根據(jù)能否和查詢相關(guān)、能否包含ti分成如下四個子集合，每個集合的大小知。. 現(xiàn)代信息檢索RSJ權(quán)重 Robertson & Sprck Jones權(quán)重(RSJ權(quán)重)46(0.5)(0.5)log(0.5)(0.5)RSJiiiiiiirNRnrWnrRr. 現(xiàn)代信息檢索pi qi參數(shù)的計算(續(xù)) 由于真實情況下，對于每個查詢，無法事先得到相關(guān)文檔集和不相關(guān)文檔集，所以無法運用理想情況下的公式計算，因此必需進展估

29、計 有多種估計方法 初始檢索：第一次檢索之前的估計 基于檢索結(jié)果：根據(jù)上次檢索的結(jié)果進展估計47. 現(xiàn)代信息檢索pi qi參數(shù)的計算(續(xù))48IDF因此，BIM在初始假設(shè)情況下，其檢索公式實踐上相當(dāng)于對一切同時出如今q和d中的詞項的IDF的求和QDtIDFiQDtiiQDtiiQDtiiiiiiiiiiiWnnNnnNqqppNnqp5 .05 .0loglog)1/()1/(log5 .0 初始情況：檢索初始并沒有相關(guān)和不相關(guān)文檔集合，此時可以進展假設(shè)： pi是常數(shù)， qi近似等于term i在一切文檔集合中的分布(假定相關(guān)文檔很少，Ri=ri=0). 現(xiàn)代信息檢索pi qi參數(shù)的計算(續(xù))

30、iiiiiVpVnVqNV49 基于前面的檢索結(jié)果：假定檢索出的結(jié)果集合V(可以把V看成全部的相關(guān)文檔結(jié)合)，其中集合Vi包含term i，那么可以進一步進展計算 防止較小的V和Vi集合，參與常數(shù)或非常數(shù)平滑因子(以下用V和Vi表示同名集合的大小)0.510.51iiiiiVpVnVqNV11iiiiiiinVNpVnnVNqNV. 現(xiàn)代信息檢索BIM模型小結(jié) 小結(jié)BIM計算過程：目的是求排序函數(shù) P(D|R=1)/P(D|R=0) 首先估計或計算每個term分別在相關(guān)文檔和不相關(guān)文檔中的出現(xiàn)概率pi=P(t|R=1)及qi=P(t|R=0) 然后根據(jù)獨立性假設(shè)，將P(D|R=1)/P(D|R=0) 轉(zhuǎn)化為pi和qi的某種組合，將pi和qi代入即可求解。50. 現(xiàn)代信息檢索BIM模型的優(yōu)缺陷 優(yōu)缺陷： 優(yōu)點： BIM模型建立在數(shù)學(xué)根底上，實際性較強 缺陷： 需求估計參數(shù)