支持向量机(SVM)原理与推导

1. 支持向量机的原理

Support Vector Machine (SVM)是一种二类分类模型。它的基本模型是在特征空间中寻找间隔最大化的分隔超平面的线形分类器。（间隔最大是它有别于感知机），通过该超平面实现对未知样本集的分类。

1. 当训练样本线性可分时，通过硬间隔最大化，学习一个线性分类器，即线性可分支持向量机；
2. 当训练数据近似线性可分时，引入松弛变量，通过软间隔最大化，学习一个线性分类器，即线性支持向量机；
3. 当训练数据线性不可分时，通过使用核技巧及间隔最大化，学习非线性支持向量机。

2. SVM推导

线性分类器是最简单的有效分类器形式，SVM则在线性分类器基础上演化而成。

所谓线性函数，在一维空间中就是一个点，在二维空间中就是一条直线，三维空间就是一个平面，随着维度不断增加，线性函数也不断改变，被叫做超平面。

SVM的目标就是找到图中的超平面，在任意维空间中，超平面可以表示为函数：

$$G(x)=W^TX+b$$

一个样本点到$P(X_i,Y_i)$超平面的几何距离为：

$$\frac{\left|W^TX_i+b\right|}{\left\|{W}\right\|}$$

Note:这里的几何距离是距离而非间隔。

对于正样本$Y_i=1$，意味着该点在超平面正样本一侧：

$$W^TX_i+b>0$$

对于负样本$Y_i =-1$，意味着该点在超平面负样本一侧：

$$W^TX_i+b<0$$

所以可用下述公式表示点到超平面的几何距离：

$$\frac{Y_i(W^TX_i+b)}{\left\|W\right\|}$$

其中，分子部分表示函数间隔。

几何间隔可以表示点到超平面的距离，在进行分类过程中使分类更加准确，需要优化所有样本中到分类超平面几何间隔最小点的间隔值更大，所以对于SVM公式的求解转换为了一个最优化问题：

$$\max_{W,b}[\min_{X_i}\frac{Y_i(W^TX_i+b)}{\left\|W\right\|}]$$

即求解出最优的$W,b$使得到超平面最近的样本几何间隔最大。

对于一个超平面，如果等比例缩放$W,b$的值其公式表示的超平面不变，我们可以假设到超平面距离最小的样本点到超平面的函数间隔都大于1（通过缩放可$W,b$以实现）：

$$Y_i(W^TX_i+b)\ge1$$

由此可以将原最优化问题进行改变为带约束条件的最优化问题，优化目标为：

$$\max_{W,b}\frac{1}{\left\|W\right\|}$$

约束条件为：

$$Y_i(W^TX_i+b)\ge1，i=1,2,3...k$$

为了便于求解，目标函数等价于：

$$\min_{W,b}\frac{1}{2}\left\|w\right\|^2$$

下面便对该式子进行求解。对于没有约束的最优化问题，我们可以采用求导的方式求解出最优解。针对带约束最优化问题，一个比较好的方法是将其转化为没有约束条件的最优化问题，我们将带约束最优化问题泛化为：

$$\min_xf(x)\\\\s.t.\\\\g(x)\le0,i=1,2,3...k\\\\h(x)=0,i=1,2,3...l$$

泛化问题可以等价于求：

$$\min_{x}\max_{\alpha,\beta}f(x)+\sum_{i=1}^k\alpha g_i(x)+\sum_{j=1}^l\beta h_j(x)$$

其中$\alpha$大于零，$\beta$不等于零。若$g(x)$大于零，而$\alpha$也大于零，对于可变$\alpha$项则不存在极大值，关于$\beta$同理，其可正可负不为0，若$h(x)$不能满足等于零，在该项上也不存在极大值，通过max求极值实现了对原有约束条件的保留。

基于此SVM最优化方程转化为：

$$\min_{W,b}\max_{\alpha}\frac{1}{2}\left\|w\right\|^2+\sum_{i=1}^k\alpha_{i}(1-Y_i(W^TX_i+b))\\\\ s.t.\\\\ \alpha_i\gt0,i=1,2,3...k$$

在满足KTT条件的情况下满足拉格朗日对偶性，其等价于优化方程：

$$\max_{\alpha}\min_{W,b}\frac{1}{2}\left\|w\right\|^2+\sum_{i=1}^k\alpha_{i}(1-Y_i(W^TX_i+b))\\\\ s.t.\\\\ \alpha_i\gt0,i=1,2,3...k\\\\ 1-Y_i(W^TX_i+b)\le0,i=1,2,3...k\\\\ \alpha_{i}(1-Y_i(W^TX_i+b))=0,i=1,2,3...k$$

对于该最优化的方程内部进行求导：

$$\frac{\partial L}{\partial W} =W-\sum_{i=1}^k\alpha_{i}Y_iX_i\\\\ \frac{\partial L}{\partial b} =-\sum_{i=1}^k\alpha_{i}Y_i$$

在偏导数为0时取得极值。

$$W= \sum_{i=1}^k\alpha_{i}Y_iX_i\\\\ \sum_{i=1}^k\alpha_{i}Y_i=0$$

将求导后的等式带入原方程可以得到最终关于$\alpha$的最优化方程：

$$\max_{\alpha}\sum_{i=1}^k\alpha_i-\frac{1}{2}\sum_{i=1}^k\alpha_{i}Y_iX_i^T\sum_{j=1}^k\alpha_jY_jX_j\\\\ s.t.\\\\ \alpha_i\gt0,i=1,2,3...k\\\\ 1-Y_i(W^TX_i+b)\le0,i=1,2,3...k\\\\ \alpha_{i}(1-Y_i(W^TX_i+b))=0,i=1,2,3...k\\\\ \sum_{i=1}^k\alpha_iY_i=0$$

求出该式子中各个$\alpha$的值，由于$W,b$与$\alpha$均有等价关系，便可以得到SVM模型的$W,b$参数。上面式子显然无法通过求导得到最优的$\alpha$值，可以使用Sequential Minimal Optimization(SMO)方法去进行求解。