主成分分析(PCA)的详细推导过程
Overview
Based on Deep Learning (2017, MIT) book.
本文基于Deep Learning (2017, MIT)，推导过程补全了所涉及的知识及书中推导过程中跳跃和省略的部分。 blog
1 概述
现代数据集，如网络索引、高分辨率图像、气象学、实验测量等，通常包含高维特征，高纬度的数据可能不清晰、冗余，甚至具有误导性。数据可视化和解释变量之间的关系很困难，而使用这种高维数据训练的神经网络模型往往容易出现过拟合（维度诅咒）。 主成分分析（PCA）是一种简单而强大的无监督机器学习技术，用于数据降维。它旨在从大型变量集中提取一个较小的数据集，同时尽可能保留原始信息和特征（有损压缩）。PCA有助于识别数据集中最显著和有意义的特征，使数据易于可视化。应用场景包括：统计学、去噪和为机器学习算法预处理数据。
- 主成分是什么？ 主成分是构建为原始变量的线性组合的新变量。这些新变量是不相关的，并且包含原始数据中大部分的信息。
2 背景数学知识
这些知识对下一节的推导很重要。
- 正交向量和矩阵：
- 如果两个向量垂直，则它们是正交的。即两个向量的点积为零。
- 正交矩阵是一个方阵，其行和列是相互正交的单位向量；每两行和两列的点积为零，每一行和每一列的大小为1。
- 如果$A^T=A^{-1}$或$AA^T=A^TA=I$，则$A$是正交矩阵。
- 在机器人学中，旋转矩阵通常是一个$3\times3$的正交矩阵，在空间变换中它会旋转向量的方向但保持原始向量的大小。
- 矩阵、向量乘法规则：
- $(AB)^T=B^TA^T$，两个矩阵的乘积的转置。
- $\vec{a}^T\vec{b}=\vec{b}^T\vec{a}$，两个结果都是标量，标量的转置是相同的。
- $(A + B)C = AC + BC$，乘法是可分配的。
- $AB \neq{} BA$，乘法一般不满足交换律。
- $A(BC)=(AB)C$，乘法满足结合律。
- 对称矩阵：
- $A=A^T$，$A$是对称矩阵。
- $X^TX$是对称矩阵，因为$(X^TX)^T=X^TX$。
- 向量导数规则（$B$是常量矩阵）：
- $d(x^TB)/dx=B$
- $d(x^Tx)/dx=2x$
- $d(x^TBx)/dx=2Bx$
- 矩阵迹规则：
- $Tr(A)=Tr(A^T)$
- $Tr(AB)=Tr(BA)$
- $Tr(A)=\sum_i{\lambda_i}$，其中$\lambda$是$A$的特征值。
- 迹在循环移位下不变：$Tr(ABCD)=Tr(BCDA)=Tr(CDAB)=Tr(DABC)$
- 向量和矩阵范数：
- 向量的$L^2$范数，也称为欧几里得范数：$||x||_2=\sqrt{\sum_i|x_i|^2}$。
- 通常使用平方的$L^2$范数来衡量向量的大小，可以计算为$x^Tx$。
- Frobenius范数用于衡量矩阵的大小：$||A||F=\sqrt{\sum{i,j}A^2_{i,j}}$
- Frobenius范数是所有矩阵元素的绝对平方和的平方根。
- Frobenius范数是矩阵版本的欧几里得范数。
- 特征值分解和特征值：
- 方阵$A$的特征向量是一个非零向量$v$，使得$A$的乘法仅改变$v$的比例：$Av=\lambda v$。$\lambda$是特征值，$v$是特征向量。
- 假设矩阵$A$有$n$个线性无关的特征向量$v^{(i)}$，我们可以将所有特征向量连接起来形成一个矩阵$V=[v^{(1)},\ldots,v^{(n)}]$，并通过连接所有特征值$\lambda=[\lambda_1,\ldots,\lambda_n]^T$形成一个向量，那么$A$的特征分解是$A=Vdiag(\lambda)V^{-1}$
- 每个实对称矩阵都可以分解为$A=Q\Lambda Q^T$，其中$Q$是由$A$的特征向量组成的正交矩阵，$\Lambda$（读作'lambda'）是一个对角矩阵。
- 拉格朗日乘数法：
- 拉格朗日乘数法是一种在方程约束下寻找函数局部最大值和最小值的策略。
- 一般形式：$\mathcal{L}(x,\lambda)=f(x)+\lambda\cdot g(x)$，$\lambda$称为拉格朗日乘子。
3 详细PCA推导
需求描述
我们有$m$个点的输入数据，表示为${x^{(1)},...,x^{(m)}}$在$\mathbb{R}^{n}$的实数集中。因此，每个点$x^{(i)}$是一个列向量，具有$n$维特征。
需要对输入数据进行有损压缩，将这些点编码以表示它们的较低维度版本。换句话说，我们想要找到编码向量$c^{(i)}\in \mathbb{R}^{l}$，$(l<n)$来表示每个输入点$x^{(i)}$。我们的目标是找到产生输入的编码向量的编码函数$f(x)=c$，以及相应的重构（解码）函数$x\approx g(f(x))$，根据编码向量$c$计算原始输入。
解码的$g(f(x))$是一组新的点（变量），因此它与原始$x$是近似的。存储$c^{(i)}$和解码函数比存储$x^{(i)}$更节省空间，因为$c^{(i)}$的维度较低。
解码矩阵
我们选择使用矩阵$D$作为解码矩阵，将编码向量$c^{(i)}$映射回$\mathbb{R}^{n}$，因此$g(c)=Dc$，其中$D\in \mathbb{R}^{n\times l}$。为了简化编码问题，PCA将$D$的列约束为彼此正交。
衡量重构的表现
在继续之前，我们需要弄清楚如何生成最优的编码点$c^{}$，我们可以测量输入点$x$与其重构$g(c^)$之间的距离，使用$L^2$范数（或欧几里得范数）：$c^{*}=\arg\min_c||x-g(c)||_2$。由于$L^2$范数是非负的，并且平方操作是单调递增的，所以我们可以转而使用平方的$L^2$范数：
$$c^{*}={\arg\min}_c||x-g(c)||_2^2$$ 向量的$L^2$范数是其分量的平方和，它等于向量与自身的点积，例如$||x||_2=\sqrt{\sum|x_i|^2}=\sqrt{x^Tx}$，因此平方的$L^2$范数可以写成以下形式：
$$||x-g(c)||_2^2 = (x-g(c))^T(x-g(c))$$ 由分配率： $$=(x^T-g(c)^T)(x-g(c))=x^Tx-x^Tg(c)-g(c)^Tx+g(c)^Tg(c)$$ 由于$x^Tg(c)$和$g(c)^Tx$是标量，标量等于其转置，$(g(c)^Tx)^T=x^Tg(c)$，所以： $$=x^Tx-2x^Tg(c)+g(c)^Tg(c)$$ 为了找到使上述函数最小化的$c$，第一项可以省略，因为它不依赖于$c$，所以： $$c^={\arg\min}_c-2x^Tg(c)+g(c)^Tg(c)$$ 然后用$g(c)$的定义$Dc$进行替换： $$={\arg\min}_c-2x^TDc+c^TD^TDc$$ 由于$D$的正交性和单位范数约束： $$c^={\arg\min}_c-2x^TDc+c^TI_lc$$ $$= {\arg\min}_c-2x^TDc+c^Tc$$
目标函数
现在目标函数是$-2x^TDc+c^Tc$，我们需要找到$c^*$来最小化目标函数。使用向量微积分，并令其导数等于0： $$\nabla_c(-2x^TDc+c^Tc)=0$$ 根据向量导数规则： $$-2D^Tx+2c=0 \Rightarrow c=D^Tx$$
找到编码矩阵 $D$
所以编码器函数是 $f(x)=D^Tx$。因此我们可以定义 PCA 重构操作为 $r(x)=g(f(x))=D(D^Tx)=DD^Tx$。
因此编码矩阵 $D$ 也被重构过程使用。我们需要找到最优的 $D$ 来最小化重构误差，即输入和重构之间所有维度特征的距离。这里使用 Frobenius 范数（矩阵范数）定义目标函数：
$$D^={\arg\min}D\sqrt{\sum{i,j}(x_j^{(i)}-r(x^{i})_j)^2},\quad D^TD=I_l$$
从考虑 $l=1$ 的情况开始（这也是第一个主成分），$D$ 是一个单一向量 $d$，并使用平方 $L^2$ 范数形式：
$$d^={\arg\min}d{\sum{i}||(x^{(i)}-r(x^{i}))}||_2^2, ||d||_2=1$$
$$ = {\arg\min}d{\sum{i}||(x^{(i)}-dd^Tx^{(i)})||_2^2}, ||d||_2=1$$
$d^Tx^{(i)}$ 是一个标量：
$$= {\arg\min}d{\sum{i}||(x^{(i)}-d^Tx^{(i)}d)}||_2^2, ||d||_2=1$$
标量等于其自身的转置：
$$d^*= {\arg\min}d{\sum{i}||(x^{(i)}-x^{(i)T}dd)}||_2^2, ||d||_2=1$$
使用矩阵形式表示
令 $X\in \mathbb{R}^{m\times n}$ 表示所有描述点的向量堆叠，即 ${x^{(1)^T}, x^{(2)^T}, \ldots, x^{(i)^T}, \ldots, x^{(m)^T}}$，使得 $X_{i,:}=x^{(i)^T}$。
$$ X = \begin{bmatrix} x^{(1)^T}\ x^{(2)^T}\ \ldots\ x^{(m)^T} \end{bmatrix} \Rightarrow Xd = \begin{bmatrix} x^{(1)^T}d\ x^{(2)^T}d\ \ldots\ x^{(m)^T}d \end{bmatrix} $$
$$ \Rightarrow Xdd^T = \begin{bmatrix} x^{(1)^T}dd^T\ x^{(2)^T}dd^T\ \ldots\ x^{(m)^T}dd^T\ \end{bmatrix} $$
$$ \Rightarrow X-Xdd^T = \begin{bmatrix} x^{(1)^T}-x^{(1)^T}dd^T\ x^{(2)^T}-x^{(2)^T}dd^T\ \ldots\ x^{(m)^T}-x^{(m)^T}dd^T\ \end{bmatrix} $$
矩阵中的一行的转置： $$(x^{(i)^T}-x^{(i)^T}dd^T)^T=x^{(i)}-dd^Tx^{(i)}$$ 由于 $d^Tx^{(i)}$ 是标量： $$=x^{(i)}-d^Tx^{(i)}d=x^{(i)}-x^{(i)^T}dd$$ 所以我们知道 $X$ 的第 $i$ 行的 $L^2$ 范数与原始形式相同，因此我们可以使用矩阵重写问题，并省略求和符号： $$d^={\arg\min}{d}||X-Xdd^T||F^2, \quad d^Td=1 $$ 利用矩阵迹规则简化 Frobenius 范数部分如下： $${\arg\min}{d}||X-Xdd^T||F^2$$ $$={\arg\min}{d}Tr((X-Xdd^T)^T(X-Xdd^T))$$ $$={\arg\min}{d}-Tr(X^TXdd^T)-Tr(dd^TX^TX)+Tr(dd^TX^TXdd^T)$$ $$={\arg\min}{d}-2Tr(X^TXdd^T)+Tr(X^TXdd^Tdd^T)$$ 由于 $d^Td=1$： $$={\arg\min}{d}-2Tr(X^TXdd^T)+Tr(X^TXdd^T)$$ $$={\arg\min}{d}-Tr(X^TXdd^T)$$ $$={\arg\max}{d}Tr(X^TXdd^T)$$ 由于迹是循环置换不变的，将方程重写为： $$d^={\arg\max}{d}Tr(d^TX^TXd), \quad d^Td=1$$ 由于 $d^TX^TXd$ 是实数，因此迹符号可以省略： $$d^*={\arg\max}{d}d^TX^TXd,\quad d^Td=1$$
寻找最优的 $d$
现在的问题是找到最优的 $d$ 来最大化 $d^TX^TXd$，并且有约束条件 $d^Td=1$。
使用拉格朗日乘子法来将问题描述为关于 $d$ 的形式：
$$\mathcal{L}(d,\lambda)=d^TX^TXd+\lambda(d^Td-1)$$
对 $d$ 求导数（向量导数规则）：
$$\nabla_d\mathcal{L}(d,\lambda)=2X^TXd+2\lambda d$$
令导数等于0，$d$ 将是最优的：
$$2X^TXd+2\lambda d=0$$
$$X^TXd=-\lambda d$$
$$X^TXd=\lambda' d,\quad(\lambda'=-\lambda)$$
这个方程是典型的矩阵特征值分解形式，$d$ 是矩阵 $X^TX$ 的特征向量，$\lambda'$ 是对应的特征值。
利用上述结果，让我们重新审视原方程：
$$d^*={\arg\max}{d}d^TX^TXd, \quad d^Td=1$$
$$={\arg\max}{d}d^T\lambda' d$$
$$={\arg\max}{d}\lambda'd^T d$$
$$={\arg\max}{d}\lambda'$$
现在问题已经变的非常清楚了，$X^TX$ 的最大特征值会最大化原方程的结果，因此最优的 $d$ 是矩阵 $X^TX$ 对应最大特征值的特征向量。
这个推导是针对 $l=1$ 的情况，只包含第一个主成分。当 $l>1$ 时，$D=[d_1, d_2, \ldots]$，第一个主成分 $d_1$ 是矩阵 $X^TX$ 对应最大特征值的特征向量，第二个主成分 $d_2$ 是对应第二大特征值的特征向量，以此类推。
4 总结
我们有一个数据集，包含 $m$ 个点，记为 ${x^{(1)},...,x^{(m)}}$。 令 $X\in \mathbb{R}^{m\times n}$ 为将所有这些点堆叠而成的矩阵：$[x^{(1)^T}, x^{(2)^T}, \ldots, x^{(i)^T}, \ldots, x^{(m)^T}]$。
主成分分析（PCA）编码函数表示为 $f(x)=D^Tx$，重构函数表示为 $x\approx g(c)=Dc$，其中 $D=[d_1, d_2, \ldots]$ 的列是 $X^TX$ 的特征向量，特征向量对应的特征值大小为降序排列。$D^Tx$即是降维度之后的数据。