Upload
internet
View
118
Download
2
Embed Size (px)
Citation preview
1
CIn- UFPE
Redes Bayesianas
Renato Fernandes Corrêa
2
CIn- UFPE
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.
3
CIn- UFPE
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.
4
CIn- UFPE
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 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
– evidências: percepções que o agente recebeu até agora– Ex: P(cárie|dor de dente)= 0.8
5
CIn- UFPE
Probabilidade condicional
Probabilidade condicional (a posteriori) de A dado que B ocorreu é definida por:• P(A|B) = P(AB) , 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
6
CIn- UFPE
Probabilidade condicional e independência
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.
7
CIn- UFPE
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
8
CIn- UFPE
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
RouboRoubo
Maria ligarMaria ligarJoão ligarJoão ligar
TerremotoTerremoto
AlarmeAlarme
Rede Bayesiana com as probabilidades condicionais
Roubo Ter. P(A)V V 0,950V F 0,940F V 0,290F F 0,001
A P(J)V 0,90F 0,05
A P(M) V 0,70 F 0,01
P(R)0,001
P(T)0,002
P(A|R,T) =P(alarme-disparou|roubo, terremoto)
10
CIn- UFPE
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 %
Inferência em Redes Bayesianas
Roubo Alarme JoãoLigar
Evidência Query
• Causal (das causas para os efeitos) P (João Ligar|Roubo) = 0.86
Roubo Alarme JoãoLigar
EvidênciaQuery
• Diagnóstico (dos efeitos para as causas) P (Roubo|João Ligar) = 0.016
Inferência em Redes Bayesianas
• Intercausal (entre causas com um efeito comum)P(Roubo/Alarme) = 0,376P(Roubo/Alarme Terremoto) = 0,003
• Mista (combinando duas ou mais das de cima)P(Alarme/JoãoLigar Terremoto) = 0,03Este é um uso simultâneo de inferência causal e diagnóstico.
Terremoto Alarme JoãoLigar
Evidência EvidênciaQuery
Roubo Alarme Terremoto
Query EvidênciaEvidência
13
CIn- UFPE
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.
14
CIn- UFPE
Engenharia do conhecimentopara Redes Bayesianas
1. Escolher um conjunto de variáveis relevantes que descrevam o domínio
2. Ordem de inclusão dos nós na rede1. causas “raízes”2. variáveis que elas influenciam3. 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
15
CIn- UFPE
Engenharia do conhecimentopara Redes Bayesianas
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.
16
CIn- UFPE
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
17
CIn- UFPE
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
BNPC
Conjunto de Dados
Conhecimentodo Domínio
•Ordem dos atributos(total ou parcial)
•Causas e efeitos diretos•Estrutura Inicial•Arcos proibidos•Raízes e folhas
X1X2
X3
X4
Estrutura eParâmetrosOpcional
Belief Network Power Constructor (Cheng, Bell e Liu)
19
CIn- UFPE
Cooper, 1984
Visita à Asia
Tuberculose
Tuberculoseou Câncer
Raio-X Dispnéia
BronquiteCâncer (Pulmão)
Fumante
Informação do Paciente
Dificuldades Médicas
Exames diagnósticos
Aplicação em Diagnóstico Médico
20
CIn- UFPE
Aplicação em Diagnóstico Médico
As relações são tabelas de probabilidades condicionais
Visita à Asia
Tuberculose
Tuberculoseou Câncer
Raio-X Dispnéia
BronchitisCâncer (Pulmão)
FumanteTuber
Presente
Presente
Ausente
Ausente
Câncer
Presente
Ausente
Presente
Ausente
Tub ou Can
True
True
True
False
Medical DifficultiesTub ou Can
True
True
False
False
Bronquite
Presente
Ausente
Presente
Ausente
Presente
0.90
0.70
0.80
0.10
Ausente
0.l0
0.30
0.20
0.90
Dispnéia
21
CIn- UFPE
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).
22
CIn- UFPE
Aplicação em Recuperação de Informação
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
23
CIn- UFPE
Aplicação em Recuperação de Informação
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.
24
CIn- UFPE
Aplicação em Recuperação de Informação
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 f ik
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)
25
CIn- UFPE
Aplicação em Recuperação de Informação em artigos de jornal
Políticacontraditória
do governo dosEUA
mortos
Conflito no Oriente-Médio
Forças armadasIntervenção
Corrupção de oficiais
corrupçãoempréstimo
26
CIn- UFPE
Aplicação em Recuperação de Informação
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
27
CIn- UFPE
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/
28
CIn- UFPE
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
29
CIn- UFPE
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
30
CIn- UFPE
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.
31
CIn- UFPE
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/