深度学习（二）：主成分分析算法

2019-08-08 本文已影响2人交大小浪花

版权声明:本文为博主原创文章，转载请注明出处和作者，商业转载请联系作者(huxingfei097@163.com)，谢谢合作！

本节内容涉及对主成分分析算法的推导，推导主要应用线性代数知识，如果对线性代数知识不太熟悉，可以参考我的上一篇文章：深度学习（一）：线性代数基础

概念：
主成分分析（principal components analysis, PCA）是一个简单的机器学习降维算法。通俗的讲，PCA降维就是通过线性变换，减少数据维度，保留数据主要的信息。在机器学习中，该技术多应用于数据可视化和特征选择，由于处理的数据是无标签的，通过维度的线性变换而来，所以是无监督降维方法。
直观解释：
数据集合中的样本由实数空间（正交坐标系）中的点表示，空间中的一个坐标轴表示一个变量，规范化处理后得到的数据分布在原点（空间中的原点）附近。主成分分析就是对坐标系进行旋转变换，将数据投影到新坐标系的坐标轴上：新坐标系的第一坐标轴、第二坐标轴等分别表示第一主成分、第二主成分等，数据在每一轴上的坐标值的平方表示相应变量的方差，并且，这个坐标系是在所有可能的新的坐标系中，坐标轴上的方差最大的。下图展示了在二维空间中对一个斜椭圆进行主成分分析（其中，x1，x2为原坐标轴，y1，y2为主成分分析变换之后的坐标系，y1为第一主成分对应原椭圆的长轴，y2为第二主成分对应原椭圆的短轴）：


主成分分析示例	主成分分析的几何解释

上方右图是主成分分析的几何解释。主成分分析要求在新的坐标轴中方差最大，即意味着，对于样本点 A，B，C，投影到y1上得到A'，B'，C'，OA'² + OB'² + OC'²最大，等价于样本点到y1轴的距离的平方和AA'² + AB'² + AC'²最小。所以，主成分分析在旋转变换中等价于选取离样本点的距离平方和最小的轴，作为第一主成分，第二主成分的选取，在保证与已选坐标轴正交的条件下，类似的进行。

算法过程：
主成分分析，首先要对给定数据进行规范化，使得每一变量的平均值为0，方差为1，然后顺序地找一组相互正交的坐标轴。其中，第一个新坐标轴选择是原始数据中方差最大的方向，第二个新坐标轴选取是与第一个坐标轴正交的平面中使得方差最大的，第三个轴是与第1,2个轴正交的平面中方差最大的。依次类推，可以得到n个这样的坐标轴。通过这种方式获得的新的坐标轴，大部分方差都包含在前面k个坐标轴中，后面的坐标轴所含的方差几乎为0。于是，可以忽略余下的坐标轴，只保留前面k个含有绝大部分方差的坐标轴。事实上，这相当于只保留包含绝大部分方差的维度特征，而忽略包含方差几乎为0的特征维度，从而实现对数据特征的降维处理。
主成分分析的求解：
** 设 x 是 m 维随机变量，∑ 是x的协方差矩阵，∑的特征值分别是 λ₁ ≥ λ₁ ≥ λ₂ ≥ ... ≥ λ_m ≥ 0,特征值对应的单位向量分别是 α₁，α₂ ... α_m，则 x 的第k主成分是：
y_k = α_k^T x = α_1kx₁ + α_2kx₂ + ... +α_mkx_m
x 的第k主成分的方差是：
var(y_k) = α_k^T Σ α_k, k = 1,2,3，...，m
即协方差矩阵的第k个特征值（若特征值有重根，对应的特征向量组成m维空间R^m的一个子空间，子空间的维数等于重根数，在子空间任取一个正交坐标系，这个坐标系的单位向量可作为特征向量，取法不唯一！）。
具体推导（拉格朗日乘子法）：
先求 x 的第一主成分 y₁ = α₁^T x。即求系数向量 α₁，其中 α₁ 是在α₁^T α₁ = 1的条件下，x 的所有线性变换中使方差 var(α₁ x) = α₁^T Σα₁ ( 注意：Σ 不是求和符号，而是协方差矩阵，Σ = cov( x , x ) =E[( x - μ)( x - μ)^T] )达到最大(求解约束最优化问题)。
max_{_α₁} = α₁^T Σ α₁ s.t α₁^T α₁ = 1
定义拉格朗日函数：
α₁^T Σα₁ - λ(α₁^T α₁ - 1)
对 α₁ 求导，并令其为0，得：
Σα₁ - λ α₁ = 0
因此，λ 是Σ 的特征值，α₁ 是对应的单位向量。即：
α₁^T Σ α₁ = α₁^T λ α₁ = λ α₁^T α₁ = λ
所以，α₁^T x，构成第一主成分，其方差对于协方差矩阵的最大特征值：
var(α₁^T x) = α₁^T Σ α₁ = λ₁
接着求x的第二主成分 y₂ = α₂^T x，第二主成分是在α₂ 是在α₂^Tα₂ = 1，且 α₂^T x 与 α₁^T x 不相关的条件下，x 的所有线性变换中使方差 var(α₂^T x ) = α₂^T Σ α₂ 达到最大的。
求第二主成分同样需要求解约束最优化问题。
max_{_{_α₂}} α₂^T Σ α₂ α₁^T Σ α₂ = 0，α₂^T Σ α₁，α₂^T α₂ = 0
注意到：
α₁^T Σ α₂ = α₂^T Σ α₁ = α₂^T λα₁ = λ α₂^T α₁ = λ α₁^T α₂
并且：
α₁^T α₂ = 0 α₂^T α₁ = 0
定义拉格朗日函数：
α₂^T Σ α₂ - λ(α₂^T α₂ - 1) - фα₂^T α₁
其中 λ，ф都是拉格朗日乘子，对 α₂ 求导，并令其为0，得到：
2Σ α₂ - 2λ α₂ - фα₁ = 0
将方程左乘 α₁^T：
2α₁^TΣα₂ - 2λ α₁^T α₂ - фα₁^T****α₁ = 0
此式子前两项为0，且 α₁^T****α₁ = 1，得出 ф = 0，则拉格朗日函数导数可以表示为：
Σα₂ - λ α₂ = 0
因此，λ是Σ的特征值，α₂是对应的单位向量。即：
α₂^T Σ α₂ = α₂^T λ α₂ = λα₂^T α₂ = λ
于是 α₂^T x 构成第二主成分，其方差对于协方差矩阵的第二大特征值：
var(α₂^T x) = α₂^T α₂ = λ₂
以此类推， x 的第 k 主成分是 α_k^T x，并且 var(α_k^T x) = λ_k，其中，λ_k是 Σ 的第k个特征值，并且是 α_k 对应的单位特征向量。

花书上采用的是计算 Frobenius 范数来推导的，个人感觉要难懂一些，感兴趣可以看一下
推导过程：
通常使用矩阵乘法来实现PCA。对于每一个点x⁽ⁱ⁾∈Rⁿ,会存在一个编码后的对应向量c⁽ⁱ⁾∈R^l(一般l会小于n)。为了简化，使用矩阵乘法将编码后的向量映射回 Rⁿ，即满足 x ≈ g(c) = D c，其中D∈R^{n * l}是定义的解码矩阵。
PCA算法限定 D 中的列向量彼此正交，并且都有单位范数。
首先需要明确的是如何根据每一个输入 x 得到一个最优编码 c 。一种做法是使用 L² 范数来衡量原始向量 x 与重映射后的结果 g(c)之间的距离。在PCA算法中，使用 L² 范数：

可以使用平方 L² 范数来替代L²范数，即：

该最小化函数可以简化为：
(x -g(c))^T (x -g(c))
= x^T x - x^T g(c) - g(c)^T x + g(c)^T g(c)
= x^T x - 2x^T g(c) + g(c)^T g(c) (g(c)^Tx是一个标量，转置为自身)
因为第一项x^T x不依赖于c，所以可以忽略得到下述优化目标：
c* = (arg min)_c - 2x^T g(c) + g(c)^T g(c)
更进一步，代入g(c)的定义可得：
c* = (arg min)_c - 2x^T D c + c^T D^T D c
（矩阵D的正交性和单位范数约束）
= (arg min)_c - 2x^T D c + c^T I_l c
= (arg min)_c - 2x^T D c + c^Tc
可以通过向量微积分来求解该最优化问题(如果不太清楚矩阵求导，可以参考：矩阵求导术)
∇_c (- 2x^T D c + c^Tc) = 0
- 2D^T x + 2c = 0
c = D^T x
即若要得到最优编码 c，只需要一个矩阵向量乘法即可，可令 f(x) = D^T x，进一步使用矩阵乘法，还可以定义PCA重构(即重新升维到x的维度)操作：
(x≈)r(x) = g(f(x)) = D D^T x
接下来需要挑选编码矩阵D。可以采用最小化所有维度上点的误差矩阵的Frobenius范数：