支持向量机（二）——线性可分支持向量机求解

〇、说明

支持向量机(Support Vector Machine,SVM)是监督学习中非常经典的算法。笔者主要参考学习的是李航老师《统计学习方法（第二版）》[1]和周志华老师的西瓜书《机器学习》[2]。

如有错误疏漏，烦请指正。如要转载，请联系笔者，hpfhepf@gmail.com。

一、问题描述

如此系列笔记的上一篇《支持向量机（一）——线性可分支持向量机导出》[3]所述，给定线性可分训练数据集 $T=\{(x_{1},y_{1}),(x_{2},y_{2}),…(x_{N},y_{N})\}$ ，其中 $x_{i}\in \mathcal X = \mathbb{R}^n$ ， $y_{i}\in \mathcal{Y}=\{+1,-1\}$ ， $i=1,2,\cdot \cdot \cdot ,N$ 。

求解如下优化问题的最优解

优化问题一：

$\begin{split}&\mathop{min}\limits_{w,b} \quad & \frac{1}{2} ||w||^2 \\&s.t. & y_{i}(w\cdot x_{i}+b) \geq 1,\ \ i=1,2,\dots,N\end{split} \tag{1}$

可得最大间隔分离超平面

$w^*\cdot x+b^* =0 \tag{2}$

和对应的分类决策函数

$f(x)=sign(w^* \cdot x +b^*) \tag{3}$

二、朗格朗日对偶算法

优化问题一（式 $(1)$ ）是一个凸二次规划问题，可以通过求解拉格朗日对偶问题来求解。关于凸优化内容可以参见笔者相关笔记。

构建拉格朗日函数

$L(w,b; \alpha )=\frac{1}{2}||w||^2+\sum_{i=1}^N\alpha_{i}(1-y_{i}(w\cdot x_{i}+b)) \tag{4}$

其中， $\alpha =(\alpha_{1},\alpha_{2},\dots,\alpha_{N})^T,\ \alpha_{i} \geq 0$ 为拉格朗日乘子组成的向量。

原问题是凸优化问题，则拉格朗日强对偶性成立，所以如下优化问题和原优化问题等价，具体请参见[4]

优化问题二：

$\mathop{max}\limits_{\alpha} \ \mathop{min}\limits_{w,b} \ L(w,b;\alpha) \tag{5}$

也就是说，优化问题二的最优解，即是优化问题一的最优解。

三、求解拉格朗日对偶问题

第一步，先求解 $\mathop{min}\limits_{w,b} \ L(w,b;\alpha)$

对拉格朗日函数分别对 $w$ 和 $b$ 求偏导，并令其等于0。

$\frac{\partial}{\partial w} L(w,b;\alpha)=w-\sum_{i=1}^N \alpha_{i}y_{i}x_{i}=0 \tag{6}$

$\frac{\partial}{\partial b} L(w,b;\alpha)=-\sum_{i=1}^N \alpha_{i}y_{i}=0 \tag{7}$

可得

$w=\sum_{i=1}^N \alpha_{i}y_{i}x_{i} \tag{8}$

$\sum_{i=1}^N \alpha_{i}y_{i}=0 \tag{9}$

将 $(8)$ 式和 $(9)$ 式代入拉格朗日函数（ $(4)$ 式）

$\begin{align}L(w,b;\alpha) =& \frac{1}{2} ||w||^2 + \sum_{i=1}^N \alpha_{i}y_{i}(1-(w \cdot x_{i}+b)) \\=& \frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \alpha_{i} \alpha_{j} y_{i} y_{j}(x_{i} \cdot x_{j}) + \sum_{i=1}^N \alpha_{i} y_{i} - \sum_{i}^N \alpha_{i} y_{i}((\sum_{j=1}^N \alpha_{j} y_{j} x_{j}) \cdot x_{i}) - b \sum_{i=1}^N \alpha_{i} y_{i} + \sum_{i=1}^N \alpha_{i} \\=& -\frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \alpha_{i} \alpha_{j} y_{i} y_{j}(x_{i} \cdot x_{j}) + \sum_{i=1}^N \alpha_{i} \end{align}$

也即

$\mathop{min}\limits_{w,b} L(w,b;\alpha) = -\frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \alpha_{i} \alpha_{j} y_{i} y_{j}(x_{i} \cdot x_{j}) + \sum_{i=1}^N \alpha_{i} \tag{10}$

第二步，求解对偶问题 $\mathop{max}\limits_{\alpha}\ \mathop{min}\limits_{w,b} \ L(w,b;\alpha)$

由 $(10)$ 式和 $(9)$ 式，可得

优化问题三：

$\begin{split}&\mathop{min}\limits_{\alpha} \ &\frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \alpha_{i} \alpha_{j} y_{i} y_{j}(x_{i} \cdot x_{j}) - \sum_{i=1}^N \alpha_{i} \\& s.t. & \sum_{i=1}^N \alpha_{i} y_{i}=0 \\&& \alpha_{i} \geq 0, \ \ i=1,2,\dots,N\end{split} \tag{11}$

这就是线性可分支持向量机的对偶优化问题。求解此优化问题请参见此系列笔记的后续篇章（敬请期待）。

第三步，求解分类超平面 $(w^*,b^*)$ 和分类模型

当求解优化问题三（式 $(11)$ ）的最优解为 $\alpha^* = (\alpha^*_{1},\alpha^*_{2},\dots,\alpha^*_{N})^T$ ，根据式 $(8)$ 可得

$w^*=\sum_{i=1}^N \alpha^*_{i}y_{i}x_{i} \tag{12}$

接下来求解截距 $b$ 的最优解 $b^*$ 。

根据凸优化问题的KTT条件：优化问题一（式 $(1)$ ）是凸优化问题，则满足KKT条件的点是原问题和对偶问题的最优解（具体请参见[4]）。

$\begin{align}& y_{i}(w^*\cdot x_{i}+b^*) \geq 1,\ \ i=1,2,\dots,N \tag{13a} \\& \alpha^*_{i}(1-y_{i}(w^* \cdot x_{i}+b^*))=0,\ \ i=1,2,\dots,N \tag{13b} \\& \alpha^*_{i} \geq 0 ,\ \ i=1,2,\dots,N \tag{13c}\\& \frac{\partial}{\partial w} L(w^*,b^*;\alpha^*)=w^*-\sum_{i=1}^N \alpha^*_{i}y_{i}x_{i}=0 \tag{13d} \\& \frac{\partial}{\partial b} L(w^*,b^*;\alpha^*)=-\sum_{i=1}^N \alpha^*_{i}y_{i}=0 \tag{13e}\end{align}$

由式 $(13d)$ 也可得出式 $(12)$ 。

将式 $(13b)$ 单独拿出来，在 $\alpha^*_{i},\ i=1,2,\dots,N$ 中选择一个 $\alpha^*_{i}>0$ (支持向量)，则有

$\begin{align}& y_{i}(w^*_{i} \cdot x_{i}+b^*)-1=0 \tag{14a}\\\implies \ & y_{i}=w^*_{i}\cdot x_{i}+b^* \tag{14b}\\\implies \ & b* =y^*_{i}-w^*\cdot x_{i} \tag{14c}\end{align}$

将式 $(12)$ 代入式 $(14c)$ ，对于任一 $\alpha_{j} >0$ ，有

$b* =y^*_{j}-\sum_{i=1}^N \alpha^*_{i}y_{i}(x_{i} \cdot x_{j}) \tag{15}$

到此，对于已经求出优化问题的朗格朗日乘子的最优解 $\alpha^*=(\alpha^*_{1},\alpha^*_{2}, \dots,\alpha^*_{N})^T$ ，则线性可分支持向量机的最优超平面为 $w^*\cdot x+b^* = 0$ 的参数为

$\begin{align}& w^*=\sum_{i=1}^N \alpha^*_{i}y_{i}x_{i} \\& b* =y^*_{j}-\sum_{i=1}^N \alpha^*_{i}y_{i}(x_{i} \cdot x_{j}) , \ \alpha^*_{j} >0 \end{align}\tag{16}$