SVM分类器中的最优化问题

SVM分类器中的最优化问题电子工程学院周娇1121摘要支持向量机（SupportVectorMachines,SVM）是一种分类方法，它通过学会一个分类函数或者分类模型，该模型能把数据库中的数据项映射到给定类别中的某一个，从而可以用于预测未知类别数据的类别。所谓支持向量机，顾名思义，分为两个部分了解：一，什么是支持向量（简单来说，就是支持或支撑平面上把两类类别划分开来的超平面的向量点）；二，这里的“机（machine,机器）”便是一个算法。支持向量机是基于统计学习理论的一种机器学习方法，通过寻求结构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较少的情况下，亦能获得良好统计规律的目的。在本文中，主要介绍了如何通过求解最优化问题来得到SVM分类器的最佳参数，使得SVM分类器的性能最好。一、线性分类如图（1）,在二维平面上有两种不同的数据点，分别用红色和蓝色来表示，红颜色的线就把这两种不同颜色的数据点分开来了。这些数据点在多维空间中就是向量，红颜色的线就是一个超平面。

假设xt=(xilfxi2,......,xinj)T是加维空间中的一个数据点，其中Xilfx.2f......，兀”是心这个数据点的加个特征，令z=/(xj,y=h(z)1,zN0）‘=/?（?）=-1?z<o在图(1)中，处在红线左边的数据点，其y值为T,反之，处在红线右边的数据点其y值为1o这样，根据y的值就把心这个数据点分类To那么分类的重点就在如何构造z=/(£)这个函数。设图(1)中的超平面(即红线)其表达式为a/X+b=O,则直观上卑斗表示数据点到超平面的几何间隔，去掉分子的绝对值11^II就有了正负性，/是法向量，b是截距。eP+b表示了数据点到超

平面的函数间隔，如图(2)所示。由于兀",……，心是兀这个数据点的川个特征，0丫•就是对兀特征进行线性组合，即给每一个特征加上一个权重。因为y=h(z)=i1z<0，z=/(£)二力1+〃，y-1或T分别表示两个类别，而7的正负决定它该分到哪个类别，所以我们以乙和y符号是否一致来判断分类是否正确。令〜Yi0Yi二——则彳>0表示分类正确，否则分类错误。那么我们需要求解出°卩和b这两个参数。二、最大间隔分类器对一个数据点进行分析，当它到超平面的几何间隔越大的时候，分类正确的把握率越大。对于一个包含n个点的数据集X(X1,X2,,Xn),我们可以很自然地定义它的间隔为所有这n个点的间隔中最小的那个。于是，为了使得分类的把握尽量大，我们希望所选择的超平面能够最大化这n个间隔值。令Y-minyi,i二1,2,所以最大间隔分类器的目标函数为max丫

条件为yjOy.O工y条件为yjOy.O工y其中Y二VW即&二工，由于3和b的值可以缩放，令y=1,则最优化问题转为：max.Yi（）M1,i-1,2,……，n通过求解这个最优化问题，我们可以得到一个最大间隔分类器，如图（2）所示，中间的红线为最优超平面，另外两条虚线到红线的距离都等于丄，即丫=1o从原始问题到对偶问题及求解。原规划即：max-YiO工1,i二1,2,•,n由于求丄的最大值相当于求¥的最小值，所以上述问题等价于:min?2y()-1>0y()-1>0,i=1,2,容易证明这是个凸优化问题。构造Lagrange函数将其变为无约束的最优化问题，给每一个约束条件加上一个Lagrange乘子a二（aba2,,an）T（其中TOC\o"1-5"\h\zaiM0,i-1,2,*,n）:I畀ZX(O.b.a)=-1|ft)||2_^a.(y.(a>rx.+b)_1)2/=!max6(.(o)=aiM0容易验证，当某个约束条件不满足时，例如yi（coTxi+b）-l<0,那么显然有畑=+8（此时a：二+*）。而当所有约束条件都满足时，则有（此时ai=0）,亦即我们最初要最小化的量。因此，在要求约束条件得到满足的情况下最小化丄II如f,实际上等价于直接最小2化&少）（因为如果约束条件没有得到满足，会等于无穷大，自然不会是我们所要求的最小值。）具体写出来，我们现在的目标函数变成了：*min:,b二minmax二p,ba,0这里用P冬表示这个问题的最优值，也是原问题的最优值。现在我们把最小和最大的位置交换一下：•*maxmin二qaj0,b式（）是（）的对偶问题，p*是gbg的上确界（即最小上界），q*是的下确界（最大下界），显然p*q*,当且仅当原问题满足Slater条件（即存在Xi使得原规划的约束条件严格成立，即冶（）-1=0）时，等号成立。上文已说明此优化为凸优化，所以Kuhn-Tucker条件为某个数据点x*是最优解的充要条件。所以当Xi满min足KKT条件时，Xi才是，b的最优解。当同时满足Slater条件和KKT条件时，原规划可以取到最优值且为卩*（p*二q*）。求解过程：要求解这个对偶问题，先求出心b,⑵关于3,b的最小值，再对a求最大。1、先把a当做常数，求出a）关于3,b的偏导（即求，b）*/Egba）关于3,b求最小值，也是极值?Lvnc•応二3_右二1QiYixi=0?Lvnn?b二-5=iaiVi二o3二》；二［ajyjX,叽a“i二0将式（）和（）代入到式（）中

!“£(◎氏么丿二牙11e『一工y(ygp+b)-1)Lr=i-?3丁10-col：二1aiYiXj-bE：二1aWi+E；二•(ai二0斗=1aiyjXj-3吃;=1aiYiXj+斗=1aiEn1✓v'n\T^ni二1ai-2^i二1aiViXi)力i二1aiyixi'v1"pn丨2^i二2j二1ai『iajYjX|Xj2、从式（）可以看出只包含a二（aba2,,an）T这一个变量（用来训练SVM分类器的数据集X（X[,X2,,xj和每个数据点的类别Vi是已知的）。对式（）求关于a的最大值，根据式（）得到最优化问题：max=1i-2^i二2j二1aMa川」凶xi•斗二1QiVi二0Q；M0,i—1,2,,n运用SM0算法（序列最小最优化算法）求以上最优化问题，此算法太繁琐，可以查找SMO算法的资料来了解，此处不赘述。3、求出a—（a1,2?*,Qn）丫之后,根据式（）求出co;b是截距，如图（3）所示，红线是分割超平面，另外两条虚线到红

线的距离相等，为两种数据点到分割平面的最小距离，贝心b二一z(bi+b2)二-z(min+max)一i：y；=1i：yj1()图(4)()图(4)至此，这个分类器的参数都已经解出来了。四、使用松弛变量处理离群点数据本身是线性结构，但是由于噪声的影响，导致一些数据点偏离正常位置很远，这样的数据点就叫做离群点。图（4）就是数据中有离群点存在的情况。在图（4）中，因为离群点（用黑圈圈起来的蓝色的数据点）的存在，导致分类的超平面发生了偏离。分类的超平面本应该是中间的那根红线，但是由于离群点的存在，发生了偏差，变成了中间那条黑色的虚线。这样一来，当我们用这个学习好的SVM分类器对新的数据点进行分类的时候就有可能发生误判。为了解决这个问题，我们将离群点移回本来的位置，这就通过在约束条件中添加松弛变量(/=1,2,……，n)来实现，5就对应于数据点兀允许偏离的距离。原来的约束条件式()就变成YiO-5M,i-1,2,,n()但是5的取值也必须受到约束，即斗二Q要尽可能小。那么目标函数就由()变为：min学+0斗二〔Ci()B是一个参数，用来控制目标函数中两项(即寻求间隔最大的分割超平面和保证数据点偏差量最小)的权重。那么这个最优化问题变为：min孑+0斗二0.YiO-c；1,i=1,2,,nCjM0,i—1,2,n

其求解方法与第三节中的方法一致。五、存在的问题这样构建的分类器对于线性可分的情况很有效，但是对于线性不可分的情况，例如图（6）中的情况，其效果就不那么好了。需要去构造一些新的最优化问题来对非线性可分的数据进行分类。图(6)参考文献1＞《支持向量机导论》,［美］NelIoCristianini/JohnShawe-Taylor着；2、《StatisticaIbehaviorandconsistencyofcla