第12章 计算学习理论
正如本章开篇所述，计算学习理论研究目的是分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计。例如，"西瓜书"定理12.1、定理12.3、定理12.6所表达意思的共同点是，泛化误差与经验误差之差的绝对值以很大概率(1 − δ 1-\delta 1 − δ m m m ∣ H ∣ \vert\mathcal{H}\vert ∣ H ∣
12.1 基础知识
统计学中有总体集合和样本集合之分,
比如要统计国内本科生对机器学习的掌握情况,
此时全国所有的本科生就是总体集合,
但总体集合往往太大而不具有实际可操作性, 一般都 是取总体集合的一部分,
比如从双一流 A \mathrm{A} A B \mathrm{B} B 1.2 1.2 1.2 D D D D D D D \mathcal{D} D D D D D ( t ) \mathcal{D}(t) D ( t ) t t t
12.1.1 式(12.1)的解释
该式为泛化误差的定义式，所谓泛化误差，是指当样本x x x D \mathcal{D} D h ( x ) h(\boldsymbol{x}) h ( x ) y y y D \mathcal{D} D D \mathcal{D} D D D D D \mathcal{D} D
12.1.2 式(12.2)的解释
该式为经验误差的定义式，所谓经验误差，是指观测集D D D x i , i = 1 , 2 , ⋯ , m x_i, i=1,2,\cdots,m x i , i = 1 , 2 , ⋯ , m h ( x i ) h(\boldsymbol{x}_i) h ( x i ) y i y_i y i
12.1.3 式(12.3)的解释
假设我们有两个模型h 1 h_1 h 1 h 2 h_2 h 2 x \boldsymbol{x} x
12.1.4 式(12.4)的解释
Jensen不等式：这个式子可以做很直观的理解，比如说在二维空间上，凸函数可以想象成开口向上的抛物线，假如我们有两个点x 1 , x 2 x_1, x_2 x 1 , x 2 f ( E ( x ) ) f(\mathbb{E}(x)) f ( E ( x )) E ( f ( x ) ) \mathbb{E}(f(x)) E ( f ( x ))
12.1.5 式(12.5)的解释
随机变量的观测值是随机的, 进一步地, 随机过程的每个时刻都是一个随机变量。
式中, 1 m ∑ i = 1 m x i \frac{1}{m} \sum_{i=1}^m x_i m 1 ∑ i = 1 m x i m m m 1 m ∑ i = 1 m E ( x i ) \frac{1}{m} \sum_{i=1}^m \mathbb{E}\left(x_i\right) m 1 ∑ i = 1 m E ( x i ) m m m
式(12.5)表示事件
1 m ∑ i = 1 m x i − 1 m ∑ i = 1 m E ( x i ) ⩾ ϵ \frac{1}{m} \sum_{i=1}^m x_i-\frac{1}{m} \sum_{i=1}^m \mathbb{E}\left(x_i\right) \geqslant \epsilon m 1 ∑ i = 1 m x i − m 1 ∑ i = 1 m E ( x i ) ⩾ ϵ ⩽ ) e − 2 m ϵ 2 \left.\leqslant\right) e^{-2 m \epsilon^2} ⩽ ) e − 2 m ϵ 2 ∣ 1 m ∑ i = 1 m x i − 1 m ∑ i = 1 m E ( x i ) ∣ ⩾ ϵ \left|\frac{1}{m} \sum_{i=1}^m x_i-\frac{1}{m} \sum_{i=1}^m \mathbb{E}\left(x_i\right)\right| \geqslant \epsilon m 1 ∑ i = 1 m x i − m 1 ∑ i = 1 m E ( x i ) ⩾ ϵ
1 m ∑ i = 1 m x i − 1 m ∑ i = 1 m E ( x i ) ⩾ ϵ ∨ 1 m ∑ i = 1 m x i − 1 m ∑ i = 1 m E ( x i ) ⩽ − ϵ \frac{1}{m} \sum_{i=1}^m x_i-\frac{1}{m} \sum_{i=1}^m \mathbb{E}\left(x_i\right) \geqslant \epsilon \quad \vee \quad \frac{1}{m} \sum_{i=1}^m x_i-\frac{1}{m} \sum_{i=1}^m \mathbb{E}\left(x_i\right) \leqslant-\epsilon m 1 i = 1 ∑ m x i − m 1 i = 1 ∑ m E ( x i ) ⩾ ϵ ∨ m 1 i = 1 ∑ m x i − m 1 i = 1 ∑ m E ( x i ) ⩽ − ϵ 其中, ∨ \vee ∨ 1 m ∑ i = 1 m x i − 1 m ∑ i = 1 m E ( x i ) ⩽ − ϵ \frac{1}{m} \sum_{i=1}^m x_i-\frac{1}{m} \sum_{i=1}^m \mathbb{E}\left(x_i\right) \leqslant-\epsilon m 1 ∑ i = 1 m x i − m 1 ∑ i = 1 m E ( x i ) ⩽ − ϵ
Hoeffding 不等式表达的意思是 1 m ∑ i = 1 m x i \frac{1}{m} \sum_{i=1}^m x_i m 1 ∑ i = 1 m x i 1 m ∑ i = 1 m E ( x i ) \frac{1}{m} \sum_{i=1}^m \mathbb{E}\left(x_i\right) m 1 ∑ i = 1 m E ( x i ) ϵ \epsilon ϵ 2 e − 2 m ϵ 2 2 e^{-2 m \epsilon^2} 2 e − 2 m ϵ 2
如果对Hoeffding不等式的证明感兴趣，可以参考Hoeffding在1963年发表的论文[1]，这篇文章也被引用了逾万次。
12.1.6 式(12.7)的解释
McDiarmid不等式：首先解释下前提条件：
sup x 1 , … , x m , x i ′ ∣ f ( x 1 , … , x m ) − f ( x 1 , … , x i − 1 , x i ′ , x i + 1 , … , x m ) ∣ ⩽ c i \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} x 1 , … , x m , x i ′ sup ∣ f ( x 1 , … , x m ) − f ( x 1 , … , x i − 1 , x i ′ , x i + 1 , … , x m ) ∣ ⩽ c i 表示当函数f f f x i x_i x i x i ′ x_i^\prime x i ′ sup \sup sup c i c_i c i f ( x 1 , … , x m ) f(x_1,\dots,x_m) f ( x 1 , … , x m ) E ( f ( x 1 , … , x m ) ) \mathbb{E}\left(f(x_1,\dots,x_m)\right) E ( f ( x 1 , … , x m ) ) ϵ \epsilon ϵ exp ( − 2 ϵ 2 ∑ i c i 2 ) \exp \left(\frac{-2 \epsilon^{2}}{\sum_{i} c_{i}^{2}}\right) exp ( ∑ i c i 2 − 2 ϵ 2 )
12.2 PAC学习
本节内容几乎都是概念, 建议多读几遍，仔细琢磨一下。
概率近似正确(Probably Approximately Correct, PAC)学习, 可以读为
[pæk]学习。
本节第 2 段讨论的目标概念, 可简单理解为真实的映射函数;
本节第 3 段讨论的假设空间, 可简单理解为学习算法不同参数时的存在,
例如线性分类 超平面
f ( x ) = w ⊤ x + b f(\boldsymbol{x})=\boldsymbol{w}^{\top} \boldsymbol{x}+b f ( x ) = w ⊤ x + b ( w , b ) (\boldsymbol{w}, b) ( w , b )
本节第 4 段讨论的可分的(separable)和不可分的(non-separable),
例如西瓜书第 100 页的 图 5.4, 若假设空间是线性分类器,
则(a)(b)(c)是可分的, 而(d)是不可分的; 当然, 若假设空 间为椭圆分类器
(分类边界为椭圆), 则(d)也是可分的;
本节第 5 段提到的 "等效的假设"指的是第 7 页图 1.3 1.3 1.3 A \mathrm{A} A B \mathrm{B} B
定义 12.1 PAC 辨识的式(12.9)表示输出假设 h h h E ( h ) ⩽ ϵ E(h) \leqslant \epsilon E ( h ) ⩽ ϵ 1 − δ 1-\delta 1 − δ L \mathfrak{L} L 1 − δ 1-\delta 1 − δ c c c ϵ \epsilon ϵ
定义 12.2 PAC 可学习的核心在于, 需要的样本数目 m m m 1 / ϵ , 1 / δ , size ( x ) , size ( c ) 1 / \epsilon, 1 / \delta, \operatorname{size}(\boldsymbol{x}), \operatorname{size}(\mathrm{c}) 1/ ϵ , 1/ δ , size ( x ) , size ( c )
定义 12.3 PAC 学习算法的核心在于, 完成 PAC 学习所需要的时间是
1 / ϵ , 1 / δ , size ( x ) 1 / \epsilon, 1 / \delta, \operatorname{size}(\boldsymbol{x}) 1/ ϵ , 1/ δ , size ( x ) size ( c ) \operatorname{size}(\mathrm{c}) size ( c )
定义 12.4 样本复杂度指完成 PAC 学习过程需要的最少的样本数量,
而在实际中当然也 希望用最少的样本数量完成学习过程。
在定义 12.4 之后, 抛出来三个问题:
研究某任务在什么样的条件下可学得较好的模型？（定义 12.2）
某算法在什么样的条件下可进行有效的学习?（定义 12.3）
需多少训练样例才能获得较好的模型？（定义 12.4）
有限假设空间指 H \mathcal{H} H
12.2.1 式(12.9)的解释
PAC辨识的定义：E ( h ) E(h) E ( h ) L \mathcal{L} L D D D h h h h h h ϵ \epsilon ϵ 1 − δ 1-\delta 1 − δ L \mathcal{L} L H \mathcal{H} H C \mathcal{C} C
12.3 有限假设空间
本节内容分两部分, 第 1 部分 "可分情形" 时, 可以达到经验误差
E ^ ( h ) = 0 \widehat{E}(h)=0 E ( h ) = 0 1 − δ 1-\delta 1 − δ ϵ \epsilon ϵ E ^ ( h ) = 0 \widehat{E}(h)=0 E ( h ) = 0 1 − δ 1-\delta 1 − δ min h ∈ H E ( h ) \min _{h \in \mathcal{H}} E(h) min h ∈ H E ( h ) ϵ \epsilon ϵ h ∈ H h \in \mathcal{H} h ∈ H E ( h ) E(h) E ( h ) E ^ ( h ) \widehat{E}(h) E ( h ) m m m h h h
从式12.10到式12.14的公式是为了回答一个问题：到底需要多少样例才能学得目标概念c c c D D D L \mathcal{L} L 1 − δ 1-\delta 1 − δ ϵ \epsilon ϵ
12.3.1 式(12.10)的解释
P ( h ( x ) = y ) = 1 − P ( h ( x ) ≠ y ) P(h(\boldsymbol{x})=y) =1-P(h(\boldsymbol{x}) \neq y) P ( h ( x ) = y ) = 1 − P ( h ( x ) = y ) P ( h ( x ) ≠ y ) = E ( h ) P(h(x)\neq y)=E(h) P ( h ( x ) = y ) = E ( h ) E ( h ) > ϵ E(h)>\epsilon E ( h ) > ϵ 1 − E ( h ) < 1 − ϵ 1-E(h)<1-\epsilon 1 − E ( h ) < 1 − ϵ
12.3.2 式(12.11)的解释
先解释什么是h h h D D D h h h D D D ( h ( x 1 ) = y 1 ) ∧ … ∧ ( h ( x m ) = y m ) \left(h\left(\boldsymbol{x}_{1}\right)=y_{1}\right) \wedge \ldots \wedge\left(h\left(\boldsymbol{x}_{m}\right)=y_{m}\right) ( h ( x 1 ) = y 1 ) ∧ … ∧ ( h ( x m ) = y m ) P ( ( h ( x 1 ) = y 1 ) ∧ … ∧ ( h ( x m ) = y m ) ) = ∏ i = 1 m P ( h ( x i ) = y i ) 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) P ( ( h ( x 1 ) = y 1 ) ∧ … ∧ ( h ( x m ) = y m ) ) = ∏ i = 1 m P ( h ( x i ) = y i ) ∏ i = 1 m P ( h ( x i ) = y i ) = ∏ i = 1 m ( 1 − P ( h ( x i ) ≠ y i ) ) \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) ∏ i = 1 m P ( h ( x i ) = y i ) = ∏ i = 1 m ( 1 − P ( h ( x i ) = y i ) )
∏ i = 1 m ( 1 − P ( h ( x i ) ≠ y i ) ) < ∏ i = 1 m ( 1 − ϵ ) = ( 1 − ϵ ) m \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} i = 1 ∏ m ( 1 − P ( h ( x i ) = y i ) ) < i = 1 ∏ m ( 1 − ϵ ) = ( 1 − ϵ ) m 12.3.3 式(12.12)的推导
首先解释为什么"我们事先并不知道学习算法L \mathcal{L} L H \mathcal{H} H D D D h h h ϵ \epsilon ϵ P ( h ∈ H : E ( h ) > ϵ ∧ E ^ ( h ) = 0 ) P(h \in \mathcal{H}: E(h)>\epsilon \wedge \widehat{E}(h)=0) P ( h ∈ H : E ( h ) > ϵ ∧ E ( h ) = 0 ) h h h P ( E ( h ) > ϵ ∧ E ^ ( h ) = 0 ) < ( 1 − ϵ ) m P(E(h)>\epsilon \wedge \widehat{E}(h)=0)<\left(1-\epsilon \right)^m P ( E ( h ) > ϵ ∧ E ( h ) = 0 ) < ( 1 − ϵ ) m ∣ H ∣ \vert\mathcal{H}\vert ∣ H ∣ h h h h h h E ( h ) > ϵ E(h)>\epsilon E ( h ) > ϵ E ^ ( h ) = 0 \widehat{E}(h)=0 E ( h ) = 0 P ( h ∈ H : E ( h ) > ϵ ∧ E ^ ( h ) = 0 ) P(h \in \mathcal{H}: E(h)>\epsilon \wedge \widehat{E}(h)=0) P ( h ∈ H : E ( h ) > ϵ ∧ E ( h ) = 0 )
P ( h ∈ H : E ( h ) > ϵ ∧ E ^ ( h ) = 0 ) = ∑ i ∣ H ∣ P ( E ( h i ) > ϵ ∧ E ^ ( h i ) = 0 ) < ∣ H ∣ ( 1 − ϵ ) m \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} P ( h ∈ H : E ( h ) > ϵ ∧ E ( h ) = 0 ) = i ∑ ∣ H ∣ P ( E ( h i ) > ϵ ∧ E ( h i ) = 0 ) < ∣ H ∣ ( 1 − ϵ ) m 小于号依据公式(12.11)。
第二个小于号实际上是要证明∣ H ∣ ( 1 − ϵ ) m < ∣ H ∣ e − m ϵ \vert\mathcal{H}\vert(1-\epsilon)^m < \vert\mathcal{H}\vert e^{-m\epsilon} ∣ H ∣ ( 1 − ϵ ) m < ∣ H ∣ e − m ϵ ( 1 − ϵ ) m < e − m ϵ (1-\epsilon)^m < e^{-m\epsilon} ( 1 − ϵ ) m < e − m ϵ ϵ ∈ ( 0 , 1 ] \epsilon\in(0,1] ϵ ∈ ( 0 , 1 ] m m m
当ϵ = 1 \epsilon=1 ϵ = 1 ϵ ∈ ( 0 , 1 ) \epsilon\in(0, 1) ϵ ∈ ( 0 , 1 ) m ln ( 1 − ϵ ) < − m ϵ m\ln(1-\epsilon) < -m\epsilon m ln ( 1 − ϵ ) < − m ϵ ln ( 1 − ϵ ) < − ϵ \ln(1-\epsilon)<-\epsilon ln ( 1 − ϵ ) < − ϵ f ( ϵ ) = ln ( 1 − ϵ ) + ϵ f(\epsilon)=\ln(1-\epsilon) + \epsilon f ( ϵ ) = ln ( 1 − ϵ ) + ϵ ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 ) f ′ ( ϵ ) = 1 − 1 1 − ϵ = 0 ⇒ ϵ = 0 f^\prime(\epsilon)=1-\frac{1}{1-\epsilon}=0 \Rightarrow \epsilon=0 f ′ ( ϵ ) = 1 − 1 − ϵ 1 = 0 ⇒ ϵ = 0 l n ( 1 − ϵ ) < − ϵ ln(1-\epsilon)<-\epsilon l n ( 1 − ϵ ) < − ϵ ∣ H ∣ ( 1 − ϵ ) m < ∣ H ∣ e − m ϵ \vert\mathcal{H}\vert(1-\epsilon)^m < \vert\mathcal{H}\vert e^{-m\epsilon} ∣ H ∣ ( 1 − ϵ ) m < ∣ H ∣ e − m ϵ
12.3.4 式(12.13)的解释
回到我们要回答的问题：到底需要多少样例才能学得目标概念c c c D D D L \mathcal{L} L 1 − δ 1-\delta 1 − δ ϵ \epsilon ϵ L \mathcal{L} L ϵ \epsilon ϵ P ( h ∈ H : E ( h ) > ϵ ∧ E ^ ( h ) = 0 ) < ∣ H ∣ e − m ϵ P\left(h \in \mathcal{H}: E(h)>\epsilon \wedge \widehat{E}(h)=0\right)<\vert\mathcal{H}\vert e^{-m\epsilon} P ( h ∈ H : E ( h ) > ϵ ∧ E ( h ) = 0 ) < ∣ H ∣ e − m ϵ L \mathcal{L} L ϵ \epsilon ϵ 1 − P ( h ∈ H : E ( h ) > ϵ ∧ E ^ ( h ) = 0 ) ≥ 1 − ∣ H ∣ e − m ϵ 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 − P ( h ∈ H : E ( h ) > ϵ ∧ E ( h ) = 0 ) ≥ 1 − ∣ H ∣ e − m ϵ 1 − δ 1-\delta 1 − δ 1 − δ ⩽ 1 − ∣ H ∣ e − m ϵ ⇒ ∣ H ∣ e − m ϵ ⩽ δ 1-\delta\leqslant 1-\vert\mathcal{H}\vert e^{-m\epsilon}\Rightarrow\vert\mathcal{H}\vert e^{-m\epsilon}\leqslant\delta 1 − δ ⩽ 1 − ∣ H ∣ e − m ϵ ⇒ ∣ H ∣ e − m ϵ ⩽ δ
12.3.5 式(12.14)的推导
∣ H ∣ e − m ϵ ⩽ δ e − m ϵ ⩽ δ ∣ H ∣ − m ϵ ⩽ ln δ − ln ∣ H ∣ m ⩾ 1 ϵ ( ln ∣ H ∣ + ln 1 δ ) \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} ∣ H ∣ e − m ϵ e − m ϵ − m ϵ m ⩽ δ ⩽ ∣ H ∣ δ ⩽ ln δ − ln ∣ H ∣ ⩾ ϵ 1 ( ln ∣ H ∣ + ln δ 1 ) 这个式子告诉我们，在假设空间H \mathcal{H} H h h h ϵ \epsilon ϵ m m m O ( 1 m ) O(\frac{1}{m}) O ( m 1 )
12.3.6 引理12.1的解释
根据式(12.2),
E ^ ( h ) = 1 m ∑ i = 1 m I ( h ( x i ) ≠ y i ) \widehat{E}(h)=\frac{1}{m} \sum_{i=1}^m \mathbb{I}\left(h\left(\boldsymbol{x}_i\right) \neq y_i\right) E ( h ) = m 1 ∑ i = 1 m I ( h ( x i ) = y i ) I ( ⋅ ) \mathbb{I}(\cdot) I ( ⋅ ) 0 ≤ I ( h ( x i ) ≠ y i ) ≤ 1 0 \leq \mathbb{I}\left(h\left(\boldsymbol{x}_i\right) \neq y_i\right) \leq 1 0 ≤ I ( h ( x i ) = y i ) ≤ 1 E ( h ) E(h) E ( h ) I ( h ( x i ) ≠ y i ) \mathbb{I}\left(h\left(\boldsymbol{x}_i\right) \neq y_i\right) I ( h ( x i ) = y i ) E ( I ( h ( x i ) ≠ y i ) ) \mathbb{E}\left(\mathbb{I}\left(h\left(\boldsymbol{x}_i\right) \neq y_i\right)\right) E ( I ( h ( x i ) = y i ) ) h h h E ( h ) = 1 m ∑ i = 1 m E ( I ( h ( x i ) ≠ y i ) ) 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) E ( h ) = m 1 ∑ i = 1 m E ( I ( h ( x i ) = y i ) )
此时, 将 E ^ ( h ) \widehat{E}(h) E ( h ) E ( h ) E(h) E ( h )
12.3.7 式(12.18)的推导
令δ = 2 e − 2 m ϵ 2 \delta=2e^{-2m\epsilon^2} δ = 2 e − 2 m ϵ 2 ϵ = ln ( 2 / δ ) 2 m \epsilon=\sqrt{\frac{\ln(2/\delta)}{2m}} ϵ = 2 m l n ( 2/ δ )
P ( ∣ E ( h ) − E ^ ( h ) ∣ ⩾ ϵ ) ⩽ 2 exp ( − 2 m ϵ 2 ) P ( ∣ E ( h ) − E ^ ( h ) ∣ ⩾ ϵ ) ⩽ δ P ( ∣ E ( h ) − E ^ ( h ) ∣ ⩽ ϵ ) ⩾ 1 − δ P ( − ϵ ⩽ E ( h ) − E ^ ( h ) ⩽ ϵ ) ⩾ 1 − δ P ( E ^ ( h ) − ϵ ⩽ E ( h ) ⩽ E ^ ( h ) + ϵ ) ⩾ 1 − δ \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} P ( ∣ E ( h ) − E ( h ) ∣ ⩾ ϵ ) P ( ∣ E ( h ) − E ( h ) ∣ ⩾ ϵ ) P ( ∣ E ( h ) − E ( h ) ∣ ⩽ ϵ ) P ( − ϵ ⩽ E ( h ) − E ( h ) ⩽ ϵ ) P ( E ( h ) − ϵ ⩽ E ( h ) ⩽ E ( h ) + ϵ ) ⩽ 2 exp ( − 2 m ϵ 2 ) ⩽ δ ⩾ 1 − δ ⩾ 1 − δ ⩾ 1 − δ 带入 ϵ = ln ( 2 / δ ) 2 m \epsilon=\sqrt{\frac{\ln(2/\delta)}{2m}} ϵ = 2 m l n ( 2/ δ )
这个式子进一步阐明了当观测集样本数量足够大的时候，h h h
12.3.8 式(12.19)的推导
令h 1 , h 2 , … , h ∣ H ∣ h_1,h_2,\dots,h_{\vert\mathcal{H}\vert} h 1 , h 2 , … , h ∣ H ∣ H \mathcal{H} H
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{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} = ⩽ 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 ) ∣ > ϵ ) 这一步是很好理解的，存在一个假设h h h ∣ E ( h ) − E ^ ( h ) ∣ > ϵ |E(h)-\widehat{E}(h)|>\epsilon ∣ E ( h ) − E ( h ) ∣ > ϵ h i , i ∈ 1 , … , ∣ H ∣ h_i, i\in 1,\dots,\vert\mathcal{H}\vert h i , i ∈ 1 , … , ∣ H ∣ ∣ E h i − E ^ h i ∣ > ϵ \left|E_{h_{i}}-\widehat{E}_{h_{i}}\right|>\epsilon E h i − E h i > ϵ P ( A ∨ B ) = P ( A ) + P ( B ) − P ( A ∧ B ) P(A\vee B)=P(A) + P(B) - P(A\wedge B) P ( A ∨ B ) = P ( A ) + P ( B ) − P ( A ∧ B ) P ( A ∧ B ) ⩾ 0 P(A\wedge B)\geqslant 0 P ( A ∧ B ) ⩾ 0
由式12.17：
P ( ∣ E ( h ) − E ^ ( h ) ∣ ⩾ ϵ ) ⩽ 2 exp ( − 2 m ϵ 2 ) ⇒ ∑ h ∈ H P ( ∣ E ( h ) − E ^ ( h ) ∣ > ϵ ) ⩽ 2 ∣ H ∣ exp ( − 2 m ϵ 2 ) \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} P ( ∣ E ( h ) − E ( h ) ∣ ⩾ ϵ ) ⩽ 2 exp ( − 2 m ϵ 2 ) ⇒ h ∈ H ∑ P ( ∣ E ( h ) − E ( h ) ∣ > ϵ ) ⩽ 2∣ H ∣ exp ( − 2 m ϵ 2 ) 因此：
P ( ∃ h ∈ H : ∣ E ( h ) − E ^ ( h ) ∣ > ϵ ) ⩽ ∑ h ∈ H P ( ∣ E ( h ) − E ^ ( h ) ∣ > ϵ ) ⩽ 2 ∣ H ∣ exp ( − 2 m ϵ 2 ) \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} P ( ∃ h ∈ H : ∣ E ( h ) − E ( h ) ∣ > ϵ ) ⩽ h ∈ H ∑ P ( ∣ E ( h ) − E ( h ) ∣ > ϵ ) ⩽ 2∣ H ∣ exp ( − 2 m ϵ 2 ) 其对立事件：
P ( ∀ h ∈ H : ∣ E ( h ) − E ^ ( h ) ∣ ⩽ ϵ ) = 1 − P ( ∃ h ∈ H : ∣ E ( h ) − E ^ ( h ) ∣ > ϵ ) ⩾ 1 − 2 ∣ H ∣ exp ( − 2 m ϵ 2 ) \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} P ( ∀ h ∈ H : ∣ E ( h ) − E ( h ) ∣ ⩽ ϵ ) = 1 − P ( ∃ h ∈ H : ∣ E ( h ) − E ( h ) ∣ > ϵ ) ⩾ 1 − 2∣ H ∣ exp ( − 2 m ϵ 2 ) 令δ = 2 ∣ H ∣ e − 2 m ϵ 2 \delta=2\vert\mathcal{H}\vert e^{-2m\epsilon^2} δ = 2∣ H ∣ e − 2 m ϵ 2 ϵ = ln ∣ H ∣ + ln ( 2 / δ ) 2 m \epsilon=\sqrt{\frac{\ln |\mathcal{H}|+\ln (2 / \delta)}{2 m}} ϵ = 2 m l n ∣ H ∣ + l n ( 2/ δ )
P ( ∀ h ∈ H : ∣ E ( h ) − E ^ ( h ) ∣ ⩽ ln ∣ H ∣ + ln ( 2 / δ ) 2 m ) ⩾ 1 − δ 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 P ( ∀ h ∈ H : ∣ E ( h ) − E ( h ) ∣ ⩽ 2 m ln ∣ H ∣ + ln ( 2/ δ ) ) ⩾ 1 − δ 其中∀ h ∈ H \forall h\in\mathcal{H} ∀ h ∈ H
12.3.9 式(12.20)的解释
这个式子是"不可知PAC可学习"的定义式，不可知是指当目标概念c c c L \mathcal{L} L H \mathcal{H} H H \mathcal{H} H arg min h ∈ H E ( h ) \arg\min_{h\in \mathcal{H}}E(h) arg min h ∈ H E ( h ) ϵ \epsilon ϵ 1 − δ 1-\delta 1 − δ H \mathcal{H} H
12.4 VC维
不同于12.3节的有限假设空间，从本节开始，本章剩余内容均针对无限假设空间。
12.4.1 式(12.21)的解释
这个是增长函数的定义式。增长函数Π H ( m ) \Pi_{\mathcal{H}}(m) Π H ( m ) H \mathcal{H} H [ [ 0 , 0 ] , [ 0 , 1 ] , [ 1 , 0 ] , [ 1 , 1 ] ] [[0, 0], [0, 1], [1, 0], [1, 1]] [[ 0 , 0 ] , [ 0 , 1 ] , [ 1 , 0 ] , [ 1 , 1 ]] H 1 \mathcal{H}_1 H 1 [ [ 0 , 0 ] , [ 1 , 1 ] ] [[0, 0], [1, 1]] [[ 0 , 0 ] , [ 1 , 1 ]] Π H 1 ( 2 ) = 2 \Pi_{\mathcal{H}_1}(2)=2 Π H 1 ( 2 ) = 2 H \mathcal{H} H H \mathcal{H} H H \mathcal{H} H
12.4.2 式(12.22)的解释
值得指出的是，这个式子的前提假设有误，应当写成对假设空间H \mathcal{H} H m ∈ N m\in\mathbb{N} m ∈ N 0 < ϵ < 1 0<\epsilon<1 0 < ϵ < 1 h ∈ H h\in\mathcal{H} h ∈ H
Theorem 2 The probability that the relative frequency of at least one
event in class S S S ε \varepsilon ε l ≧ 2 / ε 2 l \geqq 2 / \varepsilon^2 l ≧ 2/ ε 2
P ( π ( l ) > ε ) ≦ 4 m S ( 2 l ) e − ε 2 l / 8 . \mathbf{P}\left(\pi^{(l)}>\varepsilon\right) \leqq 4 m^S(2 l) e^{-\varepsilon^2 l / 8} . P ( π ( l ) > ε ) ≦ 4 m S ( 2 l ) e − ε 2 l /8 . 注意定理描述中使用的是"at least one event in class S", 因此应该是 class
S 中"存在"one event 而不是 class S 中的 "任意" event。
另外, 该定理为基于增长函数对无限假设空间的泛化误差分析,
与上一节有限假设空间 的定理 12.1。在证明定理 12.1 12.1 12.1
P ( ∃ h ∈ H : ∣ E ( h ) − E ^ ( h ) ∣ > ϵ ) ⩽ 2 ∣ H ∣ e − 2 m ϵ 2 P(\exists h \in \mathcal{H}:|E(h)-\widehat{E}(h)|>\epsilon) \leqslant 2|\mathcal{H}| e^{-2 m \epsilon^2} P ( ∃ h ∈ H : ∣ E ( h ) − E ( h ) ∣ > ϵ ) ⩽ 2∣ H ∣ e − 2 m ϵ 2 根据该结论可得式(12.19)的原型（式(12.19)就是将 ϵ \epsilon ϵ δ \delta δ
P ( ∀ h ∈ H : ∣ E ( h ) − E ^ ( h ) ∣ ⩽ ϵ ) ⩽ 1 − 2 ∣ H ∣ e − 2 m ϵ 2 P(\forall h \in \mathcal{H}:|E(h)-\widehat{E}(h)| \leqslant \epsilon) \leqslant 1-2|\mathcal{H}| e^{-2 m \epsilon^2} P ( ∀ h ∈ H : ∣ E ( h ) − E ( h ) ∣ ⩽ ϵ ) ⩽ 1 − 2∣ H ∣ e − 2 m ϵ 2 这是因为事件 ∃ h ∈ H : ∣ E ( h ) − E ^ ( h ) ∣ > ϵ \exists h \in \mathcal{H}:|E(h)-\widehat{E}(h)|>\epsilon ∃ h ∈ H : ∣ E ( h ) − E ( h ) ∣ > ϵ ∀ h ∈ H : ∣ E ( h ) − E ^ ( h ) ∣ ⩽ ϵ \forall h \in \mathcal{H}:|E(h)-\widehat{E}(h)| \leqslant \epsilon ∀ h ∈ H : ∣ E ( h ) − E ( h ) ∣ ⩽ ϵ
注意到当使用 ∣ E ( h ) − E ^ ( h ) ∣ > ϵ |E(h)-\widehat{E}(h)|>\epsilon ∣ E ( h ) − E ( h ) ∣ > ϵ ∣ E ( h ) − E ^ ( h ) ∣ ⩽ ϵ |E(h)-\widehat{E}(h)| \leqslant \epsilon ∣ E ( h ) − E ( h ) ∣ ⩽ ϵ
综上所述, 式(12.22)使用 ∣ E ( h ) − E ^ ( h ) ∣ > ϵ |E(h)-\widehat{E}(h)|>\epsilon ∣ E ( h ) − E ( h ) ∣ > ϵ
12.4.3 式(12.23)的解释
这是VC维的定义式：VC维的定义是能被H \mathcal{H} H
式(12.23)中的 { m : Π H ( m ) = 2 m } \left\{m: \Pi_{\mathcal{H}}(m)=2^m\right\} { m : Π H ( m ) = 2 m } Π H ( m ) = 2 m \Pi_{\mathcal{H}}(m)=2^m Π H ( m ) = 2 m m m m n n n n n n
V C \mathrm{VC} VC d d d H \mathcal{H} H d d d 12.2 12.2 12.2
12.4.4 引理12.2的解释
首先解释下数学归纳法的起始条件"当m = 1 , d = 0 m=1, d=0 m = 1 , d = 0 d = 1 d=1 d = 1 m = 1 , d = 0 m=1,d=0 m = 1 , d = 0 V C ( H ) = max { m : Π H ( m ) = 2 m } = 0 \mathrm{VC}(\mathcal{H})=\max \left\{m: \Pi_{\mathcal{H}}(m)=2^{m}\right\}=0 VC ( H ) = max { m : Π H ( m ) = 2 m } = 0 Π H ( 1 ) < 2 \Pi_{\mathcal{H}}(1)<2 Π H ( 1 ) < 2 d d d Π H ( m ) \Pi_{\mathcal{H}}(m) Π H ( m ) Π H ( 1 ) ∈ [ 0 , 1 ] \Pi_{\mathcal{H}}(1)\in[0, 1] Π H ( 1 ) ∈ [ 0 , 1 ] ∑ i = 0 0 ( 1 i ) = 1 \sum_{i=0}^{0}\left(\begin{array}{c}{1} \\ {i}\end{array}\right)=1 ∑ i = 0 0 ( 1 i ) = 1 m = 1 , d = 1 m=1,d=1 m = 1 , d = 1 Π H ( 1 ) = 2 \Pi_\mathcal{H}(1)=2 Π H ( 1 ) = 2 ∑ i = 0 1 ( 1 i ) = 2 \sum_{i=0}^{1}\left(\begin{array}{c}{1} \\ {i}\end{array}\right)=2 ∑ i = 0 1 ( 1 i ) = 2
再介绍归纳过程，这里采样的归纳方法是假设式(12.24)对( m − 1 , d − 1 ) (m-1, d-1) ( m − 1 , d − 1 ) ( m − 1 , d ) (m-1, d) ( m − 1 , d ) ( m , d ) (m,d) ( m , d ) D = { x 1 , x 2 , … , x m } D=\left\{\boldsymbol{x}_{1}, \boldsymbol{x}_{2}, \ldots, \boldsymbol{x}_{m}\right\} D = { x 1 , x 2 , … , x m } D ′ = { x 1 , x 2 , … , x m − 1 } D^\prime=\left\{\boldsymbol{x}_{1}, \boldsymbol{x}_{2}, \ldots, \boldsymbol{x}_{m-1}\right\} D ′ = { x 1 , x 2 , … , x m − 1 } D D D D ′ D^\prime D ′ x m x_m x m
H ∣ D = { ( h ( x 1 ) , h ( x 2 ) , … , h ( x m ) ) ∣ h ∈ H } H ∣ D ′ = { ( h ( x 1 ) , h ( x 2 ) , … , h ( x m − 1 ) ) ∣ h ∈ H } \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 ∣ D = { ( h ( x 1 ) , h ( x 2 ) , … , h ( x m ) ) ∣ h ∈ H } H ∣ D ′ = { ( h ( x 1 ) , h ( x 2 ) , … , h ( x m − 1 ) ) ∣ h ∈ H } 如果假设h ∈ H h\in\mathcal{H} h ∈ H x m x_m x m + 1 +1 + 1 − 1 -1 − 1 H ∣ D ′ \mathcal{H}_{\vert D^\prime} H ∣ D ′ H ∣ D \mathcal{H}_{\vert D} H ∣ D m = 3 m=3 m = 3
H ∣ D = { ( + , − , − ) , ( + , + , − ) , ( + , + , + ) , ( − , + , − ) , ( − , − , + ) } H ∣ D ′ = { ( + , + ) , ( + , − ) , ( − , + ) , ( − , − ) } \begin{aligned}
\mathcal{H}_{\vert D}&=\{(+,-,-),(+,+,-),(+,+,+),(-,+,-),(-,-,+)\}\\
\mathcal{H}_{\vert D^\prime}&=\{(+,+),(+,-),(-,+),(-,-)\}\\
\end{aligned} H ∣ D H ∣ D ′ = {( + , − , − ) , ( + , + , − ) , ( + , + , + ) , ( − , + , − ) , ( − , − , + )} = {( + , + ) , ( + , − ) , ( − , + ) , ( − , − )} 其中串( + , + ) (+,+) ( + , + ) H ∣ D \mathcal{H}_{\vert D} H ∣ D ( + , + , + ) , ( + , + , − ) (+, +, +), (+, +, -) ( + , + , + ) , ( + , + , − ) H ∣ D ′ \mathcal{H}_{\vert D^\prime} H ∣ D ′ ( + , − ) , ( − , + ) , ( − , − ) (+,-), (-, +), (-, -) ( + , − ) , ( − , + ) , ( − , − ) H ∣ D \mathcal{H}_{\vert D} H ∣ D x m x_m x m + + + − - − h h h x m x_m x m H D ′ ∣ D \mathcal{H}_{D^\prime\vert D} H D ′ ∣ D H ∣ D \mathcal{H}_{\vert D} H ∣ D H ∣ D ′ \mathcal{H}_{\vert D^\prime} H ∣ D ′ H D ′ ∣ D = { ( + , + ) } \mathcal{H}_{D^\prime\vert D}=\{(+,+)\} H D ′ ∣ D = {( + , + )}
∣ H ∣ D ∣ = ∣ H ∣ D ′ ∣ + ∣ H D ′ ∣ D ∣ \left|\mathcal{H}_{| D}\right|=\left|\mathcal{H}_{| D^{\prime}}\right|+\left|\mathcal{H}_{D^{\prime} | D}\right| H ∣ D = H ∣ D ′ + H D ′ ∣ D 由于H ∣ D ′ \mathcal{H}_{\vert D^\prime} H ∣ D ′ D ′ D^\prime D ′ H \mathcal{H} H D ′ D^\prime D ′ D ′ D^\prime D ′ m − 1 m-1 m − 1 H \mathcal{H} H m − 1 m-1 m − 1 Π H ( m − 1 ) \Pi_{\mathcal{H}}(m-1) Π H ( m − 1 ) ∣ H ∣ D ′ ∣ ⩽ Π H ( m − 1 ) \vert\mathcal{H}_{\vert D^\prime}\vert \leqslant \Pi_\mathcal{H}(m-1) ∣ H ∣ D ′ ∣ ⩽ Π H ( m − 1 )
∣ H ∣ D ′ ∣ ⩽ Π H ( m − 1 ) ⩽ ∑ i = 0 d ( m − 1 i ) \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) H ∣ D ′ ⩽ Π H ( m − 1 ) ⩽ i = 0 ∑ d ( m − 1 i ) 由记号H ∣ D ′ \mathcal{H}_{\vert D^\prime} H ∣ D ′ ∣ H ∣ D ′ ∣ ⩾ ⌊ ∣ H ∣ D ∣ 2 ⌋ \vert\mathcal{H}_{\vert D^\prime}\vert \geqslant \left\lfloor\frac{\vert\mathcal{H}_{\vert D}\vert}{2}\right\rfloor ∣ H ∣ D ′ ∣ ⩾ ⌊ 2 ∣ H ∣ D ∣ ⌋ ∣ H ∣ D ′ ∣ \vert\mathcal{H}_{\vert D^\prime}\vert ∣ H ∣ D ′ ∣ ∣ H D ′ ∣ D ∣ \vert\mathcal{H}_{D^\prime\vert D}\vert ∣ H D ′ ∣ D ∣ ∣ H D ′ ∣ D ∣ ⩽ ⌊ ∣ H ∣ D ∣ 2 ⌋ \vert\mathcal{H}_{D^\prime\vert D}\vert \leqslant \left\lfloor\frac{\vert\mathcal{H}_{\vert D}\vert}{2}\right\rfloor ∣ H D ′ ∣ D ∣ ⩽ ⌊ 2 ∣ H ∣ D ∣ ⌋ D D D m m m ∣ H D ′ ∣ D ∣ ⩽ ⌊ ∣ H ∣ D ∣ 2 ⌋ ⩽ Π H ( m − 1 ) \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) H D ′ ∣ D ⩽ ⌊ 2 ∣ H ∣ D ∣ ⌋ ⩽ Π H ( m − 1 ) Q Q Q H D ′ ∣ D \mathcal{H}_{D^\prime\vert D} H D ′ ∣ D H D ′ ∣ D \mathcal{H}_{D^\prime\vert D} H D ′ ∣ D H D H_{D} H D x m x_m x m Q ∪ { x m } Q \cup\left\{\boldsymbol{x}_{m}\right\} Q ∪ { x m } H ∣ D \mathcal{H}_{\vert D} H ∣ D H \mathcal{H} H d d d H D ′ ∣ D \mathcal{H}_{D^\prime\vert D} H D ′ ∣ D d − 1 d-1 d − 1
∣ H D ′ ∣ D ∣ ⩽ Π H ( m − 1 ) ⩽ ∑ i = 0 d − 1 ( m − 1 i ) \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) H D ′ ∣ D ⩽ Π H ( m − 1 ) ⩽ i = 0 ∑ d − 1 ( m − 1 i ) 因此：
∣ H ∣ D ∣ = ∣ H ∣ D ′ ∣ + ∣ H D ′ ∣ D ∣ ⩽ ∑ i = 0 d ( m − 1 i ) + ∑ i = 0 d + 1 ( m − 1 i ) = ∑ i = 0 d ( ( m − 1 i ) + ( m − 1 i − 1 ) ) = ∑ i = 0 d ( m i ) \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} H ∣ D = H ∣ D ′ + H D ′ ∣ D ⩽ i = 0 ∑ d ( m − 1 i ) + i = 0 ∑ d + 1 ( m − 1 i ) = i = 0 ∑ d ( ( m − 1 i ) + ( m − 1 i − 1 ) ) = i = 0 ∑ d ( m i ) 注：最后一步依据组合公式，推导如下：
( m − 1 i ) + ( m − 1 i − 1 ) = ( m − 1 ) ! ( m − 1 − i ) ! i ! + ( m − 1 ) ! ( m − 1 − i + 1 ) ! ( i − 1 ) ! = ( m − 1 ) ! ( m − i ) ( m − i ) ( m − 1 − i ) ! i ! + ( m − 1 ) ! i ( m − i ) ! ( i − 1 ) ! i = ( m − 1 ) ! ( m − i ) + ( m − 1 ) ! i ( m − i ) ! i ! = ( m − 1 ) ! ( m − i + i ) ( m − i ) ! i ! = ( m − 1 ) ! m ( m − i ) ! i ! = m ! ( m − i ) ! i ! = ( m i ) \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} ( m − 1 i ) + ( m − 1 i − 1 ) = ( m − 1 − i )! i ! ( m − 1 )! + ( m − 1 − i + 1 )! ( i − 1 )! ( m − 1 )! = ( m − i ) ( m − 1 − i )! i ! ( m − 1 )! ( m − i ) + ( m − i )! ( i − 1 )! i ( m − 1 )! i = ( m − i )! i ! ( m − 1 )! ( m − i ) + ( m − 1 )! i = ( m − i )! i ! ( m − 1 )! ( m − i + i ) = ( m − i )! i ! ( m − 1 )! m = ( m − i )! i ! m ! = ( m i ) 12.4.5 式(12.28)的解释
Π H ( m ) ⩽ ∑ i = 0 d ( m i ) ⩽ ∑ i = 0 d ( m i ) ( m d ) d − i = ( m d ) d ∑ i = 0 d ( m i ) ( d m ) i ⩽ ( m d ) d ∑ i = 0 m ( m i ) ( d m ) i = ( m d ) d ( 1 + d m ) m < ( e ⋅ m d ) d \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} Π H ( m ) ⩽ i = 0 ∑ d ( m i ) ⩽ i = 0 ∑ d ( m i ) ( d m ) d − i = ( d m ) d i = 0 ∑ d ( m i ) ( m d ) i ⩽ ( d m ) d i = 0 ∑ m ( m i ) ( m d ) i = ( d m ) d ( 1 + m d ) m < ( d e ⋅ m ) d 第一步到第二步和第三步到第四步均因为m ⩾ d m\geqslant d m ⩾ d ( x + y ) n = ∑ k = 0 n ( n k ) x n − k y k (x+y)^{n}=\sum_{k=0}^{n}\left(\begin{array}{l}{n} \\ {k}\end{array}\right) x^{n-k} y^{k} ( x + y ) n = ∑ k = 0 n ( n k ) x n − k y k k = i , n = m , x = 1 , y = d m k=i, n=m, x=1, y = \frac{d}{m} k = i , n = m , x = 1 , y = m d ( m d ) d ∑ i = 0 m ( m i ) ( d m ) i = ( m d ) d ( 1 + d m ) 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 ( d m ) d ∑ i = 0 m ( m i ) ( m d ) i = ( d m ) d ( 1 + m d ) m ( 1 + d m ) m ⩽ e d {\left(1+\frac{d}{m}\right)}^m\leqslant e^d ( 1 + m d ) m ⩽ e d ( 1 + d m ) m = ( 1 + d m ) m d d {\left(1+\frac{d}{m}\right)}^m={\left(1+\frac{d}{m}\right)}^{\frac{m}{d}d} ( 1 + m d ) m = ( 1 + m d ) d m d e e e ( 1 + d m ) m d d < e d {\left(1+\frac{d}{m}\right)}^{\frac{m}{d}d}< e^d ( 1 + m d ) d m d < e d ⩽ \leqslant ⩽ e = lim d m → 0 ( 1 + d m ) m d e=\lim _{\frac{d}{m} \rightarrow 0}\left(1+\frac{d}{m}\right)^{\frac{m}{d}} e = lim m d → 0 ( 1 + m d ) d m < < <
12.4.6 式(12.29)的解释
这里应该是作者的笔误，根据式12.22，E ( h ) − E ^ ( h ) E(h)-\widehat{E}(h) E ( h ) − E ( h )
P ( ∣ E ( h ) − E ^ ( h ) ∣ > ϵ ) ⩽ 4 ( 2 e m d ) d exp ( − m ϵ 2 8 ) 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) P ( ∣ E ( h ) − E ( h ) ∣ > ϵ ) ⩽ 4 ( d 2 e m ) d exp ( − 8 m ϵ 2 ) 令4 ( 2 e m d ) d exp ( − m ϵ 2 8 ) = δ 4{\left(\frac{2em}{d}\right)}^d\exp\left(-\frac{m\epsilon^2}{8}\right)=\delta 4 ( d 2 e m ) d exp ( − 8 m ϵ 2 ) = δ
δ = 8 d ln 2 e m d + 8 ln 4 δ m \delta=\sqrt{
\frac{8d\ln\frac{2em}{d}+8\ln\frac{4}{\delta}}{m}
} δ = m 8 d ln d 2 e m + 8 ln δ 4 带入式12.22，则定理得证。这个式子是用VC维表示泛化界，可以看出，泛化误差界只与样本数量m m m ln m m \sqrt{\frac{\ln m}{m}} m l n m 1 m \frac{1}{\sqrt{m}} m 1
12.4.7 式(12.30)的解释
这个是经验风险最小化的定义式。即从假设空间中找出能使经验风险最小的假设。
12.4.8 定理12.4的解释
首先回忆PAC可学习的概念，见定义12.2，而可知/不可知PAC可学习之间的区别仅仅在于概念类c c c H \mathcal{H} H
δ ′ = δ 2 ( ln 2 / δ ′ ) 2 m = ϵ 2 \begin{aligned}
\delta^\prime = \frac{\delta}{2} \\
\sqrt{\frac{\left(\ln 2 / \delta^{\prime}\right)}{2 m}}=\frac{\epsilon}{2}
\end{aligned} δ ′ = 2 δ 2 m ( ln 2/ δ ′ ) = 2 ϵ 结合这两个标记的转换，由推论12.1可知：
E ^ ( g ) − ϵ 2 ⩽ E ( g ) ⩽ E ^ ( g ) + ϵ 2 \widehat{E}(g)-\frac{\epsilon}{2} \leqslant E(g) \leqslant \widehat{E}(g)+\frac{\epsilon}{2} E ( g ) − 2 ϵ ⩽ E ( g ) ⩽ E ( g ) + 2 ϵ 至少以1 − δ / 2 1-\delta/2 1 − δ /2
P ( ∣ E ( g ) − E ^ ( g ) ∣ ⩽ ϵ 2 ) ⩾ 1 − δ / 2 P\left(|E(g)-\widehat{E}(g)| \leqslant \frac{\epsilon}{2}\right) \geqslant 1-\delta / 2 P ( ∣ E ( g ) − E ( g ) ∣ ⩽ 2 ϵ ) ⩾ 1 − δ /2 即P ( ( E ( g ) − E ^ ( g ) ⩽ ϵ 2 ) ∧ ( E ( g ) − E ^ ( g ) ⩾ − ϵ 2 ) ) ⩾ 1 − δ / 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 ( ( E ( g ) − E ( g ) ⩽ 2 ϵ ) ∧ ( E ( g ) − E ( g ) ⩾ − 2 ϵ ) ) ⩾ 1 − δ /2 P ( E ( g ) − E ^ ( g ) ⩽ ϵ 2 ) ⩾ 1 − δ / 2 P\left(E(g)-\widehat{E}(g) \leqslant \frac{\epsilon}{2}\right) \geqslant 1-\delta / 2 P ( E ( g ) − E ( g ) ⩽ 2 ϵ ) ⩾ 1 − δ /2 P ( E ( g ) − E ^ ( g ) ⩾ − ϵ 2 ) ⩾ 1 − δ / 2 P\left(E(g)-\widehat{E}(g) \geqslant -\frac{\epsilon}{2}\right) \geqslant 1-\delta / 2 P ( E ( g ) − E ( g ) ⩾ − 2 ϵ ) ⩾ 1 − δ /2
8 d ln 2 e m d + 8 ln 4 δ ′ m = ϵ 2 \sqrt{\frac{8 d \ln \frac{2 e m}{d}+8 \ln \frac{4}{\delta^{\prime}}}{m}}=\frac{\epsilon}{2} m 8 d ln d 2 e m + 8 ln δ ′ 4 = 2 ϵ 由式12.29可知
P ( ∣ E ( h ) − E ^ ( h ) ∣ ⩽ ϵ 2 ) ⩾ 1 − δ 2 P\left(\left\vert
E(h)-\widehat{E}(h) \right\vert\leqslant \frac{\epsilon}{2}
\right)
\geqslant 1-\frac{\delta}{2} P ( E ( h ) − E ( h ) ⩽ 2 ϵ ) ⩾ 1 − 2 δ 同理，P ( E ( h ) − E ^ ( h ) ⩽ ϵ 2 ) ⩾ 1 − δ / 2 P\left(E(h)-\widehat{E}(h) \leqslant \frac{\epsilon}{2}\right) \geqslant 1-\delta / 2 P ( E ( h ) − E ( h ) ⩽ 2 ϵ ) ⩾ 1 − δ /2 P ( E ( h ) − E ^ ( h ) ⩾ − ϵ 2 ) ⩾ 1 − δ / 2 P\left(E(h)-\widehat{E}(h) \geqslant -\frac{\epsilon}{2}\right) \geqslant 1-\delta / 2 P ( E ( h ) − E ( h ) ⩾ − 2 ϵ ) ⩾ 1 − δ /2 P ( E ( g ) − E ^ ( g ) ⩾ − ϵ 2 ) ⩾ 1 − δ / 2 P\left(E(g)-\widehat{E}(g) \geqslant - \frac{\epsilon}{2}\right) \geqslant 1-\delta / 2 P ( E ( g ) − E ( g ) ⩾ − 2 ϵ ) ⩾ 1 − δ /2 P ( E ( h ) − E ^ ( h ) ⩽ ϵ 2 ) ⩾ 1 − δ / 2 P\left(E(h)-\widehat{E}(h) \leqslant \frac{\epsilon}{2}\right) \geqslant 1-\delta / 2 P ( E ( h ) − E ( h ) ⩽ 2 ϵ ) ⩾ 1 − δ /2 E ( g ) − E ^ ( g ) ⩾ − ϵ 2 E(g)-\widehat{E}(g) \geqslant -\frac{\epsilon}{2} E ( g ) − E ( g ) ⩾ − 2 ϵ E ( h ) − E ^ ( h ) ⩽ ϵ 2 E(h)-\widehat{E}(h) \leqslant \frac{\epsilon}{2} E ( h ) − E ( h ) ⩽ 2 ϵ
P ( ( E ( g ) − E ^ ( g ) ⩾ − ϵ 2 ) ∧ ( E ( h ) − E ^ ( h ) ⩽ ϵ 2 ) ) = P ( E ( g ) − E ^ ( g ) ⩾ − ϵ 2 ) + P ( E ( h ) − E ^ ( h ) ⩽ ϵ 2 ) − P ( ( E ( g ) − E ^ ( g ) ⩾ − ϵ 2 ) ∨ ( E ( h ) − E ^ ( h ) ⩽ ϵ 2 ) ) ⩾ 1 − δ / 2 + 1 − δ / 2 − 1 = 1 − δ \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 ( ( E ( g ) − E ( g ) ⩾ − 2 ϵ ) ∧ ( E ( h ) − E ( h ) ⩽ 2 ϵ ) ) P ( E ( g ) − E ( g ) ⩾ − 2 ϵ ) + P ( E ( h ) − E ( h ) ⩽ 2 ϵ ) − P ( ( E ( g ) − E ( g ) ⩾ − 2 ϵ ) ∨ ( E ( h ) − E ( h ) ⩽ 2 ϵ ) ) 1 − δ /2 + 1 − δ /2 − 1 1 − δ 即
P ( ( E ( g ) − E ^ ( g ) ⩾ − ϵ 2 ) ∧ ( E ( h ) − E ^ ( h ) ⩽ ϵ 2 ) ) ⩾ 1 − δ 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 ( ( E ( g ) − E ( g ) ⩾ − 2 ϵ ) ∧ ( E ( h ) − E ( h ) ⩽ 2 ϵ ) ) ⩾ 1 − δ 因此
P ( E ^ ( g ) − E ( g ) + E ( h ) − E ^ ( h ) ⩽ ϵ 2 + ϵ 2 ) = P ( E ( h ) − E ( g ) ⩽ E ^ ( h ) − E ^ ( g ) + ϵ ) ⩾ 1 − δ 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 P ( E ( g ) − E ( g ) + E ( h ) − E ( h ) ⩽ 2 ϵ + 2 ϵ ) = P ( E ( h ) − E ( g ) ⩽ E ( h ) − E ( g ) + ϵ ) ⩾ 1 − δ 再由h h h g g g h h h g g g D D D E ^ ( h ) ⩽ E ^ ( g ) \widehat{E}(h)\leqslant\widehat{E}(g) E ( h ) ⩽ E ( g )
P ( E ( h ) − E ( g ) ⩽ ϵ ) ⩾ 1 − δ P\left(E(h)-E(g)\leqslant\epsilon\right)
\geqslant 1 - \delta P ( E ( h ) − E ( g ) ⩽ ϵ ) ⩾ 1 − δ 根据式12.32和式12.34，可以求出m m m ( 1 / ϵ , 1 / δ , size ( x ) , size ( c ) ) \left(1/\epsilon,1/\delta,\text{size}(x),\text{size}(c)\right) ( 1/ ϵ , 1/ δ , size ( x ) , size ( c ) ) H \mathcal{H} H
12.5 Rademacher复杂度
上一节中介绍的基于VC维的泛化误差界是分布无关、数据独立的，本节将要介绍的Rademacher复杂度则在一定程度上考虑了数据分布。
12.5.1 式(12.36)的解释
这里解释从第一步到第二步的推导，因为前提假设是2分类问题，y k ∈ { − 1 , + 1 } y_k\in\{-1, +1\} y k ∈ { − 1 , + 1 } I ( h ( x i ) ≠ y i ) ≡ 1 − y i h ( x i ) 2 \mathbb{I}\left(h(x_i)\neq y_i\right)\equiv \frac{1-y_i h(x_i)}{2} I ( h ( x i ) = y i ) ≡ 2 1 − y i h ( x i ) y i = + 1 , h ( x i ) = + 1 y_i=+1, h(x_i)=+1 y i = + 1 , h ( x i ) = + 1 y i = − 1 , h ( x i ) = − 1 y_i=-1, h(x_i)=-1 y i = − 1 , h ( x i ) = − 1 I ( h ( x i ) ≠ y i ) = 0 = 1 − y i h ( x i ) 2 \mathbb{I}\left(h(x_i)\neq y_i\right)=0= \frac{1-y_i h(x_i)}{2} I ( h ( x i ) = y i ) = 0 = 2 1 − y i h ( x i ) y i = − 1 , h ( x i ) = + 1 y_i=-1, h(x_i)=+1 y i = − 1 , h ( x i ) = + 1 y i = + 1 , h ( x i ) = − 1 y_i=+1, h(x_i)=-1 y i = + 1 , h ( x i ) = − 1 I ( h ( x i ) ≠ y i ) = 1 = 1 − y i h ( x i ) 2 \mathbb{I}\left(h(x_i)\neq y_i\right)=1= \frac{1-y_i h(x_i)}{2} I ( h ( x i ) = y i ) = 1 = 2 1 − y i h ( x i )
12.5.2 式(12.37)的解释
由公式12.36可知，经验误差E ^ ( h ) \widehat{E}(h) E ( h ) 1 m ∑ i = 1 m y i h ( x i ) \frac{1}{m} \sum_{i=1}^{m} y_{i} h\left(\boldsymbol{x}_{i}\right) m 1 ∑ i = 1 m y i h ( x i ) h h h 1 m ∑ i = 1 m y i h ( x i ) \frac{1}{m} \sum_{i=1}^{m} y_{i} h\left(\boldsymbol{x}_{i}\right) m 1 ∑ i = 1 m y i h ( x i ) h h h
12.5.3 式(12.38)的解释
上确界sup \sup sup y i y_i y i σ i , arg max h ∈ H \sigma_i, \arg \max _{h \in \mathcal{H}} σ i , arg max h ∈ H sup h ∈ H ∘ \sup _{h \in \mathcal{H}^{\circ}} sup h ∈ H ∘ D = { x 1 , x 2 , … , x m } D=\left\{\boldsymbol{x}_1, \boldsymbol{x}_2, \ldots, \boldsymbol{x}_m\right\} D = { x 1 , x 2 , … , x m } H \mathcal{H} H { h ( x 1 ) , h ( x 2 ) , … , h ( x m ) } \left\{h\left(\boldsymbol{x}_1\right), h\left(\boldsymbol{x}_2\right), \ldots, h\left(\boldsymbol{x}_m\right)\right\} { h ( x 1 ) , h ( x 2 ) , … , h ( x m ) } σ = { σ 1 , σ 2 , … , σ m } \boldsymbol{\sigma}=\left\{\sigma_1, \sigma_2, \ldots, \sigma_m\right\} σ = { σ 1 , σ 2 , … , σ m } 1 m ∑ i = 1 m σ i h ( x i ) \frac{1}{m} \sum_{i=1}^m \sigma_i h\left(\boldsymbol{x}_i\right) m 1 ∑ i = 1 m σ i h ( x i ) σ = { σ 1 , σ 2 , … , σ m } \boldsymbol{\sigma}=\left\{\sigma_1, \sigma_2, \ldots, \sigma_m\right\} σ = { σ 1 , σ 2 , … , σ m } { h ( x 1 ) , h ( x 2 ) , … , h ( x m ) } \left\{h\left(\boldsymbol{x}_1\right), h\left(\boldsymbol{x}_2\right), \ldots, h\left(\boldsymbol{x}_m\right)\right\} { h ( x 1 ) , h ( x 2 ) , … , h ( x m ) } h ∈ H h \in \mathcal{H} h ∈ H 1 m ∑ i = 1 m σ i h ( x i ) \frac{1}{m} \sum_{i=1}^m \sigma_i h\left(\boldsymbol{x}_i\right) m 1 ∑ i = 1 m σ i h ( x i ) σ \sigma σ h h h
进一步地,
sup h ∈ H 1 m ∑ i = 1 m σ i h ( x i ) \sup _{h \in \mathcal{H}} \frac{1}{m} \sum_{i=1}^m \sigma_i h\left(\boldsymbol{x}_i\right) sup h ∈ H m 1 ∑ i = 1 m σ i h ( x i ) σ = { σ 1 , σ 2 , … , σ m } \boldsymbol{\sigma}=\left\{\sigma_1, \sigma_2, \ldots, \sigma_m\right\} σ = { σ 1 , σ 2 , … , σ m } H \mathcal{H} H σ \sigma σ h h h
例如, σ = { − 1 , + 1 , − 1 , + 1 } \boldsymbol{\sigma}=\{-1,+1,-1,+1\} σ = { − 1 , + 1 , − 1 , + 1 } m = 4 m=4 m = 4 σ \boldsymbol{\sigma} σ H = { h 1 , h 2 , h 3 } \mathcal{H}=\left\{h_1, h_2, h_3\right\} H = { h 1 , h 2 , h 3 }
{ h 1 ( x 1 ) , h 1 ( x 2 ) , h 1 ( x 3 ) , h 1 ( x 4 ) } = { − 1 , − 1 , − 1 , − 1 } { h 2 ( x 1 ) , h 2 ( x 2 ) , h 2 ( x 3 ) , h 2 ( x 4 ) } = { − 1 , + 1 , − 1 , − 1 } { h 3 ( x 1 ) , h 3 ( x 2 ) , h 3 ( x 3 ) , h 3 ( x 4 ) } = { + 1 , + 1 , + 1 , + 1 } \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} { h 1 ( x 1 ) , h 1 ( x 2 ) , h 1 ( x 3 ) , h 1 ( x 4 ) } = { − 1 , − 1 , − 1 , − 1 } { h 2 ( x 1 ) , h 2 ( x 2 ) , h 2 ( x 3 ) , h 2 ( x 4 ) } = { − 1 , + 1 , − 1 , − 1 } { h 3 ( x 1 ) , h 3 ( x 2 ) , h 3 ( x 3 ) , h 3 ( x 4 ) } = { + 1 , + 1 , + 1 , + 1 } 易知
1 m ∑ i = 1 m σ i h 1 ( x i ) = 0 , 1 m ∑ i = 1 m σ i h 2 ( x i ) = 2 4 , 1 m ∑ i = 1 m σ i h 3 ( x i ) = 0 \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 m 1 ∑ i = 1 m σ i h 1 ( x i ) = 0 , m 1 ∑ i = 1 m σ i h 2 ( x i ) = 4 2 , m 1 ∑ i = 1 m σ i h 3 ( x i ) = 0
sup h ∈ H 1 m ∑ i = 1 m σ i h ( x i ) = 2 4 \sup _{h \in \mathcal{H}} \frac{1}{m} \sum_{i=1}^m \sigma_i h\left(\boldsymbol{x}_i\right)=\frac{2}{4} h ∈ H sup m 1 i = 1 ∑ m σ i h ( x i ) = 4 2 12.5.4 式(12.39)的解释
E σ [ sup h ∈ H 1 m ∑ i = 1 m σ i h ( x i ) ] \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] E σ [ h ∈ H sup m 1 i = 1 ∑ m σ i h ( x i ) ] [解析]：这个式子可以用来衡量假设空间H \mathcal{H} H σ \sigma σ σ \sigma σ H \mathcal{H} H h h h σ i \sigma_i σ i 2 m 2^m 2 m σ i \sigma_i σ i D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x m , y m ) } D=\{(x_1, y_1), (x_2, y_2),\dots, (x_m, y_m)\} D = {( x 1 , y 1 ) , ( x 2 , y 2 ) , … , ( x m , y m )} σ i \sigma_i σ i h h h h ( x i ) h(x_i) h ( x i ) σ i \sigma_i σ i σ i \sigma_i σ i
12.5.5 式(12.40)的解释
对比式12.39，这里使用函数空间F \mathcal{F} F H \mathcal{H} H f f f h h h h h h x i x_i x i y i y_i y i F : Z → R \mathcal{F}:\mathcal{Z}\rightarrow\mathbb{R} F : Z → R f f f z i z_i z i σ i \sigma_i σ i σ i ∈ { + 1 , − 1 } \sigma_i\in\{+1, -1\} σ i ∈ { + 1 , − 1 }
12.5.6 式(12.41)的解释
这里所要求的是F \mathcal{F} F D \mathcal{D} D D \mathcal{D} D Z Z Z
12.5.7 定理12.5的解释
首先令记号
E ^ Z ( f ) = 1 m ∑ i = 1 m f ( z i ) Φ ( Z ) = sup f ∈ F ( E [ f ] − E ^ Z ( f ) ) \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} E Z ( f ) Φ ( Z ) = m 1 i = 1 ∑ m f ( z i ) = f ∈ F sup ( E [ f ] − E Z ( f ) ) 即E ^ Z ( f ) \widehat{E}_{Z}(f) E Z ( f ) f f f Φ ( Z ) \Phi(Z) Φ ( Z ) Z ′ Z^\prime Z ′ Z Z Z z m ∈ Z z_m\in Z z m ∈ Z z m ′ ∈ Z ′ z^\prime_m\in Z^\prime z m ′ ∈ Z ′
Φ ( Z ′ ) − Φ ( Z ) = sup f ∈ F ( E [ f ] − E ^ Z ′ ( f ) ) − sup f ∈ F ( E [ f ] − E ^ Z ( f ) ) ⩽ sup f ∈ F ( E ^ Z ( f ) − E ^ Z ′ ( f ) ) = sup f ∈ F ∑ i = 1 m f ( z i ) − ∑ i = 1 m f ( z i ′ ) m = sup f ∈ F f ( z m ) − f ( z m ′ ) m ⩽ 1 m \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(z_i)-\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} Φ ( Z ′ ) − Φ ( Z ) = f ∈ F sup ( E [ f ] − E Z ′ ( f ) ) − f ∈ F sup ( E [ f ] − E Z ( f ) ) ⩽ f ∈ F sup ( E Z ( f ) − E Z ′ ( f ) ) = f ∈ F sup m ∑ i = 1 m f ( z i ) − ∑ i = 1 m f ( z i ′ ) = f ∈ F sup m f ( z m ) − f ( z m ′ ) ⩽ m 1 第一个不等式是因为上确界的差不大于差的上确界[5]，第四行的等号由于Z ′ Z^\prime Z ′ Z Z Z z m z_m z m F : Z → [ 0 , 1 ] \mathcal{F}:\mathcal{Z}\rightarrow [0,1] F : Z → [ 0 , 1 ] f ( z m ) , f ( z m ′ ) ∈ [ 0 , 1 ] f(z_m),f(z_m^\prime)\in[0,1] f ( z m ) , f ( z m ′ ) ∈ [ 0 , 1 ]
Φ ( Z ) − Φ ( Z ′ ) = sup f ∈ F f ( z m ′ ) − f ( z m ) m ⩽ 1 m \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} Φ ( Z ) − Φ ( Z ′ ) = f ∈ F sup m f ( z m ′ ) − f ( z m ) ⩽ m 1 综上二式有：
∣ Φ ( Z ) − Φ ( Z ′ ) ∣ ⩽ 1 m \left\vert \Phi(Z)-\Phi\left(Z^{\prime}\right)\right\vert \leqslant \frac{1}{m} ∣ Φ ( Z ) − Φ ( Z ′ ) ∣ ⩽ m 1 将Φ \Phi Φ f f f f f f Φ \Phi Φ f f f
P ( Φ ( Z ) − E Z [ Φ ( Z ) ] ⩾ ϵ ) ⩽ exp ( − 2 ϵ 2 ∑ i c i 2 ) 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) P ( Φ ( Z ) − E Z [ Φ ( Z )] ⩾ ϵ ) ⩽ exp ( ∑ i c i 2 − 2 ϵ 2 ) 令exp ( − 2 ϵ 2 ∑ i c i 2 ) = δ \exp \left(\frac{-2 \epsilon^{2}}{\sum_{i} c_{i}^{2}}\right)=\delta exp ( ∑ i c i 2 − 2 ϵ 2 ) = δ ϵ = ln ( 1 / δ ) 2 m \epsilon=\sqrt{\frac{\ln (1 / \delta)}{2 m}} ϵ = 2 m l n ( 1/ δ )
P ( Φ ( Z ) − E Z [ Φ ( Z ) ] ⩾ ln ( 1 / δ ) 2 m ) ⩽ δ P\left(\Phi(Z)-\mathbb{E}_{Z}[\Phi(Z)] \geqslant \sqrt{\frac{\ln (1 / \delta)}{2 m}}\right) \leqslant \delta P ( Φ ( Z ) − E Z [ Φ ( Z )] ⩾ 2 m ln ( 1/ δ ) ) ⩽ δ 由逆事件的概率定义得
P ( Φ ( Z ) − E Z [ Φ ( Z ) ] ⩽ ln ( 1 / δ ) 2 m ) ⩾ 1 − δ P\left(\Phi(Z)-\mathbb{E}_{Z}[\Phi(Z)] \leqslant \sqrt{\frac{\ln (1 / \delta)}{2 m}}\right) \geqslant 1-\delta P ( Φ ( Z ) − E Z [ Φ ( Z )] ⩽ 2 m ln ( 1/ δ ) ) ⩾ 1 − δ 即书中式12.44的结论。下面来估计E Z [ Φ ( Z ) ] \mathbb{E}_{Z}[\Phi(Z)] E Z [ Φ ( Z )]
E Z [ Φ ( Z ) ] = E Z [ sup f ∈ F ( E [ f ] − E ^ Z ( f ) ) ] = E Z [ sup f ∈ F E Z ′ [ E ^ Z ′ ( f ) − E ^ Z ( f ) ] ] ⩽ E Z , Z ′ [ sup f ∈ F ( E ^ Z ′ ( f ) − E ^ Z ( f ) ) ] = E Z , Z ′ [ sup f ∈ F 1 m ∑ i = 1 m ( f ( z i ′ ) − f ( z i ) ) ] = E σ , Z , Z ′ [ sup f ∈ F 1 m ∑ i = 1 m σ i ( f ( z i ′ ) − f ( z i ) ) ] ⩽ E σ , Z ′ [ sup f ∈ F 1 m ∑ i = 1 m σ i f ( z i ′ ) ] + E σ , Z [ sup f ∈ F 1 m ∑ i = 1 m − σ i f ( z i ) ] = 2 E σ , Z [ sup f ∈ F 1 m ∑ i = 1 m σ i f ( z i ) ] = 2 R m ( F ) \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} E Z [ Φ ( Z )] = E Z [ f ∈ F sup ( E [ f ] − E Z ( f ) ) ] = E Z [ f ∈ F sup E Z ′ [ E Z ′ ( f ) − E Z ( f ) ] ] ⩽ E Z , Z ′ [ f ∈ F sup ( E Z ′ ( f ) − E Z ( f ) ) ] = E Z , Z ′ [ f ∈ F sup m 1 i = 1 ∑ m ( f ( z i ′ ) − f ( z i ) ) ] = E σ , Z , Z ′ [ f ∈ F sup m 1 i = 1 ∑ m σ i ( f ( z i ′ ) − f ( z i ) ) ] ⩽ E σ , Z ′ [ f ∈ F sup m 1 i = 1 ∑ m σ i f ( z i ′ ) ] + E σ , Z [ f ∈ F sup m 1 i = 1 ∑ m − σ i f ( z i ) ] = 2 E σ , Z [ f ∈ F sup m 1 i = 1 ∑ m σ i f ( z i ) ] = 2 R m ( F ) 第二行等式是外面套了一个对服从分布D \mathcal{D} D Z ′ Z^\prime Z ′ E Z ′ ∼ D [ E ^ Z ′ ( f ) ] = E ( f ) \mathbb{E}_{Z^\prime\sim\mathcal{D}}[\widehat{E}_{Z^\prime}(f)]=\mathbb{E}(f) E Z ′ ∼ D [ E Z ′ ( f )] = E ( f ) Z ′ Z^\prime Z ′ Z Z Z E Z ′ ∼ D [ E ^ Z ( f ) ] = E ^ Z ( f ) \mathbb{E}_{Z^\prime\sim\mathcal{D}}[\widehat{E}_{Z}(f)]=\widehat{E}_{Z}(f) E Z ′ ∼ D [ E Z ( f )] = E Z ( f )
第三行不等式基于上确界函数sup \sup sup sup f ∈ F \sup_{f\in\mathcal{F}} sup f ∈ F f f f E ^ Z ′ ( f ) − E ^ Z ( f ) \widehat{E}_{Z^{\prime}}(f)-\widehat{E}_{Z}(f) E Z ′ ( f ) − E Z ( f ) x x x E Z [ sup f ∈ F E Z ′ [ E ^ Z ′ ( f ) − E ^ Z ( f ) ] ] ⩽ E Z , Z ′ [ sup f ∈ F ( E ^ Z ′ ( f ) − E ^ Z ( f ) ) ] \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] E Z [ sup f ∈ F E Z ′ [ E Z ′ ( f ) − E Z ( f ) ] ] ⩽ E Z , Z ′ [ sup f ∈ F ( E Z ′ ( f ) − E Z ( f ) ) ] E Z , Z ′ [ ⋅ ] \mathbb{E}_{Z, Z^{\prime}}[\cdot] E Z , Z ′ [ ⋅ ] E Z [ E Z ′ [ ⋅ ] ] \mathbb{E}_{Z}[\mathbb{E}_{Z^\prime}[\cdot]] E Z [ E Z ′ [ ⋅ ]]
第五行引入对Rademacher随机变量的期望，由于函数值空间是标量，因为σ i \sigma_i σ i σ i ∈ { − 1 , + 1 } \sigma_i\in\{-1, +1\} σ i ∈ { − 1 , + 1 } σ i \sigma_i σ i E σ \mathbb{E}_{\sigma} E σ
第六行利用了上确界的和不小于和的上确界[5]，因为第一项中只含有变量z ′ z^\prime z ′ E Z \mathbb{E}_Z E Z z z z E Z ′ \mathbb{E}_{Z^\prime} E Z ′
第七行利用σ \sigma σ − σ -\sigma − σ σ \sigma σ Z Z Z Z ′ Z^\prime Z ′ D \mathcal{D} D i . i . d . i.i.d. i . i . d . z i ′ z^\prime_i z i ′ z z z Z ′ Z^\prime Z ′ Z Z Z
最后根据定义式12.41可得E Z [ Φ ( Z ) ] = 2 R m ( F ) \mathbb{E}_{Z}[\Phi(Z)]=2\mathcal{R}_m(\mathcal{F}) E Z [ Φ ( Z )] = 2 R m ( F )
12.6 定理12.6的解释
针对二分类问题, 定理 12.5 12.5 12.5
式(12.47)基于 Rademacher 复杂度 R m ( H ) R_m(\mathcal{H}) R m ( H ) E ( h ) E(h) E ( h )
式(12.48)基于经验 Rademacher 复杂度 R ^ D ( H ) \widehat{R}_D(\mathcal{H}) R D ( H ) E ( h ) E(h) E ( h )
可能大家都会有疑问：定理12.6的设定其实也适用于定理12.5, 即值域为二 值的
{ − 1 , + 1 } \{-1,+1\} { − 1 , + 1 } [ 0 , 1 ] [0,1] [ 0 , 1 ]
根据(经验)Rademacher 复杂度的定义可以知道, R m ( H ) R_m(\mathcal{H}) R m ( H ) R ^ D ( H ) \widehat{R}_D(\mathcal{H}) R D ( H ) [ 0 , 1 ] ) [0,1]) [ 0 , 1 ])
因此, 为二分类问题量身定制的定理12.6相比于通用的定理12.5来说,
二者的区别在 于定理12.6考虑了二分类的特殊情况,
得到了比定理12.5更紧的泛化误差界, 仅此而已。
下面做一些证明：
(1)首先通过式(12.49)将值域为 { − 1 , + 1 } \{-1,+1\} { − 1 , + 1 } H \mathcal{H} H [ 0 , 1 ] [0,1] [ 0 , 1 ] F H \mathcal{F}_{\mathcal{H}} F H
(2)接下来是该证明最核心部分, 即证明式(12.50)的结论
R ^ Z ( F H ) = 1 2 R ^ D ( H ) \widehat{R}_Z\left(\mathcal{F}_{\mathcal{H}}\right)=\frac{1}{2} \widehat{R}_D(\mathcal{H}) R Z ( F H ) = 2 1 R D ( H ) 12.8 12.8 12.8 f h ( x i , y i ) f_h\left(\boldsymbol{x}_i, y_i\right) f h ( x i , y i ) I ( h ( x i ) ≠ y i ) \mathbb{I}\left(h\left(\boldsymbol{x}_i\right) \neq y_i\right) I ( h ( x i ) = y i )
sup h ∈ H 1 m ∑ i = 1 m σ i 1 − y i h ( x i ) 2 = sup h ∈ H 1 2 m ∑ i = 1 m σ i + sup h ∈ H 1 2 m ∑ i = 1 m − y i σ i h ( x i ) 2 \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} h ∈ H sup m 1 i = 1 ∑ m σ i 2 1 − y i h ( x i ) = h ∈ H sup 2 m 1 i = 1 ∑ m σ i + h ∈ H sup 2 m 1 i = 1 ∑ m 2 − y i σ i h ( x i ) 其中 sup h ∈ H 1 2 m ∑ i = 1 m σ i \sup _{h \in \mathcal{H}} \frac{1}{2 m} \sum_{i=1}^m \sigma_i sup h ∈ H 2 m 1 ∑ i = 1 m σ i h h h sup h ∈ H 1 2 m ∑ i = 1 m σ i = 1 2 m ∑ i = 1 m σ i \sup _{h \in \mathcal{H}} \frac{1}{2 m} \sum_{i=1}^m \sigma_i=\frac{1}{2 m} \sum_{i=1}^m \sigma_i sup h ∈ H 2 m 1 ∑ i = 1 m σ i = 2 m 1 ∑ i = 1 m σ i E σ [ 1 m ∑ i = 1 m σ i ] = 0 \mathbb{E}_{\boldsymbol{\sigma}}\left[\frac{1}{m} \sum_{i=1}^m \sigma_i\right]=0 E σ [ m 1 ∑ i = 1 m σ i ] = 0 m = 2 m=2 m = 2 σ \boldsymbol{\sigma} σ ( − 1 , − 1 ) (-1,-1) ( − 1 , − 1 ) ( − 1 , + 1 ) , ( + 1 , − 1 ) (-1,+1),(+1,-1) ( − 1 , + 1 ) , ( + 1 , − 1 ) ( + 1 , + 1 ) (+1,+1) ( + 1 , + 1 ) − y i σ i -y_i \sigma_i − y i σ i σ i \sigma_i σ i E Z [ Φ ( Z ) ] ⩽ 2 R m ( F ) \mathbb{E}_Z[\Phi(Z)] \leqslant 2 R_m(\mathcal{F}) E Z [ Φ ( Z )] ⩽ 2 R m ( F ) σ \sigma σ
(3)关于式(12.51), 根据式(12.50)的结论, 可证明如下:
R m ( F H ) = E Z [ R ^ Z ( F H ) ] = E D [ 1 2 R ^ D ( H ) ] = 1 2 E D [ R ^ D ( H ) ] = 1 2 R m ( H ) R_m\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}) R m ( F H ) = E Z [ R Z ( F H ) ] = E D [ 2 1 R D ( H ) ] = 2 1 E D [ R D ( H ) ] = 2 1 R m ( H ) 其中第 2 个等号由 Z Z Z D D D
(4)最后, 将式(12.49)定义的 f h f_h f h 12.5 12.5 12.5 f f f
E [ f ( z ) ] = E [ I ( h ( x ) ≠ y ) ] = E ( h ) 1 m ∑ i = 1 m f ( z i ) = 1 m ∑ i = 1 m I ( h ( x i ) ≠ y i ) = E ^ ( h ) \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} E [ f ( z )] = E [ I ( h ( x ) = y )] = E ( h ) m 1 i = 1 ∑ m f ( z i ) = m 1 i = 1 ∑ m I ( h ( x i ) = y i ) = E ( h ) 将式(12.51)代入式(12.42), 即用
1 2 R m ( H ) \frac{1}{2} R_m(\mathcal{H}) 2 1 R m ( H ) R m ( F ) R_m(\mathcal{F}) R m ( F )
将式(12.50)代入式(12.43), 即用 1 2 R ^ D ( H ) \frac{1}{2} \widehat{R}_D(\mathcal{H}) 2 1 R D ( H ) R ^ Z ( F ) \widehat{R}_Z(\mathcal{F}) R Z ( F )
这里有个疑问在于，定理 12.5 12.5 12.5 F : Z → [ 0 , 1 ] \mathcal{F}: \mathcal{Z} \rightarrow[0,1] F : Z → [ 0 , 1 ] f h ( z ) f_h(z) f h ( z ) { 0 , 1 } \{0,1\} { 0 , 1 } 12.5 12.5 12.5 [ 0 , 1 ] [0,1] [ 0 , 1 ]
12.6.1 式(12.52)的证明
比较繁琐，同书上所示，参见Foundations of Machine
Learning[6]
12.6.2 式(12.53)的推导
根据式12.28有Π H ( m ) ⩽ ( e ⋅ m d ) d \Pi_{\mathcal{H}}(m) \leqslant\left(\frac{e \cdot m}{d}\right)^{d} Π H ( m ) ⩽ ( d e ⋅ m ) d R m ( H ) ⩽ 2 ln Π H ( m ) m R_{m}(\mathcal{H}) \leqslant \sqrt{\frac{2 \ln \Pi_{\mathcal{H}}(m)}{m}} R m ( H ) ⩽ m 2 l n Π H ( m ) Π H ( m ) ⩽ 2 d ln e m d m \Pi_{\mathcal{H}}(m) \leqslant \sqrt{\frac{2 d \ln \frac{e m}{d}}{m}} Π H ( m ) ⩽ m 2 d l n d e m E ( h ) ⩽ E ^ ( h ) + R m ( H ) + ln ( 1 / δ ) 2 m E(h) \leqslant \widehat{E}(h)+R_{m}(\mathcal{H})+\sqrt{\frac{\ln (1 / \delta)}{2 m}} E ( h ) ⩽ E ( h ) + R m ( H ) + 2 m l n ( 1/ δ )
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 ∣ ≤ ∣ a ∣ + ∣ b ∣ |a+b| \leq|a|+|b| ∣ a + b ∣ ≤ ∣ a ∣ + ∣ b ∣ a = ℓ ( L D , z ) − ℓ ( L D i ) a=\ell\left(\mathfrak{L}_{D}, \boldsymbol{z}\right)-\ell\left(\mathfrak{L}_{D^{i}}\right) a = ℓ ( L D , z ) − ℓ ( L D i ) b = ℓ ( L D i , z ) − ℓ ( L D \ i , z ) b=\ell\left(\mathfrak{L}_{D^{i}, \boldsymbol{z}}\right)-\ell\left(\mathfrak{L}_{D^{\backslash i}, \boldsymbol{z}}\right) b = ℓ ( L D i , z ) − ℓ ( L D \ i , z ) D \ i D^{\backslash i} D \ i D D D i i i D i D^i D i D D D i i i a , b a,b a , b a ⩽ β , b ⩽ β a\leqslant\beta, b\leqslant\beta a ⩽ β , b ⩽ β a + b ⩽ 2 β a +b \leqslant 2\beta a + b ⩽ 2 β
12.7.3 定理12.8的解释
西瓜书在该定理下方已明确给出该定理的意义, 即 "定理 12.8 12.8 12.8 L \mathfrak{L} L
（1）定理 12.8 12.8 12.8 0 ⩽ ℓ ( L D , z ) ⩽ M 0 \leqslant \ell\left(\mathfrak{L}_D, \boldsymbol{z}\right) \leqslant M 0 ⩽ ℓ ( L D , z ) ⩽ M I ( L D ( x ) , y ) \mathbb{I}\left(\mathfrak{L}_D(\boldsymbol{x}), y\right) I ( L D ( x ) , y ) M = 1 M=1 M = 1
（2）在前面泛化误差上界的推导中（例如定理 12.1、定理 12.3、定理 12.6、定理
12.7), 上界中与样本数 m m m O ( 1 / m ) O(1 / \sqrt{m}) O ( 1/ m ) O ( β m ) O(\beta \sqrt{m}) O ( β m ) m m m β = 1 / m \beta=1 / m β = 1/ m β = O ( 1 / m ) \beta=O(1 / m) β = O ( 1/ m ) 12.10 12.10 12.10 β \beta β m m m β \beta β m m m
12.7.4 式(12.60)的推导
将β = 1 m \beta=\frac{1}{m} β = m 1
12.7.5 经验损失最小化
顾名思义, "经验损失最小化" 指通过最小化经验损失来求得假设函数。
这里, "对于损失函数 ℓ \ell ℓ L \mathfrak{L} L L \mathfrak{L} L L \mathfrak{L} L h h h L \mathfrak{L} L
那么最小化经验误差和最小化经验损失有什么区别么?
在"西瓜书"第 286 页左下角边注中提到,
"最小化经验误差和最小化经验损失有时并不相同, 这
是由于存在某些病态的损失函数 ℓ \ell ℓ
对于 "误差"、"损失"、"风险" 等概念的辨析，参见"西瓜书"第 2 章 2.1 2.1 2.1
12.7.6 定理(12.9)的证明的解释
首先明确几个概念，ERM表示算法L \mathcal{L} L L \mathcal{L} L g g g
ℓ ( g , D ) = min h ∈ H ℓ ( h , D ) \ell(g, \mathcal{D})=\min _{h \in \mathcal{H}} \ell(h, \mathcal{D}) ℓ ( g , D ) = h ∈ H min ℓ ( h , D ) 再令
ϵ ′ = ϵ 2 δ 2 = 2 exp ( − 2 m ( ϵ ′ ) 2 ) \begin{array}{l}{\epsilon^{\prime}=\frac{\epsilon}{2}} \\ {\frac{\delta}{2}=2 \exp \left(-2 m\left(\epsilon^{\prime}\right)^{2}\right)}\end{array} ϵ ′ = 2 ϵ 2 δ = 2 exp ( − 2 m ( ϵ ′ ) 2 ) 将ϵ ′ = ϵ 2 \epsilon^\prime=\frac{\epsilon}{2} ϵ ′ = 2 ϵ δ 2 = 2 exp ( − 2 m ( ϵ ′ ) 2 ) {\frac{\delta}{2}=2 \exp \left(-2 m\left(\epsilon^{\prime}\right)^{2}\right)} 2 δ = 2 exp ( − 2 m ( ϵ ′ ) 2 ) m = 2 ϵ 2 ln 4 δ m=\frac{2}{\epsilon^{2}} \ln \frac{4}{\delta} m = ϵ 2 2 ln δ 4
P ( ∣ 1 m ∑ i = 1 m x i − 1 m ∑ i = 1 m E ( x i ) ∣ ⩾ ϵ ) ⩽ 2 exp ( − 2 m ϵ 2 ) 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) P ( m 1 i = 1 ∑ m x i − m 1 i = 1 ∑ m E ( x i ) ⩾ ϵ ) ⩽ 2 exp ( − 2 m ϵ 2 ) 其中1 m ∑ i = 1 m E ( x i ) = ℓ ( g , D ) \frac{1}{m} \sum_{i=1}^{m} \mathbb{E}\left(x_{i}\right)=\ell(g, \mathcal{D}) m 1 ∑ i = 1 m E ( x i ) = ℓ ( g , D ) 1 m ∑ i = 1 m x i = ℓ ^ ( g , D ) \frac{1}{m} \sum_{i=1}^{m} x_{i}=\widehat{\ell}(g, \mathcal{D}) m 1 ∑ i = 1 m x i = ℓ ( g , D )
P ( ∣ ℓ ( g , D ) − ℓ ^ ( g , D ) ∣ ⩾ ϵ 2 ) ⩽ δ 2 P(|\ell(g, \mathcal{D})-\widehat{\ell}(g, D)| \geqslant \frac{\epsilon}{2})\leqslant \frac{\delta}{2} P ( ∣ ℓ ( g , D ) − ℓ ( g , D ) ∣ ⩾ 2 ϵ ) ⩽ 2 δ 根据逆事件的概率可得
P ( ∣ ℓ ( g , D ) − ℓ ^ ( g , D ) ∣ ⩽ ϵ 2 ) ⩾ 1 − δ 2 P(|\ell(g, \mathcal{D})-\widehat{\ell}(g, D)| \leqslant \frac{\epsilon}{2})\geqslant 1- \frac{\delta}{2} P ( ∣ ℓ ( g , D ) − ℓ ( g , D ) ∣ ⩽ 2 ϵ ) ⩾ 1 − 2 δ 即文中∣ ℓ ( g , D ) − ℓ ^ ( g , D ) ∣ ⩽ ϵ 2 |\ell(g, \mathcal{D})-\widehat{\ell}(g, D)| \leqslant \frac{\epsilon}{2} ∣ ℓ ( g , D ) − ℓ ( g , D ) ∣ ⩽ 2 ϵ 1 − δ / 2 1-\delta/2 1 − δ /2
由2 m + ( 4 + M ) ln ( 2 / δ ) 2 m = ϵ 2 \frac{2}{m}+(4+M) \sqrt{\frac{\ln (2 / \delta)}{2 m}}=\frac{\epsilon}{2} m 2 + ( 4 + M ) 2 m l n ( 2/ δ ) = 2 ϵ
m = ( 4 + M ) ln ( 2 / δ ) 2 + ( 4 + M ) 2 ln ( 2 / δ ) 2 − 4 × ϵ 2 × ( − 2 ) 2 × ϵ 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 = 2 × 2 ϵ ( 4 + M ) 2 l n ( 2/ δ ) + ( 4 + M ) 2 2 l n ( 2/ δ ) − 4 × 2 ϵ × ( − 2 ) 即m = O ( 1 ϵ 2 ln 1 δ ) m=O\left(\frac{1}{\epsilon^{2}} \ln \frac{1}{\delta}\right) m = O ( ϵ 2 1 ln δ 1 )
由P ( ∣ ℓ ( g , D ) − ℓ ^ ( g , D ) ∣ ⩽ ϵ 2 ) ⩾ 1 − δ 2 P(|\ell(g, \mathcal{D})-\widehat{\ell}(g, D)| \leqslant \frac{\epsilon}{2})\geqslant 1- \frac{\delta}{2} P ( ∣ ℓ ( g , D ) − ℓ ( g , D ) ∣ ⩽ 2 ϵ ) ⩾ 1 − 2 δ
P ( ℓ ( L , D ) − ℓ ( g , D ) ⩽ ϵ ) ⩾ 1 − δ P(\ell(\mathfrak{L}, \mathcal{D})-\ell(g, \mathcal{D})\leqslant\epsilon)\geqslant 1-\delta P ( ℓ ( L , D ) − ℓ ( g , D ) ⩽ ϵ ) ⩾ 1 − δ 又因为m m m ( 1 / ϵ , 1 / δ , size ( x ) , size ( c ) ) \left(1/\epsilon,1/\delta,\text{size}(x),\text{size}(c)\right) ( 1/ ϵ , 1/ δ , size ( x ) , size ( c ) ) H \mathcal{H} H
参考文献
[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.
