Seção 6: ESTATÍSTICA EM ENGENHARIA E CIÊNCIAS EXATAS
Título:
Jaime Shinsuke Ide
Fábio Gagliardi Cozman
Escola Politécnica, Universidade de São Paulo
Av. Prof. Mello Moraes, 2231, 05508-900, São Paulo, SP – Brasil
[email protected], [email protected]
1
Este trabalho apresenta métodos para geração uniforme de redes Bayesianas (modelos
baseados em grafos direcionados para representação de distribuições conjuntas). Redes
Bayesianas foram originalmente propostas pela comunidade de inteligência artificial na
década de 80 e tem sido aplicadas em uma enorme variedade de problemas de decisão e
diagnóstico automatizado. Inúmeros trabalhos tem sido propostos para inferência e
estimação de redes Bayesianas, e testes tem sido conduzidos em conjuntos de redes
selecionados arbitrariamente. Até o momento não existe nenhum método na literatura que
permita gerar redes Bayesianas de forma uniforme. A proposta deste trabalho é construir
um gerador aleatório e uniforme de redes Bayesianas com características determinadas pelo
usuário (tipo de estrutura, tipo de distribuições de probabilidade associadas, número
máximo de arcos ou número máximo de arcos por nó e número de nós). Para tanto,
empregam-se cadeias de Markov para geração da estrutura da rede (informação qualitativa)
e métodos baseados em distribuições Dirichlet para geração das distribuições de
probabilidades associadas a cada nó (informação quantitativa). O método para geração de
estruturas foca tanto a geração de grafos multi-conectados quanto de grafos conectados de
forma única (“polytrees”). O método desenvolvido foi implementado e o programa
resultante (BNGenerator) está disponível na Internet pelo endereço:
http://www.pmr.poli.usp.br/ltd/Software/BNGenerator/index.html
2
Inteligência
Artificial
(incertezas)
Redes
Bayesianas
(RB)
BNGenerator
Algoritmos
de
Inferência
Métodos
Aproximados
números quasialeatórios
Métodos
MCMC
Geração
de RB
Gibbs
sampler
Geração de
distribuições
condicionais
Geração
de DAG
(Estrutura do
grafo)
Motivação: Inúmeros trabalhos tem sido propostos para inferência e estimação de redes
Bayesianas, e testes tem sido conduzidos em conjunto com redes selecionados arbitrariamente.
Até o momento não existe nenhum método na literatura que permita gerar redes Bayesianas de
forma uniforme. A proposta deste trabalho é construir um gerador aleatório e uniforme de
redes Bayesianas com características determinadas pelo usuário (tipo de estrutura, tipo de
distribuições de probabilidade associadas, etc).
3
Ilustração: Rede com 3 nós.
Nó: representa
uma variável
Definição
A
• Grafos
acíclicos
direcionados.
(Directed Acyclic Graph - DAG)
• Cada variável está associada à uma
distribuição de probabilidade.
B
de interesse.
C
• Distribuição Conjunta definida por:
Conjunto de todas as variáveis
Arco: indica uma
dependência
causal e de
informação entre
duas variáveis
p(A,B,C) = p(A).p(B/A).p(C/A)
p(X) = Pi p(Xi | pa{Xi})
p (C/A)
0 0
0,3
p (A)
0 1
0,2
A=0
0,3
1 0
0,7
A=1
0,7
1 1
0,8
Conjunto de todos os pais ( se tiver)
•Resultado:representação compacta e eficiente.
4
Grafos
Tipos diferentes
de estruturas
Direcionados
de grafos
Não direcionados
Conectado
B
Acíclico
Cíclico
A
A
Desconectado
D
C
E
B
D
C
E
A
Uni-conectado
(árvore)
Multi-conectado
B
D
A
Árvore simples
Polytree
A
B
D
A
C
E
B
D
B
D
C
C
E
C
E
Ilustrações
para cada
tipo de
estrutura
E
5
Nó: representa
uma variável
A
B
de interesse.
C
Arco: indica uma
dependência
causal e de
informação entre
duas variáveis
p(A,B,C) = p(A).p(B/A).p(C/A)
p (C/A)
0 0
0,3
p (A)
0 1
0,2
A=0
0,3
1 0
0,7
A=1
0,7
1 1
0,8
Para gerar (construir) uma
rede Bayesiana precisamos:
• Gerar a estrutura (grafo)
• Gerar as distribuições
condicionais associadas a cada
nó
A parte mais difícil é a
geração de grafos (de maneira
controlada)
6
Distribuições a
serem geradas de
forma uniforme
Sejam as variáveis
binárias: A, B e C
p (C/A,B)
A
B
C
0 0 0
0,1
0 0 1
0,2
0 1 0
0,3
0 1 1
0,4
1 0 0
0,9
1 0 1
0,8
1 1 0
0,7
1 1 1
0,6
[0,1 0,9]
Metodologia geral
• Para uma distribuição com k
valores, emprega-se a distribuição
multivariável de Dirchlet de
dimensão k. Para isso, define-se k
parâmetros (1,2,...,k).
• Para se ter distribuição
uniforme, define-se ’s =1.
[0,2 0,8]
• Geração :
- Sorteia-se k valores de u~U(0,1)
[0,3 0,7]
- Computar - log(u) para cada u
- Normalizar os k valores obtidos
[0,4 0,6]
7
Número total de combinações possíveis
número de nós (n)
1 2 3
combinações possíveis (cn) 1
4
5
6
7
8
3 25 543 29281 3781503 1138779265 783702329343
• Dimensão da dificuldade. O número de estruturas de grafos possíveis
cresce super-exponencialmente em função do número de nós.
• Métodos heurísticos são propostos para geração de redes Bayesianas.
Não garante sobre a distribuição dos grafos gerados.
• É desejável que se possua controle sobre a geração do grafo.
• “Geração uniforme de grafos” significa que cada grafo tem a mesma
probabilidade de ser gerado, dentro do domínio de todos os grafos
possíveis.
8
...
• Idéia chave: partir de um grafo (estado) inicial, e gerar grafos subsequentes segundo uma
regra de transição de Markov que garante a convergência da simulação. A cada n- iterações
suficientes para a convergência, o grafo (estado) atual é selecionado para a amostra. Estes
grafos selecionados constituirão uma amostra uniforme de grafos com determinadas
características.
• Condições que devem ser satisfeitas:
• Irredutibilidade
• Aperiodicidade
• Matriz de transição duplamente estocástica
Cadeia de Markov Ergódica
Distribuição estacionária
converge para uniforme
9
Exemplo de geração de grafo multi-conectado com 3 nós
estado 0
0
1
estado 1
P01(0,2)=1/6
2
0
P10(0,2)=1/6
0
1
2
3.
..
17
P11=1/2
...
17
5/6 1/6 0
0
...
0
1/6 1/2 1/6 1/6
1/6 p22
1/6
. 0.
..
2
...
..
0
p33
...
...
...
.. .
. ..
estado 3
1
2
P13(0,1)=1/6
3
..
.
1
P31(0,1)=1/6
0
2
0
0
0
P22
Matriz de transição
1
2
P12(1,2)=1/6
P00=5/6
0
1
estado 2
P21(1,2)=1/6
...
P33
Regra de transição
• Sortear um arco(i,j), com probabilidade 1/6
• Se o arco(i,j) existir, manter atual estado
• Senão, adicionar o arco(i,j)
10
Algoritmo 1: Gerando DAG´s multi-conectados
Entrada: número de nós (n), número máximo de arcos por nó
(maxD), número de iterações (N).
Saída: DAG multi-conectado com n nós.
01. Inicializar grafo como uma árvore única ordenada.
02. Repetir o seguinte ciclo N vezes;
03.
Gerar um par distinto de nós, i e j, distribuído
uniformemente;
04.
Se o arco (i,j) existir no grafo atual, remover o
arco (i,j), desde que o grafo permaneça acíclico e conectado;
05.
Senão;
06.
Adicionar o arco(i,j), desde que o grafo
permaneça acíclico e satisfaça a condição maxD;
07.
Teorema 1- A matriz de transição
definida pelo Algoritmo 1 é
duplamente estocástica.
Teorema 2 - A cadeia de Markov
gerada pelo Algoritmo 1 é
irredutível.
Teorema 3 - A cadeia de Markov
gerada é aperiódica.
Teorema 4 - A cadeia de Markov
gerada é ergódica e sua distribuição
estacionária única converge para a
distribuição uniforme.
Senão, permaneça no mesmo estado (grafo) ;
08. Retornar o grafo atual após as N iterações.
11
Algoritmo 2: Gerando polytrees
Entrada: número de nós (n), número máximo de arcos por nó (maxD), número de iterações (N).
Saída: polytree com n nós.
01. Inicializar grafo como uma árvore simples ordenada.
02. Repetir o seguinte ciclo N vezes;
03.
Gerar um par distinto de nós, i e j, distribuído uniformemente;
04.
Se o arco (i,j) existir no grafo atual ou se o grafo resultante não satisfazer a condição
maxD, manter o mesmo estado (grafo);
05.
Senão;
06.
07.
Inverter o arco (i,j) com probabilidade de 1/2, e então;
Encontrar o predecessor, nó k, no caminho entre os nós i e j, remover o arco
entre k e j, e adicionar o arco (i,j) ou (j,i), dependendo do sorteio na linha 6;
08. Retornar o grafo atual após as N iterações.
12
( http://www.pmr.poli.usp.br/ltd/Software/BNGenerator/index.html)
• Geração aleatória e uniforme de
redes Bayesianas
• Programa desenvolvido em Java
BNGenerator
• Linha de comando do BNGenerator:
java BnGenerator -nNodes 20 maxDegree 3 -nGraphs 1 -format xml
-nval 4 -fName Poly1 -structure
singly
Visualização (no sistema JavaBayes - http://www-2.cs.cmu.edu/~javabayes ) de uma
polytree de 20 nós gerada pelo BNGenerator.
13
Histograma 1: Gerando grafos multi-conectados
Histograma 2: Gerando polytrees
300
900
800
250
700
200
média
600
média
500
150
400
100
300
200
50
estado
0
1 00
estado
0
0
100
200
300
400
4 nós; maxDegree 3; 446 diferentes tipos de grafos
500
0
50
1 00
5 nós; maxDegree 3; 128 diferentes tipos
14
• O gerador aleatório de redes Bayesianas desenvolvido, BNGenerator, é algo inédito na área.
Devido à sua característica de possibilitar o controle da estrutura da rede gerada. Vale a pena
ressaltar que a metodologia desenvolvida, empregando cadeias de Markov, para geração aleatória de
redes é flexível o suficiente para aplicá-la a diversos tipos de estruturas de interesse.
• A desvantagem do método é a dificuldade em determinar o número de iterações necessários para a
convergência da cadeia de Markov. O inconveniente é superado, adotando-se um número grande de
iterações; e constatou-se que o algoritmo desenvolvido é rápido, podendo processar muitas iterações
em pouco tempo.
• Provas teóricas sobre o método desenvolvido encontra-se no artigo:
Random generation of Bayesian networks. XI Simpósio em Inteligência Artificial (SBIA2002), Recife, 2002.
(artigo aceito, a ser publicado)
• O uso de amostras uniformes de redes Bayesianas para análise de métodos MCMC de inferência é
apresentado em:
Testing MCMC algorithms with ramdomly generated Bayesian networks. I Workshop de Teses e Dissertações
em Inteligência Artificial - WTDIA'02, realizado junto ao SBIA2002. (artigo submetido)
(Para os interessados, o autor estará distribuindo alguns exemplares dos artigos acima, entre 17h30 e 18h30. Compareça!)
15