机器学习(15)之支持向量机原理(一)线性支持向量机

关键字全网搜索最新排名

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

【机器学习】:排名第二

【Python】:排名第三

【算法】:排名第四

前言

支持向量机(Support Vecor Machine,以下简称SVM)虽然诞生只有短短的二十多年,但是自一诞生便由于它良好的分类性能席卷了机器学习领域,并牢牢压制了神经网络领域好多年。如果不考虑集成学习的算法,不考虑特定的训练数据集,在分类算法中的表现SVM说是排第一估计是没有什么异议的。

SVM是一个二元分类算法,线性分类和非线性分类都支持。经过演进,现在也可以支持多元分类,同时经过扩展,也能应用于回归问题。本篇的重点是SVM用于线性分类时模型和损失函数优化的一个总结。

回顾感知机模型

在(机器学习(7)之感知机python实现)中,讲到了感知机的分类原理,感知机的模型就是尝试找到一条直线,能够把二元数据隔离开。放到三维空间或者更高维的空间,感知机的模型就是尝试找到一个超平面,能够把所有的二元类别隔离开。对于这个分离的超平面,我们定义为 wTx+b=0,如下图。在超平面 wTx+b=0 上方的我们定义为y=1,在超平面 wTx+b=0下方的我们定义为y=−1。可以看出满足这个条件的超平面并不止一个。那么我们可能会尝试思考,这么多的可以分类的超平面,哪个是最好的呢?或者说哪个是泛化能力最强的呢?

感知机模型的损失函数优化,它的思想是让所有误分类的点(定义为M)到超平面的距离和最小,即最小化下式:

当和w和b成比例的增加,比如,当分子的和w和b扩大N倍时,分母的L2范数也会扩大N倍。也就是说,分子和分母有固定的倍数关系。那么我们可以固定分子或者分母为1,然后求另一个即分子自己或者分母的倒数的最小化作为损失函数,这样可以简化我们的损失函数。在感知机模型中,我们采用的是保留分子,固定分母||w||2=1,即最终感知机模型的损失函数为:

如果我们不是固定分母,改为固定分子,作为分类模型有没有改进呢?

函数间隔与几何间隔

在正式介绍SVM的模型和损失函数之前,还需要先了解下函数间隔和几何间隔的知识。

在分离超平面固定为wTx+b=0的时候,|wTx+b|表示点x到超平面的距离。通过观察wTx+b和y是否同号,我们判断分类是否正确,这些知识我们在感知机模型里都有讲到。这里我们引入函数间隔的概念,定义函数间隔γ′为:

它就是感知机模型里面的误分类点到超平面距离的分子。对于训练集中m个样本点对应的m个函数间隔的最小值,就是整个训练集的函数间隔。

函数间隔并不能正常反应点到超平面的距离,在感知机模型里我们也提到,当分子成比例的增长时,分母也是成倍增长。为了统一度量,我们需要对法向量w加上约束条件,这样我们就得到了几何间隔γ,定义为:

支持向量

在感知机模型中,我们可以找到多个可以分类的超平面将数据分开,并且优化时希望所有的点都离超平面远。但是实际上离超平面很远的点已经被正确分类,我们让它离超平面更远并没有意义。反而我们最关心是那些离超平面很近的点,这些点很容易被误分类。如果我们可以让离超平面比较近的点尽可能的远离超平面,那么我们的分类效果会好有一些。SVM的思想起源正起于此。

如下图所示,分离超平面为wTx+b=0,如果所有的样本不光可以被超平面分开,还和超平面保持一定的函数距离,那么这样的分类超平面是比感知机的分类超平面优的。可以证明,这样的超平面只有一个。和超平面平行的保持一定的函数距离的这两个超平面对应的向量,我们定义为支持向量,如下图虚线所示。

SVM模型目标函数与优化

SVM的模型是让所有点到超平面的距离大于一定的距离,也就是所有的分类点要在各自类别的支持向量两边。用数学式子表示为:

一般我们都取函数间隔γ′为1,这样我们的优化函数定义为:

也就是说,我们要在约束条件yi(wTxi+b)≥1(i=1,2,...m)下,最大化1)||w||2。可以看出,这个感知机的优化方式不同,感知机是固定分母优化分子,而SVM是固定分子优化分母,同时加上了支持向量的限制。由于1||w||2的最大化等同于12||w||22的最小化。这样SVM的优化函数等价于:

由于目标函数12||w||22是凸函数,同时约束条件不等式是仿射的,根据凸优化理论,我们可以通过拉格朗日函数将我们的优化目标转化为无约束的优化函数,这和(机器学习(13)之最大熵模型详解)中讲到了目标函数的优化方法一样。具体的,优化函数转化为:

这个优化函数满足KKT条件,也就是说,我们可以通过拉格朗日对偶将我们的优化问题转化为等价的对偶问题来求解。我们可以先求优化函数对于和w和b的极小值。接着再求拉格朗日乘子α的极大值。

首先我们来求和w和b的极小值,即minL(w,b,α)。这个极值我们可以通过对和w和b分别求偏导数得到:

从上两式子可以看出,我们已经求得了和w和α的关系,只要我们后面接着能够求出优化函数极大化对应的α,就可以求出我们的w了,至于b,由于上两式已经没有b,所以最后的b可以有多个。既然我们已经求出和w和α的关系,就可以带入优化函数L(w,b,α)消去w了。我们定义:

现在我们来看将w替换为α的表达式以后的优化函数ψ(α)的表达式:

对ψ(α)求极大化的数学表达式如下:

可以去掉负号,即为等价的极小化问题如下:

只要我们可以求出上式极小化时对应的α向量就可以求出和w和b了。在这里,我们假设通过SMO算法,我们得到了对应的α的值α∗。可以求出对应的w的值:

求b则稍微麻烦一点。注意到,对于任意支持向量(xx,ys),都有

小结

线性可分SVM的学习方法对于非线性的数据集是没有办法使用的, 有时候不能线性可分的原因是线性数据集里面多了少量的异常点,由于这些异常点导致了数据集不能线性可分, 那么怎么可以处理这些异常点使数据集依然可以用线性可分的思想呢? 我们在下一节的线性SVM的软间隔最大化里继续讲。

参考:

1. 周志华《机器学习》

2. 博客园:作者(刘建平)http://www.cnblogs.com/pinard/p/6097604.html

3. 李航 《统计学习方法》

4. 《机器学习实战》

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

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专知

神经网络编程 - 前向传播和后向传播(附完整代码)

【导读】本文的目的是深入分析深层神经网络,剖析神经网络的结构,并在此基础上解释重要概念,具体分为两部分:神经网络编程和应用。在神经网络编程部分,讲解了前向传播和...

31970
来自专栏机器之心

教程 | 从头开始:用Python实现带随机梯度下降的Logistic回归

选自machine learning mastery 机器之心编译 参与:Jane W、Panda logistic 回归是一种著名的二元分类问题的线性分类算...

720100
来自专栏机器学习之旅

理论:决策树及衍射指标

特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵H(D)与特征A给定条件下的经验条件熵H(D|A)之差

8740
来自专栏WD学习记录

机器学习 学习笔记(23) 卷积网络

卷积网络(convolutional network),也叫做卷积神经网络(convolutional neural network,CNN),是一种专门用来处...

29420
来自专栏张俊红

一些算法的小结

总第54篇 算法目的:分类、预测 算法分类:监督型、非监督型 算法的核心:你有什么数据、你要解决什么问题 ---- 01|线性回归: 1、什么是回归 回归,指...

34640
来自专栏自学笔记

Neural Network

重新回顾一下一开始学的PLA,preceptron learning Algorithm。PLA适用于二维及高维的线性可分的情况,如果是非线性可分的数据,如果使...

25420
来自专栏杨熹的专栏

TensorFlow-9-词的向量表示

今日资料: https://www.tensorflow.org/tutorials/word2vec 中文版: http://wiki.jikexuey...

40570
来自专栏yl 成长笔记

kera 学习-线性回归

园子里头看到了一些最基础的 keras 入门指导, 用一层网络,可以训练一个简单的线性回归模型。

15140
来自专栏机器学习与自然语言处理

Stanford机器学习笔记-8. 支持向量机(SVMs)概述

8. Support Vector Machines(SVMs) Content 8. Support Vector Machines(SVMs)   ...

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

从AlexNet剖析-卷积网络CNN的一般结构

作者:张旭 编辑:王抒伟 算了 想看多久看多久 零 参考目录: 一、卷积层 1.CNN中卷积层的作用 2.卷积层如何...

95350

扫码关注云+社区

领取腾讯云代金券