第六章 支持向量机 Support Vector Machine

SVM原理、核技巧

6.1 最大间隔分类器

引子

线性模型：在样本空间中寻找一个超平面, 将不同类别的样本分开.

Q:将训练样本分开的超平面可能有很多, 哪一个好呢?
A:应选择”正中间”, 容忍性好, 鲁棒性高, 泛化能力最强.

间隔

如何把间隔 γ 表示为 w 的函数？

假设线性可分。超平面将训练样本分成了2类：

$$\{\begin{array}{cc}{w}^{\mathrm{T}}{x}_i+b⩾+1,& y_i=+1\\ w^{\mathrm{T}}{x}_i+b⩽-1,& y_i=-1\end{array}$$

距离超平面最近的训练样本点使等号成立。

间隔与支持向量

★支持向量机 (SVM)

SVM原理：SVM学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。比如：$\mathbf{w}\cdot x+b=0$ 即为分离超平面，对于线性可分的数据集来说，这样的超平面有无穷多个（即感知机），但是几何间隔最大的分离超平面却是唯一的。

支持向量机 (Support Vector Machine, SVM) 是 Cortes 和 Vapnik 于1995 年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其它机器学习问题中 。

支持向量机方法是建立在统计学习理论的 VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷，以期获得最好的推广能力（或称泛化能力）。

3 个关键想法：

• 通过优化来求解（一个超平面）

• 寻找最大间隔分类器来提高模型的泛化能力

• 采用核技巧使得在高维特征空间的计算更有效率

结构风险最小化

(Vapnik , 1995, "Structural Risk Minimization Principle")

结构风险：经验风险 + 置信风险

提高样本数量，降低 VC 维 ，从而降低置信风险。

VC 维

VC维等于可以分开的最多样本数，d维度空间的超平面的VC维为d+1，最小化VC维==>最大化间隔

（函数空间复杂度的⼀个度量）

VC维（ Vapnik Chervonenkis 维度）是衡量可以通过统计分类算法学习的函数空间的容量（复杂度， 表现力或 灵活性）的度量。它被定义为算法 可以打散的 最大点集 的大小。

d 维度空间的超平面的 VC 维为 d+1

3 个点共有 8 种标记方法

VC 维与间隔

线性分类器是一大簇函数，VC 维 h = d+1

我们是否可以通过限制来减小它的VC 维？

限制线性分类器对一个球体内的数据进行分类

间隙容忍分类器：一个线性分类器，其 活动被限制在一个球体内和间隔之外。

当间隔 M 相对于球体直径 D 比较小时，仍然可以打散 3 个点。

但是，当间隔 M 增大后，只能打散 2 个点。

对于分类平面，增大间隔 M ，可以减小 VC 维度。

间隙容忍分类器的 VC 维 h 满足：

$$h\le \min \left\{ceil\right[\frac{D^2}{M^2}],d\}+1$$

通常情况下，数据是有界的（D 是固定的），增大间隔 M 可以减小 VC 维，从而提高泛化能力。

6.2 对偶问题

支持向量机基本型

学习一个基于间隔的分类器：

最大间隔: 寻找参数w和b, 使得γ最大.

支持向量机的原问题、凸二次优化

支持向量机的对偶问题：拉格朗日乘子法

第一步：引入拉格朗日乘子 ${\alpha }_i\ge 0$ 得到拉格朗日函数

$$L(\mathbf{w},b,\mathbf{\alpha })=\frac{1}{2}\Vert \mathbf{w}{\Vert }^2-\sum _{i=1}^m{\alpha }_i\left(y_i({\mathbf{w}}^{\top }{\mathbf{x}}_i+b)-1\right)$$

第二步：令 $L(\mathbf{w},b,\mathbf{\alpha })$ 对 $\mathbf{w}$ 和 $b$ 的偏导为零可得

$$\begin{gathered} \mathbf{w}=\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i \\ \sum _{i=1}^m{\alpha }_i{y}_i=0. \end{gathered}$$

第三步：回代

支持向量机的对偶问题没有对偶间隙，更容易解，稀疏解

解的稀疏性

最终模型：$f(\mathbf{x})={\mathbf{w}}^{\top }\mathbf{x}+b={\sum }_{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i^{\top }\mathbf{x}+b$

KKT条件：

$$\{\begin{array}{l}{\alpha }_i\ge 0,\\ y_{i}f({\mathbf{x}}_i)\ge 1,\\ {\alpha }_i(y_{i}f({\mathbf{x}}_i)-1)=0.\end{array}$$

$$y_{i}f({\mathbf{x}}_i)>1\stackrel{互补松弛条件}{}{\alpha }_i=0$$

支持向量机解的稀疏性: 训练完成后, 大部分的训练样本都不需保留, 最终模型仅与支持向量有关.

支持向量

超平面法向量是支持向量的线性组合

支持向量是对应α不为零训练样本点

解的性质

6.3 ★核技巧

线性不可分情形：映射到高维空间

对于线性不可分的样本怎么办？
如何找到正确的分类曲线和曲面对此类情况分类?

关键点 : 把 $x_i$ 变换到高维的特征空间

为什么要变换？使得样本在高维的特征空间里变得线性可分的
通过加入（一个）新的特征xi，使得样本变成线性可分的，此时特征空间维数变高

Transform $x\to \varphi (x)$

数据变换

1维到2维

2维到3维

核技巧思想

核技巧：一般特征空间是高维或者无穷维的，因此很难去定义一个特征空间以及输入空间到这个特征空间的映射，核技巧的想法是，在学习和预测中只定义核函数 K(x,z)，而不显式地定义特征空间和映射，简化计算难度。

总的来说，在核函数 $K(x,z)$ 给定的条件下，可以利用解线性分类问题的方法求解非线性分类问题，学习是隐式地在特征空间进行，不需要显式地定义特征空间和映射，这样的技巧叫做核技巧。在实际应用中，往往依赖领域知识直接选择核函数。

特征空间的支持向量机

引入核函数

如何选择到较高维空间的非线性映射？给定的检验元组，必须计算与每个支持向量的点积，出现形如 $\varphi (X_i)\cdot \varphi (X_j)$ 可以引入核函数（内积）来替代

$K(X_i,X_j)=\varphi (X_i{)}^T\cdot \varphi (X_j)$

基本想法：不显式地设计核映射, 而是设计核函数.

$$\kappa ({\mathbf{x}}_i,{\mathbf{x}}_j)=\varphi ({\mathbf{x}}_i{)}^{\top }\varphi ({\mathbf{x}}_j)$$

如何选择到较高维空间的非线性映射？

在上述对偶问题和模型预测时，必须计算样本间的点积，出现形如 $\varphi ({\mathbf{x}}_i{)}^{\top }\varphi ({\mathbf{x}}_j)$，可以引入核函数来替代：

$$\kappa ({\mathbf{x}}_i,{\mathbf{x}}_j)=\varphi ({\mathbf{x}}_i{)}^{\top }\varphi ({\mathbf{x}}_j)$$

采用核函数的优点：

• 不需要知道和计算 $\varphi ()$。

• 即使特征空间的维度非常高，计算仍然是可行的，因为核函数是在原空间运算。

核构造

⼀种⽅法是选择⼀个特征空间映射ϕ(x)，然后使⽤这个映射寻找对应的核

另⼀种⽅法是直接构造核函数

Mercer 核

Mercer定理(充分非必要)：只要一个对称函数所对应的核矩阵半正定, 则它就能作为核函数来使用.

非线性分类

需要求解的最优化问题

$$\begin{array}{rl}\underset{\alpha }{\min }& \frac{1}{2}\sum _{i=1}^l\sum _{j=1}^l{y}_i{y}_j{\alpha }_i{\alpha }_j\left(\varphi (x_i{)}^T\cdot \varphi (x_j)\right)-\sum _{j=1}^l{\alpha }_j\\ s.t.& \sum _{i=1}^1{y}_i{\alpha }_i=0\\ & 0\le {\alpha }_{{}_1}\le C,i=1,\cdots l\end{array}$$

最后得到决策函数

$$f(x)=\text{sgn}((w^{\ast }\cdot \varphi (x))+b^{\ast })$$

或

$$f(x)=\mathrm{sgn}(\sum _{i=1}^l{y}_i{\alpha }_i(\varphi (x_i{)}^T\cdot \varphi (x))+b^{\ast })$$

实现非线性分类的思想

给定训练集后，决策函数仅依赖于 $K(x_i,x_j)=((x_i\cdot x_j)+1{)}^2$，而不需要再考虑非线性变换 $\varphi (x)$。

如果想用其它的非线性分划办法，则可以考虑选择其它形式的函数 $K(x_i,x_j)$，一旦选定了函数，就可以求解最优化问题。

解得 ${\alpha }^{\ast }=({\alpha }_1^{\ast },\cdots {\alpha }_l^{\ast }{)}^T$， 而决策函数

$$f(x)=\text{sgn}(\sum _{i=1}^l{y}_i{\alpha }_{i}K(x_i,x_j))+b^{\ast })$$

其中

$$\begin{array}{r}{b}^{\ast }=y_j-\sum _{i=1}^l{y}_i{\alpha }_{i}K(x_i,x_j),j\in \{j|0<{\alpha }_j^{\ast }<C\}\end{array}$$

$K(x_i,x_j)$ - 核函数

核函数的选择

常用核函数：

目前研究最多的核函数主要有三类：

多项式内核 polynomial kernel

$K(x,x_i)=[(x\cdot x_i)+c{]}^q$

得到q 阶多项式分类器

高斯径向基函数内核RBF

$K\left(x,x_i\right)=\exp \left\{-\frac{{|x-x_i|}^2}{{\sigma }^2}\right\}$

每个基函数中心对应一个支持向量，它们及输出权值由算法自动确定

Sigmoid 内核

$K(x,x_i)=\tanh (\omega (x\cdot x_i)+c)$

包含一个隐层的多层感知器，隐层节点数是由算法自动确定

例子

现有5个一维数据，$x_1=1,x_2=2,x_3=4,x_4=5,x_5=6$, 其中 1, 2, 6 为 class 1；4, 5 为class 2 ，即 $y_1=1,y_2=1,y_3=-1,y_4=-1,y_5=1$。

选择 polynomial kernel of degree 2

• $K(x,y)=(xy+1{)}^2$
• $C=100$

求解 ${\alpha }_i(i=1,\dots ,5)$

$$\text{max.}\sum _{i=1}^5{\alpha }_i-\frac{1}{2}\sum _{i=1}^5\sum _{j=1}^5{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i{x}_j+1{)}^2$$

$$\text{subject to }100\ge {\alpha }_i\ge 0,\sum _{i=0}^5{\alpha }_i{y}_i=0$$

通过二次规划求解，得到

$${\alpha }_1=0,{\alpha }_2=2.5,{\alpha }_3=0,{\alpha }_4=7.333,{\alpha }_5=4.833$$

支持向量为 $x_2=2,x_4=5,x_5=6$

判别函数为

$$\begin{array}{rl}f(z)& =2.5(1)(2z+1{)}^2+7.333(-1)(5z+1{)}^2+4.833(1)(6z+1{)}^2+b\\ & =0.6667z^2-5.333z+b\end{array}$$

$b$ 满足 $f(2)=1,f(5)=-1,f(6)=1$, 得到 $b=9$

$$f(z)=0.6667z^2-5.333z+9$$

结果：判别函数

6.4 软间隔分类器

软间隔

-Q: 现实中, 很难确定合适的核函数使得训练样本在特征空间中线性可分; 同时一个线性可分的结果也很难断定是否是有过拟合造成的.

-A: 引入”软间隔”的概念, 允许支持向量机在一些样本上不满足约束.

0/1损失函数

基本想法：最大化间隔的同时, 让不满足约束的样本应尽可能少.

$$\underset{\mathbf{w},b}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+C\sum _{i=1}^m{l}_{0/1}\left(y_i({\mathbf{w}}^{\top }\varphi ({\mathbf{x}}_i)+b)-1\right)$$

其中 $l_{0/1}$ 是”0/1损失函数”

$$l_{0/1}=\{\begin{array}{ll}1& z<0\\ 0& otherwise\end{array}$$

存在的问题：0/1损失函数非凸、非连续, 不易优化！

软间隔支持向量机

松弛变量

${\xi }_i=0$ 的数据点被正确分类，要么位于边缘上，要么在边缘的正确⼀侧；
$0<{\xi }_i\le 1$ 的点位于边缘内部，但是在决策边界的正确⼀侧；
${\xi }_i>1$ 的点位于决策边界的错误⼀侧，是被错误分类的点。

采用铰链损失函数的表示

对偶问题

根据KKT条件可推得最终模型仅与支持向量有关, 也即hinge损失函数依然保持了支持向量机解的稀疏性.

正则化视角

支持向量机学习模型的更一般形式

通过替换上面两个部分, 可以得到许多其他学习模型

• 对数几率回归(Logistic Regression)
• 最小绝对收缩选择算子(LASSO)
• ……

替代损失

替代损失函数数学性质较好, 一般是0/1损失函数的上界

Hinge loss vs. 0/1 loss

逻辑回归的损失函数

二分类的损失函数比较

SVM对偶问题总结

6.5 支持向量机vs.逻辑回归

SVM 和正则化的逻辑回归它们的损失函数

可以将两者统一起来

也就是说，它们的区别就在于逻辑回归采用的是 log loss（对数损失函数），svm采用的是

二分类的损失函数比较

6.6 算法与实践

坐标上升算法

坐标上升算法每次通过更新多元函数中的一维，经过多次迭代直到收敛来达到优化函数的目的。
简单的讲就是不断地选中一个变量做一维最优化直到函数达到局部最优点。

例子

序列最小优化算法 SMO

序列最小优化算法 SequenIal Minimal Optimization (SMO): Efficient way of solving the dual problem arising from the derivation of the SVM

SMO的思想类似坐标上升算法，我们需要优化一系列的α的值，每次选择尽量少的α来优化，不断迭代直到函数收敛到最优值。

从上式可以看出，最终需要优化的是n个变量α，一次型优化显然行不通，此时可以采用一种从局部到整体的思路，即先优化其中一部分变量，使这部分变量满足上述KKT条件，然后重复这种思路，直到n个变量α均被优化到满足KKT条件，那么此时的α即为满足条件的最优解，此时问题的关键为我们选几个变量进行优化。

坐标上升法可行？

这个凸二次优化问题的其他求解算法的复杂度很高
但是Platt提出的SMO算法可以高效的求解上述对偶问题
把原始问题的求解N个参数二次规划问题分解成多个二次规划问题求解
每个子问题只需要求解2个参数，节省了时间成本和内存需求

基本思路

基本思路：不断执行如下两个步骤直至收敛.

第一步：选取一对需更新的变量αi和αj.

第二步：固定αi和αj以外的参数, 求解对偶问题更新αi和αj.

仅考虑αi和αj时, 对偶问题的约束变为

用一个变量表示另一个变量, 回代入对偶问题可得一个单变量的二次规划, 该问题具有闭式解.

偏移项 b ：通过支持向量来确定.

具体实现

略

6.7 过拟合

SVM 也会产生过拟合

解决方案

• 选择更合适的参数 $C$（如软间隔）
• 选择一个更好的核函数 $K$
• 选择一个更好的核函数的参数（如 $\delta$）

高斯核参数 σ 的作用

大的 ${\sigma }^2$ 导致欠拟合
小的 ${\sigma }^2$ 导致过拟合

参数 C 在分类中的作用

正则化系数 C 事先设定 , 它定义了模型复杂度与经验损失间的权衡。

当 C 增加时，正则化的作用减弱， SVM 趋向于过拟合 。

例题

核技巧

试说明为什么核技巧（kernel trick）能让我们可以在高维特征空间运用SVM而不显著增加运行时间。

例题1

例题2