第二讲支持向量机

第二讲支持向量机技术•二分类问题•支持向量机的模型•支持向量机的特色•支持向量机的求解•支持向量机的变形二分类问题二分类问题：根据给定的训练集，其中要求寻找上的决策函数以便能用决策函数“较好地”推断任一模式相对应的值。),(,),,(11llyxyxTnixRC{1,1}iyУli,,2,1C():fxCУ()fxxy支持向量机模型•线性可分情形•线性近似可分情形•线性不可分情形•小结线性可分情形：最大间隔原理0:(,)1:(,)0:(,)1lwxblwxblwxb2/||||w0lllw2,1min||||2..((,))1(1)1,,wbiiwSTywxbil*,*1:()sgn((*,)*)wbfxwxb分类决策函数(设是模型（）的最优解）近似线性可分情形0:(,)1:(,)0:(,)1lwxblwxblwxb2,,1min||||2..((,))1(2)0,1,,iiwbiiiiiwCSTywxbil*,*:()sgn((*,)*)wbfxwxb分类决策函数(设是模型（2）的最优解）2/||||w0lllwC代表了经验风险与置信风险的折中线性不可分情形（1）线性不可分情形（2）2,,1min||||2..((,()))1(3)0,1,,iiwbiiiiiwCSTywxbil*,*:()sgn((*,)*)wbfxwxb分类决策函数(设是模型（3）的最优解）•模型（3）的求解，必须知道非线性映射Ф的具体形式，但实际工作上，给出Ф的具体形式是非常困难的！线性不可分情形（3）—对偶模型2,,11min||||2..((,()))1(3)0,1,,iliwbiiiiiwCSTywxbil*1**1*()*(,)(0)liiiiljiiijjiwyxbyykxxC11111min(,)2..0,0(4)1,,lllijijijiiiiliiiiyyKxxSTyCil对偶模型原问题的解与对偶问题的解之间的关系：**11()sgn((*,)*)sgn((,)(,))lliiijiiijiifxwxbykxxyykxx分类决策函数：这里K(xi,xj)=(Ф(xi),Ф(xj))是样本xi,xj在特征空间中的内积，称为输入空间X上的核函数。支持向量机的建模小结统一归结到C-SVC模型：11111min(,)2..0,0(4)1,,lllijijijiiiiliiiiyyKxxSTyCil当C=∞,K(xi,xj)=(xi,xj)时对应线性可分情形；当0C∞,K(xi,xj)=(xi,xj)时对应近似线性可分情形。支持向量机的特色•用间隔定量地定义了置信风险：间隔越大，置信风险越小，间隔越小，置信风险越大•用参数C实现了经验风险与置信风险的折中•最优分类超平面只由少数支持向量决定，问题具有稀疏性•模型为凸二次规划模型，没有陷入局部最优解的问题，任何局部最优解都是全局最优解•通过使用核方法，具备了强大的非线性处理能力支持向量0lll*iC支持向量：界内支持向量：界上支持向量：*0iC*0i注：问题具有稀疏性是指决策时可以不管非支持向量的样本，而仅用到少数支持向量样本。注意训练时还是用到了所有的样本。支持向量机模型的求解•任何求解凸二次规划问题的算法；•大规模问题时：序贯最小最优化算法(SequentialMinimalOptimization,SMO)SMO算法•C-SVC模型当Lagrange乘子只有2个时，可以求得它的解析解。•每次选择两个训练点，求出它的解析解；训练点的选择标准是使得目标函数值下降得尽可能的多。•迭代的停止准则为所有训练点满足KKT条件。二个Lagrange乘子变量的C-SVC122212111222121212,12111222112231211min(,)22()..(5)0,CliiiMkkyykyvyvSTyyy常数常数KKT条件i11110C,1,,;00((,))10((,))1((,))1liiiliijjijjliijjijjliijjijjilyyykxxbCyykxxbCyykxxb支持向量机的变形•基于平分最近点原理的模型•L2-SVC•ν-支持向量机（ν-SVC）平分最近点原理基于平分最近点原理的模型2111111min||()()||()22..1,(6)0D(),()(,);D1(D=1D1iiiiTiiiiyyiiyyiijiijjiijjxxGKSTGKlGKyKyykxxy这里是个阶的矩阵表示线性可分情形，表示线性不可分情形）特点：•与C-SVC基本上是等价的；•给出了比C-SVC更为直观的几何意义；•给出了比C-SVC更好的样本线性可分性描述；•D的选取不如C方便L2-SVC22i,,11min||||2..((,()))1(7)0,1,,ilwbiiiiiwCSTywxbil22i,,11min||||2..((,()))1(8)1,,ilwbiiiiwCSTywxbil111111min((,))2..0,0,1,,(9)1,0,lllijijijijiiiiliiiiijyyKxxCSTyilijij其中模型（8）的对偶模型为：ν-SVC•ν-SVC的模型•ν-SVC的性质ν-SVC模型（1）2/||||w0lllw0:(,):(,)0:(,)lwxblwxblwxbw给定时,ρ越大，间隔就越大，但是间隔内的支持向量也越多，即经验风险也越大，所以当w给定时，我们也可以设置一个参数代表经验风险与置信风险的折中，或者更准确地说，这个参数可以控制间隔内的支持向量的个数iν-SVC模型（2）2,,,111min||||(())2..((,()))0,1,,,0iliwbiiiiiwClSTywxbil11111min(,)2..0,10,1,,llijijijiilliiiiiiyyKxxSTyCCill2,,,111min||||2..((,()))(10)0,1,,,0iliwbiiiiiwlSTywxbil对偶模型11111min(,)2..0,(11)10,1,,llijijijiilliiiiiiyyKxxSTyill对偶模型ν-SVC性质•间隔错误样本点•参数v的意义•ν-SVC与C-SVC的关系•ν-SVC与平分最近点原理的关系间隔错误样本点：2/||||w0lllw*0i参数v的意义•若，则V是间隔错误样本的个数占总样本个数比率的一个上界，同时也是支持向量的个数占总样本个数比率的一个下界，即*0,pqllpq这里是间隔样本点的个数，是支持向量的个数C-SVC与ν-SVC的关系(1)2,,11min||||2()..((,()))10,1,,iliwbiCiiiiwCPSTywxbil11111min(,)2()..0,0,1,,lllijijijiiiilCiiiiyyKxxDSTyCil2,,,111min||||2()..((,()))0,1,,,0iliwbiviiiiwlPSTywxbil11111min(,)2()..0,10,1,,llijijijiillviiiiiiyyKxxDSTyillC-SVC与ν-SVC的关系(2)CTC*Cv*CC0Cv(D),0CCe/(C);C03C0(D)(D)limClimC4(P)(P)CCCClTT**(1)若和是对偶问题的解，则ee因此可定义(,)上的的函数()=(2)()是(,)恒取正值的连续单调下降函数;()若按映射=()建立从(,)到(,)的对应关系，则问题和有相同的解集，这里()，()；()若问题和CCC-SVCv-SVC的解是唯一的，按映射=()建立与的对应关系，则与有相同的决策函数的图像C()ν-SVC与平分最近点原理的关系(1)2,,,11min||||22..((,()))0,1,,,0iliwbiiiiiwSTywxbil11111min(,)2..0,201,1,,llijijijiilliiiiiiyyKxxSTyilV=2的v-svc模型的对偶模型为：与平分最近点原理的模型完全一样11111min(,)2..1,01,1,,iillijijijiiiiyyiyyKxxSTilν-SVC与平分最近点原理的关系(2)•V-SVC通过变量变换：得到一个仅比例发生变化的模型，而它的对偶模型（称为μ-SVC）为：22,,,,,/2iiFwbFwbvvlvvvvν-SVC与平分最近点原理的关系(3)•这与缩减的凸壳(reducedconvexhull)的平分最近点原理的模型本质上完全一样2111111min||()()||()22..1,0DiiiiTiiiiyyiiyyixxGKST111min(,)4..0,2,0,1,,llijijijiiiiiiiiyyKxxSTyil