Um Estudo Sobre os Modelos Ocultos de Markov

Pontif´cia Universidade Cat´ lica do Rio Grande do Sul ı o
Faculdade de Inform´ tica a P´ s-Graduacao em Ciˆ ncia da Computacao o ¸˜ e ¸˜

Um Estudo sobre Modelos Ocultos de Markov
HMM - Hidden Markov Model

Luciana da Silveira Espindola

Orientador: Paulo Henrique Lemelle Fernandes

Introducao a Pesquisa I
¸˜ `
Porto Alegre, junho de 2009

Sum´ rio a LISTA DE FIGURAS

ii

Cap´tulo 1: Introducao ı ¸˜

1

Cap´tulo 2: Cadeias de Markov ı 3

2.1

Definicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
¸˜

4

2.2

Modelo Markoviano do Tempo . . . . . . . . . . . . . . . . . . . . . . . . . .

7

Cap´tulo 3: Modelos Ocultos de Markov ı 3.1

Definicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
¸˜

Cap´tulo 4: Problemas Canˆ nicos ı o
4.1

9
10

13

Algoritmo Forward-Backward . . . . . . . . . . . . . . . . . . . . . .

16

Solucao do Problema 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
¸˜

20

4.2.1

Algoritmo de Viterbi . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

Solucao do Problema 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
¸˜

24

4.3.1

4.3

14

4.1.1
4.2

Solucao do Problema 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
¸˜

24

Algoritmo de Baum-Welch . . . . . . . . . . . . . . . . . . . . . . . .

Cap´tulo 5: Consideracoes Finais ı ¸˜

27

´
ˆ
REFERENCIAS BIBLIOGRAFICAS

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: a a
Jelinek [1]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.1

12

Trellis para a sequˆ ncia de observ´ veis “0 1 1 0” relativa a Figura 3.1 (Fonte: e a
`
Jelinek [1]) . . . . . . . . . . . . . . . . . . . . . . .