chapter12.md 56 KB
第12章 计算学习理论
正如本章开篇所述，计算学习理论研究目的是分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计。例如，"西瓜书"定理12.1、定理12.3、定理12.6所表达意思的共同点是，泛化误差与经验误差之差的绝对值以很大概率($1-\delta$)很小，且这个差的绝对值随着训练样本个数($m$)的增加而减小，随着模型复杂度（定理12.1为假设空间包含的假设个数$\vert\mathcal{H}\vert$，定理12.3中为假设空间的VC维，定理12.6中为(经验)Rademacher复杂度）的减小而减小。因此，若想要得到一个泛化误差很小的模型，足够的训练样本是前提，最小化经验误差是实现途径，另外还要选择性能相同的模型中模型复杂度最低的那一个；"最小化经验误差"即常说的经验风险最小化，"选择模型复杂度最低的那一个"即结构风险最小化，可以参见"西瓜书"6.4节最后一段的描述，尤其是式(6.42)所表达的含义。
12.1 基础知识
统计学中有总体集合和样本集合之分, 比如要统计国内本科生对机器学习的掌握情况, 此时全国所有的本科生就是总体集合, 但总体集合往往太大而不具有实际可操作性, 一般都 是取总体集合的一部分, 比如从双一流 $\mathrm{A}$ 类、双一流 $\mathrm{B}$ 类、一流学科建设高校、普通高校 中各找一部分学生 (即样本集合)进行调研, 以此来了解国内本科生对机器学习的掌握情况。 在机器学习中, 样本空间 (参见 $1.2$ 节) 对应总体集合, 而我们手头上的样例集 $D$ 对应 样本集合, 样例集 $D$ 是从样本空间中采样而得, 分布 $\mathcal{D}$ 可理解为当从样本空间采样获得样例 集 $D$ 时每个样本被采到的概率, 我们用 $\mathcal{D}(t)$ 表示样本空间第 $t$ 个样本被采到的概率。
12.1.1 式(12.1)的解释
该式为泛化误差的定义式，所谓泛化误差，是指当样本$x$从真实的样本分布$\mathcal{D}$中采样后其预测值$h(\boldsymbol{x})$不等于真实值$y$的概率。在现实世界中，我们很难获得样本分布$\mathcal{D}$，我们拿到的数据集可以看做是从样本分布$\mathcal{D}$中独立同分布采样得到的。在西瓜书中，我们拿到的数据集，称为样例集$D$[也叫观测集、样本集，注意与花体$\mathcal{D}$的区别]。
12.1.2 式(12.2)的解释
该式为经验误差的定义式，所谓经验误差，是指观测集$D$中的样本$x_i, i=1,2,\cdots,m$的预测值$h(\boldsymbol{x}_i)$和真实值$y_i$的期望误差。
12.1.3 式(12.3)的解释
假设我们有两个模型$h_1$和$h_2$，将它们同时作用于样本$\boldsymbol{x}$上，那么他们的"不合"度定义为这两个模型预测值不相同的概率。
12.1.4 式(12.4)的解释
Jensen不等式：这个式子可以做很直观的理解，比如说在二维空间上，凸函数可以想象成开口向上的抛物线，假如我们有两个点$x_1, x_2$，那么$f(\mathbb{E}(x))$表示的是两个点的均值的纵坐标，而$\mathbb{E}(f(x))$表示的是两个点纵坐标的均值，因为两个点的均值落在抛物线的凹处，所以均值的纵坐标会小一些。
12.1.5 式(12.5)的解释
随机变量的观测值是随机的, 进一步地, 随机过程的每个时刻都是一个随机变量。
式中, $\frac{1}{m} \sum_{i=1}^m xi$ 表示 $m$ 个独立随机变量各自的某次观测值的平均, $\frac{1}{m} \sum{i=1}^m \mathbb{E}\left(x_i\right)$ 表示 $m$ 个独立随机变量各自的期望的平均。
式(12.5)表示事件 $\frac{1}{m} \sum_{i=1}^m xi-\frac{1}{m} \sum{i=1}^m \mathbb{E}\left(xi\right) \geqslant \epsilon$ 出现的概率不大于 (i.e., $\left.\leqslant\right) e^{-2 m \epsilon^2}$; 式(12.6)的事件 $\left|\frac{1}{m} \sum{i=1}^m xi-\frac{1}{m} \sum{i=1}^m \mathbb{E}\left(x_i\right)\right| \geqslant \epsilon$ 等价于以下事件:
$$ \frac{1}{m} \sum_{i=1}^m xi-\frac{1}{m} \sum{i=1}^m \mathbb{E}\left(xi\right) \geqslant \epsilon \quad \vee \quad \frac{1}{m} \sum{i=1}^m xi-\frac{1}{m} \sum{i=1}^m \mathbb{E}\left(x_i\right) \leqslant-\epsilon $$
其中, $\vee$ 表示逻辑或 (以上其实就是将绝对值表达式拆成两部分而已)。这两个子事件并无 交集, 因此总概率等于两个子事件概率之和; 而 $\frac{1}{m} \sum_{i=1}^m xi-\frac{1}{m} \sum{i=1}^m \mathbb{E}\left(x_i\right) \leqslant-\epsilon$ 与式(12.5) 表达的事情对称, 因此概率相同。
Hoeffding 不等式表达的意思是 $\frac{1}{m} \sum_{i=1}^m xi$ 和 $\frac{1}{m} \sum{i=1}^m \mathbb{E}\left(x_i\right)$ 两个值应该比较接近, 二者 之差大于 $\epsilon$ 的概率很小 (不大于 $2 e^{-2 m \epsilon^2}$ )。
如果对Hoeffding不等式的证明感兴趣，可以参考Hoeffding在1963年发表的论文[1]，这篇文章也被引用了逾万次。
12.1.6 式(12.7)的解释
McDiarmid不等式：首先解释下前提条件：
$$ \sup {x{1}, \ldots, x{m}, x{i}^{\prime}}\left|f\left(x{1}, \ldots, x{m}\right)-f\left(x{1}, \ldots, x{i-1}, x{i}^{\prime}, x{i+1}, \ldots, x{m}\right)\right| \leqslant c{i} $$
表示当函数$f$某个输入$x_i$变到$x_i^\prime$的时候，其变化的上确$\sup$仍满足不大于$c_i$。所谓上确界sup可以理解成变化的极限最大值，可能取到也可能无穷逼近。当满足这个条件时，McDiarmid不等式指出：函数值$f(x_1,\dots,x_m)$和其期望值$\mathbb{E}\left(f(x_1,\dots,xm)\right)$也相近，从概率的角度描述是：它们之间差值不小于$\epsilon$这样的事件出现的概率不大于$\exp \left(\frac{-2 \epsilon^{2}}{\sum{i} c_{i}^{2}}\right)$，可以看出当每次变量改动带来函数值改动的上限越小，函数值和其期望越相近。
12.2 PAC学习
本节内容几乎都是概念, 建议多读几遍，仔细琢磨一下。
概率近似正确(Probably Approximately Correct, PAC)学习, 可以读为 [pæk]学习。
本节第 2 段讨论的目标概念, 可简单理解为真实的映射函数;
本节第 3 段讨论的假设空间, 可简单理解为学习算法不同参数时的存在, 例如线性分类 超平面 $f(\boldsymbol{x})=\boldsymbol{w}^{\top} \boldsymbol{x}+b$, 每一组 $(\boldsymbol{w}, b)$ 取值就是一个假设;
本节第 4 段讨论的可分的(separable)和不可分的(non-separable), 例如西瓜书第 100 页的 图 5.4, 若假设空间是线性分类器, 则(a)(b)(c)是可分的, 而(d)是不可分的; 当然, 若假设空 间为椭圆分类器 (分类边界为椭圆), 则(d)也是可分的;
本节第 5 段提到的 "等效的假设"指的是第 7 页图 $1.3$ 中的 $\mathrm{A}$ 和 $\mathrm{B}$ 两条曲线都可以完 美拟合有限的样本点, 故称之为 "等效" 的假设; 另外本段最后还给出了概率近似正确的 含义, 即 "以较大概率学得误差满足预设上限的模型"。
定义 12.1 PAC 辨识的式(12.9)表示输出假设 $h$ 的泛化误差 $E(h) \leqslant \epsilon$ 的概率不小于 $1-\delta$; 即 "学习算法 $\mathfrak{L}$ 能以较大概率 (至少 $1-\delta$ ) 学得目标概念 $c$ 的近似 (误差最多为 $\epsilon$ )"。
定义 12.2 PAC 可学习的核心在于, 需要的样本数目 $m$ 是 $1 / \epsilon, 1 / \delta, \operatorname{size}(\boldsymbol{x}), \operatorname{size}(\mathrm{c})$ 的多 项式函数。
定义 12.3 PAC 学习算法的核心在于, 完成 PAC 学习所需要的时间是 $1 / \epsilon, 1 / \delta, \operatorname{size}(\boldsymbol{x})$, $\operatorname{size}(\mathrm{c})$ 的多项式函数。
定义 12.4 样本复杂度指完成 PAC 学习过程需要的最少的样本数量, 而在实际中当然也 希望用最少的样本数量完成学习过程。
在定义 12.4 之后, 抛出来三个问题:
研究某任务在什么样的条件下可学得较好的模型？（定义 12.2）
某算法在什么样的条件下可进行有效的学习?（定义 12.3）
需多少训练样例才能获得较好的模型？（定义 12.4）
有限假设空间指 $\mathcal{H}$ 中包含的假设个数是有限的, 反之则为无限假设空间; 无限假设空间 更为常见, 例如能够将图 5.4(a)(b)(c)中的正例和反例样本分开的线性超平面个数是无限多的。
12.2.1 式(12.9)的解释
PAC辨识的定义：$E(h)$表示算法$\mathcal{L}$在用观测集$D$训练后输出的假设函数$h$，它的泛化误差(见公式12.1)。这个概率定义指出，如果$h$的泛化误差不大于$\epsilon$的概率不小于$1-\delta$，那么我们称学习算法$\mathcal{L}$能从假设空间$\mathcal{H}$中PAC辨识概念类$\mathcal{C}$。
12.3 有限假设空间
本节内容分两部分, 第 1 部分 "可分情形" 时, 可以达到经验误差 $\widehat{E}(h)=0$, 做的事 情是以 $1-\delta$ 概率学得目标概念的 $\epsilon$ 近似, 即式(12.12); 第 2 部分 "不可分情形" 时, 无法达 到经验误差 $\widehat{E}(h)=0$, 做的事情是以 $1-\delta$ 概率学得 $\min _{h \in \mathcal{H}} E(h)$ 的 $\epsilon$ 近似, 即式(12.20)。无 论哪种情形, 对于 $h \in \mathcal{H}$, 可以得到该假设的泛化误差 $E(h)$ 与经验误差 $\widehat{E}(h)$ 的关系, 即 "当 样例数目 $m$ 较大时, $h$ 的经验误差是泛化误差很好的近似", 即式(12.18); 实际研究中经常需 要推导类似的泛化误差上下界。
从式12.10到式12.14的公式是为了回答一个问题：到底需要多少样例才能学得目标概念$c$的有效近似。只要训练集$D$的规模能使学习算法$\mathcal{L}$以概率$1-\delta$找到目标假设的$\epsilon$近似即可。下面就是用数学公式进行抽象。
12.3.1 式(12.10)的解释
$P(h(\boldsymbol{x})=y) =1-P(h(\boldsymbol{x}) \neq y)$ 因为它们是对立事件，$P(h(x)\neq y)=E(h)$是泛化误差的定义(见12.1)，由于我们假定了泛化误差$E(h)>\epsilon$，因此有$1-E(h)<1-\epsilon$。
12.3.2 式(12.11)的解释
先解释什么是$h$与$D$"表现一致"，12.2节开头阐述了这样的概念，如果$h$能将$D$中所有样本按与真实标记一致的方式完全分开，我们称问题对学习算法是一致的。即$\left(h\left(\boldsymbol{x}{1}\right)=y{1}\right) \wedge \ldots \wedge\left(h\left(\boldsymbol{x}{m}\right)=y{m}\right)$为True。因为每个事件是独立的，所以上式可以写成$P\left(\left(h\left(\boldsymbol{x}{1}\right)=y{1}\right) \wedge \ldots \wedge\left(h\left(\boldsymbol{x}{m}\right)=y{m}\right)\right)=\prod{i=1}^{m} P\left(h\left(\boldsymbol{x}{i}\right)=y{i}\right)$。根据对立事件的定义有：$\prod{i=1}^{m} P\left(h\left(\boldsymbol{x}{i}\right)=y{i}\right)=\prod{i=1}^{m}\left(1-P\left(h\left(\boldsymbol{x}{i}\right) \neq y_{i}\right)\right)$，又根据公式(12.10)，有
$$ \prod{i=1}^{m}\left(1-P\left(h\left(\boldsymbol{x}{i}\right) \neq y{i}\right)\right)<\prod{i=1}^{m}(1-\epsilon)=(1-\epsilon)^{m} $$
12.3.3 式(12.12)的推导
首先解释为什么"我们事先并不知道学习算法$\mathcal{L}$会输出$\mathcal{H}$中的哪个假设"，因为一些学习算法对用一个观察集$D$的输出结果是非确定的，比如感知机就是个典型的例子，训练样本的顺序也会影响感知机学习到的假设$h$参数的值。泛化误差大于$\epsilon$且经验误差为0的假设(即在训练集上表现完美的假设)出现的概率可以表示为$P(h \in \mathcal{H}: E(h)>\epsilon \wedge \widehat{E}(h)=0)$，根据式12.11，每一个这样的假设$h$都满足$P(E(h)>\epsilon \wedge \widehat{E}(h)=0)<\left(1-\epsilon \right)^m$，假设一共有$\vert\mathcal{H}\vert$这么多个这样的假设$h$，因为每个假设$h$满足$E(h)>\epsilon$且$\widehat{E}(h)=0$是互斥的，因此总的概率$P(h \in \mathcal{H}: E(h)>\epsilon \wedge \widehat{E}(h)=0)$就是这些互斥事件之和，即
$$ \begin{aligned}P\left(h \in \mathcal{H}: E(h)>\epsilon \wedge \widehat{E}(h)=0\right) &=\sum_i^{\mathcal{\vert H\vert}}P\left(E(h_i)>\epsilon \wedge \widehat{E}(h_i)=0\right)\&<|\mathcal{H}|(1-\epsilon)^{m}\end{aligned} $$
小于号依据公式(12.11)。
第二个小于号实际上是要证明$\vert\mathcal{H}\vert(1-\epsilon)^m < \vert\mathcal{H}\vert e^{-m\epsilon}$，即证明$(1-\epsilon)^m < e^{-m\epsilon}$，其中$\epsilon\in(0,1]$，$m$是正整数，推导如下：
当$\epsilon=1$时，显然成立，当$\epsilon\in(0, 1)$时，因为左式和右式的值域均大于0，所以可以左右两边同时取对数，又因为对数函数是单调递增函数，所以即证明$m\ln(1-\epsilon) < -m\epsilon$，即证明$\ln(1-\epsilon)<-\epsilon$，这个式子很容易证明：令$f(\epsilon)=\ln(1-\epsilon) + \epsilon$，其中$\epsilon\in(0,1)$，$f^\prime(\epsilon)=1-\frac{1}{1-\epsilon}=0 \Rightarrow \epsilon=0$ 取极大值0，因此$ln(1-\epsilon)<-\epsilon$ 也即$\vert\mathcal{H}\vert(1-\epsilon)^m < \vert\mathcal{H}\vert e^{-m\epsilon}$成立。
12.3.4 式(12.13)的解释
回到我们要回答的问题：到底需要多少样例才能学得目标概念$c$的有效近似。只要训练集$D$的规模能使学习算法$\mathcal{L}$以概率$1-\delta$找到目标假设的$\epsilon$近似即可。根据式12.12，学习算法$\mathcal{L}$生成的假设大于目标假设的$\epsilon$近似的概率为$P\left(h \in \mathcal{H}: E(h)>\epsilon \wedge \widehat{E}(h)=0\right)<\vert\mathcal{H}\vert e^{-m\epsilon}$，因此学习算法$\mathcal{L}$生成的假设落在目标假设的$\epsilon$近似的概率为$1-P\left(h \in \mathcal{H}: E(h)>\epsilon \wedge \widehat{E}(h)=0\right)\ge 1-\vert\mathcal{H}\vert e^{-m\epsilon}$，这个概率我们希望 至少是$1-\delta$，因此$1-\delta\leqslant 1-\vert\mathcal{H}\vert e^{-m\epsilon}\Rightarrow\vert\mathcal{H}\vert e^{-m\epsilon}\leqslant\delta$
12.3.5 式(12.14)的推导
$$ \begin{aligned} \vert\mathcal{H}\vert e^{-m \epsilon} &\leqslant \delta\ e^{-m \epsilon} &\leqslant \frac{\delta}{\vert\mathcal{H}\vert}\ -m \epsilon &\leqslant \ln\delta-\ln\vert\mathcal{H}\vert\ m &\geqslant \frac{1}{\epsilon}\left(\ln |\mathcal{H}|+\ln \frac{1}{\delta}\right) \end{aligned} $$
这个式子告诉我们，在假设空间$\mathcal{H}$是PAC可学习的情况下，输出假设$h$的泛化误差$\epsilon$随样本数目$m$增大而收敛到0，收敛速率为$O(\frac{1}{m})$。这也是我们在机器学习中的一个共识，即可供模型训练的观测集样本数量越多，机器学习模型的泛化性能越好。
12.3.6 引理12.1的解释
根据式(12.2), $\widehat{E}(h)=\frac{1}{m} \sum_{i=1}^m \mathbb{I}\left(h\left(\boldsymbol{x}_i\right) \neq y_i\right)$, 而指示函数 $\mathbb{I}(\cdot)$ 取值非 0 即 1 , 也就是 说 $0 \leq \mathbb{I}\left(h\left(\boldsymbol{x}_i\right) \neq y_i\right) \leq 1$; 对于式(12.1) 的 $E(h)$ 实际上表示 $\mathbb{I}\left(h\left(\boldsymbol{x}_i\right) \neq y_i\right)$ 为 1 的期望 $\mathbb{E}\left(\mathbb{I}\left(h\left(\boldsymbol{x}_i\right) \neq yi\right)\right)$ (泛化误差表示样本空间中任取一个样本, 其预测类别不等于真实类别的 概率), 当假设 $h$ 确定时, 泛化误差固定不变, 因此可记为 $E(h)=\frac{1}{m} \sum{i=1}^m \mathbb{E}\left(\mathbb{I}\left(h\left(\boldsymbol{x}_i\right) \neq y_i\right)\right)$ 。
此时, 将 $\widehat{E}(h)$ 和 $E(h)$ 代入式(12.15)到式(12.17), 对比式(12.5)和式(12.6)的 Hoeffding 不等式可知, 式(12.15)对应式(12.5), 式(12.16)与式(12.15)对称, 式(12.17)对应式(12.6)。
12.3.7 式(12.18)的推导
令$\delta=2e^{-2m\epsilon^2}$，则$\epsilon=\sqrt{\frac{\ln(2/\delta)}{2m}}$，由式(12.17)
$$ \begin{aligned} P(|E(h)-\widehat{E}(h)| \geqslant \epsilon) &\leqslant 2 \exp \left(-2 m \epsilon^{2}\right)\ P(|E(h)-\widehat{E}(h)| \geqslant \epsilon) &\leqslant \delta\ P(|E(h)-\widehat{E}(h)| \leqslant \epsilon) &\geqslant 1 - \delta\ P(-\epsilon \leqslant E(h)-\widehat{E}(h) \leqslant \epsilon) &\geqslant 1 - \delta\ P(\widehat{E}(h) -\epsilon \leqslant E(h) \leqslant \widehat{E}(h)+\epsilon) &\geqslant 1 - \delta\ \end{aligned} $$
带入 $\epsilon=\sqrt{\frac{\ln(2/\delta)}{2m}}$得证。
这个式子进一步阐明了当观测集样本数量足够大的时候，$h$的经验误差是其泛化误差很好的近似。
12.3.8 式(12.19)的推导
令$h_1,h2,\dots,h{\vert\mathcal{H}\vert}$表示假设空间$\mathcal{H}$中的假设，有
$$ \begin{aligned} & P(\exists h \in \mathcal{H}:|E(h)-\widehat{E}(h)|>\epsilon) \ =& P\left(\left(\left|E{h{1}}-\widehat{E}{h{1}}\right|>\epsilon\right) \vee \ldots \vee\left(| E{h{|\mathcal{H}|}}-\widehat{E}{h{|\mathcal{H}|} |>\epsilon}\right)\right) \ \leqslant & \sum_{h \in \mathcal{H}} P(|E(h)-\widehat{E}(h)|>\epsilon) \end{aligned} $$
这一步是很好理解的，存在一个假设$h$使得$|E(h)-\widehat{E}(h)|>\epsilon$的概率可以表示为对假设空间内所有的假设$hi, i\in 1,\dots,\vert\mathcal{H}\vert$，使得$\left|E{h{i}}-\widehat{E}{h_{i}}\right|>\epsilon$这个事件成立的\"或\"事件。因为$P(A\vee B)=P(A) + P(B) - P(A\wedge B)$，而$P(A\wedge B)\geqslant 0$，所以最后一行的不等式成立。
由式12.17：
$$ \begin{aligned} &P(|E(h)-\widehat{E}(h)| \geqslant \epsilon) \leqslant 2 \exp \left(-2 m \epsilon^{2}\right)\ &\Rightarrow \sum_{h \in \mathcal{H}} P(|E(h)-\widehat{E}(h)|>\epsilon) \leqslant 2|\mathcal{H}| \exp \left(-2 m \epsilon^{2}\right) \end{aligned} $$
因此：
$$ \begin{aligned} P(\exists h \in \mathcal{H}:|E(h)-\widehat{E}(h)|>\epsilon) &\leqslant \sum_{h \in \mathcal{H}} P(|E(h)-\widehat{E}(h)|>\epsilon)\ &\leqslant 2|\mathcal{H}| \exp \left(-2 m \epsilon^{2}\right) \end{aligned} $$
其对立事件：
$$ \begin{aligned} P(\forall h\in\mathcal{H}:\vert E(h)-\widehat{E}(h)\vert\leqslant\epsilon)&=1-P(\exists h \in \mathcal{H}:|E(h)-\widehat{E}(h)|>\epsilon)\ &\geqslant 1- 2|\mathcal{H}| \exp \left(-2 m \epsilon^{2}\right) \end{aligned} $$
令$\delta=2\vert\mathcal{H}\vert e^{-2m\epsilon^2}$，则$\epsilon=\sqrt{\frac{\ln |\mathcal{H}|+\ln (2 / \delta)}{2 m}}$，带入上式中即可得到
$$ P\left(\forall h\in\mathcal{H}:\vert E(h)-\widehat{E}(h)\vert\leqslant\sqrt{\frac{\ln |\mathcal{H}|+\ln (2 / \delta)}{2 m}}\right)\geqslant 1- \delta $$
其中$\forall h\in\mathcal{H}$这个前置条件可以省略。
12.3.9 式(12.20)的解释
这个式子是"不可知PAC可学习"的定义式，不可知是指当目标概念$c$不在算法$\mathcal{L}$所能生成的假设空间$\mathcal{H}$里。可学习是指如果$\mathcal{H}$中泛化误差最小的假设是$\arg\min_{h\in \mathcal{H}}E(h)$，且这个假设的泛化误差满足其与目标概念的泛化误差的差值不大于$\epsilon$的概率不小于$1-\delta$。我们称这样的假设空间$\mathcal{H}$是不可知PAC可学习的。
12.4 VC维
不同于12.3节的有限假设空间，从本节开始，本章剩余内容均针对无限假设空间。
12.4.1 式(12.21)的解释
这个是增长函数的定义式。增长函数$\Pi_{\mathcal{H}}(m)$表示假设空间$\mathcal{H}$对m个样本所能赋予标签的最大可能的结果数。比如对于两个样本的二分类问题，一共有4中可能的标签组合$[[0, 0], [0, 1], [1, 0], [1, 1]]$，如果假设空间$\mathcal{H}1$能赋予这两个样本两种标签组合$[[0, 0], [1, 1]]$，则$\Pi{\mathcal{H}_1}(2)=2$。显然，$\mathcal{H}$对样本所能赋予标签的可能结果数越多，$\mathcal{H}$的表示能力就越强。增长函数可以用来反映假设空间$\mathcal{H}$的复杂度。
12.4.2 式(12.22)的解释
值得指出的是，这个式子的前提假设有误，应当写成对假设空间$\mathcal{H}$，$m\in\mathbb{N}$，$0<\epsilon<1$，存在$h\in\mathcal{H}$ 详细证明参见原论文 On the uniform convergence of relative frequencies of events to their probabilities [2]，在该论文中，定理的形式如下：
Theorem 2 The probability that the relative frequency of at least one event in class $S$ differs from its probability in an experiment of size l by more then $\varepsilon$, for $l \geqq 2 / \varepsilon^2$, satisfies the inequality
$$ \mathbf{P}\left(\pi^{(l)}>\varepsilon\right) \leqq 4 m^S(2 l) e^{-\varepsilon^2 l / 8} . $$
注意定理描述中使用的是"at least one event in class S", 因此应该是 class S 中"存在"one event 而不是 class S 中的 "任意" event。
另外, 该定理为基于增长函数对无限假设空间的泛化误差分析, 与上一节有限假设空间 的定理 12.1。在证明定理 $12.1$ 的式(12.19)过程中, 实际证明的结论是
$$ P(\exists h \in \mathcal{H}:|E(h)-\widehat{E}(h)|>\epsilon) \leqslant 2|\mathcal{H}| e^{-2 m \epsilon^2} $$
根据该结论可得式(12.19)的原型（式(12.19)就是将 $\epsilon$ 用 $\delta$ 表示):
$$ P(\forall h \in \mathcal{H}:|E(h)-\widehat{E}(h)| \leqslant \epsilon) \leqslant 1-2|\mathcal{H}| e^{-2 m \epsilon^2} $$
这是因为事件 $\exists h \in \mathcal{H}:|E(h)-\widehat{E}(h)|>\epsilon$ 与事件 $\forall h \in \mathcal{H}:|E(h)-\widehat{E}(h)| \leqslant \epsilon$ 为对立事件。
注意到当使用 $|E(h)-\widehat{E}(h)|>\epsilon$ 表达时对应于 "存在", 当使用 $|E(h)-\widehat{E}(h)| \leqslant \epsilon$ 表达时 则对应于 "任意"。
综上所述, 式(12.22)使用 $|E(h)-\widehat{E}(h)|>\epsilon$, 所以这里应该对应于 "存在"。
12.4.3 式(12.23)的解释
这是VC维的定义式：VC维的定义是能被$\mathcal{H}$打散的最大示例集的大小。"西瓜书"中例12.1和例12.2 给出了形象的例子。
式(12.23)中的 $\left{m: \Pi{\mathcal{H}}(m)=2^m\right}$ 表示一个集合, 集合的元素是能使 $\Pi{\mathcal{H}}(m)=2^m$ 成立 的所有 $m$; 最外层的 max表示取集合的最大值。注意, 这里仅讨论二分类问题。注意，VC维的定义式上的底数2表示这个问题是2分类的问题。如果是$n$分类的问题，那么定义式中底数需要变为$n$。
$\mathrm{VC}$ 维的概念还是很容易理解的, 有个常见的思维误区西瓜书也指出来了, 即 "这并不 意味着所有大小为 $d$ 的示例集都能被假设空间 $\mathcal{H}$ 打散", 也就是说只要 "存在大小为 $d$ 的示例 集能被假设空间 H打散" 即可, 这里的区别与前面 "定理 $12.2$ 的解释" 中提到的 "任意" 与 "存在" 的关系一样。
12.4.4 引理12.2的解释
首先解释下数学归纳法的起始条件\"当$m=1, d=0$或$d=1$时，定理成立\"，当$m=1,d=0$时，由VC维的定义(式12.23) $\mathrm{VC}(\mathcal{H})=\max \left{m: \Pi{\mathcal{H}}(m)=2^{m}\right}=0$ 可知$\Pi{\mathcal{H}}(1)<2$，否则$d$可以取到1，又因为$\Pi{\mathcal{H}}(m)$为整数，所以$\Pi{\mathcal{H}}(1)\in[0, 1]$，式12.24右边为$\sum{i=0}^{0}\left(\begin{array}{c}{1} \ {i}\end{array}\right)=1$，因此不等式成立。当$m=1,d=1$时，因为一个样本最多只能有两个类别，所以$\Pi\mathcal{H}(1)=2$，不等式右边为$\sum_{i=0}^{1}\left(\begin{array}{c}{1} \ {i}\end{array}\right)=2$，因此不等式成立。
再介绍归纳过程，这里采样的归纳方法是假设式(12.24)对$(m-1, d-1)$和$(m-1, d)$成立，推导出其对$(m,d)$也成立。证明过程中引入观测集$D=\left{\boldsymbol{x}{1}, \boldsymbol{x}{2}, \ldots, \boldsymbol{x}{m}\right}$ 和观测集$D^\prime=\left{\boldsymbol{x}{1}, \boldsymbol{x}{2}, \ldots, \boldsymbol{x}{m-1}\right}$，其中$D$比$D^\prime$多一个样本$x_m$，它们对应的假设空间可以表示为：
$$ \begin{array}{l}{\mathcal{H}{| D}=\left{\left(h\left(\boldsymbol{x}{1}\right), h\left(\boldsymbol{x}{2}\right), \ldots, h\left(\boldsymbol{x}{m}\right)\right) | h \in \mathcal{H}\right}} \ {\mathcal{H}{| D^{\prime}}=\left{\left(h\left(\boldsymbol{x}{1}\right), h\left(\boldsymbol{x}{2}\right), \ldots, h\left(\boldsymbol{x}{m-1}\right)\right) | h \in \mathcal{H}\right}}\end{array} $$
如果假设$h\in\mathcal{H}$对$xm$的分类结果为$+1$，或为$-1$，那么任何出现在$\mathcal{H}{\vert D^\prime}$中的串都会在$\mathcal{H}_{\vert D}$中出现一次或者两次。这里举个例子就很容易理解了，假设$m=3$：
$$ \begin{aligned} \mathcal{H}{\vert D}&={(+,-,-),(+,+,-),(+,+,+),(-,+,-),(-,-,+)}\ \mathcal{H}{\vert D^\prime}&={(+,+),(+,-),(-,+),(-,-)}\ \end{aligned} $$
其中串$(+,+)$在$\mathcal{H}{\vert D}$中出现了两次$(+, +, +), (+, +, -)$，$\mathcal{H}{\vert D^\prime}$中得其他串$(+,-), (-, +), (-, -)$均只在$\mathcal{H}_{\vert D}$中出现了一次。这里的原因是每个样本是二分类的，所以多出的样本$x_m$要么取$+$，要么取$-$，要么都取到(至少两个假设$h$对$xm$做出了不一致的判断)。 记号$\mathcal{H}{D^\prime\vert D}$表示在$\mathcal{H}{\vert D}$中出现了两次的$\mathcal{H}{\vert D^\prime}$组成的集合，比如在上例中$\mathcal{H}_{D^\prime\vert D}={(+,+)}$，有
$$ \left|\mathcal{H}{| D}\right|=\left|\mathcal{H}{| D^{\prime}}\right|+\left|\mathcal{H}_{D^{\prime} | D}\right| $$
由于$\mathcal{H}{\vert D^\prime}$表示限制在样本集$D^\prime$上的假设空间$\mathcal{H}$的表达能力(即所有假设对样本集$D^\prime$所能赋予的标记种类数)，样本集$D^\prime$的数目为$m-1$，根据增长函数的定义，假设空间$\mathcal{H}$对包含$m-1$个样本的集合所能赋予的最大标记种类数为$\Pi{\mathcal{H}}(m-1)$，因此$\vert\mathcal{H}{\vert D^\prime}\vert \leqslant \Pi\mathcal{H}(m-1)$。又根据数学归纳法的前提假设，有：
$$ \left|\mathcal{H}{| D^{\prime}}\right| \leqslant \Pi{\mathcal{H}}(m-1) \leqslant \sum_{i=0}^{d}\left(\begin{array}{c}{m-1} \ {i}\end{array}\right) $$
由记号$\mathcal{H}{\vert D^\prime}$的定义可知，$\vert\mathcal{H}{\vert D^\prime}\vert \geqslant \left\lfloor\frac{\vert\mathcal{H}{\vert D}\vert}{2}\right\rfloor$，又由于$\vert\mathcal{H}{\vert D^\prime}\vert$和$\vert\mathcal{H}{D^\prime\vert D}\vert$均为整数，因此$\vert\mathcal{H}{D^\prime\vert D}\vert \leqslant \left\lfloor\frac{\vert\mathcal{H}{\vert D}\vert}{2}\right\rfloor$，由于样本集$D$的大小为$m$，根据增长函数的概念，有$\left|\mathcal{H}{D^{\prime}| D}\right| \leqslant \left\lfloor\frac{\vert\mathcal{H}{\vert D}\vert}{2}\right\rfloor\leqslant \Pi{\mathcal{H}}(m-1)$。 假设$Q$表示能被$\mathcal{H}{D^\prime\vert D}$打散的集合，因为根据$\mathcal{H}{D^\prime\vert D}$的定义，$H_{D}$必对元素$xm$给定了不一致的判定，因此$Q \cup\left{\boldsymbol{x}{m}\right}$必能被$\mathcal{H}{\vert D}$打散，由前提假设$\mathcal{H}$的VC维为$d$，因此$\mathcal{H}{D^\prime\vert D}$的VC维最大为$d-1$，综上有
$$ \left|\mathcal{H}{D^{\prime}| D}\right| \leqslant \Pi{\mathcal{H}}(m-1) \leqslant \sum_{i=0}^{d-1}\left(\begin{array}{c}{m-1} \ {i}\end{array}\right) $$
因此：
$$ \begin{aligned} \left|\mathcal{H}{| D}\right|&=\left|\mathcal{H}{| D^{\prime}}\right|+\left|\mathcal{H}{D^{\prime} | D}\right|\ &\leqslant \sum{i=0}^{d}\left(\begin{array}{c}{m-1} \ {i}\end{array}\right) + \sum{i=0}^{d+1}\left(\begin{array}{c}{m-1} \ {i}\end{array}\right)\ &=\sum{i=0}^d \left(\left(\begin{array}{c}{m-1} \ {i}\end{array}\right) + \left(\begin{array}{c}{m-1} \ {i-1}\end{array}\right)\right)\ &=\sum_{i=0}^{d}\left(\begin{array}{c}{m} \ {i}\end{array}\right) \end{aligned} $$
注：最后一步依据组合公式，推导如下：
$$ \begin{aligned}\left(\begin{array}{c}{m-1} \ {i}\end{array}\right)+\left(\begin{array}{c}{m-1} \ {i-1}\end{array}\right) &=\frac{(m-1) !}{(m-1-i) ! i !}+\frac{(m-1) !}{(m-1-i+1) !(i-1) !} \ &=\frac{(m-1) !(m-i)}{(m-i)(m-1-i) ! i !}+\frac{(m-1) ! i}{(m-i) !(i-1) ! i} \ &=\frac{(m-1) !(m-i)+(m-1) ! i}{(m-i) ! i !} \ &=\frac{(m-1) !(m-i+i)}{(m-i) ! i !}=\frac{(m-1) ! m}{(m-i) ! i !} \ &=\frac{m !}{(m-i) ! i !}=\left(\begin{array}{c}{m} \ {i}\end{array}\right) \end{aligned} $$
12.4.5 式(12.28)的解释
$$ \begin{aligned} \Pi{\mathcal{H}}(m) & \leqslant \sum{i=0}^{d}\left(\begin{array}{c}{m} \ {i}\end{array}\right) \ & \leqslant \sum{i=0}^{d}\left(\begin{array}{c}{m} \ {i}\end{array}\right)\left(\frac{m}{d}\right)^{d-i} \ &=\left(\frac{m}{d}\right)^{d} \sum{i=0}^{d}\left(\begin{array}{c}{m} \ {i}\end{array}\right)\left(\frac{d}{m}\right)^{i} \ & \leqslant\left(\frac{m}{d}\right)^{d} \sum_{i=0}^{m}\left(\begin{array}{c}{m} \ {i}\end{array}\right)\left(\frac{d}{m}\right)^{i} \ &={\left(\frac{m}{d}\right)}^d{\left(1+\frac{d}{m}\right)}^m\ &<\left(\frac{e \cdot m}{d}\right)^{d} \end{aligned} $$
第一步到第二步和第三步到第四步均因为$m\geqslant d$，第四步到第五步是由于二项式定理[3]：$(x+y)^{n}=\sum{k=0}^{n}\left(\begin{array}{l}{n} \ {k}\end{array}\right) x^{n-k} y^{k}$，其中令$k=i, n=m, x=1, y = \frac{d}{m}$得$\left(\frac{m}{d}\right)^{d} \sum{i=0}^{m}\left(\begin{array}{c}{m} \ {i}\end{array}\right)\left(\frac{d}{m}\right)^{i}=\left(\frac{m}{d}\right)^{d} (1+\frac{d}{m})^m$，最后一步的不等式即需证明${\left(1+\frac{d}{m}\right)}^m\leqslant e^d$，因为${\left(1+\frac{d}{m}\right)}^m={\left(1+\frac{d}{m}\right)}^{\frac{m}{d}d}$，根据自然对数底数$e$的定义[4]，${\left(1+\frac{d}{m}\right)}^{\frac{m}{d}d}< e^d$，注意原文中用的是$\leqslant$，但是由于$e=\lim _{\frac{d}{m} \rightarrow 0}\left(1+\frac{d}{m}\right)^{\frac{m}{d}}$的定义是一个极限，所以应该是用$<$。
12.4.6 式(12.29)的解释
这里应该是作者的笔误，根据式12.22，$E(h)-\widehat{E}(h)$应当被绝对值符号包裹。将式12.28带入式12.22得
$$ P\left(\vert E(h)-\widehat{E}(h) \vert> \epsilon \right) \leqslant 4{\left(\frac{2em}{d}\right)}^d\exp\left(-\frac{m\epsilon^2}{8}\right) $$
令$4{\left(\frac{2em}{d}\right)}^d\exp\left(-\frac{m\epsilon^2}{8}\right)=\delta$可解得
$$ \delta=\sqrt{ \frac{8d\ln\frac{2em}{d}+8\ln\frac{4}{\delta}}{m} } $$
带入式12.22，则定理得证。这个式子是用VC维表示泛化界，可以看出，泛化误差界只与样本数量$m$有关，收敛速率为$\sqrt{\frac{\ln m}{m}}$ (书上简化为$\frac{1}{\sqrt{m}}$)。
12.4.7 式(12.30)的解释
这个是经验风险最小化的定义式。即从假设空间中找出能使经验风险最小的假设。
12.4.8 定理12.4的解释
首先回忆PAC可学习的概念，见定义12.2，而可知/不可知PAC可学习之间的区别仅仅在于概念类$c$是否包含于假设空间$\mathcal{H}$中。令
$$ \begin{aligned} \delta^\prime = \frac{\delta}{2} \ \sqrt{\frac{\left(\ln 2 / \delta^{\prime}\right)}{2 m}}=\frac{\epsilon}{2} \end{aligned} $$
结合这两个标记的转换，由推论12.1可知：
$$ \widehat{E}(g)-\frac{\epsilon}{2} \leqslant E(g) \leqslant \widehat{E}(g)+\frac{\epsilon}{2} $$
至少以$1-\delta/2$的概率成立。写成概率的形式即：
$$ P\left(|E(g)-\widehat{E}(g)| \leqslant \frac{\epsilon}{2}\right) \geqslant 1-\delta / 2 $$
即$P\left(\left(E(g)-\widehat{E}(g) \leqslant \frac{\epsilon}{2}\right) \wedge\left(E(g)-\widehat{E}(g) \geqslant-\frac{\epsilon}{2}\right)\right) \geqslant 1-\delta / 2$，因此$P\left(E(g)-\widehat{E}(g) \leqslant \frac{\epsilon}{2}\right) \geqslant 1-\delta / 2$且$P\left(E(g)-\widehat{E}(g) \geqslant -\frac{\epsilon}{2}\right) \geqslant 1-\delta / 2$成立。 再令
$$ \sqrt{\frac{8 d \ln \frac{2 e m}{d}+8 \ln \frac{4}{\delta^{\prime}}}{m}}=\frac{\epsilon}{2} $$
由式12.29可知
$$ P\left(\left\vert E(h)-\widehat{E}(h) \right\vert\leqslant \frac{\epsilon}{2} \right) \geqslant 1-\frac{\delta}{2} $$
同理，$P\left(E(h)-\widehat{E}(h) \leqslant \frac{\epsilon}{2}\right) \geqslant 1-\delta / 2$且$P\left(E(h)-\widehat{E}(h) \geqslant -\frac{\epsilon}{2}\right) \geqslant 1-\delta / 2$成立。 由$P\left(E(g)-\widehat{E}(g) \geqslant - \frac{\epsilon}{2}\right) \geqslant 1-\delta / 2$和$P\left(E(h)-\widehat{E}(h) \leqslant \frac{\epsilon}{2}\right) \geqslant 1-\delta / 2$均成立可知 则事件$E(g)-\widehat{E}(g) \geqslant -\frac{\epsilon}{2}$和事件$E(h)-\widehat{E}(h) \leqslant \frac{\epsilon}{2}$同时成立的概率为：
$$ \begin{aligned} &P\left( \left(E(g)-\widehat{E}(g) \geqslant -\frac{\epsilon}{2} \right)\wedge\left(E(h)-\widehat{E}(h) \leqslant \frac{\epsilon}{2} \right)\right) \= & P\left(E(g)-\widehat{E}(g) \geqslant -\frac{\epsilon}{2}\right) + P\left(E(h)-\widehat{E}(h) \leqslant \frac{\epsilon}{2}\right)
- P\left(\left(E(g)-\widehat{E}(g) \geqslant -\frac{\epsilon}{2} \right)\vee\left(E(h)-\widehat{E}(h) \leqslant \frac{\epsilon}{2} \right)\right) \\geqslant &1 - \delta/2 + 1 - \delta/2 - 1 \=& 1-\delta \end{aligned} $$
即
$$ P\left( \left(E(g)-\widehat{E}(g) \geqslant -\frac{\epsilon}{2} \right)\wedge\left(E(h)-\widehat{E}(h) \leqslant \frac{\epsilon}{2} \right)\right) \geqslant 1-\delta $$
因此
$$ P\left( \widehat{E}(g)-E(g)+E(h)-\widehat{E}(h)\leqslant\frac{\epsilon}{2} + \frac{\epsilon}{2} \right) = P\left(E(h)-E(g)\leqslant\widehat{E}(h)-\widehat{E}(g)+\epsilon\right) \geqslant 1 - \delta $$
再由$h$和$g$的定义，$h$表示假设空间中经验误差最小的假设，$g$表示泛化误差最小的假设，将这两个假设共用作用于样本集$D$，则一定有$\widehat{E}(h)\leqslant\widehat{E}(g)$，因此上式可以简化为：
$$ P\left(E(h)-E(g)\leqslant\epsilon\right) \geqslant 1 - \delta $$
根据式12.32和式12.34，可以求出$m$为关于$\left(1/\epsilon,1/\delta,\text{size}(x),\text{size}(c)\right)$的多项式，因此根据定理12.2，定理12.5，得到结论任何VC维有限的假设空间$\mathcal{H}$都是(不可知)PAC可学习的。
12.5 Rademacher复杂度
上一节中介绍的基于VC维的泛化误差界是分布无关、数据独立的，本节将要介绍的Rademacher复杂度则在一定程度上考虑了数据分布。
12.5.1 式(12.36)的解释
这里解释从第一步到第二步的推导，因为前提假设是2分类问题，$y_k\in{-1, +1}$，因此$\mathbb{I}\left(h(x_i)\neq y_i\right)\equiv \frac{1-y_i h(x_i)}{2}$。这是因为假如$y_i=+1, h(x_i)=+1$或$y_i=-1, h(x_i)=-1$，有$\mathbb{I}\left(h(x_i)\neq y_i\right)=0= \frac{1-y_i h(x_i)}{2}$；反之，假如$y_i=-1, h(x_i)=+1$或$y_i=+1, h(x_i)=-1$，有$\mathbb{I}\left(h(x_i)\neq y_i\right)=1= \frac{1-y_i h(x_i)}{2}$。
12.5.2 式(12.37)的解释
由公式12.36可知，经验误差$\widehat{E}(h)$和$\frac{1}{m} \sum{i=1}^{m} y{i} h\left(\boldsymbol{x}{i}\right)$呈反比的关系，因此假设空间中能使经验误差最小的假设$h$即是使$\frac{1}{m} \sum{i=1}^{m} y{i} h\left(\boldsymbol{x}{i}\right)$最大的$h$。
12.5.3 式(12.38)的解释
上确界$\sup$这个概念前面已经解释过，见式(12.7)的解析。相比于式(12.37), 样例真实标记 $y_i$ 换为了 Rademacher 随机变量 $\sigma_i, \arg \max _{h \in \mathcal{H}}$ 换为了 上确界 $\sup _{h \in \mathcal{H}^{\circ}}$ 该式表示, 对于样例集 $D=\left{\boldsymbol{x}_1, \boldsymbol{x}_2, \ldots, \boldsymbol{x}_m\right}$, 假设空间 $\mathcal{H}$ 中的假设对其预 测结果 $\left{h\left(\boldsymbol{x}_1\right), h\left(\boldsymbol{x}_2\right), \ldots, h\left(\boldsymbol{x}_m\right)\right}$ 与随机变量集合 $\boldsymbol{\sigma}=\left{\sigma_1, \sigma_2, \ldots, \sigmam\right}$ 的契合程度。接下 来解释一下该式的含义。 $\frac{1}{m} \sum{i=1}^m \sigma_i h\left(\boldsymbol{x}_i\right)$ 中的 $\boldsymbol{\sigma}=\left{\sigma_1, \sigma_2, \ldots, \sigma_m\right}$ 表示单次随机生成的结果（生成后就固定不 动 ), 而 $\left{h\left(\boldsymbol{x}_1\right), h\left(\boldsymbol{x}_2\right), \ldots, h\left(\boldsymbol{x}m\right)\right}$ 表示某个假设 $h \in \mathcal{H}$ 的预测结果, 至于 $\frac{1}{m} \sum{i=1}^m \sigma_i h\left(\boldsymbol{x}_i\right)$ 的 取值则取决于本次随机生成的 $\sigma$ 和假设 $h$ 的预测结果的契合程度。
进一步地, $\sup {h \in \mathcal{H}} \frac{1}{m} \sum{i=1}^m \sigma_i h\left(\boldsymbol{x}_i\right)$ 中的 $\boldsymbol{\sigma}=\left{\sigma_1, \sigma_2, \ldots, \sigma_m\right}$ 仍表示单次随机生成的结 果 (生成后就固定不动), 但此时需求解的是假设空间 $\mathcal{H}$ 中所有假设与 $\sigma$ 最契合的那个 $h$ 。
例如, $\boldsymbol{\sigma}={-1,+1,-1,+1}$ （即 $m=4$, 这里 $\boldsymbol{\sigma}$ 仅为本次随机生成结果而已, 下次生 成结果可能是另一组结果), 假设空间 $\mathcal{H}=\left{h_1, h_2, h_3\right}$, 其中
$$ \begin{aligned} & \left{h_1\left(\boldsymbol{x}_1\right), h_1\left(\boldsymbol{x}_2\right), h_1\left(\boldsymbol{x}_3\right), h_1\left(\boldsymbol{x}_4\right)\right}={-1,-1,-1,-1} \ & \left{h_2\left(\boldsymbol{x}_1\right), h_2\left(\boldsymbol{x}_2\right), h_2\left(\boldsymbol{x}_3\right), h_2\left(\boldsymbol{x}_4\right)\right}={-1,+1,-1,-1} \ & \left{h_3\left(\boldsymbol{x}_1\right), h_3\left(\boldsymbol{x}_2\right), h_3\left(\boldsymbol{x}_3\right), h_3\left(\boldsymbol{x}_4\right)\right}={+1,+1,+1,+1} \end{aligned} $$
易知 $\frac{1}{m} \sum_{i=1}^m \sigma_i h_1\left(\boldsymbol{x}i\right)=0, \frac{1}{m} \sum{i=1}^m \sigma_i h_2\left(\boldsymbol{x}i\right)=\frac{2}{4}, \frac{1}{m} \sum{i=1}^m \sigma_i h_3\left(\boldsymbol{x}_i\right)=0$, 因此
$$ \sup {h \in \mathcal{H}} \frac{1}{m} \sum{i=1}^m \sigma_i h\left(\boldsymbol{x}_i\right)=\frac{2}{4} $$
12.5.4 式(12.39)的解释
$$ \mathbb{E}_{\boldsymbol{\sigma}}\left[\sup {h \in \mathcal{H}} \frac{1}{m} \sum{i=1}^{m} \sigma{i} h\left(\boldsymbol{x}{i}\right)\right] $$
[解析]：这个式子可以用来衡量假设空间$\mathcal{H}$的表达能力，对变量$\sigma$求期望可以理解为当变量$\sigma$包含所有可能的结果时，假设空间$\mathcal{H}$中最契合的假设$h$和变量的平均契合程度。因为前提假设是2分类的问题，因此$\sigma_i$一共有$2^m$种，这些不同的$\sigma_i$构成了数据集$D={(x_1, y_1), (x_2, y_2),\dots, (x_m, y_m)}$的"对分"(12.4节)，如果一个假设空间的表达能力越强，那么就越有可能对于每一种$\sigma_i$，假设空间中都存在一个$h$使得$h(x_i)$和$\sigma_i$非常接近甚至相同，对所有可能的$\sigma_i$取期望即可衡量假设空间的整体表达能力，这就是这个式子的含义。
12.5.5 式(12.40)的解释
对比式12.39，这里使用函数空间$\mathcal{F}$代替了假设空间$\mathcal{H}$，函数$f$代替了假设$h$，很容易理解，因为假设$h$即可以看做是作用在数据$x_i$上的一个映射，通过这个映射可以得到标签$y_i$。注意前提假设实值函数空间$\mathcal{F}:\mathcal{Z}\rightarrow\mathbb{R}$，即映射$f$将样本$z_i$映射到了实数空间，这个时候所有的$\sigma_i$将是一个标量即$\sigma_i\in{+1, -1}$。
12.5.6 式(12.41)的解释
这里所要求的是$\mathcal{F}$关于分布$\mathcal{D}$的Rademacher复杂度，因此从$\mathcal{D}$中采出不同的样本$Z$，计算这些样本对应的Rademacher复杂度的期望。
12.5.7 定理12.5的解释
首先令记号
$$ \begin{aligned} \widehat{E}{Z}(f) &=\frac{1}{m} \sum{i=1}^{m} f\left(\boldsymbol{z}_{i}\right) \ \Phi(Z) &=\sup {f \in \mathcal{F}} \left(\mathbb{E}[f]-\widehat{E}{Z}(f)\right) \end{aligned} $$
即$\widehat{E}_{Z}(f)$表示函数$f$作为假设下的经验误差，$\Phi(Z)$表示泛化误差和经验误差的差的上确界。再令$Z^\prime$为只与$Z$有一个示例(样本)不同的训练集，不妨设$z_m\in Z$和$z^\prime_m\in Z^\prime$为不同的示例，那么有
$$ \begin{aligned} \Phi\left(Z^{\prime}\right)-\Phi(Z) &=\sup {f \in \mathcal{F}} \left(\mathbb{E}[f]-\widehat{E}{Z^{\prime}}(f)\right)-\sup {f \in \mathcal{F}} \left(\mathbb{E}[f]-\widehat{E}{Z}(f)\right) \ & \leqslant \sup {f \in \mathcal{F}} \left(\widehat{E}{Z}(f)-\widehat{E}{Z^{\prime}}(f)\right) \ &=\sup{f\in\mathcal{F}}\frac{\sum^m_{i=1}f(zi)-\sum^m{i=1}f(z^\prime_i)}{m}\&=\sup {f \in \mathcal{F}} \frac{f\left(z{m}\right)-f\left(z_{m}^{\prime}\right)}{m} \ & \leqslant \frac{1}{m} \end{aligned} $$
第一个不等式是因为上确界的差不大于差的上确界[5]，第四行的等号由于$Z^\prime$与$Z$只有$z_m$不相同，最后一行的不等式是因为前提假设$\mathcal{F}:\mathcal{Z}\rightarrow [0,1]$，即$f(z_m),f(z_m^\prime)\in[0,1]$。 同理
$$ \Phi(Z)-\Phi\left(Z^{\prime}\right) =\sup {f \in \mathcal{F}} \frac{f\left(z{m}^\prime\right)-f\left(z_{m}\right)}{m} \leqslant \frac{1}{m} $$
综上二式有：
$$ \left\vert \Phi(Z)-\Phi\left(Z^{\prime}\right)\right\vert \leqslant \frac{1}{m} $$
将$\Phi$看做函数$f$(注意这里的$f$不是$\Phi$定义里的$f$)，那么可以套用McDiarmid不等式的结论式12.7
$$ P\left(\Phi(Z)-\mathbb{E}{Z}[\Phi(Z)] \geqslant \epsilon\right) \leqslant \exp \left(\frac{-2 \epsilon^{2}}{\sum{i} c_{i}^{2}}\right) $$
令$\exp \left(\frac{-2 \epsilon^{2}}{\sum{i} c{i}^{2}}\right)=\delta$可以求得$\epsilon=\sqrt{\frac{\ln (1 / \delta)}{2 m}}$，所以
$$ P\left(\Phi(Z)-\mathbb{E}_{Z}[\Phi(Z)] \geqslant \sqrt{\frac{\ln (1 / \delta)}{2 m}}\right) \leqslant \delta $$
由逆事件的概率定义得
$$ P\left(\Phi(Z)-\mathbb{E}_{Z}[\Phi(Z)] \leqslant \sqrt{\frac{\ln (1 / \delta)}{2 m}}\right) \geqslant 1-\delta $$
即书中式12.44的结论。下面来估计$\mathbb{E}_{Z}[\Phi(Z)]$的上界：
$$ \begin{aligned} \mathbb{E}{Z}[\Phi(Z)] &=\mathbb{E}{Z}\left[\sup {f \in \mathcal{F}} \left(\mathbb{E}[f]-\widehat{E}{Z}(f)\right)\right] \ &=\mathbb{E}_{Z}\left[\sup {f \in \mathcal{F}} \mathbb{E}{Z^{\prime}}\left[\widehat{E}{Z^{\prime}}(f)-\widehat{E}{Z}(f)\right]\right] \ & \leqslant \mathbb{E}_{Z, Z^{\prime}}\left[\sup {f \in \mathcal{F}}\left( \widehat{E}{Z^{\prime}}(f)-\widehat{E}{Z}(f)\right)\right] \ &=\mathbb{E}{Z, Z^{\prime}}\left[\sup {f \in \mathcal{F}} \frac{1}{m} \sum{i=1}^{m}\left(f\left(\boldsymbol{z}{i}^{\prime}\right)-f\left(\boldsymbol{z}{i}\right)\right)\right] \ &=\mathbb{E}_{\boldsymbol{\sigma}, Z,Z^{\prime}}\left[\sup {f \in \mathcal{F}} \frac{1}{m} \sum{i=1}^{m} \sigma{i}\left(f\left(\boldsymbol{z}{i}^{\prime}\right)-f\left(\boldsymbol{z}{i}\right)\right)\right] \ &\leqslant \mathbb{E}{\boldsymbol{\sigma}, Z^{\prime}}\left[\sup {f \in \mathcal{F}} \frac{1}{m} \sum{i=1}^{m} \sigma{i} f\left(\boldsymbol{z}{i}^{\prime}\right)\right]+\mathbb{E}_{\boldsymbol{\sigma}, Z}\left[\sup {f \in \mathcal{F}} \frac{1}{m} \sum{i=1}^{m}-\sigma{i} f\left(\boldsymbol{z}{i}\right)\right] \ &=2 \mathbb{E}_{\boldsymbol{\sigma}, Z}\left[\sup {f \in \mathcal{F}} \frac{1}{m} \sum{i=1}^{m} \sigma{i} f\left(\boldsymbol{z}{i}\right)\right] \ &=2 R_{m}(\mathcal{F}) \end{aligned} $$
第二行等式是外面套了一个对服从分布$\mathcal{D}$的示例集$Z^\prime$求期望，因为$\mathbb{E}{Z^\prime\sim\mathcal{D}}[\widehat{E}{Z^\prime}(f)]=\mathbb{E}(f)$，而采样出来的$Z^\prime$和$Z$相互独立，因此有$\mathbb{E}{Z^\prime\sim\mathcal{D}}[\widehat{E}{Z}(f)]=\widehat{E}_{Z}(f)$。
第三行不等式基于上确界函数$\sup$是个凸函数，将$\sup{f\in\mathcal{F}}$看做是凸函数$f$，将$\widehat{E}{Z^{\prime}}(f)-\widehat{E}{Z}(f)$看做变量$x$根据Jesen不等式(式12.4)，有$\mathbb{E}{Z}\left[\sup {f \in \mathcal{F}} \mathbb{E}{Z^{\prime}}\left[\widehat{E}{Z^{\prime}}(f)-\widehat{E}{Z}(f)\right]\right] \leqslant \mathbb{E}_{Z, Z^{\prime}}\left[\sup {f \in \mathcal{F}}\left( \widehat{E}{Z^{\prime}}(f)-\widehat{E}{Z}(f)\right)\right]$，其中$\mathbb{E}{Z, Z^{\prime}}[\cdot]$是$\mathbb{E}{Z}[\mathbb{E}{Z^\prime}[\cdot]]$的简写形式。
第五行引入对Rademacher随机变量的期望，由于函数值空间是标量，因为$\sigma_i$也是标量，即$\sigma_i\in{-1, +1}$，且$\sigmai$总以相同概率可以取到这两个值，因此可以引入$\mathbb{E}{\sigma}$而不影响最终结果。
第六行利用了上确界的和不小于和的上确界[5]，因为第一项中只含有变量$z^\prime$，所以可以将$\mathbb{E}Z$去掉，因为第二项中只含有变量$z$，所以可以将$\mathbb{E}{Z^\prime}$去掉。
第七行利用$\sigma$是对称的，所以$-\sigma$的分布和$\sigma$完全一致，所以可以将第二项中的负号去除，又因为$Z$和$Z^\prime$均是从$\mathcal{D}$中$i.i.d.$采样得到的数据，因此可以将第一项中的$z^\prime_i$替换成$z$，将$Z^\prime$替换成$Z$。
最后根据定义式12.41可得$\mathbb{E}_{Z}[\Phi(Z)]=2\mathcal{R}_m(\mathcal{F})$，式(12.42)得证。
12.6 定理12.6的解释
针对二分类问题, 定理 $12.5$ 给出了 "泛化误差" 和 "经验误差" 的关系, 即:
式(12.47)基于 Rademacher 复杂度 $R_m(\mathcal{H})$ 给出了泛化误差 $E(h)$ 的上界;
式(12.48)基于经验 Rademacher 复杂度 $\widehat{R}_D(\mathcal{H})$ 给出了泛化误差 $E(h)$ 的上界。
可能大家都会有疑问：定理12.6的设定其实也适用于定理12.5, 即值域为二 值的 ${-1,+1}$ 也属于值域为连续值的 $[0,1]$ 的一种特殊情况, 这一点从接下来的式(12.49)的 转换可以看出。那么, 为什么还要针对二分类问题专门给出定理12.6呢?
根据(经验)Rademacher 复杂度的定义可以知道, $R_m(\mathcal{H})$ 和 $\widehat{R}_D(\mathcal{H})$ 均大于零 (参见前面 有关式(12.39)的解释, 书中式(12.39)下面的一行也提到该式取值范围是 $[0,1])$; 因此, 相比 于定理12.5来说, 定理12.6的上界更紧, 因为二者的界只有中间一项关于(经验)Rademacher 复杂度的部分不同, 在定理12.5中是两倍的(经验)Rademacher 复杂度, 而在定理 12.6中是 一倍的(经验)Rademacher 复杂度, 而(经验)Rademacher 复杂度大于零。
因此, 为二分类问题量身定制的定理12.6相比于通用的定理12.5来说, 二者的区别在 于定理12.6考虑了二分类的特殊情况, 得到了比定理12.5更紧的泛化误差界, 仅此而已。
下面做一些证明：
(1)首先通过式(12.49)将值域为 ${-1,+1}$ 的假设空间 $\mathcal{H}$ 转化为值域为 $[0,1]$ 的函数空间 $\mathcal{F}_{\mathcal{H}}$ ;
(2)接下来是该证明最核心部分, 即证明式(12.50)的结论 $\widehat{R}Z\left(\mathcal{F}{\mathcal{H}}\right)=\frac{1}{2} \widehat{R}_D(\mathcal{H})$ : 第 1 行等号就是定义 $12.8$; 第 2 行等号就是根据式(12.49)将 $f_h\left(\boldsymbol{x}_i, y_i\right)$ 换为 $\mathbb{I}\left(h\left(\boldsymbol{x}_i\right) \neq y_i\right)$; 第 3 行等号类似于式(12.36)的第 2 个等号; 第 4 行等号说明如下:
$$ \sup {h \in \mathcal{H}} \frac{1}{m} \sum{i=1}^m \sigma_i \frac{1-y_i h\left(\boldsymbol{x}_i\right)}{2}=\sup {h \in \mathcal{H}} \frac{1}{2 m} \sum{i=1}^m \sigma_i+\sup {h \in \mathcal{H}} \frac{1}{2 m} \sum{i=1}^m \frac{-y_i \sigma_i h\left(\boldsymbol{x}_i\right)}{2} $$
其中 $\sup {h \in \mathcal{H}} \frac{1}{2 m} \sum{i=1}^m \sigma_i$ 与 $h$ 无关, 所以 $\sup {h \in \mathcal{H}} \frac{1}{2 m} \sum{i=1}^m \sigmai=\frac{1}{2 m} \sum{i=1}^m \sigmai$, 即第 4 行等号; 第 5 行等号是由于 $\mathbb{E}{\boldsymbol{\sigma}}\left[\frac{1}{m} \sum_{i=1}^m \sigma_i\right]=0$, 例如当 $m=2$ 时, 所有可能得 $\boldsymbol{\sigma}$ 包括 $(-1,-1)$, $(-1,+1),(+1,-1)$ 和 $(+1,+1)$, 求期望后显然结果等于 0 ; 第 6 行等号正如边注所说, " $-y_i \sigma_i$ 与 $\sigma_i$ 分布相同" (原因跟定理12.5中证明 $\mathbb{E}_Z[\Phi(Z)] \leqslant 2 R_m(\mathcal{F})$ 相同, 即求期望时要针对所 有可能的 $\sigma$ 参见"西瓜书"第 282 页第 8 行); 第 7 行等号再次使用了定义12.8。
(3)关于式(12.51), 根据式(12.50)的结论, 可证明如下:
$$ Rm\left(\mathcal{F}{\mathcal{H}}\right)=\mathbb{E}_Z\left[\widehat{R}Z\left(\mathcal{F}{\mathcal{H}}\right)\right]=\mathbb{E}_D\left[\frac{1}{2} \widehat{R}_D(\mathcal{H})\right]=\frac{1}{2} \mathbb{E}_D\left[\widehat{R}_D(\mathcal{H})\right]=\frac{1}{2} R_m(\mathcal{H}) $$
其中第 2 个等号由 $Z$ 变为 $D$ 只是符号根据具体情况的适时变化而已。
(4)最后, 将式(12.49)定义的 $f_h$ 替换定理 $12.5$ 中的函数 $f$, 则
$$ \begin{gathered} \mathbb{E}[f(\boldsymbol{z})]=\mathbb{E}[\mathbb{I}(h(\boldsymbol{x}) \neq y)]=E(h) \ \frac{1}{m} \sum_{i=1}^m f\left(\boldsymbol{z}i\right)=\frac{1}{m} \sum{i=1}^m \mathbb{I}\left(h\left(\boldsymbol{x}_i\right) \neq y_i\right)=\widehat{E}(h) \end{gathered} $$
将式(12.51)代入式(12.42), 即用 $\frac{1}{2} R_m(\mathcal{H})$ 替换式(12.42)的 $R_m(\mathcal{F})$, 式(12.47)得证;
将式(12.50)代入式(12.43), 即用 $\frac{1}{2} \widehat{R}_D(\mathcal{H})$ 替换式(12.43)的 $\widehat{R}_Z(\mathcal{F})$, 式(12.48)得证。
这里有个疑问在于，定理 $12.5$ 的前提是 "实值函数空间 $\mathcal{F}: \mathcal{Z} \rightarrow[0,1]$ ", 而式(12.49) 得到的函数 $f_h(z)$ 的值域实际为 ${0,1}$, 仍是离散的而非实值的; 当然, 定理 $12.5$ 的证明也 只需要其函数值在 $[0,1]$ 范围内即可, 并不需要其连续。
12.6.1 式(12.52)的证明
比较繁琐，同书上所示，参见Foundations of Machine Learning[6]
12.6.2 式(12.53)的推导
根据式12.28有$\Pi{\mathcal{H}}(m) \leqslant\left(\frac{e \cdot m}{d}\right)^{d}$，根据式12.52有$R{m}(\mathcal{H}) \leqslant \sqrt{\frac{2 \ln \Pi{\mathcal{H}}(m)}{m}}$，因此$\Pi{\mathcal{H}}(m) \leqslant \sqrt{\frac{2 d \ln \frac{e m}{d}}{m}}$，再根据式12.47 $E(h) \leqslant \widehat{E}(h)+R_{m}(\mathcal{H})+\sqrt{\frac{\ln (1 / \delta)}{2 m}}$ 即证。
12.7 稳定性
上上节中介绍的基于VC维的泛化误差界是分布无关、数据独立的，上一节介绍的Rademacher复杂度则在一定程度上考虑了数据分布，但二者得到的结果均与具体学习算法无关；本节将要介绍的稳定性分析可以获得与算法有关的分析结果。算法的"稳定性"考察的是算法在输入发生变化时，输出是否会随之发生较大的变化。
12.7.1 泛化/经验/留一损失的解释
根据式(12.54)上方关于损失函数的描述："刻画了假设 的预测标记 与真实标记 之间的差别"，这里针对的是二分类，预测标记和真实标记均只能取 和 两个值，它们之间的"差别"又能是什么呢？
因此，当"差别"取为 时，式(12.54)的泛化损失就是式(12.1)的泛化误差，式(12.55)的经验损失就是式(12.2)的经验误差，如果类似于式(12.1)和式(12.2)继续定义留一误差，那么式(12.56)就对应于留一误差。
12.7.2 式(12.57)的解释
根据三角不等式[7]，有$|a+b| \leq|a|+|b|$，将$a=\ell\left(\mathfrak{L}{D}, \boldsymbol{z}\right)-\ell\left(\mathfrak{L}{D^{i}}\right)$，$b=\ell\left(\mathfrak{L}{D^{i}, \boldsymbol{z}}\right)-\ell\left(\mathfrak{L}{D^{\backslash i}, \boldsymbol{z}}\right)$带入即可得出第一个不等式，根据$D^{\backslash i}$表示移除$D$中第$i$个样本，$D^i$表示替换$D$中第$i$个样本，那么$a,b$的变动均为一个样本，根据式12.57，$a\leqslant\beta, b\leqslant\beta$，因此$a +b \leqslant 2\beta$。
12.7.3 定理12.8的解释
西瓜书在该定理下方已明确给出该定理的意义, 即 "定理 $12.8$ 给出了基于稳定性分析 推导出的学习算法 $\mathfrak{L}$ 学得假设的泛化误差界", 式(12.58)和式(12.59)分别基于经验损失和留 一损失给出了泛化损失的上界。接下来讨论两个相关问题:
（1）定理 $12.8$ 的条件包括损失函数有界, 即 $0 \leqslant \ell\left(\mathfrak{L}_D, \boldsymbol{z}\right) \leqslant M$; 如本节第 1 条注解 "泛 化/经验/留一损失的解释" 中所述, 若 "差别" 取为 $\mathbb{I}\left(\mathfrak{L}_D(\boldsymbol{x}), y\right)$, 则泛化损失对应于泛化误 差, 此时上限 $M=1$ 。
（2）在前面泛化误差上界的推导中（例如定理 12.1、定理 12.3、定理 12.6、定理 12.7), 上界中与样本数 $m$ 有关的项收玫率均为 $O(1 / \sqrt{m})$, 但在该定理中却是 $O(\beta \sqrt{m})$; 一般来讲, 随着样本数 $m$ 的增加, 经验误差/损失应该收玫于泛化误差/损失, 因此这里假设 $\beta=1 / m$ (书 中式(12.59)下方第 3 行写为 $\beta=O(1 / m)$ ), 而在第 2 条注解 "定义 $12.10$ 的解释" 中已经提 到 $\beta$ 的取值的确会随着样本数 $m$ 的增多会变小, 虽然书中并没有严格去讨论 $\beta$ 随 $m$ 增多的变 化规律, 但至少直觉上是对的。
12.7.4 式(12.60)的推导
将$\beta=\frac{1}{m}$带入至式(12.58)即得证。
12.7.5 经验损失最小化
顾名思义, "经验损失最小化" 指通过最小化经验损失来求得假设函数。
这里, "对于损失函数 $\ell$, 若学习算法 $\mathfrak{L}$ 所输出的假设满足经验损失最小化, 则称算法 $\mathfrak{L}$ 满足经验风险最小化原则, 简称算法是 ERM 的"。 在"西瓜书"第 278 页, 若学习算法 $\mathfrak{L}$ 输出的假设 $h$ 满足式(12.30), 则也称 $\mathfrak{L}$ 为满足经验风险最小 化原则的算法。而很明显, 式(12.30)是在最小化经验误差。
那么最小化经验误差和最小化经验损失有什么区别么?
在\"西瓜书"第 286 页左下角边注中提到, "最小化经验误差和最小化经验损失有时并不相同, 这 是由于存在某些病态的损失函数 $\ell$ 使得最小化经验损失并不是最小化经验误差"。
对于 "误差"、"损失"、"风险" 等概念的辨析，参见"西瓜书"第 2 章 $2.1$ 节的注解。
12.7.6 定理(12.9)的证明的解释
首先明确几个概念，ERM表示算法$\mathcal{L}$满足经验风险最小化(Empirical Risk Minimization)。由于$\mathcal{L}$满足经验误差最小化，则可令$g$表示假设空间中具有最小泛化损失的假设，即
$$ \ell(g, \mathcal{D})=\min _{h \in \mathcal{H}} \ell(h, \mathcal{D}) $$
再令
$$ \begin{array}{l}{\epsilon^{\prime}=\frac{\epsilon}{2}} \ {\frac{\delta}{2}=2 \exp \left(-2 m\left(\epsilon^{\prime}\right)^{2}\right)}\end{array} $$
将$\epsilon^\prime=\frac{\epsilon}{2}$带入到${\frac{\delta}{2}=2 \exp \left(-2 m\left(\epsilon^{\prime}\right)^{2}\right)}$可以解得$m=\frac{2}{\epsilon^{2}} \ln \frac{4}{\delta}$，由Hoeffding不等式12.6，
$$ P\left(\left\vert\frac{1}{m} \sum{i=1}^{m} x{i}-\frac{1}{m} \sum{i=1}^{m} \mathbb{E}\left(x{i}\right)\right\vert \geqslant \epsilon\right) \leqslant 2 \exp \left(-2 m \epsilon^{2}\right) $$
其中$\frac{1}{m} \sum{i=1}^{m} \mathbb{E}\left(x{i}\right)=\ell(g, \mathcal{D})$，$\frac{1}{m} \sum{i=1}^{m} x{i}=\widehat{\ell}(g, \mathcal{D})$，带入可得
$$ P(|\ell(g, \mathcal{D})-\widehat{\ell}(g, D)| \geqslant \frac{\epsilon}{2})\leqslant \frac{\delta}{2} $$
根据逆事件的概率可得
$$ P(|\ell(g, \mathcal{D})-\widehat{\ell}(g, D)| \leqslant \frac{\epsilon}{2})\geqslant 1- \frac{\delta}{2} $$
即文中$|\ell(g, \mathcal{D})-\widehat{\ell}(g, D)| \leqslant \frac{\epsilon}{2}$至少以$1-\delta/2$的概率成立。
由$\frac{2}{m}+(4+M) \sqrt{\frac{\ln (2 / \delta)}{2 m}}=\frac{\epsilon}{2}$可以求解出
$$ \sqrt{m}=\frac{(4+M) \sqrt{\frac{\ln (2 / \delta)}{2}}+\sqrt{(4+M)^{2} \frac{\ln (2 / \delta)}{2}-4 \times \frac{\epsilon}{2} \times(-2)}}{2 \times \frac{\epsilon}{2}} $$
即$m=O\left(\frac{1}{\epsilon^{2}} \ln \frac{1}{\delta}\right)$。
由$P(|\ell(g, \mathcal{D})-\widehat{\ell}(g, D)| \leqslant \frac{\epsilon}{2})\geqslant 1- \frac{\delta}{2}$可以按照同公式12.31中介绍的相同的方法推导出
$$ P(\ell(\mathfrak{L}, \mathcal{D})-\ell(g, \mathcal{D})\leqslant\epsilon)\geqslant 1-\delta $$
又因为$m$为与$\left(1/\epsilon,1/\delta,\text{size}(x),\text{size}(c)\right)$相关的多项式的值，因此根据定理12.2，定理12.5，得到结论$\mathcal{H}$是(不可知)PAC可学习的。
参考文献
[1] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American statistical association, 58(301):13–30, 1963.
[2] Vladimir N Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of complexity, pages 11–30. Springer, 2015.
[3] Wikipedia contributors. Binomial theorem, 2020.
[4] Wikipedia contributors. E, 2020.
[5] robjohn. Supremum of the difference of two functions, 2013.
[6] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. 2018.
[7] Wikipedia contributors. Triangle inequality, 2020.