第四章介绍了在两个完美可分类别之间构建最优分离超平面的方法。我们回顾这个方法并推广到不可分的情况中，即类别之间可能没有线性边界可以分隔开。
训练集数据为 $N$ 个样本 $(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)$，其中 $x_i\in\mathbb{R}^p$ 以及 $y_i\in\{-1,1\}$。一个超平面（hyperplane）可定义为：
$$\\{x : f(x) = x^T\beta + \beta_0 = 0\\} \tag{12.1}$$其中 $\beta$ 是单位向量：$\|\beta\|=1$。$f(x)$ 定义出的分类规则为：
$$G(x) = \text{sign}[x^T\beta + \beta_0] \tag{12.2}$$第 4.5 节回顾了超平面的代数几何性质，定义 12.1 中的函数 $f(x)$ 即为一个点 $x$ 到超平面 $f(x)=x^T\beta+\beta_0=0$ 的有向距离（signed distance）。由于类别是可分的，所以可以找到一个满足条件 $y_if(x_i)>0$ $\forall i$ 的函数 $f(x)=x^T\beta+\beta_0$。所以能够找出在训练样本中与类别 1 和 -1 间隔最大的超平面（见图 12.1）。这个思路可表达为最优化问题：
$$\begin{gather} \max_{\beta, \beta_0, \|\beta\| = 1} M \\ \text{subject to } y_i (x_i^T\beta + \beta_0) \geq M, i = 1,\dots,M \end{gather}\tag{12.3}$$图中的阴影范围边界在超平面两侧的距离均为 $M$ 个单位，因此阴影的宽度为 $2M$ 个单位。这个范围称为间隔（margin）。
已证明过这个问题可更方便地重写为：1
$$\begin{gather} \min_{\beta, \beta_0} \|\beta\| \\ \text{subject to } y_i (x_i^T\beta + \beta_0) \geq 1, i = 1,\dots,M \end{gather}\tag{12.4}$$上面去掉了 $\beta$ 的单位约束，并有 $M=1/\|\beta\|$。式 12.4 是可分离样本数据的支持向量准则的通常表达方法。这是一个凸优化问题（二次准则函数，线性不等式约束条件），第 4.5.2 节介绍了这个问题的解。
现在假设不同的类别在特征空间上存在重叠。一种处理重叠的方法是依然对 $M$ 求最大，但允许一些点落在间隔线误分类的一侧。定义松弛变量2（slack variable）为 $\xi=(\xi_1,\xi_2,\dots,\xi_N)$。则对 12.3 中的约束条件有两种自然的改写方法：
$$\begin{align} y_i (x_i^T\beta + \beta_0) &\geq M - \xi_i \tag{12.5} \\ &\text{or} \\ y_i (x_i^T\beta + \beta_0) &\geq M (1 - \xi_i) \tag{12.6} \end{align}$$其中 $\forall i,\xi_i\geq0,\sum_{i=1}^N\xi_i\leq\text{常数}$。两个不同的选择会得出不同的解。第一个方法看起来更自然，因为它用与间隔的实际绝对距离来描述重叠距离3；第二个方法用相对距离来描述重叠距离，当间隔宽度 $M$ 变化时重叠距离会随之变化。不过方法一是非凸优化问题，而方法二是凸优化问题。因此“标准”的支持向量分类器使用的是方法二，我们接下来也将使用约束条件 12.6。
可以这样理解这个约束不等式。约束条件 $y_i(x_i^T\beta+\beta_0)\geq M(1-\xi_i)$ 中的 $\xi_i$ 值，是预测值 $f(x_i)=x_i^T\beta+\beta_0$ 在间隔（虚线）误分类一侧的距离（与间隔大小的）比例值。因此只要限制比例值的和 $\sum\xi_i$，就限制住了预测值落入间隔的误分类一侧的总比例值。当 $\xi_i>1$ 时，意味着预测分类是误分类，所以控制 $\sum\xi_i$ 的上限值为 $K$，其意义就是控制了训练集的误分类总数上限为 $K$。
与第 4.5.2 节 的 4.48 式类似，可以去掉 $\beta$ 的单位模约束，并令 $M=1/\|\beta\|$，则 12.4 式可等价地写为：
$$\min \|\beta\| \text{ subject to } \begin{cases} y_i (x_i^T\beta + \beta_0) \geq 1 - \xi_i \, \forall i \\ \xi_i \geq 0, \sum \xi_i \leq \text{常数}. \end{cases}\tag{12.7}$$这便是支持向量分类器在类别不可分情况下的通常定义方式。不过约束条件 $y_i(x_i^T\beta+\beta_0)\geq1-\xi_i$ 中的常量“1”不好理解，所以本书中会使用式 12.6。图 12.1 的右图掩饰了类别重叠的情况。
从式 12.7 中可看出，深处在类别边界内部的样本点对构造边界不会起到什么作用。这可能是一个很有用的性质，这一点也与线性判别分析（第 4.3 节）不同。线性判别分析的决策边界是由（所有样本的）类别分布协方差和类别中心点的的位置决定的。第 12.3.3 节 将说明在这个差异上，对数几率回归（逻辑回归）与支持向量分类器更相似。
12.2.1 支持向量分类器的计算 😱
最优化问题 12.7 的目标是二次函数约束是线性不等式，因此它是一个凸优化问题。下面介绍一个基于拉格朗日乘子（Lagrange multiplier）的二次规划解法。为了计算的方便，把式 12.7 写为等价的形式：
$$\begin{align} & \min_{\beta, \beta_0} \frac{1}{2} \|\beta\|^2 + C \sum_{i=1}^N \xi_i \\ & \text{subject to } \xi \geq 0, y_i (x_i^T\beta + \beta_0) \geq 1 - \xi_i \, \forall i \end{align}\tag{12.8}$$其中使用了一个“成本”参数 $C$ 代替了式 12.7 中的常数（constant）；在类别可分的问题中，$C = \infty$。
拉格朗日原始（primal）函数为：
$$\begin{align} L_p =& \frac{1}{2} \|\beta\|^2 + C \sum_{i=1}^N \xi_i \\ & -\sum_{i=1}^N \alpha_i [y_i (x_i^T\beta + \beta_0) - (1-\xi_i)] - \sum_{i=1}^N \mu_i \xi_i \end{align}\tag{12.9}$$对 $\beta$、$\beta_0$、和 $\xi_i$ 求最小化。设置相应的一阶导数为 0，可得到等式：
$$\begin{align} \beta &= \sum_{i=1}^N \alpha_i y_i x_i \tag{12.10} \\ 0 &= \sum_{i=1} \alpha_i y_i \tag{12.11} \\ \alpha_i &= C - \mu_i, \forall i \tag{12.12} \end{align}$$以及非负的约束条件 $\alpha_i,\mu_i,\xi_i\geq0,\forall i$。将式 12.10-12.12 带入到式 12.9 中，则得到了拉格朗日对偶目标函数：
$$L_D = \sum_{i=1}^N \alpha_i - \frac{1}{2}\sum_{i=1}^N \sum_{i'=1}^N \alpha_i \alpha_{i'} y_i y_{i'} x_i^T x_{i'} \tag{12.13}$$这是目标函数 12.8 的任意取值下的下界。在 $0\leq\alpha_i\leq C$ 和 $\sum_{i=1}^N\alpha_iy_i=0$ 条件下对 $L_D$ 求最大。除式 12.10-12.12 外，KKT（Karush–Kuhn–Tucker）条件4 附加了以下约束，对任意 $i=1,2,\dots,N$：
$$\begin{align} a_i [y_i (x_i^T\beta + \beta_0) - (1 - \xi_i)] &= 0 \tag{12.14} \\ \mu_i \xi_i &= 0 \tag{12.15} \\ y_i (x_i^T\beta + \beta_0) - (1 - \xi_i) & \geq 0 \tag{12.16} \end{align}$$等式组 12.10-12.16 可确定原始和对偶问题的唯一解。
从式 12.10 中可得 $\beta$ 的解为：
$$\hat{\beta} = \sum_{i=1}^N \hat{\alpha}_i y_i x_i \tag{12.17}$$（由式 12.14 可得）只有使不等式约束 12.16 严格成立的样本点 $i$ 才对应着非负的参数估计 $\hat{\alpha}_i$。因为 $\hat{\beta}$ 的表达式只依赖于这些样本点，他们被称为 支持向量（support vectors）。在这些样本点中，一部分会落在间隔的边缘上（$\hat{\xi}_i=0$），因此式 12.15 和式 12.12 可由 $0<\hat{\alpha}_i<C$ 确定；其余的点（$\hat{\xi}_i>0$）则为 $\hat{\alpha}_i=C$。从式 12.14 可见将任意的间隔边缘点（$0<\hat{\alpha}_i$，$\hat{\xi}_i=0$）均可带入后解出 $\beta_0$，而通常会用所有解的平均值以获得更稳定的数值计算结果。
与原始目标函数 12.9 相比，对偶目标函数 12.13 的最大化是个更简单的凸二次规划问题，可通过一些常规的方法求解（例如 Murray et at., 1981）。
带入最优解 $\hat{\beta}_0$ 和 $\hat{\beta}$，决策函数可写为：
$$\begin{align} \hat{G}(x) &= \operatorname{sign}[\hat{f}(x)] \\ &= \operatorname{sign}[x^T\hat{\beta} + \hat{\beta}_0] \tag{12.18} \end{align}$$上述计算过程中，待调整的参数为成本参数 $C$。
12.2.2 例：混合分布（续）
图 12.2 演示了在图 2.5 中的混合分布例子中存在两个重叠的类别时的支持向量边界，两个图为不同的成本参数 $C$。两个分类器的表现比较相近。在判别边界误分类一侧的点均为支持向量。另外，在边界正确分类一边但比较接近的（在间隔范围内）的点也为支持向量。$C=0.01$ 的间隔比 $C=10,000$ 的间隔区域更大。因此对于边界正确分类的点中，$C$ 的取值越大，模型越关注判别边界附近的点；而取值越小则会同时考虑距离更远的点。误分类的点则不管距离判别边界多远，都会参与到计算中。在这个例子中，分类模型对 $C$ 的选择并不太敏感，这是由线性边界的限制导致的。
最优的 $C$ 值可通过第 7.10 节介绍的交叉验证估计得出。值得注意的是，留一法（leave-one-out）交叉验证误差的上界就是样本中支持点的占比。其原因是去掉一个非支持点的样本后模型的解保持不变。因此被原判别边界正确分类的点，在交叉验证的过程中仍然会被正确分类。不过这个上界通常过高，对选择 $C$ 一般没有什么作用（在这个例子里分别为 62% 和 85%)。