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 11 Literatur 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 Gegen- satz zum Perzeptron ohne Lehrer auskommt, der nach jeder Eingabe die Ausgabe ¨ uberpr¨ uft und ggF. die Verbindungsgewichte anpaßt, um die Ausgabe zu korrigie- ren. Ein weiteres spezifisches Merkmal der SOMs (Selforganizing Map) ist, dass auch die r¨ aumliche Anordnung der Neuronen untereinander eine wichtige Rolle im Lernverfahren spielt. 27. Mai 2004
Transcript
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 11
Literatur 13
Zusammenfassung
Bei Selbstorganisierenden Karten (nach ihrem Entwickler auch Kohonen-Kartenoder Kohonen Feature Maps genannt) handelt es sich um ein spezielles neuronalesNetz, das — wie der Name schon sagt — sich selbst organisiert, also im Gegen-satz zum Perzeptron ohne Lehrer auskommt, der nach jeder Eingabe die Ausgabeuberpruft und ggF. die Verbindungsgewichte anpaßt, um die Ausgabe zu korrigie-ren. Ein weiteres spezifisches Merkmal der SOMs (Selforganizing Map) ist, dassauch die raumliche Anordnung der Neuronen untereinander eine wichtige Rolle imLernverfahren spielt.
27. Mai 2004
1 Das menschliche Gehirn als Vorbild
Eine SOM erstellt aus den Eingaben eine topographische Karte. Je ahnlicherzwei Eingaben sind, desto naher liegen die dadurch aktivierten Neuronen bei-einander. Einander sehr ahnliche Eingabemuster werden von der SOM alsoauch benachbart dargestellt. Vorbild fur diese Topologieerhaltung ist — wieso oft bei neuronalen Netzen — das menschliche Gehirn.
Abbildung 1. Topologieerhaltung im Menschlichen Gehirn
In Abbildung 1 ist auf der linken Seite die somatosensorische Hirnrinde —zustandig fur den Tastsinn — und auf der rechten Seite die motorische Rindezu sehen. Die einzelnen Korperteile sind bei ihrer jeweils zustandigen Hirn-region angeordnet. Es ist gut zu erkennen, dass benachbarte Hirnregionenauch benachbarte bzw. ahnliche Korperteile kontrollieren: z.B. liegt das Arealfur den Tastsinn der Arme direkt neben der Hirnregion fur die Hande. Wiedas menschliche Gehirn Sinneseindrucke wirklich verarbeitet und speichert,ist noch nicht genugend erforscht. Unter anderem ist die selbstorganisieren-de Karte dazu entwickelt worden, mehr Einblick in die Organisationsweiseunseres Gehirns zu geben.
2
2 Architektur einer SOM
2.1 Aufbau der Neuronenschichten
Eine selbstorganisierende Karte besteht aus zwei Schichten. Die Eingabe-schicht (UI) setzt sich aus den Eingabeneuronen, die Ausgabeschicht (UO)— auch Kohonen- oder Kartenschicht genannt — aus den Ausgabe- oderKohonenneuronen zusammen. Die Eingabeschicht ist mit den Neuronen derAusgabeschicht voll vernetzt: jedes Neuron der Eingabeschicht ist mit allenAusgabeneuronen durch Gewichte verbunden. Gewichtete Verbindungen in-nerhalb der Ausgabeschicht gibt es allerdings nicht, jedoch spielt im spaterenLernverfahren die raumliche Anordnung der Kartenneuronen eine wichtigeRolle.
Abbildung 2. Architektur einer SOM
Die Ausgabeschicht kann unterschiedliche Dimensionen annehmen. Am hau-figsten werden zwei-dimensionale quadratische Neuronengitter eingesetzt. Al-lerdings sind auch drei- oder mehr-dimensionale Gitter moglich. Die Positionjedes Kohonenneurons wird dabei durch den Koordinatenvektor angegeben,der bei der Initialisierung der SOM festgelegt und auch im Laufe des Trai-nings nicht mehr verandert wird.
2.2 Gewichts- und Eingabevektor
Jedes Eingabeneuron schickt einen Eingabewert an alle Neuronen der Karten-schicht. Faßt man die einzelnen Eingaben zusammen, ergibt dies das Einga-bemuster bzw. den Eingabevektor:
3
x = (x1, x2, ..., xi), i =Anzahl der Eingabeneuronen
Aus den einzelnen Gewichten, die ein Ausgabeneuron zu jedem Eingabeneu-ron besitzt, kann jedem Kohonenneuron j ein Gewichtsvektor wj zugewiesenwerden:
wj = (w(1,j), w(2,j), ..., w(i,j)), i =Anzahl der Eingabeneuronen
Die Gewichtsvektoren aller Neuronen bestimmen die sog. Netzstruktur einerSOM. Diese kann uber die Gewichtsvektoren visualisiert werden. Fur eineSOM 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 desGewichts des Kartenneurons j zum Eingabeneuron 1 und an der Y-Achse dasGewicht zum Eingabeneuron 2 eingetragen ist. Eine solche Darstellung kannjedoch nur bei zweidimensionalen Eingabedaten verwirklicht werden.
3 Das Training der Karte
3.1 Bestimmung des Siegerneurons
Eine SOM bewertet fur ein Eingabemuster die Ahnlichkeit zu jedem Gewichts-vektor und bestimmt ein sog. Siegerneuron, auch Prototyp genannt. DiesesSiegerneuron reprasentiert die Eingabe von allen Kartenneuronen am besten.Fur die Bewertung der Ahnlichkeit gibt es zwei verschiedene Methoden. Amplausibelsten jedoch ist die minimale Euklidische Distanz zwischen Eingabe-und Gewichtsvektor:
j(X) = arg minj
‖ X − Wj ‖= arg minj
√i∑
n=1(xi − wij)2
4
Wobei j(x) das Siegerneuron des Eingabemusters X, i die Anzahl der Eingabe-neuronen, xi der Eingabewert des i-ten Neurons und wij ein einzelnes Gewichtdes Neurons j zum i-ten Eingabeneuron ist.
Abbildung 4. Minimale Euklidische Distanz
Abbildung 4 zeigt anschaulich die Bestimmung der minimalen EuklidischenDistanz zwischen einem Eingabevektor und einem Gewichtsvektor. Sie istnichts anderes als die Entfernung zweier Vektoren und damit ein Maß furdie Ahnlichkeit dieser.Nun kann es allerdings vorkommen, dass zwei Gewichtsvektoren die gleicheeuklidische Distanz zum Eingabevektor aufweisen. In solchen Fallen wird ent-weder zufallig oder ein beliebiger Vektor aus dieser Gruppe gewahlt und dessenNeuron als Sieger bestimmt.Eine weitere Moglichkeit zur Bestimmung des Siegerneurons ist das maxi-male Skalarprodukt der beiden Vektoren, aber da, wie schon erwahnt, dieeuklidische Distanz am plausibelsten fur die Ahnlichkeit ist, wird diese auchhauptsachlich verwendet.Ist das Siegerneuron bestimmt, wird nach dem Winner-Takes-All-Prinzip dieAusgabe des Siegerneurons auf 1, die aller anderen Kartenneuronen auf 0 ge-setzt.
3.2 Adaption der Gewichtsvektoren
Jetzt beginnt erst das eigentliche Training der Karte. Die Gewichtsvektorendes Siegerneurons und die seiner umliegenden Neuronen werden an den Ein-gabevektor mit Hilfe einer Lernvorschrift angepaßt. Dabei spielt der Grad derNachbarschaft zum Siegerneuron eine große Rolle. Vereinfachend beschrankenwir diese Adaption erst einmal auf das Siegerneuron, da dieses sich selbst amnachsten ist und damit zu 100% lernt:
∆wi,j = α(xi − wi,j)
Dabei ist α die sog. Lernrate, die nach jeder Epoche verkleinert wird, um denLernfortschritt der Karte im Laufe des Trainings zu verringern. Sind alle vor-handenen Eingabemuster der Karte einmal prasentiert worden, beginnt eineneue Epoche, in der wieder alle Muster eingegeben werden. Dies wird solangewiederholt bis die Lernrate auf 0 gesunken oder eine andere Abbruchbedin-gung erfullt ist.Um die anfangs erwahnte Topologieerhaltung, also die benachbarte Anord-
5
nung (Aktivierung des Siegerneurons) ahnlicher Eingabemuster in der Karte,zu gewahrleisten, mussen auch Neuronen in der Nachbarschaft des Siegerneu-rons in den Lernprozess mit einbezogen werden. Dies erfolgt uber die Kombi-nation verschiedener Funktionen.
3.3 Nachbarschafts- und Lernratenfunktion
Eine Nachbarschaftsfunktion berechnet den Grad der Nachbarschaft, welcherzwischen 0 und 1 liegt, eines Ausgabeneurons zum Siegerneuron. Die Nach-barschaftsfunktion ist von den Werten einer Distanz- und Radiusfunktionabhangig. Letztere bestimmt den Abstand der Ausgabeneuronen zum Sie-gerneuron und beruht meist auf der Basis der euklidischen Norm. Zu einemgegebenen Koordinatenvektor h
(D)j des Neurons j, mit der Dimension D, be-
rechnet diese den Abstand zum Ursprung des Koordinatensystems:
reukl(hj) =
√D∑
n=1(h
(n)j )2
Der Abstand zum Siegerneuron mit dem Koordinatenvektor hj′ wird an derStelle hj − hj′ berechnet. Fur das Siegerneuron selbst ist der Wert der Ra-diusfunktion also 0. Diese kann im ubrigen auch auf Basis der Eins- oderMaximumsnorm beruhen:
• reins(hj) =D∑
n=1| h
(n)j |
• rmax(hj) = max{| h(1)j | .... | h
(D)j |}
Da im Laufe des Trainings nach jedem Eingabemuster der Einflussbereichdes Siegerneurons abnehmen soll, wird eine monoton fallende Distanzfunktionbenotigt. Dies ist sinnvoll, da sich die Karte so besser entfalten kann undschneller konvergiert. Mogliche Funktionen sind folgende:
Wobei t die aktuelle, und tend die Epoche, bei der das Training abgebrochenwerden soll, darstellt.
Die Ergebnisse der Radius- und Distanzfunktion werden der Nachbarschafts-funktion als Parameter ubergeben, welche den Grad der Nachbarschaft lie-fert. Dieser bestimmt letztendlich wie stark die Gewichte der Neuronen ange-
6
paßt werden. Auch hier sind verschiedene Arten von Funktionen, wie z.B. dieGauß’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 Nachbar-schaftsgrad 1 — lernen also so wie das Siegerneuron — alle anderen Neuronenerfahren keine Veranderung ihrer Gewichte.Eine weitere Moglichkeit zur Berechnung des Nachbarschaftsgrads liefert dieaus der Wahrscheinlichkeitsrechnung bekannte Gauß’sche Glockenkurve:
• fgauss(r, d) = e−( rd)
Folgende Abbildung zeigt den Nachbarschaftsgrad uber die Gaussfunktion fureine zweidimensionale Ausgabeschicht. Das Siegerneuron liegt hier im Koor-dinatenursprung:
Abbildung 5. Gauß’sche Glockenkurve
Die Mexican-Hat-Funktion ist in Abbildung 6 zu sehen. Sie besitzt einennegativen Wertebereich. Die Gewichte der Neuronen mit einem solchen Nach-barschaftsgrad werden dem Eingabemuster nicht ahnlicher gemacht, sondernnoch mehr verfalscht. Laut [Lam01] hat dies jedoch ein Divergieren der Kartezur Folge, weshalb in der Praxis auf diese Abstoßung der Gewichte verzichtetwird.
7
Abbildung 6. Mexican-Hat-Funktion
Die schon angesprochene Lernratenfunktion verhalt sich ahnlich wie dieDistanzfunktion, weshalb hier nur eine spezielle Funktion angesprochen wer-den soll: die Ordering-Phase-FunktionSei t die aktuelle Epoche, torder eine Epoche, ab der die Lernrate konstantbleibt, und tend die Anzahl der insgesamt zu durchlaufenden Epochen:
α =
c − 0,8ctorder
· c falls t < torder
0, 2 falls torder < t ≤ 0, 8 · t
1 − 1tend
· t falls 0, 8 · tend < t ≤ tend
0 sonst
3.4 Der Lernalgorithmus
Nachdem nun alle notigen Funktionen definiert und erklart wurden, kann nunder Lernalgorithmus formuliert werden. Man unterscheidet bei selbstorga-nisierenden Karten zwischen zwei verschiedenen Lernmethoden, dem muster-weisen und epochenweisen Lernen. Beim musterweisen Lernen erfolgt die Ad-aption der Gewichtsvektoren nach jedem Eingabemuster, das an die Eingabe-schicht angelegt wurde, wohingegen beim epochenweisen Lernen die Gewichts-anpassung erst nach Durchlaufen einer kompletten Epoche, also nach Eingabealler vorhandenen Eingabemuster, vorgenommen wird. Am haufigsten wird
8
jedoch das musterweise Lernen verwendet, weshalb wir uns auf diesen Algo-rithmus beschranken:
Algorithm 1 Musterweises Lernen einer SOM
1: Initialisiere die Verbindungsgewichte wj . Erklarung s.u.2: Bestimme fur jedes Eingabemuster X das Siegerneuron j(X):
j(X) = arg minj
‖ X − Wj ‖= arg minj
√i∑
n=1(xi − wij)2
3: Bestimme fur jedes Ausgabeneuron j den Grad der Nachbarschaft λ(j)zum Siegerneuron wahrend der Epoche p:
λ(j) = f(rnorm(hj − hj′), d(p))4: Passe die Gewichtsvektoren der betreffenden Neuronen um ∆wj an:
erfullt ist, breche das Training ab, ansonsten iteriere die Epochenzahlp und fahre mit Schritt (2) fort.
Uber diesen Algorithmus laßt sich nun eine selbstorganisierende Karte trai-nieren. Bevor allerdings mit dem Training begonnen werden kann, mussen dieEingabedaten korrekt aufbereitet und kodiert werden, um diese uberhaupt furdie Karte “lesbar” zu machen. Will man der SOM z.B. Tierdaten (siehe An-wendungsbeispiel) prasentieren, so ist klar, dass die Tiermerkmale passend,d.h. in richtiger Relation zueinander, kodiert werden mussen, da ansonstendas Training fehlerhaft durchgefuhrt wird.Liegen die Eingabedaten bereits vor, muss die richtige Neuronenanzahl be-stimmt werden. Die Anzahl der Eingabeneuronen ist offensichtlich gleich derDimension der Eingabedaten, aber die Menge der Ausgabeneuronen ist nochungeklart. Hier empfiehlt es sich, durch vorhergehende Tests die passendeGroße des Neuronengitters ausfindig zu machen. Ein den selbstorganisieren-den Karten verwandtes neuronales Netz sind die Growing Cell Structures, diedieses Problem umgehen, indem sie wahrend des Trainings neue Neuronenbilden bzw. alte Neuronen entfernen konnen.Ist die Große des Netzes bestimmt, muss nun die Gewichtsinitialisierung ge-klart werden (Schritt(1) im Lernalgorithmus). Es bieten sich zwei Moglich-keiten an, die Gewichtsvektoren festzulegen: entweder man initialisiert dieGewichte zufallig klein, oder man setzt die Gewichtsvektoren alle auf einenfesten Wert. Dieser kann laut [Uni04] auch in Abhangigkeit von der Anzahlder Eingabeneuronen stehen, z.B. 1√
UI
Letztendlich mussen jetzt noch Nachbarschafts- und Lernratenfunktiondefiniert werden. Durch unterschiedliche Kombinationen der Funktionen las-sen sich verschiedene Ergebnisse erzielen, wie folgende Abbildungen zeigen.
9
Abbildung 7. 8x8 Kohonenkarte nach zufalliger Initialisierung, 20, 50 und 300 Epo-chen
Abbildung 8. 8x8 Kohonenkarte nach zufalliger Initialisierung, 50, 100 und 300Epochen
Abbildung 7 zeigt die Entfaltung einer selbstorganisierenden Karte mit 8x8Ausgabeneuronen nach zufalliger Gewichtsinitialisierung, und nach jeweils 20,50 und 300 eingegebenen Epochen. Als Nachbarschaftsfunktion wurde eine
10
Kegelfunktion gewahlt. Lernraten- und Distanzfunktion verlaufen jeweils ex-ponentiell. Die Radiusfunktion basiert auf der euklidischen Norm.Zum Vergleich ist in Abbildung 8 die Karte mit veranderten Trainingsparam-tern zu sehen. Diesmal wurde als Nachbarschaftsfunktion die Gauss-Kurveund als Lernratenfunktion die Ordering-Phase-Funktion gewahlt. Es ist deut-lich zu erkennen, dass sich Variante 2 zuerst deutlich langsamer entwickelt alsVariante 1. Nach 300 Epochen hat sich die Gauss-Variante jedoch vollkom-men entfaltet, wohingegen bei Variante 1 noch leichte topologische Defekteerkennbar sind.
4 Anwendungsbeispiel: das Rundreiseproblem
Beim Rundreiseproblem geht es darum, die kurzeste Reiseroute zwischen ge-gebenen Orten zu bestimmen. Der Berechnungsaufwand steigt mit der Anzahlder Orte exponentiell an. Versucht man dieses Problem mit Hilfe einer selbst-organisierenden Karte zu losen, wird man feststellen, dass die Losung zwarkeine 100%-ige Losung darstellt, aber in Relation zum Berechnungsaufwandsehr positiv zu bewerten ist.Jedem Ort wird eine Koordinate zugewiesen, welche an die Eingabeschichtangelegt wird. Es werden also zwei Eingabeneuronen benotigt, die diese andie Kartenschicht weiterleiten. Die daraus entstehenden Gewichtsvektoren derAusgabeneuronen sind zweidimensional und konnen ebenfalls als Koordinatenbetrachtet werden. Jedes Neuron spiegelt also einen Ort wieder. Die Gewichts-initialisierung wird so gewahlt, dass die Neuronen bei einer Visualisierung derKarte einen Kreis mit moglichst kleinem Radius bilden, da dies den Optimal-fall fur die Anordnung der Orte darstellt.
Abbildung 9. Gewichtsinitalisierung beim Rundreiseproblem
Legt man nun die Orts-Koordinaten an die Eingabeschicht an, so passen sichdie Verbindungsgewichte der Neuronen immer mehr an diese an. Nach mehr-eren Iterationen verringert sich der Abstand zwischen den Orten und denzugehorigen Siegerneuronen immer mehr bis letztendlich Orts- und Gewichts-koordinaten nahezu identisch sind. Vor Trainingsbeginn mussen die Neuronennoch durchnumeriert werden, so dass nach Ende des Lernvorgangs nur nochder Numerierung gefolgt werden muss, um die Reiseroute zu erhalten.
11
Abbildung 10. Karte nach 1900 Iterationen
Laut [Lam01] ließ sich eine Rundreise durch 150 Orte mit 750 Kartenneuro-nen innerhalb weniger Sekunden in 1900 Schritten berechnen. Abbildung 10zeigt das Ergebnis dieser Eingaben.Selbstorganisierende Karten lassen sich jedoch nicht nur fur das Rundreise-problem benutzen. Sie finden auch Anwendung in der Robotik, z.B. fur dieSteuerung eines Roboterarms in der Industrie, dessen Position mit Hilfe zweierKameras erfaßt und an eine Kohonenkarte ubergeben wird. Auch eine Klassi-fizierung von Daten ist mit einer SOM moglich.Abbildung 11 soll die Topologieerhaltung der selbstorganisierenden Kartenverdeutlichen. An die Eingabeschicht einer SOM wurden kodierte Tiermerk-male angelegt und an die Stelle des Siegerneurons das jeweilige Tier gesetzt.Das Ergebnis ist gut zu erkennen: verwandte Tierarten wurden auch in derKarte benachbart angeordnet.
Abbildung 11. Karte nach Eingabe von Tiermerkmalen
12
Literatur
[Uni04] Technische Anwendungen von Selbstorganisierenden Karten, UniversitatPassau; http://lrs2.fmi.uni-passau.de/online/SOM/index.html
