支持向量机

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

  • 当训练数据线性可分时,通过硬间隔最大化(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在样本空间中找到一个划分超平面,将不同类别的样本分开。

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

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

\[ r=\frac{|\boldsymbol{w^Tx}+b|}{||\boldsymbol{w}||} \qquad (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; \qquad (3) \\ \boldsymbol{w^Tx_i}+b \leqslant -1, & y_i=-1. \end{cases} \] 如下图所示,距离超平面最近的这几个训练样本点使式(3)等号成立,它们被称为支持向量(support vector),这两类支持向量到超平面的距离之和为

\[ \gamma=\frac{2}{||\boldsymbol{w}||} \qquad (4) \] 它被称为间隔(margin)

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

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

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

对偶问题

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

\[ 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)), \qquad (7) \] 其中\(\boldsymbol{\alpha}=(\alpha_1;\alpha_2;...;\alpha_m)\)。令\(L(\boldsymbol{w},b,\boldsymbol{\alpha})\)\(\boldsymbol{w}\)\(b\)的偏导为零可得

\[ \begin{aligned} & \boldsymbol{w}=\sum_{i=1}^m\alpha_iy_ix_i, \qquad & (8) \\ & 0=\sum_{i=1}^m\alpha_iy_i. & (9) \end{aligned} \] 将式(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} \qquad (10) \\ & s.t. \ \sum_{i=1}^m\alpha_iy_i=0, \\ & \alpha_i \geqslant 0, \qquad i=1,2,...,m. \end{aligned} \] 解出\(\alpha\)后,求出\(\boldsymbol{w}\)\(b\)即可得到模型

\[ \begin{aligned} f(x)&=\boldsymbol{w^Tx}+b \\ &=\sum_{i=1}^m\alpha_iy_i\boldsymbol{x_i^Tx}+b \qquad (11) \end{aligned} \] 从对偶问题(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; \qquad (12) \\ \alpha_i(y_if(x_i)-1)=0. \end{cases} \] 于是,对任意训练样本\((\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)中的约束可重写为:

\[ \alpha_iy_i+\alpha_jy_j=-\sum_{k\neq i,j}\alpha_ky_k=c \qquad (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}\)映射后的特征向量,在特征空间中划分超平面所对应的模型可表示为

\[ f(\boldsymbol{x})=\boldsymbol{w^T}\phi(\boldsymbol{x})+b \qquad (14) \] 其中\(\boldsymbol{w}\)\(b\)是模型参数,间隔最大化类似式(6)

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

\[ \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}) \qquad (16) \\ & s.t. \ \sum_{i=1}^m\alpha_iy_i=0, \\ & \alpha_i\geqslant0, \quad i=1,2,...,m. \end{aligned} \] 式中\(\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
《机器学习》
《统计学习方法》