深入研究组合的LSH函数以确保更可靠的搜索
相似性搜索是一个问题，给定一个查询，目标是在所有数据库文档中找到与之最相似的文档。
介绍
在数据科学中，相似性搜索经常出现在自然语言处理领域、搜索引擎或推荐系统中，需要为查询检索出最相关的文档或项目。有许多不同的方法来提高在大量数据中的搜索性能。
在本文系列的最后两部分中，我们深入研究了LSH——一种将输入向量转换为低维哈希值的算法，同时保留有关它们相似性的信息。特别是，我们已经看过了两种适用于不同距离度量的算法：
相似性搜索，第5部分：局部敏感哈希（LSH）
探索如何将相似性信息合并到哈希函数中
towardsdatascience.com
经典的LSH算法构造的签名反映了向量的Jaccard指数的信息。
相似性搜索，第6部分：随机投影与LSH森林
了解如何通过构建随机超平面对数据进行哈希并反映其相似性
towardsdatascience.com
随机投影方法构建了保留向量余弦相似性的超平面森林。
事实上，LSH算法也适用于其他距离度量。虽然每种方法都有其独特的部分，但在每种方法中都有许多共同的概念和公式。为了便于未来学习新方法，我们将更多地关注理论，并提供几个在高级LSH文献中经常出现的重要定义和定理。在本文结束时，我们将能够通过简单地组合基本方法来构建更复杂的LSH方案，就像组合乐高积木一样。
作为奖励，在最后，我们还将看看如何将欧几里德距离合并到LSH中。
注意。作为主要前提条件，预期您已经熟悉了本文系列的第5部分和第6部分。如果没有，请强烈建议先阅读它们。
注意。余弦距离在范围[0, 2]内正式定义。为简单起见，我们将其映射到区间[0, 1]，其中0和1分别表示最低和最高可能的相似性。
正式的LSH定义
给定距离度量d，如果对于随机选择的对象x和y，满足以下条件，则称H为（d₁，d₂，p₁，p₂）敏感的LSH函数：
- 如果d(x, y) ≤ d₁，则p(H(x) = H(y)) ≥ p₁，即至少以概率p₁哈希到同一个桶中。
- 如果d(x, y) ≥ d₂，则p(H(x) = H(y)) ≤ p₂，即至多以概率p₂哈希到同一个桶中。
让我们理解这些语句的含义。当两个向量相似时，它们之间的距离较小。基本上，第一个语句确保将它们哈希到相同桶的概率高于某个阈值。这样，一些错误的负例被消除了：如果两个向量之间的距离大于d₁，则它们哈希到相同桶的概率始终小于p₁。相反，第二个语句控制了错误的正例：如果两个向量不相似且它们之间的距离大于d₂，则它们以最多p₂的概率出现在同一个桶中。
给定上述陈述，我们通常希望系统中满足以下陈述：
- p₁应尽可能接近1，以减少误报的数量。
- p₂应尽可能接近0，以减少误报的数量。
- d₁和d₂之间的间隔应尽可能低，以减少无法进行数据概率估计的区间。
有时，上述陈述使用相似度s而不是距离d来引入：
给定相似度度量s，如果对于随机选择的对象x和y，满足以下条件，则称H为（s₁、s₂、p₁、p₂）-敏感LSH函数：
- 如果s(x, y) ≥ s₁，则p(H(x) = H(y)) ≥ p₁，即H(x) = H(y)的概率至少为p₁。
- 如果s(x, y) ≤ s₂，则p(H(x) = H(y)) ≤ p₂，即H(x) = H(y)的概率最多为p₂。
备注：在本文中，将同时使用（d₁、d₂、p₁、p₂）和（s₁、s₂、p₁、p₂）两种表示方法。根据文本中表示法中使用的字母，应该清楚是距离d还是相似度s。默认情况下，使用表示法（d₁、d₂、p₁、p₂）。
LSH示例
为了更清晰地说明问题，让我们证明以下陈述：
如果距离度量s是Jaccard指数，则H是（0.6、0.6、0.4、0.4）-敏感LSH函数。基本上，等效的陈述必须被证明：
- 如果d(x, y) ≤ 0.6，则p(H(x) = H(y)) ≥ 0.4
- 如果d(x, y) ≥ 0.6，则p(H(x) = H(y)) ≤ 0.4
根据本文系列的第5部分，我们知道对于两个二进制向量来说，得到相等的哈希值的概率等于Jaccard相似度。因此，如果两个向量的相似度至少为40%，那么可以保证得到相等的哈希值的概率也至少为40%。同时，至少40%的Jaccard相似度等效于最大的Jaccard指数为60%。因此，第一个陈述被证明。对于第二个陈述，可以做类似的推理。
这个例子可以推广为以下定理：
定理。如果d是Jaccard指数，则H是（d₁、d₂、1 – d₁、1 – d₂）-LSH函数族。
同样地，根据第6部分得到的结果，可以证明另一个定理：
定理。如果s是余弦相似度（在-1和1之间），那么H是一个（s₁，s₂，1 – arccos(s₁) / 180，1 – arccos(d₂) / 180）-LSH函数族。
组合LSH函数
让我们回顾一下在前面的LSH部分中学到的有用概念：
- 回顾第5部分的minhashing，每个向量被分成几个带，每个带包含一组行。为了将一对向量视为候选对，必须存在至少一个带，其中所有向量行都相等。
- 关于第6部分的随机投影，只有存在至少一个树，其中所有随机投影没有分离初始向量的情况下，两个向量才被视为候选。
我们可以注意到，这两种方法在内部具有相似的范式。它们都只有在至少一次出现n个配置中向量的哈希值在k次中都相同的情况下，才将一对向量视为候选。用布尔代数表示，可以写成这样：
基于这个例子，让我们介绍逻辑运算符OR和AND，它们允许聚合一组哈希函数。然后我们将估计它们对两个向量作为候选的输出概率以及误差的虚警率和漏警率的影响。
AND运算符
给定n个独立的LSH函数H₁，H₂，…Hₙ，AND运算符只有在两个向量的所有n个相应哈希值都相等时，才将它们视为候选对。否则，不将向量视为候选。
如果将两个高度不同的向量的哈希值由AND运算符聚合，那么它们被视为候选的概率随着使用的哈希函数数量的增加而减小。因此，虚警率减少。
同时，两个相似的向量可能会偶然产生一对不同的哈希值。因此，根据该算法，这样的向量将不被认为相似。这一方面导致漏警率较高。
定理。考虑r个独立的（s₁，s₂，p₁，p₂）-敏感LSH函数。将这些r个LSH函数与AND运算符结合，结果是一个具有以下参数的新LSH函数：
可以通过使用几个独立事件的概率公式，将所有事件的概率相乘来证明这个陈述，从而估计所有事件都会发生的概率。
OR运算符
给定n个独立的LSH函数H₁，H₂，…Hₙ，OR运算符只有在两个向量的至少一个相应哈希值相等时，才将它们视为候选对。否则，不将向量视为候选。
与AND运算符相反，OR运算符增加了任意两个向量成为候选对的概率。对于任意一对向量，只需要至少一个相应哈希值相等即可。因此，OR聚合减少了漏警率，增加了虚警率。
定理。考虑b个独立的（d₁，d₂，p₁，p₂）-族LSH函数。将这些b个LSH函数与AND运算符结合，结果是一个具有以下参数的新LSH函数：
我们不会证明这个定理，因为类似的概率公式在本系列文章的第5部分中已经得到并解释过了。
组合
通过AND和OR操作，可以以不同的方式将它们结合在一起，以更好地控制误报率和漏报率。假设AND组合器使用了r个LSH函数，OR组合器使用了b个LSH函数，可以使用这些基本组合器构建两种不同的组合：
前两篇文章中描述的算法使用了AND-OR组合。事实上，我们可以根据AND和OR操作构建更复杂的组合。
组合示例
让我们通过一个例子来了解AND和OR的组合如何显著提高性能。假设使用参数b = 4和r = 8的OR-AND组合。根据上面的相应公式，我们可以估计在组合后两个向量成为候选项的初始概率如何转变：
例如，如果对于两个向量之间的某个相似性值，单个LSH函数在40%的情况下将它们哈希到相同的桶中，则在应用OR-AND组合后，它们将在32.9%的情况下被哈希。
为了理解组合的特殊之处，考虑一个(0.4, 1.7, 0.8, 0.2)-敏感的LSH函数。经过OR-AND转换后，LSH函数转化为(0.4, 1.7, 0.0148, 0.987)-敏感的格式。
实际上，如果最初两个向量非常相似，距离小于0.4，那么它们在80%的情况下将被视为候选项。然而，使用组合后，它们在98.7%的情况下成为候选项，从而大大减少了误报错误！
同样地，如果两个向量彼此非常不同，距离大于1.7，那么它们现在只在1.48%的情况下被视为候选项（之前是20%）。这样，误报错误的频率减少了13.5倍！这是一个巨大的改进！
一般来说，通过具有(d₁, d₂, p₁, p₂)-敏感的LSH函数，可以将其转换为接近1的(d₁, d₂, p’₁, p’₂)格式，其中p’₁接近1，p’₂接近0。要更接近1和0通常需要使用更多的组合。
用于其他距离度量的LSH
我们已经深入研究了用于保留Jaccard指数和余弦距离信息的LSH方案。现在出现的自然问题是是否可以将LSH用于其他距离度量。不幸的是，对于大多数度量，没有相应的LSH算法。
尽管如此，对于欧氏距离（机器学习中最常用的度量之一），存在LSH方案。由于它经常被使用，我们将学习如何为欧氏距离获得哈希值。使用上面介绍的理论符号，我们将证明这个度量的一个重要LSH属性。
欧几里得距离的局部敏感哈希（LSH）
在欧几里得空间中，哈希点的机制包括将它们投影到一条随机线上。算法假设：
- 如果两个点相对靠近，那么它们的投影也应该靠近。
- 如果两个点相距较远，那么它们的投影也应该相距较远。
为了衡量两个投影的相似程度，可以将一条线段分成几个相等的部分（桶），每个线段对应一个特定的哈希值。如果两个点投影到同一线段上，则它们具有相同的哈希值。否则，哈希值是不同的。
尽管该方法一开始可能似乎很强大，但仍然可能将相距较远的点投影到同一段上。特别是当连接两个点的线几乎垂直于初始投影线时，就会发生这种情况。
为了降低错误率，强烈建议使用上述所讨论的随机投影线的组合。
几何上可以证明，如果 a 是欧几里得空间中单个线段的长度，则 H 是 (a / 2, 2a, ½, ⅓)-敏感的局部敏感哈希函数。
结论
在本章中，我们积累了关于一般LSH符号的知识，这使我们能够正式引入组合操作，从而显著降低错误率。值得注意的是，LSH仅适用于机器学习指标的一小部分，但至少适用于最受欢迎的指标，包括欧几里得距离、余弦距离和Jaccard指数。在处理衡量向量相似度的其他指标时，建议选择其他相似性搜索方法。
有关本文介绍的陈述的正式证明，请参阅这些注释。
资源
- 局部敏感哈希 | 大数据分析讲义 | Nimrah Mustafa
- 余弦距离 | 维基百科
除非另有说明，所有图片均为作者所创作。