机器学习算法系列(4)支持向量机(一)

上个学期忙着写论文,博客因此而有一段时间没有打理。看看自己的博客,距离机器学习算法系列的上一篇文章已经两个多月过去了,说来实在惭愧。这篇文章主要讲支持向量机的公式推导,因为许多“面经”都有提到面试官会考应聘者的公式推导,SVM 的尤其频繁。其实推导的过程比较好理解,主要的方法是拉格朗日对偶问题的优化,难一点的地方在于对 KKT 条件、SMO 算法的理解。看李航老师的《统计学习方法》的时候,密密麻麻的字母下标还是伤了不少神,不过只要有耐心,理解了之后便有“柳暗花明”的感觉。废话少说,开始推导!

1. 线性可分支持向量机原始问题

支持向量机(Support vector machine, SVM)是一种分类模型,它的任务是在特征空间上找到正确划分数据集的间隔(gap),并且能使几何间隔最大的分离超平面,简而言之,就是要找到一个平面,能够将空间中的点隔开!如果我们定义超平面可以通过线性方程:$w^Tx+b=0$ 来表示,将其记为 $(w,b)$。那么空间中任意一点 $x$ 到该超平面 $(w,b)$ 的距离可以表示为

\begin{equation}
r=\frac{|w^Tx+b|}{||w||}
\end{equation}

那么如何找到使得间隔最大的分离超平面呢?我们先从最简单的情形开始分析,假设超平面可以将数据集 100% 正确分类,若 $w^Tx_i+b>0$,有 $y_i=+1$,若 $w^Tx_i+b<0$,有 $y_i=-1$,令

\begin{equation}
\left{
\begin{array}{c}
w^Tx_i+b\ge+1, y_i=+1; \
w^Tx_i+b\le-1, y_i=-1.
\end{array}
\right.
\end{equation}

支持向量与间隔

2. 原始问题转化为对偶问题

如果我们将可以容忍的间隔设为1,也就是要求距离该平面 $(w,b)$ 正负距离为1的空间内没有一个异常点(outlier)存在,那么寻找最大分离的超平面就转化为如下的约束最优化问题:

\begin{equation}
\underset{w,b}{max}\ \frac{2}{||w||} \
s.t.\ y_i(w^Tx_i+b)\ge1,\ i=1,2,…,m.
\end{equation}

如何求解这个最优化问题呢?

(1)构建拉格朗日函数

该问题的拉格朗日函数可以等价写为(求$\frac{2}{||w||}$的最大值等价于求$\frac{1}{2}{||w||}^2$最小值)

\begin{equation}
L(w,b,\alpha)=\frac{1}{2}{||w||}^2-\sum_{i=1}^m{\alpha_i(1-y_i(w^Tx_i+b))} \label{lagrangefunction}
\end{equation}

这是一个凸二次规划问题,通过拉格朗日乘子法可得到其对偶问题。应用拉格朗日对偶性,原始问题$(w,b)$的对偶问题$(\alpha)$是极大极小问题:

分别令拉格朗日函数对$w$和$b$的偏导数为零可得

\begin{equation}
w=\sum_{i=1}^m\alpha_iy_ix_i
\end{equation}

\begin{equation}
0=\sum_{i=1}^m\alpha_iy_i
\end{equation}

然后将上述两个式子带入拉格朗日函数$\eqref{lagrangefunction}$即可将消去$w$和$b$
\begin{equation}
\begin{aligned}
L(w,b,\alpha)&=\frac{1}{2}\sum{i=1}^{N}\sum{j=1}^{N}\alphai\alpha_jy_iy_j(x_i·x_j)-\sum{i=1}^{N}\alphaiy_i((\sum{j=1}^{N}\alphajy_jx_j)x_i+b)+\sum{i=1}^{N}\alphai\
&=\frac{1}{2}\sum
{i=1}^{N}\sum{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i·x_j)+\sum{i=1}^{N}\alpha_i
\end{aligned}
\end{equation}
然后就得到了原约束问题的对偶问题,即求拉格朗日函数$L(w,b,\alpha)$对$\alpha$的极大

\begin{equation}
\underset{\alpha}{max}\ \sum{i=1}^m\alpha_i+\frac{1}{2}\sum{i=1}^m\sum{j=1}^m\alpha_i\alpha_jy_iy_j(x_i·x_j)\
s.t.\ \sum
{i=1}^{N}\alpha_iy_i=0\
\alpha_i\ge0,\ i=1,2,…,N
\end{equation}

故原始问题转化成为了求解对偶问题,为什么要这样做呢?这样做的优点是对偶问题需要求解的参数数量下降,原来需要考虑两个参数 $(w,b)$ ,现在只需要关注 $\alpha$ 便可以了,往往更容易求解。然后可以引入核函数,进而推广到非线性分类问题。设$\alpha^*$是对偶问题的最优化解,那么

\begin{equation}
w^=\sum_{i=1}^m{\alpha_i}^yix_i\
b^*=y_j-\sum
{i=1}^{N}{\alpha_i}^*y_i(x_i·x_j)
\end{equation}

求得了$w^$,$b^$,也就得到了我们需要的分离超平面。

当然这篇文章主要针对的是线性可分问题,那么线性不可分问题以及对偶问题的求解又怎么解决呢?后面的文章将会继续解释。

推荐阅读

  • 周志华.机器学习[M].2016年1月第一版.清华大学出版社.2016

  • 李航.统计学习方法[M].2012年3月第1版.清华大学出版社.2015

继续阅读机器学习算法系列笔记

觉得还不错?赞助一下~
0%