PTC-5720-Aula-11-12

Prévia do material em texto

PTC-5720 Controle Estocástico
Oswaldo Luiz do Valle Costa
Aulas 11-12 - 2023
PTC-EPUSP
()PTC-5720 Controle Estocástico 1 / 60
Hidden Markov Models (HMM) - Modelos de Markov
Ocultos
Seja {Xk ; k = 1, 2, . . .} uma cadeia de Markov com matriz de transição
P = [pij ] e probabilidade inicial pi = P(X1 = i). Suponha que existe um
conjunto finito S de sinais que é emitido cada vez que a cadeia de Markov
entra em um estado. Assume-se que Sk representa o kesimo sinal emitido
então
P(S1 = s|X1 = j) = p(s|j),
P(Sk = s|X1, S1, . . . ,Xk−1, Sk−1,Xk = j) = p(s|j)
1 S1, S2, . . . são observados
2 X1,X2, . . . não são observados
()PTC-5720 Controle Estocástico 2 / 60
Exemplo
Máquina pode estar em 2 estados:
a) Estado 1 - Perfeitas condições
b) Estado 2 - Condições Impróprias
()PTC-5720 Controle Estocástico 3 / 60
Exemplo
Máquina é inspecionada e 2 possíveis resultados podem ser obtidos:
a) Estado G - Estado Bom
b) Estado B - Estado Ruim
Temos então
p(G |1), p(B|1)
p(G |2), p(B|2)
()PTC-5720 Controle Estocástico 4 / 60
HMM
Seja
Sn =
S1
...
Sn

o vetor aleatório com as n primeiras observações. Suponha que as n
observações coletadas sejam agrupadas no vetor sn da forma
sn =
s1
...
sn

Definimos
Fn(j) = P(Sn = sn,Xn = j).
()PTC-5720 Controle Estocástico 5 / 60
HMM
Note que
P(Xn = j |Sn = sn) =
P(Sn = sn,Xn = j)
P(Sn = sn)
=
Fn(j)∑
i Fn(i)
()PTC-5720 Controle Estocástico 6 / 60
Proposição
Temos que
Fn(j) =
∑
i
Fn−1(i)pijp(sn|j), n = 2, 3, . . .
F1(i) = pip(s1|i).
()PTC-5720 Controle Estocástico 7 / 60
()PTC-5720 Controle Estocástico 8 / 60
()PTC-5720 Controle Estocástico 9 / 60
()PTC-5720 Controle Estocástico 10 / 60
()PTC-5720 Controle Estocástico 11 / 60
Exemplo
Considere no exemplo anterior:
p1 = 0, 8, p11 = 0, 90, p(G |1) = 0, 99, p(G |2) = 0, 1.
Foram observados: S1 = G , S2 = B, S3 = G . Obtenha
i) A probabilidade da máquina estar no estado 1 quando a 3a inspeção
foi realizada.
ii) A probabilidade de X4 = 1.
iii) A probabilidade de S4 = G .
()PTC-5720 Controle Estocástico 12 / 60
()PTC-5720 Controle Estocástico 13 / 60
()PTC-5720 Controle Estocástico 14 / 60
()PTC-5720 Controle Estocástico 15 / 60
()PTC-5720 Controle Estocástico 16 / 60
()PTC-5720 Controle Estocástico 17 / 60
()PTC-5720 Controle Estocástico 18 / 60
Algoritmo de Viterbi
Desejamos calcular
max
xn
P(X n = xn|Sn = sn)
onde
X n =
X1
...
Xn
 , xn =
i1
...
in

()PTC-5720 Controle Estocástico 19 / 60
Algoritmo de Viterbi
Como
P(X n = xn|Sn = sn) =
P(X n = xn, Sn = sn)
P(Sn = sn)
e o termo P(Sn = sn) não depende de xn, o problema de maximização
acima é equivalente a
max
xn
P(X n = xn, Sn = sn)
()PTC-5720 Controle Estocástico 20 / 60
Algoritmo de Viterbi
Para k ≤ n, defina
Vk(j) = max
i1,...,ik−1
P
(
X k−1 =
 i1
...
ik−1
 ,Xk = j , Sk = sk
)
Segue que
Vk(j) = p(sk |j)max
i
pi |jVk−1(i)
()PTC-5720 Controle Estocástico 21 / 60
()PTC-5720 Controle Estocástico 22 / 60
()PTC-5720 Controle Estocástico 23 / 60
()PTC-5720 Controle Estocástico 24 / 60
()PTC-5720 Controle Estocástico 25 / 60
Algoritmo de Viterbi - Forward Algorithm
Vk(j) = p(sk |j)max
i
pijVk−1(i), k = 2, . . . , n
V1(j) = p(s1|j)pj
Algoritmo de Viterbi - Backward Algorithm
jn = argmaxj Vn(j)
ik(j) = argmaxi pijVk(i)
A sequência ótima é
jn, in−1(jn), in−2(in−1(jn)), . . . , i1(. . .).
()PTC-5720 Controle Estocástico 26 / 60
()PTC-5720 Controle Estocástico 27 / 60
()PTC-5720 Controle Estocástico 28 / 60
()PTC-5720 Controle Estocástico 29 / 60
()PTC-5720 Controle Estocástico 30 / 60
Algoritmo de Viterbi - Exemplo
Aplique o Algoritmo de Viterbi para o problema anterior e determine a
sequência ótima de estados.
()PTC-5720 Controle Estocástico 31 / 60
()PTC-5720 Controle Estocástico 32 / 60
()PTC-5720 Controle Estocástico 33 / 60
()PTC-5720 Controle Estocástico 34 / 60
()PTC-5720 Controle Estocástico 35 / 60
Problema com Observações Parciais
Exemplo das Máquinas: Suponha agora que uma ação de controle Uk deve
ser tomada no instante k (início do dia por simplicidade). Considere as
ações:
i) C0 - não fazer nada
ii) St - realizar inspeção detalhada de deixa a máquina como se fosse
nova
()PTC-5720 Controle Estocástico 36 / 60
Problema com Observações Parciais
As matrizes de transição para cada ação são dadas por:
P(Co) =
[2
3
1
3
0 1
]
, P(St) =
[2
3
1
3
2
3
1
3
]
()PTC-5720 Controle Estocástico 37 / 60
Problema com Observações Parciais
Suponha que:
P(G |1) = 3
4
, P(G |2) = 1
4
P(B|1) = 1
4
, P(B|2) = 3
4
Considere os seguintes custos:
g(1,Co) = 0, g(2,Co) = 2
g(1, St) = 1, g(2, St) = 1
()PTC-5720 Controle Estocástico 38 / 60
Problema com Observações Parciais
Desejamos obter U1 e U2 de forma a minimizar
E (g(X1,U1) + g(X2,U2))
Considere os seguintes vetores de informação:
I1 = S1, I2 = (S1, S2,U1)
()PTC-5720 Controle Estocástico 39 / 60
Problema com Observações Parciais
Os controles devem ser da forma:
U1 = U1(I1), U2 = U2(I2)
Desejamos obter U1 e U2 de forma a minimizar
min
U1,U2
E (g(X1,U1(I1)) + g(X2,U2(I2)))
()PTC-5720 Controle Estocástico 40 / 60
Programação Dinâmica
i) Último Estágio (k = 2)
J∗2 (I2) = min{1, 2P(X2 = 2|I2)}
ii) Primeiro Estágio (k = 1)
J∗1 (s1) = min
{
1+ E (J∗2 (S2, s1, St)|S1 = s1,U1 = St),
2P(X1 = 2|S1 = s1) + E (J∗2 (S2, s1,Co)|S1 = s1,U1 = Co)
}
()PTC-5720 Controle Estocástico 41 / 60
Último Estágio (k = 2) e Primeiro Estágio (k = 1)
()PTC-5720 Controle Estocástico 42 / 60
()PTC-5720 Controle Estocástico 43 / 60
()PTC-5720 Controle Estocástico 44 / 60
()PTC-5720 Controle Estocástico 45 / 60
()PTC-5720 Controle Estocástico 46 / 60
()PTC-5720 Controle Estocástico 47 / 60
()PTC-5720 Controle Estocástico 48 / 60
()PTC-5720 Controle Estocástico 49 / 60
()PTC-5720 Controle Estocástico 50 / 60
()PTC-5720 Controle Estocástico 51 / 60
()PTC-5720 Controle Estocástico 52 / 60
()PTC-5720 Controle Estocástico 53 / 60
()PTC-5720 Controle Estocástico 54 / 60
()PTC-5720 Controle Estocástico 55 / 60
()PTC-5720 Controle Estocástico 56 / 60
()PTC-5720 Controle Estocástico 57 / 60
()PTC-5720 Controle Estocástico 58 / 60
()PTC-5720 Controle Estocástico 59 / 60
()PTC-5720 Controle Estocástico 60 / 60
	7) Cadeias de Markov Ocultas