Modelo oculto de Markov

Os estados do processo ${\displaystyle X_{n}}$ (resp. ${\displaystyle X_{t})}$ são chamados de estados ocultos, e ${\displaystyle \operatorname {\mathbf {P} } {\bigl (}Y_{n}\in A\mid X_{n}=x_{n}{\bigr )}}$ (resp. ${\displaystyle \operatorname {\mathbf {P} } {\bigl (}Y_{t}\in A\mid X_{t}\in B_{t}{\bigr )})}$ é chamado de probabilidade de emissão ou probabilidade de saída.

Em sua forma discreta, um processo de Markov oculto pode ser visualizado como uma generalização do problema da urna com reposição (onde cada item da urna é devolvido à urna original antes do próximo passo).^[7]

Considere dois amigos, Alice e Bob, que moram longe um do outro e conversam diariamente por telefone sobre o que fizeram naquele dia. Bob só se interessa por três atividades: passear no parque, fazer compras e limpar seu apartamento. A escolha do que fazer é determinada exclusivamente pelo clima em um determinado dia. Alice não tem informações precisas sobre o tempo, mas conhece as tendências gerais. Com base no que Bob lhe diz que fez a cada dia, Alice tenta adivinhar como o tempo devia estar.

Alice acredita que o clima opera como uma cadeia de Markov discreta. Existem dois estados, "Chuvoso" e "Ensolarado", mas ela não pode observá-los diretamente; ou seja, eles estão ocultos para ela. Em cada dia, há uma certa probabilidade de que Bob realize uma das seguintes atividades, dependendo do tempo: "passear", "fazer compras" ou "limpar". Como Bob conta a Alice sobre suas atividades, essas são as observações. O sistema inteiro é o de um modelo oculto de Markov (HMM).

Alice conhece as tendências gerais do tempo na região e o que Bob gosta de fazer em média. Em outras palavras, os parâmetros do HMM são conhecidos. Eles podem ser representados da seguinte forma na linguagem de programação Python:

states = ("Rainy", "Sunny")

observations = ("walk", "shop", "clean")

start_probability = {"Rainy": 0.6, "Sunny": 0.4}

transition_probability = {
    "Rainy": {"Rainy": 0.7, "Sunny": 0.3},
    "Sunny": {"Rainy": 0.4, "Sunny": 0.6},
}

emission_probability = {
    "Rainy": {"walk": 0.1, "shop": 0.4, "clean": 0.5},
    "Sunny": {"walk": 0.6, "shop": 0.3, "clean": 0.1},
}

Neste trecho de código, start_probability representa a crença de Alice sobre em qual estado o HMM está quando Bob liga para ela pela primeira vez (tudo que ela sabe é que, em média, tende a chover). A distribuição de probabilidade particular usada aqui não é a de equilíbrio, que é (dadas as probabilidades de transição) aproximadamente {'Rainy': 0.57, 'Sunny': 0.43}. A transition_probability representa a mudança do tempo na cadeia de Markov subjacente. Neste exemplo, há apenas 30% de chance de que amanhã seja ensolarado se hoje estiver chuvoso. A emission_probability representa a probabilidade de Bob realizar uma certa atividade em cada dia. Se chover, há 50% de chance de ele estar limpando seu apartamento; se fizer sol, há 60% de chance de ele estar fora para passear.

Um exemplo semelhante é melhor elaborado na página do algoritmo de Viterbi.

A tarefa é computar da melhor maneira, dados os parâmetros do modelo, a probabilidade de uma sequência de saída específica. Isso requer somar sobre todas as sequências de estados possíveis:

A probabilidade de observar uma sequência

${\displaystyle Y=y(0),y(1),\dots ,y(L-1),}$

de comprimento L é dada por

${\displaystyle P(Y)=\sum _{X}P(Y\mid X)P(X),}$

onde a soma percorre todas as sequências possíveis de nós ocultos

${\displaystyle X=x(0),x(1),\dots ,x(L-1).}$

Aplicando o princípio da programação dinâmica, esse problema também pode ser tratado eficientemente usando o algoritmo forward.

Uma série de tarefas relacionadas questiona a probabilidade de uma ou mais variáveis latentes, dados os parâmetros do modelo e uma sequência de observações ${\displaystyle y(1),\dots ,y(t)}$.

Para alguns dos problemas acima, também pode ser interessante questionar sobre a significância estatística. Qual é a probabilidade de que uma sequência sorteada a partir de alguma distribuição nula tenha uma probabilidade HMM (no caso do algoritmo forward) ou uma probabilidade máxima de sequência de estados (no caso do algoritmo de Viterbi) pelo menos tão grande quanto a de uma sequência de saída específica?^[8] Quando um HMM é usado para avaliar a relevância de uma hipótese para uma sequência de saída particular, a significância estatística indica a taxa de falsos positivos associada à falha em rejeitar a hipótese para a sequência de saída.

Nos modelos ocultos de Markov considerados acima, o espaço de estados das variáveis ocultas é discreto, enquanto as observações em si podem ser discretas (tipicamente geradas a partir de uma distribuição categórica) ou contínuas (tipicamente a partir de uma distribuição gaussiana). Os modelos ocultos de Markov também podem ser generalizados para permitir espaços de estado contínuos. Exemplos de tais modelos são aqueles em que o processo de Markov sobre as variáveis ocultas é um sistema dinâmico linear, com uma relação linear entre variáveis relacionadas e em que todas as variáveis ocultas e observadas seguem uma distribuição gaussiana. Em casos simples, como o sistema dinâmico linear recém-mencionado, a inferência exata é tratável (neste caso, usando o filtro de Kalman); entretanto, em geral, a inferência exata em HMMs com variáveis latentes contínuas é inviável, e métodos aproximados devem ser usados, como o filtro de Kalman estendido ou o filtro de partículas.

Atualmente, a inferência em modelos ocultos de Markov é realizada em cenários não paramétricos, onde a estrutura de dependência permite a identificabilidade do modelo^[41] e os limites de aprendizado ainda estão sob exploração.^[42]

Modelos ocultos de Markov são modelos generativos, nos quais a distribuição conjunta das observações e estados ocultos, ou equivalentemente tanto a distribuição a priori dos estados ocultos (as probabilidades de transição) quanto a distribuição condicional das observações dados os estados (as probabilidades de emissão), é modelada. Os algoritmos acima assumem implicitamente uma distribuição a priori uniforme sobre as probabilidades de transição. Contudo, também é possível criar modelos ocultos de Markov com outros tipos de distribuições a priori. Uma candidata óbvia, dada a distribuição categórica das probabilidades de transição, é a distribuição de Dirichlet, que é a distribuição a priori conjugada da distribuição categórica. Tipicamente, escolhe-se uma distribuição de Dirichlet simétrica, refletindo ignorância sobre quais estados são inerentemente mais prováveis do que outros. O único parâmetro dessa distribuição (denominado parâmetro de concentração) controla a densidade relativa ou esparsidade da matriz de transição resultante. Uma escolha de 1 produz uma distribuição uniforme. Valores maiores que 1 produzem uma matriz densa, na qual as probabilidades de transição entre pares de estados tendem a ser quase iguais. Valores menores que 1 resultam em uma matriz esparsa na qual, para cada estado de origem dado, apenas um pequeno número de estados de destino têm probabilidades de transição não negligenciáveis. Também é possível usar uma distribuição a priori de Dirichlet em dois níveis, na qual uma distribuição de Dirichlet (a distribuição superior) governa os parâmetros de outra distribuição de Dirichlet (a distribuição inferior), que por sua vez governa as probabilidades de transição. A distribuição superior rege a distribuição geral dos estados, determinando a probabilidade de ocorrência de cada estado; seu parâmetro de concentração determina a densidade ou esparsidade dos estados. Essa distribuição a priori de dois níveis, onde ambos os parâmetros de concentração são ajustados para produzir distribuições esparsas, pode ser útil, por exemplo, na etiquetagem não supervisionada de classes gramaticais, onde algumas classes ocorrem muito mais frequentemente do que outras; algoritmos de aprendizado que assumem uma distribuição a priori uniforme geralmente apresentam mau desempenho nesta tarefa. Os parâmetros de modelos deste tipo, com distribuições a priori não uniformes, podem ser aprendidos usando a amostragem de Gibbs ou versões estendidas do algoritmo de maximização da expectativa.

Uma extensão dos modelos ocultos de Markov descritos anteriormente com prioris de Dirichlet usa um processo de Dirichlet no lugar de uma distribuição de Dirichlet. Este tipo de modelo permite um número desconhecido e potencialmente infinito de estados. É comum usar um processo de Dirichlet de dois níveis, semelhante ao modelo anteriormente descrito com dois níveis de distribuições de Dirichlet. Um modelo desse tipo é chamado de modelo oculto de Markov do processo de Dirichlet hierárquico, ou simplesmente HDP-HMM. Foi originalmente descrito sob o nome "Modelo Oculto de Markov Infinito"^[43] e foi posteriormente formalizado em "Processos Hierárquicos de Dirichlet".^[44]

Um tipo diferente de extensão usa um modelo discriminativo no lugar do modelo generativo dos HMMs padrão. Esse tipo de modelo aborda diretamente a distribuição condicional dos estados ocultos dadas as observações, em vez de modelar a distribuição conjunta. Um exemplo desse modelo é o chamado modelo de Markov de máxima entropia (MEMM), que modela a distribuição condicional dos estados usando regressão logística (também conhecido como "modelo de máxima entropia"). A vantagem desse tipo de modelo é que recursos (ou seja, funções) arbitrários das observações podem ser modelados, permitindo que conhecimentos do domínio específico sobre o problema em questão sejam inseridos no modelo. Modelos dessa categoria não se limitam a modelar dependências diretas entre um estado oculto e sua observação associada; em vez disso, atributos de observações próximas, combinações da observação associada e observações vizinhas, ou até mesmo observações arbitrárias a qualquer distância de um determinado estado oculto podem ser incluídos no processo usado para determinar o valor de um estado oculto. Ademais, não é necessário que esses recursos sejam estatisticamente independentes uns dos outros, como seria o caso se tais recursos fossem usados em um modelo generativo. Por fim, atributos arbitrários em pares de estados ocultos adjacentes podem ser usados em vez das simples probabilidades de transição. As desvantagens de tais modelos são: (1) Os tipos de distribuições a priori que podem ser colocadas nos estados ocultos são severamente limitadas; (2) Não é possível prever a probabilidade de ver uma observação arbitrária. Essa segunda limitação frequentemente não é um problema na prática, já que muitos usos comuns de HMMs não exigem tais probabilidades preditivas.

Uma variante do modelo discriminativo descrito anteriormente é o campo aleatório condicional de cadeia linear. Ele usa um modelo gráfico não direcionado (também conhecido como campo aleatório de Markov) em vez dos modelos gráficos direcionados do MEMM e modelos semelhantes. A vantagem desse tipo de modelo é que ele não sofre do chamado problema de viés de rótulo dos MEMMs e, portanto, pode fazer previsões mais precisas. A desvantagem é que o treinamento pode ser mais lento do que o dos MEMMs.

Ainda outra variante é o modelo oculto de Markov fatorial, que permite que uma única observação seja condicionada às variáveis ocultas correspondentes de um conjunto de ${\displaystyle K}$ cadeias de Markov independentes, ao invés de uma única cadeia de Markov. Ele é equivalente a um único HMM com ${\displaystyle N^{K}}$ estados (assumindo que existem ${\displaystyle N}$ estados para cada cadeia), e, portanto, o aprendizado em um modelo desse tipo é difícil: para uma sequência de comprimento ${\displaystyle T}$, um algoritmo simples de Viterbi tem complexidade ${\displaystyle O(N^{2K}\,T)}$. Para encontrar uma solução exata, um algoritmo de árvore de junção poderia ser usado, mas resulta em uma complexidade de ${\displaystyle O(N^{K+1}\,K\,T)}$. Na prática, técnicas aproximadas, como abordagens variacionais, poderiam ser usadas.^[45]

Todos os modelos acima podem ser estendidos para permitir dependências mais distantes entre estados ocultos, por exemplo, permitindo que um dado estado dependa de dois ou três estados anteriores ao invés de um único estado prévio; ou seja, as probabilidades de transição são estendidas para englobar conjuntos de três ou quatro estados adjacentes (ou em geral ${\displaystyle K}$ estados adjacentes). A desvantagem desses modelos é que os algoritmos de programação dinâmica para treiná-los têm um tempo de execução de ${\displaystyle O(N^{K}\,T)}$ para ${\displaystyle K}$ estados adjacentes e um total de ${\displaystyle T}$ observações (ou seja, uma cadeia de Markov de comprimento ${\displaystyle T}$). Essa extensão tem sido amplamente usada em bioinformática, na modelagem de sequências de DNA.

Outra extensão recente é o modelo de Markov em tripleto,^[46] no qual um processo auxiliar subjacente é adicionado para modelar algumas especificidades dos dados. Muitas variantes deste modelo foram propostas. Pode-se mencionar também o interessante elo que foi estabelecido entre a teoria da evidência e os modelos de Markov em tripleto^[47] e que permite a fusão de dados em um contexto markoviano^[48] e modelar dados não estacionários.^[49][50] Estratégias alternativas de fusão de dados em vários fluxos também foram propostas na literatura recente, p. ex.,^[51]

Por fim, uma lógica diferente para lidar com o problema da modelagem de dados não estacionários por meio de modelos ocultos de Markov foi sugerida em 2012.^[52] Consiste no emprego de uma pequena rede neural recorrente (RNN), especificamente uma rede de reservatório (reservoir network),^[53] para capturar a evolução da dinâmica temporal nos dados observados. Essa informação, codificada na forma de um vetor de alta dimensão, é usada como uma variável de condicionamento para as probabilidades de transição de estado do HMM. Sob tal configuração, obtém-se, por fim, um HMM não estacionário, cujas probabilidades de transição evoluem ao longo do tempo de uma maneira que é inferida dos dados, ao contrário de algum modelo ad hoc irrealista de evolução temporal.

Em 2023, dois algoritmos inovadores foram introduzidos para o Modelo Oculto de Markov. Esses algoritmos permitem o cômputo da distribuição a posteriori do HMM sem a necessidade de modelar explicitamente a distribuição conjunta, utilizando apenas as distribuições condicionais.^[54][55] Diferente de métodos tradicionais, como os algoritmos Forward-Backward e de Viterbi, que exigem o conhecimento da lei conjunta do HMM e cujo aprendizado pode ser computacionalmente intenso, os algoritmos Discriminative Forward-Backward e Discriminative Viterbi evitam a necessidade da lei da observação.^[56][57] Esse avanço permite que o HMM seja aplicado como um modelo discriminativo, oferecendo uma abordagem mais eficiente e versátil para o uso de Modelos Ocultos de Markov em várias aplicações.

O modelo adequado no contexto de dados longitudinais é denominado modelo de Markov latente.^[58] A versão básica deste modelo foi estendida para incluir covariáveis individuais, efeitos aleatórios e para modelar estruturas de dados mais complexas, como dados multinível. Uma visão geral completa dos modelos de Markov latentes, com atenção especial às premissas do modelo e ao seu uso prático, é fornecida em.^[59]

• Teif, V. B.; Rippe, K. (2010). «Statistical–mechanical lattice models for protein–DNA binding in chromatin». J. Phys.: Condens. Matter. 22 (41). Bibcode:2010JPCM...22O4105T. PMID 21386588. arXiv:1004.5514. doi:10.1088/0953-8984/22/41/414105 
• A Revealing Introduction to Hidden Markov Models por Mark Stamp, San Jose State University.
• Fitting HMM's with expectation-maximization – complete derivation
• A step-by-step tutorial on HMMs Arquivado em 2017-08-13 no Wayback Machine (Universidade de Leeds)
• Hidden Markov Models (uma exposição utilizando matemática básica)
• Hidden Markov Models (por Narada Warakagoda)
• Hidden Markov Models: Fundamentals and Applications Parte 1, Parte 2 (por V. Petrushin)
• Aula em planilha de cálculo por Jason Eisner, Vídeo e planilha interativa