Akinator.com und Naive Bayes Klassifikator

12

Kontext: Ich bin ein Programmierer mit etwas (halb vergessener) Erfahrung in der Statistik von Uni-Kursen. Kürzlich bin ich auf http://akinator.com gestoßen und habe einige Zeit damit verbracht, es zum Scheitern zu bringen. Und wer war das nicht? :)

Ich habe beschlossen, herauszufinden, wie es funktionieren könnte. Nachdem ich verwandte Blog-Beiträge gegoogelt und gelesen und einige meiner (begrenzten) Kenntnisse in die resultierende Mischung eingefügt habe, habe ich das folgende Modell (ich bin mir sicher, dass ich die falsche Schreibweise verwenden werde, bitte töte mich nicht dafür):

Es gibt Themen (S) und Fragen (Q). Ziel des Prädiktors ist es, das Subjekt S auszuwählen, bei dem die größte Wahrscheinlichkeit besteht, dass es das Subjekt ist, über das der Benutzer nachdenkt, angesichts der bisher gesammelten Fragen und Antworten.

Lassen Sie Spiel G eine Reihe von Fragen und Antworten sein: .{q1,a1},{q2,a2}...{qn,an}

Dann sucht der Prädiktor nach .P(S|G)=P(G|S)P(S)P(G)

Prior für Probanden ( ) kann nur die Anzahl der erratenen Probanden dividiert durch die Gesamtanzahl der Spiele sein.P(S)

Unter der Annahme, dass alle Antworten unabhängig sind, könnten wir die Wahrscheinlichkeit von Subjekt S bei gegebenem Spiel G wie folgt berechnen:

P(G|S)=ich=1 ..nP({qich,einich}|S)

Wir könnten das berechnen , wenn wir nachverfolgen, welche Fragen und Antworten gegeben wurden, wenn die verwendeten zwar von gegebenem Thema:P({qich,einich}|S)

P(q,a|S)=answer a was given to question q in the game when S was the subjectnumber of times q was asked in the games involving S

Nun definiert eine Wahrscheinlichkeitsverteilung über Subjekte und wenn wir die nächste Frage auswählen müssen, müssen wir die auswählen, für die die erwartete Änderung der Entropie dieser Verteilung maximal ist:P(S|G)

einrGmeinxj(H[P(S|G)]-ein=yes,nÖ,meinybe...H[P(S|G{qj,ein})]

Ich habe versucht, dies umzusetzen und es funktioniert. Mit zunehmender Anzahl von Probanden nimmt die Leistung jedoch offensichtlich ab, da das nach jeder Bewegung neu berechnet und die aktualisierte Verteilung P ( S | G { q j , a } ) für die Fragenauswahl berechnet werden muss .P(S|G)P(S|G{qj,ein})

Ich habe den Verdacht, dass ich einfach das falsche Modell gewählt habe, da ich an die Grenzen meines Wissens gebunden bin. Oder vielleicht liegt ein Fehler in der Mathematik vor. Bitte klären Sie mich auf: Womit sollte ich mich vertraut machen oder wie ich den Prädiktor so ändern kann, dass er Millionen von Themen und Tausende von Fragen bewältigen kann?

Geschickt
quelle
4
Ich bezweifle, dass es sich um einen naiven Bayes handelt, sondern um einen Entscheidungsbaum, der jedes Mal erweitert wird, wenn er jemanden nicht erkennt.
1
Wäre ein solcher Entscheidungsbaum nicht zu unhandlich, um aktualisiert zu werden? Außerdem sehe ich keinen einfachen Weg, um versehentlich falsche / ehrliche Fehler zu erklären und es am Ende trotzdem mit dem Entscheidungsbaum
richtig zu machen
5
Sieht aus wie eine Reinkarnation des zwanzigjährigen 20-Fragen-Guessers, jetzt bei 20q.net . Hier ist eine beliebte Erklärung, wie es funktioniert mentalfloss.com/blogs/archives/13725
Yaroslav Bulatov
5
Entschuldigen Sie, aber ich denke, dass die Verwendung von "künstlicher Intelligenz" und "neuronalen Netzen" ohne jeglichen Kontext als Erklärung gilt. Und ich kann nicht sehen, wie man neuronales Netz für solche Dinge verwenden könnte - was wäre zum Beispiel die Ausgabefunktion?
8.
Hallo @ADEpt, es ist schon eine Weile her, dass die Frage gestellt wurde, aber können Sie den Quellcode für die Implementierung, die Sie dort hatten, mit anderen teilen?
Prikha

Antworten:

10

Dieses Spiel sieht aus wie 20 Fragen auf http://20q.net , die dem Ersteller zufolge auf einem neuronalen Netzwerk basieren. Hier ist ein Weg, ein solches Netzwerk zu strukturieren, ähnlich dem neuronalen Netzwerk, das in den Concept-Beschreibungsvektoren und im 20-Fragen-Spiel beschrieben ist .

Du hättest

  1. Eine feste Anzahl von Fragen, wobei einige Fragen als "endgültige" Fragen markiert sind.
  2. Eine Eingabeeinheit pro Frage, wobei 0/1die no/yesAntwort darstellt. Anfangs eingestellt auf0.5
  3. Eine Ausgabeeinheit pro Frage, Sigmoid in den 0..1-Bereich gequetscht
  4. Versteckte Ebene, die alle Eingabeeinheiten mit allen Ausgabeeinheiten verbindet.

Eingabeeinheiten für beantwortete Fragen werden auf 0 oder 1 gesetzt, und es wird davon ausgegangen, dass das neuronale Netz so trainiert wurde, dass Ausgabeeinheiten Ausgabewerte nahe 1 für Fragen ausgeben, bei denen eine Antwort mit "Ja" für eine Reihe vorhandener Antworten vorliegt.

In jeder Phase würden Sie die Frage auswählen, die NNam wenigsten sicher ist, dh, die entsprechende Ausgabeeinheit ist in der Nähe 0.5, die Frage stellen und die entsprechende Eingabeeinheit auf die Antwort setzen. Im letzten Schritt wählen Sie eine Ausgabeeinheit aus der Liste "Letzte Frage" mit dem Wert, der dem am nächsten kommt1 .

Jedes Spiel mit 20 Fragen enthält 20 Datenpunkte, mit denen Sie die NNGewichte mit Backpropagation aktualisieren können. Das heißt, Sie aktualisieren die Gewichte, um sicherzustellen, dass die Ausgaben des aktuellen neuronalen Netzwerks mit der richtigen Antwort übereinstimmen, wenn alle zuvor gestellten Fragen beantwortet wurden.

Jaroslaw Bulatow
quelle
7

Ich denke nicht, dass es sich wirklich um ein Klassifizierungsproblem handelt. 20 Fragen werden oft als Kompressionsproblem charakterisiert . Dies passt eigentlich besser zum letzten Teil Ihrer Frage, in dem Sie über Entropie sprechen.

Siehe Kapitel 5.7 ( Google books ) von

Cover, TM und Joy, AT (2006) Elemente der Informationstheorie

und auch Huffman-Codierung . Dieses Papier, das ich auf arXiv gefunden habe, könnte ebenfalls von Interesse sein.

Gill, JT und Wu, W. (2010) "Zwanzig Frage-Spiele enden immer mit Ja" http://arxiv.org/abs/1002.4907

Nehmen Sie der Einfachheit halber Ja / Nein-Fragen an (wohingegen akinator.com erlaubt, vielleicht erlaubt, weiß es nicht). Angenommen, jedes mögliche Thema (was akinator.com weiß) kann eindeutig durch eine Folge von Ja / Nein-Fragen und Antworten identifiziert werden - im Wesentlichen ein binärer Vektor.

Die gestellten Fragen (und ihre Antworten) definieren eine rekursive Unterteilung des Subjektraums. Diese Aufteilung entspricht ebenfalls einer Baumstruktur. Die inneren Eckpunkte des Baumes entsprechen Fragen, und die Blätter entsprechen Themen. Die Tiefe der Blätter entspricht genau der Anzahl der Fragen, die zur eindeutigen Identifizierung des Themas erforderlich sind. Sie können (trivial) jedes bekannte Thema identifizieren, indem Sie jede mögliche Frage stellen. Das ist nicht interessant, weil es möglicherweise Hunderte von Fragen gibt.

Der Zusammenhang mit der Huffman-Codierung besteht darin, dass sie (unter einem bestimmten Wahrscheinlichkeitsmodell) eine optimale Möglichkeit bietet, den Baum so zu konstruieren, dass die durchschnittliche Tiefe (fast) minimal ist. Mit anderen Worten, Sie erfahren, wie Sie die Reihenfolge der Fragen (Erstellen eines Baums) so gestalten, dass die Anzahl der Fragen, die Sie stellen müssen, im Durchschnitt gering ist. Es verwendet einen gierigen Ansatz.

Natürlich gibt es bei akinator.com noch mehr als das, aber die Grundidee ist, dass Sie sich das Problem in Form eines Baums vorstellen und versuchen können, die durchschnittliche Tiefe seiner Blätter zu minimieren.

vqv
quelle
Das ist ein guter Anfang, aber ich denke, das Problem hat mehr zu bieten. Zum Beispiel: Wie bekommen sie die Antworten auf die Fragen? Vermutlich verwenden sie die Antworten von früheren Spielern (ein Problem des verstärkten Lernens). In diesem Fall stehen wir vor dem Kompromiss, eine Frage zu wählen, die (a) das Problem für den aktuellen Spieler löst und (b) Informationen für zukünftige Spieler liefert.
Simon Byrne
Auf den ersten Blick hängt die Fähigkeit, Analogien zwischen 20 Fragen und der Huffman-Codierung zu ziehen, von der Fähigkeit ab, "Bereichsfragen" zu stellen. Das heißt, anstelle von "Warst du jemals im Weltraum?" wir stellen "pauschale" Fragen wie "War er jemals im Weltraum oder ist ein Mann oder hat eine Glatze oder war er in einem Film oder ... (100500 andere Optionen)?" Habe ich recht? Wenn ja, dann sollte ich wahrscheinlich meine Frage bearbeiten, um zu verdeutlichen, dass ich an der Sorte "
Nacheinander
Außerdem implizieren die meisten Artikel, in denen Huffman-Codes als Modell für 20 Fragen verwendet werden, dass der Fragesteller seine eigenen Fragen erstellen kann, die sich im Wesentlichen auf "Beißt" beschränken ich im Codewort für das Objekt ist 0"? In meinem Fall (oder eher im Fall von akinator.com) sind die Fragen vordefiniert, und es hat (offensichtlich) nichts mit Huffman-Codewörtern zu tun. Im Moment kann ich nicht sehen, wie ich von meiner Frage übergehen soll nach Huffman-Codes. Vielleicht könnten Sie
näher darauf eingehen
@vqv: Re: "Ich glaube nicht, dass es sich wirklich um ein Klassifizierungsproblem handelt. 20 Fragen werden oft als Kompressionsproblem charakterisiert." Stehen statistische Schlussfolgerungen und Informationskomprimierung nicht in direktem Zusammenhang mit demselben Problem?
Yang
@Yang Beziehen Sie sich auf Jorma Rissannens Argument? Sowohl die statistische Inferenz als auch die Informationskomprimierung verwenden probabilistische Modelle, um die Unsicherheit zu beschreiben, jedoch sind ihre Perspektiven und die der Forscher in diesen Bereichen im Allgemeinen sehr unterschiedlich. Was ich oben sagen möchte, ist, dass 20 Fragen natürlicher als ein Kompressionsproblem (speziell das Quellcodierungsproblem) formuliert werden können als ein Klassifizierungsproblem. … Weiter unten
vqv