机器学习-白板推导学习笔记-6支持向量机SVM1

GiggleMiao

1289人浏览 · 2022-02-23 18:10:03

GiggleMiao · 2022-02-23 18:10:03 发布

本篇文章是根据视频（ link.）所作的学习笔记，旨在对机器学习的相关知识更好的理解和巩固。本人基础较弱，推导中看不懂的公式可能会细究，如果有理解不当之处也欢迎指出。

硬间隔SVM（hard-margin SVM）

之前介绍感知机算法的时候说到希望找到一个超平面，使两类数据不分错。我们想一下，仅仅要求不分错数据的超平面可能不止一个（如下图的L1，L2，L3），而支持向量机SVM就是来寻找一个最优的超平面。怎么去定义和寻找这个最优超平面，就是本篇要介绍的内容。

依然采用判别模型 $f(x)=sign(\omega ^{T}x+b)$ 对数据进行分类。

最大间隔分类

硬分隔SVM也叫做最大间隔分类器，即 $max\, margin(\omega ,b)$ ，这里的间隔margin指的是所有样本点中离分类超平面最近的那个点到超平面的距离。想一下，分类之后离超平面最近的点的间隔最大的话，那其他的样本点离超平面就更远，这样就能保证分类算法的鲁棒性，使得到的超平面是最优的分类平面。

同时还要保证分类正确的前提下去找最优的超平面，所以要记得带上约束条件 $y_{i}(\omega ^{T}x_{i}+b)> 0$ （这里不明白的话去看这个机器学习-白板推导学习笔记-4线性分类1_gigglehuahua的博客-CSDN博客）。

因此，硬分隔SVM所要优化的问题就是：

$\left\{\begin{matrix} max\, margin(\omega ,b)\: \: \textcircled{1}\\ \\s.t. \, \, y_{i}(\omega ^{T}x+b)> 0\: \: \textcircled{2}\end{matrix}\right.$

当数据 $x_{i}$ 是多维时，任一点到达超平面 $\omega ^{T}x_{i}+b$ 的距离为 $\frac{\left | \omega ^{T}x_{i}+b \right |}{\left \| \omega \right \|}$ ，其中 $\left \| \omega \right \|=\sqrt{\omega _{1}^{2}+\omega _{2}^{2}+...+\omega _{N}^{2}}$ 。

对于优化问题中的①：

$max\, margin(\omega ,b)\\ \\ =\mathop{max}_{\omega ,b} \: \mathop{min}_{x_{i}}\frac{\left | \omega ^{T}x_{i}+b \right |}{\left \| \omega \right \|}$

因为约束 $y_{i}(\omega ^{T}x+b)> 0$ ，而且 $\left | y_{i} \right |=1$ ，所以用 $y_{i}(\omega ^{T}x+b)$ 替换掉 $\left | \omega ^{T}x_{i}+b \right |$ 并不影响结果。

$\therefore \, \textcircled{1}=\mathop{max}_{\omega ,b} \: \mathop{min}_{x_{i}}\frac{1}{\left \| \omega \right \|}y_{i}(\omega ^{T}x_{i}+b)=\mathop{max}_{\omega ,b}\frac{1}{\left \| \omega \right \|}\, \mathop{min}_{x_{i}}y_{i}(\omega ^{T}x_{i}+b)$

对于约束条件②， $\exists r> 0, \: min\,\, y_{i}(\omega ^{T}x_{i}+b)=r$ ，这里r可以理解为该超平面的缩放尺度，令r=1不影响结果，所以 $min\,\, y_{i}(\omega ^{T}x_{i}+b)=1$ ，即 $y_{i}(\omega ^{T}x_{i}+b)\geq 1$ 。

此时优化问题变形为：

$\left\{\begin{matrix}\mathop{max}_{\omega ,b}\: \frac{1}{\left \| \omega \right \|} \\ \\s.t.\, \, y_{i}(\omega ^{T}x_{i}+b)\geq 1 \end{matrix}\right.$

$max\frac{1}{\left \| \omega \right \|}$ 与 $min \, \left \| \omega \right \|$ 等价，为了后面方便计算， $min\: \left \| \omega \right \|^{2}$ 也一样，可以进一步改写成：

$\left\{\begin{matrix} \mathop{min}_{\omega ,b}\: \frac{1}{2}\omega ^{T}\omega \\ \\s.t.\, \, y_{i}(\omega ^{T}x_{i}+b)\geq 1 \end{matrix}\right.$

带约束的求极值问题可以转化成拉格朗日函数的形式：

$L(\omega ,b,\lambda )= \frac{1}{2}\omega ^{T}\omega+\sum_{i=1}^{N}\lambda _{i}(1-y_{i}(\omega ^{T}x_{i}+b))$ , 其中 $\lambda _{i}\geq 0$ ， $1-y_{i}(\omega ^{T}x_{i}+b)\leq 0$

对于这个 $\lambda_{i}$ ，当 $\lambda _{i}= 0$ 时，称对应的约束条件 $1-y_{i}(\omega ^{T}x_{i}+b)$ 是松弛的，该约束对初始问题不起作用；当 $\lambda _{i}> 0$ 时，称对应的约束条件 $1-y_{i}(\omega ^{T}x_{i}+b)$ 是紧致的，是起作用的约束。

原问题与对偶问题

为了更好的去求解硬间隔分类SVM的目标函数，需要进行原问题和对偶问题的的介绍，首先通过凸优化问题来引入。

凸优化问题

一般对于优化问题，求取最值min,max,argmin,argmax这些，我们往往求导（偏导）或者求梯度等于零的方法来求取极值，这种情况下我们默认问题是一个凸问题（凹凸函数都是），这类问题有一个特点，即极值就是最值。但对于非凸问题，极值不止一个，这种情况下就不能直接用求导或者是梯度了。

那什么是凸优化问题呢？需要满足两个条件：

1) 目标函数是对凸（凹）函数求最值。

2) 约束条件是一个凸集。（凸集就是指集合中任意两个点之间的连线上所有的点也都属于这个集合）

不满足凸优化问题的，叫做非凸问题。对于非凸问题，我们希望将其转化为凸优化问题进行解决，怎么转化，就是对偶了！这里不对对偶性转化过多介绍，等下一看例题就会知道其形式了。对偶问题一定是凸优化问题，所以，往往将原问题转化为对偶问题，再加以解决。

例如有优化问题：

$\left\{\begin{matrix} min\: f_{0}(x)\\ \\ s.t.\: \left\{\begin{matrix} f_{i}(x)\leq 0\\ h_{j}(x)= 0\ \end{matrix}\right. \end{matrix}\right.$

该问题写成拉格朗日函数形式为 $L(x,\lambda ,\nu )=f_{0}(x)+\sum \lambda _{i}f_{i}(x)+\sum \nu _{i}h_{i}(x)$ 。

原问题

该目标函数的原问题形式为：

$\left\{\begin{matrix} min_{x}\: max_{\lambda ,\nu }L(x,\lambda ,\nu )\\ \\ s.t.\: \lambda _{i}\geq 0\end{matrix}\right.$

对偶问题

其对偶问题形式为：

$\left\{\begin{matrix} max_{\lambda ,\nu }\, min_{x}\: L(x,\lambda ,\nu )\\ \\s.t.\: \, \lambda _{i}\geq 0\end{matrix}\right.$

进一步，求 $min_{x}\: L(x,\lambda ,\nu )$ 相当于求 $\bigtriangledown _{x}L(x,\lambda ,\nu )=0$ ，所以对偶问题可进一步写成：

$\left\{\begin{matrix} max_{\lambda ,\nu }\,\, g(\lambda ,\nu )\\ \\s.t.\: \, \lambda _{i}\geq 0 \, ;\: \: \bigtriangledown _{x}L(x,\lambda ,\nu )=0 \end{matrix}\right.$

其中， $g(\lambda ,\nu )=min_{x}\: L(x,\lambda ,\nu )$ 。

对偶关系的强弱

需要注意的是，原问题与对偶问题不一定是等价的。一般情况下，对偶问题的解小于等于原问题的解，对于这点的证明如下：

$max_{\lambda ,\nu }\, min_{x}L(x,\lambda ,\nu )\leq min_{x}\, max_{\lambda ,\nu }L(x,\lambda ,\nu )$

令 $A(\lambda ,\nu )=min_{x}\, L(x,\lambda ,\nu ),\: B(x)=max_{\lambda ,\nu }\, L(x,\lambda ,\nu )$

则有 $A(\lambda ,\nu )\leq L(x,\lambda ,\nu )\leq B(x)$ ，即 $A(\lambda ,\nu )\leq B(x)$ ， $max_{\lambda ,\nu }\, A(\lambda ,\nu )\leq min_{x}\, B(x)$

因此 $max_{\lambda ,\nu }\, min_{x}L(x,\lambda ,\nu )\leq min_{x}\, max_{\lambda ,\nu }L(x,\lambda ,\nu )$

当原问题的解等于对偶问题的解时，构成强对偶关系，此时原问题和对偶问题是等价的。当然，我们希望构成的关系是强对偶的。

1 充分条件

满足Slater条件时，称二者构成强对偶关系。

Slater条件：存在一个点x在可行域的相对内部，使 $f_{i}(x)< 0$ 。

SVM为二次规划问题，天然满足Slater条件，所以为强对偶关系。

2 必要条件

当构成强对偶关系时，满足KKT条件。 $L(x,\lambda ,\nu )=f_{0}(x)+\sum \lambda _{i}f_{i}(x)+\sum \nu _{i}h_{i}(x)$

KKT条件：1）原问题可行条件—— $f_{i}(x)\leq 0\, ,\, h_{i}(x)=0$

2）对偶可行条件—— $\bigtriangledown _{x}L(x,\lambda ,\nu )=0 \, ,\, \lambda_{i}\geq 0$

3）互补松弛条件—— $\lambda _{i}f_{i}(x)=0$

当构成强对偶关系时，KKT条件就是要求的对偶问题的最优解，也即是原问题的最优解。

求解硬分隔SVM中参数

返回到最大间隔分类那里的目标函数 ${\color{Red} L(\omega ,b,\lambda )= \frac{1}{2}\omega ^{T}\omega+\sum_{i=1}^{N}\lambda _{i}(1-y_{i}(\omega ^{T}x_{i}+b))}$ , 其中 $\lambda _{i}\geq 0$ 。

其原问题的形式为：

$\left\{\begin{matrix} min_{\omega ,b}\, \, max_{\lambda }L(\omega ,b,\lambda )\\ \\s.t. \: \lambda _{i}\geq 0\end{matrix}\right.$

转化为对偶问题：

$\left\{\begin{matrix} max_{\lambda }\, \, min_{\omega ,b} L(\omega ,b,\lambda )\\ \\s.t. \: \lambda _{i}\geq 0\end{matrix}\right.$

进一步，令 $g(\lambda )=min_{\omega ,b} L(\omega ,b,\lambda )$ ，形式转化为：

$\left\{\begin{matrix} max_{\lambda }\, \, g(\lambda ) \\ \\s.t. \: \lambda _{i}\geq 0\, ;\, \, \bigtriangledown _{\omega ,b} L(\omega ,b,\lambda )=0\end{matrix}\right.$

其对应的KKT条件为：

$\left\{\begin{matrix}1-y_{i}(\omega ^{T}x_{i}+b)\leq 0\: \textcircled{1}\\ \\\bigtriangledown _{\omega ,b} L(\omega ,b,\lambda )=0\:\, \, ,\lambda _{i}\geq 0\, \, \textcircled{2}\\ \\\lambda _{i}(1-y_{i}(\omega ^{T}x_{i}+b))=0\: \textcircled{3}\end{matrix}\right.$

其中，KKT条件①对应原问题中的约束条件，也叫做原问题可行条件；KKT条件②对应对偶问题的约束条件，也叫做对偶可行条件；KKT条件③叫做互补松弛条件。

通过KKT条件可以来求最优解了，首先通过KKT条件②得到：

$\frac{\partial L}{\partial \omega }=0,\: \frac{\partial L}{\partial b }=0$ ，其中 $L(\omega ,b,\lambda )= \frac{1}{2}\omega ^{T}\omega+\sum_{i=1}^{N}\lambda _{i}(1-y_{i}(\omega ^{T}x_{i}+b))$ ，可以得到

$\left\{\begin{matrix} \frac{\partial L}{\partial \omega }=\omega -\sum_{i=1}^{N}\lambda _{i}y_{i}x_{i}=0\: ,\: \:{\color{Red} \hat{ \omega}=\sum_{i=1}^{N}\lambda _{i}y_{i}x_{i}} \\\\ \frac{\partial L}{\partial b}=-\sum _{i=1}^{N}\lambda _{i}y_{i}=0\: ,\, \:\sum _{i=1}^{N}\lambda _{i}y_{i}=0 \end{matrix}\right.$
然后根据KKT条件③可以得到，一定存在一组数据 $(x_{k},y_{k})$ ，使得 $1-y_{k}(\omega ^{T}x_{k}+b)=0$ ，此时 $y_{k}(\omega ^{T}x_{k}+b)=1$ ，又因为 $y_{k}$ 取值为+1，-1，所以 $y_{k}^{2}=1$ 。

$\therefore y_{k}^{2}(\omega ^{T}x_{k}+b)= y_{k}$

${\color{Red} \hat{b} }=y_{k}-\omega ^{T}x_{k} =y_{k}-(\sum_{i=1}^{N}\lambda _{i}y_{i}x_{i})^{T}x_{k}={\color{Red} y_{k}-\sum_{i=1}^{N}\lambda _{i}y_{i}x_{i}^{T}x_{k}}$