支持向量机,因其英文名为support vector machine,故一般简称SVM,通俗来讲,它是一种二类分类模型,其基本模型定义为特征空间上的间隔最大的线性分类器,其学习策略便是间隔最大化,最终可转化为一个凸二次规划问题的求解。
理解SVM,咱们必须先弄清楚一个概念:线性分类器。
考虑一个二类的分类问题,数据点用x来表示,类别用y来表示,可以取1或者-1,分别代表两个不同的类,且是一个n 维向量,w^T中的T代表转置。一个线性分类器的学习目标就是要在n维的数据空间中找到一个分类超平面,其方程可以表示为:
可能有读者对类别取1或-1有疑问,事实上,这个1或-1的分类标准起源于logistic回归,为了过渡的自然性,咱们就再来看看这个logistic回归。
Logistic回归目的是从特征学习出一个0/1分类模型,而这个模型是将特性的线性组合作为自变量,由于自变量的取值范围是负无穷到正无穷。因此,使用logistic函数(或称作sigmoid函数)将自变量映射到(0,1)上,映射后的值被认为是属于y=1的概率。
假设函数
其中x是n维特征向量,函数g就是logistic函数。
而的图像是
可以看到,通过logistic函数将自变量从无穷映射到了(0,1),而假设函数就是特征属于y=1的概率。
从而,当我们要判别一个新来的特征属于哪个类时,只需求,若大于0.5就是y=1的类,反之属于y=0类。
再审视一下,发现
只和
有关,
>0,那么
>0.5,g(z)只不过是用来映射,真实的类别决定权还在
。还有当
>>0时,
=1,反之
=0。如果我们只从
出发,希望模型达到的目标无非就是让训练数据中y=1的特征
>>0,而是y=0的特征
<<0。Logistic回归就是要学习得到
,使得正例的特征远大于0,负例的特征远小于0,强调在全部训练实例上达到这个目标。
这样,我们让,进一步
。也就是说除了y由y=0变为y=-1,只是标记不同外,与logistic回归的形式化表示没区别。
再明确下假设函数
上面提到过我们只需考虑的正负问题,而不用关心g(z),因此我们这里将g(z)做一个简化,将其简单映射到y=-1和y=1上。映射关系如下:
于此,想必已经解释明白了为何线性分类的标准一般用1 或者-1 来标示。
假定现在有一个一个二维平面,如下图所示,平面上有两种不同的点,分别用两种不同的颜色表示,一种为红颜色的点,另一种为蓝颜色的点,如果我们要在这个二维平面上找到一个可行的超平面的话,那么这个超平面可以是下图中那根红颜色的线(在二维空间中,超平面就是一条直线)。
从上图中我们可以看出,这条红颜色的线作为一个超平面,把红颜色的点和蓝颜色的点分开来了,在超平面一边的数据点所对应的y全是 -1 ,而在另一边全是1。
接着,我们可以令分类函数:
显然,如果 f(x)=0 ,那么x是位于超平面上的点。我们不妨要求对于所有满足 f(x)<0 的点,其对应的 y 等于 -1 ,而 f(x)>0 则对应 y=1 的数据点。
注:上图中,定义特征到结果的输出函数,与我们之前定义的
实质是一样的。为什么?因为无论是,还是,不影响最终优化结果。下文你将看到,当我们转化到优化
的时候,为了求解方便,会把yf(x)令为1,即yf(x)是y(w^x + b),还是y(w^x - b),对我们要优化的式子max1/||w||已无影响。
从而在我们进行分类的时候,将数据点 x代入 f(x) 中,如果得到的结果小于 0 ,则赋予其类别 -1 ,如果大于 0 则赋予类别 1 。如果 f(x)=0,则很难办了,分到哪一类都不是。
此外,有些时候,或者说大部分时候数据并不是线性可分的,这时满足这样条件的超平面可能就根本不存在,这里咱们先从最简单的情形开始推导,就假设数据都是线性可分的,亦即这样的超平面是存在的。
一般而言,一个点距离超平面的远近可以表示为分类预测的确信或准确程度。
于此,我们便引出了定义样本到分类间隔距离的函数间隔functional margin的概念。
我们定义函数间隔functional margin 为:
接着,我们定义超平面(w,b)关于训练数据集T的函数间隔为超平面(w,b)关于T中所有样本点(xi,yi)的函数间隔最小值,其中,x是特征,y是结果标签,i表示第i个样本,有:
= min
i (i=1,...n)
然与此同时,问题就出来了:上述定义的函数间隔虽然可以表示分类预测的正确性和确信度,但在选择分类超平面时,只有函数间隔还远远不够,因为如果成比例的改变w和b,如将他们改变为2w和2b,虽然此时超平面没有改变,但函数间隔的值f(x)却变成了原来的2倍。
事实上,我们可以对法向量w加些约束条件,使其表面上看起来规范化,如此,我们很快又将引出真正定义点到超平面的距离--几何间隔geometrical margin的概念(很快你将看到,几何间隔就是函数间隔除以个||w||,即yf(x) / ||w||)。
对于一个点 x ,令其垂直投影到超平面上的对应的为 x0 ,w 是垂直于超平面的一个向量,为样本x到分类间隔的距离,
我们有
其中,||w||表示的是范数。
又由于 x0 是超平面上的点,满足 f(x0)=0 ,代入超平面的方程即可算出:
不过这里的是带符号的,我们需要的只是它的绝对值,因此类似地,也乘上对应的类别 y即可,因此实际上我们定义 几何间隔geometrical margin 为(注:别忘了,上面
的定义,
=y(wTx+b)=yf(x) ):
代人相关式子可以得出:yi*(w/||w|| + b/||w||)。
综上,函数间隔y(wx+b)=yf(x)实际上就是|f(x)|,只是人为定义的一个间隔度量;而几何间隔|f(x)|/||w||才是直观上的点到超平面距离。
由上,我们已经知道,函数间隔functional margin 和 几何间隔geometrical margin 相差一个的缩放因子。按照我们前面的分析,对一个数据点进行分类,当它的 margin 越大的时候,分类的 confidence 越大。对于一个包含 n 个点的数据集,我们可以很自然地定义它的 margin 为所有这n个点的 margin 值中最小的那个。于是,为了使得分类的 confidence 高,我们希望所选择的超平面hyper plane 能够最大化这个 margin 值。
且
functional margin 明显是不太适合用来最大化的一个量,因为在 hyper plane 固定以后,我们可以等比例地缩放 w 的长度和 b 的值,这样可以使得的值任意大,亦即 functional margin可以在 hyper plane 保持不变的情况下被取得任意大,
而 geometrical margin 则没有这个问题,因为除上了这个分母,所以缩放 w 和 b 的时候
的值是不会改变的,它只随着 hyper plane 的变动而变动,因此,这是更加合适的一个 margin 。
这样一来,我们的 maximum margin classifier 的目标函数可以定义为:
当然,还需要满足一定的约束条件:
其中 (等价于
=
/||w||,故有稍后的
=1 时,
= 1 / ||w||),处于方便推导和优化的目的,我们可以令
=1(对目标函数的优化没有影响) ,此时,上述的目标函数
转化为:
其中,s.t.,即subject to的意思,它导出的是约束条件。
通过求解这个问题,我们就可以找到一个 margin 最大的 classifier ,通过最大化 margin ,我们使得该分类器对数据进行分类时具有了最大的 confidence,从而设计决策最优分类超平面。
如下图所示,中间的红色线条是 Optimal Hyper Plane ,另外两条线到红线的距离都是等于的(
便是上文所定义的geometrical margin,当令
=1时,
便为1/||w||,而我们上面得到的目标函数便是在相应的约束条件下,要最大化这个1/||w||值):
通过上节1.4节最后一张图:
我们可以看到两个支撑着中间的 gap 的超平面,到中间的纯红线separating hyper plane 的距离相等,即我们所能得到的最大的 geometrical margin,而“支撑”这两个超平面的必定会有一些点,而这些“支撑”的点便叫做支持向量Support Vector。
换言之,Support Vector便是下图中那蓝色虚线和粉红色虚线上的点:
很显然,由于这些 supporting vector 刚好在边界上,所以它们满足,而对于所有不是支持向量的点,也就是在“阵地后方”的点,则显然有
。
根据我们之前得到的目标函数(subject to导出的则是约束条件):
由于求的最大值相当于求
的最小值,所以上述目标函数等价于:
换言之,除了用解决QP问题的常规方法之外,还可以通过求解对偶问题得到最优解,这就是线性可分条件下支持向量机的对偶算法,这样做的优点在于:一者对偶问题往往更容易求解;二者可以自然的引入核函数,进而推广到非线性分类问题。
那什么是Lagrange duality?简单地来说,通过给每一个约束条件加上一个 Lagrange multiplier(拉格朗日乘值),即引入拉格朗日乘子,如此我们便可以通过拉格朗日函数将约束条件融和到目标函数里去(也就是说把条件融合到一个函数里头,现在只用一个函数表达式便能清楚的表达出我们的问题):
然后我们令
容易验证:
因此,在要求约束条件得到满足的情况下最小化,实际上等价于直接最小化
(当然,这里也有约束条件,就是≥0,i=1,…,n) ,因为如果约束条件没有得到满足,
会等于无穷大,自然不会是我们所要求的最小值。
具体写出来,我们现在的目标函数变成了:
这里用表示这个问题的最优值,这个问题和我们最初的问题是等价的。不过,现在我们来把最小和最大的位置交换一下:
当然,交换以后的问题不再等价于原问题,这个新问题的最优值用来表示。并且,我们有
≤
,这在直观上也不难理解,最大值中最小的一个总也比最小值中最大的一个要大。总之,第二个问题的最优值
在这里提供了一个第一个问题的最优值
的一个下界,在满足某些条件的情况下,这两者相等,这个时候我们就可以通过求解第二个问题来间接地求解第一个问题。
也就是说,下面我们可以先求L 对w、b的极小,再求L 对的极大。而且,之所以从minmax的原始问题
,转化为maxmin的对偶问题
,一者因为
是
的近似解,二者,转化为对偶问题后,更容易求解。
与此同时,上段说“在满足某些条件的情况下”,这所谓的“满足某些条件”就是要满足KKT条件。那KKT条件的表现形式是什么呢?
据维基百科:KKT 条件的介绍,一般地,一个最优化数学模型能够表示成下列标准形式:
其中,f(x)是需要最小化的函数,h(x)是等式约束,g(x)是不等式约束,p和q分别为等式约束和不等式约束的数量。同时,我们得明白以下两个定理: