週一我們講了 TF-IDF 算法和它的四個變種，相對於 TF-IDF 而言，在信息檢索和文本挖掘領域，BM25 算法則更具理論基礎，而且是工程實踐中當仁不讓的重要基線（Baseline）算法 。BM25 在 20 世紀 70 年代到 80 年代被提出，到目前為止已經過去二三十年了，但是這個算法依然在很多信息檢索的任務中表現優異，是很多工程師首選的算法之一。
今天我就來談談 BM25 算法的歷史、算法本身的核心概念以及 BM25 的一些重要變種，幫助你快速掌握這個信息檢索和文本挖掘的利器。
BM25 的歷史
BM25，有時候全稱是 Okapi BM25，是由英國一批信息檢索領域的計算機科學家開發的排序算法。這裡的“BM”是“最佳匹配”（Best Match）的簡稱。
BM25 背後有兩位著名的英國計算機科學家。第一位叫斯蒂芬·羅伯遜（Stephen Robertson）。斯蒂芬最早從劍橋大學數學系本科畢業，然後從城市大學（City University）獲得碩士學位，之後從倫敦大學學院（University College London）獲得博士學位。斯蒂芬從 1978 年到 1998 年之間在城市大學任教。1998 年到 2013 年間在微軟研究院劍橋實驗室工作。我們之前提到過，美國計算機協會 ACM 現在每三年頒發一次“傑拉德·索爾頓獎”，用於表彰對信息檢索技術有突出貢獻的研究人員。2000 年這個獎項頒給斯蒂芬，獎勵他在理論方面對信息檢索的貢獻。BM25 可謂斯蒂芬一生中最重要的成果。
另外一位重要的計算機科學家就是英國的卡倫·瓊斯（Karen Spärck Jones）。週一我們在 TF-IDF 的文章中講過。卡倫也是劍橋大學博士畢業，並且畢生致力於信息檢索技術的研究。卡倫的最大貢獻是發現 IDF 以及對 TF-IDF 的總結。卡倫在 1988 年獲得了第二屆“傑拉德·索爾頓獎”。
BM25 算法詳解
現代 BM25 算法是用來計算某一個目標文檔（Document）相對於一個查詢關鍵字（Query）的“相關性”（Relevance）的流程。通常情況下，BM25 是“非監督學習”排序算法中的一個典型代表。
顧名思義，這裡的“非監督”是指所有的文檔相對於某一個查詢關鍵字是否相關，這個信息是算法不知道的。也就是說，算法本身無法簡單地從數據中學習到相關性，而是根據某種經驗法則來“猜測”相關的文檔都有什麼特質。
那麼 BM25 是怎麼定義的呢？我們先來看傳統的 BM25 的定義。一般來說，經典的 BM25 分為三個部分：
單詞和目標文檔的相關性
單詞和查詢關鍵詞的相關性
單詞的權重部分
這三個部分的乘積組成某一個單詞的分數。然後，整個文檔相對於某個查詢關鍵字的分數，就是所有查詢關鍵字裡所有單詞分數的總和。
我們先從第一部分說起，即單詞和目標文檔的相關性。這裡相關性的基本思想依然是“詞頻”，也就是 TF-IDF 裡面 TF 的部分。詞頻就是單詞在目標文檔中出現的次數。如果出現的次數比較多，一般就認為更相關。和 TF-IDF 不同，BM25 最大的貢獻之一就是挖掘出了詞頻和相關性之間的關係是非線性的，這是一個初看有違常理但細想又很有道理的洞察。
具體來說，每一個詞對於文檔相關性的分數不會超過一個特定的閾值。這個閾值當然是動態的，根據文檔本身會有調整。這個特徵就把 BM25 裡的詞頻計算和一般的 TF 區分開了。也就是說，詞頻本身需要“標準化”（Normalization），要達到的效果是，某一個單詞對最後分數的貢獻不會隨著詞頻的增加而無限增加。
那 BM25 裡詞頻的標準化是怎麼做的呢？就是某一個詞的詞頻，除以這個詞的詞頻加上一個權重。這個權重包含兩個超參數（Hyper-parameter），這些超參數後期是可以根據情況手動調整的。這個做法在非監督的排序算法中很普遍。同時，這個權重還包括兩個重要信息：第一，當前文檔的長度；第二，整個數據集所有文檔的平均長度。
這幾個因素混合在一起，我們就得到了一個新的詞頻公式，既保證單詞相對於文檔的相關度和這個單詞的詞頻呈現某種正向關係，又根據文檔的相對長度，也就是原始長度和所有文檔長度的一個比值關係，外加一些超參數，對詞頻進行了限制。
有了單詞相對於文檔的相關度計算公式作為基礎，單詞相對於查詢關鍵字的相關度可以說是異曲同工。首先，我們需要計算單詞在查詢關鍵字中的詞頻。然後，對這個詞頻進行類似的標準化過程。
和文檔的標準化過程唯一的區別，這裡沒有采用文檔的長度。當然，對於查詢關鍵字來說，如果需要使用長度，也應該是使用查詢關鍵字的長度和平均長度。但是，根據 BM25 經典公式來說，這一部分並沒有使用長度信息進行重新標準化。
接著我來談談最後一個部分，單詞權重的細節，通常有兩種選擇。
第一種選擇就是直接採用某種變形的 IDF 來對單詞加權。一般來說，IDF 就是利用對數函數（Log 函數）對“文檔頻率”，也就是有多少文檔包含某個單詞信息進行變換。這裡回顧一下週一講的內容，IDF 是“文檔頻率”的倒數，並且通過對數函數進行轉換。如果在這裡使用 IDF 的話，那麼整個 BM25 就可以看作是一個某種意義下的 TF-IDF，只不過 TF 的部分是一個複雜的基於文檔和查詢關鍵字、有兩個部分的詞頻函數。
第二種單詞的權重選擇叫作“羅伯遜 - 斯巴克 - 瓊斯”權重（Robertson-Spärck-Jones），簡稱 RSJ 值，是由計算機科學家斯蒂芬·羅伯遜和卡倫·瓊斯合作發現。我們剛才講過，這兩位都是重要的信息檢索學術權威。這個權重其實就是一個更加複雜版本的 IDF。一個關鍵的區別是 RSJ 值需要一個監督信息，就是要看文檔對於某個查詢關鍵字是否相關，而 IDF 並不需要。
對比以上兩種思路，在很多情況下，利用 IDF 來直接進行單詞權重的版本更加普遍。如果在有監督信息的情況下，RSJ 值也不失為一個很好的選擇。
通過這裡簡單的介紹，我們可以很容易地發現，BM25 其實是一個經驗公式。這裡面的每一個成分都是經過很多研究者的迭代而逐步發現的。很多研究在理論上對 BM25 進行了建模，從“概率相關模型”（Probabilistic Relevance Model）入手，推導出BM25 其實是對某一類概率相關模型的逼近。對這一部分我在這裡就不展開論述了。需要你記住的是，BM25 雖然是經驗公式，但是在實際使用中經常表現出驚人的好效果。因此，很有必要對這一類文檔檢索算法有所瞭解。
BM25 算法變種
由於 BM25 的情況，一方面是經驗公式，另一方面是某種理論模型的逼近，這樣就出現了各式各樣的 BM25 變種。這裡我僅僅介紹一些有代表性的擴展。
一個重要的擴展是BM25F，也就是在 BM25 的基礎上再多個“域”（Field）文檔上的計算。這裡“域”的概念可以理解成一個文檔的多個方面。比如，對於很多文檔來說，文檔包括標題、摘要和正文。這些組成部分都可以認為是不同的“域”。那麼，如何結合不同的“域”，讓文檔的相關性能夠統一到一個分數上就是 BM25F 的核心內容。
具體來說，BM25F 對於 BM25 的擴展很直觀。那就是每一個單詞對於文檔的相關性是把各個域當做一個“小文檔”的加權平均。也就是說，我們先把每個域當做單獨的文檔，計算詞頻，進行標準化。然後集合每個域的值，進行加權平均，再乘以詞的權重（我們上面提到了，用 IDF 或者是 RSJ 值）。
另外一個重要的擴展就是把 BM25 和其他文檔信息（非文字）結合起來。這個想法是在“學習排序”（Learning To Rank）這一思路出現以前的一種普遍的做法，往往就是用線性加權的形式直接把各種信息相結合。例如，在 21 世紀初期比較流行的做法是用 BM25 和 PageRank 的線性結合來確定網頁的相關度。這裡面，BM25 是和某個查詢關鍵字有聯繫的信息，而 PageRank 則是一個網頁的總體權重。
小結
今天我為你講了文檔檢索領域或者說搜索領域裡最基本的一個技術：BM25。我們可以看到，BM25 由三個核心的概念組成，包括詞在文檔中相關度、詞在查詢關鍵字中的相關度以及詞的權重。BM25 是一個長期積累的經驗公式，也有很深的理論支持，是一個強有力的非監督學習方法的文本排序算法。
一起來回顧下要點：第一，簡要介紹了 BM25 的歷史。第二，詳細介紹了 BM25 算法的三個主要組成部分。第三，簡要地介紹了 BM25 的一些變種 。
最後，給你留一個思考題，雖然 BM25 是非監督的排序方法，並且我們提到其中有一些超參數，那麼是否可以通過機器學習的手段來學習到這些超參數的最佳取值呢？
閱讀更多 小鳥編程 的文章
