Support Vector Machine — SVMs
Artigo de suporte ao seu aprendizado *ba dum tss*
SVMs — Support-Vector Machines são classificadores lineares, ou seja, utilizam um hiperplano para classificar as classes.
Hiperplano
Em geometria, hiperplano é um subespaço com uma dimensão a menos que seu espaço ambiente, alguns exemplos:
- hiperplano de um espaço de duas dimensões: reta;
- hiperplano de um espaço de três dimensões: plano (uma parede);
Definição da função da fronteira de decisão
A função é definida por x como sendo os pontos, v são os coeficientes de cada ponto e a é o um escalar (número) de interceptação da função.
Quando o resultado é 0 sabemos que o ponto está exatamente sobre a função de separação definida, a classificação é feita quando o número é maior ou menor do que zero, e para isso basta abraçarmos a função anterior com outra para verificar o sinal em cada ponto:
Mas ainda resta um problema, muitas retas podem cumprir a função de separar as classes, como escolher uma delas?
A escolha é feita de maneira a maximizar a margem (distância entre os pontos mais próximos da reta e a reta). E isso é ótimo, pois ganhamos uma margem mais segura para a classificação.
Para determinar essa reta precisamos de alguns pontos para dar suporte, e daí vem o nome Máquina de vetores de suporte 😃
Dessa forma podemos definir a nossa fronteira de decisão como sendo todos os pontos no conjunto de dados que satisfaçam a nossa função:
Podemos interpretá-la como ‘todo x pertencente ao conjunto dos reais tal que a função da fronteira de decisão resulte em 0’.
Mas ainda precisamos maximizar a margem, e isso pode ser feito encontrando a distância mínima entre os pontos dos dados e a fronteira de decisão e depois maximizando a distância entre os mínimos encontrados.
Entretanto, ainda temos o problema de ter dois vetores de tamanhos diferentes na mesma orientação que satisfaçam o problema, e isso pode ser resolvido utilizando a Norma-2 (ou Norma Euclidiana) e colocando a restrição do seu resultado como 0.
Dualidade em otimização matemática
Normalmente um problema de otimização pode ser descrito de duas formas diferentes, a primal (solução primária) e a dual (solução mais simples, gerada).
Por exemplo, podemos ter o problema de achar o mínimo ou máximo de uma função, sendo que ela pode ser sujeita à determinadas restrições de igualdade ou desigualdade, essa seria a solução primal.
Pela possível dificuldade de manipular todas essas restrições, nós inserimos os multiplicadores de Lagrange (variáveis duais) combinando as restrições com a função.
SVMs Hard Margin (SVMs lineares)
Nesse caso nós consideramos que os dados são linearmente separáveis, ou seja, falando de classificação binária, uma das classes estaria de um lado da reta e a outra classe estaria do outro lado.
SVMs Soft Margin (Slack variables)
Aqui é possível que exista erros, ou seja, casos não separáveis.
Esperamos que o erro seja 0 para a maioria dos pontos, mas ainda existente, por isso inserimos um termo na nossa equação que busca minimizar a soma dos erros.
O peso dos erro permitido é definido arbitrariamente por quem utiliza, e quanto maior o peso, mais restrições existirão na definição da largura da margin de partição das instâncias, o que também pode levar à overfitting.
SVMs não lineares (kernels)
Existem casos que não é possível separar bem as instâncias de forma linear (com uma reta), neste caso podemos mapear os dados para um espaço dimensional maior (onde eles serão linearmente separáveis por estarem mais dispersos) e criar um classificador linear nesse espaço. Isso também é chamado de kernel trick.
Podemos então projetar esse classificador em um espaço de duas dimensões e veremos provavelmente uma curva, mas originalmente ele terá mais dimensões.
Esse mapeamento depende da condição de mercer, que é complexa de ser provada, por isso existe um catálogo de funções já provadas e que podemos consultar para saber se é possível utilizar o SVM não linear. Entretanto como escolher os kernels e seus parâmetros é uma questão em aberto ainda.
Kernel linear
Corresponde ao SVM linear que descrevemos anteriormente, e são indicados onde:
- As instâncias são linearmente separáveis;
- Os dados são esparsos, como em categorização de textos;
- Os dados possuem muitas características.
Kernel polinomial
Caso escolhamos o número de polinômios como 1, então se torna o kernel linear. Popular em processamento de imagens, onde normalmente o espaço dimensional é transformado para uma alta dimensão.
Kernel gaussiano (RBF — Radial Basis Function)
Considerado uma boa primeira tentativa quando você não sabe muitos sobre os dados. Ele também consegue um bom desempenho em dados que parecem ilhados quando vistos em uma baixa dimensão (como vistos na imagem 1).
Kernel sigmóide
Equivalente à utilização de uma rede neural de duas camadas (rede perceptron) usando uma função de ativação sigmóide.
Observações sobre kernels não lineares
É importante lembrar que a variação dos parâmetros para teste em cada tipo de kernel vai influenciar no overfitting e um método comum de teste é variar na escala logarítmica, ou seja, ir multiplicando 10 nos valores (0.1, 1, 10, etc).
O melhor método utilizado é testar os parâmetros utilizando validação cruzada, de forma a encontrar os melhores parâmetros testando as combinações.
Observações sobre SVM
Além de saber as bibliotecas e a teoria, assim como quase qualquer técnica, também existem alguns detalhes que caso seguidos podem prover um melhor desempenho em vários quesitos.
Normalização (scaling)
Pode ser feita no intervalo [0;1] ou [-1;1], normalmente já implementada por várias bibliotecas, bastando informar a opção no parâmetro da mesma. Importante lembrar de utilizar a mesma normalização no treinamento e no teste.
Variáveis categóricas
O SVM não é recomendado para utilização com variáveis categóricas, entretanto é possível utilizar transformando as variáveis categóricas nominais em variáveis dummies.
Outliers
Existe uma sensibilidade da fronteira de decisão à outliers, o que pode fazer com que ela seja alterada devido à presença deles.
Desbalanceamento
Existe uma sensibilidade ao desbalanceamento, pois a reta de decisão calculada leva em consideração o erro, e tendo classes minoritárias levará à um maior erro. Por isso o ideal é balancear os dados.
Uso na classificação
Na fase de treinamento são realizados os cálculos para encontrar o hiperplano que melhor separa as classes.
Na fase de classificação é verificado de que lado do hiperplano está uma instância através da função 2 descrita acima.
Gostou do conteúdo?
Siga a Luna no Medium. E não se esqueça de deixar alguns aplausos 👏🏽Qualquer dúvida ou sugestão é só deixar nos comentários!
