支持向量机

支持向量机是一种二分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器,支持向量机还包括核技巧,这使它成为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化,可形式化为一个求解凸二次规划的问题。
支持向量机学习方法包含构建由简至繁的模型:

  • 当训练数据线性可分时,通过硬间隔最大化(hard margin maximization),学习一个线性的分类器,即线性可分支持向量机。
  • 当训练数据近似线性可分时,通过软间隔最大化(soft margin maximization),也学习一个线性的分类器,即线性支持向量机。
  • 当训练数据线性不可分时,通过使用核技巧(kernel trick)及软间隔最大化,学习非线性支持向量机。

间隔与支持向量

给定训练样本集$D={(\boldsymbol{x_1},y_1),(\boldsymbol{x_2},y_2),…,(\boldsymbol{x_m},y_m)}, y_m\in{-1,+1}$,分类学习最基本的想法就是基于训练集D在样本空间中找到一个划分超平面,将不同类别的样本分开。

能将两类训练样本分开的超平面有很多,应该找两类训练样本正中间的划分超平面,因为该划分超平面对训练样本局部扰动的容忍性最好,产生的分类结果是最鲁棒的,对未见实例的泛化能力最强。
在样本空间中,划分超平面可通过如下线性方程来描述:

$$
\begin{aligned}
\boldsymbol{w^{T}x}+b=0
\end{aligned}\tag{1}
$$
其中$\boldsymbol{w}=(w_1;w_2;…;w_d)$为法向量,决定了超平面的方向,b为位移项,决定了超平面与原点之间的距离。划分超平面可被法向量$\boldsymbol{w}$和位移b确定,下面将其记为$(\boldsymbol{w},b)$。样本空间中任意点$\boldsymbol{x}$到超平面$(\boldsymbol{w},b)$的距离可写为

$$
\begin{aligned}
r=\frac{|\boldsymbol{w^Tx}+b|}{||\boldsymbol{w}||}
\end{aligned}\tag{2}
$$
假设超平面$(\boldsymbol{w},b)$能将训练样本正确分类,即对于$(\boldsymbol{x_i},y_i)\in D$,若$y_i=+1$,则有$\boldsymbol{w^Tx_i}+b>0$;若$y_i=-1$,则有$\boldsymbol{w^Tx_i}+b<0$。令

$$
\begin{cases}
\boldsymbol{w^Tx_i}+b \geqslant +1, & y_i=+1; \\
\boldsymbol{w^Tx_i}+b \leqslant -1, & y_i=-1.
\end{cases}\tag{3}
$$
如下图所示,距离超平面最近的这几个训练样本点使式(3)等号成立,它们被称为支持向量(support vector),这两类支持向量到超平面的距离之和为

$$
\begin{aligned}
\gamma=\frac{2}{||\boldsymbol{w}||}
\end{aligned}\tag{4}
$$
它被称为间隔(margin)

要找到具有最大间隔(maximum margin)的划分超平面,也就是要找到能满足式(3)中约束的参数$\boldsymbol{w}$和$b$,使得$\gamma$最大,即

$$
\begin{aligned}
& \max_{\boldsymbol{w},b}\frac{2}{||\boldsymbol{w}||} \\
& s.t. \ y_i(\boldsymbol{w^Tx_i}+b) \geqslant 1, \quad i=1,2,…,m.
\end{aligned}\tag{5}
$$
为了最大化间隔,需最大化$||\boldsymbol{w}||^{-1}$,等价于最小化$||\boldsymbol{w}||^2$。因此,式(5)可写为

$$
\begin{aligned}
& \min_{\boldsymbol{w},b}\frac{1}{2}||\boldsymbol{w}||^2 \\
& s.t. \ y_i(\boldsymbol{w^Tx_i}+b) \geqslant 1, \quad i=1,2,…,m.
\end{aligned}\tag{6}
$$
这就是支持向量机(Support Vector Machine)的基本型。

对偶问题

式(6)是一个凸二次规划(convex quadratic programming)问题,能直接用现成的优化计算包求解,但还有更高效的办法。对式(6)使用拉格朗日乘子法可得到其对偶问题(dual problem)。对式(6)的每条约束添加拉格朗日乘子$\alpha_i\geqslant0$,则该问题的拉格朗日函数可写为

$$
\begin{aligned}
L(\boldsymbol{w},b,\boldsymbol{\alpha})=\frac{1}{2}||\boldsymbol{w}||^2+\sum_{i=1}^m\alpha_i(1-y_i(\boldsymbol{w^Tx_i}+b)),
\end{aligned}\tag{7}
$$
其中$\boldsymbol{\alpha}=(\alpha_1;\alpha_2;…;\alpha_m)$。令$L(\boldsymbol{w},b,\boldsymbol{\alpha})$对$\boldsymbol{w}$和$b$的偏导为零可得

$$
\begin{eqnarray}
\boldsymbol{w} &=& \sum_{i=1}^m\alpha_iy_ix_i, \tag{8} \\
0 &=& \sum_{i=1}^m\alpha_iy_i. \tag{9}
\end{eqnarray}
$$
将式(8)代入(7),即可将$L(\boldsymbol{w},b,\boldsymbol{\alpha})$中的$\boldsymbol{w}$和$b$消去,再考虑式(9)的约束,就得到式(6)的对偶问题

$$
\begin{aligned}
& \max_\alpha\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\boldsymbol{x_i^Tx_j} \\
& s.t. \ \sum_{i=1}^m\alpha_iy_i=0, \\
& \alpha_i \geqslant 0, \qquad i=1,2,…,m.
\end{aligned}\tag{10}
$$
解出$\alpha$后,求出$\boldsymbol{w}$与$b$即可得到模型

$$
\begin{aligned}
f(x)&=\boldsymbol{w^Tx}+b \\
&=\sum_{i=1}^m\alpha_iy_i\boldsymbol{x_i^Tx}+b
\end{aligned}\tag{11}
$$
从对偶问题(10)解出的$\alpha_i$是式(7)中的拉格朗日乘子,它对应着训练样本$(\boldsymbol{x_i},y_i)$。注意到式(6)中有不等式约束,因此上述过程需满足KKT(Karush-Kuhn-Tucker)条件,即要求

$$
\begin{cases}
\alpha_i\geqslant 0; \\
y_if(x_i)-1\geqslant 0; \\
\alpha_i(y_if(x_i)-1)=0.
\end{cases}\tag{12}
$$
于是,对任意训练样本$(\boldsymbol{x_i},y_i)$,总有$\alpha_i=0$或$y_if(\boldsymbol{x_i})=1$。若$\alpha_i=0$,则该样本不会在式(11)的求和中出现,也就不会对$f(x)$有任何影响;若$\alpha_i>0$,则必有$y_if(\boldsymbol{x_i})=1$,所对应的样本点位于最大间隔边界上,是一个支持向量。支持向量机的一个重要性质:训练完成后,大部分的训练样本都不需要保留,最终模型仅与支持向量有关。
式(10)是一个二次规划问题,可以用通用的二次规划算法求解,但是该问题的规模正比于训练样本数,人们通过利用问题本身的特性,提出了很多高效算法,SMO(Sequential Minimal Optimization)是最流行的一种。
SMO的思想是每次选取两个变量$\alpha_i$和$\alpha_j$,并固定其他的参数$\alpha_k$,求解式(10)获得更新后的$\alpha_i$和$\alpha_j$,不断迭代直至收敛。SMO采用了一个启发式:使选取的两变量所对应样本之间的间隔最大。仅考虑$\alpha_i$和$\alpha_j$时,式(10)中的约束可重写为:

$$
\begin{aligned}
\alpha_iy_i+\alpha_jy_j=-\sum_{k\neq i,j}\alpha_ky_k=c
\end{aligned}\tag{13}
$$
消去式(10)中的变量$\alpha_j$,则得到一个关于$\alpha_i$的单变量二次规划问题,仅有的约束是$\alpha_i\geqslant0$。这样的二次规划具有闭式解,不必调用数值优化算法即可高效地计算出更新后的$\alpha_i$和$\alpha_j$。
根据式(8)可求出$\boldsymbol{w}$,对于$b$,可以用任意一个支持向量的性质$y_s(\boldsymbol{w^Tx_s}+b)=1$来计算。当然现实任务中采用更鲁棒的做法,使用所有支持向量求解的平均值。

软间隔支持向量机

基础型的SVM的假设所有样本在样本空间是线性可分的(硬间隔),但现实中的情况通常不满足这种特性。为此,要引入软间隔(soft margin)的概念。

允许某些样本不满足约束 $y_i(\boldsymbol{w^Tx_i}+b)\geqslant1$,当然,在最大化间隔的同时,不满足约束的样本应尽可能少。

核函数

前面的讨论中,假设的训练样本是线性可分的,即存在一个划分超平面能将训练样本正确分类。然而现实任务中,原始样本空间内也许并不存在能正确划分两类样本的超平面。

这样的问题,可将样本从原始空间映射到一个更高维的特征空间,使得样本在这个特征空间内线性可分。令$\phi(\boldsymbol{x})$表示将$\boldsymbol{x}$映射后的特征向量,在特征空间中划分超平面所对应的模型可表示为

$$
\begin{aligned}
f(\boldsymbol{x})=\boldsymbol{w^T}\phi(\boldsymbol{x})+b
\end{aligned}\tag{14}
$$
其中$\boldsymbol{w}$和$b$是模型参数,间隔最大化类似式(6)

$$
\begin{aligned}
& \min_{\boldsymbol{w},b}\frac{1}{2}||\boldsymbol{w}||^2 \\
& s.t. \ y_i(\boldsymbol{w^T}\phi(\boldsymbol{x_i})+b)\geqslant1, \quad i=1,2,…,m.
\end{aligned}\tag{15}
$$
其对偶问题是

$$
\begin{aligned}
& \max_{\alpha}\sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\phi(\boldsymbol{x_i})\cdot\phi(\boldsymbol{x_j}) \\
& s.t. \ \sum_{i=1}^m\alpha_iy_i=0, \\
& \alpha_i\geqslant0, \quad i=1,2,…,m.
\end{aligned}\tag{16}
$$
式中$\phi(\boldsymbol{x_i})\cdot\phi(\boldsymbol{x_j})$为$\phi(\boldsymbol{x_i})$和$\phi(\boldsymbol{x_j})$的内积。
核函数的定义: 设$\mathcal{X}$是输入空间(欧式空间$\boldsymbol{R^n}$的子集或离散集合),又设$\mathcal{H}$为特征空间,如果存在一个从$\mathcal{X}$到$\mathcal{H}$的映射

$$
\phi(\boldsymbol{x}):\mathcal{X} \to \mathcal{H}
$$
使得对所有$\boldsymbol{x_i,x_j}\in\mathcal{X}$,函数$K(\boldsymbol{x_i,x_j})$满足条件

$$
K(\boldsymbol{x_i,x_j})=\phi(\boldsymbol{x_i})\cdot\phi(\boldsymbol{x_j})
$$
则称$K(\boldsymbol{x_i,x_j})$为核函数,$\phi(\boldsymbol{x})$为映射函数。
核技巧的想法是,在学习与预测中只定义核函数$K(\boldsymbol{x_i,x_j})$,而不显式定义映射函数。通常,直接计算核函数比较容易,计算映射函数的内积很困难,因为特征空间的维数可能很高,甚至是无穷维。

reference
《机器学习》
《统计学习方法》