5.3 非线性可分情况

在大多数实际情况下，训练数据不是线性可分的，这意味着对于任何超平面 $\mathbf{w}\cdot \mathbf{x}+b=0$ ，都存在 ${\mathbf{x}}_i\in S$ 使得

$$y_i\left[\mathbf{w}\cdot {\mathbf{x}}_i+b\right]1\text{\hspace{1em}(5.22)}$$

因此，在5.2节中讨论的线性可分情况下施加的约束不能同时成立。然而，这些约束的放松版本确实可以成立，即对于每个 $i\in \left[m\right]$ ，都存在 ${\xi }_i\ge 0$ 使得

$$y_i\left[\mathbf{w}\cdot {\mathbf{x}}_i+b\right]\ge 1-{\xi }_i\text{\hspace{1em}(5.23)}$$

变量 ${\xi }_i$ 被称为松弛变量，通常用于优化中定义约束的松弛版本。在这里，一个松弛变量 ${\xi }_i$ 衡量向量 ${\mathbf{x}}_i$ 违反期望不等式 $y_i\left(\mathbf{w}\cdot {\mathbf{x}}_i+b\right)\ge 1$ 的程度。图 5.4 描述了这种情况。对于一个超平面 $\mathbf{w}\cdot \mathbf{x}+b=0$ ，一个具有 ${\xi }_i>0$ 的向量 ${\mathbf{x}}_i$ 可以被视为异常值。每个 ${\mathbf{x}}_i$ 都必须定位在正确的边际超平面的一侧，以不被视为异常值。因此，一个具有 $0<y_i\left(\mathbf{w}\cdot {\mathbf{x}}_i+b\right)<1$ 的向量 ${\mathbf{x}}_i$ 虽然被超平面 $\mathbf{w}\cdot \mathbf{x}+b=0$ 正确分类，但仍然被视为异常值，即 ${\xi }_i>0$ 。如果我们忽略异常值，训练数据就可以通过 $\mathbf{w}\cdot \mathbf{x}+b=0$ 以一个称为软边界的边缘 $\rho =1/\parallel \mathbf{w}\parallel$ 被正确分开，这与可分情况下的硬边界相对。

在不可分情况下，我们应该如何选择超平面？一个想法是选择使经验误差最小化的超平面。但是，这个解决方案将无法从我们将在第 5.4 节中提出的大的边界保证中受益。此外，确定具有最小零一损失的超平面的问题，即最小化误分类数量的问题，作为空间维度 $N$ 的函数是 NP-难问题。

在这里，有两个相互冲突的目标:一方面，我们希望限制由于异常值造成的总松弛量，这可以通过 $\sum _{i=1}^m{\xi }_i$ 来衡量，或者更一般地通过 $\sum _{i=1}^m{\xi }_i^p$ 对于某些 $p\ge 1$ 来衡量；另一方面，我们寻求具有大边界的超平面，尽管更大的边界可能导致更多的异常值，从而产生更多的松弛量。

5.3.1 原始优化问题

5.3.2 支持向量

5.3.3 对偶优化问题