机器学习基础-SVM与感知机

参考《统计学习方法》李航等

SVM定义

SVM(Support Vector Machine，支持向量机)，是一种用来进行二分类的机器有监督的学习方法，是定义在特征空间上的间隔最大的线性分类器。

hard margin maximization 硬间隔最大化，当数据线性可分，学习一个线性可分支持向量机

soft margin maximization 软间隔最大化，当数据近似线性可分，学习一个线性支持向量机

kernel trick 核方法，当数据线性不可分，学习非线性支持向量机（核函数将输入从输入空间映射到特征空间得到的特征向量之间的内积，隐式地在高维特征空间中学习线性支持向量机）

给定一个训练样本集 $D=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m) \}, y_i \in \{ -1,+1 \}$ ,分类学习的基本想法就是基于训练集D在样本空间中找到一个划分超平面将不同样本分开。处于两类样本最中间的划分超平面对样本局部扰动的容忍性最好。即当对分类边界处的样本进行扰动时，更不容易产生分类错误。此时我们需要找到最大间隔。如下图

红色实线代表划分超平面，虚线表示决策边界，边界上的样本称为支持向量

则此时可设划分超平面可用线性方程

$\omega^Tx+b = 0$

表示，此时 $\omega$ 为法向量，决定超平面的方向， $b$ 为位移项，决定超平面与原点的距离。

分类决策函数为 $f(x)=sign(\omega^Tx+b)$

此时在超平面确定的情况下， $\vert\omega^Tx_i+b\vert$ 可相对的表示点 $x_i$ 距离超平面的远近，同时 $\omega^Tx_i+b$ 与类标记 $y_i$ 符号是否一致能够表示分类是否正确，所以可用 $y_i(\omega^Tx_i+b)$ 来表示分类的正确性和确信度，也叫函数间隔(functional margin)

则函数间隔为

$\hat\gamma_i=y_i(\omega^Tx_i+b)$

此时由于成比例改变 $\omega$ 和 $b$ 超平面不变但函数间隔会改变，于是我们对法向量加些约束，如规范化， $\|\omega\|=1$ ,使得间隔确定。 $\|\omega\|$ 为L2范数。

则此时要求 $\hat\gamma=\min_{i=1,2,...,N} \hat\gamma_i$ 即 $y_i(\omega^Tx_i+b)\geq \hat\gamma$

空间中任意样本点到超平面的距离为

$margin = \frac{\vert\omega^Tx+b\vert }{\|\omega\| }$ (由点到直线距离可得)

由于 $y_i(\omega^Tx_i+b)\geq 0$ 当分类正确时成立，margin可转化为

$margin = \frac{y_i(\omega^Tx_i+b) }{\|\omega\| }$

则我们需要最优化一个如下的问题：

$\left\{\begin{aligned}\max_{\omega,b}&\ margin \\s.t. &\ y_i(\omega^Tx_i+b)\geq \hat{\gamma}, (i=1,2,...,N)\end{aligned}\right.$

由上可知 $margin = \frac{\hat\gamma }{\|\omega\| }$ 则，可化为

$\left\{\begin{aligned}\max_{\omega,b}&\ \frac{\hat\gamma }{\|\omega\| } \\s.t. &\ y_i(\omega^Tx_i+b)\geq \hat{\gamma}, (i=1,2,...,N)\end{aligned}\right.$