什么是支持向量机

支持向量机（SVM）是一种二分类模型，它的基础模型时定义在特征空间上的间隔最大的线性分类器。如下图：

简单支持向量机模型

支持向量机当训练模型线性可分时，可以通过硬间隔最大化，学习一个线性的模型，上图就是一个硬间隔最大化的模型。当训练数据近似线性不可分时，使用软间隔支持向量机。当线性不可分时，使用核函数和软间隔最大化来学习。本文主要讲述硬间隔支持向量机的推导过程。

硬间隔支持向量机

对于一个线性可分的数据集 $T = \left\{ (x_{1}, y_{1} ), (x_{2}, y_{2}), …, (x_{n}, y_{n}) \right\}$ ，划分平面有很多，我们需要找到一个最具鲁棒性的平面，即超平面，来划分数据集。什么才是最具鲁棒性，我们将在后面讲解。

首先定义超平面的线性方程,w和b就是需要求解：

$w^TX + b = 0$

i点到超平面的距离几何间隔(即距离)为：

$\gamma_{i} =y_{i}(\frac{ w^TX_{i} +b }{\vert \vert w\vert \vert } )$

对于 $\gamma _i$ 存在最小值，即距离平面最近的点：

$\gamma =\min\gamma_{i}$

这里就要提到上面的最具鲁棒性，需要最具鲁棒性就需要将 $\gamma$ 最大化，简单来说，就是要找到距离超平面最近的点，同时这些点距离超平面的间隔要近可能的大，这些点我们称之为支持向量，也就是我们需要保留的点。我们写成数学公式：

$\max \limits_{W,b} \gamma\\$

$s.t. y_{i}(\frac{w^TX+b}{||w||} ) \geq \gamma, i=1,2,3,…,n\\$

将 $\gamma$ 定义为 $\frac{\hat{\gamma} }{||w||}$ ,于是上面的式子可以写成：

$\max \limits_{w,b} \frac{\hat{\gamma} }{||w||} \\$

$s.t. y_{i}(w^TX+b) \geq \hat{\gamma}, i=1,2,3,…,n\\$

对面上面式子，我们可以用 $\hat{\gamma}$ =1,代替，相对于对数据点进行了等比例缩放，不影响求解的w和b。同时最大化 $\frac{1 }{||w||}$ 和最小化 $\frac{1}{2}||w||^2$ 等价，再次化简：

$\min \limits_{w,b} \frac{1}{2}||w||^2 \\$

$s.t. y_{i}(w^TX+b)-1 \geq 0, i=1,2,3,…,n\\$

这就是最终要求解的最优化问题。

求解方程，对偶问题

对于求解线性可分支持向量机的最优化问题，需要应用到拉格朗日对偶问题(PS.请自行查阅)。

首先构建拉格朗日函数：

$L(w,b,\alpha ) = \frac{1}{2} ||w||^2-\sum_{i=1}^n\alpha_{i}y_i(w^Tx_i+b) +\sum_{i=1}^n\alpha_i\\s.t.\alpha_i\geq 0,i=1,2,3…,n$

根据拉格朗日对偶问题，原始问题的对偶问题就是

$\max \limits_{\alpha}\min\limits_{w,t}L(w,b, \alpha)$

先求解 $\min\limits_{w,t}L(w,b, \alpha)$ ，分别对w和b的偏导为0，可得到：

$w=\sum_{i=1}^n\alpha_iy_ix_i\\0=\sum_{i=1}^n\alpha_iy_i$

将上述式子带入L(w,b, $\alpha$ )中：

$\max\limits_{\alpha}\sum_{I=1}^n\alpha_i-\frac{1}{2} \sum_{i=1}^n\sum_{i=1}^n\alpha_i\alpha_jy_iy_jX_i^TX_j\\s.t. \sum_{i=1}^n\alpha_iy_i=0,\\\alpha_i\geq 0, I =1,2,…,n.$

如何求解 $\alpha$ ，需要用到SMO算法，这个算法比较复杂，简单来说就是选取两个参数 $\alpha_i$ 和 $\alpha_j$ ,固定 $\alpha_i$ 和 $\alpha_j$ 以为的参数,然后求解式子，更新两个参数。最后求出 $\alpha$ ,通过 $\alpha$ 和KKT条件求出w，b求解为某个支持向量带入得到的解：

$w=\sum_{i=1}^n\alpha_iy_iX_i\\b=1-w^TX^j$

KKT条件：

$w-\sum_{i=1}^n\alpha_iy_iX_i=0\\-\sum_{i=1}^n\alpha_iy_i=0\\\alpha_{I}(y_i(w^TX_i+b)-1)=0,i=1,2,…,n\\y_i(wX_i+b)-1\geq 0, i=1,2,…,n\\\alpha_i\geq 0,i=1,2,…,n\\$