lecture12-languagemodel-信息检索导论-王斌-PPT-课件-第12章

IntroductiontoInformationRetrieval现代信息检索中科院研究生院2011年秋季课程《现代信息检索》更新时间：ModernInformationRetrieval授课人：王斌~wangbin*改编自”AnintroductiontoInformationretrieval”网上公开的课件，地址第12讲基于语言建模的IR模型LanguageModelsforIR2011/11/07现代信息检索提纲❶上一讲回顾❷语言模型❸基于统计建模的IR模型❹SLMIR模型讨论现代信息检索提纲❶上一讲回顾❷语言模型❸基于统计建模的IR模型❹SLMIR模型讨论现代信息检索概率检索模型概率检索模型是通过概率的方法将查询和文档联系起来定义3个随机变量R、Q、D：相关度R={0,1}，查询Q={q1,q2,…}，文档D={d1,d2,…}，则可以通过计算条件概率P(R=1|Q=q,D=d)来度量文档和查询的相关度。概率模型包括一系列模型，如LogisticRegression(回归)模型及最经典的二值独立概率模型BIM、BM25模型等等(还有贝叶斯网络模型)。1998出现的基于统计语言建模的信息检索模型本质上也是概率模型的一种。4现代信息检索概率排序原理(PRP)简单地说：如果文档按照与查询的相关概率大小返回，那么该返回结果是所有可能获得结果中效果最好的。严格地说：如果文档按照与查询的相关概率大小返回，而这些相关概率又能够基于已知数据进行尽可能精确的估计，那么该返回结果是所有基于已知数据获得的可能的结果中效果最好的。5现代信息检索几种概率检索模型基于Logistic回归的检索模型经典的二值独立概率模型BIM经典的BM25模型(BestMatch25)6现代信息检索Logistic回归IR模型0log(,)1iiiPfQDP7基本思想：为了求Q和D相关的概率P(R=1|Q,D)，通过定义多个特征函数fi(Q,D)，认为P(R=1|Q,D)是这些函数的组合。Cooper等人提出一种做法*：定义log(P/(1-P))为多个特征函数的线性组合。则P是一个Logistic函数，即：0(,)11iiifQDPe*WilliamS.Cooper,FredricC.Gey,DanielP.Dabney,Probabilisticretrievalbasedonstagedlogisticregression,ProceedingsofACMSIGIR'92,p.198-210,June21-24,1992,Copenhagen,Denmark现代信息检索BIM模型(续)(1|)(|1)(1)/()loglog(0|)(|0)(0)/()(|1)log(|0)PRDPDRPRPDPRDPDRPRPDPDRPDR8对每个Q定义排序(Ranking)函数RSV(Q,D)：其中，P(D|R=1)、P(D|R=0)分别表示在相关和不相关情况下生成D的概率。Ranking函数显然是随着P(R=1|D)的增长而增长。现代信息检索BIM模型(续)1(|1)(|1)(|1)(1),1,=0iiiiiiitDtDeeiiiiitPDRPtRPtRppiftDtheneelsee91(|0)(|0)(|0)(1),1,=0iiiiiiitDtDeeiiiiitPDRPtRPtRqqiftDtheneelseeijijtDtDtt(|1)(|0)iiiipPtRqPtR将D看成，于是注：P(ti|R=1)表示在相关情况下，ti出现在文档中的概率(也就是说某个、或者某几个P(ti|R=1)可以为1)，注意：不是在相关文档集合中出现的概率，因此所有P(ti|R=1)的总和不为1。这个可以和前面抛硬币的过程对照一下就明白了。现代信息检索piqi参数的计算ri(35)ni-ri(165)Ri-ri(65)N-Ri-ni+ri(235)10350.351001650.413400iiiiiiirpRnrqNR0.50.50.50.5iiiiiiirpRnrqNR相关Ri(100)不相关N-Ri(400)包含tini(200)不包含tiN-ni(300)引入平滑因子其中，N、ni分别是总文档以及包含ti的文档数目。Ri、ri分别是相关文档及相关文档中包含ti的文档数目。括号中列举的数值是给出的一个总文档数目为500的计算例子。则：理想情况下，可以将整个文档集合根据是否和查询相关、是否包含ti分成如下四个子集合，每个集合的大小已知。现代信息检索piqi参数的计算(续)由于真实情况下，对于每个查询，无法事先得到相关文档集和不相关文档集，所以无法使用理想情况下的公式计算，因此必须进行估计有多种估计方法初始检索：第一次检索之前的估计基于检索结果：根据上次检索的结果进行估计11现代信息检索piqi参数的计算(续)0.5/(1)loglog/(1)iiiiiiitqdiiipnqNppNnqqn12初始情况：检索初始并没有相关和不相关文档集合，此时可以进行假设：pi是常数，qi近似等于termi在所有文档集合中的分布(假定相关文档很少，Ri=ri=0)IDF因此，BIM在初始假设情况下，其检索公式实际上相当于对所有同时出现在q和d中的term的IDF的求和现代信息检索OkapiBM25:一个非二值模型13现代信息检索本讲内容(统计)语言模型基于统计语言建模的IR模型(基本)查询似然模型一些扩展的模型现代信息检索提纲❶上一讲回顾❷语言模型❸基于统计建模的IR模型❹SLMIR模型讨论现代信息检索统计语言模型(StatisticalLanguageModeling，SLM)121211112(...)()(...|)...()(|...)nnniiiP16SLM广泛使用于语音识别和统计机器翻译领域，利用概率统计理论研究语言。规则方法：词、句、篇章的生成比如满足某些规则，不满足该规则就不应存在。统计方法：任何语言片断都有存在的可能，只是可能性大小不同对于一个文档片段d=w1w2…wn，统计语言模型是指概率P(w1w2…wn)求解，根据Bayes公式，有历史(history)无历史，一元模型最近一个历史，二元模型(Bigram)最近N-1个历史，N元模型(N-gram)现代信息检索类比：打扑克中的出牌策略只根据当前牌出牌，一元模型；根据上一轮牌出牌，二元模型；……现代信息检索不同模型的例子12341213243()()(|)(|)(|)P18一元模型(unigram)：二元模型(bigram)：一阶马尔科夫链三元模型(trigram)：对于n-gram，n越大，则模型越复杂，估计的参数(即估计的概率)也越多。当然，当数据量足够大的情况下，模型阶数越高越对片段概率的计算也越准确。1234121312423()()(|)(|)(|)P12341234()()()()()P现代信息检索课堂思考设词典大小为M，试估计N元模型要估计的参数(概率)空间大小。估计的参数数目为：M+M2+…+MN=(MN+1-M)/(M-1)假定M=1000，N=4，则需要估计约1012=1万亿个参数，参数空间巨大！1912341213243()()(|)(|)(|)P1234121312423()()(|)(|)(|)P12341234()()()()()P现代信息检索SLM的一个应用例子拼音输入法(以下例子中将字看成语言单位)：输入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)的值课堂思考：一元模型存在的问题？20现代信息检索SLM的一个应用例子(续)二元模型(Bigram)：P(中国科学院)=P(中)P(国|中)P(科|国)P(学|科)P(院|学)，等价于一阶马尔科夫链(MarkovChain)三元模型(Trigram)：P(中国科学院)=P(中)P(国|中)P(科|中国)P(学|国科)P(院|科学)根据语料，估计所使用模型的参数，然后在搜索空间中搜索概率最大的语言片段。21以下经允许，借用了丁国栋博士的部分报告现代信息检索SLM的参数估计理论上说，在数据充足的情况下，利用更多的历史(高阶)的模型更准确，但是总计算量也越大数据规模总是有限的，即用于训练模型参数的语料存在稀疏性(DataSparseness，即某参数在训练语料中没有出现)问题。如二元模型中，在训练语料中恰巧没有出现“国科”组合。数据稀疏性导致零概率问题，上述稀疏性情况下，如果直接计算，那么P(中国科学院)=0，但是在训练集上不出现的事件并不代表在新的语料上不出现。SLM的一个重要工作就是进行平滑(Smoothing)：重新分配概率，即使没出现的事件也会赋予一个概率。22现代信息检索23另一个角度看语言模型我们可以把一个有穷状态自动机(finitestateautomaton)看成一个确定性语言模型(deterministiclanguage)上述模型可以生成片段“IwishIwishIwishIwish...”但是不能生成片段“wishIwish”或“IwishI”如果上述自动机是带有概率的，则是概率语言模型(probabilisticLM，也称统计语言模型SLM)现代信息检索24一个概率语言模型的例子单状态概率有穷状态自动机—一元语言模型—状态发射概率分布如右表。其中STOP不是词，而是表示自动机结束的一个标识符。这样，概率P(frogsaidthattoadlikesfrogSTOP)=0.01·0.03·0.04·0.01·0.02·0.01·0.02=0.0000000000048现代信息检索25两个不同的语言模型string=frogsaidthattoadlikesfrogSTOP则P(string|Md1)=0.01·0.03·0.04·0.01·0.02·0.01·0.02=0.0000000000048=4.8·10-12P(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”更相关现代信息检索统计语言建模IR模型(SLMIR)马萨诸塞大学(UniversityofMassachusetts,UMass)大学Ponte、Croft等人于1998年提出。随后又发展了出了一系列基于SLM的模型。代表系统Lemur。查询似然模型：把相关度看成是每篇文档对应的语言下生成该查询的可能性翻译模型：假设查询经过某个噪声信道变形成某篇文章，则由文档还原成该查询的概率(翻译模型)可以视为相关度KL距离模型：查询对应某种语言，每篇文档对应某种