【西瓜书】第六章支持向量机

本文是周志华老师《机器学习》第六章支持向量机的学习笔记。部分内容来自PRML,凸优化, 线代启示录和李航老师的统计学习方法. 　　

间隔与支持向量

支持向量机(Support Vector Machine)是最常用的机器学习算法之一.
首先我们从最简单的SVM开始回顾. 假设一个特征空间中有若干二分类样本, 且它们是线性可分的,那么在能够将其正确分类的无数个超平面中,我们应该挑选怎样的超平面呢?
SVM给出的答案是: 找到在两类样本正中间的超平面. 很容易想出,此时该划分的泛化能力比较强.

我们用下式来表示划分的超平面:
$w^Tx+b=0$
其中$w$为法向量,$b$为位移, 那么样本空间中任一点$x$到该超平面的距离即为:

$r=\frac{|w^Tx+b|}{||w||}$

假设超平面能够分类正确,则可以(通过适当放缩)使下式成立:

$\begin{cases} w^Tx_i+b \ge +1& y_i = +1\\ w^Tx_i+b \le -1& y_i = -1 \end{cases}$

此时, 距离超平面最近的这几个训练样本刚好使上式的等号成立,它们就被称作支持向量,两个异类的支持向量到超平面的距离和为:

$\gamma = \frac{2}{||w||}$

该项则被称作间隔.

那么SVM的目标即为找到拥有最大间隔的那个超平面, 最大化间隔即为最小化下式:

$\begin{aligned} \min\limits_{w,b}&\quad \frac{1}{2}||w||^2 \\ s.t.&\quad y_i(w^Tx_i+b) \ge 1,\quad i=1,2,...,m \end{aligned}$

那么SVM问题就转为解决一个不等式限制下的优化问题.

对偶问题

为了解决这个问题, 可以使用拉格朗日乘子法来构造其对偶问题.

对于拉格朗日对偶性,可以参考李航老师<统计机器学习>附录C部分. 需要注意的是,对偶函数的解给出了的是主问题的下界, 即对偶问题的最优解并不等于主问题(原问题)的最优解. 只有当 主问题是凸优化问题且可行域中至少有一点满足约束时,两个问题的最优解一样, 称作 强对偶性.

幸运的是SVM要解决的问题恰好满足强对偶性,因此我们可以通过构造并解决对偶问题来解SVM的主问题,且通过对偶问题,可以自然地引入后面的核技巧.

由之前的优化目标根据约束加入拉格朗日乘子$\alpha_i\ge 0$,将带约束的优化目标写为拉格朗日函数:

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

通常拉格朗日乘子法到这一步, 接下去应该是对原问题参数和乘子求偏导置零, 但是此处我们发现虽然将约束化到了优化目标中,但是引入的拉格朗日乘子也有约束($\alpha_i\ge 0$).
这里有巧妙的一个处理, 我们构造如下的一个函数:

$\theta_P(w,b)=\max\limits_{\alpha \ge 0}L(w,b,\alpha)$

容易看出, 当某个约束条件不满足时, 该函数的值一定是$+\infty$ (设此时对应的不满足约束条件的乘子项为$\alpha_k$.约束条件不满足即为$1-y_i(w^Tx_i+b) >0$. 由于$\alpha$只要大于等于零即可, 则它可以取到正无穷,从而使得整个函数也为正无穷).
当所有约束条件满足时(即$1-y_i(w^Tx_i+b) \le 0$), 为了使$L(w,b,\alpha)$最大, 所有$\alpha$都会取到零, 此时$\theta_P(w,b)=1/2||w||^2$, 即为我们原始问题的优化目标.

也就是说我们构造的这个$\theta_P$函数和之前的那个带约束优化问题是等价的.

因此我们的主问题(Primal mini-max) 的形式就可以写作:

$\min\limits_{w,b}\theta_P(w,b)=\min\limits_{w,b}\max\limits_{\alpha\ge 0} L(w,b,\alpha)$

其最优解我们记做$p*$.

然后交换min和max以构造其对偶问题(Dual maximin):

$\max\limits_{\alpha}\theta_D(\alpha)=\max\limits_{\alpha\ge 0}\min\limits_{w,b}L(w,b,\alpha)$

注意一下这里主问题要解的是模型参数$w,b$, 对偶问题要解的是拉格朗日乘子$\alpha$. 当然,模型参数和乘子这二者解出来一个都能用来求出剩下的.

进一步的,为了解这个对偶问题,先来考虑右边min的部分: 我们对$L(w,b,\alpha)$在$w,b$上求偏导置零,然后将结果代入回去,得到对偶问题的另一种表达:

$\begin{aligned}\max\limits_\alpha &\sum_{i=1}^m-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_jx^T_ix_i \\ s.t. &\quad \sum_{i=1}^m\alpha_iy_i=0,\\ &\alpha_i\ge 0,\quad i=1,2,...,m \end{aligned}$

由上式解出$\alpha$后再求$w,b$可以得到最终模型:

$\begin{aligned} f(x) &=w^Tx+b \\ &=\sum_{i=1}^m\alpha_iy_ix_i^Tx+b \end{aligned}$

KKT条件

回顾上面的过程,这里该问题满足KKT(Karush-Kuhn-Tucker)条件. 该条件是优化问题中一个重要的限制条件, 其泛化的过程是这样的:

对于无限制优化问题, 只要求其驻点就行了.
对于等号限制优化问题, 则需要加上拉格朗日乘子.
对于不等限制优化问题, 则需要保证KKT条件了.

具体而言, 该条件是这样的:

$\begin{cases} \alpha_i \ge 0\quad &\text{dual feasibility};\\ y_if(x_i)-1\ge 0\quad & \text{primal feasibility}; \\ \alpha_i(y_if(x_i)-1)= 0\quad & \text{complementary slackness.} \end{cases}$

第一个条件dual feasibility(对偶可行性), 正如其名, 是对偶问题的限制条件,也就是对拉格朗日乘子的限制.
第二个条件primal feasibility(主可行性), 则是我们最初主问题的限制条件.
第三个条件complementary slackness, 直接翻译成中文可以叫互补松弛量. 对于这个条件的理解,首先明确对偶问题(max-min)的解是主问题(min-max)的下界. 那么这个变量大概就衡量了该界的准确的, 当slackness为零时,表示主问题和对偶问题的最优解一致. 因此台湾那边也把这个slackness叫做”差余”, 大概是衡量两个问题最优解之间的差. 当该条件得到满足时,我们通常也叫保证了 强对偶.

对于凸优化问题,KKT条件就保证了不等限制优化问题能够得到最值解(充要条件). 但是需要注意,对于一些非凸问题, KKT条件就只是一个必要条件而非充要条件. (另一种有趣的可以替代KKT的条件叫做FJ条件, 感兴趣可以搜搜看)

SMO算法

前面说了很多问题的转换,包括从主问题引入拉格朗日算法,再转成对偶问题,在KKT条件下对偶问题的最优解等价于主问题最优解,因此我们可以通过求解对偶问题来解主问题.

当然这种二次规划问题可以通过二次规划算法来解,但是问题规模正比于样本数, 实际任务中很难接受.一个常用的高效算法就是SMO(Sequential Minimal Optimization, 序列最小化优化算法).
这是一个启发式算法, 其大体步骤为:

选取两个需要更新的变量$\alpha_i,\alpha_j$
固定其他变量,针对上述两个变量做更新
所有参数都满足KKT, 则得到解, 否则重复上述两步操作.

可以看出, 步骤一是启发式的, 步骤二则是解析的.
对于步骤二,由于我们只关心两个变量,而且可以用约束条件消去一个变量,因此最终我们只需要解一个单变量的二次规划问题,该问题有解析解,所有很容易求得.

对于步骤一, 我们如何选取这两个变量呢? SMO中选择第一个变量为违背KKT条件最严重的变量,第二个变量则选择使目标函数增长最快的变量, 实践中SMO选择对应的样本之间的间隔最大的两变量.

解出所有$\alpha$后,我们可以通过:

$w^T=\sum_{i=1}^m\alpha_iy_ix_i^T$

来求$w$, 至于$b$, 此时其实可以任意选取支持向量来获取,但是现实中,我们使用所有支持向量解的均值来增强其鲁棒性.

　核函数　　　

前面的算法中，　虽然和线性回归不同，引入了最大间隔，但是本质上还是一个线性模型，　无法处理线性不可分的情况（异或）．

为了解决这个问题, 我们需要在SVM上加入核技巧. 需要注意的是, 核技巧的适用范围不仅是SVM, 它是一种更通用的方法能够广泛适用于各个ML算法.

简单来说,对于线性不可分的问题, 我们可将其映射岛更高维度的特征空间使其线性可非.

令$\phi(x)$表示将$x$映射后的特征向量,那么该模型即为:

$f(x)=w^T\phi(x)+b$

类似的, 我们的优化问题就变成了:

$\begin{aligned} \min\limits_{w,b} &\quad \frac{1}{2}||w||^2 \\ s.t.&\quad y_i(w^T\phi(x)+b) \ge 1,\quad i=1,2,..,m \end{aligned}$

同样的,对偶问题写作:

$\begin{aligned} \max\limits_{\alpha} &\quad \sum_{i=1}^m\alpha_i - \frac{1}{2}\sum_{j=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\phi(x_i)^T\phi(x_j)\\ s.t.&\quad \sum_{i=1}^m\alpha_iy_i=0\\ &\quad \alpha_i \ge 0, \quad i=1,2,...,m. \end{aligned}$

但是由于新的特征空间的维数可能很高,因此直接计算内积可能会很困难, 因此我们假设有个函数可以算出这个内积:

$\kappa(x_i,x_j) = \phi(x_i)^T\phi(x_j)$

这个函数就是核函数, 因此我们求解就可以得到:

$\begin{aligned} f(x)&=w^T\phi(x)+b \\ &=\sum_{i=1}^m\alpha-iy_i\phi(x_i)^T\phi(x)+b \\ &=\sum_{i=1}^m\alpha-iy_i\kappa(x, x_i) + b \end{aligned}$

当然如果我们知道合适的映射$\phi()$则很容易推出$\kappa$,但是即使我们不知道映射的具体形式,我们也可以使用核函数. 满足下面的条件的函数都可以用过核函数

核函数定理 $\kappa$是核函数当前仅当任意数据$D={x_1,…,x_m}$的核矩阵(需要是对称矩阵)$K$总是半正定的.

每个核函数都隐式定义了一个叫做再生核希尔伯特空间的特征空间.

下面给出常见核函数:

线性核
$\kappa(x_i,x_j) = x_i^Tx_j$
多项式核
$\kappa(x_i,x_j) = (x_i^Tx_j)^d, \quad d\ge1$

高斯核 $\kappa(x_i,x_j) = exp(-\frac{||x_i-x_j||^2}{2\sigma^2})$
拉普拉斯核
$\kappa(x_i,x_j) = exp(-\frac{||x_i-x_j||}{\sigma})$
Sigmoid核
$\kappa(x_i,x_j) = tanh(\beta x_i^Tx_j+\theta)$

软间隔和正则化

简单说一下,就是当数据量较大且很复杂时,我们很难确定一个核函数能够使我们的SVM完美分开不同样本.此时我们想到允许一些瑕疵,即允许部分样本点被分类错误.
之前那种需要完全分对的叫做硬间隔,而允许出现错误的叫 软间隔.

当然我们在最大化间隔的同时,要求不满足约束的样本尽可能小,实现上是通过给优化目标加上一个项来控制这些瑕疵. 例如:

$\min\limits_{w,b}\frac{1}{2}||w||^2 +C\sum_{i=1}^ml_{0/1}(y_i(w^Tx_i+b)-1)$

$C$是控制惩罚项的常数, $l_{0/1}$是01损失函数.但是该算是函数非凸非连续, 数学性质不好,因此,人们常用一些其他的函数来代替之:

hinge损失 $l_{hinge}(z)=\max(0,1-z)$
指数损失 $l_{exp}(x)=\exp(-z)$
对率损失 $l_{log}(z)=\log(1+\exp(-z))$

当使用对率损失函数时,SVM和对率回归就几乎一样,其优化目标类似,性能也相当. 但是对率回归能够给出具有概率意义的输出.

更广义上来说, 我们可以将优化目标分为两部分:

$\min\limits_{f}\Omega(f)+C\sum_{i=1}^ml(f(x_i),y_i)$

前面的称作 结构风险描述模型的性质,后面的则称作 经验风险用于描述模型对数据的拟合程度.$C$用于折中二者.

相比大家也猜到前者就是之前提过的 正则化项, 我们常用$L_p$范数作为正则化项.其中:

$L_2$范数倾向于使参数的分量取值均衡,非零参数个数尽量多.
$L_0$和$L_1$范数倾向于参数分量尽量稀疏,即非零分量个数尽量少.

支持向量回归

SVM也可以用于回归问题,即SVR. 其解法也类似, 需要注意的是和传统回归模型不同,类似之前提到的软间隔, 我们可以容忍预测输出和实际结果有$\epsilon$的偏差, 等于说以$f(x)$为中心构建了一个宽度为$2\epsilon$的间隔带, 当样本落入该间隔带,就认为其被预测正确.
其解法可以通过引入松弛变量然后拉格朗日乘子再化为对偶问题来解.
同样的, SVR也可以使用核函数, 具体的就不赘述了.

核方法

对于前面说到的SVM和SVR, 我们发现学到的模型可以表示为核函数的线性组合, 事实上, 表示定理给出了更一般的结论:

表示定理: 令$\mathbb{H}$为核函数$\kappa$对应的再生核希尔伯特空间，$||h||_\mathbb{H}$表示$\mathbb{H}$空间中关于$h$的范数，对于任意单调递增函数$\Omega:[0,\infty]\rightarrow \mathbb{R}$ 和任意非负损失函数 $l:\mathbb{R}^m\rightarrow [0,\infty]$, 优化问题：

$\min_{h\in\mathbb{H}}F(h)=\Omega(\|h\|_{\mathbb{H}}) + l(h(x_1), h(x_2),...,h(x_m))$

的解总可写为：

$h*(x)=\sum_{i=1}^m\alpha_i\kappa(x,x_i)$

表示定理对损失函数没有限制，且正则化项仅要求单调递增（不要求是凸函数），也就是说对于我们常用的损失函数和正则化项，优化问题的最优解都可以表示为核函数的线性组合。

所有基于核函数的学习方法都叫做核方法，常用的手段是通过引入核函数来将线性学习器拓展为非线性学习器（例如线性回归->广义线性回归，线性判别分析LDA->核线性判别分析KLDA）

习题及参考

6.1: 试证明样本空间中任意点$x$到超平面$(w,b)$的距离为式6.2.

6.2: 使用libsvm,在西瓜数据集3.0a上分别用线性核和高斯核训练一个svm,并比较其支持向量的差别.
见github .

6.3 选择两个UCI数据集,分别用线性核和高斯核训练一个SVM并与BP神经网络和C4.5决策树进行实验比较
见github .

6.4 是讨论线性判别分析和线性核支持向量在何种条件下等价.

很多情况下LDA和线性SVM的分类表现都很相近, 不过仅当所有样本点都被SVM用作为支持向量时二者才等价.

6.5 试述高斯核SVM和RBF神经网络之间的联系

高斯核SVM的主要思想是先用RBF函数将原数据做转换, 然后再施加SVM.
RBF神经网络也是类似的思想, 先用RBF函数将原来的数据做转换, 然后线性加权组合输出.

但是不同点在于,高斯核SVM将RBF函数仅作为计算高维空间内积的假想函数,即实际上数据并非是被映射到RBF函数的输出; 而RBF神经网络则是真的用RBF函数将输入映射一个已知的空间.

6.6 试析SVM对噪声敏感的原因

因为SVM最终只用到了若干支持向量来生成分类的超平面, 如果噪声更好成为支持向量,则整个超平面的划分就会有问题. 而噪声往往又都是outlier离群点, 容易成为支持向量.

6.7 试给出式(6.52)的完整KKT条件.

不是很理解这里的题意, 6.52不是给出了KKT条件了吗..

6.8 以西瓜数据集3.0a的密度为输入,含糖率为输出,试使用LIBSVM训练一个SVR.

见github .

6.9 试使用核技巧推广对率回归,产生”核对率回归”.

很简单, 略了.