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

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

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

minp,q(u,iκ)(ruiqiTpu)2+λ(qi2+pu2){\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=PQTR = P Q^T

对比

SGD 快,简单

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

实践技巧

Adding Biases

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

bui=μ+bi+bub_{ui} = \mu + b_i + b_u

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

包含 bias 项的评分估计为

r^ui=μ+bi+bu+qiTpu\hat r_{ui} = \mu + b_i + b_u + q_i^{T} p_u

那么 loss 定义

minp,q,b(u,i)κ(ruiμbubipuTqi)2+λ(pu2+qi2+bu2+bi2)\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) 的物品感兴趣,用户偏好可以表示为

iN(u)xi \sum_{i \in N(u)}{x_i}

加上 normalizing

N(u)0.5iN(u)xi4.5|N(u)|^0.5 \sum_{i \in N(u)}{x_i}\cdot ^{4.5}

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

aA(u)ya\sum_{a \in A(u)} y_a

综上的到评分估计项

r^ui=μ+bi+bu+qiT[pu+N(u)0.5iN(u)xi+aA(u)ya]\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

r^ui(t)=μ+bi(t)+bu(t)+qiTpu(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 的数据,当用户行为频繁时,会有更高的权重。

综合考虑,评分估计项

minp,q,b(u,i)κcui(ruiμbubipuTqi)2+λ(pu2+qi2+bu2+bi2)\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.

本文有帮助?