Ein Partyknüller bei IT-Nerds ist das Ziegenproblem schon lange nicht mehr, aber dennoch eine lohnende Jungfernfahrt für angehende Statistiker. Im Rahmen der KI-Reihe des Snapshots stellt sich heute die Frage, ob ein zunächst unbedarftes neuronales Netzwerk die Lösung der Aufgabe aus einigen Trainingsläufen erlernen kann. Wie ging das Problem nochmal?
In einer Spielshow darf ein Kandidat zwischen drei verschlossenen Türen wählen, hinter denen ein Auto als Hauptpreis, eine Ziege, und noch eine Ziege warten. Der Kandidat entscheidet sich für eine Tür, der Moderator öffnet eine andere, hinter der eine Ziege meckert. Wie kommt der Kandidat am ehesten zum Hauptpreis, indem er seine Wahl beibehält oder zur noch verbleibenden geschlossenen Tür wechselt?
| |
| Abbildung 1: Ziegenproblem auf Wikipedia |
Wie man auf [2] oder [3] oder [4] nachlesen kann, lohnt es sich für den Kandidaten, zu wechseln, denn damit verdoppelt er seine Gewinnchancen. Doch wie lernt ein neuronales Netzwerk die optimale Spielstrategie aus Belohnung bei Gewinnen und Bestrafung bei Verlusten?
Als erstes gilt es, wie bei allen Aufgaben im Machine-Learning, die Ein- und Ausgabedaten fachgerecht hinzubiegen, denn ein KI-System ist kein Hexenkessel, in den man Probleme hineinwirft und aus dem dann wie durch ein Wunder Lösungen heraussprudeln. Vielmehr lösen KI-Algorithmen nur eine kleine Zahl sehr präzise definierter Probleme.
Zur Lösung der Aufgage nutzt der verwendete Algorithmus ein mehrschichtiges neuronales Netzwerk nach Abbildung 2, das drei Eingabeparameter erwartet: Als erstes die Tür, die der Kandidat ausgewählt hat, als zweites die Tür, die der Moderator daraufhin geöffnet hat, und als drittes die noch verbleibende verschlossene Tür.
 |
| Abbildung 2: Ein mehrschichtiges neuronales Netzwerk lernt aus alten Spielshows mit ausgewählten Türen und dem dann gefundenen Preis, um in der Testphase später selbständig die beste Tür zu wählen. |
In der mittleren, verborgenen Schicht ist jedes künstliche Neuron mit jedem Eingangsneuron der ersten Schicht verborgen. Auch wenn ein neuronales Netzwerk nicht ganz wie ein menschliches Gehirn arbeitet, kann man diese massenhaften Verknüpfungen doch als Abbild menschlichen Designs auslegen. Jedes der inneren Neuronen der verdeckten Schicht feuert wiederum Impulse an alle Neuronen der Ausgangsschicht, in Abbildung 2 ist mit nur einem Ausgangsneuron ein vereinfachter Fall.
In der Trainingsphase soll das Netzwerk aus alten Spielshows eine Strategie lernen, um abhängig von der aktuellen Türenkonstellation die Tür mit dem Preis auf dem Ausgabeneuron vorherzusagen. Während ein paar tausend Durchgängen speist das Skript dem KI-System jeweils die drei Eingangsparameter ein und vergleicht den am Ausgang anliegenden Wert mit der Tür, die in der Gameshow den Hauptpreis enthüllt hat. Hat das System die Tür richtig vorhergesagt, wird es belohnt. Liegt es falsch, muss es über einen Feedback-Mechanismus die Parameter seiner Neuronen anpassen.
Die Trainingsdurchgänge nennt man im KI-Fachjargon "Episodes". Oft ist es hilfreich, die Neuronenparameter nicht gleich bei jedem Datensatz anzupassen, sondern erst nach einem sogenannten "Batch" von Eingangswerten. Das spart Rechenzeit, und verhindert, dass das System ungebremst die Gewichte herumwuchtet, sich aufschaukelt, und dann am Ende keine Lösung findet.
Listing 1 zeichnet die Ergebnisse von 1000 Spielshows auf, indem es jeweils den Preis hinter eine zufällige Tür stellt, dann den Moderator eine im Rahmen der Spielregeln zufällige Tür öffnen lässt, die weder bereits offen ist noch den Hauptpreis enthält, und gibt das Ergebnis im CSV-Format aus (Abbildung 3). Die Türen numeriert es von 0 bis 2 durch, und stellt pro Zeile den Index der folgenden vier Türen dar: Die vom Spielshow-Kandidaten ausgewählte Tür, die Tür, die der Moderator daraufhin öffnet, die verbleibende Tür, und die Tür, hinter der sich der Preis befindet.
Stößt das neuronale Netzwerk später zum Beispiel einmal auf die Kombination [1,2,0,0] in der ersten Zeile von Abbildung 3, weiß es, dass der Kandidat die zweite Tür ausgewählt hat (Index 1), der Moderator daraufhin die dritte geöffnet hat (Index 2), und somit die erste noch geschlossen ist (Index 0). Hinter der ersten Tür steht in diesem Beispiel auch der Hauptpreis, sodass sich das neuronale Netzwerk für die erste Tür entscheiden sollte.
 |
| Abbildung 3: Ein Zufallsgenerator erzeugt Ausgänge von Spielshows und gibt sie im CSV-Format aus, zum späteren Trainieren des neuronalen Netzwerks. |
01 #!/usr/bin/env python3
02 from random import shuffle, randrange
03
04 class Door(object):
05 def __init__(self,prize):
06 self.prize = prize
07
08 class Show(object):
09 def __init__(self):
10 self.picked = None
11 self.revealed = None
12 self.alternate = None
13
14 # hide prize behind random door
15 self.prizes = [1,0,0]
16 shuffle(self.prizes)
17
18 self.doors = []
19 for prize in self.prizes:
20 self.doors.append(Door(prize))
21
22 def pick(self):
23 # candidate picks a door
24 idx = randrange(0,len(self.doors))
25 self.picked = idx
26
27 def reveal(self):
28 # moderator reveals another door
29 for idx,door in \
30 enumerate(self.doors):
31 if door.prize or \
32 self.picked == idx:
33 continue
34 if self.revealed is None:
35 self.revealed = idx
36 # determine remaining door
37 for idx,door in \
38 enumerate(self.doors):
39 if self.picked != idx and \
40 self.revealed != idx:
41 self.alternate = idx
42
43 def prize_idx (self):
44 for idx,door in \
45 enumerate(self.doors):
46 if door.prize:
47 return idx
48
49 print("picked,revealed,alternate,prize");
50
51 for i in range(1000):
52 show = Show()
53 show.pick()
54 show.reveal()
55
56 print("{0},{1},{2},{3}".format(
57 show.picked, show.revealed,
58 show.alternate,show.prize_idx()))
Dabei definiert es zwei Klassen, Door für einzelne Türen und Show
für alle drei Türen mit den Spielregeln der Fernsehsendung. Door-Objekte
werden entweder mit oder ohne Hauptpreis initialisiert, Zeile 15 platziert
den Preis hinter der ersten Tür und lässt dann Zeile 16 die Türen durchmischen,
sodass der Preis zufällig irgendwo landet. Mit der Methode pick() ab Zeile
22 wählt der Kandidat mittels randrange() eine zufällige Tür, deren
Index sich das Objekt in der Instanzvariablen picked merkt.
Der Moderator muss anschließend in reveal() ab Zeile 27 eine weitere Tür
öffnen, darf damit aber nicht den Hauptgewinn preisgeben. Im Attribut
revealed speichert das Objekt den Index dieser Tür. Bleibt noch die letzte
Tür, deren Index die Methode im Attribut alternate ablegt. Ab Zeile 51
startet die for-Schleife mit 1000 Spielshows, und für jede legt die
print()-Anweisung ab Zeile 56 Eckdaten im CSV-Format ab. Dort stehen dann zeilenweise
für jede Show die Indices der Kandidatentür, der Moderatortür, der
verbleibenden Tür, sowie der Tür, hinter der der Hauptgewinn lungert.
Traktiert der KI-Lehrling ein neuronales Netzwerk mit diesen 3-er
Eingangstupeln mit jeweils einem 1-er Ergebnistupel in der Trainingsphase,
wird allerdings kein Schuh daraus. Die Indices sind auch weniger als
Zahlenwerte relevant, sie stehen vielmehr für Kategorien, von denen
jede Tür eine andere repräsentiert. Solche Datensätze formt der KI-Fachmann
vor dem Training mit sogenanntem One-Hot-Encoding um. Besteht
ein Datensatz aus N Kategorien, formt der Kodierer daraus N-Tupel, in denen
jeweils ein Element auf 1 gesetzt ist, und die sonst aus Nullen bestehen.
Abbildung 4 zeigt als Beispiel, wie der Tupel [2,1,2,0,1,0] in sechs
one-hot-kodierte Matrixreihen umgeformt wird. Der Code in Listing 2
nutzt dazu die Funktion to_categorical() aus dem Fundus np_utils
des Pakets keras.utils. Um von der One-Hot-Kodierung wieder zurück zum
ursprünglichen Wert zu gelangen, dient die Methode argmax(), die
jeder Numpy-Array bereitstellt.
 |
| Abbildung 4: Die One-Hot-Kodierung wandelt numerische Werte in Kategorien um, die jeweils einen Wert pro Kategorie-Tupel auf 1 setzen. |
01 #!/usr/bin/env python3
02
03 from keras.utils import np_utils
04 import numpy
05
06 X = numpy.array([2,1,2,0,1,0])
07 print("org=", X)
08
09 onehot=np_utils.to_categorical(X)
10 print("onehot=", onehot)
11
12 a=onehot.argmax(1)
13 print("reverse=", a)
Mit den Eingabewerten im One-Hot-Format lernt nun das in Listing 3 definierte dreischichtiges neuronale Netzwerk wie ein Einserschüler. Wichtig: Auch die Ausgabewerte kodiert das Netzwerk nun nach der One-Hot-Methode und benötigt dadurch jetzt nicht ein Neuron für die Ausgabe, sondern gleich drei, da sowohl die Trainings- als auch später die vorhergesagten Werte als 3er-Tupel mit gesetzen Einsen vorliegen, wobei jede Kombination eine bestimmte Tür der Spielshow anzeigt.
01 #!/usr/bin/env python3
02 from keras.models import Sequential
03 from keras.layers import Dense
04 from keras.utils import np_utils
05 import numpy
06
07 data = numpy.loadtxt("shows.csv",
08 delimiter=",", skiprows=1)
09 X = data[:,0:3]
10 Y = data[:,3]
11
12 categories=np_utils.to_categorical(Y)
13
14 model = Sequential()
15 model.add(Dense(10, input_dim=3,
16 activation='relu'))
17 model.add(Dense(3, activation='relu'))
18 model.add(Dense(3, activation='sigmoid'))
19
20 model.compile(loss='binary_crossentropy',
21 optimizer='adam')
22 model.fit(X, categories, epochs=100,
23 batch_size=100, verbose=0)
24
25 test_data = numpy.array(
26 [[0,1,2], [0,2,1], [1,0,2],
27 [1,2,0], [2,0,1], [2,1,0]
28 ])
29
30 pred = model.predict(test_data)
31
32 for (idx,row) in enumerate(test_data):
33 print(row, pred[idx].argmax())
Liegen die von Listing 1 erzeugten Trainingsdaten in der Datei shows.csv,
liest Listing 3 diese in Zeile 12 wieder von der Platte. Die ersten drei
Elemente jeder Zeile sind die Eingangsdaten des Netzwerks (Kandidatentür,
Moderatortür, alternative Tür), und das letzte gibt den Index der Tür
mit dem Hauptpreis, also das gewünschte Ergebnis, an.
Zeile 16 transformiert die gewünschten Ausgabewerte in Kategorien in
der One-Hot-Kodierung und die Zeilen 18-21 bauen das neuronale Netzwerk
mit einer Eingangsschicht, einer verdeckten Schicht und einer Ausgabeschicht
auf. Alle Layer sind vom Typ Dense, also mit allen Elementen angrenzender
Schichten gehirnartig vernetzt. Die Klasse Sequential des Keras-Pakets
hält die Schichten zusammen. Zeile 23 kompiliert das Netzwerk-Modell,
wobei Listing 3 als Lernparameter die Fehlerfunktion als
binary_crossentropy angibt, und als Optimizer den Algorithmus "adam" wählt.
Im dreischichtige Modell nehmen in der Eingangsschicht 10 Neuronen die
Eingabedaten entgegen, die Datenbreite legt input_dim=3 auf drei fest,
da es sich um 3er-Tupel (jeweils Daten von drei Türen) handelt.
Der mittlere Layer hat drei Neuronen,
und der Ausgabe-Layer nochmals drei, letzteres ist wie vorher erwähnt
der One-hot-Kodierung der Ergebnisse als Kategorien geschuldet.
Die Trainingsphase bricht in Zeile 22 mit dem Aufruf von model.fit() an.
Sie definiert 100 Durchgänge (epochs) und erst nach der Batchgröße von
100 Trainingswerten soll das neuronale Netzwerk seine Gewichte mit den
gesammelten Informationen anpassen.
Ob das Training von Erfolg gekrönt war oder nicht, zeigt ab Zeile 25 das Licht
(Michael Schanze möge verzeihen): Für alle möglichen Türkombinationen weist
Zeile 30 die Methode predict() an, die zu wählende Tür vorzuschlagen.
Und, siehe da, Abbildung 5 zeigt tatsächlich, dass Kollege Computer jedes
Mal die alternative Tür wählt, also den Kandidaten wechseln lässt, um,
wie auch der mathematische Beweis zeigt, die Gewinnwahrscheinlichkeit
zu maximieren.
 |
| Abbildung 5: Das neuronale Netzwerk hat gelernt, dass die Alternativ-Tųür (rechteste Spalte) die lukrativste zum Gewinnen des Hauptpreises ist. |
Das ist bemerkenswert, denn weder weiß das Netzwerk um die mathematischen
Zusammenhänge, sondern richtet sich nur nach empirisch ermittelten Daten.
Außerdem sind die Eingabedaten keineswegs eindeutig, denn die Wechselmethode
führt nur in 2/3 aller Fälle zum Erfolg. Trickst man bei den Eingangsdaten und
versteckt den Preis jedesmal hinter der Wechseltür, misst der interne
Erfolgszähler genau 100%, dann ist sich das Netzwerk absolut sicher. Sind, wie
im vorliegenden Fall, die Daten nicht eindeutig und verliert der Kandidat mit
der Wechselmethode in 1/3 aller Fälle, optimiert das Netzwerk anscheinend die
Strategie, könnte aber auch leicht danebenliegen. Variiert man die Parameter
des Netzwerks etwas, wie zum Beispiel die Anzahl der Durchgänge oder der
Neuronen, kommen auch teilweise etwas ungenauere Ergebnisse zutage. Wie immer
in der KI gilt: Probieren geht über Studieren, aber anschließend sollte man das
Modell schon noch mit Hilfe der von Keras bereitgestellten metrics-Parameter
verifizieren.
Listings zu diesem Artikel: http://www.linux-magazin.de/static/listings/magazin/2017/11/snapshot/
Michael Schilli, "Eine Ziege, wahrscheinlich": Linux-Magazin 14/07, S.XXX, <U>http://www.linux-magazin.de/Ausgaben/2014/07/Perl-Snapshot
Michael Schilli, "Ziegenproblem": Linux-Magazin 09/99, S.XXX, (Online-Version auf linux-magazin.de leider verschollen)
Wikipedia, "Ziegenproblem", https://de.wikipedia.org/wiki/Ziegenproblem
"Deep Learning with Python", Jason Brownlee, Machine Learning Mastery, 2017
 |
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. |