2.2.4 Neural Gas

Martinetz et al. (1993) presented an algorithm called `Neural Gas' that outperforms deterministic annealing (Rose et al., 1990). Neural Gas is also a variant of soft-clustering, and it also uses annealing. In contrast, Neural Gas has a different (heuristic) assignment, and it can be only carried out as an on-line version.

The algorithm starts by randomly choosing m data points as starting points for the m code-book vectors. The annealing consists of a predefined number of t_max steps. During each annealing step t, a pattern $\bf x_{i}^{}$ is randomly drawn from the training set. Then, the code-book vectors are sorted in the order of their Euclidean distance to $\bf x_{i}^{}$. Let k($\bf x_{i}^{}$,$\bf c_{j}^{}$(t)) be the resulting rank of each code-book vector, with k = 0 for the closest vector, and k = m - 1 for the most distant vector. The soft-assignment is then given by the function h_$\varrho$^ij = exp(- k($\bf x_{i}^{}$,$\bf c_{j}^{}$(t))/$\varrho$). The parameter $\varrho$ is a measure of the neighborhood range. Given this assignment, all code-book vectors $\bf c_{j}^{}$ are updated according to

$$\bf c_{j}^{} \bf c_{j}^{} \varepsilon \varrho \left[\vphantom{{\bf x}_i - {\bf c}_j(t)}\right. \bf x_{i}^{} \bf c_{j}^{} \left.\vphantom{{\bf x}_i - {\bf c}_j(t)}\right]$$ (2.15)

During the annealing process both parameters $\varepsilon$ and $\varrho$ decrease exponentially, $\varrho$(t) = $\varrho$(0)[$\varrho$(t_max)/$\varrho$(0)]^(t/t_max), and $\varepsilon$(t) = $\varepsilon$(0)[$\varepsilon$(t_max)/$\varepsilon$(0)]^(t/t_max). At the end of the annealing, the algorithm changes to on-line k-means, and thus, also (locally) minimizes (2.12). The exponential decay of $\varepsilon$ enforces convergence. Neural Gas is stable and does not depend on the initial configuration of {$\bf c_{i}^{}$} (Martinetz et al., 1993).