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.
Analysis of Existing MSVMs
The paper rigorously analyzes four prominent MSVM loss functions:
- Naive Hinge Loss: A simple extension of the binary case.
- Lee et al. (2004): A sum-of-margins approach.
- Vapnik/Weston/Watkins: A pairwise comparison approach.
- 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.
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