在最近的工作中，再次接触了bm25用来计算query和doc相关性的问题，在此记录一下bm25计算方法，备查阅。
相关性的度量
搜索引擎最重要的职能，是根据用户输入的query，将文档库中最相关的内容返回给用户，因此相关性贯穿了搜索引擎的各个阶段。为此，我们需要对相关性进行定义和量化，基于量化的数值进行排序，然后将最相关的内容返回给用户。TF-IDF和BM25就是对相关性进行量化的两种计算方法。特别是在召回阶段，由于文本量巨大，使用TF-IDF和BM25这种简单的计算方法可以快速从海量文本中初筛出相关性高的doc。
TF-IDF
TF-IDF是由词频和逆文档词频两项组成。TF即Term Frequency，表示一个词在文档中出现的次数，通常认为一个词在一篇文档中出现的次数阅读，那么这个词越能表示这个文档的主题。其次为了考虑文档长度对词频的影响，通常会用词频除以文档的长度：
$$
TF = \frac{词w在文档中出现的次数}{文档的长度}
$$
IDF表示逆文档词频，其表示的物理含义为一个词在所有文档都出现过，那么这个词对于表示相关性就不那么重要，因为没有区分度。逆文档词频的计算方法：
$$
IDF(w) = log(\frac{N}{N(w) + 1})
$$
$N$表示文档库中的所有文档的数量，$N(w)$表示包含词w的文档的数量，$+1$是为了防止除0错误。
TF-IDF最后是通过TF乘上IDF得到。
对于一个query中有多个词，如果用TF-IDF计算，那么最终的TF-IDF值是累加还是求均值？
BM25
BM25可以认为是TF-IDF的改良，既然是改良，那么必然有与TF-IDF相同的地方和不同的地方。BM25的公式为：
$$
Score(Q, d) = \sum_i^n{W_i R(q_i, d)}
$$
其中，$W_i$表示term的权重，Q表示一个query，$q_i$表示query分词后的term，d表示一篇文档。所以，BM25表示一个term与一篇文档的相关性的加权求和。
权重$W_i$
权重$W_i$其实就是IDF，但是这里的IDF与上面介绍的计算方法有所不同：
$$
W_i = log(\frac{N - df_i + 0.5}{df_i + 0.5})
$$
N表示所有文档的数量，$df_i$表示包含$q_i$的文档量。虽然计算方法不一样，但是IDF的作用是一样的，即越多的文档包含一个term，那么这个term用来区分不同文档的作用就越小。
相关性
相关性包含两个部分：单词与query的相关性和单词与文档的相关性，也即：
$$
R(q_i, d) = S(q_i, d) * S(q_i, Q)
$$
单词与query的相关性
当query很长时，可以通过下面的公式刻画单词与query之间的相关性；但是当query很短时，可以不需要此项：
$$
S(q_i, Q) = \frac{(k_3 + 1)tf_{tq}}{k_3 + tf_{tq}}
$$
上式中，$tf_{tq}$表示词在query中的词频，而$k_3$是一个可调节的参数。
因为query一般都很短，所以不需要考虑这项，而是假设query中词频都是1。
单词与doc的相关性
词频与文档之间的相关性不是线性增加的，当词频达到一个阈值后，其与文档的相关性将不再线性增加，并且这个阈值与与文档本身有关。因此BM25通过下面的公式刻画单词与文档之间的相关性：
$$
S(q_i, d) = \frac{(k_1 + 1)tf_{td}}{K + tf_{td}}
$$
$$
K = k1(1 - b + b * \frac{L_d}{L_{avg}})
$$
其中，$tf_{td}$表示单词t在文档中的词频，$L_d$表示文档的长度，$L_{avg}$表示所有文档的平均长度。变量$k_1$和$b$都是可调节的参数。$k_1$是正参数，用来标准化词频的范围，$k_1=0$时说一个二元模型，即只表示词在或没在文档中出现过。b用来控制文档长度对相关性的影响，当$b=0$时，文档长度对相关性没有影响。
BM25最终的公式
$$
RSV_d = \sum_i^n{[log(\frac{N - ni + 0.5}{ni + 0.5})] \cdot \frac{(k_1 + 1) tf_{td}}{k1(1 - b + b * (L_d / L_{avg})) + tf_{td}} \cdot \frac{(k_2 + 1)tf_{tq}}{k_2 + tf_{tq}}}
$$