Transcript The CSG algorithm

國立雲林科技大學
National Yunlin University of Science and Technology
Cell-splitting grid: a self-creating
and self-organizing neural network
Tommy W.S. Chow, Sitao Wu
Neurocomputing. 57 (2004) 373 – 387
Advisor : Professor Chung-Chian Hsu
Reporter : Wen-Chung Liao
2006/4/12
1
Intelligent Database Systems Lab
Outline









N.Y.U.S.T.
I. M.
Motivation
Objectives
The CSG algorithm
Network adjustment
Advantages of CSG algorithm
Relations to quadtrees and tree structured SOM
Experimental results
Conclusion
Comments
2
Intelligent Database Systems Lab
Motivation


N.Y.U.S.T.
I. M.
The main drawback of SOM is that one must
pre-define the map structure and the map
size before the commencement of the
training process.
Another problem is that the neurons in SOM
are uniformly distributed in the output space,
which does not well reflect the neurons in the
input space.
3
Intelligent Database Systems Lab
Objectives


N.Y.U.S.T.
I. M.
Present a new self-creating and self-organizing
neural network model called cell-splitting grid
algorithm (CSG), which resembles the cell-splitting
mechanism in biological perspective.
Using the proposed CSG algorithm, it is able to
overcome the discussed shortcomings of SOM and
its other improved algorithms
4
Intelligent Database Systems Lab
The CSG algorithm

N.Y.U.S.T.
I. M.
The difference between the proposed algorithm and
the classical SOM are the followings:
(1) During the processing in the CSG algorithm, the network
itself determines the growth of new neurons according to
the activation level τ .
(2) The weight adaptation in the CSG algorithm is adapted
slightly within the winner neuron and its direct neighboring
neurons.
The learning rate is small and does not decrease to zero.
This is called dynamic equilibrium.
5
Intelligent Database Systems Lab
The CSG algorithm
Start from one neuron
1.



2.
3.
4.
5.
6
N.Y.U.S.T.
I. M.
initialize w and L=0, R=1, T=1,B=0,Len=1,XY=[0.5 0.5].
τ(the first neuron)=τi , enough large to learn the information
before splitting.
Cycle=0, denoting the epochs performed on the network
before splitting.
Select an input x randomly from input space.
Find the best-matching neuron c, wc - x  wi - x ,i
Δwc = α1(x − wc), for winner neuron c
(1)
Δwb = α2(x − wb), for all b∈ Nc
(2)
Δτc = −1
(3)
ΔCycle = 1
(4)
Intelligent Database Systems Lab
The CSG algorithm
When τ(c)=0,
6.

perform the cell-splitting mechanism; set Cycle=0.
Initialize the new weights and the activation level of
the new generated neurons.
7.


8.
N.Y.U.S.T.
I. M.
The new weights are endowed according to existed weight
distribution on the output map before splitting.
τ(the new neurons) = τi +Δτ, Δτ>0, to slow down the
splitting rate.
If Cycle < TMax, then go to 2.
Otherwise, stop
7
Intelligent Database Systems Lab
Network adjustments (1/3)
N.Y.U.S.T.
I. M.
α1 and α2 must be rather small, but would
not be decreased to zero.
1)


α2<α1 must be met.
α1 = 0.01~0.1 and α2 = 0.01α1~0.1α1.
8
Intelligent Database Systems Lab
Network adjustments (2/3)
2)
N.Y.U.S.T.
I. M.
Weight initialization at the time of cell-splitting (avoid disorder
of topology in the input space)
only one neuron at the first stage,



introduce a vector Random, Random = A+B,
Top-left: w+A+B, top-right: w+A-B,
bottom-left: w-A+B, bottom-right: w-A-B
Random  w
# of neurons > 1









ML
MR
MT
MB
w1=(ML+MT)/2
w2=(MR+MT)/2
w3=(ML+MB)/2
w4=(MR+MB)/2
9
Intelligent Database Systems Lab
Network adjustments (3/3)
3)
At each splitting stage, it is required to compute the lengths
and border coordinates of the square regions of the new four
neurons

4)
N.Y.U.S.T.
I. M.
compute L, R, T, B, Len, XY.
The initial activation level τi affects the growing rate of the
network.


If τi is too small, the network size increases without learning
enough information and finally will not be able to well represent
the topology of the input data.
Usually τi is chosen to 0.05N ∼ 0.5N.
The stopping criterion, TMax.



10 5)
If TMax is too large, the final neurons will be very large and
excessive to represent the topology of the input data.
If TMax is too small, the network stop increasing before it
saturates.
Usually, TMax≧τi
Δτ = 0.001 ∼ 0.01τi
Intelligent Database Systems Lab
Advantages of CSG algorithm
N.Y.U.S.T.
I. M.
The overall time can
be adjusted by two
parameters:TMax, τi
Neuron distribution
on the output space
1)
2)
SOM: uniformly
GNG, GCS:



DSOM: Fig. 5



Not straightforward
2D output space, but
like SOM
CSG: Fig. 6
11
Intelligent Database Systems Lab
Relations to quadtrees and tree structured
SOM

CSG and quadtrees




CSG and tree structured SOM





12
From 2-D perspective, they’re are similar
Quadtree, the resulting decomposed space : not more than
3 dimensions.
CSG : the 2-D map representing the input space whose
dimension larger than 3.
TS-SOM : the neurons arranged in a tree structure,
TS-SOM : search BMU, O(log N)
TS-SOM : static quadtree structure in 3-D space.
TS-SOM : the leaf neurons plotted on a 2-D square region
will be similar to neurons on the output map in the CSG
algorithm.
But the dynamic quadtree structure has not been used for
TS-SOM.
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
Experimental results
N.Y.U.S.T.
I. M.
(CSG: α1 = 0.09; α2 = 0.0045, τi =500, Δτ = 10, TMax = 1200)
(CSG: α1 = 0.05; α2 = 0.0045, τi =500, Δτ = 10, TMax = 1100)
13
Intelligent Database Systems Lab
Experimental results
N.Y.U.S.T.
I. M.
(CSG: α1 = 0.05; α2 = 0.0025, τi =500, Δτ = 50, TMax = 6000)
14
Intelligent Database Systems Lab
Conclusion

CSG



N.Y.U.S.T.
I. M.
reflecting the topology and distribution of the data set
directly onto the output map.
effective for vector quantization and topology preservation
especially for non-uniformly distributed data sets.
Distinguished features



The output map is confined to a square and regular map
The neurons are non-uniformly distributed on a 2-D map.
The quantization error of the CSG algorithm is the
smallest while topology preservation is maintained
15
Intelligent Database Systems Lab
Comments



N.Y.U.S.T.
I. M.
Except CSG has a better output map, it
seems SOM, DSOM, and CSG have no
significance difference in performance.
Difficult to decide α1 , α2 ,τi , Δτ, and TMax 
parameterless CSG?
Why not using 3-D output space?
16
Intelligent Database Systems Lab