bm25算法與tf-idf算法比較

一、tf-idf算法介紹

詞頻（TF）=某篇文章中某個關鍵詞出現的次數/文章總字數，逆文檔頻率（IDF） = log（語料庫文章總數/包含該關鍵詞的文章總數+1），tfidf=tf*idf，下面給大家舉個實例，你大概就明白了，例如語料庫中有以下三篇文章：

第一篇：張一山與楊紫疑似相戀；
第二篇：C羅又一次完成了帽子戲法，這就是足球的魅力；
第三篇：恭喜TES創歷史記錄，在s10的世界總決賽上完成了讓二追三；

首先是對每篇文章進行分詞且過濾停用詞得doc_lis=[[張一山，…，相戀]，[C羅，…，魅力]，[恭喜，…，讓二追三]]，然后依次計算每個關鍵詞的tfidf。TF(張一山)=1/4(“與”作為停用詞過濾掉了所以是4) IDF(張一山)=log(3/1+1)，所以tfidf=TF*IDF=1/4*log3/2=0.25*0.405=0.1，按照這個方式依次計算就能得到所有詞的tfidf，最終的結果如下表：

文章\詞	張一山	楊紫	…	完成	讓二追三
第一篇	0.1	0.1		0	0
第二篇	0	0		0	0
第三篇	0	0		tfidf值	tfidf值

這張表的shape應該（總詞數，總文章數），因此tfidf的應用可以有：
1、文章關鍵詞提取（可以提取tfidf值前幾個作為關鍵詞）；
2、文章分類，這個矩陣直接輸入到項lsvm，lr等模型（當然要打好label）；
3、用LDA或SVD進行降維（為什么要降維，因為語料庫的總詞數是非常多的，所以每篇文章的向量是非常稀疏的），再當做文章的embeding；
4、把tfidf或idf值當做每個詞的權重。

tfidf算法的優點：

簡單，快速，如果語料庫是不變的話，可以提前離線計算好語料庫中所有詞的tfidf值（這在實際應用中非常重要的，后面有這個應用的舉例）

tfidf算法的缺點：

1、僅以“詞頻”度量詞的重要性，后續構成文檔的特征值序列，詞之間各自獨立，無法反映序列信息；
2、tfidf得到是一個稀疏而龐大的矩陣，需要采用降維方式，才方便做后續的文本任務，而降維可能會損失一些信息，同時降維的也會提高模型的復雜度，而失去了原本快速的優點；
3、tfidf得到的embedings再輸入后續的模型，做文本分類、文本匹配等任務，在效果上通常會差于采用詞向量模型訓練得到的embedding。

二、BM25算法介紹

bm25是一種用來評價搜索詞和文檔之間相關性的算法，它是一種基于概率檢索模型提出的算法，再用簡單的話來描述下bm25算法：我們有一個query和一批文檔Ds，現在要計算query和每篇文檔D之間的相關性分數，我們的做法是，先對query進行切分，得到單詞$q_i$，然后單詞的分數由3部分組成：
1、單詞$q_i$和D之間的相關性
2、單詞$q_i$和D之間的相關性
3、每個單詞的權重
最后對于每個單詞的分數我們做一個求和，就得到了query和文檔之間的分數。

bm25算法解釋

講bm25之前，我們要先介紹一些概念。

二值獨立模型 BIM

BIM(binary independence model)是為了對文檔和query相關性評價而提出的算法，BIM為了計算$P(R|d,q)$，引入了兩個基本假設：
假設1
一篇文章在由特征表示的時候，只考慮詞出現或者不出現，具體來說就是文檔d在表示為向量$\vec x=(x_1,x_2,…,x_n)$，其中當詞$t$出現在文檔d時，$x_t=1$，否在$x_t=0$。
假設2
文檔中詞的出現與否是彼此獨立的，數學上描述就是$P(D)=\sum_{i=0}^n P(x_i)$
有了這兩個假設，我們來對文檔和query相關性建模：

其中

分別表示當返回一篇相關或不相關文檔時文檔表示為x的概率。
接著因為我們最終得到的是一個排序，所以，我們通過計算文檔和query相關和不相關的比率，也可得文檔的排序，有下面的公式：

其中

是常數，我們可以不考慮，再根據之前的假設2：一個詞的出現 與否與任意一個其他詞的出現與否是互相獨立的，我們可以化簡上面的式子：

我們接著引入一些記號：

詞出現在相關文檔的概率

詞出現在不相關文檔的概率

于是我們就可得到：

我們接著做下面的等價變換：

此時，公式中

根據出現在文檔中的詞計算，

則是所有詞做計算，不需要考慮，此時我們定義RSV （retrieval status value），檢索狀態值：

定義單個詞的ct

下一步我們要解決的就是怎么去估計pt和ut，看下表：

其中dft是包含詞t的文檔總數，于是

此時詞t的ct值是：

為了做平滑處理，我們都加上1/2，得到：

在實際中，我們很難知道t的相關文檔有多少，所以假設S=s=0，所以：

其中N是總的文檔數，dft是包含t的文檔數。
以上就是BIM的主要思想，后來人們發現應該講BIM中沒有考慮到的詞頻和文檔長度等因素都考慮進來，就有了后面的BM25算法，下面按照
1、單詞t和D之間的相關性
2、單詞t和D之間的相關性
3、每個單詞的權重
3個部分來介紹bm25算法。

單詞權重
單詞的權重最簡單的就是用idf值，即

，也就是有多少文檔包含某個單詞信息進行變換。如果在這里使用 IDF 的話，那么整個 BM25 就可以看作是一個某種意義下的 TF-IDF，只不過 TF 的部分是一個復雜的基于文檔和查詢關鍵字、有兩個部分的詞頻函數，還有一個就是用上面得到的ct值。
單詞和文檔的相關性
tf-idf中，這個信息直接就用“詞頻”，如果出現的次數比較多，一般就認為更相關。但是BM25洞察到：詞頻和相關性之間的關系是非線性的，具體來說，每一個詞對于文檔相關性的分數不會超過一個特定的閾值，當詞出現的次數達到一個閾值后，其影響不再線性增長，而這個閾值會跟文檔本身有關。
在具體操作上，我們對于詞頻做了”標準化處理“，具體公式如下：

其中，tftd 是詞項 t 在文檔 d 中的權重，Ld 和 Lave 分別是文檔 d 的長度及整個文檔集中文檔的平均長度。k1是一個取正值的調優參數，用于對文檔中的詞項頻率進行縮放控制。如果 k 1 取 0，則相當于不考慮詞頻，如果 k 1取較大的值，那么對應于使用原始詞項頻率。b 是另外一個調節參數 （0≤ b≤ 1），決定文檔長度的縮放程度：b = 1 表示基于文檔長度對詞項權重進行完全的縮放，b = 0 表示歸一化時不考慮文檔長度因素。
單詞和查詢的相關性
如果查詢很長，那么對于查詢詞項也可以采用類似的權重計算方法。

其中，tftq是詞項t在查詢q中的權重。這里k3 是另一個取正值的調優參數，用于對查詢中的詞項tq 頻率進行縮放控制。
于是最后的公式是：

bm25算法gensim中的實現
gensim在實現bm25的時候idf值是通過BIM公式計算得到的：

然后也沒有考慮單詞和query的相關性。

其中幾個關鍵參數取值：
PARAM_K1 = 1.5
PARAM_B = 0.75
EPSILON = 0.25
此處EPSILON是用來表示出現負值的時候怎么獲取idf值的。

bm25的算法的優點：
優點：可以方便線下做離線先計算好文檔中出現的每一個詞的idf并保存為一個字典，當用戶搜了一個query，直接分詞然后查字典就能得到這個詞的idf，如果字典中沒有idf值無意義，因為R=0。同于tfidf。
缺點：同于tfidf

總結下本文的內容：BM25是檢索領域里最基本的一個技術，BM25 由三個核心的概念組成，包括詞在文檔中相關度、詞在查詢關鍵字中的相關度以及詞的權重。BM25里的一些參數是經驗總結得到的，后面我會繼續介紹BM25的變種以及和其他文檔信息（非文字）結合起來的應用。

bm25算法適用于什么情況

BM25算法，通常用來作搜索相關性平分。一句話概況其主要思想：對Query進行語素解析，生成語素qi；然后，對于每個搜索結果D，計算每個語素qi與D的相關性得分，最后，將qi相對于D的相關性得分進行加權求和，從而得到Query與D的相關性得分。
BM25算法的一般性公式如下：

其中，Q表示Query，qi表示Q解析之后的一個語素（對中文而言，我們可以把對Query的分詞作為語素分析，每個詞看成語素qi。）；d表示一個搜索結果文檔；Wi表示語素qi的權重；R(qi，d)表示語素qi與文檔d的相關性得分。
下面我們來看如何定義Wi。判斷一個詞與一個文檔的相關性的權重，方法有多種，較常用的是IDF。這里以IDF為例，公式如下：

其中，N為索引中的全部文檔數，n(qi)為包含了qi的文檔數。
根據IDF的定義可以看出，對于給定的文檔集合，包含了qi的文檔數越多，qi的權重則越低。也就是說，當很多文檔都包含了qi時，qi的區分度就不高，因此使用qi來判斷相關性時的重要度就較低。
我們再來看語素qi與文檔d的相關性得分R（qi，d）。首先來看BM25中相關性得分的一般形式：

其中，k1，k2，b為調節因子，通常根據經驗設置，一般k1=2，b=0.75；fi為qi在d中的出現頻率，qfi為qi在Query中的出現頻率。dl為文檔d的長度，avgdl為所有文檔的平均長度。由于絕大部分情況下，qi在Query中只會出現一次，即qfi=1，因此公式可以簡化為：

從K的定義中可以看到，參數b的作用是調整文檔長度對相關性影響的大小。b越大，文檔長度的對相關性得分的影響越大，反之越小。而文檔的相對長度越長，K值將越大，則相關性得分會越小。這可以理解為，當文檔較長時，包含qi的機會越大，因此，同等fi的情況下，長文檔與qi的相關性應該比短文檔與qi的相關性弱。
綜上，BM25算法的相關性得分公式可總結為：

從BM25的公式可以看到，通過使用不同的語素分析方法、語素權重判定方法，以及語素與文檔的相關性判定方法，我們可以衍生出不同的搜索相關性得分計算方法，這就為我們設計算法提供了較大的靈活性。