基于矩阵分解的推荐算法

1.背景

  推荐系统的两大应用场景分别是评分预测(Rating Prediction)和Top-N推荐(Item Ranking)。其中评分预测主要用于评价网站，比如用户给自己看过的电影评多少分，或者用户给自己看过的书籍评价多少分，矩阵分解技术主要应用于评分预测问题；Top-N推荐常用于购物网站或获取不到显式评分的网站，通过用户的隐式反馈为用户提供一个可能感兴趣的Item列表，此排序任务需要排序模型进行建模。本文主要介绍如何利用矩阵分解来解决评分预测问题。

2.矩阵分解概述

  协同过滤技术可划分为基于内存/邻域的协同过滤(Memory-based CF)与基于模型的协同过滤技术(Model-based CF)。这里基于模型的协同过滤技术中矩阵分解(Matrix Factorization，MF)技术最为普遍和流行，因为它的可扩展性好并且易于实现。

  矩阵分解是一种隐语义模型。隐语义模型是通过隐含特征(Latent Factor)联系用户兴趣和物品，基于用户行为的自动聚类。在评分预测问题中，收集到的用户行为评分数据可用一个评分矩阵表示，矩阵分解要做的是预测出评分矩阵中缺失的评分，使得预测评分能反映用户的喜欢程度，从而可以把预测评分最高的前K个电影推荐给用户。为了预测缺失的评分，矩阵分解学习 $User$ 矩阵和 $Item$ 矩阵，使得$User$矩阵$\ast$ $Item$矩阵​与评分矩阵中已知的评分差异最小，此时评分预测问题转化为了一个最优化问题，求解该最优化问题即可将评分矩阵分解成User矩阵和Item矩阵，从而可以计算出缺失的评分。

在评分预测问题中：

• 构建 user -item 评分矩阵(数据是稀疏的，矩阵分解就是填充缺失的评分)
• 学习 $User$ 矩阵和 $Item$ 矩阵，使得评分与矩阵中已知的评分差异最小(最优化问题)

以电影评分预测为例，用评分矩阵表示收集到的用户行为数据，12个用户，9部电影。

  对上述用户-物品评分矩阵(12×9)进行矩阵分解，得到User(12×3)矩阵和Item(3×9)矩阵。观察下图User矩阵，可知用户的观影爱好体现在User向量上，观察Item矩阵，可知电影的风格体现在Item向量上，MF用user向量和item向量的内积去拟合评分矩阵中该user对该item的评分，内积的大小反映了user对item的喜欢程度，内积越大表明用户对该电影的喜爱程度高，反之用户对该电影的喜爱程度低。这里“动作”、“动画”、“爱情”为隐含特征，隐含特征个数k越大，隐类别分得越细，计算量越大。

把User矩阵与Item矩阵相乘，就能预测每个用户对每部电影的预测评分了，评分值越大，表示用户喜欢该电影的可能性越大，该电影就越值得推荐给用户。

3.矩阵分解目标函数

在用户-物品评分矩阵 $\mathbf{R}$ 中，ruir_{ui}rui​ 表示 用户 $u$ 对 Item $i$ 的评分 , 当 rui>0r_{ui}\\ \\gt 0rui​ >0 时，表示有评分，当rui=0\\ r_{ui}\\ = 0 rui​ =0，表示没有评分。

在User矩阵 $\mathbf{X}$ 中($M\times k$，用户数为M)，xux_uxu​ 表示用户 $u$ 的向量，k维列向量。X=[x1,x2,...,xM]\\bold X=[x_1,x_2,...,x_M]X=[x1​,x2​,...,xM​]

在Item矩阵 $\mathbf{Y}$ 中($k\times N$，物品数为N)，yiy_iyi​ 表示用户 itemiitem_iitemi​ 的向量，k维列向量。Y=[y1,y2,...,yN]\\bold Y=[y_1,y_2,...,y_{N}]Y=[y1​,y2​,...,yN​]

用户向量与物品向量的内积，表示用户 $u$ 对物品 $i$ 的预测评分。矩阵分解的目标函数为：
min⁡X,Y∑rui≠0(rui−xuTyi)2+λ(∑u∣∣xu∣∣22+∑i∣∣yi∣∣22)\\min \\limits_{X,Y} \\sum\\limits_{r_{ui}\\neq\\ 0}\\left(r_{ui}-x^T_uy_i\\right)^2+\\lambda\\left(\\sum\\limits_{u}||x_u||^2_2+\\sum\\limits_{i}||y_i||^2_2\\right) X,Ymin​rui​= 0∑​(rui​−xuT​yi​)2+λ(u∑​∣∣xu​∣∣22​+i∑​∣∣yi​∣∣22​)
上式前半部分表示的是User矩阵*Item矩阵与评分矩阵中已知的评分差异，后半部分是L2正则项，保证数值计算稳定性，防止过拟合。

4.目标函数最优化问题求解

  目标函数最优化问题的工程解法一般采用交替最小二乘法( Alternating Least Squares , ALS)或随机梯度下降(SGD)。 在实际应用中，交替最小二乘更常用一些，这也是社交巨头 Facebook 在他们的推荐系统中选择的主要矩阵分解方法。

4.1 交替最小二乘法(ALS)

交替最小二乘的核心是 “交替”，接下来看看 ALS 是如何 “交替” :

矩阵分解的最终任务是找到两个矩阵 $\mathbf{X}$ 和 $\mathbf{Y}$，让它们相乘后约等于原矩阵 $\mathbf{R}$：
Rm×n=Xm×k×Yn×kT\\bold R_{m×n}=\\bold X_{m×k}\\ ×\\ \\bold Y_{n×k}^T Rm×n​=Xm×k​ × Yn×kT​
难就难在，$\mathbf{X}$ 和$\mathbf{Y}$ 两个都是未知的，如果知道其中一个的话，就可以按照线性代数标准解法求得，比如如果知道了 $\mathbf{Y}$，那么 $\mathbf{X}$ 就可以这样算：
Rm×n=Xm×k×Yn×k−1\\bold R_{m×n}=\\bold X_{m×k}\\ ×\\ \\bold Y_{n×k}^{-1} Rm×n​=Xm×k​ × Yn×k−1​
也就是 $\mathbf{R}$ 矩阵乘以 $\mathbf{Y}$ 矩阵的逆矩阵就得到了结果，反之知道了 $\mathbf{X}$ 再求$\mathbf{Y}$ 也是一样。

交替最小二乘通过迭代的方式解决了这个鸡生蛋蛋生鸡的难题：

1. 初始化随机矩阵 $\mathbf{Y}$ 里面的元素值；
2. 把 $\mathbf{Y}$ 矩阵当做已知的，直接用线性代数的方法求得矩阵 $\mathbf{X}$；
3. 得到了矩阵 $\mathbf{X}$后，把 $\mathbf{X}$ 当做已知的，故技重施，回去求解矩阵 $\mathbf{Y}$ ；
4. 上面两个过程交替进行，一直到误差满足设定条件为止。

交替最小二乘法步骤：

• $\mathbf{S}tep1$，固定 $\mathbf{Y}$ 优化 $\mathbf{X}$
  min⁡X∑rui≠0(rui−xuTyi)2+λ∑u∣∣xu∣∣22\\min \\limits_{X} \\sum\\limits_{r_{ui}\\neq\\ 0}\\left(r_{ui}-x^T_uy_i\\right)^2+\\lambda\\sum\\limits_{u}||x_u||^2_2 Xmin​rui​= 0∑​(rui​−xuT​yi​)2+λu∑​∣∣xu​∣∣22​
  将目标函数转化为矩阵表达形式：
  J(xu)=(Ru−YuTxu)T(Ru−YuTxu)+λxuTxuJ(x_u)=(R_u-Y^T_ux_u)^T(R_u-Y^T_ux_u)+\\lambda x^T_ux_u J(xu​)=(Ru​−YuT​xu​)T(Ru​−YuT​xu​)+λxuT​xu​
  其中 Ru=[rui1,rui2,...ruin]TR_u=[r_{ui_1},r_{ui_2},...r_{ui_n}]^TRu​=[rui1​​,rui2​​,...ruin​​]T 表示用户 $u$ 对 $n$ 个物品的评分；Yu=[yi1,yi2,...yim]Y_u=[y_{i_1},y_{i_2},...y_{i_m}]Yu​=[yi1​​,yi2​​,...yim​​] 为 $n$ 个物品的向量。

  求解目标函数 $J$ 关于 xux_uxu​ 的梯度，并令梯度等于0，得到：
  ∂J(xu)∂xu=−2Yu(Ru−YuTxu)+2λxu=0\\frac{\\partial J(x_u)}{\\partial x_u}=-2Y_u(R_u-Y^T_ux_u)+2\\lambda x_u=0 ∂xu​∂J(xu​)​=−2Yu​(Ru​−YuT​xu​)+2λxu​=0
  求解后可得：
  xu=(YuYuT+λI)−1YuRux_u = (Y_uY^T_u+\\lambda I)^{-1}Y_uR_u xu​=(Yu​YuT​+λI)−1Yu​Ru​

• $\mathbf{S}tep2$，固定 $\mathbf{X}$ 优化 $\mathbf{Y}$
  min⁡Y∑rui≠0(rui−xuTyi)2+λ∑i∣∣yi∣∣22\\min \\limits_{Y} \\sum\\limits_{r_{ui}\\neq\\ 0}\\left(r_{ui}-x^T_uy_i\\right)^2+\\lambda\\sum\\limits_{i}||y_i||^2_2 Ymin​rui​= 0∑​(rui​−xuT​yi​)2+λi∑​∣∣yi​∣∣22​

  • 将目标函数转化为矩阵表达形式：
    J(yi)=(Ri−XiTyi)T(Ri−XiTyi)+λyiTyiJ(y_i)=(R_i-X^T_iy_i)^T(R_i-X^T_iy_i)+\\lambda y^T_iy_i J(yi​)=(Ri​−XiT​yi​)T(Ri​−XiT​yi​)+λyiT​yi​
    其中Ru=[ru1i,ru2i,...rumi]TR_u=[r_{u_1{i}},r_{u_2i},...r_{u_mi}]^TRu​=[ru1​i​,ru2​i​,...rum​i​]T表示 $m$个用户对个物品 $i$ 的评分；Xi=[xu1,xu2,...xum]X_i=[x_{u_1},x_{u_2},...x_{u_m}]Xi​=[xu1​​,xu2​​,...xum​​] 为 $m$个用户的向量。

    求解目标函数 $J$关于 yiy_iyi​ 的梯度，并令梯度等于0，得到：
    ∂J(yi)∂xi=−2Xi(Ri−XiTyi)+2λyi=0\\frac{\\partial J(y_i)}{\\partial x_i}=-2X_i(R_i-X^T_iy_i)+2\\lambda y_i=0 ∂xi​∂J(yi​)​=−2Xi​(Ri​−XiT​yi​)+2λyi​=0
    求解后可得：
    yi=(XiXiT+λI)−1XiRiy_i = (X_iX^T_i+\\lambda I)^{-1}X_iR_i yi​=(Xi​XiT​+λI)−1Xi​Ri​

• 重复$\mathbf{S}tep1$和$2$，直到 $\mathbf{X}$ 和 $\mathbf{Y}$ 收敛，每次固定一个矩阵，优化另一个矩阵，都是最小二乘问题

  除了针对显式评分矩阵，ALS还可以对隐式矩阵进行分解，将评分看成行为的强度，比如浏览次数，阅读时间等。 当 rui>0r_{ui}\\ \\gt 0rui​ >0时， 表示用户 $u$对商品 $i$ 有行为，当 rui=0r_{ui}\\ = 0rui​ =0， 表示用户 $u$对商品 $i$ 没有行为。
Pui={1rui>00rui=0P_{ui}=\\begin{cases} 1 & r_{ui} \\gt 0 \\\\ 0 & r_{ui} = 0 \\end{cases} Pui​={10​rui​>0rui​=0​
上式 PuiP_{ui}Pui​ 称为用户偏好：当用户$u$对物品$i$有过行为，认为用户$u$对物品$i$感兴趣，PuiP_{ui}Pui​=1；当用户$u$对物品$i$没有过行为，认为用户$u$对物品$i$不感兴趣，PuiP_{ui}Pui​=0.

对隐式矩阵进行分解的步骤:

• 引入置信度($\alpha$ 为置信系数)
  cui=1+αruic_{ui}=1+\\alpha r_{ui} cui​=1+αrui​
  当rui>0\\ r_{ui}\\ \\gt 0 rui​ >0时， cuic_{ui}cui​ 与 ruir_{ui}rui​ 线性递增，当 rui=0r_{ui}\\ = 0rui​ =0时， cui=1c_{ui}\\ = 1cui​ =1，即 cuic_{ui}cui​ 最小值为1.

• 目标函数
  min⁡X,Y∑u=1m∑i=1ncui(rui−xuTyi)2+λ(∑u∣∣xu∣∣22+∑i∣∣yi∣∣22)\\min \\limits_{X,Y} \\sum\\limits_{u=1}\\limits^{m} \\sum\\limits_{i=1}\\limits^{n}c_{ui}\\left(r_{ui}-x^T_uy_i\\right)^2+\\lambda\\left(\\sum\\limits_{u}||x_u||^2_2+\\sum\\limits_{i}||y_i||^2_2\\right) X,Ymin​u=1∑m​i=1∑n​cui​(rui​−xuT​yi​)2+λ(u∑​∣∣xu​∣∣22​+i∑​∣∣yi​∣∣22​)

• ALS求解矩阵$\mathbf{X}$和$\mathbf{Y}$

ALS工具

• spark ml库（官方推荐）
• python代码：https://github.com/tushushu/imylu/blob/master/imylu/recommend/als.py

4.2 随机梯度下降SGD

  SGD基本思路是以随机方式遍历训练集中的数据，并给出每个已知评分的预测评分。用户和物品特征向量的调整就沿着评分误差越来越小的方向迭代进行，直到误差达到要求。所以，SGD不需要遍历所有的样本即可完成特征向量的求解。

矩阵分解的目标函数为：
J(xu,yi)=min⁡X,Y∑rui≠0(rui−xuTyi)2+λ(∑u∣∣xu∣∣22+∑i∣∣yi∣∣22)J(x_u,y_i)= \\min \\limits_{X,Y} \\sum\\limits_{r_{ui}\\neq\\ 0}\\left(r_{ui}-x^T_uy_i\\right)^2+\\lambda\\left(\\sum\\limits_{u}||x_u||^2_2+\\sum\\limits_{i}||y_i||^2_2\\right) J(xu​,yi​)=X,Ymin​rui​= 0∑​(rui​−xuT​yi​)2+λ(u∑​∣∣xu​∣∣22​+i∑​∣∣yi​∣∣22​)
分别求解J(xu,yi)J(x_u,y_i)J(xu​,yi​)关于 xux_uxu​ 和 yiy_iyi​的梯度如下：
∂J(xu,yi)∂xu=∑u,rui≠0−2(rui−xuTyi)yi+∑u2λ∣∣xu∣∣2∂J(xu,yi)∂yi=∑i,rui≠0−2(rui−xuTyi)xu+∑i2λ∣∣yi∣∣2\\begin{align} & \\frac{\\partial J(x_u,y_i)}{\\partial x_u}=\\sum\\limits_{u,r_{ui}\\neq 0}-2\\left(r_{ui}-x^T_uy_i\\right)y_i+\\sum\\limits_u 2\\lambda||x_u||_2 \\\\[2ex] & \\frac{\\partial J(x_u,y_i)}{\\partial y_i}=\\sum\\limits_{i,r_{ui}\\neq 0}-2\\left(r_{ui}-x^T_uy_i\\right)x_u+\\sum\\limits_i 2\\lambda||y_i||_2 \\end{align} ​∂xu​∂J(xu​,yi​)​=u,rui​=0∑​−2(rui​−xuT​yi​)yi​+u∑​2λ∣∣xu​∣∣2​∂yi​∂J(xu​,yi​)​=i,rui​=0∑​−2(rui​−xuT​yi​)xu​+i∑​2λ∣∣yi​∣∣2​​​
不断更新矩阵 $\mathbf{X}$ 和 $\mathbf{Y}$
xu=xu+α(∑u,rui≠0−2(rui−xuTyi)yi+∑u2λ1∣∣xu∣∣2)yi=yi+α(∑i,rui≠0−2(rui−xuTyi)xu+∑i2λ2∣∣yi∣∣2)\\begin{align} &x_u=x_u+\\alpha(\\sum\\limits_{u,r_{ui}\\neq 0}-2\\left(r_{ui}-x^T_uy_i\\right)y_i+\\sum\\limits_u 2\\lambda_1||x_u||_2) \\\\[2ex] &y_i=y_i+\\alpha(\\sum\\limits_{i,r_{ui}\\neq 0}-2\\left(r_{ui}-x^T_uy_i\\right)x_u+\\sum\\limits_i 2\\lambda_2||y_i||_2) \\end{align} ​xu​=xu​+α(u,rui​=0∑​−2(rui​−xuT​yi​)yi​+u∑​2λ1​∣∣xu​∣∣2​)yi​=yi​+α(i,rui​=0∑​−2(rui​−xuT​yi​)xu​+i∑​2λ2​∣∣yi​∣∣2​)​​
由于 $\mathbf{X}$ 和 $\mathbf{Y}$ 是两个不同的矩阵，通常分别采取不同的正则参数，如 λ1\\lambda_1λ1​和λ2\\lambda_2λ2​

5.矩阵分解算法

  MF(Matrix Factorization，矩阵分解)模型核心思想是通过两个低维小矩阵(一个代表用户embedding矩阵，一个代表物品embedding矩阵)的乘积计算，来模拟真实用户点击或评分产生的大的协同信息稀疏矩阵，本质上是编码了用户和物品协同信息的降维模型。

当训练完成，每个用户和物品得到对应的低维embedding表达后，如果要预测某个 UseriUser_iUseri​ 对 ItemjItem_jItemj​ 的评分的时候，只要它们做个内积计算 <Useri,Itemj><User_i,Item_j><Useri​,Itemj​> ，这个得分就是预测得分。

5.1 Traditional SVD

5.1.1 回顾特征值和特征向量

特征值和特征向量的定义如下：
$$Ax=\lambda x$$
其中 $A$ 是一个 $n\times n$ 的实对称矩阵，$x$ 是一个 $n$ 维向量，则我们说 $\lambda$ 是矩阵 $A$ 的一个特征值，而 $x$ 是矩阵 $A$ 的特征值 $\lambda$ 所对应的特征向量。

求出特征值和特征向量有什么好处呢?

可以将矩阵A特征分解。

如果我们求出了矩阵$A$的$n$个特征值λ1≤λ2≤...≤λnλ_1≤λ_2≤...≤λ_nλ1​≤λ2​≤...≤λn​,以及这 $n$个特征值所对应的特征向量w1,w2,...wn{w_1,w_2,...w_n}w1​,w2​,...wn​，如果这 $n$ 个特征向量线性无关，那么矩阵 $A$ 就可以用下式的特征分解表示：
A=WΣW−1A=W\\Sigma W^{-1} A=WΣW−1
其中 $W$ 是这 $n$ 个特征向量所张成的 $n\times n$ 维矩阵，而 $\Sigma$ 为这 $n$ 个特征值为主对角线的 $n\times n$ 维矩阵。

一般我们会把$W$的这$n$个特征向量标准化，即满足∣∣wi∣∣2=1||w_i||_2=1∣∣wi​∣∣2​=1, 或者说 wiTwi=1w^T_iw_i=1wiT​wi​=1，此时 $W$ 的 $n$ 个特征向量为标准正交基，满足WTW=IW^TW=IWTW=I，即WT=W−1W^T=W^{−1}WT=W−1, 也就是说$W$为酉矩阵。
A=WΣWTA=W\\Sigma W^{T} A=WΣWT
注意到要进行特征分解，矩阵$A$必须为方阵。那么如果$A$不是方阵，即行和列不相同时，我们还可以对矩阵进行分解吗？答案是可以，此时我们的SVD登场了。

5.1.2 SVD

假设矩阵$A$是一个$m\times n$的矩阵，那么我们定义矩阵$A$的SVD为： ：
A=UΣVTA=U\\Sigma V^{T} A=UΣVT
其中 $U$ 是一个 $m\times m$ 的矩阵，$\Sigma$ 是一个 $m\times n$ 的矩阵，除了主对角线上的元素以外全为 $0$ ，主对角线上的每个元素都称为奇异值，$V$是一个 $n\times n$ 的矩阵。$U$ 和 $V$ 都是酉矩阵，即满足UTU=I,VTV=IU^TU=I,V^TV=IUTU=I,VTV=I。下图可以很形象的看出上面SVD的定义：

如何求出SVD分解后的$U,\Sigma ,V$这三个矩阵呢？

如果将$A$的转置和$A$做矩阵乘法，那么会得到$n\times n$的一个方阵ATAA^TAATA。既然ATAA^TAATA是方阵，那么可以进行特征分解，得到的特征值和特征向量满足下式：
(ATA)vi=λivi(A^TA)v_i=\\lambda_i v_i (ATA)vi​=λi​vi​
这样可以得到矩阵ATAA^TAATA的$n$个特征值和对应的$n$个特征向量$v$了。将ATAA^TAATA的所有特征向量张成一个$n\times n$的矩阵$V$，即为SVD公式里面的$V$矩阵了。一般将$V$中的每个特征向量叫做$A$的右奇异向量。

如果我们将A和A的转置做矩阵乘法，那么会得到$m\times m$的一个方阵AATAA^TAAT。既然AATAA^TAAT是方阵，那么可以进行特征分解，得到的特征值和特征向量满足下式：
(AAT)ui=λiui(AA^T)u_i=\\lambda_iu_i (AAT)ui​=λi​ui​
这样可以得到矩阵AATAA^TAAT的$n$个特征值和对应的$m$个特征向量$u$了。将AATAA^TAAT的所有特征向量张成一个$m\times m$的矩阵$U$，即为SVD公式里面的$U$矩阵了。一般将$U$中的每个特征向量叫做$A$的左奇异向量。

$U$和$V$都求出来了，现在就剩下奇异值矩阵 $\Sigma$ 没有求出了。由于除了对 $\Sigma$ 角线上是奇异值其他位置都是0，那只需要求出每个奇异值$\sigma$ 就可以了。
A=UΣVT⇒AV=UΣVTV⇒AV=UΣ⇒Avi=σiui⇒σi=Avi/uiA=U\\Sigma V^T \\Rightarrow AV=U\\Sigma V^TV \\Rightarrow AV=U\\Sigma \\Rightarrow Av_i = \\sigma_i u_i \\Rightarrow \\sigma_i = Av_i / u_i A=UΣVT⇒AV=UΣVTV⇒AV=UΣ⇒Avi​=σi​ui​⇒σi​=Avi​/ui​
这样我们可以求出我们的每个奇异值，进而求出奇异值矩阵$\Sigma$。

ATAA^TAATA的特征向量组成的就是我们SVD中的$V$矩阵，而AATAA^{T}AAT的特征向量组成的就是我们SVD中的$U$矩阵，这有什么根据吗？这个其实很容易证明，我们以$V$矩阵的证明为例。
A=UΣVT⇒AT=VΣTUT⇒ATA=VΣTUTUΣVT=VΣ2VTA=U\\Sigma V^T \\Rightarrow A^T=V\\Sigma^T U^T \\Rightarrow A^TA = V\\Sigma^T U^TU\\Sigma V^T = V\\Sigma^2V^T A=UΣVT⇒AT=VΣTUT⇒ATA=VΣTUTUΣVT=VΣ2VT
上式证明使用了: UTU=I,ΣTΣ=Σ2U^TU=I, \\Sigma^T\\Sigma=\\Sigma^2UTU=I,ΣTΣ=Σ2。 可以看出ATAA^TAATA的特征向量组成的的确就是我们SVD中的$V$矩阵。类似的方法可以得到AATAA^TAAT的特征向量组成的就是我们SVD中的$U$矩阵。

特征值矩阵等于奇异值矩阵的平方，也就是说特征值和奇异值满足如下关系：
σi=λi\\sigma_i = \\sqrt{\\lambda_i} σi​=λi​​
通过求出ATAA^{T}AATA的特征值取平方根来求奇异值更加方便。

5.1.3 SVD的性质

  对于奇异值,它跟特征分解中的特征值类似，在奇异值矩阵中也是按照从大到小排列，而且奇异值的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上的比例。也就是说，可以用最大的$k$个的奇异值和对应的左右奇异向量来近似描述矩阵。也就是说：
Am×n=Um×mΣm×nVn×nT≈Um×kΣk×kVk×nTA_{m \\times n} = U_{m \\times m}\\Sigma_{m \\times n} V^T_{n \\times n} \\approx U_{m \\times k}\\Sigma_{k \\times k} V^T_{k \\times n} Am×n​=Um×m​Σm×n​Vn×nT​≈Um×k​Σk×k​Vk×nT​
  SVD可以用于PCA降维，来做数据压缩和去噪。也可以用于推荐算法，将用户和喜好对应的矩阵做特征分解，进而得到隐含的用户需求来做推荐。同时也可以用于NLP中的算法，比如潜在语义索引(LSI)。

5.1.4 SVD与PCA的关系

PCA的算法流程

求样本x(i)x^{(i)}x(i)的n′n'n′维的主成分其实就是求样本集的协方差矩阵XXTXX^TXXT的前n′n'n′个特征值对应特征向量矩阵$W$，然后对于每个样本x(i)x^{(i)}x(i)，做如下变换 z(i)=WTx(i)z^{(i)}=W^Tx^{(i)}z(i)=WTx(i)，即达到降维的PCA目的。

下面我们看看具体的算法流程。

输入：$n$维样本集D=(x(1),x(2),...,x(m))D=(x^{(1)}, x^{(2)},...,x^{(m)})D=(x(1),x(2),...,x(m))，要降维到的维数n′n'n′.

输出：降维后的样本集$D\prime$

1. 对所有的样本进行中心化： x(i)=x(i)−1m∑j=1mx(j)x^{(i)} = x^{(i)} - \\frac{1}{m}\\sum\\limits_{j=1}^{m} x^{(j)}x(i)=x(i)−m1​j=1∑m​x(j)

2. 计算样本的协方差矩阵XXTXX^{T}XXT

3. 对矩阵XXTXX^{T}XXT进行特征值分解

4）取出最大的n’个特征值对应的特征向量(w1,w2,...,wn′)(w_1,w_2,...,w_n′)(w1​,w2​,...,wn​′), 将所有的特征向量标准化后，组成特征向量矩阵$W$。

5）对样本集中的每一个样本x(i)x^{(i)}x(i),转化为新的样本z(i)=WTx(i)z^{(i)}=W^Tx^{(i)}z(i)=WTx(i)

6. 得到输出样本集D′=(z(1),z(2),...,z(m))D' =(z^{(1)}, z^{(2)},...,z^{(m)})D′=(z(1),z(2),...,z(m))

有时候，我们不指定降维后的n′n'n′的值，而是换种方式，指定一个降维到的主成分比重阈值$t$。这个阈值$t$在$(0,1]$之间。假如我们的n个特征值为λ1≥λ2≥...≥λn\\lambda_1 \\geq \\lambda_2 \\geq ... \\geq \\lambda_nλ1​≥λ2​≥...≥λn​,则n′n'n′可以通过下式得到:
∑i=1n′λi∑i=1nλi≥t\\frac{\\sum\\limits_{i=1}^{n'}\\lambda_i}{\\sum\\limits_{i=1}^{n}\\lambda_i} \\geq t i=1∑n​λi​i=1∑n′​λi​​≥t
SVD用于PCA

PCA仅仅使用了我们SVD的右奇异矩阵，没有使用左奇异矩阵，那么左奇异矩阵有什么用呢？

现有样本是$m\times n$的矩阵$X$，如果我们通过SVD找到了矩阵XXTXX^{T}XXT最大的$d$个特征向量张成的$m\times d$维矩阵$U$，则如果进行如下处理：
Xd×n′=Ud×mTXm×nX'_{d \\times n} = U_{d \\times m}^TX_{m \\times n} Xd×n′​=Ud×mT​Xm×n​
可得一个$d\times n$的矩阵$X＇$，和原来的$m\times n$维样本矩阵$X$相比，行数从$m$减到了$d$，可见对行数进行了压缩。也就是说，左奇异矩阵可以用于行数的压缩。相对的，右奇异矩阵可以用于列数即特征维度的压缩，也就是PCA降维。

5.2 FunkSVD(LFM)

  2006年的Netflix Prize之后， Simon Funk公布了一个矩阵分解算法叫做Funk-SVD, 后来被 Netflix Prize 的冠军Koren称为Latent Factor Model(LFM)。

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

目标:让用户的评分和用矩阵乘积得到的评分残差尽可能的小，也就是说，可以用均方差作为损失函数，来寻找最终的$P$和$Q$。

  对于某一个用户评分mijm_{ij}mij​，如果用FunkSVD进行矩阵分解，则对应的表示为qjTpiq_j^Tp_iqjT​pi​，采用均方差做为损失函数，则我们期望(mij−qjTpi)2(m_{ij}-q_j^Tp_i)^2(mij​−qjT​pi​)2尽可能的小，如果考虑所有的物品和样本的组合，则我们期望最小化下式：
∑i,j(mij−qjTpi)2\\sum\\limits_{i,j}(m_{ij}-q_j^Tp_i)^2 i,j∑​(mij​−qjT​pi​)2
只要能最小化上面的式子，并求出极值所对应的pi,qjp_i, q_jpi​,qj​，则可以得到矩阵$P$和$Q$，那么对于任意矩阵$M$任意一个空白评分的位置，我们可以通过qjTpiq_j^Tp_iqjT​pi​计算预测评分。