Question

1. 主成分分析Principal Component Analysis:PCA是最常用的一种降维方法。

2.1 PCA 原理

2.1.1 坐标变换

1. 给定数据集 $ MathJax-Element-778 $ ，其中 $ MathJax-Element-100 $ 。假定样本经过了中心化，即：

   $ \mathbf{\vec x}_i \leftarrow\mathbf{\vec x}_i- \frac 1N \sum_{j=1}^{N}\mathbf{\vec x}_j $
   • $ MathJax-Element-746 $ 称作数据集 $ MathJax-Element-841 $ 的中心向量，它的各元素就是各个特征的均值。
   • 之所以进行中心化，是因为经过中心化之后常规的线性变换就是绕原点的旋转变换，也就是坐标变换。

2. 假设坐标变换矩阵为 $ MathJax-Element-103 $ ，经过变换之后样本 $ MathJax-Element-753 $ 的坐标为： $ MathJax-Element-105 $ 。其中 $ MathJax-Element-106 $ ， $ MathJax-Element-107 $ 。

   令 $ MathJax-Element-108 $ ，它表示样本 $ MathJax-Element-753 $ 降低到 $ MathJax-Element-586 $ 维度。令 $ MathJax-Element-111 $ ，则有： $ MathJax-Element-192 $ 。

   根据坐标变换矩阵的性质，有：

   • $ MathJax-Element-113 $ ， $ MathJax-Element-114 $ 。
   • $ MathJax-Element-115 $ 。
   • $ MathJax-Element-116 $ ， $ MathJax-Element-117 $ 。

3. 对数据集 $ MathJax-Element-138 $ 中的样本 $ MathJax-Element-917 $ ，降维后的数据为 $ MathJax-Element-937 $ 。令：

   $ \mathbf X=\begin{bmatrix} \mathbf{\vec x}_1^T\\ \vdots\\ \mathbf{\vec x}_N^T \end{bmatrix}= \begin{bmatrix} x_{1,1}&x_{1,2}&\cdots&x_{1,n}\\ x_{2,1}&x_{2,2}&\cdots&x_{2,n}\\ \vdots&\vdots&\ddots&\vdots\\ x_{N,1}&x_{N,2}&\cdots&x_{N,n}\\ \end{bmatrix}\quad \mathbf Z=\begin{bmatrix} \mathbf{\vec z}_1^T\\ \vdots\\ \mathbf{\vec z}_N^T \end{bmatrix}= \begin{bmatrix} z_{1,1}&z_{1,2}&\cdots&z_{1,d}\\ z_{2,1}&z_{2,2}&\cdots&z_{2,d}\\ \vdots&\vdots&\ddots&\vdots\\ z_{N,1}&z_{N,2}&\cdots&z_{N,d}\\ \end{bmatrix} $

   即 $ MathJax-Element-676 $ 的第 $ MathJax-Element-874 $ 行就是样本 $ MathJax-Element-123 $ ， $ MathJax-Element-388 $ 的第 $ MathJax-Element-874 $ 行就是降维后的数据 $ MathJax-Element-126 $ 。

   • 令 $ MathJax-Element-127 $ ，它表示 $ MathJax-Element-676 $ 的第 $ MathJax-Element-875 $ 列，也就是原始的第 $ MathJax-Element-875 $ 个特征。
   • 令 $ MathJax-Element-131 $ ，它表示 $ MathJax-Element-388 $ 的第 $ MathJax-Element-875 $ 列 ，也就是降维之后的第 $ MathJax-Element-875 $ 个特征。

   则根据 $ MathJax-Element-135 $ ，有 ：

   $ \mathbf{\vec v}_j = \sum_{k=1}^n w_{j,k} \mathbf{\vec u}_j $

   因此降维的物理意义为：通过线性组合原始特征，从而去掉一些冗余的或者不重要的特征、保留重要的特征。

2.1.2 重构误差

1. 考虑对 $ MathJax-Element-607 $ 进行重构，重构之后的样本为： $ MathJax-Element-137 $ 。

   对整个数据集 $ MathJax-Element-138 $ 所有重建样本与原始样本的误差为：

   $ \sum_{i=1}^{N} ||\hat{\mathbf {\vec x}}_i- \mathbf{\vec x}_i ||_2^{2}=\sum_{i=1}^{N} ||\mathbf W\mathbf W^{T} \mathbf {\vec x}_i -\mathbf{\vec x}_i||_2^{2} $

2. 根据定义有：

   $ \mathbf W \mathbf W ^{T} \mathbf {\vec x}_i=(\mathbf {\vec w}_1,\mathbf {\vec w}_2,\cdots,\mathbf {\vec w}_d)\begin{bmatrix}\mathbf {\vec w}_1^{T}\\ \mathbf {\vec w}_2^{T}\\ \vdots \\ \mathbf {\vec w}_d^{T}\end{bmatrix} \mathbf {\vec x}_i=\sum_{j=1}^{d}\mathbf {\vec w}_j(\mathbf {\vec w}_j^{T} \mathbf {\vec x}_i) $

   由于 $ MathJax-Element-139 $ 是标量，所以有： $ MathJax-Element-140 $ 。

   由于标量的转置等于它本身，所以有： $ MathJax-Element-141 $ 。

   则有：

   $ \sum_{i=1}^{N} ||\hat{\mathbf {\vec x}}_i- \mathbf{\vec x}_i ||_2^{2}=\sum_{i=1}^{N} ||\mathbf W\mathbf W^{T} \mathbf {\vec x}_i-\mathbf{\vec x}_i||_2^{2}\\ =\sum_{i=1}^{N} ||\sum_{j=1}^{d}(\mathbf {\vec x}_i^T\mathbf {\vec w}_j )\mathbf {\vec w}_j -\mathbf{\vec x}_i ||_2^2\\ =\sum_{i=1}^{N} ||\mathbf{\vec x}_i-\sum_{j=1}^{d}(\mathbf {\vec x}_i^T\mathbf {\vec w}_j )\mathbf {\vec w}_j ||_2^2 $

3. 根据 $ MathJax-Element-676 $ 的定义，可以证明（ $ MathJax-Element-143 $ 为矩阵的Frobenius范数）：

   $ ||\mathbf X- \mathbf X \mathbf W \mathbf W^{T}||_F^{2}=\sum_{i=1}^{N}||\mathbf {\vec x}_i- \sum_{j=1}^{d}(\mathbf {\vec x}_i^{T} \mathbf {\vec w}_j)\mathbf {\vec w}_j||_2^{2} $

   证明：

   $ \mathbf X- \mathbf X \mathbf W \mathbf W^{T}=\mathbf X-\begin{bmatrix} \mathbf{\vec x}_1^T\\ \vdots\\ \mathbf{\vec x}_N^T \end{bmatrix} \begin{bmatrix}\mathbf{\vec w}_1,\mathbf{\vec w}_2,\cdots,\mathbf{\vec w}_d\end{bmatrix} \begin{bmatrix} \mathbf{\vec w}_1^T\\ \vdots\\ \mathbf{\vec w}_d^T \end{bmatrix}\\ =\mathbf X- \begin{bmatrix} \mathbf{\vec x}_1^T\mathbf{\vec w}_1&\cdots&\mathbf{\vec x}_1^T\mathbf{\vec w}_d\\ \vdots&\ddots&\vdots\\ \mathbf{\vec x}_N^T\mathbf{\vec w}_1&\cdots&\mathbf{\vec x}_N^T\mathbf{\vec w}_d \end{bmatrix} \begin{bmatrix} \mathbf{\vec w}_1^T\\ \vdots\\ \mathbf{\vec w}_d^T \end{bmatrix}\\ =\mathbf X- \begin{bmatrix} \sum_{k=1}^dw_{k,1}\times \mathbf{\vec x}_1^T\mathbf{\vec w}_k&\cdots&\sum_{k=1}^dw_{k,n}\times \mathbf{\vec x}_1^T\mathbf{\vec w}_k\\ \vdots&\ddots&\vdots\\ \sum_{k=1}^dw_{k,1}\times \mathbf{\vec x}_N^T\mathbf{\vec w}_k&\cdots&\sum_{k=1}^dw_{k,n}\times \mathbf{\vec x}_N^T\mathbf{\vec w}_k\\ \end{bmatrix} $

   则有：

   $ ||\mathbf X- \mathbf X \mathbf W \mathbf W^{T}||_F^{2}=\sum_{i=1}^N\sum_{j=1}^n\left[x_{i,j}-\left(\sum_{k=1}^dw_{k,j}\times \mathbf{\vec x}_i^T\mathbf{\vec w}_k\right)\right]^2\\ =\sum_{i=1}^N|| \mathbf{\vec x}_i - \sum_{k=1}^d(\mathbf{\vec x}_i^T\mathbf{\vec w}_k)\mathbf{\vec w}_k||_2^2 $

   将最后的下标从 $ MathJax-Element-395 $ 替换为 $ MathJax-Element-875 $ 即可得证。

4. PCA降维要求重构误差最小。现在求解最优化问题：

   $ \mathbf W^{*}=\arg\min_{\mathbf W}\sum_{i=1}^{N}||\hat{\mathbf {\vec x}}_i- \mathbf{\vec x}_i ||_2^{2} =\arg\min_{\mathbf W} ||\mathbf X - \mathbf X \mathbf W\mathbf W^{T}||_F^{2} \\ =\arg\min_{\mathbf W}tr\left[(\mathbf X - \mathbf X \mathbf W\mathbf W^{T})^{T}(\mathbf X - \mathbf X \mathbf W\mathbf W^{T})\right]\\ =\arg\min_{\mathbf W}tr\left[(\mathbf X^T- \mathbf W\mathbf W^{T}\mathbf X^T)(\mathbf X - \mathbf X \mathbf W\mathbf W^{T})\right] \\ =\arg\min_{\mathbf W}tr\left[ \mathbf X^T\mathbf X-\mathbf X ^T\mathbf X \mathbf W\mathbf W^{T}-\mathbf W\mathbf W^{T}\mathbf X^T\mathbf X + \mathbf W\mathbf W^{T}\mathbf X^T\mathbf X \mathbf W\mathbf W^{T}\right]\\ =\arg\min_{\mathbf W}\left[ tr(\mathbf X^T\mathbf X )-tr(\mathbf X^T \mathbf X \mathbf W\mathbf W^{T})-tr(\mathbf W\mathbf W^{T}\mathbf X^T\mathbf X) +tr(\mathbf W\mathbf W^{T}\mathbf X^T\mathbf X \mathbf W\mathbf W^{T})\right] $

   • 因为矩阵及其转置的迹相等，因此 $ MathJax-Element-146 $ 。

     由于可以在 $ MathJax-Element-147 $ 中调整矩阵的顺序，则 $ MathJax-Element-148 $ 。

     考虑到：

     $ \mathbf W^{T} \mathbf W=\begin{bmatrix}\mathbf {\vec w}_1^{T}\\ \vdots \\ \mathbf {\vec w}_d^{T}\end{bmatrix}(\mathbf {\vec w}_1,\cdots,\mathbf {\vec w}_d) =\mathbf I_{d\times d} $

     代入上式有： $ MathJax-Element-149 $ 。

     于是有：

     $ \mathbf W^{*}=\arg\min_{\mathbf W}\left[tr(\mathbf X^T\mathbf X)-tr(\mathbf X^T\mathbf X \mathbf W\mathbf W^{T})\right] $

   • 由于 $ MathJax-Element-150 $ 与 $ MathJax-Element-775 $ 无关，因此：

     $ \mathbf W^{*} =\arg\min_{\mathbf W} -tr(\mathbf X^{T} \mathbf X \mathbf W\mathbf W^{T}) = \arg\max_{\mathbf W}tr(\mathbf X ^{T}\mathbf X\mathbf W\mathbf W^{T}) $

   • 调整矩阵顺序，则有： $ MathJax-Element-152 $ 。其约束条件为： $ MathJax-Element-153 $ 。

5. PCA 最优化问题需要求解就是 $ MathJax-Element-754 $ 的特征值。

   • 只需要对矩阵 $ MathJax-Element-155 $ 进行特征值分解，将求得的特征值排序： $ MathJax-Element-156 $ 。然后取前 $ MathJax-Element-582 $ 个特征值对应的单位特征向量构成坐标变换矩阵 $ MathJax-Element-168 $ 。
   • 当样本数据进行了中心化时 ， $ MathJax-Element-159 $ 就是样本集的协方差矩阵。这也是为什么需要对样本进行中心化的一个原因。

2.2 PCA 算法

1. PCA 算法：
   

   • 输入：

     • 样本集 $ MathJax-Element-371 $ 。
     • 低维空间维数 $ MathJax-Element-582 $ 。

   • 输出：投影矩阵 $ MathJax-Element-168 $ 。

   • 算法步骤：

     • 对所有样本进行中心化操作： $ MathJax-Element-163 $ 。
     • 计算样本的协方差矩阵 $ MathJax-Element-754 $ 。
     • 对协方差矩阵 $ MathJax-Element-754 $ 做特征值分解。
     • 取最大的 $ MathJax-Element-582 $ 个特征值对应的单位特征向量 $ MathJax-Element-167 $ ，构造投影矩阵 $ MathJax-Element-168 $ 。

2. 通常低维空间维数 $ MathJax-Element-586 $ 的选取有两种方法：
   

   • 通过交叉验证法选取较好的 $ MathJax-Element-586 $ 。“比较好”指的是在降维后的学习器的性能比较好。

   • 从算法原理的角度设置一个阈值，比如 $ MathJax-Element-581 $ ，然后选取使得下式成立的最小的 $ MathJax-Element-582 $ 的值：

     $ \frac{\sum_{i=1}^{d }\lambda_i}{\sum_{i=1}^{n}\lambda_i} \ge t $

     其中 $ MathJax-Element-515 $ 从大到小排列。

2.3 性质

1. 从物理意义上看： 给定协方差矩阵 $ MathJax-Element-754 $ ，通过坐标变换将其对角化为矩阵：

   $ \Lambda=\begin{pmatrix} \lambda_1&0&0&\cdots&0\\ 0&\lambda_2&0&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&\lambda_n\\ \end{pmatrix} $

   这相当于在新的坐标系中：

   • 任意一对特征之间的协方差为 0 。
   • 单个特征的方差为 $ MathJax-Element-175 $ 。

   即：数据在每个维度上尽可能分散，且任意两个维度之间不相关。

   降维的过程就是寻找这样的一个坐标变换，也就是坐标变换矩阵 $ MathJax-Element-775 $ 。

   由于协方差矩阵 $ MathJax-Element-754 $ 是对称矩阵，根据实对称矩阵的性质，这样的坐标变换矩阵一定存在。

2. PCA算法中，低维空间与高维空间必然不相同。因为末尾 $ MathJax-Element-178 $ 个最小的特征值对应的特征向量被抛弃了，这就是降维导致的结果。

   • 舍弃这部分信息之后能使得样本的采样密度增大（因为维数降低了），这是缓解维度灾难的重要手段。
   • 当数据受到噪声影响时，最小特征值对应的特征向量往往与噪声有关，将它们舍弃能在一定程度上起到降噪的效果。

3. PCA降低了输入数据的维度同时保留了主要信息/能量，但是这个主要信息只是针对训练集的，而且这个主要信息未必是重要信息。

   有可能舍弃了一些看似无用的信息，但是这些看似无用的信息恰好是重要信息，只是在训练集上没有很大的表现，所以PCA也可能加剧了过拟合。

4. PCA中训练样本越多越好。

   • 如果训练样本太少，则训练集很有可能“偶然”近似落在同一个平面上。

   • 极端情况下，如果样本数量小于目标维度，比如样本数量为 100，目标维度为 1000 维。则这 100个样本总可以构成一个 1000 维的平面，且这样的平面有无穷多个。此时如果进行PCA降维，则前几个特征值 $ MathJax-Element-185 $ 占比非常大。

     但是如果将样本数量扩充为 10000 ，则这些样本构成一个 1000 维的平面的巧合就几乎很难成立。此时如果进行PCA降维，则前几个特征值 $ MathJax-Element-185 $ 占比就会降低。

   • 本质上是因为 $ MathJax-Element-657 $ 决定了协方差矩阵 $ MathJax-Element-754 $ 的秩的上界。

     当 $ MathJax-Element-657 $ 较小时， $ MathJax-Element-184 $ 也会很小，导致大量的特征值 $ MathJax-Element-185 $ 为 0 。

5. PCA不仅将数据压缩到低维，它也使得降维之后的数据各特征相互独立。

   注意：PCA推导过程中，并没有要求数据中心化；但是在推导协方差矩阵时，要求数据中心化。此时：

   $ Var[\mathbf{\vec z}]=\frac{1}{N-1}\mathbf Z^{T}\mathbf Z=\frac{1}{N-1}\Sigma^{2} $

   其中：

   • $ MathJax-Element-186 $ 为 $ MathJax-Element-754 $ 的最大的 $ MathJax-Element-586 $ 个特征值组成的对角矩阵。
   • $ MathJax-Element-388 $ 为降维后的样本集组成的矩阵。

6. 对于训练集、验证集、测试集，当对训练集进行PCA 降维时，也需要对验证集、测试集执行同样的降维。

   注意：对验证集、测试集执行中心化操作时，中心向量必须从训练集计算而来。不能使用验证集的中心向量，也不能用测试集的中心向量。

2.4 最大可分性

1. PCA降维的准则有两个：

   • 最近重构性：样本集中所有点，重构后的点距离原来的点的误差之和最小（就是前面介绍的内容）。
   • 最大可分性：样本点在低维空间的投影尽可能分开。

2. 可以证明，最近重构性就等价于最大可分性。证明如下：

   对于样本点 $ MathJax-Element-917 $ ， 它在降维后空间中的投影是 $ MathJax-Element-937 $ 。 则有： $ MathJax-Element-192 $ 。

   由于样本数据进行了中心化，则投影后样本点的方差是：

   $ \sum_{i=1}^N\mathbf{\vec z}_i \mathbf{\vec z}_i^T=\sum_{i=1}^{N}\mathbf W^T \mathbf {\vec x}_i\mathbf {\vec x}_i^{T}\mathbf W $

   根据 $ MathJax-Element-676 $ 的定义，有： $ MathJax-Element-194 $ 。则样本点的方差最大的优化目标可写作：

   $ \max_{\mathbf W} tr(\mathbf W^T \mathbf X^{T} \mathbf X \mathbf W)\\ s.t. \mathbf W ^{T}\mathbf W=\mathbf I_{d\times d} $

   这就是前面最近重构性推导的结果。

3. LDA 也可以用于降维。对于2维空间降低到1维直线的情况下，它设法将样例投影到某一条直线上，使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离。

   • LDA 考虑的是：向类别区分最大的方向投影。如下图中的绿色投影直线。
   • PCA 考虑的是：向方差最大的方向投影。如下图中的紫色投影直线。

   因此LDA 降维对于类别的区分效果要好的多。

   

2.5 PCA 与 SVD

1. 酉矩阵：若 $ MathJax-Element-897 $ 阶矩阵满足 $ MathJax-Element-196 $ ，则它是酉矩阵。其中 $ MathJax-Element-197 $ 为 $ MathJax-Element-227 $ 的共轭转置。

   $ MathJax-Element-227 $ 为酉矩阵的充要条件是： $ MathJax-Element-200 $ 。

2. 奇异值分解：设 $ MathJax-Element-676 $ 为 $ MathJax-Element-202 $ 阶矩阵，且 $ MathJax-Element-203 $ ，则存在 $ MathJax-Element-657 $ 阶酉矩阵 $ MathJax-Element-218 $ 和 $ MathJax-Element-897 $ 阶酉矩阵 $ MathJax-Element-227 $ ，使得：

   $ \mathbf V^{H}\mathbf X\mathbf U=\begin{bmatrix}\Sigma &\mathbf 0\\ \mathbf 0 & \mathbf 0\end{bmatrix}_{N \times n} $

   其中

   $ \Sigma=\begin{bmatrix} \sigma_1&0&0&\cdots&0\\ 0&\sigma_2&0&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&\sigma_r \end{bmatrix} $

   $ MathJax-Element-208 $ 称作矩阵 $ MathJax-Element-676 $ 的奇异值。

3. 根据酉矩阵的性质， $ MathJax-Element-210 $ ，则有：

   $ \mathbf X=\mathbf V\begin{bmatrix}\Sigma &\mathbf 0\\ \mathbf 0 & \mathbf 0\end{bmatrix}_{N \times n} \mathbf U^{H} \Longrightarrow \mathbf X^{H}=\mathbf U\begin{bmatrix}\Sigma &\mathbf 0\\ \mathbf 0 & \mathbf 0\end{bmatrix}_{n \times N}\mathbf V^{H} \ $

   则有 $ MathJax-Element-211 $ ， 其中 $ MathJax-Element-412 $ 是个 $ MathJax-Element-897 $ 阶对角矩阵：

   $ \mathbf M=\begin{bmatrix}\Sigma &\mathbf 0\\ \mathbf 0 & \mathbf 0\end{bmatrix}_{n \times N}\times\begin{bmatrix}\Sigma &\mathbf 0\\ \mathbf 0 & \mathbf 0\end{bmatrix}_{N \times n}= \begin{bmatrix} \lambda_1&0&0&\cdots&0\\ 0&\lambda_2&0&\cdots&0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 0&0&0&\cdots&\lambda_n \end{bmatrix}_{n\times n}\\ \lambda_i=\sigma_i^{2}\quad, i=1,2,\cdots,r\\ \lambda_i=0\quad, i=r+1 ,r+2,\cdots,n $

4. 由数据集 $ MathJax-Element-841 $ 中样本构成的 $ MathJax-Element-676 $ 为实矩阵，因此有 $ MathJax-Element-216 $ 。另外考虑到 $ MathJax-Element-754 $ 为实对称矩阵，因此 $ MathJax-Element-218 $ 也是实矩阵，因此 $ MathJax-Element-219 $ 。 则有：

   $ \mathbf X^{T}\mathbf X=\mathbf U\mathbf M\mathbf U^{T} $

   • 根据 $ MathJax-Element-527 $ ，则有： $ MathJax-Element-221 $ 。

   • 根据 $ MathJax-Element-412 $ 是个对角矩阵的性质，有： $ MathJax-Element-223 $ ，则有： $ MathJax-Element-224 $ 。

     则 $ MathJax-Element-225 $ 就是的 $ MathJax-Element-754 $ 特征值， 其对应的单位特征向量组成正交矩阵 $ MathJax-Element-227 $ 。

     因此SVD奇异值分解等价于PCA主成分分析，核心都是求解 $ MathJax-Element-754 $ 的特征值以及对应的单位特征向量。