支持向量机 (Support Vector Machine, SVM)：支持向量机在高维或无限维空间中构造超平面或超平面集合，其可以用于分类、回归或其他任务。直观来说，分类边界距离最近的训练资料点越远越好，因为这样可以缩小分类器的泛化误差。

1. 定义

更正式地来说，支持向量机在高维或无限维空间中构造超平面或超平面集合，其可以用于分类、回归或其他任务。直观来说，分类边界距离最近的训练资料点越远越好，因为这样可以缩小分类器的泛化误差。（来源：维基百科，使用 CC BY-SA 3.0 协议）

对于二维二分类问题如下：

（来源：维基百科，使用 CC BY-SA 3.0 协议）

当我们来对两种样本人工分类的时候，一定是想找到间隔最宽的一个空隙划开，因为我们感觉这样的分类效果最好。

支持向量机和人的思维一致，就是要找到一个分类超平面 $\boldsymbol{w}\cdot\boldsymbol{x}-b=0$，并且希望该超平面支持向量的间隔越大越好，因为这样可以减小在测试集上的泛化误差。

支持向量是训练数据集中最靠近分类超平面的点。

2. 线性 SVM

2.1 硬间隔

2.1.1 间隔的定义

SVM 的核心就是间隔越大越好，那么我们首先要找到间隔的数学表达。

平面中点 $(x_0,y_0)$ 到直线的 $ax+by+c=0$ 距离公式：

$$ d=\frac{|ax_0+by_0+c|}{\sqrt{a^2+b^2}} \tag{a.1} $$

有些资料向量相乘写成 $\boldsymbol{w}\cdot\boldsymbol{x}$，有些资料写成 $\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}$，二者实际是一样的。因为前者是点乘（内积），后者是叉乘（外积）。

将上式推广到多维空间中一样成立。对于超平面 $\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}+b=0$，点 $\boldsymbol{x}$ 到其的距离为：

$$ d=\frac{\lvert\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}+b\rvert}{\lVert\boldsymbol{w}\rVert} \tag{a.2} $$

$\lVert\boldsymbol{x}\rVert$ 为 $\boldsymbol{x}$ 的二范数（下标 2 可省略），其定义是：$\lVert\boldsymbol{x}\rVert_2=\sqrt{\sum_{i=1}^n x_i^2}$

我们将 $\pm1$ 作为每个样本点的类别标签，如果样本可以线性可分，那么一定存在分类超平面满足：

$$ \begin{cases} \boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}_i+b>0,&y_i=1\\ \boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}_i+b<0,&y_i=-1 \end{cases} \tag{a.3} $$

这个条件实际上非常弱，它相当于只规定了分类超平面能把两种样本点隔开，没有任何对间隔的限制。

为了引入间隔，我们假设支持向量到分类超平面的距离为 $d$，那么我们要求分类超平面：

$$ \begin{cases} \text{if }y_i=1,&\text{then }\frac{\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}_i+b}{\lVert\boldsymbol{w}\rVert}\geq d\\ \text{if }y_i=-1,&\text{then }\frac{\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}_i+b}{\lVert\boldsymbol{w}\rVert}\leq -d \end{cases} \tag{a.4} $$

这样表达式中终于包含了间隔。接下来，我们对上式两边除以 $d$：

$$ \begin{cases} \text{if }y_i=1,&\text{then }\frac{\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}_i+b}{\lVert\boldsymbol{w}\rVert d}\geq 1\\ \text{if }y_i=-1,&\text{then }\frac{\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}_i+b}{\lVert\boldsymbol{w}\rVert d}\leq -1 \end{cases} \tag{a.5} $$

由于 $\lVert\boldsymbol{w}\rVert$ 和 $d$ 都是标量，因此除以分母相当于对该超平面进行缩放，实际上超平面是没有变化的。

就像 $2x+4y=0$ 缩放为 $x+2y=0$，两个式子表示的仍然是同一条直线。

因此为了式子简单，我们直接忽略掉缩放的值：

$$ \begin{cases} \text{if }y_i=1,&\text{then }\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}_i+b\geq 1\\ \text{if }y_i=-1,&\text{then }\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}_i+b\leq -1 \end{cases} \tag{a.6} $$

对于支持向量 $\boldsymbol{x}_i$，其满足：

$$ \lvert\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}_i+b\rvert=1 \tag{a.7} $$

那么支持向量与分类超平面的距离为：

$$ d=\frac{\lvert\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}_i+b\rvert}{\lVert\boldsymbol{w}\rVert}=\frac{1}{\lVert\boldsymbol{w}\rVert} \tag{a.8} $$

由于间隔有两侧，那么间隔的距离为：

$$ d=\frac{2}{\lVert\boldsymbol{w}\rVert} \tag{a.9} $$

2.1.2 待求解的问题

获得了间隔的表达式，支持向量机要求解的问题就可以用形式化的语言表达：

$$ \begin{align} &\max_{\boldsymbol{w},b}\frac{2}{\lVert\boldsymbol{w}\rVert}\\ &s.t.\;y_i(\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}_i+b)\geq1 \end{align} \tag{b.1} $$

这里第二行公式把 $y_i$ 乘到左边去了，是为了表达式的简洁。实际上这一行表达的含义与式 $\text{(a.6)}$ 是一模一样的。

我们习惯求最小化问题，因此将以上问题分子分母颠倒，等价转换为：

$$ \begin{align} &\min_{\boldsymbol{w},b}\frac{1}{2}\lVert\boldsymbol{w}\rVert^2\\ &s.t.\;y_i(\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}_i+b)\geq1 \end{align} \tag{b.2} $$

其中，加平方是为了求导时正好能把前面的 $1/2$ 消去。

2.1.3 前置知识

可以先看下一节求解的过程，过程中遇到了对应的方法后再看这一节。

2.1.3.1 拉格朗日乘子法

对于不等式约束优化问题：

$$ \begin{align} &\min_xf(x)\\ &\begin{aligned} s.t.\;&h_i(x)=0,\;i = 1,2,...,m\\ &g_j(x)<0,\;j = 1,2,...,n \end{aligned} \end{align} $$

转化为其对应的无约束的拉格朗日函数：

$$ L(x,\boldsymbol\alpha,\boldsymbol\beta)=f(x)+\sum_{i=1}^m\alpha_i h_i(x) +\sum_{j=1}^n\beta_jg_j(x) $$

要满足 KKT 条件：

$$ \begin{align} \frac{\partial L(x,\boldsymbol\alpha,\boldsymbol\beta)}{\partial x}&= 0\tag{1}\\ \beta_jg_j(x) &= 0 , \ j=1,2,...,n\tag{2}\\ h_i(x)&= 0 , \ i=1,2,...,m\tag{3}\\ g_j(x) &\le 0 , \ j=1,2,...,n\tag{4}\\ \beta_j &\ge 0 , \ j=1,2,...,n\tag{5}\\ \end{align} $$

其中：

1. 拉格朗日取得可行解的必要条件
2. 松弛互补条件
3. 初始的约束条件
4. 初始的约束条件
5. 不等式约束的拉格朗日乘子需满足的条件

2.1.3.2 拉格朗日对偶

对于原问题：

$$ p^*=\min_x\max_{\alpha,\beta;\beta_i\geq0}L(x,\alpha,\beta) $$

它的对偶问题为：

$$ d^*=\max_{\alpha,\beta;\beta_i\geq0}\min_x L(x,\alpha,\beta) $$

定义以下式子：

$$ \begin{align} f(\alpha,\beta)&=\min_x L(x,\alpha,\beta)\\ d^*&=\max_{\alpha,\beta;\beta_i\geq0}f(\alpha,\beta)=\max_{\alpha,\beta;\beta_i\geq0}\min_x L(x,\alpha,\beta)\\ g(x)&=\max_{\alpha,\beta;\beta_i\geq0} L(x,\alpha,\beta)\\ p^*&=\min_x g(x)=\min_x\max_{\alpha,\beta;\beta_i\geq0}L(x,\alpha,\beta)\\ \end{align} $$

我们可以写出如下不等式：

$$ f(\alpha,\beta)=\min_x L(x,\alpha,\beta)\leq L(x,\alpha,\beta)\leq\max_{\alpha,\beta;\beta_i\geq0} L(x,\alpha,\beta)=g(x) $$

再进一步转换到 $d^*$ 与 $p^*$ 上：

$$ d^*=\max_{\alpha,\beta;\beta_i\geq0}f(\alpha,\beta)\leq\min_x g(x)=p^* $$

综上，我们可以得到原问题 $p^*$ 和对偶问题 $d^*$ 的最优解的关系：

$$ d^*\leq p^* $$

2.1.3.3 SMO 算法

SMO (Sequential Minimal Optimization) 算法的基本步骤：

• 选取一对需要更新的变量 $\alpha_i$ 与 $\alpha_j$
• 固定 $\alpha_i$ 与 $\alpha_j$ 以外的参数，求解出更新后的 $\alpha_i$ 与 $\alpha_j$

一直循环以上两个步骤，直到收敛。

对于选取的 $\alpha_i$ 与 $\alpha_j$，可以使用随机选取的方法，但是该方法收敛速度较慢。更优的方法是选取最不满足 KKT 条件的参数，这样更新时收敛速度会更快。

2.1.4 求解支持向量机

2.1.4.1 问题转换

由拉格朗日乘子法，我们列出拉格朗日函数：

$$ L(\boldsymbol{w},b,\boldsymbol{\alpha})=\frac{1}{2}\lVert\boldsymbol{w}\rVert^2+\sum_{i=1}^m \alpha_i(1-y_i(\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}_i+b)) $$

其中 $\alpha_i\geq0$，为拉格朗日乘子；$m$ 为样本点的数量。

我们知道，$1-\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}_i+b\leq0$，因此式子后半段的求和项一定 $\leq0$，那么 $L(\boldsymbol{w},b,\boldsymbol{\alpha})$ 的最大值为 $\frac{1}{2}\lVert\boldsymbol{w}\rVert^2$ 即原问题：

$$ \max_{\boldsymbol{\alpha}}L(\boldsymbol{w},b,\boldsymbol{\alpha})=\frac{1}{2}\lVert\boldsymbol{w}\rVert^2 $$

我们要求的是原问题的最小值，因此问题转换为：

$$ \min_{\boldsymbol{w},b}\max_{\boldsymbol{\alpha}}L(\boldsymbol{w},b,\boldsymbol{\alpha}) $$

该问题不好求解，因此使用拉格朗日对偶法转换为对偶问题，我们求出对偶问题的最大值，便是原问题的下界：

$$ \max_{\boldsymbol{\alpha}}\min_{\boldsymbol{w},b}L(\boldsymbol{w},b,\boldsymbol{\alpha}) $$

2.1.4.2 求解问题

第一步，求解内层问题：

$$ \min_{\boldsymbol{w},b}L(\boldsymbol{w},b,\boldsymbol{\alpha})=\min_{\boldsymbol{w},b}\frac{1}{2}\lVert\boldsymbol{w}\rVert^2+\sum_{i=1}^m \alpha_i(1-y_i(\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}_i+b)) \tag{e.1} $$

首先对 $\boldsymbol{w}$ 与 $b$ 求偏导，并算出偏导为 $0$ 时的解：

$$ \begin{align} &\begin{cases} \displaystyle{\frac{\partial L(\boldsymbol{w},b,\boldsymbol{\alpha})}{\partial\boldsymbol{w}}=\boldsymbol{w}-\sum_{i=1}^m \alpha_i y_i\boldsymbol{x}_i=0}\\ \displaystyle{\frac{\partial L(\boldsymbol{w},b,\boldsymbol{\alpha})}{\partial b}=\sum_{i=1}^m \alpha_i y_i=0} \end{cases}\\ \Rightarrow &\begin{cases} \displaystyle{\boldsymbol{w}=\sum_{i=1}^m \alpha_i y_i \boldsymbol{x}_i}\\ \displaystyle{\sum_{i=1}^m \alpha_i y_i=0} \end{cases} \end{align} \tag{e.2} $$

将上式的解带入式 $(18)$，即可得到内层问题的解如下，我们令该结果为 $L(\boldsymbol{\alpha})$：

$$ L(\boldsymbol{\alpha})=\min_{\boldsymbol{w},b}L(\boldsymbol{w},b,\boldsymbol{\alpha})=\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_j y_i y_j \boldsymbol{x}_i^{\mathrm{T}}\boldsymbol{x}_j \tag{e.3} $$

我们发现还有个条件 $\sum_{i=1}^m \alpha_i y_i=0$ 还没用上，它将会在后续作为约束条件使用。

另外，我们令要计算的分割超平面为 $g(\boldsymbol{x})=\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}+b$，将 $\boldsymbol{w}$ 的值代入后得到：

$$ g(\boldsymbol{x})=\sum_{i=1}^m \alpha_i y_i \boldsymbol{x}_i^{\mathrm{T}}\boldsymbol{x}+b \tag{e.4} $$

第二步，求解外层问题：

$$ \begin{align} &\max_{\boldsymbol{\alpha}}L(\boldsymbol{\alpha})=\max_{\boldsymbol{\alpha}}\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_j y_i y_j \boldsymbol{x}_i^{\mathrm{T}}\boldsymbol{x}_j\\ &s.t.\;\sum_{i=1}^m\alpha_i y_i=0,\;\alpha_i\geq0 \end{align} \tag{e.5} $$

我们习惯求最小值，因此给上述问题乘上一个 $-1$ 转换成等价问题：

$$ \begin{align} &\min_{\boldsymbol{\alpha}}L(\boldsymbol{\alpha})=\min_{\boldsymbol{\alpha}}\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_j y_i y_j \boldsymbol{x}_i^{\mathrm{T}}\boldsymbol{x}_j-\sum_{i=1}^m\alpha_i\\ &s.t.\;\sum_{i=1}^m\alpha_i y_i=0,\;\alpha_i\geq0 \end{align} \tag{e.6} $$

该问题还需要满足 KKT 条件：

$$ \begin{cases} \alpha_i\geq0\\ y_i(\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}_i+b)-1\geq0\\ \alpha_i(y_i(\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}_i+b)-1)=0 \end{cases} \tag{e.7} $$

对于该问题，我们共有 $m$ 个 $\alpha_i$ 等待优化，这个量实在是太大了，不可能同时进行优化求解。使用 SMO 算法可以解决这个问题。

第三步，使用 SMO 求解外层问题：

不妨设我们选择要优化的变量为 $\alpha_1$ 与 $\alpha_2$，问题可以写为：

$$ \begin{align} & \begin{aligned} \min_{\alpha_1,\alpha_2}L(\alpha_1,\alpha_2)&=\min_{\alpha_1,\alpha_2}\frac{1}{2}\alpha_1^2\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_1+\frac{1}{2}\alpha_2^2\boldsymbol{x}_2^{\mathrm{T}}\boldsymbol{x}_2+\alpha_1\alpha_2y_1y_2\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_2\\ &-\alpha_1-\alpha_2+\alpha_1y_1\sum_{i=3}^m y_i\alpha_i\boldsymbol{x}_i^{\mathrm{T}}\boldsymbol{x}_1+\alpha_2y_2\sum_{i=3}^m y_i\alpha_i\boldsymbol{x}_i^{\mathrm{T}}\boldsymbol{x}_2\\ \end{aligned}\\ &s.t.\;\alpha_1y_1+\alpha_2y_2=-\sum_{i=3}^m\alpha_i y_i,\;\alpha_i\geq0 \end{align} \tag{e.8} $$

注意上式的前两项没有 $y_i$ 了，因为 $y_i=\pm1$，所以 $y_i^2=1$ 可以直接省略。另外由于变量相当于只剩 $\alpha_1$ 和 $\alpha_2$，因此后面的双层连加变成了两个单层连加。下面该技巧也会用到多次，也会反向用到。

上式的约束条件可以进行变形：

$$ \begin{align} &\alpha_1y_1+\alpha_2y_2=-\sum_{i=3}^m\alpha_i y_i\\ \Rightarrow&\alpha_1=(-\sum_{i=3}^m\alpha_i y_i-\alpha_2y_2)y_1 \end{align} \tag{e.9} $$

其中除了 $\alpha_1$ 与 $\alpha_2$ 之外的其他变量全部都是已知的，因此 $\alpha_1$ 与 $\alpha_2$ 之间存在确定的关系。如果知道了二者其一，另一个也可以直接计算得到。因此，上面两个变量的优化问题实际上是一个变量的优化问题，完全可以将另一个变量代入替换。

为了式子简洁，我们令：

$$ \begin{align} f&=-\sum_{i=3}^m\alpha_i y_i=\alpha_1y_1+\alpha_2y_2\\ v_i&=\sum_{j=3}^my_j\alpha_j\boldsymbol{x}_j^{\mathrm{T}}\boldsymbol{x}_i=g(x_i)-\sum_{j=1}^2y_j\alpha_j\boldsymbol{x}_j^{\mathrm{T}}\boldsymbol{x}_i-b \end{align} \tag{e.10} $$

通过式 $\text{(e.9)}$ 将式 $\text{(e.8)}$ 中的所有 $\alpha_1$ 替换为 $\alpha_2$，另外使用式 $\text{(e.10)}$ 的第二个等号前半段化简式 $\text{(e.8)}$ 中的表示方法（第二个等号后半段将在后续操作中用到），可以得到：

$$ \begin{align} &\begin{aligned} \min_{\alpha_2}L(\alpha_2)&=\min_{\alpha_2}\frac{1}{2}(f-\alpha_2y_2)^2\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_1+\frac{1}{2}\alpha_2^2\boldsymbol{x}_2^{\mathrm{T}}\boldsymbol{x}_2+(f-\alpha_2y_2)\alpha_2y_2\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_2\\ &-(f-\alpha_2y_2)y_1-\alpha_2+(f-\alpha_2y_2)v_1+\alpha_2y_2v_2\\ \end{aligned}\\ &s.t.\;\alpha_i\geq0 \end{align} \tag{e.11} $$

此时，整个式子已经只剩 $\alpha_2$ 这一个参数了，我们终于可以对它求偏导并置为 $0$ 得到结果了：

$$ \begin{align} \frac{\partial L(\alpha_2)}{\partial\alpha_2}&=\alpha_2\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_1-fy_2\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_1+\alpha_2\boldsymbol{x}_2^{\mathrm{T}}\boldsymbol{x}_2-fy_2\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_2-2\alpha_2\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_2+y_1y_2-1-y_2v_1+y_2v_2=0\\ &\Rightarrow\alpha_2(\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_1+\boldsymbol{x}_2^{\mathrm{T}}\boldsymbol{x}_2-2\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_2)=y_2(f\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_1-f\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_2-y_1+y_2+v_1-v_2) \end{align} \tag{e.12} $$

此时这个式子已经能用来计算结果了，但是还不够简单，编程实现比较麻烦，我们可以进一步进行化简。

首先注意到式 $(28)$ 的后半段，$f$ 和 $v_i$ 其实可以转化成关于 $\alpha_1,\alpha_2$ 的式子，为了区分新算出来的 $\alpha$，我们将$f$ 和 $v_i$ 里的记作 $\alpha_1^{old},\alpha_2^{old}$.同时，我们令损失值 $E_i$ 为预测值与实际值的差：

$$ E_i=g(x_i)-y_i=\sum_{i=j}^m \alpha_j y_j \boldsymbol{x}_j^{\mathrm{T}}\boldsymbol{x_i}+b-y_i \tag{e.13} $$

将 $\text{(e.10)}$ 的后半段与 $\text{(e.13)}$ 代入 $\text{(e.12)}$，即可得到以下式子：

$$ \begin{align} &\alpha_2^{newunc}(\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_1+\boldsymbol{x}_2^{\mathrm{T}}\boldsymbol{x}_2-2\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_2)\\ =\;&y_2(f\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_1-f\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_2-y_1+y_2+v_1-v_2)\\ =\;&y_2((\alpha_1^{old}y_1+\alpha_2^{old}y_2)\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_1-(\alpha_1^{old}y_1+\alpha_2^{old}y_2)\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_2-y_1+y_2\\ &+g(x_1)-y_1\alpha_1^{old}\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_1-y_2\alpha_2^{old}\boldsymbol{x}_2^{\mathrm{T}}\boldsymbol{x}_1-b\\ &-g(x_2)+y_1\alpha_1^{old}\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_2+y_2\alpha_2^{old}\boldsymbol{x}_2^{\mathrm{T}}\boldsymbol{x}_2+b)\\ =\;&y_2(\alpha_2^{old}y_2\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_1+\alpha_2^{old}y_2\boldsymbol{x}_2^{\mathrm{T}}\boldsymbol{x}_2-2\alpha_2^{old}y_2\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_2+E_1-E_2)\\ =\;&\alpha_2^{old}\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_1+\alpha_2^{old}y\boldsymbol{x}_2^{\mathrm{T}}\boldsymbol{x}_2-2\alpha_2^{old}y\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_2+y_2(E_1-E_2)\\ =\;&\alpha_2^{old}(\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_1+\boldsymbol{x}_2^{\mathrm{T}}\boldsymbol{x}_2-2\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_2)+y_2(E_1-E_2) \end{align} \tag{e.14} $$

令 $\eta=\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_1+\boldsymbol{x}_2^{\mathrm{T}}\boldsymbol{x}_2-2\boldsymbol{x}_1^{\mathrm{T}}\boldsymbol{x}_2$，将上式左右同除以 $\eta$ 得到：

$$ \alpha_2^{newunc}=\alpha_2^{old}+\frac{y_2(E_1-E_2)}{\eta} \tag{e.15} $$

如此，我们将式 $\text{(e.12)}$ 化简得到了非常优美的新式子，编程实现时更加简单。

上面求出来的答案并不是最终答案，我们还需要注意到约束条件 $\alpha_i\geq0$，我们计算得到的 $\alpha_1$ 和 $\alpha_2$ 都要满足该条件。

对 $y_1$ 与 $y_2$ 的符号进行分类讨论：

• $y_1=y_2$

由式 $\text{(e.10)}$，我们不关心符号，因此将符号并入 $t$ 中得到：

$$ \begin{align} &y_1\alpha_1+y_2\alpha_2=f\\ \Rightarrow\;&\alpha_1+\alpha_2=t \end{align} $$

由于 $\alpha_1\geq0,\;\alpha_2\geq0$ 可知：

$$ 0\leq\alpha_2^{new}\leq t=\alpha_1^{old}+\alpha_2^{old} $$

由此，我们可以将 $\alpha_2^{newunc}$ 剪辑：

$$ \alpha_2^{new}= \begin{cases} \alpha_1^{old}+\alpha_2^{old},&\alpha_1^{old}+\alpha_2^{old}<\alpha_2^{newunc}\\ \alpha_2^{newunc},&0\leq\alpha_2^{newunc}\leq\alpha_1^{old}+\alpha_2^{old}\\ 0,&\alpha_2^{newunc}<0 \end{cases} $$

• $y_1\neq y_2$

由式 $\text{(e.10)}$，我们不关心符号，因此将符号并入 $t$ 中得到：

$$ \begin{align} &y_1\alpha_1+y_2\alpha_2=f\\ \Rightarrow\;&\alpha_2-\alpha_1=t \end{align} $$

由于 $\alpha_1\geq0,\;\alpha_2\geq0$ 可知：

$$ 0\leq\alpha_2^{new}\leq t=\alpha_2^{old}-\alpha_1^{old} $$

由此，我们可以将 $\alpha_2^{newunc}$ 剪辑：

$$ \alpha_2^{new}= \begin{cases} \alpha_1^{old}+\alpha_2^{old},&\alpha_2^{old}-\alpha_1^{old}<\alpha_2^{newunc}\\ \alpha_2^{newunc},&0\leq\alpha_2^{newunc}\leq\alpha_2^{old}-\alpha_1^{old}\\ 0,&\alpha_2^{newunc}<0 \end{cases} $$

2.2 软间隔

2.2.1 软间隔的定义

上述硬间隔 SVM 考虑的情况比较理想，样本点不存在噪音。如果样本点存在噪音，将会对硬间隔 SVM 造成干扰，导致泛化能力下降。或者样本点线性不可分，硬间隔 SVM 就无法处理。

在硬间隔 SVM 里，我们要求两类样本点一定分别分布于分割超平面两侧，即样本点一定被分割超平面正确分割。在软间隔 SVM 里，我们降低这个要求，允许样本点被错误分类。

如果样本点能随便被错误分类，那么就没办法找最优解了，因此样本点被错误分类时要有一定的代价，而正确分类时没有代价。我们将其与 $\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}+b=\pm1$ 距离作为代价（松弛变量）$\xi\geq0$：

$$ \xi_i=l(y_i(\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}_i+b)-1) $$

其中，$l(\cdot)$ 可以有多种选择，下面的后三个是连续的函数：

$$ \begin{align} l_{0/1}(z)&= \begin{cases} 1&z<0\\ 0&\text{otherwise} \end{cases}\\\\ l_{\text{hinge}}(z)&=\max\{0,1-z\}\\\\ l_{\text{exp}}&=e^{-z}\\\\ l_{\text{log}}&=\log(1+e^{-z}) \end{align} $$

它们的函数图像如下：

2.2.2 待求解的问题

将硬间隔 SVM 的问题加上松弛变量后，便是软间隔 SVM 待求解的问题：

$$ \begin{align} &\min_{\boldsymbol{w},b}\frac{1}{2}\lVert\boldsymbol{w}\rVert^2+C\sum_{i=1}^m\xi_i\\ &s.t.\;y_i(\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}_i+b)\geq1-\xi_i \end{align} $$

其中 $C$ 的值是松弛量的权重，$C$ 越大即代表优化该问题时，更多考虑松弛量，即让错误分类的样本越少，反之则是允许错误分类的样本越多。

2.2.3 求解支持向量机

软间隔与硬间隔 SVM 的求解过程基本相同，因此下面写的比较简略。

由拉格朗日乘子法，我们列出拉格朗日函数：

$$ L(\boldsymbol{w},b,\boldsymbol{\alpha},\boldsymbol{\xi},\boldsymbol{\mu})=\frac{1}{2}\lVert\boldsymbol{w}\rVert^2+C\sum_{i=1}^m\xi_i+\sum_{i=1}^m \alpha_i(1-y_i(\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}_i+b))-\sum_{i=1}^m\mu_i\xi_i $$

由于 $\xi_i\geq0$，因此最后一项是减而不是加。

其中 $\alpha_i\geq0,\;\mu_i\geq0$，为两种拉格朗日乘子；$m$ 为样本点的数量。

原问题为：

$$ \min_{\boldsymbol{w},b,\boldsymbol{\xi}}\max_{\boldsymbol{\alpha},\boldsymbol{\mu}}L(\boldsymbol{w},b,\boldsymbol{\alpha},\boldsymbol{\xi},\boldsymbol{\mu}) $$

转化为对偶问题：

$$ \max_{\boldsymbol{\alpha},\boldsymbol{\mu}}\min_{\boldsymbol{w},b,\boldsymbol{\xi}}L(\boldsymbol{w},b,\boldsymbol{\alpha},\boldsymbol{\xi},\boldsymbol{\mu}) $$

对内层问题，求偏导得到解：

$$ \begin{align} &\begin{cases} \displaystyle{\frac{\partial L(\boldsymbol{w},b,\boldsymbol{\alpha},\boldsymbol{\xi},\boldsymbol{\mu})}{\partial\boldsymbol{w}}=\boldsymbol{w}-\sum_{i=1}^m \alpha_i y_i\boldsymbol{x}_i=0}\\ \displaystyle{\frac{\partial L(\boldsymbol{w},b,\boldsymbol{\alpha},\boldsymbol{\xi},\boldsymbol{\mu})}{\partial b}=\sum_{i=1}^m \alpha_i y_i=0}\\ \displaystyle{\frac{\partial L(\boldsymbol{w},b,\boldsymbol{\alpha},\boldsymbol{\xi},\boldsymbol{\mu})}{\partial\xi_i}}=C-\alpha_i-\mu_i=0 \end{cases}\\ \Rightarrow &\begin{cases} \displaystyle{\boldsymbol{w}=\sum_{i=1}^m \alpha_i y_i \boldsymbol{x}_i}\\ \displaystyle{\sum_{i=1}^m \alpha_i y_i=0}\\ \displaystyle{C=\alpha_i+\mu_i} \end{cases} \end{align} $$

由 $\alpha_i\geq0,\;\mu_i\geq0,\;C=\alpha_i+\mu_i$ 可得：$0\leq\alpha_i\leq C$. 回代后，得到再对外层问题求解：

$$ \begin{align} &\max_{\boldsymbol{\alpha}}L(\boldsymbol{\alpha})=\max_{\boldsymbol{\alpha}}\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_j y_i y_j \boldsymbol{x}_i^{\mathrm{T}}\boldsymbol{x}_j\\ &\begin{aligned} s.t.\;&\sum_{i=1}^m\alpha_i y_i=0,\\ &0\leq\alpha_i\leq C\\ &\alpha_i\geq0\\ \end{aligned} \end{align} $$

该问题还需要满足 KKT 条件：

$$ \begin{cases} \alpha_i\geq0\\ \mu_i\geq0\\ \xi_i\geq0\\ \mu_i\xi_i\geq0\\ y_i(\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}_i+b)-1+\xi_i\geq0\\ \alpha_i(y_i(\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}_i+b)-1+\xi_i)=0 \end{cases} $$

接下来的 SMO 过程一模一样，最后得到：

$$ \alpha_2^{newunc}=\alpha_2^{old}+\frac{y_2(E_1-E_2)}{\eta} $$

然后要对其进行剪辑：

$$ \alpha_2^{new}= \begin{cases} H,&H<\alpha_2^{newunc}\\ \alpha_2^{newunc},&L\leq\alpha_2^{newunc}\leq H\\ L,&\alpha_2^{newunc}<L \end{cases} $$

具体的范围如下，对 $y_1,y_2$ 分类讨论：

• $y_1=y_2$

$$ \begin{cases} L=\max\{0,\alpha_2^{old}-\alpha_1^{old}-C\}\\ H=\min\{C,\alpha_2^{old}-\alpha_1^{old}\} \end{cases} $$

• $y_1\neq y_2$

$$ \begin{cases} L=\max\{0,\alpha_2^{old}-\alpha_1^{old}\}\\ H=\min\{C,C+\alpha_2^{old}-\alpha_1^{old}\} \end{cases} $$

3. 非线性 SVM

$\varphi$ 是一个从低维的输入空间 $\mathcal{X}$ 到高维的希尔伯特空间 $\mathcal{H}$ 的映射。如果存在函数 $\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)$ 对于任意 $\boldsymbol{x}_i,\boldsymbol{x}_j\in\mathcal{X}$ 都有：

$$ \kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)=\varphi(\boldsymbol{x_i})\varphi(\boldsymbol{x_j}) $$

就称 $\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)$ 为核函数。

通过核函数，我们可以将样本点从低维空间 $\mathcal{X}$ 映射到高维 $\mathcal{H}$，在低维空间中线性不可分的样本点，可能在高维空间中线性可分，由此便可以解决线性不可分的数据。

对于核函数 $\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)$，我们没有必要知道其对应的 $\varphi(\boldsymbol{x})$ 是多少，因为它的表达可能会非常复杂。我们只需要知道 $\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)$ 的表达式便可以使用它了。常用的核函数有：

要使用核函数，公式推导过程和前文一模一样，只需要把公式内的 $\boldsymbol{x}_i^{\mathrm{T}}\boldsymbol{x}_j$ 替换成 $\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)$ 就行了。