Support Vector Machines

Posted by Anna Eloyr, Arthur Nunes on July 4, 2020

Support Vector Machines

Support Vector Machine (ou Máquina de Vetores de Suporte) é um método de aprendizado de máquinas supervisionado usado principalmente para problemas de classificação. Surge como a generalização e automatização de outros modelos, que por sua vez, utilizam-se de determinados conceitos estruturantes.

Introdução: Conceitos estruturantes

Dilema Viés-Variância

O Dilema Viés-Variância é um conceito fundamental ao se analisar a aplicação de um algoritmo de aprendizado de máquinas a determinado problema. Como um modelo é, por natureza, uma simplificação de uma relação real mais complexa, surge um trade-off relacionado à flexibilidade do modelo.

O Viés diz respeito a quão distante o modelo está de representar a relação real desejada. Ou seja, um modelo com muito viés tem dificuldade em representar as nuances de uma relação mais complexa, como um modelo linear e uma relação não-linear, por exemplo. Já a Variância diz respeito ao tamanho da variação entre os resultados obtidos pelo modelo para os dados de treino e os dados de teste.

Em problemas de classificação, no qual um conjunto de dados é utilizado para treinar o modelo, surge a necessidade de optar entre:

  • Um modelo pouco flexível, que terá difícil adaptação à relação real (tendo um grande viés), mas pela inflexibilidade, não apresenta uma grande diferença em relação aos dados de teste (pouca variância).
  • Um modelo bem mais flexível, que se adapta bem aos dados de treino (minimizando o viés), mas apresenta uma grande diferença de resultado em relação aos dados de teste (apresentando uma grande variância). A esse fenômeno, é dado o nome de overfitting.

Um modelo ótimo busca diminuir tanto o viés quanto a variância, visando uma boa representação do fenômeno estudado e um bom desempenho classificando novas entradas.

Método de Validação Cruzada

O Método de Validação Cruzada é uma ferramenta utilizada para avaliar o melhor modelo ou melhor combinação de parâmetros de um modelo. Em problemas de classificação, no qual o aprendizado supervisionado (ou seja, um conjunto de dados é utilizado para treinar e outro para testar o modelo) é empregado, é preciso determinar qual parte dos dados será usado para cada etapa desse processo.

Esse método resolve essa questão dividindo esse conjunto de dados em partes iguais (geralmente 10) e usando um a um como teste após utilizar os demais como treino. No final, os resultados são sumarizados e é determinado um modelo ou conjunto de parâmetros ótimo para o problema.

Maximal Margin Classifier

O Maximal Margin Classifier (ou Classificador da Margem Máxima) é o método utilizado em problemas de classificação, no qual seja possível utilizar um hiperplano para separar as observações baseado no aspecto desejado. No caso de uma observação com 2 variáveis (ou seja, um plano bidimensional), o hiperplano será uma reta (espaço unidimensional). Portanto, os dados precisam ser totalmente separáveis.

Como existe uma infinidade de posições possíveis para o hiperplano caso os dados sejam perfeitamente separáveis, esse classificador busca determinar essa posição a partir da maximização da margem.

Figura 2: Á esquerda, existem duas classes de observações, rosa e azul, cada uma delas possuem medidas de duas variáveis.Três hiperplanos possível, dentre vários, são mostrados em preto.À direita, um hiperplano é utilizado como um classificador.

A margem diz respeito ao espaço vazio que fica entre as observações do extremo interno de cada grupo (ou seja, as observações da “ponta” mais próxima ao outro grupo) e o hiperplano.

Como nesse classificador a margem é intransponível, utiliza-se otimização para alargá-la o máximo possível à fim de criar um espaço de segurança para as classificações. Assim, devemos resolver o seguinte problema:

As restrições asseguram que cada observação estará no lado correto do hiperplano e, no mínimo, a uma distância M do mesmo. Consequentemente, M representa a margem, e o problema de otimização escolhe $\beta_0, \beta_1, \beta_2, …, \beta_p$ para maximizar M. Essa é a exata definição de margem máxima.

Figura 2: Existem duas classes de observações, rosa e azul. O hiperplano plano ótimo é representado pela linha sólida. A margem é a distância entre a linha sólida e a linha pontilhada de cada lado.

Porém, caso exista algum outlier no conjunto de dados ou os grupos não sejam completamente separáveis, esse método perde muito em eficiência ou até a aplicação, pois ou a margem fica pequena demais ou não é possível traçar o hiperplano.

Figura 3: À esquerda, duas classes de observações são classificadas por um hiperplano ótimo. À direita, uma observação em azul foi acrescentada, causando uma mudança dramática na escolha do hiperplano ótimo, da reta pontilhada para a negritada.

Support Vector Classifier

O Support Vector Classifier (ou Classificador dos Vetores de Suporte) é uma generalização do modelo anterior, visto que se aplica aos casos em que o Maximal Margin Classifier não se aplica.

Isso se dá pela flexibilização em relação à invasão da margem por parte de determinadas observações. Esse classificador, ao permitir isso busca um melhor mecanismo de classificação no longo prazo (permitindo a classificação “errada” de certas observações). Portanto, o problema de otimização do classificador anterior ganha uma nova forma, com um parâmetro que controlará o “grau” de permissão de invasão à margem.

onde C é a um parâmetro não-negativo de ajustamento. Como no problema de otimização anterior, M é a vriável que representa a margem, que procuramos maximizar. $\epsilon_1$, $\epsilon_2$, …, $\epsilon_n$ são variáveis de erro que permitem observações com problemas de classificação.

Após a resolução do problema, classificamos uma observação teste, $x^*$a ao determinar de qual lado do hiperplano ela ficará. Ou seja, classificamos a observação com base no sinal da seguinte equação:

\[f\left(x^{*}\right)=\beta_{0}+\beta_{1} x_{1}^{*}+\ldots+\beta_{p} x_{p}^{*}\]

A partir disso, observa-se a aplicação dos dois conceitos estruturantes: o modelo permitirá que algumas observações sejam classificadas de maneira errada (com um maior viés) para que a classificação no longo prazo seja melhor (uma menor variância). O parâmetro que controla essa permissão, C, é determinado por validação cruzada, achando o ponto ótimo de equilíbrio entre essas duas características.

Support Vector Machine (SVM)

O Support Vector Classifier é um método natural de classificação para dois conjuntos de dados se o delimitador entre as classes é linear. Entretanto, na prática, lidamos com limites não lineares.

Figura 4: À esquerda, as observações são classificadas em duas classes, com um delimitador não linear entre elas. À direita, o Support Vector Classifier procura um classificador linear, mas tem um desempenho ruim.

Uma solução para esse problema é mapear o conjunto de treinamento de seu espaço original (não linear) para um novo espaço de maior dimensão, denominado espaço de características (feature space), que é linear.

Para isso, precisamos encontrar uma transformação não linear, $\boldsymbol{\varphi}(x)=\left[\varphi_{1}(x), \ldots, \varphi_{m}(x)\right]$. Essa transformação mapeia o espaço original das observações para um novo espaço de atributos $m$ - dimensional, o qual pode ser muito maior do que o espaço original. Nesse novo espaço, as observações passam a ser linearmente separáveis. Com a função de transformação, nosso problema de otimização recai pra uma SVM linear.

Ao analisar a estimação dos coeficientes no problema de otimização e a representação do classificador linear $f(x)$, que é dada por:

\[f(x)=\beta_{0}+\sum_{i \in \mathcal{S}} \alpha_{i}\left\langle x, x_{i}\right\rangle\]

onde $\mathcal{S}$ é a coleção de índices desses pontos de suporte, concluímos que apenas precisamos dos produtos escalares.

O algoritmo linear depende somente de $\left\langle x, x_{i}\right\rangle$, portanto o algoritmo transformado também dependerá somente de $\left\langle \boldsymbol{\varphi}(x), \boldsymbol{\varphi}(x_i)\right\rangle$.

Esse produto escalar entre os vetores transformados é chamado de função Kernel:

\[K(x, x_i)=\left\langle \boldsymbol{\varphi}(x), \boldsymbol{\varphi}(x_i)\right\rangle\]

A função Kernel nos permite operar no espaço original, sem precisar computar as coordenadas dos dados em um espaço dimensional superior. Esse método é chamado de truque de Kernel.

Por exemplo, vamos supor que $x$ e $y$ são observações em $3$ dimensões:

\[\begin{array}{l} \mathbf{x}=\left(x_{1}, x_{2}, x_{3}\right)^{T} \\ \mathbf{y}=\left(y_{1}, y_{2}, y_{3}\right)^{T} \end{array}\]

Vamos assumir que precisamos mapear $x$ e $y$ para um espaço 9-dimensional.

Para isso, precisamos realizar as seguintes operações para chegar ao resultado final, que é apenas um escalar:

\[\phi(\mathbf{x})=\left(x_{1}^{2}, x_{1} x_{2}, x_{1} x_{3}, x_{2} x_{1}, x_{2}^{2}, x_{2} x_{3}, x_{3} x_{1}, x_{3} x_{2}, x_{3}^{2}\right)^{T}\] \[\phi(\mathbf{y})=\left(y_{1}^{2}, y_{1} y_{2}, y_{1} y_{3}, y_{2} y_{1}, y_{2}^{2}, y_{2} y_{3}, y_{3} y_{1}, y_{3} y_{2}, y_{3}^{2}\right)^{T}\] \[\phi(\mathbf{x})^{T} \phi(\mathbf{y})=\sum_{i, j=1}^{3} x_{i} x_{j} y_{i} y_{j}\]

Porém, se usarmos a função Kernel, ao invés de fazer operações complexas em um espaço 9-dimensional, obtemos o mesmo resultado com um espaço 3-dimensional ao calcular o produto escalar do transposto de $x$ e y:

\begin{equation} \begin{aligned} K(\mathbf{x}, \mathbf{y}) &=\left(\mathbf{x}^{T} \mathbf{y}\right)^{2}
&=\left(x_{1} y_{1}+x_{2} y_{2}+x_{3} y_{3}\right)^{2}
&=\sum_{i, j=1}^{3} x_{i} x_{j} y_{i} y_{j} \end{aligned} \end{equation
}

Um exemplo de Kernel é:

\[K\left(x_{i}, x_{i^{\prime}}\right)=\left(1+\sum_{j=1}^{p} x_{i j} x_{i^{\prime} j}\right)^{d}\]

que é conhecido como Kernel polinomial de grau $d,$ onde $d$ é um inteiro positivo.

Outra opção bastante popular é o Kernel radial, que possui a seguinte forma:

\[K\left(x_{i}, x_{i^{\prime}}\right)=\exp \left(-\gamma \sum_{j=1}^{p}\left(x_{i j}-x_{i^{\prime} j}\right)^{2}\right)\]

onde $\gamma$ é uma constante positiva.

Quando o Support Vector Classifier é combinado com uma função Kernel, como o polinomial, o classificador resultante é conhecido como Support Vector Machine.

Note que, de forma geral, a função do hiperplano terá a seguinte forma:

\[f(x)=\beta_{0}+\sum_{i \in \mathcal{S}} \alpha_{i} K\left(x, x_{i}\right)\]

Figura 5: À esquerda, um SVM com Kernel polinomial de grau 3 é aplicado a um conjunto de dados não-linear. À direita, um SVM com Jernel radial é utilizado.

Aplicação

Iremos fazer uma aplicação do método SVM, utilizando R. Para isso, vamos precisar de alguns pacotes:

library(tidyverse)    # data manipulation and visualization
library(e1071)        # SVM methodology
library(ISLR)         # contains example data set "Khan"
library(RColorBrewer) # customized coloring of plots

Para demonstrar uma classificação não-linear, precisamos construir um conjunto de dados:

x <- matrix(rnorm(200*2), ncol = 2)
x[1:100,] <- x[1:100,] + 2.5
x[101:150,] <- x[101:150,] - 2.5
y <- c(rep(1,150), rep(2,50))
dat <- data.frame(x=x,y=as.factor(y))

ggplot(data = dat, aes(x = x.2, y = x.1, color = y, shape = y)) + 
  geom_point(size = 2) +
  scale_color_manual(values=c("#000000", "#FF0000")) +
  theme(legend.position = "none")

Obtendo o seguinte gráfico:

Vamos utilizar 100 amostras aleatórias para serem nossas observações de treinamento. Baseado no formato do nosso conjunto de dados, escolhemos o Kernel radial:

set.seed(123)

train <- base::sample(200,100, replace = FALSE)
svmfit <- svm(y~., data = dat[train,], kernel = "radial", gamma = 1, cost = 1)

O gráfico após aplicação do SVM é dado por:

plot(svmfit, dat)

Utilizamos a função tune() para encontrar a melhor condição para os parâmetros $C$ e $\gamma$.

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)))
tune.out$best.model

A tabela criada, comparando os dados reais com os dados previstos, é chamada de Matriz de Confusão. Seu funcionamento é simples: é uma tabela de contingência em que na linha está o valor previsto e na coluna o valor observado

(valid <- table(true = dat[-train,"y"], pred = predict(tune.out$best.model,
                                                       newx = dat[-train,])))

Para descobrirmos a porcentagem de acertos do nosso modelo, basta somarmos os valores da diagonal da tabela, e depois dividir o resultado pelo total de observações da amostra utilizada. No nosso exemplo, obtemos os seguintes valores:

    pred
true  1  2
   1 55 28
   2 12  5

Portanto, temos 65 acertos diante de um total de 100 observações. Dessa forma, ao aplicar o SVM na nossa amostra, 65% das classificações foram feitas de maneira correta.

Referências

Gareth James et al. An introduction to statistical learning. Vol. 112. Springer, 2013.

Alexandre Kowalczyk. “Support vector machines succinctly”. Em: Syncfusion Inc(2017).