支持向量机|机器学习推导系列（七）

作者: 酷酷的群 | 来源:发表于2020-08-01 16:23 被阅读0次

支持向量机|机器学习推导系列（七）
机器学习笔记（10）：支持向量机
机器学习（四）支持向量机
SVM(支持向量机)的原理
支持向量机（SVM）入门理解与推导
新2019计划：机器学习100天—支持向量机【6】
机器学习实战：基于Scikit-Learn和TensorFlow
[机器学习入门] 李宏毅机器学习笔记-23（Support Ve
机器学习-----支持向量机
机器学习：支持向量机

一、硬间隔SVM

模型定义

假设有以下数据：

$\left \{(x_{i},y_{i})\right \}_{i=1}^{N},x_{i}\in \mathbb{R}^{p},y_{i}\in \{+1,-1\}$

SVM的主要思想是在特征空间中寻找一个最大间隔的超平面 $w^{T}x+b$ 实现数据的二分类，SVM属于判别模型。这里的间隔指的是样本点到分离超平面的距离的最小值，用函数 $margin(w,b)$ 来表达。下图中在 $w\cdot x+b=1$ 和 $w\cdot x+b=-1$ 线上的样本点就叫支持向量：

支持向量机

超平面实现将数据的正例和负例分隔开，因此有：

$\left.\begin{matrix} y_{i}=+1,w^{T}x_{i}+b>0\\ y_{i}=-1,w^{T}x_{i}+b<0 \end{matrix}\right\}y_{i}(w^{T}x_{i}+b)>0,for\; \forall i=1,2,\cdots ,N$

另外最大间隔通过以下方式来表达：

$①\; 首先要明确样本点到超平面的距离公式：\\ distance(w,b,x_{i})=\frac{\left | w^{T}x+b\right |}{\left \| w\right \|}\\ (可以参考初中知识点：点到直线距离d=\frac{\left | Ax+By+C\right |}{\sqrt{A^{2}+B^{2}}})\\ ②\; 因此间隔可以表达为：\\ margin(w,b)=\underset{x_{i}}{min}\; distance(w,b,x_{i})=\underset{x_{i}}{min}\frac{\left | w^{T}x_{i}+b\right |}{\left \| w\right \|},i=1,2,\cdots ,N\\ ③\; 最大间隔可以表达为：\\ \underset{w,b}{max}\; margin(w,b)=\underset{w,b}{max}\; \underset{x_{i}}{min}\frac{\left | w^{T}x_{i}+b\right |}{\left \| w\right \|}=\underset{w,b}{max}\; \underset{x_{i}}{min}\frac{y_{i}(w^{T}x_{i}+b)}{\left \| w\right \|},i=1,2,\cdots ,N$

然后求解支持向量机就可以转化为以下带约束的优化问题：

$\left\{\begin{matrix} \underset{w,b}{max}\; margin(w,b)=\underset{w,b}{max}\; \underset{x_{i}}{min}\frac{y_{i}(w^{T}x_{i}+b)}{\left \| w\right \|},i=1,2,\cdots ,N\\ s.t.\; y_{i}(w^{T}x_{i}+b)>0,i=1,2,\cdots ,N \end{matrix}\right.$

上述优化问题还可以进一步转化：

$由约束y_{i}(w^{T}x_{i}+b)>0,i=1,2,\cdots ,N可以得出\\ \exists \gamma >0使得\underset{x_{i}}{min}\; y_{i}(w^{T}x_{i}+b)=\gamma \\ 由于确定同一个超平面的w,b可以任意放缩，所以这里的\gamma 可以约束等于1。\\ 则\underset{w,b}{max}\; margin(w,b)\\ =\underset{w,b}{max}\; \underset{x_{i}}{min}\frac{y_{i}(w^{T}x_{i}+b)}{\left \| w\right \|}\\ =\underset{w,b}{max}\frac{1}{\left \| w\right \|}\underset{=\gamma =1}{\underbrace{\underset{x_{i}}{min}\; y_{i}(w^{T}x_{i}+b)}}\\ =\underset{w,b}{max}\frac{1}{\left \| w\right \|}\\ =\underset{w,b}{min}\frac{1}{2}w^{T}w\\ i=1,2,\cdots ,N$

由此上述优化问题转化为：

$\left\{\begin{matrix} \underset{w,b}{min}\frac{1}{2}w^{T}w \\ s.t.\; y_{i}(w^{T}x_{i}+b)\geq 1,i=1,2,\cdots ,N \end{matrix}\right.$

这是一个带N个约束的凸优化问题。

优化问题的转化

上述优化问题可以使用拉格朗日乘子法来求解，构建拉格朗日函数：

$L(w,b,\lambda )=\frac{1}{2}w^{T}w+\sum_{i=1}^{N}\lambda _{i}(1-y_{i}(w^{T}x_{i}+b))\\ \lambda =\begin{pmatrix} \lambda _{1} & \lambda _{2} & \cdots & \lambda _{N} \end{pmatrix}^{T}$

然后上述优化问题就可以转换为以下优化问题：

$\left\{\begin{matrix} \underset{w,b}{min}\; \underset{\lambda }{max}L(w,b,\lambda )=\frac{1}{2}w^{T}w+\sum_{i=1}^{N}\lambda _{i}(1-y_{i}(w^{T}x_{i}+b))\\ s.t.\; \lambda _{i}\geq 0,i=1,2,\cdots ,N \end{matrix}\right.$

我们可以简单地看一下为什么可以这么转化：

$当1-y_{i}(w^{T}x_{i}+b)>0时，由于\lambda _{i}\geq 0，所以\underset{\lambda }{max}L(w,b,\lambda )=\infty \\ 当1-y_{i}(w^{T}x_{i}+b)\leq 0时，由于\lambda _{i}\geq 0，所以\underset{\lambda }{max}L(w,b,\lambda )=\frac{1}{2}w^{T}w \\ 因此\underset{w,b}{min}\; \underset{\lambda }{max}L(w,b,\lambda )=\underset{w,b}{min}\left \{\frac{1}{2}w^{T}w,\infty \right \}=\frac{1}{2}w^{T}w$

然后使用以下结论继续对该优化问题进行转化：

$min\; max\; L的对偶问题为max\; min\; L,有以下结论：\\ min\; max\; L\geq max\; min\; L\\ 可以简单地认为对于L先取最大，再从最大里面取最小就一定大于等于先取最小，再从最小里面取最大\\ 类似于“凤尾”\geq “鸡头”\\ 如果min\; max\; L是凸优化问题，所以min\; max\; L=max\; min\; L，为强对偶关系$

因此该优化问题可以继续转化：

$\left\{\begin{matrix} \underset{\lambda }{max}\; \underset{w,b}{min}\;L(w,b,\lambda )=\frac{1}{2}w^{T}w+\sum_{i=1}^{N}\lambda _{i}(1-y_{i}(w^{T}x_{i}+b))\\ s.t.\; \lambda _{i}\geq 0,i=1,2,\cdots ,N \end{matrix}\right.$

总结一下，该优化问题经历了以下转化过程：

$①\; 带约束优化问题\left\{\begin{matrix} \underset{w,b}{max}\; margin(w,b)=\underset{w,b}{max}\; \underset{x_{i}}{min}\frac{y_{i}(w^{T}x_{i}+b)}{\left \| w\right \|},i=1,2,\cdots ,N\\ s.t.\; y_{i}(w^{T}x_{i}+b)>0,i=1,2,\cdots ,N \end{matrix}\right.\\ ②\; 带约束优化问题\left\{\begin{matrix} \underset{w,b}{min}\;\frac{1}{2}w^{T}w\\ s.t.\; y_{i}(w^{T}x_{i}+b)\geq 1,i=1,2,\cdots ,N \end{matrix}\right.\\ ③\; 无约束优化问题\left\{\begin{matrix} \underset{w,b}{min}\; \underset{\lambda }{max}L(w,b,\lambda )=\frac{1}{2}w^{T}w+\sum_{i=1}^{N}\lambda _{i}(1-y_{i}(w^{T}x_{i}+b))\\ s.t.\; \lambda _{i}\geq 0,i=1,2,\cdots ,N \end{matrix}\right.\\ ④\; 无约束优化问题\left\{\begin{matrix} \underset{\lambda }{max}\; \underset{w,b}{min}\;L(w,b,\lambda )=\frac{1}{2}w^{T}w+\sum_{i=1}^{N}\lambda _{i}(1-y_{i}(w^{T}x_{i}+b))\\ s.t.\; \lambda _{i}\geq 0,i=1,2,\cdots ,N \end{matrix}\right.$

模型求解

对 $b$ 求导

$\frac{\partial L}{\partial b}=\frac{\partial \sum_{i=1}^{N}\lambda _{i}-\sum_{i=1}^{N}\lambda _{i}y_{i}(w^{T}x_{i}+b)}{\partial b}=\frac{\partial -\sum_{i=1}^{N}\lambda _{i}y_{i}b}{\partial b}=-\sum_{i=1}^{N}\lambda _{i}y_{i}=0\\ 因此得出\sum_{i=1}^{N}\lambda _{i}y_{i}=0$

求解 $w$

$将上一步的结果代入L(w,b,\lambda )\\ L(w,b,\lambda )=\frac{1}{2}w^{T}w+\sum_{i=1}^{N}\lambda _{i}-\sum_{i=1}^{N}\lambda _{i}y_{i}w^{T}x_{i}-\underset{=0}{\underbrace{\sum_{i=1}^{N}\lambda _{i}y_{i}b}} \\ =\frac{1}{2}w^{T}w+\sum_{i=1}^{N}\lambda _{i}-\sum_{i=1}^{N}\lambda _{i}y_{i}w^{T}x_{i} \\ \frac{\partial L}{\partial w}=w-\sum_{i=1}^{N}\lambda _{i}y_{i}x_{i}=0 \\ 得出w^{*}=\sum_{i=1}^{N}\lambda _{i}y_{i}x_{i}$

这里我们可以看出 $w^{*}$ 是数据的线性组合。

得出 $\underset{w,b}{min}\;L(w,b,\lambda )$

$接着将上一步的结果代入L(w,b,\lambda )\\ \underset{w,b}{min}\;L(w,b,\lambda )=\frac{1}{2}(\sum_{i=1}^{N}\lambda _{i}y_{i}x_{i})^{T}(\sum_{j=1}^{N}\lambda _{j}y_{j}x_{j})+\sum_{i=1}^{N}\lambda _{i}-\sum_{i=1}^{N}\lambda _{i}y_{i}(\sum_{j=1}^{N}\lambda _{j}y_{j}x_{j})^{T}x_{i}\\ =\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}x_{i}^{T}x_{j}-\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}{\color{Red}{x_{j}^{T}x_{i}}}+\sum_{i=1}^{N}\lambda _{i} \\ =\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}x_{i}^{T}x_{j}-\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}{\color{Red}{x_{i}^{T}x_{j}}}+\sum_{i=1}^{N}\lambda _{i} \\ =-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}x_{i}^{T}x_{j}+\sum_{i=1}^{N}\lambda _{i}$

因此该优化问题就相当于：

$\left\{\begin{matrix} \underset{\lambda }{max}\; -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}x_{i}^{T}x_{j}+\sum_{i=1}^{N}\lambda _{i},i=1,2,\cdots ,N \\ s.t.\; \lambda _{i}\geq 0,i=1,2,\cdots ,N \end{matrix}\right.$

也就相当于：

$\left\{\begin{matrix} \underset{\lambda }{min}\; \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}x_{i}^{T}x_{j}-\sum_{i=1}^{N}\lambda _{i},i=1,2,\cdots ,N\\ s.t.\; \lambda _{i}\geq 0,i=1,2,\cdots ,N \end{matrix}\right.$

KKT条件

首先定义该优化问题的KKT条件：

$\left\{\begin{matrix} \frac{\partial L}{\partial w}=0,\frac{\partial L}{\partial b}=0\\ \lambda _{i}(1-y_{i}(w^{T}x_{i}+b))=0\\ \lambda _{i}\geq 0\\ 1-y_{i}(w^{T}x_{i}+b)\leq 0 \end{matrix}\right.$

该优化问题满足上述KKT条件，这是由于以下定理：

$原问题、对偶问题具有强对偶关系\Leftrightarrow 满足KKT条件$

KKT条件中 $\lambda _{i}(1-y_{i}(w^{T}x_{i}+b))=0$ 也叫松弛互补条件，即 $\lambda _{i}$ 和 $1-y_{i}(w^{T}x_{i}+b)$ 总有一个为0。也就是说只有支持向量对应的 $\lambda _{i}$ 才可能有值（ $\lambda _{i}\neq 0$ ），而其他不在 $w\cdot x+b=1$ 和 $w\cdot x+b=-1$ 上的样本点对应的 $\lambda _{i}$ 一定为 $0$ ，该性质可以用来求出 $b^{*}$ 。

我们已经根据 $\frac{\partial L}{\partial w}=0$ 求出了 $w^{*}$ ，接下来要求出 $b^{*}$ ，我们可以通过求解 $\underset{\lambda }{min}\; \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}x_{i}^{T}x_{j}-\sum_{i=1}^{N}\lambda _{i},i=1,2,\cdots ,N\\$ 来得出各个 $\lambda _{i}$ ，而这个过程也是支持向量机算法计算量最大的地方，这里我们就不展示过程了。

找出求解得到的不等于 $0$ 的 $\lambda _{i}$ ，也就是支持向量对应的 $\lambda _{i}$ ，假设其中一个支持向量为 $(x_{k},y_{k})$ ，则有 $1-y_{k}(w^{T}x_{k}+b)=0$ ，最终可以解得：

$b^{*}=y_{k}-w^{T}x_{k}=y_{k}-\sum_{i=1}^{N}\lambda _{i}y_{i}x_{i}^{T}x^{k}$

二、软间隔SVM

我们的训练数据通常不是理想的线性可分，有时甚至是线性不可分的数据。对于存在噪声的一些数据，我们应该允许一点分类错误，因此我们需要对目标函数进行一些调整：

$\underset{w,b}{min}\; \frac{1}{2}w^{T}w+loss$

使用误分类点的个数作为loss

$loss=\sum_{i=1}^{N}I\left \{y_{i}(w^{T}x_{i}+b)<1\right \}$

显然使用的指示函数是不连续的，不利于求解，所以不使用这种loss函数。

使用距离作为loss

$\left.\begin{matrix} 如果y_{i}(w^{T}x_{i}+b)\geq 1,loss=0\\ 如果y_{i}(w^{T}x_{i}+b)< 1,loss=1-y_{i}(w^{T}x_{i}+b) \end{matrix}\right\}loss=max\left \{0,1-y_{i}(w^{T}x_{i}+b)\right \}$

该函数为合页损失函数（hinge loss），令 $z=y_{i}(w^{T}x_{i}+b)$ ，则 $loss$ 对 $z$ 的图像如下：

合页损失函数

软间隔SVM的优化问题

$\left\{\begin{matrix} \underset{w,b}{min}\; \frac{1}{2}w^{T}w+C\sum_{i=1}^{N}max\left \{0,1-y_{i}(w^{T}x_{i}+b)\right \}\\ s.t.\; y_{i}(w^{T}x_{i}+b)\geq 1,i=1,2,\cdots ,N \end{matrix}\right.$

引入 $\xi _{i}=1-y_{i}(w^{T}x_{i}+b),\xi _{i}\geq 0,i=1,2,\cdots ,N$ ，则该优化问题转化为：

$\left\{\begin{matrix} \underset{w,b}{min}\; \frac{1}{2}w^{T}w+C\sum_{i=1}^{N}\xi _{i}\\ s.t.\; y_{i}(w^{T}x_{i}+b)\geq 1-\xi _{i},i=1,2,\cdots ,N \end{matrix}\right.$

上面的式子中，常数 $C$ 可以看作允许的错误⽔平，同时上式为了进⼀步消除 $max$ 符号，对数据集中的每⼀个观测，我们可以认为其⼤部分满⾜约束，但是其中部分违反约束，因此这部分约束变成 $y_{i}(w^{T}x_{i}+b)\geq 1-\xi _{i}$ 。

软间隔SVM也是使用拉格朗日乘子法进行求解。

支持向量机|机器学习推导系列（七）
一、硬间隔SVM 模型定义假设有以下数据： SVM的主要思想是在特征空间中寻找一个最大间隔的超平面实现数据的二分...
机器学习笔记（10）：支持向量机
本文来自之前在Udacity上自学机器学习的系列笔记。这是第10篇，介绍了监督学习中的支持向量机。支持向量机支持...
机器学习（四）支持向量机
支持向量机的数学推导较复杂，本篇文章不对支持向量机的数学原理进行推导。仅仅从支持向量机要解决的问题出发，大致推导支...
SVM(支持向量机)的原理
原博文：支持向量机（SVM）入门理解与推导一、简介支持向量机（support vector machines）...
支持向量机（SVM）入门理解与推导
首先推荐：机器学习实战教程（八）：支持向量机原理篇之手撕线性SVM机器学习实战教程（九）：支持向量机实战篇之再撕非...
新2019计划：机器学习100天—支持向量机【6】
支持向量机本篇简单介绍下支持向量机，后面章节将会详细介绍支持向量机的公式推导和原理。它是定义在特征空间上的间隔最...
机器学习实战：基于Scikit-Learn和TensorFlow
机器学习实战：基于Scikit-Learn和TensorFlow---第五章笔记支持向量机支持向量机（简称SV...
[机器学习入门] 李宏毅机器学习笔记-23（Support Ve
[机器学习入门] 李宏毅机器学习笔记-23（Support Vector Machine；支持向量机） Suppo...
机器学习-----支持向量机
今天接着总结西瓜书的支持向量机（support vector machine) 支持向量机的概念理解本质上就是我们...
机器学习：支持向量机
本文来自同步博客。 P.S. 不知道简书怎么显示数学公式以及更好的排版内容。所以如果觉得文章下面格式乱的话请自行跳...