评分预测之SVD

By jyd 2013/05/22 个性化推荐 5 Comments

[toc] 用户对物品的评分行为可以表示成一个矩阵R，其中R[u][i]表示用户u对物品i的评分。可以想象，大部分用户只会对少部分物品评分，因此这个矩阵中有很多元素是空的。所以，评分预测从某种意义上来说就是填空，根据已有的用户信息来预测用户对物品的评分。

传统SVD 传统的SVD也就是直接用数学上的SVD（奇异值分解）将矩阵R分解成如下形式：R = U^{T}SV。 不过，因为R矩阵有很多元素是空的，所以需要先把矩阵R填满得到R‘，可以用平均分什么的来填。则：

R^{'} = U^{T}SV

其中U和V是两个正交矩阵【如果A^{-1} = A^{T}, 则A就是正交矩阵】，S是对角阵【除对角线上的元素外，其余的元素都是零的方阵，叫做对角矩阵】，对角线上的元素就是矩阵的奇异值。从S中选出最大的f个奇异值以及在U、V中对应的行和列，从而得到一个降维后的评分矩阵：

R^{'}_{f} = U^{T}_{f}S_{f}V_{f}

其中，R^{'}_{f}(u, i)就是用户u对物品i评分的预测值。 很显然，传统的SVD所需要的空间和时间都是很大的，假设用户10万，物品1W，则矩阵R就有10W*1W个元素，这在实际系统中是难以接受的。

Funk-SVD（LFM） 先说下Latent Factor Model（LFM），按我的理解，LFM就是加入特征这一概念，然后通过某种方式计算出用户u和每个特征的关系以及物品i和每个特征的关系【在这里，我们并不能知道特征是什么】。这样，就可以通过“用户u和每个特征的关系以及物品i和每个特征的关系”来预测用户u对物品i的得分了。LFM的预测用户u对物品i的评分公式如下：

\hat{r}_{ui} = p^{T}_{u}q_{i} = \sum_{f=1}^{F} p_{u,f}q_{i,f}

其中F表示有F个特征， p_{u,f} 则表示用户u和特征f的关系， q_{i,f} 表示物品i和特征f的关系。 SVD是把R矩阵分成三个矩阵，参考LFM，我们可以把矩阵R分解成P和Q两个维度比较低的矩阵，然后通过LFM的预测公式来预测评分。 那么如何求P和Q的值呢？ 我们先定义一个损失函数为：

C(p, q) = \sum_{(u, i) \in Train} (r_{ui} - \hat{r}_{ui})^{2} = \sum_{(u, i) \in Train} \left ( r_{ui} - \sum_{f=1}^F p_{uf}q_{if} \right )^{2}

其中 \hat{r}_{ui} 为预测评分， r_{ui} 为实际评分。 这样我们就能通过随机梯度下降来最小化损失函数，从而得到p和q矩阵。 但是，如果直接最小化上面那个损失函数可能会导致学习的过拟合，所以一般会加入一个防止过拟合的项，也叫正则项：

\lambda (|| p_u ||^2 + || q_i ||^2)

其中,λ叫做正则化参数，λ的取值对评分预测的准度有很大影响。

然后，为了方便后面的计算，我们给损失函数乘上1/2, 因此，现在的损失函数为：

C(p, q) = \frac{1}{2} \sum_{(u, i) \in Train} \left ( r_{ui} - \sum_{f=1}^F p_{uf}q_{if} \right )^{2} + \frac{1}{2} \lambda (|| p_u ||^2 + || q_i ||^2)

假设你对随机梯度下降已经了解，如果不了解，可以先搜索下。

损失函数里面有两组参数 p_{uf}和 q_{if},分别对它们求偏导，则

\frac{\partial C}{\partial p_{uf}} = - q_{if} (r_{ui} - \sum_{f=1}^F p_{uf}q_{if}) + \lambda p_{uf}

\frac{\partial C}{\partial q_{if}} = - p_{uf} (r_{ui} - \sum_{f=1}^F p_{uf}q_{if}) + \lambda q_{if}

因此，根据随机梯度下降法，可以得到如下递推公式：

p_{uf}' = p_{uf} - \alpha \frac{\partial C}{\partial p_{uf}} = p_{uf} + \alpha \left ( q_{if} (r_{ui} - \sum_{f=1}^F p_{uf}q_{if}) - \lambda p_{uf} \right )

q_{if}'= q_{if} - \alpha \frac{\partial C}{\partial q_{if}} = q_{if} + \alpha \left ( p_{uf} (r_{ui} - \sum_{f=1}^F p_{uf}q_{if}) - \lambda q_{if} \right )

其中，α为学习速率，也就是步长。

对于学习速率α以及正则化参数λ的取值也是一门学问，貌似现在大家主要都是靠多次实验，多次调整，从而得到一个较好的取值。

关于如何调整α，因为怕这篇博文太长，所以另外写了一篇。请查看http://jyd.me/resys/sgd-alpha-value/。

最后说下，矩阵p和q的初始化，从迭代公式可以看出，p和q一开始必须有值，然后迭代调整。初始化p和q的方法很多，一般是用随机数填充，而随机数和1/sqrt(F)成正比，也就是 random(0, 1)/sqrt(F). 【书上说的，因为感觉初始化对结果影响不大，所以就没去实验别的方法了】

这次就先写到这里吧，接下去再写下SVD的各种拓展。至于代码，有空再整理下发上来。对了，如果文中哪里有错，麻烦跟我说下，万分感谢O(∩_∩)O~~

参考：http://sifter.org/~simon/journal/20061211.html 参考：《推荐系统实践》

转载请注明： 转载自http://jyd.me/

本文链接地址: 评分预测之SVD

Tagged on: , , ,

5 thoughts on “评分预测之SVD”

  1. scenderut

    你好。。。求偏导那部分是不是有错。。。Puf在捐失函数中出现的次数应该训练集中用户u出现的次数吧。。。所有不考虑惩罚项求偏导的话，得到的结果应该是个累加项吧。。。Qif应该也一样。。。

    Reply ↓

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。