3线性可分SVM

线性可分SVM王成（副教授）计算机科学与技术学院目录支持向量机概述支持向量机理论函数间隔和几何间隔最优间隔分类器广义最优分类面支持向量机实现:SMO优化问题支持向量机概述1963年，Vapnik在解决模式识别问题时提出了支持向量方法,这种方法从训练集中选择一组特征子集,使得对特征子集的划分等价于对整个数据集的划分,这组特征子集就被称为支持向量(SV)。1971年，Kimeldorf提出使用线性不等约束重新构造SV的核空间,解决了一部分线性不可分问题。1990年，Grace,Boser和Vapnik等人开始对SVM进行研究。1995年，Vapnik正式提出统计学习理论。目录支持向量机概述支持向量机理论函数间隔和几何间隔最优间隔分类器广义最优分类面支持向量机实现:SMO优化问题3.2支持向量机理论SVM从线性可分情况下的最优分类面发展而来。最优分类面就是要求分类线不但能将两类正确分开(训练错误率为0),且使分类间隔最大。SVM考虑寻找一个满足分类要求的超平面,并且使训练集中的点距离分类面尽可能的远,也就是寻找一个分类面使它两侧的空白区域(margin)最大。过两类样本中离分类面最近的点且平行于最优分类面的超平面上H1,H2的训练样本就叫做支持向量。目录支持向量机概述支持向量机理论函数间隔和几何间隔最优间隔分类器广义最优分类面支持向量机实现:SMO优化问题定义函数间隔：ˆ()Tiiiywxbˆi的值实际上就是||Tiwxb，反之亦然。为了使函数间隔最大（更大的信心确定该例是正例还是反例），当0Tiwxb，ˆi应该是个大正数，反之是个大负数。因此函数间隔代表了认为特征是正例还是反例的确信度。函数间隔和几何间隔给定一个训练样本111(,),...,(,),...,(,),,{1,1}niilliixyxyxyxy，ix是特征，iy是结果标签，i表示第i个样本。若0Tiwxb，则1iy；若0Tiwxb，则1iy；可以被一个超平面分开1()0,,Tnwxbwb刚刚定义的函数间隔是针对某一个样本的，现在定义全局样本上的函数间隔某种试验方法的名称——这种方说白了就是在训练样本上分类正例和负例确信度最小那个函数间隔。1,2,,ˆˆminiil接下来定义几何间隔，先看图如上图所示，对于一个点，令其垂直投影到超平面上的对应的为，由于是垂直于超平面的一个向量，为样本到分类间隔的距离，有(表示的是范数)又由于是超平面上的点，满足，代入超平面的方程即可算出：不过这里的是带符号的，我们需要的只是它的绝对值，因此类似地，也乘上对应的类别y即可，因此实际上定义几何间隔为：γ函数间隔和几何间隔x0xwx0wxxww0x0()0fx0wxxw()()ˆTyfxywxbyww()Twxbfxww函数间隔和几何间隔继续考虑w和b，如果同时加大w和b，比如在Tiwxb前面乘个系数比如2，那么所有点的函数间隔都会增大2倍，这个对求解问题来说不应该有影响，因为要求解的是0Tiwxb，同时扩大w和b对结果是无影响的。为了限制w和b，可能需要加入归一化条件，毕竟求解的目标是确定唯一一个w和b，而不是多组线性相关的向量。这里用规约，使得是几何间隔。1wwTwxb目录支持向量机概述支持向量机理论函数间隔和几何间隔最优间隔分类器广义最优分类面支持向量机实现:SMO优化问题最优间隔分类器前面我们提到我们的目标是寻找一个超平面，使得离超平面比较近的点能有更大的间距。也就是我们不考虑所有的点都必须远离超平面，我们关心求得的超平面能够让所有点中离它最近的点具有最大间距。形象的说，我们将上面的图看作是一张纸，我们要找一条折线，按照这条折线折叠后，离折线最近的点的间距比其他折线都要大。形式化表示为：到此，我们已经将模型定义出来了。如果求得了和，那么来一个特征，我们就能够分类了，称为最优间隔分类器。接下的问题就是如何求解和的问题了。,,max.(()),1,...,1wbTiistywxbilwwxwbb,,max.(()),1,...,1wbTiistywxbilw,,max.(())1,1,...,1wbTiiwbstyxilw,,1,,1max.(())1,1,...,1wbTiiwbwb,1max.(())1,1,...,wbTiiwstywxbil2,1min2.(())1,1,...,wbTiiwstywxbil这时候其实我们求的最大值仍然是几何间隔，只不过此时的不受的约束了。然而这个时候目标函数仍然不是凸函数，没法直接代入优化软件里计算，我们还要改写。前面说到同时扩大和对结果没有影响，但我们最后要求的仍然是和的确定值，不是他们的一组倍数值。因此，我们需要对做一些限制，以保证我们解是唯一的。这里为了简便我们取=1。这样的意义是将全局的函数间隔定义为1，也即是将离超平面最近的点的距离定义为。由于求的最大值相当于求的最小值，因此改写后结果为：这下好了，只有线性约束了，而且是个典型的二次规划问题（目标函数是自变量的二次函数）。ˆw1w1221wˆ2,,,11min()minmin()22.(())1,1,...,TwbwbwbTiiwbwbw1w目录支持向量机概述支持向量机理论函数间隔和几何间隔最优间隔分类器广义最优分类面KKT条件和对偶问题支持向量机实现:SMO优化问题支持向量机理论（续1）广义最优分类面错了吧，应该是（w*x2）+b=-1广义最优分类面（续1）假定训练数据可以被一个超平面分开我们进行正归化此时分类间隔等于使最大间隔最大等价于使最小(())1,1,...,Tiiywxbil1()0,,Tnwxbwb111(,),...,(,),...,(,),,{1,1}niilliixyxyxyxy2w2w广义最优分类面（续2）最优分类面问题可以表示成约束优化问题MinimizeSubjectto211()()22(())1,1,...,TTii典型的凸二次规划问题（目标函数是自变量的二次函数，且只有线性约束了）。•这个问题可以用任何现成的QP(QuadraticProgramming)的优化包进行求解，归结为：在一定的约束条件下，目标最优，损失最小；•这种问题可以通过求解对偶问题得到最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：a)对偶问题往往更容易求解；b)可以自然的引入核函数，进而推广到非线性分类问题。目录支持向量机概述支持向量机理论函数间隔和几何间隔最优间隔分类器广义最优分类面KKT条件和对偶问题支持向量机实现:SMO优化问题广义最优分类面（续2）最优分类面问题可以表示成约束优化问题MinimizeSubjectto211()()22(())1,1,...,TTii典型的凸二次规划问题（目标函数是自变量的二次函数，且只有线性约束了）。•这个问题可以用任何现成的QP(QuadraticProgramming)的优化包进行求解，归结为：在一定的约束条件下，目标最优，损失最小；•这种问题可以通过求解对偶问题得到最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：a)对偶问题往往更容易求解；b)可以自然的引入核函数，进而推广到非线性分类问题。2121(,,)(()1)lTiiiiLwbwywxb21212121212111212111(,,)(1)()()lTiiiiilTiiiiiiilllTiiiiiiiiilllTiiiiiiiiiLwbwywxybwywxybwywxybbywywx(,,)0(,,)0LwbLwbbw110lliiiiiiiaywyx定义Lagrange函数：关于Lagrangeduality，就是通过给每一个约束条件加上一个Lagrangemultiplier(拉格朗日乘子)，即引入拉格朗日乘子α，如此我们便可以通过拉格朗日函数将约束条件融入到目标函数里去。1211111()().0,1,...,,0()sgn()sgn(())lllTiijijijiijliiiilTTiiiiLyyxxstilandyfxxwbyxxb考虑Wolf对偶性质，即可得到优化问题的对偶问题：可见对偶问题仍然是线性约束的凸二次优化，存在唯一的最优解。*121111max()max(()).0,1,...,,0lllTiijijijiijliiiiLyyxxstilandy目录支持向量机概述支持向量机理论函数间隔和几何间隔最优间隔分类器广义最优分类面KKT条件和对偶问题支持向量机实现:SMO优化问题这个问题有更加高效的优化算法，即SMO算法:当：要解决的是在参数上求最大值的问题，至于和都是已知数，其中C是一个参数，用于控制目标函数中两项（“寻找最大的超平面”和“保证数据点偏差量最小”）之间的权重。由SMO算法得出在（0，C）内的样例都能够遵循KKT条件。i121111max()max(()).0,1,...,,0lllTiijijijiijliiiiLyyxxstCilandy1(,,,,)TilwSMO优化问题基本思路：每次从α1α2α3……αl中选择αi,αj当做变量，其他当做常量。更新αi,αj重复以上两步，直到收敛。11111max2s.t.,0,0,=1,2,...,lllliijijiijliiiijiyxxyyi如何选择待更新的两个量？如何更新这两个量？11220111={(,)(,),(,)},{1,1},1,2,,(1)0,0(2),,,(3)nnniifinalKKKKKKijijTxyxyxyxRyiNK：训练数据集，…，其中有…，精度：近似解算法描述：取初始值选取优化变量针对优化问题，求解得最优解，更新为在精度范输出输入围内，测1KKT1(4)=KfinalKK试是否满足停止条件：是否有变量违反条件，如果违反，令，转到(2),否则转到(4)得到近似解SMO优化问题SMO优化问题SMO算法流程SMO优化问题•如何选择待更新的两个量？•如何更新这两个量？两个问题：一个简单的例子：4x3x2x1x222123422334123412341()()(444)20,0,0,0,0Land,y1=+1,y2=+1,y3=-1,y4=-1可调用Matlab中的二次规划程序，求得1,2,3,4的值，进而求得和b的值。w1(0,0)Tx2(1,0)Tx3(2,0)Tx4(0,2)Tx1234112013/41/41120312002144231113,022240()3220liiiiTwyxwbwxbgxxx根据约束优化问题的KKT（Karush-Kuhn-Tucker）条件，优化最优解时，应满足如下条件：由于只有少部分观测样本满足,它们对应的Lagrang