机器学习:支持向量机(SVM)与Python实现第(一)篇
前言
最近看了Andrew Ng的机器学习视频中的支持向量机,视频的内容比较浅显,没有深入解释支持向量机中的数学原理。但是对于一个比较执着于知道为什么的人,笔者还是去网上查找了有关支持向量机原理以及实现的相关资料。在查找的过程中,笔者发现支持向量机的内容还是蛮多的,于是笔者根据自己的理解,并且参考了一些相关资料,最终写下了支持向量机的四篇博客。
机器学习:支持向量机(SVM)与Python实现第(一)篇——此篇主要介绍了分类间隔,引入SVM。
机器学习:支持向量机(SVM)与Python实现第(二)篇——此篇主要介绍了使用拉格朗日乘子来简化SVM问题的优化。
机器学习:支持向量机(SVM)与Python实现第(三)篇——此篇主要介绍非线性分类(核函数)以及松弛变量。
机器学习:支持向量机(SVM)与Python实现第(四)篇——此篇主要介绍SMO算法并用python实现了简单的SVM分类器。
引子
一开始听到支持向量机这个名词,我还以为是某种机器呢。其实它确实可以算是一个机器,只不过它是算法层面的机器,用来给数据分类的。
首先我们来回顾一下逻辑回归(logistic regression)。在逻辑回归中,我们的假设函数(hypothesis function)为:
对于一个输入
因此,我们其实希望得到的一组
现在,让我们抛开逻辑回归,来考虑一个线性分类的问题。
如上图所示,其中打叉的表示正样本,圆圈表示负样本。直线就是决策边界(它的方程表示为
对于图中的A点来说,它距离决策边界很远。如果要我们预测一下A点对应的y值,我们应该会很确定地说y=1。反过来,对于C点来说,它距离决策边界很近。虽然它也是在决策边界的上方,但是只要决策边界有稍微的改变,它就可能变成在决策边界的下方。所以相比较而言,我们对于预测A点的自信要比预测C点要高。
所以,对于一组训练集,我们希望所有的样本都距离决策边界很远,这样我们确信度就高。而要使样本距离决策边界都很远,我们只需要保证距离决策边界最近的点的距离都很大,那么其它的点的距离肯定就更大了。怎么距离又是说大又是说小呢?理解如下:
分类超平面可以有多个,上图中的灰色线已经将两个类别分开了,但是为什么说它not as good呢?因为距离灰色线最近的点(最下面的红色三角形)的边距很小(small margin)。相反,对于黑色线,距离它最近的点(最上面的红色的三角形)的边距很大(large margin),这个大是指比灰色线的那个margin要大。我们要找的就是看看哪个超平面的最近点的边距最大。
那么我们怎么来刻画这个距离(margin)呢?
首先为了方便,我们分类的标签记为
函数间距(functional margins)与几何间距(geometric margins)
d
如上图,点x到蓝色线的距离
现在让我们来定义一下函数间距。对于一个训练样本
所以,如果
好了,有了函数间距的定义,我们接下来就是要找所有点中间距最小的点了。对于给定的数据集
但是这里有一个问题就是,对于函数间距来说,当w和b被替换成2w和2b时,
考虑上图,直线为决策边界(由w,b决定)。向量w垂直于直线(为什么?
那么,我们应该如何计算
首先我们知道
可以看到,当
同样,有了几何间距的定义,我们接下来就是要找所有点中间距最小的点了。对于给定的数据集
讨论到这里,对于一组训练集,我们要找的就是看看哪个超平面的最近点的边距最大。因为这样我们的确信度是最大的。所以我们现在的问题就是:
写成这样子之后,我们还是没办法直接来求解这个问题,更没有办法写代码来实现训练。怎么办呢?
前面我们说过,对于函数间距来说,等比例缩放w和b不会改变
所以最大化
可能一开始很难理解为什么?其实对于上面的问题,如果那些式子都除以
而最大化
现在,我们把问题转换成一个可以有效求解的问题了。上面的优化问题就是一个典型的二次凸优化问题,这种优化问题可以使用QP(quadratic programming )来求解。但是上面的问题有着特殊结构,通过 Lagrange Duality 变换到对偶变量 (dual variable) 的优化问题之后,可以找到一种更加有效的方法来进行求解,而且通常情况下这种方法比直接使用通用的 QP 优化包进行优化要高效得多。也就说,除了用解决QP问题的常规方法之外,还可以应用拉格朗日对偶性,通过求解对偶问题得到最优解,这就是线性可分条件下支持向量机的对偶算法,这样做的优点在于:一是对偶问题往往更容易求解;二者可以自然的引入核函数,进而推广到非线性分类问题。
那么如何使用拉格朗日乘子来高效求解这个问题呢?我们下一篇博客再来讲解。