本文翻譯自Doug Turnbull的《BM25 The Next Generation of Lucene Relevance》
原文地址：http://opensourceconnections.com/blog/2015/10/16/bm25-the-next-generation-of-lucene-relevation/
前言
Lucene自6.0起使用BM25相關(guān)性算法代替了之前的TF*IDF相關(guān)性算法避诽，切換到BM25之后自娩，基于Lucene的Solr 和 Elasticsearch應(yīng)用程序會(huì)獲得怎樣的提升柠横？本文主要內(nèi)容包括：介紹最初的TF*IDF算法及其過程蛤育；BM25算法相較TF*IDF算法的優(yōu)勢壁熄。
BM25 和 TF*IDF相關(guān)性算法是Lucene排序的核心算法耻台，它們包含了Lucene所稱的“field weight”。字段權(quán)重計(jì)算匹配文本與搜索詞的匹配程度紫皇。
Lucene經(jīng)典相關(guān)性算法：什么是TF*IDF
TF*IDF是近似用戶如何評價(jià)文本匹配相關(guān)性的粗略方法慰安。TF * IDF相似度計(jì)算相當(dāng)直觀，依賴算分公式名稱中嵌入的兩個(gè)主要因素聪铺，傾向于對應(yīng)于人類的思維如何評估搜索相關(guān)性：
- tf(Term Frequency):詞頻化焕，"dog"這個(gè)詞在一篇文檔中出現(xiàn)了幾次；
- idf(Inverse Document Frequency):逆向文檔頻率铃剔；文檔頻率(Document Frequency)描述一個(gè)詞出現(xiàn)在多少個(gè)文檔中撒桨。逆向文檔頻率用于描述詞的特殊性，"dog"非常罕見（只出現(xiàn)在一個(gè)文檔中）番宁，或者比較常見（幾乎出現(xiàn)在所有文檔中）元莫。
換句話說赖阻，TF*IDF度量給定文本中一個(gè)詞的相對集中度蝶押。如果"dog"在一篇文檔中很常見，但在其他文檔中比較少見火欧，那么它的得分就會(huì)很高棋电。這篇文檔應(yīng)該被認(rèn)為是與搜索詞"dog"強(qiáng)相關(guān)的。如果"dog"只在文檔中出現(xiàn)一次苇侵，但在其他文檔多次出現(xiàn)赶盔，其得分將相對較低。
此外榆浓，文本的長度也是TF*IDF關(guān)注的因素之一于未。 在500頁的書中出現(xiàn)兩次的"dog"幾乎沒有說這本書是關(guān)于"dog"的。 然而陡鹃，如果在一篇只有100個(gè)字的文檔中出現(xiàn)了兩次"dog",這個(gè)文檔就跟"dog"強(qiáng)相關(guān)了烘浦。 因此，引入了一個(gè)額外的偏差萍鲸，稱為"fieldNorms"闷叉。這個(gè)偏差，認(rèn)為搜索詞在短文檔中貢獻(xiàn)度更大脊阴，搜索詞在短文檔中更“集中”握侧，因此短文檔更可能是關(guān)于搜索詞的蚯瞧，應(yīng)該得分更高。
Lucene經(jīng)典相關(guān)性算法：TF*IDF舉例
通過不斷的實(shí)驗(yàn)品擎，信息檢索領(lǐng)域（搜索的學(xué)術(shù)方面）已經(jīng)認(rèn)識到埋合，原始的TF*IDF計(jì)算值不完全對應(yīng)于用戶直覺相關(guān)性。如果一個(gè)文檔中提到了6次"dog",其相關(guān)性就是提到3次"dog"文檔的兩倍嗎萄传？并不是饥悴，確實(shí)提到6次的文檔更相關(guān)，但是不是2倍的關(guān)系盲再。同理IDF也是西设，不能說出現(xiàn)在500個(gè)文檔里的詞比出現(xiàn)在1000個(gè)文檔里的詞，具有2倍的特殊性答朋。
作為替代贷揽，修改后的TF*IDF中TF,IDF和field length不被直接使用，在Lucene的算分公式中使用sqrt(TF)代替TF梦碗。這樣相關(guān)性不會(huì)根據(jù)TF的比例線性增長禽绪。
| Raw TF | TF |
|---|---|
| 1 | 1.0 |
| 2 | 1.414 |
| 4 | 2.0 |
| 8 | 2.828 |
| 16 | 4.0 |
使用sqrt(TF)之后，擁有16個(gè)搜索詞的相關(guān)性大約是擁有4個(gè)搜索詞的兩倍洪规。
類似的印屁，我們并不認(rèn)為中出現(xiàn)在10個(gè)文檔的詞的特殊性是出現(xiàn)在100個(gè)文檔中的詞的10倍，作為替代斩例，IDF分?jǐn)?shù)計(jì)算為：
log ( numDocs / (docFreq + 1)) + 1
譯者注：log方法調(diào)用的是Math.log()方法雄人，實(shí)際上是ln。該公式在Lucene6.0之前的版本使用念赶，6.0之后的版本使用以下公式：
log((numDocs + 1) / (docFreq + 1))+1
| Raw DF | IDF Score |
|---|---|
| 1 | 7.214 |
| 2 | 6.809 |
| 4 | 6.298 |
| 64 | 3.733 |
| 128 | 3.048 |
| 256 | 2.359 |
假設(shè)numDocs=1000础钠，則有：
| Raw DF | IDF Score |
|---|---|
| 1 | 7.214 |
| 2 | 6.809 |
| 4 | 6.298 |
| 64 | 3.733 |
| 128 | 3.048 |
| 256 | 2.359 |
那么文件長度的影響是如何計(jì)算的？這是基于另一個(gè)簡單的公式計(jì)算:
1 / sqrt(length)
| Raw Length | Field Norm Score |
|---|---|
| 1 | 1.0 |
| 2 | 0.707 |
| 4 | 0.5 |
| 64 | 0.125 |
| 128 | 0.088 |
| 256 | 0.0625 |
因此叉谜，長度為128的文檔大約是長度為1的文檔中相關(guān)性的十分之一旗吁。基于我們的直覺停局，這會(huì)產(chǎn)生某種意義：如果只匹配一個(gè)文檔中的唯一字詞很钓，那么該文檔絕對是關(guān)于該詞的！在長度為128的文檔中董栽，該詞只是其中的一個(gè)码倦，不一定能代表該文檔的全部內(nèi)容。
Lucene經(jīng)典相關(guān)性算法
IDF score * TF score * fieldNorms
或者
(log(numDocs / (docFreq + 1)) + 1)* sqrt(tf) * (1/sqrt(length))
注意事項(xiàng)：
- numDocs實(shí)際上是maxDocs裆泳，它包含被刪除的文檔數(shù)
- fieldNorms被計(jì)算并存儲(chǔ)為8位浮點(diǎn)數(shù)叹洲。精度很差，會(huì)造成各種有趣的問題工禾！
BM25(Best Match 25)相關(guān)性算法
BM25于1994年發(fā)布运提，這是調(diào)整相關(guān)性計(jì)算的第25次迭代蝗柔。BM25根源在概率信息檢索。 概率信息檢索本身就是一個(gè)引人入勝的領(lǐng)域民泵⊙⑸ィ基本上，它將相關(guān)性視為概率問題栈妆。 根據(jù)概率信息檢索胁编，相關(guān)性分?jǐn)?shù)應(yīng)該反映用戶將考慮結(jié)果相關(guān)性的概率。
BM25’s Take on IDF
首先鳞尔，讓我們把IDF的計(jì)算放在一邊嬉橙。 在圖上，BM25的IDF看起來非常類似于經(jīng)典的Lucene IDF寥假。 有所不同的唯一的原因是它是從概率信息檢索推導(dǎo)出來市框。Lucene修改了BM25的常規(guī)IDF，這是因?yàn)锽M25的IDF有可能對擁有非常高的文件頻率的搜索詞給予負(fù)分糕韧。所以在Lucene的BM25中解決了這個(gè)問題枫振，將值加1，這使得無法計(jì)算負(fù)值萤彩。 最終的結(jié)果是一個(gè)與Lucene當(dāng)前的IDF曲線非常相似的IDF粪滤，如下圖所示：
所以對于IDF來說，沒有太多的變化雀扶。在BM25相似度計(jì)算時(shí)杖小，不需要改變對IDF的認(rèn)識。如果你想了解怕吴，IDF是如何從概率論中推導(dǎo)出來的（這篇文章的范圍之外的話）舔琅，這將會(huì)更加有趣滋将。
BM25’s Take on TF
相比傳統(tǒng)的TF*IDF相關(guān)性算法，在BM25中詞頻的影響降低戈毒。詞頻的影響一直在增加硼啤，但漸漸地逼近一個(gè)值议经。不考慮文件長度情況下，詞頻遵循公式：
((k + 1) * tf) / (k + tf)
正如圖中所示谴返，MB25中詞頻的曲線只會(huì)無限的逼近(k+1)煞肾，這里的k=1.2，更高的詞頻意味著更大的相關(guān)性嗓袱，但是很快就會(huì)趨于飽和籍救，收益遞減。而經(jīng)典的Lucene 詞頻相關(guān)性只會(huì)一直增加渠抹，沒有飽和點(diǎn)蝙昙。
這個(gè)k值是多少呢闪萄？對于BM25來說，k通常設(shè)為1.2奇颠，不去改變败去。改變k雖然可以是一個(gè)有用的調(diào)整方法來修改詞頻的影響，修改k使得漸近線有明顯的移動(dòng)烈拒。但是圆裕，更大的k會(huì)導(dǎo)致詞頻相關(guān)性需要更長的時(shí)間達(dá)到飽和點(diǎn)。通過擴(kuò)展飽和點(diǎn)荆几，可以擴(kuò)展更高詞頻和更低詞頻的文檔之間的相關(guān)性差異吓妆！
BM25如何使用文檔長度？
上面的詞頻相關(guān)性進(jìn)一步受到高于還是低于文檔平均長度的影響吨铸。那么文檔長度是如何影響詞頻相關(guān)性的呢耿战？從之前的詞頻公式出發(fā)，引入兩個(gè)變量：一個(gè)常數(shù)b和一個(gè)長度值L焊傅。取上面的公式并在分母中加上（1.0 - b + b * L）作為k的倍數(shù)剂陡。
((k + 1) * tf) / (k * (1.0 - b + b * L) + tf)
這里L(fēng)是文檔相對于平均文檔長度的長度。如果要評分的文檔是平均文檔長度的兩倍狐胎，那么L是2鸭栖。如果得分的文檔是平均文檔長度的十分之一，那么L是0.1握巢。 因此晕鹊，L實(shí)際上表示為|d|/avgDl，此文檔長度除以平均文檔長度暴浦。
正如在圖表中看到的溅话，不同L值的最終結(jié)果是較短的文檔更快地接近漸近線。 他們幾乎馬上飽和到最大的TF分?jǐn)?shù)歌焦。這是有道理的飞几，簡短的文件有較少的詞。 這些簡短文檔中的匹配越多独撇，就越能確定對相關(guān)性的信心屑墨，所以這個(gè)數(shù)字上升得更快。 另一方面纷铣，一本漫長的書卵史，需要更多的匹配來達(dá)到我們可以感到自信的地步。 所以達(dá)到“最大TF分?jǐn)?shù)”需要更長的時(shí)間搜立。
常數(shù)b可以精確地調(diào)整L值對得分的影響程度以躯。注意在上面的公式中，b=0時(shí)完全消除了L的影響啄踊，更大的b值增加了文檔長度對評分的影響忧设。
MB25相關(guān)性算法
IDF * ((k + 1) * tf) / (k * (1.0 - b + b * (|d|/avgDl)) + tf)
譯者注：IDF是根據(jù)概率信息檢索獲得色鸳，文章中并沒有給出明確的公式
BM25是否適合所有搜索評分
我對BM25印象非常深刻。 我在O'Reilly圖書館項(xiàng)目中使用它來搜索書籍见转。這里包含了很多的有意義的思考命雀！詞頻飽和度對于相關(guān)性很有意義，調(diào)整field length的影響也是如此斩箫。雖然對于包含長度的文章文本是有意義的吏砂，但并不是搜索的所有內(nèi)容都是博客文章或維基百科頁面，相關(guān)性需要根據(jù)比較的事物的類型而改變乘客。例如狐血，標(biāo)題域有其特有的相關(guān)性傾向（標(biāo)題域可以確定文章的主題內(nèi)容，因此標(biāo)題中的詞易核，不能使用相同的方法計(jì)算相關(guān)性）匈织。BM25是核心文檔搜索問題的巨大改進(jìn)。但是圍繞數(shù)字邊緣牡直，圖像和其他搜索實(shí)體缀匕，BM并不一定適用。
隨著BM25成為Lucene默認(rèn)相關(guān)性算法碰逸，我們將直接看到當(dāng)理論遇到實(shí)踐時(shí)會(huì)發(fā)生什么乡小。 相關(guān)性從來就不是一個(gè)常數(shù)，而是一種用戶體驗(yàn)《罚現(xiàn)實(shí)世界可以有很大的不同满钟，文檔不僅僅是文檔，還包括餐館胳喷，產(chǎn)品湃番，新聞文章，推文吭露，醫(yī)生辦公室等等吠撮。也許對于你的“相似性”來說，正確的答案就是總是在朋友們的推特上發(fā)布推文奴饮，而這些推特也是有著類似的興趣纬向。對于文本相似性，其更重要的是用戶找到的需要的內(nèi)容戴卜。換句話說，搜索和用戶體驗(yàn)一樣重要琢岩。這就是為什么我們對Quepid幫助理解用戶對搜索的期望感到興奮投剥！
無論如何，我對BM25的可能性担孔，感到非常興奮江锨。它在Lucene的基準(zhǔn)相關(guān)性功能中打開了大門吃警，并將為Solr和Elasticsearch功能打開大量門戶！如果您想了解BM25或其他相關(guān)解決方案是否適合您的應(yīng)用啄育，請聯(lián)系我們酌心！
注：能力一般，水平有限挑豌，如有不當(dāng)之處安券，請批評指正，定當(dāng)虛心接受氓英！
