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

${\min_{p,q}} {\sum_{(u,i \in \kappa)}{(r_{ui} - q_i^T p_u)^2}}$

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

${\min_{p,q}} {\sum_{(u,i \in \kappa)}{(r_{ui} - q_i^T p_u)^2} + \lambda (||q_i||^2+||p_u||^2)}$

其中 $$\kappa​$$ 是已知用户物品评分的集合。

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，直到收敛。

$R = P Q^T$

SGD v.s. ALS

SGD 快，简单

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

实践技巧

Adding Biases

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

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

其中$\mu$ 表示平均评分，$b_i$ 和 $b_u$ 表示物品 i 和用户 u 相对于平均值的偏差。

包含 bias 项的评分估计为

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

那么 loss 定义

$\min_{p,q,b} \sum_{(u,i) \in \kappa} (r_{ui} - \mu - b_u - b_i - p_u^T q_i)^2 + \lambda (||p_u||^2 + ||q_i||^2 + b_u^2 + b_i^2)$

Additional Input Sources

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

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

$\sum_{i \in N(u)}{x_i}$

加上 normalizing

$|N(u)|^0.5 \sum_{i \in N(u)}{x_i}\cdot ^{4.5}$

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

$\sum_{a \in A(u)} y_a$

综上的到评分估计项

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

Temporal Dynamics

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

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

Inputs with Varying Confidence Levels

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

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

综合考虑，评分估计项

$\min_{p,q,b} \sum_{(u,i)\in \kappa} c_{ui}(r_{ui} - \mu - b_u - b_i - p_u^T q_i)^2 + \lambda (||p_u||^2 + ||q_i||^2 + b_u^2 + b_i^2)$

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.