机器学习算法——支持向量机SVM
SVM面试常考问题
参考博客：https://blog.csdn.net/szlcw1/article/details/52259668
SVM的优缺点：
优点：
1.适合对小样本数据学习，注重样本自身信息，而非产生样本的规律。
2.网络结构简单，只需一层（线性可分情况）或最多一个隐层（线性不可分情况），隐层的节点数由所求得的支持向量个数自行决定。
3.可以根据核函数的选择自动计算重要网络参数。
4.在解决模式分类问题方面，能提供较好的泛化性能。
缺点：
1.有些参数（如控制对错分样本惩罚程度的C）不易确定。
2.虽然可以不需要知道非线性映射的具体形式，但非线性映射的核函数不易得。
3.在待分类的模式为线性不可分时，怎样控制支持向量机的选择是一个困难问题。
4.没有一个统一的解决多分类的方法。
1.SVM的原理是什么？
SVM是一种二类分类模型。它的基本模型是在特征空间中寻找间隔最大化的分离超平面的线性分类器。（间隔最大是它有别于感知机）
（1）当训练样本线性可分时，通过硬间隔最大化，学习一个线性分类器，即线性可分支持向量机，也称为硬间隔支持向量机；
（2）当训练数据近似线性可分时，引入松弛变量，通过软间隔最大化，学习一个线性分类器，即线性支持向量机，也称软间隔SVM；
（3）当训练数据线性不可分时，通过使用核技巧及软间隔最大化，学习非线性支持向量机。
注：以上各SVM的数学推导应该熟悉：硬间隔最大化（几何间隔）---学习的对偶问题---软间隔最大化（引入松弛变量）---非线性支持向量机（核技巧）。
2.SVM为什么采用间隔最大化？
当训练数据线性可分时，存在无穷个分离超平面可以将两类数据正确分开。
感知机利用误分类最小策略，求得分离超平面，不过此时的解有无穷多个。
线性可分支持向量机利用间隔最大化求得最优分离超平面，这时，解是唯一的。另一方面，此时的分隔超平面所产生的分类结果是最鲁棒的，对未知实例的泛化能力最强。
然后应该借此阐述，几何间隔，函数间隔，及从函数间隔—>求解最小化1/2 ||w||^2 时的w和b。即线性可分支持向量机学习算法—最大间隔法的由来。
3.为什么要将求解SVM的原始问题转换为其对偶问题？
1>、为了求解线性可分SVM的最优化问题，引入对偶问题，由于对偶问题往往更易求解（当我们寻找约束存在时的最优点的时候，约束的存在虽然减小了需要搜寻的范围，但是却使问题变得更加复杂。为了使问题变得易于处理，我们的方法是把目标函数和约束全部融入一个新的函数，即拉格朗日函数，再通过这个函数来寻找最优点。）
2>、自然引入核函数，进而推广到非线性分类问题。
为什么要转为对偶问题？（阿里面试）
(a) 目前处理的模型严重依赖于数据集的维度d，如果维度d太高就会严重提升运算时间；
(b) 对偶问题事实上把SVM从依赖d个维度转变到依赖N个数据点，考虑到在最后计算时只有支持向量才有意义，所以这个计算量实际上比N小很多。
4.为什么SVM要引入核函数？
当样本在原始空间线性不可分时，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。
引入映射后的对偶问题：
在学习预测中，只定义核函数K(x,y)，而不是显式的定义映射函数ϕ。因为特征空间维数可能很高，甚至可能是无穷维，因此直接计算ϕ(x)·ϕ(y)是比较困难的。相反，直接计算K(x,y)比较容易（即直接在原来的低维空间中进行计算，而不需要显式地写出映射后的结果）。
核函数的定义：K(x,y)=<ϕ(x),ϕ(y)>，即在特征空间的内积等于它们在原始样本空间中通过核函数K计算的结果。
除了 SVM 之外，任何将计算表示为数据点的内积的方法，都可以使用核方法进行非线性扩展。
5.svm RBF核函数的具体公式？
Gauss径向基函数则是局部性强的核函数，其外推能力随着参数σ的增大而减弱。
这个核会将原始空间映射为无穷维空间。不过，如果 σ 选得很大的话，高次特征上的权重实际上衰减得非常快，所以实际上（数值上近似一下）相当于一个低维的子空间；反过来，如果 σ 选得很小，则可以将任意的数据映射为线性可分——当然，这并不一定是好事，因为随之而来的可能是非常严重的过拟合问题。不过，总的来说，通过调控参数σ ，高斯核实际上具有相当高的灵活性，也是使用最广泛的核函数之一。
6.为什么SVM对缺失数据敏感？
这里说的缺失数据是指缺失某些特征数据，向量数据不完整。SVM没有处理缺失值的策略（决策树有）。而SVM希望样本在特征空间中线性可分，所以特征空间的好坏对SVM的性能很重要。缺失特征数据将影响训练结果的好坏。
7.SVM是用的是哪个库？Sklearn/libsvm中的SVM都有什么参数可以调节？
用的是sklearn实现的。采用sklearn.svm.SVC设置的参数。本身这个函数也是基于libsvm实现的（PS: libsvm中的二次规划问题的解决算法是SMO）。
SVC函数的训练时间是随训练样本平方级增长，所以不适合超过10000的样本。
对于多分类问题，SVC采用的是one-vs-one投票机制，需要两两类别建立分类器，训练时间可能比较长。
sklearn.svm.SVC(C=1.0, kernel='rbf', degree=3, gamma='auto', coef0=0.0, shrinking=True, probability=False,tol=0.001, cache_size=200, class_weight=None, verbose=False, max_iter=-1, decision_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。
8.SVM如何处理多分类问题？
一般有两种做法：一种是直接法，直接在目标函数上修改，将多个分类面的参数求解合并到一个最优化问题里面。看似简单但是计算量却非常的大。
另外一种做法是间接法：对训练器进行组合。其中比较典型的有一对一，和一对多。
一对多，就是对每个类都训练出一个分类器，由svm是二分类，所以将此而分类器的两类设定为目标类为一类，其余类为另外一类。这样针对k个类可以训练出k个分类器，当有一个新的样本来的时候，用这k个分类器来测试，那个分类器的概率高，那么这个样本就属于哪一类。这种方法效果不太好，bias比较高。
svm一对一法（one-vs-one），针对任意两个类训练出一个分类器，如果有k类，一共训练出C(2,k) 个分类器，这样当有一个新的样本要来的时候，用这C(2,k) 个分类器来测试，每当被判定属于某一类的时候，该类就加一，最后票数最多的类别被认定为该样本的类。
二、
SVM推导过程点击打开链接
现在的目标就是找出分类器定义中的w和b。为此，我们必须找到具有最小间隔的数据点，而这些数据点也就是前面提到的支持向量。一旦找到具有最小间隔的数据点，我们就需要对该间隔最大化。这就可以写作：
直接求解上面的公式很难。并且到目前为止，我们知道所有数都不那么干净，不能100%线性可分。我们可以通过引入松弛变量，来允许有些数据点可以处于分割面的错误的一侧。如下面几幅图所示
εi是松弛变量，常数C代表惩罚系数，即如果某个x是属于某一类，但是它偏离了该类，跑到边界上后者其他类的地方去了，C越大表明越不想放弃这个点，边界就会缩小，错分点更少，但是过拟合情况会比较严重。
为此，我们引入拉格朗日乘子，用条件极值求解最优分界面，构造拉格朗日函数，也是之前公式(3)的对偶形式：
也就是说，只要求的拉格朗日乘子ai，我们就能得到分类边界。
三、SMO算法实现SVM（李航课本）
SMO算法是支持向量机学习的一种快速算法，其特点是不断地将原二次规划问题分解为只有两个变量的二次规划子问题，并对子问题进行解析求解，直到所有变量满足KKT条件为止。
基本思想：将大优化的问题分解成多个小优化问题，这些小问题往往比较容易求解，并且对他们进行顺序求解的结果与他们作为整体来求解的结果完全一致。
过程：
常见问题：
四、总结：
支持向量机的基本思想可以概括为，首先通过非线性变换将输入空间变换到一个高维的空间，然后在这个新的空间求最优分类面即最大间隔分类面，而这种非线性变换是通过定义适当的内积核函数来实现的。SVM实际上是根据统计学习理论依照结构风险最小化的原则提出的，要求实现两个目的：
1）两类问题能够分开（经验风险最小）
2）margin最大化（风险上界最小）既是在保证风险最小的子集中选择经验风险最小的函数。
支持向量机面试必考：点击打开链接