SVM 原理引入

支持向量机( SVM，Support Vector Machine )

背景

2012年前较为火热, 但是在12年后被神经网络逼宫, 由于应用场景以及应用算法的不同, SVM还是需要有所了解，而且在面试中SVM一般都会问到, 支持向量机是一个非常 经典且高效的分类模型

要解决的问题

如下图所示，3条黑色的线都可以将两边的数据进行分类，

那哪条线作为决策边界才是最好的呢？

如果特征数据本身就很难分，那又怎么办呢？

计算复杂度怎么样？能否实际应用？

机器学习 - 算法 - SVM 支持向量机-LMLPHP

决策边界定义

两边雷区, 要选择一条部队不触发地雷的行军路线, 而且要尽可能的宽一点

向左边的图就窄一些, 右边宽一些

而这个所谓的行军道路就是 决策边界 , 越胖越好

以下的公式推导也皆使用此实例

机器学习 - 算法 - SVM 支持向量机-LMLPHP

距离计算

计算目的

对决策边界理解之后, 决策边界的计算就是我们要解决的问题, 即这里的物理意义就是距离的计算

决策边界的宽度是根据距离最近的点的距离决定的, 这里需要首选引入距离如何计算

数学转换计算

机器学习 - 算法 - SVM 支持向量机-LMLPHP

假设决策边界是一个阴影平面，那这个距离 distance 就是求点到平面 hyperplane 的距离

既然垂直于这个平面, 那就自然垂直于这个平面的任意一条线

但是直接求这个距离还是不容易的, 需要一定的转换

这里取出来 hyperplane 上的两个点 x` .x`` , 这两个点形成一个向量

计算出 x 到 x` 的距离, 然后计算出这个距离在垂直方向到平面的投影即可, 这也是 x 到平面的垂直距离了

公式中的 x` 需要消除掉, 利用 x` 在平面的特性, 因此将其转换成 -b 即可从而得到最终的距离计算公式

数学补充

wx+b=0 ? 是从何而来?

　　因为二维空间里面，一条直线的方程可以表示为：Ax+By+C=0

　　三维空间里面，平面的方程可以表示为：Ax+By+Cz+D=0。

　　依次推广，n维空间的超平面方程可以表示为：Ax+Bx+Cx+Dx+Ex+Fx+....+K=0

因为n维空间对应的是n维坐标系，仅仅用x、y、z几个字母较难表示

所以此处用x、x、x、...、x来表示n维坐标系，各个维度的系数此处也可以用w、w、w、...、w来表示

所以n维空间里面的超平面方程可以写成如下形式：wx+wx+wx+wx+...+wx+b=0。wx相乘可以看作是内积的相乘：

机器学习 - 算法 - SVM 支持向量机-LMLPHP

可以将x看作w，y看作x则上面超平面方程就变成了：[w,x]+b = 0 ，即wx+b=0。所以，样本空间中，任何一个超平面都可以用方程如下方程表示：WX+b=0。

其中，W=(w,w,w,...,w)为法向量，b为位移项可以认为是截距，该超平面可以唯一的由此方程决定

SVM 目标函数

数据标签定义

数据集

机器学习 - 算法 - SVM 支持向量机-LMLPHP

Y 为样本的类别 (标签), X 为每一个样本数据

这里依旧是个二分类的问题将 Y 进行了两个区间的判断

　　X 为正例的时候 Y = +1

　　X 为负例的时候 Y = -1

和回归的时候使用的 0 / 1 不同, 这里使用的是 +1 / -1

决策方程

机器学习 - 算法 - SVM 支持向量机-LMLPHP

在基于之前 y = wx+b 的情况下多加了一个 Φ

这里的 Φ 是对 x 做了一个转换, 后面会解释

机器学习 - 算法 - SVM 支持向量机-LMLPHP

对于预测结果可以进行简化, 不论 Xi 正例还是负例, yi * y(Xi) > 0 恒成立

优化目标

通俗解释

找到一个线 ( w, b ) 使得距离该线的最近的点 (雷区) 能够最远

优化目标即是如何让这个距离尽可能靠近最远, 或者足够远

将点到直线的距离化简得

机器学习 - 算法 - SVM 支持向量机-LMLPHP

由于 yi * y(Xi) > 0 , 所以将绝对值展开依旧成立

机器学习 - 算法 - SVM 支持向量机-LMLPHP

本来机器学习 - 算法 - SVM 支持向量机-LMLPHP 是恒大于 0 的, 这里使用放缩变换将其用某种手段让他恒大于 1

然后下面的优化目标中的正好对这里进行求最小值, 恒大于 1 的最小值那最小值自然就是 1 了约分掉了这块内容

由此将目标这样化简成机器学习 - 算法 - SVM 支持向量机-LMLPHP

目标函数

当前目标

　　机器学习 - 算法 - SVM 支持向量机-LMLPHP 约束条件 - 任何 w 都需满足

常规套路

　　求解极大值转换成极小值问题

　　- 求 1/w 的最大值就是求 w 的最小值

　　- 当然求 w 的最小值也是一样的

　　- ||w|| 看着碍眼, 总之是正数, 那就用 w 代替

　　- 为了方便后面的求导, 多加个常数项 1/2 方便消去

　　- 最终的结果优化为机器学习 - 算法 - SVM 支持向量机-LMLPHP

如何求解 - 拉格朗日乘子法

机器学习 - 算法 - SVM 支持向量机-LMLPHP

直接将我们的式子和约束带进转换即可, 这里多加个一个 α 的对每个 x 的系数

最终目标函数

机器学习 - 算法 - SVM 支持向量机-LMLPHP

SVM 目标函数求解

根据对偶性质 KKT 可以进行一下的推导

机器学习 - 算法 - SVM 支持向量机-LMLPHP

KKT 　　大概意思就是说在拉格朗日乘子法中

先求解最大值然后求解最小值这个过程可以转换成先求解成最小值再求解成最大值

在这儿我们先求解这个函数的极小值，首先在L(w,b,α)函数中对w，b分别求偏导

由于需要求解极值点，令其偏导等于0

机器学习 - 算法 - SVM 支持向量机-LMLPHP

可以看出w与α这个变量有了关系，就是说求出α也就求出了w。然后继续接下来的求解，将上面求出的两个式子带回原式。

机器学习 - 算法 - SVM 支持向量机-LMLPHP

然后接下来求解α的极大值

机器学习 - 算法 - SVM 支持向量机-LMLPHP

求解一直以来都是较难的事情, 这里先看一个简单的 SVM 的求解实例参考

简单示例

上面其实已经得出最终的表达式了，下面我们会根据一些具体的点来求解α的值

数据：3个点，其中正例 X(3,3) ，X(4,3) ，负例X(1,1) 如下图所示

机器学习 - 算法 - SVM 支持向量机-LMLPHP

分别对α和α求偏导，偏导等于0可得： α=1.5，α=-1（并不满足约束条件α >= 0，i=1,2,3 ）

所以这时求出来的α的值是无效的，那这个时候 α 的解应在边界上，也就是说要么 α=0，要么 α=0，再代入上式然后求偏导看下

机器学习 - 算法 - SVM 支持向量机-LMLPHP

(这儿经过我的计算发现α似乎等于正的2/13，应该是教程有些小问题，猜测可能是上式由α+α=α化简这儿出了点小问题，但是对于答案似乎影响不大) ，

所以经过计算最小值在 (α0.25,α20,α30.25) 处取得

机器学习 - 算法 - SVM 支持向量机-LMLPHP

上面的平面方程其实就是代表直线方程，也就是决策边界的方程。

支持向量机名词解释

以上就是我们对 SVM 的一次实际求解过程

注意公式中

机器学习 - 算法 - SVM 支持向量机-LMLPHP

可以看出只要 α 为 0 , 则结果一定为 0, 因此为 0 的点就是无意义的点

在图中展示就是说 x2 所在的点, 也就是不在觉得边界的点, 这些点对我们画出方程是无价值的也就是非支持向量

而这也就是支持向量机的说法由来, 决策边界的生成是由决策边界上的有价值的点支撑起来的也叫做支持向量

机器学习 - 算法 - SVM 支持向量机-LMLPHP

于此原理, 对于结果有影响的点是支持向量, 哪怕加入多少非支持向量, 对结果都不会有意义

软间隔 soft-margin

松弛因子

机器学习 - 算法 - SVM 支持向量机-LMLPHP

目标函数

机器学习 - 算法 - SVM 支持向量机-LMLPHP

C 趋近很大的时候, 为了满足式子最小, 那就只能要求松弛因子 ε 越小, 即越严格, 反之越宽容

解法

引入新的参数后的解法

机器学习 - 算法 - SVM 支持向量机-LMLPHP

SVM 核变换

低纬不可分问题

假设在低纬度的时候发现很难分, 比如下图二维中是一条非线性的曲线来划分

这时候可以考虑转换到高纬来尝试, 比如转换为下图中三维的中的平面

机器学习 - 算法 - SVM 支持向量机-LMLPHP

核变换原理

低纬不可分问题映射到高纬后通过一种变换方式从而实现更直观更效率的划分

原理阐述的简单示例

机器学习 - 算法 - SVM 支持向量机-LMLPHP

我们为了一个简单直观的非线性的问题简化, 如果将维度上升到过分大的程度, 就会导致计算量暴增

因此上升到什么样的维度, 以及什么维度又是在可解范围内的程度才是最重要核心的问题

但是还有一个发现就是, 高纬度的内积和低纬度的内积是有一定关系的

先做内积在做映射和先做映射在做内积的结果是一致的

机器学习 - 算法 - SVM 支持向量机-LMLPHP

因此实际操作的时候并没有真的去高纬中进行复杂的内积计算

只需要在低纬中计算内积之后也映射到高纬的值即可

核函数

核函数就是在公式中的机器学习 - 算法 - SVM 支持向量机-LMLPHP 的具体操作, 通常使用的是高斯核函数

公式机器学习 - 算法 - SVM 支持向量机-LMLPHP

体现效果如下图中所示

机器学习 - 算法 - SVM 支持向量机-LMLPHP

SVM 总结梳理

支持向量机被说为机器学习中最复杂的算法, 真正理解起来最好还是从物理意义上去着手

物理意义 - 解决的问题是什么 ?

找出最胖的决策边界, 越宽越好

怎么决定宽度?

距离计算, 从而引出距离计算公式

机器学习 - 算法 - SVM 支持向量机-LMLPHP

优化目标是什么?

找到一条线 (w, b) 使得离该线的点越远越好 (从而更宽)

进一步的化简得到机器学习 - 算法 - SVM 支持向量机-LMLPHP

转换成数学表达 - 目标函数 ?

利用放缩, 用 |Y| >= 1 机器学习 - 算法 - SVM 支持向量机-LMLPHP 带入到优化目标中

约掉了右边的式子后就只需要考虑机器学习 - 算法 - SVM 支持向量机-LMLPHP 从而得到了

目标函数机器学习 - 算法 - SVM 支持向量机-LMLPHP

以及一个约束条件机器学习 - 算法 - SVM 支持向量机-LMLPHP

如何求解目标函数 ?

第一步 - 　　将极大值问题先转换成极小值问题,

第二步 - 　　然后应用 拉格朗日乘子法

　　在拉格朗日乘子法中将求 w,b 的问题转换成了求 α 的问题

　　　　求 α 的时候利用分别求偏导在求解, 利用到了拉格朗日乘子法中某些特质

　　　　利用支持向量进行比对 (不在最边界的点就是无价值的点了) 从而求出 w, b

这里也点出了支持向量机的名字由来, 所谓支持向量是什么, 意义如何等

特殊问题处理 ?

过耦合问题

引入了松弛因子, 然后利用 C 的大小让计算更加严格或者宽松

再多一个约束条件的情况下, 再次求解也是类似的操作

低纬不可分问题

利用核函数变换为高纬度中去解决问题

需要注意并么有真的在高纬中进行复杂计算