本文cmd地址：經(jīng)典檢索算法：BM25原理
bm25 是什么？
bm25 是一種用來評(píng)價(jià)搜索詞和文檔之間相關(guān)性的算法孕暇，它是一種基于概率檢索模型提出的算法，再用簡(jiǎn)單的話來描述下bm25算法：我們有一個(gè)query和一批文檔Ds辐董，現(xiàn)在要計(jì)算query和每篇文檔D之間的相關(guān)性分?jǐn)?shù)甚亭，我們的做法是，先對(duì)query進(jìn)行切分怔匣，得到單詞$q_i$握联，然后單詞的分?jǐn)?shù)由3部分組成：
- 單詞$q_i$和D之間的相關(guān)性
- 單詞$q_i$和D之間的相關(guān)性
- 每個(gè)單詞的權(quán)重
最后對(duì)于每個(gè)單詞的分?jǐn)?shù)我們做一個(gè)求和，就得到了query和文檔之間的分?jǐn)?shù)每瞒。
bm25 解釋
講bm25之前金闽，我們要先介紹一些概念。
二值獨(dú)立模型 BIM
BIM(binary independence model)是為了對(duì)文檔和query相關(guān)性評(píng)價(jià)而提出的算法剿骨，BIM為了計(jì)算$P(R|d,q)$代芜，引入了兩個(gè)基本假設(shè)：
假設(shè)1
一篇文章在由特征表示的時(shí)候，只考慮詞出現(xiàn)或者不出現(xiàn)浓利，具體來說就是文檔d在表示為向量$\vec x=(x_1,x_2,...,x_n)$挤庇，其中當(dāng)詞$t$出現(xiàn)在文檔d時(shí)，$x_t=1$贷掖，否在$x_t=0$嫡秕。
假設(shè)2
文檔中詞的出現(xiàn)與否是彼此獨(dú)立的，數(shù)學(xué)上描述就是$P(D)=\sum_{i=0}^n P(x_i)$
有了這兩個(gè)假設(shè)羽资，我們來對(duì)文檔和query相關(guān)性建模：
其中
接著因?yàn)槲覀冏罱K得到的是一個(gè)排序，所以屠升，我們通過計(jì)算文檔和query相關(guān)和不相關(guān)的比率潮改，也可得文檔的排序，有下面的公式：
其中
由于每個(gè) xt 的取值要么為 0 要么為 1脏答，所以糕殉，我們可得到：
我們接著引入一些記號(hào)：
于是我們就可得到：
我們接著做下面的等價(jià)變換：
此時(shí)，公式中
定義單個(gè)詞的ct
下一步我們要解決的就是怎么去估計(jì)pt和ut羡洁，看下表：
其中dft是包含詞t的文檔總數(shù)，于是
此時(shí)詞t的ct值是：
為了做平滑處理筑煮，我們都加上1/2辛蚊，得到：
在實(shí)際中，我們很難知道t的相關(guān)文檔有多少真仲，所以假設(shè)S=s=0袋马，所以：
其中N是總的文檔數(shù)，dft是包含t的文檔數(shù)秸应。
以上就是BIM的主要思想虑凛，后來人們發(fā)現(xiàn)應(yīng)該講BIM中沒有考慮到的詞頻和文檔長(zhǎng)度等因素都考慮進(jìn)來，就有了后面的BM25算法灸眼，下面按照
- 單詞t和D之間的相關(guān)性
- 單詞t和D之間的相關(guān)性
- 每個(gè)單詞的權(quán)重
3個(gè)部分來介紹bm25算法卧檐。
單詞權(quán)重
單詞的權(quán)重最簡(jiǎn)單的就是用idf值，即
焰宣，也就是有多少文檔包含某個(gè)單詞信息進(jìn)行變換霉囚。如果在這里使用 IDF 的話，那么整個(gè) BM25 就可以看作是一個(gè)某種意義下的 TF-IDF匕积，只不過 TF 的部分是一個(gè)復(fù)雜的基于文檔和查詢關(guān)鍵字盈罐、有兩個(gè)部分的詞頻函數(shù)，還有一個(gè)就是用上面得到的ct值闪唆。
單詞和文檔的相關(guān)性
tf-idf中盅粪，這個(gè)信息直接就用“詞頻”，如果出現(xiàn)的次數(shù)比較多悄蕾，一般就認(rèn)為更相關(guān)票顾。但是BM25洞察到：詞頻和相關(guān)性之間的關(guān)系是非線性的，具體來說帆调，每一個(gè)詞對(duì)于文檔相關(guān)性的分?jǐn)?shù)不會(huì)超過一個(gè)特定的閾值奠骄，當(dāng)詞出現(xiàn)的次數(shù)達(dá)到一個(gè)閾值后，其影響不再線性增長(zhǎng)番刊，而這個(gè)閾值會(huì)跟文檔本身有關(guān)含鳞。
在具體操作上，我們對(duì)于詞頻做了”標(biāo)準(zhǔn)化處理“芹务，具體公式如下：
其中蝉绷，tftd 是詞項(xiàng) t 在文檔 d 中的權(quán)重，Ld 和 Lave 分別是文檔 d 的長(zhǎng)度及整個(gè)文檔集中文檔的平均長(zhǎng)度枣抱。k1是一個(gè)取正值的調(diào)優(yōu)參數(shù)熔吗，用于對(duì)文檔中的詞項(xiàng)頻率進(jìn)行縮放控制。如果 k 1 取 0佳晶，則相當(dāng)于不考慮詞頻磁滚，如果 k 1取較大的值，那么對(duì)應(yīng)于使用原始詞項(xiàng)頻率。b 是另外一個(gè)調(diào)節(jié)參數(shù) （0≤ b≤ 1）垂攘，決定文檔長(zhǎng)度的縮放程度：b = 1 表示基于文檔長(zhǎng)度對(duì)詞項(xiàng)權(quán)重進(jìn)行完全的縮放，b = 0 表示歸一化時(shí)不考慮文檔長(zhǎng)度因素淤刃。
單詞和查詢的相關(guān)性
如果查詢很長(zhǎng)晒他，那么對(duì)于查詢?cè)~項(xiàng)也可以采用類似的權(quán)重計(jì)算方法。
其中逸贾，tftq是詞項(xiàng)t在查詢q中的權(quán)重陨仅。這里k3 是另一個(gè)取正值的調(diào)優(yōu)參數(shù)，用于對(duì)查詢中的詞項(xiàng)tq 頻率進(jìn)行縮放控制铝侵。
于是最后的公式是：
bm25 gensim中的實(shí)現(xiàn)
gensim在實(shí)現(xiàn)bm25的時(shí)候idf值是通過BIM公式計(jì)算得到的：
然后也沒有考慮單詞和query的相關(guān)性灼伤。
其中幾個(gè)關(guān)鍵參數(shù)取值：
PARAM_K1 = 1.5
PARAM_B = 0.75
EPSILON = 0.25
此處EPSILON是用來表示出現(xiàn)負(fù)值的時(shí)候怎么獲取idf值的。
總結(jié)下本文的內(nèi)容：BM25是檢索領(lǐng)域里最基本的一個(gè)技術(shù)咪鲜，BM25 由三個(gè)核心的概念組成狐赡，包括詞在文檔中相關(guān)度、詞在查詢關(guān)鍵字中的相關(guān)度以及詞的權(quán)重疟丙。BM25里的一些參數(shù)是經(jīng)驗(yàn)總結(jié)得到的颖侄，后面我會(huì)繼續(xù)介紹BM25的變種以及和其他文檔信息（非文字）結(jié)合起來的應(yīng)用。
參考
BM25 算法淺析
搜索之 BM25 和 BM25F 模型
經(jīng)典搜索核心算法：BM25 及其變種
信息檢索導(dǎo)論
