【笔记】Recommender System:Classical RS

重新整理出来的推荐系统相关的资料；

传统的推荐系统包括：

1. 基于用户的（User-based ）推荐系统
2. 基于物品的（Item-based ）推荐系统
3. 运用PMF（Probabilistic matrix factorization）技术的推荐系统

导言

推荐系统指的是依照用户过去的信息来判断用户的喜好，并且给用户未接触过的事物打分，将分数排序后将最高者推荐给用户。这在社交媒体发达的当今社会被广泛运用。

但是推荐算法的建立中有这么经典的两大问题-Sparsity and Scalability.

稀疏性指得是可用的训练数据在矩阵形式的表现中稀疏。这个方面还能扩展到冷启动问题，指对于一个新用户该如何推荐的难题。

可扩性指得是在小规模的运算中表现很好，但是当对大数量的数据进行运算时计算成本飞速增长。

当然对这些个问题现在都有了许多针推性的研究，不过在基础部分我们介绍的就只是经典的两种模型，以及一个可以作为推荐系统里程碑的算法。

Github 上有大佬整理出了所有推荐系统相关的文章，可以通过 此处 进行拓展阅读

User-based

推荐阅读 《GroupLens An Open Architecture for Collaborative Filtering of Netnews》^[1]^

作为研究推荐系统的首几篇论文，GroupLens这篇文章更多的是在描述其系统在文章推荐的作用。不过我们的关注的点还是在算法的建立上。首先，进行基础的定义：

$U_{(i)}:$ 访问过物品 $i$ 的用户集合

$I_{(u)}:$ 用户 $u$ 访问过的物品集合

$|I_{u}|:$ 用户 $u$ 访问过的物品的个数

$r_{ui}:$ 用户 $u$ 对物品 $i$ 的打分

$R_{(u)}:$ 用户 $u$ 的打分集合

$$R_{(u)} \in \{r_{ui}\ |\ i \in I_{(u)}\}$$

$\overline{r_{u}}:$ 用户 $u$ 的所有评分的均值

$$\overline{r_{u}}=\frac{\sum\limits_{i\in I_{(u)}}r_{ui}}{|I_{(u)}|}$$

$\rho_{uj}:$ 用户 $u$ 与用户 $j$ 的相关系数

$$\begin{align} \rho_{ui}&=\frac{Cov(R_{(u)},R_{(j)})}{\sigma_{R_{(u)}}\sigma_{R_{(j)}}} \\ &=\frac{\sum\limits_{i\in I_{(u)} \cap I_{(j)}}(r_{ui}-\overline{r_{u}})(r_{ji}-\overline{r_{j}})}{\sqrt{\sum\limits_{i\in I_{(u)} \cap I_{(j)}}(r_{ui}-\overline{r_{u}})^{2}}\sqrt{\sum\limits_{i\in I_{(u)} \cap I_{(j)}}(r_{ji}-\overline{r_{j}})^{2}}} \end{align}$$

$\hat{r_{ui}}:$ 用户 $u$ 对物品 $i$ 的打分的预测值

$$\hat{r_{ui}}=\overline{r_{u}}+\frac{\sum\limits_{j\in U_{(i)}}(r_{ij}-\overline{r_{j}})\rho_{uj}}{\sum\limits_{j\in U_{(i)}}\rho_{uj}}$$

我们可以看到，定义中使用了 $\rho_{ui}$ 这个用户间的相关系数，而对未知物品的打分也最主要取决于这个值。用通俗的话来解释，如果 u 喜欢苹果，i 也喜欢苹果，那么这个相似的爱好会使两人之间的相关系数增大，当猜测 u 喜欢不喜欢梨子的时候，参考 i 的可信度也就越大。因此这个算法被称为 User-based。

Example

这是一个文章中给的例子，左边表格横轴是四个用户，纵轴是六个文章，又可以认作物品。而每个人和物品对应的值就是那个人对特定物品的评分。如果空白便是没有评分记录。如果问号便是我们待求的值。其中 K 代表 Ken，L 代表 Lee。我们可以轻松算得评分值。

但在现实中得到数据的会存在大量的空白值，导致矩阵稀疏且使结果不那么准确。同时用户的数量众多，运算量也巨大。为了减轻运算的压力，另一种模型被提出。

Item-based

推荐阅读 《Item based Collaborative Filtering Recommendation Algorithms》^[2]^

此文章不再局限于对于文字的推荐，而将视野放宽到了视频，电影，与音乐的领域。而在算法上也不再以用户间的相关系数为主，是以物品间的相关系数为主。

$U_{(i)}:$ 访问过物品 $i$ 的用户集合

$I_{(u)}:$ 用户 $u$ 访问过的物品集合

$|U_{(i)}|:$ 访问过物品 $i$ 的用户的个数

$r_{ui}:$ 用户 $u$ 对物品 $i$ 的打分

$R_{(i)}:$ 物品 $i$ 的打分集合

$$R_{(i)} \in \{r_{ui}\ |\ u \in U_{(i)}\}$$

$\overline{r_{i}}:$ 物品 $i$ 的所有评分的均值

$$\overline{r_{i}}=\frac{\sum\limits_{u\in U_{(i)}}r_{ui}}{|U_{(i)}|}$$

$\rho_{ki}:$ 物品 $k$ 与物品 $i$ 的相关系数

$$\begin{align} \rho_{ki}&=\frac{Cov(R_{(k)},R_{(i)})}{\sigma_{R_{(k)}}\sigma_{R_{(i)}}} \\ \quad&=\frac{\sum\limits_{u\in U_{(k)} \cap U_{(i)}}(r_{ui}-\overline{r_{i}})(r_{uk}-\overline{r_{k}})}{\sqrt{\sum\limits_{u\in U_{(k)} \cap U_{(i)}}(r_{uk}-\overline{r_{k}})^{2}}\sqrt{\sum\limits_{u\in U_{(k)} \cap U_{(i)}}(r_{ui}-\overline{r_{i}})^{2}}} \end{align}$$

$\hat{r_{ui}}:$ 用户 $u$ 对物品 $i$ 的打分的预测值

$$\hat{r_{ui}}=\overline{r_{i}}+\frac{\sum\limits_{k\in I_{(u)}}(r_{uk}-\overline{r_{k}})\rho_{ki}}{\sum\limits_{k\in I_{(u)}}\rho_{ki}}$$

我们可以发现，两种算法在定义上很相似，而最大的区别就是 $\rho_{ki}$ 现在指的是物品间的相关系数。用通俗的话来解释，如果用户 u 喜欢苹果，因为梨子和苹果相似也属于水果，而坚果与苹果相差巨大，所以在评分时会更多地参考用户给梨子的评分。

作者认为，在系统中存在许多不活跃的用户，而即使是活跃的用户对物品评分的数量也仅仅占了所以物品的一小部分。因此作者将重点放在了物品的相关性上，并且提出可以预先进行相关性的判断得到一组静态的模型，来适应不断增大的用户数量。

评估

到此处最经典的两个已经被提出，而作为评估的方法在此时也有必要提及一下。Mean Absolute Error (MAE) 是一个被广泛运用的度量标准

$$MAE=\frac{\sum_{i=1}^N|p_i-q_i|}{N}$$

其中 $p_i$ 指得是真实的评分 $q_i$ 指得是预测的评分。MAE 的值越低，推荐系统的评分越准确。

Root Mean Squared Error (RMSE) 是另一种被常用的度量方法

$$RMAE=\sqrt{\frac{\sum_{i=1}^N(p_i-q_i)^2}{N}}$$

PMF

推荐阅读 《Matrix Factorization Techniques for Recommender Systems》^[3]^

Probabilistic Matrix Factorization 的方法是推荐算法研究史上的一大突破。在 Netflix Prize competition 中，Koren 第一次将这个算法带到了舞台上。比起之前的两种算法，PMF在速度与准确度上有了显著的提升，一举成为推荐系统的主流算法。

假定有 n个用户，m个物品，f个特征

$P_{n\times f}: $ user-factor matrix

$Q_{m\times f}:$ item-factor matrix

$R^f:$ 1$×$factor vector

$q_i:$ $Q$ 中物品 $i$ 所在行的向量

$p_u:$ $P$ 中用户所在的行的向量

$U_{(i)}:$ 访问过物品 $i$ 的用户集合

$I_{(u)}:$ 用户 $u$ 访问过的物品集合

$r_{ui}:$ 用户 $u$ 对物品 $i$ 的评分

$\kappa$ $:$ $\{ (u,i)|$ $r_{ui}$ is known $\}$

$|\kappa|:$ 已知的所有评分总数

$\mu:$ 所有评分的均值

$$\mu = \frac{\sum\limits_{(u,i) \in \kappa} r_{ui}}{|\kappa|}$$

$b_i:$ 物品 $i$ 的平均分与整体评分均值的偏差

$$b_i = \frac{ \sum\limits_{u \in U_{(i)}}(r_{ui} - \mu) }{ |U_{(i)}| }$$

$b_u:$ 用户 $u$ 的平均分与整体评分均值的偏差

$$b_u = \frac{ \sum\limits_{i \in I_{(u)}}(r_{ui} - \mu - b_i) }{ |I_{(u)}| }$$

$b_{ui}:$ A baseline estimate for an unknown rating

$$b_{ui} = \mu + b_i + b_u$$

$\hat{r_{ui}}:$ 用户 $u$ 对物品 $i$ 的评分的预测值

$\lambda:$ 正则化系数

$\alpha:$ 学习速率(learning rate)

$$\hat{r_{ui}} = b_{ui} + q_i^T p_u \quad (q_i,p_u \in R^f ，下同)$$ $$C(q_i, p_u, b_u, b_i) =\frac{1}{2} \sum\limits_{(u,i) \in \kappa}\{(r_{ui} - \hat{r}_{ui})^2 + \lambda(||q_i||^2 + ||p_u||^2 + b_u^2 + b_i^2)\}$$ $$||q_i||^2 = q_i^T q_i \quad ||p_u||^2 = p_u^T p_u$$

By Stochastic Gradient Descent(SGD):

$$\begin{align} error &= r_{ui} - \hat{r}_{ui} \end{align}$$ $$\begin{align} b_u :&= b_u - \triangledown C \\ &= b_u - \alpha \frac{\partial C}{\partial b_u} \\ &= b_u - \frac{\alpha}{2} (error\cdot(-2) + \lambda \cdot 2b_u) \\ &= b_u + \alpha(error - \lambda \cdot b_u) \end{align}$$ $$\begin{align} b_i :&= b_i - \triangledown C \\ &= b_i - \alpha \frac{\partial C}{\partial b_i} \\ &= b_i - \frac{\alpha}{2} (error\cdot(-2) + \lambda \cdot 2b_i) \\ &= b_i + \alpha(error - \lambda \cdot b_i) \end{align}$$ $$\begin{align} p_u :&= p_u - \triangledown C \\ &= p_u - \alpha \frac{\partial C}{\partial p_u} \\ &= p_u - \frac{\alpha}{2} (error\cdot(-2)\cdot q_i + \lambda \cdot 2p_u) \\ &= p_u + \alpha(error \cdot q_i - \lambda \cdot p_u) \end{align}$$ $$\begin{align} q_i :&= q_i - \triangledown C \\ &= q_i - \alpha \frac{\partial C}{\partial q_i} \\ &= q_i - \frac{\alpha}{2} (error\cdot(-2)\cdot p_u + \lambda \cdot 2q_i) \\ &= q_i + \alpha(error \cdot p_u - \lambda \cdot q_i) \end{align}$$

此算法的主要是将 “特征” 作为连接物品与用户评分的桥梁。作者评分矩阵 R 拆分为了 user-factor matrix 和 item-factor matrix，而每个 matrix 都包含对 f 个特征的评分，只有两个矩阵对应的特征分数都大时，最终的评分才会大。比如，《阿凡达》在科幻的特征上高分，在喜剧的特征上低分，而用户 u 偏爱科幻片，所以他在科幻的特征上高，在喜剧的特征上低。这样预测用户 u 对《阿凡达》的总体评分就会高，而其他喜剧片的分就偏低。其中，因为 P Q 矩阵的未知，需要机器学习利用历史数据结合梯度下降来进行训练得出。具体推算过程可以参考有关 MAP 的笔记。

作者还提出了后续几点改进的方向。

一是添加 Implicit Feedback ，即那些非评分分数，而是需要处理的，类似于浏览记录，购买记录等额外的信息。作者将 $N(u)$ 定义为那些用户在Implicit Feedback中提供了的所有项。$x_i$ 为用户 u 在 Implicit Feedback 中对物品 i 的偏好。另一种 Implicit Feedback 指的是已知的用户属性，如人口统计，性别，年龄，收入水平等。这些数据被包括在集合 $A(u)$ 中，$y_a$ 是一个特殊的值来描述用户的属性。最终预测公式可变为

$$\hat{r_{ui}} = b_{ui} + q_i^T[ p_u+|N(u)|^{-0.5}\sum_{i\in N(u)}x_i+\sum_{a\in A(u)}y_a]$$

另一种是考虑到时间的因素，因为人的兴趣爱好可能会随着时间而改变。因此变量从定值变成了一个与时间有关的函数

$$\hat{r_{ui}} =\mu + b_i(t) + b_u(t) + q_i^T p_u(t)$$

最后，作者考虑到了同样的评分不一定值得同样的权重与信息，因为有些物品的高分可能是短时期的广告宣传的影响，而在回过头来看，其实并不是那么优秀。因此，作者以观看节目或者购买某个物品的频率 $c_{ui}$ 作为置信度，作为优化函数的改进。

$$C(q_i, p_u, b_u, b_i) =\sum\limits_{(u,i) \in \kappa}c_{ui}(r_{ui} - \hat{r}_{ui})^2 + \lambda(||q_i||^2 + ||p_u||^2 + b_u^2 + b_i^2)$$

---

Reference

1. Resnick, P., Iacovou, N., Suchak, M., Bergstrom, P., & Riedl, J. (1994). GroupLens: an open architecture for collaborative filtering of netnews. CSCW ‘94.
2. Sarwar, B.M., Karypis, G., Konstan, J.A., & Riedl, J. (2001). Item-based collaborative filtering recommendation algorithms. WWW ‘01.
3. Koren, Y., Bell, R.M., & Volinsky, C. (2009). Matrix Factorization Techniques for Recommender Systems. Computer, 42.