Campos Aleatórios de Markov (Redes de Markov)

Visão geral

Um Campo Aleatório de Markov (MRF, Markov Random Field) — também chamado de rede de Markov (Markov network) — é um modelo gráfico probabilístico não direcionado (undirected probabilistic graphical model) para representar uma distribuição conjunta (joint distribution) sobre muitas variáveis aleatórias usando um grafo mais um conjunto de funções de potencial (potential functions). MRFs são amplamente usados quando as interações são naturalmente simétricas (sem uma direção clara de causalidade), como relações espaciais em imagens, conexões em redes sociais ou restrições de compatibilidade em predição estruturada.

Um MRF combina duas ideias:

Independências condicionais (conditional independencies) codificadas por um grafo não direcionado (undirected graph).
Uma fatoração (factorization) da distribuição conjunta em potenciais de cliques (clique potentials), produzindo uma distribuição de Gibbs (log-linear) (Gibbs (log-linear) distribution).

Os MRFs ficam ao lado de Redes Bayesianas na família de modelos gráficos probabilísticos (probabilistic graphical models) e se conectam diretamente a Grafos de Fatores, Propagação de Crenças (Soma-Produto / Passagem de Mensagens), Campos Aleatórios Condicionais (CRFs, Conditional Random Fields) e Redes Lógicas de Markov (MLNs, Markov Logic Networks).

Estrutura do grafo e propriedades de Markov

Grafos não direcionados e vizinhanças

Um MRF é definido sobre um grafo não direcionado (G = (V, E)):

Cada nó (i \in V) é uma variável aleatória (X_i).
Cada aresta ((i,j) \in E) representa uma dependência direta (não necessariamente causal).

Um conceito central é o manto de Markov (Markov blanket) de um nó: em um MRF, o manto de Markov de (X_i) é simplesmente seus vizinhos no grafo: [ \text{MB}(X_i) = {X_j : (i,j) \in E}. ]

Propriedades de independência condicional (Markov)

MRFs codificam independências condicionais via separação no grafo. Formas equivalentes comuns (sob suposições brandas de positividade) são:

Propriedade de Markov local (local Markov property):
(X_i) é condicionalmente independente de todos os não-vizinhos dado seus vizinhos: [ X_i \perp X_{V \setminus ({i}\cup \text{MB}(i))} \mid X_{\text{MB}(i)}. ]
Propriedade de Markov global (global Markov property):
Se um conjunto de nós (S) separa (A) de (B) no grafo, então [ X_A \perp X_B \mid X_S. ]

Este é o principal ganho representacional: o grafo declara de forma compacta quais variáveis não interagem diretamente uma vez que você condiciona em uma fronteira apropriada.

Dos grafos às probabilidades: potenciais de cliques e distribuições de Gibbs

Fatoração por cliques

Diferentemente das redes bayesianas (que fatoram via probabilidades condicionais), os MRFs fatoram usando potenciais (potentials) sobre cliques (cliques) (subconjuntos totalmente conectados de nós). A forma padrão é:

[ P(x) = \frac{1}{Z}\prod_{C \in \mathcal{C}} \psi_C(x_C) ]

(\mathcal{C}) é um conjunto de cliques (frequentemente cliques maximais).
(\psi_C(x_C) \ge 0) é um potencial de clique (clique potential) (não necessariamente normalizado).
(Z) é a função de partição (partition function): [ Z = \sum_x \prod_{C \in \mathcal{C}} \psi_C(x_C) ] garantindo que (P(x)) some 1.

Como potenciais não são probabilidades, você pode pensá-los como escores de compatibilidade (compatibility scores): (\psi) maior significa atribuições mais “compatíveis”.

Visão por energia (distribuição de Gibbs)

Frequentemente é conveniente trabalhar no espaço log e definir uma função de energia (energy function) (E(x)):

[ P(x) = \frac{1}{Z}\exp(-E(x)). ]

Se (\psi_C(x_C) = \exp(-E_C(x_C))), então (E(x) = \sum_C E_C(x_C)). Essa visão baseada em energia (energy-based) é especialmente comum em visão computacional e física estatística.

Teorema de Hammersley–Clifford (por que cliques?)

O teorema de Hammersley–Clifford (Hammersley–Clifford theorem) afirma (informalmente):

Se (P(x) > 0) para todas as configurações (x), então
(P) satisfaz as independências condicionais de Markov do grafo se, e somente se (iff) (P) pode ser escrita como uma distribuição de Gibbs que fatoriza sobre cliques.

Assim, o grafo não direcionado e a forma produto de fatores por cliques estão fortemente ligados — desde que a distribuição seja estritamente positiva.

MRFs pareados vs. de ordem superior

MRFs pareados

Uma subclasse muito comum é o MRF pareado (pairwise MRF), em que os fatores envolvem apenas nós e arestas:

[ P(x) = \frac{1}{Z}\left(\prod_i \psi_i(x_i)\right)\left(\prod_{(i,j)\in E}\psi_{ij}(x_i, x_j)\right). ]

Isso é popular porque:

Combina diretamente com as arestas do grafo.
Muitos algoritmos de inferência (por exemplo, passagem de mensagens, cortes em grafo para certos casos) são mais simples aqui.

MRFs de ordem superior

Em MRFs de ordem superior (higher-order), cliques podem ser maiores que 2 (por exemplo, triplas, regiões ou subconjuntos arbitrários):

[ P(x) = \frac{1}{Z}\prod_{C} \psi_C(x_C), \quad |C| \ge 3 \text{ permitido.} ]

Fatores de ordem superior podem modelar restrições mais ricas (por exemplo, “esses 5 pixels preferem compartilhar um rótulo”), mas a inferência fica mais difícil.

Um truque prático comum é representar fatores de ordem superior usando a visão de Grafos de Fatores (variáveis + nós de fator) e às vezes introduzir variáveis auxiliares (auxiliary variables) para reduzir certos termos de ordem superior a termos pareados — embora isso possa aumentar o tamanho e a complexidade do grafo.

Exemplos práticos

Exemplo 1: Modelo de Ising (MRF pareado binário)

O modelo de Ising (Ising model) é um MRF pareado clássico para variáveis binárias (x_i \in {-1, +1}):

[ P(x) \propto \exp\left(\sum_i h_i x_i + \sum_{(i,j)\in E} J_{ij} x_i x_j\right). ]

(h_i) enviesam um nó em direção a (+1) ou (-1).
(J_{ij}) incentiva concordância se (J_{ij}>0) e discordância se (J_{ij}<0).

Interpretação: cada aresta é uma restrição suave em que nós vizinhos “querem” se alinhar (ou anti-alinhar).

Exemplo 2: Remoção de ruído / suavização de imagem (MRF em grade)

Suponha que cada pixel tenha um rótulo limpo oculto (X_i) e você observe um valor ruidoso (Y_i). Um prior MRF simples sobre a imagem limpa pode favorecer suavidade por partes:

Termo unário: casar com os dados observados (fidelidade aos dados) [ \psi_i(x_i) = \exp(-\lambda \cdot \text{loss}(x_i, y_i)) ]
Termo pareado: incentivar pixels vizinhos a concordarem [ \psi_{ij}(x_i,x_j)=\exp(-\beta\cdot \mathbf{1}[x_i \ne x_j]). ]

Isso produz um modelo que equilibra explicar as observações com regularidade espacial.

Muitos sistemas de segmentação e remoção de ruído podem ser vistos como inferência MAP em um MRF (ou no cenário CRF intimamente relacionado).

Exemplo 3: Restrições relacionais (ponte para MLNs)

Em domínios de base de conhecimento ou relacionais, você pode querer restrições suaves como:

“Amigos tendem a compartilhar interesses.”
“Se uma pessoa é mãe/pai de alguém, é provável que seja mais velha.”

Quando elevadas a muitas entidades, essas se tornam grandes MRFs estruturados; Redes Lógicas de Markov (MLNs) fornecem uma linguagem de template que compila fórmulas lógicas ponderadas em um MRF.

Problemas centrais de inferência

Inferência em MRFs significa computar algo sobre (P(X)) dado um grafo e potenciais.

1) MAP / MPE (explicação mais provável)

A inferência MAP (MAP inference) encontra a atribuição mais provável:

[ x^* = \arg\max_x P(x) = \arg\max_x \prod_C \psi_C(x_C) = \arg\min_x E(x). ]

Isso também é chamado de MPE (Most Probable Explanation) quando todas as variáveis são otimizadas.

MAP é central em aplicações como segmentação (escolher a melhor rotulagem), decodificação e otimização combinatória com incerteza.

2) Inferência marginal (probabilidades a posteriori)

Inferência marginal computa probabilidades de subconjuntos, por exemplo:

[ P(X_i = x_i) \quad \text{ou} \quad P(X_i, X_j). ]

Marginais são necessárias para estimativas de incerteza, perdas esperadas e aprendizado (pois gradientes frequentemente requerem expectativas sob o modelo).

3) A função de partição \(Z\)

Computar (Z) (ou (\log Z)) é crucial para:

Avaliação exata de verossimilhança
Aprendizado por máxima verossimilhança
Comparação de modelos

Infelizmente, para grafos gerais com ciclos, computar (Z) é intratável (#P-hard).

Inferência exata (quando é viável)

A inferência exata é tratável principalmente quando o grafo tem pequena largura de árvore (treewidth).

Árvores: passagem de mensagens / propagação de crenças

Se o grafo do MRF é uma árvore, a propagação de crenças (belief propagation) computa marginais exatas eficientemente via mensagens locais. Veja Propagação de Crenças (Soma-Produto / Passagem de Mensagens).

Para um MRF pareado em árvore, uma mensagem soma-produto típica tem a forma: [ m_{i\to j}(x_j) = \sum_{x_i}\psi_i(x_i)\psi_{ij}(x_i,x_j)\prod_{k \in \mathcal{N}(i)\setminus j} m_{k\to i}(x_i). ]

Uma variante max-produto similar resolve MAP em árvores.

Grafos gerais com pequena largura de árvore: árvore de junção

Se o grafo não é uma árvore, mas tem pequena largura de árvore, você pode:

Triangular o grafo
Construir uma árvore de junção de cliques
Rodar passagem de mensagens entre cliques

Isso é exato, mas pode explodir exponencialmente com a largura de árvore — frequentemente inviável para grafos de visão em grade, a menos que sejam estreitos.

Inferência aproximada (o caso comum)

A maioria dos MRFs interessantes tem ciclos e é grande demais para inferência exata. Métodos aproximados se agrupam em várias famílias.

Propagação de crenças com ciclos

Executar propagação de crenças em grafos com ciclos (“loopy BP”) frequentemente funciona bem na prática, mas não há garantia de convergência nem de exatidão. É amplamente usada em códigos de correção de erros e em alguns modelos de visão.

Amostragem MCMC (por exemplo, amostragem de Gibbs)

A amostragem de Gibbs (Gibbs sampling) amostra iterativamente cada variável condicionada em seus vizinhos: [ P(x_i \mid x_{-i}) = P(x_i \mid x_{\mathcal{N}(i)}). ]

Isso usa diretamente a propriedade de Markov local. Pode aproximar marginais e expectativas, mas pode misturar lentamente em modelos fortemente acoplados.

Um esboço mínimo de um amostrador de Gibbs para um MRF pareado binário poderia ser:

import numpy as np

def gibbs_step(x, unary_logpot, pair_logpot, neighbors):
    """
    x: (n,) current binary state in {0,1}
    unary_logpot[i, xi] gives log ψ_i(xi)
    pair_logpot[(i,j)][xi, xj] gives log ψ_ij(xi, xj) for ordered pair i<j
    neighbors[i] is list of adjacent nodes
    """
    n = len(x)
    for i in range(n):
        logp = np.zeros(2)
        for xi in (0, 1):
            s = unary_logpot[i, xi]
            for j in neighbors[i]:
                a, b = (i, j) if i < j else (j, i)
                xj = x[j]
                if i < j:
                    s += pair_logpot[(a, b)][xi, xj]
                else:
                    s += pair_logpot[(a, b)][xj, xi]
            logp[xi] = s
        # normalize
        p = np.exp(logp - logp.max())
        p /= p.sum()
        x[i] = np.random.choice([0, 1], p=p)
    return x

Inferência variacional (campo médio e variacional estruturada)

Métodos variacionais aproximam (P(x)) com uma distribuição mais simples (Q(x)) (por exemplo, campo médio totalmente fatorado (Q(x)=\prod_i Q_i(x_i))) minimizando a divergência KL. Eles frequentemente escalam bem e fornecem aproximações determinísticas.

Aproximações de MAP baseadas em otimização

A inferência MAP pode ser atacada via:

Cortes em grafo (graph cuts) para certas funções de energia binárias/submodulares (comum em visão clássica).
Relaxações LP (LP relaxations) e decomposição dual (dual decomposition).
Métodos com reponderação por árvores (tree-reweighted methods) (TRW), que se relacionam a limites convexos sobre (\log Z).

Essas abordagens tratam MAP como um problema de otimização sobre variáveis discretas, às vezes produzindo soluções globalmente ótimas em casos especiais.

Aprendizado de parâmetros de MRF (e às vezes da estrutura)

Em muitos usos de ML, a estrutura do grafo é fixa e você aprende parâmetros dos potenciais.

Parametrização log-linear / baseada em características

Uma parametrização comum torna os potenciais exponenciais em características ponderadas:

[ P_\theta(x) = \frac{1}{Z(\theta)}\exp\left(\sum_k \theta_k f_k(x)\right) ]

(f_k(x)) podem ser contagens de padrões locais (por exemplo, concordância de rótulos em uma aresta, ou uma característica que casa com uma observação).
Isso torna os MRFs primos próximos de modelos log-lineares (log-linear models) e modelos baseados em energia (energy-based models).

Máxima verossimilhança e o problema da função de partição

Dado dados ({x^{(n)}}), o aprendizado por máxima verossimilhança requer gradientes como:

[ \frac{\partial}{\partial \theta_k}\log P_\theta(x) = f_k(x) - \mathbb{E}{P\theta}[f_k(X)]. ]

O segundo termo exige expectativas sob o modelo, o que tipicamente requer inferência (aproximada) — frequentemente a parte mais difícil.

Estratégias comuns de aprendizado

Máxima verossimilhança com inferência aproximada: usar MCMC, loopy BP ou métodos variacionais para aproximar expectativas.
Pseudo-verossimilhança (pseudo-likelihood): substituir a verossimilhança conjunta por um produto de condicionais locais: [ \prod_i P(x_i \mid x_{\mathcal{N}(i)}), ] evitando (Z). Frequentemente eficaz para MRFs grandes, embora possa ser estatisticamente menos eficiente.
Divergência contrastiva (contrastive divergence) (popular em modelos ao estilo máquina de Boltzmann): aproximar a expectativa do modelo com execuções curtas de MCMC.
Correspondência de escores / abordagens de contraste de ruído (score matching / noise-contrastive approaches): alternativas que podem evitar (Z) explícito em alguns cenários (mais comum na literatura contínua/EBM).

O aprendizado de estrutura (aprender arestas/cliques) é possível, mas geralmente mais difícil; frequentemente usa penalidades de esparsidade, testes de independência condicional ou busca baseada em pontuação.

Relação com CRFs, grafos de fatores e MLNs

MRFs vs CRFs

Um Campos Aleatórios Condicionais (CRFs) modela uma distribuição condicional: [ P(y \mid x) \propto \prod_C \psi_C(y_C, x), ] em que a entrada observada (x) influencia os potenciais. CRFs podem ser vistos como MRFs sobre as variáveis de saída (y), mas condicionados em (x). Isso evita modelar (P(x)) e frequentemente é melhor para tarefas de predição.

Na prática:

MRF: modelo conjunto gerativo sobre todas as variáveis.
CRF: modelo discriminativo focado em (P(\text{rótulos} \mid \text{observações})).

Grafos de fatores: uma representação unificadora

Grafos de Fatores representam explicitamente fatores (potenciais) como nós em um grafo bipartido. Muitos algoritmos de MRF ficam mais limpos na forma de grafo de fatores, especialmente quando cliques de ordem superior estão presentes.

Redes Lógicas de Markov: MRFs com templates

Redes Lógicas de Markov (MLNs) combinam lógica de primeira ordem com MRFs tratando cada fórmula instanciada (grounded) como uma característica (potencial) com um peso. Isso produz MRFs muito grandes com estrutura repetida; métodos de inferência elevada (lifted inference) (veja Inferência Elevada (Inferência Probabilística Elevada)) exploram simetrias para acelerar a inferência.

Aplicações

MRFs permanecem fundamentais em IA e ML:

Visão computacional: remoção de ruído, segmentação, estéreo, fluxo óptico (frequentemente via minimização de energia MAP).
Estatística espacial / geoestatística: modelagem de correlações espaciais (por exemplo, MRFs gaussianos em domínios contínuos).
Biologia computacional: mapas de contato de proteínas, redes gênicas, modelagem de haplótipos.
PLN (NLP) e predição estruturada: rotulagem de sequência/grafo (frequentemente via CRFs, que são MRFs condicionais).
Redes e sistemas sociais: homofilia e modelagem de influência (com cuidado na interpretação causal).
Códigos de correção de erros: decodificação como inferência em modelos gráficos com ciclos.

Notas práticas e armadilhas comuns

Potenciais não são probabilidades: (\psi) pode ser qualquer função de compatibilidade não negativa; apenas o produto normalizado é uma distribuição de probabilidade.
O custo de inferência é dominado pela estrutura do grafo: a largura de árvore (não apenas o número de nós) determina a viabilidade da inferência exata.
Trabalhe no espaço log: implemente (\log \psi) e (-E(x)) para evitar underflow.
MAP vs marginais são problemas diferentes: um método bom para MAP (por exemplo, cortes em grafo) pode não fornecer boas marginais, e vice-versa.
A qualidade da inferência aproximada varia: loopy BP pode ser excelente ou instável; MCMC pode ser assintoticamente correto, mas lento.

Resumo

Campos Aleatórios de Markov (redes de Markov) representam distribuições conjuntas complexas usando um grafo não direcionado (para independências condicionais) e potenciais de cliques (para fatoração). Sua formulação de Gibbs/energia sustenta tanto o raciocínio probabilístico quanto formulações baseadas em otimização comuns em visão e ML estruturado.

Principais pontos:

MRFs fatoram como (P(x) = \frac{1}{Z}\prod_C \psi_C(x_C)), com (Z) frequentemente intratável.
MRFs pareados são amplamente usados; MRFs de ordem superior são mais expressivos, porém mais difíceis.
Tarefas centrais de inferência incluem MAP/MPE e inferência marginal, tipicamente exigindo métodos aproximados em grafos com ciclos.
MRFs se conectam diretamente a Campos Aleatórios Condicionais (CRFs) (modelagem condicional) e Redes Lógicas de Markov (MLNs) (templates relacionais), com Grafos de Fatores fornecendo uma representação conveniente para algoritmos.

Se você quiser, posso adicionar um exemplo numérico curto resolvido (por exemplo, um MRF de 3 nós computando uma marginal e uma atribuição MAP) ou uma seção especificamente sobre Campos Aleatórios de Markov Gaussianos (GMRFs, Gaussian Markov Random Fields) para variáveis contínuas.