深度学习推荐系统实战
王喆
Roku 推荐系统架构负责人,前 hulu 高级研究员,《深度学习推荐系统》作者
33298 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 44 讲
深度学习推荐系统实战
15
15
1.0x
00:00/00:00
登录|注册

12 | 局部敏感哈希:如何在常数时间内搜索Embedding最近邻?

参数选择建议
“或”操作
“且”操作
构建局部敏感哈希“桶”
映射高维空间到低维空间
局限性和边缘点问题
Kd-tree索引
局限性和边界情况
K-means算法
设计线上的搜索过程
存储和使用离线产生的分桶数据
局部敏感哈希的优势
聚类和索引的局限性
实际分桶操作
模型参数设置
Spark MLlib中的LSH模型
局部敏感哈希的多桶策略
局部敏感哈希的基本原理
索引方法
聚类方法
时间复杂度问题
Embedding方法在推荐系统中的应用
课后思考
小结
局部敏感哈希实践
局部敏感哈希的基本原理及多桶策略
使用“聚类”还是“索引”来搜索最近邻?
推荐系统中的“快速”Embedding最近邻搜索问题
如何在常数时间内搜索Embedding最近邻?

该思维导图由 AI 生成,仅供参考

你好,我是王喆。
在深度学习推荐系统中,我们经常采用 Embedding 召回这一准确又便捷的方法。但是,在面对百万甚至更高量级的候选集时,线性地逐一计算 Embedding 间的相似度,往往会造成极大的服务延迟。
这个时候,我们要解决的问题就是,如何快速找到与一个 Embedding 最相似的 Embedding?这直接决定了召回层的执行速度,进而会影响推荐服务器的响应延迟。
今天,我们就一起来学习一下业界解决近似 Embedding 搜索的主要方法,局部敏感哈希。

推荐系统中的“快速”Embedding 最近邻搜索问题

在深度学习推荐系统中,我们经常会使用 Embedding 方法对物品和用户进行向量化。在训练物品和用户的 Embedding 向量时,如果二者的 Embedding 在同一个向量空间内(如图 1),我们就可以通过内积、余弦、欧式距离等相似度计算方法,来计算它们之间的相似度,从而通过用户 - 物品相似度进行个性化推荐,或者通过物品 - 物品相似度进行相似物品查找。
图1 用户和电影的Embedding向量空间
假设,用户和物品的 Embeding 都在一个 维的 Embedding 空间中,物品总数为 ,那么遍历计算一个用户和所有物品向量相似度的时间复杂度是多少呢?不难算出是 。虽然这一复杂度是线性的,但物品总数 达到百万甚至千万量级时,线性的时间复杂度也是线上服务不能承受的。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

本文介绍了解决深度学习推荐系统中Embedding召回的主要方法——局部敏感哈希(LSH)。文章首先指出了线性计算Embedding间相似度导致的服务延迟问题,然后对比了使用“聚类”和“索引”来搜索最近邻的可行性,分析了它们的局限性。接着介绍了Kd-tree索引方法的弊端,以及局部敏感哈希的基本原理及多桶策略。局部敏感哈希通过简洁而高效的方法几乎完美地解决了最近邻搜索问题,为推荐系统的召回层提供了有效的解决方案。局部敏感哈希的基本思想是让相邻的点落入同一个“桶”,从而降低最近邻搜索的时间复杂度。通过内积操作构建局部敏感哈希“桶”,并介绍了多桶策略,即使用多个分桶函数来增加找到相似点的概率。文章深入浅出地解释了局部敏感哈希的原理和多桶策略,为读者提供了深度学习推荐系统中Embedding召回的解决方案。文章还提供了实践环节,利用Sparrow Recsys训练好的物品Embedding,来实现局部敏感哈希的快速搜索。通过具体的代码示例和分桶操作的效果展示,读者可以更直观地了解局部敏感哈希的应用。最后,文章总结了各种方法的优缺点,并引发了读者的思考,鼓励他们参与开源项目的贡献。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《深度学习推荐系统实战》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(42)

  • 最新
  • 精选
  • Dikiwi
    b 是 0 到 w 间的一个均匀分布随机变量,避免分桶边界固化。这是什么意思呢?是说可以通过调整b来形成另外一个一个hash函数?

    作者回复: 这是个好问题,推荐其他同学也关注。 因为如果总是固定边界,很容易让边界两边非常接近的点总是被分到两个桶里。这是我们不想看到的。 所以随机调整b,生成多个hash函数,并且采用或的方式组合,就可以一定程度避免这些边界点的问题。

    2020-11-01
    64
  • Alan
    悄悄告诉大家:embedding层K值的初始判断,有个经验公式:K= Embedding维数开4次方 ,x=初始的维度数; 后续,K值调参按照2的倍数进行调整,例如:2,4,8,16;

    作者回复: 赞,这个我也不知道,非常感谢分享!

    2021-03-03
    4
    39
  • 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-31
    2
    39
  • Alr
    课后思考问题:以item_id作为key, item_id对应的BucketId作为value存储在redis, 再以每个BucketId作为key, item_id作为value存储在redis, 在召回的时候遍历item_id的所有BucketId,获取BucketId对应的item_id就是需要召回的item, 请问老师这个思路对吗

    作者回复: 对的。就是建立倒排索引的思路。

    2020-12-25
    25
  • 浣熊当家
    请问老师关于这句话 “在训练物品和用户的 Embedding 向量时,如果二者的 Embedding 在同一个向量空间内”, 我们在之前6-7节embedding的中,讲了怎么把物品序列信息转化为embedding, 想知道,用户的embedding是怎么生成的呢? 然后,物品和用户在同一个向量空间,这个是怎么得到的呢?

    作者回复: 好问题。在咱们的项目里,用户embedding就是通过平均这个用户评论过的高分电影的embedding得到的。 所以他们肯定是在一个向量空间里。 只要是利用用户历史的item embedding生成的用户embedding,可以说都是在一个向量空间内,这些生成方式包括但不限于average pooling,sum pooling,attention等等。

    2020-10-31
    2
    16
  • 范闲
    LSH也有自己的问题。数据量太大的时候,hash的个数不好选择,另外存在hash冲突,容易降低召回率。 同基于树的,基于量化的,基于的图的方法来比,在召回率,速度和内存使用上都不占优势。

    作者回复: 没有magic嘛,各种方法都有优势,适用的数据量也不同。所以facebook在faiss里面其实是融合了多种索引方式,大家有兴趣还是推荐深入去看一下faiss的原理。

    2020-12-02
    12
  • haydenlo
    请问对于计算距离,欧几里得距离和余弦距离等应该怎么选择?

    作者回复: 根据你训练embedding时候选择的相似度来确定。 比如你训练embedding模型时就采用了欧式距离,那么这里就用欧式距离。训练模型时用了内积,这里就用内积。

    2020-11-07
    9
  • 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-26
    7
  • 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-20
    5
  • JustDoDT
    如何精确的控制每个桶内的点的规模是 C?

    作者回复: 很难精确控制每个桶内的规模是C,但能通过控制桶的宽度w,来大概控制桶的规模在C附近。去掉一些噪声点后,如果点的分布比较均匀,那么每个桶的规模就比较稳定。

    2020-11-01
    5
收起评论
显示
设置
留言
42
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部