分类算法3_SVM数学推导部分

SVM优化部分简述

1.问题引入

对于如上如图的红、紫色样本点，希望找到一决策边界 $\vec{w}\cdot\vec{x}+b=0$ （ $\vec{w}$ 表示权重向量， $\vec{x}$ 表示样本特征矩阵，b 表示偏置）使得两条平行与决策边界的虚线到决策边界的相对距离最大化。两类数据中距离决策边界最近的点，就称为”支持向量“。紫色类的点为xp,红色的点为xr，可以得到：
$\vec{w}\cdot{x_p}+b=1,\vec{w}\cdot{x_r}+b=-1$
两式相减，得到：
$\vec{w}\cdot({x_p-x_r})=2$
上是两边同除以 $\Vert{w}\Vert$ ，则可以得到：
$\frac{\vec{w}\cdot(x_p-x_r)}{\Vert{w}\Vert}=\frac{2}{\Vert{w}\Vert}$
即:
$d=\frac{2}{\Vert{w}\Vert}$
所以最大边界所对应的决策边界就是要最大化d，就是求解 $\Vert{w}\Vert$ 的最小值。可以转化为以下函数的最小值：
$f(x)=\frac{\Vert{w}\Vert^2}{2}$
对于任意样本 $\mathcal{i}$ ，决策函数可写作：
$\vec{\mathbf{w}}\cdot{\vec{\mathbf{x_i}}}\geq1,if\quad y_i=1$

$\vec{\mathbf{w}}\cdot{\vec{\mathbf{x_i}}}\le-1,if\quad y_i=-1$

上面两个式子表示为：
$y_i(\vec{w}\cdot\vec{x_i}+b)\geq1,i=1,2,...N$
即可得到目标函数的形式：
$\min_{w,b}\frac{\Vert{w}\Vert^2}{2}$

$subject\quad y_i(\vec{w}\cdot\vec{x_i}+b)\geq1,i=1,2,...N$

2.拉格朗日乘数形式

由于损失函数是二次的。并且损失函数的约束条件在参数w和b下是线性的，因此目标函数为凸函数，可得到如下拉格朗日函数：
$L(\mathbf{w},b,\alpha)=\frac{1}{2}\Vert{w}\Vert^2-\sum_{i=1}^N\alpha_i(y_i(\vec{w}\cdot\vec{x_i}+b)-1),\alpha_i\geq0$

对于上式，为了实现求解最小值的同时让约束条件被满足，先以 $\alpha$ 为参数，求解 $L(w,b,a)$ 的最大值，再以w和b为参数，求解 $L(w,b,a)$ 的最小值，得到：
$\min_{w,b}\max_{\alpha_i\geq0}L(w,b,\alpha),\alpha_i\geq0$

3.拉格朗日对偶函数

$g(\alpha)=inf_{x\in\mathcal{D}}L(w,b.a)$

由
$\frac{\partial{L(\mathbf{w},b,\alpha)}}{\partial{\mathbf{w}}}=0\\\frac{\partial{L(\mathbf{w},b,\alpha)}}{\partial{{b}}}=0$
得到：
$\mathbf{w}=\sum_{i=1}^N\alpha_iy_i\vec{x_i}\quad\quad\quad (1)\\\sum_{i=1}^N\alpha_iy_i=0\quad\quad\quad\quad(2)$
其中：
$\begin{aligned} L(\mathbf{w},b,\alpha)&=\frac{1}{2}\Vert\mathbf{w}\Vert^2-\sum_{i=1}^N\alpha_i(y_i(\mathbf{w}\cdot\mathbf{x_i}+b)-1)\\&=\frac{1}{2}\Vert\mathbf{w}\Vert^2-\mathbf{w}\sum_{i=1}^N(\alpha_iy_i\mathbf{x_i})-b\sum_{i=1}^N\alpha_iy_i+\sum_{i=1}^N\alpha_i \end{aligned}$

代入(1)、（2）式整理得对偶函数：
$g(\alpha)=\sum_{i=1}^N\alpha_i-\frac{1}{2}\sum_{i,j=1}^N\alpha_i\alpha_jy_iy_j\mathbf{x_i}\mathbf{x_j}$

4.KKT条件及求解

当满足KKT条件：
$\begin{aligned} \frac{{\partial}L(\mathbf{w},b,\alpha)}{{\partial}{\mathbf{w}}}&=0\\\frac{{\partial}L(\mathbf{w},b,\alpha)}{{\partial}{b}}&=0\\1-y_i((\mathbf{w\cdot{x_i}})+b)&\leq0,\forall_i=1,2,...,N\\\alpha_i&\geq0,\forall_i=1,2,...,N\\\alpha_i(1-y_i((\mathbf{w\cdot{x_i}})+b))&=0,\forall_i=1,2,...,N \end{aligned}$
求解
$\min_{w,b}\max_{\alpha_i\geq0} L(w,b,\alpha)\Rightarrow{max_{\alpha_i\geq0} g(\alpha)}=\max_{\alpha_i\geq0}\min_{w,b}L(w,b,\alpha)$
所以求解的目标函数变化为：
$\max_{\alpha_i\geq0}(\sum_{i=0}^N\alpha_i-\frac12\sum_{i,j=1}^N\alpha_i\alpha_jy_iy_j\mathbf{x_i}\mathbf{x_j})$
使用SMO或者QP即可求解 $\alpha$ ，求得 $\alpha$ 后，代入(1)式求解 $\mathbf{w}$ ,使用(1)和决策边界的表达式结合式：
$\sum_{i=1}^N\alpha_iy_i\mathbf{x_i}\mathbf{x}+b=0$
来求解b。

至此，决策函数就可以被写作：
$\begin{aligned} f(x_{test})&=sign(\mathbf{w}\cdot\mathbf{x_{test}}+b)\\ &=sign(\sum_{i=1}^N\alpha_iy_i\mathbf{x_i\cdot{x_{test}}}+b) \end{aligned}$
$x_{test}$ 是任意测试样本，sign(h)当h>0时返回1(正样本)，h＜0时，返回-1(负样本)。

最后编辑于：2020.11.02 13:24:30