单层感知机
旨在从训练数据集中得到一个线性的分类超平面,学习的策略是使所有误分类的样本距离超平面的距离最小,具体采用随机梯度下降法,每次随机找到一个误分类样本,使这个样本沿着最小化目标函数的方向更新参数。
给定一个训练数据集 :
其中x∈X=Rn,y∈Y={−1,1},i=1,2,...,N,因为误分类样本yi(wi∗xi+b)(函数距离)小于零,所以损失函数为
其中M为误分类的集合。可以看出,当误分类的点为0时,函数距离为0。当有误分类的点时,希望能够使得误分类的函数距离最小化。
感知机学习算法经过有限次的迭代可以得到一个将训练集完全正确划分的分离超平面即感知机模型。感知机模型是一个由w, b决定的超平面:
这样得到的感知机模型可以有无数个,为了得到唯一的超平面,需要对分离超平面增加约束条件,这就是线性支持向量机的想法。且当训练集线性不可分时,感知机算法不收敛,迭代结果发生震荡。
支持向量机(Support vector machine SVM)
支持向量机是一种二分类模型。它的基本模型是定义在特征空间上的间隔最大化的线性分类器。支持向量机的基础是单层感知机,从一堆样本(xi,yi)中学习到参数w,b, 得到一个超平面将样本分开。只不过单层感知机是靠误分类样本离超平面的距离最小驱动的,而SVM依靠的是最大化几何间隔驱动的。间隔最大化使其有别于感知机。支持向量机还包括核技巧,这使得其可以用于划分非线性样本数据,而感知机不能划分非线性数据。单层感知的解有无数个,但支持向量机利用间隔最大化求得的最优分离超平面是唯一的。间隔最大化就是:对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类,也就是说不仅将正确 的划分正负实例,而且对最难分的点(离超平面最近的点)也能够以足够大的确信度将他们分开。所以,这个平面应该对测试集也会有很好的分类预测能力(泛化能力)。
函数间隔:超平面w,b对于数据集的函数间隔是超平面对于每个样本点函数间隔的最小值。
当样本正确分类的时候,函数间隔就是样本到平面的距离。
而几何间隔是函数间隔除以∥w∥。
要几个间隔最大化,由此这个问题可表示为下面的约束
即我们希望最大化超平面(w,b)关于训练集的几何间隔γ,约束条件表示的是超平面(w,b)关于每个训练样本点的几何间隔至少是γ。即γ是训练集上离超平面最近的点的距离。将上式中的几何间隔用函数间隔代替,可得
函数间隔的取值对目标函数和最优化问题的不等式约束都没有影响,可对函数间隔ý取1,得到下面的线性可分的支持向量机学习的最优化问题:
这是个凸二次优化 问题,可将他作为原始最优化问题 ,应用拉格朗日对偶性,通过求解对偶问题得到原始问题的最优解。定义如下拉格朗日函数:
α为拉格朗日乘子向量,假设测试集中有n个实例,那么α就有n维。根据拉格朗日的对偶性,将原始问题转换为对偶问题的极大极小问题:
先对w和b求导,得到极小值问题
将求得的解代入到拉格朗日函数中,可以得到下面的优化函数(将代入后原本的求α 的极大问题转换成了极小问题),即对偶问题
对对偶问题求α的解,即可得到原始问题(w,b)对应的解。
KKT条件是拉格朗日求解最优化问题的必要条件:
由KKT条件可知:对于任意训练样本(xi,yi)总有α=0或者yi(w*xi+b)=1,若α=0,则样本不会在模型求和中出现。若α>0,则必有yi(w*xi+b)=1,所对应的样本点位于最大间隔边界上,这些样本点是一个支持向量。综上可知,最终模型(w,b)只与这些支持向量有关,与其他大部分训练样本无关。因此很多时候支持向量在小样本集分类时也能表现的很好。此外,α向量的维数是与数据集样本数成正比的,在处理大数据集的时候,可能会比其他算法处理起来要慢。还有,如果可以发现求出的α向量里有很多0元素。
线性支持向量机与软间隔最大化:
上述推导的线性支持向量机只是能处理线性可分的问题,而对于线性不可分的训练数据是不适用的。通常情况下,训练数据中有一些异常点,这些异常点去掉后,剩下的大部分样本点组成的集合是线性可分的。线性不可分意味着,这些样本点不能满足函数间隔大于等于1的条件。于是引入一个松弛变量,这样约束条件变成:
目标函数中加入对松弛变量的惩罚项,惩罚参数C > 0,目标优化函数变为:
于是线性不可分的线性支持向量学习问题变成如下的凸二次规划问题:
最小化目标函数包括两层含义:一使得1/2||w||尽量小即间隔尽量要大,同时使得误分类的点的个数要尽量小,C为调和二者系数的参数。
利用拉格朗日将约束问题转化为无约束的问题,将原始问题转化为求极大极小问题的对偶问题,可以得到最终的求解问题:
合页损失函数
线性支持向量机还有另外一种解释,就是最小化以下目标函数:
目标函数第1项为经验风险,第 2项为结构风险,是系数λ的w的L2范数,是正则化项。L(y(w*x+b))=[1-y(w*x+b)]+称为合页损失函数(hinge loss fuction),表达式如下:
该表达式可以理解为取正值的函数。这就是说,当样本点(xi,yi)被正确分类时且函数间隔(确信度)yi(w*xi+b)大于1时,损失为 0,yi(w*xi+b)小于1时损失为
1-yi(w*xi+b)。对比先前的感知机损失函数可知,当样本点正确分类时,损失函数为0.否则损失为-yi(w*xi+b)。相比之下,合页损失函数对学习有更高的要求。
非线性支持向量机与核函数
上面的的软间隔最大化支持向量,只是解决线性可分的数据集中存在少数线性不可分的样本的问题。但是对于本身分类问题就是非线性的,那么线性分类支持向量机就无能为力了。这时就要使用非线性支持向量机。对于非线性问题,一般映射到高维空间,一般是可变成线性可分的问题。
以上式为例,引入映射函数ϕ(x)。将实例的内积xi•xj映射成特征空间中的ϕ(xi)•ϕ(xj),然后在新的特征空间里线性可分。但是映射之后,特征维度会很大,直接计算ϕ(xi)•ϕ(xj)并不容易。于是引入了核函数来解决这个问题令K( xi · xj )=ϕ(xi)•ϕ(xj)。已有证明这样是可行的。用核函数K( xi · xj )来替代在映射特征空间的ϕ(xi)•ϕ(xj)的求解就容易多了。这样,在核函数给定的情况下,可以利用解决线性可分的问题的方法求解非线性分类问题。这就是支持向量机的一大优点:利用核函数来进行求解非线性可分问题。但核函数的选择往往需要通过一定验证。目前主要的核函数有
线性核函数
一般用于处理线性问题
多项式核函数
特点是:参数比较多
高斯核函数 也称高斯径向基函数(rbf)
Sigmiod核函数
K(x, y) = tanh (ax · z + r)
tanh为双曲正切函数,a>0,r<0
核函数选择问题:
由于高阶可导的函数一般都可以用多项式函数来表示,而径向基核函数和Sigmoid核函数都是可以表述高阶多项式的,因此在选择核函数时,径向基核函数和Sigmoid 核函数通常要比多项式核函数表现的要好,因为可以自动的去匹配阶数,而不需要我们去指定多项式核函数的阶数,此外,多项式核函数需要调试的参数也比较多,因此对于非线性问题,常选择径向基核函数和Sigmoid函数。
总结
SVM支持向量机的优点:
(1)能够准确的分类实例较少的样本集,而且能够在较少样本集上就能学得具有不错的泛化能力
(2)引入了核函数,能够解决非线性分类问题
(3)能解决高维特征的分类、回归问题,即使特征维度多于样本实例的数据,也能有很好的表现
缺点:
(1)在样本量非常大时,核函数中內积的计算以及拉格朗日乘子α 参数的个数与样本数密切相关,会导致在求解模型时的计算量过大
(2)核函数的选择通常没有明确的指导,有时候难以选择一个合适的核函数,而且像多项式核函数,需要调试的参数也非常多
(3)对样本中的缺失值敏感