协同滤波和它的子孙们
2022年Q4，在项目里接触了一些跟召回相关的工作，但坦白讲做的比较匆忙。整好最近在家带娃，空余时间比较系统地学习了一下，这篇小作文做个总结。 本文总结的算法都有一个共同的发端，就是大名鼎鼎的协同滤波（collaborative filtering，CF）算法。这个协同只看字面也看不出个所以然，维基百科的解释如下 协同过滤（collaborative filtering）是一种在推荐系统中广泛使用的技术。 该技术通过分析用户或者事物之间的相似性（“协同”），来预测用户可能感兴趣的内容并将此内容推荐给用户。 经典CF 最早的CF算法是user CF。这种算法包含两个主要步骤 对于当前用户，在所有用户中寻找与他最相似的一些用户 用相似用户对item的评价来作为当前用户对item的评价 我做的几个召回渠道也是基于CF的。如果把这个技术用在召回里，就是对于当前user，返回在与之相似的用户中受欢迎的item。这里面用户相似度的评价方式比较重要，例如通过计算两个用户交互过item的Jaccard距离来作为相似度。这种做法在用户集合很大时计算复杂度相当高。在早期的系统里，item的数量可能远远少于用户的数量，并且用户的相似度会随着用户行为的变化而变化。所以有人提出在item与item之间直接计算相似度，这种相似度相对稳定，离线计算好一个相似度关系表之后在线可以直接使用，这样就可以避免相似用户计算这个耗时的步骤，这种做法称为item CF。 矩阵分解 Matrix Factorization 上面的经典CF算法实际是个间接推荐的方法，人们发现可以从用户和item的交互历史中得到用户和item的关系，从而进行直接推荐。基本的思路是将user-item交互矩阵近似为user矩阵和item矩阵的乘积。具体来说，若用户数为N，item数为M，则交互矩阵为N*M，希望把它近似为N*K和M*K两个矩阵的乘积。K可以远小于N和M，这样相似度的计算复杂度将比jaccard大大降低。实际上也就是获得了K维的user和item的embedding。交互矩阵通常是0,1矩阵（称为implicit feedback data），上面的操作实际上要让有交互的user和item embedding之间的点积接近1，没有交互的embedding点积远离1。 以下图为例，我们获得了4个用户和5部电影的交互矩阵，右边是矩阵分解之后的结果。左边4*2的矩阵为用户矩阵，在一个二维空间对用户进行表征，上面5*2的矩阵是电影矩阵，在同一个二维空间对电影进行表征。右边的大矩阵是这两个矩阵相乘的结果，和左侧0,1矩阵是比较接近但不完全一致的（毕竟降维了）。对于一个user未交互过的item，我们可以拿user的embedding和item embedding做点积来预测用户发生交互的概率。 {: .align-center style=“width:80%”} Matrix Factorization示意图 {: .align-caption style=“text-align:center;font-size:smaller”} 这个算法实际上优化的是下面这个目标 $$ \min_{U \in \mathbb R^{m \times d},\ V \in \mathbb R^{n \times d}} |A - U V^T|_F^2. $$ 学过数值分析的话会知道矩阵分解有一些经典算法，例如SVD。但这个交互矩阵A实在是太稀疏且太大了，经典算法比较难处理，因此实用的损失函数是这样 $$ \min_{U \in \mathbb R^{m \times d},\ V \in \mathbb R^{n \times d}} \sum_{(i, j) \in \text{obs}} (A_{ij} - \langle U_{i}, V_{j} \rangle)^2 + w_0 \sum_{(i, j) \not \in \text{obs}} (\langle U_i, V_j\rangle)^2....