线性支持向量机 (3)

线性可分问题的支持向量机学习方法，对线性不可分训练数据是不适用的，因为这时上述方法中的不等式约束并不能都成立，因此这时候需要将硬间隔最大化，使其变成软间隔最大化。

假定给定特征空间上的训练数据集：T={(x₁,y₁),(x₂,y₂),...(x_n,y_n)}，x_i为第i个特征向量，y_i为x_i的类标记，一般情况下，线性不可分的数据主要在于存在部分特异点，除去这些点后剩下的大部分样本点组成的集合是线性可分的。线性不可分意味着样本点(x_i,y_i)不能满足函数间隔大于等于1的约束条件，为了解决这个问题，可以对样本点(x_i,y_i)引进松弛变量ξ_i≥0，使得函数间隔加上松弛变量ξ_i大于等于1，这样约束条件则变为：

同时，对于每个松弛变量ξ_i，支付一个代价ξ_i，目标由原来的变成,这里C>0称为惩罚函数，一般由实际问题的情况来变动C的值，当C值增大的时候对误分类的惩罚增大，C值小的时候对误分类的惩罚减小，最小化目标函数包含两层含义：使尽量小即使间隔尽量大，同时使误分类点的个数尽量小，C是作为调和二者的系数。

线性不可分的线性支持向量机的学习问题转变为如下凸二次规划问题：

上述问题是一个凸二次规划问题，因而关于(w,b,ξ)的解是存在的，可以证明w的解是唯一的，但b的解可能不唯一，而是存在于一个区间。

由上式得到的解w，b，可以得到分离超平面wx+b=0及分类决策函数 f(x)=sign(wx+b)  ，称这样的模型为训练样本线性不可分时的线性支持向量机，简称线性支持向量机。

 原始问题的对偶问题是：

原始最优化问题的拉格朗日函数是：(拉格朗日乘法用于解决等式约束，对于包含等式约束和不等式约束条件则转为KKT条件下的最优求解)

对偶问题是拉格朗日函数的极大极小问题，首先求L(w,b,ξ,a,u)对w,b,ξ极小，由

将上述等式代入原式可得：

再对求a的极大，即得对偶问题：

 其中上式中最后3条的约束条件可以转换成：0≤a_i≤C

再对目标函数求极大转换为求极小，从而得到对偶问题：

通过求解对偶问题而得到原始问题的解，进而确定分离超平面和决策函数。

设是以上对偶问题的一个解，若存在a^*的一个分量aj^*，存在,则原问题的解w^*，b^*可按下式求得：

 线性支持向量机学习算法如下：

输入：训练数据集T={(x₁,y₁),(x₂,y₂),...(x_n,y_n)}，其中,

输出：分离超平面和分离决策函数

（1）选择惩罚函数C>0，构造并求解凸二次规划问题

求得最优解

（2）计算，选择a^*的一个分量aj^*适合条件0<aj^*<C，计算

（3）求得分离超平面w^*x+b^*=0

       分类决策函数：  f(x)=sign(w^*x+b^*)

在上述的步骤（2）中，对任一适合条件0<aj^*<C的aj^*，按照b^*的求解方法都可求出b^*，从理论上原始问题对b的解可能不唯一。

在线性不可分的情况下，将对偶问题的解中对应于的样本点(x_i,y_i)的实例x_i称为支持向量。

不同的和ξ_i对应的支持向量分类情况：

软间隔的支持向量x_i有如下几种分布情况，在间隔边界上、在间隔边界与分离超平面之间、在分离超平面误分类一侧。若,则ξ_i=0，支持向量x_i刚好落在间隔边界上；若，0<ξ_i<1，则分类正确，x_i在间隔边界与分离超平面之间；若，ξ_i=1，则x_i在分离超平面上，若，ξ_i>1，则x_i位于分离超平面误分类一侧。