matrix-filter.md

# 矩阵分解协同过滤推荐算法

---

# 1. 矩阵分解用于推荐算法要解决的问题

在推荐系统中，我们常常遇到的问题是这样的，我们有很多用户和物品，也有少部分用户对少部分物品的评分，我们希望预测目标用户对其他未评分物品的评分，进而将评分高的物品推荐给目标用户。比如下面的用户物品评分表：

| 用户\物品 | 物品1 | 物品2 | 物品3 | 物品4 | 物品5 | 物品6 | 物品7 |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- |
| 用户1 | 3 |  | 5 |  |  | 1 |  |
| 用户2 |  | 2 |  |  |  |  | 4 |
| 用户3 |  |  |  | 4 |  |  |  |
| 用户4 |  |  | 2 |  |  |  | 1 |
| 用户5 | 1 |  |  |  | 4 |  |  |

对于每个用户，我们希望较准确的预测出用户对未评分物品的评分。对于这个问题我们有很多解决方法，本文我们关注于用矩阵分解的方法来做。如果将m个用户和n个物品对应的评分看做一个矩阵M，我们希望通过矩阵分解来解决这个问题。

# 2. 传统的奇异值分解SVD用于推荐

说道矩阵分解，我们首先想到的就是奇异值分解SVD。在[奇异值分解\(SVD\)原理与在降维中的应用](/ml/clean-feature/svd.md)中，我们对SVD原理做了总结。如果大家对SVD不熟悉的话，可以翻看该文。

此时可以将这个用户物品对应的$$m \times n$$矩阵M进行SVD分解，并通过选择部分较大的一些奇异值来同时进行降维，也就是说矩阵M此时分解为：$$M_{m \times n}=U_{m \times k}\Sigma_{k \times k}V_{k \times n}^T$$

其中k是矩阵M中较大的部分奇异值的个数，一般会远远的小于用户数和物品数。如果我们要预测第i个用户对第j个物品的评分$$m_{ij}$$,则只需要计算$$u_i^T\Sigma v_j$$即可。通过这种方法，我们可以将评分表里面所有没有评分的位置得到一个预测评分。通过找到最高的若干个评分对应的物品推荐给用户。

可以看出这种方法简单直接，似乎很有吸引力。但是有一个很大的问题我们忽略了，就是SVD分解要求矩阵是稠密的，也就是说矩阵的所有位置不能有空白。有空白时我们的M是没法直接去SVD分解的。大家会说，如果这个矩阵是稠密的，那不就是说我们都已经找到所有用户物品的评分了嘛，那还要SVD干嘛! 的确，这是一个问题，传统SVD采用的方法是对评分矩阵中的缺失值进行简单的补全，比如用全局平均值或者用用户物品平均值补全，得到补全后的矩阵。接着可以用SVD分解并降维。

虽然有了上面的补全策略，我们的传统SVD在推荐算法上还是较难使用。因为我们的用户数和物品一般都是超级大，随便就成千上万了。这么大一个矩阵做SVD分解是非常耗时的。那么有没有简化版的矩阵分解可以用呢？我们下面来看看实际可以用于推荐系统的矩阵分解。

# 3. FunkSVD算法用于推荐

FunkSVD是在传统SVD面临计算效率问题时提出来的，既然将一个矩阵做SVD分解成3个矩阵很耗时，同时还面临稀疏的问题，那么我们能不能避开稀疏问题，同时只分解成两个矩阵呢？也就是说，现在期望我们的矩阵M这样进行分解：$$M_{m \times n}=P_{m \times k}^TQ_{k \times n}$$

我们知道SVD分解已经很成熟了，但是FunkSVD如何将矩阵M分解为P和Q呢？这里采用了线性回归的思想。我们的目标是让用户的评分和用矩阵乘积得到的评分残差尽可能的小，也就是说，可以用均方差作为损失函数，来寻找最终的P和Q。

对于某一个用户评分$$m_{ij}$$，如果用FunkSVD进行矩阵分解，则对应的表示为$$q_j^Tp_i$$，采用均方差做为损失函数，则我们期望$$(m_{ij}-q_j^Tp_i)^2$$尽可能的小，如果考虑所有的物品和样本的组合，则我们期望最小化下式：$$\sum\limits_{i,j}(m_{ij}-q_j^Tp_i)^2$$

只要我们能够最小化上面的式子，并求出极值所对应的$$p_i, q_j$$，则我们最终可以得到矩阵P和Q，那么对于任意矩阵M任意一个空白评分的位置，我们可以通过$$q_j^Tp_i$$计算预测评分。很漂亮的方法！

当然，在实际应用中，我们为了防止过拟合，会加入一个L2的正则化项，因此正式的FunkSVD的优化目标函数$$J(p,q)$$是这样的：$$arg\;min(p_i,q_j)\;\;\sum\limits_{i,j}(m_{ij}-q_j^Tp_i)^2 + \lambda(||p_i||_2^2 + ||q_j||_2^2)$$

其中$$\lambda$$为正则化系数，需要调参。对于这个优化问题，我们一般通过梯度下降法来进行优化得到结果。

将上式分别对$$p_i, q_j$$求导我们得到:

$$\frac{\partial J}{\partial p_i} = -2(m_{ij}-q_j^Tp_i)q_j + 2\lambda p_i$$

$$\frac{\partial J}{\partial q_j} = -2(m_{ij}-q_j^Tp_i)p_i + 2\lambda q_j$$

则在梯度下降法迭代时，$$p_i, q_j$$的迭代公式为：

$$p_i = p_i + \alpha((m_{ij}-q_j^Tp_i)q_j - \lambda p_i)$$

$$q_j =q_j + \alpha((m_{ij}-q_j^Tp_i)p_i - \lambda q_j)$$

通过迭代我们最终可以得到P和Q，进而用于推荐。FunkSVD算法虽然思想很简单，但是在实际应用中效果非常好，这真是验证了大道至简。

# 4. BiasSVD算法用于推荐

在FunkSVD算法火爆之后，出现了很多FunkSVD的改进版算法。其中BiasSVD算是改进的比较成功的一种算法。BiasSVD假设评分系统包括三部分的偏置因素：一些和用户物品无关的评分因素，用户有一些和物品无关的评分因素，称为用户偏置项。而物品也有一些和用户无关的评分因素，称为物品偏置项。这其实很好理解。比如一个垃圾山寨货评分不可能高，自带这种烂属性的物品由于这个因素会直接导致用户评分低，与用户无关。

假设评分系统平均分为$$\mu$$,第i个用户的用户偏置项为$$b_i$$,而第j个物品的物品偏置项为$$b_j$$，则加入了偏置项以后的优化目标函数$$J(p,q)$$是这样的$$arg\;min(p_i,q_j)\;\;\sum\limits_{i,j}(m_{ij}-\mu-b_i-b_j-q_j^Tp_i)^2 + \lambda(||p_i||_2^2 + ||q_j||_2^2+ ||b_i||_2^2+||b_j||_2^2)$$

这个优化目标也可以采用梯度下降法求解。和FunkSVD不同的是，此时我们多了两个偏执项$$b_i,b_j,p_i, q_j$$的迭代公式和FunkSVD类似，只是每一步的梯度导数稍有不同而已，这里就不给出了。而$$b_i,b_j$$一般可以初始设置为0向量，然后参与迭代。这里给出$$b_i,b_j$$的迭代方法

$$b_i = b_i + \alpha(m_{ij}-\mu-b_i-b_j-q_j^Tp_i -\lambda b_i)$$

$$b_j = b_j + \alpha(m_{ij}-\mu-b_i-b_j-q_j^Tp_i -\lambda b_j)$$

通过迭代我们最终可以得到P和Q，进而用于推荐。BiasSVD增加了一些额外因素的考虑，因此在某些场景会比FunkSVD表现好。

# 5. SVD++算法用于推荐

SVD++算法在BiasSVD算法上进一步做了增强，这里它增加考虑用户的隐式反馈。好吧，一个简单漂亮的FunkSVD硬是被越改越复杂。

对于某一个用户i，它提供了隐式反馈的物品集合定义为$$N(i)$$, 这个用户对某个物品j对应的隐式反馈修正的评分值为$$c_{ij}$$, 那么该用户所有的评分修正值为$$\sum\limits_{s \in N(i)}c_{sj}$$。一般我们将它表示为用$$q_j^Ty_s$$形式，则加入了隐式反馈项以后的优化目标函数J\(p,q\)是这样的:$$arg\;min(p_i,q_j)\;\;\sum\limits_{i,j}(m_{ij}-\mu-b_i-b_j-q_j^Tp_i - q_j^T|N(i)|^{-1/2}\sum\limits_{s \in N(i)}y_{s})^2+ \lambda(||p_i||_2^2 + ||q_j||_2^2+ ||b_i||_2^2 + ||b_j||_2^2 + \sum\limits_{s \in N(i)}||y_{s}||_2^2)$$

其中，引入$$|N(i)|^{-1/2}$$是为了消除不同$$|N(i)|$$个数引起的差异。式子够长的，不过需要考虑用户的隐式反馈时，使用SVD++还是不错的选择。

# 6. 矩阵分解推荐方法小结

FunkSVD将矩阵分解用于推荐方法推到了新的高度，在实际应用中使用也是非常广泛。当然矩阵分解方法也在不停的进步，目前张量分解和分解机方法是矩阵分解推荐方法今后的一个趋势。

对于矩阵分解用于推荐方法本身来说，它容易编程实现，实现复杂度低，预测效果也好，同时还能保持扩展性。这些都是它宝贵的优点。当然，矩阵分解方法有时候解释性还是没有基于概率的逻辑回归之类的推荐算法好，不过这也不影响它的流形程度。小的推荐系统用矩阵分解应该是一个不错的选择。大型的话，则矩阵分解比起现在的深度学习的一些方法不占优势。