简介

支持向量机(Support Vector Machine,SVM),是一种二分类模型,它是定义在特征空间上的间隔最大的线性分类器。目的是找到一个超平面,可以正确的将数据分类。

与其他线性分类器的区别是,支持向量机除了找到分界面之外,还需要保证间隔最大。所以该分界面是唯一的,也保证了一定的泛化能力。像感知机和逻辑回归,他们的分界面并不唯一。

支持向量机还引入了核函数的概念,让其在线性不可分的数据集上,可以通过核函数将特征映射到更高维甚至无穷维数空间上,达到可分的目的。

类型

根据数据的不同可以分为三种形式:线性可分 SVM,线性 SVM,非线性 SVM。

线性可分支持向量机

线性可分 SVM,也叫做硬间隔 SVM,处理的数据是线性可分的,通过硬间隔最大化来学习一个线性可分的模型。

线性支持向量机

线性 SVM,也叫做软间隔 SVM,当数据近似线性可分时,通过引入松弛因子,软间隔最大化学习一个线性可分的模型。

非线性支持向量机

当数据线性不可分时,通过引入核函数将数据映射到高维空间后,学习得到一个非线性支持向量机。

基本概念

  • 线性可分:在二维空间上,两类点被一条直线完全分开叫做线性可分。

  • 超平面:多维空间上,两类点被超平面 $wx+b=0 $ 分开。

  • 支持向量:样本中离超平面最近的点叫做支持向量。

  • 决策函数:$f(x)=sign(wx+b)$.

  • 决策边界:$wx+b = \pm1$.

  • 几何间隔:${2\over||w||}$.

  • 函数间隔:$y\cdot (wx+b)$.

原理

支持向量机是为了找到一个间隔最大的分类超平面,从而达到将不同的两类数据点分开,并且因为间隔最大化,所以有更好的泛化容错能力。那么如何找到这个间隔最大的超平面呢?

首先,既然要一个间隔最大的超平面,那么数据点到该平面的距离应该尽可能的要大。在二维空间上点到直线公式为

$d = {|Ax+By+C|\over \sqrt{A^2+B^2}}$

而多维空间上的点到平面距离公式为

$r = {|wx+b| \over ||w||},其中||w|| = \sqrt{w^2_1+\dots+w_n^2}$

目标函数

要找到间隔最大的超平面,也就是要找到满足 $y(wx+b)\geq 1$ 约束条件的参数 $w$ 和 $b$,使得 ${2\over ||w||}$ 最大。即:

$max \ {2\over ||w|| } \ s.t. y_i(w^Tx_i+b) \geq 1, i=1,2 \dots m.$

显然为了最大化间隔,仅需最小化 ||w||,所以原式等价于最小化 $||w||^2$,所以可以重写为:

$min_{w,b} \ {1\over 2}||w||^2 \ s.t. \ y_i(w^Tx_i+b)-1 \geq 0 , i=1,2,\dots m.$

其中目标函数和约束函数都是连续可微的凸函数,并且目标函数是二次函数,约束函数是仿射函数,所以该约束问题是一个凸二次规划问题。