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:

  1. Was Frage weiter.
  2. Wie man das am besten machen, denke mal am Ende der 20 Fragen.
  3. Wie fügen Sie ein neues Objekt und eine neue Frage in die Datenbank.
  4. 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/...
InformationsquelleAutor IVlad | 2011-02-06
  1. 11

    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:

    • eine Personen Tabelle hält, dass die Figuren und Gegenstände gespielt;
    • eine Fragen Tabelle enthält die Fragen, die auch von den Benutzern eingereicht werden;
    • eine EntityQuestions Tabelle enthält entity-Frage Beziehungen. Diese enthält die Anzahl, wie oft jede Antwort für jede Frage in Bezug auf jede Person (auch jene, für die die Frage angesprochen wurde, sowieso). Es hat auch ein Fitness-Bereich, verwendet für ranking-Fragen "mehr allgemein" unten auf "spezifisches";
    • eine GameEntities Tabelle wird verwendet für die Einstufung der Personen nach den Antworten, die bisher für jedes laufende Spiel. Eine Antwort von A auf eine Frage Q treibt alle Entitäten, für die die Mehrheit die Antwort zu Frage Q ist A;
    • Die erste Frage, die gestellt wird, ist ausgewählt aus jenen mit der höchsten Summe des fitnesses über die EntityQuestions Tabelle;
    • Jede nächste Frage ist, ausgewählt aus jenen mit der höchsten fitness im Zusammenhang mit der derzeit höchsten Einträge in die 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;
    • Wenn das system ist ziemlich sicher die Antwort, noch bevor alle 20 Fragen gestellt wurden, und es wird beginnen, Fragen zu stellen, die nicht im Zusammenhang mit seiner Antwort, so wie zu lernen mehr über, die Person. Dies geschieht in einer, round-robin-Weise aus der globalen Fragen-pool jetzt. Diskussion: round-robin-gut, oder sollte es völlig zufällig?
    • Vorzeitigen Antworten werden auch gegeben, unter bestimmten Bedingungen und Wahrscheinlichkeiten;
    • Vermutungen gegeben, basierend auf der Rangliste in GameEntities. Dies ermöglicht es dem system-Konto für Lügen, weil Sie nie beseitigt jede Möglichkeit, nur sinkt die Möglichkeit des seins die Antwort;
    • Nach jedem Spiel, die fitness-und Antworten-Statistiken entsprechend aktualisiert: fitness-Werte für entity-Frage, die Verbände abnehmen, wenn das Spiel verloren wurde, und erhöhen sonst.

    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.

    • ja... wenn Sie teilen können Sie den code, es könnte sein, sehr cool.... Ich bin sehr corious!! danke
    • Hi @IVlad ist es möglich, die Freigabe der source-code bei mir ? Dank
    • Hey, danke für die Antwort! Ich bin wirklich neugierig auf den code. Würde der Geist Sie teilen es mit mir?
    • Ja kann man teilen, source-codes, mit mir? Sie ThanI
    InformationsquelleAutor IVlad
  2. 4

    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:

    • Wenn Sie in der Lage sind, zu halbieren, die Menge der möglichen Antworten auf jede Frage, die man unterscheiden kann zwischen 2^20 ~ 1 Millionen "Objekte". Dein set ist wahrscheinlich größer sein, so ist es richtig anzunehmen, dass man manchmal haben, um eine Vermutung.
    • Sie wünschen, zu maximieren utility. Einige Objekte gewählt werden, öfter als andere. Wenn Sie möchten, machen Sie gute Vermutungen, die Sie haben zu berücksichtigen, die Gewicht jedes Objekt (= die Wahrscheinlichkeit, das Objekt wird wahrgenommen, wenn Sie den Baum.
    • Wenn Sie Vertrauen, ein wenig von Ihrer Benutzer können Sie gewinnen Kenntnisse, die basierend auf Ihren Antworten. Dies bedeutet auch, dass man nicht mit einem statische Baum, Fragen zu stellen, denn dann bekommst du die Antworten auf die gleichen Fragen.. und du wirst lernen, nichts neues, wenn Sie die Begegnung mit dem gleichen Objekt.
    • Wenn eine einfache Frage ist nicht in der Lage sich zu teilen, die zwei Hälften, man könnte Sie kombinieren, um bessere Ergebnisse zu erhalten: z.B.: "ist das Objekt grün oder blau?". "grün oder hat eine Runde Form?"
    • Danke für die Antwort! Zunächst, ich glaube nicht, dass mein set sein wird, die größer als 1 million, ich denke, es ist tatsächlich viel weniger. Wie viele Objekte / Personen denken Sie, Sie könnte mit kommen wenn da, sagen wir, eine Woche? Es wird immer Leute geben, die kommen mit mehr, aber wie viel mehr? Eine Menge von dem, was intelligentere Leute in der Lage sind, zu denken, überlappen sich mit dem, was Sie dachten, und die meisten Leute spielen beliebte Wahl sowieso. Ich denke, dass sogar 100 000 Einträge für die Objekte Tabelle, ist eine übertreibung.
    • Zweiten, dem ersten "if" ist ein sehr großes wenn. Ich denke, es ist selten möglich, Halbierung der Anzahl der zur Verfügung stehenden Antworten. Sie können sich wahrscheinlich tun Sie es frühzeitig mit Fragen wie "ist Ihre Figur Männlich?", "ist Ihre Figur real?" usw., aber Fragen, die spezifische, die Sie bis Ende Beseitigung entweder viel mehr oder viel weniger als die Hälfte. Dies reduziert die von dem Vorteil, was ich gesagt habe, aber nicht viel ich denke: auch wenn diese Frage nicht schneiden Sie die Anzahl der Möglichkeiten, eine Menge, die Antwort sollte in der Regel helfen, die nächste Frage zu tun.
    • Ich habe es tatsächlich gegeben, das mehr Gedanken über das vergangene Jahr und ich kam mit einem scheinbar anständigen (meiner Meinung nach) theoretisches Modell, das wäre relativ einfach zu implementieren. Ich habe nicht die Zeit, es umzusetzen doch. Es verwendet, was Sie sagen, Ihre letzten 2 Punkte. Wenn Sie Zeit haben, vorbei zu schauen und vielleicht auch zu diskutieren, schreiben Sie mir bitte eine E-Mail (E-Mail im Profil).
    • Ja, ich weiß, das ist eine große, wenn.. vor allem in der frühen Ausbildung Zeit, wenn Sie versuchen zu lernen, welche Fragen helfen, bessere Entscheidungen zu treffen. Ich habe nur geschrieben, dass als theoretische Grenze. Aber ich denke, Sie sollten in der Lage sein, ziemlich in der Nähe, um es (2^18 oder 2^19), siehe mein update.
    InformationsquelleAutor Karoly Horvath
  3. 4

    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.

    1. Vorzugsweise wählen Sie Fragen, die mit geringen verbleibenden Entropie Erwartung. (Für die Zusammenstellung etwas zu schnell, ich habe von ε-greedy multi-armed bandit learning und Verwendung: Mit Wahrscheinlichkeit 1–ε: die Frage mit der niedrigsten verbleibenden Entropie Erwartung. Mit Wahrscheinlichkeit ε: Fragen Sie in jeder x-beliebigen Frage. Jedoch dieser Ansatz scheint bei weitem nicht optimal.)
    2. Da mein Ansatz ist es, ein Bayes-Netzwerk, erhält man die Wahrscheinlichkeiten der Objekte und können Fragen für das wahrscheinlichste Objekt.
      • Ein neues Objekt Hinzugefügt wird als neue Spalte die Wahrscheinlichkeiten matrix, mit geringer a priori Wahrscheinlichkeit und die Antworten auf die Fragen gegeben, wenn gegeben, oder wie geahnt, die durch die Bayes-Netz, wenn Sie nicht gegeben. (Ich erwarte, dass dieser zweite Teil würde viel besser funktionieren, wenn ich hinzufügen würde, Bayes-Netz-Struktur lernen statt nur mit naive Bayes.)
      • Ebenso eine neue Frage eine neue Zeile in der matrix. Wenn es darum geht, Benutzereingaben, wohl nur sehr wenige beantworten, die Wahrscheinlichkeiten sind bekannt, der rest muss erraten werden. (Im Allgemeinen, wenn Sie können Objekte, indem Sie Eigenschaften, die Sie erhalten können Eigenschaften mit der Frage, ob bestimmte Objekte haben oder nicht, und die transformation zwischen diesen ist im wesentlichen Bayes-theorem und bricht zu der übernahme der einfachste Fall. Das schätzen die Qualität verbessern sollte wieder einmal das Netzwerk hat eine angemessene Struktur.)
    3. (Dies ist ein problem, da ich berechnen viele Wahrscheinlichkeiten. Mein Ziel ist es mithilfe der Datenbank-orientierten sparse tensor-Berechnungen optimiert für das arbeiten mit gewichteten gerichteten azyklischen Graphen.)
    InformationsquelleAutor Anaphory
  4. 1

    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:

    1. Sie nur zu Fuß den Baum 🙂
    2. Dies ist ein großer Nachteil der Entscheidungsbäume. Würde man nur eine Vermutung, die angebracht werden können, um die Ende-Knoten des Baumes in der Tiefe 20 (oder früher, wenn der Baum ist noch spärlich).
    3. Es gibt ganze Bücher diesem Thema widmet. Soweit ich mich erinnere, AI-Klasse, die Sie versuchen, minimieren die Entropie zu allen Zeiten, so Sie wollen, Fragen zu stellen, die im Idealfall teilen die Menge der restlichen Objekte in zwei Gruppen gleicher Größe. Ich fürchte, Sie würde schauen müssen, das in AI Bücher.
    4. Entscheidung, die Bäume sind hoch effizient bei der Abfrage der phase, als Sie buchstäblich der Baum und befolgen Sie die 'ja' oder 'Nein' - Zweig an jedem Knoten. Update-Effizienz hängt vom Lern-Algorithmus angewendet. Sie könnten in der Lage sein zu tun, diese offline, wie in einem nächtlichen Batch-update oder sowas.
    • Entscheidungen, die Bäume sind auch problematisch, als dass mehrere Antworten. Zum Beispiel, was tun Sie, wenn jemand antwortet, "ich weiß nicht"? 19 richtige Antworten und ein "ich weiß nicht" - Antwort sollte immer noch erlauben, Sie richtig zu raten.
    • Ich bin mir nicht sicher, ob dies ein problem. Jeder Knoten konnten drei (oder mehr) Zweigen wie "ja", "Nein" und "weiß ich nicht". Es ist nicht wirklich ändern, die grundlegende Methoden und algorithmen. In der Tat mehr Zweige bedeuten weniger Kollisionen und dazu beitragen, das problem in Frage 2.
    • Aber "ich weiß nicht" sollten Sie beide sich das "ja" und "Nein" tragfähige äste, damit der Baum müsste erweitert werden, für diesen Zweck. Ein ähnliches problem ist, wenn ein falsch Antwort gegeben wird. Eine falsche Antwort, bei jedem Schritt, würde auf jeden Fall bedeuten, dass Sie die falsche denke, am Ende, in der bei einem klassischen Entscheidungsbaum. Könnte es möglich sein (und vielleicht sogar empfohlen) zu verwenden, decision trees, aber ich denke, Sie müssen gestärkt werden, ein bisschen, um einen anständigen Algorithmus. Wenn du meinst das Gebäude eine ganz neue, für jeden Eintrag "weiß ich nicht" beantwortet, was zu der gleichen Vermutung, würde dies nicht verwenden eine Menge Speicher?
    • Sie würden wahrscheinlich haben, um roll Ihrer eigenen Entscheidung-Baum-Implementierung. Fast alle, die ich gesehen habe arbeiten als Klassifikatoren auf einem kompletten Satz von Funktionen. Sie nicht leicht, können Sie auf "Wanderung" der Baum, obwohl dies sicherlich möglich.
    • Implementiert habe ich eine basic-20Q-Algorithmus. Ich würde empfehlen, wenigstens diese beiden Standard-Auswahlmöglichkeiten für jede Frage. 1) "ich weiß nicht", was bedeutet, es gibt eine gültige Antwort auf die Frage, aber es ist unbekannt, und 2) "Irrelevant", das heißt es gibt keine gültige Antwort auf die Frage.
    InformationsquelleAutor Kevin Read
Schreibe einen Kommentar