Aprendizado de Máquina

Aprendizado de Máquina
Aprendizado Supervisionado
7a parte
Até o momento ...
• … já vimos
–
–
–
–
Árvores de decisão
Algoritmos associativos
Naive Bayes
k-NN
Até o momento ...
• … já vimos
–
–
–
–
–
Árvores de decisão
Algoritmos associativos
Naive Bayes
k-NN
SVM
SVM
• Conceitos
• Margem
• Margem flexivel
• Múltiplas classes
Até o momento ...
• … já vimos
–
–
–
–
–
Árvores de decisão
Algoritmos associativos
Naive Bayes
k-NN
SVM – separação não-linear
SVM
• Casos não-separáveis
–
Na prática, pontos não são linearmente
separáveis
•
–
SVM só produz funções lineares
Ideias?
SVM
• Mudar o espaço de busca
– Onde o novo espaço seja separável
SVM
• Mudar o espaço de busca
– Onde o novo espaço seja separável
• {(x1, y1), (x2, y2), …, (xr, yr)}
• {(φ(x1), y1), (φ(x2), y2), …, (φ(xr), yr)}
SVM
• Mudar o espaço de busca
– Onde o novo espaço seja separável
SVM
• Problemas:
– Essa transformação pode levar à
“maldição da dimensionalidade”
• O número de dimensões pode se tornar
imenso
• A quantidade de exemplos permanece a
mesma
– O problema torna-se mais difícil
SVM
• Como mudar o espaço?
– Kernels
• Um kernel é uma função que retorna o
produto escalar das imagens de seus
argumentos
– Então:
• Dada uma função K, é possível verificar se
K é um kernel
SVM
• “Truque do kernel”
– Nós só precisamos realizar o produto
escalar
• Não precisamos saber o vetor ϕ(x)
• O vetor separador passa a ser:
〈 w ⋅ x〉 + b =
r
∑
i= 1
yiα i 〈 x i ⋅ x〉 + b = 0
• Que é equivalente a:
SVM
• Como encontrar um kernel?
– Toda função definida, semi-positiva, e
simétrica é um kernel
• Existe uma função ϕ tal que:
SVM
• Exemplo simples
– Kernel baseado em funções polinomiais
SVM
• Exemplo simples
– Kernel quadrático (polinômio de grau 2)
2
2
( x1 , x2 )  ( x1 , x2 , 2 x1 x2 )
• Seja o ponto original ((2,3), -1)
SVM
• Exemplo simples
– Kernel quadrático (polinômio de grau 2)
2
2
( x1 , x2 )  ( x1 , x2 , 2 x1 x2 )
• Seja o ponto original ((2,3), -1)
• No espaço expandido é ((4,9,8.5), -1)
SVM
• Propriedades de um kernel k
– Fechamento:
• k+k' é um kernel
• ck é um kernel, para c > 0
• ak + bk' é um kernel, para a e b > 0
– Kernels mais complexos a partir de
kernels mais simples
• Modularidade
SVM
• Kernels comuns
– Linear:
– Polinomial:
– Gaussiano:
Obrigado!