Peter教你谈情说AI | 10支持向量机(1)—SVM原型

“谈情说AI” 有段日子没有更新了，今天我们挽起袖子继续新的一节。从今天起我们的学习之旅进入了新的阶段，之所以说是新的阶段，是因为之前讲的几个模型：线性回归、朴素贝叶斯、逻辑回归和决策树等背后的数学推导都算初级难度。今天开始讲AI的经典算法——SVM，经过几天坐地铁时间的学习终于搞清楚了SVM背后的来龙去脉。废话少说，让我们进入 “谈情说AI” 新的旅程——SVM。

线性可分

先举个简单的例子。如下图所示，现在有一个二维平面，平面上有两种不同的数据，分别用圈和叉表示。由于这些数据是线性可分的，所以可以用一条直线将这两类数据分开，这条直线就相当于一个超平面，超平面一边的数据点所对应的y全是红色 ，另一边所对应的y全是蓝色。

这样，两类样本完美地被绿线分隔开。此时，我们说这两类样本在其特征空间里线性可分。

那什么样的超平面是最佳的呢，一个合理的策略是：以最大间隔把两类样本分开的超平面，是最佳超平面！

其实线性可分支持向量机就是：以找出线性可分的样本在特征空间中的最大间隔超平面为学习目的的分类模型。

下面我们看看如何找到最大间隔超平面。

寻找最大间隔超平面

我们可以先找到两个平行的，能够分离正负例的辅助超平面，然后将它们分别推向正负例两侧，使得它们之间的距离尽可能大，一直到有至少一个正样本或者负样本通过对应的辅助超平面为止——推到无法再推，再推就“过界”为止。

下图是二维坐标系里，两个辅助超平面（蓝、红两条直线）的例子：

这两个超平面互相平行，它们范围内的区域称为“间隔”，最大间隔超平面位于这两个辅助超平面正中的位置与它们平行的超平面——图中绿线为最大间隔超平面。

下面我们推导下红蓝绿这三条直线的式子：

故这个超平面由其法向量 w 和截距 b 确定，可用 (w, b) 表示。

这些样本在特征空间是线性可分的，因此我们可以找到两个将正负两类样本分离到距离尽可能大的超平面，它们分别是：

和

通过几何不难得到这两个超平面之间的距离是

，因此要使两平面间的距离最大，我们需要最小化

。

根据定义，我们知道样本数据需满足下列两个条件之一：

将上面两个式子合并一下就是

。也就是说，我们要最小化

是有约束条件的，条件就是：

因此，求最大分割超平面问题其实是一个约束条件下的最优化问题，我们要的是：

为了后面好算，我们变换一下约束形式：

这就是支持向量机的学习目标，其中

是目标函数，我们要对它进行最优化。

对这样一个最优化问题，需要通过优化算法来求解。关于优化算法，我们之前学习过梯度下降法，简单直接，是不是可以应用到这里呢？可惜不行。因为，梯度下降是优化没有约束条件问题的算法。

这里我们遇到的，是一个有约束条件的最优化问题。

那么该如何求解呢？在此我们要学习一个新的算法：拉个朗日乘子法。

下一节我们来看下拉个朗日乘子法。