Collaborative Filtering¶

协同过滤（Collaborative Filtering）推荐算法是最经典、最常用的召回算法。基本思想是：根据用户之前的喜好以及其他兴趣相近的用户的选择来给用户推荐物品。

基于对用户历史行为数据的挖掘发现用户的喜好偏向，并预测用户可能喜好的产品进行推荐。 一般是仅仅基于用户的行为数据（评价、购买、下载等）, 而不依赖于项的任何附加信息（物品自身特征）或者用户的任何附加信息（年龄，性别等）。

目前应用比较广泛的协同过滤算法是基于邻域的方法，主要有：

• 基于用户的协同过滤算法（UserCF）：给用户推荐和他兴趣相似的其他用户喜欢的产品。
• 基于物品的协同过滤算法（ItemCF）：给用户推荐和他之前喜欢的物品相似的物品。

不管是 UserCF 还是 ItemCF 算法，重点是计算用户与物品 (U2I) 之间或物品与物品 (I2I) 之间的相似度。

相似性度量 ¶

有一些机器学习基础我们就应该知道我们往往希望将对象转变为向量以便于从数学角度进行运算；而转变为向量的目的就是期望：更加相似的对象在向量空间中距离更近。衡量相似度的方法较大，总体大同小异。详细可以参考：

• 相似性和距离度量
• 度量类型

向量相似度 ¶

内积 ¶

杰卡德（Jaccard）相似系数 ¶

\(N(u)\) 表示用户 u 交互物品集合，显然依据用户交互物品的重合程度来表征。

余弦相似度（cosine_similarity）¶

如果对内积进行归一化，则得到向量夹角余弦值：

皮尔逊（pearsonr）相关系数 ¶

相比于余弦相似度，皮尔逊相关系数通过平均分来对某一物品的评分进行修正。

使用场景 ¶

• Jaccard 相似度表示两个集合的交集元素个数在并集中所占的比例，所以适用于隐式反馈数据（0-1）。
• 余弦相似度在度量文本相似度、用户相似度、物品相似度的时候都较为常用。
• 皮尔逊相关度，实际上也是一种余弦相似度。不过先对向量做了中心化，范围在 [-1,1]。
  • 相关度量的是两个变量的变化趋势是否一致，两个随机变量是不是同增同减。
  • 不适合用作计算布尔值向量（0-1）之间相关度。
• 标签 / 关键词匹配
  • 在追求速度、不是那么关心准确度的场景下合适
  • 使用多级标签可以一定程度提高效果

内容相似度模型 ¶

为了便于比较，我们期望将内容表征为一个数字向量以利用计算机的计算能力衡量物品之间的相似度。向量相似度在上面进行了解释，如何将物品嵌入为向量是这部分的重点。除去矩阵分解，几乎所有嵌入方法都使用到了神经网络（这些是后面的内容，与本节无关），基本架构如下：

针对对应形式内容使用对应模型进行嵌入（例如图片使用 CNN，文字使用 BERT，多种内容类型还可以将初步得到的向量拼接交给 FC 处理）得到嵌入向量。基于相似度度量（图中使用余弦相似度）构建损失函数；图中正负样本的选取有很多方式，例如基于 ItemCF（不依赖于向量）或是人工标注寻找相似笔记和无关笔记。

样本为三元组，损失函数一般使用 Triplet hinge loss

或 Triplet logistic loss:

近似最近邻 (ANN) ¶

在一个向量库 D 中，我们希望找到其中与向量 u 最近的 k 个向量 \(v \in D\)，全部都计算相似度并比较将非常慢（向量库 D 中向量数量往往非常大）；使用（近似）最近邻查找能够帮助更快寻找。

一个朴素的做法是，在向量空间中依据希望使用的相似度进行分区（例如使用余弦相似度则以原点划分扇形 / 圆锥形……），并以分区中具有代表性向量（如平均向量）作为索引 w，仅比较 u 与 w 的相似度，找到最近的 \(w_{0}\) ，从其所位于的分区中召回所有向量再逐一比较。

User/Item CF¶

一般地，我们考虑针对用户 user 如何推荐 item，提高用户的使用体验、实现平台的业务需求。

UserCF¶

基于用户的协同过滤（UserCF）：例如，我们要对用户 u 进行物品推荐，可以先找到和他有相似兴趣的其他用户。然后，将共同兴趣用户喜欢的，但用户 u 未交互过的物品推荐给 u。

对于用户 u 未交互而其他用户交互过的物品 p

1. 依据已有的共同评分物品，将 u 与其他用户 s 计算相似度 \(w_{u, s}\)
2. 依据其他用户对 p 的评分，基于相似度加权预测用户 u 的评分 \(R_{u, p}\)
3. 依据预测评分进行之后的工作

考虑到部分用户偏向于打高分 / 低分，所以减去该用户平均打分

缺点：

• 用户之间的交互重叠度可能较低
• 存储相似度矩阵的开销很大

ItemCF¶

基于用户与物品交互的稀疏性，以及在用户总数较少时可能难以找到相似用户；我们转向寻找物品之间的相似度。

1. 依据已有的共同用户，将 p 与其他物品 k 计算相似度 \(w_{p, k}\)
2. 依据目标用户对其他物品 k 的评分，基于相似度加权计算评分 \(R_{u, p}\)
3. 依据预测评分进行之后的工作

公式与上面是类似的，不再重复

算法分析 ¶

1. 泛化性差，无法将两个相似物品信息推广
2. 长尾物品被忽略：热门物品容易和大量物品相似而反复被推荐，尾部物品特征向量稀疏很少被推荐

UserCF 由于是基于用户相似度进行推荐，所以具备更强的社交特性，这样的特点非常适于用户少，物品多，时效性较强的场合。

• 比如新闻推荐场景，因为新闻本身兴趣点分散，相比用户对不同新闻的兴趣偏好，新闻的及时性，热点性往往更加重要，所以正好适用于发现热点，跟踪热点的趋势。
• 另外还具有推荐新信息的能力，更有可能发现惊喜 , 因为看的是人与人的相似性 , 推出来的结果可能更有惊喜，可以发现用户潜在但自己尚未察觉的兴趣爱好。

ItemCF 更适用于兴趣变化较为稳定的应用，更接近于个性化的推荐，适合物品少，用户多，用户兴趣固定持久，物品更新速度不是太快的场合。

• 比如推荐艺术品，音乐，电影。

Swing¶

上述基于用户和物品的协同过滤算法能在一定程度上捕捉用户与用户、物品与物品之间的相似度，但是考虑下面的情况：

用户 A 希望换新手机，故而在购物软件中搜索了“手机”；此时我们应该按照用户的需求推送手机商品项目；但是在用户购置了新手机后，短时间内 A 应该是不会再购置手机，而此时我们应该推送的是“手机”相关的附属商品（如手机壳）。它们之间的并非相似性，而是相关性，相关性通过用户的交互行为来体现。

量化相似度为：

其中 \(U_i\) 表示与 i 交互过的用户的集合；\(I_u\) 表示用户 u 交互过的物品的集合；\(w_u = \frac{1}{\sqrt{|I_{u}|}}, w_v = \frac{1}{\sqrt{|I_{v}|}}\) 表示用户 u,v 的权重（降低过于活跃的用户的影响），\(\alpha\) 是一个平滑系数。

通俗来说，若用户 u 和用户 v 之间除了购买过 i 外，还购买过商品 j ，则认为两件商品是具有某种程度上的相似的。也就是说，商品与商品之间的相似关系，是通过用户关系来传递的。为了衡量物品 i 和 j 的相似性，比较同时购买了物品 i 和 j 的用户 u 和用户 v，如果这两个用户共同购买的物品越少，即这两个用户原始兴趣不相似，但仍同时购买了两个相同的物品 i 和 j，则物品 i 和 j 的相似性越高。

Matrix Factorization (FM in recall)¶

User/Item CF 都是基于用户与物品之间的交互情况来判断相似度。如果我们能够获得更为细致的、关于用户和物品之间的统计信息——例如在电影推荐中，如果我们能够知道用户对各类电影的偏好程度（动作类、喜剧类、电影导演、年份、语言……）以及电影本身在这些方面的特征——基于内积即可判断用户对于某部电影的喜好程度。

这其实构成了用户 / 物品的隐向量，这与现在深度学习中的向量嵌入是类似的。

具体来说，对于我们希望评估的具体指标 \({a_1, a_2, \cdots, a_k}\)，我们可以

• 将 m 个用户 u 对 \(a_j\) 的偏好表示为 \(x_{u,j}\)，构成 \(k * m\) 的用户矩阵 \(P\)
• 将 n 个物品 i 的 \(a_j\) 的属性表示为 \(y_{m,j}\)，构成 \(k * n\) 的物品矩阵 \(Q\)

那么 \(P^T Q\) 就可以得到 \(m * n\) 的矩阵，矩阵的每一行表示 m 个用户对 n 部电影的评分。

但是实际上能够得到得只有稀疏的用户评分矩阵，因此通过将评分矩阵进行矩阵分解（特征值分解 EVD 或者奇异值分解 SVD），得到 \(P,Q\)。

EVD 和 SVD 面对大而稀疏的矩阵分解存在性能瓶颈，利用机器学习最优化的思想，创建分解模型，称为 Latent Factor Model(LFM)。

Funk-SVD¶

Funk-SVD 的思想很简单： 把求解上面两个矩阵的参数问题转换成一个最优化问题，可以通过训练集里面的观察值利用最小化来学习用户矩阵和物品矩阵。

1. 随机初始化一个用户矩阵和物品矩阵 \(P_0, Q_0\)，（据经验取 \(\frac{1}{\sqrt{K}}\)）获取用户和物品的初始隐语义向量 \(p_{u}, q_{i}\)
2. 以 \(\hat{r}_{ui}=p_u^Tq_i=\sum_{k=1}^Kp_{u,k}q_{i,k}\) 作为用户对物品的预测评分

3. 对于具有真实评分 \(r_{ui}\) 的数据点，计算损失函数 \(e_{ui}=r_{ui} - \hat{r}_{ui}\)，并累计计算平方误差

   \[ \mathrm{SSE}= \frac{1}{2} \sum_{u,i}e_{ui}^2= \frac{1}{2} \sum_{u,i}\left(r_{ui}-\sum_{k=1}^Kp_{u,k}q_{i,k}\right)^2 \]

4. 最小化损失（其中 K 为矩阵中非空的数据点，即具有真实用户评分的矩阵元素）

   \[ \min_{\boldsymbol{q}^*,\boldsymbol{p}^*}\frac12\sum_{(u,i)\in K}\left(\boldsymbol{r}_\mathrm{ui}-p_u^Tq_i\right)^2 \]

使用梯度下降法更新学习。为了控制模型复杂度，加入 \(L_2\) 正则化项：

BiasSVD¶

不同用户的准则不同，容易给出低分或者给出高分；不同物品本身质量不同，单纯看物品的属性并不能够说明物品值得被推荐。

为了体现用户或物品本身（而非之间的关系）导致的偏差，加入偏置项：

• \(\mu\) 表示推荐模型的整体偏置，一般用所有用户对物品的评分的均值
• \(b_u\) 表示用户 u 的偏置，一般用 u 对所有物品评分的均值
• \(b_i\) 表示物品 i 的偏置，一般用 i 收到的所有评分的均值

更新优化目标：

Other¶

其他召回通道 ¶

GeoHash 召回 ¶

在离线状态下为每一分区获取 k 项优质内容，如果用户允许获取定位，则在召回时添加这 k 篇优质内容（因为是用户兴趣无关的，所以需要内容本身质量较高；同时一般使用时间倒排）。

同城召回 ¶

也是地理召回，但是 GeoHash 依据经纬度进行划分，同城召回只是依据城市进行了划分。

作者召回 ¶

用户对同一作者作品的兴趣较高（点击、点赞、收藏）甚至关注 / 订阅了作者，那么会更偏向于召回该作者的其他作品。一般维护两个索引：用户 -> 作者, 作者 -> 作品，作品同样是时间倒排。

类似于用户之间具有相似度，作者之间也具有相似度，召回时也可能考虑相似作者的作品。相似作者可以利用 CF，例如粉丝群体相近的作者很可能较为相似。

缓存召回 ¶

对于在上一次推荐中 最后通过精排而在重排的随机抽样中被筛选掉的内容，用户对其兴趣应当是较高的，值得被缓存，再次被召回尝试。

缓存的大小是有限的，不可避免的涉及替换规则，如 FIFO，成功被曝光、多次缓存未被曝光、缓存时间过长的内容应当移出。

曝光过滤 ¶

经验表明有些物品（尤其是短视频、短文类）被重复曝光时会损害用户体验。曝光过滤即移除那些已经曝光给用户后的物品，最简单直接的方法当然是：维护用户最近的浏览记录（n 个），与召回的 r 个物品逐一匹配检查，但是时间复杂度为 O(nr)，效率低下。

Bloom filter 是一种近似算法；对于物品 i 和物品列表 \(List<Item>\)，Bloom filter 能够判断 i 是否在 \(List<Item>\) 中：

• 如果返回 false，那么 i 一定不在列表中；
• 如果返回 true，那么 i 很可能在列表中。

总体而言，会有一定的假阳性，“宁杀错不放过”。

在 Bloom filter 中，物品列表被表征为一个 m 维的二进制向量 M，并包含 k 个哈希函数用于将物品列表映射在 [0, m-1] 之间的整数。

• 在 k=3 时，Bloom filter 的三个哈希函数不是逐层使用，而是将一个物品映射到三个 bit 位；

Bloom filter 利用 k 个哈希函数，将每个物品都映射为 M 上的 k 个比特位：

• 构建时，将物品列表的所有物品映射的比特位设置为 1；
• 检索时，将待检测物品进行映射，如果 k 个位置均为 1，则认为该物品已经曝光

认为哈希函数是无序随机的，我们可以得到“误伤”的大致概率为 \(\delta\approx\left(1-\exp\left(-\frac{kn}m\right)\right)^k\)。

仅考虑“误伤率”来看，n 应该尽量小、m 应该尽量大（哈希碰撞程度低），k 的取值适中有最优值。 一般而言，我们基于期望的误伤概率 \(\delta\) 来取超参数：\(k = 1.44 \ln\left( \frac{1}{\delta} \right), m = 2n\cdot \ln\left( \frac{1}{\delta} \right)\)。

如果这对你有用的话，请给我点个star吧 ===>