信息检索模型

形式特征

检索策略=文档表示+查询表示+匹配函数

文档表示：反映文档在系统中的存储形式描述，可用一组关键词或标引词表示；
查询表示：反映对用户信息需求的描述；
匹配函数：用于将经过处理的文档表示和查询表示放入系统中进行匹配，以过滤输出结果；

这样的模型主要从两个方面抽象出信息检索的方法：

如何表示文档，检索式
确定和计算 文档和检索式的关系

信息检索的任务就是建立文档，查询和它们的匹配函数之间的数学模型；

一般地，我们将信息检索用如下四元组表示：

是文档集中的一组文档逻辑视图（表示），称为文档的表示；
是一组用户信息需求的逻辑视图（表示），这种视图（表示）称为查询；
是一种机制，用于构建文档表示、查询及它们之间关系的模型；
是排序函数，该函数输出一个与查询文档表示有关的实数，这样就在文档之间根据定义了一个顺序。

经典模型

标引词：每篇文档都可以用一组有代表性的关键词来表示，属于文档中的词语；

对于经典模型一般都有如下的数学表示：

系统中的所有标引词集合为;
文档用表示,所有文档集合；
权值用于衡量二元组标引词的重要性,通常认为是独立的；
文档也可以用一个标引词向量表示
函数用于返回文档中标引词的权，

布尔模型

概念

BM假定标引词要么在文档中出现，要么不出现，权值是二值数据，也即;

对于查询是一个常规的布尔表达式,由连接词非，或，与连接多个标引词组成；

查询的析取范式为
的任意合取分量为

文档和查询的相似度可以定义为

优点

查询简单，易于理解，易于实现
经过某种训练的用户可以容易地写出布尔表达式
可以通过扩展来包含排序的功能

缺点

布尔逻辑式的构造不易全面反映用户的需求
不适合普通用户
检索结果不能按照用户定义的重要性排序输出
不支持部分匹配，构建不当，检索结果过多或者过少

优化

半结构化检索：仅在标题，摘要等检索项目
检索对半结构化的语义位置起作用,比如说标引词出现在标题一定比出现在正文要重要
增加proximity操作符，指定项的距离

向量模型

概念

VSM对检出文档按相似度降序排列的方式，实现文档和查询的部分匹配

模型的构建由四部分组成：

文档向量的构造
查询向量的构造
查询与文档的匹配函数选择
相似度阈值的选择

在VSM中标引词在文档的权重是非二值的,对于所有的特征项，文档和查询可以表征为如下的向量

可抽象为如下过程：

二者的相似性一般用内积或余弦相似度衡量,夹角越小说明相似度越高；

根据计算的相似度，可以对检索结果进行排序，进一步作相关检索

排序后的结果与设定的相似度阈值比较
大于阈值说明文档和查询相关，保留查询结果；
小于阈值说明不相关，过滤此页；

TFIDF函数

从文档，查询到向量的映射需要计算特征项权重，TFIDF函数用于解决这一问题，通过词语加权和聚类实现；

将文档看作对象集,用户查询看作的模糊描述，这样信息检索被描述称一个聚类问题；这样的问题有两个重要特征

Intra-clustering:描述内部聚类的相似度
Inter-clustering:描述交叉聚类的相异度

一个好的聚类算法应该使二者达到平衡；

TF(Term Frequency)因子：

用文档中的词语的初始频率衡量
用于度量标引词描述文档内容好坏的程度；

IDF(Inverse Document Frequency)因子：

用文档中的词语的逆频率衡量
该因子说明许多文档出现的词语对于区分相关文档和不相关文档是没有作用的；

对于一个信息检索系统：

文档总数为;
包含标引词的文档数目为;
标引词在文档的被提及的次数(初始频率)为;
所有词语的最大初始频率值为

定义在文档中，标引词的标准化频率为

如果词语不出现在文档中，则
对于查询，类似定义

定义词语的逆文档频率为

著名的词语加权方案为

对于查询词语的权值，可以用如下方法：

优点

标引词加权改进了检索效果
部分匹配策略可以检索出与查询条件相近的文档
可以根据文档与查询之间的相似度对文档进行排序

缺点

没考虑特征项出现在文档的位置
- 特征项在文档中不同位置应该代表不同权重
- 这样的计算方式甚至可能导致出现标题的词语的权重比摘要、正文更低，与我们的经验相违；
没考虑关键词的长度
- 关键词长度越长，在文档中出现的概率越小，但是较长的关键词比较短的包含了更多的信息；
- 关键词出现在较短的文档的权重理应要高
- 如果同一特征项在不同文档出现次数不同，在出现频率较高的文档中权重应该较高，而不是统一的1；
没考虑标引词之间的相关性
- 在VSM中，标引词被认为相互独立
对于动态变化的文档集，查询性能降低
- 没增加一个文档需要重新计算向量

概率模型

对文档与查询相匹配的概率进行估计，估计值作为衡量文档相关性的尺度。

概率排序原理：给定一个用户查询，如果搜索系统能够在搜索结果排序时按照文档和用户需求的相关性由高到低排序，那么这个搜索系统的准确性是最优的。

对于给定的用户查询,按照查询将文档聚类为2类：；

对于任意的文档,根据Bayes公式，与其相关/不相关的概率表示如下：

二元独立模型

标引词独立性假设：任意一个标引词的出现不会影响到其他标引词的出现，他们相互独立

二元属性取值：对于任意的文档可表示为元随机变量,若在中出现，值为1,否则为0；

预先使用一定数量带有相关性标记的文档，用最大似然估计法确定

一般难以预先给出带有标记的文档集，可以利用反馈技术获取标记文档：先再用其他检索技术标记；

定义文档和检索排序函数

取对数重新表示

这种假设往往不符合实际情况，因为标引词往往具有相关性；

双Poisson分布概率模型

文档的单词可分为两类：

内容词：与表达文档的主题有关
功能词：只完成语法功能

其中内容词概率分布波动情况近似泊松分布：用表示某个功能词在文档中出现的频率

Harter假设

根据一个内容词可以将文档从主题上分为两类，同时该内容词在两类文档中的出现频率也会很不相同
一类文档的主题与该内容词相关，那么该内容词在其中的出现频率应该比较高，其波动特征可以用一个泊松分布表示；
而另一类文档的主题与内容词不相关，所以内容词在其中的出现频率应该比较低，其波动特征也可以用一个泊松分布表示。

一个内容词在文档中的出现频率可以表示为两个泊松分布的加权组合：

其中，分别为内容词在两类文档中出现频率的均值，表示了任意一个文档属于第一类的概率;

只要将所有的标引词看作是内容词，则它们也满足2-Poisson模型，则就形成了双Poisson模型。与二元独立模型相比，2-Poisson模型的不同在于不承认标引词独立性假设，其余都相同。

优点

利用概率论原理，通过赋予索引词某种概率值来表示这些词在相关文档集合和非相关文档集合中出现的概率，然后计算某一给定文档与某一给定用户提问相关的概率并做出决策
具有内在的相关反馈机制，将文档根据它们的相关概率按递减顺序排列

缺点

最初需要把文档分成相关的集合和不相关的集合
这种方法并不考虑标引词在文档中出现的频率，即所有的权值都是二值的
假设标引词相互独立，然而如同VSM一样，这并不能明确标引词的独立性在实际情况中是否为一个不利的假设

集合理论模型

模糊集合模型

模糊集合理论

模糊集合理论主要研究边界不明确的集合的表示。

把隶属函数和集合中的元素结合在一起。
该函数的取值在区间[0,1]上，0对应于不隶属于该集合，1表示完全隶属于该集合，隶属值在0和1之间表示集合中的边际元素。

将每一个查询语词定义成一个模糊集合，论域的一个模糊子集可以用隶属函数来描述，为的每个元素分配一个数值，该数值在区间上。

检索时通过匹配运算，计算每篇文档在查询中的标引词所定义的模糊集合中的隶属度，并根据隶属度大小对文档排序。

标引词关联矩阵

叙词表可以通过定义一个词-词关联矩阵来构建，这个矩阵的行和列分别对应于文档集合中的标引词。

在矩阵中，语词和之间的标准化关联因子可以定义为：

表示包含语词的文档的数目，表示包含语词的文档的数目，表示同时包含语词的文档的数目。

对于标引词,对文档的隶属度定义如下：

只要文档中至少有一个标引词与密切相关，则接近1，且标引词是文档的一个很好的模糊索引；

只要文档中所有标引词与不是密切相关，则接近0，且标引词不是文档的一个很好的模糊索引；

和布尔模型一样，模糊集合模型也会将查询转换为析取范式

计算文档与查询相关的过程类似于采用经典布尔模型进行比较的过程。
其区别在于：此处的集合是松散的集合而不是布尔集合。

优点

模糊集合模型与经典布尔模型关系密切，它基本保留了布尔检索功能，但是更为灵活，避免了布尔检索的二值相关性测度局限性。
模糊集合模型支持对命中文档按相关性大小排序。

缺点

模糊集合模型仅局限于小规模的文档集合，相关实试验结果的可比性差。
它的研究工作主要集中于模糊学领域的文档中，在信息检索领域的研究并不广泛

拓展布尔模型

用部分匹配和语词加权功能来扩展布尔模型，可以使布尔查询表达式与向量模型的特征结合在一起。

文档,其中第个标引词的权值为
对于检索式,其中第个标引词的权值为

定义文本和查询的相似度为

粗糙集模型

在粗糙集理论中，

一个等价关系将一个非空集合划分成互不相连的等价类，根据这个关系等价类中的对象是不可区分的。
全集和等价关系一同定义了一个近似空间，等价类和空集被称为这个近似空间的基本集或原子集。这样一个近似空间可以用来描述全集的任意子集
不需要先验知识，就可以从数据中获取潜在依赖规律

设是划分非空全集的一个等价关系

近似空间为;
一个划分被定义为，这里是的一个等价类
对于的任意一个子集,定义下近似集，上近似集

上近似集和下近似集近似描述了近似空间中的子集，粗糙集就可以用这两个近似集来描述;

边界定义为在上近似集中，但不在下近似集中的元素集合；

利用粗糙集将词汇建模：

该模型是将给定范围的单词（单个词汇和段落）当作全集，表示等价关系定义为字眼的相似关系
对产生一个划分，这样一个类中的字眼彼此都是同义的，用向量来表示文本和查询
文本和查询是全集的子集，分别求出它们在近似空间中的上、下近似集;
下近似集中的属性确定地描述了子集，而上近似集中的属性可能地描述了子集;
这些确定性和可能性当然很大程度上是由近似空间决定的，因此，下近似集自动向核心描述靠近，而上近似集在词汇空间允许的范围内扩大了描述。;

文本和查询的相似度计算：

定义全集的两个中心和拓扑意义上的边界差后

计算

保持为中心，如果上式为0，表示不匹配，上式为1，表示和的最大匹配；

优点：

无须提供问题所需处理数据集合之外的任何先验信息，粗糙集理论对不确定性的描述相对客观；
只处理离散性属性，连续属性的离散化使得粗糙集理论对离散和连续属性都能够处理，扩大了该理论的应用范围。

缺点：

存在局限性，不能使用用权值描述的文本和查询
不能利用除了同义词之外的字眼关系。

代数模型

广义向量空间模型

对于经典模型认为标引词相互独立，可以理解为标引词向量两两正交，；在实践中，我们并不能将标引词向量当作向量空间的正交基；

最小项: 布尔代数上由产生的形如

的布尔表达式称为由产生的最小项

其中,定义;最小项不能进一步简化，因此布尔代数的基本元素可用如下向量唯一确定：

对于每一个标引词，可以表示称基本元素的析取式；

定义标引词的向量

定义文档和查询为

可以用余弦相似度计算，最后文档按照相似度大小降序输出；

潜语义标引模型

基本思想：

将标引词之间、文档之间的依赖关系以及标引词与文档之间的语义关联都考虑在内，将文档向量和提问向量映射到与语义概念相关联的较低维空间中，从而把文档的标引词空间向量转化为语义概念空间。
在降维的语义概念空间中，计算文档向量和提问向量的相似度，然后根据所得的相似度把排列结果返回给用户。

关键词-文档矩阵

设表示具有个标引词，个文档的检索系统的关键词-文档矩阵，则

矩阵的每一个元素为关键词-文档的权值;权值的确定可以用TFIDF确定；

现对作奇异值分解（SVD），假设的秩;

可分解为三个矩阵的乘积：

矩阵的含义如下：

:是由词-词关联矩阵导出的正交特征向量矩阵,称为的左奇异矩阵；
:是由词-词关联矩阵导出的正交特征向量矩阵,称为的右奇异矩阵；
:由奇异值组成的对角矩阵；

现在潜语义模型需要选取合适的值，保留前个最大的奇异值和相应的正交单位化的奇异向量，得到某种近似意义上的矩阵：

秩近似矩阵将文档的关键词向量空间转化为语义概念空间，且语义概念空间的维度;

因而，次要的术语区别就被忽略了，有相似用法的关键词，其向量也就相似，用法不同的关键词，对应的向量也就不相似，从而降低了同义词、多义词的影响，减少了冗余。

的选择是折中的;

首先，必须足够大，能包括所有的实数结构；
其次，又必须足够小，以便能忽略掉一些错误和不重要的描述细节。

对于两篇文档，现已进入维度为的降维空间

文档的相似度可以用列向量的内积表示；

标引词和文档相似度为;

为了对与用户提问相关的文档进行排序，我们通常把用户提问向量作为初识词-文档矩阵的一个伪文档向量;

计算文档向量与提问向量的相似度，并根据相似度的计算结果，把文档排列起来返回给用户。

优点：

选取合适的折中值降低了空间的维度，消除了标引词表示的描述的噪音
克服了多义词和同义词对检索的影响，提高了检索的精度；

神经网络模型

将检索模型看作一个神经网络如下图：

传播过程

由第一层的查询语词结点分别向对应的第二层文档语词结点发出信号；
文档语词结点又产生信息并向第三层的相关文档结点传送；
文档节点在收到文档词语节点发送的信号后，产生新的信号并返回到文档词语结点；
过程3将重复进行，直到信号不断衰减而终止。

分配查询语词结点的初始最大活跃值，也就是网络结点上的权值，可以用查询向量的2范数进行规范化

一旦信号到达文档语词结点，这些结点就直接向文档结点发出新的信号，这些信号已用规范化的文档语词结点的权值来衰减，同样规范化。

对到达文档结点的信号进行求和，在信号传播的第一个阶段之后，与文档相关联的文档结点的活跃值表示为

一般采用反向传播算法（BP）网络，或者或者遗传算法；

遗传算法：

模拟生物进化机制和遗传学原理，利用简单的编码和繁殖机制实现优胜劣汰的进化过程；

迭代一个大小为的群体，建立算子进行遗传和进化的操作，将适应度高的个体遗传到下一代

选择算子
交叉算子
变异算子

这种设计是基于自然选择的自适应算法，适合动态环境的应用，某种程度上提取用户兴趣模型也是一个优化问题；

遗传算法描述如下：

**初始化：**设置最大进化代数；随机生成个个体作为初识群体。
**个体评价：**计算群体中各个个体的适应度。
**选择运算：**将选择算子作用于群体。
**交叉运算：**将交叉算子作用于运算。
**变异运算：**将变异算子作用于群体。群体经过选择、交叉、变异运算之后得到下一代群体。
**终止条件判断：**若，则：,转到(2)，若,则以进化过程所得到的具有最大适应度的个体作为最优解输出，终止计算。

由于遗传算法存在某种随机性，因此发现用户没能正确表达的兴趣需求成为可能；

用户兴趣模型：定义一组含有权重的关键字描述用户的兴趣

对于一个描述关键字频率的文档向量；

向量的相似度仍然可以用余弦相似度描述

采用表示用户对文档的评分，则提取用户兴趣模型可看作使得

最小的优化问题；

针对于个体的变异算子有两种：

权值变异，即只改变个体中对应单词的权值；
单词变异，即个体中的单词和相应权值都改变。

两个个体通过杂交算子产生两个后代，杂交算子为：

随机从两个个体中选择两个基因点；
从这个基因点开始交换两者后面的基因，从而产生两个新的个体

算法中的个体基因必须唯一，也就是说在同一个体中每个基因单词都必须在个体中唯一，无论是杂交还是变异，都不能违背这一点。

拓展概率模型

概率粗糙集模型

概率粗糙集模型将条件概率关系和粗糙集理论结合，表示对象间的关联；

通过条件概率关系与模糊条件关系均用来表示对象间相似关系，而模糊条件概率关系代表了更一般化的情形。

对于非空有限论域,定义一个条件概率相似关系是指一个映射

对于是关于关于属性的模糊集，其关于的隶属函数为

一个模糊条件概率关系是指一个映射

对于,支持的对象集和被支持的对象集，也就是其被支持集和支持集分别定义为

由于条件概率关系满足自反性，因此

构成论域的一个覆盖；

对于论域的任意有限子集，可以定义其上下近似集

对于文档集,其标引词空间

同样将文档表示为向量;不同的是当分量的值定义在时，这就是文档的模糊标引词空间表示；

考虑定义在上的论域,定义论域的标引词对应的基本元素（等价类）为和标引词关于文档的隶属度;

我们需要寻找一个合适的分类粒度,用描述,定义标引词和文档的模糊条件概率关系和上下近似集，用于在标引词空间挖掘概念形成类空间

越大则分类粒度越小；
越小则分类粒度越大；

我们需要对文档作出模糊表示，这表明要构造文档论域上的一个模糊集；

先定义标引词关于模糊集的上下近似隶属度为

以文档论域为基础根据形成标引词概念空间，计算文档对象的近似集，再根据近似集隶属度定义计算每一标引词关于文档对象近似集的隶属度，从而得到文档近似集的模糊表示。

对于查询的上下近似集和隶属度，和文档类似；

查询和文档的上下近似关系采用Jaccard 相似度的计算方式，相加得到贴近度公式；

实现了查询和文档的上下近似集模糊表示后，可采用贴近度公式计算文档和文档间，文档和查询间的语义贴近度，最终排序输出；

推理网模型

将推理网模型分为两个部分

文档网络
检索网络

满足如下关系

网络中所有节点属于;
文档节点对应文档集合中的一个实际文档，其取值表示该文档是否被观察到。表示节点对应文档的索引项，其取值表示某一文档是否包含该索引项。每个文档节点与表示节点用有向边连接，强度用表示节点的条件概率表来表示。
检索网络以用户的检索需求是否被满足作为构成网络的因果关系，因此与文档网络的方向相反。节点表示用户的信息检索需求，节点代表各种不同的检索方案，其取值表示该检索是否被满足。不同节点的组合用于表示检索方案的不同表示方案，每种表示方案通过一批不同的表示节点来表示，每个节点的取值表示该节点是否被观察到。

将文档网络与检索网络结合在一起的是两者的表示节点各自构成的空间。这两个空间可以根据实际的应用背景，建立起多种映射关系;

这样信息检索过程转化为一个基于证据的推理过程；

指定文档变量的值为1，计算检索节点的后验概率后，换下一个文档；
根据后验概率对文档和相关度进行排序；

合并节点,用向量表示，计算相关度排序，将视作条件独立，变量值确定时，子节点相互独立

指定各项的不同取值，可以模拟多种检索模型。理论上来说可以综合多种检索模型的优点；

信度网模型

定义样本空间为文档集合中所有文档组成的索引项;定义概念为集合的一个子集;

用随机变量表示这些概念之间的关系

对于索引项，若其被一个概念包含值设为1，否则设为0；
每一个文档/查询可以看作样本空间的概念；

定义概念(全集为)对样本空间的覆盖度为其分布

定义检索和文档的相关程度为其覆盖度

选定一些基本概念

变量间的概率依赖关系构成Bayes网络；

结构化模型

非重叠链表模型

文档的整个文本划分成若干个非重叠的文本区域，并用链表连接起来。

由于将文本分为非重叠区域的方法有多种，所以会产生多种链表。

特点

各链表彼此独立，并且具有不同的数据结构。
同一链表中的文本区域没有重叠，不同链表中的文本区域可能重叠。
每个链表都对应一个独立的倒排文档，每个结构单元作为索引中的一项。与每个项相关的是一个文本区域的链表，表示文本区域在哪些文档中出现。
链表可与倒排文档合并，以表示文本中的单词。

由于文本区域是非重叠的，所以可以被提交的查询类型很简单：

选择一个包含给定单词的区域（不包含其他区域）；
选择一个不包含任何区域B的区域A（B属于一个不同于链表A的链表）；
选择一个不被包含于任何其他区域的区域。

邻近节点模型

模型允许在相同文档的文本上定义独立分层（非扁平的）索引结构。每个索引都有严格的层次结构，即由章、节、段、页、行所组成，这些结构单元通常称之为结点

每个节点指明了结构化单元（如章、节）在文本中的位置；

每个结点都与一个文本区域相关。
两个不同的层次结构可能会涉及到重叠的文本区域。
对于涉及不同层次结构的用户查询而言，所汇集的结果只能由来自其中一个层次结构的所有结点形成。

对于查询语言，可以为字符串检索的正则表达式，这个模型是表达和高效中的一个折中；

扁平浏览模型

当用户的兴趣不在于提交查询，而是浏览文档中感兴趣的内容时，可以称为用户是在对文档空间进行浏览而不是检索。

扁平浏览模型的思想是假设用户浏览一个扁平组织结构的文档空间。

扁平浏览模型的一个缺陷是：在给定的页面和屏幕上，可能没有关于用户所处上下文情况的任何提示。

结构导向模型

为了对浏览的任务提供更好的支持，文档可以被组织成为像目录那样的结构。

目录是类的层次结构，将文档按照相关主题来分类和组织。用户可以根据目录执行一个具有结构导向的浏览。

除了用于浏览任务导向的结构外，界面也可以提供一些其他的工具如历史地图，用来指明最近访问过的类，这对于浏览结构庞大的文档集是很有用的。

在检索时，通过表明事件发生来表示出这种结构（如采用内容表格的方法），这使我们能在全部文档上下文中看到事件的发生，而不是文本的某一页——以至于不清楚我们处在文档的哪个位置。

超文本模型

超文本：是一个允许以非顺序的方式在计算机屏幕上浏览文本的高层交互式导航结构。

它由结点和链所组成，结点之间的关系用链表示，结点和链构成一个有向图结构。

对于超文本来说，每个结点都与一个文本区域相关，这个区域可能是书中的章，或文章中的节，或是一个Web页面。

超文本的导航过程可以被理解为遍历一个有向图的过程。图中被链接的结点表示文本结点之间具有某种语义关联。

缺点：

当超文本很大时，用户可能会失去超文本组织结构的路线，其结果，用户进行错误的导航决策，并偏离他的主目标（一般只是查找超文本上少量的信息），这种情况称之为用户在网络空间中的迷航。
当用户浏览一个超文本时，会局限于由超文本设计者所构建的信息流。
在超文本导航中，用户可能发现很难确定自己的方位，即使在前面讨论的导航工具如超文本地图存在的情况下，这种困难也依旧存在，原因可能是由于复杂的超文本组织具有太多允许用户前进和后退的链接。

超文本结构的定义应该是在域建模(domain modeling)阶段，即在需求分析阶段之后完成的。

超文本为形成万维网(World Wide Web)的HTML（超文本标记语言）和HTTP（超文本传输协议）的构想和设计奠定了基础。