Modelos de Markov e Aplicações∗
Graçaliz P. Dimuro1 , Renata H. S. Reiser1 , Antônio C. R. Costa12 , Paulo L. R. Sousa3
1
2
Escola de Informática – Universidade Católica de Pelotas
Rua Felix da Cunha 412 – 96010-140 Pelotas, RS
Programa de Pós-Graduação em Computação – Universidade Federal do Rio Grande do Sul
Caixa Postal 15064 – 90501-970 Porto Alegre, RS
3
Mestrado em Saúde e Comportamento – Universidade Católica de Pelotas
Rua Felix da Cunha 412 – 96010-140 Pelotas, RS
{liz,reiser,rocha}@atlas.ucpel.tche.br
Abstract. This tutorial presents the basic concepts concerning Markov chains,
in particular, regular and absorbing chains. The principal concepts of Hidden Markov Models are also presented. Some applications of these models are
shown.
Resumo. Este tutorial apresenta os conceitos básicos das cadeias de Markov,
ressaltando principalmente, as cadeias regulares e as absorventes. Também
apresentam-se os principais conceitos sobre os modelos de Markov ocultos.
Exemplos ilustrativos foram incluı́dos, para mostrar as potencialidades de
aplicação destes modelos.
1. Introdução
Um processo de Markov é um processo estocástico cujo comportamento dinâmico é tal
que as distribuições de probabilidade para o seu desenvolvimento fututo depende somente
do estado presente, não levando em consideração como o processo chegou em tal estado.
Os processos markovianos são modelados formalmente por sistemas de transições
de estados, onde os estados são representados em termos de seus vetores probabilı́sticos,
que podem variar no espaço temporal (discreto ou contı́nuo), e as transições entre estados
são probabilı́sticas e dependem apenas do estado corrente.
Se o espaço de estados é discreto (enumerável), então o modelo de Markov é denominado de cadeia de Markov [17, 19]. As propriedades desses modelos são estudadas
em termos das propriedades das matrizes de transições de estados que são utilizadas na
sua descrição.
Existem processos de Markov que são modelados como aproximações do mundo
real, onde nem todos os estados são perfeitamente conhecidos. Nestes casos, diz-se que
o modelo é escondido, e a questão central em torno desses modelos é o grau com que são
capazes de capturar a essência do processo escondido sob eles.
∗
Este trabalho foi parcialmente financiado pela FAPERGS e CNPq.
O estudo dos modelos de Markov têm uma aplicação muito ampla em várias áreas,
como, por exemplo, ciências sociais, biológicas e administrativas. Os modelos de Markov
escondidos, que surgiram originalmente no domı́nio de reconhecimento da fala, atualmente têm sido empregados como modelos de computação natural – the so-called brain’s
programs [2], em trabalhos sobre visão computacional [4] e reconhecimento de manuscritos, de formas, gestos e expressões faciais, em biologia computacional, entre outros (veja
em http://www-sig.enst.fr/∼cappe).
Este tutorial é fruto dos estudos sobre os modelos de Markov, visando a sua
aplicação em processos de tomada de decisão, que está sendo desenvolvido junto ao Mestrado em Saúde Mental e Comportamento da UCPel.
2. Modelos de Markov
Uma modelo de Markov é um sistema de transições de estados, onde a probabilidade do
sistema estar em um certo estado futuro depende apenas do estado corrente do sistema.
Esta seção resume os principais conceitos básicos e propriedades desses modelos. As
provas das proposições e teoremas podem ser encontradas em [17, 19].
2.1. Cadeias de Markov
Um modelo de Markov onde o espaço de estados I é discreto é denominado de Cadeia de
Markov e é completamente descrito por sua matriz de transição de estados. Esta matriz
é dinâmica, pois permite que as probabilidades de transição se modifiquem em função do
tempo t, onde t é discreto.
Considere uma cadeia de Markov com N estados xn ∈ I e sejam xi , xj ∈ I.
Denota-se xi (t) para significar que o processo está no estado xi no tempo t.
Definição 1 Se pij é a probabilidade de transição do estado xi (t) para o estado xj (t+1),
então a matriz N × N , dada por
P = [pij ],
denomina-se matriz de transição de estados da cadeia de Markov.
Observa-se que, na Definição 1, a soma das linhas da matriz P deve ser sempre
igual a 1.
A matriz de transição também pode ser dada por um diagrama de transições de
estados. A Figura 1 mostra o diagrama de transições de estados para uma cadeia de
Markov com apenas 2 estados.
Proposição 1 Para t arbitrário, tem-se que:
(i) A probabilidade de transição do estado xi (t) para o estado xj (t + n) (em n passos) é
dada por pni,j ;
(ii) A matriz de transição de n passos, denotada por Pn , é calculada como a potência n
da matriz de transição P , isto é,
Pn = P n .
p 01
p 00
x1
x0
p 11
p 10
Figura 1: Diagrama da matriz de transições de estados de uma cadeia de Markov
de dois estados.
Para simular um processo de Markov, considerando um estado inicial x0 , pode-se
escolher um estado sucessor de acordo com as probabibilidades p0j , para j = 1, . . . , N ,
determinando um novo estado x1 . Repite-se o processo para gerar o próximo estado, e
assim sucessivamente. Devido à natureza probabilı́stica do modelo, cada ves que esta
simulação for repetida, é provável que uma sequência diferente de estados seja obtida
como resultado. Portanto, a única forma de analisar o proceso é manter o registro das
probabilidades de estar em um estado.
Definição 2 Seja Si (t) a probabilidade de que um processo de Markov esteja em um
estado xi no tempo t. Então o vetor


S1 (t)
 S2 (t) 


s(t) =  .. 
 . 
SN (t)
é denominado de vetor de distribuição de probabilidades de estado da cadeia de Markov
no tempo t.
Seja sT (0) a distribuição inicial do processo1 . A evolução do vetor de distribuição
é governada pela matriz de transição em t passos.
Proposição 2 Para qualquer tempo t, tem-se que
sT (t) = sT (0)Pt ,
onde Pt é calculada como em ?? e sT é o vetor transposto de s.
2.2. Cadeias Regulares
Considerando que o vetor de distribuição evolui no tempo, observa-se que há circunstâncias em que ocorre uma distribuição de probabilidade de equilı́brio v tal que
lim s(t) = v,
t→∞
independentemente da distribuição inicial s(0). Isto ocorre em processos de Markov denominados de regulares.
1 T
s é o vetor transposto de s.
Definição 3 Diz-se que um modelo de Markov é regular se sua matriz de transição inicial
P é regular, isto é, alguma potência de P contém somente entradas positivas.
Segue da Definição 3 que um processo de Markov é regular se, para algum t,
tem-se que Pt > 0. Isto significa que, em uma cadeia de Markov regular, todo estado é
acessı́vel a partir de outro, existindo um caminho de comprimento finito entre quaiquer
dois estados, possibilitando a comunicação entre todos os estados.
Seja wT = [w1 , w2 , . . . , wN ] um vetor de comprimento N . Diz-se que w é um
vetor probabiı́stico se w1 , w2 , . . . , wN ≥ 0 e w1 + w2 + . . . + wN = 1.
Teorema 1 Se um processo de Markov é regular, então exite único vetor probabilı́stico
v, denominado de distribuição de equilı́brio, tal que:
(i) v T P = v T ;
(ii) limt→∞ P t = P ∗ , onde P ∗ é formada por t linhas iguais a v T .
2.3. Cadeias Não-Regulares
Existem processos que podem apresentar estados que não acessı́veis a partir de algum
outro estado, isto é, a probabilidade de transição para tais estados é igual a zero. Além
disso, um estado de um processo de Markov finito poderá eventualemnte atingir um estado
de comunicação fechada, absorvente, cuja probabilidade é igual a 1.
Um estado xi de uma cadeia de Markov é denominado de estado absorvente se,
uma vez nesse estado, é impossı́vel sair dele, isto é, pii = 1. Segue que pij = 0, para
i 6= j.
Definição 4 Diz-se que uma cadeia de Markov é absorvente se ela apresenta um estado
absorvente e se de cada estado não absorvente é possı́vel ir para algum estado absorvente em algum tempo t, isto é, para cada estado não absorvente xi (t), existe um estado
absorvente xj (t + 1) tal que pij > 0, para algum t.
Observa-se que, e uma cadeia de Markov absorvente, o estado do sistema será
eventualemente um dos estados absorventes.
Dada uma cadeia de Markov com k estados absorventes, é possı́vel redistribuir
as linhas da matriz de transição P , de modo que os estados absorventes fiquem nas k
primeiras linhas. Com isso, um processo de Markon não regular pode ser sempre reorganizado em quatro submatrizes.
Definição 5 Seja P a matriz de transição de uma cadeia de Markov com k estados absorventes. Então:
(i) A matriz canônica da cadeia é dada por:
Ik
θ
∗
P =
Px→a Px→x
(ii) A matriz fundamental é obtida por:
F = [I − Px→x ]−1
(iii) A matriz de probabilidade de absorção é calculada como o produto:
A = F Px→a
onde Ik é uma matriz diagonal unitária k × k que representa os k estados absorventes,
θ é uma matriz nula, Ps→a representa as probabilidades de transição de qualquer estado
para todos os estados absorventes, Ps→s representa as probabilidades de transição entre
todos os estados não absorventes, e aij é a probabilidade de que o sistema venha a estar
no estado absorvente xj (t), para algum tempo t, dado que esteja inicialmente no estado
não absorvente xi .
2.4. Aplicações de Cadeias Regulares à Genética
Nesta seção introduz-se uma aplicação trivial das cadeias de Markov em problemas de
Genética, através de um exemplo extraı́do de [19].
Certas caracterı́sticas das plantas e dos animais são determinadas por um par de
genes, cada um dos quais podendo ser de dois tipos, denotados por A e a. Existem três
genótipos possı́veis: AA, Aa e aa (os genótipos Aa e aA são idênticos).
Em alguns casos esses três genótipos resultam em três caracterı́sticas distintas e
em outros o AA e o Aa exibem uma mesma forma observável. Nesta última situação,
diz-se que o gene A domina o gene a.
O indivı́duo chama-se dominante se tem o genótipo AA, heterozigoto se tem
genótipo Aa e recessivo se tem o genótipo aa. Por conveniência, denota-se um indivı́duo
AA por D, um Aa por H e um aa por R.
No caso de cruzamento, o filho herda um gene de cada um dos pais. Admita-se
que as probabilidades dos genótipos dos filhos de acordo com os dos pais sejam as dadas
nas Tabelas 1, 2 e 3, a seguir.
Tabela 1: Probabilidades dos genótipos do filho de dois indivı́duos H
D (AA) H (Aa) R (aa)
0.25
0.50
0.25
Tabela 2: Probabilidades dos genótipos do filho de um indivı́duo H com outro D
D (AA) H (Aa) R (aa)
0.50
0.50
0.00
Tabela 3: Probabilidades dos genótipos do filho de um indivı́duo H com outro R
D (AA) H (Aa) R (aa)
0.00
0.50
0.50
As cadeias de Markov intervalares podem auxiliar em cálculos sobre hereditariedade, como descrito neste próximo exemplo.
Exemplo 1 Suponha que no tempo 0, um indivı́duo é acasalado com outro, sendo este
do tipo H. No tempo 1, o produto do acasalamento é novamente acasalado com um
indivı́duo H. O processo repete-se então da mesma maneira. Considera-se como estado
do sistema no tempo t o genótipo do t-ésimo filho. Tem-se como resultado uma cadeia de
Markov com três estados (D, H, R), cuja matriz de transição é dada por:


0.5 0.5 0
P =  0.25 0.5 0.25  ,
0 0.5 0.5
sendo a matriz de transição de 2 passos calculada como (com precisão igual a 2 no
Maple):


0.38 0.50 0.13
P2 =  0.25 0.50 0.25  .
0.13 0.50 0.38
Observa-se que, em 1, devido a erros de arredondamento, tem-se que
(1)
P3
j=1
p1 j 6=
1.
Pela observação da matriz de transição de dois passos P2 dada em 1, que apresenta todas as entradas positivas, conclui-se que esta matriz aproxima uma matriz real
regular que tem uma distribuição de equilı́brio v aproximada pelo vetor probabilı́stico
V = [v1 , v2 , v3 ], tal que V P ≡ V . O sistema correpondente é:
5v1 + 0.25v2
5v1 + 5v2 + 5v3
0.25v2 + 0.5v3
v1 + v2 + v3
=
=
=
=
v1
v2
v3
1
A solução do sistema resulta na distribuição real de equilı́brio v = [.25, .5, .25].
2.5. Aplicações de Cadeias Absorventes na Aprendizagem por Pares Associados
Nesta seção apresenta-se o clássico modelo de Bower [3] de aprendizagem por pares associados. Neste modelo, uma lista de estı́mulos é apresentada a um paciente em ordem
aleatória. Os estı́mulos podem ser palavras, números, sı́labas sem nexo, figuras ou ı́tens
similares. A cada estı́mulo corresponde uma resposta correta que se supões que o paciente
aprenda. Antes que a experiência comece realmente, o paciente pode ser informado de
algum modo sobre o conjunto das respostas ou pode tomar cinhecimento delas gradulamente no decorrer da experiência.
A experiência consiste em apresentar ao paciente um estı́mulo de cada vez, durante um breve perı́odo de tempo, durante o qual solicita-se ao paciente tentar indicar a
resposta correta. Após o paciente ter dado sua resposta, mostra-se a ele a resposta correta. Isso serve como uma confirmação de uma resposta correta ou como uma correção de
uma resposta incorreta. Depois de apresentada toda a lista de estı́mulos, ela é novamente
apresentada, porém em ordem aleatória diferente da anterior.
Na situação experimental modelada por Bower os estı́mulos consistiam em 10
pares de consoantes, enquanto as respostas eram os números 1 e 2. A cada par de consoantes atribuı́a-se aleatoriamente um desses números como resposta, antes do inı́cio da
experiência. Os estı́mulos eram apresentados e pedia-se que o paciente para responder
1 ou 2. Após dar sua resposta, o paciente era informado da resposta correta ao estı́mulo
apresentado. Depois de exibidos os 10 pares de consoantes (constituindo um ensaio)
os 10 cartões com estı́mulos eram baralhados e novamente apresentados ao paciente.
Esse processo era repetido até que o paciente coseguisse passar sem erros pela lista de
estı́mulos, por duas vezes consecutivas. Ao acontecer isso, considerava-se que o paciente
tinha aprendido as respostas corretas.
Para analisar esse tipo de experiência utilizando cadeias de Markov, considera-se
os seguintes axiomas:
1. Cada par estı́mulo-resposta encontra-se em um estado dentre dois possı́veis, em
qualquer ensaio n: condicionado (C(n)) ou palpite (P (n)). O estado de condicionamento do par estı́mulo-resposta corresponde ao paciente ter aprendido o par.
Caso contrário, o paciente estará simplesmente adivinhando.
2. Em qualquer ensaio n, a probabilidade de transição de P (n) para C(n + 1) é uma
constante c(0 ≤ c ≤ 1); segue que a probabilidade de uma transição de P (n) para
P (n + 1) é 1 − c.
3. Em qualquer ensaio n, a probabilidade de transição de C(n) para C(n + 1) é 1;
segue que a probabilidade de uma transição de C(n) para P (n + 1) é 0.
4. Se estiver em P (n), em qualquer ensaio n, a probabilidade de sucesso S(n) (resposta correta ao estı́mulo) é 1/N , onde N ó número total de respostas possı́veis.
5. Cada ı́tem está no estado não condicionado (palpite) no ensaio inicial.
Numa primeira modelagem, considere uma cadeia de Markov com dois estados:
condicionado (1) e palpite (2). De acordo com o axioma 5, a distribuição inicial é então:
sT =
0.00 1.00
.
Pelos axiomas 2 e 5, a matriz de transiçao inicial da cadeia de Markov é:
P =
1.00 0.00
c 1−c
.
(2)
Fazendo c = 0.30 na equação 2, tem-se:
P =
1.00 0.00
0.30 0.70
.
Calcula-se algumas potências da matriz P (com precisão igual a 2):
5
P =
1.00 0.00
0.83 0.17
15
,P
=
1.00 0.00
1.00 0.0047
,P
100
=
1.00
0.00
1.00 0.32.10−15
.
Calcula-se a distribuição da cadeia de Markov nos diversos ensaios realizados:
s(1) = s(0)P1 =
s(10) = s(0)P10 =
0.30 0.70
0.97 0.028
, s(5) = s(0)P5 =
, s(15) = s(0)P15 =
,
1.00 0.0047
0.83 0.17
,....
Observa-se que os resultados obtidos indicam, por exemplo, que no tempo 10 (ou
seja, logo após o décimo ensaio), há uma probabilidade de aproximadamente 97% de um
paciente sob teste estar no estado condicionado. Já no tempo 15 há uma probabilidade
virtual (pois o valor 1 está sujeito há erros de arredondamento) de 100% de um paciente
estar no estado condicionado.
Refina-se agora o modelo, considerando-o como uma cadeia de Markov com três
estados: condicionado (1), palpite errado (2) e palpite certo (3). Para determinar a matriz
de transição da cadeia de Markov correpondente utiliza-se o axioma 4, juntamente com
os outros axiomas. Assim, tem-se que p11 = 1, p12 = 0, p13 = 0, p21 = c, p31 = c.
Para calcular p23 , sejam Gn+1 o evento “o paciente tenta adivinhar no ensaio n +
1”, Sn+1 o evento “o paciente responde corretamente no ensaio n + 1” e Tn o evento “o
paciente faz um palpite errado no ensaio n”. Se P r(x) denota a probabilidade de x e
P r(x|y) denota a probabilidade condicional de x dado que y tenha ocorrido, tem-se que:
p23 = P r(Sn+1 ∩ Gn+1 |Tn ) = P r(Sn+1 |Gn+1 ∩ Tn )P r(Gn+1 |Tn ).
(3)
Pelo axioma 2, tem-se que P r(Gn+1 |Tn ) = 1 − c, e, pelo axioma 4, é válido
que P r(Sn+1 |Gn+1 ∩ Tn ) = 1/N , onde N é o número total de respostas possı́veis. Da
equação 3, segue que:
p23 =
1
(1 − c)
N
.
De forma análoga, conclui-se que:
p22 = (1 −
1
1
1
)(1 − c), p32 = (1 − )(1 − c), p33 = (1 − c).
N
N
N
Assim, a matriz de transição dessa cadeia de Markov é

1.00
0.00
P =  c (1 − N1 )(1 − c)
c (1 − N1 )(1 − c)

0.00
1
(1 − c)  ,
N
1
(1 − c)
N
(4)
que é uma cadeia absorvente, com o estado 1 absorvente e os estados 2 e 3 não absorventes.
Os axiomas 4 e 5 implicam que a distribuição inicial dessa cadeia é:
0.00 1 −
s(0) =
1
N
1
N
.
Sejam c = 0.30 e N = 4. Então a equação 4 torna-se (com precisão igual a 3):


1.000 0.000 0.000
P =  0.30 0.525 0.175 
0.30 0.525 0.175
0.000 0.750 0.250 .
e a distribuição inicial é s(0) =
Calcula-se a distribuição da cadeia em vários tempos, obtendo-se, por exemplo:
s(2) =
0.510 0.368 0.123
s(30) =
, s(15)
1.000 0.169.10−4
0.995 0.356 0.119.10−2
0.563.10−5 , . . .
,
Observa-se que, no trigésimo ensaio, é virtualmente certo que (a incerteza é devido
aos erros de arredondamento) que o paciente esteja no estado condicionado.
Uma importante questão é saber qual o número de vezes em que o paciente se
encontra no estado 2, ou seja, o número de respostas incorretas dadas pelo paciente ao
par estimulo-resposta em questão. Em [19] há a prova de que o número de vezes que o
paciente se encontra nos estados 2 ou 3 é finito, isto é, eventualmente ele estará no estado
condicionado.
Observe que a matriz canônica dessa cadeia de Markov é:

0.000 0.000
0.525 0.175 
0.525 0.175

1.000
∗

P =
0.300
0.300
onde
Px→x =
0.525 0.175
0.525 0.175
Px→a =
0.300
0.300
,
.
O número médios esperado de vezes em que o paciente se encontra no estado 2
ou 3 é dado por
0.750 0.250
F.
Tem-se que
I − Px→x =
1.000 0.000
0.000 1.000
0.525 0.175
0.525 0.175
=
0.475 −0.175
−0.525 0.825
,
e, portanto,
=
2.750 0.583
1.750 1.583
F =
2.500 0.833
−1
F = [I − Px→x ]
.
Consequentemente, tem-se que
0.750 0.250
,
o que significa que, por exemplo, o número esperado de respostas incorretas dadas pelo
paciente ao ı́tem em questão é 2.5. Além disso, tem-se que a matriz de probabilidade de
absorção é dada por:
A = F Px→a =
1.000
1.000
,
significando que, desconsiderando os erros de arredondamento, há 100% de probabilidade
de que o paciente venha a estar no estado condicionado eventualmente.
3. Modelos de Markov Ocultos
Em alguns casos existe a possibilidade de que se tenha uma descrição incompleta do
ambiente em que ocorre um processo Markoviano, onde o espaço de estados é desconhecido. Nestes casos, é possı́vel definir um modelo de Markov considerando uma
aproximação desse espaço. Modelos deste tipo são denominados Modelos de Markov
Ocultos (HMM) [15]. Esta seção apresenta uma discussão sobre esses modelos,
3.1. Conceitos Básicos
Definição 6 Um Modelos de Markov Ocultos (HMM) é uma tripla M = (s, P, B), onde
consideram-se:
(i) Um conjunto especı́fico Ok de observações do tipo k que resultam de um experimento;
(ii) Um conjunto X de estados xi , onde em cada estado xi é possı́vel realizar uma
observação bi (k), com i = 1, . . . , N e k ∈ Ok ;
(iii) Uma distribuição de probabilidade para o estado inicial dada pelo vetor s = [si ],
onde si = P r(xi (0));
(iv) Uma distribuição de probabilidade para as transições de estados dada pela matriz
P = [pij ], onde pij = P r(xj (t + 1)|xi (t));
(v) Uma distribuição de probabilidade para as observações em cada estado dada pela
matriz B = [bj (k)], onde bj (k) = P r(Ok |xj ).
p 11
x begin
p begin-1
p 12
x1
b 1 (m)
b 1 (n)
p 22
x2
p 21
p 2-end
x end
b 2 (m)
b 2 (n)
Figura 2: Diagrama de transições de estados de um modelo de Markov oculto
de dois estados não terminais, onde há a probabilidade de emissão de
dois sı́mbolos (m e n).
Pode-se pensar nesse tipo de modelo como um autômato finito (não determinı́stico) com saı́da [9], cujas transiçoes são vazias e probabilı́sticas, sendo que, em
cada estado poderá haver a emissão de sı́mbolos (ı́tens observáveis) segundo uma certa
probabilidade.
Exemplo 2 Os modelos ocultos podem ser representados como diagramas de estados, como, por exemplo, o modelo oculto com conjunto de estados X = {xbegin , x1 ,
x2 , xend } da Figura 2, onde somente os estados não terminais x1 e x2 emitem os simbolos
(ı́tens observáveis) m e n.
Simulando um experimento, a partir do estado x1 é possı́vel ir para o outro estado
x2 ou não, de acordo com as probabilidades de transição p12 ou P11 , respectivamente. O
mesmo acontece no estado x2 . Segue-se assim sucessivamente, até atingir o estado final.
Em cada estado não terminal observa-se a emissão do sı́mbolo m ou m, de acordo
com as probabilidades de emissão do sı́mbolo m ou n no estado x1 (b1 (m), b1 (n)) e no
estado x2 (b2 (m), b2 (n)).
Como resultado, obtém-se uma seqüencia oculta (que não é observada) de estados
percorridos e um seqüência de sı́mbolos (que é observada). Uma seqüência de sı́mbolos
que pode ser observada, por exemplo, é O = m, n, m; uma seqüência possı́vel de estados
ocultos é I = xbegin , x1 , x1 , x2 , xend . A probabilidade do modelo percorrer os estado de
I para produzir a seqüência de observações O é dada por:
P r(O, I|M ) = pbegin−1 · b1 (m) · p11 · b1 (n) · p12 · b2 (m) · p2−end .
Assim, dada uma seqüência de observações, não se conhece a seqüência de estados pela qual passa o modelo, mas somente uma função probabilı́stica deste caminho.
Exemplo 3 Um exemplo extraido de [2] consiste no modelo das urnas. Suponha que
exitem N urnas contendo L bolas coloridas (preto, branco e cinza). Uma pessoa inicia
por uma das urnas, retira uma bola e observa a sua cor, recoloca-a na urna, e vai para
outra urna ou permanece na mesma urna, com uma certa probabilidade, e toma outra
bola, e assim sucessivamente. O processo termina após W seqüencias de passos deste
tipo.
Considere uma configuração especı́fica de N = 2 urnas e um tempo de
observação W = 3, como mostra a Figura 3, e uma distribuição de probabilidade dada
por:
Estado 1
.8
.7
.2
.1
Estado 2
.9
.3
t=1
t=2
t=3
Figura 3: Esquema do experimento com o modelo de urna com 2 estados em 3
fases de tempo.
s=
0.7
0.3
.
A matriz B define as probabilidades das possı́veis observações para cada estado:
b1 (Branco) b1 (P reto) b1 (Cinza)
0.1 0.4 0.5
B=
=
.
b2 (Branco) b2 (P reto) b2 (Cinza)
0.6 0.2 0.2
A matriz das probabilidades de transição de estado é dada por:
P =
0.8 0.2
0.1 0.9
.
A Figura 3 mostra um esquema do experimento. O modelo está representado
na Figura 4. O algoritmo dado na Tabela 4 é utilizado para gerar as seqüências de
observações. Salienta-se que a seqüência mais provável é O = {Cinza, Cinza, Cinza}.
Isto ocorre porque o estado inicial mais provável é o Estado 1 (urna 1), Cinza é a cor
mais provável de ser observada no Estado 1, e, a partir do Estado 1, o estado mais
provável é ainda o Estado 1. A probabilidade de ocorrer esta seqüência dada a seqüência
I = {Estado1, Estado1, Estado1} de estados é calculada então como:
P r(O, I|M ) = s1 · b1 (cinza) · p11 · b1 (cinza) · p11 · b2 (cinza) = 0.056.
Exemplo 4 Considere um jogo de cara de cara (h) ou coroa (t) no qual sabe-se que o
lançador pode utilizar duas moedas, uma normal e uma viciada. A moeda normal oferece probabilidade de 50% tanto para cara como para coroa, enquanto a moeda viciada
oferece 75% de chance para cara e apenas 25% para coroa.
Sabe-se também o lançador pode iniciar o processo escolhendo qualquer uma das
moedas com igual probabilidade, entretanto, uma vez tendo utilizado uma das moedas
(normal ou viciada) a probabilidade de que o lançador a troque por outra é de apenas
20%.
.8
.1
.2
.3
.7
.9
branco = .1
preto = .4
cinza = .5
branco = .1
preto = .4
cinza = .5
Estado 1
Estado 2
Figura 4: Modelo de urna com 2 estados.
Tabela 4: Algoritmo gerador de seqüências de observações.
t = 1
Escolha um estado inicial utilizando s
Enquanto t <= W :
Escolha uma observação O utilizando B
Escolha um novo estado utilizando P
t = t + 1
O modelo está representado na Figura 5. Tem-se então o conjunto de observações
O = {h, t}, o conjunto de estados X = {N = normal, V = viciada}, a matriz B das
possı́veis observações para cada estado:
B=
bN (h) = 0.50 bN (t) = 0.50
bV (h) = 0.75 bV (t) = 0.25
a matriz de transição:
P =
0.8 0.2
0.2 0.8
e a distribuição inicial:
s=
0.5
0.5
.
Observe que, neste caso, é mais difı́cil descobrir qual a seqüência mais
provável observada em um dado experimento. Considere então uma dada seqüência de
observações O = {h, h, t, t}. Em princı́pio não sabe-se a seqüência de estados que a gerou. Entretanto, considerando uma dada seqüência de estados (por exemplo, a seqüência
I = {N, N, V, N }), é possı́vel estimar qual a probabilidade da seqüência O ter sido
gerada pelo modelo a partir desse caminho de estados:
P r(O, I|M ) = sN · bN (h) · pN N · bN (h) · pN V · bV (t) · pV N · bN (h) = 0, 0005.
.2
.8
.8
N = .5
b N (h) = .5
b N (t) = .5
V = .5
0.2
b V(h) = .75
b V(h) = .25
Figura 5: Modelo das moedas.
3.2. A Probabilidade de uma Seqüência de Observações
Uma discussão interessante, que pode ser feita a partir da análise dos exemplos 2, 3 e 4,
é o problema relacionado à descoberta da probabilidade de que uma dada seqüência
de observações O tenha sido gerada por M . Para calcular a probabilidade de que
tal seqüência venha a ser observada, deve-se considerar a soma das probabilidades da
geração dessa seqüência sobre todos os possı́veis caminhos que a geram. Assim, seja
I = x1 , x2 , . . . , xW uma seqüência particular de estados possı́vel em W passos e considere a expansão de P r(O|M ) em todos os estados, dada por:
P r(O|M ) =
X
P r(O, I|M ).
(5)
∀I
Para qualquer seqüência individual de estados, pode-se usar a regra de Bayes na
equação 5, obtendo:
P r(O, I|M ) = P r(O|I, M )P r(I, M ).
(6)
O primeiro termo do lado direito da equação 6, P r(O|I, M ), é a probabilidade de
se ver uma dada seqüência de observações, considerando um dado conjunto de estados.
Para os estados conhecidos, considerando Ok , o cálculo é realizado como:
P r(O|I, M ) =
Y
bj (k).
j∈I
O segundo termo do lado direito da equação 6 é dado pelo produto da probabilidade de iniciar no estado x1 e passar pelos estados x2 , . . . , xW :
P r(I|M ) = s1 p12 p23 . . . p(W −1)W .
Assim, a equação 5 pode ser escrita como:
P r(O, I|M ) = s1 b1 (k)
W
−1
Y
i=1
bi+1 (k)pi(i+1) .
(7)
Tabela 5: Algoritmo para computar P r(O|M ).
Versão Iterativa
Versão Recursiva
α1 = [si bi (1)]
Para t em {1, . . . , W − 1}:
αt+1 = P · [αit bi (t + 1)]
P
W
P r(O|M ) = N
i=1 αi
Defina α(W ):
se W == 1:
[si bi (1)]
senão:
P · [αiW −1 bi (W )]
P
W
P r(O|M ) = N
i=1 αi
Considerando um modelo onde se tem os estados distingüı́veis xbegin e xend (como
o modelo da Figura 2), então a equação 7, para W +2 passos, onde a sqüência é observada
nos estados não terminais, torna-se:
P r(O, I|M ) = pbegin−1
W
Y
bi (k)pi(i+1) ,
i=1
onde xW +1 = xend .
Uma crı́tica grave a esta formulação é que o custo computacional do somatório da
equação 5 é muito alto (da ordem N W ). Entretanto, é possı́vel usar resultados parciais,
que são acumulados em um vetor αt , conforme descrito no procedimento “forward” do
algoritmo da Tabela 5.
Exemplo 5 Considere o modelo das urnas apresentado no Exemplo 3. Define-se αit como
a probabilidade de acontecer a observação Ot no estado xi . Então, se
0.7
0.5
s=
e B(Cinza) =
,
0.3
0.2
tem-se que o vetor inicial α1 é dado por:
1
α = [si bi (1)] =
s1 b1 (Cinza)
s2 b2 (Cinza)
=
0.35
0.06
Sucessivamente, calcula-se:
α2 = P [αi1 bi (2)]
0.8 0.2
=
0.1 0.9
0.8 0.2
=
0.1 0.9
0.142
=
0.0283
α11 b1 (Cinza)
α21 b2 (Cinza)
0.175
0.012
.
e
α3 = P [αi2 bi (3)]
0.8 0.2
=
0.1 0.9
0.8 0.2
=
0.1 0.9
.0581
=
.
.0122
α12 b1 (Cinza)
α22 b2 (Cinza)
.0712
.00566
Finalmente, a probabilidade de ver a seqüência Cinza,Cinza,Cinza é dada por:
P r(O|M ) =
N
X
i=1
αiW
=
2
X
αi3 = 0.0703.
i=1
Exemplo 6 Considere o modelo das moedas apresentado no Exemplo 4. Define-se αit
como a probabilidade de acontecer a observação Ot no estado xi . Então, se
0.5
0.5
s=
e B(h) =
,
0.5
0.75
tem-se que o vetor inicial α1 é dado por:
s1 b1 (h)
0.25
1
α = [si bi (1)] =
=
.
s2 b2 (h)
0.375
Sucessivamente, calcula-se:
α2 = P [αi1 bi (2)]
1
0.8 0.2
α1 b1 (h)
=
α1 b2 (h)
0.1 0.9
2
0.8 0.2
0.125
=
0.2 0.8
0.281
0.156
=
0.250
e
α3 = P [αi2 bi (3)]
0.8 0.2
=
0.2 0.8
0.8 0.2
=
0.2 0.8
.0750
=
,
.0656
α12 b1 (t)
α22 b2 (t)
.0781
.0625
α4 = P [αi3 bi (4)]
0.8 0.2
=
0.2 0.8
0.8 0.2
=
0.2 0.8
.0333
=
.
.0206
α13 b1 (t)
α23 b2 (t)
.0375
.0164
Finalmente, a probabilidade de ver a seqüência h,h,t,t é dada por:
P r(O|M ) =
N
X
i=1
αiW
=
2
X
αi4 = 0.0539.
i=1
3.3. Caminho Gerador Ótimo
Outra questão fundamental é, dada um seqüência de observações O, descobrir a seqüência
de estados I mais provável, que seja capaz de gerar O. Um critério simples para tratar
este problema é considerar a seqüência que torna cada um dos estados o mais provável2 .
Observa-se que, de forma análoga ao procedimento dado no algoritmo da Tabela 5,
é possı́vel definir um procedimento “backward”, através de um vetor β(t) que registra a
probabilidade de alcançar um dos estados finais, dado um determinado estado corrente.
Este vetor β(t) pode ser utilizado para definir um algoritmo para prever a probabilidade
de seqüências de estados de forma análoga ao algoritmo da Tabela 5.
Seja γit a probabilidade de terminar no estado xi no tempo t, dada a seqüência de
observações O, calculada como:
γit = P r(xi (t) = si |O, M ).
(8)
Em 8, pode-se utilizar os vetores α(t) e β(t) para expressar γit , obtendo:
[αit βit ]
,
P r(O|M )
P
t
onde P r(O|M ) é um fator de normalização tal que N
i=1 γi = 1.
γt =
(9)
Dado γ t , os estados mais prováveis são expressados pelos seus ı́ndices, como:
indext = ı́ndice do max1≤i≤N {γit }.
Para computar a equação 9, pode-se utilizar o algoritmo de Viterbi, onde, para
registrar os estados mais prováveis, define-se um vetor r(t), como mostra o algoritmo
dado na Tabela 6.
2
Pode acontecer que não exista um caminho entre estados sucessores, mas isto geralmente não ocorre
na prática.
Tabela 6: Algoritmo para computar o caminho gerador ótimo.
Vesão Iterativa
Versão Recursiva
γ 1 = [si bi (1)]
Defina r(W):
r(1) = [index1 ]
Se W == 1:
Para t em {1, . . . , W − 1}:
γ 1 = [si bi (1)]
t+1
t
γ
= P · [γi bi (t + 1)]
r(1) = [index1 ]
r(t + 1) = anexe(indext+1 , r(t))
Senão:
γ W = P · [γiW −1 bi (W )]
r(W ) = anexe(indexW , r(W − 1))
Exemplo 7 Considerando o modelo das urnas trabalhado nos Exemplos 3 e 5, dada a
seqüência de observações O = {Cinza, Cinza, Cinza}, pode-se calcular a seqüência
de estados mais provável para produzı́-la. Primeiramente, calcula-se:
1
γ = [si bi (1)] =
s1 b1 (Cinza)
s2 b2 (Cinza)
.35
.06
=
,
onde max1≤i≤N {γi1 } = .35, logo index1 = 1(x1 (1)), e, portanto,
r(1) = [index1 ] =
1(x1 (1)) .... ....
.
Calcula-se sucessivamente:
γ 2 = P [γi1 bi (2)]
.8 .2
=
.1 .9
.8 .2
=
.1 .9
.142
=
,
.0283
γ11 b1 (Cinza)
γ21 b2 (Cinza)
.175
.012
onde max1≤i≤N {γi2 } = .142, logo index2 = 1(x1 (2)), e, portanto,
r(2) =
1(x1 (1)) 1(x1 (2)) ....
γ 3 = P [δi2 bi (3)]
;
γ12 b1 (Cinza)
=
γ 2 b2 (Cinza)
2
.8 .2
.0712
=
.1 .9
.00566
0.0581
=
,
0.0122
.8 .2
.1 .9
onde max1≤i≤N {γi3 } = .0581, index3 = 1(x1 (3)), e, portanto,
r(3) =
1(x1 (1)) 1(x1 (2)) 1(x1 (3))
.
Logo o caminho gerador ótimo da sequência cinza,cinza,cinza é x1 , x1 , x1 , como
era esperado.
Exemplo 8 Considerando o modelo das moedas trabalhado nos Exemplos 4 e 6, dada a
seqüência de observações O = {h, h, t, t}, pode-se calcular a seqüência de estados mais
provável para produzı́-la. Primeiramente, calcula-se:
1
γ = [si bi (1)] =
s1 b1 (h)
s2 b2 (h)
=
.25
.675
,
onde max1≤i≤2 {γi1 } = .675, logo index1 = 2(x2 (1)), e, portanto,
r(1) = [index1 ] =
2(x2 (1)) .... ....
.
Calcula-se sucessivamente:
γ 2 = P [γi1 bi (2)]
.8 .2
=
.2 .8
.8 .2
=
.2 .8
.156
=
,
.250
γ11 b1 (h)
γ21 b2 (h)
.125
.281
onde max1≤i≤2 {γi2 } = .250, logo index2 = 2(x2 (2)), e, portanto,
r(2) =
2(x2 (1)) 2(x2 (2)) ....
γ 3 = P [γi2 bi (3)]
;
γ12 b1 (t)
=
γ 2 b2 (t)
2
.8 .2
.0781
=
.2 .8
.0625
0.0750
=
,
0.0656
.8 .2
.2 .8
onde max1≤i≤2 {γi3 } = .075, index3 = 1(x1 (3)), e, portanto,
r(3) =
2(x2 (1)) 2(x2 (2)) 1(x1 (3))
γ 4 = P [γi3 bi (4)]
.8 .2
=
.2 .8
.8 .2
=
.2 .8
0.0333
=
,
0.0206
;
γ13 b1 (t)
γ23 b2 (t)
.0375
.0164
onde max1≤i≤2 {γi4 } = .0333, index4 = 1(x1 (4)), e, portanto,
r(4) =
2(x2 (1)) 2(x2 (2)) 1(x1 (3)) 1(x1 (4))
.
Logo o caminho gerador ótimo da sequência h,h,t,t é x2 , x2 , x1 , x1 .
3.4. Aperfeiçoando o Modelo
O principal problema em HMM é descobrir o melhor modelo M , o que é muito difı́cil e
não tem solução analı́tica conhecida. Pode-se derivar uma aproximação que é melhor que
a versão corrente. Este procedimento pode ser repetido até que nehuma melhoria possa
ser verificada.
Em linhas gerais, esta estratégia iniciará com um conjunto inicial M = (s, P, B)
e executar o modelo um número suficiente de vezes para estimar um novo conjunto de
parâmetros M 0 = (s0 , P 0 , B 0 ). Estas estimativas são então utilizadas como o novo modelo,
e, então, o processo é repetido.
As estimativas de s e B são simples de calcular:
s0 = γ t
(10)
e
PW
0
bj (k) =
t
t=1,Ot =k γj
PW t .
t=1 γj
(11)
Tabela 7: Algoritmo de Baum-Welch.
Repita os seguintes passos até que os
parâmetros do modelo estejam de acordo
com a tolerância considerada:
Estimar s utilizando a equação 10
Estimar B utilizando a equação 11
Estimar P utilizando a equação 12
Para estimar pij , calcula-se ηij como:
ηij = P r(xi (t) = si , xi (t + 1) = sj |), M )
resultando em
ηij =
αit pij bj (t + 1)βjt+1
,
P r(O|M )
de tal forma que a estimativa pode ser obtida como uma média ao longo do tempo:
p0ij
PW
= Pt=1
W
ηij
t
t=1 γj
.
(12)
A Tabela 7 apresenta o algoritmo de Baum-Welch para aperfeiçoamento do modelo pelo cálculo sucessivo de estimativas para os parâmetros.
Referências
[1] J. F. F. Araújo, G. P. Dimuro, M. A. Campos, “Probabilidades Intervalares com Aplicações no Maple”, ESIN/UCPel, Pelotas, RS, 2001.
(http://gmc.ucpel.tche.br/fmc)
[2] D. H. Ballard, “An Introduction to Natural Computation”, MIT Press, Cambridge, 1997.
[3] G. H. Bower, Applications of a Model to Paired-Associate Learning, “Psychometrika”,
Vol. 26, pp. 225-2380, 1961,
[4] H. Bunke, T. Caelli (Eds), “Hidden Markov Models Applied in Computer Vision”, in Machine Perception and Artificial Intelligence, Vol. 45, World Scientific, N. J., 2001.
[5] M. A. Campos, “Uma Extensão Intervalar para a Probabilidade Real”, Tese de Doutorado,
Centro de Informática/UFPE, 1997.
[6] M. A. Campos, Interval probabilities, application to discrete ramdom variables, “Seleta
do XXII CNMAC” (E.X.L. de Andrade, J. M. Balthazar, S. M. Gomes, G. N. Silva,
A. Sri Langa, eds.), TEMA, Vol. 1.2, pp. 333-344, SBMAC, 2000.
[7] M. A. Campos, G. P. Dimuro, A. C. R. Costa, J. F. F. Araujo, A. M. Dias, “Probabilidade
Intervalar e Cadeias de Markov Intervalares no Maple”, “Seleta do XXIV CNMAC”
(E.X.L. de Andrade, J. M. Balthazar, S. M. Gomes, G. N. Silva, A. Sri Langa, eds.),
TEMA, SBMAC, 2002.
[8] A. M. Dias, G. P. Dimuro, “Matemática Intervalar com Aplicações no Maple”,
ESIN/UCPel, Pelotas, 2000. (http://gmc.ucpel.tche.br/mat-int)
[9] J. Hopcroft and J. D. Ullman, “Introduction to Automata Theory, Languages and Computation”, Addison-Wesley, Reading, 1979).
[10] U. W. Kulisch, W. L. Miranker, “Computer Arithmetic in Theory and Practice”, Academic
Press, New York, 1981.
[11] H. E. Kyburg, Jr., Interval-valued Probabilities, http://www.ensmain.rug.ac.be/ ipp.
[12] M. B. Monagan, K. O. Geddes, K. M. Heal, G. Labahn, and S. M. Vorkoetter, “Maple V:
Program. Guide”, Springer, N. York, 1998.
[13] R. E. Moore,“Methods and Applications of Interval Analysis”, SIAM, Philadelphia, 1979.
[14] A. Neumaier, “Interval Methods for Systems of Equations”, Cambridge University Press,
Cambridge, 1990.
[15] L. R. Rabiner and B. H. Juang, An Introduction to Hidden Markov Models, “IEEE ASSP
Magazine”, 3(4):4-16, 1986.
[16] B. Tessem, Interval Probability Propagation, “International Journal of Approximate Reasoning”, 7:95-120, 1992.
[17] K. S. Trivedi, “Probability and Statistics with Reliability, Queuing, and Computer Science
Applications”, Prentice-Hall, Englewood Cliffs, NJ, 2000.
[18] K. Weichselberger, Axiomatic foundations of the theory of interval-probability, “Symposia Gaussiana”, Conference B: Statistical Sciences, pp. 47-64, Munich, Germany,
August 2-7, 1993.
[19] W. Yoselogff, “Finite Mathematics”, Worth Publishing, New York, 1975.
[20] I. O. Kozine and L. V. Utkin, Interval-Valued Finite Markov Chains, “Reliable Computing”, 8(2): 97-113, 2002.