12 | 局部敏感哈希：如何在常数时间内搜索Embedding最近邻？
该思维导图由 AI 生成，仅供参考
推荐系统中的“快速”Embedding 最近邻搜索问题
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
本文介绍了解决深度学习推荐系统中Embedding召回的主要方法——局部敏感哈希（LSH）。文章首先指出了线性计算Embedding间相似度导致的服务延迟问题，然后对比了使用“聚类”和“索引”来搜索最近邻的可行性，分析了它们的局限性。接着介绍了Kd-tree索引方法的弊端，以及局部敏感哈希的基本原理及多桶策略。局部敏感哈希通过简洁而高效的方法几乎完美地解决了最近邻搜索问题，为推荐系统的召回层提供了有效的解决方案。局部敏感哈希的基本思想是让相邻的点落入同一个“桶”，从而降低最近邻搜索的时间复杂度。通过内积操作构建局部敏感哈希“桶”，并介绍了多桶策略，即使用多个分桶函数来增加找到相似点的概率。文章深入浅出地解释了局部敏感哈希的原理和多桶策略，为读者提供了深度学习推荐系统中Embedding召回的解决方案。文章还提供了实践环节，利用Sparrow Recsys训练好的物品Embedding，来实现局部敏感哈希的快速搜索。通过具体的代码示例和分桶操作的效果展示，读者可以更直观地了解局部敏感哈希的应用。最后，文章总结了各种方法的优缺点，并引发了读者的思考，鼓励他们参与开源项目的贡献。
《深度学习推荐系统实战》，新⼈⾸单¥68
全部留言(42)
- 最新
- 精选
Dikiwib 是 0 到 w 间的一个均匀分布随机变量，避免分桶边界固化。这是什么意思呢？是说可以通过调整b来形成另外一个一个hash函数？作者回复: 这是个好问题，推荐其他同学也关注。 因为如果总是固定边界，很容易让边界两边非常接近的点总是被分到两个桶里。这是我们不想看到的。 所以随机调整b，生成多个hash函数，并且采用或的方式组合，就可以一定程度避免这些边界点的问题。
2020-11-0164
Alan悄悄告诉大家：embedding层K值的初始判断，有个经验公式:K= Embedding维数开4次方 ,x=初始的维度数； 后续，K值调参按照2的倍数进行调整，例如：2，4，8，16；作者回复: 赞，这个我也不知道，非常感谢分享！
2021-03-03439
kaijien老师您好，您提到点数越多越应该增加桶的个数，还有Embedding维度越大越应该增加哈希函数并多用且的方式，那从您的经验上: 1 每个桶维持多少个点比较好？ 2 Embedding一般多少算大？比如768维是否应该用且的方式？应该用多少哈希函数比较好？作者回复: 1、每个桶取多少点跟你在线上想寻找top N的规模有关系。比如召回层想召回1000个物品，那么N就是1000，那么桶内点数的规模就维持在1000-5000的级别是比较合适的。当然了点数还跟你想取且还是或，有多少个哈希函数有关系，但基本上需要跟N在一个量级且高于N。 2、Embedding在实践中其实很少取768那么高的维度，我们训练模型时候的经验是，超过100维后，增加维度的作用就没那么明显了，通常取10-50维就足够了。比如说50维，这其实已经是非常高维的embedding了，我推荐用比较复杂一点的操作，比如取5个哈希函数，同时落在3+个桶里的点作为候选点。 但还是那句话，要自己观察数据，观察LSH的召回率如何，因为每家的数据都不一样，从别人那得来的经验经常不奏效是很正常的。
2020-10-31239- Alr课后思考问题：以item_id作为key， item_id对应的BucketId作为value存储在redis， 再以每个BucketId作为key， item_id作为value存储在redis， 在召回的时候遍历item_id的所有BucketId，获取BucketId对应的item_id就是需要召回的item， 请问老师这个思路对吗
作者回复: 对的。就是建立倒排索引的思路。
2020-12-2525 
浣熊当家请问老师关于这句话 “在训练物品和用户的 Embedding 向量时，如果二者的 Embedding 在同一个向量空间内”， 我们在之前6-7节embedding的中，讲了怎么把物品序列信息转化为embedding， 想知道，用户的embedding是怎么生成的呢？ 然后，物品和用户在同一个向量空间，这个是怎么得到的呢？作者回复: 好问题。在咱们的项目里，用户embedding就是通过平均这个用户评论过的高分电影的embedding得到的。 所以他们肯定是在一个向量空间里。 只要是利用用户历史的item embedding生成的用户embedding，可以说都是在一个向量空间内，这些生成方式包括但不限于average pooling，sum pooling，attention等等。
2020-10-31216
范闲LSH也有自己的问题。数据量太大的时候，hash的个数不好选择，另外存在hash冲突，容易降低召回率。 同基于树的，基于量化的，基于的图的方法来比，在召回率，速度和内存使用上都不占优势。作者回复: 没有magic嘛，各种方法都有优势，适用的数据量也不同。所以facebook在faiss里面其实是融合了多种索引方式，大家有兴趣还是推荐深入去看一下faiss的原理。
2020-12-0212- haydenlo请问对于计算距离，欧几里得距离和余弦距离等应该怎么选择？
作者回复: 根据你训练embedding时候选择的相似度来确定。 比如你训练embedding模型时就采用了欧式距离，那么这里就用欧式距离。训练模型时用了内积，这里就用内积。
2020-11-079 - Infp本人用过faiss，LSH无论是召回率还是速度方面都不是很好。基于图的HNSW或者HNSWSQ是比较好的索引方式，当然缺点是会占用较大的存储空间，还有很多其他索引方式，可参考faiss的GitHub介绍。另外，faiss的wiki里面有关于如何选择索引的指南，有需要的同学可以去了解一下：https://github.com/facebookresearch/faiss/wiki/Guidelines-to-choose-an-index。
作者回复: LSH只是ANN的一种解决方法，Faiss采用了多种索引的结构，可以扩展学习一下。
2021-07-267 - Yang Hong课后思考： 离线训练：LSH model为每个item embedding生成m个分桶，同时为每个user embedding生成m个分桶。 离线存储：1）在redis中存储item的分桶结果，key为item_id， value为item对应的BucketId；建立倒排索引，再以每个BucketId作为key， value为对应的item_id；2）在redis中存储user的分桶结果，key为user_id， value为user对应的BucketId； 在线召回：1）取出目标user的user embedding，和user对应的BucketId；2）查询redis分别获取m个BucketId对应的item_id，用且/或的多桶策略找到需要召回的item。 不知道这个思路对不对。
作者回复: user emb不用预存分桶，保存hash函数在线算就可以
2021-07-205 
JustDoDT如何精确的控制每个桶内的点的规模是 C？作者回复: 很难精确控制每个桶内的规模是C，但能通过控制桶的宽度w，来大概控制桶的规模在C附近。去掉一些噪声点后，如果点的分布比较均匀，那么每个桶的规模就比较稳定。
2020-11-015