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