简介

We can think of dimensionality reduction as a way of compressing data with some loss, similar to jpg or mp3. Principal Component Analysis (PCA) is one of the most fundamental dimensionality reduction techniques that are used in machine learning. In this module, we use the results from the first three modules of this course and derive PCA from a geometric point of view. Within this course, this module is the most challenging one, and we will go through an explicit derivation of PCA plus some coding exercises that will make us a proficient user of PCA.

PCA 和 Orthogonal Projection, Orthogonal complements，Orthogonal decompostiion, SVD, Eigen vector and Eigen value, Covariance Matrix, Variance, Optimization(maximization or minimization), lower-rank approximation,encoder-decoder 等诸多概念都有着很密切的关系！可以从不同的角度、进行多方位的阐释。

学习目标

总结 PCA

线性代数角度

统计角度

优化角度

用代码实现PCA

探讨当PCA用在 Hight-dimensional 数据时的性质

两个很有用的资料

关于vector space的定义：link.

关于Orthogonal complement: link ; 关于Orthogonal decomposition（正交分解）link.

Orthogonal complement and Orthogonal decomposition（正交补和正交分解）

关键概念为：

If we look at $n$-dimensional vector space $V$ and a $k$-dimensional subspace $W\subset V$, then the orthogonal complement $W^\perp$ is an $(n-k)$-dimensional subspace of $V$ and contains all vectors that are orthogonal to every vector in $W$.
Every vector $\mathbf x \in V$ can be (uniquely) decomposed into $\mathbf x = \sum_{i=1}^k \lambda_i \mathbf w_i + \sum_{j=1}^{n-k}\psi_j \mathbf w^\perp_j, \lambda_i, \psi_j \in \mathbb R,$where $\mathbf w_1, \mathbf w_2,…, \mathbf w_k $ is a basis of $W$ and $\mathbf w_1,\mathbf w_2,…,\mathbf w_{n-k}$ is a basis of $W^\perp$.

PCA 推导

A key idea behind the PCA, is to use orthogonal projections to find a lower representation of the data and retain as much information as possible.

即：利用正交投影找到高维数据的低维表示，同时保证尽量不损失太多有用的信息。

我们的数据集为：

$\mathbf X \in \mathbb R^{m\times n}= \lbrace \mathbf x_1,…,\mathbf x_m\rbrace$[^1] where $\mathbf x_i \in \mathbb R^n \text{ for } i=1,…,$m. i.e. Design matrix $\mathbf X$ contains $m$ examples and each with $n$ features.

PCA 的问题设置和目标

PCA的目的：是“高效地” 将 design matrix 中的向量 $\mathbf x \in \mathbb R^n$ 用低维向量 $\widetilde {\mathbf x} \in \mathbb R^c$ 表示, 其中 $c<n$；从而最终将 design matrix $\color{blue}{\mathbf X\in \mathbb R^{m\times n} \longrightarrow \mathbf X^\prime\in\mathbb R^{m\times c}}$.

回忆上节课的知识：

根据“正交补和正交分解” 小节的知识，For every element $\mathbf x \in \mathbb R^n$, 一定可以唯一的分解为如下形式：
$$
\begin{align}
&\color{blue}{\mathbf x = \widetilde{\mathbf x} + \widetilde{\mathbf x}^\perp}, \text{where: }\\
&\widetilde{\mathbf x}\in W:\text{orthogonal projection of }\mathbf x \text{ onto } W. \\
&W: \text{ is a c-dimensional subspace of } \mathbb R^n.\\
&\widetilde {\mathbf x}^\perp: \text{orthogonal projection of } \mathbf x \text{ onto } W^\perp.\\
&W^\perp:\text{ is a (n-c)-dimensional subspace of } \mathbb R^n.\\
&c: \text{ is a hyperparameter which denote dimensions you want to transform/compress.}
\end{align}
$$

基于以上，我们假设和约定

The basis vectors of $W$ is $\lbrace \mathbf b_1,…,\mathbf b_c \rbrace$ and the basis vectors of $W^\perp$ is $\lbrace \mathbf b^\perp_1,…, \mathbf b^\perp_{n-c} \rbrace$, where every $\mathbf b_i (i=1,…,c)$ and $\mathbf b^\perp_j ( j=1,…,n-c) \in \mathbb R^n$.
We denote the $\mathbf B = [ \mathbf b_1,…,\mathbf b_c ]\in\mathbb R^{n\times c}, \mathbf B^\perp = [\mathbf b^\perp_1,…,\mathbf b^\perp_{n-c}] \in \mathbb R^{n\times(n-c)}$.

由此我们可以得到如下式子：
$$
\begin{align}
\mathbf x &= \color{blue}{\widetilde{\mathbf x} }+ \color{purple}{\widetilde{\mathbf x}^\perp} \in \mathbb R^n\\
& = \color{blue}{\sum_{i=1}^c \lambda_i \mathbf b_i}+ \color{purple}{\sum_{j=1}^{n-c}\psi_j \mathbf b^\perp_j}\\
&=\color{blue}{\mathbf B\lambda}+ \color{purple}{\underbrace{\mathbf B^\perp\mathbf \psi}_{residual/diff} }
\end{align}
$$

$\mathbf b_1,…, \mathbf b_c$ Span the principal subspace $W$. 尽管 $\widetilde{\mathbf x} \in \mathbb R^n$, 但它lives in c-dimensional subspace: $\mathbb R^c$, 因此只需要 c 个 coordinates：$\lambda_1,…,\lambda_c$ 就可以表示它。

根据上一课-“正交投影”的内容，我们知道：
$$
\widetilde{\mathbf x} = \underbrace{\mathbf B(\mathbf B^T\mathbf B)^{-1}\mathbf B^T}_{P} \mathbf x =\mathbf P\mathbf x \\
$$

同时：
$$
\widetilde{\mathbf x}= \mathbf B \underbrace{(\mathbf B^T\mathbf B)^{-1}\mathbf B^T\mathbf x}_{\lambda} = \mathbf B \lambda\\
$$
矩阵 $\mathbf P$ 是 projection matrix，向量 $\mathbf \lambda \in \mathbb R^c$ 是 $\widetilde{\mathbf x}$ 的 “coordinates” or “codes”.

我们将 $\widetilde{\mathbf x}^\perp =\text{difference/error}= \mathbf x - \widetilde{\mathbf x}$ 视为 “error/difference”, PCA 的obejctive就是使其尽可能小。

因此，PCA just want to use $\widetilde{\mathbf x}$ to approximate the original vector $\mathbf x$，i.e. $\mathbf x \approx \widetilde{\mathbf x}$. and meanwhile, retain the error as small as possible.

Remark: both of them is still $\in \mathbb R^n$.

PCA 算法至此似乎告一段落了，因为我们最终得出了对向量 $\mathbf x \in \mathbb R^n$ 近似 $\widetilde{\mathbf x} \in \mathbb R^n$，而 $\widetilde{\mathbf x}$ 可以由其coordinate $\lambda$ 唯一表示（以 $\mathbf B$ 的列为basis vector），那么我们就可以用一个低维的 $\lambda$ 去代替原始的特征向量 $\mathbf x$, 图示如下：
$$
\begin{align}
&\color{red}{\mathbf x} \approx \color{red}{\widetilde{\mathbf x}}\in\mathbb R^n \longleftrightarrow \color{blue}{\lambda}\in \mathbb R^c \text{, so}\\
&\color{red}{\mathbf x}\in\mathbb R^n \longrightarrow \color{blue}{\lambda} \in \mathbb R^c. \\
& \text{dimension reduced!}
\end{align}
$$
Remark:

PCA 就是将向量 $\mathbf x \in \mathbb R^n$ 正交分解为 $\widetilde{\mathbf x} + \widetilde{\mathbf x}^\perp$, 然后“丢弃” $\widetilde{\mathbf x}^\perp$ 将其看做 “error”，并使其最小化从而得到满足需求的 $\widetilde{\mathbf x}$ 及其coordinates $\lambda$, 最终以 $\lambda$ 代替 original vector $\mathbf x$ 来参与后续的计算。

现在的困难是：$\mathbf B$ 和 $\lambda$ 到底如何确定呢（ $\lambda $ 也由 $\mathbf x$ 和 $\mathbf B$ 决定)？向量 $\mathbf x$ 所在的空间$\mathbb R^n$ 无穷多的子空间，选取不同的子空间就对应不同的矩阵 $\mathbf B$, 自然对应很多的 $\widetilde{\mathbf x}$!

因此，我们必须回答以下问题才能最终完成整个PCA的计算过程：

如何选取合适的subspace $W$ (i.e. 如何选取basis vectors $\mathbf b_1,…,\mathbf b_c$),以得到具体的 coordinates $\lambda$ ($\lambda_1,…,\lambda_c$), 才能使得 “误差” 最小？这个所谓的“小” 如何来衡量呢？

我们需要一个objective，我们optimize它可以为我们解答上述问题。

Objective of PCA

现在，我们暂时忘记之前的几个几何概念（如：正交投影，正交补， etc.）与PCA的联系，从PCA的目标函数出发去得到合适的参数：

a lower dimensional subspace: basis vectors are $\mathbf b_1,…,\mathbf b_c$
coordinates corresponding to each original vector (example in data set).

事实上，minimize objective 之后得到的参数，恰恰符合之前纯粹几何角度看待PCA的情况：

对一个向量的所有分解中，投影（正交分解）的结果与original vector 的“误差”最小（用2-norm衡量）。

把 original vector $\mathbf x$ 投影到其上的那些 lower dimensional subspaces ，恰恰就是使得整个数据集的 variance最大的那些 subspace。

也就是说，PCA可以同时从几何与优化的角度解释；而且优化的结果完全包含并符合几何解释。

总之，如果纯粹从几何角度创造PCA的话，我们只能回答“分解必须是正交分解（使用正交投影）”，仅仅到这一步。但无法解决 subspace 的选取问题，即：沿着些 subspace（方向）进行投影，才能保证所有 original vectors 在所有的可能子空间（无穷多）上的投影所得到的 projected vector 与 original vector 之间 difference/ error 的2-norm 之和最小！

回忆PCA的目标：“将高维向量 $\mathbf x \in \mathbb R^n$ , 投影到一个lower-dimensional subspace of $\mathbb R^n$ 得到 $\widetilde{\mathbf x}$ 的同时保留足够多的信息（损失足够少的信息）。”
- 记住，$\widetilde{\mathbf x}$ is still $\in \mathbb R^n$, but it lives in a c-dimensional subspace: $\mathbb R^c$.
- 这里我们用2-norm 来衡量两个向量之间difference的大小。那么根据上小节的内容， “损失最小” 即：使得 $\Vert\mathbf x - \widetilde{\mathbf x}\Vert ^2$ 最小。
我们的数据集 (design matrix) 为：$\mathbf X \in \mathbb R^{m\times m}=\lbrace \mathbf x_1,…,\mathbf x_n\rbrace$, where each $\mathbf x_k (k=1,…,m)\in \mathbb R^n$.

综合1，2，PCA完整的 objective 有如下三种具体形式：

Sum of 2-norm of difference:
$$
\mathcal L(\mathbf B,\lambda) = \frac{1}{m}\sum_{k=1}^m \Vert {\mathbf x}_k - \widetilde{\mathbf x}_k\Vert ^2 \\
$$
Orthogonal projection, say $\mathbf {\widetilde{x}}$ could be represented as a linear combination of the basis vectors of which the projected onto subspaces.
$$
\mathcal L(\mathbf B,\lambda)=\frac{1}{m}\sum_{k=1}^m\Vert \mathbf x_k - \sum_{i=1}^c\lambda_{ik} \mathbf b_i \Vert^2
$$
We can rewrite the form of linear combination as “Matrix-Form”:

$$
\mathcal L(\mathbf B,\lambda) = \frac{1}{m}\sum_{k=1}^m \Vert {\mathbf x}_k - \mathbf B\lambda_k \Vert ^2
$$

符号说明：

$\mathbf x_k$ : k-th vector in design matrix, i.e. k-th example in datasets.
$\widetilde{\mathbf x}_k$ : the projection of $\mathbf x_k$ onto the c-dimensional subspace $\mathbb R^c$.
$\mathbf b_i$ : the i-th basis vector of the subspace $\mathbb R^c$.
$\lambda_{ik}$ : the coordinate that corresponding to the i-th basis vector $\mathbf b_i$ for $\mathbf x_k$.

We also make two general assumptions:

Centering the data: $E[\mathbf X] = \mathbf 0$.
- Means that: $\mathbf x_k := \mathbf x_k - \mathbf \mu$ ($\in \mathbb R^n$.)
The basis vectors $\mathbf b_1,..,\mathbf b_c$ are orthonormal.

Optimization for PCA:

Remark:

和一般地优化问题-“设计objective，minimize/maximize 这个objective function，从而求出optimal parameters” 的流程相同；但从 geometry 角度出发推导、解释、实现PCA的时候，我们是这样思考的：

首先，几何上我们知道有一个lower-dimensional subspace, 并且我们要将 original vector $\mathbf x$ 正交投影到这个subspace 上，得到 $\widetilde{\mathbf x}$。

基于1，根据正交补 and 正交分解的知识，我们知道：$\mathbf x - \widetilde{\mathbf x}$ 就是一个original vector 和 orthogonal projected vector 的距离(误差 or 残差)。

$$
\begin{align}
&\underbrace{\text{min}}{\lambda} \mathcal L \Rightarrow x\\
&\frac{\partial \mathcal L}{\partial \lbrace \lambda{ik},\mathbf b_i\rbrace} = 0\\
&where: i=1,…,c; k=1,…,m
\end{align}
$$

利用多元函数链式法则, 我们得到：

$$
\frac{\partial \mathcal L}{\partial \lbrace \lambda_{ik},\mathbf b_i\rbrace} =\frac{\partial \mathcal L}{\partial \widetilde{\mathbf x}_k}\frac{\partial \widetilde{\mathbf x}k}{\partial \lbrace \lambda{ik},\mathbf b_i\rbrace}
$$

对于每个original vector而言，

PCA 算法

参考资料

关于orthogonal decomposition
关于orthogonal complement
关于PCA
1. Almost all things you need to know about PCA.
2. Asad

[^1]: 这里可能使得读者在概念上产生一定的混淆，实际上这里 design matrix 采用了两种表示方式，第一种即矩阵表示，行的个数代表 # of examples, 列的个数代表 # of features/dimensions；第二种是采用集合的表示方式，其中每个元素都是design matrix 中的一行值构成的列向量。这仅仅是符号上的选择，无关乎问题本质。