SVM原理分析

所需积分/C币:16 2018-03-20 18:24:25 503KB PDF
85
收藏 收藏
举报

SVM原理分析,讲解SVM当中的数学原理,支持向量机,嘿嘿。
m,b(//2(vx+b) arg maxI min +b in max L(u, a, 6) arg max min a. D 推论6.线性支持向量机基本型中描述的优化问题属于 mnn(a)+ma∑a9a)+∑ B,hilu ax, 6 二次规划问题,包括d+1个优化变量,m项约束 ∫o若满足约束 明.令 in f(u)+ 否则 minf(u),且u满足约束 其中,当;不满足约束时,即g1()>0,我们可以 (18 取c:=∞,使得c;9(u)=∞;当h;不满足约束 时,即l3(u)≠0,我们可以取月;=sign(1;(u)x,使 代入公式10即得 得月h(u)=∞.当t满足约束时,由于a;>0, g(u)≤0,则azsz(u)≤0.因此ag(u)最大值为0 3对偶问题 推论8(KKT条件)·公式1描述的优化冋题在最优值 处必须满足如下条件 现在,我们可以通过调用现成的凸二次规划软件包 ·主问题可行:92(u)≤0,h2()=0 来求解定理5描述的优化问题.不过,通过借助拉格朗 对偶问题可行:a;≥0; 日( Lagrang)函数和对偶(dual)问题,我们可以将问 ·互补松弛(comp! ementary slacken5:a;g(u)=0 题更加简化. 证明.由引理7可知,α必须满足约束,即主问题可 行.对偶问题可行是公式21描述的优化问题的约束项 3.1拉格朗∏函数与对偶形式 ax;g2(u)=0是在主问题和对偶问题都可行的条件下的 构造拉格朗日函数是求解带约束优化间题的重要最大值 方法 定义4(对偶问题)·定义公式19描述的优化问题的对 定义3(拉格朗日函数),对于优化问题 偶问题为 min f(u) (19 x min C(u, a 2 t.9(u)≤0,i=1,2, s.t.a;≥0,=1,2,…,m. h()=0,y=1,2 引理9.对偶问题是主( Dr"iral)问题的下界,即 定义其拉格朗日函数为 maxmin C(u, a, B)< min max c(u, a, B).(2 C(u,a,B)=f(x)+∑a9(a)+∑h1(u),(20 对任意(a′,), min, L(,’,() minu maxx,B C(u, a, B) G 其中a2≥0 maxa,a/ minu L(u,a',/)时,该式仍然成立,即 引理7.公式19描述的优化问题等价于 maxa,B minu C(u, a, B)< minu maxo, B C(u, a, B) 引理10( Slater条件).当主闩题为凸优化问题,即f min max I. O 2 和g;为凸函数,h;为仿射函数,且可行域中至少有 t >0,2=1,2 点使不等式约兔严格成立时,对偶问题等价于原闩题. 证明.此证明已超出木文范围,感兴趣的读者叮参考.代入公式10即得.其中,e;是第氵位置元索为1,其余 推论11.线性支持向量机满足 Slater条件 位置元素为0的单位向量.我们需要通过两个不等式约 束 a≤dm+1和cm+21≤dm+2来得到一个等式 证明.1和1-:(mz+b)均为凸函数 约束 3.2线性支持向量机对偶型 33支持向量 线性支持向量机的拉格朗日函数为 定理14(线性支持向量机的KKT条件)·线忙支持向 量机的KKT条件如下 C(, b, a) (1-y;(vc;+b).(25) 主问题可行 b)≤0 对偶问题可行:a;≥0 其对偶问题为 ·互补松弛:a1(1-y(rz+b)=0 max min5mtm+∑a:(1-m(mym;+b)(26)证明,令 s. t 1.2 g;(u):=1 定理12(线性攴持向量机对偶型).线忙支持向量机的 对偶问题等价于找到一组合适的参数α,使得 代入引理⑧即得. 定义5(支持向量).对偶变量Gz>0对应的样本 n2∑∑°aym吗∑1(2 引理15.线性支持向量机中,支持向量是距离划分超平 面最近的样本,落在最大间隔边界上 s. t Ceili=0 证明.由线性支持向量机的KKT条件可知,az(1 ≥0,2=1,2 y +b)=0.当a>0时,1-y(utaz+b) 即v(u+ 正明.因为公式26内层对(,b的优化属于无约束优 化问题,我们可以通过令偏导等于零的方法得到(,.b)定理16.支持向量机的参数(,b)仅由支持向量决定, 的最优值. 与其他样本无关 C 证明.由于对偶变量α;>0对应的样本是支持向量, =0 aiyi (28 aiis ac (29 m ∑0·x2+∑a 将其代入公式26,消去(v,b),即得. i: ai=0 讠:a:>0 推论13.线性支持向量杌对偶型中描述的优化问题属 ∑a:y (35) i∈SV 于二次规划问题,包括m个优化变量,m+2项约束 其中SV代表所有支持向量的集合.b可以由互补松 证明.令 弛松弛算出.对于某一支持向量c。及其标记y,由于 +b)=1,则 :=a,Q:=[vw;cr]lnm,t:=-1,(30) d;:=0,i=1,2 (31) y192 +1 32 实践中,为了得到对b更稳健的估计,通常使用对所有 :=-y1y t dmt (33 支持向量求解得到b的平均值. 推论17.线性支持向量机的假设函数可表示为 4.2核技巧 h(ax)=sign(2 a,,a;a+b 注意到,在支持向量机的对偶型中,被映射到 (37) 高维的特征向量总是以成对内积的形式存在,即 i∈SV φ(x)φ(x).如果先计算特征在R4空间的映射,再计 证明.代入公式35即得. 算内积,复杂度是O(d).当特征被映射到非常高维的空 间,甚至是无穷堆空间时,这将会是沉重的存储和计算 4核函数 负担 核技巧旨在将特征映射和内积这两步运算压缩为 至此,我们都是假设训练样本是线性可分的.即,存 步,并且使复杂度由O(d)降为O(d).即,核技巧希 在一个划分超平面能将属于不同标记的训练样本分开 望构造一个核函数A(m,y),使得 但在很多任务中,这样的划分超平面是不存在的.支持 K(x;,x)=d(x;)(x;) (40) 向量机通过核技巧( kernel tric)来解决样本不是线性 可分的情况[ 并且h(x;,)的计算复杂度是Od). 引理19.映射 4.1非线性可分问题 既然在原始的特征空间R4不是线性可分的,支持 向量机希望通过一个映射φ:R→R,使得数据在新 P: 3 H exp( 41 的空间R4是线性可分的 引理18.当d有服时,一定存在,使得样本在空闻R4对应于核函数 中线性可分 (x;,x3):=exp(-(x;-x)2) 证明.此证明已超出本文范围,感兴趣的读者可参考计 算学习理论中打散( shatter)的相应部分[1 令中(x)代表将样本m映射到R中的特征向量,k(x;,x)=exp(-(x2-x)2) 参数u的维数也要相应变为d维.则支持向量机的基 (-2)exp(-2)e(2x;x) 本型和对偶型相应变为 2\exp (2x:) mIn b 2 (38 s.t.v(or(x;)+b)≥1,i=1,2 exp(-C i kl p、 k:! (ai) (ai) 2∑∑a03())-∑01(3)4,3核函数选择 通过向高维空间映射及核技巧,我们可以高效地解 aigi=o 决样本非线性可分问题.但面对一个现实任务,我们很 a2≥0,i=1,2,…,m 难知道应该具体向什么样的高维空间映射,即应该选什 么样的核函数,而核函数选择的适合与否直接决定整体 其中,基本型对应于d+1个优化变量,m项约束的二的性能 次规划问题;对偶型对应于m个优化变量,m+2项约 表1列出了几种常用的核函数.通常,当特征维数d 束的二次规划问题 超过样本数m时(文本分类问题通常是这种情况),使 用线性核;当特征维数d比较小.样木数m中等时,使定理22(简化版表示定理).优化问题 用RBF核;当特征维数d比较小.样本数m特别大时, 支持向量札性能通常不如深度神经网络 min ∑(q(),v)+51p|2(53 mi-1 除此之外,用户还可以根据需要自定义核函数,但 的解ω是样本的线性组合 需要满足 Mercer条件同 定理20( Mercer条件).核函数K(c1,c,)对应的矩阵 ∑a(z:) 5 K:--[K(i,i)Imxm (44)证明.我们使用反证法.令 是半正定的,反之亦然 Φ:=[(m1)p(c 证明.因为核函数可表示为两向量内积:K 假设最优解不是样本的线性组合,那么 k(x;,x)=d(x)q(x),令 a,e≠0.w=重a+e, :=[φ(x1)d(x2)…(mm)∈Rxm,(45)其中,e不是样本的线性组合,即对任意φ(c), d(x;)e=0.因为 则K一更亚.对任意非零向量a, ((a),列)=(4a+e)o(;),y) Ka=a重重a=(重a)(小a)=|重a2≥0 (4a)φ(x1),y) (57) (46) |2=a|2+|e|2+2(a)e>‖中a|2,(5S 反之亦然. 新的核函数还可以通过现有核函数的组合得到.使 即更α比α有更小的目标函数值,说明ω不是最优解, 用多个核函数的凸组合是多核学习[⑨的研究内容 与假设矛盾.因此,最优解必定是样本的线性组合. 此外,原版表示定理适用于任意单调递增正则项 引理21.若h(a1,)是核函数,那么下列函数也是核9(v).此证明已超出本文范围,感兴趣的读者可参 函数 考[13 e11(;,cj)+c262(x,),c1,e2>0,(47 表示定理对损失函数形式没有限制.这意味着对许 1(;,c1)2(2,m;), 多优化问题,最优解都可以写成样本的线性组合.更进 48 一步,中(a)将可以写成核函数的线性组合 f(x1)1(m,m)f(a2) ∑ (a;,c (59) 证明.因为核函数可表示为两向量内积:k(x;,x)= i=1 d(;)φ(x) 通过核函数,我们可以将线性模型扩展成非线性模型. 这启发了一系列基于核函数的学习方法,统称为核方 c1F1(ax2,m)+c22(a2,y) Ve中1(x)√c1中1(c;) V2q2(z)√a中)法 (50) 1(i,Tj)2( 软间阝 vec(1(x)中2(x;))vec(1(1)2(x;)),(5 不管直接在原特征空间,还是在映射的高维空间, f(x1)1(x;,1)f(x2)=(f(x1)中(x1)((m)(ar) 我们都假设样本是线性可分的.虽然理论上我们总能找 到一个高维映射使数据线性可分,但在实际任务中,寻 找到这样一个合适的核函数通常很难.此外,由于数据 44核方法 中通常有噪声存在,一味追求数据线性可分可能会使模 上述核技巧不仅使用于支持向量机,还适用于一大型陷入过拟合的泥沼.因此,我们放宽对样本的要求,即 类问题. 允许有少量样本分类错误 Table1:常用核函数.除此之外,还有其他一些核函数,例如卡方核( chi squared kernel),直方图交叉核( histogram intersection kernel) 名称 形式 优点 缺点 线性核 有高效实现,不易过拟合 无法解决非线性可分问题 多项式核(xx;+0)n比线性核更一般,n直接描述了被映射空间的复杂度参数多,当n很大时会导致计算不稳定 RBF核exp 只有一个参数,没有计算不稳定问题 计算慢,过拟合风险大 5.1软间隔支持向量机基本型 更多的样本满足大间隔约束;当C比较小时,我们允许 我们希望在优化间隔的同时,允许分类错误的样本 有一些样本不满足大间隔约束 出现,但这类样本应尽可能少 证明.当样本满足约東〃((mz)+b)≥1时, v(d(a2)+b)≥1-5;对任意5≥0成立,而优 1D+C∑I(m≠sign(po(x;)+b)(60 化目标要最小化5,所以ξ=0.当样本不满足约束时, st.y(pTp(x2)+b)≥1,若y=sign(uo(ae1)+b) £;≥1-(vφ(axz)+b),而优化目标要最小化5,所 以£2=1-(Dp(x)+b) 其中,I()是指示函数,C是个可调节参数用于权衡优 化间隔和少量分类错误样本这两个目标.但是,指示函 推论24.软间隔支持向量机基本型中描述的优化问题 属于二次规划冋题,包括m+d+1个优化变量,2m项 数不连续,更不是凸函数,使得优化间题不再是二次规 约束 划问题.所以我们需要对其进行简化 公式60难以实际应用的原因在于指示函数只有两 正明.令 个离散取值0/1.对应样本分类正确/错误.为了能使优 化问题继续保持为二次规划问题,我们需要引入一个取 u:=b|,Q:= t 值为连续值的变量,刻画样本满足约束的程度.我们引 00 1 入松弛变量( slack variable)s2,用于度量样本违背约束 的程度.当样本违背约束的程度越大,松弛变量值越大 v(∞) d;;=1,讠-1, m 6 若y(φ(a;)+b)≥ 1-y2(v(x)+b)否侧 d m+1 65 e (61 代入公式10即得 定理23(软间隔支持向量机基本型).软间隔支持向量 机旨在找到一组合适的参教(U,b),使得 5.2软间隔支持向量机对偶型 min ww+C w, b, 4 ∑ (62 定理25(软间隔支持向量机对偶型)·软隔支持向量 机的对偶冋题等价于找到一组合适的α,使得 v:(vp(x)+b)≥1- 1,2, 5;≥0,2=1,2 min 2∑∑ap(a)0a)-∑ (66 其中,C是个可调节参数用于权衡优化间隔和少量样本 n 违背大间隔约束这两个目标,当C比较大时,我们希望 ∑ a;y=0, 0≤az≤5,i=1,2, 53软间隔攴持向量机的攴持向量 证明.软间隔支持向量机的拉格朗日函数为 定理27(软间隔支持向量机的KKT条件).软间隔支 持向量机的KKT条件如下 c(sa,):-w+c∑ ·主问题可行:1-5;-(oφ(xz)+b)≤0,5≤0 ·对偶问题可行:a;≥0,62≥0 +∑a;(1-5;-91(o(x;)+b) 互补松弛:a1(1-5-y(ud(a)+b)=0,月5 +∑:(-5 (67)证明.令 其对偶问题为 b max min C(w, b,$,a, B) (68 a B w, 6, s (69) 9z() yi m,(79) B;>0,t=1,2 e 因为内层对(1,b,5)的优化属于无约束优化间题,我们 i=m+1...,2 8 可以通过令偏导等于零的方法得到(,b,5)的最优值 Oc 代入引理8即得 →? (70 引理28.软间隔攴持向量机中,支持向量落在最大间隔 aC 0→∑ 边界,內部,或被错误分类的样本 0 (71) 证明.由软间隔支持向量札的KKT条件可知.αa(1 ac +6z=C (72)5-y(中(a1)+b)=0且;=0.当a1>0时, 1-5;-y(u(z)+b)=0.进一步可分为两种情况 因为存在约束β=C-az≥0,不失一般性,我们可以 0<c;<C.此时B=C-a;>0.因此s;=0. 约束0≤c;≤C,从而去掉变量β2.将其代入公式68 即该样木恰好落在最大间隔边界上 消去(,b,,③),即得. a;=C.此时2=C-az=0.若5z≤1,该样木 落在最大间隔内部;若ξ>1,该样木被错误分类. 推论26.软间隔支持向量杌对偶型中描述的优化问题 属于二次规划问题,包括m个优化变量,2m+2项约定理29.支持向量机的参数(αo,b)仅由支持向量决定, 束 与其他样本无关 证明.令 证明.和线性支持向量机证明方式相同 u:α,q:[vyφ(x)φ(xnm,t:=-1,(73)5.4铰链损失 C;:=e;,d=0,讠=1,2, (74)引理30.公式6等价为 c:=-e,d:=一5,=m+1,…,2m,(75) 5;=max(0,1-y(nd(x)+b).(81) y2…ym],d 0 76) c2n+2:=-[1y…,mn],an+2=0,(7)证明,当样本满足约束时,1-m(p(ax)+b) ;-0;当样本不满足约束时,1-y1(u(xz)+b)>0 代入公式10即得 -1-y;(φ(x1)+b) 定理31.软间隔支诗向量机的基本型等价于 algorithn1坐标下降 r put:优化目标∫ m max(0,1-:()9(m:)+b)+n| Output:u,使得∫(u)最小 b 1: whilc不收敛do (82 2:fort←1 to n do 其中,第一项称为经验风险,度量了模型对训练数捃的 3:;← arg minu;f(a) 拟合程度;第二项称为结构风险,也称为正则化项,度量 end for 了模型自身的复杂度。正则化项削减了假设空间,从而 5: end while 降低过拟合风险.λ是个叮调节的超参欻,用于权衡经 return ? 验风险和结构风险. 定理32(SM0每步的优化目标).SMO每步的优化月 证明.对应于软间隔支持向量机的基本型,ξ; 标为 max(0,1-v;(o(a;)+b)>0,且A= 定义6(饺链损失( hinge loss)·饺链损失函数定义为 m2(a2的)a)+a)x) +2a2013((m)(m;)-(a;+a)(84) e(s)=max(0,1-6) s.t. aiGi+a,,=C, 除铰链损失外,还有其他一些常用损失函数[9,见 0<az≤5, 表2.s:=yφ(∞)的数值大小度量了模型认为该样 0≤a;≤5 本属于某一标记的确信程度.我们希望,当样本分类正 确吋,即>0时,(s)小一些;当样本分类错误吋,即 其中,c:=-∑k≠;hDh s<0时,(s)大一些 正明固定住公式68中取m,a;外的其他变量即得 推论33.SMO每步的优化目标可等价为对cz的单变 6优化方法 量二次规划问题 证明.由于a;=9;(c-aiy),我们可以将其代入SMO 6.1 SMO 每步的优化目标,以消去变量;·此时,优化目标函数 是对于Qz的二次函数,约束是一个取值区间L≤a;≤ 如果直接用经典的二次规划软件包求解支持向量 机对偶型,由于Q:=[yd(a)"d(x)]mnxm的存储开 H.之后根据目标函数顶点与区间[,H的位置关系, 销是O(m2),当训练样本很多时,这将是一个很大的存 可以得到a的最优值 储和计算开销.序列最小化(SMO)是一个利用支持 理论上讲,每步优化时cz和α;可以任意选择,但 向量机自身特性高效的优化算法.SMO的基本忠路是 实践中通常取az为违背KKT条件最大的变量:而 坐标下降 基本思路是取对应样本与;对应样本之间间隔最大的变量.对 SMO算法收敛性的测试可以用过检测是否满足KKT 定义7(坐标下降)通过循环使用不同坐标方向,每次条件得到 固定其他元素,只沿一个坐标方向进行优化,以达到目 标函数的局部最小,见算法1 6.2 Pegasos 我们希望在支持向量机中的对偶型中,每次固定除 我们也可以直接在原问题对支持向量机进行优化, ax外的其他变量,之后求在α;方向上的极值.但由于尤其是使用线性核函数时,我们有很高效的优化算法, 约束∑m1van=0,当其他变量固定时,a;也随着确如 Pegasos14. Pegasos使用基于梯度的方法在线性支 定.这样,我们无法在不违背约束的前提下对c;进行优持向量机基木型 化.因此,SMO每步同时选择两个变量a和a;进行 u, b m 2 max(0, 1-y(aai+b))+ min U 优化,并固定其他参数,以保证不违背约束 Table2常用损失函数.其中s:=v(x) 名称 形式 特点 实例 0/1损失 I(S<0) 直接优化日标;非凸,不连续,NP难感知机 铰链损失 max(0,1-δ)替代损失,0/1损失上界;凸,连续支持向量机,基于二次规划方法优化 对数几率损失log(1+exp(-s))替代损失,0/1损失上界;凸,连续对数几率回归,基于梯度下降方法优化 指数损失 exp(s) 替代损失,0/1损失上界;凸,连续 Adaboost,分布优化基分类器杈重 进行优化,见算法2 {(51,v1),(s2,y2),,(5m,mm)}当做新的训练数据训练 一个对数几率回归模型,得到参数(61,分0).因此,Prob- Algorithm 2 Pegasos SVM的假设函数为 Input:{(x1,y1),(c2,y2),…,(m,ym)} Output:支持向量机参数(t,b) h(a): =sigm(0,( (a)+b)+0o 1: while不收敛do 2:←-n∑m=1(y,(x;+b)≤1)yx;+ 对数几率冋归模型可以认为是对训练得到的支持向量 ←-1∑m1((Dm;+b)≤1)·v 机的微调,包括尺度(对应的1)和平移(对应60).通常 4:w←0 61>0,0≈0. 5:b←b-7 多分类攴持向量机.支持向量机也可以扩展到多分类问 6: end while 题中.对于K分类问题,多分类支持向量机[7有K 7: return (w, b) 组参数{(1,b1),(2,b2),,(DK,bκ)},并希望模型 对于属于正确标记的结果以1的间隔高于其他类的结 果,形式化如下 6.3近似算法 F mIn 当使用非线性核函数下的支持向量机时,由于核 w. b ∑∑max(0,(an(a:)+b) i=1k=1 矩阵K:=(;,)]mxm,所以时间复杂度一定是 8 因此,有许多学者致力于研究一些快速的近 (k(x)+b)+1)+2∑ k-1 似算法.例如,CVM[习基于近似最小包围球算法, Nystrom方法[8]通过从K采样出一些列来得到K 支持向量回归(SVR).经典回归模型的损失函数度量 的低秩近似,随机傅里叶特征[12]构造了向低维空间的 了模型的预测h(c;)和v的差别,支持向量回归同能 随机映射. 够容忍h(x;)与vi之间小于ε的偏差.令S:-y 本章介绍了许多优化算法实际上现在已有许多开 (vφ(∞)+b,我们定义e-不敏感损失为 源软件包对这些算法有很好的实现,目前比较著名的有 若|-(eφ(x)+b)|≤ 8 Liblinear[和 Libsvm[3],分别适用于线性和非线性 s-c否则 核函数 定理34(支持向量冋归).支持向量回归可形式化为 7支持向量机的其他变体 min max(0,32-((m;)+b)l-e)+。 77L Probsvm.对数几率回归可以估计出样本属于正类 的概率,而支持向量机只能判断样本属于正类或负类,证明,当|y-(u(x)+b)≤ε时,|y-(u(x)-b) 无法得到概率. ProbsvM[先训练一个支持向量≤0,max(0,)结果为0:当|y-((x)+b)>e 机,得到参数(0,b).再令s;:-y1tp(x;)+b,将时,max(0,)结果为|y-(vp(x)+b)|-c 10

...展开详情
试读 11P SVM原理分析
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
SVM原理分析 16积分/C币 立即下载
1/11
SVM原理分析第1页
SVM原理分析第2页
SVM原理分析第3页

试读结束, 可继续读1页

16积分/C币 立即下载 >