支持向量机(上)

1. 背景

考虑一个二类分类的问题,样本用方块和圆圈表示,如下图所示。这个数据集是线性可分的,即可以找到一个超平面,使得所有的方块位于这个超平面的一侧,而所有的圆圈位于它的另一侧。然而,如图所示,可能存在无穷多个那样的超平面。虽然它们的训练误差都等于零,但是不能保证这些超平面对未知样本划分得同样好。因此,我们应该从中选择一个“最佳”分离超平面,那么问题来了,我们用什么度量来刻划“最佳”呢?


sample

本文将介绍一种称作支持向量机(support vector machine, SVM)的方法,它利用间隔最大化(margin maximization)来求解最佳的分离超平面。

假设给定一个特征空间上的训练数据集
$$
T = \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N) \}
$$
其中,$x_i \in R^n, y_i \in \{+1,-1\}, i = 1,2,\cdots, N$。$x_i$为第$i$个特征向量,也称为实例,$y_i$为$x_i$的类标记,当$y_i=+1$时,称$x_i$为正例;当$y_i=-1$时,称$x_i$为负例,$(x_i,y_i)$称为样本点。

假设训练数据集是线性可分的,训练的目标是在特征空间中找到一个分离超平面,能将实例分到不同的类。分离超平面对应于方程$w \cdot x + b =0 $,它由法向量$w$和截距$b$决定,因此可用$(w,b)$来表示。分离超平面将特征空间划分为两部分,一部分是正类,另一部分是负类。法向量指向的一侧为正类,另一侧为负类。

2. 支持向量机

支持向量机包含以下几种模型:

  • 线性可分支持向量机(linear support vector machine in linearly separable case)
  • 线性不可分支持向量机(linear support vector machine in non-linearly separable case)
  • 非线性支持向量机(non-linear support vector machine)

svm

如图所示:

  • 当训练数据线性可分时,通过硬间隔最大化(hard margin maximization),学习一个线性的分类器,即线性可分支持向量机,又称为硬间隔支持向量机;
  • 当训练数据近似线性可分时(或者线性不可分),通过软间隔最大化(soft margin maximization),也学习一个线性的分类器,即线性支持向量机,又称为软间隔支持向量机;
  • 当训练数据线性不可分时,通过使用核技巧(kernel trick)及软间隔最大化,学习非线性支持向量机.

本文主要介绍线性可分支持向量机线性可分支持向量机的定义如下:

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

3. 函数间隔和几何间隔

如下图所示,有A,B,C三个点,表示3个实例(样本),它们均在分离超平面$L$的正类(假设圆圈是正类)一侧,我们要预测它们的类别。点A距分离超平面$L$较远,若预测该点为正类,就比较确信预测是正确的;点C距分离超平面较近,若预测该点为正类就不那么确信;点B介于点A与C之间,预测其为正类的确信度也在A与C之间。


sample

一般来说,一个点距分离超平面的远近可以表示分类预测的确信程度。在超平面$w \cdot x + b = 0$确定的情况下,$|w \cdot x + b|$能够相对地表示点$x$距离超平面的远近。而$w \cdot x + b$的符号与类标记$y$的符号是否一致能够表示分类是否正确。所以可以用$y(w \cdot x + b)$来表示分类的正确性及确信度,这就是函数间隔(functional margin)的概念。

函数间隔)对于给定的训练数据集$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(\hat{\gamma_1},\hat{\gamma_2},\cdots,\hat{\gamma_N})
$$

函数间隔可以表示分类预测的正确性及确信度。但是选择分离超平面时,只有函数间隔还不够。因为只要成比例地改变$w$和$b$,例如将它们改为$2w$和$2b$,超平面并没有改变,但函数间隔却成为原来的2倍。因此,我们可以对分离超平面的法向量$w$加某些约束,如规范化,$||w||=1$,使得间隔是确定的,这时函数间隔成为几何间隔

几何间隔)对于给定的训练数据集$T$和超平面$(w,b)$,定义超平面$(w,b)$关于样本点$(x_i,y_i)$的几何间隔为
$$
\gamma_i=y_i \left(\frac{w}{||w||} \cdot x_i + \frac{b}{||w||}\right)
$$
定义超平面$(w,b)$关于训练数据集$T$的几何间隔为超平面$(w,b)$关于$T$中所有样本点$(x_i,y_i)$的几何间隔之最小值,即
$$
\gamma = min(\gamma_1,\gamma_2,\cdots,\gamma_N)
$$

从函数间隔和几何间隔的定义可知,函数间隔和几何间隔有如下关系:
$$
\gamma = \frac{\hat{\gamma}}{||w||}
$$

如果$||w||=1$,那么函数间隔和几何间隔相等。如果超平面参数$w$和$b$成比例地改变(超平面没有改变),函数间隔也按此比例改变,而几何间隔不变

4. 线性可分支持向量机

支持向量机学习的基本思想是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对线性可分的训练数据集而言,线性可分分离超平面有无穷多个(等价于感知机),但是几何间隔最大的分离超平面是唯一的。这里的间隔最大化又称为硬间隔最大化(与训练数据集近似线性可分时的软间隔最大化相对应)。

间隔最大化的直观解释是:对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。也就是说,不仅将正负实例点分开,而且对最难分的实例点(离超平面最近的点)也有足够大的确信度将它们分开。这样的超平面应该对未知的新实例有很好的分类预测能力。

4.1 最大间隔分离超平面

下面考虑如何求得一个几何间隔最大的分离超平面(即最大间隔分离超平面)。该问题可以表示为下面的约束最优化问题:
$$
\left\{
\begin{array}{ll}
\max \limits_{w,b} & \gamma \\
s.t. & y_i \left(\frac{w}{||w||} \cdot x_i + \frac{b}{||w||}\right) \ge \gamma , i=1,2,\cdots,N \\
\end{array}
\right.
$$

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

考虑几何间隔和函数间隔的关系式,可将这个问题改写为:
$$
\left\{
\begin{array}{ll}
\max \limits_{w,b} & \frac{\hat{\gamma}}{||w||} \\
s.t. & y_i(w \cdot x_i + b) \ge \hat{\gamma} , i = 1,2,\cdots,N \\
\end{array}
\right.
$$

函数间隔$\hat{\gamma}$的取值并不影响最优化问题的解。事实上,假设将$w$和$b$按比例改变为$\lambda w$和$\lambda b$,这时函数间隔为$\lambda \hat{\gamma}$。函数间隔的这一改变对上面最优化问题的不等式约束没有影响,对目标函数的优化也没有影响,也就是说,它产生一个等价的最优化问题。这样,可以取$\hat{\gamma}=1$,将$\hat{\gamma}=1$代入上面的最优化问题,注意到最大化$\frac{1}{||w||}$和最小化$\frac{1}{2}||w||^2$是等价的,于是就得到下面的线性可分支持向量机学习的最优化问题

\begin{equation}
\left\{
\begin{array}{ll}
\min \limits_{w,b} & \frac{1}{2}||w||^2 \\
s.t. & y_i(w \cdot x_i + b) -1 \geq 0 , i = 1,2,\cdots, N \\
\end{array}
\right.
\end{equation}

这是一个凸二次规划(convex quadratic programming)问题。

4.2 线性可分支持向量机学习算法

综上所述,可以得到下面的线性可分支持向量机学习算法—-最大间隔法(maximum margin method)

[线性可分支持向量机学习算法—-最大间隔法]
输入:线性可分训练数据集$$T = \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N) \}$$ 其中,$x_i \in R^n, y_i \in \{+1,-1\}, i = 1,2,\cdots, N $ 。
输出:最大间隔分离超平面和分类决策函数。
(1) 构造并求解约束最优化问题:

$$
\left\{
\begin{array}{ll}
\min \limits_{w,b} & \frac{1}{2}||w||^2 \\
s.t. & y_i(w \cdot x_i + b) -1 \geq 0 , i = 1,2,\cdots, N \\
\end{array}
\right.
$$

求得最优解$w^{*},b^{*}$。
(2) 由此得到分离超平面:
$$
w^{*} \cdot x + b^{*} = 0
$$
和分类决策函数
$$
f(x) = sign(w^{*} \cdot x + b^{*})
$$

4.3 学习的对偶算法

可以看到,线性可分支持向量机的最优化问题(1)含有不等式约束,不宜直接求解,可以引入拉格朗日函数,将不等式约束嵌入目标函数,应用拉格朗日对偶性,通过求解对偶问题(dual problem)得到原始问题(primal problem)的最优解,这就是线性可分支持向量机的对偶算法(dual algorithm)。这样做的优点,一是对偶问题往往更容易求解;二是自然引入核函数,进而推广到非线性分类问题。

首先构建拉格朗日函数(Lagrange function)。为此,对每一个不等式约束,引进拉格朗日乘子(Lagrange multiplier)$\alpha_i \ge 0$,$i=1,2,\cdots,N$,定义拉格朗日函数:

$$
L(w,b,\alpha) = \frac{1}{2} ||w||^2 - \sum_{i=1}^N \alpha_i y_i(w \cdot x_i + b) + \sum_{i=1}^N \alpha_i
$$

其中,$\alpha=(\alpha_1,\alpha_2,\cdots,\alpha_N)^T$为拉格朗日乘子向量。

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

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

所以,为了得到对偶问题的解,需要先求$L(w,b,\alpha)$对$w,b$的极小,再求对$\alpha$的极大。

  • 求$\min \limits_{w,b} L(w,b,\alpha)$
    将拉格朗日函数$L(w,b,\alpha)$分别对$w,b$求偏导数并令其等于0,得到
    $$
    \left\{
    \begin{split}
    \nabla_{w} L(w,b,\alpha) &= w - \sum_{i=1}^N \alpha_i y_i x_i = 0 \\
    \nabla_{b} L(w,b,\alpha) &= \sum_{i=1}^N \alpha_i y_i = 0 \\
    \end{split}
    \right.
    $$

得到
$$
\left\{
\begin{split}
w = \sum_{i=1}^N \alpha_i y_i x_i \\
\sum_{i=1}^N \alpha_i y_i = 0 \\
\end{split}
\right.
$$

将上式代入拉格朗日函数,化简可以得到:
$$
\min \limits_{w,b} 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
$$

  • 求$\min \limits_{w,b} L(w,b,\alpha)$对$\alpha$的极大,即对偶问题
    $$
    \left \{
    \begin{split}
    \max \limits_{\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 \\
    s.t. & \sum_{i=1}^N \alpha_i y_i = 0 \\
    & \alpha_i \ge 0, i = 1,2,\cdots,N
    \end{split}
    \right.
    $$

将极大转换成极小,得到下面与之等价的对偶最优化问题:

\begin{equation}
\left \{
\begin{split}
\min \limits_{\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 \\
s.t. & \sum_{i=1}^N \alpha_i y_i = 0 \\
& \alpha_i \ge 0, i = 1,2,\cdots,N
\end{split}
\right.
\end{equation}

因此,求解原始最优化问题(1)可以转换为求解对偶问题(2)。对线性可分训练数据集,假设对偶最优化问题(1)对$\alpha$的解为$\alpha^{*}=(\alpha_1^{*},\alpha_2^{*},\cdots,\alpha_N^{*})^T$,可以由$\alpha^{*}$求得原始最优化问题(1)对$(w,b)$的解$w^{*}$,$b^{*}$:

\begin{equation}
\left \{
\begin{split}
w^{*} &= \sum_{i=1}^N \alpha_i^{*} y_i x_i \\
b^{*} &= y_j - \sum_{i=1}^N \alpha_i^{*} y_i (x_i \cdot x_j)
\end{split}
\right.
\end{equation}

综上所述,对于给定的线性可分训练数据集,可以首先求对偶问题(2)的解$\alpha^{*}$;再利用(3)求得原始问题的解$w^{*}$,$b^{*}$;从而得到分离超平面及分类决策函数。这种算法称为线性可分支持向量机的对偶学习算法,是线性可分支持向量机学习的基本算法。

[线性可分支持向量机对偶学习算法]
输入:线性可分训练数据集$$T = \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N) \}$$ 其中,$x_i \in R^n, y_i \in \{+1,-1\}, i = 1,2,\cdots, N $ 。
输出:最大间隔分离超平面和分类决策函数。
(1) 构造并求解约束最优化问题:
$$
\left \{
\begin{split}
\min \limits_{\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 \\
s.t. & \sum_{i=1}^N \alpha_i y_i = 0 \\
& \alpha_i \ge 0, i = 1,2,\cdots,N
\end{split}
\right.
$$
求用SMO算法得最优解$\alpha^{*}=(\alpha_1^{*},\alpha_2^{*},\cdots,\alpha_N^{*})^T$。
(2) 计算
$$
w^{*} = \sum_{i=1}^N \alpha_i^{*} y_i x_i
$$
并选择$\alpha^{*}$的一个正分量$\alpha_j^{*} > 0$,计算
$$
b^{*} = y_j - \sum_{i=1}^N \alpha_i^{*} y_i (x_i \cdot x_j)
$$
(3) 求得分离超平面
$$
w^{*} \cdot x + b^{*} = 0
$$
分类决策函数:
$$
f(x) = sign(w^{*} \cdot x + b^{*})
$$

5. 参考资料