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:

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).