Selbstorganisierende Karten

Selbstorganisierende Karten
Jochen Weiß
Inhaltsverzeichnis
1
Das menschliche Gehirn als Vorbild
2
2
Architektur einer SOM
3
2.1
Aufbau der Neuronenschichten
3
2.2
Gewichts- und Eingabevektor
3
3
Das Training der Karte
4
3.1
Bestimmung des Siegerneurons
4
3.2
Adaption der Gewichtsvektoren
5
3.3
Nachbarschafts- und Lernratenfunktion
6
3.4
Der Lernalgorithmus
8
4
Anwendungsbeispiel: das Rundreiseproblem
Literatur
11
13
Zusammenfassung
Bei Selbstorganisierenden Karten (nach ihrem Entwickler auch Kohonen-Karten
oder Kohonen Feature Maps genannt) handelt es sich um ein spezielles neuronales
Netz, das — wie der Name schon sagt — sich selbst organisiert, also im Gegensatz zum Perzeptron ohne Lehrer auskommt, der nach jeder Eingabe die Ausgabe
überprüft und ggF. die Verbindungsgewichte anpaßt, um die Ausgabe zu korrigieren. Ein weiteres spezifisches Merkmal der SOMs (Selforganizing Map) ist, dass
auch die räumliche Anordnung der Neuronen untereinander eine wichtige Rolle im
Lernverfahren spielt.
27. Mai 2004
1
Das menschliche Gehirn als Vorbild
Eine SOM erstellt aus den Eingaben eine topographische Karte. Je ähnlicher
zwei Eingaben sind, desto näher liegen die dadurch aktivierten Neuronen beieinander. Einander sehr ähnliche Eingabemuster werden von der SOM also
auch benachbart dargestellt. Vorbild für diese Topologieerhaltung ist — wie
so oft bei neuronalen Netzen — das menschliche Gehirn.
Abbildung 1. Topologieerhaltung im Menschlichen Gehirn
In Abbildung 1 ist auf der linken Seite die somatosensorische Hirnrinde —
zuständig für den Tastsinn — und auf der rechten Seite die motorische Rinde
zu sehen. Die einzelnen Körperteile sind bei ihrer jeweils zuständigen Hirnregion angeordnet. Es ist gut zu erkennen, dass benachbarte Hirnregionen
auch benachbarte bzw. ähnliche Körperteile kontrollieren: z.B. liegt das Areal
für den Tastsinn der Arme direkt neben der Hirnregion für die Hände. Wie
das menschliche Gehirn Sinneseindrücke wirklich verarbeitet und speichert,
ist noch nicht genügend erforscht. Unter anderem ist die selbstorganisierende Karte dazu entwickelt worden, mehr Einblick in die Organisationsweise
unseres Gehirns zu geben.
2
2
2.1
Architektur einer SOM
Aufbau der Neuronenschichten
Eine selbstorganisierende Karte besteht aus zwei Schichten. Die Eingabeschicht (UI ) setzt sich aus den Eingabeneuronen, die Ausgabeschicht (UO )
— auch Kohonen- oder Kartenschicht genannt — aus den Ausgabe- oder
Kohonenneuronen zusammen. Die Eingabeschicht ist mit den Neuronen der
Ausgabeschicht voll vernetzt: jedes Neuron der Eingabeschicht ist mit allen
Ausgabeneuronen durch Gewichte verbunden. Gewichtete Verbindungen innerhalb der Ausgabeschicht gibt es allerdings nicht, jedoch spielt im späteren
Lernverfahren die räumliche Anordnung der Kartenneuronen eine wichtige
Rolle.
Abbildung 2. Architektur einer SOM
Die Ausgabeschicht kann unterschiedliche Dimensionen annehmen. Am häufigsten werden zwei-dimensionale quadratische Neuronengitter eingesetzt. Allerdings sind auch drei- oder mehr-dimensionale Gitter möglich. Die Position
jedes Kohonenneurons wird dabei durch den Koordinatenvektor angegeben,
der bei der Initialisierung der SOM festgelegt und auch im Laufe des Trainings nicht mehr verändert wird.
2.2
Gewichts- und Eingabevektor
Jedes Eingabeneuron schickt einen Eingabewert an alle Neuronen der Kartenschicht. Faßt man die einzelnen Eingaben zusammen, ergibt dies das Eingabemuster bzw. den Eingabevektor:
3
x = (x1 , x2 , ..., xi ),
i =Anzahl der Eingabeneuronen
Aus den einzelnen Gewichten, die ein Ausgabeneuron zu jedem Eingabeneuron besitzt, kann jedem Kohonenneuron j ein Gewichtsvektor wj zugewiesen
werden:
wj = (w(1,j) , w(2,j) , ..., w(i,j) ),
i =Anzahl der Eingabeneuronen
Die Gewichtsvektoren aller Neuronen bestimmen die sog. Netzstruktur einer
SOM. Diese kann über die Gewichtsvektoren visualisiert werden. Für eine
SOM mit zwei Eingabeneuronen — also zweidimensionalen Gewichtsvektoren
— und 10x10 Kartenneuronen kann dies z.B. folgendermaßen aussehen:
Abbildung 3. Visualisierung der Gewichte
Abbildung 3 zeigt ein Koordinatensystem, an deren X-Achse der Wert des
Gewichts des Kartenneurons j zum Eingabeneuron 1 und an der Y-Achse das
Gewicht zum Eingabeneuron 2 eingetragen ist. Eine solche Darstellung kann
jedoch nur bei zweidimensionalen Eingabedaten verwirklicht werden.
3
3.1
Das Training der Karte
Bestimmung des Siegerneurons
Eine SOM bewertet für ein Eingabemuster die Ähnlichkeit zu jedem Gewichtsvektor und bestimmt ein sog. Siegerneuron, auch Prototyp genannt. Dieses
Siegerneuron repräsentiert die Eingabe von allen Kartenneuronen am besten.
Für die Bewertung der Ähnlichkeit gibt es zwei verschiedene Methoden. Am
plausibelsten jedoch ist die minimale Euklidische Distanz zwischen Eingabeund Gewichtsvektor:
s
j(X) = arg min k X − Wj k= arg min
j
j
4
i
P
n=1
(xi − wij )2
Wobei j(x) das Siegerneuron des Eingabemusters X, i die Anzahl der Eingabeneuronen, xi der Eingabewert des i-ten Neurons und wij ein einzelnes Gewicht
des Neurons j zum i-ten Eingabeneuron ist.
Abbildung 4. Minimale Euklidische Distanz
Abbildung 4 zeigt anschaulich die Bestimmung der minimalen Euklidischen
Distanz zwischen einem Eingabevektor und einem Gewichtsvektor. Sie ist
nichts anderes als die Entfernung zweier Vektoren und damit ein Maß für
die Ähnlichkeit dieser.
Nun kann es allerdings vorkommen, dass zwei Gewichtsvektoren die gleiche
euklidische Distanz zum Eingabevektor aufweisen. In solchen Fällen wird entweder zufällig oder ein beliebiger Vektor aus dieser Gruppe gewählt und dessen
Neuron als Sieger bestimmt.
Eine weitere Möglichkeit zur Bestimmung des Siegerneurons ist das maximale Skalarprodukt der beiden Vektoren, aber da, wie schon erwähnt, die
euklidische Distanz am plausibelsten für die Ähnlichkeit ist, wird diese auch
hauptsächlich verwendet.
Ist das Siegerneuron bestimmt, wird nach dem Winner-Takes-All-Prinzip die
Ausgabe des Siegerneurons auf 1, die aller anderen Kartenneuronen auf 0 gesetzt.
3.2
Adaption der Gewichtsvektoren
Jetzt beginnt erst das eigentliche Training der Karte. Die Gewichtsvektoren
des Siegerneurons und die seiner umliegenden Neuronen werden an den Eingabevektor mit Hilfe einer Lernvorschrift angepaßt. Dabei spielt der Grad der
Nachbarschaft zum Siegerneuron eine große Rolle. Vereinfachend beschränken
wir diese Adaption erst einmal auf das Siegerneuron, da dieses sich selbst am
nächsten ist und damit zu 100% lernt:
∆wi,j = α(xi − wi,j )
Dabei ist α die sog. Lernrate, die nach jeder Epoche verkleinert wird, um den
Lernfortschritt der Karte im Laufe des Trainings zu verringern. Sind alle vorhandenen Eingabemuster der Karte einmal präsentiert worden, beginnt eine
neue Epoche, in der wieder alle Muster eingegeben werden. Dies wird solange
wiederholt bis die Lernrate auf 0 gesunken oder eine andere Abbruchbedingung erfüllt ist.
Um die anfangs erwähnte Topologieerhaltung, also die benachbarte Anord5
nung (Aktivierung des Siegerneurons) ähnlicher Eingabemuster in der Karte,
zu gewährleisten, müssen auch Neuronen in der Nachbarschaft des Siegerneurons in den Lernprozess mit einbezogen werden. Dies erfolgt über die Kombination verschiedener Funktionen.
3.3
Nachbarschafts- und Lernratenfunktion
Eine Nachbarschaftsfunktion berechnet den Grad der Nachbarschaft, welcher
zwischen 0 und 1 liegt, eines Ausgabeneurons zum Siegerneuron. Die Nachbarschaftsfunktion ist von den Werten einer Distanz- und Radiusfunktion
abhängig. Letztere bestimmt den Abstand der Ausgabeneuronen zum Siegerneuron und beruht meist auf der Basis der euklidischen Norm. Zu einem
(D)
gegebenen Koordinatenvektor hj des Neurons j, mit der Dimension D, berechnet diese den Abstand zum Ursprung des Koordinatensystems:
s
reukl (hj ) =
D
P
n=1
(n)
(hj )2
Der Abstand zum Siegerneuron mit dem Koordinatenvektor hj 0 wird an der
Stelle hj − hj 0 berechnet. Für das Siegerneuron selbst ist der Wert der Radiusfunktion also 0. Diese kann im übrigen auch auf Basis der Eins- oder
Maximumsnorm beruhen:
• reins (hj ) =
D
P
n=1
(n)
| hj
|
(1)
(D)
• rmax (hj ) = max{| hj | .... | hj
|}
Da im Laufe des Trainings nach jedem Eingabemuster der Einflussbereich
des Siegerneurons abnehmen soll, wird eine monoton fallende Distanzfunktion
benötigt. Dies ist sinnvoll, da sich die Karte so besser entfalten kann und
schneller konvergiert. Mögliche Funktionen sind folgende:


 c(1 −
• lineare Distanzfunktion: dlin (t) = 

t
)
te nd
für t < tend
0 sonst
−tc2
• exponentielle Distanzfunktion: dexp (t) =qc1 e
• Wurzel-Distanzfunktion: dwurzel (t) = c1 ( 1t )c2
Wobei t die aktuelle, und tend die Epoche, bei der das Training abgebrochen
werden soll, darstellt.
Die Ergebnisse der Radius- und Distanzfunktion werden der Nachbarschaftsfunktion als Parameter übergeben, welche den Grad der Nachbarschaft liefert. Dieser bestimmt letztendlich wie stark die Gewichte der Neuronen ange6
paßt werden. Auch hier sind verschiedene Arten von Funktionen, wie z.B. die
Gauß’sche Glockenkurve oder die Mexican-Hat-Funktion, anwendbar.
Die simpelste Nachbarschaftsfunktion ist die Rechtecksfunktion:
• frechteck (r, d) =


1
r<d

0
sonst
Alle Neuronen im Einflussbereich des Siegerneurons erhalten den Nachbarschaftsgrad 1 — lernen also so wie das Siegerneuron — alle anderen Neuronen
erfahren keine Veränderung ihrer Gewichte.
Eine weitere Möglichkeit zur Berechnung des Nachbarschaftsgrads liefert die
aus der Wahrscheinlichkeitsrechnung bekannte Gauß’sche Glockenkurve:
r
• fgauss (r, d) = e−( d )
Folgende Abbildung zeigt den Nachbarschaftsgrad über die Gaussfunktion für
eine zweidimensionale Ausgabeschicht. Das Siegerneuron liegt hier im Koordinatenursprung:
Abbildung 5. Gauß’sche Glockenkurve
Die Mexican-Hat-Funktion ist in Abbildung 6 zu sehen. Sie besitzt einen
negativen Wertebereich. Die Gewichte der Neuronen mit einem solchen Nachbarschaftsgrad werden dem Eingabemuster nicht ähnlicher gemacht, sondern
noch mehr verfälscht. Laut [Läm01] hat dies jedoch ein Divergieren der Karte
zur Folge, weshalb in der Praxis auf diese Abstoßung der Gewichte verzichtet
wird.
7
Abbildung 6. Mexican-Hat-Funktion
Die schon angesprochene Lernratenfunktion verhält sich ähnlich wie die
Distanzfunktion, weshalb hier nur eine spezielle Funktion angesprochen werden soll: die Ordering-Phase-Funktion
Sei t die aktuelle Epoche, torder eine Epoche, ab der die Lernrate konstant
bleibt, und tend die Anzahl der insgesamt zu durchlaufenden Epochen:
α=



c −






0,8c
torder



1−






3.4
· c falls t < torder
0, 2 falls torder < t ≤ 0, 8 · t
1
tend
· t falls 0, 8 · tend < t ≤ tend
0 sonst
Der Lernalgorithmus
Nachdem nun alle nötigen Funktionen definiert und erklärt wurden, kann nun
der Lernalgorithmus formuliert werden. Man unterscheidet bei selbstorganisierenden Karten zwischen zwei verschiedenen Lernmethoden, dem musterweisen und epochenweisen Lernen. Beim musterweisen Lernen erfolgt die Adaption der Gewichtsvektoren nach jedem Eingabemuster, das an die Eingabeschicht angelegt wurde, wohingegen beim epochenweisen Lernen die Gewichtsanpassung erst nach Durchlaufen einer kompletten Epoche, also nach Eingabe
aller vorhandenen Eingabemuster, vorgenommen wird. Am häufigsten wird
8
jedoch das musterweise Lernen verwendet, weshalb wir uns auf diesen Algorithmus beschränken:
Algorithm 1 Musterweises Lernen einer SOM
1: Initialisiere die Verbindungsgewichte wj
. Erklärung s.u.
2: Bestimme für jedes Eingabemuster X das Siegerneuron j(X) :
s
j(X) = arg min k X − Wj k= arg min
j
j
i
P
n=1
(xi − wij )2
3: Bestimme für jedes Ausgabeneuron j den Grad der Nachbarschaft λ(j)
zum Siegerneuron während der Epoche p:
λ(j) = f (rnorm (hj − hj 0 ), d(p))
4: Passe die Gewichtsvektoren der betreffenden Neuronen um ∆wj an:
∆wj = (X − Wj ) · λ(j) · α(p)
5: Falls eine vorher festgelegte Abbruchbedingung (z.B. Epochenanzahl)
erfüllt ist, breche das Training ab, ansonsten iteriere die Epochenzahl
p und fahre mit Schritt (2) fort.
Über diesen Algorithmus läßt sich nun eine selbstorganisierende Karte trainieren. Bevor allerdings mit dem Training begonnen werden kann, müssen die
Eingabedaten korrekt aufbereitet und kodiert werden, um diese überhaupt für
die Karte “lesbar” zu machen. Will man der SOM z.B. Tierdaten (siehe Anwendungsbeispiel) präsentieren, so ist klar, dass die Tiermerkmale passend,
d.h. in richtiger Relation zueinander, kodiert werden müssen, da ansonsten
das Training fehlerhaft durchgeführt wird.
Liegen die Eingabedaten bereits vor, muss die richtige Neuronenanzahl bestimmt werden. Die Anzahl der Eingabeneuronen ist offensichtlich gleich der
Dimension der Eingabedaten, aber die Menge der Ausgabeneuronen ist noch
ungeklärt. Hier empfiehlt es sich, durch vorhergehende Tests die passende
Größe des Neuronengitters ausfindig zu machen. Ein den selbstorganisierenden Karten verwandtes neuronales Netz sind die Growing Cell Structures, die
dieses Problem umgehen, indem sie während des Trainings neue Neuronen
bilden bzw. alte Neuronen entfernen können.
Ist die Größe des Netzes bestimmt, muss nun die Gewichtsinitialisierung geklärt werden (Schritt(1) im Lernalgorithmus). Es bieten sich zwei Möglichkeiten an, die Gewichtsvektoren festzulegen: entweder man initialisiert die
Gewichte zufällig klein, oder man setzt die Gewichtsvektoren alle auf einen
festen Wert. Dieser kann laut [Uni04] auch in Abhängigkeit von der Anzahl
der Eingabeneuronen stehen, z.B. √1UI
Letztendlich müssen jetzt noch Nachbarschafts- und Lernratenfunktion
definiert werden. Durch unterschiedliche Kombinationen der Funktionen lassen sich verschiedene Ergebnisse erzielen, wie folgende Abbildungen zeigen.
9
Abbildung 7. 8x8 Kohonenkarte nach zufälliger Initialisierung, 20, 50 und 300 Epochen
Abbildung 8. 8x8 Kohonenkarte nach zufälliger Initialisierung, 50, 100 und 300
Epochen
Abbildung 7 zeigt die Entfaltung einer selbstorganisierenden Karte mit 8x8
Ausgabeneuronen nach zufälliger Gewichtsinitialisierung, und nach jeweils 20,
50 und 300 eingegebenen Epochen. Als Nachbarschaftsfunktion wurde eine
10
Kegelfunktion gewählt. Lernraten- und Distanzfunktion verlaufen jeweils exponentiell. Die Radiusfunktion basiert auf der euklidischen Norm.
Zum Vergleich ist in Abbildung 8 die Karte mit veränderten Trainingsparamtern zu sehen. Diesmal wurde als Nachbarschaftsfunktion die Gauss-Kurve
und als Lernratenfunktion die Ordering-Phase-Funktion gewählt. Es ist deutlich zu erkennen, dass sich Variante 2 zuerst deutlich langsamer entwickelt als
Variante 1. Nach 300 Epochen hat sich die Gauss-Variante jedoch vollkommen entfaltet, wohingegen bei Variante 1 noch leichte topologische Defekte
erkennbar sind.
4
Anwendungsbeispiel: das Rundreiseproblem
Beim Rundreiseproblem geht es darum, die kürzeste Reiseroute zwischen gegebenen Orten zu bestimmen. Der Berechnungsaufwand steigt mit der Anzahl
der Orte exponentiell an. Versucht man dieses Problem mit Hilfe einer selbstorganisierenden Karte zu lösen, wird man feststellen, dass die Lösung zwar
keine 100%-ige Lösung darstellt, aber in Relation zum Berechnungsaufwand
sehr positiv zu bewerten ist.
Jedem Ort wird eine Koordinate zugewiesen, welche an die Eingabeschicht
angelegt wird. Es werden also zwei Eingabeneuronen benötigt, die diese an
die Kartenschicht weiterleiten. Die daraus entstehenden Gewichtsvektoren der
Ausgabeneuronen sind zweidimensional und können ebenfalls als Koordinaten
betrachtet werden. Jedes Neuron spiegelt also einen Ort wieder. Die Gewichtsinitialisierung wird so gewählt, dass die Neuronen bei einer Visualisierung der
Karte einen Kreis mit möglichst kleinem Radius bilden, da dies den Optimalfall für die Anordnung der Orte darstellt.
Abbildung 9. Gewichtsinitalisierung beim Rundreiseproblem
Legt man nun die Orts-Koordinaten an die Eingabeschicht an, so passen sich
die Verbindungsgewichte der Neuronen immer mehr an diese an. Nach mehreren Iterationen verringert sich der Abstand zwischen den Orten und den
zugehörigen Siegerneuronen immer mehr bis letztendlich Orts- und Gewichtskoordinaten nahezu identisch sind. Vor Trainingsbeginn müssen die Neuronen
noch durchnumeriert werden, so dass nach Ende des Lernvorgangs nur noch
der Numerierung gefolgt werden muss, um die Reiseroute zu erhalten.
11
Abbildung 10. Karte nach 1900 Iterationen
Laut [Läm01] ließ sich eine Rundreise durch 150 Orte mit 750 Kartenneuronen innerhalb weniger Sekunden in 1900 Schritten berechnen. Abbildung 10
zeigt das Ergebnis dieser Eingaben.
Selbstorganisierende Karten lassen sich jedoch nicht nur für das Rundreiseproblem benutzen. Sie finden auch Anwendung in der Robotik, z.B. für die
Steuerung eines Roboterarms in der Industrie, dessen Position mit Hilfe zweier
Kameras erfaßt und an eine Kohonenkarte übergeben wird. Auch eine Klassifizierung von Daten ist mit einer SOM möglich.
Abbildung 11 soll die Topologieerhaltung der selbstorganisierenden Karten
verdeutlichen. An die Eingabeschicht einer SOM wurden kodierte Tiermerkmale angelegt und an die Stelle des Siegerneurons das jeweilige Tier gesetzt.
Das Ergebnis ist gut zu erkennen: verwandte Tierarten wurden auch in der
Karte benachbart angeordnet.
Abbildung 11. Karte nach Eingabe von Tiermerkmalen
12
Literatur
[Uni04] Technische Anwendungen von Selbstorganisierenden Karten, Universität
Passau; http://lrs2.fmi.uni-passau.de/online/SOM/index.html
[Läm01] Uwe Lämmel, Jürgen Cleve: Lehr- und Übungsbuch Künstliche Intelligenz,
Fachbuchverlag Leipzig, 2001, ISBN: 3-446-21421-6
[Roj93] Raul Rojas: Theorie der neuronalen Netze - Eine systematische Einführung,
Springer-Lehrbuch, 1993, ISBN: 3-540-56353-9
[Neg01] Michael Negnevitsky: Artificial Intelligence: A Guide to Intelligent Systems,
Addison Wesley, Band 1, 2001, ISBN: 0-201-71159-1
13