class: center, middle, title-slide .title[ # Máquinas de vetores de suporte (SVM) ] .subtitle[ ## Em classificação ] .author[ ### Jaime Utria ] .institute[ ### Departamento de EstatÃstica - UFF ] --- <!-- macro comandos matemáticos Latex --> <script type="text/x-mathjax-config"> MathJax.Hub.Config({ TeX: { Macros: { vet: ["{\\mathbf #1}",1], prodint: ["\\langle #1, #2 \\rangle",2], posto: ["{\\mathrm{posto} (#1)}",1], tr: ["{\\mathrm{tr} (#1)}",1] } } }); </script> ## Introdução - Os algoritmos de *SVM* (*Support Vector Machines*) foram introduzidos por Cortes e Vapnik (1995). - Os *SVM* são generalizações não lineares do algoritmo *Generalized Portrait* desenvolvido por Vapnik e Chervonenkis (1964). - Os *SVM* podem ser usados tanto para problemas de classifição quanto de regressão. - Os *SVM* competem com outros métodos amplamente utilizados, como os *GLM*, *LDA*, *GAM*, *NN*, *CART*, etc. --- ## Classes linearmente separáveis (perfeitamente separáveis) <img src="data:image/png;base64,#svm-separating-hyperplanes-1.png" width="2048" /> --- ## Classificador de margem rÃgida (*HMC: Hard Margin Classifier*) - Para duas classes perfeitamente separáveis, existe um número infinito de **hiperplanos** separadores (fronteiras de decisão). - Qual o "melhor"? - Aqui, o principal critério a ser atendido: boa generalização. - Em vista disso, gostariamos de uma fronteira de decisão que forneça a máxima separação entre as classes. - O *HMC*, é justamente, aquele que atende essa condição e o tipo mais simples de *SVM*. --- <img src="data:image/png;base64,#svm-hmc-1.png" width="1792" /> --- - O *HMC* é ótimo no sentido que separa as duas classes maximizando a distância dos pontos mais próximos das duas classes (vetores suporte). - A distância máxima é chamada de margem `\(M\)`. Geometricamente, o *HMC* pode ser encontrado como segue: 1. Encontre o *convex hull* (envoltura convexa) ao redor de cada classe. 2. Encontre o segmento mÃnimo (distância mÃnima) que conecta os dois *convex hull*. 3. O bissector perpendicular desse segmento é o *HMC*. 4. As fronterias da margem são aquelas paralelas ao *HMC* e que passam pelos vetores de suporte. --- ## *HMC* obtido por um problema de otimização convexa - Seja `\(\mathcal{L} = \{(\mathbf{x}_i,y_i): \mathbf{x}_i \in \mathbb R^p, y_i \in \{-1,+1\}\}\)` o conjunto de treino. - Pode-se mostrar que `\(M = 1/||\boldsymbol{\beta}||\)`. Logo, `$$\begin{align}\min_{\beta_0,\beta_1,\ldots, \beta_p} \frac{1}{2} ||\boldsymbol{\beta}||^2\\ \text{s.a. } y_i(\beta_0 + \boldsymbol \beta^\top\mathbf{x}_i) \ge 1, \; i = 1, \ldots, n\end{align}$$` - `\(y_i(\beta_0 + \boldsymbol \beta^\top\mathbf{x}_i)/||\boldsymbol{\beta}||\)` é a distância (perpendicular) da i-ésima amostra à fronteira de decisão. - Note que a solução do problema de otimização acima não permite que nenhuma amostra esteja no lado errado da margem; daà o nome de **classificador de margem rÃgida**. --- ## Classes perfeitamente separáveis mas com ruÃdo <img src="data:image/png;base64,#svm-noisy-1.png" width="1792" height="500" /> --- ## Classificador de margem flexÃvel (*SMC: Soft Margin Classifier*) - Por vezes podemos conseguir separar perfeitamente as classes, porém, não é desejável, por exemplo, no caso da presença de valores atÃpicos. - Neste caso, podemos relaxar as restrições, permitindo algumas observações ficarem do lado errado. - Os novos margens obtidos com esse relaxamento, são chamados de margens suaves ou flexÃveis; daà o nome de **classificador de margem flexÃvel**. --- ## *SMC* como problema de otimização convexa Seja `\(C \ge 0\)` um **hiperparâmetro de regularização**. O problema a ser resolvido é o seguinte: `$$\begin{align}&\min_{\beta_0,\beta_1,\ldots, \beta_p, \xi_1, \ldots, \xi_n} \frac{1}{2} ||\boldsymbol{\beta}||^2 + C \sum_{i=1}^n \xi_i \\ &\text{s.a. } \xi_i \ge 0, \; y_i(\beta_0 + \boldsymbol \beta^\top\mathbf{x}_i) \ge 1-\xi_i, \; i = 1, \ldots, n\; \end{align}$$` - `\(\xi_1, \ldots, \xi_n\)` são variáveis de "folga", que medem as violações das observações à s restrições impostas por seus hiperplanos. De modo que `\(\xi_i = 0\)`, se a i-ésima observação está do lado certo. - Ao variar o valor de `\(C\)`, permitimos que algumas amostras quebrem as margens, o que faz o modelo mais robusto à presença de valores atÃpicos. - Quando `\(C = 0\)` recuperamos o *HMC*, e quando `\(C = \infty\)`, temos a máxima superposição das classes. --- .center[ <img src="data:image/png;base64,#smc-slacks.png" width="1192" height="500" /> **Fonte**: Izenman, A. ] --- <img src="data:image/png;base64,#smc-1.png" width="2048" /> --- ## *SVM* para Classificação Binária: Ideias principais - **Separação de classes**: procura-se o melhor hiperplano separador das classes, maximizando a **margem** (menor distância entre os pontos do conjunto de treino e o hiperplano separador). As amostras localizados nas fronteiras dessas classes são chamados de **vetores suporte**. - **Superposição de classes**: amostras de uma classe que estão no outro lado do hiperplano separador são ponderados com baixo peso para reduzir sua influência. - **Não linearidade**: quando não é possÃvel separar as classes por um separador linear, utilizamos um **kernel** para mapear os dados do conjunto original para um conjunto de alta dimensão (*feature space*). Os hiperplanos separadores são construÃdos nesse novo espaço. - **Solução do problema**: envolve otimização quadrática e pode ser resolvida com métodos conhecidos. --- ## Classificadores *SVM* 1. **Classificador de margem rÃgida**: A classe positiva e a classe negativa são perfeitamente separáveis por uma fronteira linear. 2. **Classificador de margem flexÃvel**: A classe positiva e a classe negativa não podem ser separados perfeitamente por uma fronteira linear ou podem ser perfeitamente separáveis, porém, temos alguns valores atÃpicos. 3. **Classificador de margem não linear**: A classe positiva e a classe negativa não são linearmente separáveis, ou seja, utilizar um separador linear pode não conduzir a resultados satisfatórios, portanto devemos considerar fronteiras não lineares (via o "truque" de *kernel*). --- ## Diabetes .center[ <!-- --> ] --- ``` r library(caret) library(e1071) # svm models ``` ``` r diabetes <- readRDS("diabetes.rds") diabetes <- diabetes[,-1] diabetes$Outcome <- as.factor(diabetes$Outcome) set.seed(12345) train_index <- createDataPartition(y = diabetes$Outcome, p = 0.8, list = F) training <- diabetes[train_index,] testing <- diabetes[-train_index,] ``` --- <div class="small-output"> ``` r # Ajustamos um SMC aos dados de treino svm.model <- svm(Outcome ~ Glucose + Pregnancies, data = training, type = "C-classification", kernel = "linear", scale = FALSE) svm.model ``` ``` ## ## Call: ## svm(formula = Outcome ~ Glucose + Pregnancies, data = training, type = "C-classification", ## kernel = "linear", scale = FALSE) ## ## ## Parameters: ## SVM-Type: C-classification ## SVM-Kernel: linear ## cost: 1 ## ## Number of Support Vectors: 219 ``` --- ``` r # coeficientes do hiperplano separador coef(svm.model) ``` ``` ## (Intercept) Glucose Pregnancies ## -5.03685527 0.03194273 0.13086894 ``` A equação do hiperplano (reta) separador é: `$$-5,04 + 0,03 Glucose + 0,13 Pregnancies = 0$$` ou equivalentemente, `$$Glucose = \frac{5,04}{0,03} - \frac{0,13}{0,03} Pregnancies$$` **OBS**. Em geral, para o hiperplano `\(\beta_0 + \beta_1 x_1 + \beta_2 x_2 = 0\)`, temos `$$f(x_1)= x_2 = -\frac{\beta_0}{\beta_2} - \frac{\beta_1}{\beta_2}$$`. --- .center[ <!-- --> ] --- <div class="small-output"> ``` ## Confusion Matrix and Statistics ## ## Reference ## Prediction 0 1 ## 0 64 20 ## 1 7 15 ## ## Accuracy : 0.7453 ## 95% CI : (0.6514, 0.8249) ## No Information Rate : 0.6698 ## P-Value [Acc > NIR] : 0.05839 ## ## Kappa : 0.3643 ## ## Mcnemar's Test P-Value : 0.02092 ## ## Sensitivity : 0.4286 ## Specificity : 0.9014 ## Pos Pred Value : 0.6818 ## Neg Pred Value : 0.7619 ## Prevalence : 0.3302 ## Detection Rate : 0.1415 ## Detection Prevalence : 0.2075 ## Balanced Accuracy : 0.6650 ## ## 'Positive' Class : 1 ## ``` --- <div class="small-output"> ``` r # Ajustamos um SMC aos dados de treino svm.model2 <- svm(Outcome ~ ., data = training, type = "C-classification", kernel = "linear", scale = FALSE) svm.model2 ``` ``` ## ## Call: ## svm(formula = Outcome ~ ., data = training, type = "C-classification", ## kernel = "linear", scale = FALSE) ## ## ## Parameters: ## SVM-Type: C-classification ## SVM-Kernel: linear ## cost: 1 ## ## Number of Support Vectors: 203 ``` --- ``` r # coeficientes do hiperplano separador coef(svm.model2) ``` ``` ## (Intercept) Pregnancies Glucose ## -6.992709323 0.096912931 0.028286033 ## BloodPressure SkinThickness BMI ## -0.006900647 -0.007564727 0.057314823 ## DiabetesPedigreeFunction Age ## 0.961815416 0.024819739 ``` --- <div class="small-output"> ``` ## Confusion Matrix and Statistics ## ## Reference ## Prediction 0 1 ## 0 64 15 ## 1 7 20 ## ## Accuracy : 0.7925 ## 95% CI : (0.7028, 0.8651) ## No Information Rate : 0.6698 ## P-Value [Acc > NIR] : 0.003808 ## ## Kappa : 0.5019 ## ## Mcnemar's Test P-Value : 0.135593 ## ## Sensitivity : 0.5714 ## Specificity : 0.9014 ## Pos Pred Value : 0.7407 ## Neg Pred Value : 0.8101 ## Prevalence : 0.3302 ## Detection Rate : 0.1887 ## Detection Prevalence : 0.2547 ## Balanced Accuracy : 0.7364 ## ## 'Positive' Class : 1 ## ``` --- ## Classificadores de margem não lineares - Se quisermos considerar fronteiras de decisão não lineares, precisamos aumentar a dimensão do espaço de dados por meio de outras funções. - No caso de duas variáveis preditoras `\(x_1\)` e `\(x_2\)`, por exemplo, podemos considerar o espaço determinado por `\(x_1,x_2,x_1^2 + x_2^2\)`. <img src="data:image/png;base64,#svm-circle-1.png" width="3072" /> --- - No entanto, uma abordagem mais conveniente é usar *kernels*. - De fato, pode-se mostrar que o classificador linear flexÃvel pode ser escrito da forma: `$$f(\mathbf x) = \sum_{\mathbf{x}_i \in S} \gamma_i \langle \mathbf{x},\mathbf{x}_i \rangle + \delta$$` em que `\(S\)` é o conjunto de vetores suporte, `\(\gamma_i\)` são funções de `\(\beta_0\)`, `\(\boldsymbol{\beta}\)` e `\(\langle \mathbf{x}, \mathbf{y} \rangle\)` indica o produto interno de `\(\mathbf{x}\)` e `\(\mathbf{y}\)`. - O classificador de margem flexÃvel usa um *kernel* linear, da forma: `$$K(\mathbf x, \mathbf y) = \langle \mathbf{x}, \mathbf{y} \rangle = \mathbf{x}^\top \mathbf{y}$$` - Se quisermos um classificador em um espaço caracterÃstico de dimensão maior, podemos incluir polinômios de grau maior ou funções mais gerais. --- ## Principais *kernels* 1. lineares: `\(K(\mathbf x, \mathbf y) = \mathbf{x}^\top \mathbf{y}\)` 2. polinomiais: `\(K(\mathbf x, \mathbf y) = (a + \gamma\mathbf{x}^\top \mathbf{y})^d\)` 3. radiais: `\(K(\mathbf x, \mathbf y) = \exp(-\gamma||\mathbf x - \mathbf y||^2)\)`, `\(\gamma > 0\)` constante. 4. tangentes hiperbólicas: `\(K(\mathbf x, \mathbf y) = \tanh(k_1 + k_2 \mathbf{x}^\top \mathbf{y})\)`. Os classificadores de margem não linear são obtidos misturando os de margem flexÃveis com *kernels* não lineares: `$$f(\mathbf x) = \beta_0 + \sum_{\mathbf{x}_i \in S} \gamma_i K(\mathbf{x},\mathbf{x}_i) + \delta$$` --- ``` r # kernel polinomial svm.model3 <- svm(Outcome ~ ., data = training, type = "C-classification", kernel = "polynomial", # kernel polinomial degree = 3, # grau do polinomio gamma = 1, cost = 4, # parâmetro de regularização coef0 = 1, # termo independente do kernel scale = FALSE) ``` --- <div class="small-output"> ``` ## Confusion Matrix and Statistics ## ## Reference ## Prediction 0 1 ## 0 52 21 ## 1 19 14 ## ## Accuracy : 0.6226 ## 95% CI : (0.5233, 0.715) ## No Information Rate : 0.6698 ## P-Value [Acc > NIR] : 0.8714 ## ## Kappa : 0.1343 ## ## Mcnemar's Test P-Value : 0.8744 ## ## Sensitivity : 0.4000 ## Specificity : 0.7324 ## Pos Pred Value : 0.4242 ## Neg Pred Value : 0.7123 ## Prevalence : 0.3302 ## Detection Rate : 0.1321 ## Detection Prevalence : 0.3113 ## Balanced Accuracy : 0.5662 ## ## 'Positive' Class : 1 ## ``` --- ``` r # kernel radial svm.model4 <- svm(Outcome ~ ., data = training, type = "C-classification", kernel = "radial", gamma = 1, cost = 10, scale = FALSE) ``` --- <div class="small-output"> ``` ## Confusion Matrix and Statistics ## ## Reference ## Prediction 0 1 ## 0 71 35 ## 1 0 0 ## ## Accuracy : 0.6698 ## 95% CI : (0.5718, 0.7581) ## No Information Rate : 0.6698 ## P-Value [Acc > NIR] : 0.5457 ## ## Kappa : 0 ## ## Mcnemar's Test P-Value : 9.081e-09 ## ## Sensitivity : 0.0000 ## Specificity : 1.0000 ## Pos Pred Value : NaN ## Neg Pred Value : 0.6698 ## Prevalence : 0.3302 ## Detection Rate : 0.0000 ## Detection Prevalence : 0.0000 ## Balanced Accuracy : 0.5000 ## ## 'Positive' Class : 1 ## ``` --- # Ajuste de hiperparâmetros ``` r ctrl <- trainControl(method = "repeatedcv", number = 10,repeats = 3) ``` ``` r grid <- expand.grid( degree = c(2, 3, 4), scale = c(0.001, 0.01, 0.1), # equivalente ao parâmetro gamma C = c(0.5, 1, 2) ) ``` --- ``` r model.svmPoly <- train( Outcome ~., data = training, method = "svmPoly", tuneGrid = grid, trControl = ctrl ) ``` ``` r model.svmPoly$bestTune ``` ``` ## degree scale C ## 15 3 0.01 2 ``` ``` r predictions <- predict(model.svmPoly, newdata = testing) ``` --- <div class="small-output"> ``` r confusionMatrix(predictions, testing$Outcome) ``` ``` ## Confusion Matrix and Statistics ## ## Reference ## Prediction 0 1 ## 0 62 15 ## 1 9 20 ## ## Accuracy : 0.7736 ## 95% CI : (0.6821, 0.8492) ## No Information Rate : 0.6698 ## P-Value [Acc > NIR] : 0.01311 ## ## Kappa : 0.4649 ## ## Mcnemar's Test P-Value : 0.30743 ## ## Sensitivity : 0.8732 ## Specificity : 0.5714 ## Pos Pred Value : 0.8052 ## Neg Pred Value : 0.6897 ## Prevalence : 0.6698 ## Detection Rate : 0.5849 ## Detection Prevalence : 0.7264 ## Balanced Accuracy : 0.7223 ## ## 'Positive' Class : 0 ## ``` --- ## Créditos das imagens https://bradleyboehmke.github.io/HOML/svm.html#fn40