Universidade Federal de Ouro Preto (UFOP)
Programa de Pós-Graduação em Ciência da Computação (PPGCC)
Reconhecimento de Padrões
Classificadores Lineares
David Menotti, Ph.D.
www.decom.ufop.br/menotti
Objetivos
• Introduzir o conceito de classificação
linear.
– LDA
– Funções Discriminantes Lineares
• Perceptron
• SVM
Introdução
• Para utilizar uma função discriminante linear
(Linear Discriminant Function) precisamos ter:
– Dados rotulados (supervisão)
– Conhecer o shape da fronteira
– Estimar os parâmetros desta fronteira a partir dos
dados de treinamento.
• Nesse caso uma reta.
Introdução: Idéia Básica
Ruim
Boa
• Suponha duas classes
• Assuma que elas são linearmente separáveis por uma
fronteira l(θ)
• Otimizar o parâmetro θ para encontrar a melhor
fronteira.
• Como encontrar o parâmetro
– Minimizar o erro no treinamento
– O ideal é utilizar uma base de validação.
Introdução
• Funções discriminantes podem ser mais gerais
do que lineares
• Vamos focar em problemas lineares
– Mais fácil de compreender
– Entender a base da classificação linear
• Diferentemente de métodos paramétricos, não
precisamos conhecer a distribuição dos dados
– Podemos dizer que temos uma abordagem não
paramétrica.
Análise Discriminante Linear
LDA (Linear Discriminant Analysis)
• LDA tenta encontrar uma transformação linear
através da maximização da distância entreclasses e minimização da distância intra-classe.
• O método tenta encontrar a melhor direção de
maneira que quando os dados são projetados
em um plano, as classes possam ser
separadas.
Reta ruim
Reta boa
LDA
LDA
• Diferença entre PCA e LDA quando
aplicados sobre os mesmos dados
LDA
• Para um problema
linearmente
separável, o
problema consiste em
rotacionar os dados
de maneira a
maximizar a distância
entre as classes e
minimizar a distância
intra-classe.
LDA Tutorial
• 1) Para um dado conjunto de dados,
calcule os vetores médios de cada classe
μ1,μ2 (centróides) e o vetor médio geral,μ.
Centroide
Classe +1
Centroide
Classe -1
Centroide
geral
LDA Tutorial
• Calcular as médias de cada classe e a total.
LDA Tutorial
• Calcular o espalhamento de cada classe
Si = SUM{(m-xi)(m-xi)t}
• Calcular o espalhamento entre classes
(within class)
SW = S1 + S2
priors
LDA Tutorial
• Calcular a inversa de SW
– Custo???
• Finalmente, o vetor projeção
w = SW-1 (m1 – m2)
• Reprojetando os vetores sobre w
x 1’ = ( x 1 w ) w t
x 2’ = ( x 2 w ) w t
LDA Tutorial
• Para visualizar a transformação, basta
aplicar a função discriminante a todos os
dados
LDA Tutorial
Taxa de Reconhecimento = 99%
Exercício
• Gere duas distribuições
• Classifique os dados usado LDA
• Verifique o impacto da sobreposição das
distribuições.
Tutorial 1/2
•
•
•
•
•
•
•
•
•
•
x1 = [ 2.95 6.63; 2.53 7.79; 3.57 5.65; 3.16 5.47];
x2 = [2.58 4.46; 2.16 6.22; 3.27 3.52];
m1 = mean(x1);m2 = mean(x2);m = mean([x1;x2]);
S1 = (x1-repmat(m1,size(x1,1),1))'* ...
(x1-repmat(m1,size(x1,1),1));
S2 = (x2-repmat(m2,size(x2,1),1))'* ...
(x2-repmat(m2,size(x2,1),1));
S = S1 + S2;
w=inv(S)*(m1-m2)';
Tutorial 2/2
•
•
•
•
•
•
•
•
•
•
•
•
•
•
figure,hold on
axis([0 8 0 8]);
plot(x1(:,1),x1(:,2),'bx');
plot(m1(1),m1(2),'bd');
plot(x2(:,1),x2(:,2),'rx');
plot(m2(1),m2(2),'rd');
plot(m(1),m(2),'kd');
plot([w(1) 0],[w(2) 0],'g');
w = w/norm(w);
x1l=(x1*w)*w‘; x2l=(x2*w)*w';
plot(x1l(:,1),x1l(:,2),'bo');
plot(x2l(:,1),x2l(:,2),'ro');
Tutorial 2 1/3
•
http://www.eeprogrammer.com/tutorials/Matlab/discriminant_analyses.html
•
a
b
c
d
e
=
=
=
=
=
5*[randn(500,1)+5, randn(500,1)+5];
5*[randn(500,1)+5, randn(500,1)-5];
5*[randn(500,1)-5, randn(500,1)+5];
5*[randn(500,1)-5, randn(500,1)-5];
5*[randn(500,1), randn(500,1)];
Group_X = [a;b;c];
Group_Y = [d;e];
All_data = [Group_X; Group_Y];
All_data_label = [];
for k = 1:length(All_data)
if k<=length(Group_X)
All_data_label = [All_data_label; 'X'];
else
All_data_label = [All_data_label; 'Y'];
end
end
testing_ind = [];
for i = 1:length(All_data)
if rand>0.8
testing_ind = [testing_ind, i];
end
end
training_ind = setxor(1:length(All_data), testing_ind);
Tutorial 2 2/3
•
http://www.eeprogrammer.com/tutorials/Matlab/discriminant_analyses.html
•
[ldaClass,err,P,logp,coeff] = classify(All_data(testing_ind,:),...
All_data((training_ind),:),All_data_label(training_ind,:),'linear');
[ldaResubCM,grpOrder] = confusionmat(All_data_label(testing_ind,:),ldaClass)
K = coeff(1,2).const;
L = coeff(1,2).linear;
f = @(x,y) K + [x y]*L;
h2 = ezplot(f,[min(All_data(:,1)) max(All_data(:,1)) min(All_data(:,2))
max(All_data(:,2))]);
hold on
[ldaClass,err,P,logp,coeff] = classify(All_data(testing_ind,:),...
All_data((training_ind),:),All_data_label(training_ind,:),'diagQuadratic');
[ldaResubCM,grpOrder] = confusionmat(All_data_label(testing_ind,:),ldaClass)
K = coeff(1,2).const;
L = coeff(1,2).linear;
Q = coeff(1,2).quadratic;
f = @(x,y) K + [x y]*L + sum(([x y]*Q) .* [x y], 2);
h2 = ezplot(f,[min(All_data(:,1)) max(All_data(:,1)) min(All_data(:,2))
max(All_data(:,2))]);
hold on
Tutorial 2 3/3
•
http://www.eeprogrammer.com/tutorials/Matlab/discriminant_analyses.html
•
Group_X_testing = [];
Group_Y_testing = [];
for k = 1:length(All_data)
if ~isempty(find(testing_ind==k))
if strcmp(All_data_label(k,:),'X')==1
Group_X_testing = [Group_X_testing,k];
else
Group_Y_testing = [Group_Y_testing,k];
end
end
end
plot(All_data(Group_X_testing,1),All_data(Group_X_testing,2),'g.');
hold on
plot(All_data(Group_Y_testing,1),All_data(Group_Y_testing,2),'r.');
Funções Discriminante Lineares
• Em geral, uma função discriminante linear pode
ser escrita na forma
g ( x)  wT x  w0
• w é conhecido como o vetor dos pesos e w0
representa o bias
Funções Discriminante Lineares
•
é um hiperplano
– Um hiperplano é
• Um ponto em 1D
• Uma reta em 2D
• Um plano em 3D
Funções Discriminante Lineares
• Para duas dimensões, w determina a orientação
do hiperplano enquanto w0 representa o
deslocamento com relação a origem
Perceptron
• Um classificador linear bastante simples, mas
bastante importante no desenvolvimento das
redes neuronais é o Perceptron.
– O perceptron é considerado como sendo a primeira e
mais primitiva estrutura de rede neuronial artificial.
– Concebido por McCulloch and Pits na década de 50.
• Diferentemente do LDA, o perceptron não
transforma os dados para fazer classificação.
– Tenta encontrar a melhor fronteira linear que separa
os dados.
Perceptron
x1
x2
xn
w1

w2
wn
 (.)
w0
y    wi  xi  w0 
y
A função de ativação normalmente
utilizada no perceptron é a
hardlim (threshold)
1 x  0
f ( x)  
0 x  0
A função de ativação é responsável por determinar a forma e a intensidade
de alteração dos valores transmitido de um neurônio a outro.
Perceptron:
Algoritmo de Aprendizagem
1.
2.
3.
4.
5.
Iniciar os pesos e bias com valores pequenos,
geralmente no intervalo [0.3-0.8]
Aplicar um padrão de entrada com seu respectivo
valor desejado de saída (ti) e verificar a saída y da
rede.
Calcular o erro da saída e  t j  a
Se e=0, volta ao passo 2
Se e<>0,
1.
2.
6.
•
Atualizar pesos wi  wi  e  xi
Atualizar o bias b  bold  e
old
Voltar ao passo 2
Critério de parada: Todos os padrões classificados
corretamente.
Perceptron: Exemplo
• Considere o seguinte conjunto de
aprendizagem.
2
X
2
t
0
-2
-2
1
-2
2
0
-1
1
1
Nesse tipo de algoritmo é importante que os dados sejam
apresentados ao algoritmo de treinamento de maneira
intercalada (shuffle)
Perceptron: Exemplo
• Nesse exemplo, vamos inicializar os pesos e bias com
0, ou seja, w =(0,0) e b = 0
Apresentando o primeiro padrão (x1) a rede:

 2 
y  hard lim[0,0]   0   hard lim(0)  1
 2 

Calcula-se o erro
e  ti  y  0 1  1
Como o erro é diferente de 0, atualizam se os pesos e o bias
W  W old  e  xi  [0,0]  (1[2,2])  [2,2]
b  bold  e  0  (1)  1
Apresentando o segundo padrão (x2) a rede:


  2
y  hard lim[2,2]   (1)   hard lim(7)  1
  2


Calcula-se o erro
e  ti  y  1 1  0
Como o erro é 0, os pesos e o bias não precisam ser atualizados.
Apresentando o terceiro padrão (x3) a rede:


  2

y  hard lim[2,2]   (1)   hard lim(1)  0
2


Calcula-se o erro
e  ti  y  0  0  0
Como o erro é 0, os pesos e o bias não precisam ser atualizados.
Apresentando o quarto padrão (x4) a rede:


 1

y  hard lim[2,2]   (1)   hard lim(1)  0
1


Calcula-se o erro
e  ti  y  1  0  1
W  W old  e  xi  [2,2]  (1[1,1])  [3,1]
b  bold  e  1  1  0
Perceptron: Exemplo
• O processo acaba quando todos os
padrões forem classificados corretamente.
• Para esse exemplo, os pesos finais são
w=[-1,-3] e b = 2.
Determinando a fronteira
• No caso bi-dimensional, a fronteira de decisão
pode ser facilmente encontrada usando a
seguinte equação
 W1  x  b
y
W2
Considere o seguinte exemplo, w = [1.41, 1.41], b = 0.354
Escolha duas coordenadas x, para então encontrar os y’s correspondentes
x=[-3,3]
Efeito do bias diferente
de zero.
Para x = -3, y = 2.74
Para x = 3, y = -3.25
SVM
• Proposto em 79 por Vladimir Vapnik
• Um dos mais importantes acontecimentos
na área de reconhecimento de padrões
nos últimos 15 anos.
• Tem sido largamente utilizado com
sucesso para resolver diferentes
problemas.
SVM - Introdução
• Como vimos anteriormente, o perceptron
é capaz de construir uma fronteira se os
dados forem linearmente separáveis.
A
B
Mas qual a fronteira que deve ser escolhida??
SVM - Introdução
• Suponha que a fronteira escolhida é a A.
• Como ela está bem próxima da classe azul, seu
poder de generalização é baixo
– Note que um novo elemento (dados não usados no
treimamento), bem próximo de um azul será
classificado erroneamente.
SVM - Introdução
• Escolhendo a fronteira B, podemos notar que o
poder de generalização é bem melhor.
• Novos dados são corretamente classificados,
pois temos uma fronteira mais distante dos
dados de treinamento.
Maximização da Margem
• O conceito por traz do SVM é a maximização da
margem, ou seja, maximizar a distância da
margem dos dados de treinamento
Distância Pequena
Distância Grande
Hiperplano ótimo: Distância da margem para o exemplo da classe positiva é igual
a distância da margem para o exemplo da classe negativa.
Vetores de Suporte
• São os exemplos da base de treinamento mais
próximos do hiperplano.
– O hiperplano é definido unicamente pelos vetores de
suporte, os quais são encontrados durante o
treinamento.
– Minimização de uma função quadrática
• Alto custo computacional.
SVM: Decisão
f ( x)   i yi K ( x, xi )  b
i
• A função de decisão pode ser descrita
pela fórmula acima, na qual,
– K é a função de kernel,
– α e b são os parâmetros encontrados durante
o treinamento,
– xi e yi são os vetores de características e o
label da classe respectivamente.
Soft Margin
• Mesmo para dados que não podem ser
separados linearmente, o SVM ainda pode ser
apropriado.
• Isso é possível através do uso das “variáveis de
folga” (parâmetro C).
Para um bom desempenho, os dados devem ser “quase” linearmente
separáveis
Soft Margin
• Quanto maior o número de variáveis de
folga (C), mais outliers serão descartados.
• Se C for igual a zero, temos um problema
linearmente separável.
Mapeamento não Linear
• A grande maioria dos problemas reais não são
linearmente separáveis.
• A pergunta então é: “Como resolver problemas
que não são linearmente separáveis com um
classificador linear?”
Projetar os dados em um espaço onde
os dados são linearmente separáveis.
xi
Espaço de
entrada
 ( xi )
Espaço de
características
Mapeamento não Linear
• Projetar os dados em outra dimensão usando
uma função de kernel (kernel trick).
• Encontrar um hiperplano que separe os dados
nesse espaço.
Em qual dimensão esses dados seriam linearmente separáveis?
 ( x)  ( x, x 2 )
1D
2D
Kernel Trick
• A função que projeta o espaço de entrada no
espaço de características é conhecida como
Kernel
• Baseado no teorema de Cover
– Dados no espaço de entrada são transformados
(transf. não linear) para o espaço de características,
onde são linearmente separáveis.
• O vetor  ( xi ) representa a “imagem” induzida no
espaço de características pelo vetor de entrada
Exemplo
Exemplo
Kernel Trick
• Permite construir um hiperplano no
espaço de característica sem ter que
considerar o próprio espaço de
características de forma explícita.
• Toda vez que um produto interno entre
vetores deve ser calculado, utiliza-se o
kernel.
• Uma função de kernel deve satisfazer o
teorema de Mercer para ser válida.
Exemplos de Kernel
Tomada de Decisão
• SVM são classificadores binários, ou seja,
separam duas classes.
• Entretanto, a grande maioria dos
problemas reais possuem mais que duas
classes.
• Como utilizar os SVMs nesses casos?
– Pairwise, um-contra-todos
Pairwise
• Consiste em treinar classificadores
pairwise e arranjá-los em uma árvore
A competição se dá nos níveis inferiores, e o ganhador chegará ao
nó principal da árvore.
Número de classificadores para q classes = q(q-1)/2.
Um-Contra-Todos
• Aqui, o número de classificadores é igual
a q.
• Treina-se um classificador ci para a
primeira classe, usando-se como contra
exemplos as outras classes, e assim por
diante.
• Para se obter a decisão final pode-se
utilizar uma estratégia de votos.
Exercício
• Utilizar a ferramente LibSVM para realizar
classificação usando SVM.