周志华 《机器学习》笔记五 支持向量机

应聘数据挖掘工程师或机器学习工程师,面试官经常会考量面试者对SVM的理解。

以下是我自己在准备面试过程中,基于个人理解,总结的一些SVM面试常考问题(想到会再更新),如有错漏,请批评指正。(大神请忽视)

转载请注明出处:blog.csdn.net/szlcw1

SVM的原理是什么?

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

(1)当训练样本线性可分时,通过硬间隔最大化,学习一个线性分类器,即线性可分支持向量机;

(2)当训练数据近似线性可分时,引入松弛变量,通过软间隔最大化,学习一个线性分类器,即线性支持向量机;

(3)当训练数据线性不可分时,通过使用核技巧及软间隔最大化,学习非线性支持向量机。

注:以上各SVM的数学推导应该熟悉:硬间隔最大化(几何间隔)—学习的对偶问题—软间隔最大化(引入松弛变量)—非线性支持向量机(核技巧)。

SVM为什么采用间隔最大化?

当训练数据线性可分时,存在无穷个分离超平面可以将两类数据正确分开。

感知机利用误分类最小策略,求得分离超平面,不过此时的解有无穷多个。

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

然后应该借此阐述,几何间隔,函数间隔,及从函数间隔—>求解最小化1/2 ||w||^2 时的w和b。即线性可分支持向量机学习算法—最大间隔法的由来。

 

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

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

二、自然引入核函数,进而推广到非线性分类问题。

 

为什么SVM要引入核函数?

当样本在原始空间线性不可分时,可将样本从原始空间映射到一个更高维的特征空间,使得样本在这个特征空间内线性可分。

引入映射后的对偶问题:

在学习预测中,只定义核函数K(x,y),而不是显式的定义映射函数ϕ。因为特征空间维数可能很高,甚至可能是无穷维,因此直接计算ϕ(xϕ(y)是比较困难的。相反,直接计算K(x,y)比较容易(即直接在原来的低维空间中进行计算,而不需要显式地写出映射后的结果)。

核函数的定义:K(x,y)=<ϕ(x),ϕ(y)>,即在特征空间的内积等于它们在原始样本空间中通过核函数K计算的结果。

除了 SVM 之外,任何将计算表示为数据点的内积的方法,都可以使用核方法进行非线性扩展。

svm RBF核函数的具体公式?


Gauss径向基函数则是局部性强的核函数,其外推能力随着参数σ的增大而减弱。

这个核会将原始空间映射为无穷维空间。不过,如果 σ 选得很大的话,高次特征上的权重实际上衰减得非常快,所以实际上(数值上近似一下)相当于一个低维的子空间;反过来,如果 σ 选得很小,则可以将任意的数据映射为线性可分——当然,这并不一定是好事,因为随之而来的可能是非常严重的过拟合问题。不过,总的来说,通过调控参数σ ,高斯核实际上具有相当高的灵活性,也是使用最广泛的核函数之一。

 

为什么SVM对缺失数据敏感?

这里说的缺失数据是指缺失某些特征数据,向量数据不完整。SVM没有处理缺失值的策略(决策树有)。而SVM希望样本在特征空间中线性可分,所以特征空间的好坏对SVM的性能很重要。缺失特征数据将影响训练结果的好坏。

SVM是用的是哪个库?Sklearn/libsvm中的SVM都有什么参数可以调节?

用的是sklearn实现的。采用sklearn.svm.SVC设置的参数。本身这个函数也是基于libsvm实现的(PS: libsvm中的二次规划问题的解决算法是SMO)。

SVC函数的训练时间是随训练样本平方级增长,所以不适合超过10000的样本。

对于多分类问题,SVC采用的是one-vs-one投票机制,需要两两类别建立分类器,训练时间可能比较长。

sklearn.svm.SVC(C=1.0kernel=’rbf’degree=3gamma=’auto’coef0=0.0shrinking=Trueprobability=False,tol=0.001cache_size=200class_weight=Noneverbose=Falsemax_iter=-1decision_function_shape=None,random_state=None)

参数:

l  C:C-SVC的惩罚参数C?默认值是1.0

C越大,相当于惩罚松弛变量,希望松弛变量接近0,即对误分类的惩罚增大,趋向于对训练集全分对的情况,这样对训练集测试时准确率很高,但泛化能力弱。C值小,对误分类的惩罚减小,允许容错,将他们当成噪声点,泛化能力较强。

l  kernel :核函数,默认是rbf,可以是‘linear’, ‘poly’, ‘rbf’, ‘sigmoid’, ‘precomputed’

0 – 线性:u’v

1 – 多项式:(gamma*u’*v + coef0)^degree

2 – RBF函数:exp(-gamma|u-v|^2)

3 –sigmoid:tanh(gamma*u’*v + coef0)

l  degree :多项式poly函数的维度,默认是3,选择其他核函数时会被忽略。

l  gamma : ‘rbf’,‘poly’ 和‘sigmoid’的核函数参数。默认是’auto’,则会选择1/n_features

l  coef0 :核函数的常数项。对于‘poly’和 ‘sigmoid’有用。

l  probability :是否采用概率估计?.默认为False

l  shrinking :是否采用shrinking heuristic方法,默认为true

l  tol :停止训练的误差值大小,默认为1e-3

l  cache_size :核函数cache缓存大小,默认为200

l  class_weight :类别的权重,字典形式传递。设置第几类的参数C为weight*C(C-SVC中的C)

l  verbose :允许冗余输出?

l  max_iter :最大迭代次数。-1为无限制。

l  decision_function_shape :‘ovo’, ‘ovr’ or None, default=None3

l  random_state :数据洗牌时的种子值,int值

主要调节的参数有:C、kernel、degree、gamma、coef0。

SVM如何处理多分类问题?

一般有两种做法:一种是直接法,直接在目标函数上修改,将多个分类面的参数求解合并到一个最优化问题里面。看似简单但是计算量却非常的大。

另外一种做法是间接法:对训练器进行组合。其中比较典型的有一对一,和一对多

一对多,就是对每个类都训练出一个分类器,由svm是二分类,所以将此而分类器的两类设定为目标类为一类,其余类为另外一类。这样针对k个类可以训练出k个分类器,当有一个新的样本来的时候,用这k个分类器来测试,那个分类器的概率高,那么这个样本就属于哪一类。这种方法效果不太好,bias比较高。

svm一对一法(one-vs-one),针对任意两个类训练出一个分类器,如果有k类,一共训练出C(2,k) 个分类器,这样当有一个新的样本要来的时候,用这C(2,k) 个分类器来测试,每当被判定属于某一类的时候,该类就加一,最后票数最多的类别被认定为该样本的类。

 

参考资料:

李航 《统计学习方法》(强烈推荐)

周志华 《机器学习》

部分资料整理于网上。

支持向量机: Kernel  http://blog.pluskid.org/?p=685&cpage=1

 

1、L1范式和L2方式的区别

(1)L1范式是对应参数向量绝对值之和

(2)L1范式具有稀疏性

(3)L1范式可以用来作为特征选择,并且可解释性较强(这里的原理是在实际Loss function中都需要求最小值,根据L1的定义可知L1最小值只有0,故可以通过这种方式来进行特征选择)

(4)L2范式是对应参数向量的平方和,再求平方根

(5)L2范式是为了防止机器学习的过拟合,提升模型的泛化能力

2、优化算法及其优缺点

温馨提示:在回答面试官的问题的时候,往往将问题往大的方面去回答,这样不会陷于小的技术上死磕,最后很容易把自己嗑死了。

(1)随即梯度下降

优点:可以一定程度上解决局部最优解的问题

缺点:收敛速度较慢

(2)批量梯度下降

优点:容易陷入局部最优解

缺点:收敛速度较快

(3)mini_batch梯度下降

综合随即梯度下降和批量梯度下降的优缺点,提取的一个中和的方法。

(4)牛顿法

牛顿法在迭代的时候,需要计算Hessian矩阵,当维度较高的时候,计算Hessian矩阵比较困难。

(5)拟牛顿法

拟牛顿法是为了改进牛顿法在迭代过程中,计算Hessian矩阵而提取的算法,它采用的方式是通过逼近Hessian的方式来进行求解。

(6)共轭梯度

(7)启发式的优化算法

启发式的优化算法有遗传算法,粒子群算法等。这类算法的主要思想就是设定一个目标函数,每次迭代根据相应的策略优化种群。直到满足什么样的条件为止。

3、RF与GBDT之间的区别

(1)相同点

  • 都是由多棵树组成
  • 最终的结果都是由多棵树一起决定

(2)不同点

  • 组成随机森林的树可以分类树也可以是回归树,而GBDT只由回归树组成
  • 组成随机森林的树可以并行生成,而GBDT是串行生成
  • 随机森林的结果是多数表决表决的,而GBDT则是多棵树累加之和
  • 随机森林对异常值不敏感,而GBDT对异常值比较敏感
  • 随机森林是通过减少模型的方差来提高性能,而GBDT是减少模型的偏差来提高性能的
  • 随机森林不需要进行数据预处理,即特征归一化。而GBDT则需要进行特征归一化

(3)RF:

优点:

  • 易于理解,易于可视化
  • 不需要太多的数据预处理,即数据归一化
  • 不易过拟合
  • 易于并行化

缺点:

  • 不适合小样本数据,只适合大样本数据
  • 大多数情况下,RF的精度低于GBDT
  • 适合决策边界的是矩阵,不适合对角线型

(4)GBDT

优点:

  • 精度高

缺点:

  • 参数较多,容易过拟合
  • 不易并行化

4、SVM的模型的推导

5、SVM与树模型之间的区别

(1)SVM

  • SVM是通过核函数将样本映射到高纬空间,再通过线性的SVM方式求解分界面进行分类。
  • 对缺失值比较敏感
  • 可以解决高纬度的问题
  • 可以避免局部极小值的问题
  • 可以解决小样本机器学习的问题

(2)树模型

  • 可以解决大样本的问题
  • 易于理解和解释
  • 会陷入局部最优解
  • 易过拟合

6、梯度消失和梯度膨胀

(1)梯度消失:

  • 根据链式法则,如果每一层神经元对上一层的输出的偏导乘上权重结果都小于1的话,那么即使这个结果是0.99,在经过足够多层传播之后,误差对输入层的偏导会趋于0
  • 可以采用ReLU激活函数有效的解决梯度消失的情况

(2)梯度膨胀

  • 根据链式法则,如果每一层神经元对上一层的输出的偏导乘上权重结果都大于1的话,在经过足够多层传播之后,误差对输入层的偏导会趋于无穷大
  • 可以通过激活函数来解决

7、LR的原理和Loss的推导

 

Leave a Reply

Your email address will not be published. Required fields are marked *