SVM 的推导

SVM（Support Vector Machine，支持向量机）是一个线性分类器，是最经典的分类算法，其核心目标就是找到最大间隔超平面。本文记录SVM的推导过程。

概述

SVM就是一个分类器，只是相对于传统的线性分类器，它添加了一个支持向量的概念。

• 考虑一个分类任务

从图片上解释，对于一组数据，SVM在使用直线的同时要求数据点距离这条直线的最小距离最大，也就是说分类器和数据之间要有足够大的“间隔”。这样做的好处是很明显的，越大的“间隔”代表了更大的转圜空间，在得到新的数据之后更容易将其正确分类。 而SVM的工作就是求解这个最大间隔，也就是最优化问题。对于线性可分的数据，可以直接套用线性规划的知识进行推导，但如果数据线性不可分，就需要核函数进行数据升维，进行超平面分类。

目标函数

SVM是一个线性分类器，SVM的目标就是找到最大间隔超平面。

• 定义任意的超平面函数为：

• 二维空间点(x,y)到直线Ax+By+C=0​的距离为：

• 扩展到k维空间后，点X=(x_1,x_2,\dots,x_k)到超平面w^{T} x+b=0​距离为：

• 其中：

• 我们希望这个超平面可以区分不同两类数据特征，这个分类决策函数就是：

• 我们的数据为({{\bf{x}}_i},{y_i}),i \in \{ 1,2, \ldots ,n\},y_i \in \{1,-1\} ，定义点({{\bf{x}}_i},{y_i}) 到超平面的函数距离\hat{\gamma}_{i}：

• 而我们的目标是找到可以最大化数据到点几何距离的超平面，将几何距离用{\gamma}_{i}表示，为：

• 因此优化函数为：

• 根据已有结论可以将优化函数转化为：

事实上函数间隔${\hat \gamma }$并不影响最优化问题的解，假设将w和b成倍的改变为

，那么函数间隔也会相应变成

，因此为简便，我们取

，因此优化函数为最大化

，这等价于最小化

，考虑到求导方便，我们最小化

- 优化函数最终为：

拉格朗日对偶求极值

• 写成拉格朗日优化的格式：

• 拉格朗日方程：

• 原始问题为凸优化问题，我们按照KKT条件求解该问题的对偶问题，即可根据强对偶条件获得原始问题的解
• 对偶问题为：

• 先求最小化极值问题 \mathop {\min }\limits_{{\bf{w}},b} L({\bf{w}},b,{\bf{\alpha }})：

• 解得：

• 带入L({\bf{w}},b,{\bf{\alpha }})得：

• 此时我们需要解决的优化问题是：

• 可以看到通过拉格朗日对偶，我们将原始拉格朗日方程k+1+n个未知数、n个复杂不等式约束条件的优化问题转换为了n个未知数，1个等式约束的问题，当然满足KKT条件是前提
• 对于这个问题，我们有更高效的优化算法，即序列最小优化（SMO）算法。我们通过这个优化算法能得到\bf{α}，再根据\bf{α}，我们就可以求解出\bf{w}和b，进而求得我们最初的目的：找到超平面，即"决策平面"。

参考资料

• https://www.jianshu.com/p/0f8f9d52abcf
• https://www.pianshen.com/article/15821257925/
• https://blog.csdn.net/qq_40778406/article/details/79879434