Self Organizing Map -- ein Demonstrationsbeispiel


Erstellt von Uwe Schneider
März 2001









Das Problem
Die Self Organizing Map
Die Nachbarschaftsfunktion
Die Implementierung
Die Bedienoberfläche
Das Programmverhalten
Erkenntnisse
Systemumgebung
Download
Kontakt




Das Problem


Ein Ball soll durch einen Wagen aufgefangen werden. Wagen und Ball haben nur einen Freiheitsgrad, in der Bildebene nach links und rechts.


Auffangen eines Balls


Dabei sind:


Damit der Wagen den Ball auffangen kann, muß die folgende Bedingung erfüllt sein:
Auffangbedingung

Die Wagengeschwindigkeit ergibt sich also zu
Wagengeschwindigkeit
Dabei entspricht tGesamt der Gesamtzahl der Einzelbilder in der Animation und ist deshalb konstant. Des weiteren gilt für die Fallhöhe des Balls
Fallhöhe
Alle Größen in dieser Gleichung sind ebenfalls Konstanten. Es ist also zu erwarten, daß die Selbstorganisierende Karte diese linear abbildet.
Als variable Größen treten also nur die aktuelle Position des Wagens sowie die Geschwindigkeit des Balls auf. Die Startposition des Balls ist konstant in der Bildmitte.

<<




Die Self Organizing Map


Der Aufbau der Self Organizing Map ist aus der folgenden Abbildung ersichtlich.



Die Self Organizing Map



Legt man an die Map die Position des Wagens und die Ballgeschwindigkeit an und ermittelt das Gewinnerneuron, so soll das dritte Vektorelement des Gewinnerneurons die Geschwindigkeit, die der Wagen haben muß,um den Ball aufzufangen, enthalten. Die Pfeile deuten dies an.
Sensorische und motorische Karte sind also direkt miteinander gekoppelt.

<<




Die Nachbarschaftsfunktion


Zu Beginn enthält die Kohonenkarte innerhalb des zulässigen Wertebereichs zufällig initialisierte Vektoren. Im dreidimensionalen Raum dargestellt, ergibt sich folgendes Bild:


Ungeordnete Kohonenkarte

Die ungeordnete Kohonenkarte


Die in den Neuronen gespeicherten Werte kann man als Koordinaten im Darstellungsfeld auffassen, so werden diese in der Ansicht auch dargestellt. Kurze Linien bedeuten demnach angenäherte Werte, lange dagegen weit auseinanderliegende. Wie leicht einzusehen ist, stellt demnach eine perfekt formierte Map ein Koordinatengitter mit einer Maschenweite, die dem Wertebereich geteilt durch die Anzahl der Neuronen entspricht, dar. Die Linien verbinden die Koordinaten jeweils räumlich untereinander benachbarter Neuronen. Wie man anhand der Linienlängen sieht, haben hier benachbarte Neuronen noch höchst unterschiedliche Vektoren. Ziel ist es also, die Vektoren benachbarter Neuronen einander anzunähern.
Die wichtigste Größe bei der Formierung einer Kohonenkarte ist die Nachbarschaft des jeweiligen Gewinnerneurons. Die Ausdehnung, Form und Verringerung im Laufe des Adaptionsprozesses sind entscheidend für die spätere Qualität des Gitters. Im vorliegenden Beispiel wurde folgende Form gewählt.

Die Nachbarschaft


Das rote Neuron ist dasjenige mit dem dem Eingabevektor am nächsten liegenden Gewichtsvektor. Die grauen Neuronen zählen nicht zur Nachbarschaft. Alle dazwischenliegenden werden entsprechend ihrer Farbe mehr oder weniger stark in die Richtung des Eingabevektors verändert. Idealerweise erstreckt sich die Nachbarschaft am Anfang über alle Neuronen und nimmt dann mit fortschreitender Anpassung langsam ab. Auch andere Formen wären denkbar, wurden hier aber nicht ausprobiert.
Als Funktion, die den Radius der beeinflussten Nachbarschaft bestimmt, wurde die folgende ausgewählt:
Nachbarschaft
N(t) ist eine linear abfallende Funktion, die mit einem Wert beginnt, der alle Neuronen beinhaltet. Der Abfall bewegt sich in der Größenordnung von 10-5.
Der Parameter p(t) ist die Anzahl der durchlaufenen Lernschritte. Der Exponent r(t) ist ebenfalls eine linear abfallende Funktion, die ungefähr bei 10-1 startet und mit jeder Iteration um einen Wert von 10-6 anwächst. Die Lernrate wird im Laufe der Zeit folgendermaßen angepaßt:
Lernrate
Hier ist p(t) wieder die Anzahl der Iterationen und q(t) verhält sich wie r(t), allerdings mit einem Anstieg von nur etwa 10-7. Hier diese Funktion in einer 3-D-Darstellung:
Lernrate
Der ansteigende Exponent bewirkt, daß der Algorithmus schneller zum Stehen kommt, ist allerdings kritisch, weil ein zu schnelles Absinken das räumliche Gitter der abgebildeten Vektoren stark verzerren kann. Innerhalb der ermittelten Nachbarschaft wird die Anpassung nach folgender Formel ermittelt:
Anregung in der Nachbarschaft
Hier steht z für den euklidischen Abstand zwischen den Indexvektoren des Gewinnerneurons und des j-ten Neurons in der Map. Der Gewichtsvektor wird um den H-ten Teil der Differenz zwischen Sollwert und Istwert in die Richtung des Sollwertes verschoben. Wie man sieht, kann der Anpassungskoeffizient auch negative Werte annehmen. Das bewirkt, daß die Karte besonders in der Anfangsphase schnell auseinanderstrebt.

<<




Die Implementierung


Wie man aus der Problematik unschwer erkennen kann, besitzt ein Neuron vier unmittelbare Nachbarn. Aufgabe der Kohonenkarte ist die Klassifizierung eben dieser Nachbarn. Das bedeutet, daß auch die Datenstruktur diese Eigenschaft widerspiegeln muß. Ein eindimensionales Gebilde würde diese Forderung nicht erfüllen. Man kann diesen Sachverhalt leicht überprüfen, indem man im Beispielprogramm eine Karte mit nur einem Neuron in einer Dimension erzeugt. Die Map wird dann Also kommt für die sensorische und die motorische Karte naturgemäß nur eine Matrix in Frage. Es bietet sich an, die beiden Karten miteinander zu verbinden, so daß alle Vektorverschiebungen in einem einzigen Zugriff erfolgen können.

<<




Die Bedienoberfläche


Hier nun die Bedienoberfläche des Programms.


Bedienoberfläche

Die Schaltflächen "Start" und "Stop" starten bzw. stoppen die Animation. Mit "Trainiere Som" und "Stop Training" wird der Lernprozeß der Kohonenkarte angestoßen oder angehalten. Mit dem Button "Einstellungen" wird der Dialog zur Konfiguration des Programms geöffnet.


Bedienoberfläche

Breite und Länge legen die Abmessungen der Map fest, auch nichtquadratische Karten sind möglich. Obwohl das Programm mit sehr großen Werten zurecht kommt, steigen die Rechenzeiten dann natürlich sehr stark an, auch die grafische Darstellung macht dann keinen Sinn mehr. Deshalb wurden beide Werte auf 300 begrenzt. Die Lernrate ist zwischen 0 und 1 variierbar wird aber beim voreingestellten Wert von 0.6 gute Ergebnisse liefern. Der Exponent für den Abfall der Lernrate entspricht dem Parameter r(t) in obiger Gleichung. Der Nachbarschaftsradius ist standardmäßig auf 2/3 der größeren Ausdehnung eingestellt. Damit ist sichergestellt, daß anfänglich alle Neuronen erfaßt werden. Der Exponent für den Abfall der Nachbarschaft ist der Parameter q(t). Die Anzahl der Lernschritte pro Zyklus ist frei wählbar, sinvoll ist eine Größenordnung von 100000. Die Pause zwischen zwei Animationen kann zwischen 0.1 und 5.0 Sekunde gewählt werden. Die Toleranz beim Auffangen legt den maximalen Abstand fest, den der Ball beim Aufschlagen von der Wagenmitte haben darf und ist zwischen 22 und 30 Pixeln wählbar. Die Wagenbreite entspricht demnach der doppelten Toleranz Mit dem Wert Schritte zwischen Neuzeichnen kann festgelegt werden, nach wievielen Trainingsschritten der Zustand der Karten neu dargestellt werden soll. Hier sind Werte zwischen 1 und 10000 möglich. Da die Neudarstellung einen erheblichen Anteil an der Rechenzeit ausmacht, ist es bei größeren Netzen sinnvoll, diesen Wert nicht zu gering einzustellen.
Alle Werte können natürlich während des Trainings jederzeit verändert werden. Mit "OK" werden geänderte Daten übernommen. Bei Änderung von Breite und Länge findet zusätzlich eine Initialisierung statt. "Init" setzt das Netz auf zufällige Daten zurück, die restlichen Daten, die mit den Abmessungen in direktem Zusammenhang stehen werden auf Standardwerte gesetzt. Mit "Export" können die aktuellen Netzdaten in eine ASCII.Datei exportiert und mit Hilfe eines normalen Editors angesehen oder einem Programm wie z.B. Maple analysiert werden.
Hinter dem Knopf "Monitor" verbirgt sich ein kleines Dialogfeld, in dem die Anzahl der absolvierten Trainingsrunden sowie die erfolgreichen und erfolglosen Auffangversuche des Wagens angezeigt werden.


Monitor

Mit der Schaltfläche "Netzdaten" kann die grafische Anzeige der Map aktiviert werden. Beendet wird das Programm durch Drücken der Schaltfläche "Beenden".

<<




Das Programmverhalten


Beim Programmstart sind alle Vektoren der Map in zufällig initialisiertem Zustand, das heißt, daß es eher unwahrscheinlich ist, daß der Wagen den Ball fängt. Wir wollen im folgenden von einer Map mit 30 mal 30 Neuronen ausgehen. In der grafischen Darstellung sieht das so aus:


Unsortierte Karte

Die Titelleiste zeigt jeweils an, welche Ebene gerade dargestellt wird. Bereits beim zweiten Schritt fällt die Karte in sich zusammen:


Karte nach dem zweiten Schritt

Und nach dem 10. Schritt ist schon die Entfaltung zu erkennen:


Karte nach dem 10. Schritt

Nach 100 Schritten:


Karte nach dem 100. Schritt

Nach 30000 Schritten zeichnet sich bereits eine Gitterstruktur, die parallel zu den Bereichsgrenzen verläuft, ab und das Bild paßt sich in den Darstellungsraum ein:


Karte nach dem 30000. Schritt

Nach 100000 Schritten ist die Karte im wesentlichen formiert. Da der Nachbarschaftradius jetzt soweit gesunken ist, daß vom jeweiligen Gewinnerneuron weiter entfernte Neuronen nicht mehr beeinflusst werden, müssen jetzt die gröbsten Verwerfungen bereinigt sein, da das sonst jetzt nicht mehr möglich wäre.


Karte nach dem 100000. Schritt

Die fertige Karte nach 200000 Schritten hat dann nur noch geringe Fehler, nur an den Rändern treten einige Verwerfungen auf:


Karte nach dem 200000. Schritt

Die Wagengeschwindigkeit, in Relation zur Wagenposition gesetzt, ergibt jetzt das folgende Bild:


Karte nach dem 200000. Schritt in X-Z Ebene

Und die Wagengeschwindigkeit zur Ballgeschwindigkeit dieses:


Karte nach dem 200000. Schritt in Y-Z Ebene

Hier noch das Bild einer Karte mit 80 mal 80 Neuronen nach 300000 Trainingsschritten. Durch die wesentlich höhere Auflösung der Abbildung der Eingangswertebereiche auf das Neuronengitter werden die globalen Strukturfehler gemindert und die Karte erreichte bei einer Toleranz von 24 Pixeln eine Fehlerquote von nur 10-5, das heißt, daß bei 100000 geworfenen Bällen nur einer nicht aufgefangen wurde.


Karte mit 80 mal 80 Neuronen




<<




Erkenntnisse


Wie bereits erwähnt, ist die Nachbarschaftsfunktion von essentieller Bedeutung für die Funktionsfähigkeit einer Self Organizing Map. Da man Kompromisse zwischen langsamem Abfall des Nachbarschaftsbereichs und der Rechenzeit treffen muß, erreicht das Koordinatengitter sicherlich nicht seine maximale Güte. Um aber die vorliegende Software zu Lern- und Demonstrationszwecken einsetzen zu können, wurde der Algorithmus so optimiert, daß nach etwa 300000 Lernzyklen ein stabiles Netz entsteht. Bei schnellerem Abfallen der beeinflussten Nachbarschaft entstehen signifikante Gitterfehler, wie der Nutzer leicht herausfinden kann, indem er die Parameter im Einstellungsdialog von Hand verändert.
Damit die Map eine gute Fehlerquote liefert, muß sie ausreichend Neuronen enthalten. Bei Abmessungen von weniger als 30 mal 30 ist kaum eine ausreichende Auflösung der Eingabedaten zu erwarten. Es hat sich herausgestellt, daß die Maschenweite eines formierten Netzes zu den Rändern zu abnimmt.
Die oben geäußerte Erwartung einer linearen Abbildung der Übertragungsfunktion zwischen Ein- und Ausgabedaten hat sich bestätigt, wie man unschwer in den Abbildungen des formierten Netzes erkennen kann.
Da die beiden Eingabegrößen Wagenposition und Ballgeschwindigkeit stark unterschiedliche Wertebereiche besitzen, hat sich eine Normierung erforderlich gemacht, da ansonsten eine Überbetonung der Wagenposition stattfand, das Netz verformte sich u-förmig.
Als sehr leistungsfähig hat sich die oben beschriebene Funktion für die Verschiebung der Gewichtsvektoren innerhalb des effektiven Nachbarschaftsbereichs erwiesen. Die Karte entfaltet sich damit innerhalb kürzester Zeit.


<<



Die Systemumgebung


Das Programm wurde unter dem Betriebssystem Windows NT 4.0 (Service Pack 4) mit den Mitteln der MFC unter Visual C++ 6.0 entwickelt und läuft dort stabil. Die Verwendung unter Windows 98 ist aus technischen Gründen nicht möglich, da Timer verwendet werden, deren Intervalle für besagtes Betriebssystem zu kurz sind.


<<




Download

Für den, der es einmal selbst ausprobieren möchte, hier das ausführbar Programm für Windows NT : Som.exe

Kontakt

Bei Fragen zum Thema Self Organizing Map eine E-mail an: Uwe Schneider



<<