# 第 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. 区分降维与特征选择，并辨析过滤式、包裹式、嵌入式三类特征选择方法。

### 前置知识检查

| 你需要知道 | 在哪一节补齐 |
|---|---|
| 特征值/特征向量、对称矩阵的谱定理、正定性 | 第 3 章 3.1、3.2 节 |
| SVD、奇异值、低秩近似与压缩率 | 第 3 章 3.3 节 |
| 协方差矩阵的定义与性质 | 第 4 章 |
| 拉格朗日乘子与约束优化 | 第 6 章 |
| 广义特征值问题 `Aw = λBw` | 第 3 章（对称矩阵对角化） |
| 核技巧（内积的高维替换） | 第 14 章 14.1 节 |

---

## 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`，投影后全体样本的方差是

```
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 为协方差矩阵）
```

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

```
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`，得

```
C u = λ u
```

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

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

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

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

> [!IMPORTANT]
> 这条推导给出了真题 `【09-02 选择 Q10】` 的全部依据：**协方差矩阵的第 `i` 个特征值 `λ_i` 就等于数据在第 `i` 主成分方向上的方差**。所以"前 `k` 维保留了多少信息"可以直接用特征值算，见 11.1.4 节。反过来，特征向量的**模长**恒为 1（单位化过），不携带任何信息量，不能作为选择依据。

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

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

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

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

```
‖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` 无关，是常数。因此

```
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 就是该方向上的投影方差）
```

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

```
Σ_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` 个主成分保留的信息占比是

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

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

| 干扰项 | 为什么错 |
|---|---|
| 数据的均值 | PCA 之前已被中心化减掉，与保留几维无关 |
| 特征向量的模长 | 特征向量都已单位化，模长恒为 1，不含信息 |
| 投影后方差的**倒数** | 方向搞反了：方差越大越该保留，取倒数会把最该丢的排到最前 |

**白化（whitening）**：把主成分坐标再除以 `√λ_j`，使降维后各维方差都等于 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`，**它是奇异的**：

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

实践上的两条处理路径：

| 路径 | 做法 | 适用 |
|---|---|---|
| 只取非零主成分 | 只保留 `k ≤ n−1` 个最大特征值对应的方向 | 目的就是降维/去噪 |
| 用 SVD 而非特征分解 | 直接对中心化矩阵 `X` 做 SVD：`X = UΣVᵀ`，则 `λ_j = σ_j²/(n−1)`、主成分方向就是 `V` 的列 | 高维（`d` 很大）时避免显式构造 `d×d` 的 `C` |

**用 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`，全体均值为 `μ`。定义两个散度矩阵：

```
类内散度 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）：

```
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`：

```
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 最常考的结论，必须会证：

```
① 把 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 的对比、小样本问题

| 维度 | PCA | LDA |
|---|---|---|
| 监督性 | **无监督**（不用标签） | **有监督**（必须用标签） |
| 优化目标 | 投影后**总方差最大**（等价于重构误差最小） | 广义瑞利商最大：**类间散度大、类内散度小** |
| 解的本质 | `C = (1/(n−1))XᵀX` 的特征分解 | `S_W⁻¹S_B` 的（广义）特征分解 |
| 降维维数上限 | 无硬上限（`≤ min(n−1, d)`） | **C − 1**（`C` 为类别数） |
| 是否用类结构 | 不用，可能把两类混在一起 | 用，专门为分类服务 |
| 典型用途 | 压缩、去噪、可视化、去相关 | 有标签数据的判别降维、特征提取 |
| 何时更好 | 无标签；或类结构与最大方差方向一致 | 有标签且目标是分类；类间方向与最大方差方向不一致 |

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

| 对策 | 做法 | 代价 |
|---|---|---|
| 正则化 LDA | 用 `S_W + λI` 代替 `S_W`（与岭回归同一思想） | 引入超参 `λ`，需交叉验证 |
| 先 PCA 再 LDA | 先用 PCA 把维度降到 `n − C` 以下，再跑 LDA | 两步都无监督/有监督混用，可能先丢掉了判别信息 |
| 用伪逆 | 以 `S_W⁺` 代替 `S_W⁻¹` | 数值上可行，但无唯一解、解释性差 |

---

## 11.3 矩阵分解与隐语义

### 11.3.1 SVD 在推荐中的应用

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

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

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

```
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 没有的好处：**可解释的"部分构成"**。

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

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

| 方法 | 约束 | 输出性质 | 典型用途 |
|---|---|---|---|
| SVD | 正交基，无符号约束 | 最优低秩近似（Eckart-Young 定理） | 压缩、去噪、隐语义推荐 |
| NMF | `W ≥ 0, H ≥ 0` | 局部化、部件化、可解释 | 主题模型、人脸部件、光谱解混 |
| 隐语义模型 | 只对观测项拟合 + L2 正则 | 隐因子内积预测缺失值 | 协同过滤、CTR 预估 |

> [!NOTE]
> **降维 ≠ 表示学习。** PCA/LDA 是**线性、无参数**的变换（解有闭式形式）；而矩阵分解（尤其带正则的隐语义模型）是**通过优化学出来的参数化表示**，属于表示学习。二者的共同点是把数据映射到低维；区别在于前者有闭式解与几何解释，后者依赖优化与正则。

---

## 11.4 流形学习速览

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

| 方法 | 核心机制 | 保留什么 | 主要局限 |
|---|---|---|---|
| MDS（多维缩放） | 让低维坐标下的点对距离尽量逼近原始距离矩阵 | 全局距离结构 | 仍是线性嵌入；`O(n³)` 特征分解；对距离度量敏感 |
| Isomap | 先用 k-近邻图上的**测地距离**替换欧氏距离，再跑 MDS | 全局测地结构 | 近邻图必须连通（否则测地距离为无穷）；对短路边敏感 |
| LLE（局部线性嵌入） | 用近邻的线性组合重构每个点，求出保持这些**重构权重**的低维坐标 | 局部线性关系 | 对近邻数 `k` 敏感；不保留全局尺度；可能因权重矩阵奇异失败 |
| t-SNE | 在高维用高斯、低维用 t 分布衡量"邻域概率"，最小化两者 KL 散度 | **局部邻域结构** | 不保全局；随机性（需多次运行）；`O(n²)`（无近似时）；簇间距离无意义 |
| UMAP | 构造模糊近邻图，用低维图布局优化最小化交叉熵 | 局部结构 + **部分**全局结构 | 参数（`n_neighbors`、`min_dist`）影响大；理论保证弱于 t-SNE 的清晰度 |

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

```
① 高维用高斯核：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 只需要**内积**，把内积换成核函数即可：

```
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 降维与特征选择

| 对比项 | 降维（dimensionality reduction） | 特征选择（feature selection） |
|---|---|---|
| 输出 | **新的**、通常不可直接解释的特征（原特征的线性/非线性组合） | 原特征的一个**子集**，语义不变 |
| 可解释性 | 差（主成分是混合量） | 好（保留的仍是"年龄""收入"） |
| 是否丢原始信息 | 会丢（被丢方向的方差/信息损失） | 不丢原始语义，只丢整个特征 |
| 典型方法 | PCA、LDA、核 PCA、自编码器 | 卡方/互信息、RFE、L1/L2 正则 |
| 适用 | 特征间高度相关、需要压缩或去噪 | 特征数量大但只有少数真正有用、需要解释 |

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

| 类别 | 是否训练模型 | 做法 | 优点 | 缺点 | 代表 |
|---|---|---|---|---|---|
| 过滤式 filter | 不训练 | 用统计量给每个特征单独打分排序，取前 `k` 个 | 极快、与模型无关、不易过拟合 | 忽略特征间的组合效应（单个没用、合起来很有用） | 方差阈值、卡方检验、互信息、相关系数 |
| 包裹式 wrapper | 训练多次 | 把特征子集当作搜索空间，用模型表现作为评分反复搜索 | 效果好（直接优化目标任务） | 极慢（组合爆炸）、容易过拟合验证集 | 递归特征消除 RFE、前向/后向搜索 |
| 嵌入式 embedded | 训练一次 | 在训练过程中自动完成选择 | 效率与效果的折中 | 依赖具体模型 | L1 正则（Lasso）使系数稀疏、树模型的 `feature_importances_` |

> [!TIP]
> 记忆锚点：**过滤式"先筛后训"，包裹式"边训边选（反复训）"，嵌入式"训的时候顺手选"**。只有包裹式需要反复训练模型，因此它是三者中最贵、也是唯一直接以模型性能为目标的。

---

## 本章小结

| 关键结论 | 一句话表述 | 常见错误 |
|---|---|---|
| PCA 两视角 | 最大投影方差 ⟺ 最小重构误差，"丢掉的方差 = 重构误差" | 以为两者是两种不同算法 |
| 特征值的含义 | `λ_i` **就是**数据在第 `i` 主成分上的投影方差 | 把特征值当成"某种权重" |
| 累计贡献率 | `Σ_{i≤k}λ_i / Σ_{i≤d}λ_i`，取到 85%/95% 的最小 `k` | 用特征向量模长或均值做判据 |
| 必须中心化 | 协方差衡量的是围绕均值的波动 | 忘记中心化导致第一主成分指向均值方向 |
| 白化 | 各维再除以 `√λ_j`，方差归一、去相关 | 忽略它会把噪声维也放大 |
| `n < d` | `C` 必奇异，最多 `n−1` 个非零主成分 | 以为能取到 `d` 个主成分 |
| 计算路径 | 用截断 SVD 代替 `XᵀX` + 特征分解，避免条件数平方 | 高维时显式构造 `d×d` 协方差矩阵 |
| LDA 目标 | 最大化 `(wᵀS_B w)/(wᵀS_W w)` ⟹ `S_W⁻¹S_B w = λw` | 把目标与 PCA 对调 |
| LDA 维数上限 | `r(S_B) ≤ C − 1`（因 `Σ_c n_c(μ_c − μ) = 0`） | 以为能降到任意维 |
| 小样本问题 | `n_c < d` 时 `S_W` 奇异，需正则化或先 PCA | 直接求 `S_W⁻¹` |
| SVD 推荐 | `R̂_ij = 用户隐向量·物品隐向量` | 以为隐维度有人工语义 |
| NMF | 非负约束 ⟹ 部件化、可解释表示 | 与 SVD 混为一谈 |
| t-SNE | 保局部、**不保全局**；簇间距离不可解读 | 用 t-SNE 图比较不同簇的远近 |
| 核 PCA | 只换内积为核函数，代价是 `n×n` 核矩阵 | 以为能得到显式投影矩阵 |
| 特征选择三类 | 过滤式不训练、包裹式反复训练、嵌入式训练时顺手选 | 把 RFE 当成过滤式 |

## 自测题

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

<details><summary>答案与解析</summary>

对单样本，`x̂ = WWᵀx` 是正交投影，故残差与 `x̂` 垂直，由勾股定理：

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

对全部样本求和，`Σ_i ‖x_i‖²` 与 `W` 无关，于是

`min_W Σ_i‖x_i − x̂_i‖² ⟺ max_W Σ_i Σ_j (u_jᵀx_i)² ⟺ max_W Σ_j u_jᵀCu_j`

而 `u_jᵀCu_j` 恰是第 `j` 个方向上的投影方差。故两个目标等价。

**重构误差与被丢弃特征值的关系**：在最优解处 `Σ_i‖x_i‖² = Σ_{j=1}^{d} λ_j`（总方差），而 `Σ_{j=1}^{k} u_jᵀCu_j = Σ_{j=1}^{k} λ_j`，所以

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

即**重构误差 = 被丢弃方向上的方差之和**，这就是累计贡献率能精确度量信息保留比例的原因。

</details>

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

<details><summary>答案与解析</summary>

最多 **499 个**（即 `n − 1`）。

中心化后 `X` 的每一列之和为 0，所以 `X` 的行向量之和为 0，存在一个线性约束，故 `r(X) ≤ n − 1 = 499`。协方差矩阵 `C` 满足 `r(C) = r(X) ≤ 499 < 800`，因此 `C` 奇异，至少有 `800 − 499 = 301` 个零特征值，对应"数据在该方向上是平的"。

实践中应选 **截断 SVD**：直接对中心化矩阵 `X` 做 `X = UΣVᵀ`，则 `λ_j = σ_j²/(n−1)`、主成分方向是 `V` 的列。理由是显式构造 `C = XᵀX/(n−1)` 需要 `O(nd²)` 时间与 `O(d²)` 空间（此处 `d = 800`，`d² = 640000` 尚可，但 `d = 10⁵` 时不可行），且 `XᵀX` 会把条件数平方，数值稳定性更差。取前 `k` 个奇异值的截断 SVD 可以近似 `O(ndk)`。

</details>

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

<details><summary>答案与解析</summary>

`S_B = Σ_{c=1}^{C} n_c(μ_c − μ)(μ_c − μ)ᵀ` 是 `C` 个秩 1 矩阵之和，故 `r(S_B) ≤ C`。

但类均值满足 `μ = (1/n)Σ_c n_c μ_c`，即 `Σ_c n_c(μ_c − μ) = 0`：这 `C` 个中心化向量存在一个线性相关关系，故其中只有 `C − 1` 个线性无关，于是

`r(S_B) ≤ C − 1`

而秩等于非零特征值的个数，`S_W⁻¹S_B` 最多有 `C − 1` 个非零特征值，每个非零特征值对应一个有效的判别方向，故最多提取 `C − 1` 维。

**二分类（`C = 2`）时只能降到 1 维**：把原本可能上百维的两类数据压到一个标量上，虽然最大化了两类的可分性，但信息损失可能极大——这正是真题 `【09-04 选择 Q8】` 中"LDA 必定优于 PCA"这一说法不成立的核心理由。此外当类内协方差差异悬殊或样本远少于维度时，LDA 会因 `S_W` 奇异而严重退化。

</details>

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

<details><summary>答案与解析</summary>

**A 正确，D 正确；B 错误，C 错误。**

- A：PCA 的目标是 `uᵀCu` 最大（等价于重构误差最小），不用标签；LDA 最大化广义瑞利商 `(wᵀS_B w)/(wᵀS_W w)`，必须用标签。
- B：监督性说反了。PCA **无监督**，LDA **有监督**。
- C：错在"必定"。二分类时 LDA 只能降到 1 维，信息损失可能极大；且类内协方差差异悬殊、或样本数远少于维度时 LDA 严重退化；此外 LDA 的判别方向未必与最大方差方向一致，当两者冲突时 LDA 反而丢掉了更多总方差。
- D：正确，由 `r(S_B) ≤ C − 1` 推出。

</details>

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

<details><summary>答案与解析</summary>

t-SNE 最小化 `KL(P‖Q) = Σ p_ij ln(p_ij/q_ij)`。高维相似度用高斯核，`p_ij ∝ exp(−‖x_i−x_j‖²/(2σ²))`，**远点的 `p_ij` 迅速趋近 0**；低维相似度用重尾的 t 分布，`q_ij ∝ (1+‖y_i−y_j‖²)⁻¹`。

由于 `KL(P‖Q)` 中 `p_ij` 是权重，`p_ij ≈ 0` 的点对（即原空间中本来就远的点对）对损失几乎没有贡献，优化因此**只关心"原本邻近的点对"**——这就是"保局部"。同时低维重尾分布产生斥力，把不同簇推开，使视觉上簇间空隙被显著放大。

必须遵守的纪律：

1. **不要解读簇间距离**——簇间的空隙大小由重尾斥力与 perplexity 决定，不是原空间距离的反映；
2. **不要跨图比较**——结果有随机性（依赖初始化与随机种子），不同 perplexity/不同运行得到的是不同的图；
3. **不要用簇的疏密推断原始密度**——低维密度是优化目标塑造出来的；
4. 需要全局结构时改用 UMAP，或先做 PCA 看整体轮廓。

</details>

## 与真题的关联

| 真题 | 考查角度 | 对应本章小节 |
|---|---|---|
| 【09-04 选择 Q8】PCA vs LDA | PCA 最大化总方差（等价于最小化重构误差）、无监督；LDA 最大化广义瑞利商、有监督；LDA 维数上限 `C−1`，二分类只能降到 1 维，"必定优于"不成立 | 11.2.3、11.2.2 |
| 【09-02 选择 Q10】累计贡献率 | 协方差矩阵第 `i` 个特征值即第 `i` 主成分上的方差，故用 `Σ_{i≤k}λ_i / Σλ` 判断保留几维；干扰项是均值、特征向量模长、方差倒数 | 11.1.4 |
| 【09-09 选择 Q2】协方差矩阵维度 | `d` 维特征的协方差矩阵是 `d×d`，与样本数无关 | 11.1.1、11.1.4 |

## 延伸阅读

- 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。


---

> 作者: [破戒僧](https://onlyblacktea.cn)  
> URL: https://onlyblacktea.cn/book/ai/ch11/  

