盒马唠机器学习之SVM支持向量机
SVM的分类思想本质上和线性回归LR分类方法类似,就是求出一组权重系数,在线性表示之后可以分类。我们先使用一组trainging set来训练SVM中的权重系数,然后可以对testing set进行分类。说的更加更大上一些:SVM就是先训练出一个分割超平面separation hyperplane, 然后该平面就是分类的决策边界,分在平面两边的就是两类。显然,经典的SVM算法只适用于两类分类问题,当然,经过改进之后,SVM也可以适用于多类分类问题。
SVM推导
我们希望找到离分隔超平面最近的点,确保它们离分隔面的距离尽可能远。这里点到分隔面的距离被称为间隔margin. 我们希望这个margin尽可能的大。支持向量support vector就是离分隔超平面最近的那些点,我们要最大化支持向量到分隔面的距离。
给定数据集:(X1,Y1)(X2,Y2)… (Xn,Yn) ,其中Y为样本的类别(当X为正例时候 Y = +1 当X为负例时候 Y = -1 )。决策函数为:
通过上式,其点到直线的距离就可变为:
我们对其做放缩变换:对于决策方程(w,b)我们总是可以通过放缩使得其结果值|Y|>= 1 (之前我们认为恒大于0,现在严格了些) 。
优化目标:
min代表是找出离决策边界最近的点(也就是支持向量),max代表的是使得最近的点离决策边界越远越好。由于
所以我们只需要考虑
目标函数搞定。其约束条件为
接下来就是常规套路了,将求解极大值问题转换成极小值问题啦。
要求求w和b,我们需要先了解下拉格朗日乘子法和KKT条件可以解决的问题:
我们使用拉格朗日乘子法和KKT条件来求w和b,一个重要原因是使用拉格朗日乘子法后,还可以解决非线性划分问题。
分别对w和b求偏导,分别得到两个条件(由于对偶性质)
即 min ( max L ), max L 是因为后面的超平面公式经过减号后变成了 <= 形式,其求和的最大值为0。
得到的两条件为
带入原式可得
这就完成了第一步求解。
继续对ɑ求极大值:
条件为:
极大值转换成求极小值:
是不是看得有点云里雾里的啊?下面我们通过一个实例去理解这个最终公式。
有数据:3个点,其中正例 X1(3,3) ,X2(4,3) ,负例X3(1,1) 。
求解最小值:
其约束条件是:
将数据带入式子:
将a3去掉,化简可得:
分别对ɑ1和ɑ2求偏导,偏导等于0可求得
但是发现并不满足约束的条件,所以解应该是在边界上。可求得:
由此看来只有a2=0时才满足条件。所以最小值在(0.25,0,0.25)处取得。
将ɑ结果带入求解:
可得:
因此平面方程为:
软间隔(soft-margin)
有时候数据中存在一些噪音点,如果考虑它们咱们的分割面就不太好。例如:
实线明显是用之前的方法把两类点完全分开,这个要求是很严格的,泛化性太差。为了解决该问题,我们引入了松弛因子。
因此新的目标函数变为:
当C趋近于很大时:意味着分类严格不能有错误,当C趋近于很小时:意味着可以有更大的错误容忍。
推导和上面差不多:
核变换
一些数据低维的时候不可分,找到一种变换给它映射到高维那不就就可分了。根据机器学习的理论,非线性问题可以通过映射到高维度后,变成一个线性问题。比如:二维下的一个点<x1,x2><x1,x2>, 可以映射到一个5维空间,这个空间的5个维度分是:x1,x2,x1x2,x1^2,x2^2。映射到高维度,有两个问题:一个是如何映射?另外一个问题是计算变得更复杂了。幸运的是我们可以使用核函数(Kernel function)来解决这个问题。核函数(kernel function)也称为核技巧(kernel trick)。
核函数的思想是:我们发现关于向量x的计算,总是在计算两个向量的内积K(x1,x2)=⟨x1,x2⟩K(x1,x2)=⟨x1,x2⟩。因此,在高维空间里,公式的变化只有计算低维空间下的内积⟨x1,x2⟩⟨x1,x2⟩变成了计算高维空间下的内积⟨x′1,x′2⟩⟨x1′,x2′⟩。核函数提供了一个方法,通过原始空间的向量值计算高维空间的内积,而不用管映射的方式。我们可以用核函数代替K(x1,x2)K(x1,x2)。
高斯核函数: