Support Vector Machine
支持向量机 (SVM) 是一种基于间隔最大化的线性分类器。
- 当数据线性可分时，通过硬间隔最大化，可学习硬间隔支持向量机（线性可分支持向量机）；
- 当数据近似线性可分时，通过软间隔最大化，可学习软间隔支持向量机（线性支持向量机）；
- 当数据线性不可分时，利用核技巧以及软间隔最大化，可学习一般的非线性支持向量机。
在本文中，记数据集为 \(D=\{(\mathbf x_1,y_1),\ldots,(\mathbf x_n,y_n)\}\)，其中 \(\mathbf x_i\in\mathcal X=\mathbb R^d,\,y_i\in\mathcal Y=\{-1,+1\}\).
线性可分与硬间隔最大化
基本思想
当数据是线性可分时，存在无数多个超平面 \(\mathbf w^T\mathbf x+b=0\) 都可以作为决策平面，超平面一侧是正类，另一侧是负类。朴素地想，在这些超平面中，找到间隔数据点最远的那个超平面，应该是最为稳妥的。
根据一些几何学知识可以知道，点 \(\mathbf x_i\) 到平面 \(\mathbf w^T\mathbf x+b=0\) 的距离为 \(\frac{|\mathbf w^T\mathbf x_i+b|}{\Vert\mathbf w\Vert}\). 特别地，由于正类的数据点满足 \(\mathbf w^T\mathbf x_i+b>0\)，负类反之，所以绝对值可以用如下方式去掉： \[ d(\mathbf x_i)=\frac{|\mathbf w^T\mathbf x_i+b|}{\Vert\mathbf w\Vert}=\begin{cases}+(\mathbf w^T\mathbf x_i+b)/\Vert\mathbf w\Vert,&y_i=+1\\-(\mathbf w^T\mathbf x_i+b)/\Vert\mathbf w\Vert,&y_i=-1\end{cases}\quad=\frac{y_i(\mathbf w^T\mathbf x_i+b)}{\Vert\mathbf w\Vert} \] 于是，超平面与数据点的最小间隔为： \[ \min_{\mathbf x_i,y_i\in D}\;\frac{y_i(\mathbf w^T\mathbf x_i+b)}{\Vert\mathbf w\Vert} \] 那么，最大化最小间隔就可以写为如下优化问题： \[ \begin{align} \max_{\mathbf w,b}\min_{\mathbf x_i,y_i\in D}\quad&\frac{y_i(\mathbf w^T\mathbf x_i+b)}{\Vert\mathbf w\Vert}\\ \text{s.t.}\quad&y_i(\mathbf w^T\mathbf x_i+b)>0,&\forall i=1,\ldots,n \end{align} \] 注意到同时放缩 \(\mathbf w,b\) 并不改变超平面，从而也不改变优化目标的值，因此我们完全可以将约束条件改写作 \(y_i(\mathbf w^T\mathbf x_i+b)\geq 1\)，即： \[ \begin{align} \max_{\mathbf w,b}\min_{\mathbf x_i,y_i\in D}\quad&\frac{y_i(\mathbf w^T\mathbf x_i+b)}{\Vert\mathbf w\Vert}\\ \text{s.t.}\quad&y_i(\mathbf w^T\mathbf x_i+b)\geq 1,&\forall i=1,\ldots,n \end{align} \] 这样，只要约束条件的符号是正确的，那么我们就能通过放缩 \(\mathbf w,b\) 来满足新的约束条件，所以改写前后问题是等价的。
进一步地，我们可以小心地缩放，让 \(y_i(\mathbf w^T\mathbf x_i+b)\) 中最小的那个正好等于 1，“恰好”让约束条件得到满足。这时，最小间隔简化为： \[ \min_{\mathbf x_i,y_i\in D}\;\frac{y_i(\mathbf w^T\mathbf x_i+b)}{\Vert\mathbf w\Vert}=\frac{1}{\Vert\mathbf w\Vert} \] 所以优化问题变成了： \[ \begin{align} \max_{\mathbf w,b}\quad&\frac{1}{\Vert\mathbf w\Vert}\\ \text{s.t.}\quad&y_i(\mathbf w^T\mathbf x_i+b)\geq 1,&\forall i=1,\ldots,n \end{align} \] 又由于最大化 \(1/\Vert\mathbf w\Vert\) 等价于最小化 \(\frac{1}{2}\Vert\mathbf w\Vert^2\)，所以问题继续改写作： \[ \begin{align} \min_{\mathbf w,b}\quad&\frac{1}{2}\Vert\mathbf w\Vert^2\\ \text{s.t.}\quad&y_i(\mathbf w^T\mathbf x_i+b)\geq 1,&\forall i=1,\ldots,n \end{align} \] 现在问题转化为了一个凸二次规划问题，在优化理论中人们对凸二次规划已经有着非常成熟的研究，直接调用相关算法求解即可。
对偶问题
对于上一节最终得到的优化问题，除了直接求解以外，我们也可以尝试求解其对偶问题。
首先构建 Lagrange 函数。对每个约束条件引入一个 Lagrange 乘子 \(\alpha_i\geq0\)，定义 Lagrange 函数为： \[ L(\mathbf w,b,\alpha)=\frac{1}{2}\Vert\mathbf w\Vert^2-\sum_{i=1}^n\alpha_i(y_i(\mathbf w^T\mathbf x_i+b)-1) \] 其中 \(\alpha=(\alpha_1,\ldots,\alpha_n)^T\). 那么原问题和对偶问题分别为： \[ \min_{\mathbf w,b}\;\underbrace{\max_\alpha L(\mathbf w,b,\alpha)}_{\text{Primal}(\mathbf w,b)}\iff \max_\alpha\;\underbrace{\min_{\mathbf w,b}L(\mathbf w,b,\alpha)}_{\text{Dual}(\alpha)} \] 考虑 \(\text{Dual}(\alpha)\) ，取 Lagrange 函数对 \(\mathbf w,b\) 求导并令为零： \[ \begin{align} &\frac{\partial L}{\partial \mathbf w}=\mathbf w-\sum_{i=1}^n\alpha_iy_i\mathbf x_i=0&&\implies \mathbf w=\sum_{i=1}^n\alpha_iy_i\mathbf x_i\\ &\frac{\partial L}{\partial b}=-\sum_{i=1}^n\alpha_iy_i=0&&\implies \sum_{i=1}^n\alpha_iy_i=0 \end{align} \] 代入 \(\text{Dual}(\alpha)\) 得： \[ \text{Dual}(\alpha)=\min_{\mathbf w,b}L(\mathbf w,b,\alpha)=-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j\mathbf x_i^T\mathbf x_j+\sum_{i=1}^n\alpha_i \] 因此原问题转化为如下对偶问题： \[ \begin{align} \min_\alpha\quad&\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j\mathbf x_i^T\mathbf x_j-\sum_{i=1}^n\alpha_i\\ \text{s.t.}\quad&\sum_{i=1}^n\alpha_iy_i=0\\ &\alpha_i\geq 0,\quad\forall i=1,\ldots,n \end{align} \] 由于支持向量机的优化问题满足 Slater's condition（优化目标是凸函数并且约束条件是仿射函数），因此具有强对偶性，即原问题与对偶问题的最优解是相同的，所以我们可以通过求解上述对偶问题来求解原问题。对比对偶问题和原问题，可以发现对偶问题的优化目标变得更复杂了，但约束条件变简单了，而且依然是一个凸二次规划问题，可以直接调用相关算法求解。
支持向量
设原问题最优解为 \(\mathbf w^\ast,b^\ast\)，即分离超平面为 \(\mathbf {w^\ast}^T\mathbf x+b^\ast=0\)，间隔边界为 \(\mathbf {w^\ast}^T\mathbf x+b^\ast=1\) 和 \(\mathbf {w^\ast}^T\mathbf x+b^\ast=-1\)，那么样本点可以分为两类——在间隔边界上和在间隔边界以外的，如图所示：
我们称在间隔边界上的样本为支持向量，它们是距离分离超平面最近的点（距离为 \(1/\Vert\mathbf w^\ast\Vert\)）。支持向量机的解只依赖于支持向量，去掉或在间隔边界以外移动其他样本对解没有任何影响。
从对偶变量的角度来看，设对偶问题的最优解为 \(\alpha^\ast\)，那么根据 KKT 条件的互补松弛性条件有： \[ \alpha^\ast_i(y_i(\mathbf {w^\ast}^T\mathbf x_i+b^\ast)-1)=0,\quad \forall i=1,\ldots,n \] 因此，如果一个样本不是支持向量，那么 \(y_i(\mathbf {w^\ast}^T\mathbf x_i+b^\ast)>1\)，于是根据互补松弛性条件，必有 \(\alpha_i^\ast=0\)；反过来，如果 \(\alpha_i^\ast>0\)，那么根据互补松弛性条件，必有 \(y_i(\mathbf {w^\ast}^T\mathbf x_i+b^\ast)=1\)，即是支持向量。
线性不可分与软间隔最大化
基本思想
在实际应用中，我们经常会遇到噪声数据点，它们可能导致问题线性不可分。为了解决这个问题，可以对每个样本点 \((\mathbf x_i,y_i)\) 引入一个松弛因子 \(\xi_i\geq 0\)，将约束条件放松为 \(y_i(\mathbf w^T\mathbf x_i+b)\geq 1-\xi_i\). 当然，我们并不希望 \(\xi_i\) 任意地大，否则约束条件约束了个寂寞，因此在优化目标中加入 \(\xi_i\)，并用超参数 \(C>0\) 做一个权衡： \[ \begin{align} \min_{\mathbf w,b,\xi}\quad&\frac{1}{2}\Vert\mathbf w\Vert^2+C\sum_{i=1}^n\xi_i\\ \text{s.t.}\quad&y_i(\mathbf w^T\mathbf x_i+b)\geq 1-\xi_i,&\quad\forall i=1,\ldots,n\\ &\xi_i\geq 0,&\forall i=1,\ldots,n \end{align} \] 其中 \(\xi=(\xi_1,\ldots,\xi_n)^T\). 这依旧是一个凸二次规划问题，所以也可以直接调用相关算法求解。
对偶问题
对于软间隔最大化，我们同样也可以考虑求解其对偶问题。
首先构建 Lagrange 函数。对约束条件引入 Lagrange 乘子 \(\alpha_i\geq0\) 和 \(\mu_i\geq0\)，定义 Lagrange 函数为： \[ L(\mathbf w,b,\xi,\alpha,\mu)=\frac{1}{2}\Vert\mathbf w\Vert^2+C\sum_{i=1}^n\xi_i-\sum_{i=1}^n\alpha_i(y_i(\mathbf w^T\mathbf x_i+b)-1+\xi_i)-\sum_{i=1}^n\mu_i\xi_i \] 其中 \(\alpha=(\alpha_1,\ldots,\alpha_n)^T,\,\mu=(\mu_1,\ldots,\mu_n)^T\). 那么原问题和对偶问题分别为： \[ \min_{\mathbf w,b,\xi}\;\underbrace{\max_{\alpha,\mu}L(\mathbf w,b,\xi,\alpha,\mu)}_{\text{Primal}(\mathbf w,b)}\iff \max_{\alpha,\mu}\;\underbrace{\min_{\mathbf w,b,\xi}L(\mathbf w,b,\xi,\alpha,\mu)}_{\text{Dual}(\alpha,\mu)} \] 对于 \(\text{Dual}(\alpha,\mu)\)，取 Lagrange 函数对 \(\mathbf w,b,\xi\) 求导并令为零： \[ \begin{align} &\frac{\partial L}{\partial \mathbf w}=\mathbf w-\sum_{i=1}^n\alpha_iy_i\mathbf x_i=0&&\implies \mathbf w=\sum_{i=1}^n\alpha_iy_i\mathbf x_i\\ &\frac{\partial L}{\partial b}=-\sum_{i=1}^n\alpha_iy_i=0&&\implies \sum_{i=1}^n\alpha_iy_i=0\\ &\frac{\partial L}{\partial\xi_i}=C-\alpha_i-\mu_i=0&&\implies C-\alpha_i-\mu_i=0,\quad i=1,\ldots,n \end{align} \] 代入 \(\text{Dual}(\alpha,\mu)\) 得： \[ \text{Dual}(\alpha,\mu)=\min_{\mathbf w,b,\xi}L(\mathbf w,b,\xi,\alpha,\mu)=-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j\mathbf x_i^T\mathbf x_j+\sum_{i=1}^n\alpha_i \] 因此原问题转化为如下对偶问题： \[ \begin{align} \min_{\alpha,\mu}\quad&\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j\mathbf x_i^T\mathbf x_j-\sum_{i=1}^n\alpha_i\\ \text{s.t.}\quad&\sum_{i=1}^n\alpha_iy_i=0\\ &\alpha_i\geq 0,\quad i=1,\ldots,n\\ &\mu_i\geq 0,\quad i=1,\ldots,n\\ &\alpha_i+\mu_i=C,\quad i=1,\ldots,n \end{align} \] 注意优化目标其实与 \(\mu\) 无关，并且最后三个约束条件可以简化为 \(0\leq\alpha_i\leq C\)，所以上述对偶问题可以进一步简化为： \[ \begin{align} \min_{\alpha}\quad&\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j\mathbf x_i^T\mathbf x_j-\sum_{i=1}^n\alpha_i\\ \text{s.t.}\quad&\sum_{i=1}^n\alpha_iy_i=0\\ &0\leq\alpha_i\leq C,\quad i=1,\ldots,n\\ \end{align} \] 对比硬间隔最大化的对偶问题，可以发现二者仅有一个区别：约束条件从 \(\alpha_i\geq0\) 变成了 \(0\leq\alpha_i\leq C\). 这并不改变问题是一个凸二次规划问题的形式，所以还是可以直接调用相关算法求解。
支持向量
软间隔的支持向量要比线性可分时的情况复杂一些，它们既可以在间隔边界上、也可以在间隔边界与分离超平面之间，还可以在分离超平面的误分一侧，如下图所示：
事实上，设原问题的最优解为 \(\mathbf {w^\ast},b^\ast,\xi^\ast_i\)，对偶问题的最优解为 \(\alpha^\ast_i,\mu^\ast_i\)，那么根据 KKT 条件的互补松弛性条件有： \[ \begin{cases} \alpha^\ast_i(y_i(\mathbf {w^\ast}^T\mathbf x_i+b^\ast)-1+\xi_i^\ast)=0\\ \mu^\ast_i\xi^\ast_i=(C-\alpha^\ast_i)\xi^\ast_i=0 \end{cases}\quad,\quad\forall i=1,\ldots,n \] 因此可以分析：
- 若 \(\alpha^\ast_i=0\)，则 \(\xi^\ast_i=0\)，于是原问题的约束条件变成 \(y_i(\mathbf {w^\ast}^T\mathbf x_i+b^\ast)\geq1\)，这意味着 \(\mathbf x_i\) 位于间隔边界之外，不是支持向量；
- 若 \(0<\alpha_i^\ast<C\)，那么 \(\xi_i^\ast=0\) 并且 \(y_i(\mathbf {w^\ast}^T\mathbf x_i+b^\ast)=1\)，这意味着 \(\mathbf x_i\) 位于间隔边界上；
- 若 \(\alpha_i^\ast=C\)，那么 \(y_i(\mathbf {w^\ast}^T\mathbf x_i+b^\ast)-1+\xi_i^\ast=0\implies y_i(\mathbf {w^\ast}^T\mathbf x_i+b^\ast)\leq1\)，这意味着 \(\mathbf x_i\) 位于间隔边界内。此时：
- 若 \(0\leq\xi_i^\ast<1\)，则 \(y_i(\mathbf {w^\ast}^T\mathbf x_i+b^\ast)>0\)，即 \(\mathbf x_i\) 分类正确，在间隔边界和分离超平面之间；
- 若 \(\xi_i^\ast=1\)，则 \(y_i(\mathbf {w^\ast}^T\mathbf x_i+b^\ast)=0\)，即 \(\mathbf x_i\) 正好在分离超平面上；
- 若 \(\xi_i^\ast>1\)，则 \(y_i(\mathbf {w^\ast}^T\mathbf x_i+b^\ast)<0\)，即 \(\mathbf x_i\) 分类错误，在分离超平面误分的那一侧。
Hinge loss
让我们重新考察支持向量机的原问题： \[ \begin{align} \min_{\mathbf w,b,\xi}\quad&\frac{1}{2}\Vert\mathbf w\Vert^2+C\sum_{i=1}^n\xi_i\\ \text{s.t.}\quad&y_i(\mathbf w^T\mathbf x_i+b)\geq 1-\xi_i,&\quad\forall i=1,\ldots,n\\ &\xi_i\geq 0,&\forall i=1,\ldots,n \end{align} \] 注意到：
- 如果 \(y_i(\mathbf w^T\mathbf x_i+b)\geq1\)，那么第一个约束始终成立，于是为了最小化目标函数，必然有 \(\xi_i=0\)；
- 如果 \(y_i(\mathbf w^T\mathbf x_i+b)<1\)，那么第一个约束表明 \(\xi_i\geq1-y_i(\mathbf w^T\mathbf x_i+b)>0\)，于是为了最小化目标函数，必然有 \(\xi_i=1-y_i(\mathbf w^T\mathbf x_i+b)\).
综上，有： \[ \xi_i=\max\left(0,1-y_i(\mathbf w^T\mathbf x_i+b)\right)=[1-y_i(\mathbf w^T\mathbf x_i+b)]_+ \] 因此原问题与下面这个优化问题是等价的： \[ \min_{\mathbf w,b}\quad\frac{1}{2}\Vert\mathbf w\Vert^2+C\sum_{i=1}^n[1-y_i(\mathbf w^T\mathbf x_i+b)]_+ \] 为了形式上的需要，做一个人畜无害的变量代换 \(\lambda=1/2C\)，于是原问题等价于： \[ \min_{\mathbf w,b}\quad\sum_{i=1}^n[1-y_i(\mathbf w^T\mathbf x_i+b)]_++\lambda\Vert\mathbf w\Vert^2 \] 从这个角度看，支持向量机是用 hinge loss 的二分类问题，还带了个正则项。事实上，二分类问题真正的损失函数是 0-1 损失函数，但 0-1 损失函数梯度为零，直接优化比较困难，而 hinge loss 是 0-1 损失的上界，因此可以作为 0-1 损失函数的一个合适的代理损失函数，如图所示：
线性不可分与核函数
基本思想与核技巧
虽然软间隔支持向量机可以处理线性不可分的数据，但得到的依旧是一个超平面，因此只能用于处理近似线性可分的问题。如果数据本身就完全不是线性可分的，如异或问题，那么软间隔支持向量机显然也不合适。核技巧是解决非线性可分问题的常用技巧，其基本思想为将线性不可分的数据映射到高维空间中，使之线性可分，进而可以使用线性模型求解。完成这个映射的函数称为核函数。
具体而言，设 \(\mathcal X\) 为输入空间，\(\mathcal H\) 为映射后的特征空间，存在映射： \[ \phi(\mathbf x):\mathcal X\to\mathcal H \] 使得对任意 \(\mathbf x,\mathbf y\in\mathcal X\)，函数 \(K(\mathbf x,\mathbf y)\) 满足： \[ K(\mathbf x,\mathbf y)=\phi(\mathbf x)\cdot\phi(\mathbf y) \] 则称 \(K(\mathbf x,\mathbf y)\) 为核函数，其中 \(\phi(\mathbf x)\cdot\phi(\mathbf y)\) 表示向量内积。
核技巧的核心是只设计核函数 \(K(\mathbf x,\mathbf y)\)，而不显式定义映射函数 \(\phi(\mathbf x)\). 也就是说，计算特征内积时并不是先映射、再计算，而是直接用核函数计算；一些核函数对应的特征空间 \(\mathcal H\) 甚至是无穷维的，根本无法先映射再计算。
既然不显式定义映射函数，那怎么判断一个给定的函数究竟是不是核函数呢？可以证明，如果 \(K:\mathcal X\times\mathcal X\to\mathbb R\) 是对称函数，则 \(K(\mathbf x,\mathbf y)\) 为正定核函数的充要条件是对任意 \(\mathbf x_i\in\mathcal X,\,i=1,\ldots,m\)，\(K\) 对应的 Gram 矩阵： \[ K=[K(\mathbf x_i,\mathbf x_j)]_{m\times m} \] 是半正定矩阵。
常用核函数
多项式核函数： \[ K(\mathbf x,\mathbf y)=(\mathbf x^T\mathbf y+1)^p \]
高斯核函数： \[ K(\mathbf x,\mathbf y)=\exp\left(-\frac{\Vert\mathbf x-\mathbf y\Vert^2}{2\sigma^2}\right) \] Sigmoid (Tanh) 核函数： \[ K(\mathbf x,\mathbf y)=\tanh(\kappa\mathbf x^T\mathbf y+\theta) \]
核函数+软间隔支持向量机
注意到在支持向量机的对偶问题中，优化目标只需要样本之间的内积，并不需要每个样本单独的值。因此，只需要将内积替换为核函数，就相当于是在映射后的高维特征空间中做支持向量机了： \[ \begin{align} \min_{\alpha}\quad&\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_jK(\mathbf x_i,\mathbf x_j)-\sum_{i=1}^n\alpha_i\\ \text{s.t.}\quad&\sum_{i=1}^n\alpha_iy_i=0\\ &0\leq\alpha_i\leq C,\quad i=1,\ldots,n\\ \end{align} \] 能够使用核技巧也是对偶问题相比原问题的优势之一，因为原问题需要每个样本单独的值，无法使用核技巧。然而，要找到一个合适的核函数使得映射后的数据近似线性可分并不是一件容易的事，因而也是当年的研究热点。
SMO 优化算法
我们已经看到，无论是硬间隔最大化、软间隔最大化、亦或是加入核函数的支持向量机，它们最终都建模为了一个凸二次规划问题。到这一步，我们只需要调用很多成熟的凸二次规划求解器即可。但是，当训练样本量很大时，这些算法往往会变得低效。因此，对于支持向量机而言，人们最常使用的优化方法是一种称为 SMO (Sequential Minimal Optimization) 的算法。
SMO 算法要解的是对偶问题： \[ \begin{align} \min_{\alpha}\quad&\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_jK(\mathbf x_i,\mathbf x_j)-\sum_{i=1}^n\alpha_i\\ \text{s.t.}\quad&\sum_{i=1}^n\alpha_iy_i=0\\ &0\leq\alpha_i\leq C,\quad i=1,\ldots,n\\ \end{align} \] 其基本思想是，由于 KKT 条件是最优解的充要条件，因此在达到最优解之前，一定有变量不满足 KKT 条件。那么，每次拿出两个变量（其中至少一个不满足 KKT 条件），固定其他变量，问题就变成了针对这两个变量的凸二次规划问题。而两个变量的凸二次规划问题有解析解，因此可以提高算法的速度。
显然，SMO 算法的一个关键问题就是每步究竟选哪两个变量 \(\alpha_1,\alpha_2\) 最好。一种启发式的选法为：首先选择 \(\alpha_1\) 为违反 KKT 条件最严重的那个变量，然后选择 \(\alpha_2\) 使得这一步优化后 \(\alpha_2\) 的变化足够大。当然，所谓启发式就意味着这种选法不一定是最好的，因此也有很多文献做这方面的研究。