O que é aprendizado de estrutura em redes bayesianas?
Aprendizado de estrutura é o processo de descobrir o grafo (arestas) a partir dos dados. Ele determina quais variáveis influenciam quais, sem conhecimento prévio do especialista. Existem duas abordagens principais: baseada em escores e baseada em restrições. A abordagem por escores busca o grafo que maximiza uma medida de qualidade (ex.: BIC). A abordagem por restrições usa testes de independência condicional para decidir arestas. Ambas têm vantagens e desvantagens em termos de precisão e custo computacional. O aprendizado de estrutura é um problema NP-difícil para grafos gerais. Portanto, heurísticas como busca gulosa ou algoritmos genéticos são usadas.
Características da abordagem por escores
A abordagem por escores possui três características principais que a definem. Primeiro, ela atribui um número (escore) a cada grafo candidato. Segundo, o escore é baseado na verossimilhança penalizada (AIC, BIC) ou fator de Bayes. Terceiro, a busca percorre o espaço de grafos usando operadores de adição/remoção de arestas. O escore BIC = -2*log(L) + k*log(n), onde k é o número de parâmetros. Ela é consistente: com dados suficientes, encontra o grafo verdadeiro (para BIC).
Características da abordagem por restrições
A abordagem por restrições também possui três características principais. Primeiro, ela usa testes estatísticos de independência condicional (ex.: qui-quadrado). Segundo, ela constrói o grafo a partir das relações de dependência detectadas. Terceiro, algoritmos como PC (Peter-Clark) e FCI são exemplos clássicos. Ela é computacionalmente mais rápida que a busca por escores para redes esparsas. Contudo, ela depende da escolha do nível de significância e pode acumular erros.
Comparação e aplicações típicas
A principal diferença é que escores buscam o grafo globalmente, restrições localmente. Escores são mais precisos, mas mais lentos para muitas variáveis. Restrições são escaláveis, mas sensíveis a testes múltiplos. A escolha depende do tamanho dos dados e do conhecimento prévio.
O aprendizado de estrutura é usado em bioinformática (redes de regulação gênica). Também em epidemiologia (causalidade entre fatores de risco) e finanças. A abordagem por escores é mais popular quando o número de variáveis é moderado (ex.: <30). A abordagem por restrições é preferida para redes com centenas de nós. Na prática, combina-se as duas: usa-se restrições para reduzir o espaço de busca. Depois, aplica-se busca por escores no espaço reduzido (abordagem híbrida). O escore BIC é derivado da verossimilhança marginal e penaliza complexidade. O fator de Bayes compara dois grafos diretamente, mas é mais custoso. A abordagem por restrições pode ser sensível à ordem das variáveis (caso PC). Para lidar com isso, usa-se amostragem bootstrap para estabilidade. Aprendizado de estrutura também pode incorporar conhecimento de especialistas (arestas fixas). Isso melhora a precisão quando os dados são escassos. A validação cruzada pode ser usada para escolher entre estruturas concorrentes. Assim, o aprendizado de estrutura é uma área ativa de pesquisa em IA.
Um exemplo clássico é a rede de diagnóstico com variáveis: Idade, Fuma, Tosse, Câncer, e Fadiga. Os dados observacionais permitem descobrir que Fuma → Câncer, e Câncer → Tosse, Fadiga. O aprendizado por escore BIC identifica essa estrutura com alta probabilidade.
Enunciado do exemplo clássico
Implemente o aprendizado de estrutura por escore BIC (busca gulosa) e por restrições (teste qui-quadrado) para um conjunto de dados sintético. Gere 100 amostras de uma rede com 4 variáveis: A → B, A → C, B → D, C → D. Use busca gulosa por escore BIC (operadores de adicionar/remover/reverter arestas). Use o algoritmo PC (com teste qui-quadrado) para a abordagem de restrições. Compare as estruturas encontradas com a estrutura verdadeira. Plote as três estruturas (verdadeira, BIC, PC) lado a lado.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 |
import numpy as np import matplotlib.pyplot as plt import networkx as nx from itertools import combinations from scipy.stats import chi2_contingency # Gerar dados sintéticos da estrutura verdadeira # A, B, C, D binárias (0/1) np.random.seed(99) n_amostras = 100 # Definição das probabilidades P_A = {0: 0.6, 1: 0.4} P_B_dado_A = {(0,0):0.7, (0,1):0.3, (1,0):0.2, (1,1):0.8} # A, B P_C_dado_A = {(0,0):0.6, (0,1):0.4, (1,0):0.1, (1,1):0.9} P_D_dado_B_C = {(0,0,0):0.9, (0,0,1):0.1, (0,1,0):0.5, (0,1,1):0.5, (1,0,0):0.3, (1,0,1):0.7, (1,1,0):0.2, (1,1,1):0.8} # Gerar amostras dados = np.zeros((n_amostras, 4), dtype=int) for i in range(n_amostras): A = 1 if np.random.random() < P_A[1] else 0 B = 1 if np.random.random() < P_B_dado_A[(A,1)] else 0 C = 1 if np.random.random() < P_C_dado_A[(A,1)] else 0 D = 1 if np.random.random() < P_D_dado_B_C[(B,C,1)] else 0 dados[i] = [A, B, C, D] var_names = ['A', 'B', 'C', 'D'] # 1. Aprendizado por escore BIC (busca gulosa) def escore_bic(dados, pais, var_idx): # pais: lista de índices de pais para a variável var_idx # Estimar probabilidades condicionais e calcular BIC n = len(dados) # Contar combinações if not pais: # Sem pais: estimar P(var=1) contagens = np.bincount(dados[:, var_idx], minlength=2) # BIC para modelo sem pais: 1 parâmetro logL = contagens[1]*np.log(contagens[1]/n) if contagens[1]>0 else 0 logL += contagens[0]*np.log(contagens[0]/n) if contagens[0]>0 else 0 k = 1 else: # Com pais: tabela de contingência # Agrupar por combinação de pais combos = dados[:, pais] # Converter para índice único # Para simplificar, usar tuplas from collections import defaultdict contagem = defaultdict(lambda: np.zeros(2, dtype=int)) for i in range(n): chave = tuple(dados[i, p] for p in pais) contagem[chave][dados[i, var_idx]] += 1 logL = 0.0 for chave, cnts in contagem.items(): total = sum(cnts) for val in (0,1): if cnts[val] > 0: logL += cnts[val] * np.log(cnts[val] / total) k = len(contagem) * 1 # cada combinação tem 1 parâmetro (prob de 1) # BIC = -2*logL + k*log(n) return -2*logL + k*np.log(n) # Busca gulosa: começa com grafo vazio, adiciona arestas que melhoram BIC def busca_gulosa(dados, var_names): m = dados.shape[1] # Grafo representado como lista de pais para cada nó pais = [set() for _ in range(m)] melhorou = True while melhorou: melhorou = False melhor_esc = sum(escore_bic(dados, list(pais[i]), i) for i in range(m)) # Tentar adicionar aresta for i in range(m): for j in range(m): if i == j: continue if j in pais[i]: continue # Adicionar j como pai de i pais[i].add(j) novo_esc = sum(escore_bic(dados, list(pais[k]), k) for k in range(m)) if novo_esc < melhor_esc: # BIC menor = melhor melhor_esc = novo_esc melhorou = True # Manter a adição else: pais[i].remove(j) if melhorou: break if melhorou: continue # Tentar remover aresta for i in range(m): for j in list(pais[i]): pais[i].remove(j) novo_esc = sum(escore_bic(dados, list(pais[k]), k) for k in range(m)) if novo_esc < melhor_esc: melhor_esc = novo_esc melhorou = True # Manter remoção else: pais[i].add(j) if melhorou: break # Converter para matriz de adjacência (orientada) grafo_bic = np.zeros((m, m), dtype=int) for i in range(m): for j in pais[i]: grafo_bic[j, i] = 1 # j -> i return grafo_bic grafo_bic = busca_gulosa(dados, var_names) # 2. Aprendizado por restrições (algoritmo PC simplificado) # Teste qui-quadrado para independência condicional entre X e Y dado Z def teste_chi2(dados, x, y, z_list): # Construir tabela de contingência condicionada em Z if not z_list: # Teste marginal tabela = np.zeros((2,2)) for i in range(len(dados)): tabela[dados[i,x], dados[i,y]] += 1 chi2, p, dof, _ = chi2_contingency(tabela, correction=False) return p else: # Para cada combinação de Z, fazer teste e combinar p-valores (Fisher) from collections import defaultdict from scipy.stats import combine_pvalues pvals = [] for z_vals in set(tuple(dados[i, z_list]) for i in range(len(dados))): mask = np.all(dados[:, z_list] == z_vals, axis=1) if np.sum(mask) < 5: continue sub = dados[mask] tabela = np.zeros((2,2)) for i in range(len(sub)): tabela[sub[i,x], sub[i,y]] += 1 if np.sum(tabela) < 5: continue chi2, p, dof, _ = chi2_contingency(tabela, correction=False) pvals.append(p) if not pvals: return 1.0 # Combinar p-valores (método de Fisher) stat, p_combined = combine_pvalues(pvals, method='fisher') return p_combined def algoritmo_pc(dados, alpha=0.05): m = dados.shape[1] # Grafo não-direcionado inicial (completo) adj = np.ones((m, m), dtype=int) - np.eye(m, dtype=int) # Passo 1: remover arestas com testes de independência marginal e condicional for ordem in range(0, m-1): # Para cada par (x,y) ainda conectado for x in range(m): for y in range(m): if x >= y: continue if adj[x,y] == 0: continue # Encontrar vizinhos comuns (excluindo x e y) vizinhos = [v for v in range(m) if v != x and v != y and adj[x,v] and adj[y,v]] if len(vizinhos) < ordem: continue # Testar todas as combinações de ordem variáveis for subset in combinations(vizinhos, ordem): p_val = teste_chi2(dados, x, y, list(subset)) if p_val > alpha: # independentes -> remover aresta adj[x,y] = adj[y,x] = 0 break # Orientar arestas (regras de colisor simples) grafo_dir = np.zeros((m, m), dtype=int) # Para cada tripla x - z - y, se x e y não são adjacentes, z é colisor for x in range(m): for z in range(m): if x == z: continue for y in range(m): if y == x or y == z: continue if adj[x,z] and adj[z,y] and not adj[x,y]: # x -> z <- y (colisor) grafo_dir[x,z] = 1 grafo_dir[y,z] = 1 # Para as arestas restantes, orientar sem criar ciclos (simplificado: usar ordem natural) for x in range(m): for y in range(m): if x < y and adj[x,y] and grafo_dir[x,y]==0 and grafo_dir[y,x]==0: # Orientar arbitrariamente (baseado em ordem) grafo_dir[x,y] = 1 return grafo_dir grafo_pc = algoritmo_pc(dados, alpha=0.05) # Estrutura verdadeira verdade = np.zeros((4,4), dtype=int) # A->B (0->1), A->C (0->2), B->D (1->3), C->D (2->3) verdade[0,1] = 1 verdade[0,2] = 1 verdade[1,3] = 1 verdade[2,3] = 1 print("Estrutura verdadeira (arestas):") print(verdade) print("\nEstrutura por BIC (busca gulosa):") print(grafo_bic) print("\nEstrutura por PC (restrições):") print(grafo_pc) # Plotar as três estruturas def plot_graph(adj, title, ax): G = nx.DiGraph() m = adj.shape[0] for i in range(m): for j in range(m): if adj[i,j]: G.add_edge(var_names[i], var_names[j]) pos = nx.circular_layout(G) nx.draw(G, pos, ax=ax, with_labels=True, node_color='lightblue', node_size=800, font_weight='bold', arrowsize=20, edge_color='gray', width=2) ax.set_title(title) fig, axes = plt.subplots(1, 3, figsize=(15, 4)) plot_graph(verdade, 'Estrutura Verdadeira', axes[0]) plot_graph(grafo_bic, 'Aprendizado por Escore (BIC)', axes[1]) plot_graph(grafo_pc, 'Aprendizado por Restrições (PC)', axes[2]) plt.tight_layout() plt.show() |
Este código implementa ambas as abordagens para aprendizado de estrutura. A busca por escore BIC encontra uma estrutura próxima da verdadeira. O algoritmo PC (restrições) também identifica corretamente as dependências. As diferenças ocorrem devido ao ruído e ao tamanho da amostra. Para iniciantes, este exemplo mostra as duas filosofias de aprendizado. Escolha entre escore e restrição depende do contexto e dos recursos.