PaperlayerView exact revision on arXiv

Source-linked AI summary

A review of learning vector quantization classifiers

David Nova, Pablo A. Estevez

arXiv:1509.07093v1cs.LGastro-ph.IMcs.NEstat.ML

TL;DR

LVQ has developed into a family of classifiers with different objectives and design choices, while early learning rules faced convergence and stability problems. This review organizes and compares supervised LVQ approaches, finding that they are competitive but have dataset-dependent trade-offs rather than a universally best method.

  • Problem

    LVQ has developed many variants, while early rules were sensitive to initialization, slow to converge, and unstable.

    Source: §1 · p. 2

  • Method

    The paper reviews and taxonomizes supervised LVQ approaches, describes their main algorithms, and compares eleven methods on three datasets.

    Source: §1 · p. 3

  • Results

    LVQ methods have different pros and cons for specific problems and datasets, and are competitive classifiers overall.

    Source: §6 · pp. 20–21

  • Takeaways & Limitations

    No single LVQ method is best across datasets; each was designed for particular problems and datasets.

    Source: §6 · p. 20

    Kernelized and relational LVQ methods are not easily visualized and interpreted when they work in a space different from the data space.

    Source: §5 · p. 20

Abstract

from arXiv · show

In this work we present a review of the state of the art of Learning Vector Quantization (LVQ) classifiers. A taxonomy is proposed which integrates the most relevant LVQ approaches to date. The main concepts associated with modern LVQ approaches are defined. A comparison is made among eleven LVQ classifiers using one real-world and two artificial datasets.

1 Introduction

LVQ classifiers learn class-representing prototypes that partition the input space, and this review surveys supervised variants and their development. It compares their strengths and limitations across datasets.

1 Introduction

  • LVQ classifiers use class-labeled prototypes to represent class regions, typically forming Voronoi partitions in the input space.The review focuses on supervised classifiers, while noting that LVQ can also be trained without labels for clustering.Source: §1 · pp. 1–2
  • LVQ is presented as intuitive and fast, with computational cost tied to the usually fixed number of prototypes rather than training-set size.The review contrasts prototypes as typical vectors with SVM support vectors as extreme data values.Source: §1 · p. 2
  • Original LVQ learning rules were heuristic and sensitive to initialization, slow to converge, and unstable; GLVQ and RSLVQ use explicit objectives to derive learning rules.GLVQ uses steepest descent on a cost function associated with error minimization and margin maximization; RSLVQ uses gradient ascent on a log ratio of class probability densities under a Gaussian-mixture assumption.Source: §1 · p. 2
  • Later extensions address initialization sensitivity and replace Euclidean distance with weighted, adaptive, pseudo-Euclidean, or kernel-space metrics.These extensions include relevance-matrix metrics and kernelized LVQ.Source: §1 · p. 2
  • The review compares eleven supervised LVQ algorithms on artificial and real-world datasets and discusses advantages and limitations depending on dataset characteristics.It also presents a taxonomy and describes the main algorithms.Source: §1 · p. 3

2 A Taxonomy of LVQ Classifiers

The taxonomy groups LVQ classifiers into heuristic Kohonen methods, margin-maximization methods, and likelihood-ratio-maximization methods. The section describes these families alongside extensions for adaptive distances, kernelized data, and pairwise dissimilarities.

2.1 Learning Vector Quantization

  • LVQ classifies through labeled prototypes whose class regions form Voronoi partitions, and the taxonomy distinguishes heuristic Kohonen, margin-maximization, and likelihood-ratio-maximization families.The section also describes the basic learning goal as choosing prototypes so training samples map to their class labels.Source: §2.1 · pp. 3–4

2.2 Margin Maximization

  • GLVQ optimizes a hypothesis margin based on distances to the nearest correct- and incorrect-class prototypes, addressing slow convergence, initialization sensitivity, and correlated dimensions.The cost function includes the relative distance difference and applies a logistic sigmoid to it.Source: §2.2 · pp. 4–5

2.3 Likelihood Ratio Maximization

  • RSLVQ models each class with a Gaussian mixture and maximizes the logarithm of the ratio between correct-class and incorrect-class probability densities.The method compares the density of a sample under the correct class mixture with its density under the incorrect-class mixtures.Source: §2.3 · pp. 5–6

2.4 Distance Learning

  • Adaptive distance learning replaces a fixed Euclidean metric to accommodate dimension scaling and correlations; a full relevance matrix can represent rotations, while a diagonal restriction yields GRLVQ.Fig. 2 contrasts receptive fields under Euclidean, diagonal-relevance, and full-relevance metrics.Source: §2.4 · pp. 6–7, Figure 2 · p. 6

2.5 Kernelization

  • Kernel LVQ maps data into a possibly linearly separable feature space and uses kernels to compute distances without explicitly knowing the nonlinear mapping.The described kernelized method is called KGLVQ.Source: §2.5 · pp. 7–8

2.6 Dis-/similarities

  • For non-vectorial problems, dissimilarity approaches represent data through pairwise similarities or dissimilarities and describe prototypes as linear combinations of samples.Unlike kernel approaches, these methods do not assume the data are Euclidean.Source: §2.6 · p. 8

3.1 LVQ 2.1

LVQ2.1 updates the nearest correct-class and incorrect-class prototypes in opposite directions when a sample falls within a window around their mid-plane. The window restricts updates to samples near the classification boundary.

3.1 LVQ 2.1

  • LVQ2.1 moves the nearest correct-class prototype toward the sample and the nearest incorrect-class prototype away from it, using a learning rate between 0 and 1.The two prototypes are the closest representatives of the sample's correct and incorrect classes.Source: §3.1 · p. 9
  • Updates occur only when the sample lies within a relative-width window around the mid-plane of the two prototypes, near the classification boundary.The window width is typically set to 0.2 or 0.3.Source: §3.1 · p. 9

3.2 LVQ Methods Based on Margin Maximization

Margin-based LVQ extends GLVQ through alternative prototype updates, adaptive distance metrics, kernel feature spaces, and dissimilarity representations. These variants address initialization sensitivity or broaden the data representations that can be used.

3.2 LVQ Methods Based on Margin Maximization

  • GLVQ updates the nearest same-class prototype toward an input and the nearest different-class prototype away from it using stochastic gradient descent.Its update factors derive from the relative distance difference and the cost function.Source: §3.2 · p. 10
  • SNG adapts same-class prototypes according to rank and moves the nearest different-class prototype away; SGNG selects an adaptive number of prototypes.H2MLVQ updates all prototypes using harmonic-average distances, and these methods address sensitivity to prototype initialization.Source: §3.2 · pp. 10–11
  • CSDLVQ uses a Cauchy–Schwarz divergence with Parzen density estimates and fuzzy class labels for information-theoretic optimization.The review describes this as a numerically well-behaved approach to information optimization in prototype-based vector quantization.Source: §3.2 · p. 11

3.2.1 Distance Learning Approaches

  • GRLVQ and GMLVQ adapt the distance metric while deriving prototype updates from the GLVQ relative-distance rule.GMLVQ updates both prototypes and its matrix parameters.Source: §3.2.1 · p. 11

3.2.2 Kernel Approaches

  • KGLVQ applies GLVQ in a nonlinearly mapped feature space, while AKGLVQ adds sparsity and a Nyström approximation to reduce learning complexity on large datasets.Kernel prototypes are represented implicitly through coefficients.Source: §3.2.2 · p. 12

3.2.3 Dis-/similarities Approaches

  • RGLVQ extends margin maximization to dissimilarity data by representing prototypes implicitly.Its updates begin from the GLVQ rule and use distances computed from the dissimilarity representation.Source: §3.2.3 · pp. 12–13

3.3 Methods Based on Likelihood Ratio Maximization

Likelihood-ratio LVQ derives prototype updates by maximizing a likelihood-ratio cost through gradient ascent. Extensions adapt distances, move the method into kernel feature spaces, or represent prototypes through dissimilarities.

3.3 Methods Based on Likelihood Ratio Maximization

  • RSLVQ derives prototype updates by maximizing the likelihood-ratio cost through gradient ascent; changing its function f extends the approach to other distance measures.The update uses assignment probabilities for the sample and its class.Source: §3.3 · p. 13

3.3.1 Distance Learning Approaches

  • MRSLVQ adds matrix distance learning to RSLVQ, and LMRSLVQ adapts a full relevance matrix locally for each prototype.The approach uses a conditional probability density for the component generating a data point.Source: §3.3.1 · pp. 13–14

3.3.2 Kernel Approaches

  • KRSLVQ extends RSLVQ to kernel feature space, representing prototypes as linear combinations of data images and measuring Euclidean distance there.It retains the Gaussian mixture model assumption.Source: §3.3.2 · p. 14

3.3.3 Dis-/similarities Approaches

  • Relational RSLVQ extends likelihood-ratio maximization to a pseudo-Euclidean space using dissimilarity data and implicit prototype representations.The prototypes are represented through linear combinations of data points.Source: §3.3.3 · p. 15

4 Results

The review compares eleven LVQ classifiers on two artificial datasets and USPS using 10-fold cross-validation and pairwise statistical comparisons. Which methods perform best varies by dataset: H2M-LVQ leads on the multi-modal data, LGMLVQ on Image Segmentation, and the likelihood-ratio methods on USPS*; SNG performs best on USPS.

4 Results

  • The comparison covered eleven classifiers on Multi-modal, Image Segmentation, and USPS datasets, using 10-fold cross-validation and a multiple-comparison test.The test compared pairs of classifier means with a Bonferroni adjustment.Source: §4 · pp. 15–16

4.1 Multi-modal dataset

  • H2M-LVQ, SNG, SGNG, and GLVQ performed best on the multi-modal dataset; H2M-LVQ was significantly better than six classifiers.Four classifiers were not significantly different from H2M-LVQ, while LVQ 2.1 performed worse than the others.Source: §4.1 · p. 18, Table 3 · p. 18

4.2 Image Segmentation dataset

  • 0.0357: LGMLVQ had the lowest mean classification error on Image Segmentation and significantly outperformed six algorithms.LGMLVQ was not significantly different from GLVQ, GRLVQ, SNG, or GMLVQ; matrix learning outperformed relevance learning among the local distance-learning methods.Source: §4.2 · pp. 18–19

4.3 USPS dataset

  • 0.0415: RSLVQ had the best mean classification error on USPS*, while RSLVQ and KRSLVQ were not significantly different; SNG performed best on USPS.On USPS*, both likelihood-ratio methods significantly outperformed six other algorithms; on USPS, SNG was followed by H2M-LVQ.Source: §4.3 · p. 19

5 Open Problems

The review identifies methodological, computational, data-labeling, and interpretability challenges for LVQ classifiers.

Principled Approach to LVQ and Sparsity

  • GLVQ’s cost function is not derived from probabilistic or information-theoretic first principles.The review also notes growing computational cost as real-world datasets grow, while citing sparsity approaches that allow linear training time without losing classification performance.Source: §5 · p. 19

Principled Approach to LVQ

  • The review identifies developing principled LVQ cost functions as an open challenge.Although GLVQ has a cost function and can be shown to maximize margins, the review says that function is not derived from first principles.Source: §5 · p. 19

Semi-supervised learning and Active learning

  • LVQ classifiers need adaptation to semi-supervised or active learning because real-world datasets cannot all be labeled.The review frames this as a consequence of increasing dataset size.Source: §5 · p. 20

Visualization of LVQ classifiers

  • Kernelized and relational LVQ are less easily visualized and interpreted when they operate outside the data space.The review presents preserving the interpretability associated with prototypes in the input space as an open problem.Source: §5 · p. 20

Active learning

  • Active learning lets the learner select training samples and can increase generalization ability and learning speed.The review presents active learning as a possible way to improve prototype-based methods.Source: §5 · p. 20

6 Conclusions

The review finds that LVQ methods have distinct strengths for different data conditions, with no single method suited to every dataset. It concludes that LVQ classifiers are competitive, while further research is needed for pattern-recognition tasks.

Conclusions

  • Margin-maximizing LVQ can perform well but is less flexible with overlapping data, while likelihood-ratio methods offer a probabilistic alternative.The review says margin-based methods place prototypes at class centroids, whereas likelihood-ratio methods do not.Source: §6 · p. 20
  • Adaptive-metric LVQ has achieved the best performance on heterogeneous-feature datasets.The review also reports that methods updating multiple prototypes per iteration are less sensitive to initialization and perform better on multi-modal datasets.Source: §6 · p. 20
  • LVQ methods have no free lunch: each has pros and cons and was designed for specific problems and datasets.The review also says kernelized and relational approaches use data representations for more complex data, with relational LVQ supporting non-Euclidean spaces.Source: §6 · p. 20
  • LVQ classifiers are very competitive, and further research is needed for greater success in pattern-recognition tasks.Source: §6 · p. 21
Loading 1509.07093v1…