周志华-机器学习-西瓜书-全书16章-ppt-Chap06支持向量机

第六章：支持向量机大纲间隔与支持向量对偶问题核函数软间隔与正则化支持向量回归核方法引子线性模型：在样本空间中寻找一个超平面,将不同类别的样本分开.0引子-Q:将训练样本分开的超平面可能有很多,哪一个好呢?0引子-Q:将训练样本分开的超平面可能有很多,哪一个好呢?-A:应选择”正中间”,容忍性好,鲁棒性高,泛化能力最强.0间隔与支持向量超平面方程:间隔0支持向量支持向量机基本型最大间隔:寻找参数和,使得最大.min()s.t.()0,1,2,,()0,1,,xDijfxgxihxjqmq带有的化问优题约束其中f(x)是目标函数，g(x)为不等式约束，h(x)为等式约束。若f(x)，h(x)，g(x)三个函数都是线性函数，则该优化问题称为线性规划。若任意一个是非线性函数，则称为非线性规划。若目标函数为二次函数，约束全为线性函数，称为二次规划。若f(x)为凸函数，g(x)为凸函数，h(x)为线性函数，则该问题称为凸优化。注意这里不等式约束g(x)=0则要求g(x)为凸函数，若g(x)=0则要求g(x)为凹函数。凸优化的任一局部极值点也是全局极值点，局部最优也是全局最优。等式约束考虑一个简单的问题目标函数122212min()()2=0fxxxhxxx1212())=(contourfxxxxxC的等高线是一条条斜率相同的直线：不考虑圆h(x)的限制时，f(x)要得到极小值，需要往f(x)的负梯度（下降最快的方向）方向走，如下左图蓝色箭头。如果考虑圆h(x)的限制，要得到极小值，需要沿着圆的切线方向走，如下右图红色粗箭头。注意这里的方向不是h(x)的梯度，而是正交于h(x)的梯度，h(x)梯度如下右图的红色细箭头。在极小值点，f(x)和h(x)的等高线是相切的。在关键的极小值点处，f(x)的负梯度和h(x)的梯度在同一直线上，如下图左下方criticalpoint的蓝色和红色箭头所示。**fhxxxx特别注意：优化问题是凸优化的话，通过上图两个条件求得的解就是极小值点（而且是全局极小）。不是凸优化的话，这两个条件只是极小值点的必要条件，还需要附加多一个正定的条件才能变成充要条件，如下图所示。不等式约束对于不等式约束g(x)=0和等式约束h(x)=0不一样，h(x)=0可以在平面上画出一条等高线，而g(x)=0是一个区域，很多个等高线堆叠而成的一块区域，我们把这块区域称为可行域。极小值点落在可行域内（不包含边界）22122212min()()10fxxxgxxx最小值点为(0,0)极小值点落在可行域外（包含边界）22122212min()1.11.1()10fxxxgxxx对于f(x)而言要沿着f(x)的负梯度方向走，才能走到极小值点，如下图的蓝色箭头。这个时候g(x)的梯度往区域外发散，如下图红色箭头。显然，走到极小值点的时候，g(x)的梯度和f(x)的负梯度同向。因为极小值点在边界上，这个时候g(x)等于0极小值点落在可行域内（不包含边界）：这个时候可行域的限制不起作用，相当于没有约束，直接f(x)的梯度等于0求解，这个时候g(x极小值点)0（因为落在可行域内）。极小值点落在可行域外（包含边界）：可行域的限制起作用，极小值点应该落在可行域边界上即g(x)=0，类似于等值约束，此时有g(x)的梯度和f(x)的负梯度同向。总结总结对于不等式约束的优化，需要满足三个条件，满足这三个条件的解x*可能的极小值点。这三个条件就是著名的KKT条件，它整合了上面两种情况的条件。优化问题是凸优化的话，KKT条件就是极小值点（而且是全局极小）存在的充要条件。不是凸优化的话，KKT条件只是极小值点的必要条件，不是充分条件，KKT点是驻点，是可能的极值点。也就是说，就算求得的满足KKT条件的点，也不一定是极小值点，只是说极小值点一定满足KKT条件。特别注意：不是凸优化的话，还需要附加多一个正定的条件才能变成充要条件，如下图所示。推广到多个等式和不对等式约束122212,,12121212331..4311minwwb例：121,22wwb221211212312212132133L(,,,,,12)(3)411解：1111232123123123121212121212123L40L30L0()0033331431133104310100,0,00wwbwwbwwbwwbwwbwwb121212121212121231231222133133=()031431133104310100,03,033004wwbwwbwwbwwbwwbwwbww121231211231231221211212112132222110141810452=()00322121510121145100,0,01834313145bbbwbwbb2121===0=001wwb当时，，从而b1&，矛盾！121112121121=0241=0121=00402=bbbww当时，，满足其余条件121231211231231221211212112132222110141810452=()00322121510121145100,0,01834313145bbbwbwbb1212212211181=051=0=0213151361341371451=03=00bwwbbb当时，不符此时，合题意！12112121221221333104310=-1=22000==1041071135=0wwbwwb当时，此时，不符合题意！121212121212111223121223112323232331431133104310100,20=34()0003,03wwbwwbwwbwwbwwbwb总结如果有m个不等式约束，就需要讨论2m种情况！需要找到新的方法。对偶方法大纲间隔与支持向量对偶问题核函数软间隔与正则化支持向量回归核方法对偶问题拉格朗日乘子法第一步：引入拉格朗日乘子得到拉格朗日函数和第二步：令对的偏导为零可得第三步：回代可得11112mmmTTiiiiiiiii112mTiiww解的稀疏性最终模型：KKT条件：支持向量机解的稀疏性:训练完成后,大部分的训练样本都不需保留,最终模型仅与支持向量有关.重要性质：模型训练完后，大部分的训练样本都不需要保留，最终模型仅仅与支持向量有关必有或对偶方法重新求解前面的问题1233,3,4,3,1,1,负正如图所示的训练数据集，其实例点是xx实例x试求其线性可分的支持向量机。312xxx122212,,12121212331..431++1minwwb例：121,22wwb对偶方法重新求解前面的问题第一步：转化为对偶问题123333,,111123123100,0.02.,miniijijijiijyytxxs123222123121323123,,1231231182524200,0,2..11420minst第二步：代入约束条件312=+221211212213()41022,2s目标函数变形为：1212221121()8102()1302,1,ss21213不符合要求，从而最小值在边界达到。第三步：利用KKT条件，计算向量w21122=2121222min2314i111m=n21=00,0,=0,013()2()=2()3142(),04=ssss当，且，时，时，当且23min110,.=411.44从而：当s此时，时，11133311,22yxywx故：110,从而x为支注意到持向量。第四步：利用KKT条件，计算b21121111111()1()2yyfxyfbxyywx从而如果样本变多，人工计算不现实，需要一种高效的计算算法1211222=0xx分离超支持平这样我们就得到了)面向量机(1211()sign222xxfx对于新的样本点，我们使用的为决策函数高效求解方法–SMO:sequentialminimaloptimization基本思路：不断执行如下两个步骤直至收敛.第一步：选取一对需更新的变量和.第二步：固定和以外的参数,求解对偶问题更新和.仅考虑和时,对偶问题的约束变为偏移项：通过支持向量来确定.用一个变量表示另一个变量,回代入对偶问题可得一个单变量的二次规划,该问题具有闭式解.SMO变量选择原则第一个变量是在KKT条件不满足的中间选择，直观来看，KKT条件违背的程度越大，则变量更新后可能会使得目标函数的增幅越大，从而选择违背KKT条件程度越大的变量第二个变量应选择使得目标函数增长最快的变量；常用启发式，也就是两样本的间距最大大纲间隔与支持向量对偶问题核函数软间隔与正则化支持向量回归核方法线性不可分-Q:若不存在一个能正确划分两类样本的超平面,怎么办?-A:将样本从原始空间映射到一个更高维的特征空间,使得样本在这个特征空间内线性可分.核支持向量机设样本映射后的向量为,划分超平面为.原始问题对偶问题预测只以内积的形式出现核函数基本想法：不显式地设计核映射,而是设计核函数.Mercer定理(充分非必要)：只要一个对称函数所对应的核矩阵半正定,则它就能作为核函数来使用.111213121222323132333123K=,,,,,,,,,,,,,,,,mmmmmmmmxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx核矩阵核函数基本想法：不显式地设计核映射,而是设计核函数.Mercer定理(充分非必要)：只要一个对称函数所对应的核矩阵半正定,则它就能作为核函数来使用.常用核函数：核函数的注意事项：核函数选择成为svm