支持向量机(1)-概念及推导
之前一篇文章《Andrew机器学习课程笔记(3)—— K均值、SVM、PCA》有分析过SVM,但感觉不够系统,也没有算法落地
本篇及下一篇从“概念及推导”和“算法实现”两个方面讨论SVM
本篇包含:SVM基本概念、线性可分SVM、非线性可分SVM、带有松弛变量的SVM
概念
支持向量机(SVM)是一种二类分类模型,其基本目标是找到一个分类平面,使得两边的特征点与之距离(margin)最大。
图1-1. 二维空间线性SVM
图1-1中落在蓝色边界的样本称为支撑向量
对于非线性可分的情况,SVM通过引入核函数,将样本映射到高维空间实现分类。
SVM一直被认为是效果最好的现成可用的分类算法之一
线性可分SVM
目标函数推导
考虑线性分类器的超平面方程
使用sign的**函数
由此可以得到样本点到分类面的函数间隔(functional margin)
乘上y可以保证间隔的非负性
同时,由点面距离可以得到几何间隔(geometrical margin)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
几何间隔的推导
参考文章《支持向量机: Maximum Margin Classifier》的评论
令
等式(5)两边左乘
又因为
而
于是有
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
可以看到,几何间隔较函数间隔多了一个缩放因子
由此确定 SVM 的目标函数
为了计算方便,固定
目标函数求解
为了方便,将SVM目标函数(7)做等价变形
根据拉格朗日乘子法,(8)式可以变为求(9)式的极值
对
令各偏导为0,得
这里
事实上我们将式(11)中的
也就是说,对于新点
此外,非支持向量点对应的
非线性可分SVM
参考文章《支持向量机: Kernel》,考虑如图2-1所示的数据分布
图2-1. 两类数据无法用线性分类器分类
图1-2理想的分类面为
为了实现线性可分,可以将2维数据映射到5维:
于是有线性形式
因此对于非线性可分的情况,理论上首先将数据做适当升维即可(对比式(12))
但这样一来会遇到“维数爆炸”的问题(高斯核会将数据升到无穷维),导致计算量急剧升高
SVM核函数的做法是:在原始维度以某种函数做运算,确保与升维内积一个效果
常用的核函数:
-
多项式核
K(x1,x2)=(<x1,x2>+R)d 2 维度映射Rm−>Rm+d -
高斯核
K(x1,x2)=e−||x1−x2||22σ2 2 维度映射Rm−>∞ ,- 如果
σ 很大,高次特征的权重衰减的很快,近似于映射到一个低维空间 - 如果
σ 很小,则可以将任意数据映射为线性可分。但有可能出现过拟合问题 - 因此通过调节
σ ,高斯核具有相当高的灵活性。是使用最广泛的核函数之一
- 如果
-
线性核
K(x1,x2)=<x1,x2>
退化为线性SVM
带有松弛变量的SVM
由于不可避免的噪声,有些数据会偏离正常位置很远,给SVM分类平面带来很大影响(图3-1)
图3-1. 被黑圈包围的蓝点是异常点(outlier),需要被排除
如式(17)所示,引入一个松弛变量
参考
【1】Free Mind 支持向量机系列
【2】支持向量机(Support Vector Machines-SVM)算法笔记(一)-Python