Upload
internet
View
109
Download
5
Embed Size (px)
Citation preview
Redes BayesianasRedes Bayesianas
Paulo AdeodatoGeorge Cavalcanti
CIn-UFPE
RoteiroRoteiro
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:Probabilidade Condicional:Definição e PropriedadesDefinição e Propriedades
.0)( se)(
0)( se )(
)()|(
APBP
APAP
BAPABP
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- )()|()()|()( BPBAPAPABPBAP
Teorema da Multiplicação de Teorema da Multiplicação de ProbabilidadesProbabilidades
11
12121
,,|
|
nn
n
AAAP
AAPAPAAAP
Esse resultado permite calcular a probabilidade de ocorrência simultânea de vários eventos a partir das probabilidades condicionais.
Probabilidade de um EventoProbabilidade de um Evento
iBP
B
jiBB
i
i
k
i
ji
,0)(
,
1
Considere os eventos B1,...,Bk formando uma partição de , isto é,
* Intuitivamente, qualquer que seja o resultado de um experimento, um e somente um desses eventos Bi acontecerá.Graficamente,
B1
B2
B3 B6
B5B4
A
A A Bi
i
1
6Sempre vale a decomposição
mas os eventos A Bi são mutuamente excludentes.
Assim, podemos calcular a probabilidade de A deforma aditiva
61
)(i
iBAPAP
)()|()( iii BPBAPBAP onde cada uma dessas interseções é dada por:
E dessa maneira temos o seguinte
Teorema da Probabilidade TotalTeorema da Probabilidade Total
iki
i BPBAPAP
1
|
A 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 BayesTeorema de Bayes
jjj
iii BPBAP
BPBAPABP
)()|(
)()|()|(
Permite calcular a probabilidade da “causa” Bi ter acontecido, dado que a “conseqüência A tenha sido observada.
ExemploExemplo 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)Exemplo (Continuação)
Cada elemento da matriz de confusão representa a probabilidade condicionada P(tipo diagnosticado | tipo real) de hepatite.
DIAGNOSTICADAR A B CE A 0,85 0,10 0,05A B 0,10 0,70 0,20L C 0,20 0,15 0,65
ExercícioExercí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 BidimensionaisVariaveis 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 DiscretasVAs 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:
YjXijiji yxyxpyx , )],,(),,[(
onde: ),(),( jiji yYxXPyxp
p(xi,yj) representa a Probabilidade Conjunta:
VAs Bidimensionais DiscretasVAs Bidimensionais Discretas (cont.)(cont.)
Assim:
0),( ji yxp
e
1),( XYji yxp
ExemploExemplo
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)?
EMPRESAF E1 E2 E3A F1 1/5 1/5 1/5B. F2 1/5 0 1/5
Distribuições MarginaisDistribuições Marginais
Dada p(xi,yj), é possível obter, tanto a distribuição de X quanto a distribuição de Y:
Yjy
jii yYxXPxXP ),()(
e
Yjy
ji yxp ),(
Xix
jij yYxXPyYP ),()(
Xix
ji yxp ),(
Distribuições Marginais (cont.)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?
EMPRESAF E1 E2 E3A F1 1/5 1/5 1/5B. F2 1/5 0 1/5
2/5 2/51/52/53/5
IndependênciaIndependê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 ConjuntaDistribuiçã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 Toothache
Cavity 0.04 0.06Cavity 0.01 0.89
Exemplo de uma distribuição de probabilidade conjunta
Redes Bayesianas: representação do Redes Bayesianas: representação do conhecimento para raciocínio com conhecimento para raciocínio com
incertezaincerteza
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.
Conhecimento representado:• pode ser aprendido a partir de exemplos reutilizando parte
dos mecanismos de raciocínio
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.
Estrutura de uma rede bayesianaEstrutura 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 Construção (manual) de uma rede bayesianabayesiana
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 Exemplo simples de rede bayesiana (cont.)(cont.)
P(T)
0,002
P(R)
0,001
R T P(A)
T T 0,95T F 0,94F T 0,29F F 0,001
A P(J)
T 0,90F 0,05
A P(M)
T 0,70F 0,01
Roubo Terremoto
Alarme
JohnCalls MaryCalls
Decomposição da Probabilidade ConjuntaDecomposição da Probabilidade Conjunta
121 ,,,| nn xxxxP
121 ,,, xPxxxP n 213 ,| xxxP 12 | xxP
X1
X2
X3
Xn
Decomposição da Probabilidade ConjuntaDecomposiçã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 bayesianasAprendizagem 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 conhecimentoTipos 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 bayesianaOrdenar 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 Exemplo de rede bayesiana não puramente causalnã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.
Roubo
Terremoto
Alarme
JohnCalls
MaryCalls
Exemplo de rede bayesiana Exemplo de rede bayesiana não puramente causal (cont.)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 Exemplo de rede bayesiana não puramente causal (cont.)não puramente causal (cont.)
Roubo
Terremoto
Alarme
JohnCalls
MaryCalls
Preencher tabelas de probabilidades Preencher tabelas de probabilidades condicionais com conhecimento do condicionais com conhecimento do
domíniodomí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 Preencher tabelas de probabilidades condicionais com conhecimento do condicionais com conhecimento do
domíniodomínio
Cold Flu Malaria P(Fever) P(Fever)
F F F 0,0 1,0F F T 0,9 0,1F T F 0,8 0,2F T T 0,98 0,02T F F 0,4 0,6
T F T 0,94 0,06
T T F 0,88 0,12
T T T 0,988 0,012
Versatilidade das redes bayesianasVersatilidade 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 Alarme Roubo
EvidênciaQuery
Versatilidade das redes bayesianasVersatilidade das redes bayesianas
• Intercausal (entre causas com um efeito comum) P(Roubo/Alarme) = 0,376 P(Roubo/Alarme Terremoto) = 0,373
• 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.
Roubo Alarme Terremoto
Query Evidência
JohnCalls Alarme Terremoto
Evidência EvidênciaQuery
Exemplo da tarefa de aprendizagemExemplo da tarefa de aprendizagem
Roubo Terremoto
Alarme
JohnCalls MaryCalls
P(T)0,002
P(R)0,001
R T P(A)T T ?T F ?F T ?T T ?
A P(J)T ?F ?
A P(M)T ?F ?
Outros UsosOutros 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 PontoAula Encerrada Neste Ponto
Calcular probabilidades a posteriori Calcular probabilidades a posteriori usando uma rede bayesianausando 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 Aprender probabilidades com estrutura fixafixa
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 aprendizagemExemplo da tarefa de aprendizagem
Roubo Terremoto
Alarme
JohnCalls MaryCalls
P(T)0,002
P(R)0,001
R T P(A)T T ?T F ?F T ?T T ?
A P(J)T ?F ?
A P(M)T ?F ?
Exemplo da tarefa de aprendizagemExemplo 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)Gradiente ascendente de P(D|H)
exemplo passo a passo formula de Mitchell que mostra similaridade com RN
Algoritmo EMAlgoritmo EM
Redes Bayesianas x Redes Neurais:Redes Bayesianas x Redes Neurais:similaridadessimilaridades
processo iterativo em N épocas ajuste das probabilidades condicionais no lugar de
pesos use gradiente ascendente de P(D|Hi)
Redes Bayesianas x Redes NeuraisRedes Bayesianas x Redes Neuraisdiferençasdiferenças
Redes Bayesianas• representações locais• as variáveis possuem dois
níveis de ativação• pode tratar qualquer sub-
conjunto 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
BibliografiaBibliografia
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