Im Rahmen eines Projektes, musste ich mich in die Thematik der Kohonenkarten (Self Organizing Maps) einlesen. Ich möchte hier kurz einen Überblick über diesen Algorithmus geben und ein paar Links zusammentragen.
Die Kohonenkarte ist eine Art von neuronalem Netzwerk. Es wurde von Teuvo Kohonen erfunden und ist ein unüberwachtes Lernverfahren. Das bedeutet, dass man vorab nicht wissen muss, wie viele “Kategorien” es gibt. Sprich man trainiert das Netzwerk einfach mit den Daten die man hat und das Netzwerk sorgt für eine Gruppierung.
Die Kohonenkarte besteht aus zwei Schichten, die erste Schicht sind Inputneuronen und die zweite Schicht beschreibt das Netzwerk welches ebenfalls aus Neuronen besteht.
Die Inputneuronen sind dafür da um die Vektoren, mit denen das Netzwerk trainiert werden soll, dem Netzwerk zu präsentieren. Mit anderen Worten, für den Fall, dass man ein Netzwerk mit Farben trainieren möchte, existieren drei Inputneuronen. Je ein Neuron für den R-, G- und B-Wert des Vektors.
Das Netzwerk besteht aus ein vorher festgelegten Anzahl an Neuronen die typischerweise in einem Quadrat angeordnet sind. Es gibt zwar auch wabenartige Strukturen und Strukturen in höheren Dimensionen wie dem Würfel, aber wir nutzen hier ausschliesslich das Quadrat.
Nehmen wir an, dass das Netzwerk aus 16 Neuronen besteht. Ordnen wir diese zu einem Quadrat, erhält man ein Quadrat mit einer Kantenlänge von vier Neuronen.
Jedes dieser 16 Neuronen hat eine bestehende Verbindung zu jedem Inputneuron
Untereinander sind die Neuronen in der Netzwerkschicht nicht verbunden. Programmatisch gesehen muss aber eine Adressierung der einzelnen Neuronen möglich sein. Warum das so ist wird später erwähnt.
Jedes der 16 Neuronen der Netzwerkschicht enthält einen Vektor der in der Länge der Anzahl an Inputneuronen entspricht. Das heisst, das im Falle von drei Inputneuronen jedes der 16 Neuronen im Netzwerk einen Vektor der Größe 3 enthält. Dieser Vektor wird Gewichtsvektor genannt.
Um die späteren Rechnungen zu vereinfachen werden die alle Werte, mit denen das Netzwerk trainiert wird, auf einen Wert zwischen 0 und 1 normalisiert. Praktisch bedeutet das, dass z. B. der Farbwert 255 normalisiert der 1 entspricht und der Farbwert 0 analog dazu 0. Jedes Element des Gewichtsvektors enthält einen Wert zwischen 0 und 1 diese werden zu Beginn zufällig vergeben. Es gibt auch andere Initialisierungsmöglichkeiten wie z.B. Gradient oder alle mit dem selben Wert. Die unterschiedlichen Initialisierungen können zu verschiedenen Ergebnissen führen.
Bevor das Training des Netzwerks beginnen kann, existieren, am Beispiel der RGB Farben, also drei Inputneuronen, sowie 16 Neuronen mit je einem Gewichtsvektor der Größe 3.
Der Trainingsalgorithmus besteht aus insgesamt fünf Schritten:
1. Schritt: Die Gewichtsvektoren werden mit zufälligen Werten zwischen 0 und 1 initialisiert.
2. Schritt: Aus der Menge der Trainingsvektoren, mit denen das Netzwerk trainiert werden soll, wird zufällig einer ausgewählt.
3. Schritt: Dieser ausgewählte Vektor wird nun dem Netzwerk mit Hilfe der Inputneuronen präsentiert und die so genannte Best Matching Unit (BMU) ermittelt. Dieser Vorgang läuft mit einer Hilfe einer Metrik ab. Wir nutzen hier die allseits bekannte euklidische Metrik bzw. den euklidischen Abstand. Die BMU ist nun das Neuron der Netzwerkschicht dessen Gewichtsvektor, anhand der Metrik, den kleinsten Abstand zu dem Datensatz hat, welches dem Netzwerk präsentiert wurde.
Beispiel:
Angenommen wir haben zufällig die Farbe Rot aus der Menge an Trainingsvektoren gewählt (255;0;0) und präsentieren diese Farbe nun den 16 Neuronen des Netzwerkes. Innerhalb des Netzwerkes existiert ein Neuron, dessen Gewichtsvektor zufällig mit den Werten 0,9;0;0 initialisiert wurde. Die Farbe Rot würde normalisiert den Vektor 1;0;0 ergeben. Die Distanz zwischen diesen beiden Neuronen wäre demnach 
4. Schritt: Jetzt beginnt das eigentliche Training des Netzwerks. Ein vorher festgelegter, oder errechneter Wert, stellt den Radius um die BMU dar. Dieser Radius schrumpft mit der Zeit. Der Sinn ist, dass alle Neuronen in der Nachbarschaft der BMU angepasst werden, wofür noch eine Nachbarschaftsfunktion notwendig ist. Jeder Gewichtsvektor eines Neurons in der Nachbarschaft um die BMU, sowie der Gewichtsvektor der BMU selbst werden nun dem Trainingsvektor angeglichen. Dieses Angleichen geschieht auf Basis folgender Gleichung
W(t+1) ist der entstehende angepasste Gewichtsvektor eines Neurons
W(t) ist der aktuelle Gewichtsvektor eines Neurons
N(t) ist die Nachbarschaftsfunktion basierend auf der Zeit t
L(t) ist die Lernrate basierend auf der Zeit t
V(t) ist der Trainingsvektor
Am Beispiel der Farben würde der Gewichtsvektor eines Neuron (die BMU oder ein Neuron in der Nachbarschaft), Index für Index, an den Trainingsvektor angepasst werden.
Die Nachbarschaftsfunktion N(t) hat die Aufgabe, den Einfluss der Nachbarschaft auf das Lernen zu bestimmen. Sie nutzt den über die Zeit t schrumpfenden Radius.
Es gibt viele Arten von Nachbarschaftsfunktionen. Die gebräuchlichste ist die der gaußschen Nachbarschaft
N(t) = exp(-(pow(gridDistance, 2)/(pow(radius, 2))));
eine weitere Variante ist die der zylindrische Nachbarschaft. Diese gibt, solange sich ein Neuron innerhalb der Nachbarschaft befindet, eine 1 zurück und sobald ein Neuron ausserhalb der Nachbarschaft ist eine 0.
Die Funktion beschreibt, dass sich Gewichtsvektoren von Neuronen die näher an der BMU sind stärker anpassen als Gewichtsvektoren von Neuronen die weiter weg sind.
Um den Radius mit der Zeit schrumpfen zu lassen, kann folgende Funktion genutzt werden
radius = defaultRadius*exp(-(iteration/(iterations/ln(defaultRadius)))
Die Funktion L(t), um die Lernrate zu schrumpfen, lässt sich auf verschiedene Weisen formulieren. Hauptsache ist, dass diese auch mit der Zeit schrumpft. Dabei ist wichtig, dass sie nicht zu schnell und nicht zu langsam schrumpft. Möglichkeiten diese formulieren sind
learningrate = defaultLearningrate*exp(-(((double)iteration)/iterations))
learningrate = defaultLearningrate*exp(((double)iteration/(iterations/ln(defaultLearningrate))))
5. Schritt: Wiederhole alle Schritte ab Schritt 2 für n Iterationen.
Mit so einer Kohonenkarte lassen sich nun witzige Sachen anstellen. Am Beispiel der Farben richten sich die Neuronen an den Farben aus, mit denen sie trainiert wird.
Wenn man die Gewichtsvektoren der Neuronen anstatt mit Farben, mit zwei Werten für Koordinaten initialisiert und diese visualisiert kann man mit voranschreitender Iterationen beobachten wie sich die Koordinaten sortieren und sich ein Netz aufspannt.
Mit Hilfe einer Kohonenkarte ist allerdings noch mehr möglich. Mit ihr lässt sich das Traveling Salesman Problem näherungsweise lösen. Dazu wird statt eines Netzwerk aus Neuronen, eine Reihe aus Neuronen erstellt. Jedes Neuron hat je eine Gewichtsvektor der Länge 2 hat und hält x- und y-Koordinaten. Diese Neuronen werden so initialisiert, dass sie einen Kreis ergeben. Die Trainingsvektoren bestehen aus vorher festgelegten Koordinaten von “Städten”. Um das TSP mit der Kohohenkarte lösen zu können, muss zusätzlich die Metrik zur Abstandsbestimmung ein wenig angepasst werden, sodass es den Abstand innerhalb eines Kreises messen kann. Nun wird das Netzwerk nach den oben genannten fünf Schritten immer wieder mit den Städten trainiert. Die Neuronen werden sich nun optimalerweise so anordnen, dass sie alle Städte, ohne Überschneidungen, erreichen.
Dieser Artikel entstand unter Zuhilfenahme von mehreren Seiten. Zudem sei gesagt, dass ich kein Mathematiker bin, falls sich Fehler eingeschlichen haben sollten so bitte ich um Nachsicht. Anbei eine Liste aller Links:
http://www.ai-junkie.com/ann/som/som1.html
http://www.generation5.org/content/2004/aiSomPic.asp
http://fbim.fh-regensburg.de/~saj39122/vhb/NN-Script/script/gen/k02080103020102.html
http://www.f4.htw-berlin.de/~weberwu/diplom/tsp/HTMLS/KOHONEN.HTM
http://fuzzy.cs.uni-magdeburg.de/ci/nn/nn-09-som.pdf