支持向量机 (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的目标函数

对于二维平面来说，通过一条直线 $y=ax+b$ 可以将平面分成两部分，一部分数据为正，一部分数据为负，由此进行拓展，对于 $d$ 维的 $x$ ，其超平面的方程为：
$w^{T} x+b=0$
与之超平面对应的分类模型为
$f(w,b) = sign(w^{T} x+b)$

首先明确一点 $w$ 垂直与所求的超平面：
证明：任意取超平面上的两点 $x_{1}$ , $x_{2}$ ，其构成向量 $x_{1}-x_{2}$
$w^{T} x_{1}+b=0$

$w^{T} x_{2}+b=0$

两个公式相减，得到 $w^{T} (x_{1}-x_{2})= 0$

为了后续方便计算和说明，这里做一个假设
$w^{T} x_{n}+b=1$ 其中 $x_{n}$ 为距离超平面最近的正类点

进一步说明： $w^{T} x_{n}+b$ 可以为任何值，但是由于已经确定了 $x_{n}$ 为距离超平面最近的正类点，所以即使结果为10或者为100或者任意大于1的值，只要对其进行归一化，并不会对其他的点有任何影响（主要就是强调一个相对的概念）。

1/||w||的由来.png

$w^{T} (x_{n}-x) = w^{T} (a+c) =w^{T} c = ||w||*||c||$

$||c|| = \frac{1}{\|\vec{w}\|}$

所以距离超平面最近的点与超平面的距离为 $\frac{1}{\|\vec{w}\|}$ ,也就是所谓的maximum margin的的表达，于是SVM的目标函数则找到了，即
$max \frac{1}{\|\vec{w}\|}$

SVM目标函数的转化

虽然找到了SVM的目标函数 $\frac{1}{\|\vec{w}\|}$ ，并且想要找到其的最大值，但是不要忘记一个假设前提， $w^{T} x_{n}+b=1$ , 其限制了与超平面最近的正类点，与其说是限制了与超平面最近的正类点，不如说是限制了所有的点，也就是说，除开最近的点 $w^{T} x_{n}+b=1$ ，其他点的得到的结果必须比1大，也就是目标函数扩展成：

（1）
$\max \frac{1}{\|\vec{w}\|}$

$s.t. \min |w^{T} x_{i}+b|=1 ,i = 1...N$ 其中N表示数据点的总数

我们对其进行进一步转化
（2）

$\min ||w||$

$s.t. \min |w^{T} x_{i}+b|=1 ,i = 1...N$

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

$\min ||w||$

$\forall i , |w^{T} x_{i}+b| \geq1 ,i = 1...N$

这里需要解释一下（2）到（3）的过程，其实严格来说（2）的限制和（3）的限制其实不对等，因为（2）中说明是最近的点距离为1，但是（3）中说明的是所有点距离大于等于1，这里是对于（2）来说是一个充分不必要条件，唯一的风险就是所有的点都比1大，举个例子，比如说一共5个点，对于（2）的话距离的列表可能为[1,2,3,4,5]，对于（3）来说可能为[10,20,30,40,50]。

这里就需要重新回到我们之前提到的相对距离的概念了，这个结果10的得到其实是 $w^{T} x_{i}+b = 10$ ，所以只要将 $w$ 和 $b$ 的除以10，最近距离的点结果依旧是1，所以在这里的话（2）和（3）的限制是相等的。

对（3）进一步转化得到（4），这里还进行一步转化的原因是为了利用已有的凸优化理论，使用1/2是为了方便后续计算
（4）
$\min \frac{1}{2} w^{T} \cdot w$

$\forall i , |w^{T} x_{i}+b| \geq1 ,i = 1...N$

这里我们可以发现其实限制有N个， $|w^{T} x_{i}+b| \geq1$ 带上绝对值符号不利于后续的计算，所以对其进行分解，
当point为正类时， $w^{T} x_{i}+b \geq1$ ， $y_{i} = +1$
当point为正类时， $w^{T} x_{i}+b \leq1$ ， $y_{i} = -1$
所以限制转化为
$\forall i , y_{i} (w^{T} x_{i}+b) \geq1 ,i = 1...N$

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

$\min \frac{1}{2} w^{T} \cdot w$

$\forall i , y_{i} (w^{T} x_{i}+b) \geq1 ,i = 1...N$

优化问题求解（数学背景）

通过上述一系列的转化，可以发现，最终目标函数的求解本质上是一个线性规划的优化问题，其中给定的约束有 $N$ 个（ $N$ 个点，所以有 $N$ 个不等式），未知参数有 $d+1$ 个（ $d$ 个 $w$ 和 $1$ 个 $b$ )，目标函数是二次的。

拉格朗日乘子法

拉格朗日乘子法：有约束情况下求函数极值的方法,这里借助拉格朗日乘子法引出对偶问题
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/

这里我们将原问题称为 $p1$ ,
$p1$ 的拉格朗日函数 $p2$ 为（更多信息参考上述链接，这里直接给出结论）：
$L(w, b, \lambda)=\frac{1}{2} w^{T} w+\sum_{i=1}^{N} \lambda_{i}\left[1-y_{i}\left(w^{T} x_{i}+b\right)\right]$

$\lambda_{i} \geq 0$

$1- y_{i}(w^{T} x_{i}+b) \leq 0$

最小化问题 $p1$ : $\min_{w, b} \frac{1}{2} w^{T} \cdot w$ 转化为 $p2:$ $\min _{w, b} \max _{\lambda} L(w, b ,\lambda)$
$p1$ 对 $w, b$ 的函数， $w,b$ 为自变量
$p2$ 首先以 $\lambda$ 为自变量求 $L$ 的最大值 $L1$ ，随后以 $w,b$ 为自变量求得到的 $L1$ 中的最小值，其本质上还是对 $w, b$ 的函数

使用拉格朗日乘子的好处：
将带约束的问题转化为无约束的问题，这里指的带约束是指对参数 $w,b$ 的限制条件

但是描述 $p2$ 的时候可以知道其实是带了 $1- y_{i}(w^{T} x_{i}+b) \leq 0$ ，这样子的话其实还是会有对参数 $w,b$ 的约束，其实这个约束可以舍去，因为函数 $L$ 天然的带有 $1- y_{i}(w^{T} x_{i}+b) \leq 0$ 约束

解释：https://www.youtube.com/watch?v=WeoASoHnTpc&list=PLOxMGJ_8X74Z1N3OcacUaCxiXaGNHtFw2&index=2

Lagrange的奇妙之处.png

对偶的引出

目标函数是二次，约束条件是线性，=> 凸二次规划问题 (QPP,Quadratic programming problem)，理想情况可以使用一些QP的套件直接进行求解得到答案，但是存在样本维度过高或者样本数很多，或者存在样本特征升维的一些情况，QP可能就不太能够直接求解，由此引入了对偶求解的概念。

由于将问题 $p1$ 转化成了 $p2$ ,为了求解的方便，可以将 $p2$ 转化为其对偶问题 $p3$

$p2: \min _{w, b} \max _{\lambda} L(w, b ,\lambda)$

$p3: \max _{\lambda} \min _{w, b} L(w, b ,\lambda)$

这里需要提及一个关于对偶问题的性质：
1.弱对偶性——对偶问题 $\leqslant$ 原问题
$\max \min L \leqslant \min \max L$

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

2.强对偶性
$\max \min L = \min \max L$

凸二次函数优化问题 + 约束线性 ---> 满足强对偶关系

根据上述的定理可以发现通过这样一步的对偶问题转换，我们把本来需要求的以 $\lambda$ 为参数的 $L$ 的最大值后以以 $w,b$ 为参数的最小值(本质上未知数是 $w,b$ ) 转换成
以 $w,b$ 为参数的 $L$ 的最小值后以 $\lambda$ 为参数的最大值(本质上未知数是 $\lambda$ )

对偶问题转化1.png

对偶问题转化2.png

KKT

一句话解释：对偶问题具有强对偶性 <=> KKT

KTT与w* ,b*求解.png

总结：
SVM参数的求解主要是通过问题的不断转化得到的
其主要流程为：
1.原始的约束问题 $p1$ 通过拉格朗日函数转化为无约束问题 $p2$
2.通过 $p2$ 的强对偶性转换成为对偶问题 $p3$
3.在 $p3$ 满足KKT的条件下进行 $w^{*},b^{*}$ 的求解

拉格朗日对偶性的求解

函数的转换图片复制于github.png

SMO 算法

通过上述的描述，得到最终所求的 $w^{*},b^{*}$ 为
$w^{*}=\sum_{i=1}^{N} \lambda_{i} y_{i} x_{i}$

$b^{*}=y_{k}-\sum_{i=1}^{N} \lambda_{i} y_{i} x_{i}^{T} x_{k}$

所以我们的目的为求合适的 $\lambda_{i} , i= 1...N$ ,这里就采用SMO的算法来进行解决，由于本人水平有限，暂时还没搞懂，待到明白了再来补上。
下次一定，下次一定。

OP优化包

pip install cvxopt

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

最后编辑于：2020.04.19 14:29:13

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,732评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 87,496评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,264评论 0赞 338
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,807评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,806评论 5赞 368
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,675评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,029评论 3赞 399
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,683评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 41,704评论 1赞 299
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,666评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,773评论 1赞 332
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,413评论 4赞 321
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,016评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,978评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,204评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,083评论 2赞 350
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,503评论 2赞 343