A Unified View on Multi-class Support Vector Classification

Ürün Dogan, Tobias Glasmachers, Christian IgelJMLR 2016 · OpenReview

TL;DR

This paper presents a unified framework for understanding and developing multi-class Support Vector Machines (SVMs). By categorizing existing methods based on their margin concepts and aggregation operators, the authors reveal surprising insights into their performance and consistency, leading to practical recommendations for choosing the right multi-class SVM.

What Problem Does This Paper Address?

Support Vector Machines (SVMs) are powerful tools for binary classification, but extending them to multi-class problems has led to a proliferation of different approaches. These methods often differ in subtle ways regarding how they define "margin" and combine losses across classes. This lack of a unified perspective makes it difficult to understand their theoretical underpinnings, compare their performance, and choose the most appropriate one for a given task. The authors aim to bridge this gap by providing a unifying framework that categorizes and analyzes existing multi-class SVMs, leading to a deeper understanding of their strengths and weaknesses.

Methods

The core of the paper is a unifying framework that categorizes multi-class SVMs based on three key components:

  • Margin Functions: How the margin is defined for each class (e.g., relative margins, absolute margins, or a "self-margin" concept).
  • Aggregation Operators: How the individual class margins or losses are combined into a single objective function (e.g., sum-over-others, max-over-others, total-sum).
  • Sum-to-Zero Constraint: Whether the decision function components are constrained to sum to zero, which influences the interpretation and properties of the margins.

Using this framework, the authors analyze the theoretical properties (like Fisher and universal consistency) of various existing machines and introduce new variants by exploring under-utilized combinations of these components. They also derive a unified dual problem formulation, which is crucial for efficient training algorithms.

Datasets

The paper uses a combination of:

  • Artificial Benchmark Problems: Two variants of a "noiseless circle problem" and a "noisy circle problem" are introduced. These are specifically designed to highlight differences in how machines handle uneven class distributions and label noise, serving as controlled "counter-examples."
  • Standard Benchmark Datasets: Twelve standard datasets are used for evaluating non-linear SVMs, and an additional set of datasets are used for linear SVMs. These are standard in the machine learning community for evaluating classification algorithms.

Key Insights and Ideas

  • Margin Concept Matters More Than Aggregation: The authors find that the choice of margin concept (relative vs. absolute) has a more significant impact on performance than the specific aggregation operator used.
  • Absolute Margins Can Be Problematic: Absolute margin machines, especially in low-dimensional feature spaces or with noisy data, can fail to find good solutions, even when theoretically consistent. This is because they may not be compatible with the structure of the decision function.
  • Relative Margins Offer Robustness: Relative margin machines, particularly the WW (Weston & Watkins) and CS (Crammer & Singer) approaches, generally exhibit more robust performance across various scenarios.
  • Consistency vs. Performance: A machine can be theoretically inconsistent (its loss function is not Fisher consistent) but still achieve good practical performance when regularized properly (e.g., MMR, WW, OVA). This highlights the importance of the regularizer in the overall SVM formulation.
  • Maximum Aggregation Can Lead to Guessing: Machines using maximum-based aggregation operators (like CS, AMO, ATM) can exhibit random guessing behavior in scenarios without a clear majority class, especially in the presence of noise.

Key Results

  • Empirical Performance: In non-linear settings, WW and RM machines generally performed best, with WW showing slightly more stable performance. MMR machines performed worst in terms of accuracy but were fastest to train. For linear SVMs, drastic differences were observed, with WW and CS outperforming others, especially in high-dimensional spaces.
  • Training Times: Training times varied significantly, with MMR being the fastest, followed by OVA, WW, and CS. Absolute margin machines were generally much slower to train.
  • Theoretical Findings:
    • LLW and ATS machines are Fisher consistent.
  • AMO and ATM machines are not Fisher consistent.
  • MMR, WW, and OVA machines, despite having inconsistent losses, can be made universally consistent with appropriate regularization.
  • CS, AMO, and ATM machines cannot be made universally consistent, regardless of regularization.

Limitations and Future Work

  • Limitations: The paper acknowledges that the stopping criteria for quadratic programming could influence training times but not test accuracies. The analysis of universal consistency for some machines relies on specific assumptions about the regularization parameter's dependency on data size and kernel properties. The authors also note that their analysis of linear SVMs is an extension of their non-linear kernel work.
  • Future Work: The paper suggests that the unified framework can be used to construct and analyze new multi-class SVM variants. The authors also leave open the question of whether an SVM can be consistent for parameters in a "gap" between different regimes of regularization. The empirical comparison highlights the need for careful model selection and suggests that training time can be a significant factor in choosing a method.

Summary updated

BibTeX
@article{dogan2016unified,
  author = {Ürün Dogan and Tobias Glasmachers and Christian Igel},
  title = {{A Unified View on Multi-class Support Vector Classification}},
  journal = {J. Mach. Learn. Res.},
  year = {2016},
  url = {https://openreview.net/forum?id=UALbdmJoeRG},
}

Loading related content...

Figure