工程

BM25 实用详解 - 第 2 部分：BM25 算法及其变量

作者
Shane Connelly

BM25 实用详解系列分三部分讲解相似度排序（相关性），本文是第二部分。如果您刚刚加入，不妨先查看第 1 部分：分片对 Elasticsearch 中的相关性评分有怎样的影响。

BM25 算法

我会尽量从数学角度带大家深入探究 BM25 算法，仅在绝对必要的情况下才会进行相关解释，但在这个部分中，我们将介绍 BM25 公式的结构，方便您深入了解每一项的含义。我们先来看看下面这个公式，为方便大家理解，我将逐一介绍公式中的每个参数：

bm25_equation.png

我们可以看到一些常见的参数，比如 qi、IDF(qi)、f(qi,D)、k1、b，以及一些关于字段长度的参数。各项参数的含义如下：

  1. qi 是第 i 个查询项。

    例如，如果我搜索“shane”，只有 1 个查询项，所以 q0 是“shane”。如果我用英语搜索“shane connelly”，Elasticsearch 看到空格会将这个搜索内容切分为 2 个项：q0 将为“shane”，q1 将为“connelly”。我们需要将这些查询项插入到等式的其他位中，并对其全部求和。
  2. IDF(gi) 是第 i 个查询项的逆文档频率。

    如果您以前使用过 TF/IDF，可能对 IDF 的概念会比较熟悉。如果没用过，也不用担心！ （如果用过，请注意，TF/IDF 中的 IDF 公式与 BM25 中的 IDF 公式有所不同。） 我们公式中的 IDF 部分衡量的是某个项在所有文档中出现的频率，并“惩罚”常见的项。Lucene/BM25 用于该部分的实际公式为：

    idf_equation.png
    其中，docCount 是分片（如果您使用的是 search_type=dfs_query_then_fetch，则跨分片）中具有该字段值的文档总数，f(qi) 是包含第 i 个查询项的文档数。在我们的示例中，“shane”在所有 4 个文档中均有出现，因此对于“shane”项，我们最终得到的 IDF(“shane”) 为：

    idf_shane.png
    然而，只有 2 个文档中出现了“connelly”，因此我们得到的 IDF(“connelly”) 为：

    idf_connelly.png
    由此可以看出，包含这些稀有项的查询（在我们这 4 个文档的语料库中，“connelly”比“shane”更稀有）具有更高的乘数，因此它们对最终分数的贡献更大。直观来讲就是：“the”这个词很可能几乎每个英语文档都有，因此，当用户搜索类似“the elephant”这样的内容时，“elephant”可能比“the”（几乎所有文档中都有）这个词更重要，我们希望“elephant”对分数的贡献更大。
  3. 我们看到，fieldLen/avgFieldLen 表示字段的长度除以分母中的平均字段长度。

    我们可以把它看作是某个文档相对于平均文档长度的长度。 如果某个文档的长度比平均值长，则分母会变大（分数降低）；如果比平均值短，则分母就会变小（分数增加）。请注意，Elasticsearch 中字段长度的实现基于项数（而不是字符长度等其他因素）。这与原始 BM25 论文中所描述的完全相同，不过，如果您需要的话，我们确实有一个特殊的标志 (discount_overlaps) 来专门处理同义词。 可以这样想：文档中的项越多（至少是与查询不匹配的项），文档的分数就越低。同样，直观来讲就是：如果一份文档有 300 页，只提到我的名字一次，那么它与我的关系就不太可能像一条同样提到我一次的短推文那么大。
  4. 我们看到分母中有一个变量 b，它需要乘以我们刚才讨论过的字段长度与平均字段长度的比值。b 越大，文档长度与平均长度之比的影响就越大。为了弄明白这一点，您可以想象，如果将 b 设为 0，那么长度比的影响将完全无效，而且文档的长度将与分数无关。在 Elasticsearch 中，b 的默认值为 0.75。
  5. 最后，还有两个参数会影响分数，并且分子和分母中都出现了：k1 和 f(qi,D)。由于分子和分母中都有，单看公式很难看出它们起什么作用，我们不妨单独进行讲解。
    1. f(qi,D) 是指“第 i 个查询项在文档 D 中出现了多少次？” 在所有这些文档中，f(“shane”,D) 都为 1，但f(“connelly”,D) 不同：对于文档 3 和 4，它为 1，但对于文档 1 和 2，它为 0。如果有第 5 个文档，且内容包含“shane shane”文本，则它的 f(“shane”,D) 为 2。我们可以看到 分子和分母中都有 f(qi,D)，而且有一个特殊的因数“k1”，我们接下来会讲到。可以这样看 f(qi,D)：一个文档中查询词出现的次数越多，其分数就越高。直观来讲就是：一份多次出现我们名字的文档比一份只出现一次的文档更有可能与我们相关。
    2. k1 是一个有助于确定项频率饱和度特性的变量。也就是说，它限制了单个查询项对给定文档分数的影响程度。它通过接近渐近线来实现这一点。BM25 与 TF/IDF 的对比如下图所示：
      term_frequency_saturation.png
      k1 值越高/越低，表示“BM25 的 tf()”曲线的斜率发生变化。这就改变了“出现额外次数的项增加额外分数”的方式。 k1 的一种解释是，对于平均长度的文档，它是项频率的值，给出的分数是所考虑项的最大分数的一半。tf 对分数的影响曲线在 tf() ≤ k1 时增长很快，而在 tf() > k1 时越来越慢。

      继续看我们的示例，我们通过 k1 控制着以下问题的答案：“向文档中添加第二个“shane”对分数的贡献比第一个多多少？添加第三个“shane”对分数的贡献比第二个又多多少？” k1 越高意味着每个项的分数可以继续上升，如果该项的实例越多，上升也相对越多。k1 的值为 0 意味着除 IDF(qi) 之外的所有内容都会抵消。在 Elasticsearch 中，k1 的默认值为 1.2。

运用新知识重新审视我们的搜索结果

我们将删除 people 索引，然后仅用 1 个分片重新创建，这样我们就不必使用 search_type=dfs_query_then_fetch 了。我们将通过设置三个索引来检验知识的掌握情况：第一个索引的 k1 值为 0，b 为 0.5；第二个索引 (people2) 的 b 为 0，k1 为 10；第三个索引 (people3) 的 b 为 1，k1 为 5。 

DELETE people
PUT people
{
  "settings": {
    "number_of_shards": 1,
    "index" : {
        "similarity" : {
          "default" : {
            "type" : "BM25",
            "b": 0.5,
            "k1": 0
          }
        }
    }
  }
}
PUT people2
{
  "settings": {
    "number_of_shards": 1,
    "index" : {
        "similarity" : {
          "default" : {
            "type" : "BM25",
            "b": 0,
            "k1": 10
          }
        }
    }
  }
}
PUT people3
{
  "settings": {
    "number_of_shards": 1,
    "index" : {
        "similarity" : {
          "default" : {
            "type" : "BM25",
            "b": 1,
            "k1": 5
          }
        }
    }
  }
}

现在，我们将向这三个索引添加一些文档： 

POST people/_doc/_bulk
{ "index": { "_id": "1" } }
{ "title": "Shane" }
{ "index": { "_id": "2" } }
{ "title": "Shane C" }
{ "index": { "_id": "3" } }
{ "title": "Shane P Connelly" }
{ "index": { "_id": "4" } }
{ "title": "Shane Connelly" }
{ "index": { "_id": "5" } }
{ "title": "Shane Shane Connelly Connelly" }
{ "index": { "_id": "6" } }
{ "title": "Shane Shane Shane Connelly Connelly Connelly" }
POST people2/_doc/_bulk
{ "index": { "_id": "1" } }
{ "title": "Shane" }
{ "index": { "_id": "2" } }
{ "title": "Shane C" }
{ "index": { "_id": "3" } }
{ "title": "Shane P Connelly" }
{ "index": { "_id": "4" } }
{ "title": "Shane Connelly" }
{ "index": { "_id": "5" } }
{ "title": "Shane Shane Connelly Connelly" }
{ "index": { "_id": "6" } }
{ "title": "Shane Shane Shane Connelly Connelly Connelly" }
POST people3/_doc/_bulk
{ "index": { "_id": "1" } }
{ "title": "Shane" }
{ "index": { "_id": "2" } }
{ "title": "Shane C" }
{ "index": { "_id": "3" } }
{ "title": "Shane P Connelly" }
{ "index": { "_id": "4" } }
{ "title": "Shane Connelly" }
{ "index": { "_id": "5" } }
{ "title": "Shane Shane Connelly Connelly" }
{ "index": { "_id": "6" } }
{ "title": "Shane Shane Shane Connelly Connelly Connelly" }

接下来，如果执行以下操作： 

GET /cn/people/_search
{
  "query": {
    "match": {
      "title": "shane"
    }
  }
}

我们可以在 people 中看到，所有文档的分数都是 0.074107975。这与我们将 k1 设置为 0 的理解一致：只有搜索项的 IDF 对分数有影响！

下面我们来看一下 people2，其中 b = 0，k1 = 10： 

GET /cn/people2/_search
{
  "query": {
    "match": {
      "title": "shane"
    }
  }
}

从这次搜索的结果中可以得出两点结论。

首先，我们可以看到分数是完全按照“shane”出现的次数排序的。文档 1、2、3 和 4 中都出现了一次“shane”，因此分数都为 0.074107975。文档 5 中出现了两次“shane”，所以 f(“shane”,D5) = 2，分数要高一点 (0.13586462)；文档 6 的 f(“shane”,D6) = 3，分数自然更高 (0.18812023)。上述结果与我们在 people2 中将 b 设为 0 的直觉不谋而合：长度（或文档中项的总数）对分数没有影响；只有匹配项的计数和相关性会影响分数。

第二点要注意的是，这些分数之间的差值是非线性的，尽管在这 6 个文档看起来确实非常接近线性。

  • 我们的搜索词没有出现和第一次出现之间的分数差为 0.074107975
  • 我们的搜索词第二次出现和第一次出现之间的分数差为：0.13586462 - 0.074107975 = 0.061756645
  • 我们的搜索词第三次出现和第二次出现之间的分数差为：0.18812023 - 0.13586462 = 0.05225561

0.074107975 与 0.061756645 非常接近，后者又非常接近 0.05225561，但下降趋势明显。它们的差值看起来几乎是线性的是因为 k1 数值较大。我们至少可以看到，分数并没有随着出现次数的增加而呈线性增加 — 如果呈线性增加的话，每增加一项的差值应该是相同的。我们运行完 people3 再回头讨论这个问题。

现在，我们来看一下 people3，其中 k1 = 5，b = 1：

GET /cn/people3/_search
{
  "query": {
    "match": {
      "title": "shane"
    }
  }
}

我们得到了以下结果： 

"hits": [
      {
        "_index": "people3",
        "_type": "_doc",
        "_id": "1",
        "_score": 0.16674294,
        "_source": {
          "title": "Shane"
        }
      },
      {
        "_index": "people3",
        "_type": "_doc",
        "_id": "6",
        "_score": 0.10261105,
        "_source": {
          "title": "Shane Shane Shane Connelly Connelly Connelly"
        }
      },
      {
        "_index": "people3",
        "_type": "_doc",
        "_id": "2",
        "_score": 0.102611035,
        "_source": {
          "title": "Shane C"
        }
      },
      {
        "_index": "people3",
        "_type": "_doc",
        "_id": "4",
        "_score": 0.102611035,
        "_source": {
          "title": "Shane Connelly"
        }
      },
      {
        "_index": "people3",
        "_type": "_doc",
        "_id": "5",
        "_score": 0.102611035,
        "_source": {
          "title": "Shane Shane Connelly Connelly"
        }
      },
      {
        "_index": "people3",
        "_type": "_doc",
        "_id": "3",
        "_score": 0.074107975,
        "_source": {
          "title": "Shane P Connelly"
        }
      }
    ]

我们可以在 people3 中看到，现在匹配项（“shane”）与非匹配项的比率是唯一影响相对得分的因素。文档 3 中有 3 个词，但只有 1 个词匹配，分数比文档 2、4、5 和 6 都要低，后面这几个文档都恰好有一半的词匹配，但这些文档的分数没有文档 1 的分数高，因为文档 1 实现了完全匹配。

同样，我们可以注意到，在 people2 和 people3 中，得分最高的文档和得分较低的文档之间存在“很大”的差异。这要（再次）归功于 k1 的数值较大。作为附加练习，请尝试删除 people2/people3，然后将它们重新设置为 k1 = 0.01 这样的值，您会发现设置的值越小，文档之间的分差就越小。当 b = 0 且 k1 = 0.01 时：

  • 我们的搜索词没有出现和第一次出现之间的分数差为 0.074107975
  • 我们的搜索词第二次出现和第一次出现之间的分数差为：0.074476674 - 0.074107975 = 0.000368699
  • 我们的搜索词第三次出现和第二次出现之间的分数差为：0.07460038 - 0.074476674 = 0.000123706

因此，当 k1 = 0.01 时，我们可以看到每多出现一次对分数的影响比 k1 = 5 或 k1 = 10 时下降得更快。第 4 次出现增加的分数会比第 3 次增加的分数少的多，以此类推。换句话说，k1 值越小，项分数越快达到饱和。正如我们所料！

希望本文有助于您了解这些参数对各种文档集的作用。如果上述内容已掌握，接下来我们将介绍如何选择合适的 b 和 k1，以及 Elasticsearch 如何提供工具来理解分数并迭代您的方法。

继续阅读本系列文章：第 3 部分：在 Elasticsearch 中选取 b 和 k1 的注意事项