Follow

Vi avevo parlato già degli alberi decisionali in relazione al famoso gioco 20q. Ne avevo parlato in questo articolo facendovi vedere come un semplice albero binario potesse mostrare caratteristiche di apprendimento molto ampie. Questa volta voglio invece mostrarvi un concetto molto utilizzato negli alberi decisionali per migliorare l’efficienza dell’albero stesso: l’entropia. Prima di questo però è necessario che precisare che esistono due metodologie di apprendimento.

APPRENDIMENTO GLOBALE E APPRENDIMENTO STOCASTICO

Il gioco 20q è un ottimo esempio di apprendimento stocastico. In questo caso infatti l’algoritmo apprende domanda per domanda e si aggiorna progressivamente verso la forma definitiva. L’apprendimento avviene alla fine di ogni esempio.

L’apprendimento globale invece si svolge in maniera diversa. Si prende un insieme numeroso di esempi, li si da al programma tutti insieme, e il programma apprende. In questo caso l’apprendimento avviene globalmente alla fine di tutti gli esempi.

L’apprendimento stocastico è solitamente il più usato nella pratica (specie nelle reti neurali) per la sua migliore efficienza, adattabilità e possibilità di successo. Nonostante ciò in questo esempio useremo un apprendimento globale per semplificarci i conti.

L’ENTROPIA

Supponiamo di dover scrivere un applicazione in grado di apprendere quale sono le giornate ideali per andare a giocare a tennis. La prima cosa da fare è elencare alcuni attributi della giornata: tempo, temperatura, umidità e vento. A questo punto forniamo al programma 10 “giornate” e indichiamo se la giornata è adatta al tennis o meno. Ad esempio:

1. sole, caldo, secco, lieve = si
2. sole, caldo, umido, lieve = no
3. nuvoloso, freddo, umido, forte = no
4. nuvoloso, caldo, secco, lieve = si
5. pioggia, caldo, umido, forte = no
6. pioggia, freddo, umido, lieve = no
7. sole, freddo, secco, lieve = si
8. sole, freddo, umido, forte = no
9. nuvoloso, caldo, secco, forte = no
10. sole, caldo, secco, forte = si

A questo punto dobbiamo costruire un albero a partire da questi dati. Ma quale attributo testiamo alla radice? Ovviamente dobbiamo testare l’attributo la cui risposta ci da il maggior numero di informazioni (detto diversamente, quella che ci permette di eliminare il maggior numero di ipotesi). Per far questo utilizziamo l’entropia. Essa infatti ci è molto utile per calcolare l’information gain ovvero il grado di informazione associato ad ogni attributo.

L’entropia è espressa dalla seguente formula:

Dove c è il numero di possibili risposte (nel nostro caso sono due, “si” e “no”), e i vari p sono la frazione di esempi che hanno come risultato l’i-esima risposta. Ad esempio nella nostra lista di 10 giornate ce ne sono 4 con esito positivo e 6 con esito negativo. L’entropia del nostro insieme sarà:

Cioè circa 0.97.

INFORMATION GAIN

A questo punto dobbiamo cacolare l’information gain per ogni attributo. Secondo questa formula:

La formula sembra complicata ma non lo è. Vediamo infatti un rapido esempio. Cominciamo trovando il gain dell’attributo tempo. Tale attributo ha 3 valori possibili: sole, nuvoloso e pioggia.  La prima cosa da fare è trovare il sottoinsieme S(v) per ogni valore di tempo, cominciamo con S(sole). Per fare ciò dobbiamo identificare tutte le giornale che hanno come attributo di tempo il valore “sole” e fra queste contare quante sono associate ad una giornata “si” e quante ad una giornata “no”.

Il risultato è 3 “si” (la 1, la 7 e la 10) e 2 “no” (2,8). A questo punto calcoliamo l’entropia di questo sotto-insieme e moltiplichiamola per la frazione di giornate assolate (5/10). Ottenendo: 0.48. Facciamo lo stesso per tutti gli altri valori ottenendo che il gain per tempo vale esattamente 0.23.

Facciamo lo stesso per tutti gli altri attributi ottenendo:

• tempo = 0.23
• temperatura = 0.05
• umidità =  0.61
• vento = 0.13

Bene. A questo punto sappiamo cosa scegliere: umidità. Possiamo quindi porre come nodo radice la domanda “è umido o secco?”. Inoltre notiamo che l’entropia per l’insierme S(umido) è esattamente zero. Questo ci indica che se la risposta è “umido” possiamo già dare la risposta: no.

Se invece la risposta è “secco” dobbiamo continuare. Per fare ciò dobbiamo togliere dall’insieme tutte le giornate umide. A questo punto rifacciamo tutto il calcolo da capo, ricalcoliamo il nuovo gain per ogni attributo restante (tempo, temperatura e vento) e scegliamo nuovamente il maggiore. Così fino alla fine.

Ovviamente, tutti questi conti che abbiamo fatto a mano possono essere facilmente automatizzati, altrimenti non parleremmo di apprendimento automatico 😉  In un prossimo post infatti presenterò un piccolo script che dato un insieme di esempi calcola l’albero decisionale migliore in base ai dati forniti con tanto di dati sull’entropia del sistema.