5.2 可分情况

内容

• 5.2.1 原始优化问题
• 5.2.2 支持向量
• 5.2.3 对偶优化问题
• 5.2.4 留一法分析

介绍

在这一节中，我们假设训练样本 $S$ 可以线性分离，也就是说，我们假设存在一个超平面，能够完美地将训练样本分离成两个分别标记为正负的点集，如 ^fig-5-1 左侧面板所示。

fig 5.1 两个可能的分隔超平面。 右侧的图形显示了一个最大化边缘的超平面。

这等同于存在 $\left(\mathbf{w},b\right)\in \left({\mathbb{R}}^N-\{0\}\right)\times \mathbb{R}$ 使得

$$\forall i\in \left[m\right],y_i\left(\mathbf{w}\cdot {\mathbf{x}}_i+b\right)\ge 0.\text{\hspace{1em}(5.3)}$$

但如 ^fig-5-1 所示，存在无限多个这样的分离超平面。 学习算法应该选择哪一个超平面呢？ SVM 解决方案的定义基于 定义5.1 几何边缘 的概念。

线性分类器 $h$ 对于样本 $S=\left({\mathbf{x}}_1,\dots ,{\mathbf{x}}_m\right)$ 的几何边缘 ${\rho }_h$ 是样本点上的最小几何边缘 ${\rho }_h=\underset{i\in \left[m\right]}{\min }{\rho }_h\left(x_i\right),$ 即定义 $h$ 的超平面到最近样本点的距离。

SVM解决方案是具有最大几何间隔的分隔超平面，因此被称为 最大间隔超平面。 ^fig-5-1 右面板展示了在可分情况下 SVM 算法返回的最大间隔超平面。

在本章后面，我们将介绍一个理论，为这个解决方案提供有力的证明。 然而，我们目前已经可以观察到，SVM 解决方案也可以被视为在以下意义上 “最安全” 的选择:

• 即使测试点落在与具有相同标签的训练样本的距离 $\rho$ 内，分隔超平面也能以几何间隔 $\rho$ 正确分类测试点；
• 对于 SVM 解决方案，$\rho$ 是最大几何间隔，因此是最“安全”的值。