『IR 信息检索入门必看』#4 概率模型（简明）

2021-10-14 本文已影响0人 Hwcoder

访问博客查看本文最新内容，排版更美观ヾ(•ω•`)o 如有错误欢迎指出~

IR 信息检索系列笔记：

IR学习笔记 #1 概论&布尔模型

IR学习笔记 #2 统计语言模型

IR学习笔记 #3 向量空间模型

IR学习笔记 #4 概率模型

IR学习笔记 #5 检索系统评价

IR学习笔记 #6 网络信息检索

IR学习笔记 #7 IRLbot

IR学习笔记 #8 倒排索引模型

IR学习笔记 #9 网页排序

IR学习笔记 #10 查询相关反馈

IR学习笔记 #11 问答系统

IR课程项目-文学检索-开发文档

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

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

朴素贝叶斯分类 | 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\left( R|D \right) >P\left( NR|D \right)$ 时，我们认定该文档是相关文档，将其返回。

但在实际中，我们还要考虑最小化期望损失（也称为贝叶斯风险，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$	n	n
不包含词项 $T_k$	N-n	N-n
总数	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 公式。