SVM 概述

支持向量机(support vector machines,SVM)是一种二分类模型。基本模型是定义在特征空间上的间隔最大的线性分类器,也就是一个最优的分离超平面,学习策略是最大间隔法,最终转化成一个凸二次规划问题求解。

SVM

对于一个线性可分数据集来说,我们的目标就是找到一个超平面,使得所有的类别都能够正确分类,但是这样的类别有很多个,怎么选取最优的那个呢?最直观的就是选择出一个超平面,所有正确分类的样本到超平面都大于等于某个间隔值。那如何将这个思想转换成数学模型呢?

假设给定一个特征空间上的训练数据集:$T={(x_1,x_2),(x_2,x_2),\cdots,(x_N,y_N)}$,其中 $x_i \in R^n,y_i \in {-1,1},i=1,2,\cdots,N$。
定义分离超平面为:$w^T \cdot x+b=0$
分类决策函数为:$f(x)=sign(w^T \cdot x+b)$

函数间隔和几何间隔

定义超平面 $(w,b)$ 关于样本点 $(x_i,y_j)$ 的函数间隔为:
$$
\hat{\gamma}_{i}=y_{i}(w \cdot x_i+b)
$$
定义超平面 $(w,b)$ 关于训练数据集 $T$ 的函数间隔为超平面 $(w,b)$ 关于 $T$ 中所有样本点 $(x_i,y_j)$ 的函数间隔之最小值,即:
$$
\hat{\gamma}=\min_{i=1,\cdots,N}\hat{\gamma}_i
$$
函数间隔可以便是分类预测的正确性及确信度。如果 $\hat{\gamma}_{i}$ 的值越大,分类结果的确信度越大。反之亦然。

那么问题来了,如果 $w,b$同时扩大 $\lambda$ 倍,超平面没有改变,但是函数间隔却扩大了 $\lambda$ 倍,这显然不是我们想要的,因为这样的话,就没有办法利用最大间隔法找出最优的分隔超平面。所以需要将 $w$ 的大小固定,如 $||w||=1$,使得间隔是确定的。这时函数间隔成为几何间隔。

定义超平面 $(w,b)$ 关于样本点 $(x_i,y_j)$ 的几何间隔,:
$$
\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,\cdots,N} \gamma_{i}
$$

注:在二维空间中,几何间隔就是点 $(x_i,y_i)$ 到直线 $ax+by+c=0$ 的距离 $d(x_i,y_i)=\frac{|ax_i+by_i+c|}{\sqrt{a^2+b^2}}$。在三维及以上空间中,就是点到超平面的距离。

间隔最大化

对于线性可分的训练数据集而言,线性可分分离超平面有无穷多个,但是几何间隔最大的分离超平面是唯一的。我们的目标是寻找几何间隔最大的分离超平面:
$$
\max_{w,b} \quad \frac{\hat{\gamma}}{||w||} \\
s.t. \quad y_{i}(w \cdot x_i + b) \geq \hat{\gamma}, i=1,2,\cdots,N
$$

前面我们知道,随意同时缩放 $w,b$ 不会改变几何间隔的大小,所以可以通过缩放 $w,b$ 使得函数间隔 $\hat{\gamma}=1$。为了求解这个优化问题,还需要做一些数学转换,这里的 $||w||$ 是一个非凸函数,求解比较困难。原始目标最大化 $\frac{1}{||w||}$ 等价于最小化 $\frac{1}{2}||w||^2$ ,因此可以转化为凸优化问题:
$$
\min_{w,b} \quad \frac{1}{2}||w||^2 \\
s.t. \quad y_{i}(w \cdot x_i + b) \geq 1, i=1,2,\cdots,N
$$
现在问题明确了,先求解问题,得出最优解 $w^{*},b^{*}$ ,再得到上述的分类决策函数。

线性可分 SVM 的对偶算法

通过求解对偶问题得到原始问题的最优解,就是线性可分支持向量机的对偶算法。这样做有两个优点:

  • 对偶问题更容易求解;
  • 引入核函数,推广到线性分类问题。
  1. 构建拉格朗日函数
    $$
    L(w,b,\alpha)=\frac{1}{2}||w||^2-\sum_{i=1}^{N}\alpha_iy_{i}(w \cdot x_i +b ) + \sum_{i=1}^{N}\alpha_i
    $$
    其中,$\alpha_i \geq 0,i=1,2,\cdots,N $, $\alpha=(\alpha_1,\alpha_2,\cdots,\alpha_N)^T$ 为拉格朗日乘子向量。
    根据拉格朗日对偶性,原始问题的对偶问题是极大极小问题:
    $$
    \max_{\alpha} \min_{w,b} L(w,b,\alpha)
    $$

  2. 求 $\min_{w,b}L(w,b,\alpha)$
    将拉格朗日函数分别对 $w,b$ 求偏导并令其等于 0,可得:
    $$
    w=\sum_{i=1}^{N}\alpha_iy_ix_i \\
    \sum_{i=1}^{N}\alpha_iy_i=0
    $$
    代入拉格朗日函数可得:
    $$
    L(w,b,\alpha)=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_j y_i y_j(x_i \cdot x_j)+ \sum_{i=1}^{N} \alpha_i
    $$

  3. $\min_{w,b}L(w,b,\alpha)$ 对 $\alpha$ 的极大,即对偶问题
    $$
    \max_{\alpha} \quad -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_j y_i y_j(x_i \cdot x_j)+ \sum_{i=1}^{N} \alpha_i \\
    s.t. \quad \sum_{i=1}^{N} \alpha_iy_i=0 \\
    \alpha_i \geq 0, i=1,2,\cdots,N
    $$

所以,实际求解的时候,可以根据 KKT 公式,先求出最优解 $\alpha^{*}$ ,再求出 $w^{*},b^{*}$。

软间隔 SVM

如果训练数据中存在一些特异点,如下图所示,两种类别有交集,怎么处理呢?
image

这个时候我们引入一个松弛变量(slack variable)$\xi_i \geq 0$,使得函数间隔加上松弛变量后大于等于1。对于正确分类的样本 $\xi_i=0$,对于错误分类的样本$\xi_i >1$,对于在间隔当中但是正确分类的样本 $0 < \xi \leq 1$。对于每个松弛变量$\xi_i$,有个惩罚。目标优化函数就变成如下:
$$
\min_{w,b,\xi} \quad \frac{1}{2}||w||^2 + C\sum_{i=1}^{N}\xi_i \\
s.t. \quad y_{i}(w \cdot x_i + b) \geq 1, i=1,2,\cdots,N \\
\xi_i \geq 0, \quad i=1,2,\cdots,N
$$

非线性 SVM

前面介绍的数据集都是线性可分的,如下图所示,如果数据集是非线性可分的,又该怎么处理呢?这个时候,就该核函数就隆重出场了。

非线性不可分

核技巧

对于非线性可分问题,可以用一个超曲面将正负样本正确分开。基本想法是通过一个非线性变换将输入空间对应于一个特征空间,使得输入空间中超曲面模型对应于特征空间中的超平面模型。

请作者吃酒!