Self-organizing map

unsupervised learning, based on a grid of artificial neurons whose weights are adapted to match input vectors in a training set. It was first described by Teuvo Kohonen, and so is sometimes referred to as a Kohonen map.

A mathematical approach to the algorithm

Preliminary definitions

The actual training of the net is called vector quantization. "Unsupervised learning" is, technically, supervised in that we do have a desired output.

To explain the algorithm in-depth, let us create a 10x10 array of nodes. Each node will contain a weight vector, and will be omniscient of its "physical location", i.e. its location in the array. The weight vector each node contains will be of the same dimension as the following input vectors. (N.B. Weights in the nodes in the map are initially set to random values.)

Now we need input to feed the map. (Note: the generated map and the given input exist in separate subspaces!) Sticking with the norm, we will create three vectors to represent colors. In the world of computing, colors have the following three components: red, green, and blue. Consequently our input vectors will have three components, each one corresponding to a color space. Our input vectors will now be thus...

Some variables

Vectors are in bold

Stepping through the algorithm

1. Randomize the map's node's weight vectors
2. Grab an input vector
3. Traverse each node in the map
   1. Use Euclidean distance formula to find similarity
   2. Track the node that produces the smallest distance (this node will be called the Best Matching Unit (BMU)
4. Update the nodes in the neighbourhood of BMU by pulling them closer to the input vector
   1. Wv(t + 1) = Wv(t) + Θ(t)α(t)(D(t) - Wv(t))

An analytic approach to the algorithm

The SOM algorithm is fed with feature vectors, which can be of any dimension. In most applications, however, the number of dimensions will be high. Output maps can also be made in different dimensions: 1-dimensional, 2-dimensional, etc., but most popular are 2D and 3D maps, for SOMs are mainly used for dimensionality reduction rather than expansion.

The algorithm is explained most easily in terms of a set of artificial neurons, each having its own physical location on the output map, which take part in a Euclidean distance between input vector an weight vector.)

An alternative to the self-organizing map, called the generative topographic map (GTM), was presented in 1996 in a paper by Bishop, Svensen, and Williams. The GTM is a probabilistic counterpart to SOM, which is provably convergent and does not require a shrinking neighborhood or a decreasing step size. The GTM is a Expectation-Maximization (EM) algorithm.