6.线性支持向量机（线性SVM 6.线性支持向量机（线性SVM Soft margin SVM 1. =w-之ayH=0 Soft margin SVM Ow .-之ay=0 aL ■约简KKT条件，可得对偶形式一二次规划问题 2. 80p 3. aL ag, C-a-4=0 min KKT conditions4. i=l 2台m y(w'x+)-1+≥0： 0≤a≤C,i=l,…,N; 5. 号≥0 s.t. 6. g20: 7. 4≥0 8 a(y(w'x,+0,)-1+5)=0 9. 45=0 6.线性支持向量机（线性SVM 6.线性支持向量机（线性SVM Soft margin SVM Soft margin SVM ■几何意义：超平面法向量是支持向量的线性组合。 ■几何意义 KKT complementarity conditions: y,(xw+b)>1g,=0 i:ay(wx,+)-(1-》=0 (C-a)5=0. =0for non-support vectors y,(x*w+b)<1 g马≠0 for support vectors a=C 0<a,<C→y,(wTx,+0。)=l5 ,(◆w+b)=1 a,=0→y,(w'x,+o。)>1; 0<a,<C ■ a,=C→，(w'x,+o。）<1 12 6.线性支持向量机（线性SVM 6.线性支持向量机（线性SV) 口序贯最小优化(SMO)算法 口序贯最小优化(SMO)算法 ■无论Hard Margin或Soft Margin SVM,均可用 ■算法框架 经典的二次规划方法求解，但同时求解N个拉格 for =1:iter 朗日乘子涉及很多次迭代，计算开销太大，所以 a.根据预先设定的规则，从所有样本中选出两个 一般采用Sequential Minimal Optimization(SMO) b.保持其他拉格朗日乘子不变，更新所选样本对应的拉格 算法(.Plat,1999). 朗日乘子 end ■基本思路：每次只更新两个乘子，迭代获得最终 解。 ■优，点：只有两个变量的二次规划问题存在解析解。 ■关能技术细节： 口在每次迭代中，怎样更新乘子？ 口怎么选择每次迭代需要更新的乘子？7 6. 线性支持向量机 (线性SVM)  Soft margin SVM   1 0 1 0 0 1. 0; 2. 0; 3. 0; 4. ( ) 1 0; 5. 0; 6. 0; 7. 0; 8. ( ) 1 0; 9. 0; KKT conditions N iii i N i i i i i i T ii i i i i T ii i i i i L y L y L C y y                                                              w x w w x w x 8 6. 线性支持向量机 (线性SVM)  Soft margin SVM  约简 KKT 条件，可得对偶形式 — 二次规划问题 1 11 1 1 min ( ) ; 2 0 , 1, , ; . . 0. N NB T D i i ji ji j α i ij i N i i i L α αα y y α Ci N s t α y            α x x  9 6. 线性支持向量机 (线性SVM)  Soft margin SVM  几何意义：超平面法向量是支持向量的线性组合。     0   KKT complementarity conditions: : 1 0; ( ) 0. T ii i i i i i y C           w x i = 0 for non-support vectors i  0 for support vectors       0 1 0 0 0 1; 0 1; . 1; i T N i ii iii T i i ii T i ii iii α C y α y α y α C y α y                  x w x w x w x w x x S V 10 6. 线性支持向量机 (线性SVM)  Soft margin SVM  几何意义 11 6. 线性支持向量机 (线性SVM)  序贯最小优化 (SMO) 算法  无论 Hard Margin 或 Soft Margin SVM，均可用 经典的二次规划方法求解，但同时求解 N 个拉格 朗日乘子涉及很多次迭代，计算开销太大，所以 一般采用 Sequential Minimal Optimization (SMO) 算法 (J. Platt, 1999)。  基本思路：每次只更新两个乘子，迭代获得最终 解。 12 6. 线性支持向量机 (线性SVM)  序贯最小优化 (SMO) 算法  算法框架  优点：只有两个变量的二次规划问题存在解析解。  关键技术细节： 在每次迭代中，怎样更新乘子？ 怎么选择每次迭代需要更新的乘子？