33 - Support Vector Machine: il margine massimo e il trucco del kernel

Due quartieri sono separati da un terreno vuoto e devi tracciare una strada che li divida. Puoi farla passare vicinissima alle case del primo quartiere o a quelle del secondo, oppure nel mezzo, il più lontano possibile da entrambi. Se un giorno qualcuno costruisce una casa leggermente fuori posto, la strada centrale è quella che continua a separare bene i due quartieri. Una Support Vector Machine (SVM) fa esattamente questo: tra tutti i confini che separano le classi, sceglie quello con il margine più largo.

Poi aggiunge due idee potenti: accettare qualche errore quando le classi non sono separabili, e il trucco del kernel, che permette confini curvi senza mai calcolare coordinate in spazi giganteschi. In questa lezione deriviamo la matematica, implementiamo una SVM lineare a mano, e vediamo dove la libreria si comporta in modo traditore.

Tre strumenti matematici, spiegati prima di usarli

• Prodotto scalare w · x = w₁x₁ + w₂x₂ + ... + w_nx_n. È un numero che dice «quanto x punta nella direzione di w». Se w è un vettore unitario, w · x è la lunghezza dell'ombra di x lungo w. Con pesi w fissati, è anche un punteggio: la somma pesata delle feature.
• Norma ‖w‖ = √(w₁² + ... + w_n²): la lunghezza del vettore. Dividere un vettore per la sua norma lo rende unitario.
• Problema convesso: un problema di ottimizzazione la cui funzione da minimizzare ha forma di conca, senza avvallamenti secondari. Ha un solo fondo e qualunque discesa lo trova.

I tre strumenti servono in tre momenti diversi. Il prodotto scalare dice da che parte del confine sta un punto, la norma trasforma quel punteggio in una distanza vera, e la convessità garantisce che l'addestramento abbia una sola risposta giusta. Se devi ricordarne uno, ricorda la norma: tutta la storia del margine è una divisione per ‖w‖. Un kernel, che compare nel titolo, è invece una funzione che misura la «somiglianza» tra due punti e permette all'SVM di tracciare confini curvi: lo definiamo più sotto, dopo aver capito il margine.

L'iperpiano e la distanza dal confine

In due dimensioni un confine lineare è una retta; in n dimensioni è un iperpiano, l'insieme dei punti x con

w · x + b = 0

dove w è il vettore dei pesi (perpendicolare all'iperpiano) e b l'intercetta. Un punto sta da una parte o dall'altra a seconda del segno di w · x + b. La distanza di un punto x dall'iperpiano è

d(x) = |w · x + b| / ‖w‖

Il fattore ‖w‖ compare perché moltiplicare w e b per una costante non cambia l'iperpiano, ma cambierebbe il valore di w · x + b: dividere per ‖w‖ rende la distanza indipendente da questa scelta arbitraria.

Nel disegno la retta nera è il confine; le due linee tratteggiate sono i bordi del margine; i punti cerchiati sono i vettori di supporto, quelli che «toccano» i bordi. Se togli un punto lontano, il confine non si muove: dipende solo dai punti più vicini a esso.

Il margine e il problema di ottimizzazione

Chiamiamo le due classi y = +1 e y = −1. Un classificatore corretto soddisfa y_i (w · x_i + b) > 0 per ogni punto. Siccome w e b si possono scalare liberamente, fissiamo la scala in modo che i punti più vicini al confine abbiano esattamente y_i (w · x_i + b) = 1. Questi punti si chiamano vettori di supporto. La loro distanza dall'iperpiano è 1/‖w‖ da ciascun lato, quindi il margine totale è

margine = 2 / ‖w‖

Massimizzare il margine equivale a minimizzare ‖w‖, ovvero (per comodità di derivazione) ½‖w‖². Il problema a margine rigido (hard margin) è:

minimizza   ½ ‖w‖²
soggetto a  y_i (w · x_i + b) ≥ 1    per ogni i

È un problema convesso: ha un unico minimo, nessun minimo locale ingannevole. Ma funziona solo se le classi sono perfettamente separabili da un iperpiano, e basta un punto fuori posto (rumore, un errore di etichetta) per renderlo impossibile.

Margine morbido: il parametro C

Si permette ad alcuni punti di violare il margine, pagando una penalità. Per ogni punto si introduce una variabile di slack ξ_i ≥ 0, la misura della violazione:

minimizza   ½ ‖w‖² + C · Σ_i ξ_i
soggetto a  y_i (w · x_i + b) ≥ 1 − ξ_i ,   ξ_i ≥ 0

Per un dato (w, b), il valore più piccolo ammissibile di ξ_i è max(0, 1 − y_i (w · x_i + b)). Sostituendolo, il problema diventa senza vincoli e si legge come «regolarizzazione + errore»:

minimizza   ½ ‖w‖² + C · Σ_i max(0, 1 − y_i (w · x_i + b))
                ↑ margine largo      ↑ hinge loss: errori e violazioni

La funzione max(0, 1 − m) con m = y(w·x+b) si chiama hinge loss: costa zero se il punto è correttamente classificato e fuori dal margine (m ≥ 1), e cresce linearmente man mano che il punto entra nel margine o dal lato sbagliato. Il parametro C regola il compromesso:

• C grande: ogni violazione costa molto, il modello cerca di classificare correttamente anche i punti rumorosi, margine stretto, rischio di overfitting.
• C piccolo: le violazioni costano poco, margine largo, il modello tollera errori, rischio di underfitting.

Le due voci non sono due modelli ma i due estremi della stessa manopola, e nessuno dei due valori è giusto in sé: dipende da quanto rumore c'è nelle etichette. C premia la precisione sul training, mentre 1/C premia la larghezza del margine. Più sotto una tabella misurata mostra che cosa succede ai vettori di supporto e al margine quando C passa da 0,001 a 1000, su dati che si sovrappongono davvero.

SVM lineare a mano

La forma senza vincoli si può minimizzare con la discesa del gradiente (la trovi per intero in La discesa del gradiente; qui basta l'idea: si fa un passo nella direzione che riduce l'errore). La hinge loss non è derivabile nel punto di giuntura, ma ha un sottogradiente semplice: dove il punto viola il margine (y(w·x+b) < 1) il contributo al gradiente è −y·x, altrove è zero. Dividendo l'obiettivo per C·n otteniamo (λ/2)‖w‖² + media della hinge, con λ = 1/(C·n):

Il termine λ·w viene dalla regolarizzazione, e agisce su ogni passo come una piccola forza che riporta w verso zero. Il secondo termine compare solo per i punti «violanti», cioè dentro il margine o dal lato sbagliato, e spinge w verso la loro etichetta. Scritto per esteso:

∂/∂w = λ·w − (1/n) · Σ_{i violanti} y_i x_i
∂/∂b =     − (1/n) · Σ_{i violanti} y_i

Il listato traduce queste due righe in NumPy: viola è la maschera dei punti che violano il margine, gw e gb sono le due derivate scritte sopra, e il passo lr decresce come 1/√t. Alla fine confronta il risultato con SVC(kernel="linear") di scikit-learn, che risolve lo stesso problema per un'altra via.

import numpy as np
from sklearn.datasets import make_blobs
from sklearn.svm import SVC

X, y01 = make_blobs(n_samples=200, centers=[(-1.5, -1), (1.5, 1)],
                    cluster_std=1.1, random_state=1)
y = 2 * y01 - 1                       # etichette in {-1, +1}

def svm_sgd(X, y, C=1.0, epochs=2000, lr0=0.5):
    n, d = X.shape
    lam = 1.0 / (C * n)
    w, b = np.zeros(d), 0.0
    for t in range(1, epochs + 1):
        viola = y * (X @ w + b) < 1                    # punti dentro il margine o sbagliati
        gw = lam * w - (y[viola, None] * X[viola]).sum(axis=0) / n
        gb = -y[viola].sum() / n
        lr = lr0 / np.sqrt(t)                           # passo decrescente
        w, b = w - lr * gw, b - lr * gb
    return w, b

w, b = svm_sgd(X, y)
sk = SVC(kernel="linear", C=1.0).fit(X, y)
w_sk = sk.coef_[0]

cos = w @ w_sk / (np.linalg.norm(w) * np.linalg.norm(w_sk))
print("accuratezza a mano / sklearn: %.3f / %.3f" % ((np.sign(X @ w + b) == y).mean(), sk.score(X, y)))
print("w a mano:", np.round(w, 3), " w sklearn:", np.round(w_sk, 3))
print("coseno tra le due direzioni: %.4f" % cos)
print("margine a mano %.3f   sklearn %.3f" % (2 / np.linalg.norm(w), 2 / np.linalg.norm(w_sk)))
print("vettori di supporto per classe (sklearn):", sk.n_support_, "su", len(X), "punti")

accuratezza a mano / sklearn: 0.950 / 0.950
w a mano: [1.31  0.889]  w sklearn: [1.415 0.914]
coseno tra le due direzioni: 0.9997
margine a mano 1.263   sklearn 1.187
vettori di supporto per classe (sklearn): [14 15] su 200 punti

Cosa fa il codice. make_blobs genera due nuvole gaussiane di 100 punti ciascuna attorno ai centri (−1,5; −1) e (1,5; 1), con deviazione 1,1: si sovrappongono un po', quindi il problema non è perfettamente separabile e serve il margine morbido. y = 2*y01 - 1 converte le etichette da {0,1} in {−1,+1}, come richiede la hinge loss. In svm_sgd il ciclo ripete 2000 volte: calcola il margine funzionale di ogni punto y * (X @ w + b), individua i punti che lo violano (valore minore di 1) nel vettore booleano viola, calcola il sottogradiente solo su quelli e fa un passo di ampiezza lr, decrescente come 1/√t (un passo che si riduce garantisce che la ricerca si assesti invece di oscillare). Nel confronto, SVC(kernel="linear") espone coef_ (il vettore w) e intercept_ (b).

La direzione di w coincide quasi perfettamente (coseno 0.9997) e l'accuratezza è identica; la norma è leggermente diversa perché la discesa del gradiente a passo decrescente è un'approssimazione, mentre la libreria risolve il problema in forma duale con precisione molto maggiore. Il margine è 1.26 contro 1.19. Osserva anche che i vettori di supporto sono 29 su 200 punti: solo loro determinano il confine. Si può togliere qualunque altro punto e il confine non si muove. Questa è la proprietà che dà il nome all'algoritmo.

Il trucco del kernel

Se i dati non sono separabili da un iperpiano nello spazio originale (due lune intrecciate, cerchi concentrici), l'idea è trasformare le feature con una mappa φ in uno spazio più grande dove diventano separabili, e usare lì un iperpiano. Un esempio concreto: in 2D non puoi separare con una retta i punti dentro un cerchio da quelli fuori; ma se aggiungi la coordinata x₁² + x₂² il cerchio diventa una soglia su una sola coordinata.

Il costo di questa idea sembra proibitivo: φ può mandare in migliaia (o infinite) dimensioni. Il trucco sta nella forma duale del problema, in cui i dati compaiono solo attraverso prodotti scalari tra coppie di punti:

f(x) = Σ_i α_i y_i ⟨φ(x_i), φ(x)⟩ + b      (α_i > 0 solo per i vettori di supporto)

Se esiste una funzione K(x, z) = ⟨φ(x), φ(z)⟩ calcolabile direttamente dai punti originali, non serve mai costruire φ. Un esempio che puoi verificare a mano: in due dimensioni, il kernel polinomiale K(x, z) = (x · z)² corrisponde a φ(x) = (x₁², √2·x₁x₂, x₂²). Infatti:

⟨φ(x), φ(z)⟩ = x₁²z₁² + 2·x₁x₂z₁z₂ + x₂²z₂²
             = (x₁z₁ + x₂z₂)²  =  (x · z)²

Controlliamo l'identità numericamente su due punti scelti a mano, x = (1, 2) e z = (3, −1): da un lato il prodotto scalare delle immagini phi(x) e phi(z) in tre dimensioni, dall'altro il kernel (x·z)² calcolato direttamente nelle due dimensioni originali.

phi = lambda v: np.array([v[0] ** 2, np.sqrt(2) * v[0] * v[1], v[1] ** 2])
x, z = np.array([1.0, 2.0]), np.array([3.0, -1.0])
print("kernel (x.z)^2 calcolato nello spazio originale:", (x @ z) ** 2)
print("prodotto scalare dopo la mappa phi, in 3D:      %.6f" % (phi(x) @ phi(z)))

kernel (x.z)^2 calcolato nello spazio originale: 1.0
prodotto scalare dopo la mappa phi, in 3D:      1.000000

Il codice verifica numericamente l'identità: phi trasforma un punto 2D in tre numeri (x₁², √2·x₁x₂, x₂²). Il prodotto scalare dei due punti trasformati vale 1,000000, e il kernel (x·z)² calcolato senza trasformare nulla vale 1,0 (qui x·z = 3 − 2 = 1). È il cuore del trucco: lo stesso risultato, con un calcolo in 2 dimensioni invece che in 3. Per kernel come l'RBF la mappa φ ha infinite dimensioni e il calcolo diretto è l'unica strada praticabile.

Il kernel più usato è il RBF (gaussiano): K(x, z) = exp(−γ‖x − z‖²). Corrisponde a una φ con infinite dimensioni, e si interpreta come una «similarità»: vale 1 per punti coincidenti e tende a 0 al crescere della distanza. Il parametro γ regola il raggio di influenza di ogni punto: γ grande significa influenza locale (confine molto frastagliato), γ piccolo influenza ampia (confine liscio, quasi lineare).

Confronto dei kernel su dati non lineari

from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

Xm, ym = make_moons(n_samples=600, noise=0.25, random_state=0)
Xt, Xe, yt, ye = train_test_split(Xm, ym, test_size=0.3, stratify=ym, random_state=0)

for kernel in ("linear", "poly", "rbf"):
    m = make_pipeline(StandardScaler(), SVC(kernel=kernel, C=1.0)).fit(Xt, yt)
    print("%-6s train %.3f  test %.3f  vettori di supporto: %d" % (
        kernel, m.score(Xt, yt), m.score(Xe, ye), m[-1].n_support_.sum()))

linear train 0.886  test 0.856  vettori di supporto: 126
poly   train 0.876  test 0.839  vettori di supporto: 135
rbf    train 0.936  test 0.917  vettori di supporto: 103

Cosa fa il codice. make_moons produce due semicerchi intrecciati con rumore 0,25 (600 punti, 420 di training). La Pipeline concatena StandardScaler (che porta ogni feature a media 0 e deviazione 1, usando solo il training) e SVC; l'attributo m[-1] prende l'ultimo passo della pipeline per leggere n_support_, il numero di vettori di supporto per classe.

Il kernel RBF batte il lineare sul test (0.917 contro 0.856): il confine curvo segue la forma delle due lune. Il kernel polinomiale (grado 3 per default) qui non aiuta: un kernel più espressivo non è automaticamente migliore. Nota anche che il numero di vettori di supporto è alto (103 su 420 punti di training con l'RBF, circa uno su quattro): con classi che si sovrappongono molti punti finiscono dentro il margine.

Overfitting con C e gamma: l'accuratezza di training che mente

Con C grande e γ grande l'SVM può «accerchiare» ogni singolo punto di training. Guarda cosa succede fissando C = 1000 e variando γ:

for gamma in (0.1, 1, 10, 100, 1000):
    m = make_pipeline(StandardScaler(), SVC(kernel="rbf", C=1000, gamma=gamma)).fit(Xt, yt)
    print("gamma %6.1f  train %.3f  test %.3f  vettori di supporto: %d" % (
        gamma, m.score(Xt, yt), m.score(Xe, ye), m[-1].n_support_.sum()))

gamma    0.1  train 0.957  test 0.917  vettori di supporto: 66
gamma    1.0  train 0.964  test 0.911  vettori di supporto: 50
gamma   10.0  train 1.000  test 0.867  vettori di supporto: 109
gamma  100.0  train 1.000  test 0.856  vettori di supporto: 378
gamma 1000.0  train 1.000  test 0.667  vettori di supporto: 419

Cosa fa il codice: tiene C fisso a 1000 e fa variare γ su cinque ordini di grandezza, stampando accuratezza di training, di test e numero di vettori di supporto. Il test set qui serve solo a mostrare il fenomeno: in un progetto vero sceglieresti γ con la validazione incrociata sul training.

L'accuratezza di training sale a 1.000 già con γ = 10, mentre quella di test scende da 0.917 (γ = 0.1) a 0.667 (γ = 1000): il modello ha memorizzato il rumore. Il numero di vettori di supporto è un campanello d'allarme utile: con γ = 1000 sono 419 su 420, cioè quasi ogni punto è un vettore di supporto e il modello sta memorizzando. I due iperparametri vanno scelti con la validazione incrociata (GridSearchCV), cercando su scala logaritmica (0.001, 0.01, 0.1, 1, 10...), mai con il test set.

La trappola della scala delle feature

L'SVM con kernel RBF si basa su distanze euclidee: una feature con valori nell'ordine delle migliaia domina tutte le altre. Per mostrarlo moltiplichiamo per 1000 una delle feature informative di un dataset sintetico:

from sklearn.datasets import make_classification

Xc, yc = make_classification(n_samples=600, n_features=5, n_informative=3,
                             n_redundant=0, random_state=3)
Xc[:, 0] *= 1000                                   # una feature con scala enorme
Xa, Xb, ya, yb = train_test_split(Xc, yc, test_size=0.3, stratify=yc, random_state=0)

print("senza scaling: test %.3f" % SVC().fit(Xa, ya).score(Xb, yb))
print("con scaling:   test %.3f" % make_pipeline(StandardScaler(), SVC()).fit(Xa, ya).score(Xb, yb))

senza scaling: test 0.817
con scaling:   test 0.950

Cosa fa il codice: make_classification con 3 feature informative su 5; poi Xc[:, 0] *= 1000 moltiplica per mille la prima colonna, simulando per esempio un importo in euro accanto a percentuali. Le due righe di valutazione addestrano lo stesso SVC con e senza lo StandardScaler.

Stesso modello, stessi dati: la sola standardizzazione sposta l'accuratezza da 0.817 a 0.950. Lo scaler va dentro la Pipeline (altrimenti calcoleresti media e deviazione sul dataset intero e faresti data leakage, come spiega il processo di un progetto di ML).

Trade-off

• Pro: efficace in spazi ad alta dimensione, ottimo con pochi dati, problema convesso (nessun minimo locale), i kernel permettono confini non lineari, memoria contenuta (si tengono solo i vettori di supporto).
• Contro: l'addestramento scala male col numero di campioni (la documentazione di scikit-learn dà una scala tra n_features·n_samples² e n_features·n_samples³ per l'implementazione basata su libsvm): con centinaia di migliaia di righe diventa lento; richiede scaling; iperparametri delicati; non produce probabilità nativamente (probability=True aggiunge una calibrazione con validazione incrociata a cinque fold, che la documentazione definisce costosa).
• Scelta pratica: dataset piccoli o medi con molte feature → SVM RBF è un ottimo candidato; dataset enormi → LinearSVC o SGDClassifier, oppure modelli ad alberi.

Pro e contro sono due facce della stessa struttura: la soluzione dipende dai soli vettori di supporto, quindi è compatta e robusta, ma per trovarli il solver deve confrontare coppie di campioni, e il costo cresce in fretta. La regola pratica è dunque di scala. Fino a qualche migliaia o decine di migliaia di righe l'RBF è un buon candidato; oltre, la scelta è lineare o ad alberi. Se ti servono probabilità, metti in conto il costo della calibrazione.

Trappole reali

• Dimenticare lo StandardScaler (vedi sopra).
• Scegliere C e γ guardando il test set: usa GridSearchCV sul training.
• Etichette in {0,1} nell'implementazione a mano: la hinge loss richiede {−1,+1}. Misurato sostituendo y con y01 nella chiamata a svm_sgd: nessun errore, w = (0,131; 0,009), e l'accuratezza contro le vere etichette scende a 0,500, cioè il caso.
• Classi sbilanciate: usa class_weight="balanced" e valuta con precision/recall.
• Aspettarsi probabilità calibrate da decision_function: è una distanza con segno, non una probabilità.

Le cinque trappole non pesano allo stesso modo. Le prime due falsano la misura in silenzio: il modello sembra buono perché è stato valutato male. La terza produce un modello assurdo senza alcun errore. Le ultime due riguardano come leggere il risultato, non come ottenerlo. Se devi controllare una cosa sola prima di consegnare un modello, controlla che lo scaler stia dentro la pipeline.

Il parametro C visto da vicino: margine, vettori di supporto e accuratezza

Nella derivazione hai visto che C regola il compromesso tra un margine largo e pochi errori. Lo misuriamo su un problema con classi che si sovrappongono (due nuvole gaussiane vicine, quindi non separabili): per ogni C addestriamo una SVM lineare e leggiamo il numero di vettori di supporto, la larghezza del margine 2/‖w‖ calcolata da coef_, e l'accuratezza su training e test (200 punti ciascuno, quindi un solo punto vale 0,005). In coda stampiamo le tre funzioni di perdita, errore 0-1, hinge e logistica, calcolate per sette valori del margine funzionale m.

from sklearn.datasets import make_blobs, load_digits, make_classification
from sklearn.model_selection import train_test_split

X_ov, y_ov = make_blobs(n_samples=400, centers=[(-1, -0.7), (1, 0.7)], cluster_std=1.3, random_state=2)
X_ov_tr, X_ov_te, y_ov_tr, y_ov_te = train_test_split(X_ov, y_ov, test_size=0.5, stratify=y_ov, random_state=0)

print("C         vettori di supporto   larghezza del margine   acc. training   acc. test")
for C in (0.001, 0.01, 0.1, 1, 10, 1000):
    m = SVC(kernel="linear", C=C).fit(X_ov_tr, y_ov_tr)
    margin = 2 / np.linalg.norm(m.coef_[0])
    print("%-8g  %12d             %10.3f          %9.3f        %9.3f" % (C, m.n_support_.sum(), margin, m.score(X_ov_tr, y_ov_tr), m.score(X_ov_te, y_ov_te)))

# le tre funzioni di perdita, come funzione del margine funzionale m = y (w.x + b)
margins = np.array([-2, -1, -0.5, 0, 0.5, 1, 2])
print("\nm              ", margins)
print("errore 0-1     ", (margins <= 0).astype(int))
print("hinge (SVM)    ", np.round(np.maximum(0, 1 - margins), 3))
print("logistica     ", np.round(np.log(1 + np.exp(-margins)), 3))

C         vettori di supporto   larghezza del margine   acc. training   acc. test
0.001              200                  7.963              0.805            0.780
0.01               123                  3.573              0.805            0.795
0.1                 90                  2.315              0.805            0.805
1                   82                  2.040              0.825            0.800
10                  82                  2.041              0.825            0.800
1000                82                  2.040              0.825            0.800

m               [-2.  -1.  -0.5  0.   0.5  1.   2. ]
errore 0-1      [1 1 1 1 0 0 0]
hinge (SVM)     [3.  2.  1.5 1.  0.5 0.  0. ]
logistica      [2.127 1.313 0.974 0.693 0.474 0.313 0.127]

La tabella racconta tre fasi. Con C = 0,001 la penalità per le violazioni è così bassa che tutti i 200 punti di training diventano vettori di supporto e il margine si allarga a 7,96. Con C = 0,1 i vettori scendono a 90, il margine a 2,32 e l'accuratezza di test tocca il massimo della tabella, 0,805. Da C = 1 in su la soluzione non cambia più (82 vettori, margine 2,04): in questo esperimento oltre quella soglia il termine C·Σξ domina e le violazioni sono già al minimo possibile. Attenzione però alla scala delle differenze: tra 0,780 e 0,805 sul test ballano cinque punti su 200, quindi non leggerei «C = 0,1 è il migliore» come una scoperta, ma come l'indicazione che i valori molto piccoli sottoadattano.

Le righe sotto mostrano perché la SVM si chiama così. La hinge vale zero per m ≥ 1 (il punto è fuori dal margine e non produce alcun gradiente), mentre la perdita logistica, che è quella della regressione logistica, non arriva mai a zero: anche un punto lontano e ben classificato continua a contribuire un poco. È la stessa proprietà dei vettori di supporto vista dalla parte della perdita.

Più di due classi: uno contro uno, uno contro tutti

L'SVM è nata per due classi. Per K classi si compongono più classificatori binari. Nella strategia uno contro tutti (OvR) se ne addestrano K, ciascuno «classe k contro il resto», e si sceglie la classe con il punteggio più alto. Nella strategia uno contro uno (OvO) se ne addestrano K(K − 1)/2, uno per ogni coppia di classi, e si decide per voto di maggioranza. Con le 10 cifre di Digits: 10 classificatori contro 45. Misuriamo accuratezza e tempo di addestramento, aggiungendo come riferimento una SVM lineare (LinearSVC), che non usa kernel.

Il listato fa due cose: confronta le tre strategie multiclasse sulle cifre e poi misura quanto cresce il tempo di fit al raddoppiare dei campioni. Il tempo è letto con time.time() attorno al solo fit; il rapporto con la riga precedente (t_rbf / previous) è ciò che interessa, non il valore assoluto.

import time
from sklearn.svm import LinearSVC
from sklearn.multiclass import OneVsRestClassifier

X_d, y_d = load_digits(return_X_y=True)
X_d_tr, X_d_te, y_d_tr, y_d_te = train_test_split(X_d, y_d, test_size=0.3, stratify=y_d, random_state=0)

models = {"SVC RBF, uno contro uno (default)": SVC(kernel="rbf"),
          "SVC RBF, uno contro tutti": OneVsRestClassifier(SVC(kernel="rbf")),
          "LinearSVC (lineare, uno contro tutti)": LinearSVC(max_iter=5000)}
for name, clf in models.items():
    pipe = make_pipeline(StandardScaler(), clf)
    t0 = time.time(); pipe.fit(X_d_tr, y_d_tr); elapsed = time.time() - t0
    print("%-52s accuratezza %.3f   tempo di addestramento %.2f s" % (name, pipe.score(X_d_te, y_d_te), elapsed))

print("\ntempo di addestramento al crescere dei campioni (20 feature):")
print("n          SVC (RBF)     LinearSVC")
previous = None
for n in (1000, 2000, 4000, 8000):
    X_n, y_n = make_classification(n_samples=n, n_features=20, n_informative=8, random_state=0)
    X_n = StandardScaler().fit_transform(X_n)
    t0 = time.time(); SVC().fit(X_n, y_n); t_rbf = time.time() - t0
    t0 = time.time(); LinearSVC(max_iter=5000).fit(X_n, y_n); t_lin = time.time() - t0
    print("%-9d  %8.3f s    %8.3f s    %s" % (n, t_rbf, t_lin, "" if previous is None else "(×%.1f rispetto a n/2)" % (t_rbf / previous)))
    previous = t_rbf

# Uscita (una esecuzione; i tempi cambiano a ogni esecuzione)
# SVC RBF, uno contro uno (default)                    accuratezza 0.981   tempo di addestramento 0.09 s
# SVC RBF, uno contro tutti                            accuratezza 0.980   tempo di addestramento 0.21 s
# LinearSVC (lineare, uno contro tutti)                accuratezza 0.948   tempo di addestramento 0.37 s
#
# tempo di addestramento al crescere dei campioni (20 feature):
# n          SVC (RBF)     LinearSVC
# 1000          0.021 s       0.002 s    
# 2000          0.079 s       0.004 s    (×3.7 rispetto a n/2)
# 4000          0.231 s       0.008 s    (×2.9 rispetto a n/2)
# 8000          0.525 s       0.016 s    (×2.3 rispetto a n/2)

Il primo confronto addestra tre varianti sulle cifre (10 classi, 1 797 immagini 8×8), sempre con la standardizzazione dentro la Pipeline. L'accuratezza è 0,98 per la SVM con kernel RBF, sia con la strategia uno contro uno (la scelta predefinita: la documentazione di SVC la indica come schema multiclasse) sia con OneVsRestClassifier; LinearSVC arriva a 0,95. Il kernel serve: c'è un divario di tre punti rispetto al modello lineare. Sui tempi, in due esecuzioni consecutive uno contro uno ha impiegato 0,07-0,09 s contro 0,16-0,21 s di uno contro tutti: l'ordine è stato lo stesso entrambe le volte, ma sono decimi di secondo su una sola macchina e non devono guidare la scelta. La spiegazione plausibile è che i 45 classificatori di uno contro uno vedono ciascuno solo due classi, quindi pochi dati, e il costo di una SVM con kernel cresce più che linearmente.

Il secondo esperimento è quello che conta. Passando da 1 000 a 8 000 campioni (otto volte i dati) l'SVM con kernel ha impiegato, in sei esecuzioni separate, da 17 a 30 volte il tempo, cioè un esponente tra 1,4 e 1,6; LinearSVC da 5 a 9 volte. Misure dell'autore, 2026-11-12, 12 thread logici, Python 3.14.4, scikit-learn 1.8.0: variano da una esecuzione all'altra, e a questi valori di n non mostrano ancora la legge asintotica. La documentazione di SVC dice che il tempo di addestramento cresce almeno quadraticamente con i campioni e che può essere impraticabile oltre qualche decina di migliaia, e consiglia LinearSVC o SGDClassifier, eventualmente dopo un'approssimazione del kernel. Non estrapolare da 8 000 a 800 000 con il mio esponente: fidati del limite documentato.

Dentro la soluzione duale: la decisione come somma sui vettori di supporto

Nella derivazione abbiamo affermato che la funzione di decisione si scrive come f(x) = Σ_i α_i y_i K(x_i, x) + b, con α_i diversi da zero solo per i vettori di supporto. Verifichiamolo ricostruendo a mano le previsioni di un SVC dai suoi attributi interni: support_vectors_ (i punti x_i), dual_coef_ (i prodotti α_i y_i) e intercept_ (b). Per il kernel RBF si calcola K(x_i, x) = exp(−γ‖x_i − x‖²), con γ = 0,5 fissato nel listato (gamma=0.5, al posto del valore predefinito 'scale') in modo che la formula a mano usi lo stesso numero della libreria.

X_m, y_m = make_blobs(n_samples=300, centers=[(-1, -0.7), (1, 0.7)], cluster_std=1.1, random_state=5)
rbf = SVC(kernel="rbf", C=1.0, gamma=0.5).fit(X_m, y_m)

SV = rbf.support_vectors_                                         # (n_sv, 2): i vettori di supporto x_i
alpha_y = rbf.dual_coef_[0]                                       # (n_sv,): i prodotti alpha_i * y_i

def decision_by_hand(x_new):
    d2 = ((SV[None, :, :] - x_new[:, None, :]) ** 2).sum(axis=2)  # (n_new, n_sv): distanze al quadrato
    return (np.exp(-0.5 * d2) @ alpha_y) + rbf.intercept_[0]      # sum_i alpha_i y_i K(x_i, x) + b

x_test = np.array([[0.0, 0.0], [2.0, 1.5], [-2.0, -1.0], [0.5, -1.0]])
print("vettori di supporto: %d su %d punti (%.0f%%)" % (len(SV), len(X_m), 100 * len(SV) / len(X_m)))
print("decisione a mano:      ", np.round(decision_by_hand(x_test), 4))
print("decision_function:     ", np.round(rbf.decision_function(x_test), 4))
print("max |differenza| su tutto il training: %.2e" % np.abs(decision_by_hand(X_m) - rbf.decision_function(X_m)).max())

# nel caso lineare la somma si può comprimere in un solo vettore w = sum_i alpha_i y_i x_i
lin = SVC(kernel="linear", C=1.0).fit(X_m, y_m)
w_from_dual = lin.dual_coef_[0] @ lin.support_vectors_
print("w ricostruito dalla forma duale: %s   coef_ di scikit-learn: %s" % (np.round(w_from_dual, 4), np.round(lin.coef_[0], 4)))

vettori di supporto: 108 su 300 punti (36%)
decisione a mano:       [-0.1481  1.0233 -1.0086 -0.049 ]
decision_function:      [-0.1481  1.0233 -1.0086 -0.049 ]
max |differenza| su tutto il training: 0.00e+00
w ricostruito dalla forma duale: [1.405  0.7192]   coef_ di scikit-learn: [1.405  0.7192]

Il listato ha tre parti. Addestra una SVM con kernel RBF e ne estrae i tre ingredienti della formula duale. decision_by_hand calcola, per ogni nuovo punto, le distanze al quadrato da tutti i vettori di supporto con il broadcasting (forma (n_nuovi, n_sv)), le trasforma in similarità RBF con exp(−γ d²), le pesa per α_i y_i e somma, aggiungendo il bias. I valori coincidono con decision_function di scikit-learn su tutto il training, con una differenza massima nulla in questa esecuzione (al più dell'ordine di 10⁻¹⁵): la formula duale non è un'astrazione, è esattamente ciò che la libreria calcola. Questo ha una conseguenza concreta: il costo della previsione è proporzionale al numero di vettori di supporto, perché ogni nuovo punto va confrontato con ciascuno; con kernel lineare invece la somma si comprime in un solo vettore w = Σ α_i y_i x_i (l'ultima riga lo mostra: coincide con coef_) e la previsione costa una sola moltiplicazione.

Ne segue che un modello con troppi vettori di supporto è lento e ingombrante in produzione, e che un C piccolo, che ne produce molti, non è «gratuito» in termini di costo di inferenza.

Come scegliere il kernel e gli iperparametri: una procedura

1. Standardizza (dentro la pipeline). Senza è la causa più frequente di risultati scadenti.
2. Parti dal lineare (LinearSVC o SVC(kernel="linear")): veloce, e dice subito se i dati sono quasi separabili con una retta.
3. Passa all'RBF se il lineare è insufficiente. Cerca C e γ su una griglia logaritmica (per esempio C in 10⁻²...10³ e γ in 10⁻⁴...10¹) con la validazione incrociata sul solo training.
4. Controlla il numero di vettori di supporto: se è quasi tutto il training, il modello sta memorizzando (γ troppo grande) o il problema è molto rumoroso.
5. Confronta con modelli più semplici e con più semi: una regressione logistica o una foresta spesso fa altrettanto bene con meno messa a punto.

L'ordine dei cinque passi non è casuale. La standardizzazione viene per prima perché cambia le distanze su cui lavora l'RBF; il modello lineare viene prima dell'RBF perché è il termine di confronto, e se basta ti fermi. La griglia arriva solo dopo, perché cercare C e γ su un modello che non ne ha bisogno spreca tempo. Due aggiunte: guarda l'altopiano intorno al massimo della griglia, perché un picco isolato è una scelta fragile; e ricorda che la previsione costa quanto il numero di vettori di supporto. Se servono probabilità, la documentazione indica probability=True (scaling di Platt, con validazione incrociata interna) o CalibratedClassifierCV, da validare a parte.

Tre prove da fare

Esercizio 1. Ripeti l'esperimento su C con i dati separabili (cluster_std=0.6): il margine continua a variare per C grandi? Esercizio 2. Calcola a mano il numero di classificatori binari di OvO per 100 classi: quanto cresce rispetto a OvR? Esercizio 3. Usa SVC(kernel="rbf", probability=True) e misura quanto più lento diventa l'addestramento: è il costo della calibrazione interna delle probabilità.

Se vuoi allenarti sullo stesso argomento con un dominio diverso, distinguere olio extravergine e lampante da due indici chimici, c'è uno scheletro di esercizi in Python con tre parti da completare (l'iperpiano dai vettori di supporto, il kernel, la scala). Usa solo NumPy e, finché i punti da completare sono vuoti, stampa quali esercizi mancano.

Che cosa sai fare adesso

Sai ricavare il margine 2/‖w‖ e spiegare che cosa cambia con C, sai verificare a mano che il kernel è un prodotto scalare in uno spazio che non costruisci, sai riconoscere dal numero di vettori di supporto un modello che sta memorizzando, e sai scegliere tra SVM lineare, RBF e alternative in base al numero di righe. Nella lezione successiva, KNN, il confine sparisce del tutto: si classifica guardando i vicini più prossimi.

Fonti

Lezione precedente del percorso: Naive Bayes: il teorema di Bayes con un'ipotesi ingenua. Nella stessa serie rimandano a questa lezione anche: Ottimizzazione vincolata: moltiplicatori di Lagrange, dualità e condizioni KKT.