2025-03-22
Hamming Distance
问题：给定 \(d\) 维 01 向量集合和若干次问询，每次问询求出最小 Hamming Distance 的 \(c-\)近似.
人类智慧：在对字符串做随机排列意义下，Hamming Distance 小意味着 LCP 有较高概率大.
所以考虑随机 \(M\) 个排列，然后对于每个排列，问询时求出 LCP 最大的。然后比较这 \(M\) 则结果即可.
\(M\) 要取在 \(O(n^{\frac{1}{c}})\). 下面是分析.
令答案为 \(r\)，\(p_1=1-r/d\)，\(p_2=1-cr/d\)，\(k=\log_{p_2}(1/n)\). 那么对于集合中的 \(q'\) 和问询点 \(q\)，若距离 \(>cr\)，则在两者 LCP \(\ge k\) 的概率至多 \(p_2^k=1/poly(n)\).
而另一方面，最优点和询问点 LCP \(\ge k\) 的概率为 \(p_1^k=1/n^{\frac{1}{c}}\). 于是令 \(M=O(n^\frac{1}{c})\) 就能大概率使得存在一个排列使得两点 LCP \(\ge k\).
Sim Hash
Cosine Similarity：对于两个向量 \(x,y\)，定义他们的 Cosine Similarity 为两者的夹角的 Cosine 值，即 \(\frac{x\cdot y}{|x||y|}\).
我们想要找到一个函数 \(H(x)\)，使得 \(Pr(H(x)=H(y))\) 能反应两者的距离.
考虑取随机向量 \(w\)，令 \(H(x)=\operatorname{sgn}(w\cdot x)\). 分析一下即可知道 \(Pr(H(x)=H(y))\) 等于 \(1-\theta/\pi\).
若我们随机取 \(T\) 个独立的这样的 \(H(x)\)，那么每个向量就变成了一个 01 向量，然后距离也就转化为了上面的 Hamming 距离.
Locality Sensitive Hashing
给出一个一般化的 Locality Sensitive Hashing：
- 在 \({\mathbb R}^{d}\)向量空间中，LSH 为一族随机哈希函数 \(H\)，满足：
- \(||x-y||\le r\) 的 \(x,y\) 有 \(Pr(H(x)=H(y))\ge p_1\).
- \(||x-y||\ge cr\) 的 \(x,r\) 有 \(Pr(H(x)=H(y))\le p_2\).
对于这样的 Hashing，定义 \(\rho=\frac{\log p_1}{\log p_2}\). 那么有了这个 Hashing，我们就能在 \(O(n^{1+\rho})\) 预处理 \(O(n^{\rho})\) 查询的时间复杂度下解决 \(c-\)近似的判定问题.
所以 LSH 的目标就是设计一个哈希，使得 \(\rho\) 尽量小.
上面提到的 Hamming 空间的 LSH 就有 \(\rho\le O(1/c)\).
而比如单位球空间上欧式空间中，若使用上述的 Sim Hash，那么也有 \(\rho\le O(1/c)\).
一个更好的算法是，对向量做随机旋转（即被随机旋转矩阵 \(M\) 作用），然后返回最近的标准基单位向量. 然后若干个这样的独立的 LSH 拼接得到最终的 LSH. 这样的 \(\rho\le O(1/c^2)\).