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

第六章：支持向量机 大纲 间隔与支持向量 对偶问题 核函数 软间隔与正则化 支持向量回归 核方法 引子 线性模型：在样本空间中寻找一个超平面, 将不同类别的样本分开. 0 引子 -Q:将训练样本分开的超平面可能有很多, 哪一个好呢? 0 引子 -Q:将训练样本分开的超平面可能有很多, 哪一个好呢? -A:应选择”正中间”, 容忍性好, 鲁棒性高, 泛化能力最强. 0 间隔与支持向量 超平面方程: 间隔 0 支持向量 支持向量机基本型 最大间隔: 寻找参数 和 , 使得 最大. 其中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的蓝色和红色箭头所示。 特别注意：优化问题是凸优化的话，通过上图两个条件求得的解就是极小值点（而且是全局极小）。不是凸优化的话，这两个条件只是极小值点的必要条件，还需要附加多一个正定的条件才能变成充要条件，如下图所示。 不等式约束 对于不等式约束g(x)=0和等式约束h(x)=0不一样，h(x)=0可以在平面上画出一条等高线，而 g(x)=0是一个区域，很多个等高线堆叠而成的一块区域，我们把这块区域称为可行域。 极小值点落在可行域内（不包含边界）  极小值点落在可行域外（包含边界） 对于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条件。 特别注意： 不是凸优化的话，还需要附加多一个正定的条件才能变成充要条件，如下图所示。  推广到多个等式和不对等式约束 总结 对偶方法 大纲 间隔与支持向量 对偶问题 核函数 软间隔与正则化 支持向量回归 核方法 对偶问题 拉格朗日乘子法 和  第三步：回代可得 解的稀疏性 最终模型： KKT条件： 支持向量机解的稀疏性: 训练完成后, 大部分的训练样本都不需保留, 最终模型仅与支持向量有关. 重要性质：模型训练完后，大部分的训练样本都不需要 保留，最终模型仅仅与支持向量有关 必有 或 对偶方法重新求解前面的问题 对偶方法重新求解前面的问题 第一步：转化为对偶问题 第二步：代入约束条件 第三步：利用KKT条件，计算向量w 第四步：利用KKT条件，计算b 如果样本变多，人工计算不现实，需要一种高效的计算算法 高效求解方法 – SMO: sequential minimal optimization 基本思路：不断执行如下两个步骤直至收敛. 第一步：选取一对需更新的变量 和 . 第二步：固定 和 以外的参数, 求解对偶问题更新 和 . 仅考虑 和