SVM

作者: Manfestain | 来源:发表于2019-11-04 11:18 被阅读0次

通俗易懂的支持向量机SVM
机器学习入门（十六）：SVM——线性 SVM，间隔由硬到软
第7章 SVM的三层理解
05 SVM - 支持向量机 - 概念、线性可分
机器学习技法笔记：02 Dual Support Vector
机器学习系列（三十二）——Support Vector Mach
svm支持向量机
Support Vector Machine
11 SVM - SMO - 序列最小优化算法
机器学习技法笔记：05 Kernel Logistic Regr

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$ 时，样本点落在最大间隔内部（不属于自己的另一部分），即被分类错误

8. SVM的优缺点

优点：

由于SVM是一个凸优化问题，所以求得的解一定是全局最优而不是局部最优。
不仅适用于线性线性问题还适用于非线性问题(用核技巧)。
拥有高维样本空间的数据也能用SVM，这是因为数据集的复杂度只取决于支持向量而不是数据集的维度，这在某种意义上避免了“维数灾难”。
理论基础比较完善(例如神经网络就更像一个黑盒子)。

缺点：

二次规划问题求解将涉及m阶矩阵的计算(m为样本的个数), 因此SVM不适用于超大数据集。(SMO算法可以缓解这个问题)
只适用于二分类问题。(SVM的推广SVR也适用于回归问题；可以通过多个SVM的组合来解决多分类问题)

通俗易懂的支持向量机SVM
SVM 的原理和目标几个基本概念线性可分SVM——线性 SVM——非线性 SVM1、线性可分SVM，表示可以用...
机器学习入门（十六）：SVM——线性 SVM，间隔由硬到软
从线性可分 SVM 到线性 SVM 从现实情况引出线性 SVM 线性可分 SVM，这种 SVM 学习的训练数据本身...
第7章 SVM的三层理解
内容一、了解SVM 二、深入SVM 三、证明SVM（暂时不懂） ########################...
05 SVM - 支持向量机 - 概念、线性可分
04 SVM - 感知器模型一、SVM概念支持向量机(Support Vector Machine, SVM)...
机器学习技法笔记：02 Dual Support Vector
Roadmap Motivation of Dual SVM Lagrange Dual SVM Solving ...
机器学习系列（三十二）——Support Vector Mach
本篇主要内容：SVM，Hard Margin SVM，Soft Margin SVM 什么是支撑向量机支撑向量机...
svm支持向量机
1.1 svm简介 A Support Vector Machine (SVM) is a discriminat...
Support Vector Machine
SVM学习笔记 1. The target of SVM is finding a hyper plane to ...
11 SVM - SMO - 序列最小优化算法
05 SVM - 支持向量机 - 概念、线性可分06 SVM - 线性可分模型算法和案例07 SVM - 软间隔模...
机器学习技法笔记：05 Kernel Logistic Regr
Roadmap Soft-Margin SVM as Regularized Model SVM versus L...