Learning Vector Quantization

The aim of learning vector quantization (LVQ) is to find vectors within a multidimensional space that best characterise each of a number of classifications. One use of the output vectors is as a minimal reference set for the nearest neighbour algorithm.

The algorithm requires a multidimensional space that contains pre-classified training data. Into this space are placed a number of movable vectors which are themselves distributed among the classes present in the training data (1…n movable vectors for each class). Placement can either occur at random or (as an optimization) based on some theory as to where the vectors are likely to end up. Then:

• a training data item is chosen at random;
• the class of the training data item is compared with the class of the closest movable vector;
• if the classes agree, the movable vector is moved towards the training data item;
• if they disagree, the movable vector is moved away from the training data item.

The aim is that the movable vectors should end up at their centres of their respective classes. However, because this is not mathematically provable and may not always work in practice if the classes are not clearly delineated within the vector space. For this reason, other algorithms are likely to perform better than LVQ in most scenarios.

The learning rate is the distance that the movable vectors are moved with each step. If it is constant, learning has to be stopped after an arbitrarily chosen number of steps because otherwise the vectors will never stop moving. To prevent this problem, it is also possible gradually to reduce the learning rate as the number of completed steps increases.

LVQ is a relatively old algorithm that was first discovered within the context of neural networks and is often described in terms of them; the way an individual neuron within some neural networks such as perceptrons is trained is isomorphic to the vector-based description above.