学习总结

（1）上一个task我们提到用embedding召回，快速过滤商品，缩小候选集。但是embedding相似度如果都用余弦计算，当数据量很大时计算量很大。所以提出用【局部敏感哈希LSH】解决高维空间下，embedding最近邻问题。在每个桶内点的数量接近时，LSH最近邻查找embedding的时间复杂度为常数级别。
（2）还可以用【多桶策略】提高搜索效率和召回率：
1）基于“且”操作的多桶策略能够进一步减少候选集规模，增加计算效率，
2）基于“或”操作的多桶策略则能够提高召回率，减少漏掉最近邻点的可能性。

（3）LSH的取值（注意：一切工程问题都是取舍的问题。）：

• 点数越多，我们越应该增加每个分桶函数中桶的个数；相反，点数越少，我们越应该减少桶的个数；
• Embedding 向量的维度越大，我们越应该增加哈希函数的数量，尽量采用且的方式作为多桶策略；相反，Embedding 向量维度越小，我们越应该减少哈希函数的数量，多采用或的方式作为分桶策略。

（4）其实LSH也有缺点：数据量太大的时候，hash的个数不好选择，另外存在hash冲突，容易降低召回率。同基于树的，基于量化的，基于的图的方法来比，在召回率，速度和内存使用上都不占优势。可以参考Facebook的开源向量最近邻搜索库FAISS（Faiss适合大规模库向量的查找，Lsh适合小规模的查找，效果上，Faiss召回比Lsh低）。

一、“快速”Embedding 最近邻搜索

在训练物品和用户的 Embedding 向量时，如果二者的 Embedding 在同一个向量空间内（如图 1），我们就可以通过内积、余弦、欧式距离等相似度计算方法，来计算它们之间的相似度，从而通过用户 - 物品相似度进行个性化推荐，或者通过物品 - 物品相似度进行相似物品查找。

假设，用户和物品的 Embeding 都在一个 k 维的 Embedding 空间中，物品总数为 n，那么遍历计算一个用户和所有物品向量相似度的时间复杂度是多少呢？不难算出是 O(k×n)。虽然这一复杂度是线性的，但物品总数 n 达到百万甚至千万量级时，线性的时间复杂度也是线上服务不能承受的。

二、“聚类”or“索引”

2.1 kmeans算法

• 随机指定 k 个中心点；
• 每个中心点代表一个类，把所有的点按照距离的远近指定给距离最近的中心点代表的类；
• 计算每个类包含点的平均值作为新的中心点位置；
• 确定好新的中心点位置后，迭代进入第 2 步，直到中心点位置收敛，不再移动。

缺点：

• 还是存在着一些边界情况。比如，聚类边缘的点的最近邻往往会包括相邻聚类的点，如果我们只在类别内搜索，就会遗漏这些近似点。
• 中心点的数量 k 也不那么好确定，k 选得太大，离线迭代的过程就会非常慢，k 选得太小，在线搜索的范围还是很大，并没有减少太多搜索时间。

2.2 Kd-tree算法

Kd-tree是为空间中的点 / 向量建立一个索引。

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

• 但它还是无法完全解决边缘点最近邻的问题。对于点 q 来说，它的邻接片区是右上角的片区，但是它的最近邻点却是深蓝色切分线下方的那个点。所以按照 Kd-tree 的索引方法，我们还是会遗漏掉最近邻点，它只能保证快速搜索到近似的最近邻点集合。
• 而且 Kd-tree 索引的结构并不简单，离线和在线维护的过程也相对复杂

三、LSH原理及多桶策略

3.1 LSH介绍

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

时间复杂度：如果保持每个桶中的元素个数在一个常数附近，我们就可以把最近邻搜索的时间复杂度降低到常数级别。

先看实验得出的一个结论（上图就是将高维的彩色点映射到低维的abc中）：欧式空间中，将高维空间的点映射到低维空间，原本接近的点在低维空间中肯定依然接近，但原本远离的点则有一定概率变成接近的点。

（1）将高维embedding映射到低维：
由于 Embedding 大量使用内积操作计算相似度，因此我们也可以用内积操作来构建局部敏感哈希桶。假设 v 是高维空间中的 k 维 Embedding 向量，x 是随机生成的 k 维映射向量。那我们利用内积操作可以将 v 映射到一维空间，得到数值 h(v)=v⋅x。

（2）分桶：
一维空间也会部分保存高维空间的近似距离信息。因此，我们可以使用哈希函数 h(v) 进行分桶，公式为：$$h^{x,b}(v)=\lfloor \frac{x\cdot v+b}{w}]$$ 其中， ⌊ ⌋ 是向下取整操作， w 是分桶宽度，b 是 0 到 w 间的一个均匀分布随机变量，避免分桶边界固化。

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

（3）用多个哈希函数同时分桶：
映射的过程会损失部分的距离信息，并且为了防止相近点误判，可以同时用m个哈希函数同时进行分桶操作——如果两个点都同时掉入同一个桶中，则他们是相似的点的概率就很大。就这样得到的候选集再通过遍历得到K邻近。

哈希策略是基于内积操作来制定的，内积相似度也是我们经常使用的相似度度量方法，事实上距离的定义有很多种，比如“曼哈顿距离”、“切比雪夫距离”、“汉明距离”等等。针对不同的距离定义，分桶函数的定义也有所不同，但局部敏感哈希通过分桶方式保留部分距离信息，大规模降低近邻点候选集的本质思想是通用的。

3.2 多桶策略

刚才3.1的使用多个哈希函数进行分桶操作：

（1）分桶栗子

背景：
假设有 A、B、C、D、E 五个点，有 h1和 h2两个分桶函数。
使用 h1来分桶时，A 和 B 掉到了一个桶里，C、D、E 掉到了一个桶里；
使用 h2来分桶时，A、C、D 掉到了一个桶里，B、E 在一个桶。
那么请问如果我们想找点 C 的最近邻点，应该怎么利用两个分桶结果来计算呢？

（1）用“且”（And）操作：
这样处理两个分桶结果之间的关系，则找到与点 C 在 h1函数下同一个桶的点，且在 h2函数下同一个桶的点，作为最近邻候选点。我们可以看到，满足条件的点只有一个，那就是点 D。也就是说，点 D 最有可能是点 C 的最近邻点。

作为多桶策略，可以最大程度地减少候选点数量。但是，由于哈希分桶函数不是一个绝对精确的操作，点 D 也只是最有可能的最近邻点，不是一定的最近邻点，因此，“且”操作其实也增大了漏掉最近邻点的概率。

（2）采用“或”（Or）操作：
找到与点 C 在 h1函数下同一个桶的点，或在 h2函数下同一个桶的点。这个时候，我们可以看到候选集中会有三个点，分别是 A、D、E。这样一来，虽然我们增大了候选集的规模，减少了漏掉最近邻点的可能性，但增大了后续计算的开销。

better：局部敏感哈希的多桶策略还可以更加复杂，比如使用 3 个分桶函数分桶，把同时落入两个桶的点作为最近邻候选点等等。

（2）取值建议：

• 点数越多，我们越应该增加每个分桶函数中桶的个数；相反，点数越少，我们越应该减少桶的个数；
• Embedding 向量的维度越大，我们越应该增加哈希函数的数量，尽量采用且的方式作为多桶策略；相反，Embedding 向量维度越小，我们越应该减少哈希函数的数量，多采用或的方式作为分桶策略。

（3）时间复杂度

局部敏感哈希能在常数时间得到最近邻的结果吗？
答案是可以的，如果我们能够精确地控制每个桶内的点的规模是 C，假设每个 Embedding 的维度是 N，那么找到最近邻点的时间开销将永远在 O(C⋅N) 量级。采用多桶策略之后，假设分桶函数数量是 K，那么时间开销也在 O(K⋅C⋅N) 量级，这仍然是一个常数。

3.3 局部敏感哈希实践

使用 Spark MLlib 完成 LSH 的实现。

在将电影 Embedding 数据转换成 dense Vector 的形式之后，我们使用 Spark MLlib 自带的 LSH 分桶模型 BucketedRandomProjectionLSH（我们简称 LSH 模型）来进行 LSH 分桶。其中最关键的部分是设定 LSH 模型中的 BucketLength 和 NumHashTables 这两个参数：
（1）BucketLength 指的就是分桶公式中的分桶宽度 w；
（2）NumHashTables 指的是多桶策略中的分桶次数。

和其他 Spark MLlib 模型一样，都是先调用 fit 函数训练模型，再调用 transform 函数完成分桶的过程。

def embeddingLSH(spark:SparkSession, movieEmbMap:Map[String, Array[Float]]): Unit ={
  //将电影embedding数据转换成dense Vector的形式，便于之后处理
  val movieEmbSeq = movieEmbMap.toSeq.map(item => (item._1, Vectors.dense(item._2.map(f => f.toDouble))))
  val movieEmbDF = spark.createDataFrame(movieEmbSeq).toDF("movieId", "emb")


  //利用Spark MLlib创建LSH分桶模型
  val bucketProjectionLSH = new BucketedRandomProjectionLSH()
    .setBucketLength(0.1)
    .setNumHashTables(3)
    .setInputCol("emb")
    .setOutputCol("bucketId")
  //训练LSH分桶模型
  val bucketModel = bucketProjectionLSH.fit(movieEmbDF)
  //进行分桶
  val embBucketResult = bucketModel.transform(movieEmbDF)
  
  //打印分桶结果
  println("movieId, emb, bucketId schema:")
  embBucketResult.printSchema()
  println("movieId, emb, bucketId data result:")
  embBucketResult.show(10, truncate = false)
  
  //尝试对一个示例Embedding查找最近邻
  println("Approximately searching for 5 nearest neighbors of the sample embedding:")
  val sampleEmb = Vectors.dense(0.795,0.583,1.120,0.850,0.174,-0.839,-0.0633,0.249,0.673,-0.237)
  bucketModel.approxNearestNeighbors(movieEmbDF, sampleEmb, 5).show(truncate = false)
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
 

使用 LSH 模型对电影 Embedding 进行分桶得到的五个结果打印：

+-------+-----------------------------+------------------+
|movieId|emb                          |bucketId          |
+-------+-----------------------------+------------------------+
|710    |[0.04211471602320671,..]     |[[-2.0], [14.0], [8.0]] |
|205    |[0.6645985841751099,...]     |[[-4.0], [3.0], [5.0]]  |
|45     |[0.4899883568286896,...]     |[[-6.0], [-1.0], [2.0]] |
|515    |[0.6064003705978394,...]     |[[-3.0], [-1.0], [2.0]] |
|574    |[0.5780771970748901,...]     |[[-5.0], [2.0], [0.0]]  |
+-------+-----------------------------+------------------------+

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
 

可以使用多桶策略：BucketId 这一列，因为我们之前设置了 NumHashTables 参数为 3（用了3个分桶/哈希函数），所以每一个 Embedding 对应了 3 个 BucketId。

拓展：业界中广泛使用的Facebook的开源向量最近邻搜索库FAISS，https://github.com/facebookresearch/faiss。

四、作业

如果让你在推荐服务器内部的召回层实现最近邻搜索过程，你会怎样存储和使用我们在离线产生的分桶数据，以及怎样设计线上的搜索过程呢？

【答】建立倒排索引的思路：
以item_id作为key， item_id对应的BucketId作为value存储在redis， 再以每个BucketId作为key， item_id作为value存储在redis， 在召回的时候遍历item_id的所有BucketId，获取BucketId对应的item_id就是需要召回的item。

五、课后答疑

（1）embedding层K值的初始判断，有个经验公式:K= Embedding维数开4次方 ,x=初始的维度数；后续，K值调参按照2的倍数进行调整，例如：2，4，8，16；K是分桶的数量。

（2） “在训练物品和用户的 Embedding 向量时，如果二者的 Embedding 在同一个向量空间内”， 我们在之前6-7节embedding的中，讲了怎么把物品序列信息转化为embedding， 想知道，用户的embedding是怎么生成的呢？ 然后，物品和用户在同一个向量空间，这个是怎么得到的呢？

【答】项目里，用户embedding就是通过平均这个用户评论过的高分电影的embedding得到的。所以他们肯定是在一个向量空间里。只要是利用用户历史的item embedding生成的用户embedding，可以说都是在一个向量空间内，这些生成方式包括但不限于average pooling，sum pooling，attention等等。
【注意】但是如果用户 Embedding 和物品 Embedding 是分别独立生成的，或者说是通过一个模型中没有直接关系的两个 Embedidng 层生成的，那么它们就不在一个向量空间内了。注意啦，这个时候，我们不能直接求用户和物品之间的相似度，只能求用户 - 用户的相似度，和物品 - 物品的相似度。

（3）对于计算距离，欧几里得距离和余弦距离等应该怎么选择？
【答】根据你训练embedding时候选择的相似度来确定。
比如你训练embedding模型时就采用了欧式距离，那么这里就用欧式距离。训练模型时用了内积，这里就用内积。

Reference

（1）https://github.com/wzhe06/Reco-papers
（2）《深度学习推荐系统实战》，王喆
（3）LSH(Locality Sensitive Hashing)原理与实现
（4）如何通俗易懂讲解局部敏感哈希算法？

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/120999433