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

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

4.3 分析实例

理论回顾

定理3.6

  ${\mathbb{R}}^d$ 中由非齐次线性超平面构成的假设空间 $\mathcal{H}$ 的 VC维为 d+1

定理3.7

  若 $\Vert x\Vert \le r$，D 为大小为 m 的数据集，则超平面族 $\mathcal{H}=\{x\mapsto {\mathbf{w}}^T\mathbf{x}:\Vert \mathbf{w}\Vert \le \Lambda \}$ 的经验 Rademacher复杂度满足

$$\widehat{{\mathcal{R}}_D}(\mathcal{H})\le \sqrt{\frac{r^2{\Lambda }^2}{m}}$$

定理3.8

  若 $\Vert \mathbf{x}\Vert \le r$，则超平面族 $\{x\mapsto \text{sign}({\mathbf{w}}^T\mathbf{x}):{\min }_{\mathbf{x}}|{\mathbf{w}}^T\mathbf{x}|=1\wedge \Vert \mathbf{w}\Vert \le \Lambda \}$ 的 VC维 d满足

$$d\le r^2{\Lambda }^2$$

定义 3.3

  函数空间 $\mathcal{F}$ 关于 𝑍 的经验 Rademacher 复杂度为

定义 3.4

  函数空间 $\mathcal{F}$ 关于 $\mathcal{Z}$ 在分布 m 上的 Rademacher 复杂度为

引理 (第一章中的 Hoeffding 不等式)

  若训练集 $\mathcal{D}$ 包含 m 个从分布 $\mathcal{D}$ 上独立同分布采样而得的样本，$0<ϵ<1$，则对任意 $h\in \mathcal{H}$，有

$$\begin{gathered} P\left(\hat{E}(h)-E(h)\ge ϵ\right)\le \exp (-2m{ϵ}^2) \\ P\left(\hat{E}(h)-E(h)\le -ϵ\right)\le \exp (-2m{ϵ}^2) \\ P\left(|\hat{E}(h)-E(h)|\ge ϵ\right)\le 2\exp (-2m{ϵ}^2) \end{gathered}$$

  学习方法的泛化能力分析往往是通过研究泛化误差的概率上界进行的，具体来说，就是通过比较两种学习方法的泛化误差上界的大小来比较它们的优劣。
  泛化误差上界是样本容量和空间容量的函数，样本容量越大，空间容量越小，泛化误差上界越小。

间隔损失函数

  引入间隔使得泛化误差界与数据分布相关。

定义 4.1

  对任意 $\rho >0$，$\rho -$ 间隔损失为定义在 $z,z^{\prime }\in \mathbb{R}$ 上的损失函数 ${\ell }_{\rho }:\mathbb{R}\times \mathbb{R}\mapsto {\mathbb{R}}_{+},{\ell }_{\rho }(z,z^{\prime })={\Phi }_{\rho }(z{z}^{\prime })$，其中

$${\Phi }_{\rho }(x)=\{\begin{array}{ll}0& \rho ⩽x\\ 1-x/\rho & 0⩽x⩽\rho \\ 1& x⩽0\end{array}$$

  对于集合 $D=x_1,\dots ,x_m$ 与假设 $h$，经验间隔损失表示为

$$E_{\rho }(h)=\frac{1}{m}\sum _{i=1}^m{\Phi }_{\rho }(y_{i}h(x_i))$$

  又 ${\Phi }_{\rho }(y_{i}h(x_i))⩽{\mathbb{I}}_{y_{i}h(x_i)⩽\rho }$，由拉格朗日定理可得

$$|{\Phi }_{\rho }(x_1)-{\Phi }_{\rho }(x_2)|⩽|{\Phi }_{\rho }^{{}^{\prime }}(\xi )||x_1-x_2|$$

  由间隔损失函数定义可得

$$|{\Phi }_{\rho }^{{}^{\prime }}(\xi )|⩽\frac{1}{\rho }$$

  (补充:对于在实数集的子集的函数 $f:D\subseteq \mathbb{R}\to \mathbb{R}$，若存在常数 $K$，使得 $|f(a)-f(b)|⩽|a-b|,\forall a,b\in D$，则称 $f$ 符合 Lipschitz 条件，对于 $f$ 最小的常数 $K$ 称为 $f$ 的 Lipschitz 常数) 可知 ${\Phi }_{\rho }$ 最多是 $\frac{1}{\rho }$-Lipschitz

Talagrand 收缩引理

引理 4.4 (Talagrand 收缩引理)

若 $\Phi :\mathbb{R}\mapsto \mathbb{R}$ 为 ${\ell }_{\rho }$− Lipschitz 函数，则对于任意实值假设空间 $\mathcal{H}$ 有下式成立:

$${\mathfrak{R}}_D(\Phi \circ \mathcal{H})⩽L{\hat{\mathfrak{R}}}_D(\mathcal{H})$$

  说明 Lipschitz 函数与假设空间 $\mathcal{H}$ 复合后的经验 Rademacher 复杂度可以基于假设空间 $\mathcal{H}$ 的经验 Rademacher 复杂度表示

证明

  固定样本空间 $D=(x_1,\dots ,x_m)$，根据定义

$$\begin{array}{rl}{\Re }_S(\Phi \circ H)& =\frac{1}{m}\mathrm{E}\left[\underset{h\in H}{\sup }\sum _{i=1}^m{\sigma }_i(\Phi \circ h)\left(x_i\right)\right]\\ & =\frac{1}{m}{\sigma }_{{\sigma }_1,\dots ,{\sigma }_{m-1}}^{\mathrm{E}}\left[\underset{{\sigma }_m}{\mathrm{E}}\left[\underset{h\in H}{\sup }{u}_{m-1}(h)+{\sigma }_m(\Phi \circ h)\left(x_m\right)\right]\right]\end{array}$$

  $u_{m-1}(h)={\sum }_{i=1}^{m-1}{\sigma }_i(\Phi \circ h)(x_i)$ 假设上确界能够达到，令 $h_1,h_2\in H$ 满足

$$\begin{array}{rl}& u_{m-1}\left(h_1\right)+{\Phi }_m\left(h_1\left(x_m\right)\right)=\underset{h\in H}{\sup }{u}_{m-1}(h)+{\Phi }_m\left(h\left(x_m\right)\right)\\ & u_{m-1}\left(h_2\right)-{\Phi }_m\left(h_2\left(x_m\right)\right)=\underset{h\in H}{\sup }{u}_{m-1}(h)-{\Phi }_m\left(h\left(x_m\right)\right)\end{array}$$

  如果上确界达不到，可以考虑接近 $ϵ$ 的上确界，可以得到类似下面的结论。因为 ${\sigma }_m$ 是 $\{-1,+1\}$ 上的均匀分布，根据期望的定义有

$$\begin{array}{rl}& \mathrm{E}\left[\underset{m\in H}{\sup }{u}_{m-1}(h)+{\sigma }_m(\Phi \circ h)\left(x_m\right)\right]]\\ & =\frac{1}{2}\left[u_{m-1}\left(h_1\right)+\left(\Phi \circ h_1\right)\left(x_m\right)\right]+\frac{1}{2}\left[u_{m-1}\left(h_2\right)-\left(\Phi \circ h_2\right)\left(x_m\right)\right]\\ & \le \frac{1}{2}\left[u_{m-1}\left(h_1\right)+u_{m-1}\left(h_2\right)+sL\left(h_1\left(x_m\right)-h_2\left(x_m\right)\right)\right]\\ & =\frac{1}{2}\left[u_{m-1}\left(h_1\right)+sL{h}_1\left(x_m\right)\right]+\frac{1}{2}\left[u_{m-1}\left(h_2\right)-sL{h}_2\left(x_m\right)\right]\\ & \le \frac{1}{2}\underset{h\in H}{\sup }\left[u_{m-1}(h)+sLh\left(x_m\right)\right]+\frac{1}{2}\underset{h\in H}{\sup }\left[u_{m-1}(h)-sLh\left(x_m\right)\right]\\ & =\underset{{\sigma }_m}{\mathrm{E}}\left[\underset{h\in H}{\sup }{u}_{m-1}(h)+{\sigma }_{m}Lh\left(x_m\right)\right]\end{array}$$

  令 $s=\text{sgn}(h_1(x_m)-h2(x_m))$，对所有其他 $i(i\ne m)$ 以相同的方式进行，得证。

二分类 SVM 的泛化误差界

定理 4.8 (关于 Rademacher 复杂度的泛化上界)

  令 $\mathcal{H}$ 为实值假设空间，给定 $\rho >0$，对于 $0<\delta <1$ 和 $h\in \mathcal{H}$，以至少 $1-\delta$ 的概率有

$$\begin{array}{c}E(h)⩽E_{\rho }(h)+\frac{2}{\rho }{\Re }_m(\mathcal{H})+\sqrt{\frac{\ln \frac{1}{\delta }}{2m}}\\ E(h)⩽E_{\rho }(h)+\frac{2}{\rho }{\Re }_D(\mathcal{H})+3\sqrt{\frac{\ln \frac{2}{\delta }}{2m}}\end{array}$$

证明

  构造 $\tilde{\mathcal{H}}=\{z=(x,y)\mapsto yh(x):h\in \mathcal{H}\}$，考虑值域为 $[0,1]$ 的假设空间 $\mathcal{F}=\left\{{\Phi }_{\rho }\circ f:f\in \tilde{\mathcal{H}}\right\}$ 由定理 4.4 知，对所有 $g\in \mathcal{F}$，以至少 $1-\delta$ 的概率有 :

$$\mathbb{E}[g(z)]⩽\frac{1}{m}\sum _{i=1}^{m}g(z_i)+2{\Re }_m(\mathcal{F})+\sqrt{\frac{\ln \frac{1}{\delta }}{2m}}$$

  因此对于 $h\in \mathcal{H}$，以至少 $1-\delta$ 的概率有:

$$\mathbb{E}[{\Phi }_{\rho }(yh(x))]⩽E_{\rho }(h)+2{\Re }_m\left({\Phi }_{\rho }\circ \tilde{\mathcal{H}}\right)+\sqrt{\frac{\ln \frac{1}{\delta }}{2m}}$$

  因为对 $\forall u\in \mathbb{R},{\mathbb{I}}_{u⩽0}⩽{\Phi }_{\rho }(u)$ 成立，所以

$$E(h)=\mathbb{E}\left[{\mathbb{I}}_{yh(x)⩽0}\right]⩽\mathbb{E}\left[{\Phi }_{\rho }(yh(x))\right]$$

  代入可知，以至少 $1-\delta$ 的概率有:

$$E(h)⩽E_{\rho }(h)+2{\Re }_m\left({\Phi }_{\rho }\circ \tilde{\mathcal{H}}\right)+\sqrt{\frac{\ln \frac{1}{\delta }}{2m}}$$

  由于 ${\Phi }_{\rho }$ 是 $\frac{1}{\rho }$-Lipschitz，由引理 4.4 可知

$${\Re }_m\left({\Phi }_{\rho }\circ \tilde{\mathcal{H}}\right)⩽\frac{1}{\rho }{\Re }_m(\tilde{\mathcal{H}})$$

  又由 Rademacher 复杂度定义知

$$\begin{array}{rl}{\Re }_m(\tilde{\mathcal{H}})=& \frac{1}{m}{\mathbb{E}}_{D,\sigma }\left[\underset{h\in \mathcal{H}}{\sup }\sum _{i=1}^m{\sigma }_i{y}_{i}h(x_i)\right]\\ =& \frac{1}{m}{\mathbb{E}}_{D,\sigma }\left[\underset{h\in \mathcal{H}}{\sup }\sum _{i=1}^m{\sigma }_{i}h(x_i)\right]\\ =& {\Re }_m(\mathcal{H})\end{array}$$

  代入得，以至少 $1-\delta$ 的概率有:

$$\begin{gathered} {\Re }_m\left({\Phi }_{\rho }\circ \tilde{\mathcal{H}}\right)⩽\frac{1}{\rho }{\Re }_m(\mathcal{H}) \\ \Rightarrow E(h)⩽E_{\rho }(h)+2{\Re }_m\left({\Phi }_{\rho }\circ \tilde{\mathcal{H}}\right)+\sqrt{\frac{\ln \frac{1}{\delta }}{2m}} \\ ⩽E_{\rho }(h)+\frac{2}{\rho }{\Re }_m(\mathcal{H})+\sqrt{\frac{\ln \frac{1}{\delta }}{2m}} \end{gathered}$$

  得证。由定理 4.4 可知，以至少 $1-\delta$ 的概率有:

$$\mathbb{E}[g(z)]⩽\frac{1}{m}\sum _{i=1}^{m}g(z_i)+2{\Re }_D(\mathcal{F})+3\sqrt{\frac{\ln \frac{2}{\delta }}{2m}}$$

  同理可证，以至少 $1-\delta$ 的概率有:

$$E(h)⩽E_{\rho }(h)+2{\Re }_D\left({\Phi }_{\rho }\circ \mathcal{H}\right)+3\sqrt{\frac{\ln \frac{2}{\delta }}{2m}}$$

  对于经验 Rademacher 复杂度，由于 ${\Phi }_{\rho }$ 是 $\frac{1}{\rho }$-Lipschitz，类似地有

$$\begin{array}{rl}& {\hat{\mathfrak{R}}}_D\left({\Phi }_{\rho }\circ \tilde{\mathcal{H}}\right)⩽\frac{1}{\rho }{\mathfrak{R}}_D(\tilde{\mathcal{H}})\\ & {\mathfrak{R}}_D(\tilde{\mathcal{H}})=\frac{1}{m}{\mathbb{E}}_{\sigma }\left[\underset{h\in \mathcal{H}}{\sup }\sum _{i=1}^m{\sigma }_i{y}_{i}h\left({\mathbf{x}}_i\right)\right]\\ & =\frac{1}{m}{\mathbb{E}}_{\mathbf{\sigma }}\left[\underset{h\in \mathcal{H}}{\sup }\sum _{i=1}^m{\sigma }_{i}h\left({\mathbf{x}}_i\right)\right]\\ & ={\hat{\mathfrak{R}}}_D(\mathcal{H})\end{array}$$

  则以至少 $1-\delta$ 的概率有:

$$E(h)⩽E_{\rho }(h)+\frac{2}{\rho }{\Re }_D(\mathcal{H})+3\sqrt{\frac{\ln \frac{2}{\delta }}{2m}}$$

定理 4.9

  令 $\mathcal{H}$ 为实值假设空间，对于 $0<\delta <1$ 和 $h\in \mathcal{H}$，以及任意 $\rho \in (0,1)$，以至少 $1-\delta$ 的概率有:

$$\begin{array}{rl}& E(h)⩽E_{\rho }(h)+\frac{4}{\rho }{\Re }_m(\mathcal{H})+\sqrt{\frac{\ln {\log }_2\frac{2}{\rho }}{m}}+\sqrt{\frac{\ln \frac{2}{\delta }}{2m}}\\ & E(h)⩽E_{\rho }(h)+\frac{4}{\rho }{\mathfrak{R}}_D(\mathcal{H})+\sqrt{\frac{{\ln }_{{\log }_2\frac{2}{\rho }}^m}{m}}+3\sqrt{\frac{\ln \frac{4}{\delta }}{2m}}\end{array}$$

  由定理 3.7 可知 ${\mathfrak{R}}_D(\mathcal{H})⩽\sqrt{\frac{r^2{\Lambda }^2}{m}}$，两边取期望得到，${\mathfrak{R}}_m(\mathcal{H})⩽\sqrt{\frac{r^2{\Lambda }^2}{m}}$

推论 4.1

  令 $\mathcal{H}=\{x\mapsto w\cdot x:|w|⩽\Lambda \}$ 且 $\Vert x\Vert ⩽r$，对于 $0<\delta <1$ 和 $h\in \mathcal{H}$ 和固定的 $\rho >0$，以至少 $1-\delta$ 的概率有:

$$E(h)⩽E_{\rho }(h)+2\sqrt{\frac{r^2{\Lambda }^2/{\rho }^2}{m}}+\sqrt{\frac{\ln \frac{1}{\delta }}{2m}}$$

推论 4.2

  令 $\mathcal{H}=\{x\mapsto w\cdot x:|w|⩽\Lambda \}$ 且 $\Vert x\Vert ⩽r$，对于 $0<\delta <1$ 和 $h\in \mathcal{H}$ 和任意的的 $\rho \in (0,1)$，以至少 $1-\delta$ 的概率有:

$$E(h)⩽E_{\rho }(h)+4\sqrt{\frac{r^2{\Lambda }^2/{\rho }^2}{m}}+\sqrt{\frac{\ln {\log }_2\frac{2}{\rho }}{m}}+\sqrt{\frac{\ln \frac{2}{\delta }}{2m}}$$

经验风险最小化

定义 4.2

  如果学习算法 $\mathfrak{L}$ 输出 $\mathcal{H}$ 中具有最小经验误差的假设 $h$，即 $\hat{E}(h)={\min }_{h^{\prime }\in \mathcal{H}}E(h^{\prime })$，则称 $\mathfrak{L}$ 为满足经验风险最小化原则的算法

  假设 $\mathfrak{L}$ 为满足经验风险最小化原则的算法，令 $g$ 表示 $\mathcal{H}$ 中具有最小泛化误差的假设，即 $E(h)={\min }_{h^{\prime }\in \mathcal{H}}E(h^{\prime })$ 由引理 2.1 可知，

$$P(|E(g)-E(g)|⩾\frac{ϵ}{2})⩽2\exp \left(-\frac{m{ϵ}^2}{2}\right)$$

  由于 ${\delta }^{\prime }=\frac{\delta }{2},\sqrt{\frac{(\ln 2/{\delta }^{\prime })}{2m}}⩽\frac{ϵ}{2}$，即 $2\exp \left(-\frac{m{ϵ}^2}{2}\right)⩽{\delta }^{\prime }$ 以至少 $1-\frac{\delta }{2}$ 的概率有:

$$E(g)-\frac{ϵ}{2}⩽E(g)⩽E(g)+\frac{ϵ}{2}$$

  由定理 4.3 可知，以至少 $1-\frac{\delta }{2}$ 的概率有:

$$|E(h)-E(h)|⩽\frac{ϵ}{2}$$

  即 $E(h)⩽E(h)+\frac{ϵ}{2}$ (根据经验最小化原则，$E(h)⩽E(g)$)，所以以至少 $1-\delta$ 的概率有:

$$\begin{array}{rl}E(h)-E(g)& ⩽E(h)+\frac{ϵ}{2}-\left(E(g)+\frac{ϵ}{2}\right)\\ & =E(h)-E(g)+ϵ\\ & ⩽ϵ\end{array}$$

  所以若学习算法 $\mathfrak{L}$ 输出 $\mathcal{H}$ 中具有最小经验误差的假设 $h$，其泛化误差
$E(h)$ 以至少 $1-\delta$ 的概率不大于最小泛化误差 $E(h)+ϵ$

结论

• 泛化误差边界不取决于维度，而取决于间隔
• 这需要我们在更高维的特征空间中寻找大间隔的超平面

计算问题

• 高维特征空间上使用点积是很昂贵的
• 可以使用核函数来解决

  Orz 快累死了。