Posts

KNN: Rückwärtspass

Im letzten Artikel der Serie haben wir gesehen wie bereits trainierte Netzwerke verwendet werden können. Als Training wird der Prozess bezeichnet der die Gewichte in einen Netzwerk so anpasst, dass bei einem Vorwärtspass durch ein Netzwerk zu einen festgelegten Eingangsdatensatz ein bestimmtes Ergebnis in der Ausgangsschicht ausgegeben wird. Im Umkehrschluss heißt das auch, dass wenn etwas anderes ausgeliefert wurde als erwartet, das Netzwerk entweder noch nicht gut genug oder aber auf ein anderes Problem hin trainiert wurde.

Training

Das Training selbst findet in drei Schritten statt. Zunächst werden die Gewichte initialisiert. Üblicherweise geschieht das mit zufälligen Werten, die aus einer Normalverteilung gezogen werden. Je nachdem wie viele Gewichte eine Schicht hat, ist es sinnvoll die Verteilung über den Sigma Term zu skalieren. Als Daumenregeln kann dabei eins durch die Anzahl der Gewichte in einer Schicht verwendet werden.

Im zweiten Schritt wird der Vorwärtspass für die Trainingsdaten errechnet. Das Ergebnis wird beim ersten Durchlauf alles andere als zufrieden stellend sein, es dient aber dem Rückwärtspass als Basis für dessen Berechnungen und Gewichtsänderungen. Außerdem kann der Fehler zwischen der aktuellen Vorhersage und dem gewünschten Ergebnis ermittelt werden, um zu entscheiden, ob weiter trainiert werden soll.

Der eigentliche Rückwärtspass errechnet aus der Differenz der Vorwärtspassdaten und der Zieldaten die Steigung für jedes Gewicht aus, in dessen Richtung dieses geändert werden muss, damit das Netzwerk bessere Vorhersagen trifft. Das klingt zunächst recht abstrakt, die genauere Mathematik dahinter werde ich in einem eigenen Artikel erläutern. Zur besseren Vorstellung betrachten wir die folgende Abbildung.

    visuelle Darstellung aller Gewichtskombinationen und deren Vorhersagefehler

Das Diagramm zeigt in blau zu allen möglichen Gewichtskombinationen eines bestimmten, uns unbekannten, Netzwerks und Problems den entsprechenden Vorhersagefehler. Die Anzahl der Kombinationen hängt von der Anzahl der Gewichte und der Auflösung des Wertebereiches für diese ab. Theoretisch ist die Menge also unendlich, weshalb die blaue Kurve eine von mir ausgedachte Darstellung aller Kombinationen ist. Der erste Vorwärtspass liefert uns eine Vorhersage die eine normalisierte Differenz von 0.6 zu unserem eigentlichen Wunschergebnis aufweist. Visualisiert ist das Ganze mit einer schwarzen Raute. Der Rückwärtspass berechnet aus der Differenz und den Daten vom Vorwärtspass einen Änderungswunsch für jedes Gewicht aus. Da die Änderungen unabhängig von den anderen Gewichten ermittelt wurden, ist nicht bekannt was passieren würde wenn alle Gewichte sich auf einmal ändern würden. Aus diesem Grund werden die Änderungswünsche mit einer Lernrate abgeschwächt. Im Endeffekt ändert sich jedes Gewicht ein wenig in die Richtung, die es für richtig erachtet. In der Hoffnung einer Steigerung entlang zu einem lokalen Minimum zu folgen, werden die letzten beiden Schritte (Vor- und Rückwärtspass) mehrfach wiederholt. In dem obigen Diagramm würde die schwarze Raute der roten Steigung folgen und sich bei jeder Iteration langsam auf das linke lokale Minimum hinzubewegen.

 

Anwendungsbeispiel und Programmcode

Um den ganzen Trainingsprozess im Einsatz zu sehen, verwenden wir das Beispiel aus dem Artikel “KNN: Vorwärtspass”. Die verwendeten Daten kommen aus der Wahrheitstabelle eines X-OR Logikgatters und werden in ein 2-schichtiges Feedforward Netzwerk gespeist.

XOR Wahrheitstabelle

X1 X2 Y = X1 ⊻ X2
0 0 0
0 1 1
1 0 1
1 1 0

Der Programmcode ist in Octave geschrieben und kann zu Testzwecken auf der Webseite von Tutorialpoint ausgeführt werden. Die erste Hälfte von dem Algorithmus kennen wir bereits, der Vollständigkeit halber poste ich ihn noch einmal, zusammen mit den Rückwärtspass. Hinzugekommen sind außerdem ein paar Konsolenausgaben, eine Lernrate- und eine Iterations-Variable die angibt wie viele Trainingswiederholungen durchlaufen werden sollen.

Zu jeder Zeile bzw. Funktion die wir im Vorwärtspass geschrieben haben, gibt es im Rückwärtspass eine abgeleitete Variante. Dank den Ableitungen können wir die Änderungswünsche der Gewichte in jeder Schicht ausrechnen und am Ende einer Trainingsiteration anwenden. Wir trainieren 10.000 Iterationen lang und verwenden eine Lernrate von 0,8. In komplexeren Fragestellungen, mit mehr Daten, würden diese Werte niedriger ausfallen.

Es ist außerdem möglich den ganzen Programmcode viel modularer aufzubauen. Dazu werde ich im nächsten Artikel auf eine mehr objekt-orientiertere Sprache wechseln. Nichts desto trotz liefert der obige Algorithmus gute Ergebnisse. Hier ist mal ein Ausgabebeispiel:

 

KNN: Vorwärtspass

Wenn die Gewichte eines künstlichen neuronalen Netzwerkes trainiert sind, kann es verwendet werden, um Vorhersagen über eine am Eingang angelegte Beobachtung zu treffen. Hierzu werden Schicht für Schicht, in einem sogenannten Vorwärtspass (Forward-Pass), die Aktivierungen der einzelnen Neuronen ermittelt, bis ein Ergebnis an der Ausgabeschicht anliegt. Der ganze Prozess hat zwar einen eigenen Namen (Vorwärtspass), ist aber im Endeffekt nur ein iteratives durchführen von mehreren logistischen Regressionen und entspricht dem Vorgehen aus dem Artikel „KNN: künstliche Neuronen“.

Anwendungsbeispiel

Im folgenden Beispiel verwenden wir die Wahrheitstabelle von einem X-OR Logikgatter (siehe Abbildungen unten links) als Ground Truth Data. Ziel ist es, den Ausgangwert Y, für einen beliebig anliegenden Eingangsvektor [X1, X2] vorherzusagen. Die Aufgabe ist recht komplex, so dass eine einfache lineare oder logistische Regression keine zufriedenstellende Lösung finden wird. Die zum Einsatz kommende  Netzwerkstruktur ist ein 2-schichtiges Feedforward Netzwerk mit zwei Eingangsneuronen, einer verborgenen Schicht und einem Ausgangsneuron.

XOR Wahrheitstabelle

X1 X2 Y = X1 ⊻ X2
0 0 0
0 1 1
1 0 1
1 1 0

 

Da das Netzwerk wie anfänglich erwähnt, bereits trainiert ist, gebe ich die Gewichte (Theta) vor. Werden die Werte als Matrix dargestellt, können mit Hilfe der linearen Algebra die Aktivierungswahrscheinlichkeiten aller Neuronen einer Schicht auf einmal ausgerechnet werden.

Theta 1

θ11 =  2,7 θ12 =   3,1
θ13 =  5,6 θ14 = -6
θ15 = -5,4 θ16 =  6,2
Theta 2

θ21 =  9,6
θ22 = -6,6
θ23 = -6,5

Programmcode

Für die eigentlichen Berechnungen verwenden wir die Programmiersprache Octave oder MATLAB. Octave ist eine kostenlose alternative zu MATLAB. Wobei es nicht notwendig ist irgendetwas zu installieren, da es auch eine Online Variante von MATLAB/Octave gibt:
http://www.tutorialspoint.com/execute_matlab_online.php

Ein paar Sätze zu den verwendeten Befehlen. Der Punkt vor manchen Operationen gibt an, dass die Operation Elementweise durchzuführen ist (wichtig bei der Sigmoid Funktion). Die Methode ones(M,N) erzeugt eine MxN große Matrix gefüllt mit den Werten 1. Wir erzeugen damit einen Spaltenvektor der unseren Bias Units entspricht und den wir anschließend an eine vorhandene Matrix horizontal anfügen.

Wird das Programm ausgeführt schreibt es unter anderem die Werte von der Ausgabeschicht O (Output Layer) auf die Konsole. Da wir alle XOR Variationen auf einmal ausgerechnet haben, erhalten wir auch vier Vorhersagen. Verglichen mit der Zielvorgaben Y sind die Werte von O sehr vielversprechend (ähnlich).

X1 X2 Y O
0 0 0 0.057099
0 1 1 0.936134
1 0 1 0.934786
1 1 0 0.050952

 

Komplexe Netzwerke

Hätte das Netzwerk noch weitere verborgene Schichten, müssen Teile des Programmcodes wiederholt ausgeführt werden. Grundsätzlich sind drei Befehle pro Schicht notwendig:

Im nächsten Artikel schauen wir uns das Training solcher Netzwerke an.

Text-Mining mit dem Aika Algorithmus

In diesem Beitrag möchte ich das Open Source Projekt Aika vorstellen. Ziel des Projektes ist es einen Text-Mining Algorithmus zu entwickeln, der ein künstliches Neuronales Netz (kNN) mit einem Pattern Mining Algorithmus kombiniert. Dabei dient die Silbentrennung von Wörtern als initiale Aufgabe, anhand derer der Algorithmus weiterentwickelt wird. Für diese Aufgabe soll allerdings kein vordefiniertes Wörterbuch verwendet werden. Stattdessen sollen die Silben in ihrer Eigenschaft als häufig auftretende Muster in rohem Text erkannt werden. Hier reicht es allerdings nicht einen Mining Algorithmus nach häufig auftretenden Strings suchen zu lassen, da sich viele der Strings überlappen oder schlicht keinen Sinn ergeben würden. Es ist also wichtig, dass sich die erkannten Silben gegenseitig unterdrücken können und dass der Algorithmus in der Lage ist, die so entstehenden unterschiedlichen Interpretationen eines Wortes miteinander zu vergleichen und die am höchsten gewichtete auszuwählen. Beispielsweise taucht die Silbe ‘der’ zu Beginn des Wortes ‘de-re-gu-lie-ren’ auf. In diesem Fall muss der Algorithmus erkennen, dass die erste Silbe des Wortes nicht ‘der’ sondern nur ‘de’ ist.

Wenn nun nach häufig auftretenden Mustern in Text gesucht werden soll, warum verwenden wir nicht einen reinen Pattern Mining Algorithmus? Der Grund für die Kombination mit einem kNN liegt darin, dass die erkannten Muster innerhalb einer kNN Topologie aufeinander aufsetzen können. Wenn z. B. das Wort “hausboot” als Muster erkannt werden soll, dann entstünden in der Datenstruktur des Mining Algorithmus sehr viele Teilmuster, die alle evaluiert werden müssten. Viel leichter wäre es für den Algorithmus, wenn die Muster “haus” und “boot” bereits erkannt worden wären und nun als Eingaben für die Erkennung des Wortes “hausboot” dienen könnten. So ist der Algorithmus zum einen in der Lage komplexere Muster zu erkennen und muss gleichzeitig weniger Teilmuster untersuchen. Ausserdem erlaubt es ein kNN ‘weiche’ Muster zu erlernen, also Muster bei denen einzelne Eingänge optional sind, die aber trotzdem noch sicher erkannt werden. Dadurch kann eine höhere Toleranz gegenüber Fehlern erreicht werden.

Im Gegensatz zu einem klassischen kNN nutzt Aika einen eher mit Googles Pagerank vergleichbaren Ansatz um Gewichte zwischen den einzelnen Neuronen des Netzwerks zu propagieren. Der Grutext-pattern-knnndgedanke dabei ist es, dass Neuronen entsprechend höher gewichtet werden sollten, wenn sie mit anderen hoch gewichteten Neuronen in Beziehung stehen. Wenn also beispielsweise eine Silbe in vielen hoch gewichteten Worten auftaucht, wird sie selbst entsprechend höher gewichtet.

Neuronen eines kNN erlauben es aber nicht nur Konjunktionen wie etwa bei Mustern zu erlernen, sondern auch Disjunktionen. Disjunktionen sind insbesondere beim Erlernen von Grammatikregeln wichtig, wenn z. B. einzelne Worte als Nomen erkannt werden sollen. Wenn nun solche Disjunktionen erlernt werden sollen, können auch hier häufige Muster behilflich sein. Angenommen, es wurden durch den Mining Algorithmus bereits die folgenden häufigen Muster gefunden: “der Baum” (f=4), “der Hammer” (f=3) und “der Nagel” (f=6). Dann können diese Muster so umgeformt werden, dass ein neues, deutlich häufigeres Muster “der <NOMEN>” (f=13) und eine Disjunktion <NOMEN> = “Baum” oder “Hammer” oder “Nagel”, entsteht.

KNN: Natur als Vorbild – Biologische Neuronen

Bisher ist die genaue Funktionsweise des Gehirns bei der Verarbeitung sensorischer Informationen nicht bekannt. Neue Erkenntnisse im Bereich der Neurowissenschaften liefern jedoch einen Einblick über grundlegende Prinzipien wie das Gehirn von Säugetieren sensorische Informationen repräsentiert. Einer der wichtigsten Punkte ist dabei die Erkenntnis, dass der Neocortex, einem ankommenden Signal erlaubt ein komplexes Netzwerk von Neuronen zu durchlaufen, wodurch es zu einer abstrakten Repräsentation des ursprünglichen Eingabesignals kommt. Auch ist das Gehirn in der Lage die Leitfähigkeit der Verbindungen zwischen den Neuronen zu modifizieren, was sich auf eine Änderung der Abbildungsvorschrift auswirkt. Beobachtungen können dadurch noch besser getrennt und effizienter repräsentiert werden. Die Entdeckung dieses Verhaltens motivierte die Entstehung des Forschungszweiges Deep Machine Learning, welcher sich darauf fokussiert Modelle zu entwickeln, die ähnliche Charakteristiken wie der Neocortex aufweisen.

Das Eingabesignal durchläuft das Netzwerk bis zu einer Ausgabeschicht. Das Resultat dieser nicht linearen Transformation lässt sich dann beispielsweise mit einem Klassifizierungsalgorithmus auswerten. Die praktischen Anwendungen solcher Algorithmen sind sehr vielfältig. Deep Machine Learning Algorithmen liefern zurzeit die besten Ergebnisse zu vielen Problemen in Anwendungsdomänen wie Bilderkennung, Spracherkennung und der Verarbeitung natürlicher Sprache. Mit Hilfe dieser Algorithmen wurden beispielsweise neue elementare Teilchen gefunden, entdeckte Galaxien noch besser klassifiziert und Auswirkungen von Mutationen innerhalb von DNA vorhergesagt.

Das Neuron

Das Neuron ist die Basis-Recheneinheit des Gehirns. Ungefähr 86 Milliarden solcher Neuronen befinden sich im menschlichen Nervensystem, welche durch ca. 10^15 Synapsen miteinander vermascht sind. In Abbildung unten links wird eine Schemazeichnung eines biologischen Neurons dargestellt. Dieses besteht unter Anderem aus Dendriten, dem Zellkörper, der den Zellkern beinhaltet und einem Axon. Die Dendriten gehen aus dem Zellkörper hervor und sind über Synapsen mit sensorischen Zellen oder Axonen anderer Neuronen verbunden. Ihre Aufgabe ist die Aufnahme von ankommenden Signalen in Form von elektrischen Spannungsänderungen und der Transport dieser in den Zellkörper des Neurons, der Recheneinheit einer Nervenzelle. Dort angekommen entscheiden bestimmte Faktoren, ob ein Aktionspotential anhand einer Schwellwertfunktion ausgelöst wird oder nicht. Ist dies der Fall leitet das Neuron elektrische Energie über sein Axon an weitere angeschlossene Dendriten anderer Neuronen weiter.

Neuronen
Das biologische Neuron diente als Inspiration für das Software-Neuron. Beim mathematischen Modell eines Software-Neurons (Künstliches Neuron eines KNN) wird davon ausgegangen, dass die verschiedenen Dendriten unterschiedlich stark ausgeprägt sind und ein Signal daher auch verschieden stark gewichtet in den Zellkörper übertragen wird. Jedes Dendrit enthält demnach einen Faktor(θi), der das Signal(xi) vor dem Eintreffen in den Zellkörper skaliert (θixi). Diese Faktoren werden auch als Gewichte bezeichnet. Im Zellkörper selbst werden die Signale die von unterschiedlichen Neuronen stammen aufsummiert bis schließlich ein fester Bias-Wert(b) auf das Ergebnis der Summation aufaddiert wird. Anschließend bestimmt eine nicht-lineare Aktivierungsfunktion über den finalen Ausgangswert des Neurons.

Bildquelle: Wikipedia

Ähnliche Artikel:

KNN: Künstliche Neuronen

Es gibt sehr ausführliche Definitionen und Abbildungen für ein künstliches Neuron, die in diesem Artikel aber nicht behandelt werden. Der Grund dafür ist pragmatischer Natur. Es soll eine gewisse Konsistenz zu den anderen KNN-Beiträgen dieser Reihe bestehen und das Thema soll nicht zu einer wissenschaftlichen Abhandlung mutieren.

In dem Beitrag  KNN: Was sind künstliche neuronale Netze  geht es um den grundsätzlichen Aufbau von künstlichen neuronalen Netzwerken. Zusammengesetzt werden die Strukturen aus einer oftmals großen Anzahl von künstlichen Neuronen. Die nachfolgende Abbildung zeigt auf der Linken Seite einen extrahierten Ausschnitt aus einem Netzwerk. Es kann auch als einfaches allein stehendes Netzwerk betrachtet werden. Auf der rechten Seite ist eine allgemeingültigere Form zu sehen. Die Bias Unit (VB) wird üblicherweise als X0 bezeichnet und hat immer den Wert 1.

 

neuronen-netzwerk1 neuronen-netzwerk2

 


Um den Ausgangswert Y zu berechnen wird zunächst jeder Eingangswert X mit seinem dazugehörigen Gewicht \theta (Theta) multipliziert und die Ergebnisse aufsummiert. Das Zwischenergebnis ist die Aktivierungsstärke z:

    \[ z = X_0 \cdot \theta_0 + X_1 \cdot \theta_1 + X_2 \cdot \theta_2 \]

Im nächsten Schritt wird der eigentliche Ausgangswert Y errechnet, indem die Aktivierungsstärke z an eine Aktivierungsfunktion angelegt wird. Es gibt zwar verschiedene Funktionen, häufig wird aber die Logistische bzw. Sigmoid-Funktion verwendet. Sie ist nicht-linear und hat einen Ausgangswertebereich zwischen 0 und 1.

sigmoid-funktion

    \[ sigmoid(z) = \frac{1}{1+e^{-z}} \]

Wird das Bias Neuron und sein Gewicht nicht beachtet, bestimmen die eingehenden Daten die Aktivierungsstärke und damit den Ausgang der Funktion. Unter Verwendung der Bias Unit verschiebt sich die Funktion entlang der Y-Achse, was einer Verschiebung von einem Schwellwert gleich kommt.

Die endgültige Formel für die Aktivierung eines Neurons sieht sehr ähnlich zu der Logistischen Regression aus. Werden die Werte von X und Theta zu Vektoren zusammengefasst, lässt sich die Berechnung stark vereinfachen:

    \[ Y = sigmoid(X\theta) \]

Als Programmcode müsste diese Berechnung dennoch mit einer Schleife realisiert werden oder noch besser mit einer Bibliothek für lineare Algebra.

Ähnliche Artikel:
KNN: Was sind künstliche neuronale Netze
KNN: Vorteile und Nachteile

KNN: Vorteile und Nacheile

Wie jedes Verfahren haben auch künstliche Neuronale Netzwerke (KNN) ihre Vor- und Nachteile. Im Folgenden sollen einige benannt werden.

Vorteile

  • KNN können bessere Ergebnisse liefern als existierende statistische Ansätze, wenn das Problem ausreichend komplex ist. Das heißt, wenn das Problem nicht linear ist und es viele Eingabedaten mit vielen Variablen gibt.
  • Es gibt zwar sogenannte Hyperparameter, die je nach Einstellung das Netzwerk besser oder schlechter trainieren lassen, diese müssen aber nur manuell geändert werden, wenn neue Rekordwerte erreicht werden sollen. Ansonsten gibt es verhältnismäßig wenige Parameter.
  • Auch für stark nicht lineare Probleme, werden gute Lösungen gefunden. Dazu zählen fast alle Probleme die aus einer Datenbasis stammen, wo menschliche oder andere unvorhersehbare Einflüsse wirken.
  • Für große Datenmengen und viele Datendimensionen (Einflussfaktoren) können sinnvolle Ergebnisse ermittelt werden.

Nachteile

  • Künstliche Neuronale Netzwerke sind oftmals wie eine Blackbox. Dadurch ist es nicht möglich nachzuverfolgen wieso ein Netzwerk eine bestimmte Entscheidung getroffen hat.
  • Damit ein allgemeingültiges gutes Ergebnis berechnet werden kann, bedarf es vieler Beispiel-/Trainingsdaten.
  • Aufgrund der hohen Datenmenge, ist es sinnvoll die Berechnungen auf einer Grafikkarte durchzuführen.
  • Während des Trainings finden sehr viele Gewichtsänderungen in kurzer Zeit statt. Daher ist ein Aufteilen der Arbeit in ein verteiltes System wie Apache Hadoop oder Apache Spark nur schwer möglich und führt oftmals zu drastischen Performanz Einbußen.
  • Ist das Problem mathematisch beschreibbar sind KNNs oftmals schlechter oder maximal genauso gut.
  • Es ist zu keinen Zeitpunkt bekannt ob die gefundene Lösung das globale Optimum ist oder ob es noch bessere Lösungen gibt.

In der Forschung gibt es viele Ansätze um einige der Nachteile aufzuheben.