机器学习算法系列(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)\)是极大极小问题:

\[ max\ min\ L(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}\alpha_i\alpha_jy_iy_j(x_i·x_j)-\sum_{i=1}^{N}\alpha_iy_i((\sum_{j=1}^{N}\alpha_jy_jx_j)x_i+b)+\sum_{i=1}^{N}\alpha_i\\ &=\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}^*y_ix_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

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

觉得还不错?帮我赞助点域名费吧:)