Support Vector Machine 1

SVM 是机器学习中的一种经典方法，除了硬间隔 SVM 之外，还包括软间隔 SVM，核技巧等 SVM 的变种，本文主要介绍硬间隔 SVM的推导。

假设两类样本点是可以被准确分开的，那么则可以使用硬间隔 SVM 来进行分类，假设分隔的超平面方程为$w\cdot x+b=0$，则每个样本点$x_{i}$到该超平面的距离为$|w\cdot x_{i}+b|$，如果设定与超平面之间的距离为正的点为正分类，即$y_{i}=+1$，相反负距离的点为负分类，即$y_{i}=-1$，那么可以将样本点到分离超平面的距离表示为$\hat{\gamma}_{i}=y_{i}(w\cdot x_{i}+b)$，这称为样本点到分离超平面之间的函数距离。

令$\hat{\gamma}=min(\hat{\gamma}_{i})$，即为最小函数距离。需要注意到，函数距离$\hat{\gamma}_{i}=y_{i}(w\cdot x_{i}+b)$在$w$和$b$同时增大某个比例倍数时，函数间隔会增大但是超平面不会发生改变，此时便需要将超平面的$w$进行约束，比如令$||w||=1$，我们可以重新定义距离为$\gamma_{i}=y_{i}(\frac{w}{||w||}\cdot x_{i}+\frac{b}{||w||})$，称之为几何距离，令$\gamma=min(\gamma_{i})$，即可以得到$\gamma=\frac{\hat\gamma}{||w||}$。

那么最大化分隔距离的优化问题即可表示如下：

$$\begin{align*} &max_{w,b}\quad \gamma \\ &s.t.\quad y_{i}(\frac{w}{||w||}\cdot x_{i}+\frac{b}{||w||})\ge\gamma，i=1,2...n \end{align*}$$

即

$$\begin{align*} &max_{w,b}\quad \frac{\hat\gamma}{||w||} \\ &s.t.\quad y_{i}(w\cdot x_{i}+b)\ge\hat \gamma，i=1,2...n \end{align*}$$

注意上式中，函数间隔$\hat\gamma$的取值并不会影响最优化问题的解，不妨假设$\hat\gamma=1$，并且注意到最大化$\frac{1}{||w||}$与最小化$\frac{1}{2}||w||^{2}$等价，那么上述问题即可以等价为：

$$\begin{align*} &min_{w,b}\quad \frac{1}{2}||w||^{2}\\ &s.t.\quad y_{i}(w\cdot x_{i}+b)-1\ge0 \end{align*}$$

上述问题即为一个不等式约束的最优化问题，可以利用拉格朗日乘子法与 KKT 条件来求解，令$\alpha=[\alpha_{1},\alpha_{2},\alpha_{3},...,\alpha_{n}]^{T}$，首先构造拉格朗日函数为：$L(w,b,\alpha)=\frac{1}{2}||w||^{2}-\sum_{i}\alpha_{i}y_{i}(w\cdot x_{i}+b)+\sum_{i}\alpha_{i}$

假设$W^{*},b^{*},\alpha^{*}$是优化问题的最优解，那么根据 KKT 条件，$W^{*},b^{*},\alpha^{*}$一定满足以下方程：

$$\begin{align} &\nabla_{w}L(w^{*},b^{*},\alpha^{*})=w^{*}-\sum_{i=1}^{N}\alpha^{*}_{i}y_{i}x_{i}=0\tag{1}\\ &\nabla_{b}L(w^{*},b^{*},\alpha^{*})=-\sum_{i=1}^{N}\alpha_{i}^{*}y_{i}=0\tag{2}\\ &\alpha_{i}^{*}(y_{i}(w^{*}\cdot x_{i}+b^{*})-1)=0\tag{3}\\ &y_{i}(w^{*}\cdot x_{i}+b^{*})-1\ge 0\tag{4}\\ &\alpha_{i}^{*}\ge0\tag{5} \end{align}$$

KKT 条件主要包括几个方面的内容：1.拉格朗日函数对于原始优化变量的梯度为 0，如（1）和（2）2.拉格朗日乘子和不等式约束的左式（化为标准形式）的乘积全为 0，如（3）3.原问题的约束条件，如（4）4.拉格朗日乘子非负，如（5）

由（1）和（2）可以得到：

$$w^{*}=\sum_{i}^{N}\alpha_{i}^{*}y_{i}x_{i}\\ \sum_{i}^{N}\alpha_{i}^{*}y_{i}=0$$

根据拉格朗日对偶性，原问题可以化为：

$$min_{w,b}\ max_{\alpha}\ \frac{1}{2}||w||^{2}-\sum_{i}\alpha_{i}y_{i}(w\cdot x_{i}+b)+\sum_{i}\alpha_{i},\alpha_{i}\ge 0$$

即

$$max_{\alpha}\ min_{w,b}\ \frac{1}{2}||w||^{2}-\sum_{i}\alpha_{i}y_{i}(w\cdot x_{i}+b)+\sum_{i}\alpha_{i},\alpha_{i}\ge 0$$

其中$min_{w,b}\ \frac{1}{2}||w||^{2}-\sum_{i}\alpha_{i}y_{i}(w\cdot x_{i}+b)+\sum_{i}\alpha_{i}$问题的最优解由 KKT 条件可以得到为$w^{*}=\sum_{i}^{N}\alpha_{i}^{*}y_{i}x_{i}$，并且有$\sum_{i}^{N}\alpha_{i}^{*}y_{i}=0$，代入上式即可将原问题化为：

$$\begin{align*} max_{\alpha}\quad&-\frac{1}{2}\sum_{i}\sum_{j}\alpha_{i}\alpha_{j}y_{i}y_{j}(x_{i}\cdot x_{j})+\sum_{i}\alpha_{i}\\ s.t.\quad&\alpha_{i}\ge 0 \end{align*}$$

在求解了$\alpha^{*}$之后，即可根据$w^{*}=\sum_{i}^{N}\alpha_{i}^{*}y_{i}x_{i}$求得$w^{*}$，由于分离超平面的参数是$w^{*},b^{*}$决定的，而分离超平面由$\alpha_{i}\neq0$的$\alpha_{i},x_{i},y_{i}$决定的，因此再选取任意$j$使得$\alpha_{j}\neq0$，得到$b^{*}=y_{j}-w^{*}\cdot x_{j}$，这样便可以得到分离超平面$w^{*}\cdot x+b^{*}=0$。

对于上面的求解$\alpha^{*}$的优化问题，我们在下文将会介绍 SMO 算法来求解