锐客网

  1. 首页 > it技术 > >

支持向量机|支持向量机 (Support Vector Machine)

SVM俗语：
SVM有三宝： 间隔 、对偶、核技巧
SVM的由来
对于线性可分的问题，一般可以使用PLA得到解决，但是根据其原理可以得到，PLA只是负责得到一个线性可分的线/超平面，但是对于这根线/超平面，并不能保证最好。
所以对于线性可分数据来说，有无数条线/平面满足条件，但是最完美（最完美的意思表示在在新的数据上拟合效果最好）只有一条, 鲁棒性最好
margin：
the distance of hyperplane to its closest point
has at least 2 closest points (one is a positive point and one is a negative point)
总结一下
SVM = hyperplane + maximum margin
SVM关键词
监督学习，二分类器，学习策略：间隔最大化
SVM的目标函数
对于二维平面来说，通过一条直线可以将平面分成两部分，一部分数据为正，一部分数据为负，由此进行拓展，对于维的，其超平面的方程为：

与之超平面对应的分类模型为

首先明确一点垂直与所求的超平面：
证明：任意取超平面上的两点,，其构成向量


两个公式相减，得到
为了后续方便计算和说明，这里做一个假设
其中为距离超平面最近的正类点
进一步说明：可以为任何值，但是由于已经确定了为距离超平面最近的正类点，所以即使结果为10或者为100或者任意大于1的值，只要对其进行归一化，并不会对其他的点有任何影响（主要就是强调一个相对的概念）。

支持向量机|支持向量机 (Support Vector Machine)
文章图片
1/||w||的由来.png



所以距离超平面最近的点与超平面的距离为,也就是所谓的maximum margin的的表达，于是SVM的目标函数则找到了，即

SVM目标函数的转化 虽然找到了SVM的目标函数，并且想要找到其的最大值，但是不要忘记一个假设前提，, 其限制了与超平面最近的正类点，与其说是限制了与超平面最近的正类点，不如说是限制了所有的点，也就是说，除开最近的点，其他点的得到的结果必须比1大，也就是目标函数扩展成：
（1）

其中N表示数据点的总数
我们对其进行进一步转化
（2）


我们对第（2）中第二个限制进行分解，得到
(3)


【支持向量机|支持向量机 (Support Vector Machine)】这里需要解释一下（2）到（3）的过程，其实严格来说（2）的限制和（3）的限制其实不对等，因为（2）中说明是最近的点距离为1，但是（3）中说明的是所有点距离大于等于1，这里是对于（2）来说是一个充分不必要条件，唯一的风险就是所有的点都比1大，举个例子，比如说一共5个点，对于（2）的话距离的列表可能为[1,2,3,4,5]，对于（3）来说可能为[10,20,30,40,50]。
这里就需要重新回到我们之前提到的相对距离的概念了，这个结果10的得到其实是，所以只要将和的除以10，最近距离的点结果依旧是1，所以在这里的话（2）和（3）的限制是相等的。
对（3）进一步转化得到（4），这里还进行一步转化的原因是为了利用已有的凸优化理论，使用1/2是为了方便后续计算
（4）


这里我们可以发现其实限制有N个， 带上绝对值符号不利于后续的计算，所以对其进行分解，
当point为正类时，，
当point为正类时，，
所以限制转化为

这样目标函数求解问题得到的最终的完美形式：


优化问题求解 （数学背景）
通过上述一系列的转化，可以发现，最终目标函数的求解本质上是一个线性规划的优化问题，其中给定的约束有个（个点，所以有个不等式），未知参数有个（个和个)，目标函数是二次的。
拉格朗日乘子法 拉格朗日乘子法：有约束情况下求函数极值的方法,这里借助拉格朗日乘子法引出对偶问题
https://www.youtube.com/watch?v=lDehPPIgQpI
https://charlesliuyx.github.io/2017/09/20/%E6%8B%89%E6%A0%BC%E6%9C%97%E6%97%A5%E4%B9%98%E6%B3%95%E5%92%8CKKT%E6%9D%A1%E4%BB%B6/
这里我们将原问题称为,
的拉格朗日函数为（更多信息参考上述链接，这里直接给出结论）：



最小化问题 : 转化为
对的函数，为自变量
首先以为自变量求的最大值，随后以为自变量求得到的中的最小值，其本质上还是对的函数
使用拉格朗日乘子的好处：
将带约束的问题转化为无约束的问题，这里指的带约束是指对参数的限制条件
但是描述的时候可以知道其实是带了，这样子的话其实还是会有对参数的约束，其实这个约束可以舍去，因为函数天然的带有约束
解释：https://www.youtube.com/watch?v=WeoASoHnTpc&list=PLOxMGJ_8X74Z1N3OcacUaCxiXaGNHtFw2&index=2

支持向量机|支持向量机 (Support Vector Machine)
文章图片
Lagrange的奇妙之处.png
对偶的引出 目标函数是二次，约束条件是线性，=> 凸二次规划问题 (QPP,Quadratic programming problem)，理想情况可以使用一些QP的套件直接进行求解得到答案，但是存在样本维度过高或者样本数很多，或者存在样本特征升维的一些情况，QP可能就不太能够直接求解，由此引入了对偶求解的概念。
由于将问题转化成了 ,为了求解的方便，可以将转化为其对偶问题


这里需要提及一个关于对偶问题的性质：
1.弱对偶性——对偶问题原问题

简单的来说就是小的里面最大的小不会比大的里面最小的大（鸡头<凤尾）
证明：
https://www.youtube.com/watch?v=bscvk5n_TsM&list=PLOxMGJ_8X74Z1N3OcacUaCxiXaGNHtFw2&index=5
2.强对偶性

凸二次函数优化问题 + 约束线性 ---> 满足强对偶关系
根据上述的定理可以发现通过这样一步的对偶问题转换，我们把本来需要求的以为参数的的最大值后以以为参数的最小值(本质上未知数是) 转换成
以为参数的的最小值后以为参数的最大值(本质上未知数是)

支持向量机|支持向量机 (Support Vector Machine)
文章图片
对偶问题转化1.png
支持向量机|支持向量机 (Support Vector Machine)
文章图片
对偶问题转化2.png
KKT 一句话解释：对偶问题具有强对偶性 <=> KKT

支持向量机|支持向量机 (Support Vector Machine)
文章图片
KTT与w* ,b*求解.png 总结：
SVM参数的求解主要是通过问题的不断转化得到的
其主要流程为：
1.原始的约束问题通过拉格朗日函数转化为无约束问题
2.通过的强对偶性转换成为对偶问题
3.在满足KKT的条件下进行的求解
拉格朗日对偶性的求解

支持向量机|支持向量机 (Support Vector Machine)
文章图片
函数的转换 图片复制于github.png SMO 算法
通过上述的描述，得到最终所求的为


所以我们的目的为求合适的 ,这里就采用SMO的算法来进行解决，由于本人水平有限，暂时还没搞懂，待到明白了再来补上。
下次一定，下次一定。
OP优化包
pip install cvxopt
支持向量机|支持向量机 (Support Vector Machine)
文章图片
cvxopt.png 总结 至此，SVM的整个流程基本上捋了一遍，注意这里主要介绍的是硬间隔问题，但是掌握了这个，再去看软间隔和非线性分类（核函数），一定会事半功倍。
参考资料：https://github.com/ws13685555932/machine_learning_derivation/blob/master/06%20%E6%94%AF%E6%8C%81%E5%90%91%E9%87%8F%E6%9C%BA.pdf
http://slidesplayer.com/slide/11358544/
https://www.zhihu.com/question/36301367
https://www.jiqizhixin.com/articles/2018-10-17-20
https://charlesliuyx.github.io/2017/09/20/%E6%8B%89%E6%A0%BC%E6%9C%97%E6%97%A5%E4%B9%98%E6%B3%95%E5%92%8CKKT%E6%9D%A1%E4%BB%B6/
https://www.youtube.com/watch?v=lDehPPIgQpI
https://blog.csdn.net/v_JULY_v/article/details/7624837

    推荐阅读


    上一篇：看书有道

    下一篇：陈英书法家|陈英书法家 神贯气畅 书写江山