ARCHIVE Snapshot of the Rätsch lab website (Tübingen, then New York) as of February 2016: preserved, not maintained. The group today: bmi.inf.ethz.ch
Personal tools
Home → Rätsch Lab → Supplements → PMSVM → m-SVM: A General Primal Multiclass SVM
 

m-SVM: A General Primal Multiclass SVM

Paper "Training and Approximation of a Primal Multiclass Support Vector Machine" [PDF, abstract] by Alexander Zien, Fabio de Bona, Cheng Soon Ong at The 12th International Conference on Applied Stochastic Models and Data Analysis (ASMDA 2007).

Supplementary Results

Summary of Features and Conclusions

  • Optimization and approximation:
    • Optimization of multiclass SVMs in the primal is possible, simple, and more principled if approximations are taken (cf. Chapelle, 2006).
    • PCA-based approximation is plausible and can be better than other schemes (denoising effect).
    • The quality of PCA-based approximation can partially be forcast by the kernel's spectrum (cf. supplement on kernel spectra).
  • Generality and special cases:
    • The joint feature map approach allows the generalization to structured output spaces.
    • Joint kernels formed by multiplying a kernel on the input with one on the output still allow to model non-trivial relations between classes.
    • With a diagonal kernel on the outputs, we get the classical multiclass approach (for each class, a separate hyperplane in a common feature space) as special case.
    • The softmax interpolates between two previously proposed modes of loss aggregation: sum (Vapnik, 1998; Weston & Watkins, 1999) and max (Crammer & Singer, 2001).
  • Joint feature map, 1-vs-rest, and 1-vs-1:
    • The m-SVM is roughly as good as 1-vs-rest or 1-vs-1 (cf. paper).
    • 1-vs-1 with probabilistic postprocessing (PWC_PSVM) is better (cf. paper; Duan & Keerthi 2005).
    • Thus: If you can use 1-vs-1 and PWC_PSVM, do so.
    • Note that the 1-vs-1 approach cannot be extended to semi-supervised learning.
    • Further, 1-vs-1 cannot be used to model complex outputs (eg multiclass with known structure on the classes, or label sequences).
  • Use in muliple kernel learning (MKL):
    • In recent work, a semi-supervised structured output SVM (including a multiclass TSVM as special case) has been developed (Zien, Brefeld, Scheffer, 2007). It does not yet incorporate approximation schemes, but computation time is an urgent problem there.
    • The m-SVM may also serve as a part of an optimizer for multiclass multiple kernel learning ("MCMKL"; Zien and Ong, 2007). There, PCA-based approximation is particularly attractive, as the PCA has to be performed only once, but will speed up several m-SVM trainings.

Links

Document Actions