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 条评论
登录 后参与评论

相关文章

来自专栏量子位

提高驾驶技术:用GAN去除(爱情)动作片中的马赛克和衣服

作者:達聞西 量子位 已获授权编辑发布 作为一名久经片场的老司机,早就想写一些探讨驾驶技术的文章。这篇就介绍利用生成式对抗网络(GAN)的两个基本驾驶技能: 1...

3626
来自专栏机器学习和数学

[高大上的DL] BEGAN: Boundary Equilibrium GAN

自己基本翻译了BEGAN,错误在所难免,希望有大神可以给我留言,我们也可以交流一下训练的一些事情。讲道理,我特别希望有人给我留言,不然我感觉我每天就是在自嗨!囧...

2873
来自专栏机器学习之旅

基于Tensorflow的神经网络解决用户流失概率问题

注意,已经很多很多人和我说最后的loss不变,大家的数据都不一样,如果发现loss不变请降低learning_rate = 1e-6,就可以解决,还有问题的话,...

643
来自专栏AI科技评论

干货 | 浙大博士生刘汉唐带你回顾图像分割的经典算法

AI科技评论按:图像语义分割是 AI 领域中一个重要的分支,是机器视觉技术中关于图像理解的重要一环。近年的自动驾驶技术中,也需要用到这种技术。车载摄像头探查到图...

3495
来自专栏磐创AI技术团队的专栏

使用Keras进行深度学习:(三)使用text-CNN处理自然语言(上)

上一篇文章中一直围绕着CNN处理图像数据进行讲解,而CNN除了处理图像数据之外,还适用于文本分类。CNN模型首次使用在文本分类,是Yoon Kim发表的“Con...

5518
来自专栏CVer

[计算机视觉论文速递] 2018-05-08

[1]《DCAN: Dual Channel-wise Alignment Networks for Unsupervised Scene Adaptation...

921
来自专栏AI科技评论

学界 | ECCV 2018 行为识别论文笔记之多纤维网络

AI 科技评论按:本文为上海交通大学林天威为 AI 科技评论撰写的独家稿件,未经许可不得转载。

811
来自专栏新智元

谷歌发布迄今最大注释图像数据集,190万图像目标检测挑战赛启动

1969
来自专栏小小挖掘机

推荐系统遇上深度学习(一)--FM模型理论和实践

1、FM背景 在计算广告和推荐系统中,CTR预估(click-through rate)是非常重要的一个环节,判断一个商品的是否进行推荐需要根据CTR预估的点击...

1.1K10
来自专栏数值分析与有限元编程

共旋坐标法( 三 ) 算例

为计算方便,根据对称性取半结构,且刻意将初始刚度设为1,便于观察。取半结构之后,自由度只有一个,用Excel也能算了。当外荷载较小时,不会出现“跳跃”...

761

扫码关注云+社区