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

信息檢索與Web搜索

第12講概率檢索模型ProbabilisticInformationRetrieval授課人：高曙明

*改編自“現(xiàn)代信息檢索”網(wǎng)上公開(kāi)課件（/~wangbin）*改編自“現(xiàn)代信息檢索”網(wǎng)上公開(kāi)課件（/~wangbin）隨機(jī)試驗(yàn)和隨機(jī)事件隨機(jī)試驗(yàn)：可在相同條件下重復(fù)進(jìn)行；試驗(yàn)可能結(jié)果不止一個(gè)，但能確定所有的可能結(jié)果；一次試驗(yàn)之前無(wú)法確定具體是哪種結(jié)果出現(xiàn)擲一顆骰子，考慮可能出現(xiàn)的點(diǎn)數(shù)隨機(jī)事件：隨機(jī)試驗(yàn)中可能出現(xiàn)或可能不出現(xiàn)的情況叫“隨機(jī)事件”擲一顆骰子，4點(diǎn)朝上2概率和條件概率概率：直觀上來(lái)看，事件A的概率是指事件A發(fā)生的可能性，記為P(A)擲一顆骰子，出現(xiàn)6點(diǎn)的概率為多少？條件概率：已知事件A發(fā)生的條件下，事件B發(fā)生的概率稱為A條件下B的條件概率，記作P(B|A)30顆紅球和40顆黑球放在一塊，請(qǐng)問(wèn)第一次抽取為紅球的情況下第二次抽取黑球的概率？3相關(guān)概率公式4乘法公式：P(AB)＝P(A)P(B|A)全概率公式：貝葉斯公式：優(yōu)勢(shì)率：事件的獨(dú)立性兩事件獨(dú)立：事件A、B，若P(AB)=P(A)P(B)，則稱A、B獨(dú)立三事件獨(dú)立：事件ABC，若滿足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獨(dú)立多事件獨(dú)立：兩兩獨(dú)立、三三獨(dú)立、四四獨(dú)立…5隨機(jī)變量隨機(jī)變量：若隨機(jī)試驗(yàn)的各種可能的結(jié)果都能表示為一個(gè)變量的取值（或范圍），則稱這個(gè)變量為隨機(jī)變量，常用X、Y、Z來(lái)表示(離散型隨機(jī)變量)：擲一顆骰子，可能出現(xiàn)的點(diǎn)數(shù)X(可能取值1、2、3、4、5、6)(連續(xù)型隨機(jī)變量)：北京地區(qū)的溫度(-15~45)6概率檢索模型為什么適合在IR中使用概率論？檢索系統(tǒng)中，給定查詢，計(jì)算每個(gè)文檔的相關(guān)度檢索系統(tǒng)對(duì)用戶查詢的理解是非確定的(uncertain)，對(duì)返回結(jié)果的確定也是非確定的而概率理論為非確定推理提供了堅(jiān)實(shí)的理論基礎(chǔ)可以基于概率計(jì)算文檔和查詢相關(guān)的可能性大小7概率檢索模型概率檢索模型：其核心是通過(guò)概率的方法確定查詢與文檔之間的關(guān)聯(lián)度定義3個(gè)隨機(jī)變量R、Q、D：相關(guān)度R={0,1}，查詢Q={q1,q2,…}，文檔D={d1,d2,…}，則可以通過(guò)計(jì)算條件概率P(R=1|Q=q,D=d)來(lái)度量文檔和查詢的相關(guān)度概率模型包括一系列模型：最經(jīng)典的二值獨(dú)立概率模型BIM、BM25模型等等1998出現(xiàn)的基于統(tǒng)計(jì)語(yǔ)言建模的信息檢索模型本質(zhì)上也是概率模型的一種8概率排序原理(PRP)簡(jiǎn)單地說(shuō)：如果文檔按照與查詢的相關(guān)概率大小返回，那么該返回結(jié)果是所有可能獲得結(jié)果中效果最好的嚴(yán)格地說(shuō)：如果文檔按照與查詢的相關(guān)概率大小返回，而這些相關(guān)概率又能夠基于已知數(shù)據(jù)進(jìn)行盡可能精確的估計(jì)，那么該返回結(jié)果是所有基于已知數(shù)據(jù)獲得的可能的結(jié)果中效果最好的9二值獨(dú)立概率模型BIM10二值獨(dú)立概率模型(BinaryIndependenceModel）文檔和查詢都表示為詞項(xiàng)出現(xiàn)與否的布爾向量，d表示為：

=(x1,…,xm),xi=0或xi=1獨(dú)立性：假設(shè)詞項(xiàng)在文檔中的出現(xiàn)是相互獨(dú)立的用P(R|,)對(duì)概率P(R|d,q)建模BIM模型通過(guò)Bayes公式對(duì)所求條件概率P(R|,)展開(kāi)進(jìn)行計(jì)算11公式推導(dǎo)

貝葉斯定理

貝葉斯定理排序函數(shù)推導(dǎo)給定查詢q，按來(lái)排序不需要直接計(jì)算概率值故，可采用文檔相關(guān)性的優(yōu)勢(shì)率來(lái)排序它是相關(guān)性概率的單調(diào)遞增函數(shù)可以忽略，簡(jiǎn)化了計(jì)算12排序函數(shù)推導(dǎo)（續(xù)）在獨(dú)立性假設(shè)下，我們有：由于xt為布爾變量，所以有：13排序函數(shù)推導(dǎo)（續(xù)）令：則：假定當(dāng)qt=0時(shí)，pt=ut進(jìn)一步有：14documentrelevant(R=1)nonrelevant(R=0)Termpresentxt=1Termabsentxt=0ptut1?pt1?ut排序函數(shù)推導(dǎo)（續(xù)）排序中唯一需要估計(jì)的量是：

，稱RSV定義：Ct是查詢?cè)~項(xiàng)的優(yōu)勢(shì)率比率的對(duì)數(shù)值15理論上的概率估計(jì)方法給定一詞項(xiàng)t，相關(guān)數(shù)據(jù)列表為：N為總文檔數(shù)目，dft是包含t的文檔數(shù)目假定上述數(shù)據(jù)已知，則有：

pt=s/S,ut=(dft-s)/(N-S）16實(shí)際中的概率估計(jì)方法假設(shè)給定一查詢q，其相關(guān)文檔只占全部文檔的極小部分，則S、s可忽略，ut=dft/N,于是有：pt的估計(jì)方法如下：如果已知某些相關(guān)文檔，則以其為基礎(chǔ)估計(jì)pt假設(shè)pt是一個(gè)常數(shù)，比如0.5,因?yàn)橹庇^上Pt會(huì)隨dft的增長(zhǎng)而增長(zhǎng)17基于概率的相關(guān)反饋基本思想：通過(guò)利用用戶反饋信息不斷提高pt的精確性來(lái)提高檢索效果基本過(guò)程給出pt和ut的初始估計(jì)利用當(dāng)前的pt

、ut確定相關(guān)文檔集返回給用戶用戶交互選擇相關(guān)文檔利用已知的相關(guān)文檔和不相關(guān)文檔對(duì)pt、ut進(jìn)行重新估計(jì)重復(fù)第2-4步，直到用戶滿意為止1819pt

、ut的重新估計(jì)：設(shè)檢索出的結(jié)果集合為V(可以把V看成全部的相關(guān)文檔結(jié)合)，其中集合Vt包含詞項(xiàng)t，則可以如下進(jìn)一步估算pt

、ut：基于概率的相關(guān)反饋BIM模型存在問(wèn)題分析BIM概率模型的思想很好，理論基礎(chǔ)好，但性能并不理想原因:其建立在若干不太合理的假設(shè)之上文檔、查詢及相關(guān)性的布爾表示詞項(xiàng)之間具有獨(dú)立性查詢中不出現(xiàn)的詞項(xiàng)不會(huì)影響最后的結(jié)果不同文檔的相關(guān)性之間是互相獨(dú)立的20詞項(xiàng)獨(dú)立性假設(shè)去除該假設(shè)不合實(shí)際，例如：HongKong之間存在很強(qiáng)的相關(guān)性{New,York,England,City,Stock,Exchange,University}之間存在復(fù)雜的依賴關(guān)系詞項(xiàng)之間的樹型依賴21OkapiBM25:一個(gè)非二值模型基本思想：在BIM模型中增加對(duì)詞項(xiàng)頻率和文檔長(zhǎng)度的考慮，以提高檢索效果考慮詞項(xiàng)在文檔中的tf權(quán)重，有：tftd:詞項(xiàng)t在文檔d中的詞項(xiàng)頻率Ld(Lave):文檔d的長(zhǎng)度(整個(gè)文檔集的平均長(zhǎng)度)k1:用于控制文檔中詞項(xiàng)頻率比重的調(diào)節(jié)參數(shù)b:用于控制文檔長(zhǎng)度比重的調(diào)節(jié)參數(shù)22OkapiBM25:一個(gè)非二值模型如果查詢比較長(zhǎng)，則加入查詢的tftftq

:詞項(xiàng)t在q中的詞項(xiàng)頻率k3:用于控制查詢中詞項(xiàng)頻率比重的調(diào)節(jié)參數(shù)沒(méi)有查詢長(zhǎng)度的歸一化理想情況下，上述參數(shù)都必須在開(kāi)發(fā)測(cè)試集上調(diào)到最優(yōu)。一般情況下，實(shí)驗(yàn)表明k1

和

k3

應(yīng)該設(shè)在1.2到2之間，

b

設(shè)成0.7523OkapiBM25:一個(gè)非二值模型如果存在相關(guān)性判斷結(jié)果，則有：24TFdocOkapiBM25:一個(gè)非二值模型被廣泛使用，獲得成功詳細(xì)內(nèi)容請(qǐng)參考：S.ERobersonandS.Walker,

Somesimpleeffectiveapproximationstothe2-Poissonmode