VC 维与 Rademacher 复杂度

【概述】

在 PAC 学习理论概述 中，介绍了 PAC 学习理论，由于恰 PAC 学习并不实际，因此更重要的是研究假设空间 $\mathcal{H}$ 与概念类 $\mathcal{C}$ 不同的情景，即在给定 $n$ 个样本的训练集 $D$ 时，找出满足误差参数 $\epsilon$ 的假设

在 $|\mathcal{H}|$ 无限时，称假设空间 $\mathcal{H}$ 为无限假设空间，现实学习任务所面临的通常都是无限假设空间，例如实数域中的所有空间、$\mathbb{R}^{d}$​ 空间中的所有线性超平面等，要想对该种情形的可学习性进行研究，就需要度量假设空间的复杂度，最常见的方法就是考虑假设空间的 VC 维（Vapnik-Chervonenkis Dimension）

而由于基于 VC 维的泛化误差界是分布无关、数据独立的，也就是说，对任何数据分布都成立，这使得基于 VC 维的可学习性分析结果具有一定的普适性，但从另一方面来说，由于没有考虑数据自身，基于 VC 维得到的泛化误差界通常比较松，对那些与学习问题的典型情况相差甚远的较坏分布来说尤其如此

Rademacher 复杂度（Rademacher Complexity）是另一种刻画假设空间复杂度的途径，与 VC 维不同的是，它在一定程度上考虑了数据分布

【基本概念】

增长函数

给定假设空间 $\mathcal{H}$ 和样本集 $D=\{\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_n\}$，$\mathcal{H}$ 中每个假设 $h$ 都能对 $D$ 中的样本赋予标记，标记结果可表示为：

$$h_{|D} = \Big\{\big(h(\mathbf{x}_1),h(\mathbf{x}_2),\cdots,h(\mathbf{x}_n)\big)\Big\}$$

随着 $n$ 的增大，$\mathcal{H}$ 中所有假设对 $D$ 中样本所能赋予标记的可能结果数也会增大，对所有 $n\in \mathbb{N}$，假设空间 $\mathcal{H}$ 的增长函数为：

$$\Pi_{\mathcal{H}}(n) = \max_{\{\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_n\}\subseteq\mathcal{X}} \Big|\Big\{\big(h(\mathbf{x}_1),h(\mathbf{x}_2),\cdots,h(\mathbf{x}_n)\big)\Big|h\in \mathcal{H}\Big\}\Big|$$

其表示假设空间 $\mathcal{H}$ 对 $n$ 个样本所能赋予标记的最大可能数

显然，$\mathcal{H}$ 对样本所能赋予标记的可能结果数越大，假设空间 $\mathcal{H}$ 的表示能力越强，对学习任务的适应能力也就越强

因此，增长函数可认为描述了假设空间 $\mathcal{H}$ 的表示能力，由此反映出假设空间的复杂度，可以用其来估计经验误差和泛化误差之间的关系

$$P(|E(h)-\hat{E}(h)|>\epsilon) \leq 4\Pi_{\mathcal{H}}(2n)\exp (-\frac{m\epsilon^2}{8})$$

对分和打散

假设空间 $\mathcal{H}$ 中不同的假设对于 $D$ 中样本赋予标记的结果可能相同，也可能不同

尽管 $\mathcal{H}$ 可能包括无穷多个假设，但其对 $D$ 中样本赋予标记的可能结果数是有限的，即对于 $n$ 个样本，最多有 $2^n$ 个可能结果

在二分类问题中，$\mathcal{H}$ 中的假设对 $D$ 中赋予标记的每种可能结果称为对 $D$ 的一种对分，若假设空间 $\mathcal{H}$ 能实现样本集 $D$ 上的所有对分，即：

$$\Pi_{\mathcal{H}}(n)=2^n$$

则称样本集 $D$ 能被假设空间 $\mathcal{H}$ 打散

【VC 维】

定义

假设空间 $\mathcal{H}$ 的 VC 维是能被 $\mathcal{H}$ 打散的最大样本集大小，即：

$$VC(\mathcal{H}) = \max \{ n: \Pi_{\mathcal{H}}(n) = 2^n \}$$

$VC(\mathcal{H})=d$​ 表明存在大小为 $d$ 的样本集能被假设空间 $\mathcal{H}$ 打散，但这并不意味着所有大小为 $d$ 的样本集都能被假设空间 $\mathcal{H}$ 打散

需要注意的是，根据 VC 维的定义，其与数据分布 $\mathcal{D}$ 无关，因此在数据分布未知时仍能计算出假设空间 $\mathcal{H}$ 的 VC 维

通常计算 $\mathcal{H}$​ 的 VC 维的方式是：若存在大小为 $d$​ 的样本集能被 $\mathcal{H}$​ 打散，但不存在任何大小为 $d＋1$​ 的样本集能被 $\mathcal{H}$​ 打散，则 $\mathcal{H}$​ 的 VC 维是 $d$

泛化误差界

从 VC 维的定义出发，VC 维与增长函数有密切联系，下述引理给出了两者间的定量关系：

若假设空间 $\mathcal{H}$ 的 VC 维为 $d$，则对任意整数 $n\in N$，有：

$$\Pi_{\mathcal{H}}(n) \leq \sum_{i=0}^d \left( \begin{array}{c} n\\i \end{array} \right)$$

从该引理出发，可以计算出增长函数的上界：

若假设空间 $\mathcal{H}$ 的 VC 维为 $d$，则对任意整数 n\geq d$，有：

$$\Pi_{\mathcal{H}}(n) \leq (\frac{e\cdot n}{d})^d$$

根据上述引理和增长函数的上界，可以得出基于 VC 维的泛化误差界：

若假设空间 $\mathcal{H}$ 的 VC 维为 $d$，则对任意整数 $n> d$ 与 $0<\delta<1,h\in\mathcal{H}$，有：

$$P\Big( E(h) - \hat{E}(h) \leq \frac{8d\ln \frac{2en}{d}+8\ln \frac{4}{\delta}}{n} \Big) \geq 1-\delta$$

由上述定理可知，基于 VC 维的泛化误差界只与样本数目 $n$ 有关，收敛速率为 $O(\frac{1}{\sqrt{n}})$，与数据分布 $D$ 和样本集 $D$ 无关，因此，基于 VC 维的泛化误差界是分布无关（Distribution-free）、数据独立（Data-independent）的

若令 $h$ 表示学习算法 $\mathcal{L}$ 输出的假设，且 $h$ 满足：

$$\hat{E}(h) = \min_{h'\in\mathcal{H}} \hat{E}(h')$$

则称 $\mathcal{L}$​ 为满足经验最小化（Empirical Risk Minimization，ERM）原则的算法

再令 $g$ 表示 $\mathcal{H}$ 中具有最小泛化误差的假设，即：

$$E(g) = \min_{h\in\mathcal{H}} E(h)$$

根据基于 VC 维的泛化误差界有：

$$P(E(h)-\hat{E}(h)\leq \frac{\epsilon}{2}) \geq 1-\frac{\delta}{2}$$

而在样本数量 $n$ 较大时，假设 $h$ 的经验误差 $\hat{E}(h)$ 是其泛化误差 $E(h)$ 很好的近似

从而可得：

$$\begin{align*} E(h) - E(g) &\leq \hat{E}(h) +\frac{\epsilon}{2}-(\hat{E}(g)-\frac{\epsilon}{2}) \\ &=\hat{E}(h)-\hat{E}(h)+\epsilon \\ &\leq \epsilon \end{align*}$$

至少以 $1-\delta$ 的概率成立，再取

$$\delta'=\frac{\delta}{2},\sqrt{\frac{(\ln \frac{2}{\delta'})}{2n}}=\frac{\epsilon}{2}$$

有：

$$\hat{E}(g) -\frac{\epsilon}{2} \leq E(g) \leq \hat{E}(g)+\frac{\epsilon}{2}$$

至少以 $1-\frac{\delta}{2}$ 的概率成立，令：

$$\sqrt{\frac{8d\ln \frac{2en}{d}+8\ln \frac{4}{\delta'}}{n}} = \frac{\epsilon}{2}$$

可解出 $n$，再由 $\mathcal{H}$ 的任意性，可知任何 VC 维有限的假设空间 $\mathcal{H}$ 都是（不可知）PAC 可学习的

【Rademacer 复杂度】

定义

对于给定训练集 $D=\{(\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),\cdots,(\mathbf{x}_n,y_n)\}$，假设 $h$ 的经验误差为：

$$\begin{align*} \hat{E}(h) &= \frac {1}{n} \sum _ {i=1}^ {n} \mathbb{I}(h(\mathbf{x}_ {i} ) \neq y_ {i} )\\ &= \frac {1}{n} \sum _ {i=1}^ {n} \frac {1-y_ {i}h(\mathbf{x}_ {i})}{2} \\ &= \frac {1}{2} - \frac {1}{2n} \sum _ {i=1}^ {n} y_ {i} h( \mathbf{x}_ {i} ) \end{align*}$$

其中，$\frac{1}{n}\sum\limits{i=1}^ny_ih(\mathbf{x}_i)$ 体现了预测值 $h(\mathbf{x}_i)$ 与样本真实标记 $y_i$ 的一致性

若对于所有的 $i\in \{1,2,\cdots,n\}$ 都有 $h(\mathbf{x}_i)=y_i$，则 $\frac{1}{n}\sum\limits_{i=1}^ny_ih(\mathbf{x}_i)$ 取最大值 $1$，即经验误差最小的假设为：

$$\arg\max_{h\in\mathcal{H}} \frac{1}{n} \sum_{i=1}^n y_ih(\mathbf{x}_i)$$

然而，现实任务中样本的标记有时会受到噪声影响，即对某些样例 $(\mathbf{x}_i,y_i)$，其 $y_i$ 或许已受到随机因素的影响，不再是 $\mathbf{x}_i$ 的真实标记

在这种情况下，选择假设空间 $\mathcal{H}$ 中在训练集上表现最好的假设，有时还不如选择 $\mathcal{H}$ 中事先已考虑了随机噪声影响的假设

考虑随机变量 $\sigma_i$，它以 $0.5$ 的概率取值 $-1$，$0.5$ 的概率取值 $+1$，将其称为 Rademacher 随机变量，那么可将经验误差最小的假设重写为：

$$\sup_{h\in\mathcal{H}} \frac{1}{n} \sum_{i=1}^n \sigma_i h(\mathbf{x}_i)$$

考虑到 $\mathcal{H}$ 中的所有假设，令 $\boldsymbol{\sigma}=\{\sigma_1,\sigma_2,\cdots,\sigma_n\}$ 对上式取期望可得：

$$\mathbb{E}_{\boldsymbol{\sigma}}\Big[\sup_{h\in\mathcal{H}} \frac{1}{n}\sum_{i=1}^n \sigma_i h(\mathbf{x}_i) \Big]$$

上式的取值范围是 $[0,1]$，其体现了假设空间 $\mathcal{H}$ 的表达能力，当 $|\mathcal{H}|=1$ 时，$\mathcal{H}$ 中仅有一个假设，此时可计算出期望为 $0$，当 $|\mathcal{H}|=2^n$ 且 $\mathcal{H}$ 能打散 $D$ 时，对任意 $\boldsymbol{\sigma}$ 总有一个假设使得 $h(\mathbf{x}_i) = \sigma_i$，此时可计算出期望为 $1$​

考虑实值函数空间 $\mathcal{F}:\mathcal{Z}\rightarrow \mathbb{R}$，令 $Z=\{\mathbf{z}_1,\mathbf{z}_2,\cdots,\mathbf{z}_n\},\mathbf{z}_i\in \mathcal{Z}$，将上式期望中的 $\mathcal{X}$ 和 $\mathcal{H}$ 替换为 $\mathcal{Z}$ 和 $\mathcal{F}$，即函数空间 $\mathcal{F}$ 关于 $\mathcal{Z}$ 的经验 Rademacher 复杂度：

$$\hat{R}_{Z}(\mathcal{F}) = \mathbb{E}_{\boldsymbol{\sigma}}\Big[\sup_{f\in\mathcal{F}}\sum_{i=1}^n \frac{1}{n} \sigma_i f(\mathbf{z}_i) \Big]$$

其衡量了函数空间 $\mathcal{F}$ 与随机噪声在集合 $Z$​ 中的相关性

通常来说，希望了解的是函数空间 $\mathcal{F}$ 在 $\mathcal{Z}$ 上关于分布 $\mathcal{D}$ 的相关性，因此，对所有从 $\mathcal{D}$ 上独立同分布采样得到的大小为 $n$ 的集合 $Z$ 求期望可得函数空间 $\mathcal{F}$ 关于 $\mathcal{Z}$ 上分布 $\mathcal{D}$ 的 Rademacher 复杂度

$$R_{n}(\mathcal{F}) = \mathbb{E}_{Z\subseteq \mathcal{Z}:|Z|=n}\Big[ \hat{R}_{Z}(\mathcal{F}) \Big]$$

泛化误差界

基于 Rademacher 复杂度，可得关于函数空间 $\mathcal{F}$​ 的泛化误差界

对于回归问题，实值函数空间 $\mathcal{F}:\mathcal{Z}\rightarrow [0,1]$，令 $0<\delta<1$，根据分布 $\mathcal{D}$ 从 $\mathcal{Z}$ 中独立同分布采样得到的样本集 $Z=\{\mathbf{z}_1,\mathbf{z}_2,\cdots,\mathbf{z}_n\},\mathbf{z}_i\in\mathcal{Z}$，对任意 $f\in\mathcal{F}$，至少以 $1-\delta$ 的概率有：

$$\begin{gather*} \mathbb{E}[f(\mathbf{z})] \leq \frac{1}{n} \sum_{i=1}^n f(\mathbf{z}_i) + 2R_m(\mathcal{F}) + \sqrt{\frac{\ln \frac{1}{\delta}}{2n}} \\ \mathbb{E}[f(\mathbf{z})] \leq \frac{1}{n} \sum_{i=1}^n f(\mathbf{z}_i) + 2\hat{R}_Z(\mathcal{F}) + 3\sqrt{\frac{\ln \frac{2}{\delta}}{2n}} \end{gather*}$$

对于二分类问题，对假设空间 $\mathcal{H}:\mathcal{X}\rightarrow\{-1,+1\}$，令 $0<\delta<1$，根据分布 $\mathcal{D}$ 从 $\mathcal{X}$ 中独立同分布采样得到样本集 $D=\{\mathbf{x}_1,\mathbf{x}_2,\cdots,\mathbf{x}_n\},\mathbf{x}_i\in\mathcal{X}$，对任意 $h\in\mathcal{H}$​，至少以 $1-\delta$ 的概率有：

$$\begin{gather*} \mathbb{E}[h]\leq \hat{\mathbb{E}}[h] + R_m(\mathcal{H}) + \sqrt{\frac{\ln \frac{1}{\delta}}{2n}} \\ \mathbb{E}[h]\leq \hat{\mathbb{E}}[h] + \hat{R}_D(\mathcal{H}) + 3\sqrt{\frac{\ln \frac{2}{\delta}}{2n}} \end{gather*}$$

上述定理给出了与分布 $\mathcal{D}$ 有关的基于 Rademacher 复杂度的泛化误差界，即其依赖于具体学习问题上的数据分布，因此其通常比基于 VC 维的泛化误差界更严格一些

增长函数

对于假设空间 $\mathcal{H}$ 的 Rademacher 复杂度 $R_{n}(\mathcal{H})$ 与增长函数 $\Pi_{\mathcal{H}}(n)$，满足：

$$R_n(\mathcal{H}) \leq \sqrt{\frac{2\ln \Pi_{\mathcal{H}}(n)}{n}}$$

进一步，从 Rademacher 复杂度和增长函数，能够推导出基于 VC 维的泛化误差界，即：

$$\mathbb{E}[h] \leq \hat{\mathbb{E}}(h) + \sqrt{\frac{2d\ln\frac{en}{d}}{n}} + \sqrt{\frac{\ln\frac{1}{\delta}}{2n}}$$