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

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

0 感言

  没什么太多感言了，拔刀吧！(orange 主题感觉非常鲜明，最近又把替代函数剩下部分补全了，学习笔记下也应该很快就能发布了)

6.1 基本概念

一些标记

$$\begin{array}{rl}\mathcal{X}& \text{样本空间, }\mathcal{X}\subseteq {\mathbb{R}}^d\\ \mathcal{Y}& \text{标签空间, }\mathcal{Y}=\{-1,+1\}\\ \mathcal{D}& \mathcal{X}\times \mathcal{Y}\text{ 上的联合概率分布}\\ {\mathcal{D}}_{\mathcal{X}}& \mathcal{X}\text{ 的边缘概率分布}\\ \eta (\mathbf{x})& \text{条件概率 }P(y=+1|\mathbf{x})\\ \mathbf{h}:\mathcal{X}\to \mathcal{Y}& \text{分类器}\end{array}$$

泛化风险

• 泛化风险 : 分类器在分布 $\mathcal{D}$ 上的分类错误率

$$\begin{array}{rl}R(h)& =P_{(x,y)\sim \mathcal{D}}(h(x)\ne y)=E_{(x,y)\sim \mathcal{D}}[\mathbb{I}(h(x)\ne y)]\\ & =E_{x\sim D_x}[\eta (x)\mathbb{I}(h(x)\ne +1)+(1-\eta (x))\mathbb{I}(h(x)\ne -1)]\\ & =E_{x\sim D_x}[\eta (x)\mathbb{I}(h(x)=-1)+(1-\eta (x))\mathbb{I}(h(x)=+1)]\end{array}$$

Bayes 分类器

• 贝叶斯最优分类器 ${\mathbf{h}}^{\ast }$ : 在分布 $\mathcal{D}$ 上取得最小错误率的分类器 (简称贝叶斯分类器)

$${\mathbf{h}}^{\ast }=\arg \underset{h}{\min }R(h)$$

Bayes 风险

• 贝叶斯风险 $R^{\ast }$ : 贝叶斯分类器的泛化风险

$$\begin{array}{rl}{R}^{\ast }& =R\left(h^{\ast }\right)\\ & =\underset{h}{\min }\{R(h)\}\\ & ={\mathbb{E}}_{\mathbf{x}\sim {\mathcal{D}}_{\mathcal{X}}}\left[\underset{h(\mathbf{x})}{\min }\{\eta (\mathbf{x})\mathbb{I}(h(\mathbf{x})=-1)+(1-\eta (\mathbf{x}))\mathbb{I}(h(\mathbf{x})=+1)\}\right]\end{array}$$

• 若分布 $\mathcal{D}$ 已知 (即 $\eta (\mathbf{x})$ 已知)，则可以直接根据分布给出贝叶斯分类器和贝叶斯风险:

	$\eta (\mathbf{x})⩾1-\eta (\mathbf{x})$	$\eta (\mathbf{x})<1-\eta (\mathbf{x})$
$\eta (\mathbf{x})$	$⩾\frac{1}{2}$	$<\frac{1}{2}$
$h^{\ast }(\mathbf{x})$	$+1$	$-1$
$R^{\ast }$	$1-\eta (\mathbf{x})$	$\eta (\mathbf{x})$

• 因此，

$$\begin{gathered} h^{\ast }(\mathbf{x})=2\mathbb{I}(\eta (\mathbf{x}⩾\frac{1}{2}))-1 \\ {R}^{\ast }=R(h^{\ast })={\mathbb{E}}_{\mathbf{x}\sim {\mathcal{D}}_x}[\min \{\eta (\mathbf{x}),1-\eta (\mathbf{x})\}] \end{gathered}$$

引理 6.1 (贝叶斯最优分类器 ${\mathbf{h}}^{\ast }$ 和一般的分类器 $\mathbf{h}$ 的关系)

  $\forall h:\mathcal{X}\to \mathcal{Y}$ 和贝叶斯最优分类器 $h^{\ast }$，满足

$$R(h)-R^{\ast }={\mathbb{E}}_{\mathbf{x}\sim {\mathcal{D}}_{\mathcal{X}}}\left[|1-2\eta (x)|\mathbb{I}(h(x)\ne h^{\ast }(x)\right]$$

证明

  对任意样本 $x\in \mathcal{X}$，令

$$\begin{array}{rl}\Delta (x)& =\eta (x)\mathbb{I}(h(x)=-1)+(1-\eta (x))\mathbb{I}(h(x)=+1)\\ & -\eta (x)\mathbb{I}(h^{\ast }(x)=-1)-(1-\eta (x))\mathbb{I}(h^{\ast }(x)=+1)\end{array}$$

  然后有

$$\begin{array}{rl}R(h)-R^{\ast }& ={\mathbb{E}}_{\mathbf{x}\sim {\mathcal{D}}_{\mathcal{X}}}\left[\eta (x)\mathbb{I}(h(x)=-1)+(1-\eta (x))\mathbb{I}(h(x)=+1)\right]\\ & -{\mathbb{E}}_{\mathbf{x}\sim {\mathcal{D}}_{\mathcal{X}}}\left[\eta (x)\mathbb{I}(h^{\ast }(x)=-1)+(1-\eta (x))\mathbb{I}(h^{\ast }(x)=+1)\right]\\ & ={\mathbb{E}}_{\mathbf{x}\sim {\mathcal{D}}_{\mathcal{X}}}\left[\Delta (x)\right]\end{array}$$

• 若 $\eta (x)>\frac{1}{2}$ 时，则 $h^{\ast }(x)=+1$，于是当 $h(x)=-1$ 时，$\Delta (x)=2\eta (x)-1$，当 $h(x)=+1$ 时，$\Delta (x)=0$，因此 $\Delta (x)=\mathbb{I}(h(x)\ne h^{\ast }(x))|1-2\eta (x)|$
• 同理可证当 $\eta (x)⩽\frac{1}{2}$ 时成立，引理得证。

  若数据分布 $\mathcal{D}$ 未知，常见的方法是通过训练集 ${\mathcal{D}}_m$ 估计条件概率，然后构建分类器

$$h(x)=2\mathbb{I}\left(\hat{\eta }(x)⩾\frac{1}{2}\right)-1$$

  这种基于条件概率估计的分类方法被称为插入 (plug-in) 法。

引理 6.2

  对插入法的分类器 $h(x)$ 有

$$R(h)-R^{\ast }⩽2{\mathbb{E}}_{\mathbf{x}\sim {\mathcal{D}}_{\mathcal{X}}}\left[|\eta (x)-\hat{\eta }(x)|\right]⩽2\sqrt{{\mathbb{E}}_{\mathbf{x}\sim {\mathcal{D}}_{\mathcal{X}}}\left[|\eta (x)-\hat{\eta }(x){|}^2\right]}$$

证明

  根据引理 6.1 可知 $R(h)-R^{\ast }={\mathbb{E}}_{\mathbf{x}\sim {\mathcal{D}}_{\mathcal{X}}}\left[|1-2\eta (x)|\mathbb{I}(h(x)\ne h^{\ast }(x)\right]$，根据 $h^{\ast }(x)=2\mathbb{I}(\eta (x)⩾\frac{1}{2})-1$ 和 $h(x)=2\mathbb{I}(\hat{\eta }(x)⩾\frac{1}{2})-1$

  当 $\mathbb{I}(h(x)\ne h^{\ast }(x)$ 时有 $\mathbb{I}(\hat{\eta }(X)⩾\frac{1}{2})\ne \mathbb{I}(\eta (x)⩾\frac{1}{2})$

• 若 $\hat{\eta }(x)⩾\frac{1}{2}$ 且 $\eta (x)<\frac{1}{2}$，则 $|1-2\eta (x)|=2|\frac{1}{2}-\eta (x)|⩽2|\hat{\eta }(x)-\eta (x)|$

• 若 $\hat{\eta }(x)<\frac{1}{2}$ 且 $\eta (x)⩾\frac{1}{2}$，则 $|1-2\eta (x)|=2|\frac{1}{2}-\eta (x)|⩽2|\hat{\eta }(x)-\eta (x)|$

  由此可得 $R(h)-R^{\ast }⩽2{\mathbb{E}}_{\mathbf{x}\sim {\mathcal{D}}_{\mathcal{X}}}\left[|\eta (x)-\hat{\eta }(x)|\right]$，再利用 Jensen 不等式，可得 $R(h)-{\mathbb{E}}_{\mathbf{x}\sim {\mathcal{D}}_{\mathcal{X}}}\left[|\eta (x)-\hat{\eta }(x)|\right]⩽\sqrt{{\mathbb{E}}_{\mathbf{x}\sim {\mathcal{D}}_{\mathcal{X}}}\left[|\eta (x)-\hat{\eta }(x){|}^2\right]}$，引理得证。

  学习算法 $\mathfrak{L}$ 基于训练集 $D_m$ 学习得到分类器 ${\mathfrak{L}}_{D_m}$，随着训练集规模 $m$ 的增加，可以得到一系列分类器 ${\mathfrak{L}}_{D_1},{\mathfrak{L}}_{D_2},\dots ,{\mathfrak{L}}_{D_m},\dots$

定义 6.1 一致性 (consistency)

  当 $m\to \infty$，若学习算法 $\mathfrak{L}$ 满足 ${\mathbb{E}}_{D_m\sim {\mathcal{D}}^m}\left[R({\mathfrak{L}}_{D_m})\right]\to R(h^{\ast })$，则称学习算法 $\mathfrak{L}$ 是一致的。

  直观来说，一致性反映了在训练数据足够多的情形下，算法 $\mathfrak{L}$ 能否学习得到贝叶斯最优分类器；在理论上，一致性刻画了学习算法 $\mathfrak{L}$ 在无限多数据情形下学习的性能极限。

6.2 替代函数

  对二分类问题，常见的方法是学习一个实值函数 $f:\mathcal{X}\to \mathbb{R}$，然后根据实值函数输出函数得到分类器

$$h(x)=\{\begin{array}{ll}+1& f(x)⩾0\\ -1& f(x)<0\end{array}$$

  实值函数 $f$ 在分布 $\mathcal{D}$ 上的泛化风险为

$$\begin{array}{rl}R(f)=& {\mathbb{E}}_{(\mathbf{x},\mathbf{y})\sim \mathcal{D}}\left[\mathbb{I}(\mathbf{y}f(\mathbf{x}))\right]\\ =& {\mathbb{E}}_{(\mathbf{x},\mathbf{y})\sim {\mathcal{D}}_{\mathcal{X}}}\left[\eta (\mathbf{x})\mathbb{I}(f(\mathbf{x})⩽0)+(1-\eta (\mathbf{x}))\mathbb{I}(f(\mathbf{x})⩾0)\right]\end{array}$$

  考虑到 Bayes 风险和 Bayes 实值函数

$$\begin{gathered} R^{\ast }=R(h^{\ast })={\mathbb{E}}_{\mathbf{x}\sim {\mathcal{D}}_{\mathcal{X}}}[\min \{\eta (\mathbf{x}),1-\eta (\mathbf{x})\}] \\ \begin{array}{rl}{f}^{\ast }\in {\mathcal{F}}^{\ast }=\{f:\text{当}& \eta (x)=\frac{1}{2}\text{ 时，}f(x)\text{ 可以是任意的实数}\\ & \eta (x)\ne \frac{1}{2}\text{ 时，}f(x)\left(\eta (x)-\frac{1}{2}>0\right)\}\end{array} \end{gathered}$$

  给定训练集 $D_m=\{(x_1,y_1),(x_2,y_2),\dots ,(x_m,y_m)\}$ 和实值函数 $f$，函数 $f$ 在训练集 $D_m$ 上的分类错误率为

$$\frac{1}{m}\sum _{i=1}^m\mathbb{I}(y_{i}f(x_i)⩽0)$$

  其本质上是泛化风险 $R(f)$ 的一种无偏估计，$\mathbb{I}(y_{i}f(x_i)⩽0)$ 是非凸不连续的，因此直接优化上式是 NP 难问题。因此在现实算法设计中可以对 $\mathbb{I}(y_{i}f(x_i)⩽0)$ 进行凸放松，用一个具有良好数学性质的凸函数 $\varphi :\mathbb{R}\mapsto \mathbb{R}$ 进行替代。考虑一般的替代函数

$$\ell (f(\mathbf{x}),\mathbf{y})=\varphi (\mathbf{y}f(\mathbf{x}))$$

  其中 $\varphi$ 是连续的凸函数或光滑的连续函数。替代函数本质上也是损失函数，这里使用 “替代” 主要针对 $0/1$ 目标函数进行连续凸放松的替代。

机器学习中常用的替代函数

• 平方函数 $\varphi (t)=(1-t{)}^2$
• Hinge 函数 $\varphi (t)=\max (0,t-1)$
• 指数函数 $\varphi (t)=e^{-t}$
• 对率函数 $\varphi (t)=\ln (1+e^{-t})$

  常见的替代函数如下图所示

替代泛化风险 (surrogate generalization risk)

• 替代泛化风险 : 给定替代函数 $\varphi$，它在数据分布 $\mathcal{D}$ 上的泛化风险，定义为

$$R_{\varphi }(f)={\mathbb{E}}_{(\mathbf{x},\mathbf{y})\sim \mathcal{D}}\left[\varphi (\mathbf{y}f(\mathbf{x}))\right]$$

• 最优替代泛化风险 :

$$R_{\varphi }^{\ast }=\min \left(R_{\varphi }(f)\right)$$

• 替代经验风险 (surrogate empirical risk)，它是替代泛化风险 $R_{\varphi }(f)$ 在训练集上的无偏估计

$$\frac{1}{m}\sum _{i=1}^m\varphi (y_{i}f(x_i))$$

定义 6.2 替代函数一致性

  随着训练数据规模 $m\to \infty$，通过优化替代经验风险得到一系列输出函数 ${\hat{f}}_1,{\hat{f}}_2,\dots ,{\hat{f}}_m,\dots$ 若 $R_{\varphi }({\hat{f}}_m)\to R_{\varphi }^{\ast }$ 时有 $R({\hat{f}}_m)\to R^{\ast }$ 成立，则称替代函数 $\varphi$ 对原目标函数具有一致性，简称替代函数一致性

  下面研究满足什么性质的替代函数，才具有对原 $0/1$ 目标函数的一致性，根据替代泛化风险和最优替代泛化风险的定义，我们有

$$\begin{array}{rl}{R}_{\varphi }(f)& ={\mathbb{E}}_{\mathbf{x}\sim {\mathcal{D}}_{\mathcal{X}}}\left[\eta (x)\varphi (f(x))+(1-\eta (x))\varphi (-f(x))\right]\\ R_{\varphi }^{\ast }& ={\mathbb{E}}_{\mathbf{x}\sim {\mathcal{D}}_{\mathcal{X}}}\left[\underset{f(x)\in \mathbb{R}}{\min }\left(\eta (x)\varphi (f(x))+(1-\eta (x))\varphi (-f(x))\right)\right]\end{array}$$

  从而得到替代函数的最优实值输出函数 $f_{\varphi }^{\ast }(x)$ 为

$$f_{\varphi }^{\ast }(\mathbf{x})\in \arg \underset{f(\mathbf{x})\in \mathbb{R}}{\min }(\eta (\mathbf{x})\varphi (f(\mathbf{x}))+(1-\eta (\mathbf{x}))\varphi (-f(\mathbf{x})))$$

定理 6.1 替代函数一致性的充分条件

  对替代函数 $\varphi$，若最优实值输出函数满足 $f_{\varphi }^{\ast }\in {\mathcal{F}}^{\ast }$，且存在常数 $c>0$ 和 $s⩾1$ 使

$${\left|\eta (x)-\frac{1}{2}\right|}^{\mathcal{S}}⩽c^{\mathcal{S}}\left(\varphi (0)-\eta (x)\varphi \left(f_{\varphi }^{\ast }(x)\right)-(1-\eta (x))\varphi \left(-f_{\varphi }^{\ast }(x)\right)\right)$$

证明

  回顾一致性的定义，我们发现当 $R({\hat{f}}_m)\to R^{\ast }$ 与 $R_{\varphi }({\hat{f}}_m)\to R_{\varphi }^{\ast }$ 时，替代函数满足一致性要求。

  故证明分为以下三点

• 计算 $R({\hat{f}}_m)\to R^{\ast }$
• 计算 $R_{\varphi }({\hat{f}}_m)\to R_{\varphi }^{\ast }$
• 将 $R({\hat{f}}_m)\to R^{\ast }$ 与 $R_{\varphi }({\hat{f}}_m)\to R_{\varphi }^{\ast }$ 相结合

  下面沿着思路划分开始证明

1. 计算 $R({\hat{f}}_m)\to R^{\ast }$

  回顾

$$\begin{gathered} R(f)={\mathbb{E}}_{(\mathbf{x},\mathbf{y})\sim {\mathcal{D}}_{\mathcal{X}}}\left[\eta (\mathbf{x})\mathbb{I}(f(\mathbf{x})⩽0)+(1-\eta (\mathbf{x}))\mathbb{I}(f(\mathbf{x})⩾0)\right] \\ {R}^{\ast }={\mathbb{E}}_{\mathbf{x}\sim {\mathcal{D}}_{\mathcal{X}}}[\min \{\eta (\mathbf{x}),1-\eta (\mathbf{x})\}] \end{gathered}$$

  所以

$$\begin{array}{rl}R(f)-R^{\ast }& ={\mathbb{E}}_{(\mathbf{x},\mathbf{y})\sim {\mathcal{D}}_{\mathcal{X}}}\left[\eta (\mathbf{x})\mathbb{I}(f(\mathbf{x})⩽0)+(1-\eta (\mathbf{x}))\mathbb{I}(f(\mathbf{x})⩾0)\right]\\ & -{\mathbb{E}}_{\mathbf{x}\sim {\mathcal{D}}_{\mathcal{X}}}[\min \{\eta (\mathbf{x}),1-\eta (\mathbf{x})\}]\\ & ={\mathbb{E}}_{\mathbf{x}\sim {\mathcal{D}}_{\mathcal{X}}}\left[{\Delta }_1(x)\right]\end{array}$$

  其中

$${\Delta }_1(x)=\eta (x)\mathbb{I}(f(x)⩽0)+(1-\eta (x))\mathbb{I}(f(x)⩾0)-\min \{\eta (x),1-\eta (x)\}$$

• 根据 $\eta (x)-\frac{1}{2}$ 和 $f(x)$ 的不同取值，分五种情况讨论 ${\Delta }_1(x)$ :
  • $\eta (x)>\frac{1}{2}$且 $f(x)>0$ 时，有 ${\Delta }_1(x)=0$
  • $\eta (x)>\frac{1}{2}$且 $f(x)⩽0$ 时，有 ${\Delta }_1(x)=2\eta (x)-1$
  • $\eta (x)<\frac{1}{2}$且 $f(x)⩾0$ 时，有 ${\Delta }_1(x)=1-2\eta (x)$
  • $\eta (x)<\frac{1}{2}$且 $f(x)<0$ 时，有 ${\Delta }_1(x)=0$
  • $\eta (x)=\frac{1}{2}$，${\Delta }_1(x)=0$

  所以有

$$\begin{array}{rl}& {\Delta }_1(\mathbf{x})=2\mathbb{I}(\eta (\mathbf{x})-\frac{1}{2})f(\mathbf{x})\le 0)|\eta (\mathbf{x})-\frac{1}{2}|\\ & R(f)-R^{\ast }=2{\mathbb{E}}_{(\eta (\mathbf{x})-\frac{1}{2})f(\mathbf{x})\le 0}[|\eta (\mathbf{x})-\frac{1}{2}|]\end{array}$$

  根据 Jensen 不等式 $(\mathbb{E}[X])⩽\sqrt[\mathcal{S}]{\mathbb{E}[X^{\mathcal{S}}]}$，有

$$R(f)-R^{\ast }⩽2\sqrt[\mathcal{S}]{{\mathbb{E}}_{(\eta (\mathbf{x})-\frac{1}{2})f(\mathbf{x})\le 0}[|\eta (\mathbf{x})-\frac{1}{2}{|}^{\mathcal{S}}]}$$

  定义

$$\begin{array}{c}{\Delta }_2(\mathbf{x})=\eta (\mathbf{x})\varphi (f(\mathbf{x}))+(1-\eta (\mathbf{x}))\varphi (-f(\mathbf{x}))\\ {\Delta }_3(\mathbf{x})=\eta (\mathbf{x})\varphi \left(f_{\varphi }^{\ast }(\mathbf{x})\right)+(1-\eta (\mathbf{x}))\varphi \left(-f_{\varphi }^{\ast }(\mathbf{x})\right)\end{array}$$

  在充分条件下，

$$R(f)-R^{\ast }⩽2c\sqrt[\mathcal{S}]{{\mathbb{E}}_{(\eta (\mathbf{x})-\frac{1}{2})f(\mathbf{x})\le 0}[\varphi (0)-{\Delta }_3(\mathbf{x})]}$$

2. 计算 $R_{\varphi }({\hat{f}}_m)\to R_{\varphi }^{\ast }$

  回顾

$$\begin{array}{rl}{R}_{\varphi }(f)& ={\mathbb{E}}_{(\mathbf{x},\mathbf{y})\sim \mathcal{D}}\left[\varphi (yf(x)\right]\\ & ={\mathbb{E}}_{\mathbf{x}\sim {\mathcal{D}}_{\mathcal{X}}}\left[\eta (x)\varphi (f(x))+(1-\eta (x))\varphi (-f(x))\right]\\ R_{\varphi }^{\ast }& ={\mathbb{E}}_{\mathbf{x}\sim {\mathcal{D}}_{\mathcal{X}}}\left[\underset{f(x)\in \mathbb{R}}{\min }\left(\eta (x)\varphi (f(x))+(1-\eta (x))\varphi (-f(x))\right)\right]\end{array}$$

  所以

$$\begin{array}{rl}{R}_{\varphi }(f)-R_{\varphi }^{\ast }& ={\mathbb{E}}_{x\sim {\mathcal{D}}_{\mathcal{X}}}[{\Delta }_2(x)-{\Delta }_3(x)]\\ & ⩾{\mathbb{E}}_{(\eta (\mathbf{x})-\frac{1}{2})f(\mathbf{x})\le 0}[{\Delta }_2(x)-{\Delta }_3(x)]\end{array}$$

  这里 ${\Delta }_3(x)$ 正好包含在充分条件中。

3. 将 $R({\hat{f}}_m)\to R^{\ast }$ 与 $R_{\varphi }({\hat{f}}_m)\to R_{\varphi }^{\ast }$ 相结合

$$\begin{array}{rl}R(f)-R^{\ast }⩽& 2c\sqrt[\mathcal{S}]{{\mathbb{E}}_{(\eta (\mathbf{x})-0.5)f(\mathbf{x})\le 0}\left[\varphi (0)-{\Delta }_3(\mathbf{x})\right]}\\ & \cdots \\ ⩽& 2c\sqrt[\mathcal{S}]{{\mathbb{E}}_{(\eta (\mathbf{x})-0.5)f(\mathbf{x})\le 0}\left[{\Delta }_2(\mathbf{x})-{\Delta }_3(\mathbf{x})\right]}\\ ⩽& 2c^{\mathcal{S}}\sqrt[\mathcal{S}]{R_{\varphi }(f)-R_{\varphi }^{\ast }}\end{array}$$

  下面即证明 $\varphi (0)⩽{\Delta }_2(x)$，令 $\Gamma (t)=\eta (\mathbf{x})\varphi (t)+(1-\eta (\mathbf{x}))\varphi (-t)$ 现在 $\Gamma (f(x))={\Delta }_2(x)$ 和 $\Gamma (0)=\varphi (0)$，根据凸函数的性质可知，当 $\varphi (t)$ 是凸函数时 $\Gamma (t)$ 也是凸函数，以及当 $0\in [a,b]$ 时有 $\Gamma (0)⩽\max \{\Gamma (a),\Gamma (b)\}$。下面分三种情况讨论 :

• 若 $\eta (x)>\frac{1}{2}$，则 $f_{\varphi }^{\ast }(x)>0$，由 $\left(\eta (x)-\frac{1}{2}\right)f(x)⩽0$ 可知 $f(x)⩽0$，故 $\varphi (0)=\Gamma (0)⩽\max \{\Gamma (f(x)),\Gamma (f_{\varphi }^{\ast }(x))\}$，又因为 $\Gamma (f(x))⩾\Gamma (f_{\varphi }^{\ast }(x))$，于是 ${\varphi }_0⩽\Gamma (f(x))={\Delta }_2(x)$

• 若 $\eta (x)<\frac{1}{2}$，同理有 $f_{\varphi }^{\ast }(x)<0,f(x)⩾0$，以 $\varphi (0)=\Gamma (0)⩽\max \{\Gamma (f(x)),\Gamma (f_{\varphi }^{\ast }(x))\}=\Gamma (f(x))={\Delta }_2(x)$

• 若 $\eta (x)=\frac{1}{2}$，对凸函数 $\varphi$ 有 $\varphi (0)⩽\frac{\varphi (f(x))}{2}+\frac{\varphi (-f(x))}{2}={\Delta }_2(x)$

证毕。

支持向量机 (support vector machine, SVM)

  支持向量机 (support vector machine, SVM) 的替代函数是 hinge 函数

$$\varphi (t)=\max (0,t-1)$$

  在这个实例中，我们希望证明 hinge 函数的一致性。

引理 6.3

  优化 hinge 函数 $\varphi (t)=\max (0,1-t)$ 得到输出函数

$$f_{\varphi }^{\ast }(x)=\{\begin{array}{ll}\mathrm{sign}(2\eta (x)-1)& \eta (x)\ne 1/2\\ \forall c\in [-1,1]& \eta (x)=1/2\end{array}$$

  是最优实值输出函数，其对应的最优替代泛化风险为 $R_{\varphi }^{\ast }=2{\mathbb{E}}_{x\sim {\mathcal{D}}_{\mathcal{X}}}[\min \left(\eta (x),1-\eta (x)\right)]$。

证明

   将 hinge 函数 $\varphi (t)=\max (0,1-t)$ ，代入可得

$$\begin{array}{rl}{R}_{\varphi }(f)& ={\mathbb{E}}_{(\mathbf{x},y)\sim \mathcal{D}}[\varphi (yf(\mathbf{x}))]\\ & ={\mathbb{E}}_{\mathbf{x}\sim {\mathcal{D}}_{\mathcal{X}}}[\eta (\mathbf{x})\varphi (f(\mathbf{x}))+(1-\eta (\mathbf{x}))\varphi (-f(\mathbf{x}))]\\ & ={\mathbb{E}}_{\mathbf{x}\sim {\mathcal{D}}_{\mathcal{X}}}[\eta (\mathbf{x})\max (0,1-f(\mathbf{x}))+(1-\eta (\mathbf{x}))\max (0,1+f(\mathbf{x}))]\end{array}$$

  令 $\alpha =f(\mathbf{x})$，则有

$$\begin{gathered} f_{\varphi }^{\ast }(\mathbf{x})\in \arg \underset{\alpha \in \mathbb{R}}{\min }(\eta (\mathbf{x})\max (0,1-\alpha )+(1-\eta (\mathbf{x}))\max (0,1+\alpha )) \\ =\arg \underset{\alpha \in \mathbb{R}}{\min }g(\alpha ) \\ g(\alpha )=\{\begin{array}{ll}\eta (\mathbf{x})(1-\alpha )& \alpha ⩽1\\ 1+\alpha (1-2\eta (\mathbf{x}))& \alpha \in [-1,+1]\\ (1-\eta (\mathbf{x}))(1+\alpha )& \alpha ⩾1\end{array} \end{gathered}$$

  根据 $f_{\varphi }^{\ast }(x)={\mathrm{argmin}}_{\alpha \in \mathbb{R}}g(\alpha )$

$$f_{\varphi }^{\ast }(x)=\{\begin{array}{ll}1& \eta (x)>\frac{1}{2}\\ \forall c\in [-1,1]& \eta (x)=\frac{1}{2}\\ -1& \eta (x)<\frac{1}{2}\end{array}$$

  将函数 $f_{\varphi }^{\ast }(x)$ 代入替代泛化风险可得

$$R_{\varphi }^{\ast }=R_{\varphi }\left(f_{\varphi }^{\ast }(x)\right)=2{\mathbb{E}}_{x\sim {\mathcal{D}}_{\mathcal{X}}}[\min \left(\eta (x),1-\eta (x)\right)]$$

  引理得证

定理 6.2

  hinge 函数 $\varphi (t)=\max (0,1-t)$ 针对原 $0/1$ 目标函数具有替代一致性。

证明

  根据引理 6.3 可知优化 hinge 函数 $\varphi (t)=\max (0,1-t)$ 所得的最优实值输出函数 $f_{\varphi }^{\ast }(x)=\{\begin{array}{ll}\mathrm{sign}(2\eta (x)-1)& \eta (x)\ne 1/2\\ \forall c\in [-1,1]& \eta (x)=1/2\end{array}$，显然 $f_{\varphi }^{\ast }(x)\in {\mathcal{F}}^{\ast }$。

  给定样本 $x\in \mathcal{X}$，我们有

• 当 $\eta (x)>\frac{1}{2}$ 时，$f_{\varphi }^{\ast }(x)=1$，$\varphi (0)-\eta (x)\varphi \left(f_{\varphi }^{\ast }(x)\right)-(1-\eta (x))\varphi \left(-f_{\varphi }^{\ast }(x)\right)=2\left|\eta (x)-\frac{1}{2}\right|$
• 当 $\eta (x)<\frac{1}{2}$ 时，$f_{\varphi }^{\ast }(x)=-1$，$\varphi (0)-\eta (x)\varphi \left(f_{\varphi }^{\ast }(x)\right)-(1-\eta (x))\varphi \left(-f_{\varphi }^{\ast }(x)\right)=2\left|\eta (x)-\frac{1}{2}\right|$
• 当 $\eta (x)=\frac{1}{2}$ 时，$f_{\varphi }^{\ast }(x)\in [-1,+1]$，$\varphi (0)-\eta (x)\varphi \left(f_{\varphi }^{\ast }(x)\right)-(1-\eta (x))\varphi \left(-f_{\varphi }^{\ast }(x)\right)=2\left|\eta (x)-\frac{1}{2}\right|$

  取 $c=\frac{1}{2},s=1$，由定理 6.1 可知 hinge 函数针对原 $0/1$ 函数具有替代一致性，定理得证。

  支持向量机常用的另一种替代函数是平方 hinge 函数:

$$\varphi (t)=(\max (0,1-t){)}^2$$

定理 6.3

  证明平方 hinge 函数的一致性。

证明

  当 $f_{\varphi }^{\ast }\in {\mathcal{F}}^{\ast }$ 且 $\exists c>0,s⩾1$ 使得

$${\left|\eta (\mathbf{x})-\frac{1}{2}\right|}^s\le c^s\left[\varphi (0)-\eta (\mathbf{x})\varphi \left(f_{\varphi }^{\ast }(\mathbf{x})\right)-(1-\eta (\mathbf{x}))\varphi \left(-f_{\varphi }^{\ast }(\mathbf{x})\right)\right]$$

  则替代函数 $\varphi$ 是一致的。我们同时有 $f_{\varphi }^{\ast }(x)=2\eta (x)-1,\varphi (f_{\varphi }^{\ast }(x))=(1-f_{\varphi }^{\ast }(x){)}^2$，将 $f_{\varphi }^{\ast }(x)$ 代入可得

$$\begin{gathered} \left[\varphi (0)-\eta (\mathbf{x})\varphi \left(f_{\varphi }^{\ast }(\mathbf{x})\right)-(1-\eta (\mathbf{x}))\varphi \left(-f_{\varphi }^{\ast }(\mathbf{x})\right)\right] \\ =1-4\eta (\mathbf{x})(1-\eta (\mathbf{x}))=4{\left|\eta (\mathbf{x})-\frac{1}{2}\right|}^2 \end{gathered}$$

  让 $c=\frac{1}{2},s=2$，即可得证