机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

(写在前面:机器学习入行快2年了,多多少少用过一些算法,但由于敲公式太过浪费时间,所以一直搁置了开一个机器学习系列的博客。但是现在毕竟是电子化的时代,也不可能每时每刻都带着自己的记事本。如果可以掏出手机或iPad登陆网站就可以看到自己的一些笔记,才更有助于知识的巩固。借此机会,重新整理各大算法,希望自己能有更深的认识,如果有可能,也大言不惭的说希望能够帮助到需要帮助的朋友~)

(本篇博客内容来自台大林轩田老师Coursera Machine Learning Technology视频及周志华老师Machine Learning西瓜书,转载请标明出处

 一。SVM之起源(Support Vector Machine)

对于一个线性可分的数据集,使用感知器模型(PLA)可以得到一个线性的分类器:linear classifier: h(x) = sign(wTx)

但是PLA生成分类器的过程(如下图所示)是:

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

随机(Randomness)选取一个错误分类的数据点,更新分类器的参数。

但是这样的选择非常具有随机性,也就是说对于同一份数据集,每次用PLA算法训练的分类器可能都不一样,因此得到的分类器

可能如下图所示:

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

上图中的分类器都可能有PLA算法训练出来,但哪个是最好的呢?明眼人一看可能会说:第三个 !没错。为什么这样说呢?

因为,我们的数据集并不能总是保证是严格线性可分的,里面可能会有一些噪声,如果选择第一个或者第二个分类器的话,

随便一丢丢噪声分类器将会识别不出来!

所以说,如果距离分类超平面(hyperlane)最近的数据点的距离(margin)越大,该分类器的噪声容忍度就越大,也就是越robust。

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

于是,我们的目标就变为了:在保证所有训练数据分类正确的前提下,最大化距离分类超平面最小距离。

形式化的表示为:

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

二。SVM的标准形式之产生

有了上面的分析,下面我们就要来求任一点到分类超平面的距离,然后使最小距离最大化。

(1.)点到超平面的距离

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

假设超平面的方程为:wTx+ b = 0, 假设平面上的任意两点:x' 和 x'' ,则两点都满足 wTx= -b;  wTx'' = -b;

w为超平面的法向量,  则有  wT (x'' - x') = 0

那么,空间中的任意一点x到超平面的距离为x到超平面的一个向量到该超平面的单位法向量的投影,即:

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

所以,如果一个数据点与超平面的法向量同向,则乘积大于0;

如果一个数据点与超平面的法向量反向,则乘积小于0.

即: y(wTxn+b) > 0.

所以SVM问题可以表示为:

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

(2.)缩放(下面关于问题的缩放解释,将使用周老师西瓜书中的解释,个人感觉更加直观一些。)

将 y(wTxn+b) > 0 扩大一点,变为下图的形式(原谅我发射暖黄(?)光线的小台灯)

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

这样,margin = 2/||w||,而且只由边界上的点确定,这些点酒称为Support Vector.(这是个重要的结论,要牢记!!)

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

(3.)取倒数,将最大化问题变为最小化,得到如下SVM的标准形式:

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

三。使用QP解标准的SVM问题

通过以上的分析,我们得到了SVM的标准形式。那么,应该如何求解出参数w的最优解呢?

(1.)Gradient Decent?NoNoNo。因为这里是有s.t.条件的,无法找到一个下降的最优方向;

(2.)幸运的是,我们可以证明这个问题是convex凸函数

(3.)这类问题可以使用凸二次规划 quadratic programming(QP)的方法来求解。

求解方法如下:

QP的求解需要4个参数:Q(二次项系数), p(一次项系数), A(条件中的系数), c(条件中的常数)

将SVM的表达形式与之一一对应就可以了。得出四个系数之后,使用现在以后的计算包就可以轻而易举的解决SVM问题。

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

如果原始的数据资料集不是线性可分的怎么办?用Kernel Function将原始数据映射到线性空间中:zn = Φ(xn);

(4.)与Regularization的对比:

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

对于正则化来说,目标是最小化Ein,但是担心会overfitting,因此给出一定的限制条件;

对于SVM来说,目标是最小化wTw,但是限制是Ein = 0(或者稍微放松一下).

(两者的限制和目标刚好相反)

四。Dual SVM

动机:对于一般的SVM来说,如果我们的初始数据集不是线性可分的,这时我们会需要核函数将数据相高维度映射一下。

(一般的核函数变换都是低维度-》高维度)那么如果对于一个映射之后的数据,如果它的维度非常大,将会对我们的SVM的QP求解造成很大的困难。因此我们的目标

是希望将SVM的形式转化一下,在问题性质不变的前提小,使问题的求解仍然在原来的数据维度中。

(1.)Lagrange Multiplier(拉格朗日乘子法)

拉格朗日乘子法的思想是:将带限制条件的优化问题用拉格朗日乘子整合到一起,然后将新加入的乘子也作为未知参数

然后将问题分别求偏导。

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

所以,用Lagrange Multiplier表示General SVM就是如下形式:

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

可能会有疑问,为什么可以将General SVM表示成拉格朗日乘子法呢?

这里给出一点直观上的分析:

  • 目标是求w, b.
    • 如果通过Lagrange Multiplier求得的w, b不满足左边General SVM的条件,则1-yn(wTzn+b)>0, 而αn>=0,所以最大化L函数将会导致α趋向无穷;
    • 如果通过Lagrange Multiplier求得的w, b不满足左边General SVM的条件,则1-yn(wTzn+b)<0,而αn>=0,所以最大化L函数将会导致α趋向0.
    • 两者的目标是一致的!

对于L(b,w,α) = 1/2wTw + Σαn(1 - yn(wTzn+b)) 整体是一个二次函数,所以求一定条件下的最大值会非常麻烦,最好的办法是转化为求min。

下面的问题缩放的过程:

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

对上面图片的解释是:任意给出一个固定的α,则一堆α中最大的一定大于等于任意取出来的一个;

而对于取出的最好的一个α,所有的最大的中一定大于等于取出的这个最好的,所以,我们相当于将max, min换了一下位置。

将L(b, w, α)代入缩放后的式子:

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

对于上式,分别对b 和 w求偏导得:

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

然后将两个等式带回缩放后的式子,就得到了需要满足KKT condition(Karush-Kuhn-Tucker的Dual SVM:

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

然后像求解General SVM问题一样,用QP凸二次规划解Dual SVM问题,因此将系数对应过去就可以求的我们新加入的αn.(过程与General SVM的QP求解过程一致,这里不再赘述)

然后根据KKT条件的第三,第四个条件就可以求出w 与 b。

这里需要说明的一点:

  • 第四个条件:αn(1 - yn(wTzn+b)) = 0 中 要么αn = 0; 要么1 - yn(wTzn+b) = 0;
    • 再啰嗦一句:为什么会有这个条件呢?
      • 回到Lagrange Multiplier最初使用的地方:如果是不好的w, b,那么我们的式子会趋于无穷大;
      • 如果是好的w, b,那么我们的式子会趋于0,所有就得到了第四个条件的形式;
      • 这个条件是primal-inner optimal,是SVM本身就需要满足的一个条件,也称为complementary slackness条件。
    • 如果αn > 0,则我们才有办法求出b,而这时有1 - yn(wTzn+b) = 0 !!
      • 1 - yn(wTzn+b) = 0(αn > 0)意味着我们使用的这些点刚刚好在边界上(如那张黄黄的照片所示),就是support vector啊!
  • 满足αn > 0 的那些点在boundary上,称为support vector
  • w = Σαyz所以,只有support vector才会用来计算w;
  • b = yn - wTzn 所以,只有support vector才会用来计算b.

综上,SVM可以看作是这样一个问题:找出所有的support vector,然后用它们算出margin,其他的数据点一点都不重要。 

五。Kernel Support Vector Machine

对于一个线性不可分的资料,我们如果使用SVM作为分类器,则必须要使用Kernel function,将原来低维线性不可分的数据转换为高维线性可分的数据,所以直接使用SVM的QP求解方法将不可避免

的使用转换后的空间zn,如果zn维度特别高则会导致我们的计算非常复杂,因此想到使用Dual SVM来解决使用核函数的SVM来避免这种情况的发生。

那么,Dual SVM是如何避免在zn空间做计算的呢?

(1.)对于上面第四部分我们求出的QP求解的Dual SVM是如下形式:

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

可以看到,在求Q矩阵的时候需要zn与zn的内积,我们是否有比较简单的方法可以将它简化一下呢?

(2.)假设我们使用二次转换(多项式转换)将原来的数据集的各种表示形式列出来:

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

如图中红框内所示,只要我们需要求zn与zn的内积,我们都可以转化为在原来的数据空间中计算,所以对于二次转换来说,

相当于将O(d2)的时间计算复杂度降为了O(d)。

(3.)下面我们来看一下w与b的计算过程是否一样可以简化呢?

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

所以,但凡需要求zn与zn的内积,我们都将转换到x空间中计算!!!

综上,Dual SVM确实可以简化含有核函数的QP计算过程。

下面开始导出Polynomial Kernel。

上面我们使用了Φ2 = (1, x1, x2, ...., x12....., xd2), 如果在一次项或者二次项前面加入一些系数,就得到了Polynomial Kernel。

Φ2 = (1, √2r x1, √2r x2, ...., r x12....., r xd2)

更一般的形式写为:

K(x, x') = 1 + 2r xTx' + r2(xTx')2 = (1 + rxTx')2

则General Polynomial Kernel SVM为:

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

  • 需要注意的是,在Polynomial Kernel中有3个参数:ζ , γ 和 Q,其中Q来控制SVM的复杂度。
  • 与之前模型不同的是,在SVM世界中做10次的多项式会简单很多,确定ζ , γ就可以轻而易举的计算;
  • 但大家也会担心,太复杂的模型会不会overfitting?
    • 可能啊!但是SVM中有large margin的保证,会帮助我们稍微降低一下复杂度。

**************************我是分界线*****************************

通过Dual SVM的分析,我们可以巧妙的将问题转化一下,使之可以不用直接在高维度的z空间内做计算而是直接在原来的x空间内计算。

那么,我们不需要care x空间转换后的z空间的维度是多少。可不可以将它转换到一个无限维度的空间里呢?Of course!

假设对于只有一个维度的数据集x,我们使用高斯变换:

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

在第三步我们使用指数函数在0处的泰勒展开式,就把数据集映射到了无限维度里面,然后导出了我们需要的kernel的形式。

所以对于一般形式的Gaussian Kernel,我们加入一个γ作为控制高斯核SVM的参数,得到如下形式:

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

然后将Kernel代入SVM做决策的函数里面,就得到了:

机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

所以,Gaussian Kernel相当于将所有的Support Vector做高斯变换后的线性组合,

由于有这个性质,所以Gaussian Kernel也称为Radial Basis Function(RBF) Kernel.

但是使用Gaussian SVM特别需要注意γ的使用,因为大的γ会导致SVM更复杂,也就更容易overfitting,所以一定要慎用!

**************************我是分界线*****************************

比较Linear Kernel, Polynomial Kernel, Gaussian Kernel

  • Linear Kernel:K(x, x') = xTx'
    • 优点是:
      • safe(一般不太会overfitting,所以线性的永远是我们的首选方案);
      • fast,可以直接使用General SVM的QP方法来求解,比较迅速;
      • explainable,可解释性较好,我们可以直接得到w, b,它们直接对应每个feature的权重。
    • 缺点是:
      • restrict:如果是线性不可分的资料就不太适用了!
  • Polynomial Kernel: K(x, x') = (ζ + γxTx')Q
    • 优点是:
      • 我们可以通过控制Q的大小任意改变模型的复杂度,一定程度上解决线性不可分的问题;
    • 缺点是:
      • 含有三个参数,太多啦!
  • Gaussian Kernel:K(x, x') = exp(-γ ||x - x'||2)
    • 优点是:
      • powerful:比线性的kernel更powerful;
      • bounded:比多项式核更好计算一点;
      • one  parameter only:只有一个参数
    • 缺点是:
      • mysterious:与线性核相反的是,可解释性比较差(先将原始数据映射到一个无限维度中,然后找一个胖胖的边界,将所有的数据点分隔开?)
      • too powerful!如果选择了太大的γ,SVM希望将所有的数据都分开,将会导致产生太过复杂的模型而overfitting。

所以在实际应用中,一般是先使用线性的kernel,如果效果不好再使用gaussian kernel(小的γ)和多项式kernel(小的Q)。

**************************我是分界线*****************************

如何自己来定义kernel呢?kernel应该满足什么样的条件呢?

首先回到kernel的意义上。

  • kernel具有什么含义呢?
    • 实际是内积,表示的是两个数据点 x 和 x' 转换到z空间后的相似性
  • 所以,什么样的是valid kernel呢?需要满足Mercer's consition:
    • symmetric
    • 核矩阵满足半正定性(positive semi-definite)
    • 核矩阵是指:
      • 机器学习——SVM详解(标准形式,对偶形式,Kernel及Soft Margin)

所以,满足了以上条件就可以定义自己的kernel function了~

六。Soft Margin Support Vector Machine

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

线性不可分

线性不可分意味着某些样本点$(x_{i}, y_{i})$不能满足函数间隔大于等于1的约束条件 -- $y_{i}(w^{T}x_{i}+b) \ge 1$. 所以对每个样本点,引入一个松弛变量$\xi_{i} \ge 0$, 使函数间隔加上松弛变量大于等于1,这样约束条件变为:
$y_{i}(w^{T}x_{i}+b) \ge 1 - \xi_{i}$,
同时,对于每个松弛变量$\xi_{i}$,要付出一个代价,目标函数由原来的$\frac{1}{2}\lVert w \rVert^{2}$变为:
$\frac{1}{2}\lVert w \rVert^{2} + C\sum_{i=1}^{N}\xi_{i}$
其中,C>0为惩罚参数。C越大表示对错误分类的惩罚力度越大,越小则表示惩罚力度越小。
目标函数表达的含义有:使$\frac{1}{2}\lVert w \rVert^{2}$尽量小即间隔尽量大,同时使误分类点的个数尽量小。


Soft Margin SVM的标准形式
$min_{w, b, \xi}\frac{1}{2}\lVert w \rVert^{2} + C\sum_{i=1}^{N}\xi_{i}$
$s.t. y_{i}(w^{T}x_{i} + b) \ge 1 - \xi_{i}, i = 1,2,3...,N$
$s.t. \xi_{i} \ge 0$

(未完待续)

上一篇:[转帖]Linux教程(21)-Linux条件循环语句


下一篇:linux目录