Press "Enter" to skip to content

机器学习:SVM(支持向量机)原理推导

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

据说SVM是机器学习的分水岭,翻过这座大山机器学习就在眼前。本篇将详细介绍SVM的原理推导过程,包括线性、近线性、非线性、优化方法等,大量思想都源自于《统计学习方法》和刘顺祥《零基础入门python数据挖掘与分析》。

 

首先我们介绍数学中的 距离公式 :

 

 

d 表示 二位空间的一个点到直线 Ax+By+C=0的距离。

 

一、线性可分的SVM

 

引申出函数间隔的概念

 

此概念是所有SVM推导的核心,我们用式子表示:

 

 

式子并不复杂,我们分别介绍参数名称及含义:

 

等式左边代表 函数间隔 ,《统计学习方法》称硬间隔。

 

yi 为样本点类别yi={1,-1},分类用的-1和1,没有使用1和0是因为和后面计算有关。

 

xi 为样本点。

 

W’为超平面参数矩阵W的转置。

 

b 为超平面参数

 

函数间隔性质:

 

1、函数间隔永大于0,因为样本在超平面两侧正负号不同,分类的正负号也不同。

 

2、直线y=W’x+b为通过某一样本点的直线,同比例增加W’和b直线不变,但是函数间隔会成比例增加,因此我们需要对原来函数间隔进行单位化处理。

 

 

此时我们的函数间隔就和距离公式的距离是一样的形式了。

 

此时的γ具有几何意义,故城几何间隔。

 

机器学习的关键我认为是构造目标函数,目标函数直接决定了模型的性质。

 

构造目标函数

 

这里我们稍微讲一下SVM的核心思路,我们找到一个最大限度区分样本的超平面。说的非常宽泛无数学含义,我们可以举个例子,比如印度贫富差距大,但贫富的分布是和地理有关系的,假设某一地区可以用一条线把富人区和贫民区完全且完美的分割开来,线是没有面积的,但是我们希望这条线尽可能的宽,越宽我们分的越清晰,甚至我们可以贴着样本划线取得最宽 分割带(超平面) 。比如挖一条河河越宽两岸的分界线就越明显,分析预测就越可靠。放到上面就是我们要求最大的几何间隔γ,并且我们所有点都必须在超平面之外,即所有样本点到超平面的距离都必须大于最大几何间隔γ。

 

 

如果超平面参数w,b同比例增长,函数间隔会成增长,但是几何间隔不会,上述关系也不会受到影响。对于函数间隔:yi类别的取值就可以定为任意值,-2,2,-0.1,0.1这种都行。这样我们可以使最近的几何间隔对应的函数间隔取1。

 

《统计学习方法》也只是稍微提了一下对函数优化没有影响所以取1,这里我把它细化一下,我们取的是离超平面最近距离的点的函数间隔取1,无论你是增缩yi,还是超平面参数w、b,都可以做到而且对优化函数没有影响。

 

如图下图转换函数:

 

 

这就转化为一个凸二次规划的问题,普遍存在于机器学习问题。所以要掌握。

 

拉格朗日乘数法:

 

首先看一下拉格朗日乘数发的形式:

 

 

图片展示的是最小的目标函数f(x)在受到g(x)>0的约束条件时的拉格朗日函数形式。其中,λ i 即为拉格朗日乘子,且λ i >0。上式就称为广义拉格朗日函数的极小极大问题。在求解极小值问题时,还需要利用对偶性将极小极大问题转换为极大极小问题,即

 

 

根据如上介绍的拉格朗日数乘法,就可以将目标函数重新表示为

 

 

看似未知变量挺多,但是是可以求最优的问题。

 

首先我们求minw,b部分,满足最小的目标函数的参数值。

 

对w、b分别求导并令其导函数为0:

 

 

在将求出的w值带入原式子,求max α的部分。

 

 

原来的目标函数经过拉格朗日乘子法的变换,把二次规划的问题变成关于拉格朗日乘子α求函数最大值的问题。接下来我们的问题就是求满足条件的α。

 

即:

 

 

由于限制条件是个等式,在最优化的时候会好求的多,如果所有的解都不能满足以上条件,则代表α只能在边界取得最优化值,带入多个边界值,比较最优解。

 

这种算法非常繁琐,于是延伸出一种非常好用的算法SMO算法。

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注