SupportVectorMachine支持向量机

Welcome To My Blog
支持向量机(support vector machine,SVM)是一种二分类模型,它的基本模型是定义在特征空间上的间隔最大的线性分类器,间隔最大使它有别于感知机.
有3类支持向量机模型:
1. 线性可分支持向量机
2. 线性支持向量机
3. 非线性支持向量机
(这三种模型建立思路很像,求解过程不同)

一.线性可分支持向量机

几何间隔与函数间隔的引出

超平面wx+b=0外一点x0到超平面的距离公式(几何间隔):

1.png
分母是w的二范式,不随x0的改变而改变,所以可以分子|wx0+b|能够相对地表示点x0距离超平面wx+b=0的远近.
一个点距离分离超平面的远近可以表示分类预测的确信程度.
wx0+b的符号与类标记y0的符号是否一致能够表示分类是否正确.
所以,可用y0(wx0+b)来表示分类的正确性及确信度,这就是函数间隔(functional margin)

函数间隔

超平面(w,b)关于样本点xi的函数间隔为:

2.png
超平面(w,b)关于训练集T的函数间隔为:
3.png

几何间隔

超平面(w,b)关于样本点xi的几何间隔为:

4.png
超平面(w,b)关于训练集T的几何间隔为:
5.png

硬间隔最大化

找到了超平面(w,b)关于训练集T的几何间隔后,自然地希望最大化这个几何间隔以保证之后分类预测的确信程度
目标函数和约束如下:
约束表示超平面(w,b)关于任意样本点的几何间隔大于等于超平面(w,b)关于训练集T的几何间隔

6.png
在约束中约去||w||并展开γ^
6.1.png
求出w,b的话问题就解决了,先别急,让我们化简一下上面的式子
注意到,如果对w,b同比例的放缩,即变成kw,kb,函数间隔yi(wxi+b)也会成比例k变化,而超平面(w,b)没有变化,
此时原问题和约束变为:
7.png
约掉k后,目标函数和约束没有改变,说明对w,b进行同比例放缩丝毫不影响目标函数和约束,那么可以选取合适的k让函数间隔γ^=1,也就是
8.1.png
这样一来,目标函数和约束就变成了:
8.png
把||w||挪到分子上平方一下再乘个常数就有了:
9.png
比最初的形式简化了不少,这是个带约束问题,通过Lagrange Multiplier拉格朗日乘子法化成无约束问题:
(原问题:极大极小)
10.png

具体原理可参考之前的文章Lagrange duality拉格朗日对偶性
对偶形式:

11.png
其中:
12.png
所以有:
13.png
进而有(最终形式):
下面的约束是求 min L(w,b,α)时得到的
这是个凸二次规划问题(目标函数是二次函数,不等式约束是仿射函数)
14.png
求解得到α*=(α1,α2,...,αN)^t,这是对偶问题的解,
可由α*得到w*,b*
15.png
之所以能从对偶问题获得原问题的解,是因为原问题为凸二次规划问题,并且解α*,w*,b* 满足KKT条件
有了w*,b*就能得到最大间隔分离超平面和分类决策函数: 16.png

支持向量

通过由α*得到w*,b*的公式可以知道,对应α*=0的实例xi对超平面(w*,b*)的两个参数都没有贡献,只有对应α*＞0的实例xi对超平面(w*,b*)的两个参数有贡献,也就是说超平面完全由对应α*＞0的实例决定,这些实例称为支持向量,由KKT的互补条件知,若α*＞0,则有y(wx+b)-1=0,即wx+b=±1,说明支持向量都在间隔边界上

小结

对于线性可分SVM学习来说:

1. 模型为分离超平面和决策函数
2. 学习策略:硬间隔最大化(间隔的描述及约束)
3. 学习算法:凸二次规划

二.线性支持向量机

通常情况下,训练数据中有一些特异点(outlier),将这些特异点去掉后,剩下的大部分样本点组成的集合是线性可分的.线性不可分意味着不是所有点都满足函数间隔大于等于1的约束,为解决这个问题,引入一个松弛变量ζi≥0,使函数间隔加上松弛变量后大于等于1.即,y(wx+b)+ζ≥1

软间隔最大化

对每个松弛变量ζi,支付一个代价ζi,目标函数变为

17.png
这里C>0称为惩罚参数,C越大则对错误分类的惩罚越大
最小化上述目标函数实现的是软间隔最大化,最小化上式包含两层含义:使1/2||w||^2尽量小,即间隔尽量大,同时使误分类点的个数尽量小.
硬间隔就是真正的间隔,软间隔是包含了代价项ζ的硬间隔
由上分析便得到了线性支持向量机的学习目标:
18.png
化为拉格朗日形式(不带约束)的原问题:
19.png
对偶问题:
20.png
其中: 21.png
进而:
22.png
所以对偶问题的最终形式:
23.png
与线性可分SVM的对偶最终形式相比只是α的约束不同,约束增强了
求解得到α*=(α1,α2,...,αN)^t,这是对偶问题的解,
可由α*得到w*,b*
24.png
有了w*,b*就能得到最大间隔分离超平面和分类决策函数: 16.png

支持向量

和线性可分SVM类似,超平面完全由对应α*＞0的实例决定,这些实例称为支持向量,但是线性SVM的支持向量不一定都在间隔边界上

25.png
KKT互补条件之一:α*(y(w*x+b)+ζ-1)=0
当0<αi<C时,ζi=0,则y(w*x+b)-1=0,此时支持向量在间隔边界上
当αi=C时,ζi>0,支持向量可能在:
间隔边界与超平面之间:0<ζi<1
超平面上:ζi=1
误分类一侧:ζi>1

Hinge Loss Function合页损失函数

线性SVM的学习还有另一种等价模型,即最小化目标函数:

26.png
27.png
28.png
证明新目标函数与原问题等价时,主要抓住三点:
1. hinge loss≥0
2. 令[1-y(wx+b)]_+=ζ
3. 讨论1-y(wx+b)的取值范围
L(y(wx+b))说明了:
1. 点到超平面的函数距离≥1时,损失为0
2. 点到超平面的函数距离＜1时,损失为1-y(wx+b)
下图蓝线代表hinge loss的图像
29.png

小结

对于线性SVM学习来说:

1. 模型为分离超平面和决策函数(线性SVM的对偶形式)
2. 学习策略:软间隔最大化(间隔的描述及约束)
3. 学习算法:凸二次规划

三.非线性支持向量机

用线性分类方法求解非线性分类任务分为两步:
1. 将训练数据从输入空间(欧式空间或离散集合)映射到新的特征空间(希尔伯特空间)使数据在新特征空间中线性可分
2. 在新特征空间中用线性分类学习方法从训练数据中学习分类模型,使得输入空间中的超曲面模型对应特征空间中的超平面模型
Kernel trick(核技巧)便属于这样的方法

目标

30.png
K(x1,x2)=φ(x1)φ(x2)是个对称函数,叫作正定核(positive definite kernel)
一般只定义K(x1,x2),而不显式地定义φ(x),那么如何保证K(x1,x2)是正定核呢?
正定核的充要条件:
33.png
证明过程需要预备知识:构造希尔伯特空间

• 定义映射φ并构成向量空间S(对加法和数乘运算封闭的集合)
• 在S上定义内积构成内积空间(用到了欧式空间Gram矩阵的半正定性)
• 将内积空间S完备化为希尔伯特空间

由α*得到b*

31.png
分类决策函数
32.png

常用的核函数

正定核的充要条件在构造核函数时很有用.但对于一个具体函数K(x,z)来说,检验它是否为正定核并不容易,因为需要对任意有限输入集{x1,x2,...,xm}验证K对应的Gram矩阵(在希尔伯特空间)是否为半正定的.实际问题中往往应用已有的核函数

1. 多项式核函数(polynomial kernel function)
   34.png
   对应的支持向量机是一个p次多项式分类器,分类决策函数为:
   35.png
2. 高斯核函数(Gaussian kernel function)
   36.png
   对应的支持向量机是高斯径向基函数(radial basis function)分类器,分类决策函数为:
   37.png
3. 字符串核函数(string kernel function)
   定义在字符串集合上的核函数,字符串核函数应用在文本分类,信息检索,生物信息学等方面.
   k_n(s,t)给出了字符串s和t中长度等于n的所有子串组成的特征向量的余弦相似度(cosine similarity).直观上,两个字符串相同的子串越多,它们就越相似,字符串核函数的值就越大.字符串核函数可以由动态规划快速计算

SMO算法

SMO:sequential minimal optimization
利用SMO算法实现SVM的学习

30.png
SMO算法包括两个部分:

1. 求解两个变量二次规划的解析方法(线性规划;把握好对g(x)和Ei的理解)
2. 选择变量的启发式方法(KKT;|E1-E2|最大)

参考:李航,统计学习方法