机器学习基础-SVM

本系列是Machine Learning-Andrew Ng学习后整理的读书笔记。

本节主要介绍SVM部分知识,由于Ng介绍过为简单,本节整理自周志华《机器学习》对应章节。

最大化几何间隔

在样本空间存在许多个超平面,SVM的作用即找到所有超平面中“最好”的那个,通俗点讲即在正负样本“正中间”确定的那个平面。

141143467929408.jpg

在样本空间中,划分超平面可通过如下线性方程描述:
$$
\boldsymbol{w}^T\boldsymbol{x}+b=0
$$
其中,$\boldsymbol{w}=(w_1,w_2,\dots,w_n)^T$表示超平面法向量,b表示位移项。

任意点到超平面$(\boldsymbol{w},b)$的距离可写作$r=\frac{|w^Tx+b|}{|w|}$

若超平面$(\boldsymbol{w},b)$能将训练样本正确分类,即对$(x_i,y_i)$,若$y_i=1$,则$\boldsymbol{w}^Tx_i+b>0$;若$y_i=-1$,则$\boldsymbol{w}^Tx_i+b<0$。令
$$
\begin{cases}
\boldsymbol{w}^Tx_i+b\ge+1&y_i=+1;\
\boldsymbol{w}^Tx_i+b\le-1&y_i=-1;
\end{cases}
$$
如上图,距离超平面最近的样本点能使上诉不等式成立,这些点即为支持向量(support vector),两个异类支持向量到超平面的距离之和被称为间隔(margin)
$$
d=\frac{2}{|w|}
$$
为了找到最大间隔的超平面,即在满足上诉不等式的条件下,使得$d$最大,等效为
$$
\begin{align}
&\min_{w,b}\frac{1}{2}|w|^2\
&\text{s.t.}\;y_i(w^Tx_i+b)\ge1,&i=1,2,\dots,m
\end{align}\tag{1}
$$

对偶问题

对式$1$进行拉格朗日乘子法,得到对偶的拉格朗日函数
$$
L(\boldsymbol{w},b,\boldsymbol{\alpha})=\frac{1}{2}|\boldsymbol{w}|^2+\sum_{i=1}^{m}\alpha_i(1-y_i(\boldsymbol{w}^Tx_i+b)) \tag{2}
$$
令$L(\boldsymbol{w},b,\boldsymbol{\alpha})$对$\boldsymbol{w},b$求偏导并置为零,可得到
$$
\boldsymbol{w}=\sum_{i=1}^{m}\alpha_iy_ix_i\
0=\sum_{i=1}^{m}\alpha_iy_i
$$
将上式代入$2$可消去$w,b$,即可得到$1$对偶问题。
$$
\begin{align}
&L(\boldsymbol{w},b,\boldsymbol{\alpha})=\max_{\alpha}\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{i=j}^{m}\alpha_i\alpha_jy_iy_j\boldsymbol{x_i}^T\boldsymbol{x_j}\
&s.t.\quad
\begin{cases}
\sum_{i=1}^{m}\alpha_iy_i=0\
\alpha_i\ge0,&i=1,2,\dots,m
\end{cases}
\end{align}
$$

核函数

若样本在原始空间中不存在一个能正确划分类别的超平面,可将样本从原始空间映射到一个更高位的特征空间,使得样本在这个特征空间内线性可分,记这个映射为$\phi$,对应超平面可表示为$\boldsymbol{w}^T\phi(x)+b=0$。

image.png

由于高维空间下,直接计算$\phi(x_i)^T\phi(x_j)$较为困难,因此可以采用*核函数来封装该部分计算,即
$$
k(\boldsymbol{x_i},\boldsymbol{x_j})=\phi(x_i)^T\phi(x_j)
$$
image.png

高斯核

高斯核有两个主要参数$\mu,\sigma$,高斯核的形式为
$$
exp(-\frac{|x-\mu|^2}{2\sigma^2})
$$
其中,$\mu$控制核中心的位置,$\sigma$控制陡峭程度。

image.png

在SVM中,若采用高斯核,需要控制的参数只有$\sigma$。

  • $\sigma$越大,特征变化越平缓,会产生高偏差低方差(更易欠拟合);
  • $\sigma$越小,特征变化越陡峭,会产生低偏差高方差(更易过拟合);

软间隔

现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分,即便线性可分,也很难判定这个结果不是由于过拟合造成的。

缓解这个问题的一个方法是允许支持向量机在一些样本上出错,引入“软间隔”概念。允许某些样本不满足约束 $y_i(\boldsymbol{ω}^Tx_i+b)\ge1$,优化目标可写成
$$
\min_{w,b}\frac{1}{2}|\boldsymbol{w}|^2+C\sum_{i=1}^{m}l_{0/1}(y_i(\boldsymbol{ω}^Tx_i+b)-1) \tag{3}
$$
其中$l_{0/1}$是“0/1损失函数”
$$
l_{0/1}(z)=
\begin{cases}
1,&if\;z<0\
0,&otherwise
\end{cases}
$$
由于$l_{0/1}$非凸、非连续、数学性质不好,使得式$3$难以求解,因此人们用其他一些函数来代替它,称为“代替函数”。

image.png

SVM调参

在SVM中,需要调整的参数包括系数$C$,核函数选择,$\sigma$ (如果采用高斯核)。其中$C$可看做logestic regression中$\frac{1}{\lambda}$。因而,在调整$C$时

  • $C$越大,会产生低偏差高方差(更易过拟合),将会迫使所有样本均满足分类;
  • $C$越小,会产生高偏差低方差(更易欠拟合),允许一些样本不满足分类;

最后,在操作SVM,一般按照下述步骤。

image.png

本文标题:机器学习基础-SVM

文章作者:Lumo Wang

发布时间:2018年03月16日 - 14:03

最后更新:2019年04月17日 - 20:04

原始链接:https://luameows.github.io/2018/03/16/学习笔记-机器学习基础-svm/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

请我喝杯咖啡,我会继续熬夜的~