作者：Benjamin Trent

Elasticsearch：将最大内积引进 Lucene

目前，Lucene 限制 dot_product (点积)只能在标准化向量上运用。 归一化迫使一切向量起伏等于一。 虽然在许多情况下这是可以接受的，但它或许会导致某些数据集的相关性问题。 一个典型的例子是 Cohere 构建的嵌入（embeddings）。 它们的向量运用起伏来供给更多相关信息。

那么，为什么不答应点积中存在非归一化向量，从而完成最大内积呢？ 有什么大不了的？

负值和 Lucene 优化

Lucene要求分数非负，因此在析取 (disjunctive query) 查询中多匹配一个子句只能使分数更高，而不是更低。 这实际上关于动态修剪优化（例如 block-max WAND）非常重要，假如某些子句或许发生负分数，则其效率会大大下降。 此要求如何影响非标准化向量？

在归一化情况下，一切向量都在单位球面上。 这答应经过简略的缩放来处理负分数。

Elasticsearch：将最大内积引进 Lucene
图 1：二维单位球体（例如单位圆）中的两个相反的二维向量。 在这里核算点积时，最糟糕的情况是 -1 = [1, 0] * [-1, 0]。 Lucene 经过向结果加 1 来处理这一问题。

当向量坚持其大小时，或许值的规模是未知的。

Elasticsearch：将最大内积引进 Lucene
图 2：核算这些向量的点积时 [2, 2] * [-5, -5] = -20

为了答应 Lucene 将 blockMax WAND 与非标准化向量结合运用，咱们有必要缩放分数。 这是一个适当简略的处理方案。 Lucene 将运用简略的分段函数缩放非标准化向量：


1.  if (dotProduct < 0) {
2.    return 1 / (1 + -1 * dotProduct);
3.  }
4.  return dotProduct + 1;

现在，一切负分数都在 0 -1 之间，一切正分数都在 1 以上。这仍然可以保证较高的值意味着更好的匹配并消除负分数。 很简略，但这不是最后的妨碍。

三角形问题

最大内积不遵循与简略欧几里得空间相同的规矩。 三角不等式的简略假设常识被抛弃。 不直观的是，向量不再最接近其本身。 这或许会令人不安。 Lucene 的向量底层索引结构是分层可导航小世界 (HNSW)。 这是基于图的算法，它或许依赖于欧几里得空间假设。 或者在非欧几里得空间中探索图会太慢吗？

一些研讨表明，快速查找需求转换到欧几里得空间。 其他人则经历了更新向量存储以强制转换为欧几里得空间的费事。

这导致咱们停下来深入发掘一些数据。 要害问题是：HNSW 是否经过最大内积查找供给杰出的召回率和延迟？ 虽然 HNSW 最初的论文和其他已发表的研讨表明的确如此，但咱们需求进行尽职查询。

咱们进行的试验很简略。 一切的试验都是在实在数据集或略微修改的实在数据集上进行的。 这关于基准测验至关重要，因为现代神经网络创立契合特定特征的向量（请参阅本文第 7.8 节中的评论）。 咱们测量了非标准化向量的延迟（以毫秒为单位）与召回率。 将数字与具有相同测量值但采用欧几里德空间改换的数字进行比较。 在每种情况下，向量都被索引到 Lucene 的 HNSW 完成中，而且咱们测量了 1000 次查询迭代。 每个数据集考虑了三种单独的情况：按大小次序刺进的数据（从小到大）、按随机次序刺进的数据以及按相反次序刺进的数据（从大到小）。

以下是 Cohere 实在数据集的一些结果：

图 3：以下是嵌入维基百科文章的 Cohere 多语言模型的结果。 可在 HuggingFace 上找到。 前 10 万份文档已建立索引并进行了测验。
Elasticsearch：将最大内积引进 Lucene
Elasticsearch：将最大内积引进 Lucene

Elasticsearch：将最大内积引进 Lucene
图 4：这是 Cohere 在维基百科上的英语和日语嵌入的混合。 这两个数据集都可以在 HuggingFace 上找到。
Elasticsearch：将最大内积引进 Lucene
Elasticsearch：将最大内积引进 Lucene
Elasticsearch：将最大内积引进 Lucene

咱们还针对一些组成数据集进行了测验，以保证咱们的严谨性。 咱们运用 e5-small-v2 创立了一个数据集，并经过不同的计算散布缩放了向量的大小。 为了简洁起见，我将仅显现两个散布。

图 5： 起伏 Pareto distribution。 pareto distribution 具有“肥尾”，这意味着散布的一部分的起伏比其他部分大得多。
Elasticsearch：将最大内积引进 Lucene
Elasticsearch：将最大内积引进 Lucene
Elasticsearch：将最大内积引进 Lucene

图 6：起伏的伽马散布。 这种散布或许具有很高的方差，并使其在咱们的试验中独一无二。

在咱们一切的试验中，仅有需求进行转换的是运用伽玛散布创立的组成数据集。 即使这样，向量也有必要以相反的次序刺进，首先是最大起伏，以证明改换的合理性。 这些都是例外情况。

假如你想了解一切试验以及整个过程中的一切过错和改善，请参阅 Lucene Github 问题，其间包括一切详细信息（以及过程中的过错）。 这是一个开放式研讨和开发的项目！

定论

这是一个适当长的旅程，需求进行多次查询才干保证 Lucene 可以支持最大内积。 咱们相信数据不言自明。 无需进行严重转换或对 Lucene 进行严重更改。 一切这些作业将很快解锁 Elasticsearch 的最大内积支持，并答应 Cohere 供给的模型成为 Elastic Stack 中的一等公民。

注：最大内积已经在 8.11 中进行了支持！

原文：Bringing Maximum-Inner-Product into Lucene — Elastic Search Labs