支持向量机的数学原理.

支持向量机（1）线性支持向量机的求解重庆大学余俊良什么是支持向量机在右图中A图表示有两类的数据集，图B,C,D都提供了一个线性分类器来对数据进行分类？但是哪个效果好一些？什么是支持向量机•支持向量机（SVM）是90年代中期发展起来的基于统计学习理论的一种机器学习方法，通过寻求结构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较少的情况下，亦能获得良好统计规律的目的。在深度学习出现之前，SVM一直霸占着机器学习老大哥的位子。他的理论很优美，各种变种改进版本也很多，比如latent-SVM,structural-SVM等。通俗来讲，它是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，即支持向量机的学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。支持向量机的学习算法是求解凸二次规划的最优化算法。什么是支持向量机•支持向量机学习方法包含构建由简至繁的模型：线性可分支持向量机、线性支持向量机及非线性支持向量机。当训练数据线性可分时，通过硬间隔最大化，学习一个线性的分类器，即线性可分支持向量机；当训练数据近似可分时，通过软间隔最大化，也学习一个线性的分类器，即线性支持向量机；当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性支持向量机。•第一部分线性可分支持向量机与硬间隔最大化线性可分支持向量机•下面举个简单的例子，一个二维平面(一个超平面，在二维空间中的例子就是一条直线)，如下图所示，平面上有两种不同的点，分别用两种不同的颜色表示，一种为红颜色的点，另一种则为蓝颜色的点，红颜色的线表示一个可行的超平面。•从右图中我们可以看出，这条红颜色的线把红颜色的点和蓝颜色的点分开来了。而这条红颜色的线就是我们上面所说的超平面，也就是说，这个所谓的超平面的的确确便把这两种不同颜色的数据点分隔开来，在超平面一边的数据点所对应的y全是-1，而在另一边全是1。线性可分支持向量机接着，我们可以令分类函数：显然，如果f(x)=0，那么x是位于超平面上的点。我们不妨要求对于所有满足f(x)0的点，其对应的y等于-1，而f(x)0则对应y=1的数据点。当然，有些时候，或者说大部分时候数据并不是线性可分的，这个时候满足这样条件的超平面就根本不存在(不过关于如何处理这样的问题我们后面会讲)，这里先从最简单的情形开始推导，就假设数据都是线性可分的，亦即这样的超平面是存在的。线性可分支持向量机如何确定分类函数中的两个参数w和b？寻找两条边界端或极端划分直线中间的最大间隔（之所以要寻最大间隔是为了能更好的划分不同类的点），从而确定最终的最大间隔分类超平面和分类函数；进而把寻求分类函数的问题转化为对w，b的最优化问题。函数间隔一般而言，一个点距离超平面的远近可以表示为分类预测的确信或准确程度。在超平面w*x+b=0确定的情况下，|w*x+b|能够相对的表示点x到距离超平面的远近，而w*x+b的符号与类标记y的符号是否一致表示分类是否正确，所以，可以用量y*(w*x+b)的正负性来判定或表示分类的正确性和确信度。于此，我们便引出了定义样本到分类间隔距离的函数间隔functionalmargin的概念。我们定义函数间隔functionalmargin为：定义超平面(w，b)关于训练数据集T的函数间隔为超平面(w，b)关于T中所有样本点(xi，yi)的函数间隔最小值，其中，x是特征，y是结果标签，i表示第i个样本，有：几何间隔函数间隔虽然可以表示分类预测的正确性和确信度，但在选择分类超平面时，只有函数间隔还远远不够，因为如果成比例的改变w和b，如将他们改变为2w和2b，虽然此时超平面没有改变，但函数间隔的值f(x)却变成了原来的2倍。其实，我们可以对法向量w加些约束条件，使其表面上看起来规范化，如此，我们很快又将引出真正定义点到超平面的距离--几何间隔的概念。对于给定的训练数据集T和超平面（w,b），定义超平面关于样本点(x,y)的几何间隔为：定义超平面(w，b)关于训练数据集T的几何间隔为超平面(w,b)关于T中所有样本点(xi，yi)的几何间隔最小值，r=minri(i=1,2,…n)支持向量和间隔边界在线性可分情况下，训练数据集的样本点与分离超平面距离最近的样本点的实力称为支持向量，支持向量是使约束条件式y(i)(wTx(i)+b)≥1,i=1,2,3……m中等号成立的的点。在决定分离超平面时只有支持向量起作用，而其他实例点并不起作用间隔最大化支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面，对线性可分的数据集而言，线性可分分离超平面有无穷多个（等价于感知机），但是几何间隔最大的分离超平面是唯一的。间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类，也就是说，不仅将正负实例分开，而且对最难分的实例点（离超平面最近的点）也有足够大的确信度将它们分开，这样的超平面应该对未知的新实例有很好的分类预测能力。间隔最大化按照前面的分析，对一个数据点进行分类，当它的间隔越大的时候，分类的可信度越大。对于一个包含n个点的数据集，我们可以很自然地定义它的间隔为所有这n个点的间隔值中最小的那个。于是，为了使得分类的可信度高，我们希望所选择的超平面能够最大化这个间隔值。间隔最大化下面考虑如何求得一个几何间隔最大的分离超平面，即最大间隔分离超平面，具体地，这个问题可以表示为下面的约束最优化问题：*此处公式有问题，约束条件左边应除以一个||w||即我们希望最大化超平面(w,b)关于训练数据集的几何间隔，约束条件表示的是超平面(w,b)关于每个训练样本点的几何间隔至少是γ。考虑到几何间隔和函数间隔的关系式，可将这个问题改写为：间隔最大化函数间隔的取值并不影响最优化问题的解。事实上，假设将w和b按比例改变为λw和λb,这时函数间隔成为λγ’。函数间隔的这一改变对上面最优化问题的不等式约束，对目标函数的优化也没有影响，也就是说，它产生一个等价的最优化问题。这样，就可以取γ’=1,将γ’=1代入前面的最优化问题，也即是将离超平面最近的点的距离定义为1/||w||，由于最大化1/||w||和最小化1/2||w||2等价，于是得到下面的线性可分支持向量机学习的最优化问题：这是一个凸二次规划问题。如果求出了该问题的解w*、b*,那么就可以得到最大间隔分离平面w*x+b*=0及分类决策函数f(w)=sign(w*x+b*),即线性可分支持向量机模型。关于凸优化的一些简单概念凸集的定义为：其几何意义表示为：如果集合C中任意2个元素连线上的点也在集合C中，则C为凸集。其示意图如下所示：关于凸优化的一些简单概念凸函数的定义为：其几何意义表示为函数任意两点连线上的值大于对应自变量处的函数值，示意图如下：常见的凸函数有：指数函数族；非负对数函数；仿射函数；二次函数；常见的范数函数；关于凸优化的一些简单概念凸优化问题（OPT）的定义为：即要求目标函数是凸函数，变量所属集合是凸集合的优化问题。或者目标函数是凸函数，变量的约束函数是凸函数（不等式约束时），或者是仿射函数（等式约束时）。*f(x)称为仿射函数，如果它满足f(x)=ax+b,a∈Rn,b∈Rn,x∈Rn凸二次规划问题求解原始问题转换为形式后，原问题成了一个凸二次规划问题。解此问题除了用解决QP问题的常规方法之外，还可以通过求解对偶问题得到最优解，这就是线性可分条件下支持向量机的对偶算法，这样做的优点在于：一者对偶问题往往更容易求解；二者可以自然的引入核函数，进而推广到非线性分类问题。首先构建拉格朗日函数，通过给每一个约束条件加上一拉格朗日乘值，即引入拉格朗日乘子，如此我们便可以通过拉格朗日函数将约束条件融和到目标函数里去。条件极值与拉格朗日乘数法例：要设计一个容量为V的长方体开口水箱，试问水箱的长、宽、高各为多少时，其表面积最小？为此，设水箱的长、宽、高分别为x,y,z,则表面积为依题意，上述的长、宽、高不仅要符合定义域的要求：x0,y0,z0,而且还须满足条件这类附有约束条件的极值问题称为条件极值条件极值问题的一般形式是等式约束：即在条件组：的限制下，求目标函数的极值。xyyzxzS)(2Vxyz)(,,2,1,0),,,(21nmmkxxxnk),,,(21nxxxfy条件极值与拉格朗日乘数法条件极值的一种求解方法是代入法.，将条件极值化为无条件极值。例如，在上述例子中，由条件解出代入目标函数中，得到然后求这个函数的无条件极值。然而在一般情形下，这种方法往往是行不通的，因为要从条件组解出m个变元常常是不可能的.下面介绍的拉格朗日乘数法是求条件极值的一种有效方法.VxyzxyVzxyyzxzS)(2xyxyVS)11(2)(,,2,1,0),,,(21nmmkxxxnk条件极值与拉格朗日乘数法可确定函数则问题等价于一元函数的极值问题,由极值的必要条件，知极值点x0必满足因故有即记极值点必满足想法：把上面的条件极值点转化为一般极值点问题,下0),(在条件yx.),(的极值求函数yxfz0),(yx,)(xgy)())(,(xhxgxfz0)(),(),()(000000xgyxfyxfxhyx,yxg0yxyxffyyxxffyyxxff0xxf0yyf0),(yx条件极值与拉格朗日乘数法构造一个函数使得其极值点就是上面函数的条件极值点引入辅助函数则极值点满足:辅助函数L称为拉格朗日(Lagrange)函数.利用拉格朗日函数求极值的方法称为拉格朗日乘数法.),(),(),,(yxyxfyxL条件极值与拉格朗日乘数法利用拉格朗日乘数法求函数在条件下的极值步骤如下：1.作拉格朗日函数2.求拉格朗日函数的极值先求解拉格朗日函数的偏导数构成的方程组再考察驻点是否是极值点),(yxfz0),(yx),(),(),,(yxyxfyxL拉格朗日对偶性拉格朗日对偶性拉格朗日对偶性拉格朗日对偶性拉格朗日对偶性拉格朗日对偶性拉格朗日对偶性对偶算法求解对偶算法求解对偶算法求解对偶算法求解对偶算法求解对偶算法求解对偶算法求解对偶算法求解对偶算法求解对偶算法求解对偶算法求解对偶算法求解对偶算法求解对偶算法求解最大间隔分离超平面的存在唯一性最大间隔分离超平面的存在唯一性•第二部分线性支持向量机与软间隔最大化线性支持向量机在第一部分最开始讨论支持向量机的时候，我们就假定，数据是线性可分的，亦即我们可以找到一个可行的超平面将数据完全分开。然而，这只是一种理想状态，通常情况下数据往往不是线性可分的，因为数据中一般存在噪声。对于这种偏离正常位置很远的噪声点，我们称之为outlier，在我们原来的SVM模型里，outlier的存在有可能造成很大的影响，因为超平面本身就是只有少数几个supportvector组成的，如果这些supportvector里又存在outlier的话，其影响就很大了。线性支持向量机用黑圈圈起来的那个蓝点是一个outlier，它偏离了自己原本所应该在的那个半空间，如果直接忽略掉它的话，原来的分隔超平面还是挺好的，但是由于这个outlier的出现，导致分隔超平面不得不被挤歪了，变成途中黑色虚线所示（这只是一个示意图，并没有严格计算精确坐标），同时margin也相应变小了。当然，更严重的情况是，如果这个outlier再往右上移动一些距离的话，我们将无法构造出能将数据分开的超平面来。线性支持向量机为了处理这种情况，SVM允许数据点在一定程度上偏离一下超平面。例如上图中，黑色实线所对应的距离，就是该outlier偏离的距离，如果把它移动回来，就刚好落在原来的超平面上，而不会使得超平面发生变形了。线性支持向量机线性支持向量机线性支持向量机学习的对偶算法学习的对偶算法学习的对偶算法学习的对偶算法学习的对偶算法学习的对偶算法学习的对偶算法软间隔下的