Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Learning Vector Quantization (LVQ)

English · فارسی

Learning Vector Quantization (LVQ)

Computer Science Dept, Ferdowsi University of Mashhad

Where this page sits

Chapter 13 of Hastie et al. (2009) is about prototype methods: instead of fitting a parametric model, keep a small set of points in feature space and classify by proximity to them. The chapter develops three of them in turn:

methodprototypes are placed usingsupervision
K-means clustering (§13.2.1)the geometry of each class separatelylabels used only after clustering
LVQ (§13.2.2)the geometry of all classes at oncelabels used during training
Gaussian mixtures (§13.2.3)a density model per classsoft, likelihood based

This page follows §13.2.2. It states the classifier, gives the algorithm (Algorithm 13.1 of the book), implements it from scratch in a few lines of NumPy, and compares the prototypes it produces with the ones K-means produces on the same data — the comparison the book makes in Figure 13.1.

What you should be able to do at the end

  • state the nearest-prototype classifier and say what the prototypes are;

  • write the LVQ1 update rule from memory and explain the sign of the two branches (attract / repel);

  • explain why the learning rate has to go to zero, and why K-means prototypes are a good starting point;

  • describe how K-means prototypes differ from LVQ prototypes in a picture, and why the difference is a consequence of who “has a say” in placing them;

  • name the price the method pays for being defined by an algorithm rather than by the minimisation of a criterion.

1. The nearest-prototype classifier

Fix a number of prototypes per class, R, and let K be the number of classes. Training produces K*R prototypes m_1, ..., m_{K*R}, each carrying a class label c_j. A new point x is classified by the label of the closest prototype:

G^(x)=cj∗,j∗=arg⁡min⁡j=1,…,KR∥x−mj∥.\hat G(x) = c_{j^*}, \qquad j^* = \arg\min_{j=1,\dots,KR} \lVert x - m_j \rVert .

Two things make this attractive for teaching and for practice: the decision boundary can be arbitrarily curved (it is a union of Voronoi cells), and the model is just a list of points, so it can be drawn, stored and explained. Everything difficult is in the question where to put the prototypes, and that is where the methods differ.

The book standardises the features to mean 0 and variance 1 before using Euclidean distance (p. 461), and so do we.

2. The problem that LVQ is answering

The straightforward recipe of §13.2.1 is: cluster the training data of each class separately with R centres, keep all centres, and classify by the nearest one. It works, and it has a visible weakness that the book points out (p. 462):

… prototypes are near the class boundaries, leading to potential misclassification errors for points near these boundaries. This results from an obvious shortcoming with this method: for each class, the other classes do not have a say in the positioning of the prototypes for that class.

A prototype computed inside one class has no idea that another class is nearby, so it is happy to sit on the frontier. LVQ fixes exactly this: the update rule sees the label of the training point and the label of the nearest prototype, so a prototype that is winning points of the wrong class is pushed away.

3. A simulated three-class problem

To see the difference we need data where the classes touch, since with well-separated classes every method looks the same. We use the simulation of ESL §2.3.3 — the one behind Figure 13.1 — with three classes instead of two:

  • three classes, two features;

  • each class has 10 means, drawn from a normal distribution centred at a class-specific location — (1.5,0), (0,1.5) and (1.5,1.5) — with covariance I/4;

  • each observation is generated by picking one of the ten means at random (probability 1/10) and adding Gaussian noise with covariance I/5.

This is the “model somewhere between the two scenarios” of p. 16: the classes are neither linearly separable nor far apart, and the Bayes boundary is genuinely curved. The spread of the ten means (I/4) is narrower than the book’s I, which keeps the problem hard without making it hopeless: even a good rule errs on a sizeable fraction of the points, but nothing like the two-in-three of a coin toss among three classes.

Source
Source
((300, 2), array([100, 100, 100]))
Source
<Figure size 600x500 with 1 Axes>

4. K-means prototypes (the starting point)

R = 5 prototypes per class, produced by clustering the points of each class separately. Every prototype inherits the label of the class it was computed in.

Source
prototypes: (15, 2)
<Figure size 600x500 with 1 Axes>

5. The LVQ algorithm

Algorithm 13.1 (Learning Vector Quantization — LVQ), as printed in Hastie et al. (2009), p. 462

  1. Choose R initial prototypes for each class m_1^(k), ..., m_R^(k), k = 1..K — for example by sampling R training points at random from each class, or by running K-means on each class.

  2. Sample a training point x_i at random (with replacement), and let (j,k) index the closest prototype m_j^(k) to x_i.

    • (a) If g_i = k — the same class — move the prototype towards the training point:

      mj(k)←mj(k)+ε (xi−mj(k))m_j^{(k)} \leftarrow m_j^{(k)} + \varepsilon\,(x_i - m_j^{(k)})
    • (b) If g_i != k — a different class — move the prototype away from the training point:

      mj(k)←mj(k)−ε (xi−mj(k))m_j^{(k)} \leftarrow m_j^{(k)} - \varepsilon\,(x_i - m_j^{(k)})
  3. Repeat step 2, decreasing the learning rate ε with each iteration towards zero.

Three remarks that the book makes next:

  • LVQ is an online algorithm: observations arrive one at a time, and each one updates a single prototype.

  • The decay of ε must obey the stochastic-approximation conditions of §11.4 (ε_t -> 0, sum ε_t = infinity, sum ε_t^2 < infinity); a schedule such as ε_t = ε_0 / (1 + t) satisfies them.

  • The procedure above is LVQ1; variants (LVQ2, LVQ3) exist. A drawback of the whole family is that they are defined by an algorithm rather than by the minimisation of a fixed criterion, which makes their properties harder to analyse. Newer cost-function-based versions (generalised LVQ) were invented precisely to repair this.

The book also uses the K-means solution as the starting values, and gets the result shown in its Figure 13.1 (lower panel): the prototypes have moved away from the decision boundaries and away from prototypes of competing classes.

Source
Source
training error before LVQ: 0.240
training error after  LVQ: 0.170
<Figure size 1200x500 with 2 Axes>

Look at the stars in the two panels. In the left one several prototypes sit inside the territory of another colour; in the right one they have been pulled into their own region and pushed away from the frontier. That is the whole effect of the sign in step 2, repeated a few thousand times.

Source
<Figure size 700x400 with 1 Axes>

Measuring “away from the boundary”

A single number makes the claim checkable: for every prototype, compute the distance to the nearest prototype of a different class, and take the median. LVQ should increase it, because a prototype that is close to an enemy is the one the repel step keeps hitting.

Source
median distance to the nearest other-class prototype
  before LVQ : 0.800
  after  LVQ : 1.493

6. Does it help on unseen data?

Prototypes that leave the training points can also leave the useful ones, so the training error alone proves nothing. The honest test is a fresh sample from the same distribution, which we generated with a different seed.

Source
prototypes              train error  test error
K-means prototypes            0.240       0.277
LVQ1 prototypes               0.170       0.227

The numbers move by a few points, in the direction the book describes, and the size of the improvement is itself part of the lesson: LVQ is a cheap, local repair of a K-means solution, not a different model class. Where the classes are well separated it changes almost nothing; where they overlap, it redraws the frontier.

7. Practical notes

Initialisation. ESL starts from the K-means solution, and so should anyone in practice: starting from random training points leaves far more work for the online updates. The next cell shows the difference on the same data.

Learning rate. ε_0 sets how far a prototype moves on one observation; epochs sets how long the schedule runs. Too large and the prototypes oscillate, too small and they never arrive. ε_t = ε_0/(1+t) is a safe default.

R, the number of prototypes per class. More prototypes give a finer boundary and a larger model; R = 1 reduces LVQ to a nearest-centroid classifier, and the update rule to a perceptron-like correction of the centroids.

Feature scaling. Euclidean distance is meaningless without it; standardise as ESL does, with the training statistics.

Sampling with replacement. Step 2 draws a random training point every time, not a pass over a shuffled list, so classes with more points are seen more often. For imbalanced data that is a bias worth knowing about.

Source
random start, eps0=0.1     test error = 0.250
k-means start, eps0=0.1    test error = 0.227
k-means start, eps0=0.5    test error = 0.207

8. On real data: the iris flowers

Four features, three classes, R = 3 prototypes per class. With R equal to the class count and well-behaved data the prototypes end up near the class means, so LVQ has little to repair — which is exactly why the simulated problem above was needed to see the effect.

Source
nearest centroid (R=1)     test error = 0.244
K-means prototypes (R=3)   test error = 0.000
LVQ1 prototypes (R=3)      test error = 0.000

9. Where the name comes from

“Quantization” is the older idea behind the method: replace a vector by the index of the nearest prototype and store only that index. With K prototypes each index costs log2(K) bits instead of the bits of a whole vector, so the prototype set becomes a codebook and the method becomes lossy compression.

The name survives in the title of LVQ, but the compression application is a different lesson: it uses K-means with no labels at all and is measured in bits and decibels rather than in error rates. It therefore has a page of its own:

Vector Quantization and Image Compression — ESL §14.3.9, with the rate/distortion trade-off measured on a test image.

Summary

  • A prototype method classifies by the label of the closest prototype; K*R prototypes encode a curved decision boundary.

  • Clustering each class on its own (§13.2.1) puts prototypes where that class is dense, with no regard for the others, so they drift onto the boundaries — the shortcoming the book names explicitly.

  • LVQ (§13.2.2) is online and label-aware: the point attracts the closest prototype of its own class and repels the closest prototype of another class, with a step ε that decays to zero.

  • This is LVQ1; LVQ2, LVQ3 extend it, and the family has no fixed objective function — that is the method’s price.

  • Starting from the K-means prototypes (ESL’s choice) is far better than starting from random points, and the effect of LVQ is a local repair of the boundary.

  • The same “nearest prototype + store the index” idea, applied to image blocks, is vector quantization: the origin of the name, and a compression method with a page of its own.

Exercises

  1. Set R = 1 and run LVQ on the simulated data. What does the update rule become, and why does the boundary stay almost straight?

  2. Replace the schedule ε_t = ε_0/(1+t) by a constant ε = 0.1. Plot the training error against the epoch: what do you see, and which of the three stochastic-approximation conditions is violated?

  3. Use R = 2, 5, 10, 20 prototypes per class and plot the test error. Where does the curve flatten, and what is the cost per prototype?

  4. Attract-only variant: delete the repel branch and train from the K-means start. Explain the result in terms of the book’s sentence about who has a say in the placement of prototypes.

  5. Calculate the Bayes error of the simulated problem analytically (or estimate it with a very large 1-NN model) and compare it with the errors of the two prototype sets.

  6. For the compression experiment, try bs = 2 and bs = 8 with the same number of bits per pixel. Which block size gives the better picture, and why is tile structure visible in the reconstruction?

Sources

  • The method, its algorithm (Algorithm 13.1) and the simulated example: §13.2.2 and §13.2 of Hastie et al. (2009) (2nd edition, pp. 461–463); the compression application is on its own page (§14.3.9 of the same book). Figures on this page are generated by the code above, reproducing the comparison of ESL Figure 13.1.

  • Kohonen’s original LVQ papers are the references given there; the GLVQ reformulation is the cost-function-based repair of the “no fixed criterion” objection.

  • sklearn.cluster.KMeans documentation for the implementation used to build the initial prototypes.

References
  1. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer. 10.1007/978-0-387-84858-7