支持向量机
支持向量机(Support Vector Machine)是 Cortes 和 Vapnik 于 1995 年首先提出的,它在解决小样本、非线性及高维模式识别中表现出许多特有的优势,并能够推广应用到函数拟合等其他机器学习问题中。
最简单的 SVM 从线性分类器导出,根据最大化分类间隔的目标(Large Margin Classifier),我们可以得到线性可分问题的 SVM 训练时求解的问题(Hard SVM)。但现实应用中很多数据是线性不可分的,通过加入松弛变量和惩罚因子,可以将 SVM 推广到线性不可分的情况(Soft SVM)。这个优化问题是一个凸优化问题,并且满足 Slater 条件,因此强对偶成立,通过拉格朗日对偶可以将其转化成对偶问题求解(Dual Soft SVM)。到这里为止,支持向量机还是一个线性模型,只不过允许有错分的训练样本存在。通过核函数(Kernel Trick),可以将它转化成非线性模型,此时的对偶问题也是一个凸优化问题(Soft Kernel SVM)。这个问题的求解普遍使用的是 SMO 算法,这是一种分治法,它每次选择两个变量进行优化,这两个变量的优化问题是一个带等式和不等式约束条件的二次函数极值问题,可以求出公式解,并且这个问题也是凸优化问题。优化变量的选择通过 KKT 条件来确定。
I. 统计学习理论
支持向量机方法是建立在统计学习理论的 VC 维理论和结构风险最小原理基础上的,根据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度,Accuracy)和学习能力(即无错误地识别任意样本的能力)之间寻求最佳折衷,以期获得最好的推广能力(或称泛化能力)。
统计机器学习能够精确的给出学习效果,能够解答需要的样本数等等一系列问题。
- VC 维是对函数类的一种度量,可以简单的理解为问题的复杂程度,VC 维越高,一个问题就越复杂。正是因为 SVM 关注的是 VC 维,SVM 解决问题的时候,和样本的维数是无关的(甚至样本是上万维的都可以。当然,有这样的能力也因为引入了核函数)。
- 机器学习本质上就是一种对问题真实模型的逼近(我们选择一个我们认为比较好的近似模型,这个近似模型就叫做一个假设)。既然真实模型不知道,那么我们选择的假设与问题真实解之间究竟有多大差距(称为风险),我们就没法得知。但我们可以用某些可以掌握的量来逼近它。
- 最直观的想法就是使用分类器在样本数据上的分类的结果与真实结果之间的差值来表示,这个差值叫做经验风险
。 - 以前的机器学习方法都把经验风险最小化作为努力的目标,但回头看看经验风险最小化原则我们就会发现,此原则适用的大前提是经验风险要确实能够逼近真实风险才行。因此很多分类函数能够在样本集上轻易达到 100% 的正确率,在真实分类时却一塌糊涂(即所谓的推广能力差,或泛化能力差)。
- 统计学习因此而引入了泛化误差界的概念,就是指真实风险应该由两部分内容刻画,一是经验风险,代表了分类器在给定样本上的误差;二是置信风险,代表了我们在多大程度上可以信任分类器在未知文本上分类的结果。很显然,第二部分是没有办法精确计算的,因此只能给出一个估计的区间,也使得整个误差只能计算上界,而无法计算准确的值(所以叫做泛化误差界,而不叫泛化误差)。统计学习的目标从经验风险最小化变为了寻求经验风险与置信风险的和最小,即结构风险最小。SVM 正是这样一种努力最小化结构风险的算法。
- 置信风险与两个量有关,一是样本数量,显然给定的样本数量越大,我们的学习结果越有可能正确,此时置信风险越小;二是分类函数的 VC 维,显然 VC 维越大,推广能力越差,置信风险会变大。
- 最直观的想法就是使用分类器在样本数据上的分类的结果与真实结果之间的差值来表示,这个差值叫做经验风险
小样本,并不是说样本的绝对数量少(实际上,对任何算法来说,更多的样本几乎总是能带来更好的效果),而是说与问题的复杂度比起来,SVM 算法要求的样本数是相对比较少的。
非线性,是指 SVM 擅长应付样本数据线性不可分的情况,主要通过松弛变量(也有人叫惩罚变量)和核函数技术来实现,这一部分是 SVM 的精髓。
II. SVM
支持向量机属于一般化线性分类器,这族分类器的特点是他们能够同时最小化经验误差与最大化几何边缘区,因此支持向量机也被称为最大边缘区分类器。除了进行线性分类之外,SVM 还可以使用所谓的核技巧有效地进行非线性分类,将其输入隐式映射到高维特征空间中。
SVM 本身是从感知机算法演变而来,往简单来说其实就只是改了感知机的损失函数而已,而且改完之后还很像。感知机算法是在一个线性可分的数据集中找到一个分类超平面,尽可能的将数据集划分开。
理论上这样的超平面有无数多个,但是从直觉上,我们知道离两侧数据都比较远的超平面更适合用于分类,于是我们选择了一个比较 “胖” 的边界的超平面作为分类界,这就是 SVM。 SVM 本身 “只是” 一个线性模型。只有在应用了核方法后,SVM 才会 “升级” 成为一个非线性模型
因此,支持向量机 - SVM (Support Vector Machine) 从本质来说是一种:用一条线(方程)分类两种事物。SVM 的任务是找到这条分界线使得它到两边的 margin(构成了两条平行于分离超平面的长带,二者之间的距离称之为 margin)都最大。注意,这里的横坐标是
如上图所示,在 Maximum Margin 上的这些点就是支持向量(将距离分离超平面最近的两个不同类别的样本点称为支持向量),具体说即最终分类器表达式中只含有这些支持向量的信息,而与其他数据点无关。在下面的公式中,只有支持向量的系数
图中带黑圈的样本点即是支持向量,数学上来说的话,就是
这里有一个视频解释可以告诉你最佳的超平面是如何找到的 1:直观可视化解释。
对于我们需要求解的这个超平面(直线)来说,我们知道它离两边一样远(待分类的两个部分的样本点),最近的距离就是到支持向量中的点的距离。根据这两点,抽象 SVM 的直接表达(Directly Representation):
注:
表示当 取最大值时,x 的取值。
II.I. 背景知识
假设样本为 (x,y),超平面为
- 空间上的点:
, 指的是点的数量, 表示的是 维空间 - 分界线:
,简化为
- 向量的形式更加简洁,特别是在高维空间的情况下,还有一个好处就是,矢量的形式下
刚好与分界线垂直,这个性质会在后面用到。 表示的是分界线上所有的点,当 时,表示的是分界线上方的区域,反之则是分界线下方的区域。 - 优化问题
,使得 的求解过程常称为硬间隔最大化,求解出来的超平面则常称为最大硬间隔分离超平面 - 优化问题
,使得 的求解过程常称为软间隔最大化,求解出来的超平面则常称为最大软间隔分离超平面 - 若数据集线性可分,则最大硬间隔分离超平面存在且唯一
- 若数据集线性不可分,则最大软间隔分离超平面的解存在但不唯一,其中:法向量(w )唯一,偏置量(b)可能不唯一
II.I.I. 函数间隔
- 样本到超平面的函数间隔为:
由二维直线
函数间隔:超平面
定义超平面关于样本集 S 的函数间隔为超平面
定义
II.I.II. 几何间隔
- 样本到超平面的几何间隔为:
II.I.II.I. 解释一
设样本点 A 坐标为
如果点被正确分类,
超平面与样本集 S 的几何间隔为
II.I.II.II. 解释二
我们在定义点 (x,y) 到平面(超平面)
- 将
(垂直)投影到 上 - 设投影点为
,则定义 .
注意这里我们允许(当样本被错分类时的)间隔为负数,所以间隔其实严格来说并不是一般意义上的距离。
那么为了找到垂直投影,我们得先找到垂直于超平面
那么结合之前那张图,不难得知我们可以设
从而
注意这么定义的间隔有一个大问题:当 w 和 b 同时增大 k 倍时,新得到的超平面
但此时
所以我们需要把 scale 的影响给抹去,常见的做法就是做某种意义上的归一化:
(注意:由于 scale 的影响已被抹去,所以
不难看出上式可改写为:
这正是我们想要的结果。
II.I.III. 间隔最大化
支持向量机的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。为了间隔最大化,只需要最大化几何间隔
上述问题,可以转变为一个凸二次规划问题,这是支持向量机的一个重要属性,局部极值即为全局最值。
考虑函数间隔与几何间隔的关系:
当超平面参数
II.I.IV. 感知机模型
感知机模型只有
训练方法则是梯度下降,其中梯度公式为:
我们在实际实现时,采用了 “极大梯度下降法”(亦即每次只选出使得损失函数最大的样本点来进行梯度下降)。然后有理论证明,只要数据集线性可分,这样下去就一定能收敛。
1 | for _ in range(epoch): |
II.I.V. 优化问题的等价性
为方便,称优化问题:
为问题一;称:
为问题二,则我们需要证明问题一与问题二等价
先来看问题一怎么转为问题二。事实上不难得知:
注意问题一是针对 w 和 b 进行优化的,且当 w 和 b 固定时,为使
时, 时, (因为我们要求 )
亦即
再来看问题二怎么转为问题一。事实上,直接令
- 模型的损失为
- 模型的约束为
亦即转为了问题一
II.I.VI. 带约束的二次规划求解
不妨设我们选取出来的两个参数就是
注意到我们的对偶问题为
使得对
Gram 矩阵:
所以 L 就可以改写为
把和
约束条件则可以化简为对 i=1 和 i=2,都有
而带约束的二次规划求解过程也算简单:只需先求出无约束下的最优解,然后根据约束 “裁剪” 该最优解即可。
无约束下的求解过程其实就是求偏导并令其为 0。以
令
于是
考虑到
令
于是
注意到
令
从而
接下来就要对其进行裁剪了。注意到我们的约束为
- 当
, 异号( )时,可知 为常数、亦即 ,结合 ,可知: 不应小于 ,否则 将小于 0 不应大于 ,否则 将大于
- 当
, 同号( )时,可知 为常数、亦即 ,结合 ,可知: 不应小于 ,否则 将大于 不应大于 ,否则 将小于 0
综上可知
的下界为 的上界为
那么直接做一个 clip 即可得到更新后的
1 | alpha1_new = np.clip(alpha1_new_raw, u, v) |
注意由于我们要保持
综上所述,我们就完成了一次参数的更新,之后就不断地更新直至满足停机条件即可
II.II. Hard Linear SVM
注意我们感知机的损失函数为
从直观上来说,我们希望得到的是这样的决策面:
那么应该如何将这种理想的决策面的状态翻译成机器能够学习的东西呢?直观来说,就是让决策面离正负样本点的间隔都尽可能大。
首先定义超平面:
因此,这个 “间隔” 翻译成数学语言,其实就是简单的:
在有了样本点到决策面的间隔后,数据集到决策面的间隔也就好定义了:
如果这些训练数据是线性可分的,也可称为硬间隔(Hard Margin)。选出两条直线(图中的虚线),使得他们的距离尽可能的大,这两条直线的中央就是待求的超平面(直线)。为了表达直观,我们定义这两个超平面(直线)分别为
为了使得所有样本数据都在间隔区(两条虚线)以外,我们需要保证对于所有的
上面的表达(Directly Representation)可以被写成:让所有样本点都被正确分类:
注意到
我们知道同时放缩一个超平面的系数并不会改变这个超平面,such as 3wx+3b=0=wx+b,所以我们可以假设离我们超平面最近的那个向量到平面的距离为 1。选择 1 的好处是,w 和 b 进行尺缩变换(kw 和 kb)不改变距离,方便计算。
所以我们完全可以假设:若
注意由于
所以
则可以对
注:s.t.:subject to 表示约束条件,表达的意思等价于:为了使得所有样本数据都在间隔区(两条虚线)以外。
但是这会导致另一个问题:当数据集线性不可分时,上述优化问题是必定无解的,这就会导致模型震荡(换句话说,
II.III. Dual Linear SVM
为什么我们还要考虑它的对偶问题?这是因为化作对偶问题后会更容易求解,同样也方便引入 Kernel Trick。表现在 SMO 上的话就是,我们可以通过简单粗暴地将核矩阵 K 代替 Gram 矩阵 G 来完成核方法的应用。直观地说,我们只需将上面所有出现过的
为了解
根据约束的形式,我们引入 m 个拉格朗日乗法子,记为
根据拉格朗日对偶性,原始的约束最优化问题可等价于极大极小的对偶问题:
解这个拉格朗日方程,对
将这两个条件带回公式 (4),可以得到对偶形式(dual representaiton),我们的目的也变为最大化
等价于最优化问题:
以上表达式可以通过二次规划算法解出
这显然又是一个二次规划问题!所
使用这些条件,可以构建高效算法来解这个方程,比如 SMO(Sequential Minimal Optimization)就是其中一个比较著名的,这就是对偶问题的求解方案。至于 SMO 是如何做的,考虑到现代很多 SVM 的 Pakage 都是直接拿来用,秉承着前人付出了努力造了轮子就不重复造的核心精神,直接调用就好 。
II.IV. Soft Linear SVM
上面的例子很简单,因为那些数据是线性可分的 —— 我们可以通过画一条直线来简单地分割红色和蓝色。然而,大多数情况下事情没有那么简单。如果样本数据你中有我我中有你(线性不可分),应该如何处理呢?你无法找出一个线性决策边界(一条直线分开两个类别)。这里就需要引入软间隔(Soft Margin),意味着,允许支持向量机在一定程度上出错。
由上一节我们得知,约束为:
对于
三种常见损失函数如下图:
我们已知 Hard LinearSVM 问题为
且式中的
所以为了让模型在线性不可分的数据上仍有不错的表现,从直观来说,我们应该 “放松” 对我们模型的限制(让我们模型的约束 “软” 一点),引入松弛变量(slack variables) :
正如前文所说,只放松限制的话肯定不行,会使模型变得怠惰,还得给这个放松一些惩罚。若假设数据集为
其中 “
综上所述,在目标优化函数中加一个
不难得知原始问题相应的拉格朗日函数为:
其中
于是 KKT 条件的其中四个约束即为(不妨设最优解为
, (这是拉格朗日乘子法自身的要求) 、 (此即原始约束) (换句话说, 和 中必有一个为 0)- 该等式有着很好的直观:设想它们同时不为 0,则必有
(注意原始约束)、从而 ,等号当且仅当 时取得。然而由于 ,所以若将 取为 0、则上述 L 将会变大。换句话说,将参数 取为 0 将会使得目标函数比参数取 时的目标函数要大,这与 的最优性矛盾 -
换句话说, 和 中必有一个为 0,理由同上)
对偶问题的实质,其实就是将原始问题
转化为对偶问题
于是我们需要求偏导并令它们为 0:
- 对
求偏导: - 对
求偏导: - 对
求偏导:
后一个 KKT 条件:最优解自然需要满足这么个条件:
注意这些约束中
于是对偶问题为
亦即
可以看到在对偶形式中,样本仅以内积的形式
通过构造拉格朗日函数并求解偏导可得到等价的对偶问题:
II.V. Soft Linear SVM 的训练
虽然比较简单,但是调优 LinearSVM 的训练这个过程是相当有启发性的事情。关于各种梯度下降算法的定义、性质等等可以参见参数的更新。
II.V.I. 极大梯度下降法
极大梯度下降法其实就是随机梯度下降 SGD 的特殊形式。
我们已知:
所以我们可以认为:
于是:
- 当
时: 、 - 当
时: 、
所以我们可以把极大梯度下降的形式写成(假设学习速率为
若
1 | import numpy as np |
虽然看上去不错,但仍然存在着问题:
- 训练过程其实非常不稳定
- 从直观上来说,由于 LinearSVM 的损失函数比感知机要更复杂,所以相应的函数形状也会更复杂。这意味着当数据集稍微差一点的时候,直接单纯地应用极大梯度下降法可能会导致一些问题 —— 比如说模型会卡在某个很奇怪的地方无法自拔。解释 1:每次只取使得损失函数极大的一个样本进行梯度下降
通过将正负样本点的 “中心” 从原点 (0, 0)(默认值)挪到 (5, 5)(亦即破坏了一定的对称性)并将正负样本点之间的距离拉近一点,我们可以复现这个问题:
II.V.II. Mini-Batch 梯度下降法(MBGD)
解决方案的话,主要还是从改进随机梯度下降(SGD)的思路入手(因为极大梯度下降法其实就是 SGD 的特殊形式)。我们知道 SGD 的 “升级版” 是 MBGD、亦即拿随机 Mini-Batch 代替随机抽样。这样的话,通常而言会比 SGD 要好 。
1 | self._w *= 1 - lr |
但是问题仍然是存在的:那就是它们所运用的梯度下降法都只是朴素的 Vanilla Update,这会导致当数据的 scale 很大时模型对参数极为敏感、从而导致持续的震荡(所谓的 scale 比较大,可以理解为 “规模很大”,或者直白一点 —— 以二维数据为例的话 —— 就是横纵坐标的数值很大)。
II.VI. Kernel Trick
注意,核函数技巧实际上并不是 SVM 的一部分。它可以与其他线性分类器共同使用,如逻辑回归等。支持向量机只负责找到决策边界。
以上我们求解的支持向量机都是在线性情况下的,那么非线性情况下如何处理?这里就引入:核方法 2。
核方法是将一个低维的线性不可分的数据映射到一个高维的特征空间、并期望映射后的数据在高维特征空间里是线性可分的。
至此,似乎问题就转化为了如何寻找合适的映射
而核方法的巧妙之处就在于,它能将构造映射这个过程再次进行转化、从而使得问题变得简易:它通过核函数来避免显式定义映射
假设
其中:
在这个例子中,映射后特征的内积和原始特征的内积的平方是等价的。 也就是说, 我们只需要计算原始特征的内积再进行平方就可以了,并不需要先得到映射后的特征再计算映射后特征的内积。计算原始特征内积的时间复杂度为
映射函数
看一下这个列子:
相比于从低维映射到高维空间再进行矢量积运算,核函数大大简化了计算的过程,使得向更高维转化变为了可能,我们不需要知道低维空间的数据是怎样映射到高维空间的,我们只需要知道结果是怎么计算出来的。
我们再来看另一个 kernels:
更广泛的来说,我们有:
核方法的思想如下:
- 将算法表述成样本点内积的组合(这经常能通过算法的对偶形式实现)
- 设法找到核函数
,它能返回样本点 被 作用后的内积 - 用
替换 、完成低维到高维的映射(同时也完成了从线性算法到非线性算法的转换)
如果我们有一个新的问题我们该如何构造一个 kernel?假设我们有映射后的特征向量
我们再来看一个 kernel:
这个 kernel 应该挺符合上面的想法吧。这个 kernel 长得像高斯分布,我们一般叫他高斯 kernel,也可以叫 Radial basis funtction kernel,简称 RBF 核。
下面有张图说明在低维线性不可分时,映射到高维后就可分了,使用高斯核函数。
II.VI.I. 核函数有效性判定
并不是所有的函数
幸运的是,1909 年提出的 Mercer 定理解决了这个问题。Mercer 定理为寻找核函数带来了极大的便利。如果
Mercer 定理:函数
是 上的映射。如果 是一个有效的 (Mercer) Kernel, 那么当且仅当对于任意 , 相应的 kernel matrix 是半正定的。
那么核方法的应用场景有哪些呢?在 2002 年由 Scholkopf 和 Smola 证明的表示定理告诉我们它的应用场景非常广泛。
II.VII. Kernel SVM
因此,SVM 其实并不需要真正的向量,它可以用它们的数量积(点积)来进行分类。核函数可以减少大量的计算资源需求。通常,内核是线性的,所以我们得到了一个线性分类器。但如果使用非线性内核,我们可以在完全不改变数据的情况下得到一个非线性分类器:我们只需改变点积为我们想要的空间,SVM 就会对它忠实地进行分类。这意味着我们可以避免耗费计算资源的境地了。(直观可视化解释)。
为了完成这个目的,令
在 SVM 的等价对偶问题中的目标函数中有样本点的内积
同理上文中引入拉格朗日乘子,求解整个方程后可得:
注意,使用核函数后,怎么分类新来的样本呢?是否先要找到
这里的函数
名称 | 表达式 | 参数 |
---|---|---|
线性核 | |
无 |
多项式核 | |
|
高斯核 | |
|
拉普拉斯核 | |
|
Sigmoid 核 | |
II.VII.I. 感知器核方法
怎么应用核方法?简单来说,就是把算法中涉及到样本(
感知机的原始损失函数为
为了让损失函数中的样本都变成内积形式,考虑令
在此之上应用核方法是平凡的:设核函数为
于是优化问题变为
预测步骤则变为
当我们对感知机应用核方法后,它就能对非线性数据集(比如螺旋线数据集)进行分类了 。
II.VII.II. Soft Kernel SVM
将其代入一般化的 SVM 学习算法的目标函数中,可得非线性 SVM 的最优化问题:
预测步骤则仍然是:
II.VIII. 核方法的训练
SMO 算法的效果
III. SVR
对 SVM 解回归问题,进行分析。
IV. 扩展应用
当数据未被标记时,不能进行监督式学习,需要用非监督式学习,它会尝试找出数据到簇的自然聚类,并将新数据映射到这些已形成的簇。将支持向量机改进的聚类算法被称为支持向量聚类,当数据未被标记或者仅一些数据被标记时,支持向量聚类经常在工业应用中用作分类步骤的预处理。
V. MATLAB 实现
得到数值 temp1:
1 | cmd = ['-v ',num2str(v),' -c ',num2str(ga_bestc),' -g ',num2str(ga_bestg),' -s 3 -p 0.01']; |
得到训练的模型 temp2:
1 | cmd = ['-t 2',' -c ',num2str(ga_bestc),' -g ',num2str(ga_bestg),' -s 3 -p 0.01']; |
livsvm 的 svr 验证:
1 | % 训练集输入 |
VI. SVM 参数优化
In support vector machines (SVM) how can we adjust the parameter C?
C is a trade-off between training error and the flatness of the solution. The larger C is the less the final training error will be. But if you increase C too much you risk losing the generalization properties of the classifier, because it will try to fit as best as possible all the training points (including the possible errors of your dataset). In addition a large C, usually increases the time needed for training.
If C is small, then the classifier is flat (meaning that its derivatives are small - close to zero, at least for the gaussian rbf kernel this is substantiated theoretically). You have to find a C that keeps the training erro small, but also generalizes well (i.e., it doesn't have large fluctuations). There are several methods to find the best possible C automatically, but you must keep in mind that this depends on the application you are interested in.
Related Issues not found
Please contact @sli1989 to initialize the comment