???? 『精品学习专栏导航帖』
- ????最适合入门的100个深度学习实战项目????
- ????【PyTorch深度学习项目实战100例目录】项目详解 + 数据集 + 完整源码????
- ????【机器学习入门项目10例目录】项目详解 + 数据集 + 完整源码????
- ????【机器学习项目实战10例目录】项目详解 + 数据集 + 完整源码????
- ????Java经典编程100例????
- ????Python经典编程100例????
- ????蓝桥杯历届真题题目+解析+代码+答案????
- ????【2023王道数据结构目录】课后算法设计题C、C++代码实现完整版大全????
文章目录
2021人工智能领域新星创作者，带你从入门到精通，该博客每天更新，逐渐完善机器学习各个知识体系的文章，帮助大家更高效学习。
一、概述
本篇文章将讲解机器学习中的一个非常强的算法——支持向量机（SVM），一听到它的名字就会感到这个算法非常的厉害，确实是这样，在神经网络还没有发展起来的一段时间，它确实称霸了很久，而且也具有较高的能力。
支持向量机最开始是一个简单的二分类模型，后面不断发展引入了核函数、非线性因子等将其精度变得更加精准，能够适应更加复杂的数据。
它的算法原理就是，假设我们的数据样本分布在二维平面，有两个分类，支持向量机的做法就是要找到一条直线可以将所有的样本进行区分，这里假设线性可分，如果不可分需要引入核函数，之后的文章会进行讲解，本篇侧重讲解线性可分的二分类数据。
我们可以看到上面的图片，存在3条直线可以将我们的样本进行区分，但是我们可以发现A线是最好的，为什么？因为A线的鲁棒性最好，什么是鲁棒性？你可以理解为模型的牛逼程度，如果鲁棒性越强，模型越健壮，抗烦扰能力越强，如果此时有一个新的样本点在靠近C线或者B线的边缘，模型很有可能会将其进行误分类，而A却能很好的进行区分，因为A线对于所有的样本点的距离都很远，误分类的几率很低，这个分类边界有个很响亮的名字叫做最大间隔分类超平面。
这个平面有两条性质：
- 能够将两个类别的数据分到平面两端
- 距离两个类别样本最近的样本最远
其中图中最边缘的两条直线包含了距离分类平面最近的样本，它们被称作支持向量，而我们的目的是要使两条直线之间的距离最大。
这里解释一下，可能很多地方讲的最大化距离不太一样，有的是最大化上面两条直线之间的距离，有的是最大化所有样本到超平面的距离，还有的是最大化所有样本到分类界面的距离当中最小的距离。
其实没有关系，上面只是不同角度理解，不会影响结果的，从不同的角度引出待优化的目标，最终经过转换都是会转化成同一个优化函数的。
二、相关概念
1.超平面
所谓的超平面就是我们的决策边界，能够将我们数据进行区分的一个面，如果在二维是一条直线，三维是一个平面，在高维中可能是别的维度空间的一种形状，所以叫做超平面，总是n-1个维度。
这里假设还是以二维平面进行讲解，假设我们的超平面为 
因为是二分类问题，假设两个分类为
然而这两个式子我们可以将其进行合并，成为 ：
2.优化目标
我们引出优化函数的方式有三种，分别进行讲解
2.1方法一
我们上面说到了为了要使两条直线间的间隔最大，即我们的优化目标为：
第一个式子是我们需要最大化的距离，第二个是需要满足的条件约束，就是要满足将所有样本正确分类的情况下求得使距离最大的w。
因为一般情况下，我们都是算最小化，所以需要将max进行转化，求它的最大值就是求分母的最小值，我们就是要分母最小，这时我们的优化函数就变成了：
我们可以看到从原来的L2范数直接加了平方，其实这是等价的，两个方程通解，加入1/2 的目的就是为了使之后的求导方便，直接消去2。
2.2 方法二
其实支持向量机是一种最大间隔分类器，意思就是要使我们所有样本到超平面的距离的最小值最大化，什么意思？就是每个样本到超平面都会有一个距离，肯定存在一个样本到该平面的距离最小，如果我们使得这个最小距离最大化的化，那么其它样本的距离也是会变大的，我们就是要最小的变大，从而使整体变大，那么我们就会引入一个式子：
这个公式很容易理解，就是每个样本到超平面的距离。
那么我们的优化函数就变成了：
那么根据第二个式子，我们可以得到
2.3 方法三
其实方法三和上面两种差不多，这里就不细致讲解了，感兴趣可以看看李航的统计学习那本书，我就简单说说。
它的原理就是我们同样和方法二要最大化每个样本到超平面的距离，但是服从的条件是我们所有的数据样本到该超平面的数据都大于我们要求的最大距离，就是说它保持所有样本到超平面的距离都大于我们要求的距离，这其实和方法二等价，即最大化最小的距离，方法三也是这样，每个样本距离都大于它，那么就说明我们优化的是所有样本中距离最小的，这里有个不一样的地方，就是引入了函数距离和几何距离，这里就不细讲了。
三、算法流程
整个算法流程为：
- 获取优化目标函数
- 将目标函数与约束条件结合进行拉格朗日乘子法
- 强对偶性，转化求解问题
- 二次规划求解
- 获取最优解
1.获取优化函数
我们需要优化的函数就是上面推导出的，如果单是对第一个式子进行优化很容易求导，梯度下降，但是对于本问题来说，求解第一个式子的时候，会有m个约束条件，显然不能够直接进行计算，所以需要下面的几步进行转化成我们可以求解的目标函数，第一步就是要能不能将整个带有约束条件的函数转化为无约束的呢？肯定是能，这就引出了拉格朗日乘子法。
2.拉格朗日乘子法
我们高数中学过拉格朗日乘法，就是有一个函数
这就引出了松弛变量这个概念， 松弛变量的引入常常是为了便于在更大的可行域内求解。我们可以尝试引入松弛变量将上面的不等式变成等式，具体怎么做？看！另：
引入松弛变量后就变成了：
因为
我们的目标就是要对该式求极值：
这里解释一下为什么
根据第二个式子我们可以知道
1.
如果
2.
因为
所以综上所述，真正起到作用的是
将这两点结合起来，就引出了KKT条件：
其中更新的第二个式子和第三个式子就是根据上面得出的结论得到的。
也就是说对于支持向量满足
所以我们之前求
因为之前求得
所以此时待优化得就是
假设此时我们的
如果
那么此时我们的优化函数又变为了：
又因为L的最大值肯定是
此时优化函数就是：
3.强对偶性
我们上面得到了优化函数，但是求解起来不太方便，所以我们需要用到强对偶的方法，将其换个方式进行求解，针对于强对偶的两个方程是同解的。
这里解释下什么是弱对偶和强对偶。
如果针对一个函数
那么则说明两者为弱对偶关系，怎么理解上面的不等式呢？
从大的里面挑出最小的要大于从小的里面挑出最大的，或者你可以理解为清华里的菜鸡要强于专科里的学霸，这个例子很好理解吧。
那么强对偶就是满足等号成立，即
我们引出这个就是为个将上文获得的优化函数进行对偶转化，所以：
就变成了：
我们就可以优化新的方程式了，对偶的目的是将原来难以求解的问题转化为一个容易求解的问题，同时我们之前说的KKT条件就是强对偶性的充要条件。
这里因为我们的L是凸函数，所以可以直接确定能够进行强对偶。
4.二次规划求解
根据上文，我们最终优化函数是这个，首先将min和max分离，先计算内层min函数，因为是凸函数，所以可以直接进行求导，由于此时
我们可以获得 ：
我们将这两个式子带入到原式当中进行化简，由于是凸函数，所以导数为0的点就是其最小值，我们把w、b的值带入后就可以得到
此时的
我们的优化函数就变成了：
一般我们习惯优化最小值将上式加个符号就变成了：
注意上面的这个条件不能丢，因为该优化函数满足的前提是对b的偏导为0得来的，为什么没有考虑对w的偏导，因为现在的优化函数与w参数没关系，所以不需要，而b的偏导为0的条件是
接下来的问题就是如何求取满足最大值的
这里采用一种算法叫做SMO算法，其核心思想非常简单：每次只优化一个参数，其他参数先固定住，仅求当前这个优化参数的极值。
由于优化函数同时存在两个优化变量，所以需要根据约束条件消去一个。
由于有
其中
对于单变量优化问题我们就可以使用梯度下降或者其它迭代算法进行求解。
5.求解最优解
说了这么这么多，到底怎么获得最终模型的参数和偏置呢？
我们之前对拉格朗日进行求导，获得：
由于我们在第四步，已经通过SMO算法求出了每个样本对应的
那么如果求取
我们之前讲到我们的支持向量是满足
其中（x_k，y_k）对应着支持向量的信息。
此时上式两边同时左乘
因为
又因为为了使我们的模型更加的稳定，鲁棒性更强，所以我们可以求得所有支持向量的均值：
其中
这样我们就求出了模型最优解系数
决策函数为：
其中的
这样我们的支持向量机线性可分分类器就构建成功了，但是这只是针对线性可分的数据有用，如果我们的数据线性不可分，找不到一个超平面进行分割，那么那么我们的模型就会没用，进而引出了核函数和软间隔的概念，如何处理线性不可分数据，下篇文章再讲。
写在最后
一键三连”哦！！！
