Neural gas

Not to be confused with Nerve gas.

Neural gas is an artificial neural network, inspired by the self-organizing map and introduced in 1991 by Thomas Martinetz and Klaus Schulten.[1] The neural gas is a simple algorithm for finding optimal data representations based on feature vectors. The algorithm was coined "neural gas" because of the dynamics of the feature vectors during the adaptation process, which distribute themselves like a gas within the data space. It is applied where data compression or vector quantization is an issue, for example speech recognition,[2] image processing[3] or pattern recognition. As a robustly converging alternative to the k-means clustering it is also used for cluster analysis.[4]

Algorithm

Given a probability distribution P(x) of data vectors x and a finite number of feature vectors wi, i=1,...,N.

With each time step t a data vector randomly chosen from P is presented. Subsequently, the distance order of the feature vectors to the given data vector x is determined. i0 denotes the index of the closest feature vector, i1 the index of the second closest feature vector etc. and iN-1 the index of the feature vector most distant to x. Then each feature vector (k=0,...,N-1) is adapted according to

${\displaystyle w_{i_{k}}^{t+1}=w_{i_{k}}^{t}+\varepsilon \cdot e^{-k/\lambda }\cdot (x-w_{i_{k}}^{t})}$

with ε as the adaptation step size and λ as the so-called neighborhood range. ε and λ are reduced with increasing t. After sufficiently many adaptation steps the feature vectors cover the data space with minimum representation error.[5]

The adaptation step of the neural gas can be interpreted as gradient descent on a cost function. By adapting not only the closest feature vector but all of them with a step size decreasing with increasing distance order, compared to (online) k-means clustering a much more robust convergence of the algorithm can be achieved. The neural gas model does not delete a node and also does not create new nodes.

Variants

A number of variants of the neural gas algorithm exists in the literature so as to mitigate some of its shortcomings. More notable is perhaps Bernd Fritzke's growing neural gas,[6] but also one should mention further elaborations such as the Growing When Required network[7] and also the incremental growing neural gas.[8]

Growing neural gas

Fritzke describes the growing neural gas (GNG) as an incremental network model that learns topological relations by using a "Hebb-like learning rule",[6] only, unlike the neural gas, it has no parameters that change over time and it is capable of continuous learning.

Growing when required

Having a network with a growing set of nodes, like the one implemented by the GNG algorithm was seen as a great advantage, however some limitation on the learning was seen by the introduction of the parameter λ, in which the network would only be able to grow when iterations were a multiple of this parameter.[7] The proposal to mitigate this problem was a new algorithm, the Growing When Required network (GWR), which would have the network grow more quickly, by adding nodes as quickly as possible whenever the network identified that the existing nodes would not describe the input well enough.

Incremental growing neural gas

Another neural gas variant inspired in the GNG algorithm is the incremental growing neural gas (IGNG). The authors propose the main advantage of this algorithm to be "learning new data (plasticity) without degrading the previously trained network and forgetting the old input data (stability)."[8]

References

1. ^ Thomas Martinetz and Klaus Schulten (1991). "A "neural gas" network learns topologies" (PDF). Artificial Neural Networks. Elsevier. pp. 397–402.
2. ^ F. Curatelli and O. Mayora-Iberra (2000). "Competitive learning methods for efficient Vector Quantizations in a speech recognition environment". In Osvaldo Cairó, L. Enrique Sucar, Francisco J. Cantú-Ortiz. MICAI 2000: Advances in artificial intelligence : Mexican International Conference on Artificial Intelligence, Acapulco, Mexico, April 2000 : proceedings. Springer. p. 109. ISBN 978-3-540-67354-5.
3. ^ Angelopoulou, Anastassia and Psarrou, Alexandra and Garcia Rodriguez, Jose and Revett, Kenneth (2005). "Automatic landmarking of 2D medical shapes using the growing neural gas network". In Yanxi Liu, Tianzi Jiang, Changshui Zhang. Computer vision for biomedical image applications: first international workshop, CVBIA 2005, Beijing, China, October 21, 2005 : proceedings. Springer. p. 210. doi:10.1007/11569541_22. ISBN 978-3-540-29411-5.
4. ^ Fernando Canales and Max Chacon (2007). "Modification of the growing neural gas algorithm for cluster analysis". In Luis Rueda, Domingo Mery, Josef Kittler, International Association for Pattern Recognition. Progress in pattern recognition, image analysis and applications: 12th Iberoamerican Congress on Pattern Recognition, CIARP 2007, Viña del Mar-Valparaiso, Chile, November 13–16, 2007 ; proceedings. Springer. pp. 684–693. doi:10.1007/978-3-540-76725-1_71. ISBN 978-3-540-76724-4.
5. ^
6. ^ a b Fritzke, Bernd (1995). "A Growing Neural Gas Network Learns Topologies". Advances in Neural Information Processing Systems. 7: 625–632. Retrieved 2016-04-26.
7. ^ a b Marsland, Stephen; Shapiro, Jonathan; Nehmzow, Ulrich (2002). "A self-organising network that grows when required". Neural Networks. 15 (8): 1041–1058. doi:10.1016/s0893-6080(02)00078-3. Retrieved 2016-04-26.
8. ^ a b Prudent, Yann; Ennaji, Abdellatif (2005). "An incremental growing neural gas learns topologies". Neural Networks, 2005. IJCNN'05. Proceedings. 2005 IEEE International Joint Conference on. 2: 1211–1216. Retrieved 2016-04-26.