本文为阅读 MF 经典论文 Matrix Factorization Techniques for Recommender Systems 的笔记。
推荐系统算法
从推荐系统做推荐的依据，大体上可以将推荐系统分为两种：
- 基于内容
- 协同过滤
基于内容的推荐算法
对于用户，根据个人身份信息或者回答相关问题，来构造用户的特征。对于物品，则根据物品自身的内容，或属性来构造特征。例如电影，其特征可以是类型、风格、参演演员等等。有了用户信息和物品信息之后，将两者特征向量化，然后用某种策略，来给各个用户匹配合适的物品。
基于内容的推荐系统，需要较多的领域知识。用户和物品的特征需要针对不同场景来选择和设计。
协同过滤推荐算法
协同过滤算法依赖于用户过去的行为信息，过去的购买记录、点赞记录、评分等等。协同过滤类的算法往往和领域无关，因为它不直接分析用户和物品自身的属性，只是基于用户与物品之间的交互信息（用户行为）来生成推荐。
协同过滤算法又可分为两大类：
1. Neighborhood methods
这类方法会寻找相似用户或相似物品，以相似关系为依据来生成推荐。包括 Item-based CF 和 User-based CF 两类。
2. Latent factor models
latent factor models 也基于 user-item 评分矩阵，但它并不用此矩阵来计算 user 或 item 间的相似度。而是用这个矩阵找出隐因素（factors），比如在电影推荐领域，喜剧、悲剧、动作、情感等都是会影响用户是否喜欢某特征。
latent factor models 通常采用矩阵分解的方法，将 user-item 评分矩阵分解为 user 和 item 矩阵。
图片来自于 推荐系统之矩阵分解模型
user 矩阵的各行是 user 的向量表示 \(p_u\)，item 矩阵各列是 item 的向量表示 \(q_i\)。user 和 item 向量的每一维代表一种隐因子的强度。矩阵分解时可以控制 user 和 item 向量的维度，即控制隐因子的数量。
假如第一维代表的隐因子是电影的喜剧，那么 user 向量第一维的值表示该用户喜欢喜剧的程度，而 item 向量的第一维代表电影的喜剧成分的多少。
user 和 item 向量的內积就是 user 对 item 的评分，可以看出 user 和 item 向量越契合，即 item 的各种特征恰好是 user 喜欢的，那么评分就高。
\[ \hat{r}_{u i}=q_{i}^{T} p_{u} \]
矩阵分解
矩阵分解的策略有很多，常见的有 SVD (Singular Value Decomposition)，NMF (Nonnegative Matrix Factorization) 等。
因为 user-item 矩阵往往是非常稀疏的，直接采用线性代数中的矩阵分解策略是行不通的。一种想法是利用矩阵中已有的值，期望 \(q_{i}^{T} p_{u}\) 尽可能地接近这些值。得到 user 和 item 矩阵后，就可以恢复出完整的 user-item 评分矩阵，以此预测 user 对于没有评分过的 item 的评分。
这样以来矩阵分解可以转变成下面的优化问题：
\[ \min _{q^* p^*} \sum_{(u, i) \in \mathbf{K}}\left(r_{u i}-q_{i}^{T} p_{u}\right)^{2}+\lambda\left(\left\|q_{i}\right\|^{2}+\left\|p_{u}\right\|^{2}\right) \tag{1}\label{1} \]
对原评分矩阵中存在的值，希望 user 向量和 item 向量相乘后尽可能地接近该值。上式中另外加入了正则化项，防止过拟合。因为目的不单单是逼近 user-item 矩阵中存在的值，也希望能够最好地预测未知的数。
解上面的优化问题，可以使用随机梯度下降法，也可以使用交替最小二乘法。
随机梯度下降法（Stochastic gradient descent, SGD）
为了公式更短，先定义：
\[ e_{u i}=r_{u i}-q_{i}^{T} p_{u} \]
求偏导，即可得出更新公式：
\[ \begin{array}{l}{q_{i} \leftarrow q_{i}+\gamma \cdot\left(e_{u i} \cdot p_{u}-\lambda \cdot q_{i}\right)} \\ {p_{u} \leftarrow p_{u}+\gamma \cdot\left(e_{u i} \cdot q_{i}-\lambda \cdot p_{u}\right)}\end{array} \]
交替最小二乘法（Alternating least squares, ALS）
因为 \(q_i\) 和 \(p_u\) 都是未知的，前面的优化目标，公式 1 是非凸函数，不好求解。但是如果能够固定 \(q_i\) 和 \(p_u\) 中的一个，交替地更新另外一个，公式中只有一个变量，而且是二次的，优化问题就更容易得到最优解。
SGD 更容易实现且更快，但 ALS 可以并行化独立更新 \(q_i\) 和 \(p_u\)。
优化策略
相较于简单的矩阵分解，作者提出了下面四点优化策略。
Adding biases
考虑到不同用户评分严格程度不同，打分范围不同。比如有的用户对很差的电影打 6 分，对好电影一律 10 分。而有的用户对差电影会打 1 分，好电影打分 9 分。这就是用户的偏差。
另外电影本身因为某种原因，也可以存在偏差，比如因为某些流量明星的加入，很烂的电影，也可以有 6 分。
因此可以将评分值分解为 4 部分：global average，item bias，user bias 和 user-item interaction。举个例子，已知所有电影的平均评分是 3.7 分，而 Titanic 是不错的电影，会比平均分高，其 item bias 为 +0.5，另外 Joe 是一个严格的人，一向打分就偏低，存在 user bias -0.3。因此 Joe 对 Titanic 的评分为：\(3.7 + 0.5 - 0.3 + q^{T}p\)。
考虑到上面这些因素，对评分的估计为：
\[ \hat{r}_{u i}=\mu+b_{i}+b_{u}+q_{i}^{T} p_{u} \tag{2}\label{2} \]
优化目标就变成了：
\[ \begin{array}{l}{\min _{p^* , q^* , b^*} \sum_{(u, i) \in \mathrm{K}}\left(r_{u i}-\mu-b_{u}-b_{i}-p_{u}^{T} q_{i}\right)^{2}+\lambda} \\ {\left(\left\|p_{u}\right\|^{2}+\left\|q_{i}\right\|^{2}+b_{u}^{2}+b_{i}^{2}\right)}\end{array} \]
对每个用户和物品学习一个偏置项。
Additional Input Sources
推荐系统往往需要处理冷启动问题，很多用户可能只对个别物品进行了评分，这就很难得出可靠的用户向量表示。引入其他的信息能够解决这种信息较少的问题。
推荐系统可以利用隐式信息，比如用户的浏览记录、搜索记录、鼠标停留信息等，在没有足够多的明确信息（购买、评分）时，此类信息也能在一定程度上对用户进行刻画。
考虑到上面这些，作者引入用户的 implicit feedback 和 user attributes 等信息。
implicit feedback 指的是浏览记录、搜索记录等。定义 \(N(u)\) 为用户有过 implicit feedback 的 items 集合，每一个 item 对应一个向量 \(x_{i} \in R^{f}\) ，\(N(u)\) 中的 items 给用户带来的特征可以表示为：
\[ |N(u)|^{-0.5} \sum_{i \in N(u)} x_{i} \]
前面的 \(|N(u)|^{-0.5}\) 用于归一化。
另外用户自身的属性也是一个信息来源，设用户有一组特征 \(A(u)\)，每个特征用向量表示 \(y_{a} \in \mathbb{R}^{f}\)，用户的属性给用户来的特征可以表示为：
\[ \sum_{a \in A(u)} y_{a} \]
如此以来，用户对物品的评分可以表示为：
\[ \hat{r}_{u i}=\mu+b_{i}+b_{u}+q_{i}^{T}\left[p_{u}+|N(u)|^{-0.5} \sum_{i \in N(u)} x_{i}+\sum_{a \in A(u)} y_{a}\right] \]
和 \(\eqref{2}\) 比起来，就相当于 \(p_u\) 做了些调整。
Temporal dynamics
有很多因素会随时间变化，比如用户看的电影越来越多，眼光越来越刁钻，以前喜欢给电影打 4 星，现在倾向于打 3 星。引入时序信号，可以捕获到用户或物品随着时间的改变。
引入时序信号后，对 \(\hat{r}\) 的估计变为：
\[ \hat{r}_{u i}(t)=\mu+b_{i}(t)+b_{u}(t)+q_{i}^{T} p_{u}(t) \]
\(b_{i}(t)\) 是物品的 bias，它会随时间改变，比如电影刚上映时很好评如潮，后来人们越来越理智，评分渐渐变低。\(b_{u}(t)\) 是用户偏置，如前面所述，用户的品味会变化。\(p_{u}(t)\) 是用户向量，用户对各种电影的喜好会变化，比如之前喜欢看喜剧片，最近喜欢看惊悚片。\(q_i\) 是隐因素向量，因为电影的各种因素相对稳定，因此不需要加时间因子。
加入了时间维度，式中 \(b_{i}, b_{u}, p_{u}\) 就变成了和时间相关的变量了。是不是说它们在不同的时间就有不同的值呢？是不是将时间分段，每一段得到一组参数呢？详情可以参考文献1。
大体思路是，假设这些变量是随时间线性变化的，于是用一个线性模型来表示这些变量。线性模型 \(y=at+b\)，对每个变量学习一个斜率和截距，代入时间就可以得到对应时间的估计值了。
思考:
作者的这篇论文中的方法是用来评分预测的，Netflix 的比赛评估的是 RMSE，所以作者需要尽可能准确地预测缺失的值。加入时间信息，考虑到了用户品味等的变化。
这里是使用过去的部分信息，来预测过去的另一部分信息。但在实际的推荐系统中，需要用过去的数据预测未来的用户的评分。模型需要定期重新训练，以尽可能准确地预测用户在接下来的一端实际的评分。
Inputs With Varying confidence Levels
不是所有评分都有一样的权重，有些评分可能受到了广告的影响，这对刻画长期的特征贡献不大。因此，作者对每个观察到的评分引入了 confidence level，然置信度低的评分贡献小一点。如此，优化目标变为：
\[ \begin{array}{l}{\min _{p^* , q^* , b^*} \sum_{(u, i) \in K} c_{u i}\left(r_{u i}-\mu-b_{u}-b_{i}\right.} \\ {\left.-p_{u}^{T} q_{i}\right)^{2}+\lambda\left(\left\|p_{u}\right\|^{2}+\left\|q_{i}\right\|^{2}\right.} \\ {\left.+b_{u}^{2}+b_{i}^{2}\right)}\end{array} \]
实验结果
使用的数据是 Netflix 2006 年的比赛数据，作者获得了冠军，下图为上述几种算法的实验结果。图中曲线上的 50,100,200 表示 latent factor 横轴是模型参数量。根据纵轴的 RMSE 可以看出各种模型的性能。
总结
相比于最为基本的矩阵分解，本文考虑到了 bias，冷启动，特征随时间变化等事实，并将其融入到矩阵分解的策略中。本文是 Latent factor models 的经典之作，值得学习。
Y. Koren, “Collaborative Filtering with Temporal Dynamics,” Proc. 15th ACM SIGKDD Int’l Conf. Knowledge Discovery and Data Mining (KDD 09), ACM Press, 2009, pp. 447-455.↩