#

KNN unleashed #1

Schon vor geraumer Zeit interessierten sich einige Freunde für das Fach künstliche neuronale Netze (KNN), welches ich während meines Studiums belegte. Die Tatsache, dass die KNN einen wichtigen Beitrag zum Fachgebiet der künstlichen Intelligenz (KI) bei steuerte, sowie dass die KNN auf Modellen des menschlichen Gehirns aufbauen, machte das Thema zu einem Stein der Weisen. Doch sind KNN wesentlich deterministischer als manch einer zuerst glauben mag.

Um dem auf den Grund zu gehen, muss man jedoch zuerst eine Unterscheidung verschiedener Typen von KNN treffen. Die beiden bekanntesten Typen sind die multi layered Perceptrons, kurz MLP, und die Selforganizing Maps, kurz SOM oder auch Kohonen Map genannt.
Zuerst will ich etwas zu den MLPs erzählen, welchen einfachere mathematische Grundprinzipien zugrunde liegen.
MLPs basieren auf einer Regression, deren einfachste Form die (Gaussche) Methode der kleinsten Quadrate ist. Dabei soll eine Gerade gefunden werden, welche zu allen Punkten einer Punktemenge minimalen Abstand hat.

Man kann sich das so vorstellen, als hätte man eine Versuchsreihe (mehrere Punkte) erstellt, die eigentlich auf einer Geraden liegen sollten, aber dies nicht tun, da jede menge Messungenauigkeiten ins Spiel kommen. So liegen die Punkte also zerstreut um die „ideale“ Gerade, welche es zu ermitteln gilt.
Nun beginnt man, etwa mit Augenmaß, oder auch per Zufall, eine Gerade zu bestimmen, die scheinbar in die Punktemenge gut hineinpaßt. Dies kann natürlich nicht das Ende der Fahnenstange sein, also wird nun der Abstand aller Punkte zu den entsprechenden Punkten der Geraden bestimmt.

Denn diese gilt es insgesamt zu minimieren, so dass die Gerade im Idealfall zu allen Punkten einen möglichst geringen Abstand hat. Mit der Minimierung des Abstandes befindet man sich denn auch mitten in einer Regression, bei der es im allgemeinen darum geht, eine Funktion an gegebene Daten anzupassen.

Im Falle der geraden geht es wie folgt weiter: Die Gerade ist durch eine Geradengleichung mit zwei Unbekannten m (Steigung) und b (y-Achsen Schnittpunkt) bestimmt: m*x+b. Durch Augenmaß wurden Werte für m und b festgelegt. Für die Summe der Abweichungen zwischen vorliegenden Daten und den entsprechenden Punkten auf der Geraden wird aber noch das Quadrat der Abstände gebildet. Damit werden zum einen Vorzeichenprobleme gelöst (Punkte unterhalb der Geraden haben einen negativen, oberhalb einen Positiven Wert, der sich leicht aufheben könnte), zum anderen werden die Abstände verschieden gewichtet (größere Abstände werden weiter vergrößert und fallen daher mehr ins Gewicht). Die Summe der quadrierten Abstände hat dann die Form . tp bezeichnet den vorliegenden Wert bei x=p, yp den entsprechenden Punkt auf der Geraden bei x=p.

Der Abstand zwischen den Punkten und der Geraden kann auch grafisch dargestellt werden, in dem man den Abstand für verschiedene Werte von m und b ausrechnet. Die Höhe in diesem dreidimensionalen Graphen gibt auch die Höhe des Abstandes an.

Um nun den Abstand zu minimieren, suchen wir, mit der Sprache der Analysis, ein Minimum. Bekannter maßen führen die Nullstellen der ersten Ableitung einer Funktion zu ihren Extremwerten. Aber auch mit einer numerischen Methode, bei der man lediglich die Parameter m und b Schrittweise ändert und nur diejenigen Änderungen behält, welche zu einer Verkleinerung des Abstandes führten, kann das Minimum bestimmt werden.

In diesem Beispiel existierte lediglich ein Minimum und dieses ist durch ein numerisches Verfahren recht leicht auffindbar. In komplizierteren Fällen können durchaus mehrere Minima existieren, welche berücksichtigt werden müssen.

Wo bleibt nun das KNN? Nun, angenommen, wir haben für das Beispiel oben eine Gerade gefunden, welche minimalen Abstand zu allen Punkten bietet.

Dann hat sie die Form m*x+b. Dies ist auch zugleich das einfachste KNN mit zwei Eingängen und einem Ausgang.

Formal betrachtet beschriebt das rechte KNN eine einfache Gerade. Noch formaler betrachtet beschreiben MLP lediglich eine Funktion, die aus verschiedenen einfachen Bausteinfunktionen aufgebaut werden.
Das obere MLP wird wie folgt evaluiert: An den linken Eingang (die Eingänge befinden sich stets unten) wird konstant der Wert 1 angelegt. Diese besondere Form eines Eingangs wird BIAS genannt. Der zweite Eingang erhält den x Wert, zu dem wir das Passende y suchen. Anschließend wandern die Eingaben durch das Netz (nach oben). An jeder Verbindung (Kante) wird der jeweilige Wert mit einer Zahl, das Kantengewicht, multipliziert. Das Gewicht der linken Kante entspricht dem b, das der rechten dem m. Auf diese Weise wird die 1 des BIAS mit b und das x des anderen Eingangs mit dem m multipliziert und beide Werte gelangen zum Ausgang. Hier werden sie zusammen addiert und am Ausgang somit 1*b+x*m ausgegeben.
Das kleine Netz repräsentiert also nichts anderes als eine Geradengleichung und kann durch numerische Algorithmen einer Datenmenge angepaßt werden.

Mich persönlich erinnert ein solches Netz sehr stark an einen abstrakten Syntaxbaum (AST), den diejenigen, welche schon mal mit Kompilern und Interpretern zu tun hatten, sicherlich kennen.

Aber auch nicht Kompilerentwickler kennen das Prinzip der Priorität beim Rechnen, welches sich als ein Baum ausdrücken läßt. So läßt sich die Rechenaufgabe (x+1)*(3*x+2) anhand der Klammern und der „Punkt vor Strich“ Rechenregel zu einem Baum wie rechts zerlegen. Der Baum wird dann von unten nach oben ausgewertet.

Prinzipiell handelt es sich aber auch um einfache gerichtete und gewichtete Graphen, wie man sie aus der Graphentheorie kennt.

Im nächsten Teil werde ich noch genauer in die Welt der MLP eindringen und auch die parallelen zur Neurobiologie aufzeigen. Auch ein eigener Teil zum Thema SOM ist geplant.

Bilder von einem Kurs über neuronale Netze.

Tags:, , , ,

3 Responses to “KNN unleashed #1” »»

  1. Comment by andrej | 19:37 26.11.05|X

    sehr klare darstellung. weiter so!

  2. Comment by Secco | 13:11 03.12.05|X

    Nun, das KNN im Beispiel ist lediglich eine andere Darstellung der selben Geraden und kann mit den gleichen Methoden regressiert werden. Das KNN ist die Geradengleichung, so wie der AST unten die entsprechende Funktion repräsentiert.

  3. Comment by Toni | 12:18 03.12.05|X

    Wie du von der Geradengleichung mx+b plötzlich auf ein KNN kommst ist mir immernoch Schleierhaft. Der Sprung ist für nichteingeweihte wie mich einfach zu groß um sie durch deine o.g. Andeutung zu verstehen.

Leave a Reply »»

Note: All comments are manually approved to avoid spam. So if your comment doesn't appear immediately, that's ok. Have patience, it can take some days until I have the time to approve my comments.