Lezione 22Support vector machines e kernel

Settimana: 8 · Fonte: slide del corso Machine Learning, Ingegneria dell'Automazione UniPD (lezione 22)

Argomenti trattati

1. Avvertenza d'esame: le SVM sono valutate solo nella parte teorica.
2. Classificatore a margine massimo: bordo di decisione, margine, sensibilità agli outlier (overfitting e alta varianza).
3. Margine morbido e Support Vector Classifier: variabili di scarto, parametro $C$ scelto per cross-validation; esempio sull'Iris (Virginica contro Versicolour, soli attributi del petalo) con $C$ da $0{,}01$ a $100$.
4. Formulazione: iperpiani $w\cdot x+b=0,\pm1$, margine $2/\|w\|$, problema convesso $\min\frac12\|w\|^2$ con vincoli, forma primale con hinge loss; la discesa del gradiente non è la scelta migliore (meglio SMO e solutori per programmazione quadratica).
5. Oltre i bordi lineari: espansione di base e suo costo, kernel trick (lineare, polinomiale, RBF, sigmoide), confronto su Moons, Circles e Iris.
6. Support Vector Regression con tubo $\varepsilon$.
7. Curva ROC e AUC applicate alle SVM sul dataset Moons (trattate in dettaglio in Metriche di classificazioneIn classificazione binaria ogni previsione è vero positivo (TP), vero negativo (TN), falso positivo (FP, errore di tipo I) o falso negativo (FN, errore di tipo II). Da queste quattro quantità: accuracy $=\frac{TP+TN}{TP+TN+FP+FN}$, specificità $=\frac{TN}{TN+FP}$, precision $=\frac{TP}{TP+FP}$, recall $=\frac{TP}{TP+FN}$, e la loro media armonica $F_1=\frac{2PR}{P+R}$. Con dati sbilanciati l'accuracy inganna (un modello che predice sempre la classe maggioritaria ha 99%): si usano precision, recall, F1, ROC-AUC, la cross-validation stratificata e il riequilibrio con undersampling o oversampling (non SMOTE). Cambiando la soglia sulla probabilità si ottiene la curva ROC (TPR contro FPR) e l'area AUC. Approfondimento: non nel programma di Telecomunicazioni.Metriche di classificazione →).

Teoria

• Support vector machines e metodi kernelUna SVM cerca l'iperpiano $w\cdot x+b=0$ che separa due classi con il margine più largo possibile: normalizzando $y_i(w\cdot x_i+b)\ge1$ il margine totale vale $2/|w|$, quindi si risolve $\min\frac12|w|^2$ (problema convesso, nessun minimo locale). Con classi sovrapposte si ammettono errori con le variabili di scarto $\xi_i$ e il parametro $C$ (soft margin, equivalente alla hinge loss più una penalità su $|w|^2$); $C$ piccolo = margine largo e più bias, $C$ grande = margine stretto e più varianza, si sceglie per cross-validation. La soluzione dipende solo dai vettori di supporto ($w=\sum\alpha_iy_ix_i$) e solo tramite prodotti scalari, per questo si può sostituire $x_i\cdot x_j$ con un kernel $K(x_i,x_j)=\langle\phi(x_i),\phi(x_j)\rangle$ (polinomiale, RBF) senza calcolare $\phi$: così si ottengono bordi non lineari. La SVR usa lo stesso schema con un tubo di tolleranza $\varepsilon$. Nell'esame le SVM sono solo nella parte teorica.Support vector machines e metodi kernel →

Esercizi

• Esercizio - SVM a margine rigido e morbido a mano
• Esercizio - Kernel e confronto tra SVM

Lezione precedente: Lezione 21 · Laboratorio anomaly detection e clustering Lezione successiva: Lezione 23 · Introduzione al deep learning