机器学习系列（9）：从感知器到支持向量机

摘要：这一章，我们将介绍一种强大的分类和回归模型，称为支持向量机（support vector machine，SVM）。

从感知器到支持向量机

上一章我们介绍了感知器。作为一种二元分类器，感知器不能有效的解决线性不可分问题。其实在第二章，线性回归里面已经遇到过类似的问题，当时需要解决一个解释变量与响应变量存在非线性关系的问题。为了提高模型的准确率，我们引入了一种特殊的多元线性回归模型，多项式回归。通过对特征进行合理的组合，我们建立了高维特征空间的解释变量与响应变量的线性关系模型。

随着特征空间的维度的不断增多，在用线性模型近似非线性函数时，上述方法似乎依然可行，但是有两个问题不可避免。首先是计算问题，计算映射的特征，操纵高维的向量需要更强大的计算能力。然后是与算法归纳有关的问题，特征空间的维度的不断增多会导致维度灾难。从高维的特征变量中学习，要避免拟合过度，就需要呈指数级增长的训练数据。

这一章，我们将介绍一种强大的分类和回归模型，称为支持向量机（support vector machine，SVM）。首先，我们将学习高维空间的特征映射。然后，我们将介绍，在处理被映射到高维空间的数据时，支持向量机是如何缓解那些计算与综合问题的。有许多书整本整本的介绍SVM，相关的优化算法需要比前面章节里介绍其他算法更多的数学知识。我们不再用前面那些章节的小例子来演示算法，而是通过直观的案例来介绍scikit-learn如何有效的使用SVM去解决问题。

核与核方法

感知器是用超平面作决策边界对阳性和阴性类型进行分类的。其决策边界公式如下：

预测是通过下面的格式计算得出：

为了与SVM的概念一致，我们要对上面的概念做一些调整。

我们可以把模型写成另一种形式，其证明过程忽略。下面的模型表达式称为对偶型（dual form）。前面介绍的表达式称为原型（primal form）:

对偶型与原型的最重要区别就是原型计算模型参数（model parameters ）内积，测试样本的特征向量，而对偶型计算训练样本（training instances）的内积，测试样本的特征向量。总之，我们将利用对偶型的这个特性来解决线性不可分问题。首先，我们必须定义高维空间特征映射。

在第二章，线性回归介绍多元回归时，我们将特征映射成与响应变量线性相关的高维空间。映射将原来的特征进行组合，通过建立二次项增加特征的数量。这些综合特征允许我们用线性模型表示非线性函数。通常，映射表达式如下所示：

x→ϕ(x) ϕ:Rd→RD

下图中左边显示了一个线性不可分数据集。而右边就是将数据集映射到更高维空间后线性可分的结果。

让我们回到决策边界的对偶型，观察特征向量只以点积呈现的情况。我们可以用下面的方法将数据映射到一个高维空间：

这个映射允许我们表述更复杂的模型，但是它也引入了计算和综合相关的问题。映射特征向量并计算它们的点积需要极大的计算能力。

注意在第二个方程里，我们将特征向量映射到高维空间中，特征向量仍然是以点积呈现。点积是标量，如果一个标量已经被计算出来，我们就不需要去映射对应的特征向量了，这样我们在计算点击和映射特征向量这些事情上省点儿事儿。

有一种方法叫做核方法（ kernel trick）。核是一个考虑原始特征向量的函数，返回对应的映射后特征向量点积相同的值。核不直接将特征向量映射到高维空间，或者计算映射后特征向量点积。而且通过一组更有效的计算步骤得出同样的值。核更正式定义如下：

K(x,z)=

下面我们演示核是如何运行的。假设我们有两特征向量，x和z：

x=(x1,x2) z=(z1,z2)

在我们的模型里面，我们想用下面的转换函数将特征向量映射到高维空间：

ϕ(x)=x2

映射后的标准化特征向量的点积等价于：

=

而下面公式的核可以产生与映射后的特征向量的点积同样的结果：

$$K(x,z)= grid_search = GridSearchCV(pipeline, parameters, n_jobs=3, verbose=1, scoring=accuracy) grid_search.fit(X_train, y_train) print(最佳效果：%0.3f % grid_search.best_score_) print(最优参数集：) best_parameters = grid_search.best_estimator_.get_params() for param_name in sorted(parameters.keys()): print(t%s: %r % (param_name, best_parameters[param_name])) predictions = grid_search.predict(X_test) print(classification_report(y_test, predictions))

这个任务比识别MNIST数据集里面的手写数据需要耗费更多的计算能力。字母的外形变化很大，因为这些字母都是从照片里提取的，不是扫描件。另外，Chars74K数据集里每个类型的训练样本数量比MNIST数据集更少。分类器的性能可以通过增加训练数据，用另外的图片预处理方法，或者用更复杂的特征表述等手段来改善。

总结

本章，我们介绍了支持向量机——一种可以弥补感知器不足的强大模型。感知器可以有效的处理线性可分问题模型，但是如果不把特征空间扩展到更高的维度，它不能表达更复杂的决策边界。但是，这样的扩展会导致计算与综合相关的问题。支持向量机用核函数修正第一个问题，可以避免特征映射的复杂计算，通过决策边界与最近样本的间隔最大化修正第二个问题。下一章，我们将介绍人工神经网络模型，和支持向量机一样，可以弥补感知器的不足。