【王树森推荐系统】召回12:曝光过滤 Bloom Filter
概述
- 曝光过滤通常是在召回阶段做,具体的方法就是用 Bloom Filter
曝光过滤问题
- 如果用户看过某个物品,则不再把该物品曝光给用户。原因是同一个物品重复曝光给用户会损害用户体验,但也不是所有推荐系统都有曝光过滤,像 youtube 这样的长视频就没有曝光过滤,看过的也可以再次推荐
- 对于每个用户,记录已经曝光给他的物品(小红书只召回 1 个月以内的笔记,因此只需要记录每个用户最近 1 个月的曝光历史)
- 对于每个召回的物品,判断它是否已经给该用户曝光过,排除掉曾经曝光过的物品
- 一位用户看过 nnn 个物品,本次召回 rrr 个物品,如果爆力对比,需要 O(nr)O(nr)O(nr) 的时间。
- 在小红书一个月 nnn 的曝光量级大概是几千,每次推荐召回量 rrr 的量级也是几千,暴力对比的计算量太大了,所以实践中不暴力对比,而是用 Bloom Fliter
Bloom Filter
- Bloom Filter是一种数据结构,发表在 1970 年,以它的发明者命名
- 推荐系统的曝光过滤基本上都是用 Bloom Fliter 做的
- Bloom Fliter 判断要给物品ID是否已经在已曝光的物品集合中
- 如果判断为 no,那么该物品一定不在集合中
- 如果判断为 yes,那么该物品很可能在集合中(可能误伤,错误判断未曝光物品为已曝光,将其过滤掉)
- 如果用 Bloom Fliter 过滤,肯定能干掉所有已经曝光的物品,但是可能会误伤
- Bloom Fliter 把物品集合表征为一个 m 维二进制向量
- 每个用户有一个曝光物品的集合,表征为一个向量,需要 m bit 的存储
- Bloom fliter 有 k 个哈希函数,每个哈希函数把物品ID映射成介于 0 和 m-1 之间的整数
Bloom Filter (k=1)
- 初始的时候向量是全 0 的
- 我们知道用户有哪些已经曝光过的物品,如下图哈希函数把第一个物品 ID1ID_1ID1 映射为 1,所以我们将二进制的第一位映射为 1
- 第二个物品 ID2ID_2ID2 映射为了 8,所以把位置 8 的二进制位改为 1
- 哈希函数把第三个物品 ID3ID_3ID3 映射为了位置 1,这个位置的元素已经是 1 了,不需要修改这个数值
- 哈希函数把第四个物品 ID4ID_4ID4 映射到了位置 5,我们也将其置为 1
- 哈希函数把第五第六个物品都映射到了位置 5,这个位置已经是 1 了,不需要修改这个数值,到此为止我们已经把 6 个物品表征为一个向量
- 用户发起推荐请求后曝光很多物品,这里用一个之前未曝光给用户的物品,他被映射到位置 2,这个位置是 0,所以 Bloom Filter 判断这个物品之间没有被曝光
- 这个判断是正确的。如果 Bloom Filter 认为它没有被曝光,那么它肯定没被曝光,Bloom Filter 不会把已曝光的物品错判未未曝光
- 而下面又一个新来的物品已经曝光了,那么它就会被映射到之前它标记过的位置
- 对于又一个新的未曝光的物品,哈希函数把它映射到了位置 8,这个位置已经被标记为了 1,所以被认为已经曝光过了,此时错判
Bloom Filter (k=3)
- 初始全0,来了一个 ID1ID_1ID1 物品,此时有 3 个哈希函数,我们把它映射到了 3 个位置上,我们把 3 个位置都置为 1
- ID2ID_2ID2 也是一个已曝光的物品,我们还用 3 个哈希函数把它映射到 3 个位置上,把 3 个位置的都置为 1
- 现在有一个召回的物品 ID8ID_8ID8,用 3 个哈希函数把它映射到了 3 个不同的位置。假如这个物品已经曝光,那么 3 个位置肯定都是 1 了,但其中 1 个位置是 0,说明这个物品还未曝光
- 对于 ID4ID_4ID4 ,它已经被曝光,判断是正确的
- 对于未曝光的 ID9ID_9ID9 ,它映射的 3 个位置都为 1,被误判了
误伤概率分析
- 曝光物品集合大小为 nnn,二进制向量维度为 mmm,使用 kkk 个哈希函数
- nnn 越大,向量中的 1 越多,误伤的概率越大(未曝光的 kkk 个位置恰好都是 1 的概率大)
- mmm 越大,向量越长,越不容易发生哈希碰撞,需要的存储也越多
- kkk 太大,太小都不好,kkk 有最优取值
- 设定可容忍的误伤概率为 δ\deltaδ ,那么最优参数为:
- 只需要 m = 10n bit,就可以把误伤概率降低到 1% 以下
曝光过滤的链路
- 把曝光物品记录下来,反馈给召回阶段,用于过滤召回的物品
- app 的前端有埋点,所有曝光的物品都会被记录下来。这个落表的速度要足够快,否则可能会出问题
- 用户推荐页面两次刷新间隔也就几分钟,快的话也就一二十秒,在下次刷新前就得把本次曝光的结果写道 Bloom Filter 上,否则下一刷很可能会出重复的物品。
- 所以要用实时流处理,比如把曝光物品写入 Kafka 消息队列,用 Flink 做实时计算
- Flink 实时读取 Kafka 消息队列,计算曝光物品的哈希值,把结果写道 Bloom Fliter 的二进制向量上
- 用这样的实时数据链路,在曝光发生的几秒后,这位用户的 Bloom Filter 就会被修改,就可以避免重复曝光
- 但实时流这部分也是最容易出问题的,如果挂掉了或者延时特别大。那么上一刷才看过的物品又会出现
- 曝光过滤具体用在召回完成之后:召回服务器请求曝光过滤服务,曝光过滤服务把二进制向量发送给召回服务器,在召回服务器上用 Bloom Filter 计算召回的物品的哈希值,再和二进制向量做对比,把已经曝光的物品给过滤掉,发送剩余的物品给排序服务器
Bloom Filter 的缺点
- Bloom 把物品的集合表示成一个二进制向量
- 每往集合中添加一个物品,只需要把向量的 k 个位置的元素置为 1
- Bloom Filter 只支持添加物品,不支持删除物品,从集合中移除物品,无法消除它对向量的影响。因为是共享的,所以要移除的话不能简单的把它的位置都改为 0,因为有可能别的物品也在这个位置有标记
- 每天都需要从物品集合中移除年龄大于 1 个月的物品(超龄物品不可能被召回,没必要把它们记录在 Bloom Filter,降低 n 可以降低误伤率)
- 想要删除一个物品,需要计算整个集合的二进制向量