SVM参数的两种求解方法 | 第35期

       支持向量机(Support Vector Machine, SVM)曾经是传统机器学习模型中的神话，各种文章都在努力挖掘它的潜力。在数学上具有高度的可解释性是SVM的一大优势，高效的序列最小优化(Sequential Minimal Optimization, SMO)算法为其求解参数提供了极大便利。深度学习兴起之后，使用梯度下降来进行误差反传以求解参数的方法对于SVM是否适用呢？本文就提供SMO和随机梯度下降(Stochastic Gradient Descent, SGD)两种参数求解方法供大家参考。

1. SVM的模型描述

      可以回顾一下感知机解决一个分类问题的思路：对误分类点建立损失函数，通过优化损失函数减少误分类点，直到没有误分类点。这样就存在一个问题，即满足这种要求的分类超平面是有无穷多个的，却无法从这无穷多个解中确定最优的参数解。那么有没有办法定义一种准则来进一步评价超平面的优化程度呢？SVM提供了另一种思路：定义样本点到分类超平面的距离为间隔，使得所有样本点到分类超平面的间隔离最大化所得到的参数就是最优解，而且对于一个线性可分的二分类问题，这个最优解还是唯一的。

       样本点  与分类超平面  的几何间隔  可以由下式表示

要想所有样本点到超平面的几何间隔最大，可以使用以下优化方程进行描述

应当满足的约束条件如下：

由于几何间隔 与函数间隔 具有一个比例关系 ，则以上优化方程可以描述为

函数间隔应当满足的约束条件如下：

       由于在这个优化问题中是一个常数，我们可以假定其大小为单位 。同时，优化  与优化  是等价的，因此，以上优化方程又可以转换为如下形式：

       到此，就可以使用拉格朗日乘数法构建一个新的便于求解的优化问题。由于新的优化问题求解起来仍然困难，所以还需要利用对偶原理构造当前优化问题的对偶问题，然后通过求解对偶问题来获得当前优化问题的解。

       从以上优化问题的描述，我们可以看出，只有在超平面  上的样本点才是对优化有效的点，这些点也被称作“支持向量(Support Vectors)”。对偶问题的优化实质上就是找出这些“支持向量“，从而逆向求解出参数 。除此之外，还有另一种求解思路，即直接从损失函数优化的角度解决。下面就对这两种求解方式的软件求解和结果进行说明。

2. 使用SMO算法优化

       一种传统的求解算法是序列最小优化(Sequential Minimal Optimization, SMO)，该算法由libsvm开源代码库实现。scipy模块提供的支持向量分类(Support Vector Classification, SVC)正是通过调用libsvm的求解器来实现的。在机器学习中，我们认为损失函数中的  这一项是一种正则(Regularization)，因为该项会对复杂的参数配置进行惩罚，从而获得相对简单的参数解。在scipy的SVC中，输入参数参数 C 即是以的方式作用于正则项 ，通过调节 C 的大小来控制参数配置的复杂程度。以下展示在不同的惩罚因子 C 之下的两种结果。

       从两种不同惩罚因子下的分类直线可以看出，在 C 值比较小，也就是惩罚作用比较大时，优化器会在效果和参数复杂度之间进行折中，最终选择了一种对误分类样本存在容忍，但是泛化能力更强的一种参数配置。而在 C 值较大，也就是惩罚作用较弱时，优化器试图寻找一个误分类最少的参数配置，但是最终表现出现的泛化能力却比较差。在求解SVM时，我们常常需要需要调节惩罚因子 C 来获得一组满意的模型参数。除此之外，SVC的求解器还默认加上了松弛因子，即对误分类存在一定的容忍性，也就是通常所说的软间隔。在实际使用中，基本不太会使用原理中所描述的硬间隔，而是在这个基础上加上松弛因子。更多SVC输入参数的配置情况可以参考相关手册。

3. 使用SGD算法优化

       除了SMO算法之外，我们还可以从损失函数优化的角度来解决这个问题。现在对于损失函数优化最流行的算法是随机梯度下降(Stochastic Gradient Descent, SGD)。如果我们能够构建出SVM的损失函数，则可以通过一些深度学习通用的软件求解器来进行求解，比如tensorflow或者pytorch等等。

      通过SVM原理的分析，我们可以考虑构建一种hinge损失函数，其数学表示如下：

      该函数表示，正确分类并且置信度大于1的样本点对损失函数贡献为0，而其他样本点则会对损失函数存在影响，从而在优化损失函数的时候有针对地调整。对于这样在开放空间上的参数解，我们通常都会增加一个正则项，以降低最终参数的复杂度。那么最终使用的损失函数可以表示如下

       关于某些操作在个别点存在不可导的情况，软件框架已经进行了一些修正处理，我们不需要关心这些问题。这里展示使用tensorflow2.0中的SGD求解器进行求解，在不同的惩罚因子之下，所得分类直线结果如下：

      从结果图看出，当惩罚作用越强时，优化所得参数的数值越小。在实际使用中需要调节惩罚因子，以使模型在测试集上能够得到一个不错的结果。

       从两个不同的角度来看待同一个问题，就能够得到两种截然不同的解释和求解方法。使用传统的SMO算法能够非常高效的求解，使用SGD算法求解能够与现在通行的深度学习模型相融合。具体的实验代码演示，可以在本文的notebook文件中获取。

【资源分享】

github链接：https://github.com/cnbluegeek/notebook/tree/master

更多编程书籍，请发送关键字“书籍”到【青衣极客】公众号获取下载链接。

添加“cnbluegeek”微信号为好友，获得邀请加入“python交流群”，编程问题迎刃而解。