信息检索 Information Retrieval (IR) 第一章 概述 （Introduction） 2007-09 ~ 2007-12

第一章 简介 信息检索（ IR ）定义及相关概念 IR和相关领域的关系 IR系统的建立 IR系统的评估 IR评价试验平台TREC 第一章 简介 信息检索（ IR ）定义及相关概念 IR和相关领域的关系 IR系统的建立 IR系统的评估 IR评价试验平台TREC 本课主要内容

IR抽象图 目的 = 在一个大的文档集合中找到和所需的信息 相关的文档 所需信息 询问 信息检索系统 文档集合 查找 答案列表

IR定义 信息检索（Information Retrieval，IR），是指将信息按一定的方式组织和存储起来，并利用一定的检索算法，借助于特定的检索工具、根据用户的需要从结构化或非结构化的数据中获取有关信息的过程。 发展的几个阶段 手工检索(早期,情报检索) 穿孔卡片检索(1950s) 计算机检索(面向主题,1960s) 联机检索（1970s,1980s) Web检索(1990s) IR的两种形式： 特别检索（Ad Hoc，文档集不变） and 筛选（Filtering，用户需求不变）

信息检索原理示意图 信息存储与组织 信息检索与实施 信息结果展示 数据库 信息集合 信息处理者 外部信息 信息存储 信息加工 信息采集 处理结果 结果展示 检索模式 结果输出 特征组配 需求特征 检索需求 匹配算法

IR分类 1、书目信息检索系统 1、单纯检索服务系统 按资源形式划分 按服务功能划分 2、全文检索系统 3、多媒体信息检索系统 2、统计分析信息服务系统 3、决策支持系统

IR分类 按服务区域划分 1、单机检索系统 2、联机检索系统 3、网络检索系统 在这门课中，我们只讨论全文检索系统的形式。

IR和其他领域的关系 数据库(DB ),在DB系统中，要创建数据组织方案，这个方案定义了各种关系及关系内的属性，利用这些方案，系统可以对用户提问做出解释。例如，在DB内，可以定义如下的关系： 作者（书，名字） 其中，作者是关系的名字， 书和名字是这种关系的属性，分别对应着书的ID 和它的作者名，这只是定义的一部分。为了查找由“Knuth”编写的书，可以使用如下的SQL语句： SELECT book FROM author WHERE name= “Knuth” 问答系统(QA),两个系统中，问题回答的方式是不同的。在IR中，对问题的回答是间接的：鉴别关联的文档，然后用户寻找问题的直接答案。在问答系统中，系统提供直接的答案。

相关概念 文档（Document），是指包含各种信息的信息源，通常情况下，用户查询的问题的答案存在于此，它的表现形式可能是文本、网页、图片、音频、视频等。在这门课中，我们只讨论文本的形式。 询问（Query），表示用户所需要的信息，一般情况下，它可以用如下的形式表示：“查找和… …. 相关联的文档。” 关联（Relevance），信息检索的目的是寻找相关联的文档。通常情况下，在相关联的文档中，用户应该能够找到他们所需要的信息。可见，关联是用来判断是否某个文档能够为用户问题提供回答的。关联的概念是非常复杂的。关联是存在于C 和D 之间的通过E 进行判断的B中的A。其中， A = 测量区间，B = 关联方面（绝对关联）， C = 文档，D = 上下文，在这里进行关联测量（包括需要的信息） E = 用户的判断

相关概念 文本形式，文本存在多种规范形式，通常包括非结构化（也称为纯文本）、半结构化和结构化文本。大多数情况下，文本被看作是半结构化。比如，一本书的说明书可能是如下的形式： 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: <Text Content>

相关概念 切词（segmentation），或称分词，主要在中文信息处理中使用，即把一句话分成一个词的序列。 例如，“网络与分布式系统实验室”，分词为“网络/ 与/ 分布式/ 系统/ 实验室/”。 停用词（stop word），指文档中出现的连词，介词，冠词等并无太大意义的词。例如在英文中常用的停用词有the，a, it等；在中文中常见的有“是”，“的”，“地”等。通常这些词被放在一个列表中，称为停用词表（stoplist）。 索引词（keyword,标引词，关键词）:可以用于指代文档内容的预选词语,一般为名词或名词词组。 组合词（compound words）:由两个或两个以上的单词构成的词，也称为合成词，如：北京大学，建设银行等。 词干提取（stemming 英语文档处理）：单、复数，人称，时态等 countries => country，interesting => interest

Web检索实例：搜索引擎 搜索引擎（Search Engine，SE），Web上的一种应用软件系统，它以一定的策略在Web上搜集和发现信息，对信息进行处理和组织后，为用户提供Web信息查询服务 搜索引擎三段式工作流程 搜集 预 处 理 服务

Google Web Example

IR系统的建立 最初应用于图书馆系统(1950s) ISBN: 0-201-12227-8 外部属性和内部属性（内容） Author: Salton, Gerard Title: Automatic text processing: the transformation, analysis, and retrieval of information by computer Editor: Addison-Wesley Date: 1989 Content: <Text> 外部属性和内部属性（内容） DB：通过外部属性查找 IR: 通过内部属性（内容）进行检索

实现方法 1. 字符串匹配 (在文档中进行线性扫描) - 速度慢 - 难于改进 1. 字符串匹配 (在文档中进行线性扫描) - 速度慢 - 难于改进 例如：查找与“数据库和人工智能在工业上的应用”相关联的文档。对于 “人工智能和数据库在工业上的应用，人工智能在工业上的应用，数据库在工业上的应用，... ... ”等情况不兼容。

实现方法 2. 索引 (*) - 速度快 易于改进 例如： 关键词表示： 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}

基于索引的IR Document Query indexing indexing (Query analysis) Representation Representation (keywords) Query (keywords) evaluation

基于索引的IR系统形式化表示 Docs Index Terms doc match Ranking Information Need query Ranking match

通用IR系统框图 4, 10 6, 7 5 8 2 User Interface Text Operations Query Indexing Searching Ranking Index Text query user need user feedback ranked docs retrieved docs logical view inverted file DB Manager Module 4, 10 6, 7 5 8 2 Database

全文检索系统评估 问题 如何评价系统的好与坏？ 返回的文档都是相关的吗？（精度） 所有相关的文档都被找到了吗？（全度）

系统评估主要方面 效率: 时间, 空间 效果: 常用方法: relevant retrieved 某系统是否有能力检索到相关联的文档? 哪个系统更好？ 常用方法: 查准率 = 检索到的相关文档数 / 检索的文档数 查全率 =检索到的相关文档数 / 所有的相关文档数 relevant retrieved retrieved relevant

测量方法 a c a+c b d b+d a+b c+d 相关文献 不相关文献 总计 被检出文献 未检出文献 a+b+ c+d 查准率：是指在系统所找到的文档中关联文档所占的比例。 Precision = 检出的相关文献量 /检出的文献总量 = a/(a+c) 查全率：是指系统所找到的关联文档在文档库中所有的关联文档中所占的比例。 Recall= 检出的相关文献量/ 检索系统中的相关文献总量 = a/(a+b) 噪音(Noise) = 检出的不相关的文档数 / 检索的文档数=c/a+c 静音(Silence) = 没有检出的相关文档数 / 相关文档数 =b/a+b 噪音 = 1 – 求精率;静音 = 1 – 求全率 非相关检出率（Fallout）=检索出的不相关文档数/不相关文档数=c/c+d 相关文献 不相关文献 总计 被检出文献 a c a+c 未检出文献 b d b+d a+b c+d a+b+ c+d

P/R 计算图示 List Rel? Doc1 Y Doc2 Doc3 Doc4 Doc5 … 假设: 5 个相关文档

precision/recall的关系 查全率（R）和查准率（P）之间具有密切的关系（即“互逆关系”），反映了某一检索结果集合的不同方面的特征。目前，在评价试验的实践中，经常采用的方法是将R和P结合在一起， 形成某种单一指标或平均值指标，对它们进行替代。

测试集 系统间的比较：在相同的测试集上，比较不同的IR系统 测试集包括： 文档集合 询问集合 文档-询问对的相关性判断 (每个询问所对应的答案 ) 系统的结果和答案集进行比较

其他测量方法 单值测量: F-measure = 2 P * R / (P + R) E-measure = 1-（1+b*b）/（b*b/R+1/P），其中，b为参数，用以反映或调整R和P的相对重要性。注意：当b=1时，E = 1- F；当b〉1时,意味着P的重要性大于R；当b<1时, 意味着R的重要性大于P。 平均求精率 = 求全率的n个点取值所对应的求精率的平均值 在n 个文档处的求精率 (常用于 Web IR) 期待的检索长度 （在获得n个相关文档时所需检索的不相关文档数）

在方法1基础上的方法2的改善 = （方法2的性能 — 方法1的性能）/方法1的性能 平均求精度、平均求全度的计算方法 平均求精度（Average Recall）和平均求全度（Average Precision）的计算方法有3点（0.25,0.50,0.75）或（0.2,0.5,0.8） 、 10点（0.1, 0.2, ..., 1.0） 、11点（0.0, 0.1, 0.2, ..., 1.0）平均值计算三种方式。 在对系统进行测试时，为了比较新旧两个系统或两个方法，经常使用相对改善的方法，具体的计算公式如下： 在方法1基础上的方法2的改善 = （方法2的性能 — 方法1的性能）/方法1的性能

An evaluation example (SMART) Run number: 1 2 Num_queries: 52 52 Total number of documents over all queries Retrieved: 780 780 Relevant: 796 796 Rel_ret: 246 229 Recall - Precision Averages: at 0.00 0.7695 0.7894 at 0.10 0.6618 0.6449 at 0.20 0.5019 0.5090 at 0.30 0.3745 0.3702 at 0.40 0.2249 0.3070 at 0.50 0.1797 0.2104 at 0.60 0.1143 0.1654 at 0.70 0.0891 0.1144 at 0.80 0.0891 0.1096 at 0.90 0.0699 0.0904 at 1.00 0.0699 0.0904 Average precision for all points 11-pt Avg: 0.2859 0.3092 % Change: 8.2 Recall: Exact: 0.4139 0.4166 at 5 docs: 0.2373 0.2726 at 10 docs: 0.3254 0.3572 at 15 docs: 0.4139 0.4166 at 30 docs: 0.4139 0.4166 Precision: Exact: 0.3154 0.2936 At 5 docs: 0.4308 0.4192 At 10 docs: 0.3538 0.3327 At 15 docs: 0.3154 0.2936 At 30 docs: 0.1577 0.1468

实用系统评测：MAP (Mean Average Precision) rij = 询问Qi 的第j个相关文档的排序 |Ri| =询问Qi 的相关文档数 n = 测试集中询问的个数 E.g. Rank: Q1 Q2 1 4 1st rel. doc. 5 8 2nd rel. doc. 10 3rd rel. doc. 假设Q1 的相关文档数为3， Q2的相关文档数为4，则MAP计算如下： 实例

实用系统评测: MRR 第一个正确答案出现位置的倒数平均值 例子 其中，N代表测试集中的问题数；ranki表示第i 个问题的正确答案的排序。如果正确答案不包含在答案列表中，它的排序为无限大, 取值为零。 例子

信息检索评价试验平台TREC TREC= Text Retrieval Conference 文本检索会议 由美国国家标准与技术局（NIST）和国防部高级研究项目计划局（DARPA）共同发起并主办 TREC并不是一个真正意义上的学术性会议，而是一项致力于对文本信息检索技术进行大规模评价研究的试验活动 TREC的参与者，必须拥有自己研究、开发的检索系统，而且必须提交检索系统的实验数据以参加检索试验和评价。所以，有学者形象地TREC为选拔优秀检索系统的“奥林匹克”。可以说，TREC的出现，开创了检索评价研究的一个新的里程碑

TREC 的组织形式 每年一次； 1~2月份， 欲参加者提出申请（必须有自己设计、开发的系统，3月份评审者确定参加者名单并发送密码给参加者； 4月份，主办者向参加者发送标准实验文档和用户提问；随后参加者进行系统的调试，在8月份左右，将实验数据返回给主办方； 9~10月份，职业的信息分析员进行定量分析和评价，排出名次，并反馈给参加者； 11月份，TREC大会，发言或私下交流。

TREC 评估方法 已知文档集(>100K)与问题集 (50) 每位参加者对每个问题提交1000 个文档 将每位参加者的前100个文档汇集起来，形成一个可能相关的文档“池” ( global pooling) 检索评价专家进行人工判断，评出每一文档的相关性 其它的文档被认为是不相关的 系统的性能以1000个答案来计算

比赛项目分类 特殊检索Ad Hoc : 不同的提问式，在同一个文档集合中进行检索 筛选检索Routing (filtering) : 用户的需求是固定的，文档集合是变化的 跨语言检索Cross-Language: 属于Ad Hoc 检索 网页检索Web: 对WWW文档快照集合进行检索 问答系统Question-Answering: When did Nixon visit China? 交互式检索Interactive: 使用户和系统进行交互 口语文档检索Spoken document retrieval 图像和视频检索Image and video retrieval

TREC的意义 为理论检索模型和试验检索系统提供了公平、定量、具有实用价值的性能评价机会，并为前几位的系统提供了商业机会 开发了新的系统评估方法 促进了相关领域的发展 (NLP, 机器翻译, 摘要, …) 建议成立C-TREC,促进中国信息检索技术的发展

其他研究机构 CLEF = Cross-Language Experimental Forum For European languages Organized by Europeans Each per year (March – Oct.) NTCIR: Organized by NII (Japan) For Asian languages Cycle of 1.5 year

本课的主要研究内容 索引理论：如何最好地表示文档和用户询问的内容，切词、关键词选取 检索模型：如何判断询问和文档之间的关联性 自动索引的基本原理 基于词汇分布特征的索引方法 基于语言规则与内容的索引 人工智能索引法 汉语自动索引 检索模型：如何判断询问和文档之间的关联性 布尔模型（Boolean，1957）：集合论，布尔代数（逻辑操作） 矢量模型(Vector Space Model, VSM，1960s末)：线性代数 概率模型（Probability，1976）：经典概率论 搜索引擎：Web检索实例 信息搜集 预处理 检索服务 信息处理与组织 自动分类与聚类 自动摘要 IR的高级技术（性能改善技术） 自然语言处理、语言模型 多语言检索与分布式检索 用户询问技术