机器学习课程笔记03——低秩矩阵分解

何为低秩矩阵(low-rank matrix)

我们先来回忆下矩阵的秩。举个简单的例子：
$\begin{cases} \ 2x+3y+z=10\\ \ 3x+y+z=7\\ \ 6x+2y+2z=14 \end{cases}$⎩⎪⎨⎪⎧​ 2x+3y+z=10 3x+y+z=7 6x+2y+2z=14​
对于上面的线性方程组，方程1和方程2有不同的解，而方程2和方程3的解完全相同。我们可以说方程3是多余的，因为它没有带来有用的信息，把它去掉对解方程组没影响。从方程组中去掉多余的方程，自然就导出了“矩阵的秩”这一概念。

还记得徒手求矩阵的秩吗？我们先通过矩阵初等变换将矩阵A化为阶梯型矩阵，若该阶梯型矩阵有r个非零行，那矩阵A的秩rank(A)就等于r。矩阵的秩度量的其实就是矩阵的行列之间的相关性。如果矩阵的各行或列是线性无关的，那么矩阵就是满秩的，也就是秩等于行数。

让我们回到上面线性方程组，因为线性方程组可以用矩阵描述，所以秩就表示有多少个有用的方程。上面的方程组实际上只有2个是有用的，方程3是多余的，因此对应的矩阵的秩就是2。

既然秩可以度量相关性，而矩阵的相关性实际上就表示矩阵的结构信息。如果矩阵之间各行的相关性很强，那么就表示这个矩阵实际可以投影到更低维的线性子空间，也就是用几个向量就可以完全表达，那么它就是低秩的。

Summary：如果矩阵表达的是结构性信息，例如图像、用户-商品推荐表等等，那么这个矩阵各行之间存在这一定的相关性，那这个矩阵一般就是低秩的。

向量化：低秩矩阵分解(low-rank matrix factorization)

我们使用机器学习课程16中推荐系统(recommender system)的例子来说明。

将左边表格中的数据写为矩阵形式，即为右边的矩阵Y。因为用户j对电影i的评分预测为
$(\theta^{(j)})^Tx^{(i)}$(θ(j))Tx(i)
则矩阵Y所对应的预测值矩阵如下：

我们整理一下x和θ：
$X= \left[ \begin{matrix} (x^{(1)})^T \\ (x^{(2)})^T \\ \vdots \\ (x^{(n_m)})^T \end{matrix} \right] \quad \quad \Theta= \left[ \begin{matrix} (\theta^{(1)})^T \\ (\theta^{(2)})^T \\ \vdots \\ (\theta^{(n_u)})^T \end{matrix} \right] \\ \quad \\ 所以预测值矩阵可以表示为X\Theta^T$X=⎣⎢⎢⎢⎡​(x(1))T(x(2))T⋮(x(nm​))T​⎦⎥⎥⎥⎤​Θ=⎣⎢⎢⎢⎡​(θ(1))T(θ(2))T⋮(θ(nu​))T​⎦⎥⎥⎥⎤​所以预测值矩阵可以表示为XΘT
上述过程就是协同矩阵的向量化。那么我们如何找出相关商品呢？

1. 对于每一个商品i，我们找出其特征向量x(i)
2. 找出两个特征比较相同的商品，即找出使特征向量差值的绝对值最小的若干个商品
3. 这些商品就是和商品i最相似的商品，既可以作为相关商品推荐

实现细节：均值归一化(implementation detail: mean normalization)

假设我们有一个用户Eve没有评价任何电影

此时，倘若我们仍然使用之前的算法，即：

因为Eve对于任意电影i都没有评价，所以不满足r(i,j)=1的条件，因此方程的第一部分为零，而方程的第二部分为一个常数，所以方程的前两个部分对于求最小值没啥作用。唯一起作用的只有方程的第三部分。又因为本例子中电影分为动作电影和爱情电影两类，所以θ^(5)是一个[2×1]的矩阵。则方程简化如下：
$min_{\theta^{(5)}}\quad \frac{\lambda}{2}[(\theta^{(5)}_1)^2+(\theta^{(5)}_2)^2]$minθ(5)​2λ​[(θ1(5)​)2+(θ2(5)​)2]
显然，两个θ为零就得到最小值零了，即Eve的预测评分都为零。然而对于这个结果，我们就无法推荐相关电影了，因为对所有电影其||x(i)-x(j)||都为零。所以，我们需要引入归一化。

首先计算平均分μ。

然后将原来的矩阵Y的每一个数减去这一行（这一部电影）对应的平均值，得到新的矩阵Y如下所示。

利用这个新的矩阵Y学习θ和x的值，则对于Eve，之前关于最小化的分析仍成立，则归一化之后的预测值公式为：
$(\theta^{(j)})^Tx^{(i)}+\mu$(θ(j))Tx(i)+μ
所以，Eve的预测值为：
$(\theta^{(5)})^Tx^{(i)}+\mu=\mu=\left[ \begin{matrix} 2.5 \\ 2.5 \\ 2 \\ 2.25 \\ 1.25 \end{matrix} \right]$(θ(5))Tx(i)+μ=μ=⎣⎢⎢⎢⎢⎡​2.52.522.251.25​⎦⎥⎥⎥⎥⎤​
对于这个预测结果我们是可以接受的，因为我们不知道Eve的喜好，所以把她的评分预测为平均水平。

reference

https://blog.****.net/quiet_girl/article/details/72436605
https://blog.****.net/manduner/article/details/80564414