Self-Organizing Maps (SOM) PDF

Self-organising Maps Mills, Correia Self-organising Maps Artificial Life / Vida Artificial & The 3 Computational methodologies / Metodologias da Computação: component mechanisms Self-organising Maps Properties examp...

Self-organising Maps Mills, Correia Self-organising Maps Artificial Life / Vida Artificial & The 3 Computational methodologies / Metodologias da Computação: component mechanisms Self-organising Maps Properties example Rob Mills Luı́s Correia Informatics FCUL November 2014  Outline Self-organising Maps Mills, Correia Self-organising Maps 1 Self-organising Maps The 3 component mechanisms 2 The 3 component mechanisms Properties example 3 Properties 4 example  Outline Self-organising Maps Mills, Correia Self-organising Maps 1 Self-organising Maps The 3 component mechanisms 2 The 3 component mechanisms Properties example 3 Properties 4 example  Self-organising Maps (I) Self-organising Maps Mills, Correia Self-organising Maps The 3 component Models of competitive learning – unsupervised mechanisms In each situation there is one winner – “winner-takes-all” Properties (or nearly so... ) example Use lateral inhibition – to produce a single winner Neurons are in a grid, usually 2D  Self-organising Maps (II) Self-organising Maps Mills, Correia Self-organising The neurons organise topologically, to reflect the statistical char- Maps acteristics of the training examples The 3 component mechanisms Projection of multi-dimensional data into a space of fewer Properties dimensions ( 2 → 2) example Can be seen as a non-linear generalisation of PCA Analogies with areas of the brain that are topologically organised – such as sensory inputs (touch, whisking, visual, auditory)  Self-organising Maps (III) Self-organising Maps Mills, Correia Self-organising Maps Desirable property The 3 component Preservation of topology: neighbouring patterns map to mechanisms neighbouring neurons Properties example Inspiration Codes for quantification of vectors associative memories Mammalian cortex  Self-organising Maps (IV) Self-organising Maps Mills, Correia Self-organising Maps Uses The 3 component Clustering mechanisms Detecting novelties in an input space Properties example Easy to observe visually ⇒ Visualisation and analysis of high-dimensional data – possibility to use “U-Matrices” Classification (with “learning vector quantisation”)  SOM models Self-organising Maps Kohonen maps Mills, Correia Self-organising Maps The 3 component mechanisms Properties example every input connects to all neurons in the grid (the output layer) the model is more general (than W-vdM) Wilshaw – von der Malsburg’s model Also uses a grid of neurons More than one neuron can be active in the output layer Input and output spaces use the same dimensionality  Training the SOM Self-organising Maps Mills, Correia Self-organising 1 Initialisation: assign small, random values to the weights. Maps 2 Competition: for every input pattern calculate the value of The 3 component the discriminant (for each neuron). The highest value is mechanisms the winner – which neuron is topologically closest to the Properties pattern (in the lower-dimensional space) example 3 Cooperation: The winning neuron defines a spatial neighbourhood for other neurons that can adapt 4 Synaptic adaptation: The more excited neurons increase their discriminant value, relative to the input pattern [Hebbian]  The SOM: A basic description Self-organising Maps Mills, Correia Each neuron is a vector in the input space, and their Self-organising Maps geonmetic position is the output that reduces the dimensions of The 3 the input space component mechanisms Properties During the training, the neurons are pulled towards the example positions of the closest input patterns, also pulling their neighbours in the output space The map can be viewed as a surface of rubber that is stretched and twisted to reflect the patterns in the training set (or to be near to them)  Mapping 2D → 1D Self-organising Maps 2D input data are uniformly distributed in a triangle, and a 1D Mills, Correia linear SOM is trained on the data. Self-organising Maps end of the ordering phase The 3 component mechanisms Properties example end of the convergence phase  Mapping 2D → 2D Self-organising Maps phases of learning (ordering; convergence) Mills, Correia Self-organising Maps The 3 component mechanisms Properties example  Problems Self-organising Maps Mills, Correia How to know when the map is well trained? Self-organising Maps Folding [Ritter, 1991] The 3 component mechanisms Properties example over-learning  Outline Self-organising Maps Mills, Correia Self-organising Maps 1 Self-organising Maps The 3 component mechanisms 2 The 3 component mechanisms Properties example 3 Properties 4 example  Competition Self-organising Maps Let the input vector be of dimension m: Mills, Correia x = [x1 , x2 ,... , xm ]T. (1) Self-organising Maps The 3 And the vector of weights for neuron j is: component mechanisms Properties wj = [wj1 , wj2 ,... , wjm ]T , j = 1, 2,... , l (2) example where l is the number of neurons in the SOM. Calculate the l interior products wjT x and pick the biggest – equivalent to minimising the Euclidean distance. The winning neuron i is i(x) = arg min kx − wj k , j = 1, 2,... , l (3) j The result may be i or the corresponding weight vector  Cooperation (I) Self-organising Maps Mills, Correia A neurobio analogy: neural activity tends to excite neighbours Self-organising more than distal neurons Maps The 3 hj,i : the topological neighbourhood centred on the winning component mechanisms neuron i and includng a neighbour j Properties dj,i : the lateral distance between winner i and a neighbour j example hj,i = f (dj,i ): Neighbourhood is a unimodal function of distance: hj,i is symmetric about the point, with dj,i = 0, where it is maximal The amplitude of hj,i decreases monotonically with dj,i , and tends to zero when dj,i → ∞.  Cooperation (II) Self-organising Maps A typical function of topological distance (Gaussian) Mills, Correia ! 2 dj,i Self-organising hj,i(x) = exp − 2 (4) Maps 2σ The 3 component mechanisms This is invariant to translation – it only depends on the Properties distance between the neurons (not their position) example σ is the effective width of the topological neighbourhood: Other functions can be used (rectangular/triangular/... )  Cooperation (III) Self-organising Maps With a 1d grid, dj,i is a positive integer for kj − ik. In the case Mills, Correia of a 2d grid: Self-organising 2 dj,i = krj − ri k2 , (5) Maps The 3 for coodinates rj and ri of neurons j and i in the output space component mechanisms The neighbourhood hj,i decreases with time. Normally, Properties   example n σ(n) = σ0 exp − , (6) τ1 σ0 : the initial value of σ ; τ1 : the time constant Thus, ! 2 dj,i hj,i(x)(n) = exp − (7) 2σ 2 (n)  Adaptation (I) Self-organising Maps Mills, Correia We use a modified Hebb rule – to prevent saturation: Self-organising Maps The 3 ∆wj = ηyj x − g (yj )wj , (8) component mechanisms where g (yj )wj is the “forgetting” term, with the restriction that Properties g (yj ) = 0, for yj = 0. example So, we can use g (yj ) = ηyj. With the simplification: yj = h,i (x), then we obtain ∆wj = ηhj,i(x) (x − wj ). (9)  Adaptation (II) Self-organising Maps Mills, Correia Self-organising The update of the synaptic weights becomes: Maps The 3 component wj (n + 1) = wj (n) + η(n)hj,i(x) (n)(x − wj ). (10) mechanisms Properties This update is applied to all neurons j in the neighbourhood of example the winner i ⇒ weight wi of winner i is moved towards the input x Result A topological ordering of the features of the input space: adjacent neurons in the grid tend to have similar weights  Adaptation (III) Self-organising Maps Mills, Correia Self-organising Maps The 3 component Note: the learning parameter also decreases over time, mechanisms   Properties n example η(n) = η0 exp −. (11) t2  The two phases of adaptation 1: Self-organisation, or ordering Self-organising Maps Mills, Correia The topological ordering of the weight vectors. Self-organising Maps Can take ≥ 1000 iterations The 3 component η(n) should remain above 0.01 mechanisms η0 = 0.1 Properties τ2 = 1000 example hj,i (n) should initially include nearly all the network, and decrease to very few neighbours (∼ 0). For a 2D grid: 1000 τ1 = log σ0 where σ0 is the ‘radius’ of the grid. A large radius allows unfolding in the SOM  The two phases of adaptation 2: Convergence Self-organising Maps Mills, Correia Self-organising Fine-tuning of the map (improving accuracy) Maps The 3 Can need 500× the number of neurons! component mechanisms (1000s or 10000s of iterations) Properties example η(n) should be maintained ∼ 0.01 and never reach 0 This prevents reaching metastability (topol. defects) hj,i(x) should only contain the nearest neighbours of the winner – an eventual radius of 1 or 0.  Summary of the SOM Algorithm (I) Self-organising Maps Mills, Correia 1 Initialisation – pick random initial weights wj. (ensure Self-organising Maps that values are different for different neurons) The 3 component mechanisms 2 Sampling – Randomly select a sample x from the training Properties set (x has dimensionality m) example 3 Similarity matching – Find the neuron closest to the input pattern, for timestep n, i(x) = arg min kx(n) − wj k , j = 1, 2,... , l j  Summary of the SOM Algorithm (II) Self-organising Maps Mills, Correia Self-organising Maps The 3 4 Updating – Adjust the synaptic weights (for neurons in hi ): component mechanisms Properties wj (n + 1) = wj (n) + η(n)hj,i(x) (n)(x − wj ). example note: varying η and h dynamically leads to better results 5 Continuation – Return to step 2 until the map stops changing  Outline Self-organising Maps Mills, Correia Self-organising Maps 1 Self-organising Maps The 3 component mechanisms 2 The 3 component mechanisms Properties example 3 Properties 4 example  Mappings in the SOM Self-organising Maps Mills, Correia Self-organising Maps Φ:X →A The 3 component mechanisms Properties Components of wi example represent coordinates of the image of neuron i, projected into the input space  Properties of the SOM (I) Approximation of the input space Self-organising Maps Mills, Correia Self-organising Maps The feature map Φ, represented by the set of weight vectors The 3 {wj } in the output space A, provides a good approximation to component mechanisms the input space, X. Properties example Reduces a large set of input vectors x ∈ X of high dimensionality to a smaller set of ‘prototypes’ {wj } ∈ A Reduction of dimensionality – or data compression Vector quantization algorithm  Properties of the SOM (II) Topological Ordering Self-organising Maps Mills, Correia Self-organising The feature map Φ, calculated by the SOM algorithm, is Maps topologically ordered: the spatial location of a neuron in the The 3 component output grid corresponds to a particular feature of the input mechanisms patterns. Properties example The map Φ is normally representative of the input space X The pointers represent vectors of the synaptic weights wj and the lines connecting wi and wj represent relationships between neurons i and j  Properties of the SOM (III) Density Matching Self-organising Maps Mills, Correia Self-organising Maps The feature map Φ reflects statistical variations in the The 3 component distribution of inputs: regions in the input space X where mechanisms Properties samples x are obtained with high probability are mapped to example larger regions of the output space, giving a higher resolution than regions of X that are less likely to be drawn. But, the difference is not as great as would be desirable...  Properties of the SOM (IV) Feature selection Self-organising Maps Mills, Correia Self-organising Given the data from an input space with a non-linear Maps distribution, the SOM is able to select from a set of best The 3 component features that can approximate the underlying distribution mechanisms Properties Properties 1..3 give rise to this capacity: example It can provide a discrete approximation of principal curves or principal surfaces The SOM can be viewed as a non-linear generalisation of PCA (which is linear)  Outline Self-organising Maps Mills, Correia Self-organising Maps 1 Self-organising Maps The 3 component mechanisms 2 The 3 component mechanisms Properties example 3 Properties 4 example Self-organising Maps Mills, Correia Self-organising Maps The 3 component mechanisms Properties (dim reduction mapping – external) example  Applications Self-organising Maps Mills, Correia Self-organising Maps chemical analysis (data of spectroscopy, Tokutaka 98) The 3 component analysis of fluid movements (Labont 98) mechanisms follows the position of particles in a fluid. Properties example analyses the trajectory of neurons during learning control of a robot arm monitoring the state/condition of machines sound recognition