svm算法简介.

svm(supportedvectormachine)概念：支持向量机是CorinnaCortes和Vapnik等于1995年首先提出的，其基本原理是（以二维数据为例）：如果训练数据是分布在二维平面上的点，它们按照其分类聚集在不同的区域。基于分类边界的分类算法的目标是，通过训练，找到这些分类之间的边界。对于多维数据（如N维），可以将它们视为N维空间中的点，而分类边界就是N维空间中的面，称为超面（超面比N维空间少一维）。线性分类器使用超平面类型的边界，非线性分类器使用超曲面。数据：线性可分&线性不可分•线性可分•线性不可分情况1：样本本质上是非线性可分的解决方法：核函数情况2：本质上线性，非线性由噪音导致强制使用非线性函数，会导致过拟合解决方法：软间隔两种情况线性可分定义：对于来自两类的一组模式,如果能用一个线性判别函数正确分类,则称他们是线性可分的。12,,....NxxxX轴Y轴123边界2x1x线性不可分线性可分情况•我们怎样才能取得一个最优的划分直线f(x)呢？bxwxfr)(0bxwr最大距离MaximumMarginal•从概率的角度上来说，就是使得置信度最小的点置信度最大•从实践的角度来说，这样的效果非常好•从误差的角度，误分次数≤（其中，是样本集合到分类面的间隔，R是空间中一个能完全包含样本数据的球的半径）误分次数一定程度上代表分类器的误差，间隔越大的解，它的误差上界越小。2)2(R函数间隔•定义函数间隔为：•接着，我们定义超平面（w,b）关于训练数据集T的函数间隔为超平面（w,b）关于T中所有样本点（xi,yi）的函数间隔最小值，其中，x是特征，y是结果标签，i表示第i个样本，有)()(xyfbxwyTimin定义函数间隔的原因一般而言，一个点距离超平面的远近可以表示为分类预测的确信或准确程度。在超平面确定的情况下，能够相对的表示点X到超平面的远近，而的符号与类标记y的符号是否一致表示分类是否正确，所以，可以用量的正负性来判定或表示分类的正确性和确信度，于是引出函数间隔概念。bxw0bxwbxw)(bxwy函数间隔的局限性上述定义的函数间隔虽然可以表示分类预测的正确性和确信度，但在选择分类超平面时，只有函数间隔还远远不够，因为如果成比例的改变w和b，如将他们改变为2w和2b，虽然此时超平面没有改变，但函数间隔的值却发生改变。我们可以对法向量w加些约束条件，使其表面看起来规范化，如此，我们引入了真正意义点到超平面的距离--几何间隔。几何间隔•在函数间隔的基础上，对w和b进行归一化，即为几何间隔：•这时如果成比例的改变w和b，几何间隔的值不会发生改变。wxfwbwxwwT)(~)()(xyfbxwyT因为wx+b=0，为了方便，我们可以按任意比例缩放w和b，而不会改变结果。我们可以添加这样的约束条件，这意味着可以先求出w和b的解，之后重新缩放这些参数，就可以轻易地满足这个条件。1w最大间隔分类器的定义•由于函数间隔的缺陷，不适合用来最大化一个量，因为在超平面固定以后，我们可以等比例地缩放w好b的值，这样可以使得的值任意打，亦即函数间隔可以在超平面不变的情况下被取得任意大。•而几何间隔则没有这个问题，因为除上这个分母，所以缩放w和b的时候几何间隔不会随之改变，它只随超平面的变动而变动，因此更加适合用其来定义最大距离。bxwxfT)(w因此，我们的最大间隔分类的目标函数可以定义为：事实证明这个约束是一个非凸性约束，我们需要避免，所以我们需要改变优化问题的表述方式。wˆmaxˆ)(..)()(.....bxwytsiTi1ˆ1)(min)()(bxwyiTi添加约束条件，这是一个隐含的缩放约束，因为假设你已经解出了w和b，并且发现最差情形的函数间隔是10或者其他值，这样，通过对w和b除以10或者其他值，我们可以将函数间隔变为1。此时，优化问题的表达式为：我们的优化问题转变成了一个凸优化问题221minw1)(..)()(.....bxwytsiTi目标函数是二次的，约束条件是线性的，所以这是一个凸二次规划问题，所以一定会存在全局的最优解，这个问题可以用现成的QP（quadraticprogramming）优化包或者二次程序软件进行求解。此外，由于这个问题的特殊结构，还可以通过拉格朗日对偶性变换到对偶变量的优化问题，即通过与原问题等价的对偶问题得到原始问题的最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：一者对偶问题往往更容易求解，二者可以自然的引入核函数，进而推广到非线性分类问题。最优问题的求解拉格朗日乘数法的扩展形式)()()(),,(11whwgwfwLiliiikii•minf(w)•s.t.gi(w)≤0i=1,2,...,khi(w)=0i=1,2,...,l（这里0指的是零向量）定义：),,(max)(0wLwip)(wfp当所有约束条件都满足时有对偶问题),,(maxmin)(min0,,abwLwpibwbw),,(minmax,0abwLdbwipd一般有，但是在某些特定条件下（KKT），这两个最优化问题会取相同的值。（经证明，我们求解的目标函数满足条件KKT条件）1.首先固定α，要让L关于w和b最小化，我们分别对w,b偏导并令其等于零，得到带回得到：凸二次规划问题求解问题转换为：由凸二次规划的性质能保证这样最优的向量a是存在的凸二次规划问题求解iiniixyw1•2.求对α的极大，即是关于对偶变量的优化问题（SMO优化算法--序列最小最优化算法）•然后根据•可求出最优的w和b，即最优超平面。2minmax1:1:iyiiyixwxwbTiTi一个简单的例子：4x3x2x1x2221234223341()()(444)2Qx1=(0,0),y1=+1x2=(1,0),y2=+1x3=(2,0),y3=-1x4=(0,2),y4=-1可调用Matlab中的二次规划程序，求得1,2,3,4的值，进而求得w和b的值。123412013/41/41120312002144231113,02224()3220wbgxxx线性不可分情况下情况1：样本本质上是非线性可分的解决方法：核函数)()(1iiniixywxxybxwxfiiniiT,)()()(1将分类函数变形得最终分类函数，为：根据线性可分情况下的结论：我们把横轴上断电a,b之间红色部分里的所有点定为正类，两边黑色部分定为负类，不能找到一个线性函数将两类正确分开。问题引入：但是能找到一条二次曲线将正负类分开，它的函数表达式可以写为：2210)(xcxccx23211xxzzzz问题只是它不是一个线性函数，但是，新建一个向量在z和a：210321cccaaaaazazx)(在任意维度的空间中，这种形式的函数都是一个线性函数（只不过其中的a,z是多维向量），因此，自变量z的次数不大于1。经过映射，判别函数为：bxxybxwxfiiniiinii)()()()(11原来在二维空间中一个线性不可分的问题，映射到四维空间后，变成了线性可分的。因此，这也形成了我们最初想解决线性不可分问题的基本思路---向高维空间转化，使其变得线性可分。而转化的关键的部分在于找到x到y的映射方法。遗憾的是，如何找到这个映射没有系统的方法，此外，在数据维度较大时，计算困难（我们对一个二维空间做映射，选择的新空间是原始空间的所有一阶和二阶的组合，得到了五个维度；如果原始空间是三维，那么我们会得到19维的新空间，这个数目是呈爆炸性增长的，这给的计算带来了非常大的困难，而且如果遇到无穷维的情况，就根本无从计算了）。)()(),(zxzxk•如果有一种方式可以在特征空间中直接计算内积〈φ(xi）·φ(x)〉，就像在原始输入点的函数中一样，就有可能将两个步骤融合到一起建立一个非线性的学习器，这样直接计算法的方法称为核函数方法，于是，核函数便横空出世了。•核函数：对所有x,z属于X，满足这里是从X到内积特征空间F的映射。分类函数为：优化问题的表达式：常见核函数–多项式核–线性核–高斯径向基函数核–Sigmoid核yxyxk),(对于核函数的选择，现在还缺乏指导原则。各种实验的观察结果表明，某些问题用某些核函数效果很好，用另一些很差，但一般来讲，径向基核函数是不会出现太大偏差的一种，首选。如果使用核函数向高维空间映射后，问题仍然是线性不可分的，怎么办？情况2：本质上线性，非线性由噪音导致强制使用非线性函数，会导致过拟合解决方法：软间隔想象我们有另一个训练集，它是方形的（负类），这单独的一个样本使得原本线性可分的问题变成了线性不可分的。这样类似的问题（仅有少数点线性不可分）。叫做“近线性可分”问题。我们会觉得，这个点可能是错误的，是噪声。所以我们会简单的忽略这个样本点，仍然使用原来的分类器，其效果丝毫不受影响。但这种对噪声的容错性是人的思维带来的，我们的程序没有，在此基础上寻找正负类之间的最大几何间隔，而几何间隔本身代表距离，是非负的，像这种情况会使得整个问题无解。这种解法其实也叫做“硬间隔”分类法，因为他硬性的要求所有样本点都满足和分类平面间的距离大于某个值。由上面的例子可以看出，硬间隔分类法其结果容易受少数点的控制。解决方法允许一些点到分类平面的距离不满足原先的要求。原先对样本点的要求是（意思是说离分类面最近的样本点函数间隔要比1大）：如果引入容错性，就给1这个硬性的阈值加一个松弛变量，即允许：因为松弛变量是非负的，因此最终的结果是要求间隔可以比1小。但是当某些点出现这种间隔比1小的情况时（这些点叫离群点），意味着我们放弃了对这些点的精确分类，而这对我们的分类器来说是种损失。但是放弃这些点也带来了好处，那就是使分类面不必向这些点的方向移动，因而可以得到更大的间隔。如何衡量损失•把损失加入到目标函数里的时候，就需要一个惩罚因子C，原来的优化问题变为：注意•并非所有的样本点都有一个松弛变量与其对应，实际上只有离群点才有。•松弛变量的值实际上标示出了对应的点到底离群多远，值越大，点越远。•惩罚因子决定了你有多重视离群点带来的损失，显然当所有离群点的松弛变量的和一定时，你定的C越大，对目标函数的损失也越大，此时就暗示着你非常不愿意放弃这些离群点，最极端的情况是你把C定为无限大，这样只要稍有一个点离群，目标函数的值马上变成无限大，马上让问题变成无解，这就退化成了硬间隔问题。注意•惩罚因子C不是一个变量，整个优化问题在解的时候，C是一个你必须事先指定的值，指定这个值以后，解一下，得到一个分类器，然后用测试数据看看结果怎么样，如果不够好，换一个C的值，再解一次优化问题，得到另一个分类器，再看看效果，如此就是一个参数寻优的过程，但这和优化问题本身不是一回事，优化问题在求解的过程中，C一直是定值。•尽管加入了松弛变量，但是优化问题的求解过程与硬间隔问题求解过程无异。用之前的方法将限制条件加入到目标函数中，得到新的拉格朗日函数，分析方法和前面一样，让L对w,b,ξ最小化将w带回目标函数并化简得到不过，由于我们得到而又有（作为拉格朗日乘数法的条件），因此有优化表达式变为和之前的结果对比一下，可以看到唯一的区别就是α多了一个上限C,而核函数化的非线性形式也是一样的，只要把xi,xj换成kxi,xj即可。加入松弛变量的优化问题求解过程先试着确定一下w，也就是确定图中的三条直线，看看间隔有多大，有多少离群点，算出目标函数。