## **2. VC 维（Vapnik-Chervonenkis Dimension）** VC 维（**Vapnik-Chervonenkis 维数**）是一种**衡量假设类复杂度**的数学工具，表示某个假设空间 $H$ 在最坏情况下能够**完全分开**（shatter）的点的最大数量。 ### **核心概念** - **Shattering（打散）**：如果一个假设类 $H$ 能够对某个数据集 $S$ 的所有可能标注方式都正确分类，则称 $H$ **shatter** 了 $S$。 - **VC 维**：能被假设类 $H$ 打散的**最多样本数**。 ### **VC 维的计算** 假设 $H$ 是某个模型的假设空间： - 如果存在某个样本集 $S$（大小为 $d$），使得 $H$ 能对其进行**所有可能的二分类方式**（即 $2^d$ 种标注），则 VC 维至少是 $d$。 - 如果对于所有大小 $d+1$ 的数据集，都存在至少一种标注无法被 $H$ 实现，则 VC 维为 $d$。 ### **VC 维的例子** 1. **感知机（线性分类器）** - 在二维空间中，感知机可以完全正确地分类任意三个点（无论如何标注），但无法对任意四个点的所有可能标注都做到完美分类。因此，VC 维为 **3**。 2. **k 维线性分类器** - 在 k 维空间中的线性分类器，其 VC 维为 **k+1**。 3. **单层神经网络（感知机）** - 二维感知机的 VC 维 = 3 - 三维感知机的 VC 维 = 4 - 以此类推，n 维感知机的 VC 维 = n + 1 4. **决策树** - 叶子节点数为 $T$ 的决策树，其 VC 维通常是 $O(T)$。