矩阵分解算法原文。

论文背景

2009年发表于IEEE旗下的Computer期刊。
　　谷歌学术引用数为7954（截至2020年12月7日）。
　　作者：Yehuda Koren, Yahoo Research
　　Robert Bell and Chris Volinsky, AT&T Labs—Research
　　DOI: 10.1109/MC.2009.263
　　PDF

Recommender System Stratrgies 推荐系统策略

两种策略：content filtering approach和collaborative filtering
　　前者需要收集外部信息，但这不容易得到。后者聚焦于用户过去的行为，相比前者精确度更高，但它有冷启动问题。相反，在冷启动问题方面，前者更优越。

协同过滤又分为neighborhood methods和latent factor models。
　　基于领域的策略又可分为基于用户和基于物品。
　　基于物品的策略基于同一个用户对相邻物品的评分对用户偏好进行评估。同一个用户给一件物品的相邻物品会打相似的评分。
　　基于用户的方法鉴定相似的用户，他们可以互相补充对方的评分信息。

LFM隐语义模型

　　意思是把特征刻画分为k个维度。如图，将刻画特征设为性别和题材类别（serious/escapist），形成一个坐标空间，每个用户和物品都在这个空间中，如果在坐标系中距离越近则说明越相似。

Matrix Factorization Methods 矩阵分解策略

一些最成功的隐语义模型是基于矩阵分解实现的。
　　矩阵分解通过从评分矩阵推断出的因子向量来刻画物品和用户。
　　优势：当显式反馈无法得到时，可以添加其它信息（比如使用隐式反馈推断用户偏好）。

A Basic Matrix Factorization Model 基本矩阵分解模型

矩阵分解模型将用户和物品映射到维度f的联合潜在因素空间，用户-物品交互在空间中使用内积建模。
　　每一个item的向量设为$q_i$，每一个用户的向量设为$p_u$。$q_i$表示item拥有的积极或消极的因子，$p_u$表示用户拥有的积极或消极的因子。两者内积可以捕捉用户u和item i之间的交互，即用户在这个item上的整体兴趣。设评分为$r_{ui}$，

$$\hat{r}_{ui} = {q_i}^T{p_u}$$

这个模型和SVD（singular value decomposition）很接近。但在协同过滤中使用SVD要用到用户-物品评分矩阵，这个矩阵稀疏性太大。如果数据不完整，SVD不能被确定。并且用少数数据尝试容易过拟合。
　　早期系统都在填补缺失评分和使评分矩阵更稠密上下功夫。但是这个运算很昂贵。因此，更多的工作聚焦在直接观察现有评分数据，并通过正则化来避免过拟合。为了学习${p_u}$和${q_i}$，使用下述公式

min_{q\*,p\*}\sum_{(u,i)∈k}({r_ui} - {p_u}^Tq_i)^2 + \lambda(||p_u||^2 + ||q_i||^2)

其中，k是(u,i)对的集合。${r_{ui}}$是未知的（训练集）。

Learning Algorithms 学习算法

使上述式子最小化的两种方法是随机梯度下降和交替最小二乘法。

Stochastic gradient descent 随机梯度下降

计算error

\begin{equation}{e_{ui}}\overset{def}{=} {r_{ui}} - {q_i}^T{p_u}\end{equation}

调参

$${q_i} \leftarrow q_i + \gamma·({e_ui}·{p_u} - \lambda · {q_i})$$

$${p_u} \leftarrow p_u + \gamma·({e_ui}·{q_i} - \lambda · {p_u})$$

该方法运行速度较快。不过在有些场景下，使用ALS优化更好。

Alternating least squares 交替最小二乘法

一般随机梯度下降比ALS简单且快。但ALS适用于两个场景，一是系统可以并行化。ALS可独立计算${q_i}$和${p_u}$。二是隐式数据情况下使用。

Adding Biases

每个用户评价严格度不同，因此引入偏置项。

$${b_{ui}} = μ + {b_i} + {b_u}$$

加了偏置项后，公式改为

$$\hat{r}_{ui} = μ + {b_i} + {b_u} + {q_i}^T{p_u}$$

四部分：全局均值、item偏置、user偏置和user-item交互。
　　系统通过最小化平方误差函数来学习：

min_{p\*,q\*,b\*}\sum_{(u,i)∈k}({r_ui} - μ - {b_u}- {b_i}-{p_u}^Tq_i)^2 + \lambda(||p_u||^2 + ||q_i||^2 + b_u^2 + b_i^2)

Additional Input Sources 额外输入资源

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

N(u)指用户u有过隐式反馈的若干个item集合。x是和item i相关的因素。$\sum_{i∈N(u)}{x_i}$表示一个用户对N(u)中的若干item的偏好刻画向量。系数代表规范化。
　　用户属性用A(u)表示，每一个用户的每一个属性对应的因素向量用$y_a$表示。$\sum_{a∈A(u)}{y_a}表示每个用户的属性集。

Temporal dynamics 时空动态

用户兴趣会发生兴趣漂移，即随着时间而变化。

$$\hat{r}_{ui}(t) = μ + b_i(t) + b_u(t) + q_i^Tp_u(t)$$

$b_i(t)$表示物品随时间变化的流行程度，$b_u(t)$表示用户评分随时间变化的严格程度，$p_u(t)$表示用户偏好随时间变化的改变程度。物品是静态的，所以$q_i$也是静态的。

Inputs with varying confidence levels 各种信任级别的输入

不是每一条评分数据的权重和信任都是一样的。为了给不同的评分以不同的信任程度，修改损失函数为

min_{p\*,q\*,b\*}\sum_{(u,i)∈k}c_{ui}({r_ui} - μ - {b_u}- {b_i}-{p_u}^Tq_i)^2 + \lambda(||p_u||^2 + ||q_i||^2 + b_u^2 + b_i^2)

$c_{ui}$为评分的信任程度。

Netflix prize competition Netflix大奖竞赛

使用矩阵分解的方法取得了第一名的成绩。

　　加的因素越多，精确度越高。

阅后总结

本文主要介绍了矩阵分解的具体算法。