Self Organizing Maps: Fundamentals

1 Self Organizing Maps: FundamentalsIntroduction to Neural Networks : Lecture 16 John A. Bullinaria, 20041. What is a Self Organizing Map?2. Topographic Maps3. Setting up a Self Organizing Map4. Kohonen Networks5. Components of Self Organization6. Overview of the SOM AlgorithmL16-2 What is a Self Organizing Map?So far we have looked at networks with supervised training techniques, in which there is atarget output for each input pattern, and the network learns to produce the required now turn to unsupervised training, in which the networks learn to form their ownclassifications of the training data without external help. To do this we have to assume thatclass membership is broadly defined by the input patterns sharing common features, andthat the network will be able to identify those features across the range of input particularly interesting class of unsupervised system is based on competitive learning,in which the output neurons compete amongst themselves to be activated, with the resultthat only one is activated at any one time.

2 This activated neuron is called a winner-takes-all neuron or simply the winning neuron. Such competition can be induced/implementedby having lateral inhibition connections (negative feedback paths) between the result is that the neurons are forced to organise themselves. For obvious reasons, sucha network is called a Self Organizing Map (SOM).L16-3 Topographic MapsNeurobiological studies indicate that different sensory inputs (motor, visual, auditory, etc.)are mapped onto corresponding areas of the cerebral cortex in an orderly form of map, known as a topographic map, has two important properties:1. At each stage of representation, or processing, each piece of incoming information iskept in its proper Neurons dealing with closely related pieces of information are kept close together sothat they can interact via short synaptic interest is in building artificial topographic maps that learn through self-organizationin a neurobiologically inspired shall follow the principle of topographic map formation: The spatial location of anoutput neuron in a topographic map corresponds to a particular domain or feature drawnfrom the input space.

3 L16-4 Setting up a Self Organizing MapThe principal goal of an SOM is to transform an incoming signal pattern of arbitrarydimension into a one or two dimensional discrete map, and to perform this transformationadaptively in a topologically ordered therefore set up our SOM by placing neurons at the nodes of a one or two dimensionallattice. Higher dimensional maps are also possible, but not so neurons become selectively tuned to various input patterns (stimuli) or classes ofinput patterns during the course of the competitive locations of the neurons so tuned ( the winning neurons) become ordered and ameaningful coordinate system for the input features is created on the lattice. The SOMthus forms the required topographic map of the input can view this as a non-linear generalization of principal component analysis (PCA).

4 L16-5 ContinuousHigh DimensionalInput SpaceOrganization of the MappingWe have points x in the input space mapping to points I(x) in the output space:Each point I in the output space will map to a corresponding point w(I) in the input DiscreteLow DimensionalOutput SpacexwI(x)I(x)L16-6 Kohonen NetworksWe shall concentrate on the particular kind of SOM known as a Kohonen Network. ThisSOM has a feed-forward structure with a single computational layer arranged in rows andcolumns. Each neuron is fully connected to all the source nodes in the input layer:Clearly, a one dimensional map will just have a single row (or a single column) in thecomputational layerComputational layerL16-7 Components of Self OrganizationThe self-organization process involves four major components:Initialization: All the connection weights are initialized with small random : For each input pattern, the neurons compute their respective values of adiscriminant function which provides the basis for competition.

5 The particular neuronwith the smallest value of the discriminant function is declared the : The winning neuron determines the spatial location of a topologicalneighbourhood of excited neurons, thereby providing the basis for cooperation amongneighbouring : The excited neurons decrease their individual values of the discriminantfunction in relation to the input pattern through suitable adjustment of the associatedconnection weights, such that the response of the winning neuron to the subsequentapplication of a similar input pattern is Competitive ProcessIf the input space is D dimensional ( there are D input units) we can write the inputpatterns as x = {xi : i = 1, .., D} and the connection weights between the input units i andthe neurons j in the computation layer can be written wj = {wji : j = 1.}

6 , N; i = 1, .., D}where N is the total number of can then define our discriminant function to be the squared Euclidean distancebetween the input vector x and the weight vector wj for each neuron jdxwjijiiD( )()x= = 21In other words, the neuron whose weight vector comes closest to the input vector ( ismost similar to it) is declared the this way the continuous input space can be mapped to the discrete output space ofneurons by a simple process of competition between the Cooperative ProcessIn neurobiological studies we find that there is lateral interaction within a set of excitedneurons. When one neuron fires, its closest neighbours tend to get excited more thanthose further away. There is a topological neighbourhood that decays with want to define a similar topological neighbourhood for the neurons in our SOM.

7 If Sijis the lateral distance between neurons i and j on the grid of neurons, we takeTSj Ij I, (), ()exp(/)xx= 222 as our topological neighbourhood, where I(x) is the index of the winning neuron. This hasseveral important properties: it is maximal at the winning neuron, it is symmetrical aboutthat neuron, it decreases monotonically to zero as the distance goes to infinity, and it istranslation invariant ( independent of the location of the winning neuron)A special feature of the SOM is that the size of the neighbourhood needs to decreasewith time. A popular time dependence is an exponential decay: ( )exp(/)tt= Adaptive ProcessClearly our SOM must involve some kind of adaptive, or learning, process by which theoutputs become self-organised and the feature map between inputs and outputs is point of the topographic neighbourhood is that not only the winning neuron gets itsweights updated, but its neighbours will have their weights updated as well, although bynot as much as the winner itself.

8 In practice, the appropriate weight update equation is wtTtxwjij Iiji= ( )( )(), () .. xin which we have a time (epoch) t dependent learning rate ( )exp(/)tt= 0, and theupdates are applied for all the training patterns x over many effect of each learning weight update is to move the weight vectors wi of the winningneuron and its neighbours towards the input vector x. Repeated presentations of thetraining data thus leads to topological and ConvergenceProvided the parameters ( 0, , 0, ) are selected properly, we can start from an initialstate of complete disorder, and the SOM algorithm will gradually lead to an organizedrepresentation of activation patterns drawn from the input space. (However, it is possibleto end up in a metastable state in which the feature map has a topological defect.)

9 There are two identifiable phases of this adaptive process:1. Ordering or self- Organizing phase during which the topological ordering of theweight vectors takes place. Typically this will take as many as 1000 iterations ofthe SOM algorithm, and careful consideration needs to be given to the choice ofneighbourhood and learning rate Convergence phase during which the feature map is fine tuned and comes toprovide an accurate statistical quantification of the input space. Typically thenumber of iterations in this phase will be at least 500 times the number of neuronsin the network, and again the parameters must be chosen the Self Organization Process Suppose we have four data points (crosses)in our continuous 2D input space, and wantto map this onto four points in a discrete1D output space.

10 The output nodes map topoints in the input space (circles). Randominitial weights start the circles at randompositions in the centre of the input randomly pick one of the data pointsfor training (cross in circle). The closestoutput point represents the winning neuron(solid diamond). That winning neuron ismoved towards the data point by a certainamount, and the two neighbouring neuronsmove by smaller amounts (arrows).L16-13 Next we randomly pick another data pointfor training (cross in circle). The closestoutput point gives the new winning neuron(solid diamond). The winning neuronmoves towards the data point by a certainamount, and the one neighbouring neuronmoves by a smaller amount (arrows). We carry on randomly picking data pointsfor training (cross in circle).