第 11 章 降维与表示学习

高维数据里，“距离"会失效、“可视化"会失真、“参数"会爆炸。本章给出三条出路：把方差最大的方向留下（PCA）、把类间可分的方向留下（LDA）、或者假设数据躺在一张低维曲面上（流形学习）。

学习目标

读完本章，你应当能够：

1. 从最大化投影方差与最小化重构误差两个视角推导 PCA，并证明二者等价；
2. 计算协方差矩阵的特征分解、累计贡献率与白化变换，说明 n < d 时该怎么处理；
3. 写出 LDA 的 S_W、S_B 与广义瑞利商，证明降维维数上限为 C−1，并辨析它与 PCA 的适用场景、小样本下 S_W 奇异的原因；
4. 说明 SVD 在推荐系统中的应用、NMF 与隐语义模型的核心思想；
5. 说明 MDS、Isomap、LLE、t-SNE、UMAP 的核心机制与局限，特别是"t-SNE 保局部不保全局”；
6. 区分降维与特征选择，并辨析过滤式、包裹式、嵌入式三类特征选择方法。

前置知识检查

11.1 PCA：两个等价视角

11.1.1 问题设定与第一步必须做的事

主成分分析（Principal Component Analysis, PCA）要找一组正交方向，把 d 维数据投影到 k 维（k < d）而"损失最小”。动手前必须先中心化：把每个特征减去它的均值，记中心化后的数据矩阵为 X ∈ R^(n×d)，此时 Σ_i x_i = 0。

为什么必须中心化？ 协方差矩阵的定义是 Cov(X) = (1/(n−1))·Σ_i (x_i − μ)(x_i − μ)ᵀ，它衡量的本来就是"围绕均值的波动”。如果不中心化，第一主成分会被"数据离原点多远"主导，而不是"数据往哪个方向散得最开"——在原始尺度上直接做 PCA 会得到一个主要指向均值方向的分量，毫无意义。

11.1.2 视角一：最大化投影方差

设单位向量 u（‖u‖ = 1）是一个待求的投影方向。样本 x_i 投影后变成标量 uᵀx_i，投影后全体样本的方差是

1
2
3

Var(投影) = (1/(n−1))·Σ_i (uᵀx_i − uᵀμ)² = (1/(n−1))·Σ_i (uᵀ(x_i − μ))²
          = uᵀ·[ (1/(n−1))·Σ_i (x_i − μ)(x_i − μ)ᵀ ]·u
          = uᵀC u                （C 为协方差矩阵）

于是"找方差最大的方向"变成一个带约束的优化问题：

1

max_u  uᵀC u       s.t.  uᵀu = 1

为什么约束是 ‖u‖ = 1？ 没有它的话，目标函数随 ‖u‖ → ∞ 无界增大，问题没有意义。单位约束只固定方向、不固定长度，恰好是我们想要的。

用拉格朗日乘子法：L(u, λ) = uᵀCu − λ(uᵀu − 1)，令 ∂L/∂u = 2Cu − 2λu = 0，得

1

C u = λ u

这正是特征值方程。 把两边左乘 uᵀ 得 uᵀCu = λ·uᵀu = λ，所以：

1

投影方差 = λ                    （特征值就是投影后的方差）

因此要让方差最大，就取 C 最大特征值对应的特征向量作为第一主成分；再取第二大特征值对应的特征向量作为第二主成分（特征向量两两正交，所以各主成分互不相关），依此类推。要降到 k 维，就取前 k 个最大特征值对应的特征向量，按列拼成投影矩阵 W ∈ R^(d×k)：

1

Z = X W          （Z ∈ R^(n×k) 就是降维后的数据）

11.1.3 视角二：最小化重构误差

换一个完全不同的出发点：我们要找一组正交基 {u_1, …, u_k}，使数据投影到它们张成的子空间后再还原回去，误差最小。记投影坐标为 z_i = Wᵀx_i（W 的列是 u_1..u_k），重构为 x̂_i = Wz_i = WWᵀx_i，目标是

1

min_W  Σ_i ‖x_i − WWᵀx_i‖²       s.t.  WᵀW = I_k

两个视角等价的证明。 对单个样本用勾股定理（因为 x̂ = WWᵀx 是正交投影，残差 x − x̂ 与 x̂ 垂直）：

1

‖x_i − x̂_i‖² = ‖x_i‖² − ‖x̂_i‖² = ‖x_i‖² − ‖Wᵀx_i‖² = ‖x_i‖² − Σ_{j=1}^{k} (u_jᵀx_i)²

对全部样本求和，Σ_i ‖x_i‖² 与 W 无关，是常数。因此

1
2

min_W Σ_i ‖x_i − x̂_i‖²  ⟺  max_W Σ_i Σ_{j=1}^{k} (u_jᵀx_i)²
                        ⟺  max_W Σ_{j=1}^{k} u_jᵀ C u_j      （每个 u_jᵀCu_j 就是该方向上的投影方差）

结论：最大投影方差与最小重构误差是同一件事的两面。 而且这个等价性还有一个漂亮的解释——重构误差恰好等于被丢掉的那些方向上的方差之和：

1

Σ_i ‖x_i − x̂_i‖² = Σ_i ‖x_i‖² − Σ_{j=1}^{k} λ_j = Σ_{j=k+1}^{d} λ_j

即"丢掉的方向上原本有多少方差，就产生多少重构误差"。这就是 PCA 的信息损失可以精确计量的原因。

11.1.4 累计贡献率、白化与 n < d 的处理

累计贡献率（cumulative explained variance ratio）：前 k 个主成分保留的信息占比是

1

累计贡献率(k) = (Σ_{i=1}^{k} λ_i) / (Σ_{i=1}^{d} λ_i)

实践中取它达到 85% 或 95% 所需的最小 k。真题 【09-02 选择 Q10】 问的正是"用什么判断保留几个主成分"，答案是特征值的累计贡献率。

白化（whitening）：把主成分坐标再除以 √λ_j，使降维后各维方差都等于 1、且互不相关：

1

z_white = diag(1/√λ_1, …, 1/√λ_k)·Wᵀ(x − μ)

为什么要白化？ K-Means、SVM、神经网络这些对特征尺度敏感的模型，若输入各维方差差异极大（λ_1 = 1000, λ_2 = 0.001），大尺度维度会主导距离与梯度。白化把所有维度拉到同一尺度。代价是它同时把噪声维度也放大到同样尺度，所以在信噪比低时白化反而有害。

n < d 时怎么办？ 当样本数少于特征数时，中心化后数据的秩最多是 min(n−1, d)，协方差矩阵 C 是 d×d 但秩只有 n−1，它是奇异的：

1
2

r(X) ≤ n − 1  ⟹  r(C) ≤ n − 1  ⟹  C 有至少 d − (n−1) 个零特征值
⟹ 最多只有 n − 1 个非零主成分，其余方向上的方差恒为 0（数据在该方向上是"平的"）

实践上的两条处理路径：

用 SVD 是工程上的首选：显式构造协方差矩阵需要 O(nd²) 时间与 O(d²) 空间，再对它做特征分解还要 O(d³)；而只取前 k 个奇异值的截断 SVD 可以做到接近 O(ndk)，且数值上更稳定（不用显式做 XᵀX，避免条件数被平方）。

11.2 LDA：有监督的降维

11.2.1 类内散度与类间散度

线性判别分析（Linear Discriminant Analysis, LDA）的目标与 PCA 完全不同：投影后同类要聚拢、异类要分开。设共有 C 个类，第 c 类的样本集为 D_c、均值为 μ_c、样本数为 n_c，全体均值为 μ。定义两个散度矩阵：

1
2
3

类内散度 S_W = Σ_{c=1}^{C} Σ_{x∈D_c} (x − μ_c)(x − μ_c)ᵀ      （同类内部的波动）
类间散度 S_B = Σ_{c=1}^{C} n_c·(μ_c − μ)(μ_c − μ)ᵀ            （各类均值围绕总均值的波动，按类大小加权）
总散度   S_T = S_W + S_B

投影到方向 w 后，一维"方差"分别是 wᵀS_W w 与 wᵀS_B w。LDA 要最大化它们的比值，即广义瑞利商（generalized Rayleigh quotient）：

1

J(w) = (wᵀS_B w) / (wᵀS_W w)

为什么"比值"而不是"差"？ 差值 wᵀS_B w − wᵀS_W w 会随 ‖w‖ 无界增大，必须在长度上额外加约束；比值对尺度不敏感（w 换成 2w 结果不变），天然免除了尺度约束，只需固定 ‖w‖。

11.2.2 求解与维数上限 C−1 的证明

求导：最大化 J 等价于在约束 wᵀS_W w = 1 下最大化 wᵀS_B w（因为比值不随尺度变化，可以任意固定分母）。构造拉格朗日函数 L = wᵀS_B w − λ(wᵀS_W w − 1)，令 ∂L/∂w = 0：

1

2S_B w − 2λS_W w = 0   ⟹   S_B w = λ S_W w        （广义特征值问题）

若 S_W 可逆，两边左乘 S_W⁻¹ 得 S_W⁻¹S_B w = λw，即普通特征值问题。取 S_W⁻¹S_B 最大的 k 个特征值对应的特征向量作为投影矩阵。

J(w) 的最大值就是最大特征值 λ：两边左乘 wᵀ 得 wᵀS_B w = λ·wᵀS_W w，代入定义即 J(w) = λ。

维数上限为 C−1 的证明。 这是 LDA 最常考的结论，必须会证：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

① 把 S_B 展开（利用 Σ_c n_c(μ_c − μ) = Σ_c Σ_{x∈D_c}(x − μ) = 0）：
   S_B = Σ_c n_c(μ_c − μ)(μ_c − μ)ᵀ
   ⟹ S_B 是 C 个秩 1 矩阵之和 ⟹ r(S_B) ≤ C

② 但 μ = (1/n)·Σ_c n_c μ_c，即这 C 个向量的加权和等于全局均值 μ，二者线性相关：
   Σ_c n_c(μ_c − μ) = 0
   ⟹ 这 C 个中心化向量 (μ_1 − μ), …, (μ_C − μ) 中只有 C−1 个线性无关
   ⟹ r(S_B) ≤ C − 1

③ 秩就是非零特征值的个数，故 S_W⁻¹S_B 最多有 C−1 个非零特征值
   ⟹ LDA 最多只能提取 C−1 个有效判别方向

二分类（C = 2）时只能降到 1 维，这也是真题 【09-04 选择 Q8】 中"D 选项错在’必定优于’“的关键证据之一：把 100 维的两类数据压到 1 维，信息损失可能极大。

11.2.3 与 PCA 的对比、小样本问题

小样本问题（S_W 奇异）：当每个类的样本数都小于特征维数（n_c < d，典型如人脸识别），S_W 是 d×d 但秩至多 n − C，必然奇异、不可逆，S_W⁻¹S_B 直接失效（数值上表现为特征值爆炸）。三条标准对策：

11.3 矩阵分解与隐语义

11.3.1 SVD 在推荐中的应用

推荐系统的输入是一个用户–物品评分矩阵 R ∈ R^(m×n)（m 个用户、n 个物品）。这个矩阵通常极其稀疏（一个用户只评过几百个物品中的几个），我们想预测那些空缺位置。SVD 给出

1

R ≈ U Σ Vᵀ,     U ∈ R^(m×k), Σ = diag(σ_1 ≥ … ≥ σ_k > 0), V ∈ R^(n×k)

隐语义的解释：把 UΣ 的行看成用户的 k 维"兴趣画像”、V 的行看成物品的 k 维"属性画像"，则第 (i, j) 个评分约等于两者的内积：

1

R̂_ij = (第 i 个用户向量)·(第 j 个物品向量)      ← 两者在第 t 个隐维度上"合拍"就贡献高分

这些隐维度不是人工定义的（不是"动作片/文艺片"），而是从评分模式里学出来的，所以叫隐语义（latent semantics）。工程上常用带正则的矩阵分解（把最小化 Σ_{(i,j)∈观测} (R_ij − u_iᵀv_j)² + λ(‖u_i‖² + ‖v_j‖²) 做随机梯度下降），它只对已观测的评分拟合，这正是第 8 章"正则化 + 只对观测建模"的组合。

11.3.2 NMF 与隐语义模型

非负矩阵分解（Non-negative Matrix Factorization, NMF）要求 R ≈ WH 中的 W、H 都非负。这个约束带来一个 SVD 没有的好处：可解释的"部分构成"。

1
2

SVD：  R ≈ UΣVᵀ   —— 基向量可正可负 ⟹ "一个主成分减去另一个主成分"难以解释
NMF：  R ≈ W H    —— 都是非负 ⟹ 每个样本都是若干"部件"的非负叠加

直观例子：人脸数据做 NMF，W 的列会学到眼睛、鼻子、嘴这类局部部件，因为"非负叠加"不允许用减法去抵消——要表示一张完整人脸只能把部件加起来，于是分解自然趋向局部化、部件化的表示。若把 H 的每列归一化，还能得到"软聚类"式的隶属度（一篇文章由 60% 体育 + 40% 财经构成）。

11.4 流形学习速览

核心假设：高维数据往往集中在低维流形（manifold）附近——就像一张揉皱的纸（2 维流形）嵌在 3 维空间里。流形学习的任务是"把纸展开"，恢复出内在的低维坐标，而不要求变换是线性的（这是它与 PCA 的根本区别）。

为什么 t-SNE 保局部不保全局？ 看它的目标函数（高维相似度 p_ij、低维相似度 q_ij，最小化 KL(P‖Q) = Σ p_ij·ln(p_ij/q_ij)）：

1
2
3
4
5
6

① 高维用高斯核：p_ij ∝ exp(−‖x_i − x_j‖²/(2σ²))  —— 远点的 p_ij 衰减极快、接近 0
② 低维用 t 分布：q_ij ∝ (1 + ‖y_i − y_j‖²)⁻¹      —— 重尾，远点的 q_ij 衰减慢
③ KL(P‖Q) 中 p_ij 是权重：p_ij ≈ 0 的点对（原空间里的远点）
   对损失几乎没有贡献 ⟹ 优化只关心"原本就邻近的点对"
④ 重尾的 t 分布还产生"斥力"，把不同簇推开，使视觉上簇间空隙明显放大
⟹ 结论：t-SNE 图上的簇间距离与簇大小不可解读，只能在**同一个图内**比较"谁和谁更近"

因此使用 t-SNE 有三条纪律：不要跨图比较（不同随机种子/不同 perplexity 的图不可比）、不要解读簇间距离、不要用簇的疏密推断原始密度。需要同时看全局结构时，用 UMAP 或先做 PCA 看整体。

11.4.1 核 PCA 与非线性降维

PCA 只能做线性映射。核 PCA（kernel PCA）用核技巧把它非线性化：把样本映到高维特征空间 φ(x)，在那边做 PCA。由于 PCA 只需要内积，把内积换成核函数即可：

1
2
3
4

K_ij = φ(x_i)ᵀφ(x_j) = k(x_i, x_j)          （常用 RBF 核 k(x,y) = exp(−γ‖x−y‖²)）
① 在特征空间中心化：K ← HKH，H = I − (1/n)·11ᵀ
② 对 K 做特征分解：K = UΛUᵀ，第 j 个主成分方向的投影为 Λ_j^(-1/2)·(第 j 列 of U)
⟹ 完全不需要显式算出 φ(x)，只需 n×n 的核矩阵

代价是核矩阵是 n×n：n 大时空间与时间都不可接受（这与 11.1.4 节"用 SVD 避开通病"的思路刚好相反），且需要调核参数 γ。此外核 PCA 没有显式的投影矩阵，新样本要投影必须计算它与全部训练样本的核值（因此必须保存训练集）。

11.5 降维与特征选择

特征选择三类方法的判别标准只有一条：“有没有用到模型？用在哪一步？”

本章小结

自测题

Q1（证明）证明 PCA 的"最大化投影方差"与"最小化重构误差"是等价的，并说明重构误差与被丢弃特征值之间的关系。

Q2（计算/辨析）某数据集有 500 个样本、800 个特征。对它做 PCA 时最多能得到多少个非零主成分？为什么？实践中应该用特征分解还是 SVD？

Q3（证明）证明 LDA 的降维维数上限为 C − 1（C 为类别数），并说明二分类时意味着什么。

Q4（辨析）写出 PCA 与 LDA 的对比要点，并判断下列说法： A. PCA 最大化投影后总方差，LDA 使同类聚集、异类分离； B. PCA 是有监督方法，LDA 是无监督方法； C. 在任何带类别标签的数据集上，LDA 降维效果必定优于 PCA； D. LDA 降维维数上限为 C − 1。

Q5（辨析）解释 t-SNE 为什么"保局部不保全局"，并列出使用它时两条以上必须遵守的纪律。

与真题的关联

延伸阅读

• Hastie, Tibshirani, Friedman. The Elements of Statistical Learning, 第 3.5、4.3 节（PCA 与 LDA 的完整推导）、第 14.9 节（流形学习与 Isomap、LLE）。
• Bishop. Pattern Recognition and Machine Learning, 第 12 章（PCA、核 PCA、流形学习）。
• Jolliffe. Principal Component Analysis（PCA 的权威专著，含全部变体）。
• van der Maaten, Hinton. Visualizing Data using t-SNE, JMLR 2008。
• McInnes, Healy, Melville. UMAP: Uniform Manifold Approximation and Projection, 2018。
• Lee, Seung. Learning the parts of objects by non-negative matrix factorization, Nature 1999。