搜索中的權重度量利器: TF-IDF和BM25
- 2019 年 10 月 6 日
- 筆記
我們在網上搜東西時，搜索引擎總是會把相關性高的內容顯示在前面，相關性低的內容顯示在後面。那麼，搜索引擎是如何計算關鍵字和內容的相關性呢？這裡介紹2種重要的權重度量方法：TF-IDF和BM25。
在進入理論探討之前，我們先舉個例子。假如，我們想找和「Lucence」相關的文章。可以想一下，那些內容里只出現過一次「Lucence」的文章，有可能是在講某種技術，順便提到了Lucence這個工具。而那些出現了兩三次「Lucence」的文章，很可能是專門討論Lucence的。通過直覺，我們可以得出判斷：關鍵字出現的次數越多，文檔與關鍵字的匹配度越高。
TF的定義
有一個專門的術語來表示關鍵字出現的次數，叫「詞頻」(Term Frequency), 簡寫為TF。TF越大，通常相關性越高。
但是，你可能會發現一個問題。 如果一篇小短文里出現了一次「Lucence」，而一部好幾百頁的書里提到兩次「Lucence」，我們不會認為那部書與Lucence相關性更高。為了消除文檔本身大小的影響，一般使用TF時會把文本長度考慮上：
TF Score ＝ 某個詞在文檔中出現的次數 ／ 文檔的長度
舉例：某文檔D，長度為200，其中「Lucence」出現了2次，「的」出現了20次，「原理」出現了3次，那麼:
TF(Lucence|D) = 2/200 = 0.01 TF(的|D) = 20/200 = 0.1 TF(原理|D) = 3/200 = 0.015
「Lucence的原理」這個短語與文檔D的相關性就是三個詞的相關性之和。
TF(Lucence的原理|D) = 0.01 + 0.1 + 0.015 = 0.125
我們發現一個問題，就是「的」這個詞佔了很大權重，而它對文檔主題的幾乎沒什麼貢獻。這種詞叫停用詞，在度量相關性時不考慮它們的詞頻。去掉這個詞後，上面的相關性變為0.025。其中「Lucence」貢獻了0.01, 「原理」貢獻了0.015。
細心的人還會發現，「原理」是個很通用的詞，而「Lucence」是個專業詞。直覺告訴我們，「Lucence」這個詞對我們的搜索比「原理」更重要。抽象一下，可以理解為 一個詞預測主題的能力越強，就越重要，權重也應該越大。反之，權重越小。
假設我們把世界上所有的文檔的總和看成一個文檔庫。如果一個詞，很少在文檔庫里出現過，那通過它就容易找到目標，它的權重也應該大。反之，如果一個詞在文檔庫中大量出現，看到它仍然不清楚在講什麼內容，它的權重就應該小。「的、地、得」這些虛詞出現的頻率太高，以至於權重設為零也不影響搜素，這也是它們成為停用詞的原因之一。
IDF的定義
假設關鍵詞w在n個文檔中出現過，那麼n越大，則w的權重越小。常用的方法叫「逆文本頻率指數」(Inverse Dcument Frequency, 縮寫為IDF)。一般的：
IDF = log(N/n)
注意: 這裡的log是指以2為底的對數,不是以10為底的對數。
N表示全部文檔數。假如世界上文檔總數位100億，"Lucence"在1萬個文檔中出現過，「原理」在2億個文檔中出現過，那麼它們的IDF值分別為：
IDF(Lucence) = log(100億/1萬) = 19.93 IDF(原理) ＝ log(100億/2億) ＝ 5.64
「Lucence」重要性相當於「原理」的3.5倍。停用詞「的」在所有的文檔里出現過，它的IDF=log(1)=0。短語與文檔的最終相關性就是TF和IDF的加權求和：
simlarity = TF1*IDF1 + TF2*IDF2 + ... + TFn*IDFn
現在可以計算出上文中提到的「Lucence的原理」與文檔D的相關性:
simlarity(Lucence的原理|D) = 0.01*19.93 + 0 + 5.64*0.015 ＝ 0.2839
其中，「Lucence」佔了70%的權重，「原理」僅佔30%的權重。
Lucence中的TF-IDF
早期的Lucence是直接把TF-IDF作為默認相似度來用的，只不過做了適當調整，它的相似度公式為:
simlarity = log(numDocs / (docFreq + 1)) * sqrt(tf) * (1/sqrt(length))
numDocs:索引中文檔數量，對應前文中的N。lucence不是(也不可能)把整個互聯網的文檔作為基數，而是把索引中的文檔總數作為基數。
- docFreq: 包含關鍵字的文檔數量，對應前文中的n。
- tf: 關鍵字在文檔中出現的次數。
- length: 文檔的長度。
上面的公式在Lucence系統里做計算時會被拆分成三個部分：
IDF Score = log(numDocs / (docFreq + 1)) TF Score = sqrt(tf) fieldNorms = 1/sqrt(length)
fieldNorms 是對文本長度的歸一化(Normalization)。所以，上面公式也可以表示成:
simlarity = IDF score * TF score * fieldNorms
BM25, 下一代的TF-IDF
新版的lucence不再把TF-IDF作為默認的相關性演算法，而是採用了BM25(BM是Best Matching的意思)。BM25是基於TF-IDF並做了改進的演算法。
BM25中的TF
傳統的TF值理論上是可以無限大的。而BM25與之不同，它在TF計算方法中增加了一個常量k，用來限制TF值的增長極限。下面是兩者的公式：
傳統 TF Score = sqrt(tf) BM25的 TF Score = ((k + 1) * tf) / (k + tf)
下面是兩種計算方法中，詞頻對TF Score影響的走勢圖。從圖中可以看到，當tf增加時，TF Score跟著增加，但是BM25的TF Score會被限制在0~k+1之間。它可以無限逼近k+1，但永遠無法觸達它。這在業務上可以理解為某一個因素的影響強度不能是無限的，而是有個最大值，這也符合我們對文本相關性邏輯的理解。 在Lucence的默認設置里，k＝1.2，使用者可以修改它。
BM25如何對待文檔長度
BM25還引入了平均文檔長度的概念，單個文檔長度對相關性的影響力與它和平均長度的比值有關係。BM25的TF公式里，除了k外，引入另外兩個參數：L和b。L是文檔長度與平均長度的比值。如果文檔長度是平均長度的2倍，則L＝2。b是一個常數，它的作用是規定L對評分的影響有多大。加了L和b的公式變為：
TF Score = ((k + 1) * tf) / (k * (1.0 - b + b * L) + tf)
下面是不同L的條件下，詞頻對TFScore影響的走勢圖：
從圖上可以看到，文檔越短，它逼近上限的速度越快，反之則越慢。這是可以理解的，對於只有幾個詞的內容，比如文章「標題」，只需要匹配很少的幾個詞，就可以確定相關性。而對於大篇幅的內容，比如一本書的內容，需要匹配很多詞才能知道它的重點是講什麼。
上文說到，參數b的作用是設定L對評分的影響有多大。如果把b設置為0，則L完全失去對評分的影響力。b的值越大，L對總評分的影響力越大。此時，相似度最終的完整公式為：
simlarity = IDF * ((k + 1) * tf) / (k * (1.0 - b + b * (|d|/avgDl)) + tf)
傳統TF-IDF vs. BM25
傳統的TF-IDF是自然語言搜索的一個基礎理論，它符合資訊理論中的熵的計算原理，雖然作者在剛提出它時並不知道與資訊熵有什麼關係，但你觀察IDF公式會發現，它與熵的公式是類似的。實際上IDF就是一個特定條件下關鍵詞概率分布的交叉熵。
BM25在傳統TF-IDF的基礎上增加了幾個可調節的參數，使得它在應用上更佳靈活和強大，具有較高的實用性。
讀者思考
為什麼BM25的TF Score計算要用 d/avgDl, 而不是用平方根、log或者其它計算方法？它背後是否有理論支援？
相關文章
