5.1支持向量机(SVM)算法(上)
1.背景:
1.1最早是由VIadimir N.Vapnik和Alexey Ya.Chervonenkis在1963年提出
1.2目前的版本(soft margin)是由Cornnia Cortes和Vapnik在1993年提出,并在1995年发表
1.3深度学习(2012)出现之前,SVM被认为机器学习中近十几年来最成功,表现最好的算法
2.机器学习的一般框架:
训练集 =》提取特征向量 =》结合一定的算法(分类器:比如决策树,KNN)=》得到训练好的模型(当有新的实例来的时候就可以用训练好的模型对它进行预测和分类)
3.介绍:
3.1例子:
两类?哪条线最好?
3.2 SVM寻找区分两类的超平面(hyper plane),使边际(margin)最大
(1)总共可以有多少个可能的超平面?无数个
(2)如何选取使边际(margin)最大的超平面(Max Margin Hyperplane)(将边际设置为最大是为了减小犯错的机会)
(3)超平面到一侧最近点的距离等于到另一侧最近点的距离,两侧的两个超平面平行
3.3线性可区分(linear separable)和线性不可区分(linear inseparable):上面是线性可区分,下面是线性不可区分
4.定义与公式建立
超平面可以定义为:
W*X + b = 0
W:weight vector,
W = {w1,w2,w3,.....,wn},n是特征值的个数
X:训练实例
b:bias
4.1假设2维特征向量:X = {x1,x2},把b想象为额外的weight,泽超平面方程变为:
w0 + w1x1 + w2x2 = 0
所有超平面右上方的点满足:
w0 + w1x1 +w2x2 > 0
所有超平面左下方的点满足:
w0 + w1x1 +w2x2 < 0
调整weight,使超平面定义边际的两边:
H1:w0 + w1x1 + w2x2 >=1 for yi = +1
H2:w0 + w1x1 + w2x2 <=-1 for yi = -1
综合以上两式,得到:
yi(w0 + w1x1 + w2x2) >=1,任意i. (1)
所有坐落在边际的两边的超平面上的点被称作“支持向量(support vectors)”
分界的超平面到H1或H2上任意一点的距离为:
(i.e:其中是向量的范数(norm))
所以,最大边际距离为:
5.求解
5.1SVM如何找出最大边际的超平面呢(MMH)?
利用一些数学推倒,以上公式(1)可变为有限制的凸优化问题(convex quadratic optimization)
利用Karush-Kuhn-Tucker(KKT)条件和拉格朗日公式,可以推出MMH可以被表示为以下“决定边界”(decision boundary)
其中,yi是支持向量点Xi(support vector)的类别标记(class lable)
是要测试的实例
和b0都是单一数值型参数,由以上提到的最优算法得出
l是支持向量点的个数
5.2对于任何测试(要归类的)实例,带入以上公式,得出的符号是正还是负决定
6.例子: