支持向量机（SVM）入门理解与推导

1. 简介

支持向量机（support vector machines）是一种二分类模型，它的目的是寻找一个超平面来对样本进行分割，分割的原则是间隔最大化，最终转化为一个凸二次规划问题来求解。由简至繁的模型包括：

当训练样本线性可分时，通过硬间隔最大化，学习一个线性可分支持向量机；
当训练样本近似线性可分时，通过软间隔最大化，学习一个线性支持向量机；
当训练样本线性不可分时，通过核技巧和软间隔最大化，学习一个非线性支持向量机；

2. 线性可分支持向量机

2.1 间隔最大化和支持向量

如果一个线性函数能够将样本分开，称这些数据样本是线性可分的。那么什么是线性函数呢？其实很简单，在二维空间中就是一条直线，在三维空间中就是一个平面，以此类推，如果不考虑空间维数，这样的线性函数统称为超平面。我们看一个简单的二维空间的例子，空心圆代表正类，实心圆代表负类，样本是线性可分的，但是很显然不只有这一条直线可以将样本分开，而是有无数条，我们所说的线性可分支持向量机就对应着能将数据正确划分并且间隔最大的直线。
支持向量机（SVM）入门理解与推导
下面我们开始计算间隔，其实间隔就等于两个异类支持向量的差在 w 上的投影，即：

推出：

代入公式（4）中可以得到：
至此，我们求得了间隔，SVM的思想是使得间隔最大化，也就是

公式（7）即为支持向量机的基本型。

2.2 对偶问题

公式（7）本身是一个凸二次规划问题，可以使用现有的优化计算包来计算，但我们选择更为高效的方法。对公式（7）使用拉格朗日乘子法得到其对偶问题，该问题的拉格朗日函数可以写为：
支持向量机（SVM）入门理解与推导
公式（8）分别对 w 和 b求偏导：

令其分别为0，可以得到：

将公式（9）（10）代入公式（8），可得：

此时，原问题就转化为以下仅关于 a 的问题：

解出 $\alpha $ 之后，根据公式（9）可以求得 w ，进而求得 b，可以得到模型：
支持向量机（SVM）入门理解与推导
上述过程的KKT条件为：

3. 非线性支持向量机和核函数

对于非线性问题，线性可分支持向量机并不能有效解决，要使用非线性模型才能很好地分类。先看一个例子，如下图，很显然使用直线并不能将两类样本分开，但是可以使用一条椭圆曲线（非线性模型）将它们分开。非线性问题往往不好求解，所以希望能用解线性分类问题的方法求解，因此可以采用非线性变换，将非线性问题变换成线性问题。
支持向量机（SVM）入门理解与推导

于是有最小化函数：

其对偶问题为：

求解后得到：

此外，核函数也可以通过组合得到，在此不再赘述。