© Iurii Konoval, 123RF

Mit künstlicher Intelligenz bauen Programme Entscheidungsbäume selbstständig auf, indem sie aus vorliegenden Messwerten lernen. So ermittelt Mike Schilli, welches seiner Autos welchen Fahrer hatte.

In den 70er Jahren des vorigen Jahrhunderts strahlten die öffentlich-rechtlichen Sender noch Straßenfeger aus, die heute wohl keinen Hund mehr hinter dem Ofen hervorlocken würden. Einer war “Was bin ich?” mit Moderator Robert Lembke, in dem ein Rateteam durch Fragen mit Ja/Nein-Antworten die Identität eines Stargasts erraten musste.

Die vier versierten Ratefüchse schränkten zunächst mit möglichst generellen Fragen (“Sind Sie ein Mann?”) den Lösungsraum ein, um im Schlussspurt konkreter nachzubohren, bis das Netz um den Stargast enger wurde und schließlich seine Identität feststand.

Abbildung 1: Manuell erstellter Entscheidungsbaum zum Und-Gatter.

In der Software-Entwicklung setzen Programmierer ähnliche Verfahren ein, um Computern beizubringen, gelernte Verhaltensweisen zu imitieren. Das Verhalten eines Und-Gatters (Tabelle 1), das am Ausgang immer den Wert »0« zeigt bis an beiden Eingängen eine »1« anliegt, wird zwar normalerweise durch Binäroperatoren implementiert, aber zu Studienzwecken kann auch der Entscheidungsbaum in Abbildung 1 herhalten.

In diesem startet ein Programm am Kopfknoten und prüft, ob die Eingangsvariable »X« auf »1« steht. Ist dies nicht der Fall, erübrigen sich weitere Tests und das Ergebnis »0« steht fest. Ist »X« hingegen »1«, schreitet der Algorithmus nach unten links zum Knoten »Y==1?« fort. Mit dessen Auswertung steht das Endergebnis fest, ist nämlich auch »Y« gleich »1«, zeigt das Und-Gatter »1« an, ist »Y« hingegen »0«, ist auch der Gatterwert »0«.

Lernen unter Anleitung

Künstliche Intelligenz kann nun weit komplexere Zusammenhänge als simple Und-Gatter erfassen und simulieren. Die dort verwendeten Entscheidungsbäume gehen aber nach genau dem gleichen Verfahren vor. Beim so genannten Supervised Learning, also beim Lernen unter Anleitung, erhalten sie Eingabewerte wie »X« und »Y« sowie die erwarteten Ausgabewerte wie die Ergebnisse des Und-Gatters, bauen daraus automatisch Entscheidungsbäume und hangeln sich später im ausgelernten Zustand im Produktionsbetrieb durch die Abfrageregeln, um aus neuen Live-Eingabewerten passende Ergebnisse zu liefern – oder zumindest ähnliche Werte.

Beim automatischen Erstellen dieser auf Eingabedaten basierenden Entscheidungsbäume helfen nun KI-Kits [2] wie das Python-Modul »scikit-learn«, das sich einfach mittels

pip3 install scikit-learn scipy

installieren lässt, am besten in einer »virtualenv«-Umgebung, um den heimischen Rechner sauber zu halten:

virtualenv -p /usr/local/bin/python3 dt
source dt/bin/activate
pip3 install [...]

Listing 1 importiert zusätzlich das Modul »pydotplus«, um den Entscheidungsbaum zu Studienzwecken aufzuzeichnen.

01 #!dt/bin/python3
02 from sklearn import tree
03 import pydotplus
04
05 X=[[0,0],\
06    [0,1],\
07    [1,0],\
08    [1,1]]
09
10 Y=[0,0,0,1]
11
12 clf = tree.DecisionTreeClassifier()
13 clf = clf.fit(X, Y)
14
15   # dump decision tree
16 dot_data = tree.export_graphviz(
17     clf, out_file=None,
18     filled=True, rounded=True,
19     feature_names=['X','Y'],
20     class_names=['0','1'])
21 graph = \
22     pydotplus.graph_from_dot_data(dot_data)
23 graph.write_png("tree.png")
24
25   # Check predictions
26 for input in X:
27     print( input, ":",
28            clf.predict( [input] ) )

Zwingender Algorithmus

Die Python-Liste »X« enthält die vorab bekannten Eingabewerte des Gatters als eine Reihe von x/y-Werten, ebenfalls in Listenform. Die zugehörigen Ergebnisse führt die Variable »Y« weiter unten in der gleichen Reihenfolge. Die Klasse »tree« aus dem Modul »scikit-learn« (auch der abgekürzte Name »sklearn« ist gültig) bietet nun den Klassifizierer »DecisionTreeClassifier«, der durch Fitting mit der Methode »fit()« die Zusammenhänge lernt, intern einen Baum aufbaut und später mit »predict()« aus neuen Eingabewerten Ergebnisse vorhersagt.

Abbildung 2: Nach der Lernphase kann das Skript die Ausgabewerte des Und-Gatters reproduzieren.

Um einen Blick auf die internen Vorgänge in der Wurstfabrik des Verfahrens zu werfen, holt die Methode »export_graphviz()« ab Zeile 16 den generierten Baum hervor und gibt ihn in Text-Notation für das Diagrammtool »graphviz« aus. Das Python-Modul »pydotplus« (ebenfalls mit »pip3« installiert) macht daraus die PNG-Datei in Abbildung 3. Es benötigt hierzu das Paket »graphviz«, das der Admin unter Ubuntu mit »sudo apt-get install graphviz« nachinstalliert. Die Ausgabe des Skripts in Abbildung 2 zeigt, dass es nach der Fitting-Phase aus allen möglichen Eingabewerten die perfekten Ergebnisse erzielt.

Abbildung 3: Automatisch erstellter Entscheidungsbaum zum Und-Gatter.

Der maschinell erstellte Entscheidungsbaum in Abbildung 3 sieht auf den ersten Blick etwas unorthodox aus, aber Maschinen denken ja nicht rational, sie folgen stur ihren Algorithmen. So prüft der Klassifizierer erst, ob »X« kleiner als 0,5 ist, und gibt im Knoten links unterhalb davon als Ergebnis »class=0« aus, falls dies der Fall ist. Ist »X« größer als 0,5, prüft der Knoten rechts unterhalb, ob »Y« kleiner als 0,5 ist, und zeigt im nächsten Schritt »0« falls ja und »1«, falls »Y« größer, also wohl gleich »1« ist.

Das Verfahren ist genauso optimal wie der Baum in Abbildung 1, nur – typisch Computer – etwas verkopft. Genau wie das Superhirn Alpha Go [3], das mittlerweile reihenweise die weltbesten Go-Brettspieler der Welt schlägt, mit teilweise absurd erscheinenden Zügen, die kein Mensch jemals zuvor probiert hat.

Von unsicher nach sicher

Das von »scikit-learn« genutzte Verfahren [4] ist mathematisch belegt und baut den Baum auf, indem es die Gesamtmenge aller möglichen Eingabetupel und ihrer vorab vorliegenden Ergebnisse immer weiter in Teilmengen aufspaltet. Jede Unterteilung hat zum Ziel, die Unsicherheit im System – seine Entropie – weiter zu minimieren. Am Kopfknoten ist die Entropie noch hoch, dort ist noch nichts über das Ergebnis bekannt, also müsste der Algorithmus als Ergebnis zufällig entweder 0 oder 1 auswählen. Da die Ausgabe in 75 Prozent aller Fälle 0 und zu 25 Prozent gleich 1 ist (Tabelle 1), beträgt die Entropie im System anfangs:

- (1/4)*ln(1/4) - (3/4)*ln(3/4) = 0,56

Unterteilt der erste Knoten die möglichen Eingabewerte mit dem Vergleich »X<=0,5?« in zwei Teilmengen »[[0,0],[0,1]]« und »[[1,0],[1,1]]«, dann ist die Entropie der ersten Teilmenge gleich 0 (das Ergebnis ist in jedem Fall 0, also sicher) und die der zweiten weiterhin 0,56, also ist die Gesamtentropie:

- 1/2*8 + 1/2*0,56 = 0,28

Mit nur einem Knoten im Baum hat die Entropie des Systems von 0,56 auf 0,28 abgenommen. Ein weiterer Knoten, der die zwei verbleibenden Ergebnistupel im Fall »X>0,5« mit »Y<=0,5« in zwei Einzelergebnisse aufspaltet, lässt die Entropie des Gesamtsystems auf »0« sinken. Es kann folglich mit zwei Knoten das Ergebnis für jeden beliebigen Eingabetupel mit 100-prozentiger Wahrscheinlichkeit fehlerfrei voraussagen.

Das ist in unserem Fall höchstens von akademischem Interesse, denn ein Und-Gatter lässt sich trivial in Hardware oder Software aufbauen. Aber dass ein Algorithmus, der nichts vom internen Aufbau ahnt und nur aus Kombinationen von Eingabe- und Ausgabewerten lernt, das Verhalten des ihm unbekannten Systems imitiert, hat Potenzial. Als Bonus unterstützt er sogar nicht erlaubte Eingabewerte wie »[0.9,0.8]«, die er in sinnvolle Ergebnisse (in dem Fall »1«) umgießt.

Wer ist gefahren?

Als praktische KI-Anwendung soll ein Entscheidungsbaum anhand von Fahrdaten aus dem Auto ermitteln, wer am Steuer saß. Wie im vorigen Snapshot [5] habe ich Daten aus den Automatic-Adaptern [6] meiner beiden Autos aufbereitet, die festhalten, wann, wo und wie schnell die Fahrzeuge gefahren sind.

Nur weiß der Adapter nicht, wer gefahren ist, und da meine Frau und ich abwechselnd mit zwei Autos fahren, soll die lernfähige Maschine mittels einiger von Hand mit dem Fahrerkürzel (»M« oder »A«) ergänzten Trip-Daten in Listing 2 eventuell vorhandene Kriterien lernen, um bei neuen Trip-Daten automatisch den Fahrer zu ergänzen.

01 dow,miles,brakes,accels,speed,vehicle,driver
02 3,5894.2,0,0,0,1,A
03 3,471.4,0,0,0,1,A
04 2,1279.4,0,0,0,1,A
05 4,21876.9,5,2,0,1,A
06 4,1510,1,1,0,1,A
07 4,20586.9,3,0,0,1,A
08 3,22381.9,1,1,0,1,A
09 2,39883.3,2,2,18,1,A
10 1,2005.6,2,4,0,1,A
11 3,16131.6,4,2,6,2,M
12 7,11788.7,1,0,14,1,M
13 6,19103.8,0,2,20,1,M
14 5,21384.3,1,0,15,2,M

Jede Zeile in der CSV-Datei in Listing 2 repräsentiert eine aufgezeichnete Autofahrt, die vorletzte Spalte »vehicle« gibt an, ob der “Brummi” genannte Honda Fit »1« fuhr oder meine “Rakete” genannte Rennsemmel, ein 1998er Acura Integra »2«. Letzteren lenkt meine Frau eher selten, sie fährt aber häufig unter der Woche mit “Brummi” zur Arbeit (»dow= 1-5«), während ich eher am Wochenende (»dow=6-7«) spazieren fahre.

Egal ob mit “Brummi” oder “Rakete”, die Spalte »speed« scheint mir als Fahrer aus unverständlichen Gründen mehr Punkte zu geben als meiner Frau. Bremsen oder Gas geben (»brakes« und »accels«) scheinen gleich verteilt. Reichen diese Kriterien mit den von Hand ergänzten Fahrern aus, um dem System beizubringen, bei neuen Trips den Fahrer richtig zu erraten?

Fahrpraxis

Listing 3 liest die CSV-Datei in einen Pandas-Dataframe ein. Die Liste »Y« erhält die Einträge, die von Hand mit »M« oder »A« ergänzt wurden, in der Spalte »driver« als gewünschte Ergebnisse. In »X« steht ab Zeile 9 eine zweidimensionale Liste, in der reihenweise Trip-Daten stehen, die den Wochentag (»dow«: 1-7), die Anzahl der gefahrenen Kilometer (»miles«), Brems- und Beschleunigungsvorgänge (»brakes« und »accels«), eine Geschwindigkeitswertung (»speed«) sowie die Fahrzeug-ID (»vehicle«) enthalten.

01 #!dt/bin/python3
02 from sklearn import tree
03 import pandas as pd
04
05 df = pd.read_csv("trips-learn.csv",
06         header = 0)
07
08 Y = df['driver']
09 X = df[['dow', 'miles', 'brakes', 'accels',
10         'speed', 'vehicle']]
11
12 clf = tree.DecisionTreeClassifier()
13 clf = clf.fit(X, Y)
14
15    # Check predictions
16 for input in [[6,2000,0,2,20,1],
17               [6,2000,0,2,0,1]]:
18     print( input, ":",
19            clf.predict( [input] ) )

Wie in der vorherigen Theorievorlesung kommt auch in Listing 3 die »sklearn«-Klasse »DecisionTreeClassifier« zum Einsatz, deren Methode »fit« die Trainingsdaten verarbeitet und später mit »predict()« neue Ergebnisse voraussagt.

Erstaunlicherweise errät »driver.py« in Abbildung 4 bei neuen Trip-Records, deren Kilometerstand bisher noch nirgends in den Testdaten vorkam, und beim gleichen Auto (»1«: Honda Fit) nur aufgrund der Geschwindigkeitspunkte die Fahrer einmal als »M« und einmal als »A«. Der Entscheidungsbaum hat also nach tiefschürfender Analyse festgestellt, dass dies das wesentliche Unterscheidungsmerkmal der beiden Fahrer ist.

Abbildung 4: Nach der Lernphase identifiziert der Entscheidungsbaum Autofahrer am Fahrverhalten.

Im ersten Versuch liefert das Verfahren schon sehr ordentliche Ergebnisse, wie zuverlässig sie wirklich sind, sollen später weitere Testdaten zeigen. Besteht Verbesserungsbedarf führen mehr Trainingsdaten dann auch zu einem besseren Entscheidungsbaum.