支持向量机中的优化关系推导

杜世平 智岩

[摘要]支持向量机（SVM）是通过寻找最优分离超平面实现分类的目标。但是这个过程涉及负责的逻辑过程。本文通过详细解释SVM的相关逻辑关系，展示了SVM中解决优化问题的一般性数值关系推导。

[关键字]支持向量机;分离超平面;优化问题;最大化间隔

Vapnik[1]提出SVM算法[2，3，4]用于解决两类问题，第一类是线性可分的问题第二类是线性不可分问题。本文讨论svm能够解决的线性可分问题为例，介绍SVM。

注意到，使用margin最大的条件来求解支持向量引出的问题就是这样的直线并不唯一。理论分析表明，支持向量机寻找的最优的分类直线应该满足：（1）该直线分开了两类;（2）该直线最大化了间隔（margin）;（3）该直线处于间隔的中间，到所有支持向量的距离相等。即支持向量就是分离超平面最近的那些点（“最近的意思是，点和直线可以刚好相交”）。支持向量机就是寻找空间中的一条能够将类别不同的对象以最大间隔分割开来的直线，这条直线与两侧的支持向量直线的距离相等。

上述关于是基于二维特征空间的结果，而在高维空间中，直线将变成超平面。理论表明，上述结论却是一致的。现在，我们开始寻找最优的分类超平面的过程。为了说明这个问题，我们首先看“线性可分”的定义：

假定训练样本是线性可分的，SVM需要寻找的是最大化间隔的超平面，则这个优化问题可写成如下形式：

之所以有以上关系，是因为，我们可以假定w是一个m维的向量具体的，设，则，||w||2=w12+w22+ ... wm2。这就是说，SVM的优化问题就是最小化w模的平方，且有N个限制条件。为了推出这个优化问题，我们注意到如下两个事实：

2 二次规划

定义：二次规划[5，6]的定义包括两个条件：（1）目标函数是二次项;（2）限制条件是一次项。

在最优化理论中，如果一个问题是凸优化问题，我们就可以把它当成一个已经解决的问题。因为凸优化问题只有唯一一个全局的极值。我们可以用梯度下降法来求得它的解。

3 线性不可分及其求解

如果训练样本线性不可分，那么以上优化问题的解释什么？显然是无解。即不存在（w，b）使得它满足上述N各限制条件。对于线性不可分的情形，我们需要适当放松限制条件，使得上面的优化问题变的有解。放松限制条件的思路是，对于每个训练样本xi与其标签yi，我们需要设置一个松弛变量δi。于是，我们可将上面的N个不等式的限制条件放松为如下的限制条件：yi（wTxi + b）≥1-δi ，（i=1 ， ... ， N）。

那就是说，在线性不可分的情况下，我们不可能让所有的yi乘以wTxi + b大于等于1。于是，注意到，我们引入δi，作用到不等式的右边，可以看到，只要每个δi足够的大，那么，上面的N个不等式的限制条件都是可以成立的。当然，我们应该增加新的限制条件以阻止δi无限变大，让它限定在一个合理的范围内。最终，我们可以获得改造后的SVM的优化版本：

两个限制条件分析如下：第一个条件保证每个δi是大于等于0的。限制条件（2）将以前的难以达到的不等式变的容易达到。再看目标函数，以前的目标函数只需要最小化模的方的一半，而现在的目标函数增加了一项，即所有的δi的总和，这就不但要求w的模越小越好，还要求每个δi的和越小越好。

在这里强调的是，平衡两项的比例因子C是认为设定的，我们把一个算法中，人为设定参数叫做算法的超参数（hyperparameter）。一般来说，在实际应用中，我们会不断的变化C的值，同时对每个C，我们要测试算法的识别率。然后我们选取识别率达到最大的超参数C的值。显然如果一个算法的超参数越多，意味着算法需要手动调整优化的地方越多，这样算法的自动性就会降低，SVM是超参数很少的算法模型。

4 从低维到高维的映射

這里我们要考察的是如何扩大考察函数的范围，从而提高处理非线性可分数据集的能力。SVM在扩大可选参数范围方面可谓独树一帜。其它算法，如ANN，决策树等采用的是直接产生更多可逆函数的方式。例如ANN中，通过多层非线性函数的组合能够产生类似于椭圆的曲线，从而区分比如由圆圈（○）包围的叉（×）。SVM不是直接产生这样的函数，而是通过将特征空间由低维映射到高维，然后在高维特征空间当中仍然用线性超平面对数据进行分类。

这里有一个一般性的结论需要强调一下：假设在一个M维的空间上，随机取N个训练样本，随机的对每个训练样本赋予标签+1或者-1.并假设，这些训练样本线性可分的概率为P（M），则当M趋于无穷大时，P（M）=1。

关于这个结论，直观上很容易理解，即当我们增加特征空间的维度M的时候，超平面待估计的参数（w，b）的维度也会增加。也就是说，整个算法模型的自由度会增加，当然，就更有可能分开低维时候无法分开的数据集。上述结论告诉我们，将训练集样本由低维映射到高维，能够增加线性可分的概率。因此，我们如何构造一个由低维到高维映射函数就成为关键性的问题。在从低维到高维的映射过程中，我们要注意核函数的使用规则：核函数K和映射函数是一一对应的关系，知道其中一个，就可以知道另一个。

5 举例 - 兵王问题

兵王问题是，如果在国际象棋中的残局，黑方只剩下一个王，拜访还剩下一个兵一个王，那么将有两种可能：第一，白方将死黑方，白方获胜。第二，和棋。

这两种可能是三个棋子在棋盘的位置而确定的。为了让大家对这个问题有更直观的了解，需详细的说一下与之关联的国际象棋规则，其中有一条规则叫做“兵的升变”。也就是说，并走至对方的底线，可以升为除王外任意棋子。第二条规则就是“逼和”，也就是说，一方的王未被将军，但是下一步它移动到任意的地方都会被对方将死，则此时是和棋。

从这个规则中我们可以大致了解到，黑方要想防止自己被将死，有一个好消息，和一个坏消息。坏消息是，黑方必须防止兵走到底线，升变为王，这样的强子。往后可以横竖斜走若干步。若王后和王一起配合，一定可以将死对方的王。而好消息是，黑方可以利用逼和的规则，主动造成无路可走的情形，从而导致和棋。

接下来就是一个神奇的事：我们在不输入计算机规则的前提下，利用SVM，我們可以让计算机学会判断兵王问题是白方胜还是和棋。这是一个二分类问题。

首先，我们需要标注好的训练数据集，在著名的UCI ML数据集上，我们可以下载到兵王问题的数据。在这里，我们用SVM来处理这个问题。首先我们将和棋标签标为drw当做一类。设定此时的yi=±1。将其它标签从1到x当做另一类，设定此时相应的标签yi=-1接下来我们用SVM的程序进行训练，我们用LIBsvm工具包，就可以得到相应的超平面方程。

[结束语] 本文详细分析了支持向量机解决优化问题过程中的数值关系，并给出了相关的数学推导，为初学者后续的相关课题学习研究给予指导。

[1] Guyon I ， Weston J ， Barnhill S ， et al. Gene Selection for Cancer Classification using Support Vector Machines[J]. Machine Learning， 2002， 46（1-3）：389-422.

[2] Bi J ， Vapnik V N . Learning with Rigorous Support Vector Machines[C]// Computational Learning Theory and Kernel Machines， 16th Annual Conference on Computational Learning Theory and 7th Kernel Workshop， COLT/Kernel 2003， Washington， DC， USA， August 24-27， 2003， Proceedings. DBLP， 2003.

[3] Tao Y ， Zhu X ， Huang D ， et al. Soft Sensor Modeling Based on the Soft Margin Support Vector Regression Machine[C]// IEEE International Conference on Control & Automation. IEEE， 2007.

[4] Chapelle O ， Vapnik V . Model Selection for Support Vector Machines. 2000.

[5]Fei S ， Lin Y ， Saul L K ， et al. Multiplicative Updates for Nonnegative Quadratic Programming[J]. Neural Computation， 2007， 19（8）：2004-2031.

[6]Kleinhans J M ， Sigl G . GORDIAN： VLSI placement by quadratic programming and slicing optimization[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems， 2002， 10（3）：356-365.

广州工商学院 广东省佛山市 528138