UNIVERSIDADE DO VALE DO ITAJAÍ
CENTRO DE CIÊNCIAS TECNOLÓGICAS DA TERRA E DO MAR
CURSO DE ENGENHARIA DE COMPUTAÇÃO
AMBIENTE COMPUTACIONAL PARA MODELAGEM E
SIMULAÇÃO DE REDES BAYESIANAS
Área de Inteligência Artificial
por
Thales Lange
Raimundo Celeste Ghizoni Teive, Dr.
Orientador
São José (SC), dezembro de 2008
UNIVERSIDADE DO VALE DO ITAJAÍ
CENTRO DE CIÊNCIAS TECNOLÓGICAS DA TERRA E DO MAR
CURSO DE ENGENHARIA DE COMPUTAÇÃO
AMBIENTE COMPUTACIONAL PARA MODELAGEM E
SIMULAÇÃO DE REDES BAYESIANAS
Área de Inteligência Artificial
por
Thales Lange
Relatório apresentado à Banca Examinadora do
Trabalho de Conclusão do Curso de Engenharia
de Computação para análise e aprovação.
Orientador: Raimundo C. Ghizoni Teive, Dr.
São José (SC), dezembro de 2008
SUMÁRIO
LISTA DE ABREVIATURAS....................................................................................v
LISTA DE FIGURAS................................................................................................vi
LISTA DE TABELAS...............................................................................................vii
LISTA DE EQUAÇÕES..........................................................................................viii
RESUMO.....................................................................................................................ix
ABSTRACT.................................................................................................................x
1. INTRODUÇÃO.......................................................................................................1
1.1. PROBLEMATIZAÇÃO................................................................................................................3
1.1.1. Formulação do Problema...........................................................................................................3
1.1.2. Solução Proposta.........................................................................................................................3
1.2. OBJETIVOS...................................................................................................................................4
1.2.1. Objetivo Geral.............................................................................................................................4
1.2.2. Objetivos Específicos...................................................................................................................4
1.3. METODOLOGIA...........................................................................................................................4
1.4. ESTRUTURA DO TRABALHO..................................................................................................5
2. FUNDAMENTAÇÃO TEÓRICA..........................................................................6
2.1. PROBABILIDADE........................................................................................................................6
2.1.1. Probabilidade incondicional.......................................................................................................6
2.1.2. Probabilidade condicional..........................................................................................................6
2.1.3. Probabilidade conjunta e regra fundamental da probabilidade............................................7
2.1.4. Regra de Bayes.............................................................................................................................8
2.1.5. Regra da cadeia............................................................................................................................8
2.2. REDES BAYESIANAS..................................................................................................................9
2.2.1. Redes causais..............................................................................................................................10
2.2.2. Evidências...................................................................................................................................11
2.2.3. D-separação em redes causais..................................................................................................12
2.2.3.1. Conexões seriais......................................................................................................................12
2.2.3.2. Conexões divergentes.............................................................................................................12
2.2.4. Propagação de evidências.........................................................................................................13
2.2.4.4. Rede Bayesiana dada a evidência M Ligou.........................................................................22
2.2.4.6. Rede Bayesiana dada as evidências em M Ligou e J Ligou...............................................24
2.3. ALGORITMOS PARA PROPAGAÇÃO DE EVIDÊNCIAS.................................................25
2.3.1. Junction Tree.............................................................................................................................26
2.3.1.1. Grafos triangulados................................................................................................................26
2.3.1.2. Grafos de domínios não triangulados..................................................................................29
2.3.1.3. Construção da join tree..........................................................................................................31
2.3.1.4. Marginalização e normalização............................................................................................32
2.3.1.5. Propagação na junction tree.................................................................................................33
2.3.2. Amostragem de Gibbs...............................................................................................................35
2.3.2.1. Cálculo das probabilidades dos estados...............................................................................36
2.3.2.2. Influência do número de amostras.......................................................................................38
2.3.2.3. Cálculo das probabilidades dos estados dado evidências..................................................40
2.3.2.4. Influência do número de amostras dado evidências...........................................................41
3. DESENVOLVIMENTO........................................................................................44
3.1. VISÃO DE NEGÓCIO................................................................................................................44
iii
3.1.2.1. Requisitos funcionais..............................................................................................................45
3.1.2.2. Requisitos não funcionais......................................................................................................48
3.1.2.3. Regras de negócio...................................................................................................................49
3.2. VISÃO DE CASO DE USO.........................................................................................................49
3.2.1. Ator do sistema: Projetista.......................................................................................................50
3.2.2. Telas do sistema.........................................................................................................................50
3.2.3. Casos de Uso...............................................................................................................................51
3.3. VISÃO DINÂMICA.....................................................................................................................51
3.3.1. Pacotes do sistema.....................................................................................................................52
3.3.2. Diagramas de classe por componente.....................................................................................53
3.3.3. Diagramas de atividade da interface de desenho...................................................................58
3.3.4. Algoritmos para propagação de evidências............................................................................60
4. SIMULAÇÕES......................................................................................................63
4.1. REDE BAYESIANA PARA ANÁLISE DO MERECIMENTO DO CRÉDITO..................63
4.2. AMOSTRAGEM DE GIBBS......................................................................................................64
4.2.1. Simulação sem evidências.........................................................................................................64
4.2.2. Simulação com múltiplas evidências.......................................................................................65
4.2.3. Influência do número de amostras..........................................................................................67
4.2.4. Desempenho...............................................................................................................................68
4.3. JUNCTION TREE.......................................................................................................................70
4.3.1. Grafo moral................................................................................................................................70
4.3.2. Triangulação..............................................................................................................................70
4.3.3. Construção da Join Tree...........................................................................................................71
4.3.4. Simulação sem evidências.........................................................................................................72
4.3.5. Simulação com evidências........................................................................................................74
4.3.6. Considerações finais da implementação do Junction Tree...................................................75
5. CONSIDERAÇÕES FINAIS................................................................................76
5.1. SUGESTÕES PARA TRABALHOS FUTUROS.....................................................................77
iv
LISTA DE ABREVIATURAS
GUI
IA
INPE
TCC
UFV
UML
UNIVALI
Graphical User Interface
Inteligência Artificial
Instituto Nacional de Pesquisas Espaciais
Trabalho de Conclusão de Curso
Universidade Federal de Viçosa
Unified Modeling Language
Universidade do Vale do Itajaí
v
LISTA DE FIGURAS
Figura 1. Um grafo cíclico. Isto não é permitido nas Redes Bayesianas...............................................10
Figura 2. Rede causal para o problema reduzido da falha da partida do motor de um carro.................11
Figura 3. Rede causal com conexão serial..............................................................................................12
Figura 4. Rede causal com conexão divergente......................................................................................13
Figura 5. Rede causal com conexão convergente...................................................................................13
Figura 6. Rede Bayesiana para o problema do alarme...........................................................................14
Figura 7. Rede Bayesiana com probabilidades dos estados...................................................................18
Figura 8. Rede Bayesiana para o problema do alarme dada a evidência MLigou.................................23
Figura 9. Rede Bayesiana para o problema do alarme dada as evidências MLigou e JLigou...............25
Figura 10. Grafo moral não direcionado para a rede causal do problema do alarme.............................27
Figura 11. Grafo resultante dado a eliminação do nó Alarme................................................................28
Figura 12. Eliminação das variáveis Ladrão, Terremoto e Maria..........................................................29
Figura 13. Grafo moral não triangulado..................................................................................................29
Figura 14. Grafo moral G' não triangulado, depois da seqüência de eliminação A, C, H, I e J............30
Figura 15. Os cliques, separadores e índices resultantes da Figura 10...................................................32
Figura 16. Join tree para cliques e separadores da Figura 15.................................................................32
Figura 17. Junction Tree para o problema do alarme.............................................................................34
Figura 18. Junction Tree com transmissão de mensagens, dado a evidência MLigou..........................34
Figura 19. Junction Tree com transmissão de mensagens, dado a evidência JLigou............................35
Figura 20. Fluxograma do algoritmo amostragem de Gibbs..................................................................37
Figura 21. Gráfico erro (%) versus número de amostras para LSim e JLigou (1º ensaio)..........................39
Figura 22. Gráfico erro (%) versus número de amostras para LSim e JLigou (2º ensaio)..........................39
Figura 23. Gráfico erro médio (%) versus número de amostras para LSim e JLigou.................................39
Figura 24. Gráfico erro (%) versus número de amostras para TSim e LNão (1º ensaio)............................41
Figura 25. Gráfico erro (%) versus número de amostras para LNão e TSim (2º ensaio)............................42
Figura 26. Gráfico erro médio (%) versus número de amostras para TSim e LNão...................................42
Figura 27. Tela de desenho e simulação (TFMain)................................................................................50
Figura 28. Telas para configurações: (a) TFBNProperties ; (b) TFNodeProperties..............................51
Figura 29. Casos de Uso..........................................................................................................................51
Figura 30. Pacotes do sistema: (a) pacotes da visão macro; (b) pacotes do Motor da BN....................52
Figura 31. Diagramas de componentes: (a) visão macro; (b) Motor da RB..........................................53
Figura 32. Diagramas de classe para o componente Interface Gráfica..................................................54
Figura 33. Diagramas de classe para o componente Desenho................................................................54
Figura 34. Diagramas de classe para o componente Motor da RB.........................................................56
Figura 35. Diagrama de classe para o componente Controladora..........................................................58
Figura 36. Diagrama de atividade para a ferramenta de inserção de arestas entre nós..........................59
Figura 37. Diagrama de atividade para a ferramenta de seleção............................................................59
Figura 38. Visão macro da implementação do algoritmo JunctionTree.................................................60
Figura 39. Triangular o grafo G..............................................................................................................61
Figura 40. Determinar os cliques e separadores.....................................................................................61
Figura 41. Conectar os separadores aos seus respectivos cliques..........................................................62
Figura 42. Rede Bayesiana para análise do merecimento do crédito.....................................................63
Figura 43. Erro médio e máximo conforme o número de amostras.......................................................68
Figura 44. Erro médio e tempo de execução versus número de amostras..............................................69
Figura 45. Grafo moral............................................................................................................................70
vi
LISTA DE TABELAS
Tabela 1. Tabela de probabilidades condicionais.....................................................................................7
Tabela 2. Nomes das variáveis e estados................................................................................................14
Tabela 3. Probabilidades incondicionais para as variáveis: (a) Ladrão; (b) Terremoto.........................15
Tabela 4. P (A | L , T)..............................................................................................................................16
Tabela 5. P (J | A)....................................................................................................................................16
Tabela 6. P (M | A)..................................................................................................................................16
Tabela 7. P (A , L , T) e P (A).................................................................................................................17
Tabela 8. P (J , A) e P (J).........................................................................................................................17
Tabela 9. P (M , A) e P (M).....................................................................................................................18
Tabela 10. P (A | e = M Ligou)...................................................................................................................19
Tabela 11. P (J , A) e P(J | e = M Ligou)....................................................................................................19
Tabela 12. P (A , T).................................................................................................................................20
Tabela 13. P (A | T).................................................................................................................................20
Tabela 14. P (T | A) não normalizadas....................................................................................................20
Tabela 15. P (T | A ) normalizadas..........................................................................................................21
Tabela 16. P (T , A) e P (T | e = M Ligou)..................................................................................................21
Tabela 17. P (A , L).................................................................................................................................21
Tabela 18. P (A | L).................................................................................................................................22
Tabela 19. P (L | A) não normalizadas....................................................................................................22
Tabela 20. P ( L | A) normalizadas..........................................................................................................22
Tabela 21. P ( L , A ) e P (L | e = M Ligou)................................................................................................22
Tabela 22. P (A | e = M Ligou , J Ligou)........................................................................................................24
Tabela 23. P (T , A) e P(T | e = M Ligou , J Ligou).......................................................................................24
Tabela 24. P (L , A) e P (L | e = M Ligou , J Ligou)......................................................................................24
Tabela 25. Domínio para cada variável...................................................................................................27
Tabela 26. Domínio para cada variável do grafo da Figura 13..............................................................30
Tabela 27. Domínio para cada variável do grafo G'...............................................................................30
Tabela 28. P (A , L , T) e P (A)...............................................................................................................33
Tabela 29. Cobertura de Markov para as variáveis da Rede Bayesiana da Figura 6 ............................36
Tabela 30. Vetor com estados aleatórios para as variáveis....................................................................36
Tabela 31. Amostragem de Gibbs e erro percentual...............................................................................38
Tabela 32. Amostragem de Gibbs e erro percentual, dada as evidências MLigou e JLigou.................40
Tabela 33. Probabilidades a posteriori e erro..........................................................................................65
Tabela 34. Evidências instanciadas ........................................................................................................66
Tabela 35. Probabilidades a posteriori e erro – múltiplas evidências....................................................67
Tabela 36. Probabilidades a posteriori e diferença.................................................................................73
Tabela 37. Probabilidades a posteriori e diferença, para simulação com múltiplas evidências............74
Tabela 38. Evidências instanciadas.........................................................................................................75
vii
LISTA DE EQUAÇÕES
Equação 1...................................................................................................................................................6
Equação 2...................................................................................................................................................6
Equação 3...................................................................................................................................................7
Equação 4...................................................................................................................................................7
Equação 5...................................................................................................................................................7
Equação 6...................................................................................................................................................7
Equação 7...................................................................................................................................................8
Equação 8...................................................................................................................................................8
Equação 9...................................................................................................................................................8
Equação 10.................................................................................................................................................8
Equação 11.................................................................................................................................................9
Equação 12.................................................................................................................................................9
Equação 13...............................................................................................................................................17
Equação 14...............................................................................................................................................17
Equação 15...............................................................................................................................................17
Equação 16...............................................................................................................................................19
Equação 17...............................................................................................................................................19
Equação 18...............................................................................................................................................20
Equação 19...............................................................................................................................................20
Equação 20...............................................................................................................................................20
Equação 21...............................................................................................................................................21
Equação 22...............................................................................................................................................31
Equação 23...............................................................................................................................................33
Equação 24...............................................................................................................................................33
Equação 25...............................................................................................................................................33
Equação 26...............................................................................................................................................33
Equação 27...............................................................................................................................................33
Equação 28...............................................................................................................................................34
Equação 29...............................................................................................................................................36
Equação 30...............................................................................................................................................37
Equação 31...............................................................................................................................................68
viii
RESUMO
LANGE, Thales. Ambiente Computacional para modelagem e simulação de Redes Bayesianas.
São José, 2008. 98 folhas. Trabalho de Conclusão de Curso (Graduação em Engenharia de
Computação)–Centro de Ciências Tecnológicas da Terra e do Mar, Universidade do Vale do Itajaí,
São José, 2008.
O presente trabalho aborda o paradigma simbólico da Inteligência Artificial (IA), especificamente as
Redes Bayesianas. Como as Redes Bayesianas possuem um modelo matemático considerado NPDifícil e necessitam de um modelo conceitual adequado para que um sistema computacional raciocine
coerentemente, desenvolveu-se um ambiente computacional para modelagem visual e simulação de
Redes Bayesianas, onde o modelo matemático para propagação de evidências é abstraído. Antes do
desenvolvimento do ambiente computacional, verificou-se a necessidade de conhecer os princípios
básicos das Redes Bayesianas, como a regra fundamental da probabilidade, regra de Bayes, regra da
cadeia de Bayes, probabilidades condicionais e incondicionadas, evidências, redes causais, dseparação e algoritmos para propagação de evidência. Com intuito de não comprometer a
aplicabilidade real das Redes Bayesianas, necessita-se utilizar algoritmos eficientes para a propagação
de evidências, uma vez que considera-se esta tarefa NP-Difícil. A fim de atender ao critério de
precisão, com custo computacional aceitável, implementou-se o algoritmo exato Junction Tree e
como alternativa, também implementou-se o algoritmo de simulação amostragem Gibbs. Para a
implementação do ambiente computacional, inicialmente realizou-se a modelagem completa do
sistema no Enterprise Architect, com foco na minimização do acoplamento e generalização das
classes e componentes, para aumentar a reusabilidade. Depois de concebida a arquitetura do sistema,
realizou-se a codificação do modelo conceitual em linguagem C++, com o auxílio das bibliotecas
gráficas do QT. Após a implementação, determinou-se o processo de avaliação do sistema,
principalmente dos algoritmos. O processo de avaliação ocorreu através do emprego da Rede
Bayesiana da análise do merecimento do crédito. Com essa Rede Bayesiana, realizou-se ensaios
comparativos entre os algoritmos desenvolvidos e um algoritmo exato, proveniente de um software
comercial. Para o algoritmo amostragem de Gibbs realizou-se ensaios com intuito de verificar a
precisão das probabilidades posteriores e mensurar o seu desempenho computacional. Para o
algoritmo Junction Tree, realizou-se ensaios para verificação da acurácia do algoritmo, além da
descrição do processo de cálculo das probabilidade a posteriori.
Palavras-chave: IA, Redes Bayesianas, algoritmos para propagação de evidência.
ix
ABSTRACT
This present work approaches the symbolic paradigm of Artificial Intelligence (AI), especially the
Bayesian Networks. As the Bayesian Networks have a mathematical model considered NP-Hard and
they need a suitable conceptual model so that a computational system reasoning consistently, a
computational environment was developed to model, and simulate, Bayesian Networks,where, the
mathematical model to belief update is abstracted. Before the develop of computational environment,
the author found the necessity to know the basic principles of the Bayesian Networks, as the
probability's key rule, Bayes' rule, Bayes' chain rule, unconditional probability and conditional
probability, evidences, causal networks, d-separation and belief update algorithms. In order to avoid
jeopardizing the real applicability of the Bayesian Networks, the algorithms must be efficient, since
the belief update is considered NP-Hard. In order to meet the precision, with acceptable cost, the
Junction Tree algorithm was developed, and as alternative, the algorithm Gibbs Sampling. Before the
develop of computational system, the system was fully modeled in the Enterprise Architect, as focus
on minimizing the coupling and generalizing the classes and components to achieve better re
usability. After the system's architecture was designed, the conceptual model was codified in the
language C++, with the help of QT's graphical libraries. After the system's develop, the system was
assessed, specially the algorithms. The assessment occurred through the use of the Bayesian Network
to analysis of credit worthiness. With this Bayesian Network was realized comparative trials between
the algorithms developed and a commercial software algorithm. For the algorithm Gibbs sampling,
trials were realized in order to check the probability precision, and measure the computational
performance. For the Junction Tree algorithm was realized trials to check the accuracy, beyond the
process description of the probability's calculus
Keywords: AI, Bayesian Networks,belief update algorithms
x
1. INTRODUÇÃO
A Inteligência Artificial (IA) é um ramo da Ciência da Computação que é ao mesmo tempo
atual e antiga, pois a IA nasceu a partir de idéias filosóficas, científicas e tecnológicas herdadas de
outras ciências (BITTENCOURT, 1998).
A IA moderna para alguns autores divide-se em 5 paradigmas: simbólica, conexionista,
evolucionária, multi-agente e híbrido (BITTENCOURT, 1998).
Este trabalho segue o paradigma simbólico da IA, focado nas Redes Bayesianas. Schreiber
(2002), cita que:
“O raciocínio probabilístico é uma das formas de processar a incerteza. As redes
Bayesianas, baseadas no teorema de Bayes, podem ser utilizadas como mecanismo de
raciocínio incerto, alterando (atualizando) as probabilidades de ocorrência de um evento
posterior segundo a observação dos eventos presentes e anteriores”.
Orlandeli (2005, p. 57) define as Redes Bayesianas como:
“redes de conhecimento que descrevem um modelo do mundo real baseado em informações
de independência condicional entre os eventos, não sendo necessário usar uma enorme
tabela de probabilidades conjuntas para listar todas as combinações possíveis dos eventos”.
Redes Bayesianas são aplicadas nas áreas que incluem diagnóstico, investigação,
reconhecimento de imagens, planejamento e controle, reconhecimento de voz – resumidamente, quase
qualquer tarefa que requisite conclusões que são retiradas de pistas incertas e informações
incompletas (PEARL, 1988). Como casos de aplicações, podem-se citar:
•
DiagSD, Instituto de Telecomunicações de Portugal e Instituto Superior de Engenharia de
Lisboa, 2000. Sistema para diagnóstico de doenças do sono. Esse sistema indica as
prováveis doenças do paciente, conforme os sintomas relatados (MILHO e FRED, 2002);
•
ADVOCATE II, Ifremer, ATLAS Elektronik, University of Alcalá de Henares, 2004.
Utilizado em veículos aquáticos. Sistema para classificação ou decisão em situações de
erro, dados incompletos ou duvidosos, em problemas que envolvam análise sensitiva,
análise de conflitos e cálculo do valor da informação;
•
Delineamento de culturas agrícolas usando informações contextuais, INPE (Instituto
Nacional de Pesquisas Espaciais) e UFV (Universidade Federal de Viçosa), 2007.
Classificação de imagens em sensoriamento remoto. Este projeto utiliza Redes Bayesianas
na classificação de imagens, para aumentar a precisão da estimativa de área plantada de
cada cultura em questão (MELLO et al, 2007);
•
Spamassassin, Apache sistema Foundation, 2008. Sistema para reconhecimento de
Spam's. Este sistema é utilizado em servidores de correio eletrônico para detectar e
bloquear automaticamente Spam's; e
•
COMET, A collaborative tutoring system for Medical Problem-Based Learning, 2007.
Sistema para melhorar as habilidades de raciocínio clínico de estudantes, sem o uso de
tutor humano (SUEBNUKARN E HADDWY, 2004).
Em casos reais, como os descritos anteriormente, geralmente são aplicadas Redes Bayesianas
em ambientes computacionais, em função do modelo matemático envolvido, principalmente para o
cálculo da propagação de evidências nos nós (JENSEN, 2001).
Em razão do modelo matemático, utilizam-se GUI's (graphical user interface) para
modelagem de Redes Bayesianas genéricas que propiciam modelagem intuitiva, abstraem o modelo
matemático independentemente do tamanho e/ou complexidade da rede, facilitam a verificação e
validação do modelo, melhoram a produtividade, uma vez que os desenvolvedores focam-se apenas
no modelo conceitual da rede e na obtenção das probabilidades.
No mercado existem GUI's específicas para modelagem de Redes Bayesianas que permitem a
criação de redes de forma visual, realizam inferência, aprendizado, permitem escolha de algoritmos
para propagação de evidências, geração de código e exploração automática de todos os casos na rede
(JENSEN, 2001), contudo todas possuem limitações de uso em licenças gratuitas. Como exemplos de
ferramentas para modelagem de Redes Bayesianas pode-se citar: Hugin, GeNIe e NETICA
Application.
Com intuito de desenvolver a própria ferramenta (shell) para modelagem e simulação de
Redes Bayesianas, este TCC apresenta o desenvolvimento do sistema SRB (Simulador de Redes
Bayesianas). Com esse sistema, permite-se modelar Redes Bayesianas genéricas de maneira visual e
realizar ensaios a partir de evidências, onde abstrai-se o modelo matemático para propagação de
evidências, independentemente do tamanho e/ou complexidade da rede.
A licença de uso do sistema é gratuita, pois o objetivo de sua criação é oferecer um sistema
gratuito e de código “aberto” para uso educacional.
A execução deste projeto se justifica em nível de TCC para o curso de Engenharia de
Computação porque trata do desenvolvimento de um sistema que faz uso de tecnologias, conceitos e
teorias relevantes, como: linguagem de programação; orientação a objetos; ergonomia; uso de
técnicas da Engenharia de Software para modelagem e documentação; Redes Bayesianas; UML
(Unified Modeling Language) e teoria da probabilidade.
2
Outro ponto importante que merece destaque, é a implementação dos algoritmos amostragem
de Gibbs e Junction Tree. Ambos realizam os cálculos das probabilidades a posteriori em Redes
Bayesianas, mas eles diferem essencialmente, pois a amostragem de Gibbs trata-se de um algoritmo
de simulação com resultados aproximados, enquanto que o Junction Tree trata-se de um algoritmo
exato.
Este projeto não buscou implementar todas as funcionalidades disponíveis nos sistemas
comerciais, uma vez que existem vários sistemas, alguns com anos de desenvolvimento contínuo.
1.1. PROBLEMATIZAÇÃO
1.1.1. Formulação do Problema
A implementação prática de Redes Bayesianas somente é viável em sistemas computacionais
em razão dos cálculos necessários para a propagação de evidências. Para facilitar a modelagem e
simulação são utilizados GUI's específicas, que geralmente são proprietárias ou possuem limitações
de uso em versões gratuitas. Ainda como fatores estimulantes para o desenvolvimento da GUI,
ressalta-se que:
•
a maioria das GUI's comerciais para modelagem e simulação de Redes Bayesianas não
permitem a escolha do algoritmo de propagação de evidências; e
•
as aplicações comerciais não disponibilizam o código fonte dos algoritmos para
propagação de evidências.
1.1.2. Solução Proposta
Este trabalho compreende a implementação de uma GUI específica para a modelagem e
simulação de Redes Bayesianas para uso acadêmico, com licença gratuita que permita a escolha do
algoritmo de propagação de evidência e com código fonte “aberto”.
1.2. OBJETIVOS
1.2.1. Objetivo Geral
Desenvolver um sistema (shell) com ambiente visual que permita a criação e simulação de
Redes Bayesianas genéricas, onde o modelo matemático para propagação de evidências é abstraído.
1.2.2. Objetivos Específicos
Os objetivos específicos deste projeto de pesquisa são:
•
Estudar a teoria da probabilidade;
•
Estudar os algoritmos para propagação de evidências;
3
•
Analisar sistemas similares e bibliotecas para Redes Bayesianas;
•
Modelar a arquitetura do sistema;
•
Implementar (codificar) o sistema;
•
Avaliar o sistema através de um caso realístico; e
•
Elaborar a documentação.
1.3. Metodologia
São necessárias sete etapas a fim de executar esse projeto de forma que atinja os objetivos
específicos. São elas: (1) Estudar teoria, (2) Estudar algoritmos, (3) Analisar sistemas e bibliotecas,
(4) Modelar, (5) Implementar, (6) Avaliar e (7) Documentar.
1. Estudar a teoria: estudo da teoria de Redes Bayesianas para permitir a correta modelagem
e implementação do programa.
2. Estudar algoritmos: estudo de dois algoritmos para propagação de evidências em Redes
Bayesianas, especificamente os algoritmos: Junction Tree e amostragem de Gibbs;
3. Analisar sistemas e bibliotecas: visa a análise das funcionalidades e metodologias
oferecidas por alguns sistemas comerciais de modelagem e simulação de Redes
Bayesianas. Após verificadas as funcionalidades e metodologias, são pesquisadas e
analisadas, bibliotecas para simulação de Redes Bayesianas;
4. Modelar: Esta etapa visa a análise e modelagem da arquitetura do sistema com uso das
técnicas de Engenharia de sistema, linguagem UML e ferramenta automatizada para
modelagem de sistema;
5. Implementar: visa transformar o modo conceitual no sistema real, basicamente através de
codificação;
6. Avaliar: o sistema e os algoritmos de propagação de evidências serão avaliados através da
simulação de um caso realístico e resultados serão comparados com simulações realizadas
em ferramentas comerciais; e
7. Elaborar documentação: Esta etapa visa registar todo o processo pertinente à pesquisa
científica. A documentação deve permitir a outros pesquisadores a reprodução dos
resultados e testes realizados. Esta etapa ainda visa o desenvolvimento de um artigo
científico para posterior publicação.
4
1.4. Estrutura do trabalho
Esse TCC está dividido em cinco capítulos, que mantêm uma seqüência lógica e coerente. O
primeiro capítulo, a Introdução, além de uma visão geral do escopo do trabalho, também apresenta a
problematização (justificativa), objetivos (gerais e específicos) e a metodologia geral de trabalho.
No Capítulo 2, Fundamentação teórica, descrevem-se os conceitos relevantes de probabilidade
aplicados nas Redes Bayesianas, as definições teóricas, um exemplo de propagação de evidências
através das regras básicas da probabilidade e a descrição teórica, com exemplos, dos algoritmos
Junction Tree e amostragem de Gibbs. Também apresentam-se os resultados obtidos com a
implementação da versão não genérica do algoritmo amostragem de Gibbs.
No Capítulo 3, Desenvolvimento, apresenta-se a documentação e arquitetura do sistema
empregada na implementação. Demonstram-se os pacotes, componentes, classes, diagramas de
atividade e fluxogramas pertinentes ao projeto e implementação do ambiente computacional.
No Capítulo 4, Simulações, revelam-se e discutem-se os resultados obtidos com os ensaios
realizados nos algoritmos amostragem de Gibbs e Junction Tree. Apresentam-se ensaios para
determinação do erro das probabilidades a posteriori em cenários em que existem evidências
instanciadas ou não. Também verifica-se ensaios para determinação do desempenho computacional.
No Capítulo 5, Conclusões, apresentam-se os comentários finais do autor sobre todas as
atividades realizadas e resultados obtidos. Ainda propõem-se sugestões para trabalhos futuros.
5
2. FUNDAMENTAÇÃO TEÓRICA
Neste capítulo apresenta-se a parte relevante, para este TCC, dos fundamentos teóricos das
Redes Bayesianas. São apresentados: os fundamentos da probabilidade, redes causais e algoritmos
para propagação de evidências em variáveis discretas.
Este trabalho não abrange técnicas para diagramas de influência, aprendizado, análise
sensitiva, cálculo da “força das influências”, 2,50notação específica para redes temporais e variáveis
contínuas.
2.1. Probabilidade
Nesta seção mostram-se os fundamentos matemáticos necessários para o adequando
entendimento de Redes Bayesianas. Inicialmente são apresentadas as diferenças entre probabilidade
incondicional, condicional e conjunta para que então seja possível o adequado entendimento da regra
fundamental da probabilidade, do teorema de Bayes e da regra da cadeia.
2.1.1. Probabilidade incondicional
Conforme Russell e Norvig (2004, p. 455), “A probabilidade incondicional ou probabilidade a
priori é o grau de crença acordado para a proposição (variável) na ausência de quaisquer outras
informações”.
A representação de uma probabilidade incondicional associada a uma variável A é
demonstrada na Equação 1, onde xn representa a probabilidade associada ao evento n (JENSEN,
2001).
P A= x 1 , x 2 ,... , x n 
Equação 1
A probabilidade para cada evento xn da variável A é um número no intervalo de [0,1], onde a
distribuição das probabilidades para os estados obedecem à Equação 2. Em notação textual, a
somatória das probabilidades da variável A deve ser igual a 1 (JENSEN, 2001).
n
∑ P  Ax =1
1
n
Equação 2
2.1.2. Probabilidade condicional
Pearl (1988) afirma que as relações condicionadas são importantes, pois elas são compatíveis
com a organização do conhecimento humano.
Sempre que a declaração da probabilidade da variável A é condicionada por outras fatores
conhecidos, é dito que essa probabilidade é condicional. A notação utilizada para relação condicional
é demonstrada na Equação 3, que representa a seguinte frase: dado o evento bn da variável B, a
probabilidade do evento an da variável A é x (JENSEN, 2001).
P  A∣B=x
Equação 3
Na Tabela 1 é demonstrada a tabela de probabilidade condicional genérica uma vez dado a
Equação 3. Observa-se que a distribuição das probabilidades, para cada estado bn da variável B, deve
respeitar a Equação 2, onde a somatória das probabilidades devem ser iguais a 1 (JENSEN, 2001).
Tabela 1. Tabela de probabilidades condicionais
A\B
a1
...
ak
b1
x1,1
...
xk,1
b2
x1,2
...
xk,2
...
...
...
...
bn
x1,n
...
xk,n
O número de probabilidades condicionais da variável A condicionada a n variáveis, é dada
pela Equação 4, onde NEstados é o número de estados da variável. Se a variável A não for
condicionada, então essa variável não possui probabilidades condicionais, mas sim probabilidades
incondicionais, desta forma a Equação 4 não é aplicada (JENSEN, 2001).
n
NEstados  A∗∏ NEstados  pai n 
Equação 4
1
2.1.3. Probabilidade conjunta e regra fundamental da probabilidade
Probabilidade conjunta é a probabilidade dado que P (A = an) e P (B = bn) sejam verdadeiras
simultaneamente (RUSSELL e NORVIG, 2004).
A probabilidade conjunta das variáveis A e B é obtida através da regra fundamental do cálculo
da probabilidade, apresentada na Equação 5 (JENSEN, 2001). Na Equação 6 é demonstrada a
probabilidade conjunta no sentido contrário.
P  A , B=P  A∣B∗P  B
Equação 5
P  A , B=P  B∣A∗P  A
Equação 6
Diferentemente da probabilidade incondicional e condicional, a distribuição das
probabilidades condicionais é dada pela Equação 7, onde n é o número de estados da variável A e m é
o número de estados da variável B. Em linguagem textual: na tabela de probabilidade conjunta, a
soma de todas as probabilidades devem ser iguais a 1 (JENSEN, 2001).
7
n
m
1
1
∑ ∑ x n m=1
Equação 7
Observa-se que as P (A , B) são idênticas às P (B , A); a única diferença é a forma da
representação da tabela com as probabilidades conjuntas. Já nas probabilidades condicionais as P (A |
B) diferem das P (B | A) (JENSEN, 2001).
2.1.4. Regra de Bayes
A Regra de Bayes é a equação básica utilizada para propagar evidências nas Redes Bayesianas
(JENSEN, 2001).
Na Equação 8 e Equação 9 revela-se a dedução matemática da Regra de Bayes. Na Equação 8
é igualada a regra fundamental da probabilidade (Equação 5) e a regra fundamental da probabilidade
inversa (Equação 6), pois ambas resultam na P (A ^ B) (Russell e Norvig, 2001).
P  A∣B∗P  B=P  B∣A∗P  A
Equação 8
Através de operações matemáticas básicas na Equação 8 é obtida então a Regra de Bayes,
demonstrada na Equação 9 (JENSEN, 2001).
P  B∣A=
P  A∣B∗P  B
P  A
Equação 9
Na Equação 10 mostra-se que a Regra de Bayes pode ser condicionada a mais variáveis
(JENSEN, 2001).
P  B∣A ,C =
P  A∣B ,C ∗P  B∣C
P  A∣C 
Equação 10
2.1.5. Regra da cadeia
A regra da cadeia é uma metodologia para realizar a propagação de evidências em Redes
Bayesianas, quando é conhecida a probabilidade conjunta universal de todas as variáveis. O método
para o cálculo de P(U) é descrito na Equação 11. (JENSEN, 2001)
PU =∏ P Ai∣pais Ai 
Equação 11
A equação para propagação de evidências (crenças) e1,...,en, sobre o universo U de variáveis
numa Rede Bayesiana é demonstrada na Equação 12. (JENSEN, 2001)
8
PU , e=∏ P Ai∣pais Ai  ∏ ei
Equação 12
A distribuição conjunta universal é um método completo para responder consultas
probabilísticas para variáveis discretas, mas em razão do rápido crescimento da tabela P(U), dado o
aumento do número de variáveis, logo se torna completamente impraticável definir o vasto número de
probabilidades. (RUSSELL e NORVIG, 2004)
Ainda, a respeito da aplicabilidade da distribuição conjunta universal, Jensen (2001, p. 25) cita
que, “P(U) cresce exponencialmente com o número de variáveis do problema, e U não necessita ser
muito grande antes das tabelas tornarem-se demasiadamente grandes”.
2.2. Redes Bayesianas
As Redes Bayesianas provém um formalismo para o raciocínio a respeito de crenças parciais
sobre condições de incerteza. (PEARL, 1988)
A seguir apresentam-se as definições básicas sobre Redes Bayesianas conforme Russell e
Norvig (2004):
•
Um conjunto de variáveis que constituem os nós da redes;
•
Um conjunto de vínculos orientados conecta pares de nós. Se houver uma seta do nó X até
o nó Y, X será denominado pai de Y;
•
Cada nó Xi tem uma distribuição de probabilidade condicional P ( Xi | Pais(Xi) ) que
quantifica o efeito dos pais sobre o nó; e
•
O grafo não tem nenhum ciclo orientado (A Figura 1 apresenta um ciclo orientado).
Conforme Jensen (2001), Redes Bayesianas consistem basicamente:
•
Um conjunto de variáveis e um conjunto de arestas direcionadas entre variáveis;
•
Cada variável tem um conjunto finito de estados mutuamente exclusivos;
•
As variáveis em conjunto com as arestas direcionadas, formam um grafo acíclico
direcionado; e
•
Para cada variável A com pais B1,...,Bn, é associado uma tabela P (A | B1, ... , Bn).
2.2.1. Redes causais
Para este trabalho adota-se a representação de Redes Bayesianas em forma de redes causais
(grafos), pois é a linguagem de modelagem mais utilizada no meio comercial e acadêmico (JENSEN,
2001). O motivo da maior utilização das redes causais é que a representação facilita a quantificação
9
das conexões locais, de forma que os parâmetros conceitualmente significativos constituam uma base
de conhecimento global consistente (PEARL, 1988).
Nas redes causais os nós (círculos ou elipses) representam as variáveis do problema, sendo
que essas variáveis podem assumir n estados finitos mutuamente exclusivos. As arestas direcionadas
entre as variáveis representam a relação de causa (RUSSELL e NORVIG, 2004).
Somente é possível a modelagem de grafos acíclicos direcionados, pois nenhum método
matemático foi desenvolvido para suportar grafos cíclicos em redes causais (JENSEN, 2001).
Na Figura 1 dá-se a conhecer um grafo cíclico direcionado, no qual o ciclo é formado pelas
variáveis (nós) B, C, D e E. (JENSEN, 2001)
Figura 1. Um grafo cíclico. Isto não é permitido nas Redes Bayesianas
Fonte: Jensen (2001).
Nas redes causais as relações entre as variáveis são definidas conforme uma relação familiar
(JENSEN, 2001). Por exemplo, na Figura 2 a variável “Medidor de combustível” é definida como
filho da variável “Combustível”; já a variável “Combustível” é definida como pai das variáveis
“Medidor de Combustível” e “Partida do Motor”. Vale ressaltar que uma variável (nó) pode possuir
tanto n finitos pais com também n finitos filhos (RUSSELL e NORVIG, 2004).
Na Figura 2 revela-se a rede causal para o problema reduzido da falha da partida do motor de
um carro. O exemplo é apresentado para demonstrar como o modelo conceitual de um problema é
correlacionado com a metodologia das redes causais. Jensen (2001, p. 3) descreve o problema como:
De manhã, o carro não liga. A partida elétrica é ouvida, mas nada acontece. Pode haver
várias razões para o problema. Já que a partida é ouvida, então deve existir energia na
bateria. Portanto, as causas mais prováveis são que o combustível foi roubado durante a
noite ou que as velas do sistema de ignição estão “sujas”. Para descobrir se a causa do
problema é a falta de combustível, pode-se observar o medidor de combustível.
10
Figura 2. Rede causal para o problema reduzido da falha da partida do motor de um carro
Fonte: Adaptado de Jensen (2001).
Pearl (1988, p. 13) afirma que, “As redes causais não são dispositivos auxiliares previstos para
fazer o raciocínio mais eficiente, mas sim uma parte integral das semânticas da base de
conhecimento”.
A representação de Redes Bayesianas através de redes causais (grafos acíclicos direcionados)
facilita a compreensão do modelo conceitual da rede, pois sua representação é intuitiva. Mesmo
pessoas que somente conhecessem as características intrínsecas do problema, poderiam entender o
modelo conceitual, pois as redes causais representam o problema de maneira similar ao raciocínio
humano em circunstâncias que envolvem incertezas. (JENSEN, 2001)
2.2.2. Evidências
Nas Redes Bayesianas uma evidência é a crença de que determinada variável A esteja no
estado an. Suponha que a variável A possua estados a1, a2, a3 e a4. É descoberto que a variável A está
no estado a3 (uma crença), então a partir dessa premissa, pode-se determinar que a probabilidade dos
demais estados da variável A é 0, pois os estados de uma mesma variável são mutuamente exclusivos;
em outras palavras, somente pode ocorrer um estado por variável. (JENSEN, 2001)
Quando uma evidência é instanciada numa variável, ela é chamada de evidência
“pesada” (crença). Uma evidência é dita “leve”, quando um estado da variável possui probabilidade
1, porém não foi instanciada uma evidência na variável. A evidência “leve” pode ocorrer em
decorrência do modelo conceitual da rede e das evidências instanciadas em outras variáveis.
(JENSEN, 2001)
2.2.3. D-separação em redes causais
De acordo com Pearl (1988, p. 117):
“X, Y e Z são três conjuntos separados de nós num grafo direcionado acíclico, então Z é
dito d-separado de X e Y se ao longo de todos caminhos entre um nó de X e um nó de Y
11
existir um nó w satisfazendo uma das seguintes condições: w tem arestas convergentes e
seus descendentes estão em Z, ou w não tem arestas convergentes e w está em Z.”
A direção da aresta não é um fator limitante para os caminhos possíveis entre variáveis, uma
vez que a direção representa a relação de causa e não a orientação da influência entre as variáveis. As
variáveis que não são d-separadas, são chamadas de d-conectadas (JENSEN, 2001).
2.2.3.1. Conexões seriais
A Figura 3 demonstra uma rede causal com conexão serial entre as variáveis A, B e C.
Figura 3. Rede causal com conexão serial
Fonte: Adaptado de Jensen (2001).
Na Figura 3 a variável A influencia variável B e vice-versa, como B influencia a variável C e
vice-versa, contudo as variáveis A e C são influenciadas indiretamente através de B. Uma evidência
na variável C influencia as probabilidades da variável B, que por sua vez, influencia as probabilidades
de A. Por outro lado, uma evidência na variável B influencia A e C, mas depois o canal é bloqueado,
pois existe uma crença na variável B (evidência). Desta forma as variáveis A e C são consideradas dseparadas, pois em função da evidência em B, A e C não se influenciam. (JENSEN, 2001)
2.2.3.2. Conexões divergentes
Na Figura 4 demonstra-se uma rede causal com conexão divergente. A variável A influencia
B1 ... Bn e vice-versa. As variáveis B1 ... Bn se influenciam indiretamente através de A. Já, dado uma
evidência em A, ocorre a propagação desta em B1 ... Bn, contudo após essa propagação, A bloqueia o
canal de influência entre as variáveis B1 ... Bn. Desta forma é dito que B1 ... Bn são d-separados.
(JENSEN, 2001)
Figura 4. Rede causal com conexão divergente
Fonte: Adaptado de Jensen (2001).
12
2.2.3.3. Conexões convergentes
Na Figura 5 é demonstrado uma rede causal com conexão convergente.
Figura 5. Rede causal com conexão convergente
Fonte: Adaptado de Jensen (2001).
Numa situação convergente, como na Figura 5, as variáveis B1 ... Bn influenciam A e viceversa, mas as variáveis B1 ... Bn não se influenciam se não for atribuída uma evidência a A ou a um
dos descendentes. Dado uma evidência na variável A, ocorre a propagação nas variáveis B1 ... Bn e
depois o canal é aberto, assim as variáveis B1 ... Bn são d-conectadas (JENSEN, 2001)
2.2.4. Propagação de evidências
Conforme Russell e Norvig (2004, p. 490) a propagação de evidências “é calcular a
distribuição de probabilidades posteriores para um conjunto de variáveis de consulta, dado algum
evento observado – isto é, alguma atribuição de valores a um conjunto de variáveis de evidência.”
De acordo com Pearl (1988, p. 143), a propagação de evidências:
“promove a fusão e propagação de novas evidências e crenças, através da Rede Bayesiana,
de modo que cada proposição eventualmente será atribuída a uma medida consistente
conforme os axiomas da teoria da probabilidade”.
Nesta seção demonstra-se matematicamente como ocorre a propagação de evidências numa
Rede Bayesiana, através de um exemplo.
2.2.4.1. Modelagem conceitual do problema
Russell e Norvig (2004, p. 481) descrevem o problema como:
Você possui um novo alarme contra ladrões em casa. Este alarme é muito confiável na
detecção de ladrões, entretanto, ele também pode disparar caso ocorra um terremoto. Você
tem dois vizinhos, João e Maria, os quais prometeram telefonar-lhe no trabalho, caso o
alarme dispare. João sempre liga quando ouve o alarme, entretanto, algumas vezes
confunde o alarme com o telefone e também liga nestes casos. Maria, por outro lado, gosta
de ouvir música alta e às vezes não escuta o alarme.
Na Figura 6 vê-se o modelo conceitual do problema na forma de uma rede causal. Observa-se
que tanto o Ladrão como Terremoto são causas para que o alarme seja ativo, e o alarme a causa da
13
ligação do João e/ou da Maria, mas é atribuída incertezas às causas. Desta forma, apresenta-se,
similarmente, o problema descrito, na forma de uma rede causal. (RUSSELL e NORVIG, 2004)
Figura 6. Rede Bayesiana para o problema do alarme
Fonte: Adaptado de Russell e Norvig (2004).
Na modelagem da Rede Bayesiana devem ser consideradas as variáveis e estados que
possuem maior relevância para o problema, pois se forem inseridas muitas variáveis e estados
irrelevantes, o modelo pode tornar-se muito complexo e até, eventualmente, incoerente. (JENSEN,
2001)
Na Tabela 2 descreve-se o nome dos estados para cada variável da Rede Bayesiana da Figura
6 e o apelido da variável, entre parênteses, ao lado do nome da variável, o qual é utilizado para
diminuir o tamanho das expressões.
Tabela 2. Nomes das variáveis e estados
Estado 1
Estado 2
Ladrão (L)
Terremoto(T)
Alarme(A)
João(J)
Maria(M)
Sim
Não
Sim
Não
Ativo
Não Ativo
Ligou
Não Ligou
Ligou
Não Ligou
Fonte: Adaptado de Russell e Norvig (2004).
O número de estados iguais, para as variáveis do problema do alarme, são mera coincidência,
pois as diferentes variáveis podem possuir n finitos estados. Apenas existem recomendações para
facilitar a modelagem da Rede Bayesiana, pois o número de probabilidades condicionais necessárias
numa variável aumenta consideravelmente com o número de estados dos pais e do filho. Basta
observar a Equação 4, onde o número de probabilidades condicionais de uma variável é determinado
por um produtório. (JENSEN, 2001).
Depois de definidos os possíveis estados para as variáveis é necessário, então, definir as
probabilidades condicionais e incondicionais. A definição das probabilidades incondicionais como as
condicionais, pode ser dada através da freqüência (número de vezes que determinado estado ocorre
num grupo de amostras) ou pode ser simplesmente subjetiva (JENSEN, 2001).
14
Por exemplo, as probabilidades para a variável Alarme poderiam ser obtidas através de
informações quantitativas fornecidas pelo fabricante, mas a probabilidade de João ligar no caso do
alarme estar ativo é subjetiva, pois a verificação quantitativa dessa probabilidade é difícil de ser
obtida. A respeito da usabilidade de probabilidades subjetivas, Pearl (1988, p. 21) cita que:
“Se as pessoas preferem raciocinar qualitativamente, por quê deveriam as máquinas
raciocinar com números? Probabilidades são sumário de conhecimento que é deixado para
trás quando a informação é transferida para um alto nível de abstração. Os sumários podem
ser codificados logicamente ou numericamente; lógica aprecia as vantagens da parcimônia
e simplicidade, enquanto número são mais informativos e algumas vezes são necessários.”
Na Tabela 3 demonstram-se as probabilidades incondicionais para as variáveis Ladrão (L) e
Terremoto (T) conforme Russell e Norvig (2004). As probabilidades das variáveis não representam a
realidade brasileira, pois existe uma probabilidade maior de ocorrer um terremoto do que um roubo,
contudo essas probabilidades não foram definidas para realidade brasileira, mas sim para a realidade
do autor do problema. Desta forma fica evidente que a correta representação do modelo, depende do
contexto e do entendimento do problema.
Tabela 3. Probabilidades incondicionais para as variáveis: (a) Ladrão; (b) Terremoto
Ladrão (L)
Estado
Probabilidade
Sim
0,001
Não
0,999
Terremoto (T)
Estado
Probabilidade
Sim
0,002
Não
0,998
(a)
(b)
Fonte: Adaptado de Russell e Norvig (2004).
Na Tabela 4 expressam-se as probabilidades condicionais para a variável Alarme, dado que
essa variável possui 2 pais, ambos com 2 estados. Reitera-se que o número de probabilidades
condicionais para esta variável é dado conforme a Equação 4, que neste caso é igual a 8 (oito).
(RUSSELL e NORVIG, 2004)
Na Tabela 5 e Tabela 6 verificam-se as probabilidades condicionais para as variáveis João e
Maria, respectivamente, conforme Russell e Norvig (2004).
Tabela 4. P (A | L , T)
L Sim
A Ativo
A Não Ativo
T Sim
0,950
0,050
L Não
T Não
0,950
0,050
Fonte: Adaptado de Russell e Norvig (2004).
15
T Sim
0,290
0,710
T Não
0,001
0,999
Tabela 5. P (J | A)
A Ativo
0,90
0,10
J Ligou
J Não Ligou
A Não Ativo
0,05
0,95
Fonte: Adaptado de Russell e Norvig (2004).
Tabela 6. P (M | A)
A Ativo
0,70
0,30
M Ligou
M Não Ligou
A Não Ativo
0,01
0,99
Fonte: Adaptado de Russell e Norvig (2004).
2.2.4.2. Cálculo das probabilidades dos estados
Depois de definidas as probabilidades incondicionais e condicionais, faz-se necessário
calcular as probabilidades dos estados nas variáveis, pois deseja-se saber, qual a probabilidade do
estado ai da variável A.
Para as variáveis incondicionais Ladrão e Terremoto, a probabilidade do evento ai ocorrer é a
própria probabilidade do estado, pois essas variáveis não possuem nós pais. Já para os nós com
probabilidades condicionais, é preciso calcular a probabilidade conjunta do nó com seus respectivos
pais, para então ser determinado a probabilidade do evento ai (JENSEN, 2001).
A probabilidade do evento ai ocorrer numa variável A condicionada é determinada pela
marginalização (Equação 13), onde n é número de pais de A, mn é o número de estados do pai Bn e ai
é um estado de A (JENSEN, 2001).
m1
m2
mn
1
1
1
P A=ai=∑ ∑ ... ∑ P A=ai , B1=b m1 , B2=bm2 , ..., B n=bmn 
Equação 13
Para determinar as probabilidades dos estados da variável Alarme, é necessário calcular as
probabilidades conjuntas para as variáveis Ladrão, Terremoto e Alarme. Para tal, é utilizada a regra
fundamental da probabilidade (Equação 5). Entretanto a Equação 5 é utilizada para o cálculo da
probabilidade conjunta entre 2 variáveis, porém ela pode ser expandida. A Equação 14 mostra a
Equação 5 expandida para o cálculo da probabilidade conjunta de Alarme, Terremoto e Ladrão
(JENSEN, 2001).
P A ,T , L=P A∣T , L∗PT ∗P L
Equação 14
Para o cálculo das P (A ^ L ^ T) são obtidas as P (A | T ^ L) na Tabela 4, as P (L) e as P (T) na
Tabela 3. Na Equação 15 é demonstrada o cálculo para P (A Não Ativo ^ L Não ^ T Não).
16
P A Não Ativo , L Não ,T Não =P A Não Ativo∣LNão ,T Não ∗P LNão ∗P T Não 
P A Não Ativo , L Não ,T Não =0,999∗0,999∗0,998=0.996004998
Equação 15
Conforme a metodologia aplicada na Equação 15, é necessário calcular a probabilidade
conjunta para todas as combinações de estados. Na Tabela 7 são demonstradas as P (A ^ L ^ T) para
todas as combinações de estados. Uma vez calculada a probabilidade conjunta, é utilizada a Equação
13 para determinar as P (A). (JENSEN, 2001)
Tabela 7. P (A , L , T) e P (A)
L Sim
A Ativo
A Não Ativo
T Sim
1,9*10-6
1,0*10-7
T Não
9,4810*10-4
4,9900*10-5
L Não
T Sim
T Não
-4
5,7942*10
9,97002*10-4
-3
1,41858*10
0,996004998
P (A)
0,002526422
0,997473578
Para calcular as probabilidades dos estados da variável João, é necessário calcular as P ( J , A)
através da regra fundamental da probabilidade. Para o cálculo são obtidas as P (J | A) na Tabela 5 e as
P (A) na Tabela 7. Depois de calculada as P (J , A) é utilizada a Equação 13 para marginalizar Alarme
e obter as P (J). Os resultados são demonstrados na Tabela 8.
Tabela 8. P (J , A) e P (J)
J Ligou
J Não Ligou
A Ativo
0,0022737798
0,0002526422
A Não Ativo
0,0498736789
0,9475998991
P(J)
0,0521474587
0,9478525413
O cálculo das probabilidades dos estados de Maria é realizado de maneira similar,
inicialmente é utilizada a regra fundamental da probabilidade para o cálculo das P (M , A) para então
utilizar a Equação 13 e marginalizar Alarme, a fim de obter as P (M). Os resultados são demonstrados
na Tabela 9.
Tabela 9. P (M , A) e P (M)
M Ligou
M Não Ligou
A Ativo
0,00176849540
0,00075792660
A Não Ativo
0,00997473578
0,98749884222
P(M)
0,01174323118
0,98825676882
Na Figura 7 demonstram-se as Redes Bayesiana com as probabilidades dos estados nas
variáveis. Observa-se que a Rede Bayesiana já permite análise do problema, mesmo sem evidências
inseridas, pois é possível gerar conclusões como: João tem maior probabilidade de ligar do que Maria,
independentemente do alarme estar ativo ou não. (RUSSELL e NORVIG, 2004)
17
Figura 7. Rede Bayesiana com probabilidades dos estados
2.2.4.3. Propagação dada a evidência M Ligou
Para demonstrar os cálculos da propagação de evidência, é pressuposto que Maria ligou para
avisar que o alarme está ativo. A evidência neste caso é: Maria = Ligou, também denotada como M
.
Ligou
O processo da propagação da evidência é iniciado na variável Alarme, porque é única variável
diretamente conectada a variável Maria. Depois de propagado em Alarme, ocorre a propagação nas
demais variáveis da Rede Bayesiana. (RUSSELL e NORVIG, 2004)
Propagação na variável Alarme
Na Equação 16 apresenta-se a regra de Bayes adaptada para propagação da evidência M
Ligou
em Alarme. Para os cálculos são obtidas as P (M Ligou | Alarme) na Tabela 6, as P(A) na Tabela 7 e a P
(M Ligou) na Tabela 9.
P A∣e=M Ligou =
P M Ligou∣A∗P A
P M Ligou 
Somente é preciso utilizar a regra de Bayes quando M
Equação 16
, pois foi atribuído a esse estado a
Ligou
evidência. Como o estado M Ligou tem probabilidade 1, a P(M Não Ligou) = 0.
Na Equação 17 é demonstrado o cálculo da P (A Ativo | M Ligou).
P Aativo∣e=M Ligou =
P A Ativo∣e=M Ligou =
P M Ligou∣A ativo ∗P A ativo 
P M Ligou 
Equação 17
0,7∗0,0025264220
=0,150597001190945
0,01174323118
Na Tabela 10 visualizam-se as P(A | e = M
). É observado o aumento significativo da
Ligou
probabilidade do Alarme estar ativo, uma vez que Maria dificilmente liga erroneamente, contudo a
18
probabilidade ainda é baixa, uma vez que as probabilidades de existir roubo e/ou terremoto são
pequenas.
Tabela 10. P (A | e = M Ligou)
M Ligou
0,150597001190945
0,849402998809055
A Ativo
A Não Ativo
Propagação na variável João
Na Tabela 11 demonstram-se as P (J , A) e as P (J | e = MLigou). É utilizada a regra fundamental
da probabilidade para propagar a evidência na variável Ligação do João, através de Alarme. Para o
cálculo são obtidas as P (J | A) na Tabela 5 e as P (A) na Tabela 10.
Tabela 11. P (J , A) e P(J | e = M Ligou)
J Ligou
J Não Ligou
A Ativo
0,13553730107
0,01505970012
A Não Ativo
0,04247014994
0,80693284887
P(J | e = M Ligou)
0,17800745101
0,82199254899
Ainda na Tabela 11 observa-se que a probabilidade de João ligar aumentou, uma vez que a
probabilidade do alarme estar ativo também aumentou, contudo a probabilidade ainda é baixa, em
função das P(LSim) e P (TSim).
Propagação na variável Terremoto
Para o cálculo da propagação na variável Terremoto utiliza-se a Equação 18, que é a regra de
Bayes adaptada para propagação em Terremoto.
PT∣A=
P  A∣T ∗P T 
P A 
Equação 18
Para o cálculo são obtidas as P (A) na Tabela 10 e as P (T) na Tabela 3. As P (A | T) são
obtidas através da P (A , L , T). Para isso são necessárias duas etapas:
•
Primeira etapa: obter as P (A , T) das P (A , L , T) (Tabela 7). O procedimento é somar as
probabilidades conjuntas para os estados iguais de Terremoto, independentemente de
outras combinações, separadamente para cada estado do Alarme (JENSEN, 2001). Na
Tabela 12 são demonstrados os resultados para essa operação; e
Tabela 12. P (A , T)
A Ativo
A Não Ativo
T Sim
6,0*10-4
1,4*10-3
19
T Não
1,9*10-3
0,9961
•
Segunda etapa: obter a P (A | T) através da regra fundamental da probabilidade. Na
Equação 19 dá-se a conhecer a fórmula de maneira genérica. Na Tabela 13 são
demonstrados os resultados.
P  A∣T =
PA,T 
P T 
Equação 19
Tabela 13. P (A | T)
T Sim
0,2907
0,7094
A Ativo
A Não Ativo
T Não
0,0019
0,9981
Depois de calculadas as P (A | T) é possível utilizar a regra de Bayes adaptada para
propagação em Terremoto (Equação 18). Os resultados são demonstrados na Tabela 14.
Tabela 14. P (T | A) não normalizadas
A Ativo
0,0039
0,0129
T Sim
T Não
A Não Ativo
0,0017
1,1727
Os resultados apresentados na Tabela 14 precisam ser normalizados para 1. Na Equação 20
revela-se o método utilizado para normalizar os valores da Tabela 14, onde MAX é a soma dos
valores que são normalizados. (JENSEN, 2001)
Valor normatizado=
Valor∗1
MAX
Equação 20
Na Equação 21 é apresentado o cálculo para normalização de P (T Não | A Não Ativo).
PT Não∣A Não Ativo normalizado =
PT Não∣A Não Ativo ∗1
PT Não∣A Não Ativo PT Sim∣A Não Ativo 
PT Não∣A Não Ativo normalizado=
1,1727∗1
1,17270,0017
Equação 21
PT Não∣A Não Ativo normalizado=0,9986
Conforme a metodologia aplicada na Equação 21, é necessário realizar a normalização para as
outras probabilidades condicionais. Na Tabela 15 percebem-se os resultados normalizados.
Tabela 15. P (T | A ) normalizadas
T Sim
T Não
A Ativo
0,2301
0,7699
A Não Ativo
0,0014
0,9986
Para a obter as probabilidades de Terremoto, é necessário utilizar a regra fundamental da
probabilidade em P (T | A) normalizada a fim de obter as P (T , A). Uma vez determinada as P (T ,
20
A), é possível calcular as P (T | e = M
). O procedimento é somar todas as probabilidades
Ligou
conjuntas para cada estado de Terremoto (JENSEN, 2001). Demonstram-se os resultados na Tabela
16.
Tabela 16. P (T , A) e P (T | e = M Ligou)
T Sim
T Não
A Ativo
0,0347
0,1159
A Não Ativo
0,0012
0,8482
P(T | e = M Ligou)
0,0359
0,9641
Propagação na variável Ladrão
O cálculo da propagação na variável Ladrão é similar ao cálculo da propagação na variável
Terremoto. Desta forma revela-se o procedimento de maneira resumida.
Inicialmente, é necessário obter as P (A | L) com intuito de utilizar a regra de Bayes. O
processo para obter as P(A | L) é similar ao processo para obter as P (A | T). Primeiro é obtido as P (A
, L) através das probabilidades da Tabela 7, para então calcular as P (A | L) através da regra
fundamental da probabilidade. Nas Tabela 17 e Tabela 18 apresentam-se as P (A , L) e as P (A | L),
respectivamente.
Tabela 17. P (A , L)
A Ativo
A Não Ativo
L Sim
0,0010
0,0001
L Não
0,0016
0,9974
L Sim
0,000950000
0,000050000
L Não
0,001576422
0,997423578
Tabela 18. P (A | L)
A Ativo
A Não Ativo
Depois de calculada as P (A | L) utiliza-se regra de Bayes para calcular as P (L | A). Para os
cálculos são obtidas as P (A | L) na Tabela 18, as P(L) na Tabela 3 e as P(A | e = MLigou) na Tabela 10.
Na Tabela 19 especificam-se os resultados não normalizados. Na Tabela 20 apresentam-se as P (L |
A) normalizados.
Tabela 19. P (L | A) não normalizadas
L Sim
L Não
A Ativo
0,006308226541613
0,010467818001244
A Não Ativo
0,000058864873411
1,174264253126590
A Ativo
0,376025857912890
0,623974142087110
A Não Ativo
0,000050126641049
0,999949873358951
Tabela 20. P ( L | A) normalizadas
L Sim
L Não
21
Para obter as probabilidades incondicionais da variável Ladrão, dada a evidência, é
inicialmente aplicada a regra fundamental da probabilidade em P (L | A) normalizada a fim de obter
as P (L , A). Para obter as P (L | e = M Ligou) é necessário somar todas as probabilidades conjuntas para
cada estado de Ladrão, que é a definição textual da Equação 13 (JENSEN, 2001). Os resultados são
demonstrados na Tabela 21.
Tabela 21. P ( L , A ) e P (L | e = M Ligou)
L Sim
L Não
A Ativo
0,056628366571934
0,093968634619011
A Não Ativo
0,000042577719227
0,849360421089828
P(L | e = M Ligou)
0,056670944291161
0,943329055708839
2.2.4.4. Rede Bayesiana dada a evidência M Ligou
Na Figura 8 evidenciam-se as probabilidades dos estados nas variáveis após a inserção da
evidência M Ligou. Observa-se que essa evidência modificou as probabilidades dos estados nas demais
variáveis, de forma coerente com a formulação do problema e a sistemática do raciocínio humano.
Por exemplo, dado que Maria ligou, é intuitivo que existe o aumento considerável da probabilidade do
alarme estar ativo, uma vez que dificilmente Maria liga quando o alarme está Não Ativo. Em contra
ponto, a probabilidade de ocorrer terremoto e/ou roubo é muito baixa. Também é atribuída uma maior
probabilidade para João ligar, em decorrência da maior probabilidade do alarme estar ativo (causa e
efeito).
Figura 8. Rede Bayesiana para o problema do alarme dada a evidência MLigou
2.2.4.5. Propagação dada a nova evidência J Ligou
Numa Rede Bayesiana é permitido a inserção de mais de uma evidência na rede, desde que
sejam em diferentes variáveis, pois os estados numa mesma variável são mutuamente exclusivos.
(JENSEN, 2001)
Como continuação do caso do alarme, é pressuposto que João ligou depois de Maria, para
avisar que o alarme está ativo. Assim deve ser inserido na rede a nova evidência João = Ligou
).
Ligou
22
(J
Observa-se que a ordem da inserção das evidências não diferencia as probabilidades dos
estados nas variáveis, ao final da inserção, em métodos exatos. As probabilidades das variáveis
Alarme, Terremoto e Ladrão são as mesmas, tanto se forem inseridas as evidências M
respectivamente, como se forem inseridas as evidências J
eM
Ligou
Ligou
eJ
,
Ligou
, respectivamente. (JENSEN,
Ligou
2001)
Dada a nova evidência J
, é necessário propagá-la nas variáveis que são d-conectadas à
Ligou
João. A variável diretamente conectada a João é Alarme, desta forma é preciso propagar a evidência
em Alarme, que por sua vez propaga a evidência nas variáveis Terremoto e Ladrão. A variável Maria
não sofre propagação, pois a ela foi instanciada a evidência M Ligou. (JENSEN, 2001)
Propagação na variável Alarme
Para propagar a evidência em Alarme utiliza-se a regra de Bayes. Para o cálculo das P (A| e =
M Ligou , J ligou), são obtidas as P (J Ligou | A) na Tabela 5, as P (A | e = M Ligou) na Tabela 10 e a P (J Ligou |
e = M Ligou ) na Tabela 11. Na Tabela 22 observam-se os resultados.
Reitera-se que somente é necessário utilizar a regra de Bayes quando J Ligou, pois a este estado
foi atribuída a evidência.
Tabela 22. P (A | e = M Ligou , J Ligou)
P (A | e = M Ligou ^ J Ligou)
0,761413639164106
0,238586360835894
A Ativo
A Não Ativo
Propagação na variável Terremoto
O procedimento para propagar a evidência J
utilizado para propagar a evidência M
Ligou
Ligou
em Terremoto é similar ao procedimento
em Terremoto. Utiliza-se a regra fundamental da
probabilidade para obter as P (T , A). Para os cálculos são obtidas as P (T | A) na Tabela 15 e as P (A |
e = M Ligou , J Ligou) na Tabela 22.
Depois de calculado as P (T , A) somam-se as probabilidades conjuntas para cada estado de
Terremoto, com intuito de obter as P (T | e = M
Ligou
,J
). Na Tabela 23 são demonstrados os
Ligou
resultados.
Tabela 23. P (T , A) e P(T | e = M Ligou , J Ligou)
T Sim
T Não
A Ativo
0,175198354320410
0,586215284843696
A Não Ativo
P (T | e = M Ligou ^ J Ligou)
0,000339335001805
0,175537689322215
0,238247025834089
0,824462310677785
23
Propagação na variável Ladrão
Por último é preciso propagar a evidência J
Ligou
em Ladrão. O procedimento é similar à
propagação na variável Terremoto.
Inicialmente é calculado as P (L , A) através da regra fundamental da probabilidade. Para os
cálculos são obtidas as P (L | A) na Tabela 20 e as P (A | e = M
utiliza-se a Equação 13 para obter as P (L | e = M
Ligou
,J
Ligou
,J
) na Tabela 22. Então
Ligou
). Os resultados são demonstradas na
Ligou
Tabela 24.
Tabela 24. P (L , A) e P (L | e = M Ligou , J Ligou)
Alarme
L Sim
L Não
A Ativo
0,286311216893261
0,475102422270845
A Não Ativo
0,000011959532869
0,238574401303025
P(L | e = MLigou ^ JLigou)
0,286323176426129
0,713676823573871
2.2.4.6. Rede Bayesiana dada as evidências em M Ligou e J Ligou
Na Figura 9 demonstram-se as probabilidades dos estados dado que tanto Maria como João
ligaram. Observa-se o aumento significativo da probabilidade do alarme estar ativo, o qual condiz
com a formulação do problema e a sistemática do raciocínio, pois a chance de ambos ligarem
erroneamente são baixas. (RUSSELL e NORVIG, 2004)
Figura 9. Rede Bayesiana para o problema do alarme dada as evidências MLigou e JLigou
Ainda na Figura 9, constata-se que a probabilidade do roubo é maior que probabilidade do
terremoto. A princípio, isto aparenta ser uma contradição, pois a probabilidade a priori do roubo é
menor do que a do terremoto. Contudo ressalta-se que a probabilidade do alarme ser ativo em função
do terremoto é menor que a probabilidade do alarme ser ativo em função do Ladrão. Na Tabela 4 o
motivo desse comportamento é descrito, onde a P (AAtivo | LNão , TSim) = 0,29 e não 0,95, como na P
(AAtivo | LSim , TNão). Desta forma na maioria dos terremotos, o alarme permanece Não Ativo, enquanto
que na maioria dos roubos o alarme é ativo.
24
2.3. Algoritmos para propagação de evidências
Nesta seção apresentam-se dois algoritmos para o cálculo das probabilidades posteriores
(propagação de evidências) em Redes Bayesianas.
Anteriormente demonstrou-se a propagação de evidências no problema do alarme. Contudo a
resolução do problema não foi conduzida por uma metodologia formal (algoritmo); ela foi realizada
através dos princípios básicos, como a regra fundamental da probabilidade e a regra de Bayes,
mecanismos matemáticos necessários para a propagação de evidências. (PEARL, 1988)
Porém num sistema computacional necessita-se a utilização de um algoritmo eficiente, pois a
propagação de evidências é de fundamental importância na aplicabilidade das Redes Bayesianas.
(JENSEN, 2001)
Conforme Russell e Norvig (2004), os algoritmos para propagação de evidências em Redes
Bayesianas são divididos em 2 grupos:
•
exatos: resultam em probabilidades posteriores exatas. Exemplos: junction tree,
clustering, polytree, cutset conditioning method e relevance-based;
•
aproximados: resultam em probabilidades posteriores aproximadas. Exemplos: forward
sampling (logic sampling), likelihood weighting, gibbs sampling, algoritmo MetropolisHasting, self importance sampling, backward sampling e adaptive importance sampling
for Bayesian Networks(AIS-BN).
A princípio, é imperceptível a motivação para o desenvolvimento e/ou utilização de métodos
aproximados uma vez que existem métodos exatos. Contudo, em Redes Bayesianas de grande porte,
pode ocorrer que a quantidade de memória necessária, para métodos de propagação exatos, seja
impraticável, em função do hardware disponível. Neste sentido, utilizam-se algoritmos baseados em
simulações, que usualmente necessitam menor quantidade de memória (JENSEN, 2001).
2.3.1. Junction Tree
O algoritmo junction tree propõem uma metodologia que utiliza a regra da cadeia (Equação
12) em conjunto com a distribuição conjunta universal. Contudo, neste algoritmo propõem-se uma
metodologia que faz uso da lei distributiva, com intuito de reduzir e otimizar o tamanho das tabelas.
(JENSEN, 2001)
Conforme Russell e Norvig (2004, p. 496) a idéia básica do algoritmo junction tree é “unir nós
individuais da rede para formar nós de agrupamento, de tal modo que a rede resultante seja uma
poliárvore”.
25
Para exemplificar o algoritmo utiliza-se a Rede Bayesiana do problema do alarme,
demonstrada na Figura 6.
Entretanto, antes de construir a Junction Tree necessita-se verificar se a rede causal (grafo) do
problema é triangulado, pois a construção da Junction Tree necessita que o grafo seja triangulado.
Caso o grafo não seja triangulado, realiza-se o processo de triangulação. (JENSEN, 2001)
2.3.1.1. Grafos triangulados
Para determinar a triangularidade de grafos, inicialmente é necessário transformar o grafo
direcionado em um grafo não direcionado. Para isso são substituídas as arestas direcionadas por
arestas não direcionadas e são incluídas as conexões morais (JENSEN, 2001). Ainda o mesmo autor
descreve:
•
Conexões morais: são arestas não direcionadas que conectam dois ou mais nós pais que
possuem um filho em comum.
Na Figura 10 demonstra-se o grafo com a conexão moral para o problema do alarme. Observase que foi inserida apenas uma conexão moral, pois os únicos nós que atendem ao critério são os nós
Ladrão e Terremoto, os quais possuem o nó Alarme como filho em comum.
Figura 10. Grafo moral não direcionado para a rede causal do problema do alarme
Uma vez transformado o grafo em não direcionado e inseridas as conexões morais, é
necessário determinar os domínios para cada nó. Jensen (2001) descreve:
•
Domínios do grafo: deixe ɸ = {Ø1, ... , Øn} ser potenciais sobre o universo de variáveis U =
{A1, ... , An} com domínio Øi = Di. O domínio do grafo para ɸ é um grafo não direcionado
com as variáveis de U como nós e com conexões (arestas) entre pares de variáveis
membros do mesmo domínio Di. Em outras palavras, o domínio para a variável An é
composto por todos os nós vizinhos (nós conectados ao nó An) mais An .
Na Tabela 25 são demonstrados os domínios para cada variável (nó) da Figura 10.
26
Tabela 25. Domínio para cada variável
Domínio
ØL
ØT
Variável
Ladrão (L)
Terremoto (T)
ØA
Alarme (A)
ØM
ØJ
Maria (M)
João (J)
Integrantes
Ladrão, Terremoto, Alarme
Ladrão, Terremoto, Alarme
Ladrão, Terremoto, Alarme,
Maria e João
Alarme, Maria
Alarme, João
Conforme visto na Tabela 25, pode ocorrer a repetição de um mesmo domínio para várias
variáveis. Por exemplo o domínio de Alarme contém os domínios de Ladrão, Terremoto, João e
Maria, então, utiliza-se um único domínio para essas variáveis (JENSEN, 2001). O domínio resultante
do grafo é: Ø1 = {L,T,A,J,M}.
Uma vez determinados os domínios do grafo, é possível determinar se o grafo é triangulado.
Jensen (2001) define que “um grafo não direcionado é triangulado se, e somente se, todos os nós
possam ser eliminados por sucessivas eliminações de nós An simplicials”.
Para o correto entendimento do processo de verificação é necessário especificar as seguintes
definições: família do nó An, cliques, nós simplicials, eliminação de nós (variáveis), seqüência de
eliminações e fill-ins. Conforme Jensen (2001):
•
Família de AN é o conjunto de nós formados pelo nó AN mais seus vizinhos (nós
conectados por arestas ao próprio nó AN, também chamados de nós adjacentes);
•
AN é um clique se existem arestas que conectam todos os membros da família entre si;
•
Um nó AN é simplicial, se e somente se a família de AN constituir um clique;
•
É considerado uma eliminação de variável a exclusão (remoção) do nó e suas arestas do
grafo;
•
Um nó AN, somente pode ser eliminado do grafo sem inserção de fill-ins, se o nó AN for
simplicial;
•
Seqüência de eliminação é a ordem de eliminação dos nós do grafo; e
•
Fill-ins são arestas que são inseridas entre os nós adjacentes de AN, quando a variável AN é
eliminada, contudo ela não é simplicial. A introdução dessas novas arestas (fill-ins)
destaca o fato que, quando eliminado An, trabalha-se com um potencial sobre um domínio
que não está presente originalmente. Tenta-se evitar fill-ins, pois a junction tree construída
através de seqüências de eliminações que não introduzem fill-ins são menores do que as
geradas por seqüências de eliminações que introduziram fill-ins.
27
Para exemplificar os fill-ins, é eliminado do grafo da Figura 10 o nó não simplicial Alarme.
Quando um nó AN não simplicial é eliminado, são inseridos fill-ins entre os nós adjacentes de AN de
tal maneira que eles formem um clique. (JENSEN, 2001)
Figura 11. Grafo resultante dado a eliminação do nó Alarme
Para exemplificar todo o processo da verificação da triangularidade, retorna-se ao grafo da
Figura 10. É reiterado que o domínios resultante (ɸ) do grafo da Figura 10 é: Ø1 = {L,T,A,J,M}.
Como continuação, é necessário determinar os nós simplicials dos domínios de ɸ (JENSEN,
2001). Os nós simplicials para o domínio Ø1 são {L, T, M, J}.
Na Figura 12 é demonstrado o grafo após a eliminação das variáveis simplicials L, T e M.
Figura 12. Eliminação das variáveis Ladrão, Terremoto e Maria
Para eliminar todos os nós simplicials disponíveis, é ainda necessário eliminar a variável
João; desta forma restaria apenas Alarme no grafo.
Em alguns grafos, pode ocorrer que sobrem nós no grafo depois de eliminado todos os nós
simplicials dos potenciais de ɸ. Nestas ocasiões, é reiniciado o processo com o grafo G' resultante.
Então seriam determinados os novos domínios do grafo G', para então eliminar os novos nós
simplicials, e assim por diante até que todos os nós do grafo sejam eliminados. No caso do problema
do alarme, na reinicialização do processo, o nó Alarme seria simplicial e seria eliminado. Uma vez
eliminados todos os nós do grafo, ele é considerado triangulado. (JENSEN, 2001)
28
2.3.1.2. Grafos de domínios não triangulados
Entretanto, pode ocorrer em alguns grafos, que em tal ponto não existam mais nós simplicials
nos domínios para serem eliminados. Nestes casos, é necessário embutí-los num grafo triangulado
(JENSEN, 2001).
Para demonstrar o processo de transformação de um grafo não triangulado em triangulado,
considere o grafo da Figura 13. Na Tabela 26 mostram-se os domínios para cada variável e se o nó é
simplicial.
Figura 13. Grafo moral não triangulado
Fonte: Jensen (2001).
Tabela 26. Domínio para cada variável do grafo da Figura 13
ɸ
ØA
ØB
ØC
A,B,C,D
Domínio A,B,D
B,C,E
,E
Simplicial? Sim
Não
Sim
ØD
A,B,
D,F
Não
ØE
B,C,
E,G
Não
ØF
ØG
D,F,H, E,F,G,
I,G
I, J
Não
Não
ØH
ØI
ØJ
H,F
F,G,I
G,J
Sim
Sim
Sim
Na Figura 14 determina-se o grafo G' depois da eliminação dos nós simplicials, na seqüência
A, C, H, I e J.
Figura 14. Grafo moral G' não triangulado, depois da seqüência de eliminação A, C, H, I e J
Fonte: Adaptado de Jensen (2001).
Na Tabela 27 visualizam-se os domínios para o grafo G' da Figura 14. É observado que não
existem nós simplicials; desta forma, é necessário eliminar um nó não simplicial, que insere fill-ins.
(JENSEN, 2001)
29
Na Figura 14 existem várias diferentes ordens de eliminação e muitas delas produzem
diferentes grafos triangulados. É recomendado trabalhar para determinar os menores domínios.
Infelizmente, determinar a menor seqüência de eliminação é uma tarefa NP-Difícil. Contudo, existe
um bom algoritmo heurístico que tem provado dar relativos bons resultados. (JENSEN, 2001)
Tabela 27. Domínio para cada variável do grafo G'
DomínioVariável
ØB
ØD
ØE
ØF
ØG
Integrantes
B, D, E
B, D, F
B, E, G
D, F, G
E, F, G
Nó simplicial
Não
Não
Não
Não
Não
Jensen (2001, p. 185) descreve a heurística: “Eliminar repetidamente os nós simplicials, e se
não existem mais nós simplicials para serem eliminados, deve-se eliminar o nó X com sz (Fx)
mínimo.”
O sz (Fx) é demonstrado na Equação 22, onde i representa o número de nós da família da
variável V e n(Xi) representa o número de estados da variável Xi. Em linguagem textual, sz (V) é o
produtório do número de estados das variáveis da família de V. (JENSEN, 2001)
sz V =∏ i n X i 
Equação 22
Jensen (2001, p. 185) exemplifica a heurística:
“Deixe que o número de estados para a variáveis da Figura 14 sejam as seguintes: B tem 2
estados, D tem 4 estados, E tem 5 estados, F tem 6 estados e G tem 7 estados. Depois de ter
eliminados as variáveis A, C, H, I e J, é necessário eliminar um nó não simplicial. O sz(FB)
= 40, sz(FD) = 48, sz(FE) = 70, sz(F F) = 168 e sz(F G) = 210. É escolhido para ser
eliminado o nó B, o qual resulta na criação de um fill-in entre os nós D e E. Com essa nova
conexão, é obtido novos tamanhos sz(FD) = 120 e sz(FE) = 140. É eliminado o nó D e
adicionado um fill-in entre os nós E e F. Agora, o grafo é triangulado. A seqüência de
eliminação apresentada não é ótima.”
2.3.1.3. Construção da join tree
Jensen (2001, p. 172) define, “Se o grafo G não direcionado é triangulado, então os cliques de
G podem ser organizados em uma join tree”.
Como primeira etapa da construção da join tree é necessário organizar todos os cliques do
grafo G não direcionado triangulado, conforme a ordem de eliminação utilizada, para então
determinar os separadores. (JENSEN, 2001)
Na Figura 15 revelam-se graficamente os cliques, separadores e índices para o grafo não
direcionado triangulado da Figura 10, conforme a ordem de eliminação L, T, M, J e A. Os cliques são
30
representados em forma de elipses e os separadores em forma de retângulo. O conjunto de nós que
constituem os separadores são: os nós do clique menos os nós simplicials eliminados.
Jensen (2001, p. 166) descreve que a eliminação da variável X “corresponde a usar a lei
distributiva no produto. Ao invés de calcular o produto, é mantido os fatores numa “caçamba” e esses
não são multiplicados até que sejam forçados a tal.”
Os cliques e os separadores são denotados de acordo com o número de nós eliminados
(JENSEN, 2001). Por exemplo na Figura 15, o clique {L, T e A} é determinado V2 porque no grafo
foram eliminados 2 nós (L e T), já o clique {A, M} é V3, porque foram eliminados os nós L, T e M do
grafo.
Figura 15. Os cliques, separadores e índices resultantes da Figura 10
Constata-se que existem diferentes seqüências de eliminações possíveis para o grafo da Figura
10, por exemplo, a seqüência de eliminação M, J, T, L e A também poderia ser utilizada. Tanto a
seqüência de eliminação M, J, T, L e A, como a seqüência de eliminação utilizada na Figura 15 (L, T,
M, J e A), são consideradas seqüências de eliminações perfeitas. Uma ordem de eliminação é
considerada perfeita, quando a eliminação de todos os nós não introduz fill-ins; então o grafo moral é
originalmente triangulado (JENSEN, 2001).
Depois de determinados os cliques e separadores, faz-se necessário construir a join tree. O
procedimento é conectar os separadores (retângulos) aos cliques (elipses) com uma aresta não
direcionada, de tal forma que o conjunto de nós Vj (clique) contenha o conjunto de nós Si (separador).
Somente é conectado um separador a um clique, quando Si for menor do que Vj, em outras palavras, o
número que denota S tem que ser menor do que o número que denota V (JENSEN, 2001).
Jensen (2001, p. 176) descreve que “qualquer separador S divide o grafo em duas partes, e
todos os caminhos conectando as duas partes devem passar através de S”.
Cada separador somente é conectado a um clique, pois a estrutura resultante é uma árvore, e
nas estruturas em árvores, um nó somente pode ser acessado por um único caminho, não pode existir
múltiplos caminhos (JENSEN, 2001).
Na Figura 16 é demonstrada a join tree para os cliques e separadores da Figura 15.
31
Figura 16. Join tree para cliques e separadores da Figura 15
2.3.1.4. Marginalização e normalização
Antes de especificar o método de propagação de evidências em junction tree, propriamente
dito, é necessário especificar o que é normalização e marginalização. Normalização é tornar
proporcional as probabilidades conjuntas. O método de normalização já foi utilizado anteriormente
(na Equação 21 é demonstrado um exemplo de sua utilização). Marginalização é o nome dado para o
cálculo que realiza operação similar à Equação 23 (JENSEN, 2001).
m1 m2
mn
P A=ai=∑ ∑ ... ∑ P A=ai , B1=b m1 , B2=bm2 , ..., B n=bmn 
1
1
Equação 23
1
Verifica-se que a marginalização não precisa ocorrer necessariamente para uma variável, ela
pode ocorrer para um conjunto de variáveis, como demonstra Equação 24, onde n representa o
número da variável que pertence ao conjunto (variáveis diferentes de A e B) e m representa o número
do estado da variável Cn. As variáveis do conjunto (C1, ... , Cn) são ditas marginalizadas (JENSEN,
2001).
m1
m2
mn
1
1
1
P A=ai , B=b j =∑ ∑ ... ∑ P  A=ai , B=b j , C1=c m1 , C2=cm2 , ..., Cn =Cmn 
Equação 24
A marginalização representada na Equação 24 está na notação de somatório; contudo, ela
também pode ser representada na notação de projeção. Na Equação 25 evidencia-se a notação de
projeção, onde as variáveis que compõem o conjunto são marginalizadas, menos A e B (JENSEN,
2001).
  A , B
P A , B= A , B , C1 , ..., Cn 
Equação 25
Para exemplificar o processo de marginalização, considere a Tabela 28. Essa tabela demonstra
as P (A , L , T) e as P (A). É observado que P (A) é obtida através da marginalização, especificamente
conforme a Equação 26. O procedimento é somar todas as probabilidades conjuntas que contenha
Aativo, independentemente de outras combinações de estados. O processo também é realizado para ANão
.
Ativo
32
P Ak =∑i ∑ j P  A k ,T i , L j 
Equação 26
Tabela 28. P (A , L , T) e P (A)
L Sim
A Ativo
A Não Ativo
T Sim
1,9*10-6
1,0*10-7
T Não
9,4810*10-4
4,9900*10-5
L Não
T Sim
T Não
-4
5,7942*10
9,97002*10-4
1,41858*10-3 0,996004998
P (A)
0,002526422
0,997473578
A Equação 27 demonstra a marginalização da Equação 26 na notação de projeção.
P A= A , T , L A
Equação 27
2.3.1.5. Propagação na junction tree
Inicialmente é necessário construir a junction tree a partir da join tree. Na Figura 17 é
demonstrada a junction tree para a join tree da Figura 16. Na Figura 17 os separadores foram
expandidos para caixas de mensagens, onde as setas indicam a direção da mensagem (JENSEN,
2001).
Figura 17. Junction Tree para o problema do alarme
Para demonstrar o funcionamento da propagação de evidências na junction tree, considere que
foi inserida a evidência MLigou. A primeira etapa é localizar algum clique (elípse) que contenha a
variável M. Na Figura 17 o clique V3 contém M. Então é utilizada a Equação 28 que atualiza as
probabilidades conjuntas do clique V3 conforme a evidência MLigou. As P (A , MNão Ligou) são atribuídas
com valor 0, pois não existe a possibilidade do evento MNão Ligou ocorrer. Observa-se que podem ser
obtidas as probabilidades dos estados, sem necessariamente, existir evidencias instanciadas (JENSEN,
2001).
P A , M Ligou =P A∣M Ligou ∗P M Ligou 
Equação 28
Depois de calculadas as probabilidades conjuntas para o clique V3, é necessário propagá-la
pela junction tree. O procedimento é enviar mensagens (Ψx) para os separadores conectados ao clique
V3. As mensagens transmitidas através dos separadores S2 e S3 são demonstradas na Figura 18. O fato
de Ψ1 e Ψ2 serem a mesma mensagem é coincidência, já que a mensagem é a projeção das variáveis
do clique, em função das variáveis do separador (JENSEN, 2001).
33
Figura 18. Junction Tree com transmissão de mensagens, dado a evidência MLigou
Depois que V3 enviou as mensagens, o clique V2 recebe a mensagem Ψ1 e V4 recebe a
mensagem Ψ2. Receber a mensagem é multiplicar a tabela de probabilidade conjunta do clique pela
tabela de probabilidade conjunta transmitida pela mensagem. No caso da Figura 18, as mensagens
apenas contém as probabilidades da variável A, pois foi realizada a marginalização da variável M.
Após a multiplicação é necessário normalizar os cliques (JENSEN, 2001).
Caso os cliques V2 e/ou V4 possuíssem outros separadores conectados, V2 e/ou V4 também
deveriam encaminhar mensagens para os separadores vizinhos (menos o separador que enviou a
mensagem), e esses iriam recalcular suas probabilidades conjuntas e enviariam mensagens para
separadores vizinhos, e assim por diante, até que seja alcançado os cliques folhas e assim toda a
junction tree seria atualizada (JENSEN, 2001).
A evidência MLigou foi propagada por toda a junction tree. Então é permitido calcular as
probabilidades dos estados condicionados a evidência (JENSEN, 2001). Por exemplo, para descobrir
as P (L | e = MLigou), apenas seria necessário realizar V2 ↓L.
A junction tree permite a instância de várias evidências. Considere a nova evidência JLigou.
Inicialmente é localizado algum clique que contenha a variável J, no caso específico o clique V 4.
Então são recalculadas as probabilidades conjuntas do clique V4 e depois é enviada uma mensagem
para o separador S3. O clique V3 recebe a mensagem Ψ3, recalcula as probabilidades conjuntas,
normaliza-as e encaminha uma mensagem para o separador S2. O clique V2 recebe a mensagem Ψ4,
recalcula as probabilidades conjuntas e normaliza-as (JENSEN, 2001). Na Figura 19 é demonstrada a
junction tree após esses procedimentos.
Figura 19. Junction Tree com transmissão de mensagens, dado a evidência JLigou
Ao término da propagação é possível calcular, por exemplo, V2↓A, que resulta nas P (A | e =
MLigou , JLigou). É observado, que tanto V2↓A, V3↓A como V4↓A resultariam nas P (A | e = MLigou ,
JLigou).
34
2.3.2. Amostragem de Gibbs
O algoritmo de propagação de evidências, amostragem de Gibbs, é uma forma particularmente
conveniente da Cadeia de Markov Monte Carlo (CMMC) (RUSSELL e NORVIG, 2004).
Como a amostragem de Gibbs é uma variante da CMMC, as cadeias de Markov presentes em
cada variável da Rede Bayesiana devem ser ergódica (RUSSELL e NORVIG, 2004). Ainda Russell e
Norvig (2004, p. 503) definem ergódicas, “em essência, todo estado tem de ser acessível a partir de
qualquer outro estado e não pode haver nenhum ciclo estritamente periódico”.
O algoritmo faz uso da cobertura de Markov nas variáveis. Russell e Norvig (2004, p. 502)
descrevem que a cobertura de Markov em uma variável é constituída, “dos pais da variável X, os
filhos Y da variável X e os demais pais das variáveis Y”
2.3.2.1. Cálculo das probabilidades dos estados
O algoritmo é descrito juntamente com um exemplo. Para tal, considere a Rede Bayesiana do
problema do alarme, demonstrada na Figura 6. O fluxograma do algoritmo é demonstrado na Figura
20.
Inicialmente é necessário definir a cobertura de Markov para cada variável da Rede Bayesiana
(RUSSELL e NORVIG, 2004). Na Tabela 29 é demonstrada a cobertura de Markov para as variáveis
da Rede Bayesiana da Figura 6.
Tabela 29. Cobertura de Markov para as variáveis da Rede Bayesiana da Figura 6
Variável
Cobertura de Markov
L
TeA
T
LeA
A
L, T, J e M
J
A
M
A
Depois de determinada a cobertura de Markov das variáveis, é definido um vetor com os
estados aleatórios para cada variável da Rede Bayesiana (RUSSELL e NORVIG, 2004). Na Tabela 30
é demonstrado o vetor gerado com estados aleatórios, sem critério específico. Não existem evidências
instanciadas.
Tabela 30. Vetor com estados aleatórios para as variáveis
Variável
Estado
Ladrão
Não
Terremoto
Não
Alarme
Ativo
João
Não Ligou
Maria
Ligou
Depois de definida a amostra (vetor) inicial é necessário escolher uma variável da Rede
Bayesiana e calcular a probabilidade da variável condicionada à cobertura de Markov. Na Equação 29
é demonstrada a fórmula genérica para obtenção das probabilidades da variável A condicionada à
cobertura de Markov. Na fórmula, ai representa um estado da variável A, mb(A) representa as
variáveis da cobertura de Markov e Yj são variáveis filhos de A (RUSSELL e NORVIG, 2004).
35
Pai∣mb  A =Pai∣pais A∗∏Y ∈filhos A  P y i∣pais Y j 
j
Equação 29
Com intuito de deixar mais claro o entendimento da Equação 29, na Equação 30 é
demonstrada a Equação 29 adaptada para obtenção das P(L | AAtivo , TNão). É observado que os estados
das variáveis da cobertura de Markov são definidos pelo vetor de amostra (antigo e/ou atual), neste
caso a amostra antiga é definida na Tabela 30. Cada vetor gerado é considerado uma amostra
(RUSSELL e NORVIG, 2004).
P L∣A Ativo ,T Não =P L∗P A Ativo∣L ,T Não 
Equação 30
Figura 20. Fluxograma do algoritmo amostragem de Gibbs
Depois de calculada a probabilidade de L condicionada à cobertura de Markov, essas
probabilidades são normalizadas. Então é sorteado um número aleatório no intervalo de [1,0] e é
verificado em qual intervalo de valores o número sorteado é enquadrado (os limites dos intervalos são
36
determinados pelas probabilidades calculadas); e assim é determinado o estado para a variável L na
amostra atual (RUSSELL e NORVIG, 2004).
Desta maneira, é repetido o processo para todas as variáveis da Rede Bayesiana. É observado
que o estado da variável L já foi determinado na amostra atual, então os demais cálculos que
necessitarem do estado de L na amostra atual, utilizariam o estado da amostra atual, e não o estado da
amostra anterior. Caso não fosse ainda determinado o estado de L na amostra atual, seria utilizado o
estado da amostra anterior. (RUSSELL e NORVIG, 2004)
Então esse processo é repetido para n número de amostras. Ao término da amostragem, são
obtidas as freqüências dos estados nas variáveis. O procedimento é contar o número de vezes que os
estados das variáveis ocorreram, independentemente dos estados das outras variáveis na amostra.
Uma vez determinada a freqüência dos estados nas variáveis, elas são normalizadas e assim são
determinadas as probabilidades dos estados nas variáveis. (RUSSELL e NORVIG, 2004)
Para demonstrar na prática, que a amostragem de Gibbs permite a propagação de evidências
em Rede Bayesianas, o algoritmo foi implementado em linguagem C++, pois a amostragem de Gibbs
necessita de números aleatórios e quantidade significativa de cálculos, que seria inviável realizar
manualmente, ao contrário do outro algoritmo apresentado nesse trabalho.
Na Tabela 31 são demonstrados os resultados obtidos pela amostragem de Gibbs (10000
amostras) para a Rede Bayesiana da Figura 6 e o erro percentual em relação a probabilidade exata
esperada. Observa-se que para os estados com probabilidade exata esperada maior que 0,05, o método
da amostragem de Gibbs apresentou erros aceitáveis, contudo para os estados com probabilidade
exata esperada menor que 0,05, o erro aumenta significativamente.
Tabela 31. Amostragem de Gibbs e erro percentual
Variável
Ladrão
Terremoto
Alarme
João
Maria
Estado
Freqüência
Sim
Não
Sim
Não
Ativo
Não Ativo
Ligou
Não Ligou
Ligou
Não Ligou
22
9978
17
9983
40
9960
536
9464
123
9877
Probabilidade
(Gibbs)
0,0022
0,9978
0,0017
0,9983
0,0040
0,9960
0,05
0,95
0,01
0,99
37
Probabilidade
(Algorit. Exato)
0,001
0,999
0,002
0,998
0,00253
0,99747
0,05215
0,94785
0,01174
0,98826
Erro (%)
120
-0,12
-15
0,03
58,10
-0,15
-4,12
0,23
-14,82
0,18
2.3.2.2. Influência do número de amostras
Para determinar a influência do número de amostras na precisão numérica das probabilidades,
na Figura 21 e Figura 22 são demonstrados os gráficos do erro percentual versus o número de
amostras do primeiro e segundo ensaio, respectivamente, para os estados LSim e JLigou. Optou-se por
essas variáveis e estados, porque Lsim possui probabilidade exata esperada menor que 0,05 e JLigou
probabilidade exata esperada maior que 0,05.
O motivo da repetição da mesma simulação (Figura 21 e Figura 22), é que o algoritmo
amostragem de Gibbs apresenta erros percentuais significativamente diferentes entre distintos ensaios
sob mesmas condições.
Erro (%)
350
300
2 50
Erro (%) x Número de Amostras
300
2 00
1 50
1 00
50
0
-50
73,33
0
2 2,72
500
-20
-6,04
1000
0
7,96
-4,1 2
5000
-25
13,33
2,01
2 ,52
10000 1 5000 20000
0,74
30000
-15
-3,21
40000
Número de Amostras
-8
-10,67
-2 ,01
-0,06
34
-11
0,34
-0,21
29
8,33
2 ,73
0,03
50000 75000 1 00000 1 50000 200000 300000
Ladrão = Sim
João = Lig ou
Figura 21. Gráfico erro (%) versus número de amostras para LSim e JLigou (1º ensaio)
Erro (%) x Número de Amostras
100
80
Erro (%)
50
0
-50
-100
-19,46
20
-100
5,47
-2,97
5,85
0
4,95
20
4,99
6,67
-2 ,7 8
35
0
-0,38
-17,33
-0,75
1,5
-9
8,67
-0,63
-1 ,1 7
5,5
0,7 5
26
1,94
-100
-150
500
1 000
5000
10000 1 5000 2 0000
30000
40000
50000
Número de Amostras
75000 1 00000 1 50000 200000 300000
Ladrão = Sim
João = Ligou
Figura 22. Gráfico erro (%) versus número de amostras para LSim e JLigou (2º ensaio)
Observa-se na Figura 21 e Figura 22 a grande discrepância entre os erros percentuais do
estado Lsim para os diferentes ensaios. Para diminuir a influência da instabilidade dos resultados entre
um ensaio e outro, na Figura 23 é apresentado o gráfico do erro versus o número de amostras para Lsim
e JLigou, porém o valor do erro percentual é a média de 31 simulações distintas (31 simulações para
cada número de amostras).
38
Erro Médio (%) x Número de Amostras
Erro Médio (%)
300
257,19
250
200
150
143,66
100
50
0
-50
-19,04
6,2 4
500
2,64
1000
4,83
5000
27,98
1
0,95
1 0000
-17,84
-2 ,03
15000
-0,34
20000
10,43
-1 ,18
30000
7,35
24,22
-2,61
40000
Número de Amostras
0,91
-2,81
-0,7
2,33
1 ,06
50000
7 5000
100000
Lad rão = Sim
Joã o = Ligou
Figura 23. Gráfico erro médio (%) versus número de amostras para LSim e JLigou
Na Figura 23 constata-se que na média os ensaios com menores números de amostras
apresentam os maiores erros percentuais, especialmente para o estado LSim, pois o valor exato
esperado para este estado é pequeno (0,001). Para o estado JLigou é observado uma pequena diminuição
do erro com o aumento do número de amostras.
Ressalta-se que a diminuição do erro não é proporcional ao aumento do números de amostras,
mas o custo computacional aumenta exponencialmente com o número de amostras. Então o número
de amostras utilizadas para a obtenção do melhor custo/benefício deve ser um número não tão
pequeno, para poder atender ao critério de precisão numérica, porém nem tão grande, para poder
atender ao critério de desempenho computacional. Para este caso específico, é observado que um
número de amostras entre [5000, 15000] atinge o melhor custo/benefício.
2.3.2.3. Cálculo das probabilidades dos estados dado evidências
No caso de inserção de evidências na Rede Bayesiana, o procedimento para determinar as
probabilidades dos estados nas variáveis pouco difere. A diferença é que inserido um conjunto de
evidências (ai , bj, cj, ...) numa numa Rede Bayesiana com n variáveis (A, B, C, ...), o primeiro vetor
de amostra é iniciado com A = ai , B = bj, C = cj, ..., e não com um estado aleatório. Esses estados
permanecem os mesmos até o fim da amostragem. Já as variáveis que não possuem evidências, são
iniciadas com estados aleatórios e o algoritmo é aplicado normalmente. (RUSSELL e NORVIG,
2004)
Russell e Norvig (2004, p. 502) consideram que o fato de um estado a i instanciado permanecer
o mesmo até o fim da amostragem, como uma vantagem, pois o algoritmo “vagueia ao acaso pelo
espaço de estados – o espaço de atribuições completas possíveis, invertendo uma variável de cada
vez, mas mantendo fixas as variáveis de evidência”.
39
Para exemplificar, na Tabela 32 são demonstradas as probabilidades dos estados obtidas pelo
método da amostragem de Gibbs (10000 amostras) e erro percentual em relação a probabilidade exata
esperada.
Percebe-se na Tabela 32 que a amostragem de Gibbs obteve as probabilidades dos estados
com precisão numérica aceitável. Como as probabilidades exatas esperadas são maiores do que 0,05,
é observado o mesmo comportamento da simulação sem evidência, onde o erro era menor para o
estado em que a probabilidade exata esperada é maior que 0,05. Neste ensaio, não é possível afirmar
que necessariamente a inserção de evidência melhora a precisão numérica, uma vez que não existem
probabilidades exatas esperadas menores que 0,05.
Tabela 32. Amostragem de Gibbs e erro percentual, dada as evidências MLigou e JLigou
Variável
Ladrão
Terremoto
Alarme
João
Maria
Estado
Freqüência
Sim
Não
Sim
Não
Ativo
Não Ativo
Ligou
Não Ligou
Ligou
Não Ligou
2917
7083
1711
8289
7639
2361
10000
0
10000
0
Probabilidade
(Gibbs)
0,2900
0,7083
0,1711
0,8289
0,7639
0,2361
1
0
1
0
Probabilidade
(Algorit. Exato)
0,28632
0,71368
0,17554
0,82448
0,76141
0,23859
1
0
1
0
Erro (%)
1,29
-0,75
-2,53
0,54
0,33
-1,04
0
0
0
0
2.3.2.4. Influência do número de amostras dado evidências
Nesta seção realiza-se o estudo da influência do número de amostras no erro das
probabilidades, em situações que existem evidências instanciadas. Para os ensaios são utilizadas as
evidências LNão e TSim.
Em função da existência de grandes discrepâncias entre o erro em diferentes simulações sem
evidências instanciadas, na Figura 24 e Figura 25 são apresentados os gráficos do erro percentual
versus o número de amostras do primeira e segundo ensaio, respectivamente, para os estados LNão e
TSim. O objetivo é confirmar ou não o mesmo comportamento em situações em que existam evidências
instanciadas.
Verifica-se, na Figura 24 e Figura 25, que a instabilidade, entre ensaios distintos, é similar aos
ensaios sem evidências, porém é ressaltado que as probabilidades exatas esperadas para LNão e TSim são
maiores do que 0,05, região que também demonstrou maior estabilidade entre ensaios diferentes
quando não existem evidências instanciadas.
40
Erro (%) x Número de Amostras
20,00 18,49
15,00
Erro (%)
10,00
5,00
-7,71
0,00
3,97
-5,00
0,18
-0,82
-3,60
3,70
3,19
2,83
-1,22
0,62
-1 ,36
3,13
0,69
0,36
0,95
-1,96
0,37
0,17
0,49
-0,2 8
0,61
0,1 9
0,42
-0,2 9
0,25
-0,01
0,2 6
-1 0,00
500
1000
5000
10000 1 5000 20000 30000
40000 50000 75000 1 00000 150000 200000 300000
Número de Amostras
Terremoto = Sim
La drã o = Não
Figura 24. Gráfico erro (%) versus número de amostras para TSim e LNão (1º ensaio)
Erro (%) x Número de Amostras
Erro (%)
4,00
1,88
2 ,00 -1 1,13
0,45 1,09 0,69 -0,53 -0,28 -0,64 -0,04
-0,31 -1,67 0,72 0,64 -3,13
0,00
0,15
0,02
0,1 7
0,1 1
-0,01
0,1 4 -0,1 2
-0,09 0,02
0,89
-0,30
-2 ,00
-0,81
-0,96
-4,00
-6,00
-6,68
-8,00
-1 0,00
-12 ,00
500
1000
5000 10000 15000 2 0000 30000 40000 50000 75000 100000 1 50000 200000 300000
Número de Amostras
Terremoto = Sim
La drã o = Não
Figura 25. Gráfico erro (%) versus número de amostras para LNão e TSim (2º ensaio)
Com intuito de evitar ensaios tendenciosos e mitigar a instabilidade entre diferentes
simulações, na Figura 26 é demonstrado o gráfico do erro versus o número de amostras para os
estados LNão e TSim, porém o valor do erro percentual é a média de 31 simulações distintas.
Erro Médio (%) x Número de Amostras
Erro Médio (%)
5,00
4,00
3,00 2,09
2 ,00
1 ,00
0,00
-1 ,00
-2 ,00
2,13
0,26
4,66
500
-0,86
1000
-0,12
5000
-0,05
-0,05
0,74
10000
0,21
-0,06
15000
0,49
0,13
-0,94
20000
30000
Número de Amostras
-0,07
-0,21
-0,16
-0,83
40000
50000
Ladrão = Não
-0,02
0,12
-0,22
-0,47
7 5000 1 00000
Terremoto = Sim
Figura 26. Gráfico erro médio (%) versus número de amostras para TSim e LNão
Na Figura 26 confirma-se o comportamento do método da amostragem de Gibbs conforme a
variação do número de amostras. Com pequeno número de amostras, o método apresentada os
maiores erros percentuais, contudo a diminuição do erro não é proporcional ao incremento do número
de amostras, então reitera-se a importância do adequado número de amostras, pois não pode ser tão
41
pequeno, para poder atender ao critério de precisão, contudo nem tão grande, para poder atender ao
critério de desempenho computacional.
Também é possível comparar o erro médio para estados com probabilidade exata esperada
maior que 0,05. Observa-se que os ensaios apresentam erros médios similares, tanto sem como com
evidências, desta forma é possível afirmar que o método da amostragem de Gibbs calcula
probabilidades, na média, com precisão numérica similar em ambas circunstâncias. No ensaio sem
evidência o erro médio máximo foi 6,24% enquanto que no ensaio com evidência instanciada, o erro
médio máximo foi de 4,66%.
42
3. DESENVOLVIMENTO
Neste capítulo apresenta-se a documentação da arquitetura do sistema e características
importantes da implementação. O capítulo é dividido em três seções: visão de negócio, visão de caso
de uso e por fim a visão dinâmica do sistema.
3.1. Visão de negócio
Esta seção descreve sucintamente o problema envolvido, o objetivo macro a ser alcançado, a
situação no início e a desejada ao término do projeto.
3.1.1. Apresentação do sistema
Nome do sistema
SRB (Simulador de Redes Bayesianas).
Objetivo do sistema
Desenvolver um sistema (shell) com ambiente visual que permita a criação e simulação de
Redes Bayesianas genéricas, onde o modelo matemático para propagação de evidências é abstraído.
Situação no início do projeto
A Universidade não possui nenhum projeto de sistema para modelagem e simulação de Redes
Bayesianas.
Situação desejada
Existência de um sistema de modelagem e simulação de Redes Bayesianas desenvolvido na
Universidade, tanto para iniciar a produção de uma GUI completa (pois grafos de influência, redes
temporais, estados contínuos, entre outros tópicos não são abordados nesse TCC), como também
permitir que sejam desenvolvidos outros trabalhos a fim de estender o sistema.
3.1.2. Modelo de Requisitos
Nesta seção apresenta-se o detalhamento das necessidades que o sistema precisa atender ao
seu término. Os requisitos são divididos em funcionais, não funcionais e regras de negócios. Todos
eles apresentam a situação, que suscita a relação entre a implementação realizada versus as
características proposta, e a importância, que quantifica sua importância em prol do projeto.
3.1.2.1. Requisitos funcionais
REF 001 Construção de Redes Bayesianas visuais
Situação: 90% implementado e validado.
Importância: Crítico. Representa uma funcionalidade essencial do ambiente computacional.
Comentários: Não foi implementado o ajuste do tamanho dos objetos através da interface gráfica.
O sistema deve criar Redes Bayesianas em forma de redes causais (grafos). Propor um
ambiente em que possam ser: movimentadas as variáveis (elípses, barras gráficas); inseridas arestas
direcionadas entre variáveis; movimentado um conjunto de objetivos visuais selecionados; alterados
os nomes das variáveis; alteradas as configurações de fonte; alterado o tamanho dos objetos; e
excluídos um ou grupo de objetos visuais.
REF 002 Abrir/Salvar a Rede Bayesiana
Situação: Não Implementado.
Importância: crítica. Para fins de utilização prática, a opção de salvar e abrir Redes Bayesianas é
fundamental para o ganho de produtividade.
Razão: não houve tempo hábil e em função deste requisito possuir caráter secundário em relação ao
objetivo marco, optou-se por implementar os requisitos mais importantes.
O sistema deve permitir que seja aberto ou salvo uma Rede Bayesiana modelada.
Deve ser salvo as propriedades visuais da rede causal, as probabilidades inseridas nas variáveis,
configurações da rede, nome das variáveis, as arestas, enfim, todas as informações que foram
atribuídas à Rede Bayesiana. Já para abrir uma Rede Bayesiana, “carrega-se” para o sistema todas as
informações salvas no arquivo.
REF 003 Modos de representação visual da Rede Bayesiana
Situação: Implementado e validado
Importância: crítico. Representa o meio principal para visualização das probabilidades a posteriori.
O sistema deve permitir a visualização da Rede Bayesiana na forma de uma rede causal, como
também, numa forma que seja possível ver as probabilidades dos estados no próprio grafo (barra
gráfica, por exemplo).
REF 004 Inserção de evidências
Situação: Validado.
Importância: crítico. Permite a simulação de casos.
O sistema deve permitir a inserção de evidências na Rede Bayesiana de maneira visual.
REF 005 Modos para cálculo das probabilidades dos estados.
Situação: Validado.
Importância: médio. Ferramenta para aumento da produtividade na simulação.
44
O sistema deve possuir duas maneiras de propagação de evidências:
•
automática: a cada alteração na Rede Bayesiana, são determinadas as probabilidades dos
estados.(inserção/remoção de evidências, alteração de probabilidades condicionais ou
incondicionais, inserção de novas variáveis, etc); e
•
manual: somente são calculadas as probabilidades dos estados quando requisitado.
REF 006 Inserção/remoção estados das variáveis
Situação: Parcialmente implementado e validado.
Importância: crítico. Permite a criação de Redes Bayesianas genéricas.
Comentários: as bibliotecas dos algoritmos suportam a inserção e remoção de estados das variáveis,
entretanto a interface com o usuário para modificação está incompleta.
Razão: sem tempo hábil.
O sistema deve permitir que em qualquer variável sejam inseridos n estados. Também deve
permitir a remoção de estados.
REF 007 Probabilidades condicionais/incondicionais
Situação: Parcialmente implementado e validado.
Importância: crítico. As Redes Bayesianas são compostas por probabilidades.
O sistema deve propor uma método para inserção das probabilidades condicionais ou
incondicionais nos estados. No caso da variável ser condicionada, o sistema deve automaticamente
combinar os estados dos pais e da variável, na forma de uma tabela.
REF 008 Visualização de várias Redes Bayesianas simultâneas
Situação: Validado
Importância: baixo. Permite a simulação e/ou modelagem de várias Redes Bayesianas.
O sistema deve permitir que sejam aberta n Redes Bayesianas distintas numa mesma seção do
sistema.
REF 009 Opções de Zoom
Situação: Validado.
Importância: média. Ferramenta que auxilia a visualização dos nós da Rede Bayesiana.
O sistema deve implementar opções de zoom para o ambiente visual de desenho da Rede
Bayesiana.
45
REF 010 Opção de desfazer/refazer/copiar/colar
Situação: Não implementado.
Importância: média. Otimiza o processo de modelagem.
Razão: Optou-se por não implementar esse requisito em função do tempo hábil insuficiente e por
tratar-se de uma necessidade de caráter secundário em relação ao objetivo.
O sistema deve implementar opção de desfazer/refazer/copiar/colar para o ambiente visual de
desenho da Rede Bayesiana.
REF 011 Visualizar variáveis da Rede Bayesiana numa árvore
Situação: Não implementado.
Importância: baixa. Meio para visualização das variáveis, estados e probabilidades.
Razão: Optou-se por não implementar esse requisito em função do tempo hábil insuficiente e por
tratar-se de uma necessidade de caráter secundário em relação ao objetivo.
O sistema deve permitir a visualização das variáveis da Rede Bayesiana numa árvore. Nesta
árvore também percebe-se as probabilidades dos estados. (TreeView)
REF 012 Algoritmos de propagação de evidências
Situação:
Amostragem de Gibbs: implementado e validado.
Junction Tree: implementado, entretanto tem funcionamento parcial. Motivo:
encontrou-se dificuldades quando o grafo possui domínio não triangulado.
Importância: crítica. Os algoritmos permitem os cálculos das probabilidades a posteriori.
O sistema deve permitir a seleção do algoritmo de propagação de evidência desejado.
Algoritmos que deverão ser implementados:
•
Exato: junction tree;
•
Aproximado: amostragem de Gibbs.
REF 013 Configurações para algoritmos
Situação: Validado.
Importância: crítica. Permite a personalização das configurações dos algoritmos.
O sistema deve permitir que sejam alterados parâmetros de configuração dos algoritmos de
propagação de evidências (por exemplo: número de amostras para algoritmo aproximado).
46
REF 014 Uso de abas flutuantes/ancoradas
Situação: Validado.
Importância: média. Permite a personalização da interface gráfica.
O sistema deve implementar o uso de abas e janelas flutuantes/ancoradas.
REF 015 Personalização de objetos visuais
Situação: Validado.
Importância: baixa. Permite a personalização do grafo.
O sistema deve permitir a personalização dos objetos visuais da Rede Bayesiana. Exemplo:
cores, largura das linhas, cor de fundo, etc.
REF 016 Estatísticas da Rede Bayesiana
Situação: Não implementado.
Importância: baixa. Mensura a grandeza da Rede Bayesiana.
Razão: Optou-se por não implementar esse requisito em função do tempo hábil insuficiente e por
tratar-se de uma necessidade de caráter secundário em relação ao objetivo.
O sistema deve mostrar as estatísticas da Rede Bayesiana (numero de nós, número de arestas e
número de estados).
REF 017 Inserção de comentários
Situação: Validado.
Importância: baixa. Documentação o significado das variáveis ou outras informações relevantes.
O sistema deve permitir a inserção de comentários nas variáveis e no ambiente visual da Rede
Bayesiana.
REF 018 Alternar entre Redes Bayesianas distintas
Situação: Validado.
Importância: baixa. Simulação de várias Redes Bayesianas simultaneamente.
O sistema deve permitir a alternação da Rede Bayesiana que está sendo modelada e/ou
simulada.
REF 019 Alinhamento de nós
Situação: Validado.
Importância: média. Ferramenta para organização dos nós da Rede Bayesiana.
47
O sistema deve permitir o alinhamento de um grupo de nós selecionados da Rede Bayesiana.
Modos: alinhar para esquerda;
centralizar verticalmente;
alinhar para direita; alinhamento superior; alinhamento inferior;
centralizar horizontalmente;
distribuir verticalmente e
distribuir
horizontalmente;
REF 020 Posicionamento das janelas das distintas Redes Bayesianas
Situação: Validado.
Importância: baixa.
O sistema deve permitir forma de auto organizar as janelas das diferentes Redes Bayesianas
abertas. Modos: distribuição vertical; distribuição horizontal; auto organizar (organiza janelas na
forma de uma matriz) e distribuição em cascata;
3.1.2.2. Requisitos não funcionais
RNF 001 Sistema Operacional Windows XP e Vista
Situação: Validado.
O sistema deve funcionar nos sistemas operacionais Windows XP e Windows Vista.
RNF 002 Implementação em C++
Situação: Validado.
O sistema deve ser codificado em linguagem C++.
RNF 003 Uso das bibliotecas do QT
Situação: Validado.
O sistema deve usufruir dos recursos gráficos oferecidos pelas bibliotecas de código aberto do
QT (TrollTech), principalmente para interface gráfica.
3.1.2.3. Regras de negócio
RN 001 Verificação de grafos cíclicos
Situação: Não implementado.
O sistema não deve permitir a modelagem de grafos cíclicos.
RN 002 Verificar probabilidades
Situação: Não implementado.
Razão: A implementação dessa regra de negócio não foi executado em razão da interface gráfica para
inserção das probabilidades estar incompleta.
48
O sistema deve verificar se as probabilidades atribuídas aos estados de uma variável respeitam
as regras. Se as probabilidades forem:
•
incondicionais: a soma das probabilidades dos estados devem ser igual a 1.
•
condicionais: a soma das probabilidades dos estados, para cada combinação de estados dos
pais, devem ser igual a 1.
RN 003 Número mínimo de estados = 2
Situação: Validado.
O sistema não deve permitir a utilização de variáveis que possuam menos que 2 estados.
RN 004 Estados discretos nas variáveis
Situação: Validado.
O sistema apenas utiliza estados discretos nas variáveis.
3.2. Visão de Caso de Uso
Nesta seção apresenta-se o ator, as telas e os Casos de Uso do sistema.
3.2.1. Ator do sistema: Projetista
Projetista é quem desenvolve o modelo conceitual e/ou quem realiza simulações da Rede
Bayesiana.
3.2.2. Telas do sistema
TEL 001 Tela de desenho e simulação (TFMain)
Na Figura 27 apresenta-se o protótipo final da tela de desenho e simulação do sistema.
Percebe-se que esta tela é encarregada pela maioria das funcionalidades visíveis ao projetista.
TEL 002 Tela para configuração da Rede Bayesiana (TFBNProperties)
Na Figura 28 (a) revela-se o protótipo da tela de configurações da Rede Bayesiana. Esta tela
permite ao projetista alterar o nome, configurar o número de amostras para o algoritmo de simulação,
inserir a descrição e apresenta o sumário da Rede Bayesiana.
TEL 003 Tela para configuração do nó (TFNodeProperties)
Na Figura 28 (b) verifica-se o protótipo da tela para configuração de um nó. Esta tela tem por
objetivo permitir a configuração das probabilidades a priori, do número de estados, do nome da
variável, do comentário, das opções visuais do nó na área de desenho (aba formato) como também
apresenta as probabilidades dos estados com precisão máxima.
49
Figura 27. Tela de desenho e simulação (TFMain)
(a)
(b)
Figura 28. Telas para configurações: (a) TFBNProperties ; (b) TFNodeProperties
3.2.3. Casos de Uso
Na Figura 29 são demonstrados os casos de uso do sistema. O sistema basicamente é
constituido por três grandes funcionalidades, abrir/salvar ou iniciar um novo projeto, modelar e
simular. Verifica-se que o caso de uso modelar abrange a maior parte das funcionalidades que
envolvem a construção da Rede Bayesiana, enquanto que o caso de uso Simular é responsável pelos
cálculos das probabilidades a posteriori (os algoritmos). Já o caso de uso Nova/Abrir Rede Bayesiana
tem caráter auxiliar, principalmente para aumento da produtividade. Os fluxos dos casos de uso são
apresentados no apêndice A.
50
Figura 29. Casos de Uso
3.3. Visão dinâmica
Nesta seção descrevem-se os pacotes, os componentes, os diagramas de classe para cada
componente, a descrição da utilidade de cada classe implementada, diagramas de atividade para
comportamentos na ferramenta de desenho de grafos e por fim o detalhamento da implementação do
algoritmo Junction Tree.
3.3.1. Pacotes do sistema
Nesta seção apresentam-se os quatros principais pacotes do sistema. Na Figura 30 (a) revelamse os pacotes Desenho, Interface Gráfica e Motor da RB, os quais representam as funcionalidades
perceptíveis ao projetista. Com intuito de que os pacotes das funcionalidades trabalhem em harmônia
e de maneira independente (reduzir o acoplamento), existe o pacote Controladora que serve como
interface de comunicação entre os pacotes.
(a)
(b)
Figura 30. Pacotes do sistema: (a) pacotes da visão macro; (b) pacotes do Motor da BN
Para facilitar a compreensão da utilidade do pacote Controladora, observe a Figura 28. Esta
figura demonstra a tela principal do sistema e nela verifica-se a presença de três Redes Bayesianas
distintas abertas na interface de desenho. As três representam instancias distintas para o
comportamento do pacote controladora.
51
Em função da necessidade de desenvolver algoritmos desacoplados que possam ser utilizados
em outras aplicações, optou-se por dividir o pacote do Motor da RB em outros quatros pacotes, como
mostra a Figura 30 (b). Este pacote foi projetado para que possam ser adicionados novos algoritmos
com apenas a adição dos pacotes que definem o comportamento do algoritmo. Para atingir esse
objetivo, foi desenvolvido dois pacotes de uso geral para os algoritmos, eles são:
1. Topologia da RB: representa a estrutura da topologia da Rede Bayesiana, as
probabilidades condicionais/incondicionais das variáveis, as probabilidades dos estados,
definição da relação pai filho, tipo de algoritmo, entre outras funcionalidades; e
2. Controladora de Algoritmo: cria uma interface genérica entre os algoritmos e a topologia
da rede. Verifica-se que o pacote somente tem uma entrada, a topologia da RB,
independentemente do algoritmo utilizado.
A fim auxiliar a compreensão do fluxo de dados entre os diferentes pacotes do sistema, na
Figura 31 (a) revela-se o diagrama de componentes para os pacotes do sistema na visão macro e na
Figura 31 (b) apresenta-se o diagrama de componentes para o pacote Motor da BN. Verifica-se que o
nome das interfaces são as classes que realmente fornecem a interface entre o conjunto de classes do
componente com o exterior. Por exemplo, um comportamento do componente interface gráfica nunca
acessa um comportamento do componente Desenho diretamente. Para que ocorra troca de mensagens
entre os dois componentes, necessita-se o intermédio do pacote Controladora.
(a)
(b)
Figura 31. Diagramas de componentes: (a) visão macro; (b) Motor da RB
3.3.2. Diagramas de classe por componente
Nesta seção apresentam-se os diagramas de classe para cada componente da visão macro do
sistema, além da breve descrição da utilidade das classes.
52
Componente: Interface gráfica
Na Figura 32 visualiza-se o diagrama de classe para o componente que contem os
comportamentos da interface gráfica do sistema. Observa-se que as classes herdam outras classes que
não são demonstradas no diagrama. Essas classes pertencem ao conjunto de classes das bibliotecas do
QT, as quais permitem a construção de interfaces gráficas customizadas.
A seguir, descrevem-se as principais características das classes do componente:
•
TFBNProperties: meio para alteração de configurações pertinentes da Rede Bayesiana;
•
TFNodeProperties: permite a realização de alterações das configurações das propriedades
das variáveis (nós);
•
TFileInterface: responsável por abrir e/ou salvar a Rede Bayesiana num arquivo; e
•
TFMain: fornece uma interface homem máquina para as principais funcionalidades do
sistema (conjunto de ferramentas);
Figura 32. Diagramas de classe para o componente Interface Gráfica
Componente: Desenho
Na Figura 33 revela-se o diagrama de classe do componente Desenho. Percebe-se que algumas
classes possuem heranças de outras classes que não estão presentes no diagrama. Essas classes são
fornecidas pelas bibliotecas gráficas do QT. Por exemplo, a classe TEllipseDrawing herda a classe
QGraphicsPolygonItem, que é uma classe que contem os comportamentos necessários para o desenho
de polígonos genéricos.
Reitera-se que esse componente somente tem por objetivo representar a Rede Bayesiana numa
forma visual. Este componente não implementa os comportamentos necessários para a execução dos
algoritmos, entretanto a classe TScene (a interface do componente) emite eventos quando ocorrem
alterações na topologia do grafo na área de desenho. Esses eventos são de suma importância para que
o componente Topologia da RB seja atualizado conforme as alterações que o projetista realiza na
Rede Bayesiana. Entretanto na visão do projetista, este componente aparenta desenhar a Rede
53
Bayesiana e realizar a propagação das evidências, mas a propagação das evidências necessariamente
ocorre em outro componente.
Figura 33. Diagramas de classe para o componente Desenho
A seguir são descritas as principais características das classes do componente da Figura 33:
•
TScene: classe responsável pela apresentação visual dos polígonos na área de desenho e
serve como interface de saída do componente. Também é responsável pela gerência dos
eventos provenientes do mouse, entre outras funcionalidades da área de desenho. Esta
classe gerencia os comportamentos implementados para a representação da Rede
Bayesiana na forma de um grafo;
•
TRectSelection: permite o desenho de um retângulo de tamanho genérico. Esta classe é
utilizada pela classe TScene para implementar o comportamento da seleção de polígonos
na área de desenho;
•
TAlign: executa ações de alinhamento entre polígonos de qualquer formato;
•
TArrow: gera o desenho de uma aresta direcionada entre dois pontos. Essa classe é tanto
utilizada na ferramenta de adição de arestas entre nós como na inserção de arestas
permanentes entre nós;
•
TNodeArrow: gera o desenho de uma aresta entre as bordas dos polígonos de dois nós.
Verifica-se que essa classe é compatível com qualquer formato de polígono suportado pela
classe TNode;
•
TResizeDrawing: responsável pelo desenho do retângulo que funciona como ferramenta
de alteração das dimensões do polígono;
54
•
TResizeBoundingRect: insere oito ou menos TResizeDrawing dispostos simetricamente
ao redor de um polígono. Eles representam a ferramenta completa para alteração das
dimensões do desenho;
•
TDrawingSelection: responsável pelo desenho de um retângulo pontilhado ao redor de de
um polígono. Neste sistema o retângulo reitera que o desenho está selecionado;
•
TResizeRect: em funções das classes TDrawingSelection e TResizeBoundingRect estarem
associadas aos mesmos comportamentos, criou-se uma interface genérica que controla o
comportamento de ambas as classes.
•
TStatesDrawing: responsável pelo desenho do nome do estado, valor da probabilidade e
barra de gráfica;
•
TText: escreve um texto na área de desenho que respeite as dimensões do polígono no
qual o texto está contido. Se o texto ultrapassar o tamanho de alguma borda do polígono,
automaticamente o texto é ajustado para que ele fique totalmente contido dentro do
polígono;
•
TBarChart: desenha o nó na forma de barra gráfica. Essa classe desenha o polígono que
representa visualmente as probabilidades dos estados da variável;
•
TEllipseDrawing: desenha o nó em forma de elipse, conforme as especificações das redes
causais;
•
TNodeDrawing: interface genérica para controle das características dos polígonos que
representam a variável da Rede Bayesiana na interface de desenho; e
•
TNode: interface genérica que permite o controle de todas as características associadas ao
polígono que representa a variável da Rede Bayesiana na interface de desenho.
Componente: Motor da RB
Na Figura 34 revela-se o diagrama de classe para o componente Motor da RB. Verifica-se que
esse diagrama contém classes pertentes a quatro componentes. Adotou-se essa representação para que
seja possível visualizar o projeto das classes na integra.
Uma característica importante da implementação separada do componente Motor da RB é o
desacoplamento em relação a interface gráfica. Da forma pela qual foi projetado o componente,
permite-se sua reutilização em outros projetos, desde que algumas bibliotecas do QT sejam incluídas
no projeto, pois em função da necessidade de rápida implementação dos algoritmos, optou-se por
utilizar algumas classes do QT que fornecem controle listas e permitem a geração de eventos
personalizáveis, entretanto criou-se uma dependência.
55
Figura 34. Diagramas de classe para o componente Motor da RB
Segue a baixo as principais considerações sobre as classes do componente:
•
TMatrix: permite o uso de matrizes adequadas ao contexto das Redes Bayesianas;
•
TNodeProbs: representa todas as características relevantes de uma variável da Rede
Bayesiana, como por exemplo: probabilidades a priori, evidências, estados, nome da
variável, lista com os nós pais e filhos entre outros. Também oferece métodos para
operações matemáticas;
•
TTopology: lista com todos os nós da Rede Bayesiana, tipo de algoritmo, entre outras
características. Os algoritmos implementados utilizam uma instância dessa classe como
base para a execução do comportamento;
•
TBNAlgorithm : interface genérica para o uso dos algoritmos de propagação de
evidências. Para que exista a abstração da implementação dos algoritmos, esta classe
somente implementa três métodos públicos, o construtor, o destruidor e o método calc();
•
TJunctionTree: interface genérica para os cálculos das probabilidades a posteriori quando
utilizado o algoritmo Junction Tree;
•
TMoralNode: representa os nós da Rede Bayesiana, entretanto os nós são adaptados para
grafos morais (arestas não direcionadas);
•
TMoralTopology: lista de nós que compõem o grafo moral da Rede Bayesiana. Esta classe
determina as conexões morais, triangulariza grafos, determina a ordem de eliminação,
cliques entre outras funcionalidades;
•
TClique: conjunto de nós que formam o clique. Esta classe fornece comportamentos
necessários para a correta execução do algoritmo Junction Tree;
•
TSeparator: conjunto de nós do Clique que constituem o separador;
56
•
TJoinSet: conjunto formado por um clique e separador com o mesmo identificador. Esta
classe é responsável pela transmissão de mensagens entre os diferentes cliques e
separadores, além de executar operações matemáticas necessárias para a propagação de
evidências na Junction Tree;
Componente: Controladora
Na Figura 35 revela-se o diagrama de classe para o componente Controladora. Além das
classes pertencentes ao componente, apresentam-se classes de outros componentes, as quais fazem
interface com o componente atual. O objetivo é fornecer uma visão da interface entre os diferentes
componentes do sistema.
Ressalta-se que a TUniqueName não é uma classe pertinente ao objetivo do componente
Controladora, ela apenas foi adicionada ao diagrama da Figura 35 por conveniência. Ainda observa-se
que SRBEnum não é uma classe, mas sim um header que contem todos os enumeradores utilizados
no sistema. Adotou-se essa alternativa afim de centralizar a declaração dos enumeradores do sistema.
Figura 35. Diagrama de classe para o componente Controladora
Segue a baixo as principais considerações sobre as classes do componente:
•
TUniqueName: funciona como um gerador de nomes únicos, de grande valia quando
inserido um novo nó ou quando criada uma nova Rede Bayesiana (não podem existir
variáveis com o mesmo nome); e
•
TFBN: é uma classe que serve de intermédio entre todas as funcionalidades oferecidas
pelos diferentes componentes do sistema.
3.3.3. Diagramas de atividade da interface de desenho
Nesta seção apresentam-se os diagramas de atividade para os principais comportamentos da
interface de desenho da Rede Bayesiana. Na Figura 36 revela-se o diagrama para a inserção de arestas
entre nós distintos e na Figura 37 mostra-se o diagrama de atividade para a seleção e movimentação
dos desenhos.
57
Com intuito de facilitar a compreensão dos diagramas observe a Figura 27. Nesta figura
verifica-se uma das etapas de inserção de arestas, especificamente entre os nós Ladrão e Alarme.
Ainda observe que o nó Alarme está selecionado.
Figura 36. Diagrama de atividade para a ferramenta de inserção de arestas entre nós
Figura 37. Diagrama de atividade para a ferramenta de seleção
58
3.3.4. Algoritmos para propagação de evidências
Nesta subseção apresenta-se a documentação do algoritmo Junction Tree. A documentação
referente ao algoritmo amostragem de Gibbs não é detalhado em função da sua implementação
representar fielmente o fluxograma da Figura 20.
Junction Tree
O algoritmo para propagação de evidências em Redes Bayesianas Junction Tree, conforme o
projeto especificado, pode ser visto no fluxograma da Figura 38, que representa a visão macro do
funcionamento do algoritmo.
Figura 38. Visão macro da implementação do algoritmo JunctionTree
Em função da complexidade de algumas atividades do algoritmo, elas são separadas
individualmente em fluxogramas distintos.
Na Figura 39 verifica-se o fluxograma do processo de triangulação de grafos,
independentemente do grafo ser originalmente triangulado ou não. O processo divide-se basicamente
em duas etapas: na primeira determinam-se as conexões morais entre os nós do grafo G e a segunda
determina-se a ordem de eliminação. Caso o grafo G' não for originalmente triangulado, adicionamse os fill-ins necessários para transforma-lo num grafo triangulado.
Na Figura 40 revela-se o fluxograma para criar os cliques e separadores da Join Tree a partir
do grafo G moral triangulado. Em função do grafo G de entrada ser triangulado e de ser conhecida
uma ordem de eliminação, não necessita-se verificar se o nó é simplicial antes de elimina-lo. O
processo caracteriza-se por eliminar os nós simplicials e formar um novo clique e separador a partir
das famílias desses nós, entretanto somente se a família do nó que foi eliminado não estiver contido
em outro clique. Se a família do nó estiver contido em outro clique, apenas elimina-se o nó.
59
Figura 39. Triangular o grafo G
Figura 40. Determinar os cliques e separadores
Na Figura 41 verifica-se o fluxograma para conexão dos separadores aos seus respectivos
cliques (construção da Join Tree). Para o correto funcionamento desta etapa, necessita-se que a lista,
que contém os cliques e separadores, esteja ordenado crescentemente conforme o número do
identificador. A ordenação é importante, pois para qualquer separador (menos o último clique, pois
ele não tem separador) sempre existe um clique que contem todos os nós do separador e ele
necessariamente deve possuir um identificador de maior valor. Ressalta-se que um separador somente
conecta-se a um único clique de identificador superior, entretanto vários separadores podem estar
conectados a um mesmo clique.
60
Figura 41. Conectar os separadores aos seus respectivos cliques
61
4. SIMULAÇÕES
Este capítulo visa documentar os resultados obtidos com a implementação dos algoritmos
Amostragem de Gibbs e Junction Tree, através de um caso.
Com intuito de possuir um mesmo referencial de comparação entre os diferentes resultados e
simulações, adotou-se a Rede Bayesiana para análise de merecimento do crédito como base para todas
as simulações realizadas.
Na primeira seção apresenta-se a Rede Bayesiana adotada para as simulações. A segunda
seção revela a documentação dos resultados e simulações pertinentes ao algoritmo Amostragem de
Gibbs e, por último, a documentação dos resultados e simulações do algoritmo Junction Tree.
4.1. Rede Bayesiana para análise do merecimento do crédito
Adotou-se a Rede Bayesiana para análise do merecimento do crédito, visível na Figura 42,
como base para todas as simulações, em função da sua topologia com redes convergentes, pelo
número de estados, pelo número de arestas e principalmente por tratar-se de um grafo de domínio não
triangulado (se considerado arrestas não direcionadas), especialmente importante para simulações
com o algoritmo Junction Tree.
Figura 42. Rede Bayesiana para análise do merecimento do crédito
Verifica-se que as simulações visam o teste da capacidade de cálculos das probabilidades a
posteriori para ambos os algoritmos em circunstâncias sem e com múltiplas evidências instanciadas.
A capacidade do modelo em representar a relação de causa e efeito real e os valores das
probabilidades condicionais e incondicionais não são criticados, pois o objetivo é realizar as críticas
necessárias sobre as implementações dos algoritmos e não o domínio do problema.
As probabilidade a priori adotadas na Rede Bayesiana para análise do merecimento do crédito
são demonstradas no apêndice B.
62
4.2. Amostragem de Gibbs
Nesta seção apresentam-se os resultados pertinentes ao algoritmo Amostragem de Gibbs,
quando utilizada a Rede Bayesiana para análise do merecimento do crédito.
As simulações, resultados e comentários são divididos em quatro sub-seções. Na primeira
relata-se a simulação da Rede Bayesiana sem a presença de evidências, a segunda com múltiplas
evidências, a terceira visa a influência do número de amostras e a última corresponde aos comentários
sobre o desempenho computacional.
4.2.1. Simulação sem evidências
Esta simulação visa demonstrar a capacidade do algoritmo em calcular as probabilidades a
posteriori quando não existem evidências instanciadas na Rede Bayesiana.
Na Tabela 33 são apresentadas as probabilidades a posteriori calculadas pelo algoritmo
amostragem de Gibbs (5000 amostras), as probabilidades exatas (obtidas no software GeNIe com o
algoritmo Clustering) e o erro percentual da probabilidade em relação ao valor exato.
Constata-se que na maioria dos estados, o erro encontrou-se no intervalo de [-5%,+5%]. O
maior erro encontrado foi de aproximadamente 13,6%, no estado Baixo da variável Valor. No outro
extremo, verificou-se que o valor da probabilidade para estado Não aceitável da variável Histórico de
pagamento foi idêntico ao valor exato.
Como previsto na teoria, este algoritmo apresenta probabilidades a posteriori aproximadas,
entretanto os resultados obtidos são plausíveis com os valores exatos esperados.
63
Tabela 33. Probabilidades a posteriori e erro
Nome da variável
Probabilidade Probabilidade
(Gibbs)
(Algorit. Exato)
0,3394000
0,3333333
0,3178000
0,3333333
0,3428000
0,3333334
0,3522000
0,3333333
0,3242000
0,3333333
0,3236000
0,3333334
0,4570000
0,4667778
0,5430000
0,5332222
0,3194000
0,3333333
0,3340000
0,3333333
0,3466000
0,3333334
0,5650000
0,5861489
0,2188000
0,2235270
0,2162000
0,1903241
0,3338000
0,3333333
0,3292000
0,3333333
0,3370000
0,3333334
0,6726000
0,6815710
0,3274000
0,3184290
0,2488000
0,2500000
0,2522000
0,2500000
0,2500000
0,2500000
0,2490000
0,2500000
0,2584000
0,2500000
0,2516000
0,2500000
0,2458000
0,2500000
0,2442000
0,2500000
0,4412000
0,4472768
0,5588000
0,5527232
0,3398000
0,3333333
0,3252000
0,3333333
0,3350000
0,3333334
0,5228000
0,5405550
0,4772000
0,4594450
Nome do estado
a0_11100
a11101_25900
a25901_mais
s0_30000
Receitas
s30001_70000
s70001_mais
Favorável
Taxa: débitos/receitas
Desfavorável
Saudáveis
Ativos
Médios
Poucos
Alto
Valor
Médio
Baixo
Muito rentável
Profissão
Rentável
Pouco rentável
Promissora
Receitas futuras
Não promissora
Excelente
Aceitável
Histórico de
pagamento
Não aceitável
Sem referência
Estável
Não estável
Histórico de trabalho
Sem trabalho, justificado
Sem trabalho, não justificado
Confiável
Confiabilidade
Não confiável
a16_21
Idade
a22_65
a66_mais
Positivo
Merecimento de
crédito
Negativo
Débito
Erro (%)
1,8200102
-4,6599905
2,8399794
5,6600106
-2,7399903
-2,9200194
-2,0947400
1,8337160
-4,1799904
0,2000100
3,9799792
-3,6081079
- 2,1147372
13,5956991
0,1400100
-1,2399901
1,0999798
- 1,3162189
2,8172575
- 0,4800000
0,8800000
0,0000000
- 0,4000000
3,3600000
0,6400000
-1,6800000
-2,3200000
- 1,3586245
1,0994314
1,9400102
-2,4399902
0,4999799
- 3,2845871
3,8644451
4.2.2. Simulação com múltiplas evidências
Nesta simulação relata-se o comportamento da precisão numérica das probabilidades a
posteriori quando inserida múltiplas evidências na Rede Bayesiana.
As evidências instanciadas na Rede Bayesiana foram dispostas nas variáveis conforme a
Tabela 34. Verifica-se que as evidências instanciadas foram dispostas a fim de maximar o número de
propagações em rede convergentes e para que algumas probabilidades exatas sejam menores do que
0,05. O objetivo é explorar o comportamento do algoritmo em extremos e comparar o resultados da
implementação algoritmo que suporta topologias genéricas com o resultados do algoritmo estático,
apresentado na Fundamentação Teórica.
64
Tabela 34. Evidências instanciadas
Nome da variável
Valor
Taxa: débitos/receitas
Merecimento do crédito
Estado em que foi atribuída a evidência
Baixo
Favorável
Negativo
O motivo da busca de estados com probabilidades menores do 0,05 é que nas simulações com
o algoritmo estático, verificou-se a presença dos maiores erros percentuais em estados em que as
probabilidades a posteriori exatas eram menores do que 0,05.
Os resultados obtidos com a simulação com múltiplas evidências são demonstrados na Tabela
35. Verifica-se que para a maioria das probabilidades a posteriori, o erro encontra-se no intervalo de
[-5%, +8%], que de certa forma, representa a mesma tendência de erro encontrada na simulação sem
evidências.
Constata-se que o estado Saudáveis da variável Ativo apresentou o maior erro percentual,
aproximadamente 43,6%, o qual representa um erro percentual significativo. Por outro lado, o erro
absoluto da probabilidade desse estado é de 0,0019 (0,19%), que para este caso é pouco significativo.
Com intuito de reforçar a necessidade de cautela na interpretação dos erros percentuais,
considere o estado Estável da variável Histórico de Trabalho. O erro percentual para este estado é de
aproximadamente 5,5% e o erro absoluto da probabilidade é de 0,0117 (1,17%). Verifica-se então que
o erro percentual do estado Saudáveis da variável Ativo é maior do que erro do estado Estável da
variável Histórico de Trabalho, entretanto o erro absoluto associado ao estado Estável é mais
significativo do que o erro em Saudável, conforme o ponto de vista do autor.
Ainda em relação aos resultados apresentados na Tabela 35, verifica-se a presença da mesma
tendência de erro encontrada nas simulações com o algoritmo estático, apresentado no capítulo da
fundamentação teórica.
Nesta tendência, constatou-se que o erro percentual aumenta consideravelmente conforme a
diminuição da probabilidade a posteriori exata prevista para o estado. Na Tabela 35 observa-se que os
dois maiores erros percentuais (em modulo) estão associados a estados em que a probabilidade a
posteriori exata esperada é menor do que 0,05.
Entretanto não é possível afirmar que necessariamente que todas as probabilidades a
posteriori menores do que 0,05 tenham os maiores erros, pois na Tabela 35 visualiza-se casos que
afirmam o contrário. Mas pode-se afirmar que existe uma tendência de aumento do erro quando a
probabilidade a posteriori exata do estado é inferior a 0,05.
65
Tabela 35. Probabilidades a posteriori e erro – múltiplas evidências
Nome da variável
Probabilidade
(Gibbs)
0,9190
0,0612
0,0198
0,8280
0,1444
0,0276
1,0000
0,0000
0,0062
0,3746
0,6192
0,0000
0,0000
1,0000
0,2598
0,3268
0,4134
0,2444
0,7556
0,1930
0,2256
0,3248
0,2566
0,2226
0,2518
0,2386
0,2870
0,2542
0,7458
0,3152
0,2532
0,4316
0,0000
1,0000
Nome do estado
a0_11100
a11101_25900
a25901_mais
s0_30000
Receitas
s30001_70000
s70001_mais
Favorável
Taxa: débitos/receitas
Desfavorável
Saudáveis
Ativos
Médios
Poucos
Alto
Valor
Médio
Baixo
Muito rentável
Profissão
Rentável
Pouco rentável
Promissora
Receitas futuras
Não promissora
Excelente
Aceitável
Histórico de
pagamento
Não aceitável
Sem referência
Estável
Não estável
Histórico de trabalho
Sem trabalho, justificado
Sem trabalho, não justificado
Confiável
Confiabilidade
Não confiável
a16_21
Idade
a22_65
a66_mais
Positivo
Merecimento de
crédito
Negativo
Débito
Probabilidade
(Algorit. Exato)
0,9179
0,0639
0,0183
0,8251
0,1468
0,0282
1,0000
0,0000
0,0043
0,3643
0,6314
0,0000
0,0000
1,0000
0,2433
0,3341
0,4226
0,2394
0,7606
0,1961
0,2274
0,3222
0,2544
0,2109
0,2612
0,2446
0,2833
0,2535
0,7465
0,3228
0,2547
0,4225
0,0000
1,0000
Erro (%)
0,1216
-4,1709
8,4795
0,3562
-1,6208
-1,9907
0,0000
0,0000
43,5837
2,8333
-1,9327
0,0000
0,0000
0,0000
6,7949
-2,1820
-2,1863
2,0839
-0,6559
-1,5628
-0,7998
0,8223
0,8783
5,5291
-3,6080
-2,4398
1,3160
0,2833
-0,0962
-2,3468
-0,5999
2,1546
0,0000
0,0000
4.2.3. Influência do número de amostras
Esta sub-seção visa descrever a influência do número de amostras na precisão numérica das
probabilidades a posteriori. Nesta simulação emprega-se a mesma Rede Bayesiana e conjunto de
evidências utilizadas na simulação com múltiplas evidências.
Na Figura 43 revela-se o gráfico com o erro percentual médio e máximo para as simulações
com diferentes números de amostras. Para o cálculo do erro médio, realizou-se a média dos módulos
dos erros de cada estado de cada variável da Rede Bayesiana, conforme pode ser visto na Equação 31.
O erro máximo também é um valor absoluto (módulo).
66
n
Erro médio=
∑1 ∣erro do estadon ∣
Equação 31
n
Erro (%)
Erro médio e máximo conforme o número de amostras
45
40
35
30
25
20
15
10
5
0
38,95
30,52
26,04
26,6
2 2,8
19,65
15,7 9
6,59
500
4,73
1000
3,84
2 000
2,99
2 ,44
3000
2,2 7
4000
5000
13,01
12
1 0,7 8
2 ,43
7500
8,5
2,35
10000
Número de amostras
1,04
1 ,1 3
6,1 8
1,09
0,77
2 0000
30000
40000
50000
Erro mé dio (%)
Erro má ximo (%)
Figura 43. Erro médio e máximo conforme o número de amostras
Ainda na Figura 43, percebe-se a diminuição do erro médio conforme o aumento do número
de amostras, entretanto a diminuição do erro não é proporcional ao aumento do esforço
computacional necessário para os cálculos das probabilidade a posteriori, mas o esforço
computacional aumenta exponencialmente conforme o acréscimo do número de amostras. Reitera-se
que uma conclusão similar foi apresentada quando utilizado o algoritmo estático.
O mesmo comportamento, diminuição do erro conforme o acréscimo do número de amostras,
verifica-se para o erro máximo da Figura 43, entretanto percebe-se oscilações conforme o aumento do
número de amostras, mas a tendência é a diminuição do erro máximo.
Yuan e Druzdzel (2004) também verificaram a mesma tendência de diminuição sucinta do
erro conforme o aumento do número de amostras.
4.2.4. Desempenho
Nesta sub-seção pretende-se documentar aspectos sobre o desempenho computacional do
algoritmo Amostragem de Gibbs. Para as simulações, emprega-se a mesma Rede Bayesiana e
conjunto de evidências utilizadas na simulação com múltiplas evidências.
Com intuito de comprovar que o esforço computacional aumenta exponencialmente e o erro
diminui sucintamente com o acréscimo do número de amostras, na Figura 44 revela-se o gráfico do
erro percentual médio e tempo de execução versus número de amostras. Observe que o erro
percentual é calculado conforme a Equação 31, a escala de tempo é segundos e os eixo x e y estão
representados na forma logarítmica.
Realizou-se a coleta dos tempos de execução na mesma plataforma de hardware, sob o mesmo
sistema operacional e condições de ensaio.
67
10,91
Valor (% ou segundos)
Erro percentual e tempo de execução versus número de amostras
10
8,73
8
6,59
6
6,71
4,73
4
2
0,11
3,84
0,22
0,43
4,86
2,99
2 ,44 2,27
0,66
0
0,88
500
1,1
2,43
1,66
2,44
2 ,35
1 ,04
1 ,1 3 0,77 1,09
5000
Número de amostras
50000
Erro mé dio (%)
Tempo (s)
Figura 44. Erro médio e tempo de execução versus número de amostras
Reitera-se que o desempenho computacional para o algoritmo amostragem de Gibbs não
somente depende do número de amostras, mas também do número de variáveis, arestas e estados,
enfim, quanto maior for a Rede Bayesiana, maior esforço computacional necessita-se para obtenção
das probabilidades a posteriori.
Percebe-se a necessidade do uso adequado do número de amostras, pois se o número for
insuficiente, os erros associados tornam os resultados insatisfatórios, por outro lado busca-se não
utilizar grandes quantidades de amostras, pois o esforço computacional pode ser proibitivo sem
grandes melhorias na precisão numérica dos resultados. Quando empregado este algoritmo, deseja-se
utilizar uma quantidade de amostras que apresente o melhor custo/benefício na relação precisão dos
resultados e esforço computacional.
Através do gráfico da Figura 44 constata-se que o algoritmo amostragem de Gibbs não é a
solução mais adequada para os cálculos das probabilidades a posteriori em Redes Bayesianas, pois
além de se tratar de um algoritmo com solução aproximada, o fator desempenho torna proibitivo o uso
do algoritmo para grandes Redes Bayesianas. Ressalta-se que a Rede Bayesiana empregada nas
simulações deste trabalho é de pequeno porte.
Yuan e Druzdzel (2004) também verificam que o algoritmo amostragem de Gibbs demonstra
desempenho insatisfatório quando empregado na resolução de probabilidades a posteriori em Redes
Bayesiana de grande tamanho ou mesmo se comparado com outros algoritmos.
4.3. Junction Tree
Nesta seção apresenta-se todo o processo pertinente à propagação de evidências, na Rede
Bayesiana de análise de merecimento de crédito, quando utilizado o algoritmo Junction Tree.
Antes de necessariamente apresentar os valores das probabilidades a posteriori, demonstra-se
todo o processo necessário para a construção da Junction Tree. Na primeira sub-seção revela-se o
processo de transformação do grafo direcionado acíclico num grafo moral. Na segunda, apresenta-se o
68
processo de triangulação do grafo moral. Na terceira, verifica-se a metodologia para a criação da Join
Tree. Na quarta revela-se os resultados obtidos com a simulação sem evidência. Na sexta os
resultados da simulação com múltiplas evidências instanciadas e, por último, os comentários finais da
implementação.
4.3.1. Grafo moral
Esta sub-seção visa demostrar o resultado obtido no processo de transformação do grafo
direcionado acíclico num grafo moral (não direcional).
Na Figura 45 revela-se o grafo moral para a Rede Bayesiana da análise do merecimento do
crédito. Verifica-se que as arestas direcionadas do grafo foram transformadas em não direcionais e
que as conexões morais foram determinadas. Observe que as arrestas provenientes das conexões
morais são apresentadas com linhas tracejadas, afim de que o leitor discirna as arestas originais das
conexões morais.
Figura 45. Grafo moral
4.3.2. Triangulação
Nesta sub-seção verifica-se o resultado do processo de triangulação do grafo moral e a
determinação da ordem de eliminação.
Conforme observado anteriormente, a topologia da Rede Bayesiana da análise do
merecimento do crédito não forma um grafo de domínio triangulado. De qualquer forma, para o
processo de triangulação desenvolvido, não necessita-se saber se o grafo possui ou não domínio
triangulado, pois a necessidade de eliminação de nós não simplicials ocorre naturalmente.
Então, ao aplicar o procedimento, determina-se a seguinte ordem de eliminação, antes de
eliminar um nó não simplicial: Ativos, Débitos, Profissão, Histórico de Pagamento, Histórico de
Trabalho, Merecimento do crédito, Idade e Confiabilidade. Desta forma, ainda restam quatro nós não
simplicials no grafo moral, conforme percebe-se na Figura 46 (a).
69
(a)
(b)
Figura 46. (a)grafo moral de domínio não triangulado; (b) grafo moral com fill-in
Com intuito de eliminar um nó não simplicials, utiliza-se a heurística que escolhe o nó que
tem o menor valor do produtório do número de estados da família. Para este caso específico, os nós
Valor e Taxa: débitos/receitas possuem o mesmo valor, então, elimina-se o primeiro, que para este
caso é o nó Valor.
Depois de eliminado o nó não simplicial Valor, necessita-se inserir os fill-ins, que nada mais
são do que arestas não direcionadas entre todos os membros da família do nó eliminado ainda
presentes no grafo. Na Figura 46 (b) percebe-se que o nó Valor foi eliminado e que sua família forma
um clique, dado a nova aresta (fill-in), que no grafo moral é representado por uma linha tracejada com
dois pontos.
Em continuação com o processo de triangulação, os nós remanescentes Receitas, Receitas
Futuras e Taxa: débitos/receitas são eliminados, nesta seqüência, pois todos são simplicials.
4.3.3. Construção da Join Tree
Depois do grafo moral ser triangulado, permite-se a construção da Join Tree, que é constituída
por um conjunto de cliques e separadores. Com intuito de determiná-los, o grafo moral é
reconstituído, de tal forma que sejam consideradas as arestas originais não direcionadas, as conexões
morais e os fill-ins, conforme demonstra a Figura 47. Observe ainda a abreviatura do nome da
variável entre parentes.
Em função da certeza de existir uma ordem de eliminação de nós simplicials, dado que o grafo
é triangulado, utiliza-se a ordem de eliminação dos nós da etapa anterior, a fim de determinar os
cliques e separadores da Join Tree.
Depois de determinados os cliques e separadores do grafo, necessita-se determinar as
conexões entre os separadores aos seus respectivos cliques. Na Figura 48 apresenta-se a Join Tree, o
resultado desse processo.
70
Figura 47. Grafo moral triangulado
Figura 48. Join Tree
Para transformar a Join Tree numa Junction Tree basta transformar os separadores em caixas
de mensagens.
4.3.4. Simulação sem evidências
Esta simulação visa demonstrar a capacidade do algoritmo Junction Tree em calcular as
probabilidades a posteriori da Rede Bayesiana da análise do merecimento do crédito sem a inserção
de evidências.
Verifica-se na Tabela 36 que a maioria das probabilidades a posteriori não diferem dos
resultados obtidos com outro sistema. Entretanto na variável Merecimento de crédito percebe-se a
presença de uma diferença entre os resultados. Em primeira instância determinou-se que a razão dessa
diferença eram problemas da implementação, entretanto constatou-se que o motivo da diferença é o
tipo de representação numérica.
Na implementação do algoritmo deste trabalho utilizou-se representação numérica do tipo
double (8 bytes), enquanto que o GeNIe utiliza o tipo single (4 bytes). Outro motivo que determinou
essa conclusão, é que os mesmos procedimentos são utilizados para os cálculos das outras
probabilidades, que não apresentaram diferenças entre os resultados. Ainda constata-se a grande
71
quantidade de multiplicações necessárias para a obtenção das probabilidades a posteriori da variável
Merecimento do Crédito.
Tabela 36. Probabilidades a posteriori e diferença
Nome da variável
Probabilidade
(Juntion Tree)
0,3333333
0,3333333
0,3333334
0,3333333
0,3333333
0,3333334
0,4667778
0,5332222
0,3333333
0,3333333
0,3333334
0,5861489
0,2235270
0,1903241
0,3333333
0,3333333
0,3333334
0,6815710
0,3184290
0,2500000
0,2500000
0,2500000
0,2500000
0,2500000
0,2500000
0,2500000
0,2500000
0,4472768
0,5527232
0,3333333
0,3333333
0,3333334
0,5440134
0,4559866
Nome do estado
a0_11100
Débito
a11101_25900
a25901_mais
s0_30000
Receitas
s30001_70000
s70001_mais
Favorável
Taxa: débitos/receitas
Desfavorável
Saudáveis
Ativos
Médios
Poucos
Alto
Valor
Médio
Baixo
Muito rentável
Profissão
Rentável
Pouco rentável
Promissora
Receitas futuras
Não promissora
Excelente
Aceitável
Histórico de
pagamento
Não aceitável
Sem referência
Estável
Não estável
Histórico de trabalho
Sem trabalho, justificado
Sem trabalho, não justificado
Confiável
Confiabilidade
Não confiável
a16_21
Idade
a22_65
a66_mais
Positivo
Merecimento de
crédito
Negativo
Probabilidade (GeNIe) Diferença (%)
0,3333333
0,3333333
0,3333334
0,3333333
0,3333333
0,3333334
0,4667778
0,5332222
0,3333333
0,3333333
0,3333334
0,5861489
0,2235270
0,1903241
0,3333333
0,3333333
0,3333334
0,6815710
0,3184290
0,2500000
0,2500000
0,2500000
0,2500000
0,2500000
0,2500000
0,2500000
0,2500000
0,4472768
0,5527232
0,3333333
0,3333333
0,3333334
0,5405550
0,4594450
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,6397782
-0,7527241
4.3.5. Simulação com evidências
Esta simulação visa demonstrar a capacidade do algoritmo Junction Tree em calcular as
probabilidades a posteriori da Rede Bayesiana da análise do merecimento do crédito com a inserção
de múltiplas evidências. Apresenta-se as evidências instanciadas na Tabela 37.
Os resultados obtidos são revelados na Tabela 38. Constata-se novamente que existem
diferenças entre os valores simulados no sistema desenvolvido com os resultados obtidos em outro
72
sistema. Novamente atribui-se essa diferença em função da precisão numérica de representação
utilizada pelo outro sistema.
Tabela 37. Evidências instanciadas
Nome da variável
Receitas
Valor
Merecimento do crédito
Histórico de pagamento
Estado em que foi atribuída a evidência
s0_30000
Baixo
Positivo
Sem referência
Tabela 38. Probabilidades a posteriori e diferença, para simulação com múltiplas evidências
Nome da variável
Probabilidade
(Junction Tree)
0,4207006
0,2896497
0,2896498
1,0000000
0,0000000
0,0000000
0,2771111
0,7228889
0,0006254
0,4371482
0,5622264
0,0000000
0,0000000
1,0000000
0,4889327
0,3320258
0,1790415
0,6865373
0,3134627
0,0000000
0,0000000
0,0000000
1,0000000
0,3052791
0,2248731
0,2650761
0,2047716
0,6214922
0,3785078
0,3302642
0,3772048
0,2925310
1,0000000
0,0000000
Nome do estado
a0_11100
a11101_25900
a25901_mais
s0_30000
Receitas
s30001_70000
s70001_mais
Favorável
Taxa: débitos/receitas
Desfavorável
Saudáveis
Ativos
Médios
Poucos
Alto
Valor
Médio
Baixo
Muito rentável
Profissão
Rentável
Pouco rentável
Promissora
Receitas futuras
Não promissora
Excelente
Aceitável
Histórico de
pagamento
Não aceitável
Sem referência
Estável
Não estável
Histórico de trabalho
Sem trabalho, justificado
Sem trabalho, não justificado
Confiável
Confiabilidade
Não confiável
a16_21
Idade
a22_65
a66_mais
Positivo
Merecimento de
crédito
Negativo
Débito
Probabilidade
Diferença (%)
(Algorit. Exato)
0,4207000
0,0001318
0,2896490
0,0002346
0,2896500
-0,0000807
1,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,2771110
0,0000204
0,7228890
-0,0000078
0,0006254
0,0001439
0,4371470
0,0002785
0,5622270
-0,0001082
0,0000000
0,0000000
0,0000000
0,0000000
1,0000000
0,0000000
0,4889330
-0,0000607
0,3320260
-0,0000730
0,1790420
-0,0002574
0,6865370
0,0000401
0,3134630
-0,0000877
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
0,0000000
1,0000000
0,0000000
0,3052790
0,0000422
0,2248730
0,0000548
0,2650760
0,0000475
0,2047720
-0,0001846
0,6214920
0,0000283
0,3785080
-0,0000464
0,3302640
0,0000596
0,3772050
-0,0000508
0,2925320
-0,0003436
1,0000000
0,0000000
0,0000000
0,0000000
4.3.6. Considerações finais da implementação do Junction Tree
Por mais que os resultados obtidos sejam satisfatórios, necessita-se esclarecer que a versão
atual do algoritmo Junction Tree falha ao calcular as probabilidades a posteriori em Redes
73
Bayesianas com múltiplas conexões. O motivo dessa dificuldade trata-se dos domínios não
triangulados, pois em função da existência de um domínio não realmente presente, existem
dificuldades para realização das operações matemáticas pertinentes. Como conseqüência dessa
dificuldade, o algoritmo Junction Tree calcula probabilidades a posteriori errôneas para alguns
conjuntos específicos de evidências.
74
5. CONSIDERAÇÕES FINAIS
O presente trabalho resultou num sistema para modelagem e simulação de Redes Bayesianas
que oferece como meio de propagação de evidências os algoritmos Amostragem de Gibbs e Junction
Tree.
O desenvolvimento adequado das atividades executadas neste trabalho,
necessitou a
utilização de várias ferramentas, como as seguintes: Eclipse integrado com o QT, MinGw
(compilador GCC adaptado para funcionar no sistema operacional Windows), bibliotecas do QT,
Enterprise Architect, QT Designer (ferramenta para desenho de telas), GIMP, Hugin, GeNIe, Netica
Application, Microsoft Office Vision (desenho de fluxogramas), MatLab e ferramentas do
OpenOffice.
Com uso das ferramentas apropriadas, permitiu-se o desenvolvimento do sistema na
linguagem C++, com o adequado auxilio das bibliotecas do QT, que foram essenciais para a
elaboração da interface gráfica, implementação da ferramenta para visualização da Rede Bayesiana na
forma de um grafo e implementação dos algoritmos. Reitera-se que os algoritmos foram totalmente
desenvolvidos, de tal maneira que eles possam ser reaproveitados em outras aplicações.
Constata-se o grande desafio envolvido no desenvolvimento desse trabalho, pois a maioria das
ferramentas de desenvolvimento utilizadas eram novidades, os algoritmos para propagação de
evidências têm razoável complexidade em função dos modelos matemáticos e por fim o
desenvolvimento de um ferramenta de desenho de grafos 2D, pois por mais que a ferramenta de
desenho 2D seja simples do ponto de vista do usuário, a sua implementação é complexa. Ainda como
dificuldade enfrentada, verifica-se o próprio emprego das bibliotecas do QT, que por mais bem
documentadas que elas sejam, elas proporcionaram dificuldades por se tratar de uma tecnologia
desconhecida antes da implementação.
Verifica-se como um ponto positivo da elaboração deste trabalho o modelo da arquitetura do
sistema, pois este visou desacoplar as funcionalidades distintas oferecidas no software e maximizar a
reusabilidade. Como exemplo de reusabilidade, a ferramenta de desenho de grafos facilmente pode
ser reaproveitada para outros fins que necessitam de desenhos de grafos 2D, como também os
algoritmos para propagação de evidências podem ser reutilizados em outras aplicações.
Constata-se ainda como ponto positivo, o desenvolvimento da interface gráfica com o usuário,
principalmente a ferramenta para criação de grafos direcionados, a qual permite a criação de nós e a
inserção de arestas entre os nós, de maneira visual, além de disponibilizar ferramentas para adequar o
posicionamento dos nós do grafo entre outras funcionalidades. Essa ferramenta proporciona
satisfatório benefício na etapa de elaboração das relações de causas e efeito entre as variáveis, pois a
representação visual da rede facilita a compreensão do domínio do problema.
Reitera-se a capacidade de simulação propiciada pelo sistema, pois permite-se a simulação de
cenários de evidências de maneira visual, através da interface gráfica, além dos modelos de
propagação de evidência serem abstraídos tanto para a simulação como para a modelagem da Rede
Bayesiana.
Em função do exito da implementação do algoritmo Amostragem de Gibbs, permitiu-se a
realização de experimentos para mensurar o nível de erro médio, determinar a influência das
evidências na obtenção das probabilidades a posteriori, determinar a influência do número de
amostras na precisão numérica das probabilidades como também sua influência no desempenho
computacional.
Já o algoritmo Junction Tree apresentou bons resultados para algumas situações particulares
de redes, envolvendo poucas variáveis e poucas evidências simultâneas. Entretanto realizaram-se
testes que comprovam, ao menos, o funcionamento parcial do algoritmo. Como descrito
anteriormente, o motivo do sucesso parcial é a dificuldade em compreender o processo matemático
envolvido quando o grafo não possui domínio triangulado.
5.1. Sugestões para trabalhos futuros
Desenvolvimento de algoritmos que abrangessem grafos de influência, variáveis contínuas,
aprendizado, determinação de conflitos de evidências ou casos raros, uso de níveis de certeza na
inserção de evidências (likelihood), cálculo da probabilidade das evidências, determinação automática
de casos, geração automática de código, implementação dos algoritmos de simulação AIS-BN ou/e
APIS-BN, determinação das forças das influências, detecção de d-separação e d-conexão,
implementação de outros algoritmos exatos e algoritmos para Redes Bayesianas Dinâmicas (grafos
temporais).
76
REFERÊNCIAS BIBLIOGRÁFICAS
BITTENCOURT, Guilherme. Inteligência Artificial: ferramentas e teorias. 1. ed Florianópolis:
Editora da UFSC, 1998.
BLANCHETTE, Jasmin; SUMMERFIELD, Mark. C++ GUI Programming with QT 4. 1 ed New
Jersey: Prentice Hall, 2006.
ERIKSSON, Hans-Erik; PENKER, Magnus; LYONS, Brian; FADO, David. UML 2 toolkit. 1. ed
Indianapolis: Wiley, 2004.
JENSEN, Finn Verner. Bayesian Networks and Decision Graphs. 1. ed New York: SpringerVerlag, 2001.
MARQUES, Roberto L.; DUTRA, Inês. Redes Bayesianas: o que são, para que servem,
algoritmos e exemplos de aplicações. Disponível em: “www.cos.ufrj.br/~ines/courses/cos740/
leila/cos740/ Bayesianas.pdf”. Acessado em: 12/03/2008.
MELLO, Márcio P. de; VIEIRA, Carlos A. O.; PETERNELLI, Luiz A.; RUDORFF, Bernardo F. T.;
SILVA, Gustavo B. S. da. Redes Bayesianas no delineamento de culturas agrícolas usando
informações contextuais. Disponível em: “http://sputnik.dpi.inpe.br:1910/rep-/sid.inpe.br/mtcm17@80/ 2007/11.06.02.49”. Acessado em 12/03/2008.
MILHO, Isabel; FRED, Ana. Sistema de apoio ao diagnóstico médico baseado em Redes
Bayesianas. Lisboa, 2002. Disponível em: “www2.dcce.ufs.br/images/7/72/Diagnostico Medico.pdf”.
Acessado em 12/03/2008.
ORLANDELI, Rogério. Um modelo markoviano-bayesiano de inteligência artificial para
avaliação dinâmica do aprendizado: aplicação à logística. UFSC, Florianópolis, 2005. Tese de
doutorado (Engenharia de Produção).
PEARL, Judea. Probabilistic reasoning in intelligent systems: networks of plausible inference. 2
ed San Francisco: Elsevier, 1988.
RUSSELL, Stuart J; NORVIG, Peter. Inteligência Artificial. 2 ed. Rio de Janeiro: Elsevier, 2004.
SCHREIBER, Jacques Nelson Corleta. Um Modelo para Hipermídia Adaptativa utilizando
Redes Bayesianas. UFSC, Florianópolis, 2002. Artigo (Departamento de Engenharia de Produção).
SHAFER, G. Conditional probability. Int. Statist. Review,1985.
SUEBNUKARN, Siriwan. HADDWY, Peter. Comet: a Collaborative Tutoring System for
Medical Problem-Based Learning. IEEE Inteligent Systems, 2007.
YUAN, Changhe. DRUZDZEL, Marek J. Importance Sampling Algorithms for Bayesian
Networks: Principles and Performance. 19th Annual Conference on Uncertainty in Artifical
Intelligence, 2004.
APÊNDICES
A FLUXOS DOS CASOS DE USO DO SISTEMA
A.1 USC 001 – NOVA/ABRIR REDE BAYESIANA
A.1.1 Fluxo base
FLUXO BASE
Pré-condição
Fluxo
Descrição
Pós-condições
Associado com
a etapa
Tela
1
TFMain
2
3
TFMain
4
TFMain
5
6
7
8
TFMain
9
10
TFMain
11
TFMain
12
13
O projetista inicializa o sistema.
O sistema mostra a tela inicial
O sistema inicializa um novo projeto de Redes
Bayesianas (RB).
O sistema atualiza a interface para estado de modelagem
(existe uma RB aberta – mostrar todas as ferramentas)
*O projetista opta por abrir projeto salvo.
O sistema mostra a tela para escolha do diretório
(Dialog).
O projetista escolhe o arquivo do projeto.
*O projetista confirma.
O sistema fecha o projeto de RB criado no início da
execução do sistema caso ele não tenha sido modificado
ou fechado. Novo projeto associado a etapa:
O sistema lê os atributos do arquivo.
O sistema mostra na árvore a RB com suas variáveis e
estados.
O sistema mostra graficamente a RB numa janela MDI
conforme os parâmetros do arquivo (posição dos nós,
tamanho, cores, fontes), seleciona-a e expande-a.
O sistema volta para a etapa
3
5
A.1.2 Fluxo alternativo: Novo Projeto
FLUXO ALTERNATIVO
Pré-condição
A
Fluxo
5
Descrição
O projetista opta por iniciar um novo projeto.
Pós-condições
Associado com
a etapa
Tela
TFMain
5-›01
TFMain
5-›02
5-›03
5-›04
5-›05
O projetista inicia um novo projeto de Rede Bayesiana.
O sistema fecha o projeto de RB criado no início da
execução do sistema caso ele não tenha sido modificado ou
fechado. Novo projeto associado a etapa:
O sistema cria uma nova janela MDI para modelagem de
uma nova Rede Bayesiana.
O sistema seleciona essa janela MDI e expande-a.
O projetista inicia a modelagem da nova Rede Bayesiana
(ver USC 001)
3
A.1.3 Fluxo alternativo: Cancela
FLUXO ALTERNATIVO
Pré-condição
A
Fluxo
8
Descrição
O projetista opta por cancelar a operação de abrir o projeto salvo.
Pós-condições
Tela
8-›01
O sistema volta para o passo
Associado com
a etapa
5
A.2 USC 002 – NOVA/ABRIR REDE BAYESIANA
A.2.1 Fluxo Base
FLUXO BASE
Pré-condição
A
Fluxo
Descrição
Estar aberto ao menos uma Rede Bayesiana
Pós-condições
Associado
com a etapa
Tela
10
O projetista escolhe a Rede Bayesiana aberta para ser
modificada.
*O projetista insere os novos nós na Rede Bayesiana.
O sistema mostra graficamente os novos nós.
O sistema atualiza o sumário (índices das Rede Bayesiana)
e árvore.
O projetista insere as arrestas direcionadas entre os nós.
O sistema atualiza o sumário (índices das Rede Bayesiana)
e árvore.
O sistema mostra graficamente as arrestas.
*O projetista seleciona um ou grupo de nós.
O sistema mostra visualmente o nó selecionado.
*O projetista opta por configurar as propriedades do nó.
11
O sistema busca as propriedades do nó.
TFMain
1
TFMain
2
3
4
TFMain
5
6
7
TFMain
8
9
TFMain
TFNodeProperties
14
O sistema mostra a tela para configurar as propriedades
dos nós conforme as propriedades do nó selecionado. Caso
for um grupo de nós selecionados o sistema mostrará as
propriedades do primeiro nó selecionado.
O projetista define o nome da variável.
O projetista insere a descrição da variável.
15
O projetista insere n número de estados.
16
O sistema ajusta a tabela para inserção das probabilidades.
O projetista insere as probabilidades dos estados.
O projetista configura as opções de letra e cor da variável
O sistema mostra a pré-visualização do nó.
*O projetista confirma as configurações.
O sistema verifica se o nome da variável é única; verifica
critério dos valores das probabilidades.
O sistema confirma que os critérios estão adequados.
O sistema aplica as novas configurações.
O sistema fecha a tela para edição das propriedades do nó.
O sistema volta para a etapa
12
13
17
18
19
20
21
22
23
TFNodeProperties
24
25
1
A.2.2 Fluxo alternativo: Salvar como
FLUXO ALTERNATIVO
Pré-condição
A
Fluxo
8
B
Descrição
O projetista opta por salvar o projeto.
O projeto ser novo (nunca ter sido salvo) ou seleção da
opção de Salvar como.
Pós-condições
Associado
com a etapa
Tela
8-›01
8-›02
8-›03
8-›04
8-›05
8-›06
8-›07
O sistema mostra a tela para seleção do diretório e
nome do arquivo (Dialog).
O projetista seleciona o diretório e insere o nome do
arquivo
*O projetista confirma
O sistema cria um novo arquivo.
O sistema salva os parâmetros das Rede Bayesiana no
arquivo.
O sistema alerta que o arquivo foi salvo com sucesso
(Aviso na barra de status).
O sistema volta para o passo
1
A.2.3 Fluxo alternativo: Salvar
FLUXO ALTERNATIVO
Pré-condição
A
B
Fluxo
8
Descrição
O projetista opta por salvar o projeto.
Opção de salvar e o projeto já ter sido salvo anteriormente.
Pós-condições
Associado com
a etapa
Tela
8-›01
8-›02
8-›03
8-›04
O sistema cria um novo arquivo.
O sistema salva os parâmetros das Rede Bayesiana no
arquivo.
O sistema alerta que o arquivo foi salvo com sucesso
(Aviso na barra de status).
O sistema volta para o passo
1
A.2.4 Fluxo alternativo: Configurar Rede Bayesiana
FLUXO ALTERNATIVO
Pré-condição
A
Fluxo
10
Descrição
O projetista opta por configurar as propriedades da Rede Bayesiana.
Pós-condições
Associado com
a etapa
Tela
1 0-›01
TFBNProperties
1 0-›02
1 0-›03
1 0-›04
1 0-›05
1 0-›06
1 0-›07
O sistema busca as propriedades da Rede Bayesiana
selecionada (janela MDI selecionada)
O sistema mostra a tela para configuração das
propriedades da Rede Bayesiana conforme a Rede
Bayesiana selecionada.
O projetista altera o nome da Rede Bayesiana.
O projetista altera o número de amostras para o
algoritmo de Gibbs.
O projetista insere a descrição da Rede Bayesiana.
*O projetista confirma.
O sistema volta para a etapa
1
A.2.5 Fluxo alternativo: Cancelar
FLUXO ALTERNATIVO
Pré-condição
A
Fluxo
8-›03
B
10-›06
Descrição
O projetista opta por salvar o projeto.
OU
Opção de salvar e o projeto já ter sido salvo anteriormente.
Pós-condições
Tela
8->03->01
O sistema não realiza a operação e volta para a etapa
Associado com
a etapa
1
A.3 USC 003 – SIMULAR
A.3.1 Fluxo Base
FLUXO BASE
Pré-condição
A
Fluxo
Descrição
Existir uma Rede Bayesiana aberta e possuir ao menos 1 nó (variável)
Pós-condições
Associado com
a etapa
Tela
TFMain
1
TFMain
2
TFMain
3
4
5
6
7
8
9
10
11
12
O projetista seleciona a Rede Bayesiana.
O sistema busca os parâmetros associados a Rede
Bayesiana e atualiza a interface (ex.: algoritmo
selecionado, número de amostras, sumário, etc)
O sistema mostra a tela da Rede Bayesiana no topo
(acima das outras telas)
O projetista seleciona o algoritmo de propagação de
evidências.
*O projetista opta pelo modo de representação que
mostra as probabilidades dos estados diretamente no
grafo (barras gráficas)
O sistema mostra no gráfico as variáveis com seus
respectivos estados.
*O projetista insere/remove as evidências desejadas.
O sistema mostra em quais variáveis foram instanciadas evidências.
O projetista opta por atualizar as probabilidades
posteriores.
O sistema calcula as probabilidades posteriores dada
a configuração da Rede Bayesiana e as
probabilidades associadas.
O sistema atualiza as probabilidades posteriores dos
estados nas variáveis.
O sistema volta para o passo
7
A.3.2 Fluxo alternativo: Modo de representação
FLUXO ALTERNATIVO
Pré-condição
A
Fluxo
5
Descrição
O projetista opta por visualizar a Rede Bayesiana em forma de rede causal.
Pós-condições
Associado com
a etapa
Tela
5-›01
5-›02
O sistema mostra a Rede Bayesiana na forma de uma rede
causal.
O sistema volta para a etapa
7
A.3.3 Fluxo alternativo: Propagação automática
FLUXO ALTERNATIVO
Pré-condição
A
Fluxo
7
Descrição
Opção de atualização automática das probabilidades posteriores ativada
Pós-condições
Associado com
a etapa
Tela
7 -›01
7 -›02
7-›03
7 -›04
O sistema calcula as probabilidades posteriores dada a
configuração da Rede Bayesiana e as probabilidades
associadas.
O sistema atualiza as probabilidades posteriores dos
estados nas variáveis.
*O projetista realiza qualquer operação que altere as
probabilidades dos estados (exemplo: inserção de novas
arrestas, novos estados, alteração das probabilidades
condicionais e/ou incondicionais, etc)
O sistema volta para a etapa
7-›01
A.3.4 Fluxo alternativo: Propagação automática desabilitada
FLUXO ALTERNATIVO
Pré-condição
A
Fluxo
7-›03
Descrição
Atualização das probabilidades posteriores manuais
Pós-condições
Tela
7 ->03->01
O sistema volta para a etapa
Associado com
a etapa
1
B PROBABILIDADES A PRIORI
B. VARIÁVEIS INCONDICIONAIS
Ativos
Saudáveis
Médios
Poucos
Receitas
0,333333
0,333333
0,333334
Profissão
Muito rentável
Rentável
Pouco Rentável
0,333333
0,333333
0,333334
Idade
a_16_21
a22_65
a66_acima
0,333333
0,333333
0,333334
s0_30000
s30001_70000
s70001_mais
Débitos
A0_11100
A11101_25900
a25901_mais
0,333333
0,333333
0,333334
Histórico de trabalho
Estável
Não estável
Sem trabalho – justificado
0,250000
0,250000
0,250000
Sem trabalho – não justificado
0,250000
0,333333
0,333333
0,333334
Histórico de pagamento
Excelente
0,250000
Aceitável
0,250000
Não Aceitável
0,250000
Sem referência
0,250000
B.1 VARIÁVEIS CONDICIONAIS
B.1.1 Variável - Valor
Receitas
s0_30000
s30001_70000
s70001_mais
Ativos
Saudáveis Médios Poucos Saudáveis Médios Poucos Saudáveis Médios
Alto
0,899
0,001
0,001
0,989
0,699
0,100
0,989
0,907
Médio
0,100
0,300
0,100
0,010
0,300
0,800
0,010
0,092
Baixo
0,001
0,699
0,899
0,001
0,001
0,100
0,001
0,001
Poucos
0,690
0,300
0,010
B.1.2 Variável - Taxa: débitos/receitas
Débitos
A0_11100
A11101_25900
a25901_mais
Receitas
s0_30000 s30001_70000 s70001_mais s0_30000 s30001_70000 s70001_mais s0_30000 s30001_70000 s70001_mais
Favorável
0,500
0,800
0,999
0,001
0,500
0,800
0,001
0,100
0,500
Desfavorável 0,500
0,200
0,001
0,999
0,500
0,200
0,999
0,900
0,500
B.1.3 Variável – Receitas futuras
Valor
Profissão
Promissora
Não Promissora
Alto
Muito
rentável
0,990
0,010
Pouco
Muito
Rentável
Rentável rentável
0,800
0,600
0,850
0,200
0,400
0,150
Médio
Baixo
Pouco
Muito
Rentável
Rentável
Rentável rentável
0,600
0,400
0,800
0,400
0,400
0,600
0,200
0,600
Pouco
Rentável
0,010
0,990
B.1.4 Variável - Confiabilidade
Histórico de
pagamento
Confiável
Não confiável
Estável
Não estável
Sem trabalho – justificado
Sem trabalho – não justificado
Estável
Não estável
Sem trabalho – justificado
0,990000
0,700000
0,700000
0,500000
0,700000
0,550000
0,600000
0,010000
0,300000
0,300000
0,500000
0,300000
0,450000
0,400000
Sem trabalho – não justificado
Estável
Não estável
Não Aceitável Sem trabalho – justificado
0,400000
0,196429
0,010000
0,100000
0,600000
0,803571
0,990000
0,900000
Sem trabalho – não justificado
Estável
Não estável
Sem trabalho – justificado
0,010000
0,700000
0,300000
0,500000
0,990000
0,300000
0,700000
0,500000
Sem trabalho – não justificado
0,200000
0,800000
Excelente
Aceitável
Sem
referência
Histórico de trabalho
B.1.5 Variável – Merecimento do crédito
Confiabilidade
Taxa:
débitos/receitas
Receitas
Futuras
Promissora
Favorável
Não Promissora
Confiável
Promissora
Desfavorável
Não Promissora
Promissora
Favorável
Não Promissora
Não confiável
Promissora
Desfavorável
Não Promissora
Idade
Positivo
Negativo
a_16_21
a22_65
a66_acima
a_16_21
a22_65
a66_acima
a_16_21
a22_65
a66_acima
a_16_21
a22_65
a66_acima
a_16_21
a22_65
a66_acima
a_16_21
a22_65
a66_acima
a_16_21
a22_65
a66_acima
a_16_21
a22_65
a66_acima
0,900000
0,908257
0,800000
0,700000
0,800000
0,600000
0,700000
0,727273
0,700000
0,250000
0,400000
0,250000
0,700000
0,800000
0,500000
0,300000
0,400000
0,200000
0,500000
0,500000
0,400000
0,001000
0,001000
0,001000
0,100000
0,091743
0,200000
0,300000
0,200000
0,400000
0,300000
0,272727
0,300000
0,750000
0,600000
0,750000
0,300000
0,200000
0,500000
0,700000
0,600000
0,800000
0,500000
0,500000
0,600000
0,999000
0,999000
0,999000