49lecture11-probmodel-信息检索导论-王斌-PPT-课件-第11章

IntroductiontoInformationRetrieval现代信息检索中科院研究生院2011年秋季课程《现代信息检索》更新时间：ModernInformationRetrieval授课人：王斌~wangbin*改编自”AnintroductiontoInformationretrieval”网上公开的课件，地址第11讲概率检索模型ProbabilisticInformationRetrieval12011/11/07提纲2❶上一讲及向量空间模型回顾❷基本概率统计知识❸Logistic回归模型❹BIM模型❺BM25模型提纲3❶上一讲及向量空间模型回顾❷基本概率统计知识❸Logistic回归模型❹BIM模型❺BM25模型现代信息检索4结构化检索(Structuredretrieval)基本配置：结构化或非结构化查询+结构化文档结构化检索的应用场景数字图书馆、专利数据库、博客、包含已标注命名实体（如人名、地名）的文本例子数字图书馆:givemeafull-lengtharticleonfastfouriertransforms专利:givemepatenswhoseclaimsmentionRSApublickeyencryptionandthatciteUSpatent4,405,829实体标记文本:givemearticlesaboutsightseeingtoursoftheVaticanandtheColiseum4现代信息检索5XML文档5现代信息检索6挑战1:返回文档的一部分XML检索中，用户希望返回文档的一部分（即XML元素），而不像非结构化检索那样往往返回整个文档上述情况下，用户可能在查找场(scene)但是，另一个没有具体指定返回节点的查询Macbeth，应该返回剧本的名称而不是某个子单位解决办法:结构化文档检索原理(structureddocumentretrievalprinciple)例子如果在《莎士比亚全集》中查找Macbeth’scastle，那么到底应该返回场（scene）、幕（act）还是整个剧本呢？6现代信息检索7结构化文档检索原理上述原理会引发这样一种检索策略，即返回包含信息需求的最小单位但是，要在算法上实现这种原理是非常困难的。比如查询：title:Macbeth，整个剧本的标题Maccbeth以及第一幕第六场的标题Macbeth’scastle都是包含匹配词项Macbeth的较好的命中结果。然而在这个例子中，剧本的标题这个位于更高层的节点作为答案却更合适确定查询应答的正确层次是非常困难的。结构化文档检索原理选择最合适的文档部分:系统应该总是检索出回答查询的最明确最具体的文档部分7挑战2:如何确定文档的索引单位8IR索引和排名中的核心概念：文档单位或索引单位在非结构化检索中，合适的文档单位往往比较明显，如PC上的文档、邮件、Web上的网页等等而在结构化检索中，却有定义索引单位的一系列不同的方法❶将节点分组，形成多个互不重叠的伪文档（pseudodocument)❷索引最大元素，然后自顶向下(topdown)后处理❸索引叶节点，然后自底向上(bottomup)进行后处理扩展❹对所有元素建立索引现代信息检索挑战3：元素嵌套针对元素嵌套所造成的冗余性，普遍的做法是对返回元素进行限制。这些限制策略包括：这些限制策略包括：忽略所有的小元素忽略用户不会浏览的所有元素类型（这需要记录当前XML检索系统的运行日志信息忽略通常被评估者判定为不相关性的元素类型（如果有相关性判定的话）只保留系统设计人员或图书馆员认定为有用的检索结果所对应的元素类型在大部分上述方法中，结果集中仍然包含嵌套元素。9现代信息检索基于词汇化子树表示的向量空间模型目标:对向量空间中的每一维都同时考虑单词及其在XML树中的位置信息做法:将XML文档映射成词汇化子树BookTitleAuthorBillGatesMicrosoftAuthorBillGatesMicrosoftBillGatesTitleMicrosoftAuthorGatesAuthorBillBookTitleMicrosoft...Book10现代信息检索INEX(InitiativefortheEvaluationofXMLretrieval)INEX:XML检索研究中的首要评测平台，它通过协作产生参考文档集、查询集及相关性判断。在每年一度的INEX会议上，研究人员展示并讨论交流各自的研究结果。INEX2002文档集包含大概12000篇来自IEEE期刊的文章。(自2006年开始，INEX使用英文Wikipedia这个更大的库)文档的相关性判定主要通过人工判断来完成INEX2002文档集统计信息12,107文档数目494MB规模1995—2002文章发表年份1,532平均每篇文档中的XML节点个数6.9平均每个节点的深度30CAS主题的数目30CO主题的数目11现代信息检索向量空间模型文档表示成向量查询也表示成向量计算两个向量之间的相似度：余弦相似度、内积相似度等等在向量表示中的词项权重计算方法主要是tf-idf公式，实际考虑tf、idf及文档长度3个因素12现代信息检索13tf-idf权重计算的三要素13现代信息检索14向量空间模型的优缺点优点：简洁直观，可以应用到很多其他领域(文本分类、生物信息学)。支持部分匹配和近似匹配，结果可以排序检索效果不错缺点：理论上不够：基于直觉的经验性公式标引项之间的独立性假设与实际不符：实际上，term的出现之间是有关系的，不是完全独立的。如：“王励勤”“乒乓球”的出现不是独立的。现代信息检索本讲内容概率基础知识基于概率理论的检索模型Logistic回归模型二值独立概率模型BIM：不考虑词项频率和文档长度考虑词项频率和文档长度的BM25模型15提纲16❶上一讲及向量空间模型回顾❷基本概率统计知识❸Logistic回归模型❹BIM模型❺BM25模型现代信息检索概率vs.统计概率统计necessity概率是统计的理论基础统计是概率的实际应用典型问题：已知某数据总体满足某分布，抽样得到某数据的概率是多少？典型问题：已知某抽样数据(或总体分布)，判断总体的分布(或分布参数)是多少？现代信息检索概率统计初步随机试验与随机事件概率和条件概率乘法公式、全概率公式、贝叶斯公式随机变量随机变量的分布18现代信息检索随机试验和随机事件随机试验：可在相同条件下重复进行；试验可能结果不止一个，但能确定所有的可能结果；一次试验之前无法确定具体是哪种结果出现。掷一颗骰子，考虑可能出现的点数随机事件：随机试验中可能出现或可能不出现的情况叫“随机事件”掷一颗骰子，4点朝上19现代信息检索概率和条件概率概率：直观上来看，事件A的概率是指事件A发生的可能性，记为P(A)掷一颗骰子，出现6点的概率为多少？条件概率：已知事件A发生的条件下，事件B发生的概率称为A条件下B的条件概率，记作P(B|A)30颗红球和40颗黑球放在一块，请问第一次抽取为红球的情况下第二次抽取黑球的概率？20现代信息检索乘法公式、全概率公式和贝叶斯公式1()()(|)niiiPBPAPBA＝21乘法公式：P(AB)＝P(A)P(B|A)P(A1A2…An)＝P(A1)P(A2|A1)...P(An|A1…An－1)全概率公式：A1A2…An是整个样本空间的一个划分贝叶斯公式：A1A2…An是整个样本空间的一个划分1()(|)(|),(1,...,)()(|)jjjniiiPAPBAPABjnPAPBA现代信息检索22事件的独立性两事件独立：事件A、B，若P(AB)=P(A)P(B)，则称A、B独立三事件独立：事件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独立多事件独立：两两独立、三三独立、四四独立….现代信息检索随机变量随机变量：若随机试验的各种可能的结果都能用一个变量的取值（或范围）来表示，则称这个变量为随机变量，常用X、Y、Z来表示(离散型随机变量)：掷一颗骰子，可能出现的点数X(可能取值1、2、3、4、5、6)(连续型随机变量)：北京地区的温度(-15~45)23现代信息检索各种分布关系图二值分布多值多项分布n元贝努利分布二项分布n重贝努利试验k次朝上的概率硬币朝上或朝下X=0或者1骰子某个面朝上X=0,1,2,3n重试验，X1=x1,X2=x2,…n次不同硬币n重贝努利试验现代信息检索贝努利瑞士数学家家族，产生过11位数学家雅可比贝努利(JacobBernoulli):1654-1705积分“integral”这一术语即由他首创贝努利试验、贝努利分布25现代信息检索26概率检索模型检索系统中，给定查询，计算每个文档的相关度检索系统对用户查询的理解是非确定的(uncertain)，对返回结果的猜测也是非确定的而概率理论为非确定推理提供了坚实的理论基础概率检索模型可以计算文档和查询相关的可能性现代信息检索概率检索模型概率检索模型是通过概率的方法将查询和文档联系起来定义3个随机变量R、Q、D：相关度R={0,1}，查询Q={q1,q2,…}，文档D={d1,d2,…}，则可以通过计算条件概率P(R=1|Q=q,D=d)来度量文档和查询的相关度。概率模型包括一系列模型，如LogisticRegression(回归)模型及最经典的二值独立概率模型BIM、BM25模型等等(还有贝叶斯网络模型)。1998出现的基于统计语言建模的信息检索模型本质上也是概率模型的一种。27现代信息检索概率排序原理(PRP)简单地说：如果文档按照与查询的相关概率大小返回，那么该返回结果是所有可能获得结果中效果最好的。严格地说：如果文档按照与查询的相关概率大小返回，而这些相关概率又能够基于已知数据进行尽可能精确的估计，那么该返回结果是所有基于已知数据获得的可能的结果中效果最好的。28现代信息检索几种概率检索模型基于Logistic回归的检索模型经典的二值独立概率模型BIM经典的BM25模型(BestMatch25)贝叶斯网络模型：本讲义不介绍，请参考有关文献。基于语言建模的检索模型：1998年兴起，研究界的热点。下一讲介绍。29提纲30❶上一讲及向量空间模型回顾❷基本概率统计知识❸Logistic回归模型❹BIM模型❺BM25模型现代信息检索回归(Regression)0iiiyx31回归分析：回归分析是处理变量之间相关关系的一种工具，回归的结果可以用于预测或者分类一元线性回归：根据观测点，拟合出一条直线，使得某种损失(如离差平方和)最小多元线性回归：xy1x(,)iixy^(,)iixy^yabx现代信息检索Logistic回归()1()11xxxeyfxee32Logistic回归是一种非线性回归Logistic(也叫Sigmoid)函数(S型曲线)：Logistic回归可以转化成线性回归来实现,ln11xyyexyyy1.0xα=0β=1现代信息检索Logistic回归IR模型0log(,)1iiiPfQDP33基本思想：为了求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,Probabilisticretrievalba