深度讲解支持向量机背后的数学思想

在支持向量机（support vector machine，SVM）算法中，有诸多数学思想。学习SVM是一个非常好的实践数学思想的过程，为我们以后创新解决问题思路提供了启发。

在卷积神经网络兴起之前，在机器学习界一直是非常受追捧的算法，不光是因为其有良好的泛化能力、很高的准确度，更是因为其完备的数学理论依据以及诸多较难理解的数学知识。这两点让人们觉得SVM是一个很精妙很酷的算法！所以在实际应用也非常多。

本文从头到尾阐述SVM从建模到求解过程中的数学思想，我们发觉SVM建模的出发点是非常简单的，通过了解其数学思想，对其一步一步为什么、怎么应用各种数学思想方法，变得越来越复杂的整个过程就有了非常清晰的了解。更重要的，我们对科学建模过程也有了充分了解，便于我们以后进行各种创新设计。SVM主要概括为：

• 理解SVM问题是通过简单的直觉和严谨的数学来约束最小化问题。
• SVM问题应用拉格朗日方法来解决约束优化问题。
• 为了找到不同类别点之间最宽的间隔，最大化问题仅取决于点积。

其背后的数学思想概括有下边要讲的四点，本文详细分析之。

几何思想：简单直觉的理解世界

SVM出发点是非常直觉的，那就是把二分类问题放到几何上理解。

SVM最初的问题是：把二分类问题转化为在二维空间中，找到最佳分隔线，如下图所示：

这个分隔线怎么找才最好，最直觉的思想就是"不偏不倚"，与两类样本点的边界保持相等的最远的距离。

这是一个非常直觉、非常朴素的直观感觉！作为一个比较难理解的算法，SVM发点竟然如何简单！这也给我们一个启发，那就是对于现实世界问题建模，刚开始一定要追求极简原则、直觉原则，为什么呢？因为越是简单，越容易检验正确与否，类似于几何中公理一样。

接下来，我们继续演绎，那就是在几何上，怎么表达"不偏不倚"？很显然，再一次直觉感知，那就是最大化间隔。

我们希望找到这样一个决策边界，这个边界距离两类数据点最远。更进一步的，是距离两类数据点的边界最远，所以定义最接近边界的数据点定义为支持向量。最后，我们的目标变为找到这样一个直线（多维叫超平面），它与支持向量有最大的间隔。

抽象思维：由实际问题建模的数学思想

抽象思维，是由实际问题抽象为数学模型的非常重要的思想。

刚才我们已经把问题用几何说清楚了，接下来，仍然是用几何求解。为了表达这个距离（间隔），需要把现实世界中的这类问题抽象共性表达。所以我们进行若干设定：

• 设这个平面用g(x)=0来表示，其法向量用w表示
• 点与平面实际距离为r
• 点与平面的距离可以用g(x)的绝对值来度量（称为函数间隔）

如上图所示，点x可以表示为：

这是g(x)为正的情况，点x在平面一侧。

我们的目标就是求r最大化。函数间隔的取值并不影响最优解，假设将w,b按比例扩大a倍，函数间隔变为ag(x)，分母也变为原来的a 倍，上下抵消。对目标函数没有影响 ，因此为优化方便我们设函数间隔为 1。

也意味着，支持向量边界被设定为g(x)=±1，即间隔面。最后，间隔变为：

同时我们的约束是：

最后抽象后的数学问题变为：

惩罚函数（因子）：提升系统的鲁棒容错能力

惩罚函数亦称处罚函数，是一类制约函数。对于约束非线性规划它的制约函数称为惩罚函数，系数称为惩罚因子 。是数学中非常重要的一种处理方法。

引入惩罚因子C的SVM（软间隔支持向量机）的目标函数为：

这个做法非常精妙，体现非常精妙神奇的数学思维。

为什么要引入C？要理解参数C的意义，先要理解ξ的意义。如下图所示，

当样本点越过本类样本点的边界时，

时，点在分离超平面与本侧间隔面之间;

时，点在超平面上；

时，点在分离超平面与另一侧间隔面之间；

时，点在分离超平面误分一侧。

所以，设置C就是为了对这些在边界地带误分的点，而这些点在现实世界是天然存在的，如果对于他们不进行容错（对应硬间隔支持向量机），那么我们是无论如何也不能把样本分开的。而引入惩罚因子，目的就是，对这类误分的样本进行容错，相当于把点拉到正确一侧。

具体分析之，我们要最小化目标函数：

①当C很大时，ξ趋近于0，结合上图和上边的解释，分离超平面被边界的点朝相反类别一侧挤压，换句话说：惩罚很大，容忍度很低，错分较少，对样本的拟合性较好，但容易过拟合；

②C的变小时，ξ开始变大，结合上图和上边的解释，处于两个间隔面之间的点（甚至另一侧）变多，错分较多，对样本的拟合性下降。

所以要权衡折中。

转化思想：转化为容易解决的问题

转化思想，是数学中最为灵魂、最为常用的思想。

这里主要讲的对于SVM目标函数求解用到了拉格朗日对偶与KKT条件，如果不太了解拉格朗日对偶与KKT条件，可以参考本头条号文章《深入讲解强弱对偶理论与KKT条件》视频《形象直观理解KKT条件》。

我们已经得到SVM的目标函数（以硬间隔为例）：

对于求解不等式约束的问题，我们转化为求其对偶问题，这个对应的对偶问题是：

其中

最终我们得到目标函数如下，由我个变量变为只有一个变量：

核思想：升维的同时避免维度灾难带来的复杂计算

目标函数中有点积：

不仅如此，因为决策函数还取决于支持向量和新样本的点积：

这意味着如果我们使用将数据映射到更高维度空间的映射函数，那么最大化和决策函数取决于不同样本的映射函数的点积，那么我们只需要知道K而不是映射函数本身。这就是核函数，它降低了寻找映射函数的复杂性。核函数定义了转换空间中的内积。

对于核函数的透彻理解，请参考本头条号另一文章《透彻形象理解核函数》，本文仅以高斯核函数作为举例，推导其映射函数：

其映射函数为：

可以映射到无穷维。看核函数，注意到它取决于两点之间的欧几里德距离，即如果两个矢量更接近则该项很小。由于方差总是正的，这意味着对于更接近的向量，其值更大。当伽马参数高时，核函数的值将更小，即使对于非常靠近两个样本，这可能导致复杂的决策边界或引起过度拟合。如下图所示：