Instituto de Tecnologia de Massachusetts
Departamento de Engenharia Elétrica e Ciência da Computação
6.345 Reconhecimento Automático da Voz
Primavera, 2003
Publicado: 07/03/03
Devolução: 19/03/03
Tarefa 5
Introdução aos Modelos Ocultos Markov
Introdução
Os modelos Ocultos( Escondidos ) de Markov (Hidden Markov Models – HMM) são uma
classe de modelos estatísticos úteis para análise de uma serie discreta no tempo de
observações tal como uma corrente de sinais acústicos extraídos de um sinal de voz. Os
HMMs são adequados para o trabalho de reconhecimento de voz por sua capacidade
inerente de representar os eventos acústicos de duração variável e da existência de
algoritmos eficientes para automatizar o calculo dos parâmetros dos modelos a partir dos
dados de treino.
Software
Neste laboratório usaremos um programa chamado hmm_tool. Este programa opera na
observação discreta dos HMMs. Ele tem a capacidade de gerar seqüências de observação
aleatórias de um HMM, executar o algoritmo de pesquisa de Viterbi em uma seqüência de
observação de um HMM particular, e estimar parâmetror de um HMM usando o
algoritmo de Baum-Welch. Para este laboratório utilizaremos hmm_tool em dados
artificiais para nos familiarizarmos com as propriedades de HMMs e de seus algoritmos
associados. O programa hmm_tool opera diretamente a partir da linha de comando do
Unix. Os HMMs e as seqüências de observações são armazenadas em arquivos ASCII e
passados para o hmm_tool através das opções da linha de comando. Para listar o conjunto
completo de opções disponíveis da linha de comando digite:
% hmm_tool -help
Iniciando
Para iniciar este laboratório, digite os seguinte comando no prompt do UNIX:
% start_lab5.cmd
Isto fará uma cópia local (no seu diretório raiz) do conjunto de arquivos necessários para o
laboratório. Estes arquivos contêm os modelos ocultos de Markov e as seqüências de
observações usadas durante o laboratório. O emprego do hmm_tool também será exibido.
Parte I: HMMs Simétricos
Começaremos com um classe de HMMs chamada de “simétrica”. A estrutura dos HMMs
simétricos é suficientemente simples para permitir a estimação direta do parâmetros do
modelos a partir da observação dos dados em vez de fazer estimação interativa usando o
algoritmo de re-estimação de Baum-Welh. Um HMM simétrico de N-estados tem as
seguintes propriedades:
1. O tamanho do alfabeto de saída é igual ao número de estados N.
2. Cada estado pode ser a saída de apenas um símbolo e dois estados não podem ser a
saída do mesmo símbolo. Mais precisamente, a matriz B é uma matriz identidade N
por N . Isto basicamente significa que o modelo não é mais “oculto”.
3. Todas as transições que deixam um nó são igualmente prováveis (exceto as autotransições); por exemplo para um estado dado i, aij = aik ∀ j, k ≠ i onde 0 ≤ i,j,k < N.
4. Um HMM simétrico de N estados é completamente determinado pela suas N
probabilidades de transição auto loop a00, a11, ..., a(N-1)(N-1).
Aqui esta um exemplo de HMM simétrico de 4 estados :
T1. Mostre os parâmetros de dois HMMs simétricos que utilizaremos e analisaremos
suas propriedades com os comandos:
% hmm_tool -hmm_in symmetric1.hmm -print_models
% hmm_tool -hmm_in symmetric2.hmm -print_models
Use symetric1.hmm (que é na realidade o mesmo que o modelo mostrado acima) para
gerar um única seqüência de observações de 100 símbolos de comprimento com o
seguinte comando:
% hmm_tool -hmm_in symmetric1.hmm -generate 1 100 \-print_obs -obs_out seq1.obs
Note que a sequência de observação é escrita no arquivo seq1.obs. Calcule e registre o
número de vezes que todas os 16 possíveis símbolo bigramas de saída tenham
ocorrido na seqüência de observação, utilizando o seguinte comando:
% hmm_tool -hmm_in symmetric1.hmm -obs_in seq1.obs \-count_bigrams
Gere outra seqüência de observação com o comprimento de 10.000 símbolos e calcule e
registre novamente a contagem de bigramas (não use a opção –print_obs neste
momento para evitar imprimir as 10.000 observações na tela).
Q1: Derive uma formula que estime o probabilidade de transições de auto loop
diretamente da contagem de bigramas calculada. Use esta formula juntamente com a
contagem observada para estimar a probabilidade de transição de auto loop a partir de
de ambas as seqüências de observações. A contagem proveniente da seqüência de
observação mais longa fornece uma estimativa mais precisa como é de se esperar?
T2. O segundo modelo de HMM, symetric2.hmm, difere do primeiro apenas na
probabilidade de transição a33 que é igual a 1.0. Gere um seqüência de observação
de 5.000 símbolos de comprimento usando symetric2.hmm e calcule a contagem de
bigramas.
Q2: O que acontece quando se tenta estimar as probabilidade s de transição do auto
loop para este HMM e por quê? Observar uma seqüência longa ajuda? O que se
pode fazer para estimar as transições de auto loop para este modelo?
Parte II: Treinando via o algoritmo de Baum-Welch
Nesta parte do laboratório, analisaremos alguns questões relacionadas ao treino de
HMMs utilizando Baum-Welch ou o algoritmo de Retrocesso e Avanço (forward –
backward algorithm). Estaremos interssados com um modelo oculto de Markov de
5 estados esquerda para a direita definido pela seguintes matrizes de transição e
de probabilidades de saídas:
0
0,8 0,1 0,1 0
 0 0,9 0,1 0
0 

A= 0
0 0,8 0,1 0,1


0
0 0,9 0,1
0
 0
0
0
0
1 
0
0,7 0,3 0
0
0 0,8 0,2

B= 0
0
0
0

0
0
0
0
 0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0 
0
0
0
0

0,2 0,8 0
0
0
0 0,3 0,7 
Note que A é triangula superior, que resulta do modelo esquerda para a direita
(transições para trás são proibidas). Geraremos algumas observações usando este
modelo e então usaremos o algoritmo de treinamento de Baum-Welch para treinar
um novo modelo HMM e examinar quão próxima é a estimativa do modelo real.
Exploraremos o efeito de diferentes quantidades de dados de teste e o efeito de
diferentes matrizes iniciais A e B.
T3. Analise o modelo 5-state -lr.hmm para ver se ele se ajusta as matrizes A e B, acima
com o comando:
% hmm_tool -hmm_in 5-state-lr.hmm -print_models
Gere 10 seqüencias de observação, cada uma com um comprimento de 50 símbolos,
usando o seguinte modelo:
% hmm_tool -hmm_in 5-state-lr.hmm -generate 10 50 \-print_obs -obs_out
seq2.obs
Analise o HMM 5-state-init.hmm, que tem os mesmos elementos zeros nas suas
matrizes A e B (ou seja, as mesmas transições proibidas e saídas) como o modelo
atual mas os elementos que não são zeros são uniformemente inicializados.
Usaremos o 5-state-init1.hmm como o modelo inicial para a re-estimação do
algoritmo de Baum-Welch para treinar um HMM a partir dos dados observados.
Para executar o treinamento de Baum-Welch usando as seqüências de observações
que você acabou de gerar , digite o seguinte comando:
% hmm_tool -hmm_in 5-state-init1.hmm -obs_in seq2.obs \ -bw 20 -print_models
Observe o log da probabilidade do resultado dos dados de treinamento após cada
iteração e note quão rapidamente o algoritmo de Baum-Welch converge.
Depois, crie 100 seqüências de observações de 50 símbolos de comprimento e use
novamente 5-state-init1.hmm como modelo inicial para a re-estimativa dos
parâmetros do HMM a partir do novo conjunto de 100 seqüências de observações.
Compare os parâmetros dos modelos estimados a partir de 10 seqüências de dados e
de 100 seqüências dados com os parâmetros do modelo real que gerou as
seqüências.
Q3: Qual é a razão do número de pontos de dados no conjunto de dados de
treinamento para o número de parâmetros livres sendo estimados nos dois ensaios
executados acima? Existe uma diferença notável da qualidade das estimativas das
matrizes A e B entre os dois ensaios?
T4. Iremos agora estimar os parâmetros do HMM usando HMMs iniciais mais gerais.
Examine os três modelos HMM iniciais:
• 5-state-init2.hmm
• 5-state-init3.hmm
• 5-state-init4.hmm
Note que o 5-state-init2.hmm é um modelo esquerda para direita enquanto os 5state-init3.hmm e o 5-state-init4.hmm não são. Use o algoritmo de Baum-Welch
para estimar os parâmetros do HMM usando uma seqüência de observação de 100
dados gerados em T3 começando com o modelo inicial 5-state-init2.hmm. Grave os
valores de log probabilidade dos dados de treino depois de cada iteração. Quando o
treinamento terminar, compare os valores dos parâmetros do HMM estimado com
aqueles do modelo real .
Repita esta operação para 5-state-init3.hmm e para o 5-state-init4.hmm.
Q4: No mesmo conjunto de eixos, plote a log probabilidade como uma função do
número de iterações observadas no treinamento 5-state-init2.hmm, 5-stateinit3.hmm e 5-state-init4.hmm. O que se pode dizer da dificuldade relativa do
treinamento de modelos mais gerais versus os mais específicos ? O que se conclui
sobre a importância da inicialização das matrizes A e B antes de começar o
treinamento ?
Q5: Qual propriedade do algoritmo de Baum-Welch que deveria ser considerada
como responsável pelas maiores discrepâncias que você tem observado entre os
parâmetros estimados e os verdadeiros?
Parte III: Representação Treliça (ou grade) e Procura (ou pesquisa) de Viterbi
Ambos os algoritmos de Avanço e Retrocesso usados na re-estimação de Baum-Welch e a
decodificação de Viterbi dependem da representação treliça (ou gráfico) dos modelos
ocultos de Markov. Nesta sessão o laboratório lida com HMM de 2-estados .
0,4 0,6
A=
1 
0
 0,8 0,1 0,1
B=

0,2 0,2 0,6
T5. Gere e escreva uma seqüência , de 5 observações a partir do modelo mostrado
acima com o comando:
% hmm_tool -hmm_in 2-state-lr.hmm -generate 1 5 \-print_models -print_obs
Q6: Use a folha de resposta anexada para desenhar uma treliça para a seqüência
que você observou. Calcule todos as probabilidades dos ramos e determine qual o
caminho mais provável através da treliça.
Q7: Estime aproximadamente o comprimento de uma seqüência de observação que
poderia causar underflow em computador típico se o logaritmo não fosse utilizado,
ou seja, qual seria o comprimento da seqüência de observação para uma
probabilidade da ordem de 10-100?
Parte IV: Reconhecimento com Hmms
Em um típico sistema de reconhecimento de palavras baseado em HMM, as acústicas de
cada palavra no vocabulário são representadas por um modelo oculto de Markov em
separado . O reconhecimento pode ser feito através do algoritmo de Viterbi para calcular a
sequência de estados ocultos mais provável em cada um dos HMMs candidatos e então
selecionar a palavra correspondente ao HMM com a seqüência de estados mais provável.
T6: Cada um destes arquivos
• testA.obs
• testB.obs
• testC.obs
contêm uma seqüência de 50 observações geradas a partir de um dos três HMMs:
• recognition1.hmm
• recognition2.hmm
• recognition3.hmm
Os HMMs são modelos de 5-estados da esquerda para direita que diferem apenas nas suas
matrizes B . Use o algoritmo de pesquisa de Viterbi para calcular o log da probabilidade
da contagem da seqüência de estados ocultos mais provável através de cada modelo para
cada seqüência de observação (certifique-se de calcular as nove probabilidades). Por
exemplo, para calcular a contagem entre testA.obs e recognition1.hmm, podemos dizer :
% hmm_tool -hmm_in recognition1.hmm \-obs_in testA.obs -viterbi
Q8: Faça uma tabela 3 x 3 mostrando o calculo da contagem de Viterbi para cada modelo
candidato e cada seqüência de observação. Qual modelo foi o mais provável para gerar
cada seqüência de teste baseada nesta contagem? Qual outro método de contagem pode ser
utilizado para realizar esta tarefa de reconhecimento?
Parte V: HMMs de Densidade Continua
Em classe, resolvemos os três principais problemas de HMM para o caso de quando as
observações forem caracterizadas como símbolos discretos escolhidos a partir de um
alfabeto finito, e portanto foi possível utilizar uma densidade de probabilidade discreta
para cada estado do modelo HMM. A classe mais comum de HMM é a dos HMMs de
densidade contínua onde as observações são continuas. A representação mais geral da
função densidade de probabilidade (fdp) para qual um procedimento de re-estimação tem
sido formulado, é a mistura de gaussianas da forma :
b j (ot ) = ∑ c jk N (ot , µ jk ,U jk )
M
k =1
onde ot é o vetor de observação sendo modelado no tempo t, cjk é o coeficiente de mistura
para a kth componente da mistura no estado j e N é a densidade gaussiana com o vetor
media µjk e matriz de covariância Ujk para a kth componente da mistura no estado j.
Neste problema, veremos uma simples aproximação para derivar a formula de re-estimação
através do uso de um caso simplificado de uma única fdp gaussiana observada , quando o
número de misturas for igual M=1:
b j (ot ) = N (ot , µ j ,U j )
Q9: Para encontrar a formula de re-estimação para µj, quantizaremos a variável
aleatória contínua usando um conjunto de partes derivadas a partir da distribuição
continua . Sejam ot os valores a serem quantizados tal que cada ot ≈ ok para algum
valor de k. Note que o ok é agora equivalente a um símbolo de observação do caso
discreto. Expresse µj como uma função de ok e b j (k ) onde b j (k ) é formula de a reestimação para a observação do kth símbolo no jth estado para o caso discreto e é
dado como:
T
b j (k ) =
∑γ ( )
t j
t =1
s . t . ot = o k
T
∑γ ( j )
t
t =1
lembre-se que γ t ( j ) é a probabilidade de estar no estado j no instante t.
Sugestão: Comece com a definição da média para um variável aleatória contínua e
aproxime a integração por uma soma sobre os valores quantizados.
Q10: Mostre que a formula de re-estimação para µ j , a média para a Gaussiana no
estado j, é dada por:
T
µj =
∑γ ( )
t =1
T
t j ot
∑γ ( j )
t =1
t
Folha de Resposta para Tarefa 5 Q6
Instruções:
1. Entre com os cinco símbolos que você observou (de T5) no topo da linha.
2. Rotule cada arco do diagrama no topo com a probabilidade conjunta de
ocorrer a transição e a saída correspondente sendo gerada no estado seguinte.
3. No segundo diagrama, entre em cada caixa com a probabilidade do caminho
parcial mais provável através daquele estado e desenhe setas conectando os
estados que estão no melhor caminho parcial.
4. Veja qual a seqüência de estados ocultos mais provável a partir do segundo
diagrama e escreva o resultado no espaço fornecido.