如何理解SVM算法

1. SVM算法概述

SVM算法（support vector machine，支持向量机），是一种二分类算法，可以分为线性SVM算法和非线性SVM算法，线性SVM指的是通过高维空间的超平面做分类，非线性SVM指通过高维空间中的曲面做分类。关于线性SVM又可以分为线性可分SVM算法和线性不可分SVM算法，对于线性可分的样本，采用的分割方法为间隔最大化，对于线性不可分的样本，如果使用线性分类方法，那么无法避免要产生错误的分类，这时候需要在容许一定误差的情况下做到间隔最大化。非线性SVM算法其实是通过低维空间向高维空间的映射来完成的，映射的过程需要用到核函数。

2. 线性可分SVM算法

给定线性可分训练数据集，通过间隔最大化来寻找分离超平面，如下图所示

分类函数为

$f(x) = sign(\pmb \omega^* \cdot \pmb x + b) \tag{2.1}$f(x)=sign(ωωω∗⋅xxx+b)(2.1)
待判别的类型取值为{-1, 1}
间隔距离指的是正样本到分类超平面的距离与负样本到超平面的距离之和，距离如下
$d = \frac{2}{|\pmb\omega|}$d=∣ωωω∣2​
因此对于解决线性可分SVM算法，等价于最大化d，既有下式
$\max_{\omega, b} \frac{2}{|\pmb\omega|} \tag{2.2}$ω,bmax​∣ωωω∣2​(2.2)
$s.t. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ y_i(\pmb \omega * x_i + b) \ge 1 \tag{2.3}$s.t.                   yi​(ωωω∗xi​+b)≥1(2.3)
上式通过等价可以转换为
$\min_{\omega, b}\frac{1}{2}||\pmb\omega|| \tag{2.4}$ω,bmin​21​∣∣ωωω∣∣(2.4)
$s.t. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ y_i(\pmb \omega * x_i + b) \ge 1 \tag{2.5}$s.t.                   yi​(ωωω∗xi​+b)≥1(2.5)
通过拉格朗日法，可以将上面最优化式子转化为
$\max_{\alpha}\min_{\omega, b}L(\pmb\omega, b, \pmb\alpha) = \frac{1}{2}||\pmb\omega|| - \sum_{i=1}^N{\alpha_iy_i(\pmb\omega\cdot x_i + b)} + \sum_{i=1}^{N}\alpha_i \tag{2.6}$αmax​ω,bmin​L(ωωω,b,ααα)=21​∣∣ωωω∣∣−i=1∑N​αi​yi​(ωωω⋅xi​+b)+i=1∑N​αi​(2.6)
上式表示$L(\pmb\omega, b, \pmb\alpha)$L(ωωω,b,ααα)先对$\pmb\omega, b$ωωω,b求极小值，再对$\pmb\alpha$ααα求最大值,其中要求$\alpha_i \ge 0$αi​≥0
$L(\pmb\omega, b, \pmb\alpha)$L(ωωω,b,ααα)对$\pmb\omega, b$ωωω,b求梯度得
$\nabla_\omega L(\pmb\omega, b, \pmb\alpha) = \pmb \omega - \sum_{i=1}^{N}\alpha_iy_ix_i \tag{2.7}$∇ω​L(ωωω,b,ααα)=ωωω−i=1∑N​αi​yi​xi​(2.7)
$\nabla_b L(\pmb\omega, b, \pmb\alpha) = - \sum_{i=1}^{N}\alpha_iy_i \tag{2.8}$∇b​L(ωωω,b,ααα)=−i=1∑N​αi​yi​(2.8)
令二者均为0得到$\pmb\omega$ωωω关于$\alpha$α的表达式，并将该表达式带入到拉格朗日最优化式子，可以得到下面这个等价的式子
$L(\pmb\omega, b, \pmb\alpha) = -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i \cdot x_j) + \sum_{i=1}^{N}\alpha_i$L(ωωω,b,ααα)=−21​i=1∑N​j=1∑N​αi​αj​yi​yj​(xi​⋅xj​)+i=1∑N​αi​
该式对$\pmb\alpha$ααα求极大值，得到如下

$\min_{\alpha} \ \ \ \ \ \ \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i \cdot x_j) - \sum_{i=1}^{N}\alpha_i \tag{2.9}$αmin​      21​i=1∑N​j=1∑N​αi​αj​yi​yj​(xi​⋅xj​)−i=1∑N​αi​(2.9)
$s.t.\ \ \ \ \ \ \ \ \ \sum_{i=1}^{N}\alpha_iy_i = 0 \tag{2.10}$s.t.         i=1∑N​αi​yi​=0(2.10)
其中$\alpha_i \ge 0$αi​≥0
因此SVM算法的问题就将原式间隔最大化的问题转化为了式（2.7）和（2.8），关于$\alpha_i$αi​的具体求法，请在我的另一篇关于介绍SMO算法的文章中做介绍，现在需要关注的是，若已知$\alpha_i$αi​，如何求$\pmb \omega, b$ωωω,b，
由公式（2.8）可知
$\pmb \omega = \sum_{i=1}^{N}\alpha_iy_ix_i$ωωω=i=1∑N​αi​yi​xi​
由于（2.3）是算法满足的先决条件，并且总有一些点是要在分类的临界面上，也就是说，总有点$(x_i, y_i)$(xi​,yi​)满足
$y_i = \pmb \omega * x_i + b$yi​=ωωω∗xi​+b
那么，对于位于临界面上的点$(x_i, y_i)$(xi​,yi​)
$b = y_i - \pmb \omega * x_i$b=yi​−ωωω∗xi​

3. 线性不可分SVM算法

对于线性不可分的类型，通过引入松弛变量$\xi$ξ来解决，约束条件变成下面式子
$y_i(\pmb \omega * x_i + b) \ge 1 - \xi_i \tag{3.1}$yi​(ωωω∗xi​+b)≥1−ξi​(3.1)
其中，$\xi_i \ge 0$ξi​≥0
目标函数变成如下
$\max_{\omega, b}\frac{1}{2}||\omega|| + C\sum_{i=1}^{N}\xi_i \tag{3.2}$ω,bmax​21​∣∣ω∣∣+Ci=1∑N​ξi​(3.2)
$s.t. \ \ \ \ \ \ \ \ \ \ \ y_i(\pmb \omega * x_i + b) \ge 1 - \xi_i \tag{3.3}$s.t.           yi​(ωωω∗xi​+b)≥1−ξi​(3.3)
按照线性可分的方式推导下去，可以得到该问题的对偶问题为
$\min_\alpha \ \ \ \ \ \ \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i \cdot x_j) - \sum_{i=1}^{N}\alpha_i \tag{3.4}$αmin​      21​i=1∑N​j=1∑N​αi​αj​yi​yj​(xi​⋅xj​)−i=1∑N​αi​(3.4)
$s.t.\ \ \ \ \ \ \ \ \ \sum_{i=1}^{N}\alpha_iy_i = 0 \tag{3.5}$s.t.         i=1∑N​αi​yi​=0(3.5)
其中要求$0 \le \alpha_i \le C$0≤αi​≤C，解决方法同线性可分SVM算法

4. 非线性SVM算法

对于非线性SVM算法，是通过核函数来解决的，一般表示核函数为
$K(x_1, x_2)$K(x1​,x2​)
引入核函数之后的对偶问题表示如下
$\min_\alpha \ \ \ \ \ \ \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jK(x_i \cdot x_j) - \sum_{i=1}^{N}\alpha_i \tag{4.1}$αmin​      21​i=1∑N​j=1∑N​αi​αj​yi​yj​K(xi​⋅xj​)−i=1∑N​αi​(4.1)
$s.t.\ \ \ \ \ \ \ \ \ \sum_{i=1}^{N}\alpha_iy_i = 0 \tag{4.2}$s.t.         i=1∑N​αi​yi​=0(4.2)
引入核函数之后的分割面表示为
$f(x) = sign(\sum_{i=1}^{N}\hat \alpha y_iK(x_i, x) + \hat b)$f(x)=sign(i=1∑N​α^yi​K(xi​,x)+b^)
最常用的核函数有以下四种，分别是

1. 高斯核函数
   $K(x_1, x_2) = \exp(-\frac{||x_1 - x_2||^2}{2\sigma^2})$K(x1​,x2​)=exp(−2σ2∣∣x1​−x2​∣∣2​)
2. 多项式核函数
   $K(x_1, x_2) = (x_1 \cdot x_2 + 1)^p, p \in \{1,2,3,...\}$K(x1​,x2​)=(x1​⋅x2​+1)p,p∈{1,2,3,...}

这些核函数在sklearn库中都有实现，可以直接调用。