机器学习算法总结_SVM

第5章支持向量机5.1引言支持向量机(SupportVectorMachine，简称SVM)是于1995年由Cortes和Vapnik首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。它通过寻求结构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较少的情况下，亦能获得良好统计规律的目的。支持向量机是一种二类分类模型。其基本模型定义为特征空间上的间隔最大的线性分类器，即支持向量机的学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。支持向量机的学习算法就是求解凸二次规的最优化算法。5.2线性可分支持向量机5.2.1线性可分线性分类器是最简单也很有效的分类器形式。在一个线性分类器中，可以看到SVM形成的思路，并接触很多SVM的核心概念。用一个二维空间里仅有两类样本的分类问题来举个小例子。如图1.1所示1C和2C是要区分的两个类别，在二维平面中它们的样本如图1.1所示。中间图5.1二维空间两样本分类问题的直线就是一个分类函数，它可以将两类样本完全分开。一般的，如果一个线性函数能够将样本完全正确的分开，就称这些数据是线性可分的，否则称为非线性可分的。线性函数，在一维空间里就是一个点，在二维空间里就是一条直线，在三维空间里就是一个平面，可以如此想象下去，如果不关注空间的维数，这种线性函数还有一个统一的名称——超平面（HyperPlane）！实际上，一个线性函数是一个实值函数（即函数的值是连续的实数），而我们的分类问题（例如这里的二元分类问题——回答一个样本属于还是不属于一个类别的问题）需要离散的输出值，例如用1表示某个样本属于类别1C，而用0表示不属于（不属于1C也就意味着属于2C），这时候只需要简单的在实值函数的基础上附加一个阈值即可，通过分类函数执行时得到的值大于还是小于这个阈值来确定类别归属。例如我们有一个线性函数()gxwxb（5-1）我们可以取阈值为0，这样当有一个样本ix需要判别的时候，我们就看()igx的值。若()0igx，就判别为类别1C，若()0igx，则判别为类别2C。此时，也等价于给函数()igx附加一个符号函数()sign，即()sgn[()]fxgx是我们真正的判别函数。5.2.2分类间隔显然，图5.1中间那条分界线并不是唯一的，我们把它稍微旋转一下，只要不把两类数据分错，仍然可以达到上面说的效果，稍微平移一下，也可以（如图5.2所示）。此时就牵涉到一个问题，对同一个问题存在多个分类函数的时候，哪一个函数更好呢？显然必须要先找一个指标来量化“好”的程度，通常使用的都是叫做“分类间隔”的指标。如图5.3，方形点和圆形点代表两类样本,H为分类线，1H和2H分别为过各类中离分类线最近的样本且平行于分类线的直线,它们之间的距离叫做分类间隔(margin)。所谓的最优分类线就是要求分类线不但能将两类正确分开，而且使得分类间隔最大。而将这一理论推广到高维空间，最优分类线就变为最优分类面。我们将问题延伸到高维数据上，并进行形式化的表示。假设给定一个特征空间上的训练集：𝑇={(𝑥1,𝑦1),(𝑥2,𝑦2)⋯(𝑥𝑛,𝑦𝑛)}其中，xi∈χ=Rn,yi∈γ={+1,−1},i=1,2,⋯,N，xi为第i个特征向量，也称为实例，yi为xi的类标记，(xi,yi)称为样本点，假设训练数据集是线性可分的。图5.2不同的分类线图5.3分类间隔定义5-1（函数间隔）对于给定的训练数据集𝑇和超平面(,)wb，定义超平面(,)wb关于样本点(,)iixy的函数间隔为ˆ()iiiywxb（5-2）定义超平面(,)wb关于训练数据集T的函数间隔为超平面(,)wb关于T中所有样本点(,)iixy的函数间隔之最小值，即1,,ˆˆminiiN（5-3）函数间隔可以表示分类预测的正确性。如果考虑w和b，如果同时成比例的改变为2w和2b。因为我们要求解的是0Twxb，同时扩大w和b对结果是无影响的。但是，函数间隔ˆ却成为了原来的2倍。因此，我们需要对其法向量w加一些约束，对其进行规范化。我们可以取1w，这样函数间隔便也就确定了。由这一事实到处几何间隔的概念。定义5-2（几何间隔）对于给定的训练数据集𝑇和超平面(,)wb，定义超平面(,)wb关于样本点(,)iixy的函数间隔为（5-4）定义超平面(,)wb关于训练数据集T的函数间隔为超平面(,)wb关于T中所有样本点(,)iixy的几何函数间隔之最小值，即（5-5）从前面的两个定义我们可以看到，函数间隔和几个间隔有下面的关系（5-6）实际上，i就是样本点ix到超平面(,)wb的距离。同时，当1w时，函数间隔与几何间隔是相等的。也就是说，前面提到的对ˆi的规范化的结果就是几何间隔。此时如果同时扩大w和b，w也会随之扩大多少倍，对于最终的几何间隔并无影响。5.2.3间隔最大化支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。我们不需要考虑所有的点都必须远离超平面，我们关心求得的超平面能够让所有点中离它最近的点具有最大间距。我们可以对该问题进行形iiiwbyxww1,,miniiNˆw式化的表示：,ˆmaxwbw（5-7）s.t.ˆ(),1,2,,iiywxbiN（5-8）函数间隔ˆ的取值并不影响最优化问题的解。事实上，假设将w和b按比例改变为实际上，i就是样本点ix到超平面(,)wb的距离。同时，当1w时，函数间隔与几何间隔是相等的。也就是说，前面提到的对ˆi的规范化的结果就是几何间隔。此时如果同时扩大w和b，w也会随之扩大多少倍，对于最终的几何间隔并无影响。不妨对ˆ做一些限制，以保证我们的解是唯一的。这里为了简便我们取ˆ1，将离超平面最近的点的距离定义为。由于求的最大值相当于求的最小值。我们可以将（1-7）改写为下面的式子：（5-9）s.t.()1,1,2,,iiywxbiN（5-10）这是一个凸二次规划（ConvexQuadraticProgramming）问题。5.2.4拉格朗日对偶拉格朗日对偶性常用于带约束的最优化问题中，其将原始问题转化为对偶问题，并通过解对偶问题而得到原始问题的解。考虑约束最优化问题min()nxRfx（5-11）s.t.()0,i=1,2,,kicx（5-12）()0,j=1,2,,ljhx（5-13）引进一般的拉格朗日函数11(,,)()()()kliijjijLxfxcxhx（5-14）这里i和j是拉格朗日乘子，由于()icx在这里是不等式约束，因此需要考虑下面的函数：,:0()max(,,)ipxLx（5-15）1w1w212w2,1min2wbw这里的p代表primal，即原始问题。因此，(),()+pfxxx满足原始问题约束，其它（5-16）这样，我们原来要求的min()nxRfx就可以转换成求min()npxRx，进而,:0min()=minmax(,,)nnipxRxRxLx（5-17）为了方便，我们用*p来表示min()npxRx，定义原始问题的最优值为*min()npxRpx（5-18）但是，对于上式，如果直接求解，首先面对的是两个参数，且i又是不等式约束，然后在x上求其最小值，这个问题的求解较为麻烦，我们可以先考虑其对偶问题。定义一个(,)D，使得(,)min(,,)nDxRLx（5-19）D的意思是对偶，考虑极大化(,)D，则有,:0,:0max(,)maxmin(,,)niiDxRLx（5-20）这个问题是原问题的对偶问题，定义对偶问题的最优值*,:0max(,)iDd（5-21）在一般情况下**,:0,:0maxmin(,,)minmax(,,)nniixRxRdLxLxp（5-22）当满足后面的条件时则会有**dp：假设函数()fx和()icx是凸函数，()jhx是仿射函数；并且假设不等式约束()icx是严格可行的，此时一定存在*x和**,使得*x是原始问题的解，**,是对偶问题的解。另外，*x和**,满足Karush-Kuhn-Tucker（KKT）条件：***(,,)0xLx（5-23）***(,,)0Lx（5-24）***(,,)0Lx（5-25）**()0,1,2,,iicxik（5-26）*()0,1,2,,icxik（5-27）*0,1,2,,iik（5-28）*()0,1,2,,jhxik（5-29）其中，式（5-26）称为KKT的对偶互补条件（KKTdualcomplementarity）。这个条件隐含了如果*0i，那么*()0icx。5.2.5最优间隔分类器重新回到（5-9）及条件（5-10）表示的优化问题。首先看图5.4。如图5.4，H2是最大间隔超平面，则在H1和H3上的点就是函数间隔为1的点，这些点对应的系数0i，其他点都是0i。如图中在H1和H3上的四个点，被称为支持向量，这也正是支持向量机名称的由来。随后，构造拉格朗日函数，引入拉格朗日乘子0,1,2,,iiN，定义拉格朗日函数：2111(,,)()2NNiiiiiiLwbwywxb（5-30）根据拉格朗日对偶性，可以先求原始问题的对偶问题：,maxmin(,,)wbLwb首先求(,,)Lwb的最小值，此时i可视为固定值。将(,,)Lwb对,wb求偏导并令其等于0。1(,,)0NwiiiiLwbwyx（5-31）1(,,)0NbiiiLwby（5-32）得到1Niiiiwyx（5-33）将（5-33）回代入（5-30）中可得：111111(,,)()(())2nnnNnijijijiijjjiiijijiLwbyyxxyyxxb图5.4支持向量1111()2nnnijijijiijiyyxx即最后可以得到1111(,,)()2nnnijijijiijiLwbyyxx下面是极大化过程，即将(,,)Lwb对求其极大1111max()2nnnijijijiijiyyxx（5-34）s.t.10Niiiy（5-35）0,=1,2,,iiN（5-36）在5.2.4小节中提到了原始问题与对偶问题等价且同解的条件，如果求出了i（即*），根据公式（5-33）即可求出*w，然后代入公式（5-37）可求得*b**1()njijijibyyxy（5-37）最终再将结果回代到（5-1）中的公式中，可以得到分类决策的函数**1()(())nijjigxsignyxxb（5-38）从上式可以看出，当引入了拉格朗日乘子i之后，不需要再求出w才能分类，只需将新来的样本和训练数据中的所有样本做内积和即可。在实际运算中，只有支持向量对应的0i，其他情况下0i。因此，我们只需求新来的样本和支持向量的内积，然后运算即可。5.3非线性支持向量机在实际应用中，有时分类问题是非线性的，这时可以使用非线性支持向量机。本节中利用核技巧构造非线性支持向量机。5.3.1非线性分类问题非线性分类问题是指通过利用非线性模型才能很好地进行分类的问题。如图5.5所示，正方形和原形分别代表正负实例点。5.5左图中，无法用直线将正负实例正确分开，但是可以用抛物线（如图5.5右图）将他们正确分开。设原空间为2R，(1)(2)(,)Txxx，新空间为2YR，(1)(2)(,)TyyyY，定义从原空间到新空间的映射