Uma conversa entre tempo e geometria

HMMs, clusterização
e MS-VAR

Como descobrir padrões quando o mecanismo que os produz não é diretamente observado?

Uma sequência pode alternar entre regimes. Cada regime deixa uma assinatura nos dados; a persistência e as transições contam outra parte da história.

Use as setas do teclado ou os botões para navegar.

1 · A peça temporal

O que é uma cadeia de Markov?

Imagine que uma certa dinâmica admite estados/regimes evoluindo com o tempo. Denote por $S_t$ o regime no instante $t$. A hipótese de Markov diz que, conhecido o estado atual, o passado anterior não acrescenta informação para escolher o próximo estado:

$$\Pr(S_{t+1}=j\mid S_t=i,S_{t-1},\ldots)=P_{ij}.$$

Cada linha de $P$ é uma distribuição de probabilidades: $P_{ij}\geq0$ e $\sum_jP_{ij}=1$. A distribuição inicial $\pi_i=\Pr(S_1=i)$ começa a história.

Se $P_{ii}$ é grande, o estado $i$ tende a persistir.

2 · Uma cadeia em figura

Três estados, nove transições

De cada estado, as setas mostram para onde a cadeia pode ir no próximo passo. O número junto à seta é a probabilidade da transição; por exemplo, de $A$ para $B$ a chance é $20\%$.

$$P=\begin{pmatrix}.70&.20&.10\\.15&.70&.15\\.10&.25&.65\end{pmatrix}$$

Linhas = estado de origem; colunas = destino. Em cada linha, as probabilidades somam $100\%$.

Cadeia de Markov · Persistência

Quanto tempo ficamos em um estado?

Numa cadeia homogênea, seja $q=P_{ii}<1$. A cada passo no estado $i$, permanecemos nele com probabilidade $q$ e saímos com probabilidade $1-q$.

Uma duração geométrica

$D$ conta os instantes consecutivos no estado $i$ durante uma visita, incluindo o instante de entrada.

$$\Pr(D=d)=q^{d-1}(1-q),\quad d=1,2,\ldots.$$

Para durar $d$ instantes: fazemos $d-1$ autotransições e depois saímos.

Duração média, via série geométrica

Somamos cada duração $d$, ponderada por sua probabilidade. Como $0\le q<1$:

$$\begin{aligned} \mathbb E[D] &=\sum_{d=1}^{\infty}d\,q^{d-1}(1-q) =(1-q)\,\frac{d}{dq}\sum_{d=0}^{\infty}q^d\\ & =\frac{1}{1-P_{ii}}. \end{aligned}$$

$P_{ii}=0{,}70\;\Rightarrow\;3{,}33$ instantes$P_{ii}=0{,}95\;\Rightarrow\;20$ instantes$P_{ii}=0{,}99\;\Rightarrow\;100$ instantes

É uma duração média, esperada. A unidade é o intervalo entre observações.

Cadeia de Markov · Construindo a loss

Likelihood de uma trajetória observada

Observamos $s_0,\ldots,s_T$. Para $\theta=(\pi,P)$, a probabilidade da trajetória, vista como função de $\theta$, é:

$$L(\theta;s_{0:T})=\pi_{s_0}\,P_{s_0,s_1}\,P_{s_1,s_2}\cdots P_{s_{T-1},s_T}.$$

Likelihood: produto de probabilidades

$$L(\theta;s_{0:T})=\pi_{s_0}\prod_{t=1}^{T}P_{s_{t-1},s_t}.$$

O fator $\pi_{s_0}$ escolhe o estado inicial. Cada $P_{s_{t-1},s_t}$ corresponde a uma transição observada.

Loss: negativo do logaritmo

$$\begin{aligned}\mathcal L(\theta;s_{0:T})&=-\log L(\theta;s_{0:T})\\ &=-\log\pi_{s_0}-\sum_{t=1}^{T}\log P_{s_{t-1},s_t}.\end{aligned}$$

Maximizar a likelihood equivale a minimizar essa loss.

A propriedade de Markov permite usar apenas o estado anterior. Esta independência nos permite escrever a likehood como produtório.

2 · Estados ocultos

Da cadeia ao HMM

Em um hidden Markov model, não observamos diretamente $S_t$. Observamos $Y_t$, cuja distribuição depende desse estado.

Mecanismo

$S_1\sim\pi$, depois $S_t\mid S_{t-1}\sim P_{S_{t-1},:}$.

Em seguida $Y_t\mid S_t=k\sim \phi_k$. No exemplo, $\phi_k=\mathcal N(c_k,\Sigma_k)$.

Pergunta inversa

Vendo apenas $y_{1:T}$, quais parâmetros e estados são plausíveis?

O modelo pressupõe emissões independentes condicionadas à trajetória de estados.

A hipótese é sobre o modelo, não uma garantia de que os dados reais obedeçam a ela.

HMM · Estados e suas distribuições

Cada estado tem sua gaussiana

A cadeia percorre os estados ocultos. No estado $k$, a observação é amostrada da densidade $\phi_k$.

Seta sólida → transição entre estadosSeta tracejada → amostragem de uma observação

4 · Experimente

Um HMM gaussiano em 2D

Número de estados N

Variâncias dos centros$\sigma_x^2$$\sigma_y^2$

Favorecimento da diagonal: 3Velocidade: 4 passos/s

Altere N, as variâncias dos centros ou a diagonal e sorteie novamente. As variâncias de emissão por estado valem imediatamente.

Controles e detalhes da simulação

Roda do mouse: zoom · Clique e arraste: deslocar

Sorteie um modelo para começar.

Elipses tracejadas mostram as emissões circulares; os centros são amostrados com variâncias distintas em x e y.

Centros $c_k\sim\mathcal N(0,\operatorname{diag}(\sigma_x^2,\sigma_y^2))$; emissões circulares $Y_t\mid S_t=k\sim\mathcal N(c_k,v_k I_2)$. Os controles $\sigma_x^2$ e $\sigma_y^2$ mudam a dispersão dos centros; cada estado tem uma única variância de emissão.

4 · O objetivo de ajuste

Qual é a loss do HMM?

Para uma trajetória hipotética $s_{1:T}$, a densidade conjunta é um produto de probabilidades de estado e densidades de emissão:

$$p_\theta(y_{1:T},s_{1:T})=\pi_{s_1}\phi_{s_1}(y_1)\prod_{t=2}^T P_{s_{t-1}s_t}\phi_{s_t}(y_t).$$

Mas só observamos $y_{1:T}$. Somamos sobre todas as trajetórias possíveis e minimizamos o negativo do logaritmo:

$$\mathcal L(\theta)=-\log p_\theta(y_{1:T})=-\log\sum_{s_{1:T}}p_\theta(y_{1:T},s_{1:T}).$$

Para dados contínuos, $p_\theta(y)$ é uma densidade, não a probabilidade do ponto. $N$ e a família das emissões são escolhas do modelo.

5 · Como calcular

O algoritmo forward soma caminhos

Definimos $\alpha_t(j)$ como a probabilidade conjunta de o estado atual ser $j$ e termos observado o prefixo até $t$:

$$\alpha_t(j)=p_\theta(Y_{1:t}=y_{1:t},\ S_t=j).$$

Como $Y$ é contínuo, $p_\theta$ aqui denota uma densidade conjunta em $y_{1:t}$ e uma probabilidade no estado discreto $S_t$. A soma sobre todos os estados finais recupera a densidade do prefixo observado.

$$\alpha_1(j)=\pi_j \phi_j(y_1),\quad \alpha_t(j)=\phi_j(y_t)\sum_i\alpha_{t-1}(i)P_{ij},\quad p_\theta(y_{1:T})=\sum_j\alpha_T(j).$$

A recorrência custa $O(TN^2)$. Em implementações, usamos reescala ou log-sum-exp para evitar underflow.

6 · Aprender com estados ocultos

EM em duas ideias

Se os estados fossem conhecidos, ajustar transições e emissões seria mais direto. Como não são, alternamos:

E · Expectation

Com os parâmetros atuais, calculamos as probabilidades posteriores dos estados e pares de transições, usando toda a sequência observada.

$\gamma_t(k)=\Pr(S_t=k\mid Y_{1:T}=y_{1:T})$.

M · Maximization

Maximizamos $Q(\theta\mid\theta^{\mathrm{ant}})$, a expectativa da log-verossimilhança completa sobre as trajetórias de estados. As probabilidades do passo E ficam fixas.

Ex.: $\pi_k\leftarrow\gamma_1(k)$.

EM exato não reduz a verossimilhança observada, mas pode chegar a um ótimo local. Reinicializações podem ajudar; covariâncias degeneradas exigem cuidados.

EM · A expectativa que entra no ajuste

Uma média sobre trajetórias de estados

Para os parâmetros atuais $\theta^{\mathrm{ant}}$, o passo E obtém a distribuição posterior das trajetórias, usando toda a sequência observada:

$$q(s_{1:T})=p_{\theta^{\mathrm{ant}}}(s_{1:T}\mid y_{1:T}).$$

O passo M procura aumentar a expectativa da log-verossimilhança completa, mantendo $q$ fixa:

$$\begin{aligned} Q(\theta\mid\theta^{\mathrm{ant}}) &=\mathbb E_{S_{1:T}\sim q}\!\left[\log p_\theta(y_{1:T},S_{1:T})\right]\\ &=\sum_{s_{1:T}}q(s_{1:T})\,\log p_\theta(y_{1:T},s_{1:T}). \end{aligned}$$

No passo E, usamos $\theta^{\mathrm{ant}}$ para determinar $q$. No passo M, variamos $\theta$ dentro do logaritmo, mantendo os pesos $q(s_{1:T})$ fixos.

EM · Por que melhorar Q ajuda?

Da expectativa à verossimilhança observada

Nos dados observados, somamos sobre as trajetórias possíveis e depois tomamos o logaritmo:

$$\ell(\theta)=\log\sum_{s_{1:T}}p_\theta(y_{1:T},s_{1:T}).$$

Com o posterior exato dos parâmetros atuais no passo E, temos:

$$\begin{aligned} \ell(\theta^{\mathrm{novo}})-\ell(\theta^{\mathrm{ant}}) \ \ge\ &Q(\theta^{\mathrm{novo}}\mid\theta^{\mathrm{ant}}) -Q(\theta^{\mathrm{ant}}\mid\theta^{\mathrm{ant}}). \end{aligned}$$

Assim, aumentar $Q$ no passo M garante que $\ell$ não diminua. Equivalentemente, a loss $-\ell$ não aumenta.

A desigualdade vem do limite inferior de Jensen: para $q$ fixo, $\ell(\theta)\ge Q(\theta\mid\theta^{\mathrm{ant}})+H(q)$, com igualdade em $\theta^{\mathrm{ant}}$. Aqui $H(q)=-\sum_s q(s)\log q(s)$ é a entropia do posterior e fica constante no passo M.

EM · Como calcular essa média no HMM

A expectativa vira contagens suaves

O logaritmo da densidade conjunta separa estado inicial, emissões e transições. A média de cada termo usa as probabilidades posteriores:

Pesos calculados no passo E

$$\gamma_t(k)={\Pr}_{\theta^{\mathrm{ant}}}(S_t=k\mid y_{1:T}).$$

$$\begin{aligned}\xi_t(i,j)&={\Pr}_{\theta^{\mathrm{ant}}}\bigl(S_{t-1}=i, S_t=j\mid y_{1:T}\bigr),\quad t\ge2.\end{aligned}$$

O forward–backward calcula $\gamma$ e $\xi$. Esses pesos ficam fixos no passo M.

Objetivo maximizado no passo M

$$\begin{aligned} Q(\theta\mid\theta^{\mathrm{ant}}) ={}&\sum_k\gamma_1(k)\log\pi_k +\sum_{t=1}^{T}\sum_k\gamma_t(k)\log\phi_k(y_t)\\ &+\sum_{t=2}^{T}\sum_{i,j}\xi_t(i,j)\log P_{ij}. \end{aligned}$$

Ajustamos a distribuição inicial $\pi$, as emissões $\phi_k$ e as transições $P$.

$$P_{ij}^{\mathrm{novo}}= \frac{\sum_{t=2}^{T}\xi_t(i,j)}{\sum_{t=2}^{T}\gamma_{t-1}(i)}.$$

Numerador: número esperado de transições $i\to j$. Denominador: número esperado de oportunidades de sair de $i$, incluindo autotransições. A fórmula vale quando o denominador é positivo.

7 · Sem ordem temporal

GMM: uma mistura de gaussianas

Para observações independentes, cada ponto recebe um rótulo latente $Z_i$; não há matriz de transição.

$$p_\theta(y_i)=\sum_{k=1}^N w_k\,\mathcal N(y_i;\mu_k,\Sigma_k),\qquad \mathcal L=-\sum_i\log p_\theta(y_i).$$

Os pesos $w_k$ somam 1. O posterior $\Pr(Z_i=k\mid y_i)$ é uma associação suave: um ponto pode pertencer parcialmente a vários grupos.

EM também se aplica: calcula responsabilidades no passo E e atualiza pesos, médias e covariâncias no passo M.

Laboratório · GMM

Da amostra ao ajuste de uma mistura

Primeiro escolha um modelo e amostre. No ajuste, o EM alterna: E calcula responsabilidades; M atualiza pesos, médias e variâncias. Aqui usamos covariâncias diagonais e variância mínima $0{,}03$ por eixo.

8 · Geometria

K-means: proximidade aos centros

$$\min_{z_1,\ldots,z_m,\mu_1,\ldots,\mu_N}\sum_{i=1}^m\lVert y_i-\mu_{z_i}\rVert^2.$$

Alternamos: atribuir cada ponto ao centro mais próximo; atualizar cada centro como a média dos pontos atribuídos. A atribuição é rígida.

GMM: modelo probabilístico, grupos com covariâncias e incerteza.

K-means: objetivo geométrico, distância euclidiana, sem probabilidades posteriores.

Ambos dependem da escala das variáveis e da inicialização; K-means pode ter grupos vazios.

Laboratório · K-means

Classificar, recalcular, repetir

1 · Atribuição: associe cada ponto ao centro mais próximo. 2 · Atualização: mova cada centro para a média de seu grupo. Repita até as atribuições estabilizarem. As regiões do fundo mostram a classificação pelo centro mais próximo.

9 · Dinâmica por regime

MS-VAR: cada estado tem sua regressão

Agora a média da observação depende também do passado observado. Para $t=p,\ldots,T-1$:

$$Y_t=c_{S_t}+\sum_{\ell=1}^{p}A_{\ell,S_t}Y_{t-\ell}+B_{S_t}x_t+\varepsilon_t,\qquad \varepsilon_t\mid S_t=k\sim\mathcal N(0,\Sigma_k).$$

$Y_t\in\mathbb R^d$; $x_t$ representa covariáveis dadas. $p$ é o número de defasagens, e cada estado tem seus próprios coeficientes e covariância.

Assim, um regime pode representar uma dinâmica diferente, não apenas uma nuvem em torno de outra média.

10 · A mesma arquitetura de loss

Verossimilhança do MS-VAR

Condicionamos no prefixo observado $y_{0:p-1}$ e nas covariáveis $x$. Para cada regime, a densidade local é

$$\psi_{t,k}=\mathcal N\!\left(y_t;c_k+\sum_{\ell=1}^{p}A_{\ell,k}y_{t-\ell}+B_kx_t,\Sigma_k\right).$$

$$\mathcal L(\theta)=-\log\sum_{s_{p:T-1}}\left[\pi_{s_p}\psi_{p,s_p}\prod_{t=p+1}^{T-1}P_{s_{t-1}s_t}\psi_{t,s_t}\right].$$

O forward é o mesmo, trocando $\phi_k(y_t)$ por $\psi_{t,k}$. O prefixo fornece as defasagens: não entra como observação adicional na loss condicional. Aqui $\pi$ é a distribuição do primeiro estado modelado, $S_p$.

11 · Fechamento

Uma família de perguntas

K-means: quais pontos estão próximos?

GMM: quais distribuições explicam as nuvens?

HMM: como os grupos evoluem no tempo?

MS-VAR: como a própria dinâmica muda entre regimes?

Para discutir: se dois regimes têm emissões semelhantes, como a persistência pode ajudar a distingui-los? Quando ela pode nos induzir ao erro?

Base conceitual: notas pessoais em_and_direct.tex, seções sobre HMM, MS-VAR, verossimilhança marginal e EM. Nesta aula usamos índices de HMM de 1 a T e MS-VAR de 0 a T−1.

Extra 1 · Elaborando HMMs e MS-VARs

Onde uma rede neural entra?

Os estados continuam sendo regimes discretos. As redes podem dar mais flexibilidade a duas partes do modelo:

Escolha do próximo estado

Num HMM homogêneo, a linha $P_{i,:}$ depende apenas do estado atual $i.$

$$\text{histórico observado}\ \longrightarrow\ \text{rede}\ \longrightarrow\ P_t(i,:).$$

A chance de trocar de regime passa a depender do que acabou de acontecer.

Dinâmica dentro do estado

No MS-VAR, cada regime tem uma regressão linear sobre o passado.

$$\text{passado}\ \longrightarrow\ \text{rede }k\ \longrightarrow\ m_{t,k}.$$

A média condicional $m_{t,k}$ pode descrever uma dinâmica não linear.

Podemos elaborar cada parte separadamente. Nas fórmulas a seguir, $K$ é o número de estados, $p$ é o número de defasagens e $Y_t\in\mathbb R^d$.

Referência para transições condicionadas por entradas: Bengio e Frasconi, An Input Output HMM Architecture (1994).

Extra 2 · Transições que dependem dos dados

Uma rede produz cada linha de Pₜ

Antes de gerar $Y_t$, montamos o contexto $h_t=(Y_{t-1},\ldots,Y_{t-p},x_t)$, com covariáveis $x_t$ disponíveis nesse instante. Para cada estado anterior $i$, uma rede produz $K$ números reais $a_{t,i,1:K}$.

$$\begin{aligned} a_{t,i,1:K}&=F_\eta(h_t,i),\\ P_t(i,j)&=\Pr(S_t=j\mid S_{t-1}=i,h_t) =\frac{\exp(a_{t,i,j})}{\sum_{\ell=1}^{K}\exp(a_{t,i,\ell})}. \end{aligned}$$

O softmax transforma esses números em probabilidades positivas que somam $1$ em cada linha. O estado $i$ pode entrar por uma codificação one-hot, um vetor com $1$ na posição $i$ e $0$ nas demais.

Os pesos $\eta$, incluindo $b,w$ no exemplo, são aprendidos. Se a rede ignorar $h_t$, recuperamos uma matriz de transição constante.

Extra 3 · Componentes autorregressivos neurais

Da regressão linear à dinâmica não linear

MS-VAR

$$m_{t,k}=c_k+\sum_{\ell=1}^{p}A_{\ell,k}Y_{t-\ell}+B_kx_t.$$

Cada regime transforma linearmente o passado observado.

Elaboração neural

$$m_{t,k}=f_{\omega,k}(h_t).$$

Uma rede por regime, ou uma rede compartilhada que também recebe $k$, prevê a média de $Y_t$.

$$Y_t=m_{t,S_t}+\varepsilon_t,\qquad \varepsilon_t\mid S_t=k,h_t\sim\mathcal N(0,\Sigma_k),\quad \Sigma_k\succ0.$$

Uma opção gradual é manter o MS-VAR e acrescentar uma correção neural $r_{\omega,k}$:

$$m_{t,k}=c_k+\sum_{\ell=1}^{p}A_{\ell,k}Y_{t-\ell}+B_kx_t+r_{\omega,k}(h_t).$$

Com $r_{\omega,k}=0$, recuperamos o MS-VAR. Com médias constantes e covariâncias por estado, recuperamos as emissões gaussianas do HMM. A letra $f$ aqui denota uma rede; a densidade de emissão continua sendo $\psi_{t,k}$.

Referência: Tsuboka e Takada, Neural Predictive Hidden Markov Model (1995).

Extra 5 · A mesma construção da likelihood

A rede muda os fatores; o forward ainda soma

Para a sequência observada, $h_t$ é conhecido. A densidade local e a soma das trajetórias tornam-se:

$$\psi_{t,k}=\mathcal N(y_t;m_{t,k}(h_t),\Sigma_k),\qquad \mathcal L(\theta)=-\log\sum_{s_{p:T-1}}\pi_{s_p}\psi_{p,s_p} \prod_{t=p+1}^{T-1}P_t(s_{t-1},s_t)\psi_{t,s_t}.$$

$$\begin{aligned} \alpha_p(j)&=\pi_j\psi_{p,j},\\ \alpha_t(j)&=\psi_{t,j}\sum_i\alpha_{t-1}(i)P_t(i,j),\\ \mathcal L(\theta)&=-\log\sum_j\alpha_{T-1}(j). \end{aligned}$$

O forward continua exato porque cada fator depende apenas do estado atual, do anterior e de um contexto comum a todas as trajetórias. A soma de transições custa $O((T-p)K^2)$, além de avaliar as redes.

Condicionamos no prefixo $y_{0:p-1}$ e nas covariáveis; $\pi$ é a distribuição inicial de $S_p$. Aqui $\theta$ reúne parâmetros das redes, covariâncias e distribuição inicial. Usamos log-sum-exp ou reescala na implementação.

Extra 6 · Como aprender as redes

Derivar a loss ou continuar usando EM?

Diferenciar o forward

As redes, o softmax, as densidades gaussianas e o forward formam uma computação diferenciável.

$$\theta\leftarrow\theta-\lambda\,\nabla_\theta\mathcal L(\theta).$$

O gradiente atravessa a soma dos caminhos; não é necessário sortear estados discretos para calcular essa loss.

EM com passo M numérico

O forward–backward calcula $\gamma_t(k)$ e $\xi_t(i,j)$ com os parâmetros atuais.

Com esses pesos fixos, usamos gradientes para aumentar $Q$, ajustando as redes de transição e de emissão.

Isso é EM generalizado se o passo M de fato aumentar $Q$. Um passo arbitrário de gradiente não garante monotonicidade.

$$Q(\theta\mid\theta^{\mathrm{ant}}) =\sum_k\gamma_p(k)\log\pi_k +\sum_{t=p}^{T-1}\sum_k\gamma_t(k)\log\psi_{t,k} +\sum_{t=p+1}^{T-1}\sum_{i,j}\xi_t(i,j)\log P_t(i,j).$$

Em $Q$, usamos $\psi_{t,k}(\theta)$ e $P_t(i,j;\theta)$ recalculados com os parâmetros candidatos, mas mantemos $\gamma$ e $\xi$ fixos no passo M.

HMMs, clusterizaçãoe MS-VAR