支持向量机（SVM） 是一种广泛使用且强大的监督学习算法，适用于分类和回归问题。其核心思想是寻找能够最好地区分不同类别数据点的决策边界。在本课中，我们将介绍 SVM 的基本概念与原理，并探讨其在实际中的应用。

什么是 SVM？

假设某人在银行工作，职责是根据申请人的财务历史决定是否批准贷款申请。他们拥有一个包含信用评分、收入、负债收入比等特征以及过往审批记录的贷款数据集。任务是使用 SVM 构建一个用于预测未来贷款申请结果的模型。

首先，将每个贷款申请根据其特征映射到特征空间中，并将其标记为“已批准”或“被拒绝”，从而在数据集中形成两个不同的类别。接着，尝试找到一个能线性划分这两类数据的决策边界。

SVM 会寻找最佳的超平面来分隔这两个类别，也就是将已批准和被拒绝的贷款申请分开的决策边界。该超平面的关键在于最大化间隔（margin），即超平面到每一类中最接近样本点之间的距离。这意味着我们希望超平面尽可能远离最近的已批准和被拒绝的贷款申请。

然而，在确定超平面时，并不需要考虑所有贷款申请。只有那些最靠近超平面的样本点——称为支持向量（support vectors）——才会影响超平面的位置。这种机制使得 SVM 具有较高的内存效率，并且能够处理大量特征的情况。

上图展示了两种分类器对数据集中正负类别的划分情况。蓝色线代表 SVM 分类器，绿色线代表另一种分类器。虚线上标注的点被称为支持向量，因为它们距离超平面最近；两条蓝色虚线之间的距离称为间隔（margin），这是 SVM 所要最大化的关键指标。绿色线不能被视为 SVM 的超平面，因为它没有实现最大间隔。

注意：可以将 SVM 理解为具有最大间隔的广义线性判别方法。

有符号距离与无符号距离

在 SVM 中，超平面由权重向量 $\bold w$ 和偏置项 $b$ 定义，其方程可写为 $\bold w^T\bold x + b = 0$。其中，$\bold x$ 表示一个数据点，$\bold w$ 是超平面的法向量，$b$ 表示超平面相对于原点的偏移量。

某个点 $\bold x_i$ 到超平面的有符号距离是指该点到超平面的距离，并考虑了法向量的方向。之所以“有符号”，是因为当点位于超平面的不同侧时，该距离可正可负。

如果法向量 $\bold w$ 与从超平面指向该点的方向一致，则距离为正值；若方向相反，则为负值。如图所示，位于超平面上方的所有点具有正距离，下方的所有点则具有负距离。

注意：除非特别说明，我们将偏置参数视为向量 $\bold w$ 的一部分，并在特征向量末尾添加常数项 1。

通过映射函数 $\phi$ 定义的特征空间中的超平面可表示为 $\bold w^T\phi(\bold x)=0$。给定一个二分类数据集 $D=\{(\bold x_1, y_1), (\bold x_2, y_2), \dots,(\bold x_n, y_n)\}$，其中 $\bold x_i \in \R^d$，$y_i \in \{-1, 1\}$，则点 $\bold x_i$ 到超平面 $\bold w^T\phi(\bold x)=0$ 的有符号距离 $d_i$ 可定义为：

$$d_i = \frac{\bold w^T\phi(\bold x_i)}{\|\bold w\|}$$

但有符号距离并不总是便于使用。为了提高可解释性和计算便利性，可通过乘以类别标签将其转换为无符号距离：

$$d_i = \frac{y_i\bold w^T\phi(\bold x_i)}{\|\bold w\|}$$

其中 $y_i$ 是点 $\bold x_i$ 的类别标签，取值为 $-1$ 或 $+1$。通过将有符号距离乘以类别标签，得到的无符号距离始终为正，表明我们的超平面实现了线性分离。若出现负值，则说明该点被错误分类。例如，图中的点 $p$ 具有负的无符号距离，表示当前超平面对其分类错误。这种方式更易于理解和优化，也简化了后续的优化问题求解过程。

SVM 的目标函数

SVM 的目标是寻找一个能将数据点划分为两类且具有最大间隔的超平面。我们希望找到满足以下两个条件的超平面：所有正类样本位于一侧，所有负类样本位于另一侧，同时间隔尽可能大。如果这样的超平面存在（在特征空间中两类数据线性可分的情况下总能找到），那么任意点 $\bold x_i$ 的无符号距离可表示为：

$$\frac{y_i\bold w^T\phi(\bold x_i)}{\|\bold w\|}$$

最大间隔解可通过求解如下优化问题获得：

$$\begin{align*} & \max_{\bold w}\bigg[\min_{i}\bigg(\frac{y_i\bold w^T\phi(\bold x_i)}{\|\bold w\|}\bigg)\bigg] \\ =&\max_{\bold w}\bigg[\frac{1}{\|\bold w\|}\min_{i}\big(y_i\bold w^T\phi(\bold x_i)\big)\bigg] \end{align*}$$

该优化问题旨在最大化任意样本点到超平面的最小无符号距离，同时保证所有样本均被正确分类。

二维可视化

考虑输入向量为二维的情形，即 $\bold x=\begin{bmatrix}x_{1} \\ x_{2}\end{bmatrix}$，并设 $\phi(\bold x) = \begin{bmatrix}1 \\ x_{1} \\ x_{2}\end{bmatrix}$，参数向量为 $\bold w = \begin{bmatrix}w_0 \\ w_{1} \\ w_{2}\end{bmatrix}$。下面的代码要求用户输入直线 $w_1x_1+w_2x_2+w_0=0$ 中的 $w_0$ 值，并显示对应的直线及其间隔。此时 $w_1$ 和 $w_2$ 已设定为最优值，目标是调整 $w_0$ 以获得最大间隔。

注意：若输入为 x，则代码将使用最优值 $w_0 = -7.3505$ 绘制最佳直线。

上述代码允许用户输入不同的 $w_0$ 值，而 $w_1$ 和 $w_2$ 已固定为最优值。通过分别输入 x 和 1，生成了上面两幅图。我们可以尝试不同输入值，观察其对结果的影响。

间隔值对于判断超平面是否有效至关重要。若间隔值为正，则认为该超平面是一个有效的分类器，且该值会在图标题中显示。支持向量也会用黑色标记突出显示（如上图所示）。但如果间隔值为负，则图标题会提示该超平面无法有效分类。

1import numpy as np
2from sklearn import datasets
3import matplotlib.pyplot as plt
4from sklearn import svm
5from sklearn.datasets import make_blobs
6
7def get_margin(X, Y, w1,w2,w0):
8    w = np.array([w1,w2,w0])[:, np.newaxis]
9    X_hat = np.hstack((X,np.ones((X.shape[0],1))))
10    d = X_hat.dot(w).flatten()*Y.flatten()
11    if np.sum(d<0) > 0:
12        return -1,-1
13    margin = np.min(d)
14    idx = np.argmin(d)
15    return margin, idx
16
17n = 6
18X, Y = make_blobs(n_samples=n, centers=2, n_features=2,
19                   random_state=4)
20Y[Y==0] = -1
21
22x1_samples = X[Y==1,:]
23x2_samples = X[Y==-1,:]
24
25fig = plt.figure()
26
27plt.scatter(x1_samples[:,0],x1_samples[:,1], c = 'red', marker='+',s=150)
28plt.scatter(x2_samples[:,0],x2_samples[:,1], c = 'green', marker='o',s=150)
29
30plt.xlabel('$x_1$'); plt.ylabel('$x_2$')
31
32clf_linear = svm.SVC(kernel = 'linear')
33clf_linear.fit(X,Y)
34
35
36w1, w2, w0 = clf_linear.coef_[0][0],clf_linear.coef_[0][1], input()
37if w0 == 'x':
38  w1, w2, w0 = clf_linear.coef_[0][0],clf_linear.coef_[0][1], clf_linear.intercept_[0]
39else:
40  w0 = float(w0)
41
42print(f'w1={w1}\nw2={w2}\nw0={w0}')
43p1_x2 = 1
44p1_x1 = -(w0+w2*p1_x2)/w1
45
46p2_x2 = 4
47p2_x1 = -(w0+w2*p2_x2)/w1
48
49plt.plot([p1_x1,p2_x1],[p1_x2,p2_x2],c='b')
50
51sv_indices = clf_linear.support_
52sv_x = X[sv_indices]
53sv_y = Y[sv_indices]
54
55sv_x1_samples = sv_x[sv_y==1,:]
56sv_x2_samples = sv_x[sv_y==-1,:]
57
58plt.scatter(sv_x1_samples[:,0],sv_x1_samples[:,1], c = 'k', marker='+',s=150)
59plt.scatter(sv_x2_samples[:,0],sv_x2_samples[:,1], c = 'k', marker='o',s=150)
60
61margin, idx = get_margin(X, Y, w1,w2,w0)
62title = 'Not a separator'
63if margin >= 0:
64    title = f'The margin is {margin}'
65plt.title(title)
66plt.savefig("SVM",dpi=600)

SVM 的优点

• SVM 在高维空间中表现优异，即使特征数量超过样本数量也能良好运行。
• 由于决策函数仅依赖训练样本的一个子集（即支持向量），因此具有较高的内存效率。
• 具备高度灵活性，可通过指定不同的核函数来构建决策函数。常见的核包括线性核、多项式核和径向基函数（RBF）核，同时也支持自定义核函数。

SVM 的缺点

尽管 SVM 拥有许多优势，但也存在一些局限性：

• 当特征数量远大于样本数量时，容易发生过拟合。因此，选择合适的核函数和正则化参数至关重要。
• SVM 不直接提供概率估计，若需获取概率输出，通常需要通过五折交叉验证等方式进行计算，成本较高。