支持向量机的理解（主要是对偶的理解）

谁践踏了优雅 2022-02-14 12:55 172阅读 0赞

# SVM的基本形式 #

如果找到了一个超平面可以正确分开这个数据集，那么意味着对于每个样本点x来说，其实它的函数间隔都大于等于0，即：  
![在这里插入图片描述][20190426112621236.png]  
（1）最最原始的优化目标：![在这里插入图片描述][20190426112712861.png]，即我们需要在每个可以正确分类的平面中，找到一个到数据集的间隔最大的平面，其中间隔被定义为这个数据集样本到这个平面的最小距离

（2）根据w和b缩放后优化目标不变，我们就可以让![在这里插入图片描述][20190426112735563.png]为1来简化这个问题，得到![在这里插入图片描述][2019042611274452.png]，然后再转化为等价的![在这里插入图片描述][20190426112749758.png]  
。  
(3)SVM的基本形式  
![在这里插入图片描述][20190426113035665.png]

# 对偶问题的理解 #

## 凸优化问题 ##

在优化问题中，凸优化问题由于具有优良的性质（局部最优解即是全局最优解），受到广泛研究。

对于一个含约束的优化问题：  
![在这里插入图片描述][20190426113326618.png]  
其中，f(x)为一个凸函数，变量x的可行域C是一个凸集，那么这个优化问题称为一个凸优化问题。  
将上面的约束条件的形式更加明确一点，一个凸优化问题可以写成：  
![在这里插入图片描述][20190426113406705.png]  
其中，f(x)当然仍然为一个凸函数，但对约束条件有一定要求：gi(x)是凸函数；hi(x)为仿射函数。这样的要求当然是为了保证可行域是一个凸集。  
不等式约束中gi(x)为凸函数，而凸函数的水平截集\{x|gi(x)≤α\} 是一个凸集(凸函数的性质)，这就使得不等式约束保证了可行域为凸集；  
对于等式约束hi(x)=0可以写成：  
![在这里插入图片描述][20190426113535366.png]  
要使得满足条件的x组成的集合为凸集，就要求hi(x) 既是一个凸函数，又是一个凹函数，这样hi(x)便只能是仿射函数了。

以上便是凸优化问题的一般形式。常见的线性规划、二次规划、二次约束二次规划等优化问题都是凸优化问题。

## 拉格朗日对偶 ##

抛开凸优化问题，回到一般的优化问题。

一般的优化问题可以写成以下形式：  
![在这里插入图片描述][20190426113705895.png]  
当然，这里对f(x)、gi(x)、hi(x)都是没有要求的。  
根据拉格朗日方法，对应的拉格朗日函数为：  
![在这里插入图片描述][20190426113742730.png]  
其中α 、β为拉格朗日乘数（都是向量，其长度分别对应于不等式约束和等式约束的个数），且αi≥0、β任意。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0ODYwMg_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20190426113947455.png]  
如果违背了原来的约束条件，比如存在某一个约束gi(x)>0，那么可以取αi任意大，这样θP(x)=+∞。违反等式约束hi(x)=0的情况是类似的。

所以可以认为θP(x)是对原理优化问题中的约束条件进行了吸收，是原来的约束优化问题变为无约束优化问题（相对于原来变量xx 无约束了），即原来的优化问题可以写成：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0ODYwMg_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0ODYwMg_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0ODYwMg_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0ODYwMg_size_16_color_FFFFFF_t_70 4]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0ODYwMg_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0ODYwMg_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][20190426114312360.png]

## 对偶问题和原问题的最优解相等的充要条件 ##

![在这里插入图片描述][20190426114411170.png]

## 调节svm参数：soft margin 问题 ##

当C趋于无穷大时：意味着分类严格不能有错误；  
当C趋于无穷小时：意味着可有更大的错误容忍度。

# 参考 #

凸优化与对偶问题  
[http://www.cnblogs.com/dreamvibe/p/4349886.html][http_www.cnblogs.com_dreamvibe_p_4349886.html]  
关于SVM数学细节逻辑的个人理解（二）：从基本形式转化为对偶问题  
[https://www.cnblogs.com/xxrxxr/p/7536131.html][https_www.cnblogs.com_xxrxxr_p_7536131.html]

[20190426112621236.png]: /images/20220214/f9cad13acf5c47d6bc2aedd28474f7e8.png
[20190426112712861.png]: /images/20220214/1726dc5c120a4557af42a71ec9f6aa10.png
[20190426112735563.png]: https://img-blog.csdnimg.cn/20190426112735563.png
[2019042611274452.png]: https://img-blog.csdnimg.cn/2019042611274452.png
[20190426112749758.png]: /images/20220214/6f09ff78333e4aa0985c93171311dff6.png
[20190426113035665.png]: /images/20220214/d10eba7d353244fa859940380027ef6c.png
[20190426113326618.png]: /images/20220214/44f8ea4e78254d90864585a0da57d4bb.png
[20190426113406705.png]: /images/20220214/0589025a197042ce886d1250457cdb17.png
[20190426113535366.png]: /images/20220214/57e34444fddf41de80672039770c37c4.png
[20190426113705895.png]: /images/20220214/775e22e83fc24d8ca9d0b41c4ce56320.png
[20190426113742730.png]: /images/20220214/885cc2162bb540039a7955145c8c78b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0ODYwMg_size_16_color_FFFFFF_t_70]: /images/20220214/d4a356bddede4988826ae61bc0b596ee.png
[20190426113947455.png]: /images/20220214/36231f06bc594419bc829d395995b663.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0ODYwMg_size_16_color_FFFFFF_t_70 1]: /images/20220214/05359be902694897a1c327f044bb7953.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0ODYwMg_size_16_color_FFFFFF_t_70 2]: /images/20220214/558f65ac0639462bb87f29fdab04b386.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0ODYwMg_size_16_color_FFFFFF_t_70 3]: /images/20220214/a61932485d2f46c78263893e454e6b3f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0ODYwMg_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20190426114236442.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0ODYwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0ODYwMg_size_16_color_FFFFFF_t_70 5]: /images/20220214/f45a06669d394e1eb95a23ae1904b16e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0ODYwMg_size_16_color_FFFFFF_t_70 6]: /images/20220214/0365762bfe36442fa5fee36c83dcda43.png
[20190426114312360.png]: /images/20220214/cbc5df57c1314eaf98d74748969fe0a6.png
[20190426114411170.png]: /images/20220214/ed403bd8a48f4b0f8c584e5ba0c3c914.png
[http_www.cnblogs.com_dreamvibe_p_4349886.html]: http://www.cnblogs.com/dreamvibe/p/4349886.html
[https_www.cnblogs.com_xxrxxr_p_7536131.html]: https://www.cnblogs.com/xxrxxr/p/7536131.html