slides do seminário I

Cadê o
Markov?
Andrei Andreyevich Markov, Célebre matemático Russo
(1856 – 1922)
Artigo que publicou acerca de um de seus primeiros temas de pesquisa:
А. А. Марков. "Распространение закона больших чисел на величины, зависящие друг от
друга". "Известия Физико-математического общества при Казанском университете", 2я серия, том 15, ст. 135–156, 1906.
(hein?)
MC ( Markov Chain)
(1909)
•
•
~ 50 anos
HMM (Hidden Markov Model)
(Final dos anos 50)
Os algoritmos de recursão utilizados no ajuste de um HMM, bem como cálculos de
probabilidades marginais foram descritos pela primeira vez por Ruslan L. Stratonovich,
no final dos anos 1950 (artigos publicados em em russo).
Os HMM foram posteriormente descritos por Leonard E. Baum e outros autores, na
segunda metade da década de 1960.
MC
1913 – Markov aplicou seu modelo a textos escritos em
Russo (de autoria do escritos Pushkin.
1917 - Erlang usou MC para obter fórmulas (modelos)
para o tempo de espera de chamadas em redes
telefônicas.
…
Física
Química
Informática (o ranqueamento de páginas usado pela
Google é definido como uma Cadeia de Markov)
Economia
Ciências Sociais
Biologia
Genética
Jogos
Síntese e análise musical
Síntese e analise de textos
...
HMM
1970 - reconhecimento de voz (1970)
1980 - análise de sequências biológicas (DNA) 1980
…
Análise criptográfica
Síntese e análise de voz
Síntese e análise de escrita cursiva
Tradução automática
Genética
Alinhamento de sequências
Análise de séries temporais (em financas, por exemplo)
…
Nossa abordagem dos modelos de MARKOV: UM PET VIRTUAL
Primeiro um MC para os estados do bichinho
p(1,1)
Com fome
(estado 1)
Transições:
 p (1,1)
p =  p (2,1)
 p (3,1)
Iniciais:
p (1, 2)
p(2, 2)
p (3, 2)
p (1,3) 
p(2,3) 
p (3,3) 
 p0(1) 
p0 =  p0(2) 
 p0(3) 
p(2,2)
p(1,2)
p(2,1)
Com sono
(estado 2)
p(2,3)
Brincalhão
(estado 3)
p(3,3)
Mãos à massa!
Mas... por onde começar?
R: por uma boa calculadora científica → SCILAB (www.scilab.org)
E depois?
R: Simular uma fonte aleatória de símbolos (usando um gerador pseudo-aleatório)
• Primeiro, simular um dado honesto
evento = ['face 1' 'face 2' 'face 3' 'face 4' 'face 5' 'face 6']; // Definição do conjunto de
// eventos elementares
p=[1/6 1/6 1/6 1/6 1/6 1/6 ];
// Massa de probabilidade do dado honesto
for i=1:length(p),
F(i)=sum(p(1:i));
// Probabilidade acumulada (CDF)
end,
x=rand(1,1);
// Gera um número pseudo aleatório entre 0 e 1 (dist. Uniforme)
pos=find((x-F)<0);
clf; titlepage(evento(pos(1)));
// Mostra o evento sorteado aleatoriamente
• Depois, um dado viciado
p=[1/6 2/6 0.5/6 0.5/6 1/6 1/6 ]; // Massa de probabilidade do dado viciado
// (em qual face você apostaria?)
E o resto do código? → Que tal “empacotar” isso numa função (computacional)?
function [s]=gerador(evento,p)
for i=1:length(p),
F(i)=sum(p(1:i));
end,
x=rand(1,1);
pos=find((x-F)<0);
s=evento(pos(1));
endfunction
// Probabilidade acumulada (CDF)
// Gera um número pseudo aleatório entre 0 e 1 (dist. Uniforme)
Entenda e guarde por perto esta rotina computacional, pois ela será usada muitas vezes nos MC e
HMM que serão construídos.
• Checando as frequências relativas esperadas:
for i=1:1000,
[s(i)]=gerador(evento,p);
end
sum(s=='face 2')/1000 // Devemos encontrar aprox. 2/6
Iniciando a montagem do PET VIRTUAL – Primeiro uma MC para gerar os estados
de “comportamento” do bichinho:
estado=['Com fome' 'Com sono' 'Brincalhão'];
p = [0.30 0.50 0.20
0.01 0.89 0.10
0.50 0.20 0.30]; // Cada linha é uma Massa de Probabilidades (soma sempre igual a 1)
p0 = [0; 0; 1];
estadoAtual=gerador(estado,p0');
clf; titlepage(estadoAtual);
indiceEstado=find(estado==estadoAtual);
xpause(1.5*10^6); // Pausa de 1.5 segundos
for i=1:20,
indiceEstado=find(estado==estadoAtual);
massaProb=p(indiceEstado,:);
estadoAtual=gerador(estado,massaProb);
clf; titlepage(estadoAtual);
xpause(1.5*10^6); // Pausa de 1.5 segundos
end
p(1,1)
Com fome
(estado 1)
p(2,2)
p(1,2)
p(2,1)
Com sono
(estado 2)
p(2,3)
Brincalhão
(estado 3)
p(3,3)
Completando o PET VIRTUAL – Um HMM gera o “comportamento” do bichinho a
partir de estados que não podemos ver (estados escondidos)
Prob. De observações,
dados os estados:
 o(1,1) o(1, 2) o(1,3) o(1, 4) 
o =  o(2,1) o(2, 2) o(2,3) o(2, 4) 
 o(3,1) o(3, 2) o(3,3) o(3, 4) 
obs=['Alegre' 'Triste' 'Com raiva' 'Doente'];
o = [0.5 0.4 0.1 0.0
0.7 0.0 0.1 0.2
0.0 0.0 0.1 0.9]; // Cada linha é uma Massa de Probabilidades (soma sempre igual a 1)
// Início:
estadoAtual=gerador(estado,p0');
// Emissão de observação a partir do estado (escondido):
indiceEstado=find(estado==estadoAtual);
massaProb=o(indiceEstado,:);
emissao=gerador(obs,massaProb);
clf; titlepage(emissao);
xpause(10^6); // Pausa de 1 segundo
for i=1:20
// Transição (ou não) de estado:
indiceEstado=find(estado==estadoAtual);
massaProb=p(indiceEstado,:);
estadoAtual=gerador(estado,massaProb);
// Emissão de observação a partir do estado (escondido):
massaProb=o(indiceEstado,:);
emissao=gerador(obs,massaProb);
clf; titlepage(emissao);
// xtitle(estadoAtual); // Descomente esta linha para ver também o estado oculto do processo.
xpause(1.5*10^6); // Pausa de 1.5 segundo
end
A SEGUIR (próximos seminários BioChaves):
→ HMM com observações discretas (densidades de probabilidades no lugar de massas de prob.)
Além dos PETS VIRTUAIS, usaremos como ilustração o
processo de decodificação de intenção de escrita em
teclados virtuais (sem 'apertar' pelo deslizar de dedos) →
Tarefa: 'escrever' M A R K O V
Y deslizando o mouse
X
M:
A:
R:
K:
O:
V:
X
233
63
130
246
259
155
Y
40
63
92
64
90
39
→ Como estimar as probabilidades (e densidades) do HMM quando só temos acesso às
observações?
(estes slides serão disponibilizados para download em http://www.biochaves.com/ )