Classificador SVM
Support Vector Machine
AULA 12
DATA MINING
Sandra de Amo
Idéia Geral
Margem
para
B2
Margem
para
B1
B1
B2
Problema a resolver

Qual o melhor “hiperplano separador” ?


Margem estreita: mínimas perturbações no hiperplano
podem produzir um hiperplano não-separador.
Margem grande: a propriedade de “separação” de classes
é preservada por pequenas perturbações no hiperplano.

Conclusão: Melhor hiperplano separador é o que
apresenta a maior margem.

Encontrar o melhor hiperplano separador =
Problema de Otimização com restrições
Casos a tratar

Fronteira é Linear (espaço vetorial)


Dados são “separáveis”
Dados não são “separáveis” ??
B1 ainda é o melhor
separador !
Mas B2 é o que seria
produzido usando uma
técnica própria para dados
Ruídos ?
“separáveis”
Enfoque Soft Margin:
Produz fronteira que tolera
algumas “exceções” na
separação.
E quando a fronteira não é linear ?
Transformação R2  R2 (não- linear)
Transforma a fronteira não – linear numa fronteira linear
Dados são separáveis

Hiperplano = subespaço vetorial de
dimensão n-1
Conjunto dos vetores x
w.x + b = 0
b = deslocamento do hiperplano a partir
da origem
w = vetor ortogonal ao hiperplano
Cálculo do deslocamento b
w . x = (||x||.cosθ) ||w|| = c ||w||
supondo ||w|| = 1
w.x – c = 0
k
Logo b = - c
Fronteira superior
w.x = c + k
w.x + b = k
w
c
Fronteira inferior
w.x = c - k w.x + b = - k
x
Equações simplificadas das fronteiras
B1
w x+ b = 0
w
w x+b =1
w x + b = -1
Obs: Para tornar as
equações das
fronteiras mais simples
multiplica-se w pelo
escalar 1/k de modo
que o lado direito é 1
ou -1
d
b12
b11
d = 2/ ||w||
Cálculo da margem d em função do
vetor w
B1
w
d = projeção do vetor x1 – x2
sobre o vetor w
d
x1
x2
Lei dos cossenos
w. (x1-x2) = (||x1 – x2||.cosθ) ||w|| =
d ||w||
w.x1 + b = 1
w. x2 + b = -1
b11
b12
w .(x1 – x2) = 2
Logo : d = 2/||w||
Problema


Dado um conjunto de k amostras
(x1, c1),…(xk,ck), onde xi são vetores de n dimensões e ci é a
classe (1 ou -1) das amostras
Encontrar o hiperplano determinado pelo vetor w e o escalar b tal
que:
 Qualquer amostra xi da classe ci = 1 satisfaça
 w. xi + b >= 1
 Qualquer amostra xi da classe ci = -1 satisfaça
 w.xi + b <= -1
 Margem d = 2/||w|| é maximal
2
 Ou equivalentemente: 2/||w|| é maximal
2
 Ou equivalentemente: f(w) = ||w|| /2 é minimal
Problema de Otimização com
restrições de desigualdade

Dados (x1,c1), …, (xN,cN) determinar w e b de tal
modo
2


F(w) = ||w|| / 2 seja mínimo
as N desigualdades abaixo sejam satisfeitas
ci (w. xi + b) >= 1
Classificador SVM

Consiste no vetor w e no escalar b que
caracterizam o melhor hiperplano separador.

Como usar o classificador SVM para
classificar uma amostra x ?
1
classe ( x ) = 
- 1
se w x + b  1
se w x + b  - 1
Multiplicadores de Lagrange : Técnica para
Solução de Problemas de Otimização
Com Restrições de Igualdade
Problema: Encontrar o mínimo da função
satisfazendo as restrições
Método: Achar o minimo do lagrangiano associado
= 0
1. Defina o Lagrangiano
λi = multiplicadores de Lagrange
2. Encontre as derivadas parciais de L com respeito aos xj e λi e iguale a zero.
3. Resolva as d+p equações e encontre os valores de x1,...,xd e λ1,..., λp
Exemplo
satisfazendo a restrição
Encontre o mínimo da função
Solução:
Solução das equações:
Caso 1:
Caso 2:
Portanto: a função f atinge seu valor mínimo para
Multiplicadores de Lagrange : Técnica para
Solução de Problemas de Otimização
Com Restrições de Desigualdade
Problema: Encontrar o mínimo da função
satisfazendo as restrições
Equivalente a minimizar o Lagrangiano associado a f(x)
L(x,λ1,…,λq) =
≤0
Sujeito às restrições λ1≥ 0 …, λq ≥ 0
Repare que: L(x,λ1,…,λq) ≤ f(x) para quaisquer valores de x = (x1,…,xq),
Logo: valores de x que minimizam L = valores de x que minimizam f
Dual de Wolfe (Fletcher 1987)
Minimizar L(x,λ1,…,λq) =
com respeito às variáveis x1,…,xq
sujeito às restrições λ1≥ 0 …, λq ≥ 0
∂L
= 0 para i = 1,…q
∂λi
Problema dual de Wolfe
Maximizar L(x,λ1,…,λq) =
com respeito às variáveis λ1,…, λq
sujeito às restrições λ1≥ 0 …, λq ≥ 0
∂L
= 0 para i = 1,…q
∂xi
PROBLEMAS DE OTIMIZAÇÃO CONVEXOS
Conjunto convexo
Função convexa
Conjunto não-convexo
Um problema de otimização é convexo se:
 A função objetivo é convexa
 As restrições determinam um conjunto convexo
As restrições de Karush-Kuhn-Tucker
(Fletcher 1987)
Problema Dual de Wolfe (DW)
Maximizar L(x,λ1,…,λq) =
com respeito às variáveis λ1,…, λq
sujeito às restrições λ1≥ 0 …, λq ≥ 0
∂L
= 0 para i = 1,…q
∂xi
Se o problema de otimização é convexo
então as seguintes condições são
necessárias e suficientes para
x1,…,xq, λ1, …, λq serem soluções do
problema DW
Restrições de Karush-Kuhn-Tucker (KTT)
Exemplo
Encontre o mínimo da função
2
f(x,y) = (x – 1) + (y – 3)
sujeito às restrições
2
Solução: Maximizar o Lagrangiano dual de Wolfe com respeito a λ1, λ2
2
2
Lagrangiano: L(x,y,λ1,λ2) = (x-1) + (y-3) + λ1(x+y-2) + λ2(x-y)
sujeito às restrições KTT:
Estudar todos os possíveis
casos para estas equações
Caso 1: λ1 = 0 e λ2 = 0
x-1= 0 e y-3 = 0
x = 1 e y =3
Viola a restrição x + y ≤ 2
Caso 2: λ1 = 0 e λ2 > 0
x – y = 0 , 2(x-1) + λ2 = 0, 2(y-3) - λ2 =0
Caso 3: λ2 = 0 e λ1 > 0
x + y – 2 = 0 , 2(x-1) + λ1 = 0, 2(y - 3) + λ1 =0
Solução: x = 0, y = 2, λ1 = 2
Solução: x = 1, y = 3, λ2 = -2
Viola as restrições x + y ≤ 2 e λ2 > 0
Solução possível !
Caso 4: λ1 > 0 e λ2 > 0
x + y – 2 = 0 , 2(x-1) + λ1 + λ2 = 0, 2(y - 3) + λ1 – λ2 = 0
Solução: x = 1, y = 1, λ1 = 2, λ2 = - 2
Viola a restrição λ2 > 0
Obervação:
 Transformar o problema de otimização original no problema de otimização do
Lagrangiano simplica as equações.
 Resolver o problema de otimização do Lagrangiano nem sempre
é simples, e envolve a aplicação de métodos numéricos sofisticados.
 Diversos softwares estão disponíveis (ex. MATLAB)
Referências Teóricas:
R. Fletcher. Practical Methods of Optimization.
John Wiley and Sons, Inc., 2nd Edition, 1987
Voltando ao nosso problema SVM
2
Minimizar f(w) = ||w|| /2
Restrições: yi (w. xi + b) ≥ 1 ,
i = 1,…,N
N = número de amostras
Exercício: Mostrar que o Problema de Otimização SVM é
Convexo. Logo podemos utilizar as restrições KTT para
auxiliar em sua solução.
Voltando ao nosso problema SVM
Restrições KTT
Problema Equivalente: Dual de Wolfe
(1)
MAXIMIZAR LP
Com relação às variáveis λ1, …, λN
(2)
(3)
(4)
(5)
Resolve-se as equações (1), (2), (3), (4) e (5) , começando por (5),
considerando-se os 4 casos em que a expressão (5) é nula.
Outra maneira de solucionar Lp
Exercicio: 1) Substituir as restrições (1) e (2) na fórmula do Lagrangiano LP
(1)
(2)
Resultado: Lagrangiano “Dual”
2) Mostrar que a nova formulação das restrições KTT (3) e (5) é dada por
(3) (Σ λj yi yj xj . xi) + yi b ≥ 1
j
(5) λi [Σ λj yi yj xj . xi) + yi b – 1] = 0
j
Problema de Otimização mais simples : LD
Achar o máximo da Função
(nas variáveis λ1,…, λN)
Satisfazendo as restrições
λ1 ≥ 0,….λN ≥ 0
Lagrangiano dual LD é mais simples :
• Um número menor de variáveis λ1,…, λN
• Considera-se as derivadas parciais de LD com relação a λi e iguala-se a zero.
• Considera-se somente as soluções satisfazendo as duas restrições dadas.
Método para achar a solução de LP a
partir das soluções de LD
Para obter o vetor w:
Para obter o deslocamento b usa-se a equação (restrição KTT)
Para classificar uma nova amostra
z = (z1,...,zm)
Ou equivalentemente
Testa o sinal de w.z + b
o sinal de :
Vetores de suporte (Support Vectors)
Ou λi = 0 ou
λi ≠ 0  amostra xi pertence a umas das margens
Tais amostras são chamadas : Vetores de Suporte
Hiperplano separador (determinado por w e b) só depende dos vetores suporte
Exercício
Vetores
de suporte
(Support
Vectors)
Pede-se:
1) Encontre o hiperplano separador
2) Plote as amostras e o hiperplano separador num plano
3) Classifique a nova instância (0.45, 0.29), sem plotá-la no plano, usando
o classificador.
Resposta
Vetores
Suporte
Vantagens e Desvantagens
Vantagens
Flexibilidade: Técnica aplicada a outras tarefas: detecção de novidades,
anomalias, previsão
Muitas aplicações bem sucedidas: bioinformática, reconhecimento de face,
visão computacional, reconhecimento de escrita manual,
Intuição geométrica, elegância matemática
Poucos parâmetros, resultado final é estável, reproduzível, não depende de
ajuste de parâmetros (como redes neurais, por exemplo).
Existem vários algoritmos de otimização robustos
Método é simples de usar
Desvantagens
Interpretabilidade ?
Resultados podem ser afetados pela técnica usada para normalizar os dados
Referências
Surveys
Kristin P. Bennett, Colin Campbell : Support Vector Machines: Hype or
Hallelujah? SIGKDD Explorations. Volume 2, Issue 2, pp. 1-13. 2000
 Christopher Burges. A Tutorial on Support Vector Machine for Pattern
Recognition. Data Mining and Knowledge Discovery 2(2): 121-167, 1998.

Livros
Vapnik, V. Statistical Learning Theory. Wiley, 1998.

Vapnik, V. The Nature of Statistical Learning Theory. Springer, New
York, 1995.

Cristianini N. and Shawe-Taylor J. An Introduction to Support Vector
Machines and other Kernel-based Learning Methods. Cambridge University
Press, 2000. www.support-vector.net

B. Scholkopf, A.J. Smola. Learning with Kernels: Support Vector Machines,
Regularization, Optimization and Beyond. MIT Press, 2001
Software SVMLight (livre)
http://svmlight.joachims.org/

Como utilizar classificadores binários para
classificar dados multi-classes ?
Método “um contra todos”
C = {C1, C2, ..., Ck} : conjunto de k classes

Constrói-se k modelos do classificador binário
1)
pos = C1 , neg = {C2,...,Ck}
---------> Modelo M1
2)
pos = C2, neg = {C1,C3,...,Ck}
---------> Modelo M2
3)
...
k)
Pos = {Ck}, neg = {C1,C2,...,Ck-1} ---------> Modelo Mk
Para classificar uma nova amostra X :

1)
2)
3)
Classifica X usando cada um dos modelos M1, ... , Mn
Verifica qual classe teve o maior número de votos entre os
classificadores.
Esta será a classe escolhida para classificar X
Exemplo


M1
M2
M3
M4
C = {C1, C2, C3, C4}
X : nova amostra
VOTOS RECEBIDOS POR CADA CLASSE
C1
C2
C3
C4
X
+
-
+
-
+
-
+
+
-
M1
M2
M3
M4
C1
C2
C3
C4
1
1
1
1
0
0
1
1
0
1
0
1
0
1
1
0
Classe C1 é a mais votada para classificar X
Logo X é classificada na classe C1