《Machine Learning in Action》—— 剖析支持向量机,单手狂撕线性SVM

2020年11月15日 阅读数:46
这篇文章主要向大家介绍《Machine Learning in Action》—— 剖析支持向量机,单手狂撕线性SVM,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

《Machine Learning in Action》—— 剖析支持向量机,单手狂撕线性SVM

前面在写NumPy文章的结尾处也有提到,原本是打算按照《机器学习实战 / Machine Learning in Action》这本书来手撕其中代码的,但因为实际缘由,可能须要先手撕SVM了,这个算法感受仍是挺让人头疼,其中内部太复杂了,涉及到的数学公式太多了,也涉及到了许多陌声的名词,如:非线性约束条件下的最优化、KKT条件、拉格朗日对偶、最大间隔、最优下界、核函数等等,天书或许、可能、大概就是这样的吧。css

记得与SVM初次邂逅是在17年,那个时候的本身年少轻狂,视图想着站在巨人的肩膀上,把全部本身感兴趣的内容都搞懂,深刻骨髓的那种。但后来残酷的现实让我明白一个道理:你知道的越多,你不知道的也越多。并且那个时候本身也没有能力、资源和机会去深刻SVM内部,彻底没法理解SVM的内部原理。因此,当时本身对SVM的收获只有一个:SVM主要是用来作分类任务的,仅此而已。html

第二次接触SVM是在准备考研复试吧,当时复试并无给出具体内容和范围,并且本身也仍是个初出茅庐的小子,对这种所谓的复试有种莫名的恐惧感。也只有从上届学长学姐的口中,得知复试的时候老师会考究学生是否有科研的潜力,因此最好把机器学习熟知一下。那个时候也是处于新冠疫情的紧张时期嘛,就疯狂补习机器学习的内容,其中就包括支持向量机——SVM,主要的学习渠道是吴恩达老师的机器学习课程,感受讲的的确不错,很是适合我这种菜鸟级选手学习。当时也算是对SVM有了必定的认识吧,也大体了解了SVM的工做原理,固然了,也只是对SVM有了个的浅显的认识,没有手撕SVM的过程,也没有彻底把它整明白。尽管如此,复试的过程依然被面试导师锤的体无完肤,除了问了机器学习相关内容以外,编译原理等一些专业知识对于我这个贸易专业的学生来说可太痛苦了,以前也没有接触过,全程阿巴阿巴。想到这,眼角又又。。。vue

第三次面对SVM也就是如今了,想着不管如何也要打通个人任督二脉,必定要搞清楚SVM的前因后果,也要像面试老师捶我那样,把SVM往死里锤。因而有了下文学习SVM以后的总结,一方面算是从新梳理一遍SVM,另外一方面也但愿来访的读者可以有所收获。python

对于刚刚接触SVM的读者,Taoye主要有如下几条建议,也是我学习SVM过程当中的一个小总结吧:ios

  • SVM内部的数学公式不少,但请不要未战先怯,犯下兵家大忌。不管是阅读该篇文章也好,学习其余相关SVM资源也罢,还请诸君耐心、认真且完整的看完。
  • SVM的原理过程会涉及到不少的符号或记号,必定要梳理清楚他们所表明的含义。另外,推导过程当中会存在不少的向量或矩阵,必定要明白其中shape,这一点可能在不一样的资料中会有不同的处理方式。
  • 在阅读的同时,必定要拿出稿纸手动推演SVM的过程,尽量明白整个过程的前因后果,有不明白的地方能够留言或查找其余相关资料来辅助本身的理解。
  • 阅读一遍或许有很多知识不理解,但多阅读几遍相信必定会有很多收获

本文参考了很多书籍资料以及许多大佬的技术文章,行文风格尽量作到通俗易懂,但其中涉及到的数学公式在所不免,还请诸读者静下心来慢慢品尝。因为我的水平有限,才疏学浅,对于SVM也只是略知皮毛,可能文中有很多表述稍有欠妥、有很多错误或不当之处,还请诸君批评指正。c++

我是Taoye,爱专研,爱分享,热衷于各类技术,学习之余喜欢下象棋、听音乐、聊动漫,但愿借此一亩三分地记录本身的成长过程以及生活点滴,也但愿能结实更多志同道合的圈内朋友,更多内容欢迎来访微信公主号:玩世不恭的Codergit

符号说明

符号 说明
表示单个样本,其中包含多个属性,显示为一个行向量
表示单个样本中的某个属性特征
表示单个样本所对应的标签(具体分类),为整数,非1即-1
表示的是权值行向量,其中,也是所须要训练的参数
表示的是决策面中的,也是所须要训练的参数
表示函数间隔,具体解释见下文
表示几何间隔,具体解释见下文
表示拉格朗日乘子
在这篇文章中表示线性核函数

关于上述的符号说明,仅仅只是本篇文章的一部分,其余符号可经过正文了解。上述符号可能部分暂时不懂,但不要紧,读者可在阅读的过程当中,随时返回来查看,便可理解每一个符号所表明的意义。es6

1、SVM是什么

关于SVM是什么,以前在Byte Size Biology上看到有篇文章很好的解释了SVM,在知乎上也有一位名叫“简之”的用户经过故事的形式来将其进行转述,通俗易懂,很好的向首次接触SVM的读者介绍了SVM能干吗。web

油管上也有更为直观认识SVM的短视频(翻墙):https://www.youtube.com/watch?v=3liCbRZPrZA面试

总结一哈:

对于一个二分类问题,样本数据是线性可分的,咱们则须要经过一根直线(也就是上述例子当中枝条)将两个不一样种类的样本进行分离。按道理来说,咱们已经实现了需求,可是,这根枝条的具体摆放位置可能有无数多个,而咱们的最终目的是将枝条摆放到一个最好的位置,从而当咱们引入了一些新样本的时候,依然能最好很好将两类的数据分离开来,也就是说咱们须要将模型的“泛化性能”最大化。以前也看到过一个例子(来源忘了),这里分享下,大概就是讲:咱们在经过悬崖吊桥的时候,会不自觉的尽量往中间走,由于这样的话,当左右起风的时候,虽然咱们的位置会左右稍微移动,但还不至于跌落悬崖。而越靠近边缘,风险就越大,就是这么个道理。而寻找最大“泛化性能”的过程,就是将枝条摆放在距离小球最远的位置,而小球相对于枝条的位置就是“间隔”,而咱们要作的就是将这间隔最大化

上述仅仅是对于线性可分数据分类的一种处理方式,但有的时候,理想是美好的,现实倒是残酷的。在实际样本数据中,大多都是线性不可分的,也就是说咱们没法找到合适位置的枝条将不一样分类的数据分离开来,更别提“间隔最大化”了。这个时候,咱们就须要将桌上的小球排起,而后用一个平面(纸)将不一样分类小球分离开来。也就是说,咱们将低维度映射到了高纬度,这样对于小球的分类就更加容易了。

再以后,无聊的大人们,把这些球叫作 「data」,把棍子 叫作 「classifier」, 最大间隙trick 叫作「optimization」, 拍桌子叫作「kernelling」, 那张纸叫作「hyperplane」。

2、线性可分SVM与间隔最大化

咱们先来看具体看看线性可分的二分类问题。

假如说,咱们这里有一堆样本,也就是咱们常说的训练集,且表示的是样本属性特征向量,其内部有多个不一样属性,这里咱们不妨指定每一个样本含有两个属性特征,也就是说(之因此用列向量表示,主要是方便后面超平面的构建)。而表示的是每一个样本中全部属性特征所对应的标签,因为这里的问题属性二分类,因此的值只存在两种。为此,咱们能够经过Matplotlib在平面直角坐标系中绘制其图像,初步观察其分布规律,具体代码以下:

import numpy as np
import pylab as pl
from sklearn import svm

%matplotlib inline
print(np.__version__)

"""
    Author: Taoye
    微信公众号:玩世不恭的Coder
"""

if __name__ == "__main__":
    # np.random.seed(100)        # 可自行设置随机种子每次随机产生相同的数据
    X_data = np.concatenate((np.add(np.random.randn(202), [33]),       
                             np.subtract(np.random.randn(202), [33])),
                             axis = 0)      # random随机生成数据,+ -3达到不一样类别数据分隔的目的 

    Y_label = np.concatenate((np.zeros([20]), np.ones([20])), axis = 0)

    svc = svm.SVC(kernel = "linear")
    svc.fit(X_data, Y_label)

    w = svc.coef_[0]      
    ww = -w[0] / w[1]                # 获取权重w
    xx = np.linspace(-66)
    yy = ww * xx - (svc.intercept_[0]) / w[1]   # intercept_获取结截距

    b_down = svc.support_vectors_[0]         # 获得对应的支持向量
    yy_down = ww * xx + (b_down[1] - ww * b_down[0])
    b_up = svc.support_vectors_[-1]
    yy_up = ww * xx + (b_up[1] - ww * b_up[0])

    pl.plot(xx, yy, "k-"); pl.plot(xx, yy_down, "k--"); pl.plot(xx, yy_up, "k--")
    pl.scatter(X_data[:, 0], X_data[:, 1], c = Y_label, cmap = pl.cm.Paired)

    pl.show()

执行代码,能够绘制以下所示图片,注意:以上代码每次运行都会随机产生不一样的二分类数据集,如想每次随机产生相同的数据集,可自行配置np.random.seed随机种子;另外,还有一点须要须要说明的是,上述代码使用到了NumPy,关于NumPy的使用,可自行参考以前写的一篇文章:print( "Hello,NumPy!" )

如上图所示,咱们能够发现,棕色表明一类数据集,此时标签,蓝色表明另外一类数据集,标签,而要想将上图两类数据集分离开来,显然不止一条直线,与上图两条虚线平行且居其之间的任意一条直线都能达到此目的。在这无数条直线中,要数上图中的三条最为特殊,中间实线居于两条虚线中间,咱们通常称其为“决策面”“超平面”,而其所表示的方程,咱们通常称做“决策方程”“超平面方程”,在这里能够表示为。(下面会推导)

从上图咱们还能够观察获得,在全部样本数据集中,虚线上的样本距离决策面最近,咱们把这种比较特殊的样本数据通常称之为“支持向量”,而支持向量到决策面之间的距离称为“间隔”。咱们不难发现,决策面的位置主要取决于支持向量,而与支持向量除外的数据样本没有关系。(由于支持向量的肯定就已经肯定了最大间隔)

关于上述提到的一些关于SVM的名词概念,在正式推演以前,仍是有必要理解清楚的。

前面咱们也有提到,关于能将两类不一样数据集相互分隔开来的直线有无数种,而咱们要想在这无数种直线找到一条最合适的,也就是达到一个间隔最大化的目的,这就是一个“最优化”问题。而最优化问题,咱们须要了解两个因素,分别是目标函数和优化对象。既然咱们是想要达到间隔最大化的目标,那么目标函数天然就是间隔,而优化对象就是咱们的决策面方程。因此,咱们首先须要用数学来明确间隔和决策面方程:

咱们知道,在平面直角坐标系中,一条直线能够用其通常式方程来来表示:

而根据上述图像,咱们能够知道,横纵坐标表明的意义是一个样本的不一样属性特征,而标签则是经过颜色(棕色和蓝色)来进行表示。因此上述的直线的通常式方程中的表示的就是一个样本的两种属性特征,为了方便理解,咱们不妨将其修改成,并将替换为,对此,咱们能够将上述方程向量化,获得:

不能识别此Latex公式:

 \left(
 \begin{matrix}
   w_1, w_2 \\
  \end{matrix}
  \right
  \times
  \left(
 \begin{matrix}
   x^{(1)} \\
   x^{(2)}
  \end{matrix}
  \right) \
    +b=0 \tag{2-1}

,则上述指向方程最终能够表示为:

式(1-2)表示的就是咱们优化问题的优化对象,也就是决策面方程。咱们知道在平面直角坐标系中,一条直线能够经过其斜率和截距来肯定,而在决策面方程里,咱们不可贵到:肯定了决策面的方向(斜率) ,而肯定了决策面的截距。既然咱们已经获得了优化问题的优化对象——决策面方程,那么接下来就须要获得目标函数——间隔的表达式了。

在此,咱们须要引入函数间隔几何间隔的概念了。

通常来说,咱们能够经过样本点到决策面的距离来表示分类预测的正确程度,距离决策面越远,通常分类就越正确(可根据图像自行理解),而在超平面肯定的状况下,咱们能够经过的值来描述样本距超平面的远近(注意:这里是描述远近。而不是确切的距离)。咱们知道,样本有不一样的分类,因此有的时候的符号具备不肯定性,因此咱们能够经过的符号来判断分类结果的正确性。也就是说能够经过值的大小和符号来判断一个样本分类的正确性和正确程度,这个就是咱们的函数间隔(这个概念务必要理解清楚),咱们不妨用来表示:

而咱们知道,上述的,表示的是有个样本,而在个样本中,当然存在一个样本使得该值达到最小,该样本也就是咱们前面所说的支持向量,咱们把支持向量到超平面的函数间隔定义为,则:

咱们只有函数间隔还不够,函数间隔描述的仅仅是样本分类的正确性和正确程度,而不是确切的间隔。当咱们成比例的更改的时候,决策面并无发生任何改变,而函数间隔却发生了改变,因此咱们须要对进行约束,从而当不管怎么成比例变更的时候,咱们的“间隔”都不会发生改变,也就是进行将规范化,由函数间隔规范后的间隔咱们称之为几何间隔,咱们不妨用来表示,则某个样本到超平面的几何间隔为

咱们能够将式子(1-5)理解成点到直线的距离公式(这个在中学时期就学过的)。对于这个二分类问题,咱们不妨将二分类的标签订为 ,则能够表示为(之因此乘以,主要是把绝对值符号去掉,这样就能描述全部样本了,而省去了分类讨论的麻烦):

而咱们知道,上述的,表示的是有个样本,而在个样本中,当然存在一个样本使得该值达到最小,该样本也就是咱们前面所说的支持向量,咱们把支持向量到超平面的几何间隔定义为,则:

经过上述对函数间隔和几何间隔的分析,咱们能够获得他们之间的关系:

自此,咱们已经分析获得了该优化问题的优化对象——决策面方程和目标函数——间隔(几何间隔)。在以前,咱们提到了支持向量的概念,那么支持向量具备什么特性呢?细想一下不难发现,支持向量到决策平面的间隔是最近的,即知足以下式子:

对此,咱们就能够经过数学来表达该优化问题:

前面,咱们提到了,函数间隔描述的仅仅是样本分类的正确性和正确程度,而不是确切的间隔。当咱们成比例的更改的时候,函数间隔虽然发生了改变,但并不会影响咱们的几何间隔——目标函数,也就是说,此时产生了一个等价的最优化问题。为了方便描述问题,咱们不妨取。另外,咱们注意到目标函数能够等价于,(注意,仅仅是等价。而之因此等价为二分之1、平方的形式,主要是方便后期的求导操做),对此,咱们能够将数学表达的优化问题转化为以下形式:

关于如上提到的决策平面和间隔等概念,咱们能够经过下图来直观感觉下(理解清楚):

图片来源:西瓜书
图片来源:西瓜书

至此,咱们已经获得了该优化问题的数学表达,咱们不妨经过一个小例子来检测下:


例子来源:李航-《统计学习方法》第七章内容

例子1:已知一个如图所示的训练数据集,其正例点是,负例点为,试求最大间隔分离的决策面?

根据前面的优化问题表达,咱们能够获得以下表示:

求解能够获得目标函数的最小时,,因而最大间隔分离的决策面为:

其中,为支持向量。


3、拉格朗日乘数法和对偶问题

首先,咱们有必要先了解下什么是拉格朗日乘数法。

关于对偶问题,《统计学习方法》一书中是如此描述的:

为了求解线性可分的支持向量机的最优化问题,将它做为原始最优化问题,应用拉格朗日对偶性,经过求解对偶问题(dual problem)获得原始问题(primary problem)的最优解,这就是线性可分支持向量机的对偶算法(dual algorithm)。这样作的优势,一是对偶问题每每更容易求解;二是天然引入核函数,进而推广到非线性分类问题。

按照前面对优化问题的求解思路,构造拉格朗日方程的目的是将约束条件放到目标函数中,从而将有约束优化问题转换为无约束优化问题。咱们仍然秉承这一思路去解决不等式约束条件下的优化问题,那么如何针对不等式约束条件下的优化问题构建拉格朗日函数呢?

由于咱们要求解的是最小化问题,因此一个直观的想法是若是我可以构造一个函数,使得该函数在可行解区域内与原目标函数彻底一致,而在可行解区域外的数值很是大,甚至是无穷大,那么这个没有约束条件的新目标函数的优化问题就与原来有约束条件的原始目标函数的优化是等价的问题。

对此,咱们从新回顾下原优化问题的数学表达:

关于拉个朗日乘数法的解题思路,其实早在大学《高等数学》这门课程中就已经提到过,咱们不妨经过一个小例子来了解下其解题的通常形式:


例子来源:李亿民-《微积分方法》第二章内容

例子2:求函数上的最值。

作拉格朗日函数

上面的拉格朗日函数,咱们分别对求偏导,获得:

求解获得,因此


上例就是利用拉格朗日求解最优问题的通常思路,先构造拉格朗日函数,而后分别对参数求偏导,最终求解获得最优解。而咱们要想获得最大间隔,一样能够根据该思路进行,只不过式子更加复杂,而咱们还须要利用拉格朗日的对偶性来简化优化问题。

在此以前,咱们先来回顾下该优化问题下的数学表达:

按照咱们例2的思路,咱们首先构造出该优化问题的拉格朗日函数,注意:(2-1)式的限制条件是对于样本 的,而这里的,因此想这样的约束条件有N个,而每一个约束条件都对应一个拉格朗日乘子(例2的),咱们不妨将该拉格朗日乘子定义为。据此,咱们构建出的该优化问题的拉格朗日函数以下:

其中,为拉格朗日乘子向量。

,原始目标函数便可转化为:

根据上述目标函数,咱们能够发现是先求最大值,再求最小值,而内层最小值是关于,而外层最大值是关于,而咱们的又是不等式约束,这样对于求解来说过于麻烦。由拉格朗日的对偶性,原始问题的对偶问题就是极大极小值,其对偶问题以下:

且原问题和对偶问题知足如关系:,而咱们要找的是。读到这里,咱们应该会存在两个疑问:

  • 疑问1:为何前面咱们令$\theta(w,b)=\mathop{max}\limits_{\alpha>0} \ L(w,b,\alpha)$,而不是其余的表达形式呢?

主要是由于,这样替换以后,咱们能使得该函数在可行解区域内与原目标函数彻底一致,而在可行解区域外的数值很是大,甚至是无穷大,那么这个没有约束条件的新目标函数的优化问题就与原来有约束条件的原始目标函数的优化是等价的问题。(这句话要重点理解

令:

以后,在可行解区域以内和可行解区域以外,咱们经过分析获得:在可行解区域以内,

此时,咱们要求的是 ,而减去一个大于等于0的最大值是多少?不就是等于么,而一样也是咱们可行解区域以内的目标函数。也就是说在可行解区域以内,就等价于。同理,咱们能够分析获得,在的可行解区域以外,此时可区域无穷大。因此没有约束的新目标函数的优化问题就与原来有约束条件的原始目标函数的优化是等价的问题,即:

  • 疑问2:为何将原问题转化为对偶问题以后,在什么样的条件下,才会知足$d^= p^$?

转化为对偶问题以后,要使得等式成立,则须要知足以下条件,也就是该问题成立时候的KKT条件

前两个条件咱们不可贵到,前面咱们也有过对其进行分析,那么第三个条件为何须要知足呢?

在介绍支持向量和决策平面的时候,咱们有提到,最终的决策平面只会与支持向量相关,而与其余大多数样本数据(非支持向量)无关。咱们不妨来对它们分别介绍,当样本点为支持向量的时候,此时,即当所取的样本点为非支持向量的时候,要使得,则此时的。因此从总体样本域来说,只有知足的时候,才能到达目标决策平面与支持向量有关,而与其余大多数非支持向量无关。

综上,只有知足KKT条件的时候,才能到达,即在知足KKT条件的时候,才能将原始目标问题,转化为对偶问题,此时二者是等价的,且此时的目标函数为内层关于的最小值,而外层是关于的最大值,这样一来,大大方便了咱们对目标函数的求解。因此优化问题,咱们转化以下:

而要解决这个优化问题,咱们能够分为两步来进行求解:

  1. 先求内层关于的最小值,此时咱们应该将视为常数
  2. 再求外层关于的最大值,因为通过了第一步关于的最小值,这两个参数已经被消掉了,因此第二步只会存在关于的求解

通过上述对目标函数的问题分析,咱们下面根据上述的两个步骤来手握手式的进行求解。

4、模型的求解

关于拉格朗日的内层求解

首先,咱们须要对内层的最小值问题进行求解,即求:

注意,此时仅仅只是关于,而是由外层最大值问题进行求解的,在这里当作常数处理便可。根据例2,咱们须要求出关于的偏导,咱们在这假设每一个样本含有个属性,则,应各位“老婆们”的要求,具体求偏导的详细过程以下:

为了让读者完全明白上述过程,因此步骤有点多,这里就不采用Latex语法来编辑上述公式的推导过程了,固然了,Taoye会尽量地将过程写的足够详细。上述关于拉格朗日函数求偏导的过程,自认为已经写的很详细了,最主要的是要区分的shape问题,以及各自表明的意义是什么。对于上述过程有不清楚的,随时欢迎联系Taoye或在下方留言,也欢迎更多读者来访微信公众号:玩世不恭的Coder。

对此,咱们已经经过上面过程获得关于偏导所要知足的式子:

以后,咱们将式子(4-2)从新带回到(4-1)中的最小值问题中,便可消掉参数,也就是说获得的式子仅仅只是关于,具体代回过程以下图所示:

上图就是将对求导以后所获得的式子待会的完整过程,务必要好好理解清楚。

关于这个代回的过程,有两点仍是有必要说一下的,这也是前几天实验室的同窗存在疑问的地方。(参照上述图片来解疑

  • 疑问1:这里前一项难道不是和后一项一样为0么?由于不是说了$\sum_{i=1}^N\alpha_iy_i=0$啊???

其实这个地方的后一项是为0,而前一项并不必定为0。由于后一项中的其实就至关于一个固定的常数,也就是中的每一项所乘的数都是,这样的话,固定的常数乘以0,结果固然依然等于0咯。

而咱们再看看前一项,能够发现前一项中除了以外,还有的存在,而咱们的是会随着样本的变化而改变的,因此每次乘的数可能并不必定相同。举个例子理解一下吧:,这个咱们都应该知道。当咱们在的前面同时乘以一个相同的数,这个等式是依然成立的,然而当我在前面分别乘以一个并不相同的数,那么这个等式就不成立了,好比 依然成立,而 2+33-45=0就不成立了。

就是这个道理,务必要好好理解清楚。

  • 疑问2:为何这一步能够推导至下面那一步呢???

其实这个问题很好理解,由于这两个成绩形式的式子是相互独立的,也就是说虽然都有,可是这两个并不必定是同时取同一个值的。这就像一种笛卡尔积的形式,因此将前一个式子中的换成
依然成立,因此能推导至下面那一步。。。

经过上述过程,咱们已经获得了代回以后的式子,以下:

而且咱们观察能够发现,式子此时仅仅只存在,而已经成功被消掉了。注意:上式中的表示的样本,也就说这些样本的各个属性特征以及标签都是已知的,因此上式只有是未知的。

至此,咱们已经解决了对偶问题的内层最小值问题,接下来咱们就要求解外层的最大值问题了,将最小值的式子代回原对偶问题,咱们更新下对偶问题,获得以下:

如上,已经将原对偶转换为了上式的样子,下面咱们据此再来看以前的例1


例子来源:李航-《统计学习方法》第七章内容

例子3:已知一个如图所示的训练数据集,其正例点是,负例点为,试求最大间隔分离的决策面?

根据所给数据,其对偶问题是:

咱们将代入到目标函数并记为:


求偏导数并令其为0,易知在点取极值,但该点不知足约束条件,因此最小值应在边界上达到。

时,最小值为;当时,最小值。因此,当时,此时达到最小。

这样的话,就说明所对应的点就是支持向量了,根据,咱们能够求得此时,再由,能够获得

综上,咱们能够获得决策面最终为:

其中,为支持向量。


历经九九八十一难,终于来到了这最后一步了,只要咱们能求得上式的最小值,那么模型的求解也就该到一段落了。

那么,问题来了,关于上式,咱们应当如何求解呢???

下面就应该是咱们的重头戏闪亮登场了——SMO算法,各位看官掌声欢迎一下,有请SMO大佬登台表演。。。

基于SMO算法的外层求解

关于SMO算法,李航老师的《统计学习方法》一书中是这么描述的,

关于外层问题的求解,咱们有许多方法可供使用。当咱们的数据样本比较少的时候,能够将支持向量机的学习问题转换为凸二次规划问题,这样的凸二次规划问题具备全局最优解,而且有许多最优化算法能够用于这一问题的求解。可是当训练样本容量很大时,这些算法每每变得很是低效,以至没法使用。因此,如何高效地实现支持向量机学习就成为一个重要的问题。目前人们已提出许多快速实现算法。而在这些算法中,要数Platt的序列最小最优化(sequential minimal optimization SMO)算法最为人所知。

SMO算法是一种启发式算法,其基本思想是:若是全部变量的解都知足此最优化问题的KKT条件,那么这个最优化问题的解就获得了。由于KKT条件是该最优化问题的充分必要条件。不然,选择两个变量,固定其余变量,针对这两个变量构建一个二次规划问题。这个二次规划问题关于这两个变量的解就应该更接近原始二次规划问题的解,由于这会使得原始二次规划问题的目标函数值变得更小。更重要的是,这时子问题能够经过解析方法求解,这样就能够大大提升整个算法的计算速度。子问题有两个变量,一个是违反KKT条件最严重的那一个,另外一个由约束条件自动肯定。如此,SMO算法将原问题不断分解为子问题并对子问题求解,进而达到求解原问题的目的。

上述内容来自李航——《统计学习方法》第二版。

不知道大伙读完上述关于内容是什么感觉,这里简单总结一下李航老师所表达的意思吧。

在Taoye的印象里,小学时期上语文课的时候学习过一篇文章叫作《走一步,再走一步》。(具体几年级就记不清楚了)

嘿!您还别说,刚刚去搜索了下这篇课文,还真就叫这个名儿。第一次读李航老师《统计学习方法》中关于SMO的内容以后,就让我想起这篇文章。我还专门从新读了一下这篇文章,主要讲的内容是这样的:

文章中主人公名叫小亨特,他不是天生体弱怯懦嘛,在一次和小伙伴攀登悬崖的时候,因为心里的恐惧、惧怕,在攀登途中上不去,也下不来。而后呢,他的小伙伴杰里就把小亨特的父亲找来了,父亲对小亨特说:“不要想有多远,有多困难,你须要想的是迈一小步。这个你能作到。看着手电光指的地方。看到那块石头没有?”,最终经过父亲的鼓励,小亨特成功脱险。文末做者还总结道:在我生命中有不少时刻,每当我遇到一个高不可攀、使人惧怕的情境,并感到惶恐不安时,我都可以应付——由于我回想起了好久之前本身上过的那一课。我提醒本身不要看下面遥远的岩石,而是注意相对轻松、容易的第一小步,迈出一小步、再一小步,就这样体会每一步带来的成就感,直到完成了本身想要完成的,达到了本身的目标,而后再回头看时,不由对本身走过的这段漫漫长路感到惊讶和自豪。

把《走一步,再走一步》这篇文章搬出来,真的不是在凑字数从而给你们阅读带来压力,只是以为SMO算法描述的就是这么个理儿。算了,很少说了,说多了还真的会有凑字数的嫌疑。(ノへ ̄、)

下面咱们开始进入到SMO吧。。。

在这以前,咱们把外层的最小值问题再搬出来:

在这里,咱们是假设对于全部的样本数据都是100%线性可分的。

对于该优化问题的SMO算法,咱们能够这样理解:由于在咱们的数据集中,属于每一个样本的属性特征,为样本所对应的标签,而这些都是已知的,上述优化问题的目标函数只存在为未知变量,且未知变量有个。而根据SMO算法的思想,咱们每次只将其中两个看作变量,而其余仅仅只是常数。在却肯定其中一个变量的时候,另外一个变量就能够经过约束获得。咱们不妨将该两个变量定为,则SMO不断执行以下两个步骤直至收敛:

  • 选取一对须要更新的变量
  • 固定之外的参数,根据求解式(4-5)得到更新后
  • 更新好以后,从新选取两个进行不断更新迭代(重复一、2步骤)

讲到这里,SMO算法是否是和《走一步,再走一步》中主人公相似呢?将一个大的、复杂的问题转换成多个小问题,而后不断的迭代更新。

为何咱们每次都同时优化两个参数,而不是一个呢?由于每次更新两个参数,才能确保约束条件成立。而当咱们仅仅只是修改一个时,那么就将违背这个约束条件了。

据SMO的思想,咱们不妨把目标函数中的单独拎出来,以下:

注意:由于咱们的仅仅只是对做为参数,而只是做为一个参数而存在。还有一点须要注意的是,由于咱们是二分类问题,且样本数据的标签为非1即-1,因此,这个在化简过程当中须要用到。此时咱们获得关于的目标函数为:

咱们知道对于这个式子是有一个约束条件的,咱们能够根据这个用来表示(注意:),以下:

经过上式,用来表示,咱们不妨将带到中,获得一个只关于的式子:

此时的仅仅只是关于的函数,咱们将进行求导,并令导数为0:



上述就是SMO中限制其中两个变量的推到过程的推到过程(公式太多,过程有点复杂,确实不方便使用Latex语法,不过过程都已经写的很详细了,仍是须要静下心来慢慢手动推导的)下面总结一下上述SMO算法的过程吧:

前面咱们不是获得了仅仅关于为变量的么,也就是说此时的未知数只有一个,咱们要求的最值应该怎么求呢?固然是对其进行求导咯,而后对导数为0,便可解出取最值时候的,整理以后获得以下式子:

此时,咱们能够发现除了数据样本相关信息和以外,还有的存在,而咱们前面也又说到,SMO算法自己是一个不断迭代更新的过程,咱们须要的是能够经过的更新以前的来修改,从而获得一个新的,咱们不妨令新的、旧的。而咱们知道旧的之间须要知足一个限制条件:

因此,咱们从新将代回到式,用来代替,(要时刻注意:)获得:

以后咱们经过前面拉格朗日获得的关系式,用来代替(4-10)后面的两个级数,整理最终获得:

PS:关于是什么,请见上图中的内容。

经过如上式子,咱们就能求得更新以后的,而SMO算法的核心在于两两不断的更新迭代,因此最终咱们会获得,每一个样本都会对应一个,而前面咱们也有说过,决策面最终只会与支持向量有关,而与非支持向量的样本无关,因此大多数的都等于0,只有少数为非0。如此一来,咱们就能求解获得向量:,随后,咱们就能经过就能求得参数

还有一点须要注意的是,上述过程都是默认全部样本数据都是线性可分的,也就是说没有一个样本会被误分类。但这只是理想状态下,而实际难免会有个别数据不得不被误分类,这时咱们须要定义惩罚参数和容错率,而容错率是用来不断优化的,主要经过实际值与真实值获得。而惩罚参数咱们定为,而要想成功更新获得,则须要肯定的范围。对此,咱们不妨定义以下:

而咱们知道:

综合上式,能够肯定的范围:

而这个在不一样状况下的的范围,咱们会在下面实际编程的时候须要用到,主要是用来更新值。

接下来,就是更新值了。前面咱们已经定义了惩罚参数,且,此时经过更新获得的当然是相等的;但假如咱们更新以后的不在这个区间以内,则此时获得的是不相等的,因此咱们须要肯定在不一样状况下更新以后的值:

前面,咱们已经获得:

由于咱们是打算经过的值来获得更新以后的,因此把单独拎出来,获得:

同时,由于上述中的级数形式可使用来表示,因此整理以后得:

同理,能够获得

当更新以后的都有效的时候,即在区间以内时,此时,而在不知足上述条件的时候,咱们更新以后的的均值,即:

如此一来,咱们就已经完成了SMO算法的流程,该有的参数都已经求解出来了。

说实话,写到这,Taoye的确有点累了,脑细胞也严重不足了,但为了各位“老婆们”的正常阅读,仍是得继续写下去才行。

下面,咱们就经过编程来实现线性SVM算法吧!(本次手撕SVM的数据集依然采用咱们前面所随机建立的)

5、编程手撕线性SVM

在前面,咱们其实已经实现了线性SVM的分类,只不过那个时候使用的是sklearn内置的接口。但既然是手撕SVM,固然是须要本身来实现这一功能的。

在这里须要提早说明的是,上述代码大量使用到了NumPy操做,关于NumPy的使用,可自行参考以前写的一篇文章:print( "Hello,NumPy!" )

训练SVM模型,没数据集可不行,本次手撕SVM的数据集依然采用咱们前面所随机建立,对此,咱们定义一个etablish_data方法来随机建立一个SVM二分类数据集:

"""
    Author: Taoye
    微信公众号: 玩世不恭的Coder
    Explain: 用于生成训练数据集
    Parameters:
        data_number: 样本数据数目
    Return:
        x_data: 数据样本的属性矩阵
        y_label: 样本属性所对应的标签
"""

def etablish_data(data_number):
    x_data = np.concatenate((np.add(np.random.randn(data_number, 2), [33]),       
                             np.subtract(np.random.randn(data_number, 2), [33])),
                             axis = 0)      # random随机生成数据,+ -3达到不一样类别数据分隔的目的 
    temp_data = np.zeros([data_number])
    temp_data.fill(-1)
    y_label = np.concatenate((temp_data, np.ones([data_number])), axis = 0)
    return x_data, y_label

前面,咱们在讲解SMO算法的时候提到,每次都会选取随机两个来进行更新,这里咱们不妨将第一个经过遍历的形式逐个选取,而另外一个则经过np.random模块来随机选取,这里须要主要的是,第二个选取的不能与第一个相同。为此,咱们定义一个方法random_select_alpha_j来随机选取第二个(第一个已经经过遍历获得):

"""
    Author: Taoye
    微信公众号: 玩世不恭的Coder
    Explain: 随机选取alpha_j
    Parameters:
        alpha_i_index: 第一个alpha的索引
        alpha_number: alpha总数目
    Return:
        alpha_j_index: 第二个alpha的索引
"""

def random_select_alpha_j(alpha_i_index, alpha_number):
    alpha_j_index = alpha_i_index
    while alpha_j_index == alpha_i_index:
        alpha_j_index = np.random.randint(0, alpha_number)
    return alpha_j_index

咱们知道,每个更新以后的都须要知足。为此,咱们定义一个方法modify_alpha来肯定在区间以内:

"""
    Author: Taoye
    微信公众号: 玩世不恭的Coder
    Explain: 使得alpha_j在[L, R]区间以内
    Parameters:
        alpha_j: 原始alpha_j
        L: 左边界值
        R: 右边界值
    Return:
        L,R,alpha_j: 修改以后的alpha_j
"""

def modify_alpha(alpha_j, L, R):
    if alpha_j < L: return L
    if alpha_j > R: return R
    return alpha_j

咱们模型训练是一个迭代更新的过程,而更新的前提是偏差比较大,因此咱们须要定义一个方法calc_E_i来计算偏差,但偏差又怎么计算呢?这一点其实咱们在最开始就已经提到过了,偏差是经过模型计算出来的值与其真实值最差获得,也就是前面提到的下面的推导务必要理解清楚,矩阵变换要十分熟悉):