信息检索模型高教知识

信息检索模型计算机学院信息检索研究室秦兵1全面分析这一部分将讲述n布尔模型，向量空间模型，扩展的布尔模型n概率模型和基于语言模型的信息检索模型的区别和联系n基于本体的信息检索模型和基于隐性语义索引的信息检索模型2全面分析信息检索模型的概述3全面分析什么是模型？n模型是采用数学工具，对现实世界某种事物或某种运动的抽象描述n面对相同的输入，模型的输出应能够无限地逼近现实世界的输出n举例：天气的预测模型n信息检索模型n是表示文档，用户查询以及查询与文档的关系的框架4全面分析信息检索模型n信息检索模型是一个四元组D, Q, F, R(qi, dj)nD: 文档集的机内表示nQ: 用户需求的机内表示nF: 文档表示、查询表示和它们之间的关系的模型框 架(Frame)nR(qi, dj): 排序函数，给query qi 和document dj评分n信息检索模型取决于：n从什么样的视角去看待查询式和文档n基于什么样的理论去看待查询式和文档的关系n如何计算查询式和文档之间的相似度5全面分析模型分类信息检索模型布尔向量空间概率知识模糊集扩展的布尔模型集合论代数扩展的向量空间隐性语义索引神经网络语言模型推理网络信念网络概率基于本体论的模型人工智能6全面分析布尔模型(Boolean Model)7全面分析布尔模型n最早的IR模型，也是应用最广泛的模型n目前仍然应用于商业系统中nLucene是基于布尔（Boolean）模型的8全面分析布尔模型描述n文档D表示n一个文档被表示为关键词的集合n查询式Q表示n查询式(Queries)被表示为关键词的布尔组合，用“与、或、非”连接起来，并用括弧指示优先次序n匹配Fn一个文档当且仅当它能够满足布尔查询式时，才将其检索出来n检索策略基于二值判定标准n算法Rn根据匹配框架F判定相关9全面分析举例nQ=病毒AND（计算机OR电脑）ANDNOT医n文档：D1:据报道计算机病毒最近猖獗D2：小王虽然是学医的，但对研究电脑病毒也感兴趣D3：计算机程序发现了艾滋病病毒传播途径n上述文档哪一个会被检索到？10全面分析查询表示n在布尔模型中， 所有索引项的权值变量和文档dj与查询q的相关度都是二值的 n查询q被表述成一个常规的布尔表达式，为方便计算查询q和文档d的相关度，一般将查询q的布尔表达式转换成析取范式qDNF 11全面分析示例n文档集包含两个文档：文档1：a b c f g h文档2：a f b x y z 用户查询：文档中出现a或者b，但一定要出现z。n将查询表示为布尔表达式 ,并转换成析取范式n文档1和文档2的三元组对应值分别为(1,1,0)和(1,1,1) n经过匹配 ,将文档2返回()qabz(1,0,1)(0,1,1)(1,1,1)DNFq12全面分析优点n到目前为止，布尔模型是最常用的检索模型，因为：n由于查询简单，因此容易理解n通过使用复杂的布尔表达式，可以很方便地控制查询结果n相当有效的实现方法n相当于识别包含了一个某个特定term的文档n经过某种训练的用户可以容易地写出布尔查询式n布尔模型可以通过扩展来包含排序的功能，即“扩展的布尔模型”13全面分析问题n布尔模型被认为是功能最弱的方式，其主要问题在于不支持部分匹配，而完全匹配会导致太多或者太少的结果文档被返回n非常刚性: “与”意味着全部; “或”意味着任何一个n很难控制被检索的文档数量n原则上讲，所有被匹配的文档都将被返回n很难对输出进行排序n不考虑索引词的权重，所有文档都以相同的方式和查询相匹配n很难进行自动的相关反馈n如果一篇文档被用户确认为相关或者不相关，怎样相应地修改查询式呢？14全面分析向量空间模型15全面分析模型的提出nSalton在上世纪60年代提出的向量空间模型进行特征表达n成功应用于SMART（ System for the Manipulation and Retrieval of Text）文本检索系统n这一系统理论框架到现在仍然是信息检索技术研究的基础16全面分析模型的描述n文档D(Document)：泛指文档或文档中的一个片段（如文档中的标题、摘要、正文等）。n索引项t（Term）：指出现在文档中能够代表文档性质的基本语言单位（如字、词等），也就是通常所指的检索词，这样一个文档D就可以表示为D(t1,t2,tn)，其中n就代表了检索字的数量。n 特征项权重Wk（Term Weight）：指特征项tn能够代表文档D能力的大小，体现了特征项在文档中的重要程度。n 相似度S（Similarity）：指两个文档内容相关程度的大小17全面分析模型的特点n基于关键词(一个文本由一个关键词列表组成)n根据关键词的出现频率计算相似度n例如：文档的统计特性n用户规定一个词项(term)集合，可以给每个词项附加权重n未加权的词项: Q = database; text; information n加权的词项: Q = database 0.5; text 0.8; information 0.2 n查询式中没有布尔条件n根据相似度对输出结果进行排序n支持自动的相关反馈n有用的词项被添加到原始的查询式中n例如：Q database; text; information; document 18全面分析模型中的问题n怎样确定文档中哪些词是重要的词？（索引项）n怎样确定一个词在某个文档中或在整个文档集中的重要程度？（权重）n怎样确定一个文档和一个查询式之间的相似度？19全面分析索引项的选择n若干独立的词项被选作索引项(index terms) or 词表vocabularyn索引项代表了一个应用中的重要词项n计算机科学图书馆中的索引项应该是哪些呢?体系结构总线计算机数据库.XML计算机科学文档集文档集中的索引项20全面分析索引项的选择n这些索引项是不相关的 (或者说是正交的) ，形成一个向量空间vector spacen实际上，这些词项是相互关联的n当你在一个文档中看到 “计算机”, 非常有可能同时看到“科学”n当你在一个文档中看到 “计算机”, 有中等的可能性同时看到 “商务”n当你在一个文档中看到“商务”，只有很少的机会同时看到“科学”“计算机” “科学” “商务”计算机科学文档集该文档集中的全部重要词项21全面分析词项的权重n根据词项在文档(tf)和文档集(idf)中的频率(frequency)计算词项的权重ntfij = 词项j在文档i中的频率ndf j = 词项j的文档频率= 包含词项j的文档数量nidfj = 词项j的反文档频率= log2 (N/ df j) nN: 文档集中文档总数n反文档频率用词项区别文档22全面分析Idf 计算示例23全面分析文档的词项权重(TFIDF举例)n文本：“俄罗斯频繁发生恐怖事件，俄罗斯的安全部门加大打击恐怖主义的力度。”TF IDFTFIDFTFIDFTFIDF俄罗斯2较高高安全 1中等高恐怖2较高高部门 1较低低的2非常低 很低加大 1较低低频繁1较低低打击 1中等高发生1较低低主义 1较低低事件1较低低力度 1中等高24全面分析查询式的词项权重n如果词项出现在查询式中，则该词项在查询式中的权重为1，否则为0n也可以用用户指定查询式中词项的权重n一个自然语言查询式可以被看成一个文档n查询式：“有没有周杰伦的歌？” 会被转换为:n查询式： “请帮我找关于俄罗斯和车臣之间的战争以及车臣恐怖主义首脑的资料” 会被转换为: n过滤掉了：“请帮我找”，“和”，“之间的”，“以及”，“的资料”n两个文档之间的相似度可以同理计算25全面分析由索引项构成向量空间n2个索引项构成一个二维空间，一个文档可能包含0, 1 或2个索引项ndi = 0, 0 (一个索引项也不包含)ndj = 0, 0.7 (包含其中一个索引项)ndk = 1, 2 (包含两个索引项)n类似的，3个索引项构成一个三维空间，n个索引项构成n维空间n一个文档或查询式可以表示为n个元素的线性组合26全面分析文档集 一般表示n向量空间中的N个文档可以用一个矩阵表示n矩阵中的一个元素对应于文档中一个词项的权重。“0”意味着该词项在文档中没有意义，或该词项不在文档中出现。 T1 T2 . TtD1 d11 d12 d1tD2 d21 d22 d2t : : : : : : : :Dn dn1 dn2 dnt27全面分析图示举例:D1 = 2T1 + 3T2 + 5T3D2 = 3T1 + 7T2 + T3Q = 0T1 + 0T2 + 2T3T3T1T2D1 = 2T1+ 3T2 + 5T3D2 = 3T1 + 7T2 + T3Q = 0T1 + 0T2 + 2T37325 D1比D2更接近Q吗？ 怎样衡量相似程度？夹角还是投影28全面分析相似度计算n相似度是一个函数，它给出两个向量之间的相似程度，查询式和文档都是向量，各类相似度存在于：n两个文档之间（文本分类，聚类）n两个查询式之间（常问问题集）n一个查询式和一个文档之间（检索）n人们曾提出大量的相似度计算方法，因为最佳的相似度计算方法并不存在。29全面分析通过计算查询式和文档之间的相似度n可以根据预定的重要程度对检索出来的文档进行排序n可以通过强制设定某个阈值，控制被检索出来的文档的数量n检索结果可以被用于相关反馈中，以便对原始的查询式进行修正。 (例如：将文档向量和查询式向量进行结合) 30全面分析相似度度量 内积(Inner Product)n文档D 和查询式Q 可以通过内积进行计算:sim ( D , Q ) = (dik qk)ndik 是文档di中的词项k 的权重，qk 是查询式Q中词项k的权重n对于二值向量, 内积是查询式中的词项和文档中的词项相互匹配的数量n对于加权向量, 内积是查询式和文档中相互匹配的词项的权重乘积之和kt131全面分析内积 举例n二值（Binary）:nD = 1, 1, 1, 0, 1, 1, 0nQ = 1, 0 , 1, 0, 0, 1, 1nsim(D, Q) = 3retrievaldatabasearchitecturecomputertextmanagementinformationn向量的大小 = 词表的大小 = 7n0 意味着某个词项没有在文档中出现，或者没有在查询式中出现n加权 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 = 232全面分析内积的特点n内积值没有界限n不象概率值，要在(0,1)之间n对长文档有利n内积用于衡量有多少词项匹配成功，而不计算有多少词项匹配失败n长文档包含大量独立词项，每个词项均多次出现，因此一般而言，和查询式中的词项匹配成功的可能性就会比短文档大。33全面分析余弦(Cosine)相似度度量n余弦相似度计算两个向量的夹角n余弦相似度是利用向量长度对内积进行归一化的结果2t3t1t2D1D2Q1CosSim(Di, Q) =tktktkkikqdqdkik11221)(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倍34全面分析其它相似度度量方法n存在大量的其它相似度度量方法tktkkiktktkkikqdqdqdkik111221)()(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 + 2T3nD1 比 D2 高9.5倍35全面分析示例36全面分析二值化的相似度度量tktkkiktktkkikqdqdqdkik111221)()(Inner Product:Cosine:Jaccard :qkdiqkdiqkditktktkkikqdqdkik11221)(qkdiqkditkkikqd1)(qkdidi and qk here are sets of keywordsdi 和 qk here are vector37全面分析向量空间优点n术语权重的算法提高了检索的性能 n部分匹配的策略使得检索的结果文档集更接近用户的检索需求n可以根据结果文档对于查询串的相关度通过Cosine Ranking等公式对结果文档进行排序38全面分析不足n标引词之间被认为是相互独立n随着Web页面信息量的增大、Web格式的多样化，这种方法查询的结果往往会与用户真实的需求相差甚远，而且产生的无用信息量会非常大n隐含语义索引模型是向量空间模型的延伸39全面分析扩展的布尔模型40全面分析布尔检索示例“飞碟”AND “小说”：只能检索出D4，无法显现D1,D2,D3的差异“飞碟”OR “小说”：可以检出D1,D2,D4，但无法显现它们的差异41全面分析布尔模型和向量空间模型相结合n布尔模型可以和向量空间模型相结合，先做布尔过滤，然后进行排序：n首先进行布尔查询n将全部满足布尔查询的文档汇集成一个文档n用向量空间法对布尔检索结果进行排序布尔过滤排序文档向量空间表示的查询式结果布尔查询式如果忽略布尔关系的话，向量空间查询式和布尔查询式是相同的42全面分析先“布尔”，后“排序”存在的问题n如果 “与” 应用于布尔查询式, 结果集可能太窄,因而影响了后面的排序过程n如果 “或” 应用于布尔查询式, 就和纯向量空间模型没有区别了n在第一步，如何最佳地应用布尔模型呢？n提出扩展布尔模型43全面分析扩展布尔模型中的“或”关系n给定一个或关系的查询式：x yn假设文档di中x和y的权重被归一化在(0,1)区间内:nwx,j = （tfx,j / maxl tfl,j ） （idfx / maxi idfi）nsim(qor, dj) = (x2 + y2)/2 0.5 where x = wx,j and y = wy,j (1,1)wx,jwy,j(1,0)(0,1)(0,0)最不期望的点dx yn 一个文档在(1,1)处获得最高的权重，此时意味着文档包含了全部两个查询词，并且查询词在文档中的权重也是最高的n 函数sim()度量了从原点出发的文档向量长度44全面分析扩展布尔模型中的“与”关系n给定一个联合的查询式 x ynsim(qand, dj) = 1 (1 x)2 + (1 y)2 /2 0.5n函数sim() 表示从(1,1) 出发到d的向量长度(1,1)wx,jwy,j(1,0)(0,1)(0,0)最期望的点dx y45全面分析扩展的布尔检索相似度计算示例46全面分析观察n如果权值是布尔型的，x出现在文档dj中，则x在文档dj中具有权重1，否则为0n当dj 包含x和y时sim(qand, dj) = sim(qor, dj) = 1n当dj 既不包含x 也不包含y时sim(qand, dj) = sim(qor, dj) = 0n当dj 包含x 和y二者之一时sim(qand, dj) = 1 1/20.5 = 0.293sim(qor, dj) = 1/20.5 = 0.707(1,1)wx,jwy,j(1,0)(0,1)(0,0)47全面分析观察n一个词项的存在将对“或”关系查询式提供0.707的增益值，但对“与”关系查询式仅提供0.293的增益值n一个词项不存在，将给“与”关系的查询式提供0.707的罚分n当x 和y 有权值0.5, sim(qand, d) = sim(qor, d) = 0.5n在一个“与”关系查询中，两个词项的权重均为0.5，则相似度为0.5。其中一个权重为1，另一个为0，相似度为0.293。n在“或关系”查询中，情况恰好相反n在“与关系”查询中，如果一个词项的权重低于0.5，将给相似度贡献一个较大的罚分48全面分析p-norm 模型n扩展布尔模型可以被泛化为m 个查询项:sim(qor, d) = (x12 + x22 + . + xm2 ) / m 0.5sim(qand, d) = 1 (1 x1)2 + (1 x2)2 + . + (1 xm)2 / m 0.5n它可以被进一步地 泛化为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/pn当p = 1时, sim(qor, d) = sim(qand, d) = (x1 + x2 + . + xm )/ mn通过语词-文献权值的和来求合取和析取查询的值，和向量空间中的内积相似n当p = , sim(qor, d) = max(xi); sim(qand, d) = min(xi)n模糊逻辑模型(Fuzzy logic model)49全面分析概率模型50全面分析背景n概率模型是在布尔逻辑模型的基础上为解决检索中存在的一些不确定性而引入的，试图在概率论的框架下解决信息检索的问题n信息检索系统内在存在很多的不确定性n比如对某一信息需求既没有一个查询式是唯一的n文档与查询是否“相关”也即文档是否能满足用户的需求也没有一个明确的定义和判定标准n信息检索的过程具有的不确定性是概率模型应用到信息检索中的重要前提51全面分析 概率模型检索问题即求条件概率问题If Prob(R|di, q) Prob(NR|di, q) then di是检索结果，否则不是检索结果52全面分析检索的理想结果n理想答案集(ideal answer set)n给定一个用户的查询串，相对于该串存在一个包含所有相关文档的集合n我们把这样的集合看作是一个理想的结果文档集n信息检索的过程可以被看成是描述理想文档集的过程n用索引项刻画理想答案集的属性n把查询处理看作是对理想结果文档集属性的处理n我们并不能确切地知道这些属性，我们所知道的是用索引词的语义来刻画这些属性 53全面分析实际采取的策略n初始估计n由于在查询期间这些属性都是不可见的，这就需要在初始阶段来估计这些属性。n这种初始阶段的估计允许我们对首次检索的文档集合返回理想的结果集，并产生一个初步的概率描述。n相关反馈(relevance feedback)n为了提高理想结果集的描述概率，系统需要与用户进行交互式操作，具体处理过程如下：n用户大致浏览一下结果文档，决定哪些是相关的，哪些是不相关的；n然后系统利用该信息重新定义理想结果集的概率描述；n重复以上操作，就会越来越接近真正的结果文档集。54全面分析概率模型的理论n概率模型是基于以下基本假设：n文档 对一个查询式 的相关性与文档集合中的其他文档是没有关系的，这点被称为概率模型的相关性独立原则；n文档和查询式中索引词与索引词之间是相互独立的；n文档和查询中的索引词权重都是二元的；n 文档相关性是二值的,即只有相关和不相关两种，也就是说，一篇文档要么属于理想文档集，要么不属于理想文档集。n正是由于这些假设，概率模型也被称为二值独立检索模型（Binary Independent Retrivel，BIR）。55全面分析查询式与文档的相关度概率定义n在概率模型中索引术语的权重都是二值的 nwi,j0,1, wi,q0,1, n查询式q是索引词项集合的子集n设R是相关文档集合（初始的猜测集合）， 是R的补集（非相关文档的集合）n 表示文档dj和查询式q相关的概率；n 表示文档dj和查询式q不相关的概率；R(|)jP R d(|)jP R d56全面分析查询式与文档的相关度概率定义n文档dj对于查询串q的相关度值定义为：文档与查询相关的概率和文档与查询不相关概率的比值n根据贝叶斯原理其中： 代表从相关文档集合R中随机选取 文档dj的概率，P(R)表示从整个集合中随机选取一篇文档作为相关文档的概率，依此定义 和 (, )(|)/(|)jjjSim dqP R dP R d (, )(|) ( )/(|) ( )jjjSim dqP dR P RP dR P R (|)jP dR (|)jP dR ( )P R57全面分析推导nP（R）和 表示从整个文档集合中随机选取一篇文档是否和查询相关先验概率，而对于一个确定的文档集来说，这两个先验概率仅与查询有关，而与具体的每篇文档无关，进一步简化可得n假设索引术语是相互独立的则： (, )(|)/(|)jjjSim dqP dRP dR () 1() 0() 1() 0(|) (|)(, )(|) (|)ijijijijiigdgdjiigdgdP kRP kRSim dqP kRP kR( )P R58全面分析最终的概率模型排序公式n 表示集合R中随机选取的文档中出现索引术语ki的概率， 表示集合R中随机选取的文档中不出现索引术语的概率，则有： n类似定义 和 ，在相同查询背景下，忽略对所有文献保持不变的因子，最终得到： 这是概率模型主要的排序公式( | )iP k R(|)iP kR(|)(|)1iiP kRP kR(| )iP k R(|)iP kR,1(|)1(|)(, )(log)log1(|)(|)tiiji qi jiiip kRp kRsim dqwwp kRp kR59全面分析初始化方法n由于我们在开始时并不知道集合R，因此必须 设计一个初始化计算 和 的算法。n在查询的开始间段只定义了查询串，还没有得到结果文档集。我们不得不作一些简单的假设，n假定P(ki|R)对所有的索引术语来说是常数（一般等于0.5）n假定索引术语在非相关文档中的分布可以由索引术语在集合中所有文档中的分布来近似表示。P(ki|R)=0.5=ni/Nni表示出现索引术语ki的文档的数目，N是集合中总的文档的数目。( | )iPk R(|)iP kR(|)iP kR60全面分析改进nV表示用概率模型初步检出的经过排序的子集，Vi为包含ki的V的一个子集。为了改善概率排序，需要对上述初始化公式改进：n通过迄今已检出的文献中标引词ki的分布来估计 n通过假定所有未检出的文献都是不相关的来估计n这一过程可以递归重复 (|)iiinVP kRNV(|)/iiP kRVV( | )iP k R(|)iP kR61全面分析概率模型小结n优点n文档可以按照他们相关概率递减的顺序来排序。n缺点n开始时需要猜想把文档分为相关和不相关的两个集合，一般来说很难n实际上这种模型没有考虑索引术语在文档中的频率（因为所有的权重都是二值的）n假设标引词独立n概率模型是否要比向量模型好还存在着争论，但现在向量模型使用的比较广泛。62全面分析基于统计语言模型的信息检索模型63全面分析统计语言模型n统计语言模型在语音识别中产生nargmax p(s|a)，s是文字串，a是声学参数串nargmax p(s|a)=argmax p(a|s)p(s)/p(a)n忽略p(a)，p(a|s)是声学模型np(s)是语言模型np(s)=p(w1,w2,w3,wn)=i=1n p(wi|hi)nn表示句子长度nhi=w1,w2,wi-1，代表上下文64全面分析从文档中建立语言模型n原始文本n He can buy you the can of soda n一元模型(Unigram): (8 words in vocabulary)np1(He) = p1(buy) = p1 (you) = p1 (the) = p1(of) = p1(soda)= .125, p1(can) = .25n二元模型(Bigram):np2(He|) = 1, p2(can|He) = 1, p2(buy|can) = .5, p2(of|can) = .5, p2(you |buy) = 1,.n 三元模型(Trigram):np3(He|,) = 1, p3(can|,He) = 1, p3(buy|He,can) = 1, p3(of|the,can)= 1, ., p3(|of,soda) = 1. 65全面分析举例智能拼音输入问题nyi zhi xiao hua mao一 之 小 华 毛以 只 校 话 贸异 之 销 化 猫已 枝 花 值 n基于大规模语料库建立的语言模型应该能够告诉我们：np(“一只小花猫”)p(“一枝小花猫”)p(任何其它候选字串)66全面分析语言模型和搜索引擎的相似性n利用搜索引擎查找一个词串的过程很象在建立语言模型时统计N-gram出现频度的过程n相同的数据稀疏问题n如果在Google中输入的查询式太长，则很难找到满意的结果n原因：如果查询式包括8个词，索引表中有10万词，则1000008=1040，目前互联网的字节数在T级，也就是1012，因此输入太长的查询式无法找到结果，因为数据稀疏n在建立语言模型时同样存在严重的数据稀疏问题67全面分析数据稀疏示例例：假设训练语料只有三句话：1）小明阅读报纸。2）小红阅读图书。3）小刚拿图书换鸡蛋。 需要估计“小明阅读图书”这个句子的概率。以表示句子的开始和结束。根据bigram语言模型，可以得到：n 083. 02121131)|BOS()|()|()BOS|()(图书阅读图书小明阅读小明小明阅读图书PPPPP68全面分析数据稀疏示例n然而，如果估计句子“小明拿报纸换鸡蛋”的概率，因为：n所以最终显然会得到： n很显然，这样的估计结果是不准确的，因为“小明拿报纸换鸡蛋”这个句子不仅在语法上是一个合法的句子，而且由人来判断，这也是一个有着合法语义的句子，它是会在现实中出现的句子。n解决方案：平滑技术0)|(小明拿P0)(小明拿报纸换鸡蛋P69全面分析简单的平滑-Laplace法则n这个概率比刚才的0.083小了很多，但是也合理了很多n尽管这个概率非常小，但是这远比零概率合理多了。iiwiiiiwiiiiiiwwcVwwcwwcwwcwwP)(|)(1)(1 ()(1)|(1111148 . 2132132122142)|BOS()|()|()BOS|()(ePPPPP图书阅读图书小明阅读小明小明阅读图书62.5122122121211111142|BOS()|()|()|()|()BOS|()(ePPPPPPP鸡蛋）换鸡蛋报纸换拿报纸小明拿小明小明拿报纸换鸡蛋70全面分析基于语言模型的IR模型的概念n文档语言模型n每个文档对应一个统计语言模型，称为文档的语言模型(Language Model)。n它主要描述了该文档中各个单词的统计分布特征。n因此每个文档看作是由其语言模型抽样产生的一个样本。n基于文档语言模型计算查询式的出现概率n一个查询式也可以看作是由文档的语言模型抽样产生的一个样本。n因此可以根据每个文档的语言模型抽样生成检索的概率来对其排序，其概率值越大，则该文档就越满足该检索要求。71全面分析举例n假设文档集合中只有1和2两个文本n文本1产生的语言模型1np1(a)=0.25, p1(b)=0.5, p1()=1/64, c.r ,剩下的s,t,u,v,w,x,y,z均为0n文本2产生的语言模型2np2(a)=0.7, p2(b)=0.05, p2()=1/64, c.r ,剩下的s,t,u,v,w,x,y,z均为0n查询式：q=abacaadnp1(q)=0.25*0.5*0.25*1/64*0.25*0.25*1/644.8*10-7np2(q)=0.7*0.05*0.7*1/64*0.7*0.7*1/642.9*10-672全面分析例子中的检索结果n从上例中可以看出nq在语言模型1下获得了较低的概率4.8*10-7nq在语言模型2下获得了较高的概率2.9*10-6n说明n文本2比文本1更有可能生成qn若输入q，应该检索出文本2，而不是文本173全面分析和传统概率模型的比较n基本思想完全不同n传统的信息检索概率模型n文档d与检索q的相关度排序函数定义为事件R(文档是否满足检索要求)的概率，即：f(q,d)=P(R|d) ；n相关度排序函数定义虽然比较直观，但相关性是一个抽象的概念，该定义本身没有也无法具体给出R的定义，所以该模型在理论上存在很大的模糊性。n基于语言模型的检索模型n相关度排序函数则定义为由文档的语言模型生成检索的概率，即f(q,d)=p(q|d)。n建立在统计语言模型理论基础上，定义明确，便于操作。74全面分析和传统概率模型的比较（续）n具体实施方法不同n传统的概率模型n由于没有也无法对相关性做出明确定义，因此一般需要在检索中，首先给定带有相关性标记的文档作为建立模型的基础。n在实际中，要针对每个检索给定学习数据，几乎不可能。该问题是传统信息检索模型存在的一个主要问题。n基于语言模型的信息检索模型n可以基于每个文档直接计算出相关度排序函数，从而有效地避免这个问题n还可以用该模型为传统概率模型形成初始检索。75全面分析基于本体论的信息检索模型76全面分析本体论n本体论（Ontology）最早是哲学的分支，研究客观事物存在的本质。n本体（ontology）的含义是形成现象的根本实体(常与“现象”相对)。从哲学的范畴来说，本体是客观存在的一个系统的解释或说明，关心的是客观现实的抽象本质。n它与认识论（Epistemology）相对，认识论研究人类知识的本质和来源。本体论研究客观存在，认识论研究主观认知。77全面分析各种关于本体的定义n在人工智能界，最早给出本体定义的是Neches等人，将本体定义为“给出构成相关领域词汇的基本术语和关系，以及利用这些术语和关系构成的规定这些词汇外延的规则的定义”。n1993年，Gruber给出了本体的一个最为流行的定义，即“本体是概念模型的明确的规范说明”。n后来，Borst在此基础上,给出了本体的另外一种定义：“本体是共享概念模型的形式化规范说明”。nStuder等对上述两个定义进行了深入的研究，认为“本体是共享概念模型的明确的形式化规范说明”。78全面分析本体的分类和内容n本体的分类n本体是采用某种语言对概念化的描述，本体的分类按照表示和描述的形式化的程度不同，可以分为：完全非形式化的、半形式化的、严格形式化的，形式化程度越高，越有利于计算机进行自动处理。n本体的内容n从概念化对象的定义来看，一个领域的术语、术语的定义以及各个术语之间的语义网络，应是任一个领域本体论所必须包含的基本信息。n概念之间的关系n同义关系：表达了在相似数据源间的一种等价关系，是一种对称关系n上下位关系：不对称的，是一种偏序关系，具有传递性n其它各种语义关系n各个概念间复杂的语义关系组成了语义网络图，概念在其中表现为节点，而节点间的弧则代表了上述的关系。79全面分析上下位关系和同义关系土豆马铃薯土豆白薯地瓜红薯地瓜薯类植物同义关系上下位关系上位下位80全面分析语义关系81全面分析构造本体的要点n出于对各自问题域和具体工程的考虑，构造本体的过程各不相同。目前没有一个标准的本体的构造方法。n最有影响的是Gruber在1995年提出的5条规则：n清晰（Clarity）n本体必须有效的说明所定义术语的意思。定义应该是客观的，形式化的n一致（Coherence）n它应该支持与其定义相一致的推理n可扩展性（Extendibility）n应该提供概念基础，支持在已有的概念基础上定义新的术语n编码偏好程度最小（Minimal encoding bias）n概念的描述不应该依赖于某一种特殊的符号层的表示方法n本体约定最小（Minimal ontological commitment）n本体约定应该最小，只要能够满足特定的知识共享需求即可。82全面分析领域本体n领域本体(Domain ontology)的概念n提供了某个专业学科领域中概念的词表以及概念间的关系n在该领域里占主导地位的理论，是某一领域的知识表示n建立本体的方式n借助某种本体描述语言，采用“恳谈法”从人类专家那里获得知识，经过抽象组织成领域本体n应用实例nIBM中国研究中心在信息集成项目中运用本体n哈工大机器翻译研究室基于本体进行跨语言检索的研究83全面分析基于本体的检索过程n用户向信息检索系统提出检索申请。n信息检索系统产生一个界面与用户交互。界面接收用户提出的查询关键字后，系统查询本体库，从中找出出现该关键字的各个领域，然后将其领域以及在该领域下的关键字的含义罗列给用户。n用户此时可根据自己的意图，在界面上确定所需查找的领域及含义。n系统将经过本体规范后的请求交给全文搜索引擎进行检索。n全文搜索引擎检索后返回给用户检索信息。84全面分析利用本体进行检索的好处n解决从查询语言到检索语言之间转换过程中出现的语义损失和曲解等问题n保证在检索过程中能够有效地遵循用户的查询意图，获得预期的检索信息。 马铃薯红薯地瓜白薯本体扩展85全面分析隐含语义索引(LSI)86全面分析问题引出n自然语言文本中的词汇(术语)具有一词多义(polysemy)和一义多词(synonymy)的特点. n由于一词多义, 基于精确匹配的检索算法会报告许多用户不要的东西; n处理n什么地方处理旧家具？n你去把那个叛徒处理了n处理自然语言很难n由于一义多词, 基于精确匹配的检索算法又会遗漏许多用户想要的东西. n“互联网”，“万维网”，“因特网”，“国际互联网”等87全面分析词汇-文档矩阵n设Doc1, Doc2, Doc3是三个文件. 一些术语在这三个文件中的出现情况如下表: Doc1Doc2Doc3-access X document Xretrieval XXinformation X*X*theory Xdatabase Xindexing Xcomputer X*X*-假定用information 和computer作为主题词进行检索, 那么Doc2和Doc3与之精确匹配, 因而中选.然而, Doc2是用户并不想要的文件, Doc1才是想要的查不出来, 不想要的倒查了出来. 这说明精确匹配不能很好地反映用户的意图. 88全面分析词汇-文档矩阵nLSI(Latent Semantic Indexing)将自然语言中的每个文档视为以词汇为维度的空间中的一个点，认为一个包含语义的文档出现在这种空间中，它的分布绝对不是随机的，而是服从某种语义结构。n同样地，也将每个词汇视为以文档为维度的空间中的一个点。文档是由词汇组成的，而词汇又要放到文档中去理解，体现了一种“词汇文档”双重概率关系。 89全面分析LSI地提出n当然, 如果能基于自然语言理解来做这件事, 那一切问题就都没有了。问题是：n自然语言理解的目前水平还是有限度的;n即使用自然语言理解, 效率也会很低n我们希望找到一种办法, 既能反映术语之间内在的相关性, 又具有较高的效率.n1990年，来自University of Chicago、Bell Communications Research等五家单位和学者共同提出了隐含语义分析（Latent Semantic Indexing)，缩写为LSI）这一自然语言处理的方法 90全面分析算法步骤n以词项(terms)为行, 文档(documents)为列做一个大矩阵(matrix). 设一共有t行d列, 矩阵名为A. 矩阵的元素为词项在文档中的出现频度.n数学上可以证明: nA可以分解为三个矩阵T0, S0, D0T(D0的转置)的积.n这种分解叫做单值分解(singlar value decomposition)简称SVDnA=T0*S0*D0T91全面分析算法步骤n一般要求T0, S0, D0都是满秩的. 不难做到把S0的元素沿对角线从大到小排列.n现在, 把S0的m个对角元素的前k个保留, 后m-k个置0, 我们可以得到一个新的近似的分解: nXhat=T*S*DT n奇妙的是, Xhat在最小二乘意义下是X的最佳近似! 这样, 我们实际上有了一个降维的途径. nK值的选择nk越大失真越小, 但开销越大nk的选择是按实际问题的要求进行平衡的结果92全面分析三个问题n给定矩阵A, 基于A可以问三类同文件检索密切有关的问题n术语i和j有多相似? n即术语的类比和聚类问题n文件i和j有多相似?n即文件的类比和聚类问题n术语i和文件j有多相关?n即术语和文件的关联问题93全面分析三个问题的答案n比较两个术语 n做正向乘法:nXhat*XhatT=T*S*DT*D*S*TT=T*S2*TT=(TS)*(TS)TnDT*D=I, 因为D已经是正交归一的 ,s=sTn它的第i行第j列表明了术语i和j的相似程度n比较两个文件做逆向乘法:nXhatT*Xhat=D*S*TT*T*S*DT=D*S2*DT=(SD)(SD)TnTT*T=I, 因为T已经是正交归一的, s=sTn它的第i行第j列表明了文件i和j的相似程度n比较一个文件和一个术语恰巧就是Xhat本身. n它的第i行第j列表明了术语i和文件j的相关联程度.94全面分析 示例n原始矩阵A95全面分析示例nSVD分解：TT96全面分析示例nA降维处理：B=S2*2DT2*dn图示：97全面分析示例n向量夹角余弦值：n文本之间相似度矩阵tktktkkikqdqdkik11221)(CosSim(Di, Q) =98全面分析降维前后的对比n表中列出了文档在新空间的相似度，d1和d2之间的相似度为0.78，d4,d5和d6为0.94，0.93，0.74,而在原空间上两者的值是相等的。n在原空间中，d2,d3没有共同的单词，相似度为0，但是在新空间中的相似度为0.88之所已有这种结果，在于它们之间存在着同现模式。99全面分析查询处理n如何在降维空间中表示查询字段和新增文档n查询可以作为一个伪文档n每次重新计算SVD，计算量太大n解决方案：A=TSDT,TTA=TTTSDT,TTA=SDTn新的查询q，再降维后新空间表示为Tt*kTq（可以理解为一种映射）100全面分析对LSI的理解n最佳近似矩阵n从数据压缩的角度看，Xhat是秩为k的前提下矩阵X的全局最佳近似矩阵。n降维nLSI不同于向量空间模型（VSM）中文档和词汇的高维表示，而是将文档和词汇的高维表示投影在低维的潜在语义空间（Latent Semantic Space）中，缩小了问题的规模，得到词汇和文档的低维表示。n语义关联的发现n对应于小奇异值的奇异向量被忽略后，噪声被大量消减，而使语言单元之间的意义上的相关性显示出来。n潜在语义空间中（不论是文档空间，还是词汇空间），每个维度代表了一个潜概念（Latent Concept） 101全面分析利用LSI进行检索n对查询式的要求n和传统的基于关键词的查询不同，潜语义检索允许用户提交类似于自然语言的查询条件，而不一定必须是几个分离的词汇。n查询式越长，提供的信息需求越充分，越明确n检索过程n检索过程就是把查询式的集合视为是一个虚拟的文件，检索的任务是把这个虚拟的文件和其他文件做相似性比较, 挑选最相似的出来n相似度计算方法可以采用线性代数理论中的各种方法，比如向量夹角等，根据实际情况而定102全面分析适用性n多数情况下，潜在语义索引的性能好于向量空间模型，因为利用了同现度n潜在语义索引的应用依赖于具体的文档集合n适用于词汇异构度很高的文档集合n从应用角度，计算量太大n框架定义完整，优化准则清楚103全面分析本章小结n介绍了布尔模型和向量空间模型n介绍了概率模型和基于语言模型的信息检索模型n介绍了基于本体的信息检索模型及以及隐性语义索引的信息检索模型104全面分析