Learning/Machine/LVQ

Learning Vector Quantization (LVQ)

Background

Vector quantization us a technique that exploits the underlying structure of input vectors, for the purpose of data compression. More specifically, the input space is divided up into a number of distinct regions, and for each region, a reconstruction vector is defined.

Imagine the following 2-dimensional input space...

 <<<— TODO: Add Image: /srv/trac/ai/htdocs/images/sink/lvq-input-space.png —>>> 

The input space is then divided and could look something like this...

 <<<— TODO: Add Image: /srv/trac/ai/htdocs/images/sink/lvq-divided.png —>>> 

The (Vector) Quantizer

When the quantizer is presented a new input vector, it carries out the following two steps...

  1. It first locates the region in which the new vector lies.
  2. The reproduction vector for that specific region is represented.

Thus, by using an encoded version of the original input vector (e.g. for storage, or transmission), considerable bandwidth (e.g. storage, or transmission) can be realized. Of course, this comes at a cost; detail-loss, or more specifically - information-loss. This loss, or distortion, is how lossy compression is achieved.

Definition

The Quantizer's Codebook

  1. The collection of possible reproduction vectors is called the code book of the quantizer; it's members are called code words.
  2. When compressing data by representing vectors by the labels of a relatively small set of reconstruction vectors, the set of reconstruction vectors is called the code book.

Voronoi & Voronoi Cells

A vector quantizer with its encoding distortion minimized, is called a Voronoi, or nearest-neighbor quantizer, since the Voronoi cells about a set of points in an input space correspond to a partition of that space, according to the nearest neighbor rule based on Euclidean metric (Gersho and Gray, 1992). The Voronoi vector, i.e., the reconstruction vector, are then learned in such a way as to be closest (in a Euclidean sense) to the vectors of original input space, for each Voronoi cell, among the totality of such points.

This is best illustrated with a diagram...

 <<<— TODO: Add Image: /srv/trac/ai/htdocs/images/sink/lvq-vernoi.png —>>> 

Learning Vector Quantization

So now, what is LVQ then?

LVQ is a supervised learning technique that uses class information to move the Voronoi vectors slightly, so as to improve the quality of the classifier decision regions.

The Algorithm

Here, wc represents the closes Voronoi vector to the input vector x, and n represents a time-step. Cwc represents the class of wc, and Cx represents the class of x (and each class is defined by the Voronoi cell).

  • An input vector 'x is picked at random from the input space.
  • If the class labels of a Voronoi vector w and the input vector x agree (i.e. Cwc = Cx), the Voronoi vector w is readjusted by being moved towards the input vector x.

    • Formula

      wc(n+1) = wc(n) + αn[xi - wc(n)]

  • Conversely, if the class labels of a Voronoi vector w and the input vector x disagree (i.e. Cwc ≠ Cx), the Voronoi vector w is readjusted, by being moved away form the input vector x.

    • Formula

      wc(n+1) = wc(n) - αn[xi - wc(n)]

It is desirable for the learning constant αn to be small (e.g. 0.1 or smaller), and decreased monotonically with the number of epochs n. After several sweeps (complete passes of the input data) through the input data, the Voronoi vectors typically converge, and the training is complete.

Difficulties may arise if the method is applied without proper care.  <<<— TODO: Give an example —>>> 

LVQ & SOM

In order to use LVQ, a set of approximate reconstruction vectors is first found using the unsupervised SOM algorithm. The supervised LVQ algorithm is then used to fine-tune the vectors found using SOM.

References

Ancestors ☣ Learning ☣ Learning/Machine
Other ☣ Learning/Machine/SOM