# Kernel multiclass support vector machine solvers

## Yutong Wang

## 2020/12/30

In this previous post, we listed solvers for SVMs. The focus of this post is specialized to solvers for the Crammer-Singer and Weston-Watkins kernel SVMs.

# Shark

Solves both

## Relevant papers

Igel, Heidrich-Meisner, and Glasmachers (2008) is the paper that introduced the Shark package. (link to paper)

Dogan, Glasmachers, and Igel (2011) introduces S2DO. (link to paper)

Glasmachers and Dogan (2013) introduces ACF. link to paper

Doǧan, Glasmachers, and Igel (2016) performs empirical studies of several SVM variants link to paper

## Guide to the code

The header file with the `train` functions is here

The CS-SVM uses the `solveMcSimplex` solver (see here).

The WW-SVM uses the `solveMcBox` solver. We discuss this solver in greater detail in the following subsection.

## Shark’s WW-SVM solver

This subsection is a map to help you navigate Shark’s implementation of a WW-SVM solver.

1. The `train` function calls the `solveMcBox` function.
2. `solveMcBox` creates a `QpSolver``<``QpMcBoxDecomp``<PrecomputedMatrixType>>` object `solver`.
3. `solveMcBox` calls the `solver.solve` function
4. `solver.solve` creates the `SelectionStrategy` object `workingSet` which wraps around the `selectWorkingSet` function.

The core of the `solver.solve` function is the decomposition loop:

1. Calls `workingSet` which modifies `i` and `j`. Note that the actual function invoked is `selectWorkingSet`. The working set strategy is called sequential two-dimensional optimization (S2DO), whose theory is developed in the companion paper Fast Training of Multi-Class Support Vector Machines.
2. Calls `updateSMO` which further calls the function `detail::solveQuadratic2DBox`

# BSVM

Solves both

software website | theory paper 1 | theory paper 2

# MSVMpack

Solves both

package paper (JMLR) | theory paper (publisher’s link) | theory paper (author’s link)

# MCSVM

Solves CS-SVM

# SpiderSVM

website

help page for the WW-SVM solver

Dogan, Urün, Tobias Glasmachers, and Christian Igel. 2011. “Fast Training of Multi-Class Support Vector Machines.”

Doǧan, Ürün, Tobias Glasmachers, and Christian Igel. 2016. “A Unified View on Multi-Class Support Vector Classification.” The Journal of Machine Learning Research 17 (1). JMLR. org: 1550–1831.

Glasmachers, Tobias, and Urun Dogan. 2013. “Accelerated Coordinate Descent with Adaptive Coordinate Frequencies.” In Asian Conference on Machine Learning, 72–86.

Igel, Christian, Verena Heidrich-Meisner, and Tobias Glasmachers. 2008. “Shark.” Journal of Machine Learning Research 9 (Jun): 993–96.