Abstract
We introduce Gaussian Margin Machines (GMMs), which maintain a Gaussian distribution over weight vectors for binary classification. The learning algorithm for these machines seeks the least informative distribution that will classify the training data correctly with high probability. One formulation can be expressed as a convex constrained optimization problem whose solution can be represented linearly in terms of training instances and their inner and outer products, supporting kernelization. The algorithm has a natural PAC-Bayesian generalization bound. A preliminary evaluation on handwriting recognition data shows that our algorithm improves over SVMs for the same task.
Introduction
In linear classification, Support Vector Machines (SVMs) are widely regarded as the gold standard. However, SVMs are limited by their output of a single "best" weight vector, providing no measure of confidence or information about alternative weight vectors that might perform similarly. Conversely, Bayesian methods maintain a full probability distribution over weight vectors, offering theoretical elegance but often suffering from computational complexity and the need for approximations like Laplace or Variational inference.
Gaussian Margin Machines (GMMs) bridge this gap. They combine the large-margin principle of SVMs with the probabilistic flexibility of Bayesian methods by learning a distribution over weight vectors rather than a single fixed vector. Conceptually, this represents a large-margin probabilistic principle, rather than the geometric large margin principle used in SVMs. This approach directly minimizes PAC-Bayesian generalization bounds, resulting in classifiers that are not only accurate but also robust to noise and sample variance.
Methods
The GMM algorithm learns a Gaussian distribution $\mathcal{N}(\mu, \Sigma)$ over weight vectors based on the Maximum Entropy Principle. It identifies the "least informative" distribution—the one with the smallest Kullback-Leibler (KL) divergence from a fixed isotropic prior—that satisfies specific training constraints. These distributions represent our knowledge of the weights given constraints imposed by the training examples.
Unlike the hard geometric margin of SVMs, GMMs employ a probabilistic margin. This ensures that a weight vector sampled from the learned distribution correctly classifies a training example with a probability of at least $\eta$ (a confidence parameter). While the initial formulation is complex, the authors demonstrate that a change of variables ($\Sigma = \Upsilon^2$) transforms the problem into a convex constrained optimization. Furthermore, GMMs support the "kernel trick," allowing the optimal mean $\mu$ and covariance $\Sigma$ to be expressed as linear combinations of training instances, enabling the handling of non-linear data.
Experimental Evaluation
The performance of GMMs was evaluated using the USPS handwritten digits dataset. Images were downsampled from 16x16 to 8x8 pixels, and the task involved binary classification across all 45 possible pairs of digits. GMMs were compared against standard SVMs, with hyperparameters for both models tuned via cross-validation.
Key Results and Insights
The evaluation revealed several significant advantages of GMMs over traditional SVMs:
- Superior Accuracy: GMMs outperformed SVMs in 36 out of 45 digit-pair classification tasks. As shown in the comparison of mean errors, the majority of data points lie above the $y=x$ line, indicating higher mean error for SVMs compared to GMMs.
- Increased Stability: A major finding was that GMMs had lower test error variance. This suggests that GMMs are more reliable and less sensitive to the specific random samples used for training. The standard error comparison illustrates that SVMs consistently show higher variance across the tasks.
- Learning Covariance: A key innovation is the learning of the covariance matrix $\Sigma$, rather than using a fixed one. This allows the model to capture feature correlations and identify "safe" directions for variation in the weight space.
Conclusion
Gaussian Margin Machines offer a principled way to handle uncertainty in linear classification by maintaining a distribution over weight vectors. By optimizing for a probabilistic margin, they achieve better accuracy and greater stability than SVMs on handwriting recognition tasks. Future work will focus on improving computational efficiency, as updating the covariance matrix currently requires $O(d^2)$ time, and exploring the scalability of GMMs to larger, higher-dimensional datasets.
Summary updated