Die Gestaltung einer zwanzig-Fragen-Algorithmus
Ich bin interessiert am schreiben, ein zwanzig Fragen Algorithmus ähnlich zu dem, was akinator und, in geringerem Maße, 20q.net verwendet. Letztere scheint sich mehr zu konzentrieren auf Objekte, die explizit sagen, Sie nicht daran zu denken, Personen oder Orte. Man könnte sagen, dass akinator ist mehr allgemein, so dass Sie denken, buchstäblich alles, einschließlich Abstraktionen wie "mein Bruder".
Das problem mit diesem ist, dass ich nicht weiß, welcher Algorithmus diese Websites verwenden, aber von was ich gelesen habe scheinen Sie zu sein mit einem probabilistischen Ansatz, in dem die Fragen gegeben werden, sind eine gewisse fitness basierend auf wie viele Male Sie haben zu führen, um richtige Vermutungen. Diese ALSO Frage präsentiert verschiedene Techniken, aber eher vage, und ich wäre an mehr details interessiert.
So, was könnte sein, eine genaue und effiziente Algorithmus für das spielen zwanzig Fragen?
Ich bin daran interessiert, details zu:
- Was Frage weiter.
- Wie man das am besten machen, denke mal am Ende der 20 Fragen.
- Wie fügen Sie ein neues Objekt und eine neue Frage in die Datenbank.
- Wie query (1, 2) und update (3) die Datenbank effizient.
Ich weiß, das kann nicht leicht sein und ich verlange nicht nach code oder einem 2000-Wörter-Präsentation. Nur ein paar Sätze zu jedem Vorgang und der zugrunde liegenden Datenstrukturen sollten ausreichen, um mich begonnen.
- im sicher, dass cstheory.stackexchange.com könnte besser sein...
- A. Weiß - ich habe darüber nachgedacht, aber basierend auf der vorhergehenden Diskussion scheint dies zu beinhalten, daß nur triviale Datenstrukturen. Ich bin nur skizzenhaft auf die details, aber meine intuition sagt mir, Sie sind nicht Forschungs-Ebene-schwierig. Wenn ich mich nicht Irre, 20q.net gestartet als eine Klasse-Projekt. Vielleicht werde ich versuchen es auch, aber ich möchte lassen diese bis jetzt als gut.
- Diese Art von Frage ist wahrscheinlich geschlossen auf CSTheory. Gab es eine ähnliche Frage über die stats.stackexchange, und ich stellte eine Gliederung der neuronalen Netzwerk basierenden Ansatz -- stats.stackexchange.com/questions/6074/...
Du musst angemeldet sein, um einen Kommentar abzugeben.
Nun, über drei Jahre später, habe ich es (obwohl ich nicht Vollzeit arbeiten drauf). Ich veranstaltete eine plumpe Umsetzung auf http://twentyquestions.azurewebsites.net/ wenn jemand interessiert ist (bitte nicht vermitteln, dass es zu viel Falsches Zeug noch!).
Es war nicht so schwer, aber ich würde sagen, es ist die nicht-intuitive Art nicht schwer, die man nicht sofort denkt. Meine Methoden beinhalten eine triviale fitness-basiert ranking, Ideen aus reinforcement learning und ein round-robin Methode der Planung neuer Fragen, die gestellt werden. All dies ist implementiert auf einer normalisierten relationalen Datenbank.
Meine grundlegenden Ideen Folgen. Wenn jemand interessiert ist, werde ich teilen, code, Kontaktieren Sie mich einfach. Ich der plan auf, so dass es open-source-irgendwann, aber einmal habe ich es getan, ein bisschen mehr Tests und Nacharbeiten. Also, meine Ideen:
A
auf eine FrageQ
treibt alle Entitäten, für die die Mehrheit die Antwort zu FrageQ
istA
;GameEntities
Tabelle. Fragen, für die die erwartete Antwort ist ja bevorzugt werden sogar vor dem fitness, weil diese mehr Chancen haben, die Konsolidierung der aktuellen top-Platzierten Unternehmen;Ich kann weitere Informationen geben, wenn jemand interessiert ist. Ich bin auch offen für die Zusammenarbeit auf die Verbesserung der algorithmen und der Implementierung.
Dies ist eine sehr interessante Frage. Leider habe ich nicht eine vollständige Antwort, lassen Sie mich schreiben Sie einfach die Ideen, ich könnte kommen mit in 10 Minuten:
Ich versuche, versuchen Sie zu schreiben, ein python-Implementierung mit einem naiven Bayes ' schen Netzwerk für das lernen und die Minimierung der erwarteten Entropie, nachdem die Frage beantwortet wurde als Kriterium für die Auswahl einer Frage (mit einem epsilon chance der Auswahl eine zufällige Frage, um zu lernen mehr über, die Frage nach der Ideen in http://lists.canonical.org/pipermail/kragen-tol/2010-March/000912.html. Ich habe dem, was ich bisher auf github.
Wäre es interessant zu sehen, wie gut ein Entscheidungsbaum basierenden Algorithmus, der dazu dienen würde. Der trick hier ist, rein in die Lern - /Sortierung des Baumes. Ich möchte zu beachten, dass dies Sachen, an die ich mich erinnere AI Klasse und student-Arbeit in der AI-Arbeitsgruppe und sollte mit einem semi-großes Getreide (oder nugget) Salz.
Antwort auf die Fragen: