Máquinas de Vetor de Suporte

Uma breve introdução às SVMs

O perceptron é um classificador linear e a busca por descida de gradiente permite encontrar um bom hiperplano separador mesmo quando o problema não é linearmente separável. Este separador porém não é único — dependendo dos pesos iniciais e de hiperparâmetros do algoritmo, separadores diferentes podem ser encontrados.

Dois separadores para um mesmo problema de classificação..

No exemplo acima, os dois separadores separam perfeitamente as duas classes. De fato, há infinitos separadores como esses. Podemos nos perguntar se devemos ter preferência sobre algum dos separadores ou, de forma mais genérica, se há um separador ideal.

Uma possível resposta advém de considerarmos que o objetivo último do modelo é generalizar os exemplos de treinamento para novos exemplos. Um novo exemplo será diferente dos exemplos utilizados para treinamento, mas suficientemente próximos no espaço de atributos para caracterizar uma classe. É desejável que o separador seja robusto a pequenas alterações (i.e. ruído) nos exemplos de cada lado — isto é, desejamos que para um exemplo mudar de classe, ele seja expressivamente diferente dos exemplos da classe a qual antes pertencia.

O separador azul da figura acima não possui esta robustez. Ele está excessivamente próximo da classe A, e mesmo exemplos muito próximos desta classe acabam sendo incorretamente classificados, como abaixo:

O novo exemplo é classificado como B, mesmo sendo mais semelhante a exemplos da classe A. Isso ocorre pois o hiperplano separador possui margens excessivamente pequenas

Isto leva a uma característica desejável para um separador: ele deve estar de alguma forma maximamente distante dos exemplos das classe que ele separa. Uma maneira de fazer isso é maximizar as margens do separador com relação a classe. O separador azul possui margens muito pequenas, enquanto o verde possui margens maiores.

Podemos encontrar o separador com máximas margens, em problemas linearmente separáveis, definindo dois hiperplanos paralelos que separam perfeitamente os exemplos e que estão maximamente distantes um do outro. O separador com máximas margens estará localizado exatamente no meio destes dois hiperplanos. Por estarem maximamente distantes um do outro, cada hiperplano encostará em pelo menos um exemplo de uma classe.

Hiperplano com máxima margens

De forma geral, os exemplos mais próximos de um separador são chamados de vetores de suporte. Estes são os exemplos mais difíceis de serem classificados pelo separador, pois qualquer alteração (e.g. ruído) pode fazer com que troquem de classe. O problema agora é encontrar os vetores de suporte que maximizam a margem do hiperplano. Este é um problema de otimização, onde no lugar de apenas exigirmos que o separador classifique todos exemplos corretamente, também exigimos que ele maximize a distância para os vetores de suporte.

De forma simplificada (e ineficiente), podemos definir um hiperplano e, então, deslocar hiperplanos paralelos em direção a cada classe, até que estes encostem em exemplos de cada classe (os vetores de suporte). Então, medimos o tamanho da margem. Podemos agora testar um novo hiperplano e verificar se a margem é maior, repetindo o processo até encontrar o hiperplano ótimo.

Máquinas de Vetor de Suporte (Support Vector Machines — SVM) são classificadores que fazem uso de vetores de suporte para encontrar um hiperplano separador que maximiza as margens. Em sua essência, são classificadores lineares como o perceptron e, quando apenas utilizam os vetores de suporte são chamados SVM lineares.

No entanto, SVM é uma metodologia mais abrangente e inclui uma etapa de transformação dos dados para que o modelo tenha possibilidade de lidar com exemplos que não são linearmente separáveis.

Vimos anteriormente que Engenharia de Atributos é importante e, em particular, a expansão de atributos permite encontrar uma representação alternativa para os dados que pode facilitar a tarefa de aprendizagem.

Na esquerda, representação de dados com atributos x1 e x2 originais. O problema não é linearmente separável. A adição de um atributo derivado x3=x1² + x2² torna o problema linearmente separável.

Em uma SVM, gera-se atributos derivados de forma automática utilizando uma função kernel. A função kernel projeta os exemplos originais para um espaço multi-dimensional, permitindo que a classificação ocorra neste espaço, sem aumento muito significativo no tempo de execução — algo denominado kernel trick. Importante observar que a projeção é feita de forma implícita, durante a execução do algoritmo de treinamento — isto é, não é uma etapa separada, onde geraria-se um novo conjunto de exemplos com mais atributos. Do contrário, o processo seria excessivamente ineficiente.

Diferentes funções geram diferentes combinações de atributos e o número de atributos resultantes (i.e. o número d de dimensões) é um parâmetro da função. Kernels comumente utilizados são o kernel polinomial e o kernel gaussiano. O tipo de kernel deve ser visto como um hiperparâmetro e é tipicamente necessário testar diferentes kernels, bem como diferentes números de dimensões, para verificar sua eficácia no problema em mãos.

Note que, no caso geral, não há garantias de que a aplicação de algum kernel irá tornar o problema linearmente separável. Ademais, o uso de kernel não substitui a etapa de geração de atributos derivados que tipicamente pode envolver interações complexas que não são capturadas pelas projeções feitas pelo kernel.

A união de separadores de máxima margem com o uso de kernels faz da SVM um modelo bastante eficaz em um grande número de problemas. Há versões do SVM para problemas de regressão (SVR) e pode-se expandir a SVM para problemas multi-classe (treinando múltiplas SVMs, uma para cada classe, por exemplo). Em todos os casos, os atributos devem ser numéricos, o que exige transformações quando os atributos são categóricos.