机器学习（三） --- SVM学习：模型求解

约定不等于承诺〃 2022-08-23 00:47 287阅读 0赞

学习[SVM理论基础][SVM]后，更进一步了解SVM算法就是了解SVM的算法的求解了，SVM算法的求解是一个凸优化问题，可以使用QP优化包进行求解，但是Platt提出了SMO算法，能够大大提升SVM模型的求解速度，这一节中主要就学习和掌握SVM算法的求解，会涉及到很多的数学公式，也是看了好久，查阅了好多资料，才从蒙蔽状态慢慢解放出来，然后对照着着比较简单的**SMO算法**，对照着算法流程，才慢慢变成半蒙蔽状态。

首先接着上一节理论基础遗留下的SVM算法的优化模型：

![20160603173338500][]

对于这种存在**条件约束的优化问题**，可以使用**拉格朗日乘法**来解决，学过高数的人，看着拉格朗日倍感亲切咯。

因此模型可以变成以下模型：

![20160603173625581][]

============================**拉格朗日对偶性的讨论**==============================

为了一般性的讨论问题，除了不等式条件，在这里，还引入等式条件，将上式一般化一下模型：

![20160603173849381][]

因此以拉格朗日处理以上模型的求解问题，得到：

![20160603174251209][]

将上述模型抽象为：

![20160603174408967][]其中：![20160603174435601][]代表**primal**，即原始模型的求解。

所以得到以下等价模型：

![20160603174856337][]

接着提出一个对偶性问题：上边是最大值的最小化，对偶问题应该就是最小值的最大化，即：

![20160603175746235][]

![20160603175703199][]

可以很好的理解是：**最大值的最小化大于等于最小值的最大化，对用一个式子的全局极值而言**。因此可以得到以下关系：

![20160603175959216][]

在某种条件下，上式的等号可以满足，这个条件称为KKT条件：

![20160603180155263][]

其中：![20160603180308233][]是原始模型问题的的解，![20160603180314195][]则是对偶问题的解。

===================================题外话============================================

**那么这里就有需要思考和注意的问题了，就是为什么要把问题转换到对偶问题的求解上来呢**：

在原始模型问题的求解上，即最大化值得最小化问题上，最大化是通过对alpha和beta的优化求解，最小化是通过w优化求解。

而对偶问题的求解上，即最小化值得最大化问题上，最小化是通过w的优化求解，最大化则是通过alpha和beta的求解上。

因此经过处理后，我们可以把模型的求解转换到alpha的求解上，这个就能引入所谓的SMO算。

====================**将拉格朗日对称性应用于SVM模型求解**===========================

回到SVM的模型求解问题上：经过拉格朗日处理后，得到了以下模型:

![20160603173625581][]

**求导：首先是实现最大化，对w求偏导：**

![20160603182534474][]

**得到****关系式一**：

![20160603182721179][]

**对****b求导，得到关系式二：**

![20160603182801665][]

将关系式一带入到模型中，则得到：

![20160603183320969][]

由于关系二的原因，式子简化为：

![20160603183306985][]

**因此****最后的模型求解转化为：**

![20160603183448002][]

**其中****需要注意的是，测试集的数据x的label的最后表达式为：**

![20160603183704802][]

对于该式，有以下几点说明：

*  由于支持向量具有稀疏性，因此对于大部分![20160603184055482][]的值为0，因此内积的计算仅仅只是测试数据与支持向量的内积，预算量较少
 *  测试数据和支持向量均为列向量，因此避免了复杂的矩阵计算
 *  这种内积性质可以很好的应用到核的概念中

============================= **"核"用于解决非线性分类** =============================

经过一系列的推导，最终转换到了由![20160603184055482][]的优化问题，从而求解模型优化。最后的式子是向量的内积的概念在其中，而我们上面讨论的问题都是以线性分类为基础的，从超平面的表达式就可以看出，对于非线性的分类问题呢？需要怎么求解，这就需要引出核的概念了。

核总的来说，就是一个映射函数，将一组特征向量，映射到高维的空间中，使得在低维空间不能线性分类解决的非线性问题，在高维空间内可以以线性概念解决。

下面是一组关于利用核进行映射后的概念性的解释图：

![20160603185420075][] ![20160603185435185][]

二维空间 三维空间

可以明显看到，在三维空间内，可以找到一个平面实现非线性的分类。

对于核的具体描述和分析，可以参见以下博客：

*  [http://blog.csdn.net/abcjennifer/article/details/7849812][http_blog.csdn.net_abcjennifer_article_details_7849812]
 *  [http://blog.csdn.net/v\_july\_v/article/details/7624837][http_blog.csdn.net_v_july_v_article_details_7624837]
 *  [http://cs229.stanford.edu/notes/cs229-notes3.pdf\#page=1][http_cs229.stanford.edu_notes_cs229-notes3.pdf_page_1]

但是由于在映射过程中，并不能保证完全的线性化，如下图：

![20160603190621087][]

左图是一个最优的margin classfier的情形，但是由于部分数据点映射的问题，导致跑偏的情况，所以最后的分类是右图的情形，这个分类器就不是最优的情形。对于着心中数据点成为outlier。因此需要进行一定的正则化，控制这种情况。

![20160603190917017][]

其中C是为了控制margin最大的超平面和保证数据点的偏差最小的权重，是人为设定的。经过推导，仿照之前的拉格朗日的方法，得到：

![20160603191256069][]

从而得到：

![20160603191314710][]

对于这个问题，可以用过SMO算法有效的解决。以上是SVM的模型问题，下一节将会继续学习如何将SMO算法应用于该问题的求解中。

[SVM]: http://blog.csdn.net/mao19931004/article/details/51570686
[20160603173338500]: /images/20220722/6cf040e0b22a49dbb52d8e4d9d469a8f.png
[20160603173625581]: /images/20220722/dc22082302354018afd51f4ae0d60a2d.png
[20160603173849381]: /images/20220722/808056def66c4b61a746a606e81594fb.png
[20160603174251209]: /images/20220722/2796b5b55d714c7795629b6efae18e54.png
[20160603174408967]: https://img-blog.csdn.net/20160603174408967
[20160603174435601]: /images/20220722/e2c45180572a4a6cab26d23e916899c1.png
[20160603174856337]: /images/20220722/0503556a3c6844dc9cf1566b59882625.png
[20160603175746235]: /images/20220722/7e78f97838674613b80eeffe8620a61d.png
[20160603175703199]: /images/20220722/23c46a548b4a4597b22c968fdbcb2bc4.png
[20160603175959216]: /images/20220722/6da7ff2ca8bb49c79c133b80c3535e2c.png
[20160603180155263]: /images/20220722/36628d3ae4634091aae00a6999baa4f4.png
[20160603180308233]: https://img-blog.csdn.net/20160603180308233
[20160603180314195]: /images/20220722/32663db4ed45497f89ed493383f5c7cc.png
[20160603182534474]: /images/20220722/5e2c1e3f82854961bc7b3df51d0bb1ca.png
[20160603182721179]: /images/20220722/a89c41ba7b5b451c8873f27b160e231f.png
[20160603182801665]: /images/20220722/cbf5d3cbb4844e33bf523978b768acb9.png
[20160603183320969]: /images/20220722/91b9d26cae8d431d8046e3f01fddd8ec.png
[20160603183306985]: /images/20220722/a43a8498bf3a47e096868ef0c3e31e3e.png
[20160603183448002]: /images/20220722/4d353c6692214cd6bf2e936b18d874ad.png
[20160603183704802]: /images/20220722/51b299265aae4e329860191ebd5e3850.png
[20160603184055482]: /images/20220722/36587e829b82437e926d0448b6137213.png
[20160603185420075]: https://img-blog.csdn.net/20160603185420075
[20160603185435185]: /images/20220722/cc6c1f9d40424b389611e9dffb0b88e0.png
[http_blog.csdn.net_abcjennifer_article_details_7849812]: http://blog.csdn.net/abcjennifer/article/details/7849812
[http_blog.csdn.net_v_july_v_article_details_7624837]: http://blog.csdn.net/v_july_v/article/details/7624837
[http_cs229.stanford.edu_notes_cs229-notes3.pdf_page_1]: http://cs229.stanford.edu/notes/cs229-notes3.pdf#page=1
[20160603190621087]: /images/20220722/655146f234024cd19d0be1a2a266e161.png
[20160603190917017]: /images/20220722/46c940c900414f43a537459194aba699.png
[20160603191256069]: /images/20220722/92b61c13fa2f4d8182dac81aa7cc5c3e.png
[20160603191314710]: /images/20220722/6770bc5cf54349a9ac890d67a097bdc9.png