Domande d'esame — Machine Learning

Un programma impara da un'esperienza E rispetto a un task T e a una misura di performance P, se la sua performance su T (misurata da P) migliora con l'esperienza E.

T = task (il problema da risolvere), E = esperienza (i dati), P = performance (la metrica di valutazione). Nel ML la conoscenza viene dai dati (esperienza), quindi per induzione.

Deduzione (vecchia AI): da assiomi noti si ricavano nuove verità certe. Non può fallire perché parte da premesse vere.

Induzione (base del ML): si estrae informazione dai dati. Il ML non genera nuovi dati e può fallire, perché generalizza da un campione finito e potenzialmente rumoroso a casi non visti. Per questo i risultati vanno sempre valutati criticamente.

• Direct: cerca direttamente y=f(x) esplorando lo spazio delle ipotesi. Nessuna probabilità.
• Discriminative: (1) modella p(t|x), (2) marginalizza per ottenere E[t|x].
• Generative: (1) modella la congiunta p(x,t)=p(x|t)p(t); (2) inferisce p(t|x) con Bayes; (3) marginalizza per E[t|x]. Utile per la data augmentation (può generare nuovi dati).

Gerarchia: direct modella meno di tutti, generative modella di più (l'intera congiunta).

• Parametrico vs Non-parametrico: numero di parametri fisso (regressione lineare) vs crescente coi dati (k-NN, GP).
• Frequentista vs Bayesiano: parametri come costanti fisse ignote (prob. = frequenze) vs variabili casuali con distribuzioni (prob. = grado di incertezza).
• Generativo vs Discriminativo: impara la congiunta p(x,t) (può generare) vs la condizionata p(t|x) / il confine.
• ERM vs SRM: Empirical Risk Minimization minimizza solo l'errore di training; Structural Risk Minimization bilancia errore di training e complessità del modello.

Gli umani generalizzano da pochi esempi ma con forte bias (l'esperienza filtra le soluzioni). Le macchine vedono miliardi di coppie input/output. Il messaggio: la scala dei dati tende a vincere sulla sofisticazione dell'algoritmo — investire in dati e calcolo paga più che progettare algoritmi neuro-ispirati complessi.

I modelli lineari sono lineari nei parametri (pesi), non necessariamente negli input. Applicando basis functions non-lineari φⱼ(x) (polinomiali, gaussiane, sigmoidali), il modello y(x,w)=wᵀφ(x) cattura relazioni non-lineari nello spazio di input originale, ma resta lineare nelle feature trasformate φ(x) e nei pesi w. L'unico vincolo è che le feature siano combinate linearmente coi pesi.

1. FALSO che cambi (cioè: NON cambia il bias). Con variabili linearmente indipendenti, i modelli rappresentabili con {x₁,x₂,x₃} sono gli stessi rappresentabili con {x₁+x₂,x₂,x₃} → stesso spazio di ipotesi, stesso bias.

2. VERO. Potrebbe aumentare la varianza: i modelli rappresentabili con {x₁²/100,x₂,x₃} non sono confrontabili con quelli di {x₁,x₂,x₃}, quindi la varianza può essere maggiore.

Regola generale: aggiungere variabili allarga (o lascia invariato) lo spazio dei modelli → non può aumentare il bias; rimuovere variabili non aumenta la varianza.

VERO. Aggiungendo basis non-lineari si aumenta la dimensione dello spazio di ipotesi, quindi la probabilità che il modello vero sia vicino a uno dei modelli rappresentabili (più flessibilità). Di contro, è più difficile interpretare relazioni non-lineari tra input e output (meno spiegabilità).

Riscrivi E[L]=∫[∫(t−y(x))²p(t|x)dt]p(x)dx. Per ogni x fissato minimizzi E[(t−c)²|x] rispetto alla costante c: derivi E[−2(t−c)|x]=0 ⟹ c=E[t|x]. La costante che minimizza lo scarto quadratico da una distribuzione è la sua media.

Con la Minkowski loss |t−y|^q: q=2 → media; q=1 → mediana (MAE, robusta agli outlier); q→0 → moda. Ogni loss ottimizza una statistica diversa di p(t|x).

Loss L(w)=½‖Φw−t‖². Gradiente ∇L=Φᵀ(Φw−t), posto a zero → normal equations ΦᵀΦw=Φᵀt → ŵ=(ΦᵀΦ)⁻¹Φᵀt.

Convessità (Hessiana ΦᵀΦ semidefinita positiva): ogni minimo locale è globale → la soluzione è unica e affidabile, sia in forma chiusa sia con metodi gradient-based.

Costo: O(NM²) per calcolare ΦᵀΦ + O(M³) per invertirla ≈ O(NM²+M³). Proibitivo per M grande → serve SGD.

In ℝᴺ (una dimensione per dato), le colonne di Φ generano un sottospazio S. Ogni predizione t̂=Φw vive in S. L'OLS trova il t̂∈S più vicino a t → è la proiezione ortogonale di t su S (minimizza ‖t̂−t‖²=RSS).

Hat matrix H=Φ(ΦᵀΦ)⁻¹Φᵀ: proietta t su S (t̂=Ht). Il residuo t−t̂ è ortogonale a S — la condizione di ortogonalità Φᵀ(t−t̂)=0 è identica alle normal equations (stessa cosa, vista geometricamente).

Lo SGD approssima il gradiente con un solo dato alla volta. Update: w ← w − α(wᵀφ(xₙ)−tₙ)φ(xₙ) ("errore × feature"). Utile quando OLS è troppo costoso o i dati arrivano in streaming.

Robbins-Monro: Σαₖ=∞ (passi abbastanza grandi da arrivare ovunque) e Σαₖ²<∞ (passi abbastanza decrescenti da fermarsi e spegnere il rumore). Insieme garantiscono la convergenza. Scelta tipica αₖ∝1/k.

Assumi t=wᵀφ(x)+ε, ε∼N(0,σ²) → p(t|x,w,σ²)=N(t|wᵀφ(x),σ²). Log-likelihood (i.i.d.):

ln p = −N/2·ln(2πσ²) − 1/(2σ²)·RSS(w)

Il primo termine non dipende da w. Massimizzare la log-likelihood ≡ minimizzare RSS(w) → ŵ_ML=ŵ_OLS. I minimi quadrati sono la conseguenza dell'assunzione di rumore gaussiano, non una scelta arbitraria.

(a) FALSO. La forma chiusa esiste solo per specifiche distribuzioni del rumore (es. gaussiano scorrelato a varianza fissa → OLS).

(b) VERO. Conseguenza diretta del teorema di Gauss-Markov: l'OLS è il BLUE (Best Linear Unbiased Estimator).

(c) FALSO. I modelli ML assumono dati i.i.d.; se i target sono una serie temporale (non indipendenti, distribuzione dipendente dal tempo) i metodi ML classici non sono appropriati.

Gauss-Markov: lo stimatore dei minimi quadrati ha la varianza più piccola tra tutti gli stimatori lineari e non distorti (BLUE).

I due paletti: vale solo tra stimatori lineari e solo tra quelli non distorti. Conseguenza cruciale: può esistere uno stimatore distorto con MSE minore. Accettando un po' di bias si guadagna tanta varianza → è esattamente il principio della regolarizzazione.

Se dividessi per N otterresti una stima distorta verso il basso: i residui sono "artificialmente piccoli" perché i pesi sono stati scelti apposta per minimizzarli su quegli stessi dati (hai "consumato" gradi di libertà per stimare gli M+1 parametri). Dividendo per N−M−1 correggi il bias e ottieni una stima non distorta.

Ridge (L2): L=½Σ(tₙ−wᵀφ)²+λ/2·‖w‖₂². Ha forma chiusa ŵ=(λI+ΦᵀΦ)⁻¹Φᵀt. La matrice λI+ΦᵀΦ è sempre invertibile per λ>0 → cura la multicollinearità e il caso M>N. Restringe i pesi ma non li azzera.

Lasso (L1): L=½Σ(tₙ−wᵀφ)²+λ/2·‖w‖₁. Non differenziabile in 0, nessuna forma chiusa (metodi iterativi), ma azzera alcuni pesi → sparsità e feature selection automatica.

Perché Lasso azzera e Ridge no: il vincolo L1 è un rombo con spigoli sugli assi (le ellissi dell'RSS lo toccano su un vertice → coordinata=0); il vincolo L2 è un cerchio liscio (contatto in punto generico → nessuna coordinata esattamente 0).

Entrambi introducono bias per ridurre la varianza (bias-variance tradeoff). λ si tara in cross-validation.

La regolarizzazione aggiunge una penalità sui pesi L=L_D(w)+λL_W(w): introduce bias (restringe i pesi verso zero, sottostimandoli) per abbattere la varianza (guinzaglio che impedisce ai pesi valori estremi/instabili). λ è la manopola: grande → più bias, meno varianza.

L2 (Ridge): restringe tutti i pesi uniformemente, mai a zero → riduce la complessità effettiva ma nessuna feature selection. L1 (Lasso): azzera alcuni pesi → sparsità e selezione automatica delle feature.

(a) VERO. La penalità restringe i pesi verso zero; al crescere di λ il modello diventa meno flessibile (più bias, meno varianza).

(b) VERO. La penalità L1 ha "spigoli" a zero nella geometria della loss, che spingono alcuni pesi esattamente a zero (soluzioni sparse).

(c) FALSO. La regolarizzazione spinge verso pesi più piccoli: l'obiettivo regolarizzato non peggiora, ma l'errore non regolarizzato di training (es. MSE) può aumentare.

(a) VERO. OLS non usa regolarizzazione, quindi overfitta più del Lasso (che regolarizza sulla L1).

(b) FALSO. La Ridge regolarizza ma NON produce soluzioni sparse; la feature selection è una proprietà del Lasso.

(c) FALSO. La L1 rende l'obiettivo non differenziabile → nessuna forma chiusa (resta convesso, si ottimizza numericamente).

(a) FALSO. Se Φ è singolare, OLS ha infinite soluzioni; la Ridge ha soluzione unica ma in generale diversa per via del termine di penalità.

(b) VERO. Aggiungere feature allarga lo spazio di ipotesi → il minimo su un insieme più grande non può salire → training MSE non crescente.

(c) VERO. Con rumore OLS ha alta varianza; la regolarizzazione introduce bias ma riduce abbastanza la varianza da abbassare la MSE di test attesa.

(d) FALSO. (ΦᵀΦ+λI)⁻¹Φᵀy è la soluzione della Ridge, non del Lasso.

OLS: tratta i pesi come valore fisso ignoto, produce un singolo ŵ (stima puntuale), nessuna quantificazione dell'incertezza.

Bayesiano: tratta i pesi come variabile casuale. Definisce un prior p(w), osserva i dati (likelihood p(D|w)), e calcola il posterior p(w|D)∝p(D|w)p(w). Con coniugazione gaussiana il posterior è gaussiano N(w|w_N,S_N).

Collegamenti chiave: prior vago (varianza infinita) → la MAP collassa sull'OLS; prior gaussiano a media zero → la MAP è la Ridge (con λ=σ²/τ²). Quindi regolarizzare = avere un prior.

Vantaggi: predizioni con incertezza calibrata, aggiornamento sequenziale, meno overfitting (integra sull'incertezza invece di scommettere su un punto).

Prior p(w): lo assumi (es. gaussiana a media zero, "pesi piccoli"). Likelihood p(D|w): la calcoli assumendo rumore gaussiano sul target, valutando quanto ogni w fitta i dati. Evidenza p(D): la calcoli come ∫p(D|w)p(w)dw — costante di normalizzazione.

Differenza chiave: qui la likelihood modella il target p(t|x,w) → il modello è discriminativo e NON genera input. Nel classificatore generativo (cap. 4) Bayes lega classi e input: la likelihood è p(x|Cₖ) (distribuzione degli input) → può generare. Stessa formula, oggetti diversi (pesi vs classi).

Per predire su un nuovo x* si media su tutto il posterior dei pesi: p(t|x*,D)=∫p(t|x*,w)p(w|D)dw. Il risultato (coniugazione gaussiana) è una gaussiana con media w_Nᵀφ(x*) e varianza:

σ²_N(x*) = σ² + φ(x*)ᵀS_N φ(x*)

Due termini: σ² = rumore irriducibile (resta sempre); φᵀS_N φ = incertezza sui pesi. Per N→∞: S_N→0, il secondo termine svanisce, ma resta σ² → la banda di incertezza non si azzera mai del tutto.

• Curse of dimensionality: per coprire uno spazio ad alta dimensione con basis functions localizzate ne servono un numero esponenziale nella dimensione. Non scalano.
• Feature scelte a mano: le basis functions le scegli tu a priori, indipendenti dai dati; il modello ottimizza solo i pesi sopra di esse.

Le reti neurali superano il secondo limite (imparano le feature, al costo della trattabilità); i kernel aggirano il primo.

Modello y(x)=wᵀφ(x)+b, confine y(x)=0. Presi due punti sul confine (entrambi y=0) e sottraendo: wᵀ(φ_A−φ_B)=0 → w perpendicolare a ogni direzione lungo il confine → w ne dà l'orientazione. Il bias b ne dà la posizione (distanza dall'origine |b|/‖w‖).

y(x) è la distanza con segno dal confine (y(x)/‖w‖): il segno dice la classe, il valore assoluto la confidenza geometrica. Questo diventa il margine delle SVM.

Con K funzioni yₖ(x) si assegna x alla classe con yₖ massimo. Presi due punti x_A, x_B in Rₖ (entrambi con yₖ>yⱼ ∀j), considera x̂=λx_A+(1−λ)x_B. Per linearità: yₖ(x̂)=λyₖ(x_A)+(1−λ)yₖ(x_B). Poiché yₖ>yⱼ in entrambi gli estremi e λ,(1−λ)≥0, la disuguaglianza si conserva: yₖ(x̂)>yⱼ(x̂) → x̂∈Rₖ. Quindi Rₖ è convessa. È la linearità a garantirlo.

• Distributional mismatch: l'MSE assume rumore gaussiano, ma i target 1-of-K sono discreti (multinomiale).
• Sensibilità agli outlier: la loss quadratica penalizza i punti lontani (anche giusti), che tirano il confine.
• Nessuna interpretazione probabilistica: gli output non sono in [0,1].
• Confini subottimali: non ottimizza l'accuratezza di classificazione, può sbagliare anche con dati separabili.

Modello y(x)=f(wᵀφ(x)) con f = gradino (segno), target ±1. Loss del Perceptron: L_P=−Σ_{n∈M} tₙwᵀφ(xₙ) (solo mal classificati M). Update SGD: w ← w + α·tₙφ(xₙ).

Gradiente zero sui punti giusti: la loss è definita a tratti — per un punto ben classificato il contributo è la costante 0 (grazie al max(0,·)), che non contiene w → gradiente nullo → non spinge il confine. Solo i mal classificati hanno contributo −tₙwᵀφ(xₙ) che dipende da w → gradiente non nullo. La selezione è automatica (segno di tₙy(xₙ): >0 giusto, <0 sbagliato).

Teorema: se i dati sono linearmente separabili nel feature space, il Perceptron trova un iperpiano separatore in un numero finito di passi.

Limiti: (1) se i dati non sono separabili, non converge mai — cicla all'infinito (impossibile distinguere non-separabilità da convergenza lenta); (2) se esistono più separatori, quello trovato dipende da inizializzazione e ordine dei dati — soluzione non unica, non è a margine massimo (a differenza delle SVM).

Perceptron: f = gradino, loss = criterio del percettrone (solo errori), update w←w+αtₙφ(xₙ). Converge in passi finiti solo se separabile, altrimenti cicla; soluzione non unica.

Logistic Regression: f = sigmoide, loss = cross-entropy (Bernoulli), gradiente ∇L=Σ(yₙ−tₙ)φ(xₙ). Nessuna forma chiusa, ma loss convessa → converge sempre all'ottimo globale, anche su dati non separabili.

Entrambi sono generalized linear models y=f(wᵀφ(x)). La sigmoide è l'approssimazione liscia e differenziabile del gradino, il che abilita l'ottimizzazione gradient-based e la convessità.

Modella direttamente il posterior p(C₁|x)=σ(wᵀφ(x)) con la sigmoide σ(a)=1/(1+e⁻ᵃ), che schiaccia il punteggio in (0,1) → probabilità. Sul confine σ=0.5.

Addestramento: massimizza la likelihood Bernoulli P(t|w)=Πyₙ^tₙ(1−yₙ)^(1−tₙ), equivalente a minimizzare la cross-entropy L=−Σ[tₙln yₙ+(1−tₙ)ln(1−yₙ)]. Gradiente pulito ∇L=Σ(yₙ−tₙ)φ(xₙ). Loss convessa ma senza forma chiusa → ottimizzazione iterativa (Gradient Descent, Newton-Raphson/IRLS). Multiclasse: sigmoide → softmax.

(a) VERO. Entrambi sono f(wᵀx+w₀): gradino per il Perceptron, sigmoide per la LR.

(b) FALSO. Convessità NON implica forma chiusa; la LR si ottimizza iterativamente.

(c) FALSO. Il Perceptron converge a un separatore dipendente da init/ordine; la LR converge al minimo della sua loss convessa. Coincidono solo se esiste un unico separatore.

(d) VERO. La LR minimizza sempre la loss convessa; se i dati non sono separabili, i pesi non corrispondono a un separatore ma la convergenza avviene comunque.

(a) VERO per LR (loss convessa), FALSO per PE se le classi non sono separabili.

(b) VERO per LR (gradient descent online), FALSO per PE (l'influenza del learning rate decresce nel tempo / non è critica per la convergenza).

(c) VERO per LR (i parametri hanno significato per i log-odds), FALSO per PE (fornisce solo un'etichetta secca {0,1}).

(d) FALSO per LR (loss convessa → soluzione unica), VERO per PE (se separabili, più iperplani possibili).

Binario: sì, ma perché con 2 classi basta p(C₁)=σ(a) e l'altra è il complemento p(C₂)=1−σ(a). La somma-a-1 viene dal fatto che sono due e una è il complemento.

Multiclasse: NO — K sigmoidi separate darebbero valori in (0,1) che non sommano a 1. Serve la softmax p(Cₖ|x)=exp(aₖ)/Σⱼexp(aⱼ): divide ogni punteggio esponenziato per la somma di tutti → la somma è 1 per costruzione (come tagliare una torta in fette che fanno il 100%).

Modella p(x|Cₖ) e p(Cₖ), poi Bayes: p(Cₖ|x)=p(x|Cₖ)p(Cₖ)/p(x).

• Prior p(Cₖ): si conta (frazione di ciascuna classe nel training).
• Class-conditional p(x|Cₖ): si stima dai soli dati di quella classe. Assunzione naive: indipendenza condizionata delle feature → p(x|Cₖ)=Πⱼp(xⱼ|Cₖ) (frequenze per feature discrete, gaussiana per continue).
• Evidenza p(x): non si stima, si calcola come Σⱼp(x|Cⱼ)p(Cⱼ) — costante di normalizzazione, ignorabile per la sola decisione.

È l'unico approccio che può generare nuovi input. Funziona bene anche se l'indipendenza è irrealistica (conta il ranking dei posterior, non i valori esatti).

(a) Classificazione binaria su Iris ('Iris-setosa') con due feature. Metodi: Naive Bayes gaussiano e Logistic Regression senza regolarizzazione.

(b) pred3 classifica 'setosa' solo se entrambi i modelli concordano. I TP diminuiscono e i FN aumentano → la Recall = TP/(TP+FN) diminuisce.

(c) Il Naive Bayes: è un modello generativo, quindi può generare nuovi campioni artificiali. La LR (discriminativa) no.

Prior sulle classi: Bernoulli, stimata dalle frequenze — es. P(c=0)=5/8, P(c=1)=3/8.

Class-conditional per ogni feature binaria: Bernoulli, stimata dalle frequenze condizionate alla classe — es. P(x₁=1|c=0)=3/5, ecc.

Predizione: argmax_k P(Cₖ)Πⱼp(xⱼ|Cₖ). Attenzione allo zero-frequency problem: se una P(xⱼ|Cₖ)=0, azzera l'intero prodotto (spinge la probabilità della classe a 0 o 1). Si può correggere con smoothing.

(a) FALSO per entrambi: la LR usa una procedura iterativa (no forma chiusa), il KNN è non-parametrico (nessun training).

(b) FALSO per LR (estensione della regressione lineare per classificazione), VERO per KNN (media invece di voto di maggioranza → regressione).

(c) VERO per LR (lineare nella dimensione dei parametri), DIPENDE per KNN (deve calcolare tutte le distanze; leggero solo con pochi campioni).

(d) VERO per entrambi: la LR può includere penalità; il KNN usa K come strumento di regolarizzazione (K grande = più regolarizzazione).

k-NN: memorizza il training set; per un nuovo punto assegna la classe di maggioranza dei K vicini più vicini (metrica, es. euclidea). "Lazy learning" (nessun addestramento).

Bias-variance su K: K piccolo (es. 1) → confine molto frastagliato, sensibile al rumore → bassa bias, alta varianza (overfitting). K grande → confine liscio → alto bias, bassa varianza (underfitting). K si sceglie in cross-validation.

Curse of dimensionality: in alta dimensione le distanze tra punti diventano uniformi, "vicino" perde significato → l'unica assunzione del k-NN (località: punti vicini → stessa classe) crolla.

Accuracy fuorviante: se il 99% è classe negativa, un modello che dice sempre "negativo" ha 99% di accuracy pur essendo inutile.

• Precision = TP/(TP+FP): pochi falsi allarmi.
• Recall = TP/(TP+FN): pochi mancati rilevamenti.
• F1 = media armonica di precision e recall (penalizza gli squilibri).
• AUC-ROC: qualità del classificatore indipendente dalla soglia (1=perfetto, 0.5=caso).

Precision e recall tirano in direzioni opposte; il bilanciamento dipende dai costi degli errori dell'applicazione.

NFL: mediando su tutte le possibili funzioni target, ogni learner ha accuratezza di generalizzazione pari al caso (1/2 in binario). Corollario: se L₁ batte L₂ su alcuni problemi, esistono problemi dove L₂ batte L₁. Nessun algoritmo è universalmente migliore.

Perché funziona: il mondo reale non è arbitrario, ha regolarità; la vera f è ristretta a un sottoinsieme di funzioni. Ogni algoritmo porta un inductive bias (assunzioni), e il successo dipende dal far combaciare le assunzioni col problema. Il NFL dice che devi fare assunzioni per imparare.

Con tᵢ=f(xᵢ)+ε, E[ε]=0, Var[ε]=σ²:

E[(t−y(x))²] = E[t²]−E[t]² + E[y(x)²]−E[y(x)]² − 2f(x)E[y(x)] + ...

= Var[t] (σ²) + Var[y(x)] (varianza) + (f(x)−E[y(x)])² (bias²)

• σ² = rumore irriducibile (non eliminabile con nessun modello).
• Varianza = quanto la predizione oscilla al variare del training set (overfitting).
• Bias² = quanto la predizione media si scosta dalla vera f (underfitting).

Significato pratico: l'errore totale è una U; il model selection cerca la complessità che la minimizza. Aumentare i dati riduce la varianza.

(a) FALSO. Semplificare riduce la varianza e aumenta il bias.

(b) FALSO. Aggiungere dati riduce solo la varianza; il bias non è influenzato.

(c) VERO. Es. se lo spazio più piccolo ha bias zero ed è contenuto in quello più grande.

(d) VERO. Riduce la varianza, e la MSE = varianza + bias² + rumore irriducibile.

(a) FALSO. Aumentando d si allarga lo spazio di ipotesi → la varianza NON si riduce (aumenta).

(b) FALSO. Aumentando N il bias resta fisso (dipende da d, non da N).

(c) FALSO. N↑ riduce la varianza ma d↑ la aumenta → non si può concludere nulla.

(d) VERO. N non influenza il bias; ridurre d dà modelli più semplici → bias↑.

Il training error è una stima ottimisticamente distorta del vero errore (il modello conosce già quei dati; per modelli complessi tende a zero anche in overfitting).

• Training set: fitta i parametri (pesi w).
• Validation set: tara gli iperparametri (λ, K, grado M) e confronta i modelli.
• Test set: usato una sola volta, alla fine, per la stima non distorta del modello finale.

Punto di non ritorno: una volta valutato sul test, o raccogli nuovi dati o rischi di "ottimizzare sul test" (sacrilego), contaminando la stima.

Best subset: prova tutti i 2ᴹ sottoinsiemi → infattibile per M grande.

Stepwise (greedy, ~M² modelli): Forward = parti vuoto, aggiungi la feature migliore; Backward = parti pieno, togli la peggiore. Non garantiscono l'ottimo.

• Filter: proprietà intrinseche (correlazione), indipendente dall'algoritmo. Veloce, agnostico.
• Wrapper: usa l'algoritmo come scatola nera (lo stepwise). Costoso, su misura.
• Embedded: integrato nel training (Lasso, alberi). Bilanciato.

(a) NON corretta: valuta la MSE sullo stesso training set usato per il fit → sceglierebbe sempre l'α più piccolo (0.001). Correzione: validare su dati indipendenti (validation o cross-validation).

(b) Scopo: introdurre regolarizzazione per evitare overfitting e scegliere α. Il Lasso produce coefficienti sparsi (più zeri al crescere di α).

(c) Altri approcci: Ridge (regolarizzazione L2), oppure feature selection wrapper (forward/backward). A differenza del Lasso, con Ridge la soluzione non è sparsa.

LOOCV: N allenamenti (uno per punto lasciato fuori). Stima quasi non distorta ma costosa e ad alta varianza (training set quasi identici).

k-fold: k parti (5 o 10); alleni su k−1, valuti su 1. Meno costosa (solo k allenamenti) e bilancia meglio bias/varianza. Standard per il tuning.

Information criteria: aggiustano il training error con una penalità per la complessità (senza sprecare dati). AIC = −2logL+2M; BIC = −2logL+M·logN; Cp. Valori più piccoli = meglio. BIC penalizza più di AIC (fattore logN).

Passi: (1) calcola la media; (2) centra i dati; (3) matrice di covarianza S=1/(N−1)·X̃ᵀX̃; (4) autovettori (direzioni) e autovalori (varianza catturata), ordinati; (5-6) tieni i primi k autovettori (base ortogonale); (7) proietta i dati.

Limite concettuale: la PCA massimizza la varianza degli input, ma è non supervisionata — ignora il target. La direzione utile per predire potrebbe essere a bassa varianza e venir scartata (massima varianza ≠ massima utilità predittiva). Inoltre è lineare (fallisce su manifold curvi/cluster) e perde interpretabilità.

Bagging: allena B modelli su campioni bootstrap (con rimpiazzo) in parallelo e li media (voto per classificazione). Riduce la varianza senza toccare il bias (Var(X̄)=Var(X)/N). Ideale con modelli ad alta varianza (alberi profondi). → Random Forest.

Boosting: allena modelli in sequenza, ognuno concentrato sugli errori del precedente (aumenta i pesi dei punti mal classificati). Riduce il bias, combinando weak learner. Sequenziale, sensibile al rumore. → AdaBoost, XGBoost.

(a) FALSO. Solo il Bagging è parallelizzabile (dataset indipendenti); il Boosting è sequenziale per natura.

(b) FALSO. I weak learner sono buoni per il Boosting (alto bias). Il Bagging si usa con learner complessi e instabili (alta varianza) per ridurla.

(c) FALSO. Il bootstrapping è del Bagging; il Boosting ripesa i campioni.

(d) VERO. Una deep NN ha alta varianza; col Boosting non riduci il bias senza aumentare la varianza, e ritrainarla molte volte è costoso.

PAC (Probably Approximately Correct): quanti campioni N servono perché l'ipotesi imparata h sia probabilmente (prob. ≥ 1−δ) approssimativamente corretta (vero errore ≤ ε)?

Termini: ε = errore residuo accettato; δ = probabilità di fallimento accettata; true error L_true(h)=P[c(x)≠h(x)]; training error = frazione di errori sul training.

Sample complexity (learner consistente, H finito): N ≥ (1/ε)(ln|H|+ln(1/δ)). Dipende logaritmicamente da |H| e inversamente da ε. Più grande lo spazio di ipotesi, più dati servono.

Un'ipotesi "cattiva" (L_true≥ε) azzecca un punto con prob. ≤ (1−ε), quindi azzecca tutti gli N punti (essere consistente) con prob. ≤ (1−ε)ᴺ. Con union bound su tutte le ipotesi:

Pr(∃h consistente con L_true≥ε) ≤ |H|(1−ε)ᴺ ≤ |H|e⁻ᵉᴺ

(usando 1−ε≤e⁻ᵉ). Ponendo ≤ δ e risolvendo per N si ottiene la sample complexity. Intuizione: è improbabile che un'ipotesi con vero errore alto azzecchi per caso tutti gli N punti, tanto più con tanti dati.

Agnostic: il caso realistico in cui il concetto vero non è in H o i dati sono rumorosi → L_train>0, version space vuoto. Si usa Hoeffding (la media empirica devia dalla vera con prob. che decade esponenzialmente in N).

Bound (prob. ≥ 1−δ): L_true(h) ≤ L_train(h) + √[(ln|H|+ln(1/δ))/(2N)]

Bias-variance come garanzia: il primo termine è il bias (quanto fitti male), il secondo il termine di complessità/varianza (cresce con |H|, cala con N). Bilanciarli scegliendo H è la Structural Risk Minimization.

Dichotomy: una partizione di S in due sottoinsiemi (etichettatura positiva/negativa).

Shattering: H shattera S se per ogni possibile dichotomy esiste un'ipotesi in H consistente con essa (H classifica S perfettamente per ogni etichettatura).

VC dimension: la cardinalità del più grande insieme che H riesce a shatterare (∞ se può shatterare insiemi arbitrariamente grandi).

Perché per H infiniti: il bound agnostico ha ln|H|, inutile se |H|=∞. La VC rimpiazza |H| con una misura di capacità più fine che resta finita anche per H infiniti.

Il numero di parametri spesso coincide con la VC (regola del pollice), ma non sempre. La VC misura la capacità effettiva di frantumare i dati, non quanti numeri regoli.

Esempio del seno: h(x)=sin(wx) ha un solo parametro ma VC infinita (oscillando può separare qualsiasi configurazione). Anche 1-NN e SVM gaussiana hanno VC infinita.

Classificatore lineare in ℝᴹ: VC=M+1 (in 2D shattera 3 punti, ma non 4 — la XOR).

VC≤log₂|H|: se VC(H)=d, allora H shattera d punti → realizza tutte le 2ᵈ etichettature → servono almeno 2ᵈ ipotesi distinte → |H|≥2ᵈ → d≤log₂|H|.

VC=∞ ⟹ non PAC-learnable: il modello è troppo potente, può fittare qualsiasi training (rumore incluso) senza garanzie; il termine di complessità non converge, nessuna quantità finita di dati basta. La restrizione (VC finita) è ciò che rende possibile l'apprendimento.

(a) FALSO. Il NFL dice che performano ugualmente male in media sui concetti; su uno specifico concetto la struttura può favorire un algoritmo.

(b) VERO (in questa formulazione δ è il bound sulla probabilità che il vero errore superi ε). [Nota: in alcuni testi i ruoli di ε e δ sono invertiti — attenzione alla convenzione.]

(c) FALSO. La VC è una misura più fine della cardinalità e può essere finita anche se |H|=∞.

(d) VERO. In 1D con due punti a<b si realizzano (+,+),(−,−),(−,+); con 3 punti non si separa (+,−,+).

(a) FALSO. Il training error è sempre distorto, ancor più in consistent learning (dove è sempre zero).

(b) FALSO. Il test error è sempre non distorto; la sua affidabilità dipende dalla dimensione del test set, non dalla VC.

(c) VERO. La VC quantifica la complessità dello spazio → la varianza; VC alta = più overfitting.

(d) VERO. In tutti i casi, l'accuratezza del training error come stima migliora al crescere di N.

Kernel function: k(x,x')=φ(x)ᵀφ(x') — calcola il prodotto scalare nel feature space senza costruire φ esplicitamente. Deve essere simmetrica e semi-definita positiva. È una misura di similarità.

Kernel trick: ovunque compaia un prodotto scalare nello spazio trasformato, sostituiscilo con k(x,x'). Così lavori implicitamente in spazi enormi/infiniti senza costruirli.

Esempio: con φ(x₁,x₂)=(1,√2x₁,√2x₂,x₁²,√2x₁x₂,x₂²) (6 feature), il prodotto scalare risulta ⟨φ(x),φ(y)⟩=(1+xᵀy)² — calcolabile sugli input a 2D con un prodotto scalare e un quadrato. Il costo non dipende dalla dimensione del feature space.

La Gram matrix K è la matrice N×N con elementi Kₙₘ=φ(xₙ)ᵀφ(xₘ)=k(xₙ,xₘ). È la matrice (simmetrica) delle similarità di ogni campione con ogni altro.

Ruolo: nella rappresentazione duale l'intero problema si riscrive in termini di K (non delle feature φ). La soluzione duale è a=(K+λI)⁻¹t e la predizione y(x)=k(x)ᵀ(K+λI)⁻¹t. Deve essere semi-definita positiva (teorema di Mercer) perché k sia un kernel valido. Sposta la complessità dalla dimensione delle feature M al numero di campioni N.

Minimizzando la loss Ridge e ponendo il gradiente a zero, si vede che w=Σaₙφ(xₙ)=Φᵀa — w è combinazione lineare dei dati. Sostituendo si ottiene il sistema (λI+K)a=t, risolto da a=(K+λI)⁻¹t, e la predizione y(x)=k(x)ᵀ(K+λI)⁻¹t — solo kernel, nessun φ né w.

Perché due derivazioni: una parte dalla definizione delle dual variables, l'altra riscrive l'intera loss L(a) in termini di K e la minimizza. Entrambe convergono allo stesso sistema → dimostrano che il duale è un problema di ottimizzazione autonomo ed equivalente al primale (non solo una riparametrizzazione). Questo è essenziale per algoritmi come le SVM, dove φ è infinito-dimensionale e solo il duale è risolvibile.

• La soluzione è espressa solo tramite il kernel → si evita il calcolo esplicito in spazi ad alta dimensione.
• Si inverte una matrice N×N (Gram) invece di M×M → vantaggioso quando N≪M (o M infinito).
• Permette di lavorare con feature space infinito-dimensionali purché k sia calcolabile.
• I kernel si definiscono anche su oggetti non vettoriali (grafi, stringhe, testi) purché esista una misura di similarità valida.

(a) FALSO. Anche con φ noto, la forma duale può essere preferibile per motivi computazionali (dipende da N vs dimensione feature).

(b) VERO. È il kernel Gaussiano/RBF.

(c) FALSO. A è simmetrica ma NON è semi-definita positiva (autovalore negativo: det=1−4=−3<0) → non è un kernel valido (Mercer).

(d) FALSO. Per predire su x* serve anche il vettore k(x*,xᵢ) (e i coefficienti duali); K da sola non basta.

Condizioni di Mercer: continuo, simmetrico, semi-definito positivo.

(a) Valido purché a,b>0 (combinazione conica di kernel validi).

(b) NON valido: non è simmetrico (il primo termine ‖x‖² dipende solo da x).

(c) Valido: A è simmetrica e semi-definita positiva (det=3·4−1·1=11>0, traccia positiva) → xᵀAx' è un kernel valido (regola 8 di costruzione).

Definizione: K=ΦΦᵀ, matrice N×N con Kₙₘ=φ(xₙ)ᵀφ(xₘ)=k(xₙ,xₘ). È la matrice simmetrica delle similarità di ogni campione con ogni altro.

Ruolo: nella rappresentazione duale tutto il problema si riscrive tramite K, mai tramite φ. Soluzione a=(K+λI)⁻¹t, predizione y(x)=k(x)ᵀ(K+λI)⁻¹t.

Validità: per Mercer, k è un kernel valido ⟺ K è semi-definita positiva per ogni scelta di {xₙ}. Sposta la complessità da M (feature) a N (campioni).

Cos'è: sostituire ogni prodotto scalare φ(x)ᵀφ(x') con una funzione kernel k(x,x'), operando implicitamente in uno spazio ad alta dimensione senza mai calcolare φ.

A cosa serve: (1) rendere linearmente separabili dati che non lo sono nello spazio originale; (2) evitare il costo di calcolare/immagazzinare feature ad altissima (o infinita) dimensione. Attenzione: NON riduce il costo rispetto al numero di campioni N (il training SVM resta cubico in N) — riduce il costo rispetto al numero di feature.

Dove si usa: ovunque l'algoritmo dipenda solo da prodotti scalari — SVM, Ridge duale (kernel ridge regression), Perceptron kernelizzato, PCA (kernel PCA), K-NN, Gaussian Processes.

Metodo 1 (feature space first): scegli φ e ricava k(x,x')=Σᵢφᵢ(x)φᵢ(x').

Metodo 2 (costruzione diretta): definisci k e mostra che nasconde una φ. Es. k(x,z)=(xᵀz)² in 2D → φ(x)=(x₁²,√2x₁x₂,x₂²). Il kernel costa 2 moltiplicazioni + 1 quadrato; l'inner product esplicito 6 feature + 9 moltiplicazioni. Generalizzando, (xᵀz+c)ᵖ dà tutti i termini fino al grado p.

Metodo 3 (Mercer): condizione necessaria e sufficiente perché k sia valido è che la Gram matrix K sia semi-definita positiva per ogni scelta di {xₙ}, cioè xᵀKx≥0 ∀x≠0.

Regole di costruzione (dati k₁,k₂ validi): 1) ck₁ con c>0; 2) f(x)k₁f(x'); 3) q(k₁) con q polinomio a coeff. non-negativi; 4) exp(k₁); 5) k₁+k₂; 6) k₁k₂; 7) k₃(φ(x),φ(x')); 8) xᵀAx' con A simmetrica PSD; 9) kₐ+k_b su sotto-blocchi; 10) kₐ·k_b su sotto-blocchi.

Lineare: k=xᵀx' · Polinomiale: k=(xᵀx'+c)ᵈ · Gaussiano (RBF): k=exp(−‖x−x'‖²/2σ²).

Dimostrazione validità Gaussiano: espandendo ‖x−x'‖²=xᵀx+x'ᵀx'−2xᵀx' si ottiene
k=exp(−xᵀx/2σ²)·exp(xᵀx'/σ²)·exp(−x'ᵀx'/2σ²).
Il termine centrale è exp di un kernel lineare → valido per la regola (4). I due termini esterni hanno forma f(x)·…·f(x') → regola (2). Quindi il Gaussiano è valido.

Infinito-dimensionale: espandendo l'esponenziale in serie di Taylor si generano tutti i termini polinomiali di ogni grado → φ ha infinite componenti. È RBF perché dipende solo da ‖x−x'‖.

Non-vettoriali: insiemi k(A₁,A₂)=2^|A₁∩A₂|; modelli generativi k(x,x')=p(x)p(x') (inner product in uno spazio 1-D).

(a) VERO. Ponendo φ(x)=x+1 si ha k₁=φ(x)ᵀφ(y) — è un inner product per costruzione.

(b) FALSO. Non è simmetrico: il termine ‖x‖² dipende solo da x.

(c) VERO. Stessa trasformazione cos(·) applicata a entrambi gli argomenti (regola 7), e (·)³ è un polinomio a coefficienti non-negativi (regola 3) applicato a k₁ valido.

(d) VERO. Sviluppando: k₄=exp(2xᵀy−‖x‖²−‖y‖²)=exp(−‖x−y‖²) → kernel Gaussiano con σ²=½.

Intuitiva: non è una misura di similarità sensata — un elemento non risulta simile a sé stesso. Decomponendo: exp(xᵀx)·exp(2xᵀx')·exp(x'ᵀx'); a differenza del caso ‖x−x'‖, manca il segno meno, quindi non si può applicare la regola (2) (che dà condizioni solo sufficienti).

Formale (controesempio): in ℝ con dataset {1,−1}, si calcola la Gram matrix e il suo determinante (= prodotto degli autovalori) risulta negativo → almeno un autovalore negativo → K non è PSD → Mercer violato.

RBF: basi che dipendono solo dalla distanza radiale da un centro: φⱼ(x)=h(‖x−μⱼ‖). Una "campana" simmetrica: rilevatore di vicinanza. La rete è la somma pesata f(x)=Σⱼwⱼφⱼ(x) (mix di esperti locali).

Interpolazione esatta: una campana su ogni dato, f(x)=Σₙwₙh(‖x−xₙ‖₂), con N equazioni in N incognite → la curva passa per tutti i punti. Inutile in pratica: i dati ML sono rumorosi, quindi si insegue il rumore → overfitting.

Perché normalizzare: le campane sono localizzate, quindi in regioni lontane da tutti i centri tutte le basi valgono ≈0 → la predizione collassa (controllata solo dal bias, o troppo piccola): sono le "zone morte" (Fig. 3.33). Normalizzando, le basi sommano a 1 in ogni punto (partizione dell'unità) e la base del centro relativamente più vicino domina.

Tipi: a somma uᵢ=ρ(‖x−cᵢ‖)/Σⱼρ(‖x−cⱼ‖); softmax (esponenzia prima, competizione più netta); probabilistica (Parzen), interpretata come kernel density estimate.

Passo 1 — densità congiunta con Parzen: p(x,t)=(1/N)Σₙf(x−xₙ, t−tₙ): una campanella attorno a ogni coppia (xₙ,tₙ).

Passo 2 — media condizionata: y(x)=E[t|x]=∫t·p(x,t)dt / ∫p(x,t)dt.

Passo 3 — semplificazione: integrando su t, ∫(campanella)dt=g(x−xₙ) e ∫t(campanella)dt estrae tₙ (campanella simmetrica e centrata). Risulta:

y(x)=Σₙg(x−xₙ)tₙ / Σₘg(x−xₘ) = Σₙk(x,xₙ)tₙ, con k(x,xₙ)=g(x−xₙ)/Σₘg(x−xₘ) e g(x)=∫f(x,t)dt.

Lettura: la predizione è una media pesata dei target, con pesi = similarità kernel normalizzate. È k-NN "morbido": invece di contare i K vicini con peso secco 0/1, pesa tutti i punti in modo graduale con la distanza.

Nota: avendo stimato l'intera p(x,t), il modello dà non solo E[t|x] ma una distribuzione condizionata completa. È però un metodo plug-in/frequentista (nessun prior, nessun Bayes). Unico iperparametro: la bandwidth h (bias-variance, scelta in CV) — non c'è alcun σ² di rumore.

Definizione: distribuzione di probabilità sulle funzioni y(x) tale che, per qualsiasi insieme finito di punti {x₁,…,x_N}, i valori {y(x₁),…,y(x_N)} hanno congiuntamente distribuzione Gaussiana. Completamente specificato da: mean function m(x)=E[y(x)] (di solito 0) e covariance function k(x,x')=E[y(x)y(x')]. Si scrive y(x)∼GP(m(x),k(x,x')).

Derivazione: in y=Φw con prior p(w)=N(w|0,τI), y è combinazione lineare di gaussiane → è gaussiana. Quindi:
E[y]=ΦE[w]=0
cov[y]=E[yyᵀ]=ΦE[wwᵀ]Φᵀ=τΦΦᵀ=K
con Kₙₘ=k(xₙ,xₘ)=τφ(xₙ)ᵀφ(xₘ). Dunque p(y)=N(y|0,K).

Chiave concettuale: il salto è dal prior sui parametri al prior sulle funzioni. K codifica lisciezza e località: input simili → kernel grande → valori della funzione correlati → interpolazione liscia. Nella formula finale spariscono w e φ: resta solo il kernel (come nella rappresentazione duale). Il GP è non-parametrico: si lavora solo sull'insieme finito di punti {xₙ}, non su uno spazio infinito intrattabile.

Modello di osservazione: tₙ=y(xₙ)+εₙ, con εₙ∼N(0,σ²). Quindi p(t|y)=N(t|y,σ²I_N) e, dato il prior p(y)=N(0,K), la marginale è p(t)=∫p(t|y)p(y)dy=N(t|0,C) con C(xₙ,xₘ)=k(xₙ,xₘ)+σ²δₙₘ (le due gaussiane sono indipendenti → le covarianze si sommano; δ aggiunge σ² solo sulla diagonale).

Congiunta col nuovo punto: p(t_{N+1})=N(0,C_{N+1}) con matrice a blocchi C_{N+1}=[[C_N, k],[kᵀ, c]], dove kᵢ=k(xᵢ,x_{N+1}) e c=k(x_{N+1},x_{N+1})+σ².

Condizionamento gaussiano:
Media: m(x_{N+1})=kᵀC_N⁻¹t
Varianza: σ²(x_{N+1})=c−kᵀC_N⁻¹k

Media = Nadaraya-Watson / ridge duale: combinazione lineare dei target pesata da similarità kernel. Nessuna novità.

Perché la varianza cresce lontano: si parte dall'incertezza a priori c e si sottrae quanto il nuovo punto è spiegato dai dati. Se x* è vicino a molti punti, kᵀC⁻¹k è grande → varianza bassa. Se è lontano, k≈0 → la varianza resta ≈c → alta. Somma due sorgenti: rumore σ² (irriducibile) + incertezza sulla funzione (epistemica) — per questo con infiniti dati la banda non si azzera: resta σ².

Entrambi danno un p(t|x) e la stessa media (media pesata dei target). Ma:

NW è plug-in/frequentista: stima p(x,t) con Parzen (una singola stima puntuale) e ne legge la condizionata. Nessun prior, nessun Bayes. Il suo p(t|x) descrive la dispersione dei target osservati vicino a x → incertezza aleatoria (rumore).

GP è bayesiano: prior sulle funzioni (non sui pesi!) → posterior → predittiva. La sua varianza descrive l'ignoranza sulla funzione dovuta a pochi dati → incertezza epistemica, + il rumore σ².

Test decisivo (estrapolazione): lontano da tutti i dati, il GP fa esplodere la varianza ("non so"); NW invece riporta lo scatter dei punti meno lontani e resta stretto → overconfident.

Attenzione: né NW né GP mettono una distribuzione sui pesi (quella è la Bayesian Linear Regression). NW non ha nemmeno un σ² di rumore: ha solo la bandwidth.

(a) VERO. NW impone un prior su p(x,t) (congiunta input/output, via Parzen), mentre il GP considera un modello probabilistico solo sul target y. Entrambi derivano da tali prior la media della predizione.

(b) FALSO. I GP sono modelli non-parametrici: non è sempre possibile definire un vettore di parametri che riassuma il modello. Il "modello" è il training set stesso.

(c) VERO. L'inversione sarebbe O(N³), ma data l'inversa: la media kᵀC⁻¹t costa O(N) e la varianza c−kᵀC⁻¹k costa O(N²) (prodotto matrice-vettore). Quindi il costo di una predizione completa è quadratico.

(d) VERO. Con k(x,y)=xᵀy la media diventa m(x)=xᵀXCt=xᵀθ: è una regressione lineare il cui θ dipende interamente dal dataset.

(a) VERO. Il processo richiede di aggiungere una nuova riga e una nuova colonna alla Gram matrix e calcolare la similarità kernel per il punto aggiuntivo ogni volta che si include un nuovo campione. È analogo al recursive least squares applicato alla Gram matrix.

(b) VERO. In quel caso la base ha un numero infinito di feature. In generale, usare un kernel valido corrisponde a proiettare il dataset in uno spazio di feature a dimensione più alta: il GP è la regressione lineare bayesiana in quello spazio (con prior sui pesi che induce il kernel).

Costo: il collo di bottiglia è l'inversione di C_N, O(N³), ma si fa una sola volta per un dato training set. Poi: media O(N), varianza O(N²). Per dataset grandi si usano metodi approssimati: random sampling, clustering, sparse GP con inducing points.

Iperparametri (parametri del kernel, es. length-scale, e σ²): due strade —

• Cross-validation: griglia discreta di valori. Robusta ma lenta.
• Massimizzazione della marginal likelihood p(t) con ottimizzazione a gradiente. Più veloce, ma può cadere in ottimi locali.

Occam automatico: un modello troppo complesso "spalma" la probabilità su troppe funzioni possibili e assegna bassa likelihood ai dati osservati; uno troppo semplice non riesce a spiegarli. Il massimo di p(t) cade nel punto di equilibrio → bilancia fit e complessità senza validation set separato.

Cosa sono: modelli instance-based che cercano l'iperpiano a margine massimo. Dipendono solo da un sottoinsieme di punti critici, i support vector. Predizione: f(x_q)=sign(Σ_{m∈S}αₘtₘk(x_q,xₘ)+b).

Come funzionano: (1) si massimizza il margine → min ½‖w‖² s.t. tₙ(wᵀφ(xₙ)+b)≥1 (QP convesso); (2) si risolve con moltiplicatori di Lagrange passando al duale, dove compare il kernel; (3) le condizioni KKT (complementarità) fanno emergere i support vector; (4) con dati non separabili si usa il soft margin (slack ξₙ, parametro C).

Punti di forza: soluzione unica (problema convesso, no minimi locali, a differenza del perceptron); massimizzazione del margine → buona generalizzazione (margin bound); sparsità (dipende solo dai SV) → predizione efficiente; kernel trick → confini non lineari e spazi infinito-dimensionali; efficaci in alta dimensione.

Punti di debolezza: training costoso, O(N²)–O(N³) → non scala a N enormi; non probabilistico di base (serve Platt scaling); scelta di kernel e C richiede cross-validation; sensibile agli outlier vicino al confine; non nativamente online; spesso usato come black-box per la complessità teorica.

Il Perceptron predice con una somma sulle feature: f(x_q)=sign(Σ_{j=1}^{M} wⱼφⱼ(x_q)).

Poiché ogni correzione somma un punto misclassificato (w←w+tₙφ(xₙ)), alla fine w è sempre una combinazione lineare dei dati (forma duale): w=Σ_{n=1}^{N}αₙtₙφ(xₙ), dove αₙ = quante volte il punto n ha causato una correzione.

Sostituendo e riordinando le somme:

f(x_q)=sign(Σⱼ[Σₙαₙtₙφⱼ(xₙ)]φⱼ(x_q)) = sign(Σₙαₙtₙ k(xₙ,x_q))

La somma-sulle-feature è diventata somma-sui-campioni: invece di combinare pesi e feature, si confronta il nuovo punto con ciascun punto di training (tramite il prodotto scalare/kernel) e si combinano i confronti. Il Perceptron è quindi un caso particolare di apprendimento instance-based.

Guadagno: sostituendo il prodotto scalare (wⱼ·φⱼ) con una similarità arbitraria k(x,x') si ottiene un learner più potente. Se K è simmetrica e PSD, k è ancora un prodotto scalare in uno spazio trasformato. Soprattutto, questa formulazione garantisce l'ottimizzazione convessa dei pesi: nessun minimo locale, a differenza del perceptron.

• Soluzione: Perceptron → dipende da inizializzazione e ordine dei dati. SVM → ottimizzazione convessa, soluzione unica (dati K e i parametri).
• Cosa ottimizza: Perceptron → la distanza dai punti misclassificati. SVM → il margine definito dai SV.
• Iperpiano trovato: Perceptron → uno qualsiasi tra quelli separanti. SVM → quello a margine massimo.
• Non separabilità: Perceptron → la convergenza richiede separabilità lineare. SVM → richiede modifiche (soft margin / kernel).

Margine: distanza perpendicolare tra il confine wᵀφ(x)+b=0 e i punti più vicini (i SV) di entrambe le classi. Formalmente il punto critico è minₙ(tₙ(wᵀφ(xₙ)+b)). Si richiede classificazione corretta: tₙ(wᵀφ(xₙ)+b)>0.

Problema originale: w*=argmax_{w,b} (1/‖w‖₂)·minₙ(tₙ(wᵀφ(xₙ)+b)). È un max di un min con ‖w‖ al denominatore: scomodo da ottimizzare.

Trucco della scala: la stessa retta si può scrivere in infiniti modi — moltiplicare w e b per una costante non sposta il confine (invarianza di scala). Sfruttando questa libertà, si fissa la scala in modo che il punto più vicino soddisfi minₙ tₙ(wᵀφ(xₙ)+b)=1.

Conseguenze: (1) tutti i punti soddisfano tₙ(wᵀφ(xₙ)+b)≥1; (2) il margine diventa 1/‖w‖ (la "strada" intera è 2/‖w‖). Massimizzare 1/‖w‖ = minimizzare ‖w‖ = minimizzare ½‖w‖² (quadrato e ½ solo per pulizia dei conti).

Problema finale: min_{w,b} ½‖w‖²₂ s.t. tₙ(wᵀφ(xₙ)+b)≥1 ∀n — QP convesso con vincoli di disuguaglianza lineari → soluzione unica.

KKT per min f(w) con gᵢ(w)≤0 e hᵢ(w)=0:

• ∇L(w*,α*,λ*)=0 — stazionarietà
• hᵢ(w*)=0, gᵢ(w*)≤0 — primal feasibility
• αᵢ*≥0 — dual feasibility
• αᵢ*gᵢ(w*)=0 — complementarità: o gᵢ o αᵢ è nullo

Nella SVM: f(w)=½‖w‖²; i vincoli di disuguaglianza (uno per punto) sono gₙ(w,b)=1−tₙ(wᵀφ(xₙ)+b)≤0 con moltiplicatori αₙ≥0. Vincoli h di uguaglianza NON ce ne sono nel primale: l'unica uguaglianza Σαₙtₙ=0 nasce dopo, da ∂L/∂b=0.

Perché il segno meno: il vincolo in forma "≥0" è cₙ=tₙ(wᵀφ(xₙ)+b)−1≥0 e la Lagrangiana canonica è L=f(w)−Σαₙcₙ. Se il punto rispetta il vincolo (cₙ≥0), sottrarre αₙcₙ≥0 abbassa L (nessuna penalità). Se lo viola (cₙ<0), sottrarre un negativo aggiunge una quantità positiva → L sale: è la penalità che vogliamo, minimizzando. Formalmente min_{w,b} max_{α≥0} L: se un vincolo è violato il max interno manda αₙ→∞ e L esplode → il minimizzatore è costretto a rispettare i vincoli.

Perché il duale (3 motivi):

• Il kernel compare solo nel duale — i dati entrano esclusivamente come prodotti scalari k(xₙ,xₘ). Permette spazi di feature infiniti senza calcolare φ. Per una SVM non lineare è l'unica strada praticabile.
• Numero di variabili: primale = M (feature), duale = N (campioni). Conviene se M≫N.
• Sparsità: la soluzione in α ha moltissimi zeri (solo i SV sopravvivono).

È lecito perché il problema è convesso: primale e duale hanno lo stesso ottimo globale.

Derivazione: L(w,b,α)=½‖w‖²₂−Σₙαₙ{tₙ(wᵀφ(xₙ)+b)−1}. Annullando le derivate:

∂L/∂w=0 ⟹ w=Σₙαₙtₙφ(xₙ)  ·  ∂L/∂b=0 ⟹ Σₙαₙtₙ=0

Sostituendo (spariscono w e b) si ottiene il duale:

max_α L̃(α)=Σₙαₙ − ½ΣₙΣₘαₙαₘtₙtₘk(xₙ,xₘ),   s.t. αₙ≥0, Σₙαₙtₙ=0

Significato di Σαₙtₙ=0: è una condizione di equilibrio tra le classi: Σ_{tₙ=+1}αₙ = Σ_{tₙ=−1}αₙ. Le "spinte" delle due classi sull'iperpiano si bilanciano; nasce dall'aver lasciato libero il bias b.

Complementarità applicata alla SVM: αₙ{tₙ(wᵀφ(xₙ)+b)−1}=0.

• Se αₙ>0 ⟹ deve valere tₙy(xₙ)=1 → il punto sta esattamente sul bordo del margine: è un support vector.
• Se tₙy(xₙ)>1 (oltre il margine) ⟹ αₙ=0 → il punto non esercita alcuna forza sul confine.

Quindi w=Σₙαₙtₙφ(xₙ) è costruito solo dai support vector → sparsità.

Metafora: un muro è sorretto solo dai pali che lo toccano davvero; gli altri sono lì ma non spingono.

Grandezza di αₙ: non è un interruttore, è un peso graduato. In w=Σαₙtₙφ(xₙ) e in y(x)=sign(Σαₙtₙk(x,xₙ)+b), αₙ è il coefficiente con cui il punto contribuisce. αₙ grande = punto "load-bearing", ancora pesante che influenza fortemente dove si posiziona l'iperpiano e che tira con forza in predizione. αₙ appena sopra zero = SV "leggero", tocca il margine ma sorregge poco. I valori escono automaticamente dall'ottimizzazione duale.

Predizione: y(x)=sign(Σ_{n=1}^{N}αₙtₙk(x,xₙ)+b) — di fatto si somma solo sui SV (gli altri hanno αₙ=0).

Bias: b=(1/N_S)Σ_{n∈S}[tₙ − Σ_{m∈S}αₘtₘk(xₙ,xₘ)], con N_S≪N.

Perché la media: ogni singolo SV soddisfa tₙy(xₙ)=1, quindi da ciascuno si potrebbe ricavare b esattamente. Mediando su tutti i SV si ottiene stabilità numerica (si attenuano gli errori di arrotondamento). Nel soft margin si usano preferibilmente i SV con 0<αₙ<C, per cui tₙy(xₙ)=1 vale esattamente.

Il classificatore dipende solo dai SV, tramite le variabili duali αₙ e il kernel k.

Curse: al crescere delle dimensioni cresce il numero di support vector N_S; la frazione può diventare significativa → problemi di scalabilità e garanzie di generalizzazione più deboli (se quasi tutti i punti sono SV, il modello "memorizza").

Margin Bound (teoria VC): dipende inversamente dalla dimensione del margine ρ. Margine più grande ⟹ capacità effettiva minore ⟹ bound di generalizzazione migliore. È la giustificazione teorica del massimizzare il margine, ma è spesso pessimistico in pratica.

Leave-One-Out Bound (più stretto): L_h ≤ E[numero di SV]/N. Modelli con meno SV generalizzano meglio. Vantaggio: si calcola da un solo training, senza cross-validation esplicita.

Perché concordano: un margine più largo non "cattura" più punti — il margine è definito dai pochi punti che lo toccano. Margine largo è sintomo di nuvole ben separate, che richiedono pochi SV. Tanti SV nascono invece da dati sovrapposti, dove il margine utile è stretto. Quindi margine ampio e pochi SV descrivono la stessa situazione favorevole.

Il duale è un QP con N variabili (una per campione). I solver QP generici sono inefficienti su dataset grandi, quindi si usano algoritmi specializzati.

SMO (Sequential Minimal Optimization): spezza il grande QP nella serie dei più piccoli QP possibili:

• aggiorna un αᵢ alla volta;
• trova un esempio xᵢ che viola le condizioni KKT;
• seleziona un secondo campione xⱼ con un'euristica (di solito quello che viola di più);
• ottimizza congiuntamente αᵢ, αⱼ.

Perché coppie: per via del vincolo Σₙαₙtₙ=0. Muovendo un solo α si romperebbe quel vincolo di equilibrio; servono due variabili che si compensino.

Altri metodi: decomposition methods e interior point methods adattati alla struttura del problema SVM.

Problema: se i dati non sono separabili (nel feature space scelto), il vincolo hard tₙ(wᵀφ(xₙ)+b)≥1 non è soddisfacibile da tutti i punti → il problema non ha soluzione.

Slack: si introducono ξₙ≥0 che permettono violazioni: tₙ(wᵀφ(xₙ)+b)≥1−ξₙ. ξₙ misura di quanto un punto sfora:

• ξₙ=0: correttamente classificato, sul bordo o oltre il margine (come nel caso separabile);
• 0<ξₙ≤1: correttamente classificato, ma dentro il margine;
• ξₙ>1: misclassificato (ha attraversato il confine).

Ottimizzazione: min ½‖w‖²₂ + CΣᵢξᵢ   s.t. tᵢ(wᵀxᵢ+b)≥1−ξᵢ, ξᵢ≥0. Il primo termine vuole il margine largo, il secondo punisce le violazioni.

Ruolo di C (parametro di regolarizzazione, bias-variance):

• C piccolo ⟹ margine più largo ⟹ (potenzialmente) più violazioni → più bias, meno varianza;
• C grande ⟹ margine più stretto ⟹ meno violazioni → meno bias, più varianza; per C→∞ si torna al hard margin.

C si sceglie tipicamente in cross-validation. Intuizione: C = quanto sei severo con gli errori.

Duale soft margin: max_α L̃(α)=Σₙαₙ − ½ΣₙΣₘαₙαₘtₙtₘk(xₙ,xₘ), s.t. Σₙαₙtₙ=0 e 0≤αₙ≤C.

Unica differenza: il tetto αₙ≤C, detto box constraint. Notevole: le ξₙ e il termine di penalità spariscono dal duale — di loro resta solo quel tetto.

Hard margin (solo αₙ≥0, nessun tetto) — due stati:

• αₙ=0: oltre il margine, irrilevante;
• αₙ>0: esattamente sul bordo → support vector.

Soft margin — tre stati:

• αₙ=0: fuori dal margine, ben classificato (non è SV);
• 0<αₙ<C: sul margine (ξₙ=0, tₙy(xₙ)=1) → SV "classici" che definiscono la larghezza;
• αₙ=C (tetto raggiunto): dentro o oltre il margine (ξₙ>0) — o correttamente classificato dentro il corridoio (0<ξₙ≤1) o misclassificato (ξₙ>1).

Ruolo del tetto C: impedisce che un singolo outlier prenda peso illimitato — viene "tappato" a αₙ=C e non domina la soluzione. È la regolarizzazione vista dal lato duale. In entrambi i casi vale: SV = punto con αₙ>0. Così i SV si identificano anche senza nuvole ben distinte: li trova la matematica dei moltiplicatori, non l'occhio.

(a) FALSO. Le SVM sono modelli sparsi: il costo di predizione scala con il numero di support vector, non con N.

(b) FALSO. Più grande è C, minore è il bias (e maggiore la varianza). Su dati rumorosi serve esattamente l'opposto: C piccolo (più regolarizzazione, margine più largo, tollera violazioni).

(c) VERO. Applicando una funzione kernel, il problema può risultare linearmente separabile nel feature space, anche se non lo è nello spazio di input.

(d) FALSO. Il costo di training della SVM è purtroppo cubico nel numero di campioni. Il kernel trick limita il costo di calcolare un gran numero di feature, non il costo rispetto a N.

(1) wᵀp₁+b=[1,3]·[3,1]−2=3+3−2=4. Poiché 4>0 → classificato positivo.

(2) wᵀp₂+b=[1,3]·[0,1]−2=0+3−2=1. Il risultato è esattamente 1 → il punto cade sul margine positivo → è un support vector.

(3) Cerco x con wᵀx+b=0 ⟹ x₁+3x₂−2=0. Ponendo x₂=0 → x₁=2. Un punto sul boundary è [2,0].

(4) Due strade: Soft-Margin SVM (slack variables, che permettono violazioni/misclassificazioni con una penalità C) oppure Kernel Trick (mappare in uno spazio più alto — es. polinomiale o RBF — dove i dati possono diventare separabili, ottenendo un confine non lineare nello spazio originale). In entrambi i casi va rifatto il training.

(1) Boundary: −2x₁+x₂−3=0. Margine positivo: −2x₁+x₂−4=0. Margine negativo: −2x₁+x₂−2=0. (I margini sono i luoghi dove wᵀx+b=±1.)

(2) −2(0.9)+1(4.5)−3=−0.3 → classificato negativo.

(3) −2(0.5)+1(3.7)−3=−0.3 → classificato negativo, quindi correttamente classificato. Tuttavia |−0.3|<1: il punto cade dentro il margine → sì, bisogna ri-addestrare (violerebbe il vincolo hard-margin e diventerebbe un SV).

(4) Servirebbero i support vector (con i loro αₙ e tₙ) e la formula del kernel compresi tutti i suoi iperparametri. Il solo w non basta, perché nel caso kernel w vive nel feature space e non è calcolabile esplicitamente.

(1) Boundary: −2x₁+x₂−1=0 ⟹ x₂=2x₁+1. Dentro il margine: |−2x₁+x₂−1|<1 ⟹ 2x₁<x₂<2x₁+2.

(2) wᵀx+b=6+1−1=6>0 → la SVM lo classifica positivo, ma la sua classe vera è negativa (t=−1) → NON correttamente classificato.

Per soddisfare il vincolo soft: t(wᵀx+b)≥1−ξ ⟹ −6≥1−ξ ⟹ ξ≥7. Quindi la condizione compatibile è ξ>1 — coerente con la regola: ξ>1 ⟺ punto misclassificato.

(3) Usare un kernel non lineare (es. Gaussiano), che può rendere i dati separabili nel feature space. In aggiunta, aumentare C nella loss penalizza di più gli errori e riduce il numero di punti misclassificati (a costo di più varianza).

(1) Scopo: addestra una SVM con kernel RBF per classificare spam/non-spam, seleziona l'iperparametro C tra alcuni candidati e riporta la performance su un test set held-out. Righe 1–2: estrae X e il target binario y; riga 4: split 70/30; righe 9–15: per ogni C addestra, calcola l'accuracy sul training e tiene il modello migliore; righe 17–18: stampa C scelto e accuracy train/test.

(2) Ruolo di C: nella SVM soft-margin C>0 controlla la forza della regolarizzazione: C grande penalizza di più le misclassificazioni (fit più aderente, rischio di alta varianza); C piccolo aumenta la regolarizzazione (margine più largo, potenzialmente migliore generalizzazione).

(3) Problemi e fix:

• C selezionato massimizzando l'accuracy di training → bias verso l'overfitting (vince sempre il C più grande). Fix: usare un validation set separato o cross-validation sui dati di training per scegliere C.
• Accuracy come metrica può essere fuorviante con classi sbilanciate (tipico nello spam). Fix: usare precision, recall, F1-score, AUC.

(1) Il codice risolve un problema di classificazione con SVM usando due kernel diversi, confrontandone l'accuracy sul test set.

(2) Il primo kernel non è valido: ker_1=−‖x₁−x₂‖² è sempre negativo (o zero) → non può essere un prodotto scalare (viola Mercer/PSD).

Il secondo invece è valido: ker_2=exp(−‖x₁−x₂‖²) è esattamente il kernel Gaussiano (RBF).

Attenzione: anche togliendo il segno meno da ker_1 il kernel non diventerebbe valido. Un fix possibile è usare un kernel più semplice e sicuramente valido, come quello lineare.

1. "Separabile" va inteso nello spazio delle feature, non nel piano di input. Il kernel solleva i dati in alta dimensione dove spesso diventano separabili da un iperpiano; riportato indietro, il confine appare curvo. È per questo che nella Fig. 3.37 (Iris) kernel diversi disegnano confini di forma diversa.

2. L'unicità è "dato il kernel". Fissato un kernel e i suoi iperparametri, il problema è convesso → una sola soluzione ottima, e la convessità garantisce che gli algoritmi (SMO) vi convergano sempre (a differenza del perceptron). Cambiando kernel cambia il problema, quindi la soluzione. La scelta del kernel è model selection (cross-validation), non una debolezza.

3. Se non separabili nemmeno nel feature space: l'hard margin è irrealizzabile (nessun w soddisfa tutti i vincoli). Si usa il soft margin, che rilassa i vincoli con le slack e resta convesso.

4. Individuare i SV senza nuvole distinte: nel soft margin un SV è qualsiasi punto con αₙ>0. Quelli con 0<αₙ<C stanno sul margine; quelli con αₙ=C lo violano. Non servono "punti di bordo" visibili a occhio: li identifica la matematica dei moltiplicatori.

• Regressione (SVR): si adatta un iperpiano tale che la maggior parte dei punti stia dentro un tubo di ampiezza ε attorno alle predizioni. Robusta a outlier e rumore.
• Ranking SVM: ordina elementi per rilevanza, confrontando coppie di elementi e imparando una funzione di ranking.
• Feature Selection: identifica le feature importanti (quelle con pesi assoluti grandi), riducendo la dimensionalità.
• Support Vector Clustering: versione non supervisionata; assegna etichette iterativamente e raffina il confine sfruttando la massimizzazione del margine.
• Semi-supervised Learning: clusterizza i dati non etichettati per assegnare pseudo-etichette, poi addestra su dati etichettati + pseudo-etichettati.

Dipende quasi sempre dalla loss:

• Loss quadratica → sensibile (OLS, Ridge, Lasso, Least Squares for Classification, Bayesian LR, GP): l'errore cresce col quadrato del residuo e non satura mai, quindi un punto lontano domina la soluzione.
• Log-loss / hinge → robusta (Logistic Regression, SVM): la cross-entropy cresce solo linearmente e satura per i punti già classificati con sicurezza; la hinge loss ignora i punti ben classificati e lontani dal margine.
• Boosting → sensibile: ripesa i punti misclassificati, quindi gli outlier vengono amplificati iterazione dopo iterazione.
• Bagging → robusto: la media su B campioni bootstrap diluisce l'influenza degli outlier.
• PCA → sensibile: si basa sulla varianza, che gli outlier gonfiano, distorcendo le direzioni principali.
• K-NN → sensibile per K piccolo: con K=1 un solo vicino rumoroso ribalta la decisione.

Overfitting alto dove c'è solo ERM senza freni: OLS, Least Squares for Classification, Perceptron (non massimizza alcun margine), K-NN con K piccolo (K=1 memorizza il training). Basso dove agisce una regolarizzazione esplicita: Ridge/Lasso (penalità), Bayesian LR (prior), SVM (margine + C), ensemble (bagging riduce varianza, boosting riduce bias), Naive Bayes (bias forte dell'indipendenza), GP (marginal likelihood = Occam).

Online learning: SÌ nei metodi che aggiornano per singolo campione — Perceptron (nativamente), Logistic Regression (SGD), Naive Bayes (conteggi incrementali), K-NN (aggiunge il punto al magazzino), Bayesian LR (posterior di oggi = prior di domani), GP (aggiunge riga/colonna alla Gram matrix). NO nei metodi batch a forma chiusa o a ottimizzazione globale: OLS/Ridge/Lasso, Bagging/Boosting, PCA, SVM (QP batch; esistono varianti incrementali).

La regolarizzazione ha sempre lo stesso ruolo — spostare il bias-variance verso più bias e meno varianza — ma cambia forma: penalità L2 (Ridge) / L1 (Lasso, che azzera pesi → feature selection); prior bayesiano (prior gaussiano ⟺ Ridge, con λ=σ²/τ²); margine + parametro C (SVM); numero di vicini K (K-NN); numero di componenti k (PCA); shrinkage ed early stopping (Boosting); smoothing di Laplace (Naive Bayes); kernel + σ² (GP).