第3章：复杂性分析

第3章：复杂性分析

Edit: 王茂霖，李一飞，詹好，赵志民

本章前言

在机器学习理论中，复杂性分析与计算理论中的算法复杂度类似，是衡量模型和假设空间能力的关键指标。复杂性越高，模型的表达能力越强，但同时也意味着过拟合的风险增加。因此，研究假设空间的复杂性有助于理解模型的泛化能力，并为模型选择和正则化提供理论依据。

3.1 【概念解释】VC维

VC维（Vapnik-Chervonenkis 维度）是衡量二元分类假设空间 \mathcal{H} 复杂性的重要工具。它表示假设空间能够打散（shatter）的最大样本集的大小，是描述二元分类问题下假设空间复杂度的核心指标。

打散（Shattering） 的定义如下：给定一个大小为 m 的样本集 S = \{x_1, x_2, \dots, x_m\}，如果假设空间 \mathcal{H} 能够对 S 实现所有 2^m 种可能的二元标记（即对每个可能的标签组合 (y_1, \dots, y_m) \in \{-1, +1\}^m，都存在某个 h \in \mathcal{H} 使得 h(x_i) = y_i 对所有 i 成立），则称 \mathcal{H} 打散了 S。

VC维的正式定义如下：

其中，\Pi_{\mathcal{H}}(m) 是假设空间 \mathcal{H} 对大小为 m 的样本集的增长函数（growth function），表示 \mathcal{H} 在任意 m 个点上能产生的不同分类方式的最大数量。VC维可以理解为模型在二元分类问题中有效的自由度。

例子： 对于假设空间 \mathrm{sign}(w^\top x + b)（即线性分类器），其在二维空间 \mathbb{R}^2 中的 VC 维为 3。这意味着，线性分类器能够打散任意三个不共线的点，但无法打散任意四个点（例如，四个点构成凸四边形时，存在一种“异或”型的标签分配无法被线性分类器实现）。

3.2 【概念解释】Natarajan维

在多分类问题（类别数 K \geq 3）中，VC维不再适用，我们使用 Natarajan 维 来描述假设空间的复杂性。Natarajan 维是能被假设空间 \mathcal{H} 打散的最大样本集的大小，这里的“打散”是多分类意义下的推广。

具体而言，一个大小为 m 的样本集 S = \{x_1, \dots, x_m\} 被 \mathcal{H} Natarajan-打散，如果存在两个函数 f, g: S \to \{1, \dots, K\}，使得对任意子集 T \subseteq S，都存在 h \in \mathcal{H} 满足：

• 若 x_i \in T，则 h(x_i) = f(x_i)；
• 若 x_i \notin T，则 h(x_i) = g(x_i)；
• 且对所有 x_i \in S，有 f(x_i) \neq g(x_i)。

Natarajan 维定义为满足上述条件的最大 m。

当类别数 K=2 时，Natarajan 维与 VC 维等价：

对于一般的 K-分类问题，若 \mathcal{H} 的 Natarajan 维为 d，则其增长函数满足以下上界（Natarajan 引理）：

该上界表明，增长函数关于样本数 m 是多项式阶的（而非指数阶），这保证了多分类问题的可学习性。需要注意的是，原文中“\Pi_{\mathcal{H}}(m) \leqslant m^d K^{2d}”虽在形式上接近，但标准文献中更常见的是上述形式或类似变体（如 (cK)^d m^d，其中 c 为常数）。此外，Natarajan 维的复杂度随类别数 K 呈对数或多项式增长，而非指数级增长；原文表述“呈指数级增长”不够准确，应修正为“随 K 和 d 增大而增大，但增长函数关于样本数 m 仍为多项式阶”。

3.3 【概念解释】Rademacher复杂度

VC维和Natarajan维均未考虑数据分布的影响，而 Rademacher 复杂度 则引入了数据分布因素。它通过考察数据的几何结构和函数类的复杂性，提供了更紧致、更实用的泛化误差界，尤其适用于实值函数（如回归、带间隔的分类）和现代深度学习模型的分析。

设 \mathcal{F} 是从输入空间 \mathcal{X} 到 \mathbb{R} 的函数类，Z = (z_1, \dots, z_m) 是从分布 \mathcal{D} 上独立同分布采样的样本集。函数类 \mathcal{F} 关于样本集 Z 的 经验 Rademacher 复杂度 定义为：

其中 \sigma = (\sigma_1, \dots, \sigma_m) 是 Rademacher 随机变量，即每个 \sigma_i 独立地以概率 1/2 取值 +1 或 -1。

总体 Rademacher 复杂度 定义为对样本集的期望：

对于二元分类假设空间 \mathcal{H} \subseteq \{-1, +1\}^{\mathcal{X}}，常将其与损失函数（如 0-1 损失）结合，或考虑其对应的实值函数类（如间隔损失）。Rademacher 复杂度与增长函数之间存在如下关系（Massart 引理的推论）：

这表明 Rademacher 复杂度可由 VC 维控制，但通常能提供更精细的界，尤其当数据分布具有特定结构时。

3.4 【概念解释】Shattering 概念的可视化

Shattering 是指假设空间能够实现样本集上所有可能的二元对分（labelings）的能力。以下通过二维空间 \mathbb{R}^2 中的线性分类器示例来说明。

示例： 对于二维空间 \mathbb{R}^2 中的任意三个不共线的点，线性分类器 \mathrm{sign}(w^\top x + b) 可以实现所有 2^3 = 8 种对分。然而，对于任意四个点（例如，四个点构成凸四边形），存在至少一种对分（如“异或”模式：相邻点标签相同，对角点标签不同）无法被任何线性分类器实现。因此，线性分类器在 \mathbb{R}^2 中的 VC 维为 3。

下图展示了三个点可被完全打散，而四个点（凸四边形）无法被完全打散的情形：

该图示说明了为何线性分类器在二维空间中的 VC 维恰好为 3：它能打散任意三个点，但不能打散任意四个点。