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