在搜索推荐中，通常使用相似Embedding进行推荐，此时就会有一个问题： 如何快速找到与一个Embedding相近的其他Embedding
如果两个Embedding在同一个向量空间中，我们就可以通过很多种方式（内积、余弦、欧氏距离等）计算其相似度；例如在推荐系统中，用户和物品的Embedding都在同一个空间中，物品总数为(n)，那么计算一个用户和所以物品向量相似度的时间复杂度是(O(n))，而(n)通常都能达到百万甚至上亿，这样的计算方式是无法接受的；
1 朴素方法
1.1 聚类
如果将相似点聚类在一起，在检索相似向量的时候则可以快速缩小范围，只计算目标Embedding所在的聚类范围内的相似度，这里可以使用叫常见的[[K-means]]聚类方法；
但是这种方法在 聚类的边缘会出现些问题，如果只检索类别内的向量，则可能遗漏在其他类别中的相近点；另外，对于 K-means方法，K值得选择也是一个问题，如果K选的太大，则迭代过程会很缓慢；K值选的太小，则搜索范围无法有效降低；
- K值得选择经验：K=Embedding的维度开4次方根，调参按照2的整数次幂进行调整
1.2 索引
例如使用经典的[[Kd-tree]]向量空间索引算法中，同样存在边缘点的问题， Kd-tree会找到最邻近的区域，但是其他区域同样存在可能的最近点；另外 Kd-tree的索引结构较为复杂，导致离线和在线的维护也相对复杂；
2 局部敏感哈希基本原理
局部敏感哈希（Locality Sensitive Hashing, LSH）高效地解决了Embedding匹配的问题。
局部敏感哈希基本思想，是将相邻的点落入同一个”桶”，这样在进行最邻近搜索时，仅需要在一个桶内或邻近几个桶内进行搜索，只需要保证每个桶内的元素个数保持在一个较小的范围内；
如下图所示例子，首先需要确定一个结论： 在[[欧式空间]]中，将高位空间的点映射到低维空间，原本接近的点在低维空间中肯定依然接近，但原本远离的点则有一定概率变成接近的点。
利用上面的 低维空间保留高位空间相近距离关系的性质，我们可以设计构造多个”桶”。假设(v)是高位空间中的(k)维Embedding向量，(x)是随机生成的(k)维向量，可以得到一个数值(h(v) = v \cdot x)。
根据这个数值，我们设计哈希函数(h(v))进行分桶：
[h^{x,b}(v)=\lfloor\frac{x\cdot v+b}{w}\rfloor ]
上面公式中(w)是分桶宽度，(b)是0到(w)之间的一个均匀分布随机变量，其作用是 避免分桶边界固化。为了避免映射操作损失信息，可以使用(m)个哈希函数进行分桶，如果同时掉入多个桶，则其相似的概率将会增加。在确定了桶后，就在其有限的集合内进行[[K近邻]]搜索即可。
3 多桶策略
当存在多个哈希函数的时候，聚合中的点可能以不同的分布方式落在多个桶当中。最简单的就是一个点在匹配的桶中都出现（AND）以及在任意一个桶中出现（OR）两种策略。多桶策略还可以更复杂，比如三个分桶，可以选择同时落入两个桶中的点作为候选点。下面有一些建议的策略：
- 点数越多，越应该增加每个分桶函数中桶的个数；点数越少，越应该减少桶的个数；
- Embedding的维度越高，越应该增加分桶哈希函数的数量，并使用且的方式作为多桶策略；若Embedding维度低，则可以少用哈希函数，并用或的方式作为分桶策略；
4 存储部署思路
例如在商品推荐系统中，商品称为(item)有对应的 item_id，可以使用以下方案：
- 存储 item_id: BucketId
- 存储 BucketId: item_id
在召回的时候，先使用目标item_id找到对应的BucketId，然后再通过BucketId桶中的商品，实际上就是建立[[倒排索引]]的思路。
5 总结
LSH相比一些朴素的方法，高效地解决了相似向量查找的问题，通过多桶机制减小其哈希分桶的损失；但是也存在一些问题，大数据量情况下哈希函数的个数不好确定，另外在进行哈希计算的时候，可能会存在哈希冲突，导致召回率降低。
此外向量相似查找，还有一些基于树、基于量化、基于图的方法，根据不同的场景也可一试。
Original: https://www.cnblogs.com/diosguo/p/16061681.html
Author: diosguo
Title: 局部敏感哈希-向量相似搜索
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/807264/
转载文章受原作者版权保护。转载请注明原作者出处！