SVM原理与实现

1. 讲讲SVM

1.1 一个关于SVM的童话故事

支持向量机(Support Vector Machine,SVM)是众多监督学习方法中十分出色的一种,几乎所有讲述经典机器学习方法的教材都会介绍。关于SVM,流传着一个关于天使与魔鬼的故事。

传说魔鬼和天使玩了一个游戏,魔鬼在桌上放了两种颜色的球。魔鬼让天使用一根木棍将它们分开。这对天使来说,似乎太容易了。天使不假思索地一摆,便完成了任务。魔鬼又加入了更多的球。随着球的增多,似乎有的球不能再被原来的木棍正确分开,如下图所示。

SVM实际上是在为天使找到木棒的最佳放置位置,使得两边的球都离分隔它们的木棒足够远。依照SVM为天使选择的木棒位置,魔鬼即使按刚才的方式继续加入新球,木棒也能很好地将两类不同的球分开。

看到天使已经很好地解决了用木棒线性分球的问题,魔鬼又给了天使一个新的挑战,如下图所示。

按照这种球的摆法,世界上貌似没有一根木棒可以将它们 完美分开。但天使毕竟有法力,他一拍桌子,便让这些球飞到了空中,然后凭借 念力抓起一张纸片,插在了两类球的中间。从魔鬼的角度看这些 球,则像是被一条曲线完美的切开了。

后来,“无聊”的科学家们把这些球称为“数据”,把木棍称为“分类面”,找到最 大间隔的木棒位置的过程称为“优化”,拍桌子让球飞到空中的念力叫“核映射”,在 空中分隔球的纸片称为“分类超平面”。这便是SVM的童话故事。

1.2 理解SVM:第一层

支持向量机,因其英文名为support vector machine,故一般简称SVM,通俗来讲,它是一种二类分类模型,其基本模型定义为特征空间上的间隔最大的线性分类器,其学习策略便是间隔最大化,最终可转化为一个凸二次规划问题的求解。

线性分类器:给定一些数据点,它们分别属于两个不同的类,现在要找到一个线性分类器把这些数据分成两类。如果用x表示数据点,用y表示类别(y可以取1或者0,分别代表两个不同的类),一个线性分类器的学习目标便是要在n维的数据空间中找到一个超平面(hyper plane),这个超平面的方程可以表示为( wT中的T代表转置):

这里可以查看我之前的逻辑回归章节回顾:

逻辑回归(LR),损失函数

这里我直接给出几何间隔的公式,详细推到请查看博文:

https://blog.csdn.net/v_july_v/article/details/7624837

OK,到此为止,算是了解到了SVM的第一层,对于那些只关心怎么用SVM的朋友便已足够,不必再更进一层深究其更深的原理。

1.2.3 最大间隔损失函数Hinge loss

SVM 求解使通过建立二次规划原始问题,引入拉格朗日乘子法,然后转换成对偶的形式去求解,这是一种理论非常充实的解法。这里换一种角度来思考,在机器学习领域,一般的做法是经验风险最小化 (empirical risk minimization,ERM),即构建假设函数(Hypothesis)为输入输出间的映射,然后采用损失函数来衡量模型的优劣。求得使损失最小化的模型即为最优的假设函数,采用不同的损失函数也会得到不同的机器学习算法。SVM采用的就是Hinge Loss,用于“最大间隔(max-margin)”分类。

通常人们会从一些常用的核函数中选择(根据问题和数据的不同,选择不同的参数,实际上就是得到了不同的核函数),例如:多项式核、高斯核、线性核。

读者可能还是没明白核函数到底是个什么东西?我再简要概括下,即以下三点:

  1. 实际中,我们会经常遇到线性不可分的样例,此时,我们的常用做法是把样例特征映射到高维空间中去(映射到高维空间后,相关特征便被分开了,也就达到了分类的目的);
  2. 但进一步,如果凡是遇到线性不可分的样例,一律映射到高维空间,那么这个维度大小是会高到可怕的。那咋办呢?
  3. 此时,核函数就隆重登场了,核函数的价值在于它虽然也是将特征进行从低维到高维的转换,但核函数绝就绝在它事先在低维上进行计算,而将实质上的分类效果表现在了高维上,避免了直接在高维空间中的复杂计算。

如果数据中出现了离群点outliers,那么就可以使用松弛变量来解决。

1.3.3 总结

不准确的说,SVM它本质上即是一个分类方法,用 w^T+b 定义分类函数,于是求w、b,为寻最大间隔,引出1/2||w||^2,继而引入拉格朗日因子,化为对拉格朗日乘子a的求解(求解过程中会涉及到一系列最优化或凸二次规划等问题),如此,求w.b与求a等价,而a的求解可以用一种快速学习算法SMO,至于核函数,是为处理非线性情况,若直接映射到高维计算恐维度爆炸,故在低维计算,等效高维表现。

OK,理解到这第二层,已经能满足绝大部分人一窥SVM原理的好奇心,针对于面试来说已经足够了。

1.4 SVM的应用

SVM在很多诸如文本分类,图像分类,生物序列分析和生物数据挖掘,手写字符识别等领域有很多的应用,但或许你并没强烈的意识到,SVM可以成功应用的领域远远超出现在已经在开发应用了的领域。

2. SVM的一些问题

  1. 是否存在一组参数使SVM训练误差为0? 答:存在
  2. 训练误差为0的SVM分类器一定存在吗? 答:一定存在
  3. 加入松弛变量的SVM的训练误差可以为0吗? 答:使用SMO算法训练的线性分类器并不一定能得到训练误差为0的模型。这是由 于我们的优化目标改变了,并不再是使训练误差最小。
  4. 带核的SVM为什么能分类非线性问题? 答:核函数的本质是两个函数的內积,通过核函数将其隐射到高维空间,在高维空间非线性问题转化为线性问题, SVM得到超平面是高维空间的线性分类平面。其分类结果也视为低维空间的非线性分类结果, 因而带核的SVM就能分类非线性问题。
  5. 如何选择核函数?
    • 如果特征的数量大到和样本数量差不多,则选用LR或者线性核的SVM;
    • 如果特征的数量小,样本的数量正常,则选用SVM+高斯核函数;
    • 如果特征的数量小,而样本的数量很大,则需要手工添加一些特征从而变成第一种情况。

3. LR和SVM的联系与区别

3.1 相同点

  • 都是线性分类器。本质上都是求一个最佳分类超平面。
  • 都是监督学习算法。
  • 都是判别模型。判别模型不关心数据是怎么生成的,它只关心信号之间的差别,然后用差别来简单对给定的一个信号进行分类。常见的判别模型有:KNN、SVM、LR,常见的生成模型有:朴素贝叶斯,隐马尔可夫模型。

3.2 不同点

  • LR是参数模型,svm是非参数模型,linear和rbf则是针对数据线性可分和不可分的区别;
  • 从目标函数来看,区别在于逻辑回归采用的是logistical loss,SVM采用的是hinge loss,这两个损失函数的目的都是增加对分类影响较大的数据点的权重,减少与分类关系较小的数据点的权重。
  • SVM的处理方法是只考虑support vectors,也就是和分类最相关的少数点,去学习分类器。而逻辑回归通过非线性映射,大大减小了离分类平面较远的点的权重,相对提升了与分类最相关的数据点的权重。
  • 逻辑回归相对来说模型更简单,好理解,特别是大规模线性分类时比较方便。而SVM的理解和优化相对来说复杂一些,SVM转化为对偶问题后,分类只需要计算与少数几个支持向量的距离,这个在进行复杂核函数计算时优势很明显,能够大大简化模型和计算。
  • logic 能做的 svm能做,但可能在准确率上有问题,svm能做的logic有的做不了。

4. 线性分类器与非线性分类器的区别以及优劣

线性和非线性是针对模型参数和输入特征来讲的;比如输入x,模型y=ax+ax^2 那么就是非线性模型,如果输入是x和X^2则模型是线性的。

  • 线性分类器可解释性好,计算复杂度较低,不足之处是模型的拟合效果相对弱些。 LR,贝叶斯分类,单层感知机、线性回归
  • 非线性分类器效果拟合能力较强,不足之处是数据量不足容易过拟合、计算复杂度高、可解释性不好。 决策树、RF、GBDT、多层感知机

SVM两种都有(看线性核还是高斯核)

5. 代码实现

本文分享自微信公众号 - 机器学习入门与实战(datanlp)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-02

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 用Python实现SVM多分类器

    支持向量机(SVM)——分类预测,包括多分类问题,核函数调参,不平衡数据问题,特征降维,网格搜索,管道机制,学习曲线,混淆矩阵,AUC曲线等

    大数据技术与机器学习
  • 基于依存句法分析的关键短语抽取算法实战

    由于最近在做一些无监督的关键词短语(实体)抽取工作,其实最大的背景还是没有标注好的实体识别训练数据;所以想到采用无监督的关键短语抽取算法折中去抽取一些实体,于是...

    大数据技术与机器学习
  • 决策树算法:ID3,C4.5,CART

    其实用一下图片能更好的理解LR模型和决策树模型算法的根本区别,我们可以思考一下一个决策问题:是否去相亲,一个女孩的母亲要给这个女海介绍对象。

    大数据技术与机器学习
  • 【分类战车SVM】第一话:开题话

    分类战车SVM (第一话:开题话) 大家好,今天开始给大家介绍机器学习世界的一种新武器——支持向量机,代号为SVM。 (1)支持向量机的出身:新贵家族“模式识别...

    数说君
  • 【分类战车SVM】第一话:开题话

    分类战车SVM (第一话:开题话) ---- 开题诗: KKT条件, 像绵延起伏的万水千山 隔断了我的视线, 却隔不断我对远方的期盼 少年傲然,曾经,要追寻生命...

    数说君
  • 机器学习|支持向量机参数求解

    01 — 支持向量机 支持向量机的简称为SVM,能在已知样本点很少情况下,获得很好的分类效果。 02 — SVM分类两个点 已知两个样本点,如果用SVM模型,决...

    double
  • 中国台湾大学林轩田机器学习技法课程学习笔记2 -- Dual Support Vector Machine

    上节课我们主要介绍了线性支持向量机(Linear Support Vector Machine)。Linear SVM的目标是找出最“胖”的分割线进行正负类的分...

    红色石头
  • BAT面试题1:请简要介绍下SVM

    接下来,每天推送1道BAT的面试题,一般问到的这些知识点都是很重要的,所以知道的呢就再复习一下,不知道的赶紧弥补。日积月累,你会在不知不觉中就已入机器学习的大门...

    double
  • 支持向量机学习笔记:数学过程及经典Tutorial

    http://blog.csdn.net/linj_m/article/details/18322149   ( SVM系列 )

    bear_fish
  • 学习SVM(五)理解线性SVM的松弛因子

    学习SVM(一) SVM模型训练与分类的OpenCV实现 学习SVM(二) 如何理解支持向量机的最大分类间隔 学习SVM(三)理解SVM中的对偶问题 ...

    chaibubble

扫码关注云+社区

领取腾讯云代金券

,,