Per coloro che non lo conoscono ancora, Akinator è un gioco per computer e un’applicazione mobile creata dalla società francese: Elokence.
Lo scopo di Akinator è quello di indovinare un personaggio reale o immaginario. Per indovinare il personaggio che il giocatore sta pensando, Akinator pone una serie di domande e il giocatore può rispondere con ‘Sì’, ‘Non so’, ‘No’, ‘Probabilmente’ e ‘Probabilmente’ no, poi il programma determina la domanda migliore.
Per ogni risposta, Akinator calcola la migliore domanda da fare al giocatore e infine dà un’ipotesi su chi questo giocatore sta pensando. Se la prima ipotesi non è corretta, Akinator continua a fare domande, e così via fino a tre ipotesi; la prima è generalmente dopo 15-20 domande. Se il terzo indovinello non è ancora corretto, al giocatore viene chiesto di aggiungere il personaggio in un database.
L’algoritmo utilizzato per la selezione delle domande è stato totalmente sviluppato dalla società francese di cui sopra, che è stato tenuto segreto. Tuttavia, è relativamente facile trovare articoli che descrivono come l’algoritmo è stato costruito e come viene utilizzato in Akinator. In questo articolo, vi mostrerò un modo semplice e divertente per capire questo algoritmo.
Akinator funziona
Alcuni articoli dichiarano che Akinator usa alberi decisionali, così come metodi probabilistici o apprendimento per rinforzo. Questo articolo si concentrerà su due importanti algoritmi di alberi di decisione; Induzione incrementale di alberi di decisione 3 (ID3) e ID4.
Per maggiori informazioni sugli Alberi di Decisione, vedi l’articolo “Tree Models Fundamental Concepts”
Incremental Induction of Decision Trees 3 (ID3)
L’idea di base dell’algoritmo ID3 è di costruire un Albero di Decisione usando una ricerca top-down, greedy attraverso i set dati per verificare ogni attributo su ogni nodo dell’albero.
Se vuoi capire meglio ID3, puoi vedere l’articolo: “Esempio: Calcolare l’impurità usando l’entropia e l’indice di Gini.”
Per trovare un modo ottimale di classificare un set di apprendimento, è necessario minimizzare le domande poste (cioè minimizzare la profondità dell’albero). Quindi, abbiamo bisogno di una funzione che possa misurare quali domande forniscono la suddivisione più equilibrata. La metrica Information Gain è una tale funzione, cioè Information Gain è la differenza tra la misura dell’impurità dell’insieme iniziale (cioè quando non è stato ancora suddiviso) e la media ponderata della misura di impurità dopo l’insieme suddiviso (nell’articolo precedente “Modelli ad albero Concetti fondamentali” abbiamo studiato che Gini e Entropia sono misure di impurità):
dove Entropia(S) è il valore dell’Impurità prima di dividere i dati e Entropia(S,X) è l’impurità dopo la divisione.
In Information Gain, ci sono due operazioni principali durante la costruzione dell’albero:
- Valutazione delle suddivisioni per ogni attributo e selezione della migliore suddivisione e,
- Creazione di partizioni utilizzando la migliore suddivisione.
Una cosa molto importante che dovreste sempre capire è che la complessità sta nel determinare la migliore suddivisione per ogni attributo e come detto prima, basandoci sull’Entropia o Gini, possiamo calcolare il Guadagno di Informazioni.
Quindi, usando l’Information Gain, l’algoritmo usato nell’albero ID3 è il seguente:
- Se tutte le istanze sono esattamente di una classe, allora l’albero decisionale è un nodo di risposta che contiene il nome di quella classe.
- Altrimenti,
(a) Definire a(best) come un attributo (o caratteristica) con il più basso Gain-score.
(b) Per ogni valore V(best,i) di a(best), far crescere un ramo da a(best) a un albero decisionale costruito ricorsivamente da tutte quelle istanze con valore V(best,i) dell’attributo a(best).
ID4
Un altro importante algoritmo è ID4. Essi sostengono che questo algoritmo accetta una nuova istanza di addestramento e poi aggiorna l’albero di decisione, il che evita di ricostruire l’albero di decisione per il fatto che una struttura di dati globale è stata mantenuta nell’albero originale.
La procedura base di aggiornamento dell’albero dell’algoritmo ID4 è data qui sotto.
Ingressi: Un albero decisionale, Un’istanza
output: Un albero di decisione
- Per ogni possibile attributo di prova al nodo corrente, aggiorna il conteggio delle istanze positive o negative per il valore di quell’attributo nell’istanza di formazione.
- Se tutte le istanze osservate al nodo corrente sono positive (negative), allora l’albero decisionale al nodo corrente è un nodo di risposta contenente un “+” (“-“) per indicare un’istanza positiva (negativa).
- Altrimenti,
(a) Se il nodo corrente è un nodo di risposta, allora cambialo in un nodo decisionale contenente un attributo test con il Gain-score più basso.
(b) Altrimenti, se il nodo di decisione corrente contiene un test di attributo che non ha il Gain-score più basso, allora
- Cambia il test di attributo con uno con il Gain-score più basso.
- Scarta tutti i sottoalberi esistenti sotto il nodo di decisione.
Aggiorna ricorsivamente l’albero di decisione sotto il nodo di decisione corrente lungo il ramo del valore dell’attributo del test corrente che ricorre nella descrizione dell’istanza. Fai crescere il ramo se necessario.
Per maggiori informazioni sull’albero decisionale vedi: “Concetti fondamentali dei modelli ad albero” e “Esempio: Calcolare l’impurità usando l’entropia e l’indice di Gini.”
.