BM25 是一個經典的數學公式，廣泛應用於評估文件與查詢字串之間的相關性，因此在某些搜索引擎的搜索結果排序中扮演重要角色。例如，Elasticsearch 就內建了使用 BM25 進行結果排序的功能。
此外，在 AI 領域，像是 RAG (Retrieval-Augmented Generation) 等應用，也實作使用 BM25 來檢索(retrieve)相關文件。
對 BM25 有所理解的話，將會對從事搜索相關工作的人有所裨益。
本文將以白話文說明搭配範例的方式，介紹 BM25 公式以及如何計算。
BM25 簡介
BM25 又稱 Okapi BM25, 其中 BM 代表 Best Matching 的意思。
BM25 經常用於排序搜尋引擎的搜尋結果，它的原理是計算 1 個文件與搜尋詞之間的相關程度，相關程度越高，搜尋結果就應該將該文件放到越前面。 (詳見好文分享 — 80 行程式碼做出 1 個搜尋引擎）
BM25 公式
BM25 公式如下所示：
上述公式中的 IDF(qi) 公式如下， IDF 全名為 Inverse Document Frequency：
相信大家都不喜歡看公式，我們直接以範例解釋最清楚！
score(D, Q)
首先講解 score(D, Q) 的意思， score(D, Q)代表 1 個字串 Q 與文件 D 的之間的相關聯程度分數，分數越高，代表文字 Q 與文件 D 相關聯程度越高。
我們可以想像 Q 是我們在搜尋引擎輸入的一段文字，例如 python tutorial, 而文件 D 代表 1 個網頁，所以當搜尋引擎找到多個網頁結果時，會有 n 個文件 D, 每個文件我們都需要算 1 次 BM25 得到關聯分數，最後再按照分數由高到低排序，這個排序又稱為 ranking 。
從 Q 到 qi
前文提到 Q 代表要查詢的字串，而 Q 字串會由多個單詞組成，這些單字代號為 q1, q2, q3… 以此類推。
同樣舉查詢搜尋字串 python tutorial 為例：
Q: python tutorial
q1: python
q2: tutorial
p.s. 1 個字串的切分方式與 BM25 無關，是由斷詞器(tokenizer)所決定
所以 score(D, Q) 是藉由將字串 Q 拆成多個單詞之後，分別針對每個詞算出 IDF 值並乘以公式後半段(如下圖)的值之後，再將所有分數加總。
IDF 怎麼算？
IDF 公式有幾個代號，其意思如下：
- N 代表文件總數，假設資料庫裡面有 1,000 筆資料，那 N 就是 1,000
- n(qi) 代表有多少文件包含單詞 qi, 假設單詞 q1 只在 N 筆文件裡出現 5 次，那 n(q1) 就是 5
- ln 代表 10 為基底的 log()
以下舉 3 個文件為例，並算出單詞 python 的 IDF:
D1: "I love new york"
D2: "I love python"
D3: "I don't like Java"
上述 N 為 3 而且 python 只在 D2 出現，因此 n(python) 為 1, 代入 IDF 公式之後，其值為 0.43:
IDF(python)
= log((3 - 1 + 0.5) / (1 + 0.5) + 1)
= 0.43
IDF 的數學意義是衡量 1 個詞的代表性（或者參考價值），如果 1 個詞在每個文件都出現，它的值就會越低，因為它不具代表性（沒有參考價值 ），無法幫助我們判斷 1 個詞與文件 D 之間的相關性，如果 1 個詞只有少數文件才出現，它的值越高，代表它可以幫助我們判斷相關性，譬如 I 在 3 個文件都有出現，它的 IDF 值為 0.06, 因此在算 BM25 時，如果使用者輸入 I python 作為查詢字串， I 在 BM25 分數的貢獻就會很低。
下圖模擬 N 等於 1,000,000 時， n(qi) 從 1 個文件出現到 N 個文件都有出現的 IDF 值的變化，可以看到越多檔案含有某個詞，某個詞的 IDF 將會越來越低，甚至最後趨近於 0:
BM25 公式的後半段
BM25 公式的前半段解釋完，剩下就是後半段了！
後半段公式如下：
同樣有多個代號需要了解它的意思：
- f(qi, D) 代表單詞 qi 在文件 D 中的出現次數，譬如 python 在文件 D 中出現 3 次，那 f(python, D) 就是 3
- |D| 代表文件 D 的長度，假設文件 D 的內容為
I love python, 那它以單詞為單位的長度為 3 - avgdl 代表所有文件的平均長度
- k1, b 是自由參數，是為了最佳化(optimization)而設計的參數，通常 k1 會在 1.2 - 2.0 之間， b 則是介於 0 - 1 之間，通常預設為 0.75
我們可以先不管 k1, b 都將它設定為 0 。
如此一來，公式只剩下 f(qi, D) / f(qi, D) ，不管怎麼算都是 1 ，就代表單詞 qi 在文件 D 裡出現幾次都不重要！
所以我們得到 k1 的數學意義， k1 調高代表 1 個詞的出現次數相對重要，調低代表詞出現的次數比較不重要。
而 f(qi, D) * (k1 + 1) / (f(qi, D) + k1) 所帶來的效果是會限制最終的值在 0 與 k1 + 1 之間，下圖是模擬 k1 為 1.2 而且 f(qi, D) 值為 0 - 100 的變化圖表，可以看到 f(qi, D) * (k1 + 1) / (f(qi, D) + k1) 公式的計算結果，其值被限制在 0 與 k1 + 1 之間：
我們可以把 k1 設定為 1.2 之後，再來看看 b 的效果。
b 在 BM25 的公式中，可以看到它會對 |D| / avgdl 有影響，假設將 b 設定為 1, 可以看到公式只剩下 |D| / avgdl ，其數學意思只剩下文件長度如果大於平均文件長度，除法的結果會大於 1, 代表它會進一步放大 k1 的效果；如果文件長度小於平均長度，除法的結果會小於 1, 代表它會減少 k1 的效果。
也就是說， b 其實是代表文件長度的影響程度， b 為 0 代表文件長度沒有影響， b 為 1 代表要完全將文件長度作為影響的參數。
簡而言之，數學意義上 k1 是決定單詞出現次數到底重不重要的參數，而 b 則是決定文件長度到底重不重要的參數。
全部結合起來算一遍
以下有 3 個文件：
D1: apple apple banana orange
D2: apple apple banana strawberry
D3: banana orange strawberry
我們會得到：
- N = 3
- 平均文件長度 avgdl = (4 + 4 + 3) / 3 = 3.67
當使用者輸入 Q apple banana 時，分別計算 apple 與 banana 的 IDF 會得到：
IDF(apple)
= log((3 - 2 + 0.5) / (2 + 0.5) + 1)
= 0.2
IDF(banana)
= log((3 - 3 + 0.5) / (3 + 0.5) + 1)
= 0.06
設定 k1 = 1.2 與 b = 0.75 時，文件 1 的 BM25 分數為 0.33 ：
score(D1, Q)
= (
IDF(apple) *
(2 * 2.2) / (2 + 1.2 * (1 - 0.75 + 0.75 * 4 / 3.67))
) + (
IDF(banana) *
(1 * 2.2) / (1 + 1.2 * (1 - 0.75 + 0.75 * 4 / 3.67))
)
= (
0.2 * (2 * 2.2) / (2 + 1.2 * (1 - 0.75 + 0.75 * 4 / 3.67))
) + (
0.06 * (1 * 2.2) / (1 + 1.2 * (1 - 0.75 + 0.75 * 4 / 3.67))
)
= 0.27 + 0.06
= 0.33
至於 D2, D3 的 BM25 則以此類推。
總結
數學其實不難，只是我們經常被公式以及符號給迷惑，變成不懂數學意涵而只會套用公式的人，如果能夠一步一步拆解數學公式，你會發現數學公式其實很有趣！
以上！
Enjoy!
References
Practical BM25 - Part 3: Considerations for Picking b and k1 in Elasticsearch
FOLLOW US
