A glimpse of Support Vector Mach

2017-09-24 本文已影响0人 massquantity

支持向量机（support vector machine，以下简称svm）是机器学习里的重要方法，特别适用于中小型样本、非线性、高维的分类和回归问题。本篇希望在正篇提供一个svm的简明阐述，附录则提供一些其他内容。（由于简书插入小图比较麻烦，以下除第一节和最后一节外均采取图片形式。）

一、原理概述

机器学习的一大任务就是分类（Classification）。如下图所示，假设一个二分类问题，给定一个数据集，里面所有的数据都事先被标记为两类，能很容易找到一个超平面（hyperplane）将其完美分类。

然而实际上可以找到无数个超平面将这两类分开，那么哪一个超平面是效果最好的呢？

要回答这个问题，首先就要定义什么叫做“效果好”？在面临机器学习问题的时候普遍不是很关心训练数据的分类正确与否，而是关心一个新数据出现的时候其能否被模型正确分类。举个上学的例子（这里主要指理科），训练数据就像是平时的作业和小测验+答案，新数据则像是期末大考或中高考。作业和小测验有答案的帮助下做得很好，我们自然很高兴，但扪心自问，做作业和小测验的目的是为了在这之中取得好成绩吗？其实本质上不是的，作业和小测验的目的是为了训练我们的“大脑模型”，以备在期末大考和中高考中取得好成绩，继而走上人生巅峰。所以在做作业和小测验的时候，重要的是训练一种解题的思路，使之充分熟练进而能举一反三，在真正的大考中灵活地运用这些思路获得好成绩。此类情况用机器学习的说法就是这种“大脑模型”有较好的泛化能力，而相应的“过拟合”则指的是平时做题都会，一到关键大考就掉链子的行为。造成此类“过拟合”的原因固然有很多种，但其中之一恐怕就是平时不训练清楚思路、老是死记硬背、以至把答案中的“噪音”也学进去了。

所以在上述二分类问题中，如果新数据被分类的准确率高，可以认为是“效果好”，或者说有较好的泛化能力。因此这里的问题就转化为：上图中哪一个超平面对新数据的分类准确率最高？

然而令人沮丧的是，没人能确切地回答哪个超平面最好，因为没人能把真实世界中的所有数据都拿过来测试。从广义上来说，大部分的理论研究都是对真实情况的模拟，譬如我们用人均收入来衡量一个国家的人民生活水平，这里的人均收入甚至只是一个不太接近的近似，因为不可能把每个国家中所有人的收入都拿出来一一比较。我们的大脑善于把繁琐的细节组合起来并高度抽象化，形成模型和假设，来逼近真实情况。

所以，在这个问题上我们能做的，也只有提出假设，建立模型，验证假设。而在svm中，这个假设就是：拥有最大间隔的超平面效果最好。

间隔（margin）指的是所有数据点中到这个超平面的最小距离。如下图所示，实线为超平面，虚线为间隔边界，黑色箭头为间隔，即虚线上的点到超平面的距离。可以看出，虚线上的三个点（2蓝1红）到超平面的距离都是一样的，实际上只有这三个点共同决定了超平面的位置，因而它们被称为“支持向量（support vectors）”，而“支持向量机”也由此而得名。

于是我们来到了svm的核心思想 —— 寻找一个超平面，使其到数据点的间隔最大。原因主要是这样的超平面分类结果较为稳健（robust），对于最难分的数据点(即离超平面最近的点)也能有足够大的确信度将它们分开，因而泛化到新数据点效果较好。

比如上左图的红线和紫线虽然能将两类数据完美分类，但注意到这两个超平面本身非常靠近数据点。以紫线为例，圆点为测试数据，其正确分类为蓝色，但因为超平面到数据点的间隔太近，以至于被错分成了黄色。而上右图中因为间隔较大，圆点即使比所有蓝点更靠近超平面，最终也能被正确分类。

附录三、svm库的使用和计算复杂度

如正片中所述，scikit-learn中svm库的两个主要超参数为C和γ，C和γ越大，则模型趋于复杂，容易过拟合；反之，C和γ越大，模型变得简单，如下图所示：

LibSVM的作者，国立台湾大学的林智仁教授在其一篇小文（A Practical Guide to Support Vector Classification）中提出了svm库的一般使用流程:

其中第二步scaling对于svm的整体效果有重大影响。主要原因为在没有进行scaling的情况下，数值范围大的特征会产生较大的影响，进而影响模型效果。

第三步中认为应优先试验RBF核，通常效果比较好。但他同时也提到，RBF核并不是万能的，在一些情况下线性核更加适用。当特征数非常多，或者样本数远小于特征数时，使用线性核已然足够，映射到高维空间作用不大，而且只要对C进行调参即可。虽然理论上高斯核的效果不会差于线性核，但高斯核需要更多轮的调参。

而且当样本量非常大时，线性核的效率要远高于其他核函数，在实际问题中这一点可能变得非常重要。scikit-learn的LinearSVC库计算量和样本数线性相关，时间复杂度约为O(m×n)，而SVC库的时间复杂度约为O(m2×n)到O(m3×n)，当样本量很大时训练速度会变得很慢，因此使用非线性核的svm不大适合样本量非常大的情景。下表总结了scikit-learn中的svm分类库：