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

A propagação de crenças (BP, belief propagation), também chamada de algoritmo soma-produto (sum-product algorithm) ou passagem de mensagens (message passing), é um método central de inferência para modelos gráficos probabilísticos (probabilistic graphical models) — incluindo Grafos de Fatores, Redes Bayesianas e Campos Aleatórios de Markov. Seu objetivo é computar eficientemente:

  • Distribuições marginais (também conhecidas como crenças), por exemplo (p(x_i)) ou (p(x_i, x_j))
  • A função de partição (Z) (constante de normalização) para modelos não direcionados
  • Com uma variante estreitamente relacionada (máx-produto / máx-soma (max-product / max-sum)), soluções MAP (MAP) (most probable assignments)

Em árvores (grafos acíclicos), a BP é exata e frequentemente dramaticamente mais rápida do que a marginalização ingênua. Em grafos com ciclos, a propagação de crenças com laços (loopy belief propagation) é uma aproximação amplamente usada que muitas vezes funciona bem na prática, mas não tem garantias universais de convergência.

Qual problema a BP está resolvendo?

Um modelo gráfico representa uma distribuição conjunta que se fatoriza em funções locais (“fatores”). Em um grafo de fatores, a distribuição conjunta sobre variáveis (x = (x_1,\dots,x_n)) é tipicamente escrita como:

[ p(x) = \frac{1}{Z} \prod_{a \in \mathcal{F}} f_a(x_{\mathrm{scope}(a)}) ]

  • Cada fator (f_a(\cdot)) é uma função não negativa sobre um subconjunto de variáveis.
  • Para redes bayesianas, os fatores são tabelas de probabilidade condicional (CPTs).
  • Para CAMs, os fatores são potenciais, e (Z) é a função de partição.

Duas tarefas centrais de inferência:

  1. Marginais: computar (p(x_i)) (ou (p(x_i, x_j))) a partir da conjunta.
  2. Função de partição: computar [ Z = \sum_x \prod_a f_a(x_{\mathrm{scope}(a)}) ] o que é essencial para verossimilhanças em modelos não direcionados e para aprendizado de parâmetros.

O cálculo direto geralmente é exponencial em (n). A BP explora a fatorização e a estrutura esparsa do grafo para reduzir a complexidade.

Grafos de fatores como uma linguagem comum

A BP é expressa de forma mais limpa em uma representação de Grafos de Fatores:

  • Nós de variável (i \in \mathcal{V})
  • Nós de fator (a \in \mathcal{F})
  • Uma aresta ((i,a)) existe se a variável (x_i) é um argumento do fator (f_a)

Tanto Redes Bayesianas quanto Campos Aleatórios de Markov podem ser convertidos em grafos de fatores, então a mesma maquinaria de passagem de mensagens se aplica.

Propagação de crenças soma-produto em árvores (exata)

Quando o grafo de fatores é acíclico, a BP computa marginais exatas em tempo proporcional ao número de arestas vezes o custo por fator.

Mensagens: os objetos-chave

A BP opera passando mensagens ao longo das arestas. Existem dois tipos:

  • Mensagem de variável para fator: (m_{i\to a}(x_i))
  • Mensagem de fator para variável: (m_{a\to i}(x_i))

Intuição:

  • (m_{i\to a}(x_i)) resume “tudo o que a variável (i) ouviu do resto do grafo, excluindo o fator (a).”
  • (m_{a\to i}(x_i)) resume “o que o fator (a) ‘pensa’ sobre (x_i), dado o resto de suas variáveis vizinhas.”

Seja (N(i)) o conjunto de fatores vizinhos da variável (i), e (N(a)) o conjunto de variáveis vizinhas do fator (a).

Equações de atualização (soma-produto)

Variável → fator [ m_{i\to a}(x_i) = \prod_{b \in N(i)\setminus a} m_{b\to i}(x_i) ]

Fator → variável [ m_{a\to i}(x_i) = \sum_{x_{N(a)\setminus i}} f_a(x_{N(a)}) \prod_{j \in N(a)\setminus i} m_{j\to a}(x_j) ]

A atualização fator-para-variável é o passo “difícil”: ela soma sobre todas as atribuições das outras variáveis do fator. Para escopos discretos pequenos, isso é viável; para escopos grandes, pode ser caro.

Crenças (marginais) a partir de mensagens

Uma vez que as mensagens foram propagadas (em uma árvore, após um número finito de passagens), a marginal em uma variável é:

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

E para um escopo de fator:

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

Estas são marginais exatas em árvores após normalização.

Computando a função de partição em uma árvore

Em uma árvore, você pode computar (Z) a partir de qualquer conjunto calibrado de crenças. Uma abordagem comum é escolher um fator (a) e computar:

[ Z = \sum_{x_{N(a)}} f_a(x_{N(a)}) \prod_{i \in N(a)} m_{i\to a}(x_i) ]

(Até convenções de normalização — muitas implementações normalizam mensagens para estabilidade e acompanham log-normalizadores separadamente.)

Complexidade e por que árvores importam

Em árvores, a BP é eficiente porque cada aresta é usada um número constante de vezes. O custo principal vem das atualizações fator-para-variável:

  • Para um fator sobre (k) variáveis discretas, cada uma com (d) estados, a soma ingênua é (O(d^k)).
  • Modelos par-a-par ((k=2)) são comuns porque mantêm os custos administráveis.

Para grafos gerais, a inferência exata pode ser reduzida à inferência em árvores agrupando nós em uma árvore de junções, mas a complexidade torna-se exponencial na largura de árvore (treewidth) (ver Algoritmo da Árvore de Junções).

Exemplo prático: BP em uma cadeia (o algoritmo forward–backward)

Uma árvore simples, mas importante, é uma cadeia, por exemplo um Modelos Ocultos de Markov. Seja os estados ocultos (x_1,\dots,x_T) formando uma cadeia com:

  • Fatores de transição (f_t(x_{t-1}, x_t))
  • Fatores de emissão/unários (g_t(x_t)) representando a evidência (y_t)

A conjunta (até normalização) é: [ p(x_{1:T}\mid y_{1:T}) \propto \left(\prod_{t=2}^T f_t(x_{t-1}, x_t)\right)\left(\prod_{t=1}^T g_t(x_t)\right) ]

Executar BP soma-produto nessa cadeia é exatamente o algoritmo forward–backward:

  • Mensagens forward: (\alpha_t(x_t)) correspondem a mensagens fator→variável da esquerda para a direita
  • Mensagens backward: (\beta_t(x_t)) correspondem a mensagens da direita para a esquerda

Então: [ p(x_t \mid y_{1:T}) \propto \alpha_t(x_t)\beta_t(x_t) ]

Isso ilustra um modelo mental útil: muitos algoritmos clássicos de programação dinâmica são casos especiais de propagação de crenças em grafos com estrutura de árvore.

Máx-produto / máx-soma para inferência MAP

Às vezes você quer a única atribuição mais provável: [ x^* = \arg\max_x p(x) ] Isso é inferência MAP (MAP inference).

Atualizações de máx-produto

Substitua somas por operações de máximo:

Fator → variável [ m_{a\to i}(x_i) = \max_{x_{N(a)\setminus i}} f_a(x_{N(a)}) \prod_{j \in N(a)\setminus i} m_{j\to a}(x_j) ]

Variável → fator permanece multiplicativa: [ m_{i\to a}(x_i) = \prod_{b \in N(i)\setminus a} m_{b\to i}(x_i) ]

Na prática, é comum trabalhar no espaço log, transformando produtos em somas e máx-produto em máx-soma:

  • mensagens em (\log)
  • atualização usa log-sum-exp para soma-produto e max para máx-soma

Exemplo: Viterbi como máx-produto em uma cadeia

Em uma cadeia de HMM, a BP máx-produto torna-se o algoritmo de Viterbi:

  • soma-produto computa marginais de estado (p(x_t\mid y))
  • máx-produto computa o melhor caminho único (x_{1:T}^*)

Para MAP, você também precisa de ponteiros de retorno (backpointers) (escolhas de argmax) para reconstruir a atribuição completa.

Propagação de crenças com laços (inferência aproximada em grafos com ciclos)

Quando o grafo tem ciclos, você ainda pode executar as mesmas atualizações de mensagens. Isso é BP com laços.

O que muda com laços?

  • Mensagens podem circular indefinidamente.
  • Não há garantia de convergência.
  • Se convergir, as crenças resultantes não são garantidamente exatas.

Ainda assim, a BP com laços é extremamente útil e frequentemente precisa na prática — notoriamente em códigos corretores de erro LDPC, onde é um método-chave de decodificação.

Pontos fixos e a aproximação de Bethe (intuição)

Os pontos fixos da BP com laços estão intimamente relacionados a pontos estacionários da energia livre de Bethe (Bethe free energy), conectando BP a métodos de inferência variacional (variational inference) (ver Inferência Variacional). Essa perspectiva explica:

  • por que a BP com laços pode funcionar bem (ela está otimizando um objetivo aproximado)
  • por que ela pode falhar (a aproximação pode ser ruim; o objetivo pode ser não convexo)

Quando a BP com laços funciona bem

  • O grafo é “localmente parecido com uma árvore” (poucos laços curtos), por exemplo muitos grafos esparsos de codificação
  • Os potenciais não são muito “pontiagudos” (não excessivamente determinísticos)
  • Amortecimento e escalonamento adequados são usados

Quando pode ter dificuldades

  • Acoplamentos fortes (restrições quase determinísticas)
  • Muitos laços curtos (por exemplo grades densas sem cuidado)
  • Posteriores multimodais
  • Escalonamento numérico ruim (subfluxo/superfluxo sem tratamento no espaço log)

Escalonamento: passagem de mensagens síncrona vs assíncrona

A ordem na qual você atualiza mensagens pode afetar dramaticamente a velocidade e a convergência.

Atualizações síncronas (paralelas)

  • Computa todas as novas mensagens a partir das mensagens da iteração anterior
  • Fácil de implementar; boa para vetorização
  • Pode oscilar em grafos com laços

Atualizações assíncronas (sequenciais)

  • Atualiza mensagens uma por vez e usa imediatamente os valores atualizados
  • Frequentemente converge mais rápido e com mais estabilidade

Escalonamento residual / por prioridade

Uma heurística comum:

  • computar um “resíduo” (quanto uma mensagem mudaria)
  • atualizar primeiro as mensagens com maior resíduo

Isso pode reduzir significativamente o número de iterações em problemas difíceis.

Convergência e truques de estabilização

Critérios de parada

Opções típicas:

  • número máximo de iterações
  • mudança máxima em qualquer mensagem abaixo de um limiar: [ \max_{(i,a),x_i} \left| m^{(t)}{i\to a}(x_i) - m^{(t-1)}{i\to a}(x_i)\right| < \epsilon ]
  • mudança nas crenças ou na log-verossimilhança aproximada abaixo de um limiar

Amortecimento (média de mensagens)

Para evitar oscilações: [ m \leftarrow (1-\lambda)m_{\text{new}} + \lambda m_{\text{old}} ] com (\lambda \in [0,1)) (por exemplo, 0.5–0.9).

Normalização

Mensagens podem ser escaladas arbitrariamente sem alterar as crenças finais normalizadas (em árvores). Na prática:

  • normalizar mensagens para somar 1 (para variáveis discretas)
  • acompanhar constantes de log-normalização se você precisar de (Z)

Domínio log para estabilidade numérica

Para soma-produto, compute atualizações fator-para-variável usando log-sum-exp para evitar subfluxo:

  • Armazene (\ell = \log m)
  • Multiplicação vira adição
  • Somatório vira logsumexp

Isso é essencial em cadeias longas (por exemplo sequências longas) ou distribuições altamente pontiagudas.

Esboço de implementação (CAM discreto par-a-par)

Para um CAM par-a-par (pairwise) com potenciais unários (\phi_i(x_i)) e potenciais par-a-par (\psi_{ij}(x_i,x_j)), uma forma comum de BP (em um grafo não direcionado) é:

[ m_{i\to j}(x_j) \propto \sum_{x_i} \phi_i(x_i),\psi_{ij}(x_i,x_j)\prod_{k\in N(i)\setminus j} m_{k\to i}(x_i) ]

Aqui vai um esboço compacto, em estilo Python, para BP com laços em um modelo par-a-par:

import numpy as np

def normalize(v):
    s = v.sum()
    return v / s if s > 0 else np.ones_like(v) / len(v)

def loopy_bp_pairwise(phi, psi, neighbors, max_iter=50, damping=0.5, tol=1e-6):
    """
    phi[i]: shape (d,) unary potential for node i
    psi[(i,j)]: shape (d,d) pairwise potential between i and j (i->rows, j->cols)
    neighbors[i]: list of neighbors of i
    """
    n = len(phi)
    d = phi[0].shape[0]

    # initialize messages m_{i->j}(x_j) as uniform
    m = {(i, j): np.ones(d) / d for i in range(n) for j in neighbors[i]}

    for it in range(max_iter):
        max_delta = 0.0
        new_m = {}

        for i in range(n):
            # precompute "incoming product" at i for each state x_i
            inc = phi[i].copy()
            for k in neighbors[i]:
                inc *= m[(k, i)]

            for j in neighbors[i]:
                # exclude j's contribution
                inc_excl = inc / m[(j, i)]

                # compute message to j: sum over x_i
                # msg(x_j) = sum_{x_i} inc_excl(x_i) * psi_{ij}(x_i, x_j)
                msg = inc_excl @ psi[(i, j)]  # (d,) @ (d,d) -> (d,)
                msg = normalize(msg)

                # damping
                msg = (1 - damping) * msg + damping * m[(i, j)]
                msg = normalize(msg)

                new_m[(i, j)] = msg
                max_delta = max(max_delta, np.max(np.abs(msg - m[(i, j)])))

        m = new_m
        if max_delta < tol:
            break

    # compute beliefs
    beliefs = []
    for i in range(n):
        b = phi[i].copy()
        for k in neighbors[i]:
            b *= m[(k, i)]
        beliefs.append(normalize(b))
    return beliefs, m

Notas:

  • Isto usa uma fórmula específica para par-a-par (comum em CAMs) em vez de nós de fator explícitos.
  • Para estabilidade e velocidade, sistemas reais frequentemente usam espaço log e operações vetorizadas.

Tratamento de evidência

Variáveis observadas são tratadas por fixação (clamping) com um fator unário:

  • Se (x_i) é observado como (x_i = c), defina (\phi_i(x_i)=\mathbb{1}[x_i=c]) (ou um potencial muito pontiagudo).
  • Em redes bayesianas, a evidência é incorporada modificando fatores de CPT ou adicionando fatores de verossimilhança.

A BP então propaga essa evidência para atualizar crenças em outros lugares.

Variáveis contínuas: propagação de crenças gaussiana

A BP não se limita a variáveis discretas. Em modelos linear-gaussianos (linear-Gaussian), as mensagens permanecem gaussianas, e a BP pode ser realizada com médias/variâncias (ou na forma de informação). Em árvores, isso é exato e se relaciona estreitamente a:

  • Filtro de Kalman (cadeias)
  • Campos aleatórios gaussianos de Markov (matrizes de precisão esparsas)
  • Problemas de SLAM / fusão de sensores

A BP gaussiana também pode ser executada “com laços” em grafos com ciclos; a convergência depende de propriedades do sistema linear subjacente.

Aplicações em IA e AM

A BP é uma técnica fundamental em modelagem probabilística:

  • Códigos corretores de erro (decodificação LDPC/Turbo): BP com laços em grafos bipartidos esparsos é um decodificador padrão.
  • Visão computacional: inferência aproximada em CAMs de grade para remoção de ruído, segmentação, estéreo (frequentemente com potenciais par-a-par).
  • Robótica (SLAM): grafos de fatores com BP gaussiana ou métodos relacionados para estimação de estado.
  • Predição estruturada (structured prediction): inferência em Campos Aleatórios Condicionais (CRFs) (Conditional Random Fields (CRFs)) frequentemente usa BP com laços (ou métodos relacionados) para computar marginais/gradientes.
  • Aprendizado com variáveis latentes: BP pode servir como o motor de inferência do passo E em Maximização de Expectativa (Expectation-Maximization) quando a inferência exata é viável (por exemplo, árvores) ou aproximada (com laços).

Relação com outros métodos de inferência

Principais conclusões

  • Propagação de crenças (soma-produto) computa marginais exatas e (Z) em árvores usando atualizações locais de mensagens.
  • Máx-produto / máx-soma adapta BP para inferência MAP, recuperando algoritmos clássicos como Viterbi em cadeias.
  • BP com laços aplica as mesmas atualizações em grafos com ciclos como uma aproximação; pode ser muito eficaz, mas pode não convergir ou pode convergir para crenças imprecisas.
  • O desempenho prático depende de escalonamento, amortecimento, normalização/cálculo no espaço log, e da estrutura dos fatores (especialmente fatores par-a-par vs fatores de ordem superior).

Se você estiver aprendendo BP em contexto, ela se combina naturalmente com artigos sobre Grafos de Fatores, Campos Aleatórios de Markov e Redes Bayesianas, pois a BP é um dos principais “motores de inferência” usados nessas representações.