Modelos de Markov e modelos ocultos de Markov

Um sistema em evolução precisa de um estado para cada momento e de uma regra para passar ao momento seguinte. Uma cadeia de Markov em tempo discreto registra esses estados em passos igualmente espaçados. Escolha o estado e o passo de tempo juntos: o tempo diário e a localização de um robô a cada segundo descrevem processos diferentes.

O que o estado atual deve conter

A propriedade de Markov de primeira ordem é

Uma vez conhecido o estado atual, os estados anteriores não acrescentam informação sobre o próximo. Isso é independência condicional, não independência entre estados consecutivos. Conhecer o tempo de ontem pode ajudar a prever o de amanhã quando o tempo de hoje é desconhecido.

Uma cadeia precisa de uma distribuição inicial, $P(X_1)$, e de um modelo de transição. Usamos transições homogêneas no tempo: as mesmas probabilidades se aplicam em todos os passos. Alguns textos de IA chamam isso de hipótese de estacionariedade. Na teoria da probabilidade, um processo estacionário tem distribuições conjuntas que não mudam quando o tempo é deslocado; transições fixas por si só não garantem isso. Iniciar uma cadeia homogênea no tempo em uma distribuição estacionária garante.

Interprete uma matriz de transição

Para o tempo, sejam os estados Ensolarado (S) e Nublado (C). As linhas indicam o estado atual e as colunas, o próximo estado:

A partir de Ensolarado, o dia seguinte é ensolarado com probabilidade 0,8 e nublado com probabilidade 0,2. A partir de Nublado, essas probabilidades são 0,4 e 0,6. Cada linha soma 1 porque lista todos os destinos a partir de um estado inicial. As colunas não precisam somar 1. Um diagrama de estados representa a mesma tabela com setas, incluindo setas de retorno ao mesmo estado.

Alguns livros transpõem essa convenção. Antes de calcular, leia a definição de uma entrada: aqui, $T_{ij}=P(X_{t+1}=j\mid X_t=i)$. Um conjunto correto de números usado na orientação errada produz uma predição errada.

Multiplique ao longo de um caminho

Um caminho específico usa sua probabilidade inicial e uma transição para cada movimento:

Se o dia 1 é certamente ensolarado, o caminho Ensolarado, Ensolarado, Nublado, Nublado tem probabilidade

O primeiro movimento contribui com 0,8, a mudança contribui com 0,2 e a permanência em Nublado contribui com 0,6. Multiplicar frequências diárias separadas descartaria as ligações entre os dias. Em uma rede bayesiana, essas ligações são as setas em $X_1\to X_2\to X_3\to \cdots$.

Mantenha histórico suficiente no estado

Um modelo de segunda ordem depende dos dois últimos valores. Transforme-o em um modelo de primeira ordem definindo o estado como (ontem, hoje). Dois valores meteorológicos fornecem então quatro pares possíveis. Uma transição de (Ensolarado, Nublado) só pode levar a um par que comece com Nublado, pois pares adjacentes devem se sobrepor. Para um processo de ordem $k$, armazene os últimos $k$ valores juntos; os algoritmos continuam sendo de primeira ordem, enquanto o número de estados combinados cresce.

Uma cadeia ocupa um estado em cada instante, mas você pode não saber qual é. Uma distribuição de estados armazena essa incerteza como um vetor linha. Suas entradas fornecem as probabilidades dos estados possíveis, não frações de tempo dentro de um único passo.

Some todas as rotas para um destino

Para prever Ensolarado amanhã, considere as duas formas de chegar lá: hoje pode ser Ensolarado ou Nublado. Pondere cada transição pela probabilidade de seu estado inicial:

Para o vetor completo, isso é $p_{t+1}=p_{t}T$. Após $k$ movimentos, $p_{t+k}=p_t{T}^k$. Essa atualização às vezes é chamada de algoritmo de avanço simplificado, a versão da filtragem de HMM sem evidências.

Acompanhe a cadeia meteorológica

Use as linhas (0,8; 0,2) a partir de Ensolarado e (0,4; 0,6) a partir de Nublado. Comece com um dia certamente ensolarado: $p_1=(1,0)$. Um movimento fornece $p_2=(\mathrm{0,8};\mathrm{0,2})$. Para o dia 3, a contribuição para Ensolarado é $\mathrm{0,8}\times \mathrm{0,8}=\mathrm{0,64}$ a partir de Ensolarado e $\mathrm{0,2}\times \mathrm{0,4}=\mathrm{0,08}$ a partir de Nublado. Some-as para obter 0,72. As contribuições para Nublado são $\mathrm{0,8}\times \mathrm{0,2}=\mathrm{0,16}$ e $\mathrm{0,2}\times \mathrm{0,6}=\mathrm{0,12}$, resultando em 0,28.

Assim, $p_3=(\mathrm{0,72};\mathrm{0,28})$. Mais uma atualização fornece $P(X_4=S)=\mathrm{0,72}\times \mathrm{0,8}+\mathrm{0,28}\times \mathrm{0,4}=\mathrm{0,688}$ e $P(X_4=C)=\mathrm{0,312}$. Use valores não arredondados entre os passos e arredonde os resultados exibidos ao final.

Verifique o significado e a orientação

Cada resultado deve ser não negativo e somar 1. Na convenção de linhas, coloque a distribuição à esquerda. Usar $T{p}_1^{𝖳}$ fornece a coluna (0,8; 0,4), cujo total é 1,2. Esse cálculo seleciona as probabilidades de alcançar Ensolarado a partir de dois estados iniciais diferentes; ele não distribui uma crença inicial entre os destinos.

O valor 0,72 no dia 3 significa que cerca de 72% de muitas execuções independentes com um dia 1 ensolarado terão sol no dia 3. Ele não descreve um padrão meteorológico fixo e repetitivo nem um dia que seja 72% ensolarado.

Por que a predição continua viável

Uma atualização densa sobre $S$ estados custa $O(S^2)$ operações. Ela resume todos os caminhos passados no vetor atual, portanto o custo por movimento permanece o mesmo com o passar do tempo. Listar cada caminho a partir de um início conhecido exigiria $S^{t-1}$ caminhos no instante $t$.

Para essa cadeia meteorológica, as probabilidades sucessivas de Ensolarado se aproximam de $2\mathrm{/}3$. Se $s_t=P(X_t=S)$, então $s_{t+1}=\mathrm{0,4}+\mathrm{0,4}{s}_t$. Subtrair $2\mathrm{/}3$ mostra que a diferença diminui por um fator de 0,4 a cada passo. Outras cadeias podem se comportar de maneira diferente; a convergência exige as condições estudadas com distribuições estacionárias.

Você também pode simular uma execução. Sorteie o estado inicial e, depois, sorteie da linha de transição correspondente ao estado ocupado no momento. A partir de Ensolarado, um sorteio aleatório uniforme abaixo de 0,8 seleciona Ensolarado; um sorteio de pelo menos 0,8 seleciona Nublado. Repetir muitas execuções estima a mesma distribuição prevista e apresenta a ideia de amostragem usada pelos filtros de partículas.

Uma distribuição pode permanecer inalterada mesmo enquanto as execuções individuais continuam mudando de estado. Uma distribuição estacionária descreve esse equilíbrio. Ela é útil para previsões de longo prazo, mas sua existência, por si só, não informa se uma cadeia se aproxima dela a partir de um início específico.

Resolva as equações de balanço

Um vetor linha estacionário satisfaz $\pi =\pi T$, juntamente com ${\sum }_j{\pi }_j=1$ e entradas não negativas. Para a cadeia meteorológica, a probabilidade que flui de Ensolarado para Nublado deve equilibrar a probabilidade que flui de volta:

A primeira equação fornece ${\pi }_S=2{\pi }_C$. A substituição fornece $3{\pi }_C=1$, portanto $\pi =(2\mathrm{/}3,1\mathrm{/}3)$. Para uma cadeia de dois estados com probabilidades de mudança $a$ do estado 1 para o 2 e $b$ do 2 para o 1, ${\pi }_1=b\mathrm{/}(a+b)$ quando $a+b>0$.

Para mais estados, escreva uma equação de fluxo de entrada por estado. Substitua uma delas pela equação que exige soma igual a 1 e resolva o sistema linear. As equações de balanço, sozinhas, deixam a escala indeterminada. Por fim, multiplique o vetor proposto pela matriz para verificá-lo.

Para as estações A, B, C de bicicletas compartilhadas, use as linhas (0,6; 0,2; 0,2), (0,1; 0,8; 0,1) e (0,2; 0,2; 0,6). A solução é (0,25; 0,5; 0,25). Por exemplo, a probabilidade que entra em B é $\mathrm{0,25}(\mathrm{0,2})+\mathrm{0,5}(\mathrm{0,8})+\mathrm{0,25}(\mathrm{0,2})=\mathrm{0,5}$. Uma probabilidade uniforme não passaria nessa verificação.

Separe três perguntas

Irredutível significa que cada estado pode alcançar todos os outros, possivelmente por vários movimentos. Aperiódica significa que os retornos não estão presos a um ciclo fixo com mais de um passo. A matriz meteorológica tem todas as entradas positivas, portanto ambas as condições são satisfeitas. Em uma cadeia finita irredutível, as probabilidades estacionárias também fornecem as frações de passos passados em cada estado no longo prazo, mesmo quando a periodicidade impede a convergência da distribuição em cada instante.

Dois contraexemplos reveladores

Se dois estados sempre alternam, a distribuição a partir de um primeiro estado certo alterna entre (1, 0) e (0, 1). O vetor estacionário único é (0,5; 0,5), mas essas predições nunca se aproximam dele. Em uma execução longa, cada estado ainda ocupa metade dos passos.

Se ambos os estados são absorventes, cada um permanece onde está para sempre. Todo vetor (q, 1 − q) é estacionário, portanto não há um equilíbrio único compartilhado por todos os inícios. Esses exemplos mostram por que unicidade, convergência e médias temporais precisam de verificações separadas.

A distribuição inicial descreve o início; ela só é igual a uma distribuição estacionária quando você começa em equilíbrio. Probabilidades de transição fixas descrevem a lei do modelo, não sua distribuição atual. O PageRank usa probabilidades estacionárias para classificar páginas em um modelo de navegação aleatória. Monte Carlo via cadeias de Markov constrói uma cadeia com uma distribuição estacionária desejada para que sua execução longa forneça amostras.

Uma leitura de sensor fornece evidência sobre um estado sem revelá-lo perfeitamente. Em um modelo oculto de Markov, ou HMM, o estado muda ao longo do tempo e cada estado produz uma observação. Um robô pode conhecer a leitura de seu sensor de distância e ainda ter incerteza sobre sua posição.

Especifique três modelos de probabilidade

Um HMM precisa de uma distribuição inicial de estados, um modelo de transição e um modelo de sensor:

O estado oculto é uma variável discreta. O modelo de sensor, também chamado de modelo de emissão ou de observação, informa a verossimilhança de cada observação em cada estado. Atribuímos uma distribuição a priori diretamente a $X_1$ e observamos $E_1$ nesse momento. Textos que começam com um $X_0$ não observado fazem uma transição antes da primeira observação.

O estado tem a propriedade de Markov de primeira ordem. A observação em um instante depende apenas do estado nesse instante: $P(E_t\mid X_{1:t},E_{1:t-1})=P(E_t\mid X_t)$. Em uma rede bayesiana, desenhe uma cadeia de estados ocultos e acrescente uma seta de cada estado para sua observação.

Construa o modelo de painel solar

O estado meteorológico oculto é Ensolarado ou Nublado, com linhas de transição (0,8; 0,2) e (0,4; 0,6). Ambos os estados iniciais têm probabilidade 0,5. A produção diária do painel é Alta ou Baixa:

Cada linha do sensor soma 1. Um dia nublado ainda pode produzir uma produção Alta, portanto Alta não identifica Ensolarado com certeza. Da mesma forma, $P(L\mid C)=\mathrm{0,7}$ é uma afirmação sobre a produção em dias nublados. Encontrar $P(C\mid L)$ também exige a distribuição a priori e a regra de Bayes.

Calcule a probabilidade conjunta de estados e evidências

Para um caminho específico de estados e uma sequência de observações,

Para Nublado, Nublado, Ensolarado com Baixa, Baixa, Alta, comece com $\mathrm{0,5}\times \mathrm{0,7}=\mathrm{0,35}$. Permanecer em Nublado e observar Baixa fornece $\mathrm{0,35}\times \mathrm{0,6}\times \mathrm{0,7}=\mathrm{0,147}$. Mudar para Ensolarado e observar Alta fornece $\mathrm{0,147}\times \mathrm{0,4}\times \mathrm{0,8}=\mathrm{0,04704}$.

Observações podem ser dependentes mesmo sem setas diretas entre elas. A persistência do tempo nublado faz com que leituras sucessivas de Baixa tendam a ocorrer juntas. Condicionar aos estados ocultos elimina essa dependência. A evidência atualiza a crença do observador; observar Baixa não faz, por si só, o tempo mudar.

Escolha a pergunta de inferência

Os mesmos três modelos sustentam as cinco tarefas. O que muda é quais variáveis você mantém, quais elimina por soma e se soma os caminhos ou seleciona a maior pontuação de caminho.

A definição do estado determina o que o modelo pode lembrar. Um modelo temporal útil mantém a informação necessária para prever o próximo estado, sem tornar a inferência custosa demais. Suas probabilidades também devem refletir os dados e as falhas de sensor que ele encontrará.

Escolha informação suficiente para o estado

A posição sozinha pode ser insuficiente para um objeto com inércia: posições anteriores revelam sua direção. Acrescentar a velocidade permite que o estado atual explique essa direção. Acrescente a estação do ano se a dinâmica depender dela. Essas escolhas tornam a aproximação de Markov mais razoável; são escolhas sobre qual informação é levada adiante.

Uma grandeza contínua pode ser colocada em uma grade. Temperaturas de 10 °C a 20 °C em incrementos de 0,1 °C produzem 101 valores, incluindo ambos os extremos. Um espaçamento menor aumenta o número de estados. Combinar várias grandezas discretizadas multiplica suas quantidades de valores, e a inferência exata densa custa $O(S^2)$ por passo.

Conte os parâmetros independentes

Uma linha de distribuição categórica com $r$ entradas tem $r-1$ parâmetros livres porque a última entrada é determinada pela soma. Com $S$ estados e $O$ valores de observação, um HMM sem restrições precisa, portanto, de

parâmetros livres: distribuição a priori, transições e emissões. O modelo solar de dois estados e duas produções precisa de $1+2+2=5$. Contar cada entrada da tabela contaria as restrições de soma das linhas como escolhas adicionais.

Fatore o estado com uma rede bayesiana dinâmica

Uma rede bayesiana dinâmica (DBN) mantém várias variáveis de estado e atribui a cada uma seus próprios nós pais. Ela pode expressar dependências locais sem construir uma enorme tabela de transição não fatorada. Vinte variáveis booleanas têm $2^{20}=\mathrm{1.048.576}$ estados conjuntos; uma tabela de transição não fatorada tem $2^{40}$ entradas. Se cada variável booleana do próximo passo tem três nós pais booleanos, sua tabela precisa de oito probabilidades, portanto as 20 precisam de $20\times 8=160$.

Uma DBN discreta pode ser transformada em um HMM tratando uma atribuição completa como um estado. O armazenamento fatorado é compacto, mas a inferência exata ainda pode se tornar custosa quando dependências unem muitas variáveis. Métodos de partículas podem amostrar essas atribuições diretamente.

Estime linhas a partir de dados

Quando os estados estão rotulados, use contagens condicionais. Quarenta sucessores ensolarados em 50 transições registradas a partir de Ensolarado fornecem $P(S\to S)=40\mathrm{/}50=\mathrm{0,8}$. O denominador conta as transições que saem de Ensolarado, não todos os dias do registro. Um estado no fim de um registro não tem sucessor observado.

Contagens zero produzem probabilidades de máxima verossimilhança iguais a zero. A correção aditiva de um dá a cada destino uma pseudocontagem e aumenta o total da linha de acordo. Isso evita descartar uma transição apenas porque um pequeno registro de treinamento não a incluiu. Quando os estados estão ocultos, Baum–Welch alterna entre contagens esperadas suavizadas e reestimação dos parâmetros.

Reserve espaço para falhas no modelo de sensor

Se todos os estados possíveis atribuem verossimilhança zero a uma leitura, uma atualização tem total zero e não pode ser normalizada. Um pequeno componente para valores atípicos pode atribuir alguma probabilidade a leituras incomuns. Uma mistura normalizada tem a forma $P(e\mid x)=\mathrm{0,99}{P}_{\mathrm{r}\mathrm{e}\mathrm{g}\mathrm{u}\mathrm{l}\mathrm{a}\mathrm{r}}(e\mid x)+\mathrm{0,01}{P}_{\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{i}\mathrm{e}\mathrm{r}}(e)$. Ambas as distribuições componentes devem ser normalizadas.

O efeito de uma leitura depende das razões de verossimilhanças entre os estados. Verossimilhanças iguais deixam a crença prevista inalterada após a normalização. Uma verossimilhança pequena em todos os estados ainda pode ser informativa se as verossimilhanças diferirem muito em termos relativos.

A filtragem acompanha o estado oculto atual usando todas as observações disponíveis até o momento. Sua saída é uma distribuição de crença, $f_t(x)=P(X_t=x\mid e_{1:t})$. Você atualiza essa distribuição compacta quando chega uma nova leitura, sem manter todos os caminhos anteriores possíveis.

Preveja, pondere e normalize

Para um passo posterior, primeiro mova a crença pelo modelo de transição:

Depois, pondere cada destino pela verossimilhança da nova observação e normalize:

A predição descreve para onde o estado pode ter se movido. A atualização com evidência é a regra de Bayes no novo instante. Com uma distribuição a priori em $X_1$, comece ponderando essa distribuição pela primeira observação; não há movimento antes dela.

Dia 1: observe Baixa

Use o modelo de painel solar: distribuição a priori (0,5; 0,5), linhas de transição (0,8; 0,2) e (0,4; 0,6), e verossimilhanças de Baixa (0,2; 0,7). A ponderação fornece $\mathrm{0,5}(\mathrm{0,2})=\mathrm{0,10}$ para Ensolarado e $\mathrm{0,5}(\mathrm{0,7})=\mathrm{0,35}$ para Nublado. O total é 0,45. Divida cada peso por ele para obter $f_1=(2\mathrm{/}9,7\mathrm{/}9)\approx (\mathrm{0,2222};\mathrm{0,7778})$.

Dia 2: observe Baixa novamente

A predição fornece ${\bar{f}}_2(S)=(2\mathrm{/}9)(\mathrm{0,8})+(7\mathrm{/}9)(\mathrm{0,4})=22\mathrm{/}45\approx \mathrm{0,4889}$. Nublado tem probabilidade $23\mathrm{/}45\approx \mathrm{0,5111}$. Os novos pesos são $22\mathrm{/}225\approx \mathrm{0,0978}$ e $161\mathrm{/}450\approx \mathrm{0,3578}$. Seu total é $41\mathrm{/}90\approx \mathrm{0,4556}$, produzindo $f_2=(44\mathrm{/}205,161\mathrm{/}205)\approx (\mathrm{0,2146};\mathrm{0,7854})$.

A segunda produção Baixa aumenta apenas um pouco a crença em Nublado. O movimento em direção ao equilíbrio da cadeia, que favorece Ensolarado, concorre com a nova evidência que favorece Nublado. Aplicar Baixa diretamente à crença de ontem ignoraria esse movimento.

Dia 3: observe Alta

Preveja ${\bar{f}}_3=(498\mathrm{/}1025,527\mathrm{/}1025)\approx (\mathrm{0,4859};\mathrm{0,5141})$. Alta tem verossimilhanças (0,8; 0,3), portanto os pesos são aproximadamente (0,3887; 0,1542). Divida pelo total, aproximadamente 0,5429, para obter $f_3\approx (\mathrm{0,7159};\mathrm{0,2841})$.

Alta é $\mathrm{0,8}\mathrm{/}\mathrm{0,3}\approx \mathrm{2,67}$ vezes mais provável em Ensolarado do que em Nublado. Essa razão de verossimilhanças desloca a razão de chances em direção a Ensolarado. Uma verossimilhança alta, sozinha, é menos informativa que seu tamanho em relação à verossimilhança do estado concorrente.

Mantenha um filtro em tempo de execução confiável

Um passo denso custa $O(S^2)$ em tempo e armazena $O(S)$ entradas de crença, independentemente do comprimento do histórico. Isso é eliminação exata de variáveis: cada estado passado é eliminado por soma conforme você avança.

Normalize a cada observação. Sem ajuste de escala, o vetor armazena probabilidades conjuntas de estado e evidências, que podem diminuir além do intervalo representável em ponto flutuante. Mantenha os totais descartados separadamente se precisar da verossimilhança das evidências. Um total zero exige recuperação do modelo ou do suporte das partículas; a divisão não consegue corrigi-lo.

Nossa fórmula com vetor linha é $f_{t+1}\propto (f_{t}T)O_{t+1}$, em que a matriz diagonal contém as novas verossimilhanças. Para crenças em coluna, a fórmula equivalente é $f_{t+1}\propto O_{t+1}{T}^{𝖳}{f}_t$. Misturar essas convenções é uma fonte frequente de erros.

Uma crença filtrada permite responder a duas perguntas úteis: o que pode acontecer em seguida e em que medida o modelo explicou as leituras já observadas? Ambas usam os mesmos modelos de transição e de sensor, mas as respostas descrevem grandezas aleatórias diferentes.

Preveja sem leituras futuras

Para uma previsão $k$ passos à frente, aplique a matriz de transição $k$ vezes à crença filtrada mais recente:

Não se faz atualização por observação em um passo futuro não observado. Depois que o modelo solar observa Baixa, Baixa, Alta, a crença do dia 3 é aproximadamente (0,7159; 0,2841). Uma predição fornece $P(X_4=S)\approx \mathrm{0,7159}(\mathrm{0,8})+\mathrm{0,2841}(\mathrm{0,4})=\mathrm{0,6864}$. Continuar com valores não arredondados fornece probabilidades de Ensolarado de 0,6745; 0,6698; 0,6679 e 0,6672.

Esses valores se aproximam de $2\mathrm{/}3$. A cadeia perde gradualmente sua dependência da crença mais recente. O tempo de mistura especifica quantos passos são necessários para ficar a uma distância escolhida do equilíbrio a partir de qualquer estado inicial. Uma previsão próxima do equilíbrio ainda conserva uma pequena influência da evidência atual; ela não é uma reinicialização exata.

A predição não precisa aumentar a incerteza a cada passo. A partir de (0,5; 0,5), essa cadeia meteorológica prevê (0,6; 0,4), uma distribuição mais concentrada. A convergência diz respeito à perda de dependência da crença inicial, não a uma regra de que as previsões devam se tornar uniformes.

Preveja uma observação

Uma previsão de produção calcula a média da verossimilhança do sensor sobre os estados previstos:

Para Alta no dia 4, use a predição de estados do dia 4, não a filtragem do dia 3: $\mathrm{0,6864}(\mathrm{0,8})+\mathrm{0,3136}(\mathrm{0,3})\approx \mathrm{0,6432}$. A probabilidade de Ensolarado e a probabilidade de produção Alta diferem porque ambos os estados meteorológicos podem produzir Alta.

Guarde os totais da filtragem

Antes da normalização de cada atualização, seu total é a probabilidade daquela observação dadas as anteriores. Chame-o de $c_t=P(e_t\mid e_{1:t-1})$. A regra da cadeia fornece

Para Baixa, Baixa, Alta, os totais são aproximadamente 0,45; 0,4556 e 0,5429. Seu produto, calculado antes do arredondamento, é 0,1113. Essa é uma soma sobre todos os caminhos ocultos compatíveis com as evidências. O melhor caminho sozinho contribui com 0,04704, apenas parte do total.

Uma passagem de avanço não normalizada fornece a mesma verossimilhança pela soma de suas entradas finais. Uma passagem normalizada é mais estável, desde que os totais sejam guardados. Em sequências longas, armazene $\log P(e_{1:t})={\sum }_i\log c_i$ em vez de multiplicar valores minúsculos. Aqui, o logaritmo natural é cerca de −2,196.

Compare modelos com as mesmas evidências

Uma verossimilhança mede em que grau um modelo explica uma determinada sequência de observações. Para comparar HMMs candidatos de palavras com a mesma gravação, calcule a pontuação dessa gravação em cada modelo e combine-a com as probabilidades a priori das palavras ao determinar suas probabilidades a posteriori. Sequências mais longas geralmente têm verossimilhanças brutas menores, portanto um número menor vindo de uma gravação mais longa, por si só, não indica um modelo pior.

Uma observação posterior pode mudar sua crença sobre um estado anterior. A suavização estima $P(X_k\mid e_{1:t})$ para $k<t$. Ela é útil para reconstruir uma trajetória registrada ou quando uma aplicação pode esperar um pouco antes de fornecer uma estimativa passada.

Divida as evidências no instante de interesse

A filtragem já resumiu as evidências até o instante $k$ como $f_k(x)=P(X_k=x\mid e_{1:k})$. Uma mensagem de retrocesso resume as observações restantes como uma verossimilhança, $b_k(x)=P(e_{k+1:t}\mid X_k=x)$. Combine-as estado a estado:

Normalize os produtos entre os estados. As evidências posteriores são ponderadas conforme sua plausibilidade a partir de cada estado candidato no instante $k$.

Propague a verossimilhança futura para trás

No último instante, não há observações posteriores, portanto $b_t(x)=1$ para cada estado. Retroceder um passo fornece

Para cada sucessor possível, multiplique a probabilidade de chegar a ele, a verossimilhança de sua observação e a verossimilhança futura restante. Depois, some os resultados para todos os sucessores. Uma mensagem de retrocesso é uma função de verossimilhança sobre possíveis estados iniciais, não uma distribuição de estados; suas entradas não precisam somar 1.

Suavize o dia 2 no exemplo solar

As observações são Baixa, Baixa, Alta. Após as duas leituras Baixa, a crença filtrada do dia 2 é aproximadamente (0,2146; 0,7854). Para a leitura final Alta, a verossimilhança de retrocesso a partir de um dia 2 ensolarado é $\mathrm{0,8}(\mathrm{0,8})+\mathrm{0,2}(\mathrm{0,3})=\mathrm{0,70}$. A partir de um dia 2 nublado, é $\mathrm{0,4}(\mathrm{0,8})+\mathrm{0,6}(\mathrm{0,3})=\mathrm{0,50}$.

Multiplique: os produtos são aproximadamente $\mathrm{0,2146}(\mathrm{0,70})=\mathrm{0,1502}$ e $\mathrm{0,7854}(\mathrm{0,50})=\mathrm{0,3927}$. Normalize seus valores não arredondados para obter uma probabilidade de 0,2767 de Ensolarado no dia 2. Alta no dia 3 torna um dia 2 ensolarado mais plausível do que indicava a probabilidade filtrada original de 0,2146.

Continue até o dia 1

A verossimilhança de retrocesso a partir de Ensolarado no dia 1 é $\mathrm{0,8}(\mathrm{0,2})(\mathrm{0,70})+\mathrm{0,2}(\mathrm{0,7})(\mathrm{0,50})=\mathrm{0,182}$. A partir de Nublado, é $\mathrm{0,4}(\mathrm{0,2})(\mathrm{0,70})+\mathrm{0,6}(\mathrm{0,7})(\mathrm{0,50})=\mathrm{0,266}$. Combine com $f_1=(2\mathrm{/}9,7\mathrm{/}9)$ e normalize. A probabilidade suavizada de Ensolarado é aproximadamente 0,1635, abaixo de 0,2222: o futuro completo inclui outra produção Baixa além da Alta final.

Evidências posteriores não precisam deslocar todas as estimativas passadas na mesma direção. No instante final, a suavização é igual à filtragem porque não há evidências posteriores.

Organize o cálculo

O algoritmo de avanço e retrocesso primeiro armazena todas as crenças de avanço, depois calcula as mensagens de retrocesso e os produtos normalizados. Para $t$ passos e $S$ estados, o cálculo denso custa $O(S^{2}t)$ e armazena $O(St)$ valores. A suavização com atraso fixo informa o estado de um número fixo de passos antes do presente, em troca de um atraso que permite usar mais evidências.

Inverter a lista de observações e executar um filtro comum é um cálculo diferente. A recursão de retrocesso usa as transições originais para frente e as verossimilhanças futuras; ela não introduz uma nova distribuição inicial a priori no fim do registro. Probabilidades suavizadas de estados também fornecem contagens esperadas para o aprendizado de Baum–Welch.

Às vezes, a resposta desejada é uma explicação completa das observações. A decodificação de Viterbi encontra a sequência de estados ocultos mais provável. Ela leva em conta as transições entre estados, que escolhas separadas dos estados mais prováveis em instantes individuais podem ignorar.

Mude o objetivo

O alvo é $\arg {\max }_{x_{1:t}}P(x_{1:t}\mid e_{1:t})$. Todas as candidatas têm o mesmo denominador de evidências, portanto maximizar a pontuação conjunta $P(x_{1:t},e_{1:t})$ seleciona o mesmo caminho. Essa pontuação difere de uma probabilidade a posteriori do estado final, que soma todos os caminhos que terminam nesse estado.

Com as observações solares Alta, Baixa, os estados individuais mais prováveis após a suavização são Ensolarado no dia 1 e Nublado no dia 2. Ainda assim, Ensolarado, Ensolarado é o caminho completo mais provável: sua probabilidade a posteriori é cerca de 0,3282, em comparação com 0,2872 para Ensolarado, Nublado. Com transições proibidas, estados individualmente plausíveis podem até formar um caminho impossível.

Mantenha o melhor prefixo para cada estado final

Seja $m_t(j)$ a melhor pontuação conjunta de caminho e evidências que termina no estado $j$. Inicialize $m_1(j)=P(X_1=j)P(e_1\mid j)$. Depois, use

Guarde o predecessor que maximiza a expressão como um ponteiro para o predecessor. Caminhos que terminam no mesmo estado têm as mesmas continuações futuras possíveis, portanto um prefixo com pontuação menor pode ser descartado. O algoritmo de avanço soma os prefixos concorrentes; Viterbi seleciona seu máximo.

Preencha a treliça para Baixa, Baixa, Alta

As pontuações iniciais são (0,10; 0,35). No dia 2, os candidatos a Ensolarado antes da emissão são $\mathrm{0,10}(\mathrm{0,8})=\mathrm{0,08}$ e $\mathrm{0,35}(\mathrm{0,4})=\mathrm{0,14}$. Mantenha o segundo e multiplique por 0,2 para obter 0,028, com ponteiro para Nublado. Para Nublado, compare 0,02 com 0,21; multiplicar o maior por 0,7 fornece 0,147, também com ponteiro para Nublado.

No dia 3, Ensolarado compara $\mathrm{0,028}(\mathrm{0,8})=\mathrm{0,0224}$ com $\mathrm{0,147}(\mathrm{0,4})=\mathrm{0,0588}$. Multiplicar o maior pela verossimilhança de Alta, 0,8, fornece 0,04704. Nublado compara 0,0056 com 0,0882; multiplicar o maior por 0,3 fornece 0,02646. Ambos os ponteiros finais levam a Nublado no dia 2.

Percorra os ponteiros a partir do fim

A maior pontuação final é 0,04704 em Ensolarado. Siga seu ponteiro até Nublado no dia 2 e depois esse ponteiro até Nublado no dia 1. Inverta esse percurso para obter Nublado, Nublado, Ensolarado. Dividir pela verossimilhança das evidências 0,1113 fornece sua probabilidade a posteriori, aproximadamente 0,4226.

Escolher a maior pontuação separadamente em cada coluna descartaria as relações entre predecessores armazenadas. O vetor de pontuações finais também não pode ser normalizado para obter uma crença filtrada: ele mantém apenas um caminho por estado, não suas somas.

Use logaritmos para sequências longas

Produtos podem sofrer subfluxo. Em vez disso, armazene pontuações logarítmicas:

Logaritmos preservam a ordem, portanto o caminho e os ponteiros permanecem inalterados. Probabilidades zero tornam-se infinito negativo. De modo equivalente, pontuações logarítmicas negativas transformam a decodificação em um caminho de custo mínimo por um grafo organizado em camadas de tempo, ou treliça. O Viterbi denso custa $O(S^{2}t)$ em tempo e armazena $O(St)$ ponteiros. Se caminhos empatam na maior pontuação, cada um é uma explicação mais provável válida.

Uma tabela de probabilidades torna-se difícil de armazenar quando o espaço de estados é enorme. Crenças contínuas também não têm, em geral, uma tabela finita. Um filtro de partículas representa uma crença usando estados amostrados, permitindo que o cálculo se concentre em uma população manejável de possibilidades.

Represente probabilidade com partículas

Cada partícula é um estado completo, não um objeto físico separado. Após a reamostragem, todas as partículas têm peso igual, e a probabilidade estimada de um estado é a fração que o ocupa. Dez partículas divididas em sete Ensolarado e três Nublado representam a crença (0,7; 0,3).

Sorteie as partículas iniciais de $P(X_1)$. Uma distribuição a priori de (0,5; 0,5) fornece contagens iguais esperadas, mas não obriga toda amostra aleatória a se dividir igualmente. Segundo nossa convenção de tempo, pondere essas partículas iniciais pela primeira observação e faça a reamostragem antes de qualquer transição.

Avance o tempo amostrando transições

Para cada passo posterior, mova cada partícula independentemente usando a linha de transição de seu estado atual. Com as linhas meteorológicas (0,8; 0,2) e (0,4; 0,6), sete partículas Ensolarado e três Nublado têm uma contagem esperada de Ensolarado de $7(\mathrm{0,8})+3(\mathrm{0,4})=\mathrm{6,8}$ após o movimento.

Uma amostra realizada pode conter seis partículas Ensolarado e quatro Nublado. Uma contagem esperada pode ser fracionária; uma contagem realizada de partículas deve ser inteira. Manter exatamente 6,8 partículas não seria um algoritmo de amostragem.

Pondere pela leitura

Suponha que a nova produção solar seja Baixa. Cada partícula Ensolarado recebe verossimilhança 0,2; cada partícula Nublado recebe 0,7. As seis partículas Ensolarado têm peso total $6(\mathrm{0,2})=\mathrm{1,2}$, e as quatro Nublado têm $4(\mathrm{0,7})=\mathrm{2,8}$. De um peso total de 4,0, Ensolarado tem probabilidade ponderada 0,3 e Nublado, 0,7.

As contagens importam tanto quanto os pesos por partícula. Normalizar apenas 0,2 e 0,7 ignoraria quanta probabilidade prevista cada grupo representava. A ponderação reutiliza a mesma atualização de Bayes da filtragem exata nessa predição amostrada.

Reamostre uma nova população

Sorteie dez partículas com reposição, cada partícula antiga sendo selecionada em proporção ao seu peso. Cada novo sorteio é Ensolarado com probabilidade 0,3 e Nublado com probabilidade 0,7. A contagem esperada de Ensolarado é três, embora uma execução possa produzir duas, quatro ou outra contagem. Cópias múltiplas são permitidas; elas representam massa de probabilidade.

Redefina as partículas resultantes para pesos iguais. A evidência já afetou quais partículas foram copiadas, portanto manter os pesos antigos de verossimilhança a contaria novamente. A próxima iteração move essa nova população antes de processar a observação seguinte.

Compare com a atualização exata

A filtragem exata a partir de (0,7; 0,3) prevê (0,68; 0,32). Baixa então fornece pesos (0,136; 0,224), portanto a probabilidade a posteriori exata de Ensolarado é $\mathrm{0,136}\mathrm{/}\mathrm{0,36}\approx \mathrm{0,3778}$. O resultado ponderado da execução com partículas foi 0,3 porque seu movimento aleatório produziu apenas seis partículas Ensolarado. A reamostragem introduz outra fonte de variação.

O ciclo é, portanto, inicialização, ponderação pela primeira observação e reamostragem, seguidas de movimento, ponderação e reamostragem repetidos. Antes da reamostragem, leia as frações ponderadas; depois, leia as contagens. Um passo custa aproximadamente $O(N)$ para $N$ partículas quando a amostragem de estados e a ponderação têm custo fixo. Para dois estados meteorológicos, a filtragem exata é mais simples. Métodos de partículas tornam-se úteis quando um estado grande ou contínuo não dispõe de um filtro exato compacto de custo viável.

Uma estimativa por partículas é aleatória, portanto sua qualidade depende tanto do tamanho da população quanto dos locais em que as partículas sobrevivem. Mais partículas melhoram a aproximação, mas uma população grande ainda pode ser pouco eficaz quando quase toda a informação útil está em poucas amostras.

Entenda a escala de precisão

Para uma estimativa de probabilidade $p$ por amostras independentes, o erro padrão é aproximadamente $\sqrt{p(1-p)\mathrm{/}N}$. Com $p=\mathrm{0,3}$, ele é cerca de 0,046 para 100 amostras e 0,0046 para 10.000. O erro do filtro de partículas muitas vezes segue aproximadamente a mesma escala $1\mathrm{/}\sqrt{N}$, embora as partículas reamostradas sejam dependentes e a dificuldade do modelo importe.

Quadruplicar a população reduz o erro aproximadamente à metade; duplicá-la não. Para um histórico fixo de observações, aumentar o número de partículas faz um filtro de partículas consistente se aproximar da crença exata. Isso não torna exata uma execução finita nem elimina erros no modelo subjacente. Fixe uma semente aleatória para comparações reproduzíveis ou compare resultados de várias execuções.

Diferencie duas falhas

Sem reamostragem, multiplicar verossimilhanças por muitos passos pode deixar quase todas as partículas com peso desprezível. A reamostragem substitui esse desperdício por cópias de estados úteis. Mas também pode eliminar uma localização alternativa que temporariamente corresponde menos às evidências.

A reamostragem sozinha não consegue recriar uma região ausente. A recuperação depende de amostras de movimento a alcançarem ou de outro mecanismo introduzir partículas nela. Se as transições tornam essa região quase inacessível, a recuperação pode ser lenta. Acrescentar pequenas perturbações aleatórias ou substituir uma pequena fração por novas partículas pode ajudar, mas essas escolhas devem respeitar a representação de estado e a aproximação pretendida.

Trate o peso total zero

Se todas as partículas recebem peso zero, as probabilidades de reamostragem ficam indefinidas. A observação pode ser possível em outro lugar do modelo, embora a população amostrada não tenha alcançado esses estados. Reinicialize a partir de uma distribuição adequada, como a distribuição a priori ou uma distribuição uniforme sobre estados válidos, e verifique o modelo de sensor. Um componente para valores atípicos com probabilidade diferente de zero pode reduzir essas falhas. Se o próprio modelo descarta a observação em todos os estados, mais partículas, sozinhas, não resolvem o problema.

Escolha uma representação adequada ao modelo

A filtragem exata pelo algoritmo de avanço é adequada a espaços de estados discretos pequenos. Um filtro de Kalman é exato quando a distribuição a priori é gaussiana e os modelos de transição e de sensor são lineares com ruído gaussiano; nesse caso, uma média e uma covariância descrevem a crença. Um filtro de partículas acomoda modelos não lineares e crenças com picos separados.

Uma única distribuição gaussiana não consegue representar fielmente um robô que provavelmente está em um de dois corredores distantes, mas dificilmente entre eles. Agrupamentos de partículas podem manter ambas as alternativas. Para um modelo de rastreamento linear gaussiano, a representação de Kalman geralmente evita ruído de amostragem desnecessário.

Em uma DBN, cada partícula contém uma atribuição completa a todas as variáveis de estado. Amostre as variáveis do próximo passo em ordem topológica a partir de seus modelos condicionados aos nós pais. A fatoração reduz o trabalho por amostra em comparação com a enumeração de todos os estados conjuntos, embora crenças de alta dimensão ainda possam exigir muitas partículas para cobrir suas regiões importantes.

O rastreamento combina movimento incerto com medições ruidosas. O estado oculto pode conter posição e velocidade; as observações podem vir de GPS, radar ou câmera. A filtragem mantém uma distribuição de localizações plausíveis de uma leitura para a seguinte.

Localize em um corredor de cinco células

Um robô ocupa uma de cinco células, com portas nas células 1 e 4. Seu sensor indica uma porta com probabilidade 0,9 em uma porta e 0,2 nos demais lugares. Comece com uma distribuição uniforme, com probabilidade 0,2 por célula. Uma indicação de porta fornece pesos (0,18; 0,04; 0,04; 0,18; 0,04), totalizando 0,48.

A crença atualizada é $(\mathrm{0,375};1\mathrm{/}12;1\mathrm{/}12;\mathrm{0,375};1\mathrm{/}12)\mathrm{.}$ Ambas as células com porta continuam plausíveis. Selecionar apenas um pico descartaria a simetria que o sensor ainda não resolveu.

Mova toda a crença

O robô tenta mover-se uma célula para a direita. Ele consegue com probabilidade 0,8 e permanece no lugar com probabilidade 0,2; a partir da célula 5, permanece com certeza junto à parede. Cada célula recebe contribuições de todas as células iniciais que podem alcançá-la.

A célula 1 recebe $\mathrm{0,375}(\mathrm{0,2})=\mathrm{0,075}$. A célula 2 recebe $\mathrm{0,375}(\mathrm{0,8})+(1\mathrm{/}12)(\mathrm{0,2})\approx \mathrm{0,3167}$. As células 3 e 4 recebem aproximadamente 0,0833 e 0,1417. A célula 5 recebe $(\mathrm{0,375})(\mathrm{0,8})+1\mathrm{/}12\approx \mathrm{0,3833}$: tanto as chegadas da célula 4 quanto toda a massa de probabilidade já existente na célula 5 permanecem ali.

A predição é aproximadamente (0,0750; 0,3167; 0,0833; 0,1417; 0,3833). Tratar a fronteira como outro movimento comum de probabilidade 0,8 faria perder probabilidade para além do corredor modelado.

Observe a ausência de porta

A verossimilhança de ausência de porta é 0,1 nas células 1 e 4 e 0,8 nos demais lugares. Multiplicar a predição não arredondada fornece peso total de aproximadamente 0,6483. A normalização produz (0,0116; 0,3907; 0,1028; 0,0219; 0,4730).

As localizações prováveis são agora as células 2 e 5, logo após as duas portas. A crença permanece multimodal, com picos separados. Uma leitura de sensor é uma evidência, não uma medição da posição verdadeira; manter alternativas permite que movimentos e leituras posteriores as distingam.

Estenda a robôs reais

Na localização de Monte Carlo, uma partícula é uma pose: posição em metros e orientação. Mova cada pose usando o movimento comandado mais ruído e depois pondere-a pela correspondência entre as distâncias observadas e as distâncias previstas a partir de um mapa conhecido. Uma população inicial concentrada acompanha uma localização inicial conhecida; uma população ampla permite a localização global.

Se o mapa também for desconhecido, inclua-o no estado oculto. A localização e mapeamento simultâneos, ou SLAM, estima mapa e pose conjuntamente. Com vários objetos, outro problema é a associação de dados: decidir a qual objeto pertence cada detecção. Atribuições diferentes produzem hipóteses diferentes de trajetória.

O rastreamento de veículos pode combinar uma predição de movimento com leituras de GPS. A 15 m/s com passos de um segundo, o movimento esperado é cerca de 15 m entre leituras. Um modelo de Kalman adequado combina movimento e medição incertos para reduzir o efeito de leituras com ruído. Um modelo de transição que não permite variação real no movimento pode excluir a trajetória verdadeira, mesmo quando seus cálculos estão corretos.

Modelos de sequências podem inferir rótulos além de estados físicos. Um reconhecedor de fala conecta um sinal sonoro em evolução a palavras possíveis. Um etiquetador morfossintático conecta palavras observadas a rótulos gramaticais ocultos. Ambos precisam atribuir pontuações a escolhas em contexto ao longo do tempo.

Combine correspondência sonora e probabilidade linguística

O reconhecimento de fala busca a sequência de palavras com maior probabilidade a posteriori:

O modelo acústico $P(s\mid w)$ avalia o quanto as palavras explicam bem o som; o modelo de linguagem $P(w)$ avalia sua plausibilidade a priori. O denominador compartilhado $P(s)$ não afeta a classificação. Uma verossimilhança acústica não é, por si só, uma probabilidade a posteriori das palavras.

Para pontuações ilustrativas, compare “o concerto começou” com “o conserto começou”. As verossimilhanças acústicas são 0,0004 e 0,0005; as probabilidades de linguagem são 0,00002 e 0,000001. O primeiro produto é $8\times {10}^{-9}$ e o segundo, $5\times {10}^{-10}$. O contexto linguístico faz a primeira frase vencer, apesar de sua verossimilhança acústica um pouco menor.

Transforme áudio em uma sequência temporal

Uma configuração comum usa quadros sobrepostos de 25 ms iniciados a cada 10 ms, produzindo cerca de 100 vetores de características por segundo. Os vetores são observações. Os estados ocultos representam partes dos sons da fala, ou fones, muitas vezes com estados de começo, meio e fim. Um dicionário de pronúncia conecta palavras a fones.

Laços para o próprio estado permitem que um estado de som ocupe vários quadros. Sem flexibilidade de duração, uma mudança na velocidade da fala exigiria um alinhamento fixo e muitas vezes inadequado entre quadros e estados de som. Caminhos de estados diferentes expressam alinhamentos diferentes da mesma gravação observada.

Represente um contexto linguístico curto

Um modelo de bigramas aproxima uma sequência de palavras por $P(w_1){\prod }_{i=2}^{n}P(w_i\mid w_{i-1})$. Um trigrama usa as duas palavras anteriores. Estime essas probabilidades condicionais a partir de contagens em textos. A hipótese de Markov aqui é uma aproximação prática: relações gramaticais e semânticas de longo alcance podem se estender além de uma ou duas palavras anteriores.

Viterbi pode encontrar o melhor caminho de estados por modelos conectados de fones e palavras. Para um vocabulário grande, a busca em feixe descarta caminhos parciais menos promissores para reduzir o trabalho. Uma vez descartado, um caminho não pode vencer depois, portanto um feixe estreito pode perder o melhor caminho completo. Além disso, o melhor caminho único de estados para uma sequência de palavras tem um objetivo diferente da soma de todos os seus alinhamentos possíveis.

Use a mesma estrutura para etiquetas

Na etiquetagem morfossintática, os estados são etiquetas e as observações são palavras. As transições avaliam $P({\mathrm{t}\mathrm{a}\mathrm{g}}_i\mid {\mathrm{t}\mathrm{a}\mathrm{g}}_{i-1})$; as emissões avaliam $P({\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{d}}_i\mid {\mathrm{t}\mathrm{a}\mathrm{g}}_i)$. Em “A velha casa”, “velha” pode ser substantivo e “casa” verbo, ou “velha” pode ser adjetivo e “casa” substantivo. O caminho de etiquetas deve levar em conta tanto as verossimilhanças das palavras quanto as transições entre etiquetas.

Situe os HMMs na prática de processamento de fala

Sistemas de vocabulário grande da década de 1980 ao início da década de 2010 costumavam combinar HMMs com modelos acústicos de mistura gaussiana. Por volta de 2010–2012, modelos acústicos neurais ganharam destaque em sistemas híbridos DNN–HMM. Sistemas neurais modernos de ponta a ponta podem mapear áudio para texto sem um HMM explícito. As ideias compartilhadas de alinhamento incerto, pontuação de sequências e programação dinâmica continuam úteis, e HMMs também aparecem em aplicações como a identificação de genes em DNA.