Aprendizado Bayesiano
Disciplina: Agentes Adaptativos e
Cognitivos
Conhecimento com Incerteza
Exemplo: sistema de diagnóstico odontológico
Regra de diagnóstico

" p sintoma (p,dor de dente)  doença (p,cárie)

A doença (causa do sintoma) pode ser outra.
Regra causal

" p doença (p,cárie)  sintoma (p,dor de dente)

Há circunstâncias em que a doença não provoca o sintoma.
A conexão entre antecedente e conseqüente não é
uma implicação lógica em nenhuma direção
Conhecimento com Incerteza
Falha no domínio de diagnóstico médico devido a:

“preguiça”:
 existem causas ou conseqüências demais a considerar

ignorância teórica e prática:
 não existe uma teoria completa para o domínio, nem podemos
fazer todos os testes necessários para o diagnóstico perfeito.
Nestes casos, o conhecimento pode apenas prover um
grau de crença nas sentenças relevantes.

P(Cárie/Dor de Dente) = 0.6
Aprendizagem Bayesiana
Fornece probabilidades para suas respostas
Permite combinar facilmente conhecimento a priori
com dados de treinamento
Métodos práticos e bem sucedidos para aprendizagem
 Aprendizagem Bayesiana Ingênua
 Aprendizagem de Redes Bayesianas
Teoria da Probabilidade
Associa às sentenças um grau de crença numérico
entre 0 e 1

Contudo, cada sentença ou é verdadeira ou é falsa
Grau de crença (probabilidade):

a priori (incondicional): calculado antes do agente receber
percepções
 Ex. P(cárie= true) = P(cárie) = 0.5

condicional: calculado de acordo com as evidências
disponíveis (permite a inferência)
 evidências: percepções que o agente recebeu até agora
 Ex: P(cárie|dor de dente)= 0.8
P(cárie|~dor de dente)= 0.3
Probabilidade condicional
Regra do produto:

P(A|B) = P(A^B) , quando P(B) > 0.
P(B)
Regra de Bayes

P(A/B) = P(B/A)P(A)
P(B)
Aplicação da Regra de Bayes:
Diagnóstico Médico
•Seja
M=doença
meningite
S= rigidez no
pescoço
•Um Doutor sabe:
P(S/M)=0.5
P(M)=1/50000
P(S)=1/20
P(M/S)=P(S/M)P(M)
P(S)
=0,5*(1/50000)=0,002
1/20
•A probabilidade de uma
pessoa ter meningite dado
que ela está com rigidez
no pescoço é 0,02% ou
ainda 1 em 5000.
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 ) 
ou seja, as variáves a1,..., an são independentes
Classificador Bayesiano Ingênuo (NB):
v NB  arg max P( v j ) P(a i / v j )
v jV
i
 P( a
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
Representa 3 tipos de conhecimento do domínio:
 Relações de independência entre atributos (ou variáveis)
 Probabilidades a priori de alguns atributos
 Probabilidades condicionais entre atributos dependentes
Permite calcular eficientemente:
 Probabilidades a posteriori de qualquer atributo
(inferência)
Conhecimento representado:
 Na estrutura da rede e nas distribuições de probabilidade
das variáveis
Estrutura das Redes Bayesianas
Uma Rede Bayesiana é um grafo acíclico onde:


Cada nó da rede representa uma variável
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 que quantifica os efeitos que os pais
têm sobre ele
Redes Bayesianas
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
Redes Bayesianas
Representa a distribuição de probabilidade conjunta
entre todas as variáveis: P(y1^...^yn)


Exemplo: P(Tempestade, , Fogo na Floresta)?
Exemplo: P(Classe=C1 ^ Atrib1=10 ^ Atrib2=Yes)?
Cálculo da probabilidade conjunta:
n
P( y1 ,, y n )   P( y i / Pr edecessore s(Yi ))
i 1
Onde Predecessores(Yi) significa predecessores imediatos de
Yi no grafo
Distribuição de Probabilidade
Conjunta
Sejam Y1, Y2,...Yn um conjunto de variáveis.
Evento atômico: uma especificação completa dos
estados do domínio
Y1= y1,Y2 = y2,....,Yn= yn
A distribuição de probabilidade conjunta, P(Y1,Y2,...,Yn),
atribui probabilidades a todos os possíveis eventos
atômicos
Exemplo: Probabilidade Conjunta
dor de dente dor de dente
cárie
0.04
0.06
cárie
0.01
0.89
P(cárie ^ dor de dente)=?
P(cárie)=?
P(dor de dente)=?
P(cárie/dor de dente)=?
Teorema da Multiplicação de
Probabilidades
P(y1^...yn) = P(yn / y1^...yn-1) ... P(y1^...yn-1)

P(y1^...yn) = P(yn / y1^...yn-1) ... P(y2 / y1) P(y1)
Esse resultado permite calcular a probabilidade de ocorrência
simultânea de vários eventos a partir das probabilidades
condicionais.
Independência Condicional
Independência: P(A|B) = P(A)

Exemplo: A = dor de dente e B=úlcera
 Úlcera não causa dor de dente
Independência condicional
 X e Y são independentes dado Z => P(X|Y,Z) = P(X|Z)
 Se o objetivo é saber a probabilidade de X então tanto
faz o valor de Y se você já sabe o valor de Z
 Exemplo: Trovão é condicionalmente independente de
Chuva, dado Relâmpago
 P(Trovão/ Chuva, Relâmpago) = P(Trovão/ Relâmpago)
Redes Bayesianas:
Cálculo da Probabilidade Conjunta
Redes Bayesianas levam em consideração a
Independência Condicional entre subconjuntos
de variáveis
P(y1^...yn) = P(yn / y1^...yn-1) ... P(y2 / y1) P(y1)
P(yn / Predecessores(Yn))
n
P(y2 / Predecessores(Y2)
P( y1 ,, y n )   P( y i / Pr edecessore s(Yi ))
i 1
Exemplo Alarme (AIMA)
P(R)
P(T)
0,001
0,002
Roubo
Terremoto
R T P(A)
Alarme
A
T
T
F
F
T
F
T
F
0,95
0,94
0,29
0,001
P(J)
T 0,90
F 0,05
JohnCalls
A P(M)
MaryCalls
T 0,70
F 0,01
Exemplo Alarme (AIMA)
Calcular a probabilidade do evento que o alarme
toca mas não houve assalto nem terremoto e que
João e Maria telefonaram.
P(J M A ~R ~T)
= P(J|A) P(M|A) P(A|~R ~T )P(~R)P(~T)
= 0.9 x 0.7 x 0.001 x 0.999 x 0.998
= 0.00062 ou 0.062 %
Construção de Redes Bayesianas
1. Escolher um conjunto de variáveis relevantes que
descrevam o domínio
2. Ordem de inclusão dos nós na rede
(a). causas como “raízes” da rede
(b). variáveis que elas influenciam
(c). folhas, que não influenciam diretamente nenhuma outra
variável.
3. Enquanto houver variáveis a representar:
(a). escolher uma variável Xi e adicionar um nó para ela na
rede
(b). estabelecer Pais(Xi) dentre os nós que já estão na rede,
satisfazendo a propriedade de dependência condicional
(c). definir a tabela de probabilidade condicional para Xi
Exemplo Alarme (AIMA)
Ordem: R T A J M
P(R)
0,001
P(T)
Roubo
Terremoto
0,002
R T P(A)
Alarme
A
T
T
F
F
T
F
T
F
0,95
0,94
0,29
0,001
P(J)
T 0,90
F 0,05
JohnCalls
A P(M)
MaryCalls
T 0,70
F 0,01
Exemplo de Rede Bayesiana
Não Puramente Causal
Vamos usar o exemplo do alarme com a seguinte
ordem de inserção dos nós:

MaryCalls, JohnCalls, Alarme, Roubo e Terremoto.
MaryCalls
JohnCalls
Alarme
Roubo
Terremoto
Exemplo de Rede Bayesiana
Não Puramente Causal
Problemas:
 A figura possui duas conexões a mais
 julgamento não natural e difícil das probabilidades
Tendo uma rede puramente causal, teríamos um
número menor de conexões
Exercício: Construa uma rede
para o problema abaixo
Eu quero prever se minha esposa está em casa
antes de eu abrir a porta.
 Eu sei que minha esposa liga a luz quando chega
em casa
 mas às vezes ela também liga ao sair (se ela for
retornar com alguma visita).

Quando não tem ninguém em casa, ela solta o
cachorro no quintal
 mas às vezes ela solta o cachorro quando ele está
molhado.

Quando o cachorro está solto, consigo ouvir o seu
latido da rua
 mas as vezes o confundo com o cachorro da vizinha.
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
Aplicações de Redes Bayesianas
PATHFINDER: diagnóstico de doenças que
atacam os nodos linfáticos. (Russel&Norvig 1995)
PAINULIM: diagnóstico de doenças neuromusculares:
http://snowhite.cis.uoguelph.ca/faculty_info/yxiang/r
esearch.html
Tutores inteligentes:
www.pitt.edu/~vanlehn/andes.html
Aplicações de Redes Bayesianas
Mais aplicações:
http://excalibur.brc.uconn.edu/~baynet/researchApps.htm
Análise de proteínas
Modelagem de Agentes Inteligentes
Detecção de fraudes na indústria
Robótica
Conclusões
Possibilidade de trabalhar com domínios onde não há
informação suficiente
Raciocínio probabilístico trata o grau de incerteza
associado à maioria dos domínios.
Combina conhecimento a priori com dados
observados
O impacto do conhecimento a priori (quando correto)
é a redução da amostra de dados necessários
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