支持向量机(SVM)

SVM 的数学推导算是一个基本功,手打公式也比手写更繁琐,但整理笔记的过程有助于更好地理解,内容基本基于《统计学习方法》第 7 章。

支持向量机简介

支持向量机(support vector machine, SVM) 是一种二分类模型,它的基本模型是定义在特征空间上的间隔最大的线性分类器,间隔最大使它有别于感知机;支持向量机还包括核技巧,这使它成为实质上的非线性分类器。支持向量机的学习策略就是间隔最大化,可形式化为一个求解凸二次规划(convex quadratic programming)的问题,也等价于正则化的合页损失函数的最小化问题。支持向量机的学习算法是求解凸二次规划的最优化算法。

支持向量机学习方法包含构建由简至繁的模型:线性可分支持向量机(linear support vector machine in linearly separable case)、线性支持向量机(linear support vector machine)及非线性支持向量机(non-linear support vector machine)。简单模型是复杂模型的基础,也是复杂模型的特殊情况。当训练数据线性可分时,通过硬间隔最大化(hard margin maximization),学习一个线性的分类器,即线性可分支持向量机,又称为硬间隔支持向量机;当训练数据近似线性可分时,通过软间隔最大化(soft margin maximization),也学习一个线性的分类器,即线性支持向量机,又称为软间隔支持向量机;当训练数据线性不可分时,通过使用核技巧 (kernel trick)及软间隔最大化,学习非线性支持向量机

本章按照上述思路介绍 3 类支持向量机、核函数及一种快速学习算法——序列最小最优化算法(SMO)

1.1 线性可分支持向量机与硬间隔最大化

输入都由输入空间转换到特征空间,支持向量机的学习是在特征空间进行的。

假设给定一个特征空间上的训练数据集

其中,$x_i \in \mathbf {\chi} = R^n$,$y_i \in \mathbf {y} = \lbrace +1,-1 \rbrace , i=1,2,…,N$,$x_i$ 为第 $i$ 个特征向量,也称为实例,$y_i$ 为 $x_i$ 的类标记,正负时分别称 $x_i$ 为正例或负例;$(x_i,y_i)$ 称为样本点,再假设训练数据集是线性可分的。

学习的目标是在特征空间中找到一个分离超平面,能将实例分到不同的类。分离超平面对应于方程 $w \cdot x + b = 0$,它由法向量 $w$ 和截距 $b$ 决定,可用$(w, b)$表示。分离超平面将特征空间划分为两部分,一部分是正类,一部分是负类。法向量指向的一侧为正类,另一侧为负类。

一般地,当训练数据集线性可分时,存在无穷个分离超平面可将两类数据正确分开。感知机利用误分类最小的策略,求得分离超平面,不过这时的解有无穷多个。线性可分支持向量机利用间隔最大化求最优分离超平面,这时,解是唯一的。

定义 (线性可分支持向量机) 给定线性可分训练数据集,通过间隔最大化或等价地求解相应的凸二次规划问题学习得到的分离超平面为

以及相应的分类决策函数

称为线性可分支持向量机。

考虑如图所示的二维特征空间中的分类问题。图中“。”表示正例,“x ”表示负例。训练数据集线性可分,这时有许多直线能将两类数据正确划分。线性可分支持向量机对应着将两类数据正确划分并且间隔最大的直线,如图所示。

间隔最大及相应的约束最优化问题将在下面叙述。这里先介绍函数间何间隔的概念。

1.2 函数间隔和几何间隔

在上图中,有 A、B、 C 三个点,表示 3 个实例,均在分离超平面的正类一侧,预测它们的类。点 A 距分离超平面较远,若预测该点为正类,就比较确信预测是正确的;点 C 距分离超平面较近,若预测该点为正类就不那么确信;点B介于点A与C之间,预测其为正类的确信度也在A与C之间。

定义(函数间隔) 对于给定的训练数据集T和超平面(w,b),定义超平 面$(w,b)$关于样本点$(x_i,y_i)$的函数间隔为

函数间隔可以表示分类的正确性和准确度:在超平面$w\cdot x + b = 0$ 确定的情况下 $\vert w\cdot x + b \vert$ 能够相对地表示点 $x$ 距离超平面的远近。而$w\cdot x + b$ 的符号与类标记 $y$ 的符号是否一致能够表示分类是否正确。所以可用量 $y(w\cdot x+b)$ 来表示分类的正确性及确信度,这就是函数间隔(functional margin)的概念。

定义超平面 $(w,b)$ 关于训练数据集 $T$ 的函数间隔为超平面$(w,b)$关于T中所有样本点 $(x_i,y_i)$ 的函数间隔之最小值,即

函数间隔可以表示分类预测的正确性及确信度。但是选择分离超平面时,只有函数间隔还不够。 因为只要成比例地改变 $w$ 和 $b$ ,例如将它们改为 $2w$ 和 $2b$ ,超平面并没有改变,但函数间隔却成为原来的 2 倍。这一事实启示我们,可以对分离超平面的法向量 $w$ 加某些约束,如规范化, $\Vert w \Vert=1$ ,使得间隔是确定的。这时函数间隔成为几何间隔(geometric margin)。

下图给出了超平面 $(w,b)$ 及其法向量 $w$ 。点 A 表示某一实例 $x_i$ ,其类标记 为 $y_i=+1$ 。点 A 与超平面 $(w, b)$ 的距离由线段 AB 给出,记作 $\gamma_i$ 。

其中, $|w|$ 为 $w$ 的 $L_2$ 范数。这是点 A 在超平面正的一侧的情形。如果点 A 在超平面负的一侧,即 $y_i=-1$ ,那么点与超平面的距离为

由这一事实导出几何间隔的概念。

定义(几何间隔) 对于给定的训练数据集 $T$ 和超平面 $(w, b)$ ,定义超平 面 $(w,b)$ 关于样本点 $(x_i,y_i)$ 的几何间隔为

定义超平面 $(w,b)$ 关于训练数据集 $T$ 的几何间隔为超平面 $(w,b)$ 关于T中所有样本点 $(x_i,y_i)$的几何间隔之最小值,即

超平面 $(w,b$) 关于样本点 $(x_i,y_i)$ 的几何间隔一般是实例点到超平面的带符号的距离(signed distance),当样本点被超平面正确分类时就是实例点到超平面的距离。

从函数间隔和几何间隔的定义可知,函数间隔和几何间隔有下面的关系:

如果 $\Vert w \Vert=1$ ,那么函数间隔和几何间隔相等。如果超平面参数 $w$ 和 $b$ 成比例地改变(超平面没有改变),函数间隔也按此比例改变,而几何间隔不变。

1.3 间隔最大化

支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对线性可分的训练数据集而言,线性可分分离超平面有无穷多个(等价于感知机),但是几何间隔最大的分离超平面是唯一的。这里的间隔最大化又称为硬间隔最大化(与将要讨论的训练数据集近似线性可分时的软间隔最大化相对应)。

间隔最大化的直观解释是:对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。也就是说,不仅将正负实例点分开,而且对最难分的实例点(离超平面最近的点)也有足够大的确信度将它们分开。这样的超平面应该对未知的新实例有很好的分类预测能力。

1.3.1. 最大间隔分离超平面

下面考虑如何求得一个几何间隔最大的分离超平面,即最大间隔分离超平面。具体地,这个问题可以表示为下面的约束最优化问题:

即我们希望最大化超平面 $(w,b)$ 关于训练数据集的几何间隔 $\gamma$ 。约束条件表示的是超平面 $(w,b)$ 关于每个训练样本点的几何间隔至少是 $\gamma$ 。

考虑几何间隔和函数间隔的关系式 $\gamma = \frac{\hat \gamma}{\Vert w \Vert}$,可将这个问题改写为:

也就是把几何间隔换为函数间隔

函数间隔函数间隔 $\hat \gamma$ 的取值并不影响最优化问题的解。事实上,假设将 $w$ 和 $b$ 按比例改变为 $\lambda w$ 和 $\lambda b$,这时函数间隔成为 $\lambda \hat \gamma$ 。函数间隔的这一改变对上面最优化问题的不等式约束没有影响,对目标函数的优化也没有影响,也就是说,它产生一个等价的最优化问题。 这样,就可以取 $\hat \gamma = 1$ 。将 $\hat \gamma = 1$ 代入上面的最优化问题,注意到最大化 $\frac{1}{\Vert w \Vert}$ 和最小化 $\frac{1}{2}{\Vert w \Vert}^2$ 是等价的,于是就得到下面的线性可分支持向量机学习的最优化问题

这是一个凸二次规划(convex quadratic programming)问题。

凸优化问题是指约束最优化问题

其中,标函数 $f(w)$ 和约束函数 $g_i(w)$ 都是上的连续可微的凸函数,约束函数是 $R^n$ 上的仿射函数:

$f(x)$ 如果满足 $f(x) = a \cdot x + b,\quad a\in R^n, b\in R^n, x \in R^n$,则被称为仿射函数

当目标函数 $f(w)$ 是二次函数且约束函数 $g(w)$ 是仿射函数时,上述凸最优化问题被称作凸二次规划问题。


线性可分支持向量机学习算法——最大间隔法

求得最优解 $w^,b^$ ,由此得到分离超平面

分类决策函数:


1.3.2. 最大间隔分离超平面的存在唯一性

这部分只是大致写一下思路。

存在性证明:证最优化问题必有解,且最优解满足$w^* \neq 0$ 。

唯一性证明:假设有两个最优解,证得两个最优解其实是相同的。

1.3.3 支持向量和间隔边界

在线性可分情况下,训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量(support vector)。支持向量是使约束条件式 $y_i(w\cdot x + b) - 1 \ge 0$ 等号成立的点,即

对 $y=+1$ 的正例点,支持向量在超平面

上。对 $y=-1$ 的负例点,支持向量在超平面

上。如图所示,在 $H_1$ 和 $H_2$ 上的点就是支持向量。

注意到$H_1$ 和 $H_2$平行,并且没有实例点落在它们中间。在 $H_1$ 和 $H_2$ 之间形成一条长带,分离超平面与它们平行且位于它们中央。长带的宽度,即 $H_1$ 和 $H_2$ 之间的距离称为间隔(margin)。间隔依赖于分离超平面的法向量 $w$ ,等于 $\frac{2}{\Vert w \Vert}$ 。$H_1$ 和 $H_2$称为间隔边界。

在决定分离超平面时只有支持向量起作用,而其他实例点并不起作用。如果移动支持向量将改变所求的解;但是如果在间隔边界以外移动其他实例点,甚至去掉这些点,则解是不会改变的。由于支持向量在确定分离超平面中起着决定性作用,所以将这种分类模型称为支持向量机。支持向量的个数一般很少,所以支持向量机由很少的“重要的”训练样本确定。

1.4 学习的对偶算法

为了求解线性可分支持向量机的最优化问题:

将它作为原始最优化问题,应用拉格朗日对偶性,通过求解对偶问题(dual problem)得到原始问题(primal problem)的最优解,这就是线性可分支持向量机的对偶算法(dual algorithm)。这样做的优点,一是对偶问题往往更容易求解;二是自然引入核函数,进而推广到非线性分类问题

首先构建拉格朗日函数(Lagrange function)。为此,对每一个不等式约束:$ y _ { i } \left( w \cdot x _ { i } + b \right) - 1 \geq 0 $ ,引进拉格朗日乘子 $\alpha_i \ge 0$,定义拉格朗日函数:

其中,$ \alpha = \left( \alpha _ { 1 } , \alpha _ { 2 } , \cdots , \alpha _ { N } \right) ^ { T } $ 为拉格朗日乘子向量。

根据拉格朗日对偶性,原始问题的对偶问题是极大极小问题:

所以,为了得到对偶问题的解,需要先求 $L ( w , b , \alpha ) $ 对 $w, b$ 的极小,再求对 $\alpha$ 的极大。


解释一下

之前原始问题的规范是这样的:

且拉格朗日函数规范是这样的:

现在我们的约束是大于号,$s.t. \qquad y_i(w\cdot x + b) - 1 \ge 0, \quad i=1,2,…,N$,相当于是 $-(y_i(w\cdot x_i +b) + 1)\alpha_i$,由于没有第二个约束条件 $h_j(x)=0$,所以没有引入另一个拉格朗日乘子 $\beta$

拉格朗日对偶的规范如下:

原始问题

对偶问题

现在再来这个案例中的原始问题和对偶问题

原始问题

对偶问题

为了得到对偶问题的解,需要先求 $L ( w , b , \alpha ) $ 对 $w, b$ 的极小,再求对 $\alpha$ 的极大。


(1) 求 $\min_{w,b} L(w,b,\alpha)$

将拉格朗日函数 $L ( w , b , \alpha ) $ 分别对 $w, b$ 求偏导并令其为 $0$ 。

得到:

将式 $ w = \sum _ { i = 1 } ^ { N } \alpha _ { i } y _ { i } x _ { i } $ 带入拉格朗日函数 $L ( w , b , \alpha ) $,并利用式 $ \sum _ { i = 1 } ^ { N } \alpha _ { i } y _ { i } = 0 $,即得:

(2) 求 $\min_{w,b} L(w,b,\alpha)$ 对 $\alpha$ 的极大

即是对偶问题

将上式的目标函数由求极大转换成求极小(取个相反数),就得到下面与之等价的对偶最优化问题:

考虑最优化问题和对偶最优化问题,原始问题满足定理 C.2,所以存在 $w^\ast, \alpha^\ast,\beta^\ast$ 使 $w^\ast$ 是原始问题的解,$\alpha^\ast,\beta^\ast$ 是对偶问题的解,这意味着求解原始问题可以转换为求解对偶问题,即上述公式。

对线性可分训练数据集,假设对偶最优化问题对 $\alpha$ 的解为 $ \alpha ^ { \ast } = \left( \alpha _ { 1 } ^ { \ast } , \alpha _ { 2 } ^ { \ast } , \cdots , \alpha _ { N } \right) ^ { T } $ , 可以由求得原始最优化问题对 $(w,b)$ 的解 $w^\ast,b^\ast$。

有下面的定理。

定理 7.2 设 $\alpha ^ { \ast } = \left( \alpha _ { 1 } ^ { \ast } , \alpha _ { 2 } ^ { \ast } , \cdots , \alpha _ { N } \right) ^ { T } $ 是对偶最优化问题的解,则存在下标 $j$,使得 $\alpha_j ^ \ast > 0$,并可按下式求得原始最优化问题的解 $w^\ast,b^\ast$:

证明 根据定理 C.3 KTT 条件成立,即得:

其中至少有一个 $\alpha_j ^ \ast > 0$ (用反证法,假设 $\alpha^\ast = 0$,由上式可知 $w^\ast = 0$,不是原始最优化问题的解)

所以对此 $j$ 有

将 $ w ^ { \ast } = \sum _ { i = 1 } ^ { N } \alpha _ { i } ^ { \ast } y _ { i } x _ { i } $ 代入 $ y _ { j } \left( w ^ { \ast } \cdot x _ { j } + b ^ { \ast } \right) - 1 = 0 $ 并注意到 $ y _ { j } ^ { 2 } = 1 $,即得

由此定理可知,分离超平面可以写成

分类决策函数可以写成

这就是说,分类决策函数只依赖于输入 $x$ 和训练样本输入的内积。$ f ( x ) = \operatorname { sign } \left( \sum _ { i = 1 } ^ { N } \alpha _ { i } ^ { \ast } y _ { i } \left( x \cdot x _ { i } \right) + b ^ { \ast } \right) $ 称为线性可分支持向量机的对偶形式。


综上所述,对于给定的线性可分训练数据集,可以首先求对偶问题

的解 $ \alpha ^ { \ast } = \left( \alpha _ { 1 } ^ { \ast } , \alpha _ { 2 } ^ { \ast } , \cdots , \alpha _ { N } \right) ^ { T } $

再利用式 $ w ^ { \ast } = \sum _ { i = 1 } ^ { N } \alpha _ { i } ^ { \ast } y _ { i } x _ { i } $ 和 $b ^ { \ast } = y _ { j } - \sum _ { i = 1 } ^ { N } \alpha _ { i } ^ { \ast } y _ { i } \left( x _ { i } \cdot x _ { j } \right)$ 求得原始问题的解 $w^\ast,b^\ast$,从而得到分离超平面及分类决策函数。这种算法称为线性可分支持向量机的对偶学习算法,是线性可分支持向量机学习的基本算法。


定义:支持向量 将训练集中对于 $\alpha_i^\ast > 0$ 的样本点 $(x_i, y_i)$ 的实例 $x_i \in R^n$ 称为支持向量。

据这一定义,支持向量一定在间隔边界上。由 KKT 互补条件之 $ \alpha _ { i } ^ { \ast } c _ { i } \left( x ^ { \ast } \right) = 0 $ 和 $-c_i = y _ { i } \left( w ^ { \ast } \cdot x _ { i } + b ^ { \ast } \right) - 1 $ 可知,对应于 $ \alpha _ { i } ^ { \ast } > 0 $ 的实例 $x_i$,有

又应为 $ y _ { i } = \pm 1 $,所以上式等效于

即 $x_i$ 一定在间隔边界上。这里的支持向量的定义与前面给出的支持向量的定义是—致的。

对于线性可分问题,上述线性可分支持向量机的学习(硬间隔最大化)算法是完美的。但是,训练数据集线性可分是理想的情形。在现实问题中,训练数据集往往是线性不可分的,即在样本中出现噪声或特异点。此时,有更一般的学习算法。

1.5 线性支持向量机与软间隔最大化

线性可分问题的支持向量机学习方法,对线性不可分训练数据是不适用的,因为这时上述方法中的不等式约束并不能都成立。怎么才能将它扩展到线性不可分问题呢?这就需要修改硬间隔最大化,使其成为软间隔最大化

通常情况是,线性不可分的训练数据中有一些特异点(outlier),将这些特异点除去后,剩下大部分的样本点组成的集合是线性可分的。

我们给每一个样本点引进一个松弛变量 $ \xi _ { i } \geq 0$, 使函数间隔加上松弛变量大于等于1,约束条件变为:

同时,对每个松弛变量 $\xi_i$,支付一个代价 $\xi_i$,目标函数由原来的 $ \frac { 1 } { 2 } | w | ^ { 2 } $ 变成

这里, $C>0$ 称为惩罚参数,一般由应用问题决定, $C$ 值大时对误分类的惩罚增大, $C$ 值小时对误分类的惩罚减小。上式包含两层含义:使 $ \frac { 1 } { 2 } | w | ^ { 2 } $ 尽量小即间隔尽量大,同时使误分类点的个数尽量小, $C$ 是调和二者的系数。

上述原始问题是一个凸二次规划问题,因而关于 $ ( w , b , 5 ) $ 的解是存在的。可以证明 $w$ 的解是唯一的,但 $b$ 的解不唯一, $b$ 的解存在于一个区间。(然而没有给出证明)

得到分离超平面:

分类决策函数:

称为线性支持向量机(没说线性可分)。

1.5.1 学习的对偶算法

(1) 选择惩罚参数 $C>0$ ,构造并求解凸二次规划问题

求得最优解 $ \alpha ^ { \ast } = \left( \alpha _ { 1 } ^ { \ast } , \alpha _ { 2 } ^ { \ast } , \cdots , \alpha _ { N } ^ { \ast } \right) ^ { \mathrm { T } } $

(2) 计算 $ w ^ { \ast } = \sum _ { i = 1 } ^ { N } \alpha _ { i } ^ { \ast } y _ { i } x _ { i } $

选择 $ \alpha ^ { \ast } $ 的一个分量 $ \alpha _ { j } ^ { \ast } $ 适合条件 $ 0 < \alpha _ { j } ^ { \ast } < C $,计算

(3) 求得分离超平面

分离超平面:

分类决策函数:

1.5.2 支持向量

在线性不可分的情况下,将对偶问题的解 $ \alpha ^ { \ast } = \left( \alpha _ { 1 } ^ { \ast } , \alpha _ { 2 } ^ { \ast } , \cdots , \alpha _ { N } ^ { \ast } \right) ^ { T } $中对应于 $ \alpha _ { i } ^ { \ast } > 0 $ 的样本点的实例 $x_i$ ,称为支持向量(软间隔的支持向量)。

这时的支持向量要比线性可分时的情况复杂一些。图中,分离超平面由实线表示,间隔边界由虚线表示,正例点由“。”表示,负例点由“X”表示。图中还标出了实例 $x_i$ 到间隔边界的距离 $ \frac { \xi _ { i } } { | w | } $。

软间隔的支持向量 $x_i$ 或者在间隔边界上,或者在间隔边界与分离超平面之间,或者在分离超平面误分一侧。若 $ \alpha _ { i } ^ { \ast } < C $,则 $ \xi _ { i } = 0 $,支持向量 $x_i$ 恰好落在间隔边界上;若$ \alpha _ { i } ^ { \ast } = C , 0 < \xi _ { i } < 1 $,则分类正确,$x_i$ 在间隔边界与分离超平面之间;若 $ \alpha _ { i } ^ { \ast } = C , \quad \xi _ { i } = 1 $,则 $x_i$ 在分离超平面上;若 $ \alpha _ { i } ^ { \ast } = C , \xi _ { i } > 1 $,则 $x_i$ 位于分离超平面误分一侧。

1.5.3 合页损失函数

对于线性支持向量机学习来说,其模型为分离超平面 $ w ^ { \ast } \cdot x + b ^ { \ast } = 0 $ 及决策函数 $ f ( x ) = \operatorname { sign } \left( w ^ { \ast } \cdot x + b ^ { \ast } \right) $,其学习策略为软间隔最大化,学习算法为凸二次规划。线性支持向量机学习还有另外一种解释,就是最小化以下目标函数

目标函数的第 1 项是经验损失或经验风险,函数

称为合页损失函数(hinge loss function)。下标 “$+$” 表示以下取正值的函数。

这就是说,当样本点 $ \left( x _ { i } , y _ { i } \right) $ 被正确分类且函数间隔(确信度)$ y _ { i } \left( w \cdot x _ { i } + b \right) $大于 1 时,损失是 0,否则损失是 $ 1 - y _ { i } \left( w \cdot x _ { i } + b \right) $

注意到在图中的实例点 $x_4$ 被正确分类,但损失不是0。目标函数的第 2 项是系数为 $\lambda$ 的 $w$ 的 $L2$ 范数,是正则化项。

定理 7.4 线性支持向量机原始最优化问题:

等价于最优化问题

证明: 令

则 $ y _ { i } \left( w \cdot x _ { i } + b \right) \geq 1 $,于是 $ \mathbf { w } , \mathbf { b } , \mathbf { \xi } _ { i } $ 满足约束条件 $ y _ { i } \left( w \cdot x _ { i } + b \right) \geq 1 - \xi _ { i } $ 和 $ \xi _ { i } \geq 0 $,由式 $1 - y _ { i } \left( w \cdot x _ { i } + b \right) = \xi _ { i } , \quad \xi _ { i } \geq 0$ 有 $ \left[ 1 - y _ { i } \left( w \cdot x _ { i } + b \right) \right] _ { + } = \left[ \xi _ { i } \right] _ { + } = \xi _ { i } $,所以最优化问题 $ \min _ { w , b } \sum _ { i = 1 } ^ { N } \left[ 1 - y _ { i } \left( w \cdot x _ { i } + b \right) \right] _ { + } + \lambda | w | ^ { 2 } $ 可以写成

若取 $ \lambda = \frac { 1 } { 2 C } $,则

等价

图中还画出0-1损失函数,可以认为它是二类分类问题的真正的损失函数,而合页损失函数是0-1损失函数的上界。由于0-1损失函数不是连续可导的,直接优化由其构成的目标函数比较困难,可以认为线性支持向童机是优化由0-1损失函数的上界(合页损失函数)构成的目标函数。这时的上界损失函数又称为代理损失函数(surrogate loss function)。

横轴是函数间隔 $ y ( w \cdot x + b ) $,纵轴是损失函数 $ \left[ y _ { i } \left( w \cdot x _ { i } + b \right) \right] _ { + } $,被正确分类时,损失是 0,否则损失是 $ - y _ { i } \left( w \cdot x _ { i } + b \right) $相比之下,合页损失函数不仅要分类正确,而且确信度足够高时损失才是0。也就是说,合页损失函数对学习有更高的要求。

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

对解线性分类问题,线性分类支持向量机是一种非常有效的方法。但是,有时分类问题是非线性的,这时可以使用非线性支持向量机。本节叙述非线性支持向量机,其主要特点是利用核技巧(kernel trick)。为此,先要介绍核技巧。核技巧不仅应用于支持向量机,而且应用于其他统计学习问题。

1.6.1 非线性分类问题

非线性问题往往不好求解,所以希望能用解线性分类问题的方法解决这个问题。所采取的方法是进行一个非线性变换,将非线性问题变换为线性问题,通过解变换后的线性问题的方法求解原来的非线性问题。如图右边所示的例子,通过变换,将左图中椭圆变换成右图中的直线,将非线性分类问题变换为线性分类问题。

设原空间为 $\mathcal { X } \subset \mathbf { R } ^ { 2 } , x = \left( x ^ { ( 1 ) } , x ^ { ( 2 ) } \right) ^ { \mathrm { T } } \in \mathcal { X }$,新空间为 $\mathcal { Z } \subset \mathbf { R } ^ { 2 } , z = \left( z ^ { ( 1 ) } , z ^ { ( 2 ) } \right) ^ { T } \in \mathcal { Z }$,定义从原空间到新空间的变换(映射):

经过变换 $ z = \phi ( x ) $,原空间 $ z = \phi ( x ) $ 变换为新空间 $ \mathcal { Z } \subset \mathbf { R } ^ { 2 }$ ,原空间中的椭圆

变换成为新空间中的直线

在变换后的新空间里,直线 $ w _ { 1 } z ^ { ( 1 ) } + w _ { 2 } z ^ { ( 2 ) } + b = 0 $ 可以将变换后的正负实例点正确分开。这样,原空间的非线性可分问题就变成了新空间的线性可分问题。

上面的例子说明,用线性分类方法求解非线性分类问题分为两步:首先使用一个变换将原空间的数据映射到新空间:然后在新空间里用线性分类学习方法从训练数据中学习分类模型。核技巧就属于这样的方法。

核技巧应用到支持向量机,其基本想法就是通过一个非线性变换将输入空间(欧氏空间 $R^n$ 或离散集合)对应于一个特征空间(希尔伯特空间$ \mathcal { H } $),使得在输入空间 $R^n$ 中的超曲面模型对应于特征空间 $ \mathcal { H } $ 中的超平面模型(支持向量机)。这样,分类问题的学习任务通过在特征空间中求解线性支持向量机就可以完成。

1.6.2 核函数的定义

定义(核函数) 设$\mathcal { X }$ 是输入空间(欧氏空间 $R^n$ 的子集或离散集合),又设$ \mathcal { H } $为特征空间(希尔伯特空间),如果存在一个从$R^n$ 到 $ \mathcal { H } $的映射

使得对所有 $ x _ { , } z \in \mathcal { X } $,函数 $ K ( x , z ) $ 满足条件

则称 $ K ( x , z ) $ 为核函数,$\phi(x)$ 为映射函数,式中 $ \phi ( x ) \cdot \phi ( z ) $ 为 $ \phi ( x ) $ 和 $ \phi ( z ) $ 的内积。

核技巧的想法是,在学习与预测中只定义核函数 $ K ( x , z ) $, 而不显式地定义映射函数 $\phi$。通常,直接计算 $ K ( x , z ) $ 比较容易,而通过 $\phi(x)$ 和 $\phi(z)$ 计算并不容易。注意,$\phi$ 是输入空间到特征空间的映射,特征空间通常是高维的,甚至是无穷维的。可以看到,对于给定的核函数 $ K ( x , z ) $,这种映射的取法并不唯一,可以取不同的特征空间,即便是在同一特征空间里也可以取不同的映射。

1.6.3 核技巧在支持向量机中的应用

我们注意到在线性支持向量机的对偶问题中,无论是目标函数还是决策函数(分离超平面)都只涉及输入实例与实例之间的内积。在对偶问题的目标函数$ \min _ { a } \frac { 1 } { 2 } \sum _ { i = 1 } ^ { N } \sum _ { j = 1 } ^ { N } \alpha _ { i } \alpha _ { j } y _ { i } y _ { j } \left( x _ { i } \cdot x _ { j } \right) - \sum _ { i = 1 } ^ { N } \alpha _ { i } $ 中的内积 $ x _ { i } \cdot x _ { j } $ 可以用核函数 $ x _ { i } \cdot x _ { j } $ 来代替,此时对偶问题的目标函数成为

同样,分类决策函数中的内积也可以用核函数代替,而分类决策函数式成为

这等价于经过映射函数 $\phi$ 将原来的输入空间变换到一个新的特征空间,将输入空间中的内积 $ x _ { i } \cdot x _ { j } $ 变换为特征空间中的内积 $ \phi \left( x _ { i } \right) \cdot \phi \left( x _ { j } \right) $ ,在新的特征空间里从训练样本中学习线性支持向量机。当映射函数是非线性函数时,学习到的含有核函数的支持向量机是非线性分类模型。

也就是说,在核函数 $K(x,z)$ 给定的条件下,可以利用解线性分类问题的方法求解非线性分类问题的支持向量机。学习是隐式地在特征空间进行的,不需要显式地定义特征空间和映射函数。这样的技巧称为核技巧,它是巧妙地利用线性分类学习方法与核函数解决非线性问题的技术。在实际应用中,往往依赖领域知识直接选择核函数,核函数选择的有效性需要通过实验验证。

1.6.4 正定核

接下来的内容涉及到大量泛函分析的背景知识,还没有学习过,书上说的我难以理解,这部分先略过。

如何判断核函数 $K(x,z)$ 是不是核函数,也就是说核函数要满足什么条件参数核函数。

正定核的充要条件

$ K ( x , z ) $ 是定义在 $ K ( x , z ) $ 上的对称函数,如果对任意 $x_i \in \mathcal { X }, \quad i=1,2,…,m$,$K(x,z)$ 所对应的 Gram 矩阵

$ K = \left[ K \left( x _ { i } , x _ { j } \right) \right] _ { m \times n } $ 是半正定矩阵,则称 $ K ( x , z ) $ 是正定核。

这一定义在构造核函数时很有用。但对于一个具体函数 $K(x,z)$ 来说,检验它是否为正定核函数并不容易,因为要求对任意有限输入集 $\{x_1,x_2,…,x_m\}$ 验证 $K(x,z)$ 对应的 Gram 矩阵是否为半正定的。在实际问题中往往应用已有的核函数。另外,由 Mercer 定理可以得到Mercer核(Mercer Kernel),正定核比Mercer核更具一般性。下面介绍一些常用的核函数。

1.6.5 常用核函数

1、多项式核函数(polynomial kernel function)

对应的支持向量机是一个p次多项式分类器。在此情形下,分类决策函数成为

2、高斯核函数(Gaussian kernel function)

对应的支持向量机是高斯径向基函数(radial basis function)分类器(rbf)。

3.字符串核函数(string kernel function)

核函数不仅可以定义在欧氏空间上,还可以定义在离散数据的集合上。比如,字符串核是定义在字符串集合上的核函数。字符串核函数在文本分类、信息检索、生物信息学等方面都有应用。

略。

1.7 SMO 序列最小最优化算法

支持向量机的学习问题可以形式化为求解凸二次规划问题。这样的凸二次规划问题具有全局最优解,并且有许多最优化算法可以用于这一问题的求解。但是当训练样本容量很大时,这些算法往往变得非常低效,以致无法使用。所以,如何高效地实现支持向量机学习就成为一个重要的问题。目前人们已提出许多快速实现算法。本节讲述其中的序列最小最优化(sequential minimal optimisation,SMO)算法,这种算法1998年由Platt提出。

SMO(Sequential Minimal Optimization)是针对求解 SVM 问题的Lagrange对偶问题,一个二次规划式,开发的高效算法。传统的二次规划算法的计算开销正比于训练集的规模,而 SMO 基于问题本身的特性(KKT条件约束)对这个特殊的二次规划问题的求解过程进行优化。对偶问题中我们最后求解的变量只有Lagrange乘子 $\vec \alpha $ 向量,这个算法的基本思想就是每次都只选取一对 $(\alpha_i,\alpha_j)$,固定 $\vec \alpha$ 向量其他维度的元素的值,然后进行优化,直至收敛。

SMO算法要解如下凸二次规划的对偶问题:

在这个问题中,变量是拉格朗日乘子,一个变量对应于一个样本点$ \left( x _ { i } , y _ { i } \right) $,变量的总数等于训练样本容量 N。

SMO算法是一种启发式算法,其基本思路是:如果所有变量的解都满足此最优化问题的KKT条件(Karush-Kuhn-Tuckerconditions),那么这个最优化问题的解就得到了。因为KKT条件是该最优化问题的充分必要条件。否则,选择两个变量,固定其他变量,针对这两个变量构建一个二次规划问题。这个二次规划问题关于这两个变量的解应该更接近原始二次规划问题的解,因为这会使得原始二次规划问题的目标函数值变得更小。重要的是,这时子问题可以通过解析方法求解,这样就可以大大提高整个算法的计算速度。子问题有两个变量,一个是违反KKT条件最严重的那一个,另一个由约束条件自动确定。如此,SMO算法将原问题不断分解为子问题并对子问题求解,进而达到求解原问题的目的。

注意,子问題的两个变童中只有一个是自由变量。假设$\alpha_1, \alpha_2$为两个边边路,$\alpha_3,\alpha_4,…\alpha_N$固定,那么由等式约束 $ \sum _ { i = 1 } ^ { N } \alpha _ { i } y _ { i } = 0 $ 可知:

(书上原来的公式可能是错误的,把 y1 放右边去了)

如果 $\alpha_2$ 确定,那么 $\alpha_1$ 也随之确定。所以子问题中同时更新两个变量。

整个SMO算法包括两个部分:求解两个变量二次规划的解析方法选择变量的启发式方法

最终的 SMO 算法如下:

输入:训练数据集 $ T = \{ \left( x _ { 1 } , y _ { 1 } \right) , \left( x _ { 2 } , y _ { 2 } \right) , \cdots , \left( x _ { N } , y _ { N } \right) \} $,其中 $ x _ { i } \in \mathcal { X } = \mathbf { R } ^ { n } ,\quad y_i \in \mathcal { Y } = \{ - 1 , + 1 \} , \quad i = 1,2 , \cdots , N$,精度 $ \varepsilon $。

输出:近似解 $ \hat { \alpha } $

(1)取初始值 $ \alpha ^ { ( 0 ) } = 0 $,令 $k=0$

(2)选取优化变量 $ \alpha _ { 1 } ^ { ( k ) } , \alpha _ { 2 } ^ { ( k ) } $,解析求解两个变量的最优化问题,求得最优解$ \alpha _ { 1 } ^ { ( k + 1 ) } , \alpha _ { 2 } ^ { ( k + 1 ) } $,更新 $\alpha$ 为 $\alpha^{(k+1)}$

(3)若在精度 $ \varepsilon $ 范围内满足停机条件

其中,

则转 (4),否则令 $k=k+1$,转 (2)

(4) 取 $\hat { \alpha } = \alpha ^ { ( k + 1 ) }$


结语

总算把整章节总结完了,花了两天的空余时间,感谢 Mathpix Snipping Tool 帮助转换 Latex 数学公式。