机器学习算法系列(12)奇异值分解——以图像压缩为例

严格地说来,本文涉及的主题并非属于机器学习算法,只是机器学习中的一种降维方法,笔者为了方便,仍旧将其归于机器学习算法系列。在解释奇异值分解的时候,笔者回避了难以理解的矩阵空间变换,而是从数学的角度用简单明了的公式说明,希望能够帮助大家理解。在这里说点题外话,在写这篇文章的时候,深感中文世界技术博客资源的匮乏,本土搜索引擎得到的结果雷同率极高不说(坚持用 Google!),博客文章质量的良莠不齐,复制粘贴的“搬运工”大行其道,初学者一不留神可能就会被误导。正是由于这种环境,笔者“不得已”逐渐养成了直接阅读英文原文的习惯,一来可以获得第一手资源,二来也可以锻炼自己的阅读能力。写博客,坚持原创、独立思考是基本的前提,也是对读者负责。

一、前言

在之前一篇文章中有提到过一种降维方法:主成分分析法(PCA),在这篇文章中我会介绍另外一种在机器学习中非常著名的降维技术:奇异值分解(Singular Value Decomposition,以下简称 SVD)是机器学习中提取信息或者也叫降维的一种方法,SVD 广泛应用于数据压缩和图像去噪。

举一个简单易懂的例子:比如,每当学习一门新的学科,想象学科中的各种概念和知识构成了一个巨大的矩阵中的每个元素。为了理解它,你阅读了大量的文献,记了许多笔记,反反复复地理解,然后你明白了哪些部分是无关紧要的,哪些是必考的核心概念,一番去粗取精之后,原本厚厚的教材便可以浓缩为几页笔记。简单地来说,SVD 本质上就是这么一个过程,它能够帮助我们去除矩阵中的冗余信息,只保留最能够代表原矩阵的部分。

那么问题来了,如何进行奇异值分解呢?在这之前,听过一次培训班的笔者在庸师的讲解下,被各种 null space 、Strang’s Diagram 留下了“阴影”,以为 SVD 乃一大难度极高的“绝学”,以至于后来一直没敢去碰。

其实,

最近重拾 SVD ,查找了许多资料,其中来自火光摇曳翻译的一篇文章:奇异值分解(We Recommend a Singular Value Decomposition)在中文世界中广为流传,这篇译文加上原文:We Recommend a Singular Value Decomposition前前后后看了不下30遍,然而笨拙如我,除了记住了“22矩阵奇异值分解的几何实质是:对于任意22矩阵,总能找到某个正交网格到另一个正交网格的转换与矩阵变换相对应”这句话,依旧还是没能弄明白 SVD 到底要干啥。罢了,只能老老实实回去啃论文,Dan Kalman, A Singularly Valuable Decomposition: The SVD of a Matrix, The College Mathematics Journal 27 (1996), 2-23.这篇论文的第2页和第3页,反复读几遍你会对 SVD 与 EVD 两者有更深的理解。然后,直到遇见统计之都的这篇文章:奇异值分解和图像压缩,看到了公式\(\eqref{svd}\)才豁然开朗,仿佛一语惊醒梦中人!什么鬼旋转、伸缩、再旋转,这才是 SVD 的精髓啊!!!

二、奇异值分解:从特征值分解的角度

回顾线性代数,我们知道,给定实对称矩阵\(A_{n*n}\),对它进行特征分解(eigenvalue decomposition,以下简称 EVD)十分简单,只需要求解$ AV=V \(即可,\)V\(是它的特征向量,\)$是特征值。忘记这部分的读者可以翻翻之前的教材或者看看麻省理工公开课:线性代数,里边有一节专门讲奇异值分解,时隔多年,老爷子去年貌似又更新了

在理解 SVD 前,我们必须抛弃以往在大学学习线性代数时留下的只对或只能方阵做特征分解的思想

考虑任意的\(m*n\)矩阵\(A\),则存在对角矩阵\(\Sigma\),正交矩阵\(U\)\(V\)(也叫左右奇异矩阵),有

\[\begin{equation}\begin{split} A=U \Sigma V^{T} \label{1} \end{split}\end{equation}\]

奇异值分解的目的就是为了找到符合条件的\(\Sigma\)\(U\)\(V\),使得上式\(\eqref{1}\)成立。但是,现实中的矩阵大多不是方阵,奇异值和奇异矩阵的求解需要转换一下思维。

不妨令\(A^{T} A =(V\Sigma U^{T}) U \Sigma V^{T}\),由于\(U\)是正交矩阵,故\(U^{T}U\)为单位矩阵。所以,有

\[ A^{T}A = V(\Sigma ^T\Sigma)V^T \\ A A^{T} = U(\Sigma ^T\Sigma)U^T\]

这样一来,非方阵的境地就得到了化解,奇异值分解巧妙地转化为特征值分解了。对任意矩阵\(A\)的 SVD, 右奇异向量是\(A^{T} A\)的特征向量,左奇异向量是\(A A^{T}\)的特征向量,奇异值为\(\Sigma ^T\Sigma\)上对角线非零元素的平方根。

正如上图下划线部分内容,如果\(A\)本身就是对称矩阵,对\(A\)的 SVD,它的左右奇异向量等价于\(A\)的特征向量,它的奇异值等价于\(A\)的特征值。所以,对任意的\(A\),实对称矩阵\(A^T A\)的 SVD 和 EVD 殊途同归。

讲了这么多,SVD 的求解应该解释得差不多了,不过读者可能还是不明白 SVD 到底是干啥的,你不是说 SVD 可以压缩数据吗?那你是怎么压缩的呢?下面就来从数学的角度来讲讲数据压缩的原理

\(A\)的左右奇异向量如果用列向量的形式表示

\[ U=(u_1,u_2,\ldots,u_n) \\ V=(v_1,v_2,\ldots,v_n)\]

\(\Sigma\)的对角元素为\(\sigma_i\),那么\(A\)可以分解为一系列的线性组合

\[\begin{equation}\begin{split} A = \sigma_1u_1v_1^{T} + \sigma_2u_2v_2^{T}+···+\sigma_nu_nv_n^{T} \\ \label{svd} \end{split}\end{equation}\]

又因为每项\(\sigma_iu_iv_i^{T}\)都表示一个\(m*n\)的矩阵\(A_i\)。这样一来,我们便可以认为矩阵\(A\)\(n\)个这样矩阵的和。特征值\(\sigma_i\)越大表示\(A_i\)对矩阵的贡献越大,所以控制等式右边多项式的个数便可以达到压缩数据的目的!

三、用 Python 实现 SVD

在 Python 下通过 numpy 下的np.linalg.svd()函数可轻松实现 SVD

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np
import time
from PIL import Image
# 读取图片数据
img = Image.open('gakki.png')
imggray = img.convert('LA')
plt.figure(figsize=(9, 6))
plt.imshow(img)
# 图片转化为 numpy 数组
imgmat = np.array(list(imggray.getdata(band=0)), float)
imgmat.shape = (imggray.size[1], imggray.size[0])
imgmat = np.matrix(imgmat)
plt.figure(figsize=(9,6))
plt.imshow(imgmat, cmap='gray')
原图

原图

1
2
3
4
5
6
7
8
9
# 奇异值分解得左右奇异矩阵和奇异值矩阵
U, sigma, V = np.linalg.svd(imgmat)
# 逐步增加奇异值的个数
for i in range(2, 40, 8):
reconstimg = np.matrix(U[:, :i]) * np.diag(sigma[:i]) * np.matrix(V[:i, :])
plt.imshow(reconstimg, cmap='gray')
title = "n = %s" % i
plt.title(title)
plt.show()

下面是图片从压缩到逐步接近原图的过程,可以看出,当只取公式\(\eqref{svd}\)的前2项时,从图像中几乎不能分辨出 gakki 酱,只能看到一个隐隐约约的轮廓。当奇异值得数目增加到 10 个,似乎能够猜到这是谁了,只是图片仍旧十分模糊。随着奇异值数目的增加,图片越来越清晰。

当取了前 51 个奇异值的时候,压缩后的图像与原图基本上看不出什么差别了,这也侧面说明了在 SVD 中,奇异值的分布是很不均衡,绝大多数奇异值集中在一极。以 gakki 的图片为例,总共有 670 个奇异值,奇异值的大小下降特别快,最大的奇异值和第二大的奇异值就相差了一个数量级。

如果您有什么问题或建议,欢迎留言!要是能够帮助分享一下那就再好不过啦!

图片来源:http://sealedbook.blogspot.jp/2015/02/legal-high-3-will-start-april.html

图片来源:http://sealedbook.blogspot.jp/2015/02/legal-high-3-will-start-april.html

参考链接

  1. 统计之都: 奇异值分解和图像压缩
  2. Singular Value Decomposition (SVD) tutorial
  3. 奇异值的物理意义是什么? - 回答作者: 郑宁
  4. We Recommend a Singular Value Decomposition
  5. 示例图片来源
  6. Dan Kalman, A Singularly Valuable Decomposition: The SVD of a Matrix, The College Mathematics Journal 27 (1996), 2-23.
觉得还不错?帮我赞助点域名费吧:)