Vediamo come sfruttare una struttura dati discreta: l’albero di decisione, per affrontare problemi di concept learning. Su questa struttura implementiamo l’algoritmo ID3, che tra le ipotesi sceglie il risultato dell’apprendimento tramite esempi di addestramento. La lista delle ipotesi in questo caso è enorme e la scelta è guidata dal cosiddetto information gain.

Siamo ancora in ambito di apprendimento supervisionato.

Si hanno attributi che hanno anche più di due valori. Per ogni ipotesi si ha un albero di decisione.

In rosso si hanno gli attributi, in blu i valori degli attributi e in arancione le foglie con i risultati. Le foglie sono le risposte booleane.

Avanzando nell’albero cerchiamo una risposta (che ci deve essere).

La flessibilità nella costruzione dell’albero sta nel scegliere gli attributi e i valori di ognuno. Con l’algoritmo ID3 si costruiscono alberi decisionali in base alle istanze che ricevo (per avere un albero coerente con le istanze ricevute).

Formule booleane possono essere rappresentate in un albero decisionale, costruendo un albero che sia yes solo nei casi la formula booleana sia vera.

Albero decisionale per la formula (Outlook = Sunny) $\land$ (Wind = Weak)

Albero decisionale per la formula (Outlook = Sunny) $\lor$ (Wind = Weak)

Riassumiamo alcune caratteristiche degli alberi decisionali:

• attributi con valori discreti
• target di uscita discreto, le foglie hanno valori precisi
• posso costruire ipotesi anche con disgiunzioni
• può esserci “rumore” nel training dei dati
• possono esserci attributi di cui non ho informazioni

Un albero decisionale è quindi formato da:

• nodes: etichettati dai vari attributi
• branches: etichettati con i possibili valori dell’attributo che etichetta il nodo sorgente del ramo
• leafes nodes: etichettati con gli outcome della precisione