Self-organizing map

Overview

A self-organizing map (SOM) is a type of artificial neural network that is trained using unsupervised learning to produce low-dimensional representation of the training samples while preserving the topological properties of the input space.

File:Synapse Self-Organizing Map.png

Self-Organizing Map showing US Congress voting patterns visualized in Synapse. The first two boxes show clustering and distances while the remaining ones show the component planes. Red means a yes vote while blue means a no vote in the component planes (except the party component where red is Republican and blue is Democrat.)

This makes SOM useful for visualizing low-dimensional views of high-dimensional data, akin to multidimensional scaling. The model was first described as an artificial neural network by the Finnish professor Teuvo Kohonen, and is sometimes called a Kohonen map.

Like most artificial neural networks, SOMs operate in two modes: training and mapping. Training builds the map using input examples. It is a competitive process, also called vector quantization. Mapping automatically classifies a new input vector.

Network structure

A self-organizing map consists of a single-layer feedforward network where the outputs are arranged in low dimensional (usually 2D or 3D) grid. Each input is connected to all output neurons. Attached to every neuron is a weight vector of the same dimension as the input vectors. The number of input dimensions is usually much higher than the output grid dimension. SOMs are mainly used for dimensionality reduction rather than expansion.

Learning algorithm

The goal of learning in the self-organizing map is to cause different parts of the network to respond similarly to certain input patterns. This is partly motivated by how visual, auditory or other sensory information is handled in separate parts of the cerebral cortex in the human brain.

The weights of the neurons are initialized either to small random values or sampled evenly from the subspace spanned by the two largest principal component eigenvectors. With the latter alternative, learning is much faster because the initial weights already give good approximation of SOM weights.

The network must be fed a large number of example vectors, that as much as possible represent the kind of vectors expected during mapping. The examples are usually administered several times.

The training utilizes competitive learning. When a training example is fed to the network, its Euclidean distance to all weight vectors is computed. The neuron with weight vector most similar to the input is called the best matching unit (BMU). The weights of the BMU and neurons close to it in the SOM lattice are adjusted towards the input vector. The magnitude of the change decreases with time and with distance from the BMU. The update formula for a neuron with weight vector Wv(t) is

Wv(t + 1) = Wv(t) + Θ (v, t) α(t)(D(t) - Wv(t)),

where α(t) is a monotonically decreasing learning coefficient and D(t) is the input vector. The neighbourhood function Θ(v, t) depends on the lattice distance between the BMU and neuron v. In the simplest form it is one for all neurons close enough to BMU and zero for others, but a gaussian function is a common choice, too. Regardless of the functional form, the neighbourhood function shrinks with time. At the beginning when the neighbourhood is broad, the self-organizing takes place on the global scale. When the neighbourhood has shrunk to just a couple of neurons the weights are converging to local estimates.

This process is repeated for each input vector for a (usually large) number of cycles λ. The network winds up associating output nodes with groups or patterns in the input data set. If these patterns can be named, the names can be attached to the associated nodes in the trained net.

During mapping, there will be one single winning neuron: the neuron whose weight vector lies closest to the input vector. This can be simply determined by calculating the Euclidean distance between input vector and weight vector.

Example

Preliminary definitions

Consider a 10×10 array of nodes each of which contains a weight vector and is aware of its location in the array. Each weight vector is of the same dimension as the node's input vector. The weights are initially set to random values.

Now we need input to feed the map. (The generated map and the given input exist in separate subspaces) We will create three vectors to represent colors. Colors can be represented by their red, green, and blue components. Consequently our input vectors will have three components, each corresponding to a color space. The input vectors will be:

R = <255, 0, 0>
G = <0, 255, 0>
B = <0, 0, 255>

Variables

Vectors are in bold

t = current iteration
λ = limit on time iteration
Wv = current weight vector
D = target input
Θ(t) = restraint due to distance from BMU - usually called the neighbourhood function
α(t) = learning restraint due to time

Stepping through the algorithm

1. Randomize the map's nodes' weight vectors
2. Grab an input vector
3. Traverse each node in the map
   1. Use Euclidean distance formula to find similarity between the input vector and the map's node's weight vector
   2. Track the node that produces the smallest distance (this node is 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))
5. Increment t and repeat while t < λ

Interpretation

There are two ways to interpret a SOM. Because in the training phase weights of the whole neighborhood are moved in the same direction, similar items tend to excite adjacent neurons. Therefore, SOM forms a semantic map where similar samples are mapped close together and dissimilar apart.

The other way is to think of neuronal weights as pointers to the input space. They form a discrete approximation of the distribution of training samples. More neurons point to regions with high training sample concentration and fewer where the samples are scarce.

See also

• Artificial intelligence
• Biologically-inspired computing
• Connectionism
• Data mining
• Growing Self Organizing Map
• Growing neural gas
• Generative Topographic Map
• Machine learning
• Pattern recognition
• Predictive analytics
• Radial basis function network
• Artificial Neural Network
• Sammon's projection

External links

• Chapter 15 Kohonen networks of Neural Networks - A Systematic Introduction by Raul Rojas (ISBN 978-3540605058)
• Prof. Kohonen's website in Helsinki University of Technology See ->research ->software for Toolkits and C and Matlab code for SOM's
• Kohonen network a Scholarpedia article on the Self-Organizing Map
• "The Self-Organized Gene, Part 1", and Part 2 beginners' level introduction to competitive learning and self-organizing maps.
• Chapter 7: Competition and self organisation: Kohonen nets, part of Kevin Gurney's web-book on Neural Nets.
• Nice application to visualize some neural-network algorithms. Written in Java, so you need a Java-plugin in your browser.
• Programming a Kohonen Neural Network in Java part of a Java Neural Network web book.
• Databionics Prof. A. Ultsch's websites on Visualization and Datamining with SOM
• Kohonen Neural Network applied to the Traveling Salesman Problem (using three dimensions).
• Python SOM example: Simple SOM replace.py library along with a 2D implementation and some very suggestive images.
• Viscovery SOMine: SOM Technology Tool from Viscovery Software (formerly Eudaptics Software)
• SomColour tutorial: Self-Organising Maps For Colour Recognition
• WEBSOM, a Kohonen network project
• Staff-Mapper, Solution for mapping knowledge based on survey results
• Kohonen Neural Network Simulation, Demonstration of and detailed discussion about Kohonen Neural Networks, a form of SOM
• The Semantic Map Interface based on Kohonen Map for Text analysis and visualization on netzspannung.org- the german platform for media art & electronic culture.