Self-organizing maps
by Manfred Füllsack
This model demonstrates the operation of self-organizing maps (SOMs), aka Kohonen neural networks. For a back-propagation neural network look here.
Self-organizing maps (SOMs) are Artificial Neural Networks that - other than Backpropagation Networks - operate unsupervised. This means that they do not need any external trainer or teacher providing an expected output - a learning target - in order to learn. Self-organizing maps look for structures in given data on their own and organize according to what they find. In this, they are thought to come close to the way the human brain is operating.
Pushing one of the buttons <RGB-map>, <Unfolding net>, <TSP> or one of the buttons under the label <Time series> generates various kinds of input data which the SOM is supposed to screen for structure and to organize according to it. The <go>-button starts the learning process. The <one step>-button lets you follow this process one step at a time.
The <RGB-map>-button generates a random order of squares with different colors given in RGB-format. The RGB-values of the colors (that is the value for the red-, green- and blue-component of the colors) are arranged in the form of vectors which serve as input-data. The SOM's neurons have correspondingly dimensioned vectors of which the values - the "weights" - initially are randomly ascribed. The neurons thus are considered sort of connected to the input-data by links with different weights. When starting the learn-process, a randomly chosen input-datum, that is one of the colored squares, compares its vector, i.e. its RGB-values, with the vectors (the values or "weights") of each neuron. To compare means to calculate the Euclidean distance of the two vectors. The neuron with the shortest Euclidean distance to the input then is chosen as the Best Matching Unit (BMU).
For the neuron, being a BMU means to be the current center of an rapprochement process of the neurons towards the active input-datum. The weights of the BMU and in some minor extent the weights of the neurons within a certain radius of the BMU are altered by a certain learn-rate in order to come a little bit closer to the input-datum (that is in this case, to the values of the RGB-colors of the currently active square). The farther the neighboring neurons are from the BMU, the less their weights are altered. The decline of this altering impact is calculated as exp(- d 2 / 2 * l) , where d denotes the distance of the neurons from the BMU within a certain radius, and l denotes the learn-rate.
After this first rapprochement the next input-datum (another colored square) is chosen and subjected to the same calculation. This is done until all data have been considered in a first learn-step and the process starts from the beginning again. In this way, input-data are being repeatedly processed, each time however in respect to a slightly reduced radius and a slightly reduced learn-rate. (In the model, the reduction of radius and learn-rate are calculated as i * exp ( - t / (n / log r 2)) , where i is the initial-radius, respectively the initial-learnrate, t stands for ticks and denotes the number of passed learn-steps, n is a value around 1000 that itself is reduced by a certain amount after each round of calculating all input-data, and r is the radius as it currently stands).
Instead of RGB-values, the <Unfolding net>-example uses the coordinates of invisibly ordered patches on the display as input-data. The neurons in their turn (positioned at the knots of the net that is to unfold) consider their own (initially randomly assigned) coordinates on the display as "weights" in the above described sense and alter them iteratively in respect to their status as BMU or as one of their neighbors. When pushing the <Unfolding net>-button a randomly folded neural network is generated in the center of the display that gradually seems to unfold in the process of "learning". Note, that depending on the initial folding, the net, when unfolding, can get trapped in entanglement. In this case, the radius of considered neighboring neurons has been too small or has been decreasing too fast, which hints to the fact that SOMS seldom yield optimal, but often "pretty good" solutions.
In the same way - again using coordinates as input-data and as weights that are being altered - , the SOM approximates solutions for the Travelling Salesman Problem. Pushing the <TSP>-button generates a "geography" of points, considered cities, that a fictive salesman is supposed to visit without visiting a city twice and without repeating parts of his journey. The aim is to keep the journey as short as possible. But to find an optimal solution is a so-called np-complete problem, that is a problem of combinatorial complexity for which the time required to solve it using any known algorithm can be larger than feasible. The worst case running time for a brute force solution on current computers (- that is for just permuting all possible combinations in order to find the shortest -) can rapidly reach astronomical dimensions. Just 15 cities for example will allow 43 589 145 600 different journeys. A SOM can not find the optimal solution, but it can - in relatively short time - approximate solutions which are acceptable considered the scale of the problem. The <cities>-slider lets you define the number of cities, and the <Same map>-button lets you search the same geography again.
Moreover SOMs can "learn" (and within certain limits also predict) Time series. To illustrate this, the buttons beneath the label <Time series> generate various curves that the neural network - now in a two-dimensional representation (as thin white line) - is supposed to "learn". If you move the speed-slider on top of the display slightly to the left (or alternatively if you use the <one step>-button), the gradual approach of the neurons (i.e. of the BMU and in respective minor extent of its neighbors) towards the curve becomes visible in action.
An other kind of artificial neural networks are backpropagation neural networks. An applet and a description can be found here.
Coded by Manfred Füllsack (source code on demand), Aug 2009 (to be improved and continued)
Literature:
Rojas, Raul (1996): Neural Networks - A Systematic Introduction. (Foreword by Jerome Feldman) Berlin, New-York: Springer.
Buckland, Mat (?): Kohonen's Self Organizing Feature Maps
Heaton, Jeff (2007): Introduction to Neural Networks with Java
And for the scope of the subject see also:
Edelman, Gerald M. (2004): Wider than the Sky. A Revolutionary View of Consciousness. London: Pinguin.
Edelman, Gerald M. (2006): Second Nature. Brain Science and Human Knowledge. Yale.