Chapter 3: 复杂度¶
约 3652 个字 预计阅读时间 12 分钟
对于有限维假设空间，我们可以直接使用假设的数目刻画空间的复杂度。但是，对于大多数学习问题来说，假设空间并非是有限的，因此无法直接使用假设的数目刻画空间复杂度，本节将介绍和数据分布 \(\mathcal{D}\) 无关的 VC 维及其扩展 Natarajan 维，以及和数据分布 \(\mathcal{D}\) 相关的 Rademacher 复杂度。
1. 数据分布无关¶
令 \(\mathcal{H}\) 表示假设空间，其中的假设是从 \(\mathcal{X}\) 到 \(\mathcal{Y} = \{-1,+1\}\) 的映射，对于数据集 \(D = \{\boldsymbol{x}_1,\ldots,\boldsymbol{x}_m\} \subset \mathcal{X}\)，\(\mathcal{H}\) 在数据集 \(D\) 上的限制/Restriction 是从 \(D\) 到 \(\{-1,+1\}^m\) 的一族映射（也可以认为是 \(m\) 维向量的集合）：
其中 \(h\) 在 \(D\) 上的限制是一个 \(m\) 维向量。
对于 \(m \in \mathbb{N}\)，假设空间 \(\mathcal{H}\) 的增长函数/Growth Function \(\Pi_{\mathcal{H}}(m)\) 表示为
对于大小为 \(m\) 的数据集 \(D\)，有
增长函数 \(\Pi_{\mathcal{H}}(m)\) 表示假设空间 \(\mathcal{H}\) 对 \(m\) 个样本所能赋予标记的最大可能的结果数。\(\mathcal{H}\) 对样本所能赋予标记的可能结果数越大，\(\mathcal{H}\) 的表示能力越强，对学习任务的适应能力也越强。这样，增长函数就在一定程度上描述了假设空间 \(\mathcal{H}\) 的表示能力，反映了假设空间的复杂程度。
引理 3.1：若假设空间 \(\mathcal{H}\) 的 VC 维为 \(d\)，则对任意 \(m \in \mathbb{N}\) 有
令 \(Q\) 表示能被 \(\mathcal{H}_{D^{\prime}\mid D}\) 打散的集合，这里认为 \(\mathcal{H}_{D^{\prime}\mid D}\) 为假设空间，给每一个 \(\boldsymbol{x}_i\) 提供结果。也就是对于 \(Q\) 的任意的二分类结果，都能在 \(\mathcal{H}_{D^{\prime}\mid D}\) 中找到一个假设 \(h\) 令其实现。并且由 \(\boldsymbol{x}_m\) 与 \(\mathcal{H}_{D^{\prime}\mid D}\) 的定义，\(Q \cup \{\boldsymbol{x}_m\}\) 必能被 \(\mathcal{H}_{D}\) 打散。若 \(Q\) 的大小为 \(k\)，则 \(k + 1 \leq \text{VC}(\mathcal{H}) = d\)，因此 \(\mathcal{H}_{D^{\prime}\mid D}\) 的 VC 维最大为 \(d-1\)，于是有
结合上面的推导，可得
这就完成了证明。
定理 3.1：若假设空间 \(\mathcal{H}\) 的 VC 维为 \(d\)，则对任意整数 \(m \geq d\) 有
证明
根据引理 3.1，有
这就完成了证明。
当假设空间 \(\mathcal{H}\) 的 VC 维无穷大时，任意大小的样本集 \(D\) 都能被 \(\mathcal{H}\) 打散，此时有 \(\Pi_{\mathcal{H}}(m) = 2^m\)，增长函数随着数据集大小的增长而呈指数级增长；当 VC 维有限为 \(d\) 且 \(m \geq d\) 时，由定理 3.1 可知增长函数随着数据集大小的增长而呈多项式级增长。
VC 维仅仅针对二分类问题定义，对于多分类问题，也可以有相应的假设空间复杂度刻画方法，即 Natarajan 维/Natarajan Dimension。在多分类问题中，假设空间 \(\mathcal{H}\) 中的假设是 \(\mathcal{X}\) 到 \(\mathcal{Y} = \{0,\ldots,K-1\}\) 的映射，其中 \(K\) 为类别数。多分类问题中也有相应的增长函数和打散的概念，Natarajan 维也依赖于打散这个概念定义。
多分类问题的增长函数表述与二分类问题一致：
对于给定的集合 \(D \subset \mathcal{X}\)，若假设空间 \(\mathcal{H}\) 中存在两个假设 \(f_0,f_1 : D \mapsto \mathcal{Y}\) 满足以下两个条件：
- 对于任意 \(\boldsymbol{x} \in D\)，\(f_0(\boldsymbol{x}) \neq f_1(\boldsymbol{x})\)，也就是说 \(f_0\) 和 \(f_1\) 对 \(D\) 中的任意样本都有不同的分类结果；
-
对于任意集合 \(B \subset D\) 存在 \(h \in \mathcal{H}\) 使得
\[\forall \boldsymbol{x} \in B, h(\boldsymbol{x}) = f_0(\boldsymbol{x}) \enspace\text{and}\enspace \forall \boldsymbol{x} \in D\setminus B, h(\boldsymbol{x}) = f_1(\boldsymbol{x}),\]
则称集合 \(D\) 能被假设空间 \(\mathcal{H}\) 打散（多分类问题）。
定义 3.2（Natarajan 维）：对于多分类问题的假设空间 \(\mathcal{H}\)，Natarajan 维是能被 \(\mathcal{H}\) 打散的最大样本集的大小，记作 \(\text{Natarajan}(\mathcal{H})\)，我也想记作 \(\mathfrak{N}(\mathcal{H})\)。
下面定理证明，二分类问题的 VC 维与 Natarajan 维相同。
定理 3.2：类别数 \(K = 2\) 时，\(\text{VC}(\mathcal{H}) = \text{Natarajan}(\mathcal{H})\)。
证明
首先证明 \(\text{VC}(\mathcal{H}) \leq \text{Natarajan}(\mathcal{H})\)。令 \(D\) 表示大小为 \(\text{VC}(\mathcal{H})\) 且能被 \(\mathcal{H}\) 打散的集合。取二分类问题打散定义中的 \(f_0,f_1\) 为常值函数，即 \(f_0 = 0,f_1 = 1\)。由于 \(D\) 能被 \(\mathcal{H}\) 打散，则对于任意集合 \(B \subset D\)，存在 \(h_B\) 使得 \(\boldsymbol{x} \in B\) 时 \(h_B(\boldsymbol{x}) = 0\)，\(\boldsymbol{x} \in D\setminus B\) 时 \(h_B(\boldsymbol{x}) = 1\)，这也就是可以实现任意的二分类结果。因此 \(\mathcal{H}\) 可以在多分类意义下打散大小为 \(\text{VC}(\mathcal{H})\) 的 \(D\)，于是有 \(\text{VC}(\mathcal{H}) \leq \text{Natarajan}(\mathcal{H})\)。
再证明 \(\text{VC}(\mathcal{H}) \geq \text{Natarajan}(\mathcal{H})\)。令 \(D\) 表示大小为 \(\text{Natarajan}(\mathcal{H})\) 且在多分类问题中能被 \(\mathcal{H}\) 打散的集合。对于 \(D\) 上的任意一种对分 \(g : D \to \mathcal{Y}\)，令 \(D^+ = \{\boldsymbol{x} \in D|g(\boldsymbol{x}) = 1\}\)，\(D^- = \{\boldsymbol{x} \in D|g(\boldsymbol{x}) = 0\}\)，只需证明存在 \(h \in \mathcal{H}\) 能实现这种分类，即 \(\forall \boldsymbol{x} \in D\) 有 \(h(\boldsymbol{x}) = g(\boldsymbol{x})\)。当 \(K = 2\) 时，\(f_0,f_1 : D \mapsto \mathcal{Y}\)。定义 \(D_i^y = \{\boldsymbol{x} \in D \mid f_i(\boldsymbol{x}) = y\}\)，\(i \in \{0,1\}\)，\(y \in \mathcal{Y}\)。取 \(B = (D^+ \cap D_0^1) \cup (D^- \cap D_0^0)\)，由多分类问题中的打散定义可知存在 \(h \in \mathcal{H}\) 使得 \(\forall \boldsymbol{x} \in B, h(\boldsymbol{x}) = f_0(\boldsymbol{x})\) 且 \(\forall \boldsymbol{x} \in D\setminus B, h(\boldsymbol{x}) = f_1(\boldsymbol{x})\)。由于 \(\forall \boldsymbol{x} \in D\) 有 \(f_0(\boldsymbol{x}) \neq f_1(\boldsymbol{x})\)，通过计算可知，\(\forall \boldsymbol{x} \in B, g(\boldsymbol{x}) = f_0(\boldsymbol{x})\) 且 \(\forall \boldsymbol{x} \in D\setminus B, g(\boldsymbol{x}) = f_1(\boldsymbol{x})\)。从而可得 \(\forall \boldsymbol{x} \in D\) 有 \(h(\boldsymbol{x}) = g(\boldsymbol{x})\)，即 \(\mathcal{H}\) 能打散大小为 \(\text{Natarajan}(\mathcal{H})\) 的 \(D\)，于是有 \(\text{VC}(\mathcal{H}) \geq \text{Natarajan}(\mathcal{H})\)。定理得证。
第二段也很直接，直接思考多分类问题语境下的二分类问题打散的本质：第一条定义指出我们可以使用两个映射覆盖任意样本的二分类结果，第二个定义指出我们可以拼凑出任意的二分类结果。
2. 数据分布相关¶
VC 维的定义与数据分布无关，因此基于 VC 维的分析结果是分布无关的。这使得基于 VC 维的分析结果具有一定的普适性，但是由于没有考虑数据自身，因此基于 VC 维的分析结果通常比较松，对那些与学习问题的典型情况相差较远的数据分布来说尤其如此。
Rademacher 复杂度的来源
给定数据集 \(D = \{(\boldsymbol{x}_1,y_1),\ldots,(\boldsymbol{x}_m,y_m)\}\)，\(h \in \mathcal{H}\) 的经验误差为
其中 \(\frac{1}{m}\sum_{i=1}^m y_ih(\boldsymbol{x}_i)\) 体现了预测值 \(h(\boldsymbol{x}_i)\) 与样本真实标记记号 \(y_i\) 之间的一致性。若 \(\forall i \in [m], h(\boldsymbol{x}_i) = y_i\)，则 \(\frac{1}{m}\sum_{i=1}^m y_ih(\boldsymbol{x}_i)\) 取得最大值 1，也就是说具有最小经验误差的假设是
然而，现实任务中样本的标记有时会受到噪声的影响，即对某些样本 \((\boldsymbol{x}_i,y_i)\)，标记 \(y_i\) 或许已经受到随机因素的影响，不再是 \(\boldsymbol{x}_i\) 的真实标记。在此情形下，选择假设空间 \(\mathcal{H}\) 中在训练集上表现最好的假设，可能不知选择 \(\mathcal{H}\) 中事先已考虑了噪声影响的假设。
给定数据集 \(D = \{(\boldsymbol{x}_1,y_1),\ldots,(\boldsymbol{x}_m,y_m)\}\)，\(h \in \mathcal{H}\)，考虑随机变量 \(\sigma_i\)，它以 0.5 的概率取值 \(+1\)，以 0.5 的概率取值 \(-1\)，称其为 Rademacher 随机变量。基于 \(\sigma_i\) 可将 \(h \in \mathcal{H}\) 的经验误差改写为 \(\sup_{h\in\mathcal{H}} \frac{1}{m}\sum\limits_{i=1}^m \sigma_ih(\boldsymbol{x}_i)\)。对 \(\boldsymbol{\sigma} = (\sigma_1,\cdots,\sigma_m)\) 求期望得到：
这样的值和增长函数有着相似的作用，体现了假设空间在数据集 \(D\) 上的表示能力，取值范围为 \([0,1]\)。当这个值取值为 1 时，意味着对任意 \(\boldsymbol{\sigma} = (\sigma_1,\cdots,\sigma_m)\)，\(\sigma_i \in \{-1,+1\}\)，有
也就是说，存在 \(h \in \mathcal{H}\) 使得 \(h(\boldsymbol{x}_i) = \sigma_i\)，即 \(\Pi_{\mathcal{H}}(m) = 2^m\)，\(\mathcal{H}\) 能打散 \(D\)。总的来说，这个值越接近 1，假设空间的表示能力越强。
考虑实值函数空间 \(\mathcal{F} : \mathcal{Z} \to \mathbb{R}\)，令 \(\mathcal{Z} = \{z_1,\ldots,z_m\}\)，将上面的 \(\mathcal{X}\) 和 \(\mathcal{H}\) 替换为 \(\mathcal{Z}\) 和 \(\mathcal{F}\) 可得我们要的 Rademacher 复杂度。
定义 3.3：函数空间 \(\mathcal{F}\) 关于 \(Z\) 的经验 Rademacher 复杂度为
定义 3.4：函数空间 \(\mathcal{F}\) 关于 \(Z\) 在分布 \(\mathcal{D}\) 的 Rademacher 复杂度为
在经验 Rademacher 复杂度的定义中，\(Z\) 是一个给定的集合。经验 Rademacher 复杂度体现了函数空间 \(\mathcal{F}\) 在数据集 \(Z\) 上的表示能力，在分布 \(\mathcal{D}\) 上独立同分布采样 \(m\) 个样本求期望就可以得到 Rademacher 复杂度。在经验 Rademacher 复杂度和 Rademacher 复杂度的定义中，\(\sigma_i\) 是 \(\{-1,+1\}\) 上服从均匀分布的随机变量，如果将均匀分布改为其他分布，会得到其他一些复杂度的定义，例如 Gaussian 复杂度：我们令随机变量 \(\boldsymbol{g} = (g_1,\cdots,g_m)\) 服从高斯 \(\mathcal{N}(0,1)\) 分布，即标准正态分布。
定义 3.5：函数空间 \(\mathcal{F}\) 关于 \(Z\) 的经验 Gaussian 复杂度为
定义 3.6：函数空间 \(\mathcal{F}\) 关于 \(Z\) 在分布 \(\mathcal{D}\) 的 Gaussian 复杂度为
Rademacher 复杂度与前面介绍的 VC 维用到的增长函数之间也有一定的关系，首先我们需要引入下面的定理。
定理 3.4：令 \(A \subset \mathbb{R}^m\) 为有限集合且 \(r = \max_{\boldsymbol{x}\in A}\|\boldsymbol{x}\|\)，有
其中 \(\boldsymbol{x} = (x_1; \ldots; x_m)\)，\(\sigma_i\) 是 Rademacher 随机变量。
证明
对任意 \(t > 0\) 使用 Jensen 不等式可得
考虑随机变量 \(\sigma_1,\ldots,\sigma_m\) 的独立性，并且使用 Hoeffding 不等式：
对不等式的两边取对数可得
当 \(t = \frac{\sqrt{2\ln|A|}}{r}\) 时，右侧取最小值，可得
两边同时除以 \(m\)，定理得证。
由定理 3.4 可得关于 Rademacher 复杂度与增长函数之间的关系。
推论 3.1：假设空间 \(\mathcal{H}\) 的 Rademacher 复杂度 \(\mathfrak{R}_m(\mathcal{H})\) 与增长函数 \(\Pi_{\mathcal{H}}(m)\) 之间满足
证明
对于 \(D = \{\boldsymbol{x}_1,\ldots,\boldsymbol{x}_m\}\)，\(\mathcal{H}_{\mid D}\) 为假设空间 \(\mathcal{H}\) 在 \(D\) 上的限制。由于 \(h \in \mathcal{H}\) 的值域为 \(\{-1,+1\}\)，可知 \(\mathcal{H}_{\mid D}\) 中的元素为模长 \(\sqrt{m}\) 的向量。因此，由定理 3.4 可得
又因为 \(|\mathcal{H}_{\mid D}| \leq \Pi_{\mathcal{H}}(m)\)，有
从而定理得证。
在下一章，我们就可以看见：基于 Rademacher 复杂度可以推导出比基于 VC 维更紧的泛化误差界。