BM25下一代Lucene相关性算法
本文翻译自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相关性算法代替了之前的TF*IDF相关性算法，切换到BM25之后，基于Lucene的Solr 和 Elasticsearch应用程序会获得怎样的提升？本文主要内容包括：介绍最初的TF*IDF算法及其过程；BM25算法相较TF*IDF算法的优势。
BM25 和 TF*IDF相关性算法是Lucene排序的核心算法，它们包含了Lucene所称的“field weight”。字段权重计算匹配文本与搜索词的匹配程度。
Lucene经典相关性算法：什么是TF*IDF
TF*IDF是近似用户如何评价文本匹配相关性的粗略方法。TF * IDF相似度计算相当直观，依赖算分公式名称中嵌入的两个主要因素，倾向于对应于人类的思维如何评估搜索相关性：
- tf(Term Frequency):词频，"dog"这个词在一篇文档中出现了几次；
- idf(Inverse Document Frequency):逆向文档频率；文档频率(Document Frequency)描述一个词出现在多少个文档中。逆向文档频率用于描述词的特殊性，"dog"非常罕见（只出现在一个文档中），或者比较常见（几乎出现在所有文档中）。
换句话说，TF*IDF度量给定文本中一个词的相对集中度。如果"dog"在一篇文档中很常见，但在其他文档中比较少见，那么它的得分就会很高。这篇文档应该被认为是与搜索词"dog"强相关的。如果"dog"只在文档中出现一次，但在其他文档多次出现，其得分将相对较低。
此外，文本的长度也是TF*IDF关注的因素之一。 在500页的书中出现两次的"dog"几乎没有说这本书是关于"dog"的。 然而，如果在一篇只有100个字的文档中出现了两次"dog",这个文档就跟"dog"强相关了。 因此，引入了一个额外的偏差，称为"fieldNorms"。这个偏差，认为搜索词在短文档中贡献度更大，搜索词在短文档中更“集中”，因此短文档更可能是关于搜索词的，应该得分更高。
Lucene经典相关性算法：TF*IDF举例
通过不断的实验，信息检索领域（搜索的学术方面）已经认识到，原始的TF*IDF计算值不完全对应于用户直觉相关性。如果一个文档中提到了6次"dog",其相关性就是提到3次"dog"文档的两倍吗？并不是，确实提到6次的文档更相关，但是不是2倍的关系。同理IDF也是，不能说出现在500个文档里的词比出现在1000个文档里的词，具有2倍的特殊性。
作为替代，修改后的TF*IDF中TF,IDF和field length不被直接使用，在Lucene的算分公式中使用sqrt(TF)代替TF。这样相关性不会根据TF的比例线性增长。
| Raw TF | TF |
|---|---|
| 1 | 1.0 |
| 2 | 1.414 |
| 4 | 2.0 |
| 8 | 2.828 |
| 16 | 4.0 |
使用sqrt(TF)之后，拥有16个搜索词的相关性大约是拥有4个搜索词的两倍。
类似的，我们并不认为中出现在10个文档的词的特殊性是出现在100个文档中的词的10倍，作为替代，IDF分数计算为：
log ( numDocs / (docFreq + 1)) + 1
译者注：log方法调用的是Math.log()方法，实际上是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 |
假设numDocs=1000，则有：
| Raw DF | IDF Score |
|---|---|
| 1 | 7.214 |
| 2 | 6.809 |
| 4 | 6.298 |
| 64 | 3.733 |
| 128 | 3.048 |
| 256 | 2.359 |
那么文件长度的影响是如何计算的？这是基于另一个简单的公式计算:
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的文档中相关性的十分之一。基于我们的直觉，这会产生某种意义：如果只匹配一个文档中的唯一字词，那么该文档绝对是关于该词的！在长度为128的文档中，该词只是其中的一个，不一定能代表该文档的全部内容。
Lucene经典相关性算法
IDF score * TF score * fieldNorms
或者
(log(numDocs / (docFreq + 1)) + 1)* sqrt(tf) * (1/sqrt(length))
注意事项：
- numDocs实际上是maxDocs，它包含被删除的文档数
- fieldNorms被计算并存储为8位浮点数。精度很差，会造成各种有趣的问题！
BM25(Best Match 25)相关性算法
BM25于1994年发布，这是调整相关性计算的第25次迭代。BM25根源在概率信息检索。 概率信息检索本身就是一个引人入胜的领域。基本上，它将相关性视为概率问题。 根据概率信息检索，相关性分数应该反映用户将考虑结果相关性的概率。
BM25’s Take on IDF
首先，让我们把IDF的计算放在一边。 在图上，BM25的IDF看起来非常类似于经典的Lucene IDF。 有所不同的唯一的原因是它是从概率信息检索推导出来。Lucene修改了BM25的常规IDF，这是因为BM25的IDF有可能对拥有非常高的文件频率的搜索词给予负分。所以在Lucene的BM25中解决了这个问题，将值加1，这使得无法计算负值。 最终的结果是一个与Lucene当前的IDF曲线非常相似的IDF，如下图所示：
image
所以对于IDF来说，没有太多的变化。在BM25相似度计算时，不需要改变对IDF的认识。如果你想了解，IDF是如何从概率论中推导出来的（这篇文章的范围之外的话），这将会更加有趣。
BM25’s Take on TF
相比传统的TF*IDF相关性算法，在BM25中词频的影响降低。词频的影响一直在增加，但渐渐地逼近一个值。不考虑文件长度情况下，词频遵循公式：
((k + 1) * tf) / (k + tf)
image
正如图中所示，MB25中词频的曲线只会无限的逼近(k+1)，这里的k=1.2，更高的词频意味着更大的相关性，但是很快就会趋于饱和，收益递减。而经典的Lucene 词频相关性只会一直增加，没有饱和点。
这个k值是多少呢？对于BM25来说，k通常设为1.2，不去改变。改变k虽然可以是一个有用的调整方法来修改词频的影响，修改k使得渐近线有明显的移动。但是，更大的k会导致词频相关性需要更长的时间达到饱和点。通过扩展饱和点，可以扩展更高词频和更低词频的文档之间的相关性差异！
BM25如何使用文档长度？
上面的词频相关性进一步受到高于还是低于文档平均长度的影响。那么文档长度是如何影响词频相关性的呢？从之前的词频公式出发，引入两个变量：一个常数b和一个长度值L。取上面的公式并在分母中加上（1.0 - b + b * L）作为k的倍数。
((k + 1) * tf) / (k * (1.0 - b + b * L) + tf)
这里L是文档相对于平均文档长度的长度。如果要评分的文档是平均文档长度的两倍，那么L是2。如果得分的文档是平均文档长度的十分之一，那么L是0.1。 因此，L实际上表示为|d|/avgDl，此文档长度除以平均文档长度。
image
正如在图表中看到的，不同L值的最终结果是较短的文档更快地接近渐近线。 他们几乎马上饱和到最大的TF分数。这是有道理的，简短的文件有较少的词。 这些简短文档中的匹配越多，就越能确定对相关性的信心，所以这个数字上升得更快。 另一方面，一本漫长的书，需要更多的匹配来达到我们可以感到自信的地步。 所以达到“最大TF分数”需要更长的时间。
常数b可以精确地调整L值对得分的影响程度。注意在上面的公式中，b=0时完全消除了L的影响，更大的b值增加了文档长度对评分的影响。
MB25相关性算法
IDF * ((k + 1) * tf) / (k * (1.0 - b + b * (|d|/avgDl)) + tf)
译者注：IDF是根据概率信息检索获得，文章中并没有给出明确的公式
BM25是否适合所有搜索评分
我对BM25印象非常深刻。 我在O'Reilly图书馆项目中使用它来搜索书籍。这里包含了很多的有意义的思考！词频饱和度对于相关性很有意义，调整field length的影响也是如此。虽然对于包含长度的文章文本是有意义的，但并不是搜索的所有内容都是博客文章或维基百科页面，相关性需要根据比较的事物的类型而改变。例如，标题域有其特有的相关性倾向（标题域可以确定文章的主题内容，因此标题中的词，不能使用相同的方法计算相关性）。BM25是核心文档搜索问题的巨大改进。但是围绕数字边缘，图像和其他搜索实体，BM并不一定适用。
随着BM25成为Lucene默认相关性算法，我们将直接看到当理论遇到实践时会发生什么。 相关性从来就不是一个常数，而是一种用户体验。现实世界可以有很大的不同，文档不仅仅是文档，还包括餐馆，产品，新闻文章，推文，医生办公室等等。也许对于你的“相似性”来说，正确的答案就是总是在朋友们的推特上发布推文，而这些推特也是有着类似的兴趣。对于文本相似性，其更重要的是用户找到的需要的内容。换句话说，搜索和用户体验一样重要。这就是为什么我们对Quepid帮助理解用户对搜索的期望感到兴奋！
无论如何，我对BM25的可能性，感到非常兴奋。它在Lucene的基准相关性功能中打开了大门，并将为Solr和Elasticsearch功能打开大量门户！如果您想了解BM25或其他相关解决方案是否适合您的应用，请联系我们！
注：能力一般，水平有限，如有不当之处，请批评指正，定当虚心接受！
