Algo from Scratch

• Locality Sensitive Hashing (LSH)
  LSH 是一类用于近似估计相似度的方法。此处只记录了最经典的一种（Shingling & MinHash）。
  • 思路
    • 得到一篇文档的某种向量表示（如 one-hot）后，直接求相似度（如 cosine）需要计算一个很大的向量乘法，虽然 GPU 计算等方法可以加速，但是我们依然希望有方法可以化简（哪怕是近似地）。LSH 方法中，我们用固定位数（|s|）的签名（signature）代表原始向量（签名位数<<原始向量长度），进而比较切割成固定份数（k）的签名中是否存在相同片段。实践发现，选取合适的|s|与 k 可以高效又精确地近似相似度计算。
    • 令高维空间中距离相近的两点哈希值相同的概率变大，由此可以将哈希值相同的数据聚为一类。
  • 步骤：
    1. 将文档切为 n-gram 格式（也称作 shingling）。
    2. 将 n-gram 后的文档编为 one-hot，并建立词典。设词典长度为|V|
    3. 建立签名（signature）索引。预先设定签名长度|s|，那么索引大小为|V|*|s|。其中每一个长为|V|的子向量都是[0, …, |V|-1]的一个乱序。
    4. 生成签名。
       1. 生成第 i 位签名时，首先抽取签名索引的第 i 个子向量
       2. 对于[0, …, |V|-1]中的每个数，找到其在子向量中的索引 index
       3. 若 one-hot[index] == 1，则此 index 将作为第 i 位签名
       4. 重复上述步骤，得到下一位签名，直到生成完整签名
    5. 切割签名（banding）。预先设定要将签名切割为 k 份。
    6. 对两篇文档同时遍历比较切割后的签名，如果出现相同片段，则认为两篇文档是相似的（is a candidate pair）。