Growing Neural Gas

The Method

The Growing Neural Gas method models the distribution of a huge set of vectors by a smaller set of prototype vectors and additionally learns the topology – i.e. neighborhood or similarity relation – of these vectors. It was originally proposed by Fritzke in the year 1995.

The GNG algorithm is described in pseudo code in listing below. It starts with two randomly initialized prototype vectors x_1,x_2 of dimension D.

GNG is an iterative method. In each iteration step we randomly choose a vector y from the set of training vectors Y and determine the prototype vector x_a with the smallest distance to y. x_a is called the Best Matching Unit (BMU). The distance in the high-dimensional space can be measured by the standard euclidian distance or any other metric that is appropriate for the application. The BMU node and all its neighbored nodes - according to the topology learned so far - are adapted into the direction of y (see lines 12,13).

So far the adaptation is similar to a Self Organizing Map that also adapts the BMU and its neighbors. Though while the topology in a SOM is fixed since predefined, in a GNG the topology is learned. New edges between nodes - that represent the similarity relation of prototype nodes - are added by creating an edge between the BMU and the node x_b with the second smallest distance to y (see line 16). Since the adaptation of nodes and the insertion of edges are done simultaneously two initial neighbored nodes can move apart to different input space regions and thereby invalidating the neighborhood relationship. Therefore a mechanism is needed that deletes edges that have become invalid. In the GNG approach this is done by introducing an age for each edge and logging how long an edge has not been confirmed (see lines 17,20). If it has not been confirmed for some time maxage it is considered as invalid and will be deleted (see line 21).

Another important mechanism within the GNG beside this generation and deletion of edges for learning the topology is the insertion of new prototype nodes. The set of prototype nodes is extended such that a new prototype node is inserted in the input space region that is modeled by too few nodes, i.e. the current prototype nodes in this region are somewhat overstrained in the sense that they stand for a huge set of different vectors. The degree of overstraining of each prototype node is measured by a local node error that accumulates the distances to the vectors it represents (see line 10). To reduce the overstraining of such nodes the local errors are accumulated for some time (see line 27) to get meaningful local error measures. An new node is then inserted near to the most overstrained prototype node (see lines 28-32). The local error measures of the nodes involved thereby become invalid and incomparable to the other nodes not involved. For this, the local error counters of all nodes are reseted (see line 33).

The GNG algorithm therefore has four control parameters:

  1. the adaption rate epsilon_1 for the BMU
  2. the adaptation rate epsilon_2 for the neighbors of the BMU
  3. the maximal age maxage of an edge being unconfirmed before being removed
  4. a minimum local error threshold theta_l that decides whether we really need to insert more nodes

Sample adaptation of a GNG to three isolated input clusters

Adaptivity to a changing input space

step 00000-03999: input space #1
step 04000-07999: input space #2
step 08000-11999: input space #1
step 12000-15999: input space #2
step 16000-19999: input space #1
step 20000-23999: input space #2

Further demos

  • See this demo by Loos & Fritzke. Nice feature: you can change the input signal (see “probability distribution” combobox) during learning and see how good the GNG and other neuronal prototpye learning models adapt to it.
 
public/growing_neural_gas.txt · Last modified: 2012/01/02 17:29 (external edit) · []
Recent changes RSS feed Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki