Support Vector Machine: il margine massimo#
Disegna due nuvole di punti su un foglio (pallini blu a sinistra, quadratini rossi a destra) e traccia una retta che li separi. Facile. Ora traccia un’altra retta che li separi lo stesso, e poi un’altra ancora: se le due nuvole sono ben distinte, di rette buone ce ne sono infinite. Quale scegliere? La regressione logistica della sezione sull’apprendimento supervisionato ne sceglie una, e nemmeno si pone la domanda. La Support Vector Machine (SVM) invece sì, e con una risposta di netta eleganza geometrica: tra tutte le rette che separano, scegli la più prudente (quella che lascia il corridoio più largo possibile tra le due classi).
L’idea del margine massimo è vecchia, e non nasce dove si crede: nasce a Mosca, all’Istituto di Problemi di Controllo, dove dal 1962 Vladimir Vapnik ne discuteva con Alexander Lerner e Alexey Chervonenkis. Il nome era metodo del ritratto generalizzato, e lo pubblicano Vapnik e Lerner nel 1963 [VL63]; l’anno dopo Vapnik e Chervonenkis ne ricavano il classificatore lineare a margine rigido. Quello che nasce trent’anni dopo nei laboratori Bell sono i due innesti che la rendono praticabile: il kernel trick (Boser, Guyon e Vapnik, 1992 [BGV92]) e il margine morbido (Cortes e Vapnik, 1995 [CV95]). Un algoritmo che ha aspettato trent’anni due idee.
Per un decennio, prima dell’ondata del deep learning, le SVM sono state il classificatore di riferimento: matematicamente solide, sorprendentemente efficaci su dataset di dimensioni medie, e ancora oggi una scelta sensata quando gli esempi sono poche migliaia.
La retta più prudente#
Il criterio si scrive in una riga. Presa una frontiera che divide le due classi, si guarda quanto dista dall’esempio più vicino di ciascuna: quella distanza è il margine, e fra tutte le frontiere possibili la SVM prende quella di margine massimo. Il motivo è la robustezza. Una frontiera che passa rasente agli esempi già visti sbaglia il primo esempio nuovo che cade poco più in là; una che li tiene tutti lontani ha del gioco prima di sbagliare, e quanto gioco lo dice il margine stesso.
Fig. 4.26 Tra le infinite rette che separano le due classi, la SVM sceglie quella che massimizza il margine: la larghezza del corridoio tra i punti più vicini. Solo quei punti (i vettori di supporto, cerchiati in ocra) determinano la soluzione.#
Come mostra Fig. 4.26, la soluzione poggia su pochissimi punti: quelli che toccano i bordi del corridoio. Tutti gli altri, per quanto numerosi, sono irrilevanti: potresti spostarli o cancellarli e il confine non si muoverebbe di un millimetro. Sono i punti sul bordo a «reggere» la frontiera, e per questo si chiamano vettori di supporto. Il «supporto» è questo, e il «vettore» viene da come li scriviamo: un esempio è un elenco ordinato di numeri, uno per colonna, e un elenco del genere si chiama vettore (lo abbiamo incontrato nella sezione sull’apprendimento supervisionato). Un vettore di supporto, insomma, è semplicemente uno dei pochi esempi appoggiati al bordo del corridoio.
È una differenza sostanziale rispetto alla regressione logistica, la cui frontiera dipende (sia pur poco) da tutti i dati.
Il classificatore a massimo margine#
Adesso mettiamo in numeri la geometria del corridoio. La frontiera è quello che in matematica si chiama un iperpiano, e la parola spaventa più della cosa: in due dimensioni è una retta, in tre un piano, e in cento dimensioni è l’oggetto che fa lo stesso mestiere, cioè taglia lo spazio in due metà, solo che non lo possiamo disegnare. Sta sempre una dimensione sotto lo spazio che divide: una retta (una dimensione) in un piano (due), un piano (due) in una scatola (tre).
Un confine fra due quartieri di case si può tirare rasente al muro dell’ultima villetta, e allora basta una casa nuova un metro più in là per trovarsi dalla parte sbagliata. Tirato invece nel mezzo del prato, il più lontano possibile dalle case di tutti e due i lati, le case nuove hanno dove arrivare senza scombinare niente. Il corridoio di Fig. 4.26 è quel prato, e mettere in numeri quel «nel mezzo» è tutto il mestiere della SVM.
L’iperpiano è l’insieme dei punti \(\mathbf{x}\) che soddisfano l’equazione
ed è lo stesso conto che faceva la regressione logistica prima di schiacciare il risultato nella curva a S: moltiplica ogni caratteristica del punto per il suo peso, somma tutto, aggiungi il numero di partenza \(b\), e guarda che segno ha il risultato. Positivo di qua, negativo di là, e zero esattamente sul confine. Nella scrittura, \(\mathbf{w}\) è l’elenco dei pesi (che dà l’orientamento della frontiera), \(\mathbf{x}\) l’elenco delle caratteristiche del punto, e la scrittura \(\mathbf{w}^\top \mathbf{x}\) è solo un modo compatto di dire «moltiplica a coppie e somma»; \(b\) sposta la frontiera avanti o indietro. La novità della SVM sta nel criterio con cui sceglie \(\mathbf{w}\) e \(b\): non una frontiera qualsiasi, ma quella che lascia il vuoto più ampio attorno a sé. Più il corridoio è largo, più il classificatore è robusto.
Su «largo», però, serve un’intesa, perché dipende da come lo si misura e il righello ce lo diamo noi. Diciamo che il corridoio è la fascia dove quel conto sta fra \(-1\) e \(+1\): i due bordi sono le righe dove vale esattamente \(-1\) e \(+1\), e il confine, dove vale zero, corre nel mezzo. Ne discende una regola sola, uguale per tutti: ogni punto di cui già conosciamo la classe deve stare dalla parte sua e fuori dalla fascia.
Scelto il righello, la larghezza non si misura più sul disegno: viene fuori dai pesi, e vale \(2\) diviso la lunghezza dell’elenco \(\mathbf{w}\) (la lunghezza di un elenco di numeri si trova con Pitagora, come la diagonale di un rettangolo). Corridoio largo vuol dire allora elenco corto, e «trova il corridoio più largo» diventa «accorcia \(\mathbf{w}\) il più possibile, senza infrangere quella regola». Di risposte migliori di tutte ce n’è una e una sola, e cercandola non ci si impantana in un falso fondo.
Fissiamo la scala imponendo che gli esempi più vicini alla frontiera soddisfino \(\mathbf{w}^\top \mathbf{x} + b = \pm 1\): sono le due rette di margine. Con la convenzione \(y_i \in \{-1, +1\}\) per le due classi, chiedere che ogni punto stia dalla parte giusta e fuori dal corridoio si scrive in un colpo solo:
La distanza di un punto sul margine dall’iperpiano è \(1/\lVert \mathbf{w}\rVert\), quindi la larghezza totale del corridoio (da un bordo all’altro) è
Il conto che porta a questa formula occupa due righe, e l’approccio della strada più larga lo svolge per intero, ricavando il problema da capo. Massimizzare il margine equivale allora a minimizzare \(\lVert \mathbf{w}\rVert\), o più comodamente il suo quadrato (differenziabile ovunque). Il problema del margine rigido (hard margin) è
dove \(\mathbf{w}\) è il vettore dei pesi, \(b\) il termine di bias, \(\mathbf{x}_i\) l’\(i\)-esimo esempio e \(y_i \in \{-1,+1\}\) la sua etichetta. È un problema di programmazione quadratica convesso: ha un’unica soluzione, senza minimi locali in cui restare intrappolati.
Un esempio con i numeri#
Mettiamo in fila numeri concreti, in due dimensioni: quattro punti, due per classe, tutti su una diagonale.
Quattro case lungo una strada in diagonale: due del quartiere blu, a \((0,0)\) e \((-1,-1)\), e due del quartiere rosso, a \((2,2)\) e \((3,3)\). Le due case più vicine fra loro, una per quartiere, sono \((0,0)\) e \((2,2)\): sono loro a decidere tutto. Il corridoio più largo possibile è quello che va dall’una all’altra, e il confine passa esattamente a metà strada, per il punto \((1,1)\), messo di traverso rispetto alla diagonale.
Quanto è largo il corridoio? Qui è la distanza fra le due case, e si calcola con Pitagora: da \((0,0)\) a \((2,2)\) ci sono \(2\) passi in orizzontale e \(2\) in verticale, quindi \(\sqrt{2^2 + 2^2} = \sqrt{8} \approx 2{,}8\). Attenzione però, qui va bene perché le due case sono messe proprio l’una di fronte all’altra attraverso la strada; se fossero sfalsate, la distanza fra loro conterebbe anche un pezzo di cammino lungo la strada, che con la larghezza non c’entra. A togliere quel pezzo di troppo è il conto con i pesi, che misura in perpendicolare ai marciapiedi.
Proviamo con i pesi. Per questo confine vanno bene \(0{,}5\) e \(0{,}5\), con numero di partenza \(-1\). Sulla casa in \((0,0)\) il conto dà \(0{,}5\cdot 0 + 0{,}5\cdot 0 - 1 = -1\), e su quella in \((2,2)\) dà \(0{,}5\cdot 2 + 0{,}5\cdot 2 - 1 = +1\): stanno esattamente sui due bordi della fascia, una per parte. Le due più lontane danno \(-2\) e \(+2\), il doppio: stanno larghe, ben fuori dalla fascia. E la larghezza si ritrova anche partendo dai pesi: l’elenco \((0{,}5;\ 0{,}5)\) è lungo \(\sqrt{0{,}5^2 + 0{,}5^2} \approx 0{,}71\), e \(2\) diviso \(0{,}71\) fa \(2{,}8\), la misura di prima.
E quelle due lontane? Prova a cancellarle dal foglio: il confine non si sposta di un millimetro, perché non toccano il corridoio. Le due case sul bordo sono i vettori di supporto: reggono da sole l’intera soluzione.
Prendiamo quattro punti:
punto |
coordinate |
classe \(y_i\) |
|---|---|---|
\(\mathbf{x}_1\) |
\((0,\,0)\) |
\(-1\) |
\(\mathbf{x}_2\) |
\((2,\,2)\) |
\(+1\) |
\(\mathbf{x}_3\) |
\((-1,-1)\) |
\(-1\) |
\(\mathbf{x}_4\) |
\((3,\,3)\) |
\(+1\) |
I punti stanno tutti sulla diagonale. Per simmetria l’iperpiano di massimo margine è perpendicolare alla diagonale e passa a metà strada tra \(\mathbf{x}_1\) e \(\mathbf{x}_2\), cioè per il punto \((1,1)\): questo fissa la direzione di \(\mathbf{w}\), che è quella della diagonale \((1,1)\). La scala la fissa la convenzione \(\mathbf{w}^\top \mathbf{x} + b = \pm 1\) sui punti di margine, e i due vincoli (in \(\mathbf{x}_1\) e in \(\mathbf{x}_2\)) danno
Verifichiamo che i due punti più interni, \(\mathbf{x}_1\) e \(\mathbf{x}_2\), cadano esattamente sulle rette di margine, cioè soddisfino \(y_i(\mathbf{w}^\top \mathbf{x}_i + b) = 1\):
\(\mathbf{x}_1=(0,0)\), classe \(-1\): \(\;\mathbf{w}^\top \mathbf{x}_1 + b = 0{,}5\cdot 0 + 0{,}5\cdot 0 - 1 = -1\), e \(\;y_1(-1) = (-1)(-1) = 1\). ✓
\(\mathbf{x}_2=(2,2)\), classe \(+1\): \(\;\mathbf{w}^\top \mathbf{x}_2 + b = 0{,}5\cdot 2 + 0{,}5\cdot 2 - 1 = 1\), e \(\;y_2(1) = (+1)(1) = 1\). ✓
Sono loro i vettori di supporto. Gli altri due stanno più lontani, oltre il margine (il vincolo vale con la disuguaglianza stretta):
\(\mathbf{x}_3=(-1,-1)\): \(\;\mathbf{w}^\top \mathbf{x}_3 + b = -0{,}5 - 0{,}5 - 1 = -2\), e \(\;y_3(-2) = (-1)(-2) = 2 \ge 1\). ✓
\(\mathbf{x}_4=(3,3)\): \(\;\mathbf{w}^\top \mathbf{x}_4 + b = 1{,}5 + 1{,}5 - 1 = 2\), e \(\;y_4(2) = (+1)(2) = 2 \ge 1\). ✓
La larghezza del corridoio è
Ed è esattamente la distanza euclidea tra \(\mathbf{x}_1=(0,0)\) e \(\mathbf{x}_2=(2,2)\), che vale \(\sqrt{2^2+2^2}=\sqrt{8}=2\sqrt{2}\): i due vettori di supporto, uno per classe, si affacciano sui bordi opposti dello stesso corridoio. Nota il punto cruciale: cancellare \(\mathbf{x}_3\) e \(\mathbf{x}_4\) non cambia nulla; la soluzione dipende solo dai due punti sul bordo.
Quando i dati non sono perfetti: il margine morbido#
Il margine rigido ha due difetti gemelli: pretende che i dati siano perfettamente separabili, e basta un solo punto fuori posto (un outlier, un errore di misura) per stravolgere la soluzione o renderla impossibile. Nel mondo reale le classi si sovrappongono quasi sempre. La risposta di Cortes e Vapnik [CV95] è il margine morbido (soft margin): concedere qualche violazione, pagandola.
Quanto paga un punto dipende da un numero solo, \(y_i(\mathbf{w}^\top\mathbf{x}_i + b)\): vale \(1\) per un punto appoggiato al bordo del corridoio, cresce allontanandosi dalla parte giusta e diventa negativo dalla parte sbagliata.
Fig. 4.27 La multa di un punto dipende solo da dove sta rispetto al corridoio. Quella della SVM va a zero appena il punto è fuori, e da lì in poi quel punto non conta più; quella della regressione logistica si abbassa e basta, e vale ancora \(0{,}45\) sul bordo e \(0{,}07\) tre volte più in là.#
Torniamo al confine tra i due quartieri. Se una singola villetta isolata sconfina nel prato dell’altro, non ha senso stravolgere tutto il confine per accontentarla: meglio tracciare comunque un bel corridoio largo e mettere in conto quella manciata di eccezioni. La SVM a margine morbido fa proprio questo, e le eccezioni le mette in conto una per una, con una multa proporzionata allo sconfinamento: chi si è spinto appena dentro il corridoio paga poco, chi è finito dalla parte sbagliata paga molto, e chi è rimasto comodamente fuori non paga niente, zero, nemmeno un centesimo. È la riga di terracotta di Fig. 4.27: scende, tocca lo zero sul bordo del corridoio e da lì in poi ci resta appoggiata. Alla fine il conto da tenere basso è uno solo: quanto è stretto il corridoio, più la somma di tutte le multe.
Quanto pesano le multe rispetto alla larghezza lo decide una manopola, chiamata \(C\):
\(C\) grande = «non tollero errori»: il corridoio si stringe pur di far stare quasi tutti dalla parte giusta. Rischio di inseguire il rumore, cioè di overfitting.
\(C\) piccolo = «accetto qualche sbavatura»: il corridoio si allarga, più robusto, anche a costo di qualche punto dentro la fascia.
È lo stesso compromesso bias-varianza della sezione sull’overfitting, con la manopola girata al contrario rispetto alla regolarizzazione: qui \(C\) grande significa freno debole.
Si introduce per ogni esempio una variabile di slack \(\xi_i \ge 0\) che misura di quanto quel punto viola il proprio margine, e la si somma nella funzione obiettivo:
dove \(\xi_i\) è la violazione dell’\(i\)-esimo punto e \(C > 0\) regola il compromesso tra «corridoio largo» (\(\lVert \mathbf{w}\rVert\) piccolo) e «poche violazioni» (\(\sum\xi_i\) piccolo). Eliminando i vincoli, il problema si riscrive come minimizzazione della hinge loss più un termine di regolarizzazione:
La hinge loss \(\max(0,\,1 - y_i f(\mathbf{x}_i))\), dove \(f(\mathbf{x}) = \mathbf{w}^\top\mathbf{x} + b\), è nulla per i punti ben classificati e fuori dal margine, e cresce linearmente per quelli dentro la fascia o dalla parte sbagliata: è l’analogo, per la SVM, di ciò che la log-loss è per la regressione logistica, con la differenza che, essendo piatta oltre il margine, ignora del tutto i punti «facili» e dà alla SVM la sua sparsità in vettori di supporto. In questa forma si legge chiaramente il ruolo di \(C\): il coefficiente della penalità \(\lVert \mathbf{w}\rVert^2\) è \(1/(2C)\), quindi \(C\) è l’inverso della forza di regolarizzazione. \(C\) grande → penalità debole → margine stretto, varianza alta; \(C\) piccolo → penalità forte → margine largo, bias più alto. È la stessa manopola \(\lambda\) della sezione sull’overfitting, letta al contrario; con un’avvertenza di normalizzazione: la loss Ridge era mediata sugli \(m\) esempi, la hinge qui è sommata, e a parità di convenzione l’identificazione esatta è \(\lambda = 1/(2Cm)\), cioè a meno di un fattore pari alla taglia del dataset.
E la lettera \(C\) non ha lo stesso verso in tutti i testi, il che rende ingannevole confrontare due grafici a occhio. Qui, in scikit-learn e in The Elements of Statistical Learning [HTF09] è il peso della penalità sulle violazioni, quindi \(C\) grande stringe il corridoio. In An Introduction to Statistical Learning [JWH+23] la stessa lettera è invece il budget concesso alle violazioni, e allora \(C\) grande allarga il corridoio e moltiplica i vettori di supporto. Prima di leggere una curva di \(C\) conviene guardare quale delle due convenzioni segue.
L’approccio della strada più larga#
Fin qui abbiamo chiesto fiducia su due cose e non ne abbiamo dimostrata nessuna: che si sappia calcolare quanto è larga la strada (ci serve, visto che vogliamo la più larga di tutte), e che a reggere la frontiera siano soltanto pochi punti, i vettori di supporto.
Adesso le dimostriamo tutte e due, e lungo il percorso salterà fuori una terza cosa che nessuno aveva cercato: il problema si può riscrivere in una forma in cui gli esempi non compaiono più uno per uno, ma soltanto a coppie, e di ogni coppia serve un numero solo. Sembra un dettaglio contabile ed è il perno di tutto il resto della sezione, kernel trick compreso.
La strada per arrivarci è corta, sta in una pagina di algebra, e lungo il percorso succede due volte una cosa che all’inizio non era prevedibile.
Il percorso che segue è quello che Patrick Winston chiamava the widest street approach, l’approccio della strada più larga, nella sedicesima lezione del corso 6.034 del MIT [Win10]. Prendiamo in prestito anche il suo vocabolario, che è più concreto del nostro: il corridoio diventa una strada, le due rette di margine diventano i marciapiedi, e quello che cerchiamo è la strada più larga che si riesca a far passare fra i più e i meno.
Winston apriva quella lezione con un avvertimento che vale per ogni derivazione elegante. Quando una derivazione così la si legge in un libro, finita e ordinata, viene da pensare che Vapnik l’abbia tirata fuori tutta insieme un sabato pomeriggio in cui il tempo era troppo brutto per uscire. Non è così che succede. Succede in un altro modo, e alla fine della sezione vedremo quale.
Primo passo: da che parte della strada sei#
Piantiamo una freccia perpendicolare alla strada e chiamiamola \(\mathbf{w}\). Di lei sappiamo una cosa sola: la direzione, di traverso alla strada. Quanto sia lunga non lo sappiamo ancora, e la cosa tornerà utile.
Arriva un punto nuovo, di cui non conosciamo la classe. Come decidiamo da che parte sta? Gli facciamo fare l’ombra sulla freccia. La freccia è appoggiata per terra, con la coda nell’origine, e una luce arriva perpendicolare a lei: l’ombra del punto cade sulla freccia, in un certo punto, e quel punto lo possiamo misurare come una distanza dalla coda. Ne esce un numero solo. Nel conto la freccia entra tutta quanta, e non solo la sua direzione, quindi quel numero cresce sia quando l’ombra cade più in là, sia quando la freccia è più lunga. Se supera una certa soglia, il punto ha attraversato la strada ed è un più; se resta al di qua, è un meno.
Guardiamo che cosa abbiamo appena buttato via. Della posizione del punto lungo la strada non ci importa niente, perché camminando lungo la strada non si cambia mai lato: l’ombra la ignora, ed è esattamente ciò che vogliamo. Conta solo di quanto la strada la si attraversa. Quell’operazione (fare l’ombra di un punto su una freccia e leggerne un numero solo) si chiama prodotto scalare, ed è il mattone di tutto ciò che segue. È la stessa cosa del «moltiplica a coppie e somma» di poco fa: si moltiplica ogni coordinata del punto per la coordinata corrispondente della freccia e si sommano i risultati. Due descrizioni molto diverse, un unico conto, ed è proprio questa doppia natura, geometrica e aritmetica insieme, che alla fine della sezione farà il miracolo.
Freccia e soglia, però, non sono ancora numeri: restano libere tutte e due, e alla stessa strada corrispondono infinite coppie, tutte ugualmente buone. I due passi che seguono servono a sceglierne una.
Sia \(\mathbf{w}\) un vettore perpendicolare all’asse della strada, di lunghezza per ora indeterminata, e sia \(\mathbf{u}\) un punto di classe ignota. La proiezione di \(\mathbf{u}\) sulla direzione di \(\mathbf{w}\) vale \(\mathbf{w}^\top\mathbf{u} / \lVert\mathbf{w}\rVert\); siccome \(\lVert\mathbf{w}\rVert\) è un numero positivo, confrontare quella proiezione con una soglia equivale a confrontare il prodotto scalare \(\mathbf{w}^\top\mathbf{u}\) con una soglia \(c\):
dove si è posto \(b = -c\). Questa è la regola di decisione, ed è il primo dei cinque pezzi che dobbiamo mettere in fila.
Il guaio è che così com’è non serve a niente: non conosciamo \(b\), e di \(\mathbf{w}\) conosciamo la direzione ma non la lunghezza. Un vettore perpendicolare alla strada può essere lungo un metro o un chilometro, e a ogni lunghezza corrisponde una soglia \(b\) diversa che dà però la stessa frontiera. Ci sono infinite coppie \((\mathbf{w}, b)\) che descrivono la stessa retta: mancano vincoli, e i prossimi due passi servono a metterne abbastanza da fissarne una sola.
Secondo passo: due vincoli che diventano uno#
La regola del primo passo dice solo «da che parte», e non basta. Di una casa che conosciamo già non vogliamo sapere soltanto che sta dal lato giusto: vogliamo che stia anche lontana dalla strada, non appiccicata al bordo. Alziamo quindi l’asticella. A una casa dei più chiediamo che l’ombra superi la soglia di almeno una tacca; a una dei meno, che le resti sotto di almeno una tacca.
Quanto vale una tacca? Lo decidiamo noi, e possiamo dire che vale \(1\). Non è un atto di fede: ricordi che la lunghezza della freccia \(\mathbf{w}\) era rimasta libera? Allungandola o accorciandola tutte le ombre si riscalano insieme, quindi fissare la tacca a \(1\) è una scelta di righello, e non dice niente sui dati. Da qui in avanti, scelta la strada, la freccia e la soglia vengono decise insieme a lei: la libertà che avanzava è spesa, e la lunghezza della freccia non la scegliamo più noi.
Restano due regole, una per i più e una per i meno, e portarsene dietro due è scomodo. Il trucco è dare a ogni casa un’etichetta numerica che vale \(+1\) se è un più e \(-1\) se è un meno, e moltiplicare la regola per quell’etichetta. Sui più non cambia nulla; sui meno si moltiplicano per un numero negativo entrambi i lati, il verso della disuguaglianza si rovescia, e le due regole diventano la stessa identica riga. Nessuna necessità matematica lo imponeva: è comodità dichiarata, e metà della matematica applicata è fatta di comodità dichiarate.
Ancora una riga, che al passo dopo diventa decisiva: le case appoggiate al marciapiede hanno esattamente una tacca, né più né meno, ed è questo a distinguerle da tutte le altre, che ne hanno di più.
Con le etichette \(y_i \in \{-1,+1\}\) già introdotte, i due vincoli separati
si fondono, moltiplicando ciascuno per il proprio \(y_i\), nell’unica scrittura
A questo aggiungiamo la condizione che completa il secondo pezzo: per gli esempi che stanno sul marciapiede la disuguaglianza vale con l’uguale,
Il valore \(1\) è la normalizzazione che spende il grado di libertà residuo sulla scala di \((\mathbf{w}, b)\). Con quella fissata, a ogni strada corrisponde una sola coppia \((\mathbf{w}, b)\), e la lunghezza di \(\mathbf{w}\) non è più libera: il terzo passo mostra che è proprio lei a misurare la strada.
Terzo passo: quanto è larga la strada#
Adesso la domanda vera. Sappiamo scrivere i vincoli, ma non sappiamo ancora misurare la quantità che vogliamo rendere massima.
Prendiamo una casa che tocca il marciapiede di sinistra e una che tocca quello di destra, e congiungiamole con una freccia. Quella freccia non è la larghezza della strada, perché va di sghembo: parte in un punto della strada e arriva in un altro, e quindi contiene sia l’attraversamento sia un pezzo di cammino lungo la strada, che a noi non interessa.
Ma sappiamo già come buttare via il pezzo che non interessa: l’ombra. Facciamo fare a quella freccia l’ombra sulla direzione perpendicolare alla strada, e quello che resta è esattamente la larghezza, come mostra Fig. 4.28. Una accortezza sola: la freccia \(\mathbf{w}\) ci serve qui come direzione e non come lunghezza, quindi se ne fa una copia lunga esattamente \(1\), dividendone tutte le coordinate per la lunghezza dell’originale. Una freccia di lunghezza \(1\) indica una direzione e basta; l’originale però resta dov’è, e fra due righe torna utile proprio con la sua lunghezza.
Il conto sta in due righe di algebra, e il risultato è sorprendente. Viene fuori che la larghezza della strada vale sempre \(2\) diviso la lunghezza della freccia \(\mathbf{w}\) di partenza, quella che non abbiamo accorciato. Sempre: delle due case, che erano il punto di partenza, non resta traccia. La ragione è che quelle due toccano il marciapiede: hanno esattamente una tacca ciascuna, né più né meno, e nel conto i loro nomi si cancellano da soli. Anche il \(2\) viene da lì, dall’asticella fissata a \(+1\) da una parte e \(-1\) dall’altra: fra i due c’è appunto una distanza di \(2\), ed è quella che riemerge qui.
E allora il problema, che era «trova la strada più larga», è diventato: rendi \(\mathbf{w}\) più corta che puoi, senza infrangere le regole del secondo passo. Sono quelle regole a impedire la risposta stupida (una freccia lunga zero, cioè nessuna frontiera).
Un’ultima comodità, e riguarda solo i conti: invece della lunghezza si accorcia il suo quadrato. La freccia più corta resta la stessa (fra due lunghezze, che sono numeri positivi, la più piccola ha anche il quadrato più piccolo), e i passaggi che verranno vengono più lisci.
Siano \(\mathbf{x}_+\) un esempio positivo sul proprio marciapiede e \(\mathbf{x}_-\) un esempio negativo sul suo. La larghezza della strada è la proiezione della loro differenza sul versore normale \(\mathbf{w}/\lVert \mathbf{w}\rVert\):
Sembra dipendere dai due punti scelti, e invece no, perché quei due punti stanno sul margine e lì vale l’uguaglianza del secondo passo. Per \(\mathbf{x}_+\) (con \(y=+1\)) si ha \(\mathbf{w}^\top\mathbf{x}_+ = 1 - b\); per \(\mathbf{x}_-\) (con \(y=-1\)) il vincolo \(-(\mathbf{w}^\top\mathbf{x}_- + b) = 1\) dà \(\mathbf{w}^\top\mathbf{x}_- = -1 - b\). Sostituendo, il termine \(b\) si elide:
È la formula che avevamo enunciato senza prova. Massimizzare \(2/\lVert\mathbf{w}\rVert\) equivale a massimizzare \(1/\lVert\mathbf{w}\rVert\), e quindi a minimizzare \(\lVert\mathbf{w}\rVert\), e infine, per pura comodità,
Il quadrato toglie di mezzo la radice quadrata nascosta nella norma e rende la funzione differenziabile ovunque, compresa l’origine; il fattore \(1/2\) serve solo a far sparire il \(2\) quando deriveremo. Nessuna delle due mosse cambia il punto di minimo, perché elevare al quadrato è monotono sui numeri non negativi. Terzo pezzo sistemato.
Fig. 4.28 La larghezza della strada, ricavata in due righe. La freccia che unisce i due esempi appoggiati ai marciapiedi va di sghembo, e si scompone in due pezzi: quello che attraversa la strada, che vale esattamente \(2/\lVert\mathbf{w}\rVert\) (cioè \(2\) diviso la lunghezza di \(\mathbf{w}\)), e quello che corre lungo la strada, in grigio, che l’ombra butta via.#
Il primo caffè
È il punto della lezione in cui Winston si ferma. Facciamo una pausa? Andiamo a prendere un caffè? Peccato che qui non si possa, dice alla classe, ma se si potesse lo faremmo. E aggiunge la frase per cui vale la pena raccontare tutto questo: «sono sicuro che quando Vapnik è arrivato a questo punto, è uscito a prendere un caffè».
Sembra una battuta buttata lì per far respirare l’aula, e in parte lo è. Ma è anche l’unico modo onesto di segnalare una cosa che le derivazioni scritte nascondono sistematicamente: qui finisce un pezzo e ne comincia un altro, e fra i due c’è un salto che nessuna riga di algebra spiega. Abbiamo una funzione da minimizzare e dei vincoli da rispettare, e la mossa successiva non discende da quella precedente. Bisogna averla vista da un’altra parte, o inventarla.
Teniamo il conto: caffè numero uno.
Quarto passo: Lagrange, e la prima sorpresa#
Da tre secoli il punto più basso di un prato lo si trova camminando finché il terreno smette di scendere: il fondo di una conca è piatto. Il nostro prato però ha una staccionata, fatta delle regole di poco fa, un paletto per ogni casa, e il fondo vero cade dall’altra parte. Il punto più basso che ci è concesso sta appoggiato ai paletti, e lì il terreno scende ancora.
Il modo di togliere la staccionata ha più di due secoli e porta il nome di Joseph-Louis Lagrange, nato a Torino nel 1736 come Giuseppe Lodovico Lagrangia. Al posto di ogni paletto si mette un casellante, con il suo cartellino: \(\alpha_i\) (si legge «alfa i-esimo», e la \(i\) dice soltanto di quale casa parliamo). Sul cartellino c’è un prezzo, mai uno sconto. Chi cammina paga la quota del terreno più i pedaggi dei caselli che ha oltrepassato, e quel conto si chiama lagrangiana: dentro non c’è più nemmeno un paletto.
Il recinto sparisce, il divieto resta. Il casellante decide da sé il prezzo e lo tira su più che può: a chi è passato dalla parte proibita lo alza senza limite, fino a mangiarsi qualunque guadagno di quota. Uscire smette di convenire, e allora il fondo si può cercare camminando dove pare, sicuri che cadrà là dove i paletti ci avrebbero lasciato stare.
I caselli davanti alle case lontane dalla strada non li oltrepassa nessuno, e chi non fa passare nessuno non ha niente da farsi pagare: il loro cartellino segna zero. A pagare sono soltanto le case appoggiate al marciapiede, e sono quelle poche a reggere la frontiera, i vettori di supporto.
Adesso camminiamo finché il terreno è piatto, e arriva la prima cosa non prevedibile. La freccia \(\mathbf{w}\), cioè la frontiera stessa, viene fuori dalle case: ognuna tira con la forza scritta sul proprio cartellino, i più da una parte e i meno dall’altra, e la freccia è la somma di quelle tirate. Sommare due case vuol dire mettere in fila i loro elenchi di numeri e sommarli coordinata per coordinata, come si fa con due frecce. Da un conto del genere poteva uscire di tutto, e di solito esce qualcosa di intrattabile. Invece è uscita una somma di case: la frontiera è fatta dei dati, e siccome quasi tutti i cartellini segnano zero, di case ne entrano pochissime.
Dallo stesso terreno piatto esce una seconda condizione, molto più modesta: i due quartieri pagano lo stesso totale. Cinque case, tre col cartellino a zero; se quella dei più paga \(4\), anche quella dei meno paga \(4\), e la differenza fa zero. Sembra contabilità e basta, e appena rimetteremo la freccia dentro il conto cancellerà da sola un pezzo intero.
Si costruisce la lagrangiana, associando a ogni vincolo un moltiplicatore \(\alpha_i \ge 0\):
dove il primo termine è la quantità da minimizzare, la parentesi quadra è esattamente il vincolo del secondo passo, quello che vale zero sui punti di margine, e \(\alpha_i\) è il moltiplicatore associato al vincolo \(i\)-esimo. Un avvertimento sul simbolo, perché qui il libro fa un’eccezione: in queste pagine \(\mathcal{L}\) è la lagrangiana, non la funzione di costo che la stessa lettera indica ovunque altrove. È la notazione consolidata di questa derivazione, e vale fino alla fine della sezione. Il segno meno, con \(\alpha_i \ge 0\), non è arbitrario: se un vincolo è violato la parentesi diventa negativa, il termine \(-\alpha_i[\,\cdot\,]\) diventa positivo e si può far crescere quanto si vuole alzando \(\alpha_i\), quindi la violazione si paga; se invece il vincolo è rispettato con margine, il valore di \(\alpha_i\) che conviene è zero. La sparsità è già lì, in nuce.
Ora si annullano le derivate. Rispetto a \(\mathbf{w}\), che è un vettore, si deriva componente per componente e il risultato ha la stessa forma del caso scalare (è la convenzione di layout dichiarata nel capitolo di matematica):
Rispetto a \(b\), l’unico termine che lo contiene è quello dentro la sommatoria:
La prima delle due è la sorpresa, e conviene dirla per esteso: il vettore dei pesi \(\mathbf{w}\) è una combinazione lineare degli esempi di addestramento, con coefficienti \(\alpha_i y_i\). Guardando il problema di partenza non c’era nulla che lo annunciasse, e invece la soluzione vive nello spazio generato dagli esempi: la frontiera si scrive con i dati e con nient’altro. La seconda equazione, \(\sum_i \alpha_i y_i = 0\), sembra per ora solo una condizione di bilanciamento fra le due classi; fra un attimo cancellerà da sola un termine intero.
E qui, alla lavagna, Winston si concede il secondo caffè. Poi aggiunge la frase che dà senso anche al primo: «a proposito, queste pause caffè durano mesi». Si sta lì a guardare il risultato, si lavora ad altro, ci si preoccupa degli esami, ogni tanto ci si ripensa. Prima o poi si torna dal caffè e si fa il passo successivo. Caffè numero due: quanto siano durate davvero, quelle due pause, lo dice l’ultima parte della sezione.
Quinto passo: il duale, e la seconda sorpresa#
Abbiamo scoperto come è fatta la freccia \(\mathbf{w}\). La mossa che resta è ovvia e faticosa: rimettere quella scoperta dentro la funzione «quota più pedaggi» del passo precedente, e vedere che aspetto prende il problema quando \(\mathbf{w}\) non compare più.
È solo algebra: sostituzioni e raccoglimenti, niente idee nuove. Quello che conta è il risultato, che è la seconda cosa non prevedibile del percorso.
Dopo la sostituzione, dei dati non restano né le coordinate né le distanze dalla frontiera. Se ne va anche la soglia, portata via dal pareggio dei prezzi trovato un attimo fa. Resta una cosa sola: per ogni coppia di case, l’ombra dell’una sulla freccia dell’altra. Il problema da risolvere e la regola per classificare un punto nuovo si scrivono entrambi usando soltanto quelle ombre a due a due.
Detto altrimenti: della mappa del quartiere si può buttare via tutto, tenendo solo una tabella che per ogni coppia di case dice quanto si «vedono». Con quella tabella si costruisce la frontiera, e senza la mappa. È un fatto che al momento sembra soltanto elegante, ed è invece la porta del kernel trick: se i dati entrano nel conto soltanto attraverso quelle ombre, nessuno ci vieta di cambiare il modo di calcolarle.
Due note prima di proseguire. Anche riscritto così, il problema ha una sola risposta migliore di tutte, e chi la cerca non rischia di fermarsi in un falso fondo. E se le case non si lasciano separare in modo pulito, cambia una riga sola: la manopola \(C\) del margine morbido diventa un tetto, e nessuna casa può spingere più forte di così.
Sostituiamo \(\mathbf{w} = \sum_i \alpha_i y_i \mathbf{x}_i\) nei tre pezzi della lagrangiana. Il termine quadratico diventa
il termine \(\sum_i \alpha_i y_i \mathbf{w}^\top\mathbf{x}_i\) è la stessa doppia somma senza il fattore \(1/2\), e il termine \(\sum_i \alpha_i y_i b = b\sum_i \alpha_i y_i\) si annulla per la seconda condizione del quarto passo. Rimane il \(+\sum_i\alpha_i\) che veniva dal \(-1\) dentro la parentesi quadra. Sommando i primi due (uno con \(1/2\), l’altro intero, di segno opposto) resta metà del secondo, cambiata di segno:
È il problema duale: non contiene più né \(\mathbf{w}\) né \(b\), solo gli \(m\) moltiplicatori. Resta una programmazione quadratica, ma con un dettaglio che vale tutta la fatica. Riscriviamo anche la regola di decisione del primo passo sostituendoci \(\mathbf{w}\):
Ecco il dettaglio: in entrambe le formule gli esempi compaiono soltanto dentro un prodotto scalare, \(\mathbf{x}_i^\top\mathbf{x}_j\) nel problema da ottimizzare e \(\mathbf{x}_i^\top\mathbf{u}\) nella regola di decisione. Non servono le coordinate, non serve la dimensione dello spazio, non serve nemmeno sapere che cosa siano gli \(\mathbf{x}_i\): serve una tabella di prodotti scalari. Da questa osservazione, e da nient’altro, nasce il kernel trick.
Due note a margine. La prima: la funzione obiettivo del duale è concava e il dominio è convesso, quindi ogni massimo locale è anche globale e non ci sono ottimi locali in cui restare intrappolati, al contrario di quanto succede addestrando una rete neurale. La seconda: passando al margine morbido cambia una riga sola, il vincolo \(\alpha_i \ge 0\) diventa \(0 \le \alpha_i \le C\), cioè il parametro \(C\) mette un tetto a quanto può spingere un singolo punto. Tutto il resto, kernel compreso, resta identico.
Perché i vettori di supporto sono pochi#
Che i punti che contano siano pochi lo abbiamo detto fin dalla prima pagina, e finora era una promessa. Adesso si dimostra in due righe, e discende dal percorso appena fatto: è una conseguenza, non un’osservazione fatta provando.
Torniamo alla frase più sorprendente di tutto il percorso: le case lontane dal confine non contano nulla, e potresti cancellarle senza spostarlo di un millimetro. Adesso sappiamo perché.
Il confine è un muro elastico teso fra le due parti, e ogni casa una mano che spinge il muro per allontanarlo da sé. Le case addossate al corridoio spingono davvero: se ne togli una, il muro scivola. Le case arretrate non toccano il muro, e la loro spinta è esattamente zero. Sono i prezzi \(\alpha_i\) del quarto passo: chi non tocca il proprio paletto non paga pedaggio, e il suo prezzo è zero. Ma \(\mathbf{w}\), l’abbiamo appena scoperto, è la somma delle case pesata con quei prezzi, e zero moltiplicato per qualunque cosa resta zero: nella soluzione, il contributo delle case arretrate non c’è proprio.
Spingono anche le case che il margine morbido ha lasciato dentro il corridoio o dalla parte sbagliata: quelle il muro lo toccano eccome. Nessuna, però, può spingere più forte di quanto la manopola \(C\) le consenta.
Sulle quattro case in diagonale la spinta si conta. Le due sul bordo spingono un quarto ciascuna, le due arretrate zero; la casa in \((0,0)\) sta nell’origine e non sposta niente, e un quarto della casa in \((2,2)\) fa \((0{,}5;\ 0{,}5)\), cioè esattamente la freccia del confine trovato prima a occhio.
È il motivo per cui la SVM, alla fine, si porta appresso solo i pochi punti che spingono e può dimenticare tutti gli altri, anche se erano un milione.
Le condizioni di Karush–Kuhn–Tucker, che completano il metodo di Lagrange nel caso di vincoli di disuguaglianza, impongono la complementarità: per ogni \(i\), il prodotto fra il moltiplicatore e il proprio vincolo è nullo,
(qui già nella forma a margine morbido, con la variabile di slack \(\xi_i\); per il margine rigido basta porre \(\xi_i = 0\)). Se un punto è strettamente fuori dal margine, la parentesi quadra è diversa da zero, e allora deve essere \(\alpha_i = 0\): quel punto sparisce dalla somma \(\mathbf{w} = \sum_i \alpha_i y_i \mathbf{x}_i\) che ricostruisce la soluzione. Restano solo i punti sul margine o dentro la fascia, cioè i vettori di supporto.
Sui quattro punti dell’esempio numerico i conti si chiudono in una riga. La condizione \(\sum_i \alpha_i y_i = 0\) e la ricostruzione di \(\mathbf{w}\) danno \(\alpha_1 = \alpha_2 = 0{,}25\) e \(\alpha_3 = \alpha_4 = 0\), da cui
esattamente la soluzione trovata per via geometrica. Come controprova vale l’identità \(\sum_i \alpha_i = \lVert\mathbf{w}\rVert^2\), che discende dall’uguaglianza fra primale e duale all’ottimo: qui \(0{,}25 + 0{,}25 = 0{,}5\) e \(\lVert\mathbf{w}\rVert^2 = 0{,}25 + 0{,}25 = 0{,}5\), e il margine \(2/\lVert\mathbf{w}\rVert = 2/\sqrt{0{,}5} \approx 2{,}83\) coincide con la larghezza già misurata sugli stessi quattro punti.
Quanto dura davvero una pausa caffè#
Il passo successivo, nella storia vera, arrivò trent’anni dopo.
Vapnik aveva scritto l’idea della strada più larga nella sua tesi a Mosca, all’inizio degli anni Sessanta, e per un pezzo non se ne fece niente. Non perché l’idea fosse debole, racconta Winston: perché non c’erano macchine su cui provarla. Negli anni successivi, sempre con Chervonenkis, costruì la teoria che stabilisce quando un modello che ha imparato bene sugli esempi visti continuerà a funzionare su quelli nuovi [VC71]: è ciò che oggi si chiama teoria dell’apprendimento statistico, e la sua misura di complessità, la dimensione VC, porta le iniziali dei due. In Occidente, per vent’anni, quel lavoro non lo lesse quasi nessuno.
Nel 1990 Vapnik emigra negli Stati Uniti e finisce ai laboratori Bell di Holmdel, nel New Jersey, dove si lavorava al riconoscimento delle cifre scritte a mano. È lì che, nel 1992, nasce il kernel [BGV92]: si prende la tabella delle ombre a due a due appena trovata e si cambia il modo di riempirla. Winston fa notare per inciso il vantaggio di studiare cose fatte da gente ancora viva: a Fourier non si può telefonare per chiedergli come gli sia venuta, a Vapnik sì. E il seguito lo racconta così. Gli articoli mandati alla conferenza NIPS quell’anno furono respinti tutti. Vapnik aveva un’opinione bassissima delle reti neurali, e scommise una cena con un collega che le SVM le avrebbero battute sulla scrittura a mano. Fu il collega a mettersi alla prova: usò un kernel appena appena curvo (un polinomio di grado due, cioè la più timida delle frontiere non dritte) e funzionò al primo colpo. A Napoleone si attribuisce l’osservazione che un soldato si batte a lungo e con ferocia per un pezzetto di nastro colorato; ecco, commenta Winston, questo è il pezzetto di nastro, ed era una cena.
Il kernel Vapnik ce l’aveva già nella tesi. Non aveva mai pensato che fosse importante, e furono i risultati sulle cifre a fargli cambiare idea. Fra il momento in cui aveva capito i kernel e il momento in cui ne capì l’importanza passarono trent’anni.
È qui che la battuta del caffè smette di essere una battuta. La derivazione che abbiamo appena percorso sta in una pagina e si legge in un quarto d’ora; le due pause in mezzo, per chi la faceva per la prima volta, sono durate una carriera. Le grandi idee, chiude Winston, sono seguite da lunghi periodi in cui non succede niente, e poi da un momento in cui l’idea di partenza si rivela potentissima con appena mezzo giro di vite. E da lì in avanti il mondo non si volta più indietro.
Da ricordare
La SVM sceglie, tra le infinite linee che separano due classi, la più prudente: quella che lascia il corridoio più largo possibile fra i due quartieri. A reggere il confine sono solo i pochi punti che ne toccano i bordi, i vettori di supporto: gli altri si possono cancellare dal foglio e il confine non si sposta di un millimetro.
Il margine morbido mette in conto qualche sconfinamento, e una manopola decide quanto è severa: severa, il corridoio si stringe pur di accontentare quasi tutti (e si rischia di inseguire il rumore); indulgente, il corridoio si allarga ed è più robusto. I punti già comodamente fuori dal corridoio non pesano affatto: a reggere il confine restano sempre e solo le poche case sul bordo.
La strada più larga si ricava in cinque passi, e due volte lungo il percorso salta fuori qualcosa che nessuno aveva chiesto: che la frontiera è fatta dei dati stessi, sommati con un peso, e che i dati entrano nel conto solo a coppie, ognuno attraverso l’ombra che fa sull’altro. È la seconda cosa ad aprire la porta al kernel trick.
Da ricordare
La SVM sceglie, tra le infinite frontiere che separano due classi, quella a margine massimo: il corridoio \(2/\lVert \mathbf{w}\rVert\) più largo. L’idea è di Vapnik, con Lerner nel 1963 e con Chervonenkis nel 1964; dai laboratori Bell arrivano trent’anni dopo il kernel trick e il margine morbido.
La derivazione («l’approccio della strada più larga») va dalla regola di decisione \(\mathbf{w}^\top\mathbf{u}+b\ge 0\) ai vincoli \(y_i(\mathbf{w}^\top\mathbf{x}_i+b)-1\ge 0\), da lì a \(\text{larghezza}=2/\lVert\mathbf{w}\rVert\) per proiezione di \(\mathbf{x}_+-\mathbf{x}_-\) sulla normale, e infine, via Lagrange, a \(\mathbf{w}=\sum_i\alpha_iy_i\mathbf{x}_i\) e \(\sum_i\alpha_iy_i=0\). Sostituendo si ottiene il duale \(\sum_i\alpha_i-\frac12\sum_{i,j}\alpha_i\alpha_jy_iy_j\,\mathbf{x}_i^\top\mathbf{x}_j\), concavo, in cui gli esempi compaiono solo dentro prodotti scalari: da qui, e da nient’altro, il kernel trick.
La soluzione dipende solo dai vettori di supporto, e non è un’osservazione ma un corollario: la complementarità KKT \(\alpha_i[y_i(\mathbf{w}^\top\mathbf{x}_i+b)-1+\xi_i]=0\) annulla \(\alpha_i\) per ogni punto fuori dal margine, e \(\mathbf{w}=\sum_i\alpha_iy_i\mathbf{x}_i\) non lo contiene.
Il margine morbido ammette violazioni \(\xi_i\) pagate dal parametro \(C\), l’inverso della forza di regolarizzazione: \(C\) grande → margine stretto (overfitting), \(C\) piccolo → margine largo. La perdita è la hinge loss, parente della log-loss ma piatta oltre il margine.
Quel mezzo giro di vite ha un nome, il kernel trick: prende la frontiera dritta costruita fin qui e la piega, cambiando del conto una riga sola. È la storia in cui il duale, percorso passo per passo, ripaga il biglietto.