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

维度灾难

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

$$\lim_{n\to\infty}\frac{CR^n}{2^nR^n}=0$$

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

主成分分析 (PCA)

目标

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

损失函数

最大化方差：

$$J=\sum_{j=1}^qu_j^TSu_j, \quad s.t. \quad u_j^Tu_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=HXX^TH$ 并特征分解：

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

坐标：$U\Sigma$

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

概率 PCA (p-PCA)

模型假设：

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

学习用 EM 算法，推断：

$$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)$$