Principal Component Analysis

29 Nov 2013 Comments

所谓的 PCA(Principal Component Analysis) 就是对数据进行降维。降维好处包括：

• 减小数据规模，使数据更易于处理
• 减少特征冗余，如果两个特征之间高度线性相关，则留下其中一个即可
• 减少数据噪音

Principal Component Analysis

假设原始输入每个 data 是一个 $n$ 维向量 $\left\{x_1, x_2, …, x_n\right\}$，PCA 实现如下操作

$$\left\{x_1, x_2, ..., x_n\right\} \rightarrow \left\{y_1, y_2, ..., y_m\right\} \; (m < n)$$

其中 $x$ 向量和 $y$ 向量可能不在同一空间，其实大多数时候不在一个空间 (所谓的不同的空间其实质就是不同的 basis)

那这一过程如何实现。最简单粗暴的降维方式就是直接将输入数据的第 $m+1$ 维到第 $n$ 维去掉，这样就将数据从 $n$ 维降到 $m$ 维，但这样的方式显然不具有普适性，很可能最 重要的特征就在第 $m+1$ 维到第 $n$ 维。因此我们需要一种能度量降维合理性的指标 (也就是 loss function)。PCA 用的指标就是数据的 variance 最大化，通俗的理解就是 保持数据中尽可能多的信息量不丢失

下面讨论将数据维数降至仅剩 1 维的情况，剩多维的情况类似

将数据降至一维其实等价于选择某一向量，以下将这一向量记为 $\b{v}$，然后将所有的 data point 都 project 到 $\b{v}$ 上，这样问题就变成如何选择 $\b{v}$ 使得 project 到其上的数据的 variance 最大。我们可以先从一个通俗的角度考虑这个问题，如果我将数据 project 到 $\b{v}$ 后所有数据都被 project 到一个点上(比如所有原始数据都在一条直线上，$\b{v}$ 是与该直线垂直的向量)，那信息的丢失就大了。显然 project 上去后点越散保持下了的 信息量也就越大。也就是说 project 后的数据的 variance 越大越好

假设原始输入记为随机向量 $X = \left\{X_1, X_2, …, X_n\right\}$，其中 每一维特征都是一个随机变量，project 后变为 $Y$ (由于只剩一维，所以 $Y$ 是个随机变量，不是随机向量)。令 $\Vert \b{v} \Vert = 1$，则 $Y = \b{v}^{T}X$。project 后的数据的 variance 可以表示为

$$\begin{align*} & \Var(Y) = \Var(\b{v}^{T}X) \\\\ = & \E((\b{v}^{T}X)(\b{v}^{T}X)^{T}) - \E(\b{v}^{T}X)\E((\b{v}^{T}X)^{T}) \\\\ = & \b{v}^{T}\E(XX^{T})\b{v} - \b{v}^{T}\E(X)\E(X^{T})\b{v} \\\\ = & \b{v}^{T}(\E(XX^{T}) - \E(X)\E(X^T))\b{v} \\\\ = & \b{v}^{T}\Sigma \b{v} \\\\ \end{align*}$$

其中 $\Sigma$ 为原始输入各维度特征的协方差矩阵。其中 $\E(\b{v}^{T}X) = \b{v}^{T}\E(X)$ 是根据期望的基本性质得到的，即 $\E(X + Y) = \E(X) + \E(Y)$ 和 $\E(aX) = a\E(X)$

因此最大化 $\Var(Y)$ 的任务就等价于

$$\underset{\left\Vert \b{v} \right\Vert = 1}{\argmax}\;\; \b{v}^T\Sigma \b{v}$$

令 $L(\b{v})=\b{v}^T \Sigma \b{v} - \lambda(\left\Vert \b{v} \right\Vert - 1)$，则有

$$\begin{align*} & L(\b{v})=\b{v}^T \Sigma \b{v} - \lambda(\left\Vert \b{v} \right\Vert - 1) \\\\ \Rightarrow & L(\b{v})=\b{v}^T\Sigma \b{v}- \lambda(\b{v}^T\b{v} - 1) \\\\ \Rightarrow & \frac{\partial L(\b{v})}{\partial \b{v}} = 2\Sigma \b{v} - 2\lambda \b{v} = 0 \\\\ \Rightarrow & \Sigma \b{v}= \lambda \b{v} \\\\ \Rightarrow & \b{v}^T\Sigma \b{v} = \b{v}^T\lambda \b{v} = \lambda \end{align*}$$

上面的倒数第二个式子告诉我们，能最大化 $\b{v}^T \Sigma \b{v}$ 的 $\b{v}$ 是 $\Sigma$ 的 eigenvector，最后一个式子告诉我们这个最大值是 $\Sigma$ 最大的那个 eigenvalue，同时 $\b{v}$ 是这个 eigenvalue 对应的 eigenvector

如果要将数据降至多维，可以参考如下我从 math stackexchange copy 来的答案：

If you want to retain more than one dimension of your data set, in principle what you can do is first find the largest principal component, call it u1, then subtract that out from all the data points to get a “flattened” data set that has no variance along u1. Find the principal component of this flattened data set, call it u2. If you stopped here, u1 and u2 would be a basis of the two-dimensional subspace which retains the most variance of the original data; or, you can repeat the process and get as many dimensions as you want. As it turns out, all the vectors u1, u2, … you get from this process are just the eigenvectors of Σ in decreasing order of eigenvalue. That’s why these are the principal components of the data set.

不过在实际中，直接选取最大的 $m$ 个 eigenvalue 对应的 eigenvector 即是。在得到 $m$ 个 eigenvector 后，假设为 $V = \left\{\b{v}_1, \b{v}_2, …, \b{v}_m\right\}$， 原始数据的 data point $\b{x}$ ($n\times 1$ vector) project 到这 $m$ 个向量上就得到了新的 $m\times 1$ 的向量 $\left\{\b{v}_1^T \b{x}, \b{v}_2^T \b{x}, …, \b{v}_n^T \b{x}\right\}$ 简写为 $V^T \b{x}$

Covariance Matrix

理论上，协方差矩阵 $\Sigma = \E[(X-\E(X))(X-\E(X))^T]$，拆开即：

$$\Sigma = \begin{pmatrix} \E[(X_1-\E(X_1))(X_1-\E(X_1))] & \cdots & \E[(X_1-\E(X_1))(X_n-\E(X_n))] \\\\ \E[(X_2-\E(X_2))(X_1-\E(X_1))] & \cdots & \E[(X_2-\E(X_2))(X_n-\E(X_n))] \\\\ \vdots & \ddots & \vdots \\\\ \E[(X_n-\E(X_n))(X_1-\E(X_1))] & \cdots & \E[(X_n-\E(X_n))(X_n-\E(X_n))] \end{pmatrix}$$

但实际中，我们通常无法得到 $X_i$ 的真实分布，也就无法计算每个特征的真实期望和 方差以及两两特征之间的协方差，因此，我们就用经验(协)方差来代替，即：

$\Sigma_{ii}=\frac{1}{m-1}\sum_{k=1}^{m}(X_{ki}-\bar{X_i})^2$ $\Sigma_{ij}=\frac{1}{m-1}\sum_{k=1}^{m}(X_{ki}-\bar{X_i})(X_{kj}-\bar{X_j})$

其中 $m$ 为训练样本个数，$X_{ki}$ 表示第 $k$ 个样本的第 $i$ 维特征 $\bar{X_i}=\frac{1}{m-1}\sum_{k=1}^{m}X_{ki}$

假设经过中心化处理后数据集为 $\b{X} \in \bb{R}^{n\times m}$，其中每个样本为一列， 那经验协方差矩阵就可以表示为

$$\Sigma = \frac{1}{m-1}\b{X}\b{X}^T$$

PCA As Low Rank Approximation

PCA 还可以从 Low Rank Approximation 的角度进行解读，能够最大化 $\b{v}^T\Sigma\b{v}$ 的 $\b{v}$ 也同时可以最小化如下 objective function

$$\Vert \b{X} - \b{v}\b{v}^T\b{X} \Vert\_F$$

其中 $\b{v}^T\b{X}$ 表示 $\b{X}$ project 到以 $\b{v}$ 为 basis 的空间的坐标，而 $\b{v}(\b{v}^T\b{X})$ 就表示 $\b{v}^T\b{X}$ 在原空间 (与 $\b{X}$ 同空间) 中的坐标，所以 $\b{v}\b{v}^T\b{X}$ 就是对 $\b{X}$ 的 rank 为 1 的近似，下面我们 看看为什么两个 objective function 是等价的

$$\begin{align*} \Vert \b{X} - \b{v}\b{v}^T\b{X} \Vert_F = & \tr((\b{X} - \b{vv}^T\b{X})^T(\b{X} - \b{vv}^T\b{X})) \\\\ = & \tr(\b{X}^T\b{X}) - 2\tr(\b{X}^T\b{vv}^T\b{X}) + \tr(\b{X}^T\b{vv}^T\b{vv}^T\b{X}) \\\\ = & \tr(\b{X}^T\b{X}) - \tr(\b{X}^T\b{vv}^T\b{X}) \\\\ = & \tr(\b{X}^T\b{X}) - \tr(\b{v}^T\b{X}\b{X}^T\b{v}) \; (\because \tr(\b{y}^T\b{z}) = \tr(\b{y}\b{z}^T) \forall \b{y}, \b{z} \in \bb{R}^n) \end{align*}$$

对于最后一个式子，第一项是个 constant，第二项和 $\b{v}^T\Sigma\b{v}$ 就差个 负的系数，因此最大化 $\b{v}^T\Sigma\b{v}$ 就等价于最小化 $\Vert \b{X} - \b{v}\b{v}^T\b{X} \Vert_F$

PCA with SVD

由于 PCA 中涉及对 $\b{XX}^T$ 进行 Eigendecomposition，因此 PCA 可以通过直接对 $\b{X}$ 进行 SVD 来求解，其中的 left singular vector 就是 $\b{XX}^T$ 的 eigenvector，而 singular value 的平方就是 eigenvalue

---

P.S. Covariance

covariance 表示两个随机变量 co-vary 的程度，表针的是他们的线性相关性，且只有它的 sign 是有意义的，正的 covariance 表示两个变量正相关，负的表示负相关， 0 表示不相关。它的 magnitude 与相关程度的强弱无直接关系，能表示相关程度强弱的是 correlation

任意两个随机变量的 covariance 等于 $\E((X-\E(X))(Y-\E(Y)))$

对于包含 $n$ 个特征的输入数据，任意两维特征之间的 covariance 就构成了 covariance matrix

P.S. Sample Variance & Empirical Variance

Sample variance is unbiased estimator of variance, while empirical variance isn’t, search google for proof.