支持向量机 SVM:SVM简介

支持向量机(support vector machine),一般简称SVM,通俗来讲,它是一种二类分类模型,其基本模型定义为特征空间上的间隔最大的线性分类器,其学习策略便是间隔最大化,最终可转化为一个凸二次规划问题的求解。

SVM 原理分为软间隔最大化、拉格朗日对偶、最优化问题求解、核函数、序列最小优化 SMO 等部分。

一、间隔和软间隔最大化

1. 分隔超平面

svm_intuition.png

对于二分类问题来说,中间这条实线(或三维空间里的平面),就叫做分隔超平面,表达式为 $\vec w \cdot \vec x + b=0$。

2. 函数间隔

SVM是通过超平面将样本分为两类。
在超平面 $w\cdot x+b=0$ 确定的情况下,$|w\cdot x+b|$ 可以相对地表示点x距离超平面的远近。对于两类分类问题,如果 $w\cdot x+b>0$ ,则x的类别被判定为1;否则判定为-1。

所以如果 $y(w\cdot x+b)>0$ ,则认为x的分类结果是正确的,否则是错误的。且 $y(w\cdot x+b)$ 的值越大,分类结果的确信度越大。反之亦然。所以样本点 $(x_{i}, y_{i})$ 与超平面(w, b)之间的函数间隔定义为:

我们用 $\hat{\gamma}$ 表示函数间隔,$\hat{\gamma}=y(w \cdot x+b)$。

3. 几何间隔(软间隔)

上面函数间隔的定义存在问题:即w和b同时缩小或放大M倍后,超平面并没有变化,但是函数间隔却变化了。所以,需要将w的大小固定。例如||w||=1,使得函数间隔固定,这时的间隔也就是几何间隔 。几何间隔的定义如下:

其中 xi 代表第 i 条数据,yi 代表第 i 条数据对应的目标变量的取值,取值有+1 和-1 两种。所以当第 i 条数据被正确分类时,y 取值和 wx+b 取值的正负一致,几何间隔为正;当被错误分类时,y 取值和 wx+b 取值的正负相反,几何间隔为负。如下图:

0529_svm_yi

我们用 $\tilde{\gamma}$ 表示几何间隔,$\tilde{\gamma}=y\frac{w \cdot x+b}{||w||}$。由于 $\hat{\gamma}=y(w \cdot x+b)$,所以 $\tilde{\gamma}=\frac{\hat{\gamma}}{||w||}$。

此外,函数间隔以及几何间隔其实并不是表示某种距离,真正的点到直线(或平面)的距离公式是:

小结一下:

(1). 实际距离 :$\gamma = \frac{w \cdot x + b}{||w||} \: (1.3.3)$

(2). 函数距离 :$\hat{\gamma}=y(w \cdot x+b) \: (1.3.4)$

(3). 几何距离 :$\tilde{\gamma}=y\frac{w \cdot x+b}{||w||}=\frac{\hat{\gamma}}{||w||} \: (1.3.5)$

4. 软间隔最大化

SVM 的核心思路是最大化支持向量到分隔超平面的间隔。后面所有的推导都是以最大化此间隔为核心思想展开。

(1). 首先定义几何间隔中最小的为:

(2). 由此可以得到间隔最大化问题的目标函数 $max \{\tilde{\gamma_i}\}$,并遵循如下约束条件:$s.t.\tilde{\gamma_i} = \frac{y_i(w\cdot x_i+b)}{||w||}\geq \tilde{\gamma}$,(s.t.表示 subject to:满足…限制) 。

这里重点解释一下上面这句话的意思:

(1).几何间隔就是点到给定超平面的距离;几何间隔中最小值 $min\{\tilde{\gamma_i}\}$ 表示所有样本点中几何间隔的最小值。

(2).间隔最大化问题 $max \{\tilde{\gamma}\}$ 表示要找到一种情况使得最小几何间隔在所有情况中取最大值,记为 $M = arg\:max_{w,b}\{\frac{min_{n}[y_i(w^T \cdot x_i+b)]}{||w||}\} \: (1.4.2)$。

5. 目标函数

为了方便计算,令函数距离的最小值 $min\{\hat{\gamma}\}=min\{y(w \cdot x+b) \}= 1$,则 $M=arg \: max_{w,b}{\{\frac{1}{||w||}\}}$。很显然,软间隔最大化 就是要求M这个最大值,也就是要求 $\frac{1}{||w||}$的最大值,也就是要求 ||w|| 的最小值。此时几何间隔的最大化情况就是:$\tilde{\gamma} = \frac{1}{||w||}$。

于是就得出了目标函数 :

等价于 :

这个公式描述的是一个典型的不等式约束条件下的二次型函数优化问题,同时也是 支持向量机的基本数学模型

可以看到这样的问题满足如下两个条件:

(1). 它所最优化的问题是一个二次式

(2). 它的限制条件是一个线性的一次式

有这样特性的最优化问题就叫二次规划(quadratic programing ,简称QP)

二、拉格朗日对偶(Lagrange duality)

1. 最优化问题的分类

通常我们需要求解的最优化问题有如下几类:

(1). 无约束优化问题,可以写为:

对于第(1)类的优化问题,常常使用的方法就是 Fermat定理(费马定理),即使用求取f(x)的导数,然后令其为零,可以求得候选最优值,再在这些候选值中验证;如果是凸函数,可以保证是最优解。

(2). 有等式约束的优化问题,可以写为:

对于第(2)类的优化问题,常常使用的方法就是 拉格朗日乘子法(Lagrange Multiplier) ,即把等式约束h_i(x)用一个系数与f(x)写为一个式子,称为 拉格朗日函数,而系数称为拉格朗日乘子。通过拉格朗日函数对各个变量求导,令其为零,可以求得候选值集合,然后验证求得最优值。

(3). 有不等式约束的优化问题,可以写为:

对于第(3)类的优化问题,常常使用的方法就是 KKT条件。同样地,我们把所有的等式、不等式约束与f(x)写为一个式子,也叫 拉格朗日函数,系数也称拉格朗日乘子,通过一些条件,可以求出最优值的必要条件,这个条件称为KKT条件。

2. KKT条件

KKT条件的全称是Karush-Kuhn-Tucker条件,KKT条件是说最优值条件必须满足以下条件:

  • 条件一:经过拉格朗日函数处理之后的新目标函数L(w,b,a)对x求导为零;
  • 条件二:$h_i(x)=0$;
  • 条件三:$a*g_j(x)=0$;

求取这三个等式之后就能得到候选最优值。其中第三个式子非常有趣,因为g(x)<=0,如果要满足这个等式,必须a=0或者g(x)=0。

3. 拉格朗日对偶

由于这个问题的特殊结构,还可以通过拉格朗日对偶性变换到对偶变量 (dual variable) 的优化问题,即通过求解与原问题等价的对偶问题(dual problem)得到原始问题的最优解,这就是 线性可分 条件下支持向量机的对偶算法,这样做的优点在于:一者对偶问题往往更容易求解;二者可以自然的引入 核函数,进而推广到 非线性分类 问题。

1). 首先回顾一下我们要处理的问题是 有不等式约束的的优化问题,这类问题的一般描述是:

我们根据原来的目标函数来构造一个新的目标函数:

2). 其中 $L(\boldsymbol{x},\boldsymbol{\alpha},\boldsymbol{\beta})$ 为广义拉格朗日函数,定义为:

这里,$\boldsymbol{\alpha}=[\alpha_1,\alpha_2,\ldots, \alpha_m]^T,~\boldsymbol{\beta}=[\beta_1,\beta_2,\ldots, \beta_n]^T$,是我们在构造新目标函数时加入的系数变量,也是我们要求的参数。另外不要忘了我们要求的是 $\theta_p(x)$ 的最小值。

3). 根据上面(2.3.2)和(2.3.3)两个公式我们得到:

其中 $h_i(x) = 0;g_j(x) \leq 0;i =1, …, n,j =1, …, m$

首先如果x不满足这两条限制,也就是在 可行解区域外,我们观察一下公式(2.3.4),一定可以找到某一种情况下的参数 $(\alpha,\beta)$ 使得 $\theta_p(x)$ 取向于 $\infty$,这种情况下肯定不是我们要求的$\theta_p(x)$ 的最小值。

再看一下x同时满足这两条显示,也就是在 可行解区域内,由于 $h_i(x) = 0;g_j(x) <= 0$,并且 $\beta_j \geq0$,那么很显然 $max_{\alpha,\beta;\beta_j\geq0} \:\{\sum_{i=1}^m\alpha_i h_i(\boldsymbol{x})+\sum_{j=1}^n\beta_j g_j(\boldsymbol{x})\}=0$,于是可以得到 $\theta_p(x)$ 的取值分布情况:

就这样原来有约束条件的 (2.3.1)问题求解现在就变成了没有约束条件求 $min \{\theta_p(x)\}$ 。

同时,我们设 $\theta_d(x)=min\{L(w,\alpha,\beta)\} \:(2.3.5)$,同时将问题转化为先求 $L(w,\alpha,\beta)$ 的最小值,再求它的最大值。与公式(2.3.2) $\theta_p(x)=max\{L(w,\alpha,\beta)\}$比较一下:

2.3.7 这个问题就是原问题 (2.3.6) 的对偶问题,相对于原问题只是更换了min和max的顺序,而一般更换顺序的结果是Max Min(X) <= Min Max(X)。然而在这里两者相等。由此我们可以设如下:

所以在一定的条件下我们可以得到:$d^{}=p^{}$,值得注意的是这里的问题要满足上面所说的 KKT条件

4. 对偶问题求解

1). 根据上面的推导我们知道了对偶问题的原理,回到一开始的问题,看一下公式 (1.5.2),再将其转换为它的对偶问题可得:

2). 首先固定α,也就是将α视为常数,要让L(w,b,α)关于w和b最小化,我们分别对w和b偏导数,令其等于0,即:

3). 将上述结果带回L(w,b,α)得到:

从上面的最后一个式子,我们可以看出,此时的L(w,α,b)函数只含有一个变量,即 $\alpha_i$。

4). 现在内侧的最小值求解完成,我们求解外侧的最大值,从上面的式子得到:

现在我们的优化问题变成了如上的形式。对于这个问题,我们有更高效的优化算法,即序列最小优化(SMO)算法。我们通过这个优化算法能得到α,再根据α,我们就可以求解出w和b,进而求得我们最初的目的:找到超平面,即”决策平面”。最终所求得的模型如下:

三、线性不可分与核函数

我们上面讨论的都是线性可分的SVM,线性可分也就是分割超平面和数据是在一个空间里。事实上,大部分时候数据并不是线性可分的,这个时候满足这样条件的超平面就根本不存在。对于非线性的情况,SVM 的处理方法是选择一个核函数 K() ,通过将数据映射到高维空间,来解决在原始空间中线性不可分的问题。

具体来说,在线性不可分的情况下,支持向量机首先在低维空间中完成计算,然后通过核函数将输入空间映射到高维特征空间,最终在高维特征空间中构造出最优分离超平面,从而把平面上本身不好分的非线性数据分开。

如下图所示,一堆数据在二维空间无法划分,从而映射到三维空间里划分:

0529_svm_no_linear.png

1. 映射x

为了完成这个目的,用 $\phi(x)$ 表示将 x 映射后的特征向量。于是,在特征空间划分超平面所对应的模型可表示为:$f(x)=w^T\:\phi(x)+b \: (5.1.1)$。对比一下上面的原始向量的模型:$f(x)=w^T\:x+b$,就是x映射成为$\phi(x)$。

同理公式(5.1.1)中引入拉格朗日乘子,求解整个方程后可得:

这里的这个 k(x_i,x) 就是我们所说的 核函数

再对比一下公式(2.4.3):$f(x) = \sum_{i=1}^m \alpha_i y_i x_i^T x + b$,其实这里的 $x_i^T x$也是一个核函数,称作 线性核

简单理解就是:非线性 SVM = 核技巧 + 线性 SVM。核技巧的本质就是简化运算。

2. 核函数

对于有限维的原始空间,一定存在更高维度的空间,使得前者中的样本映射到新空间后可分。但是新空间(特征空间)的维度也许很大,甚至可能是无限维的。这样的话,如在公式(5.1.2)中直接计算 $\phi(x_i)^T \phi(x)$ 就会很困难。

为了避免计算 $\phi(x_i)^T\phi(x)$的内积,我们需要设置一个新的函数$k(x_i,k_j)=\phi(x_i)^T\phi(x)$

原始空间中的两个样本 xi和 xj经过 k(.,.)函数计算所得出的结果,是它们在特征空间中映射成的新向量的内积。

如此一来,我们就不必真的计算出 $\phi(x_i)^T \cdot \phi(x)$ 的结果,而可以直接用 k(.,.)函数代替它们。这个函数 k(.,.) 就叫做核函数。现在我们正式给出它的正式定义:

设:X为原始空间(又称输入空间);H为特征空间(特征空间是一个带有内积的完备向量空间,又称完备内积空间或希尔伯特空间);

如果存在一个映射: $X \times X$,使得对所有 $x_i, x_j \in X$
,函数 k(x_i,x_j)满足条件:$k(x_i,k_j)=\phi(x_i)^T\phi(x)$
,即 k(.,.) 函数为输入空间中任意两个向量映射到特征空间后的内积。则称 k(.,.) 为 核函数,ϕ(⋅)为 映射函数

3. 非线性 SVM 的对偶问题

上面已经求出了线性 SVM 的对偶问题:公式(2.4.3)

于是非线性 SVM 的对偶问题就变为:

大家可以看到,和线性 SVM 唯一的不同就是:之前的 $x_i$与 $x_j$的内积(点乘) 变成了 $\phi(x_i)$与$\phi(x_j)$的内积。


参考:

  1. Python3《机器学习实战》学习笔记(八):支持向量机原理篇之手撕线性SVM

  2. 支持向量机的原理和实现

  3. 机器学习与数据挖掘-支持向量机(SVM)

  4. 支持向量机(SVM)是什么意思?

  5. 支持向量机通俗导论(理解SVM的三层境界)

  6. Support Vector Machines
    

  7. 零基础学SVM—Support Vector Machine(一)

THE END.

评论