libsdca

libsdca trains linear and kernel classifiers with the losses from my PhD work on top-k error, along with the standard multiclass and multilabel ones. It is a header-only C++11 library with a MATLAB interface, and it is the reference implementation of the top-k SVM (NeurIPS 2015) and the top-k entropy loss (CVPR 2016).

Why SDCA

Stochastic dual coordinate ascent (Shalev-Shwartz and Zhang, 2013, 2016) works on the dual problem, one training example at a time. For these losses each step reduces to a small proximal problem, usually a projection onto a simplex-like set, and libsdca solves it exactly. The dual objective also gives a duality gap, a certificate of how far the current model is from the optimum, so you know when training is actually done instead of guessing from a learning curve.

What's inside

Multiclass losses

Multiclass SVM (Crammer and Singer, 2001), plain and smoothed (Lapin et al., 2016)
Top-k SVM, both α and β versions (Lapin et al., 2015), plain and smoothed (2016)
Softmax (cross-entropy)
Top-k entropy (Lapin et al., 2016)

Multilabel losses

Multilabel SVM (Crammer and Singer, 2003), plain and smoothed (Lapin et al., 2018)
Multilabel cross-entropy (Lapin et al., 2018)

Proximal operators

Projections onto the simplex (Kiwiel, 2008), top-k simplex, and top-k cone (Lapin et al., 2015)
Entropic projections (Lapin et al., 2016, 2018)
Lambert W function of an exponential, W(exp(x)) (Corless et al., 1996)

Inputs and interfaces

Features or precomputed kernels, in float or double
Several datasets at once, e.g. to track a validation set
C++11 headers: nothing to build except a BLAS for the solver
MATLAB: matsdca_fit and matsdca_prox

For the nonconvex truncated top-k entropy loss, see libsdca_gd in v0.2.0.

Install

From C++, add include/ to your include path and link a BLAS if you use the solver. The MATLAB interface is two MEX files, built into matlab/ with CMake on Linux or macOS:

git clone https://github.com/mlapin/libsdca.git
cd libsdca && mkdir build && cd build
cmake .. && make install -j4

or from MATLAB itself:

run matlab/make.m
addpath matlab

Quick start

model = matsdca_fit(X, Y, opts);   % train
matsdca_fit('help')                % list objectives and options
matsdca_prox('help', 'prox')       % list proximal operators

A complete example is in matlab/demo.m.

See it in action

The losses demo trains softmax, multiclass SVM, top-k SVM, and top-k entropy side by side in your browser on the synthetic problem from the CVPR 2016 paper. The simplex demo runs the projection onto the top-k simplex that the top-k SVM update relies on. Both are JavaScript reimplementations rather than libsdca itself, but the math is the same.

Cite

If libsdca helps your research, please cite the paper for the losses you use.

@inproceedings{lapin2015topk,
  title     = {Top-k Multiclass {SVM}},
  author    = {Lapin, Maksim and Hein, Matthias and Schiele, Bernt},
  booktitle = {NeurIPS},
  year      = {2015}
}

@inproceedings{lapin2016loss,
  title     = {Loss Functions for Top-k Error: Analysis and Insights},
  author    = {Lapin, Maksim and Hein, Matthias and Schiele, Bernt},
  booktitle = {CVPR},
  year      = {2016}
}

The journal version adds the multilabel losses and the calibration analysis:

@article{lapin2018analysis,
  title   = {Analysis and Optimization of Loss Functions for Multiclass, Top-k, and Multilabel Classification},
  author  = {Lapin, Maksim and Hein, Matthias and Schiele, Bernt},
  journal = {IEEE TPAMI},
  volume  = {40},
  number  = {7},
  pages   = {1533--1554},
  year    = {2018}
}

References

R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth. On the Lambert W function. Advances in Computational Mathematics, 5:329–359, 1996.
K. Crammer and Y. Singer. On the algorithmic implementation of multiclass kernel-based vector machines. JMLR, 2:265–292, 2001.
K. Crammer and Y. Singer. A family of additive online algorithms for category ranking. JMLR, 3:1025–1058, 2003.
K. C. Kiwiel. Variable fixing algorithms for the continuous quadratic knapsack problem. Journal of Optimization Theory and Applications, 136(3):445–458, 2008.
M. Lapin, M. Hein, and B. Schiele. Top-k multiclass SVM. In NeurIPS, 2015.
M. Lapin, M. Hein, and B. Schiele. Loss functions for top-k error: Analysis and insights. In CVPR, 2016.
M. Lapin, M. Hein, and B. Schiele. Analysis and optimization of loss functions for multiclass, top-k, and multilabel classification. IEEE TPAMI, 40(7):1533–1554, 2018.
S. Shalev-Shwartz and T. Zhang. Stochastic dual coordinate ascent methods for regularized loss minimization. JMLR, 14:567–599, 2013.
S. Shalev-Shwartz and T. Zhang. Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization. Mathematical Programming, 155:105–145, 2016.