DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
UNIVERSITY OF CALIFORNIA, SAN DIEGO
La Jolla, California 92093-0114
Techinical Report No. CS97-557, September 1997
(First version May 1997)
Boosting and Naive Bayesian Learning
Charles Elkan
APRESENTAÇÃO:
Andréia Santos ([email protected])
Gabrielle Francês ([email protected])
Belém/PA - 03/12/2004
INTRODUÇÃO
- Naive Bayesian:
O Classificador Naive Bayesian considera a
hipótese de que os valores dos atributos de um exemplo
sejam independentes dado a classe de exemplo.
- Boosting:
É um método geral que combina múltiplos
classificadores. Ele melhora o desempenho quando
associado a qualquer método de aprendizagem, neste
caso o Naive Bayesian.
ETAPAS DO PROCESSO
- Naive Bayesian:
TREINAR UMA
SEQUÊNCIA
QUALQUER
CALCULAR
PROBABILIDADES
PRIORI
CALCULAR
PROBABILIDADES
LIKELIHOODS
GANHA A CLASSE
COM MAIOR
PROBABILIDADE
EM UM DADO EXEMPLO
CALCULAR
PROBABILIDADES
CADA CLASSE
EXEMPLOS PRÁTICOS (Naive Bayesian)
- Naive Bayesian (assumindo que os atributos são independentes)
TEOREMA DE BAYES:
P(A|B) = P(B|A) * P(A)
P(B)
P(B)
é desconsiderado
Dado um exemplo para classificar (dataset com 14 exemplos)
Tempo: sol / Temperatura: fria / Umidade: alta / Vento: forte / JOGAR = ?
Cálculo para atributos nominais (discretos):
1. Calcular as probabilidades a priori:
P(jogar = sim) = 9/14
P(jogar = não) = 5/14
2. Calcular as probabilidades likelihoods:
P(jogar = sim|tempo = sol) = 2/9
P(jogar = sim|temperatura = frial) = 3/9
P(jogar = sim|umidade = altal) = 3/9
P(jogar = sim|vento = forte) = 3/9
P(jogar = não|tempo = sol) = 3/5
P(jogar = não|temperatura = fria) = 1/5
P(jogar = não|umidade = alta) = 4/5
P(jogar = não| vento = forte) = 3/5
TEMPO
UMIDADE
SIM
NÃO
Sol
2
3
Nublado
4
0
Chuva
3
2
TEMPERATURA
SIM
NÃO
Alta
3
4
Normal
6
1
VENTO
SIM
NÃO
Quente
2
2
Média
4
2
Fria
3
1
SIM
NÃO
Fraco
6
2
Forte
3
3
EXEMPLOS PRÁTICOS (continuação)
3. Calcular a probabilidade de cada classe ocorrer:
P(jogar = sim | tempo = sol, temperatura = fria, umidade = alta, vento = forte)
= P(jogar = sim|tempo = sol) * P(jogar = sim|temperatura = fria) *
P(jogar = sim|umidade = alta) * P(jogar = sim|vento = forte) * P(jogar = sim)
= 2/9 * 3/9 * 3/9 * 3/9 * 9/14
0,0053
P(jogar = não | tempo = sol, temperatura = fria, umidade = alta, vento = forte)
= P(jogar = não|tempo = sol) * P(jogar = não|temperatura = fria) *
P(jogar = não|umidade = alta) * P(jogar = não|vento = forte) * P(jogar = não)
= 3/5 * 1/5 * 4/5 * 3/5 * 5/14
0,0206
 A classe escolhida será (JOGAR = NÃO), pois obteve uma
probabilidade maior em comparação a classe jogar = sim.
EXEMPLOS PRÁTICOS (continuação)
Cálculo para atributos contínuos (densidade de probabilidade normal):
Dado um exemplo para classificar (dataset com 14 exemplos)
Tempo: sol / Temperatura: 66 / Vento: forte / JOGAR = ?
1. Calcular as probabilidades a priori da mesma forma do nominal:
P(jogar = sim) = 9/14
P(jogar = não) = 5/14
2. Calcular as probabilidades likelihoods (média e desvio padrão)
n
n
1
m =  x k m = 74
n k =1
1
f ( x) =
e
2ps
s 2 1  ( xk - m ) 2
n
( x- m ) 2
2s 2
k =1
s 2 = 40.24
s @6
f ( x = 66) = 0,0273
TEMPERATURA
85
80
83
70
68
65
64
62
69
75
75
72
81
71
EXEMPLOS PRÁTICOS (continuação)
3. Calcular a probabilidade de cada classe ocorrer:
P(jogar = sim | tempo = sol, temperatura = 66, vento = forte)
= P(jogar = sim|tempo = sol) * P(jogar = sim|temperatura = 66) *
* P(jogar = sim|vento = forte) * P(jogar = sim)
= 2/9 * 0,0273 * 3/9 * 9/14
0,0013
P(jogar = não | tempo = sol, temperatura = 66, vento = forte)
= P(jogar = não|tempo = sol) * P(jogar = não|temperatura = 66) *
* P(jogar = não|vento = forte) * P(jogar = não)
= 3/5 * 0,0273 * 3/5 * 5/14
0,00351
 A classe escolhida será (JOGAR = NÃO), pois obteve uma
probabilidade maior em comparação a classe jogar = sim.
ETAPAS DO PROCESSO
- Boosting e Naive Bayesian (K=2):
CALCULAR
PROBABILIDADES
PRIORI
1ª
iteração
ATRIBUIR
PESOS
UNIFORMES
2ª
iteração
TREINAR UMA
SEQUÊNCIA
QUALQUER
CALCULAR
PROBABILIDADES
LIKELIHOOD
CALCULAR
PROBABILIDADES
CADA CLASSE
SAÍDA
NAIVE BAYESIAN
NORMALIZAR
NOVOS PESOS
CALCULAR
NOVOS PESOS
CALCULAR
TAXA DE ERRO
TOTAL EXEMPLOS
ATUALIZAR
NOVOS PESOS
SAÍDA DO CLASSIFICADOR
Boosting e Naive Bayesian
EXEMPLOS PRÁTICOS (Boosting)
- Boosting (Robert E. Schapire and Yoram Singer [1999])
Dado um exemplo para classificar (dataset com 5 exemplos)
::: 1ª Iteração :::
1. Atribuindo pesos uniformes para cada exemplo:
valor uniforme = 0,2
2. Aplicando o algoritmo Naive Bayesian
2.1. Calculando as probabilidades a priori:
P(class = +) = 3/5
P(class = -) = 2/5
treino
2.2. Calculando as probabilidades likelihoods:
P(a1 = T | class = +) = 2/3
P(a2 = F | class = +)
P(a1 = T | class = -) = 1/3
P(a2 = F | class = -)
P(a1 = F | class = +) = 1/2
P(a2 = T | class = +)
P(a1 = F | class = -) = 1/2
P(a2 = T | class = -)
a1
a2
Class
T
T
+
T
T
+
T
F
-
F
F
+
F
T
-
= 1/2
= 1/2
= 2/3
= 1/3
2.3. Calculando as probabilidades para cada classe ocorrer:
P(class = + | a1 = T, a2 = T)
P(class = - | a1 = T, a2 = T)
= P(a1 = T | class = +) * P(a2 = T | class = +)
= P(a1 = T | class = -) * P(a2 = T | class = -)
* P(class = +) = 2/3 * 2/3 * 3/5
* P(class = -) = 1/2 * 1/2 * 2/5
0,26
0,1
EXEMPLOS PRÁTICOS (continuação)
3. Calculando a saída do 1º classificador Naive Bayesian:
hi ( x ) =  p( + ) -  p( - )
treino
a1
a2
Class
h1 ( x) = 0.522- 0.4  0,122
T
T
+
T
T
+
4. Calculando o erro total dos exemplos:
T
F
-
F
F
+
F
T
-
wE
 = w  = 0 .2 + 0 . 2 
T
1
b=

1- 
0,4


b = 0.4 = 0.4  0,66
1- 0.4 0.6
OBS: Considerando a classe + = 1 e a classe - = 0.
5. Calculando os novos pesos:
a) classificado corretamente
wi + 1 = wi  b
b) classificado incorretamente
1- hi ( xi ) - yi
w2 = 0.2  (0.66)1- 1-1 
wi + 1 = wi  b
0,132
1- hi ( xi ) - yi
w2 = 0.2  (0.66)1- 0-1  0,2
EXEMPLOS PRÁTICOS (continuação)
6. Fator de normalização dos novos pesos:
0,132 + 0,132 + 0,2 + 0,2 + 0,132 = 0,796
7. Atualizando o peso dos exemplos:
a) classificado corretamente:
0,132 / 0,796 = 0,165
b) classificado incorretamente:
0,2 / 0,796 = 0,251
treino
w1
w2
a1
a2
Class
T
T
+
0,2 0,132 0,165
T
T
+
0,2 0,132 0,165
T
F
-
0,2
0,2
0,251
F
F
+
0,2
0,2
0,251
F
T
-
0,2 0,132 0,165
::: 2ª Iteração :::
1. Aplicando o algoritmo Naive Bayesian
1.1. Calculando as probabilidades a priori:
P(class = +) = (0,165 + 0,165 + 0,251) / 1  0,581
P(class = -) = (0,251 + 0,165) / 1  0,416
1.2. Calculando as probabilidades likelihoods:
P(a1 = T | class = +) = 0,567
P(a2 = F | class = +)
P(a1 = T | class = -) = 0,603
P(a2 = F | class = -)
P(a1 = F | class = +) = 0,432
P(a2 = T | class = +)
P(a1 = F | class = -) = 0,396
P(a2 = T | class = -)
= 0,432
= 0,603
= 0,567
= 0,396
PN
EXEMPLOS PRÁTICOS (Boosting)
1.3. Calculando as probabilidades para cada classe ocorrer:
P(class = + | a1 = T, a2 = T)
P(class = - | a1 = T, a2 = T)
= P(a1 = T | class = +) * P(a2 = T | class = +)
= P(a1 = T | class = -) * P(a2 = T | class = -)
* P(class = +) = 0,567 * 0,567 * 0,581
* P(class = -) = 0,603 * 0,396 * 0,416
0,186
2. Calculando a saída do 2º classificador Naive Bayesian:
hi ( x ) =  p( + ) -  p( - )
h1 ( x) = 0.578- 0.4140,164
3. Calculando o erro total dos exemplos:
wE
 =w
T
b=

1- 
0.165
=
 0,165
1
0,165
b=
 0,197
1 - 0,165
0,099
EXEMPLOS PRÁTICOS (Boosting)
4. Calculando os novos pesos:
wi + 1 = wi  b
1- hi ( xi ) - yi
4.1. Para os exemplos 1 e 2:
1- 1-0

0,032
1- 1-1

0,049
1- 0-1

0,165
w3 = 0,165 (0,197)
4.2. Para os exemplos 3 e 4:
w3 = 0,251 (0,197)
4.3. Para o exemplo 5:
w3 = 0,165 (0,197)
5. Fator de normalização dos novos pesos:
0,032 + 0,032 + 0,049 + 0,049 + 0,165 = 0,327
EXEMPLOS PRÁTICOS (Boosting)
6. Atualizando o peso dos exemplos:
7. Calculando a saída do
classificador Boosting:
H ( x) = ln(
1
b1
)  h1 + ln(
1
b2
)  h2
w3
PN
0,2 0,165
0,032
0,097
+
0,2 0,165
0,032
0,097
F
-
0,2 0,251
0,049
0,149
F
F
+
0,2 0,251
0,049
0,149
F
T
-
0,2 0,165
0,165
0,504
a1
a2
class
T
T
+
T
T
T
w1
w2
T
1
1
1 T
1
H ( x) =  \ se (ln )  hi ( x)   (ln )
bi
bi
2 i =1
0
i =1
= ln(
1
1
)  0,122+ ln(
)  0,164  0,316
0,66
0,197
1
1
1 
=  ln(
) + ln(
)   1,019
2  0,66
0,197 
VANTAGENS DOS CLASSIFICADORES
- Naive Bayesian:
 É notavelmente bem sucedido e nenhum método
melhor de aprendizado uniforme é conhecido;
 Com ou sem Boosting, é altamente aceitável
computacionalmente como modelo de aprendizado
humano;
- Boosting:
 Em cima de qualquer outro método tentado por Ripley
[1996], o Boosting mostra-se apto para treinar
exemplos com valores de atributos preditos;
VANTAGENS DA COMBINAÇÃO
 O desempenho de generalização é tão bom quanto, ou melhor,
que o melhor resultado publicado usando qualquer outro método
de aprendizado;
 Nenhum algoritmo de aprendizado que examina todos seus dados
de treino pode ser mais rápido, tempo linear - O(ef);
(treinando classificador)
40.000
(25 dim)
1 minuto
 São bem compatíveis para a descoberta de conhecimento em bases
de dados muito grandes;
 Leva vantagem no fato de igualar os valores dos atributos de
alguns deles que são desconhecidos para um exemplo de treino;
PROJETO
- Objetivos:
 Possibilidade de melhorar a confiança da capacidade
de generalização do Classificador Naive Bayesian;
 Discutir o Naive Bayesian com o sem Boosting que
computacionalmente é um modelo aceitável de
aprendizado humano;
 Mostrar como o aprendizado de Naive Bayesian, com
ou sem Boosting, é o melhor modelo de aprendizagem
humana.
 Esta discursão mostrará que o Naive reproduz melhor
todos os fenômenos de aprendizado da categoria
humana.
EXPERIMENTOS REALIZADOS
- Dados Utilizados (datasets):
1. “German Credit” - 1000 exemplos,
rounds
error (%)
sendo que 700 exemplos são da classe
“good” e 300 da classe “bad”. 17
características são discretas, enquanto 3
são contínuas. http://www.ryerson.ca/~dgrimsha/
1
25.1
2
24.3
3
24.0
4
24.4
courses/cps820/Resources/credit-g_arf.txt
5
24.7
6
24.9
7
25.2
8
25.1
9
25.3
10
25.4
Resultados Obtidos:
- Naive Bayesian - 25.3% taxa de erro (com 5
partes/cross-validation);
- Boosting e Naive Bayesian – melhorou a taxa de erro
para 24.0% (combinando 3 classificadoores Naive
Bayesian completamente);
...
100
- Boosting e C4.5 – aumentou a taxa de erro de 28.44% para 29.14%.
25.7
SIMULAÇÃO NO WEKA
- Classificador Naive Bayesian (usando validação cruzada com 5 folhas)
24.9%
SIMULAÇÃO NO WEKA
- Classificador C4.5 (Weka – J48)
26.7%
SIMULAÇÃO NO WEKA
- Classificador C4.5 (Weka – J48) combinado com Boosting
27.7%
SIMULAÇÃO NO WEKA
- Classificador Naive Bayesian (3 classificadores) combinado com Boosting
22.8%
EXPERIMENTOS REALIZADOS (continuação)
2. “Diabets in Pima Indians” – Usando 200 exemplos de treinos
completos, o melhor método de aprendizado reportado por Ripley
[1996] é a discriminação linear padrão. Este dataset consiste de 8
atributos numéricos: http://laps.ufpa.br/aldebaro/classes/asr2sem03/datasets/weka-arff
1.
2.
3.
4.
5.
6.
7.
8.
Número de gravidez (quantidade)
Concentração de glicose em um teste de tolerância
Pressão do sangue (mm Hg)
Soro insulina (micro U/ml)
Massa corporal inicial (Kg/m2)
Função genealógica de diabestes
Espessura da dobra da pele/do trícepes da pele (mm)
Idade em anos
Resultados Obtidos:
-
Discriminação Linear Padrão - 20.3% de taxa
de erro;
-
Boosting e Naive Bayesian - 22.0% de taxa de
erro (com 10 voltas);
-
Backpropagation - 22.6% de erro (com
unidade escondida).
uma
Usando 200
rounds exemplos completos
erro (%)
1
24.7
2
23.8
3
22.9
4
22.6
5
22.9
6
22.9
7
22.9
8
22.9
9
22.6
10
22.0
EXPERIMENTOS REALIZADOS (continuação)
* Usando o mesmo dataset, agora adicionando 100
exemplos de treinos com dados desconhecidos
(incompletos):
Usando 200
rounds exemplos completos
erro (%)
Resultados Obtidos:
-
C4.5 - 22.3% de erro;
Boosting com Naive
Bayesian - 18.7% de
erro (com 10 voltas)
Incluindo 100
exemplos incompletos
erro (%)
1
24.7
20.2
2
23.8
20.5
3
22.9
19.9
4
22.6
19.6
5
22.9
19.6
6
22.9
19.3
7
22.9
19.0
8
22.9
19.0
9
22.6
19.0
10
22.0
18.7
COMPARAÇÕES IMPORTANTES
 Naive
Bayesian,
resulta
numa
combinação
matematicamente equivalente a uma rede neural
feedforward com entradas, uma única camada
intermediária de nós e função de ativação sigmóide;
Esquema sistemático de um neurônio
 Naive Bayesian, dá ao teste melhor exatidão do que os
outros métodos conhecidos, incluindo backpropagation
e árvore de decisão C4.5.
CONCLUSÕES FINAIS
Segundo o autor, o método apresentado aqui
neste trabalho (Boosting and Naive Bayesian Learning),
mostrou ser o melhor método de aprendizado uniforme
conhecido.
Vimos que estes métodos são
aceitáveis (possíveis) computacionalmente.
altamente
No conjunto de dados do mundo real, nos quais o
método foi testado, o desempenho de generalização é
realmente excelente em comparação a qualquer outro
método de aprendizado.
MENSAGEM FINAL
Não diga que a vitória está perdida,
Se é de batalhas que se vive a vida,
Tenha fé em Deus, tenha fé na vida,
Tente outra vez... TENTE!
(Raul Seixas)
Dúvidas ou sugestões envie-nos um e-mail:
Andréia Santos  [email protected]
Gabrielle Francês  [email protected]
REFERÊNCIAS BIBLIOGRÁFICAS
1. ELKAN, Charles. Boosting and Naive Bayesian
Learning. San Diego, 1997.
2. LANGLEY, Pat; SAGE, Stephanie. Induction of
Selection Bayesian Classifiers. Palo Alto, 1994.