《信息检索理论模型》PPT课件.ppt

2019/6/10,1,第2章 信息检索理论模型,2019/6/10,2,信息检索过程,信息检索过程实际上涉及到三个重要的处理： 文档集的逻辑表示 查询的表示 相似匹配及其排序 对上述因素和检索过程建模（抽象描述），产生各种不同的信息检索模型,2019/6/10,3,信息检索模型分类,2019/6/10,4,本章主要内容,2.1 布尔检索模型 2.2 向量空间模型 2.3 概率检索模型 2.4 信息检索逻辑模型,2019/6/10,5,2.1 布尔检索模型,布尔检索模型的理论基础是布尔逻辑和集合理论,2019/6/10,6,2.1 布尔检索模型,布尔逻辑主要内容:命题逻辑与谓词逻辑 布尔逻辑是数理逻辑的基础部分 利用符号来表示逻辑中的各种概念 建立了一系列的运算法则，利用代数的方法研究逻辑问题,2019/6/10,7,布尔运算,布尔逻辑运算符: “与（AND）”、“或(OR)”、“非(NOT)”运算的定义,2019/6/10,8,传统布尔检索模型,文献表示 将文档表示成一个集合，集合中的每个元素都为一个二元变量，取值非“0”即“1”，表示该元素所代表的主题词是否包含在该篇文档之内。若包括在文档中，则元素取值为1，反之则取0。 给定一个文献集合D，包含m篇文献，分别用d1,d2,d3dm表示。再给出一个标引词集合T，包含n个标引词t1,t2,tn。假定对文献集D的描述完全是基于该标引词集合的,则文献集D中任意一篇文献di就可以表示为（di1,di2,din）,2019/6/10,9,传统布尔检索模型,查询表示 在布尔检索系统中，根据用户提出的检索需求，选取适当的检索标识，与布尔运算符“与”、“或”、“非”共同构成与查询相符的检索提问式，也即相应的布尔表达式 例如，布尔提问式q = t1 and（t2 or not t3） q的主析取范式 （t1 and t2 and t3）or（t1 and t2 and not t3）or（t1 and not t2 and not t3） q的简化形式qdnf （1，1，1） or （1，1，0） or （1，0，0）,其中，（1，1，1）、（1，1，0）和（1，0，0）是qdnf的3个合取子项（合取子项可用符号qcc表示）,2019/6/10,10,传统布尔检索模型,匹配函数,2019/6/10,11,传统布尔检索模型,文献D1=(t1 ,t2 ,not t3) 查询Q=t1 and t2 and not t3,2019/6/10,12,传统布尔查询的评价,该模型结构简单、容易实现和快速检索。,2019/6/10,13,传统布尔查询的评价,布尔模型在检索系统的开发与应用中表现出的主要问题有： （1）准确匹配（exact matching）策略问题。布尔模型采用准确匹配策略，对检索过程中客观存在的一些不确定性情形绝对排斥，认为一篇文献对于某一提问要么是“相关的”，要么是“不相关的”。这种“非此即彼”的二值判断标准严重影响到检索系统的性能改善，并带来其他一些相关问题。 （2）布尔逻辑表达用户需求的能力问题。把用户的一个信息需求转换成一个恰当的布尔表达式，在很多情况下并不容易实现。,2019/6/10,14,传统布尔查询的评价,为了弥补这些缺陷，发展了一些别的检索模型，如向量空间、扩展布尔、概率检索和聚类模型。,2019/6/10,15,2.2 向量空间模型,2.2.1 传统向量空间检索 2.2.2 项的权重模式 2.2.3 相似度的计算 2.2.4 潜在语义标引,2019/6/10,16,2.2.1 传统向量空间检索,向量空间模型(Vector space model)介绍 向量空间模型(VSM)的评价,2019/6/10,17,向量空间模型介绍,1. 文献空间 （1）文献空间的概念 文献集合中的任一文献都可以表示为这个多维空间中的一个向量,这个空间就称为“文献空间” 在一个文献空间内，用向量D1来代表某一文献，则该向量在这个文献空间各个轴上的分量就是相应的表述该文献的各个项的权重 文献与空间点 （2）标引词空间,2019/6/10,18,向量空间模型介绍,2019/6/10,19,向量空间模型介绍,2. 项权重 （1）词频 越重要的项分配越高的权值 可以用词频来作为该项的权重（用tf表示） （2）文献频率 假设存在一个文献集合，其中大部分的文献都包含了某一项，则说明该项对某一主题的专指度较差，可能就不太重要 在设计项权重时，要考虑逆文献频率 （用idf表示）,2019/6/10,20,向量空间模型介绍,2. 项权重 （3）权重的规范化处理 为了抵消由篇幅带来的不同影响，经常要对项权重进行规范化处理 在各种规范化方法中，余弦规范是一种常用、有效的方法：tfidf权重/文献向量的欧氏长度,2019/6/10,21,向量空间模型介绍,3.文献向量与查询向量的匹配 匹配函数 利用向量的内积运算，得到文献向量Di与查询向量q之间的相似度 Sim(Di,q)=Diq 简单 存在的一个主要的不足是它忽略了项之间存在一些相互联系的事实。通常，需要引入一些特别的方法来改进这个相似度计算公式，使得其能够考虑到项的相互联系这一重要因素,2019/6/10,22,向量空间模型的评价,优点 简单，功能却非常强大 能将非结构化的文献表示成向量的形式，使得各种数学处理成为可能 模型的检索效果和布尔检索模型比起来，要好得多 不足 忽略项之间存在的相互联系，必然使得检索效果产生极大的偏差 传统向量处理模型不能处理布尔表达等结构化查询 改进 广义向量空间模型（GVSM）、潜在语义标引（LSI）、概率向量处理模型以及基于语义分析的向量空间模型（SVSM）,2019/6/10,23,2.2.2 项的权重模式,项向量的规范化,2019/6/10,24,项向量的规范化,构建一个项权重模式，需要涉及三个主要因素：词频、集合频率和向量的规范化。一般来说， 会为那些在特定文献中出现非常频繁的词（有着高词频的词）分配较高的权值； 为那些在文献集中很少部分的文献中出现的词（有着低文献频率的词）分配较高的权值； 对文献集合中长度不一的文献进行规范化处理，从而排除长文献与短文献在统计上的差别。,2019/6/10,25,项向量的规范化,余弦规范化 余弦规范化是在向量空间模型中最为常用的一种规范化方法。它的规范因子是： 这里的wi是项的原始tf*idf权重。 在一个文献中，如果一个项有着异常的高出现次数，利用余弦规范化，也可以减小这个高词频对权重的影响。,2019/6/10,26,2.2.3 相似度的计算,内积相似度运算 余弦相似度 “距离”相似度运算 等等,2019/6/10,27,2.2.4 潜在语义标引,模型的提出 潜在语义标引模型 模型的评价,2019/6/10,28,模型的提出,VSM模型的主要缺陷 假定项之间是相互独立的。因为忽略项之间的联系，从而在空间中增加或剔除一个项，对空间中已然存在的项是毫无影响的，实际上，在集合中增加一个新的文献，不仅仅会增加一些新的项，而且还会影响到已经存在的项的权重分配，因为新增的文献影响了这些项在整个集合中的逆文献频率（idf）因素。 词频矩阵过大（降维处理）,2019/6/10,29,潜在语义标引模型,该方法的基本步骤是： 1) 建立词频矩阵R0； 2) 计算词频矩阵的奇异值分解，把词频矩阵分解成3个矩阵的积：T0S0D0，其中T0、D0的列向量都两两正交，S0为对角线矩阵。如果要求T0、D0是满秩的并且S0中对角线上的单值按照从小到大的顺序排列，那么词频矩阵有，并且仅有一个这样的分解； 3) S0中对角线上的k个较大的单值被保留，其它较小的单值被置为0，去掉S0中单值为0的所有行和列得到对角阵S，去掉T0、D0中相应的列，得到矩阵T、D，并可以产生一个新的矩阵R=TSD，作为新的词频矩阵； 4) 对于每一个文档 d，用SVD方法筛选得到的词的组成新的向量替换原有的文本特征向量； 5) 保存所有向量集合，并用高级多维索引技术为文本集合创建索引； 6) 使用转换后的文档向量进行相似度计算。,2019/6/10,30,模型的评价,潜在语义标引的长处在于 第一、模型具有丰富的表述能力。保持了原始数据中的主要信息，同时，也捕捉住了隐含的潜在语义信息。 第二、传统的基于字面的词匹配系统，无法解决大量的同义或歧义现象造成的查全、查准下降的问题。而在潜在语义标引中，却能自动处理这类问题。 第三、潜在语义标引能够降低检索运行的时间。 第四、能够处理由于人为原因，如拼写错误导致的匹配问题。,2019/6/10,31,模型的评价,潜在语义标引的不足： 总体上看来，潜在语义标引对于较大集合的运算却是非常耗费的,2019/6/10,32,2.3 概率检索模型,检索过程存在内在的不确定性，如信息检索系统不能精确地定义文献集合中与查询相匹配的文献 概率理论是处理随机不确定性的理论 一个概率模型就是要估计概率，即 文献dk与查询q相关的概率。,2019/6/10,33,2.3 概率检索模型,概率模型试图在一个概率框架中处理信息检索问题，其基本思想是：给定一个用户的查询，则有一个包含相关文档且不包含不相关文档的集合。设想这个文档集合是一个理想的结果集。给出这个理想结果集的描述，并用于检索。 查询的过程是说明理想结果集属性的过程，初始的时候努力的猜测它们是什么，猜测结果我们将产生一个对理想结果集的概率描述，检索出最初的结果集，然后引入用户的交互，改善结果集。,2019/6/10,34,2.3 概率检索模型,基本假设：给定一个查询q和文档集中一个文档dk，概率模型试图找出用户对其感兴趣的概率，模型假设这个概率只是依赖于查询和文档的表示，进而模型假设文档集中存在一个子集，它使得在集合中的文档被认为是与查询相关的，不在集合中的则被认为是不相关的。,2019/6/10,35,2.3 概率检索模型,其主要优点是：理论上，文档按照其与目标集合的相关概率的降序排列。 主要缺点是： 需要最初将文档分为相关和不相关的集合； 所有权重都是二值的，模型中仍然假设索引项之间是相互独立的。,2019/6/10,36,2.3 概率检索模型,概率模型（Probabilistic Model） 概率排序原则：按照根据系统已经获得的全部数据估计出来的相关概率的降序排序是最优的排序 贝叶斯推断：由feedback更新先验概率分布 w1 = document is relevant ,w2 = non-relevant. x = (x1,x2, . . ., xn) binary vector 代表：INQUERY,2019/6/10,37,2.3 概率检索模型,优点： 无需经验性的权值计算公式，完全从理论上推断出ranking 很好支持用户反馈feedback，渐进的优化检索效果 缺点： 先验分布难于得到？,2019/6/10,38,Probabilistic Models,Rigorous formal model attempts to predict the probability that a given document will be relevant to a given query Ranks retrieved documents according to this probability of relevance (Probability Ranking Principle) Relies on accurate estimates of probabilities for accurate results,2019/6/10,39,Probabilistic Retrieval,Goes back to 1960s (Maron and Kuhns) Robertsons “Probabilistic Ranking Principle” Retrieved documents should be ranked in decreasing probability that they are relevant to the users query. How to estimate these probabilities? Several methods (Model 1, Model 2, Model 3) with different emphases on how estimates are done.,2019/6/10,40,Probabilistic Models: Some Notation,D = All present and future documents Q = All present and future queries (Di,Qj) = A document query pair x = class of similar documents, y = class of similar queries, Relevance is a relation:,2019/6/10,41,Probabilistic Models: Logistic Regression,Probability of relevance is based on Logistic regression from a sample set of documents to determine values of the coefficients. At retrieval the probability estimate is obtained by:,For the 6 X attribute measures shown next,2019/6/10,42,Probabilistic Models: Logistic Regression attributes,Average Absolute Query Frequency Query Length Average Absolute Document Frequency Document Length Average Inverse Document Frequency Inverse Document Frequency Number of Terms in common between query and document - logged,2019/6/10,43,Probabilistic Models: Logistic Regression,Estimates for relevance based on log-linear model with various statistical measures of document content as independent variables.,2019/6/10,44,Probabilistic Models,Strong theoretical basis In principle should supply the best predictions of relevance given available information Can be implemented similarly to Vector,Relevance information is required - or is “guestimated” Important indicators of relevance may not be term - though terms only are usually used Optimally requires on-going collection of relevance information,Advantages,Disadvantages,2019/6/10,45,Vector and Probabilistic Models,Support “natural language” queries Treat documents and queries the same Support relevance feedback searching Support ranked retrieval Differ primarily in theoretical basis and in how the ranking is calculated Vector assumes relevance Probabilistic relies on relevance judgments or estimates,2019/6/10,46,2.4 信息检索逻辑模型,在信息检索领域，可以看作是文献d满足查询q，也可以说文献d与查询q相关。 逻辑模型着重强调信息检索是一个推理过程，即如果文献同查询相关，可以通过推理得出,2019/6/10,47,2.4 信息检索逻辑模型,逻辑模型的基本思想 假如两个对象O1和O2，O1O2则表示对象O1蕴涵对象O2，换句话说，可以从O1中推理出O2。 假设通过某一方法，将文献的信息内容用d表示，查询的信息需求用q表示，dq表示可以从文献d中推理出查询q，即文献d中的信息足以蕴涵查询q中的信息。,2019/6/10,48,2.4 信息检索逻辑模型,几种典型的信息检索逻辑模型 古典逻辑模型 基于可能世界的逻辑模型 基于情景理论的信息检索模型 基于术语逻辑的信息检索模型 信息检索的元模型,2019/6/10,49,2.4 信息检索逻辑模型,个人观点 一篇文献看成是一个知识集，把文献集看成是一个知识库，把查询看成是一个知识集把检索操作看成验证要查询的知识集是否是知识库的一个子集，也就是说，把针对文献的查询转变成针对知识的查询。 进一步，将检索操作看成是逻辑程序的自动推理过程。借助于逻辑模型，可以研究查询与知识集的蕴含关系、知识集与文献的蕴含关系、查询与文献的相关程度；,2019/6/10,50,2.4 信息检索逻辑模型,个人观点 把信息检索系统看成是一个逻辑程序P。如果Q是一个查询，且P|-Q那么我们称Q可检的,2019/6/10,51,Inference Network Model,Inference Network Model In the simplest implementation, a document instantiates a term with a certain strength, and the credit from multiple terms is accumulated given a query to compute the equivalent of a numeric score for the document. If the strength is considered to be the weight of the term in the document, then the ranking is similar to the Vector Space Model or the Probabilistic Model. Any form can be used to define the strength of the instantiation, and any formula can be used.,2019/6/10,52,结构化文本检索模型概念,有时候，用户希望能够对文档中的某些结构组元中包含的信息进行检索，例如，对出现在章节标题的词进行检索。那么就需要一种模型，把文档内容与文档的结构结合起来，为用户提供信息检索的能力。这种模型就被称为结构化文本检索模型。,2019/6/10,53,结构化文本检索模型概念,在检索任务中，传统的结构化文本检索模型没有采用相关性的思想，它只是从各个结构组元中匹配用户的查询项。从这个意义上看，过去的结构化文档检索模型是一个数据检索模型，但是，检索系统能够搜索出那些部分匹配查询条件的文档，在这种情况下，这种匹配是近似的，并且某些排序也是使用这种近似的结构。因此，结构化文档检索算法可以看作是一种信息检索算法，但排序机制并不健全。 在结构化文本检索模型中，我们使用“匹配点”来表示文本与用户查询相匹配的词串位置；我们使用“区域”表示文本的块；使用“节点”表示文档的结构化组元。这样，一个节点是一个区域，具有文档的作者与用户所共知的、预定义的逻辑属性。,2019/6/10,54,结构化文本检索模型非重叠链表模型,基于非重叠链表的模型是把文档中的整个文本划分为非重叠文本区域，并用链表连接起来。因为有多种方法将文本分为非重叠的区域