知识卡片

操作参考卡 · 9906.l · 生成模型:Hunyuan

LSH分桶与多桶策略

理解等级:高级

局部敏感哈希(LSH)解决Embedding召回中最耗时的最近邻搜索问题。遍历计算用户与所有候选物品内积的复杂度是O(kn),在几百万候选下无法承受;LSH的思路是让相邻点落入同一个桶,搜索时只在同桶或相邻桶内进行,若每桶元素数保持在常数附近,复杂度可降到常数级。构造桶利用了一个关键性质:高维点映射到低维后,原本相近的点仍相近,原本远的点则有一定概率变近。对Embedding可用随机映射向量做内积,再用带分桶宽度和随机偏移的哈希函数分桶。为减少单点误判,用多个哈希函数同时分桶,同时落入同一桶才更可能是近邻。多桶时用「与」提高准确率、缩小候选,用「或」提高召回率、增大候选,需在两者间权衡;距离标准换成余弦相似度时改用超平面分桶。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第4章 Embedding技术在推荐系统中的应用 · 查看原书依据

      局部敏感哈希的基本思想是让相邻的点落入同一个“桶”,这样在进行最近邻搜索时,仅需要在一个桶内,或相邻的几个桶内的元素中进行搜索即可。如果保持每个桶中的元素个数在一个常数附近,就可以把最近邻搜索的时间复杂度降低到常数级别。

    参考来源

    - 位置:《深度学习推荐系统》第4章 Embedding技术在推荐系统中的应用(源文件:extracted/深度学习推荐系统/_epub-src/text/part0008_split_006.html) - 结论依据:原文4.6节从最近邻搜索的复杂度出发,给出LSH的分桶思想、降维保距依据、多哈希函数与「与/或」策略,以及余弦相似度下的超平面分桶。 - 原始内容:局部敏感哈希的基本思想是让相邻的点落入同一个“桶”,这样在进行最近邻搜索时,仅需要在一个桶内,或相邻的几个桶内的元素中进行搜索即可。如果保持每个桶中的元素个数在一个常数附近,就可以把最近邻搜索的时间复杂度降低到常数级别。