机器学习算法系列(5)支持向量机(二)

先前的一篇文章我们介绍了线性可分问题的支持向量机方法,不过它的前提条件比较严苛,现实工程环境中一般不会有那么完美的数据集。但我们要求方法更具有适用性,如果碰到线性不可分问题,那就要寻求别的解决办法了。

1. 软间隔最大化

针对线性不可分的问题,硬间隔最大化的方法就不适用了,因为一旦间隔区域有异常点,软间隔的不等式约束不一定都成立。对于不能满足函数间隔条件的数据集,下面就来讲解一种软间隔最大化的方法。

所谓“软”,也就是将约束条件放松一点点,有些数据破坏了间隔条件是被容许的(不知道这也是不是一种防止过拟合的手段?),但是也不能太多。我们给约束条件加上一个松弛变量\(\xi_i\),放宽约束条件,这样硬间隔最大化里面要求的间隔强制为 1 的约束条件就变为:

\[y_i(wx_i+b)\ge1-\xi_i\]

同时,对松弛变量加上惩罚参数 \(C\gt0\),目标函数就变为

\[\frac{1}{2}{||w||}^2+C\sum_{i=1}^{N}\xi_i\]

所以线性不可分的支持向量机问题变为凸二次规划问题,我们暂且称为原始问题

\[\begin{equation}\begin{split} \underset{w,b,\xi}{min}\quad&\frac{1}{2}{||w||}^2+C\sum_{i=1}^{N}\xi_i \\\\ s.t.\quad&y_i(wx_i+b)\ge1-\xi_i, \quad\text{$i=1,2,...,N$}\\\\ &\xi_i\ge0,\quad\text{$i=1,2,...,N$}\label{origin} \end{split}\end{equation}\]

2. 转化为对偶问题

对凸二次规划问题,我们依然选择拉格朗日乘子法求解

(1)首先对原始问题构建拉格朗日函数,\(\alpha\)\(\mu\) 为拉格朗日乘数

\[\begin{equation} L(w,b,\xi,\alpha,\mu)=\frac{1}{2}{||w||}^2+C\sum_{i=1}^{N}\xi_i-\sum_{i=1}^{N}\alpha_iy_i(wx_i+b)-\sum_{i=1}^{N}\alpha_i\xi_i+\sum_{i=1}^{N}\alpha_i-\sum_{i=1}^{N}\mu_i{\xi}_i \label{lagrangefunction} \end{equation}\]

(2)极小化\(L(w,b,\alpha)\),分别对\(w,b,\xi\)求偏导并令其等于零

\[\begin{equation}\begin{split} &\frac{\partial L}{\partial w}=w-\sum_{i=1}^{N}\alpha_iy_ix_i=0 \\\\ &\frac{\partial L}{\partial b}=\sum_{i=1}^{N}\alpha_iy_i=0 \\\\ &\frac{\partial L}{\partial \xi}=C-\alpha_i-\mu_i=0 \end{split} \end{equation}\]

\[\begin{equation}\begin{split} &w=\sum_{i=1}^{N}\alpha_iy_ix_i\\\\ &\sum_{i=1}^{N}\alpha_iy_i=0\\\\ &C-\alpha_i-\mu_i=0 \end{split}\end{equation}\]

然后将上述三个式子带入拉格朗日函数\(\eqref{lagrangefunction}\)即可将消去\(w\)\(b\),即

\[L(w,b,\xi,\alpha,\mu)=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jx_ix_j+\sum_{i=1}^{N}\alpha_i\]

对偶问题是拉格朗日函数极大极小问题,求上式对\(\alpha\)的极大,即得对偶问题

\[\begin{equation}\begin{split} max\quad&-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jx_ix_j+\sum_{i=1}^{N}\alpha_i\\ s.t.\quad&\sum_{i=1}^{N}\alpha_iy_i=0\\ &C-\alpha_i-\mu_i=0\\ &\alpha_i\ge0,\mu_i\ge0,i=1,2,...,N \end{split}\end{equation}\]

看出来没有?当拉格朗日函数转化为其对偶问题的形式,令人激动的是优化问题神奇般地只剩下一个参数了!如果我们设\({\alpha_i}^*\)是对偶问题的一个解,那么原始问题\(w^*,b^*\)的解可由下式求得,接下来的任务只需要求解\(\alpha\)了,如下

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

3. 非线性支持向量机与核函数

针对非线性分类问题,我们一般使用非线性支持向量机的方法,其主要特点是核技巧(kernel trick)。核技巧的基本想法是通过非线性变换将输入空间(一般是欧式空间或离散集合)映射到另一个特征空间,简单一点理解就是函数变换。

\[\phi(x):x\to\mathcal{H}\] \[K(x,z)=\phi(x)\cdot\phi(z)\]

其中\(K(x,z)\)为核函数,\(\phi(x)\)为映射函数

因此,当核技巧应用于支持向量机中,对偶问题的目标函数中的内积\((x_i,x_j)\)便可以用核函数\(K(x,z)=\phi(x)\cdot\phi(z)\)来代替,故对偶问题的目标函数变为只有\(\alpha\)一个参数了:

\[w(\alpha)=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jK(x_i,x_j)+\sum_{i=1}^{N}\alpha_i\]

3.1 几种常见的核函数

  • 线性核
  • 多项式核
  • 高斯核(也称RBF核)
  • 拉普拉斯核
  • sigmoid核

小结

这篇文章介绍了软间隔方法和核函数,以及如何将原始问题转化为只有一个参数的对偶问题,至于如何求解 \({\alpha_i}\),在接下来的文章中,我们会学习一种专门对付求解\({\alpha_i}\)的SMO算法。

推荐阅读

  • 《机器学习 Machine Learning》 周志华
  • 《统计学习方法》李航 第七章
觉得还不错?帮我赞助点域名费吧:)