Posts

Einstieg in das Maschinelle Lernen mit Python(x,y)

Python(x,y) ist eine Python-Distribution, die speziell für wissenschaftliche Arbeiten entwickelt wurde. Es umfasst neben der Programmiersprache auch die Entwicklungsumgebung Spyder und eine Reihe integrierter Python-Bibliotheken. Mithilfe von Python(x,y) kann eine Vielzahl von Interessensbereichen bearbeitet werden. Dazu zählen unter anderem Bildverarbeitung oder auch das maschinelle Lernen. Das All-in-One-Setup für Python(x,y) ist für alle gängigen Betriebssysteme online erhältlich. Read more

Die Rastrigin-Funktion

Jeder Data Scientist kommt hin und wieder mal in die Situation, einen Algorithmus trainieren bzw. optimieren zu wollen oder zu müssen, ohne jedoch, dass passende Trainingsdaten unmittelbar verfügbar wären. Zum einen kann man in solchen Fällen auf Beispieldaten zugreifen, die mit vielen Analysetools mitgeliefert werden, oder aber man generiert sich seine Daten via mathematischer Modelle selbst, die für bestimmte Eigenschaften bekannt sind, die gute Bedingungen für das Optimierungstraining liefern. 

Ein solches Modell, das man als Machine Learning Entwickler kennen sollte, ist die Rastrigin-Funktion, die laut Wikipedia von Leonard A. Rastrigin erstmalig beschrieben wurde. Dabei handelt es sich um eine Häufigkeites-/Wahrscheinlichkeitsverteilung, deren Dichte mehrere lokale Modi (Gipfel) aufweist. Ein Modus (oder Modalwert) ist in einer Häufigkeitsverteilung der häufigste Wert (“Bergspitze”) bzw. der Wert mit der höchsten Wahrscheinlichkeit.

Anmerkung des Autors: Dieser Artikel stellt zum einen die Rastrigin-Funktion und ihre Bedeutung für die Optimierungsrechnung vor, ist zum anderen aber auch eine Einführung in den Umgang mit NumPy-Matrizen (die eine Menge For-Schleifen ersparen können).

Die Rastrigin-Funktion

Mathematisch beschrieben wird die Rastrigin-Funktion wie folgt:

f(x_1 cdots x_n) = An + sum_{i=1}^n (x_i^2 -10cos(2pi x_i))

-5.12 leq x_i leq 5.12

Wobei für das globale Minimum gilt: f(0) = 0
Außerdem ist zu beachten, dass A=10 eine Konstante ist.

Die Rastrigin-Funktion im Standard-Python umsetzen und visualisieren

Die Formel lässt sich in Python (wie natürlich in jeder anderen Programmiersprache auch) einfach umsetzen:

value = 10 + x**2 - 10 * math.cos(2 * math.pi * x)

Nun können wir über den klassischen Weg der Programmierung einfach eine For-Schleife verwenden, um die Rastrigin-Funktionswerte in eine Liste zu packen und mit einem Plot zu visualsieren, dabei bin ich leider doch nicht ganz um die Verwendung des NumPy-Pakets nicht herumgekommen:

import matplotlib.pyplot as pyplot
import numpy as np # NumPy hat die Matrizen-Datenstruktur, die wir benötigen 
import math as math # Grundlegende mathematische Funktionen (hier benötigt: Kreiszahl Pi und Cosinus-Funktion)

rastriginValues = []
i = 0


for x in np.arange(-5.12, 5.12, 0.01): # Die Python-eigene range()-Funktion kann leider keine Floats, sondern nur Integer erzeugen :-/
    value = 10 + x**2 - 10 * math.cos(2 * math.pi * x)
    i += 1
    print(i, x, value)
    rastriginValues.append(value)
    
pyplot.plot(rastriginValues)
pyplot.ylim(0,50)
pyplot.xlim(0,1024)
pyplot.show()

rastrigin-line-chart

Die grafische Darstellung zeigt, dass es sich tatsächlich um eine symmetrische multimodalen Verteilung handelt.

Die Rastrigin-Funktion mehrdimensional umsetzen, mit NumPy-Matrizen-Funktionen

Die obige Umsetzung der Rastrigin-Funktion ist eindimensional (eine Variable), braucht für die Darstellung allerdings zwei Dimensionen (f(x) und die Durchlaufanzahl bzw. Zeitachse). Nun könnten wir die Zahl der Variablen von 1 (x) auf 2 (x und y) erhöhen und eine dreidimensionale Darstellung erzeugen. Eine ähnliche dreidimensionale Darstellung gab es bereits in meiner Vorstellung des k-nearest-Neighbour-Algorithmus nachzuvollziehen. Dabei müssten wir die Konstante A=10 auf A=20 verdoppeln:

from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as pyplot
import numpy as np

figure = pyplot.figure()
axe = figure.add_subplot(111, projection='3d')

x = np.linspace(-5.12, 5.12, 100) # unterteilt den Bereich in 100 Schnitte, ähnlich: np.arange(-5.12, 5.12, 0.1)
y = np.linspace(-5.12, 5.12, 100)
x, y = np.meshgrid(x, y) # erzeugt ein Koordinatensystem

# Nun ohne Schleifen: Wir wenden die NumPy-Funktionen (np.cos statt math.cos und np.pi statt math.pi) 
# auf die NumPy-Arrays an (x und y) und erhalten ein NumPy-Array z zurück
z = 20 + x**2 - 10 * np.cos(2 * np.pi * x) + y**2 - 10 * np.cos(2* np.pi * y)

# Plotte die drei Variablen (x, y, z) im dreidimensionalen Raum
axe.plot_surface(x, y, z, rstride=1, cstride=1, cmap="jet", linewidth=0, antialiased=False)

pyplot.title('Rastrigin-Map')
pyplot.grid(True)
axes = pyplot.gca()
axes.set_xlim([-5.12,5.12])
axes.set_ylim([-5.12,5.12])
pyplot.show()

rastrigin-funktion-python-3d-plot

Die Rastrigin-Funktion wird gerne für Optimierungsalgorithmen eingesetzt, wofür sie wegen des großen Suchraums und der hohen Anzahl lokaler Modi ein herausforderndes Umfeld bietet. Beispielsweise wird – meines Erachtens nach – das wohl beliebteste Optimierungsverfahren im maschinellen Lernen, das Gradientenverfahren, hier keine guten Ergebnisse liefern, denn es gibt einfach zu viele lokale Minima.

 

 

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    

 

Toolkits & Services für Semantische Textanalysen

Named Entity Recognition ist ein Teilgebiet von Information Extraction. Ziel von Information Extraction ist die Gewinnung semantischer Informationen aus Texten (im Gegensatz zum verwandten Gebiet des Information Retrieval, bei dem es um das möglichst intelligente Finden von Informationen, die u.U. vorab mit Information Extraction gewonnen wurden, geht). Named Entity Recognition (kurz NER) bezeichnet die Erkennung von Entitäten wie z.B. Personen, Organisationen oder Orten in Texten.

[box]Beispiel:
Albert Einstein war ein theoretischer Physiker, der am 14. März 1879 in Ulm geboren wurde. Er erhielt 1921 den Nobelpreis für Physik. Isaac Newton, Einstein und Stephen Hawking werden oft als die größten Physiker seit der Antike bezeichnet.”[/box]

Die Disambiguierung von Entitäten ist ein weiterer wichtiger Schritt auf dem Weg zu einem semantischen Verständnis von Texten. Wenn man so in obigem Text erkennen kann, dass “Albert Einstein“, “Er” und “Einstein” die gleiche Person bezeichnen, so kann ein Analyseverfahren z.B. daraus schließen, dass in diesem Text Einstein eine wichtigere Rolle spielt, als Newton, der nur einmal erwähnt wurde. Die Hyperlinks hinter den jeweiligen Entitäten zeigen eine Möglichkeit der semantischen Anreicherung von Texten an – in diesem Fall wurden die Entitäten mit entsprechenden Einträgen bei DBpedia automatisch verlinkt.

Named Entity Recognition dient vorrangig zwei Zwecken:

  • Anreicherung von Texten mit Metadaten
  • Abstraktion von Texten zur besseren Erkennung von Mustern

Punkt 1 dient direkt dem Information Retrieval. Anwender können so z.B. gezielt nach bestimmten Personen suchen, ohne alle möglichen Schreibweisen oder Berufsbezeichnungen auflisten zu müssen.

Punkt 2 dient der Vorverarbeitung von Texten als Input für Machine Learning Verfahren. So ist es (je nach Anwendung!) oft nicht von Bedeutung, welche Person, welcher Ort oder auch welche Uhrzeit in einem Text steht sondern nur die Tatsache, dass Personen, Orte oder Zeiten erwähnt wurden.

Sirrus Shakeri veranschaulicht die zentrale Bedeutung semantischer Analyse in seinem Beitrag From Big Data to Intelligent Applications:

intelligent-applications-cirrus-shakeri

Abbildung 1: Von Big Data zu Intelligent Applications von Cirrus Shakeri

Sein “Semantic Graph” setzt voraus, dass Entitäten mittels “Natural Language Processing” erkannt und zueinander in Beziehung gesetzt wurden.

Es ist interessant zu vermerken, dass Natural Language Processing und Data Mining / Machine Learning über viele Jahre als Alternativen zueinander und nicht als Ergänzungen voneinander gesehen wurden. In der Tat springen die meisten Vorgehensmodelle heutzutage von “Data Preparation” zu “Machine Reasoning”. Wir argumentieren, dass sich in vielen Anwendungen, die auf unstrukturierten Daten basieren, signifikante Qualitätsverbesserungen erzielen lassen, wenn man zumindest NER (inklusive Disambiguierung) in die Pipeline mit einbezieht.

Toolkits und Services für NER

Es existiert eine Vielzahl von Toolkits für Natural Language Processing, die Sie mehr oder weniger direkt in Ihre Programme einbinden können. Exemplarisch seien drei Toolkits für Java, Python und R erwähnt:

Diese Toolkits enthalten Modelle, die auf Korpora für die jeweils unterstützten Sprachen trainiert wurden. Sie haben den Vorteil, dass sie auch vollkommen neue Entitäten erkennen können (wie z.B. neue Politiker oder Fernsehstars, die zur Trainingszeit noch unbekannt waren). Je nach Einstellung haben diese Systeme aber auch eine relativ hohe Falsch-Positiv-Rate.

Wer NER nur ausprobieren möchte oder lediglich gelegentlich kleinere Texte zu annotieren hat, sei auf die folgenden Web Services verwiesen, die auch jeweils eine REST-Schnittstelle anbieten.

DBpedia

Das DBpedia Projekt nutzt die strukturierten Informationen der verschieden-sprachigen Wikipedia Sites für den Spotlight Service. Im Unterschied zu den reinen Toolkits nutzen die nun genannten Werkzeuge zusätzlich zu den trainierten Modellen eine Wissensbasis zur Verringerung der Falsch-Positiv-Rate. Die mehrsprachige Version unter http://dbpedia-spotlight.github.io/demo zeigt die Möglichkeiten des Systems auf. Wählen Sie unter “Language” “German“) und dann über “SELECT TYPES…” die zu annotierenden Entitätstypen. Ein Beispieltext wird automatisch eingefügt. Sie können ihn natürlich durch beliebige andere Texte ersetzen. Im folgenden Beispiel wurden “Organisation”, “Person”, und “Place“ ausgewählt:

DBprediaSpotlight

Abbildung 2: DBpedia Demo (de.dbpedia.org)

Die erkannten Entitäten werden direkt mit ihren DBpedia Datenbankeinträgen verlinkt. Im Beispiel wurden die Orte Berlin, Brandenburg und Preußen sowie die Organisationen Deutsches Reich, Deutsche Demokratische Republik, Deutscher Bundestag und Bundesrat erkannt. Personen wurden in dem Beispieltext nicht erkannt. Die Frage, ob man “Sitz des Bundespräsidenten” als Ort (Sitz), Organisation (das Amt des Bundespräsidenten) und / oder Person (der Bundespräsident) bezeichnen sollte, hängt durchaus vom Anwendungsszenario ab.

OpeNER

Das OpeNER Projekt ist das Ergebnis eines europäischen Forschungsprojekts und erweitert die Funktionalität von DBpedia Spotlight mit weiteren semantischen Analysen. Die Demo unter http://demo2-opener.rhcloud.com/welcome.action (Tab “Live Analysis Demo“, “Named Entity Recognition and Classification” und “Named Entity Linking” auswählen und “Analyse” drücken, dann auf der rechten Seite das Tab “NERC” anwählen) ergibt für den gleichen Beispieltext:

opeNER-projekt

Abbildung 3: OpeNER Projekt (opener-project.eu)

Organisationen sind blau hinterlegt, während Orte orange markiert werden. Auch hier werden erkannte Entitäten mit ihren DBpedia Datenbankeinträgen verknüpft. Die Bedeutung dieser Verknüpfung erkennt man wenn man auf das Tab “Map” wechselt. Berlin wurde als Ort erkannt und über die Geo-Koordinaten (geo:long = 13.4083, geo.lat = 52.5186) im DBpedia Eintrag von Berlin konnte das Wort “Berlin” aus obigem Text automatisch auf der Weltkarte referenziert werden.

Es gibt eine Vielzahl weiterer Services für NLP wie z.B. OpenCalais. Einige dieser Services bieten bestimmte Funktionalitäten (wie z.B. Sentiment Analysis) oder andere Sprachen neben Englisch nur gegen eine Gebühr an.

Listen Tagger

Der Vollständigkeit halber sei noch erwähnt, dass in den meisten Anwendungsszenarien die oben genannten Werkzeuge durch sogenannte Listen-Tagger (englisch Dictionary Tagger) ergänzt werden. Diese Tagger verwenden Listen von Personen, Organisationen oder auch Marken, Bauteilen, Produktbezeichnern oder beliebigen anderen Gruppen von Entitäten. Listen-Tagger arbeiten entweder unabhängig von den oben genannten statistischen Taggern (wie z.B. dem Standford Tagger) oder nachgeschaltet. Im ersten Fall markieren diese Tagger alle Vorkommen bestimmter Worte im Text (z.B. „Zalando“ kann so direkt als Modemarke erkannt werden). Im zweiten Fall werden die Listen genutzt, um die statistisch erkannten Entitäten zu verifizieren. So könnte z.B. der Vorschlag des statistischen Taggers automatisch akzeptiert werden wenn die vorgeschlagene Person auch in der Liste gefunden wird. Ist die Person jedoch noch nicht in der Liste enthalten, dann könnte ein Mitarbeiter gebeten werden, diesen Vorschlag zu bestätigen oder zu verwerfen. Im Falle einer Bestätigung wird die neu erkannte Person dann in die Personenliste aufgenommen während sie im Falle einer Ablehnung in eine Negativliste übernommen werden könnte damit dieser Vorschlag in Zukunft automatisch unterdrückt wird.

Regular Expression Tagger

Manche Entitätstypen folgen klaren Mustern und können mit hoher Zuverlässigkeit durch reguläre Ausdrücke erkannt werden. Hierzu zählen z.B. Kreditkarten- oder Telefon- oder Versicherungsnummern aber auch in vielen Fällen Bauteilbezeichner oder andere firmeninterne Identifikatoren.

Fazit

Natural Language Processing und insbesondere Named Entity Recognition und Disambiguierung sollte Teil der Werkzeugkiste eines jeden Anwenders bei der Analyse von unstrukturierten Daten sein. Es existieren mehrere mächtige Toolkits und Services, die allerdings je nach Anwendungsgebiet kombiniert und verfeinert werden müssen. So erkennt DBpedia Spotlight nur Entitäten, die auch einen Wikipedia Eintrag haben, kann für diese aber reichhaltige Metadaten liefern. Der Stanford Tagger hingegen kann auch vollkommen unbekannte Personennamen aus dem textuellen Kontext erkennen, hat aber bei manchen Texten eine relativ hohe Falsch-Positiv-Rate. Eine Kombination der beiden Technologien und anwendungsspezifischen Listen von Entitäten kann daher zu qualitativ sehr hochwertigen Ergebnissen führen.

Interview – Data Science in der FinTech-Branche

Christian Rebernik ist CTO bei Number 26 und zuständig für die technische Entwicklung dieses FinTech-Unternehmens. Er studierte Informatik und Wirtschaftsinformatik und kann auf langjährige Erfahrung als Software-Entwickler zurückgreifen. Seit etwa 2010 war er als CTO und CIO bei diversen eCommerce-christian-rebernikUnternehmen, u.a. bei Immobilien.net (heute ImmobilienScout24), PARSHIP und Zanox, tätig und gilt daher als ein etablierter IT-Manager, der seine Kenntnisse als Mentor des Axel Springer Plug and Play Accelerators weitergibt.

Data Science Blog: Herr Rebernik, wie sind Sie als CTO zum FinTech Number26 gekommen?

Ich durfte die Gründer im Accelerator 2013 als Mentor begleiten. Damals war das Produkt ausgelegt auf Teenager als Zielgruppe. 2014 änderten die Gründer Valentin und Maximilian das Produkt auf Number26, ein mobile-first Gehaltskonto mit Mastercard und der Vision das weltbeste Bankerlebnis zu bieten. Damit hatten sie aus meiner Sicht den richtigen Nerv der Zeit getroffen. Mein Erfahrung mit Banken war nicht positiv bis dato. Number26 hat aus meiner Sicht das Potential Bankwesen zu verändern.

Data Science Blog: Die FinTech-Szene möchte vieles besser machen als traditionelle Banken. Welche Rolle spielt Data Science dabei?

Beim Online-Banking etablierter Banken erhält man meistens nur eine reine Ansicht des Bankkontos, quasi eine statische und nicht kundenorientierte Darstellung des Kontostandes und der Kontotransaktionen. Wir glauben, diese Auflistung ohne Intelligenz ist nicht ausreichend und wenig auf den Kundenutzen fokussiert, mit der heutigen Technik kann man deutlich mehr bieten.
Unser Ziel ist es, eine der besten Customer Experience zu schaffen. Dank moderner Technologien haben wir viele unterschiedliche Möglichkeiten, um das zu erreichen. Eine davon ist es Smart Banking anzubieten, hier kommt Data Science ins Spiel.

Data Science Blog: Wofür nutzt Number26 Data Science genau?

Wir starten in Sachen Data Science jetzt erst voll durch. Unser erster Data Scientist wurde letztes Jahr im Oktober eingestellt. Unser Team ist also noch im Aufbau. Aktuell steht die sichere und number26appautomatisierte Kategorisierung von Finanztransaktionen bei uns im Fokus. Damit bieten wir den Nutzern leicht verständliche und genaue Auswertungen ihrer finanziellen Situation sowie eine Übersicht ihrer Einnahmen und Ausgaben. Interessanterweise gibt es unseres Wissens nach noch keine Bank, die Transaktionen direkt für den Kundennutzen kategorisiert.
Abhängig von der Transaktionsart nutzen wir unterschiedliche Methoden des maschinellen Lernens, die wir für die Erkennung der übergeordneten Kategorie verwenden.

Data Science Blog: Welche Machine Learning Methoden kommen zum Einsatz? Und wo finden die Analysen statt?

Wir haben mehrere ML-Methoden ausprobiert und durch eine Prototyping-Phase hinsichtlich ihrer Treffgenauigkeit bewertet. Wir setzen auf Amazon Webservices (AWS) und nutzen das Amazon Machine Learning Framework, auf dem wir auch unsere Modelle testen und Algorithmen erstellen. Der Input ist beispielsweise eine Kontotransaktion.
Unsere Algorithmen versuchen dieses dann zu kategorisieren. Daraus gewinnen wir zusätzliche Informationen, die wir unseren Kunden als Mehrwert anbieten.
Handelt es sich um eine Peer-to-Peer-Transaktion, wenn beispielsweise ich einem Freund Geld überweise, parsen wir den Verwendungszweck und nutzen Textmustererkennung zur Kategorisierung der Überweisung. Dazu splitten wir den Überweisungstext in einzelne Wörter auf, deren Bedeutung über Wörterbücher erkannt werden. Dadurch entstehen Kategorien, die vom Nutzer auch manuell nachträglich geändert werden können. Dieses Nutzerfeedback fließt in den Algorithmus zurück und wird in zukünftige Kategorisierungen mit einbezogen. Wir arbeiten nach mehreren Experimenten nun vermehrt mit Vector Spacing Modellen, wie dem k-Nearest-Neighbour-Algorithmus, über zurzeit 12 Achsen (Vektordimensionen). Jeder Vektor stellt eine Eigenschaft einer Transaktion dar, beispielsweise Geldbetrag, Verwendungszweck, Empfänger oder Währung. Je näher die Eigenschaften, die im Vektorraum als Punkte dargestellt werden, an den Eigenschaften anderer Finanztransaktion im selben Vektorraum liegen, desto wahrscheinlicher ist die Gemeinsamkeit als Kategorie.
Natürlich gibt es immer wieder False-Positives, die die eigentliche Herausforderung in Data Science darstellen. Beispielsweise lassen sich seltene Transaktionen wie die Zahnarztrechnung nur schwer trainieren. Wir trainieren unsere Kategorisierung der Banktransaktionen unter Einbeziehung der MasterCard-Kreditkartentransaktionen. Alle Vertragspartner bei MasterCard müssen einige Angaben mahcen, z.B. welche Art von Händler sie sind, Das hilft natürlich bei der Kategorisierung.

Data Science Blog: Der Beruf des Data Scientist wurde schon öfter als„Sexiest Job des 21. Jahrhunderts“ zitiert, gilt das auch in der Finanzindustrie?

Wir als FinTech-Unternehmen sind technologiegetrieben und in unserer Branche macht es wirklich Spaß, Probleme des Finanzalltags zu lösen. Neue Lösungen anzubieten, auf die vorher noch niemand gekommen ist, ist zwar nicht jedermanns Sache, unser Schlag Menschen entwickelt aber genau dafür die größte Leidenschaft.

Data Science Blog: Was sind Ihrer Meinung nach die alltäglichen Aufgaben eines Data Scientists und welche Skills sollte ein Data Scientist dafür mitbringen?

Die Arbeit als Data Scientist ist meines Erachtens dreigeteilt: ein Drittel Datenaufbereitung, ein Drittel Software-Entwicklung und ein Drittel Analyse.
Zum ersten Drittel gehört die Sichtung der Daten und Identifikation der Datenqualität. Ein Data Scientist muss aber auch Software-Entwickler sein und ein Verständnis für Software-Architekturen mitbringen. Große Datenmengen lassen sich nur über skalierbare Anwendungen auswerten. Wichtige Hilfsmittel und Testumgebungen müssen dafür selbst entwickelt werden.
Für die Analyse ist ein gutes Verständnis von Mathematik unumgänglich. Hinzu kommt ein ausgezeichnetes Verständnis für das Kerngeschäft des Unternehmens, in unserem Fall das Finanzwesen, um dementsprechend relevante Analysen durchzuführen.

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.

Wie lernen Maschinen?

Im zweiten Teil wollen wir das mit Abstand am häufigsten verwendete Optimierungsverfahren – das Gradientenverfahren oder Verfahren des steilsten Abstiegs – anhand einiger Beispiele näher kennen lernen. Insbesondere werden wir sehen, dass die Suchrichtung, die bei der Benennung der Verfahren meist ausschlaggebend ist, gar nicht unbedingt die wichtigste Zutat ist.

Read more

Wie lernen Maschinen?

Machine Learning ist eines der am häufigsten verwendeten Buzzwords im Data-Science- und Big-Data-Bereich. Aber lernen Maschinen eigentlich und wenn ja, wie? In den meisten Fällen lautet die Antwort: Maschinen lernen nicht, sie optimieren. Fällt der Begriff Machine Learning oder Maschinelles Lernen, so denken viele sicherlich zuerst an bekannte “Lern”-Algorithmen wie Lineare Regression, Logistische Regression, Neuronale Netze oder Support Vector Machines. Die meisten dieser Algorithmen – wir beschränken uns hier vorerst auf den Bereich des Supervised Learning – sind aber nur Anwendungen einer anderen, grundlegenderen Theorie – der mathematischen Optimierung. Alle hier angesprochenen Algorithmen stellen dem Anwender eine bestimmte Ziel- oder Kostenfunktion zur Verfügung, aus der sich i.a. der Name der Methode ableitet und für die im Rahmen des Lernens ein Minimum oder Optimum gefunden werden soll. Ein großer Teil des Geheimnisses und die eigentliche Stärke der Machine-Learning-Algorithmen liegt nun darin, dass dieser Minimierungsprozess effizient durchgeführt werden kann. Wir wollen im Folgenden kurz erklären, wie dies in etwa funktioniert. In einem späteren Blogpost gehen wir dann genauer auf das Thema der Effizienz eingehen. Read more