统计学习方法(3)---SVM

Support Vector Machine,SVM

Posted by weber on February 2, 2020

支持向量机,Support Vector Machine,SVM

1. SVM简介

支持向量机(Support Vector Machine,SVM)是一种二分类模型,其基本模型定义为特征空间上 间隔最大 的线性分类器。

img

2. 线性可分SVM推导

SVM要使间隔最大,就先要明确间隔的概念。

2.1 函数间隔与几何间隔

一个点 (xi,yi) 到超平面 $wx+b=0$ 的函数间隔为: 则样本的函数间隔为: 则样本的几何间隔为:

2.2 间隔最大化

我们可以得到间隔最大化的约束最优化问题: 令$\hat \gamma = 1$,得: 问题等价转换:

2.2 对偶算法

根据拉格朗日对偶性,将约束最优化问题转换为凸二次规划问题,写出拉格朗日函数: 则问题等价于:

求解w,b的偏导数:

令偏导数为0:

代入$L(w,b,\alpha)$得: $$ \begin{aligned} \min_{\alpha}&\ L(w,b,\alpha) = \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i*x_j) - \sum_{i=1}^N\alpha_i
s.t. & \sum \alpha_iy_i = 0
& a_i \geq0

\end{aligned} \alpha^=(\alpha_1^,\alpha_2^,…,\alpha_N^)^T w^* = \sum_{i=1}^n \alpha_i^* y_ix_i b^* = y_j - \sum_{i=1}^N\alpha_i^*y_i(x_i·x_j) $$

考虑对偶的最优化问题, $\alpha_j^*>0$ 的样本点应该位于间隔边界上,称为支持向量。满足:

3. 推广到线性支持向量机

如果数据集线性不可分,可以为每个样本点添加松弛向量$\xi$ ,则原始问题为: 容易得到对偶问题: 同时,可以推导出KKT停机条件,令 $g(x) = sign\Big(\sum_{i=1}^N \alpha_i^y_i(x_i·x_j)+b^\Big)$,则有 :

4. SMO算法

序列最小最优化算法(sequential minimal optimization,SMO)是支持向量机学习的一种快速算法,其特点是不断地将原二次规划问题分解为只有两个变量的二次规划子问题,并对子问题进行解析求解,直到所有变量满足 KKT 条件为止。

##4.1 具体算法 输入:训练集$T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$,精度$\varepsilon $ 输出:近似解$\hat\alpha$ (1) 取初值 $\alpha^{(0)}=0$,令$k=0$; (2) 选取优化变量$\alpha_1^{(k)},\alpha_2^{(k)}$: 第一个变量外层循环,选取违反KKT条件最严重的点。 第二个变量内层循环,选取使$\alpha_2^{(k)}$有足够大变化的点。 (3) 固定其他变量,解析求解两个变量的最优化问题,求得最优解$\alpha_1^{(k+1)},\alpha_2^{(k+1)}$; 更新方式为:

其中,

(4) 若在精度$\varepsilon$范围内满足停机条件: 其中, 则转(5),否则$k=k+1$,转(2) (5) 取 $\hat\alpha=\alpha^{(k+1)}$

5. SVM的核函数

对于线性不可分的情况,我们想构造核函数,将输入空间映射到特征空间,从而将问题转化为线性可分SVM。

但是如果想要知道输入空间到映射空间的映射,我们需要明确输入空间内数据的分布情况,但大多数情况下,我们并不知道自己所处理的数据的具体分布,故一般很难构造出完全符合输入空间的核函数,因此我们常用如下几种常用的核函数来代替自己构造核函数。

5.1 线性核函数

线性核,主要用于线性可分的情况,我们可以看到特征空间到输入空间的维度是一样的,其参数少速度快,对于线性可分数据,其分类效果很理想,因此我们通常首先尝试用线性核函数来做分类,看看效果如何,如果不行再换别的。

5.2 多项式核函数

多项式核函数可以实现将低维的输入空间映射到高纬的特征空间,但是多项式核函数的参数多,当多项式的阶数比较高的时候,核矩阵的元素值将趋于无穷大或者无穷小,计算复杂度会大到无法计算。

5.3 高斯核函数

高斯径向基函数是一种局部性强的核函数,其可以将一个样本映射到一个更高维的空间内,该核函数是应用最广的一个,无论大样本还是小样本都有比较好的性能,而且其相对于多项式核函数参数要少,因此大多数情况下在不知道用什么核函数的时候,优先使用高斯核函数。

5.4 Sigmoid核函数

采用sigmoid核函数,支持向量机实现的就是一种多层神经网络。

5.5 选择方法

  • 如果特征的数量大到和样本数量差不多,则选用LR或者线性核的SVM;
  • 如果特征的数量小,样本的数量正常,则选用SVM+高斯核函数;
  • 如果特征的数量小,而样本的数量很大,则需要手工添加一些特征从而变成第一种情况。