SVM支持向量机

通俗来讲,SVM是一种二类分类模型,其基本模型定义为特征空间上的间隔最大的线性分类器,其学习策略便是间隔最大化,最终可转化为一个凸二次规划问题的求解。

从线性回归讲起

SVM主要是用来做分类工作,诸如文本分类,图像分类,生物序列分析和生 物数据挖掘, 手写字符识别等领域都有很多的应用。

对分类最简单的即线性分类器 用X表示数据点,Y表示类别(二分类中,y取1或-1),一个线性分类器的目标是在数据空间中找到一个分隔平面,这个分隔平面方程可以表示为: $$\omega^{T}x+b=0$$ 为使目标函数值在-1到1之间,我们使用Logistic函数作为假设函数。

假设函数:

$$h_\theta(x)=g(\theta^{T}x)=\frac{1}{1+e^(-\theta^{T}x)}, \quad h_\theta(x)\in(0,1)$$

其中,x是n维特征向量,所以假设函数就是y=1的概率:

$$P(y=1|x;\theta)=h_\theta(x) \ P(y=0|x;\theta)=1-h_\theta(x)$$

从而,有$h_\theta(x)>0.5$就是y=1的类,反之属于y=0的类。 接下来,将结果中y = 0 和 y = 1 替换为 y =-1,y = 1,然后将$\theta^Tx= \theta_0x_0+\theta_1x_1+\theta_2x_2+\cdots+\theta_nx_n(x_0=1)$中的$x_0$替换 为 b,最后将后面的$\theta_1x_1+\theta_2x_2+\cdots+\theta_nx_n(x_0=1)$替换为$\omega^Tx$,也就是说除了 y 由 y = 0 变为 y =1 外,线性分类函数跟 Logistic 回归的形式化表示$h_\theta(x)=g(\theta^Tx)=g(\omega^Tx+b)$没区别。 这里写图片描述

函数间隔与几何间隔

在超平面 $\omega^{T} x + b = 0$ 确定的情况下,$|\omega^{T} x + b|$ 能够表示点 x 到距离超平面的远近 ,而通过观察 $\omega^{T} x + b$的符号与类标记 y 的符号是否一致可判断分类是否正确,所以,可以用 $y(\omega^{T} x + b)$ 的正负性来判定或表示分类的正确性。

给定的训练数据集T和超平面w,b),定义超平面(w,b)关于样本点(xi,yi)的函数间隔为: $$\hat{\gamma}=y(\omega^{T}x+b)=y(f(x))$$ 但这样定义的函数间隔有问题,即如果成比例的改变 w 和 b(如将它们改成 2w 和 2b),则函数间隔的值 f(x) 却变成了原来的 2 倍(虽然此时超平面没有改变),所以只 有函数间隔还远远不够。

平面法向单位化的函数间隔,即几何间隔 $$\gamma=\frac{\omega^{T}x+b}{||\omega||}=\frac{f((x)}{||\omega||}$$ 假定对于一个点 x ,令其垂直投影到超平面上的对应点为 $x_0$ ,w 是垂直于超平面 的一个向量, 为样本 x 到分类间隔的距离,如图所示。 log

从上述的定义可以看出:几何间隔就是函数间隔除以 $∥\omega∥$,而且函 数间隔 $y(w ^T x + b) = yf(x)$ 实际上就是 $|f(x)|$,只是人为定义的一个间隔度量,而几何 间隔 $|f(x)|/∥\omega∥$ 才是直观上的点到超平面的距离。

最大间隔分类器

对一个数据点进行分类, SVM的思想是当超平面离数据点的“间隔”越大, 分类的确信度 (confidence)也越大。 这里写图片描述

定义目标函数: 这里写图片描述

回顾一下几何间隔的定义 $\tilde{\gamma}=y\gamma = \frac{hat{\gamma}}{∥\omega∥}$ 可知, 如果令函数间隔 $\hat{\gamma}$等于 1, 则有$\tilde{\gamma}=\frac{1}{∥w∥}$ 且 $y_i (\omega ^T x_i + b) \geq1; \quad i = 1; \cdots; n$

从而上述目标函数转化成了:

$$ max\quad \frac{1}{||w||} ;\ s.t. y_i (w^{T} x_i + b)\geq1;\quad i = 1, \cdots,n$$

这个目标函数便是在相应的约束条件$y_i (w^T x_i + b) \geq1;\quad i = 1, \cdots,n$条件下,最大化这个 $\frac{1}{||w||}$ 值,而 $\frac{1}{||w||}$便是几何间隔$\tilde{\gamma}$。

拉格朗日乘子法

由于求 $\frac{1}{||w||}$ 的最大值相当于求 $\frac{1}{2}||w||^2$ 的最小值,所以上述目标函数等价于

$$ min\quad \frac{1}{2}||w||^2 ; \ s.t. y_i (w^T x_i + b) \geq1;\quad i = 1, \cdots,n$$

因为现在的目标函数是二次的,约束条件是线性的,所以它是一个凸二次规划问题。这个问题可以用现成的 QP (Quadratic Programming) 优化包进行求解。一言以蔽之:在一定的约束条件下,目标最优,损失最小。

此外,由于这个问题的特殊结构,还可以通过拉格朗日对偶性(Lagrange Duality) 变换到对偶变量 (dual variable) 的优化问题, 即通过求解与原问题等价的对偶问题 (dual problem)得到原始问题的最优解,这就是线性可分条件下支持向量机的对偶算 法,这样做的优点在于:一者对偶问题往往更容易求解;二者可以自然的引入核函数, 进而推广到非线性分类问题。

那什么是拉格朗日对偶性呢?简单来讲,通过给每一个约束条件加上一个拉格朗日乘子(Lagrange multiplier),定义拉格朗日函数

$$L(\omega,b,\alpha)= \frac{1}{2}||w||^2-\sum_{i=1}^{n}\alpha_i(y_i(w_i^Tx_i+b)-1)$$

原问题是极小极大问题: $$\underset{\omega,b}{Min}\underset{b}{Max}L(\omega,b,\alpha)$$

原始问题的对偶问题,是极大极小问题: $$\underset{b}{Max}\underset{\omega,b}{Min}L(\omega,b,\alpha)$$

将拉格朗日函数$L(w,b,\alpha)$分别对w,b求偏导并令其为0,

log00

将上式带入拉格朗日函数$L(w,b,\alpha)$中,得到:

log01

继续求$\underset{w,b}{min}L(w,b,\alpha)$对$\alpha$的极大值:

log02

整理目标函数,求解出最优的$\alpha^{*}$ log03

上式为一般的含不等式约束问题,存在最优化解法的必要和充分条件即KKT条件(详情可查看等式约束与不等式约束问题): 为方便理解,我们把所有的不等式约束、等式约束和目标函数全部写为一个式子,简化为$$L(a,b,x)=f(x)+a∗g(x)+b∗h(x)$$

KKT条件是说最优值必须满足以下条件:

  1. $\frac{\partial{L}}{\partial{x_i}}=0$对x求导为零;
  2. $h(x) =0;$
  3. $a*g(x) = 0;$

求取这些等式之后就能得到候选最优值。其中第三个式子非常有趣,因为$g(x)<=0$,如果要满足这个等式,必须$\alpha=0$或者$g(x)=0$. 这是SVM的很多重要性质的来源,如支持向量的概念。

所谓 支撑向量Supporting Vector 也在这里显示出来——事实上,所有非 Supporting Vector 所对应的系数都是等于零的,因此对于新点的内积计算实际上 只要针对少量的“支持向量”而不是所有的训练数据即可。

核函数

对于线性不可分的情况,可以使用核函数,将输入空间映射到特征空间(通俗说来是从低维空间映射到高维空间),从而使得原本线性不可分的样本可以在特征空间可分。

log04

在实际应用中,往往依赖先验领域知识才能选择有效的核函数 ####常见的核函数有

  • 多项式核函数:$$K(x_1,x_2)=(\left \langle x_1,x_2 \right \rangle)^d$$
  • 高斯核函数: $$K(x_1,x_2)=exp^ { \frac{||x_1-x_2||}{2\sigma^2} } $$

参考链接:

  1. 统计学习方法,李航著,清华大学出版社,2012年
  2. http://blog.csdn.net/v_july_v/article/details/7624837
  3. http://www.cnblogs.com/zjgtan/archive/2013/09/03/3298213.html
我只是试试,自己给自己转点钱!