Matrix Factorization

Matrix Factorization 是一种协同过滤思想的方法，用于物品推荐和评分预测。

YAHOO 团队在 Netflix Prize 应用 Matrix Factorization 并取得较好的成绩，效果远超传统协同过滤方法 [1]，我们在下文详细展开介绍。

MF 可以把用户 - 物品评分矩阵分解，得到用户、物品特征矩阵：

R_{u \times i} = P_{u \times k} Q_{i \times k} ^T \\ \hat r_{ui} = q_i^T p_u

其中 R 是用户 pu 对物品 qi 的评分矩阵，P 是用户属性矩阵，Q 是物品属性矩阵。其中 k 远小于用户数 u 和物品数 i。

MF 形式上与 SVD 相近，但很少用 SVD 解决协同过滤问题的原因，是评分矩阵 R 的分布非常稀疏，通常有许多缺失值，且计算复杂度高。

Loss

为了解决评分矩阵 R 稀疏的问题，以往方法通过差值填补稀疏数据。这种方法缺点是增大数据量，可能插入错误数据。近期的论文提出，通过增加正则项解决这个问题：

Learning

Stochastic gradient descent

e_{ui} := r_{ui} - q_i^T p_u \\ q_i := q_i + \gamma (e_{ui} \cdot p_u - \lambda q_i) \\ p_u := p_u + \gamma (e_{ui} \cdot q_i - \lambda p_u)

Alternative least square

交替最小二乘法，已知 R，交替使 Q 或 P 为已知，求 P 或 Q，直到收敛。

对比

SGD 快，简单

ALS 可并行化，如 Spark 实现了 ALS 并行化算法；训练集可能不是稀疏的，用 SGD 遍历每个训练项并不可行 [2]。

实践技巧

Adding Biases

在训练数据中会有 bias，如有的热门物品评分偏高偏多、有的用户评分偏高。一阶 bias 可以表示为

其中μ\muμ 表示平均评分，bib_ib​i​​ 和 bub_ub​u​​ 表示物品 i 和用户 u 相对于平均值的偏差。

包含 bias 项的评分估计为

那么 loss 定义

Additional Input Sources

当用户评分很少，推荐系统会遇到冷启动问题。可以借助用户行为数据如（购买、浏览、收藏）、用户人口统计学数据（性别、年龄、城市），提取 implicit feedback。

如果一个用户 u 对集合 N(u) 的物品感兴趣，用户偏好可以表示为

加上 normalizing

如果一个用户符合 demographic 特征，记

综上的到评分估计项

Temporal Dynamics

为了刻画兴趣的短暂性，评分估计项可以引入时间衰减因子 t

Inputs with Varying Confidence Levels

训练集中，每个训练数据的权重或置信度通常不是相等的。比如大规模的推广，使某些物品有更高的点击量。

另外，implicit feedback 的数据，当用户行为频繁时，会有更高的权重。

综合考虑，评分估计项

Netflix Prize Competetion

更多 yahoo 团队参赛的细节，见 [1]

Reference

[1] Koren, Yehuda, Robert Bell, and Chris Volinsky. “Matrix factorization techniques for recommender systems.” Computer 42.8 (2009). pdf

[2] Y.F. Hu, Y. Koren, and C. Volinsky, “Collaborative Filtering for Implicit Feedback Datasets,” Proc. IEEE Int’l Conf. Data Mining (ICDM 08), IEEE CS Press, 2008, pp. 263-272.