【推荐系统中的Hash 2】局部敏感哈希（利用冲突）

二、局部敏感哈希（利用冲突）

之前提到的向量检索方法中最主流的快速方法就是利用局部敏感哈希实现的，属于近似最近邻查找（Approximate Nearest Neighbor, ANN）的一种。

向量检索目标：在海量向量中为向量q检索出最相似的k个向量。

背景方法

KNN

KNN就不多说了，遍历整个向量物料库，一一计算向量内积，返回最大的K个。如果索引频率是用户访问请求级别的是承担不起的。

Kd-tree

Kd-Tree激光点云编程中经常使用的一个工具，比如在三维点云中kd-tree的维度是3，向量是k维就是kd-tree。这里以二维为例方便讲解。

首先将2维数据点组织成二叉树的结构，比如先用红色的线把点云一分为二，再用深蓝色的线把各自片区的点云一分为二，以此类推，直到每个片区只剩下一个点，这就完成了空间索引的构建。如果我们能够把这套索引“搬”到线上，就可以利用二叉树的结构快速找到邻接点。比如，希望找到点 q 的 k 个邻接点，我们就可以先搜索它相邻子树下的点，如果数量不够，我们可以向上回退一个层级，搜索它父片区下的其他点，直到数量凑够 k 个为止。

kd-tree的实现是改造的线段树。

kd-tree的准确度缺点是无法完全解决边缘点最近邻的问题。对于点 q 来说，它的邻接片区是右上角的片区，但是它的最近邻点却是深蓝色切分线下方的那个点。

kd-tree的性能缺点是构造和维护树结构的索引也比较复杂

Locality Sensitive Hashing——LSH

局部敏感哈希的基本思想是希望让相邻的点落入同一个“桶”，这样在进行最近邻搜索时，我们仅需要在一个桶内，或相邻几个桶内的元素中进行搜索即可。

理论基础：高维空间的点映射到低维空间，原本接近的点在低维空间中肯定依然接近，但原本远离的点则有一定概率变成接近的点。比如用内积作为相似度。

把二维空间中的点通过不同角度映射到 a、b、c 这三个一维空间时，可以看到原本相近的点，在一维空间中都保持着相近的距离。而原本远离的绿色点和红色点在一维空间 a 中处于接近的位置，却在空间 b 中处于远离的位置。

假设 $v$ 是高维空间中的 $k$ 维 Embedding 向量，$x$ 是随机生成的 $k$ 维映射向量。那我们利用内积操作可以将 $v$ 映射到一维空间，得到数值$h(v)=v\cdot x$

使用哈希函数 h(v) 进行分桶，公式为
$$h^{x,b}(v)=\lfloor \frac{x\cdot v+b}{w}\rfloor$$
其中， ⌊⌋ 是向下取整操作， w 是分桶宽度，b 是 0 到 w 间的一个均匀分布随机变量，避免分桶边界固化。

分桶固化：防止相邻的点每次都落在不同的桶。如果总是固定边界，很容易让边界两边非常接近的点总是被分到两个桶里。这是我们不想看到的。 所以随机调整b，生成多个hash函数，并且采用或的方式组合，就可以一定程度避免这些边界点的问题。

采用 m 个哈希函数同时进行分桶。如果两个点同时掉进了 m 个桶，那它们是相似点的概率将大大增加。