Prof. Dr. Hugo Valadares Siqueira

Aula 16 – SVM e SVR

Redes Neurais Artificiais

• Propostas por Vladimir Vapnik e Alexey Chervonenkis em 1963 e incrementadopor Boser, Guyon e Vapnik em 1992;• Modelos de machine learning usados

para problemas de classificação e regressão;• A versão linear faz classificação linear

binária não probabilística;• O modelo encontra a fronteira de

separação (hiperplano) entre duas classes;• Usam aprendizado supervisionado –

precisa de um conjunto de treinamento;• Essa distância entre o hiperplano e o

primeiro ponto de cada classe costuma ser chamada de margem.

Máquinas de Vetores Suporte (SVM)

• Inicialmente a SVM faz a separação das classes, definindo assim cada ponto pertencente a cada uma delas;• Em seguida maximiza a margem, definindo suas distâncias;•Outliers podem ser desconsiderados;•A aplicação das SVMs implica na otimização de uma função

quadrática, que possui apenas um mínimo global;

Máquinas de Vetores Suporte (SVM)

•Grande capacidade de generalização;• Base teórica foi elaborada

por Vapnik e Chernovenkisatravés da Teoria de Aprendizado Estatístico, proposta por estes autores nas décadas de 60 e 70.

• No treinamento da versão não linear, as entradas são mapeadas no espaço multidimensional e utiliza-se regressão para encontrar um hiperplano;

• A versão que faz classificação não linear foi proposta em 1992:

O algoritmo ajusta o hiperplano de margem máxima em um espaço transformado;

A transformação pode ser não linear e o espaço transformado de dimensão elevada;

Uso do chamado truque de Kernel para aumentar a dimensionalidade.

Suport Vector Machines

Classificadores lineares

Denota +1

Denota -1

• Discutimos o classificador linear nas aula 8 sobre Perceptron e Adaline;• Como seria possível classificar esses dados?• Uma possibilidade é usar o descriminante

linear, como já visto.

a

yestf x

f(x,w,b) = sgn(wx + b)

wTx + b < 0

wTx + b > 0

• Sendo a função sinal:

ou

• Qualquer uma das fontreiras abaixo consegue fazer corretamente a sepação linear;• Mas qual o melhor proposta?• Observe que a depender da fronteira de separação a capacidade de

generalização diminui (classificação errada de um novo dado).

Classificadores lineares

Classificação

errada

• A margem de um classificadorlinear é a largura máxima que a fronteira pode ter antes de atingir um ponto;•Maximizar a margem é uma boa

estratégia de acordo com a intuição e com teorias de aprendizagem (teoria PAC); • Implica que apenas os vetores de

suporte são importantes; •Os outros exemplos de

treinamento podem serignorados;• Empiricamente esse classificador

funciona muito bem.

Margens dos Cassificadores

• O classificador linear de margem máxima é o que possui a maior margementre todos osclassificadores linearesque resolvem o problema;• Os vetores suporte serão

correspondentes as amostras que tangenciam as margens;Este é o tipo maissimples de SVM (chamado de LSVM -SVM linear).

Margens dos Classificadores

Vetores suporte

O que sabemos:w.x+ + b = +1 w.x- + b = -1• Ainda:w.(x+ - x-) = 2 w.x + b = 0 (hiperplano separador)

SVM Linear

Lugar geométrico dos hiperplanos separadoresconsiderando amostras da fronteira

• Veja que a margem é função do módulo do vetor normal ao hiperplano:

𝜌 =𝐱+ − 𝐱− 𝐰

| 𝐰 |=

2

||𝐰||

x-

ρ = Largurada margem

x+

• Para um dado vetor de pesos w e intercepto b, a separação entre o hiperplano e o dado de entrada mais próximo é chamada de margem de separação e é denotada por ρ;

• Sempre que for possível obter um ρ > 0, existirão infinitos hiperplanos, dentre os quais se busca um hiperplano particular em que a margem de separação ρ é maximizada;

• De acordo com esta condição, a superfície de decisão é dita ser o hiperplano ótimo e o método de aprendizado de máquina para determina-lo é denominado máquina de vetores suporte (SVM);

Margem

• Os dados de treinamento que se encontram à distância ρ do hiperplano são chamados vetores suporte (support vectors);

• Em termos conceituais, eles são os pontos que se encontram mais perto da superfície de decisão e, portanto, são os de classificação mais difícil;

• Como tal, eles têm uma relação direta com a localização da superfície de decisão.

• Classificar corretamente todo o conjunto de treinamento

se yi = +1se yi = -1

ou NOTAÇÃO COMPACTA

para todo i

• Maximizar a margem que é equivalente a minimizar ;

• Podemos formular um Problema de Otimização Quadrática e resolver para w e b:

Minimizar:

com a restrição:

i

SVM Linear - Objetivos

𝜌 =2

||𝐰||1

2𝐰T𝐰

F 𝐰 =1

2𝐰T𝐰

Cálculo da margem• A margem de separação ρ é dada pela metade da projeção na direção

de w da diferença entre esses vetores-suporte, conforme ilustrado na Figura;• Assim, a margem ρ é dada por:

Essa margem precisa ser maximizada

• A equação mostra que maximizar a margem de separação entre as classes é equivalente a minimizar a norma euclidiana do vetor de

pesos w, já que 𝜌 =1

𝐖.

• Com visto, para calcular quanto vale a margem de separação serão tomados dois vetores-suporte, sendo um de cada classe;

• É necessário otimizar uma função quadrática sujeita a restrições lineares;• Problemas de otimização quadrática são uma classe bem conhecida de problemas de

programação matemática e existem muito algoritmos (complexos) para resolvê-los;• A solução envolve construir um problema dual em que um multiplicador

Lagrangeano αi é associado a cada restrição do problema primário:

• Este problema de otimização tem uma única solução, não havendo a presença de mínimos locais, como em outros problemas de otimização.

Encontrar w e b tal que:é minimizado;

para todo {(xi,yi)}: yi(wTxi + b) ≥ 1

Encontrar α1…αN tal que:

L(α) = Σαi - (½)ΣΣαiαjyiyjxiTxj é maximizado e sujeito a:

(1) Σαiyi= 0(2) αi ≥ 0 para todo αi

Resolvendo o problema de otimização

F 𝐰 =1

2𝐰T𝐰

• A solução do problema dual leva ao hiperplano ótimo para classes linearmente separáveis;

• Cada αi diferente de zero indica que o xi correspondente é um vetor de suporte;

• É provado matematicamente que αi assume valores positivos para exemplos do treinamento que estão a uma distância do hiperplano ótimo exatamenteigual à margem, sendo nulo (zero) para as demais amostras;

• Os valores de αi são geralmente encontrados usando solvers de otimização, especialmente programação quadrática;

• Para o conjunto de treinamento {(xi,yi)} o vetor de pesos ótimos é:

• O intercepto (bias) b é dado por:

A solução o problema de otimização

SVM - treinamento

Fonte: Ana Carolina Lorena e André C. P. L. F. de Carvalho, 2003OBS: Haykin (2008) sugere a seguinte equação para o bias:

para y=1.

SVM para classificação• Fixados os valores de w e b após o treinamento, o classificador

então é definido pela expressão:

•Note que há um produto interno entre o ponto de teste x e osvetores de suporte xi;

•A partir da equação acima, verifica-se que a classificação de um novo padrão x requer apenas a computação do produto interno;

•Note também que a solução do problema de otimizaçãoenvolvem o cálculo de produtos internos xi

Tx entre todos os pares de treinamento.

•Margem rígida (Hard Margin):

Requer que todos os dados de treinamento sejam classificadoscorretamente;

Não há erro de treinamento;

•E se o conjunto de treinamentofor ruidoso?

Solução 1: usar kernels poderosos:

Problema: possibilidde de overfitting.

Conjunto de dados com ruído

•Variáveis de folga (slack variables) ξi podem seradicionadas para permitir erros de classificação para ruídosou exemplos de difícilclassificação;•Critério de otimização

quadrática:

Minimizar e7

e11

e2

Classificação com Margem Suave

R

k

kεC1

.2

1ww

Margem rígida x Margem suave• Formulação para margem rígida:

• Formulação incorporando variáveis de folga:

• O parâmetro C pode ser visto como uma forma de controlar o overfitting;• O valor de C precisa ser testado dentre algumas possibilidades.

Encontrar w e b tal que

Φ(w) =½ wTw é minimizado para todos {(xi ,yi)}yi (wTxi + b) ≥ 1

Encontrar w e b tal que:

Φ(w) =½ wTw + CΣξi é minimizado para todos {(xi ,yi)}

(1)yi (wTxi + b) ≥ 1- ξi(2) ξi≥ 0 para todo i

SVM com margem suave - treinamento

Fonte: Ana Carolina Lorena e André C. P. L. F. de Carvalho, 2003

SVMs lineares: Resumo• O classificador é um hiperplano de separação;

• Os exemplos de treinamento mais importantes são os vetores de suporte: eles definem o hiperplano;

• Algoritmos de otimização quadrática podem identificar que pontos de treinamento xi são vetores de suporte com multiplicadoresLagrangeanos αi não nulo;

• Tanto na formulação dual do problema quanto na solução, pontos de treinamento aparecem apenas dentro de produtos internos:

Encontrar α1…αN tal queL(α) = Σαi - ½ΣΣαiαjyiyjxi

Txj é maximizado e (1) Σαiyi = 0(2) 0 ≤ αi ≤ C para todo αi

f(x) = ΣαiyixiTx + b

• Principais diferenças das RNAsestão na convexidade do problema de otimização, já que as RNAs, possuem vários mínimos locais na função objetivo otimizada.

•SVM linear funciona bem para dados lineares com algumnível de ruído:

•Mas e se o conjunto de dados for realmente muito difícil?

•Sugestão: mapear para um espaço com mais dimensões:

SVMs não-lineares

0 x

0 x

0 x

x2

SVMs não lineares: espaços de características• Ideia geral: o espaço de entradas original sempre pode ser mapeado

para um espaço de características com mais dimensões, em que o conjunto de treinamento é linearmente separável;• A SVM implementa um mapeamento não-linear (executado por um

produto interno - kernel) dos dados de entrada para um espaço de características (feature space) de alta dimensão;• Um hiperplano ótimo é construído para separar os dados linearmente

em duas classes no espaço de alta dimensão.

Φ: x→ φ(x)

O “Truque do Kernel”• O classificador linear

utiliza produto internoentre vetores K(xi,xj) = xi

Txj;• Se cada ponto é mapeado

em um espaço de altadimensão através de alguma transformaçãoΦ:x → φ(x), o produtointerno fica:

K(xi,xj)= φ(xi)Tφ(xj)

• Uma função de kernel é alguma função que corresponde a um produto interno em algumespaço de característicasexpandido.

Que funções são Kernels?•Para algumas funções K(xi,xj) verificar que K(xi,xj)=φ(xi)

Tφ(xj) pode ser trabalhoso;

•Teorema de Mercer: toda função semi-positiva definidasimétrica é um kernel;

•Funções semi-positivas definidas simétricas correspondem a matriz de Gram semi-positivas definidas simétricas.

K(x1,x1) K(x1,x2) K(x1,x3) … K(x1,xN)

K(x2,x1) K(x2,x2) K(x2,x3) K(x2,xN)

… … … … …

K(xN,x1) K(xN,x2) K(xN,x3) … K(xN,xN)

K =

Exemplos de funções de kernel• Linear:

K(xi,xj)= xiTxj

• Polinomial ou potência p:

K(xi,xj)= (1+ xiTxj)

p

• Gaussiano (radial-basis function network - RBFN):

• Sigmóide:

K(xi,xj)= tanh(β0xiTxj + β1)

)2

exp(),(2

2

ji

ji

xxxx

K

SVMs não-lineares• Formulação do problema dual:

• A solução é:

• As técnicas de otimização para encontrar os αi’s são as mesmas!

Encontrar α1…αN tal queQ(α) =Σαi - ½ΣΣαiαjyiyjK(xi,xj) é maximizado e (1) Σαiyi = 0(2) αi ≥ 0 para todo αi

f(x) = ΣαiyiK(xi,xj) + b

•SVM localiza um hiperplano de separação no espaço de características e classificapontos neste espaço;

•Não é necessário representar o espaço explicitamente, bastadefinir a função de Kernel;

•A função de Kernel faz o papelde produto interno no espaçode características.

SVMs não-lineares - resumo

SVM não lineares - treinamento

Fonte: Ana Carolina Lorena e André C. P. L. F. de Carvalho, 2003

Propriedades de SVM•Solução esparsa mesmo com conjuntos de dados grandes:Apenas os vetores de suporte são usados para especificar

o hiperplano de separação;•Habilidade para lidar com espaços de características

grandes:Complexidade não depende da dimensionalidade do

espaço de características;•Overfitting pode ser controlado pelo uso de margem suave;•Propriedade matemática importante:Um problema de otimização convexo simples cuja

convergência a uma solução global única é garantida;•Extração de características.

•Enquanto para classificação de dados tem-se:

•Para regressão de dados, são necessárias adaptações, produzindo:

Regressão por Vetores Suporte (SVR)

• Cria-se, assim, um compromisso entre a minimização da margem e a minimização do somatório dos erros admissíveis;• O hiperplano ótimo é aquele de mínima margem e que mais se

aproxima da distribuição dos dados;

Regressão por Vetores Suporte (SVR)

• Ou seja, o hiperplano deve estar o mais próximo possível dos dados (deve “passar” pelos dados);• Quando aplicada no

contexto de regressão, SVM é denominada regressão por vetores suporte (SupportVector Regression).

YXwXX TT 0dw

dLoss

2

YbwXLoss

x

f(x)

bwxxf

ei

i01 bwxy ii

•Método dos mínimos quadrados[Ordinary Least Squares (OLS)]•Solução:

Regressão por Vetores Suporte (SVR)

Proposição com similaridade a da SVM!

Support Vector Regression (SVR)

i01 bwxy ii

e

e

ii

T

i

T

i

ybxw

bxwy

x

f(x)

bwxxf +e

-e

0

•Solução – minimizar:

•Restrições:

F 𝐰 =1

2𝐰T𝐰

i01 bwxy ii

N

i

ii

T Cww1

*

2

1

x

f(x)

bwxxf +e

-e

0

*0, *

*

ii

iii

T

ii

T

i

ybxw

bxwy

e

e

Support Vector Regression (SVR)• Inserção da variável de relaxação;•Minimizar:

•Restrições:

Otimização de Lagrange

N

i

ii

T CwwL1

*

2

1

N

i

i

T

iii bxwy1

ea

N

i

i

T

iii bxwy1

** ea

N

i

iii i

1

**

Objetivo

Restrições

Regressão resultante• Regressão:

• Propriedades:

Solução esparsa (Sparseness);

bxxααxyN

i

iii 1

* ,

f(x)

x

+e

-e0

f(x)

(x)

+e

-e0

O número de dimensões de entrada é irrelevante;

Solução global e única;

Possui extensão não-linear.

Fórmulas de regressão

• Linear:

• Não-linear:

• Geral:

bxxααxyN

i

iii 1

* ,

bxxααxyN

i

iii 1

* ,

bxxKααxyN

i

iii 1

* ,