Métodos de Tomada de Decisão

Conexão com as Aulas 1 e 2

• Na Aula 1 revisamos probabilidade condicional, Teorema de Bayes, sensibilidade, especificidade e VPP/VPN
• Hoje generalizamos o Teorema de Bayes: de duas variáveis (doença, teste) para um conjunto arbitrário de variáveis
• A referência principal de hoje é o material do Prof. Anderson Ara (UFPR), Redes Bayesianas e Aplicações, complementado pelo livro de Scutari & Denis
• O foco de hoje é conceitual: fundamentos, classificadores e aprendizado de estrutura de redes bayesianas

Origem Histórica: Judea Pearl

• Redes bayesianas surgiram no final da década de 1980, propostas por Judea Pearl, filósofo e cientista da computação
• Objetivo original: facilitar predição, indução e dedução em sistemas de inteligência artificial
• Também chamadas de redes de crença ou grafos de dependência probabilística
• Combinam Teoria de Grafos, Teoria de Probabilidades, Ciência da Computação e Estatística
• Aplicações em diagnóstico de falhas, agricultura, cibersegurança, mudanças climáticas e, especialmente, diagnóstico médico

Vantagens das Redes Bayesianas

Segundo Uusitalo (2007) e Chen & Pollino (2012), as redes bayesianas se destacam por:

• Adequação para conjuntos de dados pequenos e incompletos
• Possibilidade de aprendizagem estrutural a partir dos dados
• Combinação de diferentes fontes de conhecimento (dados + opinião de especialista)
• Tratamento explícito da incerteza e suporte direto à análise de decisão
• Descoberta de conhecimento, síntese de dados e identificação de lacunas

Grafos Acíclicos Direcionados (DAG)

• Nó: cada variável do domínio (ex.: fator de risco, sintoma, diagnóstico)
• Arco direcionado (\(X \rightarrow Y\)): \(Y\) depende diretamente de \(X\); \(X\) é pai, \(Y\) é filho
• Caminho: sequência de arcos ligando dois nós, mesmo que não diretamente
• Acíclico: nenhum caminho pode retornar a um nó já visitado

Redes Bayesianas Discretas e Contínuas

• Dados multinomiais: distribuições conjuntas, marginais e condicionais tratadas como multinomiais, representadas em tabelas — são as redes bayesianas discretas (o caso mais comum)
• Dados normais multivariados: a conjunta é normal multivariada, e as condicionais são variáveis normais univariadas ligadas por combinações lineares — chamadas redes bayesianas gaussianas
• Métodos híbridos (redes gaussianas condicionais) combinam variáveis discretas e contínuas, mas não serão aprofundados aqui

Exemplo Clínico: Triagem de Dor Torácica

• \(FR \rightarrow D\): fatores de risco influenciam a chance de SCA
• \(D \rightarrow ECG\) e \(D \rightarrow Tn\): a doença influencia ambos os exames, mas os exames não se influenciam diretamente

Diagrama do DAG Clínico

Representação Probabilística: Fatorando a Conjunta

\[Pr(FR, D, ECG, Tn) = Pr(FR)\, Pr(D \mid FR)\, Pr(ECG \mid D)\, Pr(Tn \mid D)\]

• O DAG diz exatamente como fatorar a distribuição conjunta: um termo por variável, condicional aos seus pais
• Sem essa estrutura, precisaríamos de uma tabela conjunta com \(2^4 = 16\) combinações — 15 parâmetros livres
• Com a fatoração: \(2 + 2 + 2 + 2 = 8\) parâmetros — metade, e a economia cresce exponencialmente com mais variáveis

Tabelas de Probabilidade Condicional (CPT)

• CPT: tabela que especifica \(Pr(\text{variável} \mid \text{pais})\) para cada combinação de estados dos pais
• Variáveis sem pais (raízes do DAG): tabela unidimensional — distribuição marginal
• Variáveis com pais: uma coluna para cada combinação de estados dos pais — cada coluna soma 1
• DAG + conjunto de CPTs = rede bayesiana completamente especificada

CPTs do Exemplo Clínico em R

library(bnlearn)

dag_clin <- model2network("[FR][D|FR][ECG|D][Tn|D]")

FR.prob <- array(c(0.30, 0.70), dim = 2, dimnames = list(FR = c("sim", "nao")))
D.prob  <- array(c(0.35, 0.65, 0.05, 0.95), dim = c(2, 2),
                  dimnames = list(D = c("sim", "nao"), FR = c("sim", "nao")))
ECG.prob <- array(c(0.75, 0.25, 0.10, 0.90), dim = c(2, 2),
                    dimnames = list(ECG = c("sim", "nao"), D = c("sim", "nao")))
Tn.prob  <- array(c(0.85, 0.15, 0.06, 0.94), dim = c(2, 2),
                    dimnames = list(Tn = c("sim", "nao"), D = c("sim", "nao")))

bn_clin <- custom.fit(dag_clin, list(FR = FR.prob, D = D.prob, ECG = ECG.prob, Tn = Tn.prob))
nparams(bn_clin)

[1] 7

Independência Condicional e Separação Gráfica

• Duas variáveis sem caminho aberto entre si são condicionalmente independentes
• O DAG permite ler diretamente relações de (in)dependência, sem calcular nada numericamente
• Conceito-chave: d-separação (separação direcional) — generaliza “bloquear um caminho” no grafo
• Se todo caminho entre \(X\) e \(Y\) é bloqueado por \(Z\): \(X \perp\!\!\!\perp Y \mid Z\)

As Três Conexões Fundamentais (1/2): Serial e Divergente

• Serial (\(FR \rightarrow D \rightarrow ECG\)): condicionar no nó do meio bloqueia o caminho
• Divergente (\(ECG \leftarrow D \rightarrow Tn\)): condicionar no “pai comum” também bloqueia — é exatamente o nosso exemplo clínico

As Três Conexões Fundamentais (2/2): Convergente (V-estrutura)

• Convergente (\(A \rightarrow E \leftarrow S\)): o oposto das anteriores
• Sem condicionar em \(E\): \(A\) e \(S\) são independentes
• Condicionando em \(E\) (ou descendente): \(A\) e \(S\) tornam-se dependentes
• Sem arco entre os pais: chamada de v-estrutura, essencial para aprendizado de estrutura (Bloco D)

d-Separação em R: dsep()

dsep(dag_clin, x = "ECG", y = "Tn")

[1] FALSE

dsep(dag_clin, x = "ECG", y = "Tn", z = "D")

[1] TRUE

dsep(dag_clin, x = "FR",  y = "ECG")

[1] FALSE

dsep(dag_clin, x = "FR",  y = "ECG", z = "D")

[1] TRUE

Síntese do Bloco A

• Uma rede bayesiana = DAG (estrutura) + CPTs (distribuições locais)
• O DAG permite fatorar a conjunta e ler independências via d-separação
• As três conexões fundamentais — serial, divergente, convergente — são a base de toda a teoria de redes bayesianas
• Próximo passo: como estimamos os parâmetros dessas CPTs a partir de dados? É o tema do Bloco B, inferência bayesiana

Inferência por Evidências: Retomando o Conceito

• Em redes bayesianas, “inferência” é também chamada atualização de crença (belief updating)
• Mecanismo para calcular a distribuição a posteriori de uma ou mais variáveis, dado um conjunto de evidências — variáveis observadas ou assumidas conhecidas
• Existem métodos exatos (via árvore de junção, pacote gRain) e métodos aproximados, por simulação (cpquery), quando a rede é grande

library(gRain)
junction <- compile(as.grain(bn_clin))
jev <- setEvidence(junction, nodes = c("ECG", "Tn"), states = c("sim", "sim"))
querygrain(jev, nodes = "D")$D

Redes Bayesianas Causais: uma Nota de Cautela

• Um DAG por si só codifica dependência estatística, não causalidade
• Uma rede bayesiana causal exige suposições adicionais: suficiência causal (sem confundidores não observados) e fidelidade (as independências observadas refletem a estrutura, não coincidências)
• Sob essas suposições, arcos podem ser interpretados como relações causais diretas (Pearl, 1988; 2009)

O Teorema de Bayes para Parâmetros

\[p(\theta \mid x) = \frac{p(x \mid \theta)\, p(\theta)}{p(x)} = \frac{p(x \mid \theta)\, p(\theta)}{\displaystyle\int_{\Theta} p(x \mid \theta)\, p(\theta)\, d\theta}\]

\[\text{a posteriori} \;\propto\; \text{verossimilhança} \times \text{a priori}\]

Distribuições Conjugadas

• Priori conjugada: quando a distribuição a posteriori pertence à mesma família da priori
• Simplifica a atualização bayesiana para apenas um recálculo de hiperparâmetros — forma fechada, sem integrais complicadas
• Válido para a família exponencial: Binomial, Multinomial, Normal, Gama, Poisson, entre outras

Estimando a Sensibilidade de um Teste (Conjugação Binomial-Beta)

\[p(\theta) = \frac{\Gamma(\alpha_h + \alpha_t)}{\Gamma(\alpha_h)\,\Gamma(\alpha_t)}\, \theta^{\alpha_h - 1}(1-\theta)^{\alpha_t - 1} \quad\Rightarrow\quad \Theta \sim Beta(\alpha_h, \alpha_t)\]

• Priori: \(\theta \sim Beta(1,1)\) (uniforme, sem conhecimento prévio)
• Observamos \(n=20\) pacientes com a doença confirmada; o teste deu positivo em \(h=17\) deles, negativo em \(t=3\)
• Posteriori: \(\Theta \mid x \sim Beta(\alpha_h + h,\; \alpha_t + t) = Beta(18, 4)\)

alpha_h <- 1 + 17; alpha_t <- 1 + 3
media_post <- alpha_h / (alpha_h + alpha_t)
cat(sprintf("Sensibilidade estimada (média a posteriori): %.1f%%\n", media_post * 100))

Sensibilidade estimada (média a posteriori): 81.8%

Dados Multinomiais: a Distribuição de Dirichlet

• Generalização da Beta para \(k > 2\) categorias: \((\theta_1, \ldots, \theta_k)\) com \(\sum \theta_i = 1\)
• Priori conjugada: \(Dir(\alpha_1, \ldots, \alpha_k)\)
• Posteriori, após observar contagens \((x_1, \ldots, x_k)\):

\[\theta_1, \ldots, \theta_k \mid \mathbf{x}, \boldsymbol\alpha \;\sim\; Dir(\alpha_1+x_1,\, \ldots,\, \alpha_k+x_k), \qquad E(\theta_i) = \frac{\alpha_i + x_i}{\alpha_0 + n}\]

Síntese do Bloco B

• Inferência bayesiana trata parâmetros como variáveis aleatórias, com priori e posteriori
• Distribuições conjugadas (Beta-Binomial, Dirichlet-Multinomial) tornam a atualização uma simples soma de contagens
• É exatamente esse mecanismo que estima as CPTs de uma rede bayesiana discreta a partir de dados reais
• Com estrutura e parâmetros formalizados, podemos agora usar redes bayesianas para uma tarefa concreta: classificação — tema do Bloco C

A Tarefa de Classificação

• Seja \(\mathbf{X}\) um vetor de \(p\) variáveis explicativas (sintomas, exames) e \(Y\) uma variável categórica de saída (diagnóstico), \(y \in \{1, \ldots, c\}\)
• A classificação consiste em encontrar:

\[\underset{y}{\arg\max}\; P(Y=y \mid \mathbf{X}=\mathbf{x}) = \underset{y}{\arg\max}\; P(Y=y)\,\frac{P(\mathbf{X}=\mathbf{x}\mid Y=y)}{P(\mathbf{X}=\mathbf{x})}\]

• Como \(P(\mathbf{X}=\mathbf{x})\) não depende de \(y\): basta maximizar \(P(\mathbf{X}=\mathbf{x}, Y=y)\)

Classificadores Bayesianos como DAGs Especiais

• Um classificador bayesiano é uma rede bayesiana cujo propósito é prever \(Y\)
• São, por definição, DAGs com parâmetros estimados como no Bloco B
• Limitação: por causa da forma específica de fatoração, não têm interpretação causal direta sobre as demais variáveis
• Quatro classificadores clássicos: Naïve Bayes, TAN, KDB e AODE — cada um relaxando progressivamente uma suposição de independência

Medidas de Informação: Informação Mútua

Da Teoria da Informação (Shannon, 1948), mede a dependência entre duas variáveis:

\[I(X_i, X_j) = \sum_i \sum_j p(x_i, x_j) \log \frac{p(x_i, x_j)}{p(x_i)\, p(x_j)}\]

• Quantifica quanta informação uma variável carrega sobre a outra
• É não negativa e simétrica: \(I(X_i,X_j) = I(X_j,X_i)\)
• \(I(X_i,X_j) = 0\) se, e somente se, \(X_i\) e \(X_j\) forem independentes

Informação Mútua Condicional

\[I(X_i, X_j \mid Z) = \sum_z \sum_{x_i} \sum_{x_j} p(z)\, p(x_i,x_j\mid z) \log \frac{p(x_i,x_j\mid z)}{p(x_i\mid z)\, p(x_j\mid z)}\]

• Mede a informação mútua entre \(X_i\) e \(X_j\) condicionada a um terceiro vetor \(Z\) (tipicamente, a classe \(Y\))
• Também não negativa e simétrica
• No exemplo clínico: \(I(ECG, Tn \mid D)\) mede quanta dependência sobra entre os dois exames depois de saber o diagnóstico

Naïve Bayes (NB): o Classificador Ingênuo

• O mais simples e mais difundido dos classificadores bayesianos — arquitetura fixa, sem necessidade de estimar estrutura
• Pressuposto: independência condicional entre todas as variáveis de entrada, dado \(Y\)
• \(Y\) não tem pais; cada \(X_i\) tem apenas \(Y\) como pai

\[P(\mathbf{X}, Y) = P(Y) \prod_{i=1}^{p} P(X_i \mid Y)\]

Diagrama do Naïve Bayes

• \(Y\) é raiz e pai de todas as variáveis de entrada — estrutura em “estrela”
• Estimação de parâmetros: caso conjugado Multinomial-Dirichlet, conhecido como m-estimador (Cestnik, 1990)
• Caso contínuo: tipicamente \(X_i \mid y \sim N(\mu_{i\mid y}, \sigma^2_{i\mid y})\) — Naive Bayes Gaussiano

Tree-Augmented Naïve Bayes (TAN)

• Proposto por Friedman & Goldszmidt (1996): relaxa a independência do Naive Bayes
• \(Y\) continua pai de todos os \(X_i\), mas cada \(X_i\) pode depender de no máximo mais uma covariável \(X_j\)

\[P(\mathbf{X}, Y) = P(Y) \prod_{i=1}^{p} P(X_i \mid Y, X_j)\]

• É um caso especial de rede bayesiana, com \(\Pi_{X_i} = \{Y, X_j\}\)
• Usa o Algoritmo de Chow-Liu para decidir qual \(X_j\) escolher para cada \(X_i\)

K-Dependence Bayesian Classifier (KDB)

• Proposto por Sahami (1996): generaliza o TAN permitindo até \(K\) pais adicionais por variável (além da classe), \(K \in \{0, \ldots, p-1\}\)

\[P(\mathbf{X}, Y) = P(Y) \prod_{i=1}^{p} P(X_i \mid \Pi_{X_i}), \qquad 1 \le |\Pi_{X_i}| \le K\]

• \(K=0\): recupera o Naive Bayes
• \(K=1\): recupera o TAN
• \(K\) maior: mais dependências capturadas, ao custo de mais parâmetros

Averaged One-Dependence Estimator (AODE)

• Proposto por Webb, Boughton & Wang (2005): evita o custo computacional de seleção de modelo dos classificadores de uma dependência (TAN, 1-DB)
• Ideia: calcular a média de vários classificadores SPODE (SuperParent One-Dependence Estimator), cada um com uma variável diferente como “superpai”

\[P(\mathbf{X},Y) = P(Y)\,P(X_j\mid Y) \prod_{i=1}^{p-1} P(X_i \mid X_j, Y)\]

• É um classificador do tipo ensemble: agrega várias estruturas plausíveis em vez de escolher uma só

Comparando os Quatro Classificadores

sendo \(c\) o número de categorias de \(Y\), \(p\) o número de variáveis de entrada e \(v\) o número médio de estados por variável.

Síntese do Bloco C

• Classificadores bayesianos são DAGs com propósito preditivo, com \(Y\) sempre em posição especial
• Naive Bayes (independência total) → TAN (uma dependência extra, via Chow-Liu) → KDB (até \(K\) dependências) → AODE (ensemble de estruturas de uma dependência)
• Avaliação exige métricas robustas a desbalanceamento, como o MCC, especialmente em saúde
• Próxima pergunta: e quando não sabemos o DAG de antemão — como aprendê-lo dos dados? Tema do Bloco D

O Problema do Aprendizado de Estrutura

• A estimação de uma rede bayesiana envolve duas tarefas: aprender a estrutura \(G\) e aprender os parâmetros de \(P(\mathbf{X})\) (Bloco B)
• A estrutura pode vir de especialistas — e então só resta estimar parâmetros — ou ser aprendida dos dados
• Chickering (1995): encontrar a estrutura ótima é NP-difícil, mesmo restringindo cada nó a no máximo dois pais

Duas Famílias de Algoritmos

• Métodos baseados em restrição (constraint-based): usam testes de independência condicional para decidir quais arcos existem, construindo um DAG consistente com as d-separações observadas
• Métodos baseados em pontuação (score-based): atribuem uma pontuação a cada estrutura candidata e buscam maximizá-la via heurísticas de busca
• Uma terceira classe, híbrida, combina as duas — mas não é sistematicamente mais precisa (Scutari, Graafland & Gutiérrez, 2019)

Métodos Baseados em Restrição: Principais Algoritmos

Usam testes de independência condicional para decidir quais arcos existem, apoiando-se nas conexões fundamentais do Bloco A (especialmente as v-estruturas, único padrão que deixa uma “assinatura” detectável sem ambiguidade).

Métodos Baseados em Pontuação

• Atribuem uma pontuação \(s(G\mid D)\) a cada estrutura candidata, medindo o quão bem ela descreve os dados
• Via Teorema de Bayes: \(s(G\mid D) \propto P(D\mid G) = L(G\mid D)\) — a verossimilhança da estrutura
• Forma geral com penalização por complexidade (navalha de Occam):

\[s(G\mid D) = l(G\mid D) \;-\; \phi(n) \times \lVert G \rVert\]

sendo \(l(G\mid D)\) a log-verossimilhança, \(\lVert G \rVert\) o número de parâmetros, e \(\phi(n)\) o peso da penalização

Pontuações AIC e BIC

• \(\phi(n) = 1\) (constante): critério de informação de Akaike (AIC)

\[s_{AIC}(G\mid D) = l(G\mid D) - \lVert G \rVert\]

• \(\phi(n) = \dfrac{\log_2 n}{2}\): critério de informação Bayesiano (BIC) — penalização mais forte, cresce com \(n\)

\[s_{BIC}(G\mid D) = l(G\mid D) - \frac{\log_2(n)}{2}\, \lVert G \rVert\]

Pontuações Bayesianas: K2 e BDeu

Pontuação K2 (Cooper & Herskovits, 1992), com hiperparâmetros \(\alpha_{ijk}=1\) (priori uniforme):

\[s_{K2}(G\mid 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})\]

Pontuação BDeu (Bayesian-Dirichlet equivalent uniform): generaliza o K2 com um tamanho amostral equivalente \(\alpha\)

Métodos Baseados em Pontuação: Principais Algoritmos

Exploram o espaço de DAGs por meio de adição, remoção ou reversão de arcos, sempre orientados por uma pontuação (AIC, BIC, K2 ou BDeu).

Listas de Permissões e de Bloqueios: Incorporando Conhecimento Prévio

• Lista de permissões (allowlist): conexões fixas, sempre incluídas na estimação, independentemente da pontuação
• Lista de bloqueios (blocklist): conexões proibidas, nunca testadas ou incluídas
• Permite combinar opinião de especialista com aprendizado orientado a dados
• No pacote bnlearn, esses argumentos aparecem nas funções de aprendizado como whitelist e blacklist

Equivalência de Markov e Direção de Arcos

• Estruturas Markov equivalentes (mesmo esqueleto, mesmas v-estruturas) são, em geral, score equivalentes para a maioria das pontuações usadas
• Isso dificulta a orientação de arcos que não fazem parte de uma v-estrutura — métodos baseados em restrição produzem, nesses casos, um grafo parcialmente direcionado
• Arcos do tipo \(A \rightarrow B\) fora de uma v-estrutura devem ser interpretados com cautela

Síntese do Bloco D

• Duas famílias de algoritmos: baseados em restrição (PC, PC-estável, GS, IAMB — via testes de independência e v-estruturas) e baseados em pontuação (hill-climbing, busca tabu — via AIC/BIC/K2/BDeu)
• Ambas as abordagens são heurísticas, pois o problema exato é NP-difícil
• Listas de permissões e de bloqueios permitem incorporar conhecimento clínico ao processo de estimação
• A equivalência de Markov lembra que nem toda orientação de arco pode ser decidida só pelos dados

Conexão com a Aula 2: de Regras Fixas a Redes Probabilísticas

• Na Aula 2, sistemas especialistas usavam regras fixas do tipo “SE-ENTÃO”, com encadeamento forward e backward
• Redes bayesianas generalizam essa lógica: em vez de regras binárias, cada relação é probabilística e quantificada
• O raciocínio não monotônico da Aula 2 — a hipótese diagnóstica mudando à medida que chegam evidências — é formalizado de maneira rigorosa e consistente pela atualização de crença (Bloco E)

Aplicações em Saúde: Panorama

• Diagnóstico diferencial: atualização simultânea da probabilidade de múltiplas doenças candidatas, à medida que chegam sintomas e exames
• Predição de desfechos: classificadores bayesianos para prever readmissão, mortalidade ou complicações
• Apoio a políticas de saúde pública: redes bayesianas para modelar fatores de risco populacionais (como o exemplo de trânsito do Bloco E, adaptável a epidemiologia)
• Integração com registros eletrônicos: tolerância nativa a dados faltantes, comum em prontuários reais

Atividade

• Elabore um pequeno texto (no máximo uma página), justificando cada escolha

Leitura Complementar e Preparação para a Prova

• Handouts do Prof. Anderson Ara (UFPR): Redes Bayesianas e Aplicações, Handouts #01 a #04 — referência central desta aula
• SCUTARI, M.; DENIS, J.-B. Bayesian Networks: With Examples in R, 2. ed. — aprofundamento prático em R
• KOLLER, D.; FRIEDMAN, N. Probabilistic Graphical Models — aprofundamento teórico

Referências

• ARA, A. Redes Bayesianas e Aplicações. Handouts #01–#04. UFPR, 2021.
• SCUTARI, M.; DENIS, J.-B. Bayesian Networks: With Examples in R. 2. ed. CRC Press, 2022.
• KOLLER, D.; FRIEDMAN, N. Probabilistic Graphical Models: Principles and Techniques. MIT Press, 2009.
• FRIEDMAN, N.; GOLDSZMIDT, M. Building classifiers using Bayesian networks. AAAI, 1996.
• COOPER, G. F.; HERSKOVITS, E. A Bayesian method for the induction of probabilistic networks from data. Machine Learning, 9(4), 1992.
• PEARL, J. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, 1988.