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

为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益第六章：第六章：支持向量机支持向量机为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益大纲大纲间隔与支持向量对偶问题核函数软间隔与正则化支持向量回归核方法为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益引子引子线性模型：在样本空间中寻找一个超平面,将不同类别的样本分开.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)为凹函数。凸优化的任一局部极值点也是全局极值点，局部最优也是全局最优。凸优化的任一局部极值点也是全局极值点，局部最优也是全局最优。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益等式约束考虑一个简单的问题目标函数为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益不考虑圆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条件条件。特别注意：特别注意：为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益不是不是凸优化的话，还需要附加多一个凸优化的话，还需要附加多一个正定正定的条件才能变成充要条的条件才能变成充要条件，如下图所示。件，如下图所示。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益推广到多个等式和不对等式约束 为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益总结如果有m个不等式约束，就需要讨论种情况！需要找到新的方法。对偶方法为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益大纲大纲间隔与支持向量对偶问题核函数软间隔与正则化支持向量回归核方法为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益对偶问题拉格朗日乘子法第一步：引入拉格朗日乘子得到拉格朗日函数和第二步：令对的偏导为零可得 第三步：回代可得为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益解的稀疏性解的稀疏性最终模型：KKT条件：支持向量机解的稀疏性:训练完成后,大部分的训练样本都不需保留,最终模型仅与支持向量有关.重要性质：模型训练完后，大部分的训练样本都不需要保留，最终模型仅仅与支持向量有关必有或为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益对偶方法重新求解前面的问题为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益对偶方法重新求解前面的问题为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益第一步：转化为对偶问题为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益第二步：代入约束条件为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益第三步：利用KKT条件，计算向量w为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益第四步：利用KKT条件，计算b 如果样本变多，人工计算不现实，需要一种高效的计算算法为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益高效求解方法高效求解方法 SMO:sequential minimal optimization基本思路：不断执行如下两个步骤直至收敛.l第一步：选取一对需更新的变量 和 .l第二步：固定 和 以外的参数,求解对偶问题更新 和 .仅考虑 和 时,对偶问题的约束变为偏移项 ：通过支持向量来确定.用一个变量表示另一个变量,回代入对偶问题可得一个单变量的二次规划,该问题具有闭式解.为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益SMO 变量选择原则变量选择原则 第一个变量是在KKT条件不满足的中间选择，直观来看，KKT条件违背的程度越大，则变量更新后可能会使得目标函数的增幅越大，从而选择违背KKT条件程度越大的变量 第二个变量应选择使得目标函数增长最快的变量；常用启发式，也就是两样本的间距最大为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益大纲大纲间隔与支持向量对偶问题核函数软间隔与正则化支持向量回归核方法为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益线性不可分线性不可分-Q:若不存在一个能正确划分两类样本的超平面,怎么办?-A:将样本从原始空间映射到一个更高维的特征空间,使得样本在这个特征空间内线性可分.为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益核支持向量机核支持向量机设样本 映射后的向量为 ,划分超平面为 .原始问题对偶问题预测只以内积的形式出现为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益核函数核函数基本想法：不显式地设计核映射,而是设计核函数.Mercer定理(充分非必要)：只要一个对称函数所对应的核矩阵半正定,则它就能作为核函数来使用.为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益核函数核函数基本想法：不显式地设计核映射,而是设计核函数.Mercer定理(充分非必要)：只要一个对称函数所对应的核矩阵半正定,则它就能作为核函数来使用.常用核函数：为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益核函数的注意事项：核函数的注意事项：核函数选择成为svm的最大变数经验：文本数据使用线性核，情况不明使用高斯核核函数的性质：1 核函数的线性组合仍为核函数2 核函数的直积仍为核函数3 设 为核函数，则对于任意函数g,为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益大纲大纲间隔与支持向量对偶问题核函数软间隔与正则化支持向量回归核方法为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益软间隔软间隔-Q:现实中,很难确定合适的核函数使得训练样本在特征空间中线性可分;同时一个线性可分的结果也很难断定是否是有过拟合造成的.-A:引入”软间隔”的概念,允许支持向量机在一些样本上不满足约束.0不满足约束的样本为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益0/1损失函数损失函数基本想法：最大化间隔的同时,让不满足约束的样本应尽可能少.其中 是”0/1损失函数”存在的问题：0/1损失函数非凸、非连续,不易优化！为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益替代损失替代损失012-1-2123替代损失函数数学性质较好,一般是0/1损失函数的上界软间隔SVM为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益软软间隔间隔支持向量机支持向量机原始问题为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益软软间隔与间隔与松弛向量松弛向量 超平面方程:0为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益软软间隔与间隔与松弛向量松弛向量 超平面方程:0为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益软软间隔与间隔与松弛向量松弛向量 超平面方程:0为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益软软间隔与间隔与松弛向量松弛向量 超平面方程:0为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益软软间隔与间隔与松弛向量松弛向量 超平面方程:0为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益软软间隔与间隔与松弛向量松弛向量 超平面方程:0为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益求解软间隔问题：求解软间隔问题：构造Lagrange 函数为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益软软间隔间隔支持向量机支持向量机原始问题对偶问题根据KKT条件可推得最终模型仅与支持向量有关,也即hinge损失函数依然保持了支持向量机解的稀疏性.为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益软间隔支持向量软间隔支持向量机机KKT条件条件为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益KKT条件背后的结论C C 分类正确支持向量为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益C-SVC 机的变形为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益C-SVC 机的等价变形多余了!为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益C-SVC 机的变形的对偶为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益软间隔SVM软间隔支持向量机软间隔支持向量机-稀疏性原因稀疏性原因为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益正则化正则化支持向量机学习模型的更一般形式通过替换上面两个部分,可以得到许多其他学习模型l对数几率回归(Logistic Regression)l最小绝对收缩选择算子(LASSO)l结构风险,描述模型的某些性质经验风险,描述模型与训练数据的契合程度为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益正则化正则化为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益正则化正则化为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益大纲大纲间隔与支持向量对偶问题核函数软间隔与正则化支持向量回归核方法为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益支持向量支持向量回归回归机机-SVR0间隔带对于有限个样本组成的训练集来说，一定存在一个带状区域包含所有的样本点。并且这样的带状区域有无穷多个，宽度最小的带状区域才是我们关心的。为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益支持向量支持向量回归回归当带状区域很大，所得的回归模型不精确，此时允许模型输出和实际输出间存在 的偏差.0间隔带为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益支持向量回归支持向量回归为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益损失函数损失函数落入中间 间隔带的样本不计算损失,从而使得模型获得稀疏性.0最小二乘损失函数支持向量回归损失函数为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益支持向量回归支持向量回归为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益形式化形式化原始问题对偶问题预测为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益推导推导SVR为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益大纲大纲间隔与支持向量对偶问题核函数软间隔与正则化支持向量回归核方法为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益表示定理表示定理结论:无论是支持向量机还是支持向量回归,学得的模型总可以表示成核函数的线性组合.更一般的结论(表示定理):对于任意单调增函数 和任意非负损失函数 ,优化问题的解总可以写为 .支持向量机支持向量回归为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益核线性判别分析核线性判别分析通过表示定理可以得到很多线性模型的”核化”版本l核SVMl核LDAl核PCAl核LDA:先将样本映射到高维特征空间,然后在此特征空间中做线性判别分析为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益成熟的成熟的SVM软件包软件包LIBSVMhttp:/www.csie.ntu.edu.tw/cjlin/libsvm/LIBLINEARhttp:/www.csie.ntu.edu.tw/cjlin/liblinear/SVMlight、SVMperf、SVMstructhttp:/svmlight.joachims.org/svm_struct.htmlPegasoshttp:/www.cs.huji.ac.il/shais/code/index.html