bm25算法

bm25算法，常用作搜索相关性评分。

bm25算法主要思想

对Query进行语素解析，生成语素qi(词)；然后，对于每个搜索结果d，计算每个语素qi与d的相关性得分，最后，将“一个Query各个qi相对于d的相关性得分”加权求和，从而得到“Query与d的相关性得分”。

bm25算法原理及公式推导

一条Query与搜索结果的任意doc之间相关性分数
$$Score(Q,d)=\sum _i^n{W}_{i}R(q_i,d)$$
上式，$Q$表示Query，$q_i$表示根据$Q$解析获得的语素，$d$表示搜索结果的一条文档，$W_i$表示语素$q_i$的权重，$R(q_i,d)$表示$q_i$和$d$的相关性得分。

（1）$W_i$的定义
定义一个语素与一个文档的相关性权重，较常用的是
$$IDF(q_i)=log\frac{N-n(q_i)+0.5}{n(q_i)+0.5}$$
上式，$N$是索引中的全部文档数，$n(q_i)$是包含$q_i$的文档数。
很显然，$n(q_i)$与$IDF(q_i)$成反相关，即当给定的文档集合里，很多文档都包含$q_i$时，$q_i$的区分度就不高，则使用$q_i$来判断相关性的重要度就较低。

（2）$R(q_i,d)$的定义
定义一个语素与一个文档的相关性得分，一般形式如下
$$R(q_i,d)=\frac{f_i(k_1+1)}{f_i+K}\frac{q{f}_i(k_2+1)}{q{f}_i+k_2}$$
$$K=k_1(1-b+b\frac{dl}{avgdl})$$
上式，$k_1$，$k_2$，$b$是可根据经验设置的调节因子，一般$k_1\in [1.2,2]$，$b=0.75$；$f_i$是$q_i$在$d$中出现的频率，$q{f}_i$为$q_i$在$Q$中的出现频率。$dl$为$d$的长度，$avgdl$为文档集中所有$d$的平均长度。在多数情况下，$q_i$在$Q$中只会出现一次，即$q{f}_i=1$，公式可简化为：
$$R(q_i,d)=\frac{f_i(k_1+1)}{f_i+K}$$
由$K$的表达式可知，$b$的作用是调整$dl$对“相关性的影响”的大小，即b越大，$dl$对“相关性得分的影响”越大；而$dl$越长，$K$值越大，相关性得分越小。
可如下解释，当文档较长时，包含$q_i$的机会越大，则同等$f_i$的情况下，“长文档与$q_i$的相关性”应该比“短文档与$q_i$的相关性”弱。