支持向量机以及核方法

Posted on Edited on In
Symbols count in article: 9.3k Reading time ≈ 8 mins.

以下内容由我的CSDN博客迁移。

有关支持向量机的理解在网上已经有很多了，我在这里写一下我的学习笔记。（主要参考《统计学习方法》以及部分博客）

支持向量机包含线性可分的支持向量机、线性支持向量机、非线性支持向量机，让我们从简单到复杂来学习它。

一、什么是支持向量机

支持向量机（support vector machines, SVM） 是一种二分类模型。它的基本定义是在特征空间上的间隔最大的线性分类器。借助核技巧，支持向量机成为实质上的非线性分类器。基本的学习策略就是寻找最大化的间隔。

让我们先从线性可分的数据集中获取一些基本概念

1. 间隔（函数间隔和几何间隔）

如图，这是一个线性可分的二分类(分为{+1， -1}两类)问题，其中有一个超平面分隔了两类。我们可以认为某点距离超平面越远，它为对应的类别的确信度就越高。即：对于给定的超平面\(\boldsymbol{w\cdot x +b=0}\); 点\(\boldsymbol x_0\)距离该平面的远近可以相对的使用 \(|\boldsymbol{w\cdot x_0+b}|\)来表示。而\(\boldsymbol{w\cdot x +b}\)的符号与类标记的符号y是否一致就可以表示分类的正确性。因此给出函数间隔(functional margin)的概念：

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

    \[\hat \gamma_i=y_i(w\cdot x_i +b)\] 定义超平面关于数据集T的函数间隔为所有样本点中函数间隔的最小值。 \[\hat \gamma=\min_{i=1, \dots, N}\hat \gamma_i\] 函数间隔可以表示分类预测的准确性以及确信度。

但是我们不难发现若成比例的增长超平面的参数，超平面不会改变，这对我们要优化参数找到最大间隔造成了不便，因此我们可以对参数进行某些8约束，如规范化，使得\(\|w\|=1\)（这里视为L2范数）从而使得间隔是确定的。也就是几何间隔（geometric margin）：

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

    \[\gamma_i=y_i(\dfrac{w}{\|w\|}\cdot x_i +\dfrac{b}{\|w\|})\] 定义超平面关于数据集T的几何间隔为所有样本点中几何间隔的最小值。也就是我们直观上理解的点到超平面的距离。

2.（硬）间隔最大化

支持向量机所寻找的就是所有可分割两类的超平面中，几何间隔最大的超平面。 即下面的约束最优化问题： \[ \begin{aligned} &\max_{w, b} ~~~~~\gamma\\ &~~\text{s.t.}~~~y_i(\dfrac{w}{\|w\|}\cdot x_i +\dfrac{b}{\|w\|})\ge \gamma, ~~~i=1, 2, \dots, N \end{aligned}\] 转换为函数间隔，我们得到 \[\begin{aligned} &\max_{w, b} ~~~~~\dfrac{\hat \gamma}{\|w\|}\\ &~~\text{s.t.}~~~y_i(w\cdot x_i +b)\ge \hat \gamma, ~~~i=1, 2, \dots, N \end{aligned} \]

  • 由于函数间隔的放缩对于最大间隔没有影响，因此我们这里可以认为函数间隔\(\hat \gamma=1\).
  • 同时，我们可以将最大化\(\dfrac{1}{\|w\|}\)，转化为最小化凸函数\(\dfrac{1}{2}\|w\|^2\)两者是等价的。因此，上面的约束优化问题等价于下面这个凸二次规划问题：

\[\begin{aligned} &\min_{w, b} ~~~~~\dfrac{1}{2}\|w\|^2\\ &~~\text{s.t.}~~~y_i(w\cdot x_i +b)- 1\ge 0, ~~~i=1, 2, \dots, N \end{aligned}\]

注：凸优化问题是指目标函数和约束函数都是连续可微的凸函数，且等式约束是仿射函数。

求解出优化问题的最优解\(w^*, b^*\)后，我们就可以得到分离超平面，以及决策函数：\(f(x)=\text{sign} (w^* \cdot x +b^*)\)

3. 最大间隔的确定性

这里主要解释证明一下为什么支持向量机有如下定理：

  • 最大间隔分离超平面的存在唯一性：若训练数据集线性可分，则可将数据集中的样本点完全正确分开的最大间隔分离超平面存在且唯一。

  1. 存在性：由于数据集线性可分，则根据最优化问题，我们一定可以找到可行解。又由于目标函数有下界，因此最优化问题一定有解。由于正负两类的存在，最优解\(w^*\)一定不为0。综上我们可以得出分离超平面的可行性。

  2. 唯一性：

    • 运用反证法，假设最优化问题存在两个最优解\((w_1^*, b_1^*)\)和\((w_2^*, b_2^*)\)。显然由目标函数，我们得到\(\|w_1^*\|=\|w^*_2\|=c\).
    • 令\(w={w_1^*+w_2^* \over 2}, b={b_1^*+b_2^* \over 2}\)。有\(\|w\|=c\)，即\(\|w^*_1\|={\|w_2^*\|+\\|w_1^*\| \over 2}\), 由此我们推知\(w_1^*=w_2^*\)。
    • 对于两个最优解\((w^*, b_1^*), (w^*, b_2^*)\), 对于训练集中所有的负类\((y=-1)\)，假设\(x_1^\prime, x_2^\prime\)是使得约束函数等号成立的点，同样假设\(x_1'', x_2''\)为正类中使得约束函数等号成立的点。根据约束函数，我们可以解出\(b_i^*\): \[b_i^*=-{1 \over 2}(w^*\cdot x_i'+w^*\cdot x_i''), ~~~i=1, 2\\ \Downarrow \\ b_1^*-b_2^*=-{1\over 2}[w^*\cdot (x_1'-x_2')+w^*\cdot (x_1''-x_2'')]\]

    又因为根据不等式约束 \[w^*\cdot x_2'+b_1^*\geqslant1=w^*\cdot x_1'+b_1^* \\ w^*\cdot x_1'+b_2^*\geqslant1=w^*\cdot x_2'+b_2^*\] 两式可以推出\(w^*\cdot (x_1'-x_2')=0\), 同理，\(w^*\cdot (x_1''-x_2'')=0\). 因此我们最终得到：\(b_1^*-b_2^*=0\)

    • 由\(w_1^*=w_2^*, b_1^*=b_2^*\)，最大分割超平面的唯一性得证。

4. 支持向量和间隔边界

支持向量就是使不等式约束等号成立的点，即： \[y_i(w\cdot x_i+b)-1=0\] 因此对于所有正类和负类，所有都支持向量在超平面\(w\cdot x +b=\pm 1\)上。如图所示，

两个超平面之间形成一条长带，分离超平面位于它们中央。长带的宽度，称为间隔。间隔大小为\(2\over \|w\|\)。同时两个支持向量超平面称为间隔边界。

5. 软间隔

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

  • 为了解决某些样本点不能满足函数间隔大于1的约束条件，我们可以对每个样本点引入一个松弛变量\(\xi_i\geqslant0\), 使函数间隔加上松弛变量大于等于1. 即约束条件变为：

    \[y_i(w\cdot x_i+b)\geqslant1-\xi_i\] 与此同时，对于每个松弛向量，我们都支付一个代价。即把目标函数变为： \[{1\over 2}\|w\|^2+C\sum^N_{i=1}\xi_i\] 这里\(C>0\)称为惩罚参数，由具体应用决定。\(C\)值很大时对于误分类的惩罚增大。因此对于线性不可分的训练数据集，我们的学习策略是软间隔最大化。

  • 线性不可分的支持向量机的学习问题变为如下凸二次规划问题：

\[\begin{aligned}\min_{w, b, \xi}~~~~~~&{1\over2}\|w\|^2+C\sum_{i=1}^N\xi_i\\ \text{s.t.}~~~~~~ &y_i(w\cdot x_i+b)\geqslant1-\xi_i, ~~i=1, 2, \dots, N \\& \xi_i\geqslant0, ~~i=1, 2, \dots, N \end{aligned}\]

  • 注意：此时可以证明\(w\)的解是唯一的，但\(b\)的解不唯一，而是存在于一个区间。
  • 此优化问题就是线性支持向量机的通用定义。

二、怎么求解支持向量机

1. 线性可分支持向量机

对于线性可分支持向量机的凸二次规划问题，我们可以构造广义拉格朗日函数： \[\mathcal{L}={1\over 2}\|w\|^2-\sum_{i=1}^N\alpha_i[y_i(w\cdot x_i+b)-1]\] 其中\(\alpha=(\alpha_1, \alpha_2, \dots, \alpha_N)^T\)为拉格朗日乘子向量。 对于原始问题：\(\min_{w, b}\max_\alpha \mathcal{L}(\boldsymbol{w, b, \alpha})\), 由于这是一个凸二次规划问题，因此我们可以运用拉格朗日的对偶性，求解对偶问题来得到原始问题的最优解： \[\max_\alpha\min_{w, b}\mathcal L(\boldsymbol{w, b, \alpha})\] 具体求解过程如下：

  1. 求\(\min_{w,b}\mathcal L(\boldsymbol{w,b,\alpha})\):

对拉格朗日函数求梯度并令其等于零： \[\nabla_w\mathcal L(\boldsymbol{w, b, \alpha})=w-\sum_{i=1}^N\alpha_iy_ix_i=0\\ \nabla_b\mathcal L(\boldsymbol{w, b, \alpha})=-\sum_{i=1}^N\alpha_iy_i=0\] 得到： \[w=\sum_{i=1}^N\alpha_iy_ix_i, ~~~~~\sum_{i=1}^N\alpha_iy_i=0\] 代入函数中，得到：

\[\begin{aligned}\mathcal L(\boldsymbol{w, b, \alpha})&={1\over 2}\sum_{i=1}^N\sum_{j-1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_iy_i\bigg ( \bigg(\sum_{j=1}^N\alpha_jy_jx_j\bigg )\cdot x_i +b\bigg )+\sum^N_{i=1}\alpha_i\\ &=-{1\over 2}\sum_{i=1}^N\sum_{j-1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum^N_{i=1}\alpha_i\end{aligned}\] 具体推导见图：

由此我们求出了 \[\min_{w, b}\mathcal L(\boldsymbol{w, b, \alpha})=-{1\over 2}\sum_{i=1}^N\sum_{j-1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum^N_{i=1}\alpha_i\]

  1. 求对偶问题

\[\begin{aligned}\min_\alpha~~&{1\over 2}\sum_{i=1}^N\sum_{j-1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum^N_{i=1}\\ \text{s.t.}~~&\sum_{i=1}^N\alpha_iy_i=0\\ &\alpha_i\geqslant0, i=1, 2, \dots, N\end{aligned}\] 根据拉格朗日对偶问题与原始问题等价的条件成立（KKT条件）： \[\begin{aligned}\nabla_w\mathcal L(\boldsymbol{w^*, b^*, \alpha^*})&=w^*-\sum_{i=1}^N\alpha^*_iy_ix_i=0\\ \nabla_b\mathcal L(\boldsymbol{w^*, b^*, \alpha^*})&=-\sum_{i=1}^N\alpha^*_iy_i=0\\ \alpha^*_i(y_i(w^*\cdot x_i+b^*)-1)&=0, ~~~i=1, 2, \dots, N \\ y_i(w^*\cdot x_i+b^*)-1&\geqslant0\\ \alpha_i&\geqslant0, ~~~~~i=1, 2, \dots, N \end{aligned} \] 由此得 \[w^*=\sum_i\alpha_i^*y_ix_i\] 因此至少有一个\(\alpha^*_j>0(w^*\neq0)\)，对于此点，有\(y_j(w^*\cdot x_j+b^*)-1=0\)。由此我们可以求出 \[b^*=y_j-\sum_{i=1}^N\alpha_i^*y_i(x_i\cdot x_j)\] 从而得到了我们的分离超平面： \[\sum_{i=1}^N\alpha_i^*y_i(x\cdot x_i)+b^*=0\] 也就是说，分类只依赖于输入\(x\)和训练样本输入的内积。

以上就是线性可分的支持向量机学习的基本算法。

2. 线性支持向量机

同之前一样，我们构造广义拉格朗日函数： \[\mathcal L(\boldsymbol{w, b, \xi, \alpha, \mu} )={1\over 2}\|w\|^2+C\sum^N_{i=1}\xi_i-\sum^N_{i=1}\alpha_i(y_i(w\cdot x_i+b)-1+\xi_i)-\sum^N_{i=1}\mu_i\xi_i\] 其中\(\alpha_i\geqslant0, \mu_i\geqslant0.\) 首先，我们求\(\min_{w, b, \xi} \mathcal L(\boldsymbol{w, b, \xi, \alpha, \mu} )\), 对\(w, b, \xi\)求梯度并令其为零。其中前两个与之前一样。 \[\nabla_w\mathcal L(\boldsymbol{w, b, \xi, \alpha, \mu} )=w-\sum_{i=1}^N\alpha_iy_ix_i=0\\ \nabla_b\mathcal L(\boldsymbol{w, b, \xi, \alpha, \mu} )=-\sum_{i=1}^N\alpha_iy_i=0\\ \nabla_{\xi_i}\mathcal L(\boldsymbol{w, b, \xi, \alpha, \mu} )=C-\alpha_i-\mu_i=0\] 代入函数中，会发现得到与之前一样的形式： \[\min_{w, b, \xi}\mathcal L(\boldsymbol{w, b, \xi, \alpha, \mu}) =-{1\over 2}\sum_{i=1}^N\sum_{j-1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum^N_{i=1}\alpha_i\] 因此对偶问题为： \[\begin{aligned}\min_\alpha~~&{1\over 2}\sum_{i=1}^N\sum_{j-1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum^N_{i=1}\alpha_i\\ \text{s.t.}~~&\sum_{i=1}^N\alpha_iy_i=0\\ &C-\alpha_i-\mu_i=0\\ &\alpha_i\geqslant0\\ &\mu_i\geqslant0, i=1, 2, \dots, N\end{aligned}\] 将约束条件合并，我们可以得到\[0\leqslant \alpha_i\leqslant C\]

对于原始问题和对偶问题等价性的证明，也与之前类似，证明其满足KKT条件即可。 分离超平面： \[\sum_{i=1}^N\alpha_i^*y_i(x\cdot x_i)+b^*=0\]

在决定分离超平面时，只有支持向量起作用，而其他实例点不起作用。由于支持向量在确定分离超平面中起到决定性作用，所以将这种分类模型成为“支持向量机”。

三、核技巧及非线性SVM

上面只是介绍了线性支持向量机，对于非线性的分类问题，我们可以使用非线性支持向量机，它使用了核技巧。核技巧适用于很多统计学习问题，是十分重要的方法。

1. 非线性分类问题

非线性问题是指利用非线性模型才能很好分类的问题，如左图所示，我们无法用直线将正负实例分开，但可以用一条椭圆曲线分开。一般来说，对于给定的数据集，其中，实例\(x_i\in\mathcal X=\R^n\), 对应的标记有两类\(y_i\in\mathcal Y=\{-1, +1\}, i=1, 2, \dots, N\)。如果能用\(\R^n\)中的一个超曲面将正负例正确分开，则称这个问题为非线性可分问题。

但是如果我们将数据集重新映射到一个高维的空间，如右图，我们可以发现有一个超平面将两个类别正确分类。因此我们对于非线性的分类问题，我们往往采用将其重新映射到更高维的空间，以使非线性的问题变换为线性分类问题。然后我们就可以在新空间里用线性分类学习方法从训练数据中学习分类模型。

2. 核函数

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

  • 简单来说，可以认为核函数的输入是原空间的两个向量，它的输出是映射到高维空间的两个向量的内积，因此我们不用去求复杂的映射函数\(\phi\)而直接获取映射后两个向量的内积。

关于核函数的更通俗的理解，可以看看《关于核函数的一些思考》

3. 非线性SVM

之前求解出的对偶问题中，我们发现无论是目标函数还是决策函数都只涉及向量的内积，因此我们考虑可以使用核函数代替，以此来实现非线性支持向量机的学习。

此时对偶问题的目标函数变为 \[W(\alpha)={1\over 2}\sum_{i=1}^N\sum_{j-1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum^N_{i=1}\alpha_i\]

同样，分类决策函数变为 \[f(x)=\text{sign}\bigg (\sum_{i=1}^{N_s} \alpha_i^*y_iK(x_i, x)+b^*\bigg )\]

4. 成为核函数的条件

如果我们已知映射函数\(\phi\)那么我们就可以通过\(\phi(x)\cdot \phi(z)\)直接求得核函数。但实际上我们很难去学习映射函数，那么我们怎样才能不用构造映射函数而直接判断一个给定的函数\(K(x, z)\)是否核函数呢？

我们通常所说的核函数就是正定核函数，对于它的进一步理解，建议看一下这篇教程

  • 正定核的充要条件：设\(K:\mathcal{X\times X}\rightarrow \R\)是对称函数，则\(K(x, z)\)为正定核函数的充要条件是对任意\(x_i\in\mathcal X, x=1, 2, \dots, m, ~~~K(x, z)\)对应的Gram矩阵：

    \[K=[K(x_i, x_j)]_{m\times m}\] 是半正定矩阵。

  • 由此我们可以写出正定核的等价定义： 设\(\mathcal{X}\subset \R^n, K(x, z)\)是定义在\(\mathcal{X\times X}\)上的对称函数，如果对任意\(x_i\in \mathcal{X}, i=1, 2, \dots, m, K(x, z)\)对应的Gram矩阵是半正定矩阵，则称\(K(x, z)\)是正定核。 这一定义对于构造核函数时很有用。但对于具体函数我们不容易检验它是否为正定核函数。在实际问题中我们往往应用已有的核函数。

  • 另外，由Mercer定理我们可以得到Mercer核，正定核比它更具有一般性。

5. 常用的核函数

  1. 多项式核函数

    \[K(x, z)=(x\cdot z+1)^p\] 对应的支持向量机是一个p次多项式分类器。

  2. 高斯核函数（RBF）

    \[K(x, z)=\exp\bigg (-\dfrac{\|x-z\|^2}{2\sigma^2}\bigg )\] 对应高斯径向基函数分类器，会将原始空间映射为无穷维空间。通过调控参数，高斯核实际上具有相当高的灵活性，也是使用最广泛的核函数之一。

四、支持向量机的进一步理解

1. 支持向量机的另一种解释

支持向量机还有一种解释，就是最小化以下目标函数： \[\sum^N_{i=1}[1-y_i(w\cdot x_i+b)]_++\lambda\|w\|^2\] 即SVM能够同时实现经验风险和结构风险的最小化，从而达到在统计样本量较少的情况下，能获得良好统计规律的目的。

其中第一项是经验风险，称为合页损失函数（hinge loss）即 \[[z]_+\begin{cases}z, z>0\\0, z\leqslant 0\end{cases}\] 当样本点被正确分类且函数间隔大于1时，损失是0，否则会产生损失。目标函数第二项时正则化项，也是结构风险。

2. SMO算法

SMO算法是两变量支持向量机学习的一种快速算法，不断地将原二次规划问题分解为只有两个变量的二次规划子问题，并对子问题进行解析求解，直到所有变量满足KKT条件位置。证明不在这里详述了，但它具体的学习步骤如图：

对于SMO的更深入的理解，请参阅：1、SVM算法实现，2 、SMO优化算法

这里推荐一下July大神的 支持向量机通俗导论（理解SVM的三层境界）说的非常细致且由浅入深。

以上内容如有谬误还请告知。