本文介绍曾经一度取代过神经网络的另一种监督学习算法——支持向量机（Support Vector Machine，SVM）。这是一种经典的二分类模型，基本定义为特征空间中最大间隔的线性分类器，其学习的优化目标即为间隔最大化，因此支持向量机本身可以转化为一个凸二次规划求解的问题。
1 间隔与支持向量
给定二分类问题训练样本集D=\{(\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),\dots,(\mathbf{x}_m,y_m)\},y_i\in \{-1,+1\}，分类学习最基本的想法为基于训练集D在样本空间中找到一个划分超平面，将不同类别的样本分开。存在多种划分方法，如下图所示
在样本空间中，划分超平面可通过如下线性方程来描述
\begin{aligned}
\mathbf{w}^\top \mathbf{x}+b=0
\end{aligned}其中\mathbf{w}=(w_1;w_2;\dots;w_d)为法向量，决定了超平面的方向；b为位移项，决定了超平面与原点之间的距离。样本空间中任意点\mathbf{x}到超平面(\mathbf{w},b)的距离为
\begin{aligned}
r=\frac{|\mathbf{w}^\top \mathbf{x}+b|}{\left \| \mathbf{w} \right \| }
\end{aligned}假设超平面(\mathbf{w},b)能将训练样本正确分类，即对于(\mathbf{x}_i,y_i)\in D，若y_i=+1，则\mathbf{w}^\top \mathbf{x}+b\gt 0；若y_i=-1，则\mathbf{w}^\top \mathbf{x}+b\lt 0。令
\left\{\begin{matrix}
\mathbf{w}^\top \mathbf{x}+b \ge +1, & y_i=+1 \\
\mathbf{w}^\top \mathbf{x}+b \le -1, & y_i=-1
\end{matrix}\right.若超平面
(\mathbf{w}',b')能将训练样本正确分类，则总存在缩放变换\varsigma \mathbf{w}\mapsto \mathbf{w}',\ \varsigma b \mapsto b'，使上述不等式组成立。
如下图所示，距离超平面最近的几个样本点（每个样本点对应一个特征向量）使上述不等式组中等号成立，通常称其为支持向量（Support Vector）。两个异类支持向量到超平面的距离之和称为间隔（Margin），即
\begin{aligned}
\gamma=\frac{2}{\left \| \mathbf{w} \right \| }
\end{aligned}
欲找到具有最大间隔（Maximum Margin）的划分超平面（通常直接采用几何间隔），即要找到满足上述不等式组中约束的参数\mathbf{w},b，使得\gamma最大，即
\begin{aligned}
\max\limits_{\mathbf{w},b} &\ \frac{2}{\left \| \mathbf{w} \right \| }\\
\text{s.t. }& y_i(\mathbf{w}^\top \mathbf{x}+b)\ge 1,\ i=1,2,\dots,m
\end{aligned}观察可知，为了最大化间隔，仅需最大化\left \| \mathbf{w} \right \|^{-1}，等价于最小化\left \| \mathbf{w} \right \|^2，故可对上式进行重写，得到支持向量机（Support Vector Machine，SVM）的基本型，如下所示
\begin{aligned}
\min\limits_{\mathbf{w},b} & \ \frac12 \left \| \mathbf{w} \right \|^2\\
\text{s.t. } &y_i(\mathbf{w}^\top \mathbf{x}+b)\ge 1,\ i=1,2,\dots,m
\end{aligned}2 对偶问题
大间隔划分超平面所对应的模型为
\begin{aligned}
f(\mathbf{x})=\mathbf{w}^\top \mathbf{x}+b
\end{aligned}2.1 凸二次规划
由上一节中重写后的式子可得，该问题本身是一个凸二次规划（Convex Quadratic Programming）问题，可直接用现成的优化计算包（QP优化包）求解，但由于SVM的特殊性，可使用拉格朗日乘子法得到其对偶问题（Dual Problem）。具体解法如下：对每条约束添加拉格朗日乘子\alpha_i\ge 0，则该问题的拉格朗日函数可写为
\begin{aligned}
L(\mathbf{w},b,\mathbf{\alpha})=\frac{1}{2}\left\|\mathbf{w}\right\|^2+\sum\limits_{i=1}^m\alpha_i(1-y_i(\mathbf{w}^\top \mathbf{x}+b))
\end{aligned}其中\mathbf{\alpha}=(\alpha_1;\alpha_2;\dots;\alpha_m)。故原问题等价于\min\limits_{\mathbf{w},b}\max\limits_{\alpha_i\ge 0}L(\mathbf{w},b,\mathbf{\alpha})，该问题不好求，故一般可交换极大极小的位置，得到其对偶问题\max\limits_{\alpha_i\ge 0}\min\limits_{\mathbf{w},b}L(\mathbf{w},b,\mathbf{\alpha})。注意原问题式子中有不等式约束，故整个过程需满足KKT（Karush-Kuhn-Tucker）条件，即要求
\left\{\begin{aligned}
& \alpha_i \ge 0\\
&y_if(\mathbf{x}_i)-1\ge0\\
&\alpha_i(y_if(\mathbf{x}_i)-1)=0
\end{aligned}\right.令\dfrac{\partial L(\mathbf{w},b,\mathbf{\alpha})}{\partial\mathbf{w}}=0,\ \dfrac{\partial L(\mathbf{w},b,\mathbf{\alpha})}{\partial b}=0并解方程，可直接确定\mathbf{w}的表达式，并得到了一个约束，如下所示
\begin{aligned}
\mathbf{w} &=\sum\limits_{i=1}^m \alpha_i y_i \mathbf{x}_i\\
0&=\sum\limits_{i=1}^m \alpha_i y_i
\end{aligned}结合KKT条件，可消去L(\mathbf{w},b,\mathbf{\alpha})中的\mathbf{w}与b，得到原问题的对偶问题，如下所示
\begin{aligned}
\max\limits_{\mathbf{\alpha}} & \sum\limits_{i=1}^m \alpha_i - \frac12 \sum\limits_{i=1}^m \sum\limits_{j=1}^m \alpha_i\alpha_j y_i y_j \mathbf{x}_i^\top \mathbf{x}_j\\
\text{s.t. } & \sum\limits_{i=1}^m \alpha_i y_i=0,\\
& \alpha_i \ge 0,\ i=1,2,\dots,m
\end{aligned}解出\mathbf{\alpha}后，求出\mathbf{w}与b即可得到模型
\begin{aligned}
f(\mathbf{x}) &=\mathbf{w}^\top \mathbf{x}+b\\
&=\sum\limits_{i=1}^m \alpha_i y_i \mathbf{x}_i^\top \mathbf{x} + b
\end{aligned}从对偶问题解出的拉格朗日乘子\alpha_i恰好对应训练样本(\mathbf{x}_i,y_i)。因此，又由KKT条件可知，对任意训练样本(\mathbf{x}_i,y_i)，总有\alpha_i=0或y_if(\mathbf{x}_i)=1。若\alpha_i=0，则该样本不会在模型表达式的求和中出现，即不会对模型有任何影响；若\alpha_i\gt 0，则必有y_if(\mathbf{x}_i)=1，即样本点位于最大间隔边界上，属于支持向量。由此可见支持向量机的一个重要性质：训练完成后，大部分的训练样本都不需保留，最终模型仅与支持向量有关。
2.2 SMO求解
此前通过解方程已直接解得\mathbf{w}，接下来需要确定偏移项b。可使用通用的二次规划算法来求解该对偶问题，但该问题的规模正比于训练样本数，实际任务重开销极大。通常选择使用SMO（Sequential Minimal Optimization）算法求解，基本思路为：先固定\alpha_i之外的所有参数，然后求\alpha_i上的极值；由于存在约束\sum\limits_{i=1}^m \alpha_i y_i=0，固定其他变量后，\alpha_i可由其他变量导出；故SMO每次选择两个变量\alpha_i,\alpha_j并固定其他参数。由此，在参数初始化后，SMO不断执行如下两步直至收敛：
- 选取一对需更新的变量
\alpha_i,\alpha_j - 固定
\alpha_i,\alpha_j以外的参数，求解前述的对偶问题式子，获得更新后的\alpha_i,\alpha_j
注意到只需选取的\alpha_i,\alpha_j中有一个不满足KKT条件，目标函数就会在迭代后减小。直观来看，KKT条件违背的程度越大，则变量更新后可能导致的目标函数值减幅越大。故SMO先选取违背KKT条件程度最大的变量，再选择一个使目标函数值减小最快的变量，但由于比较各变量所对应的目标函数值减幅的复杂度过高，因此SMO采用了一个启发式：使选取的两变量所对应样本之间的间隔最大。一种直观的解释是，这样的两个变量有很大的差别，与对两个相似的变量进行更新相比，对它们进行更新会带给目标函数值更大的变化。该过程十分高效，具体而言，此时前述对偶问题式子中的约束可重写为
\begin{aligned}
\alpha_i y_i +\alpha_j y_j=c,\ \alpha_i \ge 0,\ \alpha_j \ge 0
\end{aligned}其中c=-\sum\limits_{k\ne i,j}\alpha_k y_k为使\sum\limits_{i=1}^m\alpha_i y_i=0成立的常数。用\alpha_i y_i +\alpha_j y_j=c消去前述对偶问题式子中的变量\alpha_j，则得到一个关于\alpha_i的单变量二次规划问题，仅有的约束为\alpha_i \ge 0。可见，这样的二次规划问题具有闭式解，故无需调用数值优化算法即可高效地计算出更新后的\alpha_i,\alpha_j。
为了确认偏移项b，注意到对任意支持向量(\mathbf{x}_s,y_s)都有y_sf(\mathbf{x_s})=1，即
\begin{aligned}
y_s\left( \sum\limits_{i\in S} \alpha_i y_i\mathbf{x}_i^\top \mathbf{x}_s + b \right)=1
\end{aligned}其中S=\{i\mid \alpha_i\gt 0,\ i=1,2,\dots,m\}为所有支持向量的下标集。理论上可选取任意支持向量并通过求解上式获得b，但实际任务中常采用另一种更鲁棒的做法：使用所有支持向量求解的平均值，即
\begin{aligned}
b=\frac{1}{|S|}\sum\limits_{s\in S}\left(y_s- \sum\limits_{i\in S} \alpha_i y_i\mathbf{x}_i^\top \mathbf{x}_s \right)
\end{aligned}3 核函数
由于前述的超平面只能解决线性可分的问题，对于线性不可分问题（例如异或问题），可将样本从原始空间映射到一个更高维的特征空间，使得样本在该特征空间内线性可分。令\phi(\mathbf{x})表示将\mathbf{x}映射后的特征向量，则在特征空间中划分超平面锁对应的模型可表示为
\begin{aligned}
f(\mathbf{x})=\mathbf{w}^\top \phi(\mathbf{x})+b
\end{aligned}其中\mathbf{w},b为模型参数。根据前述的SVM基本型，有
\begin{aligned}
\min\limits_{\mathbf{w},b} &\ \frac12 \left \| \mathbf{w} \right \|^2\\
\text{s.t. } &y_i(\mathbf{w}^\top \phi(\mathbf{x})+b)\ge 1,\ i=1,2,\dots,m
\end{aligned}其对偶问题为
\begin{aligned}
\max\limits_{\mathbf{\alpha}} & \sum\limits_{i=1}^m \alpha_i - \frac12 \sum\limits_{i=1}^m \sum\limits_{j=1}^m \alpha_i\alpha_j y_i y_j \phi(\mathbf{x}_i)^\top \phi(\mathbf{x}_j)\\
\text{s.t. }& \sum\limits_{i=1}^m \alpha_i y_i=0,\\
& \alpha_i \ge 0,\ i=1,2,\dots,m
\end{aligned}求解上式涉及到样本\mathbf{x}_i,\mathbf{x}_j映射到特征空间之后的内积\phi(\mathbf{x}_i)^\top \phi(\mathbf{x}_j)，由于维数可能很高（甚至为无穷维），直接计算极为困难，故为了避开障碍，可以引入一个核函数（Kernel Function），此处的核函数如下所示
\begin{aligned}
\kappa (\mathbf{x}_i,\mathbf{x}_j)=\left \langle \phi(\mathbf{x}_i),\phi(\mathbf{x}_j) \right \rangle =\phi(\mathbf{x}_i)^\top \phi(\mathbf{x}_j)
\end{aligned}即样本\mathbf{x}_i,\mathbf{x}_j在特征空间的内积等于其在原始样本空间中通过核函数\kappa(\cdot,\cdot)计算的结果。由此无需直接计算高位特征空间中的内积，可将前式重写为
\begin{aligned}
\max\limits_{\mathbf{\alpha}} & \sum\limits_{i=1}^m \alpha_i - \frac12 \sum\limits_{i=1}^m \sum\limits_{j=1}^m \alpha_i\alpha_j y_i y_j \kappa (\mathbf{x}_i,\mathbf{x}_j)\\
\text{s.t. }& \sum\limits_{i=1}^m \alpha_i y_i=0,\\
& \alpha_i \ge 0,\ i=1,2,\dots,m
\end{aligned}模型最优解可通过训练样本的核函数展开。求解后可得到模型的展式，常称为支持向量展式（Support Vector Expansion），如下所示
\begin{aligned}
f(\mathbf{x}) &=\mathbf{w}^\top \phi(\mathbf{x})+b\\
&=\sum\limits_{i=1}^m\alpha_i y_i \phi(\mathbf{x}_i)^\top \phi(\mathbf{x}_j)+b\\
&=\sum\limits_{i=1}^m\alpha_i y_i \kappa (\mathbf{x}_i,\mathbf{x}_j)+b
\end{aligned}显然，若已知合适映射的具体形式，则可直接写出核函数。但通常不知道映射是何形式，故可通过以下核函数定理来寻找核函数：令\mathcal{X}为输入空间，\kappa(\cdot,\cdot)为定义在\mathcal{X} \times \mathcal{X}上的对称函数，则\kappa是核函数当且仅当对于任意数据D=\left\{\mathbf{x}_{1}, \mathbf{x}_{2}, \dots, \mathbf{x}_{m}\right\}，核矩阵（Kernel Matrix）\mathbf{K}总是半正定的：
\mathbf{K}=\left[\begin{array}{ccccc}
\kappa\left(\mathbf{x}_{1}, \mathbf{x}_{1}\right) & \cdots & \kappa\left(\mathbf{x}_{1}, \mathbf{x}_{j}\right) & \cdots & \kappa\left(\mathbf{x}_{1}, \mathbf{x}_{m}\right) \\
\vdots & \ddots & \vdots & \ddots & \vdots \\
\kappa\left(\mathbf{x}_{i}, \mathbf{x}_{1}\right) & \cdots & \kappa\left(\mathbf{x}_{i}, \mathbf{x}_{j}\right) & \cdots & \kappa\left(\mathbf{x}_{i}, \mathbf{x}_{m}\right) \\
\vdots & \ddots & \vdots & \ddots & \vdots \\
\kappa\left(\mathbf{x}_{m}, \mathbf{x}_{1}\right) & \cdots & \kappa\left(\mathbf{x}_{m}, \mathbf{x}_{j}\right) & \cdots & \kappa\left(\mathbf{x}_{m}, \mathbf{x}_{m}\right)
\end{array}\right]该定理表明，只要一个对称函数所对应的核矩阵半正定，其就能作为核函数使用。事实上，对于一个半正定核矩阵，总能找到一个与之对应的映射\phi。换言之，任何一个核函数都隐式地定义了一个称为再生核希尔伯特空间（Reproducing Kernel Hilbert Space，RKHS）的特征空间。
由此前讨论可知，希望样本在特征空间内线性可分，特征空间的好坏对支持向量机的性能至关重要。需注意的是，在不知道特征映射的形式时，无法知道什么样的核函数是合适的，而核函数也仅是隐式地定义了该特征空间。故“核函数选择”成为支持向量机的最大变数，若核函数选择不合适，则意味着将样本映射到了一个不合适的特征空间，很可能导致性能不佳。
下表列出了几种常用的核函数（在核函数选择方面有一些基本的经验，例如对文本数据通常采用线性核，情况不明时可先尝试高斯核）：
| 名称 | 表达式 | 参数 |
|---|---|---|
| 线性核 | \kappa (\mathbf{x}_i,\mathbf{x}_j)=\mathbf{x}_i^\top \mathbf{x}_j |
|
| 多项式核 | \kappa (\mathbf{x}_i,\mathbf{x}_j)=(\mathbf{x}_i^\top \mathbf{x}_j)^d |
d\ge 1为多项式的次数 |
| 高斯核 | \kappa (\mathbf{x}_i,\mathbf{x}_j)=\exp\left(-\dfrac{\left \| \mathbf{x}_i-\mathbf{x}_j \right \|^2 }{2\sigma^2} \right) |
\sigma\ge 0为高斯核的带宽（Width） |
| 拉普拉斯核 | \kappa (\mathbf{x}_i,\mathbf{x}_j)=\exp\left(-\dfrac{\left \| \mathbf{x}_i-\mathbf{x}_j \right \| }{2\sigma^2} \right) |
\sigma\ge 0 |
| Sigmoid核 | \kappa (\mathbf{x}_i,\mathbf{x}_j)=\tanh \left( \beta \mathbf{x}_i^\top \mathbf{x}_j + \theta \right) |
\tanh为双曲正切函数，\beta \gt 0,\ \theta \lt 0 |
此外还可通过函数组合得到，例如：
- 若
\kappa_1,\kappa_2为核函数，则对于任意正数\gamma_1,\gamma_2，其线性组合\gamma_1\kappa_1+\gamma_2\kappa_2也是核函数 - 若
\kappa_1,\kappa_2为核函数，则核函数的直积\kappa_1\otimes \kappa_2(\mathbf{x},\mathbf{z})=\kappa_1(\mathbf{x},\mathbf{z})\kappa_2(\mathbf{x},\mathbf{z})也是核函数 - 若
\kappa_1为核函数，则对于任意函数g(\mathbf{x})，\kappa(\mathbf{x},\mathbf{z})=g(\mathbf{x})\kappa_1(\mathbf{x},\mathbf{z})g(\mathbf{z})也是核函数
4 软间隔
前几节主要解决了以下两个问题：当数据线性可分时，直接使用最大间隔的超平面划分；当数据线性不可分时，则通过核函数将数据映射到高维特征空间，使之线性可分。然而现实问题中往往很难确定合适的核函数使得训练样本在特征空间中线性可分；退一步说，即便恰好找到了某个核函数使训练集在特征空间中线性可分，也很难断定这个貌似线性可分的结果不是由于过拟合所造成的，例如存在噪声数据（Outlier）的情形。由此需要引入软间隔（Soft Margin）的概念。
前几节所述的硬间隔（Hard Margin）要求所有样本均满足约束，而软间隔允许某些样本不满足约束（即可以在一定程度上偏移超平面），约束为
\begin{aligned}
y_i(\mathbf{w}^\top \mathbf{x}_i + b) \ge 1
\end{aligned}在最大化间隔的同时，还要使得不满足约束的数据点尽可能少，故优化目标可写为
\begin{aligned}
\min\limits_{\mathbf{w},b} \frac12 \left \| \mathbf{w} \right \|^2+C\sum\limits_{i=1}^m l_{0/1}(y_i(\mathbf{w}^\top \mathbf{x}_i + b)-1)
\end{aligned}其中C>0为常数，l_{0/1}(z)=\mathbb{I}(z \lt 0)为0/1损失函数。当C\to \infty时，上式迫使所有样本均满足约束，相当于6.1中给出的基本型；当C取有限值时，上式允许一些样本不满足约束。
然而l_{0/1}(z)数学性质不太好（非凸、非连续），使得上式不易直接求解，故常改用其他具有较好数学性质的替代损失（Surrogate Loss），常用的有以下三种：
- 铰链损失（Hinge Loss）：
l_{\text{hinge}}(z)=\max(0,1-z) - 指数损失（Exponential Loss）：
l_{\exp}=\exp(-z) - 对率损失（Logistic Loss）：
l_{\log}(z)=\log (1+\exp(-z))
若采用hinge损失，则优化目标变为
\begin{aligned}
\min\limits_{\mathbf{w},b} \frac12 \left \| \mathbf{w} \right \|^2+C\sum\limits_{i=1}^m \max(0,1-y_i(\mathbf{w}^\top \mathbf{x}_i + b))
\end{aligned}引入松弛变量（Slack Variable）\xi_i\ge 0，可将上式进一步重写
\begin{aligned}
\min\limits_{\mathbf{w},b,\xi_i} & \frac12 \left \| \mathbf{w} \right \|^2+C\sum\limits_{i=1}^m \xi_i\\
\text{s.t. } & y_i(\mathbf{w}^\top \mathbf{x}_i + b) \ge 1-\xi_i\\
& \xi_i \ge 0,\ i=1,2,\dots,m
\end{aligned}由此得到常用的软间隔支持向量机。显然，上式中每一个样本都对应一个松弛变量，其用以表征该样本不满足约束的程度。该问题仍属于二次规划问题，故与6.2中同理，使用拉格朗日乘子法，对每个约束添加拉格朗日乘子\alpha_i,\mu_i \ge 0可得上式的拉格朗日函数
\begin{aligned}
L(\mathbf{w},b,\mathbf{\alpha},\mathbf{\xi},\mathbf{\mu})= &\frac12 \left \| \mathbf{w} \right \|^2+C\sum\limits_{i=1}^m \xi_i\\
& \sum\limits_{i=1}^m \alpha_i(1-\xi_i-y_i(\mathbf{w}^\top \mathbf{x}_i + b))-\sum\limits_{i=1}^m \mu_i\xi_i
\end{aligned}令\dfrac{\partial L(\mathbf{w},b,\mathbf{\alpha},\mathbf{\xi},\mathbf{\mu})}{\partial \mathbf{w}}=0,\ \dfrac{\partial L(\mathbf{w},b,\mathbf{\alpha},\mathbf{\xi},\mathbf{\mu})}{\partial b}=0,\ \dfrac{\partial L(\mathbf{w},b,\mathbf{\alpha},\mathbf{\xi},\mathbf{\mu})}{\partial \xi_i}=0并解方程，可直接确定\mathbf{w}的表达式
\begin{aligned}
\mathbf{w} &=\sum\limits_{i=1}^m \alpha_i y_i \mathbf{x}_i\\
0&=\sum\limits_{i=1}^m \alpha_i y_i\\
C&=\alpha_i+\mu_i
\end{aligned}此外还得到了两个约束。将上述3式全部代入L(\mathbf{w},b,\mathbf{\alpha},\mathbf{\xi},\mathbf{\mu})，即得到了原问题的对偶问题，如下所示
\begin{aligned}
\max\limits_{\mathbf{\alpha}} & \sum\limits_{i=1}^m \alpha_i - \frac12 \sum\limits_{i=1}^m \sum\limits_{j=1}^m \alpha_i\alpha_j y_i y_j \mathbf{x}_i^\top \mathbf{x}_j\\
\text{s.t. }& \sum\limits_{i=1}^m \alpha_i y_i=0,\\
& 0\le \alpha_i \le C,\ i=1,2,\dots,m
\end{aligned}与硬间隔下的对偶问题对比可见，两者唯一差别在于对偶变量的约束不同。因此在引入核函数处理线性不可分问题时，可直接使用与硬间隔支持向量机完全相同的方法，此处略。