实现机器学习的循序渐进指南V——支持向量机

阅读量：3527 次

发布时间：2019-05-20

本文共 5735 字，大约阅读时间需要 19 分钟。

可访问，获取本系列完成文章列表。

介绍

支持向量机（SVM）是一种基于特征空间最大边距的分类器。SVM的学习策略是使边际最大，可以转化为凸二次规划问题。在学习SVM算法之前，我先介绍一些术语。

功能边距定义为：对于给定的训练集T和超平面(w,b)，超平面(w,b)和样本(xi, yi)之间的功能边距为：

超平面(w,b)和训练集T之间的功能边距是的最小值

功能边距表示分类结果的置信水平。如果超参数(w,b) 按比例变化，例如，(w,b)变为(2w,2b)。虽然超平面没有改变，但功能边距消耗增加了一倍。因此，我们在w上应用一些禁令来定义超平面，例如规范化||w|| = 1。然后，边界称为几何边距：对于给定的训练集T和超平面(w,b)，超平面(w,b) 和样本(xi, yi)之间的功能边距为：

类似地，超平面(w,b) 和训练集T之间的几何边距是的最小值

现在，我们可以得出功能边距与几何边距之间的关系：

SVM模型

SVM模型由优化问题，优化算法和分类组成。

优化问题

当数据集可线性分离时，支持向量是最接近超平面的样本，如下所示。

对样品H1和H2是之间的支持向量。在H1和H2之间的距离被称为硬边距。然后，SVM的优化问题是：

当数据集不是线性可分时，训练集中的一些样本不满足函数余量大于或等于1的条件。为了解决这个问题，我们为每个样本(xi, yi)添加一个松弛变量。然后，约束是：

同时，为每个松弛变量添加成本。目标函数是：

其中C是惩罚系数。当C规模很大时，对错误分类的惩罚将会增加，然而对错误分类的惩罚将会减少。然后，SVM的优化问题是：

支撑向量位于边距的边界上或边界和超平面之间，如下所示。在这种情况下，边距为软边距。

当数据集不是线性可分的时，它需要应用内核技巧将数据从原始空间转换为特征空间。内核技巧的函数叫做内核函数，定义如下：

其中是从输入空间到特征空间的映射，即

内核技巧的代码如下所示：

def kernelTransformation(self, data, sample, kernel):        sample_num, feature_dim = np.shape(data)        K = np.zeros([sample_num])        if kernel == "linear":  # linear function            K = np.dot(data, sample.T)        elif kernel == "poly":  # polynomial function            K = (np.dot(data, sample.T) + self.c) ** self.n        elif kernel == "sigmoid":  # sigmoid function            K = np.tanh(self.g * np.dot(data, sample.T) + self.c)        elif kernel == "rbf":  # Gaussian function            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

应用内核技巧后，SVM的优化问题是：

其中是拉格朗日因子。

优化算法

用传统的凸二次规划算法求解SVM优化问题是可行的。但是，当训练集很大时，算法将花费很长时间。为了解决这个问题，Platt提出了一种称为顺序最小优化（SMO）的有效算法。

SMO是一种启发式算法。当所有变量都遵循KKT条件时，优化问题就解决了。否则，选择两个变量并修复其他变量，并用两个变量构造凸二次规划问题。问题有两个变量：一个选择违反KKT条件的alpha，另一个选择由约束决定。表示，是变量，修复。因此，有如下方法计算：

如果确定，则相应地确定。在SMO的每次迭代中，更新两个变量直到问题解决。然后，SVM的优化问题是：

当只有两个变量时，它是一个简单的二次规划问题，如下所示：

因为约束是：

当，

当，因为，。

优化值如下：

其中L和H是对角线的下限和上限，其计算公式为：

未切割的优化值如下：

其中E 1和E 2是预测值g(x)和实际值之间的差值。g(x)定义为：

到目前为止，我们为获得可行的解决办法：

SMO中有两个循环，即外循环和内循环。

在外部循环中，选择违反KKT条件的alpha，即

首先，按照搜索样本。如果所有样本都遵循该条件，则搜索整个数据集。

在内部循环，先搜索，这使得最大。如果所选择的值没有减少，请首先在边距边界上搜索样本。如果选择的值减少，请停止搜索。否则，搜索整个数据集。如果我们在搜索整个数据集后找到可行的，我们将选择一个新的。

在每次迭代中，我们通过如下算式更新b：

为方便起见，我们必须存储的值，其计算方法如下：

搜索和更新代码如下所示：

def innerLoop(self, i):        Ei = self.calculateErrors(i)        if self.checkKKT(i):            j, Ej = self.selectAplha2(i, Ei)          # select alpha2 according to alpha1            # copy alpha1 and alpha2            old_alpha1 = self.alphas[i]            old_alpha2 = self.alphas[j]            # determine the range of alpha2 L and H      in page of 126            # if y1 != y2    L = max(0, old_alpha2 - old_alpha1),                              H = min(C, C + old_alpha2 - old_alpha1)            # if y1 == y2    L = max(0, old_alpha2 + old_alpha1 - C),                              H = min(C, old_alpha2 + old_alpha1)            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:                # print("L == H")                return 0            # calculate eta in page of 127 Eq.(7.107)            # eta = K11 + K22 - 2K12            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:                # print("eta <= 0")                return 0            # update alpha2 and its error in page of 127 Eq.(7.106) and Eq.(7.108)            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)            # update the alpha1 and its error in page of 127 Eq.(7.109)            # new_alpha1 = old_alpha1 + y1y2(old_alpha2 - new_alpha2)            new_alphas1 = old_alpha1 + self.train_label[i] *                           self.train_label[j] * (old_alpha2 - new_alphas2)            self.alphas[i] = new_alphas1            self.upadateError(i)            # determine b in page of 130 Eq.(7.115) and Eq.(7.116)            # new_b1 = -E1 - y1K11(new_alpha1 - old_alpha1) -                              y2K21(new_alpha2 - old_alpha2) + old_b            # new_b2 = -E2 - y1K12(new_alpha1 - old_alpha1) -                              y2K22(new_alpha2 - old_alpha2) + old_b            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

分类

我们可以使用优化的参数进行预测，该参数由下式给出：

for i in range(test_num):    kernel_data = self.kernelTransformation(support_vectors, test_data[i, :], self.kernel)    probability[i] = np.dot(kernel_data.T, np.multiply                     (support_vectors_label, support_vectors_alphas)) + self.b    if probability[i] > 0:        prediction[i] = 1    else:        prediction[i] = -1