参考：
http://www.cnblogs.com/CheeseZH/p/5265959.html
http://blog.sina.com.cn/s/blog_5eef0840010147pa.html
http://www.cppblog.com/sunrise/archive/2012/08/06/186474.html
关键词：最大间隔分类器，支持向量，svm公式推导，拉格朗日 kkt条件 对偶问题 smo算法 常用核函数 rbf核函数 01损失 hinge损失 软间隔 松弛变量 多分类 libsvm参数
svm公式推导
原问题：
通过拉格朗日对偶性（Lagrange Duality），求解与原问题等价的对偶问题（dual problem）得到原始问题的最优解。这样做的优点在于：一者对偶问题往往更容易求解；二者可以自然的引入核函数，进而推广到非线性分类问题。
然后令
目标函数变成了：
这里用表示这个问题的最优值，且和最初的问题是等价的。如果直接求解，那么一上来便得面对w和b两个参数，而又是不等式约束，这个求解过程不好做。不妨把最小和最大的位置交换一下，变成：
交换以后的新问题是原始问题的对偶问题，这个新问题的最优值用来表示。而且有≤，在满足某些条件的情况下，这两者相等，这个时候就可以通过求解对偶问题来间接地求解原始问题。
换言之，之所以从minmax的原始问题，转化为maxmin的对偶问题，一者因为是的近似解，二者，转化为对偶问题后，更容易求解。
（1）、首先固定，要让 L 关于 w 和 b 最小化，我们分别对w，b求偏导数，即令 ∂L/∂w 和 ∂L/∂b 等于零（对w求导结果的解释请看本文评论下第45楼回复）：
将以上结果代入之前的L ：
得到：
其具体推导过程是比较复杂的，如下图所示：
最后，得到：
从上面的最后一个式子，我们可以看出，此时的拉格朗日函数只包含了一个变量，那就是（求出了便能求出w，和b，由此可见，上文第1.2节提出来的核心问题：分类函数也就可以轻而易举的求出来了）。
（2）、求对的极大，即是关于对偶问题的最优化问题。经过上面第一个步骤的求w和b，得到的拉格朗日函数式子已经没有了变量w，b，只有。从上面的式子得到：
这样， 求出了 ，根据， 即可求出w， 然后通过， 即可求出b， 最终得出分离超平面和分类决策函数。（3）在求得L(w, b, a) 关于 w 和 b 最小化，以及对的极大之后，最后一步则可以利用SMO算法求解对偶问题中的拉格朗日乘子。
上述式子要解决的是在参数 上求最大值W的问题，至于 和 都是已知数 。通过SMO算法求解。见另一篇文章。函数间隔 几何间隔
定义函数间隔（用 表示）为：
超平面(w, b)关于训练数据集T的函数间隔： = mini (i=1，...n)
几何间隔从上述函数间隔和几何间隔的定义可以看出：几何间隔就是函数间隔除以||w||，而且函数间隔y*(wx+b) = y*f(x)实际上就是|f(x)|，只是人为定义的一个间隔度量，而几何间隔|f(x)|/||w||才是直观上的点到超平面的距离。函数间隔会随着w和b的缩放而缩放，但是对于算法的参数选取没有意义。几何间隔不会随着w和b的缩放而缩放。
支持向量
虚线间隔边界上的点则是支持向量。由于这些支持向量刚好在虚线间隔边界上，所以它们满足。，而对于所有不是支持向量的点，则显然有。
常用核函数
计算两个向量在隐式映射过后的空间中的内积的函数叫做核函数 (Kernel Function)
在线性不可分的情况下，支持向量机直接在原来的低维空间中完成计算，然后通过核函数将输入空间映射到高维特征空间，最终在高维特征空间中构造出最优分离超平面，从而把平面上本身不好分的非线性数据分开。
================================
径向基函数（Radical Basis Function，RBF）方法是Powell在1985年提出的。所谓径向基函数，其实就是某种沿径向对称的标量函数。通常定义为空间中任一点x到某一中心c之间欧氏距离的单调函数，可记作k(||x-c||)，其作用往往是局部的，即当x远离c时函数取值很小。例如高斯径向基函数：
当年径向基函数的诞生主要是为了解决多变量插值的问题。可以看下面的图。具体的话是先在每个样本上面放一个基函数，图中每个蓝色的点是一个样本，然后中间那个图中绿色虚线对应的，就表示的是每个训练样本对应一个高斯函数（高斯函数中心就是样本点）。然后假设真实的拟合这些训练数据的曲线是蓝色的那根（最右边的图），如果我们有一个新的数据x1，我们想知道它对应的f(x1)是多少，也就是a点的纵坐标是多少。那么由图可以看到，a点的纵坐标等于b点的纵坐标加上c点的纵坐标。而b的纵坐标是第一个样本点的高斯函数的值乘以一个大点权值得到的，c的纵坐标是第二个样本点的高斯函数的值乘以另一个小点的权值得到。而其他样本点的权值全是0，因为我们要插值的点x1在第一和第二个样本点之间，远离其他的样本点，那么插值影响最大的就是离得近的点，离的远的就没什么贡献了。所以x1点的函数值由附近的b和c两个点就可以确定了。拓展到任意的新的x，这些红色的高斯函数乘以一个权值后再在对应的x地方加起来，就可以完美的拟合真实的函数曲线了。
===================================================
在我的工作中，最常用的是Linear核与RBF核。 1. Linear核：主要用于线性可分的情形。参数少，速度快，对于一般数据，分类效果已经很理想了。 2. RBF核：主要用于线性不可分的情形。参数多，分类结果非常依赖于参数。有很多人是通过训练数据的交叉验证来寻找合适的参数，不过这个过程比较耗时。我个人的体会是：使用libsvm，默认参数，RBF核比Linear核效果稍差。通过进行大量参数的尝试，一般能找到比linear核更好的效果。 至于到底该采用哪种核，要根据具体问题，有的数据是线性可分的，有的不可分，需要多尝试不同核不同参数。如果特征的提取的好，包含的信息量足够大，很多问题都是线性可分的。当然，如果有足够的时间去寻找RBF核参数，应该能达到更好的效果。 ========================================= SVM关键是选取核函数的类型，主要有线性内核，多项式内核，径向基内核（RBF），sigmoid核。 这些函数中应用最广的应该就是RBF核了，无论是小样本还是大样本，高维还是低维等情况，RBF核函数均适用，它相比其他的函数有一下优点： 1）RBF核函数可以将一个样本映射到一个更高维的空间，而且线性核函数是RBF的一个特例，也就是说如果考虑使用RBF，那么就没有必要考虑线性核函数了。 2）与多项式核函数相比，RBF需要确定的参数要少，核函数参数的多少直接影响函数的复杂程度。另外，当多项式的阶数比较高时，核矩阵的元素值将趋于无穷大或无穷小，而RBF则在上，会减少数值的计算困难。 3）对于某些参数，RBF和sigmoid具有相似的性能。 ========================================= 一般用线性核和高斯核，也就是Linear核与RBF核 需要注意的是需要对数据归一化处理，很多使用者忘了这个小细节 然后一般情况下RBF效果是不会差于Linear 但是时间上RBF会耗费更多，其他同学也解释过了 下面是吴恩达的见解： 1. 如果Feature的数量很大，跟样本数量差不多，这时候选用LR或者是Linear Kernel的SVM 2. 如果Feature的数量比较小，样本数量一般，不算大也不算小，选用SVM+Gaussian Kernel 3. 如果Feature的数量比较小，而样本数量很多，需要手工添加一些feature变成第一种情况 软间隔与正则化 正则化指的是加号前的那项 损失函数指的是加号后的那项C.在不能线性可分的情况下，允许离群点存在。如果这时你希望分错的距离越少越好，就增大C，相当于提升了加号后式子的权重，减弱了加号前式子的权重，从而学出来的模型分错的点的距离会小，当C无穷大时，相当于没有错分的，也就是硬间隔。 损失函数 实际使用时，0-1损失函数非凸、非连续，性质不好，故使用其它“替代损失”。 误分次数 R=max ||xi||，即R是所有样本中向量长度最长的值（也就是说代表样本的分布有多么广），函数间隔δ=y(wx+b)。这个误分次数一定程度上代表分类器的误差 libsvm与liblinear（参考：http://www.aichengxu.com/other/6931652.htm）
早期的机器学习分类算法可以追溯到Perception（感知机）。Perception的基本思想和Logistic Regression类似，只不过是用在线学习的方法训练出一个线性分类器。引入了Hidden Layer （隐含层），出现了Multi-Layer Neural Networks（多层神经网络），模型的表达能力大大增强，可以训练出各种复杂的分类器。然而神经网络的致命弱点是，训练样本量较少时非常容易过拟合，而这时SVM应运而生，完美的解决了这个问题。一方面，SVM的目标函数是一个凸函数，可以保证得到问题的全局最优解，避免了神经网络优化频繁陷入局部最优的困扰。另一方面，SVM的背后有一套结构化风险最小化的理论，给定了训练样本和训练参数，是可以从理论上计算出模型在真实数据上误差的bounds。此外，SVM能使用线性和非线性核函数来训练，能够处理线性和非线性分类问题，可以得到与神经网络方法大体相当的分类能力，从而适应不同的问题。 SVM也存在局限性。一方面，基于核函数的SVM求解复杂，需要存储一个稠密的样本间Kernel矩阵，当样本量很大时，存储量相当可观。而到目前为止，一直有效的并行SVM训练方法能够从根本上提升SVM模型的训练。SVM过于依赖核函数，但是不同领域知识与业务场景，仅仅依靠常见的几种kernel函数并不能解决问题，其灵活性不如人工的特征构造方法。另一方面，很多机器学习方法以从大量的样本中进行特征的自动学习，此时只需要使用简单的线性分类器，这时的主要矛盾变成了分类器必须有能力处理足够大量的样本，于是LIBLINEAR应运而生。 LIBLINEAR在保持基本接口和调用方式一致的情况下，采用了新的训练算法，支持了线性SVM和Logistic Regression的训练。很多实际的例子证明，人工构造特征+线性模型的方式可以达到甚至超过kernel SVM的表现，LIBSVM和LIBLINEAR的作者林智仁老师在后来的很多报告中，都在大力的推广LIBLINEAR，并且同时大大降低训练的时间和消耗的资源。 最近几年，人工构造特征+线性分类器的方式在很多问题上又遇到了瓶颈。与此同时，一方面可供使用数据量更大了，另一方面，计算机的计算能力又有了突飞猛进的增长，神经网络又重新焕发了生机。与SVM相比，神经网络模型的优势在于可以通过控制模型的层数和每一层函数的类型，设计出各种灵活的分类器。同时神经网络的优化算法比kernel SVM更适合并行化。当时影响神经网络发展的主要问题是计算资源的限制和样本量少引起的过拟合。但现在这两项限制都几乎不存在了。基于GPU的并行计算技术现在已经比较成熟，可以支持高速的并行计算。 具体到LIBSVM和LIBLINEAR，我尝试总结下面几个原则：
凡是确定使用线性分类器的场景，一定使用LIBLINEAR而不是LIBSVM。如果样本量较大，比如达到10万以上的规模，这时LIBSVM已经很难处理了。如果线性分类器的效果实在不好，只能采用人工构造特征+LIBLINEAR的方式，或者采用其他的分类器，如神经网络，随机森林等。对于高维稀疏数据，典型的如文本的向量空间表示，一般都采用线性的分类器。对于样本量和维度都不算太大的问题，且没有对预测的效率有过分的需求，都可以用LIBSVM尝试一下kernel SVM的分类器，很多情况下用kernel SVM比直接用liblinear SVM还是能达到更高的精度。SVM实现多分类
http://blog.sina.com.cn/s/blog_5eef0840010147pa.html
SVM算法最初是为二值分类问题设计的，当处理多类问题时，就需要构造合适的多类分类器。目前，构造SVM多类分类器的方法主要有两类：
一类是直接法，直接在目标函数上进行修改，将多个分类面的参数求解合并到一个最优化问题中，通过求解该最优化问题“一次性”实现多类分类。
这种方法看似简单，但其计算复杂度比较高，实现起来比较困难，只适合用于小型问题中；
另一类是间接法，主要是通过组合多个二分类器来实现多分类器的构造，常见的方法有one-against-one和one-against-all两种。 一对多法（one-versus-rest,简称OVR SVMs）
训练时依次把某个类别的样本归为一类,其他剩余的样本归为另一类，这样k个类别的样本就构造出了k个SVM。分类时将未知样本分类为具有最大分类函数值的那类。
假如我有四类要划分（也就是4个Label），他们是A、B、C、D。
于是我在抽取训练集的时候，分别抽取
（1）A所对应的向量作为正集，B，C，D所对应的向量作为负集；
（2）B所对应的向量作为正集，A，C，D所对应的向量作为负集；
（3）C所对应的向量作为正集，A，B，D所对应的向量作为负集；
（4）D所对应的向量作为正集，A，B，C所对应的向量作为负集；
使用这四个训练集分别进行训练，然后的得到四个训练结果文件。
在测试的时候，把对应的测试向量分别利用这四个训练结果文件进行测试。
最后每个测试都有一个结果f1(x),f2(x),f3(x),f4(x)。
于是最终的结果便是这四个值中最大的一个作为分类结果。
评价：
这种方法有种缺陷,因为训练集是1:M,这种情况下存在biased.因而不是很实用。可以在抽取数据集的时候，从完整的负集中再抽取三分之一作为训练负集。
一对一法（one-versus-one,简称OVO SVMs或者pairwise）
其做法是在任意两类样本之间设计一个SVM，因此k个类别的样本就需要设计k(k-1)/2个SVM。
当对一个未知样本进行分类时，最后得票最多的类别即为该未知样本的类别。
Libsvm中的多类分类就是根据这个方法实现的。
假设有四类A,B,C,D四类。在训练的时候我选择A,B; A,C; A,D; B,C; B,D;C,D所对应的向量作为训练集，然后得到六个训练结果，在测试的时候，把对应的向量分别对六个结果进行测试，然后采取投票形式，最后得到一组结果。
投票是这样的： A=B=C=D=0; (A,B)-classifier 如果是A win,则A=A+1;otherwise,B=B+1; (A,C)-classifier 如果是A win,则A=A+1;otherwise, C=C+1; ... (C,D)-classifier 如果是A win,则C=C+1;otherwise,D=D+1; The decision is the Max(A,B,C,D)
评价：这种方法虽然好,但是当类别很多的时候,model的个数是n*(n-1)/2,代价还是相当大的。
决策树方法 决策树的基本思想是从根节点开始，采用某种方法将该节点所包含的类别划分为两个子类，然后再对两个子类进一步划分，如此循环，直到子类中只包含一个类别为止，这样，就得到了一个倒立的二叉树。最后，在二叉树各决策节点训练支持向量机分类器，实现对识别样本的分类。决策树支持向量机多分类方法有很多种，不同方法的主要区别在于设计树结构的方法不同。
完全二叉树结构分类时使用的平均分类器数目为log2k，偏二叉树使用的平均分类器数为(k+1)／2-1／k，具有其他层次结构的二叉树使用的分类器平均值介于二者之间。完全二叉树分类时所需要的分类器数目最少，因此具有较少支持向量的完全二叉树的分类器速度也是较快的。
DAG方法（有向无环图） DAG-SvMS是由PIatt提出的决策导向的循环图DAG导出的，是针对“一对一"SvMS存在误分，拒分现象提出的。这种方法的训练过程类似于“一对一”方法，k类别问题需要求解k(k-1)／2个支持向量机分类器，这些分类器构成一个有向无环图。该有向无环图中含有k(k-1)／2个内部节点和k个叶结点，每个节点对应一个二类分类器。
DAG-SVMS简单易行，只需要使用k一1个决策函数即可得出结果，较“一对一"方法提高了测试速度，而且不存在误分、拒分区域；另外，由于其特殊的结构，故有一定的容错性，分类精度较一般的二叉树方法高。然而，由于存在自上而下的“误差积累”现象是层次结构固有弊端，故DAG-SVMS也逃脱不掉。即如果在某个结点上发生了分类错误，则会把分类错误延续到该结点的后续结点上.
纠错输出编码法（ECOC） 对于K类分类问题，可以根据不同方法构造一系列的两类分类问题，对于每个两类分类问题可以建立一决策函数。共得到L个决策函数，如果这些决策函数完全正确，K类中的每一类都对应一个元素为-l或+1的长度为L的数列，按照K类中的第一类、第二类，...，第K类的顺序，把这些数列排列起来，便可得到一个K行L列的编码矩阵，若要判断一个测试输入点的归属，首先用所得到的L个决策函数，得到一个元素为-l或l的长度为L的数列，然后将此数列与先前得到矩阵比较，相应于矩阵中有一行且仅有一行向与此数列相同，这个行数就是输入点的归属类；若矩阵中没有一行与该数列相同，可以通过计算汉明距离找出最近的一行，改行对应的类别即为该点的类别。
sklearn.svm.SVC 参数说明
经常用到sklearn中的SVC函数，这里把文档中的参数翻译了一些，以备不时之需。
本身这个函数也是基于libsvm实现的，所以在参数设置上有很多相似的地方。（PS: libsvm中的二次规划问题的解决算法是SMO）。 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。
