信息檢索11-語言模型

第12講基于語言建模的IR模型LanguageModelsforIR2017/10/172021/6/271提綱

上一講回顧

語言模型

基于統(tǒng)計建模的IR模型

SLMIR模型討論2021/6/272提綱

上一講回顧

語言模型

基于統(tǒng)計建模的IR模型

SLMIR模型討論2021/6/273概率檢索模型概率檢索模型是通過概率的方法將查詢和文檔聯(lián)系起來定義3個隨機變量R、Q、D：相關(guān)度R={0,1}，查詢Q={q1,q2,…}，文檔D={d1,d2,…}，則可以通過計算條件概率P(R=1|Q=q,D=d)來度量文檔和查詢的相關(guān)度。概率模型包括一系列模型，如LogisticRegression(回歸)模型及最經(jīng)典的二值獨立概率模型BIM、BM25模型等等(還有貝葉斯網(wǎng)絡(luò)模型)。1998出現(xiàn)的基于統(tǒng)計語言建模的信息檢索模型本質(zhì)上也是概率模型的一種。2021/6/274概率排序原理(PRP)簡單地說：如果文檔按照與查詢的相關(guān)概率大小返回，那么該返回結(jié)果是所有可能獲得結(jié)果中效果最好的。嚴格地說：如果文檔按照與查詢的相關(guān)概率大小返回，而這些相關(guān)概率又能夠基于已知數(shù)據(jù)進行盡可能精確的估計，那么該返回結(jié)果是所有基于已知數(shù)據(jù)獲得的可能的結(jié)果中效果最好的。2021/6/275幾種概率檢索模型基于Logistic回歸的檢索模型經(jīng)典的二值獨立概率模型BIM經(jīng)典的BM25模型(BestMatch25)2021/6/276Logistic回歸IR模型基本思想：為了求Q和D相關(guān)的概率P(R=1|Q,D)，通過定義多個特征函數(shù)fi(Q,D)，認為P(R=1|Q,D)是這些函數(shù)的組合。Cooper等人提出一種做法*：定義log(P/(1-P))為多個特征函數(shù)的線性組合。則P是一個Logistic函數(shù)，即：*WilliamS.Cooper,FredricC.Gey,DanielP.Dabney,Probabilisticretrievalbasedonstagedlogisticregression,ProceedingsofACMSIGIR'92,p.198-210,June21-24,1992,Copenhagen,Denmark2021/6/277BIM模型(續(xù))對每個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)的增長而增長。2021/6/278兩種常用的文檔生成的總體分布多元貝努利分布(Multi-variateBernoullidistribution)詞項詞典大小為M，M個不規(guī)則硬幣分別對應(yīng)M個詞項，第i個硬幣朝上的概率為pi假設(shè)M=4(四個詞項分別為Iyoucanfly)，p1=0.7,p2=0.4,p3=0.1,p4=0.05則：P(Icanflyfly)=0.7*(1-0.4)*0.1*0.05多元貝努利分布不考慮出現(xiàn)位置多元貝努利分布考慮出現(xiàn)和不出現(xiàn)2021/6/279兩種常用的文檔生成的總體分布(續(xù))多項式分布(Multinomialdistribution)詞項大小為M，某個不規(guī)則骰子共有M個面，每個面對應(yīng)一個詞項(假設(shè)每次拋擲必有某個面穩(wěn)定朝上或下)，第i個面朝上的概率為pi假定M=4(四個詞項分別為Iyoucanfly)，p1=0.4,p2=0.3,p3=0.2,p4=0.1則：P(Icanflyfly)=P(X1=1,X2=0,X3=1,X4=2)=C*0.4*0.2*0.1*0.1其中C==12多項式分布考慮詞項的多次出現(xiàn)多項式分布不考慮詞項的不出現(xiàn)多項式分布同樣不考慮詞項的出現(xiàn)位置和次序2021/6/2710BIM模型(續(xù))將D看成，于是注：P(ti|R=1)表示在相關(guān)情況下，ti出現(xiàn)在文檔中的概率(也就是說某個、或者某幾個P(ti|R=1)可以為1)，注意：不是在相關(guān)文檔集合中出現(xiàn)的概率，因此所有P(ti|R=1)的總和不為1。這個可以和前面拋硬幣的過程對照一下就明白了。2021/6/2711piqi參數(shù)的計算ri(35)ni-ri(165)Ri-ri(65)N-Ri-ni+ri(235)相關(guān)Ri(100)不相關(guān)N-Ri(400)包含tini(200)不包含tiN-ni(300)引入平滑因子其中，N、ni分別是總文檔以及包含ti的文檔數(shù)目。Ri、ri分別是相關(guān)文檔及相關(guān)文檔中包含ti的文檔數(shù)目。括號中列舉的數(shù)值是給出的一個總文檔數(shù)目為500的計算例子。則：理想情況下，可以將整個文檔集合根據(jù)是否和查詢相關(guān)、是否包含ti分成如下四個子集合，每個集合的大小已知。2021/6/2712piqi參數(shù)的計算(續(xù))由于真實情況下，對于每個查詢，無法事先得到相關(guān)文檔集和不相關(guān)文檔集，所以無法使用理想情況下的公式計算，因此必須進行估計有多種估計方法初始檢索：第一次檢索之前的估計基于檢索結(jié)果：根據(jù)上次檢索的結(jié)果進行估計2021/6/2713piqi參數(shù)的計算(續(xù))初始情況：檢索初始并沒有相關(guān)和不相關(guān)文檔集合，此時可以進行假設(shè)：pi是常數(shù)，qi近似等于termi在所有文檔集合中的分布(假定相關(guān)文檔很少，Ri=ri=0)IDF因此，BIM在初始假設(shè)情況下，其檢索公式實際上相當于對所有同時出現(xiàn)在q和d中的term的IDF的求和2021/6/2714OkapiBM25:一個非二值模型2021/6/2715本講內(nèi)容(統(tǒng)計)語言模型基于統(tǒng)計語言建模的IR模型(基本)查詢似然模型一些擴展的模型2021/6/2716提綱

上一講回顧

語言模型

基于統(tǒng)計建模的IR模型

SLMIR模型討論2021/6/2717統(tǒng)計語言模型(StatisticalLanguageModeling，SLM)SLM廣泛使用于語音識別和統(tǒng)計機器翻譯領(lǐng)域，利用概率統(tǒng)計理論研究語言。規(guī)則方法：詞、句、篇章的生成比如滿足某些規(guī)則，不滿足該規(guī)則就不應(yīng)存在。統(tǒng)計方法：任何語言片斷都有存在的可能，只是可能性大小不同對于一個文檔片段d=w1w2…wn，統(tǒng)計語言模型是指概率P(w1w2…wn)求解，根據(jù)Bayes公式，有歷史(history)無歷史，一元模型最近一個歷史，二元模型(Bigram)最近N-1個歷史，N元模型(N-gram)2021/6/2718類比：打撲克中的出牌策略只根據(jù)當前牌出牌，一元模型；根據(jù)上一輪牌出牌，二元模型；……2021/6/2719不同模型的例子一元模型(unigram)：二元模型(bigram)：一階馬爾科夫鏈三元模型(trigram)：對于n-gram，n越大，則模型越復雜，估計的參數(shù)(即估計的概率)也越多。當然，當數(shù)據(jù)量足夠大的情況下，模型階數(shù)越高越對片段概率的計算也越準確。2021/6/2720課堂思考設(shè)詞典大小為M

，試估計N元模型要估計的參數(shù)(概率)空間大小。估計的參數(shù)數(shù)目為：M+M2+…+MN=(MN+1-M)/(M-1)假定M=1000，N=4，則需要估計約1012=1萬億個參數(shù)，參數(shù)空間巨大！2021/6/2721SLM的一個應(yīng)用例子拼音輸入法(以下例子中將字看成語言單位)：輸入zhongguokexueyuan，到底是：種過科雪園？重果可薛原？還是中國科學院？……一種利用SLM的解決思路：計算P(種過科雪園)P(重果可薛原)P(中國科學院)，看誰大！(為簡單起見，這里計算沒有考慮拼音，實際上是計算P(種過科雪園|zhongguokexueyuan))一元模型(Unigram)*：P(種過科雪園)=P(種)P(過)P(科)P(雪)P(園)P(重果可薛原)=P(重)P(果)P(可)P(薛)P(原)P(中國科學院)=P(中)P(國)P(科)P(學)P(院)訓練：在訓練語料庫中估計以上各P(X)的值課堂思考：一元模型存在的問題？2021/6/2722SLM的一個應(yīng)用例子(續(xù))二元模型(Bigram)：P(中國科學院)=P(中)P(國|中)P(科|國)P(學|科)P(院|學)，等價于一階馬爾科夫鏈(MarkovChain)三元模型(Trigram)：P(中國科學院)=P(中)P(國|中)P(科|中國)P(學|國科)P(院|科學)根據(jù)語料，估計所使用模型的參數(shù)，然后在搜索空間中搜索概率最大的語言片段。以下經(jīng)允許，借用了丁國棟博士的部分報告2021/6/2723SLM的參數(shù)估計理論上說，在數(shù)據(jù)充足的情況下，利用更多的歷史(高階)的模型更準確，但是總計算量也越大數(shù)據(jù)規(guī)?？偸怯邢薜模从糜谟柧毮Ｐ蛥?shù)的語料存在稀疏性(DataSparseness，即某參數(shù)在訓練語料中沒有出現(xiàn))問題。如二元模型中，在訓練語料中恰巧沒有出現(xiàn)“國科”組合。2021/6/2724數(shù)據(jù)稀疏性數(shù)據(jù)稀疏性導致零概率問題，上述稀疏性情況下，如果直接計算，那么P(中國科學院)=0，但是在訓練集上不出現(xiàn)的事件并不代表在新的語料上不出現(xiàn)。SLM的一個重要工作就是進行平滑(Smoothing)：重新分配概率，即使沒出現(xiàn)的事件也會賦予一個概率。2021/6/272526另一個角度看語言模型

我們可以把一個有窮狀態(tài)自動機(finitestateautomaton)看成一個確定性語言模型(deterministiclanguage)

上述模型可以生成片段“I

wishIwishIwishIwish...”

但是不能生成片段“wishIwish”或“IwishI”

如果上述自動機是帶有概率的，則是概率語言模型(probabilisticLM，也稱統(tǒng)計語言模型SLM)2021/6/272627一個概率語言模型的例子

單狀態(tài)概率有窮狀態(tài)自動機—一元語言模型—狀態(tài)發(fā)射概率分布如右表。其中STOP不是詞，而是表示自動機結(jié)束的一個標識符。這樣，概率

P(frogsaidthattoadlikesfrogSTOP)=0.01·0.03·0.04·0.01·0.02·0.01·0.02 =0.00000000000482021/6/272728兩個不同的語言模型

string=frogsaidthattoadlikesfrogSTOP

則

P(string|Md1

)=0.01·0.03·0.04·0.01·0.02·0.01·0.02=0.0000000000048=4.8·10-12 P(string|Md2

)=0.01·0.03·0.05·0.02·0.02·0.01·0.02=0.0000000000120=12·10-12P(string|Md1

)<

P(string|Md2

)

因此,相對于d1，文檔

d2

與字符串“frogsaidthattoadlikesfrogSTOP”更相關(guān)

2021/6/2728統(tǒng)計語言建模IR模型(SLMIR)馬薩諸塞大學(UniversityofMassachusetts,UMass)大學Ponte、Croft等人于1998年提出。隨后又發(fā)展了出了一系列基于SLM的模型。代表系統(tǒng)Lemur。查詢似然模型：把相關(guān)度看成是每篇文檔對應(yīng)的語言下生成該查詢的可能性翻譯模型：假設(shè)查詢經(jīng)過某個噪聲信道變形成某篇文章，則由文檔還原成該查詢的概率(翻譯模型)可以視為相關(guān)度KL距離模型：查詢對應(yīng)某種語言，每篇文檔對應(yīng)某種語言，查詢語言和文檔語言的KL距離作為相關(guān)度度量本講義主要介紹查詢似然模型2021/6/2729從一個問題開始課堂思考題：設(shè)有N個作者，每人都有一篇文章，對于不在上述N篇文章中的一篇新文檔Q，請問最有可能是哪個作者寫的？一個解決思路：根據(jù)每個作者寫的文章，總結(jié)出每個作者的寫作風格，然后再根據(jù)寫作風格來判斷Q與誰的風格最近。2021/6/2730和檢索的類比新文章Q作者1的文章作者2的文章作者N的文章...查詢Q文檔D文檔模型MD2021/6/2731總體分布&抽樣文檔的模型(風格)實際上是某種總體分布文檔和查詢都是該總體分布下的一個抽樣樣本實例根據(jù)文檔，估計文檔的模型，即求出該總體分布(一般假設(shè)某種總體分布，然后求出其參數(shù))然后計算該總體分布下抽樣出查詢的概率2021/6/2732查詢似然模型(QueryLikelihoodModel)模型推導：文檔D的先驗分布P(D)假定為均勻分布，則這一項可以去掉。P(D)也可以采用某個與查詢無關(guān)的量，如PageRank。QLM中不考慮這一項。2021/6/2733查詢似然模型QLMQLM計算公式于是檢索問題轉(zhuǎn)化為估計文檔D的一元語言模型MD，也即求所有詞項

w的概率P(w|MD)2021/6/2734QLM概念理解QLM中P(Q|D)本質(zhì)上是P(Q|MD)，不能把P(Q|D)稱為文檔D生成查詢Q的概率文檔D和Q都是某個總體分布的樣本(實例)，樣本(實例)是不會產(chǎn)生樣本(實例)的樣本是不會再生成其他東西的，樣本只能用來推斷總體的某些信息，比如總體的某些未知參數(shù)(通過一篇文章來推斷作者的風格)同樣，不能把P(w|MD)或P(w|D)理解為“w在文檔D中的概率”2021/6/2735QLM求解步驟第一步：根據(jù)文檔D(樣本)，估計文檔模型MD(總體)，在一元模型下，即計算所有詞項

w的概率P(w|MD)第二步：計算在模型MD下生成查詢Q的似然(即概率)第三步：按照得分對所有文檔排序2021/6/2736MD的估計問題：已知樣本D，求其模型MD的參數(shù)P(w|MD)。對于該參數(shù)估計問題，可以采用最大似然估計(MaximumLikelihoodEstimation，MLE)。MLE：使得觀察樣本出現(xiàn)概率(似然)最大的估計。一射擊世界冠軍和一菜鳥打靶，其中一人放一槍得到10環(huán)，請問是誰打的？顯然世界冠軍打的可能性大，也就是說這是使得10環(huán)這個事件出現(xiàn)概率最大的估計。2021/6/2737MD的MLE估計設(shè)詞項詞典的大小為L，則模型MD的參數(shù)可以記為：MLE估計：關(guān)鍵是如何求，也就是說假設(shè)這些參數(shù)已知的情況下，如何求上述概率。2021/6/2738總體分布MD的假設(shè)兩種文本生成模型：多元貝努利模型(概率模型BIM中使用)：D是拋L個(L是詞項詞典的大小)不同的硬幣生成的，每個硬幣對應(yīng)一個詞項，統(tǒng)計所有向上的硬幣對應(yīng)的詞項便生成文本D。多元貝努利模型中的參數(shù)是每個硬幣朝上的概率，共有Ｌ個。多項式模型：D是拋1個L面的骰子拋|D|次生成的，將每次朝上的那面對應(yīng)的詞項集合起來便生成文本D。QLM在1998年提出時采用的是多元貝努利模型，后來才有人用多項式模型并發(fā)現(xiàn)多項式模型通常優(yōu)于貝努利模型。所以后來介紹QLM時大都用多項式模型。2021/6/2739文本生成的多項式模型有一個L個面的不規(guī)則骰子，在第i個面上寫著wi,，文檔D=d1d2…dn可以認為是拋n次骰子得到的檢索過程就是根據(jù)觀察樣本D的估計Q的生成概率，即在已知拋n次的結(jié)果為文檔D的條件下，拋m次的結(jié)果為查詢Q的概率P(Q|MD)=？D=(c(w1,D),c(w2,D),…,c(wL,D))，c(wi,D)是文檔D中wi的出現(xiàn)次數(shù)D=我喜歡基于統(tǒng)計語言模型的信息檢索模型D=(<我,1>,<喜歡,1>,<基于,1>,<統(tǒng)計,1>,<語言,1>,<模型,2>,<的,1>,<信息,1>,<檢索,1>)2021/6/2740多項隨機試驗多項(Multinomial)隨機試驗是二項隨機試驗(貝努利試驗)的擴展，一篇文檔D可以看成多項隨機試驗的結(jié)果多項隨機試驗由n次相互獨立的子試驗組成每個子試驗含有L個互斥且完備的可能結(jié)果w1,w2,…,wL。如果L=2則是n重貝努利試驗，對應(yīng)二項分布B(n,p):P(X=k)=每個子試驗中wi發(fā)生的概率不變，記為2021/6/2741多項隨機試驗(續(xù))設(shè)隨機變量X1,X2,…,XL用于記錄n次子試驗中w1,w2,…,wL的發(fā)生次數(shù)，實際記錄值為x1,x2,…,xL，x1+x2+…+xL=n，如果某個wi不出現(xiàn)，則對應(yīng)的xi=0則該多項隨機試驗中w1,w2,…,wL發(fā)生次數(shù)的聯(lián)合分布是一個多項式分布：2021/6/2742MD的參數(shù)求解求解條件極值問題，采用拉格朗日法求解，得到拉格朗日函數(shù)：對每個θi求偏導，令其為0，解得：2021/6/2743一個MLE估計的例子D=(<我,1>,<喜歡,1>,<基于,1>,<統(tǒng)計,1>,<語言,1>,<模型,2>,<的,1>,<信息,1>,<檢索,1>)采用MLE估計有：

P(我|MD)=P(喜歡|MD)=P(基于|MD)=P(統(tǒng)計|MD)=P(語言|MD)=P(的|MD)=P(信息|MD)=P(檢索|MD)=0.1P(模型|MD)=0.2

其他詞項的概率為02021/6/2744MLE估計的零概率問題對于任意不屬于D的詞項，其概率的MLE估計值為0(數(shù)據(jù)的稀疏性)。然而，樣本D中不出現(xiàn)的詞，并不代表在新文本中不出現(xiàn)。類比：作者寫的一篇文章里面不用某個詞，并不代表以后不用這個詞2021/6/2745MLE估計零概率的一個例子一個不規(guī)則的骰子，分別用1-6之間的6個數(shù)字代表每個面。假設(shè)連續(xù)拋10次后，觀測到的結(jié)果序列為2132461232(一篇文檔)。問：拋3次的結(jié)果序列為325(一個查詢)的概率是多大？2021/6/2746例子(續(xù))其實就是求：在已知拋10次的觀測結(jié)果為2132461232的條件下，拋3次的觀測結(jié)果為325的概率P(325|2132461232).用pi表示第i個面朝上的概率，則pi是一個常數(shù)若已知pi(1<=i<=6)，則顯然拋3次的觀測結(jié)果為325的概率為p3p2p5但是每個pi未知，已知的只是拋10次的觀測結(jié)果2132461232。需要由觀測結(jié)果2132461232去估計各個pi（1<=i<=6）。2021/6/2747例子中的MLE估計拋骰子的例子中：P(325|2132461232)＝？估計pi

,i=1,2,..,6使用最大似然估計，根據(jù)樣本2132461232估計pi

p1=2/10,p2=4/10,p3=2/10,p4=1/10,p5=0/10,p6=1/10顯然，5沒有出現(xiàn)在樣本中，不能說明該骰子第5面永遠不會朝上。更嚴重的是，P(325|2132461232)＝p3p2p5=0!因此，上述的估計結(jié)果需要調(diào)整，使所有pi>0。思想：從p1,p2,p3,p4的估計值中扣出一點點給p5最簡單的方法：Add-One

p1=3/16,p2=5/16,p3=3/16,p4=2/16,p5=1/16,p6=2/16從上述例子總結(jié)出以下幾點:

(1)因樣本的數(shù)據(jù)稀疏性，最大似然估計(MLE)導致零概率問題

(2)必須設(shè)法調(diào)整MLE使得所有事件的概率都大于0平滑(smoothing)2021/6/2748數(shù)據(jù)平滑的一般形式在IR中，一般取p(w|C)等于w出現(xiàn)的次數(shù)除以所有詞出現(xiàn)的次數(shù)。Discounted(折扣后的)MaximumLikelihoodReferenceLanguageModelCollectionLanguageModel歸一化系數(shù)2021/6/2749幾種QLM中常用的平滑方法Jelinek-Mercer(JM)，0≤λ≤1，文檔模型和文檔集模型的混合課堂提問，對于w∈D，折扣后的PDML(w|D)是不是一定小于PML(w|D)？DirichletPriors(Dir)，μ≥0，DIR和JM可以互相轉(zhuǎn)化AbsoluteDiscounting(Abs)，0≤δ≤1，|D|u表示D中不相同的詞個數(shù)(u=unique)2021/6/2750QLM的求解過程圖示w1w2w3…wLP11P12P13…P1LP21P22P23…P2L……………PN1PN2PN3…PNLD1D2DN…√√√√√√先計算PML，然后采用平滑公式計算PMLPDML

2021/6/2751文檔排名函數(shù)的轉(zhuǎn)換

將代入最終排名函數(shù)：

不影響排名查詢中w的總次數(shù)TFDF長度2021/6/2752QLM模型小結(jié)檢索問題一元模型估計MLE估計平滑技術(shù)多項式分布假設(shè)2021/6/2753基本SLMIR模型的擴展查詢似然類：文檔建模，計算查詢的似然，例子--基本QLM模型、翻譯模型等文檔似然類：查詢建模，計算文檔的似然，例子--BIM模型、相關(guān)性模型(Relevance模型)等模型比較類：文檔建模、查詢建模，計算兩個模型的距離，KL距離模型2021/6/2754其它SLMIR模型翻譯模型(TranslationModel)KL距離模型(KLDivergenceModel)2021/6/2755香農(nóng)(Shannon)信道源信息發(fā)送器(編碼器)目標信息接收器(解碼器)噪聲信道P(X)P(Y|X)XYX’P(X|Y)=?當X是文本時,p(X)就是一個語言模型一些例子:

語音識別: X=詞序列 Y=語音信號 機器翻譯(中->英): X=英文句子 Y=中文句子

OCR: X=糾錯后的詞 Y=錯誤的詞語 文檔摘要: X=摘要 Y=文檔

信息檢索: X=文檔 Y=查詢2021/6/2756基于翻譯模型的IR模型基本的QLM模型不能解決詞語失配(wordmismatch)問題，即查詢中的用詞和文檔中的用詞不一