""" Corso Machine Learning Engineer - Modulo 02, Lezione 11 "Ottimizzazione vincolata: moltiplicatori di Lagrange, dualità e condizioni KKT" OBIETTIVO DI QUESTO FILE ------------------------ Tre esercizi che mettono alla prova le tre idee della lezione: 1. il moltiplicatore non è un numero di servizio prodotto dal calcolo: è la derivata del valore ottimo rispetto al termine noto del vincolo, cioè il prezzo marginale di quel vincolo; 2. con un vincolo di disuguaglianza i casi possibili sono due - vincolo attivo oppure inattivo - e le condizioni KKT servono esattamente a scartarne uno; 3. il duale della SVM a margine rigido si risolve a mano su sei punti disegnati su un foglio a quadretti: i moltiplicatori diversi da zero sono, uno per uno, i vettori di supporto. 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 ------------------- Eseguito con Python 3.14.4 e NumPy 2.3.5 (serve Python 3.12+ e NumPy 2.x). Serve soltanto NumPy: niente SciPy, niente scikit-learn. Non c'è nessun numero casuale e quindi non c'è nessun seed da fissare: tutti i risultati sono esatti e riproducibili ovunque, alle ultime cifre della virgola mobile. python3 -m venv .venv && source .venv/bin/activate pip install "numpy>=2.0" """ import numpy as np # ---------------------------------------------------------------------- # I sei punti della lezione: coordinate intere, disegnabili a mano su un # foglio a quadretti. Tre per classe, linearmente separabili. # ---------------------------------------------------------------------- X_SEI = np.array([[1.0, 1.0], # 0 classe -1 [0.0, 1.0], # 1 classe -1 [1.0, 0.0], # 2 classe -1 [3.0, 3.0], # 3 classe +1 [4.0, 4.0], # 4 classe +1 [5.0, 3.0]]) # 5 classe +1 Y_SEI = np.array([-1.0, -1.0, -1.0, 1.0, 1.0, 1.0]) # ---------------------------------------------------------------------- # ESERCIZIO 1 - Il moltiplicatore è un prezzo # # Massimizza f(x, y) = x * y sotto il vincolo x + y = c. # Il lagrangiano è L(x, y, lam) = x*y - lam*(x + y - c). # # Domanda a cui rispondere a parole, dopo aver visto i numeri: # perché lambda vale esattamente la metà di c, e perché il salto del # valore ottimo quando c cresce di 0.01 NON coincide esattamente con # lambda * 0.01? # ---------------------------------------------------------------------- def ottimo_lagrange(c): """Massimo di x*y sul vincolo x + y = c (con c > 0). Parametri --------- c : float, il termine noto del vincolo. Ritorna ------- tupla (x, y, lam) di float, oppure None se l'esercizio non è svolto. Suggerimento: annulla le derivate parziali del lagrangiano. dL/dx = y - lam = 0 -> y = lam dL/dy = x - lam = 0 -> x = lam Poi imponi il vincolo x + y = c e ricava lam in funzione di c. """ # TODO (esercizio 1): sostituisci `return None` con il calcolo. return None # ---------------------------------------------------------------------- # ESERCIZIO 2 - Vincolo attivo o inattivo: KKT decide # # Minimizza f(v) = ||v||^2 sotto il vincolo a . v >= c. # In forma standard: g(v) = c - a . v <= 0, e # L(v, mu) = ||v||^2 + mu * (c - a . v), con mu >= 0. # # I casi sono due e vanno esaminati entrambi: # (A) mu = 0 -> il minimo è quello libero, v = 0. Va tenuto solo se è # ammissibile, cioè solo se g(0) = c <= 0. # (B) g(v) = 0 -> il vincolo è attivo: v sta sul bordo. Va tenuto solo # se il mu che ne esce è >= 0. # # Domanda: che cosa succede alla soluzione quando c passa da 4 a -1? # ---------------------------------------------------------------------- def risolvi_kkt(a, c): """Minimo di ||v||^2 sotto il vincolo a . v >= c, risolto con le KKT. Parametri --------- a : np.ndarray, il vettore dei coefficienti del vincolo (non nullo). c : float, il termine noto. Ritorna ------- tupla (v, mu) con v array NumPy e mu float, oppure None. Suggerimento: nel caso attivo la stazionarietà è 2*v - mu*a = 0, quindi v = mu*a/2. Sostituisci nel vincolo a . v = c e ricava mu. """ # TODO (esercizio 2): sostituisci `return None` con il ragionamento # sui due casi. Ricorda di restituire il caso ammissibile, non il primo # che capita. return None # ---------------------------------------------------------------------- # ESERCIZIO 3 - Il duale della SVM sui sei punti # # Nel duale a margine rigido lo scarto complementare dice che alpha_i > 0 # soltanto sui punti che stanno esattamente sul margine. Se l'insieme dei # supporti è noto, il duale diventa un piccolo sistema LINEARE. # # Con due supporti k1 e k2 le incognite sono (alpha_k1, alpha_k2, b) e le # equazioni sono tre: # (1) somma_i alpha_i y_i = 0 # (2) y_k (w . x_k + b) = 1 per k = k1 e per k = k2 # dove w = somma_i alpha_i y_i x_i (tutti gli altri alpha valgono zero). # # Domanda: che cosa cambierebbe se passassi (3, 3) a (3.5, 3.5)? # ---------------------------------------------------------------------- def duale_sui_supporti(X, y, supporti): """Risolve il duale a margine rigido assumendo noto l'insieme dei supporti. Parametri --------- X : np.ndarray (n, d), i punti. y : np.ndarray (n,), etichette +1 / -1. supporti : lista di 2 indici, i presunti vettori di supporto. Ritorna ------- tupla (alpha, b) con alpha array di lunghezza n e b float, oppure None. Suggerimento: costruisci la matrice 3x3 del sistema riga per riga. La riga del vincolo (1) è [y[k1], y[k2], 0] con termine noto 0. La riga di (2) per il supporto k è [ y[k]*y[k1]*(x_k1 . x_k), y[k]*y[k2]*(x_k2 . x_k), y[k] ] con termine noto 1. Poi np.linalg.solve, e rimetti gli alpha al loro posto in un vettore di zeri lungo n. """ # TODO (esercizio 3): sostituisci `return None` con la costruzione del # sistema e la sua soluzione. return None def margini(X, y, w, b): """y_i (w . x_i + b) per ogni punto. Già scritta: non c'è nulla da fare. Vale esattamente 1 sui vettori di supporto e più di 1 su tutti gli altri. """ return y * (X @ w + b) # ---------------------------------------------------------------------- # Runner: stampa i risultati degli esercizi svolti e segnala quelli mancanti # ---------------------------------------------------------------------- def _sezione(titolo): print() print(titolo) print("-" * len(titolo)) def _da_fare(numero): print(f" [ ] Esercizio {numero} non ancora svolto: completa il TODO qui sopra.") def esegui_esercizio_1(): _sezione("Esercizio 1 - il moltiplicatore è un prezzo") risultato = ottimo_lagrange(10.0) if risultato is None: _da_fare(1) return False x, y, lam = risultato print(f" c = 10.00 -> x = {x:.4f} y = {y:.4f} f* = {x * y:.4f} lambda = {lam:.4f}") passo = 0.01 dopo = ottimo_lagrange(10.0 + passo) salto = dopo[0] * dopo[1] - x * y print(f" f*(10.01) - f*(10.00) = {salto:.8f}") print(f" lambda * 0.01 = {lam * passo:.8f}") print(f" scarto = {abs(salto - lam * passo):.2e} (termine di secondo ordine)") print(" Il moltiplicatore è la derivata del valore ottimo rispetto al") print(" termine noto: il prezzo di una unità in più di vincolo.") return True def esegui_esercizio_2(): _sezione("Esercizio 2 - vincolo attivo o inattivo: KKT decide") a = np.array([1.0, 2.0]) for c in (4.0, -1.0): risultato = risolvi_kkt(a, c) if risultato is None: _da_fare(2) return False v, mu = risultato g = c - a @ v stato = "attivo" if abs(g) < 1e-12 and mu > 0 else "inattivo" print(f" c = {c:5.1f} -> v* = ({v[0]:.4f}, {v[1]:.4f}) f* = {v @ v:.4f}" f" mu = {mu:.4f} vincolo {stato}") print(f" scarto complementare |mu * g(v*)| = {abs(mu * g):.2e}") print(" Con c = 4 il minimo libero non è ammissibile e il vincolo spinge;") print(" con c = -1 il vincolo non tocca, e il suo prezzo è zero.") return True def esegui_esercizio_3(): _sezione("Esercizio 3 - il duale della SVM sui sei punti") risultato = duale_sui_supporti(X_SEI, Y_SEI, [0, 3]) if risultato is None: _da_fare(3) return False alpha, b = risultato w = (alpha * Y_SEI) @ X_SEI print(" alpha =", " ".join(f"{a:.4f}" for a in alpha)) print(f" w = ({w[0]:.4f}, {w[1]:.4f}) b = {b:.4f} margine 1/||w|| = " f"{1.0 / np.linalg.norm(w):.6f}") print(" y_i (w . x_i + b) =", " ".join(f"{m:.4f}" for m in margini(X_SEI, Y_SEI, w, b))) print(f" |somma_i alpha_i y_i| < 1e-12 ? {abs(alpha @ Y_SEI) < 1e-12}") supporti = np.flatnonzero(alpha > 1e-8).tolist() print(f" vettori di supporto (alpha > 1e-8): {supporti}") print(" I due punti con alpha > 0 sono gli unici a margine esattamente 1:") print(" gli altri quattro potrebbero sparire senza cambiare la soluzione.") return True def main(): print("Corso MLE - Modulo 02, Lezione 11 - esercizi di codice") fatti = 0 for esegui in (esegui_esercizio_1, esegui_esercizio_2, esegui_esercizio_3): if esegui(): fatti += 1 print() print(f"Esercizi completati: {fatti} su 3.") if fatti < 3: print("Completa i TODO e rilancia: python3 esercizi.py") if __name__ == "__main__": main() # ====================================================================== # SOLUZIONI DI RIFERIMENTO # Decommenta una funzione alla volta, incollala al posto del TODO # corrispondente e rilancia. Guardarle prima di aver provato non insegna # niente: la difficoltà di questi esercizi è tutta nel ragionamento, # non nelle tre righe di NumPy. # ====================================================================== # # --- Esercizio 1 ------------------------------------------------------- # def ottimo_lagrange(c): # lam = c / 2.0 # da x = y = lam e x + y = c # return lam, lam, lam # # Atteso: x = y = 5.0000, f* = 25.0000, lambda = 5.0000. # f*(10.01) - f*(10.00) = 0.05002500, lambda * 0.01 = 0.05000000, # scarto 2.50e-05. # # Il valore ottimo in funzione di c è f*(c) = (c/2)^2 = c^2/4, quindi # df*/dc = c/2 = lambda: il moltiplicatore È la derivata del valore # ottimo. Lo scarto di 2.5e-05 non è un errore numerico, è il termine di # secondo ordine dello sviluppo di Taylor: f*(c + h) - f*(c) = lambda*h + # h^2/4, e con h = 0.01 vale h^2/4 = 2.5e-05, esattamente il numero # stampato. La derivata è una approssimazione lineare, e si vede. # # --- Esercizio 2 ------------------------------------------------------- # def risolvi_kkt(a, c): # a = np.asarray(a, dtype=float) # if c <= 0.0: # caso A: il minimo libero è ammissibile # return np.zeros_like(a), 0.0 # mu = 2.0 * c / (a @ a) # caso B: vincolo attivo # return mu * a / 2.0, mu # # Atteso con a = (1, 2): # c = 4.0 -> v* = (0.8000, 1.6000), f* = 3.2000, mu = 1.6000, attivo # c = -1.0 -> v* = (0.0000, 0.0000), f* = 0.0000, mu = 0.0000, inattivo # In entrambi i casi mu * g(v*) = 0: nel primo perché g = 0, nel secondo # perché mu = 0. È lo scarto complementare, e non è un caso che valga: # è il modo in cui le KKT dicono "o il vincolo tocca, o il suo prezzo è # zero". Il confine tra i due regimi è c = 0. # # --- Esercizio 3 ------------------------------------------------------- # def duale_sui_supporti(X, y, supporti): # k1, k2 = supporti # A = np.zeros((3, 3)) # rhs = np.array([0.0, 1.0, 1.0]) # A[0] = [y[k1], y[k2], 0.0] # somma alpha_i y_i = 0 # for riga, k in enumerate((k1, k2), start=1): # A[riga] = [y[k] * y[k1] * (X[k1] @ X[k]), # y[k] * y[k2] * (X[k2] @ X[k]), # y[k]] # a1, a2, b = np.linalg.solve(A, rhs) # alpha = np.zeros(len(X)) # alpha[k1], alpha[k2] = a1, a2 # return alpha, float(b) # # Atteso: # alpha = 0.2500 0.0000 0.0000 0.2500 0.0000 0.0000 # w = (0.5000, 0.5000) b = -2.0000 margine 1/||w|| = 1.414214 # y_i (w . x_i + b) = 1.0000 1.5000 1.5000 1.0000 2.0000 2.0000 # |somma_i alpha_i y_i| < 1e-12 ? True # vettori di supporto (alpha > 1e-8): [0, 3] # # Il margine vale 1/||w|| = 1/sqrt(0.5) = sqrt(2) ~ 1.414214, cioè metà # della distanza fra (1, 1) e (3, 3), che è 2*sqrt(2). I due alpha sono # uguali perché il vincolo somma_i alpha_i y_i = 0 lo impone quando i # supporti sono uno per classe. # # Se sposti (3, 3) in (3.5, 3.5) il supporto positivo si allontana, il # margine cresce e gli alpha calano: rifai il conto e verifica che # alpha * ||x+ - x-||^2 resti uguale a 2. È il legame fra i moltiplicatori # e la larghezza del margine, ed è il motivo per cui i vettori di supporto # più "stretti" pesano di più.