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

第六章：支持向量机;大纲;引子;引子;引子;间隔与支持向量;支持向量机基本型;其中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)为凹函数。 凸优化的任一局部极值点也是全局极值点，局部最优也是全局最优。;等式约束;不考虑圆h(x)的限制时，f(x)要得到极小值，需要往f(x)的负梯度（下降最快的方向）方向走，如下左图蓝色箭头。 如果考虑圆h(x)的限制，要得到极小值，需要沿着圆的切线方向走，如下右图红色粗箭头。注意这里的方向不是h(x)的梯度，而是正交于h(x)的梯度，h(x)梯度如下右图的红色细箭头。 在极小值点，f(x)和h(x)的等高线是相切的。;在关键的极小值点处，f(x)的负梯度和h(x)的梯度在同一直线上， 如下图左下方critical point的蓝色和红色箭头所示。;特别注意：优化问题是凸优化的话，通过上图两个条件求得的解就是极小值点（而且是全局极小）。不是凸优化的话，这两个条件只是极小值点的必要条件，还需要附加多一个正定的条件才能变成充要条件，如下图所示。;不等式约束;极小值点落在可行域内（不包含边界）;?极小值点落在可行域外（包含边界）;极小值点落在可行域内（不包含边界）：这个时候可行域的限制不起作用，相当于没有约束，直接f(x)的梯度等于0求解，这个时候g(x极小值点)0（因为落在可行域内）。 极小值点落在可行域外（包含边界）：可行域的限制起作用，极小值点应该落在可行域边界上即g(x)=0，类似于等值约束，此时有g(x)的梯度和f(x)的负梯度同向。;总结;优化问题是凸优化的话，KKT条件就是极小值点（而且是全局极小）存在的充要条件。 不是凸优化的话，KKT条件只是极小值点的必要条件，不是充分条件，KKT点是驻点，是可能的极值点。也就是说，就算求得的满足KKT条件的点，也不一定是极小值??，只是说极小值点一定满足KKT条件。;不是凸优化的话，还需要附加多一个正定的条件才能变成充要条件，如下图所示。 ;推广到多个等式和不对等式约束 ;总结;大纲;对偶问题 拉格朗日乘子法;解的稀疏性;对偶方法重新求解前面的问题;对偶方法重新求解前面的问题;第一步：转化为对偶问题;第二步：代入约束条件;第三步：利用KKT条件，计算向量w;第四步：利用KKT条件，计算b;高效求解方法 – SMO: sequential minimal optimization;SMO 变量选择原则;大纲;线性不可分;核支持向量机;核函数;核函数;核函数的注意事项：;大纲;软间隔;0/1损失函数;替代损失;软间隔支持向量机;软间隔与松弛向量;软间隔与松弛向量;软间隔与松弛向量;软间隔与松弛向量;软间隔与松弛向量;软间隔与松弛向量;求解软间隔问题：;软间隔支持向量机;软间隔支持向量机KKT条件;;C-SVC 机的变形;C-SVC 机的等价变形;C-SVC 机的变形的对偶;;正则化;正则化;正则化;大纲;支持向量回归机--SVR;支持向量回归;支持向量回归;损失函数;支持向量回归;形式化;推导SVR;大纲;表示定理;核线性判别分析;Take Home Message;成熟的SVM软件包