Aika: Ein semantisches neuronales Netzwerk

Wenn es darum geht Informationen aus natürlichsprachigen Texten zu extrahieren, stehen einem verschiedene Möglichkeiten zur Verfügung. Eine der ältesten und wohl auch am häufigsten genutzten Möglichkeiten ist die der regulären Ausdrücke. Hier werden exakte Muster definiert und in einem Textstring gematcht. Probleme bereiten diese allerdings, wenn kompliziertere semantische Muster gefunden werden sollen oder wenn verschiedene Muster aufeinander aufbauen oder miteinander interagieren sollen. Gerade das ist aber der Normalfall bei der Verarbeitung von natürlichem Text. Muster hängen voneinander ab, verstärken oder unterdrücken sich gegenseitig.
Prädestiniert um solche Beziehungen abzubilden wären eigentlich künstliche neuronale Netze. Diese haben nur das große Manko, dass sie keine strukturierten Informationen verarbeiten können. Neuronale Netze bringen von sich aus keine Möglichkeit mit, die relationalen Beziehungen zwischen Worten oder Phrasen zu verarbeiten. Ein weiteres Problem neuronaler Netze ist die Verarbeitung von Feedback-Schleifen, bei denen einzelne Neuronen von sich selbst abhängig sind. Genau diese Probleme versucht der Aika Algorithmus (www.aika-software.org) zu lösen.

Der Aika Algorithmus ist als Open Source Java-Bibliothek implementiert und dient dazu semantische Informationen in Texten zu erkennen und zu verarbeiten. Da semantische Informationen sehr häufig mehrdeutig sind, erzeugt die Bibliothek für jede dieser Bedeutungen eine eigene Interpretation und wählt zum Schluss die am höchsten gewichtete aus. Aika kombiniert dazu aktuelle Ideen und Konzepte aus den Bereichen des maschinellen Lernens und der künstlichen Intelligenz, wie etwa künstliche neuronale Netze, Frequent Pattern Mining und die auf formaler Logik basierenden Expertensysteme. Aika basiert auf der heute gängigen Architektur eines künstlichen neuronalen Netzwerks (KNN) und nutzt diese, um sprachliche Regeln und semantische Beziehungen abzubilden.

Die Knackpunkte: relationale Struktur und zyklische Abhängigkeiten

Das erste Problem: Texte haben eine von Grund auf relationale Struktur. Die einzelnen Worte stehen über ihre Reihenfolge in einer ganz bestimmten Beziehung zueinander. Gängige Methoden, um Texte für die Eingabe in ein KNN auszuflachen, sind beispielsweise Bag-of-Words oder Sliding-Window. Mittlerweile haben sich auch rekurrente neuronale Netze etabliert, die das gesamte Netz in einer Schleife für jedes Wort des Textes mehrfach hintereinander schalten. Aika geht hier allerdings einen anderen Weg. Aika propagiert die relationalen Informationen, also den Textbereich und die Wortposition, gemeinsam mit den Aktivierungen durch das Netzwerk. Die gesamte relationale Struktur des Textes bleibt also erhalten und lässt sich jederzeit zur weiteren Verarbeitung nutzen.

Das zweite Problem ist, dass bei der Verarbeitung von Text häufig nicht klar ist, in welcher Reihenfolge einzelne Informationen verarbeitet werden müssen. Wenn wir beispielsweise den Namen „August Schneider“ betrachten, können sowohl der Vor- als auch der Nachname in einem anderen Zusammenhang eine völlig andere Bedeutung annehmen. August könnte sich auch auf den Monat beziehen. Und genauso könnte Schneider eben auch den Beruf des Schneiders meinen. Einfache Regeln, um hier dennoch den Vor- und den Nachnamen zu erkennen, wären: „Wenn das nachfolgende Wort ein Nachname ist, handelt es sich bei August um einen Vornamen“ und „Wenn das vorherige Wort ein Vorname ist, dann handelt es sich bei Schneider um einen Nachnamen“. Das Problem dabei ist nur, dass unsere Regeln nun eine zyklische Abhängigkeit beinhalten. Aber ist das wirklich so schlimm? Aika erlaubt es, genau solche Feedback-Schleifen abzubilden. Wobei die Schleifen sowohl positive, als auch negative Gewichte haben können. Negative rekurrente Synapsen führen dazu, dass zwei sich gegenseitig ausschließende Interpretationen entstehen. Der Trick ist nun zunächst nur Annahmen zu treffen, also etwa dass es sich bei dem Wort „Schneider“ um den Beruf handelt und zu schauen wie das Netzwerk auf diese Annahme reagiert. Es bedarf also einer Evaluationsfunktion und einer Suche, die die Annahmen immer weiter variiert, bis schließlich eine optimale Interpretation des Textes gefunden ist. Genau wie schon der Textbereich und die Wortposition werden nun auch die Annahmen gemeinsam mit den Aktivierungen durch das Netzwerk propagiert.

Die zwei Ebenen des Aika Algorithmus

Aber wie lassen sich diese Informationen mit den Aktivierungen durch das Netzwerk propagieren, wo doch der Aktivierungswert eines Neurons für gewöhnlich nur eine Fließkommazahl ist? Genau hier liegt der Grund, weshalb Aika unter der neuronalen Ebene mit ihren Neuronen und kontinuierlich gewichteten Synapsen noch eine diskrete Ebene besitzt, in der es eine Darstellung aller Neuronen in boolscher Logik gibt. Aika verwendet als Aktivierungsfunktion die obere Hälfte der Tanh-Funktion. Alle negativen Werte werden auf 0 gesetzt und führen zu keiner Aktivierung des Neurons. Es gibt also einen klaren Schwellenwert, der zwischen aktiven und inaktiven Neuronen unterscheidet. Anhand dieses Schwellenwertes lassen sich die Gewichte der einzelnen Synapsen in boolsche Logik übersetzen und entlang der Gatter dieser Logik kann nun ein Aktivierungsobjekt mit den Informationen durch das Netzwerk propagiert werden. So verbindet Aika seine diskrete bzw. symbolische Ebene mit seiner subsymbolischen Ebene aus kontinuierlichen Synapsen-Gewichten.

Die Logik Ebene in Aika erlaubt außerdem einen enormen Effizienzgewinn im Vergleich zu einem herkömmlichen KNN, da die gewichtete Summe von Neuronen nur noch für solche Neuronen berechnet werden muss, die vorher durch die Logikebene aktiviert wurden. Im Falle eines UND-verknüpfenden Neurons bedeutet das, dass das Aktivierungsobjekt zunächst mehrere Ebenen einer Lattice-Datenstruktur aus UND-Knoten durchlaufen muss, bevor das eigentliche Neuron berechnet und aktiviert werden kann. Diese Lattice-Datenstruktur stammt aus dem Bereich des Frequent Pattern Mining und enthält in einem gerichteten azyklischen Graphen alle Teilmuster eines beliebigen größeren Musters. Ein solches Frequent Pattern Lattice kann in zwei Richtungen betrieben werden. Zum Einen können damit bereits bekannte Muster gematcht werden, und zum Anderen können auch völlig neue Muster damit erzeugt werden.

Da es schwierig ist Netze mit Millionen von Neuronen im Speicher zu halten, nutzt Aika das Provider Architekturpattern um selten verwendete Neuronen oder Logikknoten in einen externen Datenspeicher (z.B. eine Mongo DB) auszulagern, und bei Bedarf nachzuladen.

Ein Beispielneuron

Hier soll nun noch beispielhaft gezeigt werden wie ein Neuron innerhalb des semantischen Netzes angelegt werden kann. Zu beachten ist, dass Neuronen sowohl UND- als auch ODER-Verknüpfungen abbilden können. Das Verhalten hängt dabei alleine vom gewählten Bias ab. Liegt der Bias bei 0.0 oder einem nur schwach negativen Wert reicht schon die Aktivierung eines positiven Inputs aus um auch das aktuelle Neuron zu aktivieren. Es handelt sich dann um eine ODER-Verknüpfung. Liegt der Bias hingegen tiefer im negativen Bereich dann müssen mitunter mehrere positive Inputs gleichzeitig aktiviert werden damit das aktuelle Neuron dann auch aktiv wird. Jetzt handelt es sich dann um eine UND-Verknüpfung. Der Bias Wert kann der initNeuron einfach als Parameter übergeben werden. Um jedoch die Berechnung des Bias zu erleichtern bietet Aika bei den Inputs noch den Parameter BiasDelta an. Der Parameter BiasDelta nimmt einen Wert zwischen 0.0 und 1.0 entgegen. Bei 0.0 wirkt sich der Parameter gar nicht aus. Bei einem höheren Wert hingegen wird er mit dem Betrag des Synapsengewichts multipliziert und von dem Bias abgezogen. Der Gesamtbias lautet in diesem Beispiel also -55.0. Die beiden positiven Eingabesynapsen müssen also aktiviert werden und die negative Eingabesynapse darf nicht aktiviert werden, damit dieses Neuron selber aktiv werden kann. Das Zusammenspiel von Bias und Synpasengewichten ist aber nicht nur für die Aktivierung eines Neurons wichtig, sondern auch für die spätere Auswahl der finalen Interpretation. Je stärker die Aktivierungen innerhalb einer Interpretation aktiv sind, desto höher wird diese Interpretation gewichtet.
Um eine beliebige Graphstruktur abbilden zu können, trennt Aika das Anlegen der Neuronen von der Verknüpfung mit anderen Neuronen. Mit createNeuron(“E-Schneider (Nachname)”) wird also zunächst einmal ein unverknüpftes Neuron erzeugt, das dann über die initNeuron Funktion mit den Eingabeneuronen wortSchneiderNeuron, kategorieVornameNeuron und unterdrueckendesNeuron verknüpft wird. Über den Parameter RelativeRid wird hier angegeben auf welche relative Wortposition sich die Eingabesynapse bezieht. Die Eingabesynpase zu der Kategorie Vorname bezieht sich also mit -1 auf die vorherige Wortposition. Der Parameter Recurrent gibt an ob es sich bei dieser Synpase um eine Feedback-Schleife handelt. Über den Parameter RangeMatch wird angegeben wie sich der Textbereich, also die Start- und die Endposition zwischen der Eingabe- und der Ausgabeaktivierung verhält. Bei EQUALS sollen die Bereiche also genau übereinstimmen, bei CONTAINED_IN reicht es hingegen wenn der Bereich der Eingabeaktivierung innerhalb des Bereichs der Ausgabeaktivierung liegt. Dann kann noch über den Parameter RangeOutput angegeben werden, dass der Bereich der Eingabeaktivierung an die Ausgabeaktivierung weiterpropagiert werden soll.

    Neuron entitaetSchneiderNachnameNeuron = m.initNeuron(
            m.createNeuron("E-Schneider (Nachname)"),
            5.0,
            new Input()
                    .setNeuron(wortSchneiderNeuron)
                    .setWeight(10.0f)
                    .setBiasDelta(1.0)
                    .setRelativeRid(0)
                    .setRecurrent(false)
                    .setRangeMatch(EQUALS)
                    .setRangeOutput(true),
            new Input()
                    .setNeuron(kategorieVornameNeuron)
                    .setWeight(10.0f)
                    .setBiasDelta(1.0)
                    .setRelativeRid(-1)
                    .setRecurrent(true)
                    .setRangeMatch(NONE),
            new Input()
                    .setNeuron(unterdrueckendesNeuron)
                    .setWeight(-40.0f)
                    .setBiasDelta(1.0)
                    .setRecurrent(true)
                    .setRangeMatch(CONTAINED_IN)
    );

Fazit

Mit Aika können sehr flexibel umfangreiche semantische Modelle erzeugt und verarbeitet werden. Aus Begriffslisten verschiedener Kategorien, wie etwa: Vor- und Nachnamen, Orten, Berufen, Strassen, grammatikalischen Worttypen usw. können automatisch Neuronen generiert werden. Diese können dann dazu genutzt werden, Worte und Phrasen zu erkennen, einzelnen Begriffen eine Bedeutung zuzuordnen oder die Kategorie eines Begriffs zu bestimmen. Falls in dem zu verarbeitenden Text mehrdeutige Begriffe oder Phrasen auftauchen, kann Aika für diese jeweils eigene Interpretationen erzeugen und gewichten. Die sinnvollste Interpretation wird dann als Ergebnis zurück geliefert.

Neuronale Netzwerke zur Spam-Erkennung

Die Funktionsweise der in immer mehr Anwendungen genutzten neuronalen Netzwerke stieß bei weniger technik-affinen Menschen bislang nur auf wenig Interesse. Geschuldet wird das sicher vor allem der eher trockenen Theorie, die hinter diesen Konstrukten steht und die sich für die meisten nicht auf Anhieb erschließt. Ein populäres Beispiel für die Fähigkeiten, die ein solches neuronales Netzwerk bereits heute hat, lieferte in jüngster Zeit Googles “Inception”, welches ohne den Anspruch auf einen praktischen Nutzen eigenständig eine spektakuläre Bilderwelt kreierte, die auch Menschen ohne großes Interesse an den dahinter steckenden Technologien ins Staunen versetzte. Ansonsten bieten sich die neuronalen Netze vor allem überall dort an, wo wenig systematisches Wissen zur Verfügung steht, wie etwa bei der Bilderkennung und der Text- bzw. Sprachanalyse.

Weniger effektheischend, als die Ergebnisse von “Inception”, dafür jedoch überaus hilfreich für den vernetzten Alltag, sind neuronale Netzwerke, die zum Aufspüren und zur Kategorisierung von Spam-Seiten entwickelt werden. In diesem Anwendungsbereich können diese ein wertvolles Werkzeug sein.

Wie bei allen selbstlernenden Netzwerken muss dafür zunächst ein Grundgerüst aufgebaut werden, welches später von Hand mit Informationen gefüttert wird, bis es schließlich in der Lage ist, sich selbstständig weiter zu entwickeln, hinzuzulernen und auf diese Weise immer genauere Ergebnisse liefert.

Die Auswahl der Kriterien

Unerwünschte Webseiten mit störenden und oft illegalen Inhalten findet man im Internet zu Hauf und meist locken sie mit dubiosen Angeboten für vermeintliche Wundermittel oder gaukeln leichtgläubigen Nutzern vor, man könne ohne großes Zutun viel Geld verdienen – meist ohne ein tatsächliches Produkt oder eine Dienstleistung dahinter. Ein entsprechend programmiertes neuronales Netzwerk spürt diese Seiten anhand von bestimmten Faktoren automatisch auf. Als Trainingsdaten werden dafür zunächst von Hand Kriterien wie die Registrierungs-IP, der Nutzername und die verwendete Sprachversion eingegeben. Da das Netzwerk nur mit den Zahlen 0 und 1 arbeiten kann, müssen diese Datensätze zuvor manuell aufbereitet werden. Indem alle gewünschten Registrierungs-IPs erst auf den jeweiligen Internetdienstanbieter abgebildet werden und der Grad ihrer jeweiligen Spammigkeit von Hand bestimmt wird, lässt sich der jeweilige Durchschnitt der “Spammigkeit” eines Internetdienstanbieters berechnen. Teilt man die Anzahl der Spammer durch die Gesamtnutzerzahl eines einzelnen Anbieters, erhält man bereits ein Ergebnis, das sich zur Eingabe in das neuronale Netzwerk eignet. Ähnlich kann z. B. bei der Kombination aus Geolocation und Sprachversion verfahren werden. Mit einer Vielzahl weiterer Faktoren kann die Effizienz des neuronalen Netzwerks verbessert werden. So lassen sich etwa große Unterschiede bei dem Herkunftsland feststellen, in dem die Spam-Seiten angesiedelt sind. Ein besonders großes Erkennungspotential bieten bestimmte Keywords und Keyword-Kombinationen, die mitunter eindeutige Rückschlüsse auf ein Spam-Angebot ziehen lassen. Befindet sich z. B. die Wortkombination “Geld verdienen” besonders häufig auf einer Seite, ist dies ein recht deutliches Kriterium für die Klassifizierung als Spam. Doch auch weniger offensichtliche Faktoren helfen dem neuronalen Netzwerk dabei, hellhörig zu werden: Ein ungewöhnliches Verhältnis zwischen Vokalen und Konsonanten oder auch Seitennamen, die vermehrt Zahlen und unübliche Zeichen beinhalten, können die Spam-Wahrscheinlichkeit steigern. Kommt die verwendete IP-Adresse aus einem anonymisierten Netzwerk oder VPN, schürt dies ebenfalls den Verdacht auf unseriöse Inhalte.

Erstellung einer Korrelationsmatrix

Da jedes der einbezogenen Kriterien zur Bestimmung der Spammigkeit einer Seite eine unterschiedlich hohe Relevanz hat, müssen die einzelnen Faktoren verschieden stark gewichtet werden. Damit das neuronale Netzwerk genau das tun kann, wird deshalb eine Korrelationsmatrix erstellt. In dieser Matrix werden alle gesammelten Kriterien in Verbindung zueinander gesetzt, um es dem Netzwerk zu ermöglichen, nicht jeden Punkt nur einzeln zu werten. So ist ein Keyword wie z. B. “100 mg” an sich vergleichsweise unverdächtig. Stammt die Seite, auf der das Wort vorkommt jedoch aus einer Gegend, in der erfahrungsgemäß viele unseriöse Arzneimittelanbieter angesiedelt sind, kann dies die Spam-Wahrscheinlichkeit erhöhen.

Libraries für die Implementierung

Ein wertvolles Tool, das sich für die Implementierung des jeweiligen neuronalen Netzwerks eignet, ist die Open Source Machine Learning Library “Tensor Flow” von Google. Diese Programmierschnittstelle der zweiten Generation verfügt über einige handfeste Vorteile gegenüber anderen Libraries und ermöglicht die Parallelisierung der Arbeit. Berechnet wird sie auf der schnellen GPU des Rechners, was in direkten Vergleichen die Rechenzeit um ein Vielfaches senken konnte. Bewährt hat sich “Tensor Flow” bereits in zahlreichen kommerziellen Diensten von Google, darunter Spracherkennungssoftware, Google Photos, und Gmail.

Für eine bessere Abstraktion des Netzwerks, können zusätzlich zu der hinteren mehrere weitere Schichten angelegt werden. Die hintere Schicht bleibt dabei oft die einzige, die von außerhalb sichtbar ist.

Die Optimierung des neuronalen Netzwerks

Es liegt in der Natur der Sache, dass ein eigenständig lernfähiges Netzwerk nicht von Anfang an durch höchste Zuverlässigkeit hinsichtlich seiner Trefferquote besticht. Zum Lernen gehört Erfahrung und die muss das Netz erst noch sammeln. Zwar gelingt es auch einem noch frisch programmierten Netzwerk bereits die Erfüllung seiner Aufgabe oft recht gut, die Fehlerquote kann jedoch im Laufe der Zeit immer weiter verbessert werden. Gerade am Anfang werden noch viele Spam-Seiten nicht erkannt und einige vermeintliche Spammer stellen sich bei der Überprüfung durch den Menschen als unbedenklich heraus. Darum ist es für die Steigerung der Effizienz praktisch unerlässlich, immer wieder von Hand einzugreifen, falsche Ergebnisse zu korrigieren und dem Netzwerk auf diese Weise zu helfen.

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.

 %--------------------- Daten -----------------------
 X = [0 0;       			% Eingangsdaten
      0 1;
      1 0;
      1 1] 
     
 Y = [0;1;1;0] 				% erwartete XOR Ausgangsdaten

 theta1 = normrnd(0, 1/(3*2), 3, 2); % 3x2 Gewichtsmatrix
 theta2 = normrnd(0, 1/(3*1), 3, 1); % 3x1 Gewichtsmatrix

 m = length(X)				% Anzahl der Eingangsdaten
 
 
 iteration = 10000			% Anzahl der Trainingsiterationen
 alpha = 0.8					% lernrate 

 printf("nnStarte Training ... ")
 for(i = 1:iteration) 
 
   %--------------------- Vorwärtspass -----------------------
   V = X;					% anlegen der Eingangsdaten an die Eingangsschicht

   % 1. berechne die Aktivierungen der verborgenen Schicht
   Vb = [ones(m,1) V];		% hinzufügen der Bias Units  (sind immer 1)
   Zv = Vb * theta1;			% Summe aus den Eingangswerten multipliziert mit deren Gewichten
   H = 1 ./ (1 .+ e.^-Zv);	% anwenden der Sigmoid Funktion auf die Aktivierungsstärke Zv

   % 2. berechne die Aktivierungen der Ausgangsschicht
   Hb = [ones(m,1) H];		% hinzufügen der Bias Units an die verborgene Schicht
   Zh = Hb * theta2;			% Produkt aus den Aktivierungen der Neuronen in H und Theta2
   O = 1 ./ (1 .+ e.^-Zh);	% Vorhersage von dem Netzwerk

   % 3. berechne die Vorhersageungenauigkeit
   loss = (O .- Y) .^ 2; 	% quadratischer Fehler von der Vorhersage und der Zielvorgabe Y
   mse = sum(loss) / m;		% durchschnittlicher quadratischer Fehler aller Vorhersagen
   
   %--------------------- Rückwärtspass -----------------------
   
   % 1. Ableitung der Fehlerfunktion
   d = O .- Y;					% Differenzmatrix zwischen der Vorhersage und der Zielvorgabe Y

   % 2. berechne die Änderungen für Theta2 und die Ableitung der Ausgangsschicht
   OMO = ones(size(O)) .- O;		% Zwischenvariable: 1-Minus-Vorhersage
   Zhd = d .* O .* OMO;			% Ableitung der Sigmoid Funktion
   theta2c = Hb' * Zhd;			% Änderunswunsch für Theta2
   Hd = Zhd * theta2';			% Ableitung von der Ausgangsschicht
   Hd(:,[1]) = [];				% Ableitung von der Bias Unit

   % 3. berechne die Änderungen für Theta1 und die Ableitung der verborgenen Schicht
   HMO = ones(size(H)) .- H;		% Zweischenvariable: 1 Minus Aktivierung der verborgenen Schicht
   Zvd = Hd .* H .* HMO;			% Ableitung der Sigmoid Funktion von der Aktivierungsstärke Zv
   theta1c = Vb' * Zvd;			% Änderunswunsch für Theta1
   								% weitere Ableitungen sind nicht notwendig

  theta1 -= theta1c .* alpha;	% ändere die Gewichte von Theta1 und Theta2
  theta2 -= theta2c .* alpha;	% der Änderungswunsch wird von der Lernrate abgeschwächt 
 
 endfor
 
 % Ausgabe von der letzten Vorhersage und den Gewichten 
 printf("abgeschlossen. n")
 printf("Letzte Vorhersage und trainierte Gewichten")
 O
 theta1
 theta2

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:

X =                                                                                                                                                                                                                                                                                                                                                                                                               
   0   0                                                                                                                                                                                                          
   0   1                                                                                                                                                                                                          
   1   0                                                                                                                                                                                                          
   1   1                                                                                                                                                                                                          
                                                                                                                                                                                                                  
Y =                                                                                                                                                                                                                                                                                                                                                                                                                   
   0                                                                                                                                                                                                              
   1                                                                                                                                                                                                              
   1                                                                                                                                                                                                              
   0                                                                                                                                                                                                              
                                                                                                                                                                                                                  
theta1 =                                                                                                                                                                                                                                                                                                                                                                                                         
   0.114950   0.046125                                                                                                                                                                                            
   0.064683   0.139159                                                                                                                                                                                            
  -0.164288  -0.094688                                                                                                                                                                                            
                                                                                                                                                                                                                  
theta2 =                                                                                                                                                                                                                                                                                                                                                                                                         
   0.33607                                                                                                                                                                                                        
  -0.31128                                                                                                                                                                                                        
   0.13993                                                                                                                                                                                                        
                                                                                                                                                                                                                  
m =  4                                                                                                                                                                                                            
iteration =  10000                                                                                                                                                                                                
alpha =  0.80000                                                                                                                                                                                                  
                                                                                                                                                                                                                  
                                                                                                                                                                                                                  
Starte Training ... abgeschlossen.     
                                                                                                                                                                           
Letzte Vorhersage und trainierte Gewichte                                                                                                                                                                                    
O =                                                                                                                                                                                                                                                                                                                                                                                                                  
   0.014644                                                                                                                                                                                                       
   0.983308                                                                                                                                                                                                       
   0.986137                                                                                                                                                                                                       
   0.013060                                                                                                                                                                                                       
                                                                                                                                                                                                                  
theta1 =                                                                                                                                                                                                                                                                                                                                                                                                        
   3.2162  -3.0431                                                                                                                                                                                                
   6.4365   5.6498                                                                                                                                                                                                
  -6.3383  -5.8602                                                                                                                                                                                                
                                                                                                                                                                                                                  
theta2 =                                                                                                                                                                                                                                                                                                                                                                                                        
   4.4759                                                                                                                                                                                                         
  -9.5057                                                                                                                                                                                                         
   9.9795    

 

Wie lernen Maschinen?

Im dritten Teil meiner Reihe Wie lernen Maschinen? wollen wir die bisher kennengelernten Methoden anhand eines der bekanntesten Verfahren des Maschinellen Lernens – der Linearen Regression – einmal gegenüberstellen. Die Lineare Regression dient uns hier als Prototyp eines Verfahrens aus dem Gebiet der Regression, in weiteren Artikeln werden die Logistische Regression als Prototyp eines Verfahrens aus dem Gebiet der Klassifikation und eine Collaborative-Filtering- bzw. Matrix-Faktorisierungs-Methode als Prototyp eines Recommender-Systems behandelt.

Read more

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

 %--------------------- Daten -----------------------
 X = [0 0;       		% Eingangsdaten
      0 1;
      1 0;
      1 1] 
     
 Y = [0;1;1;0] 			% erwartete XOR Ausgangsdaten


 theta1 = [2.7, 3.1; 	% antrainierte Gewichte der ersten Schicht
           5.6,  -6;
          -5.4, 6.2]
         
 theta2 = [9.6;			% antrainierte Gewichte der zweiten Schicht
          -6.6;
          -6.5]

 m = length(X)			% Anzahl der Eingangsdaten


 %--------------------- Vorwärtspass -----------------------
 V = X					% anlegen der Eingangsdaten an die Eingangsschicht

 % 1. berechne die Aktivierungen der verborgenen Schicht
 V = [ones(m,1) V]		% hinzufügen der Bias Units  (sind immer 1)
 Zv = V * theta1			% Summe aus den Eingangswerten multipliziert mit deren Gewichten
 H = 1 ./ (1 .+ e.^-Zv)	% anwenden der Sigmoid Funktion auf die Aktivierungsstärke Zv

 % 2. berechne die Aktivierungen der Ausgangsschicht
 H = [ones(m,1) H]		% hinzufügen der Bias Units an die verborgene Schicht
 Zh = H * theta2			% Produkt aus den Aktivierungen der Neuronen in H und Theta2
 O = 1 ./ (1 .+ e.^-Zh)	% Vorhersage von dem Netzwerk

 % 3. berechne die Vorhersageungenauigkeit
 loss = (O .- Y) .^ 2 	% quadratischer Fehler von der Vorhersage und der Zielvorgabe Y
 mse = sum(loss) / m		% durchschnittlicher quadratischer Fehler aller Vorhersagen

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:

H1 = [ones(m,1) H1]			% hinzufügen der Bias Units an die verborgene Schicht
Zh1 = H1 * theta2			% Produkt aus den Aktivierungen der Neuronen in H1 und Theta2
H2 = 1 ./ (1 .+ e.^-Zh1)		% Aktivierungswahrscheinlichkeiten für die nächste verborgene Schicht

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: 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.

 

KNN: Was sind künstliche neuronale Netze?

Ein künstliches neuronales Netzwerk (KNN) besteht aus vielen miteinander verbundenen künstlichen Neuronen. Die einzelnen Neuronen haben unterschiedliche Aufgaben und sind innerhalb von Schichten (layer) angeordnet. Sogenannte Netzwerk Topologien geben vor, wie viele Neuronen sich auf einer Schicht befinden und welche Neuronen miteinander vernetzt sind. Neuronale Netze werden im Bereich der künstlichen Intelligenz eingesetzt und sind ein Ansatz im Machine Learning, haben hier jedoch besondere Vor- und Nachteile.

Es gibt drei Schicht- und vier grundlegende Neuronen-Arten. Bei den Schichten wird unterschieden zwischen Eingabe-, Ausgabe- und verborgener Schicht (Visible, Output & Hidden Layer). Alle eingehenden Daten werden an den Eingabe-Neuronen (Visible Unit) in der Eingabeschicht angelegt. Diese wiederum geben die Daten weiter an die verbundenen Ausgabe- oder verborgenen Neuronen (Output, Hidden Unit). Zusätzlich kann in jeder Schicht noch ein Bias Neuron (Bias Unit) zum Einsatz kommen. Read more