信息科学技术学院 · 网络研究所
信息检索模型
Wang Jimin
Sept. 23, 2005
Outline
_信息检索
信息检索模型
IR模型的形式化表示
IR模型的分类
经典信息检索模型
布尔模型
向量空间模型
经典概率模型
信息检索
信息检索(information retrieval,IR),将信息按一定的方式组织和存储起来,并根据用户的需要找出有关信息的过程.
发展的几个阶段
手工检索(早期,情报检索)
穿孔卡片检索(1950s)
计算机检索(面向主题,1960s)
联机检索(1970s,1980s)
Web检索(1990s)
实例:搜索引擎
搜索引擎(search engine,SE),Web上的一种应用软件系统,它以一定的策略在Web上搜集和发现信息,对信息进行处理和组织后,为用户提供Web信息查询服务
搜索引擎三段式工作流程
搜集
预
处
理
服务
实例:搜索引擎
Docs
Information Need
Index Terms
doc
query
Ranking
match
检索过程
检索过程
User
Interface
Text Operations
Query
Operations
Indexing
Searching
Ranking
Index
Text
query
user need
user feedback
ranked docs
retrieved docs
logical view
logical view
inverted file
DB Manager
Module
4, 10
6, 7
5
8
2
8
Text
Database
Text
Ad hoc retrieval (特别检索: 文档集合保持不变)
Collection
"Fixed Size"
Q2
Q3
Q1
Q4
Q5
IR的两种形式: Ad Hoc and Filtering
Filtering(过滤: 用户需求不变)
Documents Stream
User 1
Profile
User 2
Profile
Docs Filtered
for User 2
Docs for
User 1
IR的两种形式: Ad Hoc and Filtering
现代信息检索的主要内容
建模
文献分类
系统构建
用户界面
数据可视化
信息过滤
查询语言
….
相关概念
停用词(stop word),指文档中出现的连词,介词,冠词等并无太大意义的词.例如在英文中常用的停用词有the,a, it等;在中文中常见的有"是","的","地"等.
索引词(标引词,关键祠):可以用于指代文档内容的预选词语,一般为名词或名词词组.
词干提取(英文中)
countries => country,interesting => interest
组合词: 北京大学
中文切词(word segmentation),或称分词,主要在中文信息处理中使用,即把一句话分成一个词的序列.如,"网络与分布式系统实验室",分词为"网络/ 与/ 分布式/ 系统/ 实验室/".
信息检索模型
信息检索模型(IR model),依照用户查询,对文档集合进行相关排序的一组前提假设和算法.IR模型可形式地表示为一个四元组

其中D是一个文档集合,Q是一个查询集合,F是一个对文档和查询建模的框架,R(qi,dj) 是一个排序函数,它给查询qi和文档 dj 之间的相关度赋予一个排序值
文档逻辑视图
D是一个文档集合,通常由文档逻辑视图来表示.可以是一组索引词或关键词.既可以自动提取,也可以是由人主观指定.
信息检索模型
Q是一个查询集合,用户任务的表达,由查询需求的逻辑视图来表示.
F是一个框架,用以构建文档,查询以及它们之间关系的模型
R(qi,dj) 是一个排序函数,它给查询qi和文档 dj 之间的相关度赋予一个排序值
即: IR模型由上述四个要素组成

信息检索模型的分类
三类: 基于内容的信息检索模型,结构化模型,浏览型数学模型.
基于内容的信息检索模型有
集合论模型:布尔模型,模糊集合模型,扩展布尔模型
代数模型: 向量空间模型,广义向量空间模型,潜在语义标引模型,神经网络模型
概率模型: 经典概率论模型,推理网络模型,置信(信念)网络模型
信息检索模型
结构化模型:非重叠链表模型,临近节点模型
浏览型数学模型:平面(Flat),结构导航(Structure Guided),超文本(Hypertext)
Non-Overlapping Lists
Proximal 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
Structure Guided
Hypertext
信息检索模型的分类
"共有词汇"假设(shared bag of words)
一个查询q = {w1q, …wtq }
一个文档d = {w1, …wt }
ki 和 kj 属于同一个词汇集合∑={k1, …kt }(词典)
和语法无关(词的次序)
和文档结构无关(标题,段落)
和元信息无关(作者,来源,类别等)
这蕴含着:用词汇作为相关性评价的基本依据
依据共有词汇假设的信息获取
存在共有:如果dj有q含有的某些ki , 则relevant(q, dj )=1
全部共有:如果dj有q含有的所有的ki , 则relevant(q, dj )=1
比例共有:如果q和dj 共有多于m%的ki , 则relevant(q, dj)=1
经典信息检索模型
布尔模型
向量空间模型
经典概率模型
布尔检索模型
一种简单的检索模型,它建立在经典的集合论和布尔代数的基础上.
遵循两条基本规则: 每个索引词在一篇文档中只有两种状态:出现或不出现,对应权值为 0或1.
查询是由三种布尔逻辑运算符 and, or, not 连接索引词组成的布尔表达式.
布尔检索模型
首先,将查询转化为一个主析取范式DNF
_例如:查询为
进一步表达为
即:每一个分量都是三元组
的二值向量
(1,1,1)
(1,0,0)
(1,1,0)
Ka
Kb
Kc
布尔检索模型
定义:用qdnf表示查询q的析取范式,qcc表示qdnf的任意合取分量.文献dj
与查询q的相似度为
如果 ,则表示文献dj与q相关,否则为不相关.
sim(dj, q) 为该模型的匹配函数.
布尔检索模型
简单实例
q = 病毒 AND (计算机 OR 电脑)AND NOT医
d1: …据报道,计算机病毒近日猖獗…
d2: …小王虽然是学医的,但对研究电脑病毒也很感兴趣,最近发明了一种…
d3: …计算机程序发现了爱滋病病毒的传播途径…

哪些文档会被检索出来 _
布尔检索模型的特点
优点:简单,易理解,简洁的形式化.
缺点:准确匹配,信息需求的能力表达不足.
向量空间模型
向量空间模型(Vector Space Model, VSM)
相比于布尔模型要求的准确匹配, Salton在60年代末提出的VSM模型采用了"部分匹配"的检索策略(即:出现部分索引词也可以出现在检索结果中).
_通过给查询或文档中的索引词分配非二值权值来实现.
向量空间模型
词典, ∑={k1,k2,…kt}
d=
–此时,变量wi称为权值,非负;表示对应词项ki对于判断d和查询q相关性的重要程度(注意,这里的q是一般的,而d是具体的)
q=
–变量vi的含义类似于wi
两个基本问题:如何定义wi和vi;如何计算R(d,q)
向量空间模型
让wi和vi为对应的词分别在d和q中出现的次数,于是我们有了两个m维向量,用夹角的cos表示"接近度",即
R(d,q) = cos(d,q) = d·q/|d|×|q|
认为:–cos(di,q) > cos(dj,q),则di比dj与q更相关.
通常系统就会取前若干个结果返回给用户
–例如天网返回3000,虽然可能查出了几十万
向量空间模型
权值w_ij的选取方法:
对文档向量d_j的构造,考察:
局部权值 tf_ij=f_ij / max{f_ij}
全局权值 idf_i=log(N/ni)
索引词权值: wij= tf*idf
_查询向量的构造:索引词权值:
wij= (0.5+ 0.5 * fij / max{f_ij})* idf
向量空间模型
重要的学术贡献,用了几十年
–G. Salton and M. E. Lesk, "Computer evaluation of indexing and text processing," Journal of the ACM, 15(1):8-38, January 1968.
–G. Salton, The SMART Retrieval System – Experiments in Automatic Document Processing. Prentice Hall Inc., 1971.
实践证明,尽管VSM在许多方面依然和"现实"都不符,但实际效果不错(至少比布尔模型好很多)
向量空间模型
综合题(19分):按照下述描述和要求完成相关工作
给定文档语料:
d1: 北京安立文高新技术公司
d2: 新一代的网络访问技术
d3: 北京卫星网络有限公司
d4: 是最先进的总线技术...
d5: 北京升平卫星技术有限公司的新技术有...
向量空间模型
利用中文切分词软件,分别得到用"/"分开的一些字词:
d1: 北京/ 安/ 立/ 文/ 高新/ 技术/ 公司/
d2: 新/ 一/ 代/ 的/ 网络/ 访问/ 技术/
d3: 北京/ 卫星/ 网络/ 有限/ 公司/
d4: 是/ 最/ 先进/ 的/ 总线/ 技术/ ...
d5: 北京/ 升/ 平/ 卫星/ 技术/ 有限/ 公司/ 的/ 新/ 技术/ 有...
向量空间模型
你的任务是设计一个针对这些文档的信息检索系统.具体要求是:
(1). 给出系统的有效词汇集合(说明取舍原因). (2). 写出d1和d2在VSM中的表示(使用tf*idf,写出各项的数字表达式,具体数值不必实际计算出来). (3). 画出系统的倒排文件示意图. (4). 按照向量夹角的余弦计算公式,给出针对查询"技术的公司"的前3个反馈结果.
向量空间模型
特点:基于多值相关性判断,基于统计学方法的词加权处理模式,采用检索结果的排序输出策略.
概率模型
概率论模型,亦称为二值独立检索模型.
_1976年由Roberston和Sparck Jones提出的经典概率模型.在概率的框架下解决IR的问题.
_给定一个用户查询,存在一个文档集合,该集合只包括与查询完全相关的文档而不包括其他不相关的文档,称该集合为理想结果集合.
如何描述这个理想结果集合 即:该理想结果集合具有什么样的属性
_基于相关反馈的原理,需要进行一个逐步求精的过程
PRP (probability ranking principle)
将信息获取看成是一个过程:用户提交一个查询,系统提供给用户它所认为的相关结果列表;用户考察这个集合后给出一些辅助信息,系统再进一步根据这辅助信息(加上以前的信息)得到一个新的相关结果列表;如此继续.
如果每次结果列表中的元素总是按照和查询相关的概率递减排序的话,则系统的整体效果会最好.
其中概率的计算应该是基于当时所能得到的所有信息.
概率模型--相关概念
_贝叶斯定理:
词条的独立假设:P(AB)= P(A) P(B) 当且仅当 A与B相互独立
由此对一篇文档而言,若文档中的各个索引词相互独立,则有
P(dj)=P(k1)…P(kt)
概率模型—
定义:设索引词的权重为二值的,即:
R表示已知的相关文档集(或最初的猜测集),用 表示R的补集. 表示文档dj与查询q相关的概率, 表示文档dj与查询q不相关的概率.文档dj与查询q的相似度sim(dj, q)可以定义为:
概率模型
根据贝叶斯定理有
_
概率模型
假设标引词独立,则
这是概率模型中排序计算的主要表达式.
概率模型
取对数,在相同背景下,忽略对所有因子保持恒定不变的因子,则有
概率模型
如何计算上式中的 和 呢 简单假设作为最初的猜测
1). 对所有的索引词ki是恒定不变的,通常取为0.5,即
2). 不相关文档中的索引词ki的分布可以通过文档集中索引词的分布来估计,即
其中,ni表示包含索引词ki的文档数, N表示集合中的文档总数.
_
初始值确定后,根据与查询q相关的大小进行初步排序,取前若干个文档作为相关查询集合.之后通过如下方法进行改进(即开始递归计算).
概率模型
用V表示概率模型初步检出并经过排序的文档子集
Vi表示V中包含索引词ki的文档数.
_改进 和 的过程如下:
1)用已经检出的文档中索引词ki的分布来估计
2). 假定所有未检出的文档都是不相关的来估计
如此递归重复这一过程,得到理想结果集合
概率模型
对较小的V和Vi上述计算会出现问题,如V=1和Vi=0,可做一些改进:
调整因子也可以为ni/N, 即
概率模型
该方法的缺点:
不考虑索引词在文档中出现的频率,所有权值都是二元的.
索引词之间相互独立的假设.
Outline
_信息检索
信息检索模型
IR模型的形式化表示
IR模型的分类
经典信息检索模型
布尔模型
向量空间模型
经典概率模型
Reference
Ricardo Baeza-Yates, Berthier Ribiero-Neto and Berthier Ribeiro-Neto. 1999. Modern Information Retrieval. Addison-Wesley. P1-34. _
李晓明, 闫宏飞, 王继民. 搜索引擎原理,技术与系统 [M], 北京:科学出版社, 2005.
Thank you!