IR学习笔记 #04 概率模型

前面介绍的模型，都是通过对相似性的计算，得出最佳匹配的模型。而概率检索模型，则是基于概率原理，越过相似性，直接对相关性进行计算的一种检索模型。

利用相关性有一个好处，就是对于两个不相似的词，如果它们因为某些因素联系起来了，那么也会出现在检索结果中。

朴素贝叶斯分类 | Naive Bayes

贝叶斯公式是概率论中非常基础的公式，其解决的核心点在于根据已有信息，对未知事物发生结果的概率计算。这里简单介绍一下作为模型的引入。

如果我们有文档 D，可以记 \(P(R=1|D)\) 为文档和查询相关的概率（这里的 R 只有 0 和 1 两种取值），这表示在文档确定的情况下，发生 \(R=1\) 假设的后验概率。

与此同时，\(P(R=1)\) 可以表示该假设的先验概率，意思是在完全对文档无所知的情况下，这个文档的分类情况满足假设的概率。

以下我们将 \(R=1\) 简写为 R，\(R=0\) 简写为 NR，表示一下贝叶斯公式： \[ P(R|D) = \frac{P(RD)}{P(D)} = \frac{P(D|R)P(R)}{P(D)} \] 实际上，贝叶斯公式是做了一个转换，将复杂的概率式转化为三个更好计算的概率式。

• \(P(D)\) 表示随机选取一篇文档，恰好是特定的 D 的概率，这个概率对于所有文档都是一致的，如果只是作比较，就不需要考虑。
• \(P(R)\) 表示假设 R 成立的先验概率，如果有已知的数据集，我们可以用相似文档的频率近似概率；如果没有，也可以先设为 0.5。但应用在比较中，也是不需要考虑的。
• \(P(D|R)\) 表示任意一篇文档被归类为相似后，恰好是特定的 D 的概率，需要所用特殊的方法来估计。

所以，判断一篇文档是否相似，只需要比较 \(P(R|D)\) 和 \(P(NR|D)\) 两个值的大小，就是比较 \(P(D|R)P(R)\) 和 \(P(D|NR)P(NR)\)。

概率检索 | Probabilistic Retrieval

概率检索模型与贝叶斯分类的思想非常接近，但还是有本质区别的。概率检索模型的根本目的不是分类，它不需要根据查询判断一个文档属于“相关”或者“不相关”，而是计算这个文档属于属于“相关”或者“不相关”的概率大小为文档排序。

因此，在概率检索模型中，我们首先要定义一个相关度指标，考虑前文中提到的 \(P(D|R)P(R)\) 和 \(P(D|NR)P(NR)\)，由于 \(P(R)\) 和 \(P(NR)\) 在同一个查询下对所有文档都是一致的，因此只要关注剩余部分之比（也称为优势率）： \[ \alpha = \frac{P(D|R)}{P(D|NR)} \] 显然，这个比值越大，代表该文档与查询的相关度越大，因此我们最后就通过 \(\alpha\) 将文档排序。

风险最小化 | Risk Minimization

此外，在检索过程中，我们还要决定一篇文档是否被召回，即设定一个召回阈值。一般我们会选择贝叶斯最优决策定理（Bayes’ Optimal Decision Rule）来决定一个文档是否相关，进而确定是否将其返回。

所谓的贝叶斯最优决策定理其实很简单，当 $P( R|D ) >P( NR|D ) $ 时，我们认定该文档是相关文档，将其返回。

但在实际中，我们还要考虑最小化期望损失（也称为贝叶斯风险，Bayes Risk），即「返回一篇不相关文档」或「没有返回一篇相关文档」的损失。

举个例子，在就诊看病的过程中，将患病者诊断为「健康」而错失治疗时机，远比健康者诊断为「患病」代价大得多。因此我们也认为「没有返回一篇相关文档」的代价要大于「返回一篇不相关文档」。

如果记 \(c_{rr}\) 为 cost of deciding relevant when relevant， \(c_{rn}\) 为 cost of deciding relevant when not relevant，\(c_{nn}\) 和 \(c_{nr}\) 同理。那么就有： \[ c_{nr}P\left( R|D \right) +c_{nn}P\left( NR|D \right) >c_{rn}P\left( NR|D \right) +c_{rr}P\left( R|D \right) \] 移项，并引入贝叶斯公式后： \[ \left( c_{nr}-c_{rr} \right) P\left( D|R \right) P\left( R \right) >\left( c_{rn}-c_{nn} \right) P\left( D|NR \right) P\left( NR \right) \] 结合相关度指标，可以等到新的阈值： \[ \alpha =\frac{P(D|R)}{P(D|NR)}>\frac{\left( c_{rn}-c_{nn} \right)P\left( NR \right)}{\left( c_{nr}-c_{rr} \right)P\left( R \right)} \]

二值独立检索 | Binary Independence Retrieval

前面提到，\(P(D|R)\) 表示任意一篇文档被归类为相似后，恰好是特定的 D 的概率，在通常的朴素贝叶斯分类中，通常有两种方法来估计：

• 用 D 在类别 R 中的比例来估计，显然，这个方法在检索中不适用，因为同一文档 D 几乎不可能在 R 中出现过。
• 将 D 看作由 0 和 1 二值组成的向量，每个维度代表了一种词项是否包含在该文档中，默认词项之间是相互独立的，然后用下面的公式计算：

\[ P(D|R) = \prod_{T_i \in D}{P(T_i=1|R)}\prod_{T_j \notin D}{P(T_j=0|R)} \]

其中，T 就代表文档中的词项 term，\(P(T|R)\) 就是该词项在归类为相似的文档集中出现或不出现的概率。

公式推演

在以上的概念下，不妨记：

• 相似文档集中 \(P(T_k=1|R)\) 为 \(p_k\)，\(P(T_k=0|R)\) 为 \(1-p_k\)。
• 不相似文档集中 \(P(T_k=1|NR)\) 为 \(q_k\)，\(P(T_k=0|NR)\) 为 \(1-q_k\)。

则相关度指标可表示为： \[ \alpha = \frac{\prod_{T_k \in D}p_k \prod_{T_k \notin D} 1 - p_k}{\prod_{T_k \in D}q_k \prod_{T_k \notin D}1 - q_k} \] 再做一个数学上的等价变换，如下： \[ \begin{aligned} \alpha &= \frac{\prod_{T_k \in D}p_k \prod_{T_k \notin D}1 - p_k}{\prod_{T_k \in D}q_k \prod_{T_k \notin D}1 - q_k} = \frac{\prod_{T_k \in D}p_k}{\prod_{T_k \in D}q_k} \cdot \frac{\prod_{T_k \notin D}1 - p_k}{\prod_{T_k \notin D}1 - q_k}\\ &= (\frac{\prod_{T_k \in D}p_k}{\prod_{T_k \in D}q_k} \cdot \frac{\prod_{T_k \in D}1 - q_k}{\prod_{T_k \in D}1 - p_k}) \cdot (\frac{\prod_{T_k \in D}1 - p_k}{\prod_{T_k \in D}1 - q_k} \frac{\prod_{T_k \notin D}1 - p_k}{\prod_{T_k \notin D}1 - q_k})\\ &= \frac{\prod_{T_k \in D}p_k(1 - q_k)}{\prod_{T_k \in D}q_k(1 - p_k)} \cdot \frac{\prod 1 - p_k}{\prod 1 - q_k} \end{aligned} \] 在同一查询下，相似文档集和不相似文档集是固定的，也就是说 \(p_k\) 和 \(q_k\) 的值也是相同的。故公式的第二部分（与文档 D 无关）可以忽略，简化成 \[ \alpha=\prod_{T_k \in D}\frac{p_k(1 - q_k)}{q_k(1 - p_k)} \] 取对数将乘积转化为求和得到用于排序的两，称为 RSV (Retrieval Status Value，检索状态值)： \[ RSV_D=\sum_{T_k \in D} \left(\log \frac{p_k}{1 - p_k} + \log \frac{1 - q_k}{q_k} \right) \]

Estimation using training data

现在我们只要计算出 \(p_k\) 和 \(q_k\) 的值就成功了。在计算之前，我们先写出下面的索引项出现列联表：

	相关文档	不相关文档	总数
包含词项 \(T_k\)	r	n-r	n
不包含词项 \(T_k\)	R-r	N-n-R+r	N-n
总数	R	N-R	N

则可以得到估算式： \[ p_k=\frac{r}{R}, q_k=\frac{n-r}{N-R} \] 同时，为了避免可能出现的零频问题（比如所有的相关文档都包含或不包含某个特定的词项），一种很常规的做法是在之前的表格中的每个量的基础上都加上 0.5 来平滑处理，因此总数也做相应改变： \[ p_k=\frac{r+0.5}{R+1}, q_k=\frac{n-r+0.5}{N-R+1} \]

Estimation without training data

用上式代入得到的计算式也称作 Robertson-Sparck Jones 等式，这个式子的计算条件是知道相关文档总数 R，但实际上大多数时候我们都是不知道的。

一种可行的方案是，初始时令相关文档数为 0，这是因为在实际检索情景下，文档库中往往只有少部分是和查询词相关的内容：

	相关文档	不相关文档	总数
包含词项 \(T_k\)	0	n	n
不包含词项 \(T_k\)	0	N-n	N-n
总数	0	N	N

此时的 \(p_k\) 值可以用常数来代替，如 0.3。

修正公式

在本文的最后，我们再来讨论一个问题，在前面讲到的 \(p_k\) 和 \(q_k\)的值估算过程中，我们其实是用到了之前提过的文档频率 df。

而在之前的文章中，还有词频、逆文档频率、文档长度等等多种因素未被考虑到。因此，基于最初的原理和假设，可以对原来的 RSV 公式增加修正因子，使得模型更加精确。

BM25 Weighting

这是一种最常用的加权方法，考虑了词频和文档长度。BM25 模型为文档 \(D_i\) 每个词项项 \(T_j\) 分配了一个系数 \(B_{i,j}\) ，由下计算生成： \[ B_{i,j}=\frac{\left( K_1+1 \right) f_{i,j}}{K_1\left[ (1-b)+b\frac{\mathrm{len}\left( D_i \right)}{\,\,\mathrm{avg}\_\mathrm{doclen}} \right] +f_{i,j}} \] 其中，\(K_1\) 和 b 为经验参数，用于调节词频和文档长度在权重计算中起到的作用，一般来讲， \(K_1\) 取 1，b 取 0.75 已经被证明是合理的假设。而 \(f_{i,j}\) 则为词项 \(T_j\) 在文档 \(D_i\) 中的词频，avg_doclen 为平均文档长度。

Multiple Fields

在 BM25 的之后，还有一种针对其提出的修正方法。将文档划分成不同的域，如：title/abstract/body，并对不同域赋予不同的权重（每个 term 出现的当量不同）。例如，term 在标题出现 1 次相当于在 abstract 出现 1.5 次。

同理，文档长度也相应的进行加权调整，最后可以计算出新的修正因子： \[ \begin{aligned} \widetilde{t f}_{i} &=\sum_{s=1}^{S} w_{s} t f_{s i} \\ \widetilde{d l} &=\sum_{s=1}^{S} w_{s} s l_{s} \end{aligned} \] 最后计算出的频度替换原始的频度，代入 BM25 Weighting 公式。