前言

支持向量机是定义在特征空间上使得间隔最大的线性分类器。它可以形式化为凸二次规划问题。对于这样的凸二次规划问题，我们往往使用拉格朗日方法转为为它的对偶问题。对于这样的对偶问题，我们可以使用SMO最小序列算法进行求解。

我们将介绍三种支持向量机。当数据线性可分时，我们采用线性可分支持向量机；当数据近似线性可分，或者说去除掉数据中的某些点后剩余数据是线性可分的，则可以采用线性支持向量机；当数据线性不可分，则应该采用非线性支持向量机。

在进入具体的模型之前，我们先来看一个问题。

给定一个超曲面 $w\cdot x+b=0$，如果存在另一个点 $x_1$，则这个点与超平面距离是多少？

我们假设超平面上的一点 $x_2$，则 $x_1$ 与超平面的距离可以表示为
$$\begin{array}{lll}|\frac{w}{||w||}\cdot (x_1-x_2)|& =& \frac{|w\cdot x_1-w\cdot x_2|}{||w||}\\ & =& \frac{|w\cdot x_1+b|}{||w||}\end{array}$$

这里，$\frac{w}{||w||}$ 为超平面的单位法向量。第二个等号成立是因为 $x_2$ 在超平面上，也就意味着满足 $w\cdot x_2+b=0$。

有了上面的结论，我们就可以接着来介绍 函数距离和几何距离。

对于线性可分的数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } T=\{(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)\} T={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}， y i ∈ { − 1 , + 1 } y_i\in\{-1, +1\} yi​∈{−1,+1}，必然存在一个超平面 $w\cdot x+b=0$ 使得能够正确分割正负类别的数据点，也就是说，满足 对所有的 $i$，不等式$y_i(w\cdot x_i+b)>0$恒成立。

此时，借助上面问题的结论，我们有数据集中任意一点 $x_i$ 到超平面 $w\cdot x+b=0$ 的距离为
$$\frac{|w\cdot x_i+b|}{||w||}=\frac{y_i(w\cdot x_i+b)}{||w||}$$

这个等式成立，是因为正确分类的数据点 $x_i$ 始终满足 $y_i(w\cdot x_i+b)>0$ 且 $y_i=\pm 1$，则 $|w\cdot x_i+b|=y_i(w\cdot x_i+b)$。

在这里，我们将 $\frac{y_i(w\cdot x_i+b)}{||w||}$ 称为$x_i$ 到超平面的几何距离，而 $y_i(w\cdot x_i+b)$ 称为 $x_i$ 到超平面的函数距离。

有了函数距离和几何距离的定义，下面我们将依次介绍三种支持向量机。

1. 线性可分支持向量机

1.1 凸二次规划问题

对于线性可分的数据集，根据线性可分数据集的定义，我们知道必然有一个超平面，使得该超平面能够正确分开所有数据点。

但支持向量机的目标是，找到那个具有最大几何距离的那个超平面，也就是说，使得超平面能够尽可能在不同类别的数据中间，同时尽可能远离数据点。这样，超平面就可以更加明显地区分不同标记的数据点。

因此，对于线性可分的数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } T=\{(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)\} T={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}，我们给出如下最优化问题：
$$\underset{w,b}{\max }\underset{i=1,2,...,N}{\min }\frac{y_i(w\cdot x_i+b)}{||w||}$$
将上式展开，有
$$\begin{array}{lll}& \underset{w,b}{\max }& \gamma \\ & s.t.& \frac{y_i(w\cdot x_i+b)}{||w||}\ge \gamma ,i=1,2,...,N\end{array}$$

显然， $$\underset{w,b}{\max }\underset{i=1,2,...,N}{\min }\frac{y_i(w\cdot x_i+b)}{||w||}=\underset{w,b}{\max }\frac{1}{||w||}\underset{i=1,2,...,N}{\min }{y}_i(w\cdot x_i+b)$$

而这意味着上面的最优化问题等价于
$$\begin{array}{lll}& \underset{w,b}{\max }& \frac{\gamma }{||w||}(1)\\ & s.t.& y_i(w\cdot x_i+b)\ge \gamma ,i=1,2,...,N\end{array}$$

我们接下来说明优化问题(1)与
$$\begin{array}{lll}& \underset{w,b}{\max }& \frac{1}{||w||}(2)\\ & s.t.& y_i(w\cdot x_i+b)\ge 1,i=1,2,...,N\end{array}$$
等价。

令 $\gamma (w,b)=\underset{i=1,2,...,N}{\min }{y}_i(w\cdot x_i+b)$。假设问题（1）的最优解为 $(w_1,b_1)$，问题（2）的最优解为 $(w_2,b_2)$。

• $(\frac{w_1}{\gamma (w_1,b_1)},\frac{b_1}{\gamma (w_1,b_1)})$ 是问题（2）的一个可行解，这是因为 $\gamma \left(\frac{w_1}{\gamma (w_1,b_1)},\frac{b_1}{\gamma (w_1,b_1)}\right)=1$。由于 $(w_2,b_2)$ 是问题（2）的最优解，所以，我们有 $$\frac{1}{||w_2||}\ge \frac{1}{||\frac{w_1}{\gamma (w_1,b_1)}||}=\frac{\gamma (w_1,b_1)}{||w_1||}$$
• $(w_2,b_2)$ 同样是问题（1）的一个可行解，这是因为问题（1）等价于 $\underset{w,b}{\max }\frac{1}{||w||}\underset{i=1,2,...,N}{\min }{y}_i(w\cdot x_i+b)$，则 $$\begin{array}{lll}& & \underset{w,b}{\max }\frac{1}{||w||}\underset{i=1,2,...,N}{\min }{y}_i(w\cdot x_i+b)\\ & =& \frac{\gamma (w_1,b_1)}{||w_1||}\\ & \ge & \frac{\gamma (w_2,b_2)}{||w_2||}\\ & =& \frac{1}{||w_2||}\end{array}$$
• 综合上面两点，我们有等式 $$\frac{1}{||w_2||}=\frac{\gamma (w_1,b_1)}{||w_1||}$$ 这就说明 $(\frac{w_1}{\gamma (w_1,b_1)},\frac{b_1}{\gamma (w_1,b_1)})$ 是问题（2）的一个最优解；而 $(w_2,b_2)$ 是问题（1）的一个最优解。联系到问题（1）与问题（2）的最优解的唯一性，因此，我们有 $(w_1,b_1)=(w_2,b_2)$ 且 $\gamma (w_1,b_1)=1$。因此，问题（1）与问题（2）是等价的。

对于问题（2），$\underset{w,b}{\max }\frac{1}{||w||}$ 等价于 $\underset{w,b}{\min }||w||$，而 $\underset{w,b}{\min }||w||$ 等价于 $\underset{w,b}{\min }\frac{1}{2}||w|{|}^2$。因此，问题（2）等价于
$$\begin{array}{lll}& \underset{w,b}{\min }& \frac{1}{2}||w|{|}^2(3)\\ & s.t.& y_i(w\cdot x_i+b)\ge 1,i=1,2,...,N\end{array}$$

最终，我们将问题转化为问题（3）的形式，而问题（3）是一个凸二次规划的问题。

1.2 对偶问题

我们通过拉格朗日方法，将问题（3）转化为对偶问题。之所以转化为对偶问题，是因为对偶问题相对简单，同时自然引入核函数的概念。

通过拉格朗日方法，我们有拉格朗日函数
$$L(w,b,\alpha )=\frac{1}{2}||w|{|}^2-\sum _{i=1}^N{\alpha }_i{y}_i(w\cdot x_i+b)+\sum _{i=1}^N{\alpha }_i$$

其中，${\alpha }_i\ge 0，i=1,2,...,N$。

原始问题可以写为 $$\underset{w,b}{\min }\underset{\alpha }{\max }L(w,b,\alpha )$$

之所以这是原始问题，是因为从上面的表达式中，可以还原出问题（3）。我们可以这样看：

• 我们要选择 $(w,b)$ 使得选出最小的 $\underset{\alpha }{\max }L(w,b,\alpha )$；
• 仔细观察 $L(w,b,\alpha )$，可以看到 ${\alpha }_i$ 前面的系数为 $1-y_i(w\cdot x_i+b)$；
• 如果 $1-y_i(w\cdot x_i+b)>0$，则我们可以选择特别大的${\alpha }_i$，使得 $\underset{\alpha }{\max }L(w,b,\alpha )=+\infty$；
• 因此，为了确保使得 $\underset{\alpha }{\max }L(w,b,\alpha )$ 不是无限大，我们必须挑选 $(w,b)$ 使得 $1-y_i(w\cdot x_i+b)\le 0$ 对任意 $i$ 恒成立，这就意味着问题（3）的约束条件被还原出来；
• 当 $1-y_i(w\cdot x_i+b)\le 0$ 时，为了 $\underset{\alpha }{\max }L(w,b,\alpha )$，显然，对于 $1-y_i(w\cdot x_i+b)<0$ 严格成立的点，我们必须令 ${\alpha }_i=0$；而对于 $1-y_i(w\cdot x_i+b)=0$ 的点，我们则对 ${\alpha }_i>0$;
• 这样，我们可以保证 ${\sum }_{i=1}^N\left(1-y_i(w\cdot x_i+b)\right)=0$，此时，$\underset{w,b}{\min }\underset{\alpha }{\max }L(w,b,\alpha )=\underset{w,b}{\min }\frac{1}{2}||w|{|}^2$。这时，目标函数也被还原出来。

综合上面的叙述，我们可以看出，原始问题为
$$\underset{w,b}{\min }\underset{\alpha }{\max }L(w,b,\alpha )$$

此时，所谓的对偶问题为
$$\underset{\alpha }{\max }\underset{w,b}{\min }L(w,b,\alpha )$$

一般来说，这两个问题的解并不一定相等，但从库恩塔克定理可以知道，只要原问题的目标函数以及不等式约束是凸函数，则原问题与对偶问题的解一致。

现在，我们尝试求解对偶问题。

给定 $\alpha$，我们求 $\underset{w,b}{\min }L(w,b,\alpha )$。具体的，我们对 $L(w,b,\alpha )$ 分别关于 $(w,b)$ 求导，则
$$\frac{\partial L(w,b,\alpha )}{\partial w}=w-\sum _{i=1}^N{\alpha }_i{y}_i{x}_i=0$$

$$\frac{\partial L(w,b,\alpha )}{\partial b}=-\sum _{i=1}^N{\alpha }_i{y}_i=0$$

解得 $w={\sum }_{i=1}^N{\alpha }_i{y}_i{x}_i$ 和 ${\sum }_{i=1}^N{\alpha }_i{y}_i=0$。将结果代入 $L(w,b,\alpha )$，可得

$$\begin{array}{lll}L(w(\alpha ),b(\alpha ),\alpha )& =& \frac{1}{2}||w|{|}^2-{\sum }_{i=1}^N{\alpha }_i{y}_i(w\cdot x_i+b)+{\sum }_{i=1}^N{\alpha }_i\\ & =& \frac{1}{2}w\cdot w-{\sum }_{i=1}^N{\alpha }_i{y}_i{x}_i\cdot w-b{\sum }_{i=1}^N{\alpha }_i{y}_i+\sum {\alpha }_i\\ & =& \frac{1}{2}w\cdot w-w\cdot w+\sum {\alpha }_i\\ & =& -\frac{1}{2}w\cdot w+\sum {\alpha }_i\\ & =& -\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i\cdot x_j+{\sum }_{i=1}^N{\alpha }_i\end{array}$$

因此，对偶问题转化为问题
$$\begin{array}{lll}& \underset{\alpha }{\max }& L(\alpha )=-\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i\cdot x_j+{\sum }_{i=1}^N{\alpha }_i\\ & s.t.& {\sum }_{i=1}^N{\alpha }_i{y}_i=0\\ & & {\alpha }_i\ge 0,i=1,2,...,N\end{array}$$

上面的问题可以通过SMO算法（快速最小序列算法）得到解 ${\alpha }^{\ast }$。

根据库恩塔克条件，我们知道最优解 $(w^{\ast },b^{\ast },{\alpha }^{\ast })$ 满足
$$\begin{array}{rll}\frac{\partial L}{\partial w}{|}_{(w,b,\alpha )=(w^{\ast },b^{\ast },{\alpha }^{\ast })}& =& w^{\ast }-{\sum }_{i=1}^N{\alpha }_i^{\ast }{y}_i{x}_i=0\\ \frac{\partial L}{\partial b}{|}_{(w,b,\alpha )=(w^{\ast },b^{\ast },{\alpha }^{\ast })}& =& -{\sum }_{i=1}^N{\alpha }_i^{\ast }{y}_i=0\\ {\alpha }_i^{\ast }(1-y_i(w^{\ast }\cdot x_i+b^{\ast }))& =& 0,i=1,2,...,N\\ 1-y_i(w^{\ast }\cdot x_i+b^{\ast })& \le & 0,i=1,2,...,N\\ {\alpha }_i^{\ast }& \ge & 0,i=1,2,...,N\end{array}$$

从条件可知

• 由第一个等式可知，$$w^{\ast }=\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i{x}_i$$
• 由第三个等式可知，必然存在一个 ${\alpha }_j^{\ast }>0$，这是因为如果所有的 ${\alpha }_j^{\ast }=0$，则 $w^{\ast }=0$，这显然不是最优解，因此，对于第j个数据，有 $1-y_j(w^{\ast }\cdot x_j+b^{\ast })=0$，得 $$b^{\ast }=y_j-\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i{x}_i\cdot x_j$$

2. 线性支持向量机

现实生活中，我们可能遇到不能够严格线性可分的数据集，但是当去掉一些点之后，这个数据集便是线性可分的。对于这种数据集，我们可以使用线性支持向量机。

回忆到问题（3）中，约束条件 $y_i(w\cdot x_i+b)\ge 1,i=1,2,...,N$ 意味着所有数据的函数间隔最少为1，这确保了线性可分。

如果线性不可分，则意味着对于某些数据，约束条件不满足。我们引入松弛变量 ${\xi }_i\ge 0,i=1,2,...,N$，将约束条件放松为 $y_i(w\cdot x_i+b)\ge 1-{\xi }_i,i=1,2,...,N$；为了使得约束条件不至于没有任何约束作用，我们需要取尽可能紧凑的松弛变量，也就是让松弛变量尽可能小，我们可以在目标函数上加入松弛变量的惩罚项，也就是 $\underset{w,b}{\max }\frac{1}{2}||w|{|}^2+C{\sum }_{i=1}^N{\xi }_i$，其中，$C\ge 0$。

因此，线性支持向量机的问题可以表述为
$$\begin{array}{lll}& \underset{w,b,\xi }{\min }& \frac{1}{2}||w|{|}^2+C{\sum }_{i=1}^N{\xi }_i(4)\\ & s.t.& y_i(w\cdot x_i+b)\ge 1-{\xi }_i,i=1,2,...,N\\ & & {\xi }_i\ge 0,i=1,2,...,N\end{array}$$

同样的，我们用拉格朗日方法，将原始问题转化为对偶问题进行求解。此时，拉格朗日函数为
$$L(w,b,\xi ,\alpha ,\mu )=\frac{1}{2}||w|{|}^2+C\sum _{i=1}^N{\xi }_i-\sum _{i=1}^N{\alpha }_i{y}_i(w\cdot x_i+b)+\sum _{i=1}^N{\alpha }_i(1-{\xi }_i)-\sum _{i=1}^N{\mu }_i{\xi }_i$$

其中，${\alpha }_i\ge 0,{\mu }_i\ge 0,i=1,2,...,N$。

这时，原始问题为
$$\underset{w,b,\xi }{\min }\underset{\alpha ,\mu }{\max }L(w,b,\xi ,\alpha ,\mu )$$

对偶问题为
$$\underset{\alpha ,\mu }{\max }\underset{w,b,\xi }{\min }L(w,b,\xi ,\alpha ,\mu )$$

类似的，这里的对偶问题和原始问题等价。为了求得对偶问题的解，我们有
$$\frac{\partial L(w,b,\xi ,\alpha ,\mu )}{\partial w}=w-\sum _{i=1}^N{\alpha }_i{y}_i{x}_i=0$$

$$\frac{\partial L(w,b,\xi ,\alpha ,\mu )}{\partial b}=-\sum _{i=1}^N{\alpha }_i{y}_i=0$$

$$\frac{\partial L(w,b,\xi ,\alpha ,\mu )}{\partial {\xi }_i}=C-{\alpha }_i-{\mu }_i=0,i=1,2,...,N$$

• 通过第一个式子，我们有 $w={\sum }_{i=1}^N{\alpha }_i{y}_i{x}_i$
• 通过第二个式子，我们有 ${\sum }_{i=1}^N{\alpha }_i{y}_i=0$
• 通过第三个式子，我们有 ${\alpha }_i=C-{\mu }_i,i=1,2,...,N$

将上面的结果，代入拉格朗日函数 $L(w,b,\xi ,\alpha ,\mu )$，可以得到
$$L(\alpha ,\mu )=-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i\cdot x_j+\sum _{i=1}^N{\alpha }_i$$

约束条件有 ${\sum }_{i=1}^N{\alpha }_i{y}_i=0$ 和 ${\alpha }_i=C-{\mu }_i,i=1,2,...,N$。考虑到目标函数 $L(\alpha ,\mu )$ 中实际上并没有 ${\mu }_i$，所以我们可以消去 ${\mu }_i$，将等式 ${\alpha }_i=C-{\mu }_i$ 变成 $0\le {\alpha }_i\le C$。

因此，我们有如下最优化问题
$$\begin{array}{lll}& \underset{\alpha }{\max }& L(\alpha )=-\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i\cdot x_j+{\sum }_{i=1}^N{\alpha }_i\\ & s.t.& {\sum }_{i=1}^N{\alpha }_i{y}_i=0\\ & & 0\le {\alpha }_i\le C,i=1,2,...,N\end{array}$$

类似的，通过库恩塔克条件，我们有最优解 $(w^{\ast },b^{\ast })$ 需要满足 $$w^{\ast }=\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i{x}_i$$ $$b^{\ast }=y_j-\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i{x}_i\cdot x_j$$
其中，$j$ 满足 $0<{\alpha }_j^{\ast }\le C$。

3. 非线性支持向量机

对于更加一般的非线性可分数据集，我们可以采用核函数方法。

这种方法的起因来自于对上述两种方法的观察得来的。

• 线性可分支持向量机，求最优 ${\alpha }^{\ast }$ 的问题
  $$\begin{array}{lll}& \underset{\alpha }{\max }& L(\alpha )=-\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i\cdot x_j+{\sum }_{i=1}^N{\alpha }_i\\ & s.t.& {\sum }_{i=1}^N{\alpha }_i{y}_i=0\\ & & {\alpha }_i\ge 0,i=1,2,...,N\end{array}$$
• 线性支持向量机，求最优 ${\alpha }^{\ast }$ 的问题
  $$\begin{array}{lll}& \underset{\alpha }{\max }& L(\alpha )=-\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i\cdot x_j+{\sum }_{i=1}^N{\alpha }_i\\ & s.t.& {\sum }_{i=1}^N{\alpha }_i{y}_i=0\\ & & 0\le {\alpha }_i\le C,i=1,2,...,N\end{array}$$

观察上述问题，我们发现，对于线性可分或者接近线性可分的数据集，我们关心的往往不是具体的特征 $x_i$，而是特征的内积 $x_i\cdot x_j$。

当我们能够将一个线性不可分的数据，通过变换 $\varphi$ 将特征投射到另一个空间上去，从而让这些数据可分。在那个空间上，我们关心的依然只是内积 $\varphi (x_i)\cdot \varphi (x_j)$。

举一个例子。在图1中，有两类数据，标记为1的数据基本包围标记为-1的数据。可以想象，当我们把数据特征 $x=(x^{(1)},x^{(2)})$ 映射为 $\varphi (x)=((x^{(1)}{)}^2,(x^{(2)}{)}^2)$，外面的一圈圆点数据会被映射到一条直线上去，而里面的×数据则被映射到该条直线的下方，如图2所示。


经过这样的映射变换之后，我们就可以在新的特征空间中按照现行可分的数据集进行处理。注意到在求解过程中，我们仅仅关心特征的内积 $\varphi (x_1)\cdot \varphi (x_2)$。

因此，我们可以求新的特征空间中的超平面。具体问题为
$$\begin{array}{lll}& \underset{\alpha }{\max }& L(\alpha )=-\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j\varphi (x_i)\cdot \varphi (x_j)+{\sum }_{i=1}^N{\alpha }_i\\ & s.t.& {\sum }_{i=1}^N{\alpha }_i{y}_i=0\\ & & {\alpha }_i\ge 0,i=1,2,...,N\end{array}$$

这样求得的 $(w^{\ast },b^{\ast })$ 等于
$$w^{\ast }=\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i\varphi (x_i)$$ $$b^{\ast }=y_j-\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i\varphi (x_i)\cdot \varphi (x_j)$$
其中，$j$ 满足 ${\alpha }_j^{\ast }\ge 0$。

要求的超平面为
$$\begin{array}{lll}f(x)& =& w^{\ast }\cdot \varphi (x)+b^{\ast }\\ & =& {\sum }_{i=1}^N{\alpha }_i^{\ast }{y}_i\varphi (x_i)\cdot \varphi (x)+y_j-{\sum }_{i=1}^N{\alpha }_i^{\ast }{y}_i\varphi (x_i)\cdot \varphi (x_j)\end{array}$$

显而易见，上面的超平面表达式中依然只与内积有关。我们将这种特征内积定义为核函数 $K(x_i,x_j)$，即
$$K(x_i,x_j)=\varphi (x_i)\cdot \varphi (x_j)$$

上面那个例子中，$\varphi (x)=((x^{(1)}{)}^2,(x^{(2)}{)}^2)$，这里，对应的核函数 $K(x_i,x_j)=(x_1^{(1)}{x}_2^{(1)}{)}^2+(x_1^{(2)}{x}_2^{(2)}{)}^2$，作用就是将环形分布的数据转换为线性分布。

实际上，我们并不关心具体的特征函数 $\varphi (\cdot )$ 是什么，甚至于 $\varphi (\cdot )$ 与核函数 $K(\cdot ,\cdot )$ 也没有一一对应关系。上面的例子仅仅是说，这样的核函数，你可以从这样的特征函数构造，然后可以这样理解。

实际上，我们通常就是直接应用而已~

通常，我们应用的核函数为多项式核函数和高斯核函数。关于如何通过特征映射构造出多项式核函数和高斯核函数，可以参考
机器学习有很多关于核函数的说法，核函数的定义和作用是什么？ - 优达学城（Udacity）的回答 - 知乎

求解 ${\alpha }^{\ast }$ 的 SMO 算法，后面有时间再详细介绍。