BM25演算法以及變種演算法簡介

深入理解TF-IDF、BM25演算法與BM25變種：揭秘資訊檢索的核心原理與套用 原文連結： https://xie.infoq.cn/article/8b7232877d0d4327a6943e8ac

BM25演算法以及變種演算法簡介

Okapi BM25，一般簡稱 BM25 演算法，在 20 世紀 70 年代到 80 年代，由英國一批資訊檢索領域的電腦科學家發明。這裏的 BM 是 「最佳匹配」（Best Match）的縮寫，Okapi 是第一個使用這種方法的資訊獲取系統的名稱。在資訊檢索領域，BM25 演算法是工程實踐中舉足輕重的重要的 Baseline 演算法。迄今為止距 BM25 的提出已經過去三十多年，但是這個演算法依然在很多資訊檢索的任務中表現優異，是很多工程師首選的演算法之一。

BM25（Best Match 25）是一種用於資訊檢索的統計演算法，主要用於計算查詢文本與文件的相關性評分。它考慮了文件中的詞頻（）和逆文件頻率（）等因素。主要對對 Query 進行語素解析，生成語素 (詞)；然後，對於每個搜尋結果 ，計算每個語素 與 的相關性得分，最後，將 「一個 各個 相對於 的相關性得分」 加權求和，從而得到「 與 的相關性得分」。

以下是 BM25 的一些重要的變種和衍化演算法：

BM25 詳解

首先，簡單概括 BM25 究竟作何用途。BM25 演算法實質上是一個用於資訊檢索中，對給定查詢（query）和若幹 「相關」 文件（document）進行相關性排序打分的排序函式。嚴格來講，這不是一個打分函式，而是一個家族的一系列評分函式，因為它的提出並非一蹴而就的事情，它的發明經過了若幹試驗叠代演進。一般情況下，這個相關性打分是一個類似 TF-IDF 的基於統計計數的無監督學習過程。

BM25 演算法其主要思想可簡述如下：對 query 進行特征提取分解，生成若幹特征項（詞）；然後對於每個搜尋結果 D，計算每個特征與 D 的相關性得分，最後，將 相對於 D 的相關性得分進行加權求和，從而得到與的相關性得分。

BM25 演算法的一般表示可簡寫為如下形式：

其中， 表示 , 表示 分解之後的一個特征項（對中文而言我們可以把對 query 的分詞作為基本特征項）， 表示一個搜尋結果文件； 表示特征 的權重；表示特征項 與文件 的相關性得分。

上面這個一般的式子裏的 和 的具體計算，都是基於詞袋方法的詞頻計數，它不考慮多個搜尋詞在文件裏的關聯性，只考慮它們各自的出現次數。 下面我們來考察以上得分函式的兩個量 和 該如何設計和計算。 首先來看如何定義 ，考察一個特征詞的權重，方法比較多，較常用的是 IDF，BM25 選擇的是 Robertson-Sparck Jones IDF:

其中， 為文件集合中的全部文件數， 為包含 的文件數。 公式指出， 出現在越多的文件中，則 的權重則越低。這裏個定義有個問題，那就是，如果一個詞在超過半數的文件裏出現，則 為負值，於是這個詞對 BM25 分數的貢獻是負的。一般不希望這樣的特性，所以當 為負數時，可將其置為 0，或者一個比較小的正數，或者改用一種平滑過渡到 0 的函式形式。

我們再來考察特征項 與文件 的相關性得分 。 比較樸素的考慮可以用特征詞的文件詞頻來簡單表示 ，但這種直觀的想法不可避免導致長文本中，詞的頻度普遍較高，最終相關性得分會過度傾向於長文本，顯然不盡合理；另一方面，不難想象到，某個詞對文件的貢獻不應該無限度地隨詞頻增長而線性增加，當該詞的詞頻高於某個程度就應該趨於飽和，而不應該讓其得分貢獻無限度增大，從而在整個得分求和式子中占支配地位。 基於以上兩方面的考慮，BM25 采取了以下方式來計算 ：

這裏， 為 在 中的文件頻率， 為文件長度， 為文件集合中的平均長度， 和 為可自由調節的超參數，一般取值範圍是 ， 關於 的函式是一個 「飽和」 的遞增函式，使得文件詞頻增長對相關性得分增長成為非線性的。

從 的定義中不難看出，超參數 起著調節特征詞文本頻率尺度的作用， 取 意味著演算法退化為二元模型（不考慮詞頻），而取較大的值則近似於只用原始的特征詞頻。超參數 一般稱作文本長度的規範化，作用是調整文件長度對相關性影響的大小。 越大，文件長度的對相關性得分的影響越大，而文件的相對長度越長， 值將越大，則相關性得分會越小。這可以理解為，當文件相對較長時，包含 的機會越大，因此，同等 的情況下，長文件與 的相關性應該比短文件與 的相關性弱。 至此，綜合上述討論，BM25 的一般形式可完整表示如下：

此外，若 query 比較長，且某些 term 在 query 中出現頻率較高，我們理應考慮這些 term 的重要性也該相應提高，但同樣應該有類似 term 相對文件的飽和增長設定來約束 query 中的 term 頻率增長。這裏我們將類似的權重策略用於 query 中的特征項，得到：

其中， 為特征項 在查詢 中的頻率，超參數 的作用依然是調節特征詞在 query 文本頻率尺度，此時對 query 進行長度規範化卻是不必要的，因為對所有候選檢索結果而言，query 是先有的固定好的。 從以上對 BM25 的完整討論，我們知道了 BM25 其實是一個（準確說，是一系列）經驗公式，這裏面的每一個環節都是經過很多研究者的叠代而逐步發現的。很多研究在理論上對 BM25 進行了建模，從 「機率相關模型」（Probabilistic Relevance Model）入手，推匯出 BM25 其實是對某一類機率相關模型的逼近，對此我還沒有詳盡研究，就無法進一步展開論述了。從結果上看，我們應該明了 BM25 權重計算公式，已經在眾多的數據集和搜尋任務上，被極其高頻廣泛和成功地使用。

BM25演算法簡易

一條 Query 與搜尋結果的任意 doc 之間相關性分數:

上式， 表示， 表示根據 解析獲得的語素， 表示搜尋結果的一條文件， 表示語素 q_i的權重， R(q_i, d)表示q_i和d的相關性得分。 （1） W_i的定義 定義一個語素與一個文件的相關性權重，較常用的是上式， 是索引中的全部文件數，是包含 的文件數。 很顯然， 與成反相關，即當給定的文件集合裏，很多文件都包含 時， 的區分度就不高，則使用來判斷相關性的重要度就較低。 （2） 的定義 定義一個語素與一個文件的相關性得分，一般形式如下上式 ， ， 是可根據經驗設定的調節因子，一般 ， ； 是 在 中出現的頻率， 為 在 中的出現頻率。 為 的長度， 為文件集中所有 的平均長度。在多數情況下， 在中只會出現一次，即 ，公式可簡化為：

由 K 的運算式可知，的作用是調整 對 「相關性的影響」 的大小，即越大，對 「相關性得分的影響」 越大；而 越長， 值越大，相關性得分越小。 可如下解釋，當文件較長時，包含的機會越大，則同等的情況下，「長文件與的相關性」 應該比 「短文件與的相關性」 弱。

BM25 的變種和改進

BM25 演算法公式，透過使用不同的特征項的分析方法、特征項權重判定方法，以及特征項與文件的相關度計算方法，都留有較強的靈活性，自然會促使後續的研究者在此基礎上，提出更具個人化的不同的搜尋相關性得分演算法。

所有 BM25 後續改進中，Lv & Zhai 兩位研究者的工作最為深入和全面。

BM25L

Lv & Zhai 觀察到 BM25 公式中的文本長度規範化項（L_d/L_{avg}）使得模型得分過於偏好長度較短的文件。他們在 「When documents are very long, BM25 fails!」 一文中提出了 BM25L 演算法，用來彌補 BM25 的這一不足。 首先，BM25L 對特征詞的 IDF 權重項也做了小小改變，讓這一項不會取到負值：

然而，BM25L 更感興趣的是調節 BM25 中這一項，以避免演算法對過長文本的懲罰。Lv & Zhai 透過對加上一個正值的常數來實作這一點，只需這一個小操作便可以起到讓與之前比較，向偏好取更小的值轉移（即較大的分母，較長的文本）。 因此，可將 BM25L 演算法寫作如下：

同 BM25 公式記號保持一致，這裏

BM25+

Lv & Zhai 進一步發現對過長文本的懲罰不止出現在 BM25 演算法中，還出現在許多其他的排序函式中，他們為此提出了一個一般性的解決方案，即為每一個 query 中出現於文本的特征項相關性得分設定一個下界。此時，不論文本多長，某個搜尋特征項至少貢獻了一個正的常數相關性得分。他們這個做法略不同於之前的 BM25L，而是在乘 IDF 之前對整個 加上一個常數 ：

BM25-adpt

之前的 BM25 演算法和相關改進，都忽略了對超參數 的考察。Lv & Zhai 在不同的 BM25 相關研究工作中，發現對實際套用而言，全域的 參數不及特征項相關的（term-specific）參數使用起來高效。他們用隨機理論中的資訊增益和散度等概念，實作了去 「超參化」 的目標，即 跟隨 不同而變化，可以直接計算獲得，這個演算法被稱為 BM25-adpt。BM25-adpt 的具體推導比上面的 BM25 變種演算法要稍微復雜一些，要講清楚其中的想法和細節，需要另辟篇幅，只好以後得空的時候補綴上，這裏就不能多加介紹了。

小結

除了以上探討的幾種 BM25 的衍化演算法，其他重要的變種還有 等等，在許多不同的場景都表現除了優於原始 BM25 演算法的效果。當然，這些表現的優越性因具體數據集和相應 search 任務場景而異。

參考連結：