详解讲解SVM，从简单是直观理解，到函数间隔，几何间隔，以及推到优化。
版权所有,苳载·复制,请标明出处2017年12月13且 h(x)=g(0. X),xo=1,XER"T 将表达是展开 b(X)=g(·X+b,W=[O,2,2On]b= 函数间隔: 首先定义一个最大间隔的超平面函数 W7.x+b=0 对于超平面的理解如图2 X2 ★ ★ ★ 0 超平面 图2 如图2,在特性空间为2维是,超平面就是一条直线(在特征空间为三维是超平面就是 个面等),可以根据高中时学丬到的规划知识,落到直线上的点,带入超平面方程,也就 是方程左侧等于0,如果将红色的样本点带到超平面方程,方程左侧就大于0,绿色的样本 带入超平面方程,方程左侧小于0;定义红色样本为正类,绿色样本为负类,就可以用超平 血将样本分类 现在我们定义一个函数间隔,函数间隔没有几何意义,不要见到间隔这个字眼就联想到 儿何的问隔,函数间隔就一个函数定义,定义如下 Y0(W·X(+b 对于这个定义: If: y=1. want w.x+b>>0 Y=-1,wmW·x0+b<<0 那么当Y(W1·X+b)>0∈(X(),)就定是正确分类。 对于整个训练集合的函数间隔定义为: i=mini( 第3页 版权所有,苳载·复制,请标明出处2017年12月13且 函数间隔选择的是样本中到超平面间隔中最小的一个,即最坏的情况下,我们希望最坏 的间隔最大,如图3所示,主要保证了样本中最小的间隔正确,就可以正确分类,另外最大 间隔算法(SⅥM的前身)就是要找一个超平面,这个超平面到两类样木点在距离最大,在 图3中可以许多超平面可以将两类分开,但是只要蓝色粗线才是最好的超平面,蓝色粗线才 能保证这样分类两类之间的间隔最大 2 ★ 超平面 ★ 图3 对超平面来说W7·X+b=0,将W和b同时放缩K倍并不会改变这个超平面,对于函 数间隔来说,他没有具体几何意义,将W和b同时放缩K倍没有任何意义,只是函数间隔 的值也放缩K倍而已。于是我们就可以将W加一个正则化,其实W是超平面的一个法向量 正则化后W=1,W就变一个单位向量。超平面是不会发生变化的,将超平变换成 T X+m=0,函数间隔就变换成=y0r b x+m),函数间隔先说到这个。 几何间隔: 先看图4 第4页 版权所有,苳载·复制,请标明出处2017年12月13且 ★ ★ ★ 超平面 ★ 图4 设点(x",y0)到点p的儿何间隔是",那么p点就是x0-,mm,因为p点是在超面 上的,将p点带入超平面W·X+b=0得到: W(Xo )+b=0 可以推出:7x+b=1W,W W 1,于是 w? b 此公式代表的就是几何间隔,不过该间隔是有正负的,几何上是间隔都是正数,当点是 正类是此间隔就为正,当为负类是此间隔就是负值,所以 真实的几何间隔为: WX 几何间隔与函数间隔非常相似,只是对超平面法向量标准化了,函数间隔也只是成比例 的放缩了。我们希望能够找到一个合适的超平面能够合适将类别分开,所以我们希望是得到 几何间隔最大化的超平面,由于对W和b成比例放缩是不会改变超平面的位置,所以就不会 改变几何间隔。 从上述挂到可以得到两个简单结论 如果|‖=1,函数间隔等于几何间隔 2、更一般的,几何间隔等于函数间隔除以 对于整个训练集合,几何问隔为 l=mIn l 第5页 版权所有,苳载·复制,请标明出处2017年12月13且 对于为何选择集合中最小的几何间隔,解释与函数间隔一致,不再赘述。 最大间隔分类器(SVM的前身): 最近间隔分类器的目标是寻找到一个合适的超平面,将类别分开。从图4可以看到,如 果不考虑b的情况下,与蓝色粗线平行的直线都是可以很好的分开,当确定了b是就是取这 些平行直线中间一条就巧好将类别分开,因此目标函数就是寻找几何间隔最大的那个平面。 max(= max(min(e ) W·x)≥ 优化最大间隔分类器 优化最大间隔分类器的目标就是选择ω,b使几何间隔最大化,这有两种表示形式: 形式一: max(o) C, O. S r ro +b)≥t 形式 maX Lo.b S.Y(W7.Y+b)≥ 由于成比例的放缩O,b不会改变几何间隔,也就是不会改变优化的目标,可以令 k=,那么新的函数间隔就变为: =k·=1=Y(kWX(+b) 从这里对符号进行重新定义,如下,左侧是上述使用的符号,由此是变换后的符号,也 就是用变换后的符号表小变换前的符号: kW→W hb→b 变换后,目标函数为: 第6页 版权所有,苳载·复制,请标明出处2017年12月13且 max( max (r) 1. 0. b S.Y(W.x"+b)>1 对于上述的目标函数,是最大化个实数的倒数,可以转换求这个实数的最小的平方 mint S.Y(W7.x+b)>1 对于这个目标函数是一个典型的凸函数,在加上约束条件对解空间约束。如图5所示, 可以用梯度下降得到优化。 图5 将到这里是对最大间隔分类器的研究,最大问隔分类器是SⅥM的前身,如果用上述的 推到得到的分类器并没有体现出这个分类器的优势,性能和感知器,逻辑分类器都是人同小 意。SⅥM的精髓是对最大间隔分类器的另·种优化的推到,从而是最大间隔可以将核的方 法引入到最大间隔分类器。也就是sVM。在开始学习sM的求解优化前需要先理解一些微 积分的知识 拉格朗日乘法 现在开始学习微积分的相关知识,先打前面的算法忘记!!!! 拉格朗日乘法的定义 min (f)) (W)=0,j=1,2, 写成拉格朗日表达式: (W,B)=f(W)+∑(W) 求解目标函数最优值: 第7页 版权所有,苳载·复制,请标明出处2017年12月13且 O W 0=0,求W与B 如果W”是最优值,必要条件是:存在尸使得O ae 0 aw aB 另外一种形式: min(f()) S.g:(W)≤0,i=1,2,3 h(W)=0,=1,2,3. 拉格朗日表达式: (W,a,B)=f(W)+∑ag(W)+∑月(W) Det e, (w)=max e(w, a, B) B Def P=min max(, a,B)=mine,w) 对于 :g,(W)>0→6(W)→∞ :h(W)≠0→6n() otherwise 0)=f( 即当满足约束条件时最大化拉格朗日表达是的方式就是让拉格朗日乘数项的求和值等 那么 0(W)满足约束条件 不满足约束条件 所以 min,、(W)=原始问题 对偶问题 定义个对偶函数bD(a,B),以拉格朗日乘数为变量的函数,W不为变量 第8页 版权所有,苳载·复制,请标明出处2017年12月13且 0,(a, B)=min ((w, a, B) 对偶问题目标函数: 0= max mine(w,a, B)=max bp(a, B) >0H 对此原始问题p与δ”,只是max与min互换了。 实际证实了,通常是:δ≤p台 max min(…)≤ min max() 事实证明了在某些特殊的情况下,这两个优化问题会取相同的值,这个特性是情况就是KKT 条件( Trush-Kuhu- Sucker)。利用与对偶值相等的特性,可以将原来问题转换成新的形式, 会有更多的特性利用,方便求解。 对于f是个凸函数,如图6,假设h是放 射函数,意味着 h, ( W)=a,w+b g;1[WS.ⅵig(W)≤0]意识就是满足 所有的约束条件 那么:W,a",B"使得a,B是拉格朗日 乘数对于对偶问题的解,and p^=δ^=(W",a,β,换句语说,既可以求解原始问题,也可以求解对偶问题,结果都 可的代相同的解。 参数KKT互补条件(5个) (W,a,B)=0; (W,a,B)=0 C g(W)=0 g;(W)≤0, fa1>0→g(W)=0 通常a;≠0令g(W)=0 fg,W)=0就称为一个活动约束 第9页 版权所有,苳载·复制,请标明出处2017年12月13且 SVM的拉格朗日对偶推导 在拉格朗日乘数有两组a,和B,实际在SM问题中,我们只需要一组∝1。当在学习KKT 条件是,我们用W表示原始问题的参数,希望最小化f(W),而在SVM问题中,有两组参数 W和b 目标函数 Y(WX+b≥1t=1,2,3 St g(W,b)=-Y(WX+b)+1≤0 将最大间隔目标函数写成拉格朗日形式: (W,b,a)=-∑a(YWx.x+b)-1)(*-1) 对应的对偶函数 Op(a)=min((w, b, a) W. b 对对偶函数以a为自变量使其最大的形式 8=max bp(a)=max min(w,b, a) 0 w h 为了求得对偶函数,对W和b求偏导是等于0时,拉格朗日算子求的最小,也就是对 偶函数 Vn(W,b,a)=F一∑a0x=0→W=∑aYX(*-2) W,b,a)=∑a0 r(i) C,y=0(* 3) 将(*-2),(*-3)带入到(*-1)中,我们就可以得到拉格朗日算子: W,b2a)=-∑a(Ywx0 =2∑yyY<X,X> ∑∑Yyaa,<x,X0>+∑ ∑a1-∑∑ X.X 最大间隔的拉格朗日算子就变成了一个以a为变量的函数 对偶问题就变成了: 第10页