Universidade Federal de Ouro Preto (UFOP)
Programa de Pós-Graduação em Ciência da Computação (PPGCC)
Reconhecimento de Padrões
Combinando Classificadores
David Menotti, Ph.D.
www.decom.ufop.br/menotti
Introdução
• O uso de vários classificadores é uma estratégia
bastante utilizada para aumentar o desempenho
de sistemas de reconhecimento de padrões.
• A ideia é que os erros sejam minimizados
através do uso de múltiplos classificadores ao
invés de um único classificador.
– Resultados teóricos e experimentais demonstram a
viabilidade do uso de múltiplos classificadores.
• Diferentes arquiteturas
• Diferentes características
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
2
Introdução
• Combinação
– Classificadores “handcrafted” que são
posteriormente combinados para resolver um
dado problema.
• Ensembles
– Classificadores gerados automaticamente por
um algoritmo qualquer
• Bagging, boosting, seleção de características,
subespaços, etc...
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
3
Introdução
• O uso de múltiplos classificadores aparece na
literatura com diferentes nomes
–
–
–
–
–
–
–
Fusão de classificadores
Combinação de classificadores
Mistura de classificadores
Pool
Ensembles
Comitês
Etc...
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
4
Paralelo vs Série
• Múltiplos classificadores podem ser
combinados paralelamente ou em série.
• Paralelo
– Os classificadores C1, ... Cn, produzem
decisões sobre um padrão desconhecido
– Todas essas decisões são então enviadas
para um método de fusão que produzirá o
resultado final.
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
5
Combinação: Paralelo
Estrutura Paralela
C1
C2
Produto
Média
Max
Min
Soma
Classificador
Fusão
Cn
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
6
Combinação: Série
• Uma alternativa para a combinação
paralela é a combinação em série.
– A cada estágio do sistema existe somente um
classificador atuando no sistema.
• A combinação em série pode ser dividida
em duas abordagens
– Redução das classes
– Re-avaliação
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
7
Combinação: Série
• Redução de classes
– A cada estágio do sistema o número de
classes candidatas é reduzida
• Re-avaliação
– Padrões rejeitados em níveis anteriores são
re-avaliados.
– Se o nível de confiança do classificador é
baixo o padrão deverá ser avaliado no nível
seguinte.
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
8
Combinação: Série
Baixo
custo
Redução do custo computacional
A ideia é que a maioria dos padrões
sejam classificados nos primeiros
níveis, onde o custo computacional
é mais baixo.
Alto
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
9
Saída dos Classificadores
• Em geral, as saídas produzidas por
classificadores podem ser divididas em três
níveis
– Abstrato
• O classificador gera apenas o rótulo da classe escolhida.
– Ranking
• O classificador gera uma lista ordenada com as possíveis
classes.
– Probabilidades / scores
• Além da lista ordenada, as probabilidades ou scores também
são geradas.
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
10
Métodos de Fusão
• O método de fusão mais simples de ser
implementado é o voto majoritário
– Bastante utilizado com classificadores abstratos.
– Fácil implementação
• Se o classificador fornecer uma lista ordenada,
outros métodos estão disponíveis
– Borda Count
– Seleção dinâmica de classificadores
• Pesos diferentes.
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
11
Métodos de Fusão (cont)
• O uso de lista de hipóteses ordenadas
(ranking) é interessante quando a classe
correta não aparece como a principal
escolha (Top 1) do classificador.
• Mas está próxima da saída correta
– Top 2 ou 3.
• Bastante interessante para problemas
com grandes léxicos.
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
12
Métodos de Fusão (cont)
• Um método bastante usando nesses
casos é o Borda Count
Classificador 1
Classificador 2
Classificador 3
Resultado
Classe
Rank
Classe
Rank
Classe
Rank
Classe
Rank
1
5
4
5
2
5
2
13
2
4
2
4
4
4
4
11
3
3
5
3
3
3
1
9
4
2
1
2
1
2
3
7
5
1
3
1
5
1
5
5
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
13
Métodos de Fusão (cont)
• Se classificadores geram estimação de
probabilidade a posteriori, podemos
utilizar outros métodos de fusão, tais
como
– Produto
– Soma
– Max
– Min
– Média
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
14
Produto
• É uma regra bastante severa para
combinar classificadores
• Basta que um dos classificadores não
esteja de acordo com a decisão dos
outros que o resultado final será
penalizado.
 P(
k
| xi )
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
15
Soma
• Como o nome diz, a soma consiste em
somar todas as estimações de todos os
classificadores envolvidos.
• Não é drástica como o produto.
• Resultados experimentais [Kittler 98]
mostram que a soma apresenta
resultados bastante robustos.
 P(
k
| xi )
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
16
Min, Max
• Os resultados encontrados pelo Min, são
bastante similares aos resultados
encontrados com o produto.
min(P(k | xi ))
• A regra do max considera somente o
classificador que maximiza a estimação
de probabilidade.
max(P(k | xi ))
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
17
Média
• Resultado médio de todos os classificadores.
– Juntamente com a soma, geralmente produz os
melhores resultados [Kittler 98]
• Bem menos drástica que o produto, porém pode
ser afetada por classificadores que predizem
resultados errados
– Outliers por exemplo.
1
P(k | xi )

R
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
18
Ensembles
• Um conjunto de classificadores gerado
automaticamente
• Melhor desempenho do que um classificador
único
• Baseado na idéia de diversidade
– Quanto mais diversidade estiver presente no
ensemble, melhor será o resultado.
• Métodos clássicos
–
–
–
–
Bagging
Boosting
Seleção de características
Subespaços aleatórios
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
19
Bagging
• Cria classificadores para o ensemble a partir de
uma redistribuição do conjunto de treinamento.
• O conjunto de treinamento de cada classificador
é gerado selecionando-se aleatoriamente os
exemplos da base de aprendizagem com
reposição.
Bases geradas por Bagging
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
20
Bagging
• Como pode-se observar, alguns exemplos não
são selecionados para algumas bases
– Por exemplo, 4 na primeira base
• Isso faz com que provavelmente o classificador
treinando com essa base tenha um erro maior
do que o classificador treinado com a base
original
• Na realidade a maioria dos classificadores
bagging terão erro maior
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
21
Bagging
• Entretanto, na média, Bagging deve
superar o classificador treinado na base
original.
• Bagging é bastante interessante para
algoritmos de aprendizagem instáveis
– Uma pequena mudança na base pode gerar
grandes mudanças nas predições do
algoritmo
• Redes neuronais, árvores de decisão.
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
22
Boosting
• O conjunto de treinamento de cada classificador
é escolhido de acordo com o desempenho do
classificador anterior.
• Os exemplos que são classificados
erroneamente pelos classificadores anteriores
são escolhidos mais frequentemente.
• Em outras palavras, novos classificadores são
produzidos para mitigar o desempenho dos
classificadores anteriores.
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
23
Boosting
Suponha que nesse caso 1, seja um outlier, consequentemente um
exemplo difícil de ser classificado.
Sendo assim, a tendência é que ele apareça com mais frequência na base
de aprendizagem.
A implemetação mais comum de Boosting é o AdaBoost.
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
24
Bias / Variância
• Como vimos até agora, o objetivo da
aprendizagem não é construir uma
representação exata dos dados, mas sim um
modelo com alta capacidade de generalização.
– Modelos com poucos parâmetros (underfitting)
apresentam fraco desempenho
– Modelos com muitos parâmetros (overrfitting)
apresentam fraco desempenho
• Uma maneira de entender melhor o
desempenho dos classificadores é decompor o
erro em bias e variância.
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
25
Bias / Variância
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menottiq
26
Bias / Variância
• Bias
– Mede a distância do resultado do
classificador do seu objetivo
• Variância
– A variância entre os resultados dos
classificadores
(quão frequente eles divergem)
• Bagging / Boosting
– Capacidade de reduzir ambos os erros
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
27
Seleção de Características
• Como visto anteriormente, os métodos de
seleção de características tem como objetivo
encontrar um subconjunto ótimo de
características
• Vários subconjuntos ótimos ou quase ótimos
podem existir.
• Ensemble Feature Selection
– Consiste em utilizar diferentes subconjuntos gerados
durante a seleção de característica para construir um
Ensemble
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
28
Seleção de Características
Considere o conjunto de classificadores gerado pela seleção de
características baseado em algoritmos genéticos multi-objetivos.
100
90
80
weak
Error Rate (%)
70
Classificadores
fracos e médios
não trazem
benefícios
60
50
medium
40
30
20
10
0
strong
10
20
30
40
50
60
Number of Features
70
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
80
90
100
29
Seleção de Características
1st Level Pareto
2nd-Level Population
1
2
n
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
30
Subespaços Aleatórios
• Dado um conjunto inicial de
características, essa técnica consiste em
selecionar N característica aleatórias para
construir um ensemble de tamanho M
Conjunto inicial
1 2 3 4 5 6 7 8
1 3 4 6
2 3 7 8
4 5 6 8
Fusão
3 5 6 7
Média
Decisão
Subespaços
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
31
Subespaços Aleatórios
• Experimentos mostram que os subespaços
conseguem resultados melhores do que um
único classificador treinado com o classificador
inicial
• Quanto maior o tamanho do ensemble, maior é
a complexidade, entretanto.
• A ideia é que a diversidade dos classificadores
pode trazer benefícios para a decisão final.
– Combinação de classificadores fracos
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
32
Referências Bibliográficas
•
•
•
•
•
•
Kittler, Hatef, Duin & Matas
On Combining Classifiers,
IEEE Transactions on Pattern Analysis and Machine Intelligence,
vol 20, n.3, pp.226-240, 1998.
Ho,
The Random Subspace Method for Constructing Decision Forests,
IEEE Transactions on Pattern Analysis and Machine Intelligence,
vol. 20, n.8, pp. 832-844, 1998.
Kittler,
Combining Classifiers: A theoretical framework,
Pattern Analysis & Applications, vol.1, n.1, pp 18-27, 1998.
Bishop,
Pattern Recognition and Machine Learning,
Springer, 2006, Capítulo 14.
Duda, Hart & Sortk
Pattern Classification,
2nd, Wiley & Sons, 2000, Capítulo 9 (9.5, 9.6 & 9.7).
Theodoridis & Koutroumbas,
Pattern Recognition,
4th, Academic Press, 2009, Capítulo 4 (4.21 & 4.22)
Reconhecimento de Padrões
UFOP-PPGCC - Prof. David Menotti
33