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

2020-08-01 本文已影响0人酷酷的群

一、硬间隔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

猜你喜欢

热点阅读