Posts

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.

Machine Learning mit Python – Minimalbeispiel

Maschinelles Lernen (Machine Learning) ist eine Gebiet der Künstlichen Intelligenz (KI, bzw. AI von Artificial Intelligence) und der größte Innovations- und Technologietreiber dieser Jahre. In allen Trendthemen – wie etwa Industrie 4.0 oder das vernetzte und selbstfahrende Auto – spielt die KI eine übergeordnete Rolle. Beispielsweise werden in Unternehmen viele Prozesse automatisiert und auch Entscheidungen auf operativer Ebene von einer KI getroffen, zum Beispiel in der Disposition (automatisierte Warenbestellungen) oder beim Festsetzen von Verkaufspreisen.

Aufsehen erregte Google mit seiner KI namens AlphaGo, einem Algortihmus, der den Weltmeister im Go-Spiel in vier von fünf Spielen besiegt hatte. Das Spiel Go entstand vor mehr als 2.500 Jahren in China und ist auch heute noch in China und anderen asiatischen Ländern ein alltägliches Gesellschaftsspiel. Es wird teilweise mit dem westlichen Schach verglichen, ist jedoch einfacher und komplexer zugleich (warum? das wird im Google Blog erläutert). Machine Learning kann mit einer Vielzahl von Methoden umgesetzt werden, werden diese Methoden sinnvoll miteinander kombiniert, können durchaus äußerst komplexe KIs erreicht werden.  Der aktuell noch gängigste Anwendungsfall für Machine Learning ist im eCommerce zu finden und den meisten Menschen als die Produktvorschläge von Amazon.com bekannt: Empfehlungsdienste (Recommender System).

Klassifikation via K-Nearest Neighbour Algorithmus

Ein häufiger Zweck des maschinellen Lernens ist, technisch gesehen, die Klassifikation von Daten in Abhängigkeit von anderen Daten. Es gibt mehrere ML-Algorithmen, die eine Klassifikation ermöglichen, die wohl bekannteste Methode ist der k-Nearest-Neighbor-Algorithmus (Deutsch:„k-nächste-Nachbarn”), häufig mit “kNN” abgekürzt. Das von mir interviewte FinTech StartUp Number26 nutzt diese Methodik beispielsweise zur Klassifizierung von Finanztransaktionen.

Um den Algorithmus Schritt für Schritt aufbauen zu können, müssen wir uns

Natürlich gibt es in Python, R und anderen Programmiersprachen bereits fertige Bibliotheken, die kNN bereits anbieten, denen quasi nur Matrizen übergeben werden müssen. Am bekanntesten ist wohl die scikit-learn Bibliothek für Python, die mehrere Nächste-Nachbarn-Modelle umfasst. Mit diesem Minimalbeispiel wollen wir den grundlegenden Algorithmus von Grund auf erlernen. Wir wollen also nicht nur machen, sondern auch verstehen.

Vorab: Verwendete Bibliotheken

Um den nachstehenden Python-Code (Python 3.x, sollte allerdings auch mit Python 2.7 problemlos funktionieren) ausführen zu können, müssen folgende Bibliotheken  eingebunden werden:

import numpy as numpy
import matplotlib.pyplot as pyplot
from mpl_toolkits.mplot3d import Axes3D #Erweiterung für die Matplotlib - siehe: http://matplotlib.org/mpl_toolkits/

Übrigens: Eine Auflistung der wohl wichtigsten Pyhton-Bibliotheken für Datenanalyse und Datenvisualisierung schrieb ich bereits hier.

Schritt 1 – Daten betrachten und Merkmale erkennen

Der erste Schritt ist tatsächlich der aller wichtigste, denn erst wenn der Data Scientist verstanden hat, mit welchen Daten er es zu tun hat, kann er die richtigen Entscheidungen treffen, wie ein Algorithmus richtig abgestimmt werden kann und ob er für diese Daten überhaupt der richtige ist.

In der Realität haben wir es oft mit vielen verteilten Daten zu tun, in diesem Minimalbeispiel haben wir es deutlich einfacher: Der Beispiel-Datensatz enthält Informationen über Immobilien über vier Spalten.

  • Quadratmeter: Größe der nutzbaren Fläche der Immobilie in der Einheit m²
  • Wandhoehe: Höhe zwischen Fußboden und Decke innerhalb der Immobilie in der Einheit m
  • IA_Ratio: Verhältnis zwischen Innen- und Außenflächen (z. B. Balkon, Garten)
  • Kategorie: Enthält eine Klassifizierung der Immobilie als “Haus”, “Wohnung” und “Büro”

 

beispiel-txt-file

[box]Hinweis für Python-Einsteiger: Die Numpy-Matrix ist speziell für Matrizen-Kalkulationen entwickelt. Kopfzeilen oder das Speichern von String-Werten sind für diese Datenstruktur nicht vorgesehen![/box]

def readDataSet(filename):

    fr = open(filename)                 # Datei-Stream vorbereiten

    numberOfLines = len(fr.readlines()) # Anzahl der Zeilen ermitteln

    returnMat = numpy.zeros((numberOfLines-1,3)) # Eine Numpy-Matrix in Höhe der Zeilenanzahl (minus Kopfzeile) und in Breite der drei Merkmal-Spalten

    classLabelVector = [] # Hier werden die tatsächlichen Kategorien (Haus, Wohnung, Büro) vermerkt
    classColorVector = [] # Hier werden die Kategorien über Farben vermerkt (zur späteren Unterscheidung im 3D-Plot!)
    
    #print(returnMat)   # Ggf. mal die noch die ausge-null-te Matrix anzeigen lassen (bei Python 2.7: die Klammern weglassen!)
    
    fr = open(filename) # Datei-Stream öffnen
    index = 0
    
    for line in fr.readlines():  # Zeile für Zeile der Datei lesen
        if index != 0:           # Kopfzeile überspringen
            line = line.strip()
            listFromLine = line.split('\t') # Jede Zeile wird zur temporären Liste (Tabulator als Trennzeichen)

            returnMat[index-1,:] = listFromLine[1:4] #Liste in die entsprechende Zeile der Matrix überführen
            
            classLabel = listFromLine[4]  # Kategorie (Haus, Wohnung, Büro) für diese Zeile merken
            
            if classLabel == "Buero":
                color = 'yellow'
            elif classLabel == "Wohnung":
                color = 'red'
            else:
                color = 'blue'
                        
            classLabelVector.append(classLabel) # Kategorie (Haus, Wohnung, Büro) als Text-Label speichern
            classColorVector.append(color)      # Kategorie als Farbe speichern (Büro = gelb, Wohnung = rot, Haus = Blau)
        
        index += 1


return returnMat,classLabelVector, classColorVector

Aufgerufen wird diese Funktion dann so:

dataSet, classLabelVector, classColorVector = readDataSet("K-Nearst_Neighbour-DataSet.txt")

Die Matrix mit den drei Spalten (Quadratmeter, Wandhohe, IA_Ratio) landen in der Variable “dataSet”.

Schritt 2 – Merkmale im Verhältnis zueinander perspektivisch betrachten

Für diesen Anwendungsfall soll eine Klassifizierung (und gewissermaßen die Vorhersage) erfolgen, zu welcher Immobilien-Kategorie ein einzelner Datensatz gehört. Im Beispieldatensatz befinden sich vier Merkmale: drei Metriken und eine Kategorie (Wohnung, Büro oder Haus). Es stellt sich zunächst die Frage, wie diese Merkmale zueinander stehen. Gute Ideen der Datenvisualisierung helfen hier fast immer weiter. Die gängigsten 2D-Visualisierungen in Python wurden von mir bereits hier zusammengefasst.

[box]Hinweis: In der Praxis sind es selten nur drei Dimensionen, mit denen Machine Learning betrieben wird. Das Feature-Engineering, also die Suche nach den richtigen Features in verteilten Datenquellen, macht einen wesentlichen Teil der Arbeit eines Data Scientists aus – wie auch beispielsweise Chief Data Scientist Klaas Bollhoefer (siehe Interview) bestätigt.[/box]

fig = pyplot.figure()
ax = fig.add_subplot(111)
ax.scatter(dataSet[:,0], dataSet[:,1], marker='o', color=classColorVector)
ax.set_xlabel("Raumflaeche in Quadratmeter")
ax.set_ylabel("Wandhohe")
ax.set_xlim(xmin=0)
ax.set_ylim(ymin=0)
pyplot.show()
fig = pyplot.figure()
ax = fig.add_subplot(111)
ax.scatter(dataSet[:,0], dataSet[:,2], marker='o', color=classColorVector)
ax.set_xlabel("Raumflaeche in Quadratmeter")
ax.set_ylabel("IA_Ratio")
ax.set_xlim(xmin=0)
ax.set_ylim(ymin=0)
pyplot.show()

Die beiden Scatter-Plots zeigen, das Häuser (blau) in allen Dimensionen die größte Varianz haben. Büros (gelb) können größer und höher ausfallen, als Wohnungen (rot), haben dafür jedoch tendenziell ein kleineres IA_Ratio. Könnten die Kategorien (blau, gelb, rot) durch das Verhältnis innerhalb von einem der beiden Dimensionspaaren in dem zwei dimensionalen Raum exakt voneinander abgegrenzt werden, könnten wir hier stoppen und bräuchten auch keinen kNN-Algorithmus mehr. Da wir jedoch einen großen Überschneidungsbereich in beiden Dimensionspaaren haben (und auch Wandfläche zu IA_Ratio sieht nicht besser aus),

Eine 3D-Visualisierung eignet sich besonders gut, einen Überblick über die Verhältnisse zwischen den drei Metriken zu erhalten: (die Werte wurden hier bereits normalisiert, liegen also zwischen 0,00 und 1,00)

3D Scatter Plot in Python [Matplotlib]
fig = pyplot.figure()
ax = fig.add_subplot(111, projection='3d')
ax.scatter(dataSet[:,0], dataSet[:,2], dataSet[:,1], marker='o', color=classColorVector)
ax.set_xlabel("Raumflaeche in Quadratmeter")
ax.set_ylabel("IA_Ratio")
ax.set_zlabel("Wandhoehe in Meter")
ax.set_xlim(xmin=0)
ax.set_ylim(ymin=0)
ax.set_zlim(zmin=0)
pyplot.show()

Es zeigt sich gerade in der 3D-Ansicht recht deutlich, dass sich Büros und Wohnungen zum nicht unwesentlichen Teil überschneiden und hier jeder Algorithmus mit der Klassifikation in Probleme geraten wird, wenn uns wirklich nur diese drei Dimensionen zur Verfügung stehen.

Schritt 3 – Kalkulation der Distanzen zwischen den einzelnen Punkten

Bei der Berechnung der Distanz in einem Raum hilft uns der Satz des Pythagoras weiter. Die zu überbrückende Distanz, um von A nach B zu gelangen, lässt sich einfach berechnen, wenn man entlang der Raumdimensionen Katheten aufspannt.

c = \sqrt{a^2+ b^2}

Die Hypotenuse im Raum stellt die Distanz dar und berechnet sich aus der Wurzel aus der Summe der beiden Katheten im Quadrat. Die beiden Katheten bilden sich aus der Differenz der Punktwerte (q, p) in ihrer jeweiligen Dimension.Bei mehreren Dimensionen gilt der Satz entsprechend:

Distanz = \sqrt{(q_1-p_1)^2+(q_2-p_2)^2+…+(q_n-p_n)^2}

Um mit den unterschiedlichen Werte besser in ihrer Relation zu sehen, sollten sie einer Normalisierung unterzogen werden. Dabei werden alle Werte einer Dimension einem Bereich zwischen 0.00 und 1.00 zugeordnet, wobei 0.00 stets das Minimum und 1.00 das Maximum darstellt.

NormWert = \frac{Wert - Min}{Wertspanne} = \frac{Wert - Min}{Max - Min}

$

def normalizeDataSet(dataSet):
    
    dataSet_n = numpy.zeros(numpy.shape(dataSet))     #[[ 0. 0. 0.]
                                                      # [ 0. 0. 0.]
                                                      # [ 0. 0. 0.]
                                                      # ..., 
                                                      # [ 0. 0. 0.]
                                                      # [ 0. 0. 0.]
                                                      # [ 0. 0. 0.]]
    
    minValues = dataSet.min(0)                        # [ 10. 2.6 0.]
    ranges = dataSet.max(0) - dataSet.min(0)          # [ 1775. 2.4 68.]
    
    minValues = dataSet.min(0)                        # [ 10. 2.6 0.]
    maxValues = dataSet.max(0)                        # [ 1785. 5. 68.]
 
    ranges = maxValues - minValues                    # [ 1775. 2.4 68.]
 
    rowCount = dataSet.shape[0]                       # 1039 
    
    # numpy.tile() wiederholt Sequenzen (hier:  [[ 10. 2.6 0. ], ..., [ 10. 2.6 0. ]]

    dataSet_n = dataSet - numpy.tile(minValues, (rowCount, 1))  #[[ 2.56000000e+02 9.00000000e-01 1.80000000e+01]
                                                                # [ 6.60000000e+01 2.00000000e-01 5.40000000e+01]
                                                                # [ 3.32000000e+02 1.50000000e-01 1.00000000e+01]
                                                                # ..., 
                                                                # [ 1.58000000e+02 6.00000000e-01 0.00000000e+00]
                                                                # [ 5.70000000e+01 1.00000000e-01 5.20000000e+01]
                                                                # [ 1.68000000e+02 2.00000000e-01 0.00000000e+00]]

    dataSet_n = dataSet_n / numpy.tile(ranges, (rowCount, 1))   #[[ 0.14422535 0.375 0.26470588]
                                                                # [ 0.0371831 0.08333333 0.79411765]
                                                                # [ 0.18704225 0.0625 0.14705882]
                                                                # ..., 
                                                                # [ 0.08901408 0.25 0.]
                                                                # [ 0.03211268 0.04166667 0.76470588]
                                                                # [ 0.09464789 0.08333333 0.]]

    #print(dataSet_n)
        
    return dataSet_n, ranges, minValues

Die Funktion kann folgendermaßen aufgerufen werden:

dataSet_n, ranges, minValues = normalizeDataSet(dataSet)

Schritt 4 & 5 – Klassifikation durch Eingrenzung auf k-nächste Nachbarn

Die Klassifikation erfolgt durch die Kalkulation entsprechend der zuvor beschriebenen Formel für die Distanzen in einem mehrdimensionalen Raum, durch Eingrenzung über die Anzahl an k Nachbarn und Sortierung über die berechneten Distanzen.

def classify(inX, dataSet, labels, k):

    rowCount = dataSet.shape[0]              # Anzahl an Zeilen bestimmen

    diffMat = numpy.tile(inX, (rowCount,1)) - dataSet # Berechnung der Katheten 
                                                      # (über tile() wird der Eingangsdatensatz über die Zeilenanzahl des dataSet vervielfacht,
                                                      # der dataSet davon substrahiert)
 
    sqDiffMat = diffMat**2                   # Quadrat der Katheten
    sqDistances = sqDiffMat.sum(axis=1)      # Aufsummieren der Differenzpaare
    distances = sqDistances**0.5             # Quadratwurzel über alle Werte
    sortedDistIndicies = distances.argsort() # Aufsteigende Sortierung
    
    classCount = {}
    
    #print("inX = %s, k = %s" % (inX, k))
    #print(sortedDistIndicies)
    
    for i in range(k):                                        # Eingrenzung auf k-Werte in der sortierten Liste 
        closest = labels[sortedDistIndicies[i]]               # Label (Kategorie [Büro, Wohnung, Haus] entsprechend der Sortierung aufnehmen
        classCount[closest] = classCount.get(closest, 0) + 1  # Aufbau eines Dictionary über die 
    
    sortedClassCount = sorted(classCount, key = classCount.get, reverse=True) # Absteigende Sortierung der gesammelten Labels in k-Reichweite
                                                                              # wobei die Sortierung über den Count (Value) erfolgt
    
    #print(classCount)       
    #print(sortedClassCount[0])
    
    return sortedClassCount[0]   # Liefere das erste Label zurück 
                                 # also das Label mit der höchsten Anzahl innerhalb der k-Reichweite

Über folgenden Code rufen wir die Klassifikations-Funktion auf und legen die k-Eingrenzung fest, nebenbei werden Fehler gezählt und ausgewertet. Hier werden der Reihe nach die ersten 30 Zeilen verarbeitet:

 errorCount = 0
    
 k = 5                             # k-Eingrenzung (hier: auf 5 Nachbarn einschränken)

 rowCount = dataSet_n.shape[0]     # Anzahl der Zeilen im gesamten Datensatz
 
 numTestVectors = 30               # Datensätze 0 - 29 werden zum testen von k verwendet,
                                   # die Datensätze ab Zeile 30 werden zur Klassifikation verwendet
 
 for i in range(0, numTestVectors): # Aufruf des Klassifikators von 0 bis 29 
    
    result = classify(dataSet_n[i,:], dataSet_n[numTestVectors:rowCount,:], classLabelVector[numTestVectors:rowCount], k)
    
    print("%s - the classifier came back with: %s, the real answer is: %s" %(i, result, classLabelVector[i]))
 
    if (result != classLabelVector[i]):
       errorCount += 1.0

 print("Error Count: %d" % errorCount)

Nur 30 Testdatensätze auszuwählen ist eigentlich viel zu knapp bemessen und hier nur der Übersichtlichkeit geschuldet. Besser ist für dieses Beispiel die Auswahl von 100 bis 300 Datensätzen. Die Ergebnisse sind aber bereits recht ordentlich, allerdings fällt dem Algorithmus – wie erwartet – noch die Unterscheidung zwischen Wohnungen und Büros recht schwer.

0 – klassifiziert wurde: Buero, richtige Antwort: Buero
1 – klassifiziert wurde: Wohnung, richtige Antwort: Wohnung
2 – klassifiziert wurde: Buero, richtige Antwort: Buero
3 – klassifiziert wurde: Buero, richtige Antwort: Buero
4 – klassifiziert wurde: Wohnung, richtige Antwort: Wohnung
5 – klassifiziert wurde: Wohnung, richtige Antwort: Wohnung
6 – klassifiziert wurde: Wohnung, richtige Antwort: Wohnung
7 – klassifiziert wurde: Wohnung, richtige Antwort: Buero
8 – klassifiziert wurde: Wohnung, richtige Antwort: Wohnung
9 – klassifiziert wurde: Wohnung, richtige Antwort: Wohnung
10 – klassifiziert wurde: Wohnung, richtige Antwort: Wohnung
11 – klassifiziert wurde: Wohnung, richtige Antwort: Wohnung
12 – klassifiziert wurde: Buero, richtige Antwort: Buero
13 – klassifiziert wurde: Wohnung, richtige Antwort: Buero
14 – klassifiziert wurde: Wohnung, richtige Antwort: Wohnung
15 – klassifiziert wurde: Wohnung, richtige Antwort: Wohnung
16 – klassifiziert wurde: Buero, richtige Antwort: Buero
17 – klassifiziert wurde: Wohnung, richtige Antwort: Wohnung
18 – klassifiziert wurde: Haus, richtige Antwort: Haus
19 – klassifiziert wurde: Wohnung, richtige Antwort: Wohnung
20 – klassifiziert wurde: Wohnung, richtige Antwort: Wohnung
21 – klassifiziert wurde: Buero, richtige Antwort: Buero
22 – klassifiziert wurde: Buero, richtige Antwort: Buero
23 – klassifiziert wurde: Buero, richtige Antwort: Buero
24 – klassifiziert wurde: Wohnung, richtige Antwort: Wohnung
25 – klassifiziert wurde: Wohnung, richtige Antwort: Wohnung
26 – klassifiziert wurde: Wohnung, richtige Antwort: Wohnung
27 – klassifiziert wurde: Wohnung, richtige Antwort: Wohnung
28 – klassifiziert wurde: Wohnung, richtige Antwort: Wohnung
29 – klassifiziert wurde: Buero, richtige Antwort: Buero
Error Count: 2

Über weitere Tests wird deutlich, dass k nicht zu niedrig und auch nicht zu hoch gesetzt werden darf.

 Datensätze  k Fehler
 150 1   25
 150 3   23
 150 5   21
 150 20   26

Ein nächster Schritt wäre die Entwicklung eines Trainingprogramms, dass die optimale Konfiguration (k-Eingrenzung, Gewichtung usw.) ermittelt.

Fehlerraten herabsenken

Die Fehlerquote ist im Grunde niemals ganz auf Null herabsenkbar, sonst haben wir kein maschinelles Lernen mehr, sondern könnten auch feste Regeln ausmachen, die wir nur noch einprogrammieren (hard-coding) müssten. Wer lernt, macht auch Fehler! Dennoch ist eine Fehlerquote von 10% einfach zu viel für die meisten Anwendungsfälle. Was kann man hier tun?

  1. Den Algorithmus verbessern (z. B. optimale k-Konfiguration und Gewichtung finden)
  2. mehr Merkmale finden (= mehr Dimensionen)
  3. mehr Daten hinzuziehen (gut möglich, dass alleine dadurch z. B. Wohnungen und Büros besser unterscheidbar werden)
  4. einen anderen Algorithmus probieren (kNN ist längst nicht für alle Anwendungen ideal!)

Das Problem mit den Dimensionen

Theoretisch kann kNN mit undenklich vielen Dimensionen arbeiten, allerdings steigt der Rechenaufwand damit auch ins unermessliche. Der k-nächste-Nachbar-Algorithmus ist auf viele Daten und Dimensionen angewendet recht rechenintensiv.

In der Praxis hat nicht jedes Merkmal die gleiche Tragweite in ihrer Bedeutung für die Klassifikation und mit jeder weiteren Dimension steigt auch die Fehleranfälligkeit, insbesondere durch Datenfehler (Rauschen). Dies kann man sich bei wenigen Dimensionen noch leicht bildlich vorstellen, denn beispielsweise könnten zwei Punkte in zwei Dimensionen nahe beieinander liegen, in der dritten Dimension jedoch weit auseinander, was im Ergebnis dann eine lange Distanz verursacht. Wenn wir beispielsweise 101 Dimensionen berücksichtigen, könnten auch hier zwei Punkte in 100 Dimensionen eng beieinander liegen, läge jedoch in der 101. Dimension (vielleicht auch auf Grund eines Datenfehlers) eine lange Distanz vor, wäre die Gesamtdistanz groß. Mit Gewichtungen könnten jedoch als wichtiger einzustufenden Dimensionen bevorzugt werden und als unsicher geltende Dimensionen entsprechend entschärft werden.

Je mehr Dimensionen berücksichtigt werden sollen, desto mehr Raum steht zur Verfügung, so dass um wenige Datenpunkte viel Leerraum existiert, der dem Algorithmus nicht weiterhilft. Je mehr Dimensionen berücksichtigt werden, desto mehr Daten müssen zu Verfügung gestellt werden, im exponentiellen Anstieg – Wo wir wieder beim Thema Rechenleistung sind, die ebenfalls exponentiell ansteigen muss.

Weiterführende Literatur


Machine Learning in Action

 


Introduction to Machine Learning with Python

Einführung in Data Science: Grundprinzipien der Datenanalyse mit Python

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    

 

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: 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(Xtheta)
]

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.

 

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