《机器学习理论导引》笔记目录

• 第一章 : 预备知识
  • 第一章 : 预备知识(上)
  • 第一章 : 预备知识(下)
• 第二章 : 可学性
• 第三章 : 复杂度
• 第四章 : 泛化界
  • 第四章 : 泛化界(上)
  • 第四章 : 泛化界(中)
  • 第四章 : 泛化界(下)
• 第五章 : 稳定性
• 第六章 : 一致性
  • 第六章 : 一致性(上)
  • 第六章 : 一致性(下)
• 第七章 : 收敛率
  • 第七章 : 收敛率(上)
  • 第七章 : 收敛率(下)
• 第八章 : 遗憾界
  • 第八章 : 遗憾界(上)
  • 第八章 : 遗憾界(下)

0 补充感言

  我是真的没有想到这章的内容竟然这么多，之前 (上) 的部分其实在本地我分了两个 markdown 文件，因为单一 markdown 文件太大甚至已经影响到预览的响应速度了。

4.2 泛化误差下界

泛化误差下界的意义

• 指出学习算法能力的极限
• 对于任何学习算法存在一个数据分布，样本数量有限时，学习算法不能以较大概率输出目标概念的近似。

一般证明方法

• 通常采用构造法证明
• 证明的要点 : 如何构造这样的数据分布

4.2.1 可分情形

Fubini 定理

  若函数 $f(x,y)$ 的期望 ${\mathbb{E}}_{x,y}[|f(x,y)|]<\infty$，则 ${\mathbb{E}}_x[{\mathbb{E}}_y[f(x,y)]]={\mathbb{E}}_y[{\mathbb{E}}_x[f(x,y)]]$

定理 4.6

  若假设空间 $\mathcal{H}$ 的 VC 维 $d>1$，则对任意 $m>1$ 和学习算法 $\mathcal{L}$，存在分布 $\mathcal{D}$ 和目标概念 $c\in \mathcal{H}$ 使得

$$P\left(E(h_D,c)>\frac{d-1}{32m}\right)⩾\frac{1}{100}$$

  其中 $h_D$ 为学习算法 $\mathcal{L}$ 基于大小为 $m$ 的训练集 $D$ 输出的假设。

证明

  对于给定的 $D\in A$，考虑来自均匀分布 $\mathcal{U}$ 的目标概念 $c:\mathcal{S}\mapsto \{-1,+1\}$，我们可以得到以下结论 :

$$\begin{array}{rl}{\mathbb{E}}_U\left[E\left(h_D,c\right)\right]& =\sum _c\sum _{x\in S}\mathbb{I}\left(h_D(x)\ne c(x)\right)P_{x\sim \mathcal{D}}(x)P_{c\sim \mathcal{U}}(c)\\ & ⩾\sum _c\sum _{x\in S-\bar{D}-\left\{x_0\right\}}\mathbb{I}\left(h_D(x)\ne c(x)\right)P_{x\sim \mathcal{D}}(x)P_{c\sim \mathcal{U}}(c)\\ & =\sum _{x\in S-\bar{D}-\left\{x_0\right\}}\left(\sum _c\mathbb{I}\left(h_D(x)\ne c(x)\right)P_{c\sim \mathcal{U}}(c)\right)P_{x\sim D}(x)\\ & =\frac{1}{2}\sum _{x\in S-\bar{D}-\left\{x_0\right\}}{P}_{x\sim D}(x)\\ & ⩾\frac{1}{2}\frac{d-1}{2}\frac{8ϵ}{d-1}=2ϵ\end{array}$$

  上式对于任意 $D\in A$ 均成立，因此关于 $A$ 的期望也成立，有 ${\mathbb{E}}_{D\in A}[{\mathbb{E}}_{\mathcal{U}}[E(h_D,c)]]⩾2ϵ$。

  可知交换期望计算顺序不等式依然成立, 即有 ${\mathbb{E}}_{D\in A}[{\mathbb{E}}_{\mathcal{U}}[E(h_D,c)]]⩾2ϵ$ 期望的下界为 $2ϵ$，必定存在一个目标概念 $c^{\ast }\in \mathcal{H}$ 满足 ${\mathbb{E}}_{D\in A}[{\mathbb{E}}_{\mathcal{U}}[E(h_D,c^{\ast })]]⩾2ϵ$

$$\begin{array}{rl}& {\mathbb{E}}_{D\in A}\left[E\left(h_D,c^{\ast }\right)\right]\\ =& \sum _{D:E\left(h_D,c^{\ast }\right)>ϵ}E\left(h_D,c^{\ast }\right)P(D)+\sum _{D:E\left(h_D,c^{\ast }\right)⩽ϵ}E\left(h_D,c^{\ast }\right)P(D)\\ ⩽& P_{x\sim \mathcal{D}}\left(x\in \left(S-\left\{x_0\right\}\right)\right)P_{D\in A}\left(E\left(h_D,c^{\ast }\right)>ϵ\right)\\ & +ϵ\left(1-P_{D\in A}\left(E\left(h_D,c^{\ast }\right)>ϵ\right)\right)\\ =& 8ϵP_{D\in A}\left(E\left(h_D,c^{\ast }\right)>ϵ\right)+ϵ\left(1-P_{D\in A}\left(E\left(h_D,c^{\ast }\right)>ϵ\right)\right)\\ =& 7ϵP_{D\in A}\left(E\left(h_D,c^{\ast }\right)>ϵ\right)+ϵ\end{array}$$

  通过上面两个式子，我们有

$$P_{D\in A}\left(E\left(h_D,c^{\ast }\right)>ϵ\right)⩾\frac{1}{7ϵ}(2ϵ-ϵ)=\frac{1}{7}$$

  借助于这个不等式，有

$$\begin{gathered} P_{D\sim {\mathcal{D}}^m}\left(E(h_D,c^{\ast })>ϵ\right) \\ ⩾P_{D\in A}\left(E(h_D,c^{\ast })>ϵ\right)P_{D\sim {\mathcal{D}}^m}(D\in A) \\ ⩾\frac{1}{7}{P}_{D\sim {\mathcal{D}}^m}(D\in A) \end{gathered}$$

  接下来，只要找到 $P_{D\sim {\mathcal{D}}^m}(D\in A)$ 的下界即可证明定理。令 $l_m$ 表示 $\bar{D}$ 的数目，根据 Chernoff 不等式可知，对于 $\gamma >1$，有

$$P_{D\sim {\mathcal{D}}^m}(l_m⩾8ϵm(1+\gamma ))⩽\exp \left(-\frac{8ϵm{\gamma }^2}{3}\right)$$

  令 $ϵ=(d-1)/(32m),\gamma =1$，可得

$$\begin{gathered} 1-P_{D\sim {\mathcal{D}}^m}(D\in A) \\ =P_{D\sim {\mathcal{D}}^m}(l_m⩾\frac{d-1}{2})⩽\exp \left(-\frac{d-1}{12}\right)⩽\exp \left(-\frac{1}{12}\right) \end{gathered}$$

  令 $\exp \left(-\frac{1}{12}\right)⩽1-7\delta$，可得 $P_{D\sim {\mathcal{D}}^m}(D\in A)⩾7\delta$，再根据

$$P_{D\sim {\mathcal{D}}^m}\left(E(h_D,c^{\ast })>ϵ\right)⩾\frac{1}{7}{P}_{D\sim {\mathcal{D}}^m}(D\in A)$$

  可知

$$P_{D\sim {\mathcal{D}}^m}\left(E(h_D,c^{\ast })>ϵ\right)⩾\delta$$

  取 $\delta =\frac{1}{100}$，从而定理得证。

4.2.2 不可分情形

  对于不可分假设空间的泛化误差下界，主要比较学习算法 $\mathcal{L}$ 的泛化误差与贝叶斯最优分类器泛化误差之间的关系。

引理 4.2

  令 $\sigma$ 为服从 $\{-1,+1\}$ 上均匀分布的随机变量，对于 $0<\alpha <1$ 构造随机变量 ${\alpha }_{\sigma }=\frac{1}{2}+\frac{\alpha \sigma }{2}$, 基于 $\sigma$ 构造 $X\sim {\mathcal{D}}_{\sigma }$，其中 ${\mathcal{D}}_{\sigma }$ 为伯努利分布 $\text{Bernoulli}({\alpha }_{\sigma })$，即 $P(X=1)={\alpha }_{\sigma }$。令 $\mathcal{S}=\{X_1,\dots ,X_m\}$ 表示从分布 ${\mathcal{D}}_{\sigma }^m$ 独立同分布采样得到的大小为 $m$ 的集合, 即 $\mathcal{S}\sim {\mathcal{D}}_{\sigma }^m$，则对于函数 $f:X^m\mapsto \{-1,+1\}$ 有

$${\mathbb{E}}_{\sigma }\left[P_{\mathcal{S}\sim D_g^m}(f(\mathcal{S})\ne \sigma )\right]⩾\Phi (2\lceil \frac{m}{2}\rceil ,\alpha )$$

  其中 $\Phi (m,\alpha )=\frac{1}{4}\left(1-\sqrt{1-\exp \left(-\frac{m{\alpha }^2}{1-{\alpha }^2}\right)}\right)$

  引理 4.2 可以从投硬币的角度理解 :

• 我们可以将每个样本的标记视为投硬币的结果
• 红硬币投到正面概率为 $\frac{1+\alpha }{2}$，对应于 $\sigma =+1$
• 蓝硬币投到正面概率为 $\frac{1-\alpha }{2}$，对应于 $\sigma =-1$
• 算法需要通过硬币的投掷结果来判断，样本是由红硬币产生的还是蓝硬币产生的，对应于 $f$

  引理 4.2 告诉我们 : 为了区分样本对应哪个硬币，需要其在训练集中出现足够多的次数 ($\Omega (1/{\alpha }^2)$ 次)

引理 4.3

  令 $Z$ 为取值范围为 $[0,1]$ 的随机变量，对于 $\gamma \in [0,1)$ 有

$$P(Z>\gamma )⩾\frac{\mathbb{E}[Z]-\gamma }{1-\gamma }⩾\mathbb{E}[Z]-\gamma$$

证明

$$\begin{array}{rl}\mathbb{E}[Z]& =\sum _{z⩽\gamma }P(Z=z)z+\sum _{z>\gamma }P(Z=z)z\\ & ⩽\sum _{z⩽\gamma }P(Z=z)\gamma +\sum _{z>\gamma }P(Z=z)\\ & =\gamma P(Z⩽\gamma )+P(Z>\gamma )\\ & =\gamma \left(1-P(Z>\gamma )\right)+P(Z>\gamma )\\ & =(1-\gamma )P(Z>\gamma )+\gamma \end{array}$$

定理 4.7

  若假设空间 $\mathcal{H}$ 的 VC 维 $d>1$，则对任意 $m>1$ 和学习算法 $\mathfrak{L}$，存在分布 $\mathcal{D}$ 使得

证明

  $\hat{S}=\{x_1,\dots ,x_d\}\subset X$ 表示能被 $\mathcal{H}$ 打散的集合。对于 $\alpha \in [0,1]$ 和向量 $\sigma =({\sigma }_1;\dots ;{\sigma }_d)\in \{-1,+1{\}}^d$，在 $\mathcal{S}\times \mathcal{Y}$ 上构造如下分布 ${\mathcal{D}}_{\sigma }$

$$\begin{gathered} P_{{\mathcal{D}}_{\sigma }}(z=(x_i,+1))=\frac{1}{d}\left(\frac{1}{2}+\frac{{\sigma }_i\alpha }{2}\right)(i\in [d]) \\ {P}_{{\mathcal{D}}_{\sigma }}(z=(x_i,-1))=\frac{1}{d}\left(\frac{1}{2}-\frac{{\sigma }_i\alpha }{2}\right)(i\in [d]) \end{gathered}$$

  因为 $\mathcal{S}$ 能被 $\mathcal{H}$ 打散，所以我们可以构造该数据下的贝叶斯最优分类器 $h_{{\mathcal{D}}_{\sigma }}^{\ast }(x_i)={\mathrm{argmax}}_{y\in \{-1,+1\}}P(y|x_i)=\text{sign}(\mathbb{I}({\sigma }_i>0)-1/2),i\in [d]$，可知 $h_{{\mathcal{D}}_{\sigma }}^{\ast }\in \mathcal{H}$，对于 $h_{{\mathcal{D}}_{\sigma }}^{\ast }$ 计算可得

$$\begin{array}{rl}E\left(h_{{\mathcal{D}}_{\sigma }}^{\ast }\right)=& \sum _{{\mathbf{x}}_i\in S}(P_{{\mathcal{D}}_{\sigma }}\left(z=\left({\mathbf{x}}_i,+1\right)\right)\mathbb{I}\left(h_{{\mathcal{D}}_{\sigma }}^{\ast }\left({\mathbf{x}}_i\right)=-1\right)\\ & +P_{{\mathcal{D}}_{\sigma }}\left(z=\left({\mathbf{x}}_i,-1\right)\right)\mathbb{I}\left(h_{{\mathcal{D}}_{\sigma }}^{\ast }\left({\mathbf{x}}_i\right)=+1\right))\\ =& \sum _{{\mathbf{x}}_i\in S}\left(P_{{\mathcal{D}}_{\sigma }}\left(z=\left({\mathbf{x}}_i,+1\right)\right)\mathbb{I}\left({\sigma }_i<0\right)+P_{{\mathcal{D}}_{\sigma }}\left(z=\left({\mathbf{x}}_i,-1\right)\right)\mathbb{I}\left({\sigma }_i>0\right)\right)\\ =& \sum _{{\mathbf{x}}_i\in S}\frac{1}{d}\left(\frac{1}{2}-\frac{\alpha }{2}\right)=\frac{1}{2}-\frac{\alpha }{2}\end{array}$$

  对于任意 $h\in \mathcal{H}$ 计算可得

$$\begin{array}{rl}E(h)=& \sum _{x_i\in S}(P_{{\mathcal{D}}_{\sigma }}\left(z=\left(x_i,+1\right)\right)\mathbb{I}\left(h\left(x_i\right)\ne h_{{\mathcal{D}}_{\sigma }}^{\ast }\left(x_i\right)\right)\mathbb{I}\left(h_{{\mathcal{D}}_{\sigma }}^{\ast }\left(x_i\right)=+1\right)\\ & +P_{{\mathcal{D}}_{\sigma }}\left(z=\left(x_i,+1\right)\right)\mathbb{I}\left(h\left(x_i\right)=h_{{\mathcal{D}}_{\sigma }}^{\ast }\left(x_i\right)\right)\mathbb{I}\left(h_{{\mathcal{D}}_{\sigma }}^{\ast }\left(x_i\right)=-1\right)\\ & +P_{{\mathcal{D}}_{\sigma }}\left(z=\left(x_i,-1\right)\right)\mathbb{I}\left(h\left(x_i\right)\ne h_{{\mathcal{D}}_{\sigma }}^{\ast }\left(x_i\right)\right)\mathbb{I}\left(h_{{\mathcal{D}}_{\sigma }}^{\ast }\left(x_i\right)=-1\right)\\ & +P_{{\mathcal{D}}_{\sigma }}\left(z=\left(x_i,-1\right)\right)\mathbb{I}\left(h\left(x_i\right)=h_{{\mathcal{D}}_{\sigma }}^{\ast }\left(x_i\right)\right)\mathbb{I}\left(h_{{\mathcal{D}}_{\sigma }}^{\ast }\left(x_i\right)=+1\right)\\ =& \sum _{x_i\in S}\left(\frac{1+\alpha }{2d}\mathbb{I}\left(h\left(x_i\right)\ne h_{{\mathcal{D}}_{\sigma }}^{\ast }\left(x_i\right)\right)+\frac{1-\alpha }{2d}\mathbb{I}\left(h\left(x_i\right)=h_{{\mathcal{D}}_{\sigma }}^{\ast }\left(x_i\right)\right)\right)\\ =& \frac{\alpha }{d}\sum _{x_i\in S}\mathbb{I}\left(h\left(x_i\right)\ne h_{{\mathcal{D}}_{\sigma }}^{\ast }\left(x_i\right)\right)+\frac{1}{2}-\frac{\alpha }{2}\end{array}$$

  从而可知

$$E(h)-E\left(h_{{\mathcal{D}}_{\sigma }}^{\ast }\right)=\frac{\alpha }{d}\sum _{x_i\in S}\mathbb{I}\left(h\left(x_i\right)\ne h_{{\mathcal{D}}_{\sigma }}^{\ast }\left(x_i\right)\right)$$

  $|Z{|}_x$ 表示样本 $x$ 在 $Z$ 中出现的次数

$$\begin{array}{rl}& {\mathbb{E}}_{\sigma \sim u,Z\sim D_{\sigma }^m}\left[\frac{1}{\alpha }\left(E\left(h_Z\right)-E\left(h_{D_{\sigma }}^{\ast }\right)\right)\right]\\ & =\frac{1}{d}\sum _{x\in S}{\mathbb{E}}_{\sigma \sim u,Z\sim D_{\sigma }^m}\left[\mathrm{I}\left(h_Z(x)\ne h_{D_{\sigma }}^{\ast }(x)\right)\right]\\ & =\frac{1}{d}\sum _{x\in S}{\mathbb{E}}_{\sigma \sim u}\left[P_{Z\sim D_{\sigma }^m}\left(h_Z(x)\ne h_{D_{\sigma }}^{\ast }(x)\right)\right]\\ & =\frac{1}{d}\sum _{x\in S}\sum _{n=0}^m{\mathbb{E}}_{\sigma \sim u}\left[P_{Z\sim D_{\sigma }^m}\left(h_Z(x)\ne {h_{D_{\sigma }}^{\ast }(x)||Z|}_x=n\right)P\left(|Z{|}_x=n\right)\right]\\ & ⩾\frac{1}{d}\sum _{x\in S}\sum _{n=0}^m\Phi (2[n/2\rceil ,\alpha )P\left(|Z{|}_x=n\right)⩾\frac{1}{d}\sum _{x\in S}\sum _{n=0}^m\Phi (n+1,\alpha )P\left(|Z{|}_x=n\right)\\ & ⩾\frac{1}{d}\sum _{x\in S}\Phi (m/d+1,\alpha )=\Phi (m/d+1,\alpha )\end{array}$$

  由于上述关于 $\sigma$ 期望的下界被 $\Phi (m/d+1,\alpha )$ 限制住，则必定存在 ${\sigma }^{\ast }\in \{-1,+1{\}}^d$ 使得下式成立

$${\mathbb{E}}_{Z\sim {\mathcal{D}}_{\sigma }^{\prime }}\left[\frac{1}{\alpha }\left(E\left(h_Z\right)-E\left(h_{{\mathcal{D}}_{\sigma }^{\ast }}^{\ast }\right)\right)\right]⩾\Phi (m/d+1,\alpha )$$

  根据引理 4.3 可知，对于 ${\sigma }^{\ast }$ 以及任意 $\gamma \in [0,1)$ 有

$$P_{Z\sim D_{{\sigma }^{\ast }}^m}\left(\frac{1}{\alpha }\left(E(h_Z)-E\left(h_{{\mathcal{D}}_{\sigma }^{\ast }}^{\ast }\right)\right)>\gamma \mu \right)⩾(1-\gamma )u$$

  其中 $u=\Phi (m/d+1,\alpha )$，令 $\delta$ 与 $ϵ$ 满足条件 $\delta ⩾(1-\gamma )u$ 以及 $ϵ⩾\gamma \alpha u$，则有

$$P_{Z\sim D_{{\sigma }^{\ast }}^m}\left(E(h_Z)-E\left(h_{{\mathcal{D}}_{\sigma }^{\ast }}^{\ast }\right)>ϵ\right)⩾\delta$$

  为了找到满足条件的 $\delta$ 与 $ϵ$，令 $\gamma =1-8\delta$，则

$$\begin{array}{rl}\delta ⩽(1-\gamma )u\iff & u⩾\frac{1}{8}\\ \iff & \frac{1}{4}\left(1-\sqrt{1-\exp \left(-\frac{(m/d+1){\alpha }^2}{1-{\alpha }^2}\right)}\right)⩾\frac{1}{8}\\ \iff & \frac{(m/d+1){\alpha }^2}{1-{\alpha }^2}⩽\ln \frac{4}{3}\\ \iff & \frac{m}{d}⩽\left(\frac{1}{{\alpha }^2}-1\right)\ln \frac{4}{3}-1\end{array}$$

  令 $\alpha =8ϵ/(1-8\delta )$，即 $ϵ=\gamma \alpha /8$，即

$$\frac{m}{d}⩽\left(\frac{(1-8\delta {)}^2}{64{ϵ}^2}-1\right)\ln \frac{4}{3}-1$$

  令 $\delta ⩽1/64$，可得

$$\left(\frac{(1-8\delta {)}^2}{64{ϵ}^2}-1\right)\ln \frac{4}{3}-1⩾{\left(\frac{7}{64}\right)}^2\frac{1}{{ϵ}^2}\ln \frac{4}{3}-\ln \frac{4}{3}-1$$

  上式右端为关于 $\frac{1}{{ϵ}^2}$ 的函数 $f(\frac{1}{{ϵ}^2})$，可寻找 $w$ 使得 $m/d⩽w/{ϵ}^2$。令 $ϵ⩽1/64$，由 $\frac{w}{(1/64{)}^2}=f\left(\frac{1}{(1/64{)}^2}\right)$ 可得

$${\left(\frac{7}{64}\right)}^2\ln \frac{4}{3}-{\left(\frac{1}{64}\right)}^2\left(\ln \frac{4}{3}+1\right)\approx 0.003127⩾\frac{1}{320}$$

  因此, 当 ${ϵ}^2⩽\frac{1}{320m/d}$ 时，满足 $\delta ⩽(1-\gamma )u$ 以及 $ϵ⩽\gamma \alpha u$。取$ϵ=\sqrt{\frac{d}{320m}}$ 和 $\delta =1/64$，定理得证