Redes Bayesianas – Inferência Rudini Sampaio DCC / UFLA

Redes Bayesianas – Inferência

Rudini SampaioDCC / UFLA

Rudini Sampaio DCC-UFLA

Redes Bayesianas - Inferência

Classificação dos Algoritmos de Inferência Exatos Aproximados Contínuos

Principais Algoritmos Exatos Bucket Elimination Junction Tree Algoritmo de Pearl

Principais Algoritmos Aproximados Forward Sampling (Logic Sampling) Likelihood Weighting Gibbs Sampling Metropolis-Hasting



Bucket Elimination Utiliza a regra da cadeia para atualizaras probabilidades a posteriori das variáveis

de uma rede bayesiana, baseadas nas evidências disponíveis.

Exemplo: Obter P(A) com evidência e={D=d,F=f}

)|(),|(),|()|(),|()()(),,,,,,( CGPCBfPHBdPACPHABPHPAPHGfdCBAP

G G

CGPCBfPHBdPACPHABPHPAPeUP )|(),|(),|()|(),|()()(),(

HH

HBdPHABPHPCBfPACPAPHfdCBAP ),|(),|()(),|()|()(),,,,,(

),(),|()|()(),,,,( BATCBfPACPAPfdCBAP


Redes Bayesianas - Bucket Elimination

Outro Exemplo

( ) 0.8 0.2P Grav

0.99 0.02( | )

0.01 0.98P TS Grav

0.93 0.12( | )

0.07 0.88P TU Grav

( , ) ( ) ( | ) ( 1| )Grav

P TS e P Grav P TS Grav P TU Grav

( 0) ( 0| 0) ( 1| 0) ( 1) ( 0| 1) ( 1| 1)

( 0) ( 1| 0) ( 1| 0) ( 1) ( 1| 1) ( 1| 1)

P Grav P TS Grav P TU Grav P Grav P TS Grav P TU Grav

P Grav P TS Grav P TU Grav P Grav P TS Grav P TU Grav

0.8 0.99 0.12 0.2 0.02 0.88 0.108064

0.8 0.01 0.12 0.2 0.98 0.88 0.17344

0.384( | )

0.616P TS e



Algoritmo Junction Tree

O Bucket Elimination não se preocupa com a ordem de eliminação das variáveis.

O Junction Tree obtém uma sequência ótima de eliminação e cria uma estrutura para propagar as multiplicações e marginalizações das tabelas

Definições Link moral Grafo moral Potencial e Domínio


Redes Bayesianas – Junction Tree


Definições Fill-Ins Sequência Perfeita de Eliminação Grafo triangulado Vértice Simplicial (todos os vizinhos são

ligados entre si)




Procedimento para Obter Sequência Perfeita de Eliminação em um Grafo Triangulado

Elimine um vértice simplicial (todos os seus vizinhos são ligados entre si)

Se ainda há vértices, volte ao passo anterior.

A1, A4, A5 e A6 são simpliciais




Obter Sequência Ótima de Eliminação em um Grafo Não Triangulado é um Problema NP-Difícil

Heurística muito eficiente: Escolha o vértice cujo produto do número de estados dos vértices

vizinhos (inclusive o próprio vértice) é mínimo

A (2 estados): 40

B (4 estados): 48

C (5 estados): 70

D (6 estados): 168

E (7 estados): 210


Redes Bayesianas – Junction tree

Propagação dos Potenciais

Definições Clique (subconjunto de variáveis todas ligadas entre si) Árvore (Grafo sem ciclos) Join Tree (Árvore de cliques tal que, para todas cliques C1 e C2,

todas as cliques pertencentes ao caminho entre C1 e C2 na Join Tree, contém a interseção de C1 e C2)



Propagação dos PotenciaisClique versus Separador (conjunto dos vértices não simpliciais da

clique) Construção da Join Tree A eliminação das variáveis gera uma sequência de cliques e

separadores Liga-se cada separador Si a uma clique Ck, posicionada depois na

ordem (k>i), que o contém (Si Ck)



Propagação dos Potenciais Constrói-se uma Junction Tree a partir da Join Tree. Cada

separador recebe uma “caixa” para guardar valores nos dois sentidos.

Coletando dados para V6


Redes Bayesianas – Forward Sampling

Algoritmo Aproximado Forward Sampling É também chamado Logic Sampling. É o algoritmo mais simples.

O algoritmo repete diversas vezes o procedimento abaixo: Escolha uma variável V sem pais ou com pais instanciados Escolha aleatoriamente um estado para V, baseado em sua tabela

de probabilidades Se V for uma variável evidenciada e o valor for diferente da

evidência, então a configuração atual é descartada Instancie a variável para o estado escolhido e contabilize a

configuração obtida Repita até que todas as variáveis estejam instanciadas.


Redes Bayesianas - Forward Sampling

Início com a variável A. Número aleatório R entre 0 e 1. Se R < 0.4, então tomamos A=y; senão A=n. Suponha que escolhemos A=y.

Variáveis B e C: P(B | A=y) = [0.3 0.7] e P(C | A=y) = [0.7 0.3]. Se R < 0.3, tomamos B=y; senão B=n. Se R < 0.7, tomamos C=y; senão C=n.

Fazemos isso até que todas as variáveis tenham sido selecionadas. Obtemos assim uma configuração. Se a configuração gerada não satisfaz as evidências disponíveis na rede, ela é rejeitada. Após várias configurações, obtemos a tabela ao lado.


Redes Bayesianas – Forward Sampling

Problemas do Forward Sampling

Se uma evidência é muito rara, a maioria das configurações geradas serão rejeitadas e será necessário muito tempo para se gerar um número razoável de configurações compatíveis.

Exemplo: No exemplo, {B=n, E=n} é uma evidência com probabilidade muito pequena 0.00282. Para se gerar 100 configurações compatíveis, serão necessárias mais de 35000 simulações

Manter Tabela Conjunta muito grande

Solução: Mantém um contador para cada variável, ao invés de armazenar a tabela inteira de configurações.


Redes Bayesianas – Likelihood Weighting

Algoritmo Likelihood Weighting

Muito usado (BayesiaLab) Resolve o problema de rejeições do Forward Sampling, dando

pesos as configurações segundo suas probabilidades de existência

Os contadores das variáveis não são mais números inteiros, mas números reais (soma de pesos).

Exemplo: Evidência {B=n, E=n}. A configuração {A=y. B=n, C=n,

D=y, E=n} terá um peso igual a P(B=n | A=y)P(E=n | C=n,D=y) = 0.7*0.001 = 0.0007


Redes Bayesianas – Gibbs Sampling

Gibbs Sampling Configuração inicial {A=y, B=n, C=y, D=y, E=n}. Geração da configuração seguinte. Regra da cadeia. Sorteio para A:

P(A | B=n, C=y, D=y, E=n) = (0.7*0.7,0.2*0.4) = (0.86,0.14)

Número aleatório 0.456 entre 0 e 1 A = y

Sorteio para C:

P(C | A=y, B=n, D=y, E=n) = (0.7*0.1,0.3*0.001) = (0.996,0.04)

Número aleatório 0.827 entre 0 e 1 C = y

Sorteio para D:

P(D | A=y, B=n, C=y, E=n) = (0.1*0.1, 0.9*0.001) = (0.9174, 0.0826)

Número aleatório 0.394 entre 0 e 1 D = y

Documents

Redes Bayesianas – Inferência Rudini Sampaio DCC / UFLA