Neural Gas

Neural Gas ist ein an selbstorganisierende Karten angelehnter, lernender Algorithmus zur Klassifizierung vektorieller Daten.

Er wurde 1991 von Thomas Martinetz und Klaus Schulten vorgestellt.^[1] Die Bezeichnung begründet sich auf der Dynamik der Merkmalsvektoren, deren Verteilung im Datenraum während des Lernprozesses an die Ausbreitung eines Gases erinnert. Anwendung findet es überall dort, wo Datenkompression oder Vektorquantisierung durchgeführt werden müssen, also zum Beispiel in der Spracherkennung, der Bildverarbeitung oder der Mustererkennung. Als robust konvergierende Alternative zum k-Means-Algorithmus wird es auch zur Clusteranalyse eingesetzt. Prominente Erweiterungen des Neural Gas sind das Growing Neural Gas und die Topology Representing Networks.

Arbeitsweise

Gegeben sei eine Häufigkeitsverteilung P(x) von Datenvektoren x sowie eine endliche Zahl von Merkmalsvektoren w_i, i=1,...,N.

Mit jedem Zeitschritt t wird ein zufällig aus P gewählter Datenvektor präsentiert. Danach wird zunächst die Entfernungsrangfolge der Merkmalsvektoren zum gegebenen Datenvektor x bestimmt. i₀ bezeichnet den Index des nächstliegenden Merkmalsvektors, i₁ den Index des zweitnächsten usw. und i_N-1 den Index des zu x entferntesten Merkmalsvektors. Dann wird jeder Merkmalsvektor adaptiert. Der Adaptionsschritt lautet für k=0,...,N-1

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

mit ε als Adaptionsschrittweite und λ als sogenannte Nachbarschaftsreichweite. ε und λ nehmen dabei mit der Zahl t der Adaptionsschritte ab. Nach ausreichend vielen Adaptionsschritten decken die Merkmalsvektoren den Datenraum gleichmäßig ab.

Kommentare

Der Adaptionsschritt des Neural Gas kann als Gradientenabstieg auf einer Kostenfunktion interpretiert werden.
Durch Adaption nicht nur des nächstliegenden Merkmalsvektors, sondern in abnehmendem Maße auch der im Entfernungsrang folgenden Merkmalsvektoren wird im Vergleich zum K-Means-Algorithmus eine robuste und von der Initialisierung weitgehend unabhängige Konvergenz erzielt.
Als Lernrate hat sich bewährt:

\epsilon (t)=\epsilon _{\text{start}}\cdot \left({\frac {\epsilon _{\text{end}}}{\epsilon _{\text{start}}}}\right)^{\frac {t}{t_{\text{max}}}}

mit ε_start = 1 als Startlernrate und ε_end = 0,001 als Lernrate zum Ende des Verfahrens, d. h. nach t_max Stimuluspräsentationen.

Als Nachbarschaftreichweite hat sich bewährt:

\lambda (t)=\lambda _{\text{start}}\cdot \left({\frac {\lambda _{\text{end}}}{\lambda _{\text{start}}}}\right)^{\frac {t}{t_{\text{max}}}}

mit λ_start = N/2 als Reichweite zu Beginn und λ_end = 0,01 als Reichweite zum Ende des Verfahrens.

Literatur

T. M. Martinetz, K. J. Schulten: A „neural-gas“ network learns topologies. Konferenzbeitrag zur ICANN-91, Espoo, Finnland, S. 397–402 in K. Mäkisara et al. (Hrsg.): Artificial Neural Networks, North-Holland, Amsterdam, 1991, ISBN 9780444891785.
T. Martinetz, S. Berkovich, K. Schulten: „Neural-gas“ Network for Vector Quantization and its Application to Time-Series Prediction. IEEE-Transactions on Neural Networks 4, 1993, S. 558–569.
T. Martinetz, K. Schulten: Topology representing networks. Neural Networks 7, 1994, S. 507–522.

Einzelnachweise

↑ Oliver Kramer: Dimensionality Reduction with Unsupervised Nearest Neighbors. Springer, 2013, ISBN 978-3-642-38651-0, eingeschränkte Vorschau in der Google-Buchsuche.

Weblinks

Growing Neural Gas videos.
DemoGNG Java-Applet (mit Quelltext) Neural Gas, Growing Neural Gas und andere Verfahren des kompetitiven Lernens.
Neural Gas Clock Demo
Java Competitive Learning Applications Unsupervised Neural Networks (including Self-organizing map) in Java mit Quelltexten.

[1] Oliver Kramer: Dimensionality Reduction with Unsupervised Nearest Neighbors. Springer, 2013, ISBN 978-3-642-38651-0, eingeschränkte Vorschau in der Google-Buchsuche.

[1]