机器学习 - SVM-1

2019-08-12 Views 机器学习1328字6 min read
featureimg

支持向量机(Support Vector Machine, SVM)是一类按监督学习(supervised learning)方式对数据进行二元分类(binary classification)的广义线性分类器(generalized linear classifier),其决策边界是对学习样本求解的最大边距超平面(maximum-margin hyperplane)。

正文

概念

乍一看上面的内容很抽象,什么二元分类,最大边距超平面……下面让我们来剖析一下这些概念。
如果要对一些数据(比如说点)进行分类,我们可以构造一条直线简单的把数据分成两半。这条直线就叫做分隔超平面

hyper-plane - 1

这个分隔超平面旁边的点到超平面的距离就是间距,离超平面最近的点就叫做支持向量。SVM的算法原理就是找到一种分类方式,让支持向量到超平面的距离达到最大,因为这样就能很好的分类数据。


既然是要让间距达到最小,那么首先我们来看怎么计算间距。在二维空间里我们可以用w1x1+w2x2+b=0来描述一条直线。为了把这个扩展到n维空间,我们采用矩阵的形式来描述这个超平面wTx+b=0

hyper plane - 2

同时我们可以假设我们需要计算的支持向量在wTx+b=1上
根据点到直线距离公式

d=Ax0+By0+CA2+B2d=\left| \frac{Ax_{0}^{}+By_{0}^{}+C}{\sqrt{A_{}^{2}+B_{}^{2}}} \right|

我们可以得到

d=wTA+bwd=\frac{w_{}^{T}A+b}{\lVert w \rVert}

把wTx+b=1代入得到

d=1wd=\frac{1}{\lVert w \rVert}

所以我们要使得支持向量到分隔超平面得距离最大就要使得||w||最小。


计算完了间距,就要了解什么是正确的把数据进行分类,所谓正确进行分类指的就是SVM中的约束条件(如果划分之后超平面无法正确分类那就没有意义了)。
我们可以看到之前所做的假设,分隔超平面两端的支持向量分别分布在wTx+b=-1和wTx+b=1上。所以很容易知道,我们分类要达到的效果要么就是wTx+b≥1,要么就是wTx+b≤-1。所以我们可以用-1表示一种类别的值,1表示另一种类别的值(上图中的圆形为-1,方形为1)。所以我们就可以得到下面的约束条件表达式

y(i)(wTx(i)+b)1y_{}^{\left( i \right)}\left( w_{}^{T}x_{}^{\left( i \right)}+b \right) \ge 1

其中y{-1,1},因为当y为-1时,满足的条件是wTx+b≤-1,所以两个相乘负负得正大于1;同理也可以理解为什么y=1时也是大于1。
所以总结一下上面的所有内容:用SVM进行数据分类就是在满足约束条件

y(i)(wTx(i)+b)1y_{}^{\left( i \right)}\left( w_{}^{T}x_{}^{\left( i \right)}+b \right) \ge 1

下,求解d最大值。

线性不可分

SVM - Relaxation factor

针对线性不可分的数据,上面讲到的方法就失效了。所以我们引入了一个叫做松弛系数的概念。松弛变量其实就是用来放宽用来分类点的条件,经过改造后的优化函数变成:

argmin w2+Ri=1mεiarg\min\text{\ }\lVert w_{}^{2} \rVert +R\sum_{i=1}^m{\varepsilon _{i}^{}}

约束条件如下:

y(i)(wTx(i)+b)1εy_{}^{\left( i \right)}\left( w_{}^{T}x_{}^{\left( i \right)}+b \right) \ge 1-\varepsilon

其中m为样本个数,ε是松弛系数,R为算法参数
从约束条件公式我们可以看到,我们放宽了约束条件,从而让有一些点可以到达wTx+b=1和wTx+b=0之间(或者wTx+b=-1和wTx+b=0之间)。算法参数R则表示对违反最大问距规的样本的“惩罚”力度。当R很大时,我们的目标函数对违反最大问距规则的点的“惩罚力度”将变得很大;R较小时,那些违反最大问距规则的样本,其“忖出的代价”不是特别大。换句话说,也就是R越大,因为要让成本越小,我们就很趋近于少犯错误,但是容易造成数据过度拟合(因为过度细分了);R较小就有可能造成欠拟合现象。

SVM - optimization function - 2

我们可以把

y(i)(wTx(i)+b)y_{}^{\left( i \right)}\left( w_{}^{T}x_{}^{\left( i \right)}+b \right)

作为横坐标,cost作为纵坐标来画一张图。
可以看到,当

y(i)(wTx(i)+b)1y_{}^{\left( i \right)}\left( w_{}^{T}x_{}^{\left( i \right)}+b \right) \ge 1

时,成本为0;当≤1时,成本线的斜率为R。


因为SVM内容较多,所以将内容分成两部分写


注:如果文中有什么问题,欢迎在评论区指出;有不懂的也可以在评论区提问哦!


References:

  1. https://baike.baidu.com/item/支持向量机/9683835
  2. https://blog.csdn.net/DP323/article/details/80535863
  3. 《scikit-learn 机器学习:常用算法原理及编程实战》- 黄永昌

logo   WRITTEN BY:Serence

一个程序员和文艺青年的博客!

本文章采用CC BY-NC-SA 4.0进行许可。转载请注明出处!

上一篇

美化博客


下一篇

Night at HongKong