西瓜书笔记6 支持向量机

Posted on | In | Visitors:
Words count in article: 2.2k | Reading time ≈ 10
间隔与支持向量；对偶问题；软间隔与正则化；核函数；SMO算法；支持向量回归；核方法

西瓜书笔记6 支持向量机

间隔与支持向量

存在多个划分超平面将两类训练样本分开

在样本空间中，划分超平面可通过如下线性方程来描述

其中$\boldsymbol{\omega} = (\omega_1;\omega_2;…;\omega_d)$为法向量，决定了超平面的方向；b是位移项，决定了超平面与原点之间的距离。

样本空间中的任意点$x$到超平面$(\boldsymbol{\omega},b)$的距离：

假设超平面$(\boldsymbol{\omega},b)$能将训练样本正确分类，即对于样本$(\boldsymbol{x}_i,y_i)\in D$，若标签$y_i=+1$，则有$\boldsymbol{\omega}^{T}\boldsymbol{x}_i+b>0$；若$y_i=-1$，则有$\boldsymbol{\omega}^{T}\boldsymbol{x}_i+b<0$。

进一步可以令：

若超平面$(\boldsymbol{\omega}’,b’)$能将训练样本正确分类，则总存在缩放变换$\varsigma\boldsymbol{\omega}\mapsto\boldsymbol{\omega}’$和$\varsigma b\mapsto b’$使得上式成立。

距离超平面最近的几个样本点使上式等号成立，称之为“支持向量”。

两个异类支持向量到超平面的距离之和，称之为“间隔”

我们的目标就是在确保超平面能够正确分类的同时，最大化间隔：

等价于

这就是支持向量机(Support Vector Machine)的基本型。

对偶问题

上式是一个凸二次规划问题。对其使用拉格朗日乘子法可得到其“对偶问题”。

该问题的拉格朗日函数可写为

其中$\boldsymbol{\alpha}=(\alpha_1;\alpha_2;…;\alpha_m),\alpha_i\geq0$。

由于引入了拉格朗日乘子，我们的优化目标变为

转化成对偶问题，现在我们要解决的是

首先我们来求令$L(\boldsymbol{\omega},b,\boldsymbol{\alpha})$基于$\boldsymbol{\omega}$和b的最小值，即$\underset{\boldsymbol{w},b}{\min}L(\boldsymbol{\omega},b,\boldsymbol{\alpha})$。这个值，我们可以对$\boldsymbol{\omega}$和b分别求偏导数得到

将上式带入$L(\boldsymbol{\omega}, b,\boldsymbol{\alpha})$，可得

解出$\alpha$后，求出$\boldsymbol{\omega}$与b即可得到模型

软间隔与正则化

回顾一下硬间隔支持向量机，最大化的目标：

“软间隔”：允许支持向量机在一些样本上出错，即允许某些样本不满足约束$y_i(\boldsymbol{\omega}^T\boldsymbol{x}_i+b)\geq1$。

对每个样本$(\boldsymbol{x}_i,y_i)$引入一个松弛变量$\xi_i\geq0$，使函数间隔加上松弛变量大于等于1，即

软间隔最大化

对比硬间隔最大化，可以看到我们对样本到超平面的函数距离的要求放松了，之前是一定要大于等于1，现在只需要加上一个大于等于0的松弛变量能大于等于1就可以了。当然，松弛变量不能白加，这是有成本的，每一个松弛变量$\xi_i$, 对应了一个损失$\xi_i$，这个就得到了我们的软间隔最大化的SVM学习条件如下

这里，C>0为惩罚参数，可以理解为我们一般回归和分类问题正则化时候的参数。C越大，对误分类的惩罚越大，C越小，对误分类的惩罚越小。

最大化函数的优化

首先将软间隔最大化的约束问题用拉格朗日函数转化为无约束问题

其中$\alpha_i\geq0,\mu_i\geq0$是拉格朗日乘子

现在要求得是

同样转换成等价的对偶问题：

首先求$\underset{\boldsymbol{\omega},b,\boldsymbol{\xi}}{\min}L(\boldsymbol{\omega},b,\boldsymbol{\alpha}, \boldsymbol{\xi},\boldsymbol{\mu})$，可以通过求偏导数求得

带入对偶问题式可得

核函数

有些训练样本是线性不可分的，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。如果原始空间是有限维，即属性数有限，那么一定存在一个高维特征空间使样本可分。（至于为什么，以后再证，参见12章？）

令$\phi(\boldsymbol{x})$表示将$\boldsymbol{x}$映射后的特征向量。在特征空间中划分超平面对应的模型可表示为

SVM的优化目标函数变为

上式中涉及到计算$\phi(\boldsymbol{x}_i)^T\phi(\boldsymbol{x}_j)$，这是样本映射后的内积。由于映射后的特征空间维数可能很高，计算量太大；甚至是无穷维，无法计算。这时候，就需要我们的核函数了。设想有这么一个函数

核函数在低维上进行计算，而将实质上的分类效果（利用了内积）表现在了高维上，这样避免了直接在高维空间中的复杂计算，真正解决了SVM的线性不可分问题。

有哪些核函数呢

定理（核函数）

令$\chi$为输入空间，$\kappa(\cdot,\cdot)$是定义在$\chi\times\chi$上的对称函数，则$\kappa$是核函数当且仅当对于任意数据$D=\left \{\boldsymbol{x}_1,\boldsymbol{x}_2,…,\boldsymbol{x}_m\right \}$，“核矩阵”$\boldsymbol{K}$总是半正定的。

定理表明，只要是一个对称函数对应的核矩阵半正定，它就能作为核函数使用。

常用的几种核函数

名称 表达式 参数
线性核 $\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)=\boldsymbol{x}_i^T\boldsymbol{x}_j$
多项式核 $\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)=(\boldsymbol{x}_i^T\boldsymbol{x}_j)^d$` `$d\geq1$为多项式的次数
高斯核(RBF核) $\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)=\exp(-\frac{\boldsymbol{x}_i-\boldsymbol{x}_j^2}{2\sigma^2})$ $\sigma>0$为高斯核带宽
拉普拉斯核 $\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)=\exp(-\frac{\boldsymbol{x}_i-\boldsymbol{x}_j}{\sigma})$ $\sigma>0$
Sigmoid核 $\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)=\tanh(\beta\boldsymbol{x}_i^T\boldsymbol{x}_j+\theta)$ $\beta>0,\theta>0$

此外，还可通过函数组合得到

  • 若$\kappa_1$和$\kappa_2$为核函数，则对于任意正数$\gamma_1$、$\gamma_2$，其线性组合也是核函数
  • 若$\kappa_1$和$\kappa_2$为核函数，则核函数的直积也是核函数（这里不太懂，直积不是集合运算吗？）
  • 若$\kappa_1$为核函数，则对于任意函数$g(\boldsymbol{x})$，$\kappa$也是核函数

SMO算法*

优化目标

目标函数：

==解要满足的KKT条件的对偶互补条件为==

即

由于$\boldsymbol{\omega}=\sum_{i=1}^{m}\alpha_i^y_i\phi(\boldsymbol{x}_i)$。$f(\boldsymbol{x})=\sum_{i=1}^{m}\alpha_i^y_iK(\boldsymbol{x},\boldsymbol{x_i})+b$,则有

SMO基本思想

上面的优化式子比较复杂。是一个二次规划问题，可以使用通用的二次规划算法来求解。优化时间正比于训练样本数m，所以直接优化很难。

SMO算法，采用了一种启发式方法。它每次只选择两个变量，其他变量视为常数（固定）。由于存在约束$\sum_{i=1}^{m}\alpha_iy_i=0$，假如将$\alpha_3,\alpha4,…,\alpha_m$固定，那么$\alpha_1,\alpha_2$之间的关系也确定了。

SMO不断执行如下两个步骤直至收敛

  • 选取一对需要更新的$\alpha_i$和$\alpha_j$
  • 固定$\alpha_i$和$\alpha_j$以外的参数，求解目标函数式获得更新后的$\alpha_i$和$\alpha_j$

SMO算法细节

两个变量的选择

不妨记$\alpha_1,\alpha_2$为选择的两个变量

1.第一个变量的选择

SMO算法称选择第一个变量为外层循环，选择在训练集中违反KKT条件程度最大的样本点。对于每个样本点，要满足的KKT条件

一般来说，先选择违反$0<\alpha_i^<C\Rightarrow y_if(\boldsymbol{x}_i)=1$的点。如果这些*支持向量都满足KKT条件，在选择其他的

2.第二个变量的选择

SMO算法称，选择第二个变量为内层循环，假设外层循环已经找到了$\alpha_1$，第二个变量的选择标准是选择与其样本间隔最大的点。
为了方便表示，我们定义

对于E的理解有待更新

即第二个变量的选择标准是让$|E_1-E_2|$有足够大的变化。由于$\alpha_1$定了的时候$E_1$也定了，所以想要$|E_1-E_2|$最大，只需要在$E_1$为正时，选择最小的$E_i$作为$E_2$，$E_1$为负时，选择最大的$E_i$作为$E_2$，可以将所有的$E_i$保存下来加快迭代。

==如果内循环找到的点不能让目标函数有足够的下降，可以采用遍历支持向量点来做$\alpha_2$，直至目标函数有足够的下降，如果所有的支持向量做$\alpha_2$都不能让目标函数有足够的下降，可以跳出循环，重新选择$\alpha_1$。==

两个变量的更新

定义

因为$\alpha_3,\alpha_4,…,\alpha_m$都变成了常量，所以我们的目标优化函数变为

现在的问题是，求解上面含有这两个变量的目标优化问题。

首先分析约束条件，所有的$\alpha_1,\alpha_1$都要满足约束条件，然后在约束条件下求最小。

  1. 要满足的约束条件

已知约束条件：

若$y_1=y_2$,

若$y_1\neq y_2$

分别用L和H表示$\alpha_2$的上下界约束，则$L\leq\alpha_2\leq H$。也就是说，我们通过求导得到$\alpha_{2}^{new,unc}$,则最终的$\alpha_2^{new}$应该为

  1. 约束条件下的最优值

为了简化目标优化函数，我们令

这样我们的目标优化函数进一步简化为

由于$\alpha_1y_1+\alpha_2y_2=\zeta$，可以得到$\alpha_1$用$\alpha_2$表达的式子为

将上式代入我们的目标优化函数，就可以消除$\alpha_1$，得到仅包含$\alpha_2$的式子

对W求导数，得到$\alpha_2^{new,unc}$

整理上式得

将$\zeta=\alpha_1y_1+\alpha_2y_2$带入上式得

最终得到$\alpha_2^{new,unc}$的表达式

求得$\alpha_2^{new}$后，利用$\alpha_2^{new}$与$\alpha_1^{new}$的线性关系，也可以得到$\alpha_1^{new}$

计算阈值b和差值$E_i$

SMO算法总结

输入m个样本$(\boldsymbol{x}_1,y_1),(\boldsymbol{x}_2,y_2),...,(\boldsymbol{x}_m,y_m)$，其中$x_i$为n维特征向量，y为二元输出，值为1或-1。

  1. 取初值$\boldsymbol{\alpha}^0=0,k=0$

  2. 按上述方法选择$\alpha_1^k$和$\alpha_2^k$，求出新的$\alpha_2^{new,unc}$

    1
    \alpha_2^{new,unc}=\alpha_2^k+\frac{y_2(E_1-E_2)}{K_{11}+K_{22}-2K_{12}}

  3. 按照下式求出$\alpha_2^{k+1}$

    1
    2
    3
    4
    5
    \alpha_2^{k+1}=\left\{\begin{matrix}
    H&\alpha_2^{new,unc}>H\\ 
    \alpha_2^{new,unc}&L\leq\alpha_2^{new,unc}\leq H\\ 
    L&\alpha_2^{new,unc}<L
    \end{matrix}\right.

  4. 利用$\alpha_2^{k+1}$和$\alpha_1^{k+1}$的线性关系求出$\alpha_1^{k+1}$

  5. 按上述方法计算$b^{k+1}$和$E_i$

  6. 在精度e范围内检查是否满足如下的终止条件

    1
    2
    3
    4
    5
    6
    7
    8
    9
    \sum_{i=1}^m\alpha_iy_i=0

    0\leq\alpha_i\leq C\ i=1,2,...,m

    \alpha_i^{k+1}=0\Rightarrow y_if(\boldsymbol{x}_i)\geq1

    0<\alpha_i^{k+1}<C\Rightarrow y_if(\boldsymbol{x}_i)=1

    \alpha_i^{k+1}=C\Rightarrow y_if(\boldsymbol{x}_i)\leq1

  7. 如满足则结束，返回$\boldsymbol{\alpha}^{k+1}$，否则转到步骤2

支持向量机回归

考虑一个回归问题，给定训练样本$D=\left\{(\boldsymbol{x}_1,y_1),(\boldsymbol{x}_2,y_2),...,(\boldsymbol{x}_m,y_m)\right\},y_i\epsilon\mathbb{R}$，希望学得一个形如下式的回归模型，使得$f(\boldsymbol{x})$与$y$尽可能接近，$\boldsymbol{\omega}$和$b$是待确定的模型参数。

1
f(\boldsymbol{x})=\boldsymbol{\omega}^T\boldsymbol{x}+b
  • 传统回归模型：通常直接基于模型输出$f(\boldsymbol{x})$与真是输出$y$之间的差别来计算损失，当且仅当$f(\boldsymbol{x})$与$y$完全相同时，损失才为零。
  • 支持向量回归：可以容忍$f(\boldsymbol{x})$与$y$之间最多有$\epsilon$的偏差，即仅当$f(\boldsymbol{x})$与$y$之间的差别绝对值大约$\epsilon$时才计算损失。

SVR问题可形式化为

1
\underset{\boldsymbol{\omega},b}{\min}\frac{1}{2}||\boldsymbol{\omega}||^2+C\sum_{i=1}^{m}\ell_{\epsilon}(f(\boldsymbol{x}_i)-y_i)

其中C为正则化常数，$\ell_{\epsilon}$是$\epsilon-$不敏感损失函数

1
2
3
4
\ell_{\epsilon}(z)=\left\{\begin{matrix}
0,&if|z|\leq\epsilon\\ 
|z|-\epsilon,&othervise
\end{matrix}\right.

引入松弛变量$\xi_i$和$\widehat{\xi}_i$（间隔带两侧的松弛程度可有所不同，所以有两个松弛变量）

1
2
3
4
5
\underset{\boldsymbol{\omega},b,\xi_i,\widehat{\xi}_i}{\min}\frac{1}{2}||\boldsymbol{\omega}||^2+C\sum_{i=1}^m(\xi_i,\widehat{\xi}_i)

s.t.\ -\epsilon-\widehat{\xi}_i\leq f(\boldsymbol{x}_i)-y_i\leq\epsilon+\xi_i

\xi_i\geq0,\widehat{\xi}_i\geq0,i=1,2,...,m

目标函数对偶形式

引入拉格朗日乘子$\mu_i\geq0,\hat{\mu}_i\geq0,\alpha_i\geq0,\hat{\alpha}_i\geq0$，由拉格朗日乘子法可得拉格朗日函数

1
2
3
4
5
L(\boldsymbol{\omega},b,\boldsymbol{\alpha},\boldsymbol{\hat{\alpha}},\boldsymbol{\xi},\boldsymbol{\hat{\xi}},\boldsymbol{\mu},\boldsymbol{\hat{\mu}})

=\frac{1}{2}||\boldsymbol{\omega}||^2+C\sum_{i=1}^m(\xi_i+\hat{\xi}_i)-\sum_{i=1}^m\mu_i\xi_i-\sum_{i=1}^m\hat{\mu}_i\hat{\xi}_i

+\sum_{i=1}^m\alpha_i(f(\boldsymbol{x}_i-y_i-\epsilon-\xi_i))+\sum_{i=1}^m\hat{\alpha}_i(y_i-f(\boldsymbol{x}_i)-\epsilon-\hat{\xi}_i)

我们的优化目标是

1
\underset{\boldsymbol{\omega},b,\boldsymbol{\xi},\boldsymbol{\hat{\xi}}}{\min}\underset{\boldsymbol{\mu},\boldsymbol{\hat{\mu}},\boldsymbol{\alpha},\boldsymbol{\hat{\alpha}}}{\max}L(\boldsymbol{\omega},b,\boldsymbol{\alpha},\boldsymbol{\hat{\alpha}},\boldsymbol{\xi},\boldsymbol{\hat{\xi}},\boldsymbol{\mu},\boldsymbol{\hat{\mu}})

和SVM分类模型一样，这个优化目标也满足KKT条件，也就是说，我们可以通过拉格朗日对偶将我们的优化问题转化为等价的对偶问题来求解如下：

1
\underset{\boldsymbol{\mu},\boldsymbol{\hat{\mu}},\boldsymbol{\alpha},\boldsymbol{\hat{\alpha}}}{\max}\underset{\boldsymbol{\omega},b,\boldsymbol{\xi},\boldsymbol{\hat{\xi}}}{\min}L(\boldsymbol{\omega},b,\boldsymbol{\alpha},\boldsymbol{\hat{\alpha}},\boldsymbol{\xi},\boldsymbol{\hat{\xi}},\boldsymbol{\mu},\boldsymbol{\hat{\mu}})

首先通过求偏导数，求关于$\boldsymbol{\omega},b,\boldsymbol{\xi},\boldsymbol{\hat{\xi}}$的极小值

1
2
3
4
5
6
7
\frac{\partial{L}}{\partial{\boldsymbol{\omega}}}=0\Rightarrow\boldsymbol{\omega}=\sum_{i=1}^m(\hat{\alpha_i}-\alpha_i)\boldsymbol{x}_i

\frac{\partial{L}}{\partial{b}}=0\Rightarrow\sum_{i=1}^m(\hat{\alpha}_i-\alpha_i)=0

\frac{\partial{L}}{\partial{\xi}_i}=0\Rightarrow\alpha_i+\mu_i=C

\frac{\partial{L}}{\partial{\hat{\xi}_i}}=0\Rightarrow\hat{\alpha}_i+\hat{\mu}_i=C

带入，得到对偶问题

1
2
3
4
5
6
7
\underset{\boldsymbol{\alpha},\boldsymbol{\hat{\alpha}}}{\max}\sum_{i=1}^my_i(\hat{\alpha}_i-\alpha_i)-\epsilon(\hat{\alpha}_i+\alpha_i)

-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m(\hat{\alpha}_i-\alpha_i)(\hat{\alpha}_j-\alpha_j)\boldsymbol{x}_i^T\boldsymbol{x}_j

s.t.\ \sum_{i=1}^m(\hat{\alpha}_i-\alpha_j)=0

0\leq\alpha_i,\hat{\alpha}_j\leq{C}

同样可通过SMO算法解出$\boldsymbol{\alpha},\boldsymbol{\hat{\alpha}}$，SVR的解为

1
f(\boldsymbol{x})=\sum_{i=1}^m(\hat{\alpha}_i-\alpha_i)\boldsymbol{x}_i^T\boldsymbol{x}+b
-------------The End-------------