# 降维

## 背景

解决过拟合的方法有：

* 正则化
* 添加数据
* 降维

维度过高会造成维度灾难，维度灾难是造成过拟合的主要原因。在不充足的数据情况下，主要采用降维的方法。

从几何的角度来看维度灾难：

$$n$$ 维球的体积为：

$$
CR^n
$$

那么在球体积与边长为 $$2R$$ 的超立方体比值为：

$$
\lim\limits\_{n\rightarrow0}\frac{CR^n}{2^nR^n}=0
$$

这就是所谓的维度灾难，在高维数据中，主要样本都分布在立方体的边缘，所以数据集更加稀疏。

降维的方法有：

* 直接降维：特征选择
* 线性降维：PCA、MDS等
* 非线性降维：流形（lsomap、LLE等）

## 样本均值&样本方差矩阵

假设数据集$$X={x\_1,x\_2,\cdots,x\_N}$$，$$x\_i\in\mathbb{R},i=1,2,\cdots,N$$,记为：

$$
\begin{align} X&=(x\_1,x\_2,\cdots,x\_N)^T \ &= \begin{bmatrix} x\_{1}^T \ x\_{2}^T \ \vdots \ x\_{N}^T \ \end{bmatrix}*{N\times p} \ & = \begin{bmatrix} x*{11} & x\_{12} & \cdots & x\_{1p} \ x\_{21} & x\_{22} & \cdots & x\_{2p} \ \vdots & \vdots & \ddots & \vdots \ x\_{N1} & x\_{N2} & \cdots & x\_{Np} \ \end{bmatrix}\_{N\times p} \ \end{align}
$$

Sample Mean（样本均值）：

$$
\begin{align} \bar X\_{p \times 1}&= \frac{1}{N}\sum\_N^{i=1}x\_i\ &=\frac{1}{N}(x\_1,x\_2,\cdots,x\_N) \begin{bmatrix} 1 \ 1 \ \vdots \ 1 \ \end{bmatrix}\_{N\times 1} \ &= \frac{1}{N} X^t \mathbb{I}\_N \end{align}
$$

Sample Coveriance（样本协方差）：

$$
\begin{align} S\_{p \times p} &= \frac{1}{N}\sum\_N^{i=1}(x\_i-\bar x)(x\_i-\bar x)^T\ &=\frac{1}{N}(x\_1-\overline{x},x\_2-\overline{x},\cdots,x\_N-\overline{x})(x\_1-\overline{x},x\_2-\overline{x},\cdots,x\_N-\overline{x})^T\nonumber\ &=\frac{1}{N}(X^T-\frac{1}{N}X^T\mathbb{I}*{N1}\mathbb{I}*{N1}^T)(X^T-\frac{1}{N}X^T\mathbb{I}*{N1}\mathbb{I}*{N1}^T)^T\nonumber\ &=\frac{1}{N}X^T(E\_N-\frac{1}{N}\mathbb{I}*{N1}\mathbb{I}*{1N})(E\_N-\frac{1}{N}\mathbb{I}*{N1}\mathbb{I}*{1N})^TX\nonumber\ &=\frac{1}{N}X^TH\_NH\_N^TX\nonumber\ &=\frac{1}{N}X^TH\_NH\_NX=\frac{1}{N}X^THX \end{align}
$$

这个式子利用了中心矩阵 $$H$$的对称性，这也是一个投影矩阵。

$$
\begin{align} \&H = E\_N-\frac{1}{N}\mathbb{I}*{N1}\mathbb{I}*{1N} \ \&H^T = H \ \&H^2 = H \ &... \ & H^n H \end{align}
$$

## 线性降维-主成分分析 PCA

即，主成分分析中，基本想法是将所有数据投影到一个字空间中，从而达到降维的目标，为了寻找这个子空间，我们基本想法是：

1. 所有数据在子空间中更为分散
2. 损失的信息最小，即：在补空间的分量少

> 一个中心：对原始特征空间的重构（相关->无关）
>
> 两个基本点：最大投影方差，最小重构距离

原来的数据很有可能各个维度之间是相关的，于是希望找到一组 $$p$$个新的线性无关的单位基 $$u\_i$$，降维就是取其中的 $$q$$ 个基。于是对于一个样本 $$x\_i$$，经过这个**坐标变换**后：

$$
\hat{x\_i}=\sum\limits\_{i=1}^p(u\_i^Tx\_i)u\_i=\sum\limits\_{i=1}^q(u\_i^Tx\_i)u\_i+\sum\limits\_{i=q+1}^p(u\_i^Tx\_i)u\_i
$$

### 最大投影方差

对于数据集来说，首先将其中心化然后再去上面的式子的**第一项**，并使用其系数的平方平均作为损失函数并最大化：

$$
\begin{align}J&=\frac{1}{N}\sum\limits\_{i=1}^N\sum\limits\_{j=1}^q((x\_i-\overline{x})^Tu\_j)^2\nonumber\ &=\sum\limits\_{j=1}^qu\_j^TSu\_j\ ,\ s.t.\ u\_j^Tu\_j=1 \end{align}
$$

由于每个基都是线性无关的，于是每一个 $$u\_j$$ 的求解可以分别进行，使用拉格朗日乘子法：

$$
\mathop{argmax}*{u\_j}L(u\_j,\lambda)=\mathop{argmax}*{u\_j}u\_j^TSu\_j+\lambda(1-u\_j^Tu\_j)
$$

于是：

$$
\begin{align} &\frac{\partial}{\partial u\_j}L(u\_j)= 2Su\_j-2\lambda u\_j)=0 \ &有，Su\_j=\lambda u\_j \end{align}
$$

> $$u\_j$$：S的特征向量，$$\lambda$$：特征值

### 最小重构距离

下面看其损失的信息最少这个条件，同样适用系数的平方平均作为损失函数，并最小化：

$$
\begin{align}J&=\frac{1}{N}\sum\limits\_{i=1}^N\sum\limits\_{j=q+1}^p((x\_i-\overline{x})^Tu\_j)^2\nonumber\ &=\sum\limits\_{j=q+1}^pu\_j^TSu\_j\ ,\ s.t.\ u\_j^Tu\_j=1 \end{align}
$$

> (原坐标-新坐标)的平方

同样的：

$$
\mathop{argmin}*{u\_j}L(u\_j,\lambda)=\mathop{argmin}*{u\_j}u\_j^TSu\_j+\lambda(1-u\_j^Tu\_j)
$$

损失函数最小取在本征值剩下的个最小的几个值。数据集的协方差矩阵可以写成 $S=U\Lambda U^T$，直接对这个表达式可以得到本征矢。

> $$\lambda$$为最小的，$$\Lambda$$为特征值矩阵

## SVD 与 PCoA

下面使用实际训练时常常使用的 `SVD(奇异值分解)` 直接求得这个 $$q$$ 个本征矢。

对中心化后的数据集进行奇异值分解：

$$
HX=U\Sigma V^T,U^TU=E\_N,V^TV=E\_p,\Sigma:N\times p
$$

> $$HX$$是中心化后的矩阵

于是：

$$
S\_{p\times p}=\frac{1}{N}X^THX=\frac{1}{N}X^TH^THX=\frac{1}{N}V\Sigma^T\Sigma V^T
$$

因此，直接对中心化后的数据集进行 `SVD`，就可以得到特征值和特征向量 $$V$$，在新坐标系中的坐标就是：

$$
HX\cdot V = U\Sigma
$$

由上面的推导，可以得到另一种方法 `PCoA` 主坐标分析，定义并进行特征值分解：

$$
T\_{N\times N}=HXX^TH=U\Sigma\Sigma^TU^T
$$

> 可知，$$T$$和$$S$$有相同的`eigen value`（特征值）
>
> S：特征分解，得到方向（主成分），然后HXV->坐标
>
> T：特征分解，直接得到坐标（主坐标分析/PCoA）

由于：

$$
TU\Sigma=U\Sigma(\Sigma^T\Sigma)
$$

于是可以直接得到坐标。这两种方法都可以得到主成分，但是由于方差矩阵是 $$p\times p$$的，而 $$T$$是 $$N\times N$$ 的，所以对样本量较少的时候可以采用 `PCoA`的方法。

```
PCA求解步骤：
1. u1
2. 去中心化(xi-x_mean)u1 -> zi
```

## p-PCA

下面从概率的角度对 PCA 进行分析，概率方法也叫 p-PCA。使用线性模型，类似之前 LDA，选定一个方向，对原数据 $$x\in\mathbb{R}^p$$，降维后的数据为 $$z\in\mathbb{R}^q,q\<p$$。降维通过一个矩阵变换（投影）进行：

$$
\begin{align} 线性高斯模型：\ z&\sim\mathcal{N}(\mathbb{O}*{q1},\mathbb{I}*{qq})\ x&=Wz+\mu+\varepsilon\ \varepsilon&\sim\mathcal{N}(0,\sigma^2\mathbb{I}\_{pp})\ \varepsilon& \perp z \ E&(x|z) = E(Wz+\mu+\varepsilon) = Wz+\mu \ V\&ar\[x]=Var\[Wz+\mu+\varepsilon] = \sigma^2\mathbb{I}\ x&|z \sim N(Wz+\mu,\sigma^2\mathbb{I}) \ \end{align}
$$

p-PCA问题有两个：

* inference：$$p(z|x)$$
* learing(求参数)：$$w，\mu，\sigma^2$$

对于这个模型，可以使用期望-最大（EM）的算法进行学习，在进行推断的时候需要求得 $$p(z|x)$$，推断的求解过程和线性高斯模型类似。

$$
\begin{align} \&p(z|x)=\frac{p(x|z)p(z)}{p(x)}\ &\mathbb{E}\[x]=\mathbb{E}\[Wz+\mu+\varepsilon]=\mathbb{E}\[Wz+\mu]+E\[\varepsilon]=\mu\ \&Var\[x]=Var\[Wz+\mu+\varepsilon]\ & \ \ \ \ \ \ \ \ \ \ \ \ =Var\[Wz]+Var\[\mu]+Var\[\varepsilon]\ & \ \ \ \ \ \ \ \ \ \ \ \ =W\cdot\mathbb{I\_{qq}}\cdot W^T+\sigma^2\mathbb{I}\_{pp}\ & \ \ \ \ \ \ \ \ \ \ \ \ =WW^T+\sigma^2\mathbb{I}\ &有,x\sim N(\mu,WW^T+\sigma^2\mathbb{I}) \end{align}
$$

接下来求$$z$$的后验

$$
\begin{align} &记，x=\begin{pmatrix}x\_{a}\x\_{b}\end{pmatrix}\ &有，x\sim N\[\begin{pmatrix}\mu\_{a}\\\mu\_{b}\end{pmatrix} \begin{pmatrix}\Sigma\_{aa}&\Sigma\_{ab}\\\Sigma\_{ba}&\Sigma\_{bb}\end{pmatrix}] \ &于是, \ & \ \ \ \ \ \ \ \ \ x\_{b\cdot a} =x\_b - \Sigma\_{ba}\Sigma\_{aa}^{-1}x\_a \ & \ \ \ \ \ \ \ \ \ \mu\_{b\cdot a} =\mu\_b - \Sigma\_{ba}\Sigma\_{aa}^{-1}\mu\_a \ & \ \ \ \ \ \ \ \ \ \Sigma\_{bb\cdot a} =\Sigma\_{b\cdot a} - \Sigma\_{ba}\Sigma\_{aa}^{-1}\Sigma\_{a\cdot b} \ & 有, \ \ \ \ x\_{b\cdot a}\sim N(\mu\_{b\cdot a},\Sigma\_{bb\cdot a}) \ &又 \ \ \ \ \ \ x\_{b}=x\_{b\cdot a}+\Sigma\_{bb\cdot a}\Sigma\_{aa}^{-1}x\_a \ & \ \ \ \ \ \ \ \ \ E(x\_b|x\_a)=E(x\_{b\cdot a})+ \Sigma\_{bb\cdot a}\Sigma\_{aa}^{-1}x\_a \ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = \mu\_{b\cdot a}+\Sigma\_{bb\cdot a}\Sigma\_{aa}^{-1}x\_a \ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = \mu\_{b}+\Sigma\_{bb\cdot a}\Sigma\_{aa}^{-1}(x\_a-\mu\_a) \ & \ \ \ \ \ \ \ \ \ Var(x\_b|x\_a)=Var(x\_{b\cdot a}) = \Sigma\_{bb\cdot a}\ & 有, \ \ \ \ x\_b|x\_a\sim N(\mu\_{b}+\Sigma\_{bb\cdot a}\Sigma\_{aa}^{-1}(x\_a-\mu\_a),\Sigma\_{bb\cdot a}) \ \end{align}
$$

由上可知，

$$
\begin{align} &记，\begin{pmatrix}x\z\end{pmatrix} \sim N\[\begin{pmatrix}\mu\0\end{pmatrix} \begin{pmatrix}WW^T+\sigma^2\mathbb{I}&\Delta\\\Delta&\mathbb{I}\end{pmatrix}] \ &求解，\Delta\ &由于\Delta=Cov(x,z)=Cov(z,x)，求解一个即可 \ & Cov(x,z) = E\[(x-\mu)(z-0)^T] = E\[(x-\mu)z^T]\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = E\[(Wz+\varepsilon)z^T] = E\[Wzz^T+\varepsilon z^T] \ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = E\[Wzz^T]+E\[\varepsilon z^T] \ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = WE\[zz^T] = W\cdot \mathbb{I}\ & 求出后，有\begin{pmatrix}x\z\end{pmatrix} \sim N\[\begin{pmatrix}\mu\0\end{pmatrix} \begin{pmatrix}WW^T+\sigma^2\mathbb{I}\&W\cdot \mathbb{I}\W\cdot \mathbb{I}&\mathbb{I}\end{pmatrix}] \ &即可套公式求出p(z|x) \end{align}
$$

$$
即，p(z|x)=\mathcal{N}(W^T(WW^T+\sigma^2\mathbb{I})^{-1}(x-\mu),\mathbb{I}-W^T(WW^T+\sigma^2\mathbb{I})^{-1}W)
$$

## 小结

降维是解决维度灾难和过拟合的重要方法，除了直接的特征选择外，还可以采用算法的途径对特征进行筛选，线性的降维方法以 PCA 为代表，在 PCA 中，只要直接对数据矩阵进行中心化然后求奇异值分解或者对数据的协方差矩阵进行分解就可以得到其主要维度。非线性学习的方法如流形学习将投影面从平面改为超曲面。