在之前关于经验过程和经验风险最小化的文章中，我们提到了这样一个例子：如果我们想要通过最小化经验风险\(\frac{1}{n}\sum_{i=1}^n\ell(y_i,f(x_i))\) 来最小化实际的风险 \(\mathbb{E}\ell(Y,f(X))\)，通常是用一个叫“悔恨”的量来刻画这个经验风险最小化的函数的实际损失的. 而对它的控制实际上是通过 \[ \mathcal{R}(\widehat{f})-\mathcal{R}(f^*)\leq 2\sup_{f\in\mathcal{F}}|(P_n-P)f| \] 实现的. 那么在这篇文章中, 我们就来说明如何控制上式的右端项，并得到“悔恨”的收敛速度. 这里用的核心技术就是Rademacher 复杂度. 在这篇文章中，我们主要要把这个右端项和Rademacher复杂度联系起来，来说明为什么通过Rademacher复杂度的收敛，我们可以得到悔恨的收敛阶.
Rademacher 复杂度的定义
在引入Rademacher复杂度的定义之前，我们首先把问题做一步转化. 实际上想要控制\(\sup_{f\in\mathcal{F}}|(P_n-P)f|:=\parallel P_n-P\parallel_{\mathcal{F}}\)是一个比较困难的事情. 因为这实际上是一个随机变量. 不过如果我们把函数类\(\mathcal{F}\)限制在\(\{0,1\}\)值的函数的样本空间上的函数，那么它是差有界的\((1/n)\). 于是McDiarmd不等式导出 \[ P(|\parallel P_n-P\parallel_{\mathcal{F}}-\mathbb{E}\parallel P_n-P\parallel_{\mathcal{F}}|\geq t)\leq 2\exp\{-2nt^2\} \] 于是我们将首先考虑对\(\mathbb{E}\parallel P_n-P\parallel_{\mathcal{F}}\)的控制. 这里用了一个非常经典的技巧：对称化(symmetrization). 在运用这一技巧时，我们经常会引入一个“影子样本”. 即我们假设了另一个样本量为 \(n\) 的样本 \(X_1',X_2',\cdots,X_n'\)，这个样本和原来的样本是独立且同分布的. 除了在这里的应用外，我们也经常利用表达式\(Var(X)=\mathbb{E}(X-X')^2/2\) 来进行一些计算.
下面我们具体计算 \[ \begin{align} \mathbb{E}\parallel P_n-P\parallel_{\mathcal{F}} &= \mathbb{E}[\mathbb{E}[\sup_{f\in\mathcal{F}}|(P_n-P)f|\big|X_1,\cdots,X_n]] \\ &=\mathbb{E}[\sup_{f\in \mathcal{F}}\mathbb{E}|\frac{1}{n}\sum_{i=1}^n[f(X_i)-f(X_i')|\big | X_1,\cdots,X_n]]\\ &\leq \mathbb{E}\Bigg[\mathbb{E}\bigg[\sup_{f\in\mathcal{F}}\big|\frac{1}{n}\sum_{i=1}^n [f(X_i)-f(X_i')]\big|X_1,\cdots,X_n\bigg]\Bigg] \\ &=\mathbb{E}\Big[\sup_{f\in\mathcal{F}}\bigg|\frac{1}{n}\sum_{i=1}^n\big(f(X_i)-f(X_i')\big)\bigg|\Big] \end{align} \] 在这个计算中，不等号是因为\(\sup\)是一个凸函数. 观察最后一行的表达式，我们引入Rademacher随机变量\(\epsilon_i\). (即均匀取正负1的随机变量). 由于 \[ \big(f(X_i)-f(X_i')\big) \overset{d}{=}\epsilon_i\big(f(X_i)-f(X_i')\big) \] 于是上式可以进一步计算得到 \[ \begin{align} \mathbb{E}\parallel P_n-P\parallel_{\mathcal{F}}\ &\leq\mathbb{E}\Big[\sup_{f\in\mathcal{F}}\bigg|\frac{1}{n}\sum_{i=1}^n\big(f(X_i)-f(X_i')\big)\bigg|\Big]\\ &=\mathbb{E}\Big[\sup_{f\in\mathcal{F}}\bigg|\frac{1}{n}\sum_{i=1}^n\epsilon_i\big(f(X_i)-f(X_i')\big)\bigg|\Big]\\ &\leq \mathbb{E}[\sup_{f\in \mathcal{F}}|\frac{1}{n}\sum_{i=1}^n\epsilon_if(X_i)|]+\mathbb{E}[\sup_{f\in \mathcal{F}}|\frac{1}{n}\sum_{i=1}^n\epsilon_if(X_i')|]\\ &=2\mathbb{E}\big[\sup_{f\in\mathcal{F}}|\frac{1}{n}\sum_{i=1}^n\epsilon_if(X_i)|\big] \end{align} \] 于是我们就把 \(\mathbb{E}\sup_{f\in\mathcal{F}}|\frac{1}{n}\sum_{i=1}^n\epsilon_if(X_i)|\) 定义成Rademacher复杂度,我们用记号\(\mathbb{E}\parallel R_n \parallel_{\mathcal{F}}\) 来表示它.
在这些计算中引入Rademacher随机变量的操作看上去匪夷所思. 下面我们将从不同的角度来探究引入Rademacher复杂度的必要性.
Rademacher 复杂度与泛化误差
考虑一个分类问题. 训练数据为\(D=\{(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)\}\)，假设我们训练了一个分类器\(h\)(0,1值函数), 那么训练误差就是 \[ \mathcal{R}_n(h)=\frac{1}{n}\sum_{i=1}^n\mathbf{1}_{y_i\neq h(x_i)}=\frac{1}{2}-\frac{1}{n}\sum_{i=1}^n\frac{y_ih(x_i)}{2} \] 因此最小化训练误差就是最大化 \[ \frac{1}{n}\sum_{i=1}^n y_ih(x_i) \] 假设\(h\)是从\(\mathcal{F}\)中选出的一个分类器. 那么在最坏情况下这一项究竟有多大？我们假设\(y_i\)和\(h(x_i)\)是独立的. 可以把\(y_i\)看作是一个完全随机均匀的标签，此时的分类结果应当能代表分类器的最差分类性能. 而如果要用来衡量一个函数类\(\mathcal{F}\)的表达能力，自然是想要找到这个量的最大值. 我们我们会关注 \(\sup_{h\in\mathcal{F}}\frac{1}{n}\sum_{i=1}^n y_ih(x_i)\) 这一项. 对其取期望则是去除了随机性后的结果. 我们自然能意识到Rademacher复杂度能够帮助我们控制住分类器的泛化误差性能. 事实上根据我们之前对McDiarmd不等式的讨论, 我们可以直接把Rademacher复杂度放在“悔恨”项的右端. 这就是一个非常简单的泛化误差界了.
Rademacher复杂度是紧的
另一方面，由于在第一步问题转化中我们把\(\parallel P_n-P\parallel_{\mathcal{F}}\)转化成了其数学期望来处理. 这一步操作是否会导致我们损失收敛阶呢？
利用反对称化(desymmetrization)操作，我们可以讨论这个问题. 实际上 \[ \begin{align} \mathbb{E}\parallel R_n \parallel_{\mathcal{F}}&= \mathbb{E}\sup_{f\in\mathcal{F}}|\frac{1}{n}\sum_{i=1}^n\epsilon_if(X_i)| = \mathbb{E}\sup_{f\in\mathcal{F}}|\frac{1}{n}\sum_{i=1}^n\epsilon_i\big(f(X_i)-\mathbb{E}f(X)+\mathbb{E}f(X)\big)|\\ &\leq \mathbb{E}\sup_{f\in\mathcal{F}}|\frac{1}{n}\sum_{i=1}^n\epsilon_i[f(X_i)-Pf]|+\mathbb{E}\sup_{f\in\mathcal{F}}|\frac{1}{n}\sum_{i=1}^n\epsilon_iPf| \end{align} \] 其中第一项可以被\(2\mathbb{E}\parallel P_n-P \parallel_{\mathcal{F}}\)控制，第二项可以被\(\sqrt{2\log 2/n}\) 控制. 从而结合之前的结论，有 \[ \frac{1}{2}\mathbb{E}\parallel R_n \parallel_{\mathcal{F}}-\sqrt{\frac{\log 2}{2n}}\leq \mathbb{E}\parallel P_n-P\parallel_{\mathcal{F}}\leq 2\mathbb{E}\parallel R_n \parallel_{\mathcal{F}} \] 这说明这是紧的. 如果我们不引入Rademacher变量，那么左边减去那一项的收敛速度将会和\(n\)无关，这会导致这个界不再是紧的.
最后，如何通过Rademacher复杂度来分析泛化误差的收敛阶呢？我们将在之后的文章中介绍几个控制Rademacher 复杂度的量. 从本质上来说，它们都是控制一个函数族的复杂度(或者说表达能力)的量. 例如VC纬度，覆盖数，括号数，填补数等.