计算学习理论

1. 基础知识

计算学习理论（computational learning theory）研究的是关于通过“计算”来进行“学习”的理论，即关于机器学习的理论基础，其目的是分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计。
给定样例集\(D = \{(\pmb{x}_1,y_1),(\pmb{x}_2,y_2),\cdots, (\pmb{x}_m,y_m)\},\pmb{x}_i \in \mathscr{X}\)，这里主要讨论二分类问题，\(y_i \in \mathscr{Y} = \{-1,+1\}\)。假设\(\mathscr{X}\)中的所有样本服从一个隐含未知的分布\(\mathscr{D}\)，\(D\)中所有样本都是独立地从这个分布上采样而得，即独立同分布（independent and identically distributed，iid）样本。
令\(h\)为从\(\mathscr{X}\)到\(\mathscr{Y}\)的一个映射，其泛化误差为 \[E(h;\mathscr{D}) = P_{\pmb{x} \sim\mathscr{D}} (h(\pmb{x}) \neq y)\] \(h\)在\(D\)上的经验误差为 \[\hat{E}(h;D) = \frac{1}{m} \sum_{i=1}^m I(h(\pmb{x}_i) \neq y_i)\] 由于\(D\)是\(\mathscr{D}\)的独立同分布采样，因此\(h\)的经验误差的期望等于其泛化误差。上下文明确时，将\(E(h;\mathscr{D})\)和\(\hat{E}(h;D)\)分别简记为\(E(h)\)和\(\hat{E}(h)\)。令\(\epsilon\)为\(E(h)\)的上限，即\(E(h) \leqslant \epsilon\)；通常用\(\epsilon\)表示预先设定的学得模型所应满足的误差要求，亦称“误差参数”。
若\(h\)在数据集\(D\)上的经验误差为0，则称\(h\)与\(D\)一致，否则称其与\(D\)不一致。对任意两个映射\(h_1,h_2 \in \mathscr{X} \to \mathscr{Y}\)，可通过其“不合”（disagreement）来度量它们之间的差别： \[d(h_1,h_2) = P_{\pmb{x} \sim \mathscr{D}} (h_1(\pmb{x}) \neq h_2(\pmb{x}))\] 会用到以下不等式：
Jensen不等式：对任意凸函数\(f(x)\)，有 \[f(E(x)) \leqslant E(f(x))\] Hoeffding不等式：若\(x_1,x_2,\cdots,x_m\)为\(m\)个独立随机变量，且满足\(0 \leqslant x_i \leqslant 1\)，则对任意\(\epsilon > 0\)，有 \[\begin{equation} P(\frac{1}{m} \sum_{i=1}^m x_i - \frac{1}{m} \sum_{i=1}^m E(x_i) \geqslant \epsilon) \leqslant exp(-2 m \epsilon^2) \nonumber \\ P(|\frac{1}{m} \sum_{i=1}^m x_i - \frac{1}{m} \sum_{i=1}^m E(x_i)| \geqslant \epsilon) \leqslant 2 exp(-2 m \epsilon^2) \nonumber \end{equation}\] McDiarmid不等式：若\(x_1,x_2,\cdots,x_m\)为\(m\)个独立随机变量，且对任意\(1 \leqslant i \leqslant m\)，函数\(f\)满足 \[\sup_{x_1,\cdots,x_m,x_i'}||f(x_1,\cdots,x_m) - f(x_1,\cdots,x_{i-1},x_i',x_{i+1},\cdots,x_m)|| \leqslant c_i\] 则对任意\(\epsilon > 0\)，有 \[\begin{equation} P(f(x_1,\cdots,x_m) - E(f(x_1,\cdots,x_m)) \geqslant \epsilon) \leqslant \exp(\frac{-2 \epsilon^2}{\sum_i c_i^2}) \nonumber \\ P(|f(x_1,\cdots,x_m) - E(f(x_1,\cdots,x_m))| \geqslant \epsilon) \leqslant 2 \exp(\frac{-2 \epsilon^2}{\sum_i c_i^2}) \nonumber \end{equation}\]

2. PAC学习

计算学习理论中最基本的是概率近似正确（Probably Approximately Correct，PAC）学习理论。
令\(c\)表示“概念”（concept），这是从样本空间\(\mathscr{X}\)到标记空间\(\mathscr{Y}\)的映射，它决定实例\(\pmb{x}\)的真实标记\(y\)，若对任何样例\((\pmb{x},y)\)有\(c(\pmb{x}) = y\)成立，则称\(c\)为目标概念；所有我们希望学得的目标概念所构成的集合称为“概念类”（concept class），用\(\mathscr{C}\)表示。
给定学习算法\(\mathscr{L}\)，它所考虑的所有可能概念的集合称为“假设空间”（hypothesis space），用户号\(\mathscr{H}\)表示。由于学习算法事先并不知道概念类的真实存在，因此\(\mathscr{H}\)和\(\mathscr{C}\)通常是不同的，学习算法会把自认为可能的目标概念集中起来构成\(\mathscr{H}\)，对\(h \in \mathscr{H}\)，由于并不能确定它是否真是目标概念，因此称为“假设”（hypothesis）。显然，假设\(h\)也是从样本空间\(\mathscr{X}\)到标记空间\(\mathscr{Y}\)的映射。
若目标概念\(c \in \mathscr{H}\)，则\(\mathscr{H}\)中存在假设能将所有示例按与真实标记一致的方式完全分开，称该问题对学习算法\(\mathscr{L}\)是“可分的”（separable），亦称“一致的”（consistent）；若\(c \notin \mathscr{H}\)，则\(\mathscr{H}\)中不存在任何假设能将所有示例完全正确分开，称该问题对学习算法\(\mathscr{L}\)是“不可分的”（non-separable），亦称“不一致的”（non-consistent）。
给定训练集\(D\)，希望基于学习算法\(\mathscr{L}\)学得的模型所对应的假设\(h\)尽可能接近目标概念\(c\)。这里是尽可能的接近，因为想要精确地学到目标概念\(c\)是很困难的，由于机器学习过程受到很多因素的制约，例如获得训练集\(D\)往往仅包含有限数量的样例，从分布\(\mathscr{D}\)采样得到的\(D\)的过程有一定偶然性，即便对同样大小的不同训练集，学得结果也可能有所不同。因此，我们是希望以比较大的把握学得比较好的模型，即以较大的概率学得误差满足预设上限的模型，这就是“概率”“近似正确”的含义。形式化地说，令\(\delta\)表示置信度，可定义： PAC辨识（PAC Identify）：对\(0 < \epsilon, \delta < 1\)，所有\(c \in \mathscr{C}\)和分布\(\mathscr{D}\)，若存在学习算法\(\mathscr{L}\)，其输出假设\(h \in \mathscr{H}\)满足 \[P(E(h) \leqslant \epsilon) \geqslant 1 - \delta\] 则称学习算法\(\mathscr{L}\)能从假设空间\(\mathscr{H}\)中PAC辨识概念类\(\mathscr{C}\)。

这样的学习算法\(\mathscr{L}\)能以较大的概率（至少\(1-\delta\)）学得目标概念\(c\)的近似（误差最多为\(\epsilon\)）。在此基础上定义：

PAC可学习（PAC Learnable）：，令\(m\)表示从分布\(\mathscr{D}\)中独立同分布采样得到的样例数目，\(0 < \epsilon, \delta < 1\)，对所有分布\(\mathscr{D}\)，若存在学习算法\(\mathscr{L}\)和多项式函数\(poly(·,·,·,·)\)，使得对任何\(m \geqslant poly(1 / \epsilon, 1 / \delta, size(\pmb{x}),size(c))\)，\(\mathscr{L}\)能从假设空间\(\mathscr{H}\)中PAC辨识概念类\(\mathscr{C}\)，则称概念类\(\mathscr{C}\)对假设空间\(\mathscr{H}\)而言是PAC可学习的，有时也简称概念类\(\mathscr{C}\)是PAC可学习的。

对计算机算法来说，必然要考虑时间复杂度，于是：
PAC学习算法（PAC Learning Algorithm）：若学习算法\(\mathscr{L}\)使概念类\(\mathscr{C}\)为PAC可学习的，且\(\mathscr{L}\)的运行时间也是多项式函数\(poly(1 / \epsilon, 1 / \delta, size(\pmb{x}),size(c))\)，则称概念类\(\mathscr{C}\)是高效PAC可学习（efficiently PAC learnable）的，称\(\mathscr{L}\)为概念类\(\mathscr{C}\)的PAC学习算法。
假定学习算法\(\mathscr{L}\)处理每个样本的时间为常数，则\(\mathscr{L}\)的时间复杂度等价于样本复杂度。于是，对算法时间复杂度的关注就转化为对样本复杂度的关注： 样本复杂度（Sample complexity）：满足PAC学习算法\(\mathscr{L}\)所需的\(m \geqslant poly(1 / \epsilon, 1 / \delta, size(\pmb{x}),size(c))\)中最小的\(m\)，称为学习算法\(\mathscr{L}\)的样本复杂度。

PAC学习给出了一个抽象地刻画机器学习能力的框架，基于这个框架能对很多重要问题进行理论探讨，例如研究某任务在什么样的条件下可学得较好的模型？某算法在什么样的条件下可进行有效的学习？需多少训练样例才能获得较好的模型？

PAC学习中一个关键因素是假设空间\(\mathscr{H}\)的复杂度，\(\mathscr{H}\)包含了学习算法\(\mathscr{L}\)所有可能输出的假设，若在PAC学习中假设空间与概念类完全相同，即\(\mathscr{H} = \mathscr{C}\)，这称为”恰PAC可学习“（properly PAC learnable）；这意味着学习算法的能力与学习任务”恰好匹配“。然而，这种让所有候选假设都来自概念类的要求看似合理，但却并不实际。因为现实应用中我们队概念类通常一无所知，更别说获得一个假设空间与概念类恰好相同的学习算法。显然，更重要的是研究假设空间与概念类不同的情形，即\(\mathscr{H} \neq \mathscr{C}\)。一般而言，\(\mathscr{H}\)越大，其包含的目标概念的可能性越大，但从中找到某个具体目标概念的难度也越大。\(|\mathscr{H}|\)有限时，称\(\mathscr{H}\)为”有限假设空间“，否则称为”无限假设空间“。

3. 有限假设空间

3.1. 可分情形

可分情形意味着目标概念\(c\)属于假设空间\(\mathscr{H}\)，即\(c \in \mathscr{H}\)。我们的目标是在给定包含\(m\)个样例的训练集\(D\)的情况下找出满足误差参数的假设。
一种简单的学习策略：既然\(D\)中样例标记都是由目标概念\(c\)赋予的，并且\(c\)存在于假设空间\(\mathscr{H}\)中，那么，任何在训练集\(D\)上出现标记错误的假设肯定不是目标概念\(c\)。所以只需要保留与\(D\)一致的假设，剔除与\(D\)不一致的假设即可。若训练集\(D\)足够大，则可不断借助\(D\)中的样例剔除不一致的假设，直到\(\mathscr{H}\)中仅剩下一个假设为止，这个假设就是目标概念\(c\)。通常情形下，由于训练及规模有限，假设空间\(\mathscr{H}\)中可能存在不止一个与\(D\)一致的”等效“假设，对这些等效假设，无法根据\(D\)来对它们的优劣做进一步区分。
数据规模：对PAC学习来说，只要训练集\(D\)的规模能使学习算法\(\mathscr{L}\)以概率\(1 - \delta\)找到目标假设的\(\epsilon\)近似即可。
首先估计泛化误差大于\(\epsilon\)但在训练集上仍表现完美的假设出现的概率。假设\(h\)的泛化误差大于\(\epsilon\)，对分布\(\mathscr{D}\)上随机采样而得的任何样例\((\pmb{x},y)\),有 \[\begin{align} P(h(\pmb{x}) = y) &= 1 - P(h(\pmb{x}) \neq y) \nonumber \\ &= 1 - E(h) \nonumber \\ &< 1 - \epsilon \nonumber \end{align}\] 由于\(D\)包含\(m\)个从\(\mathscr{D}\)独立同分布采样而得的样例，因此，\(h\)与\(D\)表现一致的概率为 \[P((h(\pmb{x}_1) = y_1) \wedge \cdots \wedge (h(\pmb{x}_m) = y_m)) = (1 - P(h(\pmb{x}) \neq y))^m < (1 - \epsilon)^m\] 我们事先并不知道学习算法\(\mathscr{L}\)会输出\(\mathscr{H}\)中的哪个假设，但仅需保证泛化误差大于\(\epsilon\)，且在训练集上表现完美的所有假设出现概率之和不大于\(\delta\)即可： \[P(h \in \mathscr{H}:E(h) > \epsilon \wedge \hat{E}(h) = 0) < |\mathscr{H}|(1 - \epsilon)^m < |\mathscr{H}| e^{- m \epsilon}\] 令上式不大于\(\delta\)，即 \[|\mathscr{H}| e^{-m \epsilon} \leqslant \delta\] 可得 \[m \geqslant \frac{1}{\delta} (\ln |\mathscr{H}| + \ln \frac{1}{\delta})\] 有限假设空间\(\mathscr{H}\)都是PAC可学习的，所需样例数目如上式所示，输出假设\(h\)的泛化误差随样例数目的增多而收敛到0，收敛速率为\(O(\frac{1}{m})\)。

3.2. 不可分情形

对于较为困难的学习问题，目标概念\(c\)往往不存在与假设空间\(\mathscr{H}\)中。假定对任何\(h \in \mathscr{H}, \hat{E}(h) \neq 0\)，即\(\mathscr{H}\)中的任意一个假设都会在训练集上出现或多或少的错误，由Hoeffding不等式可知：引理：若训练集包含\(m\)个从分布\(\mathscr{D}\)上独立同分布采样而得的样例，\(0 < \epsilon < 1\)，则对任意\(h \in \mathscr{H}\)，有 \[\begin{equation} P(\hat{E}(h) - E(h) \geqslant \epsilon) \leqslant \exp(-2m \epsilon^2) \nonumber \\ P(E(h) - \hat{E}(h) \geqslant \epsilon) \leqslant \exp(-2m \epsilon^2) \nonumber \\ P(|E(h) - \hat{E}(h)| \geqslant \epsilon) \leqslant 2 \exp(-2m \epsilon^2) \nonumber \end{equation}\]

推论：若训练集\(D\)包含\(m\)个从分布\(\mathscr{D}\)上独立同分布采样而得的样例，\(0 < \epsilon < 1\)，则对任意\(h \in \mathscr{H}\)，下式以至少\(1 - \delta\)的概率成立： \[\hat{E}(h) - \sqrt{\frac{\ln(2 / \delta)}{2m}} \leqslant E(h) \leqslant \hat{E}(h) + \sqrt{\frac{\ln(2 / \delta)}{2m}}\] 上式表明，样例数目\(m\)较大时，\(h\)的经验误差是其泛化误差很好的近似。对于有限假设空间\(\mathscr{H}\)，有

定理：若\(\mathscr{H}\)为有限假设空间，\(0 < \epsilon < 1\)，则对任意\(h \in \mathscr{H}\)，有 \[P(|E(h) - \hat{E}(h)| \leqslant \sqrt{\frac{\ln|\mathscr{H}|+\ln(2/\delta)}{2m}}) \geqslant 1 - \delta\] 证明：令\(h_1,h_2,\cdots,h_{|\mathscr{H}|}\)表示假设空间\(\mathscr{H}\)中的假设，有 \[\begin{align} & \quad P(\exists h \in \mathscr{H}:|E(h) - \hat{E}(h)| > \epsilon) \nonumber \\ &= P((|E_{h_1} - \hat{E}_{h_1}|> \epsilon) \vee \cdots \vee(|E_{h_{|\mathscr{H}|}} - E_{h_{\mathscr{H}}}|> \epsilon)) \nonumber \\ & \leqslant \sum_{h \in \mathscr{H}} P(|E(h) - \hat{E}(h)| > \epsilon) \nonumber \end{align}\]

根据引理可得 \[\sum_{h \in \mathscr{H}} P(|E(h) - \hat{E}(h)| > \epsilon) \leqslant 2 |\mathscr{H}| \exp(-2 m \epsilon^2)\] 令\(\delta = 2 |\mathscr{H}| \exp(-2 m \epsilon^2)\)即可得到 \[P(|E(h) - \hat{E}(h)| \leqslant \sqrt{\frac{\ln|\mathscr{H}|+\ln(2/\delta)}{2m}}) \geqslant 1 - \delta\]

当\(c \notin \mathscr{H}\)时，学习算法\(\mathscr{L}\)无法学得目标概念\(c\)的\(\epsilon\)近似。但当假设空间\(\mathscr{H}\)给定时，其中必存在一个泛化误差最小的假设，找出此假设的\(\epsilon\)近似也是一个不错的目标。\(\mathscr{H}\)中泛化误差最小的假设是\(\arg \min_{h \in \mathscr{H}} E(h)\)，以此为目标可将PAC学习推广到\(c \notin \mathscr{H}\)的情况，这称为”不可知学习“。
不可知PAC可学习（agnostic PAC learnable）：令\(m\)表示从分布\(\mathscr{D}\)中独立同分布采样得到的样例数目，\(0 < \epsilon, \delta < 1\)，对所有分布\(\mathscr{D}\)，若存在学习算法\(\mathscr{L}\)和多项式函数\(poly(·,·,·,·)\)，使得对于任何\(m \geqslant poly(1/\epsilon, 1/\delta, size(\pmb{x}), size(c))\)，\(\mathscr{L}\)能从假设空间\(\mathscr{H}\)中输出满足下式的假设\(h\)： \[P(E(h) - \min_{h' \in \mathscr{H}} (h') \leqslant \epsilon) \geqslant 1 - \delta\] 则称假设空间\(\mathscr{H}\)是不可知PAC可学习的。

与PAC可学习类似，若学习算法\(\mathscr{L}\)的运行时间也是多项式函数\(poly(1/\epsilon, 1/\delta, size(\pmb{x}), size(c))\)，则称假设空间\(\mathscr{H}\)是高效不可知PAC科学系的，学习算法\(\mathscr{L}\)则称为假设空间\(\mathscr{H}\)的不可知PAC学习算法，满足上述要求的最小\(m\)称为学习算法\(\mathscr{L}\)的样本复杂度。

4. VC维

现实学习任务中所面临的通常是无限假设空间，如\(\mathbf{R}^d\)空间中的所有线性超平面，对这种情形的可学习型进行研究，需度量假设空间的复杂度，最常见的办法是考虑假设空间的”VC维“。
首先引入几个概念：增长函数、对分和打散。
给定假设空间\(\mathscr{H}\)和样例集\(D = \{\pmb{x}_1, \pmb{x}_2,\cdots,\pmb{x}_m\}\)，\(\mathscr{H}\)中每个假设\(h\)都能对\(D\)中样例赋予标记，标记结果为 \[h|_D = \{(h(\pmb{x}_1), h(\pmb{x}_2),\cdots, h(\pmb{x}_m))\}\] 随着\(m\)的增大，\(\mathscr{H}\)中所有假设对\(D\)中的样例所能赋予标记的可能结果数也会增大。
增长函数（growth function）：对所有\(m \in \mathbf{N}\)，假设空间\(\mathscr{H}\)的增长函数\(\Pi_{\mathscr{H}}(m)\)为 \[\Pi_{\mathscr{H}}(m) = \max_{\{\pmb{x}_1,\cdots,\pmb{x}_m\} \subseteq \mathscr{X}} | \{(h(\pmb{x}_1),\cdots, h(\pmb{x}_m))| h \in \mathscr{H}\} |\] 增长函数\(\Pi_{\mathscr{H}}(m)\)表示假设空间\(\mathscr{H}\)对\(m\)个样例所能赋予标记的最大可能结果数。\(\mathscr{H}\)对样例所能赋予标记的可能结果数越大，\(\mathscr{H}\)的表示能力越强，对学习任务的适应能力也越强。因此，增长函数描述了假设空间\(\mathscr{H}\)的表示能力，由此反映出假设空间的复杂度。可利用增长函数来估计经验误差与泛化误差之间的关系： 定理12.2：对假设空间\(\mathscr{H}\)，\(m \in \mathbf{N}\)，\(0 < \epsilon < 1\)和任意\(h \in \mathscr{H}\)有 \[P(|E(h) - \hat{E}(h)| > \epsilon) \leqslant 4 \Pi_{\mathscr{H}} (2m) \exp(- \frac{m \epsilon^2}{8})\] 假设空间\(\mathscr{H}\)中不同的假设对于\(D\)中样例赋予标记的结果可能相同，也可能不同；尽管\(\mathscr{H}\)可能包含无穷多个假设，但其对\(D\)中样例赋予标记的可能结果是有限的：对\(m\)个样例，最多有\(2^m\)个可能的结果（二分类问题）。对于二分类问题来说，\(\mathscr{H}\)中的假设对\(D\)中样例赋予标记的每种可能结果成为对\(D\)的一种”对分“。若假设空间\(\mathscr{H}\)能实现样例集上的所有对分，即\(\Pi_{\mathscr{H}}(m) = 2^m\)，则称样例集\(D\)能被假设空间\(\mathscr{H}\)”打散“。

定义：假设空间\(\mathscr{H}\)的VC维是能被\(\mathscr{H}\)打散的最大样例集的大小，即 \[VC(\mathscr{H}) = \max \{m: \Pi_{\mathscr{H}}(m) = 2^m\}\] \(VC(\mathscr{H}) = d\)表明存在大小为\(d\)的样例集能被假设空间\(\mathscr{H}\)打散。
注意：\(VC(\mathscr{H}) = d\)并不意味着所有大小为\(d\)的样例集都能被假设空间\(\mathscr{H}\)打散。VC维的定义与数据分布\(\mathscr{D}\)无关。因此，在数据分布未知时仍能计算出假设空间\(\mathscr{H}\)的VC维。
\(\mathscr{H}\)的VC维计算方式：若存在大小为\(d\)的样例集能被\(\mathscr{H}\)打散，但不存在任何大小为\(d+1\)的样例集能被\(\mathscr{H}\)打散，则\(\mathscr{H}\)的VC维是\(d\)。

示例：

引理：若假设空间\(\mathscr{H}\)的VC维为\(d\)，则对任意\(m \in \mathbf{N}\)有 \[\Pi_{\mathscr{H}} (m) \leqslant \sum_{i=0}^d \binom m i\]

推论12.2：若假设空间\(\mathscr{H}\)的VC维为\(d\)，则对任意整数\(m \geqslant d\)有 \[\Pi_{\mathscr{H}} (m) \leqslant (\frac{e·m}{d})^d\] 证明： \[\begin{align} \Pi_{\mathscr{H}} (m) & \leqslant \sum_{i=0} is ^d \binom m i \nonumber \\ & \leqslant \sum_{i=0}^d \binom m i (\frac{m}{d})^{d - i} \nonumber \\ & = (\frac{m}{d})^d \sum_{i=0}^d \binom m i (\frac{d}{m})^i \nonumber \\ & \leqslant (\frac{m}{d})^d \sum_{i=0}^m \binom m i (\frac{d}{m})^i \nonumber \\ & = (\frac{m}{d})^d (1 + \frac{d}{m})^m \nonumber \\ & \leqslant (\frac{e·m}{d})^d \nonumber \end{align}\]

定理12.3：若假设空间\(\mathscr{H}\)的VC维为\(d\)，则对任意\(m > d\)，\(0 < \delta < 1\)和\(h \in \mathscr{H}\)有 \[P(|E(h) - \hat{E}(h)| \leqslant \sqrt{\frac{8d \ln \frac{2em}{d} + 8 \ln \frac{4}{\delta}}{m}}) \geqslant 1 - \delta\] 证明：令\(4 \Pi_{\mathscr{H}} (2m) \exp(- \frac{m \epsilon^2}{8}) \leqslant 4 (\frac{2em}{d})^d \exp(- \frac{m \epsilon^2}{8}) = \delta\)，解得 \[\epsilon = \sqrt{\frac{8d \ln \frac{2em}{d} + 8 \ln \frac{4}{\delta}}{m}})\] 带入定理12.2，定理12.3得证。
由定理12.3的公式可知，泛化误差界只与样例数目\(m\)有关，收敛速率为\(O(\frac{1}{\sqrt{m}})\)，与数据分布\(\mathscr{D}\)和样例集\(D\)无关。
基于VC维的泛化误差界是分布无关、数据独立的。

令\(h\)表示学习算法\(\mathscr{L}\)输出的假设，若\(h\)满足 \[\hat{E}(h) = \min_{h' \in \mathscr{H}} \hat{E}(h')\] 则称\(\mathscr{L}\)为满足经验风险最小化（ERM）原则的算法，并有以下的定理：
定理12.4：任何VC维有限的假设空间\(\mathscr{H}\)都是（不可知）PAC可学习的。

5. Rademacher复杂度

基于VC维的泛化误差界是分布无关、数据独立的，即对任何数据分布都成立。这使得基于VC维的可学习性分析结果具有一定的”普适性“；但从另一方面看，由于没有考虑数据自身，基于VC维得到的泛化误差界通常比较”松“，对那些与学习问题的典型情况相差甚远的较”坏“分布来说尤其如此。
Rademacher复杂度（Rademacher complexity）是另一种刻画假设空间复杂度的途径，与VC维不同的是，它在一定程度上考虑了数据分布。

给定训练集\(D = \{(\pmb{x}_1,y_1),(\pmb{x}_2,y_2),\cdots,(\pmb{x}_m,y_m)\}\)，假设\(h\)的经验误差为 \[\begin{align} \hat{E}(h) &= \frac{1}{m} \sum_{i=1}^m I(h(\pmb{x}_i) \neq y_i) \nonumber \\ &= \frac{1}{m} \sum_{i=1}^m \frac{1 - y_i h(\pmb{x}_i)}{2} \nonumber \\ &= \frac{1}{2} - \frac{1}{2m} \sum_{i=1}^m y_i h(\pmb{x}_i) \nonumber \end{align}\]

其中\(\frac{1}{m} \sum_{i=1}^m y_i h(\pmb{x}_i)\)体现了预测值\(h(\pmb{x}_i)\)与样例真实标记\(y_i\)之间的一致性，若对于所有\(i \in \{1,2,\cdots,m\}\)都有\(h(\pmb{x}_i) = y_i\)，则\(\frac{1}{m} \sum_{i=1}^m y_i h(\pmb{x}_i)\)取最大值1。也就是说，经验误差最小的假设是 \[\arg \min_{h \in \mathscr{H}} \frac{1}{m} \sum_{i=1}^m y_i h(\pmb{x}_i)\]

然而，现实任务中样例的标记有时会受到噪声的影响，即对某些样例\((\pmb{x}_i,y_i)\)，其\(y_i\)或许是已受到随机因素的影响，不再是\(\pmb{x}_i\)的真实标记，在此情形下，选择假设空间\(\mathscr{H}\)中在训练集上表现最好的假设，有时还不如选择\(\mathscr{H}\)中事先已经考虑了随机噪声影响的假设。

考虑随机变量\(\sigma_i\)，它以0.5的概率取值-1，0.5的概率取值+1，称为Rademacher随机变量，基于\(\sigma_i\)，可将上式重写为 \[\sup_{h \in \mathscr{H}} \frac{1}{m} \sum_{i=1}^m \sigma_i h(\pmb{x}_i)\] 考虑\(\mathscr{H}\)中的所有假设，对上式取期望可得 \[E_{\pmb{\sigma}}[\sup_{h \in \mathscr{H}} \frac{1}{m} \sum_{i=1}^m \sigma_i h(\pmb{x}_i)]\] 其中\(\pmb{\sigma} = \{\sigma_1,\sigma_2,\cdots,\sigma_m\}\)。上式的取值范围是\([0,1]\)，它体现了假设空间\(\mathscr{H}\)的表达能力，例如当\(|\mathscr{H}| = 1\)时，\(\mathscr{H}\)中仅有一个假设，这时可计算出上式的值为0；当\(|\mathscr{H}| = 2^m\)且\(\mathscr{H}\)能打散\(D\)时，对任意\(\pmb{\sigma}\)总有一个假设使得\(h(\pmb{x}_i) = \sigma_i (i=1,2,\cdots,m)\)，此时可计算上式值为1。

考虑实值函数空间\(\mathscr{F}:\mathscr{Z} \to \mathbf{R}\),令\(\pmb{Z} = \{\pmb{z}_1,\pmb{z}_2,\cdots,\pmb{z}_m\}\)，其中\(\pmb{z}_i \in \mathscr{Z}\)，将上式中的\(\mathscr{X}\)和\(\mathscr{H}\)替换为\(\mathscr{Z}\)和\(\mathscr{F}\)可得 定义12.8：函数空间\(\mathscr{F}\)关于\(\pmb{Z}\)的经验Rademacher复杂度 \[\hat{R}_{\pmb{Z}} (\mathscr{F}) = E_{\pmb{\sigma}} [\sup_{f \in \mathscr{F}} \frac{1}{m} \sum_{i=1}^m \sigma_i f(\pmb{z}_i)]\]

经验Rademacher复杂度衡量了函数空间\(\mathscr{F}\)与随机噪声在集合\(\pmb{Z}\)中的相关性。通常希望了解函数空间\(\mathscr{F}\)在\(\mathscr{Z}\)上关于分布\(\mathscr{D}\)的相关性，因此，对所有从\(\mathscr{D}\)独立同分布采样而得的大小为\(m\)的集合\(\pmb{Z}\)求期望可得
定义12.9：函数空间\(\mathscr{F}\)关于\(\mathscr{Z}\)上分布\(\mathscr{D}\)的Rademacher复杂度 \[R_m (\mathscr{F}) = E_{\pmb{Z} \in \mathscr{Z}:|\pmb{Z}| = m} [\hat{R}_{\pmb{Z}}(\mathscr{F})]\] 基于Rademacher复杂度可得关于函数空间\(\mathscr{F}\)的泛化误差界：
定理12.5：对实值函数空间\(\mathscr{F}:\mathscr{Z} \to [0,1]\)，根据分布\(\mathscr{D}\)从\(\mathscr{Z}\)中独立同分布采样得到样例集\(\pmb{Z} = \{\pmb{z}_1,\pmb{z}_2,\cdots,\pmb{z}_m\}, \pmb{z}_i \in \mathscr{Z}, 0 < \delta < 1\)，对任意\(f \in \mathscr{F}\)，以至少\(1 - \delta\)的概率有 \[E[f(\pmb{z})] \leqslant \frac{1}{m} \sum_{i=1}^m f(\pmb{z}_i) + 2 R_m(\mathscr{F}) + \sqrt{\frac{\ln (1/ \delta)}{2m}} \tag{12.42}\] \[E[f(\pmb{z})] \leqslant \frac{1}{m} \sum_{i=1}^m f(\pmb{z}_i) + 2 \hat{R}_{\pmb{Z}}(\mathscr{F}) + 3 \sqrt{\frac{\ln (2/ \delta)}{2m}} \tag{12.43}\]

注意：上述定理中的函数空间\(\mathscr{F}\)是区间\([0,1]\)上的实值函数，因此上述定理只适用于回归问题。对二分类问题有如下定理：

定理12.6：对假设空间\(\mathscr{H}:\mathscr{X} \to \{-1,+1\}\)，根据分布\(\mathscr{D}\)从\(\mathscr{X}\)中独立同分布采样得到样例集\(D = \{\pmb{x}_1,\pmb{x}_2,\cdots,\pmb{x}_m\}, \pmb{x}_i \in \mathscr{X}, 0 < \delta < 1\)，对任意\(h \in \mathscr{H}\)，以至少\(1 - \delta\)的概率有 \[ E(h) \leqslant \hat{E}(h) + R_m(\mathscr{H}) + \sqrt{\frac{\ln (1 / \delta)}{2m}} \tag{12.47}\]

\[E(h) \leqslant \hat{E}(h) + \hat{R}_D (\mathscr{H}) + 3 \sqrt{\frac{\ln(2 / \delta)}{2m}} \tag{12.48}\]

定理12.6给出了基于Rademacher复杂度的泛化误差界，其更依赖于具体学习问题上的数据分布，有点类似于为该学习问题”量身定制“的，因此它通常比基于VC维的泛化误差界更紧一些。

关于Rademacher复杂度与增长函数，有如下定理：
定理12.7：假设空间\(\mathscr{H}\)的Rademacher复杂度\(R_m(\mathscr{H})\)与增长函数\(\Pi_{\mathscr{H}} (m)\)满足 \[R_m(\mathscr{H}) \leqslant \sqrt{\frac{2 \ln \Pi_{\mathscr{H}} (m)}{m}}\]

由式（12.47）和上式还有推论12.2可得 \[E(h) \leqslant \hat{E}(h) + \sqrt{\frac{2d \ln (\frac{em}{d})}{m}} + \sqrt{\frac{\ln(1/ \delta)}{2m}}\] 也就是说，从Rademacher复杂度和增长函数能推导出基于VC维的泛化误差界。

6. 稳定性

无论是基于VC维还是Rademacher复杂度来推导泛化误差界，所得到的结果均与具体学习算法无关，对所有学习算法都适用，能够脱离具体学习算法的设计来考虑学习问题本身的性质。但是若希望获得与算法有关的分析结果，则需要进行稳定性（stability）分析。
稳定性考察的是算法在输入发生变化时，输出是否会随之发生较大的变化。
学习算法的输入是训练集，先定义训练集的两种变化：
给定\(D = \{\pmb{z}_1 = (\pmb{x}_1,y_1),\pmb{z}_2 = (\pmb{x}_2,y_2),\cdots, \pmb{z}_m = (\pmb{x}_m,y_m)\}\)，\(\pmb{x}_i \in \mathscr{X}\)是来自分布\(\mathscr{D}\)的独立同分布样例，\(y_i \in \{-1,+1\}\)。对假设空间\(\mathscr{H}: \mathscr{X} \to \{-1,+1\}\)和学习算法\(\mathscr{L}\)，令\(\mathscr{L}_D \in \mathscr{H}\)表示基于训练集\(D\)从假设空间\(\mathscr{H}\)中学得的假设。考虑\(D\)的以下变化：

\(D^{\backslash i}\)表示移除\(D\)中第\(i\)个样例得到的集合：\(D^{\backslash i} = \{\pmb{z}_1,\pmb{z}_2,\cdots, \pmb{z}_{i-1}, \pmb{z}_{i+1}, \cdots, \pmb{z}_m\}\)；
\(D^i\)表示替换\(D\)中第\(i\)个样例得到的集合：\(D^i = \{\pmb{z}_1,\pmb{z}_2,\cdots, \pmb{z}_{i-1}, \pmb{z}_i', \pmb{z}_{i+1}, \cdots, \pmb{z}_m\}\)，其中\(\pmb{z}_i' = (\pmb{x}_i',y_i')\)服从分布\(\mathscr{D}\)并独立于\(D\)。

损失函数\(\mathscr{l}(\mathscr{L}_D(\pmb{x}),y):\mathscr{Y} \times \mathscr{Y} \to \mathbf{R}^+\)刻画了假设\(\mathscr{L}_D\)的预测标记\(\mathscr{L}_D(\pmb{x})\)与真实标记\(y\)之间的差别，简记为\(\mathscr{l} (\mathscr{L}_D, \pmb{z})\)，关于假设\(\mathscr{L}_D\)的几种损失如下：

泛化损失：\(\mathscr{l} (\mathscr{L},\mathscr{D}) = E_{\pmb{x} \in \mathscr{X},\pmb{z} = (\pmb{x},y)}[\mathscr{l} (\mathscr{L}_D,\pmb{z})]\)
经验损失：\(\hat{\mathscr{l}} (\mathscr{L},D) = \frac{1}{m} \sum_{i=1}^m \mathscr{l} (\mathscr{L}_D, \pmb{z}_i)\)
留一损失：\(\mathscr{l}_{loo} (\mathscr{L}, D) = \frac{1}{m} \sum_{i=1}^m \mathscr{l} (\mathscr{L}_{D^{\backslash i}}, \pmb{z}_i)\)

定义12.10：对任何\(\pmb{x} \in \mathscr{X}, \pmb{z} = (\pmb{x},y)\)，若学习算法\(\mathscr{L}\)满足 \[|\mathscr{l} (\mathscr{L}_D, \pmb{z}) - \mathscr{l}(\mathscr{L}_{D^{\backslash i}}, \pmb{z})| \leqslant \beta , \quad i=1,2,\cdots,m\] 则称\(\mathscr{L}\)关于损失函数\(\mathscr{l}\)满足\(\beta\)-均匀稳定性。

若算法\(\mathscr{L}\)关于损失函数\(\mathscr{l}\)满足\(\beta\)-均匀稳定性，则有 \[\begin{align} & \quad |\mathscr{l}(\mathscr{L}_D, \pmb{z}) - \mathscr{l}(\mathscr{L}_{D^i},\pmb{z})| \nonumber \\ & \leqslant |\mathscr{l}(\mathscr{L}_D, \pmb{z}) - \mathscr{l}(\mathscr{L}_{D^{\backslash i}},\pmb{z})| + |\mathscr{l}(\mathscr{L}_{D^i}, \pmb{z}) - \mathscr{l}(\mathscr{L}_{D^{\backslash i}},\pmb{z})| \nonumber \\ & \leqslant 2 \beta \nonumber \end{align}\]

移除样例的稳定性包含了替换样例的稳定性。

若损失函数\(\mathscr{l}\)有界，即对所有\(D\)和\(\pmb{z} = (\pmb{x},y)\)有\(0 \leqslant \mathscr{l} (\mathscr{L}_D, \pmb{z}) \leqslant M\)，则有：
定理12.8：给定从分布\(\mathscr{D}\)上独立同分布采样得到的大小为\(m\)的样例集\(D\)，弱学习算法\(\mathscr{L}\)满足关于损失函数\(\mathscr{l}\)的\(\beta\)-均匀稳定性，且损失函数\(\mathscr{l}\)的上界为\(M\)，\(0 < \delta < 1\)，则对任意\(m \geqslant 1\)，以至少\(1 - \delta\)的概率有 \[\mathscr{l} (\mathscr{L}, \mathscr{D}) \leqslant \hat{\mathscr{l}}(\mathscr{L},D) + 2 \beta + (4m \beta + M) \sqrt{\frac{\ln(1 / \delta)}{2m}} \tag{12.58}\] \[\mathscr{l} (\mathscr{L}, \mathscr{D}) \leqslant \mathscr{l}_{loo} (\mathscr{L},D) + \beta + (4m \beta + M) \sqrt{\frac{\ln(1 / \delta)}{2m}} \tag{12.59}\]

定理12.8给出了基于稳定性分析推导出的学习算法\(\mathscr{L}\)学得假设的泛化误差界。从式（12.58）可看出，经验损失与泛化损失之间差别的收敛率为\(\beta \sqrt{m}\)；若\(\beta = O(\frac{1}{m})\)，则可保证收敛率为\(O(\frac{1}{\sqrt{m}})\)，这与基于VC维和Rademacher复杂度得到的收敛度一致。

注意：学习算法的稳定性分析所关注的是\(|\hat{\mathscr{l}}(\mathscr{L},D) - \mathscr{l}(\mathscr{L}, \mathscr{D})|\)，而假设空间复杂度分析所关注的是\(\sup_{h \in \mathscr{H}}|\hat{E}(h) - E(h)|\)；也就是说，稳定性分析不必考虑假设空间中所有可能的假设，只需根据算法自身的特性（稳定性）来讨论输出假设\(\mathscr{L}_D\)的泛化误差界。
必须假设\(\beta \sqrt{m} \to 0\)才能保证稳定的学习算法\(\mathscr{L}\)具有一定的泛化能力，即经验损失收敛与泛化损失。为便于计算，假设\(\beta = \frac{1}{m}\)，带入式（12.58）可得 \[\mathscr{l} (\mathscr{L}, \mathscr{D}) \leqslant \hat{\mathscr{l}}(\mathscr{L},D) + \frac{2}{m} + (4 + M) \sqrt{\frac{\ln(1 / \delta)}{2m}}\] 对损失函数\(\mathscr{l}\)，若学习算法\(\mathscr{L}\)所输出的假设满足经验损失最小化，则称算法\(\mathscr{L}\)满足经验风险最小化原则，简称算法是ERM的。

关于学习算法的稳定性和可学习性，有如下定理：
定理12.9：若学习算法\(\mathscr{L}\)是ERM且稳定的，则假设空间\(\mathscr{H}\)可学习。