Grafos de Fatores

O que é um grafo de fatores?

Um grafo de fatores (factor graph) é um modelo gráfico bipartido (bipartite graphical model) que explicita como uma função global sobre muitas variáveis se fatoriza em um produto (ou, de forma mais geral, uma composição) de funções locais.

Em modelagem probabilística, a função global geralmente é uma distribuição de probabilidade conjunta (joint probability distribution) (ou uma conjunta não normalizada, às vezes chamada de energia (energy) ou potencial (potential)). A ideia central é:

[ p(x_1,\dots,x_n) \propto \prod_{a \in \mathcal{F}} f_a(\mathbf{x}_a) ]

(x_1,\dots,x_n) são nós de variável (variable nodes)
cada (f_a(\mathbf{x}_a)) é um fator (factor) (uma função sobre um subconjunto de variáveis)
(\mathcal{F}) é o conjunto de fatores
(\mathbf{x}_a) denota as variáveis das quais o fator (a) depende
“(\propto)” indica que o produto pode precisar de uma constante de normalização (Z)

Um grafo de fatores desenha essa estrutura como um grafo bipartido (bipartite graph):

um conjunto de nós são variáveis
o outro conjunto são fatores
uma aresta conecta a variável (x_i) ao fator (f_a) sse (x_i) é um argumento de (f_a)

Essa fatorização explícita é o que viabiliza algoritmos eficientes de passagem de mensagens (message passing) como soma-produto (sum-product) (para marginais) e máximo-produto (max-product) (para inferência MAP (maximum a posteriori)), abordados com mais profundidade em Propagação de Crenças (Soma-Produto / Passagem de Mensagens).

Por que grafos de fatores importam

Grafos de fatores são populares porque eles:

Representam a verdadeira estrutura computacional do modelo
Muitos modelos contêm interações locais repetidas (termos par-a-par, cliques pequenos, restrições). Grafos de fatores mostram essas interações diretamente.
Unificam modelos direcionados e não direcionados sob uma única representação
Tanto Redes Bayesianas (direcionadas) quanto Campos Aleatórios de Markov (não direcionados) podem ser convertidos em grafos de fatores.
Permitem inferência escalável via localidade
O custo das atualizações de mensagens depende da aridade do fator (quantas variáveis um fator toca), e não do número total de variáveis.
Generalizam além de probabilidade
O mesmo grafo pode representar objetivos como satisfação de restrições, variações de mínimos quadrados e inferência MAP ao mudar a álgebra (por exemplo, substituindo somas por máximos ou mínimos).

Definição formal e notação

Seja (\mathbf{x} = (x_1,\ldots,x_n)). Um grafo de fatores representa uma fatorização:

[ F(\mathbf{x}) = \prod_{a \in \mathcal{F}} f_a(\mathbf{x}_a) ]

Para modelos probabilísticos, (F(\mathbf{x})) é tipicamente uma probabilidade não normalizada:

[ p(\mathbf{x}) = \frac{1}{Z}\prod_{a} f_a(\mathbf{x}a), \quad Z = \sum{\mathbf{x}} \prod_{a} f_a(\mathbf{x}_a) ]

Se cada (f_a) é uma tabela de probabilidade condicional (conditional probability table, CPT) ou um termo de verossimilhança, o produto pode já ser normalizado (ou próximo disso).
Se cada (f_a) é um potencial (\psi_a) arbitrário e não negativo, a normalização é fornecida por (Z).

Nós de variável vs nós de fator

Nó de variável (x_i): uma variável aleatória (discreta ou contínua).
Nó de fator (f_a): uma função sobre um subconjunto de variáveis, frequentemente pequeno:
- fator unário (f(x_i))
- fator par-a-par (f(x_i, x_j))
- fator de ordem superior (f(x_i, x_j, x_k, \dots))

As arestas indicam participação, não direcionalidade.

Um exemplo concreto: uma cadeia (como um HMM)

Considere uma sequência de estados ocultos (x_1,\dots,x_T) e observações (y_1,\dots,y_T). Uma fatorização comum é:

[ p(\mathbf{x}, \mathbf{y}) = p(x_1)\prod_{t=2}^T p(x_t \mid x_{t-1}) \prod_{t=1}^T p(y_t \mid x_t) ]

Na forma de grafo de fatores:

nós de variável: (x_1,\dots,x_T) (e, opcionalmente, (y_t) se você os incluir explicitamente)
fatores:
- (f_{\text{init}}(x_1)=p(x_1))
- (f_t(x_{t-1},x_t)=p(x_t\mid x_{t-1}))
- (g_t(x_t)=p(y_t\mid x_t)) (com (y_t) observado; portanto, isso se torna um fator unário de “evidência (evidence)”)

Esse grafo é uma árvore (uma cadeia), então soma-produto computa marginais exatas de forma eficiente — isso é essencialmente o algoritmo forward-backward (forward-backward algorithm) expresso como propagação de crenças.

Relação com redes bayesianas e campos aleatórios de Markov

Grafos de fatores não são “concorrentes” de redes bayesianas ou MRFs, mas sim uma representação alternativa que torna a fatorização explícita.

De uma rede bayesiana para um grafo de fatores

Uma rede bayesiana se fatoriza como:

[ p(\mathbf{x}) = \prod_i p(x_i \mid \mathrm{pa}(x_i)) ]

Converta para um grafo de fatores por:

criar um nó de variável para cada (x_i)
criar um nó de fator (f_i) para cada condicional (p(x_i\mid \mathrm{pa}(x_i)))
conectar (f_i) a (x_i) e a todas as variáveis-pais (\mathrm{pa}(x_i))

Isso preserva a fatorização do modelo direcionado, mas remove a semântica das setas (o grafo de fatores em si é não direcionado/bipartido).

Leitura relacionada: Redes Bayesianas

De um campo aleatório de Markov para um grafo de fatores

Um campo aleatório de Markov se fatoriza sobre cliques (cliques):

[ p(\mathbf{x}) = \frac{1}{Z}\prod_{c \in \mathcal{C}} \psi_c(\mathbf{x}_c) ]

Converta por:

nós de variável para cada variável
nós de fator para cada potencial de clique (\psi_c)
conectar (\psi_c) a todas as variáveis no clique (c)

Essa conversão frequentemente é quase um-para-um porque campos aleatórios de Markov já são baseados em fatores.

Leitura relacionada: Campos Aleatórios de Markov

Por que usar grafos de fatores em vez de apenas figuras de BN/MRF?

Diagramas de BN e MRF mostram a estrutura de independência condicional, mas podem obscurecer a computação:

Em um campo aleatório de Markov, um único potencial de clique pode envolver muitas variáveis; um grafo de fatores deixa isso explícito e permite fatorização adicional (dividindo um potencial grande em potenciais menores quando possível).
Em uma rede bayesiana, o grafo codifica direção e independências, mas a inferência frequentemente é implementada multiplicando fatores e eliminando variáveis — grafos de fatores se alinham naturalmente a essas operações.

Problemas centrais de inferência

Grafos de fatores suportam várias tarefas padrão de inferência:

Inferência marginal

Compute (p(x_i)) ou (p(\mathbf{x}_S)) para um subconjunto (S). Com a fatorização:

[ p(x_i) = \sum_{\mathbf{x}\setminus x_i} \frac{1}{Z}\prod_a f_a(\mathbf{x}_a) ]

Somar ingenuamente sobre todas as atribuições é exponencial em (n). Grafos de fatores permitem programação dinâmica via passagem de mensagens local.

Cálculo da função de partição \(Z\) (partition function)

[ Z = \sum_{\mathbf{x}} \prod_a f_a(\mathbf{x}_a) ]

Isso é crucial para avaliar verossimilhança e para treinar muitos modelos probabilísticos.

Inferência MAP (atribuição mais provável)

[ \mathbf{x}^* = \arg\max_{\mathbf{x}} \prod_a f_a(\mathbf{x}_a) ]

Frequentemente reformulada usando energias (E(\mathbf{x}) = -\sum_a \log f_a(\mathbf{x}_a)) como (\arg\min E(\mathbf{x})).

Passagem de mensagens em grafos de fatores

O algoritmo característico para grafos de fatores é a propagação de crenças (belief propagation, BP), também chamada de soma-produto (para marginais) e máximo-produto (para MAP). As regras de atualização exploram a estrutura bipartida: variáveis enviam mensagens a fatores, e fatores enviam mensagens de volta às variáveis.

Soma-produto (para marginais)

Para variáveis discretas, mensagens são funções sobre o domínio de uma variável.

Mensagem de variável para fator: [ m_{i\to a}(x_i) = \prod_{b \in N(i)\setminus a} m_{b\to i}(x_i) ]
Mensagem de fator para variável: [ m_{a\to i}(x_i) = \sum_{\mathbf{x}a \setminus x_i} f_a(\mathbf{x}a)\prod{j \in N(a)\setminus i} m{j\to a}(x_j) ]

Aqui, (N(i)) são os fatores vizinhos da variável (i), e (N(a)) são as variáveis vizinhas do fator (a).

Quando as mensagens convergem (ou após uma varredura em uma árvore), a crença (marginal estimada) é:

[ b_i(x_i) \propto \prod_{a \in N(i)} m_{a\to i}(x_i) ]

Em um grafo de fatores com estrutura de árvore (tree-structured), essas marginais são exatas.

Máximo-produto (para MAP)

Substitua a soma por maximização:

[ m_{a\to i}(x_i) = \max_{\mathbf{x}a \setminus x_i} f_a(\mathbf{x}a)\prod{j \in N(a)\setminus i} m{j\to a}(x_j) ]

Isso produz crenças MAP (e, com backpointers, uma atribuição MAP) exatamente em árvores e aproximadamente em grafos com ciclos.

Uma variante numericamente estável opera no espaço logarítmico (log space) e é frequentemente chamada de mínimo-soma (min-sum):

transforme (g_a(\mathbf{x}_a) = -\log f_a(\mathbf{x}_a))
produtos viram somas, max vira min

Esboço de pseudocódigo

repeat until convergence or max_iters:
  for each variable i:
    for each neighboring factor a:
      m_{i->a}(x_i) = Π_{b in N(i)\a} m_{b->i}(x_i)

  for each factor a:
    for each neighboring variable i:
      m_{a->i}(x_i) = Σ_{x_a \ x_i} f_a(x_a) Π_{j in N(a)\i} m_{j->a}(x_j)

  optionally normalize messages to prevent underflow

Para mais detalhes, escalonamentos (schedules) e comportamento de convergência, veja Propagação de Crenças (Soma-Produto / Passagem de Mensagens).

Quando a inferência é eficiente?

O custo da inferência depende principalmente de:

Estrutura do grafo: árvores vs grafos com ciclos
Aridade do fator: o número de variáveis em cada fator
Tamanho do domínio das variáveis (para variáveis discretas)

Árvores: exata e eficiente

Se o grafo de fatores é acíclico, a propagação de crenças executa em tempo aproximadamente linear no número de arestas, com um custo multiplicativo para computações de fatores:

Para um fator que toca (k) variáveis, cada uma com tamanho (d), uma mensagem ingênua de fator para variável custa (O(d^k)) devido à soma sobre (k-1) variáveis.
Portanto, fatores de baixa aridade (unários/par-a-par) são particularmente eficientes.

Grafos com ciclos: aproximada, mas frequentemente útil

Se o grafo de fatores tem ciclos, a propagação de crenças se torna propagação de crenças com ciclos (loopy belief propagation):

Não há garantia de convergência
Se convergir, as crenças não são garantidamente exatas
Empiricamente forte em muitos domínios (notavelmente códigos de correção de erros)

Truques práticos comuns incluem amortecimento (damping) de mensagens, bons escalonamentos e trabalhar no espaço logarítmico.

Exemplo prático: campo aleatório de Markov par-a-par / remoção de ruído em imagens

Um modelo par-a-par clássico para remoção de ruído em imagens binárias usa:

variáveis (x_i \in {0,1}) para o rótulo latente “verdadeiro” de cada pixel
pixels ruidosos observados (y_i)
fatores unários que incentivam concordância com a observação: (f_i(x_i) = p(y_i \mid x_i))
fatores par-a-par que incentivam suavidade entre pixels vizinhos (i,j): (f_{ij}(x_i,x_j) = \exp(\beta \cdot \mathbb{1}[x_i=x_j]))

Grafo de fatores:

um nó de variável por pixel
um nó de fator unário por pixel (evidência)
um nó de fator par-a-par por par de vizinhos

Soma-produto produz marginais aproximadas (probabilidades por pixel). Máximo-produto aproxima uma rotulagem MAP.

Isso está intimamente relacionado a modelos usados em visão computacional e a frameworks de treinamento como Campos Aleatórios Condicionais (CRFs).

Exemplo prático: restrições de paridade em códigos de correção de erros (LDPC)

Códigos de verificação de paridade de baixa densidade (LDPC — Low-Density Parity-Check) são naturalmente expressos como grafos de fatores:

nós de variável são bits do código
nós de fator são restrições de verificação de paridade que impõem paridade XOR (XOR parity) (soma mod 2 igual a 0)

Um fator de paridade tem a forma:

[ f_a(\mathbf{x}a)=\mathbb{1}\left[\bigoplus{i \in N(a)} x_i = 0\right] ]

Decodificar com soma-produto nesse grafo de fatores esparso e com ciclos é uma das histórias de sucesso mais famosas da propagação de crenças com ciclos: as restrições são locais e o grafo é esparso, tornando a passagem de mensagens rápida e precisa na prática.

Grafos de fatores para “objetivos gerais” (além de probabilidade)

Embora frequentemente introduzidos para distribuições de probabilidade, grafos de fatores podem representar uma ampla classe de objetivos globais que se decompõem localmente.

Visão por semianel (semiring) (intuição)

Muitos problemas de inferência têm a forma:

[ \text{Combinar fatores localmente} \quad \text{e então} \quad \text{eliminar variáveis} ]

Para marginais: elimina por soma, combina por produto (soma-produto)
Para MAP: elimina por máximo, combina por produto (máximo-produto)
No domínio logarítmico: combina por soma, elimina por mínimo/máximo (mínimo-soma / máximo-soma)

Essa perspectiva ajuda a explicar por que o mesmo grafo suporta diferentes tarefas de inferência simplesmente trocando o “operador de eliminação”.

Aprendizado com grafos de fatores (alto nível)

Grafos de fatores definem uma família estruturada de distribuições. O aprendizado tipicamente significa estimar parâmetros dentro dos fatores, por exemplo:

[ f_a(\mathbf{x}_a) = \exp\left(\theta^\top \phi_a(\mathbf{x}_a)\right) ]

Essa forma de família exponencial (exponential family) é comum em CRFs e modelos log-lineares (log-linear models). O treinamento frequentemente requer:

computar marginais (para gradientes da log-verossimilhança)
computar ou aproximar (Z)
usar inferência aproximada (propagação de crenças com ciclos, métodos variacionais (variational methods), amostragem (sampling)) quando a inferência exata é intratável

Para predição estruturada discriminativa, veja Campos Aleatórios Condicionais (CRFs).

Dicas de implementação e armadilhas

Normalize e use o domínio logarítmico

Produtos de muitas probabilidades sofrem facilmente subfluxo (underflow). Abordagens típicas:

normalizar cada mensagem após a atualização (dividir pela soma)
trabalhar no domínio logarítmico (log domain):
- soma-produto vira operações de log-soma-exp (log-sum-exp)
- máximo-produto vira max + soma

O escalonamento de mensagens importa

Árvore: um escalonamento em duas passadas (coletar e depois distribuir) fornece marginais exatas eficientemente.
Com ciclos: atualizações síncronas podem oscilar; atualizações assíncronas e amortecimento (damping) (misturar mensagens novas e antigas) frequentemente ajudam.

A aridade do fator domina o custo

Um único fator de alta ordem pode tornar a inferência cara. Se o próprio fator se fatoriza ainda mais, represente-o como múltiplos fatores menores (às vezes introduzindo variáveis auxiliares (auxiliary variables)).

Onde grafos de fatores são usados em IA/AM (AI/ML)

Grafos de fatores aparecem em toda a IA moderna, especialmente quando problemas têm estrutura local:

PLN (NLP — Natural Language Processing): rotulagem de sequências e modelos de parsing; CRFs e suas variantes
Visão computacional (computer vision): segmentação, estéreo, remoção de ruído usando potenciais par-a-par/de ordem superior
Robótica (robotics): SLAM (Simultaneous Localization and Mapping; localização e mapeamento simultâneos) e fusão de sensores (sensor fusion) frequentemente usam estruturas do tipo grafo de fatores (frequentemente com variáveis contínuas e fatores gaussianos)
Biologia computacional (computational biology): inferência de haplótipos, modelagem de proteínas
Códigos de correção de erros (error-correcting codes): LDPC e decodificação turbo via propagação de crenças com ciclos
Programação probabilística (probabilistic programming) / modelos estruturados: como uma representação intermediária para motores de inferência

Para ideias mais avançadas de escalabilidade em cenários relacionais, veja Inferência Levantada (Inferência Probabilística Levantada).

Resumo

Um grafo de fatores é uma representação bipartida de como uma função global (frequentemente uma probabilidade conjunta) se decompõe em fatores locais sobre subconjuntos de variáveis.
Ele fornece uma visão unificadora que conecta e pode ser derivada tanto de Redes Bayesianas quanto de Campos Aleatórios de Markov.
Sua estrutura permite passagem de mensagens eficiente:
- soma-produto para marginais e funções de partição
- máximo-produto (ou mínimo-soma no espaço logarítmico) para inferência MAP
Em árvores, a propagação de crenças é exata; em grafos com ciclos, é aproximada, mas frequentemente eficaz na prática.
Grafos de fatores são amplamente usados em IA/AM sempre que modelos têm interações locais repetidas — apoiando tanto raciocínio probabilístico fundamentado quanto inferência prática em larga escala.