Maximização da Expectativa

Visão geral

Maximização da Expectativa (Expectation–Maximization, EM) é um algoritmo iterativo de uso geral para ajustar modelos probabilísticos com variáveis latentes (latent variables) (também conhecidos como de dados incompletos (incomplete-data)) por estimação de máxima verossimilhança (maximum likelihood) ou MAP (máximo a posteriori, maximum a posteriori).

Muitos modelos ficam fáceis de estimar se você conhecesse as variáveis ocultas (atribuições de cluster, alinhamentos, entradas ausentes, estados ocultos). O EM explora isso alternando entre:

  • E-step (Expectativa): calcular expectativas de quantidades das variáveis latentes sob o posterior (posterior) atual sobre as variáveis ocultas (frequentemente “estatísticas suficientes (sufficient statistics) esperadas”).
  • M-step (Maximização): atualizar os parâmetros do modelo para maximizar o objetivo de dados completos esperado vindo do E-step.

O EM é a base por trás de:

  • modelos de mistura de gaussianas (Gaussian mixture models, GMMs)
  • modelos ocultos de Markov (Hidden Markov models, HMMs) via algoritmo de Baum–Welch (Baum–Welch)
  • Aprendizado de parâmetros em redes bayesianas (Bayesian networks) com dados ausentes

Conceitualmente, o EM é melhor entendido como ascensão por coordenadas (coordinate ascent) em um limite inferior (lower bound) da log-verossimilhança, o que explica por que ele tipicamente aumenta a verossimilhança dos dados a cada iteração.

O EM fica próximo de tópicos como Estimativa de Máxima Verossimilhança (MLE), Inferência Bayesiana, e é intimamente relacionado à Inferência Variacional.

Modelos com variáveis latentes e o problema de “dados incompletos”

Sejam os dados observados (X = {x_i}{i=1}^N), as variáveis latentes (Z = {z_i}{i=1}^N) e os parâmetros (\theta). Um modelo com variáveis latentes define uma distribuição conjunta:

[ p(X, Z \mid \theta) = \prod_{i=1}^N p(x_i, z_i \mid \theta). ]

Por que a máxima verossimilhança direta é difícil

A verossimilhança dos dados observados marginaliza as variáveis latentes:

[ p(X \mid \theta) = \sum_Z p(X, Z \mid \theta) \quad \text{(ou } \int p(X,Z\mid\theta),dZ \text{)}. ]

A log-verossimilhança é:

[ \ell(\theta) = \log p(X \mid \theta) = \log \sum_Z p(X, Z \mid \theta), ]

e o logaritmo de uma soma (ou integral) frequentemente é intratável para otimizar diretamente.

Se tivéssemos dados completos…

Se (Z) fosse conhecido, maximizaríamos a log-verossimilhança de dados completos (complete-data log-likelihood):

[ \log p(X, Z \mid \theta), ]

o que, para modelos da família exponencial (exponential family), frequentemente produz atualizações em forma fechada (closed-form) usando estatísticas suficientes (por exemplo, contagens, somas, soma de quadrados).

O EM preenche essa lacuna substituindo o (Z) desconhecido por sua distribuição posterior dados os parâmetros atuais.

O algoritmo EM (nível alto)

O EM itera o seguinte até convergir:

  1. Inicialize os parâmetros (\theta^{(0)})
  2. Para (t = 0,1,2,\dots):
    • E-step: compute (q^{(t)}(Z) \leftarrow p(Z \mid X, \theta^{(t)})) ou as expectativas necessárias sob ela
    • M-step: atualize (\theta^{(t+1)} \leftarrow \arg\max_\theta \mathbb{E}_{q^{(t)}(Z)}[\log p(X,Z\mid\theta)]) (ML), ou inclua um prior para MAP

Uma forma comum de apresentar o M-step é por meio da função Q (Q-function):

[ Q(\theta \mid \theta^{(t)}) = \mathbb{E}_{p(Z \mid X, \theta^{(t)})}\left[\log p(X, Z \mid \theta)\right]. ]

Então:

  • E-step: computar (Q(\theta \mid \theta^{(t)})) (isto é, expectativas sob o posterior atual)
  • M-step: definir (\theta^{(t+1)} = \arg\max_\theta Q(\theta \mid \theta^{(t)}))

Pseudocódigo

input: data X, model p(X,Z | θ)
initialize θ

repeat:
  # E-step
  compute posterior over latent variables:
    q(Z) ← p(Z | X, θ)
  compute expected sufficient statistics under q(Z)

  # M-step
  θ ← argmax_θ  E_q(Z)[ log p(X, Z | θ) ]     (ML)
      or argmax_θ E_q(Z)[ log p(X, Z | θ) ] + log p(θ)  (MAP)

until convergence criterion met

Por que o EM aumenta a verossimilhança: a intuição do limite inferior

A melhora monotônica do EM vem de uma desigualdade clássica (desigualdade de Jensen (Jensen’s inequality)) e de uma decomposição usando divergência KL (KL divergence).

Comece de:

[ \log p(X \mid \theta) = \log \sum_Z p(X,Z\mid \theta). ]

Introduza uma distribuição arbitrária (q(Z)) e escreva:

[ \log p(X \mid \theta) = \log \sum_Z q(Z)\frac{p(X,Z\mid \theta)}{q(Z)} \ge \sum_Z q(Z)\log \frac{p(X,Z\mid \theta)}{q(Z)}. ]

Defina o limite inferior da evidência (evidence lower bound, ELBO):

[ \mathcal{L}(q,\theta) = \mathbb{E}_q[\log p(X,Z\mid \theta)] - \mathbb{E}_q[\log q(Z)]. ]

Então:

[ \log p(X \mid \theta) = \mathcal{L}(q,\theta) + \mathrm{KL}(q(Z),|,p(Z\mid X,\theta)). ]

Como a divergência KL é sempre (\ge 0), (\mathcal{L}(q,\theta)) é um limite inferior da log-verossimilhança.

EM como ascensão por coordenadas

O EM alterna a otimização dos dois “blocos” (q) e (\theta):

  • E-step: definir (q(Z) \leftarrow p(Z\mid X,\theta^{(t)})). Isso zera o termo de KL, apertando o limite de modo que (\mathcal{L}(q,\theta^{(t)}) = \log p(X\mid \theta^{(t)})).
  • M-step: maximizar (\mathcal{L}(q^{(t)},\theta)) em relação a (\theta). Isso aumenta o ELBO, o que aumenta (ou ao menos não diminui) a log-verossimilhança.

Isso também destaca a relação do EM com a Inferência Variacional: métodos variacionais mantêm (q) em uma família restrita, enquanto o EM clássico usa o posterior exato no E-step (quando isso é tratável).

EM de ML vs EM de MAP

  • EM de máxima verossimilhança otimiza (\log p(X\mid \theta)).
  • EM de MAP otimiza (\log p(X\mid \theta) + \log p(\theta)), adicionando um prior sobre os parâmetros.

No EM de MAP, o M-step se torna:

[ \theta^{(t+1)} = \arg\max_\theta \left{ \mathbb{E}_{p(Z\mid X,\theta^{(t)})}[\log p(X,Z\mid\theta)] + \log p(\theta)\right}. ]

Priores podem:

  • evitar degenerescências (por exemplo, colapso de covariância em GMMs),
  • codificar conhecimento de domínio,
  • atuar como regularização (regularization).

Para um contexto mais amplo sobre priores e posteriores, veja Inferência Bayesiana.

Exemplo 1: Modelos de Mistura de Gaussianas (GMMs)

Um GMM assume que cada ponto (x_i \in \mathbb{R}^d) foi gerado por um de (K) componentes gaussianos:

  • atribuição latente (z_i \in {1,\dots,K})
  • pesos de mistura (\pi_k), médias (\mu_k), covariâncias (\Sigma_k)

Modelo:

[ p(z_i=k) = \pi_k,\quad p(x_i\mid z_i=k)=\mathcal{N}(x_i\mid \mu_k,\Sigma_k). ]

E-step: responsabilidades

Compute a probabilidade posterior de que o componente (k) gerou o ponto (x_i):

[ \gamma_{ik} \equiv p(z_i=k \mid x_i,\theta) = \frac{\pi_k \mathcal{N}(x_i\mid \mu_k,\Sigma_k)}{\sum_{j=1}^K \pi_j \mathcal{N}(x_i\mid \mu_j,\Sigma_j)}. ]

Esses (\gamma_{ik}) são chamados de responsabilidades (responsibilities).

M-step: atualizações de parâmetros (ML)

Seja (N_k = \sum_{i=1}^N \gamma_{ik}). Então:

[ \pi_k \leftarrow \frac{N_k}{N},\quad \mu_k \leftarrow \frac{1}{N_k}\sum_i \gamma_{ik} x_i, ]

[ \Sigma_k \leftarrow \frac{1}{N_k}\sum_i \gamma_{ik}(x_i-\mu_k)(x_i-\mu_k)^\top. ]

Notas práticas para EM em GMMs

  • A inicialização importa: o EM pode convergir para ótimos locais. Inicializações comuns incluem k-médias (k-means) (atribuições duras), responsabilidades aleatórias, ou semear as médias via k-médias++ (k-means++).
  • Degenerescência: com ML, a covariância de um componente pode colapsar em direção a zero ao redor de um único ponto, levando a verossimilhança ao infinito. Soluções incluem:
    • estimação MAP com priores (por exemplo, Normal-Inverse-Wishart),
    • piso de covariância (covariance flooring) (adicionar (\epsilon I)),
    • restringir a estrutura da covariância (diagonal, compartilhada (tied)).
  • Seleção de modelo: escolha (K) via verossimilhança em conjunto de validação (held-out likelihood) ou critérios como AIC/BIC; veja Critérios de Informação.

Esboço mínimo em estilo Python (EM para GMM)

import numpy as np

def log_gaussian(x, mu, Sigma):
    d = x.shape[-1]
    L = np.linalg.cholesky(Sigma)
    diff = x - mu
    sol = np.linalg.solve(L, diff.T).T
    quad = np.sum(sol**2, axis=1)
    logdet = 2*np.sum(np.log(np.diag(L)))
    return -0.5*(d*np.log(2*np.pi) + logdet + quad)

def em_gmm(X, K, iters=50, eps=1e-6):
    N, d = X.shape
    rng = np.random.default_rng(0)

    # init
    pi = np.ones(K) / K
    mu = X[rng.choice(N, K, replace=False)]
    Sigma = np.array([np.cov(X.T) + 1e-3*np.eye(d) for _ in range(K)])

    for _ in range(iters):
        # E-step: responsibilities
        log_r = np.stack([np.log(pi[k]) + log_gaussian(X, mu[k], Sigma[k])
                          for k in range(K)], axis=1)
        log_r -= log_r.max(axis=1, keepdims=True)
        r = np.exp(log_r)
        r /= r.sum(axis=1, keepdims=True)

        Nk = r.sum(axis=0) + 1e-12

        # M-step
        pi = Nk / N
        mu = (r.T @ X) / Nk[:, None]
        for k in range(K):
            diff = X - mu[k]
            Sigma[k] = (r[:, [k]] * diff).T @ diff / Nk[k]
            Sigma[k] += eps * np.eye(d)  # regularize

    return pi, mu, Sigma

Este código ilustra o padrão central do EM: computar “atribuições suaves” a posteriori e, em seguida, reestimar parâmetros usando estatísticas suficientes ponderadas.

Exemplo 2: Treinamento de HMM via Baum–Welch (EM)

Um modelo oculto de Markov (Hidden Markov Model, HMM) tem:

  • estados ocultos (z_t \in {1,\dots,K}) para o tempo (t=1\dots T)
  • probabilidades de transição (A_{ij}=p(z_{t}=j \mid z_{t-1}=i))
  • distribuição de emissão (emission distribution) (p(x_t \mid z_t)) (discreta ou contínua)

Dadas sequências de observações (x_{1:T}), queremos estimar parâmetros (\theta = (A,\text{emissions},\pi)).

E-step: contagens esperadas via forward–backward

O E-step requer:

  • marginais de estado (state marginals): (\gamma_t(i)=p(z_t=i\mid x_{1:T},\theta))
  • marginais de transição (transition marginals): (\xi_t(i,j)=p(z_t=i,z_{t+1}=j\mid x_{1:T},\theta))

Elas são computadas eficientemente usando o algoritmo forward–backward (forward–backward algorithm), e não enumerando todas as sequências de estados.

M-step: atualizar transições e emissões

Transições (ML):

[ A_{ij} \leftarrow \frac{\sum_{t=1}^{T-1} \xi_t(i,j)}{\sum_{t=1}^{T-1} \gamma_t(i)}. ]

A atualização das emissões depende do modelo de emissão:

  • Emissões discretas: atualizar probabilidades de símbolos usando contagens esperadas
  • Emissões gaussianas: atualizar médias/covariâncias usando somas ponderadas semelhantes às de GMMs, com pesos (\gamma_t(i))

Baum–Welch é “EM para HMMs”: compute estatísticas suficientes esperadas de caminhos ocultos e, então, maximize os parâmetros dadas essas expectativas.

Exemplo 3: Redes bayesianas com dados ausentes

Em uma rede bayesiana (BN), os parâmetros frequentemente são tabelas de probabilidade condicional (conditional probability tables, CPTs) como:

[ p(X \mid \mathrm{Pa}(X)). ]

Com dados totalmente observados, a estimação por ML se reduz a contar ocorrências de cada configuração filho/pais (com suavização opcional).

Quando algumas variáveis estão ausentes, as “contagens” são desconhecidas. O EM lida com isso naturalmente:

E-step: estatísticas suficientes esperadas (contagens suaves)

Para cada caso de dados (x^{(n)}), compute distribuições posteriores sobre as variáveis ausentes dadas as observadas e os parâmetros atuais:

[ p(\text{missing vars} \mid \text{observed vars}, \theta^{(t)}). ]

A partir desse posterior, compute contagens esperadas como:

[ \mathbb{E}\left[ \mathbf{1}{X=a,\mathrm{Pa}(X)=u} \right] ]

e acumule-as ao longo do conjunto de dados. Na prática, a inferência pode exigir métodos exatos (eliminação de variáveis (variable elimination)) ou métodos aproximados (amostragem (sampling)).

M-step: reestimação de CPT

Substitua contagens brutas por contagens esperadas e normalize:

[ \theta_{a\mid u} \leftarrow \frac{\text{expected count}(X=a,\mathrm{Pa}(X)=u)} {\sum_{a'} \text{expected count}(X=a',\mathrm{Pa}(X)=u)}. ]

Se estiver fazendo MAP, incorpore priores de Dirichlet (Dirichlet priors) como pseudo-contagens.

Essa interpretação de “contagem suave” é uma das formas mais práticas de entender o EM: compute estatísticas de dados completos esperadas e, então, ajuste como se os dados fossem completos.

Comportamento de convergência e o que o EM garante (e o que não garante)

O que o EM garante

Sob condições padrão (E-step exato, M-step exato):

  • A log-verossimilhança dos dados observados (\log p(X\mid \theta^{(t)})) é não decrescente a cada iteração.
  • O EM converge para um ponto estacionário (stationary point) da verossimilhança (ou do posterior no caso de MAP).

O que o EM não garante

  • Ótimo global: o EM pode convergir para máximos locais ou pontos de sela (saddle points).
  • Convergência rápida: pode ser lento, especialmente perto da convergência (frequentemente tem convergência linear — não quadrática).
  • Estabilidade numérica por padrão: alguns modelos têm singularidades (notavelmente o colapso de covariância em GMMs) sem regularização.

Critérios práticos de parada

Critérios comuns incluem:

  • Melhora relativa na log-verossimilhança abaixo de um limiar
  • Pequenas mudanças nos parâmetros (norma de (\theta^{(t+1)}-\theta^{(t)}))
  • Número máximo de iterações
  • Verossimilhança em conjunto de validação para de melhorar (parada antecipada (early stopping))

Variantes e extensões usadas na prática

EM generalizado (GEM)

Às vezes o M-step é difícil; o EM generalizado (Generalized EM, GEM) exige apenas aumentar a função Q em vez de maximizá-la exatamente, por exemplo, tomando alguns passos de gradiente (gradient steps). Isso pode ser útil em modelos grandes.

Essa perspectiva conecta EM à Descida do Gradiente: o M-step pode ser baseado em gradiente quando formas fechadas não estão disponíveis.

EM duro e k-médias

  • No EM suave (soft EM), (q(z_i)) é uma distribuição (responsabilidades).
  • No EM duro (hard EM), você substitui responsabilidades por uma única melhor atribuição (argmax).
    Para GMMs esféricos com covariância igual, o EM duro se assemelha ao k-médias, que pode ser visto como um caso limite.

EM estocástico / online

Para grandes conjuntos de dados, você pode atualizar estatísticas suficientes esperadas usando mini-lotes (mini-batches) (aproximação estocástica (stochastic approximation)). Isso é útil quando E-steps completos sobre todos os dados são caros.

EM com inferência aproximada

Se o posterior do E-step (p(Z\mid X,\theta)) for intratável, você pode usar:

  • aproximações baseadas em amostragem (EM de Monte Carlo (Monte Carlo EM)),
  • aproximações variacionais (levando diretamente à Inferência Variacional).

Quando usar EM (e quando não usar)

EM é uma boa escolha quando

  • Seu modelo tem variáveis latentes e está em uma família exponencial (de modo que estatísticas suficientes esperadas levam a M-steps simples).
  • Posteriores (p(Z\mid X,\theta)) são tratáveis (ou podem ser bem aproximados).
  • Você quer clusterização/segmentação probabilística interpretável (por exemplo, GMMs, HMMs).
  • Você tem dados ausentes sob suposições como “ausente ao acaso (missing at random)”, e a inferência é viável.

Considere alternativas quando

  • Você precisa de ótimos globais (EM é local).
  • O E-step é muito caro ou intratável e as aproximações são ruins.
  • Você prefere incerteza totalmente bayesiana sobre os parâmetros em vez de estimativas pontuais (aí você pode usar Monte Carlo via cadeia de Markov (Markov chain Monte Carlo, MCMC) ou Bayes variacional (variational Bayes)).

Armadilhas comuns e boas práticas

  • Inicialização: rode EM múltiplas vezes com seeds diferentes; escolha a melhor verossimilhança.
  • Regularização / priores: use MAP ou restrições de covariância para evitar degenerescências.
  • Troca de rótulos (label switching): rótulos de componentes de mistura são arbitrários; não superinterprete a ordenação.
  • Verifique a monotonicidade: se sua implementação reduz a verossimilhança, provavelmente há um bug (ou você está fazendo passos aproximados sem garantias).
  • Seleção de modelo: não apenas aumente o número de componentes; use validação ou Critérios de Informação.

Resumo

O EM é um método principiado e amplamente usado para ajustar modelos com variáveis latentes alternando entre:

  • E-step: inferir a estrutura latente probabilisticamente sob os parâmetros atuais (computar estatísticas suficientes esperadas),
  • M-step: reestimar parâmetros maximizando o objetivo esperado de dados completos (ML ou MAP).

Seu apelo vem de transformar a difícil otimização de verossimilhança do tipo “log-soma” em uma sequência de problemas mais simples, com uma interpretação probabilística clara. Na prática, o EM sustenta algoritmos centrais como a clusterização com GMMs, o Baum–Welch para HMMs e o aprendizado de modelos gráficos probabilísticos com dados ausentes — desde que você administre seus ótimos locais, a sensibilidade à inicialização e possíveis degenerescências.