给定一个用户需求(query),如果搜索系统展示的搜索结果是根据文档和query的相关性由高向低排序的，那么这个搜索引擎是最优的。在文档集合的基础上计算其相关性估计是其核心~

概率排序原理

以往的向量空间模型是将query和文档使用向量表示然后计算其内容相似性来进行相关性估计的，而概率检索模型是一种直接对用户需求进行相关性的建模方法,一个query进来，将所有的文档分为两类—-相关文档、不相关文档,这样就转为了一个相关性的分类问题,赞!

对于某个文档$D$来说，$P(R|D)$表示该文档数据相关文档的概率，则$P(NR|D)$表示该文档属于不相关文档的概率，如果query属于相关文档的概率大于不相关文档$P(R|D)>P(RN|D)$，则认为这个文档是与用户查询相关相关的.

现在使用贝叶斯公式将其转一下:

$P(R|D)>P(NR|D) <=>\frac{P(D|R)P(R)}{P(D)}>\frac{P(D|NR)P(NR)}{P(D)} <=> \frac{P(D|R)}{P(D|NR)}>\frac{P(NR)}{P(R)}$

在搜索排序过程中不需要真正的分类，只需要保证相关性由高到底排序即可，所以只需要$\frac{P(D|R)}{P(D|NR)}$降序即可，
这样就最终转为计算$P(D|R)$,$P(D|NR)$的值即可.

二元独立模型(BIM)

词汇独立性假设:文档里面出现的词没有任何关联，这样一个文档的出现就可以转为各个单词出现概率的乘积（虽然这种假设有违实际，但是算起来简单的啊^_^）

上述提到的文档$D$表示为{1,0,1,0,1}，用$p_i$来表示第$i$个单词在相关文档出现的概率,则在已知相关文档集合的情况下，观察到$D$的概率为:

$P(D|R)=p_1 \times (1-p_2) \times p_3 \times (1-p_4) \times p_5$

第1,3,5表示这个单词在$D$中出现,所以其贡献概率为$p_i$，而第2,4这两个单词并没有在$D$中出现，所以其贡献的概率为$1-p_i$

同理在不相关文档中观察到的概率为:

$P(D|NR)=s_1 \times (1-s_2) \times s_3 \times (1-s_4) \times s_5$

最终得到的相关性概率估算为:

$\frac{P(D|R)}{P(D|NR)}=\frac{p_1 \times (1-p_2) \times p_3 \times (1-p_4) \times p_5}{s_1 \times (1-s_2) \times s_3 \times (1-s_4) \times s_5}$

现在将其推广之后可以有通用的式子：

$$\frac{P(D|R)}{P(D|NR)}= \prod_{i:d_i=1} \frac{p_i}{s_i} \times \prod_{i:d_i=0} \frac{1-p_i}{1-s_i}$$

$d_i=1$表示在文档中出现的单词，$d_i=0$表示没在文档中出现的单词:

在这里进一步对上述公式进行等价变换之后有:

$$\begin{equation}\begin{split} \frac{P(D|R)}{P(D|NR)} &=\prod_{i:d_i=1} \frac{p_i}{s_i} \times \left ( \prod_{i:d_i=1} \frac{1-s_i}{1-p_i} \times \prod_{i:d_i=1} \frac{1-p_i}{1-s_i} \right ) \times \prod_{i:d_i=0} \frac{1-p_i}{1-s_i}\\
&= \left ( \prod_{i:d_i=1} \frac{p_i}{s_i} \times \prod_{i:d_i=1} \frac{1-s_i}{1-p_i} \right ) \times \left ( \prod_{i:d_i=1} \frac{1-p_i}{1-s_i} \times \prod_{i:d_i=0} \frac{1-p_i}{1-s_i} \right ) \\
&=\prod_{i:d_i=1} \frac{p_i(1-s_i)}{s_i(1-p_i)} \times \prod_i \frac{1-pi}{1-s_i} \\
&=\prod_{i:d_i=1} \frac{p_i(1-s_i)}{s_i(1-p_i)}
\end{split}\end{equation}$$

其中上面式子第三步的第二部分$\prod_i \frac{1-pi}{1-s_i} $表示各个单词在所有文档中出现的概率，所以这个式子的值和具体文档并没有什么关系，在排序中不起作用，才可以简化到第4步.

为了方便计算，将上述连乘公式取$log$:

$log(\frac{P(D|R)}{P(D|NR)}) = \sum_{i:d_i=1} log \frac{p_i(1-s_i)}{s_i(1-p_i)}$

有了上述最终可计算的式子之后，我们就只需要统计文档$D$中的各个单词在相关文档/不相关文档中出现的概率即可:

	相关文档	不相关文档	文档数量
$d_i=1$	$r_i$	$n_i-r_i$	$n_i$
$d_i=0$	$R-r_i$	$(N-R)-(n_i-r_i)$	$N-n_i$
文档数量	$R$	$N-R$	$N$

上面的表格表示各个单词在文档集合中的相关文档/不相关文档出现数量,同时为了避免$log(0)$出现，加上平滑之后可以计算得到:

$p_i=\frac{r_i+0.5}{R+1}$
$s_i=\frac{(n_i-r_i)+0.5}{(N-R)+1}$

则最终可以得到如下公式:

$\sum_{q_i=d_i=1} log \frac {(r_i+0.5)((N-R)-(n_i-r_i)+0.5)}{(n_i-r_i+0.5)(R-r_i+0.5)}$

上面的公式表示对于同时出现查询$q_i$以及文档$d_i$的时候，对$q_i$在$d_i$中出现的单词在相关文档/不相关文档进行统计，即可得到查询与文档的相关性估计值.

在不确定哪些文档是相关的，哪些文档是不相关的的时候，可以给公式的估算因子直接赋予固定值，则该公式将会蜕化为$IDF$因子.

BM25 模型

模型概述

上一小节中的BIM模型效果并不佳，也没有考虑单词权重，但是他给BM25模型打下了深深的基础

BM25 模型在BIM模型的基础上考虑了查询词在Query以及Doc中的权重，并通过实验引入了一些经验参数。BM25模型是目前最成功的内容排序模型.

改进之后的BM25模型的拟合公式如下:

$\sum_{i\in Q} log \frac {(r_i+0.5)((N-R)-(n_i-r_i)+0.5)}{(n_i-r_i+0.5)(R-r_i+0.5)} \cdot \frac{(k_1+1)f_i}{K+f_i} \cdot \frac{(k_2+1)qf_i}{k_2+qf_i}$

上面的式子中:

1. 第1部分即为上一小节的二元独立模型BIM计算得分
2. 第2部分是查询词在$D$中的权重，其中$f_i$代表词在文档中的词频,$K$因子代表了对文档长度的考虑，其计算公式为$K=k_1((1-b)+b \cdot \frac{dl}{avdl})$
   1. $k_1$为经验参数,这里的$k_1$一般设置为1.2,
   2. $b$为调节因子，将$b$设为0时，文档长度因素将不起作用，经验表明一般$b=0.75$
   3. $dl$代表当前文档的长度
   4. $avdl$代表所有文档的平均长度
3. 第3部分是查询词在自身的权重,$qf_i$表示在查询中的词频,$k_2$也为调节因子，因为在短查询下这部分一般为1，为了放大这部分的差异，$k_2$一般取值为0~1000

综合看来,BM25模型结合了BIM因子、文档长度、文档词频和查询词频进行公式融合，并利用$k_1$、$k_2$、$b$对各种因子进行权重的调整.

栗子

假设当前以乔布斯 IPAD2这个查询词为例，来计算在某文档$D$中BM25相关性的值，由于不知道文档集中相关与不相关的分类，所以这里直接将相关文档个数$r$置为0,则将得到的BIM因子为:

$Rel_{BIM}=log \frac {(0+0.5)((N-0)-(n_i-0)+0.5)}{(n_i-0+0.5)(0-0+0.5)}=log \frac{N-n_i+0.5}{n_i+0.5}$

其他数值假定如下:

1. 文档的集合总数$N=100000$
2. 包含乔布斯的文档个数为$n_{乔布斯}=1000$
3. 包含IPAD2的文档个数为$n_{IPAD2}=100$
4. 文档$D$中出现乔布斯的词频为$f_{乔布斯}=8$
5. 文档$D$中出现IPAD2的词频为$f_{IPAD2}=8$
6. 查询词频均为$qf_i=1$
7. 调节因子$k_1=1.2$
8. 调节因子$k_2=200$
9. 调节因子$b=0.75$
10. 设文档$D$的长度为平均长度的1.5倍($\frac{dl}{avdl}=1.5$),即$K=1.2 \times (0.25+0.75 \times 1.5)=1.65$

则最终可以计算到的BM25结果为:

$Rel_{BM25}=log \frac{100000-1000+0.5}{1000+0.5} \times \frac{(1.2+1) \times 8}{1.65+8} \times \frac{(200+1) \times 1}{200+1}+ log \frac{100000-1000+0.5}{1000+0.5} \times \frac{(1.2+1) \times 5}{1.65+5} \times \frac{(200+1) \times 1}{200+1} = 8.59$

每个文档按上述公式计算得到相关性排序即可.

BM25F 模型

在BM25模型中，文档被当做一个整体进行进行词频的统计，而忽视了不同区域的重要性，BM25F模型正是抓住了这点进行了相应的改进。

BM25F模型在计算相关性时候，会对文档分割成不同的域来进行加权统计，非常适用于网页搜索，因为在一个网页有标题信息、meta信息、页面内容信息等，而标题信息无疑是最重要的，其次是meta信息，最后才是网页内容，BM25F在计算相关性的，会将网页分为不用的区域，在各个区域分别统计自己的词频。
所以BM25F模型的计算公式为:

$$\sum_{i:q_i=d_i=1} log \frac {(r_i+0.5)((N-R)-(n_i-r_i)+0.5)}{(n_i-r_i+0.5)(R-r_i+0.5)} \times \frac{f_i^u}{k_1+f_i^u}$$

BM25F的第1部分还是BIM的值

其中与BM25主要的差别体现在$f_i^u$因子上,它是单词$i$在各个区域不同的得分,计算公式如下:

$$f_i^u=\sum_{k=1}^uw_k \times \frac{f_{ui}}{B_u}$$

$$B_u=((1-b_u)+b_u \times \frac{ul_u}{uvul_u})$$

上面的公式表示:

1. 文档$D$来个不同的$u$个域
2. 各个域对应的权重为$W_k$
3. $f_i^u$为第$i$个单词在各个域中的 $\frac{f_{ui}}{B_u}$ 的加权和
4. $f_{ui}$表示词频
5. $B_u$表示各个域的长度情况
6. $ul_u$为实际域的实际长度,$uvul_u$表示域的平均长度
7. $b_u$则为各个域长度的调节因子

总结

BM25系列的模型主要是考虑查询词到文档里面的各种词频，含有大量自由的调节因子，最终给出查询到文档的相关性，模型都是比较简单的，但是里面提高的相关文档和不相关文档的引入将比较麻烦，有实际场景可以一试。

参考

1. 《这就是搜索引擎：核心技术详解》 . 第五章

---

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。