@zakexu 2021-01-18T17:04:38.000000Z 字数 2889 阅读 944

SVM模型

机器学习&深度学习

首发时间：2020.7.19
作者：zakexu（个人主页）

SVM模型

一、简介

1、支持向量机，因其英文名为Support Vector Machine，故一般简称SVM。通俗来讲，它是一种二分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化，最终可转化为一个凸二次规划问题的求解。

二、模型

1、SVM模型可以表示为：

$f(x)=sign(wx+b)$
其中：

$sign(x)= \begin{cases} +1, & \text {x>0} \\ 0, & \text{x=0}\\ -1, & \text{x<0} \end{cases}$
可以看出，分类的超平面为

$wx+b=0$ ，而当

$wx+b>0$ 时，表示正样本；当

$wx+b<0$ 时，表示负样本。

三、策略

1、SVM模型的策略是使间隔最大，函数间隔可以表示为：

$\hat{\gamma_i}=y_i(wx_i+b)$

几何间隔可以表示：

$\gamma_i=\frac{y_i(wx_i+b)}{||w||}$

2、SVM模型的优化策略可以表示如下：

$\max_{w,b}\gamma\\ s.t. \frac{y_i(wx_i+b)}{||w||}=\gamma_i>=\gamma$

根据函数间隔与几何间隔之间的关系，上述优化策略可以表示如下：

$\max_{w,b}\frac{\hat{\gamma}}{||w||}\\ s.t. y_i(wx_i+b)>=\hat{\gamma}$
由于函数间隔的大小随着w与b的同比例变化而变化，可暂定

$\hat{\gamma}=1$ （函数间隔为1的样本点称为支持向量），那么上述可以表示：

$\min_{w,b}\frac{1}{2}||w||^2\\ s.t. y_i(wx_i+b)>=1$

注：用hinge loss的形式表示就是：

$\sum_i max(0, 1-y_i(wx_i+b)) + \lambda ||w||^2$
可以有几层的理解：（1）函数间隔

$y_i(wx_i+b)$ 越接近1越好，也就是当

$y_i=1$ 时，

$wx_i+b=1$ ，当

$y_i=-1$ 时，

$wx_i+b=-1$ 。（2）当函数间隔大于1时，不影响优化目标，体现了支持向量的定义。（3）在优化loss的同时，加入正则项。

3、SVM的学习策略是具有线性约束的二次型目标函数，属于凸优化问题；为优化该学习策略，可以采用已经比较成熟的相关方法论；不过在实际应用中，为了引入核技巧使SVM扩展到高维非线性空间中，常使用拉格朗日对偶的思想来转换策略。
定义拉格朗日函数如下：

$L(w,b,\alpha)=\frac{1}{2}||w||^2+\sum_i\alpha_i(1-y_i(wx_i+b))$

根据KKT条件可得：

$\frac{\partial L(w,b,\alpha)}{\partial w}=w-\sum_i\alpha_iy_ix_i=0$

$\frac{\partial L(w,b,\alpha)}{\partial b}=-\sum_i\alpha_iy_i=0$

$\alpha_i(1-y_i(wx_i+b))=0$

$1-y_i(wx_i+b)<=0$

$\alpha_i>=0$

由此可得：

$w=\sum_i\alpha_iy_ix_i$

$b=y_i-x_i\sum_i\alpha_iy_ix_i$

代入拉格朗日函数可得：

$L(w,b,\alpha)=\sum_i\alpha_i-\frac{1}{2}\sum_{i,j}\alpha_i\alpha_jy_iy_jx_ix_j$

那么对偶问题就可以表示为：

$\min_{\alpha}\frac{1}{2}\sum_{i,j}\alpha_i\alpha_jy_iy_jx_ix_j-\sum_i\alpha_i\\ s.t. \sum_i\alpha_iy_i=0 \\ \alpha_i>=0$

通过SMO算法可求得 $\alpha^*$ ，那么即可得到该问题的最优解 $w^*,b^*$ 。

4、上述的算法更适合于数据集完全线性可分的情况，但若存在部分不可分的样本点，则可以引入松弛变量：

$\min_{w,b}\frac{1}{2}||w||^2+C\sum_{i}\xi_i\\ s.t. y_i(wx_i+b)>=1-\xi_i \\ \xi_i>=0$

基于拉格朗日可以得到对偶问题如下：

$\min_{\alpha}\frac{1}{2}\sum_{i,j}\alpha_i\alpha_jy_iy_jx_ix_j-\sum_i\alpha_i\\ s.t. \sum_i\alpha_iy_i=0 \\ 0=<\alpha_i<=C$

5、对于非线性数据集，可以在线性支持向量机中引入核技巧，用来解决非线性可分数据的分类问题。

$\min_{\alpha}\frac{1}{2}\sum_{i,j}\alpha_i\alpha_jy_iy_jK(x_ix_j)-\sum_i\alpha_i\\ s.t. \sum_i\alpha_iy_i=0 \\ 0=<\alpha_i<=C$

其中的核函数可以定义如下：

$K(x,y)=\phi(x)\phi(y)$

常见的核函数有：

（1）高斯核函数：

$K(x,y)=exp(-\frac{||x-y||^2}{2\sigma^2})$

（2）多项式核函数：

$K(x,y)=(x+y+1)^p$

注：拉格朗日对偶算法

1、基于拉格朗日对偶性可以将原始问题转化为对偶问题，通过解对偶问题而得到原始问题的解。

2、原始问题一般表示如下：

$\min_{w}f(w)\\ s.t. g_i(w)<=0,i=1,2,...,k \\h_i(w)=0,i=1,2,...,l$
其中：
（1）

$f(x)$ 函数与

$g(x)$ 函数是多元连续可导函数，

$h(x)$ 函数是仿射函数。
（2）若

$f(x)$ 是二次函数且与

$g(x)$ 是仿射函数，则为凸二次规划问题。

3、定义拉格朗日函数如下：

$L(w,\alpha,\beta)=f(w)+\sum_i\alpha_ig_i(w)+\sum_i\beta_ih_i(w)$

基于拉格朗日函数，原始问题可以表示为：

$p^*=\min_w\theta_p(w)=\min_w\max_{\alpha,\beta;\alpha_i>=0}L(w,\alpha,\beta)$

对偶问题可以表示为：

$d^*=\max_{\alpha,\beta;\alpha_i>=0}\theta_d(w)=\max_{\alpha,\beta;\alpha_i>=0}\min_wL(w,\alpha,\beta)$

原始解跟对偶解的关系如下：

$d^*<=p^*$

当 $f(x)$ 函数与 $g(x)$ 函数为凸函数且 $h(x)$ 函数是仿射函数时，等号成立。

4、拉格朗日函数的KKT条件：

$\frac{\partial L(w,\alpha,\beta)}{\partial w_i}=0$

$\frac{\partial L(w,\alpha,\beta)}{\partial \beta_i}=0$

$\alpha_ig_i(w)=0$

$g_i(w)<=0$