4线性不可分SVM

线性不可分SVM王成（副教授）计算机科学与技术学院目录线性不可分问题核函数松弛变量多输入多输出支持向量机回归算法支持向量机实现研究现状数据线性不可分的情况解决的一个途径(支持向量机算法)是用“超曲面”代替“超平面”,找一个能够正确分类所有观测样本的的“最大间隔超曲面”。红点x2+y2-4y=0绿点x2+y2-4y=-3映射形式为：Φ(x,y)=x2,y2,y例：二维线性不可分映射到三维后线性可分在用线性学习器学习一个非线性关系，需要选择一个非线性特征集，并且将数据写成新的表达形式，等价于：用一个固定的非线性映射，将数据映射到特征空间，在特征空间中使用线性学习器。因此，考虑的假设集是这种类型的函数：这里ϕ：X-F是从输入空间到某个特征空间的映射1.首先使用一个非线性映射将数据变换到一个特征空间F2.然后在特征空间使用线性学习器分类。1()()Niiifxwxb低维非线性到高维线性这意味着建立非线性学习器分为如下几步：如何处理线性不可分数据目录线性不可分问题核函数松弛变量支持向量机实现研究现状核函数对于非线性的情况，SVM的处理方法是选择一个核函数κ(⋅,⋅)，通过将数据映射到高维空间，来解决在原始空间中线性不可分的问题。核函数通过把数据映射到高维空间来增加第一节所述的线性学习器的能力，使得线性学习器对偶空间的表达方式让分类操作更具灵活性和可操作性。因为训练样例一般是不会独立出现的，它们总是以成对样例的内积形式出现，而用对偶形式表示学习器的优势在为在该表示中可调参数的个数不依赖输入属性的个数，通过使用恰当的核函数来替代内积，可以隐式得将非线性的训练数据映射到高维空间，而不增加可调参数的个数(当然，前提是核函数能够计算对应着两个输入特征向量的内积)。基本概念低维非线性到高维线性在我们遇到核函数之前，如果用原始的方法，那么在用线性学习器学习一个非线性关系，需要选择一个非线性特征集，并且将数据写成新的表达形式，这等价于应用一个固定的非线性映射，将数据映射到特征空间，在特征空间中使用线性学习器，因此，考虑的假设集是这种类型的函数：这里ϕ：X-F是从输入空间到某个特征空间的映射，这意味着建立非线性学习器分为两步：1.首先使用一个非线性映射将数据变换到一个特征空间F，2.然后在特征空间使用线性学习器分类。1()()Niiifxwxb9在上文我提到过对偶形式，而这个对偶形式就是线性学习器的一个重要性质，这意味着假设可以表达为训练点的线性组合，因此决策规则可以用测试点和训练点的内积来表示：对一个函数k，满足所有的x，z都有k(x,z)=ϕ(x),ϕ(z),这里的ϕ(x)为从X到内积特征空间F的映射，则称k为核函数。1()(),()liiiifxayxxb1()(()(){})wnTiiiixfxWxbybxx为原空间中待分类的特征向量为高维空间超平面，的系数向量1111(),()1max2s.t.0,0,=1,2,...,nnniijijiijniiiiijyyyinxx•求解αi,i=1,2,…n•进行分类回顾：核函数的引入在求解分类函数和利用分类函数进行分类时，都涉及到“高维特征向量求内积”。若映射到的高维空间维数太高甚至是无穷维时，存在“维数灾难”。若存在这么一个函数Κ(.,.),满足：(,),()()ijjixxxx也就是说，我们要求的高维空间中向量内积运算，可以直接在低维空间进行运算求得，两者的值相等，这样就避免直接在高维空间求向量积可能带来的维数灾难问题。那么分类函数相应为11w()(){}(){(,())}mTiiimiiijiixfxWxbybyxbxxx为原空间中待分类的特征向量为高维空间超平面的系数向量，当特征空间维数很高或为无穷维时，直接计算高维空间中的内积是非常困难的，因此需要另外的方法。那么巧妙地将高维空间中的求内积运算转化为低维空间中的运算，避免“维数灾难”。核函数的引入12核函数能简化映射空间中的内积运算，在我们的SVM里需要计算的地方数据向量总是以内积的形式出现的。对比刚才我们上面写出来的式子，现在我们的分类函数为：其中由如下dual问题计算而得：避开了直接在高维空间中进行计算，而结果却是等价的！***111,1max2nnniijijiijjiKxxyy1..0,0,1,niiiistyin…，***11sgn,sgn,nniiiiiiiifxyxxbybKxx*i核函数的引入核函数：如何处理非线性数据01某种试验方法的名称——这种方法的特点如果用X1和X2来表示这个二维平面的两个坐标的话，我们知道一条二次曲线（圆圈是二次曲线的一种特殊情况）的方程可以写作这样的形式：062152242321211aXXaXaXaXaXa如果我们构造另外一个五维空间，其中五个坐标为则有：0651aZaiii如果我们做一个映射ϕ:R2→R5，将X按照上面的规则映射为Z，那么在新的空间中原来的数据将变成线性可分的，从而使用之前我们推导的线性分类算法就可以进行处理了。这正是Kernel方法处理非线性问题的基本思想。2211213242512,,,,2ZXZXZXZXZXX例子.设两个向量和，而即是到前面说的五维空间的映射，因此映射过后的内积为：而这个式子与下面这个是等价的：一个是映射到高维空间中，然后再根据内积的公式进行计算；而另一个则直接在原来的低维空间中进行计算，而不需要显式地写出映射后的结果。我们把这里的计算两个向量在隐式映射过后的空间中的内积的函数叫做核函数(KernelFunction)112(,)Tx212(,)Tx222212111122221212(),()2xx22112112212()((,))(,,,,2)TTx22212112212()((,))(,,,,2)TTx221212121122112212,()()()()(),()TTKxxxxxxxx()15核函数能简化映射空间中的内积运算，在我们的SVM里需要计算的地方数据向量总是以内积的形式出现的。对比刚才我们上面写出来的式子，现在我们的分类函数为：其中由如下dual问题计算而得：这样一来计算的问题就算解决了，避开了直接在高维空间中进行计算，而结果却是等价的！****1111max(,)2llliijijijiijyyKxx**1.0,0,1,,liiiistyil****1sgnsgn,lTiiiifxwxbyKxxb*iΦ(.),Φ(.)是高维或无穷维度空间中的向量积运算核函数K（.，.）是直接在低维度空间中进行计算，两者计算结果相等按照前面的思路，处理线性不可分数据步骤为:1.首先寻找一个映射函数2.将数据映射到高维空间，(在高维空间中数据可能变得线性可分)3.在高维空间中应用SVM分析4.求解过程中引入核函数。5.得到分类函数但实际上，寻找使变得线性可分的映射函数很难。寻找与映射函数对应的核函数更难。核函数的实际应用问题上：理论上核函数的使用下：实际中核函数的使用高维空间中的最优分类面非线性问题——通过非线性变换将它转化为某个高维空间中的线性问题，在这个高维空间中寻找最优分类面。分类函数只涉及到训练样本之间的内积运算,因此,在高维空间中只需进行内积运算,这种内积运算可通过定义在原空间中的函数来实现,甚至不必知道变换的形式。SLT指出,根据Hibert-Schmidt原理,只要一种运算满足Mercer条件,就可以作为内积使用。**0TiwxbMercer条件'2'''(,),()0(),)()()0KxxxxdxKxxxdxdx对于任意的对称函数它是某个特征空间中的内积运算的充要条件是,对于任意的且有(x,'(,)Kxx()0x2(),xdx(,''')()()0Kxxxxdxdx问题：什么样的函数能作为核函数？2.3支持向量机2数据线性不可分的情况对偶优化问题（D）:求解对偶问题的最优解后,支持向量机的决策函数为：1111max(,)2llliijijijiijyyKxx10,C0,1,,liiiiyil****1sgnsgn,lTiiiifxwxbyKxxb在最优分类面中采用适当的内积函数就可以实现某一非线性变换后的线性分类,而计算复杂度却没有增加。非线性支持向量机核函数分类不同的内积核函数将形成不同的算法,目前,在SVM理论研究与实际应用中,最常使用的有以下四类核函数:（1）线性核函数：（2）多项式核函数：,q是自然数。此时得到的支持向量机是一个q阶多项式分类器。（3）Gauss径向基核函数:。得到的支持向量机是一种径向基函数分类器。（4）Sigmoid核函数：a和t是常数，tanh是Sigmoid函数。221,exp,02iiKxxxx,tanh,TiiKxxaxxt,TiiKxxxx,(1)TqiiKxxxx2222222221||||/2||||/2||||/2||||/2||||/20||||||||221/1/0||||||||1/2211/01()!!!,!TkiixyxyxyTjxyjjxyjjTjjjxyjnnkjjnjeeeexyeejeexyjjejexxnnjk………，12111/2211/1||||1/2211/10,,!(),!kkkiijnnkjxjnnkjjnjjyynnjejxxxnnjkk…，………，映射函数为：………，RBF核函数•如何选择核函数，有哪些指导原则？•映射到高维空间就一定线性可分吗？如果高维空间仍然线性不可分，那该怎么办？•核函数的选择，没有明确的原则，一般根据具体问题，采用试探的方式。•核函数隐藏着一个到高维的映射，可能使得数据在高维变得线性可分，但并不不能保证映射到高维空间后一定线性可分。若仍然线性不可分，引入松弛变量、惩罚系数，放松约束，虽然仍然不能保证对训练数据线性可分，但它会根据我们给出的惩罚因子找到代价最小的分类器。《机器学习》-周志华著上有这样一句话：“幸运的是，如果原始空间是有限维，即属性有限，那么一定存在一个高纬度特征空间使样本可分。”但是没有给出证明或参考文献。两个问题回答高维空间中的最优分类面非线性问题——通过非线性变换将它转化为某个高维空间中的线性问题，在这个高维空间中寻找最优分类面。分类函数只涉及到训练样本之间的内积运算。因此,在高维空间中只需进行内积运算,这种内积运算可通过定义在原空间中的函数来实现,甚至不必知道变换的形式。在最优分类面中采用适当的内积函数就可以实现某一非线性变换后的线性分类,而计算复杂度却没有增加。SLT指出,根据Hibert-Schmidt原理,只要一种运算满足Mercer条件,就可以作为内积使用。目录线性不可分问题核函数松弛变量多输入多输出支持向量机回归算法支持向量机实现研究现状引入松弛变量27现在去考虑映射到高维也不可分的情况，原来的约束条件是其中c是一个参数为常量，ξ是需要优化的变量之一。nibxwyiTi,,1,1)(现在考虑到