Support Vector Machine

终于，我们来到了SVM。SVM是我个人感觉机器学习中最优美的算法，这次我们要来非常细致地介绍。SVM是一类有监督的分类算法，它的大致思想是：假设样本空间上有两类点，我们希望找到一个划分超平面，将这两类样本分开，而划分超平面应该选择泛化能力最好的，也就是能使得两类样本中距离它最近的样本点距离最大。

Hard Margin&Dual Problem

Hard Margin

如图所示，中间那条加粗的超平面就是我们所求的最优划分超平面。我们知道平面的方程可以用线性方程：$w^{T}x+b=0$来表示，$w=(w_1,w_2,\dots ,w_n)$表示的是平面的法矢量。现在，我们假设样本空间$D=\{(x_i,y_i)|i\in Z^{+}\}$中只有两个类别的样本，类别标记分别为$y_i=1$或$y_i=-1$。那么对于$(x_i,y_i),y_i=1$，超平面得到的结果$w^T{x}_i+b\ge 1$；反之，$w^T{x}_i+b\le -1$。因此我们有：
$$\{\begin{array}{l}{w}^T{x}_i+b\ge 1,y_i=1\\ w^T{x}_i+b\le -1,y_i=-1\end{array}$$
某一个样本点$(x_i,y_i)$到划分超平面的距离公式为：
$$\gamma =\frac{|w^T{x}_i+b|}{||w||}$$
考虑两类样本点中距离划分超平面最近的样本，这类样本恰好能够使得上式中的等号成立，如图：

我们称这类距离划分超平面最近的样本点为“支持向量”，称$\gamma =\frac{2}{||w||}$为“间隔”。

之前我们说到了，我们希望这个间隔能够最大化来使得模型泛化能力最强，因此我们的任务就是：
$$\begin{gathered} maximiz{e}_w\frac{2}{||w||} \\ s.t.y_i(w^T{x}_i+b)\ge 1 \end{gathered}$$
这个任务等价于：
$$\begin{gathered} minimiz{e}_w\frac{1}{2}||w|{|}^2 \\ s.t1-y_i(w^T{x}_i+b)\le 0 \end{gathered}$$
这就变成了一个非常典型的凸优化问题。

Dual Problem

对于求条件极值，我们自然要先写出他的Lagrange乘子式：
$$L(\alpha ,w,b)=\frac{1}{2}||w|{|}^2-\sum _{i=1}^n{\alpha }_i(1-y_i(w^T{x}_i+b))$$
我们的任务是$minimizeL(\alpha ,w,b)$。
下面考虑它的dual problem：
$$mi{n}_{w,b}ma{x}_{\alpha }L(\alpha ,w,b)$$
接下来求出$L$对$w,b$的偏导：
$$\begin{gathered} {\nabla }_{w}L=w-\sum _{i=1}^n{\alpha }_i{y}_i{x}_i=0w=\sum _{i=1}^n{\alpha }_i{y}_i{x}_i \\ {\nabla }_{b}L=-\sum _{i=1}^n{\alpha }_i{y}_i=0\sum _{i=1}^n{\alpha }_i{y}_i=0 \end{gathered}$$
代入$L(\alpha ,w,b)$我们可以得到一个只与$\alpha$相关的函数：
$$g(\alpha )=\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$$
因此我们可以把问题转化为：
$$\begin{gathered} ma{x}_{\alpha }\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j \\ s.t.{\alpha }_i\ge 0 \\ \sum _{i=1}^n{\alpha }_i{y}_i=0 \end{gathered}$$
如果满足的是strong dual，那么应该满足的KKT条件是：
$$\{\begin{array}{l}1-y_i(w^T{x}_i+b)\le 0primalconstraint\\ {\alpha }_i\ge 0dualconstraint\\ {\alpha }_i(1-y_i(w^T{x}_i+b))=0complementaryslackness\end{array}$$
(突然发现学过凸优化理论就是好……)

Soft Margin

前面我们谈到的都是理想状况，也就是能够找到一个划分平面把两类样本点完全分开。但是很多时候，我们会遇到一些特殊的数据导致无法用一个平面实现完全准确的分类，因此提出了Soft Margin软间隔，即允许有分类错误的情况发生。如图所示，红色点样本点就是被分类错误的点。

那么我们就在原来的目标函数中加入一个分类错误的损失${\xi }_i$，在最小化$\frac{||w|{|}^2}{2}$的同时也最小化总体分类误差，即：
$$minimize\frac{1}{2}||w|{|}^2+C\sum _{i=1}^n{\xi }_i$$
C是一个惩罚系数，C越大，代表模型对分类正确的要求越高
现在我们要考虑这个${\xi }_i$到底应该是什么。在Hard Margin当中，我们提到了如果某个样本被分类正确，那么他应该满足的条件是：
$$y_i(w^T{x}_i+b)\ge 1$$
因此，对于${\xi }_i$，我们希望的是当样本满足上述条件时，等于0；否则，等于一个正比于$y_i(w^T{x}_i+b)$与$1$之间差距的值。我们常用的损失函数有MSE、Sigmoid+Cross Entropy等等，如下图所示：

但我们会发现这些损失函数都不太符合我们的需求。因此，在SVM中，我们提出了Hinge Loss，即：
$$L_{hinge}=\{\begin{array}{l}0y_i(w^T{x}_i+b)\ge 1\\ 1-y_i(w^T{x}_i+b)y_i(w^T{x}_i+b)<1\end{array}$$

那么，${\xi }_i$也就可以用Hinge Loss来表示，与此同时，我们的约束条件也发生了一些变化：
$$\begin{gathered} minimize\frac{1}{2}||w|{|}^2+C\sum _{i=1}^{n}max(0,1-y_i(w^T{x}_i+b)) \\ s.t.y_i(w^T{x}_i+b)\ge 1-{\xi }_i \\ {\xi }_i\ge 0 \end{gathered}$$
我们看到这里的约束条件从$\ge 1$变成了$\ge 1-{\xi }_i$，也就是条件放宽了一些，因此我们也称${\xi }_i$为松弛变量(slack variable)。

同理，我们还是写出拉格朗日乘子式，然后求对偶问题，可以得到：
$$\begin{gathered} maximiz{e}_{\alpha }\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j \\ s.t.0\le {\alpha }_i\le C \\ \sum _{i=1}^n{\alpha }_i{y}_i=0 \end{gathered}$$
需要满足的KKT条件为：
$$\{\begin{array}{l}1-{\xi }_i-y_i(w^T{x}_i+b)\le 0\\ {\alpha }_i\ge 0\\ {\alpha }_i(1-{\xi }_i-y_i(w^T{x}_i+b))=0\\ {\xi }_i\ge 0\\ {\beta }_i{\xi }_i=0(\beta 是另一个拉格朗日乘子)\end{array}$$

Kernel

Intuition

再来考虑一类问题，假如有一组样本，软间隔也失效了该怎么办，话可能不太好描述，直接看图：

这种样本显然用线性的平面是不可能划分开的。但是假如我们能够把它映射到高维空间，那是不是就能线性可分了？如图：

再举一个例子，感知机中经典的异或问题，我们都知道异或问题单个感知机是无法实现的，但是如果我们将它映射到高维，如图：

这样我们就能找到一个线性的平面实现划分了。

Kernel Function

从上面的图中我们发现，只要我们找到一种映射$x->\varphi (x)$，或者说从空间$R$到空间$H$，然后就能在新的空间用线性的超平面进行划分。但是问题又来了，这种映射关系倒是很好找，例如$x=(x_1,x_2\dots ,x_n)$，$\varphi (x)=(x_1{x}_2,x_1{x}_3,\dots ,x_1{x}_n,x_2{x}_1,x_2{x}_3,\dots x_2{x}_n,\dots )$，即$\varphi (x)$表示$x$中两两特征之积，那么当我们要计算$\varphi (x)$的时候，所花费的代价是$O(n^2)$的。在机器学习或深度学习任务中，成千上万的数据量是非常正常的，这就导致了模型效率的大幅下降。

因此，我们希望找到某种函数$K(x,z)$，使得我们不需要显式地写出映射关系$\varphi (x)$，就能计算得到$\varphi (x{)}^T\varphi (z)$的结果。我们称这样的函数为核函数。下面举个例子：
$$\begin{gathered} 证明K(x,z)=(x\cdot z{)}^2是一个核函数,x,z\in R^2 \\ x=(x_1,x_2)z=(z_1,z_2) \\ (x\cdot z{)}^2=(x_1{x}_2+z_1{z}_2{)}^2=x_1^2{x}_2^2+2x_1{x}_2{z}_1{z}_2+z_1^2{z}_2^2 \\ 于是,对于\varphi (x)=(x_1^2,x_1{x}_2,x_2^2),K(x,z)=\varphi (x{)}^T\varphi (z)=(x\cdot z{)}^2 \\ 所以利用核函数K(x,z)=(x\cdot z{)}^2,我们可以将数据映射到R^3空间 \end{gathered}$$
下面是核函数的严格定义：

Sufficient&Necessary Condition

了解即可

Common Kernel Function

Linear Kernel

$$K(x,z)=x^{T}z+c$$

Polynomial Kernel

$$K(x,z)=(a{x}^{T}z+b{)}^c$$

RBF Kernel

$$K(x,z)=exp(\frac{||x-z|{|}^2}{-2{\sigma }^2})$$

Laplacian Kernel

$$K(x,z)=exp(-\frac{||x-z||}{\sigma })$$

Non-Linear SVM

上面介绍Kernel的目的就是引出下面的非线性SVM。对于线性不可分的问题，SVM中就是使用核函数技巧将原样本映射到高维空间，在高维空间寻找线性解。而我们唯一需要做的变化就是将原来目标函数中的$x_i^T{x}_j$变为$K(x_i,x_j)$，就实现了从低位到高维空间的映射，即：
$$\begin{gathered} maximiz{e}_{\alpha }\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i,x_j) \\ s.t.0\le {\alpha }_i\le C \\ \sum _{i=1}^n{\alpha }_i{y}_i=0 \end{gathered}$$
事实上，对于任意的模型，只要目标函数中出现了$x$的内积形式，我们都可以应用核技巧。

SMO Algorithm

前面我们只得到了最终要优化的函数，但是还没有讲到底怎么得到最优的$\alpha$。首先，我们引入一个定理：

这个定理告诉我们，只要求解出最优的$\alpha$，我们就可以返回去求出最优的划分平面。

接下来，我们来一步步地推导SMO算法，这是一个非常复杂的过程。SMO地思想是每次找到两个变量${\alpha }_i{\alpha }_j$，针对这两个变量构建一个凸二次规划问题。最终，当所有的$\alpha$都满足KKT条件时，我们的优化就完成了。而每次选取两个变量的标准就是，${\alpha }_i$选择样本中违反KKT条件最严重的，${\alpha }_j$根据约束条件来自动确定，下面开始推导。

Mathematical Deduction

不失一般性，我们假设选择的两个变量为${\alpha }_1,{\alpha }_2$，其他变量${\alpha }_j$看作是固定的常数，于是我们要优化的问题就可以写成：
$$\begin{gathered} minimiz{e}_{{\alpha }_1,{\alpha }_2}\frac{1}{2}{K}_{11}{\alpha }_1^2+\frac{1}{2}{K}_{22}{\alpha }_2^2+K_{12}{\alpha }_1{\alpha }_2-({\alpha }_1+{\alpha }_2)+y_1{\alpha }_1\sum _{i=3}^n{y}_i{\alpha }_i{K}_{i1}+y_2{\alpha }_2\sum _{i=3}^n{y}_i{\alpha }_i{K}_{i2} \\ s.t.{\alpha }_1{y}_1+{\alpha }_2{y}_2=-\sum _{i=3}^n{\alpha }_i{y}_i=\delta \\ 0\le {\alpha }_i\le C \end{gathered}$$
首先我们来分析约束条件${\alpha }_1{y}_1+{\alpha }_2{y}_2$，对于两个变量，我们可以用图像来表示

其实这就是一个直线方程，$y_1,y_2$有两种情况：同号和异号
因此我们要求的的是目标函数在平行于对角线的线段上的最优值，这样我们又可以转化为一个单变量的最优化问题，不妨只考虑${\alpha }_2$
假设初始可行解为${\alpha }_1^{old},{\alpha }_2^{old}$最优解为${\alpha }_1^{new},{\alpha }_2^{new}$, 假设在沿着约束方向未经修剪的${\alpha }_2$的最优解为${\alpha }_2^{new,unc}$。由于${\alpha }_2^{new}$要满足不等式约束，因此$L\le {\alpha }_2^{new}\le H$，$L,H$是${\alpha }_2^{new}$的上下界。

• 当$y_1=y_2$时
  • 下界: $L=min(0,{\alpha }_2^{old}-{\alpha }_1^{old})$
  • 上界: $H=max(C,C+{\alpha }_2^{old}-{\alpha }_1^{old})$
• 当$y_1\ne y_2$时,
  • 下界: $L=min(0,{\alpha }_2^{old}+{\alpha }_1^{old}-C)$
  • 上界: $H=max(C,{\alpha }_2^{old}+{\alpha }_1^{old})$

下面，首先求未经约束条件修剪的最优值${\alpha }_2^{new,unc}$
记$g(x)={\sum }_{i=1}^n{\alpha }_i{y}_{i}K(x_i,x)+b$
令$E_i=g(x_i)-y_i=({\sum }_{j=1}^n{\alpha }_j{y}_{j}K(x_j,x_i)+b)-y_{i}i=1,2$
那么$E_i$就表示预测值与真实值之间的误差

接下来计算阈值b和差值E

Principle of Choosing Variable

其实当我们优化完得到最后所有的${\alpha }_i$后，我们会发现只有少数的${\alpha }_i$不为$0$，而那些不为$0$的$\alpha$就是我们的支持向量！