1.2.1 支持向量机分类问题

对于二元分类问题在线性可分的条件下，分类方法有很多种。例如，图1.2.1与图1.2.2均可将数据成功进行分类。但图1.2.1所示的分类方法和图1.2.2所示的分类方法哪个更好呢？

对于分类问题，最好的分类方法不但能正确将两类区分开，而且能使区分间隔或分类距离最大，即达到最优的分类方法。如图1.2.3所示，空心球与实心球分别代表两类训练样本，H为分类线，负责把两类样本分开。H₁、H₂分别为两类样本中过离分类线最近的点且平行于分类线H的直线。H₁与H₂之间的距离称为分类间隔（margin）。最优分类线即为H，其到H₁、H₂的距离为1/‖w‖，这样不仅可以将样本分开，并且可以使分类间隔最大。其中，落在H₁与H₂上的训练样本点称之为支持向量。

设训练样本数据为（x（1）,y（1））,（x（2）,y（2））,…,（x（N）,y（N）），x∈Rd，类别y∈{-1,1}。若线性可分，则表明存在超平面（w·x）+b=0使两类不同的输入分别在该分类面的两侧，即存在参数对（w,b）使

式中，sgn（·）为符号函数。

构造决策函数f（x）=sgn（（w·x（n））+b）。使训练样本成功分类的参数对（w,b）有很多对，图1.2.3表明，最优的分类超平面是训练样本对超平面的几何间隔为1/‖w‖的超平面。此时要满足的条件为

最优分类问题转换为求解二次规划问题：

式（1.2.3）是不等式条件约束下的二次函数极值问题，根据原始最优化问题的KKT（Karush-Kuhn-Tucker）条件，它的解存在且唯一。求解式（1.2.3）最优解的方法是将其转换为对应的对偶问题。

首先，引入拉格朗日函数

式中，α=（α（1），α（2），…，α（N））T∈为Lagrange乘子。

由最优化原理可知，需求拉格朗日函数对w和b的微分且令其等于零，即

得到

将式（1.2.6）代入式（1.2.4），得原始优化问题对应的对偶函数为

求解上述问题得到的最优分类函数为

当训练样本线性不可分时，任何分划超平面都会有些错划，这时不能要求所有的训练样本点都满足约束条件y（n）[（w·x（n））+b]-1≥0。为此，可引入松弛变量ξ，将约束条件变为

向量ξ=（ξ（1）,ξ（2）,…,ξ（n））T体现了训练样本允许被错划的情况。

选取最优分类函数时，一方面希望分类间隔2/‖w‖尽可能大，另一方面又希望错划程度尽可能小。为此，引进惩罚参数C作为对错分样本的惩罚，以表示分类间隔与错划程度的折中。

此时，最优分类问题为

通过化简，其最优化问题对应的对偶问题转化为

通过观察可知，式（1.2.11）与式（1.2.7）几乎完全相同，唯一的区别只是系数α（n）的约束不同。

统计学习理论指出，在N维空间中，如果样本分布在一个半径为R的超球范围内，若满足条件‖w‖≤d，则其VC维满足的条件为

式（1.2.12）表明，支持向量机的分类方法是在获得较小经验风险的基础上，通过利用分类间隔来控制VC维，使机器学习的复杂度与推广能力得到了很好的折中，体现了结构经验风险最小化原则。