Relevance matrices in LVQ

Petra Schneider, Michael Biehl, Barbara HammerESANN 2007 · OpenReview

Abstract

Generalized Matrix Learning Vector Quantization (GMLVQ) represents a significant advancement in prototype-based classification. By transitioning from standard Euclidean distances to learned correlation matrices, the algorithm can adapt to complex, ellipsoidal data distributions and capture feature dependencies. This paper explores GMLVQ and its localized variant (LGMLVQ), demonstrating substantial accuracy gains on both artificial and real-world datasets while maintaining robust generalization through large-margin optimization.

Introduction

Standard Learning Vector Quantization (LVQ) is a popular "winner-takes-all" classification method because it’s intuitive: you classify a data point based on its proximity to "prototypes" representing different classes. However, original LVQ relies on the Euclidean metric, which assumes that all features are equally important and completely independent. In real-world scenarios, features are often correlated and vary in importance. While previous improvements like GRLVQ introduced relevance factors to scale axes, they remained limited to axis-parallel ellipsoids. This work addresses the need for a distance metric capable of adapting to arbitrary ellipsoidal shapes in high-dimensional space.

Methods

The authors extend the Generalized Relevance LVQ framework through two primary innovations:

  1. Generalized Matrix LVQ (GMLVQ): Introduces a full square matrix $\Lambda = \Omega \Omega^T$ to represent the distance metric. This allows the model to learn feature correlations via gradient descent on $\Omega$.
  2. Localized GMLVQ (LGMLVQ): Assigns an individual matrix to every prototype, allowing for region-specific feature space warping.
Visual comparison of decision boundaries for various LVQ algorithms on artificial data.

As shown in Figure 1, the localized matrices allow for non-linear decision boundaries and non-convex receptive fields, better capturing the underlying data structure compared to standard methods. The off-diagonal elements in the learned matrices represent discovered correlations between features that are most relevant for classification.

Key Results

The proposed methods were evaluated on an artificial 2D dataset with rotated ellipsoidal Gaussians and the UCI Image Segmentation dataset. The inclusion of full matrices provided a massive performance boost over standard methods.

Performance comparison of LVQ variants on artificial and image datasets.

The results in Figure 2 highlight the dramatic performance boost provided by full matrix learning. On artificial data, LGMLVQ reached 90.75% test accuracy, a significant jump from the 71.83% achieved by standard GLVQ. Similarly, on the image dataset, LGMLVQ achieved 94.29% accuracy compared to 79.05% for GLVQ. Crucially, the gap between training and test accuracy remained minimal, supporting the theory that the algorithm acts as a large-margin optimizer, preventing overfitting despite the increased parameter count.

Conclusion

GMLVQ and LGMLVQ successfully address the limitations of Euclidean-based LVQ by learning adaptive distance metrics. While the computational complexity scales quadratically with dimensionality ($N^2$), the gains in accuracy and the ability to discover relevant feature correlations make it a powerful tool for complex classification tasks. Future work may explore restricted matrix bandwidths to improve scalability for high-dimensional data.

Summary updated

BibTeX
@inproceedings{schneider2007relevance,
  author = {Petra Schneider and Michael Biehl and Barbara Hammer},
  title = {{Relevance matrices in LVQ}},
  booktitle = {ESANN},
  year = {2007},
  url = {https://openreview.net/forum?id=-_6qchfmLAgg},
}
Figure