5.2.4 留一法分析

我们现在使用留一法错误的概念来导出基于训练集中支持向量比例的第一个SVM学习保证。

定义5.2 留一法错误

令 $h_S$ 表示学习算法 $\mathcal{A}$ 在固定样本 $S$ 上训练时返回的假设。那么，$\mathcal{A}$ 在大小为 $m$ 的样本 $S$ 上的 留一法错误 定义为:

$${\hat{R}}_{\mathrm{LOO}}\left(\mathcal{A}\right)=\frac{1}{m}\sum _{i=1}^m{1}_{h_{S-\{x_i\}}\left(x_i\right)\ne y_i}.$$

因此，对于每一个 $i\in \left[m\right],\mathcal{A}$ 都在除了 $x_i$ 之外的所有 $S$ 上的点进行训练，即 $S-\left\{x_i\right\}$ ，然后使用 $x_i$ 计算其误差。 留一法误差是这些误差的平均值。 我们将使用留一法误差的一个重要性质，如下面的引理所述。

引理5.3

对于大小为 $m\ge 2$ 的样本的留一法误差的平均值是无偏估计，用于大小为 $m-1$ 的样本的平均泛化误差:

$$\underset{S\sim {\mathcal{D}}^m}{\mathbb{E}}\left[{\hat{R}}_{\mathrm{LOO}}\left(\mathcal{A}\right)\right]=\underset{S^{\prime }\sim {\mathcal{D}}^{m-1}}{\mathbb{E}}\left[R\left(h_{S^{\prime }}\right)\right]\text{\hspace{1em}(5.20)}$$

其中 $\mathcal{D}$ 表示从中抽取点的分布。

\begin{proof} 由于期望的线性，我们可以写出

$$\begin{array}{rl}\underset{S\sim {\mathcal{D}}^m}{\mathbb{E}}\left[{\hat{R}}_{\mathrm{LOO}}\left(\mathcal{A}\right)\right]& =\frac{1}{m}\sum _{i=1}^m\underset{S\sim {\mathcal{D}}^m}{\mathbb{E}}\left[1_{h_{S-\{x_i\}}(x_i)\ne y_i}\right]\\ & =\underset{S\sim {\mathcal{D}}^m}{\mathbb{E}}\left[1_{h_{S-\{x_1\}}(x_1)\ne y_1}\right]\\ & =\underset{S^{\prime }\sim {\mathcal{D}}^{m-1},x_1\sim \mathcal{D}}{\mathbb{E}}\left[1_{h_{S^{\prime }}(x_1)\ne y_1}\right]\\ & =\underset{S^{\prime }\sim {\mathcal{D}}^{m-1}}{\mathbb{E}}\left[\underset{x_1\sim \mathcal{D}}{\mathbb{E}}\left[1_{h_{S^{\prime }}(x_1)\ne y_1}\right]\right]\\ & =\underset{S^{\prime }\sim {\mathcal{D}}^{m-1}}{\mathbb{E}}\left[R(h_{S^{\prime }})\right].\end{array}$$

对于第二个等式，我们使用了这样一个事实:由于 $S$ 的点是独立同分布地抽取的，所以期望 ${\mathbb{E}}_{S\sim {\mathcal{D}}^m}\left[1_{h_{S-\{x_i\}}\left(x_i\right)\ne y_i}\right]$ 不依赖于 $i\in \left[m\right]$ 的选择，因此等于 ${\mathbb{E}}_{S\sim {\mathcal{D}}^m}\left[1_{h_{S-\{x_1\}}\left(x_1\right)\ne y_1}\right]$ 。 \end{proof}

通常，计算留一法误差可能是昂贵的，因为它需要在大小为 $m-1$ 的样本上训练 $m$ 次。 然而，在某些情况下，可以更有效地推导出 ${\hat{R}}_{\mathrm{LOO}}\left(\mathcal{A}\right)$ 的表达式(参见练习11.9)。

定理5.4

设 $h_S$ 是SVMs对于样本 $S$ 返回的假设，并且设 $N_{SV}\left(S\right)$ 是定义 $h_S$ 的支持向量的数量。那么，

$$\underset{S\sim {\mathcal{D}}^m}{\mathbb{E}}\left[R\left(h_S\right)\right]\le \underset{S\sim {\mathcal{D}}^{m+1}}{\mathbb{E}}\left[\frac{N_{\mathrm{SV}}\left(S\right)}{m+1}\right].$$

\begin{proof} 设 $S$ 是线性可分样本 $m+1$ 。如果 $x$ 不是 $h_S$ 的支持向量，移除它不会改变SVM的解。因此， $h_{S-\{x\}}=h_S$ 和 $h_{S-\{x\}}$ 正确分类 $x$ 。通过反证法，如果 $h_{S-\{x\}}$ 错误分类 $x,x$ 必须是一个支持向量，这意味着

$${\hat{R}}_{\mathrm{LOO}}\left(\mathrm{SVM}\right)\le \frac{N_{\mathrm{SV}}\left(S\right)}{m+1}.\text{\hspace{1em}(5.21)}$$

对两边取期望并使用引理5.3得到结果。 \end{proof}

定理5.4 为支持向量机提供了一个稀疏性论证: 算法的平均误差被支持向量的平均分数上界。 人们可能希望对于实践中看到的许多分布，相对较少的训练点将位于边缘超平面上。 那么解在意义上将是稀疏的，即一小部分对偶变量 ${\alpha }_i$ 将是非零的。 然而，请注意，这个界限相对较弱，因为它仅适用于所有大小为 $m$ 的样本的算法平均泛化误差。它没有提供关于泛化误差方差的信息。在5.4节中，我们使用基于边缘概念的不同论证，提出了更强的高概率界限。

图5.4 一个分离超平面，点 ${\mathbf{x}}_i$ 被错误分类，而点 ${\mathbf{x}}_j$ 被正确分类，但边缘小于1。