6.线性支持向量机（线性SVM① 6.线性支持向量机（线性SV① 口序贯最小优化(SMO)算法 口序贯最小优化(SMO)算法 ■假定在某一次迭代中，需更新样本【1,2对应的 ■约束的几何意义 拉格明日乘子a1,a %=C g:=C ■这个小规模的二次规划问题可以写成 化1=0 a=c L,@=a+a)广2++a 1=C =0 ay+a=ya a3=0 s1. 0≤a,≤C,i=1,2: 6.线性支持向量机（线性SVM① 6.线性支持向量机（线性SVM 口序贯最小优化(SMO)算法 口序贯最小优化(SMO)算法 ■更新拉格朗日乘子的步骤 ■更新拉格期日乘子的步骤 1.计算a,w的上下界L和H: 4.计算（剪辑）变量a2: L=max(0,ag-a),H=mim(C,C+ag-a),ify≠为 H,ifa≥H L=max(0.a+a-C).H=min(C.a+a )ify =y a={a,ifLsa≤H 2.计算Ls的二阶导数： L,ifa≤L =2xx2-xx-x2 5.更新a1 3.更新Ls asm=au(e-e) a=a+yy(da) e =g (x)-y 17 6.线性支持向量机（线性SVM 6.线性支持向量机（线性SVM0 口序贯最小优化(SMO)算法 口序贯最小优化(SMO)算法 ■选择需更新的乘子（启发式选择算法) ■由于所有乘子可分为三种情况，当还存在违反 口两个基本原则：(1)任何乘子必须满足KKT条 KKT条件的乘子时，在扫描时可忽略在0和C 件；(2)对一个不满足KKT圣件的乘子进行更 之间的乘子，以加速扫描进程。 新，应能最大限度增大目标函数的值（类似于梯 Training Set SMO Time PCG Time SMO PCG 度下降)： Size (CPU sec)(CPU sec) Iterations Iterations 2477 26.3 64.9 10838 1888 口步骤：(1)先“扫描”所有乘子，把第一个（最）违 3H70 44.1 110.4 13975 2270 反KKT条件的作为更新对象，令其为a2;(②)在 4912 83.6 372.5 18978 5460 7366 156.7 545.4 27402 5274 所有不违反KKT条件的乘子中，选择使|日-e 9888 248.1 907.6 29751 5972 最大的对象，令其为a1 17188 581.0 3317.9 42020 9413 24692 1214.0 G659.7 55490 14H12 49749 3863.5 28877.6 93358 2423513 6. 线性支持向量机 (线性SVM)  序贯最小优化 (SMO) 算法  假定在某一次迭代中，需更新样本 x1, x2 对应的 拉格朗日乘子α1, α2；  这个小规模的二次规划问题可以写成 1 2 2 1 2 111 2 2 2 , 3 11 2 2 1 1 2 2 3 1 max ( ) ( ) , 2 . . 0 , 1, ( 2 ) ; N S iii i N old old i i i i L yy y yy y y y s t C i k                           α xx x 常数 14 6. 线性支持向量机 (线性SVM)  序贯最小优化 (SMO) 算法  约束的几何意义 15 6. 线性支持向量机 (线性SVM)  序贯最小优化 (SMO) 算法  更新拉格朗日乘子的步骤 1. 计算 α2 new的上下界 L 和 H ： 2. 计算 LS 的二阶导数： 3. 更新 LS： 12 11 2 2 2 TTT    xx xx xx 16  序贯最小优化 (SMO) 算法  更新拉格朗日乘子的步骤 4. 计算（剪辑）变量α2 ： 5. 更新α1 ： 6. 线性支持向量机 (线性SVM) 17 6. 线性支持向量机 (线性SVM)  序贯最小优化 (SMO) 算法  选择需更新的乘子（启发式选择算法） 两个基本原则：(1) 任何乘子必须满足 KKT 条 件；(2) 对一个不满足 KKT 条件的乘子进行更 新，应能最大限度增大目标函数的值（类似于梯 度下降）； 步骤： (1) 先“扫描”所有乘子，把第一个（最）违 反 KKT 条件的作为更新对象，令其为α2 ；(2) 在 所有不违反 KKT 条件的乘子中，选择使 最大的对象，令其为α1 。 | | 1 2 e  e 18 6. 线性支持向量机 (线性SVM)  序贯最小优化 (SMO) 算法  由于所有乘子可分为三种情况，当还存在违反 KKT 条件的乘子时，在扫描时可忽略在 0 和 C 之间的乘子，以加速扫描进程