支持向量机（SVM）

支持向量机（SVM）

本文摘录《统计学习方法》

SVM 简介

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

线性可分 SVM 和硬间隔最大化

线性可分 SVM

假设给定一个特征空间上线性可分的训练数据集： $\begin{align} &T={(x_1, y_1),(x_2, y_2),...,(x_N, y_N)} \\ &x_i \in \mathrm{R}^n, ~~~y_i \in \{+1,-1\}, ~~~i=1,2,...,N \end{align}$

其中，$x_i$ 为第 $i$ 个特征向量，$y_i$ 为类标记，当它等于 $+1$ 时为正例；为 $-1$ 时为负例

线性可分 SVM：给定可分训练数据集，通过间隔最大化或等价地求解相应的凸二次规划问题学习得到的分离超平面为： $w^* \cdot x + b^* = 0$ 以及相应的分类决策函数： $f(x) = sign(w^* \cdot x + b^*)$ 称为线性可分 SVM

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

图来源于支持向量机（SVM）——原理篇

函数间隔和几何间隔

函数间隔：对于给定的训练数据 $T$ 和超平面 $(w,b)$，定义超平面 $(w,b)$ 关于样本点 $(x_i,y_i)$ 的函数间隔为： $\hat \gamma_i = y_i(w \cdot x_i + b)$ 定义超平面 $(w,b)$ 关于训练数据集 $T$ 的函数间隔为超平面 $(w,b)$ 关于 $T$ 中所有样本点 $(x_i,y_i)$ 的函数间隔之最小值，即： $\hat \gamma = \min_{i=1,2,...,N} \hat \gamma_i$

函数间隔可以表示分类预测的正确性和确信度。

由于成比例的改变 $w$ 和 $b$，超平面没有变化，但函数间隔会发生改变，故需要对 $w$ 加些约束，如规范化，这时候函数间隔就变成了几何间隔

几何间隔：对于给定的训练数据 $T$ 和超平面 $(w,b)$，定义超平面 $(w,b)$ 关于样本点 $(x_i,y_i)$ 的几何间隔为： $\gamma_i = y_i(\frac{w}{||w||} \cdot x_i + \frac{b}{||w||})$ 定义超平面 $(w,b)$ 关于训练数据集 $T$ 的几何间隔为超平面 $(w,b)$ 关于 $T$ 中所有样本点 $(x_i,y_i)$ 的几何间隔之最小值，即： $\gamma = \min_{i=1,2,...,N} \gamma_i$

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

实际上这个距离就是我们所谓的支持向量到超平面的距离

函数间隔和几何间隔有如下关系： $\gamma_i = \frac{\hat \gamma_i}{||w||} \\ \gamma = \frac{\hat \gamma}{||w||}$

间隔最大化

间隔最大化：对训练数据集找到的集合间隔最大的超平面意味着已充分大的确信度对训练数据进行分类

根据以上定义，SVM 模型的求解最大分割超平面问题可以表示为以下约束最优化问题： $\begin{align} &\max_{w,b} \gamma \\ &s.t. ~~y_i(\frac{w}{||w||} \cdot x_i + \frac{b}{||w||}) \geqslant \gamma, ~~i = 1, 2, ..., N \end{align}$

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

考虑几何间隔和函数间隔的关系式，可改写为： $\begin{align} &\max_{w,b} \frac{\hat \gamma}{||w||} \\ &s.t. ~~y_i(w \cdot x_i + b) \geqslant \hat \gamma, ~~i = 1, 2, ..., N \end{align}$ 函数间隔 $\hat \gamma$ 的取值并不影响最优化问题的解，所有可以取 $\hat \gamma = 1$，代入方程，由于最大化 $\frac{1}{||w||}$ 和最小化 $\frac{1}{2} ||w||^2$ 是等价的，故可以化简为凸二次规划问题（convex quadratic programming）： $\begin{align} &\min_{w,b} \frac{1}{2} ||w||^2 \\ &s.t. ~~y_i(w \cdot x_i + b) - 1 \geqslant 0, ~~i = 1, 2, ..., N \end{align}$

凸优化问题指约束最优化问题： $\begin{align} \min_w ~&f(w) \\ s.t. ~~ &g_i(w) \leqslant 0, ~~i = 1,2,...,k \\ &h_i(w) = 0, ~~i=1,2,...,l \end{align}$ 其中，目标函数 $f(w)$ 和约束函数 $g_i(w)$ 都是 $\mathrm{R}^n$ 上连续可微的凸函数，约束函数 $h_i(w)$ 是 $\mathrm{R}^n$ 上仿射函数（满足$h(w)=a \cdot w + b$）

线性可分 SVM 学习算法 – 最大间隔法

输入：线性可分训练数据集： $T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\} \\ x_i \in \mathrm{R}^2, y_i \in \{-1,+1\}, ~~i=1,2,...,N$

输出：最大间隔分离超平面和分类决策函数

构造并求解约束最优化问题： $\begin{align} &\min_{w,b} \frac{1}{2} ||w||^2 \\ &s.t. ~~y_i(w \cdot x_i + b) - 1 \geqslant 0, ~~i = 1, 2, ..., N \end{align}$

由此得到分离超平面： $w^* \cdot x + b^* = 0$ 分类决策函数： $f(x) = sign(w^* \cdot x + b^*)$

$sign$ 函数是符号函数，功能是取某个数的符号。逻辑回归中用 $sigmoid$ 函数实现

支持向量和间隔边界

在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量（support vector）

支持向量是使约束条件式等号成立的点，即： $y_i(w \cdot x_i + b) - 1 = 0$ 对于 $y_i = +1$ 的正例点，支持向量在超平面： $H_1:w \cdot x + b = 1$ 对于 $y_i=-1$ 的负例点，支持向量在超平面： $H_2:w \cdot x + b = -1$ 即在 $H_1,H_2$ 上的点就是支持向量，$H_1,H_2$ 之间的距离称为间隔（margin），$H_1,H_2$ 称为间隔边界，间隔等于 $\frac{2}{||w||}$。在决定分离平面时只有支持向量起作用。

学习的对偶算法

todo

线性 SVM 和软间隔最大化

线性 SVM

给定一个特征空间上的训练数据集： $\begin{align} &T = \{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\} \\ &x_i \in \mathrm{R}^n, ~~~y_i \in \{+1,-1\}, ~~~i=1,2,...,N \end{align}$

其中，$x_i$ 为第 $i$ 个特征向量，$y_i$ 为 $x_i$ 的类标记

假设训练数据集中不是线性可分的，有一些特异点（outlier），将这些特异点去掉，剩下大部分的样本点组成的集合时线性可分的。

线性不可分意味着某些样本点 $(x_i, y_i)$ 不能满足函数间隔大于等于 $1$ 的约束条件，所有可以对每个样本点 $(x_i,y_i)$ 引进一个松弛变量 $\varepsilon_i \geqslant 0$，使函数间隔加上松弛变量大于等于 $1$，即：

\[y_i(w \cdot x_i + b) \geqslant 1-\varepsilon_i\]
同时，对每个松弛变量 $\varepsilon_i$，支付一个代价 $\varepsilon_i$。目标函数从原来的 $\frac{1}{2}||w||^2$ 变成： $\frac{1}{2} ||w||^2 + C \sum_{i=1}^{N} \varepsilon_i$

其中，$C > 0$ 称为惩罚参数，一般由应用问题决定，$C$ 值大时对误分类的惩罚增大，$C$ 值小时对误分类的惩罚增小

线性不可分的线性 SVM 的学习问题变成如下凸二次规划问题： $\begin{align} \min_{w,b,\zeta} &\frac{1}{2} ||w||^2 + C \sum_{i=1}^N \varepsilon_i \\ s.t. ~~&y_i(w \cdot x_i + b) \geqslant 1 - \varepsilon_i, ~~i = 1, 2, ..., N \\ & \varepsilon_i \geqslant 0, ~~i = 1, 2, ..., N \end{align}$

2.也可以在优化的目标函数里增加一个对特异点的惩罚项，最常用的是 $hinge$ 函数： $l_{hinge}(z) = max(0,1-z)$ 即若样本点满足约束条件损失就是 $0$，否则损失就是 $1-z$，则优化目标变成： $\begin{align} &\min_{w,b} \frac{1}{2} ||w||^2 + C \sum_{i=1}^n max(0,1-y_i(w \cdot x_i + b)) \\ &s.t. ~~y_i(w \cdot x_i + b) \geqslant 1 \end{align}$

惩罚参数 $C$

对于不同的惩罚参数 $C$，SVM 结果如下：

本小段来源于看了这篇文章你还不懂SVM你就来打我

原始目标函数： $\min_{w,b,\zeta} \frac{1}{2}||w||^2 + C \sum_{i=1}^n \varepsilon_i$ 可抽象为： $\min_f \Omega(f) + C \sum_{i=1}^n l(f(x_i),y_i)$ 前一项可理解为“结构风险（structural risk）”，用来描述所求模型的某些性质（SVM就是要求间隔最大）；第二项称为“经验风险（empirical risk）”，用来描述模型与训练数据的契合程度（即误差）。而参数 $C$ 就是用于对二者的折中，即我们一方面要求模型要满足某种性质另一方面又想使模型与训练数据很契合。

从正则化角度来讲，$\Omega(f)$ 称为正则化项，$C$ 称为惩罚参数，$C$ 值大时对误分类的惩罚增大（要求模型对训练模型更契合），这可能会存在过拟合；$C$ 值小时对误分类的惩罚增小，即相对更加看重正则化项，此时可能存在欠拟合。

学习的对偶算法

todo

支持向量

todo

合页损失函数

todo

非线性 SVM 和核函数

前面介绍的都是线性问题，但是我们经常会遇到非线性的问题(例如异或问题)，此时就需要用到核技巧（kernel trick）将线性支持向量机推广到非线性支持向量机。需要注意的是，不仅仅是 SVM，很多线性模型都可以用核技巧推广到非线性模型，例如核线性判别分析（KLDA）

核技巧

用线性可分方法求解非线性分类问题分为两步：首先使用一个变换将原空间的数据映射到新空间；然后在新空间里用线性分类学习方法从训练数据中学习分类模型

图来源于看了这篇文章你还不懂SVM你就来打我

核技巧应用到 SVM，其基本思想就是通过一个非线性变换将输入空间（欧氏空间 $\mathrm{R}^2$ 或离散集合）对应于一个特征空间（希尔伯特空间 $\mathcal{H}$），使在输入空间 $\mathrm{R}^2$ 中的超曲面模型对应于特征空间 $\mathcal{H}$ 中的超平面模型（SVM）

核技巧的定义：

设 $\mathcal{X}$ 是输入空间（欧氏空间 $\mathrm{R}^n$ 的子集或离散集合），又设 $\mathcal{H}$ 为特征空间（希尔伯特空间），如果存在一个从 $\mathcal{X}$ 到 $\mathcal{H}$ 的映射： $\phi(x):\mathcal{X} \to \mathcal{H}$ 使得对所有的 $x,z \in \mathcal{X}$，函数 $K(x,z)$ 满足条件： $K(x,z) = \phi(x) \cdot \phi(z)$ 则称 $K(x,z)$ 为核函数，$\phi(x)$ 为映射函数，式中 $\phi(x) \cdot \phi(z)$ 为两者内积（Inner product）

核技巧的想法是，在学习和预测中只定义核函数 $K(x,z)$，而不显示地定义映射函数 $\phi$，这样计算比较容易。可以看到，对于给定的核 $K(x,z)$，特征空间 $\mathcal{H}$ 核映射函数 $\phi$ 的取法不唯一，可以取不同的特征空间，即便在同一特征空间里也可以取不同的映射

核技巧在 SVM 中的应用

todo

正定核

充要条件证明

todo

常用核函数

多项式核函数：

\[K(x,z) = (x \cdot z + 1)^p\]
对应的 SVM 是一个 $p$ 次多项式分类器。在此情况下，分类决策函数称为： $f(x)=sign(\sum_{i=1}^{N_s} a_i^* y_i (x_i \cdot x + 1)^p + b^*)$

高斯核函数：

\[K(x,z) = exp(-\frac{||x-z||^2}{2\sigma^2})\]
对应的 SVM 是高斯径向基函数分类器。在此情况下，分类决策函数称为： $f(x)=sign(\sum_{i=1}^{N_s} a_i^* y_i exp(-\frac{||x-z||^2}{2\sigma^2}) + b^*)$

字符串核函数：

todo

非线性 SVM

todo

序列最小最优算法（SMO）

todo

总结

任何算法都有其优缺点，支持向量机也不例外。

支持向量机的优点是:

由于SVM是一个凸优化问题，所以求得的解一定是全局最优而不是局部最优。

不仅适用于线性线性问题还适用于非线性问题(用核技巧)。

拥有高维样本空间的数据也能用SVM，这是因为数据集的复杂度只取决于支持向量而不是数据集的维度，这在某种意义上避免了“维数灾难”。

理论基础比较完善(例如神经网络就更像一个黑盒子)。

支持向量机的缺点是:

二次规划问题求解将涉及m阶矩阵的计算(m为样本的个数), 因此SVM不适用于超大数据集。(SMO算法可以缓解这个问题)

只适用于二分类问题。(SVM的推广SVR也适用于回归问题；可以通过多个SVM的组合来解决多分类问题)

本小节来源于看了这篇文章你还不懂SVM你就来打我