布尔模型和向量空间模型可以给出文档内容和查询是否相关的非确定性的推测，而概率论的方法可以给这种推测提供一个基本的理论。

概率论基础知识

事件A发生的概率为P(A)，它满足0≤P(A)≤1，对于两个事件A、B，它们的联合事件发生的可能性通过联合概率P(A,B)描述，条件概率P(A|B)表示在事件B发生的条件下A发生的概率。联合概率和条件概率的关系可以通过链式法则(Chain Rule)来体现：

P(AB)=P(A∩B)=P(A|B)P(B)=P(B|A)P(A)

事件A 的补集的概率记为P(\bar{A})，同样有

P(\bar{A}B)=P(B|\bar{A})P(\bar{A})

全概率定理为：如果事件B可以划分为互斥的多个子事件，那么B的概率将是所有子事件概率的和。例如

P(B)=P(AB)+P(\bar{A}B)

基于此可推出贝叶斯定理(Bayes rule)：

P(A|B)=\frac{P(B|A)P(A)}{P(B)}=\biggl [ \frac{P(B|A)}{\sum_{X \in {\{A,\bar{A}\}}} P(B|X)P(X)} \biggr] P(A)

优势率odds，提供了一种反映概率如何变化的放大器，定义为

O(A)=\frac{P(A)}{P(\bar{A})}=\frac{P(A)}{1-P(A)}

概率排序原理

概率排序原理Probability Ranking Principle可描述为“the optimum retrieval is achieved when documents are ranked according to decreasing values of the probability of relevance (with respect to the current query)”，即“最优的文档排序应为按照文档与当前查询的相关性的概率降序排序”。

令\bar{C}表示返回一篇不相关文档的代价，而C表示返回一篇相关文档的代价。PRP认为，如果一篇特定的文档d_m及所有其他未返回的文档d_j都满足

C \cdot P(R|q_k,d_m) + \bar{C}(1-P(R|q_k,d_m)) \le C \cdot P(R|q_k,d_j) + \bar{C}(1-P(R|q_k,d_j))

则d_m就应该是下一篇被返回的文档。也就是说，检索结果应该为期望代价最小的文档。因为通常有C<\bar{C}，上述条件等价于

P(R|q_k,d_m) \ge P(R|q_k,d_j),

因此，文档应该按照相关性的概率降序排列。

二值独立模型BIR

BIR模型的目标在于估计P(R|q_k,d_m)，即对于查询q_k，文档d_m被判定为相关的概率。模型最基本的假设为词项在相关文档与不相关文档中的分布是不同的；该假设也被称为"cluster hypothesis"。

令T=\{t_i\} (i \in [1,n])表示文档集中的词项，因此文档d_m中的词项集合d_m^T可以表示为一个二值向量\vec{x}=\{x_i,\cdots,x_n\}，其中当t_i \in d_m^T时，x_i=1，否则为0。

对于二值模型而言，如果文档包含的词项集相同，则表示文档的向量相同，其与某个查询的相关的概率也相同。因此利用P(R|q_k,\vec{x})表示一系列表示为\vec{x}的文档与查询相关的概率。此外，BIR还假设查询q_k是词项集合T的子集。

下面是文档d_m相关性概率P(R|q_k,d_m)的推导过程：

首先，计算二值向量\vec{x}与查询q_k相关的odds为

O(R|q_k,\vec{x})=\frac{P(R|q_k,\vec{x}}{P(\bar{R}|q_k,\vec{x}}=\frac{P(R|q_k)}{\bar{R}|q_k} \cdot \frac{P(\vec{x}|R,q_k)}{P(\vec{x}|\bar{R},q_k)}

此时引入朴素贝叶斯条件独立性假设，即在给定查询的情况下，一个词出现与否与任意一个其他词出现与否是相互独立的，因此有

\frac{P(\vec{x}|R,q_k)}{P(\vec{x}|\bar{R},q_k)}=\prod_{i=1}^{n}\frac{P(x_i|R,q_k)}{P(x_i|\bar{R},q_k)}

因此，O(R|q_k,\vec{x})可转化为，

O(R|q_k,\vec{x})=O(R|q_k) \prod_{i=1}^{n}\frac{P(x_i|R,q_k)}{P(x_i|\bar{R},q_k)}

上述等式中的连乘部分可以根据词项在当前文档中出现与否分解为：

O(R|q_k,\vec{x})=O(R|q_k) \prod_{x_i=1}\frac{P(x_i=1|R,q_k)}{P(x_i=1|\bar{R},q_k)} \cdot \prod_{x_i=0}\frac{P(x_i=0|R,q_k)}{P(x_i=0|\bar{R},q_k)}

令p_{ik}=P(x_i=1|R,q_k)且q_{ik}=P(x_i=1|\bar{R},q_k)。此外，假设对于没有出现在集合q_k^T中的词项均有p_{ik}=q_{ik}。通过上述简化，可以得到

O(R|q_k,\vec{x})=O(R|q_k) \prod_{t_i \in {d_m^T \cap q_k^T} } \frac{p_{ik}}{q_{ik}} \prod_{t_i \in q_k^T \backslash d_m^T} \frac{1-p_{ik}}{1-q_{ik}}

=O(R|q_k) \prod_{t_i \in {d_m^T \cap q_k^T}} \frac{p_{ik}(1-q_{ik})}{q_{ik}(1-p_{ik})} \prod_{t_i \in q_k^T} \frac{1-p_{ik}}{1-q_{ik}}

观察上述公式，对于某个特定的查询q_k而言，O(R|q_k)是常数。而第二个连乘是作用于查询中所有的词项，它的值对于所有的文档也都是相同的，即也可看作一个常数。因此对于上式仅仅需要考虑第一个连乘积，对其取log，可得到文档d_m对于查询q_k的检索状态值RSV(retrieval status value):

\sum_{t_i \in d_m^T \cap q_k^T} c_{ik}，其中，c_{ik}=\log \frac{p_{ik}(1-q_{ik})}{q_{ik}(1-p_{ik})}

当查询词项出现在相关文档时，优势率为p_i / (1-p_i)；当查询词项出现在不相关文档时，优势率为q_i / (1-q_i)。优势率比率就是上述两个优势率的比值，最终对这个值取对数。若两个优势率值相等，则c取0，即词项在检索时不起作用。如果词项更可能出现在相关文档中，则c取正值。c其实给出了模型中词项的权重，而查询文档的得分则是所有c值得和。

Okapi BM25

BM25是基于词袋模型的一族检索方程。词袋模型是在自然语言处理和信息检索中的一种简单假设。在这种模型中，文本（段落或者文档）被看作是无序的词汇集合，忽略语法甚至是单词的顺序。BM25方程最主要的实现方式如下：

给定查询Q，其中包含关键词项q_1,\cdots,q_n，文档D的BM25值为：

\textrm{score}(D,Q)=\sum_{i=1}^{n} \textrm{IDF}(q_i) \cdot \frac{f(q_i,D) \cdot (k_1+1)}{f(q_i,D)+k_1 \cdot (1-b+b \cdot \frac{|D|}{\textrm{avgdl}})}

其中f(q_i,D)是词项q_i在文档D中的词频tf，|D|是文档D的长度，avgdl是整个文本集合中文档的平均长度，k_1和b是自由参数，通常取值为k_1 \in [1.2,2.0]和b=0.75。

\textrm{IDF}(q_i)是查询词项q_i的逆文档频率，通常通过以下公式计算：

\textrm{IDF}(q_i)=\log\frac{N-n(q_i)+0.5}{n(q_i)+0.5}

其中N是文档集中文档的数量，n(q_i)是包含词项q_i的文档数。

计算IDF的公式表现有点奇怪，如果词项在文档集中出现的文档数超过一般，那么该公式取值为负，这可能并不是事先想要的结果。不过在使用停用词表的前提下，这种情况不会发生；此外，可以讲该值得最小值设为0。

参考文献：

[1] Manning et al. Introduction to information retrieval. Vol. 1. Cambridge: Cambridge university press, 2008.

[2] Fuhr, N. Probabilistic models in information retrieval The Computer Journal, Br Computer Soc, 1992, 35, 243-255.

概率检索模型回顾