Redes Bayesianas e Aplicações
Alguns Algoritmos de Estimação de Estrutura
Prof. Dr. Anderson Ara
18 de Março de 2021 - Handout #04
CC BY NC ND
4.1 Aprendizado de Estrutura
O aprendizado de redes bayesiana busca por modelos que melhor representem a maneira com que as variáveis se conectam entre si, em que tais conexões caracterizem as dependências marginais e condicionais entre seus nós (Koller e Friedman 2009). Uma vez que as redes bayesianas são compostas por dois elementos, sua estimação é dividida em duas tarefas principais: a estimação da estrutura \(G\) e dos parâmetros de \(P(\mathbf{X})\). Os métodos básicos de estimação dos parâmetros já foram abordados no Capítulo 2.
A estrutura de uma rede bayesiana pode ser descrita por especialistas e, neste caso, o processo de estimação irá se restringir à estimação dos parâmetros (Uusitalo 2007). Porém, o processo de estimação pode ser realizado através dos dados e da utilização de algoritmos de estimação.
Encontrar a estrutura ótima de uma rede bayesiana a partir de dados é um processo difícil. Chickering (1995) salienta que a estimação de estrutura é uma tarefa de alta complexidade computacional (NP-difícil), mesmo quando cada nó é restrito a ter no máximo dois pais.
Neste contexto, os métodos de estimação de estrutura são moderadamente recentes e ainda estão em evolução, mas têm sido eficazes para solução de alguns problemas de modelagem. Além disso, são capazes de ajustar modelos de alta dimensão que não são afetados pelo problema conhecido como maldição de dimensionalidade (Scutari 2010).
Duas classes de métodos para estimar a estrutura de redes bayesianas a partir de dados são comuns na literatura: métodos baseados em restrições e métodos baseados em pontuação.
Métodos baseados em restrição: Esses algoritmos baseiam-se em estimar a estrutura da rede analisando as relações probabilísticas decorrentes da propriedade de Markov e de testes de independência condicional e, em seguida, construindo um DAG que satisfaça as declarações de d-separação. Os modelos resultantes são frequentemente interpretados como modelos causais, mesmo quando estimados a partir de dados observacionais (Pearl 1988).
Métodos baseados em pontuação: Esses algoritmos atribuem uma pontuação a cada estrutura de rede bayesiana candidata e tentam maximizá-la através de meta-heurísticas. Algoritmos de greedy-search (como subida de encosta ou busca tabu) são uma escolha comum, mas muitos outros tipos de procedimento de busca podem ser utilizados.
Uma terceira classe de métodos de estimação é composta por algoritmos híbridos, que combinam ambas as abordagens acima. Scutari, Graafland, e Gutiérrez (2019), em uma comparação geral entre diversos de algoritmos, mostram que os algoritmos híbridos não são mais rápidos que algoritmos baseados em restrição ou pontuação, bem como não há diferença sistemática entre a precisão dos algoritmos híbridos e os baseados em restrição.
Nas próximas seções, os métodos baseados em restrição e os métodos baseados em pontuação são apresentados com maiores detalhes.
4.2 Métodos baseados em restrição
Essa classe de algoritmos se baseia em testes de independência condicional para verificar as conexões de arcos. De uma forma geral, quando há independência (marginal ou condicional) entre duas variáveis, o arco entre tais variáveis é retirado (Zhang et al. 2012). Desta forma, os testes de independência condicional devem ser definidos previamente e são vinculados ao tipo de dado em análise, para o caso discreto testes comuns são via informação mútua condicional e \(\chi^2\) de Pearson, para o caso contínuo, sobre a suposição de normalidade, uma escolha natural é o teste via correlações parciais de Pearson (Nagarajan, Scutari, e Lèbre 2013).
4.2.1 Algoritmo PC
Dentre os algoritmos mais comuns entre os métodos baseados em restrição, tem-se o algoritmo PC (Spirtes, Glymour, e Scheines 2000) (nomeado em homenagem a seus autores, Peter e Clark), sendo considerado uma implementação do algoritmo IC (Inductive Causation) proposto por Pearl e Verma (1991), um algoritmo conceitual relativo a estimação baseada em restrição. O algoritmo PC foi modernizado por Colombo e Maathuis (2014), em uma versão conhecida como PC-estável.
Pseudocódigo do algoritmo IC
Para cada par de variáveis \(A\) e \(B\), procure um conjunto \(S_{AB}\) tal que \(A \perp B | S_{AB}\). Construa um grafo não direcionado, tal que os vértices \(A\) e \(B\) sejam conectados com uma aresta se e somente se nenhum \(S_{AB}\) for encontrado.
Para cada par de variáveis não adjacentes \(A\) e \(B\) com um vizinho comum \(C\), verifique se \(C \in S_{AB}\). Se estiver contido, continue, caso contrário, oriente \(A \rightarrow C \leftarrow B\).
No gráfico parcialmente direcionado resultante, oriente o máximo possível de arestas não direcionadas, sujeito a duas condições: (i) a orientação não deve criar uma nova estrutura head-to-head; e (ii) a orientação não deve criar um ciclo direcionado.
Assim, o algoritmo PC inicia com um grafo completo não direcionado e exclui as arestas recursivamente com base nas decisões baseadas em independência condicional. A Figura 4.1 ilustra como o funcionamento do algoritmo PC para quatro variáveis, onde (i) apresenta o grafo verdadeiro, (ii) o início do algoritmo através de um grafo não direcionado e totalmente conectado, (iii) a aresta \(X_1 - X_2\) é removida porque \(X_1 \perp X_2\), (iv) as arestas $X_1 − X_4 $ e \(X_2 − X_4\) são removidas devido \(X_1 \perp X_4 | X_3\) e \(X_2 \perp X_4 | X_3\), (v) apresenta o grafo parcialmente conectado após encontrar as estruturas head-to-head. Finalmente, (vi) apresenta o grafo final após orientação dos demais arcos.
Basicamente, o algoritmo PC encontra o esqueleto da rede e, após isso, identifica as estruturas head-to-head baseando nas propriedades de d-separação. Se as decisões de independência condicional estiverem corretas para uma amostra suficientemente grande, o algoritmo PC tende a convergir para a verdadeira Classe de Equivalência de Markov (Glymour, Zhang, e Spirtes 2019).
Figura 4.1 Estimação de estrutura: Ilustração do Algoritmo PC. Adaptado de Glymour, Zhang, e Spirtes (2019)
Algoritmo PC-estável
Este algoritmo, proposto por Colombo e Maathuis (2014), lida com a dependência da ordenação de variáveis do algoritmo de PC. Os mesmos autores mostraram que a ordenação de variáveis para dados de baixa dimensão não é um grande problema, mas para dados de alta dimensão, pode trazer resultados bastante variados para a estrutura estimada. Além disso, algumas modificações que poderiam remover parte ou toda a dependência da ordenação de variáveis no algoritmo de PC foram propostas. As modificações do algoritmo foram realizadas ao logo da fase de estimação do esqueleto da rede (???).
4.3 Métodos baseados em pontuação
Métodos de estimação baseados em pontuação consistem em atribuir uma pontuação a cada estrutura candidata. De uma forma geral, essa pontuação mede o quão bem a rede bayesiana descreve o conjunto de dados. Assumindo que \(G=\{\mathbf{X},E\}\) denota a estrutura de rede e \(D=\{\mathbf{x}_i\}^{n}_{i=1}\) o conjunto de dados observado, a pontuação é representada pela probabilidade
\[ s(G| D) = P (G | D)=\frac{P (D | G) P (G)} {P (D)} \propto P (D | G)=L(G|D). \]
Através do uso do teorema de Bayes, nota-se que \(P(D)\) não depende dos dados e, ignorando \(P(G)\), o que é equivalente a assumir uma priori uniforme sobre as estruturas, nota-se que \(s(G|D)\) baseia-se na função de verossimilhança de \(G\). Um algoritmo baseado em pontuação tem como objetivo maximizar tal função de pontuação.
Entretanto, todas as soluções disponíveis tendem a se basear em um princípio comum conhecido como parcimônia ou navalha de Occam (Russell e Norvig 2010), o qual considera que devemos preferir modelos mais simples ao invés de modelos mais complexos.
Usando a intuição de complexidade do modelo, podemos definir uma classe comum de medidas de pontuação,
\[s{(G|D)} = l(G|D) − \phi(n) \times ||G||,\]
sendo o primeiro componente \(l(G | D)\) a função de log-verossimilhança. O segundo componente, $ (n) ||G|| $, é um termo de penalidade que favorece modelos mais simples, ou seja, modelos com menos parâmetros, sendo \(||G||\) o número de parâmetros em \(G\). Além disso, \(\phi (n) ≥ 0\) é uma função do tamanho do conjunto de dados \(n\) que controla o peso geral da penalidade.
Desta forma, existem diferentes tipos de medidas bayesianas e não bayesianas de pontuação que podem ser utilizadas e a escolha é realizada previamente. Algumas destas medidas serão exibidas ao final desta seção. Antes disso, expomos como se dá o processo de maximização destas medidas para uma rede bayesiana.
O procedimento de estimação de estrutura para os algoritmos baseado em pontuação constitui em uma busca recursiva por conexões, seguida do cálculo de uma função objetivo que mede o grau ajuste da rede aos dados (Beretta et al. 2018). A repetição recursiva desses passos visa encontrar a melhor estrutura \(g*\) em \(G\) a qual maximize a função objetivo \(s(G|D)\).
Para isso, o algoritmo realiza uma busca via greedy search no espaço de possíveis grafos \(G\) a fim de encontrar uma estrutura que não cause perda em \(s(G|D)\) em relação a opção anterior . Algoritmos amplamente utilizados são o subida de encosta (hill-climbing) e o busca tabu (tabu search):
Subida de encosta: algoritmo construído via greedy-search que explora o espaço dos grafos acíclicos direcionados por meio das operações de adição, remoção e reversão de um único arco. Este método é chamado de algoritmo ganancioso pois move-se, a cada passo, para um bom estado vizinho de maneira oportunista (Russell e Norvig 2010). Comumente é implementado com reinicializações aleatórias para evitar ótimos locais (Gámez, Mateo, e Puerta 2011).
Busca Tabu (Glover 1986): algoritmo de subida de encosta modificado para minimizar a parada em ótimos locais, permitido que durante sua busca seja selecionada uma rede que diminui a pontuação minimamente. Assim, este algoritmo limita os locais que já foram testados anteriormente, na lista tabu, os quais não podem ser revisitados por interações pré-definidas. Além disso, quando encontra um máximo, realiza mais algumas iterações para garantir que tenha atingido um máximo global (Scutari, Graafland, e Gutiérrez 2019).
Os algoritmos greedy-search seguem uma heurística direcionada a fazer a escolha ideal localmente, a cada passo, na esperança de encontrar um ótimo global. Em muitos problemas, essa estratégia não produz em geral uma solução ótima, mas, ainda assim, pode produzir soluções localmente ótimas que se aproximam de uma solução ótima global em um tempo razoável (Gámez, Mateo, e Puerta 2011).
Figura 4.2 Algoritmo subida de encosta: Adaptado de Russell e Norvig (2010).
Para o caso de estimação de estrutura de redes bayesianas, o passo principal do algoritmo consiste realizar operações de adição, remoção ou reversão de arco, tornando como nova candidata a estrutura que gera um aumento na pontuação. O processo termina quando não há nenhuma alteração de único arco que aumente a pontuação. O pseudocódigo do algoritmo subida de consta é exibo a seguir, bem como ilustrado genericamente através da Figura 4.3 (Margaritis 2003).
Pseudocódigo do algoritmo subida de encosta
\(E \leftarrow \emptyset\)
\(\theta \leftarrow\) TPC \((E,D)\)
\(g \leftarrow\{\mathbf{X},E,\theta\}\)
\(s(g|D)=-\infty\)
Repetir:
maxscore \(\leftarrow\) score;
para cada par de variáveis \((X,Y)\), faça:
b1. para cada \(E'\in\left\{ g\cup\{X\rightarrow Y\},g-\{X\rightarrow Y\},g-\{X\rightarrow Y\}\cup\{X\leftarrow Y\}\right\}\)
\(\theta' \leftarrow\) TPC \((E',D)\)
\(g' \leftarrow (\mathbf{X},E',\theta')\)
\(s_{novo} \leftarrow s(g'|D)\)
se \(s_{novo} > s(g'|D)\) entao \(g \leftarrow g'\)
Enquanto \(s_{novo} > s_{max}\)
Retorne \(g\)
4.3 Estimação de estrutura: abordagem baseada em pontuação. Adaptada de Margaritis (2003)
4.3.1 Pontuação AIC e BIC
Quando o peso da penalidade \(\phi(n)\) é uma constante, sendo independente de \(n\), obtemos uma pontuação em que a complexidade do modelo é uma questão secundária. Neste caso, a complexidade do modelo só será utilizada para distinguir entre modelos que têm termos de log-verossimilhança relativamente iguais. Para \(\phi(n)=1\), essa medida de pontuação é conhecida como critério de informação de Akaike (AIC).
Outra escolha comum do termo de penalidade é \(\phi(n) = \frac{\text{log}_2 n}{2}\), o que leva a um termo de penalidade mais influente. Esta medida é conhecida como critério de informação Bayesiano (BIC).
Isto é,
\[s_{AIC}(\textit{G}| D) = l(G|D) − ||G||\]
e
\[s_{BIC}(\textit{G}| D) = l(G|D) − \frac{\text{log}_2(n)}{2} ||G||.\]
4.3.2 Pontuação K2
Proposta por Cooper e Herskovits (1992), essa pontuação bayesiana com uma adaptação na definição dos hiperparâmetros \(\alpha_{ijk}\) iguais a 1. Essa atribuição é o mesmo que assumir uma distribuição uniforme a priori para o valor de cada parâmetro (desconhecimento prévio quanto ao seu valor). A pontuação K2 é apresentada a seguir.
\[s_{K2}(\textit{G}| D) = \prod_{i=1}^{p} \prod_{j = 1}^{q_{i}} \frac{\Gamma(r_{i})}{\Gamma(r_{i} + n_{ij})} \prod_{k = 1}^{r_i} \Gamma( 1 + n_{ijk}),\]
onde \(p\) é o número de variáveis no modelo, \(r_i\) é o número de estados de \(X_i\), \(q_i\) é o número de diferentes valores que os pais de \(X_i\) podem assumir em conjunto, \(n_{ijk}\) é o número de vezes que \(X_i\) assumiu \(k\)-ésimo valor quando os pais de \(X_i\) assumiram seu valor de \(j\)-ésimo valor. Além disso, \(n_{ij}=\sum_{k = 1}^{r_i}n_{ijk}\).
4.3.3 Pontuação BDeu
Considerando a pontuação anterior, quando \(\alpha_{ijk}=\frac{\alpha}{r_i q_i}\), e \(\alpha_i= \ \alpha\) para todos \(X_i\), sendo que \(\alpha\) representa um tamanho de amostra equivalente a priori, esta pontuação é chamada pontuação do Bayesiano Dirichlet Equivalente com Uniforme a priori (BDeu - Bayesian-Dirichlet equivalent uniform) (Heckerman, Geiger, e Chickering 1995)(Zeng, Jiang, e Neapolitan 2016) . A pontuação BDeu é dada por.
\[s_{BDeu}(G|D) = \prod_{i=1}^{p} \prod_{j = 1}^{q_{i}} \frac{\Gamma(\frac{\alpha}{q_i})}{\Gamma(\frac{\alpha}{q_i} + n_{ij})} \prod_{k = 1}^{r_i} \frac{\Gamma(\frac{\alpha}{r_i q_i} + n_{ijk})}{\Gamma(\frac{\alpha}{r_i q_i})},\]
A pontuação BDeu tem apenas um parâmetro e é a única pontuação deste caso que é equivalente a pontuação (Chickering 1995). Isso significa que é a única pontuação do caso Multinomial-Dirichlet que assume o mesmo valor para DAGs na mesma classe de equivalência (codificando a mesma distribuição). Devido a este fato, quando os arcos recebem uma interpretação causal, a pontuação BDeu é preferencial (Pearl 2009)(Zeng, Jiang, e Neapolitan 2016).
As pontuações K2 e BDEU podem ser otimizadas pelo uso da função logarítmica, melhorando a velocidade do tempo de execução (Cooper e Herskovits 1992).
4.4 Comentários adicionais
Através da opinião de especialistas e para reduzir o número de DAGs candidatos e auxiliar ambos os tipos de algoritmos para estimação de estrutura, existe a possibilidade de impor restrições durante o processo de estimação. Tais restrições são conhecidas como lista branca e lista negra. A primeira se refere a conexões consideradas fixas durante todo o processo de estimação, a segunda se refere a conexões que nunca serão visitadas durante o processo de estimação.
Existem diversos outros métodos de estimação tanto para a classe dos métodos baseados em restrição quanto para a classe dos métodos baseados em pontuação. Além disso, outros métodos de busca em conjunto com as medidas de pontuação adotada. Este texto apenas aborda as metodologias mais historicamente utilizadas. Glymour, Zhang, e Spirtes (2019) e Scutari, Graafland, e Gutiérrez (2019) trazem uma visão geral do estado da arte sobre métodos de estimação de estrutura em redes bayesianas.
4.5 Estimação de estrutura usando R
require(bnlearn)
data(learning.test)
dag = model2network("[A][C][F][B|A][D|A:C][E|B:F]")
pc.est <- pc.stable(learning.test)
k2.est <- hc(learning.test,score="k2")
score(k2.est,learning.test, type = "k2")## [1] -23957.68bic.est <- hc(learning.test)
score(k2.est,learning.test, type = "bic")## [1] -24006.73bdeu.est <- hc(learning.test,score="bde")
score(k2.est,learning.test, type = "bde")## [1] -24028.09par(mfrow=c(1,5))
graphviz.compare(dag,pc.est,k2.est,
bic.est,bdeu.est,
main=c("Real","PC","K2",
"BIC","BDE"))
#BiocManager::install("RBGL")
bn.aju <- bn.fit(bdeu.est,learning.test)
par(mfrow=c(1,1))
graphviz.chart(bn.aju, layout = "dot",type="barprob",draw.levels =TRUE,bar.col='tomato',grid=TRUE)
Referências
Beretta, Stefano, Mauro Castelli, Ivo Gonçalves, Roberto Henriques, e Daniele Ramazzotti. 2018. «Learning the structure of Bayesian Networks: A quantitative assessment of the effect of different algorithmic schemes». Complexity 2018.
Chickering, DM. 1995. «A transformational characterization of equivalent Bayesian network structures». Proceedings of the 11th Conference on Uncertainty in Artificial Intelligence, 87–98.
Colombo, Diego, e Marloes H Maathuis. 2014. «Order-independent constraint-based causal structure learning». The Journal of Machine Learning Research 15 (1): 3741–82.
Cooper, Gregory F, e Edward Herskovits. 1992. «A Bayesian method for the induction of probabilistic networks from data». Machine learning 9 (4): 309–47.
Gámez, José A, Juan L Mateo, e José M Puerta. 2011. «Learning Bayesian networks by hill climbing: efficient methods based on progressive restriction of the neighborhood». Data Mining and Knowledge Discovery 22 (1-2): 106–48.
Glover, Fred. 1986. «Future paths for integer programming and links to artificial intelligence». Computers & operations research 13 (5): 533–49.
Glymour, Clark, Kun Zhang, e Peter Spirtes. 2019. «Review of causal discovery methods based on graphical models». Frontiers in genetics 10: 524.
Heckerman, David, Dan Geiger, e David M Chickering. 1995. «Learning Bayesian networks: The combination of knowledge and statistical data». Machine learning 20 (3): 197–243.
Koller, Daphne, e Nir Friedman. 2009. Probabilistic graphical models: principles and techniques. MIT press.
Margaritis, Dimitris. 2003. «Learning Bayesian network model structure from data». Carnegie-Mellon Univ Pittsburgh Pa School of Computer Science.
Nagarajan, Radhakrishnan, Marco Scutari, e Sophie Lèbre. 2013. «Bayesian networks in r». Springer 122: 125–27.
Pearl, Judea. 2009. «Introduction to probabilities, graphs, and causal models». Causality: models, reasoning and inference, 1–40.
Pearl, J, e TS Verma. 1991. «A theory of inferred causation. 1991». Em 2-nd Conference on the Principles of Knowledge Representation and Reasoning, Cambridge, MA.
Russell, Stuart, e Peter Norvig. 2010. «Artificial intelligence: a modern approach».
Scutari, Marco. 2010. «Learning Bayesian networks with the bnlearn R package». Journal of Statistical Software 35 (3): 1–22.
Scutari, Marco, Catharina Elisabeth Graafland, e José Manuel Gutiérrez. 2019. «Who learns better Bayesian network structures: Accuracy and speed of structure learning algorithms». International Journal of Approximate Reasoning 115: 235–53.
Spirtes, Peter, Clark N Glymour, e Richard Scheines. 2000. Causation, prediction, and search. MIT press.
Uusitalo, Laura. 2007. «Advantages and challenges of Bayesian networks in environmental modelling». Ecological modelling 203 (3-4): 312–18.
Zeng, Zexian, Xia Jiang, e Richard Neapolitan. 2016. «Discovering causal interactions using Bayesian network scoring and information gain». BMC bioinformatics 17 (1): 221.
Zhang, Xiujun, Xing-Ming Zhao, Kun He, Le Lu, Yongwei Cao, Jingdong Liu, Jin-Kao Hao, Zhi-Ping Liu, e Luonan Chen. 2012. «Inferring gene regulatory networks from gene expression data by path consistency algorithm based on conditional mutual information». Bioinformatics 28 (1): 98–104.