从SVM中获取支持向量

柔光的暖阳◎ 2022-01-31 14:23 181阅读 0赞

### 1.KKT条件（不等式约束条件） ###

设目标函数f(x)，不等式约束为g(x)，等式约束条件h(x)。此时的约束优化问题描述如下：

![Center][]

则我们定义不等式约束下的拉格朗日函数L，则L表达式为：

![Center 1][]

其中f(x)是原目标函数，hj(x)是第j个等式约束条件，λj是对应的约束系数，gk是不等式约束，uk是对应的约束系数。0

此时若要求解上述优化问题，必须满足下述条件（也是我们的求解条件）：

![Center 2][]

这些求解条件就是KKT条件。(1)是对拉格朗日函数取极值时候带来的一个必要条件，(2)是拉格朗日系数约束（同等式情况），(3)是不等式约束情况，(4)是互补松弛条件，(5)、(6)是原约束条件。

> 对于一般的任意问题而言，KKT条件是使一组解成为最优解的必要条件，当原问题是凸问题的时候，KKT条件也是充分条件。

关于条件(3)，后面一篇博客中给出的解释是：我们构造L(x,λ,u)函数，是希望L(x,λ,u)<=f(x)的（min表示求最小值）。在L(x,λ,u)表达式中第二项为0，若使得第三项小于等于0就必须使得系数u>=0，这也就是条件(3)。

关于条件(4),直观的解释可以这么看:要求得L(x,λ,u)的最小值一定是三个公式项中取得最小值，此时第三项最小就是等于0值的时候。稍微正式一点的解释，是由松弛变量推导而来。

为方便表示，举个简单的例子：

现有如下不等式约束优化问题：

![Center 3][]

此时引入松弛变量可以将不等式约束变成等式约束。设a1和b1为两个松弛变量，则上述的不等式约束可写为：

![Center 4][]

则该问题的拉格朗日函数为：

![Center 5][]

根据拉格朗日乘子法，求解方程组：

![Center 6][]

则

![Center 7][]

同样 u2b1=0，来分析g2(x)起作用和不起作用约束。

> 于是推出条件：SVM就是据此条件推出支持向量的，支持向量和超平面有相同的W， b

![Center 8][]  
  
[原文链接：][Link 1]

### 2.线性可分，硬间隔的支持向量 ###

> **根据KKT条件中的对偶互补条件 ![\\alpha\_\{i\}^\{\*\}(y\_i(w^Tx\_i + b) - 1) = 0][alpha_i_y_i_w_Tx_i _ b_ - 1_ _ 0]**
> 
> **如果 ![\\alpha\_i>0][alpha_i_0] 则有![y\_i(w^Tx\_i + b) = 1][y_i_w_Tx_i _ b_ _ 1] 即点在支持向量上**
> 
> **如果![\\alpha\_i = 0][alpha_i _ 0] 则有![y\_i(w^Tx\_i + b) \\geq 1][y_i_w_Tx_i _ b_ _geq 1]， 即样本在支持向量上 或者 已经被正确分类。**

### 3.非线性可分，软间隔 ###

> **根据KKT条件中的对偶互补条件 ![\\alpha\_\{i\}^\{\*\}(y\_i(w^Tx\_i + b) - 1 + \\xi\_i^\{\*\}) = 0][alpha_i_y_i_w_Tx_i _ b_ - 1 _ _xi_i_ _ 0]**
> 
> **　a) 如果![\\alpha\_i = 0][alpha_i _ 0],那么 ![y\_i(w^Tx\_i + b) \\geq 1][y_i_w_Tx_i _ b_ _geq 1] , 即样本在间隔边界上 或者 已经被正确分类。如图中所有远离间隔边界的点。**
> 
>  **b) 如果![0< \\alpha < C][0_ _alpha _ C] , ![\\xi\_i = 0][xi_i _ 0] 那么 ![y\_i(w^Tx\_i + b) = 1][y_i_w_Tx_i _ b_ _ 1] ,即点在间隔边界上。**
> 
>  **c) 如果![\\alpha = C][alpha _ C]，说明这是一个可能比较异常的点，需要检查 ![\\xi\_i][xi_i]**
> 
> **　　　　　　i)如果![0 \\leq \\xi\_i < 1][0 _leq _xi_i _ 1], 则有 ![y\_i(w^Tx\_i + b) > 0][y_i_w_Tx_i _ b_ _ 0] ，大于0但是小于1 ， 那么点被正确分类，但是却在超平面和自己类别的间隔边界之间。如图中的样本 （2 和 4）**
> 
> **　　　　　　ii)如果 ![\\xi\_i = 1][xi_i _ 1] , 则有 ![y\_i(w^Tx\_i + b) = 0][y_i_w_Tx_i _ b_ _ 0 1] 那么点在分离超平面上，无法被正确分类。**
> 
> **　　　　　　iii)如果![\\xi\_i > 1][xi_i _ 1 1] , 则有 ![y\_i(w^Tx\_i + b) < 0][y_i_w_Tx_i _ b_ _ 0 2] 那么点在超平面的另一侧，也就是说，这个点不能被正常分类。如图中的样本 1 和 3 . 分类错误**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70][]

**参考：[https://www.cnblogs.com/pinard/p/6100722.html][https_www.cnblogs.com_pinard_p_6100722.html]**

### 项目推荐： ###

**[2000多G的计算机各行业电子资源分享（持续更新）][2000_G]**

**[2020年微信小程序全栈项目之喵喵交友【附课件和源码】][2020]**

**[Spring Boot开发小而美的个人博客【附课件和源码】][Spring Boot]**

**[Java微服务实战296集大型视频-谷粒商城【附代码和课件】][Java_296_-]**

**[Java开发微服务畅购商城实战【全357集大项目】-附代码和课件][Java_357_-]**

**[最全最详细数据结构与算法视频-【附课件和源码】][-]**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70_pic_center]

[Center]: /images/20220131/69b78ff904044c9c87bbd986e0b78d77.png
[Center 1]: /images/20220131/8bf1c2decf3f4acb93178c097e7dad3b.png
[Center 2]: /images/20220131/c4516dea926e4424a28a952ad5dbffc4.png
[Center 3]: /images/20220131/77f8843d544148609018800ce58794ac.png
[Center 4]: /images/20220131/a9713d24f8af428889113ce0a6c31b82.png
[Center 5]: /images/20220131/ed7991a8aefe4844bb8c364c9d3efd69.png
[Center 6]: /images/20220131/8648020dc2214b88b996d2c147de96d7.png
[Center 7]: /images/20220131/655aa518e46d43fb9a2e721c5a4618cc.png
[Center 8]: /images/20220131/2a299d874b8d40babcc466841dd6cf29.png
[Link 1]: https://blog.csdn.net/johnnyconstantine/article/details/46335763%C2%A0
[alpha_i_y_i_w_Tx_i _ b_ - 1_ _ 0]: https://private.codecogs.com/gif.latex?%5Calpha_%7Bi%7D%5E%7B*%7D%28y_i%28w%5ETx_i%20&plus;%20b%29%20-%201%29%20%3D%200
[alpha_i_0]: https://private.codecogs.com/gif.latex?%5Calpha_i%3E0
[y_i_w_Tx_i _ b_ _ 1]: https://private.codecogs.com/gif.latex?y_i%28w%5ETx_i%20&plus;%20b%29%20%3D%201
[alpha_i _ 0]: https://private.codecogs.com/gif.latex?%5Calpha_i%20%3D%200
[y_i_w_Tx_i _ b_ _geq 1]: https://private.codecogs.com/gif.latex?y_i%28w%5ETx_i%20&plus;%20b%29%20%5Cgeq%201
[alpha_i_y_i_w_Tx_i _ b_ - 1 _ _xi_i_ _ 0]: https://private.codecogs.com/gif.latex?%5Calpha_%7Bi%7D%5E%7B*%7D%28y_i%28w%5ETx_i%20&plus;%20b%29%20-%201%20&plus;%20%5Cxi_i%5E%7B*%7D%29%20%3D%200
[0_ _alpha _ C]: https://private.codecogs.com/gif.latex?0%3C%20%5Calpha%20%3C%20C
[xi_i _ 0]: https://private.codecogs.com/gif.latex?%5Cxi_i%20%3D%200
[alpha _ C]: https://private.codecogs.com/gif.latex?%5Calpha%20%3D%20C
[xi_i]: https://private.codecogs.com/gif.latex?%5Cxi_i
[0 _leq _xi_i _ 1]: https://private.codecogs.com/gif.latex?0%20%5Cleq%20%5Cxi_i%20%3C%201
[y_i_w_Tx_i _ b_ _ 0]: https://private.codecogs.com/gif.latex?y_i%28w%5ETx_i%20&plus;%20b%29%20%3E%200
[xi_i _ 1]: https://private.codecogs.com/gif.latex?%5Cxi_i%20%3D%201
[y_i_w_Tx_i _ b_ _ 0 1]: https://private.codecogs.com/gif.latex?y_i%28w%5ETx_i%20&plus;%20b%29%20%3D%200
[xi_i _ 1 1]: https://private.codecogs.com/gif.latex?%5Cxi_i%20%3E%201
[y_i_w_Tx_i _ b_ _ 0 2]: https://private.codecogs.com/gif.latex?y_i%28w%5ETx_i%20&plus;%20b%29%20%3C%200
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70]: /images/20220131/a8122e49dbc14f128f0d34a034611024.png
[https_www.cnblogs.com_pinard_p_6100722.html]: https://www.cnblogs.com/pinard/p/6100722.html
[2000_G]: https://mp.weixin.qq.com/s/sP4JgGWkCzpgwKr9sAV2_Q
[2020]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487704&idx=1&sn=5f4b2127c4d49fd07ae072a0721424a2&chksm=e8036fc2df74e6d489c4aa9b06f917ef7cee6027f13e150fca53cf79d5d188d4ccc1af49e098&scene=21#wechat_redirect
[Spring Boot]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487798&idx=2&sn=ac0293b996521b872a9dba5fbb3e65e6&chksm=e8036e2cdf74e73aba104a9a994a5b2e31483e8dcbe0f1d9936f6d5173b887e1560f59d2819c&scene=21#wechat_redirect
[Java_296_-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487674&idx=1&sn=7aff0bdf2bb727303f3d3618995aef21&chksm=e8036fa0df74e6b6d872c7e6ece179c524ed463a4a6b74c96875475c9a3d5ddb903427dd993b&scene=21#wechat_redirect
[Java_357_-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247486376&idx=1&sn=d1fef270c463ea8ac663f6fbfedd70a0&chksm=e80374b2df74fda4d3bafba878a106a19e18c5fcda266008f4f37975847a21bc612ffcd5ff39&scene=21#wechat_redirect
[-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487750&idx=1&sn=747bccbb5f5ea6b58915198de40da777&chksm=e8036e1cdf74e70ae97a5e8e265b49d7236d904d291203309159d07ba1724033062c0e370843&scene=21#wechat_redirect
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70_pic_center]: /images/20220131/bf44796f7dcd49cc9ed7ce5d0fd68a20.png