machine learning / 机器学习

支持向量机

支持向量机

1.间隔(margin)与支持向量(support vector):

给定训练样本集

在样本空间中找到一个超平面,将不同类别的样本分开。

划分超平面通过如下线性方程描述:

其中 为法向量,决定超平面的方向,b为位移项,决定了超平面与原点间的距离。

样本空间中任意点x到超平面(w,b)的距离可写为:

该公式和中学学过的点到直线距离公式如出一辙。亦可用法向量内积推导。

假设该超平面能正确对训练集分类,那么有(人为规定的没什么为什么):

距离超平面最近的几个训练样本点使上述公式成立,即样本点在边界上使得 (下图虚线),它们被称为支持向量。

两个异类支持向量到超平面的距离之和为

它被称为间隔。

.

.

.

.

.

找到具有最大间隔(maximum margin)的划分超平面,即

等价于最小化:

s.t.的含义是subject to ,即受约束。

通过 可以避免用绝对值表示距离的问题,该公式永远为正。

这就是支持向量机(Support Vector MachineSVM)的基本型。

.

2.对偶问题(dual problem

求解 是一个凸二次优化问题(凸优化,目标函数二次)(quadratic programming)。可用现成的QP优化包求解。

但是对于处理大数据来说,算法越高效越好,因此通过引入拉格朗日乘子法(Lagrange multiplier)将QP问题变换为对偶问题(dual problem)可以更加高效的求解。

拉格朗日乘子可以把约束条件(即 )融合到目标函数中,这样求解最优化问题会更容易。

其中

wb求极值(偏导为0)可得:

代入

可得

同时因为 因此有约束

这样原先 需要求三个变量,现在只需要求一个变量α即可。

解出α后,再代入 求出wb

可得出如下模型:

由于 有不等式约束 ,因此上述过程需满足KKTKarush-Kuhn-Tucker)条件,即:

  • 因此如果αi=0,则该样本不会在 中出现,因为会导致f(x)=b,也就不会对f(x)产生任何影响。

  • 如果αi>0,则 ,即该样本位于最大间距边界上,是一个支持向量。

这两个特性意味着,训练完成后,大部分训练样本都不需要保留,只要保留支持向量即可,这样如果是大数据的环境,该算法对磁盘和内存的占用率会非常的低。

.

3.SMOsequential minimal optimization)算法

通过 求解αi有许多种优化算法,最常用的一种叫SMO,其原理是每次选取两个α,固定其它α(视为常量),通过极值计算求得α的最佳值,然后依次将所有α进行这样的计算。该方法比每次迭代都计算所有α要提高很多效率。个人感觉这个算法和随机梯度下降算法有异曲同工之妙。

具体算法建议自行百度一下,计算比较复杂,有机会我再整理上来。

.

4.核函数(kernel function

假如我们的样本集分布如下图所示,很显然无法找到一个可以将其划分的超平面。

.

.

.

.

.

对这样的问题,可将样本从原始空间映射到一个更高维的特征空间,使得样本在这个特征空间中线性可分。

Φ(x)表示将x映射后的特征向量,于是在特征空间中划分超平面的特征模型可表示为:

对偶问题可表示为:

求解式涉及到计算 ,这是xixj映射到特征空间的内积,由于特征空间维度可能很高,甚至无穷,因此直接计算 是困难的。为了避开这个障碍,假设有如下函数:

xixj映射到特征空间的内积等于它们在原始样本空间中通过函数计k(·,·)算的结果,这样就可以避免计算高维甚至无穷维特征空间中的内积

因此对偶问题又可以表示为:

求解后可得

这里的函数k(·,·)就是核函数。这一项式亦称作“支持向量展开式”(support vector expansion

核函数定义了特征空间,称为“再生核希尔伯特空间”(Reproducing Kernel Hilbert Space 简称RKHS),这部分内容建议自行百度,非常大的篇幅。特征空间的好坏对SVM的性能至关重要,因此选择合适的核函数很重要。

下面列出常见核函数

名称

表达式

参数

线性核

多项式核

d≥1为多项式的次数,d=1时为线性核

高斯核

σ>0为高斯核的带宽

拉普拉斯核

σ>0

Sigmod

tanh为双正切函数,β>0θ>0

  • k1k2为核函数,则对任意正数γ1γ2,其线性组合k1γ1+k2 γ2也是核函数。

  • k1k2为核函数,则核函数的直积 也是核函数。

  • k1为核函数,则对于任意函数g(x) 也是核函数

    .

5.软间隔(soft margin

我们一直假定训练样本在样本空间和特征空间中是线性可分的,然而现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分。即便恰好找到某个核函数使得训练集线性可分,也很难断定这个结果不是由于过拟合造成的。

缓解该问题的一个办法是允许SVM在一些样本上出错,因此引入软间隔概念(之前那种全部正确划分的叫硬间隔)。

软间隔允许某些样本不满足约束 ,但最大化间隔时应尽量保证不满足的样本数量少,优化目标可写为:

其中C是常数,l0/10/1损失函数(0-1 loss function):

(公式工具问题右边的花括号忽略它)

C无穷大时,必然只有让l0/1(z)=0才能保证最小化,这时就需要满足z≥0,即

所以当所有样本都满足约束条件时, 等价于

C取有限值时,则允许一些样本不满足约束。

由于l0/1非凸、非连续,不易求解,于是可以采用其他函数替代l0/1,称作“替代损失”(syrrogate loss)。

常用的替代损失函数有:

名称

表达式

hinge损失

指数损失

对率损失

.

.

2016.10.25 完成支持向量机基本型内容

2016.10.27 完成核函数内容

本文内容参考李航老师、ng和周志华老师的书籍,结合自己的理解,所有公式全部为本人推导,并进行整合勘误。转载请注明出处。

Leave a Reply

Your email address will not be published. Required fields are marked *