Aprendizado Bayesiano
Disciplina: Sistemas Inteligentes
Aprendizagem Bayesiana
Fornece probabilidades para suas respostas
Permite combinar facilmente conhecimento a priori
com dados de observação
Métodos práticos e bem sucedidos para aprendizagem
 Aprendizagem Bayesiana Ingênua
 Aprendizagem de Redes Bayesianas
Teorema de Bayes
Calcula a probabilidade de diferentes hipóteses a
medida que novas evidências são observadas.


Seja h : hipótese e D: evidência
Objetivo: Calcular P(h/D)
P(h /D) = P(D / h)P(h)
P(D)
P(h): probabilidade a priori de h
P(D): probabilidade a priori de D
P(D/h): probabilidade de observar D dado que h
aconteceu
Exemplo: Classificar Risco
- Seguradora de Veículos
Hipóteses: {risco=alto; risco=baixo}
Probabilidades a priori:


P(risco = alto) = 0.2
P(risco = baixo) = 0.8
Clientes: sexo = masculino, ou sexo = feminino
Pergunta: Qual a probabilidade a posteriori?


Qual a P(risco = alto | sexo = M) ?
Qual a P(risco = alto | sexo = F) ?
Exemplo: Classificar Risco
- Seguradora de Veículos
Evidência ‘sexo = M’:



P(risco = alto) = 0.2
P(sexo = M) = 0.6
P(sexo = M / risco = alto) = 0.7
P(h /D) = P(D / h)P(h)
P(D)
P(risco = alto | sexo = M) =
P(sexo = M / risco = alto) * P(risco = alto)
=
P(sexo = M)
= 0.7 * 0.2 / 0.6 = 0.23
 P(risco = baixo|sexo=M) = 1 – 0.23 = 0.77
Exemplo: Classificar Risco
- Seguradora de Veículos
Evidência ‘sexo = F’:



P(risco = alto) = 0.2
P(sexo = F) = 0.4
P(sexo = F / risco = alto) = 0.3
P(h /D) = P(D / h)P(h)
P(D)
P(risco = alto | sexo = F) =
P(sexo = F / risco = alto) * P(risco = alto)
=
P(sexo = F)
= 0.3 * 0.2 / 0.4 = 0.1
P(risco = baixo|sexo=F) = 1 – 0.1 = 0.9
Escolha das Hipóteses
Geralmente, existe um espaço de hipóteses (H), e desejase a hipótese (hH) mais provável, observados os dados
de treinamento (D)
Hipótese de máxima a posteriori hMAP
h MAP  arg max P( h / D)
hH
P( D / h ) P( h )
 arg max
P( D )
hH
 arg max P( D / h )P( h )
hH
Hipótese de máxima verossimilhança hML (supondo que
P(hi)=P(hj))
h ML  arg max P( D / h i )
hiH
Aprendizagem pelo Método da
Força Bruta
1. Para cada hipótese h  H, calcule a probabilidade a
posteriori
P( D / h )P( h )
P( h / D) 
P( D)
2. Escolha a hipótese hMAP de maior probabilidade à
posteriori
h MAP  arg max P( h / D)
hH
Aprendizagem pelo Método da
Força Bruta
Suponha que D é o conjunto de exemplos
D = {(x1, f(x1)),  (xm, f(xm))}
Cálculo de P(D/h)

P(D/h) = 1, se h é consistente com D (ou seja
f(xi) = h(xi), (x1, f(xi)) D)

P(D/h) = 0, caso contrário
Aprendizagem pelo Método da
Força Bruta
Escolha P(h) sob a hipótese de distribuição uniforme
1
P( h ) 
H
hH
P(D) = |VSH,D|
|H|
onde VSH,D é subconjunto de hipóteses de H
consistentes com D
Aprendizagem pelo Método da
Força Bruta
Cálculo da probabilidade a posteriori:

Se h é inconsistente com D
P(h/D) = P(D/h)P(h)
= 0 * P(h) = 0
P(D)

P(D)
Se h é consistente com D
P(h/D) = P(D/h)P(h)
P(D)
1
= 1 * |H| =
|VSH,D|
|H|
1
|VSH,D|
Exemplo:
Método da Força Bruta
Considere H = {h1, h2, h3, h4}
 h1: risco = alto, h2: risco = baixo
 h3: se sexo = M então risco = alto senão risco = baixo
 h4: se sexo = M então risco = baixo senão risco = alto
Considere exemplo: D1 = {sexo = M, risco = alto}
 Então VSH,D1 = {h1, h3}, P(h1|D1) = P(h3|D1) = 0.5 e
P(h2|D1) = P(h4|D1) = 0
Considere exemplo: D2 = {sexo = F, risco = baixo}
 Então VSH,{D1,D2} = {h3}, P(h3|{D1,D2}) = 1 e P(h1|{D1,D2})
= P(h2|{D1,D2}) = P(h4|{D1,D2}) = 0
Evolução das Probabilidades a
Posteriori
P(h)
P(h|D1)
hipóteses
(a)
P(h|D1,D2)
hipóteses
(b)
hipóteses
(c)
• em (a) todas as hipóteses tem a mesma probabilidade
• em (b) e (c) a medida que novos exemplos são adquiridos, a
probabilidade a posteriori das hipóteses inconsistentes se tornam
nulas, enquanto que a probabilidade a posteriori das hipóteses
que restaram no espaço de versões aumenta
Método da Força Bruta –
Observações
Na prática:
 só funciona quando o conceito verdadeiro está contido no
espaço de hipóteses
 funciona com dados sem ruído
No cálculo da probabilidade P(h/D) pode se levar em
consideração
 erro obtido pela hipótese h no conjunto D
 o tamanho da hipótese
Classificador Bayesiano Ótimo
Dada uma nova instância x, qual é a sua classificação
mais provável?

hMAP(x) nem sempre é a classificação mais provável
Considere três hipóteses:

P(h1/D) = 0.4, P(h2/D) = 0.3 e P(h3/D) = 0.3
Dada uma nova instância x a ser classificada como
alto (+) ou baixo (-):

Suponha: h1(x) = +, h2(x) = - e h3(x) = -
A classificação mais provável de x?
Classificador Bayesiano Ótimo
Se a possível classificação do novo exemplo pode
ser qualquer vj  V, a probabilidade de que a
classificação correta seja vj
P( v j / D) 
 P( v
h iH
j
/ h i )P( h i / D)
Classificação Bayesiana ótima
arg max  P( v j / h i )P( h i / D)
v jV
h iH
Classificador Bayesiano Ótimo
Exemplo



P(h1/D) = 0.4, P(-/h1) = 0, P(+/h1) = 1
P(h2/D) = 0.3, P(-/h2) = 1, P(+/h2) = 0
P(h3/D) = 0.3, P(-/h3) = 1, P(+/h3) = 0
Portanto
 P( / h )P(h
i
/ D)  0.4
 P( / h )P(h
i
/ D)  0.6
h iH
e
h iH
i
i
arg max  P( v j / h i )P( h i / D)  
v jV
h iH
Classificador Bayesiano Ingênuo
Suponha uma função de classificação f: X  V, onde
cada instância x é descrita pelos atributos {a1, , an}
O valor mais provável de f(x) é
v MAP  arg max P( v j / a1 ,, a n )
v jV
 arg max
P( a 1 ,  , a n / v j ) P( v j )
P( a 1 ,  , a n )
 arg max P(a1 ,, a n / v j )P( v j )
v jV
v jV
Classificador Bayesiano Ingênuo
vMAP
 arg max P(a1 , , an / vj )P( vj )
v j V
Calcular P(vj) a partir dos dados de treinamento é fácil, o
problema é calcular a probabilidade P(a1,..., an | vj)
Suposição Bayesiana Ingênua: P(a1 ,, a n / v j ) 
 P( a
i
ou seja, as variáves são a1,..., an independentes
Classificador Bayesiano Ingênuo (NB):
v NB  arg max P( v j ) P(a i / v j )
v jV
i
i
/ vj)
Classificador Bayesiano Ingênuo
Estimativa das Probabilidades P(vj) e P(ai/vj) através
das freqüências relativas P’(vj) e P’(ai/vj)
Para cada vj


P’(vj)  estimativa de P(vj)
Para cada valor ai de cada atributo a
•
P’(ai/vj)  estimativa de P(ai/vj)
Classificador de novas instancias(x)
v NB  arg max P' ( v j ) P' (a i / v j )
v jV
a ix
Classificador Bayesiano Ingênuo:
Exemplo
•
•
•
•
•
•
•
•
•
•
•
Dia
D1
D2
D3
D4
D5
D6
D7
D8
D9
D10
Tempo
Sol
Sol
Coberto
Chuva
Chuva
Chuva
Coberto
Sol
Sol
Chuva
• D11 Sol
Temp.
Quente
Quente
Quente
Normal
Frio
Frio
Frio
Normal
Frio
Normal
Frio
Humid.
Alta
Alta
Alta
Alta
Normal
Normal
Normal
Alta
Normal
Normal
Vento
Fraco
Forte
Fraco
Fraco
Fraco
Forte
Forte
Fraco
Fraco
Fraco
Jogar
Não
Não
Sim
Sim
Não
Não
Sim
Não
Sim
Sim
Alta
Forte
?
P(Sim) = 5/10 = 0.5
P(Não) = 5/10 = 0.5
P(Sol/Sim) = 1/5 = 0.2
P(Sol/Não) = 3/5 = 0.6
P(Frio/Sim) = 2/5 = 0.4
P(Frio/Não) = 2/5 = 0.4
P(Alta/Sim) = 2/5 = 0.4
P(Alta/Não) = 3/5 = 0.6
P(Forte/Sim) = 1/5 = 0.2
P(Forte/Não) = 2/5 = 0.4
P(Sim)P(Sol/Sim) P(Frio/Sim)
P(Alta/Sim) P(Forte/Sim) =
= 0.0032
P(Não)P(Sol/Não)P(Frio/Não)
P(Alta/Não) P(Forte/Não) =
= 0.0288
 Jogar_Tenis (D11) = Não
Algoritmo Bayesiano
Ingênuo: Dificuldades
Suposição de independência condicional quase sempre
violada, mas funciona surpreendentemente bem
P ( a 1 ,  , a n / v j )   P( a i / v j )
i
O que acontece se nenhuma das instancias
classificadas como vj tiver o valor ai?
P' (a i / v j )  0  P' ( v j ) P' (a i / v j )  0
i
Algoritmo Bayesiano
Ingênuo: Dificuldades
Solução típica
P ' (a i / v j ) 
nc  m  p
nm

n é o número de exemplos para os quais v = vj

nc número de exemplos para os quais v = vj e a = ai

p é a estimativa à priori para P’(ai/vj)

m é o peso dado à priori (número de exemplos “virtuais”)
Exemplo: Classificação de
Documentos
Classificar documentos em duas classes vj = {‘interesse’, ‘nãointeresse}
Variáveis a1,..., an são palavras de um vocabulário e P’(ai/vj) é a
freqüência com que a palavra ai aparece entre os documentos da
classe vj
P’(vj) = número de documentos da classe vj
número total de documentos
Exemplo: Classificação de
Documentos
P’(ai/vj) =
nij + 1
nj + |Vocabulário|
onde nj é o número total de palavras nos documentos da classe vj
e nij é o número de ocorrências da palavra ai nos documentos da
classe vj.
Usa-se m = |Vocabulário| e p = 1/ |Vocabulário| (assumindo que
cada palavra tem a mesmo probabilidade de ocorrência)
Exemplo: Classificação de
Documentos
Classificação Final:
v NB  arg max P' ( v j ) P' (a i / v j )
v jV
a ix
Observação: nem sempre a ocorrência de uma palavra independe
das outras palavras. Exemplo: ‘Inteligência’ e ‘Artificial’.
Redes Bayesianas
Uma Rede Bayesiana é um grafo acíclico e dirigido
onde:

Cada nó da rede representa uma variável aleatória

Um conjunto de ligações ou arcos dirigidos conectam pares de
nós
 cada nó recebe arcos dos nós que tem influência direta sobre ele
(nós pais).

Cada nó possui uma tabela de probabilidade condicional
associada que quantifica os efeitos que os pais têm sobre ele
Exemplo
Tempestade
Ônibus de Turismo
Fogo no
Acampamento
Raio
Trovão
Fogo na floresta
T,O T,O T, O T, O
Distribuição de Probabilidade:
P(FA/T,O)
FA 0.4
FA 0.6
0.1
0.9
0.8
0.2
0.2
0.8
Fogo no Acampamento
Aprendizagem de Redes Bayesianas
Variantes da tarefa de aprendizagem


A estrutura da rede pode ser conhecida ou desconhecida
O conjunto de treinamento pode fornecer valores para
todas as variáveis da rede ou para somente algumas
Se a estrutura é conhecida e todas as variáveis
observadas

Então é tão fácil como treinar um classificador Bayesiano
ingênuo
Aprendizagem de Redes Bayesianas
Suponha a estrutura conhecida e variáveis
parcialmente observáveis

Exemplo, observa-se fogo na Floresta, Tempestade,
Ônibus de turismo, mas não Raio, Fogo no Acampamento

Aprende-se a tabela de probabilidades condicionais de
cada nó usando o algoritmo do gradiente ascendente

O sistema converge para a rede h que maximiza
localmente ln (P(D/h))
Exemplo
Tempestade
Ônibus de Turismo
Fogo no
Acampamento
Raio
Trovão
Fogo na floresta
T,O T,O T, O T, O
Distribuição de Probabilidade:
P(FA/T,O)
FA
FA
?
?
?
?
?
?
?
?
Fogo no Acampamento
Gradiente Ascendente para
Redes Bayesianas
Seja wijk uma entrada na tabela de probabilidade
condicional para a variável Yi na rede

wijk = P(Yi = yij/Predecessores(Yi) = lista uik de valores)

Exemplo, se Yi = Fogo no Acampamento, então uik pode ser
{Tempestade = T, Ônibus de Turismo = O}
Aplicar o gradiente ascendente repetidamente

Atualizar todos os wijk usando os dados de treinamento D
w ijk  w ijk   
Ph ( yij , u ik / d )
dD

w ijk
Normalizar os wijk para assegurar
w
j
ijk
1
e
0  w ijk  1
Aprendizagem da Estrutura de
Redes Bayesianas
Métodos baseados em Busca e Pontuação



Busca no espaço de estruturas
Cálculo das tabelas de probabilidade para cada estrutura
Definição da medida de avaliação (Pontuação)
 Ex.: Minimum Descrition Length (MDL)



Operadores de busca (adição, remoção ou reversão de arcos
da rede)
Processo de busca prossegue enquanto a pontuação de uma
rede for significativamente melhor que a anterior
Ex: K2(Cooper e Herskovits, 1992)
Aprendizagem da Estrutura de
Redes Bayesianas
Métodos baseados em análise de dependência



Arcos são adicionados ou removidos dependendo de um
teste de independência condicional entre os nós
Teste de independência pode ser feito entre pares de nós ou
com um conjuntos maior de variáveis condicionais
Ex: CDL(Chen, Bell e Liu 1997)
Aprendizagem da Estrutura de
Redes Bayesianas
Métodos baseados em Busca e Pontuação


Vantagem: Menor complexidade no tempo
Desvantagem: Não garante encontrar melhor solução
Métodos baseados em análise de dependência


Vantagem: Sob certas condições, encontra a melhor solução
Desvantagem: Teste de independência com uma quantidade
muito grande de variáveis pode se tornar inviável
Conclusões
Aprendizado Bayesiano pode ser usado para
determinar as hipóteses mais prováveis dado um
conjunto de exemplos
Fornece algoritmos que podem ser usados na
prática
Classificador Bayesiano Ingênuo
Redes Bayesianas
Bibliografia
Russel, S, & Norvig, P. (1995). Artificial Intelligence:
a Modern Approach (AIMA) Prentice-Hall. Pages
436-458, 588-593
Mitchell, T. & (1997): Machine Learning, McGrawHill. Cap.6
Fayyad et al. (1996): Advances in knowledge
discovery and data mining, AAAI Press/MIT Press.
Cap.11
Pearl, J. (1988) Probabilistic Reasoning in Inteligent
Systems