支持向量机推导

    本文记录的目的是方便自己学习和复习，有误之处请谅解，欢迎指出。

   支持向量机（SVM）是算法工程师最耳熟能详的机器学习模型之一，这节对SVM作粗略的推导。

   SVM旨在找到一个超平面使得正负样本的距离该平面的距离最大。如下图所示，通常存在多条可划分正负样本集的超平面，为了区分效果最好，需要找到一条间隔最大化的超平面，在图中，红色超平面的划分效果最好。

       通过直线方程知道，超平面公式为：

超平面

其中，、为超平面参数，为样本值。通过点到直线的距离公式容易得到任意样本到超平面的距离为：

超平面距离公式

    假设有样本集 使用超平面对其正确分类，满足以下式子：

    等同于：

    下图中距离超平面最近的几个样本点使得等式成立，也就是常说的支持向量。通过平行直线之间的距离公式，可知，正负两类之间的距离间隔为：

    如下图：

    SVM目的是最大化样本到超平面的距离，在能够正确分类的情况下，也就是最大化间隔，即最小化。问题转为求极值条件问题：

    拉格朗日方法求极值：

    上式等价于：

    由于上式不容易求出结果，所以通过弱对偶性进行变换：

    证明弱对偶性成立（鸡头凤尾，截图来自视频，相关视频连接见文章底部）：

弱对偶性

    现在两式之间的关系是小于等于，对我们的作用不是很大，我们需要取等于号。为了式子两边相等，需要证明其强对偶性，由于SVM属于凸优化，且满足Slater条件（凸优化 + Slater条件 → 强对偶性），这时我们转化为求下式：

    现在分别对中求偏导等于0得到：

    将上式带入，消去得到：

    即：

    用SMO解出后，求出的值，即可得出模型：

    由于上述过程中证明了强对偶性，因此满足KKT条件，即之间存在一定关系：

    观察发现，KKT条件成立，需要或。如果，则此样本不会参与模型参数的计算，对超平面无影响；如果，则此样本就是超平面上的支持向量。

    这就形成了SVM的一个重要特性——决策超平面的计算仅与支持向量有有关。

    推荐一个非常不错的SVM推导视频：https://www.bilibili.com/video/BV1Hs411w7ci?p=8