Compreendendo o Modelo Oculto de Markov

Modelos ocultos de Markov são estruturas probabilísticas onde os dados observados são modelados como uma série de saídas geradas por um de vários estados internos (ocultos). Tanto os modelos de Markov quanto os modelos ocultos de Markov são projetados para lidar com dados que podem ser representados como uma sequência de observações ao longo do tempo.

Conteúdo

Definição do Modelo Oculto de Markov

Um modelo oculto de Markov é uma estrutura probabilística usada para prever os resultados de um evento com base em uma série de observações, considerando um ou vários estados internos ocultos.

Para entender melhor como um modelo oculto de Markov funciona, é útil primeiro compreender o que é um modelo estocástico.

O que é um Modelo Estocástico?

Um processo estocástico é uma coleção de variáveis aleatórias indexadas por alguns conjuntos matemáticos. Em outras palavras, cada variável aleatória do processo estocástico está associada exclusivamente a um elemento no conjunto. O conjunto usado para indexar as variáveis aleatórias é chamado de conjunto de índice, e o conjunto de variáveis aleatórias forma o espaço de estados. Um processo estocástico pode ser classificado de várias maneiras com base no espaço de estados, conjunto de índices, etc.

Quando o processo estocástico é interpretado como tempo, se o processo tem um número finito de elementos, como inteiros, números e números naturais, então é tempo discreto.

É um processo de tempo discreto indexado no tempo “1,2,3,…” que assume valores chamados estados, que são observados.

Por exemplo, se os estados: (S)={hot , cold}
Séries de estados ao longo do tempo: z∈ S_T
O clima para quatro dias pode ser uma sequência: {z1=hot, z2=cold, z3=cold, z4=hot}

Suposições do modelo de Markov

Os modelos de Markov são desenvolvidos com base em duas suposições:

1. Suposição de horizonte limitado

A probabilidade de estar em um estado em um momento t depende apenas do estado no momento (t-1).

Equação de suposição de horizonte limitado

Isso significa que o estado no tempo t representa um resumo suficiente do passado para prever razoavelmente o futuro. Esta suposição é um processo de Markov de ordem 1. Um processo de Markov de ordem k assume independência condicional do estado z_t dos estados que são k + 1-passos de tempo antes dele.

2. Suposição de processo estacionário

Distribuição condicional (probabilidade) sobre o próximo estado, dado o estado atual, não muda ao longo do tempo.

Equação de suposição de processo estacionário

Isso significa que os estados continuam mudando ao longo do tempo, mas o processo subjacente é estacionário.

Convenção de Notação

Existe um estado inicial e uma observação inicial z_0=s_0
s_0: Distribuição de probabilidade inicial sobre estados no tempo 0.
Probabilidade do estado inicial: (π)
No t=1probabilidade de ver o primeiro imóvel z_1 é p(z_1/z_0).
Desde z0=s0:

Matriz de Transição de Estado

𝐀𝐢,𝐣: probabilidade de transição do estado i declarar j a qualquer momento t.

O gráfico a seguir é uma matriz de transição de estado de quatro estados, incluindo o estado inicial:

Gráfico de matriz de transição de estado.

2 perguntas respondidas em um modelo de Markov

Qual é a probabilidade de sequências particulares de estado z?
Como estimamos o parâmetro da matriz de transição de estado A para maximizar a probabilidade da sequência observada?

Probabilidade de sequências particulares em um modelo de Markov

Eq.4. Encontrando a probabilidade de uma sequência particular

Considere a matriz de transição de estado acima. Vamos determinar a probabilidade da sequência:

${z1=shot,z2=scold,z3=srain,z4=srain,z5=scold}\{ z_1 = s_{\text{hot}}, z_2 = s_{\text{cold}}, z_3 = s_{\text{rain}}, z_4 = s_{\text{rain}}, z_5 = s_{\text{cold}} \}$

A probabilidade da sequência é dada por:

$P(s_{\text{hot}} | s_0) \cdot P(s_{\text{cold}} | s_{\text{hot}}) \cdot P(s_{\text{rain}} | s_{\text{cold}}) \cdot P(s_{\text{rain}} | s_{\text{rain}}) \cdot P(s_{\text{cold}} | s_{\text{rain}})$

Dado os valores fornecidos, temos:

$\times 0.1 \times 0.2 \times 0.7 \times 0.2 = 0.000924$

O que é um modelo oculto de Markov (HMM)?

Quando não podemos observar os estados em si, mas apenas o resultado de alguma função de probabilidade (observação) dos estados, utilizamos um Modelo Oculto de Markov (HMM). O HMM é um modelo estatístico de Markov no qual o sistema que está sendo modelado é assumido como um processo de Markov com estados não observados (ocultos).

Modelo de Markov

Série de estados ocultos: $\{z_1, z_2, \ldots\}$ , desenhada do alfabeto estadual $\{s_1, s_2, \ldots, s_{|S|}\}$ , onde $z_i$ pertence a $S$ .

Modelo Oculto de Markov

Série de saídas observadas: $\{x_1, x_2, \ldots\}$ , extraída de um alfabeto de saída $\{v_1, v_2, \ldots, v_{|V|}\}$ , onde $x_i$ pertence a $V$ .

Suposições do Modelo Oculto de Markov

Um modelo oculto de Markov é construído com base em várias suposições, incluindo:

Suposição de Independência de Saída

A observação de saída é condicionalmente independente de todos os outros estados ocultos e de todas as outras observações, dado o estado oculto atual.

2. Matriz de Probabilidade de Emissão

Probabilidade de estado oculto gerar saída v_i dado que o estado no momento correspondente era s_j.

Exemplo de modelo oculto de Markov

Considere o exemplo abaixo, que explica como uma pessoa se sente em diferentes climas.

Fig.3. Modelo de Markov como Máquina de Estado Finito — Imagem do Autor

Quando não podemos observar os estados em si, mas apenas o resultado de alguma função de probabilidade (observação) dos estados, utilizamos um Modelo Oculto de Markov (HMM). O HMM é um modelo estatístico de Markov no qual o sistema que está sendo modelado é assumido como um processo de Markov com estados não observados (ocultos).

Conjunto de Estados e Estados Ocultos

Conjunto de estados: $\{ \text{Happy}, \text{Grumpy} \}$
Conjunto de estados ocultos: $\{ \text{Sunny}, \text{Rainy} \}$
Séries de estados ao longo do tempo: $\in S_T$
Estados observados por quatro dias: ${z1=Happy,z2=Grumpy,z3=Grumpy,z4=Happy}\{ z_1 = \text{Happy}, z_2 = \text{Grumpy}, z_3 = \text{Grumpy}, z_4 = \text{Happy} \}$

O sentimento que você entende de uma pessoa emocionada é chamado de observações, já que você pode observá-los. O clima que influencia o sentimento de uma pessoa é chamado de estado oculto, pois você não pode observá-lo diretamente.

Probabilidades de Emissão

No exemplo acima, sentimentos (“Happy” ou “Grumpy”) podem ser apenas observados. Uma pessoa pode observar que há 80% de chance de alguém estar “Happy” dado que o clima é ensolarado. Da mesma forma, há 60% de chance de uma pessoa estar “Grumpy” dado que o clima é chuvoso. Essas porcentagens são chamadas de probabilidades de emissão, pois lidam com observações.

Probabilidades de Transição

Quando consideramos os climas (estados ocultos) que influenciam as observações, há correlações entre dias consecutivos sendo ensolarados ou dias alternados sendo chuvosos. Há 80% de chance de o clima ser ensolarado em dias sucessivos, enquanto há 60% de chance de ser chuvoso em dias consecutivos. Essas probabilidades que explicam a transição entre estados ocultos são chamadas de probabilidades de transição.

Como Funciona um Modelo Oculto de Markov?

Um Modelo Oculto de Markov responde a três perguntas principais:

Qual é a probabilidade de uma sequência observada?
Qual é a série de estados mais provável de gerar uma sequência observada?
Como podemos aprender os valores dos parâmetros A e B dos HMMs dados alguns dados?

Probabilidade de Sequência Observada

Para calcular a probabilidade de uma sequência observada $x$ , dado uma série possível de estados ocultos, devemos somar a probabilidade dos dados $x$ dada cada série de estados ocultos. Isso leva a uma complexidade de $O(|S|^T)$ . Portanto, dois procedimentos alternativos foram introduzidos para encontrar a probabilidade de uma sequência observada.

Procedimento Forward

Calcule a probabilidade total de todas as observações (de $t_1$ ) até o momento $t$ :

$αi(t)=P(x1,x2,…,xt,zt=si;A,B)\alpha_i (t) = P(x_1, x_2, \ldots, x_t, z_t = s_i; A, B)$

Procedimento Backward

Calcule de forma semelhante a probabilidade total de todas as observações do tempo final ( $T$ ) até $t$ :

$βi(t)=P(xT,xT−1,…,xt+1,zt=si;A,B)\beta_i (t) = P(x_T, x_{T-1}, \ldots, x_{t+1}, z_t = s_i; A, B)$

Modelo de Markov Oculto Usando Procedimento Forward

Abaixo está um exemplo de um modelo de Markov oculto usando o procedimento forward.

Conjunto de estados: $\{ \text{hot}, \text{cold} \}$

Alfabeto de saída: $\{ v_1 = 1 \text{ ice cream}, v_2 = 2 \text{ ice cream}, v_3 = 3 \text{ ice cream} \}$ onde $V$ é o número de sorvetes consumidos em um dia.

Exemplo de sequência: ${ x_1 = v_2, x_2 = v_3, x_3 = v_1, x_4 = v_2 \}$

Máquinas de estados finitos geradas para HMM

Primeiro precisamos calcular as probabilidades anteriores, ou seja, a probabilidade de estar quente ou frio antes de qualquer observação real. Isso pode ser obtido de S_0 ou π. Da Fig.4, S_0 é fornecido como 0,6 e 0,4, que são as probabilidades anteriores. Então, com base nas suposições de Markov e HMM, seguimos os passos nas figuras abaixo para calcular a probabilidade de uma determinada sequência.

1. Primeira saída observada x1=v2

Etapa um do modelo de Markov oculto ilustrado

2. Saída observada x2=v3

3. Saída observada x3 e x4

Da mesma forma para x3=v1 e x4=v2temos que simplesmente multiplicar os caminhos que levam a v1 e v2.

4. Atribuição de Máxima Verossimilhança

Para uma dada sequência observada de saídas𝑥 𝜖 𝑉_𝑇pretendemos encontrar a série de estados mais provável𝑧 𝜖 𝑆_𝑇. Podemos entender isso com um exemplo encontrado abaixo.

Fig.10. Modelo de Markov como uma máquina de estados finitos a partir de dados da Fig.9.

O Algoritmo de Viterbi é um algoritmo de programação dinâmica similar ao procedimento forward que é frequentemente usado para encontrar a máxima verossimilhança. Em vez de rastrear a probabilidade total de gerar as observações, ele rastreia a probabilidade máxima e a sequência de estados correspondente.

Considere a sequência de emoções: H,H,G,G,G,H por seis dias consecutivos. Usando o algoritmo de Viterbi, descobriremos a maior probabilidade da série.

Fig.11. O algoritmo de Viterbi requer a escolha do melhor caminho

Haverá vários caminhos que levarão ao sábado ensolarado, e muitos caminhos que levarão ao sábado chuvoso. Aqui, pretendemos identificar o melhor caminho para o sábado ensolarado ou chuvoso e multiplicar pela probabilidade de emissão de transição de “Feliz”, já que o sábado faz a pessoa se sentir “Feliz”.

Vamos considerar um sábado ensolarado. O dia anterior, sexta-feira, pode ser ensolarado ou chuvoso. Então precisamos saber o melhor caminho até sexta-feira e, então, multiplicar com probabilidades de emissão que levam a um sentimento de mau-humor. Iterativamente, precisamos descobrir o melhor caminho em cada dia terminando em mais probabilidade da série de dias.

Fig.14. Iterar o algoritmo para escolher o melhor caminho — Imagem do autor

O algoritmo deixa você com valores de máxima verossimilhança e agora podemos produzir a sequência com máxima verossimilhança para uma determinada sequência de saída.

5. Aprenda os valores dos parâmetros A e B dos HMMs

O aprendizado em HMMs envolve estimar as probabilidades de transição de estado A e as probabilidades de emissão de saída B que tornam uma sequência observada mais provável. Algoritmos de Expectativa-Maximização são usados para esse propósito. Um algoritmo conhecido como algoritmo Baum-Welch se enquadra nessa categoria e usa o algoritmo forward. Ele é comumente usado.

Este artigo descreve de forma abrangente os modelos de Markov e Markov oculto. Sua principal intenção foi fornecer uma explicação com um exemplo para encontrar a probabilidade de uma dada sequência e máxima verossimilhança para HMM, que é frequentemente questionável em exames também.

Conclusão

Os Modelos Ocultos de Markov (HMMs) oferecem uma poderosa abordagem para lidar com problemas onde os estados subjacentes de um sistema não são diretamente observáveis, mas suas consequências ou observações são evidentes. Essa estrutura probabilística é particularmente valiosa em áreas como processamento de linguagem natural, reconhecimento de fala, e bioinformática, onde compreender a sequência e a dependência dos estados ocultos é essencial para prever e interpretar os dados observados.

Os processos estocásticos proporcionam uma base para a modelagem de fenômenos complexos ao associar variáveis aleatórias a um conjunto de estados. Ao introduzir conceitos como probabilidades de emissão e probabilidades de transição, os HMMs permitem a modelagem detalhada de sistemas onde os estados de um processo influenciam as observações ao longo do tempo. A capacidade de modelar a sequência de estados ocultos e suas probabilidades associadas permite uma análise mais profunda e uma compreensão aprimorada dos processos subjacentes que afetam os dados observados.

A probabilidade de sequência observada é um dos aspectos centrais dos HMMs, fornecendo uma métrica para a confiabilidade de uma determinada sequência de estados. Os procedimentos de avanço e retrocesso são técnicas críticas para calcular essa probabilidade de maneira eficiente, considerando todas as possíveis configurações dos estados ocultos. Esses algoritmos ajudam a superar a complexidade computacional inerente à tarefa, oferecendo uma maneira prática de lidar com grandes volumes de dados e modelar sistemas dinâmicos.

No entanto, a implementação de HMMs não está isenta de desafios. A complexidade dos modelos estocásticos e a necessidade de ajustar os parâmetros de forma adequada requerem uma compreensão detalhada das técnicas de inferência e dos algoritmos envolvidos. A precisão das probabilidades de emissão e transição é crucial para garantir a eficácia do modelo, e a capacidade de identificar e ajustar esses parâmetros pode determinar o sucesso de aplicações práticas.

A governança e a supervisão das aplicações de HMMs também são importantes para assegurar que os modelos sejam utilizados de maneira ética e responsável. Com o avanço contínuo da tecnologia e a crescente capacidade de processamento, a aplicação de HMMs em contextos diversos continuará a expandir, trazendo novas oportunidades e desafios. O entendimento dos princípios fundamentais dos HMMs e das técnicas associadas é essencial para profissionais e pesquisadores que buscam explorar e aplicar essas ferramentas em suas áreas de atuação.

Portanto, os Modelos Ocultos de Markov oferecem uma abordagem robusta para a modelagem de sistemas complexos com estados não observáveis. A combinação de algoritmos de inferência, modelagem probabilística e técnicas de ajuste de parâmetros permite uma análise detalhada e precisa dos processos subjacentes. À medida que avançamos na aplicação e no desenvolvimento dessas técnicas, é vital continuar a explorar e refinar nossas abordagens para maximizar o potencial dos HMMs e enfrentar os desafios emergentes.