svm 之 线性可分支持向量机

定义:给定线性可分训练数据集,通过间隔最大化或等价的求解凸二次规划问题学习获得分离超平面和分类决策函数,称为线性可分支持向量机。

目录:

       • 函数间隔

       • 几何间隔

       • 间隔最大化

       • 对偶算法

1、函数间隔

考虑分类算法的两个方面:确信度 + 正确性

确信度:用点到分离超平面的距离表示,间接表示为$w ⋅x_i+b$,分类的结果有多大的自信保证它是正确的;

正确性:$y_i$  与 $w ⋅x_i+b$的符号是否一致,表征分类是否正确;

结合以上两点,

某一实例点的函数间隔的定义即:$γ ̂_i= y_i (w⋅x_i+b)$;

训练数据集的函数间隔定义为:$γ ̂*=min\quadγ ̂*_i$;

确信度:$w⋅x_i+b$可以间接的表示点到超平面的距离,距离越小,说明确信度越低,反之;

正确性:当 $y_i$  与 $w⋅x_i+b$ 的符号一致时,函数间隔为正,此时分类是正确的,反之,分类错误;

2、几何间隔

但是.........

当w,b成倍的变化,变成了ℷw,ℷb时,超平面没有发生变化,但是函数间隔却变化了 ℷ 倍,基于此,

某一实例点的几何间隔就被定义为:$γ_i=y_i\frac{(w⋅x_i+b)}{‖w‖}$;

训练数据集的几何间隔定义为:$γ=min⁡\quadγ_i$;

几何间隔不会随着w和b的比例变化而同比例的变化;

而且,$\frac{(w⋅x_i+b)}{‖w‖}$    也是点到超平面真正的距离(不再是间接的表示了),所以几何间隔其实是带符号的距离;

几何间隔和函数间隔之间的关系:$γ=\frac{γ^*}{‖w‖}$

3、间隔最大化

线性可分支持向量机的目的是:正确的分离超平面 + 最大的几何间隔

最大的几何间隔直观的解释:以最大的确信度分离数据集,即使是最难分的实例点也可以被分的很好(大的确信度);

最大化几何间隔:

$max\quadγ$  ;             

$s.t.\quad\frac{(y_i (w⋅x_i+b))}{‖w‖} ≥γ ,\qquad i=1,2……N$ ;

带入函数间隔:

$max\quad\frac{γ^*}{‖w‖}$ ;           

$s.t.\quad y_i (w⋅x_i+b)≥γ^*, \qquad  i=1,2……N$;

考虑上优化问题,可知$γ^*$ 的取值不会影响优化问题(当w和b成比例变化时,$γ^*$也会成比例变化,优化问题不变),可取$γ^*$ 为1,又可知最大化 $\frac1{‖w‖}$   等价与最小化 $\frac1{2} ‖w‖^2$,故优化问题就可以写成一个凸二次规划问题:

$min\quad\frac⁡{1}{2} ‖w‖^2$ ;      

$s.t. \quad y_i (w⋅x_i+b)≥1 ,\qquad i=1,2…N$;

算法:线性可分支持向量机学习算法 -- 最大间隔算法

输入:训练数据集 $T{(x_1,y_1 ),(x_2,y_2 ),…,(x_n,y_n )}  ,  x∈R^n  ,  y∈ \left \{ +1,-1 \right \} $;

输出:分离超平面和分类决策函数;

(1)构造并求解凸二次规划问题:                 

$min⁡\quad\frac1{2} ‖w‖^2$ ;           

$s.t.\quad y_i (w⋅x_i+b)≥1 , \qquad i=1,2…N$;

得到问题的解:$w^∗, b^∗ $  ;

(2)得到分离超平面:$w^∗⋅x+b^∗=0$ ;

            分类决策函数:$f(x)=sign(w^∗⋅x+b^∗ )$;

支持向量:距离超平面最近的实例点,(那些最难分类的实例点)

间隔边界:

$H_1  : w⋅x+b=1$;

$H_2  : w⋅x+b=−1$;

4、对偶算法

根据拉格朗日对偶性,求对偶问题即可求原始问题。对偶问题一般更容易求解。

构建拉格朗日函数:$L(w,b,α)=\frac1{2} ‖w‖^2−∑α_i y_i (w⋅x_i+b)+∑α_i $;

根据拉格朗日对偶性,原始问题的对偶问题是极大极小问题:max⁡  min⁡  L(w,b,α)  

(1)求解极小问题 ⁡min⁡ L(w,b,α)   分别对w和b求导:

     $\frac{\partial L(w,b,\alpha)}{\partial w}=w-\sum_{i=1}^N\alpha_iy_ix_i=0$           ;            $\frac{\partial L(w,b,\alpha)}{\partial b}=-\sum_{i=1}^N\alpha_iy_i=0$

得到:

$w=\sum_{i=1}^N\alpha_iy_ix_i$;

$\sum_{i=1}^N\alpha_iy_i=0$;

带入到极小问题中:

$min\quad L(w,b,α)=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot{x_j})+\sum_{i=1}^N\alpha_i$

(2)求解极大问题:max⁡ min⁡ L(w,b,α) 

$max\quad-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot{x_j})+\sum_{i=1}^N\alpha_i$               

$s.t.\quad\sum_{i=1}^N\alpha_iy_i=0 , \alpha_i\geqslant 0,i=1,2,...,N$

等价于:

$min\quad\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot{x_j})-\sum_{i=1}^N\alpha_i$               

$s.t.\quad\sum_{i=1}^N\alpha_iy_i=0 , \alpha_i\geqslant 0,i=1,2,...,N$

我们的原始问题是: 

$min\quad \frac1{2} ‖w‖^2$    ; 

$s.t. \quad y_i (w⋅x_i+b)≥1$;

原始问题满足定理C.3(统计机器学习附录)的条件,故可以通过求解对偶问题来求解原始问题;

定理:设$α^∗$ 是对偶问题的解,则存在$α_j>0$,按下式求原始问题的解:

$w^∗=∑α_i^∗ y_i x_i$;

$b^∗=y_j−∑α_i^∗ y_i (x_i⋅x_j )$;

证明:

根据KKT的互补条件:$α_i c_i (x)=0,若α_j>0,则c_j (x)=0;y_j (w⋅x_j+b)−1=0≫  y_j^2 (w⋅x_j+b)−y_j=0≫b=y_j−w⋅x_j$

至此,就得到了分离超平面和分类决策函数。

算法:线性可分支持向量机 -- 对偶学习算法

输入:训练数据集 $T{(x_1,y_1 ),(x_2,y_2 ),…,(x_n,y_n )}  ,  x∈R^n  ,  y ∈ \left \{ +1,-1 \right \} $ ;

输出:分离超平面和分类决策函数;

(1)构造并求解原始问题的对偶问题:

$min\quad\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot{x_j})-\sum_{i=1}^N\alpha_i$               

$s.t.\quad\sum_{i=1}^N\alpha_iy_i=0 , \alpha_i\geqslant 0,i=1,2,...,N$

得到解为$α^∗$;

(2)根据对偶问题的解求原始问题的解:

$w^∗=∑α_i^∗ y_i x_i$;

$b^∗=y_j−∑α_i^∗ y_i (x_i⋅x_j )$;

(3)得到分离超平面和分类决策函数;

支持向量:$α_i^∗>0$的实例点,

根据KKT互补条件,对于$α_i^∗>0$的实例点,$y_j (w⋅x_j+b)−1=0 ≫ w⋅x_j+b=±1$  ,即实例点在间隔边界上,这个定义和之前的定义是一致的;

至此,线性可分支持向量机完结。

但是...........

线性可分支持向量机(硬间隔最大化)针对的是线性可分训练数据集,然而,现实世界里有很多数据集是线性不可分的(样本数据中有噪声或特异点),这种情况下改怎么办?

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏应兆康的专栏

AdaBoost

671
来自专栏决胜机器学习

深层神经网络参数调优(五) ——超参数调试、batch归一化、softmax回归

深层神经网络参数调优(五) ——超参数调试、batch归一化、softmax回归 (原创内容,转载请注明来源,谢谢) 一、超参数调试 1、超参数 超参数是不直...

4298
来自专栏计算机视觉战队

详聊CNN的精髓

现在的深度学习发展速度已经超出每个人的想象,很大一部分人只是觉得我用他人的框架去实现自己的目的,并且效果很好就可以了,这也是现在一大部分的一个瓶颈。曾经有一个老...

3625
来自专栏Petrichor的专栏

目标检测: RCNN系列

传统的detection主流方法: DPM(Deformable parts models), 在VOC2007上能到43%的mAP,虽然DPM和CNN看起...

1155
来自专栏机器学习原理

梯度下降算法

最优化算法的一种,解决无约束优化问题,用递归来逼近最小偏差的模型。 关于梯度的概念可参见以前的文章: 从方向导数到梯度 梯度下降法迭代公式为: ...

32411
来自专栏机器学习、深度学习

跟踪算法基准--Tracking the Trackers: An Analysis of the State of the Art in Multiple Object Tracking

Tracking the Trackers: An Analysis of the State of the Art in Multiple Object Tr...

2526
来自专栏机器学习原理

深度学习(6)——卷积神经网络cnn层级结构CNN特点卷积神经网络-参数初始化卷积神经网络过拟合解决办法

1961
来自专栏ATYUN订阅号

【学术】为回归问题选择最佳机器学习算法

AiTechYun 编辑:xiaoshan 任何类型的机器学习(ML)问题,都有许多不同的算法可供选择。在机器学习中,有一种叫做“无免费午餐(No Free L...

2656
来自专栏计算机视觉战队

详聊CNN的精髓

现在的深度学习发展速度已经超出每个人的想象,很大一部分人只是觉得我用他人的框架去实现自己的目的,并且效果很好就可以了,这也是现在一大部分的一个瓶颈。曾经有一个老...

3555
来自专栏Pytorch实践

Pytorch实现CNN时间序列预测

本公众号曾经推出过PyTorch实现的LSTM时间序列预测,并开源了其源码。细心的童鞋可能发现了,我之前使用的LSTM是生成式模型,而不是使用判别式进行预测。换...

7527

扫码关注云+社区