Esercizio - Albero di decisione sul ristorante - guadagno d'informazione e potatura (slide del corso)

Teoria: Apprendimento automatico nell'IA - supervisionato, SVM e valutazioneQuadro del machine learning nel corso di IA. Tre forme di apprendimento: supervisionato (coppie ingresso-uscita, classificazione se l'uscita è discreta e regressione se è un numero), non supervisionato (pattern senza feedback, per esempio clustering) e per rinforzo (ricompense). Un'ipotesi h approssima la funzione vera f e si valuta sul test set, non sul training set: un modello troppo semplice ha bias alto (underfitting), uno troppo complesso varianza alta (overfitting). Servono training, validation e test set; con pochi dati si usa la k-fold cross-validation. Alberi di decisione: si sceglie l'attributo con massimo guadagno d'informazione Gain = B(p/(p+n)) - somma (Nk/N) B(pk/Nk), si pota con il test del chi quadro (Delta > Delta*), si riduce la varianza con bagging e random forest. Perdita L1 e L2, regressione lineare e discesa del gradiente w <- w - alpha dL/dw. SVM: separatore a margine massimo, vettori di supporto, kernel trick con K(xj,xk). Pipeline scikit-learn del laboratorio 10: load_digits, train_test_split, SVC(C, kernel, gamma), fit, predict, classification_report, confusion_matrix, cross_val_score.Apprendimento automatico nell'IA - supervisionato, SVM e valutazione →, sezione 4. Approfondimento sugli alberi: Alberi di decisioneUn albero di decisione partiziona i dati con una sequenza di regole su una sola variabile alla volta (nodi interni = regole, foglie = predizioni: classe più frequente, oppure media del target in regressione). Si costruisce in modo ricorsivo scegliendo a ogni nodo la divisione che rende i figli più «puri»: con l'entropia $H=-\sum p_i\log_2p_i$ e il guadagno d'informazione $IG=H(S)-\sum\frac{|S_v|}{|S|}H(S_v)$ (ID3), oppure con l'indice di Gini $1-\sum p_i^2$ e soglie $x\le t$ su variabili numeriche (CART); in regressione con MSE o riduzione di varianza. Un albero pienamente sviluppato fa overfitting (varianza alta): si limita con la profondità massima (pre-potatura) o con la potatura a costo-complessità $R_\alpha(T)=R(T)+\alpha|T|$ (post-potatura). Pro: interpretabile, niente normalizzazione, predizione immediata; contro: varianza alta, da cui le foreste. Programma di Telecomunicazioni: Decision Trees e Random Forests.Alberi di decisione → e Esercizio - Albero di decisione ID3 sul dataset del tennis.

Testo (dalle slide). Si vuole decidere se aspettare un tavolo al ristorante (WillWait, sì o no). Gli attributi sono 10: Alt (esiste un ristorante alternativo vicino), Bar (c'è un'area bar per aspettare), Fri (venerdì o sabato), Hun (si ha fame), Pat (clienti presenti: None, Some, Full), Price (fascia di prezzo: basso, medio, alto), Rain (piove), Res (c'è una prenotazione), Type (French, Italian, Thai, Burger), Est (attesa stimata in minuti: 0-10, 10-30, 30-60, >60). Il training set ha 12 casi:

(a) Calcolare l'entropia dell'insieme e il guadagno d'informazione di ogni attributo alla radice. (b) Costruire l'albero con l'algoritmo del corso. (c) Con il test del $\chi^2$ (5%), stabilire se vanno potati il nodo Hungry sotto Patrons = Full e il nodo Patrons alla radice.

Soluzione

Formule. $B(q)=-(q\log_2q+(1-q)\log_2(1-q))$; $\text{Gain}(A)=B(\tfrac p{p+n})-\sum_k\tfrac{N_k}{N}B(\tfrac{p_k}{N_k})$.

(a) Radice

Positivi: 1, 3, 4, 6, 8, 12, cioè $p=6$; negativi: 2, 5, 7, 9, 10, 11, cioè $n=6$. L'entropia è $B(\tfrac6{12})=B(\tfrac12)=1$ bit.

Conteggi (positivi, negativi) per ogni valore e guadagni:

Calcoli rappresentativi:

• Pat: $\tfrac2{12}B(0)+\tfrac4{12}B(1)+\tfrac6{12}B(\tfrac26)=0+0+0{,}5\cdot0{,}9183=0{,}4591$, quindi $\text{Gain}=0{,}5409$ ($\approx0{,}541$ bit nelle slide). $B(\tfrac13)=\tfrac13\log_23+\tfrac23\log_2\tfrac32=0{,}5283+0{,}3900=0{,}9183$.
• Type: ogni sottoinsieme è metà e metà, entropia $1$ in ogni caso: $\text{Remainder}=1$, $\text{Gain}=0$. Dividere per Type non aiuta (come dicono le slide).
• Hun: $\tfrac5{12}B(\tfrac15)+\tfrac7{12}B(\tfrac57)=\tfrac5{12}\cdot0{,}7219+\tfrac7{12}\cdot0{,}8631=0{,}3008+0{,}5035=0{,}8043$, quindi $\text{Gain}=0{,}1957$.
• Est: $\tfrac6{12}B(\tfrac46)+\tfrac2{12}B(\tfrac12)+\tfrac2{12}B(\tfrac12)+\tfrac2{12}B(0)=0{,}5\cdot0{,}9183+\tfrac4{12}=0{,}7925$, quindi $\text{Gain}=0{,}2075$.

La radice è Patrons.

(b) L'albero

• Patrons = None: (0,2), tutti negativi, foglia No.
• Patrons = Some: (4,0), tutti positivi, foglia Sì.
• Patrons = Full: $p=2$ (es. 4 e 12), $n=4$ (es. 2, 5, 9, 10). Entropia $B(\tfrac26)=0{,}9183$. Si ricalcolano i guadagni solo su questi 6 esempi:

Per esempio $\text{Hun}$: $\text{Remainder}=\tfrac26B(0)+\tfrac46B(\tfrac24)=0+\tfrac23\cdot1=0{,}6667$, $\text{Gain}=0{,}9183-0{,}6667=0{,}2516$. Cinque attributi sono a pari merito (Hun, Price, Res, Type, Est): l'algoritmo non dice quale scegliere e le slide scelgono Hungry. (Con una scelta diversa si ottengono alberi diversi ma tutti coerenti con il training set.)

• Full e Hun = No: (0,2), foglia No.
• Full e Hun = Sì: (2,2) (es. 2, 4, 10, 12), ancora misto. Entropia 1. Guadagni: Type $=1-\big[\tfrac24\cdot B(\tfrac12)\ (\text{Thai: es. }2,4)+\tfrac14B(0)\ (\text{Italian})+\tfrac14B(1)\ (\text{Burger})\big]=1-0{,}5=0{,}5$; Fri $=0{,}3113$; si sceglie Type: Italian $\to$ No; Burger $\to$ Sì; Thai (es. 2 con Fri = No e es. 4 con Fri = Sì) $\to$ si divide ancora con Fri (guadagno 1): Fri = No $\to$ No, Fri = Sì $\to$ Sì.

Albero completo (coerente con tutti i 12 esempi):

Patrons?
├─ None  -> No
├─ Some  -> Sì
└─ Full  -> Hungry?
            ├─ No  -> No
            └─ Sì  -> Type?
                      ├─ Italian -> No
                      ├─ Burger  -> Sì
                      └─ Thai    -> Fri?  (No -> No, Sì -> Sì)

(c) Potatura con il $\chi^2$

Hungry sotto Full (0 positivi e 2 negativi se No; 2 e 2 se Sì): $p=2$, $n=4$, $N=6$. Attesi: No ($N_k=2$): $\hat p=2\cdot\tfrac26=0{,}667$, $\hat n=4\cdot\tfrac26=1{,}333$; Sì ($N_k=4$): $\hat p=1{,}333$, $\hat n=2{,}667$. $$\Delta=\tfrac{(0-0{,}667)^2}{0{,}667}+\tfrac{(2-1{,}333)^2}{1{,}333}+\tfrac{(2-1{,}333)^2}{1{,}333}+\tfrac{(2-2{,}667)^2}{2{,}667}=0{,}667+0{,}333+0{,}333+0{,}167=1{,}5.$$ Attributo a $d=2$ valori: 1 grado di libertà, $\Delta^*=3{,}841$ (tavola, probabilità $0{,}05$). $1{,}5<3{,}841$: l'ipotesi nulla (Hungry irrilevante) non si rifiuta: si pota. Il ramo Full diventa una foglia con il valore più frequente: No (4 negativi contro 2 positivi).

Patrons alla radice ($p=n=6$, $N=12$): attesi $\hat p=\hat n=6\cdot\tfrac{N_k}{12}$: None ($N_k=2$) $1$ e $1$; Some ($N_k=4$) $2$ e $2$; Full ($N_k=6$) $3$ e $3$. $$\Delta=\tfrac{(0-1)^2}{1}+\tfrac{(2-1)^2}{1}+\tfrac{(4-2)^2}{2}+\tfrac{(0-2)^2}{2}+\tfrac{(2-3)^2}{3}+\tfrac{(4-3)^2}{3}=1+1+2+2+\tfrac13+\tfrac13=6{,}667.$$ Con $d=3$ i gradi di libertà sono 2 e $\Delta^*=5{,}991$: $6{,}667>5{,}991$, l'attributo è significativo, si tiene.

Albero potato: Patrons: None $\to$ No, Some $\to$ Sì, Full $\to$ No. Accuratezza sul training: $2+4+4=10$ esempi su 12, cioè $83{,}3\%$, contro il $100\%$ dell'albero completo; ma l'albero potato è molto più semplice (un solo test) e di solito generalizza meglio, come richiede il rasoio di Ockham.

Verifica con Python

import math

righe = """Sì No No Sì Some alto No Sì French 0-10 Sì
Sì No No Sì Full basso No No Thai 30-60 No
No Sì No No Some basso No No Burger 0-10 Sì
Sì No Sì Sì Full basso Sì No Thai 10-30 Sì
Sì No Sì No Full alto No Sì French >60 No
No Sì No Sì Some medio Sì Sì Italian 0-10 Sì
No Sì No No None basso Sì No Burger 0-10 No
No No No Sì Some medio Sì Sì Thai 0-10 Sì
No Sì Sì No Full basso Sì No Burger >60 No
Sì Sì Sì Sì Full alto No Sì Italian 10-30 No
No No No No None basso No No Thai 0-10 No
Sì Sì Sì Sì Full basso No No Burger 30-60 Sì""".split("\n")
nomi = ["Alt", "Bar", "Fri", "Hun", "Pat", "Price", "Rain", "Res", "Type", "Est"]
D = [r.split() for r in righe]

def B(q): return 0 if q in (0, 1) else -(q * math.log2(q) + (1 - q) * math.log2(1 - q))
def H(S): return B(sum(r[-1] == "Sì" for r in S) / len(S))
def gain(S, a):
    resto = sum(len(T) / len(S) * H(T) for v in set(r[a] for r in S) for T in [[r for r in S if r[a] == v]])
    return H(S) - resto
def delta(S, a):                                     # statistica chi quadro per la potatura
    p = sum(r[-1] == "Sì" for r in S); n = len(S) - p; d = 0
    for v in set(r[a] for r in S):
        T = [r for r in S if r[a] == v]; pk = sum(r[-1] == "Sì" for r in T); nk = len(T) - pk
        ph, nh = p * len(T) / len(S), n * len(T) / len(S)
        d += (pk - ph) ** 2 / ph + (nk - nh) ** 2 / nh
    return d

for a, nome in enumerate(nomi): print(nome, round(gain(D, a), 4))
full = [r for r in D if r[4] == "Full"]
print("Hungry in Full: gain", round(gain(full, 3), 4), "delta", delta(full, 3))   # 0.2516 e 1.5
print("Patrons alla radice: delta", round(delta(D, 4), 3))                         # 6.667

Output: guadagni come in tabella (Pat $0{,}5409$), $\Delta=1{,}5$ e $\Delta=6{,}667$.