Modelo de Markov Oculto - Hidden Markov model

O modelo de Markov oculto ( HMM ) é um modelo de Markov estatístico no qual o sistema que está sendo modelado se comporta como um processo de Markov com estados não observáveis ​​(" ocultos "). Como parte da definição, o HMM assume que existe um processo observável cujo comportamento é "influenciado" por uma forma conhecida. O objetivo é aprender observando . O HMM exige que, em cada instância de tempo, o resultado de deve ser "influenciado" exclusivamente pelo resultado de e que as histórias e resultados anteriores não devem ter relação com o resultado de

Os modelos ocultos de Markov são conhecidos por suas aplicações em termodinâmica , mecânica estatística , física , química , economia , finanças , processamento de sinais , teoria da informação , reconhecimento de padrões - como fala , caligrafia , reconhecimento de gestos , marcação de parte da fala , acompanhamento de partituras musicais , descargas parciais e bioinformática .

Definição

Deixe e seja processos estocásticos em tempo discreto e . O par é um modelo de Markov oculto se

  • é um processo de Markov cujo comportamento não é diretamente observável ("oculto");
para todo e qualquer conjunto do Borel .

Deixe e seja processos estocásticos de tempo contínuo. O par é um modelo de Markov oculto se

  • é um processo de Markov cujo comportamento não é diretamente observável ("oculto");
  • ,
para cada conjunto do Borel e cada família de conjuntos do Borel

Terminologia

Os estados do processo (resp. São chamados de estados ocultos e (resp. É chamada de probabilidade de emissão ou probabilidade de saída) .

Exemplos

Tirando bolas de urnas escondidas

Figura 1. Parâmetros probabilísticos de um modelo oculto de Markov (exemplo)
X - estados
y - observações possíveis
a - probabilidades de transição de estado
b - probabilidades de saída

Em sua forma discreta, um processo de Markov oculto pode ser visualizado como uma generalização do problema da urna com a substituição (onde cada item da urna é devolvido à urna original antes da próxima etapa). Considere este exemplo: em uma sala que não é visível para um observador, há um gênio. A sala contém urnas X1, X2, X3, ... cada uma das quais contém uma mistura conhecida de bolas, cada bola marcada como y1, y2, y3, .... O gênio escolhe uma urna naquela sala e tira aleatoriamente uma bola dessa urna. Em seguida, coloca a bola em uma esteira rolante, onde o observador pode observar a sequência das bolas, mas não a sequência de urnas das quais foram retiradas. O gênio tem algum procedimento para escolher urnas; a escolha da urna para a n- ésima bola depende apenas de um número aleatório e da escolha da urna para a ( n  - 1) -ésima bola. A escolha da urna não depende diretamente das urnas escolhidas antes desta única urna anterior; portanto, isso é chamado de processo de Markov . Ele pode ser descrito pela parte superior da Figura 1.

O processo de Markov em si não pode ser observado, apenas a sequência de bolas rotuladas, portanto, esse arranjo é chamado de "processo de Markov oculto". Isso é ilustrado pela parte inferior do diagrama mostrado na Figura 1, onde se pode ver que as bolas y1, y2, y3, y4 podem ser desenhadas em cada estado. Mesmo que o observador conheça a composição das urnas e tenha acabado de observar uma sequência de três bolas, por exemplo , y1, y2 e y3 na esteira rolante, o observador ainda não pode ter certeza de qual urna ( ou seja , em que estado) o gênio desenhou a terceira bola de. No entanto, o observador pode calcular outras informações, como a probabilidade de a terceira bola ter saído de cada uma das urnas.

Jogo de adivinhação do tempo

Considere dois amigos, Alice e Bob, que moram longe um do outro e conversam diariamente ao telefone sobre o que fizeram naquele dia. Bob está interessado apenas em três atividades: caminhar no parque, fazer compras e limpar seu apartamento. A escolha do que fazer é determinada exclusivamente pelo clima de um determinado dia. Alice não tem informações definitivas sobre o tempo, mas conhece as tendências gerais. Com base no que Bob diz a ela que fazia todos os dias, Alice tenta adivinhar como deve ter sido o tempo.

Alice acredita que o clima opera como uma cadeia de Markov discreta . Existem dois estados, "Rainy" e "Sunny", mas ela não pode observá-los diretamente, ou seja, eles estão escondidos dela. Em cada dia, há uma certa chance de Bob realizar uma das seguintes atividades, dependendo do clima: "caminhar", "fazer compras" ou "limpar". Já que Bob conta a Alice sobre suas atividades, essas são as observações . Todo o sistema é um modelo oculto de Markov (HMM).

Alice conhece as tendências gerais do clima na área 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 em 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_probabilityrepresenta a crença de Alice sobre em que estado o HMM se encontra quando Bob a liga pela primeira vez (tudo que ela sabe é que tende a chover em média). 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}. O transition_probabilityrepresenta a mudança do clima na cadeia de Markov subjacente. Neste exemplo, há apenas 30% de chance de amanhã estar ensolarado se hoje estiver chuvoso. O emission_probabilityrepresenta a probabilidade de Bob realizar determinada atividade a cada dia. Se estiver chovendo, há 50% de chance de que ele esteja limpando seu apartamento; se estiver ensolarado, há 60% de chance de ele sair para uma caminhada.

Representação gráfica do HMM fornecido

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

Arquitetura estrutural

O diagrama abaixo mostra a arquitetura geral de um HMM instanciado. Cada forma oval representa uma variável aleatória que pode adotar qualquer um de vários valores. A variável aleatória x ( t ) é o estado oculto no tempo t (com o modelo do diagrama acima, x ( t ) ∈ {  x 1x 2x 3  }). A variável aleatória y ( t ) é a observação no tempo t (com y ( t ) ∈ {  y 1y 2y 3y 4  }). As setas no diagrama (geralmente chamadas de diagrama de treliça ) denotam dependências condicionais.

A partir do diagrama, fica claro que a distribuição de probabilidade condicional da variável oculta x ( t ) no tempo t , dados os valores da variável oculta x em todos os momentos, depende apenas do valor da variável oculta x ( t  - 1 ); os valores no tempo t  - 2 e antes não têm influência. Isso é chamado de propriedade Markov . Da mesma forma, o valor da variável observada y ( t ) depende apenas do valor da variável oculta x ( t ) (ambos no tempo t ).

No tipo padrão de modelo oculto de Markov considerado aqui, o espaço de estado das variáveis ​​ocultas é discreto, enquanto as próprias observações podem ser discretas (normalmente geradas a partir de uma distribuição categórica ) ou contínuas (tipicamente a partir de uma distribuição gaussiana ). Os parâmetros de um modelo oculto de Markov são de dois tipos, probabilidades de transição e probabilidades de emissão (também conhecidas como probabilidades de saída ). As probabilidades de transição controlam a maneira como o estado oculto no momento t é escolhido, dado o estado oculto no momento .

Presume-se que o espaço de estado oculto consiste em um de N valores possíveis, modelados como uma distribuição categórica. (Consulte a seção abaixo sobre extensões para outras possibilidades.) Isso significa que para cada um dos N possíveis estados em que uma variável oculta no tempo t pode estar, há uma probabilidade de transição deste estado para cada um dos N possíveis estados do variável oculta no tempo , para um total de probabilidades de transição. Observe que o conjunto de probabilidades de transição para transições de qualquer estado deve somar 1. Portanto, a matriz de probabilidades de transição é uma matriz de Markov . Como qualquer probabilidade de transição pode ser determinada uma vez que as outras sejam conhecidas, há um total de parâmetros de transição.

Além disso, para cada um dos N estados possíveis, existe um conjunto de probabilidades de emissão governando a distribuição da variável observada em um determinado momento, dado o estado da variável oculta naquele momento. O tamanho deste conjunto depende da natureza da variável observada. Por exemplo, se a variável observada é discreta com M valores possíveis, governados por uma distribuição categórica , haverá parâmetros separados, para um total de parâmetros de emissão sobre todos os estados ocultos. Por outro lado, se a variável observada é um vetor M- dimensional distribuído de acordo com uma distribuição Gaussiana multivariada arbitrária , haverá parâmetros M controlando as médias e parâmetros controlando a matriz de covariância , para um total de parâmetros de emissão. (Nesse caso, a menos que o valor de M seja pequeno, pode ser mais prático restringir a natureza das covariâncias entre os elementos individuais do vetor de observação, por exemplo, assumindo que os elementos são independentes uns dos outros, ou menos restritivamente, são independentes de todos, exceto de um número fixo de elementos adjacentes.)

Evolução temporal de um modelo oculto de Markov

Inferência

A transição de estado e as probabilidades de saída de um HMM são indicadas pela opacidade da linha na parte superior do diagrama. Dado que observamos a sequência de saída na parte inferior do diagrama, podemos estar interessados ​​na sequência de estados mais provável que poderia tê-la produzido. Com base nas setas que estão presentes no diagrama, as seguintes sequências de estados são candidatas:
5 3 2 5 3 2
4 3 2 5 3 2
3 1 2 5 3 2
Podemos encontrar a sequência mais provável avaliando a probabilidade conjunta de ambos a sequência de estados e as observações para cada caso (simplesmente multiplicando os valores de probabilidade, que aqui correspondem às opacidades das setas envolvidas). Em geral, este tipo de problema (ou seja, encontrar a explicação mais provável para uma sequência de observação) pode ser resolvido de forma eficiente usando o algoritmo de Viterbi .

Vários problemas de inferência estão associados a modelos de Markov ocultos, conforme descrito a seguir.

Probabilidade de uma sequência observada

A tarefa é calcular da melhor maneira, dados os parâmetros do modelo, a probabilidade de uma determinada sequência de saída. Isso requer a soma de todas as sequências de estado possíveis:

A probabilidade de observar uma sequência

de comprimento L é dado por

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

Aplicando o princípio da programação dinâmica , esse problema também pode ser tratado com eficiência usando o algoritmo de encaminhamento .

Probabilidade das variáveis ​​latentes

Uma série de tarefas relacionadas questionam sobre a probabilidade de uma ou mais das variáveis ​​latentes, dados os parâmetros do modelo e uma sequência de observações

Filtrando

A tarefa é calcular, dados os parâmetros do modelo e uma sequência de observações, a distribuição sobre os estados ocultos da última variável latente no final da sequência, ou seja, computar . Essa tarefa é normalmente usada quando a sequência de variáveis ​​latentes é pensada como os estados subjacentes pelos quais um processo se move em uma sequência de pontos no tempo, com observações correspondentes em cada ponto no tempo. Então, é natural perguntar sobre o estado do processo ao final.

Esse problema pode ser tratado de forma eficiente usando o algoritmo de encaminhamento .

Alisamento

Isso é semelhante à filtragem, mas pergunta sobre a distribuição de uma variável latente em algum lugar no meio de uma sequência, ou seja, para calcular para alguns . Da perspectiva descrita acima, isso pode ser pensado como a distribuição de probabilidade sobre estados ocultos para um ponto no tempo k no passado, em relação ao tempo t .

O algoritmo para frente e para trás é um bom método para calcular os valores suavizados para todas as variáveis ​​de estado ocultas.

Explicação mais provável

A tarefa, ao contrário das duas anteriores, pergunta sobre a probabilidade conjunta de toda a sequência de estados ocultos que gerou uma sequência particular de observações (veja a ilustração à direita). Esta tarefa é geralmente aplicável quando HMMs são aplicados a diferentes tipos de problemas daqueles para os quais as tarefas de filtragem e suavização são aplicáveis. Um exemplo é a marcação de classes gramaticais , em que os estados ocultos representam as classes gramaticais subjacentes correspondentes a uma sequência observada de palavras. Nesse caso, o que interessa é a sequência inteira de classes gramaticais, em vez de simplesmente a classe gramatical para uma única palavra, como seria calculado com filtragem ou suavização.

Esta tarefa requer encontrar um máximo sobre todas as sequências de estado possíveis e pode ser resolvida de forma eficiente pelo algoritmo de Viterbi .

Significado estatístico

Para alguns dos problemas acima, também pode ser interessante perguntar sobre a significância estatística . Qual é a probabilidade de que uma sequência retirada de alguma distribuição nula terá uma probabilidade HMM (no caso do algoritmo direto) ou uma probabilidade de sequência de estado máxima (no caso do algoritmo de Viterbi) pelo menos tão grande quanto aquela de um determinado sequência de saída? 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.

Aprendendo

A tarefa de aprendizado de parâmetros em HMMs é encontrar, dada uma sequência de saída ou um conjunto de tais sequências, o melhor conjunto de transição de estado e probabilidades de emissão. A tarefa geralmente é derivar a estimativa de máxima verossimilhança dos parâmetros do HMM dado o conjunto de sequências de saída. Nenhum algoritmo tratável é conhecido para resolver este problema exatamente, mas uma probabilidade máxima local pode ser derivada de forma eficiente usando o algoritmo Baum-Welch ou o algoritmo Baldi-Chauvin. O algoritmo Baum – Welch é um caso especial do algoritmo de maximização de expectativa .

Se os HMMs forem usados ​​para predição de séries temporais, métodos de inferência Bayesianos mais sofisticados, como a amostragem por cadeia de Markov Monte Carlo (MCMC), são comprovadamente favoráveis ​​ao encontrar um único modelo de máxima verossimilhança em termos de precisão e estabilidade. Uma vez que MCMC impõe carga computacional significativa, nos casos em que a escalabilidade computacional também é de interesse, pode-se, alternativamente, recorrer a aproximações variacionais para inferência Bayesiana, por exemplo, de fato, a inferência variacional aproximada oferece eficiência computacional comparável à maximização de expectativa, embora produzindo um perfil de precisão apenas ligeiramente inferior à inferência bayesiana exata do tipo MCMC.

Formulários

Um perfil HMM modelando um alinhamento de sequência múltipla

Os HMMs podem ser aplicados em muitos campos onde o objetivo é recuperar uma sequência de dados que não seja imediatamente observável (mas outros dados que dependem da sequência são). Os aplicativos incluem:

História

Modelos ocultos de Markov foram descritos em uma série de artigos estatísticos de Leonard E. Baum e outros autores na segunda metade da década de 1960. Uma das primeiras aplicações dos HMMs foi o reconhecimento de voz , a partir de meados da década de 1970.

Na segunda metade da década de 1980, os HMMs começaram a ser aplicados à análise de sequências biológicas, em particular de DNA . Desde então, eles se tornaram onipresentes no campo da bioinformática .

Extensões

Nos modelos de Markov ocultos considerados acima, o espaço de estado das variáveis ​​ocultas é discreto, enquanto as próprias observações podem ser discretas (normalmente geradas a partir de uma distribuição categórica ) ou contínuas (normalmente a partir de uma distribuição gaussiana ). Os modelos ocultos de Markov também podem ser generalizados para permitir espaços de estados contínuos. Exemplos de tais modelos são aqueles em que o processo de Markov sobre variáveis ​​ocultas é um sistema dinâmico linear , com uma relação linear entre as variáveis ​​relacionadas e onde todas as variáveis ​​ocultas e observadas seguem uma distribuição gaussiana . Em casos simples, como o sistema dinâmico linear que acabamos de mencionar, 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 .

Os modelos de Markov ocultos são modelos generativos , nos quais é modelada a distribuição conjunta de observações e estados ocultos ou, de forma equivalente, a distribuição anterior de estados ocultos (as probabilidades de transição ) e a distribuição condicional de observações em determinados estados (as probabilidades de emissão ). Os algoritmos acima assumem implicitamente uma distribuição anterior uniforme sobre as probabilidades de transição. No entanto, também é possível criar modelos de Markov ocultos com outros tipos de distribuições anteriores. Um candidato óbvio, dada a distribuição categórica das probabilidades de transição, é a distribuição de Dirichlet , que é a distribuição prévia conjugada da distribuição categórica. Normalmente, uma distribuição simétrica de Dirichlet é escolhida, refletindo ignorância sobre quais estados são inerentemente mais prováveis ​​do que outros. O único parâmetro desta distribuição (denominado parâmetro de concentração ) controla a densidade relativa ou dispersão da matriz de transição resultante. A 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 são provavelmente 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 desprezíveis. Também é possível usar uma distribuição de Dirichlet anterior de 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 governa a distribuição geral dos estados, determinando a probabilidade de cada estado ocorrer; seu parâmetro de concentração determina a densidade ou dispersão dos estados. Essa distribuição anterior de dois níveis, em que ambos os parâmetros de concentração são definidos para produzir distribuições esparsas, pode ser útil, por exemplo, na marcação de classes gramaticais não supervisionada , em que algumas classes gramaticais ocorrem muito mais comumente do que outras; algoritmos de aprendizagem que assumem uma distribuição anterior uniforme geralmente têm um desempenho ruim nessa tarefa. Os parâmetros de modelos desse tipo, com distribuições anteriores não uniformes, podem ser aprendidos usando a amostragem de Gibbs ou versões estendidas do algoritmo de maximização de expectativa .

Uma extensão dos modelos ocultos de Markov descritos anteriormente com antecedentes 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 descrito anteriormente com dois níveis de distribuições de Dirichlet. Esse modelo é chamado de modelo de Markov oculto do processo de Dirichlet hierárquico ou, abreviadamente , HDP-HMM . Ele foi originalmente descrito sob o nome de "Modelo de Markov Oculto Infinito" e foi posteriormente formalizado em.

Um tipo diferente de extensão usa um modelo discriminativo no lugar do modelo generativo de HMMs padrão. Este tipo de modelo modela 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 entropia máxima de Markov (MEMM), que modela a distribuição condicional dos estados por meio de regressão logística (também conhecido como " modelo de entropia máxima "). A vantagem desse tipo de modelo é que características arbitrárias (isto é, funções) das observações podem ser modeladas, permitindo que o conhecimento específico do domínio do problema em questão seja injetado no modelo. Modelos desse tipo não se limitam a modelar dependências diretas entre um estado oculto e sua observação associada; em vez disso, características de observações próximas, de combinações da observação associada e observações próximas, ou na verdade de observações arbitrárias a qualquer distância de um determinado estado oculto, podem ser incluídas no processo usado para determinar o valor de um estado oculto. Além disso, não há necessidade de que esses recursos sejam estatisticamente independentes uns dos outros, como seria o caso se tais recursos fossem usados ​​em um modelo gerador. Finalmente, recursos arbitrários sobre pares de estados ocultos adjacentes podem ser usados ​​em vez de simples probabilidades de transição. As desvantagens de tais modelos são: (1) Os tipos de distribuições anteriores que podem ser colocadas em estados ocultos são severamente limitados; (2) Não é possível prever a probabilidade de ver uma observação arbitrária. Essa segunda limitação geralmente não é um problema na prática, uma vez 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 . Isso usa um modelo gráfico não direcionado (também conhecido como campo aleatório de Markov ) em vez dos modelos gráficos direcionados de MEMMs 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 para MEMMs.

Ainda outra variante é o modelo fatorial de Markov oculto , que permite que uma única observação seja condicionada nas variáveis ​​ocultas correspondentes de um conjunto de cadeias de Markov independentes, em vez de uma única cadeia de Markov. É equivalente a um único HMM, com estados (assumindo que haja estados para cada cadeia) e, portanto, o aprendizado em tal modelo é difícil: para uma sequência de comprimento , um algoritmo de Viterbi simples tem complexidade . Para encontrar uma solução exata, um algoritmo de árvore de junção pode ser usado, mas resulta em uma complexidade. Na prática, técnicas aproximadas, como abordagens variacionais, podem ser usadas.

Todos os modelos acima podem ser estendidos para permitir dependências mais distantes entre os estados ocultos, por exemplo, permitindo que um determinado estado seja dependente dos dois ou três estados anteriores em vez de um único estado anterior; isto é, as probabilidades de transição são estendidas para abranger conjuntos de três ou quatro estados adjacentes (ou em estados adjacentes gerais ). A desvantagem de tais modelos é que os algoritmos de programação dinâmica para treiná-los têm um tempo de execução, para estados adjacentes e observações totais (isto é, uma cadeia de Markov de comprimento ).

Outra extensão recente é o modelo tripleto de Markov , no qual um processo auxiliar subjacente é adicionado para modelar algumas especificidades de dados. Muitas variantes deste modelo foram propostas. Deve-se também mencionar a interessante ligação que se estabeleceu entre a teoria da evidência e os modelos triplos de Markov e que permite fundir dados no contexto markoviano e modelar dados não estacionários. Observe que estratégias alternativas de fusão de dados em múltiplos fluxos também foram propostas na literatura recente, por exemplo

Finalmente, um raciocínio diferente para abordar o problema de modelagem de dados não estacionários por meio de modelos ocultos de Markov foi sugerido em 2012. Consiste no emprego de uma pequena rede neural recorrente (RNN), especificamente uma rede de reservatórios, para capturar a evolução da dinâmica temporal nos dados observados. Esta informação, codificada na forma de um vetor de alta dimensão, é usada como uma variável de condicionamento das probabilidades de transição de estado do HMM. Sob tal configuração, eventualmente obtemos um HMM não estacionário cujas probabilidades de transição evoluem ao longo do tempo de uma maneira que é inferida dos próprios dados, em oposição a algum modelo ad-hoc irreal de evolução temporal.

O modelo adequado no contexto de dados longitudinais é denominado modelo de Markov latente. 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 aos pressupostos do modelo e ao seu uso prático, é fornecida em

Veja também

Referências

links externos

Conceitos