支持向量机(SVM)是一种广泛应用于分类和回归问题的机器学习算法。它的核心思想是在特征空间中寻找一个最优的超平面，使得不同类别的数据点之间的间隔最大化。本文将详细介绍SVM的学习策略，包括优化问题、优化算法以及分类方法，并提供相应的Python代码实现。
在介绍SVM的学习策略之前，先来了解一些基本概念。
功能间隔(Function Margin)：对于给定的训练集T和超平面(w, b)，超平面(w, b)与样本(xi, yi)之间的功能间隔定义为：
功能间隔反映了分类结果的置信度。如果超参数(w, b)成比例变化，例如将(w, b)变为(2w, 2b)，虽然超平面没有变化，但功能间隔会扩大两倍。因此，对w施加一些约束，使其规范化，例如||w|| = 1。然后，间隔被称为几何间隔(Geometric Margin)。
几何间隔(Geometric Margin)：对于给定的训练集T和超平面(w, b)，超平面(w, b)与样本(xi, yi)之间的几何间隔定义为：
几何间隔与功能间隔之间的关系是：
SVM模型由优化问题、优化算法和分类三部分组成。
当数据集是线性可分的时，支持向量是距离超平面最近的样本。此时，SVM的优化问题可以表示为：
当数据集不是线性可分的时，一些训练集中的样本不满足功能间隔大于等于1的条件。为了解决这个问题，为每个样本(xi, yi)添加一个松弛变量。此时，约束条件为：
同时，为每个松弛变量添加一个代价。目标函数为：
其中C是惩罚系数。当C较大时，对误分类的惩罚会增加，反之则会减少。此时，SVM的优化问题可以表示为：
传统的凸二次规划算法可以解决SVM的优化问题，但当训练集较大时，算法的运行时间会很长。为了解决这个问题，Platt提出了一种高效的算法——序列最小优化(SMO)。
SMO是一种启发式算法。当所有变量满足KKT条件时，优化问题就得到了解决。否则，选择两个变量，固定其他变量，并构建一个包含这两个变量的凸二次规划问题。
在SMO的外循环中，选择违反KKT条件的alpha，即alpha_i。首先，搜索满足条件的样本。如果所有样本都满足条件，则搜索整个数据集。在内循环中，首先搜索使alpha2最大化的alpha1。如果选择的alpha1减少得不够多，首先搜索边界上的样本。如果选择的alpha1减少得足够多，则停止搜索。否则，搜索整个数据集。如果在搜索整个数据集后找到了一个可行的alpha2，将选择一个新的alpha1。
在每次迭代中，通过以下方式更新b：
使用优化后的参数进行预测，预测结果由下式给出：
对于测试集中的每个样本i，使用核变换将支持向量与测试数据进行转换，然后计算概率。如果概率大于0，则预测结果为1，否则为-1。
SVM是一种比之前介绍的算法更复杂的算法。本文简化了搜索过程，使其更容易理解。最后，让将SVM与Sklearn中的SVM进行比较，检测性能如下所示：
检测性能略逊于Sklearn的SVM，这是因为SVM中的SMO比Sklearn的SVM中的SMO更简单。
def kernelTransformation(self, data, sample, kernel):
sample_num, feature_dim = np.shape(data)
K = np.zeros([sample_num])
if kernel == "linear":
K = np.dot(data, sample.T)
elif kernel == "poly":
K = (np.dot(data, sample.T) + self.c) ** self.n
elif kernel == "sigmoid":
K = np.tanh(self.g * np.dot(data, sample.T) + self.c)
elif kernel == "rbf":
for i in range(sample_num):
delta = data[i, :] - sample
K[i] = np.dot(delta, delta.T)
K = np.exp(-self.g * K)
else:
raise NameError('Unrecognized kernel function')
return K
def innerLoop(self, i):
Ei = self.calculateErrors(i)
if self.checkKKT(i):
j, Ej = self.selectAplha2(i, Ei)
old_alpha1 = self.alphas[i]
old_alpha2 = self.alphas[j]
if self.train_label[i] != self.train_label[j]:
L = max(0, old_alpha2 - old_alpha1)
H = min(self.C, self.C + old_alpha2 - old_alpha1)
else:
L = max(0, old_alpha2 + old_alpha1 - self.C)
H = min(self.C, old_alpha2 + old_alpha2)
if L == H:
return 0
eta = K11 + K22 - 2 * K12
K11 = self.K[i, i]
K12 = self.K[i, j]
K21 = self.K[j, i]
K22 = self.K[j, j]
eta = K11 + K22 - 2 * K12
if eta <= 0:
return 0
self.alphas[j] = old_alpha2 + self.train_label[j] * (Ei - Ej) / eta
self.alphas[j] = self.updateAlpha2(self.alphas[j], L, H)
new_alphas2 = self.alphas[j]
self.upadateError(j)
new_alphas1 = old_alpha1 + self.train_label[i] * self.train_label[j] * (old_alpha2 - new_alphas2)
self.alphas[i] = new_alphas1
self.upadateError(i)
b1 = -Ei - self.train_label[i] * K11 * (old_alpha1 - self.alphas[i]) - self.train_label[j] * K21 * (old_alpha2 - self.alphas[j]) + self.b
b2 = -Ej - self.train_label[i] * K12 * (old_alpha1 - self.alphas[i]) - self.train_label[j] * K22 * (old_alpha2 - self.alphas[j]) + self.b
if (self.alphas[i] > 0) and (self.alphas[i] < self.C):
self.b = b1
elif (self.alphas[j] > 0) and (self.alphas[j] < self.C):
self.b = b2
else:
self.b = (b1 + b2) / 2.0
return 1
else:
return 0