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

作者: Herbert002 | 来源:发表于2020-06-01 18:16 被阅读0次

支持向量机-QA
支持向量机
支持向量机—从推导到python手写
支持向量机（二）——线性可分支持向量机求解
支持向量机
支持向量机——线性可分支持向量机
SVM支持向量机
SVM第一课
吃瓜学习5-第六章支持向量机(间隔与支持向量机、对偶问题、软间隔
SVM

〇、说明

支持向量机(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}$

此时，分类模型为式 $(3)$ 。

四、支持向量

将上面KKT条件的式 $(13b)$ 单独拿出来

$\alpha^*_{i}(1-y_{i}(w^*_{i} \cdot x_{i}+b^*))=0,\ \ i=1,2,\dots,N \tag{17}$

当 $\alpha^*_{i}>0$ 时，则有

$\begin{align}& y_{i}(w^*\cdot x_{i}+b^*) = 1 \tag{18a}\\\Rightarrow \ & w^* \cdot x_{i}+b^* = \pm 1 \tag{18b}\end{align}$

对应的样本都在间隔边界上，如下图

图1[2]

再观察式 $(16)$ ，当 $\alpha^*_{i} = 0$ 时，对应的样本是不参与参数计算的。

综上，线性可分支持向量机是强依赖于离分类超平面最近的样本点的，这和基于概率统计的分类方法是不同的。

五、附录

A、参考

[1]、《统计学习方法（第二版）》，李航著，清华大学出版社

[2]、《机器学习》，周志华著，清华大学出版社

[3]、《支持向量机（一）——线性可分支持向量机导出》

[4]、《凸优化（八）——Lagrange对偶问题》

B、相关目录

[a]、支持向量机（一）——线性可分支持向量机导出

[b]、支持向量机（二）——线性可分支持向量机求解

[c]、支持向量机（三）——线性支持向量机

[d]、支持向量机（四）——核方法

[e]、支持向量机（五）——SMO算法

C、时间线

2020-06-01 第一次发布

2020-06-02 添加《支持向量》部分

2020-06-06 修改图片来源

支持向量机-QA
Q1：SVM的类型有哪些？三类：线性可分支持向量机、线性支持向量机、非线性支持向量机线性可分支持向量机：当训练数...
支持向量机
支持向量机线性可分支持向量机与硬间隔最大化线性支持向量机与软间隔最大化非线性支持向量机与核函数序列最小最优...
支持向量机—从推导到python手写
笔者比较懒能截图的地方都截图了。 1 支持向量机分类支持向量机分为三类：（1）线性可分支持向量机，样本线性可分，...
支持向量机（二）——线性可分支持向量机求解
〇、说明支持向量机(Support Vector Machine,SVM)是监督学习中非常经典的算法。笔者主要参...
支持向量机
问题 1. 支持向量机是如何进行数据分类？ 2. 支持向量机求解过程 3. 支持向量机是怎么对线性不...
支持向量机——线性可分支持向量机
GitHub简书CSDN 1 线性可分支持向量机支持向量机(Support vector machines, S...
SVM支持向量机
线性支持向量机# 径向支持向量机# 最优参数##
SVM第一课
概念 1.线性可分支持向量机：可以用一条线分割，hard margin maximization2.线性支持向量机...
吃瓜学习5-第六章支持向量机(间隔与支持向量机、对偶问题、软间隔
支持向量机基本概念支持向量机的基本想法：从几何角度，对于线性可分数据集，支持向量机就是找位于两类训练样本"正中...
SVM
二分类学习策略：间隔最大化-->求解凸二次规划分类线性可分-->硬间隔支持向量机近似线性可分-->软间隔支...