推荐算法之用矩阵分解做协调过滤——LFM模型

隐语义模型（Latent factor model，以下简称LFM），是推荐系统领域上广泛使用的算法。它将矩阵分解应用于推荐算法推到了新的高度，在推荐算法历史上留下了光辉灿烂的一笔。本文将对 LFM原理进行详细阐述，给出其基本算法原理。此外，还将介绍使得隐语义模型声名大噪的算法FunkSVD和在其基础上改进较为成功的BiasSVD。最后，对LFM进行一个较为全面的总结。

1. 矩阵分解应用于推荐算法要解决的问题

在推荐系统中，我们经常可能面临的场景是：现有大量用户和物品，以及少部分用户对少部分物品的评分，我们需要使用现有的用户对少部分物品的评分去推测用户对物品集中其他物品的可能的评分，从而将预测中评分高的物品推荐给用户。例如下面的用户物品评分表：

用户\物品	物品 1	物品 2	物品 3	物品 4	物品 5
用户 1	3		2
用户 2	1		2		6
用户 3		3	4	6
用户 4	1	2		5
用户 5		4	2		3

对于每个用户，我们希望较准确的预测出其对未评分物品的评分。将m个用户和n个物品的评分看做一个矩阵M，从而将矩阵分解应用到该场景，即可解决这一问题。而本文，将关注于矩阵分解用于到推荐的方法之一，即LFM算法的解决方案。

2. LFM

LFM算法的核心思想是通过隐含特征（Latent factor）联系用户和物品，该算法最早在文本挖掘领域中被提出用于找到文本的隐含语义，相关名词还有LDA和Topic Model等。

2.1 如何表示用户的偏好和物品（item）属性？

在被问到这个问题时，针对MovieLens（电影评分）数据集，你可能会说用户是否喜欢动作片，物品所属电影类型去回答。但用户对其他类型的电影的偏好程度呢？物品在其它类型所占的权重又是多少呢？就算针对现有的电影类型去表征用户偏好和物品，那么能否能够完全的表示出用户的偏好和物品属性呢？答案是不能，比如用户喜欢看成龙的电影这个偏好没法表示出来，电影由谁导演，主演是谁没法表示。但你要问我用哪些属性去表征呢？这个谁也无法给出一个很好的答案，粒度很难控制。

2.2 LFM来救场

隐语义模型较好的解决了该问题，它从数据出发，通过基于用户行为统计的自动聚类，可指定出表征用户偏好和物品的向量维度，最终得到用户的偏好向量以及物品的表征向量。LFM通过以下公式计算用户u对物品i的偏好：
\[ preference(u, i)=p^T_u q_i=\sum_f^F{p_{u,k}q_{i,k}} \]
这个公式，\(p_{u,k}\)度量了用户u的偏好和第f个隐类的关系，\(q_{i,k}\)度量了物品i和第f个隐类的关系。

那么现在，我们期望用户的评分矩阵M这样分解：
\[ M_{m*n}=P^T_{m*k}Q_{k*n} \]
那么，我们如何将矩阵分解呢？这里采用了线性回归的思想，即尽可能的让用户的评分和我们预测的评分的残差尽可能小，也就是说，可以用均方差作为损失函数来寻找最终的P和Q。考虑所有的用户和样本的组合，我们期望的最小化损失函数为：
\[ \sum_{i,j}{(m_{ij}-p_i^Tq_j)^2} \]
只要我们能够最小化上面的式子，并求出极值所对应的\(p_i\) 和\(q_j\)，则我们最终可以得到矩阵P和Q，那么对于任意矩阵M任意一个空白评分的位置，我们就可以通过\(p^T_i q_j\)计算预测评分。

2.3 FunkSVD用于推荐

上面是隐语义模型LFM的基本原理，但在实际业务中，为防止过拟合，我们常常会加入一个L2的正则化项，这也就诞生了我们的FunkSVD算法。其优化目标函数\(J(p,q)\)定义为：
\[ \underbrace{argmin}_{p_i,q_j}\sum_{i,j}{(m_{ij}-p^T_iq_j)^2+\lambda({\Arrowvert{p_i}\Arrowvert}^2_2+{\Arrowvert{q_i}\Arrowvert}^2_2)} \]
其中λ为正则化系数，需要调参。对于这个优化问题，我们一般通过梯度下降法来进行优化得到结果。

将上式分别对\(p_i\)和\(q_j\)求导我们得到：
\[ \frac{\partial{J}}{\partial{p_i}}=-2(m_{ij}-p^T_iq_j)q_j+2\lambda{p_i} \]

\[ \frac{\partial{J}}{\partial{q_j}}=-2(m_{ij}-p^T_iq_j)p_i+2\lambda{q_j} \]

则梯度下降中迭代公式为：
\[ p_i = p_i +\alpha((m_{ij}-p^T_iq_j)q_j-\lambda{p_i}) \]

\[ q_j = q_j+\alpha((m_{ij}-p^T_iq_j)p_i-\lambda{q_j}) \]

通过迭代我们最终可以得到P和Q，进而用于推荐。

为读者进一步理解，笔者实现了基于MovieLens数据集实现了该方法。代码详见github: FunkSVD算法实现

2.4 BiasSVD用于推荐

BiasSVD是FunkSVD较为成功的改进版算法。BiasSVD假设评分系统包括三部分的偏置因素：一些和用户物品无关的评分因素。用户有一些和物品无关的评分因素，称为用户偏置项。而物品也有一些和用户无关的评分因素，称为物品偏置项。这很好理解，对于乐观的用户来说，它的评分行为普遍偏高，而对批判性用户来说，他的评分记录普遍偏低，即使他们对同一物品的评分相同，但是他们对该物品的喜好程度却并不一样。同理，对物品来说，以电影为例，受大众欢迎的电影得到的评分普遍偏高，而一些烂片的评分普遍偏低，这些因素都是独立于用户或产品的因素，而和用户对产品的的喜好无关。

假设评分系统平均分为μ,第i个用户的用户偏置项为\(b_i\),而第j个物品的物品偏置项为\(b_j\)，则加入了偏置项以后的优化目标函数\(J(p_i,q_j)\)是这样的:
\[ \underbrace{argmin}_{p_i,q_j}\sum_{i,j}{(m_{ij}-p^T_iq_j-u-b_i-b_j)^2+\lambda({\Arrowvert{p_i}\Arrowvert}^2_2+{\Arrowvert{q_i}\Arrowvert}^2_2+{\Arrowvert{b_i}\Arrowvert}^2_2+{\Arrowvert{b_j}\Arrowvert}^2_2)} \]
这个优化目标也可以采用梯度下降法求解。和FunkSVD不同的是，此时我们多了两个偏执项\(b_i\)和 \(b_j\)，\(p_i\)和\(q_j\)的迭代公式和FunkSVD类似，只是每一步的梯度导数稍有不同而已。\(b_i\)和 \(b_j\)一般可以初始设置为0，然后参与迭代。迭代公式为：
\[ p_i = p_i +\alpha((m_{ij}-p^T_iq_j-u-b_i-b_j)q_j-\lambda{p_i}) \]

\[ q_j = q_j+\alpha((m_{ij}-p^T_iq_j-u-b_i-b_j)p_i-\lambda{q_j}) \]

\[ b_i=b_i+\alpha(m_{ij}-p^T_iq_j-u-b_i-b_j-\lambda{b_i}) \]

\[ b_j=b_j+\alpha(m_{ij}-p^T_iq_j-u-b_i-b_j-\lambda{b_j}) \]

通过迭代我们最终可以得到P和Q，进而用于推荐。BiasSVD增加了一些额外因素的考虑，因此在某些场景会比FunkSVD表现好。

为读者进一步理解，笔者实现了基于MovieLens数据集实现了该方法。代码详见github：BiasSVD算法实现

小结

LFM 是一种基于机器学习的方法，具有比较好的理论基础，通过优化一个设定的指标建立最优的模型。它实质上是矩阵分解应用到推荐的方法，其中FunkSVD更是将矩阵分解用于推荐方法推到了新的高度，在实际应用中使用非常广泛。当然矩阵分解方法也在不停的进步，目前矩阵分解推荐算法中分解机方法（matrix factorization, MF）使用最为广泛。

对于矩阵分解用于推荐方法本身来说，它容易编程实现，实现复杂度低，预测效果也好，同时还能保持扩展性。这些都是其宝贵的优点。但是LFM 无法给出很好的推荐解释，它计算出的隐类虽然在语义上确实代表了一类兴趣和物品，却很难用自然语言描述并生成解释展现给用户。

LFM 在建模过程中，假设有 M 个用户、 N 个物品、 K 条用户对物品的行为记录，如果是 F 个隐类，那么它离线计算的空间复杂度是 \(O(F*(M+N))\) ，迭代 S次则时间复杂度为 \(O(K * F * S)\)。当 M(用户数量)和 N(物品数量)很大时LFM相对于ItemCF和UserCF可以很好地节省离线计算的内存，在时间复杂度由于LFM会多次迭代上所以和ItemCF、UserCF没有质的差别。

同时，遗憾的是，LFM 无法进行在线实时推荐，即当用户有了新的行为后，他的推荐列表不会发生变化。而从 LFM的预测公式可以看到， LFM 在给用户生成推荐列表时，需要计算用户对所有物品的兴趣权重，然后排名，返回权重最大的 N 个物品。那么，在物品数很多时，这一过程的时间复杂度非常高，可达 \(O(M*N*F)\) 。因此， LFM 不太适合用于物品数非常庞大的系统，如果要用，我们也需要一个比较快的算法给用户先计算一个比较小的候选列表，然后再用LFM重新排名。另一方面，LFM 在生成一个用户推荐列表时速度太慢，因此不能在线实时计算，而需要离线将所有用户的推荐结果事先计算好存储在数据库中。

参考：

• 协同过滤算法总结---by刘建平
• 推荐系统实战---项亮
• 推荐算法-基于矩阵分解的CF算法实现（二）：BiasSvd

（欢迎转载，转载请注明出处。欢迎沟通交流： losstie@outlook.com）