SVM概述支持向量机（SVM）是一种有监督的分类算法，大部分处理的是也是一个二分类问题。先通过一系列图片来了解SVM的几个概念。上图中的橙色圆点和蓝色圆点分别代表两种标签。如果你想对它们进行分类，你需要做什么？有小伙伴可能会想到上一篇文章中提到的逻辑回归拟合决策边界。这绝对是一个好方法。本文提到的SVM也可以解决这类分类问题；由于都是分类算法，所以可以用一个例子来比较两者的异同。从超平面可以看出，这里给出了两种划分方式。就图中的实线而言，在逻辑回归中可以称为决策边界，在SVM中称为超平面。在上面的例子中，数据点都分布在二维平面上，所以此时的超平面是一条直线。如果给定的数据集是三、四、……、N维的怎么办？此时超平面对应的维度为二、三、……、N-1维。下图显示了数据集是多维时的超平面。最大间隔对于这个例子，可能有多个可以准确分类的超平面，间隔最大（两条虚线之间的距离）的超平面就是SVM要找的最优解。这个最优解对应的两条边虚线所经过的样本点就是“支持向量”，支持向量到超平面的距离称为margin，如下图所示。公式推导出超平面方程。我们用SVM算法建模，最后想从众多超平面中求解出间隔最大的超平面，所以这也是一个优化问题。这里需要了解优化问题的两个基本因素：目标函数：你希望什么指标达到最好。优化对象：要改变哪些因素使目标函数最优。在线性SVM算法中，目标函数是“区间”，优化对象是“超平面”。因此，首先需要推导出“超平面”的方程。二维空间中“超平面”的公式也是直线的方程，如下：这里，将x变为x1，y变为x2的操作就是对其进行向量化。最后整理成：一般向量是列向量，所以这里进行转置，向量和我们设置的直线垂直。只需要假设直线的斜率a是常数，画图可以证明控制的是直线的方向，b控制的是直线的位置，所以需要改和b在直线方程中优化目标函数。区间公式“区间”是图中点到“超平面”的距离。公式如下：其中d表示区间，表示二阶范数（模），即所有元素的平方和平方根。建模的目标是找到最大区间，其中最大区间W=2d，只要W越大，说明模型的分类效果越好，最后就变成了最大化d的问题。约束是针对我们上面构建的分类器的。当我们向分类器输入数据时，它会返回一个类别标签。这里我们先规定蓝色为负样本（-1），红色为正样本（+1）。我们可以得到一组公式。如果超平面能够对图中的样本点进行准确分类，则可以得到如下公式：上式可以归一化为：s.t.意思是“受制于”，即受制于某些条件。我们再回顾一下上面的最大区间方程。求最大区间的思想可以概括为最大化最小点到超平面的几何距离。最小是为了对不同的类别进行准确分类，最大距离是为了得到“最大区间”来优化分类器。公式如下：如果我们希望最优超平面区间的几何距离为，即所有样本点到超平面的几何距离至少为，则下式必成立。这里设置为1，你可以这么想，不管我们怎么设置，等式两边同时除以，b的系数就减少了2倍，但是超平面是不固定，系数可以按相同的比例缩放，可以类比为一个直线方程。固定后，可以得到下面的公式。这里已经做了一些处理，最大化和最小化是等价的。这样做是为了优化时方便推导目标函数，对最优解没有影响。第一个公式是我们的目标函数，第二个公式是这个优化问题中的约束条件。由于是凸函数，所以这个问题是凸优化问题。求解优化问题优化问题的分类优化问题一般可以分为两类：无约束优化问题和约束优化问题，而约束优化问题又可以进一步分为等式约束的优化问题和不等式约束的优化问题。对于无约束优化问题，可以对函数求导然后置零，从候选值中选出最优值并进行验证；如果函数是凸函数，则可以保证是最优解。随机梯度下降和批量梯度下降是无约束优化方法的例子。对于有等式约束的优化问题，常用的方法是用拉格朗日乘数法将其转化为无约束优化问题。具体来说，将约束和函数写成一个函数，称为拉格朗日函数，系数为拉格朗日乘子；每个变量通过拉格朗日函数推导，使其归零，并从候选值中选择最优值并进行验证。对于有不等式约束的优化问题，主要通过KKT条件转化为无约束优化问题。具体来说，通过构造拉格朗日函数，在一定条件下求最优值的必要条件就是KKT条件。A的必要条件是，对于我们构造的优化问题，A可以得出的结论显然是一个具有不等式约束的优化问题。拉格朗日函数的概念就不过多介绍了。下面介绍拉格朗日乘数法。并且对偶问题和KKT条件是通过拉??格朗日乘数法导出的。拉格朗日乘子法拉第乘子法的思想是通过引入拉格朗日乘子问题求解，将具有d个变量和k个约束的优化问题转化为d+k个变量的无约束优化。对这里感兴趣的朋友可以搜索一下老大的博客或者西瓜书上有详细的介绍。真后悔在高数课上没有认真听这部分。上面的优化问题通过引入拉格朗日乘子可以转化为如下形式：需要注意的是，通过拉格朗日函数，我们可以将上面的公式转化为：这里可能有小伙伴不理解，为什么是最大值的最小化拉格朗日函数的取值，下图说明了原因。显然，在那个时候，目标函数取正无穷大是没有意义的，在那个时候，两者是等价的。对偶问题可以利用对偶性将上述原问题转化为对偶问题，如下：这个过程的主要操作是交换min和max位置，两者之间有一个性质，即前者>=后者，就像在高个子里挑个矮的比在矮个子里挑个高的好。默认情况下，两者是弱对偶关系，但在目标函数和约束条件下，是强对偶关系（等价关系）。转化为对偶问题后，我们可以先求取函数对的偏导数，使其等于0。将以上两式带入构造的拉格朗日函数后，可以得到：最后，可以得到最终的求导后的优化问题，如下：KKT条件假设存在这样一个带有不等式约束的优化问题：如果要用KKT条件来处理这个优化问题，需要用拉格朗日乘子法结合不等式约束，等式约束和目标函数合为一个公式，如下：KKT条件是指得到的最优值必须满足以下条件：当原问题与对偶问题具有很强的对称关系时，是这个问题满足KKT条件，所以本文优化问题的条件如下：根据se条件，我们可以得出结论，只有当样本点为支持向量（样本点在虚线上时），它可以取任意值，而其他位置的样本点必须为0。这与logistic不同回归。当逻辑回归拟合决策边界时，所有样本都会产生影响，而SVM主要作用于边界线附近的样本。因为我们设超平面方程为，所以我们得到原优化问题的解为求L时得到的解，对于，求解过程如下：这里需要注意的一点是，设置为支持vector，所以，可以消去。最终得到的最优超平面方程如下：总结介绍了超平面和最大区间的概念。推导二维超平面方程，引入区间公式。导出此优化问题的约束条件。介绍了优化问题的分类和相应的解决方案。对偶问题是由拉格朗日乘数法导出的。在对偶问题的基础上解释KKT条件。博主还是菜鸟，欢迎指出文章中的问题。本文不包含代码，重点介绍公式推导。手写代码比较重要的部分应该是公式推导。只有了解每一步的思路和由来，才能更好地编程。下一篇文章将介绍序列最小化（SMO）算法的简化版，欢迎关注，感谢阅读。关注公众号[奶糖猫]获取每篇文章的源码和数据，欢迎各位小伙伴与博主交流。
