第五章 支持向量机
· Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow, 2nd Edition, by Aurélien Géron (O’Reilly). Copyright 2019 Aurélien Géron, 978-1-492-03264-9.
· 环境：Anaconda（Python 3.8） + Pycharm
· 学习时间：2022.05.04~2022.05.04
支持向量机（Support Vector Machine，SVM）是一个功能强大并且全面的机器学习模型，它能够执行线性或非线性分类、回归，甚至是异常值检测任务。它是机器学习领域最受欢迎的模型之一，任何对机器学习感兴趣的人都应该在工具箱中配备一个。SVM特别适用于中小型复杂数据集的分类。
本章将会介绍不同SVM的核心概念、如何使用它们以及它们的工作原理。
文章目录
5.1 线性SVM分类
5.1.1 基本思想
SVM的基本思想可以用一些图来说明。
两个类可以轻松地被一条直线（它们是线性可分离的）分开。左图显示了三种可能的线性分类器的决策边界。其中虚线所代表的模型表现非常糟糕，甚至都无法正确实现分类。其余两个模型在这个训练集上表现堪称完美，但是它们的决策边界与实例过于接近，导致在面对新实例时，表现可能不会太好。相比之下，右图中的实线代表SVM分类器的决策边界，这条线不仅分离了两个类，并且尽可能远离了最近的训练实例。你可以将SVM分类器视为在类之间拟合可能的最宽的街道（平行的虚线所示）。因此这也叫作大间隔分类。
请注意，在“街道以外”的地方增加更多训练实例不会对决策边界产生影响，也就是说它完全由位于街道边缘的实例所决定（或者称之为“支持”）。这些实例被称为支持向量（在图中已圈出）。
SVM对特征的缩放非常敏感。
如图所示，在左图中，垂直刻度比水平刻度大得多，因此可能的最宽的街道接近于水平。在特征缩放（例如使用Scikit-Learn的StandardScaler）后，决策边界看起来好了很多（见右图）。
5.1.2 软间隔分类
如果我们严格地让所有实例都不在街道上，并且位于正确的一边，这就是硬间隔分类。硬间隔分类有两个主要问题。首先，它只在数据是线性可分离的时候才有效；其次，它对异常值非常敏感。
下图显示了有一个额外异常值的鸢尾花数据：左图的数据根本找不出硬间隔，而右图最终显示的决策边界与我们在上图中所看到的无异常值时的决策边界也大不相同，可能无法很好地泛化。
要避免这些问题，最好使用更灵活的模型。目标是尽可能在保持街道宽阔和限制间隔违例（即位于街道之上，甚至在错误的一边的实例）之间找到良好的平衡，这就是软间隔分类。
使用Scikit-Learn创建SVM模型时，我们可以指定许多超参数。C是这些超参数之一。
如果将其设置为较低的值，则最终得到下图左侧的模型。如果设置为较高的值，我们得到右边的模型。间隔冲突很糟糕，通常最好要少一些。但是，在这种情况下，左侧的模型存在很多间隔违例的情况，但泛化效果可能会更好
如果你的SVM模型过拟合，可以尝试通过降低C来对其进行正则化。
以下Scikit-Learn代码可加载鸢尾花数据集，缩放特征，然后训练线性SVM模型（使用C=1的LinearSVC类和稍后描述的hinge损失函数）来检测维吉尼亚鸢尾花：
import numpy as np
from sklearn import datasets
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import LinearSVC
iris = datasets.load_iris()
X = iris["data"][:,(2,3)]# petal length, petal width
y =(iris["target"]==2).astype(np.float64)# Iris virginica
svm_clf = Pipeline([("scaler", StandardScaler()),("linear_svc", LinearSVC(C=1, loss="hinge"))])
svm_clf.fit(X, y)# 使用模型进行预测：
svm_clf.predict([[5.5,1.7]])# 结果输出为array([1.])
与Logistic回归分类器不同，SVM分类器不会输出每个类的概率。
我们可以将SVC类与线性内核一起使用，而不使用LinearSVC类。创建SVC模型时，我们可以编写SVC（kernel=“linear”，C=1）。或者我们可以将SGDClassifier类与SGDClassifier（loss=“hinge”，alpha=1/（m*C））一起使用。这将使用常规的随机梯度下降（见第4章）来训练线性SVM分类器。它的收敛速度不如LinearSVC类，但是对处理在线分类任务或不适合内存的庞大数据集（核外训练）很有用。
LinearSVC类会对偏置项进行正则化，所以你需要先减去平均值，使训练集居中。如果使用StandardScaler会自动进行这一步。此外，请确保超参数loss设置为"hinge"，因为它不是默认值。最后，为了获得更好的性能，还应该将超参数dual设置为False，除非特征数量比训练实例还多（本章后文将会讨论）。
5.2 非线性SVM分类
虽然在许多情况下，线性SVM分类器是有效的，并且通常出人意料的好，但是，有很多数据集远不是线性可分离的。处理非线性数据集的方法之一是添加更多特征，比如多项式特征（如第4章所述）。某些情况下，这可能导致数据集变得线性可分离。
为了使用Scikit-Learn来实现这个想法，创建一个包含PolynomialFeatures转换器（见4.3节）的Pipeline，然后是StandardScaler和LinearSVC。让我们在卫星数据集上进行测试：这是一个用于二元分类的小数据集，其中数据点的形状为两个交织的半圆（见下图）。你可以使用
make_moons()
函数生成此数据集：
from sklearn.preprocessing import StandardScaler
from sklearn.svm import LinearSVC
from sklearn.datasets import make_moons
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import PolynomialFeatures
X, y = make_moons(n_samples=100, noise=0.15)
polynomial_svm_clf = Pipeline([("poly_features", PolynomialFeatures(degree=3)),("scaler", StandardScaler()),("svm_clf", LinearSVC(C=10, loss="hinge"))])
polynomial_svm_clf.fit(X, y)
使用多项式特征的线性SVM分类器图如下：
5.2.1 多项式内核
添加多项式特征实现起来非常简单，并且对所有的机器学习算法（不只是SVM）都非常有效。但问题是，如果多项式太低阶，则处理不了非常复杂的数据集。而高阶则会创造出大量的特征，导致模型变得太慢。
幸运的是，使用SVM时，有一个魔术般的数学技巧可以应用，这就是核技巧（稍后解释）。它产生的结果就跟添加了许多多项式特征（甚至是非常高阶的多项式特征）一样，但实际上并不需要真的添加。因为实际没有添加任何特征，所以也就不存在数量爆炸的组合特征了。这个技巧由SVC类来实现，我们看看在卫星数据集上的测试：
from sklearn.preprocessing import StandardScaler
from sklearn.datasets import make_moons
from sklearn.pipeline import Pipeline
from sklearn.svm import SVC
X, y = make_moons(n_samples=100, noise=0.15)
poly_kernel_svm_clf = Pipeline([("scaler", StandardScaler()),("svm_clf", SVC(kernel="poly", degree=3, coef0=1, C=5))])
poly_kernel_svm_clf.fit(X, y)
这段代码使用了一个3阶多项式内核训练SVM分类器（
kernel="poly", degree=3
）。如下图的左图所示。而右图是另一个使用了10阶多项式核的SVM分类器。显然，如果模型过拟合，你应该降低多项式阶数；反过来，如果欠拟合，则可以尝试使之提升。超参数
coef0
控制的是模型受高阶多项式还是低阶多项式影响的程度。
寻找正确的超参数值的常用方法是网格搜索（见第2章）。先进行一次粗略的网格搜索，然后在最好的值附近展开一轮更精细的网格搜索，这样通常会快一些。多了解每个超参数实际上是用来做什么的，有助于你在超参数空间层正确搜索。
5.2.2 相似特征
解决非线性问题的另一种技术是添加相似特征，这些特征经过相似函数计算得出，相似函数可以测量每个实例与一个特定地标之间的相似度。
个人理解就是将数据进行转换，地标就是转换后的数据。
你可能想知道怎么选择地标。最简单的方法是在数据集里每一个实例的位置上创建一个地标。这会创造出许多维度，因而也增加了转换后的训练集线性可分离的机会。缺点是一个有m个实例n个特征的训练集会被转换成一个m个实例m个特征的训练集（假设抛弃了原始特征）。如果训练集非常大，那就会得到同样大数量的特征。
5.2.3 高斯RBF内核
与多项式特征方法一样，相似特征法也可以用任意机器学习算法，但是要计算出所有附加特征，其计算代价可能非常昂贵，尤其是对大型训练集来说。然而，核技巧再一次施展了它的SVM魔术：它能够产生的结果就跟添加了许多相似特征一样（但实际上也并不需要添加）。我们来使用SVC类试试高斯RBF核：
rbf_kernel_svm_clf = Pipeline([("scaler", StandardScaler()),("svm_clf", SVC(kernel="rbf", gamma=5, C=0.001))])
rbf_kernel_svm_clf.fit(X, y)
下图的左下方显示了这个模型。其他图显示了超参数gamma（γ）和C使用不同值时的模型。增加gamma值会使钟形曲线变得更窄，因此每个实例的影响范围随之变小：决策边界变得更不规则，开始围着单个实例绕弯。反过来，减小gamma值使钟形曲线变得更宽，因而每个实例的影响范围增大，决策边界变得更平坦。所以γ就像是一个正则化的超参数：模型过拟合，就降低它的值，如果欠拟合则提升它的值（类似超参数C）。
还有一些其他较少用到的核函数，例如专门针对特定数据结构的核函数。字符串核常用于文本文档或是DNA序列（如使用字符串子序列核或是基于莱文斯坦距离的核函数）的分类。
有这么多的核函数，该如何决定使用哪一个呢？有一个经验法则是，永远先从线性核函数开始尝试（要记住，LinearSVC比SVC（kernel=“linear”）快得多），特别是训练集非常大或特征非常多的时候。如果训练集不太大，你可以试试高斯RBF核，大多数情况下它都非常好用。如果你还有多余的时间和计算能力，可以使用交叉验证和网格搜索来尝试一些其他的核函数，特别是那些专门针对你的数据集数据结构的核函数。
5.2.4 计算复杂度
liblinear库为线性SVM实现了一个优化算法，LinearSVC正是基于该库的。该算法不支持核技巧，不过它与训练实例的数量和特征数量几乎呈线性相关：其训练时间复杂度大致为
O
(
m
×
n
)
O(m×n)
O(m×n)。
如果你想要非常高的精度，算法需要的时间更长。它由容差超参数ε（在Scikit-Learn中为tol）来控制。大多数分类任务中，默认的容差就够了。
SVC则是基于libsvm库的，这个库的算法支持核技巧。训练时间复杂度通常在
O
(
m
2
×
n
)
O(m^2×n)
O(m2×n)和
O
(
m
3
×
n
)
O(m^3×n)
O(m3×n)之间。很不幸，这意味着如果训练实例的数量变大（例如成千上万的实例），它将会慢得可怕，所以这个算法完美适用于复杂但是中小型的训练集。但是，它还是可以良好地适应特征数量的增加，特别是应对稀疏特征（即每个实例仅有少量的非零特征）。在这种情况下，算法复杂度大致与实例的平均非零特征数成比例。
下表比较了Scikit-Learn的SVM分类器类：
5.3 SVM回归
正如前面提到的，SVM算法非常全面：它不仅支持线性和非线性分类，而且还支持线性和非线性回归。诀窍在于将目标反转一下：不再尝试拟合两个类之间可能的最宽街道的同时限制间隔违例，SVM回归要做的是让尽可能多的实例位于街道上，同时限制间隔违例（也就是不在街道上的实例）。街道的宽度由超参数ε控制。
下图显示了用随机线性数据训练的两个线性SVM回归模型，一个间隔较大（ε=1.5），另一个间隔较小（ε=0.5）。
在间隔内添加更多的实例不会影响模型的预测，所以这个模型被称为ε不敏感。
你可以使用Scikit-Learn的LinearSVR类来执行线性SVM回归。以下代码生成如图5-10左图所示的模型（训练数据需要先缩放并居中）：
from sklearn.svm import LinearSVR
svm_reg = LinearSVR(epsilon=1.5)
svm_reg.fit(X, y)
要解决非线性回归任务，可以使用核化的SVM模型。例如，下图显示了在一个随机二次训练集上使用二阶多项式核的SVM回归。左图几乎没有正则化（C值很大），右图则过度正则化（C值很小）。
以下代码使用Scikit-Learn的SVR类（支持核技巧）生成如上图左图所示的模型：
from sklearn.svm import SVR
svm_poly_reg = SVR(kernel="poly", degree=2, C=100, epsilon=0.1)
svm_poly_reg.fit(X, y)
SVR类是SVC类的回归等价物，LinearSVR类也是LinearSVC类的回归等价物。LinearSVR与训练集的大小线性相关（与LinearSVC一样），而SVR则在训练集变大时，变得很慢（SVC也一样）。
SVM也可用于异常值检测，详细信息请参考Scikit-Learn文档。
5.4 工作原理
本节将会介绍SVM如何进行预测，以及它们的训练算法是如何工作的，从线性SVM分类器开始。如果你刚刚开始接触机器学习，可以安全地跳过本节，直接进入本章末尾的练习，等到想要更深入地了解SVM时再回来也不迟。
首先，说明一下符号。在第4章里，我们使用过一个约定，将所有模型参数放在一个向量
θ
θ
θ中，包括偏置项
θ
0
θ_0
θ0，以及输入特征的权重
θ
1
θ_1
θ1到
θ
n
θ_n
θn，同时在所有实例中添加偏置项
x
0
=
1
x_0=1
x0=1。在本章中，我们将会使用另一个约定，在处理SVM时它更为方便（也更常见）：偏置项表示为
b
b
b，特征权重向量表示为
w
w
w，同时输入特征向量中不添加偏置特征。
5.4.1 决策函数和预测
线性SVM分类器通过简单地计算决策函数
w
T
x
+
b
=
w
1
x
1
+
…
+
w
n
x
n
+
b
w^Tx + b = w_1x_1 + …+ w_nx_n + b
wTx+b=w1x1+…+wnxn+b来预测新实例x的分类。如果结果为正，则预测类别是正类（1），否则预测其为负类（0），即
y
′
=
{
0
,
w
T
x
+
b
<
0
1
,
w
T
x
+
b
≥
0
y' = \begin{cases}0,\ &w^Tx + b<0\\1,\ &w^Tx + b≥0\end{cases}
y′={0, 1, wTx+b<0wTx+b≥0。
5.4.2 训练目标
思考一下决策函数的斜率：它等于权重向量的范数，即
∣
∣
w
∣
∣
||w||
∣∣w∣∣。如果我们将斜率除以2，那么决策函数等于±1的点也将变得离决策函数两倍远。也就是说，将斜率除以2，将会使间隔乘以2。也许2D图更容易将其可视化，见下图。权重向量w越小，间隔越大。
我们要最小化
∣
∣
w
∣
∣
||w||
∣∣w∣∣来得到尽可能大的间隔。但是，如果我们想避免任何间隔违例（硬间隔），那么就要使所有正类训练集的决策函数大于1，负类训练集的决策函数小于-1。如果我们定义实例为负类（如果y（i）=0）时，t（i）=-1；实例为正类（如果y（i）=1）时，t（i）=1。那么就可以将这个约束条件表示为：对所有实例来说，
t
(
i
)
(
w
T
x
(
i
)
+
b
)
≥
1
t^{(i)}(w^Tx^{(i)} + b) ≥1
t(i)(wTx(i)+b)≥1。因此，我们可以将硬间隔线性SVM分类器的目标看作一个约束优化问题（优化
1
2
w
T
w
\frac{1}{2}w^Tw
21wTw而不是
∣
∣
w
∣
∣
||w||
∣∣w∣∣，这样可以使优化算法在可微函数上的工作效果更好）：
m
i
n
i
m
i
z
e
1
2
w
T
w
,
使
得
t
(
i
)
(
w
T
x
(
i
)
+
b
)
≥
1
,
i
=
1
,
2
,
3
…
minimize \frac{1}{2}w^Tw, 使得t^{(i)}(w^Tx^{(i)} + b) ≥ 1, i=1,2,3…
minimize21wTw,使得t(i)(wTx(i)+b)≥1,i=1,2,3…
要达到软间隔的目标，我们需要为每个实例引入一个松弛变量（衡量的是第i个实例多大程度上允许间隔违例）：
m
i
n
i
m
i
z
e
1
2
w
T
w
+
C
∑
i
=
1
m
ζ
(
i
)
,
使
得
t
(
i
)
(
w
T
x
(
i
)
+
b
)
≥
1
−
ζ
(
i
)
和
ζ
(
i
)
≥
0
,
i
=
1
,
2
,
3
…
minimize \frac{1}{2}w^Tw+C\sum^m_{i=1}ζ^{(i)}, 使得t^{(i)}(w^Tx^{(i)} + b) ≥ 1-ζ^{(i)}和ζ^{(i)}≥0, i=1,2,3…
minimize21wTw+Ci=1∑mζ(i),使得t(i)(wTx(i)+b)≥1−ζ(i)和ζ(i)≥0,i=1,2,3…
5.4.3 二次规划
硬间隔和软间隔问题都属于线性约束的凸二次优化问题。这类问题被称为二次规划（QP）问题。要解决二次规划问题有很多现成的求解器，使用到的技术各不相同，这些不在本书的讨论范围之内。
5.4.4 对偶问题
针对一个给定的约束优化问题，称之为原始问题，我们常常可以用另一个不同的，但是与之密切相关的问题来表达，这个问题我们称之为对偶问题。通常来说，对偶问题的解只能算是原始问题的解的下限，但是在某些情况下，它也可能跟原始问题的解完全相同。幸运的是，SVM问题刚好就满足这些条件，所以你可以选择是解决原始问题还是对偶问题，二者解相同。（如果你对如何从原始问题导出对偶问题感兴趣，请参阅附录C）
5.4.5 Mercer定理
常用核函数如下：
根据Mercer定理，如果函数K（a，b）符合几个数学条件——也就是Mercer条件（K必须是连续的，并且在其参数上对称，所以K（a，b）=K（b，a），等等），则存在函数φ将a和b映射到另一空间（可能是更高维度的空间），使得K（a，b）=φ（a）Tφ（b）。所以你可以将K用作核函数，因为你知道φ是存在的，即使你不知道它是什么。对于高斯RBF核函数，可以看出，φ实际上将每个训练实例映射到了一个无限维空间，幸好不用执行这个映射。注意，也有一些常用的核函数（如S型核函数）不符合Mercer条件的所有条件，但是它们在实践中通常也表现不错。
5.4.6 在线SVM
在结束本章之前，让我们快速看一下在线SVM分类器（回想一下，在线学习意味着增量学习，通常是随着新实例的到来而学习）。对于线性SVM分类器，一种实现在线SVM分类器的方法是使用梯度下降（例如，使用SGDClassifier）来最小化源自原始问题的公式5-13中的成本函数。不幸的是，梯度下降比基于QP的方法收敛慢得多。
成本函数中的第一项会推动模型得到一个较小的权重向量w，从而使间隔更大。第二项则计算全部的间隔违例。如果没有一个示例位于街道之上，并且都在街道正确的一边，那么这个实例的间隔违例为0；否则，该实例的违例大小与其到街道正确一边的距离成正比。所以将这个项最小化，能够保证模型使间隔违例尽可能小，也尽可能少。
Hinge损失函数：
函数max（0，1-t）被称为hinge损失函数（如图所示）。当t≥1时，函数等于0。如果t<1，其导数（斜率）等于-1；如果t>1，则导数（斜率）为0；t=1时，函数不可导。但是，在t=0处可以使用任意次导数（即-1到0之间的任意值），你还是可以使用梯度下降，就跟Lasso回归一样。
5.5 练习题
5.5.1 问题
- 支持向量机的基本思想是什么？
- 什么是支持向量？
- 使用SVM时，对输入值进行缩放为什么重要？
- SVM分类器在对实例进行分类时，会输出信心分数吗？概率呢？
- 如果训练集有成百万个实例和几百个特征，你应该使用SVM原始问题还是对偶问题来训练模型？
- 假设你用RBF核训练了一个SVM分类器，看起来似乎对训练集欠拟合，你应该提升还是降低γ（gamma）？C呢？
- 如果使用现成二次规划求解器，你应该如何设置QP参数（H、f、A和b）来解决软间隔线性SVM分类器问题？
- 在一个线性可分离数据集上训练LinearSVC。然后在同一数据集上训练SVC和SGDClassifier。看看你是否可以用它们产生大致相同的模型。
- 在MNIST数据集上训练SVM分类器。由于SVM分类器是个二元分类器，所以你需要使用一对多来为10个数字进行分类。你可能还需要使用小型验证集来调整超参数以加快进度。最后看看达到的准确率是多少？
- 在加州住房数据集上训练一个SVM回归模型。
5.5.2 答案
- 支持向量机的基本思想是拟合类别之间可能的、最宽的“街道”。换言之，它的目的是使决策边界之间的间隔最大化，该决策边界分隔两个类别和训练实例。SVM执行软间隔分类时，实际上是在完美分隔两个类和拥有尽可能最宽的街道之间寻找折中方法（也就是允许少数实例最终还是落在街道上）。还有一个关键点是在训练非线性数据集时，记得使用核函数。
- 支持向量机的训练完成后，位于“街道”（参考上一个答案）之上的实例被称为支持向量，这也包括处于边界上的实例。决策边界完全由支持向量决定。非支持向量的实例（也就是街道之外的实例）完全没有任何影响。你可以选择删除它们然后添加更多的实例，或者将它们移开，只要一直在街道之外，它们就不会对决策边界产生任何影响。计算预测结果只会涉及支持向量，而不涉及整个训练集。
- 支持向量机拟合类别之间可能的、最宽的“街道”（参考第1题答案），所以如果训练集不经缩放，SVM将趋于忽略值较小的特征。
- 支持向量机分类器能够输出测试实例与决策边界之间的距离，你可以将其用作信心分数。但是这个分数不能直接转化成类别概率的估算。如果创建SVM时，在Scikit-Learn中设置probability=True，那么训练完成后，算法将使用逻辑回归对SVM分数进行校准（对训练数据额外进行5-折交叉验证的训练），从而得到概率值。这会给SVM添加predict_proba（）和predict_log_proba（）两种方法。
- 这个问题仅适用于线性支持向量机，因为核SVM只能使用对偶问题。对于SVM问题来说，原始形式的计算复杂度与训练实例m的数量成正比，而其对偶形式的计算复杂度与某个介于m2和m3之间的数量成正比。所以如果实例的数量以百万计，一定要使用原始问题，因为对偶问题会非常慢。
- 如果一个使用RBF核训练的支持向量机对欠拟合训练集，可能是由于过度正则化导致的。你需要提升gamma或C（或同时提升二者）来降低正则化。
- 我们把硬间隔问题的QP参数定义为H’、f’、A’及b’（见5.4.3节）。软间隔问题的QP参数还包括m个额外参数（ n p = n + 1 + m n_p=n+1+m np=n+1+m）及 m m m个额外约束（ n c = 2 m n_c=2m nc=2m）。它们可以这样定义：H等于在H’右侧和底部分别加上m列和m行个0： H = [ H ′ … 0 … … … 0 … 0 ] H = \begin{bmatrix}H'&…&0 \…&…&…\0&…&0 \end{bmatrix} H=⎣⎡H′…0………0…0⎦⎤。f等于有m个附加元素的f’，全部等于超参数C的值。b等于有m个附加元素的b’，全部等于0。A等于在A’的右侧添加一个m×m的单位矩阵Im，在这个单位矩阵的正下方再添加单位矩阵-Im，剩余部分为0： A = [ A ′ I m 0 − I m ] A = \begin{bmatrix}A'&I_m\0&-I_m \end{bmatrix} A=[A′0Im−Im]。
版权归原作者 新四石路打卤面 所有， 如有侵权，请联系我们删除。