上文所介绍的线性判别分析和对数几率回归，都是在估计线性判别边界，估计的方法略有不同。下面介绍的是分离超平面分类器。这类模型构建一个试图直接将样本尽可能最大程度地分类的线性决策边界。第十二章中的支持向量机分类器即以此方法为基础。相较于本章其他内容，本节会涉及较多的数学知识。
图 4.14 中为在 $\mathbb{R}^2$ 空间上的 20 个二分类数据点。这些样本可被某个线性边界分离开。这种 分离超平面（separating hyperplane） 有无穷多个，图中的蓝色直线为两个例子。橙色直线为这个分类问题的最小二乘解，即用 -1 和 1 的输出变量 $Y$ 对 $X$ 进行带截距的回归，其表达式为：
$$\{x: \hat{\beta}_0 + \hat{\beta}_1 x_1 + \hat{\beta}_2 x_2 = 0 \} \tag{4.39}$$最小二乘解没有完美区分样本点，其中有一个误分类的点。在二分类问题中，线性判别分析与线性回归是等价的（第 4.3 节 以及练习 4.2），所以这也是线性判别分析的决策边界。
类似于等式 4.39 中的分类器，会根据输入特征变量的线性组合的符号进行分类，在 1950 年代末的工程领域（Rosenblatt, 1958）称之为 感知机（perceptrons）。而感知机则是 1980 和 1990 年代的神经网络模型的基础。
在继续讨论之前，下面介绍一些可能会涉及到的向量代数基础。图 4.15 中为一个超平面或仿射集 $L$，可定义为等式 $f(x)=\beta_0+\beta^Tx=0$；在 $\mathbb{R}^2$ 空间上，超平面即为一条直线。
以下为一些代数性质：
- 集合（直线） $L$ 上的任意两点 $x_1$ 和 $x_2$ 都满足 $\beta^T(x_1-x_2)=0$，因此平面 $L$ 的单位法向量1为 $\beta^*=\beta/\|\beta\|$。
- $L$ 上的任意一点 $x_0$ 都满足：$\beta^Tx_0=-\beta_0$。
- 任意点与 $L$ 的有向距离（signed distance）为 $$\begin{align} {\beta^*}^T (x-x_0) &= \frac{1}{\|\beta\|} (\beta^T x + \beta_0) \\ &= \frac{1}{\|f'(x)\|} f(x) \tag{4.40}\end{align}$$
因此某个点2 $z$ 与等式 $f(x)=0$ 定义的超平面的有方向距离，和 $f(z)$ 的值成正比。
4.5.1 Rosenblatt 感知机学习算法
感知机学习算法（perceptron learning algorithm） 通过对误分类点与决策边界之间的距离求最小来寻找分离超平面。若一个点的真实分类为 $y_i=1$ 但被误分类为 $-1$，则说明 $x_i^T\beta+\beta_0<0$；对 $y_i=-1$ 的点则相反。最小化的目标函数为：
$$D(\beta, \beta_0) = -\sum_{i \in \mathcal{M}} y_i(x_i^T\beta + \beta_0) \tag{4.41}$$其中的 $\mathcal{M}$ 代表被误分类点的集合。这个函数取值非负，并且和误分类点与决策边界 $\beta^Tx+\beta_0=0$ 的距离成正比。梯度函数为（假定 $\mathcal{M}$ 为已知集合）：
$$\begin{align} \frac{\partial D(\beta, \beta_0)}{\partial \beta} &= -\sum_{i \in \mathcal{M}} y_i x_i \tag{4.42} \\ \frac{\partial D(\beta, \beta_0)}{\partial \beta_0} &= -\sum_{i \in \mathcal{M}} y_i \tag{4.43} \end{align}$$事实上这个算法使用了 随机梯度下降（stochastic gradient descent） 来对这个分段线性的准则函数求解最小化。传统的梯度下降方法先求出每个样本对梯度向量的贡献之和，再向梯度向量的反方向更新参数；而这个算法对每个样本依次计算并相应地更新参数。因而误分类的点会按一定顺序依次进入计算，参数 $\beta$ 的更新过程为：
$$\begin{pmatrix} \beta \\ \beta_0 \end{pmatrix} \leftarrow \begin{pmatrix} \beta \\ \beta_0 \end{pmatrix} + \rho \begin{pmatrix} y_i x_i \\ y_i \end{pmatrix} \tag{4.44}$$其中的 $\rho$ 为学习率，在本例中不失一般性地可设为 1。若样本的分类在空间中为线性可分，则可证明这个算法在有限步骤之后收敛到一个分离超平面（练习 4.6）。图 4.14 中展示了虚拟例子中的两个分离超平面的解，两者的初始值为不同的随机猜测。
Ripley (1996) 概括了这个算法的一些问题：
- 若数据样本的类型可分离，则解不唯一，算法的初始值决定了收敛到哪个解上。
- 虽然收敛所需的步骤是有限的，但有可能是个很大的数字。样本分类在空间上的间隙越小，所需的步骤越多。
- 当数据的类型不可分离，则算法可能不收敛，而且会形成无法跳出的循环。这个循环有可能很长，使其难以被探测到。
第二个问题通常可以通过空间的扩展来解决，即将原始的输入变量进行基函数转换，然后在引入了很多新输入变量的扩展空间上计算分离超平面。这与在多项式回归模型问题中输入变量的多项式次数足够大后会得到 0 残差的原理类似。不过数据也并不一定会是完全可分的，一个简单的例子是当样本中出现两个输入变量相同但分类不同的点。另外，这样（扩展空间）也未必有益，因为得到的模型很可能存在过拟合、泛化表现不好。本节末也会重提这个观点。
第一个问题可以通过给分离超平面加上额外的约束来解决。
4.5.2 最优分离超平面 😱
最优分离超平面（optimal separating hyperplane） 将两个类别分离，并且使每个类别中最接近的点与平面的距离最大（Vapnik, 1996）。这不仅为分离超平面问题提供了唯一解，而且将训练集中两个类别样本之间的距离最大化也可改善其在测试数据中的分类表现。
需要扩展准则函数 4.41，则最优化问题为：
$$\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, N \end{gather}\tag{4.45}$$这组约束条件保证了所有的点与 $\beta$ 和 $\beta_0$ 确定的判别边界之间的（有向）距离都大于 $M$，最优化的解为最大距离 $M$ 和相应的参数。若去掉 $\|\beta\|=1$ 的约束，则约束条件需要改写为：
$$\frac{1}{\|\beta\|} y_i(x_i^T\beta + \beta_0) \geq M \tag{4.46}$$注意 4.45 和 4.46 中的 $\beta_0$ 不同。或等价地：
$$ y_i(x_i^T \beta + \beta_0) \geq M \|\beta\| \tag{4.47}$$任意满足这些不等式的 $\beta$ 和 $\beta_0$，乘以一个正的常数后依然满足这些不等式，因此可任意地固定 $\|\beta\|=1/M$。则 4.45 可写为：
$$\begin{gather} \min_{\beta, \beta_0} \frac{1}{2}\|\beta\|^2 \\ \text{subjext to } y_i(x_i^T\beta + \beta_0) \geq 1, i = 1,\dots, N \end{gather}\tag{4.48}$$通过式 4.40，可以理解为这些约束条件在线性决策边界周围定义了厚度为 $1/\|\beta\|$ 的空白间隔区域。而 $\beta$ 和 $\beta_0$ 的最优解会使区域的厚度最大。这是一个凸优化问题（二次准则函数和线性不等式的约束条件）。对 $\beta$ 和 $\beta_0$ 求最小的拉格朗日函数（原函数，primal function）为：
$$L_P = \frac{1}{2} \|\beta\|^2 - \sum_{i=1}^N \alpha_i[y_i(x_i^T\beta + \beta_0) - 1] \tag{4.49}$$将一阶导数设为 0：
$$\begin{align} \beta &= \sum_{i=1}^N \alpha_i y_i x_i \tag{4.50} \\ 0 &= \sum_{i=1}^N \alpha_i y_i \tag{4.51} \end{align}$$将结果带入到等式 4.49，即为 Wolfe 对偶问题：
$$\begin{align} L_D = & \sum_{i=1}^N \alpha_i - \sum_{i=1}^N\sum_{k=1}^N \alpha_i \alpha_k y_i y_k x_i^T x_k \\ & \text{subject to } \alpha_i \geq 0 \text{ and } \sum_{i=1}^N \alpha_i y_i = 0 \tag{4.52}\end{align}$$在正象限（positive orthant）上最大化 $L_D$ 可得到解，这是一个简单的凸优化问题，大多软件都实现了求解方法。另外，这个解须满足卡罗需-库恩-塔克（Karush–Kuhn–Tucker）条件，包括式 4.50、4.51、4.52、以及
$$ \alpha_i[y_i(x_i^T\beta + \beta_0) - 1] = 0 \text{ } \forall i \tag{4.53}$$从中可见：
- 若 $\alpha_i>0$，则 $y_i(x_i^T\beta+\beta_0)=1$，或者说 $x_i$ 位于间隔的边界；
- 若 $y_i(x_i^T\beta+\beta_0)>1$，则 $x_i$ 不在间隔的边界，且 $\alpha_i=0$。
从等式 4.50 可见向量 $\beta$ 的解的形式为 支持点（support point） 的线性组合，即有 $\alpha_i>0$ 的、位于间隔边界上的点 $x_i$。图 4.16 展示了虚拟例子中的最优分离超平面，其中有三个支持点。与之相似，$\beta_0$ 可从式 4.53 求解得出，也是支持点的线性组合。
最优分离超平面构建了一个可用来对新样本分类的判定函数 $\hat{f}(x)=x^T\hat{\beta}+\hat{\beta}_0$：
$$ \hat{G}(x) = \operatorname{sign} \hat{f}(x) \tag{4.54}$$从算法设计上保证了训练样本中没有落入边际区域的点，但测试样本仍有可能落入这个区间。从直观上可认为，在训练集上间隔大的模型，在测试集上可能表现更好。
最优分离超平面的解可写为支持点的形式，因此这个方法貌似更聚焦于“有用”的样本点，而且可能对模型误设（misspecification）更稳健。相比之下，线性判别分析（LDA）的解则依赖所有的数据，包括那些距离决策边界很远的点。但需要注意的是要找出这些支持点也是需要依赖所有的样本数据。而且，若真实的类别服从高斯分布，则线性判别分析为最优的方法，而分离超平面却过于关注类别边界附近的样本（而不是类别中心），会造成很大的干扰。
图 4.16 中也加入了用最大似然拟合的对数几率回归的解。在这个例子中，两个解非常相似。当分离超平面存在时（样本类别可分），对数似然度可以取值到 0，所以对数几率回归的解也必然是一个分离超平面（练习 4.5）。对数几率回归与分离超平面的解还有另外的一些相似特性。它的系数可理解为输出变量 $y_i$ 的零和线性转换后对输入变量的加权最小二乘拟合3，而且其在决策边界附近点的权重也要大于远离边界的点。
当数据中的类别不可分离，这个方法没有可行的解，需要对问题的定义进行修改。同样地，用基函数转化来扩大输入变量空间可能解决这个问题，但这可能会因为过拟合从而实现不真实的分离。第十二章中的支持向量机可以提供一个更好的解决方法，允许类别的重叠并且最小化重叠的程度。