LIBSVM与LIBLINEAR(二)

960 查看

模型与优化

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

LIBSVM

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

LIBSVM包含的各种模型:

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

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

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

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

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