信息检索模型.ppt

信息检索模型,哈工大信息检索研究室2007,这一部分将讲述,布尔模型，向量空间模型，扩展的布尔模型概率模型和基于语言模型的信息检索模型的区别和联系基于本体的信息检索模型和基于隐性语义索引的信息检索模型,信息检索模型的概述,什么是模型？,模型是采用数学工具，对现实世界某种事物或某种运动的抽象描述面对相同的输入，模型的输出应能够无限地逼近现实世界的输出举例：天气的预测模型信息检索模型给出了文档的表示方法，查询的表示方式以及查询与文档的匹配过程,信息检索模型,信息检索模型是一个四元组D,Q,F,R(qi,dj)D:文档集的机内表示Q:用户需求的机内表示F:文档表示、查询表示和它们之间的关系的模型框 架(Frame)R(qi,dj):排序函数，给query qi 和document dj评分信息检索模型取决于：从什么样的视角去看待查询式和文档基于什么样的理论去看待查询式和文档的关系如何计算查询式和文档之间的相似度,模型分类,信息检索模型,布尔向量空间概率知识,模糊集扩展的布尔模型,集合论,代数,扩展的向量空间隐性语义索引神经网络,语言模型推理网络信念网络,概率,基于本体论的模型,人工智能,布尔模型(Boolean Model),布尔模型,最早的IR模型，也是应用最广泛的模型目前仍然应用于商业系统中Lucene是基于布尔（Boolean）模型的,布尔模型描述,文档表示一个文档被表示为关键词的集合查询式表示查询式(Queries)被表示为关键词的布尔组合，用“与、或、非”连接起来，并用括弧指示优先次序匹配一个文档当且仅当它能够满足布尔查询式时，才将其检索出来检索策略基于二值判定标准,举例,Q=病毒AND（计算机OR电脑）ANDNOT医文档：D1:据报道计算机病毒最近猖獗D2：小王虽然是学医的，但对研究电脑病毒也感兴趣D3：计算机程序发现了艾滋病病毒传播途径上述文档哪一个会被检索到？,优点,到目前为止，布尔模型是最常用的检索模型，因为：由于查询简单，因此容易理解通过使用复杂的布尔表达式，可以很方便地控制查询结果相当有效的实现方法相当于识别包含了一个某个特定term的文档经过某种训练的用户可以容易地写出布尔查询式布尔模型可以通过扩展来包含排序的功能，即“扩展的布尔模型”,问题,布尔模型被认为是功能最弱的方式，其主要问题在于不支持部分匹配，而完全匹配会导致太多或者太少的结果文档被返回非常刚性:“与”意味着全部;“或”意味着任何一个很难控制被检索的文档数量原则上讲，所有被匹配的文档都将被返回很难对输出进行排序不考虑索引词的权重，所有文档都以相同的方式和查询相匹配很难进行自动的相关反馈如果一篇文档被用户确认为相关或者不相关，怎样相应地修改查询式呢？,向量空间模型,模型的提出,Gerard Salton在上世纪60年代提出的向量空间模型进行特征表达成功应用于SMART（System for the Manipulation and Retrieval of Text）文本检索系统这一系统理论框架到现在仍然是信息检索技术研究的基础,模型的描述,文档D(Document)：泛指文档或文档中的一个片段（如文档中的标题、摘要、正文等）。索引项t（Term）：指出现在文档中能够代表文档性质的基本语言单位（如字、词等），也就是通常所指的检索词，这样一个文档D就可以表示为D(t1,t2,tn)，其中n就代表了检索字的数量。特征项权重Wk（Term Weight）：指特征项tn能够代表文档D能力的大小，体现了特征项在文档中的重要程度。相似度S（Similarity）：指两个文档内容相关程度的大小,模型的特点,基于关键词(一个文本由一个关键词列表组成)根据关键词的出现频率计算相似度例如：文档的统计特性用户规定一个词项(term)集合，可以给每个词项附加权重未加权的词项:Q=database;text;information 加权的词项:Q=database 0.5;text 0.8;information 0.2 查询式中没有布尔条件根据相似度对输出结果进行排序支持自动的相关反馈有用的词项被添加到原始的查询式中例如：Q database;text;information;document,模型中的问题,怎样确定文档中哪些词是重要的词？（索引项）怎样确定一个词在某个文档中或在整个文档集中的重要程度？（权重）怎样确定一个文档和一个查询式之间的相似度？,索引项的选择,若干独立的词项被选作索引项(index terms)or 词表vocabulary索引项代表了一个应用中的重要词项计算机科学图书馆中的索引项应该是哪些呢?,索引项的选择,这些索引项是不相关的(或者说是正交的)，形成一个向量空间vector space实际上，这些词项是相互关联的当你在一个文档中看到“计算机”,非常有可能同时看到“科学”当你在一个文档中看到“计算机”,有中等的可能性同时看到“商务”当你在一个文档中看到“商务”，只有很少的机会同时看到“科学”,词项的权重,根据词项在文档(tf)和文档集(idf)中的频率(frequency)计算词项的权重tfij=词项j在文档i中的频率df j=词项j的文档频率=包含词项j的文档数量idfj=词项j的反文档频率=log2(N/df j)N:文档集中文档总数反文档频率用词项区别文档,文档的词项权重(TFIDF举例),文本：“俄罗斯频繁发生恐怖事件，俄罗斯的安全部门加大打击恐怖主义的力度。”,Idf 计算示例,查询式的词项权重,如果词项出现在查询式中，则该词项在查询式中的权重为1，否则为0也可以用用户指定查询式中词项的权重一个自然语言查询式可以被看成一个文档查询式：“有没有周杰伦的歌？”会被转换为:查询式：“请帮我找关于俄罗斯和车臣之间的战争以及车臣恐怖主义首脑的资料”会被转换为:过滤掉了：“请帮我找”，“和”，“之间的”，“以及”，“的资料”两个文档之间的相似度可以同理计算,由索引项构成向量空间,2个索引项构成一个二维空间，一个文档可能包含0,1 或2个索引项di=0,0(一个索引项也不包含)dj=0,0.7(包含其中一个索引项)dk=1,2(包含两个索引项)类似的，3个索引项构成一个三维空间，n个索引项构成n维空间一个文档或查询式可以表示为n个元素的线性组合,文档集 一般表示,向量空间中的N个文档可以用一个矩阵表示矩阵中的一个元素对应于文档中一个词项的权重。“0”意味着该词项在文档中没有意义，或该词项不在文档中出现。,T1 T2.TtD1 d11 d12 d1tD2 d21 d22 d2t:Dn dn1 dn2 dnt,图示,举例:D1=2T1+3T2+5T3D2=3T1+7T2+T3Q=0T1+0T2+2T3,D1比D2更接近Q吗？怎样衡量相似程度？夹角还是投影,相似度计算,相似度是一个函数，它给出两个向量之间的相似程度，查询式和文档都是向量，各类相似度存在于：两个文档之间（文本分类，聚类）两个查询式之间（常问问题集）一个查询式和一个文档之间（检索）人们曾提出大量的相似度计算方法，因为最佳的相似度计算方法并不存在。,通过计算查询式和文档之间的相似度,可以根据预定的重要程度对检索出来的文档进行排序可以通过强制设定某个阈值，控制被检索出来的文档的数量检索结果可以被用于相关反馈中，以便对原始的查询式进行修正。(例如：将文档向量和查询式向量进行结合),相似度度量 内积(Inner Product),文档D 和查询式Q 可以通过内积进行计算:sim(D,Q)=(dik qk)dik 是文档di中的词项k 的权重，qk 是查询式Q中词项k的权重对于二值向量,内积是查询式中的词项和文档中的词项相互匹配的数量对于加权向量,内积是查询式和文档中相互匹配的词项的权重乘积之和,内积 举例,二值（Binary）:D=1,1,1,0,1,1,0Q=1,0,1,0,0,1,1sim(D,Q)=3,retrieval,database,architecture,computer,text,management,information,向量的大小=词表的大小=70 意味着某个词项没有在文档中出现，或者没有在查询式中出现,加权 D1=2T1+3T2+5T3 D2=3T1+7T2+T3 Q=0T1+0T2+2T3sim(D1,Q)=2*0+3*0+5*2=10 sim(D2,Q)=3*0+7*0+1*2=2,内积的特点,内积值没有界限不象概率值，要在(0,1)之间对长文档有利内积用于衡量有多少词项匹配成功，而不计算有多少词项匹配失败长文档包含大量独立词项，每个词项均多次出现，因此一般而言，和查询式中的词项匹配成功的可能性就会比短文档大。,余弦(Cosine)相似度度量,余弦相似度计算两个向量的夹角余弦相似度是利用向量长度对内积进行归一化的结果,CosSim(Di,Q)=,D1=2T1+3T2+5T3 CosSim(D1,Q)=5/38=0.81D2=3T1+7T2+T3 CosSim(D2,Q)=1/59=0.13 Q=0T1+0T2+2T3,用余弦计算，D1 比 D2 高6倍；用内积计算，D1 比 D2 高5倍,其它相似度度量方法,存在大量的其它相似度度量方法,Jaccard Coefficient:,D1=2T1+3T2+5T3 Sim(D1,Q)=10/(38+4-10)=10/32=0.312D2=3T1+7T2+T3 Sim(D2,Q)=2/(59+4-2)=2/61=0.033 Q=0T1+0T2+2T3,D1 比 D2 高9.5倍,示例,二值化的相似度度量,Inner Product:Cosine:Jaccard:,di and qk here are sets of keywords,di 和 qk here are vector,向量空间优点,术语权重的算法提高了检索的性能 部分匹配的策略使得检索的结果文档集更接近用户的检索需求可以根据结果文档对于查询串的相关度通过Cosine Ranking等公式对结果文档进行排序,不足,标引词之间被认为是相互独立随着Web页面信息量的增大、Web格式的多样化，这种方法查询的结果往往会与用户真实的需求相差甚远，而且产生的无用信息量会非常大隐含语义索引模型是向量空间模型的延伸,扩展的布尔模型,布尔检索示例,“飞碟”AND“小说”：只能检索出D4，无法显现D1,D2,D3的差异“飞碟”OR“小说”：可以检出D1,D2,D4，但无法显现它们的差异,布尔模型和向量空间模型相结合,布尔模型可以和向量空间模型相结合，先做布尔过滤，然后进行排序：首先进行布尔查询将全部满足布尔查询的文档汇集成一个文档用向量空间法对布尔检索结果进行排序,如果忽略布尔关系的话，向量空间查询式和布尔查询式是相同的,先“布尔”，后“排序”存在的问题,如果“与”应用于布尔查询式,结果集可能太窄,因而影响了后面的排序过程如果“或”应用于布尔查询式,就和纯向量空间模型没有区别了在第一步，如何最佳地应用布尔模型呢？提出扩展布尔模型,扩展布尔模型中的“或”关系,给定一个或关系的查询式：x y假设文档di中x和y的权重被归一化在(0,1)区间内:wx,j=（tfx,j/maxl tfl,j）（idfx/maxi idfi）sim(qor,dj)=(x2+y2)/2 0.5 where x=wx,j and y=wy,j,一个文档在(1,1)处获得最高的权重，此时意味着文档包含了全部两个查询词，并且查询词在文档中的权重也是最高的函数sim()度量了从原点出发的文档向量长度,扩展布尔模型中的“与”关系,给定一个联合的查询式 x ysim(qand,dj)=1(1 x)2+(1 y)2/2 0.5函数sim()表示从(1,1)出发到d的向量长度,扩展的布尔检索相似度计算示例,观察,如果权值是布尔型的，x出现在文档dj中，则x在文档dj中具有权重1，否则为0当dj 包含x和y时sim(qand,dj)=sim(qor,dj)=1当dj 既不包含x 也不包含y时sim(qand,dj)=sim(qor,dj)=0当dj 包含x 和y二者之一时sim(qand,dj)=1 1/20.5=0.293sim(qor,dj)=1/20.5=0.707,观察,一个词项的存在将对“或”关系查询式提供0.707的增益值，但对“与”关系查询式仅提供0.293的增益值一个词项不存在，将给“与”关系的查询式提供0.707的罚分当x 和y 有权值0.5,sim(qand,d)=sim(qor,d)=0.5在一个“与”关系查询中，两个词项的权重均为0.5，则相似度为0.5。其中一个权重为1，另一个为0，相似度为0.293。在“或关系”查询中，情况恰好相反在“与关系”查询中，如果一个词项的权重低于0.5，将给相似度贡献一个较大的罚分,p-norm 模型,扩展布尔模型可以被泛化为m 个查询项:sim(qor,d)=(x12+x22+.+xm2)/m 0.5sim(qand,d)=1(1 x1)2+(1 x2)2+.+(1 xm)2/m 0.5它可以被进一步地 泛化为p-norm model:sim(qor,d)=(x1p+x2p+.+xmp)/m 1/psim(qand,d)=1(1 x1)p+(1 x2)p+.+(1 xm)p/m 1/p当p=1时,sim(qor,d)=sim(qand,d)=(x1+x2+.+xm)/m通过语词-文献权值的和来求合取和析取查询的值，和向量空间中的内积相似当p=,sim(qor,d)=max(xi);sim(qand,d)=min(xi)模糊逻辑模型(Fuzzy logic model),概率模型,概率模型,检索问题即求条件概率问题If Prob(R|di,q)Prob(NR|di,q)then di是检索结果，否则不是检索结果,检索的理想结果,理想答案集(ideal answer set)给定一个用户的查询串，相对于该串存在一个包含所有相关文档的集合我们把这样的集合看作是一个理想的结果文档集用索引项刻画理想答案集的属性把查询处理看作是对理想结果文档集属性的处理我们并不能确切地知道这些属性，我们所知道的是用索引词的语义来刻画这些属性,实际采取的策略,初始估计由于在查询期间这些属性都是不可见的，这就需要在初始阶段来估计这些属性。这种初始阶段的估计允许我们对首次检索的文档集合返回理想的结果集，并产生一个初步的概率描述。相关反馈(relevance feedback)为了提高理想结果集的描述概率，系统需要与用户进行交互式操作，具体处理过程如下：用户大致浏览一下结果文档，决定哪些是相关的，哪些是不相关的；然后系统利用该信息重新定义理想结果集的概率描述；重复以上操作，就会越来越接近真正的结果文档集。,概率模型的理论,概率模型是基于以下基本假设：给定一个用户的查询串 q和集合中的文档dj，概率模型估计用户查询串与文档dj 相关的概率。概率模型假设这种概率只决定于查询串和文档。更进一步说，该模型假定在文档集合中存在一个子集，即相对于查询串q的结果文档子集，这种理想的集合用R表示，集合中的文档是被预料与查询串相关的。这种假设存在着缺点，因为它没有明确定义计算相关度的概率，下面将给出这种概率的定义。,查询式与文档的相关度概率定义,在概率模型中索引术语的权重都是二值的 wi,j0,1,wi,q0,1,查询式q是索引词项集合的子集设R是相关文档集合（初始的猜测集合），是R的补集（非相关文档的集合）表示文档dj和查询式q相关的概率；表示文档dj和查询式q不相关的概率；,查询式与文档的相关度概率定义,文档dj对于查询串q的相关度值定义为：根据贝叶斯原理其中：代表从相关文档集合R中随机选取 文档dj的概率，P(R)表示从整个集合中随机选取一篇文档作为相关文档的概率，依此定义 和,推导,因为对于集合中所有的文档P(R)和 是相同的，所以假设索引术语是相互独立的则：,最终的概率模型排序公式,表示集合R中随机选取的文档中出现索引术语ki的概率，表示集合R中随机选取的文档中不出现索引术语的概率，则有：类似定义 和，在相同查询背景下，忽略对所有文献保持不变的因子，最终得到：这是概率模型主要的排序公式,初始化方法,由于我们在开始时并不知道集合R，因此必须 设计一个初始化计算 和 的算法。在查询的开始间段只定义了查询串，还没有得到结果文档集。我们不得不作一些简单的假设，假定P(ki|R)对所有的索引术语来说是常数（一般等于0.5）假定索引术语在非相关文档中的分布可以由索引术语在集合中所有文档中的分布来近似表示。P(ki|R)=0.5=ni/Nni表示出现索引术语ki的文档的数目，N是集合中总的文档的数目。,改进,V表示用概率模型初步检出的经过排序的子集，Vi为包含ki的V的一个子集。为了改善概率排序，需要对上述初始化公式改进：通过迄今已检出的文献中标引词ki的分布来估计 通过假定所有未检出的文献都是不相关的来估计这一过程可以递归重复,概率模型小结,优点文档可以按照他们相关概率递减的顺序来排序。缺点开始时需要猜想把文档分为相关和不相关的两个集合，一般来说很难实际上这种模型没有考虑索引术语在文档中的频率（因为所有的权重都是二值的）假设标引词独立概率模型是否要比向量模型好还存在着争论，但现在向量模型使用的比较广泛。,基于统计语言模型的信息检索模型,统计语言模型,统计语言模型在语音识别中产生argmax p(s|a)，s是文字串，a是声学参数串argmax p(s|a)=argmax p(a|s)p(s)/p(a)忽略p(a)，p(a|s)是声学模型p(s)是语言模型p(s)=p(w1,w2,w3,wn)=i=1n p(wi|hi)n表示句子长度hi=w1,w2,wi-1，代表上下文,从文档中建立语言模型,原始文本 He can buy you the can of soda 一元模型(Unigram):(8 words in vocabulary)p1(He)=p1(buy)=p1(you)=p1(the)=p1(of)=p1(soda)=.125,p1(can)=.25二元模型(Bigram):p2(He|)=1,p2(can|He)=1,p2(buy|can)=.5,p2(of|can)=.5,p2(you|buy)=1,.三元模型(Trigram):p3(He|,)=1,p3(can|,He)=1,p3(buy|He,can)=1,p3(of|the,can)=1,.,p3(|of,soda)=1.,举例智能拼音输入问题,yi zhi xiao hua mao一 之 小 华 毛以 只 校 话 贸异 之 销 化 猫已 枝 花 值 基于大规模语料库建立的语言模型应该能够告诉我们：p(“一只小花猫”)p(“一枝小花猫”)p(任何其它候选字串),语言模型和搜索引擎的相似性,利用搜索引擎查找一个词串的过程很象在建立语言模型时统计N-gram出现频度的过程相同的数据稀疏问题如果在Google中输入的查询式太长，则很难找到满意的结果原因：如果查询式包括8个词，索引表中有10万词，则1000008=1040，目前互联网的字节数在T级，也就是1012，因此输入太长的查询式无法找到结果，因为数据稀疏在建立语言模型时同样存在严重的数据稀疏问题有人在探讨利用互联网建立语言模型,基于语言模型的IR模型的概念,文档语言模型每个文档对应一个统计语言模型，称为文档的语言模型(Language Model)。它主要描述了该文档中各个单词的统计分布特征。因此每个文档看作是由其语言模型抽样产生的一个样本。基于文档语言模型计算查询式的出现概率一个查询式也可以看作是由文档的语言模型抽样产生的一个样本。因此可以根据每个文档的语言模型抽样生成检索的概率来对其排序，其概率值越大，则该文档就越满足该检索要求。,举例,假设文档集合中只有1和2两个文本文本1产生的语言模型1p1(a)=0.25,p1(b)=0.5,p1()=1/64,c.r,剩下的s,t,u,v,w,x,y,z均为0文本2产生的语言模型2p2(a)=0.7,p2(b)=0.05,p2()=1/64,c.r,剩下的s,t,u,v,w,x,y,z均为0查询式：q=abacaadp1(q)=0.25*0.5*0.25*1/64*0.25*0.25*1/644.8*10-7p2(q)=0.7*0.05*0.7*1/64*0.7*0.7*1/642.9*10-6,例子中的检索结果,从上例中可以看出q在语言模型1下获得了较低的概率4.8*10-7q在语言模型2下获得了较高的概率2.9*10-6说明文本2比文本1更有可能生成q若输入q，应该检索出文本2，而不是文本1,和传统概率模型的比较,基本思想完全不同传统的信息检索概率模型文档d与检索q的相关度排序函数定义为事件R(文档是否满足检索要求)的概率，即：f(q,d)=P(R|d)；相关度排序函数定义虽然比较直观，但相关性是一个抽象的概念，该定义本身没有也无法具体给出R的定义，所以该模型在理论上存在很大的模糊性。基于语言模型的检索模型相关度排序函数则定义为由文档的语言模型生成检索的概率，即f(q,d)=p(q|d)。建立在统计语言模型理论基础上，定义明确，便于操作。,和传统概率模型的比较（续）,具体实施方法不同传统的概率模型由于没有也无法对相关性做出明确定义，因此一般需要在检索中，首先给定带有相关性标记的文档作为建立模型的基础。在实际中，要针对每个检索给定学习数据，几乎不可能。该问题是传统信息检索模型存在的一个主要问题。基于语言模型的信息检索模型可以基于每个文档直接计算出相关度排序函数，从而有效地避免这个问题还可以用该模型为传统概率模型形成初始检索。,基于本体论的信息检索模型,本体论,本体论（Ontology）最早是哲学的分支，研究客观事物存在的本质。本体（ontology）的含义是形成现象的根本实体(常与“现象”相对)。从哲学的范畴来说，本体是客观存在的一个系统的解释或说明，关心的是客观现实的抽象本质。它与认识论（Epistemology）相对，认识论研究人类知识的本质和来源。本体论研究客观存在，认识论研究主观认知。,各种关于本体的定义,在人工智能界，最早给出本体定义的是Neches等人，将本体定义为“给出构成相关领域词汇的基本术语和关系，以及利用这些术语和关系构成的规定这些词汇外延的规则的定义”。1993年，Gruber给出了本体的一个最为流行的定义，即“本体是概念模型的明确的规范说明”。后来，Borst在此基础上,给出了本体的另外一种定义：“本体是共享概念模型的形式化规范说明”。Studer等对上述两个定义进行了深入的研究，认为“本体是共享概念模型的明确的形式化规范说明”。,本体的分类和内容,本体的分类本体是采用某种语言对概念化的描述，本体的分类按照表示和描述的形式化的程度不同，可以分为：完全非形式化的、半形式化的、严格形式化的，形式化程度越高，越有利于计算机进行自动处理。本体的内容从概念化对象的定义来看，一个领域的术语、术语的定义以及各个术语之间的语义网络，应是任一个领域本体论所必须包含的基本信息。概念之间的关系同义关系：表达了在相似数据源间的一种等价关系，是一种对称关系上下位关系：不对称的，是一种偏序关系，具有传递性其它各种语义关系各个概念间复杂的语义关系组成了语义网络图，概念在其中表现为节点，而节点间的弧则代表了上述的关系。,上下位关系和同义关系,土豆,马铃薯,土豆,白薯,地瓜,红薯,地瓜,薯类,植物,同义关系,上下位关系,上位,下位,语义关系,构造本体的要点,出于对各自问题域和具体工程的考虑，构造本体的过程各不相同。目前没有一个标准的本体的构造方法。最有影响的是Gruber在1995年提出的5条规则：清晰（Clarity）本体必须有效的说明所定义术语的意思。定义应该是客观的，形式化的一致（Coherence）它应该支持与其定义相一致的推理可扩展性（Extendibility）应该提供概念基础，支持在已有的概念基础上定义新的术语编码偏好程度最小（Minimal encoding bias）概念的描述不应该依赖于某一种特殊的符号层的表示方法本体约定最小（Minimal ontological commitment）本体约定应该最小，只要能够满足特定的知识共享需求即可。,领域本体,领域本体(Domain ontology)的概念提供了某个专业学科领域中概念的词表以及概念间的关系在该领域里占主导地位的理论，是某一领域的知识表示建立本体的方式借助某种本体描述语言，采用“恳谈法”从人类专家那里获得知识，经过抽象组织成领域本体应用实例IBM中国研究中心在信息集成项目中运用本体哈工大机器翻译研究室基于本体进行跨语言检索的研究,基于本体的检索过程,用户向信息检索系统提出检索申请。信息检索系统产生一个界面与用户交互。界面接收用户提出的查询关键字后，系统查询本体库，从中找出出现该关键字的各个领域，然后将其领域以及在该领域下的关键字的含义罗列给用户。用户此时可根据自己的意图，在界面上确定所需查找的领域及含义。系统将经过本体规范后的请求交给全文搜索引擎进行检索。全文搜索引擎检索后返回给用户检索信息。,利用本体进行检索的好处,解决从查询语言到检索语言之间转换过程中出现的语义损失和曲解等问题保证在检索过程中能够有效地遵循用户的查询意图，获得预期的检索信息。,马铃薯,红薯,地瓜,白薯,本体扩展,隐性语义索引(LSI),问题引出,自然语言文本中的词汇(术语)具有一词多义(polysemy)和一义多词(synonymy)的特点.由于一词多义,基于精确匹配的检索算法会报告许多用户不要的东西;处理什么地方处理旧家具？你去把那个叛徒处理了处理自然语言很难由于一义多词,基于精确匹配的检索算法又会遗漏许多用户想要的东西.“互联网”，“万维网”，“因特网”，“国际互联网”等,词汇-文档矩阵,设Doc1,Doc2,Doc3是三个文件.一些术语在这三个文件中的出现情况如下表:Doc1Doc2Doc3-access X document Xretrieval XXinformation X*X*theory Xdatabase Xindexing Xcomputer X*X*-,假定用information 和computer作为主题词进行检索,那么Doc2和Doc3与之精确匹配,因而中选.然而,Doc2是用户并不想要的文件,Doc1才是想要的查不出来,不想要的倒查了出来.这说明精确匹配不能很好地反映用户的意图.,词汇-文档矩阵,LSI(Latent Semantic Indexing)将自然语言中的每个文档视为以词汇为维度的空间中的一个点，认为一个包含语义的文档出现在这种空间中，它的分布绝对不是随机的，而是服从某种语义结构。同样地，也将每个词汇视为以文档为维度的空间中的一个点。文档是由词汇组成的，而词汇又要放到文档中去理解，体现了一种“词汇文档”双重概率关系。,LSI地提出,当然,如果能基于自然语言理解来做这件事,那一切问题就都没有了。问题是：自然语言理解的目前水平还是有限度的;即使用自然语言理解,效率也会很低我们希望找到一种办法,既能反映术语之间内在的相关性,又具有较高的效率.1990年，来自University of Chicago、Bell Communications Research等五家单位和学者共同提出了潜在语义分析（Latent Semantic Indexing)，缩写为LSI）这一自然语言处理的方法,算法步骤,以词项(terms)为行,文档(documents)为列做一个大矩阵(matrix).设一共有t行d列,矩阵名为A.矩阵的元素为词项在文档中的出现频度.数学上可以证明:A可以分解为三个矩阵T0,S0,D0T(D0的转置)的积.这种分解叫做单值分解(singlar value decomposition)简称SVDA=T0*S0*D0T,算法步骤,一般要求T0,S0,D0都是满秩的.不难做到把S0的元素沿对角线从大到小排列.现在,把S0的m个对角元素的前k个保留,后m-k个置0,我们可以得到一个新的近似的分解:Xhat=T*S*DT 奇妙的是,Xhat在最小二乘意义下是X的最佳近似!这样,我们实际上有了一个降维的途径.K值的选择k越大失真越小,但开销越大k的选择是按实际问题的要求进行平衡的结果,三个问题,给定矩阵A,基于A可以问三类同文件检索密切有关的问题术语i和j有多相似?即术语的类比和聚类问题文件i和j有多相似?即文件的类比和聚类问题术语i和文件j有多相关?即术语和文件的关联问题,三个问题的答案,比较两个术语 做正向乘法:Xhat*XhatT=T*S*DT*D*S*TT=T*S2*TT=(TS)*(TS)TDT*D=I,因为D已经是正交归一的,s=sT它的第i行第j列表明了术语i和j的相似程度比较两个文件做逆向乘法:XhatT*Xhat=D*S*TT*T*S*DT=D*S2*DT=(SD)(SD)TTT*T=I,因为T已经是正交归一的,s=sT它的第i行第j列表明了文件i和j的相似程度比较一个文件和一个术语恰巧就是Xhat本身.它的第i行第j列表明了术语i和文件j的相关联程度.,示例,原始矩阵A,示例,SVD分解：,示例,A降维处理：B=S2*2DT2*d图示：,示例,向量夹角余弦值：文本之间相似度矩阵,CosSim(Di,Q)=,降维前后的对比,表中列出了文档在新空间的相似度，d1和d2之间的相似度为0.78，d4,d5和d6为0.94，0.93，0.74,而在原空间上两者的值是相等的。在原空间中，d2,d3没有共同的单词，相似度为0，但是在新空间中的相似度为0.88之所已有这种结果，在于它们之间存在着同现模式。,查询处理,如何在降维空间中表示查询字段和新增文档查询可以作为一个伪文档每次重新计算SVD，计算量太大解决方案：A=TSDT,TTA=TTTSDT,TTA=SDT新的查询q，再降维后新空间表示为Tt*kTq（可以理解为一种映射）,对LSI的理解,最佳近似矩阵从数据压缩的角度看，Xhat是秩为k的前提下矩阵X的全局最佳近似矩阵。降维LSI不同于向量空间模型（VSM）中文档和词汇的高维表示，而是将文档和词汇的高维表示投影在低维的潜在语义空间（Latent Semantic Space）中，缩小了问题的规模，得到词汇和文档的低维表示。语义关联的发现对应于小奇异值的奇异向量被忽略后，噪声被大量消减，而使语言单元之间的意义上的相关性显示出来。潜在语义空间中（不论是文档空间，还是词汇空间），每个维度代表了一个潜概念（Latent Concept）,利用LSI进行检索,对查询式的要求和传统的基于关键词的查询不同，潜语义检索允许用户提交类似于自然语言的查询条件，而不一定必须是几个分离的词汇。查询式越长，提供的信息需求越充分，越明确对查询式q进行处理检索过程检索过程就是把查询式的集合视为是一个虚拟的文件，检索的任务是把这个虚拟的文件和其他文件做相似性比较,挑选最相似的出来相似度计算方法可以采用线性代数理论中的各种方法，比如向量夹角等，根据实际情况而定,适用性,多数情况下，潜在语义索引的性能好于向量空间模型，因为利用了同现度潜在语义索引的应用依赖于具体的文档集合适用于词汇异构度很高的文档集合从应用角度，计算量太大框架定义完整，优化准则清楚,本章小结,介绍了布尔模型和向量空间模型介绍了概率模型和基于语言模型的信息检索模型介绍了基于本体的信息检索模型及以及隐性语义索引的信息检索模型,