PPubMed1 Jun 2017Cited 12×

Distributed optimization of multi-class SVMs Distributed optimization of multi-class SVMs

Maximilian Alber, Julian Zimmert, Urun Dogan, Marius Kloft, Quan Zou

Abstract

Training of one-vs.-rest SVMs can be parallelized over the number of classes in a straight forward way. Given enough computational resources, one-vs.-rest SVMs can thus be trained on data involving a large number of classes. The same cannot be stated, however, for the so-called all-in-one SVMs, which require solving a quadratic program of size quadratically in the number of classes. We develop distributed algorithms for two all-in-one SVM formulations (Lee et al. and Weston and Watkins) that parallelize the computation evenly over the number of classes. This allows us to compare these models to one-vs.-rest SVMs on unprecedented scale. The results indicate superior accuracy on text classification data.

A figure from Distributed optimization of multi-class SVMs Distributed optimization of multi-class SVMs — fig. from the paper

§ The Valyu brief

The paper, in five minutes

Read from the full text via Valyu Contents

Distributed algorithms enable scalable training of all‑in‑one multi‑class SVMs, achieving linear speedup and higher accuracy on large text datasets.

What’s new

i.Developed distributed dual block coordinate ascent algorithms for Lee‑Lin‑Wahba (LLW) and Weston‑Watkins (WW) multi‑class SVM formulations that parallelize over the number of classes
ii.Implemented the algorithms using OpenMPI for inter‑machine communication and OpenMP for intra‑machine parallelism with minimal communication overhead
iii.Demonstrated linear speedup and up to two orders of magnitude faster training compared to state‑of‑the‑art OVR and Crammer‑Singer solvers on large‑scale LSHTC text classification datasets
iv.Showed superior classification accuracy and model sparsity of all‑in‑one SVMs over one‑vs‑rest approaches

How they did it

The authors derived distributed optimization schemes for LLW and WW by applying dual block coordinate ascent and a graph‑theoretic 1‑factorization schedule to split the problem across C nodes. They implemented the solvers with MPI/OpenMP, ran experiments on machines with up to 24 cores, and evaluated convergence, runtime, and classification performance on LSHTC datasets ranging from 451 to 27,875 classes.

What they found

Linear speedup observed when increasing cores and machines (≈4× faster with 4 machines)
Training time up to 100× faster than OVR and Crammer‑Singer implementations
Duality gap closed by two orders of magnitude across datasets
All‑in‑one SVMs achieved lower error rates and higher Micro‑F1/Macro‑F1 scores than OVR on all LSHTC datasets

Caveats

✕LLW models remained dense and did not scale well to extremely large label spaces
✕Resource and convergence limits prevented experiments with very large C values for LLW
✕Communication overhead, though modest, grows with model density for smaller C values
✕Evaluations were limited to text classification datasets; other domains were not tested

§ The Valyu brief

Reading the full paper and taking notes. This takes a few seconds…

§ Ask this paper

Ask a question about this paper

Valyu reads the full text and answers from what the paper actually says.

§ Related work in other archives

Distributed optimization of multi-class SVMs Distributed optimization of multi-class SVMs

The paper, in five minutes

Ask a question about this paper

Similar papers in all four archives

Similar papers in all four archives

The paper, in five minutes