统计学习方法|SVM

01 起

在统计学习方法这个板块中，我们学习了多个分类算法，比如逻辑斯蒂回归，在逻辑斯蒂回归模型中，我们对数据集有预先的假设——数据集满足逻辑斯蒂分布。

今天我们学习另外一种分类模型，这种分类模型对数据集没有做任何假设，它的适用性更广，当我们尚不明确数据分布特性时，使用这个模型分类可能更合适。

这个模型叫SVM，中文名叫支持向量机，是一种经典而普适的分类模型。

02 SVM简介&基本概念

2.1 分类原理

支持向量机是一种分类模型，它的输出结果是一个分离超平面，这让我们想到了“感知机”这个古老的模型。

我们回忆一下，感知机模型输出结果也是一个分离超平面，不过这个分离超平面有无数个，因为感知机只要求把数据集分开就好。我们再来看看支持向量机，它的输出也是一个分离超平面，但只有一个平面能给满足SVM模型，为什么呢？

因为SVM的分类原理是，找到与两类数据间隔均最大的分离超平面，通常，满足这种条件的分离超平面只有一个。

2.2 类型

我们再来看看支持向量机分类，

1. 线性可分支持向量机——求解策略，硬间隔最大化
2. 线性支持向量机——求解策略，软间隔最大化
3. 非线性支持向量机——求解策略，核技巧+软间隔最大化

2.3 间隔

刚才我们提到了SVM的求解策略——间隔最大化。那么间隔是指什么呢？

• 函数间隔

但是呢，函数间隔有个问题，

于是产生了几何间隔这个概念。

• 几何间隔

间隔的定义如上，它想表达什么意义呢？

1. 正确性：yi与()符号相同，则说明分类正确
2. 确信度：yi()值的大小，说明某点与分离超平面的间隔越大，分类越正确

2.4 支持向量

支持向量机之所以叫支持向量机，是因为其分离超平面位置的是由几个在分界平面上的样本点决定的，这几个样本点就叫“支持向量”，我们来看看图：

图中被圈出来的点就是支持向量，中间的实线是分离超平面，可以看到，分离超平面完全由支持向量决定。

介绍了以上基本概念后，我们来学习针对三种类型的数据集的SVM。

03 线性可分数据集

3.1 定义及学习策略

定义如下：

学习策略：硬间隔最大化

SVM间隔边界的距离是2/||w||，于是要使该距离最大，也就是最小化||w||，于是问题转化为最小化||w||**2 （平方是因为w的L2范数是根号下的，平方可以去除根号，方便计算）

3.2 算法

• 原始问题算法：

原始问题的目标函数比较简单，就是最小化参数w的L2范数，如果不考虑约束条件，很好求解，直接对w求导=0即可。

但是呢，原始问题的约束条件让求解比较麻烦，于是拉格朗日大神来了，我们使用拉格朗日对偶性，将原始问题转化为对偶问题，如下。

• 对偶问题算法：
  

可以看到，在对偶问题中，我们利用拉格朗日对偶性，将原始问题的约束条件放入了对偶问题的目标函数中，使整个问题更好求解。

• 原始问题与对偶问题解的转换：

我们的目标是求分离超平面wx+b=0，即求w和b，对偶问题中我们求出了alpha，于是可以使用上述公式计算得到w和b，其中，只有支持向量的alpha>0

04 线性支持向量机

线性可分的数据其实很少，对于线性不可分数据集的分类任务，线性可分支持向量机难以胜任>>线性支持向量机。

4.1 定义及学习策略

定义如下：

学习策略：软间隔最大化

对每个样本点引入一个松弛变量ebsilong_i

4.2 算法

这里我们直接介绍对偶算法： 我来看看线性支持向量机的支持向量在哪里：

软间隔支持向量的位置

• 位于间隔边界上(ebsilong=0)
• 位于分离超平面(ebsilong=1)
• 位于间隔边界和分离超平面之间(0<ebsilong<1)
• 位于分离超平面误分类一侧(ebsilong>1)

4.3 另一种解释

线性支持向量机学习的另一种解释：我们从目标函数这个角度来看一下，

05 非线性支持向量机

5.1 定义及学习策略

在实际数据集中，有的数据是非线性的，这时候还可以使用支持向量机么？

当然可以！

我们可以这样做：现在，大侠没有棍可以很好帮他分开两种球了，现在怎么办呢？当然像所有武侠片中一样大侠桌子一拍，球飞到空中。然后，凭借大侠的轻功，大侠抓起一张纸，插到了两种球的中间。(这句话译自一篇博文)

就像这张图：

这就是核技巧，篇幅限制，这里对核技巧就不展开讲解了，我们只要知道对于非线性数据集，可以使用核技巧将数据集转化为高维空间的线性数据集，从而利用软间隔最大化求解它。

5.2 算法

06 总结

以上就是支持向量机的简单介绍以及对于三种类型的数据集，如何使用SVM的算法。

这里我们提出一个问题：当数据量很大时，以上提出的算法求解复杂度呈指数上升，算法会变得十分低效，该怎么办呢？

提示是，在对偶问题中，每次只求解优化两个alpha的值，然后遍历求解的方法与一次求解所有alpha的方法得到的结果是完全一致的。

其实这就是SMO(序列最小优化算法)的原理，下期文章我会简单介绍SMO算法原理，然后自己写一个SMO代码来实现，敬请期待！！