Modelos de Entropia Máxima (MaxEnt / Modelos Log-Lineares)

Visão geral

Modelos de máxima entropia (Maximum Entropy; MaxEnt), também chamados de modelos log-lineares (log-linear models), são uma família de modelos probabilísticos que representam uma distribuição usando um conjunto ponderado de funções de características (feature functions). Eles são amplamente usados para classificação e predição estruturada (structured prediction), especialmente no processamento de linguagem natural (Natural Language Processing; NLP) clássico, porque permitem combinar muitos sinais sobrepostos e não independentes sem fazer suposições fortes de independência (ao contrário do Bayes ingênuo (Naive Bayes)).

O termo “máxima entropia” vem do princípio de modelagem de que, entre todas as distribuições que satisfazem certas restrições (tipicamente igualar estatísticas observadas), devemos escolher aquela com a maior entropia — isto é, a distribuição menos comprometida, consistente com o que sabemos.

Na prática, a maioria dos modelos MaxEnt é treinada por estimação de máxima verossimilhança (maximum likelihood estimation, MLE) (frequentemente um problema de otimização convexo (convex)), geralmente com regularização (regularization) (equivalentemente, estimação a posteriori máxima (maximum a posteriori, MAP) com uma distribuição a priori (prior)). Eles estão fortemente conectados a:

Regressão Linear/Logística (a regressão logística (logistic regression) é um modelo MaxEnt condicional)
Distribuições da família exponencial (exponential family) (modelos log-lineares são modelos de família exponencial)
Modelos condicionais em processamento de linguagem natural (por exemplo, classificadores MaxEnt, Modelos de Markov de Máxima Entropia (MaxEnt Markov Models; MEMMs), Campos Aleatórios Condicionais (Conditional Random Fields; CRFs))
Componentes de modelos gráficos não direcionados como campos aleatórios de Markov (Markov random fields) e Redes Lógicas de Markov (Markov Logic Networks)

A ideia central: distribuições a partir de características e pesos

Um modelo log-linear define probabilidades usando características (f_k(\cdot)) e pesos (w_k).

Forma log-linear conjunta (incondicional)

Para um resultado (x) (que pode ser um objeto estruturado), defina:

[ p_w(x) = \frac{1}{Z(w)} \exp\left(\sum_{k=1}^K w_k f_k(x)\right) ]

(f_k(x)) são funções de características (frequentemente indicadores binários, contagens ou sinais em valores reais)
(w_k) são pesos aprendíveis
(Z(w)) é a função de partição (partition function) que garante normalização:

[ Z(w) = \sum_x \exp\left(\sum_k w_k f_k(x)\right) ]

É por isso que esses modelos são chamados de log-lineares: o logaritmo da probabilidade é linear nas características:

[ \log p_w(x) = \sum_k w_k f_k(x) - \log Z(w) ]

Forma log-linear condicional (classificador MaxEnt)

Em aprendizado supervisionado, muitas vezes queremos (p(y \mid x)):

[ p_w(y \mid x) = \frac{1}{Z(x; w)} \exp\left(\sum_{k=1}^K w_k f_k(x, y)\right) ]

onde

[ Z(x; w) = \sum_{y'} \exp\left(\sum_k w_k f_k(x, y')\right) ]

Essa forma condicional é o classificador MaxEnt padrão usado em processamento de linguagem natural.

De onde vem a “máxima entropia” (o princípio de modelagem)

Suponha que queiramos uma distribuição (p(x)), mas só confiemos em certas estatísticas observadas dos dados — por exemplo, valores esperados de características.

Sejam as restrições:

[ \mathbb{E}_{p}[f_k(X)] = \hat{\mathbb{E}}[f_k(X)] \quad \text{for all } k ]

Entre todos os (p) que satisfazem essas restrições, MaxEnt escolhe aquele com máxima entropia de Shannon (Shannon entropy):

[ H(p) = -\sum_x p(x)\log p(x) ]

Usando multiplicadores de Lagrange (Lagrange multipliers), a solução tem a forma exponencial/log-linear:

[ p(x) \propto \exp\left(\sum_k w_k f_k(x)\right) ]

Assim, as perspectivas “MaxEnt” e “log-linear” são duas faces da mesma moeda:

MaxEnt: escolher a distribuição menos comprometida que satisfaz restrições de expectativa de características
Log-linear: parametrizar uma distribuição flexível de família exponencial via características e aprender pesos a partir de dados

Em fluxos de trabalho modernos de aprendizado de máquina (machine learning, ML), as pessoas frequentemente pulam a derivação explícita por maximização de entropia e vão direto para o treinamento por máxima verossimilhança da forma log-linear.

Um exemplo prático: classificação de spam com um modelo MaxEnt

Seja (x) um e-mail e (y \in {\text{spam}, \text{ham}}). Defina características indicadoras binárias como:

(f_{\text{free}}(x, y) = \mathbf{1}[\text{“free” appears in } x \ \wedge\ y=\text{spam}])
(f_{\text{meeting}}(x, y) = \mathbf{1}[\text{“meeting” appears in } x \ \wedge\ y=\text{ham}])

Então:

[ p(y \mid x) \propto \exp\left(w_{\text{free}} f_{\text{free}}(x,y) + w_{\text{meeting}} f_{\text{meeting}}(x,y) + \cdots\right) ]

Interpretação:

Se a palavra “free” aparece e (w_{\text{free}}) é grande e positivo, isso aumenta a pontuação para spam.
Muitas características podem se sobrepor; MaxEnt não supõe independência condicional entre palavras.

Isso é conceitualmente semelhante à regressão logística, mas formulado como “características de ((x,y))” em vez de “características de (x)” apenas.

Relação com regressão logística e regressão softmax

Regressão logística binária

A regressão logística binária modela:

[ p(y=1 \mid x) = \sigma(w^\top \phi(x)) ]

Isso pode ser escrito como um modelo log-linear condicional definindo:

(f_k(x, y)=\phi_k(x)) quando (y=1), e 0 quando (y=0), além de uma característica de viés (bias feature).

Então:

[ p(y \mid x) = \frac{\exp(w^\top \phi(x) \cdot \mathbf{1}[y=1])}{1 + \exp(w^\top \phi(x))} ]

Assim, a regressão logística é um modelo MaxEnt (família exponencial condicional) com uma parametrização específica de características.

Regressão multiclasse (softmax)

Para (y \in {1,\dots,C}):

[ p(y \mid x) = \frac{\exp(W_y^\top \phi(x))}{\sum_{c=1}^C \exp(W_c^\top \phi(x))} ]

Esse é o modelo MaxEnt multiclasse, também chamado de classificador de máxima entropia (maximum entropy classifier) na literatura mais antiga de processamento de linguagem natural.

Veja também: Regressão Linear/Logística

Modelos log-lineares como distribuições de família exponencial

Modelos log-lineares são uma forma padrão da família exponencial:

[ p(x \mid \eta) = h(x)\exp\left(\eta^\top T(x) - A(\eta)\right) ]

Mapeando para a notação MaxEnt/log-linear:

parâmetro natural (natural parameter) (\eta \leftrightarrow w)
estatísticas suficientes (sufficient statistics) (T(x) \leftrightarrow f(x))
função log-partição (log-partition function) (A(\eta) \leftrightarrow \log Z(w))

Essa conexão é importante porque fornece:

Propriedades de convexidade da log-verossimilhança (em configurações típicas)
Uma expressão limpa para gradientes em termos de estatísticas suficientes esperadas (expected sufficient statistics)
Ligações com máxima verossimilhança, estimação MAP e geometria da informação (information geometry)

Treinamento via máxima verossimilhança (frequentemente convexo)

Assuma dados supervisionados ({(x_i, y_i)}_{i=1}^N) e um modelo condicional (p_w(y\mid x)).

Objetivo de log-verossimilhança

[ \ell(w) = \sum_{i=1}^N \log p_w(y_i \mid x_i) = \sum_{i=1}^N \left(\sum_k w_k f_k(x_i, y_i) - \log Z(x_i; w)\right) ]

Para a classificação MaxEnt padrão, a log-verossimilhança negativa é convexa em (w) (porque (\log Z) é um termo log-sum-exp (log-sum-exp)).

Gradiente: “contagens empíricas menos contagens esperadas”

O gradiente (gradient) da log-verossimilhança condicional é:

[ \frac{\partial \ell(w)}{\partial w_k} = \sum_{i=1}^N \left(f_k(x_i, y_i) - \mathbb{E}_{p_w(y \mid x_i)}[f_k(x_i, y)]\right) ]

Esta é a principal ideia computacional:

Aumentar pesos para características que aparecem nos dados
Diminuir pesos se o modelo já as “espera” demais

Um esboço mínimo de treinamento (ascensão do gradiente em lote)

# Pseudocode for conditional MaxEnt / softmax regression training
initialize w

repeat until convergence:
    grad = 0
    for (x_i, y_i) in data:
        # compute model distribution over labels
        p = softmax(scores(y) = sum_k w[k] * f_k(x_i, y) for y in labels)

        # accumulate gradient
        for k in features:
            grad[k] += f_k(x_i, y_i) - sum_y p[y] * f_k(x_i, y)

    w += learning_rate * grad

Na prática, você tipicamente usa:

variantes de Descida do Gradiente (Gradient Descent) (descida do gradiente estocástica (stochastic gradient descent, SGD), Adam) para conjuntos de dados grandes
métodos quase-Newton (Quasi-Newton methods) como L-BFGS para problemas pequenos a médios (comum em toolkits clássicos de MaxEnt para processamento de linguagem natural)

Regularização (e a visão bayesiana)

Sem regularização, modelos log-lineares podem sobreajustar (overfit), especialmente com muitas características esparsas.

Regularização L2 (prior Gaussiano)

Adicione uma penalidade:

[ \ell_{\text{reg}}(w) = \ell(w) - \frac{\lambda}{2}|w|^2 ]

O gradiente se torna:

[ \frac{\partial \ell_{\text{reg}}}{\partial w_k} = \frac{\partial \ell}{\partial w_k} - \lambda w_k ]

Interpretação:

Equivalente à estimação MAP com um prior Gaussiano (Gaussian prior) de média zero sobre os pesos
Incentiva pesos pequenos e suaves

Regularização L1 (esparsidade)

[ \ell_{\text{reg}}(w) = \ell(w) - \lambda |w|_1 ]

Incentiva muitos pesos a se tornarem exatamente zero
Útil quando você tem conjuntos gigantes de características e quer seleção de características
A otimização frequentemente usa descida por coordenadas (coordinate descent) ou métodos proximais (proximal methods)

Tópico relacionado: Modelos Bayesianos

Modelos condicionais vs conjuntos (e por que isso importa)

Um ponto comum de confusão: MaxEnt/log-linear pode ser usado para definir distribuições conjuntas (p(x)) ou distribuições condicionais (p(y\mid x)).

MaxEnt condicional (por exemplo, regressão logística) foca em predição e evita modelar (p(x)).
- Frequentemente mais fácil: a função de partição soma sobre rótulos (y), que são poucos.
Modelos log-lineares conjuntos (por exemplo, campos aleatórios de Markov) definem (p(x)) para (x) complexos.
- Frequentemente mais difícil: a função de partição soma sobre todas as configurações de (x), o que pode ser exponencial.

Essa distinção impacta fortemente o custo computacional e quais algoritmos de inferência você precisa.

Modelos log-lineares em modelos gráficos: MRFs e fatores

Modelos gráficos não direcionados (undirected graphical models) (campos aleatórios de Markov) comumente usam parametrizações log-lineares:

[ p(x) = \frac{1}{Z} \exp\left(\sum_{c \in \mathcal{C}} \psi_c(x_c)\right) ]

Cada potencial de clique (clique potential) (\psi_c(x_c)) é frequentemente representado como uma soma ponderada de características:

[ \psi_c(x_c) = \sum_k w_k f_k(x_c) ]

Esta é a ponte padrão entre “modelos log-lineares” e modelos gráficos probabilísticos.

Quando o grafo tem ciclos ou espaços de estados grandes, computar (Z) e expectativas pode ser intratável, exigindo métodos de inferência aproximada (por exemplo, propagação de crenças com ciclos (loopy belief propagation), métodos variacionais (variational methods), Monte Carlo por cadeias de Markov (Markov chain Monte Carlo, MCMC)).

Redes Lógicas de Markov: modelos log-lineares sobre mundos

Redes Lógicas de Markov (MLNs) combinam lógica de primeira ordem (first-order logic) com modelagem probabilística ao anexar pesos a fórmulas. Cada fórmula atua como uma (suave) restrição; a probabilidade de um mundo (world) (x) é:

[ p(x) \propto \exp\left(\sum_j w_j n_j(x)\right) ]

onde (n_j(x)) conta quantas instanciações (groundings) da fórmula (j) são satisfeitas no mundo (x).

Isso é diretamente um modelo log-linear:

características = contagens de satisfação de fórmulas
pesos = força de cada fórmula
função de partição = normalizador sobre todos os mundos possíveis (geralmente enorme)

MLNs são poderosas, mas podem ser computacionalmente caras, então são mais comuns em domínios de nicho onde a estrutura relacional é essencial.

MaxEnt para sequências: MEMMs e CRFs (processamento de linguagem natural clássico)

Modelos MaxEnt foram historicamente centrais ao processamento de linguagem natural porque lidam bem com muitas características sobrepostas (lexicais, ortográficas, contextuais).

Modelos de Markov de Máxima Entropia (MEMMs)

Um MEMM é um modelo de sequência que usa um classificador MaxEnt para cada transição:

[ p(y_t \mid y_{t-1}, x, t) \propto \exp(w^\top f(y_{t-1}, y_t, x, t)) ]

MEMMs são fáceis de treinar, mas sofrem do problema de viés de rótulo (label bias problem): modelos normalizados localmente podem preferir estados com menos transições de saída.

Campos Aleatórios Condicionais (CRFs)

Um CRF de cadeia linear define:

[ p(y \mid x) = \frac{1}{Z(x)} \exp\left(\sum_t w^\top f(y_{t-1}, y_t, x, t)\right) ]

CRFs são normalizados globalmente, o que ajuda a evitar viés de rótulo e tipicamente produz melhor desempenho em rotulagem de sequências. O treinamento envolve programação dinâmica (dynamic programming) (algoritmo forward-backward (forward-backward)) para computar expectativas de forma eficiente em estruturas de cadeia.

Tópico relacionado: Modelos Ocultos de Markov (HMMs são gerativos (generative); CRFs são discriminativos (discriminative))

Inferência e a função de partição

A função de partição (Z) (ou (Z(x)) para modelos condicionais) é central:

Para classificação com um conjunto pequeno de rótulos, (Z(x)) é barato de computar (soma sobre classes).
Para saídas estruturadas (sequências, árvores) ou modelos conjuntos (MRFs), computar (Z) pode exigir:
- Programação dinâmica exata (cadeias, árvores)
- Inferência aproximada (grafos com ciclos)

O treinamento tipicamente requer não apenas (Z), mas também contagens esperadas de características sob o modelo. É aqui que o custo de inferência domina.

Engenharia de características: o que faz MaxEnt funcionar bem

Modelos MaxEnt são lineares nas características, então o desempenho depende fortemente do desenho de características.

Padrões comuns de características em processamento de linguagem natural/classificação:

Características indicadoras (indicator features): (1[\text{condition}])
Conjunções (conjunctions): identidade da palavra + tag vizinha, capitalização + sufixo etc.
Contagens / características em valores reais: TF-IDF, pontuações de léxicos, dimensões de embeddings (embeddings) (historicamente menos comum, mas possível)

Como o modelo é log-linear, características correlacionadas podem coexistir; a regularização ajuda a evitar instabilidade.

Um modelo mental útil:

MaxEnt é uma linha de base (baseline) forte quando você consegue escrever boas características.
Modelos profundos (deep models) reduzem características manuais, mas podem ser mais pesados para treinar e colocar em produção.

Aplicações práticas

Modelos MaxEnt/log-lineares ainda são úteis em sistemas modernos, especialmente quando você precisa de:

Probabilidades bem calibradas (well-calibrated probabilities)
Interpretabilidade (interpretability) (pesos ligados a características significativas)
Linhas de base convexas fortes
Eficiência com entradas esparsas

Aplicações típicas:

Classificação de texto (tópico, sentimento, spam)
Classificação de intenção e rotulagem de slots (frequentemente com CRFs para sequências)
Componentes de ranqueamento (como modelos lineares de pontuação com variantes de log-loss)
Como fatores/potenciais dentro de sistemas probabilísticos maiores (MRFs, MLNs)

Em muitos cenários tabulares, ensembles de árvores (tree ensembles) podem superá-los; veja Árvores de Decisão e Ensembles. Mas MaxEnt continua sendo uma linha de base preferida devido à simplicidade e confiabilidade.

Conexões e contrastes com modelos relacionados

Bayes ingênuo: gerativo com suposições de independência; rápido e forte com poucos dados, mas frequentemente menos preciso assintoticamente do que regressão logística/MaxEnt.
- Veja k-vizinhos mais próximos, Bayes ingênuo (k-nearest neighbors, k-NN)
Máquinas de vetores de suporte (Support Vector Machines, SVMs): classificadores discriminativos baseados em margem; frequentemente fortes, mas não produzem probabilidades diretamente sem calibração.
- Veja Máquinas de Vetores de Suporte
Métodos de kernel (kernel methods): podem ser vistos como o uso de espaços de características ricos; regressão logística com kernels é possível (modelo log-linear condicional kernelizado (kernelized conditional log-linear model)).
- Veja Métodos de Kernel

Resumo

Modelos de máxima entropia / log-lineares definem distribuições de probabilidade da forma:

Conjunta: (p(x) \propto \exp(w^\top f(x)))
Condicional: (p(y\mid x) \propto \exp(w^\top f(x,y)))

Eles surgem do princípio da máxima entropia sob restrições de correspondência de características e, na prática, são treinados via máxima verossimilhança (regularizada), frequentemente resultando em otimização convexa para classificação condicional padrão.

Eles são:

Equivalentes a regressão logística / regressão softmax em configurações supervisionadas comuns
Instâncias da família exponencial
Blocos fundamentais para MRFs, CRFs e Redes Lógicas de Markov

Apesar do avanço do aprendizado profundo (deep learning), modelos MaxEnt/log-lineares permanecem importantes como linhas de base interpretáveis e fortes, e como componentes em modelagem probabilística estruturada.