onesimple

SVM支持向量机原理简析

SVM是支持向量机support vector machine的缩写,它是现在使用比较广泛的一个分类算法。

  关于svm的研究,前人之述备矣,本篇只做归纳整理,详细推导过程可参考大牛的博客:

支持向量机通俗导论(理解SVM的三层境界)

支持向量机原理篇之手撕线性SVM

  • 什么是svm?


  svm主要用于解决机器学习领域中的数据分类问题,属于有监督学习算法的一种。
SVM要解决的问题可以用一个经典的二分类问题加以描述。
如图1所示,红色和蓝色的二维数据点显然是可以被一条直线分开的,在模式识别领域称为线性可分问题。
然而将两类数据点分开的直线显然不止一条。图1(b)和(c)分别给出了A、B两种不同的分类方案,其中黑色实线为分界线,术语称为“决策面”。
每个决策面对应了一个线性分类器。
虽然在目前的数据上看,这两个分类器的分类结果是一样的,但如果考虑潜在的其他数据,则两者的分类性能是有差别的。
当一个分类问题,数据是线性可分的,也就是用一根棍就可以将两种小球分开的时候,
我们只要将棍的位置放在让小球距离棍的距离最大化的位置即可,寻找这个最大间隔的过程,就叫做最优化。
那个具有“最大间隔”的决策面就是SVM要寻找的最优解。而这个真正的最优解对应的两侧虚线所穿过的样本点,就是SVM中的支持样本点,称为“支持向量”。
但是,现实往往是很残酷的,一般的数据是线性不可分的,也就是找不到一个棍将两种小球很好的分类。
这个时候,我们就需要像大侠一样,将小球拍起,用一张纸代替小棍将小球进行分类。
想要让数据飞起,我们需要的东西就是核函数(kernel),用于切分小球的纸,就是超平面。
通俗来讲,它是一种二类分类模型,其基本模型定义为特征空间上的间隔最大的线性分类器,其学习策略便是间隔最大化,最终可转化为一个凸二次规划问题的求解。

  • 求解过程

  以二维空间的分类问题为例来说明,决策面方程(二维空间即为直线方程):
$$
w^Tx + b = 0
$$
w控制直线的方向,b控制直线的截距。

根据点到直线的距离计算公式,得分类间隔为:
$$
d= \frac {|w^Tx+b|} {||w||}
$$

– 约束条件:
对于存在分类间隔的两类样本点,我们一定可以找到一些决策面,使其对于所有的样本点均满足下面的条件(中间省略若干推导):

$$
\begin{cases}
w^Tx_i + \gamma \ge 1 & y_i=1\\
w^Tx_i + \gamma \le -1 & y_i=-1\
\end{cases}
$$

– 优化问题

支持向量样本点到决策面方程的距离为:
$$
d= \frac {|w^Tx_i+\gamma|} {||w||} \
=\frac 1 {||w||}
$$
原来要找一组w和$\gamma$使分类间隔W=2d最大化,现在问题变成了||w||最小化问题,等效于$\frac{1}{2}||\boldsymbol{\omega}||^2$的最小化问题

则线性SVM最优化问题的数学描述就变成:
$$
\begin{cases}
min_{w,\gamma} \frac{1}{2} {||w||^2} \\
s.t. {y_i}(w^Tx_i+\gamma) \ge 1 & {i=1,2,…,m}\
\end{cases}
$$

目标函数是二次的,约束条件是线性的,所以它是一个凸二次规划问题,一般可以通过现成的QP优化包进行求解。此外,还可以通过拉格朗日对偶性变换
到对偶变量的优化问题,就是线性可分条件下支持向量机的对偶算法,这样做的优点在于:一者对偶问题往往更容易求解;二者可以自然的引入核函数,
进而推广到非线性分类问题。

  • 拉格朗日对偶
    – 将有约束的原始目标函数转换为无约束的新构造的拉格朗日目标函数
    $$
    L(w,\gamma,\alpha) = \frac{1}{2} {||w||^2} - \
    \sum_{i=1}^n\alpha_i(y_i(w^Tx_i+\gamma) - 1)
    $$

其中$\alpha_i$是拉格朗日乘子,首先分别对w和$\gamma$求偏导,令偏导为0,得:
$$
w=\sum_{i=1}^n\alpha_i y_i x_i \\
\sum_{i=0}^n\alpha_i y_i = 0
$$
代回拉格朗日目标函数,得:
$$
L(w,\gamma,\alpha) = … = \sum_{i=0}^n\alpha_i - \frac {1} {2} \sum_{i,j=1}^n{\alpha_i \alpha_j y_i y_j {x_i}^T x_j}
$$

所以对偶问题就变成:
$$
\begin{cases}
\max\limits_\alpha \sum_{i=0}^n\alpha_i - \frac {1} {2}
\sum_{i,j=1}^n{\alpha_i \alpha_j y_i y_j {x_i}^T x_j} \\
s.t. {\alpha_i} \ge 0 & {i=1,2,…,n} \\
\sum_{i=0}^n\alpha_i y_i = 0 \
\end{cases}
$$


…… 未完待续 ……

  

  

  

🐶 五百年雨打的石桥,有你走过 🐶