支持向量机SVM详解

支持向量机

支持向量机（SVM）算法在分类问题中有着很重要的地位，其主要思想是最大化两类之间的间隔。按照数据集的特点：
1：线性可分问题，如之前的感知机算法处理的问题
2：线性可分，只有一点点错误点，如感知机算法发展出来的pocket算法处理的问题
3：非线性问题，完全不可分，如在感知机问题发展出来的多层感知机和深度学习
针对以上三种情况SVM有以下三种处理方式：
1：hard-margin SVM
2：soft-margin SVM
3：kernel Method

Hard-margin SVM

支持向量机也是一种硬分类模型，在之前的感知机模型中，我们在线性模型的基础上叠加了符号函数，在几个直观上，可以看到，如果两类分的很开的话，那么其实会存在无穷多条线可以将两类分隔开。在SVM中，我们引入最大化间隔这个概念，间隔指的是数据和之间的距离的最小值，因此最大化这个值反映了我们模型倾向。
分割的超平面可以写为：

那么最大化间隔（约束为分类任务的要求）：

对于这个约束
不妨固定
这是由于分开两类的超平面的系数经过比例缩放不会改变这个平面，这个相当于给超平面的系数作出了约束。化简之后的式子可以表示为：

这就是一个包含N个约束的凸优化问题，有很多求解这种问题的软件。
但是，如果样本数量或者维度非常高，直接求解困难甚至不可解，于是需要对这个问题进一步处理。引入Lagrange函数：

原有问题就等价于：

我们交换最小和最大值的符号得到对偶问题：

由于不等式约束是仿射函数，对偶问题和原问题等价：

将上面两个参数带入：

因此，对偶问题就是：

从KKT条件得到超平面的参数：
原问题和对偶问题满足强对偶关系的充要条件为其满足KKT条件：

根据这个条件就得到了对应的最佳参数：

于是这个超平面的参数w就是数据点的线性组合，最终的参数值就是部分满足
向量的线性组合（互补松弛条件给出），这些向量也称为支持向量。