Perenial youth.

一天一个机器学习概念(四)——支持向量机(SVM)

一天一个机器学习概念(四)——支持向量机(SVM)

目录:

  1. 线性可分情况下的SVM
  2. 线性不可分情况下的SVM(线性SVM)
  3. 非线性情况下的SVM(核技巧)

为了质量,还是保证一周至少三次更新吧,一天一更有点吃不消,还要更新NLP Seminar的内容。。Seminar里的内容主要是深度学习为主,目前包括了DNN,反向传播,RNN,LSTM,Seq2seq,attention等干货,欢迎阅读

首先,来看支持向量机的描述:

“支持向量机(support vector machines, SVM)是一种二类分类模型,它的基本模型是定义在特征空间上的间隔最大的线性分类器,间隔最大使它有别于感知机;支持向量机还包括核技巧,这使它成为实质上的非线性分类器,支持向量机的学习策略就是间隔最大化,可形式化为一个求解凸二次规划(convex quadratic programming)的问题,也等价与正则化的合页损失函数的最小化问题,支持向量机的学习算法是求解凸二次规划的最优化算法”
————李航《统计学习方法》

最简单的svm,即线性可分支持向量机,是与感知机很类似的。另外,由于一些特殊的技巧,例如软间隔最大化核技巧,svm具备分类非线性可分数据的能力。

线性可分情况

让我们从最简单的线性可分支持向量机说起。上面我们说到,最简单的svm和perceptron很类似,二者都是对线性可分的数据进行分类的线性分类器,也就是都是要找到超平面分隔开数据。不同之处在于,二者的损失函数不同,学习策略也不同。perceptron利用误分类最小的策略,因此随着sgd时点的顺序不同,找到的直线也不同,解有无穷多个;svm则利用间隔最大化求最优分离超平面,解是唯一的。说白了,感知机要求分的对,线性可分svm不仅要求分的对,还要求分的好。

那么再来说一下函数间隔和几何间隔的事情。svm的损失函数就是几何间隔,而几何间隔是由函数间隔导出的。其实很好理解啦。函数间隔我们已经见过,和感知机中一样:

几何间隔也很好理解,就是几何距离啦:

感知机选用函数间隔作为损失函数的base,svm则选用几何间隔。同时,感知机的策略是一旦没有误分类就停止学习,感知机则是要找到几何间隔最大的超平面。

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

知道了我们的目标是找到最大间隔超平面,下一个问题就是:该怎么找呢?这个问难题可以表示为约束最优化问题:

r是超平面关于训练数据集的几何间隔;约束条件表示超平面(w,b)关于每个训练样本点的几何间隔至少是r

考虑几何间隔和函数间隔的关系式,可再将问题改写为:

容易看出,r并不影响最优化问题的解。事实上,假设将w和b按比例改变就可以消去r。因此问题可以再次转化为:

这就是一个凸优化问题了。根据优化理论的知识(应用拉格朗日对偶性求解对偶问题得到原始问题的最优解),求解w,b即可。

因此,svm的学习算法——最大间隔法就出来了,过程如下:

关于这里的约束最优化问题如何求解,一般的方法是拉格朗日对偶性求解,也就是将原问题转化为一个对偶问题。经过转化后的学习算法步骤如下(证明略过):


上面这里的\(a^*\)的一个正分量\(a_i^*\)其实对应着下面要说的支持向量

说一下支持向量的概念:训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量。换言之,支持向量就是使约束条件等号成立的点,即\(y_i(w \cdot x_i + b) – 1 = 0\),如图所示

其中\(H_1 H_2\)称为间隔边界,之间的距离称为间隔(margin),间隔依赖于分离超平面的法向量w。

事实上,在决定分离超平面时,只有支持向量起作用,其它实例点并不起作用;移除其它实例点解是不会改变的(因为我们一开始max的就是距离超平面最近的点)。也正是因为如此,才有“支持向量机”这个名字。

线性不可分情况

说完了最简单的线性可分情况,我们再说一下如何扩展到线性不可分的问题。此时,就需要修改硬间隔最大化,使其成为软间隔最大化。

线性不可分意味着某些样本点\((x_i, y_i)\)不能满足函数间隔大于等于1的约束条件。为了结局这个问题,可以对每个样本点\((x_i,y_i)\)引进一个松弛变量\(\xi_i>=0\),使函数间隔加上松弛变量大于等于1.这样,约束条件就变成了:

\(y_i(w\cdot x_i + b) >= 1- \xi_i \)

同时,对每个松弛变量支付一个代价,目标函数由原来的\(\frac{1}{2}\Vert W \Vert^2\)变成了\(\frac{1}{2}\Vert W \Vert^2+ C\sum_{i=1}^N \xi_i \)。这里,C>0称为惩罚参数,一般由应用问题决定。C值大时对误分类的惩罚增大,C值小时对误分类的惩罚减小。

引入松弛变量后的学习问题变成如下形式:

我们称这样的模型为训练样本线性不可分时的线性支持向量机,简称为线性支持向量机。类似的,同样给出利用对偶式时的学习算法:

非线性情况

非线性支持向量机的关键是核技巧(kernel trick)。

核技巧

非线性分类问题是指通过利用非线性模型才能很好地进行分类的模型。例如:

使用一条椭圆曲线(非线性模型)可以将正负实例点正确分开

一般来说,对给定的一个训练数据集T,若果能用\(R^n\)中的一个超曲面将正负例正确分开,则称这个问题为非线性可分问题。

非线性往往不好求解,所以我们还是希望能用解线性分类问题的方法解决这个问题。所采用的方法是进行一个非线性变换,将非线性问题变换为线性问题。对上面这个例子,我们可以将椭圆变换成下图中的直线:

上面的例子说明,用线性分类方法求解非线性分类问题分为两步:

  1. 将原空间的数据映射到新空间
  2. 在新空间里用线性分类学习方法从训练数据中学习分类模型

核技巧应用在支持向量机中,基本想法就是通过一个非线性变换将输入空间对应于一个特征空间,使得在输入空间中的超曲面模型对应于特征空间中的超平面模型。这样,分类问题的学习任务通过在特征空间中求解线性支持向量机就可以完成。

核函数的定义:

注意,特征空间一般是高维的,甚至是无穷维的。可以看到,对于给定的核K(x,z),特征空间和映射函数的取法并不唯一。可以取不同的特征空间,即使是在同一特征空间里也可以取不同的映射。

举例说明核函数和映射函数的关系:

在核技巧于SVM的实际应用中,我们只需要找到核函数,而不需要找出其中具体的映射函数。因为在对偶学习算法中我们看到,无论是目标函数还是决策函数(分离超平面)都只涉及输入实例与实例之间的内积。因此可将内积用核函数来代替,此时对偶问题的目标函数为:

分类决策函数式为:

也就是说,在核函数K(x,z)给定的情况下,可以利用解线性分类问题的方法求解非线性分类问题的支持向量机。学习是隐式地在特征空间进行的,不需要显式地定义特征空间和映射函数。这样的技巧称为核技巧

关于如何找函数K(x,z)作为核函数,即正定核的充要条件的证明这里就不展开了。只给出正定核的充要条件:

常用核函数:

学习算法:

xinyu