Skip to content

Chapter 13 降维与度量学习

一、高维的诅咒

疾旋鼬想用 \(k\) 近邻分类。它有 20 个特征。但在高维空间中，一个诡异的现象出现了：

所有点之间的距离都差不多。

这就是维数灾难 (curse of dimensionality)。

密采样假设：要让 \(k\) 近邻有效，需要在每个维度上有足够密的样本。如果每个维度需要 10 个样本，20 维就需要 \(10^{20}\) 个——比宇宙中的原子还多。

解决方案：降维 (Dimensionality Reduction)——找到一个低维空间，保留数据中最重要的信息。

为什么能降维？数据样本虽是高维的，但与学习任务密切相关的也许仅是某个低维分布，即高维空间中的一个低维"嵌入" (embedding)。

二、\(k\) 近邻学习器

基本思路

\(k\) 近邻 (\(k\)-Nearest Neighbor, \(k\)NN)：懒惰学习 (lazy learning) 的代表。"近朱者赤，近墨者黑。"

预测时，找 \(k\) 个最近邻： - 分类：投票法（\(k\) 个近邻中出现最多的类别） - 回归：平均法（\(k\) 个近邻的标签平均值）

关键：\(k\) 值选取和距离计算。

与贝叶斯最优分类器的关系

定理：最近邻分类器的泛化错误率不超过贝叶斯最优分类器错误率的两倍。

但在高维空间中，密采样条件不再满足，"最近邻"可能很远，\(k\)NN 失效。

概率化表示

样本 \(x_j\) 作为 \(x_i\) 近邻的概率 \(p_{ij}\)：

\[p_{ij} = \frac{\exp(-\text{dist}^2(x_i, x_j))}{\sum_{l \neq i}\exp(-\text{dist}^2(x_i, x_l))}\]

\(x_i\) 被分类为类别 \(y_i\) 的概率：\(P(\hat{y}_i = y_i) = \sum_{j: y_j = y_i} p_{ij}\)

三、主成分分析 (PCA)

核心思想

PCA 寻找一个低维超平面，使得： - 最大可分性：样本投影后尽可能分散（方差最大） - 最近重构性：样本到超平面的距离足够近（重构误差最小）

这两个目标是等价的。

推导一：最大可分性

对样本进行中心化：\(\sum_{i=1}^m x^{(i)} = 0\)。

寻找投影方向 \(w\)（\(\|w\| = 1\)），使投影后方差最大：

\[\max_w \frac{1}{m}\sum_{i=1}^m (w^T x^{(i)})^2 = w^T \left(\frac{1}{m}\sum_{i=1}^m x^{(i)} x^{(i)T}\right) w = w^T \Sigma w\]

其中 \(\Sigma = \frac{1}{m}\sum_i x^{(i)} x^{(i)T}\) 是样本协方差矩阵。

约束 \(\|w\| = 1\)，用拉格朗日乘子法：

\[\mathcal{L}(w, \lambda) = w^T \Sigma w - \lambda(w^T w - 1)\]
\[\frac{\partial \mathcal{L}}{\partial w} = 2\Sigma w - 2\lambda w = 0 \implies \Sigma w = \lambda w\]

这是协方差矩阵的特征值分解。\(w\) 是特征向量，\(\lambda\) 是特征值。

投影后的方差为 \(w^T \Sigma w = \lambda\)。取最大的 \(d'\) 个特征值对应的特征向量 \(W = [w_1, w_2, \ldots, w_{d'}]\)，投影后：

\[z = W^T x \in \mathbb{R}^{d'}\]

推导二：最近重构性

样本 \(x^{(i)}\) 在新坐标系中的投影为 \(z^{(i)} = W^T x^{(i)}\)。基于投影重构：

\[\hat{x}^{(i)} = Wz^{(i)} = WW^T x^{(i)}\]

最小化重构误差：

\[\min_W \sum_{i=1}^m \|x^{(i)} - WW^T x^{(i)}\|^2 \quad \text{s.t.} \quad W^T W = I\]

由于 \(W\) 是正交基，\(\|x^{(i)} - WW^T x^{(i)}\|^2 = \|x^{(i)}\|^2 - \|W^T x^{(i)}\|^2\)。

最小化重构误差等价于最大化 \(\sum_i \|W^T x^{(i)}\|^2 = \text{tr}(W^T \Sigma W)\)，即最大化投影方差。\(\square\)

\(d'\) 的选择

  • 用户指定
  • 重构阈值法：选最小 \(d'\) 使得 \(\frac{\sum_{i=1}^{d'} \lambda_i}{\sum_{i=1}^d \lambda_i} \geq t\)（如 \(t=0.95\)，保留 95% 的方差）
  • 交叉验证法：在低维空间中对分类器做交叉验证

几何解释

\(R^2\) 的几何解释：\(R^2 = \cos^2\theta\)，其中 \(\theta\) 是真实值中心化向量与预测值中心化向量的夹角。

PCA 的应用

  • 特征脸 (eigenface)：将前 \(d'\) 个特征向量还原为图像，每张图像捕捉人脸数据中的一种主要变化模式
  • 数据可视化：降到 2D 或 3D
  • 降噪：丢弃小特征值对应的维度（噪声）

PCA 的局限

  • 假设数据低维线性分布
  • 对异常值敏感
  • 无监督方法，不利用标签信息

四、核化 PCA (KPCA)

PCA 假设数据在低维空间中是线性分布的。如果数据分布在非线性流形上，PCA 失效。

核化 PCA：先用核函数将数据映射到高维特征空间，再在特征空间中做 PCA。

\[\phi: x \mapsto \phi(x), \quad \kappa(x, z) = \phi(x)^T \phi(z)\]

在特征空间中，协方差矩阵为 \(\Sigma_\phi = \frac{1}{m}\sum_i \phi(x^{(i)})\phi(x^{(i)})^T\)。

利用核技巧，只需计算核矩阵 \(K_{ij} = \kappa(x^{(i)}, x^{(j)})\)，避免显式计算 \(\phi(x)\)。

五、流形学习

ISOMAP

假设数据分布在低维流形上。

  1. 构造近邻图：每个样本只与 \(k\) 个最近邻相连
  2. 用最短路径算法（Dijkstra）近似任意两点之间的测地线距离
  3. 基于测地线距离矩阵，用 MDS (Multidimensional Scaling) 获得低维嵌入

MDS：保持样本间的相对距离不变。

  1. 构建距离矩阵 \(D\)
  2. 双中心化：\(B = -\frac{1}{2}HD^2H\)，其中 \(H = I - \frac{1}{m}\mathbf{1}\mathbf{1}^T\)
  3. 对 \(B\) 做特征值分解，取前 \(d'\) 个正特征值及其特征向量
  4. 低维坐标：\(Z = U_{d'}\Lambda_{d'}^{1/2}\)

LLE (Locally Linear Embedding)

假设每个样本可由其近邻线性重构。

  1. 为每个样本 \(x^{(i)}\) 找近邻集 \(N_i\)
  2. 计算重构系数 \(w_{ij}\)：\(x^{(i)} \approx \sum_{j \in N_i} w_{ij} x^{(j)}\)
  3. 低维空间中保持 \(w_{ij}\) 不变：
\[\min_{z_1, \ldots, z_m} \sum_{i=1}^m \left\|z^{(i)} - \sum_{j \in N_i} w_{ij} z^{(j)}\right\|^2\]

LLE 的关键：重构权值编码了数据的局部几何结构。

六、距离度量学习

核心思想

降维的本质是找到一个"合适的"低维空间。每个空间对应了一个距离度量。

能否直接学出合适的距离？

马氏距离 (Mahalanobis Distance)

\[\text{dist}_M^2(x^{(i)}, x^{(j)}) = (x^{(i)} - x^{(j)})^T M (x^{(i)} - x^{(j)})\]

其中 \(M\) 是半正定对称矩阵（度量矩阵）。\(M = I\) 时退化为欧氏距离。

NCA (Neighborhood Component Analysis)

以 \(k\)NN 分类器性能为目标，学习马氏距离 [Goldberger et al., NIPS 2004]。

样本 \(x_j\) 作为 \(x_i\) 近邻的概率：

\[p_{ij} = \frac{\exp(-\|L^T x_i - L^T x_j\|^2)}{\sum_{l \neq i}\exp(-\|L^T x_i - L^T x_l\|^2)}\]

其中 \(M = L^T L\)。最大化留一法正确率：\(\max_L \sum_i \sum_{j: y_j = y_i} p_{ij}\)。

LMNN (Large Margin Nearest Neighbors)

结合邻域信息和间隔 (margin) [Weinberger et al., NIPS 2005]：

\[\min_M \sum_{i, j \rightsquighey i} \|x_i - x_j\|_M^2 + C\sum_{i,j \rightsquighey i, l} \xi_{ijl}\]
\[\text{s.t.} \quad \|x_i - x_j\|_M^2 - \|x_i - x_l\|_M^2 \geq 1 - \xi_{ijl}, \quad \xi_{ijl} \geq 0, \quad M \succeq 0\]

其中 \(j \rightsquighey i\) 表示 \(j\) 是 \(i\) 的目标近邻，\(l\) 是不同类别的"入侵者"。

PCA 是最常用的降维方法，在不同领域有不同的称谓：信号处理中叫 Karhunen-Loève 变换，统计学中叫主轴分析。

降维与度量学习的关系：每个空间对应一个距离度量，学习距离度量就是学习一个合适的特征空间。

2026.06