Neural gas

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.

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]

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.

• 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.

• 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