线性代数 13

两个线性代数里面在机器学习领域大放异彩的算法,SVD和PageRank。

之前对方阵有对角化分解,而且不是所有的方阵都可以对角化,但是SVD是所有矩阵都可以进行分解的。SVD分解的过程如下:

这个公式会有什么特性呢?我们假设\(U = \{u_1, u_2, \cdots, u_m\}\)\(V = \{v_1, v_2, \cdots, v_n \}\)\(\Sigma\)是常数\(\{\sigma_1, \sigma_2, \cdots, \sigma_k\}\)的对角矩阵。这里有一个点要注意的就是\(\Sigma\)的样子大体上会是左上角一个对角矩阵,其余部分都是零的\(m \times n\)的矩阵。这些\(\sigma\)称为奇异值,这些奇异值会等于\(A^{\top}A\)的特征根的平方根。

那么如果矩阵经过SVD分解以后,一定会得到\(Av_i = \begin{cases}\sigma_i u_i & \text{if } 1 \le i \le k \\ 0 & \text{if } i > k \end{cases}\)\(A^{\top}u_i = \begin{cases}\sigma_i v_i & \text{if } 1 \le i \le k \\ 0 & \text{if } i > k \end{cases}\)

现在问题来了,如果给一个矩阵,要怎么计算奇异值?假设有一个矩阵\(A = \begin{bmatrix} 0 & 1 & 2 \\ 1 & 0 & 1 \end{bmatrix}\),可以直观看到,这个矩阵是\(3 \times 2\)的矩阵,因此需要在\(\mathbb{R}^3\)\(\mathbb{R}^2\)都要有orthogonal matrix。所以先构建矩阵\(A^{\top}A = \begin{bmatrix}1 & 0 & 1 \\ 0 & 1 & 2 \\ 1 & 2 & 5 \end{bmatrix}\)。那么做一个\(\mathbb{R}^3\)上面的orthogonal matrix,按照这个博客最后的正交化方法,我们可以将矩阵正交化为\(v_1 = \frac{1}{\sqrt{30}} \begin{bmatrix} 1 \\ 2 \\ 5 \end{bmatrix}\)\(v_2 = \frac{1}{\sqrt{5}} \begin{bmatrix} 2 \\ -1 \\ 0 \end{bmatrix}\)\(v_3 = \frac{1}{\sqrt{6}} \begin{bmatrix} 1 \\ 2 \\ -1 \end{bmatrix}\)。然后求一下\(A^{\top}A\)的特征根分别是6,1和0。所以奇异值就是\(\sqrt{6}\)和1。然后就可以按照上面的公式算出\(u_1 = \frac{1}{\sqrt{5}} \begin{bmatrix} 2 \\ 1 \end{bmatrix}\)\(u_1 = \frac{1}{\sqrt{5}} \begin{bmatrix} -1 \\ 2 \end{bmatrix}\)

那么事实上算到这里,只要将上面的向量集合和奇异值排列好,就完成了矩阵\(A\)的SVD分解。也就是\[ A = \begin{bmatrix} \frac{2}{\sqrt{5}} & \frac{-1}{\sqrt{5}} \\ \frac{1}{\sqrt{5}} & \frac{2}{\sqrt{5}} \end{bmatrix} \begin{bmatrix} \sqrt{6} & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{30}} & \frac{2}{\sqrt{5}} & \frac{1}{\sqrt{6}} \\ \frac{2}{\sqrt{30}} & \frac{-1}{\sqrt{5}} & \frac{2}{\sqrt{6}} \\ \frac{5}{\sqrt{30}} & 0 & \frac{-1}{\sqrt{6}} \end{bmatrix}^{\top} \]

那么SVD跟PCA是有非常多相似的地方的,如果我们使用了全部的奇异值,那么我们就可以还原原来的矩阵,但是如果我们只取了前面的一部分奇异值,我们得到的就是一个损失了一部分信息的矩阵。SVD在机器学习的领域有非常多的应用,最常用的一个地方就是用在推荐算法里面,另外就是降维。此外,还有一个矩阵分解方法是NMF,解释性会更强一些。这个在之前机器学习的博客里面也有提到。

然后是PageRank。这个算法缔造了今天的谷歌,也被称作是最贵的eigen value。PageRank实际上是一个蛮复杂的模型,这里讲一个最简单的情况,后面找机会再认真学习一下。所以这里有一些矩阵分析里面的定理(虽然我也不是很懂)就直接记结论,证明过程以后再学吧。

首先我们假设这个世界上只有四个网页,他们的关系如下:

现在假设有一个人随机浏览网页,他到每一个网站的可能性都是一样的,那么根据上图的结果我们可以得到: \[ \begin{align} x_1 & = x_3 + \frac{1}{2} x_4 \\ x_2 & = \frac{1}{3} x_1 \\ x_3 & = \frac{1}{3} x_1 + \frac{1}{2} x_2 + \frac{1}{2} x_4 \\ x_4 & = \frac{1}{3} x_1 + \frac{1}{2} x_2 \end{align} \]

所以我们就可以很简单得到这样一个矩阵\(A = \begin{bmatrix}0 & 0 & 1 & \frac{1}{2} \\ \frac{1}{3} & 0 & 0 & 0 \\ \frac{1}{3} & \frac{1}{2} & 0 & \frac{1}{2} \\ \frac{1}{3} & \frac{1}{2} & 0 & 0\end{bmatrix}\)。这样的矩阵我们叫做马尔科夫矩阵,或者叫转移矩阵。这种矩阵的特点是每一个行的和为1,或者每一个列的和为1。根据Perron-Frobenius theorem这样的矩阵必然有一个特征值为1。

所以PageRank实际上在做的事情就是计算\(A\)的特征根为1时候的特征向量。这个特征向量最后就是我们的网页排名。

如果想要对PageRank有多一点的了解可以上Wikipedia看一下PageRank的页面,也可以直接看原来的论文。另外有中文的这篇博客http://blog.codinglabs.org/articles/intro-to-pagerank.html,介绍比较全面,不过基本上没有数学证明过程。看看以后有没有空自己推导一遍,顺便Python实现一下。

乞讨码