Unsupervised Learning: PCA(Ⅱ)

本文主要从组件和SVD分解的角度介绍PCA，并描述了PCA的神经网络实现方式，通过引入宝可梦、手写数字分解、人脸图像分解的例子，介绍了NMF算法的基本思想，此外，还提供了一些PCA相关的降维算法和论文

Reconstruction Component

$u_1,u_2,u_3,...$ ，以MNIST为例，不同的笔画都是一个28×28的vector，把某几个vector加起来，就组成了一个28×28的digit

$x≈c_1u^1+c_2u^2+...+c_ku^k+\bar x$

$x$ $\sum c_iu^i$ $\bar x$

$x=u^1+u^3+u^5$ $\left [\begin{matrix}c_1\ c_2\ c_3...c_k \end{matrix} \right]^T$ 来表示一张digit image，如果component的数目k远比pixel的数目要小，那这个描述就是比较有效的

$u^1$ $u^k$ $x-\bar x$ $\hat x$ 越接近越好：

x-\bar x≈c_1u^1+c_2u^2+...+c_ku^k=\hat x

$||(x-\bar x)-\hat x||$

$u^i$ 去minimize这个error：

L=\min\limits_{u^1,...,u^k}\sum||(x-\bar x)-(\sum\limits_{i=1}^k c_i u^i) ||_2

$z=W\cdot x$ $\{w^1,w^2,...,w^k\}$ $\{u^1,u^2,...,u^k\}$ ，简单证明如下：

$x^i-\bar x≈c_1^i u^1+c_2^i u^2+...$ 都用下图中的矩阵相乘来表示，我们的目标是使等号两侧矩阵之间的差距越小越好

$X_{m×n}$ $U_{m×k}$ $\Sigma_{k×k}$ $V_{k×n}$ 的乘积，其中k为component的数目
$X$ $U$ $u^i$ $\Sigma\cdot V$ $c_k^i$ 那部分的矩阵
$U$ $XX^T$ $XX^T$ $x$ $U$ 就是PCA的k个解
$X$ $w^i$ $u^i$ $c_i$
$x$ $w^i$ $u^i$ $z^i$ $c_i$

$x$ $\left [\begin{matrix}c_1 \ c_2\ ... c_k \end{matrix} \right ]^T$ $x$ $\left [\begin{matrix}c_1 \ c_2\ ... c_k \end{matrix} \right ]^T$ 也是投影结果
$x$ $u_i$ 均为n维列向量
$\begin{split} &x= \left [ \begin{matrix} u_1\ u_2\ ...\ u_k \end{matrix} \right ]\cdot \left [ \begin{matrix} c_1\\ c_2\\ ...\\ c_k \end{matrix} \right ]\\ \\ &\left [ \begin{matrix} x_1\\ x_2\\ ...\\ x_n \end{matrix} \right ]=\left [ \begin{matrix} u_1^1\ u_2^1\ ... u_k^1 \\ u_1^2\ u_2^2\ ... u_k^2 \\ ...\\ u_1^n\ u_2^n\ ... u_k^n \end{matrix} \right ]\cdot \left [ \begin{matrix} c_1\\ c_2\\ ...\\ c_k \end{matrix} \right ]\\ \end{split}$

NN for PCA

$\{w^1,w^2,...,w^k\}$ $\{u^1,u^2,...,u^k\}$

$\hat x=\sum\limits_{k=1}^K c_k w^k$ $\hat x$ $x-\bar x$ $w^k$ $c_k$ 值

$\{w^1,w^2,...,w^k\}$ 这k个vector是标准正交化的(orthonormal)，因此：

c_k=(x-\bar x)\cdot w^k

$x$ 是3维向量，要投影到k=2维的component上：

$x-\bar x$ $w^k$ $x-\bar x$ $w^1_1$ $w^1_2$ $w^1_3$ $w^1$ $c_1$ $w^1$ $w^2$ 也同理

$c_1$ $w^1$ $\hat x$ 的一部分

$c_2$ $w^2$ $\hat x$ $\hat x$ 三个分量的值

$x-\bar x$ $\hat x$ 越接近越好，这件事就叫做Autoencoder
$w^i$ $w^i$ $w^i$ $w^i$ 相互垂直，NN无法做到Reconstruction error比PCA小，因此：
- $W$ 远比用神经网络的方式更快速方便
- 用NN的好处是，它可以使用不止一层hidden layer，它可以做deep autoencoder

Weakness of PCA

PCA有很明显的弱点：

它是unsupervised的，如果我们要将下图绿色的点投影到一维空间上，PCA给出的从左上到右下的划分很有可能使原本属于蓝色和橙色的两个class的点被merge在一起
而LDA则是考虑了labeled data之后进行降维的一种方式，但属于supervised
它是linear的，对于下图中的彩色曲面，我们期望把它平铺拉直进行降维，但这是一个non-linear的投影转换，PCA无法做到这件事情，PCA只能做到把这个曲面打扁压在平面上，类似下图，而无法把它拉开
对类似曲面空间的降维投影，需要用到non-linear transformation

PCA for Pokemon

这里举一个实际应用的例子，用PCA来分析宝可梦的数据

假设总共有800只宝可梦，每只都是一个六维度的样本点，即vector={HP, Atk, Def, Sp Atk, Sp Def, Speed}，接下来的问题是，我们要投影到多少维的空间上？

如果做可视化分析的话，投影到二维或三维平面可以方便人眼观察

$cov(x)$ $\lambda_i$ $\lambda_i$ $\lambda_i$ $\frac{\lambda_i}{\sum\limits_{i=1}^6 \lambda_i}$

$\lambda_5$ $\lambda_6$ 所占比例不高，即第5和第6个principle component(可以理解为维度)所发挥的作用是比较小的，用这两个dimension做投影所得到的variance很小，投影在这两个方向上的点比较集中，意味着这两个维度表示的是宝可梦的共性，无法对区分宝可梦的特性做出太大的贡献，所以我们只需要利用前4个principle component即可

注意到新的维度本质上就是旧的维度的加权矢量和，下图给出了前4个维度的加权情况，从PC1到PC4这4个principle component都是6维度加权的vector，它们都可以被认为是某种组件，大多数的宝可梦都可以由这4种组件拼接而成，也就是用这4个6维的vector做linear combination的结果

我们来仔细分析一下这些组件：

对第一个vector PC1来说，每个值都是正的，因此这个组件在某种程度上代表了宝可梦的强度
对第二个vector PC2来说，防御力Def很大而速度Speed很小，这个组件可以增加宝可梦的防御力但同时会牺牲一部分的速度
如果将宝可梦仅仅投影到PC1和PC2这两个维度上，则降维后的二维可视化图像如下图所示：
从该图中也可以得到一些信息：
- 在PC2维度上特别大的那个样本点刚好对应着普普(海龟)，确实是防御力且速度慢的宝可梦
- 在PC1维度上特别大的那三个样本点则对应着盖欧卡、超梦等综合实力很强的宝可梦

对第三个vector PC3来说，sp Def很大而HP和Atk很小，这个组件是用生命力和攻击力来换取特殊防御力
对第四个vector PC4来说，HP很大而Atk和Def很小，这个组件是用攻击力和防御力来换取生命力
同样将宝可梦只投影到PC3和PC4这两个维度上，则降维后得到的可视化图像如下图所示：
该图同样可以告诉我们一些信息：
- 在PC3维度上特别大的样本点依旧是普普，第二名是冰柱机器人，它们的特殊防御力都比较高
- 在PC4维度上特别大的样本点则是吉利蛋和幸福蛋，它们的生命力比较强

PCA for MNIST

再次回到手写数字识别的问题上来，这个时候我们就可以熟练地把一张数字图像用多个组件(维度)表示出来了：

digit\ image=a_1 w^1+a_2 w^2+...

$w^i$ $w^i$ 也是一张28×28的图像，下图列出了通过PCA得到的前30个组件的形状：

$Cov(x)=\frac{1}{N}\sum (x-\bar x)(x-\bar x)^T$ 的前30个最大的特征值对应的特征向量

PCA for Face

同理，通过PCA找出人脸的前30个组件(维度)，如下图所示：

用这些脸的组件做线性组合就可以得到所有的脸

What happens to PCA

在对MNIST和Face的PCA结果展示的时候，你可能会注意到我们找到的组件好像并不算是组件，比如MNIST找到的几乎是完整的数字雏形，而Face找到的也几乎是完整的人脸雏形，但我们预期的组件不应该是类似于横折撇捺，眼睛鼻子眉毛这些吗？

如果你仔细思考了PCA的特性，就会发现得到这个结果是可能的

digit\ image=a_1 w^1+a_2 w^2+...

$a_i$ 可以是正的也可以是负的，因此我们可以通过把组件进行相加或相减来获得目标图像，这会导致你找出来的component不是基础的组件，但是通过这些组件的加加减减肯定可以获得基础的组件元素

NMF

Introduction

如果你要一开始就得到类似笔画这样的基础组件，就要使用NMF(non-negative matrix factorization)，非负矩阵分解的方法

$X$ 做SVD进行矩阵分解，但并不保证分解后矩阵的正负，实际上当进行图像处理时，如果部分组件的matrix包含一些负值的话，如何处理负的像素值也会成为一个问题(可以做归一化处理，但比较麻烦)

而NMF的基本精神是，强迫使所有组件和它的加权值都必须是正的，也就是说所有图像都必须由组件叠加得到：

$a_1$ $a_2$ ...... be non-negative
- additive combination
$w_1$ $w_2$ ...... be non-negative
- More like “parts of digits”

注：关于NMF的具体算法内容可参考paper(公众号回复“NMF”获取pdf)：

Daniel D. Lee and H. Sebastian Seung. "Algorithms for non-negative matrix factorization."Advances in neural information processing systems. 2001.

NMF for MNIST

在MNIST数据集上，通过NMF找到的前30个组件如下图所示，可以发现这些组件都是由基础的笔画构成：

NMF for Face

在Face数据集上，通过NMF找到的前30个组价如下图所示，相比于PCA这里更像是脸的一部分

More Related Approaches

降维的方法有很多，这里再列举一些与PCA有关的方法：

Multidimensional Scaling (MDS) [Alpaydin, Chapter 6.7]
MDS不需要把每个data都表示成feature vector，只需要知道特征向量之间的distance，就可以做降维，PCA保留了原来在高维空间中的距离，在某种情况下MDS就是特殊的PCA
Probabilistic PCA [Bishop, Chapter 12.2]
PCA概率版本
Kernel PCA [Bishop, Chapter 12.3]
PCA非线性版本
Canonical Correlation Analysis (CCA) [Alpaydin, Chapter 6.9]
CCA常用于两种不同的data source的情况，比如同时对声音信号和唇形的图像进行降维
Independent Component Analysis (ICA)
ICA常用于source separation，PCA找的是正交的组件，而ICA则只需要找“独立”的组件即可
Linear Discriminant Analysis (LDA) [Alpaydin, Chapter 6.8]
LDA是supervised的方式