信息检索原理Lecture3-Model

11《信息检索原理》课程Beihang内容回顾1.给定查询q，相关文档集R={d1,d3,d5,d7,d9}–查询结果集{d3,d2,d4,d5,d1,d10,d11,d7,d13,d9}–试画出标准11点查全率下的PR曲线2.查全率和查准率的计算都需要已知相关文档集，但实际中往往难以准确获知，在这种情况下，如何评价一个信息检索系统？3.TREC–如何确定相关文档集？《信息检索原理》课程信息检索模型授课人：孙海龙2013.10.1123《信息检索原理》课程Beihang提纲•模型定义与分类•布尔模型•向量空间模型•概率模型•统计语言模型4《信息检索原理》课程Beihang什么是模型？•模型是采用数学工具，对现实世界某种事物或某种运动的抽象描述•针对相同的输入，模型的输出应能够无限地逼近现实世界的输出–举例：天气的预测模型35《信息检索原理》课程Beihang信息检索模型•信息检索模型是一个四元组[D,Q,F,R(qi,dj)]–D:文档集–Q:用户的查询需求–F:文档表示、查询表示及其之间的关系的模型框架–R(qi,dj):排序函数，给queryqi和documentdj评分•信息检索模型取决于：–从什么样的视角去看待查询式和文档–基于什么样的理论去看待查询式和文档的关系–如何计算查询式和文档之间的相似度6《信息检索原理》课程Beihang模型分类信息检索模型布尔向量空间概率知识模糊集扩展的布尔模型集合论代数扩展的向量空间隐性语义索引神经网络语言模型推理网络信念网络概率基于本体论的模型人工智能47《信息检索原理》课程Beihang提纲•模型定义与分类•布尔模型•向量空间模型•概率模型•统计语言模型8《信息检索原理》课程Beihang布尔模型(BooleanModel)59《信息检索原理》课程Beihang布尔模型描述•文档D表示–一个文档被表示为关键词的集合•查询式Q表示–查询式(Queries)被表示为关键词的布尔组合，用“与、或、非”连接起来，并用括弧指示优先次序•匹配F–一个文档当且仅当它能够满足布尔查询式时，才将其检索出来–检索策略基于二值判定标准•算法R–根据匹配框架F判定相关10《信息检索原理》课程Beihang查询表示•在布尔模型中，所有索引项的权值变量和文档dj与查询q的相关度都是二值的•查询q被表述成一个常规的布尔表达式，为方便计算查询q和文档d的相关度，一般将查询q的布尔表达式转换成析取范式qDNF))()(,()(|如果,1其他,0qq),(FijitqpdpqqdsimiDNFFF611《信息检索原理》课程Beihang示例•文档集包含两个文档：–文档1：abcfgh–文档2：afbxyz–用户查询：文档中出现a或者b，但一定要出现z。•将查询表示为布尔表达式,并转换成析取范式–q=(a^b^z)v(┐a^b^z)v(a^┐b^z)•文档1和文档2的三元组对应值分别为(1,1,0)和(1,1,1)•经过匹配,将文档2返回()qabz(1,0,1)(0,1,1)(1,1,1)DNFq12《信息检索原理》课程Beihang优点•到目前为止，布尔模型是昀常用的检索模型–查询简单，容易理解–通过复杂的布尔表达式，可方便地控制查询结果•相当有效的实现方法–相当于识别包含特定term的文档•用户可以容易地写出布尔查询式•布尔模型可以通过扩展来包含排序的功能，即“扩展的布尔模型”713《信息检索原理》课程Beihang问题•布尔模型表达能力弱，主要问题在于不支持部分匹配，而完全匹配会导致返回太多或太少的结果–非常刚性:“与”意味着全部;“或”意味着任何一个•很难控制被检索的文档数量–原则上讲，所有被匹配的文档都将被返回•很难对输出进行排序–不考虑索引词的权重，所有文档都以相同的方式和查询相匹配•很难进行自动的相关反馈–如果一篇文档被用户确认为相关或者不相关，怎样相应地修改查询式呢？14《信息检索原理》课程Beihang向量空间模型815《信息检索原理》课程Beihang模型的提出•GerardSalton在1960s提出的向量空间模型进行特征表达•成功应用于SMART（SystemfortheMechanicalAnalysisandRetrievalofText）文本检索系统•这一系统理论框架到现在仍然是信息检索技术研究的基础16《信息检索原理》课程Beihang模型的描述•文档D(Document)：泛指文档或文档中的一个片段（如文档中的标题、摘要、正文等）。•索引项/特征项t（Term）：文档中能够代表文档性质的基本语言单位（如字、词等），即通常所指的检索词。文档D可表示为D(t1,t2,…,tn)，其中n代表特征项的数量。•特征项权重Wi（TermWeight）：特征项ti能够代表文档D的能力的大小，体现特征项在文档中的重要程度。•相似度S（Similarity）：指两个文档内容相关程度的大小917《信息检索原理》课程Beihang模型的特点•基于关键词(一个文本由一个关键词列表组成)•根据关键词的出现频率计算相似度–例如：文档的统计特性•用户规定一个词项(term)集合，可以给每个词项附加权重–未加权的词项:Q=database;text;information–加权的词项:Q=database0.5;text0.8;information0.2–查询式中没有布尔条件•根据相似度对输出结果进行排序•支持自动的相关反馈–有用的词项被添加到原始的查询式中–例如：Qdatabase;text;information;document18《信息检索原理》课程Beihang词项的权重•根据词项在文档(tf)和文档集(idf)中的频率(frequency)计算词项的权重–tfij=词项j在文档i中的频率–dfj=词项j的文档频率=包含词项j的文档数量–idfj=词项j的逆文档频率=log2(N/dfj)•N:文档集中文档总数•用词项区别文档1019《信息检索原理》课程Beihang由索引项构成向量空间•2个索引项构成一个二维空间，一个文档可能包含0,1或2个索引项–di=0,0(一个索引项也不包含)–dj=0,0.7(包含其中一个索引项)–dk=1,2(包含两个索引项)•类似的，3个索引项构成一个三维空间，n个索引项构成n维空间•一个文档或查询式可以表示为n个元素的线性组合20《信息检索原理》课程Beihang文档集–一般表示•向量空间中的N个文档可用一个矩阵表示•矩阵中的一个元素对应于文档中一个词项的权重。“0”意味着该词项在文档中没有意义，或该词项不在文档中出现。T1T2….TtD1d11d12…d1tD2d21d22…d2t::::::::Dndn1dn2…dnt1121《信息检索原理》课程Beihang示例举例:D1=2T1+3T2+5T3D2=3T1+7T2+T3Q=0T1+0T2+2T3T3T1T2D1=2T1+3T2+5T3D2=3T1+7T2+T3Q=0T1+0T2+2T3732522《信息检索原理》课程Beihang相似度计算•查询式和文档都是向量，相似度给出两个向量之间的相似程度：–两个文档之间（文本分类，聚类）–两个查询式之间（常问问题集）–一个查询式和一个文档之间（检索）•存在多种相似度计算方法，因为普适的计算方法并不存在。1223《信息检索原理》课程Beihang查询式和文档之间的相似度•可根据重要程度对检索出的文档进行排序•可以通过强制设定某个阈值，控制检索出的文档的数量•检索结果可用于相关反馈，以对原始的查询式进行修正。(例如：将文档向量和查询式向量结合)24《信息检索原理》课程Beihang相似度度量–内积(InnerProduct)•文档D和查询式Q可以通过内积进行计算:–dik是文档di中的词项k的权重，qk是查询式Q中词项k的权重•对于二值向量,内积是查询式中的词项和文档中的词项相互匹配的数量•对于加权向量,内积是查询式和文档中相互匹配的词项的权重乘积之和tkkikqdQDsim1)(),(1325《信息检索原理》课程Beihang内积–举例•二值（Binary）:–D=1,1,1,0,1,1,0–Q=1,0,1,0,0,1,1–sim(D,Q)=3向量的大小= 词表的大小= 70 意味着某个词项没有在文档中出现，或者没有在查询式中出现加权D1= 2T1+ 3T2+ 5T3           D2= 3T1+ 7T2+   T3      Q = 0T1+ 0T2+  2T3sim(D1, Q) = 2*0 + 3*0 + 5*2  = 10sim(D2, Q) = 3*0 + 7*0 + 1*2  =  226《信息检索原理》课程Beihang内积的特点•内积值没有界限–不同于在(0,1)之间概率值•对长文档有利–内积用于衡量有多少词项匹配成功，而不计算有多少词项匹配失败–长文档包含大量独立词项，每个词项均多次出现，因此匹配成功的可能性比短文档大。1427《信息检索原理》课程Beihang余弦(Cosine)相似度度量•余弦相似度计算两个向量的夹角•余弦相似度是利用向量长度对内积进行归一化的结果t3t1t2D1D2QtktktkkikiqdqdkikQDCosSim11221)(),(D1=2T1+3T2+5T3CosSim(D1,Q)=5/38=0.81D2=3T1+7T2+T3CosSim(D2,Q)=1/59=0.13Q=0T1+0T2+2T3用余弦计算，D1比D2高6倍；用内积计算，D1比D2高5倍28《信息检索原理》课程Beihang其它相似度度量方法•存在大量的其它相似度度量方法tktkkiktktkkikqdqdqdkik111221)()(JaccardCoefficient:D1=2T1+3T2+5T3Sim(D1,Q)=10/(38+4-10)=10/32=0.312D2=3T1+7T2+T3Sim(D2,Q)=2/(59+4-2)=2/61=0.033Q=0T1+0T2+2T3D1比D2高9.5倍1529《信息检索原理》课程Beihang二值化的相似度度量tktkkiktktkkikqdqdqdkik111221)()(InnerProduct:Cosine:Jaccard:qkdiqkdiqkdi22tktktkkikqdqdkik11221)(qkdiqkditkkikqd1)(qkdidiandqkherearesetsofkeywordsdi和qkherearevector30《信息检索原理》课程Beihang向量空间模型的优点•关键词权重的算法提高了检索的性能•部分匹配的策略使得检索的结果文档集更接近用户的检索需求•可对结果文档进行排序1631《信息检索原理》课程Beihang不足•索引词之间被认为是相互独立的•随着Web页面信息量的增大、Web格式的多样化，这种方法查询的结果往往会与用户真实的需求相差甚远，而且产生的无用信息量会非常大•隐含语义索引模型是向量空间模型的延伸32《信息检索原理》课程Beihang概率模型1733《信息检索原理》课程Beihang背景•概率模型是在布尔逻辑模型的基础上为解决检索中存在的一些不确定性而引入的，试图在概率论的框架下解决信息检索的问题•信息检索系统存在很多的不确定性–比如对某一信息需求，没有一个查询式是唯一的–文档与查询是否“相关”，也即文档是否能满足用户的需求也没有一个明确的定义和判定标准•信息检索的过程具有的不确定性是概率模型应用到信息检索中的重要前提34《信息检索原理》课程Beihang概率模型检索问题即求条件概率问题IfProb(R|di,q)Prob(NR|di,q)thendi是检索结果，否则不是检索结果1835《信息检索原理》课程Beihang检索的理想结果•理想答案集(idealanswers