KI: Fast alles, was ich darüber weiß (Teil 4: Das Eleusis-Experiment)

Bevor ich zum letzten Teil komme, der an Teil 3 anschließt, hier ein kleiner Exkurs. Kann man getrost überspringen, ich habe mich aber darin verloren.

Das Kartenspiel Eleusis

Wenn ich schon eine KI zur Verfügung hatte, dann wollte ich sie auch mit etwas testen, das zumindest so aussieht, als würde es Intelligenz erfordern: Mir fiel das Spiel Eleusis ein (alter Blogeintrag). Gespielt wird mit mindestens zwei Sätzen herkömmlicher Spielkarten: Herz, Karo, Kreuz, Pik; Ass bis König. Die Kurzfassung: Eine Spielerin überlegt sich eine geheime Ablageregel, die anderen Spielerinnen müssen durch Versuch und Irrtum auf die Regel kommen – genauer gesagt, sie müssen ihre Karten loswerden, und da hilft es, Vermutungen über die Regel anzustellen. Für das Entdecken der Regel hat man etwa 30 Versuche lang Zeit.

Theoretisch kann die Regel beliebig kompliziert sein, praktisch und gerade bei Anfängerinnen wird sie ein Format haben wie:

  • Nach einer niedrigen Karte (A‑7) spiele eine hohe, nach einer hohen (7‑K) eine niedrige.
  • Nach einer roten Karte (Herz, Karo) spiele eine niedrige, nach einer schwarzen eine hohe.
  • Nach einer geraden Karte (2, 4, 6, 8, 10, Dame) spiele rot.
  • Nach einer Karte spiele eine weitere Karte mit dem gleichen Farbwert oder dem gleichen Zahlenwert.

Die letzte Regel ist die Regel, die auch beim Mau-Mau-Kartenspiel gilt.

Erste Erkenntnisse

Ich arbeite ab jetzt erst einmal mit dieser Mau-Mau-Regel. Dazu erstelle ich Kartenpaare, und wenn die zweite Karte laut Mau-Mau-Regel auf die erste folgen darf, soll das ein gültiges Paar sein, sonst nicht. Ich kann mein neuronales Netz, das nur eine einzige versteckte Schicht hat, mit einem Satz von 35 zufällig ausgewählten Kartenpaaren – die Anzahl entspricht ungefähr dem Schwierigkeitsgrad beim Spiel unter Menschen – so lange trainieren, bis diese 35 Paare alle korrekt als gültig beziehungsweise nicht gültig identifiziert werden. Das heißt, das neuronale Netz hat eine Funktion gefunden (=ist so eingestellt), die perfekt auf die vorhandenen Karten passt. Es hat sozusagen eine Regel aufgestellt, die zu den Daten passt.

Wenn ich diesem Netz dann allerdings weitere zufällige Kartenpaare zur Überprüfung vorsetze, hat es nur eine Trefferquote von (Stichproben) 67% – 89%. Das ist immer noch besser als geraten, da bestünde eine Trefferquote von 30%.

Was ist da passiert? Offensichtlich sind 35 Kartenpaare zu wenig, als dass das Netz perfekt auf die Mau-Mau-Regel trainiert werden könnte. Und zwar ziemlich unabhängig davon, ob das Netz 100 oder nur 6 Knoten in der versteckten Schicht enthält.

Frage 1: Wenn das Netz nicht die tatsächliche Mau-Mau-Regel gefunden hat, sondern eine andere Regel, die aber eben auch auf die 35 Kombinationen, passt – was ist das dann für eine Regel? Hat sie Ähnlichkeit mit der tatsächlich gesuchten Regel? – Vermutlich schon, sonst käme man nicht auf die relativ hohe Trefferquote. Vermutlich denkt der Rechner da zu kompliziert: Das kann man auch bei menschlichen Eleusis-Spielern beobachten, die teilweise sehr elaborierte Regeln aufstellen, um dem ihnen vorliegenden Datenmaterial gerecht zu werden – und dabei übersehen, dass es eine auch viel einfachere Regel gibt, die die Daten ebenso vollständig erklärt. Bei menschlichen Regelgebern ist die einfachere Regel dann auch meist die passendere – der Rechner hat erst einmal keinen Grund, davon auszugehen.

(Fußnote, weil Informatikstoff 9. Klasse: Es handelt sich bei einer Eleusis-Regel um eine Zuordnung, eine Relation: Jeder Karte sind eine oder mehrere andere Karten zugeordnet, die auf sie folgen dürfen. Die Regel ist also eine Zuordnungsvorschrift, und man könnte sie als Diagramm mit zwei Mengen zu jeweils 52 Kartenelementen und vielen Pfeilen dazwischen visualisieren. Bei menschlichen Spielern hat diese Zuordnungsvorschrift wohl meist eine Aussageform, das heißt, sie lässt sich knapp formulieren, in eine Formel packen. “Wenn, dann…” Theoretisch könnte diese Zuordnungsvorschrift auch völlig willkürlich sein, so dass es keine Aussageform gibt, sondern man zur Beschreibung der Zuordnungsvorschrift einfach alle Fälle einzeln nennen muss.)

Wenn ich mit mehr als 35 Kartenpaaren trainiere, kriege ich bessere Ergebnisse. Wenn ich mit 4000 zufälligen Kartenpaaren trainiere, kriege ich 100% richtig identifizierte Paare. Kunststück: Es gibt nur 52*52 Kartenkombinationen, also 2704. Wenn das Netz die alle durchprobiert, dann weiß es, was geht und was nicht geht. Dazu brauche ich dann aber keine KI.

Frage 2: Wie viele Knoten muss mein Netz haben, um jede beliebige Eleusisregel erkennen zu können? Puh. Es gibt ziemlich viele potenzielle Regeln: 52 * 252 – jeder der 52 Karten kann eine beliebige Teilmenge aller Karten zugeordnet werde, und die Menge aller Teilmengen heißt Potenzmenge und enthält hier eben 252 Elemente. Andererseits – es gibt nur 2704 Kombinationen, die man ausprobieren muss.

Frage 3: Wie viele Knoten in der versteckten Schicht muss mein Netz mindestens haben, um die Mau-Mau-Regel perfekt abbilden zu können? Dazu trainiere ich das Netz natürlich mit ausreichend vielen, also allen möglichen Kombinationen, klar. Die Antwort lautet, abhängig von ein paar Sachen: vier oder fünf. Kann ich diesen Neuronen dann ablesen, was sie bedeuten? Also sehen, was sich das Netz quasi dabei gedacht hat, sie so einzustellen? Und: ähnelt das Netzvorgehen dem, wie ich das als Mensch machen würde? Zumindest die Antwort auf diese Fragen kann ich versuchen.

Die Mau-Mau-Regel manuell erstellt

Dazu habe ich mir erst einmal überlegt, wie ich als Mensch die Mau-Mau-Regel angehen würde, und mir dann ein Perzeptron bauen, dass genau diese Regel abbildet:

In das Perzeptron gehen vier Werte hinein: Die ersten beiden stehen für die erste Karte, die letzten beiden für die auf sie folgende Karte. Die Werte 0.0, 0.25, 0.5, 0.75 stehen für die vier verschiedenen Farben, die Werte 0/13, 1/13, 2/13… 12/13 stehen für die dreizehn verschiedenen Werte. Hätte ich das anders kodieren können? Ja, wahrscheinlich, dazu später mehr.

Das oberste Neuron überprüft, ob die erste Karte einen höheren Farbwert als die zweite oder den gleichen hat. Das zweite Neuron überprüft, ob die zweite Karte einen niedrigeren Farbwert oder den gleichen hat. Das Neuron rechts oben überprüft, ob diese beiden Neuronen beide mit hohem Wert reagieren, es ist ein AND-Neuron: Wenn der zweite Farbwert sowohl größer gleich als auch kleiner gleich ist, müssen die Farbwerte gleich sein.

Analog überprüfen die beiden Neuronen links unten den Zahlenwert, und das Neuron rechts unten, ob beide wahr/0.99 ausgeben; es ist wieder ein AND-Neuron.

Was nicht dargestellt ist, ist das siebte Neuron in einer dritten Schicht, der eigentlichen Ausgabeschicht vor den zwei versteckten: Das verbindet die beiden letzten Neuronen mit einem ODER-Neuron – es reicht ja, wenn Farbe oder Wert gleich sind. Mein Programm hat aber keinen Platz mehr für die Darstellung dieser letzten Schicht.

Als Mensch habe ich also 2 versteckte Schichten und insgesamt 7 Neuronen (mit dem Ergebnisneuron) gebraucht. Wie geht der Rechner vor, der erst einmal nur mit 1 versteckten Schicht arbeiten soll?

Die Mau-Mau-Regel des Netzes mit 5 oder 4 Neuronen (hard limit)

Beim ersten Versuch stellte ich dem Netz sechs Neuronen zur Verfügung. Am Ergebnis sah ich, dass eines davon überflüssig war und für das Ergebnis keine Rolle spielte. Das strich ich dann, sortierte die Reihenfolge der Neuronen etwas um und glättete die Werte, so dass sie dem menschlichen Auge liebreizender sein würden:

Die Funktion der Neuronen war leicht auszumachen: Das erste Neuron überprüft, ob die Farbe der ersten Karte kleiner als die der zweiten ist, das zweite, ob sie größer ist. Daraus kann das Ausgabeneuron entscheiden, ob der Wert gleich ist. Das dritte Neuron überprüft, ob der Wert der ersten Karte kleiner als der der zweien ist, das vierte, ob der Werter kleiner oder gleich ist. Warum hier nicht analog mit kleiner oder größer? Entweder Zufall oder Mathematik, ich müsste nachdenken. Das fünfte Neuron ist deshalb da, weil alle anderen Neuronen jenseits ihrer eigentlichen Funktion auch noch stets ein doppeltes Herz Ass passieren lassen, und das verwirrt dann das Ausgabeneuron, deshalb muss das durch dieses fünfte Neuron, das nur für die doppelte Herz Ass da ist, wieder entwirrt werden.

Das liegt daran, weil ich Herz und Ass jeweils mit 0 kodiert habe. (Zur Kodierung siehe weiter unten.) Wenn ich stattdessen die Farben als 0.01, 0.26, 0.51 und 0.76 kodiere, und auch zu den Zahlenwerten jeweils 0.01 addiere, reichen mir schon 4 Neuronen:

Die Mau-Mau-Regel des Netzes mit 5 Neuronen (sigmoid)

Das gilt alles nur für die Hard-limit-Aktivierungsfunktion. Das ist die, bei der die Neuronen der linken Schicht entweder 0.01 oder 0.99 ausgeben und nichts dazwischen. Mit einer sigmoiden Aktivierungsfunktion, die eher kleine und große, aber auch schon mal mittlere Werte durchlässt, brauche ich 5 Neuronen, egal ob mit 0.01 oder 0.0 für Herz bzw. Ass:

Was die Neuronen bewirken und wie man sie eleganter runden kann… uh, bleibt der Leserin als häusliche Aufgabe überlassen… heißt: weiß nicht so recht.

Mit 4 Neuronen und Sigmoid-Funktion ist mit die Aufgabe übrigens nicht gelungen.

Eine Karte identifizieren

Um die Karte, die intern mit (0.75, 5/13) kodiert ist, zu identifizieren, brauche ich 3 versteckte Neuronen (mit Sigmoid-Funktion). Ein paar Werte konnte ich schön runden, andere nicht. Die ersten beiden Eingänge – die erste Karte – spielen bei dieser speziellen Identifikationsaufgabe keine Rolle, sie sind deshalb mit 0 gewichtet:

Was diese drei Neuronen genau machen… ist mir nicht ganz klar. Positiv wird das Gesamtergebnis nur, wenn das erste Neuron eine ziemlich kleine Zahl ausgibt und das dritte Neuron eine eher kleine Zahl und das mittlere Neuron eine halbwegs große Zahl. 0.75, 5/13 halt – die Pik 6. Und wirklich führt von allen möglichen Eingaben für die beiden letzten Eingangswerte (es gibt nur 52 Kombinationen davon) nur die eine zu 0.99, alle anderen zu 0.01. (Für das eine Neuron der Ausgabeschicht habe ich eine Hard-limit-Funktion gewählt.)

Weniger als drei Neuronen gehen vermutlich nicht. Für die Karte (0, 0) reicht sicher ein Neuron, aber das ist ein Sonderfall.

Frage 4: Kann ich jede beliebige Karte mit 3 Neuronen identifizieren oder gibt es welche, für die ich mehr brauche? Die Antwort würde vielleicht helfen herauszufinden, wie viele Neuronen ich höchstens brauche, um alle potenziellen Eleusisregeln erkennen zu können.

Und wie sähe das mit Hard Limit statt mit Sigmoid aus? Ich glaube, ich brauche einen Baukasten für neuronale Netze, so mit höchstens drei versteckten Ebenen und höchstens fünf Neuronen je Ebene – das kann man als Mensch vielleicht noch durchschauen, und das lässt sich in einer Bildschirmgröße darstellen. In Javascript am besten. Gibt es sicher schon irgendwo, oder? Dazu eine Spielkartenquelle, verschiedene Ablageregeln zum Ausprobieren, ebenso verschiedene Kodierungen.

Exkurs im Exkurs: Kodierung der Kartenwerte

Kodierung: Das heißt, ich muss meine 52 Karten irgendwie in Zahlenform repräsentieren. Natürlich könnte ich sie einscannen, aber das wäre dann ein ganz anderes Problem. Also muss ich das durch Zahlen kodieren. Ich habe mich relativ unüberlegt dazu entschieden, die vier Farben durch 0.0, 0.25, 0.5 und 0.75 zu repräsentieren, die Werte durch 0/13 bis 12/13. Dass es mitunter besser gewesen wäre, jeweils noch 0.01 dazu zu zählen, um die 0 als Wert zu vermeiden, hat man bereits oben gesehen.

Ich hätte die 52 Karten auch einfach durchnummerieren können. Oder als Farbe 1–4 und als Wert 1–13 anbieten können. Oder eine Zahl von 1 bis 52*52, um beide Paare gleich in einem einzigen Wert zu repräsentieren. Oder ich hätte das Binärsystem wählen können: zwei Bit für jeden Farbwert, vier Bit für den Zahlenwert, macht 12 Bit je Zahlenpaar, also 12 Eingangswerte für die versteckten Neuronen, jeweils mit dem Wert 0 oder 1.

Und das macht jeweils einen großen Unterschied für die Schwierigkeit der zu lösenden Aufgabe!

Unter anderem habe ich durch die Kodierung mit Zahlen ja schon viel vorgegeben: Dass eine 2 kleiner ist als eine 4, steckt bereits darin und damit ist der Rechner darauf vorbereitet, die Kategorie kleiner/größer zu erkennen. Hardcore wäre, die 52 Karten als 52 willkürliche Werte zu kodieren. Dann wollen wir mal sehen, ob der Rechner noch ein Muster erkennt! Damit ist für den Rechner gleich schwierig “auf eine hohe Karte eine rote” wie “auf diese eine Karte (ebenso wie auf 25 willkürliche weitere) können 26 andere (willkürlich ausgewählte, ohne Zusammenhang stehende) Karten folgen.”

Ganz schlecht geeignet ist meine Kodierung allerdings für die Frage, ob es sich um eine ungerade Karte (A, 3, 5, 7, 9, Bube, König) oder eine gerade handelt. Wenn ich da als Kartenwert keinen Bruch von 0/13 bis 12/13 gewählt hätte, sondern vier Bit als Eingabe, dann wäre diese Unterscheidung dagegen gar kein Problem. (Bei geraden Zahlen wäre das niedrigste Bit immer eine 0, bei ungeraden eine 1 – und das kann ein Neuron leicht erkennen.) Allgemein zu der Frage, wie ein neuronales Netz diese Unterscheidung treffen kann: https://stats.stackexchange.com/questions/161189/train-a-neural-network-to-distinguish-between-even-and-odd-numbers

(In Teil 5 geht es dann hoffentlich endlich um das Trainieren von neuronalen Netzen. Und danach um unsupervised learning ohne neuronale Netze. Irgendwann mal.)

5 Antworten auf „KI: Fast alles, was ich darüber weiß (Teil 4: Das Eleusis-Experiment)“

  1. G R O S S A R T I G. (ich habe nach der Hälfte das Verstehen aufgeben, weil ich gerade zwischen Supermarkt und Fahrradständer stehe, aber das wird zu Hause nachgeholt). Super nachvollziehbare Erklärung, die den Leser nicht für dumm erklärt. Das letzte mal hatte ich das Gefühl als Drosten im Podcast so ein paar kurze Überschlagsrechnungen durch die Gegend geworfen hat).

  2. Jein. Die “Mau-Mau-Regel in Eleusis mittels Perzeptron” ist nichts, was der Spiegel auf das Cover drucken würde. Aber die dahinter stehenden Konzepte, wie erkennt ein Programm regeln, kann man es als Mensch nachvollziehen und wenn ja, ist nun wiederum extrem fundamental und ganz und gar nicht nischig. Und verstehen am praktischen Beispiel ist fast immer einfacher.

    (Zweiter Stand übrigens: jetzt zu Hause am Rechner – ich bilde mir ein prinzipiell alles verstanden zu haben und bei den meisten Zahlen in den Bildern eine Ahnung wofür sie stehen. Bin aber noch nicht auf dem Level, dass ich anderen Menschen den Artikel sinnvoll wiedergeben könnte)

  3. Um das richtig nachzuvollziehen, bräuchte man das ganze wohl interaktiv, eben etwa mit Javascript. Ich habe Stunden damit verbracht, verschiedene Zahlen einzutippen und zu schauen, was dann passiert, und das hat mir sehr geholfen, das besser zu verstehen.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.