Introduction

The library implements Optimized Cutting Plane Algorithm (OCAS) for training linear SVM classifiers from large-scale data. The computational effort of OCAS scales with O(m log m) where m is the sample size. In an extensive empirical evaluation OCAS significantly outperforms current state of the art SVM solvers, like SVM^light, SVM^perf and BMRM, achieving speedups of over 1,000 on some datasets over SVM^light and 20 over SVM^perf, while obtaining the same precise Support Vector solution. OCAS even in the early optimization steps shows often faster convergence than the so far in this domain prevailing approximative methods SGD and Pegasos. Effectively parallelizing OCAS we were able to train on a dataset of size 15 million examples (itself about 32GB in size) in just 671 seconds --- a competing string kernel SVM required 97,484 seconds to train on 10 million examples sub-sampled from this dataset.

Features

• SVM solvers for training linear classifiers from large scale-data.
• Binary (two-class) and genuine multi-class SVM formulations.
• Optimized code written in C.
• A stand alone application and MEX interface for Matlab.
• Reads examples from SVM^light format.
• Optimized for both sparse and dense features.
• Parallelized version of the binary solver.
• Allows using different C for each training example (Matlab's interace to binary solver).
• Tools for classification.

Problem formulation

1. Binary classification problem: OCAS solves the following unconstrained convex optimization task

2. Multi-class classification probem: OCAS solves the following unconstrained convex optimization task

Download

• Version 0.91, 2008-07-14, libocas_v091.zip
• Version 0.90, 2008-10-12, libocas_v09.zip

Platforms

Licensing Information

References

V. Franc, S. Sonnenburg. OCAS optimized cutting plane algorithm for Support Vector Machines. In Proceedings of ICML. ACM Press, 2008. [pdf]