机器学习之svm

阳光穿透心脏的1/2处 2023-02-21 12:44 20阅读 0赞

## 什么是SVM： ##

SVM被提出于1964年，是一个著名的二分类算法，在人像识别、文本分类等模式识别问题中有广泛的应用

## SVM原理： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70]  
上图坐标系中有两个类别：蓝色类别与红色类别（以下称为正例与反例），svm要做的是找出一个超平面划分两个类别（假设超平面为L）,很明显当L位于正例与反例中间时（上图黑线位置），超平面的分类效果最好，因为这个时候模型的的容错性最好。假设正例到L的最小距离为d1,反例到L的最小距离为d2，接下来我们要做的就是最大化d1与d2。我们将距离L最近的正例样本点与反例样本点称为“支持向量”，这也是“支持向量机”名字的由来。svm在分类时会将正例样本分为1， 负例样本为-1， 即y的取值为\{1, -1\}

## 推导： ##

**拉格朗日函数构造**  
假定L方程为：  
![在这里插入图片描述][20200630192202744.png]  
由距离公式可得：  
![在这里插入图片描述][20200630192223737.png]  
我们将上述距离公式做如下转换：  
![在这里插入图片描述][20200630201045520.png]  
我们令：  
![在这里插入图片描述][20200630201314724.png]  
上述过程其实可以看做是一个放缩的过程。于是上述方程变为：  
![在这里插入图片描述][20200630201948330.png]  
注意此时W和b已经变为了新的W和b,我们令上述方程为L1, 同理我们可得L2：  
![在这里插入图片描述][20200630202112255.png]  
此时我们的超平面L为：  
![在这里插入图片描述][20200630202132486.png]  
L1和L2是过支持向量并且平行于L的超平面，三条直线之间的关系类似于下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 1]  
此时d1和d2的大小就等于L1和L2到L的距离，并且对所有的正例样本和负例样本都有如下关系：  
![在这里插入图片描述][20200630203120309.png]  
两者其实可以使用一个式子来表示：  
![在这里插入图片描述][20200702213024103.png]

我们由平面之间的距离公式可得：  
![在这里插入图片描述][20200630203208383.png]  
现在呢我们需要最大化D,相当于最小化||W||, 要想最小化||W||,我们可以令它的平方最小，于是构造如下函数：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 2]  
上述拉格朗日函数满足如下条件：  
![在这里插入图片描述][20200702213918939.png]  
前两个条件应该很好理解，主要是第三个约束条件，它表示的是ai和1-yi(wxi + b) 至少有一个为0，原因如下：  
当L的解满足1 – yi(wxi+b) = 0时，ai\[1 – yi(wxi + b)\] 等于0，当L的解满足1 – yi(wxi+b) < 0, 此时由于我们的解本身就落在可行域内，1 – yi(wxi+b) <= 0这条约束条件将不起任何作用，我们令ai = 0,此时ai\[1 – yi(wxi + b)\] 等于0。

由上述的三个条件可知，ai\[1 – yi(wxi + b)\] 的最大值其实就是0，也就是说我们的函数L的解是在ai\[1 – yi(wxi + b)\]取最大值时得出的，所以有：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 3]至此我们已经构造出了我们需要的拉格朗日函数

**对偶函数**  
当原问题直接求解比较困难时，我们可以求解它的对偶问题,上述拉格朗日函数的对偶问题为：  
![在这里插入图片描述][20200702221726108.jpg]原问题与对偶问题在数学上有如下关系：原问题的解大于等于对偶问题的解。特别的，如果原问题与对偶问题是强对偶关系，那么原问题的解等于对偶问题的解。强对偶关系的条件：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 4]  
很明显，我们的函数满足上述条件，所以在这儿对偶问题与原问题的解是相等的，所以接下来呢我们对对偶问题进行求解就可以了。首先对w和b求导得：  
![在这里插入图片描述][20200703150453650.png]  
我们将上述得到的关系带入L中得：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 5]接下来呢我们要求解的函数就变为了：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 6]

## SMO算法 ##

我们的函数变为了一个关于a1, a2, …an的函数L(a1, a2, …an),接下来我们要使用smo算法对函数进行求解，smo算法过程如下：首先固定ai(i>=3), 此时函数变为了关于a1和a2的函数，我们求出a1和a2,然后固定ai(i>=5),由于a1和a2已经求出，此时函数变为了关于a3, a4的函数，求出a3, a4，以此类推直到所有的a都被求出。  
接下来以a1, a2为例，我们固定ai(i>=3):  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 7]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 8]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 9]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 10]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 11]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 12]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 13]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200630185424784.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4=,size_16,color_FFFFFF,t_70
[20200630192202744.png]: https://img-blog.csdnimg.cn/20200630192202744.png
[20200630192223737.png]: https://img-blog.csdnimg.cn/20200630192223737.png
[20200630201045520.png]: https://img-blog.csdnimg.cn/20200630201045520.png
[20200630201314724.png]: https://img-blog.csdnimg.cn/20200630201314724.png
[20200630201948330.png]: https://img-blog.csdnimg.cn/20200630201948330.png
[20200630202112255.png]: https://img-blog.csdnimg.cn/20200630202112255.png
[20200630202132486.png]: https://img-blog.csdnimg.cn/20200630202132486.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200630202355745.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4=,size_16,color_FFFFFF,t_70
[20200630203120309.png]: https://img-blog.csdnimg.cn/20200630203120309.png
[20200702213024103.png]: https://img-blog.csdnimg.cn/20200702213024103.png
[20200630203208383.png]: https://img-blog.csdnimg.cn/20200630203208383.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200702213742120.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4=,size_16,color_FFFFFF,t_70
[20200702213918939.png]: https://img-blog.csdnimg.cn/20200702213918939.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200702221445492.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4=,size_16,color_FFFFFF,t_70
[20200702221726108.jpg]: https://img-blog.csdnimg.cn/20200702221726108.jpg
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200703145238909.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4=,size_16,color_FFFFFF,t_70
[20200703150453650.png]: https://img-blog.csdnimg.cn/20200703150453650.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200703151334688.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200703152039908.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200703155725389.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200703155738332.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200704151034121.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20200704151112130.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20200704151126723.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20200704151255847.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4_size_16_color_FFFFFF_t_70 13]: https://img-blog.csdnimg.cn/20200704151318265.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dlbWluZ3NodW4=,size_16,color_FFFFFF,t_70