5.4 边界理论

本节介绍了泛化界限，为 SVM 算法提供了强有力的理论依据。

回顾一下，${\mathbb{R}}^N$ 中超平面或线性假设族的 VC 维数是 $N+1$ 。因此，将推论 3.19 中的 VC 维数界限(3.29)应用于这个假设集，得到以下结果:对于任意 $\delta >0$ ，以至少 $1-\delta$ 的概率，对于任意 $h\in \mathcal{H}$ ，

$$R\left(h\right)\le {\hat{R}}_S\left(h\right)+\sqrt{\frac{2\left(N+1\right)\log \frac{em}{N+1}}{m}}+\sqrt{\frac{\log \frac{1}{\delta }}{2m}}.\text{\hspace{1em}(5.36)}$$

当特征空间的维数 $N$ 与样本大小 $m$ 相比很大时，这个界限是不明确的。值得注意的是，本节中呈现的学习保证与维数 $N$ 无关，因此无论其值如何都成立。

我们即将提出的保证适用于实值函数，例如由SVMs返回的函数 $\mathbf{x}\mapsto \mathbf{w}\cdot \mathbf{x}+b$，与返回+1或-1的分类函数不同，例如 $\mathbf{x}\mapsto \mathrm{sgn}\left(\mathbf{w}\cdot \mathbf{x}+b\right)$。它们基于置信边距的概念。实值函数 $h$ 在标记为 $y$ 的点 $x$ 上的置信边距是量 $yh\left(x\right)$。因此，当 $yh\left(x\right)>0,h$ 正确分类 $x$ 时，我们将 $\left|h\left(x\right)\right|$ 的大小解释为 $h$ 所做预测的置信度。置信边距的概念与几何边距不同，且不需要线性可分性的假设。但是，在可分的情况下，这两个概念如下相关:对于具有几何边距 ${\rho }_{\text{geom }}$ 的 $h:\mathbf{x}\mapsto \mathbf{w}\cdot \mathbf{x}+b$，训练样本上任何标记为 $y$ 的点 $\mathbf{x}$ 的置信边距至少为 ${\rho }_{\text{geom }}\parallel \mathbf{w}\parallel$，即 $\left|yh\left(\mathbf{x}\right)\right|\ge {\rho }_{\text{geom }}\parallel \mathbf{w}\parallel$。

鉴于置信边距的定义，对于任何参数 $\rho >0$，我们将定义一个 $\rho$ -边距损失函数，该函数在错误分类点 $x\left(yh\left(x\right)\le 0\right)$ 时，与零一损失一样，对 $h$ 进行惩罚，其代价为1，但是如果 $h$ 正确分类 $x$ 且置信度小于或等于 $\rho \left(yh\left(x\right)\le \rho \right)$ 时，也会(线性地)对 $h$ 进行惩罚。本节主要基于边距的泛化界限，将以这个损失函数的形式呈现，该函数正式定义如下。

定义5.5(边距损失函数)对于任何 $\rho >0$，$\rho$ -边距损失是定义为所有 $y,y^{\prime }\in \mathbb{R}$ 的函数 $L_{\rho }:\mathbb{R}\times \mathbb{R}\to {\mathbb{R}}_{+}$，通过 $L_{\rho }\left(y,y^{\prime }\right)={\Phi }_{\rho }\left(y{y}^{\prime }\right)$ 来定义，且，

$${\Phi }_{\rho }\left(x\right)=\min \left(1,\max \left(0,1-\frac{x}{\rho }\right)\right)=\{\begin{array}{ll}1& \text{ if }x\le 0\\ 1-\frac{x}{\rho }& \text{ if }0\le x\le \rho \\ 0& \text{ if }\rho \le x\end{array}$$

这个损失函数在图5.6中有所说明。参数 $\rho >0$ 可以被解释为对假设 $h$ 所需求的置信边缘。经验边缘损失同样被定义为训练样本上的边缘损失。

定义5.6(经验边缘损失)$GivenasampleS=\left(x_1,\dots ,x_m\right)andahypoth$ - 假设 $h$ ，经验边缘损失定义为

$${\hat{R}}_{S,\rho }\left(h\right)=\frac{1}{m}\sum _{i=1}^m{\Phi }_{\rho }\left(y_{i}h\left(x_i\right)\right)\text{\hspace{1em}(5.37)}$$

注意，对于任何 $i\in \left[m\right],{\Phi }_{\rho }\left(y_{i}h\left(x_i\right)\right)\le 1_{y_{i}h\left(x_i\right)\le \rho }$ 。因此，经验边缘损失可以被以下方式上界:

$${\hat{R}}_{S,\rho }\left(h\right)\le \frac{1}{m}\sum _{i=1}^m{1}_{y_{i}h\left(x_i\right)\le \rho }.\text{\hspace{1em}(5.38)}$$

图5.6

以红色表示的边缘损失，是相对于边缘参数 $\rho =0.7$ 定义的。

在所有接下来的结果中，经验边缘损失可以被这个上界替代，它有一个简单的解释:它是训练样本 $S$ 中被错误分类或分类置信度小于 $\rho$ 的点的比例。换句话说，上界是训练数据中边缘小于 $\rho$ 的点的比例。这对应于图5.6中蓝色虚线表示的损失函数。

使用基于 ${\Phi }_{\rho }$ 的损失函数而不是零一损失或图5.6中蓝色虚线定义的损失的一个关键好处是 ${\Phi }_{\rho }$ 是 $1/\rho$ -Lipschitz连续的，因为函数斜率的绝对值最大为 $1/\rho$ 。以下引理将一个假设集 $\mathcal{H}$ 与此类Lipschitz函数复合后的经验Rademacher复杂性与 $\mathcal{H}$ 的经验Rademacher复杂性联系起来。它将被用于证明基于边缘的泛化界限。

定理 5.7(Talagrand 引理)设 ${\Phi }_1,\dots ,{\Phi }_m$ 为从 $\mathbb{R}$ 到 $\mathbb{R}$ 的 l-Lipschitz 函数，${\sigma }_1,\dots ,{\sigma }_m$ 为 Rademacher 随机变量。那么，对于任何实值函数的假设集 $\mathcal{H}$，以下不等式成立:

$$\frac{1}{m}\mathbb{E}\left[\underset{h\in \mathcal{H}}{\sup }\sum _{i=1}^m{\sigma }_i\left({\Phi }_i\circ h\right)\left(x_i\right))\right]\le \frac{l}{m}\mathbb{E}\left[\underset{h\in \mathcal{H}}{\sup }\sum _{i=1}^m{\sigma }_{i}h\left(x_i\right)\right]=l{\hat{\Re }}_S\left(\mathcal{H}\right).$$

特别地，如果 ${\Phi }_i=\Phi$ 对于所有 $i\in \left[m\right]$ 成立，那么以下结论成立:

$${\hat{\Re }}_S\left(\Phi \circ \mathcal{H}\right)\le l{\hat{\Re }}_S\left(\mathcal{H}\right)$$

证明:首先我们固定一个样本 $S=\left(x_1,\dots ,x_m\right)$，然后，根据定义，

$$\frac{1}{m}\underset{\sigma }{\mathbb{E}}\left[\underset{h\in \mathcal{H}}{\sup }\sum _{i=1}^m{\sigma }_i\left({\Phi }_m\circ h\right)\left(x_i\right)\right]=\frac{1}{m}\underset{{\sigma }_1,\dots ,{\sigma }_{m-1}}{\mathbb{E}}\left[\underset{{\sigma }_m}{\mathbb{E}}\left[\underset{h\in \mathcal{H}}{\sup }{u}_{m-1}\left(h\right)+{\sigma }_m\left({\Phi }_m\circ h\right)\left(x_m\right)\right]\right],$$

其中 $u_{m-1}\left(h\right)=\sum _{i=1}^{m-1}{\sigma }_i\left({\Phi }_i\circ h\right)\left(x_i\right)$。根据上确界的定义，对于任何

$ϵ>0$，存在 $h_1,h_2\in \mathcal{H}$ 使得

$$u_{m-1}\left(h_1\right)+\left({\Phi }_m\circ h_1\right)\left(x_m\right)\ge \left(1-ϵ\right)\left[\underset{h\in \mathcal{H}}{\sup }{u}_{m-1}\left(h\right)+\left({\Phi }_m\circ h\right)\left(x_m\right)\right]$$ $$\mathrm{and}{u}_{m-1}\left(h_2\right)-\left({\Phi }_m\circ h_2\right)\left(x_m\right)\ge \left(1-ϵ\right)\left[\underset{h\in \mathcal{H}}{\sup }{u}_{m-1}\left(h\right)-\left({\Phi }_m\circ h\right)\left(x_m\right)\right].$$

因此，对于任何 $ϵ>0$，根据 ${\mathbb{E}}_{{\sigma }_m}$ 的定义，

$$\left(1-ϵ\right)\underset{{\sigma }_m}{\mathbb{E}}\left[\underset{h\in \mathcal{H}}{\sup }{u}_{m-1}\left(h\right)+{\sigma }_m\left({\Phi }_m\circ h\right)\left(x_m\right)\right]$$ $$=\left(1-ϵ\right)\left[\frac{1}{2}\underset{h\in \mathcal{H}}{\sup }\left[u_{m-1}\left(h\right)+\left({\Phi }_m\circ h\right)\left(x_m\right)\right]+\frac{1}{2}\left[\underset{h\in \mathcal{H}}{\sup }{u}_{m-1}\left(h\right)-\left({\Phi }_m\circ h\right)\left(x_m\right)\right]\right]$$ $$\le \frac{1}{2}\left[u_{m-1}\left(h_1\right)+\left({\Phi }_m\circ h_1\right)\left(x_m\right)\right]+\frac{1}{2}\left[u_{m-1}\left(h_2\right)-\left({\Phi }_m\circ h_2\right)\left(x_m\right)\right].$$

设 $s=\mathrm{sgn}\left(h_1\left(x_m\right)-h_2\left(x_m\right)\right)$。那么，前一个不等式意味着

$$\left(1-ϵ\right)\underset{{\sigma }_m}{\mathbb{E}}\left[\underset{h\in \mathcal{H}}{\sup }{u}_{m-1}\left(h\right)+{\sigma }_m\left({\Phi }_m\circ h\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]\text{ (Lipschitz property) }$$ $$=\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]\text{ (rearranging) }$$ $$\le \frac{1}{2}\underset{h\in \mathcal{H}}{\sup }\left[u_{m-1}\left(h\right)+slh\left(x_m\right)\right]+\frac{1}{2}\underset{h\in \mathcal{H}}{\sup }\left[u_{m-1}\left(h\right)-slh\left(x_m\right)\right]\text{ (definition of sup) }$$ $$=\underset{{\sigma }_m}{\mathbb{E}}\left[\underset{h\in \mathcal{H}}{\sup }{u}_{m-1}\left(h\right)+{\sigma }_m\mathrm{lh}\left(x_m\right)\right].\text{ (definition of }\underset{{\sigma }_m}{\mathbb{E}}\text{ ) }$$

由于不等式对于所有 $ϵ>0$ 都成立，我们有

$$\underset{{\sigma }_m}{\mathbb{E}}\left[\underset{h\in \mathcal{H}}{\sup }{u}_{m-1}\left(h\right)+{\sigma }_m\left({\Phi }_m\circ h\right)\left(x_m\right)\right]\le \underset{{\sigma }_m}{\mathbb{E}}\left[\underset{h\in \mathcal{H}}{\sup }{u}_{m-1}\left(h\right)+{\sigma }_m\mathrm{lh}\left(x_m\right)\right].$$

对所有其他 ${\sigma }_i\left(i\ne m\right)$ 以相同的方式进行证明，得证引理。

下面是一个基于边界的通用泛化界限，它将被用于几个算法的分析中。

定理 5.8(二分类的边界界限)$Let\mathcal{H}beasetofreal$ - $valuedfunc$ - tions。固定 $\rho >0$，那么，对于任何 $\delta >0$，以至少 $1-\delta$ 的概率，以下对于所有 $h\in \mathcal{H}$ 成立:

$$R\left(h\right)\le {\hat{R}}_{S,\rho }\left(h\right)+\frac{2}{\rho }{\Re }_m\left(\mathcal{H}\right)+\sqrt{\frac{\log \frac{1}{\delta }}{2m}}\text{\hspace{1em}(5.39)}$$ $$R\left(h\right)\le {\hat{R}}_{S,\rho }\left(h\right)+\frac{2}{\rho }{\hat{\Re }}_S\left(\mathcal{H}\right)+3\sqrt{\frac{\log \frac{2}{\delta }}{2m}}.\text{\hspace{1em}(5.40)}$$

证明:设 $\tilde{\mathcal{H}}=\{z=\left(x,y\right)\mapsto yh\left(x\right):h\in \mathcal{H}\}$。考虑取值在 $\left[0,1\right]$ 中的函数族:

$$\tilde{\mathcal{H}}=\left\{{\Phi }_{\rho }\circ f:f\in \tilde{\mathcal{H}}\right\}$$

根据定理 3.3，以至少 $1-\delta$ 的概率，对于所有 $g\in \tilde{\mathcal{H}}$，

$$\mathbb{E}\left[g\left(z\right)\right]\le \frac{1}{m}\sum _{i=1}^{m}g\left(z_i\right)+2{\Re }_m\left(\tilde{\mathcal{H}}\right)+\sqrt{\frac{\log \frac{1}{\delta }}{2m}},$$

因此，对于所有 $h\in \mathcal{H}$，

$$\mathbb{E}\left[{\Phi }_{\rho }\left(yh\left(x\right)\right)\right]\le {\hat{R}}_{S,\rho }\left(h\right)+2{\Re }_m\left({\Phi }_{\rho }\circ \tilde{\mathcal{H}}\right)+\sqrt{\frac{\log \frac{1}{\delta }}{2m}}.$$

由于 $1_{u\le 0}\le {\Phi }_{\rho }\left(u\right)$ 对于所有 $u\in \mathbb{R}$ 成立，我们有 $R\left(h\right)=\mathbb{E}\left[1_{yh\left(x\right)\le 0}\right]\le \mathbb{E}\left[{\Phi }_{\rho }\left(yh\left(x\right)\right)\right]$，因此

$$R\left(h\right)\le {\hat{R}}_{S,\rho }\left(h\right)+2{\Re }_m\left({\Phi }_{\rho }\circ \tilde{\mathcal{H}}\right)+\sqrt{\frac{\log \frac{1}{\delta }}{2m}}.$$

由于 ${\Phi }_{\rho }$ 是 $1/\rho$ -Lipschitz，根据引理 5.7，我们有 ${\Re }_m\left({\Phi }_{\rho }\circ \tilde{\mathcal{H}}\right)\le \frac{1}{\rho }{\Re }_m\left(\tilde{\mathcal{H}}\right)$ 并且 ${\mathfrak{R}}_m\left(\tilde{\mathcal{H}}\right)$ 可以重写为以下形式:

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

这证明了(5.39)。第二个不等式(5.40)也可以用定理3.3的第二个不等式(3.4)代替(3.3)以同样的方式推导出来。

定理5.8的泛化界限表明了一种权衡:$\rho$的较大值会减少复杂度项(第二项)，但往往会通过要求假设$h$具有更高的置信边缘来增加经验边缘损失${\hat{R}}_{S,\rho }\left(h\right)$(第一项)。因此，如果对于相对较大的$\rho$值，$h$的经验边缘损失仍然相对较小，那么$h$将从对其泛化误差非常有利的保证中受益。对于定理5.8，边缘参数$\rho$必须预先选择。但是，定理的界限可以推广到对所有$\rho \in (0,1]$都成立，代价是增加一个适度额外的项$\sqrt{\frac{\log {\log }_2\frac{2}{\rho }}{m}}$，如下定理所示(可以导出此定理的具有更好常数的版本，见练习5.2)。

定理5.9 设$\mathcal{H}$是一组实值函数。固定$r>0$。那么，对于任何$\delta >0$，以至少$1-\delta$的概率，以下对所有$h\in \mathcal{H}$和$\rho \in (0,r]$都成立:

$$R\left(h\right)\le {\hat{R}}_{S,\rho }\left(h\right)+\frac{4}{\rho }{\Re }_m\left(\mathcal{H}\right)+\sqrt{\frac{\log {\log }_2\frac{2r}{\rho }}{m}}+\sqrt{\frac{\log \frac{2}{\delta }}{2m}}\text{\hspace{1em}(5.41)}$$ $$R\left(h\right)\le {\hat{R}}_{S,\rho }\left(h\right)+\frac{4}{\rho }{\hat{\Re }}_S\left(\mathcal{H}\right)+\sqrt{\frac{\log {\log }_2\frac{2r}{\rho }}{m}}+3\sqrt{\frac{\log \frac{4}{\delta }}{2m}}.\text{\hspace{1em}(5.42)}$$

证明:考虑两个序列${\left({\rho }_k\right)}_{k\ge 1}$和${\left({ϵ}_k\right)}_{k\ge 1}$，其中${ϵ}_k\in (0,1]$。根据定理5.8，对于任何固定的$k\ge 1$，

$$\mathbb{P}\left[\underset{h\in H}{\sup }R\left(h\right)-{\hat{R}}_{S,{\rho }_k}\left(h\right)>\frac{2}{{\rho }_k}{\mathfrak{R}}_m\left(\mathcal{H}\right)+{ϵ}_k\right]\le \exp \left(-2m{ϵ}_k^2\right)\text{\hspace{1em}(5.43)}$$

选择${ϵ}_k=ϵ+\sqrt{\frac{\log k}{m}}$，那么，根据并集界限，以下成立:

$$\mathbb{P}\left[\underset{\begin{array}{c}h\in H\\ h\ge 1\end{array}}{\sup }R\left(h\right)-{\hat{R}}_{S,{\rho }_k}\left(h\right)-\frac{2}{{\rho }_k}{\mathfrak{R}}_m\left(\mathcal{H}\right)-{ϵ}_k>0\right]$$ $$\le \sum _{k\ge 1}\exp \left(-2m{ϵ}_k^2\right)$$ $$=\sum _{k\ge 1}\exp \left[-2m{\left(ϵ+\sqrt{\left(\log k\right)/m}\right)}^2\right]$$ $$\le \sum _{k\ge 1}\exp \left(-2m{ϵ}^2\right)\exp \left(-2\log k\right)$$ $$=\left(\sum _{k\ge 1}1/k^2\right)\exp \left(-2m{ϵ}^2\right)$$ $$=\frac{{\pi }^2}{6}\exp \left(-2m{ϵ}^2\right)\le 2\exp \left(-2m{ϵ}^2\right).$$

我们可以选择 ${\rho }_k=r/2^k$ 。对于任何 $\rho \in (0,r]$ ，存在 $k\ge 1$ 使得 $\rho \in$ $\left({\rho }_k,{\rho }_{k-1}\right]$ ，并且 ${\rho }_0=r$ 。对于那个 $k,\rho \le {\rho }_{k-1}=2{\rho }_k$ ，因此 $1/{\rho }_k\le 2/\rho$ 以及 $\sqrt{\log k}=$ $\sqrt{\log {\log }_2\left(r/{\rho }_k\right)}\le \sqrt{\log {\log }_2\left(2r/\rho \right)}$ 。此外，对于任何 $h\in \mathcal{H},{\hat{R}}_{S,{\rho }_k}\left(h\right)\le$ ${\hat{R}}_{S,\rho }\left(h\right)$ 。因此，以下不等式成立:

$$\mathbb{P}\left[\underset{\begin{array}{c}h\in H\\ \rho \in (0,r]\end{array}}{\sup }R\left(h\right)-{\hat{R}}_{S,\rho }\left(h\right)-\frac{4}{\rho }{\Re }_m\left(\mathcal{H}\right)-\sqrt{\frac{\log {\log }_2\left(2r/\rho \right)}{m}}-ϵ>0\right]\le 2\exp \left(-2m{ϵ}^2\right),$$

这证明了第一个陈述。第二个陈述可以用类似的方法证明。

具有界权向量的线性假设的Rademacher复杂度可以以下式界定。

定理5.10 设 $S\subseteq \{\mathbf{x}:\parallel \mathbf{x}\parallel \le r\}$ 是大小为 $m$ 的样本，且 $\mathcal{H}=\{\mathbf{x}\mapsto$ $\mathbf{w}\cdot \mathbf{x}:\parallel \mathbf{w}\parallel \le \Lambda \}$ 。那么，$\mathcal{H}$ 的经验Rademacher复杂度可以以下式界定:

$${\hat{\Re }}_S\left(\mathcal{H}\right)\le \sqrt{\frac{r^2{\Lambda }^2}{m}}$$

证明:证明通过一系列不等式得出:

$${\hat{\Re }}_S\left(\mathcal{H}\right)=\frac{1}{m}\underset{\sigma }{\mathbb{E}}\left[\underset{\parallel \mathbf{w}\parallel \le \Lambda }{\sup }\sum _{i=1}^m{\sigma }_i\mathbf{w}\cdot {\mathbf{x}}_i\right]=\frac{1}{m}\underset{\sigma }{\mathbb{E}}\left[\underset{\parallel \mathbf{w}\parallel \le \Lambda }{\sup }\mathbf{w}\cdot \sum _{i=1}^m{\sigma }_i{\mathbf{x}}_i\right]$$ $$\le \frac{\Lambda }{m}\underset{\sigma }{\mathbb{E}}\left[\Vert \begin{array}{c}\sum _{i=1}^m{\sigma }_i{\mathbf{x}}_i\end{array}\Vert \right]\le \frac{\Lambda }{m}{\left[\underset{\sigma }{\mathbb{E}}\left[{\Vert \begin{array}{c}\sum _{i=1}^m{\sigma }_i{\mathbf{x}}_i\end{array}\Vert }^2\right]\right]}^{\frac{1}{2}}$$ $$=\frac{\Lambda }{m}{\left[\underset{\sigma }{\mathbb{E}}\left[\sum _{i,j=1}^m{\sigma }_i{\sigma }_j\left({\mathbf{x}}_i\cdot {\mathbf{x}}_j\right)\right]\right]}^{\frac{1}{2}}\le \frac{\Lambda }{m}{\left[\sum _{i=1}^m{\Vert \begin{array}{c}{\mathbf{x}}_i\end{array}\Vert }^2\right]}^{\frac{1}{2}}\le \frac{\Lambda \sqrt{m{r}^2}}{m}=\sqrt{\frac{r^2{\Lambda }^2}{m}},$$

第一个不等式利用了Cauchy-Schwarz不等式和 $\parallel \mathbf{w}\parallel$ 的界限，第二个由Jensen不等式得出，第三个由 $\mathbb{E}\left[{\sigma }_i{\sigma }_j\right]=\mathbb{E}\left[{\sigma }_i\right]\mathbb{E}\left[{\sigma }_j\right]=$ 0 对于 $i\ne j$ ，最后一个由 $\Vert \begin{array}{c}{\mathbf{x}}_i\end{array}\Vert \le r$ 得出。

结合定理5.10和定理5.8直接得到以下具有界权向量的线性假设的一般边缘界限，呈现在推论5.11中。

推论5.11 设 $\mathcal{H}=\{\mathbf{x}\mapsto \mathbf{w}\cdot \mathbf{x}:\parallel \mathbf{w}\parallel \le \Lambda \}$ 并且假设 $X\subseteq \{\mathbf{x}:\parallel \mathbf{x}\parallel \le r\}.$ 。固定 $\rho >0$ ，那么，对于任何 $\delta >0$ ，在样本 $S$ 大小为 $m$ 的选择上，至少以 $1-\delta$ 的概率，以下对于任何 $h\in \mathcal{H}$ 成立:

$$R\left(h\right)\le {\hat{R}}_{S,\rho }\left(h\right)+2\sqrt{\frac{r^2{\Lambda }^2/{\rho }^2}{m}}+\sqrt{\frac{\log \frac{1}{\delta }}{2m}}.\text{\hspace{1em}(5.44)}$$

与定理5.8一样，这个推论的界限可以通过结合定理5.10和定理5.9，以增加一个额外项 $\sqrt{\frac{\log {\log }_2\frac{2}{\rho }}{m}}$ 的代价，推广到对所有 $\rho \in (0,1]$ 一致成立。

线性假设的这个泛化界限非常引人注目，因为它不直接依赖于特征空间的维度，而只依赖于边界。它表明，当 $\rho /\left(r\Lambda \right)$ 较大(第二项较小)且经验边界损失相对较小(第一项)时，可以取得小的泛化误差。后者发生在只有少数点被错误分类或者虽然分类正确但边界小于 $\rho$ 的情况下。当训练样本线性可分时，对于具有几何边界 ${\rho }_{\text{geom }}$ 的线性假设和置信边界参数的选择 $\rho ={\rho }_{\text{geom }}$，经验边界损失项为零。因此，如果 ${\rho }_{\text{geom }}$ 相对较大，这为相应线性假设的泛化误差提供了强有力的保证。

保障不明确依赖于特征空间的维度这一事实可能令人惊讶，并且似乎与定理3.20和3.23的VC维数下界相矛盾。那些下界表明，对于任何学习算法 $\mathcal{A}$，都存在一个使算法返回的假设误差为 $\Omega \left(\sqrt{d/m}\right)$ 的不良分布，且概率非零。然而，推论的界限并没有排除这种不良情况:对于这样的不良分布，即使边界 $\rho$ 相对较小，经验边界损失也会很大，因此推论的界限在这种情况下会比较宽松。

因此，在某种意义上，推论的学习保障取决于良好边界值 $\rho$ 的期望:如果存在一个相对较大的边界值 $\rho >0$，使得经验边界损失较小，那么推论将保证小的泛化误差。这种有利的边界情况依赖于分布:尽管学习界限与分布无关，但良好边界的存在实际上是与分布相关的。在应用中，有利的边界似乎相对频繁出现。

推论的界限为支持最大化边缘算法(如支持向量机)提供了强有力的证明。选择 $\Lambda =1$ ，通过对推论5.11的泛化到一个关于 $\rho \in (0,r]$ 的均匀界限，对于任何 $\delta >0$ ，在至少 $1-\delta$ 的概率下，以下对所有 $h\in \{\mathbf{x}\mapsto \mathbf{w}\cdot \mathbf{x}:\parallel \mathbf{w}\parallel \le 1\}$ 和 $\rho \in (0,r]$ 都成立:

$$R\left(h\right)\le {\hat{R}}_{S,\rho }\left(h\right)+4\sqrt{\frac{r^2/{\rho }^2}{m}}+\sqrt{\frac{\log {\log }_2\frac{2r}{\rho }}{m}}+\sqrt{\frac{\log \frac{2}{\delta }}{2m}}.$$

不等式对于 $\rho$ 大于 $r$ 的情况也显然成立，因为在这种情况下，根据柯西-施瓦茨不等式，对于任何 $\mathbf{w}$ 且 $\parallel \mathbf{w}\parallel \le 1$ ，我们有 $y_i\left(\mathbf{w}\cdot {\mathbf{x}}_i\right)\le r\le \rho$ 并且 ${\hat{R}}_{S,\rho }\left(h\right)$ 对所有 $h$ 都等于一。

现在，对于任何 $\rho >0$ ，$\rho$ -边缘损失函数被 $\rho$ -折页损失所上界:

$$\forall u\in \mathbb{R},{\Phi }_{\rho }\left(u\right)=\min \left(1,\max \left(0,1-\frac{u}{\rho }\right)\right)\le \max \left(0,1-\frac{u}{\rho }\right).\text{\hspace{1em}(5.45)}$$

因此，在至少 $1-\delta$ 的概率下，以下对所有 $h\in \{\mathbf{x}\mapsto \mathbf{w}$ 、$\mathbf{x}:\parallel \mathbf{w}\parallel \le 1\}$ 和所有 $\rho >0$ 都成立:

$$R\left(h\right)\le \frac{1}{m}\sum _{i=1}^m\max \left(0,1-\frac{y_i\left(\mathbf{w}\cdot {\mathbf{x}}_i\right)}{\rho }\right)+4\sqrt{\frac{r^2/{\rho }^2}{m}}+\sqrt{\frac{\log {\log }_2\frac{2r}{\rho }}{m}}+\sqrt{\frac{\log \frac{2}{\delta }}{2m}}.$$

由于任何 $\rho >0,h/\rho$ 承认与 $h$ 相同的泛化误差，在至少 $1-\delta$ 的概率下，以下对所有 $h\in \{\mathbf{x}\mapsto \mathbf{w}\cdot \mathbf{x}:\parallel \mathbf{w}\parallel \le 1/\rho \}$ 和所有 $\rho >0$ 都成立:

$$R\left(h\right)\le \frac{1}{m}\sum _{i=1}^m\max \left(0,1-y_i\left(\mathbf{w}\cdot {\mathbf{x}}_i\right)\right)+4\sqrt{\frac{r^2/{\rho }^2}{m}}+\sqrt{\frac{\log {\log }_2\frac{2r}{\rho }}{m}}+\sqrt{\frac{\log \frac{2}{\delta }}{2m}}.\text{\hspace{1em}(5.46)}$$

这个不等式可以用来导出一个算法，该算法选择 $\mathbf{w}$ 和 $\rho >0$ 以最小化右边。关于 $\rho$ 的最小化不会导致一个凸优化，并且依赖于影响第二项和第三项的理论常数因子，这可能不是最优的。因此，相反，$\rho$ 被留作算法的一个自由参数，通常通过交叉验证来确定。

现在，由于右边只有第一项依赖于 $\mathbf{w}$ ，对于任何 $\rho >0$ ，界限建议选择 $\mathbf{w}$ 作为以下优化问题的解:

$$\underset{\parallel \mathbf{w}{\parallel }^2\le \frac{1}{{\rho }^2}}{\min }\frac{1}{m}\sum _{i=1}^m\max \left(0,1-y_i\left(\mathbf{w}\cdot {\mathbf{x}}_i\right)\right).\text{\hspace{1em}(5.47)}$$

引入拉格朗日变量 $\lambda \ge 0$，优化问题可以等价地写为

$$\underset{\mathbf{w}}{\min }\lambda \parallel \mathbf{w}{\parallel }^2+\frac{1}{m}\sum _{i=1}^m\max \left(0,1-y_i\left(\mathbf{w}\cdot {\mathbf{x}}_i\right)\right).\text{\hspace{1em}(5.48)}$$

由于对于(5.47)约束中任意选择的 $\rho$，在(5.48)公式中存在一个等价的对偶变量 $\lambda$，它实现了相同的最优 $\mathbf{w},\lambda$ 可以通过交叉验证自由选择。 ${}^5$ 得到的算法与支持向量机(SVMs)完全一致。请注意，另一种目标函数以及相应的算法将基于经验边缘损失而不是合页损失。然而，合页损失的优势在于它是凸的，而边缘损失则不是。

如前所述，刚刚讨论的界限并不直接依赖于特征空间的维度，而是在给定的有利边缘时保证良好的泛化。因此，它们建议在非常高维的空间中寻找大边缘分离超平面。鉴于SVMs对偶优化问题的形式，确定优化问题的解并将其用于预测都需要在该空间中计算许多内积。对于非常高维的空间，这些内积的计算可能会变得非常昂贵。下一章提供了这个问题的解决方案，该方案进一步将SVMs推广到非向量输入空间。