机器学习(18)之支持向量机原理(三)线性不可分支持向量机与核函数

关键字全网搜索最新排名

【机器学习算法】:排名第一

【机器学习】:排名第二

【Python】:排名第三

【算法】:排名第四

前言

在(机器学习(15)之支持向量机原理(一)线性支持向量机)和(机器学习(16)之支持向量机原理(二)软间隔最大化)中我们讲到了线性可分SVM的硬间隔最大化和软间隔最大化的算法,它们对线性可分的数据有很好的处理,但是对完全线性不可分的数据没有办法。本文我们就来探讨SVM如何处理线性不可分的数据,重点讲述核函数在SVM中处理线性不可分数据的作用。

多项式回归

在线性回归原理中,我们讲到了如何将多项式回归转化为线性回归。比如一个只有两个特征的p次方多项式回归的模型:

得到了下式:

可以发现,又重新回到了线性回归,这是一个五元线性回归,可以用线性回归的方法来完成算法。也就是说,对于二维的不是线性的数据,我们将其映射到了五维以后,就变成了线性的数据。这给了我们启发,也就是说对于在低维线性不可分的数据,在映射到了高维以后,就变成线性可分的了。这个思想我们同样可以运用到SVM的线性不可分数据上。也就是说,对于SVM线性不可分的低维特征数据,我们可以将其映射到高维,就能线性可分,此时就可以运用前两篇的线性可分SVM的算法思想了。

引入核函数

线性不可分的低维特征数据,可以将其映射到高维,就能线性可分。现在我们将它运用到我们的SVM的算法上。线性可分SVM的优化目标函数:

上式低维特征仅仅以内积xi∙xj的形式出现,如果我们定义一个低维特征空间到高维特征空间的映射ϕ(比如上一节2维到5维的映射),将所有特征映射到一个更高的维度,让数据线性可分,我们就可以继续按前两篇的方法来优化目标函数,求出分离超平面和分类决策函数了。也就是说现在的SVM的优化目标函数变成:

看起来似乎这样就已经完美解决了线性不可分SVM的问题了,但是事实是不是这样呢?我们看看,假如是一个2维特征的数据,我们可以将其映射到5维来做特征的内积,如果原始空间是三维,可以映射到到19维空间,似乎还可以处理。但是如果我们的低维特征是100个维度,1000个维度呢?那么我们要将其映射到超级高的维度来计算特征的内积。这时候映射成的高维维度是爆炸性增长的,这个计算量实在是太大了,而且如果遇到无穷维的情况,就根本无从计算了。

核函数的隆重出场

假设ϕ是一个从低维的输入空间χ(欧式空间的子集或者离散集合)到高维的希尔伯特空间的H映射。那么如果存在函数K(x,z),对于任意x,z∈χ,都有:

那么就称K(x,z)为核函数。

仔细观察上式可以发现,K(x,z)的计算是在低维特征空间来计算的,它避免了在刚才我们提到了在高维维度空间计算内积的恐怖计算量。也就是说,核函数的价值在于它虽然也是将特征进行从低维到高维的转换,但核函数好在它在低维上进行计算,而将实质上的分类效果(利用了内积)表现在了高维上,这样避免了直接在高维空间中的复杂计算,真正解决了SVM线性不可分的问题。

核函数详解

对于从低维到高维的映射,核函数不止一个。那么什么样的函数才可以当做核函数呢?由于一般我们说的核函数都是正定核函数,这里我们直说明正定核函数的充分必要条件。一个函数要想成为正定核函数,必须满足他里面任何点的集合形成的Gram矩阵是半正定的。也就是说,对于任意的,xi∈χ,i=1,2,3...m, K(xi,xj)对应的Gram矩阵K=[K(xi,xj)] 是半正定矩阵,则K(x,z)是正定核函数。从上面的定理看,它要求任意的集合都满足Gram矩阵半正定,所以自己去找一个核函数还是很难的,怎么办呢?下面我们来看看常见的核函数, 选择这几个核函数介绍是因为scikit-learn中默认可选的就是下面几个核函数。

线性核函数

线性核函数(Linear Kernel)其实就是我们前两篇的线性可分SVM,表达式为:

也就是说,线性可分SVM我们可以和线性不可分SVM归为一类,区别仅仅在于线性可分SVM用的是线性核函数。

多项式核函数

多项式核函数(Polynomial Kernel)是线性不可分SVM常用的核函数之一,表达式为:

其中,γ,r,d都需要自己调参定义。

高斯核函数

高斯核函数(Gaussian Kernel),在SVM中也称为径向基核函数(Radial Basis Function,RBF),它是非线性分类SVM最主流的核函数。libsvm默认的核函数就是它。表达式为:

其中,γ大于0,需要自己调参定义。

Sigmoid核函数

Sigmoid核函数(Sigmoid Kernel)也是线性不可分SVM常用的核函数之一,表达式为:

其中,γ,r都需要自己调参定义。

SVM小结

引入了核函数后,我们的SVM算法才算是比较完整了。现在我们对分类SVM的算法过程做一个总结。不再区别是否线性可分。

输入是m个样本(x1,y1),(x2,y2),...,(xm,ym),,其中x为n维特征向量。y为二元输出,值为1,或者-1.

输出是分离超平面的参数和w∗和b∗和分类决策函数。

算法过程

1)选择适当的核函数K(x,z)和一个惩罚系数C>0, 构造约束优化问题

2)用SMO算法求出上式最小时对应的α向量的值α∗向量.

3) 得到

4) 找出所有的S个支持向量,即满足0<αs<C对应的样本(xs,ys),计算出每个支持向量(xs,ys)对应的偏置b,最终的偏置项为所有值的平均

最终的分类超平面为

最终的分类决策函数为

至此,我们的分类SVM算是总结完毕。

欢迎分享给他人让更多的人受益

参考:

  1. 博客园(作者:刘建平) http://www.cnblogs.com/pinard/p/6103615.html
  2. 周志华《机器学习》
  3. 李航《统计学习方法》

原文发布于微信公众号 - 机器学习算法与Python学习(guodongwei1991)

原文发表时间:2017-09-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏汪毅雄的专栏

机器学习之回归(二):广义线性模型(GLM)

本文在上篇线性回归的基础上,延伸到广义线性模型,并把广义线性模型目的、假设条件来源,指数族分布、连接函数等各个函数的关系都进行详细地解释。最后用两个常见的 GL...

1.4K1
来自专栏深度学习

神经网络相关名词解释

很多人认为深度学习很枯燥,大部分情况是因为对深度学习的学术词语,特别是专有名词很困惑,即便对相关从业者,亦很难深入浅出地解释这些词语的含义。 

3797
来自专栏SIGAI学习与实践平台

深入浅出聚类算法

聚类问题是机器学习中无监督学习的典型代表,在数据分析、模式识别的很多实际问题 中得到了应用。在本文中,SIGAI 将为大家深入浅出的介绍聚类问题的定义以及各种典...

1501
来自专栏量子位

卷积神经网络在图像分割中的进化史:从R-CNN到Mask R-CNN

王小新 编译自 Medium 量子位 出品 | 公众号 QbitAI 卷积神经网络(CNN)不仅能用来对图像进行分类,还在图像分割任务重有着广泛的应用。 Dh...

3965
来自专栏信数据得永生

《Scikit-Learn与TensorFlow机器学习实用指南》第5章 支持向量机

5138
来自专栏机器学习算法工程师

Mask-RCNN论文解读

Mask R-CNN是基于Faster R-CNN的基于上演进改良而来,FasterR-CNN并不是为了输入输出之间进行像素对齐的目标而设计的,为了弥补这个不足...

6878
来自专栏ATYUN订阅号

每个机器学习工程师都应该知道的基本算法

机器学习作为一门多领域交叉学科,已经存在很长时间了,但近些年才开始火热起来。本文中列出了你需要知道的机器学习领域的算法,了解这些你就可以解决在机器学习中所遇到的...

3668
来自专栏人工智能LeadAI

机器学习必须熟悉的算法之word2vector

word2vector已经成为NLP领域的基石算法。作为一名AI 从业者,如果不能主动去熟悉该算法,应该感到脸红。本文是一篇翻译的文章,原文链接是:http:/...

94215
来自专栏人工智能

神经网络基础

3.1. 神经网络基础 3.1.1 神经元(Neuron) 就像形成大脑基本元素的神经元一样,神经元是构成神经网络的基本结构。想象一下,当大脑得到新信息时如何处...

1978
来自专栏SeanCheney的专栏

《Scikit-Learn与TensorFlow机器学习实用指南》 第5章 支持向量机

支持向量机(SVM)是个非常强大并且有多种功能的机器学习模型,能够做线性或者非线性的分类,回归,甚至异常值检测。机器学习领域中最为流行的模型之一,是任何学习机器...

2642

扫码关注云+社区