Fisher Consistency of Multicategory Support Vector Machines

Yufeng LiuAISTATS 2007 · OpenReview

Abstract

Support Vector Machines (SVMs) are highly effective for binary classification, but their extension to multicategory problems is non-trivial. This paper investigates the Fisher consistency of several popular Multicategory SVM (MSVM) formulations. We demonstrate that many existing extensions, including the popular Crammer and Singer approach, are Fisher inconsistent under certain conditions. To address these shortcomings, we propose two modifications: the introduction of bounded constraints and the use of a truncated hinge loss function, both of which restore Fisher consistency.

Introduction: The Challenge of Multicategory Margins

In binary classification, the SVM is defined by an elegant hinge loss that encourages a large margin between two classes. However, when moving to $k > 2$ classes, there is no single "obvious" way to define this margin. Various researchers have proposed different Multicategory SVM (MSVM) formulations, but a fundamental question remains: are these methods Fisher consistent?

A loss function is Fisher consistent if, in the limit of infinite data, minimizing that loss leads you to the Bayes decision rule—the theoretically best possible classifier. If a method lacks Fisher consistency, it may fail to converge to the optimal boundary regardless of the amount of data provided.

The standard hinge loss used in binary SVMs, where loss is zero for correctly classified points beyond a margin.

Analysis of Existing MSVMs

The paper rigorously analyzes four prominent MSVM loss functions:

  1. Naive Hinge Loss: A simple extension of the binary case.
  2. Lee et al. (2004): A sum-of-margins approach.
  3. Vapnik/Weston/Watkins: A pairwise comparison approach.
  4. Crammer and Singer (2001): A "winner-take-all" margin approach.

The theoretical analysis reveals that the Naive hinge loss, the Vapnik/Weston/Watkins loss, and the Crammer/Singer loss are all Fisher inconsistent in various scenarios. For instance, the Crammer and Singer MSVM is only consistent if one class is "dominant" (probability $> 0.5$). In more balanced cases, such as three classes each with $0.33$ probability, the method can fail to uniquely identify the best class. Of the four reviewed, only the formulation by Lee et al. (2004) is shown to be universally Fisher consistent.

Proposed Solutions for Consistency

To rectify these inconsistencies, the paper introduces two novel strategies:

Bounded Constraints

By imposing constraints that force decision functions to stay within a specific range (e.g., between $-1$ and $k-1$), the "Naive" loss can be transformed into a Fisher consistent framework. Interestingly, this approach sacrifices the "sparsity" characteristic of standard SVMs—where only a few support vectors determine the boundary—in favor of guaranteed convergence to the Bayes boundary.

Truncated Hinge Loss

Another powerful tool is the truncation of the loss function. By "capping" the loss so it does not grow infinitely with the distance of misclassification, the author shows that the Crammer and Singer approach becomes consistent even in cases where no single class is dominant.

Comparison of loss functions: standard hinge loss ($H_1$), shifted hinge loss ($H_s$), and the proposed truncated hinge loss ($T_s$) which caps the penalty for large errors.

Conclusion

This work highlights a critical theoretical gap in popular multicategory extensions of SVMs. While the "support vector" property is a hallmark of SVM efficiency, the pursuit of Fisher consistency may require moving toward non-sparse or non-convex formulations, such as those using bounded constraints or truncated losses. These findings provide a rigorous foundation for developing more robust multicategory classifiers that perform optimally in the limit of large data.

Summary updated

Abstract

The Support Vector Machine (SVM) has become one of the most popular machine learning techniques in recent years. The success of the SVM is mostly due to its elegant margin concept and theory in binary classification. Generalization to the multicategory setting, however, is not trivial. There are a number of different multicategory extensions of the SVM in the literature. In this paper, we review several commonly used extensions and Fisher consistency of these extensions. For inconsistent extensions, we propose two approaches to make them Fisher consistent, one is to add bounded constraints and the other is to truncate unbounded hinge losses.
BibTeX
@inproceedings{liu2007fisher,
  author = {Yufeng Liu},
  title = {{Fisher Consistency of Multicategory Support Vector Machines}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2007},
  url = {https://openreview.net/forum?id=XWKIPMGOUc},
}
Figure