SVM

2019-11-04 本文已影响0人 Manfestain

1. SVM原理

SVM 是一种二类分类模型。它的基本模型是在特征空间中寻找间隔最大化的分离超平面的线性分类器。

当训练样本线性可分时，通过硬间隔最大化，学习一个线性分类器，即线性可分支持向量机；
当训练数据近似线性可分时，引入松弛变量，通过软间隔最大化，学习一个线性分类器，即线性支持向量机；
当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性支持向量机。

2. SVM为什么采用间隔最大化

当训练数据线性可分时，存在无穷个分离超平面可以将两类数据正确分开。感知机利用误分类最小策略，求得分离超平面，不过此时的解有无穷多个。

线性可分支持向量机利用间隔最大化求得最优分离超平面，这时，解是唯一的。另一方面，此时的分隔超平面所产生的分类结果是最鲁棒的，对未知实例的泛化能力最强。

函数间隔： $|wx+b|$ 能够表示 $x$ 距离超平面的远近，而 $wx+b$ 的符号与类标记 $y$ 的符号是否一致能够表示分类是否正确。用 $y(wx+b)$ 来表示分类的正确性及确信度。

仅有函数间隔是不够的。当 $w$ 和 $b$ 变为 $2w$ 和 $2b$ 时，超平面没有改变，但是函数间隔却变为原来的2倍。
几何间隔：对分离超平面的法向量 $w$ 加约束，如规范化 $||w||=1$ ，使得间隔是确定的。

定义为： $\gamma_i = y_i(\frac{w}{||w||}x_i + \frac{b}{||w||})$

3. 为什么要将求解 SVM 的原始问题转换为其对偶问题

一是对偶问题往往更易求解，当我们寻找约束存在时的最优点的时候，约束的存在虽然减小了需要搜寻的范围，但是却使问题变得更加复杂。为了使问题变得易于处理，我们的方法是把目标函数和约束全部融入一个新的函数，即拉格朗日函数，再通过这个函数来寻找最优点。

二是可以自然引入核函数，进而推广到非线性分类问题。

4. 为什么SVM要引入核函数

当样本在原始空间线性不可分时，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。而引入这样的映射后，所要求解的对偶问题的求解中，无需求解真正的映射函数，而只需要知道其核函数。

不引入核函数：先计算把 $x$ 映射到高维的 $\Phi(x)$ ，再计算 $\Phi(x_1)$ 和 $\Phi(x_2)$ 的点积，这一步开销很大。

采用核函数： $K(x,y)=<\Phi(x),\Phi(y)>$ ，即将两个低维空间中的向量映射到高维空间后的内积。

数据变成了高维空间中线性可分的数据
不需要求解具体的映射函数，只需要给定具体的核函数即可，这样使得求解的难度大大降低

5. 为什么SVM对缺失数据敏感

这里说的缺失数据是指缺失某些特征的数据，向量数据不完整。

SVM 没有处理缺失值的策略。而 SVM 希望样本在特征空间中线性可分，所以特征空间的好坏对SVM的性能很重要。缺失特征数据将影响训练结果的好坏。

6. SVM核函数如何选择

一般选择线性核和高斯核，也就是线性核与 RBF 核。

线性核： $x_i^Tx_j$ ，主要用于线性可分的情形，参数少，速度快，对于一般数据，分类效果已经很理想了。

RBF 核： $exp(-\frac{||x_i-x_j||^2}{2\sigma^2})$ ，主要用于线性不可分的情形，参数多，分类结果非常依赖于参数。

如果 Feature 的数量很大，跟样本数量差不多，这时候选用线性核的 SVM。
如果 Feature 的数量很大，超过样本数，这时候选用线性核的 SVM。
如果 Feature 的数量比较小，样本数量一般，不算大也不算小，选用高斯核的 SVM。
如果 Feature 的数量比较小，样本数量特别大，SVM性能不如深度神经网络。

7. 支持向量

硬间隔支持向量

求解目标：

$min\frac{1}{2}||w||^2$

s.t. $y_i(w^Tx_i+b)\geq1,i=1…N$
拉格朗日对偶问题：

$L(w,b,\alpha)=\frac{1}{2}||w||^2+\sum_{i=1}^{N}\alpha_i(1-y_i(w^Tx_i+b)$

s.t. $\alpha_i\geq0, i=1…N$
求解对偶问题的KKT条件：

$y_i(w^Tx_i+b)\geq1$ ；主问题可行解

$\alpha_i\geq0$ ；对偶问题可行解

$\alpha_i(1-y_i(w^Tx_i+b))=0$ ；互补松弛

支持向量对应于对偶变量 $\alpha_i>0$ 的样本

由互补松弛条件知，当 $\alpha_i>0$ 时， $1-y_i(w^Tx_i+b)=0$ ，即 $y_i(w^Tx_i+b)=1$

支持向量机的参数仅由支持向量决定，与其他样本无关

$w=\sum_{i=1}^{N}\alpha_iy_ix_i=\sum_{i:\alpha_i=0}^{N}0·y_ix_i+\sum_{i:\alpha_i>0}^{N}\alpha_iy_ix_i=\sum_{i\in SV}\alpha_iy_ix_i$ ；SV表示所有支持向量集合

$b=y_s-w^Tx_s = y_x-\sum_{i\in SV}\alpha_iy_ix_i$ ； $(x_s,y_s)$ 表示某一支持向量

软间隔支持向量

求解目标：

$min\frac{1}{2}||w||^2+C\sum_{i=1}^{N}\xi_i$

s.t. $y_i(w^Tx_i+b)\geq1-\xi_i$

$\xi_i\geq0,,i=1…N$
拉格朗日对偶问题：

$L(w,b,\alpha,\beta,\xi)=\frac{1}{2}||w||^2+\sum_{i=1}^{N}\alpha_i(1-\xi_i-y_i(w^Tx_i+b))+\sum_{i=1}^{N}\beta_i\xi_i+\sum_{i=1}^{N}C\xi_i$

s.t. $\alpha_i\geq0且\xi_i\geq0, i=1…N$
求解对偶问题的KKT条件：

$y_i(w^Tx_i+b)\ge1-\xi_i$ ， $\xi_i\geq0$ ；主问题可行解

$\alpha_i\geq0$ ， $\beta_i\geq0$ ；对偶问题可行解

$\alpha_i(1-\xi-i-y_i(w^Tx_i+b))=0$ ， $\beta_i\xi_i=0$ ；互补松弛

支持向量对应于 $\alpha_i>0$ 的样本， $\alpha_i=0$ 的样本点不是支持向量，对模型没有作用

对于 $\alpha_i >0$ ：

若 $0<\alpha_i<C$ ，则 $\beta_i=0$ ，即 $y_i(w^Tx_i+b)=1$ ，样本点刚好落在最大间隔边界上

若 $\alpha_i=C$ ，则 $\beta_i >0$ ，；

当 $\beta_i < 1$ 时，样本点落在最大间隔内部

当 $\beta_i > 1$ 时，样本点落在最大间隔内部（不属于自己的另一部分），即被分类错误