支持向量机(SVM)学习笔记

SVM 简介

在机器学习中，支持向量机（SVM，又名支持向量网络）是在分类与回归分析中分析数据的监督式学习模型与相关的学习算法。给定一组训练实例，每个训练实例被标记为属于两个类别中的一个或另一个，SVM 训练算法创建一个将新的实例分配给两个类别之一的模型，使其成为非概率二元线性分类器。

简单点讲，SVM 就是一种二类分类模型，他的基本模型是的定义在特征空间上的间隔最大的线性分类器，SVM 的学习策略就是间隔最大化。

SVM 算法原理

线性可分

以下图为例，可以发现，图中的实线刚好把两种样本一分为二，此时，我们说这两类样本在其特征空间里线性可分。

严格的数学定义是

$D_0$ 和 $D_1$ 是 n 维欧氏空间中的两个点集，如果存在 n 维向量 w 和实数 b，使得所有属于 $D_0$ 的点 $x_i$ 都有 $wx_i+b>0$ ，而对于所有属于 $D_1$ 的点 $x_j$ 则有 $wx_j+b<0$ ，则我们称 $D_0$ 和 $D_1$ 线性可分。

简单的说就是如果用一个线性函数可以将两类样本完全分开，就称这些样本是 “线性可分” 的。

最大间隔超平面

从二维扩展到多维空间中时，将 $D_0$ 和 $D_1$ 完全正确地划分开的 $wx+b=0$ 就成为超平面。

对于线性可分的数据样本来说，我们可以找到无数个超平面将数据集一分为二。

为了使这个超平面更具鲁棒性，我们会去找最佳超平面，以最大间隔把两类样本分开的超平面，也称之为最大间隔超平面。

也就是说，超平面对每个类别最近的元素距离最远。

怎么能找到最大间隔超平面呢？

我们可以先找到两个平行的，能够分离样本的辅助超平面，然后将它们分别推向样本两侧，使得它们之间的距离尽可能大，一直到有至少一个正样本或者负样本通过对应的辅助超平面为止。

支持向量

如图所示，样本中距离超平面最近的一些点，这些点叫做支持向量。

在决定最佳超平面时只有支持向量起作用，而其他数据点并不起作用

SVM 最优化问题

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

$T={(x_1,y_1),(x_2,y_2),\cdots ,(x_n,y_n)}$

其中， $x \in R^n, y\in {+1,-1}$

SVM 希望找到离各类样本点距离最远的超平面，也就是找到最大间隔超平面。任意超平面可以用下面这个线性方程来描述：

$w^Tx+b=0 \tag{1}$

我们知道在二维空间中，点 (x,y) 到直线 $Ax+By+C=0$ 的距离为

$\frac{|Ax+By+C|}{\sqrt{A^2+B^2}} \tag{2}$

扩展到 n 维空间后，点 $x=(x_1,x_2,\cdots,x_n)$ 到 $w^Tx+b=0$ 的距离为：

$\frac{|w^Tx+b|}{\Vert w\Vert} \tag{3}$

其中 $\Vert w\Vert = \sqrt{w_1^2+\cdots+w_n^2}$

根据支持向量的定义我们知道，支持向量到超平面的距离为 d，其他点到超平面的距离大于 d。

于是我们可以得到：

$\begin{cases} \frac{|w^Tx+b|}{\Vert w\Vert} \geq d \quad y = 1 \\ \frac{|w^Tx+b|}{\Vert w\Vert} \leq -d \quad y = -1 \end{cases} \tag{4}$

方程两边除以 d 可以得到：

$\begin{cases} \frac{|w^Tx+b|}{\Vert w\Vert d} \geq 1 \quad y = 1 \\ \frac{|w^Tx+b|}{\Vert w\Vert d} \leq -1 \quad y = -1 \end{cases}\tag{5}$

y 取 1 或者-1，分别代表两个不同的类

由于 $\Vert w\Vert d$ 为正数且都是标量，为了简便计算，我们令 $\Vert w\Vert d = 1$ ，这对目标函数的优化没有影响，因此有：

$\begin{cases} w^Tx+b \geq 1 \quad y = 1 \\ w^Tx+b \leq -1 \quad y = -1 \end{cases}\tag{6}$

将（6）中的两个方程合并，可以得到：

$y(w^Tx+b) \geq 1 \tag{7}$

式（7）就是最大间隔超平面的上下两个超平面。

另一方面，在上述讨论中，我们知道支持向量到超平面的距离：

$d=\frac{|w^Tx+b|}{\Vert w\Vert} \tag{8}$

根据 $y(w^Tx+b) > 1 > 0$ （y 为 1 或 -1）我们同样可以得到：

$y(w^Tx+b) = |w^Tx+b| \tag{9}$

因此根据（8）、（9）两式有：

$d=\frac{y(w^Tx+b)}{\Vert w\Vert} \tag{10}$

之后我们便可以得到目标函数：

$\max 2 * \frac{y(w^Tx+b)}{\Vert w\Vert} \tag{11}$

同时，我们知道对于支持向量 x 有 $y(w^Tx+b)=1$ 那么式（11）可以进一步化简为：

$\max \frac{2}{\Vert w\Vert} \tag{12}$

再进行一个转换，并消除 $\Vert w\Vert$ 的根号，注意两者是等价的问题的实质没有变：

$\min\frac{1}{2}\Vert w\Vert^2 \tag{13}$

式（13）中的系数 1 / 2 仅仅是为了在下面求导时能够消去系数，没有其他特殊意义

最后，我们得到了最优化问题的目标函数和优化条件：

$\min\frac{1}{2}\Vert w\Vert^2 \quad s.t.\quad y_i(w^Tx_i+b) \geq 1 \tag{14}$

对偶问题

上面我们得到了最优化问题的目标函数和优化条件，那么如何对其进行求解呢？可以应用拉格朗日乘子法构造拉格朗日函数，再通过求解其对偶问题得到原始问题的最优解。

对拉格朗日乘子法的具体说明这里不再介绍。

对偶问题来求解的原因是

对偶问题更易求解，由下文知对偶问题只需优化一个变量 α 且约束条件更简单；
能更加自然地引入核函数，进而推广到非线性问题。

我们对每个约束条件添加拉格朗日乘子 α，可以得到该问题的拉格朗日函数：

$L(w,b,\alpha) = \frac{1}{2}\Vert w\Vert^2 - \sum_{i=1}^n \alpha_i(y_i(w^Tx_i+b)-1) \tag{15}$

其中 $\alpha = (\alpha_1,\alpha_2,\cdots,\alpha_n)$ 。

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

$\underset{\alpha}{\max}\underset{w,b}{\min}L(w,b,\alpha)$

令 L 对 w 和 b 的偏导为 0 有：

$\frac{\partial L(w,b,\alpha)}{\partial w} = w - \sum_{i=1}^n \alpha_i y_i x_i = 0 \tag{16}$

$\frac{\partial L(w,b,\alpha)}{\partial b} = - \sum_{i=1}^n \alpha_i y_i = 0 \tag{17}$

由(16)、(17)可以得到：

$w = \sum_{i=1}^n \alpha_i y_i x_i \tag{18}$

$0 = \sum_{i=1}^n \alpha_i y_i \tag{19}$

将式(18)代入式(15)，即可将 L 中的 w 和 b 消去，再考虑式(19)的约束，就可以得到式(14)的对偶问题：

$\begin{aligned} L(w,b,\alpha) & = \frac{1}{2}\Vert w\Vert^2 - \sum_{i=1}^n \alpha_i(y_i(w^Tx_i+b)-1) \\ & = \frac{1}{2}w^Tw - w^T\sum_{i=1}^n\alpha_iy_ix_i - b\sum_{i=1}^n\alpha_iy_i + \sum_{i=1}^n \alpha_i\\ & = \frac{1}{2}w^T\sum_{i=1}^n\alpha_iy_ix_i - w^T\sum_{i=1}^n\alpha_iy_ix_i - b \cdot 0 + \sum_{i=1}^n \alpha_i\\ & = \sum_{i=1}^n \alpha_i - \frac{1}{2} \left(\sum_{i=1}^n\alpha_iy_ix_i \right)^T \sum_{j=1}^n\alpha_jy_jx_j\\ & = \sum_{i=1}^n \alpha_i - \frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j \end{aligned}$

从上面的式子可以看出 $L(w,b,\alpha)$ 函数只含有一个变量 $\alpha_i$ , 从而得到我们的优化问题：

$\begin{aligned} &\underset{\alpha}{\max} \sum_{i=1}^n \alpha_i - \frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j\\ &s.t. \quad\sum_{i=1}^n \alpha_i y_i = 0 \quad\alpha_i \geq 0 \quad i = 1,2,\cdots,n \end{aligned}\tag{20}$

我们废了那么大的劲推导出这个式子是为了什么呢？

其实就是为了将最初的原始问题，转换到可以使用 SMO 算法求解的问题

SMO (Sequential Minimal Optimization)，序列最小优化算法，其核心思想非常简单：每次只优化一个参数，其他参数先固定住，仅求当前这个优化参数的极值。

SMO 算法

简单来说，我们需要对 $\alpha = (\alpha_1,\alpha_2,\cdots,\alpha_n)$ 进行优化

具体来说，在 SMO 算法中我们每次需要选择一对变量 $(\alpha_i,\alpha_j)$ , 因为在 SVM 中，我们的 $\alpha$ 并不是完全独立的，而是具有约束的

$\sum_{i=1}^n \alpha_i y_i = 0$

我们没法一次只变动一个参数，所以我们选择了一次选择两个参数。

选择两个需要更新的参数 $(\alpha_1,\alpha_2)$ ，固定其他参数。于是我们有以下约束

$\alpha_1y_1 + \alpha_2y_2 = - \sum_{i=3}^n\alpha_iy_i = c \tag{21}$

于是由式（21）我们可以得到

$\alpha_1 = cy_1 - \alpha_2y_1y_2$

也就是说我们可以用 $\alpha_2$ 的表达式代替 $\alpha_1$ , 这样就相当于把目标问题转化成了仅有一个约束条件的最优化问题

对于仅有一个约束条件的最优化问题，我们完全可以在 $\alpha_2$ 上对优化目标求偏导，令导数为零，从而求出变量值 $\alpha_{2_{new}}$ ，然后根据 $\alpha_{2_{new}}$ 求出 $\alpha_{1_{new}}$ , 多次迭代直至收敛

对任意训练样本 $(x_i,y_i)$ ，总有 $\alpha_i=0$ 或 $y_if(x_i)=1$ .若 $\alpha_i=0$ ，则该样本将不会在模型的求和中出现，也就不会对 f（x）有任何影响；若 $\alpha_i>0$ ，则必有 $y_if(x_i)=1$ ，所对应的样本点位于最大间隔边界上，是一个支持向量。这显示出支持向量机的一个重要性质：训练完成后，大部分的训练样本都不需保留，最终模型仅与支持向量有关。

解出最优的 α 之后，便可以求出 w 和 b，由之前求偏导时得到的式(18)可求出 w：

$w = \sum_{i=1}^n \alpha_i y_i x_i \tag{18}$

另一方面，任选一个支持向量代入 $y_s(wx_s+b)=1$ ，因此：

$b = y_s - wx_s \tag{22}$

w 和 b 都求出来了，之后我们可以得到最大分割超平面 $w^Tx+b=0$

分类决策函数： $f(x) = sign(w^Tx+b)$

软间隔

解决问题

在实际应用中，完全线性可分的样本是很少的，我们往往会遇到许多不能够完全线性可分的样本

解决该问题的一个办法是允许 SVM 在少量样本上出错，即将之前的硬间隔最大化条件放宽一点，为此引入“软间隔”的概念。即允许少量样本不满足约束

$y_i(w^Tx_i+b) \geq 1$

为了度量这个间隔软到何种程度，我们为每个样本引入一个松弛变量 $\xi_i$ ，令 $\xi_i\geq 0$ ，且

$y_i(w^Tx_i+b) \geq 1 - \xi_i \tag{23}$

优化目标及求解

增加软间隔后我们的优化目标变成了：

$\begin{aligned} &\min \frac{1}{2}\Vert w\Vert^2 + C\sum_{i=1}^n\xi_i\\ &s.t.\quad y_i(w^Tx_i+b) \geq 1 - \xi_i , \quad \xi_i\geq 0 \end{aligned}\tag{24}$

其中 C 是一个大于 0 的常数，可以理解为错误样本的惩罚程度，若 C 为无穷大， $\xi_i$ 必然无穷小，如此一来线性 SVM 就又变成了线性可分 SVM；当 C 为有限值的时候，才会允许部分样本不遵循约束条件。

C 为惩罚因子表示异常分布的点对目标函数的贡献权重，C 越大表示异常分布的点对目标函数的影响就越大，使得目标函数对异常分布点的惩罚就越大

对偶问题

式（24）表示的软间隔支持向量机依然是一个凸二次规划问题，和我们在上面讨论的支持向量机类似

式（24）对应的拉格朗日函数为

$\begin{aligned} L(w,b,\xi,\alpha,\beta) =& \frac{1}{2}\Vert w\Vert^2 + C\sum_{i=1}^n\xi_i \\&- \sum_{i=1}^n \alpha_i(y_i(w^Tx_i+b)-1+\xi_i) - \sum_{i=1}^n\beta_i\xi_i \end{aligned}\tag{25}$

将对偶问题转换为

$\underset{\alpha,\beta}{\max}\underset{w,b,\xi}{\min}L(w,b,\xi,\alpha,\beta)$

类似的，将 $L(w,b,\alpha,\beta)$ 分别对 w, b, $\xi$ 求偏导并令为 0 可得

$w = \sum_{i=1}^n \alpha_i y_i x_i \tag{26}$

$\sum_{i=1}^n \alpha_i y_i = 0 \tag{27}$

$C = \alpha_i + \beta_i \tag{28}$

将这些关系带入拉格朗日函数（24）中，得到：

$\underset{w,b,\xi}{\min}L(w,b,\xi,\alpha,\beta) = \sum_{i=1}^n \alpha_i - \frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j \tag{29}$

注意其中没有 $\beta$ , 所以现在只需要最大化 $\alpha$ 就好

$\begin{aligned} &\underset{\alpha}{\max} \sum_{i=1}^n \alpha_i - \frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j \\ &s.t. \quad \sum_{i=1}^n \alpha_i y_i = 0, \quad \alpha_i \geq 0,\quad C = \alpha_i + \beta_i \end{aligned}\tag{30}$

然后我们利用 SMO 算法求解得到拉格朗日乘子

核函数

我们刚刚讨论的硬间隔和软间隔都是在说样本的完全线性可分或者大部分样本点的线性可分。

但是我们经常会遇到非线性的问题, 样本点不是线性可分的。此时我们就需要用到核函数将线性支持向量机推广到非线性支持向量机。

核函数的定义:

设 $\mathcal{X}$ 是输入空间 (欧式空间 $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)$ 为 $\phi(x)$ 和 $\phi(z)$ 的內积

多项式核函数

$K(x,z)=(x\cdot z+1)^p$

高斯核函数

$K(x,z)=\exp(-\frac{\Vert x-z\Vert^2}{2\sigma^2})$

我们用 x 表示原来的样本点，用 $\phi(x)$ 表示 x 映射到特征新的特征空间后到新向量。那么分割超平面可以表示为：

$f(x) =w\phi(x) + b\tag{31}$

按照前面的方法，对于非线性 SVM 的对偶问题就变成了

$\begin{aligned} \underset{\alpha}{\max} \sum_{i=1}^n \alpha_i - \frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_j(\phi(x_i)\cdot\phi(x_y)) \\ s.t. \quad \sum_{i=1}^n \alpha_i y_i = 0, \quad \alpha_i \geq 0,\quad C = \alpha_i + \beta_i \end{aligned}\tag{32}$