对于多分类问题以及核函数的选取，以下经验规则可以借鉴： 

• 如果如果特征数远远大于样本数的情况下,使用线性核就可以了.
• 如果特征数和样本数都很大,例如文档分类,一般使用线性核, LIBLINEAR比LIBSVM速度要快很多.
• 如果特征数远小于样本数,这种情况一般使用RBF.但是如果一定要用线性核,则选择LIBLINEAR较好,而且使用-s 2选项

 

 

原文：

http://orangeprince.info/2014/11/23/libsvm-liblinear-2/

http://orangeprince.info/2014/11/22/libsvm-liblinear-1/

LIBSVM与LIBLINEAR（一）

 

 

在过去的十几年里，支持向量机（Support Vector Machines）应该算得上是机器学习领域影响力最大的算法了。而在SVM算法的各种实现工具中，由国立台湾大学林智仁老师开发的工具包LIBSVM，又无疑是影响力最大的。2011年LIBSVM的系统介绍论文“LIBSVM: a library for support vector machines”发表在了期刊ACM TIST(ACM Transactions on Intelligent Systems and Technology)上。2011年的时候，这个期刊的影响因子还不到1，但到了2014年，它的影响因子居然达到了9.39，把TPAMI都甩出了一大截。这其中贡献最大的当然是关于LIBSVM的这篇论文，在google scholar上，这篇文章的引用量居然已经接近20000，着实吓人。仔细想来其实也并不奇怪，各种研究工作，只要涉及到分类，大部分都会用到SVM算法或者与SVM的算法进行对比，而此时LIBSVM往往是首选工具。其实不但是学术界，在工业界LIBSVM也有非常广泛的应用。这一方面得益于算法实现的稳定与高效，另一方面也是因为LIBSVM提供了丰富的接口与灵活的使用方式。一些非常有名的机器学习工具，如基于java的Weka和基于python的scikit-learn，其提供的SVM算法在底层也是基于LIBSVM的实现。

几年前参加过一个机器学习的学习班，主讲人是CMU的Eric Xing老师。在提问环节，大家都在讨论一些高深的理论问题，突然有一个女生举手提问主讲人如果要用SVM的话有什么工具推荐使用。这个问题在当时的场景似乎有点不合时宜，Eric Xing老师回答说他们CMU从来不用别人的库，所有的算法代码都是自己实现的云云。后来那次讲座上其他的东西我都不太记得了，印象最深的就变成了这个问答。现在想来，如果从算法学习角度，自己实现这些算法对于理论的理解和工程能力的提升都是大有好处。但是对于绝大部分人来说，自己动手实现的SVM算法在效率和扩展性上，还是会和LIBSVM的算法实现存在不小的差距，毕竟人家的程序是千锤百炼中产生的。如果单纯为了使用的话，一个大家都认可的好工具绝不失为一个很好地选择。但是，有一个好的工具并不等于我们可以对算法与实现一无所知而把所有的事情都交给工具。相反，如果我们能够很好地了解算法与实现中的一些背景知识，可以更好地使用这些工具。此外，LIBSVM与他的姊妹工具LIBLINEAR提供了丰富的优化与参数选项，通过选择适当的方法，也可以大大提高我们的工作效率。因此，下面总结一些在我之前的工作中遇到的一些与LIBSVM和LIBLINEAR相关的重要问题，希望能够为读者对这些工具的使用有所帮助。

LIBSVM与LIBLINEAR的关系

这是很多刚开始使用SVM的人容易弄混淆的问题。简单来说，LIBSVM是一套完整的SVM模型实现。用户可以在LIBSVM中使用和核函数来训练非线性的分类器，当然也能使用更基础的线性SVM。而LIBLINEAR是一个针对线性分类场景而设计的工具包，除了支持线性的SVM外，还可以支持线性的Logistic Regression等模型，但是无法通过定义核函数方式实现非线性的分类器。由于支持核函数的扩展，LIBSVM理论上具有比LIBLINEAR更强的分类能力，能够处理更为复杂的问题。但是，很多人因此就只使用LIBSVM，甚至最简单的线性分类器都是用LIBSVM来训练和预测，这也是不可取的。因为LIBLINEAR设计的初衷就是为了提高线性分类的效率，其优化算法与LIBSVM中的优化算法有着根本的区别。虽然在进行线性分类时LIBSVM和LIBLINEAR都可以达到类似的结果，但是LIBLINEAR无论是在训练上还是在预测上，都比LIBSVM高效得多。此外，受限于算法，LIBSVM往往在样本量过万之后速度就比较慢了，如果样本量再上升一个数量级，那么通常的机器已经无法处理了。但使用LIBLINEAR，则完全不需要有这方面的担忧，即便百万千万级别的数据，LIBLINEAR也可以轻松搞定，因为LIBLINEAR本身就是为了解决较大规模样本的模型训练而设计的。

虽然搞清楚了两者主要的区别，但我在刚刚接触这些工具时，一直很疑惑为什么两个紧密相关算法，却演化出两个彼此独立的工具包。而让我更加不解的是，LIBSVM早在2000年就已经发布了，而LIBLINEAR直到2007年才发布第一个版本。根据常识，应该是先有一个简单的工具，然后再逐渐完善，但是功能更加强大的LIBSVM却早于LIBLINEAR很久发布。要回答这个问题，还得从机器学习以及SVM的历史说起。

早期的机器学习分类算法可以追溯到Perception（感知机）。Perception的基本思想和Logistic Regression类似，只不过是用在线学习的方法训练出一个线性分类器。在 中可以看到很多80年代到90年代初期用于机器学习研究的数据。可以看出，这其中的很多问题都非常复杂，比如图像或者语音的识别。但是另一方面，受限于当时获取数据与计算存储能力的限制，这些数据集的规模通常非常的小，有的只有几千甚至几百个样本。对于这样相对复杂的问题，可以想到将特征直接用简单的线性分类器进行分类，肯定不会取得太好的效果。这个时候，机器学习领域一个里程碑Multi-Layer Neural Networks（多层神经网络）出现了。多层神经网络引入了Hidden Layer （隐含层），模型的表达能力大大增强，可以训练出各种复杂的分类器。然而神经网络也有一个致命的弱点，由于模型本身的局限性，非常容易过拟合，尤其是在训练样本量较少的情况下。而这时SVM应运而生，完美的解决了这个问题。一方面，SVM的目标函数是一个凸函数，可以保证得到问题的全局最优解，避免了神经网络优化频繁陷入局部最优的困扰。另一方面，SVM的背后有一套结构化风险最小化的理论，给定了训练样本和训练参数，是可以从理论上计算出模型在真实数据上误差的bounds。在SVM中，通过对参数的调节和样本量的选择，可以在模型方差与训练误差之间方便的做出权衡。此外，SVM可以定义不同的核函数来构造非线性分类器，可以得到与神经网络方法大体相当的分类能力，从而适应不同的问题。因此，在上个世纪末到这个是基础，SVM横扫了各种分类的应用场景，成为了当时最炙手可热的机器学习算法。

然而，SVM也存在局限性。首先，基于核函数的SVM求解相对比较复杂，需要存储一个稠密的样本间的Kernel矩阵，当样本量很大时，存储量相当可观。而到目前为止，一直没有一个非常有效的并行SVM训练方法能够从根本上提升SVM模型的训练。在十几年前，样本量最多只是上万级别的时候，这个问题并不显得重要。但是在十多年后，随着互联网的爆炸式发展，随便一个模型的训练样本量都可能数以亿计，这时SVM在大数据训练上的不足就凸显无疑了。SVM之所以效果好，主要是得益于非线性核函数的引入。但是新的问题不断出现，而这些问题又涉及到的不同领域知识与业务场景，很多时候仅仅依靠常见的几种kernel函数并不能解决问题。但是SVM本身过分依赖于核函数，而核函数又存在着很多的限制，其灵活性当然不如人工的特征构造方法。另一方面，随着数据量的不断增加，即使这些样不能直接被标注用于模型的训练，但是可以很多机器学习方法可以从大量的样本中进行特征的自动学习。比如早年的流形学习，还有文本上的主题模型，图像上的稀疏编码与字典学习等。通过这些非线性的方法学习的样本特征，往往已经是样本的高层语义表达，有数据充足的情况下，只需要使用较为简单的线性分类器，就可以达到比较好的效果。这时的主要矛盾变成了分类器必须有能力处理足够大量的样本，而在方法上，可以是简单地现行方法。也就是在这个时候，LIBLINEAR应运而生。

在LIBSVM诞生的时代，SVM的核函数带来的非线性模型是SVM的主要优势之一，且当时的样本量还不是瓶颈。因此LIBSVM的整体框架都是针对训练kernel SVM模型来训练的。但是如果只是需要训练一个线性的SVM模型，那么算法可以简单的多，也可以高效的多。因此LIBLINEAR在保持基本接口和调用方式一致的情况下，采用了新的训练算法，支持了线性SVM和Logistic Regression的训练。LIBSVM和LIBLINEAR的作者林智仁老师在后来的很多演讲中，都在大力的推广LIBLINEAR，并且给出了很多实际的例子证明，人工构造特征+线性模型的方式可以达到甚至超过kernel SVM的表现，同时大大降低训练的时间和消耗的资源。

其实就在最近几年，情况又有了新的变化。人工构造特征+线性分类器的方式在很多问题上又遇到了瓶颈。与此同时，一方面可供使用数据量更大了，另一方面，计算机的计算能力又有了突飞猛进的增长。此时曾经被SVM狠狠压在地上的神经网络又重新焕发了生机。与SVM相比，神经网络模型的优势在于可以通过控制模型的层数和每一层函数的类型，设计出各种灵活的分类器。同时神经网络的优化算法比kernel SVM更适合并行化。当时影响神经网络发展的主要问题是计算资源的限制和样本量少引起的过拟合。但现在这两项限制都几乎不存在了。基于GPU的并行计算技术现在已经比较成熟，可以支持高速的并行计算。而造成过拟合的原因从根本上说，是因为训练样本的比真实样本数少的太多，不能够反应真实的数据情况。但是如果把我们拥有的所有样本都作为训练样本，其实机会已经就是真实的样本集了，因此过拟合的事实基础就不存在了。虽然神经网络在理论上还有缺陷，但是通过计算能力和数据的增加，这些缺陷已经不是问题。正是因为上面的原因，这些年机器学习的热点又重新回到了神经网络。

1995年，SVM的发明人Vapnik和他在Bell实验室的老大Larry Jackel打过两个赌，而见证人是当时也在Bell而最近因为Deep Learning而声名鹊起的Yann Lecun。赌局的具体内容见下图：不管他们输赢与否，我们都能感觉到这门学科的变化之快。在神经网络大行其道的时候，很难想到半路杀出一个SVM将神经网络算法杀了一个体无完肤。而在SVM一统天下的时候，大部分人也不会相信神经网路居然还能最后等到逆袭的那一天。

仔细看每一次算法的革新，其实真正的推动力都是具体的问题需求与当时的技术条件。因此，脱离具体的应用场景去单纯比较算法的优劣并没有太多意义。对于使用者来说，最适合这个问题场景的算法就是最好的算法。具体到LIBSVM和LIBLINEAR，我尝试总结下面几个原则：

• • 凡是确定使用线性分类器的场景，一定使用LIBLINEAR而不是LIBSVM
  • 如果样本量较大，比如达到10万以上的规模，这时LIBSVM已经很难处理了。如果线性分类器的效果实在不好，只能采用人工构造特征+LIBLINEAR的方式，或者采用其他的分类器，如神经网络，随机森林等。
  • 对于高维稀疏数据，典型的如文本的向量空间表示，一般都采用线性的分类器。
  • 对于样本量和维度都不算太大的问题，且没有对预测的效率有过分的需求，都可以用LIBSVM尝试一下kernel SVM的分类器，很多情况下用kernel SVM比直接用libear SVM还是能达到更高的精度。
    • LIBSVM与LIBLINEAR（二）

    •  

      模型与优化

      LIBSVM和LIBLINEAR都提供了多种不同的模型供使用者选择，不同的模型有各自适用的场景。下面分别介绍LIBSVM和LIBLINEAR所提供的各种模型。

      LIBSVM

      下面是LIBSVM帮助内容提供的介绍，给出了LIBSVM支持的5种模型。其中模型0和1对应的都是SVM的分类模型，2对应的是one-class分类器，也就是只需要标注一个标签，模型3和4对应的是SVM的回归模型。

      1 -s svm_type : set type of SVM (default 0) 2 0 -- C-SVC (multi-class classification) 3 1 -- nu-SVC (multi-class classification) 4 2 -- one-class SVM 5 3 -- epsilon-SVR (regression) 6 4 -- nu-SVR (regression)

      首先来看最基础的C-SVC模型。SVM可以写成如下的优化目标函数（这里不详细介绍推导算法了）：

      argminw,b,ξ subjectto 12wTw+C∑i=1lξiyi(wT?(xi)?b)≥1?ξi,ξi≤0,i=1,…,l

      当模型使用linear kernel，也就是?(x)=x时，上面的问题一个标准的二次凸优化问题，可以比较方便的对每一个变量进行求导。求解这样的问题是有很多快速的优化方法的，这些方法在LIBLINEAR中都有应用。但是如果是引入kernel的SVM，情况就大不一样了。因为很多时候我们既不能得到核函数的具体形式，又无法得到特征在核空间中新的表达。这个时候，之前用在线性SVM上的的求解思路就完全不work了。为了解决这个问题，就必须采用标准的SVM求解思路，首先把原问题转化为对偶问题，得到下面的目标函数（具体过程可以参考任何介绍SVM的资料）：

      argminα subjectto f(α)=12αTQα?eTα0≤αi≤C,i=1,…,l,yTα=0

      通过对偶变化，上面的目标函数变成了一个关于变量α的二次型。很显然，上面目标函数中最重要的常亮是矩阵Q，既训练样本的Kernel Matrix，满足Qi.j=?(xi)T?(xj)。先看好的一方面，根据核函数的定义，能够保证Q是一个正定的矩阵。也就是说，上面的目标函数还是一个凸函数，优化收敛后能保证得到的解是全局最优解， 这也是SVM的重要优势之一。但是问题也随之而来，使用常用的核函数，只要任意给出两个向量，总是能够计算出一个非0的距离。这也就意味着矩阵Q将会是一个非常稠密的矩阵，如果训练样本足够多，那么矩阵Q的存储和计算将成为很大的问题，这也是SVM的优化算法中的最大挑战。

      由于矩阵Q过大，所以想一次性优化整个α是比较困难的。所以常用的方法都是先把Q大卸八块，每次选择一部分的Q，然后update与这部分Q相关的α的值。这其中最著名的算法就是1998由John C. Platt提出的，而LIBSVM的优化过程也是基于SMO算法进行的。SMO算法的每一步迭代都选择最小的优化单元，也就是固定其他的α，只挑选两个α的值进行优化。之所以不选择一个，是因为有yTα=0的约束，至少选择两个α的坐标才有可能进行更新。本文主要目的是介绍LIBSVM，所以就不详细讨论SMO的细节了。至于LIBSVM中的具体算法实现，在中介绍的很详细，这里总结部分关键问题：

      • Working Set，也就是需要优化的α部分的选取
      • 迭代停止条件的设置
      • α的更新算法，也就是每一步子问题的求解方法
      • Shrinking，即移除一些已经满足条件的α，加快收敛速度
      • Cache，当Q矩阵过大时，需要对矩阵进行缓存。

      上面的每个问题，处理起来都不简单。作为使用者，或许也没有必要深谙里面的所有细节。我觉得最需要认识的两个问题是：1) SVM的目标函数看起来好像是一个标准的优化问题，但实际求解却要复杂得多。为了提高求解的速度，既要做算法上的优化，也需要做工程上的改进。如果只是简简单单按照教科书的方法，甚至直接调用一些优化的工具包来实现的SVM算法，最多也就算个demo。要能够真正写一个高效稳定、能处理大规模数据的SVM工具还是非常不容易的。所以用LIBSVM还是比自己实现算法要简单靠谱不少。2)SVM的求解之所以要优化，就是因为这个问题本身计算和存储比较麻烦。所以虽然做了这么多的优化，整个算法求解的效率仍然较低。所以我们在使用时还要注意各种程序的细节，提高运行的效率。另外，样本量过大时，有时候为了充分利用数据，也不得不忍痛割爱，放弃kernel的使用。

      除了标准的C-SVM，LIBSVM也提供了对其他一些SVM方法的支持。其中ν-SVM与C-SVM的算法与应用场景基本是相同的，唯一的区别是原本的参数C变成了参数ν。C-SVM中参数C调整范围在[0,+∞)，而ν-SVM中与之对应的参数ν的调整范围变成了 (0,1]。这样的设置使得ν-SVM更具解释性，有时在参数设置上也能提供一定的方便。但ν-SVM与C-SVM并不存在本质上的差别，通过参数的调节，两者可以达到完全相同的效果。所以在使用LIBSVM处理分类问题是，选择上面任何一种方法都是OK的，只需要遵循自己的习惯就好了。

      One-Class SVM也是LIBSVM所支持的一种分类方法。顾名思义，使用One Class时，只需要提供一类样本，算法会学习一个尽量小的超球面包裹所有的训练样本。One-Class SVM看起来很有诱惑力，因为我们经常会遇到有一类样本而需要学习分类器的情况。但事实上，一方面很多时候我们得到的正样本在采样过程中存在很大的偏差，导致学习出的One Class分类器不一定考虑到了所有正样本的情形；另一方面，大部分问题还是存在很多构造人工负样本的办法。根据我的经验，采用普通的SVM效果通常还是会好过One-Class SVM，而One-Class SVM在真实场景中的使用也并算不上多。因此在使用这个方法前也需要对问题进行更深入的研究。

      最后，LIBSVM也支持基于SVM的回归模型，即SVR。与分类模型类似，SVR也分为C-SVR和ν-SVR。SVR的目标函数与SVM的分类模型稍有区别。由于回归问题预测值与目标值的偏差可大可小，因此SVR使用了两个slack variable用来刻画预测的误差边界。虽然存在这样的差别，但是两者的基本思路和优化算法与还是基本一致的。

      在LIBSVM的实现中，上面五种模型，即C-SVM，ν-SVM，One-class SVM，C-SVR，ν-SVR，最终都可以转化为一个更通用的优化框架，然后用同样的策略进行求解，这也是LIBSVM所实现的主要功能。在实际使用中，最常用到的方法还是C-SVM，这是最传统的SVM分类模型。

      LIBLINEAR

      LIBLINEAR是在LIBSVM流行多年后才开发的，要解决的问题本质上也比LIBSVM更简单，其优势主要在于效率与scalablility。之所以存在这样的优势，是因为线性SVM的求解要比kernel SVM简单许多。

      还从上面的对偶问题说起，之前SVM的求解很大程度上受到yTα=0的困扰，因此每次必须选择一组 α进行优化。如果对这一约束项追根述源，可以发现这一项是通过令模型的常数项b导数为0而得到的。而在线性模型中，我们可以通过一个简单地trick，令x=[x,1]和w=[w,b]，这样，在模型中的常数项就不存在了。当然，这样的trick只能在线性模型中才适用。没有了上面的约束，优化的目标函数变成了：

      argminα subjecttof(α)=12αTQα?eTα0≤αi≤C,i=1,…,l

      这个时候，就可以每次只选择一个αi进行优化，每一轮遍历α的所有维度，多轮迭代，直至最后收敛。这样的优化算法叫做coordinate descent（坐标下降法）。利用线性函数的特殊性，直接根据α就可以计算出w的向量表示，于是大大提高了算法的效率。具体的优化算法可以参考文献 。

      换一个看问题的角度，线性SVM的目标函数可以写成下面的形式：

      argminw12wTw+C∑i=1l(max(0,1?yiwTxi))

      进一步对问题进行抽象，可以把一类分类问题写成下面的形式：

      argminwΩ(w)+C∑i=1l?(yi,wTxi)

      其中的?作为误差函数，用来度量预测值与目标值的损失。在上面的线性SVM的情形中，有

      ?(yi,wTxi)=max(0,1?yiwTxi)

      这里的?称为Hinge Loss。

      又如在Logistic Regression中，loss function ?被定义为

      ?(yi,wTxi)=log(1+e?yiwTixi)

      Ω一般被称为正则化项(Regularizer)，最常使用的就是前面出现的?2-norm，写作wTw，也可以写作∥w∥22，即向量w中所有元素的平方和。除?2-norm之外，?1-norm也是经常使用regularizer，而且会带来一些特别的效果（后面会进行讨论）。大量的监督学习模型都可以写成loss function + regularizer的形式，而参数C则控制了两者在最终损失函数中所占的比重。不同loss function与regularizer的选取以及两者之间的平衡，是机器学习的最重要主题之一。

      对于上面的问题，有很多成熟的算法可以进行模型的求解，比如最速梯度法，牛顿法等，对于样本量较大时，也可以采用随机梯度的方法进行训练。 一般来说，由于考虑了二阶导数，牛顿法本身的优化效率要高于只考虑一阶导数的最速梯度法。但由于牛顿法本身在计算量和收敛性上存在很多局限性，所以很少直接使用，而是在牛顿法思想基础上进行一定的改进。其中普遍使用的算法有BFGS和L-BFGS等。具体到liblinear软件包，作者采用的是Trust Region Newton (TRON) method对模型对传统牛顿法进行了改进，该方法被证明比L-BFGS训练更加高效。

      LIBLINEAR中实现了基于TRON方法的L-2 SVM和Logistical Regression模型训练。其中的L2-loss SVM是标准SVM的变种，loss function变成了：

      ?(yi,wTxi)=(max(0,1?yiwTxi))2

      从实际效果来说，L2-loss SVM与标准的L1-loss SVM并没有太大的区别。但是在计算上，前者的求导形式更加简单，便于梯度的计算与优化。LIBLINEAR并没有实现Trust Region Newton法的标准L1-loss SVM实现，一方面是因为直接对hinge loss求导需要分段讨论比较复杂，另一方面L2-loss SVM基本可以直接替代L1-loss SVM。不过在其他的一些软件包中，如中，则实现了L1-loss SVM的原问题求解，但使用的优化算法是L-BGFS而不是TRON。

      总结

      前面介绍了LIBSVM和LIBLINEAR的优化算法，下面简单总结一下不同算法的应用场景吧：

      • 所有线性问题都是用LIBLINEAR，而不要使用LIBSVM。
      • LIBSVM中的不同算法，如C-SVM和nu-SVM在模型和求解上并没有本质的区别，只是做了一个参数的变换，所以选择自己习惯的就好。
      • LIBLINEAR的优化算法主要分为两大类，即求解原问题(primal problem)和对偶问题(dual problem)。求解原问题使用的是TRON的优化算法，对偶问题使用的是Coordinate Descent优化算法。总的来说，两个算法的优化效率都较高，但还是有各自更加擅长的场景。对于样本量不大，但是维度特别高的场景，如文本分类，更适合对偶问题求解，因为由于样本量小，计算出来的Kernel Matrix也不大，后面的优化也比较方便。而如果求解原问题，则求导的过程中要频繁对高维的特征矩阵进行计算，如果特征比较稀疏的话，那么就会多做很多无意义的计算，影响优化的效率。相反，当样本数非常多，而特征维度不高时，如果采用求解对偶问题，则由于Kernel Matrix过大，求解并不方便。反倒是求解原问题更加容易。

      多分类问题

      LIBSVM和LIBLINEAR都支持多分类（Multi-class classification）问题。所谓多分类问题，就是说每一个样本的类别标签可以超过2个，但是最终预测的结果只能是一个类别。比如经典的手写数字识别问题，输入是一幅图像，最后输出的是0-9这十个数字中的某一个。

      LIBSVM与LIBLINEAR但实现方式却完全不同。LIBSVM采取的one vs one的策略，也就是所有的分类两两之间都要训练一个分类器。这样一来，如果存在k个class，理论上就需要训练 k(k?1)/2个分类器。实际上，libsvm在这一步也进行了一定的优化，利用已有分类的关系，减少分类器的个数。尽管如此，LIBSVM在多分类问题上还是要多次训练分类器。但是，考虑到前面说的LIBSVM的优化方法，随着样本数量的增加，训练的复杂度会非线性的增加。而通过1VS1的策略，可以保证每一个子分类问题的样本量不至于太多，其实反倒是方便了整个模型的训练。

      而LIBLINEAR则采取了另一种训练策略，即one vs all。每一个class对应一个分类器，副样本就是其他类别的所有样本。由于LIBLINEAR能够和需要处理的训练规模比LIBSVM大得多，因此这种方式要比one vs one更加高效。此外，LIBLINEAR还实现了基于Crammer and Singer方法的SVM多分类算法，在一个统一的目标函数中学习每一个class对应的分类器。

      输出文件

      一般来说，我们使用LIBLINEAR或者LIBSVM，可以直接调用系统的训练与预测函数，不需要直接去接触训练得到的模型文件。但有时候我们也可能需要在自己的平台实现预测的算法，这时候就不可避免的要对模型文件进行解析。

      由于LIBLINEAR与LIBSVM的训练模型不同，因此他们对应的模型文件格式也不同。LIBLINEAR训练结果的格式相对简单，例如：

      1 solver_type L2R_L2LOSS_SVC_DUAL  2 nr_class 3  3 label 0 1 2 4 nr_feature 5 5 bias -1 6 w 7 -0.4021097293855418 0.1002472498884907 -0.1619908595357437 8 0.008699468444669581 0.2310109611908343 -0.2295723940247394 9 -0.6814324057724231 0.4263611607497726 -0.4190714505083906 10 -0.1505088594898125 0.2709227166451816 -0.1929294695905781 11 2.14656708009991 -0.007495770268046003 -0.1880325536062815

      上面的solver_type表示求解算法，w以下表示求解得到的模型权重。其中每一列对应一个class的分类器，而每一行对应特征的一个维度。其中nr_class表示求解的个数，nr_feature表示特征的维度，bias表示模型的bias，可以人工设置权重。这里容易产生误解的是label这个字段，表示的是每一个用户训练文件中label对应w的列数。比如在上面的模型中，用户指定编号为0的分类器对应w的第一列。但是上面的对应关系并不是一定存在的，比如在二分类场景中，用将整样本标为1，负样本标为0，但在模型训练中，LIBLINEAR会按照自己的编号系统进行训练，因而有可能出现负样本在前，正样本在后的情形。这时候，就必须要根据label 1 0将LIBLIENAR内部的编号体系与真实的用户标签进行对应。当然，后来LIBLINEAR和LIBSVM做了一些优化，在二分类时，如果正负样本标签分别是-1和+1，那么可以始终保证正样本出现在w的第一列。但是这个机制也不是完全靠谱，比如说在LIBLINEAR的spark实现代码中，就没有实现这个特性，曾经把我整的很惨。因此在这里还是需要十分注意。

      LIBSVM的训练结果格式就更复杂一些，例如：

      1 kernel_type rbf  2 gamma 0.0769231  3 nr_class 3  4 total_sv 140  5 rho -1.04496 0.315784 1.03037 6 label 1 0 -1 7 nr_sv 2 2 1 8 SV 9 0 1 1:0.583333 2:-1 3:0.333333 4:-0.603774 5:1 6:-1 7:1 8:0.358779 9:-1 10:-0.483871 12:-1 13:1 10 0 0.6416468628860974 1:0.125 2:1 3:0.333333 4:-0.320755 5:-0.406393 6:1 7:1 8:0.0839695 9:1 10:-0.806452 12:-0.333333 13:0.5 11 0 1 1:0.333333 2:1 3:-1 4:-0.245283 5:-0.506849 6:-1 7:-1 8:0.129771 9:-1 10:-0.16129 12:0.333333 13:-1 12 0.2685466895842373 0 1:0.583333 2:1 3:1 4:-0.509434 5:-0.52968 6:-1 7:1 8:-0.114504 9:1 10:-0.16129 12:0.333333 13:1 13 0 1 1:0.208333 2:1 3:0.333333 4:-0.660377 5:-0.525114 6:-1 7:1 8:0.435115 9:-1 10:-0.193548 12:-0.333333 13:1

      上面参数的意义都比较直接，需要注意的是SV后面就是训练出的模型参数，以支持向量的方式进行存储。nr_sv给出了每一个支持向量所对应的模型，比如“2 2 1”就表示前两行是标签为1类的支持向量，其后面两行是标签为0类的支持向量，最后一行是标签为-1类的支持向量。而具体每一行支持向量，在上面的模型中，由于存在三类，所以每一个支持向量有可能都会存在于两个分类器中，所以前两列的数分别对应了对剩下两个分类作为支持向量时候的α值，后面才是真正的支持向量。

 

 

 

 

LIBSVM与LIBLINEAR（三）

2014-11-26

调节参数

LIBSVM和LIBLINEAR工具包都包含很多需要调节的参数，参数的调节既需要足够的耐心，也有着很多的技巧。当然，还需要对参数本身的意义和对模型的影响了如指掌。下面主要讨论一些对模型影响较大的参数

参数C

参数C是在LIBLINEAR和LIBSVM的求解中都要用到的一个参数。前面说到的各种模型，可以写成统一的形式：

 

argminwΩ(ϕ(w))+C∑i=1lℓ(yi,ϕ(w)Tϕ(xi))

 

其中右边的一项是模型的损失项，其大小表明了分类器对样本的拟合程度。而左边的一项，则是人为加上的损失，与训练样本无关，被称作正则化项(Regularizer)，反映了对训练模型额外增加的一些约束。而参数C则负责调整两者之间的权重。C越大，则要求模型能够更好地拟合训练样本数据，反之，则要求模型更多的满足正则化

项的约束。以LIBLINEAR为例，下面先讨论LIBLINEAR下ℓ2norm的情况：

 

argminw∥w∥22+C∑i=1lℓ(yi,wTxi)

 

之所以要增加正则化项，是因为在设计模型的时候，我们对于样本的质量以及模型的泛化能力没有充分的自信，认为在没有其他约束的情况下，训练得到的模型会因为过于迁就已有的样本数据而无法对新的数据达到同样的效果。在这个时候，就必须在模型中增加人类的一些经验知识。比如上面对ϕ(w)增加ℓ2norm的约束就是如此。如果上面公式中的损失函数对应一个回归问题，那么这个问题就被称作Ridge Regression，中文叫做脊回归或者岭回归。

我们可以站在不同的角度来理解ℓ2norm正则化项的意义。如果把学习分类函数中w看作是一个参数估计的问题，那么不带正则化项的目标函数对应的就是对w进行最大似然估计的问题。为了使w的估计更加接近真实的情况，我们可以根据经验对w制定一个先验分布。当我们假设w先验分布是一个多元高斯分布，且不同维度之间是没有关联的(即协方差矩阵非对角线元素为0)，而每一个维度特征的方差为某一固定制，那么推导出来的最大后验概率就是上面的带正则化项的目标函数。而C与w先验分布的方差相关。C越大，就意味着正则化的效果偏弱，w的波动范围可以更大，先验的方差也更大；而C越小，则意味着正则化的效果更强，w的波动范围变小，先验的方差也变小。通过减小C的值，可以控制w的波动不至于过大，以免受一些数据的影响，造成模型的过拟合（overfitting）。　

另外也有一种更直观的解释，上面regularized形式的目标函数也可以根据KKT条件转为constraint形式，也就是：

 

argminws.t.∑i=1lℓ(yi,wTxi)∥w∥22<s2

 

通过参数s限制w的大小，而s与C也存在着一定正向相关的关系。因此，当C较小时，w的取值也被限制在的一个很小的范围内。下面的图给了一个非常直观的解释：

由于有了对w取值的限制，就出现了两种情况。第一种是当s不够大的时候，此时如果沿梯度下降的方向一直搜索，找到全局最优解，就已经找出圈外，不满足下面的约束项。这个时候，只能在满足约束的条件下找到尽量好的解。根据KKT条件，此时的最优解一定是划定范围的圆圈与目标函数等梯度线相切的位置，如上图左边所示。如果把梯度图看成一座山的等高线，那边最优解的位置一定是等高线中凸起的部分，类似于一座山上的山脊或者山岭，这也是脊（岭）回归的由来。另一种情况是当s足够大的时候，这个时候，在由s所划定的范围内已经能够达到全局最优解，这个时候，下面的约束项其实并没有起到作用，就如上图右边所示。

因此在调参过程中，如果数据量较少，或者我们对数据的质量信心不足，就应该减少C的大小，增加先验的重要性，反之则可以增加C的大小，让数据本身起更大的作用。而在优化过程中，C越大，需要搜索的w的范围也越大，计算的代价也会越高。而从前面的分析中可以看出，当C增加到一定程度后，模型已经能确保达到全局最优，此时继续增加C对提高算法的表现已经没有帮助。因此，在LIBLINEAR中，实际推荐的做法是将C的值从小向大来调，当C增加之后已经无法改变算法的效果时，说明C对模型已经没有影响，就没有必要继续调下去了。选择较小的C反而可以提高模型收敛的速度。

ℓ1norm的使用

在LIBLINEAR中，除了提供上面提到的ℓ2norm正则化项之外，还提供了ℓ1norm的选项。ℓ1norm一般写成∥w∥1，其实就是对向量w中的所有元素的绝对值进行求和。与ℓ2norm相比，ℓ1norm也具有对w本身大小的约束，使得w的某些维度值不至于过大而导致过拟合。这个特性在统计学上也称作收缩”shrinkage”。而此外，ℓ1norm还有另外一个非常有用的特征，即能够使学习到的w比较稀疏（sparse），也就是存在很多的0项，而且可以通过系数C控制0项的的个数。当C减小时，w的非0项就增多，当C无限小时，由于完全没有拟合损失的压力，w也可以变成全部是0了。

为什么ℓ1norm还有这样的功能呢？说来话长，下次可以专门再写博客讨论了。简单来说，是由ℓ1norm的特殊性质决定的。ℓ1norm所对应的绝对值函数是连续的，但并非处处可导，因为在0点存在特殊的情况，即左右导数实不相等的。因此可以认为定义sub_gradient来描述这种特殊情况的导数，这样的结果是在这个特殊点上，导数不是一个值，而是左右倒数中间的一个范围。由于在0点导数取值非常灵活，使得在模型求解的过程中，很容易在这样的点达到极值，也就会使得学习到的w尽量的稀疏。

基于ℓ1的线性回归模型也被叫做LASSO。采用这个惩罚项的基本动机是认为只有少数特征是与分类结果真正相关，而绝大多数特征是无关的。这一假设确实存在一定的道理，但是在实际分类准确度上，ℓ1norm正则化项对ℓ2norm项并没有绝对的优势，这是因为ℓ2norm虽然不能直接去除那些与分类结果无关的特征，但是模型学习的结果也会让这些特征的权重很低，所以他们能起到的影响不大。但是ℓ1norm的一个好处是可以作为一个特征选择的工具，从高维特征空间中只选取少数一些与分类结果最为相关的特征进行计算。这在处理大量高维数据或者实时计算问题是，还是非常有帮助的，可以大大减少存储，提高计算的效率。

Kernel相关参数

如果使用LIBSVM的话，参数调节的工作就会更复杂一些。首先是kernel的使用。一般来说rbf kernel是被鼓励优先使用的。如果使用rbf kernel效果都无法调到满意，那么采用poly或linear也无济于事。在一些特殊场景下，可以考虑自定义kernel，这在LIBSVM中也是支持的。

rbf的全称是Radial Basis Function，中文叫做径向基函数。而一般在SVM使用的rbf是Gaussian RBF，也就是我们一般所说的高斯核函数。给定两个点x1和x2，Gaussian RBF定义为：

 

K(x1,x2)=exp(−γ∥x1−x2∥2)

 

可见，高斯核函数是对两点之间的欧氏距离进行了一定的变换，且变换受到参数γ的控制。应该怎样理解高斯核函数的意义与γ的作用的？

 

K(x1,x2)=exp(−γ∥x1−x2∥2)=exp(−γ(−∥x1∥2+2xT1x2−∥x2∥2))=exp(−γ∥x1∥2)exp(−γ∥x2∥2)exp(2γxT1x2)=exp(−γ∥x1∥2)exp(−γ∥x2∥2)∑n=0∞(2γxT1x2)nn!

 

当γ较小，或者说在极端情况趋向于0的时候，可以有∑∞n=0(2γxT1x2)nn!≈2γxT1x2，也就是n>1以后的项远小于n=1项。这个时候，rbf kernel的效果其实和linear kernel相差无几。

相反，当γ增大时，n>1以后的项也产生作用，其基本思想和poly kernel差不多，只是rbf直接把维度从有限维度的多项式上升到了无穷维的多项式而已。当γ无限增大时，可以看到，除非∥x1−x2∥2为0，否则K(x_1, x_2) 都会无限趋近于0。也就是说，当γ趋近于无穷大的时候，每一个数据点除了和其自身外，和其他点得距离都为0。在这种情况下，模型训练的结果只能是把所有点都作为支持向量，因此在训练数据上精度可以达到100%。这样的模型也可以看成KNN的特殊情况，此时的K等于1。

上面分别讨论了问题的两个极端情况。当γ无限小的时候，rbf核SVM和线性SVM效果类似，因此模型的复杂度，或者说VC维较低，不容易过拟合。而当γ值无限增大时，所有点都变成支持向量，模型复杂多或者说VC维最高，也最容易过拟合。而一般情况下，γ取一个中间值，也就间距两者的意义，相比于线性模型，可以选择更多的支持向量，增加模型的复杂度与拟合能力。而相比于1-NN模型，也会适当降低模型的复杂度，避免过拟合的风险。此外，从上面的讨论也可以看出，通过参数调整，rbf核基本上可以达到与线性核以及poly核差不多的效果。所以，在不考虑计算效率的情况下，为了达到最优模型，只需要针对rbf模型进行调参就可以了。

上面在参数调整的讨论里，都假设参数C是固定的。但在实际SVM的调参过程中，C和γ是同时变化的，这进一步增加了调参的复杂性。关于两个变量之间的关系，也有很多理论上的分析与讨论，这里不过多进行讨论，可以参考文件：Asymptotic Behaviors of Support Vector Machines with Gaussian Kernel。

在实际的应用场景下，我们可以通过cross-validate的方法对参数进行遍历，选择最佳的参数组合。LIBSVM也提供了grid.py工具，用于SVM的调参。在一般的应用中，我们只需要设置参数的可变范围，然后在训练数据中对参数组合进行遍历，选择最优参数组合就可以了。

总结

最后简单做下总结参数与kernel的选择吧：

• 线性模型选择，选择LIBLINEAR，主要调节参数C，从小到大调节，如果再增加C对结果改变不大时，就可以不用进行测试下去了，选择较小的C就可以了。
• kernel选择，如果需要使用kernel，对于一般问题，优先使用rbf kernel。LIBSVM提供的多项式和tanh核函数，都存在一些局限性，一般来说，rbf是使用方便性和模型效果都比较稳定的核函数了。
• LIBSVM参数调节。如果使用rbf核，需要同时调节参数C和参数γ，问题要更复杂一些，最好的办法是自动遍历参数进行参数选择，比如利用grid.py。

 

LIBSVM与LIBLINEAR（四）

2015-01-17

特征的预处理

一般而言，利用LIBSVM和LIBLINEAR训练分类器之前，会对数据的特征进行预处理。预处理有两类，一类是针对特征内在逻辑的处理，比如增加一些dummy变量，或者对特征的范围进行一些认为的调整。这样的特征构造和处理对于分类器的效果也有着非常重要的影响，尤其是线性分类器，由于本身判别能力偏弱，所以更依赖于人工的特征构造。当然，这一类的特征与处理往往与数据本身的理解有很大的关系，不同的业务与应用场景处理的方法网玩那个也不同，这里就不做过多讨论了。

另一类特征的预处理则更加通用，即统一特征的尺度。由于特征的采集方式不同，造成数据原始特征在不同维度往往会有较大的差别。比如对一个人的身体指标进行描述，身高如果单位是米的话，每个人的值都在1到2之间。而体重以千克为单位，每个人至少应该是两位数，或者三位数。如果直接使用这样的原始特征进行分类，一方面某些特征的权重会被人为加大，影响模型的准确性。另外一方面，由于某些维度的scale过大，也会造成优化中的一些效率问题，增加迭代收敛的次数。因此，在进行分类前，一般需要对特征进行归一化，将特征调成到统一尺度。

最常见的归一化方法就是针对特征的每一个维度进行归一化，使得不同的度量在尺度上达到统一。一般来说，scale后特征的值都落在区间[-1,+1]或[0,1]之间。在实际使用时，更加倾向于后者，因为特征稀疏后往往能够提高优化的效率。LIBSVM提供了svm-scale程序进行特征的自动归一化，以归一化到[0,1]为例，主要是根据公式：

 

x′=(x−xmin)/(xmax−xmin)

 

此外，还有一些地方需要特别注意：第一，训练数据和测试数据必须采用统一的归一化函数，保证数据的一致性，即xmax和xmin必须是一致的。第二，并不是所有场景都是用于按特征的归一化。比如文本分类的场景中，通常会对每一个instance进行归一化，或者采用一些更加复杂的归一化算法。

其他问题

除了以上列出的一些关键问题，还有很多琐碎的小点也值得注意，如分类结果的评估方法、不同语言的调用接口、结果的可视化等等，限于篇幅，这里就不详细介绍了。感兴趣的读者可以参考相关资料。

其他的工具

除LIBSVM和LIBLINEAR之外，还有一些工具包也能完成类似的功能，下面做一个简单地介绍。

• SVMLight。与LIBSVM起名的工具包，但是我个人用的不多。数据的格式与LIBSVM相当，但是据说使用更少的资源。此外，SVMLight的扩展还支持排序学习与结构化SVM的训练，因此也有着大量的使用者。
• SVMLin。专为线性SVM训练开发的工具包，之前有过介绍，另外还支持半监督SVM的训练。
• LIBLINEAR SPARK版本。最近LIBLINEAR提供了Spark版本，保留了Liblinear的一些基本功能，能够处理更大规模的数据。

分了四个部分介绍了LIBSVM和LIBLINEAR，写到最后感觉有一些烂尾了，因为感觉越写越琐碎，以至于没有太多趣味了。后面的博客，还是希望能够集中在某一个问题，讨论的更加深入和透彻，这样写作起来也更容易坚持下去。