4.DimentionReduction

降维解决维度灾难和过拟合问题，分为特征选择、线性降维（PCA）和非线性降维（流形学习）。

维度灾难

$n$ 维球体积与超立方体比值：

${\lim }_{n\to \infty }\frac{C{R}^n}{2^n{R}^n}=0$

高维数据主要分布在边缘，样本稀疏。

主成分分析 (PCA)

目标

1. 数据在子空间中更分散
2. 损失信息最小

损失函数

最大化方差：

$J={\sum }_{j=1}^q{u}_j^{T}S{u}_j,s.t.u_j^T{u}_j=1$

解为协方差矩阵 $S$ 的特征向量，取前 $q$ 个最大特征值对应的方向。

SVD 方法

对中心化数据 $HX$ 进行奇异值分解：

$HX=U\Sigma V^T$

协方差矩阵：$S=\frac{1}{N}V{\Sigma }^T\Sigma V^T$

新坐标：$HX\cdot V$

PCoA

定义 $T=HX{X}^{T}H$ 并特征分解：

$T=U\Sigma {\Sigma }^T{U}^T$

坐标：$U\Sigma$

样本量较少时可采用 PCoA 方法。

概率 PCA (p-PCA)

模型假设：

$z\sim \mathcal{N}(0,\mathbb{I}),x=Wz+\mu +\epsilon ,\epsilon \sim \mathcal{N}(0,{\sigma }^2\mathbb{I})$

学习用 EM 算法，推断：

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