SVM分类器中的最优化问题

1、SVM分类器中的最优化问题 电子工程学院 周娇 201622021121摘要支持向量机（Support Vector Machines,SVM）是一种分类方法，它通过学会一个分类函数或者分类模型，该模型能把数据库中的数据项映射到给定类别中的某一个，从而可以用于预测未知类别数据的类别。所谓支持向量机，顾名思义，分为两个部分了解：一，什么是支持向量（简单来说，就是支持或支撑平面上把两类类别划分开来的超平面的向量点）；二，这里的“机（machine，机器）”便是一个算法。支持向量机是基于统计学习理论的一种机器学习方法，通过寻求结构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达

2、到在统计样本量较少的情况下，亦能获得良好统计规律的目的。在本文中，主要介绍了如何通过求解最优化问题来得到SVM分类器的最佳参数，使得SVM分类器的性能最好。一、 线性分类如图（1），在二维平面上有两种不同的数据点，分别用红色和蓝色来表示，红颜色的线就把这两种不同颜色的数据点分开来了。这些数据点在多维空间中就是向量，红颜色的线就是一个超平面。 图（1） 图（2）假设 是 维空间中的一个数据点，其中是这个数据点的个特征，令 , 1, z0-1, z<0 (1.1)在图（1）中，处在红线左边的数据点，其y值为-1，反之，处在红线右边的数据点其y值为1。这样，根据y的值就把这个数据点分类了。那么

3、分类的重点就在如何构造这个函数。 设图（1）中的超平面（即红线）其表达式为 ，则= (1.2)直观上表示数据点到超平面的几何间隔，去掉分子的绝对值就有了正负性，是法向量，是截距。表示了数据点到超平面的函数间隔，如图（2）所示。由于是这个数据点的个特征，就是对特征进行线性组合，即给每一个特征加上一个权重。 因为 1, z0-1, z<0 ，=，=1或-1分别表示两个类别，而的正负决定它该分到哪个类别，所以我们以和 符号是否一致来判断分类是否正确。令 i=yi() (1.3)则>0表示分类正确，否则分类错误。 那么我们需要求解出和这两个参数。二、 最大间隔分类器对一个数据点进行分析，当

4、它到超平面的几何间隔越大的时候，分类正确的把握率越大。对于一个包含n 个点的数据集x(x1,x2,xn)，我们可以很自然地定义它的间隔为所有这n 个点的间隔中最小的那个。于是，为了使得分类的把握尽量大，我们希望所选择的超平面能够最大化这n个间隔值。令 =mini ,i=1,2,n (2.1) 所以最大间隔分类器的目标函数为 max (2.2) 条件为 i=yi ，i=1,2,n (2.3)即 yi ，i=1,2,n (2.4) 其中=，即= ，由于和的值可以缩放，令=1，则最优化问题转为： max 1 (2.5) s.t. yi1 ，i=1,2,n (2.6)通过求解这个最优化问题，我们可以得

5、到一个最大间隔分类器，如图（2）所示，中间的红线为最优超平面，另外两条虚线到红线的距离都等于1，即=1。三、 从原始问题到对偶问题及求解。原规划即：max 1 (3.1) s.t. yi1 ，i=1,2,n (3.2)由于求1的最大值相当于求122的最小值，所以上述问题等价于： min 122 (3.3) s.t.yi-10 ，i=1,2,n (3.4)容易证明这是个凸优化问题。构造Lagrange函数将其变为无约束的最优化问题，给每一个约束条件加上一个Lagrange乘子=(1,2,n)T(其中i0,i=1,2,n)： (3.5)令 maxi0 (3.6)容易验证，当某个约束条件不满足时，例

6、如，那么显然有+（此时i= +）。而当所有约束条件都满足时，则有（此时i=0），亦即我们最初要最小化的量。因此，在要求约束条件得到满足的情况下最小化，实际上等价于直接最小化（因为如果约束条件没有得到满足，会等于无穷大，自然不会是我们所要求的最小值。）具体写出来，我们现在的目标函数变成了： min,b=min,bmaxi0=p* (3.7)这里用p*表示这个问题的最优值，也是原问题的最优值。现在我们把最小和最大的位置交换一下： maxi0min,b=q* (3.8)式（3.8）是（3.7）的对偶问题，p*是的上确界（即最小上界），q*是的下确界（最大下界），显然p*q*，当且仅当原问题满足Sla

7、ter条件（即存在xi使得原规划的约束条件严格成立，即yi-1=0）时，等号成立。上文已说明此优化为凸优化，所以Kuhn-Tucker条件为某个数据点x*是最优解的充要条件。所以当xi满足KKT条件时，xi才是min,b的最优解。当同时满足Slater条件和KKT条件时，原规划可以取到最优值且为p*（p*=q*）。求解过程：要求解这个对偶问题，先求出关于，b的最小值，再对求最大。1、 先把当做常数，求出关于，b的偏导（即求min,b）关于，b求最小值，也是极值 L=- i=1niyixi=0 (3.9) Lb=-i=1niyi=0 (3.10) =i=1niyixi (3.11) i=1niy

8、i=0 (3.12)将式（3.11）和（3.12）代入到式（3.5）中 =12T-Ti=1niyixi-bi=1niyi+i=1ni =12Ti=1niyixi-Ti=1niyixi+i=1ni =i=1ni-12(i=1niyixi)Ti=1niyixi =i=1ni-12i=1nj=1niyijyjxiTxi (3.13)2、 从式（3.13）可以看出只包含=(1,2,n)T这一个变量（用来训练SVM分类器的数据集x(x1,x2,xn)和每个数据点的类别yi是已知的）。对式（3.13）求关于的最大值，根据式（3.12）得到最优化问题: max i=1ni-12i=1nj=1niyijyjx

9、iTxi s.t. i=1niyi=0 i0,i=1,2,n运用SMO算法（序列最小最优化算法）求以上最优化问题，此算法太繁琐，可以查找SMO算法的资料来了解，此处不赘述。3、 求出=(1,2,n)T之后，根据式（3.11）求出；b是截距,如图（3）所示，红线是分割超平面，另外两条虚线到红线的距离相等，为两种数据点到分割平面的最小距离，则：b=-12b1+b2=-12(mini:yi=1+maxi:yi=-1) （3.14） 图（3） 图（4） 至此，这个分类器的参数都已经解出来了。四、 使用松弛变量处理离群点数据本身是线性结构，但是由于噪声的影响，导致一些数据点偏离正常位置很远，这样的数据点

10、就叫做离群点。图（4）就是数据中有离群点存在的情况。 在图（4）中，因为离群点（用黑圈圈起来的蓝色的数据点）的存在，导致分类的超平面发生了偏离。分类的超平面本应该是中间的那根红线，但是由于离群点的存在，发生了偏差，变成了中间那条黑色的虚线。这样一来，当我们用这个学习好的SVM分类器对新的数据点进行分类的时候就有可能发生误判。为了解决这个问题，我们将离群点移回本来的位置，这就通过在约束条件中添加松弛变量ci(i=1,2,n)来实现，ci就对应于数据点允许偏离的距离。原来的约束条件式（2.6）就变成 yi-ci1 ，i=1,2,n （4.1）但是ci的取值也必须受到约束，即i=1nci要尽可能小。

11、那么目标函数就由（3.3）变为： min 122+i=1nci （4.4）是一个参数，用来控制目标函数中两项（即寻求间隔最大的分割超平面和保证数据点偏差量最小）的权重。那么这个最优化问题变为： min 122+i=1nci s.t.yi-ci1 ，i=1,2,n ci0 , i=1,2,n其求解方法与第三节中的方法一致。五、 存在的问题这样构建的分类器对于线性可分的情况很有效，但是对于线性不可分的情况，例如图（6）中的情况，其效果就不那么好了。需要去构造一些新的最优化问题来对非线性可分的数据进行分类。 图（6）参考文献1、支持向量机导论，美 Nello Cristianini / John Shawe-Taylor 著；2、Statistical behavior and consistency of classification methods based on convex risk minimization张潼3、Stat