Kristof Van Laerhoven

Parallel Implementation of

the Self Organizing Map

about the algorithm

the parallel implementation

the results (data & plots)

the source code

The algorithm: Self-Organizing Map (SOM)

The (Kohonen) Self-Organizing Map is an unsupervised neural network that can be used in various applications. It has only one (output) layer of neurons, that organises itself according to the inputs that are being presented. The neurons in this layer ‘compete’ for every input, but only one neuron can win (winner-take-all). The winner is found by comparing the weights of every neuron to the current input: the neuron that has the smallest (Euclidean) distance between these two vectors has won the competition. This winning neuron is allowed to adapt its weights towards the input, thus increasing the chance that it will win for a similar input in the future. The neurons in the neighbourhood of the winner are also allowed to update their weights, but in a lesser degree.

So the algorithm looks like this:

1. Initialise the weights for every neuron to small random values
2. present an input vector to the neural network
3. calculate the distances between this input vector and the weights of every neuron
4. find the minimal distance and select the corresponding neuron as the winner
5. update the weights of the winner
6. update the weights of the neighbours
7. go to step 2

Kohonen SOMs are usually implemented to visualise the density of complex, multi-dimensional data, but also for clustering and classifying data and even principal component analysis. A large variety of improvements of the classic Kohonen Self-Organizing Map exist that make it an important and often-used algorithm.

References:

1. Hertz, J., Krogh, A., and Palmer R.G. (1991) Introduction to the Theory of Neural Computation. Addison-Wesley
2. Kohonen, T. (1989) Self-Organization and Associative Memory. Berlin: Springer-Verlag.
3. Lau, C. (1992) Neural Networks: Theoretical Foundations and Analysis. New York IEEE Pres.

The parallel implementation

The architecture of the parallel algorithm was based on a master-slave structure, having one process (the master) that controls several other processes (slaves). The master sends the data for processing purposes to all slaves, which do the necessary calculations and send the results back to the master. The slaves operate independent of each other, doing the processing in parallel.

In this particular case, the master is responsible for sending the input data to the slaves, which calculate the minimal distance for a part of the output layer. The slaves send their results back to the master, where the global minimum distance is searched. The results of this search are then broadcast to the slaves, which now have sufficient information to update their weights.

Graphic representation of the Master–Slave relationship

Results

The measurements were done on Crunch, a machine connected to eight-processors, specifically designed for running parallel tasks. The SOM program was executed for a variable number of processors (up to nine), and a variable dimension of the problem N (= the size of the competitive layer, for 10, 20, …, till 100 ). All results are written down in microseconds.

Data:

Calculated Speed-up (T₁/T_N):

Plots of the data:

Source Code

Master.c

Slave.c