Abstract
Discriminative linear models are a popular tool in machine learning. These can be generally divided into two types: The first is linear classifiers, such as support vector machines, which are well studied and provide state-of-the-art results. One shortcoming of these models is that their output (known as the 'margin') is not calibrated, and cannot be translated naturally into a distribution over the labels. Thus, it is difficult to incorporate such models as components of larger systems, unlike probabilistic based approaches. The second type of approach constructs class conditional distributions using a nonlinearity (e.g. log-linear models), but is occasionally worse in terms of classification error. We propose a supervised learning method which combines the best of both approaches. Specifically, our method provides a distribution over the labels, which is a linear function of the model parameters. As a consequence, differences between probabilities are linear functions, a property which most probabilistic models (e.g. log-linear) do not have. Our model assumes that classes correspond to linear subspaces (rather than to half spaces). Using a relaxed projection operator, we construct a measure which evaluates the degree to which a given vector 'belongs' to a subspace, resulting in a distribution over labels. Interestingly, this view is closely related to similar concepts in quantum detection theory. The resulting models can be trained either to maximize the margin or to optimize average likelihood measures. The corresponding optimization problems are semidefinite programs which can be solved efficiently. We illustrate the performance of our algorithm on real world datasets, and show that it outperforms 2nd order kernel methods.
Introduction
In supervised learning, practitioners often face a tradeoff between margin-based classifiers and probabilistic models. Support Vector Machines (SVMs) are highly effective and offer strong generalization guarantees by maximizing the decision margin. However, their output—the geometric margin—is not a calibrated probability, making it difficult to use SVMs as modular components in larger systems where confidence scores are required. Conversely, probabilistic models like logistic regression output true probabilities but do not inherently maximize margins, often leading to higher classification error.
We introduce a novel framework that bridges this gap. Our model is inherently probabilistic but can be trained using max-margin principles. By assuming that classes reside in linear subspaces rather than half-spaces, we formulate the learning task as a Semidefinite Program (SDP).
Methodology: Subspaces and Semidefinite Programming
The core of our model is the assumption that each class $y$ corresponds to a linear subspace. The probability of a data point $\mathbf{x}$ belonging to class $y$ is defined as the fraction of the point's norm that projects onto that class's subspace:
$$p(y|\mathbf{x}) = \mathbf{x}^T A_y \mathbf{x}$$
To ensure these outputs are valid probabilities, the projection matrices $A_y$ must be positive semidefinite (PSD), and the sum of all $A_y$ matrices must equal the identity matrix ($\sum A_y = I$). This mathematical structure is virtually identical to quantum detection theory, where $A_y$ act as "detection operators" and data points act as quantum states.
While the predictor $\mathbf{x}^T A_y \mathbf{x}$ is mathematically similar to an SVM using a second-order polynomial kernel, the strict PSD and identity-sum constraints force the outputs into the $[0,1]$ range, fundamentally changing the optimization landscape and the resulting bounds on classification loss.
Training Objectives
We propose two primary methods for learning the matrices $A_y$:
- MaxMargin: Formulated as an SDP, this approach maximizes the margin between the probability of the correct class and incorrect classes. It includes a dual formulation that yields a $\nu$-property, bounding the fraction of support vectors and margin errors.
- Bayes (Likelihood): This approach maximizes the average log-likelihood of the correct class. For binary classification, we have discovered a significant practical advantage: this formulation has a closed-form analytic solution based on the eigendecomposition of the difference between the classes' covariance matrices.
Experimental Results
The model's ability to learn orthogonal subspaces was initially verified on a synthetic 2D XOR problem. Subsequently, it was evaluated on the USPS handwritten digits dataset. Due to the computational intensity of standard SDP solvers, dimensionality was reduced to 64. We tested the model on all 45 possible binary pairs of the 10 digits.
As shown in the figure above, the MaxMargin SDP approach outperformed standard second-order kernel SVMs on the vast majority of the classification tasks. Beyond raw accuracy, the model provides insights into the distribution of confidence.
Analysis of the hardest classification task ("3" vs. "5") reveals that while the MaxMargin approach achieves higher accuracy, the Bayes approach produces better-calibrated probabilities. MaxMargin optimizes specifically to cross the decision threshold, whereas Bayes reflects true probabilistic uncertainty across the test set.
Conclusion
This work demonstrates that discriminative learning can be effectively performed using semidefinite probabilistic models. By combining the strengths of max-margin training with the interpretability of calibrated probabilities, we provide a robust alternative to traditional kernel methods. Future research will focus on improving the scalability of the underlying SDP solvers and extending the framework to handle structured prediction and multi-label tasks.
Summary updated