1
Redes Bayesianas
Renato Fernandes Corrêa
CIn- UFPE
2
Conhecimento incerto
 A conexão entre antecedente e consequente não é uma
implicação lógica em nenhuma direção
 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.
CIn- UFPE
3
Conhecimento incerto
 A lógica de primeira ordem 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 do agente pode apenas
prover um grau de crença nas sentenças relevantes.
CIn- UFPE
4
Teoria da Probabilidade
 Fornece um meio de descrever e manipular
conhecimento incerto ou incompleto
 Associa às sentenças um grau de crença numérico entre
0e1
• 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
– evidências: percepções que o agente recebeu até agora
– Ex: P(cárie|dor de dente)= 0.8
CIn- UFPE
5
Probabilidade condicional
 Probabilidade condicional (a posteriori) de A dado que B
ocorreu é definida por:
• P(A|B) = P(AB) , quando P(B) > 0.
P(B)
 Teorema de Bayes:
P(A|B) = P(B|A) P(A)
P(B)
 Probabilidade condicional:
• possibilita inferência sobre uma proposição
desconhecida A dada a evidência B
CIn- UFPE
Probabilidade condicional
e independência
6
 Independência:
• P(A|B) = P(A)
• Exemplo: A = dor de dente e B=úlcera
– Úlcera não causa dor de dente
 Eventos mutuamente excludentes
• P(A  B) = 0
• Experimento: Lançamento de um dado
– A = a face do dado é ímpar e B = a face do dado é par
 Independência condicional
• Seja X e Y independentes dado Z => P(X|Y,Z) = P(X|Z)
• Independência condicional é crucial para o funcionamento
eficaz de sistemas probabilísticos.
CIn- UFPE
7
Redes Bayesianas (Redes de Crença)
 Estrutura de dados usada para representar 3 tipos de
conhecimento do domínio:
• relações de dependência entre variáveis aleatórias
(graficamente);
• probabilidades a priori de algumas variáveis;
• probabilidades condicionais entre variáveis
 Permitem calcular eficientemente a probabilidades a
posteriori de qualquer variável aleatória (inferência) por
meio de uma definição recursiva do teorema de Bayes.
 Conhecimento representado pode ser aprendido a partir
de exemplos
CIn- UFPE
8
Estrutura das Redes Bayesianas
 Uma Redes 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
CIn- UFPE
Rede Bayesiana com as
probabilidades condicionais
P(R)
0,001
P(T)
0,002
Roubo
Terremoto
Alarme
A
V
F
A
V
F
P(J)
0,90
0,05
João ligar
Roubo
V
V
F
F
Ter.
V
F
V
F
P(A)
0,950
0,940
0,290
0,001
P(M)
0,70
0,01
Maria ligar
P(A|R,T) =P(alarme-disparou|roubo, terremoto)
10
Redes Bayesianas
 Fornecem uma descrição completa do domínio
 A probabilidade de ocorrencia de qualquer estado do
domínio pode ser calculada
• probabilidade de uma conjunção de assinalamentos a cada
variável, tal que
P(X1=x1  ...  Xn=xn), pode ser abreviado como
P(x1, ..., xn)
• Ex: Calcular a probabilidade de o alarme tocar sem ter havido
assalto nem terremoto e João e Maria telefonarem
– P(A  R   T  J  M)=
= 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 %
CIn- UFPE
Inferência em Redes Bayesianas
• Causal (das causas para os efeitos)
P (João Ligar|Roubo) = 0.86
Alarme
Roubo
Evidência
JoãoLigar
Query
• Diagnóstico (dos efeitos para as causas)
P (Roubo|João Ligar) = 0.016
Alarme
Roubo
Query
JoãoLigar
Evidência
Inferência em Redes Bayesianas
• Intercausal (entre causas com um efeito comum)
P(Roubo/Alarme) = 0,376
P(Roubo/Alarme Terremoto) = 0,003
Alarme
Roubo
Query
Terremoto
Evidência
Evidência
• Mista (combinando duas ou mais das de cima)
P(Alarme/JoãoLigar Terremoto) = 0,03
Este é um uso simultâneo de inferência causal e diagnóstico.
Alarme
Terremoto
Evidência
JoãoLigar
Query
Evidência
13
Inferência em Redes Bayesianas
 Caso simples:
•
polytree (redes com conexões simples)
– algoritmo recursivo usando teorema de bayes a cada
passo
 Caso complexo:
•
rede multiplamente conectados (classes de algoritmos)
– redução para polytree
– agrupamento (grandes tabelas)
– separação condicional (muitas redes)
– árvore de junção ou árvore de cliques (mais usada)
– simulação estocástica (muitas iterações)

Software para inferêcia: Nética da NORSYS.
CIn- UFPE
14
Engenharia do conhecimento
para 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
1. causas “raízes”
2. variáveis que elas influenciam
3. 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
CIn- UFPE
Engenharia do conhecimento
para Redes Bayesianas
15
 São necessários n2k números para especificar a rede
completa(variáveis aleatórias booleanas), onde:
• K= n° de pais de cada variável e n = n° de nós
• É desejável que:
– cada variável seja diretamente influenciada por poucas
variáveis
– a topologia da rede reflita essas influências com um conjunto
apropriado de Pais
• algumas dependências poderão ser relaxadas
– Ex: P(Joãoligar|Terremoto) e P(Marialigar|Terremoto)
– se o alarme tocar e houver terremoto, eles vão assumir que esta
foi a causa do alarme ter disparado, e não vão ligar.
CIn- UFPE
16
Aprendizagem das probabilidades com
estrutura fixa
 Humanos acham fácil dizer o que causa o que, mas
acham difícil colocar probabilidades 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)
algoritmo EM (Estimação Média)
ambos iterativos e sujeito a encontrar mínimo local
CIn- UFPE
17
Aprendizagem da estrutura
 A duas classes de métodos de aprendizagem da
estrutura de uma rede bayesiana:
• Métodos baseados em Busca e Pontuação pesquisa no espaço de possíveis estruturas
– Determinar a melhor estrutura que se encaixa aos dados,
iniciando com uma rede sem arcos e adicionando-os aos
poucos e avaliando(pontuando) a estrutura obtida
– Existem vários métodos de pontuação
– ex: K2(Cooper e Herskovits, 1992)
• Métodos baseados em análise de dependência entre
variáveis
– Iniciar com uma estrutura totalmente conectada com arcos
sem direção, eliminar arcos baseando-se em testes de
independência condicional, associar direções aos arcos
– ex: CDL(Chen, Bell e Liu 1997)
CIn- UFPE
Software que aprende a estrutura e
probabilidades
 Belief Network Power Constructor (Cheng, Bell e Liu)
•Ordem dos atributos
(total ou parcial)
•Causas e efeitos diretos
•Estrutura Inicial
•Arcos proibidos
•Raízes e folhas
X1
Conjunto
de Dados
X2
X3
BNPC
Conhecimento
do Domínio
Opcional
X4
Estrutura e
Parâmetros
CIn- UFPE
19
Aplicação em Diagnóstico Médico
Visita à Asia
Fumante
Informação do Paciente
Tuberculose
Câncer (Pulmão)
Bronquite
Dificuldades Médicas
Tuberculose
ou Câncer
Raio-X
Dispnéia
Exames diagnósticos
Cooper, 1984
CIn- UFPE
20
Aplicação em Diagnóstico Médico
Tuber
Câncer
Tub ou Can
Visita à Asia
Presente
Presente
True
Presente
Ausente
True
Ausente
Presente
True
Ausente
Ausente
False
Tuberculose
Câncer (Pulmão)
Tuberculose
ou Câncer
Raio-X
Fumante
Bronchitis
Dispnéia
Medical Difficulties
Presente
Ausente
Tub ou Can
Bronquite
True
Presente
0.90
0.l0
True
Ausente
0.70
0.30
False
Presente
0.80
0.20
False
Ausente
0.10
0.90
Dispnéia
 As relações são tabelas de probabilidades condicionais
CIn- UFPE
21
Aplicação em Diagnóstico Médico
 PATHFINDER é um sistema de diagnóstico de
doenças que atacam os nodos linfáticos.
• Foi construido por membros do programa Stanford
Medical Computer Science, durante os anos 80.
• O sistema lida com 60 doenças e 100
evidências(sintomas e resultados de exames).
• A metodologia utilizada para a criação da base de
conhecimento foi a especificada anteriormente.
 Uma comparação recente demonstrou que o
Pathfinder está superando os especialistas
consultados durante sua criação (patologistas
reconhecidos mundialmente).
CIn- UFPE
Aplicação em Recuperação de
Informação
22
 O objetivo:
• desenvolver uma arquitetura de IR probabilística que:
– auxilie os usuários que tem necessidade de informações
estáveis em ordenar um grande volume de material
sensitivo ao tempo;
– permita a utilização de uma linguagem intuitiva na
especificação das necessidades de informação a serem
supridas;
– integre relevance feedback e dados de treinamento com o
julgamento feito pelo usuário para incrementalmente
melhorar sua performance de recuperação
CIn- UFPE
Aplicação em Recuperação de
Informação
23
 Tendo sido especificado:
• um ou mais tópicos de interesse, e
• características do documento que devem ser usadas
como evidência de cada tópico de interesse.
 A tarefa de recuperação de informação pode ser
divida em 3 passos:
• 1. Construir a rede representando a pergunta (query)
• 2. Pontue cada documento;
– 2.1. Extrair as características de cada documento;
– 2.2. Instanciar as características na rede de recuperação;
– 2.3. Calcular a probabilidade a posteriori da relevância do
documento.
• 3. Ranquear os documentos de acordo com as
pontuações.
CIn- UFPE
Aplicação em Recuperação de
Informação
24
 Requer dois conjuntos de probabilidades a serem
especificadas:
• A probabilidade a priori de um documento ser relevante
a um dado tópico ti;
• A probabilidade condicional da uma característica fik
estar presente em um documento, dado que o
documento é relevante para um tópico ti.
 A tarefa de recuperação de informação envolve
computar a probabilidade:
P(ti|f1,...,fm) = P(ti) P (f1,...,fm|ti)
P(f1,...,fm)
CIn- UFPE
Aplicação em Recuperação de
Informação em artigos de jornal
Política
contraditória
do governo dos
EUA
empréstimo
Intervenção
Conflito no
Oriente-Médio
Forças armadas
mortos
25
Corrupção
de oficiais
corrupção
CIn- UFPE
Aplicação em Recuperação de
Informação
26
 A relação ente tópicos:
• pode ser derivado examinando uma coleção de
documentos de treinamento, onde o julgamento de
relevância do documento para cada tópico é fornecido.
• Diagramas de co-ocorrência.
 Aproximação das probabilidades:
P(fk|ti) = # documentos relevantes para ti que contém fk
#documentos relevantes para o tópico ti
P(ti) = # documentos relevantes para ti
# total de documentos
CIn- UFPE
27
Aplicações de Redes Bayesianas
 Modelo do estudante para o ANDES, tutor inteligente para
Física, do Learning R&D Center da Universidade de
Pittsburgh. www.pitt.edu/~vanlehn/andes.html
 Produto para e-commerce modelado com agentes virtuais
distribuídos baseados em RB que supervisionam as linhas
de usuários em sites Web, da Manna Network Technologies.
www.mannanetwork.com
 SymText usa um modelo de contexto baseado em RB para
extrair informação de textos médicos escritos em linguagem
natural (Universidade de Utah - Spencer Koehler, CRL).
http://students.cs.byu.edu/~sbk/
CIn- UFPE
28
Aplicações de Redes Bayesianas
 Agentes em que as suas qualidades (mentais ou
emocionais) são descritas por redes bayesianas: passa-se
de um determinado estado emocional para um outro, com
uma certa probabilidade.
[email protected]
 PAINULIM é um sistema para apoio ao diagnóstico de
doenças neuro-musculares, desenvolvido por Yang Xiang,
com base em uma rede bayesiana múltiplamente seccionada
nos domínios clínico, EMG (eletromiografia) e condução
nervosa.
http://snowhite.cis.uoguelph.ca/faculty_info/yxiang/research.html
 Diversos outros sistemas são citados por Russ Greiner na
página www.cs.ualberta.ca/~greiner/bn.html#applic
CIn- UFPE
29
Outros Usos de Redes Bayesianas
 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
CIn- UFPE
30
Conclusões
 A maior vantagem do raciocínio probabilistico em
relação ao raciocínio lógico é permitir ao agente
chegar a decisões racionais mesmo quando não
há informação suficiente para provar que qualquer
das ações dadas irá funcionar.
 Raciocínio probabilístico trata o grau de incerteza
associado à maioria dos domínios.
 Estimativas grosseiras podem implicar em
respostas imprecisas,mesmo utilizando
sofisticados método estatísticos.
 Redes Bayesianas são usadas em muitas
aplicações do mundo real.
CIn- UFPE
31
Referências Bibliográficas
 Stuart, J. Russel and Norvig, P. (1995) - Artificial Intelligence:
A Modern Approach. Prentice Hall. Pages 436-458, 588-593.
 Mitchell, T. & (1997): Machine Learning, McGraw-Hill. Cap.6.
 Carneiro, A. Lenin. Aprendizado automático em redes
bayesianas. Dissertação de Mestrado. Brasília: UnB, Ciência
da Computação, 1999.
 Fung, R., Del Favero, B. Applying Bayesian Networks to
Information Retrieval. Proceedings of Communications of the
ACM, march 1995/Vol.38, No. 3.
 BNPC: http://www.cs.ualberta.ca/~jcheng/bnpc.htm
 Nética:http://www.norsys.com/
CIn- UFPE