Come funzionano 20 domande sugli algoritmi AI?

Question

Semplici giochi online di 20 domande alimentati da un'IA incredibilmente accurata.

Come fanno ad indovinare così bene?

Answer 1

Si può pensare ad esso come Algoritmo di ricerca binaria. In ogni iterazione, facciamo una domanda, che dovrebbe eliminare circa la metà delle possibili scelte di parole. Se ci sono un totale di N parole, allora possiamo aspettarci di ottenere una risposta dopo le domande di log2 (N).

Con 20 domande, dovremmo essere in grado di trovare una parola tra 2^20 = 1 milione di parole.

Un modo semplice per eliminare i valori anomali (risposte errate) è probabilmente quello di utilizzare qualcosa come RANSAC. Ciò significherebbe, invece di prendere in considerazione tutte le domande a cui è stata data una risposta, di scegliere casualmente un sottoinsieme più piccolo, il che è sufficiente per darti un'unica risposta. Ora lo ripeti alcune volte con diversi sottoinsiemi casuali di domande, finché non vedi che la maggior parte delle volte ottieni lo stesso risultato. allora sai che hai la risposta giusta.

Naturalmente questo è solo uno dei tanti modi per risolvere questo problema.

Answer 2

Sta utilizzando un algoritmo di apprendimento.

k-NN è un buon esempio di uno di questi.

Wikipedia: k-Nearest Neighbor Algorithm

Answer 3

raccomanda la lettura del gioco qui: http://en.wikipedia.org/wiki/Twenty_Questions

In particolare i computer sezione:

Il gioco suggerisce che le informazioni (come misurato da entropia di Shannon statistica) richiesto per identificare un oggetto arbitrario è di circa 20 bit. Il gioco viene spesso utilizzato come esempio quando insegna alla teoria delle informazioni . Matematicamente, se ogni domanda è strutturata per eliminare metà degli oggetti, , 20 domande saranno consentire all'interrogazione di distinguere tra 2 o 1.048.576 soggetti. Di conseguenza, la più efficace strategia per Venti domande è a porre domande che divideranno il campo delle restanti possibilità circa a metà ogni volta. Il processo è analogo a un algoritmo di ricerca binaria in informatica.

Answer 4

Un albero decisionale supporta direttamente questo tipo di applicazione. Gli alberi decisionali sono comunemente usati nell'intelligenza artificiale.

Un albero decisionale è un albero binario che richiede la "migliore" domanda in ciascun ramo per distinguere tra le raccolte rappresentate dai figli sinistro e destro. La migliore domanda è determinata da un algoritmo di apprendimento che i creatori dell'applicazione 20 domande usano per costruire l'albero. Quindi, come sottolineano altri poster, un albero con 20 livelli di profondità ti dà un milione di cose.

Un modo semplice per definire la "migliore" domanda in ogni punto è cercare una proprietà che divida in modo più uniforme la raccolta in metà. In questo modo, quando ottieni una risposta sì/no a quella domanda, ti sbarazzi di circa metà della collezione ad ogni passaggio. In questo modo puoi approssimare la ricerca binaria.

Wikipedia fornisce un esempio più completo:

http://en.wikipedia.org/wiki/Decision_tree_learning

E alcuni contesto generale:

http://en.wikipedia.org/wiki/Decision_tree

Answer 5

Si spaccia come "la rete neurale su internet", e qui sta il tasto. Probabilmente memorizza le probabilità di domanda/risposta in una matrice di riserva. Usando queste probabilità, è in grado di utilizzare un algoritmo di albero decisionale per dedurre quale domanda porre per meglio restringere la domanda successiva. Una volta che riduce il numero di risposte possibili a qualche dozzina, o se ha già raggiunto 20 domande, allora inizia a leggere il più probabile.

L'aspetto davvero intrigante di 20q.net è che, a differenza della maggior parte degli algoritmi di reti decisionali e di reti neurali di cui sono a conoscenza, 20q supporta una matrice sparsa e aggiornamenti incrementali.

Modifica: Risulta che la risposta è stata in rete per tutto questo tempo. Robin Burgener, l'inventore, ha descritto il suo algoritmo in dettaglio nel suo 2005 patent filing.