Transcript Slide13

x0 w0

xn wn
Semiconductors, BP&A Planning, 2003-01-29
Threshold units
n
w x
i 0
i i
o
o  1 if
n
w x
i 0
i i
 0 and 0 o/w
1
Semiconductors, BP&A Planning, 2003-01-29
2
Inputs
Teuvo Kohonen
Semiconductors, BP&A Planning, 2003-01-29
3
Self-Organizing Maps : Origins
Ideas first introduced by C. von der Malsburg (1973), developed and
refined by T. Kohonen (1982)
Neural network algorithm using unsupervised competitive learning
Primarily used for organization and visualization of complex data
Biological basis: ‘brain maps’
Semiconductors, BP&A Planning, 2003-01-29
4
Self-Organizing Maps
SOM - Architecture
Lattice of neurons (‘nodes’) accepts and responds to set of input signals
Responses compared; ‘winning’ neuron selected from lattice
Selected neuron activated together with ‘neighbourhood’ neurons
Adaptive process changes weights to more closely resemble inputs
j
2d array of neurons
wj1
x1
wj2 wj3
x2
x3
Semiconductors, BP&A Planning, 2003-01-29
wjn
...
Weighted synapses
xn
Set of input signals
(connected to all neurons in lattice)
5
Self-Organizing Maps
SOM – Algorithm Overview
1. Randomly initialise all weights
2. Select input vector x = [x1, x2, x3, … , xn]
3. Compare x with weights wj for each neuron j to
determine winner
4. Update winner so that it becomes more like x, together
with the winner’s neighbours
5. Adjust parameters: learning rate & ‘neighbourhood
function’
6. Repeat from (2) until the map has converged (i.e. no
noticeable changes in the weights) or pre-defined no. of
training cycles have passed
Semiconductors, BP&A Planning, 2003-01-29
6
Initialisation
Randomly initialise the weights
Semiconductors, BP&A Planning, 2003-01-29
7
Finding a Winner
•
•
•
•
Find the best-matching neuron w(x), usually the neuron whose
weight vector has smallest Euclidean distance from the input
vector x
The winning node is that which is in some sense ‘closest’ to the
input vector
‘Euclidean distance’ is the straight line distance between the data
points, if they were plotted on a (multi-dimensional) graph
Euclidean distance between two vectors a and b,
a = (a1,a2,…,an), b = (b1,b2,…bn), is calculated as:
Euclidean distance d a, b 
 a
 bi 
2
i
i
Semiconductors, BP&A Planning, 2003-01-29
8
Weight Update
• SOM Weight Update Equation
• wj(t +1) = wj(t) + (t) (x)(j,t) [x - wj(t)]
• “The weights of every node are updated at each cycle by adding
• Current learning rate × Degree of neighbourhood with respect
to winner × Difference between current weights and input
vector
• to the current weights”
Example of (t)
Example of (x)(j,t)
L. rate
Semiconductors, BP&A Planning, 2003-01-29
No. of cycles
–x-axis shows distance from winning node
–y-axis shows ‘degree of neighbourhood’ (max. 1)
9
Kohonen’s Algorithm
wij  (i, i )( j  wij )
*
jth input
Winner ith
(i, i )  exp(  | ri  ri* | / 2 )
*
Semiconductors, BP&A Planning, 2003-01-29
2
2
10
Neighborhoods
Square and hexagonal grid with
neighborhoods based on box distance
Grid-lines are not shown
Semiconductors, BP&A Planning, 2003-01-29
11
•One-dimensional
•i
•Two-dimensional
•i
•Neighborhood of neuron i
Semiconductors, BP&A Planning, 2003-01-29
12
Semiconductors, BP&A Planning, 2003-01-29
13
•A neighborhood function (i, k) indicates how closely neurons i and
k in the output layer are connected to each other.
•Usually, a Gaussian function on the distance between the two
neurons in the layer is used:

position of i
Semiconductors, BP&A Planning, 2003-01-29
position of k
14
Semiconductors, BP&A Planning, 2003-01-29
15
A simple toy example
Clustering of the Self Organising Map
Semiconductors, BP&A Planning, 2003-01-29
16
However, instead of updating only the winning neuron i*, all
neurons within a certain neighborhood Ni* (d), of the winning
neuron are updated using the Kohonen rule. Specifically, we adjust
all such neurons i  Ni* (d), as follow
iw(q)  iw(q  1)   ( p(q)  iw(q  1))
iw(q)  (1   )iw(q  1)  p(q)
Here the neighborhood Ni* (d), contains the indices for all of the
neurons that lie within a radius d of the winning neuron i*.
N i (d )  j , d ij  d 
Semiconductors, BP&A Planning, 2003-01-29
17
Topologically Correct Maps
The aim of unsupervised self-organizing
learning is to construct a topologically correct
map of the input space.
Semiconductors, BP&A Planning, 2003-01-29
18
Self Organizing Map
• Determine the winner (the neuron of which the
weight vector has the smallest distance to the
input vector)
• Move the weight vector w of the winning
neuron towards the input i
i
i w
w
Before learning
Semiconductors, BP&A Planning, 2003-01-29
After learning
19
Network Features
• Input nodes are connected to every neuron
• The “winner” neuron is the one whose weights
are most “similar” to the input
• Neurons participate in a “winner-take-all”
behavior
– The winner output is set to 1 and all others to 0
– Only weights to the winner and its neighbors are
adapted
Semiconductors, BP&A Planning, 2003-01-29
20
a1
a2 a3
w2 w3
an2 an 1 a n
wn  2 wn1
wn
w1
P
wi
Semiconductors, BP&A Planning, 2003-01-29
1
2
3
4
5
6
7
8
9
21
a1
a2 a3
an2 an 1 a n
wn1 w
n2
w11 w21
P1 P2
5
wi2
6
4
3
9
7
1
Semiconductors, BP&A Planning, 2003-01-29
2
8
wi1 22
winner
output
input (n-dimensional)
Semiconductors, BP&A Planning, 2003-01-29
23
Semiconductors, BP&A Planning, 2003-01-29
24
Example I: Learning a one-dimensional representation of a
two-dimensional (triangular) input space:
0
20
1000
10000
Semiconductors, BP&A Planning, 2003-01-29
100
25000
25
Some nice illustrations
Semiconductors, BP&A Planning, 2003-01-29
26
Some nice illustrations
Semiconductors, BP&A Planning, 2003-01-29
27
Some nice illustrations
Semiconductors, BP&A Planning, 2003-01-29
28
Self Organizing Map
• Impose a topological order onto the
competitive neurons (e.g., rectangular map)
• Let neighbors of the winner share the
“prize” (The “postcode lottery” principle)
• After learning, neurons with similar weights
tend to cluster on the map
Semiconductors, BP&A Planning, 2003-01-29
29
Conclusion
•Advantages
• SOM is Algorithm that projects high-dimensional data onto a
two-dimensional map.
• The projection preserves the topology of the data so that
similar data items will be mapped to nearby locations on the
map.
• SOM still have many practical applications in pattern
recognition, speech analysis, industrial and medical
diagnostics, data mining
– Disadvantages
• Large quantity of good quality representative training data
required
• No generally accepted measure of ‘quality’ of a SOM
e.g. Average quantization error (how well the data is
classified)
Semiconductors, BP&A Planning, 2003-01-29
30
Topologies (gridtop, hextop, randtop)
pos = gridtop(2,3)
pos =
0 1 0 1
0 0 1 1
plotsom (pos)
0
2
pos = gridtop(3,2)
pos =
0 1 0 1
0 0 1 1
plotsom (pos)
1
2
Neuron Positions
0
2
1
2
Neuron Positions
2
1.2
1.6
1
1.4
0.8
1.2
position(2,i)
position(2,i)
1.8
1
0.8
0.6
0.4
0.6
0.2
0.4
0
0.2
0
-0.2
-0.5
0
0.5
position(1,i)
Semiconductors, BP&A Planning, 2003-01-29
1
1.5
0
0.2
0.4
0.6
0.8
1
1.2
position(1,i)
1.4
1.6
1.8
2
31
pos = gridtop(8,10);
plotsom(pos)
Neuron Positions
9
8
7
position(2,i)
6
5
4
3
2
1
0
Semiconductors, BP&A Planning, 2003-01-29
-2
0
2
4
position(1,i)
6
8
32
pos = hextop(2,3)
pos =
0 1.0000 0.5000 1.5000
0
0
0 0.8660 0.8660 1.7321
1.0000
1.7321
Neuron Positions
1.6
1.4
position(2,i)
1.2
1
0.8
0.6
0.4
0.2
0
Semiconductors, BP&A Planning, 2003-01-29
-0.2
0
0.2
0.4
0.6
0.8
position(1,i)
1
1.2
1.4
1.6
1.8
33
pos = hextop(3,2)
pos =
0 1.0000
0
0
plotsom(pos)
2.0000
0
0.5000
0.8660
1.5000
0.8660
2.5000
0.8660
Neuron Positions
1.4
1.2
1
position(2,i)
0.8
0.6
0.4
0.2
0
-0.2
-0.4
0
0.5
1
1.5
2
2.5
position(1,i)
Semiconductors, BP&A Planning, 2003-01-29
34
pos = hextop(8,10);
plotsom(pos)
Neuron Positions
7
6
position(2,i)
5
4
3
2
1
0
Semiconductors, BP&A Planning, 2003-01-29
-1
0
1
2
3
4
position(1,i)
5
6
7
8
35
pos = randtop(2,3)
pos =
0 0.7787 0.4390
0 0.1925 0.6476
1.0657
0.9106
0.1470
1.6490
0.9070
1.4027
Neuron Positions
1.2
1
position(2,i)
0.8
0.6
0.4
0.2
0
Semiconductors, BP&A Planning, 2003-01-29
0
0.2
0.4
0.6
0.8
position(1,i)
1
1.2
1.4
36
pos = randtop(3,2)
pos =
0
0.0019
0.7787
0.1944
1.5640
0
0.3157
0.9125
1.2720
1.0014
2.0320
0.7550
Neuron Positions
1.2
1
position(2,i)
0.8
0.6
0.4
0.2
0
-0.2
0
Semiconductors, BP&A Planning, 2003-01-29
0.2
0.4
0.6
0.8
1
1.2
position(1,i)
1.4
1.6
1.8
2
37
pos = randtop(8,10);
plotsom(pos)
Neuron Positions
6
5
position(2,i)
4
3
2
1
0
Semiconductors, BP&A Planning, 2003-01-29
0
1
2
3
position(1,i)
4
5
6
38
Distance Funct. (dist, linkdist, mandist, boxdist)
pos2 = [ 0 1 2; 0 1 2]
pos2 =
0 1 2
0 1 2
D2 = dist(pos2)
D2 =
0
1.4142
1.4142 0
2.8284 1.4142
Semiconductors, BP&A Planning, 2003-01-29
2.8284
1.4142
0
39
Semiconductors, BP&A Planning, 2003-01-29
40
pos = gridtop(2,3)
pos =
0 1 0 1
0 0 1 1
plotsom(pos)
0
2
1
2
Neuron Positions
1.8
1.6
1
1
1
0
1
1
Semiconductors, BP&A Planning, 2003-01-29
2
2
1
1
0
1
2
2
1
1
1
0
1.4
position(2,i)
d = boxdist(pos)
d=
0 1 1
1 0 1
1 1 0
1 1 1
2 2 1
2 2 1
2
1.2
1
0.8
0.6
0.4
0.2
0
-0.5
0
0.5
position(1,i)
1
1.5
41
pos = gridtop(2,3)
pos =
0 1 0 1
0 0 1 1
plotsom(pos)
1
2
Neuron Positions
2
1.8
1.6
2
1
1
0
2
1
2
3
1
2
0
1
3
2
2
1
1
0
1.4
position(2,i)
d=linkdist(pos)
d=
0 1 1
1 0 2
1 2 0
2 1 1
2 3 1
3 2 2
0
2
1.2
1
0.8
0.6
0.4
0.2
0
Semiconductors, BP&A Planning, 2003-01-29
-0.5
0
0.5
position(1,i)
1
1.5
42
The Manhattan distance between two vectors x and y is calculated as
D = sum(abs(x-y))
Thus if we have
W1 = [ 1 2; 3 4; 5 6]
W1 =
1 2
3 4
5 6
and
P1= [1;1]
P1 =
1
1
then we get for the distances
Z1 = mandist(W1,P1)
Z1 =
1
5
9
Semiconductors, BP&A Planning, 2003-01-29
43
A One-dimensional Self-organizing Map
angles = 0:2*pi/99:2*pi;
P = [sin(angles); cos(angles)];
plot(P(1,:),P(2,:),'+r')
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
Semiconductors, BP&A Planning, 2003-01-29
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
44
net = newsom([-1 1;-1 1],[30]);
net.trainParam.epochs = 100;
net = train(net,P);
plotsom(net.iw{1,1},net.layers{1}.distances)
Weight Vectors
0.9
0.8
W(i,2)
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.2
0.3
0.4
0.5
0.6
W(i,1)
0.7
0.8
0.9
1
The map can now be used to classify inputs, like [1; 0]:
Either neuron 1 or 10 should have an output of 1, as the above input vector was at one end of the
presented input space. The first pair of numbers indicate the neuron, and the single number indicates
its output.
p = [1;0];
a = sim (net, p)
a=
(1,1)
1
Semiconductors, BP&A Planning, 2003-01-29
45
x = -4:0.01:4
P = [x;x.^2];
plot(P(1,:),P(2,:),'+r')
net = newsom([-10 10;0 20],[10 10]);
net.trainParam.epochs = 100;
net = train(net,P);
plotsom(net.iw{1,1},net.layers{1}.distances)
Semiconductors, BP&A Planning, 2003-01-29
46