概述欧式空间中将高维空间的点映射到低维空间原本接近的点在低维空间中肯定依然接近但原本远离的点则有一定概率变成接近的点。这句话的意思是在欧氏空间中使用随机投影等降维映射时原本距离较近的点在映射后仍然会保持较近的距离因此它们被划分到同一个哈希桶中的概率很高。而原本距离较远的点也可能因为投影碰撞而意外被划分到同一个桶中但这种情况发生的概率较低。这正是局部敏感哈希LSH 能够高效进行近似最近邻搜索的核心依据。直观理解近距离点相似由于它们在原始空间中很近在任意随机方向上的投影值也相差不大因此它们落入同一个桶如取整后编号相同的概率高。远距离点不相似它们在随机方向上的投影值相差较大落入同一个桶的概率低但可能发生碰撞只是概率小。LSH 通过多次独立随机投影将每个点映射为一个由多个整数组成的哈希码并将具有相同哈希码的点放入同一个桶。查询时只需计算查询点的哈希码然后在对应桶中搜索即可。构造 LSH 桶的经典方法p-stable LSH欧氏距离对于欧氏距离常用的构造方式是从标准正态分布中随机生成一个 d 维向量 v每个分量独立同分布。随机选择一个实数 b均匀分布在 [0,w) 上w 是桶宽可调参数。定义哈希函数h(x)[v⋅xbw]其中v⋅x是点积 h(\mathbf{x}) \left[ \frac{\mathbf{v} \cdot \mathbf{x} b}{w} \right] 其中 v⋅x 是点积h(x)[wv⋅xb]其中v⋅x是点积为了降低单次投影碰撞概率通常使用 L 个哈希表每个表由 k 个独立的哈希函数组成将 k 个输出值拼接成一个 k 维的桶编号或字符串作为该表的键。当两个点距离较近时它们在每个哈希函数上的输出值相同的概率较高距离远时相同的概率较低。具体例子假设二维平面中的三个点A(1,2)B(2,3)与 A 距离近2\sqrt{2}2C(10,10)与 A 距离远约 12.7我们设定参数w4使用两个独立的哈希函数每个函数不同随机向量 v 和随机偏移 b。哈希函数 h1随机向量 v1(0.5,1.0)从标准正态分布采样随机偏移 b10.2 ,桶宽 w4计算:A:⌊(0.5∗11.0∗20.2)/4⌋⌊(0.520.2)/4⌋⌊2.7/4⌋0\lfloor(0.5 * 1 1.0 * 2 0.2)/4\rfloor \lfloor(0.5 2 0.2)/4\rfloor \lfloor 2.7/4 \rfloor 0⌊(0.5∗11.0∗20.2)/4⌋⌊(0.520.2)/4⌋⌊2.7/4⌋0B:⌊(0.5∗21.0∗30.2)/4⌋⌊(130.2)/4⌋⌊4.2/4⌋1\lfloor(0.5 * 2 1.0 * 3 0.2)/4\rfloor \lfloor(1 3 0.2)/4\rfloor \lfloor 4.2/4 \rfloor 1⌊(0.5∗21.0∗30.2)/4⌋⌊(130.2)/4⌋⌊4.2/4⌋1C:⌊(0.5∗101.0∗100.2)/4⌋⌊(5100.2)/4⌋⌊15.2/4⌋3\lfloor(0.5 * 10 1.0 * 10 0.2)/4\rfloor \lfloor(5 10 0.2)/4\rfloor \lfloor 15.2/4 \rfloor 3⌊(0.5∗101.0∗100.2)/4⌋⌊(5100.2)/4⌋⌊15.2/4⌋3哈希函数 h2随机向量 v2(0.8,−0.6)随机偏移 b20.5桶宽 w4计算:A:⌊(0.8∗1(−0.6)∗20.5)/4⌋⌊(0.8−1.20.5)/4⌋⌊0.1/4⌋0\lfloor(0.8 * 1 (-0.6) * 2 0.5)/4\rfloor \lfloor(0.8 - 1.2 0.5)/4\rfloor \lfloor 0.1/4 \rfloor 0⌊(0.8∗1(−0.6)∗20.5)/4⌋⌊(0.8−1.20.5)/4⌋⌊0.1/4⌋0B:⌊(0.8∗2(−0.6)∗30.5)/4⌋⌊(1.6−1.80.5)/4⌋⌊0.3/4⌋0\lfloor(0.8 * 2 (-0.6) * 3 0.5)/4\rfloor \lfloor(1.6 - 1.8 0.5)/4\rfloor \lfloor 0.3/4 \rfloor 0⌊(0.8∗2(−0.6)∗30.5)/4⌋⌊(1.6−1.80.5)/4⌋⌊0.3/4⌋0C:⌊(0.8∗10(−0.6)∗100.5)/4⌋⌊(8−60.5)/4⌋⌊2.5/4⌋0\lfloor(0.8 * 10 (-0.6) * 10 0.5)/4\rfloor \lfloor(8 - 6 0.5)/4\rfloor \lfloor 2.5/4 \rfloor 0⌊(0.8∗10(−0.6)∗100.5)/4⌋⌊(8−60.5)/4⌋⌊2.5/4⌋0组合哈希码一个哈希表由两个哈希函数组成桶键为 (h1,h2) 对A(0,0)B(1,0)C(3,0)可以看到A 和 B 在 h1 上不同但考虑到两个哈希函数它们依然不在同一桶中而 C 和 A 在 h2 上相同但 h1 不同也不在同一桶。为了增加相似点碰撞概率实际中会使用多个这样的哈希表每个表有自己的随机向量和偏移并采用 OR 策略只要在任一个表中同桶就视为候选。这样A 和 B 虽然在这个表中没同桶但在其他表中很可能同桶。如果增加更多哈希函数如 k5以及多个哈希表如 L10那么对于近距离点它们至少在一个表中同桶的概率会非常高接近1而远距离点同桶的概率很低。
概述欧式空间中将高维空间的点映射到低维空间原本接近的点在低维空间中肯定依然接近但原本远离的点则有一定概率变成接近的点。这句话的意思是在欧氏空间中使用随机投影等降维映射时原本距离较近的点在映射后仍然会保持较近的距离因此它们被划分到同一个哈希桶中的概率很高。而原本距离较远的点也可能因为投影碰撞而意外被划分到同一个桶中但这种情况发生的概率较低。这正是局部敏感哈希LSH 能够高效进行近似最近邻搜索的核心依据。直观理解近距离点相似由于它们在原始空间中很近在任意随机方向上的投影值也相差不大因此它们落入同一个桶如取整后编号相同的概率高。远距离点不相似它们在随机方向上的投影值相差较大落入同一个桶的概率低但可能发生碰撞只是概率小。LSH 通过多次独立随机投影将每个点映射为一个由多个整数组成的哈希码并将具有相同哈希码的点放入同一个桶。查询时只需计算查询点的哈希码然后在对应桶中搜索即可。构造 LSH 桶的经典方法p-stable LSH欧氏距离对于欧氏距离常用的构造方式是从标准正态分布中随机生成一个 d 维向量 v每个分量独立同分布。随机选择一个实数 b均匀分布在 [0,w) 上w 是桶宽可调参数。定义哈希函数h(x)[v⋅xbw]其中v⋅x是点积 h(\mathbf{x}) \left[ \frac{\mathbf{v} \cdot \mathbf{x} b}{w} \right] 其中 v⋅x 是点积h(x)[wv⋅xb]其中v⋅x是点积为了降低单次投影碰撞概率通常使用 L 个哈希表每个表由 k 个独立的哈希函数组成将 k 个输出值拼接成一个 k 维的桶编号或字符串作为该表的键。当两个点距离较近时它们在每个哈希函数上的输出值相同的概率较高距离远时相同的概率较低。具体例子假设二维平面中的三个点A(1,2)B(2,3)与 A 距离近2\sqrt{2}2C(10,10)与 A 距离远约 12.7我们设定参数w4使用两个独立的哈希函数每个函数不同随机向量 v 和随机偏移 b。哈希函数 h1随机向量 v1(0.5,1.0)从标准正态分布采样随机偏移 b10.2 ,桶宽 w4计算:A:⌊(0.5∗11.0∗20.2)/4⌋⌊(0.520.2)/4⌋⌊2.7/4⌋0\lfloor(0.5 * 1 1.0 * 2 0.2)/4\rfloor \lfloor(0.5 2 0.2)/4\rfloor \lfloor 2.7/4 \rfloor 0⌊(0.5∗11.0∗20.2)/4⌋⌊(0.520.2)/4⌋⌊2.7/4⌋0B:⌊(0.5∗21.0∗30.2)/4⌋⌊(130.2)/4⌋⌊4.2/4⌋1\lfloor(0.5 * 2 1.0 * 3 0.2)/4\rfloor \lfloor(1 3 0.2)/4\rfloor \lfloor 4.2/4 \rfloor 1⌊(0.5∗21.0∗30.2)/4⌋⌊(130.2)/4⌋⌊4.2/4⌋1C:⌊(0.5∗101.0∗100.2)/4⌋⌊(5100.2)/4⌋⌊15.2/4⌋3\lfloor(0.5 * 10 1.0 * 10 0.2)/4\rfloor \lfloor(5 10 0.2)/4\rfloor \lfloor 15.2/4 \rfloor 3⌊(0.5∗101.0∗100.2)/4⌋⌊(5100.2)/4⌋⌊15.2/4⌋3哈希函数 h2随机向量 v2(0.8,−0.6)随机偏移 b20.5桶宽 w4计算:A:⌊(0.8∗1(−0.6)∗20.5)/4⌋⌊(0.8−1.20.5)/4⌋⌊0.1/4⌋0\lfloor(0.8 * 1 (-0.6) * 2 0.5)/4\rfloor \lfloor(0.8 - 1.2 0.5)/4\rfloor \lfloor 0.1/4 \rfloor 0⌊(0.8∗1(−0.6)∗20.5)/4⌋⌊(0.8−1.20.5)/4⌋⌊0.1/4⌋0B:⌊(0.8∗2(−0.6)∗30.5)/4⌋⌊(1.6−1.80.5)/4⌋⌊0.3/4⌋0\lfloor(0.8 * 2 (-0.6) * 3 0.5)/4\rfloor \lfloor(1.6 - 1.8 0.5)/4\rfloor \lfloor 0.3/4 \rfloor 0⌊(0.8∗2(−0.6)∗30.5)/4⌋⌊(1.6−1.80.5)/4⌋⌊0.3/4⌋0C:⌊(0.8∗10(−0.6)∗100.5)/4⌋⌊(8−60.5)/4⌋⌊2.5/4⌋0\lfloor(0.8 * 10 (-0.6) * 10 0.5)/4\rfloor \lfloor(8 - 6 0.5)/4\rfloor \lfloor 2.5/4 \rfloor 0⌊(0.8∗10(−0.6)∗100.5)/4⌋⌊(8−60.5)/4⌋⌊2.5/4⌋0组合哈希码一个哈希表由两个哈希函数组成桶键为 (h1,h2) 对A(0,0)B(1,0)C(3,0)可以看到A 和 B 在 h1 上不同但考虑到两个哈希函数它们依然不在同一桶中而 C 和 A 在 h2 上相同但 h1 不同也不在同一桶。为了增加相似点碰撞概率实际中会使用多个这样的哈希表每个表有自己的随机向量和偏移并采用 OR 策略只要在任一个表中同桶就视为候选。这样A 和 B 虽然在这个表中没同桶但在其他表中很可能同桶。如果增加更多哈希函数如 k5以及多个哈希表如 L10那么对于近距离点它们至少在一个表中同桶的概率会非常高接近1而远距离点同桶的概率很低。
