信息获取模型Modeling-I.ppt

1,2.信息获取模型Modeling I,基本概念经典的IR模型结构化文本检索模型浏览模型,2,Review of Last Week,信息检索简介将用户的信息需求转变到查询匹配查询和存储的文档信息评价查询结果与用户需求的匹配程度以下概念的区别 Data retrieval and information retrieval初步介绍了索引技术倒排索引为什么使用倒排索引？倒排索引的结构如何？一些压缩技术，包括词表压缩出现位置压缩齐普夫率Zipfs Law提出了信息检索中存在的一些问题,3,前言,本周主要介绍IR系统的一些模型为什么要建模?方便深入地分析比较和预测什么是建模?通过理论方法描述系统的本质，忽略一些无关紧要的方面IR系统的一个核心问题就是预测或计算出文档集中哪些与用户查询是相关的、哪些是无关的,4,文档,文档是由文本构成的逻辑单元记录的单元(由文本或其他一些东西组成)能够被存储、检索、显示出的单元实体用来表达某种语义的实体单元units of text grouped together for a purpose也可能是完全无结构的文本Text as written by authors of documents,5,文档模型,文档应当以一种可以被计算机识别的格式或结构来处理和表达文档由文本组成并非文本中的每一个词对于搜索都有意义文档本身往往并不包含可识别的元数据信息，比如作者和文档的标题,6,文档的表现形式,文档应该能够被处理，文档的表达方式能够帮助用户从系统中识别和接受信息识别作者和标题识别文章主题提供总结/摘要对文档进行主题分类,7,查询处理,IR 系统通常采用关键词/索引词来处理查询索引词文档关键词或一些被选定来表达文档内容的词文档中的任何词(更一般意义上讲)对于文档可能进行词根处理connect:connecting,connection,connections中文也有词根处理，如：高高兴兴 高兴根据选定的索引词建倒排索引，以便查询使用,8,Docs,Information Need,Index Terms,doc,query,Ranking,match,9,结果排名,结果排名是指对检索到的文档进行排序，这个顺序反映了文档与用户需求之间的相关程度排序基于相关度计算的一些基本假设进行查询和文档关键词共享同一个词的集合如何定义相关度不同的相关性定义导致不同的IR模型,10,结果排名,在索引词层次的匹配是不精确的用户经常对搜索结果不满意大多数用户并不知道如何正确使用查询的语法，因此查得的结果就会更糟糕Web用户经常会感到不满意如何能够形成好的排名对于IR系统来说至关重要,11,Retrieval:Ad Hoc and Filtering,Ad hoc retrieval自由式查询,Collection“Fixed Size”,Q2,Q3,Q1,Q4,Q5,12,Retrieval:Ad Hoc and Filtering,Filtering过滤式查询（比如股票信息）,Documents Stream,User 1Profile,User 2Profile,Docs Filteredfor User 2,Docs forUser 1,13,IR 模型,Retrieval:Adhoc Filtering,Browsing,U s e r T a s k,14,IR模型、文档逻辑视图、用户任务之间的关联,LOGICAL VIEW OF DOCUMENTS,U,S,E,R,T,A,S,K,15,IR系统的形式化描述(MIR p.23),IR模型是一个四元组D 是文档集中文档的逻辑表示形式Q 是用户需求的逻辑表示形式，亦可理解为查询F 是一种机制，用于构建文档表示、查询以及它们之间关系的模型R(qi,dj)是排名函数，该函数输出一个与查询qiQ和文档表示dj D有关的实数，从而在文档之间根据查询qi定义一个顺序,16,框架F的含义,对于经典布尔模型而言，框架由文档集合和作用在这个集合上的标准运算（与、或、非）组成对于经典向量模型而言，框架由t维向量空间和作用在向量上的标准线性代数运算组成对于经典概率模型而言，框架由集合、标准概率运算和贝叶斯 Bayes理论组成,17,经典IR模型-基本概念,每个文档可用一组有代表性的关键词集合来描述索引项index terms往往是文档中的一个词，这个词有助于表达或记载该文档的主题索引项index terms通常是名词，因为名词本身具有语义对于一个全文检索系统来说，也可以假设所有的词都是索引项例如，一些web search engines,18,经典IR模型-基本概念,不同关键词在描述文档内容时的作用是不尽相同的，较少出现的词往往能够表征出较少的文档集合索引项index term的重要性由权重来表示，设 ki 是一个索引项 index termdj 是一个文档 document wij 是(ki,dj)之间的权重权重 wij 定量描述了某关键词ki对于描述文档dj的重要程度,19,经典IR模型 符号表示,ki 索引项 index termdj 文档documentt 系统中索引项的数目K=(k1,k2,kt)是所有索引项的集合wij 0 是索引项ki在文档dj中的权重wij=0 表明某词并不属于某文档，或词与文档无关vec(dj)=(w1j,w2j,wtj)是与文档dj相关的词的权重向量gi(vec(dj)=wij 返回vec(dj)中第i个向量的函数,20,集合(直观描述),具有某种属性的对象总体(通常用大写字母表示，如A,B)，这些对象称为其元素(通常用小写字母表示，如x,y)x是A的元素记为：xAx不是A的元素记为：xA集合的基本特性是，对于给定的集合A，任何对象x,xA与xA中有且只有一个成立,21,集合的并运算和交运算,集合A与B的并是由A或B的所有元素组成的集合,记为AB,即AB=x|xA或xB集合A与B的交是由所有A和B的公共元素组成的集合,记为AB,即AB=x|xA且xB,22,布尔代数,布尔变量：只有“真”、“假”取值的变量如命题“一篇文档中存在世界杯这个词”，其结果变量就是一个布尔变量(存在则取真，否则取假)计算机中常常用1表示“真”true，0表示“假”false布尔操作(关系)与(AND)：(A AND B)=true if A=true and B=true 或(OR)：(A OR B)=true if A=true OR B=true非(NOT)：(NOT A)=true if A=false布尔表达式：多个布尔变量之间通过布尔操作组成的表达式如：A AND(B OR C)AND NOT D蕴含：两个布尔表达式P、Q，如果P为true，那么Q也为true，则称P蕴含Q，记为PQ,23,布尔模型,基于集合论和布尔代数的简单模型查询以布尔表达式的方式出现，表示为多个合取向量的析取精确的语义，简洁的表达方式q=ka(kb kc)qdnf 表示查询q的析取范式，qcc 表示qdnf 的任意合取向量词在文档中要么出现要么不出现，因此,wij 0,1Considerq=ka(kb kc)析取范式qdnf=(1,1,1)(1,1,0)(1,0,0)qcc=(1,1,0)是一个合取子项,24,布尔模型,(1,1,1),(1,0,0),(1,1,0),Ka,Kb,Kc,任何一个布尔表达式都可以转化成析取范式以上将布尔查询转化成析取范式,25,布尔模型的缺陷,没有部分匹配的概念不提供排名先后，没有相似度计算判断要么文档与查询匹配，要么不匹配更接近一个数据库系统而不是一个信息检索系统信息需求必须被翻译为布尔表达式，然而很多用户发现自己对布尔表达式并不熟悉，很难用来表达自己的需求用户所采用的布尔查询往往过于简单直接导致的结果是布尔模型返回的查询结果要么太多，要么太少,26,课堂思考题,想查关于2009年快女6进5 比赛的新闻，用布尔模型怎么构造查询？,27,参考答案,(2009 OR 今年)AND(快乐女声OR 快女)AND(6进5 OR 六进五OR 六AND 进AND 五)表达式相当复杂，构造困难不严格的话结果过多，而且很多不相关；非常严格的话结果会很少，漏掉很多,28,布尔模型的优缺点,优点：简单：现代很多搜索引擎中仍然包含布尔模型的思想，如Google的高级检索自我保护功能：降低用户对搜索系统的期望，使自己不在责任方，检索结果不好的原因在于用户构造查询不好缺点：只能严格匹配(得分不是0就是1)，不能近似或者部分匹配，多个结果无法排序一般用户构造查询不是很容易，构造不利可能造成结果过多或者过少,29,向量模型,布尔模型二值权值的权重表示方式限制太大非二值权值的权重能够实现部分匹配，可计算用户查询与文档之间的相似度这种相似度有利于用户判断文档与自己需求的贴近程度,30,向量,向量(矢量，vector)：既有大小又有方向的量，通常用有向线段表示考虑从空间坐标系原点出发(其他向量可以平移到原点出发)的向量，终点坐标为，我们称之为一个n维向量向量的运算：加、减、倍数、内积,31,向量的模、距离和夹角,向量的模(大小)：向量的(欧氏)距离夹角,32,向量空间模型,向量空间模型(Vector Space Model，VSM)是康奈尔大学Salton等人上世纪70年代提出并倡导，原型系统SMART*可从ftp:/pub/smart/下载全部源码和相关语料Term独立性假设：Term在文档中的出现是独立、互不影响的查询和文档都可转化成Term及其权重组成的向量表示，都可以看成空间中的点，向量之间通过距离计算得到查询和每个文档的相似度,33,向量模型,定义:wij 0 whenever ki djwiq=0 associated with the pair(ki,q)vec(dj)=(w1j,w2j,.,wtj)vec(q)=(w1q,w2q,.,wtq)每一个关键词 ki 都代表一个向量 vec(i)向量 vec(i)和 vec(j)之间是独立的(i.e.,假设关键词在文档中出现是相互独立的)假设各关键词的出现是独立的，那么t 个向量 vec(i)形成了t维空间的正交基在这个t维空间，查询和文档都是权重构成的向量,34,向量模型：Cosine Similarity,Since wij=0 and wiq=0,0=sim(q,dj)=1引入了在0和1之间的相似度，一个文档即使是与查询部分匹配也能够被检索,35,向量模型Term的选择,Term能代表文档内容的特征Term粒度：Term可以是字、词、短语或者某种语义单元(比如：所有同义词作为1维)，最简单的是采用全文标引(full text indexing)，即用文档中出现的所有的字或词作为标引词降维：VSM中向量的维数很大(以中文词索引为例，向量维数会上10万)时，往往也同时引入了很多噪音。因此，实际应用中，会采用一些降维策略(如：去停用词、对英文进行词干还原、只选择名词作为Term、将Term聚成的不同类作为一个个Term、选择出现次数较多的词作为Term等等),36,向量模型的权重计算：tf vs idf,如何计算 wij 和 wiq?一个好的权重必须考虑两方面因素:词的频率(term frequency,tf)，通常称为tf因子：词对文档的重要性或相关程度tf factor,the term frequency within a document逆文档频率（inverse document frequency,idf)，通常称为idf因子：词对于区分不同文档所起的作用idf factor,the inverse document frequencywij=tf(i,j)*idf(i),37,向量模型,设,N 集合中文档的总数量ni 集合中包含 ki的文档的数量freq(i,j)表示 ki 在dj中出现的次数归一化的tf因子计算如下：f(i,j)=freq(i,j)/max(freq(l,j)max(freq(l,j)代表在文档dj中出现频度最高的词出现的频率idf 因子计算如下：idf(i)=log(N/ni)取 log 是使得tf和idf之间具有可比性，也可以把idf理解为关键词ki的信息量,38,向量模型,目前为止最好的权重机制如下所示：wij=f(i,j)*log(N/ni)the strategy is called a tf-idf weighting scheme对于计算查询的权重，通常按如下公式计算：wiq=(0.5+0.5*freq(i,q)/max(freq(l,q)*log(N/ni)对于一般集合而言，tf-idf 权重的向量模型是一个比较好的排名机制，比较简单而且易于计算,39,向量模型,优点：词权重改进了结果集的质量部分匹配允许检索出与查询接近的文档cosine ranking排名机制根据文档与查询之间的相似度对文档进行排序缺点：理论上不够：基于直觉的经验性公式标引项之间的独立性假设与实际不符：实际上，Term的出现之间是有关系的，不是完全独立的。如：“王励勤”“乒乓球”的出现不是独立的,40,向量模型:例1,41,向量模型:例2,42,向量模型:例3,43,概率统计初步,随机试验与随机事件概率和条件概率乘法公式、全概率公式、贝叶斯公式随机变量随机变量的分布,44,随机试验和随机事件,随机试验：可在相同条件下重复进行；试验的可能结果不止一个，但能确定所有的可能结果；一次试验之前无法确定具体是哪种结果出现掷一颗骰子，考虑可能出现的点数随机事件：随机试验中可能出现或可能不出现的情况叫“随机事件”掷一颗骰子，4点朝上,45,概率和条件概率,概率：直观上来看，事件A的概率是指事件A发生的可能性，记为P(A)掷一颗骰子，出现6点的概率为多少？条件概率：已知事件A发生的条件下，事件B发生的概率称为A条件下B的条件概率，记作P(B|A)30颗红球和40颗黑球放在一块，请问第一次抽取为红球的情况下第二次抽取黑球的概率？,46,乘法公式、全概率公式和贝叶斯公式,乘法公式：P(AB)P(A)P(B|A)P(B)P(A|B)P(A1A2An)P(A1)P(A2|A1).P(An|A1An1)全概率公式：A1A2An是整个样本空间的一个划分贝叶斯公式：A1A2An是整个样本空间的一个划分,47,事件的独立性,两事件独立：事件A、B，若P(AB)=P(A)P(B)，则称A、B独立三事件独立：事件A B C，若满足P(AB)=P(A)P(B),P(AC)=P(A)P(C),P(BC)=P(B)P(C),P(ABC)=P(A)P(B)P(C)，则称A、B、C独立多事件独立：两两独立、三三独立、四四独立.,48,随机变量,随机变量：若随机试验的各种可能的结果都能用一个变量的取值（或范围）来表示，则称这个变量为随机变量，常用X、Y、Z来表示(离散型随机变量)：掷一颗骰子，可能出现的点数X(可能取值1、2、3、4、5、6)(连续型随机变量)：北京地区的温度(-1545),49,概率模型,通过概率的方式来描述和刻画 IR problem理想结果集：给定一个用户查询，存在一个文献集合，该集合只包含完全相关的文献而不包括其他不相关的文献把构造查询的过程看成详细描述理想结果集属性的过程这些属性是什么呢？在开始时并不确切知道，因此需要努力猜测是什么初始的猜测允许我们形成一个初步的对理想结果集的概率描述，用于检索出初始的文献集在改进理想结果集的概率描述这一目标指引下，叠代改进假设最初查出一些文档用户查看这些文档，找到那些有用的文档 IR系统使用这些信息来优化理想结果集的描述重复以上过程，结果集会越来越好,50,假设：概率原则,给定一个用户查询 q 以及一个文档 dj，概率模型尽力去估计用户对文档dj感兴趣的概率(i.e.,relevant)，并认为文档和查询相关的概率仅依赖于查询和文档的表示模型模型假设在文献集合中存在一个子集，且用户倾向于把该子集作为查询q 的结果集，该理想的结果集用R 表示；对于用户来说，它应该能够使得总体的相关概率最大；集合R中的文献与查询相关，不在集合中的文献则不相关那么如何计算相关的概率呢？,51,排名计算,概率排名相似度计算公式如下：sim(q,dj)=P(dj relevant-to q)/P(dj non-relevant-to q)这就是文档dj 与查询q相关的判断标准以此为准则能够最小化误判发生的概率定义：wij 0,1，wiq 0,1R表示已知的相关文档集（或最初的猜测集），R 表示R的补集P(R|dj)：文档dj 与查询q相关的概率P(R|dj)：文档dj 与查询q不相关的概率,52,排名计算,P(dj|R)：从相关文档集R中随机选取 dj 的概率P(R)：从整个集合中随机选择一个文档是相关的概率P(dj|R)：从补集中随机选取 dj 的概率P(R)：从整个集合中随机选择一个文档是不相关的概率,根据贝叶斯定理：,对文档集中的每一个文档来说，P(R)和P(R)都是一样的：,53,排名计算,Assume the independence of index terms,P(ki|R)：表示索引词ki 在集合R的某篇文档中随机出现的概率P(ki|R)：表示索引词ki 不在集合R的某篇文档中随机出现的概率对于集合 R，相应的概率具有相似的含义,54,排名计算,where P(ki|R)=1-P(ki|R)P(ki|R)=1-P(ki|R),两边对对数，忽略在相同查询背景下对所有文献恒定不变的因子，则,55,初始排名计算,概率 P(ki|R)和 P(ki|R)如何计算?在没有任何检出的文档时，基于以下假设来估算：P(ki|R)=0.5P(ki|R)=ni/N where ni 是包含ki 的文档数，N表示集合中的文献总数用这个最初的猜想来获取最初排名在最初排名基础上不断改进,56,Improving the Initial Ranking,LetV：用概论模型初步检出并经过排序的文档的一个子集Vi：V中包含 ki的文档集合重新估算：,递归计算,57,Improving the Initial Ranking,为了避免 V=1 and Vi=0 在实际中引发的问题，可在公式中加入调整因子：P(ki|R)=Vi+0.5 V+1P(ki|R)=ni-Vi+0.5 N-V+1调整因子恒等于0.5并不能总是令人满意，可用分数ni/N作为调整因子：P(ki|R)=Vi+ni/N V+1P(ki|R)=ni-Vi+ni/N N-V+1,58,优缺点,优点:文档依概率相关排序良好的数学模型，便于理论分析缺点:需要猜测初始值 P(ki|R)没有考虑 tf and idf factors假设索引词相互独立,59,经典模型之间的比较,布尔模型不提供部分匹配功能，被认为是最弱的模型Salton and Buckley 作了相当的试验表明对于通常的数据集来说 vector model 要好于probabilistic model,60,结构化文本检索模型,假设一个用户回忆起来某个感兴趣的文档包含这样一页，其中字符串“Polluted Water”围绕一幅图出现，这幅图的标签包含“earth”用经典的信息检索模型，该查询可表示为：“Polluted Water”and“earth”一种更为丰富的表达方式可能是：same-page(near(Polluted Water Figure(label(earth)有的信息检索模型能够将文本的信息与结构化信息联合起来查询，我们称之为结构化文本检索(structured text retrieval,STR)模型往往搜索所有符合查询条件的文档合适的结果排名目前仍然是一个未能解决的研究问题往往是在查询语言的表现力和效率之间进行折中应用场景有限，往往是小的数据集，良好的结构相关概念Match point 匹配点，表示文本中与用户查询相匹配的词串的位置Region 区域，表示文本中连续的局域部分Node 节点，表示文献的结构化单元,61,基于非重叠链表的模型,将整个文本划分成若干非重叠的文本区域，并用链表连接起来划分方法有多种，会产生多个链表（彼此独立，有不同的数据结构）；每个链表对应一个独立的倒排文档，每个结构单元作为索引中的一个项，与每项相关的是一个文本区域链表与传统倒排表良好兼容查询简单,Chapter,Sections,Subsections,Pages,L1,L2,L3,L4,62,基于临近节点的模型,Chapter,Sections,Subsections,Subsubsections,holocaust,10,256,48324,在文档上定义独立分层索引结构，每个索引都有严格的层次结构，即由章、节、段、页、行组成 每个Node都与一个文本区域相关；两个不同的层次结构可能会指向同一个Region 对涉及不同层次结构的用户查询而言，结果只能由来自一个层次的所有Node形成，目的是允许以较少的表达获得较快的查询处理 对结构部分分层索引，对词平坦索引；在查找的时候根据倒排表中节点临近情况返回查找结果,63,结构化索引以方便查询处理,Query:(*section)with(holocaust)which search for section,subsection and subsubsection最简单直白的处理方法遍历倒排列表，对每个出现的 holocaust 都在层次索引中查找包含该词的节、子节、子子节一个更为复杂的查询处理机制对 holocaust 链表中的第一项，搜索层次索引，找到最内层的匹配单元，即最下层的节点看临近出现的 holocaust是否也在此节点中,不需要对层次索引逐个从上到下遍历结构树，只依靠邻近节点(Proximal Nodes)即可快速查找出现章节。,64,浏览模型,有时用户的兴趣并不在提出查询获得结果，而是希望通过对查询结果文档进行浏览以获得感兴趣的内容对于一个浏览任务来说，用户的目的性并不像一般搜索任务那么明确三种浏览模型：扁平（flat）结构导向（structure guided)超文本（hypertext）,65,扁平式(flat)浏览,文档空间平坦组织，并未结构化组织在相邻文档中查找相关文档，并通过浏览这些文档来修改原始查询以获得更好的查询结果以平坦式方法浏览单个文档缺陷：在给定的页面或屏幕上，可能没有关于用户所处上下文情况的任何提示,66,结构化引导的浏览,目录，即类的层次结构，将文献按照相关主题来分类和组织用户浏览在目录结构指引下进行，可以变焦的方式上下查看这些层次，并保持上下文的线索界面也可以提供一些其他工具如历史地图，用来指明最近访问过的类,67,Web Page 目录结构,Open Directory ProjectThe Open Directory Project 是最大、最具综合性、人工编辑的网站目录，它是由大量志愿者来构建和维护的Google,Baidu,Yahoo!网站分类,68,69,70,71,超文本模型,超文本是一个允许以非顺序方式在计算机屏幕上浏览文本的高层交互式导航navigational结构超文本实质上是由结点和链组成，结点之间的关系用链表示，结点和链构成一个有向图结构超文本的导航过程可以被理解成遍历一个有向图的过程关于web准确的讲，web并不是一个严格意义上的超文本，因为它缺少基本的数据模型，缺乏导航计划，而且缺乏设计统一的用户界面,