1、最优线性分类器

对于下图的二分类任务，我们想要得到一个分类平面将其分开：

显然图中的1、2、3、4、5号平面均能达成这个目的，这五个平面我们可以用下式来表示

对于任意的样本点 (xi,yi)$(x_i,y_i)$ 均满足

记模型为：

则当新的样本特征 x′${\mathit{x}}^{\prime }$ 到来时只需代入式(3)，观察输出 f(x′)$f({\mathit{x}}^{\prime })$ 的正负即可判断。

五个平面的差别就在于 w$\mathit{w}$ 和 b$b$ 不同。图中1、2、4、5号平面虽然完成了分类任务，但是其抗扰动性不佳，在这些平面附近的样本点容易被错分类，相对来说3号平面因为距离两类样本点都足够“远”，因此其抗扰动性比较好，这样的平面我们称为最优线性分类器，支持向量机(SVM)就是要寻找这样的平面，为此要引入间隔的概念。

2、函数间隔和几何间隔

2.1 函数间隔

对于每一个样本点，我们可以定义这个样本点到超平面间隔，称为样本点的函数间隔：

那么超平面的函数间隔可以从下式得到：

我们的目标就是要找到一组 w$\mathit{w}$ 和 b$b$ 使得 γ函${\gamma }_{函}$ 最大，形式化表示如下：

仔细分析式(6)我们可以发现，当 w$\mathit{w}$ 和 b$b$ 成倍数增长时，函数间隔会不断地增大，此时找不到目标函数的最优解，而此时超平面并没有改变（ 2wTx+2b=0$2{\mathit{w}}^T\mathit{x}+2b=0$ 与式(1)并没有区别 ），所以函数间隔还不足以帮助我们寻找最优 w$\mathit{w}$ 和 b$b$ ，故需要进一步引入几何间隔

2.2 几何间隔

如下图所示：

图中 x$\mathit{x}$ 表示样本点，x0${\mathit{x}}_{\mathbf{0}}$ 是 x$\mathit{x}$ 垂直投影到超平面上对应的点 ，w$\mathit{w}$ 是式(1)中的权重向量，该向量是超平面的法向量（详情见 2.4* 节介绍），γ$\gamma$ 表示样本点 x$\mathit{x}$ 到超平面的几何间隔

容易得到以下推导过程：

即有

所以

其中式(7)到式(8)这一步到转化，前一半无需赘述是很直观的，后一半主要依据向量内积与二范数的关系：

样本点 x$\mathit{x}$ 可以分布在超平面两边，因此式(9)得到的集合间隔是带有方向的，我们考虑把方向的影响去除，则有

2.3 另一个角度来看几何间隔

我们能够比较直观感受的是二维空间和三维空间，不妨就从这两个维度开始总结规律以推广到高维空间。

• 二维空间——直线
  初等数学中的一般表达式：Ax+By+C=0$\mathrm{A}x+\mathrm{B}y+\mathrm{C}=0$
  转化为本文统一的表达式：w1x1+w2x2+b=0$w_1{x}_1+w_2{x}_2+b=0$
  其中 w=(w1,w2)T,  x=(x1,x2)T$\mathit{w}=(w_1,w_2{)}^T,\mathit{x}=(x_1,x_2{)}^T$
  二维空间中某一点 (x0,y0)$(x_0,y_0)$ 到该直线的距离可以表示为：
  

  d=|Ax0+By0+C|A2+B2‾‾‾‾‾‾‾‾√=|w1x1+w2x2+b|w21+w22‾‾‾‾‾‾‾‾√=|wTx+b|||w||(12)(13)(14)$$\begin{array}{}\text{(12)}& d& =\frac{|\mathrm{A}{x}_0+\mathrm{B}{y}_0+\mathrm{C}|}{\sqrt{{\mathrm{A}}^2+{\mathrm{B}}^2}}\text{(13)}& & =\frac{|w_1{x}_1+w_2{x}_2+b|}{\sqrt{w_1^2+w_2^2}}\text{(14)}& & =\frac{|{\mathit{w}}^T\mathit{x}+b|}{||\mathit{w}||}\end{array}$$

• 三维空间——平面
  初等数学中的一般表达式：Ax+By+Cz+D=0$\mathrm{A}x+\mathrm{B}y+\mathrm{C}z+\mathrm{D}=0$
  转化为本文统一的表达式：w1x1+w2x2+w3x3+b=0$w_1{x}_1+w_2{x}_2+w_3{x}_3+b=0$
  其中 w=(w1,w2,w3)T,  x=(x1,x2,x3)T$\mathit{w}=(w_1,w_2,w_3{)}^T,\mathit{x}=(x_1,x_2,x_3{)}^T$
  三维空间中某一点 (x0,y0,z0)$(x_0,y_0,z_0)$ 到该平面的距离可以表示为：
  

  d=|Ax0+By0+Cz0+D|A2+B2+C2‾‾‾‾‾‾‾‾‾‾‾‾‾√=|w1x1+w2x2+w3x3+b|w21+w22+w23‾‾‾‾‾‾‾‾‾‾‾‾‾√=|wTx+b|||w||(15)(16)(17)$$\begin{array}{}\text{(15)}& d& =\frac{|\mathrm{A}{x}_0+\mathrm{B}{y}_0+\mathrm{C}{z}_0+\mathrm{D}|}{\sqrt{{\mathrm{A}}^2+{\mathrm{B}}^2+{\mathrm{C}}^2}}\text{(16)}& & =\frac{|w_1{x}_1+w_2{x}_2+w_3{x}_3+b|}{\sqrt{w_1^2+w_2^2+w_3^2}}\text{(17)}& & =\frac{|{\mathit{w}}^T\mathit{x}+b|}{||\mathit{w}||}\end{array}$$

式(12)(15)是初等数学中的简单知识，式(13)(16)是前一步的简单替代，式(14)(17)是统一的向量表示，根据二维和三维空间的这一结论，我们推广到任意维，n$n$ 维空间里的实例 x$\mathit{x}$ 到该空间超平面的距离可以表示为：

与式(11)相同。

2.4* 为什么权重向量是超平面的法向量

为直观感受，我们假设式(1)表示的是二维空间上的超平面，此时超平面是一条直线，这条直线上有两个点 x1${\mathit{x}}_{\mathbf{1}}$ 和 x2${\mathit{x}}_{\mathbf{2}}$，那么 x1−x2${\mathit{x}}_{\mathbf{1}}-{\mathit{x}}_{\mathbf{2}}$ 表示的向量的方向也是沿着该直线方向的。

将 x1${\mathit{x}}_{\mathbf{1}}$ 和 x2${\mathit{x}}_{\mathbf{2}}$ 分别带入式(1)，会得到：

将以上两式整合，易得

说明 wT${\mathit{w}}^T$ 与 x1−x2${\mathit{x}}_{\mathbf{1}}-{\mathit{x}}_{\mathbf{2}}$ 垂直，也就是说 wT${\mathit{w}}^T$ 是直线的法向量，那么其转置（列向量与行向量的区别而已）自然也是直线的法向量。简单的直线解析集合基础即可得证上述结论，从二维推广到任意维并不会改变这一结论。

3、形式化表示优化目标

式(11)和(18)所得到的几何间隔是超平面某一侧样本点到超平面的距离，因此两类样本点之间的最大间隔这一距离的两倍，此时我们找到了优化目标：

我们令目标函数和约束条件同时缩小 γ函${\gamma }_{函}$ 倍，则此优化问题的最优解并未发生改变，记 w∗=wγ函，b∗=bγ函${\mathit{w}}^{\ast }=\frac{\mathit{w}}{{\gamma }_{函}}，b^{\ast }=\frac{b}{{\gamma }_{函}}$ 此时我们可以得到：

由2.1节分析可知当 w$\mathit{w}$ 和 b$b$ 成比例放缩时，平面并未发生改变，所以(19)和(20)是等价的。
进一步，式(20)可以等价于下式

4、拉格朗日乘子法和对偶问题

4.1 从条件极值谈起

回顾高等数学中多元函数的条件极值求解问题：求 f(x,y)$f(x,y)$ 在不等式 g(x,y)≤0$g(x,y)\le 0$ 和 h(x,y)≤0$h(x,y)\le 0$ 约束下的极值，我们采用的方法是构造拉格朗日函数，L(x,y,α,β)=f(x,y)+αg(x,y)+βh(x,y)$L(x,y,\alpha ,\beta )=f(x,y)+\alpha g(x,y)+\beta h(x,y)$ 其中 α≥0,β≥0$\alpha \ge 0,\beta \ge 0$，然后分别求 L(x,y,α,β)$L(x,y,\alpha ,\beta )$ 对 x$x$ 和 y$y$ 的偏导，令其为0，满足这一条件的 x′,y′$x^{\prime },y^{\prime }$ 对应的 f(x′,y′)$f(x^{\prime },y^{\prime })$ 即为所求。

4.2 凸优化问题标准形

将以上做法推广到既有等式约束又有不等式约束的情形：

• 原问题
  
  minx s.t. f(x)hi(x)=0   (i=1,2,⋯,m)gj(x)≤0   (j=1,2,⋯,n)(22)$$\begin{array}{rl}\underset{\mathit{x}}{min}& f(\mathit{x})\\ \mathrm{s}.\mathrm{t}.& h_i(\mathit{x})=0(i=1,2,\cdots ,m)\\ \text{(22)}& & g_j(\mathit{x})\le 0(j=1,2,\cdots ,n)\end{array}$$

引入拉格朗日乘子（任意一个拉格朗日乘子均非负） λ=(λ1,λ2,⋯,λm)T$\mathit{\lambda }=({\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_m{)}^T$ 和 μ=(μ1,μ2,⋯,μn)T$\mathit{\mu }=({\mu }_1,{\mu }_2,\cdots ,{\mu }_n{)}^T$，构造拉格朗日函数：

• 拉格朗日函数
  
  L(x,λ,μ)=f(x)+∑i=1mλihi(x)+∑j=1nμjgj(x)(23)$$\begin{array}{}\text{(23)}& L(\mathit{x},\mathit{\lambda },\mathit{\mu })=f(\mathit{x})+\sum _{i=1}^m{\lambda }_i{h}_i(\mathit{x})+\sum _{j=1}^n{\mu }_j{g}_j(\mathit{x})\end{array}$$

由不等式约束 gj(x)≤0   (j=1,2,⋯,n)$g_j(\mathit{x})\le 0(j=1,2,\cdots ,n)$ 可以引入KKT条件：

• KKT条件
  
  ⎧⎩⎨⎪⎪gj(x)≤0μj≥0μjgj(x)=0(24)$$\begin{array}{}\text{(24)}& \{\begin{array}{l}{g}_j(x)\le 0\\ {\mu }_j\ge 0\\ {\mu }_j{g}_j(\mathit{x})=0\end{array}\end{array}$$

4.3 SVM的对偶问题

依据4.2节的内容，我们对式(21)引入拉格朗日乘子 α=(α1,α2,⋯,αn)$\mathit{\alpha }=({\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_n)$，可以得到：

令

仔细分析式(25)(26)，我们可以得出如下结论：

原始约束满足的情况下，1−yi(wTxi+b)≤0$1-y_i({\mathit{w}}^T{\mathit{x}}_i+b)\le 0$，拉格朗日乘子非负，所以 ∑ni=1αi[1−yi(wTxi+b)]$\sum _{i=1}^n{\alpha }_i[1-y_i({\mathit{w}}^T{x}_i+b)]$ 非正，因此式(25)最大值便是式(27)上式所示；反之，原始约束不满足的情况下，只需置对应项的拉格朗日乘子无限大，则无法找到 maxαi≥0L(w,b,α)$\underset{{\alpha }_i\ge 0}{max}L(\mathit{w},b,\mathit{\alpha })$，所以，我们可以把式(21)这一原始问题描述为：

式(29)的对偶问题是：

记式(28)和(29)的最优解分别为 p∗$p^{\ast }$ 和 d∗$d^{\ast }$，易证式(28)和(29)中 blue≤L(w,b,α)≤red$blue\le L(\mathit{w},b,\mathit{\alpha })\le red$，那么显然 d∗≤p∗$d^{\ast }\le p^{\ast }$ ，在强对偶性得以满足的条件下，可以得到 d∗=p∗$d^{\ast }=p^{\ast }$ 式(24)提到的KKT条件就是强对偶的一种，所以原始问题可以通过满足KKT条件转化为对偶问题，求解对偶问题所得的结果就是原问题的解。

4.4 对偶问题的求解

对偶问题的求解可以分为两步，首先对式(29)中的 blue$blue$ 部分求解，求 L(w,b,α)$L(\mathit{w},b,\mathit{\alpha })$ 对 w$\mathit{w}$ 和 b$b$ 的偏导：

分别令式(30)(31)的值为0，则可以得到 w=∑ni=1αiyixi$\mathit{w}=\sum _{i=1}^n{\alpha }_i{y}_i{x}_i$，∑ni=1αiyi=0$\sum _{i=1}^n{\alpha }_i{y}_i=0$，将其代入式(25)得到：

可以发现此时式(32)表示的拉格朗日函数中的变量只有 αi${\alpha }_i$ ，那么进一步把 αi${\alpha }_i$ 求解出来便可以确定 w$\mathit{w}$ 和 b$b$，所以接下来便是对偶问题求解的第二步求解，经过第一步，问题式(29)已经转变成为：

式(33)的求解可以通过SMO算法进行求解（笔者目前也还没有完全透彻这一算法，后续学习后将写出来与博友交流），最终得到结果：

至此，已经求出了式(1)的两个重要参数。

5、SVM中一些其他问题

5.1 为什么只有支持向量影响解的结构？

我们一般把图中红色方框框出来的样本点称为支持向量，从图示的角度很容易理解，这些样本点的位置影响了整个“管道“的位置，那么“管道“正中间的分类平面的位置也会随着变动，这是从直观的角度来解释为什么只有支持向量会影响模型，其实我们也可以从理论角度来加以解释：

将式(21)中的约束条件转换成为式(22)中的标准形式，参照式(24)KKT条件的第三条，必有下式成立：

图中红框框出的样本点满足 1−yi(wTxi+b)=0$1-y_i({\mathit{w}}^T{x}_i+b)=0$ 即只有支持向量对应的拉格朗日乘子才可能不为0，而4.4节已经提到我们是通过SMO算法求解关于 α$\alpha$ 的优化问题，最终求得模型重要参数 w$\mathit{w}$ 和 b$b$ 的。

5.2 非线性问题怎么办？

前述内容都是关于线性可分的分类问题，那么对于线性不可分的呢？核方法是一个非常不错的选择，而SVM的强大一定程度上就是由于引入核方法将线性不可分问题从低维空间映射到高维空间变成线性可分，而且，核方法并非SVM专属方法，这是一套非常有效的技巧，以后会专门写一下这一块！

【参考文献】

周志华.机器学习[M].北京:清华大学出版社,2016.
李航.统计学习方法[M].北京:清华大学出版社,2012.
July.支持向量机通俗导论（理解SVM的三层境界）