信息检索InformationRetrievalIRStillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望第一章 简介n信息检索（ IR ）定义及相关概念nIR和相关领域的关系nIR系统的建立nIR系统的评估nIR评价试验平台TRECn本课主要内容2 IR抽象图n目的目的 = 在一个大的文档集合中找到和所需的信息 相关的文档文档集合所需信息询问答案列表信息检索系统查找3IR定义n信信息息检检索索（Information Retrieval，IR），是指将信息按一定的方式组织和存储起来，并利用一定的检索算法，借助于特定的检索工具、根据用户的需要从结构化或非结构化的数据中获取有关信息的过程。n发展的几个阶段发展的几个阶段 n手工检索(早期,情报检索)n穿孔卡片检索(1950s)n计算机检索(面向主题,1960s)n 联机检索（1970s,1980s)n Web检索(1990s)4信息检索原理示意图信息检索原理示意图信息存储与组织信息检索与实施信息结果展示数据库信息集合信息处理者外部信息信息存储信息加工信息采集处理结果结果展示检索模式结果输出特征组配需求特征检索需求匹配算法5IR分类n按资源形式划分按资源形式划分 1、书目信息检索系统2、全文检索系统 3、多媒体信息检索系统n按服务功能划分按服务功能划分 1、单纯检索服务系统 2、统计分析信息服务系统3、决策支持系统 6IR分类n按服务区域划分按服务区域划分1、单机检索系统 2、联机检索系统 3、网络检索系统 在这门课中，我们只讨论全文检索系统的形式。7IR和其他领域的关系n数据库数据库(DB(DB ),),在DB系统中，要创建数据组织方案，这个方案定义了各种关系及关系内的属性，利用这些方案，系统可以对用户提问做出解释。例如，在DB内，可以定义如下的关系：作者（书，名字）其中，作者是关系的名字， 书和名字是这种关系的属性，分别对应着书的ID 和它的作者名，这只是定义的一部分。为了查找由“Knuth”编写的书，可以使用如下的SQL语句：SELECT book FROM author WHERE name= “Knuth”n问答系统问答系统(QA),(QA),两个系统中，问题回答的方式是不同的。在IR中，对问题的回答是间接的：鉴别关联的文档，然后用户寻找问题的直接答案。在问答系统中，系统提供直接的答案。8相关概念n文文档档（DocumentDocument），是指包含各种信息的信息源，通常情况下，用户查询的问题的答案存在于此，它的表现形式可能是文本、网页、图片、音频、视频等。在这门课中，我们只讨论文本的形式。n询询问问（QueryQuery），表示用户所需要的信息，一般情况下，它可以用如下的形式表示：“查找和 . 相关联的文档。” n关联关联（RelevanceRelevance），），信息检索的目的是寻找相关联的文档。通常情况下，在相关联的文档中，用户应该能够找到他们所需要的信息。可见，关联是用来判断是否某个文档能够为用户问题提供回答的。关联的概念是非常复杂的。关联是存在于关联是存在于C C 和和D D 之间的通过之间的通过E E 进行判断的进行判断的B B中的中的A A。其中，A = 测量区间，B = 关联方面（绝对关联）， C = 文档，D = 上下文，在这里进行关联测量（包括需要的信息） E = 用户的判断9相关概念n文本形式，文本形式，文本存在多种规范形式，通常包括非结构化（也称为纯文本）、半结构化和结构化文本。大多数情况下，文本被看作是半结构化。比如，一本书的说明书可能是如下的形式：ISBN: 0-201-12227-8 Author: Salton, Gerard Titre: Automatic text processing: the transformation, analysis, and retrieval of information by computer Editor: Addison-Wesley Date: 1989 Content: 10相关概念n切切词词（segmentation），或称分词，主要在中文信息处理中使用，即把一句话分成一个词的序列。例如，“网络与分布式系统实验室”，分词为“网络/ 与/ 分布式/ 系统/ 实验室/”。n停停用用词词（stop word），指文档中出现的连词，介词，冠词等并无太大意义的词。例如在英文中常用的停用词有the，a, it等；在中文中常见的有“是”，“的”，“地”等。通常这些词被放在一个列表中，称为停用词表（stoplist）。 n索索引引词词（keyword,标引词，关键词）:可以用于指代文档内容的预选词语,一般为名词或名词词组。n组组合合词词（compound words）:由两个或两个以上的单词构成的词，也称为合成词，如：北京大学，建设银行等。n词干提取词干提取（stemming 英语文档处理）：单、复数，人称，时态等 countries = country，interesting = interest11Web检索实例：搜索引擎n搜搜索索引引擎擎（Search Engine，SE），Web上的一种应用软件系统，它以一定的策略在Web上搜集和发现信息，对信息进行处理和组织后，为用户提供Web信息查询服务n搜索引擎三段式工作流程 搜集 预 处 理服务12ExampleGoogleWeb13IR系统的建立n最初应用于图书馆系统(1950s)ISBNISBN: 0-201-12227-8 AuthorAuthor: Salton, Gerard TitleTitle: Automatic text processing: the transformation, analysis, and retrieval of information by computer EditorEditor: Addison-Wesley DateDate: 1989ContentContent: n外部属性和内部属性（内容）nDB：通过外部属性查找nIR: 通过内部属性（内容）进行检索14实现方法1. 字符串匹配 (在文档中进行线性扫描)- 速度慢- 难于改进例如：查找与“数据库和人工智能在工业上的应用”相关联的文档。对于“人工智能和数据库在工业上的应用，人工智能在工业上的应用，数据库在工业上的应用，. . ”等情况不兼容。 15实现方法2.索引 (*)- 速度快-易于改进例如：关键词表示关键词表示：原句子：数据库和人工智能在工业上的应用预处理后：数据库、人工智能、工业、应用原句子：人工智能和数据库在工业上的应用预处理后：人工智能、数据库、工业、应用倒排文档：倒排文档：人工智能 d1， d3，d5, d6,d7 查找过程描述：查找过程描述：用户问题：Q = w1=数据库, w2=人工智能, w3=工业, 且 Q= w1 AND w2 AND (NOT w3)文档列表：w1 d1, d2, d5, d7, d9 w2 d1, d3, d5, d6, d7 w3 d2, d5, d6应用操作： w1 AND w2 = d1, d5,d7 w1 AND w2 AND (NOT w3) = d1,d7 16基于索引的IRDocument Query indexingindexing indexingindexing (Query analysis)Representation Representation(keywords) Query (keywords) evaluation 17基于索引的IR系统形式化表示DocsInformation NeedIndex TermsdocqueryRankingmatch18通用IR系统框图 UserInterface Text OperationsQuery OperationsIndexingSearchingRankingIndexTextqueryuser needuser feedbackranked docs retrieved docslogical viewlogical viewinverted fileDB Manager Module4, 106, 75828Text DatabaseText19全文检索系统评估n问题n如何评价系统的好与坏？n返回的文档都是相关的吗？（精度）n所有相关的文档都被找到了吗？（全度）20系统评估主要方面n效率: 时间, 空间n效果:n某系统是否有能力检索到相关联的文档? n哪个系统更好？n常用方法:n查准率 = 检索到的相关文档数 / 检索的文档数n查全率 =检索到的相关文档数 / 所有的相关文档数 relevantretrievedretrieved relevant21测量方法n查准率查准率：是指在系统所找到的文档中关联文档所占的比例。 Precision Precision = 检出的相关文献量 /检出的文献总量 = a/(a+c)n查全率查全率：是指系统所找到的关联文档在文档库中所有的关联文档中所占的比例。 Recall Recall= 检出的相关文献量/ 检索系统中的相关文献总量 = a/(a+b)n噪音噪音(Noise) = 检出的不相关的文档数 / 检索的文档数=c/a+cn静音静音(Silence) = 没有检出的相关文档数 / 相关文档数 =b/a+bn噪音 = 1 求精率;静音 = 1 求全率n非相关检出率非相关检出率（Fallout）=检索出的不相关文档数/不相关文档数=c/c+d相关文献不相关文献总计被检出文献aca+c未检出文献bdb+d总计a+b c+da+b+ c+d22P/R 计算图示 ListRel?Doc1 YDoc2Doc3 YDoc4 YDoc5假设: 5 个相关文档23precision/recall的关系查全率（R）和查准率（P）之间具有密切的关系（即“互逆关系”），反映了某一检索结果集合的不同方面的特征。目前，在评价试验的实践中，经常采用的方法是将R和P结合在一起， 形成某种单一指标或平均值指标，对它们进行替代。24测试集n系统间的比较：在相同的测试集上，比较不同的IR系统n测试集包括：n文档集合n询问集合 n文档-询问对的相关性判断 (每个询问所对应的答案 )n系统的结果和答案集进行比较25其他测量方法n单值测量:nF-measure = 2 P * R / (P + R)nE-measure = 1-（1+b*b）/（b*b/R+1/P），其中，b为参数，用以反映或调整R和P的相对重要性。注意：当b=1时，E = 1- F；当b1时,意味着P的重要性大于R；当b100K)与问题集 (50)n每位参加者对每个问题提交1000 个文档n将每位参加者的前100个文档汇集起来，形成一个可能相关的文档“池” ( global pooling)n检索评价专家进行人工判断，评出每一文档的相关性n其它的文档被认为是不相关的n系统的性能以1000个答案来计算 33比赛项目分类n特殊检索Ad Hoc : 不同的提问式，在同一个文档集合中进行检索n筛选检索Routing (filtering) : 用户的需求是固定的，文档集合是变化的n跨语言检索Cross-Language: 属于Ad Hoc 检索n网页检索Web: 对WWW文档快照集合进行检索n问答系统Question-Answering: When did Nixon visit China?n交互式检索Interactive: 使用户和系统进行交互n口语文档检索Spoken document retrievaln图像和视频检索Image and video retrieval34TREC的意义n为理论检索模型和试验检索系统提供了公平、定量、具有实用价值的性能评价机会，并为前几位的系统提供了商业机会n开发了新的系统评估方法n促进了相关领域的发展 (NLP, 机器翻译, 摘要, )n建议成立C-TREC,促进中国信息检索技术的发展35其他研究机构nCLEF = Cross-Language Experimental Forumn For European languagesn Organized by Europeansn Each per year (March Oct.)nNTCIR: nOrganized by NII (Japan)n For Asian languagesn Cycle of 1.5 year36本课的主要研究内容n索引理论：如何最好地表示文档和用户询问的内容，切词、关键词选取索引理论：如何最好地表示文档和用户询问的内容，切词、关键词选取n自动索引的基本原理 n基于词汇分布特征的索引方法n基于语言规则与内容的索引n人工智能索引法n汉语自动索引n检索模型：如何判断询问和文档之间的关联性检索模型：如何判断询问和文档之间的关联性n布尔模型（Boolean，1957）：集合论，布尔代数（逻辑操作）n矢量模型(Vector Space Model, VSM，1960s末)：线性代数n概率模型（Probability，1976）：经典概率论n搜索引擎：搜索引擎：WebWeb检索实例检索实例n信息搜集n预处理n检索服务n信息处理与组织信息处理与组织n自动分类与聚类n自动摘要nIRIR的高级技术（性能改善技术）的高级技术（性能改善技术） n自然语言处理、语言模型n多语言检索与分布式检索n用户询问技术 37