Come funzionano 20 domande sugli algoritmi AI?

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

Come fanno ad indovinare così bene?

Puoi pensarlo come l’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.

Consiglio di leggere il gioco qui: http://en.wikipedia.org/wiki/Twenty_Questions

In particolare la sezione Computer:

Il gioco suggerisce che l’informazione (misurata dalla statistica di entropia di Shannon) richiesta per identificare un object arbitrario è di circa 20 bit. Il gioco è spesso usato come esempio quando si insegna alla teoria dell’informazione. Matematicamente, se ogni domanda è strutturata per eliminare metà degli oggetti, 20 domande permetteranno all’interrogante di distinguere tra 2 20 o 1.048.576 soggetti. Di conseguenza, la strategia più efficace per Venti domande è quella di porre domande che divideranno il campo delle possibilità rimanenti approssimativamente della metà ogni volta. Il processo è analogo a un algoritmo di ricerca binaria in informatica.

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 collezioni rappresentate dai figli sinistro e destro. La migliore domanda è determinata da un algoritmo di apprendimento che i creatori dell’applicazione 20 domande usano per build 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ù uniforms 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 retroscena generali:

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

Si definisce “la rete neurale su internet”, e qui sta la chiave. 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, descrisse dettagliatamente il suo algoritmo nella sua domanda di brevetto del 2005 .

Sta usando un algoritmo di apprendimento.

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

Wikipedia: k-Nearest Neighbor Algorithm