详解SVM支持向量机算法(三:软间隔SVM和非线性SVM)

末蓝、 2022-09-16 13:20 297阅读 0赞

**目录**

背景

线性支持向量机(软间隔SVM)

硬间隔的问题

引入松弛变量

目标函数的优化

生成拉格朗日函数

软间隔原始问题

软间隔对偶问题

求解思路：

对偶问题的求解

先求L函数对w，b，ξ的极小值

分析软间隔支持向量得出结论

总结软间隔SVM算法分析求解过程

设定惩罚系数C-构造优化问题

用SMO算法求出α\*

计算W

找到全部的支持向量，计算出b

求b均值

非线性支持向量机

升维处理线性不可分

SVM的升维

维度爆炸和计算量问题

引入核函数取代计算非线性映射函数的内积

常用的核函数

核函数解决非线性分类的效果

非线性SVM目标函数和求解过程总结

选择某个核函数及其对应的超参数

选择惩罚系数C

构造最优化问题

利用SMO算法求解出一组α\*根据α\*计算w\* 根据α\*找到全部支持向量，计算每个支持向量对应的bs\*对bs\*求均值得到最后的b\*

--------------------

# 背景 #

上一篇我们说到支持向量机分为三类：线性可分支持向量机(硬间隔SVM)、线性支持向量机(软间隔SVM)、非线性支持向量机,并且详细分析了硬间隔SVM得目标函数推导和求解，接下来继续说一下剩下得两个种类。

# 线性支持向量机(软间隔SVM) #

## 硬间隔的问题 ##

线性可分svm可通过构造超平面令硬间隔最大化，要正负例完美分开，从而求得最好的分隔超平面,实际情况的数据一半都不会太理想，总在或多或少的噪声数据，根据目标函数最优化我们无法找到一组w和b, 也就是我们就很难找到一个泛化能力很好的超平面了，即使找到了，也有可能是过拟合的。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_11_color_FFFFFF_t_70_g_se_x_16][]

## 引入松弛变量 ##

也就是说，硬间隔支持向量机要求所有的样本均被最佳超平面正确划分，要严格满足条件：![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_7_color_FFFFFF_t_70_g_se_x_16][]，而软间隔支持向量机允许某些样本点**不满足**间隔大于等于1的条件。也就是说在上边这个约束条件上加了一个松弛变量**ξi**≥0（每个数据点自己有一个ξi）约束变成：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_9_color_FFFFFF_t_70_g_se_x_16][]

这样就至少肯定有好多的w和b满足条件了 但是这相当于没有约束条件了，只要**ξi**无穷大，那么所有w和b都满足条件，**ξ**代表异常点**嵌入间隔面的深度**，我们要在能选出符合约束条件的最好的w和b的同时， **让嵌入间隔面的总深度越少越好**

## 目标函数的优化 ##

### 生成拉格朗日函数 ###

那么原来硬间隔的目标函数

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_11_color_FFFFFF_t_70_g_se_x_16 1][]

将会优化成这样：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_12_color_FFFFFF_t_70_g_se_x_16][]

其实就是在原函数中引入一个惩罚系数 C>0，并对每个样本点![5abd2073ec6341b68b40166e950540aa.png][]引入一个松弛变量（slack variables）ξ≥0。

再次根据f(x)和约束调试整理成拉格朗日函数：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_20_color_FFFFFF_t_70_g_se_x_16][]

其中 αi≥0、 μi≥0是拉格朗日乘子。

### 软间隔原始问题 ###

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_7_color_FFFFFF_t_70_g_se_x_16 1][]

### 软间隔对偶问题 ###

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_6_color_FFFFFF_t_70_g_se_x_16][]

### 求解思路： ###

先求L函数对w，b，ξ的极小值，再求其对α和μ的极大值

## 对偶问题的求解 ##

### 先求L函数对w，b，ξ的极小值 ###

对3个参数w，b，ξ分别求偏导得

![fa2f39e85e1149079990054874faf6ac.png][]

带回拉格朗日函数

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_12_color_FFFFFF_t_70_g_se_x_16 1][]

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_10_color_FFFFFF_t_70_g_se_x_16][]

整理约束条件

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_7_color_FFFFFF_t_70_g_se_x_16 2][]

发现基本式和硬间隔的一样，不过是约束条件变了。由于目标函数中并没有出现C，可将约束条件的第2，3，4项合并，消去C，得到最终的待优化函数为：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_8_color_FFFFFF_t_70_g_se_x_16][]

与之前硬间隔相比，只是多了个约束条件而已，软间隔支持向量机对对偶变量的约束是 0≤αi≤C，硬间隔支持向量机对对偶变量的约束是 0≤αi，软间隔仍然可以使用 SMO来求解

## 分析软间隔支持向量得出结论 ##

•αi=0 -> 该点为分类正确的点

•0<αi<C -> 该点为软边界上的点

•αi=c -> 该点嵌入了软边界内

• 此时如果ξ<1 ，该点被正确分类

• 此时如果ξ=1 ，该点刚好落在超平面上

• 此时如果ξ>1 , 该点被错误分类

## **总结软间隔SVM算法分析求解过程** ##

### 设定惩罚系数C-构造优化问题 ###

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_8_color_FFFFFF_t_70_g_se_x_16 1][]

### 用SMO算法求出α\* ###

### 计算W ###

![95038309121a45e0bc02889147568e11.jpg][]

### 找到全部的支持向量，计算出b ###

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_6_color_FFFFFF_t_70_g_se_x_16 1][]

### 求b均值 ###

![4c0423c76f4b43a8996023f90e1b86b2.jpg][]

# 非线性支持向量机 #

## 升维处理线性不可分 ##

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_18_color_FFFFFF_t_70_g_se_x_16][]

线性可分

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_18_color_FFFFFF_t_70_g_se_x_16 1][]

线性不可分

不可分的数据通过一定方式升维到高维变成线性可分

![213d2e0d4f5131790671a13265acddb3.gif][]

## SVM的升维 ##

原始线性优化问题

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_7_color_FFFFFF_t_70_g_se_x_16 3][]

升维后：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_9_color_FFFFFF_t_70_g_se_x_16 1][]

## 维度爆炸和计算量问题 ##

升维有可能导致维度激增，例如使用多项式回归的方式进行升维，2维x1,x2会升到5维x1,x2,x1\*x2,x1^2,x2^2，3维的升维会到19维，10维升维后会更夸张。

而且升维后由于要计算![41956213941e4da98e5a851cbd89ce44.png][]即样本映射到特征空间之后的的内积，由于特征空间可能维度很高，甚至可能是无穷维，因此直接计算通常是很困难的

## 引入核函数取代计算非线性映射函数的内积 ##

由于优化问题中我们只需要求得![41956213941e4da98e5a851cbd89ce44.png][]的结果，并不需要知道具体的φ(x)是什么，于是为了解决该问题可设想存在核函数：

![0e9173e2d80a40afb25346b998dc60c2.png][]

这样跳过φ(x)直接定义![41956213941e4da98e5a851cbd89ce44.png][]的结果，既可以达到升维的效果，又可以避免维度爆炸的问题，这给求解带来很大的方便

此时，对偶问题的目标函数变为了：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_12_color_FFFFFF_t_70_g_se_x_16 2][]

判别函数(超平面f(x))变为了：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_10_color_FFFFFF_t_70_g_se_x_16 1][]

补充一下之前的判别函数是这样： ![f4db18b38cd14092a8253202af7722d0.jpg][]又因为![127c823ead23471a966bea73faa0b667.jpg][]

所以原来的判别式也可以写成这样：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_10_color_FFFFFF_t_70_g_se_x_16 2][]

## 常用的核函数 ##

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

## 核函数解决非线性分类的效果 ##

假设我们要建一个篱笆把羊群和狼群分开，这个篱笆就是分类器了，下边是SVM、逻辑回归、决策树分类的效果：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_14_color_FFFFFF_t_70_g_se_x_16][]

可以看到SVM的效果是非常好的，从侧面简单说明了SVM使用非线性分类器的优势，而逻辑模式以及决策树模式都是使用了直线方法。

## 非线性SVM目标函数和求解过程总结 ##

### 选择某个核函数及其对应的超参数 ###

## 选择惩罚系数C ##

### 构造最优化问题 ###

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_8_color_FFFFFF_t_70_g_se_x_16 2][]

### 利用SMO算法求解出一组α\*   根据α\*计算w\*   根据α\*找到全部支持向量，计算每个支持向量对应的bs\*   对bs\*求均值得到最后的b\* ###

学得的超平面为：

![108d6cadff9e4bd98f88d6c424ff6922.jpg][]

最终的判别函数为：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_9_color_FFFFFF_t_70_g_se_x_16 2][]

参考：[SVM\_liugan528的博客-CSDN博客\_svm][SVM_liugan528_-CSDN_svm]

[机器学习——svm支持向量机的原理 - it610.com][svm_ - it610.com]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_11_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/c06d365b283f455c8c96c3bef1eddf78.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_7_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/871bc81f22774411b2b5edd503d28a88.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_9_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/40cef425e8324a4cb4ffd3fc0354cd0a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_11_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/30151874920247bf8044cc28ecee5f55.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_12_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/f2dc5dbedaab414e99cd6e6869efbefe.png
[5abd2073ec6341b68b40166e950540aa.png]: /images/20220828/58bca07e3e7242b3a465ae7e2004f844.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/3eb46627054440f8983718040b75c56a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_7_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/f6d0c7135f5d4307ae0388587e3114c6.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_6_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/9af1a26bc88644649b979afd3edc7ec8.png
[fa2f39e85e1149079990054874faf6ac.png]: /images/20220828/bfb8f18fdf9b4a1d8c5ec02fdfa19e40.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_12_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/cf776bcae5a04a01969b6fb1f2e6d4a9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_10_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/c0ef19b4c63f483ab2f2971e5cadb7e1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_7_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/0f3b266cd3c04f9e8f058b0dd6796135.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_8_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/cc21c7dff2964609bc1ebbcde61c1304.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_8_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/542eb7bdd1be4e5b91b02e4979e1bf0e.png
[95038309121a45e0bc02889147568e11.jpg]: /images/20220828/29aae29c71f14f88b767a1ef34440780.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_6_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/c6a32385b0874e31b574b7345a5bdde5.png
[4c0423c76f4b43a8996023f90e1b86b2.jpg]: /images/20220828/b285fa1dba6b472ebb2b9b471b62e9d9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/399f9e11919847ff89330d123960903c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_18_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/70610d4ef4d14f639875d439ac56dedc.png
[213d2e0d4f5131790671a13265acddb3.gif]: /images/20220828/f8665f857c164f4a899399de5ec53247.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_7_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/a4accf79825e41768bb829206297d303.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_9_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/da8b5d53539543d480a263b7951ce2bd.png
[41956213941e4da98e5a851cbd89ce44.png]: /images/20220828/c063d312a8bd43649574fee99da47baa.png
[0e9173e2d80a40afb25346b998dc60c2.png]: /images/20220828/c2208bab12234fc983a00b613747a59c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_12_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/00ffddd91f334991951d010ebf975cde.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_10_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/1f149d1d2f9c4af4baddec76a3f7d5ac.png
[f4db18b38cd14092a8253202af7722d0.jpg]: https://img-blog.csdnimg.cn/f4db18b38cd14092a8253202af7722d0.jpg
[127c823ead23471a966bea73faa0b667.jpg]: /images/20220828/c8cd516da0cc4f6487fce7e36a3d2a7d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_10_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/9d24f27bc23b4946b9b21dbf83602e9d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/9f2d72f48b4241dfb6213e524af232ef.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/80da6627cb224081b0a4417a3cace209.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_8_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/2bcf64bea7a446baa73b6d5f9349c549.png
[108d6cadff9e4bd98f88d6c424ff6922.jpg]: /images/20220828/f55f51521cd64ce281837f87341ea11c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_9_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/dd5ec43e7db849abb1563673eefa7053.png
[SVM_liugan528_-CSDN_svm]: https://blog.csdn.net/liugan528/article/details/79448379
[svm_ - it610.com]: https://www.it610.com/article/5174589.htm