l53信息获取模型及算法

1、Information Retrieval Model2010年1月1OutlineInformation Retrieval Model Boolean ModelVector Space Model, VSMProbabilistic ModelEvaluation of Information Retrieval ModelData Set for TestingIndices of Evaluation 23信息检索模型四元组D, Q, F, R(qi, dj)D: 文档集的机内表示Q: 用户需求的机内表示F: 文档表示、查询表示和它们之间的关系的模型框架R(qi, dj): quer

2、y qi 和document dj间的relevance计算函数信息检索模型决定于：从什么样的视角去看待查询式和文档基于什么样的理论去看待查询式和文档的关系如何计算查询式和文档之间的相似度4信息检索模型的分类1、基于内容的信息检索模型有集合论模型：布尔模型、模糊集合模型、扩展布尔模型代数模型：向量空间模型、广义向量空间模型、潜在语义标引模型、神经网络模型概率模型：经典概率论模型、推理网络模型、置信（信念）网络模型5结构化模型：非重叠链表模型、临近节点模型浏览型数学模型：平面(Flat)、结构导航(Structure Guided)、超文本(Hypertext)6Non-Overlapping

3、ListsProximal Nodes Structured Models Retrieval: Adhoc Filtering Browsing U s e r T a s k Classic Models boolean vector probabilistic Set Theoretic Fuzzy Extended Boolean Probabilistic Inference Network Belief Network Algebraic Generalized Vector Lat. Semantic Index Neural Networks Browsing Flat Str

4、ucture Guided Hypertext信息检索模型的分类7模型1：布尔检索模型建立在经典的集合论和布尔代数的基础上。遵循两条基本规则: 每个索引词在一篇文档中只有两种状态：出现或不出现，对应0或1。查询是由三种布尔逻辑运算符 and, or, not 连接索引词组成的布尔表达式。优点：简单、易理解、简洁的形式化。缺点：准确匹配，信息需求的能力表达不足。8布尔检索模型首先，将查询转化为一个主析取范式DNF例如：查询为 进一步表达为 即：每一个分量都是三元组 的二值向量9作业3-1：q = 病毒 AND （计算机 OR 电脑）AND NOT医 d1：据报道，计算机病毒近日猖獗d2：小李虽然

5、是学医的，但对研究计算机网络的病毒也很感兴趣，最近他发明了一种新型的杀毒方法，d3：通过计算机程序来发现爱滋病病毒的传播途径，这可能吗？ 哪些文档会被检索出来？10模型2：向量空间模型 向量空间模型(Vector Space Model, VSM) 相比于布尔模型要求的准确匹配, Salton在60年代末提出的VSM模型采用了“部分匹配”的检索策略。通过计算D和Q的similarity作为它们之间的relevance.11向量空间模型 文档表示D文档用词向量表示：词典 =k1,k2,kt构成一个线性空间，d=为此空间内的向量wi称为权值，表示对应词项ki对于表达文档d的重要程度查询表示与D相似

6、q=查询可以是一个文档两个基本问题：如何定义wi和vi？如何计算R(d,q)？12相似度计算R(d,q)用向量内积计算距离R(d,q) = cos(d,q) = dq/|d|q|当使用euclidean normalization时，表示向量夹角余弦，也称为cosine similarity其它的距离函数Jaccard coefficient Jaccard(D1,D2)= w/(N-z) , w是common terms数，N是distinct terms数，z是不在D1,D2中的distinct terms数。13Two Documents Represented in 3-Dimensi

7、onal Term Vector Spacet1t2t3d1d214Vector Space Revisionx = (x1, x2, x3, ., xn) is a vector in an n-dimensional vector spaceLength of x is given by (extension of Pythagorass theorem) |x|2 = x12 + x22 + x32 + . + xn2 If x1 and x2 are vectors:Inner product (or dot product) is given by x1.x2 = x11x21 +

8、x12x22 + x13x23 + . + x1nx2nCosine of the angle between the vectors x1 and x2: cos () = x1.x2 |x1| |x2|15Weighting: Unnormalized Form of Term Frequency (tf)ant bee cat dog eel fox gnu hog length d1 2 1 5d2 1 1 4 1 19d3 1 1 1 1 1 5Weights: tij = frequency that term j occurs in document i documenttext

9、termsd1ant ant bee ant beed2dog bee dog hog dog ant dogant bee dog hogd3cat gnu dog eel fox cat dog eel fox gnu16Example (continued)d1d2d3d1 10.31 0d20.31 10.41d300.41 1Similarity of documents in example:Similarity depends upon the weights given to the terms.17Similarity: Weighting by Unnormalized F

10、orm of Term Frequencyant bee cat dog eel fox gnu hog length q 1 1 2d1 2 1 5d2 1 1 4 1 19d3 1 1 1 1 1 5queryqant dogdocumenttexttermsd1ant ant bee ant beed2dog bee dog hog dog ant dogant bee dog hogd3cat gnu dog eel fox cat dog eel fox gnu18Calculate Rankingd1d2d3q 2/10 5/38 1/10 0.63 0.81 0.32Simila

11、rity of query to documents in example:If the query q is searched against this document set, the ranked results are: d2, d1, d319Choice of Weightsant bee cat dog eel fox gnu hog q ? ? d1 ? ? d2 ? ? ? ? d3 ? ? ? ? ? queryqant dogdocumenttexttermsd1ant ant bee ant beed2dog bee dog hog dog ant dogant be

12、e dog hogd3cat gnu dog eel fox cat dog eel fox gnuWhat weights lead to the best information retrieval?20权值计算Term frequency factorTf (Representation )Document frequency factorIdf (Discrimination)Document length normalization factorEuclidean length normalizationPivoted normalization21Weighting：Term Fr

13、equency (tf)Suppose term j appears fij times in document i. What weighting should be given to a term j?Term Frequency: ConceptA term that appears many times within a document is likely to be more important than a term that appears only once.22Normalized Form of Term Frequency: Free-text DocumentLeng

14、th of documentUnnormalized method is to use fij as the term frequency.but, in free-text documents, terms are likely to appear more often in long documents. Therefore fij should be scaled by some variable related to document length.23Term Frequency: Free-text DocumentA standard method for free-text d

15、ocumentsScale fij relative to the frequency of other terms in the document. This partially corrects for variations in the length of the documents.Let mi = max (fij) i.e., mi is the maximum frequency of any term in document i.Term frequency (tf):tfij = fij / mi Note: There is no special justification

16、 for taking this form of term frequency except that it works well in practice and is easy to calculate.i24Weighting: Inverse Document Frequency (idf)Suppose term j appears fij times in document i. What weighting should be given to a term j ?Inverse Document Frequency: ConceptBy Zipfs Law we know tha

17、t some terms appear much more often than others across the documents of a corpus.A term that occurs in only a few documents is likely to be a better discriminator that a term that appears in most or all documents.25Inverse Document FrequencySuppose there are n documents and that the number of docume

18、nts in which term j occurs is nj.Simple methodWe could define document frequency as nj/n.A possible method might be to use the inverse, n/nj, as a weight. This would give greater weight to words that appear in fewer documents.26Inverse Document FrequencyA standard methodThe simple method over-emphas

19、izes small differences. Therefore use a logarithm. Inverse document frequency (idf):idfj = log2 (n/nj) + 1 nj 0Note: There is no special justification for taking this form of inverse document frequency except that it works well in practice and is easy to calculate.27Example of Inverse Document Frequ

20、encyExamplen = 1,000 documentsterm jnj n/njidfj A10010.004.32 B5002.002.00 C9001.111.13 D1,0001.001.00From: Salton and McGill28Full Weighting: A Standard Form of tf.idfPractical experience has demonstrated that weights of the following form perform well in a wide variety of circumstances:(weight of

21、term j in document i) = (term frequency) * (inverse document frequency)A standard tf.idf weighting scheme, for free text documents, is:tij = tfij * idfj = (fij / mi) * (log2 (n/nj) + 1) when nj 029Vector Similarity Computation with WeightsDocuments in a collection are assigned terms from a set of n

22、termsThe term vector space W is defined as: if term k does not occur in document di, wik = 0 if term k occurs in document di, wik is greater than zero (wik is called the weight of term k in document di)Similarity between di and dj is defined as: wikwjk |di| |dj|Where di and dj are the corresponding

23、weighted term vectorsk=1ncos(di, dj) =30Discussion of Similarity The choice of similarity measure is widely used and works well on a wide range of documents, but has no theoretical basis.There are several possible measures other that angle between vectorsThere is a choice of possible definitions of

24、tf and idfWith fielded searching, there are various ways to adjust the weight given to each field.31作业3-2：Suppose your document collection only contains 2 documents:Q = (heart attack medicine)D1= (cardiac arrest prevention medicine nitroglycerine heart disease)D2= (terrorist attack explosive semtex

25、attack nitroglycerine proximity fuse) 试写出有关的向量，为简单起见，用单词出现次数作为权值。32模型3：概率模型 1976年由Roberston和Sparck Jones提出的经典概率模型。在概率的框架下解决IR的问题。给定一个用户查询，存在一个文档集合，该集合只包括与查询完全相关的文档而不包括其他不相关的文档，称该集合为理想结果集合。 如何描述这个理想结果集合？即：该理想结果集合具有什么样的属性？33PRP (probability ranking principle)将信息获取看成是一个过程：用户提交一个查询，系统提供给用户它所认为的相关结果列表；用户

26、考察这个集合后给出一些辅助信息，系统再进一步根据这辅助信息（加上以前的信息）得到一个新的相关结果列表；如此继续。如果每次结果列表中的元素总是按照和查询相关的概率递减排序的话，则系统的整体效果会最好。其中概率的计算应该是基于当时所能得到的所有信息。34概率模型-相关概念贝叶斯定理：词条的独立假设：P(AB)= P(A) P(B) 当且仅当 A与B相互独立由此对一篇文档而言，若文档中的各个索引词相互独立，则有 P(dj)=P(k1)P(kt)35概率模型 定义：设索引词的权重为二值的，即： R表示已知的相关文档集（或最初的猜测集），用 表示R的补集。 表示文档dj与查询q相关的概率， 表示文档dj

27、与查询q不相关的概率。文档dj与查询q的相关性判别函数sim(dj, q)可以定义为：36概率模型 根据贝叶斯定理有37概率模型 假设标引词独立，则这是概率模型中排序计算的主要表达式。38概率模型 取对数，在相同背景下，忽略对所有因子保持恒定不变的因子，则有39概率模型 如何计算上式中的 和 呢 ？ 简单假设作为最初的猜测1） 对所有的索引词ki是恒定不变的，通常取为0.5，即 2). 不相关文档中的索引词ki的分布可以通过文档集中索引词的分布来估计，即其中，ni表示包含索引词ki的文档数， N表示集合中的文档总数。初始值确定后，根据与查询q相关的大小进行初步排序，取前若干个文档作为相关查询集

28、合。之后通过如下方法进行改进(即开始递归计算)。40概率模型 用V表示概率模型初步检出并经过排序的文档子集 Vi表示V中包含索引词ki的文档数。改进 和 的过程如下：1）用已经检出的文档中索引词ki的分布来估计 2). 假定所有未检出的文档都是不相关的来估计 如此递归重复这一过程，得到理想结果集合 41概率模型对较小的V和Vi上述计算会出现问题，如V=1和Vi=0，可做一些改进：调整因子也可以为ni/N， 即42概率模型该方法的缺点:不考虑索引词在文档中出现的频率,所有权值都是二元的.索引词之间相互独立的假设。43作业3-3:推导概率模型公式，从到44OutlineInformation Re

29、trieval Model Boolean ModelVector Space Model, VSMProbabilistic ModelEvaluation of Information Retrieval ModelData Set for TestingIndices of Evaluation 45检索性能的评估 系统评价主要包括功能评价，即评价一个系统是否完成了它所侧重的目标。性能评价，主要指标是时间与空间的开销。（如：对数据检索系统的评价）信息检索系统：由于用户的查询请求本身具有模糊性，检出的结果不一定是精确答案。需要依照与查询的相关度，对结果集合的准确度进行评价。其性能评价还包括

30、检索效果的评价。 46检索性能评估评估的类型实验室评估和真实环境评估，两者不同。有时，结果出入也较大。由于在实验室封闭环境下的评估具有可重复性，目前仍是主流。 还有对交互查询进行评测，需要考查界面的设计、系统引导、会话持续时间等因素。47评估指标-查全率和查准率对某个测试参考集,信息查询实例为I，I对应的相关文档集合为R。假设用某个检索策略对I进行处理后，得到一个结果集合A。令Ra表示R与A的交集。 Ra 查全率(Recall)：检出的相关文档个数与相关文档集合总数的比值，即R=|Ra| / |R|查准率(Precision)：检出的相关文档个数 与检出文档总数的比值，即P=|Ra| / |A

31、|RA48平均精度对recall增加时对应的精度求平均值和“原始定义”的区别？这样的“平均精度”有什么不好？49“针对11点标准召回率的精度”人们建议在一些特殊的点上给出Re和Pr的关系Re=0%, 10%, , 100%，对应的Pr于是就能很方便地讲“召回率为20%的时候精度为X”之类的结论也还有“3点标准”的说法：25%, 50%, 75%如果D中相关文档的个数是10的倍数，且如果算法给出的“Ranked A”包含了所有相关文档，得到这些点就会很简单；否则要考虑如何插值的问题50“省事的”例子D=d1,d1000，对查询q，所有相关文档集合（共10个元素）：Rq = d3, d5, d9,

32、 d25, d39, d44, d56, d71, d89, d123查询的返回结果序：d123*，d84，d56*，d6，d8，d9*，d511，d5*，d39*，d129，d187，d25*，d38，d44*，d57，d71*，d48，d250，d113，d3*，d200，d144，d11，d89*，d1Ranking: * * * * * * * * * * Recall: .1 .1 .2 .2 .2 .3 .3 .4 .5 .5 .5 .6 .6 .7 .7 .8 .8 .8 .8 .9 .9 .9 .9 1 1Precisio: 1 .5 .67 .5 .4 .5 .43 .5 .

33、55 .5 .45 .5 .46 .5 .46 .5 .47 .5 .42 .45 .43 .41 .39 .42 .45111 standard recall level其实只有10个点？52但实际上经常不是这样得到的结果集合不包含所有的相关元素实践上常常只是返回排序较高的若干元素因此不能得到需要的recall值D中相关元素的个数不是10的倍数于是能直接得到的recall值不一定包含0%, 10%, 20%, 30%, , 100%53插值（interpolation）目标是在11个标准召回率上都有精度值可以想出各种“合理的”方法（例如将已知的点连起来），不同的方法结果会不一样（因此做比较时

34、要讲清楚）P(rj) = max P(r), rj rrj+1取在下一个标准召回率之间的已知召回率对应的最大精度值P(rj) = max P(r), rj r取往后的已知召回率对应的最大的精度值（这得到的是阶梯函数，单调性。如何考虑返回的结果不包括所有相关文档？54例子所有相关文档集合（共10个元素）：Rq = d3, d5, d9, d25, d39, d44, d56, d71, d89, d123只能得到5个有效的recall值：10%，20%，30%，40%，50%Ranking for query q:d123*d84d56*d6d8d9*d511d129d187d25*d38d48

35、d250d113d3*55Example第15个结果处,查全率Recall=5/10， 查准率 Precision=5/15。还可以看到：对应查全率为10%时的查准率为100%；对应查全率为20%时的查准率为66%；。对应查全率为60%时的查准率降为0。图示如下56Ranking for query q:d123*d84d56*d6d8d9*d511d129d187d25*d38d48d250d113d3*57由于每个查询的查全率值不一定就是这11个标准查全率，因此需要对查准率进行插补。如上例中，若Rq只含有3个文档 Rq = d3, d56, d129. 此时，如何计算11点标准查全率呢？设

36、rjj=0,1,2,10为第j个标准查全率的一个参量 （如r3是查全率为30%的参量），则：即第j个标准查全率水平的查准率是介于第j个和第j+1个查全率之间任意一个查全率所对应的查准率的最大值。58 Rq = d3, d56, d129 Ranking for query q:d123*d84d56*d6d8d9*d511d129d187d25*d38d48d250d113d3*59总体情况多个查询下的查准率/查全率曲线，可通过计算其平均查准率得到，公式如下(Nq为查询的数量)ri取标准召回率，Nq是所考察Q的大小。这样得到一个技术（算法）在（Q，D）上精度的宏观表现60F指数用一个量来表示p

37、recision和recall的综合效果How？人们定义：为什么不是：61A(P,R)和H(P,R)并不一致例如：P1=0.1, R1=0.83: A(P1,R1)=0.42, H(P1,R1)=0.197; P2=0.3, R2=0.3: A(P2,R2)=0.3, H(P2,R2)=0.3也就是说，A(P1,R1)A(P2,R2)，但H(P1,R1)H(P2,R2)（当然也可以举出它们一致的例子）62调和平均数特性在P+R一定的情况下，希望它们接近。换句话说，这个指标不掩盖P, R一个方面特别的不足63多个查询下进行检索算法的比较对多个查询，进行平均，有时该曲线也称为：查准率/查全率的值。

38、如下为两个检索算法在多个查询下的查准率/查全率的值。第一个检索算法在低查全率下，其查准率较高。另一个检索算法在高查全率下，其查准率较高64基于P, R, F的评估小结给定包含一个新算法的IR系统（测试），一个测试文档集合D，一个查询集合Q=q一个事先确定的相关集合的集合G(Q)我们确定这个算法的P-R图和F值65流程对于Q的每一个元素q：得到一个有序结果集s(q)=与G(q)对比，依序计算s(q)中元素的ri和pi，i=1,2,q选择一种合适的插值方式，得到pi在r=0,.1,.2,.3,.4,.5,.6,.7,.8,.9,1处的插值如果rq1，则令它其后的标准点上的p=0对Q的所有元素，在标

39、准召回点上求p的平均值给出平均值的统计表和P-R图6667还要算F: 得出一个数对每一个查询q，得到标准召回点上的F，即Fq(i)=2*pi*r(i)/(p(i)+r(i), i=0,.1,.2,.3,.4,.5,.6,.7,.8,.9,1在查询内求平均（micro-average）Fq=Fq(i),i=0,.1,.2,.9,1进一步在查询间求平均（macro-average）F=Fq, qQ68困难与不适有可能D和Q太大，得出相关结果集合R代价太高“相关”的含义因人而异如此定义的P,R,F适于“批处理”评估，没有体现交互式信息检索过程（现代IR系统的典型特征）如此定义的P,R,F依赖于返回结

40、果的线性序，但有些系统不一定有这样的序什么是评估搜索引擎排序算法最好的方法（如果你没有搜索引擎的话）？69小 结信息检索模型VSM 向量空间模型概率模型信息检索系统评估测试集评估指标P,R,F70Thank You!71测试集 为了对不同的检索系统进行比较，需要建立检索系统性能评价的试验平台与基准测试，推动信息检索技术的发展。TRECText REtrieval Conference，文本检索会议一开始仅仅面向文本，现在处理对象更广情报分析和处理组织者NIST(National Institute of Standards and Technology)，政府部门DARPA(Defense Advanced Research Projects Agency)，军方会议情况评测会议199