Algoritmo da Árvore de Junções (Junction Tree)

Visão geral

O Algoritmo da Árvore de Junção (Junction Tree Algorithm, JTA) — também chamado de algoritmo da árvore de cliques (clique tree algorithm) — é um método clássico de inferência probabilística exata (exact probabilistic inference) em modelos gráficos (graphical models) com ciclos. Ele converte um grafo cíclico em uma representação estruturada como árvore sobre cliques (cliques) (agrupamentos de variáveis) e, então, executa passagem de mensagens baseada em árvore (tree-based message passing) (soma-produto) para calcular:

  • Distribuições marginais (por exemplo, (p(X_i \mid \text{evidence})))
  • Marginais de clique (marginais conjuntas sobre subconjuntos de variáveis)
  • A função de partição (partition function) (Z) (para modelos não direcionados) ou a verossimilhança da evidência (p(e))

Conceitualmente, o algoritmo da árvore de junção é:

  1. Triangular (triangulate) o grafo (adicionar arestas de preenchimento (fill-in edges) para que ele se torne cordal (chordal))
  2. Extrair cliques maximais (maximal cliques)
  3. Organizar cliques em uma árvore que satisfaça a propriedade de interseção em execução (running intersection property)
  4. Executar propagação de crenças (belief propagation) nessa árvore (o que é exato em árvores)

Isso faz do JTA uma ponte entre:

  • Eliminação de variáveis (variable elimination, VE) (exata, mas dependente da ordem) e
  • Propagação de crenças (exata em árvores, aproximada em grafos com laços)

Ele é usado para inferência exata em Redes Bayesianas (após moralização) e em Campos Aleatórios de Markov (Redes de Markov), e fornece a base teórica por trás de muitos “motores de inferência exata” em programação probabilística (probabilistic programming) e em kits de ferramentas de modelos gráficos probabilísticos (PGM toolkits).

Por que ciclos são difíceis: o problema central

Em modelos gráficos estruturados como árvore, a Propagação de Crenças (Soma-Produto / Passagem de Mensagens) computa marginais exatas de forma eficiente porque as mensagens não “contam duas vezes” a informação.

Em grafos com ciclos, a passagem de mensagens ingênua se torna propagação de crenças com laços (loopy belief propagation), que pode:

  • não convergir,
  • convergir para crenças incorretas, ou
  • funcionar bem empiricamente, mas sem garantias de exatidão.

O JTA resolve isso transformando o modelo em uma árvore de cliques, onde a passagem de mensagens volta a ser exata.

Configuração de modelo gráfico

O JTA é tipicamente descrito para modelos não direcionados (MRFs / grafos de fatores), mas também se aplica a modelos direcionados (redes Bayesianas) após convertê-los para uma forma não direcionada.

Visão por fatoração

Muitos modelos podem ser escritos como:

[ p(\mathbf{x}) = \frac{1}{Z}\prod_{a \in \mathcal{F}} \phi_a(\mathbf{x}_a) ]

  • (\phi_a) são fatores (factors) não negativos sobre subconjuntos (\mathbf{x}_a)
  • (Z = \sum_{\mathbf{x}} \prod_a \phi_a(\mathbf{x}_a)) é a função de partição

A evidência (e) é tratada fixando variáveis (ou multiplicando por fatores indicadores).

A terminologia de grafos de fatores (ver Grafos de Fatores) é frequentemente usada em implementações, mas a construção da árvore de junção é geralmente descrita no grafo primal (primal graph): conecte duas variáveis se elas aparecem juntas em qualquer fator.

Conceito-chave: largura de árvore (treewidth) (o que torna o JTA rápido ou inviável)

O algoritmo da árvore de junção é polinomial no número de variáveis para tamanho de clique fixo, mas o tamanho do clique pode crescer rapidamente. A medida estrutural relevante é a largura de árvore (treewidth).

Largura de árvore em uma frase

A largura de árvore de um grafo (mais 1) é o tamanho do maior clique que você precisa criar (no melhor caso) ao transformar o grafo em uma árvore de junção.

Mais precisamente:

  • Uma ordenação de eliminação induz um grafo triangulado com alguns cliques maximais.
  • A largura induzida (induced width) de uma ordenação é o número máximo de vizinhos anteriores ao eliminar um nó.
  • A largura de árvore é a largura induzida mínima dentre todas as ordenações.

Complexidade

Se as variáveis são discretas com tamanho máximo de domínio (d), e o maior clique tem tamanho (k), então a passagem de mensagens e as operações com tabelas são tipicamente:

[ \tilde{O}(d^k) ]

Por isso, o JTA é exato, mas pode ser inviável em grafos densos ou com alta largura de árvore.

Passo 1: Do modelo para um grafo não direcionado

Para campos aleatórios de Markov / grafos de fatores

  • Construa o grafo primal: conecte variáveis que coocorrem em um fator.

Para redes Bayesianas

Para aplicar a árvore de junção, uma rota comum é:

  1. Moralizar (moralize) o grafo acíclico dirigido (DAG): conecte todos os pais de cada nó (“case os pais”), e então remova as direções das arestas.
  2. Use o grafo moral não direcionado resultante.

Essa conversão preserva o conjunto de independências condicionais necessário para inferência exata.

(Fundamentos: Redes Bayesianas)

Passo 2: Triangulação (tornando o grafo cordal)

Um grafo é triangulado (também conhecido como cordal) se todo ciclo de comprimento (\ge 4) tem uma corda (chord) (uma aresta conectando dois vértices não adjacentes no ciclo).

A triangulação é feita adicionando arestas de preenchimento para que o grafo resultante seja cordal. Isso é crucial porque:

  • Em um grafo cordal, cliques maximais podem ser organizados em uma árvore de junção que satisfaça a propriedade de interseção em execução.

Triangulação via ordenações de eliminação de variáveis

Uma forma padrão de triangular é escolher uma ordenação de eliminação (elimination ordering) (\pi = (X_1, X_2, \dots, X_n)). Eliminar uma variável significa:

  • conectar todos os seus vizinhos atuais (torná-los um clique),
  • e então remover a variável.

As conexões adicionadas entre vizinhos são as arestas de preenchimento. O grafo preenchido resultante é cordal.

Isso está intimamente ligado à eliminação de variáveis: a mesma ordenação determina o tamanho dos fatores intermediários na VE e os tamanhos de clique no JTA.

Heurísticas de ordenação

Encontrar a largura de árvore ótima é NP-difícil, então sistemas práticos usam heurísticas como:

  • Mínimo preenchimento (min-fill): eliminar o nó que adiciona o menor número de arestas de preenchimento
  • Grau mínimo (min-degree): eliminar o nó com o menor grau atual
  • Mínimo preenchimento ponderado (weighted min-fill): levar em conta os tamanhos dos domínios das variáveis (importante quando os domínios diferem)

Essas heurísticas podem mudar drasticamente o tempo de execução.

Passo 3: Cliques maximais e a árvore de cliques

Uma vez triangulado, compute os cliques maximais do grafo cordal. Esses cliques se tornarão nós na árvore de junção.

Conjuntos separadores e a propriedade de interseção em execução

As arestas na árvore de cliques são rotuladas por conjuntos separadores (separator sets, sepsets):

[ S_{ij} = C_i \cap C_j ]

A árvore de junção deve satisfazer a propriedade de interseção em execução:

Para qualquer variável (X), o conjunto de cliques que contém (X) forma uma subárvore conectada.

Essa propriedade garante que, quando cliques concordam sobre variáveis compartilhadas, as crenças resultantes são globalmente consistentes.

Construindo a árvore: árvore geradora máxima sobre interseções de cliques

Uma construção comum:

  1. Crie um grafo completo sobre os cliques.
  2. Pondere a aresta ((C_i, C_j)) por (|C_i \cap C_j|) (ou pelo tamanho total do espaço de estados do separador).
  3. Calcule uma árvore geradora máxima (maximum spanning tree).

Isso produz uma árvore de cliques que (para grafos cordais) satisfaz a propriedade de interseção em execução.

Passo 4: Atribuir fatores a cliques e inicializar potenciais

Cada fator original (\phi_a(\mathbf{x}_a)) deve ser atribuído a algum clique (C) que contenha seu escopo (\mathbf{x}_a \subseteq C).

Defina o potencial de clique (clique potential):

[ \psi_C(\mathbf{x}C) = \prod{a \in \mathcal{A}(C)} \phi_a(\mathbf{x}_a) ]

onde (\mathcal{A}(C)) são os fatores atribuídos ao clique (C). Frequentemente, a evidência é incorporada multiplicando fatores indicadores no(s) clique(s) apropriado(s).

Passo 5: Passagem de mensagens na árvore de junção (inferência exata)

Agora executamos soma-produto na árvore de cliques, de forma similar à propagação de crenças em uma árvore, mas as mensagens são entre cliques e resumem informações sobre separadores.

Mensagem do clique \(i\) para o clique \(j\)

Seja (C_i) o clique remetente, (C_j) o clique destinatário e (S_{ij} = C_i \cap C_j) o separador entre eles.

Uma mensagem soma-produto padrão é:

[ m_{i \to j}(\mathbf{x}{S{ij}}) ;=; \sum_{\mathbf{x}{C_i \setminus S{ij}}} \psi_i(\mathbf{x}{C_i}) \prod{k \in \text{nb}(i)\setminus j} m_{k \to i}(\mathbf{x}{S{ki}}) ]

Após passar mensagens (por exemplo, coletar e depois distribuir), cada clique pode computar uma crença calibrada (calibrated belief):

[ b_i(\mathbf{x}{C_i}) \propto \psi_i(\mathbf{x}{C_i}) \prod_{k \in \text{nb}(i)} m_{k \to i}(\mathbf{x}{S{ki}}) ]

E as crenças do separador satisfazem:

[ b_{S_{ij}}(\mathbf{x}{S{ij}}) = \sum_{\mathbf{x}{C_i \setminus S{ij}}} b_i(\mathbf{x}{C_i}) = \sum{\mathbf{x}{C_j \setminus S{ij}}} b_j(\mathbf{x}_{C_j}) ]

Essa igualdade (“calibração”) é a marca registrada da inferência correta por árvore de junção.

Extraindo marginais de variável única

Para obter (p(X \mid e)), escolha qualquer clique (C) que contenha (X) e marginalize:

[ p(X \mid e) = \sum_{\mathbf{x}_{C \setminus {X}}} b_C(\mathbf{x}_C) ]

A propriedade de interseção em execução garante consistência: não importa qual clique contendo (X) você escolha.

Calculando a função de partição ou a verossimilhança da evidência

Após a calibração, você pode calcular o normalizador usando um clique (e separadores) de um modo que evite dupla contagem. Uma identidade comum é:

[ \log Z = \sum_{C} \log Z_C ;-; \sum_{S} \log Z_S ]

onde (Z_C = \sum_{\mathbf{x}_C} b_C(\mathbf{x}_C)) e, de modo análogo, para separadores, dependendo do esquema específico de normalização de mensagens e da implementação (Hugin vs. Shafer–Shenoy). Na prática, muitas bibliotecas acompanham constantes de normalização durante a passagem de mensagens para retornar (Z) (ou (p(e))) de forma robusta.

Um exemplo concreto: um ciclo de 4 (por que a triangulação importa)

Considere quatro variáveis binárias (A,B,C,D) com fatores de pares formando um ciclo:

  • (\phi_{AB}(A,B))
  • (\phi_{BC}(B,C))
  • (\phi_{CD}(C,D))
  • (\phi_{DA}(D,A))

O grafo primal é um ciclo de 4: (A-B-C-D-A). Esse grafo não é cordal (ele tem um ciclo sem corda de comprimento 4).

Triangular

Adicione uma aresta de preenchimento, por exemplo (A-C). Agora o grafo é cordal e tem cliques maximais:

  • (C_1 = {A,B,C})
  • (C_2 = {A,C,D})

Separador: (S_{12} = {A,C})

Atribuir fatores aos cliques

Por exemplo:

  • Atribua (\phi_{AB}, \phi_{BC}) a (C_1)
  • Atribua (\phi_{CD}, \phi_{DA}) a (C_2)
  • A aresta de preenchimento (A-C) não exige um fator original; ela existe para permitir cordalidade.

Potenciais de clique:

[ \psi_{1}(A,B,C) = \phi_{AB}(A,B)\phi_{BC}(B,C) ] [ \psi_{2}(A,C,D) = \phi_{CD}(C,D)\phi_{DA}(D,A) ]

Passagem de mensagens

Mensagem (m_{1\to 2}(A,C)):

[ m_{1\to 2}(A,C) = \sum_{B} \psi_1(A,B,C) ]

Mensagem (m_{2\to 1}(A,C)):

[ m_{2\to 1}(A,C) = \sum_{D} \psi_2(A,C,D) ]

Crenças calibradas dos cliques:

[ b_1(A,B,C) \propto \psi_1(A,B,C), m_{2\to 1}(A,C) ] [ b_2(A,C,D) \propto \psi_2(A,C,D), m_{1\to 2}(A,C) ]

Agora você pode obter, por exemplo, (p(A)) marginalizando (b_1) em relação a (B,C) (ou (b_2) em relação a (C,D)).

Este exemplo mostra a ideia central: um grafo com laços vira uma árvore sobre agrupamentos, onde a inferência em árvore é exata.

Pseudocode (high level)

Below is a conceptual outline; real systems optimize factor placement, caching, log-space computations, and normalization.

Input: factors {φ_a(x_a)} over variables X, evidence e

1) Build primal graph G from factor scopes
2) If BN: moralize to get undirected G
3) Choose elimination ordering π (min-fill / min-degree / weighted)
4) Triangulate G using π, record fill edges -> chordal graph G'
5) Find maximal cliques {C_i} in G'
6) Build clique tree T over cliques using maximum spanning tree on |C_i ∩ C_j|
7) Assign each factor φ_a to a clique C_i containing its scope
8) Initialize clique potentials ψ_i = product of assigned factors (include evidence)
9) Run sum-product message passing on T (collect & distribute) to calibrate
10) Extract marginals from calibrated clique beliefs; compute Z if needed

Relação com eliminação de variáveis e propagação de crenças

JTA vs. eliminação de variáveis (VE)

  • Mesmas operações centrais: somar para eliminar variáveis e multiplicar fatores.
  • A VE computa uma consulta específica eliminando variáveis; os tamanhos dos fatores intermediários são governados pela ordenação.
  • O JTA pode ser visto como “VE compilada em uma estrutura reutilizável”:
    • Uma vez que a árvore de junção é construída e calibrada, você pode responder muitas consultas marginais de forma eficiente.
    • É especialmente benéfico quando você tem múltiplas consultas ou evidência variável.

JTA vs. propagação de crenças (BP)

  • A propagação de crenças é exata em árvores. A árvore de junção é uma árvore, mas sobre cliques, não sobre variáveis individuais.
  • A propagação de crenças com laços pode ser interpretada como executar propagação de crenças em um grafo de fatores cíclico; ela é aproximada.
  • O JTA às vezes é descrito como “a versão exata da propagação de crenças para grafos com ciclos” — mas o custo é que as mensagens têm dimensionalidade mais alta (sobre separadores).

Para contexto: Propagação de Crenças (Soma-Produto / Passagem de Mensagens)

Considerações práticas em implementações reais

Estabilidade numérica: espaço logarítmico e normalização

Potenciais podem sofrer underflow rapidamente ao multiplicar muitas probabilidades. Práticas comuns incluem:

  • armazenar valores em espaço logarítmico (log-space),
  • normalizar mensagens para somarem 1 e rastrear as constantes de normalização separadamente (útil para (Z) / (p(e))).

Escolher uma boa ordenação de eliminação importa muito

Dois grafos com o mesmo número de nós podem ter larguras de árvore muito diferentes. Boas ordenações podem reduzir o tamanho máximo do clique de, por exemplo, 20 variáveis para 10 variáveis — transformando uma tarefa de inferência impossível em uma viável.

Memória frequentemente é o gargalo

Mesmo que a computação seja gerenciável, armazenar tabelas de clique de tamanho (d^k) pode dominar a memória. Implementações podem usar:

  • tabelas esparsas (quando os fatores são esparsos),
  • representações estruturadas (diagramas de decisão algébricos, tensores com estrutura de baixo posto (low-rank)),
  • ou métodos aproximados quando a largura de árvore é grande demais.

Variantes: Shafer–Shenoy vs. Hugin

Dois esquemas comuns de propagação em árvore de junção:

  • Shafer–Shenoy: mensagens são computadas puramente a partir de potenciais locais de clique e mensagens de entrada (conceitualmente simples; comum em descrições pedagógicas).
  • Hugin: mantém potenciais de separador explicitamente e atualiza potenciais de clique/separador in-place; frequentemente eficiente na prática.

Ambos produzem crenças calibradas exatas quando implementados corretamente.

Aplicações

Inferência exata em redes Bayesianas

Em muitos toolkits de BNs, a inferência é realizada compilando uma árvore de junção uma vez e, então, respondendo consultas como:

  • (p(\text{disease} \mid \text{symptoms}))
  • verossimilhança da evidência (p(e))
  • marginais a posteriori para suporte à decisão

Isso é comum em sistemas de diagnóstico, análise de risco e sistemas especialistas.

Campos aleatórios de Markov em domínios pequenos a médios

Em visão computacional e estatística espacial, MRFs podem ser do tipo grade, onde a largura de árvore pode ser grande. O JTA é mais prático quando:

  • o grafo não é muito “largo” (por exemplo, cadeias/grades finas),
  • ou o modelo pode ser decomposto em componentes menores.

Para grades grandes, métodos aproximados (propagação de crenças com laços, Monte Carlo via Cadeias de Markov (MCMC), inferência variacional (variational inference)) são mais comuns, mas o JTA continua sendo um padrão-ouro de exatidão em instâncias tratáveis.

Cálculo da função de partição

Calcular (Z) é essencial em modelos não direcionados para:

  • avaliar verossimilhanças,
  • comparar modelos,
  • treinar quando (Z) precisa ser obtida exatamente (raro, exceto em cenários pequenos/baixa largura de árvore).

Em modelos discriminativos como Campos Aleatórios Condicionais (Conditional Random Fields, CRFs), o (Z) exato costuma ser calculado via programação dinâmica (dynamic programming) em cadeias/árvores; o JTA generaliza essa ideia para grafos com baixa largura de árvore.

Limitações e quando não usar o JTA

O JTA é exato, mas não é uma solução universal:

  • Se o grafo tem alta largura de árvore, os cliques ficam grandes demais.
  • Conectividade densa (ou dependências de longo alcance) pode tornar a inferência exata inviável.
  • Nesses casos, profissionais frequentemente recorrem a:
    • propagação de crenças com laços (aproximada),
    • métodos de amostragem (MCMC),
    • inferência variacional,
    • ou aproximações estruturadas.

(Veja também: Inferência Levantada (Inferência Probabilística Levantada) para explorar simetria e reduzir a complexidade.)

Resumo

O algoritmo da árvore de junção é a abordagem padrão para inferência exata em modelos gráficos com ciclos ao transformar o problema em propagação de crenças exata em uma árvore de cliques:

  • A triangulação (via ordenação de eliminação) torna o grafo cordal.
  • Cliques maximais do grafo cordal tornam-se nós em uma árvore de cliques.
  • A propriedade de interseção em execução garante consistência global.
  • A passagem de mensagens sobre separadores computa marginais exatas e (com a contabilidade apropriada) a função de partição.

Sua praticidade é dominada pela largura de árvore: quando a largura de árvore é pequena, o JTA é rápido e exato; quando a largura de árvore é grande, ele se torna computacionalmente proibitivo e métodos aproximados normalmente são preferidos.