SVM
Support Vector Machines
Ticiano A. C. Bragatto
[email protected]
TE-803 Inteligencia Artificial Aplicada - UFPR
Sumário



Vladimir Vapnik
Histórico
Conceito






Aumento de Dimensões
Espaços: Entrada versus Característica
Classificadores Lineares





Classificação
Regressão
Kernel trick
Margem Máxima
Problemas Primal e Dual
Aplicações
Conclusão
Como Programar
2
TE-803 Inteligencia Artificial Aplicada - UFPR
Vladimir Naumovich Vapnik







Soviético
Mestrado na Universidade do
Uzbequistão(1958)
Ph. D. em estatística no Institute
of Control Science de
Moscou(1964)
Professor nesse Instituto (19611990)
Nomeado professor do Royal
Holloway, Universidade de
Londres(1995)
AT&T Bell Labs (1991-2001)
Atualmente: Funcionário da NEC
e professor na Universidade de
Columbia(NY)
3
TE-803 Inteligencia Artificial Aplicada - UFPR
Histórico



Kernel linear: 1963 – Vladimir Vapnik
Kernel trick: 1992 – Boser, Guyon e Vapnik
Regressão: 1997 – Vapnik, Golowich e Smola
4
TE-803 Inteligencia Artificial Aplicada - UFPR
Conceito

Classificação




Duas classes
Regressão
Métodos de treinamento assistido
“Kernel trick”
5
TE-803 Inteligencia Artificial Aplicada - UFPR
Classificação(Vapnik 1963)

Duas classes







“Sim” ou “Não”
Preto ou Branco
Laranja ou Banana
0 ou 1
-1 ou 1 (usado para as
contas)
Linear (Vapnik 1963)
Kernel trick(Vapnik et al
1992)
6
TE-803 Inteligencia Artificial Aplicada - UFPR
Regressão(Vapnick - 1997)


É criada com máxima
margem, como
problemas de
classificação
Pode usar kernels
lineares e não
lineares(Gauss Radial
Basis Function(RBF),
polinomial, sigmoidal)
7
TE-803 Inteligencia Artificial Aplicada - UFPR
Kernel Trick



Converte problemas não lineares em lineares em
espaço de altíssima dimensão
Transforma funções que dependem de produto
interno
Substitui o produto interno com outras funções:




RBF:
Polinomial homogêneo:
Polinomial não homogêneo:
Sigmoidal:
8
TE-803 Inteligencia Artificial Aplicada - UFPR
Aumento de Dimensões

Para uma função de Base
Quadratica





O número de termos (para m
dimensões de entrada)
=(m+2)(m+1)/2
Para m=2  6-D
Para m=3  10-D
E para uma função de
kernel elevada a 3?
E como aproximar uma
Sigmoidal?
9
TE-803 Inteligencia Artificial Aplicada - UFPR
Espaços: Entrada versus característica
10
TE-803 Inteligencia Artificial Aplicada - UFPR
Classificadores Lineares


Dados os dois
conjuntos ao lado
Esta é uma boa forma
de separação?
11
TE-803 Inteligencia Artificial Aplicada - UFPR
Classificadores Lineares

Ou esta?
12
TE-803 Inteligencia Artificial Aplicada - UFPR
Classificadores Lineares


Qual destas é a
melhor?
Para RNA, qualquer
uma destas retas é
satisfatória, uma vez
que separou
corretamente os
conjuntos!
13
TE-803 Inteligencia Artificial Aplicada - UFPR
Classificadores Lineares

Para SVM, a melhor
reta é aquela que mais
se distancia dos
pontos(vetores) de
ambos os conjuntos,
formando a maior
margem possível
14
TE-803 Inteligencia Artificial Aplicada - UFPR
Classificadores Lineares
Margem Máxima





Intuitivamente é mais seguro
Se erramos na localização das
bordas, uma margem maior nos
dá menor chance de erro
É imune à remoção de algum
vetor que não seja um SV
Segundo a teoria VapnikChervonenkis(1960-90), o erro é
minimizado para uma margem
maximizada
Empiricamente funciona muito
bem
15
TE-803 Inteligencia Artificial Aplicada - UFPR
16
TE-803 Inteligencia Artificial Aplicada - UFPR
17
TE-803 Inteligencia Artificial Aplicada - UFPR
18
TE-803 Inteligencia Artificial Aplicada - UFPR
19
TE-803 Inteligencia Artificial Aplicada - UFPR
20
TE-803 Inteligencia Artificial Aplicada - UFPR
21
TE-803 Inteligencia Artificial Aplicada - UFPR
22
TE-803 Inteligencia Artificial Aplicada - UFPR
23
TE-803 Inteligencia Artificial Aplicada - UFPR
24
TE-803 Inteligencia Artificial Aplicada - UFPR
Problemas Primal e Dual

Primal


Restrição: Erro nos vetores de treino
Dual

Restrição: Parâmetro Custo C
25
TE-803 Inteligencia Artificial Aplicada - UFPR
Aplicações









Identificação de Proteínas, 2000
Impressões Digitais, 2001
Detecção e reconhecimento de faces, 1997/2000
Reconhecimento de textos, 1998
Assinaturas, 2003
Análise de Crédito, 1999
Indústria de Mineração, 2003
Siderurgia, 2004
Técnica ganhadora no concurso mundial de predição de
carga elétrica, 2001
26
TE-803 Inteligencia Artificial Aplicada - UFPR
Conclusão:
Otimização RNA versus SVM

RNA: Mínimo Local


Definir a quantidade de
neurônios na camada
intermediária
SVM: Mínimo Global

Definir o melhor
parâmetro C (custo)
27
TE-803 Inteligencia Artificial Aplicada - UFPR
Como programar:


MATLAB: Lenta porém não há necessidade
de preocupação com o parâmetro C
LibSVM:



Biblioteca existente em várias linguagens
Usada em diversas aplicações e nossa aula
prática
http://www.csie.ntu.edu.tw/~cjlin/libsvm/
28