Binary classification is mathematically elegant. We map labels to $y \in \{-1, +1\}$, compute a real-valued prediction $f(x)$, and define the margin as $y \cdot f(x)$. If this margin is positive, the prediction is correct; if it is large, the prediction is confident. This simple geometric intuition underpins Support Vector Machines (SVMs), AdaBoost, and logistic regression, providing a clean path to prove convergence, stability, and generalization guarantees.
However, when moving to multiclass classification (where the number of classes $K > 2$), this elegance often breaks down. Historically, practitioners relied on ad-hoc reductions like one-vs-all or one-vs-one voting. While practical, these heuristics lack unified theoretical guarantees and fail to preserve the geometric properties of the binary margin.
To bridge this gap, a powerful research direction has emerged: unifying binary and multiclass learning by mapping discrete labels into structured code spaces and defining margins relatively. This approach, formalized through frameworks like Permutation Equivariant and Relative Margin-based (PERM) losses, allows multiclass models to inherit the exact theoretical guarantees of their binary predecessors.
From Scalar Labels to Code Spaces
In binary classification, the label is a simple scalar. To handle $K$ classes natively, we must map discrete categories into a continuous geometric space where multi-dimensional margins can be manipulated algebraically.
An early intuition was to frame classification as a vector-valued regression problem. For instance, Luca Baldassarre et al. demonstrated in Learning how to grasp objects that categorical labels could be mapped to one-hot encoded vectors, allowing a single regularized least squares framework to handle both discrete classification and continuous outputs. Similarly, Liang Sun et al. extended discriminant analysis to multiclass settings in Multiclass Probabilistic Kernel Discriminant Analysis by regressing samples against a structured multiclass coding matrix rather than scalar targets.
Instead of relying on fixed one-hot vectors, Alex Smola et al. showed in Adapting Codes and Embeddings for Polychotomies that algorithms can simultaneously learn both the embedding function and the continuous "code space" itself. This perspective unifies multiclass classification, multi-label learning, and ranking by treating them all as variants of multivariate regression into a shared coordinate system.
Recently, Clayton Scott et al. formalized this geometric transition in Unified Binary and Multiclass Margin-Based Classification by introducing the matrix label code. The matrix label code serves as the direct mathematical generalization of the binary $\{\pm 1\}$ encoding. By representing labels as structured matrices, it becomes possible to define and manipulate multiclass margins with the same algebraic flexibility enjoyed in the binary domain.
The Geometry of the Relative Margin
Once labels are mapped to a code space, how do we define a margin? In a multiclass setting, a model outputs a vector of scores $\mathbf{f}(x) = [f_1(x), f_2(x), \dots, f_K(x)]^T$. The model predicts the correct class $y$ if its score $f_y(x)$ is greater than all other scores.
The foundational insight, pioneered by Jason Weston et al. in Support vector machines for multi-class pattern recognition, is to define the multiclass margin relatively. Instead of looking at scores in isolation, we evaluate the differences:
$$\text{Margin} = f_y(x) - f_j(x) \quad \forall j \neq y$$
A robust multiclass margin requires that the correct class score beats the runner-up class score by a comfortable gap.
Clayton Scott et al. unified this concept into the relative margin form, characterizing a broad class of objectives known as PERM (Permutation Equivariant and Relative Margin-based) losses. These losses depend strictly on the differences between class scores and treat all classes symmetrically (permutation equivariance). By combining a symmetric "template" function with the matrix label code, the PERM framework provides a single mathematical recipe. When $K=2$, it perfectly collapses to standard binary margin losses (like the hinge or exponential loss); when $K > 2$, it naturally generates their exact, theoretically consistent multiclass counterparts.
Binary Margin: [ Score +1 ] <------- margin -------> [ Score -1 ]
(Scalar Difference)
Multiclass Margin: [ Correct Score ]
|
|---- relative margin ----> [ Incorrect Score 1 ]
|---- relative margin ----> [ Incorrect Score 2 ]
|---- relative margin ----> [ Incorrect Score 3 ]
Why It Works: Inheriting Binary Guarantees
The ultimate power of the relative margin and PERM framework is that it ensures multiclass algorithms are true structural generalizations of binary principles. Because the underlying geometry is preserved, deep theoretical guarantees transfer seamlessly from the binary case to the multiclass case.
1. Boosting and Convergence
In binary boosting, AdaBoost guarantees exponential convergence by greedily maximizing the margin. To replicate this success in higher dimensions, Mohammad J. Saberian et al. demonstrated in Multiclass Boosting: Theory and Algorithms that aligning multiclass boosting with binary AdaBoost ensures that robust convergence properties are maintained without heuristic approximations.
By extending this to multi-dimensional predictors, real-valued codewords, and margin-enforcing $\gamma-\phi$ losses, Mohammad J. Saberian et al. showed in Multiclass Boosting: Margins, Codewords, Losses, and Algorithms that proper relative margin losses allow for the direct recovery of class posterior probabilities. This aligns with the broader geometric perspective of "drifting games" introduced by Robert E. Schapire in Drifting Games, which provides a unified mathematical lens for boosting and online learning across arbitrary label dimensions.
2. Generalization and Calibration
When designing surrogate loss functions, we must ensure that minimizing the surrogate loss actually minimizes the true 0/1 classification error—a property known as classification-calibration. The relative margin form allowed Clayton Scott et al. to derive new, tight sufficient conditions for multiclass calibration.
Furthermore, François Laviolette et al. demonstrated in On Generalizing the C-Bound to the Multiclass and Multi-label Settings that mathematically consistent margin definitions allow tight theoretical error limits (such as the C-bound for majority vote classifiers) to remain valid when scaling from simple binary choices to complex, multi-label output spaces.
3. Explaining Implicit Bias
A central mystery in modern machine learning is why unregularized models trained with gradient descent generalize well. In binary classification, gradient descent on separable data exhibits an "implicit bias" toward the hard-margin SVM solution—it naturally maximizes the margin.
Using the PERM loss framework, Hrithik Ravi et al. bridged this gap in The Implicit Bias of Gradient Descent on Separable Multiclass Data. By analyzing a novel "multiclass exponential tail property" through the lens of relative margins, the authors proved that gradient descent favors simpler, margin-maximizing solutions in multiclass settings exactly as it does in the binary case.
4. Consistent Evaluation Metrics
This philosophy of exact reduction even extends to evaluation. Historically, extending the Area Under the Curve (AUC) to multiclass problems required disjoint, heuristic averaging. In AUCμ: A Performance Metric for Multi-Class Machine Learning Models, Ross Kleiman et al. introduced a multi-class metric built on the principle of exact reduction. Because their metric simplifies exactly to standard binary AUC when the number of classes is reduced to two, it provides a theoretically sound, non-heuristic measurement of multi-class model performance.
By moving away from ad-hoc combinations of binary classifiers and embracing the geometry of relative margins and matrix label codes, this framework reveals that multiclass classification is not a fundamentally different problem type—it is simply a higher-dimensional manifestation of the same elegant principles that govern binary learning.
Key Foundational Work
Support vector machines for multi-class pattern recognition (1999) — contributed 1 concept elements to this direction.
Drifting Games (2001) — contributed 1 concept elements to this direction.