Für diejenigen, die es noch nicht kennen, ist Akinator ein Computerspiel und eine mobile App, die von einer französischen Firma entwickelt wurde: Elokence.

Das Ziel von Akinator ist es, einen realen oder fiktiven Charakter zu erraten. Um die Figur zu erraten, an die der Spieler denkt, stellt Akinator eine Reihe von Fragen, die der Spieler mit ‚Ja‘, ‚Weiß nicht‘, ‚Nein‘, ‚Wahrscheinlich‘ und ‚Wahrscheinlich‘ nicht beantworten kann, dann bestimmt das Programm die beste Frage.

Für jede Antwort berechnet Akinator die beste Frage, die dem Spieler gestellt werden kann, und gibt schließlich eine Vermutung darüber ab, an wen der Spieler denkt. Wenn die erste Vermutung nicht richtig ist, stellt Akinator weitere Fragen, und so weiter bis zu drei Vermutungen, wobei die erste in der Regel nach 15-20 Fragen erfolgt. Wenn die dritte Vermutung immer noch nicht richtig ist, wird der Spieler aufgefordert, die Figur in eine Datenbank aufzunehmen.

Der Algorithmus, der für die Auswahl der Fragen verwendet wird, wurde vollständig von der oben erwähnten französischen Firma entwickelt, die geheim gehalten wird. Es ist jedoch relativ einfach, Artikel zu finden, die beschreiben, wie der Algorithmus aufgebaut ist und wie er in Akinator verwendet wird. In diesem Artikel zeige ich Ihnen einen einfachen und unterhaltsamen Weg, diesen Algorithmus zu verstehen.

Akinator Working

In einigen Artikeln wird erklärt, dass Akinator Entscheidungsbäume, sowie probabilistische Methoden oder Reinforcement Learning verwendet. Dieser Artikel wird sich auf zwei wichtige Algorithmen von Entscheidungsbäumen konzentrieren; Inkrementelle Induktion von Entscheidungsbäumen 3 (ID3) und ID4.

Weitere Informationen über den Entscheidungsbaum finden Sie im Artikel „Tree Models Fundamental Concepts“

Incremental Induction of Decision Trees 3 (ID3)

Die Grundidee des ID3-Algorithmus besteht darin, einen Entscheidungsbaum mithilfe einer Top-Down-Suche durch die gegebenen Mengen zu erstellen, um jedes Attribut an jedem Knoten des Baums zu testen.

Wenn Sie ID3 besser verstehen wollen, können Sie den Artikel: „Beispiel: Berechnung der Unreinheit mit Hilfe von Entropie und Gini-Index“

Um einen optimalen Weg zur Klassifizierung einer Lernmenge zu finden, ist es notwendig, die gestellten Fragen zu minimieren (d.h. die Tiefe des Baums zu minimieren). Daher benötigen wir eine Funktion, die messen kann, welche Fragen die ausgewogenste Aufteilung ergeben. Die Informationsgewinn-Metrik ist eine solche Funktion, d. h. der Informationsgewinn ist die Differenz zwischen dem Unreinheitsmaß der Ausgangsmenge (d. h., wenn die Menge noch nicht aufgeteilt wurde) und dem gewichteten Durchschnitt des Unreinheitsmaßes nach der Aufteilung der Menge (im vorangegangenen Artikel „Tree Models Fundamental Concepts“ haben wir untersucht, dass Gini und Entropie Maße der Unreinheit sind):

Wobei Entropie(S) die Unreinheitswerte vor der Aufteilung der Daten und Entropie(S,X) die Unreinheit nach der Aufteilung ist.

Beim Informationsgewinn gibt es zwei Hauptoperationen während der Baumbildung:

• Bewertung der Splits für jedes Attribut und Auswahl des besten Splits und,
• Erstellung von Partitionen unter Verwendung des besten Splits.

Eine sehr wichtige Sache, die man immer verstehen sollte, ist, dass die Komplexität in der Bestimmung des besten Splits für jedes Attribut liegt und wie gesagt, basierend auf Entropie oder Gini, können wir den Informationsgewinn berechnen.

Der Algorithmus, der im ID3-Baum verwendet wird, ist also der folgende:

1. Wenn alle Instanzen aus genau einer Klasse stammen, dann ist der Entscheidungsbaum ein Antwortknoten, der diesen Klassennamen enthält.
2. Andernfalls,

(a) Definieren Sie a(best) als ein Attribut (oder Merkmal) mit dem niedrigsten Gain-Score.

(b) Wachsen Sie für jeden Wert V(best,i) von a(best) einen Zweig von a(best) zu einem Entscheidungsbaum, der rekursiv aus all den Instanzen mit dem Wert V(best,i) des Attributs a(best) konstruiert wird.

ID4

Ein weiterer wichtiger Algorithmus ist ID4. Sie argumentieren, dass dieser Algorithmus eine neue Trainingsinstanz akzeptiert und dann den Entscheidungsbaum aktualisiert, was einen Neuaufbau des Entscheidungsbaums vermeidet, da eine globale Datenstruktur im ursprünglichen Baum beibehalten wurde.

Das grundlegende Baumaktualisierungsverfahren des ID4-Algorithmus wird im Folgenden dargestellt.

Eingaben: Ein Entscheidungsbaum, Eine Instanz

Ausgabe: Ein Entscheidungsbaum

1. Für jedes mögliche Testattribut am aktuellen Knoten aktualisieren Sie die Anzahl der positiven oder negativen Instanzen für den Wert dieses Attributs in der Trainingsinstanz.
2. Wenn alle am aktuellen Knoten beobachteten Instanzen positiv (negativ) sind, dann ist der Entscheidungsbaum am aktuellen Knoten ein Antwortknoten, der ein „+“ („-„) enthält, um eine positive (negative) Instanz anzuzeigen.
3. Andernfalls,

(a) Wenn der aktuelle Knoten ein Antwortknoten ist, dann ändere ihn in einen Entscheidungsknoten, der einen Attributtest mit dem niedrigsten Gain-Score enthält.

(b) Andernfalls, wenn der aktuelle Entscheidungsknoten einen Attributtest enthält, der nicht den niedrigsten Gain-Wert hat, dann

• Ändere den Attributtest in einen mit dem niedrigsten Gain-Wert.
• Verwerfe alle bestehenden Teilbäume unterhalb des Entscheidungsknotens.

Aktualisiere rekursiv den Entscheidungsbaum unterhalb des aktuellen Entscheidungsknotens entlang des Zweiges des Wertes des aktuellen Testattributs, der in der Instanzbeschreibung vorkommt. Erweitern Sie den Zweig, falls erforderlich.

Weitere Informationen über Entscheidungsbäume finden Sie unter: „Tree Models Fundamental Concepts“ und „Example: Berechnen der Verunreinigung mit Entropie und Gini-Index“