《概率检索模型》ppt课件

1、Introduction to Information Retrieval 现代信息检索现代信息检索中科院研究生院2011年秋季课程现代信息检索 更新时间： Modern Information Retrieval授课人：王斌http:/ introduction to Information retrieval”网上公开的课件，地址 /IR-book/第11讲 概率检索模型Probabilistic Information Retrieval12021/11/07.提纲2上一讲及向量空间模型回想根本概率统计知识Logistic回归模型BIM模型BM

2、25模型.提纲3上一讲及向量空间模型回想根本概率统计知识Logistic回归模型BIM模型BM25模型.现代信息检索 4构造化检索(Structured retrieval) 根本配置： 构造化或非构造化查询+构造化文档结构化检索的应用场景数字图书馆、专利数据库、博客、包含已标注命名实体（如人名、地名）的文本例子 数字图书馆: 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 实体标记文本: give me articles about sightseeing tours of the Vatican and the Coliseum4.现代信息检索 5XML 文档5.现代信息检索 6挑战1: 前往文档的一部分 XML检索中，用户希望前往文档的一部分即 XML元素，而不像非构造化检索那样往往前往整个文档上述情况下，用户能够在查找 场(scene)但是，另一个没有详细指定前往节点的查询Macbeth，应该前往剧本的称号而不是某个子单位 处理方法: 构造化文档检索原理(structured document retrieval

4、 principle)例子如果在莎士比亚全集中查找Macbeths castle，那么到底应该返回场（scene）、幕（act）还是整个剧本呢？6.现代信息检索 7构造化文档检索原理上述原理睬引发这样一种检索战略，即前往包含信息需求的最小单位但是，要在算法上实现这种原理是非常困难的。比如查询： title:Macbeth， 整个剧本的标题Maccbeth以及第一幕第六场的标题Macbeths castle都是包含匹配词项Macbeth的较好的命中结果。然而在这个例子中，剧本的标题这个位于更高层的节点作为答案却更适宜确定查询应对的正确层次是非常困难的。结构化文档检索原理选择最合适的文档部分:系统

5、应该总是检索出回答查询的最明确最具体的文档部分7.挑战2: 如何确定文档的索引单位8 IR索引和排名中的中心概念：文档单位或索引单位在非构造化检索中，适宜的文档单位往往比较明显，如PC上的文档、邮件、Web上的网页等等而在构造化检索中，却有定义索引单位的一系列不同的方法将节点分组，构成多个互不重叠的伪文档pseudodocument )索引最大元素，然后自顶向下(top down)后处置索引叶节点，然后自底向上(bottom up)进展后处置扩展对一切元素建立索引.现代信息检索 挑战3：元素嵌套针对元素嵌套所呵斥的冗余性，普遍的做法是对前往元素进展限制。这些限制战略包括： 这些限制战略包括：忽

6、略一切的小元素忽略用户不会阅读的一切元素类型这需求记录当前XML检索系统的运转日志信息忽略通常被评价者断定为不相关性的元素类型假设有相关性断定的话 只保管系统设计人员或图书馆员认定为有用的检索结果所对应的元素类型在大部分上述方法中，结果集中依然包含嵌套元素。9.现代信息检索 基于词汇化子树表示的向量空间模型目的: 对向量空间中的每一维都同时思索单词及其在XML树中的位置信息做法: 将XML文档映射成词汇化子树BookTitleAuthorBillGatesMicrosoftAuthorBillGatesMicrosoftBillGatesTitleMicrosoftAuthorGatesAut

7、horBillBookTitleMicrosoft. . . Book10.现代信息检索 INEX(Initiative for the Evaluation of XML retrieval)INEX: XML检索研讨中的首要评测平台，它经过协作产生参考文档集、查询集及相关性判别。在每年一度的INEX会议上，研讨人员展现并讨论交流各自的研讨结果。INEX 2002文档集包含大约12000篇来自IEEE期刊的文章。(自2006 年开场，INEX运用英文Wikipedia这个更大的库)文档的相关性断定主要经过人工判别来完成INEX 2002 文档集统计信息文档集统计信息12,107文档数目494

8、 MB规模19952002文章发表年份1,532平均每篇文档中的XML节点个数6.9平均每个节点的深度30CAS主题的数目30CO 主题的数目11. 现代信息检索向量空间模型 文档表示成向量 查询也表示成向量 计算两个向量之间的类似度：余弦类似度、内积类似度等等 在向量表示中的词项权重计算方法主要是tf-idf公式，实践思索tf、idf及文档长度3个要素12.现代信息检索 13tf-idf权重计算的三要素13. 现代信息检索14向量空间模型的优缺陷 优点： 简约直观，可以运用到很多其他领域(文本分类、生物信息学)。 支持部分匹配和近似匹配，结果可以排序 检索效果不错 缺陷： 实际上不够：基于直

9、觉的阅历性公式 标引项之间的独立性假设与实践不符：实践上，term的出现之间是有关系的，不是完全独立的。如：“王励勤 “乒乓球的出现不是独立的。. 现代信息检索本讲内容 概率根底知识 基于概率实际的检索模型 Logistic回归模型 二值独立概率模型 BIM：不思索词项频率和文档长度 思索词项频率和文档长度的BM25模型15.提纲16上一讲及向量空间模型回想根本概率统计知识Logistic回归模型BIM模型BM25模型.现代信息检索 概率 vs. 统计概率概率统计统计necessity概率是统计的实际根底统计是概率的实践运用典型问题： 知某数据总体满足某分布，抽样得到某数据的概率是多少？典型问

10、题：知某抽样数据(或总体分布)，判别总体的分布(或分布参数) 是多少？. 现代信息检索概率统计初步 随机实验与随机事件 概率和条件概率 乘法公式、全概率公式、贝叶斯公式 随机变量 随机变量的分布18. 现代信息检索随机实验和随机事件 随机实验：可在一样条件下反复进展；实验能够结果不止一个，但能确定一切的能够结果；一次实验之前无法确定详细是哪种结果出现。 掷一颗骰子，思索能够出现的点数 随机事件：随机实验中能够出现或能够不出现的情况叫“随机事件 掷一颗骰子，4点朝上19. 现代信息检索概率和条件概率 概率：直观上来看，事件A的概率是指事件A发生的能够性，记为P(A) 掷一颗骰子，出现6点的概率为

11、多少？ 条件概率：知事件A发生的条件下，事件B发生的概率称为A条件下B的条件概率，记作P(B|A) 30颗红球和40颗黑球放在一块，请问第一次抽取为红球的情况下第二次抽取黑球的概率？20. 现代信息检索乘法公式、全概率公式和贝叶斯公式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. 现代信息检索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独立 多事件独立：两两独立、三三独立、四四独立. 现代信息检索随机变量 随机变量：假设随机实验的各种能够的结果都能用一个 变量的取值或范围来表示，那么称这个变量为随机变量，常用X、Y、Z来表示 (离散型随机变量)：掷一颗骰子，能够出现的点数X (能够取值1、2、3、4、5、6) (延续

13、型随机变量)：北京地域的温度(-1545)23.现代信息检索 各种分布关系图二值二值分布分布多值多值多项多项分布分布n元贝努元贝努利分布利分布二项二项分布分布分布n重贝努利实验k次朝上的概率硬币朝上或朝下X=0 或者1骰子某个面朝上X=0,1,2,3n 重实验，X1=x1, X2=x2,n次不同硬币n重贝努利实验. 现代信息检索贝努利 瑞士数学家家族，产生过11位数学家 雅可比贝努利(Jacob Bernoulli) : 1654-1705 积分“integral这一术语即由他首创 贝努利实验、贝努利分布25. 现代信息检索26概率检索模型 检索系统中，给定查询，计算每个文档的相关度 检索系统

14、对用户查询的了解是非确定的(uncertain)，对前往结果的猜测也是非确定的 而概率实际为非确定推理提供了坚实的实际根底 概率检索模型可以计算文档和查询相关的能够性. 现代信息检索概率检索模型 概率检索模型是经过概率的方法将查询和文档联络起来 定义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出现的基于统计言语建模的

15、信息检索模型本质上也是概率模型的一种。27. 现代信息检索概率排序原理(PRP) 简单地说：假设文档按照与查询的相关概率大小前往，那么该前往结果是一切能够获得结果中效果最好的。 严厉地说：假设文档按照与查询的相关概率大小前往，而这些相关概率又可以基于知数据进展尽能够准确的估计，那么该前往结果是一切基于知数据获得的能够的结果中效果最好的。28. 现代信息检索几种概率检索模型 基于Logistic回归的检索模型 经典的二值独立概率模型BIM 经典的BM25模型 (BestMatch25) 贝叶斯网络模型：本讲义不引见，请参考有关文献。 基于言语建模的检索模型：1998年兴起，研讨界的热点。下一讲引

16、见。29.提纲30上一讲及向量空间模型回想根本概率统计知识Logistic回归模型BIM模型BM25模型. 现代信息检索回归(Regression)0iiiyx31 回归分析：回归分析是处置变量之间相关关系的一种工具，回归的结果可以用于预测或者分类 一元线性回归：根据观测点，拟合出一条直线，使得某种损失 (如离差平方和)最小 多元线性回归：xy1x( ,)iix y( ,)iix yyabx. 现代信息检索Logistic 回归()1( )11xxxeyf xee 32 Logistic回归是一种非线性回归 Logistic (也叫Sigmoid)函数(S型曲线)： Logistic回归可以转

17、化成线性回归来实现, ln11xyyexyy y1.0 x=0=1. 现代信息检索Logistic 回归IR模型0log( ,)1iiiPf Q DP33 根本思想：为了求Q和D相关的概率P(R=1|Q,D)，经过定义多个特征函数fi(Q,D)，以为P(R=1|Q,D)是这些函数的组合。 Cooper等人提出一种做法*：定义log(P/(1-P)为多个特征函数的线性组合。那么P是一个Logistic函数，即：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 . 现代信息检索34 特征函数fi的选择MXnnNIDFIDFMXDLXDAFMXQLXQAFMXjjjjjttMtMtMtloglog1log1log1615413211. 现代信息检索Logistic 回归IR模型(续)0635 求解和运用过程： 经过训练集合拟和得到相应系数 ，对于新的文档，代入公式计算得到概率P Learning to Rank中Pointw

19、ise方法中的一种 判别式(discriminate)模型 优缺陷： 优点：直接引入数学工具，方式简约。 缺陷：特征选择非常困难，实验中效果普通。.提纲36上一讲及向量空间模型回想根本概率统计知识Logistic回归模型BIM模型BM25模型. 现代信息检索二值独立概率模型BIM( , )(|) ( )(|)( )( )P A BP B A P AP A BP BP B37 二值独立概率模型(Binary Independence Model，简称BIM)：伦敦城市大学Robertson及剑桥大学Sparck Jones 1970年代提出，代表系统OKAPI Bayes公式 BIM模型经过Ba

20、yes公式对所求条件概率P(R=1|Q,D)展开进展计算。BIM是一种生成式(generative)模型 对于同一Q，P(R=1|Q,D)可以简记为P(R=1|D). 现代信息检索BIM模型(续)(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)函数RSV(Q,D)： 其中，P(D|R=1)、P(D|R=0)分别表示在相关和不相关情况下生成文档D的概率。Ranking函数显然是随着P(R=1|D)的增长而增长。对同一Q是常量，对排序

21、不起作用. 现代信息检索文档是怎样生成的？ 类比： 钢铁是怎样炼成的？ 博士是怎样读成的？ . 概率的观念： 词项满足某个总体分布，然后从该总体分布中抽样，将抽样出的词项连在一同，组成文档 对于P(D|R=1)或者P(D|R=0)，可以以为R=1或0的文档的词项满足某个总体分布，然后抽样生成D39. 现代信息检索两种常用的文档生成的总体分布 多元贝努利分布(Multi-variate Bernoulli distribution) 词项词典大小为M，M个不规那么硬币分别对应M个词项，第i个硬币朝上的概率为pi 假设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，某个不规那么骰子共有M个面，每个面对应一个词项(假设每次抛掷必有某个面稳定朝上或下)，第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. 现代信息检索BIM中P(D|R=1)或P(D|R=0)的计算 类比：M次独立实验 (多元

23、贝努利模型) 假想词项空间中有M个词项，相当于有M个不规那么硬币，第i个硬币对应词项 i，正面写着“出现ti，反面写着“不出现ti，独立地抛这M个硬币，然后记录下每个硬币朝上的面对应的词项便组成文档D。 因此，求P(D|R)就是抛这个M个硬币得到D的概率。假设抛不同硬币之间是独立的(独立性假设)，并且不思索ti出现的次数，只思索ti要么出现要么不出现(二值)。同时，也不思索抛硬币的次序(词袋模型) P(D|R=1)和P(D|R=0)相当于有两组硬币，因此需求求解2M个概率参数41. 现代信息检索BIM模型公式的推导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)表示在相关情况下，ti出如今文档中的概率(也就是说某个、或者某几个P(ti|R=1)可以为1)，留意：不是在相关文档集合中出现的概率，因此一切P(ti|R=1)的总和不为1。这个可以和前面抛硬币的过程对照一下就明白了。. 现代信息检索一个例子词项信息检索教

25、材教程课件R=1时的概率pi0.320.15R=0时的概率qi50.330.1043 查询为：信息 检索 教程 一切词项的在相关、不相关情况下的概率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. 现代信息检索BIM模型公式的推导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继续推导，去掉公式中的只依赖查询Q的常数项，得一切出如今文档D(ei=1)中的词项的某个属性值之和。再假定对于不出如今Q中的词项，有pi=qi，那么得到一切出如今QD中的词项的属性值

27、之和ti在D中权重0或1ti在Q中权重，只与Q相关最原始的BIM模型的计算公式，其中最关键是pi、qi的计算！类似于向量内积计算假设对不属于Q的term, pi=qi， 那么此项为零常数QDtBIMiiW. 现代信息检索pi qi参数的计算ri (35)ni- ri (165)Ri-ri (65)N-Ri-ni+ri (235)45350.351001650.413400iiiiiiirpRnrqNR0.5iiiiiiirpRnrqNR相关 Ri (100) 不相关 N-Ri (400)包含ti ni (200)不包含ti N-ni (300)引入平滑因子其中，N、ni分别是

28、总文档以及包含ti的文档数目。Ri、ri分别是相关文档及相关文档中包含ti的文档数目。括号中列举的数值是给出的一个总文档数目为500的计算例子。那么：理想情况下，可以将整个文档集合根据能否和查询相关、能否包含ti分成如下四个子集合，每个集合的大小知。. 现代信息检索RSJ权重 Robertson & Sprck Jones权重(RSJ权重)46(0.5)(0.5)log(0.5)(0.5)RSJiiiiiiirNRnrWnrRr. 现代信息检索pi qi参数的计算(续) 由于真实情况下，对于每个查询，无法事先得到相关文档集和不相关文档集，所以无法运用理想情况下的公式计算，因此必需进展估

29、计 有多种估计方法 初始检索：第一次检索之前的估计 基于检索结果：根据上次检索的结果进展估计47. 现代信息检索pi qi参数的计算(续)48IDF因此，BIM在初始假设情况下，其检索公式实践上相当于对一切同时出如今q和d中的词项的IDF的求和QDtIDFiQDtiiQDtiiQDtiiiiiiiiiiiWnnNnnNqqppNnqp5 .05 .0loglog)1/()1/(log5 .0 初始情况：检索初始并没有相关和不相关文档集合，此时可以进展假设： pi是常数， qi近似等于term i在一切文档集合中的分布(假定相关文档很少，Ri=ri=0). 现代信息检索pi qi参数的计算(续)

30、iiiiiVpVnVqNV49 基于前面的检索结果：假定检索出的结果集合V(可以把V看成全部的相关文档结合)，其中集合Vi包含term i，那么可以进一步进展计算 防止较小的V和Vi集合，参与常数或非常数平滑因子(以下用V和Vi表示同名集合的大小)0.510.51iiiiiVpVnVqNV11iiiiiiinVNpVnnVNqNV. 现代信息检索BIM模型小结 小结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代入即可求解。50. 现代信息检索BIM模型的优缺陷 优缺陷： 优点： BIM模型建立在数学根底上，实际性较强 缺陷： 需求估计参数