Open Source im professionellen Einsatz
Linux-Magazin 08/2017
© Iurii Konoval, 123RF

© Iurii Konoval, 123RF

KI lernt mit Entscheidungsbäumen

Ross nennt Reiter

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.

886

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.

Online PLUS

Im Screencast demonstriert Michael Schilli das Beispiel: http://www.linux-magazin.de/Ausgaben/2017/08/plus

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 »« 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.

Tabelle 1

Und-Verknüpfung von x/y

Input

 

Output

x

y

x und y

0

0

0

0

1

0

1

0

0

1

1

1

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 »« 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.

Listing 1

decision-tree.py

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  »« 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.

Diesen Artikel als PDF kaufen

Express-Kauf als PDF

Umfang: 3 Heftseiten

Preis € 0,99
(inkl. 19% MwSt.)

Linux-Magazin kaufen

Einzelne Ausgabe
 
Abonnements
 
TABLET & SMARTPHONE APPS
Bald erhältlich
Get it on Google Play

Deutschland

Ähnliche Artikel

  • Video zum Snapshot 08/2017

    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.

  • Perl-Snapshot

    Ein in den Diagnose-Port von Michael Schillis Auto(s) gestöpselter Stecker sendet an das mitreisende Mobiltelefon per Bluetooth aktuelle Informationen wie Geschwindigkeit, Beschleunigung, Benzinverbrauch. Eine App und ein programmierbares API lesen die Daten aus und stellen sie ansprechend dar.

  • Snapshot

    Anhand von Trainingsdaten in Form von täglich im Auto erfassten Kilometerständen versucht Michael Schillis KI-Programm Muster im Fahrverhalten zu erkennen und Prognosen abzugeben.

  • Perl-Snapshot

    Der Projekthoster Github beherbergt nicht nur die Code-Repositories vieler bekannter Open-Source-Projekte, sondern bietet auch ein durchdachtes API an, mit dem sich in ihnen herrlich herumschnüffeln lässt.

comments powered by Disqus

Ausgabe 09/2017

Artikelserien und interessante Workshops aus dem Magazin können Sie hier als Bundle erwerben.