Kuang Algorithm Engineer&Data Mining Engineer

支持向量机专题——线性支持向量机

2017-10-09
Kuang
ML

本文介绍线性支持向量机

线性支持向量机

简介

当数据线性不可分时,使用硬间隔支持向量机很难得到理想的结果。但是如果数据近似线性可分,可以采用软间隔支持向量机(线性支持向量机)进行分类。这通常适用于有少量异常样本的分类,如果使用线性支持向量机,它会尽量使得所有训练样本都正确,如下图所示。

显然这并不是最好的结果,软间隔支持向量机可以权衡“间隔最大”和“误分类点最少”,得到以下结果。

推导

基于线性可分支持向量机,我们增加一个可”容忍“不满足函数间隔大于1的约束条件的考虑。即引进一个松弛变量$ \xi_i \ge 0$ ,使约束条件变为

同时,修改代价函数(目标函数)为

接下来的步骤就和线性支持向量机一样,解一个凸二次规划问题

根据拉格朗日的对偶性,上述凸二次规划问题的拉格朗日函数是

其中$\alpha_i\ge0$,$\mu_i\ge0$

原始问题的对偶问题是拉格朗日函数的极大极小问题,先求$L(\omega,b,\xi,\alpha,\mu)$ 对$\omega,b,\xi$的极小,再求$min_{\omega,b,\xi}L(\omega,b,\xi,\alpha,\mu)$ 对$\alpha$的极大,可以得到原始问题的对偶问题为

是对偶问题的一个解,则有

其中,j为使得$0<\alpha_j^*<C$ 成立的一个值。

支持向量

对偶问题的解 中对应于 $\alpha_i^*>0$ 的样本点$(x_i,y_i)$的实例$x_i$称为支持向量(软间隔的支持向量),实例$x_i$到间隔边界的距离为

软间隔的支持向量要么在间隔边界上, 要么在间隔边界和分离超平面之间,要么在分离超平面误分一侧。

则必有 (),这时候支持向量在间隔边界上;若 ,则分类正确,支持向量在间隔边界与分离超平面之间;若 ,则在分离超平面上;若 ,则 位于分离超平面误分一侧

合页损失函数

线性支持向量机学习还有一种类似于逻辑回归,线性回归等算法的学习方式,同样是最小化一个目标函数

$[Z]_+$ 表示以下取正值的函数

合页损失函数的意思是,若正确分类,且函数间隔大于1时损失为0;否则,损失为$1-y(\omega \cdot x +b)$ ,这也就是说,合页损失函数不仅仅只在乎分类的正确性,而且还要使确信度足够高,这也就意味着,当样本足够时,它会自动“过滤”一些异常点,不会使得少量的异常点对结果产生影响。


Comments