Transcript Song Network WCCI 2008

A Hybrid Self-Organizing Neural
Gas Network
James Graham and Janusz Starzyk
School of EECS, Ohio University
Stocker Center, Athens, OH 45701 USA
IEEE World Conference on
Computational Intelligence (WCCI’08)
June 1-6, 2008
Hong Kong
Introduction

Self Organizing Networks
–
–
–

Useful for representation building in unsupervised learning
Useful for clustering, visualization and feature maps
Numerous applications in surveillance, traffic monitoring, flight
control, rescue mission, reinforcement learning, etc.
Some Types of Self Organizing Networks
–
–
–
–
–
Traditional Self-Organizing Map
Parameterless SOM
Neural Gas Network
Growing Neural Gas
Self-Organizing Neural Gas (SONG)
Description of the approach
- Fritzke’s GNG Network Algorithm Highlights
1)
2)
3)
4)
5)
6)
7)
8)
GNG starts with a set A of two units a and b at random positions wa and
wb in Rn
In the set A find two nearest neighbors s1 and s2 to the input signal x.
Connect s1 and s2, with an edge and set the edge age to zero.
Adjust the positions of s1 and its neighborhood by a constant times (x-s1).
(b for s1 and nfor the neighborhood)
Remove edges in the neighborhood that are older than amax.
Place a new node every λ cycles between the node with greatest error and
its nearest neighbor.
Reduce error of the node with the maximum error and its nearest neighbor
by  %, and add the removed error to the new node.
Reduce error of all nodes by a constant () times their current error.
Example

Example of Fritzke’s network results for 40,000 iterations with the
following constants: b=0.05, n=.0006 , amax=88, =200, =.5, =0.0005.
Description of the approach
- Proposed Hybrid SONG Network Algorithm Highlights
1)
2)
3)
4)
5)
SONG starts with a random pre-generated network of a fixed size.
Connections get “stiffer” with age, making their weight harder to
change.
Error is calculated after the node position updates rather than before.
Weight adjustment and error distribution are functions of a distance
rather than arbitrary, hard to set constants.
Edge connections are removed only under the following conditions:
–
–
When a connection is added and the node has a long connection 2x greater
than its average connection length - the long edge is removed.
When a node is moved and has at least 2 connections (after attaching to its
destination node) - its longest connection is removed.
Description of the approach
- Modification of new data neighborhood
“Force” calculations
|w1-|
nearest neighbor
s
|ws-|
|w2-|
new data

|wN-|
node removed
if orphaned

N s1
2
1 wk  
2
Weight adjustment
wi 
remove connection to
a distant neighbor >2 mean
Fi 
1 wi  
Fi
  wi 
log (mean age i  2  1


Error increase
Ei  Fi ws1  
Age increase by 1
2
Description of the approach
- Node replacement
Select a node with the minimum
error Esk
Spread Esk to its sk neighborhood
maximum error node
sq
sk
minimum error
node moved
Ei  Esk Fi
Description of the approach
- Node replacement
maximum error node
sk
sq
Select a node with the minimum
error Esk
Spread Esk to its sk neighborhood
Ei  Esk Fi
Insert sk to the neighborhood of sq
using weights
longest connection
removed
wr 
N sq

iN sq
Ei wi

Ei
Remove the longest connection
Spread half of sq neighborhood error
to sk
Results

Initial network structure with 1 random connection per node (for 200
nodes)
Results (cont.)

Structure resulting form 1 initial random connection.
Results (cont.)

Connection equilibrium reached for 1 initial connection.
Results (cont.)

Structure resulting from 16 initial random connections.
Results (cont.)

Connection equilibrium for 16 initial connections.
Video of Network Progression
Hybrid SONG Network
QuickTime™ and a
decompressor
are needed to see this picture.
Fritzke GNG Network
Results (cont.)


2-D comparison,
with SOM network
Salient features of
the SOM algorithm:
–
–
–
The SOM network starts as
a predefined grid and is
adjusted over many
iterations.
Connections are fixed and
nodes are not inserted,
moved, or relocated out of
their preexisting grid.
Weight adjustments occur
over the entire grid and are
controlled by weighted
distance to the data point.
Growing SONG Network
Number of nodes in SONG can
be automatically obtained
 The SONG network starts with
a few randomly placed nodes
and build itself up until an
equilibrium is reached between
the network size and the error.
 A node is added every λ cycles
if
MaxError > AveError + Constant
 Equilibrium appears to be
~200 nodes.

Growing SONG Network (cont.)




Error handling in growing
SONG network was
modified.
The error is “reset” and
recomputed after the
equilibrium was reached
Network continues to
learn reaching new
equilibrium
Approximation accuracy
vary from run to run
Growing SONG Network (cont.)

The results of growing SONG network run (on the right)
compared to the simpler static approach (on the left).
Other Applications
- Sparsely connected hierarchical sensory network



The major features of the SONG algorithm such as
the weight adjustment, error calculation, and
neighborhood selection are utilized in building selforganizing sparsely connected hierarchical networks.
The sparse hierarchical network is locally connected
based on neurons’ firing correlation
Feedback and time based correlation are used for
invariant object recognition.
Other Applications
- Sparsely connected hierarchical sensory network (cont.)
1
0.8
Wiring area
0.6
0.4
0.2
0
15
10
5
2
4
6
8
10
Correlation/PDF Example
12
14
Other Applications
- Sparsely connected hierarchical network (cont.)
Correlation based wiring
Sparse hierarchical representations
Image #16 Layer #1 Results
Image #16 Layer #2 Results
Image #16 Layer #4 Results
Image #16 Layer #5 Results
Image #16 Layer #3 Results
Declining
neurons’
activations
Conclusions

The SONG algorithm is more biologically plausible than
Fritzke’s GNG algorithm. Specifically:
–
–
–



Weight and error adjustment are not parameter based.
Connections become stiffer with age rather than being removed
at a maximum age as in Fritzke’s method.
Network has all neurons from the beginning
SONG approximates data distribution faster than the
other methods tested.
Connectivity between neurons is automatically obtained
and depends on the parameter that controls edge
removal and the network size.
The number of neurons can be automatically obtained in
growing SONG to achieve the desired accuracy.
Future Work


Adapt the SONG algorithm to large input spaces
(high dimensionality, i.e. images)
Adapt the SONG algorithm to a hierarchical network.
–


Possible applications in feature extraction, representation
building, and shape recognition.
Insert new nodes as needed to reduce error.
Optimize the network design.
Questions
[email protected]
?