第 11 章 支持向量机

本章开始，我们介绍非参数化模型。与参数化模型不同，非参数化模型对数据分布不做先验的假设，从而能够更灵活地适配到不同的数据分布上。但另一方面，灵活性也使其对数据更为敏感，容易出现过拟合现象。本章主要介绍一个经典的非参数化模型：支持向量机（support vector machine，SVM），以及其求解算法序列最小优化（sequential minimal optimization，SMO）算法，并利用其完成平面点集的二分类任务。

由于非参数化模型与数据集大小有关，我们假设数据集，其中是输入向量，是输入数据的分类。为了下面理论推导方便，这里我们用-1代替0作为类别标签。线性的SVM假设数据集中的点是线性可分的。需要注意，该假设与SVM是非参数化模型并不矛盾，因为SVM仍然需要与数据集大小相匹配的参数量来求解分隔平面，具体的求解流程我们会在下文详细说明。与之相反，逻辑斯谛回归作为参数化模型，其参数的维度只和输入向量的维度有关。

通常来说，即使数据集是线性可分的，可以将其分开的超平面也有无数种选择。如图11-1所示，任意一条绿色或红色的直线都可以将平面上的橙色点和蓝色点分开。然而，如果我们考虑到现实场景中可能的噪声和扰动，这些分隔线就会产生区别。假如下图中的数据点实际所处的位置可能在它们旁边标出的虚线圆圈内的任意一处，那么图中的两条红色虚线就有可能给出错误的分类结果。因此，为了使分隔直线对数据点的扰动或噪声的鲁棒性更强，我们希望从这无数个可以分隔两个点集的超平面中，挑选出与任意一点间隔（margin）的最小值最大的平面。

11.1 支持向量机的数学描述

我们首先来考虑如何计算样本点与平面的间隔。如图11-2所示，设决策边界给出的超平面方程为，其中和为支持向量机的参数，方向就是该平面的法线方向。设样本到平面的距离是，那么从出发，沿着法线方向经过长度，应当正好到达平面上。因此，满足

或者

出现两个不同的方程是因为我们还没有确定是在法线的方向还是法线的反方向。如果在法线方向，那么有，反之则是。因此，不妨规定使的样本点的类别，使的样本点的类别。对于分类问题，标签的具体值我们可以任意替换，只要最终能对应回原始类别即可。另外，我们设使的点的类别，因为这些点正好处于该超平面上，从而表示超平面无法对其进行分类。这样，我们就可以把上面两个方程统一起来，写成

或者等价变形为

对上式来说，当和的大小同时变为倍时，式中的分母也变为倍，这时划分超平面完全不变。因此，我们不妨设，称为函数间隔（functional margin），而将几何间隔（geometric margin）看作函数间隔对的长度归一化的结果。

我们希望所有样本到平面的几何间隔的最小值最大。设，，那么。于是，支持向量机的优化目标可以写为：

上面已经提到，函数间隔关于和的大小并不影响实际的几何间隔，因为其变化总会被所抵消。因此，不妨令。这样上面的优化目标就变为：

然而，优化目标是非凸的，其求解较为困难。考虑到函数关于单调递减，最大化与最小化的任意一个单调递增函数都等价。为了求解方便，我们选择凸的单调递增函数，进一步将优化目标等价地写为：

由于，其二次函数在定义域内是单调递增的，并且为凸函数。其中，系数是为了后续求导简洁，与MSE中的作用类似。

至此，我们讨论了数据线性可分的情况。如果数据线性不可分，我们可以适当放低上面的约束要求，引入松弛变量，将约束问题改写为：

可以看出，松弛变量允许某个样本点的类别与超平面给出的分类不同。但是，对这些分类错误的样本点，我们也需要进行惩罚。因此，我们在优化的目标函数上加入值本身作为惩罚项，其中是惩罚系数。

对于带约束的凸优化问题，数学上有一套成熟的解决方式，将其转化为更容易的对偶问题求解。我们将较为繁琐的数学推导放在本章的拓展阅读中，感兴趣的读者可以自行学习，这里我们直接给出结论。求解上面的优化问题等价于求解下面的二次规划：

其中是待求解的参数。这时可以看出，SVM问题的参数量是与数据集的规模相当的。当数据集规模增大时，其参数量也相应变多，表现出非参数化模型的特性。

当解出最优的后，SVM的参数和可以由下式计算得到：

并且，这组最优参数满足。因此对于数据集中的任意一个样本来说，要么其对应的参数，要么其与支持向量机对应的超平面的函数间隔，从而是所有样本中与该超平面间隔最小的。我们称这些与超平面间隔最小的向量称为支持向量（supporting vector）。引入松弛变量后，对于那些类别与SVM的超平面相反的向量，由于其，会影响SVM的参数，因此这些向量也属于支持向量。

设支持向量的集合为，那么上面所有关于的求和只需要在集合中进行，因为其余非支持向量对应的都为零，对求和没有贡献。进一步，当我们需要用支持向量机预测某个新样本的类别时，需要计算的正负性，即计算：

这样，用SVM进行预测的时间复杂度从变为了。通常情况下支持向量只占数据集的很小一部分，因此，利用支持向量的特性，SVM 模型建立完成后，再进行预测的时间复杂度就大大减小了。这一优势在线性 SVM 中并不明显，因为我们可以直接计算出的值，但是对于后面会介绍的带有非线性核函数的SVM来说，其优化是相当可观的。

现在，我们只需要从上面的二次规划问题中解出。然而，传统的求解二次规划问题的算法时间开销都非常大。因此，我们通常使用专门针对SVM的问题形式所设计的序列最小优化（SMO）算法来求解SVM的优化问题。

11.2 序列最小优化

序列最小优化的核心思想是，同时优化所有的参数较为困难，因此每次可以选择部分参数来优化。由于优化问题中有等式约束，我们每次选取两个不同的参数和，而固定其他的参数，只优化这两个参数从而保证等式约束一直成立。完成后，再选取另两个参数，固定其他个参数，进行优化。如此反复迭代，直到目标函数的值收敛位置。无论目标是需要被最大化还是最小化，SMO算法都可以工作。下面，我们以固定和为例，演示SMO算法的流程。

固定与后，优化问题的目标为：

其中是与和无关的常数。注意到上式中样本向量不会单独出现，而都以两个样本做内积的形式出现。回忆线性回归中的核技巧，我们将样本向量之间的内积记为矩阵，其中的行向量是数据集中的样本，根据矩阵乘法的规则和向量内积的对称性可知。注意到，目标函数可以用改写为：

第二个约束条件表明，与不是独立的，我们可以将用表示。记，则有：

将上式代入优化目标消去，可得：

其中，是与无关的常数，且：

如果数据集中没有相同的样本，那么严格有。因此，该优化问题本质上是寻找参数的二次函数的最大值点，非常容易计算。注意参数的取值范围是，使其二次函数取最大值的有3种情况：

其对应的大致图像如图11-3所示。

解出的最优值后，就得到的最优值。我们还需要保证也在范围内，因此在计算之前，再用这一条件对进行裁剪。

为了代码实现方便，我们进一步化简。设，则：

将与代入的表达式，得到：

于是可得：

这一形式更加简洁和对称。

在计算出和之后，阈值同样需要更新，以保证通过对偶问题推导出的SVM优化问题成立。下面我们粗略解释其原因，感兴趣的读者也可以参考本章的拓展阅读，详细了解为何要进行这样的保证。简单来说，样本对应的系数反映了样本的分类性质。说明样本被正确分类，说明样本被错误分类，这两种情况下都取边界值，样本不是支持向量。反之，时，其对应的样本必定是支持向量。这也反映出，SVM的分类边界完全是由支持向量所决定的。回到SMO中，当时，其对应的样本必定是支持向量，因此我们需要保证更新过参数的SVM一定会将分类为。设新的阈值为，将代入SVM的分类表达式可得：

同理，当时，下面的阈值可以保证SVM将分类为：

而如果和都在范围内，说明两个样本都是支持向量，此时上面两种方法算出的和是相等的。与此相对，如果和都取边界值或者，说明两个样本都不是支持向量，对的条件也就可以放宽，与之间的任何值都满足对偶问题成立的条件。此时我们通常取为两种极端情况的平均值。

最后，我们将更新后的和代回原目标函数，得到。接下来，我们再随机选取一对参数，例如和，固定其他参数，用相同的方式求解新的目标函数。注意此时参数和的值已经更新为刚刚解出的最优值和。这样反复迭代下去，直到更新参数时，的变化量小于某个预设的精度常数，或迭代次数达到预设的最大轮数为止。由于计算的时间复杂度较高，实践中通常采用后者。

11.3 动手实现SMO求解SVM

下面，我们按照上节讲述的步骤来动手实现SMO算法求解SVM。我们先考虑最简单的线性可分的情况，本节的数据集linear.csv包含了一些平面上的点及其分类。数据文件的每一行有3个数，依次是点的横坐标 、纵坐标 和类别 。由于数据集非常简单，明显线性可分，SVM应当能达 到100%的正确率，因此我们不再划分训练集和测试集，只以此为例讲解代码实现。

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
from tqdm import tqdm, trange

data = np.loadtxt('linear.csv', delimiter=',')
print('数据集大小：', len(data))
x = data[:, :2]
y = data[:, 2]

# 数据集可视化
plt.figure()
plt.scatter(x[y == -1, 0], x[y == -1, 1], color='red', label='y=-1')
plt.scatter(x[y == 1, 0], x[y == 1, 1], color='blue', marker='x', label='y=1')
plt.xlabel(r'$x_1$')
plt.ylabel(r'$x_2$')
plt.legend()
plt.show()

数据集大小： 200

下面我们来实现SVM的主要部分SMO算法，具体的讲解放在代码注释中。

def SMO(x, y, ker, C, max_iter):
    '''
    SMO算法
    x，y：样本的值和类别
    ker：核函数，与线性回归中核函数的含义相同
    C：惩罚系数
    max_iter：最大迭代次数
    '''
    # 初始化参数
    m = x.shape[0]
    alpha = np.zeros(m)
    b = 0
        
    # 预先计算所有向量的两两内积，减少重复计算
    K = np.zeros((m, m))
    for i in range(m):
        for j in range(m):
            K[i, j] = ker(x[i], x[j])
    
    for l in trange(max_iter):
        # 开始迭代
        for i in range(m):
            # 有m个参数，每一轮迭代中依次更新
            # 固定参数alpha_i与另一个随机参数alpha_j，并且保证i与j不相等
            j = np.random.choice([l for l in range(m) if l != i])
            
            # 用-q/2p更新alpha_i的值
            eta = K[j, j] + K[i, i] - 2 * K[i, j] # 分母
            e_i = np.sum(y * alpha * K[:, i]) + b - y[i] # 分子
            e_j = np.sum(y * alpha * K[:, j]) + b - y[j]
            alpha_i = alpha[i] + y[i] * (e_j - e_i) / (eta + 1e-5) # 防止除以0
            zeta = alpha[i] * y[i] + alpha[j] * y[j]

            # 将alpha_i和对应的alpha_j保持在[0,C]区间
            # 0 <= (zeta - y_j * alpha_j) / y_i <= C
            if y[i] == y[j]:
                lower = max(0, zeta / y[i] - C)
                upper = min(C, zeta / y[i])
            else:
                lower = max(0, zeta / y[i])
                upper = min(C, zeta / y[i] + C)
            alpha_i = np.clip(alpha_i, lower, upper)
            alpha_j = (zeta - y[i] * alpha_i) / y[j]
            
            # 更新b
            b_i = b - e_i - y[i] * (alpha_i - alpha[i]) * K[i, i] - y[j] * (alpha_j - alpha[j]) * K[i, j]
            b_j = b - e_j - y[j] * (alpha_j - alpha[j]) * K[j, j] - y[i] * (alpha_i - alpha[i]) * K[i, j]
            if 0 < alpha_i < C:
                b = b_i
            elif 0 < alpha_j < C:
                b = b_j
            else:
                b = (b_i + b_j) / 2
            
            # 更新参数
            alpha[i], alpha[j] = alpha_i, alpha_j

    return alpha, b