在自然语言处理或者机器学习相关应用时，通常首先要做的是将每一个样本转换成一个向量，然后将预处理过后的样本聚集在一起以矩阵计算的形式来对数据进行分析，然而很多时候都会碰到向量维度过高矩阵过大带来的计算复杂度太高问题，这个时候就要对样本数据集进行降维处理，也就是通常所说的主成分分析 (Principal components analysis，PCA)，在尽可能保持原本数据集的特征的前提下降低数据集维度，简单的线性回归就是一种降维操作（将二维平面上的点用一维的线段来表示）。
简单线性回归
而主成分分析经常用到的一种方法便是奇异值分解 (Singular value decomposition, SVD)。
奇异值分解描述
对任意一个\(m\times n\)阶矩阵\(A_{mn}\)，均存在：
\(A_{mn}=U_{mm}\Sigma_{mn}V^{T}_{nn}\)
其中\(\Sigma\)是对角矩阵，\(U\)和\(V\)均为正交矩阵 (Orthogonal matrix)，即：
\(UU_{T}=I_{mm}\)
\(VV_{T}=I_{nn}\)
\(U\)是由\(AA^{T}\)特征向量 (Eigenvector)组成，\(V\)是由\(A^{T}A\)的特征向量组成，\(\Sigma\)则是由\(A^{T}A, AA^{T}\)的特征值 (Eigenvalue)的平方根组成，
样例
下面看一个例子，先给出一个矩阵\(A\):
\(A=\left[ \begin{array}{cc} 3 & 1 & 1 \\-3 & 1 &1 \\\end{array} \right]\)
则：
\(AA^{T}=\left[ \begin{array}{cc} 11 & 1 \\ 1 & 11 \\\end{array} \right]\)
可以求得特征值为：
\(\lambda_1=10, \lambda_2=12\)
对应的特征向量为：
\(\left[ \begin{array}{cc} 1 & 1 \\ 1 & -1 \\\end{array}\right]\)
然后进行格拉姆-施密特 (Gram-Schmidt)正交化得到：
\(U=\left[\begin{array}{cc} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \\\end{array} \right]\)
同理可以由\(A^{T}A\)得到：
\(V=\left[\begin{array}{cc} \frac{1}{\sqrt{6}} & \frac{2}{\sqrt{5}} & \frac{1}{\sqrt{30}} \\ \frac{2}{\sqrt{6}} & -\frac{1}{\sqrt{5}} & \frac{2}{\sqrt{30}} \\ \frac{1}{\sqrt{6}} & 0 & -\frac{5}{\sqrt{30}}\\\end{array}\right]\)
不过通常我们需要的只是：
\(V^{T}=\left[\begin{array}{cc} \frac{1}{\sqrt{6}} & \frac{2}{\sqrt{6}} & \frac{1}{\sqrt{6}} \\ \frac{2}{\sqrt{5}} & -\frac{1}{\sqrt{5}} & 0 \\ \frac{1}{\sqrt{30}} &\frac{2}{\sqrt{30}} & -\frac{5}{\sqrt{30}}\\\end{array}\right]\)
然后还有：
\(\Sigma=\left[\begin{array}{cc} \sqrt{12} & 0 & 0 \\ 0 & \sqrt{10} & 0\\\end{array}\right]\)
更具体计算过程可以看参考资料中的《SVD-Tutorial-[Kirk-Baker]》，这份文档浅入深出，强烈推荐。
应用
在《数学之美》中曾经提到过奇异值分解在自然语言处理中的应用：
用一个大的矩阵\(A\)来表示数据集，在这个矩阵中，每一行对应一篇文章，每一列对应一个词，\(A_{ij}\)即字典中第\(j\)个词在第\(i\)篇文章中出现的加权词频（比如词的TF-IDF值），然后对\(A\)进行奇异值分解，得到三个矩阵，其中第一个矩阵\(U\)为对文本进行分类的结果，每一行表示一个文档，每一列表示一个语义相近的此类，或者简称为语义列，第三个矩阵\(V^{T}\)则是对词的分类结果，每一列对应一个词，每一行对应一个主题，中间的矩阵\(\Sigma\)则表示文本的类和词的类之间的相关性，所以奇异值分解也是隐性语义分析 (Latent semantic analysis, LSA) 的主要实现方法。
除了在自然语言处理领域有使用，奇异值分解同样还可以应用在图像处理领域。图像本身就是由R, G, B三个颜色矩阵\(A_{R}\), \(A_{G}\), \(A_{B}\) 组成，在对矩阵\(A_{R}\), \(A_{G}\), \(A_{B}\) 进行奇异值分解过后可以得到：
\(A_{R}=U_{R}\Sigma_{R}V^{T}_{R}, A_{G}=U_{G}\Sigma_{G}V^{T}_{G}, A_{B}=U_{B}\Sigma_{B}V^{T}_{B}\)
以其中的\(A_{R}\)为例，假设矩阵都是\(n\times n\)阶，我们可以只取\(U_{R}\)的前\(k\)列，记作\(U^{k}_{R}\)，取\(\Sigma_{R}\)的前\(k\)个对角线元素组成\(k\times k\)对角矩阵记作\(\Sigma^{k}_{R}\)，\(V_{R}\)也只取前\(k\)列，记作\(V^{k}_{R}\)，因此我们可以用一组比\(n\)低维的数据来重新构造\(A^{k}_{R}=U^{k}_{R}\Sigma^{k}_{R}V^{k}_{R}\)，对另外两个矩阵也做相同的处理，最后便可以实现图像的压缩了，实验效果如下：
\(p\)是压缩比，100%的时候是未压缩的，我们可以看到，在\(k\)只取到\(n\)的五分之一的时候原图像的信息基本都还有保存，效果还是很不错的。在此也给出程序的实现代码，有兴趣的自己可以去试一试：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#!/usr/bin/env python # -*- coding: utf-8 -*- ''' Author: razrlele Email: razrlele@gmail.com ''' from PIL import Image import numpy as np import sys def rebuild_img(u, sigma, v, p): # p stands for the percentage of SVD. print p m = len(u) n = len(v) a = np.zeros((m,n)) count = (int)(sum(sigma)) curSum = 0 k = 0 while curSum <= count * p: uk = u[:, k].reshape(m, 1) vk = v[k].reshape(1, n) a += sigma[k] * np.dot(uk, vk) curSum += sigma[k] k += 1 print 'k:', k a[a < 0] = 0 a[a > 255] = 255 return np.rint(a).astype("uint8") if __name__ == "__main__": img = Image.open(sys.argv[1], 'r') a = np.array(img) for p in np.arange(0.1, 1, 0.1): u, sigma, v = np.linalg.svd(a[:, :, 0]) R = rebuild_img(u, sigma, v, p) u, sigma, v = np.linalg.svd(a[:, :, 1]) G = rebuild_img(u, sigma, v, p) u, sigma, v = np.linalg.svd(a[:, :, 2]) B = rebuild_img(u, sigma, v, p) I = np.stack((R, G, B), 2) Image.fromarray(I).save("img/svd_" + str(p * 100) + ".jpg") |