1.线性可分SVM

给定训练样本集，其中xi∈RN为输入特征，yi∈{-1，+1}为样本类别输出。线性SVM的目的是在样本空间中找到一个最优分类超平面将不同类别的样本分开。数学上，一个超平面wx+b=0，其中w为法向量，b为偏移量，如果能以式（2.107）的形式将所有的样本xi分类，我们称之为完全正确分类。

即对于一个训练样本xi∈RN，当wxi+b与yi同号时可以认为超平面将xi分类正确。由于|（wxi+b）|≥+1对所有的i=1，2，…，n都成立，因此当xi被分类正确时有yi（wxi+b）≥+1成立。

如图2.5所示，圆点和三角形分别代表正负两类样本，距离超平面最近的这几个训练样本点使式（2.107）的等号成立，它们被称为“支持向量”，两种不同类支持向量到超平面的距离之和为

它称为“间隔”（margin）。SVM通过“最大化间隔”寻求最优分类超平面。最优分类超平面不但能够将两类样本完全正确分开，而且要求正负类样本中离它最近的样本点之间的距离尽可能大，即要求最大化分类间隔。

最大化分类间隔需要找到能满足式（2.107）中约束的参数w和b，使得Δ最大，即

图2.5　硬间隔与支持向量

此时，这样的间隔称之为硬间隔（hard margin）。最大化等价于最小化。于是，求解最优超平面问题可表示为

式（2.110）是一个具有线性约束的凸二次规划问题。根据最优化理论，式（2.110）所描述的原始问题（primal problem）可利用拉格朗日乘子法构造拉格朗日函数，再通过求解其对偶问题（dual problem）得到原始问题的最优解。

具体地，我们引入n个约束相关的拉格朗日变量αi≥0，拉格朗日函数表示为

想要求解L的最小值，令L对w和b的偏导为零，可得

将式（2.112）代入式（2.111）可得式（2.110）的对偶问题

记α=（α1，α2，…，αn）。此时原问题式（2.110）被转化为一个标准的线性约束凸二次规划问题，并存在唯一最优解α，优化过程在满足约束条件的同时还需要满足Karush—Kuhn—Tucker（KKT）条件，即(www.daowen.com)

将式（2.112）的目标函数由求最大化转化为求最小，可得与之等价的对偶问题

我们可以使用序列最小最优化（sequential minimal optimization，SMO）算法求解问题的最优解α。求得α后得SVM决策函数

其中，sgn为符号函数。

2.线性不可分SVM

在前面的讨论中，我们一直假定训练数据是严格线性可分的，即存在一个超平面能完全将两类数据分开。然而，在大多数的实际应用中，训练样本并不是线性可分的，即对于任意的超平面wxi+b=0，存在xi，使得yi（wxi+b）/≥1。为了在线性不可分情况下构造最优分类超平面，允许有一定的错分率，于是引入非负松弛变量（slack variable）ξi≥0，使得yi（wxi+b）≥1-ξi。此时得到的超平面称为软间隔分类超平面。如图2.6所示，少数的训练样本噪声点造成了数据的不可分。软间隔支持向量机因松弛变量的存在，可以允许少数正负类的样本出现在对方区域的情况，从而使得超平面能够将两类样本分离开来。

图2.6　软间隔与支持向量

求解软间隔分类超平面的凸二次规划问题为

其中，C＞0为误差惩罚系数，表示对误分类的惩罚程度。类似于线性可分SVM，原始问题式（2.117）对应的拉格朗日函数为

其中，αi≥0，βi≥0为拉格朗日乘子。令L对w、b和ξi的偏导为零，可得

将式（2.119）代入式（2.118）得原始问题的对偶问题

该对偶问题仍然是具有线性约束的凸二次规划问题，存在唯一最优解。求解策略与线性可分SVM类似，在此不再赘述。