矩阵分解笔记

问题背景

矩阵分解是推荐系统中的一种重要算法，具有协同过滤的 “集体智慧”，隐语义的 “深层关系”，以及机器学习的 “以目标为导向的有监督学习”。

我们以电影评分预测这个任务为例，预测过程可以简化为用户/电影评分矩阵（User-Item评分矩阵）补全的过程。在矩阵分解中，通过获得两个最优的小矩阵，我们可以计算这两个小矩阵的乘积来表示缺失的评分。因为大矩阵有一部分是有评分的，那么只要保证大矩阵有评分的位置（实际值）与两个小矩阵相乘得到的相应位置的评分（预测值）之间的误差最小即可，其实就是一个均方误差损失，这便是模型的目标函数。

奇异值分解

理论依据

矩阵分解的思想来源于奇异值分解（singular value decomposition, SVD）。其理论如下：

假设$M$是一个$m\times n$阶矩阵，其中的元素全部属于域$K$，也就是实数域或复数域。如此则存在一个分解使得

$$M=U\Sigma V^*$$

其中$U$是$m\times m$阶酉矩阵；$\Sigma$是$m\times n$阶非负实数对角矩阵；而$V^*$，即$V$的共轭转置，是$n\times n$阶酉矩阵。这样的分解就称作$M$的奇异值分解。$\Sigma$对角线上的元素$\Sigma_{i,i}$即为$M$的奇异值。

常见的做法是将奇异值由大而小排列。如此$\Sigma$便能由$M$唯一确定了。（虽然$U$和$V$仍然不能确定。）

在矩阵$M$的奇异值分解中：

• $V$​的列组成一套对M的正交“输入”或“分析”的基向量。这些向量是$M^*M$的特征向量。
• $U$的列组成一套对M的正交“输出”的基向量。这些向量是$MM^*$的特征向量。
• $\Sigma$对角线上的元素是奇异值，可视为是在输入与输出间进行的标量的“膨胀控制”。这些是$MM^*$和$M^*M$的特征值的非负平方根，并与$U$和$V$的行向量相对应。

应用

奇异值分解本身也可以直接用来进行评分预测，我们可以把User-Item矩阵A分解为：

$$A_{m\times n}\approx U_{m\times k}\Sigma_{k\times k}V^T_{k\times n}$$

其中k是矩阵A中较大的部分奇异值的个数，一般会远远的小于用户数m和物品数n。这个近似的理论依据是前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上了。因此近似操作可以极大地减少计算量，但却可以保留大部分信息。

奇异值分解后，如果要预测第$i$个用户对于第$j$个电影的评分$a_{i,j}$，就只需要计算$u_i\Sigma v_j^T$。

问题

奇异值分解固然解决减少了预测计算量，但同时也存在着一些问题：

1. SVD分解要求矩阵是稠密的，而事实上我们在做评分预测时，矩阵往往是稀疏的，存在着大量的空白。因此，为了使用SVD，必须对矩阵中缺失的部分进行插值补全。但插值操作会增大数据量，增加了算法的复杂度；同时简单粗暴的数据填充也会导致数据的失真。
2. SVD分解的算法复杂度非常高，对于$m\times n$大小的矩阵，分解算法的时间复杂度为$O(n^2\times m+n\times m^2)$即$O(n^3)$。对于较大的数据集，这样的时间复杂度是不可接受的。

基于上述的一些问题，传统的 SVD 无法直接应用于推荐系统，因此需要进行简化。

FunkSVD

理论依据

Simon Funk在博客上公开发表了一个只考虑已有评分记录的矩阵分解方法，称为FunkSVD，也就是被Yehuda Koren称为隐语义模型的矩阵分解方法。不同于SVD分解将User-Item评分矩阵分解为3个矩阵，FunkSVD只将矩阵分解为两个矩阵：

$$R_{m\times n}=P_{m\times k}\times Q_{k\times n}$$

这样，矩阵被分解为了两个低秩的用户和物品矩阵，其实就是把用户和物品都映射到一个 k 维空间中，这个 k 维空间对应着 k 个隐因子。我们认为用户对物品的评分主要是由这些隐因子影响的，所以这些隐因子代表了用户和物品一部分共有的特征，在物品身上表现为属性特征，在用户身上表现为偏好特征。然而这些隐因子并不具有实际意义，也不一定具有非常好的可解释性，每一个维度也没有确定的标签名字，所以称这些特征为 “隐因子”。

为了将稀疏矩阵$R$分解为$P$和$Q$，需要使用机器学习算法。通过最小化用户已有评分和用矩阵乘积得到的评分残差，获得最佳的$P$、$Q$。

计算过程

不妨设用户$u$对物品$i$的评分为$r_{ui}$，经过矩阵分解投射到$k$维空间的对应的用户$u$的隐含特征向量为$p_u$，对应的物品$i$的隐含特征向量为$q_i$。那么预测评分$\hat r_{ui}=q_i^Tp_u$。

此时目标函数可以表示为：

$$J=\min _{q^*,~p^*}\frac{1}{2}\sum _{(u,i)\in K}(r_{ui}-q_i^Tp_u)^2+\lambda(||p_u||^2+||q_i||^2)$$

其中，$k$是已有评分的用户和物品对的样本集，$\lambda$是正则化系数，是超参数。

有了目标函数，我们可以通过梯度下降法来进行优化得到最终结果。

沿着随机梯度下降算法继续计算，现在对$J$求偏导：

$$\frac{\partial J}{\partial p_u}=-(r_{ui}-q_i^Tp_u)q_i+\lambda p_u\\\frac{\partial J}{\partial q_i}=-(r_{ui}-q_i^Tp_u)p_u+\lambda q_i$$

此时，$p_u$、$q_i$的迭代公式为：

$$p_u=p_u+\alpha[(r_{ui}-q_i^Tp_u)q_i-\lambda p_u]\\ q_i=q_i+\alpha[(r_{ui}-q_i^Tp_u)p_u-\lambda q_i]$$

其中，$\alpha$为训练步长。

Reference

• 基于矩阵分解的推荐算法
• 推荐系统之矩阵分解模型-原理篇