资源描述：
《SVM分类器中的最优化问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、SVM分类器中的最优化问题电子工程学院周娇201622021121摘要支持向量机（SupportVectorMachines,SVM）是一种分类方法，它通过学会一个分类函数或者分类模型，该模型能把数据库中的数据项映射到给定类别屮的某一个，从而可以用于预测未知类别数据的类别。所谓支持向量机，顾名思义,分为两个部分了解：一，什么是支持向量（简单来说，就是支持或支撑平面上把两类类别划分开来的超平面的向量点）；二，这里的“机（machine,机器）”便是一个算法。支持向量机是基于统计学习理论的一种机器学习方法，通过寻求结构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达
2、到在统计样本量较少的情况下，亦能获得良好统计规律的目的。在本文中,主要介绍了如何通过求解最优化问题来得到SVM分类器的最佳参数，使得SVH分类器的性能最好。一、线性分类如图（1）,在二维平面上有两种不同的数据点，分别用红色和蓝色来表示，红颜色的线就把这两种不同颜色的数据点分开来了。这些数据点在多维空间中就是向量，红颜色的线就是一个超平面。假设兀•=（勺心2,……，心J是加维空间中的一个数据点，其中xi[fxi2,……，兀讪是科这个数据点的加个特征，令Z=f（x.）,y=h（z）y*（Z）={][宾秩（1.1）在图（1）屮，处在红线左边的数据点，其y值为-1,反Z,处在红线右边的数据点
3、其y值为1。这样，根据y的值就把兀•这个数据点分类了。那么分类的重点就在如何构造Z=/（£・）这个函数。设图（1）中的超平面（即红线）其表达式为^X+b=0,则z=/(xjxi+b(1.2)T直观上0L护表示数据点到超平面的几何间隔，去掉分子的绝对值就有了正II0II负性，/是法向量，b是截距。cJx^b表示了数据点到超平面的函数间隔，如图（2）所示。由于勺，兀・2,……，•筍“是兀•这个数据点的加个特征，iz/x,就是对兀特征进行线性组合，即给每一个特征加上一个权重。因为y=/?（z）=｛匕,z=/（乞）二以兀+b,y=l或T分别表示两个类别，而z的正负决定它该分到哪个类别，所以我
4、们以z和y符号是否一致来判断分类是否正确。令力（力匕+/?）(1.3)〜•Yi=Til则P〉0表示分类止确，否则分类错误。那么我们需要求解出⑵卩和b这两个参数。二、最大间隔分类器对一个数据点进行分析，当它到超平面的几何间隔越大的时候，分类正确的把握率越大。对于一个包含n个点的数据集x（xlfx2xn）,我们可以很自然地定义它的间隔为所有这n个点的间隔中最小的那个。于是，为了使得分类的把握尽量大，我们希望所选择的超平面能够最大化这n个间隔值。令y=miriYi,i=1,2,,n(2.1)所以最大间隔分类器的目标函数为maxy(2.2)条件为(2.3)(2.4)力（0匕+b）>Y,i=1
5、2……,n其中y=PI
6、e5，即卩=—，由于3和”的值可以缩放，令y=l,则最\0）II优化问题转为：(2.5)皿亠II/IIs.t.yt>1,i=1,2,,n(2.6)通过求解这个最优化问题，我们可以得到一个最大间隔分类器，如图(2)所示，中间的红线为最优超平面，另外两条虚线到红线的距离都等于^―,即Tily=lo三、从原始问题到对偶问题及求解。原规划即：max(3.1)1011s.t.(a/xi>1,i=1,2,,n(3.2)由于求7—的最大值相当于求
7、ll^r
8、
9、2的最小值，所以上述问题等价于：1011212minT
10、/
11、
12、(3.3)2s.t.ytcJxi+/?^—1>0,i
13、=1,2,,n(3.4)容易证明这是个凸优化问题。构造Lagrange函数将其变为无约束的最优化问题，给每一个约束条件加上一个Lagrange乘子a=(alfa2,,an)T(其中>0,i=1,2,,n):1”L(co,b,a)=—
14、
15、ft>
16、
17、2一工0.(儿(/兀・+/?)-1)(3.5)2：=令&(少)二maXa左oL(a),b.a)(3.6)容易验证，当某个约束条件不满足时，例如yi(coTxi+/?)-!<0,那么显然有0(0=+8(此时©=+8)。而当所有约束条件都满足时，则有次血)=*
18、
19、(〃『(此时他二0),亦即我们最初要最小化的量。因此，在要求约束条件得到满足的情况
20、下最小化丄恤『，实际上等价于直接最小化0G)(因为如果约束条件没有得到满足，0(CD)2会等于无穷大，自然不会是我们所要求的最小值。)具体写出来，我们现在的目标函数变成了：minCOfb0((d)=minmaxa.>0COfbL(co.b.a)=p*(3.7)这里用p*表示这个问题的最优值，也是原问题的最优值。现在我们把最小和最大的位置交换一下：(3.8)maxminLfco.b.a)=q*咔o(ofb式（3.8）是（3.7）的对偶问题,p*是L（e,b,
