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

相关文章

来自专栏开发与安全

算法:AOV网(Activity on Vextex Network)与拓扑排序

在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们称之为AOV网(Activity on Vextex ...

2517
来自专栏学海无涯

Android开发之奇怪的Fragment

说起Android中的Fragment,在使用的时候稍加注意,就会发现存在以下两种: v4包中的兼容Fragment,android.support.v4.ap...

3155
来自专栏计算机视觉与深度学习基础

Leetcode 114 Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place. For example, Given...

1938
来自专栏聊聊技术

原 初学图论-Kahn拓扑排序算法(Kah

2878
来自专栏xingoo, 一个梦想做发明家的程序员

Spark踩坑——java.lang.AbstractMethodError

百度了一下说是版本不一致导致的。于是重新检查各个jar包,发现spark-sql-kafka的版本是2.2,而spark的版本是2.3,修改spark-sql-...

1200
来自专栏Hongten

ArrayList VS Vector(ArrayList和Vector的区别)_面试的时候经常出现

1692
来自专栏项勇

笔记68 | 切换fragmengt的replace和add方法笔记

1444
来自专栏后端之路

LinkedList源码解读

List中除了ArrayList我们最常用的就是LinkedList了。 LInkedList与ArrayList的最大区别在于元素的插入效率和随机访问效率 ...

19510
来自专栏alexqdjay

HashMap 多线程下死循环分析及JDK8修复

1K4
来自专栏赵俊的Java专栏

从源码上分析 ArrayList

1171

扫码关注云+社区