Support Vector Machines (SVM)
Eduardo Borges
Gabriel Simões
Roteiro
• Introdução
– O que é SVM?
– Motivação
– Exemplo simples
• SVM
– Dados linearmente separáveis
– Dados linearmente inseparáveis
• Exemplo
Introdução
• Método supervisionado de aprendizado de
máquina
• Classificação em dois grupos
– Classificação de múltiplas classes não é uma
limitação, pois pode-se construir uma SVM para
cada classe
• Apresenta resultados melhores que muitos
métodos populares de classificação
Introdução
• 1968: base matemática
– Teoria de Lagrange
• [Vapnik et al, 1992] Primeiro artigo
• [Vapnik et al, 1998] Definição detalhada
• Última década
– Série de artigos com aplicações de SVM
– Série de artigos com otimizações de SVM
• SMO, por exemplo
Introdução
• SVM são utilizadas em diversas áreas:
– Bioinformática
– Reconhecimento de assinaturas
– Classificação de texto e imagens
– Identificação de spams
– Reconhecimento de padrões diversos
– Identificação de dados replicados
Motivação da SVM
Como separar as duas classes?
Como separar as duas classes?
Motivação da SVM
Reta / Plano / Hiperplano
Qual o hiperplano ótimo?
Menor erro de classificação
?
Conceitos de SVM
• Qual o hiperplano ótimo?
– Menor erro de classificação
– Maior margem
• Distância entre vetores de suporte e o hiperplano
Conceitos de SVM
• Qual o hiperplano ótimo?
– Menor erro de classificação
– Maior margem
• Distância entre vetores de suporte e o hiperplano
Como funciona para dados
linearmente separáveis?
• Dados de treinamento
– Tuplas no formato (X1, X2, ..., Xn, Y)
• Atributos Xi
• Classe Y (+1, -1)
• Conjunto dito linearmente separável, se existir
um hiperplano H (no espaço de entrada) que
separe as tuplas de classes diferentes
• Determinar os vetores de suporte
• Encontrar o hiperplano ótimo
– Com maior margem
O Hiperplano (H)
• Pontos que pertencem a H satisfazem a equação
w⋅x+b= 0
• w: vetor normal a H
w = w1, w2, ..., wn
• ||w|| é a norma euclidiana de w
√ (w ⋅ w ) = √ (w12 + ... + wn2 )
• |b|/||w|| é a distância perpendicular de H até a origem
• A distância r entre um ponto x e o hiperplano H é
r = g(x) / ||w||
r = ( w ⋅ x + b ) / ||w||
• Orientação de w
X2
– Define o lado do plano em que os pontos
pertencem a classe +1
• b > 0 (origem no lado positivo)
• b < 0 (origem no lado negativo)
• b = 0 (origem pertence ao plano)
H
w
|b|/||w||
x
r
X1
O Hiperplano (H) – Exemplo
• H: w ⋅ x + b = 0
H: w1x1 + w2x2 + b = 0
• Aplicando os pontos (5,0) e (0,5)
5w1 + b = 0
5w2 + b = 0
• Isolando b
5w1 = 5w2 (w1 = w2)
• Escolhendo arbitrariamente w1 = 1
b = -5
• Norma de w
||w|| = 
(w12+w22)
= 2
• Distância da origem
X2
5
H
|b| / ||w|| = 5/2
• Distância de um ponto x = (5,2) até H
r = ( w ⋅ x + b ) / ||w||
r = (5w1 + 2w2 -5 ) / 2
r = (5+2-5) / 2
r = 2
w
5/ 2
x = (5,2)
2
5
X1
Hiperplano ótimo
•
•
•
•
r+: distância entre H e o ponto positivo mais próximo
r-: distância entre H e o ponto negativo mais próximo
margem: r+ + rObjetivo da SVM é encontrar w0 e b0 para a maior margem
• H0: w0 ⋅ x + b0 = 0
• H1: w0 ⋅ xi + b0 = 1
• H2: w0 ⋅ xi + b0 = -1
= ( w ⋅ x + b ) / ||w||
r+ = 1 / ||w||
r+
X2
H1
H2
H0
r+
r-
w0
• Para o hiperplano ótimo, r+ = rr- = 1 / ||w||
Margem = 2 / ||w||
X1
Hiperplano ótimo
margem = 2 / ||w||
• É aquele que possui maior margem
• É aquele que possui menor ||w||
• Determinação do hiperplano
– Problema de otimização restrita
– Minimizar uma função de custo (produto interno)
sujeito a restrições
– Multiplicadores de Lagrange
• Fora do escopo
• Exemplo Prático
Exemplo
•
•
•
•
•
•
•
•
-1, 0, -1
0, -1, -1
0, 1, -1
1, 0, -1
3, -1, +1
3, 1, +1
6, -1, +1
6, 1, +1
Exemplo
•
•
•
•
•
•
•
•
-1, 0, -1
0, -1, -1
0, 1, -1
1, 0, -1
3, -1, +1
3, 1, +1
6, -1, +1
6, 1, +1
H1: w ⋅ x + b = 1
H2: w ⋅ x + b = -1
w1x1 + w2x2 + b = -1
1w1 + 0w2 + b = -1
 b = -1 - w1
w1x1 + w2x2 + b = 1
3w1 -1w2 + b = 1
 w2 = 3w1 -1 -w1 -1
 w2 = 2w1 -2
3w1 +1w2 + b = 1
 3w1 + 2w1 -2 -1 -w1 = 1
 w1 = 1
 b = -2
 w2 = 0
(1, 0) ⋅ x - 2 = 0
X1 = 2
Exemplo
(1, 0)  -1
(3, -1)  +1
(3, 1)  +1
H: (1, 0) ⋅ x - 2 = 0
H: x1 - 2 = 0
Exemplo
Dados de Teste
(4, 2), (1.5, 0.5), (0, -2)
4 - 2 = 2 [+1]
1.5 - 2 = -0.5 [-1]
0 - 2 = -2 [-1]
Como funciona para dados
linearmente inseparáveis?
• Mapeamento do espaço de características de
D dimensões para HD, onde HD > D
• Vetores de entrada são mapeados de forma
não linear
• Após transformado, o novo espaço de
características deve ser passível de separação
linear
Exemplo
Como separar as duas classes com apenas um ponto?
X1 Class
0
+1
1
-1
2
-1
3
+1
Class +1
Class -1
0
1
2
3
4
Exemplo
SVM usa uma função não linear sobre os atributos do
espaço de características inicial
X1 Class
0
+1
1
-1
2
-1
3
+1
Class +1
Class -1
0
1
2
Φ(X1) = (X1, X12)
Esta função torna o problema bidimensional
3
4
Exemplo
SVM usa uma função não linear sobre os atributos do
espaço de características inicial
Class +1
X1 X1
2
Class
0
0
+1
1
1
-1
Class -1
10
8
6
2
4
-1
3
9
+1
4
2
0
Φ(X1) = (X1, X12)
Esta função torna o problema bidimensional e os
dados linearmente separáveis
0
1
2
3
4
Exemplo
X1 X12 Class
• w ⋅ x + b = +1
0
0
+1
1
1
-1
2
4
-1
3
9
+1
w1x1 + w2x2 + b = +1
0w1 + 0w2 + b = +1
3w1 + 9w2 + b = +1
b=1
w1x1 + w2x2 + b = -1
1w1 + 1w2 + b = -1
2w1 + 4w2 + b = -1
substituindo b e após w1
 w1 = -2 - w2
 -4 -2w2 + 4w2 + 1 = -1
• w ⋅ x + b = -1
• w⋅x+b=0
w1x1 + w2x2 + b = 0
w2 =1 e w1 = -3
 -3x1 + x2 + 1 = 0
Exemplo
H: -3x1 + x2 + 1 = 0
Dados de Teste (1.5), (-1), (4)
Class +1
Class -1
-1
0
1
2
3
4
3
4
(1.5) mapear para (1.5, 2.25)
-3 . 1.5 + 2.25 + 1 = - 1.15 [-1]
Class +1
(-1) mapear para (-1,1)
-3 . -1 + 1 + 1 = 5 [+1]
Class -1
10
8
6
(4) mapear para (4,16)
-3 . 4 + 16 + 1 = 5 [+1]
4
2
0
0
1
2
Outro Exemplo
Como separar as duas classes com apenas uma reta?
X1 X2 Class
1
1
-1
-1
1
-1
1
-1
-1
-1
-1
-1
2
2
+1
-2
2
+1
2
-2
+1
-2
-2
+1
Outro Exemplo
Φ(x1, x2) =
(4-x2+|x1-x2|, 4-x1+|x1-x2|),
(x12 + x22) > 2
(x1, x2)
Esta função mantém o problema bidimensional
Outro Exemplo
Vetores de Suporte
x1
x2
Class
1
1
-1
-1
1
-1
1
-1
-1
-1
-1
-1
2
2
+1
6
6
+1
10
6
+1
6
10
+1
Outro Exemplo
H1: w ⋅ x + b = 1
H2: w ⋅ x + b = -1
Vetores de Suporte
w1x1 + w2x2 + b = -1
1w1 + 1w2 + b = -1
 w1 = -1 -b -w2
w1x1 + w2x2 + b = 1
2(-1 -b -w2) + 2w2 + b = 1
-2 -2b -2w2 +2w2 + b = 1
 b = -3
(2-1) x2 = (2-1) x1
2x2 - x2 = 2x1 - x1
x2 = x 1
w1 = w2 = 1
H0: (1,1) ⋅ x -3 = 0
x1 + x2 -3 = 0
Equação da reta
x1
x2
Class
1
1
-1
2
2
+1
Outro Exemplo
Φ(x1, x2) =
(4-x2+|x1-x2|, 4-x1+|x1-x2|),
(x12 + x22) > 2
(x1, x2)
Esta função realmente separa o espaço original de forma linear?
Dados de teste (5,5)
Φ(5,5) = (-1, -1)
Dados de teste (4,4)
Φ(4,4) = (0, 0)
Erros de classificação!
(4,4)
(5,5)
Outro Exemplo
• Função de mapeamento não é ideal
Problema
• Como escolher a função Φ(x) tal que o espaço de
características transformado seja eficiente para
classificação e não possua custo computacional
alto demais?
• Funções de Núcleo (kernel)
• Polinomial
• Gaussiano
• Sigmoid
– Sempre aumentam o número de dimensões
• Algumas vezes aumentam bastante!
Outro Exemplo
• Φ[x1,x2] = [x1, x2, ((x12+x22)-5)/3 ]
LibSVM
• http://www.csie.ntu.edu.tw/~cjlin/libsvm/
• Disponível em Java e C++
• Applet para brincar
Bibliografia
• Burges, J. A tutorial on support vector machines for pattern recognition. Data
Mining Knowledge Discovering, 1998, pp. 121–167.
• Han, J.; Kamber, M. Data Mining: Concepts and Techniques. 2nd edition,
Morgan Kaufmann, 2006.
• Hearst, M.; Schölkopf, B.; Dumais, S.; Osuna, E.; Platt, J. Trends and
controversies-support vector machines. IEEE Intelligent Systems 13: 18-28,
1998.
• Joachims, T. Text categorization with Support Vector Machines: Learning with
many relevant features. Proceedings of ECML-98, 10th European conference on
machine learning, 1998, pp 137–142.
• Kumar, V ; Tan, P.; Steinbach, M. Introduction to Data Mining. Addison-Wesley,
2005.
• Lin, T.; Ngo, T. Clustering High Dimensional Data Using SVM. Rough Sets, Fuzzy
Sets, Data Mining and Granular Computing. Lecture Notes in Computer Science,
Springer, 2007.
• Mangasarian, O. Data mining via support vector machines. System Modeling
and Optimization, Kluwer Academic Publishers, Boston, 2003, 91-112.
• Vapnik, V. Statistical LearningTheory. Wiley, 1998.
• Ventura, D. A (not finished) tutorial example for linear and non-linear SVMs.
Available at http://axon.cs.byu.edu/~dan/478/misc/SVM.example.pdf