《概率检索模型》PPT课件.ppt

《《概率检索模型》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《概率检索模型》PPT课件.ppt（58页珍藏版）》请在三一办公上搜索。

1、1,第11讲 概率检索模型Probabilistic Information Retrieval,2011/11/07,2,提纲,上一讲及向量空间模型回顾基本概率统计知识Logistic回归模型BIM模型BM25模型,3,提纲,上一讲及向量空间模型回顾基本概率统计知识Logistic回归模型BIM模型BM25模型,4,4,结构化检索(Structured retrieval),基本配置：结构化或非结构化查询+结构化文档,5,5,XML 文档,6,6,挑战1:返回文档的一部分,XML检索中，用户希望返回文档的一部分（即 XML元素），而不像非结构化检索那样往往返回整个文档上述情况下，用户可能在查

2、找 场(scene)但是，另一个没有具体指定返回节点的查询Macbeth，应该返回剧本的名称而不是某个子单位 解决办法:结构化文档检索原理(structured document retrieval principle),7,7,结构化文档检索原理,上述原理会引发这样一种检索策略，即返回包含信息需求的最小单位但是，要在算法上实现这种原理是非常困难的。比如查询：title:Macbeth，整个剧本的标题Maccbeth以及第一幕第六场的标题Macbeths castle都是包含匹配词项Macbeth的较好的命中结果。然而在这个例子中，剧本的标题这个位于更高层的节点作为答案却更合适确定查询应答的正

3、确层次是非常困难的。,8,挑战2:如何确定文档的索引单位,IR索引和排名中的核心概念：文档单位或索引单位在非结构化检索中，合适的文档单位往往比较明显，如PC上的文档、邮件、Web上的网页等等而在结构化检索中，却有定义索引单位的一系列不同的方法将节点分组，形成多个互不重叠的伪文档（pseudodocument)索引最大元素，然后自顶向下(top down)后处理索引叶节点，然后自底向上(bottom up)进行后处理扩展对所有元素建立索引,9,挑战3：元素嵌套,针对元素嵌套所造成的冗余性，普遍的做法是对返回元素进行限制。这些限制策略包括：这些限制策略包括：忽略所有的小元素忽略用户不会浏览的所有元

4、素类型（这需要记录当前XML检索系统的运行日志信息忽略通常被评估者判定为不相关性的元素类型（如果有相关性判定的话）只保留系统设计人员或图书馆员认定为有用的检索结果所对应的元素类型在大部分上述方法中，结果集中仍然包含嵌套元素。,10,基于词汇化子树表示的向量空间模型,目标:对向量空间中的每一维都同时考虑单词及其在XML树中的位置信息做法:将XML文档映射成词汇化子树,Book,Title,Author,Bill,Gates,Microsoft,Author,Bill,Gates,Microsoft,Bill,Gates,Title,Microsoft,Author,Gates,Author,Bi

5、ll,Book,Title,Microsoft,.,Book,11,INEX(Initiative for the Evaluation of XML retrieval),INEX:XML检索研究中的首要评测平台，它通过协作产生参考文档集、查询集及相关性判断。在每年一度的INEX会议上，研究人员展示并讨论交流各自的研究结果。INEX 2002文档集包含大概12000篇来自IEEE期刊的文章。(自2006 年开始，INEX使用英文Wikipedia这个更大的库)文档的相关性判定主要通过人工判断来完成,12,向量空间模型,文档表示成向量查询也表示成向量计算两个向量之间的相似度：余弦相似度、内积相

6、似度等等在向量表示中的词项权重计算方法主要是tf-idf公式，实际考虑tf、idf及文档长度3个因素,13,13,tf-idf权重计算的三要素,14,向量空间模型的优缺点,优点：简洁直观，可以应用到很多其他领域(文本分类、生物信息学)。支持部分匹配和近似匹配，结果可以排序检索效果不错缺点：理论上不够：基于直觉的经验性公式标引项之间的独立性假设与实际不符：实际上，term的出现之间是有关系的，不是完全独立的。如：“王励勤”“乒乓球”的出现不是独立的。,15,本讲内容,概率基础知识基于概率理论的检索模型Logistic回归模型二值独立概率模型 BIM：不考虑词项频率和文档长度考虑词项频率和文档长度

7、的BM25模型,16,提纲,上一讲及向量空间模型回顾基本概率统计知识Logistic回归模型BIM模型BM25模型,概率 vs.统计,概率,统计,necessity,概率是统计的理论基础,统计是概率的实际应用,典型问题：已知某数据总体满足某分布，抽样得到某数据的概率是多少？,典型问题：已知某抽样数据(或总体分布)，判断总体的分布(或分布参数)是多少？,18,概率统计初步,随机试验与随机事件概率和条件概率乘法公式、全概率公式、贝叶斯公式随机变量随机变量的分布,19,随机试验和随机事件,随机试验：可在相同条件下重复进行；试验可能结果不止一个，但能确定所有的可能结果；一次试验之前无法确定具体是哪种结

8、果出现。掷一颗骰子，考虑可能出现的点数随机事件：随机试验中可能出现或可能不出现的情况叫“随机事件”掷一颗骰子，4点朝上,20,概率和条件概率,概率：直观上来看，事件A的概率是指事件A发生的可能性，记为P(A)掷一颗骰子，出现6点的概率为多少？条件概率：已知事件A发生的条件下，事件B发生的概率称为A条件下B的条件概率，记作P(B|A)30颗红球和40颗黑球放在一块，请问第一次抽取为红球的情况下第二次抽取黑球的概率？,21,乘法公式、全概率公式和贝叶斯公式,乘法公式：P(AB)P(A)P(B|A)P(A1A2An)P(A1)P(A2|A1).P(An|A1An1)全概率公式：A1A2An是整个样本

9、空间的一个划分贝叶斯公式：A1A2An是整个样本空间的一个划分,22,事件的独立性,两事件独立：事件A、B，若P(AB)=P(A)P(B)，则称A、B独立三事件独立：事件A B C，若满足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独立多事件独立：两两独立、三三独立、四四独立.,23,随机变量,随机变量：若随机试验的各种可能的结果都能用一个 变量的取值（或范围）来表示，则称这个变量为随机变量，常用X、Y、Z来表示(离散型随机变量)：掷一颗骰子，可能出现的点数X(可能取值1、2、3、4、5、6)(

10、连续型随机变量)：北京地区的温度(-1545),各种分布关系图,n重贝努利试验k次朝上的概率,硬币朝上或朝下X=0 或者1,骰子某个面朝上X=0,1,2,3,n 重试验，X1=x1,X2=x2,n次不同硬币,n重贝努利试验,25,贝努利,瑞士数学家家族，产生过11位数学家雅可比贝努利(Jacob Bernoulli):1654-1705积分“integral”这一术语即由他首创贝努利试验、贝努利分布,26,概率检索模型,检索系统中，给定查询，计算每个文档的相关度检索系统对用户查询的理解是非确定的(uncertain)，对返回结果的猜测也是非确定的而概率理论为非确定推理提供了坚实的理论基础概率检

11、索模型可以计算文档和查询相关的可能性,27,概率检索模型,概率检索模型是通过概率的方法将查询和文档联系起来定义3个随机变量R、Q、D：相关度R=0,1，查询Q=q1,q2,，文档D=d1,d2,，则可以通过计算条件概率P(R=1|Q=q,D=d)来度量文档和查询的相关度。概率模型包括一系列模型，如Logistic Regression(回归)模型及最经典的二值独立概率模型BIM、BM25模型等等(还有贝叶斯网络模型)。1998出现的基于统计语言建模的信息检索模型本质上也是概率模型的一种。,28,概率排序原理(PRP),简单地说：如果文档按照与查询的相关概率大小返回，那么该返回结果是所有可能获得

12、结果中效果最好的。严格地说：如果文档按照与查询的相关概率大小返回，而这些相关概率又能够基于已知数据进行尽可能精确的估计，那么该返回结果是所有基于已知数据获得的可能的结果中效果最好的。,29,几种概率检索模型,基于Logistic回归的检索模型经典的二值独立概率模型BIM经典的BM25模型(BestMatch25)贝叶斯网络模型：本讲义不介绍，请参考有关文献。基于语言建模的检索模型：1998年兴起，研究界的热点。下一讲介绍。,30,提纲,上一讲及向量空间模型回顾基本概率统计知识Logistic回归模型BIM模型BM25模型,31,回归(Regression),回归分析：回归分析是处理变量之间相关

13、关系的一种工具，回归的结果可以用于预测或者分类一元线性回归：根据观测点，拟合出一条直线，使得某种损失(如离差平方和)最小多元线性回归：,32,Logistic 回归,Logistic回归是一种非线性回归Logistic(也叫Sigmoid)函数(S型曲线)：Logistic回归可以转化成线性回归来实现,y,1.0,x,=0=1,33,Logistic 回归IR模型,基本思想：为了求Q和D相关的概率P(R=1|Q,D)，通过定义多个特征函数fi(Q,D)，认为P(R=1|Q,D)是这些函数的组合。Cooper等人提出一种做法*：定义log(P/(1-P)为多个特征函数的线性组合。则P是一个Log

14、istic函数，即：,*William S.Cooper,Fredric C.Gey,Daniel P.Dabney,Probabilistic retrieval based on staged logistic regression,Proceedings of ACM SIGIR92,p.198-210,June 21-24,1992,Copenhagen,Denmark,34,特征函数fi的选择,35,Logistic 回归IR模型(续),求解和使用过程：通过训练集合拟和得到相应系数，对于新的文档，代入公式计算得到概率PLearning to Rank中Pointwise方法中的一种判

15、别式(discriminate)模型优缺点：优点：直接引入数学工具，形式简洁。缺点：特征选择非常困难，实验中效果一般。,36,提纲,上一讲及向量空间模型回顾基本概率统计知识Logistic回归模型BIM模型BM25模型,37,二值独立概率模型BIM,二值独立概率模型(Binary Independence Model，简称BIM)：伦敦城市大学Robertson及剑桥大学Sparck Jones 1970年代提出，代表系统OKAPIBayes公式BIM模型通过Bayes公式对所求条件概率P(R=1|Q,D)展开进行计算。BIM是一种生成式(generative)模型对于同一Q，P(R=1|Q,

16、D)可以简记为P(R=1|D),38,BIM模型(续),对每个Q定义排序(Ranking)函数RSV(Q,D)：其中，P(D|R=1)、P(D|R=0)分别表示在相关和不相关情况下生成文档D的概率。Ranking函数显然是随着P(R=1|D)的增长而增长。,对同一Q是常量，对排序不起作用,39,文档是怎么生成的？,类比：钢铁是怎么炼成的？博士是怎么读成的？.概率的观点：词项满足某个总体分布，然后从该总体分布中抽样，将抽样出的词项连在一起，组成文档对于P(D|R=1)或者P(D|R=0)，可以认为R=1或0的文档的词项满足某个总体分布，然后抽样生成D,40,两种常用的文档生成的总体分布,多元贝努

17、利分布(Multi-variate Bernoulli distribution)词项词典大小为M，M个不规则硬币分别对应M个词项，第i个硬币朝上的概率为pi假设M=4(四个词项分别为 I you can fly)，p1=0.7,p2=0.4,p3=0.1,p4=0.05则：P(I can fly fly)=0.7*(1-0.4)*0.1*0.05多项式分布(Multinomial distribution)词项大小为M，某个不规则骰子共有M个面，每个面对应一个词项(假设每次抛掷必有某个面稳定朝上或下)，第i个面朝上的概率为pi假定M=4(四个词项分别为 I you can fly)，p1=0

18、.4,p2=0.3,p3=0.2,p4=0.1则：P(I can fly fly)=0.4*0.2*0.1*0.1,41,BIM中P(D|R=1)或P(D|R=0)的计算,类比：M次独立试验(多元贝努利模型)假想词项空间中有M个词项，相当于有M个不规则硬币，第i个硬币对应词项 i，正面写着“出现ti”，反面写着“不出现ti”，独立地抛这M个硬币，然后记录下每个硬币朝上的面对应的词项便组成文档D。因此，求P(D|R)就是抛这个M个硬币得到D的概率。假设抛不同硬币之间是独立的(独立性假设)，并且不考虑ti出现的次数，只考虑ti要么出现要么不出现(二值)。同时，也不考虑抛硬币的次序(词袋模型)P(D

19、|R=1)和P(D|R=0)相当于有两组硬币，因此需要求解2M个概率参数,42,BIM模型公式的推导,将D看成，于是,注：P(ti|R=1)表示在相关情况下，ti出现在文档中的概率(也就是说某个、或者某几个P(ti|R=1)可以为1)，注意：不是在相关文档集合中出现的概率，因此所有P(ti|R=1)的总和不为1。这个可以和前面抛硬币的过程对照一下就明白了。,43,一个例子,查询为：信息 检索 教程 所有词项的在相关、不相关情况下的概率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)

20、*0.1*(1-0.35)*(1-0.33)*0.10 P(D|R=1)/P(D|R=0)=4.216,44,BIM模型公式的推导,继续推导，去掉公式中的只依赖查询Q的常数项，得所有出现在文档D(ei=1)中的词项的某个属性值之和。再假定对于不出现在Q中的词项，有pi=qi，则得到所有出现在QD中的词项的属性值之和,ti在D中权重0或1,ti在Q中权重，只与Q相关,最原始的BIM模型的计算公式，其中最关键是pi、qi的计算！,类似于向量内积计算,假设对不属于Q的term,pi=qi，则此项为零,常数,45,pi qi参数的计算,相关 Ri(100)不相关 N-Ri(400),包含ti ni(2

21、00)不包含ti N-ni(300),引入平滑因子,其中，N、ni分别是总文档以及包含ti的文档数目。Ri、ri分别是相关文档及相关文档中包含ti的文档数目。括号中列举的数值是给出的一个总文档数目为500的计算例子。则：,理想情况下，可以将整个文档集合根据是否和查询相关、是否包含ti分成如下四个子集合，每个集合的大小已知。,46,RSJ权重,Robertson&Sprck Jones权重(RSJ权重),47,pi qi参数的计算(续),由于真实情况下，对于每个查询，无法事先得到相关文档集和不相关文档集，所以无法使用理想情况下的公式计算，因此必须进行估计有多种估计方法初始检索：第一次检索之前的估

22、计基于检索结果：根据上次检索的结果进行估计,48,pi qi参数的计算(续),IDF,因此，BIM在初始假设情况下，其检索公式实际上相当于对所有同时出现在q和d中的词项的IDF的求和,初始情况：检索初始并没有相关和不相关文档集合，此时可以进行假设：pi是常数，qi近似等于term i在所有文档集合中的分布(假定相关文档很少，Ri=ri=0),49,pi qi参数的计算(续),基于前面的检索结果：假定检索出的结果集合V(可以把V看成全部的相关文档结合)，其中集合Vi包含term i，则可以进一步进行计算避免较小的V和Vi集合，加入常数或非常数平滑因子(以下用V和Vi表示同名集合的大小),50,B

23、IM模型小结,小结BIM计算过程：目标是求排序函数 P(D|R=1)/P(D|R=0)首先估计或计算每个term分别在相关文档和不相关文档中的出现概率pi=P(t|R=1)及qi=P(t|R=0)然后根据独立性假设，将P(D|R=1)/P(D|R=0)转化为pi和qi的某种组合，将pi和qi代入即可求解。,51,BIM模型的优缺点,优缺点：优点：BIM模型建立在数学基础上，理论性较强缺点：需要估计参数原始的BIM没有考虑TF、文档长度因素BIM中同样存在词项独立性假设,52,提纲,上一讲及向量空间模型回顾基本概率统计知识Logistic回归模型BIM模型BM25模型,53,Okapi BM25

24、:一个非二值模型,BIM是最简单的文档评分方式：考虑词项在文档中的tf权重，有：tf ti,D:词项ti在文档D中的词项频率LD(Lave):文档D的长度(整个文档集的平均长度)k1:用于控制文档中词项频率比重的调节参数b:用于控制文档长度比重的调节参数,54,Okapi BM25:一个非二值模型,如果查询比较长，则加入查询的tftf ti,Q:词项ti在Q中的词项频率k3:用于控制查询中词项频率比重的调节参数没有查询长度的归一化(由于查询对于所有文档都是固定的)理想情况下，上述参数都必须在开发测试集上调到最优。一般情况下，实验表明，k1 和 k3 应该设在 1.2到2之间，b 设成 0.75

25、。,55,另一个BM25写法,dfi是词项ti的df,IDF,TFdoc,长度归一化,56,BM25公式的推导,参考S.E Roberson and S.Walker,Some simple effective approximations to the 2-Poisson model for probabilistic weighted retrieval,SIGIR94S.E Roberston,S.Walker,S.Jones,Okapi at TREC-3,in Proceedings of TREC-3非常有意思，建议看看。,57,参考资料,现代信息检索第11章http:/ifnlp.org/ir,58,课后练习,习题11-1习题11-3,