现代信息检索 Chapter 3：信息检索建模

1 信息检索模型

信息检索模型是一个四元组 $[D,Q,F,R(q_i,d_i)]$ 。其中D(Document)是文档表示的集合，Q(Query)是查询表示的集合，F(Framework)是对文档、查询及其关系建模的框架，例如布尔框架、线性框架，R(Ranking)是排序函数，对于查询表达式 $q_i\in Q$ 和文档表达式 $d_i\in D$ ，函数返回文档 $d_i$ 关于查询 $q_i$ 的文档次序。

信息检索主要基于文本，文本模型也细分为是否考虑文本结构，所谓考虑文本结构就是区别对待标题、段落等文档不同结构处的内容。在web中，由于文档数量巨大，还需要考虑网页之间的链接，如今的web排序函数结合了经典的信息检索模型和基于链接模型的特征来提高检索性能。信息检索还可基于图像、音频等多媒体数据，检索策略更复杂。信息检索模型的分类体系见下图：

2 经典信息检索

2.1 基本概念

索引项(index term)：文档里的一个词或一组连续的词，主要是名词，因为名词相比于形容词、副词等往往能包含更多信息，具体的选择策略因人而异。
词汇表(vocabulary)： $V=(k_1,k_2,\cdots ,k_t)$ ，其中 $t$ 是文档集中索引项的数量， $k_i$ 是某个索引项。
文档表示：就是简单的词袋方法，表示成和词汇表一样长的向量，其中每个元素是0或1，0表示对应的索引项在文档中未出现，1表示对应的索引项在文档中出现。
查询表示：和文档表示相同，每个元素表示相应索引项是否在查询中出现。
项-文档矩阵：行数是索引项个数，列数是文档个数，元素 $f_{i,j}$ 表示第 $i$ 个索引项在第 $j$ 个文档中出现的频数。显然，在词袋方法中是0-1矩阵。
文档的逻辑视图：大概就是表示文档的方式。通常是把文档全文转变成索引项集合，流程如下图：

2.2 布尔模型

使用词袋方法表示文档，用析取范式(disjunct normal form)表示查询。例如对于词汇表 $V=(k_a,k_b,k_c,k_d)$ 和查询 $q=k_a\wedge (k_b\vee k_c)$ ，用析取范式表示查询为：

$q_{DNF}=(1,1,1,0)\vee(1,1,1,1)\vee(1,1,0,0)\vee(1,1,0,1)\vee(1,0,0,0)\vee(1,0,0,1)$

文档与查询的相关度定义为析取范式中是否有一项与文档表示相同，因此也是二值的。

布尔模型的优点是简单，缺点是不支持排序。因为相关度是二值的，只能表示相关与否，而不能表示相关的程度。

2.3 项权重

提高检索质量的一个方法是给每个索引项设置权重，通常根据索引项在整个文档集中出现的频次设置权重。如果不假设索引项之间相互独立，还要考虑索引项之间的相关性，因为索引项之间的关联往往会反映文档之间的关联，一种计算项间相关性的方法是项-文档矩阵乘他的转置矩阵，如下图：

假设项间相互独立可以简化模型、提高计算效率，而利用项间相关性提高排序水平也是十分复杂的工作，考虑了项间相关性并不能保证排序水平的提高，因此是否假设项间相互独立没有固定的标准。

2.4 TD-IDF

TF-IDF是一个常用的计算项权重的指标，其中TF(Term frequency)表示项频，IDF(Inverse document frequency)表示反比文档频率。

使用项频是基于Luhn假设，即高频项对描述文档的关键主题是重要的。可以直接将索引项的频次作为TF权重，即 $tf_{i,j}=f_{i,j}$ ，但考虑到要与IDF权重结合，而IDF使用了对数运算，因此通常使用TF权重的一个变种：

$tf_{i,j}=\begin{cases} 1+log_2f_{i,j} & f_{i,j}>0 \\ 0 & otherwise \end{cases}$

TF权重倾向于给频次高的索引项更大的权重，但也要考虑索引项的区分度，即索引项特异性(term specificity)。如果一个索引项在每个文档中都出现，虽然出现频次高，但是对于文档排序等任务没有太大帮助，最常见的就是a、the这样的冠词、连词和介词。因此不仅要考虑高频项，还要考虑区分度大的索引项。IDF权重考虑的就是某个索引项在多少个文档中出现，即相对文档频率 $n_i/N$ ， $IDF_i=log_2\frac{N}{n_i}$ ，其中 $N$ 是文档集中的文档数量， $n_i$ 是出现索引项 $k_i$ 的文档数量，因为相对文档频率越小的索引项区分度越大，所以IDF使用了相对文档频率的倒数，称作反比文档频率。

TF-IDF将二者结合起来，计算方法如下：

$w_{i,j}=\begin{cases} (1+log_2f_{i,j})*log_2\frac{N}{n_i} & f_{i,j}>0 \\ 0 & otherwise \end{cases}$

TF、IDF和TF-IDF有多种变体。TF变体如下：

IDF变体如下：

TF-IDF变体如下：

通过下图可以分析出TF-IDF的性质。TF和IDF权重表现出的幂律特性会相互平衡，高TF权重趋于和低IDF权重结合，低TF权重趋于和高IDF权重结合，结果是TF-IDF权重最高的索引项往往具有中等TF和IDF权重，而项频太高的项和文档频率太低的项经过平衡后都具有较低的TF-IDF权重。妙啊！

2.5 文档长度归一化

对于给定的查询，较长的文档仅仅因为包含更多的索引项而更可能被检出，为了消除这一影响，可以把文档的排序除以其长度，这个过程称为文档长度归一化，如何计算文档长度取决于文档的表示形式。

2.6 向量模型

布尔模型使用析取范式的每一项和文档表示进行严格匹配，难以得到理想的结果。向量模型将文档和查询表示为向量形式，使用向量夹角的余弦值衡量相似度，成功将相似度量化为可用于比较和排序的数值，基于相似度的排序可以理解为一种部分匹配策略。文档的向量表示为 $\vec{d_j}=(w_{1,j},w_{2,j},\cdots,w_{t,j})$ ，其中 $t$ 是索引项总个数， $w_{i,j}$ 是项-文档对 $(k_i,d_j)$ 的权重，一般采用TF-IDF权重，查询的向量表示为 $\vec{q}=(w_{1,q},w_{2,q},\cdots,w_{t,q})$ , $w_{i,q}$ 是项-查询对 $(k_i,q)$ 的权重。文档-查询余弦相似度公式为：

$sim(d_j,q)=\frac{\vec{d_j}\cdot\vec{q}}{|\vec{d_j}|\times|\vec{q}|}$

注意到余弦公式分母的向量范数恰好也起到了文档长度归一化的作用。

2.7 概率模型

概率模型的目标是估计文档与查询相关的概率，他假定这种相关性仅依赖于文档和查询本身的表示，并假定存在一个理想答案集，仅包含所有与查询相关的文档，因此能够最大化与用户相关的总体概率。显然，这种假设是对真实情况的简化，所以必然会存在一些缺陷。

概率模型计算相关度的公式是：

$sim(d_j,q)=\frac{P(R|\vec{d_j})}{P(\overline{R}|\vec{d_j})}$

其中 $R$ 是与查询 $q$ 相关的文档的集合， $\overline{R}$ 是与查询 $q$ 不相关的文档的集合， $P(R|\vec{d_j})$ 是文档 $d_j$ 与查询 $q$ 相关的概率， $P(\overline{R}|\vec{d_j})$ 是文档 $d_j$ 与查询 $q$ 不相关的概率。根据贝叶斯公式：

$sim(d_j,q)=\frac{P(\vec{d_j}|R,q)\times P(R,q)}{P(\vec{d_j}|\overline{R},q)\times P(\overline{R},q)}\sim\frac{P(\vec{d_j}|R,q)}{P(\vec{d_j}|\overline{R},q)}$

其中 $P(\vec{d_j}|R,q)$ 表示从查询 $q$ 的相关文档集 $R$ 中随机选择的一偏文档表示为 $\vec{d_j}$ 的概率， $P(R,q)$ 表示从整个文档集中随机选择的文档和查询 $q$ 相关的概率， $P(\vec{d_j}|\overline{R},q)$ 和 $P(\overline{R},q)$ 的含义是相似且互补的。概率模型中不考虑项权重，所以 $\vec{d_j}$ 是一个二值向量，如果假设索引项间的独立性，即所谓的二值独立假设，可以得到：

$sim(d_j,q)\sim\frac{(\prod_{k_i|w_{i,j}=1}p_{iR})\times(\prod_{k_i|w_{i,j}=0}(1-p_{iR}))}{(\prod_{k_i|w_{i,j}=1}q_{iR})\times(\prod_{k_i|w_{i,j}=0}(1-q_{iR}))}$

其中 $p_{iR}$ 表示索引项 $k_i$ 出现在从查询 $q$ 的相关文档集 $R$ 中随机选择的一偏文档内的概率， $q_{iR}$ 表示索引项 $k_i$ 出现在从查询 $q$ 的不相关文档集 $\overline{R}$ 中随机选择的一偏文档内的概率。使用对数函数只改变数值而不改变排序结果，所以可以进一步简化为：

$sim(d_j,q)\sim\sum_{k_i\in q\wedge k_i\in d_j}log(\frac{p_{iR}}{1-p_{iR}})+log(\frac{1-q_{iR}}{q_{iR}})$

得到了相似度公式，接下来就是如何计算 $p_{iR}$ 和 $q_{iR}$ 。

一种计算方法是使用索引项出现列联表，如下：

情况	相关文档数	不相关文档数	总文档数
包含 $k_i$ 的文档	$r_i$	$n_i-r_i$	$n_i$
不包含 $k_i$ 的文档	$R-r_i$	$N-n_i-(R-r_i)$	$N-n_i$
所有文档	$R$	$N-R$	$N$

那么可以得到，

$p_{iR}=\frac{r_i}{R}\quad, \quad q_{iR}=\frac{n_i-r_i}{N-R}$ $sim(d_j,q)\sim\sum_{k_i\in q\wedge k_i\in d_j}log(\frac{(r_i+0.5)(N-n_i-R+r_i+0.5)}{(R-r_i+0.5)(n_i-r_i+0.5)})$

之所以给每个包含 $r_i$ 的项加0.5，是为了减小极端情况下过小的 $r_i$ 对 $log$ 计算的影响。这种方法需要人工估计 $r_i$ 和 $R$ 值，所以不实用，同时缺少文档长度归一化的操作，使得排序效果也不是很好。

另一种方法是在避免人工估计的条件下，基于几条假设来自动更新 $r_i$ 和 $R$ 值，个人认为这里的假设太牵强，理解不了。

概率模型的优点是能按照相关概率进行排序，但其认为相关性仅与文档和查询的内容有关，所以实际应用时效果难以保证。此外，概率模型不可避免地要做初始估计将文档分为相关和不相关集合，不太好操作。观察上面计算 $sim(d_j,q)$ 的公式，与IDF权重的公式是相似的，从这个角度看，概率模型的另一个缺点是没有用到TF特征，也没有进行文档长度归一化。

3 其他集合论模型

3.1 基于集合的模型

基于集合的模型不考虑单独的索引项，而是考虑索引项之间的相互依赖性，通过引入项集的概念表示索引项之间的关联。

项集(Termset)：项集 $S_i=\{k_a,k_b,\cdots,k_n\}$ 是文档集中索引项的子集。若 $S_i$ 中所有的索引项都出现在文档 $d_j$ 中，就称项集 $S_i$ 出现在 $d_j$ 中。

显然，若文档集中有 $t$ 个索引项，则理论上有 $2^t$ 个项集，但实际数据集中一般仅包含部分项集。同时，用项集表示替代索引项表示就需要把项的词汇表改为项集的词汇表，即 $V_S=\{S_1,S_2,\cdots,S_{2^t}\}$ 。

频繁项集(Frequent termsets)：由 $n$ 个项构成的项集称为 $n$ 项集，如果包含某个 $n$ 项集的文档数 $\mathcal{N}_i$ 高于某个给定的阈值，那么这个 $n$ 项集 $S_i$ 称为是频繁的。显然，一个 $n$ 项集是频繁的当且仅当他的所有 $(n-1)$ 项集都是频繁地。

在TF-IDF中，计算的权重是项-文档矩阵的元素，在集合模型中与之类似，计算的权重是项集-文档矩阵的元素。对于 $(S_i,d_j)$ ，令 $N$ 是文档集中文档总数， $\mathcal{F}_{i,j}$ 是项集 $S_i$ 在文档 $d_j$ 中的原始出现频率，赋予项集权重：

$\mathcal{W}_{i,j}=\begin{cases} (1+log_2\mathcal{F}_{i,j})*log_2(1+\frac{N}{\mathcal{N}_i}) & \mathcal{F}_{i,j}>0 \\ 0 & otherwise \end{cases}$

同理， $\vec{d_j}=(\mathcal{W}_{1,j},\mathcal{W}_{2,j},\cdots,\mathcal{W}_{2^t,j})$ ， $\vec{q}=(\mathcal{W}_{1,q},\mathcal{W}_{2,q},\cdots,\mathcal{W}_{2^t,q})$ ，相似度计算公式为：

$sim(d_j,q)=\frac{\vec{d_j}\cdot\vec{q}}{|\vec{d_j}|\times|\vec{q}|}=\frac{\sum_{S_i}\mathcal{W}_{i,j}\times\mathcal{W}_{i,q}}{|\vec{d_j}|\times|\vec{q}|}$

由于项集空间是项空间的指数级大小，所以相似度的计算十分复杂，需要进行计算简化。例如在计算向量范数时只考虑 $1$ 项集。或是进一步缩小项集的范围，只考虑频繁闭项集，闭项集(Closed termset)就是项集的闭包，比如项集 $\{k_1\}$ 、 $\{k_2\}$ 、 $\{k_1,k_2\}$ 出现在相同的文档子集中，那么可以只计算 $\{k_1,k_2\}$ ，大大减小了计算量，除了频繁闭项集，还可选择最大频繁集，即添加任何索引项都不能使其保持频繁性。从项集数目上看，频繁项集>频繁闭项集>最大频繁集，需要注意的是，减少计算必然伴随着信息的损失，因此需要根据实际情况进行权衡。

3.2 扩展布尔模型

用向量模型的特征扩展布尔模型，狗尾续貂？

3.3 模糊集模型

模糊集模型基于模糊集理论，对于每一个索引项 $k_i$ ，为其分配一个模糊集(fuzzy set) $D_i$ ，模糊集为每一个文档 $d_j$ 分配一个介于区间 $[0,1]$ 之间的隶属度(degree of membership) $\mu_{i,j}$ ，若 $\mu_{i,j}\sim 1$ 表明 $k_i$ 是 $d_j$ 的良好模糊索引项，若 $\mu_{i,j}\sim 0$ 表明 $k_i$ 不是 $d_j$ 的良好模糊索引项。隶属度可以通过项间相关性矩阵 $C$ 来计算，索引项 $k_i$ 和 $k_l$ 的相关性计算公式为：

$c_{i,l}=\frac{n_{i,l}}{n_i+n_l-n_{i,l}}$

其中 $n_i$ 是含有索引项 $k_i$ 的文档数， $n_l$ 是含有索引项 $k_l$ 的文档数， $n_{i,l}$ 是同时含有这两个索引项的文档数，这种相关性度量被广泛应用在聚类算法中。有了相关性度量，就可以计算隶属度：

$\mu_{i,j}=1-\prod_{k_l\in d_j}(1-c_{i,l})$

这其实就是在考虑 $k_i$ 和 $d_j$ 中每一个索引项的相关性，可以看出，只要 $d_j$ 中至少有一个索引项 $k_l$ 与 $k_i$ 关系密切(即 $c_{i,l}\sim 1$ )，则 $\mu_{i,j}\sim 1$ 。此外，采用代数和的方式计算而不是对所有相关性使用 $max$ 函数，可以使 $\mu_{i,j}$ 的值变得平滑。

有了文档相对索引项的隶属度，就可以进一步计算文档相对于查询的隶属度，因为借鉴布尔模型的方法，查询可以表示成索引项组成的逻辑表达式。例如对于查询 $q=k_a\wedge (k_b\vee\neg k_c)$ ，可以写成析取范式 $\vec{q}_{dnf}=(1,1,1)\vee(1,1,0)\vee(1,0,0)$ ，设 $D_a$ 、 $D_b$ 、 $D_c$ 分别是 $k_a$ 、 $k_b$ 、 $k_c$ 的模糊集，查询的模糊集 $D_q$ 可以从下图理解：

其中， $cc_1=\mu_{a,j}\mu_{b,j}\mu_{c,j}$ 、 $cc_2=\mu_{a,j}\mu_{b,j}(1-\mu_{c,j})$ 、 $cc_3=\mu_{a,j}(1-\mu_{b,j})(1-\mu_{c,j})$ ，则：

$\mu_{q,j}=1-\prod_{i=1}^3(1-cc_i)$

同样，采用代数和的方式计算而不是对所有相关性使用 $max$ 函数，可以使 $\mu_{q,j}$ 的值变得平滑。