In den 70er-Jahren des letzten Jahrhunderts strahlten die öffentlich-rechtlichen Sender noch Straßenfeger aus, die heute wohl keinen Hund mehr hinter dem Ofen hervorlocken würden. Eine dieser Sendungen war "Was bin ich?" mit Altmoderator Robert Lembke, in der ein Rateteam durch gezielte Fragen mit Ja/Nein Antworten die Identität eines Stargasts erraten musste.
Die vier immer gleichen und deswegen strategisch äußerst versierten Ratefüchse schränkten bei diesem Quiz zunächst mit möglichst generellen Fragen (z.B. "Sind Sie ein Mann?") den Lösungsraum zügig ein, um dann im Schlussspurt immer konkreter nachzubohren, bis das Netz um den Stargast von Runde zu Runde immer enger wurde und schließlich seine Identität feststand.
| |
| Abbildung 1: Logische UND-Verknüpfung der Variablen X und Y |
In der Software-Entwicklung setzen Programmierer ähnliche Verfahren ein, um Computern beizubringen, gelernte Verhaltensweisen zu imitieren. Das Verhalten eines Und-Gatters (Abbildung 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 2 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.
 |
| Abbildung 2: Manuell erstellter Entscheidungsbaum zum Und-Gatter |
Ist X hingegen 1, schreitet der Algorithmus nach unten links zum Knoten "Y==1?" fort, und 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.
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 sogenannten "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 wie das Python-Modul scikit-learn,
das sich einfach mittels
$ pip3 install scikit-learn scipy
installiert, am besten in einer virtualenv-Umgebung, um den
heimischen Rechner sauber und aufgeräumt 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 erstellten 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] ) )
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 3: Nach der Lernphase kann das Skript die Ausgabewerte des Und-Gatters fehlerlos reproduzieren. |
Um einen Blick auf die internen Vorgänge in der Wurstfabrik des Verfahrens zu
werfen, holt die Methode export_graphviz() in Zeile 16 den generierten Baum
hervor, und gibt ihn in Text-Notation für das Diagramm-Tool graphviz aus.
Das Python-Modul pydotplus (ebenfalls mit pip3 installiert) macht daraus
die PNG-Datei in Abbildung 4. 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 3 zeigt, dass es nach der Fitting-Phase aus
allen möglichen Eingabewerten die perfekten Ergebnisse erzielt.
 |
| Abbildung 4: Automatisch erstellter Entscheidungsbaum zum Und-Gatter |
Der maschinell erstellte Entscheidungsbaum in Abbildung 4 sieht auf den ersten Blick etwas unorthodox aus, aber Maschinen denken ja nicht rational, sondern folgen stur ihren Algorithmen. So prüft der Klassifizierer erst, ob X kleiner als 0.5 ist, und gibt im links unterhalb davon gelegenen Knoten 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 2, nur eben, typisch Computer, etwas verkopft. Genau wie das Superhirn AlphaGo ([3]), das mittlerweile reihenweise die weltbesten Go-Brettspieler der Welt schlägt, mit teilweise absurd erscheinenden Zügen, die kein Mensch jemals vorher probiert hat.
Das von scikit-learn genutzte Verfahren ist mathematisch belegt und
baut den Baum auf, in dem 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% aller Fälle 0 ist
und zu 25% gleich 1 (Abbildung 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
beträgt die Entropie der ersten Teilmenge gleich Null (das Ergebnis ist
in jedem Fall 0, also sicher) und die der zweiten weiterhin 0.56, also
ist die Gesamtentropie
1/2*0 + 1/2*0.56 = 0.28
Mit nur einem Knoten im Baum hat also 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%iger Wahrscheinlichkeit fehlerfrei voraussagen.
Wie gesagt ist dies im vorliegenden Fall höchstens von akademischem Interesse, denn ein Und-Gatter lässt sich ganz 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, anschließend das Verhalten des ihm unbekannten Systems imitiert, hat gewaltiges Potential. Als Bonus unterstützt er sogar eigentlich nicht erlaubte Eingabewerte wie [0.9,0.8], die er in sinnvolle Ergebnisse (in diesem Fall 1) umgießt.
Als praktische KI-Anwendung soll nun ein Entscheidungsbaum anhand von Fahrdaten aus dem Auto ermitteln, wer bei der jeweiligen Fahrt am Steuer saß. Wie schon im letzten Snapshot ([5]) habe ich auch diesmal echte Daten aus den Automatic-Adaptern ([6]) meiner beiden Autos aufbereitet, die minutiös festhalten, wann, wo, und wie schnell die Fahrzeuge gefahren sind. Leider weiß der Adapter nicht, wer der aktuelle Fahrer war, und da meine Frau und ich abwechselnd mit zwei Autos fahren, soll die lernfähige Maschine nun mittels einiger von Hand mit dem Fahrerkürzel ("M" oder "A") ergänzten Tripdaten in Listing 2 eventuell vorhandene Kriterien erlernen, um anschließend bei neu vorliegenden Tripdaten 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 einen 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). Letzterer wird eher selten von meiner Frau gelenkt, die
andererseits häufig unter der Woche mit "Brummi" zur Arbeit fährt (dow=1-5),
während ich eher am Wochenende (dow=6-7) spazierenfahre.
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. Hartes Bremsen oder Gasgeben
("brakes" und "accels") scheinen in etwa gleichverteilt. Reichen diese
Kriterien mit den von Hand ergänzten Fahrern aus, um dem System
beizubringen, bei neuen Trips den Fahrer richtig zu erraten?
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] ) )
 |
| Abbildung 5: Nach der Lernphase identifiziert der Entscheidungsbaum Autofahrer am Fahrverhalten. |
Listing 3 liest die CSV-Datei von der Festplatte in einen Pandas-Dataframe
ein. Die Liste Y erhält die Einträge in der Spalte driver die zu
Lehrzwecken von Hand mit "M" oder "A" ergänzt wurden als gewünschte
Ergebnisse. In X steht ab Zeile 9 eine zweidimensionale Liste, in der
reihenweise Tripdaten stehen, die jeweils 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.
Wie in der vorausgegangenen Theorievorlesung kommt auch in Listing 3
wieder 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 5
bei zwei neuen Trip-Records, deren
Kilometerstand von 2000 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 nach
tiefschürfender Analyse festgestellt, dass dies das wesentliche
Unterscheidungsmerkmal der beiden Fahrer ist. Als erster Ansatz bringt
das Verfahren ganz ordentliche Ergebnisse, wie zuverlässig diese sind,
werden weitere Testdaten zeigen. Falls Verbesserungsbedarf besteht,
helfen mehr Trainingsdaten, einen besseren Entscheidungsbaum zu bauen.
Listings zu diesem Artikel: http://www.linux-magazin.de/static/listings/magazin/2017/08/snapshot/
"Python: Data Analytics and Visualization", Kirthi Raman, Ashish Kumar, Martin Czygan Phuong Vo.T.H, Packt Publishing 2017
Prateek Joshi, "Artificial Intelligence with Python", 2017, Packt Publishing
Michael Schilli, "Auf heißer Spur": Linux-Magazin 07/17, S.XXX, <U>http://www.linux-magazin.de/Ausgaben/2017/07/Snapshot
Michael Schilli, "Wege zum Connected Car": Linux-Magazin 10/16, S.84, http://www.linux-magazin.de/Ausgaben/2016/10/Perl-Snapshot
 |
Michael Schilliarbeitet als Software-Engineer in der San Francisco Bay Area in Kalifornien. In seiner seit 1997 laufenden Kolumne forscht er jeden Monat nach praktischen Anwendungen verschiedener Programmiersprachen. Unter mschilli@perlmeister.com beantwortet er gerne Ihre Fragen. |