© Olga Bosnak, 123RF

Das aus Gameshows bekannte Ziegenproblem kann eine lohnende Jungfernfahrt für angehende Statistiker sein. Lässt sich die Wahlentscheidung zwischen Ziegen und Auto mit einem neuronalen Netzwerk und einigen Trainingsläufen erlernen? KI-Meister Mike Schilli probiert es aus.

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 (Abbildung 1). Der Kandidat entscheidet sich zunächst für eine Tür, der Moderator öffnet eine andere, hinter der eine Ziege meckert. Wie kommt der Kandidat am wahrscheinlichsten 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] 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?

Vorbild Mensch

Zunächst gilt es – wie immer beim Machine Learning – die Ein- und Ausgabedaten fachgerecht hinzubiegen. Ein KI-System ist ja kein Hexenkessel, in den man die Probleme irgendwie hineinwirft und aus dem anschließend fertige Lösungen einfach heraussprudeln. Vielmehr lösen KI-Algorithmen nur eine kleine Zahl präzise definierter Probleme.

Zur Lösung der Aufgabe nutzt der verwendete Algorithmus ein mehrschichtiges neuronales Netzwerk, das drei Eingabeparameter erwartet: Erstens die Tür, die der Kandidat ausgewählt hat, zweitens die Tür, die der Moderator daraufhin geöffnet hat, und drittens schließlich die noch verbleibende verschlossene Tür.

In der mittleren, verborgenen Schicht ist jedes künstliche Neuron mit jedem Eingangsneuron der ersten Schicht verbunden. 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 ab.

Zuckerbrot und Peitsche

In der Trainingsphase soll das Netzwerk aus alten Spielshows eine Strategie lernen, um abhängig von der aktuellen Türenkonstellation jene mit dem Preis auf dem Ausgabeneuron vorherzusagen. In einigen 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 zum Auto führt. Hat das System die richtige Tür vorhergesagt, wird es belohnt. Liegt es falsch, muss es über einen Feedback-Mechanismus die Parameter seiner Neuronen anpassen.

Die Trainingsläufe nennt man im KI-Fachjargon Episodes. Oft ist es hilfreich, die Neuronenparameter nicht gleich bei jedem Datensatz anzupassen, sondern erst nach einem so genannten Batch von Eingangswerten. Das spart Rechenzeit und verhindert, dass das System ungebremst die Gewichte herumwuchtet, sich aufschaukelt und keine Lösung findet.

1000 Shows aufgezeichnet

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 Tür öffnen lässt, die weder bereits offen ist noch den Hauptpreis enthält, und gibt das Ergebnis im CSV-Format aus (Abbildung 2). Die Türen nummeriert es von 0 bis 2 durch und stellt pro Zeile den Index der folgenden Türen dar: Die vom Spielshow-Kandidaten ausgewählte Tür, die Tür, die der Moderator daraufhin öffnet, die verbleibende Tür sowie jene, hinter der sich der Preis befindet.

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()))

Stößt das neuronale Netzwerk zum Beispiel einmal auf die Kombination [1,2,0,0] wie in der ersten Zeile von Abbildung 2, weiß es, dass der Kandidat die zweite Tür ausgewählt hat (Index 1), der Moderator daraufhin die dritte geöffnet hat (Index 2), dass also die erste noch geschlossen ist (Index 0). Hinter der ersten Tür steht hier der Hauptpreis, sodass sich das neuronale Netzwerk für die erste Tür entscheiden sollte.

Abbildung 2: Ein Zufallsgenerator erzeugt Ausgänge von Spielshows und gibt sie im CSV-Format aus – für das spätere Trainieren des neuronalen Netzwerks.

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.

Moderator in der Bredouille

Der Moderator muss dann in »reveal()« ab Zeile 27 eine weitere Tür öffnen, darf 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, 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 zum Gewinn.

One-hot-Encoding

Traktiert der KI-Lehrling ein neuronales Netzwerk mit diesen 3er-Eingangstupeln mit jeweils einem 1er-Ergebnistupel in der Trainingsphase, wird 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 so genanntem 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, sonst bestehen sie aus Nullen.

Abbildung 3 zeigt als Beispiel, wie das 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.

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)

Maschine lernt

Mit den Eingabewerten im One-hot-Format lernt nun das in Listing 3 definierte dreischichtige neuronale Netzwerk. Wichtig: Auch die Ausgabewerte kodiert das Netzwerk nun nach der One-hot-Methode und benötigt daher 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 gesetzten 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 7 wieder von der Platte aus. 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 zum Hauptpreis an.

Abbildung 3: One-hot wandelt Werte in Kategorien um, die einen Wert pro Tupel auf 1 setzen.

Zeile 16 transformiert die gewünschten Ausgabewerte in Kategorien in der One-hot-Kodierung, die Zeilen 14 bis 18 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 20 kompiliert das Netzwerkmodell, wobei Listing 3 als Lernparameter die Fehlerfunktion als »binary_crossentropy« angibt und als Optimizer den Algorithmus »adam« wählt.

Im dreischichtigen Modell nehmen in der Eingangsschicht zehn Neuronen die Eingabedaten entgegen, die Datenbreite legt »input_dim=3« auf 3 fest, da es sich um 3er-Tupel (jeweils Daten von drei Türen) handelt. Der mittlere Layer hat drei Neuronen, der Ausgabe-Layer nochmals drei, Letzteres ist wie erwähnt der One-hot-Kodierung der Ergebnisse als Kategorien geschuldet.

Nagelprobe

Die Trainingsphase startet in Zeile 22 mit dem Aufruf von »model.fit()«. 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 sich ab Zeile 25: 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 4 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 4: Das Netzwerk hat gelernt, dass die Alternativ-Tür die lukrativste zum Gewinnen ist.

Das ist bemerkenswert, denn das Netzwerk kennt die mathematischen Zusammenhänge nicht, sondern richtet sich nur nach empirisch ermittelten Daten. Auch sind die Eingabedaten keineswegs eindeutig, denn die Wechselmethode führt nur in zwei Drittel aller Fälle zum Erfolg. Trickst man bei den Eingangsdaten und versteckt den Preis jedes Mal hinter der Wechseltür, misst der interne Erfolgszähler genau 100 Prozent, dann ist sich das Netzwerk absolut sicher.

Sind die Daten nicht eindeutig und verliert der Kandidat mit der Wechselmethode in einem Drittel aller Fälle, optimiert das Netzwerk anscheinend die Strategie, könnte aber auch leicht irren. Variiert man die Parameter des Netzwerks, etwa die Anzahl der Durchgänge oder der Neuronen, kommen teilweise ungenauere Ergebnisse zutage.