工业界推荐系统相关

ML Recommender System

Reference

比较系统的教学在youtube有视频: 推荐系统公开课——8小时完整版，讲解工业界真实的推荐系统

国内可以看b站的: 推荐系统公开课——8小时完整版，讲解工业界真实的推荐系统

搜推相关都会继续学习这位up的视频, blog仅做学习记录使用.

Background

Data相关

与推荐系统相关的信号多与产品有关, 举个例子: b站视频发布过后你看到一些相关视频(Impression), 你可能会点进去(Click), 你可能会看完视频(在小红书的示例中被标为ScrollToEnd), 然后点赞收藏投币评论等.

这些都是相关信号, 表示用户对相关内容是否感兴趣, 它们可以转化成训练数据, 对模型有帮助.

指标(短期指标)

  • 点击率(CTR): 点击次数 / 曝光次数
  • 点赞率: 点赞次数 / 点击次数
  • 收藏率: 收藏次数 / 点击次数
  • 转发率: 转发次数 / 点击次数
  • 阅读完成率: 完成阅读次数 / 点击次数 * \(f\) (笔记长度)

需要注意阅读完成率最后需要对笔记长度做归一化保证对长内容公平.

注意: 指标只是显示用户短期是否感兴趣, 与之对比, 内容多样性如果做得好, 用户可能更具有粘性.

北极星指标(长期指标)

  • 用户规模: 日活用户数量(DAU), 月活用户数量(MAU)
  • 消费: 人均使用推荐时长, 人均阅读数量(用户上瘾程度)
  • 发布: 发布渗透率, 人均发布量.

实验流程

离线实验 -> 小流量AB测试 -> 全流量上线

  • 离线测试即收集用户过去信息, 在历史数据上面做训练和测试, 此过程没有涉及算法和用户的交互, 也不会对用户产生负面或正面影响
  • 小流量AB测试: 挑选一部分用户做实验组, 一部分做对照组, 对比两者指标完成度, 判断是否可以全流量上线.
  • 显著优于旧策略即可以考虑全流量上线.

AB测试

举例:

  • 召回团队设计了一种GNN召回通道, 离线实验正向, 需要做AB测试来判断对线上指标影响.
  • GNN深度可能可以设置{1, 2, 3}, 我们需要AB测试来选参数

随机分桶

将n个用户随机分为b个桶, 每个桶就有 $ \frac{n}{b} $ 个用户

用哈希函数将用户ID映射为某区间内的整数, 然后将这些整数均匀分为b个桶. 比如下图选1,2,3做实验组, 4做对照组. 然后统计每个桶的业务指标, 比如DAU, CTR等, 如果某个实验组效果显著, 说明策略有效, 可以推全.

分层实验

一个产品可能包含很多部门, 大家都需要做AB实验. 假如我们将用户分10个桶, 那么最多只能开9个实验, 显然不够使用.

解决方案是分层实验: 同层互斥, 不同层正交.

  • 召回层作为单独一层, 比如GNN实验占了召回层4个桶, 那么其他召回实验就只能选其他6个桶.
  • UI层作为另外一层, 和召回层不同层, 因此还是可以使用全部10个桶.

召回层10%的用户打散分到UI层, UI层选一个桶之后只有10% * 10% = 1% 的交集.

Holdout机制

业务考核相关, 为了计算某部门对业务指标的整体提升, 我们可以取10%作为holdout桶, 部门所有AB实验使用其余90%用户, 最终考核用90%用户归一化与10%holdout做diff.

考核周期结束清除holdout推广实验从90%到100%, 重新划分用户开始下一轮周期.

反转实验

当实验策略取得显著效果, 我们希望推全, 但同时有些指标存在滞后性, 需要长期观测.

  • 保留观测好处: 观测到的指标更准确
  • 尽快推全好处: 腾出桶供其他同层实验使用, 或是基于新策略做后续开发.

反转实验解决方法: 新开一层, 留下小部分用户作为反转桶, 其他用户推全新策略.

考核周期结束清除holdout的时候依旧保留反转桶, 只将推全的策略运用到holdout上.

当反转实验完成的时候, 关闭反转实验, 清除反转桶, 真正推广新策略到全部用户.

Pipline

推荐系统的Pipline一般分为: 召回 -> 粗排 -> 精排 -> 重排

  • 召回通过不同召回通道取数据, 每个通道取几十几百, 目的是将百万级及以上数据过滤到千级.
  • 粗排: 用简单的机器学习模型打分, 按分数做排序和截断, 将千级数据过滤到百级.
  • 精排: 还是打分, 不过区别于粗排, 这里需要上模型复杂度, 怎么准确怎么来.
  • 重排: 依据精排分数和多样性随机抽样, 依据产品策略和多样性需求来重新内部排列精排结果并插入广告之类运营内容.

召回

召回通道: 协同过滤 (Collaborative Filtering), 双塔模型, 关注的作者等.

itemCF

说人话就是依据user对item的喜好程度加上item之间的相似度做推荐.

  • 用户喜欢物品1, 且物品1和物品2很相似
  • 那么用户很可能喜欢物品2

\[ \sum_j like(user, item_j) \times sim(item_j, item) \]

其中like表示user对item的喜爱程度, 比如可以用score表示

similarity

下面是一个计算相似度的例子

\[ sim(i_1, i_2) = \frac{\left| v \right|}{\sqrt{\left|{w_1}\right|\cdot\left|{w_2}\right|}} \]

其中喜欢物品$ i_1 $ 的为$ w_1 $, 喜欢物品 $ i_2 $的为 $ w_2 $, v为 $ w_1 \cap w_2 $. 不过此公式为集合形式,没考虑权重, 只有喜欢或不喜欢.

cosine similarity

也可以选择用cosine similarity

\[ sim(i_1, i_2) = \frac{\sum_{v \in V} like(v, i_1) \cdot like(v, i_2)}{\sqrt{\sum_{u_1 \in w_1}like^2(u_1, i_1)} \cdot {\sqrt{\sum_{u_2 \in w_2}like^2(u_2, i_2)}}} \]

这里like只可取0或1的时候就是上面的公式.

工业化使用

由于两两计算物品相似度是非常耗时的工作, 所以工业界采用离线计算的方式.

离线:

  • 首先记录 用户->物品 的索引, 记录每个用户最近感兴趣的物品.
  • 然后建立 物品->物品 的索引, 计算物品两两相似度, 并且取最相似的topk, 从而给定一个物品, 我们能够快速返回最相似的k个物品.

线上:

  • 给定用户ID, 通过 用户->物品 索引, 找出用户近期感兴趣物品列表(last_n)
  • 对于last_n, 我们通过 物品->物品 索引, 找出最相似的k个物品
  • 对于取回的nk个物品, 用公式计算用户对物品的感兴趣程度
  • 返回100个分数最高的物品作为召回结果

总结:

使用索引离线计算量大, 线上计算量小. 不过离线本身计算不是太复杂都是可以接受的, 主要线上必须能够迅速给出结果, 这种方式线上可以快速得到反馈, 所以能够得到使用.

Swing

类似itemCF, 不过区别的地方在于相似度计算, itemCF中物品重合用户越多表示越相似

Swing从另一个角度出发: 如果两个用户本身交集很小, 但是同时喜欢物品i和物品j, 那么说明i和j相似. 公式如下

\[ s(i, j) = \sum_{u \in U_i \cap U_j} \sum_{v \in U_i \cap U_j} \frac{1}{\alpha + \left| I_u \cap I_v \right|} \]

$ U_i $表示点击商品i的所有用户, $ I_u $表示用户u点击的所有商品, 翻译过来就是: 对于共同点击商品i,j的用户，如果用户之间共同点击的商品越少则商品 i,j 就越相似.

userCF

\[ \sum_j sim(user, user_j) \times like(user_j, item) \]

几乎和itemCF完全一致,区别在于相似度为user与user之间. 另外就是userCF中存在一个降低热门物品权重的子问题, 当某用户的相似用户集里面很多人喜欢某个热门物品的时候, 我们应该降低热门物品的权重, 比如下图就采用了 1/log(1+热门程度)这种方式来解决此问题

工业化使用流程也和itemCF很类似, 建立 用户->物品 索引和 用户->用户 索引, 然后快速返回最相似的k个用户和用户最喜欢的last_n个物品, 复杂度kn.

矩阵补充(not working)

思路非常简单: 每个user对应一个embedding, 每个item对应一个embedding, 利用内积来预测用户评分从而学习embedding.

缺点:

  1. 只利用了embedding, 其他所有信息都没有使用(比如物品的物品属性, 关键词, 地理位置等, 用户的性别,年龄,感兴趣类别等).
  2. 其次, 负样本选择也有问题: 样本曝光之后被点击算正样本是正确的, 但是不点击并不代表是用户不感兴趣, 只能算作score没有真正的正样本高,这种样本其实本身应该被算作正样本, 最起码在召回阶段应该是正样本, 在后面的精排阶段算作负样本是可以的.
  3. 训练方法只用了内积, 不如余弦相似度.
  4. 最后是作者提到的矩阵补充使用regression, 就task type而言不如classification并表示工业界一般都是classification.

工业界做法(复杂度处理)

存储: 用户可以直接存kv表, 通过查询用户k从而得到用户的embedding值v. 而item的话因为数量庞大, 所以索引构造比较复杂, 从后面的内容来看, 似乎是通过将item分扇区来建立索引了.

查找: 用户可以直接查表, 而求内积理论就需要枚举item然后获取向量然后求解. 但是这里存在问题, 如果靠枚举的话, 时间复杂度正比物品数量, 而物品的数量又特别庞大, 这是不可接受的.

Approximate Nearest Neighbor Search: Milvus, Faiss, Hnswlib等系统就支持最近邻查找.

衡量标准也有如下:

  • L2距离
  • 内积
  • 夹角余弦(cosine similarity)

假如系统不支持余弦相似度, 可以对模做归一化, 从而内积即余弦相似度.

最近邻查找就是将点在空间中划分扇区, 取扇区代表向量与目标用户求相似度, 从而知道用户与哪一个扇区相似度较高. 进而我们通过扇区找到扇区内所有点, 再枚举所有点做内积. 这样复杂度可以从 n 变成 $ \sqrt(n) $.

双塔模型

结构

类似矩阵召回, 但是是升级版. 矩阵召回直接将embedding做相似度计算, 而双塔模型则是将特征完全融合之后再求相似度.

  • id信息会扩充为embedding; 离散特征类别少用one-hot, 类别多用多种embedding; 连续变量做归一化和一些简单预处理.
  • concat之后feed到神经网络, 求出用户或者物品的表征.
  • 最后基于两个表征求余弦相似度.

训练

训练模式存在三种, pointwise, pairwise, listwise.

  1. pointwise: 独立看待每个样本, 然后做二分类. 鼓励正样本预测1, 负样本预测-1. 然后样本一般正:负=1:2或者1:3(作者原话:"我也不知道为什么但互联网大厂的人都这么做").
  2. pairwise: 正负样本每一组每一组地看. 基本思路是鼓励预测的正样本相似度大于负样本相似度; 如果cos(a, b+) - cos(a, b-) > threshold, 则我们认为没有损失. 损失函数可以用triplet hinge loss: $ L(a, b+, b-) = max\{0, cos(a, b-) + threshold - cos(a, b+)\} $, 或者换成logistic也可以, 反正能正确反应正负样本关系即可.
  3. listwise: 取一个正样本和多个负样本, 然后用softmax和crossentropy, 目标是softmax之后的正样本趋近于1, 而负样本趋近于0.

正负样本

正样本: 曝光且有点击的用户物品二元组.

问题: 少量物品会占大多数点击,导致正样本大多数是热门物品.

解决方案: 过采样冷门物品和降采样热门物品.

  • 过采样(up-sampling): 一个样本出现多次.
  • 降采样(down-sampling): 一些样本被抛弃.

负样本: 主要有三个阶段

  • 召回没被选到的 -> 简单负样本
  • 粗排和精排没有选到的 -> 困难负样本
  • 参加重排但是用户没有点击的 -> 召回阶段应该被算作正样本, 排序阶段算负样本

简单负样本:
未被召回的物品大概率是用户不感兴趣的, 而未被召回的物品约等于全体物品, 所以可以直接从全体物品抽样做负样本.

但是如果均匀抽样, 因为大部分物品都是冷门物品, 那么相当于冷门物品更容易被当作负样本, 而正样本大多数是热门物品, 这样对冷门物品不公平.

所以一般采用非均匀抽样, 目的是打压热门物品, 负样本抽样概率和热门程度相关, 比如可以用采样概率正比于点击率的0.75次方来表示.

但这种方式在batch内采样可能会出现问题: 一个batch提供的是用户和物品的二元组, 用户点击了其中一个物品而没有点击其他物品, 从而保证有n*(n-1)个简单负样本. 然而一个batch中一个物品的出现概率是正比于其点击次数的, 物品成为负样本的概率本应该正比于点击率的0.75次方, 但是这里却变成了点击率的一次方: 这导致了对热门物品惩罚过狠, 会造成偏差.

小红书采用了Sampling-bias-corrected neural modeling for large corpus item recommendations里的策略来做出调整, 具体做法如下:

  • 物品被抽样到的概率 $ p_i \propto 点击次数 $.
  • 一般用于预估用户兴趣采用的是 $ cos(a, b_i) $.
  • 做训练的时候应该调整为 $ cos(a, b_i) - logp_i $ 从而避免对热门物品的过分打压, 而等线上做召回的时候还是用 $ cos(a, b_i) $.

困难负样本:

召回阶段淘汰的物品(全体物品, 即简单负样本): 容易区分
被粗排淘汰的物品(困难负样本): 比较难区分
精排靠后的物品(困难负样本): 非常难区分

工业界做法:

混合几种负样本, 50%简单负样本, 50%是困难负样本

为什么曝光为点击不可以用作负样本

线上召回

双塔模型首先是特征提取部分, 这里分为用户特征和物品特征两部分.

其中物品特征由于计算量大, 所以我们必须选择离线计算存储的方式: 首先模型进行训练, 训练完毕之后我们把物品的特征向量存进向量数据库, 然后向量数据库建索引以方便查找. 之后线上有需求的时候直接通过索引取出物品特征.

而用户特征我们可以选择离线存储然后索引获取; 也可以选择线上直接算一个. 因为用户向量只有一个, 所以计算量不大, 线上实时计算是可以接受的. 这样做的好处是用户的兴趣随时变化的话我们也能够检测得到, 推荐效果会更好.

全量更新和增量更新

全量更新: 指的是每天一次, 在昨天的模型基础之上对昨天的新数据进行重新学习(类似LLM的全调参)

增量更新: 用户的兴趣随时会发生改变, 那么就需要实时收集线上数据做流式处理, 生成tfrecord然后对模型做增量更新(指学习embedding而不做神经网络的学习). 最后发布用户的id embedding供用户塔线上计算.

只做增量不做全量更新会导致偏差: 短时间的流式信息是没有被shuffle的, 训练效果不如全量更新时shuffle来的效果好, 其次我个人理解是全量更新除此之外还会保持神经网络对embedding层的适应, 从而使模型效果更好.

自监督学习

解决问题: 推荐系统的头部效应->即少部分物品占大部分点击, 大部分物品展少量点击->高点击物品表征学得好,低点击物品表征学得差.

带自监督学习的双塔模型基本模型还是双塔模型, 不过loss由两部分构成: 一部分是mainLoss, 另一部分是selfloss(自监督loss).

第一部分的loss是crossentropy, 如下图. 其中数据取自batch, 每个用户对应一个item, 即1对n的listwise learning.

上面这个损失函数还有点小问题, 即我们前面提到过的纠偏, 训练的时候 $ cos(a_i, b_j) $ 得换成 $ cos(a_i, b_j) - logp_j $.

第二部分是自监督学习, 具体结构如下图

具体想法就是对物品做特征变换,物品i可以生成特征bi'和bi'',物品j可以生成特征bj'和bj''.

然后我们的目标是

  1. 让物品i和物品j的特征差异尽量大.
  2. 而单个物品i经过不同特征变换的输出特征应该尽量相似.

特征变换种类:

  1. random mask: 随机挑选一些离散特征, 直接对其mask, 比如类目本来是{数码,摄影}, mask之后变成{default}.
  2. dropout: 如果物品是多值离散特征, 我们随机丢弃其中50%的值, 比如{数码,摄影}, dropout之后变成{数码}.
  3. 互补特征: 相当于把特征split为两份, 两份互不重叠.
  4. mask关联特征: mask掉一系列关联性强的特征.

对于关联特征这个仔细说一下: 我们取p(u)为u特征出现的概率, p(v)为v特征出现的概率, 那么我们可以用互信息(mutual information)来表示特征之间的关联.

\[ MI(U,V) = \sum_{u \in U} \sum_{v \in V} p(u,v) \cdot log\frac{p(u,v)}{p(u)p(v)} \]

做法: 假设有k个特征, 那么就可以构成k * k的特征矩阵, 然后我们随机选一个种子, 找到与种子最相关的k/2种特征, mask掉最相关的k/2, 然后保留剩下k/2.

好处: 比其他的特征变换效果更好

坏处: 方法复杂, 实现难度大, 不容易维护.

最终损失函数

Deep Retrieval(字节)

类似阿里的TDM. 双塔模型把物品表示为向量, 而deep retrieval把物品表示为路径, 然后线上查找用户最匹配的路径.

整体步骤如下:

  1. 给定用户特征x, 用神经网络预测用户对路径path = [a, b, c]的兴趣, 分数记为 p(path | x).
  2. 用beam search来寻找分数p(path | x)最高的s条path.
  3. 利用索引 path -> List_item来召回路径上的n个物品.
  4. 对返回的最多s*n个物品做初步排序, 然后返回分数最高的若干物品.

用户对路径的兴趣

假设路径为path = [a, b, c], 用户特征为x. 那么:

  • 给定x, 用户对节点a的兴趣为p1(a | x)
  • 给定x,a, 用户对节点b的兴趣为p2(b | a;x)
  • 给定x,a,b, 用户对节点c的兴趣为p3(c | a,b;x)

最终用户对path = [a, b, c]的兴趣为:
p(a, b, c|x) = p1(a | x) * p2(b | a;x) * p3(c | a,b;x)

注意图中神经网络是不同的神经网络, 不共享参数.

用户对路径的学习方式

首先这里为了让模型学到用户和路径的关系, 我们样本层面只用到了正样本, 即 click(user, item) = 1. 然后使用下面的思路训练神经网络

  • 假设物品可以表征为J条路径:[a1, a2, a3], ... [aj, bj, cj].
  • 用户的兴趣为 p(a, b, c|x) = p1(a | x) * p2(b | a;x) * p3(c | a,b;x)
  • 如果用户点击了物品说明用户对物品感兴趣
  • 那么就存在 $ \sum_{j=1}^{J} p(a_j, b_j, c_j | x) $ 尽可能大.
  • 所以损失函数可以用 $ loss = -log(\sum_{j=1}^{J} p(a_j, b_j, c_j | x)) $.

学习物品表征

前面说到用户的兴趣为$ p(a, b, c|x) = p_1(a | x) \times p_2(b | a;x) \times p_3(c | a,b;x) $, 我们把这个表示为 $ p(path | user) $.

那么item和path的相关性就可以表示为:

\[ score(item, path) = \sum_{user}p(path|user) \times click(user, item) \]

前面为用户对路径的兴趣, 后面为用户是否点击了物品. 然后我们依据score来选出J条路径作为item的表征.

即我们通过将user作为中介, 尝试获得item的路径表征.

loss:
即然选出了J条路径 $ \Pi = \{path_1 ... path_j\} $来作为物品表征.

那么损失函数就可以写成

\[ loss(item, \Pi) = - log(\sum_{j=1}^J score(item, path_j)) \]

即路径与物品越相关, score就越大, loss就越小.

regularization:

为了避免过多物品集中在一条path的情况, 我们加上正则项. \[ reg(path_j) = (number\,of\,items\,on\,path_j)^4. \]

其他召回通道

地理位置召回: GeoHash召回, 同城召回.

作者召回: 关注的作者, 有交互的作者, 相似的作者.

缓存召回: 设置缓存,复用前面做精排的结果. 缓存机制: 一旦成功曝光就移出缓存;超出缓存大小移除最先进入的;最多召回10次,达到后退场;最多保存3天,满3天退场.

不适合召回的模型

召回的目标是大量数据, 所以需求遍历的模型就不适合召回.

个人理解:

这个模型的神经网络需要用户和物品两边的特征输入并做前期的特征融合, 这种方法就必须线上使用神经网络跑一遍遍历, 复杂度不可接受.

对比之下双塔模型后期融合, 前期表征计算完毕可以直接存储, 需求计算相似度的时候直接依据索引取出, 复杂度仅在于相似度计算而不用线上再跑神经网络, 这才是召回应该采用的模型.

曝光过滤

一般在召回阶段做, 如果用户看过某个物品, 那么大概率用户不会想再看一遍, 所以我们要在召回阶段把重复物品筛选下去.

如果某用户看过n个物品, 本次召回k个物品, 那么暴力对比会有nk复杂度. 复杂度较大, 因此需要优化.

bloom filter

即做曝光过滤的方法之一.

方法: 其通过对物品hash然后写表的方式来做记录, 然后通过读取hash表的方式来判断是否以前存过这个物品.

因此如果bloom filter表示没记录过这个物品, 那么这个物品一定没被推过; 如果bloom filter表示这个物品以前记录过, 那么这个物品以前可能记录过也可能没记录过(存在误伤).

我们假设曝光物品集合大小为n, 二进制向量维度为m, 用了k个哈希函数. 那么bloom filter误伤的概率为

\[ \delta \approx (1 - exp(-\frac{kn}{m}))^k \]

n越大, 向量的1越多, 越容易误伤; m越大, 向量空间越大, 越不容易碰撞; k太大太小都不好, 需要取最优.

作者给出最优参数(不太清楚怎么求的, 工业化场景吧).

\[ k = 1.44 \cdot ln(\frac{1}{\delta}), m = 2n \cdot ln(\frac{1}{\delta}) \]

实际业务图

用户获取数据之后我们需要尽快写表来方便下次召回, 需要用实时流处理: 把曝光物品写kafka消息队列然后flink读取消息队列并计算物品hash并写到bloomfilter的表上.

缺点:

只能添加物品不能删除物品, 即一旦向量被写入了1就不可从1写回0, 否则会影响其他物品.

如果我们想移除一个月前的曝光物品, 让bloomfilter不记录它们了来降低误伤率, 这只能通过重新计算二进制向量来实现.