用白話文談數學公式 - BM25 (Best Matching 25)

Posted on  Apr 29, 2024  in  數學概念  by  Amo Chen  ‐ 5 min read

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 公式如下所示:

bm25.svg

上述公式中的 IDF(qi) 公式如下, IDF 全名為 Inverse Document Frequency

bm25_idf.svg

相信大家都不喜歡看公式,我們直接以範例解釋最清楚!

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 值並乘以公式後半段(如下圖)的值之後,再將所有分數加總。

bm25_tail_part.png

IDF 怎麼算?

bm25_idf.svg

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:

idf-sim.png

BM25 公式的後半段

BM25 公式的前半段解釋完,剩下就是後半段了!

後半段公式如下:

bm25_tail_part.png

同樣有多個代號需要了解它的意思:

  • 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 之間:

bm25-k1.png

我們可以把 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.2b = 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

Okapi BM25

Practical BM25 - Part 3: Considerations for Picking b and k1 in Elasticsearch

對抗久坐職業傷害

研究指出每天增加 2 小時坐著的時間,會增加大腸癌、心臟疾病、肺癌的風險,也造成肩頸、腰背疼痛等常見問題。

然而對抗這些問題,卻只需要工作時定期休息跟伸展身體即可!

你想輕鬆改變現狀嗎?試試看我們的 PomodoRoll 番茄鐘吧! PomodoRoll 番茄鐘會根據你所設定的專注時間,定期建議你 1 項辦公族適用的伸展運動,幫助你打敗久坐所帶來的傷害!

贊助我們的創作

看完這篇文章了嗎? 休息一下,喝杯咖啡吧!

如果你覺得 MyApollo 有讓你獲得實用的資訊,希望能看到更多的技術分享,邀請你贊助我們一杯咖啡,讓我們有更多的動力與精力繼續提供高品質的文章,感謝你的支持!