Capitolo 15 Support Vector Machines (SVM)
15.1 Introduzione
Support Vector Machine (SVM: Macchina a Vettori di Supporto) è un approccio per la classificazione sviluppato all’interno della comunità della computer science; il metodo di recente è cresciuto in popolarità perché ha dimostrato buone performance in molto contesti differenti. Ne presenteremo ora brevemente le principali idee senza entrare troppo nei complicati dettagli tecnici (per una presentazione completa si veda per esempio Hastie, T., Tibshirani, R., and Friedman, J., The Elements of Statistical Learning, 2nd edition, Springer, 2009).
L’idea principale della SVM è quella di “allargare” lo spazio delle feature usando funzioni quadratiche, cubiche o di dimensionalità più elevata dei predittori e dei termini di interazione, o anche funzioni più complicate, per descrivere soglie di separazione non lineari tra le classi. I mattoni fondamentali del SVM sono i “prodotti interni” delle osservazioni (piuttosto che le osservazioni stesse), che entrano nel classificatore dopo che sono stati trasformati tramite un kernel (o nucleo): grossolanamente una funzione delle osservazioni delle variabili indipendenti. Ci sono molte possibili scelte di kernel, con le più popolari che sono i cosiddetti kernel polinomiali o radiali.
15.2 Un esempio con dati simulati
Esistono molti package in R che implementano il SVM. Ci concentreremo qui sulla
funzione svm() del package e1071. Altre opzioni sono il package kernlab ed il
package LiblineaR, utile per problemi lineari molto grandi. Applicheremo ora
l’SVM ad alcuni dati simulati per mostrare la capacità di SVM di generare soglie
non lineari:
set.seed(123)
sim.data <- function(n = 200) {
if (n < 100) {
stop("La dimensione campionaria deve essere almeno pari a 100.")
}
n <- ifelse(n %% 4 == 0, n, n - (n %% 4))
x <- matrix(rnorm(n*2), ncol = 2)
x[1:(n/2), ] <- x[1:(n/2), ] + 2
x[(n/2 + 1):(3*n/4), ] <- x[(n/2 + 1):(3*n/4), ] - 2
y <- c(rep(1, 3*n/4), rep(2, n/4))
return(data.frame(x1 = x[, 1], x2 = x[, 2], y = as.factor(y)))
}
n <- 200
dat <- sim.data(n)
plot(x2 ~ x1, col = y, data = dat)
Divideremo quindi i dati in maniera casuale in un gruppo di training ed un gruppo di test ed adatteremo
i dai di training usando la funzione svm(), usando un kernel radiale con parametro
gamma pari a 1:
library(e1071)
train <- sample(n, 100)
svm.fit <- svm(y ~ ., data = dat[train, ], kernel = "radial", gamma = 1,
cost = 1)
plot(svm.fit, dat[train, ],svSymbol = "x", dataSymbol = "o")
Il grafico mostra che in questo SVM ci sono alcuni errori di training. Aumentando
il valore di cost, possiamo ridurre il numero di errori nel training
al costo di soglie più irregolari:
svm.fit <- svm(y ~., data = dat[train, ], kernel = "radial", gamma = 1,
cost = 1e5)
plot(svm.fit, dat[train, ],svSymbol = "x", dataSymbol = "o")
E’ comunque possibile eseguire una cross-validation usando la funzione tune() per
selezionare la scelta migliore di gamma e cost per un SVM con kernel radiale:
set.seed(123)
tune.out <- tune(svm, y~ ., data = dat[train, ], kernel = "radial",
ranges = list(cost = c(0.1, 1, 10, 100, 1000),
gamma = c(0.5, 1, 2, 3, 4)))
summary(tune.out)##
## Parameter tuning of 'svm':
##
## - sampling method: 10-fold cross validation
##
## - best parameters:
## cost gamma
## 1 0.5
##
## - best performance: 0.09
##
## - Detailed performance results:
## cost gamma error dispersion
## 1 1e-01 0.5 0.28 0.15491933
## 2 1e+00 0.5 0.09 0.08755950
## 3 1e+01 0.5 0.09 0.07378648
## 4 1e+02 0.5 0.11 0.11005049
## 5 1e+03 0.5 0.13 0.11595018
## 6 1e-01 1.0 0.18 0.13984118
## 7 1e+00 1.0 0.11 0.09944289
## 8 1e+01 1.0 0.11 0.08755950
## 9 1e+02 1.0 0.11 0.09944289
## 10 1e+03 1.0 0.14 0.12649111
## 11 1e-01 2.0 0.20 0.13333333
## 12 1e+00 2.0 0.11 0.09944289
## 13 1e+01 2.0 0.11 0.11005049
## 14 1e+02 2.0 0.14 0.11737878
## 15 1e+03 2.0 0.15 0.09718253
## 16 1e-01 3.0 0.26 0.16465452
## 17 1e+00 3.0 0.11 0.08755950
## 18 1e+01 3.0 0.12 0.10327956
## 19 1e+02 3.0 0.14 0.11737878
## 20 1e+03 3.0 0.15 0.11785113
## 21 1e-01 4.0 0.28 0.15491933
## 22 1e+00 4.0 0.12 0.10327956
## 23 1e+01 4.0 0.13 0.10593499
## 24 1e+02 4.0 0.11 0.12866839
## 25 1e+03 4.0 0.14 0.10749677La migliore scelta dei parametri richiede cost = 10 e gamma = 3.
svm.fit <- svm(y ~., data = dat[train, ], kernel = "radial", gamma = 3,
cost = 10)
plot(svm.fit, dat[train, ],svSymbol = "x", dataSymbol = "o")
A questo punto possiamo ottenere le previsioni sui dati di test
per questo modello tramite la funzione predict():
## Loading required package: lattice## Loading required package: ggplot2svm.pred <- predict(tune.out$best.model, newx = dat[-train, ])
confusionMatrix(data = svm.pred, reference = dat[-train, "y"], positive = "1")## Confusion Matrix and Statistics
##
## Reference
## Prediction 1 2
## 1 54 18
## 2 24 4
##
## Accuracy : 0.58
## 95% CI : (0.4771, 0.678)
## No Information Rate : 0.78
## P-Value [Acc > NIR] : 1.0000
##
## Kappa : -0.1146
##
## Mcnemar's Test P-Value : 0.4404
##
## Sensitivity : 0.6923
## Specificity : 0.1818
## Pos Pred Value : 0.7500
## Neg Pred Value : 0.1429
## Prevalence : 0.7800
## Detection Rate : 0.5400
## Detection Prevalence : 0.7200
## Balanced Accuracy : 0.4371
##
## 'Positive' Class : 1
## Usando questo modello SVM il 36% delle osservazioni di test risulta mal classificato.
15.3 Alcuni cenni di teoria su SVM
Il grafico che segue mostra un esempio di SVM con due classi perfettamente separabili in \(\mathbb{R}^2\).
Quando le classi sono perfettamente separate (hard margin), allora SVM cerca la
“linea” che separa massimamente i punti delle due classi.
SVM quindi massimizza il margine \(m\).
Poiché la distanza tra l’origine e la linea \(w^Tx = k\) è \(\frac{k}{\left \| w \right \|}\), la dimensione del margine \(m\) è \(m=\frac{2}{\left \| w \right \|}\).
Se \(\{ x_1 , \dots , x_n \}\) è il nostro data set e \(y_i \in \{1,-1\}\) contiene l’etichetta di classe di \(x_i\) (dove gli \(x_i\) sono genericamente punti in \(\mathbb{R}^p\)):
La soglia di decisione dovrebbe classificare tutti i punti in maniera corretta
\(y_i \left(w^Tx_i + b \right) \ge 1 , \forall i \in 1, \dots, n\)Quindi la soglia di decisione può essere trovata risolvendo il seguente
problema di ottimizzazione vincolato (moltiplicatori di Lagrange):
\(\min \left\{ \|w\| \right \} \text{ s.t. } y_i \left(w^Tx_i + b \right) \ge 1 \forall i \in 1, \dots, n\)
Quando le classi non sono perfettamente separate (soft margin), allora SVM è esteso introducendo la cosiddetta funzione hinge loss:
\(max\left\{ 0, 1- y_i \left(w^Tx_i + b \right) \right\}\)
Questa funzione è zero se \(x_i\) ricade dal lato corretto del margine. Per dati nel lato sbagliato del margine, il valore della funzione è proporzionale alla distanza dal margine. Vogliamo quindi cercare di ottenere:
\(\min \left\{\left[\frac 1 n \sum_{i=1}^n \max\left(0, 1 - y_i(w \cdot x_i - b)\right) \right] + \lambda\| w \|^2 \right\}\)
dove il parametro \(\lambda\) determina il tradeoff tra la crescita nella dimensione del margine e il livello di sicurezza nel fatto che che \(x_i\) ricada nel lato corretto del margine. Quindi, per valori sufficientemente piccoli di \(\lambda\), il soft-margin SVM si comporterà in maniera identica all’hard-margin SVM se i dati di input sono linearmente classificabili, mentre otterrà comunque una regola di classificazione sensata se i dati non sono perfettamente separati.