6.4.2
支持向量机SVM

同时,我们从图6-28中可以看出,感知机的超平面不是唯一的,因为有无数个超平面都能把两类数据分开!那么,是否存在一个唯一的、最优的分离超平面呢?

答案是肯定的。我们能够找到这么一个超平面,它使得分类间隔最大(Margin Maximization,这时的这个分类器称为支持向量机(SVMSupport Vector Machine

如图6-29所示,H就是这个最优的超平面,而H1H2是两个与H等距平行且通过最邻近的正/负样本点的平面。此时,H1H2之间的间隔(Margin最大,其与最优超平面的法向量有关,间隔大小等于

我们把H1H2通过的最邻近正/负样本点称为支持向量(Support Vector。可以看出,在决定最优超平面时,只有最外围的支持向量起作用,而其他内部样本点不起任何作用(去掉这些点不会有任何影响)。因此,支持向量机是典型的“少数派报告”,只由很少的几个支持向量所决定。

讨论一下,支持向量机为何青睐最大间隔,却不是最小间隔呢?因为最大间隔能获得最大的稳定性与区分度。超平面之间的距离越大,分类器的推广能力越好,也就是预测精度越高。

有些聪明的读者可能会进一步问:“您刚才讨论的都是线性可分的情况,如果数据本身不是线性可分的,那超平面怎么去分开它们呢?”

6-29  支持向量机与支持向量(图片来源:Bülent Üstün

Good question!实际上,现实情况很多时候就是线性不可分的,也即:此时的分类问题是非线性的。这里有两种解决方案。第一种解决方案针对近似线性可分的情况,把上面那样的硬间隔(Hard Margin变成软间隔(Soft Margin,也即引入松驰变量(Slack Variable,允许超平面两边有误分类点,但应该让误分类点的个数尽可能小,同时让软间隔尽可能地大。

另一种解决方案是针对线性不可分的训练数据,我们可以利用核函数,即通过非线性特征映射将输入变量映射到一个高维特征空间(它有一个很酷的名字叫希尔伯特空间:Hilbert Space),在这个高维特征空间中构造最优分类超平面。“映射”这个动词可理解为变换或对应。如图6-30左边所示是一个分类问题,我们无法用直线(线性模型)将正/负样本分开,但可用椭圆线(非线性模型)将它们分开。如图6-30右边所示,如果我们采用某个核函数(Kernel Function,通过非线性变换将原始样本映射到高维特征空间中去(比如由X/Y二维映射到X/Y/Z三维),这时就可以使得原本的非线性问题简化为一个线性问题了(通过一个超平面将样本分开)!

6-30  将低维线性不可分的数据,映射到高维变成线性可分(图片来源:DTREG

提示:再强调一下,我们并不直接定义映射函数和(高维)特征空间的具体形式,只需定义核函数即可,这就是所谓的核技巧(Kernel Trick)。 

具体地,设是输入空间(比如本例中的二维空间),Hilbert特征空间(为高维空间,如本例中的三维空间),如果存在一个从的映射,使得对任意,函数。这里的就是核函数,为映射函数,中间的圆点符号代表内积运算。

上面之所以考虑内积运算,是因为如果把支持向量机转化到对偶形式(见第1010.1.3节),可发现分类函数(超平面H)的计算只涉及输入样本之间的内积运算,甚至不必知道映射函数的具体形式。实际上,通过定义映射函数去获得高维的内积通常并非易事,而通过定义核函数在映射到高维同时可方便地获得内积──对于任意的对称函数,只要满足Mercer条件,就可作为内积使用。支持向量机采用恰当的内积函数(核函数)便可实现经某一非线性映射后的线性分类,而计算复杂度却没有增加,因为这个高维空间中的线性分类器与空间的维数无关

然而,如何针对不同的问题选择不同的核函数仍是一个悬而未决的问题,往往依赖于领域知识。下面是常见的一些核函数。

l   多项式核函数(Polynomial Kernel Function):p>0),所对应的支持向量机是一个p次多项式分类器。

l  S形(Sigmoid)核函数:,其中双曲正切函数tanhSigmoid函数的一种,所对应的支持向量机是两层感知机的一种特例。

l  高斯核函数(Gaussian Kernel Function):,所对应的支持向量机是高斯径向基函数(RBFRadial Basis Function分类器。

 

上面这段文字仍比较拗口,怎么理解它呢?我们可以将左图理解为散布在面团上的红、绿两种颜色的豆子,在二维平面上无法一刀切开(只能通过画一个非线性的椭圆)。这时,我们可以揪住内部的面团往下拉(即非线性映射),这样绿色方形豆子都被移动到红色圆形豆子的Z轴下方了,由于所处高度不同,此时红、绿两种颜色的豆子就可以一刀切开了。

提示:非线性映射是针对整个样本空间的,本例中指整个面团。这里我们定义的核函数,使得内部的面团受到的向下拉力更大,能够比外围的面团更快地下落到Z轴下方。

也许还有更聪明的读者会进一步问道:“您刚才讨论的都是两类问题(人体、猩猩),如果是多类问题(人体、猩猩、大象、老虎、狮子)呢,怎么办?”

Very good question!其实,多类问题可通过转化为多个两类问题来求解。比如共有5个类。我们可以第1次问“是第1类还是第2类”,第2次问“是第1类还是第3类”,第3次“是第1类还是第4类”,如此问下去,你终能知道属于哪一个类别。但如此一来,我们总共必须设计“5×4/2=10”个分类器。即在M个类别的情况下,总的两类分类器数目为

扩展:除了SVM,在工业界实际用得较多的一种机器学习方法是逻辑回归(Logistic RegressionLR,用于估计某种事物的可能性(取值01之间)。SVM不同,逻辑回归既可用于分类(按照可能性大于0.5或小于0.5来区分),也可用于回归逻辑回归仅能用于线性问题,其本质实际上仅在线性回归的基础上,套用了一个SigmoidS形)函数,如图6-31所示:
                        
               

6-31  SigmoidS形)函数

Sigmoid函数优势在于,虽然自变量范围是从,但值域范围限制在0~1之间,也即可被看成一个概率函数。这种归一化被认为是合乎“逻辑”的,并在实际场合中得到广泛应用。

另一方面,是多个特征变量的加权线性组合:


比如一个女生对你的好感程度(打分)可用逻辑回归量化到一个0~1之间的数值,其由多个线性因素加权得到,如通过计算你的年龄大小、经济收入多少
、身材高度等各方面条件综合得到;而是她分别为年龄、经济收入、身高等特征设置的权值参数(回归系数),分别代表着在她心目中对每个特征的看重程度。因此,为了预测她对你的打分,关键就是要通过她之前为多名特征各异男士的已有打分,来估计出她心目中对各项特征条件的权值系数。在具体实现时,可将问题形式化为最大似然估计(参见第1010.8.3节),并采用梯度下降(参见第1010.3.1节)优化方法进行求解。
综上,
逻辑回归实质为一个线性分类模型,它与线性回归的不同点在于逻辑回归将原本线性回归输出的很大范围的数,例如从负无穷到正无穷,限制在了01之间