陆铭 66134922 richard.lu@shu.edu.cn mingler.ccshu.org 第二讲　信息检索模型研究 陆铭 66134922 richard.lu@shu.edu.cn mingler.ccshu.org.

Presentation on theme: "陆铭 66134922 richard.lu@shu.edu.cn mingler.ccshu.org 第二讲　信息检索模型研究 陆铭 66134922 richard.lu@shu.edu.cn mingler.ccshu.org."— Presentation transcript:

1 陆铭 66134922 richard.lu@shu.edu.cn mingler.ccshu.org
第二讲　信息检索模型研究 陆铭 mingler.ccshu.org

2 内容提要 检索模型的基本概念与分类 布尔模型 向量模型 概率模型 其他模型 结构模型 浏览模型 统计语言建模 国内外检索模型理论研究现状

3 检索模型的基本概念——1.信息检索模型 信息检索模型是指如何对查询和文档进行表示，然后对它们进行相似度计算的框架和方法
本质上是对相关度建模 信息检索模型是IR中的核心内容之一

4 检索模型的基本概念——2.相关概念 标引项(Index Term) 标引项的权重(Weight) 文档表示成多个Term的集合
通常用词来表示，但是也可以用其他语言单位来表示 关键词(key words) 可以看成Term的一种 标引项的权重(Weight) 不同标引项作用是不同的 通过权重加以区分

5 检索模型的基本概念——3.检索模型的定义 信息检索模型是描述信息检索中的文档、查询和它们之间的关系(匹配函数)的数学模型。 模型F 文档 D
Q 匹配函数 R(qi,dj) 文档是文献在系统中的存储形式，主要由词构成。词包括关键词或标引词 查询反映了用户表达的信息需求 匹配函数把经过处理的文献表示和查询表示同时放在系统中进行匹配，通过设置不同的匹配函数得到不同的输出结果

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

7 检索模型的基本概念——5.文档逻辑视图 文档逻辑视图D：

8 检索模型的基本概念——6.检索模型的分类 三种主要类型 基于内容的信息检索模型有 基于内容的信息检索模型 结构化模型 浏览型数学模型
集合论模型 布尔模型、模糊集合模型、扩展布尔模型 代数模型 向量空间模型、广义向量空间模型、潜在语义标引模型、神经网络模型 概率模型 经典概率论模型、推理网络模型、置信（信念）网络模型

9 检索模型的基本概念——7.检索模型分类 结构化模型 非重叠链表模型 临近节点模型 浏览型数学模型 平面文本 (Hypertext)

10 检索模型的基本概念——检索模型分类 信息检索模型 检索模型 浏览模型 内容模型 结构模型 布尔 模型 向量 概率 非重叠 链表模型 邻近节
点模型 平坦 结构导 向模型 超文本

11 检索模型的基本概念——8.理论研究历史 描述查询的结构化阶段 描述相关性的量化阶段 布尔检索模型 向量空间模型 概率模型 1960’s
1986 Rijsbergen逻辑模型 1960’s

12 检索模型的基本概念——理论研究历史 定性评价与定量计算相结合的阶段 逻辑模型 1986 Rijsbergen逻辑模型 1960’s

13 基于集合论的IR模型(Set Theoretic models)
布尔模型 扩展布尔模型

14 布尔模型——1.定义 一种简单的检索模型，它建立在经典的集合论和布尔代数的基础上 基本原理
系统索引词集合中的每一个索引词在一篇文档中只有两个状态 出现 不出现 检索提问式q由三种布尔运算符 “and”、“or”、“not”连接索引词来构成

15 布尔模型——2.集合的直观描述 具有某种属性的对象总体(通常用大写字母表示，如A,B等)，这些对象称为其元素(通常用小写字母表示，如x,y等) x是A的元素记为：x∈A (读作x属于A) x不是A的元素记为：x∉A (读作x不属于A) 集合的基本特性是，对于给定的集合A，任何对象x, x∈A与x∉A中有且只有一个成立.

16 布尔模型——3.集合论 集合的几种表示 具有某种属性的事物的全体就构成一个集合，以 A,B,C,…表示构成集合的事物，以 a,b,c,…表示该集合的元 某个图书馆现存的所有图书——有限集 以 S1＝ {a,b,c,d}表示 所有的正整数——无限集 以 S2＝ {1,2,3,4,…}表示 P(x)表示与元x有关的一个属性 S3＝ {x|x是正偶数} S4＝ {x|1<x<10 } 为空集

17 布尔模型——4.集合的表示 集合间的关系 集合的图形表示 x是A中的一个元，记作x ∈ A x不是A中的一个元，记作x ∉ A 集合A 元x
空间E 集合A 元x

18 布尔模型——5.集合的运算 并运算 设A，B是两个集合，集合A与B的并运算是由A的一切元素和B的一切元素所组成的集合，记做 A∪B，数学表示为： 设 A={a,b,c,d,e}，B={c,d,x,y,z} 则 A∪B={a,b,c,d,e,x,y,z} 即 A∪B={x|x∈A∨x∈B } A B 空间E

19 布尔模型——6.集合的运算 交运算 设A，B是两个集合，包含A和B的所有公共元素的集合叫做A与B的交集，记做 A∩B，数学表示为：
设 A={a,b,c,d,e}，B={c,d,x,y,z} 则 A∩B={c,d} 即 A∩B={x|x∈A∧x∈B }

20 布尔模型——7.集合的运算 差运算 设A，B是两个集合，A-B是由一切属于A但不属于B的元素所组成的集合，称为B在A中的余集，或者A与B的差，即 设 A={a,b,c,d,e}， B={c,d,x,y,z} 则 A-B={a,b,e}， B-A={x,y,z} 数学表示为 A-B={x|x∈A﹁x∈B }

21 布尔模型——8.布尔代数 布尔变量 1849年英国数学家乔治.布尔(George Boole)首先提出，用来描述客观事物逻辑关系的数学方法——称为布尔代数 后来被广泛用于开关电路和数字逻辑电路的分析与设计，所以也称为开关代数或逻辑代数 逻辑代数中用字母表示变量——逻辑变量 每个逻辑变量的取值只有两种可能——0和1 它们也是逻辑代数中仅有的两个常数 0和1只表示两种不同的逻辑状态，不表示数量大小

22 布尔模型——布尔代数 与运算 真值表 A B Y 1 A B Y 只有输入全为1时，输出才为1
1 只有输入全为1时，输出才为1 决定事件的全部条件都满足时，事件才发生——这就是与逻辑关系。 在函数式中，用表示与运算，记做 Y=AB 或Y=AB

23 布尔模型——布尔代数 或运算 真值表 A B Y 1 输入全部为0时，输出为0 A B Y
1 决定事件的全部条件至少有一个满足时，事件就发生——这就是或逻辑关系。 在函数式中，用＋ 表示或运算，记做 Y=A＋B

24 布尔模型——布尔代数 非运算 真值表 A Y 1 A R Y 该图代表的逻辑关系是：决定事件的条件满足时，事件不发生——这就是非逻辑关系。
1 该图代表的逻辑关系是：决定事件的条件满足时，事件不发生——这就是非逻辑关系。 在函数式中，用_ 表示非运算，记做 Y=A

25 布尔模型—— Bag of Terms Example
Doc 1 Doc 2 aid 1 all back brown come dog fox good jump lazy men now over party quick their time Document 1 The quick brown fox jumped over the lazy dog’s back. Stopword List for is of Document 2 the to Now is the time for all good men to come to the aid of their party. Start: 1:35 Questions: What is the consistent order in this case? Why is a consistent order needed? How are the terms chosen in this case? Stopword lists eliminate terms that only convey meaning through word order Observations: No need to keep a position for terms that never occur 9

26 布尔模型—— Boolean Free Text Example
quick brown fox over lazy dog back now time all good men come jump aid their party 1 Term Doc 1 Doc 2 Doc 3 Doc 4 Doc 5 Doc 6 Doc 7 Doc 8 dog AND fox Doc 3, Doc 5 dog NOT fox Empty fox NOT dog Doc 7 dog OR fox Doc 3, Doc 5, Doc 7 good AND party Doc 6, Doc 8 good AND party NOT over Doc 6 Start 1:50 12

27 布尔模型——布尔代数 布尔运算的性质和定理 交换律 AB=BA A+B=B+A
结合律 A+(B+C)=(A+B)+C A(BC)=(AB)C 分配律 A(B+C)=AB+AC A+(BC)=(A+B)(A+C)

28 布尔模型——布尔代数 布尔变量 布尔操作(关系) 布尔表达式 只有“真”、“假”取值的变量
计算机中常常用1表示“真”true，0表示“假”false 布尔操作(关系) 与(AND)：(A AND B) = true iffA=true and B=true 或(OR) ：(A OR B) = true iffA=true OR B=true 非(NOT) ：(NOT A) = true iffA=false 布尔表达式 多个布尔变量之间通过布尔操作组成的表达式 如：A AND (B OR C) AND NOT D 蕴含：两个布尔表达式P、Q，如果A为true，那么Q为true，则称P蕴含Q，记为PQ

29 布尔模型 布尔模型 查询和文档均表示为Term(“是否存在”)的布尔表达式，其中文档表示成所有Term(存在)的“与”关系布尔表达式。 例子(因不会产生歧义，以下例子直接用Term进行布尔操作)： 查询：2010 AND 世界杯AND NOT 小组赛 文档1：2010年世界杯在南非举行 文档2：2006年世界杯小组赛已经结束 相似度计算 查询布尔表达式和所有文档的布尔表达式进行匹配，匹配成功的文档的得分为1，否则为0 类似于传统数据库检索，是精确匹配

30 布尔模型 遵循两条基本规则 每个索引词在一篇文档中只有两种状态：出现或不出现，对应逻辑值为 0 或 1
查询是由三种布尔逻辑运算符 and, or, not 连接索引词组成的布尔表达式

31 布尔模型——9. 形式化表示 任意查询都可转化为一个主析取范式DNF 例如：查询为q=ka∧(kb∨¬kc)可表示为
q=ka∧(kb∨¬kc)=kakbkc∨kakb¬kc∨ka¬kb ¬kc qbnf=(1,1,1)∨(1,1,0)∨(1,0,0) 即：每一个分量都是三元组的二值向量 任一文本可以写成所有Term的交，如doc=a∧b∧c∧d∧e 因为doc(蕴含)q，所以相似度为1  在布尔逻辑中，析取范式(DNF)是逻辑公式的标准化(或规范化)，它是合取子句的析取。作为规范形式，它在自动定理证明中有用。一个逻辑公式被认为是 DNF 的，当且仅当它是一个或多个文字的一个或多个合取的析取。同合取范式(CNF)一样，在 DNF 中的命题算子是与、或和非。非算子只能用做文字的一部分，这意味着它只能领先于命题变量。例如，下列公式都是 DNF: 但如下公式不是 DNF: NOT 是最外层的算子 一个 OR 嵌套在一个 AND 中 把公式转换成 DNF 要使用逻辑等价，比如双重否定除去、德·摩根定律和分配律。注意所有逻辑公式都可以转换成析取范式。但是，在某些情况下转换成 DNF 可能导致公式的指数性爆涨。例如，在 DNF 形式下，如下逻辑公式有 2n 个项:

32 布尔模型 定义 sim(dj, q) 为该模型的匹配函数(相似度)
用qdnf表示查询q的析取范式，qcc表示qdnf的任意合取分项，文献dj 与查询q的相似度为 如果 ，则表示文献dj与q相关，否则为不相关。 sim(dj, q) 为该模型的匹配函数(相似度)

33 布尔模型 简单实例 写出DNF，哪些文献会被检索出来？ q = 病毒 AND（计算机 OR 电脑）AND NOT医
q=A(B+C)~D =(AB+AC) ~D =AB~D+AC~D =AB(C+~C) ~D+A(B+~B)C~D =ABC~D+AB~C~D+ABC~D+A~BC~D A B C D d1 1 d2 d3 A B C D d1 d2 d3

34 布尔模型——10. 优缺点 布尔模型的优点 布尔模型的缺点 布尔模型目前仍然是商业文档数据库的主流模型，并为一些新的领域提供了一个好的起点
简单而整齐，为现代许多商业系统所用 自我保护功能，降低用户对搜索系统的期望，使自己不在责任方，检索结果不好的原因在于用户构造查询不好 简单、易理解、简洁的形式化 布尔模型的缺点 它的检索策略是基于二值决策准则，即一个文档只被判断成相关的或不相关的，无任何等级变化 当用布尔表达式表示精确语义的时候，很难将信息表达为一个布尔表达式 准确匹配，信息需求的能力表达不足 布尔模型目前仍然是商业文档数据库的主流模型，并为一些新的领域提供了一个好的起点 布尔模型的优点 布尔模型为普通用户提供了一个容易掌握的框架。在模型中，查询被描述为具有精确语义的布尔表达式，其特点简单而整齐，为现代许多商业系统所用 只能严格匹配(得分不是0就是1)，不能近似或者部分匹配，多个结果无法排序 􀂄一般用户构造查询不是很容易，构造不利可能造成结果过多或者过少

35 布尔模型——布尔模型的改进 布尔模型的典型问题 扩展布尔模型 两个索引词 k1 and k2 and k3 and ……and k8
含有7个k和0个k的文献一样被排除 k1 or k2 or k3 or ……or k8 含有8个k和含有1个k的文献没有区别 扩展布尔模型 两个索引词

36 布尔模型——扩展布尔模型 ky kx 如果权值是布尔型的，则文献总是处于4个角上（0,1）（0,1）（1,0）（1,1）

37 基于代数论的IR模型(Algebraic models)
向量空间模型

38 向量模型——1. n维向量 考虑从空间坐标系原点出发（其他向量可以平移到原点出发）的向量 ，其终点坐标为<x1,x2,…,xn>，我们称之为一个n维向量 向量的运算 加、减、倍数、内积

39 向量模型——2. 空间概念 文献空间 标引词空间 如果把每个标引词看作是一个向量，代表了空间的一个维，则由这些标引词集合定义了一个空间
文献集合中的任一文献都可以表示为这个多维空间中的一个向量，这个空间就成为“文献空间” 标引词空间 文献集合中的一篇文献可看成是标引词空间的一个维，空间中的一点代表一个标引词点 从原点到该点的向量就是一个标引词向量 它在各个轴上的分量就是该标引词在各个轴所代表的相应文献中的权重

40 向量模型——3. 文档-标引项矩阵(Doc-Term Matrix)
文献-标引项矩阵 n篇文档Tn，m个标引项Dm构成的矩阵Am*n 每列可以看成每篇文档的向量表示 每行也可以可以看成标引项的向量表示 T T T D1 d11 d12 d A33 = D2 d21 d22 d D3 d31 d32 d33 D1={d11,d12,d13} D2={d21,d22,d23} D3={d31,d32,d33} T1 T2 T3

41 向量模型——4. 向量的概念 | | 向量： 既有大小又有方向的量 向量表示： 或 向量的模： 向量的大小 或 单位向量： 模长为1的向量
| | 单位向量： 模长为1的向量 或 零向量： 模长为0的向量

42 向量模型——向量的概念 自由向量： 不考虑起点位置的向量 相等向量： 大小相等且方向相同的向量 负向量： 大小相等但方向相反的向量 向径：
空间直角坐标系中任一点 与原点构成的向量

43 向量模型—— 5. 向量的模、距离和夹角 向量的模 向量的(欧氏)距离 向量的夹角

44 向量模型——6. 向量加法的运算规律 （1）交换律： （2）结合律： （3） 减法运算

45 向量模型——7. 模型含义 向量空间模型(Vector Space Model, VSM)
由康奈尔大学Salton等人在上世纪70年代末提出并倡导的，原型系统为SMART* 该模型采用了“部分匹配”的检索策略，即：出现部分索引词也可以出现在检索结果中，以克服布尔模型的缺点  通过给查询或文档中的索引词分配非二值权值来实现 查询和文档都可转化成Term及其权重组成的向量表示，并可以看成空间中的点。向量之间通过距离计算得到查询和每个文档的相似度 * 可从ftp://ftp.cs.cornell.edu/pub/smart/下载全部源码和相关语料

46 向量模型——模型含义 向量模型通过分派非二值权重给查询和文档中的索引项来实现检索目标
这些权重用于计算系统中的每个文档与用户的查询请求的相似程度，向量模型通过对文档按照相似程度降序排列的方式，来实现文档与查询项的部分匹配 结果中的文档排列顺序比通过布尔模型得到的结果要合理得多

47 向量模型——模型含义 在该模型中，与（ki，dj）相关联的权重wi,j是一个非二值数
查询中的索引项也是有权重的，设wi,q是与（ki，q）相关联的权重，且wi,q≥0，则查询向量Q被定义成 Q=（w1,q，w2,q，w3,q…………wt,q） 其中，t是系统中所有索引项的数目， 文档dj的向量可以表示为 wj=（w1,j，w2,j，w3,j………wt,j）， 向量模型通过wj和Q的相关度来评价文档dj和查询q的相关度。这种关系可以用定量表示，一般使用两个向量之间的夹角余弦值来计算

48 向量模型——模型含义 变量wi称为权值，非负 两个基本问题：
表示对应词项ki对于判断d和查询q相关性的重要程度（注意，这里的q是一般的，而d是具体的） q=<v1,v2,…vt> 变量vi的含义类似于wi 两个基本问题： 如何定义wi和vi 如何计算R(d, q)

49 向量模型——模型含义 设wi和vi为对应的词分别在d和q中出现的次数，于是我们有了两个m维向量，用夹角的cos表示“接近度”，即

50 向量模型——8. 例子 查询q：(<2010,1>,<世博会,2>)
文档d1：(<2010,1>,<世博会,3>,<中国,1>,<举行,1>) 文档d2：(<2005,1>,<世博会,2>,<1970,1>,<日本,1>,<举行,1>) 2005 2010 世博会 中国 1970 日本 举行

51 向量模型——例子 查询和文档进行向量的相似度计算： 采用内积： 夹角余弦： 文档d1与q的内积：1*1+3*2=7

52 向量模型—— 9. 权重规范化 不进行权重规范化，检索结果因文献篇幅的长短而存在不合理现象
长文献词量大，同一词词频更大，命中的概率更大 长文献中不同的词量大，增加了查询和文献的相似度 Normalization seeks to remove these effects Related somehow to maximum term frequency But also sensitive to the number of terms

53 向量模型—— Cosine‘s Normalization
Compute the length of each document vector Multiply each weight by itself Add all the resulting values Take the square root of that sum Divide each weight by that length

54 向量模型—— 10. 项向量的规范方法 布尔权重 term i在文档j中的权重aij=0or 1(出现则取1，否则取0)
TF权重：TF(Term Frequency)是term在文档中出现的次数。权重aij=TFij或者归一化后的TF值 TF的归一化(Normalization) ：将一篇文档中所有Term的TF值归一化到[0,1]之间。通常可以采用以下三种方式之一 Maximum Normalization [1,2,1,0,4][0.25,0.5,0.25,0,1] Augmented Maximum Normalization [1,2,1,0,4] [0.625,0.75,0.625,0.5,1] Cosine Normalization [1,2,1,0,4] [0.213,0.426,0.213,0,0.852]

55 向量模型——11. 确定权重的方法 How to Weighting? N 文献数 ni 文献集合中包含标引词 ki的词频
freqi,j 某篇文献dj中包含标引词ki的词频(描述能力) fi,j 词频的规范化值（局部权值,描述能力） idfi 标引词ki的逆词频值 （全局权值,区分能力 ）

56 向量模型——确定权重的方法 文档向量权值 tf/idf 查询向量的构造：索引词权值: WI,q 索引词权值wij= tf*idf

57 向量模型——12. TF*IDF Example

58

59 向量模型—— Weighted Matching Schemes
未予加权的查询权重 计算全部匹配词的权重和 用户指定查询词的权重 计算每一词的查询权重和文献权重的积 计算这些词权重积的和 自动计算查询权重 多数查询的词频TF无用, 但 IDF有价值 实践中使用用户指定的查询词权重

60 向量模型 向量模型的优点 索引项的加权改善了检索的性能，其部分匹配的策略允许所检索的文档与查询条件相近似，其余弦排序公式按照文档与查询的相似程度对文档进行排序 向量模型的缺点 索引项被假设为彼此之间相互独立的，然而在实际中，考虑索引项之间的相关性也许是个缺陷 由于许多索引项之间的相关性具有局限性，不加区别地将其应用到所有文档中，会影响检索系统的整体性能

61 向量模型——13. 对模型的评价 重要的学术贡献，已用了几十年 实践证明，尽管VSM在许多方面依然和“现实”都不符，但实际效果不错
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在许多方面依然和“现实”都不符，但实际效果不错 为什么比布尔模型好很多？

62 向量模型——14. 向量模型的改进 标引词位置加权 辅助主题词表 个性化协同检索设计 结构位置 重点句位置
标题、摘要、关键词、正文、结论和超连接 重点句位置 综上所述、结束语、主要在于 辅助主题词表 将带修饰和限制作用的词——形容词和副词做成辅助主题词表，用以扩展用户查询 将检索关键词和字典库中的同义词和修饰词结合起来，形成新的查询，提高了检索的效率 个性化协同检索设计 将每次的检索结果、用户兴趣等建立个性化信息库，并进行信息反馈，定期刷新，不断充实

63 课后练习 利用夹角余弦方式(向量的分量采用TF表示) 进行计算(s=0.2，文档长度以字节数表示，1个汉字以2个字节计算，不含标点和空格)，写出计算过程，并判断哪篇文档和查询q更相关(不去除停用词)。 查询q：2010 亚运会 举办地 文档d1：第十六届亚运会2010年11月在广州开幕 文档d2：第11届亚运会在中国北京举行，参赛国家37个 如何判断两个文档之间是否存在抄袭？

64 基于概率统计的IR模型(Probabilistic models)
概率模型

65 概率模型 随机现象与随机事件 事件有多种不同的结果，在同样的条件下进行一系列重复试验，每次出现的结果都不能预先确定的事件称为随机事件
随机现象在每次试验中的结果虽然是不确定的，但在大量重复试验下，各种不同结果出现的可能性的大小是具有规律性的 例如，统计大量的新生儿的性别，男女约各占50％，多次抛一枚均匀的硬币，正反面出现的次数约各占50％ 为研究随机现象的统计规律性而进行的试验称为随机试验。用字母Ｅ来表示。

66 概率模型 随机试验具有下面三个特点 1. 在相同条件下可以重复进行 2. 试验前不能确定出现哪种结果 3. 能够知道可能出现的所有结果 在随机试验中出现的每一个结果，称为随机试验的基本事件。全体基本事件组成的集合称为样本空间Ｕ。例如，上面举过的例子中， 和 样本空间Ｕ的子集称为随机事件。因此，随机事件是指随机试验出现的一种结果或几种结果的总和。用A、B、C等表示。 样本空间Ｕ表示必然事件，空集 表示不可能事件

67 概率模型——1. 事件的关系和运算 事件的包含和相等 事件的和
如果事件A发生必然导致事件B发生，那么称事件A包含于事件B，或称事件B包含事件A，记作　　 例如，掷一枚骰子， 如果 ，同时 ，则称A＝B 事件的和 事件A发生或事件B发生，称为事件A与事件B的和，记作A＋B。 事件A发生或事件B发生，换句话说，就是事件A和事件B至少有一件发生。

68 概率模型 例如：分析下列事件的关系 解： ⑴ 随机抽查一批产品的质量，记 ⑵抛两枚硬币，记 ⑴ 事件A发生则事件B一定发生了，所以
C＝{不出现反面朝上} D＝{两个都是正面朝上} 解： ⑴ 事件A发生则事件B一定发生了，所以 ⑵ 抛两枚硬币，不出现反面朝上，即出现两个正面，显然C＝D

69 概率模型 (3) 以直径和长度两项指标衡量产品的质量，设 解
A＝{零件直径不合格}，B＝{零件长度不合格}, E＝{零件不合格}, 试用事件A、B表示E 解 事件E发生，表示或者事件A发生或者事件B发生或者事件A、B同时发生，即事件A、B至少有一件发生 故 E＝A＋B (4) 从一批产品中任意取出2件，A1＝{恰好有1件是次品}，A2＝{恰好有2件是次品}，试用A1、A2表示事件B＝{至少有1件是次品} 至少有1件是次品的意思是说，恰好有1件是次品，或者2件都是次品 因此 B＝A1＋ A2

70 概率模型 事件的积 解 事件的差 事件A和事件B同时发生，称为事件A与事件B的积，记作AB
例如，设C＝{零件的直径合格}, D＝{零件的长度合格}, F＝{零件合格}，试用事件C、D表示F 解 只有零件的直径和长度都合格，零件才算合格，因此事件F发生时，事件C、D都要发生。也就是说，事件C、D同时发生，才表示事件F发生，即 F＝CD 事件的差 事件A发生而事件B不发生，称为事件A与事件B的差，记作A－B

71 概率模型 互不相容事件 对立事件与完备事件组 事件A与事件B互为对立事件是说
如果事件A与事件B不可能同时发生，则称事件A与事件B互不相容或互斥。显然：AB＝ 对立事件与完备事件组 对立事件是一种特殊的互不相容事件。如果事件A与事件B不能同时发生，而事件A与事件B又必发生其一，则称事件A和事件B是对立事件，即事件A是事件B的反面，称为B非，记作 事件A与事件B互为对立事件是说 它们满足AB＝ ，A＋B＝Ｕ 显然，

72 概率模型 重新认识事件的差 事件的差 ，而 可见，事件A－B和事件B－A是不同的。
事件的差 ，而 可见，事件A－B和事件B－A是不同的。 如果有n个事件 两两互不相容，而他们的和是必然事件，则称事件 构成一个完备事件组

73 概率模型——2. 事件的运算律

74 概率模型——3. 例题 对飞机连续射击两次，每次发射一枚炮弹，设A1＝{第一枚击中飞机}，A2＝{第二枚击中飞机}，试用A1，A2及它们的对立事件表示以下事件： B＝{两弹都击中飞机}，C＝{两弹都没有击中飞机}，D＝{恰有一弹击中飞机}，E＝{至少有一弹击中飞机} 解： B＝A1A2， ，D＝ ， E＝A1＋A2 其中B与C，B与D，C与D，C与E都是互不相容事件，C与E是对立事件

75 概率模型——4. 随机事件的概率 概率的统计意义 随机事件在随机试验中发生的可能性大小的数值称为概率
在条件不变的情况下重复进行n次试验，事件A发生了m次，那么m称为A事件发生的频数，比值 称为事件A发生的频率，用fn(A)表示。 如果当n足够大时，事件A的频率fn(A)在一个常数p(0≤p≤1)附近摆动，则称事件A为随机事件，p为事件A在该条件下发生的概率，记作P(A)＝p 必然事件 P(A)＝1 不可能事件 P(A)＝0

76 概率模型——5. 概率性质 性质1 对于任一事件A， 性质2 性质3 对于有限个两两互不相容的事件 [推论] 如果 则
这是因为，任一事件A的频数m≥0，m≤n 性质2 性质3 对于有限个两两互不相容的事件 即 [推论] 如果 则

77 概率模型——6. 古典概型 古典概型是指等可能事件的概率模型 例1，掷一枚骰子，求C＝{4,5,6}和D＝{4,6}的概率 解
如果一次试验有n种可能的结果，且这n种结果出现的可能性都相同，而事件A包含了这n种可能中的k种可能，则事件A发生的概率为P(A)＝k／n，这种概率称为古典概率 例1，掷一枚骰子，求C＝{4,5,6}和D＝{4,6}的概率 解 掷一枚骰子出现的点数有6种可能，这6种点数的可能性是相同的，属于古典概型 其中C占了3种可能出现的情况，D占了2种可能出现的情况，故P(C)＝3／6，P(D)＝2／6

78 概率模型——7. 贝叶斯(Bayes)定理 贝叶斯定理给出了两个条件概率p(Bi|A)和p(A|Bi)之间的关系 贝叶斯定理的例子
三个抽屉分别装有金币和银币 B1: 两个金币 B2: 一个金币和一个银币 B3: 两个银币 随机地选一个抽屉并从中取出一个钱币，假定取出的是一个金币，求同一抽屉中另一个钱币是金币的概率

79 概率模型 第一次取出金币的事件，另一个钱币也是金币条件要求只能选取B1,即要求的是在A发生的条件下，选择抽屉B1的概率： p(B1|A)
在选定抽屉的情况下，取出一个金币的概率 P(A|B1)=1, p(A|B2)=0.5, p(A|B3)=0 选择某一抽屉的概率 p(B1)=p(B2)=p(B3)=1/3 由贝叶斯定理

80 概率模型 概率模型试图在一个概率框架中处理信息检索问题，其基本思想是：给定一个用户的查询，则有一个包含相关文档且不包含不相关文档的集合。设想这个文档集合是一个理想的结果集。给出这个理想结果集的描述，并用于检索。 这样，我们可以认为查询的过程是说明理想结果集属性的过程，初始的时候努力的猜测它们是什么，猜测结果我们将产生一个对理想结果集的概率描述，检索出最初的结果集，然后引入用户的交互，改善结果集。

81 概率模型 基本假设 给定一个查询q和文档集中一个文档dj，概率模型试图找出用户对其感兴趣的概率 模型假设这个概率只是依赖于查询和文档的表示，进而模型假设文档集中存在一个子集，它使得总体相关概率在集合中的文档被认为是与查询相关的，不在集合中的则被认为是不相关的

82 概率模型——8. 模型原型 概率论模型，亦称为二值独立检索模型 如何描述这个理想结果集合？
 1976年由Roberston和Sparck Jones提出的经典概率模型。它企图在概率的框架下解决IR的问题  给定一个用户查询，存在一个文档集合，该集合只包括与查询完全相关的文档而不包括其他不相关的文档，称该集合为理想结果集合 如何描述这个理想结果集合？ 即：该理想结果集合具有什么样的属性？  基于相关反馈的原理，需要进行一个逐步求精的过程

83 概率模型—9. PRP (Probability Ranking Principle)
将信息获取看成是一个过程 用户提交一个查询，系统提供给用户它所认为的相关结果列表 用户考察这个集合后给出一些辅助信息 系统再进一步根据这辅助信息(加上以前的信息)得到一个新的相关结果列表；如此继续。 如果每次结果列表中的元素总是按照和查询相关的概率递减排序的话，则系统的整体效果会最好 概率的计算基于当时所能得到的所有信息

84 概率模型——10. 贝叶斯定理 贝叶斯定理 词条的独立假设 对一篇文档而言，若文档中的各个索引词相互独立，则有
 贝叶斯定理 词条的独立假设 P(AB)= P(A) P(B) 当且仅当 A与B相互独立 对一篇文档而言，若文档中的各个索引词相互独立，则有 P(dj)=P(k1)…P(kt)

85 概率模型——11. 模型定义 定义 设索引词的权重为二值的，即：
R表示已知的相关文档集（或最初的猜测集），用 表示R的补集。 表示文档dj与查询q相关的概率， 表示文档dj与查询q不相关的概率。文档dj与查询q的相似度sim(dj, q)可以定义为：

86 概率模型—— 根据贝叶斯定理有

87 概率模型—— 假设标引词独立，则 这是概率模型中排序计算的主要表达式

88 概率模型—— 取对数，在相同背景下，忽略对所有因子保持恒定不变的因子，则有

89 概率模型—— 如何计算上式中的 和 呢 ？ 简单假设作为最初的猜测
如何计算上式中的 和 呢 ？ 简单假设作为最初的猜测 1) 对所有的索引词ki是恒定不变的，通常取为0.5，即 2) 不相关文档中的索引词ki的分布可以通过文档集中索引词的分布来估计，即 其中，ni表示包含索引词ki的文档数， N表示集合中的文档总数 初始值确定后，根据与查询q相关的大小进行初步排序，取前若干个文档作为相关查询集合 之后通过如下方法进行改进(即开始递归计算)

90 概率模型—— 用V表示概率模型初步检出并经过排序的文档子集 改进 和 的过程如下： 如此递归重复这一过程，得到理想结果集合
Vi表示V中包含索引词ki的文档数  改进 和 的过程如下： 1) 用已经检出的文档中索引词ki的分布来估计 2) 假定所有未检出的文档都是不相关的来估计 即 如此递归重复这一过程，得到理想结果集合

91 概率模型—— 对较小的V和Vi上述计算会出现问题，如V=1和Vi=0，可做一些改进： 调整因子也可以为ni/N， 即

92 概率模型—— 概率模型的算法步骤 起始时（只有查询需求，没有检索结果）假设： （1）对所有索引项概率 是常数； （2）索引项在非相关文档集中的分布近似等于在所有文档集中的分布，即：

93 概率模型—— 令V是初始检索结果的子集，有r个，取自检索结果集中前r个文档，这些检索结果是经过概率模型排好顺序的
令Vi是V中所有包含索引项ki的那些文档，显然Vi是V的子集；为简单起见，直接用V和Vi表示这些集合中的元素数量 修改对概率 和 的计算方法

94 概率模型—— 为保证数值计算的稳定性，常用下列公式计算相似度：

95 概率模型——12. 优缺点 优点 缺点 理论上讲，文档按照其与目标集合的相关概率 降序排列 需要最初将文档分为相关和不相关的集合
所有权重都是二值的，模型中仍然假设索引项之间是相互独立的

96 其他模型 结构化文本检索模型 信息浏览模型

97 其他模型——1. 结构化文本检索模型→概念 有时候，用户希望能够对文档中的某些结构组元中包含的信息进行检索，例如，对出现在章节标题的词进行检索。那么就需要一种模型，把文档内容与文档的结构结合起来，为用户提供信息检索的能力。这种模型就被称为结构化文本检索模型。 在检索任务中，传统的结构化文本检索模型没有采用相关性的思想，它只是从各个结构组元中匹配用户的查询项。从这个意义上看，过去的结构化文档检索模型是一个数据检索模型，但是，检索系统能够搜索出那些部分匹配查询条件的文档，在这种情况下，这种匹配是近似的，并且某些排序也是使用这种近似的结构

98 其他模型——结构化文本检索模型→概念 结构化文档检索算法可以看作是一种信息检索算法，但排序机制并不健全
使用“匹配点”来表示文本与用户查询相匹配的词串位置 使用“区域”表示文本的块 使用“节点”表示文档的结构化组元 这样，一个节点是一个区域，具有文档的作者与用户所共知的、预定义的逻辑属性

99 其他模型——结构化文本检索模型 基于非重叠链表的模型是把文档中的整个文本划分为非重叠文本区域，并用链表连接起来
因为有多种方法将文本分为非重叠的区域，所以，对于同一个文档，会产生多个链表 这些链表清晰的记录了文档的数据结构 在相同链表中的文本区域没有重叠，而不同链表中的文本区域可能会重叠

100 其他模型——2. 结构化文本检索模型→非重叠链表模型
为允许对索引项和文本区域进行搜索，要为每个预定义的链表建立一个索引 在索引中每个结构组元作为索引中的一个项目 因为针对每个索引项目，其索引的文本区域是不重叠的，所以可以提交的查询是简单的 选择一个包含给定词的区域 选择一个不包含在给定区域的区域 选择一个不被包含于任何其他区域的区域 Chapter Section Paragraph

101 其他模型——结构化文本检索模型 该模型是一种允许在相同文档上独立定义分层索引结构的模型，每个索引结构是一个严格的层次结构，其中每个结构组元称为节点，每个节点与一个文本区域相关，两个不同的层次结构可能涉及到两个重叠的文本区域 针对不同层次结构的用户查询，所汇集的结果是由来自其中一个层次结构的节点组成，因此，一个应答结果是不能由来自两个不同层次结构的节点组成 这样做的目的是使得查询处理的速度快

102 其他模型——3. 结构化文本检索模型→邻近节点模型
Chapter Section Paragraph Query sections with information Information 22 45 127 7892 ……

103 其他模型——4. 信息浏览模型→平坦浏览 该模型的思想假设用户浏览一个具有平坦组织的文档空间，文档集可以被描述为平面上的点或是链表中的元素
用户在这些文档上到处浏览，以寻找有关信息，在反馈过程中，用户通过在邻近文档中的浏览，查找出相关的资料，找出一些感兴趣的关键词。这些关键词将被输入到原始的查询中，以试图提供更好的、新的查询 同样，用户也可以以平面方式，浏览单一的文档。例如使用滚动条来浏览一个Web页面。 该模型的不足 在给定的一个页面或屏幕上，可能没有任何用户所处上下文情况的指示 平坦模型缺乏层次性的视图、用户的浏览行为很容易迷航 浏览模型，用户的兴趣可能不在于提交一个对系统的查询。而是有意花一点时间来浏览文档空间，以寻找所关心的文档。 在这种情况下，用户是进行文档空间的浏览而不是搜索； 浏览和搜索是不同的信息发现行为，通常来说，搜索比浏览更适合于有明确查找目标的用户。 平坦模型，结构向导模型，超文本模型

104 其他模型——5. 信息浏览模型→结构向导浏览 为了对浏览的行为提供更好的支持，文档应该被组织成为如目录那样的结构，目录是类的层次结构，对文档按照主题来分类和组织 在这样的情况下，用户执行一个具有结构向导类型的浏览。同样的思想仍然可以应用到一个单独的文档上。一个好的界面能够以变焦的方式上下查看这些层次，辅助用户的浏览过程，并保持上下文线索 除了用于浏览任务导向的结构外，界面也可以提供一些其他的导航工具，如提供浏览历史，指示最近访问的节点，这对于浏览结构庞大的文档集是相当有用的

105 其他模型——6. 信息浏览模型→超文本浏览 传统的文本书写相关的概念是顺序的
写作的顺序通常被认为是阅读的顺序，读者也不期待通过随机的阅读某段文本而全部理解作者的思想 无论是纸制或计算机中存在的文本，全部都是按顺序编排的，这样提供文档主要是为了满足顺序阅读的需要。而且顺序阅读也是大多数用户的阅读习惯，特别是上下文联系紧密的文档。

106 其他模型——信息浏览模型→超文本浏览 虽然由于制作的缘故，文档中的文字是顺序编排的，但用户不一定按编排顺序进行阅读，文本的顺序存放和管理方式与人的阅读过程中的联想思维方式及相应的活动是不相适应的。我们需要借助某种技术来实现跳跃式阅读，真正实现非线性阅读和浏览，需要定义一种新的组织结构，这种结构就是“超文本”。 超文本是一个允许以非顺序的方式在计算机上浏览文本的高层交互式导航结构。它由节点和链组成，节点之间的关系由链表示，节点和链构成一个有向图。支持用户的非线性浏览和信息存取。超文本的导航过程可以被理解为一个有向图的游历过程，图中被链接的节点表示节点之间有某种语义关联

107 其他模型与经典模型的比较 布尔、向量和概率模型是三个传统的检索模型 布尔模型是基于集合理论和布尔代数的一种简单检索模型
向量模型采用非二值的索引项权重，把文档和查询用t维权重向量表示，计算这两个向量之间的相似度来实现查询与文档的匹配 概率模型是一种规范的模型，它试图预测给定查询的相关文档，排序原则根据文档与集合的相似度进行排序

108 其他模型与经典模型的比较 文档的结构也包含了信息，基于非重叠链表和邻近节点模型是两个典型的结合和内容结合起来进行检索的模型
三种浏览模型：平坦模型，结构导向模型和超文本模型 平坦模型把文档（集）看成是一个平坦的文档空间。由于是平坦的，这种模型的导航关系不清楚 结构导向模型提供了层次性目录式的导航模型，是一种非平坦模型 超文本模型是由节点和链组成的非线性的信息组织网络，能够为用户提供比上两种模型更多的信息，更方便的浏览，Web是它最成功的应用

109 国内检索模型理论研究现状——国内主要热点
向量空间模型 统计模型 相似度 网络检索 搜索引擎 布尔模型 信息过滤 查全率 查准率 中文信息处理 查询 用户模型 文本检索 图像检索 文本分类 知识检索 数字图书馆 智能信息检索 武汉大学 焦玉英，刘伟成：模型比较 海南大学信息学院 雷景生：向量空间模型的Web信息检索 华南理工大学吴应良：模糊矢量相关信息检索模型 云南师范大学陶跃华：向量空间检索模型

110 发展趋势与研究课题 继续研究向量空间模型和概率模型 研究各种模型的融合 研究综合型的多媒体检索模型 研究检索模型的智能化
1985年，索顿先生在《信息科学研究札记》中强调了这两种模型，最近发表的文献大多数也是关于这两种模型。TREC评测中这两种模型也具有明显的优势 研究各种模型的融合 扩展布尔模型吸收了概率模型和向量模型的优点 研究综合型的多媒体检索模型 基于图像、图形、语音的案例检索模型 研究检索模型的智能化 将人工智能技术应用于检索技术

111 发展趋势与研究课题 图书馆系统 专业检索系统 互联网检索系统 集中于检索中的认知与行为问题的讨论，或者说研究模型对用户的影响
核心问题是如何避免大量无关的文献，特别需要研究先进的排序算法 互联网检索系统 核心问题是用户界面如何影响排序

112 国内检索模型理论研究现状 国内主要研究人员 中科院国科图 孙坦 武汉大学图情学院 焦玉英，刘伟成 武汉大学图书馆 邓珞华
海南大学信息学院 雷景生 华南理工大学 吴应良 云南师范大学 陶跃华 武汉大学 焦玉英，刘伟成：模型比较 武汉大学邓珞华模型比较 海南大学信息学院 雷景生：向量空间模型的Web信息检索 华南理工大学吴应良：模糊矢量相关信息检索模型 云南师范大学陶跃华：向量空间检索模型

113 参考资料 近几年来国外信息检索模型研究进展，孙坦，图书馆建设，2008.03
对布尔模型的研究主要表现在对布尔模型的改进及对扩展布尔模型的进一步优化 对向量空间模型的研究主要集中在对向量空间模型的扩展研究及对向量空间模型的应用方面 概率模型的发展主要集中在对概率模型进一步的研究、与其它信息检索模型的结合，以及语言模型的研究和发展 对于新兴的基于本体的信息检索模型的研究主要集中在对基于本体的信息检索模型理论的研究、与其它检索模型的融合、以及基于本体检索模型的应用 浅析信息检索模型的现状及趋势，田欢，计算机光盘软件与应用， 几种信息检索模型的比较，赵琳，煤炭技术， 信息检索模型的比较研究，张艳，电脑知识与技术， 数字图书馆个性化信息检索模型研究，许春漫，现代图书情报技术， TF / IDF 算法介绍