Pontifı́cia Universidade Católica do Rio Grande do Sul Faculdade de Informática Pós-Graduação em Ciência da Computação Um Estudo sobre Modelos Ocultos de Markov HMM - Hidden Markov Model Luciana da Silveira Espindola Orientador: Paulo Henrique Lemelle Fernandes Introdução à Pesquisa I Porto Alegre, junho de 2009 Sumário LISTA DE FIGURAS ii Capı́tulo 1: Introdução 1 Capı́tulo 2: Cadeias de Markov 3 2.1 Definição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Modelo Markoviano do Tempo . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Capı́tulo 3: Modelos Ocultos de Markov 3.1 Definição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Capı́tulo 4: Problemas Canônicos 4.1 4.2 4.3 9 10 13 Solução do Problema 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.1.1 Algoritmo Forward-Backward . . . . . . . . . . . . . . . . . . . . . . 16 Solução do Problema 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.2.1 Algoritmo de Viterbi . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Solução do Problema 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.3.1 24 Algoritmo de Baum-Welch . . . . . . . . . . . . . . . . . . . . . . . . Capı́tulo 5: Considerações Finais 27 REFERÊNCIAS BIBLIOGRÁFICAS 28 i Lista de Figuras 3.1 Markov de 3 estados e HMM correspondente (Fonte: Jelinek [1]) . . . . . . . . 3.2 Dois estágios do trellis, correspondendo ao HMM binário da Figura 3.1 (Fonte: Jelinek [1]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 12 Trellis para a sequência de observáveis “0 1 1 0” relativa à Figura 3.1 (Fonte: Jelinek [1]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 11 15 Trellis da Figura 4.1 contemplando apenas os caminhos que geram a sequência completa de observáveis “0 1 1 0” (Fonte: Jelinek [1]) . . . . . . . . . . . . . 16 4.3 Ilustração da parte forward do algoritmo forward-backward (Fonte: Rabiner [3]) 17 4.4 Ilustração da parte backward do algoritmo forward-backward (Fonte: Rabiner [3]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.5 Trellis para a representação do algoritmo de Viterbi (Fonte: Jelinek [1]) . . . . 23 4.6 Ilustração do algoritmo forward-backward aplicado à solução do Problema 3 (Fonte: Rabiner [3]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii 25 Resumo ”Modelos Ocultos de Markov”(Hidden Markov Models - HMM) trata-se de um formalismo Markoviano usado para modelar situações nas quais a fonte geradora dos sinais observados está oculta do observador. Esse formalismo pode ser usado tanto para estudar a natureza dessa fonte quanto para ajudar a prever observações futuras. Este trabalho tem caráter introdutório, sendo o escopo do mesmo limitado a modelos discretos tanto no espaço de estados quanto no tempo. Inicialmente, é feita a fundamentação de modelos Markovianos e Cadeias de Markov, princı́pio básico para o desenvolvimento do formalismo de HMM. Em seguida, descreve-se o formalismo propriamente dito e a resolução de uma série de problemas-controle, que auxiliam na calibração do modelo. O primeiro problema calcula a probabilidade de uma sequência de observáveis através da resolução da parte forward do algoritmo forward-backward; o segundo busca identificar, pelo uso do algoritmo de Viterbi, a sequência de estados mais provável, dada a sequência observada; o último problema-controle, resolvido pelo uso do algoritmo de Baum-Welch, trata de buscar melhores parâmetros para o modelo, otimizando a probabilidade de observação de uma dada sequência. Restrições adicionais a esse tratamento incluem a forma regular e homogênea da matriz de transição, a finitude do espaço de observáveis, a independência entre observações, e o fato de que toda transição entre estados da Markov embutida emite um observável. A intenção é aprofundar esse estudo em trabalhos futuros, buscando por uma descrição mais genérica através da eliminação das restrições acima relacionadas. 1 Introdução A grande maioria dos processos envolvendo sistemas reais são tão complexos que mesmo que haja forma analı́tica de resolvê-los, muitas vezes acaba sendo mais produtivo lançar mão do uso de teoria de probabilidade. Segundo Reichl [2], para aplicar teoria de probabilidade ao mundo real, é necessário introduzir o conceito de “variável estocástica”. Assim, X é dita variável estocástica se seu valor, dentre o conjunto {xi } de possı́veis realizações, é determinado pelo resultado de um experimento. Talvez não seja possı́vel observar diretamente a dinâmica estocástica que rege um dado processo do mundo real, mas muito provavelmente esse processo produz observáveis, também chamados “sinais”, a partir dos quais o sistema pode ser modelado. Esses sinais podem ou não ser de fonte estacionária (sistema em equilı́brio), ser de natureza discreta ou contı́nua, tratar-se de sinais limpos ou ruidosos, dentre outras caracterı́sticas imagináveis. Poderı́amos encontrar vários motivos para fazer modelagens baseadas em sinais. Rabiner [3] sugere que uma modelagem desse tipo pode servir para prover descrição teórica de uma ferramenta para processamento de sinais. Um exemplo de uso seria a otimização de um sinal de audio pela remoção de ruı́do e distorções de transmissão. Modelos de sinais também podem ajudar na compreensão de sua fonte, caso não seja possı́vel observar o processo diretamente ou caso o custo dessa observação seja muito alto. Assim, a fonte pode ser simulada e muito pode-se aprender dessa simulação, [3]. São vários os modelos estocásticos baseados em sinais. Alguns exemplos são os modelos para processos Gaussianos, processos de Poisson, processos Markovianos e os modelos para processos ocultos de Markov, sobre o qual versa essa monografia. Encontramos o formalismo de Modelos Ocultos de Markov (Hidden Markov Models - HMM) sob os mais diversos nomes, dentre eles: Processos Ocultos de Markov (Hidden Markov Processes), Fontes Markovianas (Markov Sources), Cadeias de Markov Ocultas (Hidden Markov Chains), Funções Probabilı́sticas de Cadeias de Markov (Probabilistic Functions of Markov 1 Chains). O formalismo de Modelos Ocultos de Markov (HMM) é usado para modelar processos que são governados por um processo Markoviano embutido, cuja dinâmica não pode ser diretamente observada. Esse processo Markoviano evolui no tempo por meio de transições entre seus estados, as quais são responsáveis pela emissão de sinais observáveis. Todo modelo passa por uma fase de calibração, e para modelos em HMM não poderia ser diferente. Rabiner [3] aborda o assunto por meio da resolução de três problemas fundamentais, organização essa proposta por Jack Ferguson (IDA - Institute for Defense Analysis, USA). O primeiro problema consiste em, tendo a proposta de modelo em HMM, determinar a probabilidade de observação de uma determinada sequência de sinais. O segundo problema trata de descobrir qual a sequência de estados mais provável, no contexto desse modelo, que levou à sequência de sinais observados. E por fim, o terceiro problema trata da calibração propriamente dita, buscando aperfeiçoar os parâmetros do modelo, tendo em vista melhorar as probabilidades de geração, ou emissão, de sinais. Há vários tutoriais que tratam de HMM, [4], [5], [6], [7], [8], [9]. Contudo, as bases desse estudo sobre Modelos Ocultos de Markov são fundamentadas em duas fontes. Uma delas é o artigo “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition”, escrito por Lawrence Rabiner [3]. A outra fonte é o capı́tulo sobre “Hidden Markov Models”, do livro “Estatistical Methods for Speech Recognition”, de Frederick Jelinek [1]. Muitas das idéias desses autores são aqui reproduzidas, dando a essa monografia um caráter de Review. As fórmulas apresentadas no decorrer do texto são resultado de uma tentativa de unificação entre as notações usadas por esses autores. As figuras incluı́das nessa monografia também foram todas obtidas desses dois trabalhos de Jelinek [1] e Rabiner [3]. Esse estudo sobre Modelos Ocultos de Markov está organizado da forma que segue. Num primeiro momento (Cap. 2), conceituam-se Cadeias de Markov, fundamental para a compreensão e desenvolvimento de modelagens em HMM. Após, trata-se de Modelos Ocultos de Markov (Cap. 3) de forma geral, definindo as bases do formalismo. O capı́tulo seguinte (Cap. 4) aborda com detalhes a resolução dos três problemas fundamentais (ou canônicos) desse formalismo. O fechamento do trabalho trata das considerações finais desse estudo e trabalhos futuros. 2 2 Cadeias de Markov Processos Markovianos são um tipo especial de processos estocásticos que têm aplicabilidade quase universal. Exemplos de aplicações podem ser encontrados junto à quı́mica, biologia, fı́sica, informática, entre outros, provavelmente abrangendo todas as áreas do conhecimento humano. Jelinek [1], de forma muito clara e precisa, define processos estocásticos de tempo discreto sobre um espaço de estados também discreto e finito. Seja uma sequência de variáveis estocásticas X0 X1 · · · Xt · · · XT , onde 0 ≤ t ≤ T representa uma ordenação discreta no tempo, definidas para um mesmo espaço de estados discreto e finito. Se nada mais é dito, a probabilidade conjunta dessas váriáveis estocásticas é dada pela fórmula de Bayes: P (X0 X1 · · · XT ) = T Y P (Xt |X0 X1 · · · Xt−1 ) (2.1) t=0 = P (X0)P (X1 |X0 )P (X2 |X0 X1 ) · · · P (XT |X0 X1 X2 · · · XT −1 ) Um processo estocástico, tal como descrito pela equação 2.1, é dito Markoviano de grau 1 se satisfaz a seguinte propriedade: P (Xt |X0 X1 X2 · · · Xt−1 ) = P (Xt |Xt−1 ), (2.2) ou seja, dada a sequência temporal de realizações em um processo estocástico, a probabilidade desse processo evoluir para um estado qualquer do espaço de amostras no instante seguinte é dependente única e exclusivamente do estado corrente no qual o sistema se encontra. Em outras palavras, em um processo Markoviano de grau 1, a probabilidade do próximo passo, de Xt−1 para Xt , depende apenas do estado de origem desse passo, Xt−1 . Essa propriedade é conhecida como Markov property, ou “propriedade de Markov”, em tradução literal. Assim, em se tratando de processos Markovianos de grau 1, a equação 2.1 passa a ter a 3 seguinte forma: P (X0 X1 · · · XT ) = T Y P (Xt |Xt−1 ) (2.3) t=0 = P (X0 )P (X1|X0 )P (X2 |X1 )P (X3 |X2 ) · · · P (XT |XT −1 ) O fato de estarmos tratando de processos estocásticos discretos tanto no espaço de estados quanto no tempo não implica em real restrição, trata-se apenas de uma forma de simplificar os cálculos para chegar mais rapidamente à definição de Cadeias de Markov, objetivo dessa seção. Assim, se desejado for, essas equações podem ser modificadas para representar a probabilidade conjunta e probabilidade condicional (de transição) para o caso de processos em espaço e tempo contı́nuos, assim como para processos em espaço de estados discreto e tempo contı́nuo. 2.1 Definição De acordo com a grande maioria dos autores, processos Markovianos1 em espaços de estados discretos são chamados Cadeias de Markov (Markov Chains), podendo esses processos ser tanto de tempo discreto como contı́nuo. Reichl [2] restringe o termo para contemplar apenas processos Markovianos em espaços de estados discretos a tempos discretos. Independentemente de qual das definições é mais correta, optou-se aqui por tratar apenas de Cadeias de Markov de tempo discreto. Nesse trabalho, ainda são feitas restrições adicionais quanto à forma da matriz de transição. Trataremos apenas de matrizes de transição regulares e daremos preferência às homogêneas. Matriz de transição, Â, é aquela que guarda em suas células as probabilidades de transição definidas para um espaço de estados, sendo que essas probabilidades podem ou não variar com o tempo. Dizemos que essa matriz é homogênea se Â(t) = Â, ou seja, se a matriz é estacionária, tendo probabilidades de transição independentes do tempo. De acordo com Reichl [2], a matriz  será regular se todos os elementos de alguma potência ÂN , N inteiro, forem não-nulos. Cadeias de Markov governadas por matrizes de transição regulares são ditas ergódicas, isto é, todos os estados são atingı́veis através de sucessivas transições. Sistemas ergódicos tendem à estacionariedade após algum tempo, ou seja, a distribuição de probabilidade nos estados passa a ser constante. 1 Processos Markovianos são aqueles para os quais a propriedade de Markov é satisteita, ou seja, a probabilidade de um passo depende unicamente do estado atual do sistema. 4 Como lembra Trivedi [10], dizer que uma matriz de transição chegou à sua forma estacionária, ou homogênea, não é o mesmo que dizer que o sistema alcançou estacionariedade. Como vimos, a estacionariedade da matriz diz respeito às probabilidades de transição, enquanto que a estacionariedade do processo diz respeito à probabilidade conjunta das variáveis estocásticas. Sejam 1. Um espaço de estados S = {s1 , s2 , s3 , · · · , sN } 2. Uma variável estocástica X a assumir valores do espaço de estados S em diferentes instantes de tempo 3. Uma distribuição de probabilidade inicial para cada estado Π̂ = {πi }, tal que πi = P (X0 = Si ) 4. Uma distribuição de probabilidade de transição entre estados  = {aij }, tal que aij = P (Xt = sj |Xt−1 = si ) As probabilidades de transição definidas pela matriz  possuem as seguintes propriedades: aij ≥ 0 N X j=1 aij = N X P (Xt = sj |Xt−1 = si ) = 1 (2.4) (2.5) j=1 A propriedade 2.4 determina que as probabilidades de transição são todas maiores ou iguais a zero. A propriedade 2.5, por sua vez, mostra que resulta em um a soma das probabilidades de todas as transições partindo do estado si para os estados definidos no espaço de estados S. Como visto anteriormente, a equação 2.3 decorre da propriedade de Markov e, portanto, também vale para Cadeias de Markov. Considere, então, essa equação para a probabilidade conjunta das variáveis estocásticas X0 , X1 , X2 P (X0 X1 X2 ) = P (X0 )P (X1|X0 )P (X2 |X1 ). (2.6) Ao aplicarmos um somatório sobre a variável estocástica X1 , obtemos a probabilidade conjunta de X0 , X2 P (X0 X2 ) = P (X0) · X P (X1|X0 )P (X2|X1 ). (2.7) X1 Se dividirmos a equação resultante por P (X0 ), obteremos a probabilidade condicional, P (X2 |X0 ), do sistema ocupar um determinado estado no instante t = 2 sendo que ocupou algum outro estado no instante t = 0. A equação 2.8, conhecida como equação de Chapman-Kolmogorov, 5 reflete esse raciocı́nio P (X2 |X0 ) = X P (X1 |X0 )P (X2 |X1 ). (2.8) X1 A equação de Chapman-Kolmogorov evidencia a propriedade de Markov, pois a partir dela fica clara a independência entre passos sucessivos na evolução de um sistema governado por uma cadeia de Markov. Em outras palavras, a probabilidade de transição entre X1 e X2 não é afetada pelo fato de ter sido precedida pela transição entre X0 e X1 . Ou, mais sucintamente, passos sucessivos são estatisticamente independentes, [2]. Redefinindo um dos termos da equação 2.8, temos: P (X2 = sj |X1 = si ) = aij = (Â(t))ij (2.9) onde aij é um dos elementos da Matriz de Transição, Â(t). Como dito anteriormente, no decorrer desse estudo, daremos preferência ao estudo de matrizes de transição independentes do tempo, ou homogêneas: Â(t) = Â. Então, para  independente do tempo, temos: (Â)ij = aij = P (X2 = sj |X1 = si ) = P (X1 = sj |X0 = si ) = P (Xt = sj |Xt−1 = si ). (2.10) Assim, tendo uma matriz de transição homogênea, podemos ampliar a equação de ChapmanKolmogorov, 2.8, para dar conta de um número arbitrário de passos: P (Xt′ = sj | Xt = s i ) = X = P (Xτ1 |Xt = si )P (Xτ2 |Xτ1 ) · · · P (Xτn |Xτn−1 )P (Xt′ = sj |Xτn ) All6=(t||t′ ) ′ = (Ât −t )ij . (2.11) Com relação à equação 2.11, o número de termos no produto é o número de passos desde o instante t até o instante t′ . A cada par de passos, soma-se sobre todos os possı́veis estados intermediários, como feito na equação 2.8, até que a sequência de passos seja completada. Isso é equivalente a elevar a matriz de transição  à potência (t′ − t), que é justamente o número de passos, e escolher o valor guardado na célula (i,j) dessa nova matriz. Essa célula guarda a probabilidade de sair do estado si e chegar ao estado sj em (t′ − t) passos. 6 2.2 Modelo Markoviano do Tempo Em seu artigo sobre HMM e suas aplicações em reconhecimento de fala, Rabiner [3] usa um ótimo exemplo para ilustrar a aplicação de Cadeias de Markov de forma simples. O exemplo trata da modelagem do tempo no decorrer dos dias. Assim, seja a variável estocástica X, que representa o tempo e tem suas realizações definidas no conjunto discreto {S1 = chuvoso, S2 = nublado, S3 = ensolarado}. Determina-se que as observações são feitas uma vez ao dia, que o resultado obtido será sempre um único desses três estados possı́veis, sem combinação entre estados, e que as probabilidades de transição entre esses estados são dadas pela matriz a a a 11 12 13  = {aij } = a21 a22 a23 a31 a32 a33 0.4 0.3 0.3 = 0.2 0.6 0.2 0.1 0.1 0.8 Dado que o tempo no dia 1 é “ensolarado” (X0 = S3 ), qual a probabilidade (de acordo com o modelo) de que o tempo para os próximos 7 dias seja “ensolarado-ensolarado-chuvoso-chuvosoensolarado-nublado-ensolarado”? Mais formalmente, definimos a sequência de observação O = {X0 = S3 , X1 = S3 , X2 = S3 , X3 = S1 , X4 = S1 , X5 = S3 , X6 = S2 , X7 = S3 }. Queremos obter a probabilidade de O, dado o modelo: P (O|Model) = P (S3, S3 , S3 , S1 , S1 , S3 , S2 , S3 |Model) = P (S3)P (S3 |S3 )P (S3 |S3 )P (S1 |S3 )P (S1 |S1 )P (S3|S1 )P (S2|S3 )P (S3 |S2 ) = π3 · a33 · a33 · a31 · a11 · a13 · a32 · a23 = 1 · (0.8)(0.8)(0.1)(0.4)(0.3)(0.1)(0.2) = 1.536 × 10−4 onde a notação πi = P (X0 = Si ), 1 ≤ i ≤ N (2.12) é usada para indicar a probabilidade inicial de cada estado. Outra questão de interesse é: dado que o modelo está em um estado conhecido, qual a probabilidade dele permanecer nesse estado por exatamente d dias? Essa probabilidade pode ser 7 avaliada como sendo a probabilidade da sequência de observação O = {Si , Si , Si , · · · , Si , Sj 6= Si } 1 2 3 d d+1 dado o modelo, a qual é P (O|Model, X0 = Si ) = (aii )d−1 (1 − aii ) = pi (d). (2.13) A quantidade pi (d) é a densidade de probabilidade de duração d no estado i. Essa duração exponencial é caracterı́stica do tempo de permanência em um estado numa Cadeia de Markov. A partir de pi (d) podemos calcular o número médio de observações subseqüentes em um dado estado, condicionado ao fato desse ter sido o estado inicial di = = ∞ X d=1 ∞ X d(pi (d)) (2.14) d((aii )d−1 (1 − aii )) = d=1 1 . 1 − aii (2.15) Assim, de acordo com o modelo, o número esperado de dias ensolarados consecutivos é 1/(0.2) = 5 (o atual, mais 4 dias de sol), de dias nublados é 2.5 e de dias chuvosos é 1.67. 8 3 Modelos Ocultos de Markov No final da década de 1960, Leonard E. Baum e colaboradores publicaram uma série de artigos lançando as bases para o formalismo de Modelos Ocultos de Markov (Hidden Markov Models - HMM)1 . As primeira aplicações dessa modelagem estavam voltadas para o reconhecimento de fala, sendo os trabalhos de F. Jelinek (IBM) e J. K. Baker (Carnegie Mellon University - CMU), no começo dos anos 70, pioneiros no uso de HMM. Na segunda metade da década de 80, HMM foi aplicado em seqüenciamento de DNA, alcançando posteriormente grande importância em todo o campo da bioinformática. Nas palavras de Rabiner [3], na maioria dos processos Markovianos, cada estado corresponde a um observável2 do sistema. Para esclarecer a idéia, consideremos o exemplo sobre modelagem do tempo, introduzido no capı́tulo 2, sobre Cadeias de Markov. Ao verificar a condição do tempo em um determinado dia, o observador obterá diretamente um dos estados da Markov como resposta, {S1 = chuvoso, S2 = nublado, S3 = ensolarado}. Por outro lado, Modelos Ocultos de Markov são usados na modelagem de processos Markovianos que geram observáveis de forma indireta, em função das transições entre os estados da cadeia de Markov que governa o processo, mas que não pode ser diretamente observada. Em outras palavras, a evolução da cadeia de Markov está escondida do observador. Em comparação à proposta anterior de modelagem do tempo por Cadeias de Markov, uma possı́vel modelagem em HMM poderia tratar da observação do comportamento de um trabalhador em sua forma de transporte ao trabalho. Esse trabalhador se locomove de bicicleta ou taxi em função do tempo ou de sua previsão. Geralmente vai ao trabalho de bicicleta, mas costuma pegar taxi em dias chuvosos. Assim, se esse trabalhador foi trabalhar de bicicleta em um determinado dia, há uma probabilidade maior de que o dia esteja ensolarado do que chuvoso, mas ainda assim pode se 1 Hidden Markov Models aparece na literatura sob diversos nomes, tais como Hidden Markov Processes, Mar- kov Sources, Hidden Markov Chains, Probabilistic Functions of Markov Chains. 2 Observável, no contexto desse trabalho, é algo que pode ser observado. Para ilustrar, ao jogar uma moeda para cima, obteremos como resultado da observação um dos dois possı́veis observáveis: cara ou coroa. 9 tratar de um dia de chuva. Assim, a diferença fundamental entre HMM e o resto dos formalismos Markovianos está na forma de se observar o sistema. Enquanto que na maioria dos processos Markovianos a observação é direta, pois os observáveis são os próprios estados, em HMM a observação é indireta, feita por inferência, pois os observáveis são funções probabilı́sticas dos estados da Markov ou das transições entre esses estados. 3.1 Definição No contexto desse trabalho, Modelos Ocultos de Markov são definidos como modelos Markovianos onde a observação da evolução do sistema se dá de forma indireta, como função probabilı́stica da transição entre os estados definidos num espaço de estados discreto e finito. Por mais que conheçamos todos os parâmetros do modelo3 , continua oculta a evolução da Markov que governa esse processo. Em outras palavras, não se sabe qual o caminho ou sequência de passos exatos que levaram a uma determinada observação. Sejam 1. Um espaço de estados S = {s1 , s2 , s3 , · · · , sN } 2. Um conjunto de observáveis Y = {y1 , y2 , y3, · · · , yM } 3. Uma variável estocástica Q a assumir valores do espaço de estados S em diferentes instantes de tempo 4. Uma variável estocástica O a assumir valores do conjunto de observáveis Y em diferentes instantes de tempo 5. Uma distribuição de probabilidade inicial para cada estado Π = {πi }, tal que πi = P (q0 = si ) 6. Uma distribuição de probabilidade de transição entre estados  = {aij }, tal que aij = P (qt = sj |qt−1 = si ) 7. Uma distribuição de probabilidade de observação B̂ = {bij (k)}, tal que bij (k) = P (Ot = yk |qt−1 = si , qt = sj ) associada a transições do estado si para o estado sj 3 São chamados parâmetros do modelo o conjunto de valores λ = (Â, B̂, Π) que definem o modelo, onde Π é o vetor de probabilidade inicial de cada estado da Markov oculta,  é a matriz que define as probabilidades de transição entre esses estados e B̂ é a matriz de probabilidade de emissão de observáveis. 10 Jelinek [1] cita três possı́veis definições para o formalismo de Modelos Ocultos de Markov. A primeira delas, adotada pelo próprio autor, trata dos observáveis como função das transições entre os estados da Markov oculta. Outra definição, adotada por Rabiner [3], trata dos observáveis como função dos próprios estados da Markov. A terceira definição, muito usada em modelos acústicos, remove a restrição quanto à finitude de Y. Em se tratando de mais uma variante de processos Markovianos, onde trabalhamos com uma cadeia de Markov que está escondida do observador, todas as equações que valem para Cadeias de Markov também valem para Modelos Ocultos de Markov. Como observado por Jelinek [1], se o espaço de estados da Markov não for muito grande, podemos usar autômatos para analisar graficamente as relações entre os estados, suas transições e os observáveis gerados. (a) Cadeia de Markov de 3 estados (b) HMM de 3 estados e observáveis (c) HMM e observáveis para cada y ∈ {0, 1} transição Figura 3.1. Markov de 3 estados e HMM correspondente (Fonte: Jelinek [1]) Suponha, então, a Cadeia de Markov de três estados mostrada na Figura 3.1. Algumas transições não são mostradas em (a), significando que a21 = a22 = a33 = 0. A HMM correspondente, de três estados e observáveis y ∈ {0, 1}, pode ser vista em (b). Em (c) temos a representação da HMM evidenciando os observáveis gerados em função da ocorrência de transições entre os estados da Markov que governa o processo. Seguindo na abordagem adotada por Jelinek [1] no estudo de Modelos Ocultos de Markov (HMM), além de autômatos, usaremos outro artifı́cio gráfico para nos ajudar na compreensão de HMM. Esse artifı́cio é conhecido como trellis4. Ele auxilia no cálculo da probabilidade de uma sequência de observáveis P (y1 y2 · · · yk ), colocando em evidência a evolução temporal do processo gerador dessa sequência. O trellis consiste na concatenação de estágios elementares 4 Trellis, do inglês, significa “treliça”, um gradeado para plantas trepadeiras. No contexto desse trabalho, trellis é um artifı́cio gráfico para entender a dinâmica de transições entre os estados da Markov, de momento a momento. Apesar da existência de uma tradução para o português, no decorrer do texto, opta-se pelo uso do termo em inglês. 11 atribuı́dos, um a um, a cada observável. Esses “estágios”, ilustrados na Figura 3.2 mostram as transições entre os estados da Markov que poderiam gerar aquele observável especı́fico. Figura 3.2. Dois estágios do trellis, correspondendo ao HMM binário da Figura 3.1 (Fonte: Jelinek [1]) Voltaremos ao trellis várias vezes no decorrer desse estudo, como forma de ilustrar os problemas canônicos de HMM, abordados no capı́tulo 4, cujas resoluções são fundamentais na calibração de modelos criados com base no formalismo de Modelos Ocultos de Markov. 12 4 Problemas Canônicos Por definição [11], a modelagem de um sitema fı́sico ou realidade qualquer é uma versão bastante simplificada da realidade propriamente dita. Dessa forma, não há modelo absoluto, existem apenas modelos mais ou menos adequados para uma dado sistema. Tendo isso em mente, poderı́amos tratar o processo de modelagem como sendo composto de duas etapas: a definição dos parâmetros do modelo e o ajuste do mesmo pela resolução de uma série de “problemas-controle”. No contexto de modelagens em HMM, há três problemas fundamentais (ou canônicos) a serem resolvidos antes de fazer uso de um modelo, [3] 1 . Esses problemas, responsáveis pelo ajuste fino de um modelo, são os seguintes: Problema 1: Probabilidade de uma Sequência de Observáveis Sejam o modelo λ = (Â, B̂, π) e a sequência de observáveis O = O1 O2 · · · OT . Como calcular de forma eficiente a probabilidade dessa sequência ser gerada pelo modelo, P (O|λ)? Problema 2: Sequência Ótima de Estados Sejam o modelo λ = (Â, B̂, π) e a sequência de observáveis O = O1 O2 · · · OT . Dentre as diversas sequências de estados que poderiam ter gerado essa sequência de observáveis, qual é a mais provável? Problema 3: Maximização da Probabilidade de uma Sequência de Observáveis Como ajustamos os parâmetros λ = (Â, B̂, π) do modelo para maximizar P (O|λ)? 1 Rabiner [3] fundamenta essa abordagem nas idéias apresentadas por Jack Ferguson, do IDA, em apresentações nos Laboratórios Bell. 13 4.1 Solução do Problema 1 Sejam os parâmetros do modelo e a sequência de observáveis λ = (Â, B̂, π); (4.1) O = O1 O2 · · · OT . (4.2) Queremos calcular P (O|λ), a problabilidade de gerar a sequência O a partir desse modelo. A maneira mais direta de realizar esse cálculo parte da identificação de cada sequência de estados Q que possa gerar O. Usando o jargão da área, essa seria a resolução à “força bruta” e, por consequência, tende a ser onerosa, pois dispende mais tempo e poder computacional. Veremos adiante um algoritmo mais eficiente, mas por ora vamos nos deter à análise dessa resolução “mais direta”. Para simplificar os cálculos, consideramos que cada transição entre estados qt−1 e qt gera um observável Ot . Uma simplificação adicional é feita ao considerar que, além de ser ergódico, o sistema tem a caracterı́stica especial de que aqt−1 qt > 0, ∀ t, ou seja, transições estão previstas entre quaisquer pares de estados do modelo. Dadas essas considerações, suponha que O tenha sido gerado pela seguinte sequência de estados Q = q0 q1 · · · qT , (4.3) na qual o ı́ndice numérico é um inteiro, 0 ≤ t ≤ T , que indica um instante no tempo. Assim, q0 significa o estado da Markov no instante t = 0, ou simplesmente o estado inicial. A probabilidade de Q é dada por P (Q|λ) = πq0 aq0 q1 aq1 q2 · · · aqT −1 qT (4.4) Assumindo que as observações são estatisticamente independentes entre si2 , podemos escrever P (O|Q, λ) = T Y P (Ot |qt−1 , qt , λ) (4.5) t=1 de onde segue que P (O|Q, λ) = bq0 q1 (O1 ) · bq1 q2 (O2 ) · · · bqT −1 qT (OT ). 2 (4.6) A rigor, HMM não restringe quanto à natureza da relação entre os observáveis em uma sequência, podendo as observações ser ou não estatisticamente independentes, [1]. 14 Dessas equações, podemos escrever a probabilidade conjunta de O e Q P (O, Q|λ) = P (O|Q, λ) P (Q|λ) (4.7) Fazendo o somatório de 4.7 sobre todas as sequências de estados Q = q0 q1 · · · qT , tem-se P (O|λ) = X P (O|Q, λ) P (Q|λ) = allQ = X X allQ πq0 T Y aq(t−1) qt bq(t−1) qt (Ot ) (4.8) t=1 πq0 aq0 q1 bq0 q1 (O1 ) aq1 q2 bq1 q2 (O2 ) · · · aq(T −1) qT bq(T −1) qT (OT ) (4.9) q0 q1 q2 ··· qT Para entender o significado dessa equação, considere uma única sequência de estados Q. A probalididade da Markov ocupar um dos N possı́veis estados no instante t = 0 é dada por πq0 . Em t = 1, o sistema sofre transição do estado q0 para o estado q1 , gerando o observável O1 , de acordo com as propabilidades de transição e de observação, aq0 q1 e bq0 q1 (O1 ), respectivamente. Esse procedimento se repete até t = T . Tendo calculado a probabilidade para uma dada sequência Q, passa-se à próxima, dentre as sequências restantes. A soma sobre todas as sequências resulta na probalididade do modelo gerar a sequência O de observáveis. O ı́ndice numérico 0 ≤ t ≤ T também pode ser visto como uma coluna do trellis, onde q0 é o estado da Markov na coluna 0 do trellis, q1 é o estado da Markov na coluna 1, e assim por diante. Na transição entre duas colunas do trellis, um observável é emitido. Essa dinâmica é mostrada nas Figuras 4.1 e 4.2 para a sequência de observação {0 1 1 0}, referente ao exemplo apresentado em capı́tulo anterior para o caso de uma Markov de 3 estados, gerando observáveis y ∈ {0, 1} (ver Figura 3.1 para mais detalhes). Figura 4.1. Trellis para a sequência de observáveis “0 1 1 0” relativa à Figura 3.1 (Fonte: Jelinek [1]) 15 Figura 4.2. Trellis da Figura 4.1 contemplando apenas os caminhos que geram a sequência completa de observáveis “0 1 1 0” (Fonte: Jelinek [1]) Da equação 4.9, observamos que existem N T sequências Q de T posições feitas a partir de N estados. Assim, há N T termos no somatório dessa equação, o que implica em N T − 1 adições. Também existem T operações de multiplicação entre os termos aqt−1 qt · bqt−1 qt (Ot ), sendo que 1 ≤ t ≤ T , e são T − 1 as multiplicações entre esse conjunto de termos e seus correlatos, desde aq0 q1 · bq0 q1 (O1 ) até aqT −1 qT · bqT −1 qT (OT ). Assim, são (2T − 1) multiplicações em cada termo do somatório, totalizando (2T − 1) · N T multiplicações. Portanto, a resolução da equação 4.9 envolve um total de 2T N T − 1 operações. Esse cálculo talvez não seja computacionalmente impossı́vel, mas certamente é muitı́ssimo oneroso. Como exemplo, considere um sistema com N = 5 estados e uma sequência de T = 100 observáveis. Para esse exemplo, a resolução de 4.9 envolve 2 · 100 · 5100 ≈ 1072 operações. Contudo, como frisa Rabiner [3], existe um procedimento muito mais eficiente para resolver o Problema 1. Esse algoritmo é conhecido como forward-backward procedure, do qual precisamos apenas da parte “forward”, por enquanto3 . 4.1.1 Algoritmo Forward-Backward Considere a variável forward, definida como αt (i) = P (O1 O2 · · · Ot , qt = Si |λ) (4.10) isto é, a probabilidade da observação parcial da sequência de observáveis, de O1 até Ot , conjunta com a probabilidade de ocupação do estado Si da Markov no instante t. Como estamos 3 O algoritmo completo será usado na resolução do Problema 3. 16 trabalhando com sequências em função do tempo, podemos dizer que trabalhamos com conjuntos ordenados de eventos, o que nos permite assumir, por indução, que αt (i) vale para qualquer instante de tempo dentro dos limites do problema, 0 ≤ t ≤ T . Assim, resolvemos o Problema 1 pela aplicação do seguinte procedimento: 1. Inicialização: α0 (i) = πi , 1≤i≤N (4.11) 2. Indução: αt+1 (j) = N X αt (i)aij bij (Ot+1 ), 0≤t≤T −1 (4.12) i=1 1≤j≤N 3. Finalização: P (O|λ) = N X αT (i) (4.13) i=1 A figura 4.3 ilustra a situação. Figura 4.3. Ilustração da parte forward do algoritmo forward-backward (Fonte: Rabiner [3]) A “Indução” é a parte mais importante desse procedimento, então vamos tentar compreendêla. O termo αt (i) é a probabilidade conjunta da • observação parcial O = O1 O2 · · · Ot ; • ocupação do estado qt = Si . Ao multiplicar aij e por bij (Ot+1 ) estamos calculando a probabilidade conjunta de 17 • transição do estado qt = Si para o estado qt+1 = Sj ; • emissão do observável Ot+1 em consequência da transição aij . Multiplicando, então, os termos αt (i), aij e bij (Ot+1 ), e somando sobre todos os estados 1 ≤ i ≤ N, obtemos a probabilidade conjunta de • observação parcial O = O1 O2 · · · Ot ; • ocupação do estado qt+1 = Sj , qualquer que tenha sido o estado no instante anterior; • emissão do observável Ot+1 em consequência de todas as transições com destino a qt+1 = Sj ; que nada mais é do que a o valor de αt+1 (j) (equação 4.12). Para finalizar o procedimento, faz-se o somatório de αT (i) sobre todos os estados 1 ≤ i ≤ N. Isso faz todo o sentido quando analisamos a definição da variável forward por ocasião do último instante de observação T : αT (i) = P (O1 O2 · · · OT , qT = Si |λ) (4.14) Essa equação nada mais é do que a probabilidade conjunta da sequência completa de observação com a probabilidade de ocupar o estado Si no instante T . Dessa forma, ao somarmos a equação 4.14 sobre todos os estados, obtemos a probabilidade de que um dado modelo λ = (Â, B̂, π) gere a sequência de observáveis O = O1 O2 · · · OT , ou seja, obtemos 4.13. O procedimento inteiro, até a obtenção da equação 4.13, envolve 2N 2 T multiplicações e (N − 1)NT adições, totalizando (3N − 1)NT operações4 . Nesse momento, cabe comparar a eficiência desse procedimento com relação ao anterior. Para tal, usamos o mesmo exemplo, com espaço de estados N = 5 e uma sequência de T = 100 observáveis. Enquanto que o método de resolução por “força bruta” envolve aproximadamente 1072 operações, a parte forward do procedimento forward-backward precisa de 7000 operações, uma diferença de 1069 ordens de grandeza. Com esse exemplo, não há o que discutir sobre a superioridade do forward-backward nas resolução do Problema 1. 4 No procedimento original, encontrado no artigo [3], de Rabiner, a parte “Indutiva” é dada pela equação i hP N 2 αt+1 (j) = α (i)a ij bj (Ot+1 ), o que resulta (N + 1)N T multiplicações, dando um total de 2N T i=1 t operações. Assim, para N = 5 e T = 100, seriam 5000 operações quando o observável é gerado em função do estado, contra as 7000 operações quando o observável é gerado em função da transição entre estados. 18 Considere agora a variável backward, definida como βt (i) = P (Ot+1 Ot+2 · · · OT |qt = Si , λ), (4.15) ou seja, a probabilidade conjunta de a Markov estar no estado Si no instante t com a probabilidade da observação parcial, Ot+1 Ot+2 · · · OT , nos instantes subseqüentes a t. A parte backward do procedimento forward-backward é muito semelhante ao que acabamos de ver para a parte forward. Logo, por analogia, segue: 1. Inicialização: βT (i) = 1, 1≤i≤N (4.16) 2. Indução: βt (i) = N X aij bij (Ot+1 )βt+1 (j), (4.17) j=1 t = T − 1, T − 2, · · · , 0 1≤i≤N Rabiner [3] não apresenta uma finalização para esse procedimento, contudo, se assumirmos que o modelo tem um determinado estado inicial, Si , com probabilidade P (Si) = 1, podemos dizer que o que buscamos calcular é justamente β0 , que é a probabilidade da sequência completa de observação, dado que o estado inicial foi q0 = Si : β0 (i) = P (O1 O2 · · · OT |q0 = Si , λ) (4.18) A figura 4.4 ilustra a situação. De acordo com Jelinek [1], a inicialização apresentada nesse procedimento trata-se de uma questão de convenção. Para facilitar a compreensão, vamos desenvolver os primeiros termos desse procedimento. Assim: βT −1 (j) = N X k=1 βT −2 (i) = ajk bjk (OT ) βT (k) = | {z } 1 N X N X ajk bjk (OT ) (4.19) k=1 aij bij (OT −1)βT −1 (j) (4.20) j=1 = N X j=1 " aij bij (OT −1) N X k=1 19 ajk bjk (OT ) # (4.21) Figura 4.4. Ilustração da parte backward do algoritmo forward-backward (Fonte: Rabiner [3]) Assumindo que as observações são independentes, podemos escrever: " N # " N N # X XX βT −2 (i) = aij bij (OT −1 ) · ajk bjk (OT ) j=1 | (4.22) j=1 k=1 {z P (OT −1 |qT −2 =Si ) } | = P (OT −1 OT |qT −2 = Si ) {z P (OT ) } (4.23) Assim, a sequência de observação está se criando de trás para a frente. 4.2 Solução do Problema 2 Esse é o problema de achar a sequência ótima de estados associada à sequência de observáveis. Rabiner [3] defende que a dificuldade nesse problema é a de se estabelecer um critério de otimização, dentre vários que possam existir. Assim, a resolução do Problema 2 poderia se dar de diferentes formas, indicando diferentes sequências supostamente ótimas, tudo em função do critério de otimização escolhido. Já Jelinek [1] nem entra nesse mérito, passando direto ao estudo do algoritmo de Viterbi (seção 4.2.1). Para ilustrar a dificuldade na escolha do critério de otimização, num primeiro momento, Rabiner [3] resolve o problema adotando o seguinte critério: a cada instante t escolhe-se o estado individualmente mais provável. No desenvolvimento dessa solução, Rabiner [3] usa as definições das partes do algoritmo forward-backward, como veremos adiante. Agora considere a definição da seguinte variável: γt (i) = P (qt = Si |O, λ). 20 (4.24) Por definição, γt (i) é a probabilidade de que, dado um modelo λ = (Â, B̂, π) e uma sequência completa de observáveis O1 O2 · · · OT , o sistema tenha ocupado o estado Si no instante t. Essa equação pode ser posta em termos das variáveis forward e backward vistas na seção 4.1.1: γt (i) = αt (i)βt (i) αt (i)βt (i) = PN P (O|λ) i=1 αt (i)βt (i) Como cita Rabiner [3], o fator de normalização P (O|λ) = medida de probabilidade, tal que N X PN i=1 (4.25) αt (i)βt (i) faz de γt (i) uma γt (i) = 1 (4.26) i=1 Assim, descobrimos o estado qt individualmente mais provável no instante t através da busca pelo argumento i que retorna o maior valor de γt (i) naquele instante (equação 4.25): qt = argmax [γt (i)] , 0≤t≤T (4.27) 1≤i≤N Contudo, obter o estado mais provável no instante t − 1 para, em seguida, obter o estado mais provável no instante t não é garantia de termos a sequência parcial {qt−1 = Si , qt = Sj } mais provável, pois pode acontecer que a transição entre Si e Sj não esteja prevista. Assim, Rabiner [3] explica que essa solução não se aplica para o caso em que aij = 0 para algum par (i, j) de estados do modelo. Realmente, o critério do “estado mais provável no instante t” só faz sentido se o sistema, além de ergódico, tiver aij > 0, ∀1 ≤ i, j ≤ N. Parece ser, então, mais simples passar direto à resolução pelo algoritmo de Viterbi (abordagem adotada por Jelinek [1]), pois ele comtempla apenas transições possı́veis, não apresentando o problema que acabamos de ver. 4.2.1 Algoritmo de Viterbi Segundo Forney [12], o algoritmo de Viterbi, proposto em 1967 e desde então usado em uma grande gama de aplicações, é uma solução ótima recursiva para o problema de estimar a sequência de estados de um processo Markoviano de estado finito e tempo discreto. De acordo com Rabiner [3] o critério mais usado para a resolução do Problema 2 é o de achar a melhor, ou mais provável, sequência completa de estados, e o algoritmo de Viterbi seria a técnica formal usada em vista desse critério. Ora, esse critério é na verdade o enunciado do Problema 2, o que justifica passar direto ao algoritmo de Viterbi, como fez Jelinek [1]. Ainda, achar a sequência de estados mais provável, Q = q1 q2 · · · qT , dada a sequência de observação O = O1 O2 · · · OT , ou mais formalmente, maximizar P (Q|O, λ) é equivalente a 21 maximizar P (Q, O|λ), pois ambas as operações de maximização vão devolver a sequência de estados mais provável. Seja, então, a seguinte definição: δt (j) = max P [q1 q2 · · · qt = Sj , O1 O2 · · · Ot |q0 = Si , λ] q1 q2 ··· qt−1 (4.28) ou seja, δt (j) guarda a probabilidade do caminho (ou sequência de estados) mais provável que leva ao estado Sj no instante t, gerando os primeiros t observáveis. Por indução, temos: δt+1 (k) = max [δt (j) ajk bjk (Ot+1 )] j (4.29) Para guardar a sequência de estados, usamos um vetor auxiliar ψt (k) que guarda em cada posição t o ı́ndice j do estado qt−1 = Sj que maximiza a sequência até o estado qt = Sk . O procedimento completo é mostrado a seguir: 1. Inicialização: δ1 (j) = aij bij (O1 ), 1≤j≤N ψ1 (j) = 0 (4.30) (4.31) 2. Indução: δt (k) = max [δt−1 (j) ajk bjk (Ot )] , 1≤j≤N 2≤t≤T (4.32) 1≤k≤N ψt (k) = argmax [δt−1 (j) ajk ] , 2≤t≤T (4.33) 1≤j≤N 1≤k≤N 3. Finalização: P ∗ = max [δT (k)] (4.34) qT∗ = argmax [δT (k)] (4.35) 1≤k≤N 1≤k≤N 4. Recriação do Caminho (sequência de estados): ∗ qt∗ = {ψt+1 , {qt+1 }}, t = T − 1, T − 2, · · · , 1 22 (4.36) (a) HMM e observáveis para cada (b) Trellis com a sequência mais provável de estados transição Figura 4.5. Trellis para a representação do algoritmo de Viterbi (Fonte: Jelinek [1]) A Figura 4.5 mostra a sequência mais provável para cada um dos estados finais, de acordo com o algoritmo de Viterbi, para um dado modelo λ e sequência O de observáveis. Assim, a sequência mais provável que leva ao estado 1 é {1 2 3 1 1}, a sequência mais provável que leva ao estado 2 é {1 2 3 1 2}, e aquela levando ao estado 3 é {1 2 3 2 3}. Ao invés de prover explicações formais para cada uma das equações que compõem o algoritmo de Viterbi, vamos explicar informalmente, através do uso do trellis, como funciona esse algoritmo. Para facilitar, useremos a notação (estado)coluna para indicar em que coluna está o estado do qual falamos. Não vamos recriar as sequências que levam aos três estados da última coluna do trellis, e sequer vamos calcular uma sequência completa. Para ilustrar o método, basta nos atermos ao estado 22 . Assim, dois possı́veis caminhos levam a 22 , são eles: {1 1 2} e {1 3 2}. O estado 11 só pode ter sido precedido pelo estado 10 , então atribuı́mos “peso 1” a essa transição; enquanto que o estado 31 pode ter sido precedido tanto por 10 quanto por 20 , assim, atribuı́mos “peso 0.5” a cada uma dessas transições. O estado 22 pode ter sido precedido tanto por 11 quanto por 31 , e mais uma vez atribuı́mos “peso 0.5” a cada uma das transições. Se multiplicarmos esses pesos, teremos o valor 0.25 para a sequência parcial {1 3 2} e o valor 0.5 para a sequência parcial {1 1 2}, fazendo desta última a sequência parcial mais provável, como mostra a Figura 4.5. Como dito anteriormente, a Figura 4.5 mostra a sequência mais provável para cada um dos estados finais (coluna 4 do trellis). Essas sequências são {1 2 3 1 1}, {1 2 3 1 2} e {1 2 3 2 3}. Para descobrir qual dentre essas três é de fato a mais provável, basta seguir o procedimento 23 recém explicado e obteremos probabilidades iguais para as duas primeiras sequências, sendo que a última é menos provável que as anteriores. O algoritmo de Viterbi resolve esse problema escolhendo arbitrariamente uma dentre as duas sequências igualmente prováveis. 4.3 Solução do Problema 3 Rabiner [3] menciona que, dentre os três Problemas Canônicos, este é de longe o mais difı́cil de resolver, pois não existe método analı́tico que permita obter os parâmetros λ = (Â, B̂, π) que maximizam a probabilidade de um modelo gerar a sequência completa de observáveis, P (O|λ) λ = argmax P (O|λ) (4.37) λ No entanto, existe um algoritmo capaz de maximizar a probabilidade local. Esse algoritmo, de acordo com Jelinek [1] é citado na literatura sob diferentes nomes, tais como algoritmo de Baum, Baum-Welch ou algoritmo forward-backward. Passemos então ao método. 4.3.1 Algoritmo de Baum-Welch Considere a seguinte definição5 : ξt (i, j) = P (qt = Si , qt+1 = Sj |O, λ); (4.38) ou seja, ξt (i, j) é a probabilidade conjunta de estar no estado Si no instante t e no estado Sj no instante t + 1, dado o modelo inicial λ = (Â, B̂, π) e a sequência de treinamento O. Essa variável pode ser expressa em termos das variáveis forward (equação 4.10) e backward (equação 4.15), tomando a seguinte forma: P (qt = Si , qt+1 = Sj , O|λ) P (O|λ) αt (i) aij bij (Ot+1 ) βt+1 (j) P (O|λ) αt (i) aij bij (Ot+1 ) βt+1 (j) (4.39) PN PN j=1 αt (i) aij bij (Ot+1 ) βt+1 (j) i=1 ξt (i, j) = P (qt = Si , qt+1 = Sj |O, λ) = = = 5 O desenvolvimento do algoritmo de Baum-Wech apresentado nesse trabalho é baseado no artigo de Rabiner, [3]. 24 Agora, façamos o somatório da equação 4.39 sobre o ı́ndice j, 1 ≤ j ≤ N: N X ξt (i, j) = j=1 N X αt (i) aij bij (Ot+1 ) βt+1 (j) P (O|λ) j=1 = = αt (i) hP N j=1 aij bij (Ot+1 ) βt+1 (j) P (O|λ) αt (i) βt (i) P (O|λ) i (4.40) A Figura 4.6 ilustra a situação. Figura 4.6. Ilustração do algoritmo forward-backward aplicado à solução do Problema 3 (Fonte: Rabiner [3]) A parte entre colchetes na equação 4.40 é exatamente a equação 4.17, relativa à variável backward no instante t. Logo, a equação 4.40 se iguala à equação 4.25, apresentada durante a resolução do Problema 2, que define γt (i) em função das variáveis forward e backward. Portanto, γt (i) = N X ξt (i, j) (4.41) j=1 Se fizermos o somatório de γt (i) sobre o tempo de observação, T , obteremos a estimativa do número de vezes que o estado Si é visitado em todo esse perı́odo. Se quisermos saber o número de transições a partir de Si , basta levar o somatório até o instante T − 1. Analogamente, ao fazer o somatório de ξt (i, j) até T − 1, obtemos a estimativa do número de vezes que ocorreram 25 transições entre os estados qt−1 = Si e qt = Sj . Formalmente: T −1 X γt (i) = número esperado de transições a partir de Si (4.42) ξt (i, j) = número esperado de transições de Si para Sj (4.43) t=0 T −1 X t=0 Usando essas fórmulas, podemos usar o seguinte método para reestimar os parâmetros de um modelo: π̄i = número esperado de vezes no estado q0 = Si = γ1 (i) (4.44) número esperado de transições do estado Si para o estado Sj āij = número esperado de transições a partir do estado Si PT −1 ξt (i, j) = Pt=0 (4.45) T −1 γ (i) t t=0 número esperado de transições entre os estados (i,j) e observações do sı́mbolo yk b̄ij (k) = número esperado de transições entre os estados (i,j) PT t=0 γt (j) = s.t.Ot =yk PT t=0 γt (j) (4.46) Se definirmos o modelo atual como λ = (Â, B̂, π) e usarmos esses parâmetros para calcular ¯ ¯ os parâmetros do novo modelo, λ̄ = (Â, B̂, π̄), foi provado por Baum e seus colegas que 1. ou λ̄ = λ, o que significa que λ define um ponto crı́tico da função de probabilidade e, portanto, o modelo λ é aquele que maximiza a sequência de observação; 2. ou λ̄ é mais provável que λ, pois P (O|λ̄) > P (O|λ), significando que achamos um novo modelo, λ̄, de onde é mais provável que a sequência de observação O tenha sido gerada. Esse processo é executado iterativamente, quantas vezes forem necessárias, até que λ̄ = λ. 26 5 Considerações Finais Esse trabalho tratou das bases do formalismo de Modelos Ocultos de Markov (Hidden Markov Models - HMM), como fundamentado por Rabiner [3] e Jelinek [1]. Antes de mais nada, conceituou-se Cadeias de Markov, visto que há sempre uma Markov governando uma modelagem em HMM. Logo após, apresentou-se a definição de HMM, seguida da apresentação dos problemas canônicos que, uma vez resolvidos, permitem fazer os devidos ajustes para finalização da modelagem. Assim, um dos problemas se dedicava a calcular a probabilidade de um modelo gerar uma sequência de observáveis; outro problema tratou de identificar, dentre as possı́veis sequências de estados na Markov embutida, aquela que tivesse a maior probabilidade de gerar uma determinada sequência; o último problema buscava novos parâmetros para o modelo, tentando elevar a probabilidade de geração da sequência observada. Conduzimos esses tópicos tratando de uma classe muito restrita de problemas, a começar pelo fato de termos trabalhado apenas com modelos Markovianos discretos no espaço de estados e no tempo. Outras restrições foram quanto à forma da matriz de transição, pois atacamos apenas matrizes estacionárias, regulares e, na sua grande maioria, homogêneas; quanto à finitude do espaço de observáveis e à independência entre observações. Ainda, não consideramos nesse trabalho a probabilidade de transições entre estados da Markov não emitirem observáveis. Essas simplificações são justificadas por esse se tratar de um trabalho de caráter introdutório ao assunto. Em trabalhos futuros, pretendemos expandir o conceito com o objetivo de criar modelos mais realistas, eliminando as restrições acima enumeradas e aplicando a problemas de interesse. Dentre as atividades planejadas para a continuação desse estudo, está a identificação de uma forma de relacionar HMM com Rede de Autômatos Estocásticos (Stochastic Automata Network - SAN), um formalismo Markoviano muito utilizado em nosso grupo de pesquisa (Performance Evaluation Group - PEG). 27 Referências Bibliográficas [1] F. Jelinek. Statistical Methods for Speech Recognition. The MIT Press, 1998. [2] L. E. Reichl. A Modern Course in Statistical Physics. WILEY-VCH, second edition, 2004. [3] L. R. Rabiner. A tutorial on hidden markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2):257–286, 1989. [4] S.E. Levinson, L.R. Rabiner, and M.M. Sondhi. An introduction to the application of the theory of probabilistic functions of a markov process to automatic speech recognition. The Bell System Technical Journal, 62(4):1035–1074, 1983. [5] B. H. Juang. On the hidden markov model and dynamic time warping for speech recognition - a unified view. The Bell System Technical Journal, 63(7):1213–1243, 1984. [6] L. R. Rabiner and B. H. Juang. An introduction to hidden markov models. IEEE ASSP Magazine, 3(1):4–16, 1986. [7] J. S. Bridle. Stochastic models and template matching: some important relationships between two apparently different techniques for automatic speech recognition. In Proceedings of the Institute of Acoustics (Autumn Conference), pages 1–8, 1984. [8] J. Makhoul, S. Roucos, and H. Gish. Vector quantization in speech coding. Proceedings of the IEEE, 73(11):1551–1588, 1985. [9] S.E. Levinson. Structural methods in automatic speech recognition. Proceedings of the IEEE, 73(11):1625–1650, 1985. [10] G. Bolch, S. Greiner, H. de Meer, and K. S. Trivedi. Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications. John Wiley & Sons, second edition, 2006. 28 [11] Oxford. Dictionary of Physics. Oxford University Press, fourth edition, 2000. [12] G. D. Forney. The viterbi algorithm. Proceedings of the IEEE, 61(3):268–278, 1973. 29