""" Corso Machine Learning Engineer - Modulo 02, Lezione 12 "Entropia, entropia incrociata e divergenza KL: perché le funzioni di costo sono tutte la stessa cosa" OBIETTIVO DI QUESTO FILE ------------------------ Tre esercizi che mettono alla prova le tre identità della lezione: 1. l'entropia è la sorpresa media, e cambia soltanto di un fattore costante quando si cambia la base del logaritmo (bit <-> nat); 2. la divergenza KL è lo scarto fra entropia incrociata ed entropia: non è simmetrica e non rispetta la disuguaglianza triangolare; 3. l'informazione mutua si può scrivere in due modi - come riduzione di entropia e come KL fra la congiunta e il prodotto delle marginali - e i due modi danno lo stesso numero. È anche, letteralmente, l'information gain di uno split di un albero decisionale. COME SI USA ----------- python3 esercizi.py Il file gira anche così com'è: stampa quali esercizi mancano ancora. Completa i TODO uno alla volta e rilancia. Le soluzioni di riferimento sono commentate in fondo al file: guardale solo dopo aver provato. AMBIENTE DICHIARATO ------------------- Solo libreria standard: serve unicamente il modulo math. Nessuna dipendenza esterna e nessun seed da fissare, perché tutti i numeri di questo file sono esatti: le distribuzioni usate hanno probabilità razionali scelte a mano. Scritto per Python 3.12+. """ import math TOLLERANZA = 1e-9 # ---------------------------------------------------------------------- # Dati del file: tutte le distribuzioni sono SCRITTE A MANO, non campionate. # ---------------------------------------------------------------------- # Esercizio 1: una distribuzione "diadica" su quattro esiti. Le probabilità # sono potenze di 1/2, quindi l'entropia viene un numero esatto. DIADICA = [0.5, 0.25, 0.125, 0.125] UNIFORME_4 = [0.25, 0.25, 0.25, 0.25] # Esercizio 2: tre distribuzioni su tre esiti. P = [0.75, 0.125, 0.125] Q = [0.5, 0.25, 0.25] R = [0.125, 0.75, 0.125] # Esercizio 3: la congiunta di due variabili binarie, come tabella 2x2. # Righe = valore del "canale" (0/1), colonne = etichetta (0/1). # Sedici esempi: sette concordi e uno discorde per ciascun valore del canale. CONGIUNTA = [[7 / 16, 1 / 16], [1 / 16, 7 / 16]] # ---------------------------------------------------------------------- # ESERCIZIO 1 - L'entropia in bit e in nat # # L'entropia è la sorpresa media: H(p) = - somma di p_i * log(p_i). # Con log in base 2 il risultato è in bit, con il logaritmo naturale è in # nat. Le due misure differiscono per un fattore ln(2) ~= 0.693147. # # Attenzione all'unico caso limite: una probabilità esattamente 0 va saltata, # perché log(0) non esiste. Il limite di p*log(p) per p -> 0 vale 0, quindi # saltare quel termine è matematicamente corretto, non una scorciatoia. # # Domanda a cui rispondere a parole, dopo aver visto i numeri: # perché l'entropia della distribuzione diadica è MINORE di quella # uniforme, pur avendo lo stesso numero di esiti? # ---------------------------------------------------------------------- def entropia_bit(distribuzione): """Entropia di una distribuzione discreta, in bit. Parametri --------- distribuzione : lista di float che somma a 1. Ritorna ------- float >= 0, oppure None se l'esercizio non è ancora svolto. Suggerimento: somma i termini -p * math.log2(p), saltando i p uguali a 0. """ # TODO (esercizio 1a): calcola e restituisci l'entropia in bit. return None def entropia_nat(distribuzione): """Stessa entropia, in nat (logaritmo naturale). Suggerimento: puoi riusare entropia_bit() e moltiplicare per math.log(2), oppure rifare la somma con math.log(). I due modi devono coincidere. """ # TODO (esercizio 1b): calcola e restituisci l'entropia in nat. return None # ---------------------------------------------------------------------- # ESERCIZIO 2 - La KL non è una distanza # # KL(p || q) = somma di p_i * log2(p_i / q_i), in bit. # # Calcolala per le tre distribuzioni P, Q, R definite sopra e guarda due cose: # - KL(P || Q) e KL(Q || P) sono numeri DIVERSI: non è simmetrica; # - KL(P || R) è MAGGIORE di KL(P || Q) + KL(Q || R): niente disuguaglianza # triangolare, quindi niente "distanza". # # Caso limite da gestire: se q_i vale 0 dove p_i è positiva, la divergenza è # infinita. Restituisci math.inf, non un numero finito e non un'eccezione. # ---------------------------------------------------------------------- def divergenza_kl_bit(p, q): """Divergenza di Kullback-Leibler da p a q, in bit. Parametri --------- p, q : liste di float della stessa lunghezza, ciascuna somma a 1. Ritorna ------- float >= 0 (eventualmente math.inf), oppure None se non ancora svolto. Suggerimento: itera su zip(p, q); salta i termini con p_i == 0; se q_i == 0 mentre p_i > 0, restituisci subito math.inf. """ # TODO (esercizio 2): calcola e restituisci la divergenza KL in bit. return None # ---------------------------------------------------------------------- # ESERCIZIO 3 - Informazione mutua = information gain # # Data la tabella congiunta p(x, y), l'informazione mutua è # # I(X; Y) = somma su x, y di p(x,y) * log2( p(x,y) / (p(x) * p(y)) ) # # cioè la divergenza KL fra la congiunta e il prodotto delle marginali. # Vale zero se e solo se le due variabili sono indipendenti. # # Lo stesso numero si ottiene come H(Y) - H(Y | X): è esattamente # l'information gain che un albero decisionale massimizza quando sceglie # su quale variabile fare lo split. Se hai già svolto l'esercizio 1 puoi # verificarlo da solo con entropia_bit(). # ---------------------------------------------------------------------- def informazione_mutua_bit(congiunta): """Informazione mutua di una tabella congiunta, in bit. Parametri --------- congiunta : lista di liste di float; la somma di tutte le celle è 1. Ritorna ------- float >= 0, oppure None se l'esercizio non è ancora svolto. Suggerimento: calcola prima le marginali di riga e di colonna, poi somma i termini p * log2(p / (riga * colonna)) saltando le celle a zero. """ # TODO (esercizio 3): calcola e restituisci l'informazione mutua in bit. return None # ---------------------------------------------------------------------- # Esecuzione: ogni blocco controlla se l'esercizio è stato svolto. # ---------------------------------------------------------------------- def vicino(ottenuto, atteso): """True se due float coincidono entro la tolleranza del file.""" return abs(ottenuto - atteso) < TOLLERANZA def esegui_esercizio_1(): """Ritorna True se l'esercizio 1 è svolto e i numeri tornano.""" print("Esercizio 1 - L'entropia in bit e in nat") in_bit = entropia_bit(DIADICA) if in_bit is None: print(" DA FARE: completa entropia_bit() (restituisce ancora None).") return False in_nat = entropia_nat(DIADICA) if in_nat is None: print(" DA FARE: completa entropia_nat() (restituisce ancora None).") return False print(f" H(diadica) = {in_bit:.6f} bit = {in_nat:.6f} nat") print(f" H(uniforme) = {entropia_bit(UNIFORME_4):.6f} bit") if not vicino(in_bit, 1.75): print(" NUMERO SBAGLIATO: attesi 1.750000 bit sulla diadica.") return False if not vicino(in_nat, 1.75 * math.log(2)): print(" NUMERO SBAGLIATO: i nat sono i bit moltiplicati per ln(2).") return False print(" OK: la diadica costa 1.75 bit, l'uniforme 2 bit. L'uniforme è") print(" il massimo: nessuna distribuzione su 4 esiti supera log2(4).") return True def esegui_esercizio_2(): """Ritorna True se l'esercizio 2 è svolto e i numeri tornano.""" print("Esercizio 2 - La KL non è una distanza") pq = divergenza_kl_bit(P, Q) if pq is None: print(" DA FARE: completa divergenza_kl_bit() (restituisce ancora None).") return False qp = divergenza_kl_bit(Q, P) qr = divergenza_kl_bit(Q, R) pr = divergenza_kl_bit(P, R) print(f" KL(P || Q) = {pq:.6f} bit KL(Q || P) = {qp:.6f} bit") print(f" KL(P || Q) + KL(Q || R) = {pq + qr:.6f} bit") print(f" KL(P || R) = {pr:.6f} bit") if not vicino(pq, 0.1887218755408672): print(" NUMERO SBAGLIATO: attesi 0.188722 bit per KL(P || Q).") return False if vicino(pq, qp): print(" SOSPETTO: KL(P || Q) e KL(Q || P) non devono coincidere.") return False if pr <= pq + qr: print(" SOSPETTO: su queste tre distribuzioni la triangolare deve") print(" risultare violata.") return False print(" OK: asimmetrica, e il percorso diretto costa più dei due pezzi.") return True def esegui_esercizio_3(): """Ritorna True se l'esercizio 3 è svolto e i numeri tornano.""" print("Esercizio 3 - Informazione mutua = information gain") mutua = informazione_mutua_bit(CONGIUNTA) if mutua is None: print(" DA FARE: completa informazione_mutua_bit() (restituisce ancora None).") return False print(f" I(canale; etichetta) = {mutua:.6f} bit") indipendente = [[0.25, 0.25], [0.25, 0.25]] print(f" su una congiunta indipendente: {informazione_mutua_bit(indipendente):.6f} bit") if not vicino(mutua, 0.4564355568004036): print(" NUMERO SBAGLIATO: attesi 0.456436 bit.") return False print(" OK: è lo stesso guadagno che un albero con criterion='entropy'") print(" ottiene splittando su 'canale'.") return True def main(): print("Corso Machine Learning Engineer - Modulo 02, Lezione 12") print("Entropia, entropia incrociata e divergenza KL") print("=" * 60) print() svolti = 0 for esercizio in (esegui_esercizio_1, esegui_esercizio_2, esegui_esercizio_3): if esercizio(): svolti += 1 print() print("=" * 60) print(f"Esercizi svolti: {svolti} su 3.") if svolti < 3: print("Completa i TODO e rilancia. Le soluzioni commentate sono in fondo al file.") else: print("Tutti e tre tornano. Ora prova il mini-progetto della lezione.") if __name__ == "__main__": main() # ====================================================================== # SOLUZIONI DI RIFERIMENTO - guardale dopo aver provato. # Per usarle, togli il commento e sostituisci i corpi delle funzioni sopra. # ====================================================================== # # def entropia_bit(distribuzione): # return -sum(p * math.log2(p) for p in distribuzione if p > 0.0) # # # def entropia_nat(distribuzione): # return -sum(p * math.log(p) for p in distribuzione if p > 0.0) # # # def divergenza_kl_bit(p, q): # totale = 0.0 # for p_i, q_i in zip(p, q): # if p_i == 0.0: # continue # il limite di p*log(p/q) per p -> 0 vale 0 # if q_i == 0.0: # return math.inf # il modello esclude cio' che i dati osservano # totale += p_i * math.log2(p_i / q_i) # return totale # # # def informazione_mutua_bit(congiunta): # righe = [sum(riga) for riga in congiunta] # colonne = [sum(riga[j] for riga in congiunta) for j in range(len(congiunta[0]))] # totale = 0.0 # for i, riga in enumerate(congiunta): # for j, cella in enumerate(riga): # if cella == 0.0: # continue # totale += cella * math.log2(cella / (righe[i] * colonne[j])) # return totale # # NUMERI ATTESI # ------------- # H(diadica) 1.750000 bit 1.213008 nat # H(uniforme su 4) 2.000000 bit # KL(P || Q) 0.188722 bit # KL(Q || P) 0.207519 bit # KL(Q || R) 0.853759 bit # KL(P || Q) + KL(Q || R) 1.042481 bit # KL(P || R) 1.615602 bit <- maggiore della somma # I(canale; etichetta) 0.456436 bit # I su congiunta indipendente 0.000000 bit