Neural 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 ${\displaystyle P(x)}$ of data vectors ${\displaystyle x}$ and a finite number of feature vectors ${\displaystyle w_{i},i=1,\cdots ,N}$.

With each time step ${\displaystyle t}$, a data vector ${\displaystyle x}$ randomly chosen from ${\displaystyle P(x)}$ is presented. Subsequently, the distance order of the feature vectors to the given data vector ${\displaystyle x}$ is determined. Let ${\displaystyle i_{0}}$ denote the index of the closest feature vector, ${\displaystyle i_{1}}$ the index of the second closest feature vector, and ${\displaystyle i_{N-1}}$ the index of the feature vector most distant to ${\displaystyle x}$. Then each feature vector 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}),k=0,\cdots ,N-1}$

with ${\displaystyle \varepsilon }$ as the adaptation step size and ${\displaystyle \lambda }$ as the so-called neighborhood range. ${\displaystyle \varepsilon }$ and ${\displaystyle \lambda }$ are reduced with increasing ${\displaystyle 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]. A performance-oriented approach that avoids the risk of overfitting is the Plastic Neural gas model [9].

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, i.e. learning on data streams. GNG has been widely used in several domains,[10] demonstrating its capabilities for clustering data incrementally. The GNG is initialized with two randomly positioned nodes which are initially connected with a zero age edge and whose errors are set to 0. Since the in the GNG input data is presented sequentially one by one, the following steps are followed at each iteration:

• It is calculated the errors (distances) between the two closest nodes to the current input data.
• The error of the winner node (only the closest one) is respectively accumulated.
• The winner node and its topological neighbors (connected by an edge) are moving towards the current input by different fractions of their respective errors.
• The age of all edges connected to the winner node are incremented.
• If the winner node and the second-winner are connected by an edge, such an edge is set to 0. If case there are created, an edge is created between them.
• If there are edges with an age larger than a threshold, they are removed. Nodes without connections are eliminated.
• If the current iteration is an integer multiple of a predefined frequency-creation threshold, a new node is inserted between the node with the largest error (among all) and its topological neighbor presenting the highest error. The link between the former and the latter nodes is eliminated (their errors are decreased by a given factor) and the new node is connected to both of them. The error of the new node is initialized as the updated error of the node which had the largest error (among all).
• The accumulated error of all nodes is decreased by a given factor.
• If the stopping criterion is not met, the algorithm takes a following input. The criterion might be a given number of epochs, i.e., a pre-set number of times where all data is presented, or the reach of a maximum number of nodes.

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]

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.

Plastic neural gas

The ability to only grow a network may quickly introduce overfitting; on the other hand, removing nodes on the basis of age only, as in the GNG model, does not ensure that the removed nodes are actually useless, because removal depends on a model parameter that should be carefully tuned to the "memory length" of the stream of input data.

The "Plastic Neural Gas" model [9] solves this problem by making decisions to add or remove nodes using an unsupervised version of cross-validation, which controls an equivalent notion of "generalization ability" for the unsupervised setting.

Implementations

To find the ranking ${\displaystyle i_{0},i_{1},\ldots ,i_{N-1}}$ of the feature vectors, the neural gas algorithm involves sorting, which is a procedure that does not lend itself easily to parallelization or implementation in analog hardware. However, implementations in both parallel software [11] and analog hardware[12] were actually designed.

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 (eds.). 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.CS1 maint: uses authors parameter (link)
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 (eds.). 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.CS1 maint: uses authors parameter (link)
4. Fernando Canales and Max Chacon (2007). "Modification of the growing neural gas algorithm for cluster analysis". In Luis Rueda; Domingo Mery (eds.). 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.CS1 maint: uses authors parameter (link)
5. http://wwwold.ini.rub.de/VDM/research/gsn/JavaPaper/img187.gif%5B%5D
6. Fritzke, Bernd (1995). "A Growing Neural Gas Network Learns Topologies". Advances in Neural Information Processing Systems. 7: 625–632. Retrieved 2016-04-26.
7. Marsland, Stephen; Shapiro, Jonathan; Nehmzow, Ulrich (2002). "A self-organising network that grows when required". Neural Networks. 15 (8): 1041–1058. CiteSeerX 10.1.1.14.8763. doi:10.1016/s0893-6080(02)00078-3. PMID 12416693.
8. 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. pp. 1211–1216. doi:10.1109/IJCNN.2005.1556026. ISBN 978-0-7803-9048-5.
9. Ridella, Sandro; Rovetta, Stefano; Zunino, Rodolfo (1998). "Plastic algorithm for adaptive vector quantisation". Neural Computing & Applications. 7: 37–51. doi:10.1007/BF01413708.
10. Iqbal, Hafsa; Campo, Damian; Baydoun, Mohamad; Marcenaro, Lucio; Martin, David; Regazzoni, Carlo. "Clustering Optimization for Abnormality Detection in Semi-Autonomous Systems". st International Workshop on Multimodal Understanding and Learning for Embodied Applications. doi:10.1145/3347450.3357657.
11. Ancona, Fabio; Rovetta, Stefano; Zunino, Rodolfo (1996). A parallel approach to plastic neural gas. Proceedings of International Conference on Neural Networks (ICNN'96). doi:10.1109/ICNN.1996.548878.
12. Ancona, Fabio; Rovetta, Stefano; Zunino, Rodolfo (1997). Hardware implementation of the neural gas. Proceedings of International Conference on Neural Networks (ICNN'97). doi:10.1109/ICNN.1997.616161.

Further reading

• T. Martinetz, S. Berkovich, and K. Schulten. "Neural-gas" Network for Vector Quantization and its Application to Time-Series Prediction. IEEE-Transactions on Neural Networks, 4(4):558-569, 1993.
• Martinetz, T.; Schulten, K. (1994). "Topology representing networks". Neural Networks. 7 (3): 507–522. doi:10.1016/0893-6080(94)90109-0.

External links

• DemoGNG.js Javascript simulator for Neural Gas (and other network models)
• Java Competitive Learning Applications Unsupervised Neural Networks (including Self-organizing map) in Java with source codes.
• formal description of Neural gas algorithm
• A GNG and GWR Classifier implementation in Matlab