第4章：泛化界
Edit: 赵志民，李一飞，王茂霖，詹好
本章前言
在机器学习中，泛化能力是衡量模型性能的核心标准之一。如何从有限的训练数据中获得能够在未见数据上表现良好的模型，始终是研究者关注的重要问题。本章将深入探讨与泛化界相关的理论基础和定理，通过对关键概念的补充说明和定理的详细推导，帮助读者更好地理解泛化误差的收敛性质以及不同假设空间下的泛化能力。本章还将介绍与泛化界密切相关的Rademacher复杂度及其在实际应用中的意义，为进一步的研究提供理论支持。
4.1 【概念解释】可分情形中的“等效”假设
61页 中的「可分情形」部分提到了“等效假设”的概念。这其实是我们在面对模型选择时需要处理的问题。机器学习的任务实际上是从样本空间或属性空间中选择一个最符合实际的模型假设。在理想状态下，我们希望能排除不可能的情况，直接选择唯一可能的模型。然而，这是不现实的，因为训练数据无法覆盖所有可能的情况，这些数据仅是部分经验片段的记录。因此，机器学习成为了一个不适定问题（ill-posed problem）。
通常而言，不适定问题是指不满足以下任一条件的问题：
存在解 ：对于给定的问题，至少存在一个解，即这个问题是可以解决的。唯一解 ：对于给定的问题，解是唯一的，没有其他可能的解。解连续依赖于定解条件 ：解会随着初始条件或参数的变化而连续变化，不会出现突然跳跃或不连续的情况
在这里，由于我们无法仅依靠输入数据找到唯一解，这使得学习问题成为一个不适定问题，主要违反了条件2。而在更多时候，我们说机器学习是不适定的，主要是指其违反了条件3，在那种情况下，我们通常会用正则化等方式来解决。
4.2 【概念解释】定理4.1与定理2.1、定理2.2的关系
61页 中的定理4.1 与定理2.1 和定理2.2 之间存在密切联系。
定理2.1 指出一个学习算法 L \mathfrak{L} L H \mathcal{H} H C \mathcal{C} C
P ( E ( h ) ⩽ ϵ ) ⩾ 1 − δ \begin{equation}
P(\mathbb{E}(h) \leqslant \epsilon) \geqslant 1-\delta
\end{equation} P ( E ( h ) ⩽ ϵ ) ⩾ 1 − δ 其中， 0 < ϵ , δ < 1 0 \lt \epsilon, \delta \lt 1 0 < ϵ , δ < 1 c ∈ C c \in \mathcal{C} c ∈ C h ∈ H h \in \mathcal{H} h ∈ H
定理2.2 指出，所谓PAC可学，是指对于任何 m ⩾ poly ( 1 / ϵ , 1 / δ , size ( x ) , size ( c ) ) m \geqslant \operatorname{poly}(1 / \epsilon, 1 / \delta, \operatorname{size}(\boldsymbol{x}), \operatorname{size}(c)) m ⩾ poly ( 1/ ϵ , 1/ δ , size ( x ) , size ( c )) L \mathfrak{L} L H \mathcal{H} H C \mathcal{C} C
在定理4.1 中，假设学习算法 L \mathfrak{L} L H \mathcal{H} H C \mathcal{C} C m m m D D D m ⩾ 1 ϵ ( ln ∣ H ∣ + ln 1 δ ) m \geqslant \frac{1}{\epsilon} \left( \ln \left| \mathcal{H} \right| + \ln \frac{1}{\delta} \right) m ⩾ ϵ 1 ( ln ∣ H ∣ + ln δ 1 )
m ⩾ poly ( 1 / ϵ , 1 / δ , size ( x ) , size ( c ) ) \begin{equation}
m \geqslant \operatorname{poly}(1 / \epsilon, 1 / \delta, \operatorname{size}(\boldsymbol{x}), \operatorname{size}(c))
\end{equation} m ⩾ poly ( 1/ ϵ , 1/ δ , size ( x ) , size ( c )) 的条件，从而得到
P ( E ( h ) ⩽ ϵ ) ⩾ 1 − δ \begin{equation}
P(\mathbb{E}(h) \leqslant \epsilon) \geqslant 1-\delta
\end{equation} P ( E ( h ) ⩽ ϵ ) ⩾ 1 − δ 因此，定理4.1 实际上就是逆向使用了定理2.1 和定理2.2 。
4.3 【证明补充】定理4.2补充
63页 中，在证明定理4.2时，省略了从式4.6到式4.7的推导过程。在这一过程中，主要用到了28页 中式2.7的内容。
根据式4.6，有
P ( ∃ h ∈ H : ∣ E ^ ( h ) − E ( h ) ∣ > ϵ ) = P ( ( ∣ E ^ ( h 1 ) − E ( h 1 ) ∣ > ϵ ) ∨ ⋯ ∨ ( ∣ E ^ ( h ∣ H ∣ ) − E ( h ∣ H ∣ ) ∣ > ϵ ) ) ⩽ ∑ h ∈ H P ( ∣ E ^ ( h ) − E ( h ) ∣ > ϵ ) \begin{align*}
& P(\exists h \in \mathcal{H}:|\widehat{E}(h)-\mathbb{E}(h)|\gt\epsilon) \\
=& P\left(\left(\left|\widehat{E}\left(h_{1}\right)-E\left(h_{1}\right)\right|\gt\epsilon\right) \vee \cdots \vee\left(\left|\widehat{E}\left(h_{|\mathcal{H}|}\right)-E\left(h_{|\mathcal{H}|}\right)\right|\gt\epsilon\right)\right) \\
\leqslant & \sum_{h \in \mathcal{H}} P(|\widehat{E}(h)-\mathbb{E}(h)|\gt\epsilon)
\end{align*} = ⩽ P ( ∃ h ∈ H : ∣ E ( h ) − E ( h ) ∣ > ϵ ) P ( ( E ( h 1 ) − E ( h 1 ) > ϵ ) ∨ ⋯ ∨ ( E ( h ∣ H ∣ ) − E ( h ∣ H ∣ ) > ϵ ) ) h ∈ H ∑ P ( ∣ E ( h ) − E ( h ) ∣ > ϵ ) 引理2.1提出，若训练集 D 包含 m m m 0 < ϵ < 1 0\lt\epsilon\lt1 0 < ϵ < 1 h ∈ H , h \in \mathcal{H}, h ∈ H ,
P ( E ^ ( h ) − E ( h ) ⩾ ϵ ) ⩽ exp ( − 2 m ϵ 2 ) P ( E ( h ) − E ^ ( h ) ⩾ ϵ ) ⩽ exp ( − 2 m ϵ 2 ) P ( ∣ E ( h ) − E ^ ( h ) ∣ ⩾ ϵ ) ⩽ 2 exp ( − 2 m ϵ 2 ) \begin{align*}
P(\widehat{E}(h)-\mathbb{E}(h) \geqslant \epsilon) & \leqslant \exp \left(-2 m \epsilon^{2}\right) \\
P(\mathbb{E}(h)-\widehat{E}(h) \geqslant \epsilon) & \leqslant \exp \left(-2 m \epsilon^{2}\right) \\
P(|\mathbb{E}(h)-\widehat{E}(h)| \geqslant \epsilon) & \leqslant 2 \exp \left(-2 m \epsilon^{2}\right)
\end{align*} P ( E ( h ) − E ( h ) ⩾ ϵ ) P ( E ( h ) − E ( h ) ⩾ ϵ ) P ( ∣ E ( h ) − E ( h ) ∣ ⩾ ϵ ) ⩽ exp ( − 2 m ϵ 2 ) ⩽ exp ( − 2 m ϵ 2 ) ⩽ 2 exp ( − 2 m ϵ 2 ) 使用第三个式子，即，
P ( ∣ E ( h ) − E ^ ( h ) ∣ ⩾ ϵ ) ⩽ 2 exp ( − 2 m ϵ 2 ) \begin{equation}
P(|\mathbb{E}(h)-\widehat{E}(h)| \geqslant \epsilon) \leqslant 2 \exp \left(-2 m \epsilon^{2}\right)
\end{equation} P ( ∣ E ( h ) − E ( h ) ∣ ⩾ ϵ ) ⩽ 2 exp ( − 2 m ϵ 2 ) 将其带入式4.6，则有，
∑ h ∈ H P ( ∣ E ^ ( h ) − E ( h ) ∣ > ϵ ) ⩽ ∑ h ∈ H 2 exp ( − 2 m ϵ 2 ) \begin{equation}
\begin{array}{l}
\sum_{h \in \mathcal{H}} P(|\widehat{E}(h)-\mathbb{E}(h)|\gt\epsilon) \leqslant \sum_{h \in \mathcal{H}} 2 \exp \left(-2 m \epsilon^{2}\right)
\end{array}
\end{equation} ∑ h ∈ H P ( ∣ E ( h ) − E ( h ) ∣ > ϵ ) ⩽ ∑ h ∈ H 2 exp ( − 2 m ϵ 2 ) 令 2 exp ( − 2 m ϵ 2 ) = δ / ∣ H ∣ 2 \exp \left(-2 m \epsilon^{2}\right)=\delta /|\mathcal{H}| 2 exp ( − 2 m ϵ 2 ) = δ /∣ H ∣
∑ h ∈ H P ( ∣ E ^ ( h ) − E ( h ) ∣ > ϵ ) ⩽ ∑ h ∈ H δ / ∣ H ∣ ⩽ ∣ H ∣ ⋅ δ / ∣ H ∣ = δ \begin{equation}
\begin{array}{l}
\sum_{h \in \mathcal{H}} P(|\widehat{E}(h)-\mathbb{E}(h)|\gt\epsilon) \leqslant \sum_{h \in \mathcal{H}} \delta /|\mathcal{H}| \leqslant|\mathcal{H}| \cdot \delta /|\mathcal{H}|=\delta
\end{array}
\end{equation} ∑ h ∈ H P ( ∣ E ( h ) − E ( h ) ∣ > ϵ ) ⩽ ∑ h ∈ H δ /∣ H ∣ ⩽ ∣ H ∣ ⋅ δ /∣ H ∣ = δ 从而得到式4.7。
4.4 【证明补充】引理4.1的证明思路
63页 中，引入了引理4.1及其相关的证明。由于证明过程较长，这里对其思路进行梳理和分析。
对于假设空间 H , h ∈ H , m ∈ N , ϵ ∈ ( 0 , 1 ) \mathcal{H}, h \in \mathcal{H}, m \in \mathbb{N}, \epsilon \in (0,1) H , h ∈ H , m ∈ N , ϵ ∈ ( 0 , 1 ) m ≥ 2 / ϵ 2 m \ge 2/\epsilon^2 m ≥ 2/ ϵ 2
P ( ∣ E ( h ) − E ^ ∣ > ϵ ) ≤ 4 Π H ( 2 m ) exp ( − m ϵ 2 8 ) \begin{equation}
P(|\mathbb{E}(h)-\hat{E}| \gt \epsilon) \le 4\Pi_{\mathcal{H}}(2m)\exp(-\frac{m\epsilon^2}{8})
\end{equation} P ( ∣ E ( h ) − E ^ ∣ > ϵ ) ≤ 4 Π H ( 2 m ) exp ( − 8 m ϵ 2 ) 证明简述
当我们要证明这个定理时，需要首先回忆增长函数的定义：对于 m ∈ N m \in\mathbb{N} m ∈ N H \mathcal{H} H 增长函数 (growth function) Π H ( m ) \Pi_{\mathcal{H}}(m) Π H ( m )
Π H ( m ) = max { x 1 , . . . , x m } ⊂ X ∣ { ( h ( x 1 ) , . . . , h ( x m ) ) ∣ h ⊂ H } ∣ \begin{equation}
\Pi_{\mathcal{H}}(m)=\max_{\{\mathbf{x}_1,...,\mathbf{x}_m\}\subset \mathcal{X}}|\{(h(\mathbf{x}_1),...,h(\mathbf{x}_m))|h\subset \mathcal{H}\}|
\end{equation} Π H ( m ) = { x 1 , ... , x m } ⊂ X max ∣ {( h ( x 1 ) , ... , h ( x m )) ∣ h ⊂ H } ∣ 由于泛化误差在实际过程中难以评估，证明中首先将泛化误差和经验误差的差距缩放为经验误差之间的差距。通过概率与期望之间的转化，我们将问题进一步转化，并通过上确界的定义给出一个具体的概念 h 0 h_0 h 0
第二步则是将经验误差之间的差距进一步转化为增长函数的差距，即证明了第二个公式：
P ( sup h ∈ H ∣ E ^ D ( h ) − E ^ D ′ ( h ) ∣ ≥ 1 2 ϵ ) ≤ 2 ∣ H ∣ D + D ′ ∣ ∣ exp ( − ϵ 2 m 8 ) ∣ \begin{equation}
P(\sup_{h\in\mathcal{H}}|\hat E_D(h)-\hat E_{D'}(h)|\geq\frac{1}{2}\epsilon)\leq 2|\mathcal{H}_{|D+D'|}| \exp(-\frac{\epsilon^2m}{8})|
\end{equation} P ( h ∈ H sup ∣ E ^ D ( h ) − E ^ D ′ ( h ) ∣ ≥ 2 1 ϵ ) ≤ 2∣ H ∣ D + D ′ ∣ ∣ exp ( − 8 ϵ 2 m ) ∣ 在这个过程中，使用了式 4.16，通过给出任意置换下的情况，将期望问题转化为级数求和，进一步缩放成有关指数函数的公式：
1 2 m ∑ i = 1 ( 2 m ) ! I ( ∣ E ^ T i D ( h ) − E ^ T i D ′ ( h ) ∥ ) = ∑ k ∈ [ l ] s . t . ∣ 2 k / m − l / m ∣ ≥ ϵ / 2 ( l k ) ( 2 m − l m − k ) ( 2 m m ) \begin{equation}
\frac{1}{2m}\sum_{i=1}^{(2m)!}\mathbb{I}(|\hat E_{T_iD}(h)-\hat E_{T_iD'}(h)\|)=\sum_{k\in[l]\\s.t.|2k/m-l/m|\geq\epsilon/2}\frac{\tbinom{l}{k}\tbinom{2m-l}{m-k}}{\tbinom{2m}{m}}
\end{equation} 2 m 1 i = 1 ∑ ( 2 m )! I ( ∣ E ^ T i D ( h ) − E ^ T i D ′ ( h ) ∥ ) = k ∈ [ l ] s . t .∣2 k / m − l / m ∣ ≥ ϵ /2 ∑ ( m 2 m ) ( k l ) ( m − k 2 m − l ) 注意，原不等式中的上界 2 exp ( − ϵ 2 l 8 ) 2\exp(-\frac{\epsilon^2l}{8}) 2 exp ( − 8 ϵ 2 l )
再通过进一步缩放，得到最后的缩放公式（4.19）。此时，结合前述推导可证明引理。
即使将原不等式中的 2 exp ( − ε 2 l 8 ) 2\exp(-\frac{ε^2l}{8}) 2 exp ( − 8 ε 2 l ) 2 exp ( − ε 2 l 4 ) 2\exp(-\frac{ε^2l}{4}) 2 exp ( − 4 ε 2 l ) O ( l n ( m / d ) m / d ) O(\sqrt\frac{ln(m/d)}{m/d}) O ( m / d l n ( m / d ) )
4.5 【证明补充】定理4.3补充
67页 中提到将式（4.24）带入引理4.1，即可证明定理4.3，具体推导如下：
定理4.3 表示为：
P ( ∣ E ( h ) − E ^ ( h ) ∣ ⩽ 8 d ln 2 e m d + 8 ln 4 δ m ) ⩾ 1 − δ \begin{equation}
P(|\mathbb{E}(h)-\widehat{E}(h)| \leqslant \sqrt{\frac{8 d \ln \frac{2 e m}{d}+8 \ln \frac{4}{\delta}}{m}}) \geqslant 1-\delta
\end{equation} P ( ∣ E ( h ) − E ( h ) ∣ ⩽ m 8 d ln d 2 e m + 8 ln δ 4 ) ⩾ 1 − δ 可以将其等价转化为：
P ( ∣ E ( h ) − E ^ ( h ) ∣ > 8 d ln 2 e m d + 8 ln 4 δ m ) ⩽ δ \begin{equation}
P(|\mathbb{E}(h)-\widehat{E}(h)| \gt \sqrt{\frac{8 d \ln \frac{2 e m}{d}+8 \ln \frac{4}{\delta}}{m}}) \leqslant \delta
\end{equation} P ( ∣ E ( h ) − E ( h ) ∣ > m 8 d ln d 2 e m + 8 ln δ 4 ) ⩽ δ 将（4.24）带入引理4.1可得：
P ( ∣ E ( h ) − E ^ ( h ) ∣ > 8 d ln 2 e m d + 8 ln 4 δ m ) ⩽ 4 Π H ( 2 m ) exp ( − m ϵ 2 8 ) \begin{equation}
P(|\mathbb{E}(h)-\widehat{E}(h)|\gt\sqrt{\frac{8 d \ln \frac{2 e m}{d}+8 \ln \frac{4}{\delta}}{m}}) \leqslant 4 \Pi_{\mathcal{H}}(2 m) \exp \left(-\frac{m \epsilon^{2}}{8}\right)
\end{equation} P ( ∣ E ( h ) − E ( h ) ∣ > m 8 d ln d 2 e m + 8 ln δ 4 ) ⩽ 4 Π H ( 2 m ) exp ( − 8 m ϵ 2 ) 根据 3.1 可得：
4 Π H ( 2 m ) exp ( − m ϵ 2 8 ) ⩽ 4 ( 2 e m d ) d exp ( − m ϵ 2 8 ) \begin{equation}
4 \Pi_{\mathcal{H}}(2 m) \exp \left(-\frac{m \epsilon^{2}}{8}\right) \leqslant 4\left(\frac{2 e m}{d}\right)^{d} \exp \left(-\frac{m \epsilon^{2}}{8}\right)
\end{equation} 4 Π H ( 2 m ) exp ( − 8 m ϵ 2 ) ⩽ 4 ( d 2 e m ) d exp ( − 8 m ϵ 2 ) 所以引理4.1可以转化为：
P ( ∣ E ( h ) − E ^ ( h ) ∣ > 8 d ln 2 e m d + 8 ln 4 δ m ) ⩽ 4 Π H ( 2 m ) exp ( − m ϵ 2 8 ) ⩽ 4 ( 2 e m d ) d exp ( − m ϵ 2 8 ) \begin{equation}
P(|\mathbb{E}(h)-\widehat{E}(h)|\gt\sqrt{\frac{8 d \ln \frac{2 e m}{d}+8 \ln \frac{4}{\delta}}{m}}) \leqslant 4 \Pi_{\mathcal{H}}(2 m) \exp \left(-\frac{m \epsilon^{2}}{8}\right) \leqslant 4\left(\frac{2 e m}{d}\right)^{d} \exp \left(-\frac{m \epsilon^{2}}{8}\right)
\end{equation} P ( ∣ E ( h ) − E ( h ) ∣ > m 8 d ln d 2 e m + 8 ln δ 4 ) ⩽ 4 Π H ( 2 m ) exp ( − 8 m ϵ 2 ) ⩽ 4 ( d 2 e m ) d exp ( − 8 m ϵ 2 ) 令 4 ( 2 e m d ) d exp ( − m ϵ 2 8 ) = δ 4\left(\frac{2 e m}{d}\right)^{d} \exp \left(-\frac{m \epsilon^{2}}{8}\right) = \delta 4 ( d 2 e m ) d exp ( − 8 m ϵ 2 ) = δ
P ( ∣ E ( h ) − E ^ ( h ) ∣ > 8 d ln 2 e m d + 8 ln 4 δ m ) ⩽ δ \begin{equation}
P(|\mathbb{E}(h)-\widehat{E}(h)|\gt\sqrt{\frac{8 d \ln \frac{2 e m}{d}+8 \ln \frac{4}{\delta}}{m}}) \leqslant \delta
\end{equation} P ( ∣ E ( h ) − E ( h ) ∣ > m 8 d ln d 2 e m + 8 ln δ 4 ) ⩽ δ 从而得到了定理4.3的结论。
定理4.3 说明了期望误差和经验误差之间的差异程度，以概率形式限定在一定的区域范围内，虽然这并不完全代表误差一定会在 8 d ln 2 e m d + 8 ln 4 δ m \sqrt{\frac{8 d \ln \frac{2 e m}{d}+8 \ln \frac{4}{\delta}}{m}} m 8 d l n d 2 e m + 8 l n δ 4 1 − δ 1-\delta 1 − δ m d \frac{m}{d} d m l n ( x ) ln(x) l n ( x ) x x x
4.6 【概念解释】回顾 Rademacher 复杂度
68页 谈论了基于 Rademacher 的泛化误差界，这里对 Rademacher 复杂度进行回顾。
由于 VC 维和数据分布无关，未考虑数据的特定分布情况，其得到的结论往往是“松”的。Rademacher 复杂度则是基于数据分布的考虑，在牺牲了一定“普适性”的情况下，得到更为“紧”的结论。
复杂度是人为定义的一套量化复杂度程度的概念。对应 Rademacher 复杂度，假设空间中表示能力越强的函数，其复杂度越高。回到46-47页 ，如果 E σ [ sup h ∈ H 1 m ∑ i = 1 m σ i h ( x i ) ] = 1 \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]=1 E σ [ sup h ∈ H m 1 ∑ i = 1 m σ i h ( x i ) ] = 1 x x x x x x
对于 Rademacher 复杂度的定义，我们进一步将具体的数据样本点转化为数据的样本空间分布，在经验误差的形式外面套一层期望，从而得到了一般化的 Rademacher 复杂度的定义。经验 Rademacher 复杂度和 Rademacher 复杂度的关系就如同概率论中掷硬币的观测序列和将其视为一个先验分布的随机变量序列一样。
4.7 【证明补充】引理4.6的证明解析
71页 的定理4.6给出了泛化误差下界的形式化表述：
P ( E ( h D , c ) > d − 1 32 m ) ≥ 1 100 \begin{equation}
P\left(\mathbb{E}(h_D, c) > \frac{d-1}{32m}\right) \ge \frac{1}{100}
\end{equation} P ( E ( h D , c ) > 32 m d − 1 ) ≥ 100 1 虽然不等式右边的常数 1 100 \frac{1}{100} 100 1
事实上，根据公式（4.50）的推导，只要选择一个小于 1 − e − d − 1 12 7 \frac{1 - e^{-\frac{d-1}{12}}}{7} 7 1 − e − 12 d − 1 d = 2 d=2 d = 2 0.0114 0.0114 0.0114 1 100 \frac{1}{100} 100 1
进一步分析发现，随着维度 d d d 1 7 \frac{1}{7} 7 1 1 7 \frac{1}{7} 7 1
至于常数 32 32 32 ϵ \epsilon ϵ d − 1 16 ( 1 + r ) \frac{d-1}{16(1+r)} 16 ( 1 + r ) d − 1 r = 1 r=1 r = 1 32 32 32
4.8 【证明补充】引理4.2补充
74页 提出了引理4.2，这里给出完整的证明过程。
令 σ \sigma σ { − 1 , + 1 } \{-1,+1\} { − 1 , + 1 } 0 < α < 1 0\lt\alpha\lt1 0 < α < 1 α σ = 1 / 2 − α σ / 2 \alpha_{\sigma} = 1/2 - \alpha
\sigma/2 α σ = 1/2 − α σ /2 σ \sigma σ X ∼ D σ X \sim D_{\sigma} X ∼ D σ D σ D_{\sigma} D σ B e r n o u l l i ( α σ ) Bernoulli(\alpha_{\sigma}) B er n o u l l i ( α σ ) P ( X = 1 ) = α σ P(X=1)=\alpha_{\sigma} P ( X = 1 ) = α σ S = { X 1 , ⋯ , X m } S=\{X_1,\cdots,X_m\} S = { X 1 , ⋯ , X m } D α m D_{\alpha}^m D α m m m m S ∼ D α m S \sim D_{\alpha}^m S ∼ D α m f : X m → { − 1 , + 1 } f:X^m \rightarrow \{-1,+1\} f : X m → { − 1 , + 1 }
E σ [ P S ∼ D α m ( f ( S ) ≠ σ ) ] ≥ Φ ( 2 ⌈ m / 2 ⌉ , α ) \begin{equation}
\mathbb{E}_{\sigma}[P_{S \sim D_{\alpha}^m}(f(S) \neq \sigma)] \ge \Phi (2\lceil m/2 \rceil, \alpha)
\end{equation} E σ [ P S ∼ D α m ( f ( S ) = σ )] ≥ Φ ( 2 ⌈ m /2 ⌉ , α ) 其中 Φ ( m , α ) = 1 4 ( 1 − 1 − exp ( − m α 2 1 − α 2 ) ) \Phi (m, \alpha) = \frac{1}{4} (1 - \sqrt{1 - \exp(-\frac{m\alpha^2}{1 - \alpha^2})}) Φ ( m , α ) = 4 1 ( 1 − 1 − exp ( − 1 − α 2 m α 2 ) )
证明
我们设想两枚硬币 x A x_A x A x B x_B x B P [ x A = 0 ] = 1 / 2 − α / 2 P[x_A = 0] = 1/2−\alpha/2 P [ x A = 0 ] = 1/2 − α /2 P [ x B = 0 ] = 1 / 2 + α / 2 P[x_B = 0] = 1/2+\alpha/2 P [ x B = 0 ] = 1/2 + α /2 0 < α < 1 0\lt\alpha\lt1 0 < α < 1 x ∈ { x A , x B } x \in \{x_A,x_B\} x ∈ { x A , x B } m m m α σ \alpha_{\sigma} α σ f : { 0 , 1 } m → { x A , x B } f:\{0,1\}^m\rightarrow\{x_A,x_B\} f : { 0 , 1 } m → { x A , x B } e r r o r ( f ) = E [ P S ∼ D α m ( f ( S ) ≠ x ) ] error(f)=\mathbb{E}[\mathbb{P}_{S\sim\mathcal{D}_\alpha^m}(f(S)\neq x)] er r or ( f ) = E [ P S ∼ D α m ( f ( S ) = x )]
用 f f f F A F_A F A f ( S ) = x A f(S)=x_A f ( S ) = x A F B F_B F B f ( S ) = x B f(S)=x_B f ( S ) = x B N ( S ) N(S) N ( S ) S S S
e r r o r ( f ) = ∑ S ∈ F A P [ S ∧ x B ] + ∑ S ∈ F B P [ S ∧ x A ] = 1 2 ∑ S ∈ F A P [ S ∣ x B ] + 1 2 ∑ S ∈ F B P [ S ∣ x A ] = 1 2 ∑ S ∈ F A N ( S ) < ⌈ m / 2 ⌉ P [ S ∣ x B ] + 1 2 ∑ S ∈ F A N ( S ) ≥ ⌈ m / 2 ⌉ P [ S ∣ x B ] + 1 2 ∑ S ∈ F B N ( S ) < ⌈ m / 2 ⌉ P [ S ∣ x A ] + 1 2 ∑ S ∈ F B N ( S ) ≥ ⌈ m / 2 ⌉ P [ S ∣ x A ] \begin{align*}
error(f)&=\sum_{S\in F_A}\mathbb{P}[S\wedge x_B]+\sum_{S\in F_B}\mathbb{P}[S\wedge x_A]\\
&=\frac{1}{2}\sum_{S\in F_A}\mathbb{P}[S|x_B]+\frac{1}{2}\sum_{S\in F_B}\mathbb{P}[S|x_A]\\
&=\frac{1}{2}\sum_{S\in F_A\atop N(S)\lt\lceil m/2\rceil}\mathbb{P}[S|x_B]+\frac{1}{2}\sum_{S\in F_A\atop N(S)\ge \lceil m/2\rceil}\mathbb{P}[S|x_B]
+\frac{1}{2}\sum_{S\in F_B\atop N(S)\lt \lceil m/2\rceil}\mathbb{P}[S|x_A]+\frac{1}{2}\sum_{S\in F_B\atop N(S)\ge \lceil m/2\rceil}\mathbb{P}[S|x_A]\\
\end{align*} er r or ( f ) = S ∈ F A ∑ P [ S ∧ x B ] + S ∈ F B ∑ P [ S ∧ x A ] = 2 1 S ∈ F A ∑ P [ S ∣ x B ] + 2 1 S ∈ F B ∑ P [ S ∣ x A ] = 2 1 N ( S ) < ⌈ m /2 ⌉ S ∈ F A ∑ P [ S ∣ x B ] + 2 1 N ( S ) ≥ ⌈ m /2 ⌉ S ∈ F A ∑ P [ S ∣ x B ] + 2 1 N ( S ) < ⌈ m /2 ⌉ S ∈ F B ∑ P [ S ∣ x A ] + 2 1 N ( S ) ≥ ⌈ m /2 ⌉ S ∈ F B ∑ P [ S ∣ x A ] 如果 N ( S ) ≥ ⌈ m / 2 ⌉ N(S)\ge \lceil m/2\rceil N ( S ) ≥ ⌈ m /2 ⌉ P [ S ∣ x B ] ≥ P [ S ∣ x A ] \mathbb{P}[S|x_B]\ge\mathbb{P}[S|x_A] P [ S ∣ x B ] ≥ P [ S ∣ x A ] N ( S ) < ⌈ m / 2 ⌉ N(S)\lt \lceil m/2\rceil N ( S ) < ⌈ m /2 ⌉ P [ S ∣ x A ] ≥ P [ S ∣ x B ] \mathbb{P}[S|x_A]\ge\mathbb{P}[S|x_B] P [ S ∣ x A ] ≥ P [ S ∣ x B ]
e r r o r ( f ) ≥ 1 2 ∑ S ∈ F A N ( S ) < ⌈ m / 2 ⌉ P [ S ∣ x B ] + 1 2 ∑ S ∈ F A N ( S ) ≥ ⌈ m / 2 ⌉ P [ S ∣ x A ] + 1 2 ∑ S ∈ F B N ( S ) < ⌈ m / 2 ⌉ P [ S ∣ x B ] + 1 2 ∑ S ∈ F B N ( S ) ≥ ⌈ m / 2 ⌉ P [ S ∣ x A ] = 1 2 ∑ S : N ( S ) < ⌈ m / 2 ⌉ P [ S ∣ x B ] + 1 2 ∑ S : N ( S ) ≥ ⌈ m / 2 ⌉ P [ S ∣ x A ] = e r r o r ( f o ) \begin{align*}
error(f) &\ge\frac{1}{2}\sum_{S\in F_A\atop N(S)\lt\lceil m/2\rceil}\mathbb{P}[S|x_B]+\frac{1}{2}\sum_{S\in F_A\atop N(S)\ge \lceil m/2\rceil}\mathbb{P}[S|x_A]
+\frac{1}{2}\sum_{S\in F_B\atop N(S)\lt \lceil m/2\rceil}\mathbb{P}[S|x_B]+\frac{1}{2}\sum_{S\in F_B\atop N(S)\ge \lceil m/2\rceil}\mathbb{P}[S|x_A]\\
&=\frac{1}{2}\sum_{S:N(S)\lt\lceil m/2\rceil}\mathbb{P}[S|x_B]+\frac{1}{2}\sum_{S:N(S)\ge \lceil m/2\rceil}\mathbb{P}[S|x_A]\\
&=error(f_o)
\end{align*} er r or ( f ) ≥ 2 1 N ( S ) < ⌈ m /2 ⌉ S ∈ F A ∑ P [ S ∣ x B ] + 2 1 N ( S ) ≥ ⌈ m /2 ⌉ S ∈ F A ∑ P [ S ∣ x A ] + 2 1 N ( S ) < ⌈ m /2 ⌉ S ∈ F B ∑ P [ S ∣ x B ] + 2 1 N ( S ) ≥ ⌈ m /2 ⌉ S ∈ F B ∑ P [ S ∣ x A ] = 2 1 S : N ( S ) < ⌈ m /2 ⌉ ∑ P [ S ∣ x B ] + 2 1 S : N ( S ) ≥ ⌈ m /2 ⌉ ∑ P [ S ∣ x A ] = er r or ( f o ) 因此，当我们选取 f o f_o f o N ( S ) < ⌈ m / 2 ⌉ N(S)\lt \lceil m/2\rceil N ( S ) < ⌈ m /2 ⌉ f o ( S ) = x A f_o(S)=x_A f o ( S ) = x A
注意到 P [ N ( S ) ≥ ⌈ m / 2 ⌉ ∣ x = x A ] = P [ B ( 2 ⌈ m / 2 ⌉ , p ) ≥ k ] \mathbb{P}[N(S)\ge \lceil m/2\rceil|x=x_A]=\mathbb{P}[B(2\lceil m/2\rceil,p)\ge k] P [ N ( S ) ≥ ⌈ m /2 ⌉ ∣ x = x A ] = P [ B ( 2 ⌈ m /2 ⌉ , p ) ≥ k ] p = 1 / 2 − α / 2 , k = ⌈ m / 2 ⌉ p=1/2-\alpha /2,k=\lceil m/2\rceil p = 1/2 − α /2 , k = ⌈ m /2 ⌉ 2 ⌈ m / 2 ⌉ p ≤ k ≤ 2 ⌈ m / 2 ⌉ ( 1 − p ) 2\lceil m/2\rceil p\le k\le 2\lceil m/2\rceil(1-p) 2 ⌈ m /2 ⌉ p ≤ k ≤ 2 ⌈ m /2 ⌉ ( 1 − p )
根据 Slud 不等式，我们有：
e r r o r ( f o ) ≥ 1 2 P [ N ≥ ⌈ m / 2 ⌉ α 1 / 2 ( 1 − α 2 ) ⌈ m / 2 ⌉ ] = 1 2 P [ N ≥ 2 ⌈ m / 2 ⌉ 1 − α 2 α ] \begin{equation}
error(f_o) \ge \frac{1}{2}\mathbb{P}[N\ge\frac{\lceil m/2\rceil\alpha}{\sqrt{1/2(1-\alpha^2)\lceil m/2\rceil}}]=\frac{1}{2}\mathbb{P}[N\ge\sqrt{\frac{2\lceil m/2\rceil}{1-\alpha^2}}\alpha]
\end{equation} er r or ( f o ) ≥ 2 1 P [ N ≥ 1/2 ( 1 − α 2 ) ⌈ m /2 ⌉ ⌈ m /2 ⌉ α ] = 2 1 P [ N ≥ 1 − α 2 2 ⌈ m /2 ⌉ α ] 根据第一章补充内容中的正态分布不等式推论，我们有：
e r r o r ( f o ) ≥ 1 4 ( 1 − 1 − e − 2 π u 2 ) ≥ 1 4 ( 1 − 1 − e − u 2 ) \begin{equation}
error(f_o)\ge\frac{1}{4}(1-\sqrt{1-e^{-\frac{2}{\pi}u^2}})\ge\frac{1}{4}(1-\sqrt{1-e^{-u^2}})
\end{equation} er r or ( f o ) ≥ 4 1 ( 1 − 1 − e − π 2 u 2 ) ≥ 4 1 ( 1 − 1 − e − u 2 ) 此处 u = 2 ⌈ m / 2 ⌉ 1 − α 2 α u=\sqrt{\frac{2\lceil m/2\rceil}{1-\alpha^2}}\alpha u = 1 − α 2 2 ⌈ m /2 ⌉ α
事实上，根据上面的推导，我们可以进一步提升泛化误差的下界，即：
E [ P S ∼ D α m ( f ( S ) ≠ x ) ] ≥ 1 4 ( 1 − 1 − e − 2 π u 2 ) \begin{equation}
\mathbb{E}[\mathbb{P}_{S\sim\mathcal{D}_\alpha^m}(f(S)\neq x)]\ge\frac{1}{4}(1-\sqrt{1-e^{-\frac{2}{\pi}u^2}})
\end{equation} E [ P S ∼ D α m ( f ( S ) = x )] ≥ 4 1 ( 1 − 1 − e − π 2 u 2 ) 在引理末尾处，提到了至少需要 Ω ( 1 α 2 ) \Omega(\frac{1}{\alpha^2}) Ω ( α 2 1 ) σ i \sigma_i σ i e r r o r ( f o ) = δ > 0 error(f_o)=\delta\gt0 er r or ( f o ) = δ > 0
1 4 ( 1 − 1 − e − u 2 ) ≤ δ ⇔ m ≥ 2 ⌈ 1 − ϵ 2 2 ϵ 2 ln 1 8 δ ( 1 − 2 δ ) ⌉ \begin{equation}
\frac{1}{4}(1-\sqrt{1-e^{-u^2}})\le\delta\Leftrightarrow m\ge 2\lceil \frac{1-\epsilon^2}{2\epsilon^2} \ln\frac{1}{8\delta(1-2\delta)} \rceil
\end{equation} 4 1 ( 1 − 1 − e − u 2 ) ≤ δ ⇔ m ≥ 2 ⌈ 2 ϵ 2 1 − ϵ 2 ln 8 δ ( 1 − 2 δ ) 1 ⌉ 此时，我们发现 m m m Ω ( 1 α 2 ) \Omega(\frac{1}{\alpha^2}) Ω ( α 2 1 ) 1 − δ 1-\delta 1 − δ σ \sigma σ
4.9 【证明补充】引理4.7的补充
75页 的定理4.7主要表达的是：无论算法有多强，在不可分的情况下，总会有某种“坏”分布使得输出假设的泛化误差以常数概率为O ( d m ) O(\sqrt\frac{d}{m}) O ( m d )
∑ x i ∈ S ( I ( h ( x i ) ≠ h D σ ∗ ( x i ) ) + I ( h ( x i ) = h D σ ∗ ( x i ) ) ) = d \begin{equation}
\sum_{x_i\in S}(\mathbb{I}(h(x_i)\neq h_{\mathcal{D}_{\sigma}^*}(x_i))+\mathbb{I}(h(x_i) = h_{\mathcal{D}_{\sigma}^*}(x_i))) = d
\end{equation} x i ∈ S ∑ ( I ( h ( x i ) = h D σ ∗ ( x i )) + I ( h ( x i ) = h D σ ∗ ( x i ))) = d 另外，（4.63）的第三步为何不直接利用引理4.2进行推导呢？这是考虑到函数Φ ( ⋅ , α ) \Phi(·,\alpha) Φ ( ⋅, α ) m / d + 1 ≤ 2 ⌈ m / 2 ⌉ m/d+1\le2\lceil m/2\rceil m / d + 1 ≤ 2 ⌈ m /2 ⌉ Φ ( m / d + 1 , α ) ≥ Φ ( 2 ⌈ m / 2 ⌉ , α ) \Phi(m/d+1,\alpha)\ge\Phi(2\lceil m/2\rceil,\alpha) Φ ( m / d + 1 , α ) ≥ Φ ( 2 ⌈ m /2 ⌉ , α ) ∣ Z ∣ x |Z|_x ∣ Z ∣ x
在76页 左下角的最后一个脚注中，提到了m / d m/d m / d ∣ Z ∣ x |Z|_x ∣ Z ∣ x U \mathcal{U} U { − 1 , + 1 } d \{-1,+1\}^d { − 1 , + 1 } d x x x 1 / d 1/d 1/ d D σ D_σ D σ m m m S S S x x x m / d m/d m / d
此外，（4.65）中用到了引理4.3。令 Z ′ = 1 α ( E ( h Z ) − E ( h D σ ∗ m ∗ ) ) Z'=\frac{1}{\alpha}(\mathbb{E}(h_Z)-\mathbb{E}(h_{\mathcal{D}_{\sigma^*}^{m}}^{*})) Z ′ = α 1 ( E ( h Z ) − E ( h D σ ∗ m ∗ )) 0 ≤ Z ′ ≤ 1 0\le Z'\le1 0 ≤ Z ′ ≤ 1 γ ′ = γ u \gamma'=\gamma u γ ′ = γ u Φ ( ⋅ , α ) \Phi(·,\alpha) Φ ( ⋅, α ) 1 / 4 1/4 1/4 γ ′ ∈ [ 0 , 1 / 4 ) ⊆ [ 0 , 1 ) \gamma'\in[0,1/4)\subseteq[0,1) γ ′ ∈ [ 0 , 1/4 ) ⊆ [ 0 , 1 )
P ( Z ′ > γ ′ ) ≥ E [ Z ′ ] − γ ′ ≥ u − u γ = ( 1 − γ ) u \begin{equation}
P(Z'\gt\gamma')\ge \mathbb{E}[Z']-\gamma' \ge u-u\gamma = (1-\gamma)u
\end{equation} P ( Z ′ > γ ′ ) ≥ E [ Z ′ ] − γ ′ ≥ u − u γ = ( 1 − γ ) u 同时，（4.69）到（4.70）的推导中体现了充分条件的思想。由（4.69）可知：
m d ≤ A ϵ 2 + B \begin{equation}
\frac{m}{d}\le \frac{A}{\epsilon^2}+B
\end{equation} d m ≤ ϵ 2 A + B 其中 A = ( 7 64 ) 2 ln 4 3 A=(\frac{7}{64})^2 \ln \frac{4}{3} A = ( 64 7 ) 2 ln 3 4 B = − ln 4 3 − 1 B=-\ln \frac{4}{3}-1 B = − ln 3 4 − 1
我们希望能推导出更为简洁的 m d \frac{m}{d} d m 1 ϵ 2 \frac{1}{\epsilon^2} ϵ 2 1
m d ≤ A ϵ 2 + B ≤ ω ϵ 2 \begin{equation}
\frac{m}{d}\le \frac{A}{\epsilon^2}+B\le\frac{\omega}{\epsilon^2}
\end{equation} d m ≤ ϵ 2 A + B ≤ ϵ 2 ω 即使得 ω ≥ B ϵ 2 + A \omega\ge B\epsilon^2+A ω ≥ B ϵ 2 + A ϵ ≤ 1 / 64 \epsilon\le 1/64 ϵ ≤ 1/64 ω \omega ω
值得注意的是，整个证明过程共进行了四次启发式限制，分别为 γ = 1 − 8 δ \gamma=1-8\delta γ = 1 − 8 δ α = 8 ϵ / ( 1 − 8 ϵ ) \alpha=8\epsilon/(1-8\epsilon) α = 8 ϵ / ( 1 − 8 ϵ ) δ ≤ 1 / 64 \delta\le1/64 δ ≤ 1/64 ϵ ≤ 1 / 64 \epsilon\le1/64 ϵ ≤ 1/64
4.10 【概念解释】ρ \rho ρ
79页 提到，由经验损失（公式4.72）可知 Φ ρ \Phi_\rho Φ ρ 1 ρ \frac{1}{\rho} ρ 1
根据Lipschitz连续性的定义，我们可以通过拉格朗日中值定理来证明这一点。具体来说，由拉格朗日中值定理可得：
∣ Φ ρ ( x 1 ) − Φ ρ ( x 2 ) ∣ ≤ ∣ Φ ρ ′ ( ξ ) ∣ ∣ x 1 − x 2 ∣ \begin{equation}
|\Phi_\rho(x_1)-\Phi_\rho(x_2)| \leq |\Phi_\rho'(\xi)| |x_1-x_2|
\end{equation} ∣ Φ ρ ( x 1 ) − Φ ρ ( x 2 ) ∣ ≤ ∣ Φ ρ ′ ( ξ ) ∣∣ x 1 − x 2 ∣ 其中 ξ \xi ξ x 1 x_1 x 1 x 2 x_2 x 2
已知 Φ ρ \Phi_\rho Φ ρ Φ ρ ′ ( ξ ) \Phi_\rho'(\xi) Φ ρ ′ ( ξ )
∣ Φ ρ ′ ( ξ ) ∣ ≤ 1 ρ \begin{equation}
|\Phi_\rho'(\xi)| \leq \frac{1}{\rho}
\end{equation} ∣ Φ ρ ′ ( ξ ) ∣ ≤ ρ 1 因此，根据Lipschitz条件的定义，ρ \rho ρ 1 ρ \frac{1}{\rho} ρ 1
4.11 【证明补充】定理4.8补充
79页 的定理4.8给出了关于间隔损失函数的分类问题SVM的泛化误差界。
此处存在一个小的错误：公式4.80前的 “代入 (4.96)” 应为 “代入 (4.76)” 。
观察要证明的公式，我们发现这是关于 Rademacher 复杂度的泛化上界推理，自然地回顾一下 Rademacher 复杂度。
现实任务中样本标记有时会受到噪声影响，因此我们与其在假设空间 H \mathcal{H} H H \mathcal{H} H
在此直接考虑利用前面讲到的关于实值假设空间中的期望与 Rademacher 复杂度的不等式。通过前面 4.73 讲到的关于间隔函数的经验间隔损失的式子，可以带入得到大体形式。
由于前面引理提到的关于 Lipschitz 函数的性质，结合 ρ \rho ρ
