Introdução às Máquinas de
Vetores de Suporte
(SVM – Support Vector Machines)
Nessa Aula
Introdução
 Vetores de características
 Problemas linearmente separáveis
 Perceptron
 Máxima margem
 SVMs

Introdução



SVM é um algoritmo de aprendizagem de
máquina (máquina linear).
Baseia-se no fato que em altas dimensões do
espaço de características, todos os problemas
tornam-se linearmente separáveis.
Teoria introduzida por Vapnik e tem se mostrado
muito eficiente
 Resultados
melhores do a grande maioria dos
classificadores em diversas aplicações.
Álgebra Linear

No contexto de aprendizagem de máquina, um
vetor tem o seguinte formato:
 x1 
  
x x2
x 
 3


Cada atributo é uma dimensão do vetor.
O produto interno, ou produto escalar é
 x1   y1 
     
x , y   x2    y2   x1 y1  x2 y2  x3 y3
x  y 
 3  3
Problemas Linearmente Separáveis
Como podemos separar essas duas classes?
Perceptron
x1
x2
w1
w2

wn
xn
a
f(.)
 m

a  f   wik  xi  b 
 i 1

b
Cada atributo tem um peso associado. A soma desse
pesos multiplicados pelos atributos são passados por
uma função de ativação, e então uma regra de decisão
é usada.
Se o problema for linearmente separável, o perceptron
tem garantia de convergência, ou seja, ele vai encontrar
o hiperplano que separa as duas classes.
Hiperplanos
Qual é a melhor
fronteira??
O perceptron garante que vai separar os dados, mas não
garante que a fronteira (hiperplano) ideal será encontrado.
Hiperplanos

Qual seria o melhor hiperplano?
 R: Aquele
que maximiza a margem
SVM

O SVM é baseado em duas idéias chaves:
 Margem
Máxima
 “Kernel trick”
SVM

A função de decisão pode ser descrita
pela formula acima, na qual
K
é a função de kernel,

 e b são os parâmetros encontrados durante
o treinamento.
 y e x são o rotulo e o vetor de características,
respectivamente.
Margem Máxima

Considere duas classes linearmente
separáveis

Para tanto, um hiperplano na forma

De modo que
representa uma classe
representa outra classe
produto interno
Margem Máxima

Um conjunto é dito separado otimamente
pelo hiperplano se
Pois o hiperplano ótimo deve ficar à igual
distância das amostras mais próximas.
 O hiperplano que separa otimamente os
dados é dado por

Margem Máxima
Vetores de
Suporte
O treinamento do SVM consiste em maximizar a margem entre as classes
Os vetores que estão na borda de cada classe, são conhecidos como
vetores de suporte.
Exercício

Execute os seguinte applet para verificar
que somente os vetores de suporte são
importantes para definir a fronteira.

http://www.site.uottawa.ca/~gcaron/LinearApplet/LinearApplet.htm
Problemas Não Lineares
Os problemas reais geralmente não são
linearmente separáveis.
 Para utilizar máquinas lineares, é
necessário que os dados sejam
projetados em um dimensão onde os
mesmos sejam linearmente separáveis.

xi
Espaço de
entrada
 ( xi )
Espaço de
características
Exemplo
Hiperplano
Dados em 2D
Espaço de entrada
Dados em 3D
Espaço de características
Kernel Trick


A função que projeta o espaço de entrada no
espaço de características é conhecida com
Kernel
Baseado no teorema de Cover
 Dados
no espaço de entrada são transformados
(transf. não linear) para o espaço de características,
onde são linearmente separáveis.

O vetor  ( xi ) representa a “imagem” induzida no
espaço de características pelo vetor de entrada
Exemplo
Exemplo
Kernel Trick
Permite construir um hiperplano no
espaço de característica sem ter que
considerar o próprio espaço de
características de forma explicita.
 Toda vez que um produto interno entre
vetores deve ser calculado, utiliza-se o
kernel.
 Uma função de kernel deve satisfazer o
teorema de Mercer para ser válida.

Exemplos de Kernel
Tomada de Decisão
Como dito anteriormente, SVM são
classificadores binários, ou seja, separam
duas classes.
 Entretanto, a grande maioria dos
problemas reais possuem mais que duas
classes.
 Como utilizar os SVMs nesses casos?

 Pairwise,
um-contra-todos
Pairwise

Consiste em treinar classificadores
pairwise e arranjá-los em uma árvore
A competição se dá nos níveis inferiores, e o ganhador chegará ao
nó principal da árvore.
Número de classificadores para q classes = q(q-1)/2.
Um-Contra-Todos
Aqui, o número de classificadores é igual
a q.
 Treina-se um classificador ci para a
primeira classe, usando-se como contra
exemplos as outras classes, e assim por
diante.
 Para se obter a decisão final pode-se
utilizar uma estratégia de votos.

Aplicações

Categorização de texto
 Filtragem
de email
 Web-searching
 Classificação/Indexação de documento
 GED.
Aplicações

Imagens
 Indexação
de imagens
 Aplicações médicas
 Recuperação de imagens (Image Retrieval)
Aplicações

Reconhecimento da escrita.
 Geralmente
com resultados melhores que
outros tipos de classificadores.

Bio-Informática
 Categorização
automática de genes em DNA.
 Seqüências de aminoácidos.
 Classificação de proteínas.
Applets

Os seguintes links contém applets que simulam
a aprendizagem de SVMs

http://neuron.eng.wayne.edu/java/AHK/EPM_pp.html
http://cortex.informatik.tu-ilmenau.de/~koenig/monist/applets/html/AppletSVM.html
