推荐系统局部敏感哈希解决Embedding最近邻搜索问题

文章目录

快速Embedding最近邻搜索问题

在深度学习推荐系统中，我们经常会使用Embedding方法对用户-物品进行向量化。在训练物品和用户的Embedding向量时，如果二者的 Embedding在同一个向量空间内，我们就可以通过内积、余弦、欧式距离等相似度计算方法，来计算它们之间的相似度，从而通过用户-物品相似度进行个性化推荐，或者通过物品-物品相似度进行相似物品查找。
假设用户-物品的Embedding都在一个k维的Embedding空间中，物品总数为n，那么用户和所有物品向量相似度的时间复杂度是 O(k×n)。如果物品总数n过大时，线性的时间复杂度也是线上服务器无法承受的。
用户-物品的Embedding在一个向量空间内，因此 召回与用户向量最相似的物品Embedding向量这一问题，其实就是在向量空间内搜索最近邻的过程 。

聚类、索引搜索最近邻

聚类搜索最近邻

聚类就是把相似的点聚类到一起，从而找到最近邻。
对于聚类搜索最近邻问题，最常见的方法就是K-means算法，步骤如下：
- 随机指定 k 个中心点；
- 每个中心点代表一个类，把所有的点按照距离的远近指定给距离最近的中心点代表的类；
- 计算每个类包含点的平均值作为新的中心点位置；
- 确定好新的中心点位置后，迭代进入第 2 步，直到中心点位置收敛，不再移动。
3中心点K-means迭代过程如下图：
如果我们能够在离线计算好每个Embedding向量的类别，在线上我们只需要在同一个类别内的Embedding向量中搜索就可以了。
K-means聚类的缺点：
- 对于边界情况不好处理。比如，聚类边缘的点的最近邻往往会包括相邻聚类的点，如果我们只在类别内搜索，就会遗漏这些近似点。
- k的数量也不那么好确定， k大，离线迭代慢，k小，在线搜索范围大，无法节约时间 。

索引搜索最近邻

我们还可以尝试一下经典的向量空间索引算法：Kd-tree（K-dimension tree）。与聚类不同，它是为空间中的点 / 向量建立一个索引。如下图：

红色的线把点云一分为二，再用深蓝色的线把各自片区的点云一分为二，以此类推，直到每个片区只剩下一个点，这就完成了空间索引的构建。如果我们能够把这套索引搬到线上，就可以利用二叉树的结构快速找到邻接点。
Kd-tree索引的缺点：
- 无法完全解决边缘点最近邻的问题。对于点q来说，它的邻接片区是右上角的片区，但是它的最近邻点却是深蓝色切分线下方的那个点。所以按照Kd-tree的索引方法，我们还是会遗漏掉最近邻点，它只能保证快速搜索到近似的最近邻点集合。
- Kd-tree索引结构复杂，离线和在线维护的过程也相对复杂。

局部敏感哈希及多桶策略

局部敏感哈希（Locality Sensitive Hashing,LSH）用简洁而高效的方法几乎完美地解决了这一召回层所出现的问题。

局部敏感哈希的基本原理

局部敏感哈希的基本思想是希望让相邻的点落入同一个桶，这样在进行最近邻搜索时，我们仅需要在一个桶内，或相邻几个桶内的元素中进行搜索即可。如果保持每个桶中的元素个数在一个常数附近，我们就可以把最近邻搜索的时间复杂度降低到常数级别。
欧式空间中， 将高维空间的点映射到低维空间，原本接近的点在低维空间中肯定依然接近，但原本远离的点则有一定概率变成接近的点 。利用低维空间可以保留高维空间相近距离关系的性质，我们就可以构造局部敏感哈希桶。由于Embedding大量使用内积操作计算相似度，因此就可以用内积操作来构建局部敏感哈希桶。假设v是高维空间中的k维Embedding向量，x是随机生成的k维映射向量。那我们利用内积操作可以将v映射到一维空间，得到数值 h(v)=v⋅x。
哈希分桶函数h(v) 公式如下（向下取整）：
w是分桶宽度，b是0到w间的一个均匀分布随机变量，避免分桶边界固化。
因为映射操作会损失部分距离信息，如果我们仅采用一个哈希函数进行分桶，必然存在相近点误判的情况。因此，我们可以采用m个哈希函数同时进行分桶。如果两个点同时掉进了m个桶，那它们是相似点的概率将大大增加。通过分桶找到相邻点的候选集合后，我们就可以在有限的候选集合中通过遍历找到目标点真正的K近邻了。

局部敏感哈希的多桶策略

如果有多个分桶函数的话，具体应该如何处理不同桶之间的关系？举个例子：假设有 A、B、C、D、E 五个点，有h1和h2两个分桶函数。使用h1来分桶时，一个桶内是A、B，另一个是C、D、E；使用h2来分桶时，一个桶内是A、C、D，另一个是B、E。C的最近邻点，如何找？可以通过与方法（AND）来处理两个分桶结果之间的关系。结果得出D为最近邻点。同样还有一种方法叫或(Or)，这样候选集就有三个点A、D、E。虽然增加了候选集的规模，但同样也增加计算开销。至于如何权衡与和或的方法主要是看具体项目而定。这里有以下两点建议：
1. 点数越多，分桶函数h中桶的个数也要越多；点数越少，桶的个数也要减少。
2. Embedding维度越大，哈希函数的数量增加，尽量采用且的方式作为多桶策略；反之，Embedding维度越小，哈希函数的数量减小，尽量采用或的方式作为多桶策略。

局部敏感哈希代码实现

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()
    //分桶公式中的分桶宽度w
    .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)
}