Campos Aleatórios Condicionais (Conditional Random Fields, CRFs)

Visão geral

Campos Aleatórios Condicionais (Conditional Random Fields, CRFs) são modelos gráficos probabilísticos discriminativos (discriminative probabilistic graphical models) projetados para problemas de predição estruturada (structured prediction) — cenários em que a saída é um objeto estruturado (por exemplo, uma sequência, uma grade ou um grafo), e não um único rótulo. Os CRFs são especialmente conhecidos por tarefas de rotulagem de sequências (sequence labeling), como etiquetagem morfossintática (part-of-speech tagging), reconhecimento de entidades nomeadas (NER) e chunking, em que as previsões para posições vizinhas são fortemente correlacionadas.

Ideia-chave: em vez de modelar uma distribuição conjunta (p(\mathbf{x}, \mathbf{y})) (como em muitos modelos gerativos (generative models)), os CRFs modelam a distribuição condicional (conditional distribution):

[ p(\mathbf{y}\mid \mathbf{x}) ]

Isso permite que os CRFs incorporem características (features) ricas e sobrepostas da entrada (\mathbf{x}), sem precisar modelar como (\mathbf{x}) é gerada.

Os CRFs se inserem na família mais ampla de modelos gráficos não direcionados, como Campos Aleatórios de Markov (Markov Random Fields / Markov Networks), e frequentemente são representados de forma conveniente como Grafos de Fatores (Factor Graphs). Muitos algoritmos de inferência para CRFs são instâncias de Propagação de Crenças (Belief Propagation) (Soma-Produto / Passagem de Mensagens).

Quais problemas os CRFs resolvem?

CRFs são mais úteis quando:

Você precisa de saídas estruturadas (por exemplo, um rótulo por token, um rótulo por pixel).
As variáveis de saída são dependentes (rótulos vizinhos influenciam uns aos outros).
Você quer usar muitas características correlacionadas da entrada sem fazer suposições fortes de independência.

Aplicações típicas incluem:

PLN: NER, POS tagging, chunking, parsing de citações, preenchimento de slots.
Bioinformática: rotulagem de sequências de DNA/proteínas.
Visão computacional: segmentação de imagens (frequentemente com CRFs estruturados em grade ou variantes CRF-RNN).
Extração de informação: rotulagem de campos em documentos semiestruturados.

Formulação de CRF

De MRFs a CRFs (modelagem condicional)

Um modelo não direcionado padrão (MRF) define uma distribuição conjunta usando potenciais de clique (clique potentials):

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

Um CRF condiciona nos inputs (\mathbf{x}), permitindo que os potenciais dependam de (\mathbf{x}):

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

Aqui:

(\mathbf{y}) são variáveis de saída estruturadas (por exemplo, tags (y_1,\dots,y_T)).
(\mathbf{x}) são entradas observadas (por exemplo, tokens, características de imagem).
(\mathcal{C}) é o conjunto de cliques/fatores no grafo.
(Z(\mathbf{x})) é a função de partição (partition function), garantindo que as probabilidades somem 1: [ Z(\mathbf{x}) = \sum_{\mathbf{y}} \prod_{c\in\mathcal{C}} \psi_c(\mathbf{y}_c,\mathbf{x}) ]

Potenciais log-lineares (a parametrização comum de CRF)

Na prática, CRFs quase sempre são parametrizados como um modelo log-linear (log-linear) (de máxima entropia (maximum entropy)). Cada potencial é o exponencial de uma soma ponderada de características:

[ p(\mathbf{y}\mid \mathbf{x}) = \frac{1}{Z(\mathbf{x})}\exp\left(\sum_{k} w_k, f_k(\mathbf{y}, \mathbf{x})\right) ]

(f_k(\mathbf{y},\mathbf{x})) são funções de características (feature functions) (frequentemente esparsas, binárias ou com valores reais).
(w_k) são pesos aprendíveis.
(Z(\mathbf{x}) = \sum_{\mathbf{y}} \exp(\sum_k w_k f_k(\mathbf{y},\mathbf{x}))).

Essa forma é poderosa porque você pode definir muitas características sobrepostas, como:

“a palavra atual começa com maiúscula”
“a palavra anterior é ‘Mr.’”
“a tag atual é PERSON e a tag anterior é O”
“o bigrama de tags é (B-ORG, I-ORG)”

CRFs de cadeia linear (o modelo padrão para sequências)

O CRF mais comum para rotulagem de sequências é o CRF de cadeia linear (linear-chain CRF), em que os rótulos formam uma cadeia:

[ y_1 - y_2 - \dots - y_T ]

Um CRF de cadeia linear típico usa termos unários (unary) (do tipo emissão (emission-like)) e pareados (pairwise) (do tipo transição (transition-like)):

[ p(\mathbf{y}\mid \mathbf{x}) = \frac{1}{Z(\mathbf{x})} \exp\left(\sum_{t=1}^{T}\sum_{k} w_k, f_k(y_t, \mathbf{x}, t)

\sum_{t=2}^{T}\sum_{k} w'k, g_k(y{t-1}, y_t, \mathbf{x}, t)\right) ]

Caso especial comum: características pareadas frequentemente dependem apenas de ((y_{t-1}, y_t)), enquanto características unárias dependem de ((y_t, \mathbf{x}, t)).

Inferência e decodificação

“Inferência” pode significar diferentes consultas:

Decodificação (inferência MAP (MAP inference)): encontrar a melhor rotulagem única [ \hat{\mathbf{y}} = \arg\max_{\mathbf{y}} p(\mathbf{y}\mid \mathbf{x}) ]
Marginais (marginals): calcular (p(y_t \mid \mathbf{x})) ou (p(y_{t-1},y_t\mid \mathbf{x}))
Função de partição (Z(\mathbf{x})): necessária para verossimilhança e marginais

Inferência exata para CRFs de cadeia linear

Como uma cadeia linear tem baixa largura de árvore (treewidth), podemos fazer programação dinâmica exata.

Avanço–retrocesso (forward–backward) (soma-produto (sum-product)) para marginais e \(Z(\mathbf{x})\)

Isso é análogo ao avanço–retrocesso de HMM, mas usa potenciais de CRF. Defina “escores locais”:

Escore unário na posição (t): (s_t(y_t))
Escore pareado entre (t-1) e (t): (a_t(y_{t-1}, y_t))

Então a probabilidade é proporcional a:

[ \exp\left(\sum_t s_t(y_t) + \sum_{t\ge2} a_t(y_{t-1},y_t)\right) ]

As mensagens forward computam somas parciais sobre prefixos; as mensagens backward fazem o mesmo para sufixos. A partir disso, você pode computar:

(Z(\mathbf{x}))
marginais de nó (p(y_t\mid \mathbf{x}))
marginais de aresta (p(y_{t-1},y_t\mid \mathbf{x}))

Em implementações, os cálculos tipicamente são feitos no espaço logarítmico (log-space) usando logsumexp para estabilidade numérica.

Viterbi (máximo-produto (max-product)) para decodificação MAP

A decodificação MAP é:

[ \hat{\mathbf{y}} = \arg\max_{\mathbf{y}} \sum_t s_t(y_t) + \sum_{t\ge 2} a_t(y_{t-1},y_t) ]

Isso é resolvido pelo algoritmo de Viterbi (Viterbi algorithm) (programação dinâmica), substituindo logsumexp por max e mantendo ponteiros de retorno (backpointers). Conceitualmente, é passagem de mensagens máximo-produto em uma cadeia.

Inferência em CRFs gerais (não em cadeia)

Quando o grafo do CRF tem ciclos (por exemplo, um CRF em grade para imagens), a inferência exata frequentemente é intratável. Abordagens comuns:

Propagação de crenças com ciclos (loopy belief propagation) (soma-produto/máximo-produto aproximados)
Veja Propagação de Crenças (Belief Propagation) (Soma-Produto / Passagem de Mensagens).
Inferência variacional de campo médio (mean-field variational inference)
Cortes em grafos (graph cuts) / α-expansão (α-expansion) para certas formas de energia (comum em visão)
Amostragem MCMC (MCMC) (frequentemente mais lenta, usada quando outras aproximações falham)
Árvore de junção (junction tree) / eliminação de variáveis (variable elimination) quando a largura de árvore é pequena o suficiente (exata, mas exponencial na largura de árvore)

Aprendizado de parâmetros

Objetivo: máxima verossimilhança condicional

Dado um conjunto de treinamento ({(\mathbf{x}^{(i)},\mathbf{y}^{(i)})}_{i=1}^N), um objetivo padrão de treinamento é a log-verossimilhança condicional regularizada (regularized conditional log-likelihood):

[ \mathcal{L}(\mathbf{w}) = \sum_{i=1}^{N}\log p(\mathbf{y}^{(i)}\mid \mathbf{x}^{(i)}; \mathbf{w})

\frac{\lambda}{2}|\mathbf{w}|_2^2 ]

(Você também pode ver regularização (L_1) para esparsidade.)

Expandindo o log da probabilidade:

[ \log p(\mathbf{y}\mid \mathbf{x}) = \mathbf{w}^\top \mathbf{F}(\mathbf{y},\mathbf{x}) - \log Z(\mathbf{x}) ]

onde (\mathbf{F}) agrega todas as contagens/somas de características.

Gradiente: contagens de características “empírico menos esperado”

A propriedade-chave de modelos log-lineares: o gradiente tem uma forma limpa:

[ \nabla \mathcal{L}(\mathbf{w}) = \sum_i \left(\mathbf{F}(\mathbf{y}^{(i)},\mathbf{x}^{(i)}) - \mathbb{E}_{p(\mathbf{y}\mid \mathbf{x}^{(i)})}[\mathbf{F}(\mathbf{y},\mathbf{x}^{(i)})]\right) - \lambda \mathbf{w} ]

Interpretação:

Aumente pesos para características que ocorrem nos rótulos gold.
Diminua pesos para características que o modelo prediz com frequência demais.

Para CRFs de cadeia linear, as expectativas são computadas eficientemente usando as marginais do avanço–retrocesso.

Métodos de otimização

Como o objetivo é convexo para CRFs padrão (lineares) (com características lineares), o treinamento frequentemente é feito com:

L-BFGS (comum em toolkits clássicos de CRF)
Descida de gradiente estocástica (stochastic gradient descent) / variantes adaptativas (Adam), especialmente em CRFs neurais
Descida por coordenadas (coordinate descent) (mais comum com (L_1))

A otimização é estreitamente relacionada a métodos padrão como Descida de Gradiente (Gradient Descent), mas CRFs exigem inferência (por exemplo, avanço–retrocesso) dentro de cada computação de gradiente.

Aprendizado aproximado para CRFs com ciclos

Quando marginais exatas são intratáveis, o aprendizado frequentemente usa aproximações como:

Pseudo-verossimilhança (pseudo-likelihood): substitui a verossimilhança global pelo produto de condicionais locais
(mais rápido, mas pode reduzir a acurácia devido ao acoplamento global mais fraco)
Treinamento por partes (piecewise training): treina fatores independentemente, aproximando (Z(\mathbf{x}))
Aproximações baseadas em BP com ciclos: usa marginais aproximadas dentro do gradiente
Métodos contrastivos (contrastive methods) (menos comuns do que em modelos profundos baseados em energia, mas conceitualmente relacionados)

CRFs neurais (prática moderna)

Um padrão moderno amplamente usado é: codificador neural (neural encoder) + camada de CRF (CRF layer).

Uma rede neural (LSTM bidirecional (BiLSTM), rede neural convolucional (CNN), Transformer (Transformer)) produz escores por posição (s_t(y)).
Um CRF adiciona uma matriz de transição treinável (A[y',y]) para impor consistência estruturada.
O treinamento maximiza a log-verossimilhança condicional do CRF; a inferência usa Viterbi.

Isso é comum em NER e preenchimento de slots: uma Arquitetura Transformer (Transformer Architecture) ou uma BiLSTM fornece representações fortes de tokens, e a camada de CRF melhora a consistência dos rótulos (por exemplo, desincentivando um I-ORG ilegal após O em marcação BIO).

Exemplo prático: reconhecimento de entidades nomeadas (linear-chain CRF)

Suponha que queremos rotular uma frase com tags BIO (B-PER, I-PER, O etc.). Um CRF é atraente porque pode aprender:

Quais palavras indicam entidades (características unárias)
Quais transições de tags são prováveis/permitidas (características pareadas)

Design de características (CRF clássico)

Para o token (t), você poderia criar características como:

word.lower=smith
is_titlecase=True
suffix_3=son
prev_word.lower=mr
next_word.lower=inc

E características de transição como:

prev_tag=B-ORG, tag=I-ORG
prev_tag=O, tag=I-ORG (frequentemente desincentivada)

Exemplo mínimo em Python (estilo sklearn-crfsuite)

# pip install sklearn-crfsuite
import sklearn_crfsuite

def token2features(sent, i):
    w = sent[i]
    feats = {
        "bias": 1.0,
        "word.lower": w.lower(),
        "isupper": w.isupper(),
        "istitle": w.istitle(),
        "isdigit": w.isdigit(),
    }
    if i > 0:
        w_prev = sent[i-1]
        feats.update({
            "-1:word.lower": w_prev.lower(),
            "-1:istitle": w_prev.istitle(),
        })
    else:
        feats["BOS"] = True
    if i < len(sent) - 1:
        w_next = sent[i+1]
        feats.update({
            "+1:word.lower": w_next.lower(),
            "+1:istitle": w_next.istitle(),
        })
    else:
        feats["EOS"] = True
    return feats

def sent2features(sent):
    return [token2features(sent, i) for i in range(len(sent))]

X_train = [sent2features(["Mr.", "Smith", "works", "at", "Acme"])]
y_train = [["O", "B-PER", "O", "O", "B-ORG"]]

crf = sklearn_crfsuite.CRF(
    algorithm="lbfgs",
    c1=0.1,  # L1
    c2=0.1,  # L2
    max_iterations=200
)

crf.fit(X_train, y_train)

Em sistemas reais, você treinaria em muitas sequências, ajustaria a regularização e avaliaria usando F1 em nível de span.

O que o CRF adiciona além da classificação por token

Se, em vez disso, você treinasse um classificador independente por token (por exemplo, regressão logística (logistic regression)), poderia obter saídas inconsistentes como:

O I-ORG I-ORG (ilegal em BIO sem B-ORG)
alternância rápida entre tipos de entidade

Um CRF aprende explicitamente (e impõe via decodificação) quais transições são plausíveis.

Relação com HMMs, MRFs e Redes de Lógica de Markov

CRFs vs HMMs

Um Modelo Oculto de Markov (Hidden Markov Model, HMM) é um modelo dirigido gerativo (generative directed model) que define uma conjunta:

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

CRFs são discriminativos:

[ p(\mathbf{y}\mid \mathbf{x}) ]

Implicações práticas:

Flexibilidade de características: CRFs podem usar características arbitrárias e sobrepostas de (\mathbf{x}) (incluindo pistas de longo alcance), enquanto HMMs tipicamente dependem de suposições de independência condicional como (x_t \perp x_{t-1}\mid y_t).
Sem necessidade de modelar inputs: CRFs evitam especificar (p(\mathbf{x})) ou distribuições de emissão.
Desempenho: em muitas tarefas supervisionadas de rotulagem com características ricas, CRFs superam HMMs.

Um modelo intermediário comum é o Modelo de Markov de Máxima Entropia (Maximum Entropy Markov Model, MEMM), que é discriminativo, mas usa transições normalizadas localmente e pode sofrer do problema de viés de rótulo (label bias problem). CRFs usam normalização global (global normalization) via (Z(\mathbf{x})), o que mitiga o viés de rótulo.

CRFs vs MRFs

CRFs podem ser vistos como campos aleatórios de Markov condicionais (conditional Markov random fields): eles herdam a estrutura de fatoração não direcionada de Campos Aleatórios de Markov, mas os potenciais dependem de entradas observadas (\mathbf{x}) e definem (p(\mathbf{y}\mid \mathbf{x})) em vez de (p(\mathbf{x},\mathbf{y})) ou (p(\mathbf{y})).

Em outras palavras:

MRF: modela uma distribuição conjunta, frequentemente para variáveis totalmente observadas ou configurações com variáveis latentes.
CRF: modela estrutura condicional, otimizada para predição.

CRFs também são comumente expressos como Grafos de Fatores, em que cada fator corresponde a um template de características ou a um potencial de clique.

CRFs vs Redes de Lógica de Markov (MLNs)

Redes de Lógica de Markov (Markov Logic Networks, MLNs) combinam lógica de primeira ordem (first-order logic) com redes de Markov ao anexar pesos a fórmulas lógicas. A instanciação (grounding) da lógica produz um modelo gráfico não direcionado em forma log-linear — conceitualmente muito semelhante às funções de características ponderadas de um CRF.

Conexões:

Ambos são modelos log-lineares sobre variáveis estruturadas.
As fórmulas ponderadas de uma MLN correspondem a características que “disparam” quando uma fórmula é satisfeita.
MLNs tipicamente são relacionais (relational) (podem quantificar sobre entidades e relações), enquanto CRFs padrão tipicamente são proposicionais (propositional) (conjunto fixo de variáveis para cada instância).

Também há variantes condicionais de MLNs (às vezes descritas como “MLNs discriminativas”), que se alinham ainda mais com o ponto de vista de CRFs: modelar certos predicados/variáveis condicionados a outros observados.

Variantes e extensões

CRFs vêm em muitas variantes dependendo da estrutura e das dependências desejadas:

CRFs de ordem superior (higher-order CRFs): fatores conectam mais de dois rótulos adjacentes (por exemplo, dependências de tags em trigramas).
CRFs de cadeia com saltos (skip-chain CRFs): conectam posições distantes (por exemplo, palavras repetidas em um documento).
CRFs semi-Markov (semi-Markov CRFs): rotulam segmentos em vez de posições individuais (útil para chunking ou spans de entidades).
CRFs em grade (grid CRFs): comuns em visão para rotulagem de pixels/patches (frequentemente com inferência aproximada).
CRFs neurais: redes neurais produzem potenciais; o CRF lida com a decodificação estruturada.

Quando usar CRFs (e quando não)

Use um CRF quando:

Dependências de saída importam e uma classificação simples e independente é inconsistente.
Você precisa de modelagem interpretável, baseada em características (CRFs clássicos).
Você tem dados rotulados suficientes para estimar padrões de transição e pesos de características.

Considere alternativas quando:

A estrutura de saída é muito complexa (grafos com alta largura de árvore) e a inferência exata é cara demais.
Você consegue resolver bem a tarefa com modelos modernos de sequência que modelam dependências diretamente (por exemplo, taggers com Transformer), embora camadas de CRF ainda possam ajudar com restrições e calibração.
Você precisa de decodificação globalmente restrita além de dependências de Markov; você pode preferir programação linear inteira ou frameworks especializados de predição estruturada.

Limitações e armadilhas práticas

Custo de inferência: mesmo em cadeias lineares, o treinamento requer avanço–retrocesso por exemplo; em grafos com ciclos pode ser muito pior.
Engenharia de características (feature engineering) (CRFs clássicos): o desempenho pode depender fortemente de templates de características.
Inferência aproximada: em CRFs gerais, aproximações podem enviesar o aprendizado e as previsões.
Dependências de longo alcance: CRFs de cadeia linear capturam principalmente interações locais entre rótulos (a menos que sejam estendidos com fatores com salto/de ordem superior).

Resumo

CRFs são uma ferramenta fundamental para predição estruturada: normalizados globalmente, log-lineares, e compatíveis com características ricas de entrada. Na forma de cadeia linear, eles suportam inferência exata eficiente (avanço–retrocesso para marginais, Viterbi para decodificação MAP) e aprendizado convexo sob parametrizações padrão baseadas em características. Conceitualmente, eles conectam ideias de modelagem não direcionada de Campos Aleatórios de Markov com treinamento discriminativo, e se relacionam a sistemas log-lineares relacionais como Redes de Lógica de Markov. Em pipelines modernos, CRFs frequentemente aparecem como uma camada de saída estruturada no topo de codificadores neurais.