#

KNN unleashed #2

Im ersten Teil wurde gezeigt, dass ein einfaches MLP als eine lineare Regression betrachtet werden kann. Im folgenden werden die Funktionen, welche durch MLP dargestellt werden können, genauer betrachtet.

Das einfache MLP aus Teil 1 hatte zwei Eingänge, einen Eingang mit einem fixen Wert und ein zweites, an dem der x-Wert angelegt wurde. Das Netz bestand aus zwei explizit erwähnten Komponenten: den Kantengewichten an jeder Verbindung und den Knoten.
Im folgenden seien die Knoten KNN typisch als Neuronen bezeichnet, die Werte der Kanten als Kantengewichte bzw. nur Gewichte.

Angenommen, wir erweitern unser MLP aus dem ersten Beispiel um ein weiteres Eingabeneuron und der entsprechenden Kante zum Ausgabeneuron. Im Bild sind die Eingabeneuronen durch 1, X und Y gekennzeichnet. (Das BIAS, welche den konstanten Wert 1 liefert, wird üblicherweise mit einem Rechteck dargestellt.) Das Ausgabeneuron ist mit Z gekennzeichnet. Welche Funktion wird durch dieses MLP nun repräsentiert?
z = f(x, y) = 1*w1Z + x*wxz + y*wyz

Dabei handelt es sich um eine einfache Ebene im dreidimensionalen Raum. Mathematisch gesprochen können wir mit dem bis hier gezeigten Prinzip n-dimensionale Eingabedaten auf eine Ausgabegröße linear abbilden (Rn->R), so wie es beispielsweise in der multiplen linearen Regression (MLR) gemacht wird. Dabei handelt es sich im Prinzip immernoch um die einfache lineare Regression, nur diesmal in höher dimensionalen Räumen.
Damit lässt sich jedoch nicht jede beliebige Funktion approximieren. Um dies zu verdeutlichen nun einige Beispiele.

Angenommen, wir möchten die AND Funktion durch ein MLP lernen lassen. Die dazugehörige Wertetabelle sieht dann wie rechts aus.
X Y X AND Y
0 0 0
0 1 0
1 0 0
1 1 1

Weiterhin verändern wir unser Ausgabeneuron derart, dass die Ausgabe nicht mehr lediglich die Summe der eingehenden Werte ist, sondern führen mit der Summe die Vorzeichenfunktion aus. Die Vorzeichenfunktion (Signumfunktion f(x) = sgn(x)) definieren wir derart, dass Werte größer 0 als +1 und Werte kleiner oder gleich 0 als 0 interpretiert werden. Damit beschränkt sich die Ausgabe des MLP auf die Werte 0 und 1. Nach dem trainieren des MLP erhalten wir eine Funktion, welche die Eingaben auf 0 oder 1 abbildet und damit eine Art Klassifizierung durchführt.

Im letzten Teil wurde auf die Repräsentation einer Geraden durch ein MLP eingegangen. Die AND Funktion kann also mit einer Geraden, repräsentiert durch ein einfaches MLP, gelernt werden. Ein sehr schönes Applet, mit dem man sich die Separierungsgerade eines solchen MLP anschauen kann, findet man übrigens hier.
Wo ist nun das Problem?

Das Resultat ist im Bild rechts zu sehen:
Eine korrekte Klassifizierung findet mit der Hilfe einer Geraden (gestrichelte Line) statt, welche diejenigen Eingabewerte, die als Ausgabe eine 0 haben von denen, welche als Ausgabe die 1 haben, trennt.
Betrachten wir hierzu eine weitere Funktion, die XOR (exklusives Oder) Funktion, welche nur dann 1 liefert, wenn genau eines der beiden Eingaben 1 ist.
X Y X XOR Y
0 0 0
0 1 1
1 0 1
1 1 0
Möchte man nun diese korrekt grafisch klassifizieren, so benötigt man bereits zwei Geraden, denn die beiden Eingaben, welche als Ausgabe die 0 haben, liegen in entgegengesetzten Ecken.

Dies kann jedoch durch das einfache MLP, welches nur eine Gerade zur Verfügung hat, nicht repräsentiert werden. Die Eigenschaft einer Klassifizierung, sich durch lediglich eine Gerade (oder im n-dimensionalen Falle durch eine Ebene, bzw. Hyperebene) bewerkstelligen zu lassen, wird lineare Separierbarkeit genannt. Entsprechend ist die XOR Funktion nicht linear separabel bzw. separierbar.
Wie sieht nun eine Lösung aus?
Diejenigen, welche sich mit Schaltkreisen oder logischen Funktionen, zu denen das XOR gehört, auskennen, wissen sicherlich, dass man die XOR Funktion auch durch andere logische Operationen ausdrücken kann, gemäß der folgenden Äuivalenz:
x XOR y = (x NAND (x NAND y)) NAND (y NAND (x NAND y))
Wobei NAND für die Negierung der AND Funktion steht. Für die Nicht-Experten der logischen Arithmetik sei das etwas einfacher ausgedrückt: die XOR Funktion lässt sich als Verschachtelung mehrerer AND Funktionen darstellen. Damit kann man das nicht linear separierbare Problem auf mehrere linear separierbare Probleme herunter brechen.
Dem aufmerksamen Leser ist sicherlich an dieser Stelle bereits ein Licht aufgegangen: Die XOR Funktion kann durch die Kombination mehrerer einfacher MLP dargestellt werden, welche die AND Funktion beherrschen.

Hierzu sei die obere Äquivalenz nochmal als AST dargestellt, um die Reihenfolge der Verschachtelungen zu verdeutlichen. Die Rechtecke zeigen fünf (nicht) AND Funktionen an, die verschachtelt wurden.
Nach diesem Prinzip läßt sich nun ein großes MLP aus mehreren kleinen MLP zusammenbauen.
Doch soviele Eingabeneuronen sind gar nicht notwendig. Im Gegensatz zu einem AST ist ein MLP kein binärer Baum. Das zusammengefasste MLP sieht weit ordentlicher aus.

Aber die Äquivalenz, die hier benutzt wurde ist darauf ausgelegt, lediglich AND Bausteine zu benutzen. Daher ist sie nicht die einfachste Art. Sie sollte lediglich verdeutlichen, wie komplexere Funktionen durch komplexere Netze dargestellt werden können. Die einfachste Variante das XOR Problem zu lösen ist die Kombination von AND und OR Funktionen. Die OR Funktion ist, wie die AND Funktion, linear separabel und daher durch ein einfaches Netz repräsentierbar. Eine einfachere Äquivalenzgleichung für XOR, welche auch die OR Funktion benutzt lautet .

Das Netz, das sich daraus ergibt, ist weitaus kleiner. Es besteht aus zwei AND und einem OR Teilnetz.

Zum Schluss dieses Teiles sollen noch ein paar Begriffe aus dem Gebiet der MLR eingeführt werden, welche sich aus diesem Teil ergeben, denn beim Zusammensetzen mehrerer kleiner Netze ist nun ein größeres Netz entstanden.

Die Neuronen eines MLP werden üblicherweise in Schichten angeordnet. Die Eingabeneuronen gehören dabei zur Eingabeschicht, die Ausgabeneuronen zur Ausgabeschicht. Alle Neuronen zwischen Eingabe- und Ausgabeschichten liegen in verborgenen Schichten.

Die Bezeichnung der verborgenen Schichten kann man sich besonders gut einprägen, wenn man sich das MLP als ein Programm vorstellt, was nach objektorientierten Aspekten geschrieben wurde. Als Schnittstelle nach Aussen besitzt das MLP eine Eingabe- und eine Ausgabeschicht. Die verborgenen Schichten sind daher gekapselt. Die Bildung von Schichten hat verschiedene Gründe. Wenn man beispielsweise ein Netz auswertet, so werden die Berechnungen der Werte schichtweise von der Eingabeschicht durch die verborgenen Schichten zur Ausgabeschicht durchgeführt. Sie verleihen diesem Typus von KNN auch ihren Namen: multi layer perceptron. Übrigens habe ich etwas unterschlagen. Das einfache Netz aus Teil 1 ist nämlich gar kein MLP. Es besitzt nur eine Eingabe- und eine Ausgabeschicht und wird daher nicht als multi layer perceptron bezeichnet, sondern nur als Perceptron. MLP besitzen nämlich stets mindestens eine verborgene Schicht.

Tags:, , , , ,

One Response to “KNN unleashed #2” »»

  1. Comment by secco | 10:29 01.06.06|X

    Weitere Folgen dieser Reihe wird es voraussichlich nur auf Anfrage geben. Ich habe nämlich nicht genug positives Feedback zu diesem Teil bekommen. SchlieÃlich will ich ja wissen, ob das irgend jemanden interessiert, oder ob ich mir hier vergebliche Mühen mache.

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.