Um modelo oculto de Markov (HMM, do inglês hidden Markov model) é um modelo de Markov no qual as observações são dependentes de um processo de Markov latente (ou oculto) (referido como ). Um HMM requer que haja um processo observável cujos resultados dependam dos resultados de de uma maneira conhecida. Como não pode ser observado diretamente, o objetivo é aprender sobre o estado de observando . Por definição de ser um modelo de Markov, um HMM tem um requisito adicional de que o resultado de no tempo deve ser "influenciado" exclusivamente pelo resultado de em e que os resultados de e em devem ser condicionalmente independentes de em dado no tempo . A estimativa dos parâmetros em um HMM pode ser realizada usando a estimativa de máxima verossimilhança. Para HMMs de cadeia linear, o algoritmo de Baum–Welch pode ser usado para estimar os parâmetros.

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 reconhecimento de fala, reconhecimento de caligrafia, reconhecimento de gestos,Thad Starner, Alex Pentland. Real-Time American Sign Language Visual Recognition From Video Using Hidden Markov Models. Master's Thesis, MIT, Feb 1995, Program in Media Arts etiquetagem de classes gramaticais (part-of-speech tagging), acompanhamento de partituras musicais,B. Pardo and W. Birmingham. Modeling Form for On-line Following of Musical Performances . AAAI-05 Proc., July 2005. descargas parciaisSatish L, Gururaj BI (April 2003). "Use of hidden Markov models for partial discharge pattern classification". IEEE Transactions on Dielectrics and Electrical Insulation. e bioinformática.

Definição Sejam e processos estocásticos de tempo discreto e . O par é um modelo oculto de Markov se

é um processo de Markov cujo comportamento não é diretamente observável ("oculto"); ,

para todo , , e todo conjunto de Borel .

Sejam e processos estocásticos de tempo contínuo. O par é um modelo oculto de Markov se é um processo de Markov cujo comportamento não é diretamente observável ("oculto"); ,

para todo , todo conjunto de Borel , e toda família de conjuntos de Borel .

Terminologia Os estados do processo (resp. são chamados de estados ocultos, e (resp. é chamado de probabilidade de emissão ou probabilidade de saída.

Exemplos Retirando bolas de urnas ocultas

right|thumb|300px| 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 reposição (onde cada item da urna é devolvido à urna original antes do próximo passo).

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 contendo uma mistura conhecida de bolas, com cada bola tendo um rótulo único y1, y2, y3, ... . O gênio escolhe uma urna naquela sala e sorteia aleatoriamente uma bola dela. Em seguida, coloca a bola sobre uma esteira rolante, onde o observador pode ver a sequência das bolas, mas não a sequência de urnas de onde foram retiradas.

O gênio tem um procedimento para escolher as 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 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.

Processo de Markov O processo de Markov não pode ser observado, apenas a sequência de bolas rotuladas, portanto esse arranjo é chamado de processo oculto de Markov. Isso é ilustrado pela parte inferior do diagrama mostrado na Figura 1, onde se pode ver que as bolas y1, y2, y3, y4 podem ser retiradas 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, ex. y1, y2 e y3 na esteira, o observador ainda não pode ter certeza de qual urna (ou seja, em qual estado) o gênio retirou a terceira bola. No entanto, o observador pode calcular outras informações, como a probabilidade de que a terceira bola tenha vindo 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 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.

border|center|400px|Representação gráfica do HMM fornecido

Um exemplo semelhante é melhor 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 assumir qualquer um de vários valores. A variável aleatória é o estado oculto no instante (com o modelo do diagrama acima, . A variável aleatória é a observação no tempo (com . As setas no diagrama (muitas vezes chamadas de diagrama de treliça) denotam dependências condicionais.

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

No tipo padrão de modelo oculto de Markov considerado aqui, o espaço de estados das variáveis ocultas é discreto, enquanto as próprias observações 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 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 tempo é escolhido dado o estado oculto no tempo .

Assume-se que o espaço de estados ocultos consiste em um de valores possíveis, modelados como uma distribuição categórica. (Veja a seção abaixo sobre extensões para outras possibilidades). Isso significa que, para cada um dos possíveis estados em que uma variável oculta no tempo pode estar, há uma probabilidade de transição deste estado para cada um dos possíveis estados da variável oculta no tempo , totalizando probabilidades de transição. O conjunto de probabilidades de transição partindo de qualquer estado dado deve somar . Assim, a matriz de probabilidades de transição é uma matriz estocástica. Como qualquer probabilidade de transição pode ser determinada uma vez que as outras são conhecidas, há um total de parâmetros de transição.

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

500px|center|Evolução temporal de um modelo oculto de Markov

Inferência

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

Probabilidade de uma sequência observada 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

de comprimento L é dada por

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

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

Probabilidade das variáveis latentes 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 .

Filtragem A tarefa é computar, 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 é usada quando a sequência de variáveis latentes é vista como os estados subjacentes pelos quais um processo transita em uma sequência de pontos no tempo, com observações correspondentes a cada ponto. É natural, então, perguntar qual o estado do processo no final.

Este problema pode ser tratado eficientemente usando o algoritmo forward. Um exemplo é quando o algoritmo é aplicado a uma Rede Oculta de Markov para determinar .

Suavização