Home » Intelligenza Artificiale » 📋 URL
Un albero decisionale viene utilizzato quando, data una scelta binaria che vogliamo effettuare, si vuole capire cosa scegliere sulla base di un insieme di informazioni che abbiamo disponibili. In particolare, avremo bisogno di una lista di azioni fatte in passato (hystorical data) che colleghi i diversi valori per le scelte effettuate con i relativi dati disponibili quando tale scelta è stata fatta. L’algoritmo dovrà poi imparare a tracciare tale collegamenti in maniera autonoma e generalizzare le proprie previsioni anche nel caso in cui gli vengano presentate delle situazioni nuove nelle quali non è mai stato posto.
Generalmente, i dati storici sono espressi sotto forma di una tabella come quella riportata più in basso, che descrive tutte le diverse informazioni che sono state considerate nella scelta di un ristorante.
- Alt: c’è un’alternativa?
- Bar: c’è un bar per aspettare?
- Fri: attributo con valore vero se si è di venerdì
- Hun: attributo che indica se in questo momento abbiamo fame
- Pat: quante persone ci sono nel ristorante? [None, Some, Full]
- Price: range di prezzo del ristorante $, $$, $$$
- Rain: se sta piovendo
- Res: se è stata fatta una prenotazione nel ristorante
- Type: tipologia di ristorante [French, Italian, Thai, Burger]
- Est: quantità d’attesa stimata [0-10, 10-30, 30-60, >60]
Riportati in tabella nei diversi esempi x_1,\,\dots,\,x_{12}, ovvero le coppie caratteristiche-scelte che sono state effettuate in passato
In essa possiamo quindi trovare esempi di scelte passati assieme al corrispondente output—ovvero la decisione finale—che, sulla base di tali dati, è stata presa. Vogliamo arrivare alla definizione di un albero come il seguente
attraverso il quale, tramite una sequenza di domande, si riesce sempre a individuare un output in base alle condizioni in cui ci si trova.
Prima di analizzare i metodi che possiamo utilizzare per costruire un albero del genere è però utile sottolineare delle caratteristiche generali degli alberi decisionali:
- La decisione finale che si vuole arrivare a prendere è binaria, quindi bisognerà arrivare a una delle foglie YES/NO, e non necessariamente serve sempre percorrere l’albero in tutta la sua profondità: talvolta la decisione si può prendere in maniera piuttosto veloce
- Ogni nodo dell’albero rappresenta una decisione. Alcune decisioni portano alla definizione di un risultato finale (ovvero portano a una foglia), mentre altre sono delle ulteriori domande di fronte alle quali bisogna prendere delle nuove decisioni finché non si giunge a una foglia
- Nei rami dell’albero vengono indicate le diverse possibili strade che si possono percorrere in base alle informazioni che abbiamo. Per esempio, nel caso di WaitEstimate, possiamo scegliere diversi rami (che portano a diverse decisioni finali) in base a quanto tempo effettivamente bisogna aspettare
Arriviamo quindi ora alla domanda cruciale sugli alberi decisionali: riusciamo effettivamente a trovare sempre una risposta alle nostre domande? In generale la risposta è no! La validità di un albero decisionale dipende infatti da quali attributi sono stati scelti per costruirlo. La scelta di alcuni attributi porta infatti alla creazione di alberi decisionali che potrebbero individuare in maniera sbagliata le azioni da fare di fronte a un problema, o addirittura, in casi in cui non è presente abbastanza discriminazione tra le diverse decisioni che possono essere prese, l’albero potrebbe semplicemente rispondere a caso, rendendo futile qualunque tentativo di generalizzazione.
Ciò di cui abbiamo bisogno è quindi un metodo per discriminare alcuni attributi meno importanti ed evitare di utilizzarli nelle decisioni, privilegiando invece l’utilizzo di attributi più significativi.
Di fatto, abbiamo bisogno di una funzione \texttt{importance} che ci permetta di capire quali sono gli attributi migliori da utilizzare nelle decisioni. Inoltre, attraverso tale funzione cercheremo di ordinare gli attributi secondo la loro importanza anche nella stessa struttura fisica dell’albero, ponendo le decisioni più importanti in prossimità della radice (che possiamo intendere in maniera ricorsiva anche per i diversi sottoalberi), permettendo così di prendere delle decisioni più in fretta, evitando di “perdere tempo” nell’esplorazione dell’albero quando si può già prendere una decisione tramite i soli attributi più importanti.
Per costruire la funzione \texttt{importance} useremo l’entropia.
Cosa rappresenta l’entropia?
L’entropia rappresenta una misura del disordine di un sistema, ovvero di quanto sparsa sia la distribuzione dell’energia. Un sistema con entropia bassa ha tanta energia concentrata in una piccola area, mentre un sistema con entropia alta è più disordinato e l’energia è suddivisa all’interno di un’area maggiore.
Dal punto di vista matematico l’entropia di una variabile aleatoria V viene espressa—in Bit—come
\begin{aligned}&H(V)=\sum_k P(v_k)\cdot\log_2\left(\dfrac{1}{P(v_k)}\right)\qquad[\text{Bit}]\\[10pt]&\quad\text{dove}\\&\quad v_k:\text{elemento $k$-esimo di $V$}\\&\quad P(v_k):\text{probabilità che $v_k$ si verifichi}\end{aligned}Un caso specifico della formula generale sull’entropia è quello in cui vogliamo calcolare l’entropia di una variabile booleana H_B(\cdot)=B(\cdot), dunque il tipo di variabile che ci interessa per effettuare le scelte all’interno di un albero decisionale.
In un albero decisionale infatti in ognuna delle scelte è dettata dalla maggiore (o minore) prevalenza di un certo tipo di risultato (outcome) sugli altri all’interno del dataset storico. Per esempio, considerando la porzione seguente dell’albero proposto in precedenza
Vediamo che i colori verde/rosso corrispondono agli output YES/NO e sono loro ad essere utilizzati nel calcolo dell’entropia per prendere le decisioni. Nell’utilizzo dell’attributo Type abbiamo però entropia massima per ogni categoria, dunque non possiamo usarlo per il nostro problema, mentre tramite l’attributo Patrons ci permette una divisione migliore individuando dei casi con entropia nulla e altri che possono essere divisi ulteriormente.
Consideriamo una variabile booleana che assume, per esempio, il valore \texttt{True} con probabilità q
B(q)=q\log_2\left(\dfrac{1}{q}\right)+(1-q)\log_2\left(\frac{1}{1-q}\right)\qquad[\text{Bit}]La quantità q viene generalmente calcolata considerando il numero totale di esempi positivi (o negativi) all’interno del dataset rispetto al numero totale di eventi. Chiamando p ed n rispettivamente il numero di esempi positivi e negativi, nonché N=p+n il numero totale di esempi si ottiene il valore di q in maniera immediata come
q=\dfrac{p}{N}=\dfrac{p}{p+n}Vediamo che scendendo correttamente gli attributi siamo in grado di ricondurci ai casi in cui, dopo aver fatto una certa scelta, il risultato è sempre YES o sempre NO, dunque l’entropia è nulla e possiamo effettuare la scelta in maniera univoca.
Calcolo entropia se q=0 o q=1
La quantità sottolineata non provoca indeterminatezza, mentre per la seconda è necessario passare allo studio del limite associato, che possiamo ricondurre al limite quando q\to1^-, infatti la probabilità ha come valore massimo 1 che non può essere raggiunto però dalla destra.
B(1)=\underbrace{1\cdot\log_2\left(\dfrac{1}{1}\right)}_{\log_2(1)=0}+(1-q)\log_2\left(\dfrac{1}{1-q}\right)\\
\Downarrow\\
\lim_{q\to1^-}(1-q)\log_2\left(\dfrac{1}{1-q}\right)Poiché tale limite è indeterminato quando q\to1^- possiamo applicare l’Hopital derivando numeratore e denominatore per trovare
\lim_{q\to1^-}\dfrac{\dfrac{d}{dq}\left[\log_2\left(\dfrac{1}{1-q}\right)\right]}{\dfrac{d}{dq}\left[\dfrac{1}{1-q}\right]}\\[15pt]
\lim_{q\to1^-}\dfrac{\dfrac{1}{\left(\dfrac{1}{1-q}\right)\log(2)}}{\dfrac{1}{(1-q)^2}}\\[15pt]
\lim_{q\to1^-}\dfrac{1-q}{\log(2)}\cdot(1-q)^2=\dfrac{(1-1^-)^3}{\log(2)}=\fbox{0}Per quanto riguarda invece l’entropia quando q=0 si crea indeterminatezza per l’altro termine
B(0)=q\log_2\left(\dfrac{1}{q}\right)+\underbrace{(1-q)\log_2\left(\dfrac{1}{1-q}\right)}_{\log_2(1)=0}\\
\Downarrow\\
\lim_{q\to0^+}q\log_2\left(\dfrac{1}{q}\right)Studiando ancora tale limite con l’Hopital ottenitamo
\lim_{q\to0^+}\dfrac{\dfrac{d}{dq}\left[\log_2\left(\dfrac{1}{q}\right)\right]}{\dfrac{d}{dq}\left[\dfrac{1}{q}\right]}\\[15pt]
\lim_{q\to0^+}\dfrac{-\dfrac{1}{q\log(2)}}{-\dfrac{1}{q^2}}\\[15pt]
\lim_{q\to0^+}-\dfrac{1}{\cancel{q}\log(2)}\cdot\left(-q^{\cancel{2}}\right)=\dfrac{0^+}{\log(2)}=\fbox{0}Notiamo che anche in questo caso troviamo un valore di entropia nulla, infatti nel caso in cui q=0 o q=1 non c’è casualità, dunque anche l’entropia è nulla.
Nel caso in cui si abbiano d possibili valori (3 in questo caso) per un attributo A (Patrons in questo caso) si genereranno d sottoinsiemi.
Ognuno di questi sottoinsiemi sarà descritto da un certo valore di entropia (booleana), e, presi insieme, formeranno la cosiddetta entropia attesa. Considerando che ognuno di essi avrà
N_j=p_j+n_j
elementi formati di p_j esempi positivi e n_j esempi negativi, l’entropia attesa dal test sull’attributo A è definita come
Reminder(A)=\sum_{j=1}^{d}\underbrace{\dfrac{p_j+n_j}{p+n}}_{\text{peso}}\cdot \underbrace{B\left(\dfrac{p_j}{p_j+n_j}\right)}_{\text{entropia}}Grazie a tale formula possiamo calcolare l’information gain, ovvero la riduzione dell’entropia del sistema dopo aver effettuato un test su A
Gain(A)=\underbrace{B\left(\dfrac{p}{p+n}\right)}_{\displaystyle B(q)}-Reminder(A)Utilizzando i concetti appena spiegati possiamo dunque ottenere l’albero ottimale per il problema proposto
Esercizio: calcolare l’information gain nei due alberi seguenti
Soluzione
Nella fase iniziale entrambi gli alberi hanno entropia unitaria, infatti gli esempi positivi sono tanti quanto quelli negativi. Per la figura di sinistra vale
\begin{aligned}Reminder(A_1)&=\dfrac{2}{12}\underbrace{B\left(\dfrac{1}{2}\right)}_{\displaystyle=1}+\dfrac{2}{12}\underbrace{B\left(\dfrac{1}{2}\right)}_{\displaystyle=1}+\dfrac{4}{12}\underbrace{B\left(\dfrac{1}{2}\right)}_{\displaystyle=1}+\dfrac{4}{12}\underbrace{B\left(\dfrac{2}{4}\right)}_{\displaystyle=1}\\[30pt]&=\dfrac{12}{12}=1\end{aligned}Per quella di destra invece
\begin{aligned}Reminder(A_2)&=\dfrac{2}{12}\underbrace{B\left(\dfrac{0}{2}\right)}_{\displaystyle=0}+\dfrac{4}{12}\underbrace{B\left(\dfrac{4}{4}\right)}_{\displaystyle=0}+\dfrac{6}{12}B\left(\dfrac{2}{6}\right)\\[30pt]&=\dfrac{6}{12}\left[\dfrac{2}{6}\log_2\left(\dfrac{1}{2/6}\right)+\left(1-\dfrac{2}{6}\right)\log_2\left(\dfrac{1}{1-2/6}\right)\right]\\[10pt]&\approx0.459\end{aligned}Possiamo ora semplicemente calcolare l’information gain come
Gain(A_1)=1-Reminder(A_1)=0\\[10pt]Gain(A_2)=1-Reminder(A_2)=1-0.459=0.541
Talvolta può essere utile ridurre l’overfitting che può essere causato dagli alberi decisionali tramite una delle tecniche di pruning/bagging o random forest.
In poche parole
✅ Gli alberi decisionali rappresentano un metodo importante per prendere decisioni in base a un insieme di informazioni storiche. La tecnica viene utilizzata quando si devono effettuare scelte binarie e quando si dispone di un insieme di dati storici che collega le informazioni disponibili alla decisione finale. In pratica, un albero decisionale rappresenta una sequenza di domande che permette di individuare un output sulla base delle condizioni in cui ci si trova.
✅ Per costruire un albero decisionale si utilizzano tecniche di valutazione dell’importanza degli attributi, tra cui l’entropia e l’information gain.
✅ Tuttavia, gli alberi decisionali possono essere soggetti a overfitting, cioè alla creazione di un albero troppo complesso e specifico per l’insieme di dati storici utilizzato. Per ridurre questo problema, si possono utilizzare tecniche di pruning/bagging o random forest.