Cadeia de Markov - People.csail.mit.edu

Transcrição

Processos Markovianos –
Introdução e Aplicações
Autores: Pedro Santana (04/35619)
Yasmin Mendes (03/91158)
Disciplina:
Automação
Controle para
Prof.:
Dr. João Yoshiyuki
Sumário
1.
2.
3.
4.
5.
6.
7.
8.
9.
Processos Estocásticos
Processos Markovianos
Cadeias de Markov
Equações de Chapman-Kolmogorov
Classificação de Estados em Cadeias de Markov
Probabilidades de Estados Estavéis (SteadyState)
Exemplos e Aplicações de Cadeias de Markov
Aplicações da Teoria de Cadeias de Markov
Fontes Consultadas
Processos Estocásticos
Processos Estocásticos: Definição
Processo Determinístico
Evolução do estado totalmente
previsível.
Processo Estocástico
Estado governado por funções de
distribuição de probabilidades.
Estocástico
Determinístico
Processo Estocástico
Coleção de variáveis randômicas X(t);
X(t) representa uma característica
mensurável (estado do sistema) de
interesse no parâmetro (geralmente
tempo) t;
Portanto, pode-se afirmar que X(t) é
definido em um espaço denominado
Espaço de Estados.
Processos Estocásticos: Classificação
Em relação ao estado
Estado Discreto (cadeia): X(t) é
definido sobre um conjunto enumerável
ou finito;
Estado Contínuo (seqüência): caso
contrário.
Em relação ao tempo (parâmetro)
Tempo Discreto: t é finito ou
enumerável;
Tempo Contínuo: caso contrário.
Exemplos
Número de usuários em uma fila de banco em
um determinado instante
Estado: Discreto;
Tempo: Contínuo.
Índice pluviométrico diário
Estado: Contínuo;
Tempo: Discreto.
Número de dias chuvosos
Estado: Discreto;
Tempo: Discreto.
Exemplos
Estado: Discreto;
Tempo: Contínuo.
Estado: Contínuo;
Tempo: Discreto.
Estado: Discreto;
Tempo: Discreto.
Exemplos
Estado: Discreto;
Tempo: Contínuo.
Estado: Contínuo;
Tempo: Discreto.
Estado: Discreto;
Tempo: Discreto.
Exemplos
Estado: Discreto;
Tempo: Contínuo.
Estado: Contínuo;
Tempo: Discreto.
Estado: Discreto;
Tempo: Discreto.
Exemplos
Estado: Discreto;
Tempo: Contínuo.
Estado: Contínuo;
Tempo: Discreto.
Estado: Discreto;
Tempo: Discreto.
Exemplos
Estado: Discreto;
Tempo: Contínuo.
Estado: Contínuo;
Tempo: Discreto.
Estado: Discreto;
Tempo: Discreto.
Exemplos
Estado: Discreto;
Tempo: Contínuo.
Estado: Contínuo;
Tempo: Discreto.
Estado: Discreto;
Tempo: Discreto.
Processos Markovianos
Processos Markovianos: Definição
Um Processo Estocástico é dito ser um
Processo Markoviano se o estado futuro
depende apenas do estado presente e
não dos estados passados.
Este tipo de Processo Estocástico é
também denominado de “memoryless
process” (processo sem memória), uma
vez que o passado é "esquecido"
(desprezado).
Processos Markovianos: Definição
Xn : estado atual;
Xn+1 : estado futuro;
xi : conjunto particular de valores das
variáveis aleatórias de estado ;
As probabilidades condicionais são
denominadas Probabilidades de Transição
Representam a probabilidade do estado Xn+1
ser x no instante n+1 dado que o estado é xn
no instante n.
Processos Markovianos: Exemplo
Prático
Contextualização:
Você é o engenheiro responsável pelo
planejamento de longo prazo de uma
grande empresa cuja produção tem, em
essência, três destinações principais:
Tabela 1 – Destinação
I
Militar
30%
II
Exportação
20%
III
Civil
50%
Prático
Para um intervalo de 10 anos, as
probabilidades de transição são estimadas
como segue:
Tabela 2 – Probabilidades de Transição
Entre Estados
para I
para II
para III
de I
0,8
0,1
0,1
de II
0,1
0,7
0,2
de III
0
0,1
0,9
Prático
Os valores da Tabela 1 podem ser dispostos em
um vetor x, denominado Vetor de Estados:
x = [I
II
III]
As probabilidades de cada Estado (probabilidade
não-condicional) podem também ser dispostos
em um vetor π, denominado Vetor de
Probabilidade de Estado (para distinguí-las das
probabilidades de transição).
Prático
Dado π(0) =[0.30 0.20 0.50] e P abaixo,
determine qual será a provável
participação de cada setor (militar, civil
ou exportação) na produção da empresa
daqui há 10 anos.
Prático
Solução: dado que P é a matriz de
transição de estado, o vetor de
probabilidade de estado para daqui a 10
anos (π(1)) é dado como abaixo:
Cadeias de Markov
Cadeias de Markov
Um Processo Markoviano é dito ser uma
Cadeia de Markov quando as variáveis
randômicas X(t) estão definidas em um
espaço de estados discreto E.
Exemplo: o exercício anterior.
Para o estudo de Sistemas a Eventos
Discretos (DES), vamos considerar
Cadeias de Markov de tempo discreto.
Cadeias de Markov de Tempo Discreto
As Probabilidades de Transição
P{X(k+1) = xk+1|X(k) = xk}
representam, portanto, a probabilidade
do estado X(k+1) ser xk+1 no tempo k+1
dado que o estado X(k) é xk no tempo k.
Cadeias de Markov Homogêneas
Se, para cada xk+1 e xk, tem-se:
P{X(k+1) = xk+1|X(k) = xk}=P{X(1) = x1|X(0) = x0},
a Cadeia é dita Homogênea. Assim, ter
uma Cadeia Homogênea implica que as
Probabilidades de Transição não mudam
ao longo do tempo.
Cadeias de Markov: Probabilidades de
Transição
A probabilidade de transição de Passo 1
é definida como segue:
pij = P{X(k +1) = j | X(k) = i}
De maneira muito semelhante, define-se
a probabilidade de transição de Passo n:
pij(n) = P{X(k +n) = j | X(k) = i}
Cadeias de Markov: Probabilidades de
Transição
Uma maneira conveniente de mostrar
todas as probabilidades de transição de
passo n é por meio da Matriz de
Transição de Passo n:
A matriz de transição P é a matriz de
transição de probabilidades de estado
para um passo no tempo, ou seja, de t
para t+1. Pode se dizer, de maneira
simplista, que as equações de ChapmanKolmogorov fornecem um método para
computar a matriz de transição para n
passos no tempo, ou seja, de t para t+1,
de t para t+2, ..., de t para t+n.
Seja pij(n) a probabilidade de transição do
estado i para o estado j no tempo n.
Pode-se escrever que:
Em notação matricial:
P(n) = Pm.Pn-m
Para Cadeias de Markov cujas
probabilidades de transição de estados
são constantes em relação ao tempo
(Cadeias Homogêneas), tem-se a
igualdade abaixo:
P(n) = Pn
Classificação de Estados em
Cadeias de Markov
Cadeias de Markov
Alcançável: Um estado j é dito ser
alcançável (accessible) a partir de um
estado i se pij(n) >0 para algum n ≥ 0 .
Isto implica que é possível o sistema
entrar no estado j eventualmente quando
este começa no estado i.
Comunicante: Um estado j é dito
comunicante com o estado i se o estado
j é alcançável a partir do estado i e o
estado i é alcançável a partir do estado j.
Cadeias de Markov
Se dois estados se comunicam entre si,
diz-se que eles pertencem à mesma
classe.
Se todos os estados são comunicantes,
portanto todos os estados pertencem a
uma única classe, a Cadeia de Markov é
dita ser Irredutível.
Cadeias de Markov
Um estado é dito ser Transiente
(Temporário, Efêmero, Transitório) se,
entrando neste estado, o processo pode
nunca retornar novamente para este
estado. Portanto, o estado i é transiente
se e somente se existe um estado j (j ≠ i)
que é alcançável a partir do estado i mas
não vice-versa, isto é, o estado i não é
alcançável a partir do estado j.
Cadeias de Markov
Um estado é dito ser Recorrente se
entrando neste estado, o processo
definitivamente irá retornar para este
estado. Portanto, um estado é recorrente,
se e somente se, não é transiente.
Cadeias de Markov
Um estado é dito ser Absorvente se,
entrando neste estado, o processo nunca
irá deixar este estado. Portanto, um
estado i é absorvente se, e somente se,
pii=1. Com isso, pode-se afirmar que um
estado absorvente é um caso especial de
um estado recorrente.
Cadeias de Markov
Em uma Cadeia de Markov, um conjunto
C de estados é dito ser um Conjunto
Fechado se o processo ao entrar em um
desses estados de C, este irá permanecer
nos estados de C indefinidamente, ou
seja, C é um conjunto tal que nenhum
estado fora de C é alcançável a partir de
qualquer estado de C. Com isso, pode-se
afirmar que C é um conjunto formado por
estados recorrentes.
Cadeias de Markov
Em uma Cadeia de Markov, um conjunto
C de estados é dito ser um Conjunto
Fechado Mínimo se este conjunto não
possui sub-conjuntos fechados.
Cadeias de Markov
Um estado i é periódico com período t se
um retorno a este estado é possível
somente em t, 2t, 3t,... passos para t>1 e
t é o maior inteiro com esta propriedade
(máximo divisor comum). Isto implica que
pii(n) 0 = sempre quando n não é divisível
por t.
Cadeias de Markov
Um estado i é periódico com período t se
um retorno a este estado é possível
somente em t, 2t, 3t,... passos para t>1 e
t é o maior inteiro com esta propriedade
(máximo divisor comum). Isto implica que
pii(n) 0 = sempre quando n não é divisível
por t.
Cadeias de Markov
Se há dois números consecutivos s e s+1 tal que o
processo pode estar no estado i nos tempos s e
s+1, o estado é dito ter período 1 e é chamado
estado Aperiódico.
Como a recorrência é uma classe de propriedade,
a periodicidade também é uma classe de
propriedade. Assim, se um estado i em uma classe
tem período t, todos os estados nesta classe têm
período t.
Cadeias de Markov
Um processo markoviano é dito Ergódico
se seus estados são recorrentes e
aperiódicos. Todas as suas propriedades
podem ser aferidas a partir de apenas um
conjunto de amostras. Uma Cadeia de
Markov é dita ser Ergódica se todos os
estados são estados ergódicos.
Cadeias de Markov
Exemplo: Determine para a matriz P:
Estados Transientes
Estados Recorrentes
Estados Absorventes
Conjuntos Fechados
Conjuntos Fechados Mínimos
Cadeias de Markov - Resumo
Probabilidades de Estados Estavéis
(Steady-State)
(Steady-State)
Sabemos até agora como calcular o vetor
de probabilidade de estado no passo k de
um sistema markoviano homogêneo
(equação de Chapman-Kolmogorov);
Mas, o que acontece quando k→∞?
(Steady-State)
Definição: para o j-ésimo estado, temos a
seguinte expressão para sua probabilidade
de regime permanente:
(Steady-State)
Teorema: Em uma cadeia de Markov
irredutível e aperiódica (ergódica), os
limites
sempre existem e são independentes do
vetor de probabilidade de estado inicial.
(Steady-State)
Definindo π = [π0 π1 ... πn], verifica-se o
seguinte em uma cadeia markoviana
ergódica quando k→∞:
π = πP
(Steady-State)
Conclusão: para determinar π, basta
resolver simultaneamente o seguinte
conjunto de equações lineares
1-
2-
π = πP
(Steady-State)
O sistema de equações anterior possui
n+1 incógnitas e n+2 equações.
Logo, qualquer uma das equações de (1)
pode ser eliminada para a solução do
sistema.
(Steady-State)
function [ssVec] = markovSS(A)
dim = size(A);
if(dim(1,1)==dim(1,2))
tmpM = eye(dim(1,1))-A';
ssVec = null(tmpM);
sum = 0;
for i = 1:dim(1,1)
sum = sum + ssVec(i,1);
end
ssVec = ssVec/sum;
else
ssVec = 0;
end
Implementação em
MATLAB do algoritmo
anterior.
EXEMPLOS E APLICAÇÕES DE
CADEIAS DE MARKOV
EXEMPLOS E APLICAÇÕES DE
CADEIAS DE MARKOV
PREVISÃO DO TEMPO
Modelo: Suponha que o tempo a cada dia
seja determinado apenas pelo tempo do dia
anterior, sendo que :
- Após em dia ensolarado, a probabilidade de
que o dia seguinte seja também ensolarado
é de 90% e a probabilidade de que o dia
seguinte seja chuvoso é de 10%.
- Após um dia chuvoso, há 50% de
probabilidade de que o dia seguinte seja
ensolarado e 50% de probabilidade de que
seja chuvoso.
EXEMPLO:PREVISÃO DO TEMPO
Assim, a matriz de transição associada ao modelo é
Podem-se rotular as colunas como ensolarado e chuvoso, nessa
ordem. O mesmo pode ser feito com as linhas. Assim,
representa a probabilidade de que um dia i seja seguido por
um dia j.
Suponha que o tempo no dia 0 está ensolarado. Assim, o
estado inicial pode ser representado pelo vetor seguinte:
Pelo modelo, o tempo no dia 1 pode
ser previsto como
Ou
Regras gerais para o n-ésimo dia são
ESTADO ESTACIONÁRIO
Previsões do tempo a longo prazo convergem para um vetor de
estado estacionário. Este vetor representa as probabilidades
de dias ensolarados e chuvosos para qualquer dia,
independentemente do tempo inicial.
Define-se o vetor de estado estacionário como:
O qual só converge para um vetor estritamente positivo se P é
uma matriz de transição regular (ou seja, há ao menos um Pn
com todas as entradas não-nulas).
Já que q independe das condições iniciais, ele deve
permanecer inalterado após transformado por P. Isso o torna
um autovetor (com autovalor 1), e significa que ele pode ser
derivado de P.
No nosso exemplo,
− 0.1q1 + 0.5q2 = 0
q1 + q2 = 1
Resolvendo o sistema
Assim, a longo prazo 83,3% dos dias são ensolarados!
EXERCÍCIO:PREVISÃO DO TEMPO
O mundo de Oz é abençoado com muitas
coisas, dentre as quais não se encontra o
tempo. Seus habitantes nunca têm dois dias
de sol consecutivos. Depois de um dia bom,
eles estão igualmente propensos a ter um dia
de chuva ou um dia de neve. Se eles têm
chuva ou neve num dia, há uma chance de
50% de terem o mesmo no dia seguinte. Se há
mudança do tempo após um dia chuvoso ou
com neve, esta mudança é para um dia bom
em apenas 50% das vezes. Com base nessas
informações, determine a matriz de transição
do tempo no mundo de Oz.
Resposta:
A longo prazo, qual a porcentagem de dias
ensolarados, chuvosos e com neve?
Resposta:
q = (0.4 0.2 0.4)
Na verdade, após apenas 6 dias já tem-se
a distribuição de probabilidades acima
encontrada. Observe:
EXEMPLO
Um rato é colocado numa gaiola como a da figura
seguinte. Há nove compartimentos com conexões
entre eles conforme indicado. O rato se move
aleatoriamente entre os compartimentos. Ou seja, se
há k formas de sair de um compartimento, ele escolhe
cada uma delas igual probabilidade.
EXEMPLO
Podemos representar as posições do rato por um processo
markoviano com matriz de transição dada por
Determine o vetor de estado estacionário do rato na gaiola.
EXERCÍCIO
Para encontrar o vetor de estado estacionário para tal matriz,
teríamos que resolver 10 equações com 9 incógnitas. Contudo, é
razoável considerar que o número de vezes que o rato alcança
cada compartimento, no longo prazo, deve ser proporcional ao
número de entradas para cada compartimento. Assim, basta
construir um vetor cuja jésima componente é o número de
entradas para o jésimo compartimento:
x = (2 3 2 3 4 3 2 3 2)
Normalizando para que a soma das componentes seja 1:
EXEMPLO:CADEIA DE MARKOV
ABSORVENTE
Lembrando:
Um estado de uma cadeia de Markov
é chamado absorvente quando é
impossível abandoná-lo (ou seja, pii = 1 ).
Uma cadeia de Markov é absorvente
quando tem ao menos um estado
absorvente, e a partir de cada estado,
é possível ir para um estado
absorvente(não necessariamente em
um passo). Um estado não absorvente
é chamado transiente.
EXEMPLO DE CADEIA DE MARKOV
ABSORVENTE:” Drunkard’s walk”
Um homem caminha aleatoriamente ao longo de uma avenida. Se
ele está nas esquinas 1, 2 ou 3, ele vai para a esquerda ou para a
direita com igual probabilidade. Ele continua até atingir a esquina 4,
na qual há um bar, ou a esquina 0, onde é sua casa. Se ele atingir o
bar ou o lar, ele permanece lá.
A matriz de transição para este exemplo é:
É fácil perceber que trata-se de uma cadeia de Markov
absorvente.
Perguntas interessantes que podemos formular a respeito deste
processo são:
Qual é a probabilidade de que o processo vá, no longo prazo,
parar em um estado absorvente?
Na média, após quantos passos o processo será absorvido?
Na média, quantas vezes o processo estará em cada estado
transiente?
As respostas para essas perguntas dependem, em geral, do
estado inicial do processo assim como das probabilidades de
transição.
FORMA CANÔNICA
Considere uma cadeia de Markov absorvente arbitrária.
Renumere os estados de forma que os estados transientes
sejam os primeiros. Se houver r estados absorventes e t
estados transientes, a matriz de transição terá a seguinte
forma canônica:
FORMA CANÔNICA
I é uma matriz identidade r-por-r, 0 é uma matriz de zeros rpor-t, R é uma matriz não-nula t-por-r, e Q é uma matriz tpor-t. Os primeiros t estados são transientes e os últimos r
estados são absorventes.
FORMA CANÔNICA
Após n passos:
A componente pij da matriz acima representa a probabilidade de
se alcançar o estado s j após n passos, quando a cadeia é
iniciada no estado s i. (A matriz representada por um asterisco
pode ser escrita em termos de Q e R, mas sua complicada
expressão não vem ao caso agora). As entradas de Q n fornecem
as probabilidades de estar em cada um dos estados transientes
após n passos para cada estado inicial transiente possível.
(n )
TEOREMA 1
Em uma cadeia de Markov absorvente, a
probabilidade de que o processo será absorvido é 1,
ou seja, →0 quando n→∞.
Prova: de cada estado transiente s j é possível
alcançar um estado absorvente. Seja m j o número
mínimo de passos requerido para se alcançar um
estado absorvente, a partir de s j. Seja p j a
probabilidade de que, começando no estado s j ,o
processo não alcançará um estado absorvente em m j
passos. Assim, p j <1. Seja m o maior dos mj e seja p
o maior dos p j . A probabilidade de não ser absorvido
em m passos é menor
ou igual a p, em 2m passos é
2
menor ou igual a p , e etc. Como p<1, tais
probabilidades tendem a zero. Assim, lim Q n = 0 .
n →∞
TEOREMA 1
Assim, voltando ao nosso exemplo:
A probabilidade de que o processo vá, no longo
prazo, parar em um estado absorvente é igual a
1.
TEOREMA 2
Para uma cadeia de Markov absorvente, a matriz I – Q tem
uma inversa N = I + Q + Q+... . A entrada da matriz N é o
número esperado de vezes que a cadeia passa pelo estado
transiente antes de ser absorvida, dado que o estado
transiente inicial é . O estado inicial é contado se i = j.
Voltando ao exemplo
EXEMPLO:” Drunkard’s walk”
Na forma canônica,
Donde,
Da linha do meio de N, vemos que se o estado inicial é o estado 2,
o número esperado de vezes que se passará pelos estados 1, 2 e 3
antes de ser absorvido será 1, 2 e 1.
TEOREMA 3
Seja t i o número esperado de passos
antes de a cadeia ser absorvida, dado que
o estado inicial é s i ,e seja t o vetor coluna
cuja i-ésima entrada é . Então,
t =Nc
onde c é um vetor coluna cujas entradas
são todas iguais a 1.
De volta ao nosso exemplo
Assim, a partir dos estados 1, 2 e 3, o número esperado de
passos antes da absorção é 3, 4 e 3, respectivamente.
APLICAÇÕES DA TEORIA DE
CADEIAS DE MARKOV
Jogos como o Banco Imobiliário, nos quais a
posição de cada jogador depende apenas da posição
anterior e do número tirado no dado.
Suponha que uma versão muito simplificada do jogo
seja a seguinte:
CADEIAS DE MARKOV
CADEIAS DE MARKOV
O número em cada célula indica a quantia recebida ou paga
por cada jogador ao alcançá-la. Usando a teoria de cadeias
de Markov, é possível estimar a quantia que se espera
receber após n rodadas de jogo:
P é a matriz de transição, f o vetor de payoffs, e g
é a quantia recebida/paga.
CADEIAS DE MARKOV
PageRank,do Google
O algoritmo do PageRank é basicamente uma cadeia de
Markov aplicada sobre o universo das páginas da Web.
Em essência, o Google interpreta um link da página A para
a página B como um voto, da página A para a página B.
Contudo, não é só o total de votos que conta no
ordenamento das páginas. O Google analisa também a
página “votante”. Votos dados por páginas que são elas
mesmas importantes têm um peso maior e ajudam outras
páginas a tornarem-se também importantes.
CADEIAS DE MARKOV
Apesar de a página E ter mais links apontando para ela, seu
PageRank é menor que o da página C, a qual recebe apenas um
link de uma página muito importante.
PageRank
Se uma página tem um PageRank de 0.5, há uma chance de
50% de que uma pessoa clicando em um link aleatório vá ser
direcionada para tal página.
Fontes Consultadas
Livros
CASSANDRAS, Christos G.
Introduction to discrete event
systems
/ by Christos G.
Cassandras, Stéphane Lafortune
HÄGGSTRÖM, Olle.
Finite Markov Chains and Algorithmic
Applications
Fontes Consultadas
Sítios da Internet
Cadeias de Markov
www.est.ufmg.br/~msantos/estoc/Markov.pdf
Markov Chain
http://en.wikipedia.org/wiki/Markov_chain
Markov Chains
www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/Chapter11.pdf
Markov Logic Networks
www.cs.washington.edu/homes/pedrod/kbmn.pdf
Application of Markov chains to identification of gas turbine engine dynamic models
http://www.informaworld.com/smpp/content~content=a743947737~db=jour
Application of Markov chains in deriving for predicting the dynamic behaviour of chemical
engineering processes
http://www.ingentaconnect.com/content/els/00981354/1995/00000019/90000001/art8712
1
Fontes Consultadas
Simulation of hidden Markov models with EXCEL
http://www.jstor.org/pss/3650388
Homogeneous semi-Markov reliability models for credit risk management.
http://goliath.ecnext.com/coms2/gi_0198-362250/Homogeneous-semi-Markov-reliabilitymodels.html
Application of Markov processes to predict aircraft operational reliability
pagesperso-orange.fr/andre.cabarbaye/pdf/articles/Article3.pdf
Hidden Markov models and their applications to customer relationship management
http://imaman.oxfordjournals.org/cgi/content/abstract/15/1/13
Markov fields and their applications in economics
http://www.springerlink.com/content/l220x85671g64841/
Hidden Markov Models
http://www.cs.brown.edu/research/ai/dynamics/tutorial/Documents/HiddenMarkovModels.ht
ml

Cadeia de Markov - People.csail.mit.edu

Transcrição

Documentos relacionados

Resumo da Tese de Mestrado

EST-039 e EST-171 – Processos Estocásticos Lista de Exercícios

3. Processos Estocásticos e o Lema de Ito

Acute Appendicitis in Young Children

slides do seminário I

PROCESSOS ESTOCÁSTICOS

4. Cadeias de Markov Quest˜ao 27. Mostre que se X for uma

Modelo em rede de Petri para o protocolo IEEE 802.15.4

Receitas Yämmi

Desigualdades de Markov e Chebyshev

Engenharia Química e Bioquímica - Área Interdepartamental de