Redes Bayesianas
Paulo Adeodato
George Cavalcanti
CIn-UFPE
Roteiro
Probabilidade (Teorema de Bayes).
 O que são Redes Bayesianas?
 Construindo uma Rede Bayesiana.
 Inferência em Redes Bayesianas.
 Aprendizagem em Redes Bayseanas.
 Redes Bayesianas x Redes Neurais

Probabilidade Condicional:
Definição e Propriedades
 P( A  B)
se P( A)  0

P( B | A)   P( A)
 P( B)
se P( A)  0.
1- P(B|A), para A fixo, satisfaz os axiomas de Kolmogorov
2- Se A = , então P(B|A) = P(B)
3- A probabilidade condicional define-se em função da
probabilidade não condicional, logo o cálculo da primeira
decorre do conhecimento da segunda
4- P( A  B)  P( B | A) P( A)  P( A | B) P( B)
Teorema da Multiplicação de Probabilidades
P A1  A2    An   P A1 P A2 | A1 
P An | A1 ,, An1



Esse resultado permite calcular a probabilidade de
ocorrência simultânea de vários eventos a partir
das probabilidades condicionais.
Probabilidade de um Evento
os eventos B1,...,Bk formando uma
partição de , isto é,
 Considere
Bi  B j  , i  j
k
 Bi  
i 1
P ( Bi )  0, i
* Intuitivamente, qualquer que seja o resultado de um
experimento, um e somente um desses eventos Bi
acontecerá.Graficamente,
B1
B3
B6
A
B2
B4
B5

6
Sempre vale a decomposição
A   A  Bi
i 1
mas os eventos A  Bi são mutuamente excludentes.
Assim, podemos calcular a probabilidade de A de
forma aditiva P( A) 
P A  B 

1i 6
i
onde cada uma dessas interseções é dada por:
P( A  Bi )  P( A | Bi ) P( Bi )
E dessa maneira temos o seguinte
Teorema da Probabilidade Total
P A 
 P A | B PB 
1i  k
A
i
i
utilidade desse resultado reside em que,
muitas vezes, é difícil calcular a probabilidade
do evento A em forma direta, mas pode-se
conhecer a probabilidade dele acontecer dado
que ocorreram outros eventos Bi que formam
uma partição do espaço amostral.
Teorema de Bayes

Permite calcular a probabilidade da “causa” Bi ter
acontecido, dado que a “conseqüência A tenha sido
observada.
P( A | Bi ) P( Bi )
P( Bi | A) 
 P( A | B j ) P( B j )
j
Exemplo

Um sistema automático de apoio à decisão médica
é utilizado para auxílio na diagnose do tipo de
hepatite dos pacientes num ambulatório. Erros são
inerentes ao processo decisório e o desempenho
desse sistema, medido pela sua matriz de confusão
abaixo, indica qual a probabilidade de um tipo de
hepatite ser reconhecido como qualquer deles.
Considerando que as incidências dos casos de
hepatite na região são de 10% do tipo A, 60% do
tipo B e 30% do tipo C, qual a probabilidade de um
paciente que teve diagnosticada hepatite B pelo
sistema tenha, na realidade, esse tipo de hepatite
?
Exemplo (Continuação)
Cada elemento da matriz de confusão representa a
probabilidade condicionada P(tipo diagnosticado | tipo
real) de hepatite.
DIAGNOSTICADA
R
E A
AB
L C
A
0,85
0,10
0,20
B
0,10
0,70
0,15
C
0,05
0,20
0,65
Exercício
 Em
teste de múltipla escolha, a
probabilidade de o aluno saber a resposta é
p. Havendo m escolhas, se ele sabe a
resposta responde corretamente com
probabilidade 1; se ele não sabe a resposta,
responde corretamente com probabilidade
1/m. Qual é a probabilidade de que ele
sabia a resposta dado que a pergunta foi
respondida corretamente ?
Variaveis Aleatorias Bidimensionais
 Há
3 tipos de VAs bidimensionais
caracterizados pelos tipos das VAs que
compõem o vetor aleatório:
• Discreta-discreta
(X,Y)  (estado civil, no de dependentes)
• Discreta-contínua
(X,Y)  (renda, estado civil)
• Contínua -contínua
(X,Y)  (renda, tempo de emprego)
VAs Bidimensionais Discretas
 Uma
variável aleatória bidimensional é
discreta se o seu contradomínio XY for
discreto:
XY = X x Y (produto cartesiano)
 A sua distribuição é dada por:
[(xi , y j ), p( xi , y j )],
onde:
 p(xi,yj)
xi   X , y j  Y
p( xi , y j )  P( X  xi , Y  y j )
representa a Probabilidade
Conjunta:
VAs Bidimensionais Discretas

Assim:
p( xi , y j )  0
e

 XY
p( xi , y j )  1
(cont.)
Exemplo

Duas fábricas (F1 e F2) fornecem um tipo de peça a
3 empresas distintas (E1, E2 e E3), `a excecao da
fábrica F2 que não fornece `a empresa F2. Suponha
que o lançamento de pedidos é equiprovável de cada
empresa para cada fábrica. Que modelo descreve a
VA bidimensional dos pares (fábrica, empresa)?
EMPRESA
F
A
B.
F1
F2
E1
1/5
1/5
E2
1/5
0
E3
1/5
1/5
Distribuições Marginais

Dada p(xi,yj), é possível obter, tanto a distribuição
de X quanto a distribuição de Y:
P( X  xi ) 

e
 P( X  x , Y  y )
y j Y

j
 p( x , y )
y j Y
P(Y  y j ) 
i
i
j
 P( X  x , Y  y )
i
xi  X
 p( x , y )
xi  X
i
j
j
Distribuições Marginais (cont.)
P(X=xi) e P(Y=yj) são chamadas probabilidades
marginais ou distribuições marginais porque
costumam ser colocadas nas margens das tabelas
de distribuicoes discretas bidimensionais.
 Quais são as probabilidades marginais do exemplo
anterior?

EMPRESA
F
A
B.
F1
F2
E1
1/5
1/5
E2
1/5
0
E3
1/5
1/5
2/5
1/5
2/5
3/5
2/5
Independência
 Seja
(X,Y) uma variável aleatória
bidimensional discreta. A variáveis
aleatórias X e Y são ditas independentes se
p(xi,yj) = p(xi) p(yj)
para todo (xi,yj) pertencente a X x Y
Distribuição de Probabilidade Conjunta

O que é?
• É uma tabela n-dimensional na qual os valores das células dão a
probabilidade de um dado evento ocorrer.

Poder expressivo
• Ela pode responder qualquer questão sobre o domínio.

Problema:
• complexidade de cálculo matemático e tamanho que cresce
exponencialmente com a dimensão do espaço
Toothache
Cavity
Cavity
0.04
0.01
Toothache
0.06
0.89
Exemplo de uma distribuição de probabilidade conjunta
Redes Bayesianas: representação do
conhecimento para raciocínio com incerteza

Representa 3 tipos de conhecimento do domínio:
• relações de independência entre variáveis aleatórias
(graficamente);
• probabilidades a priori de algumas variáveis;
• probabilidades condicionais entre variáveis dependentes.

Permite calcular eficientemente:
• probabilidades a posteriori de qualquer variável
aleatória(inferência); usando para isso uma definição recursiva
do teorema de Bayes.

Conhecimento representado:
• pode ser aprendido a partir de exemplos reutilizando parte dos
mecanismos de raciocínio
Estrutura de uma rede bayesiana
Cada variável aleatória (VA) é representada por um nó da
rede
 Cada nó (VA) recebe conexões dos nós que têm influência
direta (seus pais) sobre ele. (Tarefa fácil para o
especialista)
 Cada nó possui uma tabela de Probabilidades Condicionais
que quantifica a influência dos seus pais sobre ele.
(Difícil para o especialista)
 O grafo é acíclico (veremos a razao matematica para tal)

Construção (manual) de uma rede bayesiana
Escolher variáveis relevantes que descrevam o domínio;
 Escolher uma ordem para as variáveis;
 Enquanto tiver variáveis sobrando:

• pegar uma variável e adicionar um nó na rede para ela;
• criar links dos nós anteriormente inseridos que satisfaçam a
independência condicional;
• definir a tabela de probabilidade condicional para a variável.
Exemplo simples de rede bayesiana (cont.)
P(R)
P(T)
0,001
0,002
Roubo
Terremoto
Alarme
A
P(J)
T
F
0,90
0,05
JohnCalls
R
T
P(A)
T
T
F
F
T 0,95
F 0,94
T 0,29
F 0,001
MaryCalls
A
P(M)
T
F
0,70
0,01
Decomposição da Probabilidade Conjunta
Px1, x2 ,, xn   Px1  Px2 | x1  Px3 | x1, x2 
X1
Pxn | x1, x2 ,, xn1 
Xn
X2
X3
Decomposição da Probabilidade Conjunta



Essa decomposicao deixa clara a necessidade de a rede
bayesiana ser um grafo aciclico
A cada fator acrescentado na decomposicao
acrescentamos 2j-1 condicoes da tabela de probabilidades
condicionadas da j-esima VA ao total de condicoes
Assim, teremos um total (2j-1) de 25-1 condicoes nas
tabelas das probabilidades condicionadas das Vas. Esse
representa o pior caso possivel para uma rede bayesiana.
Aprendizagem em redes bayesianas

4 Situacoes possiveis:
• Estrutura conhecida, completamente observável

as tabelas de probabilidade condicionada podem ser estimadas
usando o conjunto de exemplos com classificador ingênuo? de Bayes
• Estrutura desconhecida, completamente observável

o problema é construir a topologia da rede. Busca no espaço de
estruturas.
• Estrutura conhecida, variáveis escondidas

caso parecido com aprendizado em redes neurais
• Estrutura desconhecida, variáveis escondidas

não se conhece algoritmos para este tipo de problema
Tipos de conhecimento

Causal
• Refletem a direção conhecida de causalidade no mundo: para
algumas propriedades do mundo percepções são geradas.
• ex, P(DorDeDente|Cárie), P(MaryCalls|Alarme)

Diagnóstico
• Infere a presença de propriedades escondidas diretamente da
percepção.
• Produzem conclusões fracas.
• ex, P(Cárie|DorDeDente), P(Alarme|MaryCalls)
Ordenar nós de uma rede bayesiana



Algoritmo de construção apresentado especifica a ordem
Raízes sempre causais, folhas sem influência causal sobre
nenhuma outra variável
Caracteristicas:
• compactacao da rede
• menor complexidade computacional (pior caso volta a distribuição
de probabilidade conjunta)
• menores tempo de resposta e necessidade de memoria
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 (cont.)

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
Podemos piorar ainda mais a nossa configuração da rede,
seguindo a seguinte ordem de criação:
• MaryCalls, JohnCalls, Terremoto, Roubo e Alarme.
• Resulta num total de 25-1 condicoes nas tabelas das
probabilidades condicionadas das VAs (pior caso =
probabilidade conjunta original)
Exemplo de rede bayesiana
não puramente causal (cont.)
MaryCalls
JohnCalls
Terremoto
Roubo
Alarme
Preencher tabelas de probabilidades
condicionais com conhecimento do domínio
Problema: preencher as tabelas de probabilidade
condicionada.
 Distribuições canônicas (ex, normal, binomial)

• Relações entre nós (pais e filhos) se ajustam a algum padrão.
Nesses casos, toda a tabela pode ser especificada determinando
o padrão e talvez suprimindo alguns parâmetros. (conseguido
apenas para a Normal com intervalos discretizados)

Relações determinísticas
• Os nós possuem seus valores especificados pelos valores dos seus
pais, sem incerteza.

Lógica ruidosa (noisy-OR)
• A probabilidade de o nó de saída ser falso é o produto do
parâmetro ruidoso de todos os nós de entrada que são
verdadeiros.
Preencher tabelas de probabilidades
condicionais com conhecimento do domínio
Cold
Flu
Malaria P(Fever)
P(Fever)
F
F
F
F
T
T
F
F
T
T
F
F
F
T
F
T
F
T
0,0
0,9
0,8
0,98
0,4
0,94
1,0
0,1
0,2
0,02
0,6
0,06
T
T
T
T
F
T
0,88
0,988
0,12
0,012
Versatilidade das redes bayesianas

Redes Bayesianas oferecem 4 tipos de inferência:
• Causal (da causa para o efeito)

P(JohnCalls/Roubo) = 0,86
Roubo
Alarme
JohnCalls
Evidência
Query
• Diagnóstico (do efeito para a causa)

P(Roubo/JohnCalls) = 0,016
JohnCalls
Query
Alarme
Roubo
Evidência
Versatilidade das redes bayesianas
• Intercausal (entre causas com um efeito comum)


P(Roubo/Alarme) = 0,376
P(Roubo/Alarme Terremoto) = 0,373
Roubo
Alarme
Terremoto
Query
Evidência
• Mista (combinando duas ou mais das de cima)


P(Alarme/JohnCalls Terremoto) = 0,03
Este é um uso simultâneo de inferência causal e diagnóstico.
JohnCalls
Evidência
Alarme
Query
Terremoto
Evidência
Exemplo da tarefa de aprendizagem
P(R)
0,001
Roubo
Terremoto
Alarme
A
T
F
P(J)
?
?
JohnCalls
R
T
T
F
T
P(T)
0,002
T P(A)
T
?
F
?
T
?
T
?
MaryCalls
A P(M)
T
?
F
?
Outros Usos

Além de calcular consultas a partir de variáveis como
evidência uma rede bayesiana também pode ser usada
para realizar as seguintes tarefas:
• tomada de decisão
• decidir qual variável adicional deve ser observada
• Análise sensitiva

nos dá resposta as questões:
¤ Qual evidência é a favor, contra e/ou irrelevante para uma dada
hipótese?
¤ Qual evidência distingue uma hipótese hi da hipótese hj?
• explicar os resultados para o usuário
Aula Encerrada Neste Ponto
Calcular probabilidades a posteriori
usando uma rede bayesiana

Caso simples:
• polytree (redes com conexões simples)


algoritmo recursivo usando teorema de bayes a cada passo
Caso complexo:
• rede multiplamente conectados

redução para polytree
¤ agrupamento (grandes tabelas)
¤ separação condicional (muitas redes)

simulação estocástica (muitas iterações)
Aprender probabilidades com estrutura fixa
Humanos acham fácil dizer o que causa o que, mas acham
difícil colocar números nos links.
 Tarefa de aprendizagem

• Dados:
relações de independência entre variáveis aleatórias (estrutura)
 probabilidades a priori das variáveis “de entrada”
 probabilidades a posteriori de variáveis “de saída”
• Calcular:
 probabilidades condicionais das variáveis dependentes


2 algoritmos principais:
• gradiente ascendente de P(D|Hi) - muito parecido com
aprendizagem de pesos em redes neurais
• algoritmo EM (Estimação Média)
• ambos iterativos e sujeito a encontrar mínimo local
Exemplo da tarefa de aprendizagem
P(R)
0,001
Roubo
Terremoto
Alarme
A
T
F
P(J)
?
?
JohnCalls
R
T
T
F
T
P(T)
0,002
T P(A)
T
?
F
?
T
?
T
?
MaryCalls
A P(M)
T
?
F
?
Exemplo da tarefa de aprendizagem

Dados de treinamento
• P(J|R), p(J|T), p(M|R), P(M|T)

Exemplos:
• True, False, False, False
• (...)
• False, False, True, False

explicar que usando bayes iterativamente pode calcular ?
a partir dos dados
Gradiente ascendente de P(D|H)
exemplo passo a passo
 formula de Mitchell que mostra similaridade com RN

Algoritmo EM
Redes Bayesianas x Redes Neurais:
similaridades
processo iterativo em N épocas
 ajuste das probabilidades condicionais no lugar de pesos
 use gradiente ascendente de P(D|Hi)

Redes Bayesianas x Redes Neurais
diferenças

Redes Bayesianas
• representações locais
• as variáveis possuem dois
níveis de ativação
• pode tratar qualquer subconjunto das variáveis como
entrada
• Inserção fácil de conhecimento
a priori
• nao implementavel em
hardware

Redes Neurais
• representacao global
distribuida
• variaveis discretas ou
continuas
• execucao em tempo linear
• entradas e saidas fixas
• dificil insercao de
conhecimento a priori
• implementavel em hardware
Bibliografia





Russel, S, & Norvig, P. (1995). Artificial Intelligence: a Modern
Approach (AIMA) Prentice-Hall. Pages 436-458, 588-593
An Introduction to Baysean Networks
Mitchell, T. & (1997): Machine Learning, McGraw-Hill. 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