第 11 章 支持向量机

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

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

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

seperation
图 11-1 用直线分隔带噪声的点集

11.1 支持向量机的数学描述

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

或者

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

或者等价变形为

margin
图 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所示。

SMO
图 11-3 SMO最优解示意图

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

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

代入的表达式,得到:

于是可得:

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

在计算出之后,阈值同样需要更新,以保证通过对偶问题推导出的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

png

下面我们来实现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

利用SMO算法解出后,我们可以得到SVM的参数。我们把该算法应用在导入的线性数据集上,绘制出SVM给出的分隔直线,并标记出支持向量。

# 设置超参数
C = 1e8 # 由于数据集完全线性可分,我们不引入松弛变量
max_iter = 1000
np.random.seed(0)
alpha, b = SMO(x, y, ker=np.inner, C=C, max_iter=max_iter)
0%| | 0/1000 [00:00<?, ?it/s]100%|██████████| 1000/1000 [00:16<00:00, 59.85it/s]
# 用alpha计算w,b和支持向量
sup_idx = alpha > 1e-5 # 支持向量的系数不为零
print('支持向量个数:', np.sum(sup_idx))
w = np.sum((alpha[sup_idx] * y[sup_idx]).reshape(-1, 1) * x[sup_idx], axis=0)
print('参数:', w, b)
# 绘图
X = np.linspace(np.min(x[:, 0]), np.max(x[:, 0]), 100)
Y = -(w[0] * X + b) / (w[1] + 1e-5)
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], marker='x', color='blue', label='y=1')
plt.plot(X, Y, color='black')
# 用圆圈标记出支持向量
plt.scatter(x[sup_idx, 0], x[sup_idx, 1], marker='o', color='none',
edgecolor='purple', s=150, label='support vectors')
plt.xlabel(r'$x_1$')
plt.ylabel(r'$x_2$')
plt.legend()
plt.show()
支持向量个数: 6
参数: [-1.0211867 1.66445549] -1.3343767573871523

png

11.4 核函数

对于略微有些线性不可分的数据,我们采用松弛变量的方法,仍然可以导出SVM的分隔超平面。然而,当数据的分布更加偏离线性时,可能完全无法用线性的超平面进行有效分类,松弛变量也就失效了。为了更清晰地展示非线性的情况,我们读入双螺旋数据集spiral.csv并绘制数据分布。该数据集包含了在平面上呈螺旋分布的两组点,同类的点处在同一条旋臂上。

data = np.loadtxt('spiral.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], marker='x', color='blue', label='y=1')
plt.xlabel(r'$x_1$')
plt.ylabel(r'$x_2$')
plt.legend()
plt.axis('square')
plt.show()
数据集大小: 194

png

显然,平面上任意一条直线都无法为上图的双螺旋数据集给出分类。因此,我们需要引入非线性的特征映射。在神经网络一章中我们已经提到,非线性函数可以使数据升维,将在低维中线性不可分的数据映射到高维空间,使其变得线性可分。设映射函数为。将线性SVM中的全部替换为,并进行相同的数学推导,可以得到对偶问题的优化目标函数为:

为了简化上式,我们利用核技巧,定义核函数。第5章中我们曾介绍过,引入核函数后,计算特征映射的时间复杂度被大大降低了。与不带有特征映射时类似,现在SVM对新样本的预测为:

虽然我们不知道,无法按照原来的方法由计算。但是,我们可以直接利用核函数计算

从而也可以按原方法计算得出:

实践中,仍然由SMO算法求解时同步迭代计算。这时,SVM在计算时只需要用到支持向量的优点就很明显了。在数据集上建立好SVM模型后,我们可以只保留支持向量,而将剩余的数据都舍弃,减小存储模型的空间占用。

现在,我们的任务就变成寻找合适的核函数,来让原本线性不可分的数据线性可分。通常来说,核函数应当衡量向量之间的相似度。常用的核函数有:

  • 内积核:,该函数即为线性SVM所用的核函数。
  • 简单多项式核:
  • 高斯核:,又称径向基函数(radial basis function,RBF)核。
  • 余弦相似度核:,该函数计算的是向量之间夹角的余弦值。
  • Sigmoid核:,可以证明,带有sigmoid核的SVM等价于两层的多层感知机。

下面,我们尝试用不同的非线性核函数对螺旋数据集进行分类,并观察分类效果。首先,我们实现上文介绍的几个核函数。

# 简单多项式核
def simple_poly_kernel(d):
def k(x, y):
return np.inner(x, y) ** d
return k
# RBF核
def rbf_kernel(sigma):
def k(x, y):
return np.exp(-np.inner(x - y, x - y) / (2.0 * sigma ** 2))
return k
# 余弦相似度核
def cos_kernel(x, y):
return np.inner(x, y) / np.linalg.norm(x, 2) / np.linalg.norm(y, 2)
# sigmoid核
def sigmoid_kernel(beta, c):
def k(x, y):
return np.tanh(beta * np.inner(x, y) + c)
return k

然后,我们依次用这4种核函数计算SVM在双螺旋数据集上的分类结果。其中,简单多项式核取;RBF核取标准差 ;sigmoid核取。为了更清晰地展示结果,我们在的平面上网格状均匀选点,用构建好的SVM判断这些点的类别,并将其所在小网格涂成对应的颜色。

kernels = [
simple_poly_kernel(3),
rbf_kernel(0.1),
cos_kernel,
sigmoid_kernel(1, -1)
]
ker_names = ['Poly(3)', 'RBF(0.1)', 'Cos', 'Sigmoid(1,-1)']
C = 100
max_iter = 500
# 绘图准备,构造网格
np.random.seed(0)
plt.figure()
fig, axs = plt.subplots(2, 2, figsize=(10, 10))
axs = axs.flatten()
cmap = ListedColormap(['coral', 'royalblue'])
# 开始求解 SVM
for i in range(len(kernels)):
print('核函数:', ker_names[i])
alpha, b = SMO(x, y, kernels[i], C=C, max_iter=max_iter)
sup_idx = alpha > 1e-6 # 支持向量的系数不为零
sup_x = x[sup_idx] # 支持向量
sup_y = y[sup_idx]
sup_alpha = alpha[sup_idx]
# 用支持向量计算 w^T*x
def wx(x_new):
s = 0
for xi, yi, ai in zip(sup_x, sup_y, sup_alpha):
s += yi * ai * kernels[i](xi, x_new)
return s
# 构造网格并用 SVM 预测分类
G = np.linspace(-1.5, 1.5, 100)
G = np.meshgrid(G, G)
X = np.array([G[0].flatten(), G[1].flatten()]).T # 转换为每行一个向量的形式
Y = np.array([wx(xi) + b for xi in X])
Y[Y < 0] = -1
Y[Y >= 0] = 1
Y = Y.reshape(G[0].shape)
axs[i].contourf(G[0], G[1], Y, cmap=cmap, alpha=0.5)
# 绘制原数据集的点
axs[i].scatter(x[y == -1, 0], x[y == -1, 1], color='red', label='y=-1')
axs[i].scatter(x[y == 1, 0], x[y == 1, 1], marker='x', color='blue', label='y=1')
axs[i].set_title(ker_names[i])
axs[i].set_xlabel(r'$x_1$')
axs[i].set_ylabel(r'$x_2$')
axs[i].legend()
plt.tight_layout()
plt.savefig('output_24_2.png')
plt.savefig('output_24_2.pdf')
plt.show()
核函数: Poly(3)
100%|██████████| 500/500 [00:07<00:00, 66.05it/s]
核函数: RBF(0.1)
100%|██████████| 500/500 [00:07<00:00, 63.08it/s]
核函数: Cos
100%|██████████| 500/500 [00:08<00:00, 59.20it/s]
核函数: Sigmoid(1,-1)
100%|██████████| 500/500 [00:08<00:00, 58.54it/s]
<Figure size 640x480 with 0 Axes>

png

从实验结果图我们可以看出,不同的核函数对SVM模型的分类效果是截然不同的。对于双螺旋数据的二分类任务,高斯核函数(RBF)带给SVM的性能要明显好于其他核函数。根据高斯核函数的公式,我们可以看到高斯核本质是在衡量样本和样本之间基于欧几里得距离的相似度,这样使得欧几里得距离近的样本更好的聚在一起,在高维空间中达到线性可分。此外,松弛变量带来的对错分类样本的容忍度也会极大影响分类结果,读者可以调整的值,观察不同核函数决策边界的变化。

11.5 Sklearn中的SVM工具

机器学习工具库sklearn提供了封装好的SVM工具,且支持多种内置核函数。我们以RBF核函数为例,复现上面在双螺旋数据集上的分类结果。在sklearn.SVM中,SVC表示用SVM完成分类任务,SVR表示用SVM完成回归任务,这里我们选用SVC。此外,它的参数和我们上面的公式在表达上有细微的区别。对于RBF核函数,其参数为。上一节我们设置,因此这里对应的参数为。我们同样在平面上采样,绘制出该SVM给出的分类边界。可以看出,其结果与我们自己实现的SVM基本一致。

# 从sklearn.svm中导入SVM分类器
from sklearn.svm import SVC
# 定义SVM模型,包括定义使用的核函数与参数信息
model = SVC(kernel='rbf', gamma=50, tol=1e-6)
model.fit(x, y)
# 绘制结果
fig = plt.figure(figsize=(6,6))
G = np.linspace(-1.5, 1.5, 100)
G = np.meshgrid(G, G)
X = np.array([G[0].flatten(), G[1].flatten()]).T # 转换为每行一个向量的形式
Y = model.predict(X)
Y = Y.reshape(G[0].shape)
plt.contourf(G[0], G[1], Y, cmap=cmap, alpha=0.5)
# 绘制原数据集的点
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], marker='x', color='blue', label='y=1')
plt.xlabel(r'$x_1$')
plt.ylabel(r'$x_2$')
plt.legend()
plt.show()

png

11.6 本章小结

本章介绍了支持向量机的原理及其求解算法SMO。由于SVM属于非参数化模型,其模型中的参数与数据集的规模相同,求解较为复杂,但SMO算法大大降低了求解的难度。并且在求解完成后,我们只需要保留支持向量,就可以继续利用模型完成后续的预测任务,其时间和空间复杂度都下降很多。对于非线性分布的数据,我们可以通过引入非线性的核函数使SVM完成分类任务,达到和神经网络中激活函数类似的效果。

不同的核函数适用的场景有所不同,其中最常用的是RBF核函数。但是它对参数非常敏感,读者可以尝试调整上面例子中的,观察分类边界的变化。一般来说,越大,分类边界就越光滑,其曲折越少;越小,分类边界的曲折越多,也越容易出现过拟合现象。因此,虽然上例中没有调整防止过拟合的参数,但仍然需要注意在适当的时候调节来缓解过拟合。Sigmoid核函数虽然使SVM和两层的MLP等价,但是其参数调节非常困难,两个参数都没有较为直观的理解方式。此外,如果参数设置不合适,sigmoid核函数可能无法分解成 的形式,成为无效的核函数。因此在实践中,sigmoid核函数和简单多项式、余弦相似度等其他核函数一样,只在数据分布较为特殊的情况下使用。

习题

  1. 以下关于SVM的说法不正确的是: A. SVM的目标是寻找一个使最小几何间隔达到最大值的分割超平面。 B. 分割超平面不会随的幅值改变而改变,但是函数间隔却会随之改变。 C. 为训练完成的SVM中添加新的不重复的样本点,模型给出的分隔平面可能不会改变。 D. 样本函数间隔的数值越大,分类结果的确信度越大。

  2. 以下关于核函数的说法不正确的是: A. 核函数的数值大小反映了两个变量之间的相似度高低。 B. SVM只着眼于内积计算,因此训练时可以使用核函数来代替特征映射。 C. SVM在训练过程中不需要进行显式的特征映射,不过在预测时需要计算样本进行特征映射。 D. 核函数将特征映射和内积并为了一步进行计算,所以大大降低了时间复杂度。

  3. 在逻辑斯谛回归中,我们也用解析方式求出了模型参数,但是其中涉及复杂度很高的矩阵乘法和矩阵求逆。为什么支持向量机的解析结果中不包含这类复杂运算?(提示:逻辑斯谛回归和支持向量机分别考虑了样本到分隔平面的什么间隔?)

  4. 对于同一个数据集,逻辑斯谛回归和支持向量机给出的分隔平面一样吗?用本章的linear.csv数据集验证你的想法。试着给数据集中手动添加一些新的样本点,或者更改已有样本点的分类。两种算法给出的分隔平面有什么变化?

  5. 思考RBF核函数对应的函数是什么,建议查阅相关文献来寻找答案。进一步思考输出为无穷维的特征映射的意义是什么。

  6. 试基于本章代码,标记出双螺旋数据上使用RBF核函数的SVM模型的支持向量,并讨论这些数据点成为支持向量的原因。

  7. 试通过参数量与数据集大小的关系、参数更新方式等视角,分析和体会SVM模型的原问题对应参数化模型,而对偶问题对应非参数化模型。

拓展阅读:SVM对偶问题的推导

对一般形式的带约束的凸优化问题

定义其拉格朗日函数(Lagrangian function)为:

其中称为拉格朗日乘子。拉格朗日函数的值不仅与原问题的参数有关,还与乘子有关,因此,可以利用乘子的值来表达原问题的约束条件。记原问题为:

并且定义参数使得原问题的约束条件被违反,即时,原问题。反过来说,如果原问题的约束条件都被满足,那么,从而拉格朗日函数的第3项全部为零。并且由。如果要让最大,那么所有拉格朗日乘子都应当使,否则的值会减小。因此,当约束条件满足时,拉格朗日函数的最大值恰好就等于原问题的目标函数,从而原问题可以写为:

于是,最开始带约束的优化问题等价于对原问题的无约束优化 :

记该问题的最优值为

至此,我们只是通过拉格朗日函数对原问题进行了等价变形,并没有降低问题求解的难度。为了真正解决该优化问题,我们考虑另一个稍微有些区别的函数,定义为:

将上面优化问题中计算的顺序交换,定义其对偶问题为:

记其最优值为。可以证明,先取后取的对偶问题最优值要小于等于先取后取的原问题最优值。然而,在满足某些特殊条件的情况下,两者的最优值是相等的,即。对于一个凸优化问题,如果其约束条件可以被严格满足,即存在使得以及,那么必然存在,满足:

  • 是原问题的解;
  • 是对偶问题的解;
  • 最优值

以及卡鲁什-库恩-塔克条件(Karush-Kuhn-Tucker conditions),简称KKT条件:

  • 稳定性:
  • 原问题满足性:
  • 对偶问题满足性:
  • 互补松弛性:

反过来,如果某一组满足KKT条件,那么它们也是原问题和对偶问题的解。KKT条件中的前3个条件较好理解,都是优化问题本身的约束;最后一个互补松弛性我们在推导时也提到过,否则会使目标拉格朗日函数的值减小,与是最优解矛盾。

根据上面的讨论,如果一个凸优化问题满足KKT条件,且其对偶问题比原问题更容易解决,那么我们可以通过求对偶问题的解来得到原问题的解。对线性版本的支持向量机的优化问题

来说,都是问题的参数。我们将约束条件重写为,得到其拉格朗日函数为:

为了求其最小值,令其对的梯度等于,得:

我们把代入拉格朗日函数的表达式,得到对偶函数的表达式为:

于是,对偶优化问题的形式为:

而引入松弛变量后,我们用类似的方式也可以求出其对偶问题。具体的推导过程与上面基本一致,我们在此略去,感兴趣的读者可以自行尝试推导。最后的结果为:

其中的形式与不带松弛变量的版本相同。该对偶问题是关于的二次规划问题,相比于原问题来说求解难度大大降低了。可以验证,这一问题的形式满足KKT条件,从而我们可以通过求解对偶问题得到原问题的解。并且根据KKT条件中的互补松弛性,最优的满足