支持向量机算法

支持向量机（Support Vector Machine, SVM）是有监督分类算法。

一、SVM本质

（1）无数条分类线

例如下图左侧分散了两类点（星星、圆圈），想要找到一条分类直线，当输入新点坐标 $(x_0,y_0)$ 时，这条分类直线可以判断这个输入点是星星还是圆圈。
不过，观察右图可以发现这样的直线可以有无数条，哪条直线才是最优的分类直线呢？

（2）确信度

首先，我们需要引入“确信度”的概念：一个点距离分离直线的远近表示分类预测的确信程度。
当输入新点坐标 $(x_0,y_0)$ ，该点距离分类直线距离很近的话，判断该点为XX类是没那么确认的。如果该点距离分类直线距离很远的话，就比较确信预测结果是正确的。

（3）点到直线的距离

确信度本质是点到直线的距离，让我们来回顾一下距离公式。
求P到直线的距离：

【首先过P点画直线的垂线】
由于两直线垂直，斜率之积为-1，得垂线的斜率为 $\frac{B}{A}$ ；
由于垂线过P点，垂线公式为 $y-y0=\frac{B}{A}(x-x0)$
·
【然后计算垂线和直线的交点Q】
经计算交点Q为：
$Q = (\frac{B^2x_0-ABy_0-AC}{A^2+B^2},\frac{A^2y_0-ABx_0-BC}{A^2+B^2})$
·
【点与点的距离】
P到直线的距离等价与PQ两点的距离，参考勾股定理 $a^2+b^2 = c^2$ ， $|PQ| = \sqrt{(x_1-x_0)^2+(y_1-y_0)^2}$
$=\sqrt{(\frac{B^2x_0-ABy_0-AC}{A^2+B^2}-x_0)^2+(\frac{A^2y_0-ABx_0-BC}{A^2+B^2}-y_0)^2}$
$=\frac{|Ax_0+By_0+C|}{\sqrt{A^2+B^2}}$
·
【备注】
三维空间点 $(x_0,yy_0,z_0)$ 到平面 $Ax+By+Cz+D=0$ 的距离为
$d = \frac{|Ax_0+By_0+Cz_0+D|}{\sqrt{A^2+B^2+C^2}}$

回顾上面的分类图，令分类直线为 $wx+b=0$ ，其中 $w=[w_1,w_2]^T$ ， $x=[x_1,x_2]$
代入上面点到直线的距离公式，得到任意点 $x_i$ 到该直线的距离为 $\gamma = \frac{|wx_i+b|}{||w||}$
其中 ${||w||} = \sqrt{w_1^2+w_2^2}$

（4）几何间隔

二分类的算法结果要么为正类，要么为负类，在SVM里令正类 $y=1$ ，负类 $y=-1$ 。

正类上的点到分类直线的距离为：
$\gamma = \frac{wx_i+b}{||w||}$
负类上的点到分类直线的距离为：
$\gamma = -\frac{wx_i+b}{||w||}$

因此我们构建一个新函数，我们把 $\gamma_i$ 叫做样本点到分类线的几何间隔：
$\gamma_i = y_i(\frac{wx_i+b}{||w||})$

如果点被正确分类， $\gamma$ 就是点到分类线的距离。如果分类错误，不管判断为正类还是负类，几何间隔就是一个负值。

整个训练数据集 $T={[(x_1,y_1),(x_2,y_2),...(x_n,y_n))]}$ 到分类线的几何间隔为：
$\gamma = \min_{w,b} \gamma_i$

训练数据集到分类线的几何间隔，就是离分类线最近点到分类线的距离。

(4) 最优分类线

让我们回到问题开始，什么样的分类线才是最优的分类线呢？肯定要让确信度尽可能的高吧，对最难分的点（离分类线最近的点）也要有足够大的确信度（距离尽可能大）。

就是说数据集到分类线的几何间隔最大的分类线就是最好的分类线。

二、最优分类线求解

假设给定空间上的训练数据为：
$T={[(x_1,y_1),(x_2,y_2),...(x_n,y_n))]}$ ，其中 $x_i\in R^n$ ， $y_i \in {(-1,+1)}$

（1）建立最优解

假设距离分类线最近点为 $(x_0,y_0)$ ，训练数据的几何距离为 $\gamma = \frac{y_0(wx_0+b)}{||w||}$
我们的目标是获得最大几何间隔的分类线（最大几何间隔的w,b最优解）
$\max_{w,b} \gamma$

$s.t. \frac{y_i(wx_i+b)}{||w||}\geq\gamma$

如果我们令 $y_0(wx_0+b)=\widehat{\gamma}$ ，那么 $\gamma = \frac{\widehat{\gamma}}{||w||}$ ，最优解问题就变成：
$\max_{w,b} \frac{\widehat{\gamma}}{||w||}$

$s.t. y_i(wx_i+b)\geq\widehat{\gamma}$

（2）简化问题

这个最优问题不好求解，假设令 $\widehat{\gamma}=1$ ，简化一下问题。
由于之前我们令训练数据的几何间隔 $\gamma = \frac{\widehat{\gamma}}{||w||}$ ，令 $\widehat{\gamma}=1$ 意味着我们假设训练数据的几何间隔为 $\frac{1}{||w||}$ ，意味着里分类线最近点到分类线的距离为 $\frac{1}{||w||}$

上图发现有两条虚线，虚线距离分类线的距离都是，虚线上的点到分类线的空间距离为: ，即正例方的虚线上的点满足，负例方的虚线上的点满足，我们把虚线上的点叫做“支持向量”。

简化后最优化问题为：
$\max_{w,b} \frac{1}{||w||}$

$s.t. y_i(wx_i+b)-1\geq0$

（3）最小化问题

我们一般还是喜欢求解最小化问题。求最大化 $\frac{1}{||w||}$ 等价于求最小化 $\frac{1}{2}||w||^2$ ，因此最优化问题变为：
$\min_{w,b} \frac{1}{2}||w||^2$

$s.t. y_i(wx_i+b)-1\geq0$

（4）拉格朗日乘数法

接下来我们就要求解最优的w,b值，引入神器“拉格朗日乘数法”。

拉格朗日乘数法
如果求解问题的格式为： $\min_{x,y} f(x,y)$ ， $s.t. g_i(x,y)\leq0,i=1,2,...N$
经过拉格朗日乘数法的推导，可以将问题转换为求解：
$\max_{\lambda}\min_{x,y}L(x,y,\lambda)$ ，其中 $L(x,y,\lambda) = f(x,y) + \sum_{i=1}^N\lambda_ig_i(x,y)$
其中 $\lambda = [\lambda_1,\lambda_2,...,\lambda_n]为拉格朗日乘子向量$ 。

转换最优解问题

通过加负号转换 $\ge$ 为 $\le$ ，所以最优解问题可以转换为：
$\max_{\lambda}\min_{w,b}L(w,b,\alpha)$

$L(w,b,\alpha) = \frac{1}{2}||w||^2 - \sum_{i=1}^N\alpha_i[y_i(wx_i+b)-1] = \frac{1}{2}||w||^2 - \sum_{i=1}^N\alpha_iy_i(wx_i+b) + \sum_{i=1}^N\alpha_i$

求解偏导

先求 $\min_{w,b}L(w,b,\alpha)$ ，我们知道有极大值或极小值的地方的斜率是0，所以我们先对w,b做偏导处理。
$\nabla_w L(w,b,\alpha) = w - \sum_{i=1}^N\alpha_iy_ix_i = 0$
$\nabla_b L(w,b,\alpha) = \sum_{i=1}^N\alpha_iy_i = 0$
可见 $w = \sum_{i=1}^N\alpha_iy_ix_i$ ，代入 $L(w,b,\alpha)$ ，公式变为：

$\min_{w,b}L(w,b,\alpha) = \frac{1}{2}\sum_{i=1}^N\alpha_iy_ix_i\sum_{j=1}^N\alpha_jy_jx_j - \sum_{i=1}^N\alpha_iy_i((\sum_{j=1}^N\alpha_jy_jx_j)·x_i+b) + \sum_{i=1}^N\alpha_i$
$= - \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i \alpha_jy_iy_j(x_i·x_j) + \sum_{i=1}^N\alpha_i$

此时原始求解问题变成：
$\max_{\alpha} -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i \alpha_jy_iy_j(x_i·x_j) + \sum_{i=1}^N\alpha_i$

$s.t. \sum_{i=1}^N\alpha_iy_i = 0; a_i \geq 0$

当然我们还是习惯求解最小值问题，转换后为：
$\min_{\alpha} \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i \alpha_jy_iy_j(x_i·x_j) - \sum_{i=1}^N\alpha_i$

$s.t. \sum_{i=1}^N\alpha_iy_i = 0; a_i \geq 0$

SMO求解最优 $\alpha$

到这一步原始最优化问题转变成求解最优 $alpha$ 问题，我们可以使用SMO（sequential minimal optimization，简称SMO）求解最优参数 $\alpha^*$ 。

最优参数 w,b

求解最优的 $\alpha^*$ 后，
根据上面偏导的计算结果， $w^* = \sum_{i=1}^N\alpha^*_iy_ix_i$ ；
$s.t. y_i(wx_i+b)-1\geq0$ ，最小值 $b$ 是在 $y_i(wx_i+b)-1=0$ 时，代入w后，计算得到 $b^* = y_j - \sum_{i=1}^N\alpha^*_iy_i(x_i·x_j)$

现在我们就有最优的分类线：
$w^*·x+b^* = 0$

分类决策函数：
$f(x) = sign(w^*·x+b^*)$

三、软间隔支持向量机

（1）硬间隔/软间隔

有的时候线性数据集中存在少量的异常点，由于这些异常点导致了数据集不能够线性划分。
我们通过引入软间隔的概念来解决这个问题。

支持向量机要求所有样本都必须划分正确，这叫做“硬间隔”；
而软间隔是允许一部分样本不满足约束条件的，但这样的样本要尽可能少^[5]。

软间隔面向场景：数据集由于异常点的存在是线性不可分的（不能用一条直线划分两类样本），将这些异常点去除后，剩下的大部分样本点是线性可分的。

（2）松弛变量

在二.（3）中我们经过一系列转换最后获得分类的最优解问题：
$\min_{w,b} \frac{1}{2}||w||^2$

$s.t. y_i(wx_i+b)-1\geq0$

使得所有样本点都被正确划分，都在虚线上或虚线外。
软间隔支持向量机允许存在样本点被错误划分，所以我们引入松弛变量 $\xi_i\geq 0$ ，使得 $y_i(w·x_i+b)\geq 1-\xi_i$ 。

点到分类线的几何间距 $=\frac{1-\xi_i}{||w||}$ ，两条虚线到分类线的几何间隔 $=\frac{1}{||w||}$ ，异常点到虚线的距离为 $\frac{\xi_i}{||w||}$ 。
如果 $1\geq\xi_i\geq 0$ 。回顾点到分类线的几何间隔 $=\frac{y_i(wx_i+b)}{||w||}$ ，两条虚线到分类线的几何间隔 $=\frac{1}{||w||}$ ，也就是允许存在样本点在虚线里。
如果 $\xi_i\geq 1$ ，点到分类线的几何间距 $=\frac{1-\xi_i}{||w||}\leq0$ ，说明允许存在样本点被分类错误。

改进后的最优解问题为：
$\min_{w,b} \frac{1}{2}||w||^2 + C\sum_{i=1}^N \xi_i$

$s.t. y_i(wx_i+b)\geq1-\xi_i$

这里称 $C$ 为惩罚参数， $C > 0$ 。

（3）拉格朗日乘子法转化最优问题

继续套神器，转化最优解问题为：
$L(w,b,\xi,\alpha,u)=\frac{1}{2}||w||^2 + C\sum_{i=1}^N\xi_i - \sum_{i=1}^N \alpha_i(y_i(wx_i+b)-1+\xi_i)-\sum_{i=1}^Nu_i\xi_i$
对 $w,b,\xi$ 求偏导等于0
$\nabla_w L(w,b,\xi,\alpha,u) = w - \sum_{i=1}^N\alpha_iy_ix_i = 0$
$\nabla_b L(w,b,\xi,\alpha,u) = - \sum_{i=1}^N\alpha_iy_i= 0$
$\nabla_{\xi} L(w,b,\xi,\alpha,u) = C-\alpha_i-u_i = 0$

把相关值代入 $L(w,b,\xi,\alpha,u)$ ，问题变为求解：
$\max_{\alpha} -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i·x_j) + \sum_{i=1}^N \alpha_i$
$s.t. \sum_{i=1}^N\alpha_iy_i=0;C-\alpha_i-u_i=0;\alpha_i\geq0;u_i\geq0 i=1,2,...,N$

当然，我们还是习惯求解最小值问题：
$\min_{\alpha} \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i·x_j) - \sum_{i=1}^N \alpha_i$
$s.t. \sum_{i=1}^N\alpha_iy_i=0;C\geq\alpha_i\geq0; i=1,2,...,N$

(3)最优解

根据计算出的最优值 $\alpha$ ，从而计算最优的参数w,b
$w^* = \sum_{i=1}^N\alpha_i^*y_ix_i$
$b = y_i- \sum_{i=1}^Ny_i\alpha_i^*(x_i·x_j)$
求得分离超平面： $w^*x+b^* = 0$
分类决策函数： $f(x) = sign(w^*·x + b^*)$

四、核函数

有些分类是线性划分无法满足的，不管怎么控制松弛变量，几何间隔都无法成功划分。

（1）SVM的高维转换

SVM使用核函数解决线性不可分问题。
核函数就是把低维映射到高维的方式，实质就是x特征的重组，把一个低维不可分问题转换为高维可分问题。
例如上图显然二维空间是不可线性划分的，那就把输入的 $[x_1,x_2]$ 转换成高维空间的特征，例如 $[x_1x_1,x_1x_2,x_2x_2]$ ，发现在高维空间是线性可分的，那就继续用上面的支持向量机求解最优分类函数。

（2）核函数

核函数K（kernel function）
就是指K(x, y) = <f(x), f(y)>，其中x和y是n维的输入值，f(·) 是从n维到m维的映射。<x, y>是x和y的内积^[7]。

令 x = (x1, x2, x3, x4); y = (y1, y2, y3, y4)；
令 f(x) = (x1x1, x1x2, x1x3, x1x4, x2x1, x2x2, x2x3, x2x4, x3x1, x3x2, x3x3, x3x4, x4x1, x4x2, x4x3, x4x4); f(y)亦然；
这样就实现了四维到更高维度的转换。
让我们带几个简单的数字进去看看是个什么效果：x = (1, 2, 3, 4); y = (5, 6, 7, 8). 那么：
f(x) = ( 1, 2, 3, 4, 2, 4, 6, 8, 3, 6, 9, 12, 4, 8, 12, 16) ;
f(y) = (25, 30, 35, 40, 30, 36, 42, 48, 35, 42, 49, 56, 40, 48, 56, 64) ;
<f(x), f(y)> = 25+60+105+160+60+144+252+384+105+252+441+672+160+384+672+1024
= 4900.
如果我们用核函数呢？
K(x, y) = (5+12+21+32)^2 = 70^2 = 4900.
所以核函数kernel其实就是帮我们省去在高维空间里进行繁琐计算的“简便运算法”。

支持向量机中假设输入的X映射到高维空间然后计算内积，但实际上核函数的使用，使得求解在低维空间上快速计算出目标内积。

参考资料

[1] 点到直线距离的七种推导公式：https://wenku.baidu.com/view/7f68a89cad02de80d4d840eb.html
[2] 拉格朗日乘子法：https://blog.csdn.net/loseinvain/article/details/78624888
[3] 支持向量机SVM之-SMO算法: https://blog.csdn.net/code__online/article/details/90518735
[4] SVM课程资料：https://www.bilibili.com/video/av39800693/?p=80
[5] SVM支持向量机—核函数、软间隔：https://www.cnblogs.com/luban/p/9516411.html
[6] 软间隔模型：https://www.jianshu.com/p/f8f09b638760
[7] 核函数：https://blog.csdn.net/kateyabc/article/details/79980880

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

支持向量机算法

一、SVM本质

（1）无数条分类线

（2）确信度

（3）点到直线的距离

（4）几何间隔

(4) 最优分类线

二、最优分类线求解

（1）建立最优解

（2）简化问题

（3）最小化问题

（4）拉格朗日乘数法

转换最优解问题

求解偏导

SMO求解最优

最优参数 w,b

三、软间隔支持向量机

（1）硬间隔/软间隔

（2）松弛变量

（3）拉格朗日乘子法转化最优问题

(3)最优解

四、核函数

（1）SVM的高维转换

（2）核函数

参考资料

推荐阅读更多精彩内容

SMO求解最优 $\alpha$