Algoritmos EM para Aprendizagem de Redes - FACOM

Transcrição

Algoritmos EM para
Aprendizagem de Redes
Bayesianas a partir de
Dados Incompletos
José Eduardo Ochoa Luna
Dissertação de Mestrado
Orientação: Profa. Dra. Maria Bernadete Zanusso
Área de Concentração: Inteligência Artificial
Dissertação apresentada como requisito para a obtenção do tı́tulo de mestre em Ciência
da Computação.
dct
ufms
Departamento de Computação e Estatı́stica
Centro de Ciências Exatas e Tecnologia
Universidade Federal de Mato Grosso do Sul
Julho/2004
Algoritmos EM para Aprendizagem de Redes Bayesianas a partir de
Dados Incompletos
Este exemplar corresponde à redação final
da tese devidamente corrigida
e defendida por José Eduardo Ochoa Luna
e aprovada pela comissão julgadora.
Campo Grande/MS, 29 de julho 2004.
Banca Examinadora:
• Profa. Dra. Maria Bernadete Zanusso (Orientadora) (DCT-UFMS)
• Prof. Dr. Wagner Texeira da Silva (CIC-UnB)
• Prof. Dr. Paulo Aristarco Pagliosa (DCT-UFMS)
Agradecimentos
A Deus, guia em cada passo dado.
À Professora Doutora Maria Bernadete Zanusso, por sua orientação, atenção, esclarecimentos importantes e confiança durante todo o decorrer deste trabalho.
À Fátima, em especial, pelo amor, carinho e a felicidade que significa partilhar cada
instante juntos.
A minha mãe Felicia, meu pai José Luis, e meus irmãos que sempre estiveram nos
meus pensamentos cada dia que estive longe de casa. Pelo amor e os ensinamentos que
foram e serão sempre importantes na minha vida.
Aos amigos e colegas do curso de Mestrado, cuja motivação e companheirismo sempre
foram de muita importância. Agradeço aos membros da banca examinadora, Professor
Doutor Wagner Texeira da Silva (UnB) e ao Professor Doutor Paulo Pagliosa (UFMS).
Aos professores e funcionários do DCT-UFMS.
Ao professor e amigo Marcelo Ladeira e ao pessoal do LARA-UnB pelo apoio durante
minha estada em Brasilia.
À Capes pelo apoio financeiro.
i
Resumo
O objetivo deste trabalho é implementar algoritmos de aprendizagem para redes bayesianas a partir de dados incompletos baseando-se no algoritmo Expectation Maximization
(EM). Redes bayesianas são modelos gráficos para representar incerteza e raciocinar com
probabilidades. São formadas de uma estrutura que define as relações de independência
entre variáveis, e de parâmetros numéricos que são as probabilidades condicionadas pela
estrutura. Em geral, um especialista define este modelo, porém, também pode-se aprender
a estrutura e parâmetros a partir de dados disponı́veis. Quando os dados são completos,
a aprendizagem das probabilidades é simples, pois são baseadas em freqüências. Quando
os dados são incompletos, o algoritmo EM permite determinar valores faltosos mediante
estimativas de máxima verossimilhança. Neste trabalho foi implementado o algoritmo
EM paramétrico de Lauritzen para completar os dados e realizar a aprendizagem das
probabilidades para o caso de uma estrutura qualquer. O algoritmo EM de Friedman
foi implementado para aprendizagem de estrutura baseando-se no paradigma de busca
e pontuação, o qual, entre várias estruturas candidatas, define a de maior pontuação,
segundo uma métrica, para ser a estrutura intermediária de um processo iterativo que
busca a estrutura ótima para os dados incompletos. O processo começa a partir de uma
estrutura aleatória, completa os dados a cada estrutura intermediária e aprende suas
probabilidades usando EM de Lauritzen. Do mesmo modo que as propostas atuais de
implementação oferece-se soluções descobrindo distribuições de probabilidades conjuntas
para futuras inferências e descoberta de relações causais entre variáveis, mas ainda estão
sujeitas a melhorias, principalmente quanto a otimizar o tempo de execução. As soluções
obtidas neste trabalho são semelhantes com as redes reais usadas para teste, como o
benchmark ALARM e outras, sendo que, para comparações, foi medida a qualidade das
probabilidades em termos da entropia cruzada e das estruturas aprendidas em termos
de diferenças topológicas, ou seja, inclusão ou exclusão correta de arcos. Com suporte
na plataforma da ferramenta UnBBayes o estudo foi desenvolvido ampliando, depois, sua
própria base para a construção de redes bayesianas e a realização de processos de inferência
diagnóstica ou preditiva no caso de dados incompletos.
ii
Abstract
The aim of this work is to implement algorithms for learning in bayesian networks from
incomplete data based on Expectation Maximization algorithm (EM). Bayesian networks
are graphical models for reasoning and representing probabilities. They are constituted
of a structure, which defines independence relationships between various variables, and
numerical parameters measuring the strong of the relationships. In geral, an expert defines this model, but, it is possible to learn both structure and parameters when data is
given. EM algorithm can be used when data contain missing values. In this work was
implemented parametric EM algorithm by Lauritzen, it consists of data completations
using bayesian inference and parameter learning as usual. For structure learning was
implemented structural EM algorithm by Friedman wich, based on search and score paradigm, choose the best structure among various candidats, using a particular metric. This
is an initial structure of an iterative process that search the best structure to incomplete
data. Given a random structure, complete data and for each intermediate structure make
parametric learning using Lauritzen’s algorithm. Current proposal of implementations,
provide solutions discovering joint probability distributions to future inferences and causal relationships between variables, but subject, mainly, to execution time optimization.
Research results are similar with real network tested that is Alarm benchmark and others.
In this case to make comparisons, quality of probabilities learned was measured, based
on cross entropy. For structures learned, topological differences were avaliated, indicating
added or missing arcs. It was increased UnBBayes tool funcionality, allowing predictive
and diagnostic inference and learning when incomplete data is available.
iii
Conteúdo
Resumo
ii
Abstract
iii
Lista de Figuras
viii
Lista de Tabelas
x
Lista de Abreviaturas
xi
Lista de Sı́mbolos
xii
1 Introdução
1
1.1
Justificativa e Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.2
Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.3
Perspectivas Futuras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.4
Organização do Texto
8
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 Redes Bayesianas
2.1
9
Fundamentos da Teoria da Probabilidade . . . . . . . . . . . . . . . . . . .
9
2.1.1
Experimento Aleatório, Espaço Amostral e Evento . . . . . . . . . . 10
2.1.2
Frequência Relativa . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.3
Axiomas da Probabilidade . . . . . . . . . . . . . . . . . . . . . . . 11
2.1.4
Definição Freqüentista de Probabilidade (Intuitiva) - “A Posteriori”
2.1.5
Definição Clássica de Probabilidade (Laplace) - “A Priori” . . . . . 12
2.1.6
Variáveis Aleatórias e Proposições . . . . . . . . . . . . . . . . . . . 13
iv
12
Conteúdo
2.2
2.3
2.4
dct-ufms
2.1.7
Distribuição Conjunta, Marginal e Condicional . . . . . . . . . . . . 14
2.1.8
Independência Condicional . . . . . . . . . . . . . . . . . . . . . . . 15
Modelo Bayesiano de Probabilidade (Subjetivo) . . . . . . . . . . . . . . . 16
2.2.1
Teorema de Bayes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.2
Distribuição Multinomial e de Dirichlet . . . . . . . . . . . . . . . . 17
Redes Bayesianas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1
Definição de Rede Bayesiana . . . . . . . . . . . . . . . . . . . . . . 18
2.3.2
O Problema da Inferência . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.3
O Problema da Aprendizagem . . . . . . . . . . . . . . . . . . . . . 21
2.3.4
Por que usar Redes Bayesianas? . . . . . . . . . . . . . . . . . . . . 22
Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3 Inferência em Redes Bayesianas
3.1
25
Métodos Exatos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.1.1
Propagação de Evidências . . . . . . . . . . . . . . . . . . . . . . . 26
3.1.2
Propagação em Poliárvores . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.3
Propagação em Redes Multiconectadas . . . . . . . . . . . . . . . . 33
3.1.4
Algoritmo de Árvore de Junção . . . . . . . . . . . . . . . . . . . . 35
3.2
Métodos Aproximados - Simulação Estocástica . . . . . . . . . . . . . . . . 42
3.3
Métodos Simbólicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.4
Comentários Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4 Aprendizagem de Redes Bayesianas
47
4.1
Algoritmo Expectation Maximization EM . . . . . . . . . . . . . . . . . . . 48
4.2
Aprendizagem de Parâmetros . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.3
4.4
4.2.1
Estrutura Conhecida e Dados Completos . . . . . . . . . . . . . . . 51
4.2.2
Estrutura Conhecida e Dados Incompletos - EM Paramétrico . . . . 54
Aprendizagem de Estrutura . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.3.1
Dados Completos-Paradigma Busca e Pontuação . . . . . . . . . . . 58
4.3.2
Dados Incompletos-EM . . . . . . . . . . . . . . . . . . . . . . . . . 66
v
Conteúdo
dct-ufms
5 Implementação e Resultados
73
5.1
Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.2
Descrição dos Dados Usados . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.3
Metodologia Experimental . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.4
Aspectos de Implementação e Resultados . . . . . . . . . . . . . . . . . . . 78
5.5
5.4.1
Ambiente de Implementação . . . . . . . . . . . . . . . . . . . . . . 78
5.4.2
Algoritmo EM Paramétrico . . . . . . . . . . . . . . . . . . . . . . 82
5.4.3
Algoritmo EM Estrutural . . . . . . . . . . . . . . . . . . . . . . . 95
6 Conclusão
110
6.1
Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.2
Limitações Atuais e Sugestões para Trabalhos Futuros . . . . . . . . . . . . 112
Referências Bibliográficas
114
vi
Lista de Figuras
2.1
Estrutura de rede bayesiana para detecção de problemas de fraude: F =
Fraude; I = Idade; S = Sexo; G = Gasolina; J = Jóias. . . . . . . . . . . . 19
3.1
Grafo acı́clico orientado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2
O nó D divide a poliárvore em duas poliárvores não conexas. . . . . . . . . 29
3.3
Alarme contra roubos: R = Roubo; T = Terremoto; A = Alarme; J =
João-liga; M = Maria-liga. . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.4
Pais e filhos de um nó qualquer X. . . . . . . . . . . . . . . . . . . . . . . 32
3.5
Estrutura de rede bayesiana multiconectada. . . . . . . . . . . . . . . . . . 34
3.6
Exemplo de grafo moralizado. . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.7
Grafo triangular do grafo da Figura 3.6. . . . . . . . . . . . . . . . . . . . 38
3.8
Exemplo de estrutura de árvore de junção para o exemplo da Figura 3.5. . 40
3.9
Estrutura de rede bayesiana para simulação estocástica, variáveis com estados sim e nao. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.10 Probabilidades condicionais para a rede bayesiana exemplo. . . . . . . . . . 44
4.1
Várias estruturas de rede candidatas. . . . . . . . . . . . . . . . . . . . . . 61
5.1
Rede bayesiana ALARM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.2
Rede bayesiana ASIA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.3
Rede bayesiana NETICA. . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.4
Pacotes principais da ferramenta UnBBayes. . . . . . . . . . . . . . . . . . 79
5.5
Classes principais do pacote aprendizagem. . . . . . . . . . . . . . . . . . . 81
5.6
Especificação das classes dos algoritmos EM. . . . . . . . . . . . . . . . . . 83
5.7
Rotina principal do algoritmo EM paramétrico. . . . . . . . . . . . . . . . 84
5.8
Algoritmo EM paramétrico. . . . . . . . . . . . . . . . . . . . . . . . . . . 85
vii
Lista de Figuras
5.9
dct-ufms
Porcentagens de tempo de processamento, rede bayesiana ALARM. . . . . 87
5.10 Passo Expectation dentro do algoritmo EM. . . . . . . . . . . . . . . . . . . 87
5.11 Estimativa dos parâmetros (Expectation). . . . . . . . . . . . . . . . . . . . 88
5.12 Atualização de parâmetros e cálculo da verossimilhança (Maximization). . . 89
5.13 Algoritmo Qt para o cálculo das novas probabilidades para Vi . . . . . . . . 90
5.14 Tempo e distância NETICA - algoritmo EM paramétrico. . . . . . . . . . . 92
5.15 Tempo e distância ASIA - algoritmo EM Paramétrico . . . . . . . . . . . . 93
5.16 Tempo e distância ALARM - algoritmo EM paramétrico. . . . . . . . . . . 94
5.17 Detalhe do algoritmo EM estrutural. . . . . . . . . . . . . . . . . . . . . . 96
5.18 Algoritmo EM estrutural resumido. . . . . . . . . . . . . . . . . . . . . . . 96
5.19 Algoritmo Iterated Hill Climbing. . . . . . . . . . . . . . . . . . . . . . . . 97
5.20 Algoritmo EM estrutural. . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.21 Algoritmo Greedy Hill Climbing para busca de estruturas. . . . . . . . . . . 99
5.22 Algoritmo que adiciona arco temporário e testa a pontuação. . . . . . . . . 100
5.23 Algoritmo adiciona um arco na estrutura. . . . . . . . . . . . . . . . . . . . 101
5.24 Algoritmo que calcula a pontuação por causa da mudança local. . . . . . . 102
5.25 Algoritmo que calcula a pontuação para uma variável Vi . . . . . . . . . . . 103
5.26 Aspectos do cálculo da métrica BDe para Vi . . . . . . . . . . . . . . . . . . 104
5.27 Tempo algoritmo SEM - ASIA. . . . . . . . . . . . . . . . . . . . . . . . . 108
viii
Lista de Tabelas
2.1
Distribuição conjunta de sistema operacional × processador [20]. . . . . . . 14
2.2
P (F ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3
P (I). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4
P (S).
2.5
P (G|F ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.6
P (J|F, I, S). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.7
Vantagens comparativas das redes bayesianas. . . . . . . . . . . . . . . . . 24
3.1
P (R). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2
P (T ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3
P (A|R, T ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.4
P (J|A). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.5
P (M |A). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.6
Ordem de eliminação dos nós. . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.7
Exemplo de potenciais para a árvore de junção do exemplo da Figura 3.5. . 41
3.8
Exemplo de marginalização a partir de potenciais para o exemplo da Figura
3.5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.9
Conjunto de 100 configurações de (A, B, C, D, E). . . . . . . . . . . . . . . 44
4.1
Amostra de dados disponı́vel para estrutura X → Y → Z. . . . . . . . . . 54
4.2
Freqüências calculadas para X2 |X1 (N2jk ). . . . . . . . . . . . . . . . . . . 54
4.3
Distribuição de probabilidade condicional P (X2 |X1 ). . . . . . . . . . . . . 54
4.4
Amostra de dados incompleta para aprendizagem. . . . . . . . . . . . . . . 56
4.5
Freqüências esperadas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.6
Banco de dados completo para aprendizagem. . . . . . . . . . . . . . . . . 61
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
ix
Lista de Tabelas
dct-ufms
5.1
Amostra de dados lida e armazenada para as variáveis A, B, C. . . . . . . . 82
5.2
Análise de resultados para rede bayesiana ASIA. . . . . . . . . . . . . . . . 106
5.3
Análise de resultados para rede bayesiana ALARM. . . . . . . . . . . . . . 107
x
Lista de Abreviaturas
BC
BDe
EA
EM
fd
GAO
GC
IC
LC
MAP
MCAR
MDL
MLE
MS-EM
RB
SEM
va
Bound and Collapse, algoritmo para aprendizagem de redes bayesianas.
Bayesian Dirichlet equivalence, métrica Bayesiana para redes equivalentes em verossimilhança.
Evolutionary Algorithm, algoritmo evolutivo.
Expectation Maximization.
Função de Distribuição.
Grafo Acı́clico Orientado.
Global Conditioning, condicionamento global.
Independência Condicional.
Local Conditioning, condicionamento local.
Maximum a Posteriori.
Missing Completely at Random, dados faltosos por mecanismos aleatórios.
Minimum Description Length, métrica baseada na entropia.
Maximum Likelihood Estimation, estimativa de máxima verossimilhança.
Model Selection, algoritmo EM para seleção de estruturas.
Rede Bayesiana.
Structural EM, algoritmo EM estrutural.
Variável Aleatória.
xi
Lista de Sı́mbolos
X
DX
Xi
U
P (U )
xi
D
Dl
λ
π
BEL(X)
Ci
SC i C k
φ
φC
φS
S
B
P ai
P (Xi |P ai )
Θ
θi
θij
θijk
ri
qi
n
m
N0
Nijk
Nij
αijk
αij
Dirichlet(x)
Γ(x)
Variável aleatória, conjunto de variáveis.
Domı́nio de X.
Variável aleatória com posição i, Xi ∈ X.
Um domı́nio, conjunto de variáveis aleatórias U = {X1 . . . , Xn }.
Probabilidade conjunta do domı́nio.
Instância da variável Xi (xi é um estado) não conhecida.
Um banco de dados.
l−ésimo caso do banco de dados.
Mensagens enviados de filhos para os pais.
Mensagens enviados de pais para filhos.
Crença de um conjunto de variáveis.
Clique ou agregado.
Separador de cliques.
Potencial de crença.
Potencial de clique.
Potencial de separador.
Uma estrutura de rede bayesiana.
Rede bayesiana.
Conjunto de variáveis aleatórias pais da variável i em uma estrutura de RB.
Probabilidade condicional da variável Xi dado seus pais P ai .
Conjunto de parâmetros de uma rede bayesiana.
Conjunto de parâmetros da variável Xi .
Conjunto de parâmetros da variável Xi com relação aos pais j ou P (Xi |P ai = j).
P (Xi = k|P ai = j).
Conjunto de estados da variável Xi .
Conjunto de instâncias P ai .
Número de variáveis.
Número de casos no banco de dados.
Amostra de tamanho equivalente.
Número de casos no banco de dados onde Xi = k e P ai = j.
P
= ri
k=1 Nijk .
Coeficientes de Dirichlet para θijk .
P
= ri
k=1 αij .
Distribuição de Dirichlet.
R∞
Função definida como Γ(n) = (n − 1)! ou Γ(x) = 0 tx−1 e−t dt.
xii
Capı́tulo 1
Introdução
O objetivo da inteligência artificial é prover um modelo computacional de comportamento inteligente e, sobretudo, raciocı́nio de senso comum [56]. O objetivo da teoria da
probabilidade é prover uma explicação coerente de como devem mudar as crenças à luz
de informação parcial ou incerta. Desde que ao raciocı́nio de senso comum se aplica à
informação incompleta, naturalmente poder-se-ia esperar que as duas disciplinas compartilhassem linguagem, objetivos e técnicas.
O atrativo primário da teoria da probabilidade é sua capacidade para exprimir relações
qualitativas úteis entre crenças e processar estas relações a fim de produzir, intuitivamente,
conclusões plausı́veis, pelo menos em casos nos quais julgamentos intuitivos são convincentes. Por razões de economia de armazenamento e generalidade, as pessoas esquecem
as experiências atuais e retém suas impressões mentais na forma de médias, pesos, ou
relações qualitativas abstratas que as ajudam a determinar ações futuras [8].
Segundo Pearl [56], existem três escolas para lidar com a incerteza em sistemas de inteligência artificial: a logı́stica, a neo-calculista, e a neo-probabilista. A escola logı́stica tenta
lidar com incerteza utilizando técnicas não numéricas, como lógica não monotônica. A escola neo-calculista utiliza representações numéricas de incerteza mas considera o cálculo
de probabilidades inadequado para esta tarefa, inventando um novo cálculo, tal como
função de crenças de Dempster-Shafer [25, 62, 63], lógica Fuzzy [44] e fatores de certeza. Os neo-probabilistas permanecem com os fundamentos da teoria da probabilidade,
tentando misturar a teoria com as facilidades computacionais necessárias para realizar
tarefas de inteligência artificial. As redes bayesianas [55] fazem parte desta última escola.
Para Diez [27] as redes bayesianas fazem parte dos métodos numéricos para raciocı́nio
incerto. O primeiro método numérico que surgiu foi o tratamento probabilista. Como descrito por Diez [27], no século XVIII, Bayes [2] e Laplace propuseram a probabilidade como
uma medida de crença pessoal. No inı́cio do século XX surgem outras interpretações da
probabilidade, como a freqüência (a longo prazo) associada a situações ou experimentos
que se repetem; nesta linha, estão os trabalhos estatı́sticos de Fisher [28]. No inı́cio dos
1
dct-ufms
anos 30, devido ao trabalho de Savage e B. de Finetti [23] especialmente, se redescobre a
probabilidade como medida de crença pessoal.
Alguns anos depois, são inventados os computadores e logo após surge a inteligência
artificial. Naquela época, os computadores tinham superado em muito a capacidade de
cálculo dos seres humanos, mas estavam muito aquém do denominado “comportamento
inteligente”. Para se usar a capacidade dos computadores a inteligência artificial esforçavase na resolução de problemas simbólicos e em métodos algorı́tmicos dedicados ao cálculo
numérico. Esta foi uma das razões pelas quais, inicialmente, não se prestou atenção no
estudo da probabilidade como ramo ou ferramenta da inteligência artificial.
Contudo, para determinados problemas, como o de diagnóstico médico, por exemplo,
era inevitável ter que lidar com incerteza. Naqueles anos, a única técnica disponı́vel,
ainda com suas limitações, era o método probabilista clássico (as vezes denominado naı̈ve
Bayes [49]); com ele foram construı́dos os primeiros sistemas de diagnóstico médico que
tiveram sucesso relativo em problemas que agora parecem pequenos em tamanho.
O método probabilista clássico apresentava dois inconvenientes principais: o primeiro
deles era a dificuldade de obter as probabilidades condicionais necessárias para construir o modelo. A aplicação do teorema de Bayes, usado no cálculo das probabilidades
a posteriori, requeria um número exponencial de parâmetros, pelo que precisava-se introduzir hipóteses simplificadoras. A primeira era a exclusividade dos diagnósticos e a
independência condicional dos achados. Ainda assim, o número de parâmetros continuava
sendo elevado, tendo-se o fato que raramente havia bancos de dados a partir das quais
poder-se-ia obter as probabilidades objetivas, pelo que na maioria das vezes era preciso
utilizar estimativas subjetivas, pouco confiáveis. O segundo inconveniente do modelo era
que as hipóteses eram pouco verossı́meis, sobretudo a de independência condicional. Por
estes motivos, a maior parte dos pesquisadores concordavam em que a probabilidade não
era um método adequado para a inteligência artificial.
De outro lado, o sucesso obtido pelo sistema especialista DENDRAL [4], um dos
primeiros sistemas especialistas, demonstrou as vantagens da programação baseada em
regras. Por isto, os criadores do MYCIN [5]1 procuravam um método de cálculo eficiente
que pudesse se adaptar ao raciocı́nio mediante o encadeamento de regras. Os problemas
citados anteriormente e a incapacidade dos métodos probabilistas para se encaixarem neste esquema levaram os responsáveis por este projeto a desenvolver um método próprio,
consistente em atribuir a cada regra um fator de certeza. Este modelo na prática não
tinha nenhuma relação com a teoria da probabilidade, nem sequer com sua interpretação
subjetiva.
O sucesso de MYCIN foi grande, pois em um campo tão complexo e incerto como as
doenças infecciosas, foi capaz de conseguir diagnósticos e recomendações terapêuticas tão
1
Sistema de consulta médica criado em 1976.
2
dct-ufms
boas quanto dos especialistas. Mas um estudo matemático demonstrou que no modelo de
combinação de regras havia hipóteses implı́citas muito fortes e difı́ceis de justificar. Nos
anos seguintes surgiram novas crı́ticas cada vez mais fortes contra a validade do modelo
de fatores de certeza, maiores detalhes podem ser encontrados em [8].
Quando os criadores de MYCIN estavam pensando na teoria de Dempster-Shafer para
resgatar o modelo de fatores de certeza (princı́pio dos anos 80), surgem as redes bayesianas que mudam totalmente o cenário: um modelo probabilista inspirado na causalidade,
cuja virtude principal consiste no modelo gráfico em que cada nó representa uma variável
e cada arco representa, geralmente, um mecanismo causal.
Uma rede bayesiana2 , segundo Heckerman [37], pode ser definida como um grafo com
as seguintes propriedades:
1. Um conjunto de variáveis aleatórias são os nós da rede.
2. Um conjunto de arcos ou setas conectam pares de nós. O significado intuitivo de
um arco do nó X para o nó Y é que X tem influência direta sobre Y .
3. Cada nó tem uma tabela de probabilidade condicional que quantifica os efeitos que
os pais tem sobre os nós. Os pais de um nó são todos aqueles nós que têm setas
apontando para ele.
4. O grafo não tem ciclos dirigidos. Daı́ dizer que são grafos acı́clicos orientados ou
dirigidos (GAO).
A representação visual das redes bayesianas, permite uma melhor comunicação com o especialista do domı́nio dos dados, favorecendo maior rapidez na definição, desenvolvimento
ou modificação do modelo, o que por sua vez, ajuda a compreender melhor o problema.
A natureza das variáveis pode ser discreta3 , por exemplo, com dois estados possı́veis
verdadeiro e falso, sendo suas probabilidades condicionais facilmente representadas em
tabelas de probabilidades. Ou podem ser de natureza contı́nua, neste caso representadas
por funções de densidade. Em suma, uma rede bayesiana representa uma distribuição de
probabilidade conjunta para um conjunto de variáveis. No contexto deste trabalho serão
utilizadas variáveis de natureza discreta.
A tarefa mais comum é utilizar a rede bayesiana para inferência probabilı́stica que
consiste em obter conclusões à medida que novas informações ou evidências são conhecidas. Por exemplo, na área médica, pode-se concluir por um diagnóstico baseando-se
em sintomas, que são evidências. Ou também se faz inferência para estimar estados de
2
Outras denominações são: rede de crença, rede probabilı́stica, rede causal.
Uma rede bayesiana não explora a natureza ordenável de suas variáveis, assim o caso discreto é
categórico.
3
3
dct-ufms
variáveis que não foram observadas.
Com ajuda de um especialista num certo domı́nio de dados, define-se um modelo de
redes bayesianas: determina-se a estrutura e suas probabilidades condicionais associadas.
Mas, em situações em que o especialista não está disponı́vel, ou no caso de um grande
domı́nio de dados em que fica difı́cil se especializar, são úteis métodos automáticos para
aprender estruturas e probabilidades (também denominados parâmetros) a partir de dados disponı́veis [6, 33].
A aprendizagem em redes bayesianas consiste em determinar a estrutura ou seus
parâmetros, ou ambos, a partir de dados de treinamento. Em geral, pode-se falar de
distintos tipos de aprendizagem, dependendo se a estrutura é conhecida ou não e se a
observação dos dados é completa ou parcial [33]. Pode haver instâncias em que o estado
de uma ou mais variáveis não foi observado e também o caso de uma ou mais variáveis
não terem sido observada em nenhuma instância. Existem inúmeras possibilidades de algoritmos para cada tipo de aprendizagem, cada uma com suas vantagens e desvantagens
sobre as outras [8]. Ainda não consta na literatura a existência de um algoritmo padrão
para aprendizagem de estruturas, dentro das redes bayesianas essa é uma área que está
em constante pesquisa.
Neste trabalho, aborda-se o problema de aprendizagem de redes bayesianas quanto a
suas estruturas e parâmetros, no cenário de dados incompletos e variáveis não observadas,
cujos algoritmos ainda não apresentam soluções satisfatórias. Especificamente escolheu-se
o algoritmo EM (Expectation Maximization, ou Estimation Maximization) e suas variantes porque apresentam soluções razoáveis.
Em geral, o algoritmo EM pode ser aplicado em situações onde se deseja estimar um
conjunto de parâmetros que descreve uma distribuição de probabilidade. O algoritmo se
baseia em estimar parâmetros de máxima verossimilhança para problemas onde os estados
das variáveis não foram observados [49].
A primeira formulação do algoritmo EM em redes bayesianas foi dada por Lauritzen [46], e trata com aprendizagem de parâmetros de redes bayesianas a partir de dados
incompletos e uma estrutura conhecida. Este é um problema interessante pois, usualmente, é mais fácil para um especialista decidir quais são os relacionamentos de dependência
condicional que acontecem num domı́nio de dados do que especificar as probabilidades
condicionais correspondentes [61]. Para autores como [30, 54, 68] este algoritmo é denominado EM paramétrico.
O Passo E deste algoritmo consiste em estimar os dados faltosos para completar a
amostra de dados incompleta. Lauritzen, usando os valores que foram observados na
amostra como evidência, realiza inferência em redes bayesianas para fazer esta estimativa. O algoritmo de inferência usado denomina-se árvore de junção [40].
4
1.1. Justificativa e Objetivos
dct-ufms
No Passo M, com os dados completados, realiza-se aprendizagem das probabilidades,
baseado nas freqüências dos estados das variáveis na amostra. Ambos Passos E e M fazem
parte de um processo iterativo, em que as novas probabilidade calculadas na fase M, serão
utilizadas para realizar a inferência na fase E.
Posteriormente, Friedman [29, 30] definiu um algoritmo EM para aprendizagem de
parâmetros e estrutura denominado Model Selection EM; uma versão modificada deste algoritmo, denominada EM estrutural, foi desenvolvida sucessivamente. A idéia fundamental destes algoritmos consiste em transformar o problema de aprendizagem de estrutura
com dados incompletos em um mais simples. Usa-se o algoritmo EM paramétrico (Passo
E) para completar os dados e busca-se a melhor estrutura de rede usando um algoritmo de
busca gulosa (Passo M). Cada estrutura é avaliada de acordo com uma métrica que mede
a aderência da estrutura aos dados. Sucessivamente, cada estrutura ótima encontrada no
Passo M é usada como ponto inicial para novos completamentos no Passo E, até encontrar
a melhor estrutura para os dados incompletos.
Nos últimos anos têm surgido novas versões e novos algoritmos, modificando partes do
procedimento geral do algoritmo EM estrutural de Friedman. Entretanto, considerou-se
importante conhecer em profundidade as versões de Lauritzen e de Friedman.
1.1
Justificativa e Objetivos
A aprendizagem em redes bayesianas é uma tarefa muitas vezes complexa. Muitos esforços
têm sido dedicados ao desenvolvimento de algoritmos para resolvê-la. Um problema ainda
mais interessante é a aprendizagem a partir de dados incompletos, principalmente porque
muitos bancos de dados de aplicações reais apresentam instâncias incompletas, produzidas
por falhas na coleta da informação ou por impossibilidade de medir o estado das variáveis,
históricos médicos seriam um bom exemplo disto.
O objetivo geral deste trabalho foi implementar e testar o algoritmo EM e suas variantes para aprendizagem em redes bayesianas de acordo com a topologia e parâmetros
disponı́veis, no caso de instâncias incompletas de dados. Especificamente:
• Implementar o algoritmo EM paramétrico de Lauritzen.
• Implementar o algoritmo EM estrutural de Friedman, utilizando duas métricas aproximadas.
• A partir de bancos de dados de redes bayesianas benchmark comparar os resultados
tanto no nı́vel de adequação à estrutura quanto a adequação das probabilidades.
• Através de uma revisão geral, obter o estado-da-arte da abordagem EM para redes
bayesianas.
5
1.2. Metodologia
1.2
dct-ufms
Metodologia
Para desenvolver um algoritmo de aprendizagem de estrutura e parâmetros a partir de
banco de dados incompletos sob o enfoque EM é necessário passar por uma série de etapas.
Devido ao fato que os algoritmos sendo considerados para implementação requeriam o
uso de inferência bayesiana para fazer estimativas dos estados não observados nos bancos
de dados incompletos, num primeiro estagio optou-se por desenvolver toda a estrutura
de dados que envolve uma rede bayesiana e implementar o algoritmo de árvore de junção
para a inferência. Porém, logo depois optou-se por aproveitar a API da ferramenta UnBBayes4 . Esta é uma ferramenta que oferece funcionalidades de inferência (algoritmo de
árvore de junção) e aprendizagem de redes bayesianas.
Contudo, esta ferramenta não oferece a possibilidade de aprendizagem a partir de
dados incompletos, tanto de parâmetros quanto de estrutura, e então considerou-se a possibilidade de acrescentar as classes que seriam desenvolvidas neste projeto ao UnBBayes,
ampliando assim sua funcionalidade.
Uma vez que se teve um conhecimento adequado da hierarquia de classes, das rotinas
principais e das estruturas fundamentais da UnBBayes é que iniciou-se, baseando-se nas
diretrizes de Lauritzen [46], a implementação do algoritmo EM paramétrico. A diferença
principal desta implementação é que os dados são completados no inicio do algoritmo, e
as sucessivas iterações somente estimam os novos valores faltosos.
Posteriormente, foi feita a implementação do algoritmo EM estrutural de Friedman[30].
O Passo E, aprendizagem de parâmetros, aproveitou a implementação do algoritmo EM
paramétrico de Lauritzen. O Passo M realiza uma busca de estruturas a partir de dados
completados no Passo E (supondo-os verdadeiros). As versões originais indicam que é
suficiente usar algoritmos gulosos de busca local como greedy hill climbing [42] na procura das estruturas. Esses algoritmos têm a desvantagem de freqüentemente encontrar só
ótimos locais. Assim, achou-se conveniente usar outro algoritmo heurı́stico para otimizar
esta tarefa, simulated annealing [42].
Existem algumas outras ferramentas disponı́veis para a comunidade acadêmica que
realizam inferência e aprendizagem em redes bayesianas. Netica5 e Hugin6 são as mais
conhecidas e usadas. Essas ferramentas foram usadas para geração de dados incompletos
de testes que seriam usados depois para a aprendizagem.
Particularmente, a Netica oferece uma versão de software limitada a poucas variáveis
4
Desenvolvida na Universidade de Brasilia - http://unbbayes.sourceforge.net/.
Netica 1.12 for windows - http://www.norsys.com/.
6
Hugin Lite 6.3 - http://www.hugin.com/.
5
6
1.3. Perspectivas Futuras
dct-ufms
e não oferece suporte para aprendizagem. Também permite gerar amostras de dados
incompletos, as quais foram usadas para realizar a maior parte dos testes, nas fases intermediárias e finais. No caso da ferramenta Hugin a versão avaliada também era limitada
a 500 instâncias e cerca de 10 variáveis, porém, uma implementação do algoritmo EM
paramétrico para dados incompletos estava disponı́vel, o que permitiu fazer comparações
simples.
Existem redes bayesianas reais, ou padrões, usadas pela comunidade cientı́fica a partir
das quais foram gerados dados com valores faltosos aleatórios para testes. Nas implementações iniciais foram usados dados de redes simples disponı́veis nas ferramentas Netica
e Hugin. Para comparações mais rigorosas foi usada a rede bayesiana ALARM [3] de
monitoração de pacientes anestesiados.
Em cada caso de dados de testes foram consideradas amostras com valores faltosos em
porcentagens de 10% e 30%. Para comparar com as redes padrões a adequação e exatidão
dos algoritmos de aprendizagem, foram usadas medidas padrões. A medida de divergência
Kullback-Leibler [36], ou entropia cruzada, permite medir a distância entre distribuições
de probabilidade, isto é, quanto aos seus valores numéricos. Esta foi usada para medir
a qualidade de aprendizagem de parâmetros obtida pelo algoritmo EM paramétrico. No
caso de aprendizagem de estrutura, a comparação com relação à rede bayesiana real foi
baseada no número de arcos corretamente inseridos ou faltosos.
1.3
Perspectivas Futuras
Os algoritmos EM implementados foram as primeiras soluções razoáveis para aprendizagem de estrutura e parâmetros a partir de dados incompletos [68]. Atualmente muitas
modificações foram feitas para melhorar seu desempenho. Por exemplo, para estimar os
dados faltosos usam-se métodos aproximados ou outras abordagens para completar os
dados [64]. Na busca de estruturas existem muitos algoritmos de otimização que podem
ser utilizados, resultados baseados em técnicas evolutivas têm sido usadas [51] e também
outros tipos de metaheurı́sticas. Mas todas essas soluções apresentam a abordagem do
algoritmo EM em sua forma geral e, especificamente, representam uma série de algoritmos
reunidos em um paradigma denominado busca e pontuação. O princı́pio desse paradigma
é gerar várias estruturas e escolher a melhor baseado na pontuação obtida com relação
aos dados.
Em um outro paradigma (independência condicional), avalia-se relações de dependência
que uma rede apresenta com relação aos dados. Esses algoritmos já demonstraram resultados alentadores em aprendizagem a partir de dados completos; também foram usados em
conjunção com algoritmos de busca e pontuação, porém, pouco trabalho tem sido desenvolvido para aprendizagem a partir de dados incompletos, sendo esta uma área promissora
e que poderia trazer soluções interessantes.
7
1.4. Organização do Texto
1.4
dct-ufms
Organização do Texto
No Capitulo 2 são apresentados os conceitos fundamentais da teoria da probabilidade incluindo o enfoque Bayesiano, distribuição de probabilidade conjunta, teorema de Bayes e,
além disso, apresenta-se a definição de redes bayesianas e algumas das suas caracterı́sticas
importantes.
No Capı́tulo 3 é descrito o processo de inferência em redes bayesianas e apresentase uma classificação dos tipos de algoritmos disponı́veis na literatura. Métodos exatos,
aproximados e simbólicos são descritos sucintamente, focalizando-se o algoritmo árvore
de junção usado na estimação de dados incompletos.
No Capı́tulo 4 é descrito o processo de aprendizagem em redes bayesianas, enfatizandose a utilização do algoritmo EM. Portanto, inicialmente, é dada a formulação geral deste
algoritmo. Depois é descrito o problema da aprendizagem de parâmetros para dados completos e incompletos. Neste último caso define-se o algoritmo EM de Lauritzen. Posteriormente, é definido o problema de aprendizagem de estruturas a partir de dados completos e
incompletos. Paradigmas para a escolha de estruturas e métricas são definidos para o caso
de dados completos. Para o caso de dados incompletos são descritos os dois algoritmos
de Friedman: MS-EM e EM estrutural.
No Capı́tulo 5 são detalhados aspectos da implementação dos algoritmos EM e resultados obtidos nos testes realizados. Especificamente, são descritos os dados usados, a
metodologia para avaliar os algoritmos, especificações dos algoritmos implementados e a
análise de resultados.
Finalmente, no Capı́tulo 6, são apresentadas conclusões inerentes ao trabalho realizado, destacando-se as dificuldades encontradas, perspectivas atuais, contribuições e
sugestões de trabalhos futuros.
8
Capı́tulo 2
Redes Bayesianas
A distribuição de probabilidade conjunta permite responder diversas questões sobre um
domı́nio de dados, mas a sua representação ocupa uma área que cresce exponencialmente
como o número de variáveis. Além disso, especificar as probabilidades de cada evento
em particular torna-se muito difı́cil, a menos que uma grande quantidade de dados esteja disponı́vel dos quais se possa obter estimativas estatı́sticas para essas probabilidades,
baseadas em freqüências relativas.
Na utilização do teorema de Bayes, a ocorrênciade independência condicional entre
variáveis aleatórias que descrevem os dados pode simplificar os cálculos para responder
perguntas e também reduzir consideravelmente o número de probabilidades condicionais
que precisam ser especificadas. A estrutura de dados chamada redes bayesianas representa a dependência entre as variáveis e dá uma especificação concisa da distribuição de
probabilidade conjunta.
O objetivo deste capı́tulo é introduzir conceitos da teoria da probabilidade (Seção
2.1), suas definições, axiomas, distribuições de probabilidade, Teorema de Bayes e as
distribuições multinomial e de Dirichlet (Seção 2.2) que são usadas na aprendizagem de
parâmetros de redes bayesianas. É dada uma definição formal de redes bayesianas (Seção
2.3), a qual servirá para fundamentar todo o trabalho, além de introduzir os conceitos
de inferência e aprendizagem em redes bayesianas, destacando-se os enfoques de busca e
pontuação e de independência condicional.
2.1
Fundamentos da Teoria da Probabilidade
Baseando-se no trabalho de da Silva e Ladeira [20], esta seção introduz conceitos da
teoria da probabilidade considerados relevantes para o entendimento dessa dissertação. O
leitor interessado em aprofundar seus conhecimentos pode consultar textos clássicos como
Degroot [24] e Bernardo (1994)apud [20] para o enfoque Bayesiano.
9
2.1. Fundamentos da Teoria da Probabilidade
2.1.1
dct-ufms
Experimento Aleatório, Espaço Amostral e Evento
Um experimento é um ensaio cientı́fico para a verificação de um fenômeno. Todas as vezes
que se estudam fenômenos de observação, cumpre-se distinguir o próprio fenômeno e o
modelo matemático (determinı́stico ou probabilı́stico) que melhor o explique.
Os fenômenos estudados pela Estatı́stica são aqueles cujo resultado, mesmo em condições normais de experimentação variam de uma observação para outra, dificultando
desta maneira a previsão de um resultado futuro. Para a explicação destes fenômenos
aleatórios — ou experimentais — adota-se um modelo matemático probabilı́stico.
Na realização de um experimento aleatório, o conjunto de todos os resultados possı́veis
é chamado de espaço amostral, aqui denotado por S. Os exemplos abaixo ilustram os
conceitos de experimento (ξ) e espaço amostral (S):
• Ex1 :
ξ1 = Jogue um dado e observe o número na face de cima.
S1 = {1, 2, 3, 4, 5, 6}
• Ex2 :
ξ2 = Jogue uma moeda 4 vezes e observe a seqüência de caras (H) e coroas (T)
S2 = {HHHH, HHHT, HHT H, HHT T, HT HH, HT HT, HT T H, HT T T,
T HHH, T HHT, T HT H, T HT T, T T HH, T T HT, T T T H, T T T T }
Um experimento aleatório pode ser repetido indefinidamente sob condições inalteradas; e em cada um dos experimentos não se sabe, a priori, qual resultado individual
ocorrerá. Embora se possa definir o conjunto de todos os possı́veis resultados, cada resultado individual parece ocorrer de forma acidental. Com a repetição em larga escala surge
uma regularidade que permite construir um modelo matemático para analisar o experimento. Por exemplo, as proporções de caras e coroas, após lançar uma moeda honesta um
grande número de vezes, são aproximadamente iguais. Isto faz com que se crie o modelo
que para cara atribui probabilidade 1/2 e para coroa atribui probabilidade 1/2.
Um evento é um subconjunto dos resultados possı́veis de um experimento. O espaço
amostral é em si um evento, também. Se S é um espaço amostral e A ⊆ S então A é um
evento. Um evento ocorre se um dos seus elementos ocorre:
a) Se x ∈ A ocorre, então A ocorre.
b) Se x ∈ (A ∩ B) ocorre, então A e B ocorrem.
Por exemplo, seja S = {1, 2, 3, 4, 5, 6}, então S é um evento e também são eventos:
10
dct-ufms
a) A = {2, 4, 5} e Ac = {1, 3, 6};
b) B = {1, 3, 5} e B c = {2, 4, 6}.
2.1.2
Frequência Relativa
Se um experimento ξ é repetido n vezes, então é possı́vel calcular a freqüência relativa
fA de qualquer evento A do espaço amostral S associado ao experimento ξ. Seja nA o
número de vezes que o evento A ocorre nas n repetições de ξ, calcula-se fA = nA /n.
Sejam A e B eventos de S, suas freqüências relativas apresentam as seguintes propriedades:
a) 0 ≤ fA ≤ 1,
b) fA = 1, se nA = n,
c) fA = 0, se nA = 0,
d) fA∪B = fA + fB , se A ∩ B = φ.
2.1.3
Axiomas da Probabilidade
Dado um experimento aleatório qualquer, descrito pelo espaço amostral S, a teoria da
probabilidade está baseada em uma função P que, a cada evento A de S associa um
número real no intervalo [0, 1], representado por P (A), denominado probabilidade do
evento A, que satisfaz as seguintes propriedades:
a) P (S) = 1;
b) Se A e B são eventos disjuntos de S, então P (A ∪ B) = P (A) + P (B);
c) Se A1 , A2 , . . . , An é uma famı́lia de eventos de S, dois a dois disjuntos, então P (A1 ∪
A2 ∪ . . . ∪ An ) = P (A1 ) + P (A2 ) + . . . + P (An ).
Muitas propriedades importantes podem ser extraı́das dos axiomas acima. Por exemplo:
d) P (φ) = 0;
e) Se A ⊆ B ⊆ S, então P (A) ≤ P (B);
f ) Se A, B ⊆ S, então P (A ∪ B) = P (A) + P (B) − P (A ∩ B);
g) Se A ⊆ S, então 0 ≤ P (A) ≤ 1.
11
2.1.4
dct-ufms
Definição Freqüentista de Probabilidade (Intuitiva) - “A
Posteriori”
Quando o número de repetições do experimento tende para o infinito observa-se uma certa
regularidade estatı́stica que permite definir a probabilidade do evento. Esta regularidade
se manifesta quando a freqüência relativa fA se estabiliza em torno de um valor no intervalo [0, 1], para toda A ⊆ S associado ao experimento, a medida que n cresce ficando muito
grande. Segundo este ponto de vista objetivista, as probabilidades são aspectos reais do
universo — propensão dos objetos a se comportarem de certa maneira — e não descrições
do grau de crença de um observador. Deste ponto de vista, os cálculos freqüentistas são
tentativas de observar o valor real de uma probabilidade.
No modelo freqüentista para a teoria da probabilidade, considera-se que uma distribuição de probabilidades para os eventos A do espaço amostral S pode ser obtida
tomando-se P (A) como o limite das freqüência relativas fA , isto é,
P (A) = lim fA = lim nA /n
n→∞
n→∞
(2.1)
No contexto frequentista, formalmente, só se pode falar de probabilidade para eventos
associados a um experimento passı́vel de repetição. Do ponto de vista matemático, essa
definição de probabilidade apresenta dificuldades, porque um número limite real pode
não existir na realidade. Assim, a formalização da definição não obedece rigorosamente
à teoria matemática de limite. Isto trás como conseqüência a dificuldade em demonstrar
os teoremas de probabilidade, muito embora esta definição seja bastante intuitiva. A
denominação “a posteriori” resulta do fato de se ter de repetir a experiência várias vezes
para poder calcular a probabilidade.
2.1.5
Definição Clássica de Probabilidade (Laplace) - “A Priori”
Dada um experiência aleatória uniforme, definida em um espaço de amostragem S, definese a probabilidade de ocorrer um evento A, contido em S, como sendo o quociente entre
o número de elementos do evento A, nA , e o número de elementos do espaço amostral S,
nS , isto é,
nA
(2.2)
P (A) =
nS
Embora esta definição seja bastante intuitiva também, tem algumas limitações sérias:
a) Existe dificuldade, muitas vezes, de se identificar e enumerar os casos favoráveis e
possı́veis, por exemplo, nas experiências que os resultados tenham caráter qualitativo
e/ou não se pode efetuar contagens;
b) Esta definição não depende da experiência, para que se concretize realmente o que é
idealizado, daı́ o nome “priori”;
12
dct-ufms
c) No caso em que o espaço amostral tiver infinitos elementos, não terá sentido falar em
nS ;
d) Não estabelece um critério para casos igualmente possı́veis, pois partindo da hipótese
que a experiência é uniforme (todos os resultados são equiprováveis), define-se probabilidade por aquilo exatamente que se quer definir.
Esta definição, ao contrário da freqüentista, estabelece um modelo matemático adequado à interpretação de uma certa classe de fenômenos (não todos), e considera-se o seu
comportamento ideal em condições ideais.
No trabalho com redes bayesianas a frequência com que os valores das variáveis aparecem nos dados é usada para estimar as probabilidades a posteriori. Especificamente a
distribuição de Dirichlet usa essas freqüências (também denominadas contagens suficientes) para aproximar as distribuições multinomiais condicionais das variáveis.
2.1.6
Variáveis Aleatórias e Proposições
Uma variável aleatória (va) X tem natureza funcional, X : S → Sx . Ela associa a cada
elemento do espaço amostral S um elemento de seu contradomı́nio, SX ⊂ R, onde R é o
conjunto dos números reais.
Como exemplo: seja ξ o experimento de lançar duas moedas honestas e verificar
o número de caras (H), X a va que indica o número de caras obtido no experimento ξ. S = {HH, HT, T H, T T } é o espaço amostral associado a ξ e SX = {0, 1, 2}
é o conjunto de possı́veis valores de X, pois, tomando-se X : S → SX , tem-se que:
X(HH) = 2, X(HT ) = X(T H) = 1 e X(T T ) = 0.
Embora X tenha natureza funcional, é comum ignorar tal natureza e considerar apenas que X assume um dos possı́veis valores do seu contradomı́nio SX , que passa a ser
denominado domı́nio de X. A probabilidade é definida no domı́nio de X, por exemplo:
P (X = 0) = P (T T ) = 1/4, P (X = 1) = P (HT ou T H) = 2/4 e P (X = 2) = P (HH) =
1/4. Estes números estão de acordo com a definição freqüentista, conforme experiência
que se pode realizar, e também clássica, de probabilidade.
Também pode-se pensar de uma variável aleatória como sendo o atributo de uma entidade (por exemplo, idade de uma pessoa), ou como a resposta a uma pergunta (por
exemplo, jaá visitou a Ásia?). No primeiro caso, considerando apenas número completo
de anos, tem-se o conjunto {0, 1, . . . , 120} como domı́nio e no segundo caso sim, nao.
Diz-se que uma va X é discreta se o seu domı́nio SX é um conjunto enumerável de
valores. As assertivas do tipo X = 0, X < 2, são proposições que podem ser tanto
verdadeiras quanto falsas. A expressão P (X < 2), representa a probabilidade da variável
13
dct-ufms
X assumir um valor menor do que 2, isto é, a probabilidade da proposição X < 2 ser
verdadeira.
2.1.7
Distribuição Conjunta, Marginal e Condicional
Seja X uma va e DX o seu domı́nio. Os valores P (X = x), para todas as instâncias x em
Dx , constituem a distribuição de probabilidade de X. Por exemplo, seja X o resultado de
lançar um dado não viciado, então DX = {1, 2, 3, 4, 5, 6} é o domı́nio de X. A distribuição
de probabilidade de X é dada por P (X = x) = 1/6, para todo x em DX .
Dado duas va X e Y , a distribuição de probabilidade de X e Y constitui uma distribuição conjunta de X e Y . Por exemplo: considere os computadores pessoais (PCs) de
uma empresa. Seja X o sistema operacional, DX = {windows, linux} o domı́nio de X
e Y a marca do processador, DY = {AM D, Intel} o domı́nio de Y . A parte interna da
Tabela 2.1 dá a distribuição conjunta de X e Y .
Tabela 2.1: Distribuição conjunta de sistema operacional × processador [20].
Y
AM D
Intel
Marginal de X
X
windows linux Marginal de Y
0.18
0.12
0.30
0.42
0.28
0.70
0.60
0.40
1.00
Tomando P (X = x, Y = y) = P (x, y), pode-se constatar na Tabela 2.1 que
P (windows, AM D) = 0.18; P (windows, Intel) = 0.42; P (linux, AM D) = 0.12 e
P (linux, Intel) = 0.28.
Nesse contexto de distribuição conjunta, faz sentido falar de distribuição marginal,
aquela distribuição de uma das variáveis do conjunto, que na Tabela 2.1 fica em uma
das margens. Na Tabela 2.1, a distribuição marginal de Y é dada pela última coluna: P (Y = AM D) = 0.30; e P (Y = Intel) = 0.70. E a distribuição marginal de X:
P (X = windows) = 0.60 e P (X = linux) = 0.40.
A expressão X|Y representa a variável X condicionada ao conhecimento de um valor
para Y e P (X = x|Y = y) = P (x|y), para todo x em DX , representa a distribuição de
probabilidade condicional de X dado que Y = y. A Equação 2.3
P (x|y) = P (x, y)/P (y)
(2.3)
confirma que a distribuição de X fica restrita ao contexto Y = y, pelo que P (y) funciona
como um fator de normalização.
14
dct-ufms
Na Tabela 2.1, P (X = windows|AM D) = P (windows, AM D)/P (AM D) = 0.18/0.3,
P (X = linux|AM D) = P (linux, AM D)/P (AM D) = 0.12/0.3 e P (X = windows|Intel)
= P (windows, Intel)/P (Intel) = 0.42/0.70, P (X = linux|Intel) =P (linux, Intel)
/P (Intel) = 0.28/0.70.
Dado que P (x|y) = P (x, y)/P (y), pode-se expressar a conjunta como o produto da
condicional pela marginal, conforme Equação 2.4.
P (x, y) = P (x|y)p(y)
(2.4)
A Equação 2.4 é a chamada regra do produto. Esta regra pode ser generalizada para
se obter a fórmula da regra da cadeia. Dado que X = {X1 , X2 , . . . , Xn } é um conjunto
de variáveis aleatórias, então a distribuição conjunta de X é dada pela Equação 2.5.
P (x1 , x2 , . . . , xn ) =
n
Y
P (xi |x1 , . . . , xi−1 )
(2.5)
i=1
2.1.8
Independência Condicional
Diz-se que duas variáveis X e Y são independentes se
P (x|y) = P (x)
(2.6)
sempre que P (y) > 0, ∀x ∈ DX e y ∈ DY . Se X e Y são independentes, então Y não é
informativa para X. Significa que conhecer Y não altera a probabilidade de X.
Pode-se expressar essa independência em termos da distribuição conjunta de X e Y ,
derivada da regra do produto, como P (x, y) = P (x)P (y). A Tabela 2.1 exibe X e Y como
variáveis independentes, pois este produto é válido para todo (x, y).
Uma outra maneira de fazer esse teste de independência é usar a medida de informação
mútua, dada pela Equação 2.7 abaixo:
I(X, Y ) =
XX
x
P (x, y) log
y
P (x, y)
P (x)P (y)
(2.7)
Essa relação é reflexiva, I(X, Y ) = I(Y, X). Se I(Y, X) > 0, então X e Y são informativas uma para a outra, isto é, são dependentes; em caso contrário, X e Y são
independentes. É fácil ver que se X e Y são independentes, o argumento da função log
na Equação 2.7, é igual a 1, para todos os valores de X e Y , o que leva o somatório ao
valor 0 (zero).
15
2.2. Modelo Bayesiano de Probabilidade (Subjetivo)
dct-ufms
Dado um conjunto de variáveis aleatórias Z, não contendo X e nem Y , pode-se também
usar a medida de informação mútua condicional para verificar se X e Y são condicionalmente independentes, conforme a Equação 2.8 abaixo:
XXX
P (x, y|z)
I(X, Y |Z) =
P (x, y, z) log
(2.8)
P (x|z)P (y|z)
z
x
y
Como no caso anterior, se I(X, Y |Z) = I(Y, X|Z) > 0, então X e Y são condicionalmente dependentes dado Z, e são condicionalmente independentes em caso contrário.
Em termos probabilı́sticos, se P (x|y, z) = P (x|z), então conhecido Z, conhecer Y não
informa nada para X. Isto é, X é independente de Y dado Z. Também é verdade que
P (x, y|z) = P (x|z)P (y|z), se X e Y são independentes, dado Z.
2.2
Modelo Bayesiano de Probabilidade (Subjetivo)
O modelo Bayesiano interpreta a probabilidade de uma proposição como o grau de crença
de um agente na veracidade dessa proposição. Por exemplo, um dentista pode dizer: na
minha opinião, eu espero que a probabilidade de cárie seja aproximadamente 0.1. P (A|W )
é o grau de crença do agente na veracidade da proposição A, dado sua experiência e conhecimento W . Nesse sentido, toda probabilidade é condicionada ao conhecimento do agente,
diferentemente do enfoque freqüentista em que se considera as probabilidades como sendo
aspectos reais do universo não dependentes do conhecimento do agente.
Doravante, ao falar em probabilidade se estará falando dela na acepção bayesiana de
graus de crença de um agente.
2.2.1
Teorema de Bayes
O coração da inferência Bayesiana repousa sobre a celebrada fórmula da inversão, também
chamada de Teorema de Bayes, dado pela equação abaixo:
P (H|e) =
P (e|H)P (H)
P (e)
(2.9)
onde P (H) é a probabilidade a priori de H; P (H|e) é a probabilidade a posteriori de H,
isto é, a probabilidade de H após conhecer a evidência e; P (e|H) é a verossimilhança da
evidência e dado a hipótese H, e P (e) é um fator de normalização.
Dado que P (H|e) + P (¬H|e) = 1, tem-se que P (e|H)P (H) + P (e|¬H)P (¬H) = P (e).
Deste modo, pode-se expressar a fórmula da inversão em termos proporcionais, sem o
fator de normalização P (e), como na equação abaixo:
P (H|e) ∝ P (e|H)P (H)
16
(2.10)
2.2. Modelo Bayesiano de Probabilidade (Subjetivo)
dct-ufms
Em outros termos Posteriori ∝ Verossimilhança ∗ P riori.
2.2.2
Distribuição Multinomial e de Dirichlet
Seja X uma va discreta com domı́nio DX = {x1 , x2 , . . . , xr } com P (X = xk ) = pk .
Suponha que seja dada uma amostra aleatória D = {X1 = x1 , X2 = x2 , . . . , XN = xN },
com N observações Xi independentes e identicamente distribuı́das (iid) a X, onde cada
xi é uma instância de Xi , com xi ∈ DX . Seja Y = (Y1 , Y2 , . . . , Yr ) um vetor aleatório
tal que yk é o número de vezes que o estado xk de X está presente na amostra D, e
y1 + y2 + . . . + yr = N , onde yk é uma instância de Yk . Nesse caso, diz-se que Y tem
distribuição amostral multinomial com função de distribuição (fd) dada pela Equação
2.11.
N!
P (y|N, p) =
py1 py2 . . . pyr r
(2.11)
y1 !y2 ! . . . yr ! 1 2
Observe que p = (p1 , p2 , . . . , pr ) é o vetor de probabilidades da distribuição, tido como
conhecido. Pode-se dizer que o termo N !/(y1 !y2 ! . . . yr !) na Equação 2.11 é apenas um
normalizador. Nesses termos, pode-se redefinir a fd da multinomial como na Equação
2.12, sem o termo normalizador.
P (y|N, p) ∝ py11 py22 . . . pyr r
(2.12)
Seja p = (p1 , p2 , . . . , pr ) um vetor de reais desconhecido tal que p1 + p2 + . . . + pr = 1
e pi > 0, para todo i entre 1 e r. Então p tem distribuição Dirichlet, com fd dada pela
Equação 2.13 e vetor de parâmetros α = (α1 , . . . , αr ) com αi > 1 e E(Pi ) = αi /α0 onde
α0 = α1 + α2 + . . . + αr .
f (p|α) =
Γ(α0 )
pα1 −1 pα2 2 −1 . . . pαr r −1
Γ(α1 )Γ(α2 ) . . . Γ(αr ) 1
(2.13)
onde Γ(·) é a função Gamma que satisfaz Γ(x + 1) = xΓ(x) e Γ(1) = 1.
Na Equação 2.13 o fator Γ(α0 )/Γ(α1 )Γ(α2 ) . . . Γ(αr ) tem propósito normalizador. Podese expressar a fd da Equação 2.13 como em (2.14), em termos proporcionais. Observe a
similaridade da (2.14) com a Equação 2.12.
f (p|α) ∝ pα1 1 −1 pα2 2 −1 . . . prαr −1
(2.14)
A famı́lia de distribuições de Dirichlet é uma famı́lia conjugada para amostras com distribuição multinomial. Seja Y com distribuição Multinomial(N, p) com o vetor de probabilidades p desconhecido, nesse caso p tem distribuição a priori de Dirichlet(p|α1 , α2 , . . . , αr ),
dada pela Equação 2.14, com média E(pi ) = αi /α0 . A distribuição a posteriori de p é
proporcional a P (Y |N, p)f (p|α), conforme Equação 2.15:
f (p|α + y) ∝ P (y|N, p)f (p|α)
∝ (P1y1 P2y2 . . . Pryr )(P1α1 −1 P2α2 −1 . . . Prαr −1 )
∝ P1y1 +α1 −1 P2y2 +α2 −1 . . . Pryr +αr −1
17
(2.15)
2.3. Redes Bayesianas
dct-ufms
Assim, a distribuição a posteriori de p tem distribuição de Dirichlet(p|α1 + y1 , α2 +
y2 , . . . , αr + yr ), com média E(p|y) = (αi + yi )/(α0 + N ), onde y = (y1 , y2 , . . . , yr ) é
uma instância de Y , e N = y1 + y2 + . . . + yr . Olhando a Equação 2.14 pode-se perceber
que tomar os α’s iguais a 1 leva a uma distribuição de média, tanto a priori quanto a
posteriori:
a) E(pi ) = αi /α0 = 1/r;
b) E(p|y) = (αi + yi )/(α0 + N ) = (1 + yi )/(r + N ).
2.3
Redes Bayesianas
Nesta seção é dada uma definição de rede bayesiana (RB) e através de um exemplo
ressaltam-se suas funcionalidades: como se pode obter a expressão de uma distribuição
de probabilidade conjunta? Como visualizar assertivas de dependência e independência
e fazer inferências?. Apresenta-se, de maneira resumida, dois enfoques de aprendizagem
de estrutura e de parâmetros de RBs baseando-se numa amostra aleatória dos dados do
domı́nio de interesse, um deles busca maior aderência da rede aos dados, e o outro a
melhor representação da distribuição conjunta subjacente a amostra.
2.3.1
Definição de Rede Bayesiana
Uma rede bayesiana, segundo Castillo et al [8], é um formalismo que mistura a teoria dos
grafos e a teoria da probabilidade. Nesse sentido, uma RB tem dois componentes principais: a) uma estrutura, S, que define relacionamento qualitativo causal entre os nós, e b)
parâmetros numéricos, Θ, que quantificam a relação probabilı́stica causal entre os nós da
estrutura.
Uma RB representa uma distribuição conjunta de probabilidade P sobre um conjunto
de variáveis aleatórias X = {X1 , X2 , . . . , Xn }. Pode-se falar de uma RB para X como
tendo uma estrutura S que codifica as assertivas de independência condicional sobre as
variáveis em X e de um conjunto, instância de Θ, de distribuições locais de probabilidades
associadas às variáveis em X. Juntos, a estrutura S e os parâmetros Θ definem uma
distribuição de probabilidades conjunta, tal que:
1. S é uma grafo acı́clico orientado (GAO);
2. Os nós em S estão numa relação 1-1 com as variáveis em X;
3. Cada variável Xi , em X denota uma variável e também o correspondente nó em S;
4. P ai denota os nós pais de Xi e também as variáveis correspondentes a esses pais;
18
dct-ufms
5. A distribuição conjunta de X é dada por
P (x) =
n
Y
P (xi |pai )
(2.16)
i=1
onde x é uma instância de X, pai é uma instância de P ai e, particularmente,
pai ⊂ {x1 , x2 , . . . , xi−1 }, onde {x1 , x2 , . . . , xi−1 } é o termo condicionante na regra da
cadeia, conforme Equação 2.5.
A Figura 2.1 embora represente uma situação fictı́cia e improvável, ilustra bem os
conceitos pretendidos na definição acima. Nela, pretende-se estabelecer a influência causal
da Variável Fraude (Cartão Fraudado), Idade e Sexo sobre compras de Gasolina e Jóias.
O conjunto de variáveis X = {F raude, Idade, Sexo, Gasolina, Joias} retrata as variáveis
do modelo; os cı́rculos representam tanto os nós da rede quanto as variáveis do conjunto
X; os arcos representam o relacionamento causal entre as variáveis; e os parâmetros
numéricos são representados pelas distribuições marginais ou condicionais do modelo e
que são dadas nas Tabelas 2.2, 2.3, 2.4, 2.5 e 2.6. A distribuição conjunta das variáveis
do modelo pode ser expressa via
P (F raude, Idade, Sexo, Gasolina, Joias) = P (F raude)P (Idade)
P (Sexo)P (Gasolina|F raude)
P (Joias|F raude, Idade, Sexo)
lembrando que Fraude influencia a compra de Gasolina, e que Fraude, Idade e Sexo, conjuntamente, influenciam a compra de Jóias.
F
I
G
S
J
Figura 2.1: Estrutura de rede bayesiana para detecção de problemas de fraude: F =
Fraude; I = Idade; S = Sexo; G = Gasolina; J = Jóias.
Tabela 2.2: P (F ).
P(F=F) P(F=V)
0.99999 0.00001
2.3.2
Tabela 2.3: P (I).
P(I=< 30)
0.25
P(I=30 − 50)
0.40
P(I=> 50)
0.35
O Problema da Inferência
Suponha que para o problema de detecção de fraude queira se conhecer a probabilidade de
fraude dadas as observações das outras variáveis, esta probabilidade não está armazenada
19
dct-ufms
Tabela 2.5: P (G|F ).
Tabela 2.4: P (S).
F
F
V
P(S=Feminino) P(S=Masculino)
0.5
0.5
P(G=F)
0.99
0.8
P(G=V)
0.01
0.2
Tabela 2.6: P (J|F, I, S).
F
I
S
F
< 30
F
V
< 30
F
F
< 30
M
V
< 30
M
F 30 − 50 F
V 30 − 50 F
F 30 − 50 M
V 30 − 50 M
F
> 50
F
V
> 50
F
F
> 50
M
V
> 50
M
P(J=F) P(J=V)
0.9995
0.0005
0.95
0.05
0.9999
0.0001
0.95
0.05
0.998
0.002
0.95
0.05
0.9996
0.0004
0.95
0.05
0.999
0.001
0.95
0.05
0.9998
0.0002
0.95
0.05
diretamente no modelo e é necessário calculá-la. O cálculo das probabilidades pode ser
realizado mediante uma simplificação e fatorização de variáveis:
P (F |I, S, G, J) =
P (F, I, S, G, J)
P (F, I, S, G, J)
=P
P (I, S, G, J)
F P (F = f, I, S, G, J)
Dadas as independências condicionais a equação acima pode ser expressa como:
P (F )P (I)P (S)P (G|F )P (J|F, I, S)
F P (F = f )P (I)P (S)P (G|F = f )P (J|F = f, I, S)
P (F )P (G|F )P (J|F, I, S)
= P
F P (F = f )P (G|F = f )P (J|F = f, I, S)
P (F |I, S, G, J) = P
A partir desta simplificação, substituem-se os valores das probabilidades e eliminam-se,
seguindo uma ordem especı́fica, as variáveis I, S, G, J (maiores detalhes serão apresentados no Capı́tulo 3).
Como apresentado no exemplo precedente, a tarefa fundamental para qualquer sistema
de inferência probabilı́stica é calcular a distribuição de probabilidade a posteriori para um
conjunto de variáveis, dado o valor exato de alguma outra variável. Russell e Norving [61]
denominam as primeiras “variáveis consulta” e as últimas “variáveis evidência”. Deste
modo o sistema calcula P (Consulta|Evidencia). Redes bayesianas são flexı́veis a ponto
de qualquer nó poder servir como “consulta” ou como “evidência”.
20
dct-ufms
Charniak [9] especifica que, em diagnósticos médicos baseados nos sintomas apresentados pelos pacientes, usa-se o raciocı́nio ascendente, isto significa que progride dos efeitos
às causas. Esta é uma tarefa comum também em sistemas especialistas. Mas as RBs
também podem ser utilizadas para o raciocı́nio causal descendente, ou predição; por isto,
às vezes, são nomeadas de modelos “geradores” porque especificam como as causas geram
efeitos.
A questão da inferência será revista no Capı́tulo 3, enfatizando-se em algoritmos utilizados dentro de aprendizagem de RBs.
2.3.3
O Problema da Aprendizagem
Os dois componentes de uma RB — a estrutura gráfica S e os parâmetros numéricos Θ
— podem ser aprendidos indutivamente a partir de dados. Primeiro deve-se induzir a
estrutura S, e a seguir, com a estrutura conhecida, se aprende os parâmetros numéricos
Θ. Se a estrutura já é conhecida, então o problema se restringe a aprender os parâmetros
numéricos. Enquanto a aprendizagem de parâmetros é relativamente simples, a aprendizagem de estrutura é um assunto, em geral, complexo e ainda não está bem resolvido.
A indução automática da estrutura da rede mais aderente aos dados enfrenta um
problema de explosão combinatória [20]. O espaço de busca para uma rede com n variáveis tem uma dimensão mais que exponencial. A cardinalidade desse espaço, isto é, a
quantidade de redes candidatas é dada pela Equação 2.17, derivada por Robinson (1977)
apud [20]. Para se ter uma idéia, com apenas 10 variáveis, a quantidade de redes do
espaço de busca é f (10) = 4.2 × 1018 , um número extremamente grande.
f (n) =
n
X
i=1
(−1)i+1
n!
f (n − i)
(n − i)!i!
(2.17)
Além da barreira combinatória, existe o fato de que geralmente não se pode derivar
causalidade baseada apenas numa distribuição de probabilidade [57]. Embora esse seja
um assunto de intensas pesquisas, não se chegou à solução definitiva do problema. Hoje
se convive com dois enfoques básicos para aprendizagem de estrutura de redes bayesianas:
busca e pontuação e independência condicional.
A essência do enfoque de busca e pontuação consiste na escolha de uma métrica para
pontuar a aderência de cada rede aos dados e de um algoritmo para selecionar, dentre as
redes possı́veis do espaço de busca, aquelas mais promissoras. Uma visão detalhada desse
enfoque pode ser vista em Castillo et al [8]; uma visão geral é dada por Heckerman [34]; e
um caso especı́fico e pioneiro é proposto por Cooper e Herskovits [18] em termos de uma
métrica e de um algoritmo chamado K2. Esse algoritmo exige que o especialista informe
a ordem total das variáveis. Essa ordem permite ao algoritmo evitar circularidade na rede
21
dct-ufms
e inferir a orientação dos arcos.
No enfoque de independência condicional, busca-se uma rede que melhor represente
a distribuição conjunta subjacente à amostra aleatória. Tal rede deve representar todas
as assertivas de dependência e independência presentes na distribuição conjunta induzida
pela amostra.
Os algoritmos EM para aprendizagem de estrutura implementados usam as diretrizes
do enfoque de busca e pontuação. Detalhes deste tipo de algoritmos são dados no Capı́tulo
4, onde é revisto o problema da aprendizagem.
2.3.4
Por que usar Redes Bayesianas?
Dentre os motivos para se usar RB tem-se que (a) uma RB permite expressar as assertivas de independência de forma visual e fácil de perceber; (b) uma RB representa e
armazena uma distribuição conjunta de forma econômica, explorando a esparcidade do
relacionamento entre as variáveis; e (c) uma RB torna o processo de inferência eficiente
computacionalmente [20].
Redes bayesianas permitem analisar grandes quantidades de dados: para extrair conhecimentos úteis em tomada de decisões; controlar ou prever o comportamento de um
sistema; diagnosticar as causas de um fenômeno; etc. Utilizadas em vários domı́nios:
saúde (diagnóstico, localização de genes); indústria (controle de autômatos ou de robôs);
computação e redes (agentes inteligentes); marketing (mineração de dados, gestão da relação com os clientes); banca e finanças (análise financeira); gestão (tomada de decisões,
gestão de conhecimento e risco). Exemplos de aplicações especı́ficas podem ser encontradas em [31, 35].
De acordo com o tipo de aplicação, a utilização prática de uma RB pode ser considerada da mesma maneira que modelos como: redes neurais, sistemas especialistas, árvores
de decisão, modelos para análise de dados (regressão linear), modelos lógicos, etc. Naturalmente, na escolha do método intervém diferentes critérios, como a facilidade, o custo e
a demora na implantação de uma solução. Segundo Naim et al [52] os seguintes aspectos
das RBs as fazem preferı́veis sobre outros modelos:
• Aquisição de conhecimentos. A possibilidade de juntar e fusionar conhecimentos de
naturezas diversas num mesmo modelo: dados históricos ou empı́ricos, experiência
(expressa na forma de regras lógicas, de equações, de estatı́sticas ou de probabilidades subjetivas), observações. Por exemplo, no mundo industrial, cada uma das
fontes de informação, embora presente, é amiúde insuficiente para fornecer uma
representação precisa e realista do sistema analisado.
• Representação de conhecimentos. A representação gráfica de uma RB é explicita,
22
2.4. Considerações Finais
dct-ufms
intuitiva e compreensı́vel para uma pessoa não especialista, o que por sua vez,
facilita a validação do modelo, suas evoluções eventuais e sobretudo a sua utilização.
Tipicamente, um decisor é mais confiante sobre um modelo no qual ele compreende
o funcionamento, do que num modelo tipo “caixa preta”.
• Utilização de conhecimentos. Uma RB é multifuncional: pode-se usar o mesmo
modelo para avaliar, prever, diagnosticar, ou otimizar as decisões, o que contribui a
“rentabilizar” o esforço gasto na construção da RB.
• Qualidade da oferta com relação aos programas: hoje existe inúmeros programas
para aproveitar e tratar as RBs. Estas ferramentas apresentam funcionalidades mais
ou menos evoluı́das: aprendizagem de probabilidades, aprendizagem da estrutura da
RB, possibilidade de integrar variáveis contı́nuas, variáveis de utilidade e de decisão,
etc.
Comparação com Outras Técnicas
Do ponto de vista das aplicações, as vantagens e inconvenientes das RBs com relação
a algumas técnicas alternativas são apresentadas na Tabela 2.7. Nela Naim et al [52]
agruparam as vantagens e inconvenientes baseando-se em três critérios: aquisição, representação e utilização do conhecimento. A representação adotada é a seguinte:
• Cada linha corresponde com uma caracterı́stica, que pode ser uma vantagem ou a
identificação de um problema especı́fico.
• Se a técnica considerada permite lidar com esse problema, ou apresenta vantagem,
um sı́mbolo + é colocado no caso correspondente.
• Um sı́mbolo F indica a melhor técnica do ponto de vista da caracterı́stica considerada.
2.4
Considerações Finais
O objetivo deste capı́tulo foi definir conceitos importantes para a compreensão das definições e algoritmos apresentados nesta dissertação. Foram revistas noções da teoria da
probabilidade e definidas as redes bayesianas. Também foram descritas algumas vantagens
de se usar redes bayesianas em comparação com outras técnicas alternativas. Inferência e
aprendizagem em redes bayesianas foram abordadas sucintamente, esses conceitos serão
aprofundados em capı́tulos posteriores.
23
2.4. Considerações Finais
dct-ufms
Tabela 2.7: Vantagens comparativas das redes bayesianas.
Conhecimentos
AQUISIÇÃO
Só experiência
Só dados
Misto
Incremental
Generalização
Dados incompletos
REPRESENTAÇÃO
Incerteza
Clareza
Facilidade
Homogeneidade
UTILIZAÇÃO
Requisitos elaborados
Utilidade econômica
Desempenho
Análise
de
dados
Redes
neurais
Árvores
de
decisão
Sistemas Redes
especia- bayesialistas
nas
F
+
+
+
F
+
+
F
+
+
+
+
+
+
F
F
+
F
+
+
F
+
+
F
F
F
+
+
+
+
+
F
24
F
F
Capı́tulo 3
Inferência em Redes Bayesianas
Uma vez construı́da uma representação probabilı́stica através do modelo de RBs, para a
incerteza presente no relacionamento entre variáveis de um domı́nio de dados, uma das
tarefas mais importantes consiste em obter estimativas de probabilidades de eventos relacionados aos dados, à medida que novas informações ou evidências sejam conhecidas.
Esse processo é denominado inferência em redes bayesianas.
No capı́tulo anterior foi dada a definição de RB, apresentando-se algumas das suas
principais funcionalidades. A inferência em RBs, mediante o cálculo das probabilidades a
posteriori, permite responder a uma série de “consultas” ou “queries” sobre um domı́nio
de dados modelado através das RBs, a partir de nova informação (evidência) conhecida.
O objetivo deste capı́tulo é apresentar, de maneira formal, conceitos relativos à inferência
em RBs, assim como detalhar esse processo. Pode-se fazer uso de métodos exatos (Seção
3.1) e, em situações em que os métodos exatos não sejam os mais apropriados, podese usar os métodos aproximados (Seção 3.2) e, alternativamente, os métodos simbólicos
(Seção 3.3), que apresentam algumas vantagens que podem ser aproveitadas.
A importância da inferência bayesiana não fica restrita ao cálculo de probabilidades
interessantes à luz de novas evidências, podendo-se também tirar proveito da sua funcionalidade no processo de aprendizagem de RBs. O objetivo deste trabalho é implementar
um método de aprendizagem de RBs — de estrutura e de parâmetros — a partir de dados incompletos, onde a inferência é utilizada para estimar valores faltosos na amostra de
dados. Portanto, neste capı́tulo detalha-se o algoritmo de árvore de junção (Seção 3.1.3),
utilizado na implementação dos algoritmos de aprendizagem desse trabalho.
Por exemplo, na área médica, a principal tarefa consiste em obter um diagnóstico
para um determinado paciente apresentando certos sintomas (evidências). O mecanismo para se obter essa conclusão a partir de evidências é denominado propagação de
evidências [8, 56]. Esta tarefa consiste em atualizar as probabilidades das variáveis em
função das evidências. No caso do diagnóstico médico, tenta-se conhecer as probabilidades de cada uma das possı́veis doenças, dados os sintomas observados no paciente. Essas
25
3.1. Métodos Exatos
dct-ufms
são probabilidades a posteriori.
Segundo Castillo et al [8] há três tipos distintos de algoritmos de propagação: exatos,
aproximados e simbólicos. Um algoritmo de propagação denomina-se exato se as probabilidades dos nós são calculadas sem outro erro senão o de arredondamento, inerente à
limitações de cálculo dos computadores. Os algoritmos de propagação aproximada utilizam distintas técnicas de simulação para obter valores aproximados das probabilidades.
Em geral, estes algoritmos são utilizados em casos em que os algoritmos exatos não são
aplicáveis, ou o custo computacional é elevado. Já os algoritmos de propagação simbólica
podem operar tanto com parâmetros numéricos quanto com parâmetros simbólicos, obtendo probabilidades na forma simbólica, em função dos parâmetros.
A seguir são descritos cada um desses métodos, contudo a ênfase será dada aos métodos
exatos, que apresentam soluções eficientes, tal como o algoritmo de árvore de junção.
3.1
Métodos Exatos
Um método é denominado exato se realiza o cálculo das probabilidades a posteriori através
de somatórios e combinações de valores, sem outro erro que não seja de arredondamento
no cálculo [8]. Nesta seção evidência e métodos exatos para propagá-la são definidos. Na
Seção 3.1.1 introduz-se o método “bruto”. Existem vários métodos exatos mais convenientes para a realização de inferência em uma rede bayesiana; destacando-se dois tradicionais,
o de propagação em poliárvores [56] (Seção 3.1.2) e o de eliminação de variáveis (Seção
3.1.3) com suas variações [19].
3.1.1
Propagação de Evidências
A propagação de evidências sobre uma rede bayesiana permite obter estimativas de probabilidades quando são acrescidas informações. Seja um conjunto de variáveis X =
{X1 , X2 , . . . , Xn } associadas a um domı́nio de dados e uma função de probabilidade P (x)
para X, conforme Equação 2.5, a ser descoberta. Quando se dispõe de certa evidência,
ou seja, quando é conhecido um subconjunto de variáveis E ⊂ X com valores associados
Xi = ei , para Xi ∈ E, o processo de propagação deve considerar esses valores no cálculo
das novas probabilidades dos nós.
Definição 3.1 (Evidência) Um subconjunto de variáveis E ⊂ X com valores conhecidos, E = e, em uma dada situação, é conhecido como conjunto de evidência, ou simplesmente evidência.
A propagação de evidência consiste no cálculo das probabilidades a posteriori P (xi |e)
para cada variável Xi ∈
/ E, dada a evidência E = e. A função de probabilidade a posteriori mede a influência da evidência sobre cada variável.
26
dct-ufms
Quando não há evidência (E = φ), as funções condicionadas P (xi |e) são simplesmente
as funções de probabilidades marginais P (xi ), para cada Xi ∈ X. Ou seja, se não há
informação, o processo de propagação consiste no cálculo das marginais. Essas fornecem
informações a priori sobre os valores que as variáveis podem assumir.
Uma maneira de se fazer o cálculo das probabilidades P (xi |e) é aplicar o Teorema de
Bayes dado pela Equação 2.9:
P (xi |e) =
P (xi , e)
∝ P (xi , e)
P (e)
(3.1)
onde 1/P (e) é uma constante de normalização. Portanto, pode-se obter P (xi |e), calculando e normalizando as probabilidades marginais P (xi , e). Desta forma tem-se,
X
P (xi , e) =
Pe (x1 , . . . , xn )
(3.2)
x\{xi ,e}
onde Pe (x1 , . . . , xn ) é uma função de probabilidade obtida da substituição em
P (x1 , . . . , xn ) das variáveis com evidência, E, pelos seus valores e; x\{xi , e} representam todas as combinaçõesPdos estados ou valores das varáveis em X sem considerar os
valores de Xi e E, sendo x\{xi ,e} a marginalização (às vezes denominado somatório ou
eliminação de variáveis) das variáveis não contidas em {xi , e}. Então, para fazer o cálculo
P (xi , e) é preciso somar Pe (x1 , . . . , xn ) para cada uma das possı́veis combinações de valores das variáveis que não estejam contidas em E, com exceção da variável Xi . Quando a
evidência não é informada, a Equação 3.2 reduz-se a
X
P (xi ) =
P (x1 , . . . , xn )
(3.3)
x\xi
onde x\xi são todas as combinações dos estados das variáveis em X sem considerar a
variável Xi .
Devido ao número elevado de combinações dos valores que envolve a Equação 3.2,
esse método “bruto” é bastante ineficiente, inclusive em redes com número de variáveis
reduzido. Por exemplo, no caso de variáveis binárias, a Equação 3.2 requer a soma de
2n−1 probabilidades distintas.
O problema das Equações 3.2 e 3.3 é não considerarem a estrutura de independência
contida na função de probabilidade P (x). O cálculo necessário no processo de propagação
pode ser reduzido se consideradas as relações de independência entre as variáveis da
função de probabilidade P (x). Por exemplo, seja um modelo probabilı́stico formado pelo
conjunto de variáveis X = {A, . . . , G} e uma função de probabilidade P (x) que pode ser
fatorada usando o grafo acı́clico da Figura 3.1 na forma:
P (x) =
n
Y
P (xi |pai ) = P (a)P (b)P (c|a)P (d|a, b)P (e)P (f |d)P (g|d, e)
i=1
27
(3.4)
dct-ufms
A
C
B
D
E
F
G
Figura 3.1: Grafo acı́clico orientado.
onde xi ∈ X e pai é uma instância de P ai , o conjunto de pais do nó Xi . Deseja-se calcular
as probabilidades marginais dos nós. Nesse caso, o método mais simples para obter P (xi )
é marginalizar a função de probabilidade utilizando a Equação 3.3. Por exemplo, as
probabilidades iniciais da variável D podem ser calculadas assim
X
X
P (d) =
P (x) =
P (a, b, c, d, e, f, g)
(3.5)
x\d
a,b,c,e,f,g
Supondo as variáveis binárias, o somatório
da Equação 3.3 teria 26 = 64 termos distintos,
P
posto que precisa-se marginalizar ( x\d=a,b,c,d,e,f ) 6 variáveis binárias.
A estrutura de independência, contida na função de probabilidade conjunta P (x),
permite simplificar o processo de propagação de evidência. O número de operações pode
ser reduzido agrupando os termos dentro do somatório da seguinte maneira:
X
P (d) =
P (a)P (b)P (c|a)P (d|a, b)P (e)P (f |d)P (g|d, e)
a,b,c,e,f,g
!
X
=
!
X
P (a)P (b)P (c|a)P (d|a, b)
a,b,c
P (e)P (g|d, e)P (f |d)
(3.6)
e,f,g
onde cada um dos somatórios pode ser calculado de forma independente. Portanto, o
problema de marginalizar uma função de probabilidade de seis variáveis é reduzido a
marginalizar duas funções que dependem só de três variáveis. O número de termos em
cada somatório fica reduzido (de 64 a 23 + 23 = 16), sendo reduzido também o número
de fatores de cada um dos termos (de 7 a 4 e de 7 a 3, respectivamente). Uma redução
adicional se consegue reordenando os termos dentro dos somatórios da Equação 3.6, da
forma seguinte:
"
"
##
"
"
##
X
X
X
X
X
X
P (d) =
P (a)
P (c|a)
P (b)P (d|a, b)
P (e)
P (f |d)
P (g|d, e)
a
c
e
b
f
g
(3.7)
Em geral, a propagação de evidências através de métodos exatos é NP-difı́cil, como
demonstrado por Cooper [16]. Porém, há uma classe restrita de redes que podem ser eficientemente resolvidas em tempo linear quanto ao número de nós. Essa classe é denominada
28
dct-ufms
de redes simplesmente conectadas, também conhecidas como poliárvores ou polytrees [56]
tema da seção seguinte.
3.1.2
Propagação em Poliárvores
Uma poliárvore é um dos modelos gráficos mais simples para construir RBs [8]. Nesta
seção apresenta-se um algoritmo de propagação para este tipo de modelo probabilı́stico
conforme descrito em [56]. A caracterı́stica principal desse algoritmo é sua complexidade
ser linear no número de nós e arcos que compõem a rede, comparado com o método de
força bruta, que precisa de um número exponencial de operações para realizar a propagação. O algoritmo revisado de propagação em poliárvores proposto em [58] permite a
propagação de várias variáveis simultaneamente.
Em uma poliárvore dois nós quaisquer estão unidos por um único caminho. Isto implica que cada nó divide a poliárvore em duas poliárvores não conexas: uma que possui
os seus pais e os nós que estão conectados através de seus pais, e a outra que inclui seus
filhos e os nós que estão conectados através de seus filhos.
Por exemplo, na Figura 3.1, o nó D divide a poliárvore em duas poliárvores não
conexas, a primeira, {A, B, C}, inclui seus pais e os nós que são acessı́veis desde D através
de seus pais, e a segunda, {E, F, G}, que inclui aos seus filhos e os nós acessı́veis desde D
através de seus filhos. Este fato é ilustrado na Figura 3.2. Também pode-se constatar que
o nó D separa esses dois conjuntos, a relação de independência I({A, B, C}, {E, F, G}|D)
é verificada na forma gráfica.
A
C
B
D
D
F
E
G
Figura 3.2: O nó D divide a poliárvore em duas poliárvores não conexas.
Neste tipo de grafo, o processo de propagação pode ser realizado eficientemente, combinando a informação proveniente dos distintos subgrafos mediante o envio de mensagens
(cálculos de probabilidade locais) de um subgrafo a outro [8]. As mensagens enviadas de
uma variável para seus filhos são chamadas π, e as mensagens enviadas de uma variável
para seus pais são chamadas λ.
29
dct-ufms
Antes de descrever o algoritmo de propagação em poliárvores apresenta-se um exemplo
de uma rede bayesiana com este tipo de estrutura simples (Figura 3.3). O domı́nio modelado e simplificado é um sistema de alarme para detecção de roubos descrito inicialmente
em [56]. Uma pessoa instalou um sistema de alarme contra roubos e tem dois vizinhos
João e Maria, que prometeram ligar caso eles ouvirem o alarme. João liga sempre que
escuta o alarme, mas algumas vezes confunde o som do telefone com o alarme e também
liga. Maria gosta de ouvir música alta e algumas vezes não ouve o alarme. Dada a
evidência de quem tenha, ou não, ligado, deseja-se estimar a probabilidade de um roubo.
R
T
A
J
M
Figura 3.3: Alarme contra roubos: R = Roubo; T = Terremoto; A = Alarme; J =
João-liga; M = Maria-liga.
As Tabelas 3.1 à 3.5 apresentam as distribuições de probabilidades desta RB exemplo.
Da topologia desta RB observa-se que um roubo e os terremotos influenciam na probabilidade de que o alarme se ative.
Tabela 3.1: P (R).
Tabela 3.2: P (T ).
P(R=F)
0.99
P(T=F)
0.98
P(R=V)
0.01
P(T=V)
0.02
Tabela 3.3: P (A|R, T ).
R
F
V
F
V
T
F
F
V
V
P(A=F) P(A=V)
0.999
0.001
0.71
0.29
0.06
0.94
0.05
0.95
Há duas formas básicas de influência das variáveis em uma RB. As causas influenciam
os efeitos (influência causal π — das causas para os efeitos) e os efeitos influenciam as
30
dct-ufms
Tabela 3.5: P (M |A).
Tabela 3.4: P (J|A).
A
F
V
P(J=F) P(J=V)
0.95
0.05
0.1
0.9
A
F
V
P(M=F)
0.99
0.3
P(M=V)
0.01
0.7
suas causas (influência diagnóstica λ — dos efeitos para as causas). No exemplo, suponha que há evidência de João ligar (efeito) e deseja-se saber se houve um roubo (causa),
P (R|J = V ). Um raciocı́nio errado é o seguinte: uma vez que o alarme seja ativado e
que João ligue será verdadeiro 90% do tempo. O alarme é muito preciso na detecção de
ladrões, assim P (R|J) deve também estar próximo de 0.9 ou 0.8 ou talvez pior. O problema é que este tipo de raciocı́nio ignora a probabilidade prévia das ligações de João. Sobre
a base de 1000 dias, é esperado 1 roubo, para o qual João é muito provável que ligue.
Mas João também liga com probabilidade 0.05 quando não há alarme, isto é, próximo a
50 vezes em 1000 dias. Assim espera-se receber cerca de 50 falsos alarmes de João para
cada 1 roubo, sendo P (R|J) próximo a 0.02. O valor real é 0.016.
Também é possı́vel calcular a influência das causas sobre os efeitos (influência causal
π — das causas para os efeitos). Dado um roubo, P (J|R = V ) = 0.86 e P (M |R = V ) =
0.67.
Em geral, seja X um nó, correspondente a uma variável X qualquer da rede. X sofre
a influência causal π de seus pais e a influência diagnóstica λ de seus filhos:
• Quando uma evidência externa impacta o nó X este atualiza sua crença (P (x|e)) e
a propaga para cada um de seus pais e para cada um de seus filhos;
• Quando uma evidência de um pai (mensagem π) chega ao filho X o filho atualiza
sua crença e a propaga a cada um de seus filhos e a cada um de seus pais, exceto
àquele que lhe enviou a mensagem;
• Quando uma evidência de um filho (mensagem λ) chega ao pai X, X atualiza sua
crença e a propaga para cada um de seus pais e para cada um de seus filhos, exceto
àquele que lhe enviou a mensagem.
Considere que X tenha m filhos, Y1 , . . . , Ym , e n pais, P a1 , . . . , P an , como ilustrado
na Figura 3.4. A distribuição de probabilidades da variável X pode ser calculada se três
tipos de parâmetros estão disponı́veis [56]:
1. A força atual do suporte causal, π, formado pela contribuição de cada arco de
chegada P ai → X:
(3.8)
πX (pai ) = P (pai |e+
P ai X )
onde e+
P ai X representa a evidência contida no subgrafo formado pelos nós ligados
a cada pai de X, P ai ; e P (pai |e+
P ai X ) é a crença formada pela propagação dessa
evidência (as mensagens π e as mensagens λ) sobre cada pai de X.
31
dct-ufms
Pa1
. . .
Pa n
X
Y1
. . .
Ym
Figura 3.4: Pais e filhos de um nó qualquer X.
2. A força atual do suporte diagnóstico, λ, formado pela contribuição de cada arco de
saı́da X → Yj :
λYj (x) = P (e−
(3.9)
XYj |x)
onde e−
XYj representa a evidência contida no subgrafo formado pelos nós ligados a
cada filho de X, Yj ; e P (e−
XYj |x) é a crença formada pela propagação dessa evidência
(as mensagens λ e π) sobre cada filho de X.
3. A matriz de probabilidade condicional fixa P (x|pa1 , . . . , pan ) que relaciona a variável
X aos seus pais imediatos.
Usando esses parâmetros, a atualização de crença local pode ser efetuada em três
passos [56]:
Passo 1 : Atualização de crença: quando um nó X é ativado (recebe uma evidência),
simultaneamente inspeciona as mensagens πX (pai ), i = 1, . . . , n enviadas pelos seus
pais e as mensagens λYj (x), j = 1, . . . , m enviadas pelos seus filhos. Usando está
entrada, o nó atualiza sua medida de crença
BEL(x) = αλ(x)π(x)
(3.10)
Y
(3.11)
onde
λ(x) =
λYj (x)
j
é a multiplicação de cada uma das mensagens enviadas pelos filhos de X,
X
Y
π(x) =
P (x|pa1 , . . . , pan )
πX (pai )
pa1 ,...,pan
(3.12)
i
é a soma ponderada de cada mensagem enviado pelos pais de X (πX (pai )) com a
força do seu relacionamento com X, P (x|pai ). BEL (belief) indica a crença acumulada
e
α
é
uma
constante
de
normalização
para
P
x BEL(x) = 1.
32
dct-ufms
Passo 2 : Propagação ascendente: usando as mensagens recebidas, o nó X calcula as novas mensagens λ para serem enviadas aos seus pais. Por exemplo, a nova mensagem
λX (pai ) que X envia aos seus pais P ai é calculada como
X
X
λ(x)
πX (pak )
(3.13)
λX (pai ) = β
x
pak :k6=i
Passo 3 : Propagação descendente: cada nó calcula novas mensagens π para serem
enviadas aos seus filhos. Por exemplo, a nova mensagem πYj (x) que X envia aos
seus filhos Yj é calculada como
"
#
Y
X
Y
λYk (x)
πYj (x) = α
P (x|pa1 , . . . , pan )
πX (pai )
k6=j
= α
pa1 ,...,pan
BEL(x)
λYj (x)
i
(3.14)
Cada uma das equações dadas nos passos 2 e 3 estão definidas em função da crença
e das mensagens λ e π do nó X (para maiores detalhes sobre a derivação dessas últimas
equações pode ser consultado [56]).
3.1.3
Propagação em Redes Multiconectadas
Em estruturas de redes mais gerais e complexas, denominadas multiconectadas, uma simples propagação local, como descrita na seção anterior, não é aplicável porque algoritmos
desenvolvidos para redes simplesmente conectadas —poliárvores— não prevêem a possibilidade de um nó, ao receber evidência de dois dos seus vizinhos, detectar se essa evidência
não se origina na mesma fonte e evitar contá-la duas vezes. Assim, algoritmos especializados para redes multiconectadas são necessários. Nesta seção apresenta-se um resumo
dos algoritmos exatos para inferência neste tipo de estruturas.
A Figura 3.5 ilustra uma estrutura de rede multiconectada, ou seja, na qual podem
existir vários caminhos entre dois nós. Por exemplo, pode-se observar que do nó A ao
nó F há dois possı́veis caminhos, e se a direção dos arcos não é considerada forma-se um
ciclo entre esses nós.
A abordagem natural em redes multiconectadas consiste em aplicar transformações
topológicas a essas redes visando transformá-las em poliárvores e aplicar os algoritmos
disponı́veis para propagação de evidências em poliárvores [15]. Os métodos mais utilizados com essa finalidade são os métodos de agregado e condicionantes. Ambos métodos
apresentam algumas dificuldades na transformação do GAO em poliárvores. No primeiro caso, é necessário selecionar variáveis que permitem quebrar as conexões múltiplas
do GAO e que, deste modo, formaram uma variável composta. Quanto maior for esse
agregado, maior será a dimensão da sua tabela de distribuição de probabilidades condicionais e maior a dificuldade para explicar a variação de crença devida a cada uma das
33
dct-ufms
A
B
C
G
D
E
H
F
Figura 3.5: Estrutura de rede bayesiana multiconectada.
variáveis. Em resumo, o método de agregados constrói representações auxiliares, de estrutura mais simples, unindo conjuntos de nós do grafo original. Deste modo pode-se obter
um grafo com estrutura de poliárvore no qual é possı́vel aplicar idéias de propagação de
evidências [40].
O algoritmo de árvore de junção (tema da Seção 3.1.4) é um método de agregado eficiente para inferência em redes multiconectadas [15] e foi utilizado como parte do algoritmo
de aprendizagem de parâmetros para estimar valores faltosos.
O método de condicionantes está baseado na habilidade de mudar a conectividade de
uma rede, de forma a torná-la simplesmente conectada, selecionando-se um conjunto adequado de variáveis a serem instanciadas. A idéia fundamental do método de propagação
por condicionamento é cortar os múltiplos caminhos entre os nós mediante a atribuição
de valores a um conjunto reduzido de variáveis contidas nos ciclos [8]. Essas variáveis
formam o que se chama conjunto de corte [22], ou seja, são nós que, quando excluı́dos,
eliminam os ciclos existentes na rede. O resultado disto é uma poliárvore na qual será
possı́vel aplicar o algoritmo de propagação para poliárvores. Nesses métodos, se a rede
for muito conectada, pode ocorrer um problema de complexidade computacional combinatória, em função do número de nós e variáveis necessárias para quebrar os ciclos do
GAO.
O algoritmo dado em [56], chamado Global Conditioning (GC), condiciona todos os
nós da rede a cada variável do conjunto de corte. Neste método a propagação se torna exponencial não só com relação ao número de novas evidências, mas também com o número
de variáveis do conjunto de corte [26].
O condicionamento em nós, chamado de Knots Conditioning (KC), é um método de
34
dct-ufms
propagação em redes de conhecimento que utiliza do algoritmo de propagação em poliárvores revisado. Existem outros métodos exatos para a resolução de knots que são
descritos em [40]. O processo de inferência que se utiliza do método chamado Local Conditioning (LC) [26] propõe um algoritmo eficiente para aplicações práticas utilizando o
condicionamento apenas dentro dos ciclos da rede. Este algoritmo de condicionamento
local segue a abordagem dos knots, aplicando o condicionamento somente dentro de cada
ciclo da rede. Com esta mudança, em alguns casos nos quais o KC possui complexidade
exponencial, o LC é linear.
Embora a complexidade do algoritmo para poliárvores seja linear com relação ao tamanho da rede, para o caso de redes multiconectadas o problema se torna NP-difı́cil [16].
Castillo et al [8] afirmam que, em geral, tanto o método de condicionamento quanto o de
agregado consideram este tipo de complexidade. Porém, as caracterı́sticas particulares
destes métodos fazem com que, em determinadas ocasiões, um deles seja mais eficiente
que o outro em redes com alguma estrutura particular.
3.1.4
Algoritmo de Árvore de Junção
Uma rede bayesiana representa um modelo probabilı́stico completo, com representação das
informações qualitativas (dependências), quantitativas (função de distribuição de probabilidades condicionais) e uma estrutura de controle para a inferência. Ao se obter uma
evidência, é preciso considerar se existe mais de um caminho entre o nó com a evidência
e aquele cuja probabilidade deve ser atualizada pela inferência. A estrutura de controle
determina qual estratégia usar para propagar crenças ou probabilidades. Uma árvore de
junção é um exemplo de estrutura de controle obtida a partir da estrutura de uma rede
bayesiana [41].
Em 1990, Finn Jensen et al apud [15] propuseram um método geral para propagação
de crenças em RBs. Esse método aproveita a estrutura da rede para propagar evidências,
calculando probabilidades locais (com pequeno número de variáveis) e evitando expressões
globais (grande número de variáveis). Para tanto é necessário criar uma estrutura intermediária, na forma de uma árvore com caracterı́sticas especiais, denominada árvore de
junção, cujos nós são determinados por subconjuntos das variáveis da rede bayesiana original (cliques). A estrutura da árvore de junção associada à rede original é fixa, sendo os
cálculos realizados localmente no sentido de que um nó necessite se comunicar somente
com os seus vizinhos. Esse método não se aplica às redes que possuem ciclos ou nós com
um número muito grande de pais (pois os cliques podem ficar muito grandes).
Definição 3.2 (Cliques) Um clique em um grafo não dirigido G é um subgrafo de G
que é completo e máximo. Completo significa que cada par de nós distintos é conectado
por um arco. Máximo significa que cada clique não está contido em um subgrafo completo
maior.
As seções seguintes especificam o processo de construção de uma árvore de junção e o
35
dct-ufms
processo de inferência sobre esta estrutura, cujas descrições foram adaptadas de [15, 39].
Este algoritmo foi utilizado para a inferência dos valores faltosos nas instâncias de dados
que estavam incompletas.
Construindo Árvore de Junção de Redes Bayesianas
A partir do GAO de uma rede bayesiana, as transformações que resultam em uma árvore
de junção podem ser resumidas na construção das seguintes estruturas intermediárias:
1. A construção de um grafo não dirigido, chamado grafo moralizado, a partir do GAO.
2. A adição de arcos ao grafo moralizado para formar um grafo triangular.
3. A seleção de subconjuntos de nós do grafo triangular, chamados cliques.
4. A construção da árvore de junção, utilizando os cliques como agregados: conectando os agregados para formar uma árvore não dirigida e inserindo os separadores
apropriados.
Cada um desses passos é descrito com maior detalhe a seguir.
1- Construindo o Grafo Moralizado
Para construir o grafo moralizado adiciona-se um arco (se inexistente) entre pares de pais
de cada nó do grafo original e elimina-se a orientação dos arcos do grafo resultante. Na
Figura 3.6 é apresentado o grafo moral obtido do GAO da Figura 3.5.
A
B
C
G
D
E
H
F
Figura 3.6: Exemplo de grafo moralizado.
36
dct-ufms
2- Triangularizando o Grafo Moralizado
A triangularização consiste na introdução de arcos em ciclos com mais de três nós. Os
arcos são denominados cordas e o grafo resultante, grafo cordal ou triangular. Como um
ciclo pode ser quebrado de diversas formas, existem diversas maneiras de se triangularizar
um grafo, sendo ótima a que utiliza o mı́nimo possı́vel de cordas. O algoritmo de triangularização ótima de um grafo é da classe NP-completo [71]. Os cliques de um grafo são
determinados pela sua triangularização. O tamanho dos cliques condiciona a eficiência
dos algoritmos de propagação de evidências, pois estão baseados em tabelas de probabilidades associadas a cada clique. Uma boa triangularização produz cliques pequenos
(pequenas tabelas de probabilidades). Intuitivamente, a triangularização conecta aqueles
nós que apresentam um termo comum no momento da marginalização. O procedimento
para triangularização, adaptado de Kjaerulff [43], é o seguinte:
1. Faz-se uma cópia de GM (grafo moralizado), denotada G0M .
2. Enquanto houver nós em G0M :
(a) Seleciona-se um nó V de G0M , de acordo com o critério especificado posteriormente.
(b) O nó V e seus vizinhos em G0M formam um agregado (cluster). Conecta-se
todos os nós neste agregado. Para cada arco adicionado a G0M , adiciona-se um
arco correspondente em GM .
(c) Remove-se V de G0M .
3. GM , modificado pelas arcos adicionais inseridos nos passos prévios, é agora triangular.
Para descrever o critério para selecionar os nós no passo 2a, utiliza-se a noção de peso:
• O peso de um nó V é o número de valores de V .
• O peso de um agregado é o produto dos pesos dos nós que formam o agregado.
O critério para selecionar os nós a serem removidos é assim definido: escolhe-se o nó
que produza o menor número de arcos a serem adicionados no passo 2b, quebrando as
ligações para escolher o nó que induz o agregado com o menor peso. Na Figura 3.7 é
apresentada uma das possı́veis triangularizações do grafo moralizado da Figura 3.6, onde
as linhas traçadas indicam os arcos adicionados para triangularizar o grafo moralizado.
Na Tabela 3.6 é apresentada a ordem de eliminação considerando o número de valores
(estados) de cada nó como 2.
3- Identificando Cliques
Adaptando o procedimento de triangularização, pode-se identificar os cliques do grafo
triangular no instante em que este está sendo construı́do. Precisa-se de duas observações:
37
dct-ufms
A
B
C
G
D
E
H
F
Figura 3.7: Grafo triangular do grafo da Figura 3.6.
Tabela 3.6: Ordem de eliminação dos nós.
Ordem
1
2
3
4
5
6
7
8
Nó Eliminado
H
G
F
C
B
D
E
A
Agregado Induzido Arcos Adicionados
EGH
nenhum
CEG
nenhum
DEF
nenhum
ACE
(A, E)
ABD
(A, D)
ADE
nenhum
AE
nenhum
A
nenhum
• Cada clique no grafo triangular é um agregado induzido do passo 2b da seção anterior.
• Cada agregado induzido não pode ser um subconjunto de um grupo induzido subseqüentemente.
Estas observações sugerem que pode-se extrair os cliques durante o processo de triangularização, salvando cada agregado induzido desde que não seja um subconjunto de
algum agregado salvo previamente. Da Tabela 3.6, observa-se que os cliques do grafo
triangular são EGH, CEG, DEF, ACE, ABD e ADE.
4- Construindo uma Árvore de Junção Ótima
Definição 3.3 (Árvore de Junção) Uma árvore de junção T de um Grafo G é uma
árvore cujos nós são agregados de G e a) para cada nó V em G, existem nós em T que
contêm a famı́lia de V . A famı́lia de V é a união de V e seus pais; b) para cada par de
agregados ou cliques Ci , Ck , todos os agregados entre Ci e Ck contêm Ci ∩ Ck (propriedade
38
dct-ufms
de árvore de junção); e c) o arco é rotulado com as variáveis comuns aos agregados que
une (separador).
Para construir uma árvore de junção ótima, deve-se conectar os cliques de maneira que a
árvore resultante satisfaça a propriedade de árvore de junção e um critério de otimização
que será definido posteriormente. A propriedade de árvore de junção é importante para
a árvore ser útil para inferência probabilı́stica. Dado um conjunto de n cliques, pode-se
formar uma árvore de junção inserindo iterativamente arcos entre pares de cliques, até
que os cliques estejam conectados por n − 1 arcos [41]. A especificação do algoritmo pode
ser dividida em duas partes: a primeira é um procedimento geral que forma uma árvore
de cliques pela seleção e inserção iterativa de separadores de conjuntos candidatos. Na
segunda parte, mostra-se como os separadores de conjuntos devem ser escolhidos, para
que a árvore de cliques seja uma árvore de junção ótima.
4.1- Formando a Árvore de Cliques
1. Inicia com um conjunto de n árvores, cada um formado de um só clique, e um
conjunto vazio S.
2. Para cada par distinto de cliques Ci e Ck :
(a) Cria-se um conjunto separador candidato, Ci ∩ Ck , com apontadores aos cliques
Ci e Ck . Denote este conjunto SCi Ck .
(b) Insere-se SCi Ck em S.
3. Repetir até que n − 1 separadores de conjuntos sejam inseridos na floresta.
(a) Seleciona-se um conjunto separador SCi Ck de acordo com critério especificado
no passo subseqüente. Exclui-se SCi Ck de S.
(b) Insere-se o separador de conjuntos SCi Ck entre os cliques Ci e Ck somente se Ci
e Ck estão em diferentes árvores na floresta. Note que a inserção deste conjunto
separador junta duas árvores em uma árvore maior.
4.2- Escolha dos Conjuntos Separadores Apropriados
Para descrever como escolher o próximo conjunto separador candidato, define-se as noções
de massa e custo.
• A massa de um separador de conjunto SCi Ck é o número de variáveis que contém,
ou seja, o número de variáveis em Ci ∩ Ck .
• O custo de um separador de conjunto SCi Ck é o peso de Ci mais o peso de Ck , onde
o peso é definido como:
– O peso de uma variável V é o número de valores de V .
39
dct-ufms
– O peso de um conjunto de variáveis Ci é o produto dos pesos das variáveis em
Ci .
Agora pode-se estabelecer como selecionar o próximo conjunto separador candidato
de S quando se executa o passo 3a [41]:
• Para que a árvore de cliques resultante satisfaça a propriedade de árvore de junção,
deve-se escolher o conjunto separador candidato com maior massa.
• Quando dois ou mais conjuntos separadores têm igual massa, pode-se escolher o
conjunto candidato com menor custo.
No exemplo, a partir do conjunto de cliques {ABD, ACE, ADE, CEG, DEF, EGH}
da Figura 3.7, escolhe-se os conjuntos separadores AD, AE, CE, DE e EG de acordo com
a massa. Estes cliques e separadores formam a estrutura da árvore de junção ilustrado
na Figura 3.8.
ABD
AD
ADE
AE
ACE
CE
CEG
EG
DE
Conjunto
separador
EG
DEF
EGH
Agrupamento
DEF
Figura 3.8: Exemplo de estrutura de árvore de junção para o exemplo da Figura 3.5.
Inferência com Árvores de Junção
O componente numérico de uma árvore de junção é descrito utilizando a noção de potencial
de crença. Um potencial de crença é uma função que mapeia cada instanciação de um
conjunto de variáveis em um número real. Potenciais de crença são definidos sobre os
seguintes conjuntos de variáveis:
• Agregados ou cliques: cada clique C está associado com um potencial φC que mapeia
cada instanciação dos valores das variáveis que formam C em um número real.
• Separador de conjuntos: cada separador de conjuntos S está associado com um
potencial φS que mapeia cada instanciação dos valores das variáveis S em um número
real.
40
dct-ufms
Os potenciais não são especificados de forma arbitrária, mas devem satisfazer as seguintes restrições:
• Para cada clique C e conjunto separador vizinho S, tem-se que:
X
φC = φS
(3.15)
C\S
P
onde C\S indica eliminação de variáveis ou marginalização. Quando a Equação
3.15 é satisfeita, diz-se que φS é consistente com φC . Quando esta consistência se
cumpre para cada par de cliques e separadores, diz-se que a estrutura secundária é
localmente consistente.
• Os potenciais codificam a distribuição conjunta P (U ) da rede bayesiana de acordo
com
Q
φC
P (U ) = Q i i
(3.16)
j φSj
sendo φCi e φSj são os potenciais dos cliques e dos conjuntos separadores, respectivamente.
Os potenciais φABD e φAD da Figura 3.8 são apresentados na Tabela 3.7. Note que
φABD e φAD satisfazem a exigência de consistência local, pois
X
φAD =
φABD
(3.17)
B
Tabela 3.7: Exemplo de potenciais para a árvore de junção do exemplo da Figura 3.5.
φABD
A
v
v
v
= v
f
f
f
f
B
v
v
f
f
v
v
f
f
D φABD (abd)
v
0.225
f
0.025
v
0.125
f
0.125
v
0.180
f
0.020
v
0.150
f
0.150
φAD
A
v
= v
f
f
D φAD (ad)
v
0.35
f
0.15
v
0.33
f
0.17
A consistência local também é mantida para os outros pares cliques-separadores. Finalmente, os potenciais de crença codificam a distribuição de probabilidade conjunta da
rede de acordo com
φABD φACE φADE φCEG φDEF φEGH
P (U ) =
(3.18)
φAD φAE φCE φDE φEG
Em geral são necessários os seguintes passos para realizar o processo de inferência:
41
3.2. Métodos Aproximados - Simulação Estocástica
dct-ufms
• Transformação global: transforma-se o GAO da rede bayesiana em uma estrutura
de árvore de junção, utilizando os procedimentos das seções anteriores.
• Iniciar: quantifica-se a árvore de junção com potenciais de crença. O resultado é
uma árvore de junção inconsistente, já que esta atribuição inicial de potenciais não
cumpre os requisitos de consistência local.
• Propagação global: realiza-se uma série ordenada de manuseios locais, chamados
passagens de mensagens, sobre os potenciais da árvore de junção. As passagens
de mensagens rearranjam os potenciais da árvore de junção fazendo-os localmente
consistentes; o resultado da propagação global é uma árvore de junção consistente.
• Marginalização da árvore de junção consistente: calcula-se P (V ) para cada variável
de interesse V .
Os processos Iniciar e Propagação não serão especificados aqui, maiores detalhes de
cálculo numérico e exemplos podem ser encontrados em [15, 39]. A estrutura de árvore de
junção da Figura 3.8 cumpre uma propriedade importante: para cada clique (ou conjunto
separador) C tem-se que φC = P (C). Utilizando esta propriedade, pode-se calcular a
distribuição de probabilidade de qualquer variável V , utilizando qualquer clique C que
contenha V , como
X
P (V ) =
φC
(3.19)
C\V
Por exemplo, a Tabela 3.8 apresenta um exemplo de marginalização. O potencial do
clique φABD é o potencial consistente tomado da Tabela 3.7. φABD é marginalizado para
calcular P (A) e P (B).
Tabela 3.8: Exemplo de marginalização a partir de potenciais para o exemplo da Figura
3.5.
P (A) =
P (D) =
3.2
A
P (A)
φ
=
v
0.225
+
0.025
+
0.125 + 0.125 = 0.5
BD ABD
f 0.180 + 0.020 + 0.150 + 0.150 = 0.5
P
P
AB
φABD
D
P (D)
= v 0.225 + 0.125 + 0.180 + 0.150 = 0.680
f 0.025 + 0.125 + 0.020 + 0.150 = 0.320
Métodos Aproximados - Simulação Estocástica
Os algoritmos considerados dentro do grupo de métodos aproximados utilizam distintas
técnicas de simulação para obter valores aproximados das probabilidades. Estes métodos
podem ser classificados em: algoritmos de simulação estocástica, métodos de simplificação
de modelos, métodos baseados em busca e propagação de crença em ciclos [8]. Como
42
dct-ufms
demonstrado em [21], a complexidade da inferência através destes métodos aproximados
é NP-difı́cil. Este tipo de algoritmo não foi considerado para implementação, porém, para
trabalhos futuros poderia ser avaliada a sua utilização. A seguir é apresentada uma das
suas técnicas mais representativas, a simulação estocástica.
Simulação Estocástica
Estes tipos de algoritmos também são conhecidos como algoritmos de amostragem estocástica ou Monte Carlo. A idéia principal deste método aproximado é usar o modelo
causal da RB para simular o fluxo do impacto ou influência da evidência sobre o resto das
variáveis [40]. Neste tipo de algoritmo, de acordo com as tabelas de probabilidade condicional da RB, gera-se um conjunto de amostras selecionadas aleatóriamente, então realiza-se
inferência, isto é, aproxima-se probabilidades de variáveis “consulta” pela freqüência da
suas aparições na amostra. A exatidão dos resultados vai depender do tamanho das amostras e, diferentemente dos métodos exatos, a estrutura da rede não é relevante no cálculo
da inferência, sendo essa uma de suas vantagens principais.
Para ilustrar essa técnica considere a RB da Figura 3.9 com as probabilidades condicionais especificadas na Figura 3.10.
A
B
C
D
E
Figura 3.9: Estrutura de rede bayesiana para simulação estocástica, variáveis com estados
sim e nao.
O algoritmo inicia gerando (um número suficiente de vezes) configurações aleatórias
das variáveis (A, B, C, D, E). A seleção de uma configuração aleatória é feita por amostragem dos estados das variáveis. Primeiro é amostrado o estado de A, um gerador aleatório
que devolve um número entre 0 e 1. Se o número for menor que 0.4, o estado da variável
é sim; caso contrário o estado é nao. Supondo o resultado como sim, da tabela de probabilidade condicional P (B|A) tem-se que P (B|sim) = (0.3, 0, 7). O gerador aleatório é
usado novamente, e se o número for menor a 0.3, o estado de B é sim. Este procedimento é repetido para se obter o estado de C, D e E. Assim, uma configuração é determinada.
A próxima configuração é amostrada usando o mesmo procedimento e assim sucessivamnte até obter m configurações na amostra. Na Tabela 3.9 é apresentado um conjunto
de configurações simuladas. Para calcular as distribuições de probabilidades são feitas
43
dct-ufms
Figura 3.10: Probabilidades condicionais para a rede bayesiana exemplo.
contagens no conjunto amostrado. Para 39 das amostras na Tabela 3.9, o primeiro estado
é sim, isto resulta numa estimativa da probabilidade P (A) = (0.39, 0.61).
Tabela 3.9: Conjunto de 100 configurações de (A, B, C, D, E).
A
sim
sim
nao
nao
B
sim
nao
sim
nao
sss
4
2
9
0
ssn
0
0
1
0
sns
5
16
10
4
CDE
snn nss
0
1
0
1
0
14
0
0
nsn
0
0
0
0
nns
2
8
16
7
nnn
0
0
0
0
Nesse método, chamado forward sampling, não é necessário armazenar as configurações amostradas (como a Tabela 3.9). É suficiente armazenar as freqüências para cada
variável. Quando uma configuração é determinada, as freqüências de todas as variáveis
são atualizadas e a amostra pode ser excluı́da. O método economiza espaço, e cada configuração é determinada em tempo linear ao número de variáveis.
Para o caso em que nova evidência é conhecida, simplesmente são excluı́das as configurações que não conformam essa evidência. Ou seja, é iniciada uma série de simulações
estocásticas, e quando conferido o estado de uma variável observada, o processo de simu44
3.3. Métodos Simbólicos
dct-ufms
lação para caso o estado resultante não seja o observado.
3.3
Métodos Simbólicos
Os métodos apresentados nas seções anteriores requerem que a função de probabilidade
conjunta do modelo seja especificada numericamente, isto é, que sejam atribuı́dos valores
numéricos fixos a todos os parâmetros [8]. Em algumas situações, a especificação numérica
destes parâmetros não é desejada ou possı́vel. Neste caso, os métodos numéricos devem
ser substituı́dos por métodos simbólicos que sejam capazes de lidar com os parâmetros,
sem precisar de atribuir-lhes nenhum valor.
Os métodos de propagação simbólica conduzem a soluções que se expressam como
funções dos parâmetros. As respostas a questões gerais podem ser dadas em forma
simbólica em função dos parâmetros, e as perguntas especı́ficas podem ser obtidas fazendo a substituição dos valores dos parâmetros na solução simbólica, sem precisar refazer a
propagação. A propagação simbólica pode ser útil nos casos seguintes:
1. Quando não está disponı́vel a especificação numérica dos parâmetros do modelo
probabilı́stico.
2. Quando os especialistas somente são capazes de especificar intervalos dos parâmetros
ao invés de valores exatos. Neste caso, os métodos de propagação simbólica podem
ser utilizados para obter cotas inferiores e superiores das probabilidades para todos
os valores possı́veis dos parâmetros dos intervalos dados.
3. Quando é requerida uma análise de sensibilidade. Uma das questões que surgem
normalmente no contexto é: Quão sensı́veis são os resultados a mudanças nos
parâmetros e aos valores de evidência?.
3.4
Comentários Finais
Neste capı́tulo foi definido o problema de inferência e as distintas abordagens para lidar com ele. Foi detalhado o processo de construção e inferência sobre a estrutura de
árvore de junção (Seção 3.1.4). Este algoritmo foi usado neste trabalho para estimar valores faltosos em amostras, no contexto de aprendizagem de RBs, tema do próximo capı́tulo.
Existem muitas ferramentas que oferecem a funcionalidade de inferência probabilı́stica,
sendo algumas gratuitas e outras profissionais. Os pesquisadores que desenvolveram o algoritmo de árvore de junção criaram uma empresa e uma ferramenta denominada Hugin1 .
Esta foi uma das primeiras ferramentas em que se desenvolveram algoritmos exatos para
realizar inferência em RBs. Outra funcionalidade oferecida por Hugin é a análise do tipo
1
http://www.hugin.com/.
45
3.4. Comentários Finais
dct-ufms
mais provável explanação, isto é, a configuração mais provável que as variáveis podem assumir em um dado momento, de acordo com a evidência disponı́vel. Para cada inferência
realizada Hugin permite analisar a árvore de junção e as estruturas secundárias geradas.
A ferramenta Netica2 implementa uma versão própria de árvore de junção na qual o
usuário pode inspecionar os cliques e separadores que foram criados para a inferência,
e a ordem de eliminação escolhida. Também oferece a caracterı́stica da mais provável
explanação das variáveis.
JavaBayes3 é uma ferramenta que implementa um algoritmo de inferência diferente
denominado eliminação de variáveis generalizado [19]. Diferente das ferramentas analisadas anteriormente, esta é gratuita, distribuı́da sob licença GNU, sendo o código fonte
também disponı́vel.
A ferramenta UnBBayes4 também é gratuita e implementa o algoritmo de árvore de
junção para realizar inferência. A API disponibilizada pela ferramenta possibilitou o
desenvolvimento dos algoritmos neste trabalho.
2
http://www.norsys.com/.
http://www.pmr.poli.usp.br/ltd/Software/javabayes/.
4
http://unbbayes.sourceforge.net/.
3
46
Capı́tulo 4
Aprendizagem de Redes Bayesianas
Nos capı́tulos anteriores foi pressuposto que tanto a estrutura, quanto as probabilidades,
ou parâmetros, de uma RB já estavam definidos previamente e a RB estava pronta para
responder a consultas através de um processo de inferência. Em algumas situações, é
possı́vel construir toda a RB a partir do conhecimento de um especialista, porém, dependendo do domı́nio a ser modelado, este pode ser um processo difı́cil e demorado.
Particularmente, definir cada uma das probabilidades condicionais para uma RB, cujo
número de variáveis seja maior do que dez, pode se tornar uma tarefa complicada se usada só a experiência do especialista.
Considerando isto, e também o fato que os dados estão cada vez mais acessı́veis e baratos, atualmente, há grande interesse no aperfeiçoamento e desenvolvimento de métodos
para aprender estruturas e probabilidades a partir de dados.
A aprendizagem de RBs consiste em induzir, a partir de uma amostra de dados, as
distribuições de probabilidades simples e condicionais e/ou identificar as relações de interdependência entre as variáveis de um domı́nio de dados, que se constitui na população de
interesse. Esse processo de aprendizagem indutiva pode ser de dois tipos: aprendizagem
da estrutura (Seção 4.3), quando não se tem a estrutura e aprendizagem dos parâmetros
numéricos (Seção 4.2) quando se tem a estrutura. Os métodos de aprendizagem variam,
conforme o conhecimento que se tem dos dados.
Situações ocorrem em que a estrutura da rede é conhecida e as variáveis são observadas, ou ocultas, em todas ou em algumas instâncias de dados. Ou se tem a estrutura
desconhecida com essas mesmas possibilidades para as variáveis. Quando as variáveis são
observadas em todas as instâncias, diz-se que os dados são completos. Caso contrário, os
dados são incompletos. Conseqüentemente, há quatro casos de aprendizagem de RBs a
partir de dados: estrutura conhecida e dados completos (Seção 4.2.1); estrutura conhecida e dados incompletos (Seção 4.2.2); estrutura desconhecida e dados completos (Seção
4.3.1) e estrutura desconhecida e dados incompletos (Seção 4.3.2).
47
4.1. Algoritmo Expectation Maximization EM
dct-ufms
O algoritmo EM (Expectation Maximization) é um método para estimar funções de
máxima verossimilhança a partir de dados incompletos. Se os dados são incompletos,
pode-se utilizar os casos em que foram observadas as variáveis para aprender a predizer
seus valores quando não observados. As caracterı́sticas deste algoritmo permitem usá-lo
em problemas de aprendizagem de RBs a partir de dados incompletos, sendo a abordagem
algorı́tmica principal deste trabalho. Na Seção 4.1 é dada uma formulação geral do algoritmo EM. Na Seção 4.2.2 é descrito o algoritmo EM e sua aplicação para aprendizagem
de parâmetros com estrutura conhecida e dados incompletos.
Tanto para dados completos, como para incompletos, existem dois paradigmas principais para aprendizagem de estruturas de RBs: baseado em restrições ou independência
condicional e busca e pontuação. Os algoritmos EM para aprendizagem de estrutura fazem
parte deste último paradigma e são descritos na Seção 4.3.2.
4.1
Algoritmo Expectation Maximization EM
O algoritmo EM surgiu da unificação de uma série de trabalhos aparentemente sem relação e apresentado com esse nome por Demspter et al (1977) apud [6]. Depois disto,
este algoritmo permaneceu por muito tempo esquecido. Basicamente, se alguma variável
foi algumas vezes observada e outras não, pode-se utilizar os casos para os quais foi observada para aprender a predizer seus valores quando não. O algoritmo EM realiza esta
tarefa, mas, também pode ser utilizado para variáveis cujos valores nunca foram observados, sempre e quando seja conhecida a forma geral da distribuição de probabilidade das
variáveis [49].
Em geral os parâmetros descrevem as caracterı́sticas de uma população. Seus valores
são estimados de amostras coletadas dessa população. O algoritmo EM faz uma estimativa de máxima verossimilhança dos parâmetros, ou seja, estima parâmetros que sejam
os mais consistentes como os dados da amostra no sentido de maximizar a função de
verossimilhança.
Antes de introduzir o algoritmo EM, define-se função de verossimilhança e estimador
de máxima verossimilhança, conforme [50], para o caso geral de n variáveis aleatórias que
dependem do parâmetro θ, que pode até ser um vetor de parâmetros.
Definição 4.1 (Função de Verossimilhança) A função de verossimilhança de n variáveis aleatórias X1 , X2 , . . . , Xn é definida como a densidade conjunta de n variáveis
aleatórias, digamos fX1 ,...,Xn (x1 , . . . , xn ; θ), considerada como função de θ. Em particular,
se X1 , . . . , Xn é uma amostra aleatória da densidade f (x; θ), então a função de verossimilhança é f (x1 ; θ)f (x2 ; θ) . . . f (xn ; θ).
Notação 4.1 Para lembrar que função de verossimilhança é uma função de θ, usa-se a
notação L(θ; x1 , . . . , xn ) ou L(·; x1 , . . . , xn ) para a função de verossimilhança.
48
dct-ufms
Definição 4.2 (Estimador de Máxima Verossimilhança) Seja
L(θ) = L(θ; x1 , . . . , xn )
a função de verossimilhança para as variáveis aleatórias X1 , X2 , . . . , Xn . Se θ̂ [onde θ̂ =
ϑ̂(x1 , x2 , . . . , xn ) é uma função das observações x1 , . . . , xn ] é o valor de θ em Θ̄(universo
dos θs) que maximiza L(θ), então Θ̂ = ϑ(X1 , X2 , . . . , Xn ) é o estimador de máxima
verossimilhança de θ. θ̂ = ϑ(x1 , . . . , xn ) é a estimativa de máxima verossimilhança de θ
para a amostra x1 , . . . , xn .
Em sı́ntese o algoritmo EM (Expectation Maximization) é definido por dois passos:
• Passo E: encontra-se os valores esperados das estatı́sticas suficientes para os dados
completos Y , dado os dados incompletos Z e as estimativas atuais dos parâmetros.
• Passo M: utiliza-se estas estatı́sticas suficientes para fazer uma estimativa de máxima
verossimilhança como é usual.
Observação 1: Uma definição precisa do que é estatı́stica suficiente pode ser vista
em [50].
Observação 2: Alguns autores denominam o Passo E de Estimation, o que faz sentido,
considerando que calcular valores esperados de estatı́sticas é calcular estimativas.
Uma especificação mais formal é dada a seguir.
Especificação do Algoritmo EM
Nesta seção é apresentado o algoritmo EM conforme descrito em [49]. O algoritmo EM
pode ser aplicado nos casos onde se deseja estimar algum conjunto de parâmetros θ, que
descreve uma certa distribuição de probabilidades conjunta, dada somente uma parte observada dos dados produzidos por esta distribuição. Para ser mais preciso, considere que
X = {x1 , . . . , xm } denote os dados observados em um conjunto de m instâncias ocorridas independentemente, seja Z = {z1 , . . . , zm } os dados não observados nestas mesmas
instâncias, e seja Y = X ∪ Z o total de dados.
Z pode ser tratada como uma variável aleatória cuja distribuição de probabilidades
depende do conjunto de parâmetros desconhecido θ e dos dados observados X. Analogamente, Y é uma variável aleatória porque é definida em termos da variável aleatória Z.
Para descrever a forma geral do algoritmo EM, h denota a hipótese atual dos parâmetros
θ, e h0 denota a hipótese revisada que é estimada em cada iteração do algoritmo EM.
O algoritmo EM busca a hipótese h0 de máxima verossimilhança, isto é, que maximize
E[ln P (Y |h0 )]. Este valor esperado é calculado sob a distribuição de probabilidade de Y ,
49
dct-ufms
que é determinada pelos parâmetros desconhecidos θ. Mas, o que significa E[ln P (Y |h0 )]?
Primeiro, P (Y |h0 ) é a verossimilhança de todos os dados Y , dada a hipótese h0 . É razoável
que se queira encontrar h0 que maximize alguma função desta quantidade. Segundo, maximizar o logaritmo desta quantidade ln P (Y |h0 ) também maximiza P (Y |h0 ). Terceiro, se
introduz o valor esperado de E[ln P (Y |h0 )] porque o total de dados Y é, ele próprio, uma
variável aleatória.
Dado que os dados Y são uma combinação dos dados observados X e não observados Z, deve-se mediar sobre os possı́veis valores não observados Z, ponderando cada
um de acordo com suas probabilidades. Em outras palavras, toma-se o valor esperado
E[ln P (Y |h0 )] sobre a distribuição de probabilidade da variável aleatória Y . A distribuição
de probabilidades de Y é determinada pelos valores completamente conhecidos para X,
mais a distribuição de probabilidade de Z.
Qual é a distribuição de probabilidade de Y ? Em geral não se sabe esta distribuição
porque ela é determinada pelos parâmetros θ que se está tentando estimar. Entretanto,
o algoritmo EM usa sua hipótese atual h no lugar do parâmetro θ atual para estimar a
distribuição de probabilidades de Y . Considere a definição de uma função Q(h0 |h) que
dá E[ln P (Y |h0 )] como uma função de h0 , sob a suposição que θ = h e dada a porção
observada X dos dados Y .
Q(h0 |h) = E[ln P (Y |h0 )|h, X]
(4.1)
Escreve-se esta função Q na forma Q(h0 |h) para indicar que ela é definida em parte pela
suposição que a hipótese atual h é igual a θ.
Em sua forma geral, o algoritmo EM repete os dois passos seguintes, até a convergência:
Passo E: Expectation(E): calcula Q(h0 |h) usando a hipótese atual h e os dados observados X para estimar a distribuição de probabilidade sobre Y .
Q(h0 |h) = E[ln P (Y |h0 )|h, X]
(4.2)
Passo M: Maximization(M): troca a hipótese h pela hipótese h0 que maximiza esta
função Q.
h = arg max Q(h0 |h)
h0
(4.3)
Quando a função Q é contı́nua, o algoritmo EM converge para um ponto estacionário
da função de verossimilhança P (Y |h0 ). Quando esta função tem um único máximo, EM
convergirá para esta estimativa de máxima verossimilhança global para h0 . De outro modo,
o algoritmo converge somente para um máximo local. Com relação a isto, EM compartilha algumas das limitações dos outros métodos de otimização, tais como o gradiente
50
4.2. Aprendizagem de Parâmetros
dct-ufms
descendente, gradiente conjugado, etc.
4.2
Aprendizagem de Parâmetros
Quando a estrutura de uma rede é conhecida e o componente numérico ainda não foi
especificado, pode-se usar técnicas para aprender as distribuições de probabilidade a partir
dos dados disponı́veis. Esta seção apresenta dois casos possı́veis: quando os dados são
completos (Seção 4.2.1) e quando os dados são incompletos ou o valor de uma variável
nunca foi observado, usando-se EM (Seção 4.2.2).
4.2.1
Estrutura Conhecida e Dados Completos
Este é o caso mais simples, estudado e compreendido da literatura de RBs [33]. A estrutura da RB é especificada, e só é necessário estimar os parâmetros numéricos (distribuição
de probabilidade conjunta). O problema é bem definido e os algoritmos computacionalmente eficientes. Estes algoritmos formam a base da aprendizagem bayesiana e são, ainda,
extremamente úteis, pois é difı́cil para uma pessoa expressar-se em números, mesmo um
especialista num domı́nio.
A aprendizagem deste tipo é alcançada, simplesmente, calculando estimativas de
máxima verossimilhança e Bayesianas [69], para as entradas nas tabelas de probabilidade condicional das variáveis. Estimativas de máxima verossimilhança não consideram
conhecimento a priori sobre as distribuições de probabilidade, utilizam somente os dados
disponı́veis. Estimativas Bayesianas, utilizam os dados e algum conhecimento a priori expresso na forma de distribuições de Dirichlet (ver Seção 2.2.2) para estimar os parâmetros
a posteriori. Neste trabalho é considerada este último enfoque, seu procedimento foi
adaptado de [20] e é detalhado a seguir.
Uma rede bayesiana tem dois componentes: uma estrutura, que é um GAO, denotada
por S, e um conjunto de parâmetros numéricos Θ. Os parâmetros numéricos são dados
pelas distribuições de probabilidades condicionais das famı́lias1 Xi |P ai em S. Conhecida a estrutura S, para se ter uma rede bayesiana é necessário estimar as distribuições
condicionais associadas a cada famı́lia. Esta estimativa pode ser feita diretamente pelo
especialista ou, havendo disponibilidade de dados que componham uma amostra aleatória
independente e identicamente distribuı́da, é possı́vel fazê-la usando freqüências relativas.
Para a aprendizagem de parâmetros usando estimativas Bayesianas é necessário fazer
as seguintes suposições:
Uma RB hS, Θi, para o conjunto de variáveis X = {X1 , X2 , . . . , Xn }, tem n famı́lias
1
Uma famı́lia é formada de uma variável e seus pais.
51
dct-ufms
locais Xi |P ai . Cada Xi tem ri estados possı́veis x1i , x2i , . . . , xri i . A probabilidade de Xi
estar no estado xki , dado o j-ésimo estado dos seus pais pai e a estrutura S da RB é
expressa por P (Xi = xki |paji , S) = θijk .
A quantidade qi de estados que P ai pode assumir é dado pelo produtório da cardinalidade (número de estados possı́veis) das variáveis em P ai , conforme Equação 4.4:
Y
qi =
rk
(4.4)
xk ∈P ai
pa1i , pa2i , . . . , paqi i
Assim,
denotam as qi configurações dos pais de Xi . Por exemplo, da
RB para detecção fraude apresentada na Seção 2.3.1, os pais da variável Jóias, paJoias =
{F raude, Idade, Sexo}, têm qJoias = 2 × 4 × 2 = 16 configurações.
O parâmetro θijk é a probabilidade da variável Xi estar no estado xki , dado que seus
pais estão no estado paji . O vetor de parâmetros θij = (θij1 , θij2 , . . . , θijri ) dá as probabilidades da variável Xi para qualquer dos seus ri estados, dado que seus pais estão no
j-ésimo estado. O vetor de parâmetros θi = (θi1 , θi2 , . . . , θiqi ) dá as probabilidades da
famı́lia Xi |P ai e o vetor θ = (θ1 , θ2 , . . . , θn ) dá as probabilidades de todas as famı́lias na
RB, θ é o parâmetro numérico da RB, ele é uma instância da variável Θ.
Em geral os parâmetros da rede são desconhecidos. No processo de estimar os parâmetros
da RB o problema se reduz a computar P (Θ|D, S). Onde D é uma amostra aleatória grande o suficiente para se poder estimar os parâmetros e S é o GAO determinando as famı́lias
Xi |P ai da RB. Dado S, a distribuição a priori de Θ, P (Θ|S), deve ser estimada para RB.
Com a disponibilidade de uma amostra aleatória D, deve-se atualizar o conhecimento
sobre a distribuição Θ computando a posteriori P (Θ|D, S).
Considerando a RB como sendo discreta, todas as variáveis têm domı́nios discretos e
finitos, para viabilizar a computação da posteriori P (Θ|D, S) pode-se supor o seguinte:
1. D é uma amostra aleatória com distribuição amostral multinomial.
2. D é uma amostra completa, não há valores faltosos em nenhuma observação da
amostra.
3. Os parâmetros θij são independentes. Conforme Equação 4.5 a distribuição conjunta
deles pode ser fatorada.
qi
n Y
Y
P (θ|S) =
P (θij |S)
(4.5)
i=1 j=1
4. Os parâmetros continuam independentes, dado a amostra multinomial D, conforme
Equação 4.6 a distribuição conjunta condicionada pode ser fatorada.
qi
n Y
Y
P (θ|D, S) =
P (θij |D, S)
(4.6)
i=1 j=1
52
dct-ufms
Tais suposições permitem atualizar a probabilidade de cada vetor de parâmetros θij
como se fosse uma variável simples. Aqui a variável θij é condicionada a estrutura S da
RB e tem distribuição Dirichlet, isto é, θij |S ∼ Dirichlet(θij |αij1 , αij2 , . . . , αijri ). Observe
que há um αijk para cada um dos ri estados da variável Xi . A média dessa distribuição
a priori é dada por E(θijk |S) = αijk |αij , onde αij = αij1 + αij2 + . . . + αijri . Fazendo
αij1 = αij2 = . . . = αijri = 1, então a média E(θijk |S) = 1/ri . Tomando tal média como
um bom estimador de θijk , tem-se que P (Xi = xki |paji , S) = θijk ≈ 1/ri .
Com a disponibilidade da amostra D, pode-se atualizar o conhecimento sobre a distribuição de θij , a qual condicionada a D e a S tem também uma distribuição Dirichlet,
isto é, a variável θij |D, S ∼ Dirichlet(θij |αij1 + Nij1 , αij2 + Nij2 , . . . , αijri + N ijri ). Onde
Nijk mede a freqüência, na amostra D, com que a variável Xi tem o k-ésimo estado,
condicionada ao j-ésimo estado dos seus pais. Essa distribuição a posteriori tem média
dada por:
E(θijk |D, S) = (αijk + Nijk )/(αij + Nij )
(4.7)
onde Nij = Nij1 + Nij2 + . . . + Nijri . Como no caso da priori, fazendo αij1 = αij2 =
. . . = αijri = 1 tem-se que a média assume o valor E(θijk |D, S) = (1 + Nijk )/(ri + Nij ).
Tomando essa média como um estimador de θijk tem-se que a distribuição de probabilidade
P (Xi = xki |paji , D, S) é expressa pela Equação 4.8.
P (Xi = xki |paji , D, S) = (1 + Nijk )/(ri + Nij )
(4.8)
Com os pressupostos de amostra aleatória independente e identicamente distribuı́da;
amostra completa; e distribuição amostral multinomial tem-se os elementos necessários
e suficientes para aprender os parâmetros da RB usando estimativa Bayesiana, uma vez
que sua estrutura S seja conhecida.
Por exemplo, seja uma estrutura de RB simples X1 → X2 → X3 ; com variáveis
discretas: dois estados possı́veis 0, 1; e com amostra de dados disponı́veis dada na Tabela
4.1 é possı́vel calcular a distribuição de probabilidades para cada famı́lia de variáveis.
Para determinar a distribuição de probabilidade P (X2 |X1 ) (baseado na estrutura da
RB) é preciso realizar uma contagem das freqüências2 , na amostra D, para X2 e X1 , denotadas neste caso N2jk , indicando a freqüência com que aparece a variável X2 instanciada
ao seu k-ésimo estado e condicionada ao j-ésimo estado do seu pai X1 . Estas freqüências
são apresentadas na Tabela 4.2. Para estimar a distribuição de probabilidade condicional usa-se a Equação 4.8. No exemplo, para determinar P (X2 = 0|X1 = 0) calcula-se
P (X2 = 0|X1 = 0, D, S) = (1 + N200 )/(r2 + N20 ) = (1 + 4)/(2 + 10) = 0.42, a distribuição
de probabilidade condicional final é apresentada na Tabela 4.3.
2
Também denominadas freqüências ou estatı́sticas suficientes.
53
dct-ufms
Tabela 4.1: Amostra de dados disponı́vel para estrutura X → Y → Z.

X1 X2 X3





0
1
1




0
1
0




1
1
1


 0
0
0
27 casos 1
0
1




1
0
0




1
0
0




1
0
1



.
.
..
 .
..
.
.
Tabela 4.2: Freqüências calculadas para X2 |X1 (N2jk ).
Tabela 4.3: Distribuição de
probabilidade
condicional
P (X2 |X1 ).
X1 (j)
X2 (k) 0 1
0
4 5
1
6 12
N2j
10 17
4.2.2
X1
0
1
P (X2 = 0) P (X2 = 1)
0.42
0.58
0.32
0.68
Estrutura Conhecida e Dados Incompletos - EM Paramétrico
A seção anterior apresentou o caso mais simples de aprendizagem, quando a estrutura é
conhecida e no banco de dados todas as variáveis foram observadas. Em muitos bancos de
dados reais, raramente os dados disponı́veis para aprendizagem estão completos. É comum
eles apresentarem dois tipos de variáveis: com valores faltosos (missings), variáveis cujos
estados no banco de dados, estão as vezes registrado e as vezes não, e as ocultas (hidden)
cujos estados nunca são observados na amostra de dados [64]. Esta seção apresenta
soluções para estas situações, enfatizando-se a abordagem do algoritmo EM.
EM para Aprendizagem de Parâmetros em Redes Bayesianas
O algoritmo EM para aprendizagem de parâmetros, se a estrutura da RB é conhecida, foi
proposto por Lauritzen [46]. Na literatura é freqüentemente denominado algoritmo EM
paramétrico [29, 54] e doravante será referenciado deste modo.
No Passo E do algoritmo EM paramétrico, estima-se os dados faltosos para completar
a amostra de dados incompleta. Esta estimativa é feita usando os valores das variáveis
que foram observadas.
54
dct-ufms
O cálculo da distribuição de probabilidade está baseado na freqüência com que os estados das variáveis aparecem nos dados, denominando-se estas de freqüências suficientes,
e as vezes também na informação a priori. Para realizar a contagem dessas freqüências
para um conjunto de variáveis, percorre-se cada caso da amostra de dados e acumula-se
a freqüência com que cada estado da variável aparece. Quando em um caso analisado
o estado de uma variável não foi observado, usa-se a RB corrente para estimá-lo — na
primeira iteração, essa RB corrente é obtida pela atribuição de valores aleatórios para a
distribuição de probabilidade conjunta. Para realizar essa estimativa, cada estado que foi
observado no caso corrente é inserido na RB como evidência que é propagada, obtendo-se
uma distribuição de probabilidade marginal para a variável que não foi observada. Por sua
vez, essa distribuição de probabilidade será considerada no cálculo das novas freqüências
relativas, denominadas freqüências esperadas.
No Passo M, com as novas freqüências esperadas, aplica-se um algoritmo para aprendizagem de parâmetros com dados completos, tal como o descrito na Seção 4.2.1. Estes
novos parâmetros substituem os parâmetros anteriores da RB, e a partir deles executa-se
novamente o Passo E e o Passo M. Este procedimento é repetido iterativamente até convergir.
Uma descrição formal, adaptada de [64], é dada a seguir. Algumas suposições são
as mesmas que para dados completos. Suponha que os dados D consistem de m casos
independentes e a função de máxima verossimilhança é dada por
L(θ; D, S) ∝ P (D|θ, S) =
m
Y
P (dl |θ, S)
l=1
=
qi ri
n Y
Y
Y
N
θijkijk
(4.9)
i=1 j=1 k=1
onde S é a estrutura da RB, n é o número de variáveis, qi é o número de possı́veis instanciações dos pais P ai da variável Xi , sendo ri o seu número de estados. Nijk é o número
de casos nos quais a variável Xi é instanciada em seu k-ésimo estado, enquanto P ai é
instanciado em seu j-ésimo estado, e θ = (θijk )n×qi ×ri são as probabilidades condicionais.
Tomando a esperança condicional do logaritmo da verossimilhança dos dados completos, e dado o valor corrente do parâmetro θ e os componentes dos dados observados, Dobs ,
obtém-se
qi
ri
n X
X
X
(t)
Q(θ|θ ) =
E(Nijk |Dobs , θ) log θijk
(4.10)
i=1 j=1 k=1
A partir da Equação 4.10 o Passo E, então, consiste em determinar o valor de
E(Nijk |D
obs
, θ) =
m
X
l=1
55
Eθ (χlijk |dobs
l )
(4.11)
dct-ufms
onde dobs
é o componente observado (variáveis observadas) do l-ésimo caso na amostra, e
l
χlijk é definido como

 1, se xi e pai são observados e Xi = k-ésima inst., P ai = j-ésima inst.,
l
obs
0, se xi e pai são observados e Xi 6= k-ésima inst. ou P ai 6= j-ésima inst.,
Eθ (χijk |dl ) =

P (Xi = k, P ai = j|dobs
l , θ, S), em caso contrário.
(4.12)
Para determinar P (Xi = k, P ai = j|dobs
l , θ, S), a rede bayesiana hS, Θi é instanciada
com a evidência observada no l-ésimo caso, dobs
l , e um algoritmo de inferência probabilı́stica é usado para determinar as distribuições de probabilidade.
O Passo M consiste em usar esses valores estimados para calcular θijk . Deste modo,
θijk =
E(Nijk |Dobs , θ)
E(Nij |Dobs , θ)
(4.13)
P
onde Nij = k Nijk . No Passo M, também é possı́vel usar conhecimento a priori para
determinar os valores de θijk . Embora o algoritmo EM convirja de forma confiável, não
garante um ótimo global e freqüentemente finaliza em um máximo local.
A seguir apresenta-se, através de um exemplo, uma iteração do algoritmo EM paramétrico. Suponha uma RB simples com estrutura dada por X1 → X2 , sendo as variáveis
discretas e binárias. A distribuição a priori para X1 é Dirichlet(2, 2) e as distribuições
a priori para as condicionais de X2 são Dirichlet(1, 1). Dirichlet(2, 2) representa conhecimento anterior sobre os estados da variável X1 , de acordo com isto, a distribuição de
probabilidade a priori de X1 seria (0.5, 0.5). A amostra de dados incompleta usada para
aprendizagem é apresentada na Tabela 4.4.
Tabela 4.4: Amostra de dados incompleta para aprendizagem.
Caso X1
1
0
2
0
3
0
4
0
5
1
X2
0
?
0
1
?
A partir do modelo de RB corrente, completa-se os casos (Passo E) usando inferência
probabilı́stica. Na Tabela 4.4 o caso 2 apresenta a variável X2 com estado não observado,
logo, após aplicar inferência , a Tabela 4.5 apresenta esse caso completado com cada um
dos estados possı́veis da variável X2 , sendo que a freqüência para cada um desses casos 2
é a distribuição de probabilidade P (X2 |X1 = 0). Um processo similar é realizado sobre o
caso 5.
56
dct-ufms
Tabela 4.5: Freqüências esperadas.
Caso X1
1
0
2
0
2
0
3
0
4
0
5
1
5
1
X2
0
0
1
0
1
0
1
Freqüências
1
1/2
1/2
1
1
1/2
1/2
A partir dessas freqüências esperadas, pode-se estimar as probabilidades dos parâmetros
(Passo M):
P (X1 = 0) = 6/9, P (X1 = 1) = 3/9
P (X2 = 0|X1 = 0) = 3.5/6, P (X2 = 1|X1 = 0) = 2.5/6
P (X2 = 0|X1 = 1) = 1.5/3, P (X2 = 1|X1 = 1) = 1.5/3
onde X1 = 0 aparece
indica uma freqüência
Ou seja, considerando
E(X1 |D) = (6/9, 3/9).
4 vezes na Tabela 4.5, mas a priori, tem-se Dirichlet(2, 2) que
de 2 para cada estado de X1 , por isso o valor de P (X1 ) = 6/9.
a priori X1 ∼ Dirichlet(2, 2), a posteriori X1 ∼ Dirichlet(6, 3) e
Os outros valores são calculados similarmente.
As próxima iteração usa as distribuições de probabilidades condicionais calculadas no
Passo M. Este processo é repetido até que haja estabilização nos valores das probabilidades.
Métodos Alternativos a EM
Para aprendizagem de parâmetros a partir de dados incompletos existem métodos alternativos que podem ser utilizados para substituir o algoritmo EM paramétrico, a seguir é
dada uma descrição resumida de alguns deles.
Amostragem Gibbs [33] é uma técnica muito mais geral que EM; ao invés de estimar
os parâmetros de interesse diretamente, estima a distribuição a posteriori dos parâmetros,
e sob condições de regularidade moderadas, garante convergência à posteriori verdadeira.
A desvantagem deste método é que consome mais tempo que EM.
Russell e Norving [61] usaram o enfoque do gradiente descendente na tarefa de determinar a máxima verossimilhança dos parâmetros da RB.
Ramoni e Sebastiani [60, 59] criaram um algoritmo denominado Bound and Collapse (BC). Este é um método determinı́stico para estimar probabilidades condicionais de
57
4.3. Aprendizagem de Estrutura
dct-ufms
bancos de dados incompletos. Determina limites inferiores e superiores para cada uma
das possı́veis estimativas, que sejam consistentes com a informação disponı́vel, calculando
assim estimativas máxima e mı́nima que seriam obtidas de todos os possı́veis completamentos do banco de dados. A esses limites, que determinam um intervalo de probabilidades, é aplicada uma combinação convexa, cujos pesos dependem dos padrões supostos
nos dados incompletos, que determina um ponto de corte no intervalo cujo valor vai ser a
estimativa desejada. Este método apresenta as vantagens dos métodos determinı́sticos e
um ganho de eficiência comparado com o algoritmo EM paramétrico [54].
4.3
Aprendizagem de Estrutura
Aprendizagem deste tipo é indutiva; a partir de dados disponı́veis deseja-se construir
uma estrutura para a RB cuja distribuição conjunta melhor represente a verdadeira distribuição subjacente aos dados. Para bancos de dados completos (Seção 4.3.1), embora
não seja um problema totalmente resolvido, existem algoritmos que apresentam soluções
satisfatórias. Para dados incompletos, este é ainda um problema em constante pesquisa
sendo que os algoritmos baseados no EM (Seção 4.3.2) apresentaram os primeiros resultados significativos. Muitas das técnicas usadas nos algoritmos EM para aprendizagem de
estruturas são similares as usadas nos algoritmos para dados completos, particularmente,
usam-se as diretrizes do paradigma de busca e pontuação descrito a seguir.
4.3.1
Dados Completos-Paradigma Busca e Pontuação
Uma idéia simples deste tipo de aprendizagem seria, baseando-se nos dados, determinar
relações entre as variáveis, adicionar ou excluir arcos, estabelecer direções, enfim definir um GAO para o qual serão calculadas distribuições de probabilidades. Em geral, há
dois paradigmas principais de aprendizagem de modelos gráficos a partir de dados: paradigma de busca e pontuação e o baseado em restrições ou independência condicional [11].
Em geral, conta-se com uma amostra de dados completa que representa as observações
coletadas de um conjunto de variáveis próprias de um domı́nio, e deseja-se determinar a
estrutura e, posteriormente, as probabilidades para a melhor RB que representa os dados. Este problema é útil em muitas aplicações, por exemplo, mineração de dados, onde
grandes quantidades de dados disponı́veis precisam ser interpretados [34].
O primeiro método de aprendizagem aplicado a uma estrutura de árvore representando
conhecimento é devido a Chow e Liu [14]. Para estimar uma distribuição de probabilidade conjunta P , parte de distribuição de probabilidade P 0 e em sua correspondente árvore
de conhecimento aplica um método de aprendizagem até chegar numa distribuição mais
próxima de P .
Rebane e Pearl apud [38] criaram um algoritmo para ser utilizado juntamente com
58
dct-ufms
o método de Chow e Liu, chamado algoritmo de recuperação de poliárvores, destinado
aos casos em que a representação gráfica da distribuição P é dada em forma de uma
poliárvore. Então, através do método de Chow e Liu, é gerada a estrutura básica da
árvore e em seguida, aplicando-se nesta estrutura o algoritmo de poliárvores, obtém-se a
representação gráfica da distribuição [38].
No paradigma de busca e pontuação, a aprendizagem se realiza buscando uma estrutura que seja aderente aos dados. Em geral se inicia com um grafo sem arcos, então,
usa-se algum método de busca gulosa que adicione um arco ao grafo. O próximo passo
consiste em usar uma função de pontuação para determinar se a nova estrutura é melhor
que a anterior. Se for melhor, o novo arco adicionado é mantido e tenta-se adicionar outro. Este processo continua até que nenhuma nova estrutura seja melhor que as anteriores.
Diferentes critérios de pontuação têm sido desenvolvidos para avaliar uma estrutura,
tais como métodos de pontuação Bayesianos [18, 36, 6], métodos baseados na entropia,
método de comprimento mı́nimo de descrição [45], e método de mensagem de comprimento mı́nimo.
Dentro deste paradigma a busca por novas estruturas é realizada através de métodos
de busca heurı́stica. Para reduzir o espaço de busca, muitos algoritmos requerem ordenamento dos nós. Posto que os métodos de aprendizagem usando busca e pontuação são
NP-difı́ceis [12], a aplicação da busca heurı́stica é justificada.
No paradigma de análise de independência condicional, o problema da aprendizagem
é abordado de maneira diferente. Devido a que a estrutura traz embutidas muitas dependências do modelo subjacente, os algoritmos deste paradigma tentam descobrir as
dependências a partir dos dados, e então usar essas dependências para inferir a estrutura. As relações de dependência são avaliadas pelo uso de alguma classe de teste de
Independência Condicional (IC). Os algoritmos descritos por Wermuth e Lauritzen [70];
Spirtes et al [65] e Cheng et al [11] estão nesta categoria.
Ambos paradigmas têm vantagens e desvantagens. Por serem bastante especı́ficas às
suas aplicações, não se pode eleger um paradigma como sendo o melhor [8]. Em geral,
o paradigma de análise de independência é mais eficiente que o paradigma de busca e
pontuação, quando usado para aprender redes esparsas (que não são densamente conectadas) [11]. Também podem obter a melhor estrutura quando a distribuição de probabilidade dos dados satisfaz certas suposições de modelos. Mas, muitos destes algoritmos
requerem um número exponencial de testes IC e testes IC de ordem superior (testes IC
com conjuntos condicionantes grandes, com número grande de pais).
Como apontado em [18], testes IC com conjuntos condicionantes grandes podem não
ser confiáveis, a menos que o volume de dados seja grande o suficiente. De outro lado,
embora o paradigma de busca e pontuação não possa encontrar a melhor estrutura, devido
59
dct-ufms
a sua natureza heurı́stica, seu escopo de modelos probabilı́sticos é maior que o paradigma
de análise de independência [11].
Trabalhos que apresentam soluções hı́bridas, misturando ambos paradigmas também
são encontrados na literatura, alguns exemplos podem ser vistos em [8].
A seguir aprofunda-se o estudo dos algoritmos baseados em busca e pontuação e algumas das funções de pontuação principais, versões modificadas destas métricas serão
usadas para aprendizagem de estruturas a partir de dados incompletos com EM.
Métodos Baseados em Busca e Pontuação
Os métodos baseados em busca e pontuação seguem o seguinte principio: uma função
de pontuação ou métrica é definida para cada estrutura candidata de RB, avaliando seu
grau de aderência aos dados. O objetivo é encontrar no espaço de estruturas candidatas
a a que tem maior pontuação. O espaço de estruturas é combinatório, consistente de um
número super exponencial de estruturas. Assim, não fica claro como encontrar a rede
com maior pontuação [36]. Por outro lado, o problema de busca combinatória que tenta
otimizar uma função é bem estudado na literatura. Conseqüentemente, a solução consiste
em definir um espaço de estruturas candidatas e então realizar uma busca heurı́stica.
À luz dos enunciados anteriores, um algoritmo de aprendizagem de RB neste paradigma requer os seguintes componentes:
• Função de pontuação para diferentes estruturas de rede candidatas,
• A definição do espaço de busca: operadores que tomam uma estrutura e a modificam
para produzir outra,
• Um algoritmo de busca que encontre a estrutura ótima.
Há três funções de pontuação principais freqüentemente usadas para aprender RBs:
baseada no logaritmo da verossimilhança [18], baseada no princı́pio da descrição de comprimento mı́nimo (MDL) [45], e a pontuação Bayesiana [36].
A seguir apresenta-se um exemplo de uso das métricas para avaliar estruturas. Os
dados (D) para este exemplo são apresentados na Tabela 4.6, e deseja-se conhecer a
relação entre o sexo de uma pessoa (X), o quociente intelectual(I) e o valor alto no
intervalo de confidência (C).
Suponha também um espaço de estruturas candidatas, como o dado na Figura 4.1.
Qual dessas estruturas teria a maior pontuação, considerando os dados disponı́veis?
60
dct-ufms
S1
X
I
C
S2
X
I
C
S3
X
I
C
S4
X
I
C
I
S5
X
C
. . .
Figura 4.1: Várias estruturas de rede candidatas.
Tabela 4.6: Banco de dados completo para aprendizagem.
Estudante
1
2
3
4
Sexo
QI
valor alto IC
masculino
baixo
nao
feminino promédio
sim
masculino
alto
sim
feminino
alto
sim
Em geral, seja D o conjunto de dados com m casos e B = (S, Θ) e B 0 = (S’, Θ0 ) duas
RBs, então:
P (S|D)
Q=
(4.14)
P (S’|D)
é uma métrica (Bayesiana) com uma distribuição de probabilidades P definida sobre RBs
e o conjunto de dados, e usada para avaliar estruturas.
Note que:
P (S, D)/P (D)
P (S, D)
=
P (S’, D)/P (D)
P (S’, D)
(4.15)
P (S, D) = P (D|S)P (S)
(4.16)
log P (S, D) = log P (D|S) + log P (S)
(4.17)
Q=
e
Assim:
deve ser determinado para cada RB (B = (S, Θ)). O logaritmo da verossimilhança é mais
fácil de avaliar que a verossimilhança, devido a que o logaritmo troca os produtórios por
somatórios.
61
dct-ufms
Determinando P (D|S)
Para determinar P (D|S) é necessário que as seguintes suposições se satisfaçam:
• Suposição 1: não há valores faltosos em D.
• Suposição 2: os casos dl ∈ D aconteceram independentemente, P (D|S) =
Qm
l=1
P (dl )
Um aproximação de P (D|S) foi definida em [18] e é dada a seguir:
P (D|S) =
m
Y
P (dl )
l=1
=
qi ri
m Y
n Y
Y
Y
N
θijkijk
(4.18)
l=1 i=1 j=1 k=1
Então
qi
ri
m X
n X
X
X
log P (D|S) =
Nijk log
l=1 i=1 j=1 k=1
Nijk
Nij
(4.19)
A definição da Equação 4.19 requer freqüências que podem ser facilmente coletadas de
amostras de dados completas. Essa coleta de informação depende das relações locais
entre as variáveis e seus pais correspondentes (Nijk e Nij ). Um exemplo de cálculo é
apresentado a seguir, baseado nos dados da Tabela 4.6 e a Figura 4.1. Particularmente,
para a estrutura S1 (X → I → C), a notação das freqüências Ni jk da 4.19 fica: NX
significando as freqüências da variável X que não tem pais, NI X as freqüências da variável
I condicionadas ao pai X e NC I freqüências da variável C condicionada ao pai I:
log P (D|S1 ) =
X
NX log
X
+
XX
C
2
= 2 log
4
1
1 log
2
1
1 log
2
1
1 log
1
1
1 log
1
NX X X
NIX
+
NIX log
N
NX
I
X
NCI log
I
2
4
0
+ 0 log
2
1
+ 1 log
2
0
+ 0 log
1
2
+ 2 log
2
+ 2 log
NCI
NI
+
+ 0 log
0
1
+ 1 log +
2
2
+
+ 0 log
0
0
+ 0 log +
2
1
= −8
Note que limx→0 x log x = 0. Avaliando S2 tem-se log P (D|S2 ) = −11.25, então
P (D|S1 ) > P (D|S2 ). Similarmente é avaliada cada uma das outras estruturas candidatas escolhendo-se a de maior pontuação.
62
dct-ufms
Conhecimento a Priori(P (S))
Se o conhecimento a priori para cada estrutura candidata for considerado, a métrica
denomina-se bayesiana. Em caso contrário, pode-se assumir que todas as RBs são igualmente verossı́meis, ou seja, P (S) é uma distribuição de probabilidades uniforme, está
métrica seria considerada de máxima verossimilhança e neste caso se cumpre:
log P (S, D) = log P (D|S) + c
(4.20)
onde c ∈ R, é uma constante. Assim
log q = log P (D|S) − log P (D|S’)
(4.21)
é denominado fator Bayes logarı́tmico.
Limitações de P (S, D)
O logaritmo da verossimilhança cresce linearmente conforme o tamanho dos dados, m.
As redes com as maiores pontuações são aquelas onde uma variável e seus pais têm uma
correlação maior. Portanto, a adição de uma arco a uma estrutura de RB sempre aumenta
o logaritmo da verossimilhança. Como resultado, a estrutura de rede que maximiza a
verossimilhança é, amiúde, a estrutura completamente conectada. Esta é uma falha da
métrica de pontuação do logaritmo de verossimilhança e não é desejada. Seria aconselhável
penalizar estruturas com muitos arcos. Uma solução considerada foi adicionar um fator
que penalizasse a complexidade da estrutura, isto é,reduzisse o número de arcos:
1
r = − k log m
2
onde k =
Pn
i=1
(4.22)
2qi a métrica que resulta da aplicação deste fator é:
1
Q(S, D) = log P (S) − m.H(S, D) − k · log m
2
(4.23)
com log P (D|S) = −m · H(S, D). Esta métrica é denominada descrição de comprimento
mı́nimo (MDL) [45] e consta dos seguintes elementos:
• P(S): probabilidades a priori da estrutura do grafo.
• m = |D|: número de casos no banco de dados D.
• −H(S, D): valor negativo do ajuste entre o banco de dados D e a rede bayesiana B
• − 12 k · log m: termo penalidade, onde k é o número de probabilidades que precisam
ser avaliadas para B.
A métrica MDL faz balanceamento entre ajuste aos dados e complexidade do modelo.
A adição de uma variável pai causa aumento do logaritmo da verossimilhança e, também,
63
dct-ufms
da penalização. Haverá adição de um arco se o incremento na verossimilhança for importante. Esta métrica, modificada parcialmente, pode ser usada para aprendizagem de RBs
a partir de dados incompletos. Na Seção 4.10 é retomado seu estudo.
A métrica Bayesiana é uma outra alternativa para avaliar estruturas de rede a partir
de dados, sendo sua forma geral:
BDe(S : D) = P (S|D) =
P (D|S)P (S)
P (D)
(4.24)
Usualmente P (D) é constante, e pode ser ignorado quando estruturas diferentes são comparadas e então, o modelo maximiza P (D|S)P (S). A possibilidade de usar conhecimento a
priori permite dar preferência a algumas estruturas sobre outras. Neste caso, a probabilidade P (D|S) é calculada de uma forma distinta das métricas baseadas na verossimilhança:
Z
P (D|S) = P (D|θ, S)P (θ|S)dθ
(4.25)
Da equação 4.25 pode-se observar que, havendo mais parâmetros disponı́veis, mais variáveis são integradas. Como resultado, cada dimensão faz o valor da integral diminuir
pois, o “topo” da função de verossimilhança é uma fração mais pequena do espaço. Este
princı́pio permite dar preferência a redes com poucos parâmetros. Pode ser demonstrado
que a métrica Bayesiana é uma forma geral da métrica MDL [36]. A métrica MDL pode
ser vista como uma aproximação da métrica Bayesiana. Portanto, a métrica Bayesiana é
também um compromisso entre complexidade de modelos e aderência aos dados.
Com as suposições de independência de parâmetros local e global, dados completos e
sendo as distribuições a priori Dirichlet, a verossimilhança é:
P (D|S) =
qi
n Y
Y
ri
Y
Γ(αij )
Γ(αijk + Nijk )
Γ(Nij + αij ) k=1
Γ(αijk )
i=1 j=1
onde cada αij é uma Dirichlet(αij1 , . . . , αijri ) e αij =
Pri
k=1
(4.26)
= αijk .
Cada parâmetro αijk representa estatı́sticas “intuitivas” ou conhecimento anterior sobre os parâmetros. Particularmente, se esses parâmetros não são informativos (αijk = 1),
a métrica é denominada K2 [18]:
qi
n Y
Y
ri
Y
(ri − 1)!
P (D|S) =
(Nijk )!
(N
+
r
−
1)!
ij
i
i=1 j=1
k=1
(4.27)
Se a métrica K2 fosse utilizada para avaliar estruturas, grafos equivalentes (que representam as mesmas independências) não teriam a mesma pontuação. Uma métrica
equivalente pode ser obtida se considerada uma amostra de tamanho global N 03 e a partir
3
Indica conhecimento anterior.
64
dct-ufms
dela são selecionados os parâmetros para todas as probabilidades condicionais de acordo
com a expressão dada por Buntime [6]:
αijk
N0
=
r i qi
(4.28)
As métricas Bayesianas em suas versões modificadas também são úteis em aprendizagem a partir de dados incompletos. Particularmente, o algoritmo EM estrutural (Seção
4.2.2) usa uma métrica Bayesiana denominada BDe [36] para avaliar estruturas.
A Busca Heurı́stica
Uma vez definida uma métrica para avaliar estruturas de RBs, é necessário definir uma
estratégia para percorrer o espaço super exponencial de estruturas. Os algoritmos descritos brevemente aqui, serão detalhados no Capı́tulo 5. Eles fazem sucessivas mudanças
nos arcos de uma estrutura candidata a RB. As possı́veis mudanças que podem ser feitas
são fáceis de identificar. Para qualquer par de variáveis, se há um arco entre elas, então
esse arco pode ser invertido ou removido. Se não há arco entre elas, então um arco pode
ser adicionado em cada direção.
Todos os arcos estão sujeitos à restrição de que a rede resultante não pode conter
ciclos dirigidos. Usa-se ε para denotar o conjunto de mudanças possı́veis de um grafo,
e ∆(e) para denotar o incremento no logaritmo da pontuação da rede que resultou da
modificação, e ∈ ε.
As métricas para avaliar estruturas descritas anteriormente têm uma propriedade importante, são decomponı́veis4 , ou seja, o cálculo do logaritmo da verossimilhança está
baseado em somatórios de componentes locais [36]. Componentes locais são estatı́sticas
suficientes calculadas da amostra de dados completos, para as possı́veis instâncias de uma
variável e seus pais (anteriormente denominadas Nijk ). Dada uma métrica decomponı́vel,
se um arco é adicionado ou removido de Xi , só M etrica(Xi |P ai ) (a função de pontuação)
precisa ser avaliada para determinar ∆(e), isto é, a mudança na pontuação. Se um arco
entre Xi e Xj é invertido, só M etrica(Xi |P ai ) e M etrica(Xj |P aj ) precisam ser avaliadas.
Isto possibilita a eficiência no cálculo das funções de pontuação.
Um algoritmo de busca heurı́stica simples é busca local. Primeiro, escolhe-se um grafo.
Então, avalia-se ∆(e) para todos e ∈ ε, e realiza-se a mudança e conforme ∆(e) seja
um máximo, desde que positivo. A busca termina quando não há e com valor positivo
para ∆(e). A medida que as estruturas de rede são visitadas, armazena-se os l´s com a
maior pontuação global. Candidatos para o grafo inicial incluem o grafo vazio, um grafo
aleatório, e uma rede anterior fornecida por um especialista. Estes algoritmos de busca
heurı́stica são usados da mesma maneira dentro de algoritmos de aprendizagem de RBs
4
Tradução do inglês decomposability.
65
dct-ufms
a partir de dados incompletos, a diferença principal é que, neste caso usa-se métricas
aproximadas e estatı́sticas esperadas para avaliar as estruturas.
4.3.2
Dados Incompletos-EM
Diferente do caso de dados completos, não muitos algoritmos têm sido desenvolvidos para
a tarefa mais geral de aprendizagem de estruturas a partir de dados incompletos. Os
algoritmos descritos nesta seção formam a base teórica dos algoritmos que foram implementados. Como para aprendizagem de parâmetros a partir de dados incompletos a
abordagem usada é do algoritmo EM, detalhes de implementação e maiores especificações
são apresentados no Capı́tulo 5.
Uma abordagem inicial deste problema pode ser atribuı́da a Cooper e Herskovits [18].
Esses autores apresentaram um método teórico para lidar com dados faltosos durante a
aprendizagem de RBs. A idéia principal desse método consiste em somar sobre todas as
possı́veis instanciações dos dados faltosos quando calculada a função de verossimilhança,
a qual é usada para comparar as várias RBs. Mas, dada a complexidade exponencial deste enfoque, não é factı́vel usá-lo, a não ser para conjuntos de dados pequenos. Embora,
Cooper em [17] estenda esse enfoque para produzir um algoritmo relativamente eficiente,
este ainda pode ser computacionalmente caro para muitos problemas reais.
Heckerman em [33], discute vários enfoques Monte-Carlo para calcular as funções de
verossimilhança dos dados observados, que podem então ser usados para aprender a RB
mais verossı́mil. Porém, embora adequados, esses métodos são computacionalmente ineficientes [64]. Heckerman, nesse mesmo trabalho, também apresenta um método mais
eficiente para calcular a verossimilhança baseado em aproximação Gaussiana.
Ramoni e Sebastiani [60] estendem seu enfoque bound and collapse, descrito brevemente na Seção 4.2.2, à tarefa de aprender parâmetros e estrutura de dados incompletos.
No entanto, embora o método seja computacionalmente eficiente, é válido somente se os
dados faltosos na amostra foram definidos aleatóriamente [64].
Chickering [13] usou o método de amostragem de Gibbs para tratar com dados faltosos. Na aplicação desta técnica, a detecção de convergência é uma questão aberta. Além
disso, o método é lento para convergir e computacionalmente caro.
De maneira discutı́vel, o avanço mais significativo na área de aprendizagem de estruturas a partir de dados incompletos tem sido o algoritmo EM estrutural (SEM) de
Friedman [30]. Este método transforma o problema da aprendizagem de estrutura com
dados incompletos em um mais simples. Usa o algoritmo EM paramétrico para completar
os dados e busca a melhor estrutura de RB usando um algoritmo de busca gulosa. A
inovação do método de Friedman foi economizar cálculos usando estimativas do algoritmo
66
dct-ufms
EM paramétrico para a estrutura corrente, fazendo, deste modo, a avaliação de candidatos para a próxima estrutura e, então executando EM novamente só para a estrutura
escolhida. Porém, quando o espaço de busca é muito grande, o algoritmo de busca gulosa finalizará em uma solução denominada ótima local. Para resolver este problema, na
prática, o algoritmo pode ser reiniciado com novas estruturas geradas aleatóriamente.
Singh [64] teve uma percepção similar a Friedman, mas seu procedimento é diferente.
Em cada passo, gera k atribuições conjuntas a todos os valores faltosos usando o melhor
modelo das iterações prévias. Então chama o procedimento de aprendizagem de Cooper e
Herskovists [18] sobre cada um dos conjuntos de dados completados. Finalmente, faz uma
“fusão” das redes aprendidas, treina os seus parâmetros usando o EM paramétrico e reitera. Este enfoque pode ser interpretado como uma aproximação estocástica do algoritmo
EM estrutural. Usando k conjuntos de dados completados, Singh aproxima a esperança
da métrica. Mas, ao invés de combinar estas estimativas em um único procedimento de
busca por estruturas, realiza uma busca para cada estimativa. Entretanto, a fusão é um
procedimento que traz várias complicações, conforme é descrito em [64].
Variantes do algoritmo EM estrutural foram propostas por Meila e Jordan [48] e Thiesson et al [66]. Ambos enfoques aprendem multi-redes (estas podem ser imaginadas como
“misturas” de RBs) nas quais a variável seletora está oculta. Meila e Jordan aprendem
multi-redes nas quais cada rede é uma árvore. Eles aproveitam esta restrição para coletar
todas as estatı́sticas requeridas em um passo em cada iteração. Thiesson et al aprendem
multi-redes gerais usando a métrica de Cheeseman-Stutz [10]. Este último algoritmo pode
ser visto como uma instância do algoritmo de Friedman [30], após aplicar aproximação
linear a multi-redes. Thiesson et al usam métodos eficientes para, temporariamente, armazenar estatı́sticas esperadas quando muitas das variáveis de interesse são Gaussianas.
Isto permite responder a todas as consultas durante a busca por estrutura, após um simples passo sobre os dados de treinamento em cada iteração.
Uma abordagem diferente a EM foi desenvolvida por Myers et al [51], os quais, para
completar os dados faltosos usam operações genéricas (baseadas em programação evolutiva), e desenvolvem as estruturas de rede e os dados faltosos ao mesmo tempo. Embora
possam evitar finalizar em um máximo local, uma de suas desvantagens é que o processo
para completar os dados mediante operadores genéricos é fortemente estocástico, e poderia não refletir as caracterı́sticas da distribuição de probabilidade subjacente aos dados
faltosos. Deste modo, quando o número de dados faltosos é grande, a convergência do
algoritmo poderia ser muito lenta e a eficiência do algoritmo comprometida.
Tian et al [67], baseando-se nos trabalhos de Friedman [30] e Myers et al [51], desenvolveram o algoritmo EM-EA para aprendizagem de estruturas de RB a partir de dados
incompletos. O algoritmo EM-EA transforma os dados incompletos em completos usando
o algoritmo EM e então procura por estruturas de rede usando uma algoritmo evolutivo
(EA) com os dados completados. Com este algoritmo, alivia-se os problemas de máximo
local do algoritmo EM estrutural e de pouca eficiência e convergência do algoritmo de
67
dct-ufms
Myers et al.
Peña et al [54] propuseram uma mudança na definição geral do algoritmo EM estrutural: para realizar a otimização dos parâmetros da RB usam o método BC+EM [53] ao
invés de usar o algoritmo EM paramétrico, sendo o algoritmo final denominado Bayesian
Estructural BC+EM (BS-BC+EM). A idéia principal do método BC+EM consiste em
alternar entre o método BC [60] e o algoritmo EM de paramétrico [46].
O método BC não é útil quando há variáveis ocultas [54]. A razão desta limitação é que
os intervalos de probabilidades retornados pela método BC seriam muito grandes e pouco informativos, pois todas as entradas faltosas estariam concentradas em uma variável.
O método BC+EM supera este problema realizando em cada passo um completamento
parcial do banco de dados.
Todos os algoritmos supracitados seguem as diretrizes do paradigma de busca e pontuação. Até pouco tempo atrás não havia algoritmos baseados em análise de independência para lidar com dados incompletos. Com dados completos, o método de Cheng [11]
é um dos algoritmos mais representativos desta classe de algoritmos. Tian et al [68] apresentaram um método que estende o trabalho de Cheng para dados incompletos, o algoritmo EMI. Este é um método para estimar informação mútua diretamente das amostras de
dados incompletos. Usando o princı́pio do método BC [60], EMI começa calculando estimativas de intervalos para a probabilidade conjunta de um conjunto de variáveis. Essas
estimativas são obtidas de possı́veis completamentos dos dados incompletos. Então, EMI
calcula a estimativa de um ponto via combinação convexa dos pontos extremos. Baseado
nessas estimativas dos pontos, EMI obtém a informação mútua (condicional). Finalmente, aplica-se EMI ao algoritmo de Cheng para aprender RB com dados incompletos.
Como descrito nos parágrafos anteriores, a maioria dos algoritmos que foram desenvolvidos estão baseados nas idéias de Friedman. Um dos objetivos deste trabalho é desenvolver o algoritmo EM estrutural, considerando-se que a partir desta implementação,
seja facilitado o desenvolvimento de cada uma de suas variantes. A seguir são detalhados
os dois algoritmos EM principais de Friedman.
Algoritmo Model Selection EM (MS-EM)
Muitos dados da vida real contém valores faltosos. Aprender, uma estrutura concisa a
partir deles é crucial para evitar overfitting 5 e permitir inferências eficientes no modelo
aprendido. A Introdução de variáveis ocultas, que não aparecem explicitamente no modelo, pode conduzir a aprender modelos mais simples. Essas foram as motivações principais
para Friedman desenvolver o algoritmo Model Selection EM (MS-EM) para aprendizagem
de estruturas de redes a partir de dados incompletos e com variáveis ocultas.
5
Optou-se pelo termo em inglês já que, quando usado no contexto computacional, o mesmo não possui
tradução adequada para a lı́ngua portuguesa.
68
dct-ufms
Em aprendizagem com dados completos, usando as independências embutidas na estrutura da rede, pode-se decompor a função de verossimilhança em um produto de termos
(Seção 4.3.1), onde cada termo depende só da escolha dos pais para uma variável particular e as estatı́sticas suficientes nos dados (Nijk ). Isto permite uma avaliação modular de
uma estrutura candidata e de todas as mudanças locais nela. Além disso, a avaliação de
uma mudança particular (por exemplo, a adição de um arco de X1 a X2 ) permanece igual
depois de mudar uma parte diferente da rede (por exemplo, a remoção de um arco de X2
a X3 ). Deste modo, após realizada uma mudança, não é necessário reavaliar a métrica
de pontuação de muitos dos possı́veis vizinhos no espaço de busca. Estas propriedades
determinam procedimentos de aprendizagem eficientes [29].
Quando os dados são incompletos, a função da verossimilhança não pode ser descomposta. Nesse caso é preciso uma otimização dos parâmetros da rede, por exemplo, via o
algoritmo EM paramétrico (descrito na Seção 4.2.2). Neste caso uma mudança local, em
uma parte da rede, pode afetar a avaliação de uma mudança em outra parte da rede. Um
método ingênuo avaliaria todos os possı́veis vizinhos (redes que diferem em um ou mais
arcos) de cada candidato visitado. Isto exigiria muitas chamadas ao procedimento EM
paramétrico antes de fazer uma simples mudança no candidato corrente.
A idéia de Friedman [29] foi realizar a busca pela melhor estrutura dentro do procedimento EM. Neste procedimento mantém-se uma rede candidata corrente, calculando-se
estatı́sticas esperadas para avaliar estruturas alternativas. Como esta busca é feita em um
cenário de dados completos, pode-se explorar as propriedades das métricas de pontuação
para busca efetiva. De fato, são usadas os mesmos procedimentos de busca de estruturas
a partir de dados completos. Em contraste com o método ingênuo, este procedimento
permite progredir na busca em cada iteração do EM e são necessárias, relativamente,
poucas iterações para aprender redes não triviais.
Em resumo, o algoritmo denominado Model Selection EM trata da seleção de modelos
e também de estimativas de parâmetros, formalmente:
1. Escolha S0 e Θ0 aleatóriamente.
2. Para n = 0, 1, . . . até convergir faça
(a) Encontre uma estrutura Sn+1 que maximize Q(· : Sn , Θn );
(b) Defina Θn+1 = arg maxΘ Q(Sn+1 , Θ : Sn , Θn ).
Em cada etapa escolhe-se um modelo e parâmetros com a maior pontuação esperada
(baseados nas estatı́sticas esperadas calculadas pelo algoritmo EM paramétrico), dado um
modelo prévio. Em [29], estão descritas as provas de convergência deste algoritmo.
69
dct-ufms
Para determinar totalmente este algoritmo falta definir Q, a função de pontuação ou
métrica usada. Neste caso, é uma métrica de pontuação esperada baseada na métrica
MDL [45] para dados completos. Da definição da métrica
da
P MDL e da linearidade
0
0
0
0
esperança, obtém-se a aproximação Q(S, Θ : S , Θ ) =
i Qi (Xi , θi : B ), onde B =
(S0 , Θ0 ) representa o modelo anterior e
0
Qi (Xi , θi : B ) =
qi
ri
X
X
E[Nijk |o] log(θijk )
j=1 k=1
−
log m
qi
2
(4.29)
onde o são as variáveis observadas e m o tamanho da amostra de dados.
Deste modo, a esperança é dada com relação a B 0 , obtendo-se uma decomposição
análoga à métrica MDL para dados completos. A única diferença é que usa-se estatı́sticas
esperadas baseadas no modelo B 0 ao invés de usar as estatı́sticas completas. Similarmente
ao caso de dados completos, maximiza-se a pontuação esperada para uma estrutura parE[N |o]
ticular, S, atribuindo θijk = E[Nijk
. Conseqüentemente, usam-se as mesmas estratégias
ij |o]
de busca existentes para o caso de dados completos.
Algoritmo EM Estrutural Bayesiano (SEM)
Um problema do algoritmo Model Selection EM [29] é que sua aplicação é restrita a
funções que aproximam a métrica Bayesiana [54]. Há indicações teóricas e práticas que
a métrica Bayesiana permite uma melhor avaliação das propriedades de generalização de
um modelo dado os dados. Além disso, a métrica de pontuação Bayesiana possibilita a
incorporação de conhecimento anterior no processo de aprendizagem.
Friedman, definiu um algoritmo denominado Bayesian Structural EM (SEM) [30] usando uma métrica Bayesiana fazendo suposições sobre a forma da distribuição a priori. Similarmente ao seu trabalho anterior [29], este método está também baseado na idéia de
completar dados usando a melhor estimativa atual. Porém, neste caso, a busca é sobre o
espaço de estruturas ao invés do espaço de estruturas e parâmetros. O algoritmo SEM,
tenta otimizar diretamente a métrica Bayesiana ao invés de fazer uma aproximação assintótica.
Sejam, D o conjunto de dados,O conjunto de variáveis observáveis e H o conjunto
de variáveis ocultas ou faltosas. Seja, também, um conjunto de modelos S em que cada
modelo (estrutura) S ∈ S é parametrizado por um vetor ΘS e que há atribuições a priori
para estruturas e parâmetros. Para encontrar um modelo maximum a posteriori é preciso
maximizar P (D|S)P (S). Devido a que D contém valores faltosos, P (D|S) não pode ser
avaliada eficientemente, mas, pode-se calcular ou estimar a verossimilhança dos dados
completos dada por P (H, O|S). Com estes elementos definidos, o algoritmo SEM fica
70
dct-ufms
determinado como a seguir:
Bayesian-SEM (M0 , o)
1. Para n = 0, 1, . . . até convergir
(a) Calcular a probabilidade posterior P (ΘSn |Shn , o).
(b) Passo E: Para cada S, calcular
Q(S : Sn ) = E[log P (H, o, Sh )|Shn , h]
X
P (h|o, Shn ) log P (h, o, Sh ).
=
h
(c) Passo M: Escolher Sn+1 que maximize Q(S : Sn ).
(d) Se Q(Sn : Sn ) = Q(Sn+1 : Sn ) então
retornar Sn .
Como no algoritmo MS-EM, a idéia principal deste procedimento é que a cada iteração
ele tenta maximizar a pontuação esperada dos modelos ao invés de sua pontuação corrente. O procedimento converge quando não há melhora na pontuação da função objetivo.
Para avaliar estruturas candidatas usa-se uma aproximação da métrica Bayesiana
BDe [36]. Maiores detalhes desta métrica e aspectos de implementação são dadas no
Capı́tulo 5 onde se apresenta os três tipos de aproximações de Friedman para esta métrica.
Uma restrição do algoritmo EM estrutural, é que está limitado à aprendizagem de
um modelo simples. Na prática, usa-se conjuntos de modelos (denominados comitês)
com pontuações altas para fazer predições. Tais comitês podem fornecer melhores aproximações, e garantir que as particularidades de um modelo simples não interfiram com a
evidência, que também é valida para outros modelos. Meila e Jordan [48], e Thiesson et
al [66] tentam aproximar tais comitês aprendendo misturas de modelos, onde cada componente da mistura é uma RB. Contudo, eles estão aprendendo um modelo MAP, em uma
classe maior de modelos. Isto seria útil se a fonte dos dados pudesse ser melhor descrita
por uma mistura. No entanto, não dispensa a dependência de um modelo simples.
4.4
Neste capı́tulo foi apresentado o problema da aprendizagem de RBs em situações em que a
estrutura está ou não disponı́vel, e os dados são completos ou incompletos. Foi focalizada
a aplicação do algoritmo EM em vários desses casos. Para aprendizagem de parâmetros a
partir de dados incompletos, além dos métodos descritos na Seção 4.2.2, Singh [64] discute
outros métodos alternativos.
71
dct-ufms
Para aprendizagem de estrutura, foram descritos brevemente os paradigmas de busca e pontuação e análise de independência. Para dados incompletos, foi aprofundado a
abordagem dos algoritmos EM de Friedman e discutiu-se algumas de suas variantes. Está
é uma área de pesquisa constante, sendo que algoritmos baseados em análise de independência não foram muito usados até então.
Como no caso de inferência de RBs, algumas ferramentas foram analisadas, e estudadas as suas capacidades de aprendizagem. Hugin6 , é uma ferramenta comercial que
oferece alguns algoritmos para aprendizagem de estruturas e parâmetros de RBs, porém a
versão avaliada, de tipo experimental, tinha a sua funcionalidade limitada. Os algoritmos
disponı́veis são: EM paramétrico, para aprendizagem de parâmetros e dois algoritmos
baseados em análise de independência, PC e NPC [65], para aprendizagem de estrutura.
BNPC é uma ferramenta gratuita que implementa algoritmos de aprendizagem de
estruturas a partir de dados completos, baseado no algoritmo de busca e pontuação de
Cheng et al [11]7 . Bayesware é uma ferramenta comercial para aprendizagem de estrutura
e parâmetros a partir de dados completos, usa o algoritmo Bound and Collapse [60, 59]8 .
BNJ é um conjunto de ferramentas em Java desenvolvidas na universidade de Kansas, com
algoritmos de aprendizagem dos dois paradigmas, porém limitados a dados completos9 .
6
http://www.norsys.com/
http://www.cs.ualberta.ca/ jcheng/bnpc.htm
8
http://www.bayesware.com/
9
http://bndev.sourceforge.net/
7
72
Capı́tulo 5
Implementação e Resultados
Este capı́tulo apresenta detalhes de implementação e resultados experimentais dos algoritmos EM, objetivo deste trabalho. Para avaliar o desempenho foram realizados uma
série de experimentos variando parâmetros, tais como tamanho do conjunto de dados,
quantidade de dados faltosos e mecanismos para gerar os dados. Os objetivos destes experimentos são descritos na Seção 5.1. Na Seção 5.2 são apresentados os conjuntos de
dados usados nos testes, enquanto que a metodologia experimental é discutida na Seção
5.3.
As especificações algorı́tmicas e a análise de resultados são descritos na Seção 5.4.
Especificamente, é detalhada a plataforma usada para desenvolvimento (Seção 5.4.1); o
conjunto de algoritmos que fazem parte da implementação do algoritmo EM parámetrico
(Seção 5.4.2) e o algoritmo EM estrutural (Seção 5.4.3), assim como os resultados experimentais obtidos em cada caso. Finalmente, um sumário dos resultados de aprendizagem
é dado na Seção 5.5.
5.1
Objetivos
Seguindo as diretrizes dadas no Capı́tulo 4, os algoritmos EM para aprendizagem de estrutura e parâmetros implementados devem lidar corretamente com dados incompletos e
variáveis ocultas. Assim, o objetivo principal dos testes realizados foi avaliar a qualidade
das estruturas e dos parâmetros (probabilidades) das RBs aprendidas pelos algoritmos
EM estrutural e paramétrico, respectivamente, quando os dados disponı́veis são incompletos e gerados mediante mecanismos completamente aleatórios.
Os algoritmos EM para aprendizagem de RBs não estão restritos à aprendizagem a
partir de dados incompletos gerados aleatóriamente. Segundo Friedman [30], quando existe um padrão entre as variáveis faltosas e as variáveis observadas, essas relações podem ser
introduzidas diretamente no modelo e usar os algoritmos EM sem maiores dificuldades.
73
5.2. Descrição dos Dados Usados
dct-ufms
Porém, neste trabalho, a análise foi restrita a dados faltosos obtidos mediante mecanismos
completamente aleatórios, denominados MCAR 1 .
O tamanho da amostra de dados, assim como a quantidade de variáveis faltosas devem
ter um efeito na qualidade das redes aprendidas via estes algoritmos. Daı́ o interesse
em avaliar o desempenho dos algoritmos como uma função do tamanho da amostra e a
quantidade de valores de variáveis faltosos.
5.2
Descrição dos Dados Usados
O objetivo da implementação dos algoritmos EM é aprender estruturas e parâmetros quando bancos de dados incompletos são os únicos disponı́veis, o que é a situação mais comum
na realidade. Porém, para avaliar a qualidade dos parâmetros e estruturas aprendidas
neste trabalho, foram usados dados cujas estruturas e parâmetros já eram conhecidos na
literatura, pois dados de domı́nios reais seriam difı́ceis de serem analisados porque não
seria ainda conhecido os seus modelos probabilı́sticos reais. Por outro lado, a partir de
uma RB com estrutura e distribuição de probabilidade conjunta conhecida, pode ser facilmente avaliada a precisão dos resultados experimentais [11].
Os bancos de dados usados nos testes da implementação deste trabalho e suas RBs
usadas para avaliação são freqüentemente usadas pela comunidade acadêmica. As redes
consideradas foram: a RB ALARM [3] com uma complexidade moderada; a RB ASIA [47]
de uma complexidade menor; a rede denominada NETICA usada como exemplo no tutorial online da ferramenta Netica; e a rede ANGINA especificada no livro de Jensen [40].
A maior parte destes modelos estão disponı́veis gratuitamente na Internet e em diversos
formatos.
A partir dos modelos reais das RBs consideradas, foram geradas amostras aleatórias
com diferentes porcentagens de dados faltosos. A ferramenta Netica foi usada na geração
das amostras de dados incompletos de 100, 500, 1000, 2000, 5000 e 10000 instâncias; e
com porcentagens de valores de variáveis faltosos de 10% e 30%. Estas amostras foram
armazenadas em arquivos de texto e deste modo usadas para aprendizagem. A seguir é
dada uma descrição breve de cada uma das RBs usadas para realizar os testes.
A rede ALARM foi construı́da como um protótipo para modelar problemas potenciais
de anestesia que poderiam surgir na sala de operações. É uma rede relativamente grande,
que consiste de 37 variáveis e 46 arcos representando 8 problemas de diagnóstico, 16
sintomas (findings) e 13 variáveis intermédias que relacionam problemas de diagnóstico
aos sintomas. A Figura 5.1 ilustra a RB ALARM como representada na ferramenta Netica.
1
Missing Completely at random.
74
Low
Normal
High
25.1
68.7
6.24
75
True
False
1.0
99.0
Anaphylaxis
Low
Normal
High
True
False
25.1
66.8
8.14
30.7
39.6
29.7
Low
Normal
High
44.9
28.4
26.7
Blood Pressure
Low
Normal
High
24.8
71.1
4.04
5.45
94.6
History
Low
Normal
High
True
False
7.13
41.7
51.2
HRBP
5.00
95.0
Error Low Ouput
26.4
33.4
40.1
Cardiac Output
Low
Normal
High
Total Peripheral Resistan...
Low
Normal
High
True
False
StrokeVolume
Low
Normal
High
Pulmonary Capillary We...
23.4
69.0
7.60
5.00
95.0
Left Ventricular Failure
Left Ventricular End-diast...
20.0
80.0
Central Venous Pressure
True
False
Hypovolemia
20.0
80.0
Low
Normal
High
Low
Normal
High
4.96
89.3
5.75
28.2
64.3
7.48
Low
Normal
High
True
False
8.32
40.6
51.1
HRSat
10.0
90.0
Error Cauter
Low
Normal
High
SaO2
89.7
10.3
Shunt
1.0
99.0
Normal
High
True
False
PulmEmbolus
Low
Normal
High
Low
Normal
Low
Normal
High
Pulmonary Artery Pressure
1.0
99.0
FiO2
23.4
69.4
7.20
PVSat
6.92
68.2
24.9
ArtCO2
12.1
10.2
73.4
4.18
VentAlv
Low
Normal
High
Zero
Low
Normal
High
92.0
3.00
5.00
Intubation
Normal
Esophageal
OneSided
Figura 5.1: Rede bayesiana ALARM.
8.32
40.6
51.1
HREKG
4.68
41.7
53.6
Heart Rate
40.9
59.1
Catecholamine
Normal
High
True
False
Anest./Anelgesia Insuffici...
ALARM
Zero
Low
Normal
High
Zero
Low
Normal
High
12.1
7.43
66.2
14.2
ExpCO2
11.6
5.49
79.4
3.49
VentLung
4.00
96.0
KinkedTube
True
False
Zero
Low
Normal
High
Zero
Low
Normal
High
12.2
6.28
77.2
4.32
MinVol
6.71
2.79
87.7
2.79
VentTube
5.00
95.0
Disconnection
True
False
1.0
1.96
95.1
1.96
Zero
Low
Normal
High
7.97
5.53
77.3
9.18
Breathing Pressure
Zero
Low
Normal
High
VentMach
1.00
98.0
1.00
MinVolSet
Low
Normal
High
dct-ufms
dct-ufms
A RB ASIA, ilustrada na Figura 5.2, é um exemplo popular para introduzir conceitos de RBs; criada por Lauritzen e Spiegelhalter [47], é uma versão simplificada de um
problema de diagnóstico médico. Cada nó na rede corresponde a alguma condição do
paciente, os dois nós superiores indicam predisposições que influenciam a verossimilhança
de uma doença, as doenças aparecem na fila de baixo. Na parte inferior estão os sinais
das doenças.
Visit To Asia
Visit
1.0
No Visit 99.0
Smoking
Smoker
50.0
NonSmoker
50.0
Tuberculosis
Present 1.04
Absent 99.0
Lung Cancer
Present 5.50
Absent 94.5
Present
Absent
Tuberculosis or Cancer
True
6.48
False
93.5
XRay Result
Abnormal
11.0
Normal
89.0
Bronchitis
45.0
55.0
ASIA
Present
Absent
Dyspnea
43.6
56.4
Figura 5.2: Rede bayesiana ASIA.
A ferramenta Netica disponibiliza uma rede exemplo para testar aprendizagem de
parâmetros com dados incompletos e variáveis ocultas2 , ilustrada na Figura 5.3. Esta
rede não tem uma semântica especial, simplesmente modela as relações de independência
entre 4 variáveis.
Learning Latent
Variable Example
Copyright 2002 Norsys Software Corp.
A
true
false
20.0
80.0
true
false
29.6
70.4
R
true
false
67.2
32.8
S
T
true
false
22.0
78.0
Figura 5.3: Rede bayesiana NETICA.
Com estas RBs e as distribuições de probabilidade conjunta disponı́veis, é possı́vel
avaliar a qualidade das RBs induzidas pelos algoritmos EM durante aprendizagem. A
metodologia usada nos testes é descrita na seção seguinte.
2
Rede bayesiana disponı́vel em http://www.norsys.com/tutorials/netica/secD/Learn-Latent.dne.
76
5.3. Metodologia Experimental
5.3
dct-ufms
Metodologia Experimental
A metodologia experimental usada é simples, útil na avaliação de outros algoritmos de
aprendizagem [64, 54, 68]. Esta consiste em gerar instâncias de dados com porcentagens
de dados incompletos de 10% e 30 % e a partir deles usar os algoritmos EM para aprender
as RBs. Finalmente, é medida a qualidade das redes aprendidas, comparando-as com as
redes reais que geraram os dados.
Para medir a qualidade das distribuições aprendidas pelo algoritmo EM paramétrico,
usa-se medidas de distância entre distribuições de probabilidade conjunta. A medida
escolhida foi da entropia cruzada (ou Kullback-Leibler) [36] e é definida a seguir. Seja P
a distribuição conjunta da rede real e Q a distribuição conjunta representada pela rede
aprendida. Então a entropia cruzada H(P, Q) é dada por
H(P, Q) =
X
P (x) log
x
P (x)
Q(x)
(5.1)
Valores baixos de entropia cruzada correspondem a uma distribuição aprendida que
é próxima à RB real. Se as duas RBs têm uma estrutura comum, o cálculo da entropia
cruzada pode ser realizado da seguinte maneira:
H(P, Q) =
qi
ri
n X
X
X
P (Xi = k, P ai = j) log
i=1 j=1 k=1
P (Xi = k|P ai = j)
Q(Xi = k|P ai = j)
(5.2)
Para medir a qualidade da estrutura de RB aprendida é avaliada a quantidade de arcos faltosos e arcos a mais adicionados com relação à rede real. Esta diferença estrutural
reflete o grau com que as estruturas aprendidas têm capturado interações causais.
As condições de finalização dos algoritmos são diferentes. Para o caso do algoritmo
EM paramétrico (o logaritmo da verossimilhança avalia o progresso do algoritmo), a finalização acontece quando a mudança no logaritmo da verossimilhança relativa à iteração
anterior for menor que 10−4 . Para o caso do algoritmo EM Estrutural, a finalização
depende na mudança da pontuação entre estruturas: se a mudança relativa à iteração
anterior for menor a 10−4 , a busca por novas estruturas finaliza. Estes valores foram
obtidas durante o processo de experimentação.
Para cada algoritmo implementado e cada instância testada, foi medido o tempo de
execução. Os tempos obtidos não consideraram tempos gastos na leitura dos dados, nem
o tratamento de condensação feito neles.
77
5.4. Aspectos de Implementação e Resultados
5.4
dct-ufms
Aspectos de Implementação e Resultados
Nesta seção é descrita, inicialmente, a plataforma sobre a qual foi realizada a implementação e os testes, e aspectos importantes da ferramenta UnBBayes. Posteriormente são
detalhados cada um dos algoritmos EM implementados, sendo especificadas algumas estruturas importantes para o entendimento dos procedimentos. Após cada especificação
algorı́tmica, são apresentados os resultados experimentais e a análise correspondente.
5.4.1
Ambiente de Implementação
A implementação dos algoritmos de aprendizagem EM paramétrico e estrutural foi realizada usando as facilidades da API da ferramenta UnBBayes 3 da Universidade de Brasilia,
disponı́vel sob licença GNU. Esta ferramenta foi desenvolvida na linguagem Java e possui
as seguintes caracterı́sticas: inferência em RBs (algoritmo de árvore de junção); algoritmos para aprendizagem de RBs a partir de dados completos, baseado no paradigma de
busca e pontuação (B, K2 de Cooper e Herskovits [18]) e no paradigma de independência
condicional (algoritmo CBLA, CBLB de Cheng [11]). Para o caso dos algoritmos de busca e pontuação, é possı́vel escolher a métrica para a avaliação das estruturas candidatas
(MDL, GH, GHS).
O algoritmo de aprendizagem de parâmetros disponı́vel nesta ferramenta segue as diretrizes da Seção 4.2.1. Aprendizagem das RBs não é um processo totalmente automático,
sendo necessário, para o caso dos algoritmos K2 e CBLA, fornecer uma ordenação coerente das variáveis dada por um especialista. No caso do algoritmo CBLB, aprende-se a
totalidade da RB só a partir de dados, sendo em alguns casos necessário que o especialista
acrescente alguns arcos que o algoritmo não conseguiu identificar.
A configuração da máquina utilizada para desenvolvimento e testes foi: Intel Pentium
4 de 1.7 GHz com 256 MB de memória RAM, 128 KB de memória cache e sistema
operacional Windows 98. A seguir é dada uma descrição resumida das principais classes
e pacotes da ferramenta UnBBayes.
Descrição dos Pacotes Principais da Ferramenta UnBBayes
A API da ferramenta UnBBayes está organizada em pacotes4 . Cada pacote contém um
conjunto de classes com funcionalidades diferentes. No inicio do trabalho, foi realizado
um estudo e especificação das classes, pacotes e as estruturas de dados da API. Então,
foi realizado o planejamento das modificações e adições que deviam ser feitas nas classes,
para contornar os objetivos de implementação, evitando na medida do possı́vel, conflitos
com a funcionalidade corrente. Algumas poucas modificações foram realizadas nas classes
3
4
Disponı́vel em http://unbbayes.sourceforge.net/.
Tradução de package, usado em Java para organizar um conjunto de classes.
78
dct-ufms
interface humano-computador (pacote gui), a fim de possibilitar a ligação entre os algoritmos desenvolvidos com a ferramenta. A maior parte do desenvolvimento foi realizado
nos pacotes aprendizagem e de estruturas de dados denominado prs — o algoritmo de
inferência faz parte deste último pacote.
O diagrama UML 5 da Figura 5.4 ilustra os principais pacotes desta ferramenta e as
relações de dependências entre eles. Uma descrição resumida de cada pacote é dada a
seguir.
util
prs
datamining
aprendizagem
monteCarlo
io
controller
gui
Figura 5.4: Pacotes principais da ferramenta UnBBayes.
• Pacote util: neste pacote estão definidas estruturas de dados úteis para armazenamento e operações sobre as probabilidades.
• Pacote io: conjunto de classes para leitura e armazenamento de redes bayesianas
em diversos formatos padrões.
• Pacote gui: conjunto de classes que permitem o manuseio e visualização das redes
bayesianas.
5
Unified Modeling Language
79
dct-ufms
• Pacote controller: conjunto de classes que permitem a ligação entre a interface e os
algoritmos que fazem inferência, aprendizagem e as outras funcionalidades.
• Pacote datamining: conjunto de classes com vários classificadores disponı́veis tais
como redes neurais, árvores de decisão, e classificadores bayesianos.
• Pacote monteCarlo: conjunto de classes para gerar amostras aleatórias de redes
bayesianas dadas como parâmetro.
• Pacote prs: classes principais que definem a estrutura de uma rede bayesiana, tais
como Node e Edge. Também estão definidas classes para a realização de inferência
em redes bayesianas.
• Pacote aprendizagem: aqui estão definidas as classes que permitem aprendizagem
de redes bayesianas a partir de dados. Neste pacote foram incluı́dos os algoritmos
EM implementados. Classes para amostragem Gibbs e aprendizagem incremental
estão sendo desenvolvidos atualmente neste pacote.
O pacote aprendizagem depende principalmente de: a)prs, pois precisa de classes
para criar redes bayesianas, e dos algoritmos de inferência; b)io, pois precisa ler arquivos
contendo dados para aprendizagem ; c)controller, pois precisa se comunicar com o resto
da aplicação; d) util, para uso de algumas estruturas de dados.
Descrição das Classes Principais da Implementação
A Figura 5.5 ilustra algumas das classes principais da implementação. Três novas classes
foram adicionadas ao pacote aprendizagem: EMToolkit, EMParametric e EMStruct.
Na figura, pode-se observar que a classe abstrata LearningToolkit, define a funcionalidade geral de todos os algoritmos de aprendizagem. A classe PonctuactionToolkit define a
funcionalidade dos algoritmos baseados no paradigma de busca e pontuação. Neste caso
os algoritmos K2 e B são representados respectivamente pelas classes K2 e B. A classe abstrata CBLToolkit define o comportamento das classes baseadas no paradigma de
análise de independência condicional. As classes derivadas CBLA e CBLB implementam
a funcionalidade dos algoritmos do mesmo nome. Todas estas classes, representando os
algoritmos de cada paradigma, estão agregadas em uma classe AlgorithmController que
determina a classe e/ou a métrica escolhida pelo usuário. Esta última classe e as classes
que implementam os algoritmos EM paramétrico e estrutural estão agregadas na classe
ConstructionController. Esta classe faz a ligação com as classes dos pacotes controller e
gui, o que permite a comunicação com o resto da aplicação.
Em geral, o arquivo que o usuário da ferramenta fornece para aprendizagem é organizado em linhas e colunas. O arquivo deve conter um número de colunas igual ao número
de variáveis do domı́nio. Cada linha representa um caso, ou seja, os estados observados
para cada variável. Na primeira linha, usualmente, estão indicados os nomes das variáveis.
80
dct-ufms
«metaclass»
Node
LearningToolkit
EMToolkit
ProbabilisticNode
PonctuationToolkit
CBLToolkit
1
*
«implementation class»
EMParametric
K2Toolkit
BToolkit
TVariavel
*
CBLB
K2
CBLA
B
EMStruct
*
1
AlgorithmController
*
1
ConstructionController
1
Figura 5.5: Classes principais do pacote aprendizagem.
No momento da leitura deste arquivo é instanciado um objeto da classe TVariavel6 para
cada variável presente nos dados. Nesse objeto são armazenados informações coletadas
para uma variável: nome, os possı́veis estados, posição no banco de dados. Os dados
lidos são representados em uma matriz de bytes (denominada dataBase e membro da
6
Classe derivada de ProbabilisticNode, do pacote prs e por conveniência colocada na Figura 5.5.
81
dct-ufms
classe ConstructionController), de dimensões m × n, sendo m o número de casos para n
variáveis. Os estados observados são armazenados como números, por exemplo, se uma
variável possui estados “sim” e “não”, esses dados serão armazenados como 0 e 1. Os
estados das variáveis que não foram observados são armazenados com o valor -1. A Tabela
5.1 apresenta um exemplo de leitura e armazenamento dos dados.
Tabela 5.1: Amostra de dados lida e armazenada para as variáveis A, B, C.
A
B
C
0 −1 0
sim
∗
f also
0 0 1
sim sim verdadeiro =⇒
1 1 0
nao nao
f also
0 1 1
sim nao verdadeiro
É comum os arquivos de dados apresentarem instâncias repetidas. A solução adotada,
para melhorar a eficiência dos algoritmos de aprendizagem, foi condensar essas instâncias
e armazenar a freqüência com que aparecem nos dados originais. Esse vetor de freqüências
armazenado, será útil para determinar as estatı́sticas suficientes das variáveis da RB.
Descrição das Classes para EM
A Figura 5.6 ilustra maiores detalhes nas classes que foram implementadas para os algoritmos EM paramétrico e EM estrutural. Também estão especificados alguns atributos
e métodos que foram adicionados nas classes originais. Por exemplo, dentro da classe
LearningToolkit foram adicionados atributos e métodos para o cálculo das freqüências esperadas. Na classe ConstructionController foi adicionado um método para condensar os
dados lidos.
Para os algoritmos EM é necessário realizar inferência probabilı́stica. A classe ProbabilisticNetwork do pacote prs, através dos dois métodos apresentados na Figura 5.6,
permite a propagação de evidências. Por isso que está agregada na classe EMParametric.
A classe EMStruct é derivada de EMParametric pois utiliza parte do comportamento dessa classe, diferenciando-se na busca de estruturas. Os atributos e métodos apresentados
nestas duas classes serão melhor compreendidos quando especificados os algoritmos EM
implementados nas seções posteriores.
5.4.2
Algoritmo EM Paramétrico
O algoritmo EM paramétrico é útil em situações em que o especialista tenha uma estrutura de RB de um domı́nio particular definido e queira, a partir de dados incompletos
(talvez os únicos disponı́veis), aprender os parâmetros — as distribuições de probabilidade condicional para essa estrutura definida. A Figura 5.7 apresenta o algoritmo principal
82
dct-ufms
Network
LearningToolkit
-vector_f : float
TVariavel
#getFloatFrequencies() : float
*
ProbabilisticNetwork
EMToolkit
+compile()
+updateProbabilities()
#gaussLaguerre() : double
#initParameters()
#simulate()
#randNumbers() : int
#gammaFunction() : double
+compareNets()
+distanceDistributions()
+distanceKL()
#dfsCycle()
#dfsConnectivity()
+compareStructs()
#lnGamma()
#structAnalysis()
1
EMParametric
-missingCases : float
-missingPositions : int
-distributions : float
-expectedCounts : float
-treshold : float
+initialize()
#addHiddenVariables()
#identifyMissingCases()
#addFindings()
#saveDistributions()
#expectationStep()
#maximizationStep()
#expectation()
#Qt()
+parametricEM()
EMStruct
-score : float
-scores : float
-candidatsParents
-metric
#initStructure()
#precalcParents()
#chooseBestCandidat()
#calculateScore()
#expectMDL()
#expectBDe()
#initMetric()
#updateStruct()
#simulatedAnnealing()
#greedyHillClimbing()
#addEdgeTemp()
#addEdgeHillClimbing()
#reverseTemp()
#reverseHillClimbing()
#removeTemp()
#removeHillClimbing()
#undoRemove()
+iteratedHillClimbing()
+bayesianStructuralEM()
*
1
ConstructionController
-dataBase : unsigned int
+compactDataBase()
Figura 5.6: Especificação das classes dos algoritmos EM.
que realiza a chamada do algoritmo EM paramétrico.
Nesta seção e na subseqüente considera-se a estrutura de uma rede bayesiana S constituı́da por um conjunto de vértices V (as variáveis ou nós) e um conjunto de arcos dirigidos,
A, que ligam as variáveis. O grafo resultante é acı́clico (GAO). Uma estrutura fica completamente definida quando para toda variável Vi ∈ V é conhecida o conjunto de variáveis
pais P ai . D representa o banco de dados incompleto fornecido pelo usuário e usado para
83
dct-ufms
Inicia Algoritmo EM(D, S, ε)
. Entrada : D amostra de dados disponı́vel
. Entrada : S = (V, A) estrutura da RB, GAO
. Entrada : ε limiar
. Saı́da : RB= hS, Θi, parâmetros definidos
. Dados : Θ, parâmetros da RB
. Dados : f altosos, casos com valores faltosos
1 Inı́cio
2
V ← Variáveis em D ∪ V
3
Θ ← Valores aleatórios
4
f altosos ← IdentificaValoresFaltosos(D)
5
Θ ← algoritmoEM(D, S, Θ, f altosos, ε)
6
Retorna S, Θ
7 Fim
Figura 5.7: Rotina principal do algoritmo EM paramétrico.
aprendizagem de parâmetros e/ou estruturas. Considera-se os dados condensados, ou seja
não existem duas ou mais linhas contendo instâncias idênticas; a freqüência de cada linha
condensada está armazenada num vetor. Θ, representa os parâmetros estimados para
uma estrutura definida. ε representa o limiar que determina a convergência do algoritmo
considerado.
A Figura 5.7 apresenta a rotina principal do algoritmo EM paramétrico o qual recebe
como parâmetros de entrada: os dados D incompletos, a estrutura inicial S e o limiar
ε. Como resultado retorna uma rede bayesiana com parâmetros que foram estimados a
partir dos dados incompletos. Particularmente, na linha 2, é definido o conjunto total de
variáveis de S, V , adicionando-se novas variáveis encontradas em D (estas são variáveis
ocultas). Na linha 3, o conjunto de parâmetros, Θ, que precisam ser estimados, são iniciados com valores aleatórios. Na linha 4, são identificadas as instâncias de dados faltosas
— evitando, deste modo, demora em acessos subseqüentes. Com as variáveis faltosas
identificadas e os parâmetros iniciais, na linha 5, chama-se o algoritmo EM paramétrico
que realiza a estimativa final para os parâmetros, retornados na linha 6.
A Figura 5.8 apresenta as especificações do algoritmo EM paramétrico. Se os dados
fossem completos, a distribuição de probabilidades de cada variável seria obtida calculando estatı́sticas suficientes para os dados. Porém, quando os dados são incompletos o
algoritmo EM, no Passo E, completa os valores faltosos e, com os dados completados,
realiza estimativas de máxima verossimilhança para as probabilidades, este último passo
denomina-se maximização (Passo M). Deste modo, são calculadas novas probabilidades
que substituirão as probabilidades correntes. Este processo é iterativo.
A funcionalidade descrita anteriormente é especificada na Figura 5.8. Enquanto a di-
84
dct-ufms
AlgoritmoEM(D, S, Θ, f altosos, ε)
. Entrada : Θ parâmetros da RB
. Entrada : f altosos ⊂ D variáveis com valores faltosos
. Saı́da : RB= hS, Θi, parâmetros definidos
. Dados : e, cálculo da verossimilhança atual
. Dados : eAnt, cálculo da verossimilhança anterior
. Dados : ∆e, diferença entre verossimilhanças anterior e atual
. Dados : distribuicoes, vetor de distribuições armazenadas
. Dados : f reqEsperadas, conjunto de freqüências esperadas
1 Inı́cio
2
e←0
3
eAnt ← ∞
4
∆e ← eAnt − e
5
enquanto ∆e > ε faça
6
eAnt ← e
7
distribuicoes ← SalvaDistribuições(D, S, Θ, f altosos)
8
f reqEsperadas ← passoExpectation(D, S, Θ, f altosos, distribuicoes)
9
e ← Maximization(S, Θ, f reqEsperadas)
10
∆e ← e − eAnt
11
Θ ← NormalizaProbabilidades(S, Θ)
12
fim enquanto
13
Retorna S, Θ
14 Fim
Figura 5.8: Algoritmo EM paramétrico.
ferença entre a verossimilhança dos parâmetros estimados com os parâmetros anteriores
seja maior que o limiar (linha 5), o processo, iterativamente, realiza o completamento dos
dados (Passo E) (linha 8), o cálculo das novas distribuições de probabilidade e a verossimilhança (Passo M) (linha 9). Além disso, realiza uma normalização dos parâmetros
calculados (linha 11).
Particularmente, o Passo E consiste em calcular estatı́sticas esperadas para cada variável Vi ∈ V e os pais de Vi , P ai , a partir dos dados D. Essas estatı́sticas esperadas
são contagens das freqüências de cada estado de Vi e P ai em D, também denotadas Nijk .
Quando os estados de uma variável Vi e/ou P ai não aparecem registrados em alguma
linha Dl ∈ D (valor faltoso), realiza-se inferência bayesiana (inserindo a evidência observada em Dl ) para estimar a distribuição de probabilidade marginal de Vi e/ou P ai. Se
Dl aparece uma vez em D, a freqüência de cada estado de Vi é a probabilidade marginal
obtida após a inferência. Se Dl tem uma freqüência maior que 1, a freqüência de cada
estado de Vi é obtida da multiplicação da probabilidade marginal pela freqüência de Dl .
85
dct-ufms
Por exemplo, se Dl for h−1, 0, 0, 1i com uma freqüência de 2 e supondo que Vi (a coluna
com valor -1) possua dois estados, a partir dele são gerados dois novos casos h0, 0, 0, 1i e
h1, 0, 0, 1i com probabilidades p e 1 − p, e com freqüências denominadas esperadas 2(p) e
2(1 − p).
Se este procedimento fosse realizado para cada um dos estados de Vi , P ai ∈ V , seriam necessárias muitas chamadas ao processo de inferência, a maioria das vezes redundantes. Uma outra alternativa é realizar o cálculo da inferência probabilı́stica para toda Dl ∈ D que tenha valores faltosos. Na Figura 5.8, na linha 7, o procedimento
SALVADISTRIBUIÇÕES percorre cada linha Dl ∈ D, e se houver valores faltosos, realiza inferência e armazena em uma tabela de dispersão (tendo como chaves as posições
faltosas) as distribuições de probabilidade marginal das variáveis que apresentam valores
faltosos. Essas distribuições são então passadas na linha 8 para o cálculo das estatı́sticas
esperadas, sendo o acesso a cada distribuição de probabilidade dependente da estrutura
usada para armazenamento, neste caso a tabela de dispersão.
Uma alternativa considerada inicialmente consistia em percorrer cada uma das linhas
em D, realizar inferência, gerar novos casos de acordo com a quantidade de estados das variáveis faltosas em cada linha e calcular a freqüência esperada de cada caso. Esta solução
foi descartada devido a que a geração de novos casos e, especialmente armazenamento deles para bancos de dados grandes e RBs de tamanho médio, requeria uso de uma grande
quantidade de memória.
Apesar do procedimento na linha 7 ter sido usado por razões de otimização (o processo
de inferência é chamado uma única vez em cada iteração para cada linha ou caso com
variáveis faltosas), resultou tendo o maior custo quanto a tempo de processamento. Este
custo foi medido, e é apresentado em valores percentuais na Figura 5.9. A RB testada
foi ALARM, com conjunto de dados de 10000 instâncias e com 10% de dados faltosos.
Os resultados ilustrados nessa figura mostram que o processo de inferência leva quase a
totalidade do tempo de execução, com uma porcentagem de 90%. O algoritmo EM (os
dois passos) ocupa 7% do tempo de processamento, o tempo restante é gasto em outros
processos, como armazenamento em estruturas auxiliares.
Acredita-se que uma maneira de melhorar este desempenho seria utilizar outros métodos
para completar os dados. Uma reformulação do algoritmo de inferência talvez seja necessária. Métodos aproximados são sugeridos na literatura [33, 21], porém, resultados
sobre o compromisso entre rapidez e precisão não são indicados.
Na Figura 5.10 é apresentado o algoritmo passoExpectation no qual estão descritos
maiores detalhes do cálculo das estatı́sticas esperadas. Neste caso, para cada uma das
variáveis em V (linha 3) são calculadas e armazenadas freqüências esperadas através do
método Expectation (linha 5). Este algoritmo retorna as freqüências esperadas para todas
as variáveis de V (linha 7).
86
EM
7%
dct-ufms
Outros
3%
Inferência
EM
Inferência
90%
Outros
Figura 5.9: Porcentagens de tempo de processamento, rede bayesiana ALARM.
A estrutura armazenada (f reqEsperadas) permitirá o cálculo das distribuições de
probabilidade para cada variável, assim como o cálculo da verossimilhança.
passoExpectation(D, S, Θ, f altosos, distribuicoes)
. Entrada : distribuicoes, vetor de distribuições armazenadas
. Saı́da : f reqEsperadas, conjunto de freqüências esperadas
1 Inı́cio
2
f reqEsperadas ← ∅
3
para i ← 0 até |V | faça
4
Vi ← i − ésima variável de V
5
f reqEsperadas ← f reqEsperadas∪
Expectation(Vi , D, S, Θ, f altosos, distribuicoes)
6
fim para
7
Retorna f reqEsperadas
8 Fim
Figura 5.10: Passo Expectation dentro do algoritmo EM.
O cálculo das freqüências esperadas para cada variável é apresentado na Figura 5.11.
Para a variável Vi é calculada uma matriz com ri × qi valores de freqüências — o número
de estados dessa variável pela quantidade total dos estados dos pais P ai .
Especificamente, neste procedimento são inseridos valores em uma estrutura denominada f reqEsperadasi , a qual armazena as freqüências esperadas para a familia de
variáveis P (Vi |P ai ) (a variável Vi e seus pais). Para realizar esta tarefa deve-se percorrer
os dados D, procurando instanciações dos estados de Vi , P ai . Da linha 4 até 21, é realizado o percurso de cada linha de D, dl . Para cada dl , após a leitura das variáveis faltosas,
87
dct-ufms
Expectation(Vi , D, S, Θ, f altosos, distribuicoes)
. Entrada : Vi ∈ V
. Entrada : distribuicoes, vetor distribuições armazenadas
. Saı́da : f reqEsperadasi , conjunto de freqüências esperadas para variável Vi
. Dados : P ai , pais de Vi
. Dados : dl , l-ésimo caso de D
1 Inı́cio
2
f reqEsperadasi ← ∅
3
P ai ← Pais(Vi , S)
4
para dl ← 0 até |D| faça
5
qi ← EstadosPais(f altosos(dl )(P ai ), S)
. f altosos(dl )(P ai ) retorna posições dos pais com valores faltosos em dl
. qi é o número de estados das variáveis pais com valores faltosos em dl
6
probM arginais ← distribuicoes(dl )
7
para j ← 0 até qi faça
8
f requencia ← Frequencia(D, dl )
9
para i ← 0 até |P ai | faça
10
pai ← D(dl )(i)
se pai =? então
11
. Se estado é faltoso
12
pai ← geraEstado(j)
. Determina o próximo estado para pai
13
Θpai ← probM arginais(pai )
14
f requencia ← f requencia ∗ Θpai
15
fim se
16
pospai ← Posicao(pai )
17
fim para
18
posvi ← D(dl )(vi )
19
f reqEsperadasi (posvi )(pospai ) ← f requencia
20
fim para
21
fim para
22
Retorna f reqEsperadasi
23 Fim
Figura 5.11: Estimativa dos parâmetros (Expectation).
é calculado o número de estados que precisam ser gerados para essas variáveis faltosas,
qi (linha 5), se não houver nenhuma variável faltosa em dl este processo retornará qi = 1.
Sucessivamente são lidas as distribuições de probabilidade para os estados de essas variáveis faltosas em dl (linha 6). Essas distribuições e posições das variáveis faltosas foram
pre-calculadas em passos anteriores.
88
dct-ufms
Tomando como base a freqüência de dl , (linha 8), é calculada a freqüência esperada
para cada estado das variáveis faltosas em dl (linhas 7 a 20), como é explicado a seguir.
De dl é lido cada pai de Vi (linha 9), se algum pai é faltoso (linha 11), é gerado o estado possı́vel para esse pai (linha 12) — referente a qi , ou seja, o número de estados totais
das variáveis faltosas. Com esse novo estado atribuı́do a pai , calcula-se sua freqüência
esperada. Para isto é lida a distribuição de probabilidade marginal para pai em dl (linha
13), calculada e armazenada em processos anteriores, e multiplica-se a freqüência de dl
pela distribuição de probabilidades de pai , o valor de freqüência dl é modificado de acordo
com a quantidade de valores faltosos totais, qi .
Posteriormente, determina-se a posição do estado pai na estrutura f reqEsperadasi
(linha 16). Finalmente, é lido o estado de Vi em dl (linha 18) e armazenado o valor
da freqüência esperada calculada (linha 19). Se o valor do estado Vi não for observado em dl realiza-se um procedimento parecido com as linhas 7 a 19. Porém, neste caso o
procedimento seria repetido ri vezes (linha 7), ou seja o número de estados possı́veis de Vi .
O algoritmo de maximização é um processo de cálculo da máxima verossimilhança a
partir das freqüências esperadas obtidas dos dados completados. A Figura 5.12 apresenta
este processo para todas as variáveis V .
Maximization(S, Θ, f reqEsperadas)
. Entrada : f reqEsperadas, conjunto de freqüências esperadas
. Saı́da : e erro acumulado
1 Inı́cio
2
e←0
3
para Vi ← 0 até |V | faça
4
Vi ← i − ésima variável de V
5
f reqEsperadasi ← i − ésimo estado de f reqEsperadas
6
e ← e + Qt(Vi , S, Θ, f reqEsperadasi )
7
fim para
8
Retorna e
9 Fim
Figura 5.12: Atualização de parâmetros e cálculo da verossimilhança (Maximization).
Neste caso são calculadas as novas distribuições de probabilidade conjunta para cada
uma das variáveis (linhas 3 a 7), baseadas nas novas freqüências esperadas e que substituirão as distribuições de probabilidade anteriores. Também é realizado o cálculo do
logaritmo da verossimilhança para determinar a convergência do processo (linha 6).
89
dct-ufms
O procedimento Qt apresentado na Figura 5.13, detalha o processo de maximização
feito sobre cada variável Vi .
Qt(Vi , S, Θ, f reqEsperadasi )
. Entrada : f reqEsperadasi , conjunto de freqüências esperadas para Vi
. Saı́da : veross logaritmo da verossimilhança
. Dados : P ai ∈ V pais de Vi
. Dados : qi número de estados dos pais de Vi
. Dados : ri número de estados de Vi
. Dados : j, k, nij, nijk, probijk variáveis auxiliares
1 Inı́cio
2
ri ← |Vi |
3
4
qi ← EstadosPais(P ai , S)
5
veross ← 0
6
7
nij ← 0
8
para k ← 0 até ri faça
9
nij ← nij + f reqEsperadasi (k)(j)
10
fim para
11
12
nijk ← f reqEsperadasi (k)(j)
13
probijk ← (1 + nijk)/(ri + nij)
14
veross ← veross + log(probijk)(nijk + 1)
15
Θijk ← probijk
. Atualiza as probabilidades
16
fim para
17
fim para
18
Retorna veross
19 Fim
Figura 5.13: Algoritmo Qt para o cálculo das novas probabilidades para Vi .
Com as freqüências esperadas dadas para uma variável, no procedimento Qt percorrese cada estado da variável e os estados dos pais, calculando-se as probabilidades (linhas 6
a 17). Na linha 14, é acumulado o valor do logaritmo da verossimilhança de cada estado
de acordo com a Equação 4.10. Finalmente, a nova probabilidade para esse estado é
estabelecida (linha 15) e a verossimilhança acumulada é retornada (linha 18).
90
dct-ufms
Análise de Resultados
A seguir são especificados os testes e resultados da aplicação do algoritmo EM paramétrico
aos conjuntos de dados considerados.
A primeira rede avaliada foi a NETICA. Foram medidos o tempo de processamento
e a distância entre os parâmetros aprendidos e os parâmetros da RB real. A figura 5.14
a) , ilustra os tempos obtidos para esta rede pequena (somente 4 variáveis), considerando
instâncias de 100 a 10000 dados. Observa-se que não há uma diferença significativa para
dados com porcentagens de 10% e 30% de valores faltosos. O tempo é maior conforme
as instâncias de dados são maiores, sendo o máximo atingido de 10 milisegundos para
dados com 10000 instâncias. Para instâncias pequenas de 100 e 500 dados foi necessário
executar até 100 vezes o algoritmo para obter tempos significativos.
Com relação à distância entre os parâmetros aprendidos e os reais, a Figura 5.14 b)
mostra que quanto maior a quantidade de dados disponı́veis para aprendizagem e menor
porcentagem de dados faltosos, a distribuição aprendida é mais próxima da real. Cabe
salientar que, ainda com 30% de dados faltosos, o valor de entropia obtida é baixo e,
portanto, a distribuição de probabilidade fundamental consegue ser recuperada.
A rede ASIA foi a próxima RB a ser analisada. A Figuras 5.15 a) e 5.15b) ilustram
seu desempenho quanto a tempo e qualidade da aprendizagem, respectivamente. A sua
complexidade é maior que a RB NETICA, com 8 nós ou variáveis e 8 arcos. Neste caso,
a relação entre o tempo gasto na aprendizagem e a quantidade de dados faltosos é mais
visı́vel, sendo maior para instâncias com 30% de dados faltosos. Esse resultado é devido
à necessidade de estimar uma quantidade de valores maior, sendo que a convergência
também é mais demorada. Para uma instância de 10000 casos e 10% de dados faltosos, o
número de iterações necessárias até convergir foi de 10, sendo 15 para o caso de 30%.
Com relação à medida de distância entre distribuições de probabilidade conjunta, os
resultados foram irregulares, obtendo-se distâncias mais próximas das reais em instâncias
de tamanho médio (1000 dados). Portanto, nenhuma conclusão pode ser obtida destes
resultados, a não ser que as distâncias, em geral, foram maiores devido à maior complexidade desta rede.
A última RB considerada é ALARM. A Figura 5.16 ilustra os resultados obtidos com
relação ao tempo e qualidade. Nesta RB os tempos de processamento foram significativamente elevados. A quantidade de variáveis, 37, influenciou nos resultados, especialmente
para instâncias a partir de 1000 dados. A relação entre porcentagens de dados faltosos
e tempo é notória, sendo quase 20% maior, conforme a quantidade de dados faltosos se
incrementa. Como indicado anteriormente, o processo de inferência é o gargalo deste procedimento, e com esta rede pode-se comprovar esse desempenho. Para uma amostra de
10000 dados, em cada iteração é realizada a propagação de evidências sobre 37 variáveis
91
dct-ufms
a) Tempo NETICA − EM paramétrico
Tempo (milisegundos)
12
10% valores faltosos
11
10
9
8
7
6
0
2000
4000
6000
Número de casos
8000
10000
Distância entre distribuições
b) Distância NETICA − EM paramétrico
0.2
0.18
0.16
0.14
0.12
0.1
0.08
0.06
0.04
0.02
0
0
2000
4000
6000
Número de casos
8000
10000
Figura 5.14: Tempo e distância NETICA - algoritmo EM paramétrico.
9000 vezes, aproximadamente. Mesmo assim, a convergência deste algoritmo foi relativamente rápida com 14 iterações.
92
dct-ufms
a) Tempo ASIA − EM paramétrico
4000
3500
3000
2500
2000
1500
1000
500
0
0
2000
4000
6000
Número de casos
8000
10000
b) Distância ASIA − EM paramétrico
2
1.8
1.6
1.4
1.2
1
0.8
0.6
0.4
0
2000
4000
6000
Número de casos
8000
10000
Figura 5.15: Tempo e distância ASIA - algoritmo EM Paramétrico
A medida de entropia devolveu resultados esperados, mostrando que a medida que a
quantidade de dados disponı́veis é maior, a distância dos parâmetros aprendidos é mais
próxima dos parâmetros reais. Os valores de distância obtidos foram grandes, indicando a
priori que as distribuições aprendidas não são as mais adequadas. Este fato foi analisado
com maior detalhe, observando-se que valores de distância grandes foram obtidos em
distribuições de probabilidade de variáveis com maior conectividade, ou seja, com maior
número de pais, sendo seu número de estados maior do que 2. É possı́vel que nos bancos
de dados usados para teste e gerados aleatóriamente, os valores destas combinações não
sejam suficientemente representativos. Conseqüentemente, com uma maior quantidade de
93
dct-ufms
a) Tempo ALARME − EM paramétrico
350000
300000
250000
200000
150000
100000
50000
0
0
2000
4000
6000
Número de casos
8000
10000
b) Distância ALARME − EM paramétrico
35
30
25
20
15
10
5
0
2000
4000
6000
Número de casos
8000
10000
Figura 5.16: Tempo e distância ALARM - algoritmo EM paramétrico.
dados disponı́veis, a distância tende a diminuir. Outra possibilidade da ocorrência destes
resultados é a convergência do algoritmo a um máximo local.
94
5.4.3
dct-ufms
Algoritmo EM Estrutural
O algoritmo EM estrutural de Friedman é útil para aprender estrutura e parâmetros a
partir de dados incompletos. Este algoritmo, em cada iteração e com uma estrutura dada
inicialmente, completa os dados faltosos mediante uma aproximação maximum a posteriori — o algoritmo EM paramétrico. A partir desses dados completados, realiza uma
busca por estruturas, avaliando cada estrutura candidata com métricas aproximadas. Essa estrutura encontrada será utilizada na próxima iteração do algoritmo. Após várias
iterações, espera-se que o algoritmo progrida à melhor estrutura para os dados originais.
A Figura 5.17 ilustra o processo detalhado do algoritmo EM estrutural de Friedman.
No passo A(0) com dados incompletos (os reais) e uma estrutura aleatória, aplica-se
o algoritmo EM paramétrico para completá-los e calcula-se uma primeira distribuição
de probabilidade para a estrutura inicial (passo B). Com este completamento de dados,
inicia-se o algoritmo de busca por uma estrutura ótima seguindo o paradigma de busca e
pontuação, que gera novas estruturas de maneira heurı́stica (recombina variáveis) e estas,
por sua vez, determinam freqüencias diferentes (Passos C e D). Com C e D escolhe-se a
estrutura que tenha a melhor pontuação conforme as métricas descritas a seguir, nesta
mesma seção.
No passo A(1) (a segunda iteração do algoritmo), a partir da estrutura ótima encontrada na iteração anterior, calcula-se as tabelas de probabilidade usando os dados
completados no passo B. Os dados incompletos (os reais) são novamente usados em A(1)
para realizar uma busca por outra estrutura ótima, pois deseja-se encontrar uma estrutura
ótima para os dados incompletos, que são os dados reais de um certo domı́nio.
Um resumo de como progridem as iterações do algoritmo de Friedman é ilustrado
na Figura 5.18. Em cada iteração, de A(n-1) para A(n), aplica-se o algoritmo EM paramétrico (que completa dados) e um algoritmo de busca e pontuação, terminando-a com
uma estrutura ótima intermediária e seus parâmetros correspondentes calculados usando
este último completamento.
A estrutura ótima final é obtida quando convergir para zero as distâncias entre as
pontuações das estruturas ótimas dos passos A(n) e A(n + 1), ∀n ∈ N .
Cabe observar que, para dados completos, a aprendizagem se realiza só do passo B até
o passo A(1), isto é, só ocorre uma iteração do algoritmo de Friedman. Entretanto, não
é aconselhável usar esta implementação para dados completos, porque ela vai tentar usar
o EM paramétrico para completar o que já está completo, incorrendo em maior tempo de
processamento.
A seguir são descritos os algoritmos respectivos para as idéias apresentadas anteriormente. Por ser a busca por estruturas um algoritmo de natureza heurı́stica é comum
95
Estrutura Aleatória
X1
X2
Probabilidades
X3
X1
X2
dct-ufms
X1
X2
X3
Contas Esperadas
N(X 1)
N(X 2)
N(X 3)
N(H,X 1,X 2,X 3)
N(Y 1,H)
N(Y 2,H)
N(Y 3,H)
X3
H
H
Y1
H
Y3
Y2
+
Y1
Y1
X1
Y3
Y2
+
EM
Paramétrico
Dados
Incompletos
Y1
Estrutura Ótima
Y1
N(X 2,X 1)
N(H,X 1,X 3)
N(Y 1,X 2)
N(Y 2,Y 1)
Y2
.
.
.
Y3
C
X2
X3
+H
Y2
X3
.
.
.
B
X1
X2
Y3
H
Busca e
Pontuação
Dados
Completados
A(0)
Y2
D
Probabilidades
+
Dados
Incompletos
…….
Y3
A(1)
Figura 5.17: Detalhe do algoritmo EM estrutural.
Estrutura Final
Estrutura Aleatória
EM
Paramétrico
EM
Paramétrico
+
…….
+
Busca e
Pontuação
Busca e
Pontuação
CONVERGENCIA
Dados
Incompletos
A(0)
Dados
Incompletos
Dados
Incompletos
A(1)
A(n-1)
Figura 5.18: Algoritmo EM estrutural resumido.
96
Dados
Incompletos
A(n)
dct-ufms
encontrar máximos locais. Para superar esta dificuldade, executa-se o algoritmo desde
diferentes probabilidades e estruturas iniciais, escolhendo-se a estrutura com a melhor
pontuação. Este algoritmo é denominado às vezes Iterated Hill Climbing [54, 68] e é apresentado na Figura 5.19.
IteratedHillClimbing(D, S, Θ, ε, iteracoes)
. Entrada : S = (V, A) estrutura da RB, GAO, neste caso vazia
. Entrada : iteracoes número de iterações
. Saı́da : RB= hS, Θi
. Dados : pontuacao, pontuação de uma estrutura S
. Dados : maxP ontuacao, máxima pontuação
. Dados : s, conjunto de estruturas
. Dados : θ, conjunto de parâmetros para s
1 Inı́cio
2
maxP ontuacao ← −∞
3
para i ← 0 até iteracoes faça
4
S ← estrutura aleatória
5
pontuacao ← AlgoritmoSEM(D, S, Θ, ε)
6
s←s∪S
7
θ ←θ∪Θ
8
maxP ontuacao ← max(maxP ontuacao, pontuacao)
9
fim para
10
Retorna max S ⊂ s, max Θ ⊂ θ
11 Fim
Figura 5.19: Algoritmo Iterated Hill Climbing.
Em cada iteração, escolhe-se uma estrutura e parâmetros iniciais aleatórios (linha 4).
Neste caso, a escolha da estrutura inicial foi baseada no trabalho de Friedman [29], que
consiste em unir todas as variáveis com até dois vizinhos, escolhidos aleatoriamente (outra
alternativa, sugerida por Heckerman et al [36], é definir uma estrutura inicial tipo árvore
aleatória). Posteriormente, inicia-se a busca pela melhor estrutura mediante o algoritmo
EM estrutural (linha 5). A pontuação global obtida nessa busca, assim como a estrutura
e parâmetros são armazenadas (linhas 6 e 7). Após todas essas iterações, retorna-se a RB
com a melhor pontuação (linha 10).
O procedimento de maior interesse é o algoritmo EM estrutural freqüentemente denominado SEM [68, 54] e apresentado na Figura 5.20.
Este procedimento encontra parâmetros maximum a posteriori para a estrutura prévia
97
dct-ufms
AlgoritmoSEM(D, S, Θ, ε)
. Saı́da : RB = hS, Θi e pontuacao
. Dados : pontuacao, pontuação de uma estrutura S
. Dados : pontAnterior, pontuação anterior
. Dados : e, diferença entre pontuações
1 Inı́cio
2
e←∞
3
enquanto e > ε faça
4
pontAnterior ← PontuacaoGlobal(S, Θ)
5
Θ ← IniciaAlgoritmoEM(D, S, ε)
6
pontuacao ← PontuacaoGlobal(S, Θ)
7
e ← pontuacao − pontAnterior
8
S ← PreCalcPais(S, pontuacao)
9
S ← GreedyHillClimbing(D, S, Θ, pontuacao)
10
fim enquanto
11
Retorna S, Θ, pontuacao
12 Fim
Figura 5.20: Algoritmo EM estrutural.
dada (linha 5). Com os dados completados calcula a pontuação inicial global (linha 6).
A partir dali, começa uma busca pela estrutura que tenha a pontuação máxima para os
dados completados. Esta busca é de tipo NP-difı́cil [12], sendo necessária a utilização
de um algoritmo de natureza heurı́stica, neste caso foi usado o algoritmo Greedy Hill
Climbing [36] (linha 9). A linha 7 é um procedimento que, baseado na pontuação global,
calcula possı́veis pais candidatos para cada variável de S.
O algoritmo heurı́stico Greedy Hill Climbing é apresentado na Figura 5.21. Este algoritmo gera novas combinações de variáveis e testa remoção, adição e inversão de arcos
formando as estruturas intermediárias do processo de busca.
Este algoritmo procura por estruturas enquanto essas melhoram a pontuação corrente
(linha 5). O processo finaliza quando, após uma iteração completa, não houve mudança
alguma na estrutura da RB ou o número máximo de mudanças estabelecido a priori foi
atingido. Em cada iteração escolhe-se uma variável aleatória (linha 6), e tenta-se adicionar, inverter ou remover cada uma das outras variáveis possı́veis (linha 10). Estas
modificações locais são temporárias (linhas 12 a 13), escolhendo-se a variável que gere a
maior pontuação dentre todas (linhas 15 a 18). Se a modificação nessa variável produz
um ganho na pontuação global, a modificação na estrutura é realizada (linhas 20 a 25) e
o número de mudanças totais aumentado, senão um máximo foi atingido (linha 26) e o
98
dct-ufms
GreedyHillClimbing(D, S, Θ, pontuacao)
. Entrada : pontuacao pontuação global atual
. Saı́da : S uma estrutura modificada
. Dados : numM udancas número de mudanças na estrutura S
. Dados : numT otalM udancas número total de mudanças na estrutura S
. Dados : mudou indica se S mudou
. Dados : pontM ax valor da máxima pontuação
. Dados : pamax pai candidato que produz maior pontuação
1 Inı́cio
2
numM udancas ← 0
3
numT otalM udancas ← |V |2
4
mudou ← verdadeiro
5
enquanto numM udancas < numT otalM udancas e mudou faça
6
Vi ← variável ou nó aleatório de S
7
pontuacaoAtual ← pontuacao
8
pontM ax ← −∞
9
pamax ← ∅
10
para pai ← 0 até |V | faça
11
se pai ⊂ Pais(Vi , S) então
12
pontuacaoAtual ← reverseRemoveArcoTemp(Vi , pai , S, pontuacao)
13
senão pontuacaoAtual ← adicionaArcoTemp(Vi , pai , S, pontuacao)
14
fim se
15
se pontuacaoAtual > pontM ax então
16
pontM ax ← pontuacaoAtual
17
pamax ← pai
18
fim se
19
fim para
20
se pamax 6= ∅ então
21
se pamax ⊂ Pais(Vi , S) então
S ← reverseRemoveArvoHillC(Vi , pai , S, pontuacao)
22
23
senão S ← adicionaArcoHillC(Vi , pai , S, pontuacao)
24
fim se
25
numM udancas ← numM udancas + 1
26
senão mudou ← f also
27
fim se
28
fim enquanto
29
Retorna S
30 Fim
Figura 5.21: Algoritmo Greedy Hill Climbing para busca de estruturas.
99
dct-ufms
processo finaliza.
As possı́veis operações locais podem ser adições, remoções ou a inversão na direção
dos arcos. A seguir é especificado como é feita a adição de um arco (Figura 5.22), um
processo similar é usado nas outras operações.
AdicionaArcoTemp(Vi , pai , S, pontuacao)
. Entrada : pai variável candidata a ser adicionada
. Entrada : pontuacao pontuação atual da RB
. Saı́da : pontuacaoAdicionar retorna mudança na pontuação
.
global por causa da adição
. Dados : pontuacaoAdicionar
1 Inı́cio
2
pontuacaoAdicionar ← pontuacao
3
se ¬Ciclo(Vi , pai ) então
4
A ← A ∪ Arco(Vi , pai )
5
pontuacaoAdicionar ← calculaPontuacao(Vi , S, pontuacao)
A ← A \ Arco(Vi , pai )
6
7
fim se
8
Retorna pontuacaoAdicionar
9 Fim
Figura 5.22: Algoritmo que adiciona arco temporário e testa a pontuação.
Este tipo de adição é temporária, com o objetivo de conhecer o ganho obtido na pontuação global causado pela adição deste novo arco. Suponha que, entre a variável corrente
e o pai candidato a ser adicionado não exista nenhuma ligação e, um possı́vel arco entre
eles não produzirá um ciclo dirigido na estrutura da RB (linha 3). Usa-se um algoritmo de
busca em profundidade entre os filhos do pai candidato para procurar possı́veis ciclos (por
isso é importante manter atualizada a informação de quais são os filhos de cada variável).
Feita essa comprovação, o pai candidato é adicionado ao conjunto de pais da variável
corrente e é realizado o cálculo da nova pontuação nesse nó (detalha-se este processo posteriormente). Este procedimento retorna a pontuação global obtida pela adição deste arco.
Um outro tipo de adição é própria do algoritmo Greedy Hill Climbing (Figura 5.23) e
modifica efetivamente a estrutura da RB.
Neste caso, a adição de um arco é realizada efetivamente sobre a estrutura, assim como
o cálculo da pontuação correspondente (linhas 4 e 5). Se a pontuação corrente for maior
que a pontuação anterior, ou seja, se houve um ganho na pontuação devido a adição desse
arco (processo Hill Climbing) a modificação é efetivada e a pontuação global é atualizada
100
dct-ufms
AdicionaArcoHillC(Vi , pai , S, pontuacao)
. Entrada : pai vértice candidato a ser adicionado
. Entrada : pontuacao pontuação atual da RB
. Saı́da : S retorna a estrutura da RB com um arco adicionado
. Dados : pontuacaoAdicionar pontuacao causa da adição
1 Inı́cio
2
pontuacaoAdicionar ← pontuacao
3
se ¬Ciclo(Vi , pai ) então
4
A ← A ∪ Arco(Vi , pai )
5
pontuacaoAdicionar ← calculaPontuacao(Vi , S, pontuacao)
6
se pontuacaoAdicionar > pontuacao então
7
pontuacao ← pontuacaoAdicionar
8
senão A ← A \ Arco(Vi , pai )
9
fim se
10
fim se
11
Retorna S
12 Fim
Figura 5.23: Algoritmo adiciona um arco na estrutura.
(linhas 6 e 7); caso contrário, as mudanças são desfeitas (linha 8). Neste tipo de adição
só são aceitas mudanças que gerem ganho na pontuação global, deste modo o algoritmo
vai escalando o espaço de soluções até atingir um máximo.
Há um outro tipo de algoritmo que permite mudanças (baseados em probabilidades)
que, a curto prazo, pioram a pontuação global e, a longo prazo, encontram melhores
soluções [36]. Este tipo de algoritmo, denominado Simulated Annealing, também foi implementado e testado neste trabalho. Porém, os resultados obtidos não foram significativamente melhores que Greedy Hill Climbing. Em geral, qualquer algoritmo de natureza
heurı́stica para otimização combinatória, desde que adaptado convenientemente à busca
de estruturas de RBs, poderia ser utilizado.
As duas versões do algoritmo EM Friedman [29, 30] para aprendizagem de estruturas
de RBs usam métricas de pontuação diferentes para avaliar estruturas candidatas. As
duas métricas foram implementadas neste trabalho. O algoritmo da Figura 5.24 descreve
o processo de cálculo da pontuação para uma variável.
Em um cenário de dados completos, o cálculo de pontuação de uma variável depende
das estatı́sticas suficientes dessa variável com relação aos seus pais, sendo este um processo inteiramente local (as métricas ou funções de pontuação são decomponı́veis, veja
Capı́tulo 4). Portanto, ao fazer uma modificação local (adição, remoção ou inversão da
101
dct-ufms
calculaPontuacao(Vi , S, pontuacao)
. Entrada : pontuacao pontuação global atual da RB
. Saı́da : pontuacaoF inal retorna mudança na pontuação global
. Dados : pontuacaoP revia pontuação previa para Vi
. Dados : novaP ontuacao pontuação nova para Vi
. Dados : pontuacaoF inal pontuação final da RB após a mudança
1 Inı́cio
2
pontuacaoP revia ← pontuacao(Vi )
3
novaP ontuacao ← metricaBDeExpect(Vi , S)
4
se pontuacaoP revia > novaP ontuacao então
5
pontuacaoF inal ← pontuacao − (pontuacaoP revia − novaP ontuacao)
6
senão pontuacaoF inal ← pontuacao + (pontuacaoP revia − novaP ontuacao)
7
fim se
8
Retorna pontuacaoF inal
9 Fim
Figura 5.24: Algoritmo que calcula a pontuação por causa da mudança local.
direção de um arco) e calcular a sua pontuação local é possı́vel saber se houve um ganho
ou perda na pontuação global. Para o caso de dados incompletos, este é um processo mais
demorado, as métricas não são mais decomponı́veis e precisa-se de aproximações; além
disso, as estatı́sticas suficientes não são fixas, são esperadas, e precisam ser calculadas
constantemente.
As métricas aproximadas implementadas estão baseadas em duas métricas usadas em
aprendizagem de RBs a partir de dados completos: a MDL [45] e a BDe [36]. A aproximação da métrica MDL não difere em grande medida da métrica original, a diferença
principal é que usa as freqüências esperadas para fazer o cálculo. A aproximação da
métrica BDe é detalhada posteriormente, e seu cálculo requer maiores especificações. Para ambas métricas o processo de cálculo é similar. Inicialmente, calcula-se a pontuação
global de toda a estrutura e armazena-se a pontuação obtida por cada variável na posição
correspondente do vetor de pontuações. Na linha 2 da Figura 5.24 a pontuação anterior
da variável corrente, Vi , é recuperada e comparada com a nova pontuação calculada (linha
3). As linhas 4 a 6 calculam o efeito da mudança de pontuação local na pontuação global
da estrutura.
Maior detalhe no cálculo da métrica para uma variável é dado na Figura 5.25.
Devido aos dados serem incompletos, as freqüências esperadas de cada instanciação
da variável com relação aos seus pais precisa ser calculada cada vez (linha 2), este é um
processo similar ao Passo E do algoritmo EM paramétrico (Figura 5.11). Uma vez que as
102
dct-ufms
metricaBDeExpect(Vi , S)
. Saı́da : pontuacao retorna cálculo da pontuação para Vi
. Dados : f reqEsperadas cálculo das freqüências esperadas para Vi
1 Inı́cio
2
f reqEsperadas ← Expectation(Vi , S)
3
pontuacao ← BDe(Vi , S, f reqEsperadas)
4
Retorna pontuacao
5 Fim
Figura 5.25: Algoritmo que calcula a pontuação para uma variável Vi .
freqüências são calculadas e armazenadas em uma matriz, pode-se aplicar, finalmente, as
aproximações à métrica sendo usada, neste caso particular, a métrica BDe (linha 3).
O algoritmo da Figura 5.26 representa o cálculo da métrica Bayesiana BDe, definida
no Capı́tulo 4, especificamente na equação 4.26, e por conveniência reproduzida aqui,
P (D|S) =
qi
n Y
Y
ri
Y
Γ(αij )
Γ(αijk + Nijk )
Γ(Nij + αij ) k=1
Γ(αijk )
i=1 j=1
onde αijk é um coeficiente de Dirichlet (veja Capı́tulo 4), obtido a partir de uma RB
equivalente em verossimilhança com a estrutura candidata. Ou seja, define-se uma RB a
priori equivalente com as redes procuradas, e calcula-se cada um dos coeficientes de Dirichlet. No caso de dados incompletos, Friedman [30] usa 4 aproximações dessa métrica.
Neste trabalho a aproximação linear foi usada, sendo seu cálculo dado pela Equação 4.26,
utilizando freqüências esperadas.
Nesta implementação foi suposto que não há uma RB a priori informada. Para o
cálculo de cada um dos coeficientes de Dirichlet, usa-se um parâmetro denominado amostra de tamanho equivalente (linha 6 da Figura 5.26). Este parâmetro representa conhecimento anterior sobre as probabilidades obtidas de uma amostra anterior de tamanho
N 0 . Buntime [6] considera os coeficientes de Dirichlet da Equação 5.4.3 não informados, e
baseado na amostra de tamanho equivalente oferece a fórmula a seguir, que ainda é uma
métrica BDe [36].
N0
αijk =
(5.3)
ri · qi
A função Gamma, Γ(x), para números inteiros pequenos pode ser calculada por Γ(n) =
(n − 1)! e para números grandes usa-se a fórmula de Stirling [1]. Porém, em dados
incompletos as freqüências esperadas obtidas são, em geral, números reais; nesse caso
considera-se a definição da função Γ como:
Z ∞
Γ(x) =
tx−1 e−t dt
(5.4)
0
103
dct-ufms
BDe(Vi , S, f reqEsperadas)
. Entrada : f reqEsperadas freqüências esperadas para Vi
. Saı́da : pontuacao retorna cálculo da pontuação para Vi
. Dados : P ai ∈ V pais de Vi
. Dados : ri número de estados de Vi
. Dados : qi número de estados dos pais de Vi
. Dados : tamanhoEquiv tamanho da amostra equivalente
. Dados : j, k, nij, nijknovo, nijnovo, rSum, sSum variáveis auxiliares
1 Inı́cio
2
ri ← |Vi |
3
4
qi ← EstadosPais(P ai , S)
5
pontuacao ← 0
6
tamanhoEquiv ← 64
7
8
nij ← 0
9
10
nij ← nij + f reqEsperadas(k)(j)
11
fim para
12
rSum ← 0
13
sSum ← 0
14
N ijkN ovo ← tamanhoEquiv/qi ∗ ri
15
N ijN ovo ← tamanhoEquiv/qi
16
17
rSum ← rSum + ln Γ(N ijkN ovo + f reqEsperadas(k)(j))
18
sSum ← ri ∗ ln Γ(N ijkN ovo)
19
pontuacao ← pontuacao + (rSum − sSum − ln Γ(N ijnovo + nij))
20
pontuacao ← pontuacao + ln Γ(N ijnovo)
21
fim para
22
fim para
23
Retorna pontuacao
24 Fim
Figura 5.26: Aspectos do cálculo da métrica BDe para Vi .
Esta integral pode ser calculada usando técnicas de integração numérica. Nesta implementação, inicialmente, foi usada a aproximação dada pelo método de Gauss-Laguerre [7],
útil para aproximar integrais desse tipo. Posteriormente, usou-se a aproximação do logaritmo da função Γ dada em [1] (linhas 17 a 20), a qual apresentou melhores resultados
quanto a rapidez e precisão de cálculo.
104
dct-ufms
Análise de Resultados
A seguir é feita uma análise de resultados obtidos da aplicação do algoritmo EM estrutural
para aprendizagem de estruturas. Foram feitos uma série de testes variando três tipos de
parâmetros: a) a quantidade de valores faltosos, b) o número de casos para aprendizagem
e c) a métrica usada no algoritmo EM estrutural.
Heckerman et al [36] sugerem a utilização da entropia cruzada e da análise estrutural
para medir a qualidade das redes aprendidas. Porém, na utilização da medida da entropia
são necessários os seguintes passos: criar uma estrutura comum para a rede original e a
rede aprendida, atribuir probabilidades e aplicar o algoritmo Kullback-Leibler. O enfoque
usado neste trabalho foi medir a diferença estrutural entre as redes original e aprendida,
especificamente a relação entre arcos adicionados e faltosos.
Houve uma certa dificuldade prática para comparar os algoritmos desenvolvidos com
os resultados de outros autores. Por exemplo, os resultados apresentados por Friedman [29, 30], só consideram distâncias entre distribuições. Também, não é comum os
trabalhos indicarem resultados relacionados quanto a tempos de processamento. A abordagem adotada neste trabalho foi comparar parte dos resultados com os de Tian et al [68],
os quais também usaram Netica para gerar dados de teste das RBs ASIA e ALARM e
apresentam alguns resultados de tempos e diferenças estruturais. A seguir apresenta-se a
análise para cada RB testada.
A Tabela 5.2 apresenta as diferenças estruturais entre a RB ASIA e as RBs aprendidas usando o algoritmo EM estrutural com cada uma das métricas aproximadas (MDL
e BDe). O tamanho da amostra usada e a porcentagem de dados faltosos também é
indicada. Os valores “a+b” indicam a quantidade “a” de arcos faltosos e “b” de arcos
adicionados para cada rede aprendida com relação a rede real.
A grosso modo, pode-se apreciar a diferença na utilização de cada métrica. A MDL,
em geral, apresenta um menor ı́ndice de arcos adicionados a mais, porém a quantidade de
arcos faltosos é maior quando comparado à utilização da métrica BDe. Como esperado,
a quantidade de dados usados para aprendizagem influenciou nas diferenças estruturais
para ambas métricas usadas. Quando maior a quantidade de dados para aprendizagem,
menores as diferenças estruturais.
Em geral, quando a porcentagem de dados faltosos é maior, a quantidade de arcos
adicionados e faltosos é acrescentada. Porém, há alguns casos em que a diferença da
porcentagem de dados faltosos não teve influência significativa. Por exemplo, no uso da
métrica MDL para uma amostra de 500 dados, não houve nenhuma diferença. Este resultado indica que, apesar dos dados terem uma quantidade importante de ruı́do (30% de
valores faltosos), o algoritmo EM estrutural é capaz de aprender uma estrutura próxima
da real.
105
dct-ufms
Tabela 5.2: Análise de resultados para rede bayesiana ASIA.
Tamanho Dados
100
500
1000
2000
5000
10000
Métrica
MDL
BDe
MDL
BDe
SEM(Tian)
MDL
BDe
SEM(Tian)
MDL
BDe
SEM(Tian)
MDL
BDe
SEM(Tian)
MDL
BDe
10%
4+3
2+7
3+3
1+7
0+6
1+2
0+6
1+4
2+5
0+5
1+4
2+5
1+6
1+2
4+2
0+8
30%
5+4
3+8
3+3
3+6
1+7
3+4
1+5
1+9
1+3
2+7
1+8
2+5
0+8
2+8
1+7
0+7
A menor diferença estrutural foi encontrada usando-se a métrica MDL, sendo a amostra de tamanho 1000 e 10% de dados faltosos. O resultado obtido foi “1+2”, um arco
faltoso e dois arcos a mais inseridos. Outro fenômeno analisado é o overfitting, pois,
segundo os resultados obtidos, usar dados de tamanho superior a 2000 não melhoraram
a qualidade da rede aprendida; ao contrário, a qualidade das estruturas aprendidas foi
degradada.
A métrica BDe fez parte da definição do algoritmo EM estrutural (SEM) quando criada por Friedman [30]. Na Tabela 5.2, é apresentado os resultados de Tian et al [68],
indicado como SEM (Tian). Os resultados obtidos por esses autores e o algoritmo SEM
implementado neste trabalho não diferem significativamente. mostrando em alguns casos
(não em todos) melhores resultados para a implementação desenvolvida. Por exemplo, o
melhor resultado para SEM (Tian) foi “1+2”, um arco faltoso e 2 variáveis a mais inseridas, quando usados 5000 dados com porcentagens de 10% de valores faltosos.
No caso da utilização da BDe o melhor resultado foi “0+5”, 5 variáveis inseridas a
mais, usando 2000 instâncias de dados com 10% de dados faltosos. Na utilização desta
métrica houve diferenças, embora não muito significativas, quanto à utilização de diferentes porcentagens de dados faltosos, sendo em todos os casos obtidas estruturas de
qualidade inferior, a medida que a porcentagem de dados faltosos aumentava.
As diferenças entre BDe e SEM (Tian) são justificadas, pois, embora os mecanismos
usados para gerar os dados sejam iguais (através da ferramenta Netica), as amostras ge106
dct-ufms
radas não podem ser iguais.
A RB ALARM também foi avaliada quanto a diferenças estruturais. Não há maiores
referências sobre os resultados encontrados por outros autores nesta RB, com relação a arcos faltosos e arcos adicionados. Outra vez a comparação é feita com relação ao trabalho de
Tian et al. A Tabela 5.3 apresenta os resultados obtidos. Para este tipo de RB é notória a
diferença de resultados quando a quantidade de dados usados para aprendizagem é maior.
Quando usado uma menor quantidade de dados, o algoritmo EM estrutural com as
duas métricas não consegue recuperar a estrutura fundamental, observando-se um progresso significativo quando os dados são acrescentados. Com instâncias de 10000 e 10%
de dados faltosos, a estrutura recuperada é próxima da real “5+4”, sendo que Tian et al,
conseguiram resultados similares “4+4”. Outro aspecto importante a notar é que, nesta
RB, as diferenças estruturais são maiores a medida que a porcentagem de dados faltosos
é incrementada. A métrica BDe conseguiu os melhores resultados com relação à MDL,
porém, observa-se que a adição de arcos é maior que no caso da métrica MDL.
Tabela 5.3: Análise de resultados para rede bayesiana ALARM.
Tamanho Dados
500
1000
2000
5000
10000
Métrica
MDL
BDe
MDL
BDe
MDL
BDe
MDL
BDe
MDL
BDe
SEM(Tian)
10%
28 + 16
27 + 20
18 + 10
16 + 15
16 + 9
14 + 13
10 + 8
7+9
6+6
5+4
4+4
30%
37 + 20
30 + 34
21 + 12
18 + 20
20 + 12
15 + 15
11 + 10
8 + 11
6+7
6+5
7+3
Os tempos obtidos pelo algoritmo SEM sobre dados da RB ASIA, usando as métricas
MDL e BDe e a porcentagem de dados faltosos de 10 e 30% são ilustrados na Figura 5.27.
Como previsto, a porcentagem de dados faltosos influencia o tempo de convergência
do algoritmo EM estrutural sendo, em alguns casos, até 5 vezes maior para instâncias
com 30% de dados faltosos. A métrica MDL em ambos casos requer menor tempo de
processamento, pois sua aplicação é direta. Para o caso da métrica BDe, o cálculo dos
coeficientes de Dirichlet e a aproximação da função Γ influenciam para que o tempo de
processamento seja maior.
Poucos autores indicam tempos de processamento para o algoritmo EM estrutural.
Tian et al [68] apresentam tempos de processamento de 152.12 milisegundos para uma
107
dct-ufms
instância de 2000 dados da RB ASIA, com 10% de dados faltosos. Para essa mesma
instância, os algoritmos implementados obtiveram tempos de 61.02 e 42.460 milisegundos para as métricas MDL e BDe respectivamente, melhorando os tempos de Tian et al.
Porém, deve-se considerar que as condições de teste, como plataforma usada, não são
indicadas por esses autores.
TEMPO ASIA−SEM
600000
Legenda
10% valores faltosos(BDe)
10% valores faltosos(MDL)
30% valores faltosos(BDe)
30% valores faltosos(MDL)
500000
400000
300000
200000
100000
0
0
2000
4000
6000
Número de casos
8000
10000
Figura 5.27: Tempo algoritmo SEM - ASIA.
Com relação aos tempos obtidos com a rede ALARM, apresentam o mesmo comportamento que a rede ASIA, com tempos que variam de 4.91 minutos para uma amostra
com 500 dados até 6.45 horas, para a amostra de 10000 casos e 10% de dados faltosos.
Para esta RB não existem maiores informações sobre tempos de processamento de outros
autores. Tian et al [68] indicam que para uma amostra de 40000 dados, o algoritmo EM
estrutural leva mais de 24 horas de processamento, por outro lado, Friedman [29] indica
um tempo de 6 horas aproximadamente para uma instância de 10000 dados.
O algoritmo EM estrutural descrito nesta seção conseguiu recuperar satisfatoriamente estruturas de redes bayesianas pequenas como a RB NETICA e ANGINA, mas os
resultados desses testes não foram incluı́dos neste trabalho.
108
5.5
dct-ufms
Neste capı́tulo foram apresentados as metodologias, aspectos de implementação e os resultados obtidos através de testes dos algoritmos EM para aprendizagem de RBs. Foi
realizada uma comparação com trabalhos anteriores, mostrando-se a análise correspondente.
Para o caso do algoritmo EM paramétrico a análise realizada foi baseada nos tempos
de processamento e qualidade das distribuições aprendidas. Para medir esta qualidade,
foi usada a medida da entropia cruzada como dada em [36]. Quanto menor a complexidade das redes e maior a quantidade de dados para aprendizagem, as distribuições obtidas
foram mais próximas das reais. As RBs aprendidas a partir de dados da RB ALARM
apresentaram as maiores diferenças com relação as distâncias entre as distribuições, sendo
o tempo de processamento nesta rede também maior. Foi analisado o tempo envolvido
em cada etapa do algoritmo EM paramétrico, mostrando-se que a inferência é processo
mais custoso desta implementação.
Para o caso do algoritmo EM estrutural (SEM) foram analisadas as estruturas obtidas
e o tempo de processamento. A análise estrutural foi realizada observando-se as diferenças
quanto a adições corretas e omissões de arcos entre as RBs aprendidas e as RBs reais.
Foi avaliada cada uma das métricas e a influência da porcentagem dos dados faltosos. Os
resultados obtidos com dados da rede ASIA, foram os esperados, porém encontraram-se
alguns fenômenos interessantes nestes resultados, tais como overfitting. Os resultados
desta rede foram comparados com os de Tian et al [68], sendo as diferenças justificadas e
menores.
Os resultados na rede ALARM confirmaram as suposições iniciais. A relação entre
tamanho das amostras e porcentagens de dados faltosos têm uma influência significativa
na qualidade das redes obtidas. Em nenhum dos casos as redes obtidas foram iguais
as reais, sendo os resultados obtidos na rede ALARM semelhantes com os resultados de
outros autores. O tempo para este tipo de algoritmos foi consideravelmente elevado, a
medida que a complexidade da rede e a quantidade de dados era aumentada.
109
Capı́tulo 6
Conclusão
O objetivo deste trabalho foi a implementação de algoritmos EM para aprender parâmetros
e estruturas de RBs a partir de dados com instâncias incompletas, problema bastante comum em bancos de dados de aplicações reais. Na literatura encontram-se várias propostas
para a resolução deste problema de grande importância prática.
O algoritmo EM, mediante estimativas de máxima verossimilhança, permite determinar parâmetros desconhecidos a partir das instâncias incompletas. Baseado neste princı́pio
foi desenvolvido o algoritmo EM paramétrico, usado para aprendizagem de parâmetros
em redes bayesianas. Similarmente, uma extensão do algoritmo EM foi desenvolvida para
aprendizagem de estruturas, algoritmo EM estrutural, que usa o paradigma de busca e
pontuação.
As propostas atuais de implementação desses algoritmos oferecem soluções razoáveis,
descobrindo distribuições de probabilidades conjuntas para futuras inferências e relações
causais entre variáveis, mas ainda sujeitas a melhorias, principalmente quanto a otimizar
o tempo de execução. Além disso, atualmente não existem soluções que possam ser consideradas padrões. Alguns autores citam o algoritmo EM estrutural dado por Friedman [30]
como sendo o que trouxe maior avanço nesta área, mas isto ainda está em discussão. Portanto, há necessidade de investimentos em pesquisas neste campo.
A principal dificuldade encontrada ao longo deste trabalho foi a falta de experiência
e conhecimentos anteriores sobre redes bayesianas. Foi necessária uma revisão completa
da literatura de RBs. A elaboração deste trabalho passou por diversas etapas: construção de RBs, estudo dos algoritmos de inferência e, finalmente, aprendizagem. Embora
os algoritmos para aprendizagem implementados no trabalho sejam baseados em dados
completos, verificou-se que as dificuldades para esses são de fato maiores quando os dados
são incompletos.
Os algoritmos EM são descritos pelos autores de forma sucinta, sem maiores detalhes
110
dct-ufms
de implementação. Especificamente, no algoritmo EM paramétrico [46] não fica claro
como aplicar a inferência bayesiana para completar as instâncias e também como determinar os valores numéricos esperados para o cálculo dos parâmetros. Para o algoritmo
EM estrutural [29, 30] pressupõe-se o conhecimento de algoritmos de aprendizagem para
dados completos, entretanto eles diferem no cálculo da métrica. Nesse caso, a partir de
uma estrutura aleatória, “completam-se” os dados com o algoritmo EM paramétrico e a
seguir, iterativamente, busca-se uma estrutura que tenha a maior pontuação conforme a
métrica BDe [36]. Os textos não deixam claro como se calcula a métrica, pois exigem
aproximações de funções Gamma.
Usar a funcionalidade da ferramenta UnBBayes foi de grande valia. Sua interface permitiu visualizar as estruturas intermediárias que eram criadas pelo algoritmo de busca,
inclusive suas tabelas de probabilidade, até a definição da estrutura ótima.
Também foram usadas as classes para inferência probabilı́stica e de alguns algoritmos
de aprendizagem para dados completos. Porém, notou-se que alguns métodos e estruturas
de dados não eram adequados para aprendizagem em situações de dados incompletos e
por isto foi necessário modificá-las. Respeitando hierarquias novas classes e estruturas de
dados foram criadas.
A entrada de dados na UnBBayes é feita mediante a leitura de arquivos os quais
não passam, depois da leitura, por tratamentos de condensação. Entretanto, é comum
que dados gerados para teste usando alguns dos métodos de Monte Carlo, inclusive em situações reais, apresentem instâncias repetidas. Condensar os dados usando uma tabela de
dispersão (hash) que permita eliminar as repetições mas, guardando a sua freqüência, possibilita otimizar o acesso as instâncias, agora acessando uma vez só e usando as freqüências
na aprendizagem. Neste trabalho isto foi introduzido como um novo método na classe de
leitura de dados e que faz as chamadas para os algoritmos de aprendizagem.
O desempenho das implementações quanto a aprendizagem de estruturas e de suas
probabilidades correspondentes produziu resultados semelhantes aos de outros autores
que usaram a mesma metodologia, como por exemplo Tian et al [68], o que nos faz acreditar na correta implementação. Portanto, a inclusão final das classes ao pacote pode ser
feita com confiança.
Quanto ao tempo de execução, foi difı́cil fazer uma comparação porque, quando os
autores citam um tempo de 6 horas, por exemplo para os dados ALARM, não citam a
plataforma ou a linguagem e nem a forma de obter os dados de testes que precede a
aplicação de algoritmos de aprendizagem. A utilização de Java no desenvolvimento influenciou este desempenho. Por ser uma linguagem interpretada, o processo de execução
torna-se mais lento comparado com outras linguagens como, por exemplo, C++.
Ainda que tenha sido difı́cil comparar resultados com outros autores, pois os métodos e
111
6.1. Contribuições
dct-ufms
as condições usadas por eles são diferentes, tentou-se encontrar as melhores estruturas de
dados e técnicas de programação para cada etapa do desenvolvimento. Por exemplo, para
busca de estrutura de uma rede, que é um problema NP-difı́cil, foram usadas técnicas baseadas em dois algoritmos heurı́sticos: greedy hill climbing e simulated annealing. A partir
de dados incompletos e sem nenhuma informação a priori os algoritmos conseguiram identificar estruturas e probabilidades de redes bayesianas similares as já consideradas padrões.
6.1
Contribuições
O presente trabalho trás uma série de contribuições que são detalhadas a seguir:
Foi feita uma revisão bibliográfica do estado-da-arte em inferência e aprendizagem de
RBs, dando uma atenção especial a aprendizagem a partir de dados incompletos. Certamente esta revisão poderá servir como base para futuras pesquisas dentro da área.
As implementações do algoritmo EM paramétrico e EM estrutural com as duas métricas
aproximadas serão adicionadas à ferramenta UnBBayes, sendo que o código ficará disponı́vel para pesquisa e também para contribuições no sentido de melhorá-lo. Cabe salientar que, dentre as ferramentas analisadas, nenhuma oferece esta funcionalidade gratuitamente, além disso, poucas ferramentas lidam com dados faltosos. A especificação de
detalhes quanto as estratégias e métodos usados no código dessa implementação facilita
a compreensão no caso de estudo e introdução de modificações, o que é um diferencial
importante, pois não é comum encontrá-la na literatura.
Os resultados apresentados e analisados no Capı́tulo 5 demonstraram que os algoritmos implementados neste trabalho são adequados para lidar com dados incompletos. A
comparação até o momento foi feita só com os resultados de Tian et al [68], com os quais
obteve-se similaridade quanto às estruturas aprendidas, isto é, quanto a quantidade de
arcos adicionados e faltosos.
6.2
Limitações Atuais e Sugestões para Trabalhos Futuros
Apesar dos resultados obtidos serem os esperados com a metodologia utilizada, considerase que uma aplicação da implementação em dados reais seria limitada a domı́nios com
número médio de variáveis, cerca de 37, e em situações que o tempo para aprendizagem
não seja o mais importante. Implementações recentes incorporam otimizações que podem
melhorar estes tempos [68].
112
6.2. Limitações Atuais e Sugestões para Trabalhos Futuros
dct-ufms
O algoritmo EM paramétrico implementado, segundo os resultados obtidos quanto a
tempo de execução, teve uma demora considerável no cálculo da inferência. Abordagens
como as propostas dadas em [33, 21, 61], que substituem o EM paramétrico, poderiam
ser consideradas.
Para o caso do algoritmo EM estrutural, os algoritmos para busca de estruturas são
de natureza heurı́stica o que não garante que se obtenha a melhor estrutura. Seria interessante testar outras alternativas de algoritmos heurı́sticos e avaliar se os ganhos quanto à
qualidade seriam significativos, considerando que o tempo de execução seria maior, devido
a maior sofisticação inerente a essas técnicas.
O algoritmo EM estrutural faz parte do paradigma de busca e pontuação. Há poucos
trabalhos desenvolvidos envolvendo o paradigma de independência condicional, o algoritmo EMI [68] é um deles. Os resultados obtidos, segundo os autores deste algoritmo,
foram alentadores no que diz respeito aos tempos de execução, sendo consideravelmente
menores que o algoritmo EM estrutural (SEM). A qualidade das estruturas obtidas foi
praticamente igual, entretanto, sendo necessário mais pesquisa nessa direção.
A partir do algoritmo EM estrutural pode-se pesquisar por algoritmos mais gerais,
que aprendam várias redes em conjunto, denominadas multi-redes [48, 66].
Com relação ao aspecto metodológico, quando duas RBs são comparadas, pode-se avaliar tanto a distância entre probabilidades quanto a diferença estrutural. A medição da
distância entre duas RBs com estruturas diferentes não é direta; como descrito por Heckerman et al [36] precisa-se de: uma estrutura consistente com as duas RBs comparadas
e das suas distribuições de probabilidade conjunta. Porém, esses autores não descrevem
o algoritmo para construir essa estrutura consistente, ao invés disso, fazem referência ao
artigo de Matzkevits e Abramson (1993)apud [36]. A impossibilidade de obter esse último
artigo não permitiu a utilização da distância para avaliar as estruturas das RBs aprendidas. Uma implementação futura do cálculo desta distância permitiria uma comparação
com maior número de trabalhos.
Os testes realizados para os algoritmos desenvolvidos foram feitos sobre dados fictı́cios,
usualmente usados para análise experimental. O próximo passo deve ser o teste destes
algoritmos em aplicações reais, por exemplo, poder-se-ia criar classificadores a partir das
redes aprendidas e avaliar o desempenho. Porém, para a construção de classificadores
existem outros algoritmos que precisam ser pesquisados [32].
113
[1] M. Abramowitz e A. Stegun. Handbook of mathematical functions with formulas,
graphs, and mathematical tables. Washington, National Bureau of Standards, 1972.
[2] T. Bayes. An essay towards solving a problem in the doctrine of chances. Philosophical
Transactions of the Royal Society of London, 53:370–418, 1763.
[3] I. Beinlich, H. Suermondt, R. Chavez, e G. Cooper. The ALARM monitoring system: A case study with two probabilistic inference techniques for belief networks.
In Proceedings of the Second European Conf. on Artificial Intelligence in Medicine,
volume 38, páginas 247–256. 1989.
[4] B. Buchanan e E. Feigenbaum. DENDRAL and META-DENDRAL: their applications dimensions. Artificial Intelligence, 11:5–24, 1978.
[5] B. Buchanan e E. Shortliffe. Rule-Based Expert Systems: The MYCIN Experiments
of the Stanford Heuristic Programming Project. Reading, MA: Addison-Wesley, 1984.
[6] W. Buntime. Operations for learning with graphical models. Journal of Artificial
Intelligence Research, 2:159–225, 1994.
[7] B. Carnahan, H. Luther, e J. Wilkes. Applied Numerical Methods. New York, Wiley,
1990.
[8] E. Castillo, J. Gutiérrez, e A. Hadi. Expert Systems and Probabilistic Network Models.
New York, Springer, 1997.
[9] E. Charniak. Bayesian networks without tears. Journal of Artificial Intelligence
Research, 12:50–63, 1991.
[10] P. Cheeseman e J. Stutz. Bayesian classification (AutoClass): Theory and results.
In Advances in Knowledge and Data Mining, páginas 153–180. 1995.
[11] J. Cheng e D. Bell.
Learning bayesian networks from data: An efficient approach based on information theory. In Proceeding of the sixth ACM
International Conference on Information and Knowledge Management. 1997.
http://www.cs.ualberta.ca/ jcheng/Doc/report98.pdf.
[12] D. Chickering, D. Geiger, e D. Heckerman. Learning bayesian networks is NPcomplete. In Learning from data: AI and Statistics, volume 5, páginas 121–130.
1996.
114
dct-ufms
[13] D. Chickering e D. Heckerman. Efficient approximations for the marginal likelihood of
bayesian networks with hidden variables. Machine Learning, 29(2-3):181–212, 1997.
[14] C. Chow e C. Liu. Approximating discrete probability distributions with dependence
trees. IEEE Transactions on Information Theory, 14:462–467, 1968.
[15] H. Coelho, M. Ladeira, e R. Viccari. Raciocı́nio probabilı́stico em sistemas inteligentes. In Anais XVIII Jornada de Atualização em Informática, volume 2, páginas
307–365. FUKS, 1999.
[16] G. Cooper. The computational complexity of probabilistic inference using bayesian
belief networks. Artificial Intelligence, 42:393–405, 1990.
[17] G. Cooper. A bayesian method for learning belief networks that contain hidden
variables. Journal of Intelligent Systems, 4:71–88, 1995.
[18] G. Cooper e E. Herskovits. A bayesian method for the induction of probabilistic
networks from data. Machine Learning, 9:309–347, 1992.
[19] F. Cozman. Generalizing variable elimination in bayesian networks. In Workshop on
Probabilistic Reasoning in Bayesian Networks, páginas 21–26. SBIA/Iberamia, 2000.
http://www-2.cs.cmu.edu/ javabayes/Download/jb-heading.ps.gz.
[20] W. T. da Silva e M. Ladeira. Mineração de dados em redes bayesianas. In anais do
XXII Congresso Brasileiro de Computação SBC , volume 2, páginas 235–286. Jornada
de Atualização em Informática - XXI JAI, 2002.
[21] P. Dagum e M. Luby. Approximating probabilistic inference in bayesian belief
networks is NP-hard. Artificial Intelligence, 60:141–153, 1993.
[22] A. Darwiche. Conditioning methods for exact and approximate inference in causal
networks. In Proceedings of the Eleventh Conference on Uncertainty in Artificial
Intelligence (UAI-95), páginas 99–107. 1995.
[23] B. de Finetti. Foresight: Its logical laws its subjective sources. In Kyburg H. E. and
Smokler H. G., editors, Studies in Subjetive Probability, páginas 55–118. 1937.
[24] M. Degroot. Probability and Statistics. MA, Reading, Addison-Wesley, 1975.
[25] A. Dempster. A generalization of bayesian inference. Journal of the Royal Statistical
Society (Series B), 30:205–267, 1968.
[26] F. Diez. Local conditioning in bayesian networks. Artificial Intelligence, 87:1–20,
1996.
[27] F. Diez.
Introducción al Razonamiento Aproximado.
Madrid, Departamento de Inteligencia Artificial, UNED, Edición Revisada, 2003.
http://www.ia.uned.es/%7Efjdiez/libros/razaprox.pdf.
[28] R. Fisher. On the mathematical foundations of the theoretical statistics. Philosophical
Transactions of the Royal Society of London, series A, 222:309–368, 1922.
115
dct-ufms
[29] N. Friedman.
Learning belief networks in the presence of missing values and hidden variables.
In Proceedings of the Fourteenth International Conference on Machine Learning (ICML’97), páginas 125–133. 1997.
http://www.cs.huji.ac.il/ nir/Papers/Fr1.pdf.
[30] N. Friedman. The bayesian structural EM algorithm. In Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI-98), páginas 129–138.
Morgan Kaufmann, 1998. http://www.cs.huji.ac.il/ nir/Papers/Fr2.pdf.
[31] R. Fung e B. Del Favero. Applying bayesian networks to information retrieval. Communications of the ACM , 38:42–ff, 1995.
[32] D. Geiger e M. Goldszmidt. Bayesian networks classifiers. Machine Learning, 29:131–
163, 1997.
[33] D. Heckerman.
A tutorial on learning with bayesian networks.
latório técnico,
Microsoft Research tech. report,
MSR-TR,
ftp://ftp.research.microsoft.com/pub/tr/tr-94-09.ps.
Re1996.
[34] D. Heckerman. Bayesian networks for data mining. Data Mining and Knowledge
Discovery, 1:79–119, 1997.
[35] D. Heckerman, J. Breese, e K. Rommelse. Decision-theoretic troubleshooting. Communications of the ACM , 38:49–57, 1995.
[36] D. Heckerman, D. Geiger, e D. Chickering. Learning bayesian networks: The combination of knowledge and statistical data. Machine Learning, 20:197–243, 1995.
[37] D. Heckerman e M. Wellman. Bayesian networks. Communications of the ACM ,
38:27–30, 1995.
[38] E. Hruschka. Imputação Bayesiana no Contexto da Mineração de Dados. Tese de
Doutoramento, Programa de Engenharia Civil -COPPE-UFRJ- Rio de Janeiro/RJ Brasil, Outubro 2003.
[39] C. Huang e A. Darwiche. Inference in belief networks: A procedural guide. International Journal of Approximate Reasoning, 15:225–263, 1996.
[40] F. Jensen. Bayesian Networks and Decision Graphs. Springer Verlag, 2001.
[41] F. V. Jensen e F. Jensen. Optimal junction trees. In Proceedings of the 10th Conference on Uncertainty in Artificial Intelligence, páginas 360–366. 1994.
[42] S. Kirkpatrick, C. Gelatt, e M. Vecchi. Optimization by simulated annealing. Science,
220:671–680, 1983.
[43] U. Kjærulff. Triangulation of graphs-algorithms giving small total state space. Relatório técnico, Technical Report R-90-09, Dept. of Math. and Comp. Sci., Aalborg
University, Denmark, 1990.
116
dct-ufms
[44] G. Klir e B. Yuan. Fuzzy Sets and Fuzzy Logic: Theory and Applications. New
Jersey, Prentice Hall, 1995.
[45] W. Lam e F. Bacchus. Learning bayesian belief networks: An approach based on the
MDL principle. Computational Intelligence, 10(4):269–293, 1994.
[46] S. Lauritzen. The EM algorithm for graphical association models with missing data.
Computational Statistics and Data Analysis, 19:191–201, 1995.
[47] S. Lauritzen e D. Spiegelhalter. Local computations with probabilities on graphical
structures and their application to expert systems. Journal Royal Statistics Society
B , 50(2):157–194, 1988.
[48] M. Meila e M. Jordan. Estimating dependency structure as a hidden variable. In
Proceedings of the 1997 conference on Advances in neural information processing
systems(NIPS 10), páginas 584–590. 1998.
[49] T. Mitchell. Machine Learning. McGraw Hill, 1997.
[50] A. Mood, F. Graybill, e D. Boes. Introduction to the Theory of Statistics. New York,
McGraw-Hill, Third Edition, 1974.
[51] J. Myers, K. Laskey, e K. DeJong.
Learning bayesian networks from
incomplete data using evolutionary algorithms.
In GECCO’99 . 1999.
http://ite.gmu.edu/ klaskey/papers/gecco99.pdf.
[52] P. Naim, P. Wuillemim, P. Leray, O. Pourret, e A. Becker. Réseaux Bayésiens. Paris,
Eyrolles, 2004.
[53] J. Peña, J. Lozano, e P. Larrañaga. Learning bayesian networks for clustering by
means of constructive induction. Pattern Recognition Letters, 20:1219–1230, 1999.
[54] J. Peña, J. Lozano, e P. Larrañaga. An improved bayesian structural EM algorithm
for learning bayesian networks for clustering. Pattern Recognition Letters, 21(8):779–
786, 2000.
[55] J. Pearl. Evidencial reasoning using stochastic simulation of causal models. Artificial
Intelligence, 32:247–257, 1987.
[56] J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Revised Second Printing. San Mateo, CA: Morgan Kaufmann, 1991.
[57] J. Pearl. Belief networks revisited. Artificial Intelligence, 59:49–56, 1993.
[58] M. Peot e R. Shachter. Fusion and propagation with multiple observations in belief
networks. Artificial Intelligence, 48(3):299–318, 1991.
[59] M. Ramoni. Robust learning with missing data. Machine Learning, 45(2):147–170,
2001.
117
dct-ufms
[60] M. Ramoni e P. Sebastiani. Learning bayesian networks from incomplete databases. In Proceedings of the Thirteen Conference on Uncertainty in Artificial
Intelligence(UAI-97). 1997.
[61] S. Russell e P. Norving. Artificial Intelligence: A Modern Approach. Prentice Hall,
1995.
[62] G. Shafer. A Mathematical Theory of Evidence. Princeton University Press, Princeton, New Jersey, 1976.
[63] G. Shafer e J. Pearl. Readings in Uncertain Reasoning. Morgan Kaufmann, San
Mateo, CA, 1990.
[64] M. Singh. Learning Bayesian Networks for Solving Real-World Problems. Tese
de Doutoramento, Computer and Information Science -University of PennsylvaniaUSA, Maio 1998.
[65] P. Spirtes, C. Glymour, e R. Scheines. Causation, prediction, and search. (2nd
edition, revised) Cambridge, MA: MIT Press, 2001.
[66] B. Thiesson, C. Meek, D. Chickering, e D. Heckerman. Learning mixtures of bayesian networks. In Proceedings of the Fourth Conference on Uncertainty in Artificial
Intelligence (UAI-98). 1998.
[67] F. Tian, Y. Lu, e C. Shi. Learning bayesian networks with hidden variables using the
combination of EM and evolutionary algorithm. In Proceedings of the 5th Asia-Pacific
Conference in Knowledge Discovery and Data Mining (PAKDD 2001), páginas 568–
574. 2001.
[68] F. Tian, H. Zhang, e Y. Lu. Learning bayesian networks from incomplete data based
on EMI method. In Proceedings of the Third IEEE International Conference on Data
Mining(ICDM’03), páginas 323–330. 2003.
[69] L. van der Gaag. Bayesian belief networks: Odds and ends. The Computer Journal ,
39:97–113, 1996.
[70] N. Wermuth e S. Lauritzen. Graphical and recursive models for contingency tables.
Biometrika, 72:537–552, 1983.
[71] M. Yannakakis. Computing the minimal fill-in is NP-complete. SIAM Journal of
Algebraic Discrete Methods, 2:77–79, 1981.
118

Algoritmos EM para Aprendizagem de Redes - FACOM

Transcrição

Documentos relacionados

A distribuiç ˜ao Weibull inversa generalizada na modelagem de

Modelo do trabalho - DT - Home Page

Nota de Alta

Reitores na Moncloa - Duvi

Análise de Algoritmos

SHELLAC 78`

142968

Prova - Profmat

Segundo - Laboratório de Sistemas de Potência da UFSC

RAFAEL CUNHA DE ALMEIDA