1、奇异值分解SVD

1.1 传统奇异值分解SVD

对于 $m\times n$ 矩阵 $M$ 进行SVD分解，把矩阵 $M$ 分解为： $M_{m\times n}=U_{m\times k}\Sigma _{k\times k}V^T_{k\times n}$

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

可以看出这种方法简单直接。但是有一个很大的问题我们忽略了，就是SVD分解要求矩阵是稠密的，也就是说矩阵的所有位置不能有空白。所以传统的SVD实际上在推荐系统中还是比较难用的。

1.2 FunkSVD

前面说到，传统的SVD要求的矩阵是稠密的。那么我们现在要解决的问题就是避开矩阵稀疏的问题。

FunkSVD是将矩阵 $M$ 分解为两个矩阵 $(P,Q)$ ，这里采用了线性回归的思想。我们的目标是让用户的评分和用矩阵乘积得到的评分残差尽可能的小，也就是说，可以用均方差作为损失函数，来寻找最终的 $(P,Q)$ 。

对于某一个用户评分 $m_{ij}$ ，用FunkSVD分解，则对应的表示为 $q^T_jp_i$ ，采用均方差做为损失函数，则我们期望均方差尽可能小： $\sum_{i,j}(m_{ij}-q^T_jp_i)^2$

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

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

将上式分别对 $p_i,q_j$ 求导，然后利用梯度下降法迭代， $p_i,q_j$ 的迭代公式如下：

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

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

还有许多基于FunkSVD的方法进行改进的，例如BiasSVD、SVD++等，这里就不细说了。

1.3 FunkSVD小结

在很多推荐场景中，我们都是基于现有的用户和商品之间的一些数据，得到用户对所有商品的评分，选择高分的商品推荐给用户，funkSVD算法的做法最基本的做法，使用起来十分有效，而且模型的可扩展性也非常优秀，其基本思想也能广泛运用于各种场景中。并且对于相似度计算方法的选择，有多种相似度计算方法，每种都有对应优缺点，可针对不同场景使用最适合的相似度计算方法。由于funkSVD时间复杂度高，训练速度较慢，可以使用梯度下降等机器学习相关方法来进行近似计算，以减少时间消耗。

参考：https://www.cnblogs.com/pinard/p/6351319.html

https://zhuanlan.zhihu.com/p/34497989

https://blog.csdn.net/syani/article/details/52297093

2、贝叶斯个性化排序(Bayesian Personalized Ranking,BPR)

2.1 BPR使用场景

在有些推荐场景中，我们是为了在千万级别的商品中推荐个位数的商品给用户，此时，我们更关心的是用户来说，哪些极少数商品在用户心中有更高的优先级，也就是排序更靠前。也就是说，我们需要一个排序算法，这个算法可以把每个用户对应的所有商品按喜好排序。BPR就是这样的一个我们需要的排序算法。

2.2 BPR算法流程

在BPR算法中，我们将任意用户 $u$ 对应的物品进行标记，如果用户 $u$ 在同时有物品 $i$ 和 $j$ 的时候点击了 $i$ ，那么我们就得到了一个三元组 $<u,i,j>$ ，它表示对用户 $u$ 来说， $i$ 的排序要比 $j$ 靠前

下面简要总结下BPR的算法训练流程：

输入：训练集D三元组，梯度步长 $\alpha$ ，正则化参数 $\lambda$ ,分解矩阵维度 $k$ 。

输出：模型参数，矩阵W,H

1. 随机初始化矩阵 $W,H$

2. 迭代更新模型参数：

$w_{uf}=w_{uf}+\alpha (\sum_{(u,i,j)\in D}\frac{1}{1+e^{\bar{x} _{ui}-\bar{x} _{uj}}} (h_{if}-f_{jf})+\lambda w_{uf})$

$h_{if}=h_{if}+\alpha (\sum_{(u,i,j)\in D}\frac{1}{1+e^{\bar{x} _{ui}-\bar{x} _{uj}}} w_{uf}+\lambda h_{if})$

$h_{jf}=h_{jf}+\alpha (\sum_{(u,i,j)\in D}\frac{1}{1+e^{\bar{x} _{ui}-\bar{x} _{uj}}} (-w_{uf})+\lambda h_{jf})$

3.如果 $W,H$ 收敛，则算法结束，输出 $W,H$ ，否则回到步骤2.

当我们拿到 $W,H$ 后，就可以计算出每一个用户 $u$ 对应的任意一个商品的排序分： $\bar{x} _{ui}=w_u\bullet h_i$ ，最终选择排序分最高的若干商品输出。

2.3 BPR小结

BPR是基于矩阵分解的一种排序算法，但是和funkSVD之类的算法比，它不是做全局的评分优化，而是针对每一个用户自己的商品喜好分贝做排序优化。因此在迭代优化的思路上完全不同。同时对于训练集的要求也是不一样的，funkSVD只需要用户物品对应评分数据二元组做训练集，而BPR则需要用户对商品的喜好排序三元组做训练集。

参考：https://www.cnblogs.com/pinard/p/9128682.html

3、交替最小二乘法ALS（alternating least squares）

3.1 ALS基本原理

ALS是交替最小二乘的简称。在机器学习中，ALS特指使用交替最小二乘求解的一个协同推荐算法。如：将用户（user）对商品（item）的评分矩阵分解成2个矩阵：user对item 潜在因素的偏好矩阵(latent factor vector)，item潜在因素的偏好矩阵。

假设有m个user和n个item，所以评分矩阵为R。ALS(alternating least squares)希望找到2个比较低纬度的矩阵（X和Y）来逼近这个评分矩阵R。

ALS的核心就是这样一个假设：打分矩阵是近似低秩的。换句话说，就是一个 $m*n$ 的打分矩阵可以由分解的两个小矩阵 $U（m*k）$ 和 $V（k*n）$ 的乘积来近似。这就是ALS的矩阵分解方法。

3.2 ALS算法及流程

为了让X和Y相乘能逼近R，因此我们需要最小化损失函数(loss function)，因此需要最小化损失函数，在此定义为平方误差和(Mean square error, MSE)。

$Loss(X,Y)=\sum_{i,u}(r_{ui}-x_uy^T_i)^2$

一般损失函数都会需要加入正则化项(Regularization item)来避免过拟合的问题，通常是用L2，所以目标函数会被修改为：

$Loss(X,Y)=\sum_{i,u}(r_{ui}-x_uy^T_i)^2+\lambda (\sum_{u}||x_u||^2)+\lambda (\sum_{u}||y_i||^2)$

上面介绍了“最小二乘（最小平方误差）”，但是还没有讲清楚“交替”是怎么回事。因为X和Y都是未知的参数矩阵，因此我们需要用“交替固定参数”来对另一个参数求解。

先固定Y, 将loss function对X求偏导，使其导数等于0：

再固定X, 将loss function对Y求偏导，使其导数等于0：

然后进行迭代。

具体流程如下：

3.3 ALS小结

在实际应用中，由于待分解的矩阵常常是非常稀疏的，与SVD相比，ALS能有效的解决过拟合问题。基于ALS的矩阵分解的协同过滤算法的可扩展性也优于SVD。与随机梯度下降的求解方式相比，一般情况下随机梯度下降比ALS速度快；但有两种情况ALS更优于随机梯度下降：（1）当系统能够并行化时，ALS的扩展性优于随机梯度下降法。（2）ALS-WR能够有效的处理用户对商品的隐式反馈的数据。

但是ALS算法是无法准确评估新加入的用户或商品。这个问题也被称为冷启动问题。

参考：https://flashgene.com/archives/46364.html

https://flashgene.com/archives/52522.html

https://lumingdong.cn/recommendation-algorithm-based-on-matrix-decomposition.html#ALS

4、非负矩阵分解（NMF，Non-negative Matrix Factorization）

4.1 NMF约束

非负矩阵分解(Non-negative Matrix Factorization，NMF)算法，即NMF是在矩阵中所有元素均为非负数约束条件之下的矩阵分解方法。NMF中要求原始的矩阵V的所有元素的均是非负的，并且矩阵V可以分解出的两个小矩阵也是非负的，

4.2 NMF算法流程

给定一个打分矩阵R，NMF的目标是求解两个非负秩矩阵 $W,H$ 最小化目标函数如下：

计算 $W,H$ 的梯度如下：

其中：

采用梯度下降的参数优化方式, 可得W以及H的更新迭代方式见下式：

在矩阵分解基础上，加入了隐向量的非负限制。然后使用非负矩阵分解的优化算法求解。

4.3 NMF小结

要用NMF做矩阵分解有一个很大的前提——用户item之间的评分矩阵要求是非负并且分解出的小矩阵也要满足非负约束。NMF分解是对原矩阵的近似还原分解，其存在的问题和ALS相像，对于未知的评分预测相当不准确。

参考：https://flashgene.com/archives/52522.html

http://tripleday.cn/2017/01/12/sparse-nmf/

5、带权正则矩阵分解（WRMF）

5.1 WRMF使用场景

在有些场景下，虽然没有得到用户具体的评分，但是能够得到一些类似于“置信度”的信息（也称为隐式反馈信息），例如用户的游戏时长、观看时长等数据。虽然时长信息不能直接体现用户的喜好，但是能够说明用户喜欢的概率更大。在此场景下，用户-物品记录可以表示为一个置信度 $r_{ui}$ 和一个0-1指示量 $p_{ui}$ （用户-物品是否有交互），如果用户-物品没有交互，那么置信度就为0。

5.2 WRMF原理

“带权”就是根据置信度计算每条记录对应损失的权重，优化的目标函数如下：

权重通过置信度计算得到，可以使用 $c_{ui}=1+\alpha log(1+r_{ui}/\epsilon )$ 。由于未发生的交互也存在于损失函数中，因此惯用的随机梯度下降存在性能问题，为此采用ALS来优化模型，因此训练过程如下：

（1）更新每个用户的向量：

（2）更新每个物品的向量：

5.3 WRMF小结

前面除了BPR以外，我们讲的算法都是针对显式反馈的评分矩阵的，因此当数据集只有隐式反馈时，应用上述矩阵分解直接建模会存在问题。而WRMF就可以解决隐式反馈的问题。

参考：https://sine-x.com/gorse-2/

https://flashgene.com/archives/52522.html

6、总结

SVD：

基于现有的用户和商品之间的一些数据，得到用户对所有商品的评分，选择高分的商品推荐给用户，可以根据以往的评分矩阵做全局的评分优化。有多种从SVD的改进算法可选择，如：表示biasSVD、SVD++、TimesSVD等

funkSVD可以解决矩阵稀疏的问题，但是其时间复杂度高，训练速度较慢，可以使用梯度下降等机器学习相关方法来进行近似计算，以减少时间消耗。

ALS：

ALS算法和SVD的使用场景相似，也是基于用户——商品评分数据得到全局用户对商品的评分。

ALS能有效的解决过拟合问题，但是ALS算法是无法准确评估新加入的用户或商品。这个问题也被称为冷启动问题。

NMF：

要用NMF做矩阵分解有一个很大的前提——用户item之间的评分矩阵要求是非负并且分解出的小矩阵也要满足非负约束。NMF分解是对原矩阵的近似还原分解，NMF用法和SVD、ALS相似。

NMF存在的问题和ALS相像，对于未知的评分预测相当不准确。

BPR：

BPR是基于矩阵分解的一种排序算法，但是，它不是做全局的评分优化，而是针对每一个用户自己的商品喜好分贝做排序优化。因此在迭代优化的思路上完全不同。BPR需要用户对商品的喜好排序三元组做训练集。

WRMF：

当没有得到用户具体的评分，但是能够得到一些类似于隐式反馈信息时，就可使用WRMF进行矩阵分解。

最后编辑于：2019.09.30 10:43:50

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,732评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 87,496评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,264评论 0赞 338
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,807评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,806评论 5赞 368
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,675评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,029评论 3赞 399
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,683评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 41,704评论 1赞 299
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,666评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,773评论 1赞 332
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,413评论 4赞 321
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,016评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,978评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,204评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,083评论 2赞 350
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,503评论 2赞 343

推荐系统中——矩阵分解

推荐系统中——矩阵分解

1、奇异值分解SVD

1.1 传统奇异值分解SVD

1.2 FunkSVD

1.3 FunkSVD小结

2、贝叶斯个性化排序(Bayesian Personalized Ranking,BPR)

2.1 BPR使用场景

2.2 BPR算法流程

2.3 BPR小结

3、交替最小二乘法ALS（alternating least squares）

3.1 ALS基本原理

3.2 ALS算法及流程

具体流程如下：

3.3 ALS小结

4、非负矩阵分解（NMF，Non-negative Matrix Factorization）

4.1 NMF约束

4.2 NMF算法流程

4.3 NMF小结

5、带权正则矩阵分解（WRMF）

5.1 WRMF使用场景

5.2 WRMF原理

5.3 WRMF小结

6、总结

SVD：

ALS：

NMF：

BPR：

WRMF：

推荐阅读更多精彩内容

推荐系统中——矩阵分解

1、奇异值分解SVD

1.1 传统奇异值分解SVD

1.2 FunkSVD

1.3 FunkSVD小结

2、 贝叶斯个性化排序(Bayesian Personalized Ranking,BPR)

2.1 BPR使用场景

2.2 BPR算法流程

2.3 BPR小结

3、交替最小二乘法ALS（alternating least squares）

3.1 ALS基本原理

3.2 ALS算法及流程

具体流程如下：

3.3 ALS小结

4、非负矩阵分解（NMF，Non-negative Matrix Factorization）

4.1 NMF约束

4.2 NMF算法流程

4.3 NMF小结

5、带权正则矩阵分解（WRMF）

5.1 WRMF使用场景

5.2 WRMF原理

5.3 WRMF小结

6、总结

SVD：

ALS：

NMF：

BPR：

WRMF：

推荐阅读更多精彩内容

2、贝叶斯个性化排序(Bayesian Personalized Ranking,BPR)