Aula_17_-_Redes_de_Deciso_e_Valor_de_Informao

Prévia do material em texto

Inteligência Artificial
Redes de Decisão e Valor de Informação
Professor: Felipe Alberto B. S. Ferreira
felipe.bsferreira@ufrpe.br
mailto:felipe.bsferreira@ufrpe.br
Redes de Decisão
Redes de Decisão
Tempo
Previsão
Guarda-chuva
U
Redes de Decisão
§ UME: Utilidade Máxima Esperada – escolha a ação que maximize a utilidade
esperada dada alguma evidência
Tempo
Previsão
Guarda-chuva
U
§ Pode ser extraído diretamente das redes 
de decisão
§ Redes Bayesianas com nós para utilidade
e ações
§ Calcula a utilidade esperada para cada
ação
§ Novos tipos de nós:
§ Nós de chance (similar as RBs)
§ Ações (retângulos; não tem antecessores, 
age conforme evidência)
§ Nós de utilidade (losango, depende da 
ação e nós de chance)
Redes de Decisão
Tempo
Guarda-chuva
U
T P(T)
sol 0.7
chuva 0.3
G T U(G,T)
deixar sol 100
deixar chuva 0
levar sol 20
levar chuva 70
Redes de Decisão
Tempo
Previsão
Guarda-chuva
U
§ Seleção de ações
§ Instancie todas as evidencias
§ Defina os nós de ação em
todas formas possíveis
§ Calcule a probabilidade
posterior para todos os
antecessores do nó de 
utilidade, dada a evidência
§ Calcule a utilidade esperada
para cada ação
§ Escolha a ação que maximize a 
utilidade
Redes de Decisão
Tempo
Guarda-chuva
U
T P(T)
sol 0.7
chuva 0.3
Guarda-chuva = deixar
Guarda-chuva = levar
Decisão ótima = deixar
G T U(G,T)
deixar sol 100
deixar chuva 0
levar sol 20
levar chuva 70
UE deixar =*
!
P 𝑡 U deixar, 𝑡
UE levar =*
!
P 𝑡 U levar, 𝑡
MUE ∅ = max
"
UE 𝑎 = 70
Decisões como Árvores de Busca
§ Similar a expectimax / MDPs
§ O que mudou?
U(l,s)
Tempo | {} Tempo | {}
levar
deixar
{}
sol
U(l,c)
chuva
U(d,s) U(d,c)
chuvaso
lTempo
Guarda-chuva
U
Exemplo: Redes de Decisão
Tempo
Previsão
=ruim
Guarda-chuva
U
G T U(G,T)
deixar sol 100
deixar chuva 0
levar sol 20
levar chuva 70
T P(T|Pr=ruim)
sol 0.34
chuva 0.66
Guarda-chuva = deixar
Guarda-chuva = levar
Decisão ótima = levar
UE deixar | ruim =*
!
P 𝑡 | ruim U deixar, 𝑡
UE levar | ruim =*
!
P 𝑡 | ruim U levar, 𝑡
MUE Pr = ruim = max
"
UE 𝑎 | ruim = 53
Decisões como Árvores de Busca
U(l,s)
T | {r} T | {r}
levar
deixar
sol
U(l,c)
chuva
U(d,s) U(d,c)
chuvaso
l
{r}
Tempo
Previsão
=ruim
Guarda-chuva
U
Caça-Fantasmas com Redes de Decisão
Localização do
Fantasma
Sensor (1,1)
Caçar
U
Sensor (1,2) Sensor (1,3) Sensor (1,n)
Sensor (2,1)
Sensor (m,1) Sensor (m,n)…
…
…
…
Demo: Ghostbusters with probability 
Demo – Caça-Fantasmas com Probabilidade
Valor da Informação
Valor da Informação
§ Ideia: calcular o valor de adquirir uma evidência
§ Pode ser extraído diretamente da rede de decisão
§ Exemplo: extração de óleo
§ Dois blocos A e B; um deles tem óleo; vale k
§ Você pode perfurar em apenas um local
§ Probabilidade a priori de 0.5 cada; multuamente exclusivo
§ Perfurar em A ou B tem UE = k/2, MUE = k/2
§ Questão: qual é o valor da informação de O?
§ Valor de saber em qual local (A ou B) tem óleo
§ O valor é o ganho esperado na MUE pela nova informação
§ Se conhecemos ÓleoLoc, MUE é k
§ Ganho em MUE ao conhecer ÓleoLoc?
§ VI (ÓleoLoc) = k/2
ÓleoLoc
BrocaLoc
U
B O U
a a k
a b 0
b a 0
b b k
O P
a 1/2
b 1/2
Exemplo de VI: Tempo
Tempo
Previsão
Guarda-chuva
U
G T U
deixar sol 100
deixar chuva 0
levar sol 20
levar chuva 70
MUE sem evidência:
MUE se a previsão é ruim:
MUE se a previsão é boa:
Pr P(Pr)
boa 0.59
ruim 0.41
Distribuição da previsão:
MUE ∅ = max
"
UE 𝑎 = 70
MUE 𝑃𝑟 = ruim = max
"
UE 𝑎 | ruim = 53
MUE 𝑃𝑟 = boa = max
"
UE 𝑎 | boa = 95
VI 𝐸’ | e = *
#’
P 𝑒’ | 𝑒 MUE 𝑒, 𝑒’ − MUE 𝑒
Valor da Informação
§ Assumindo que temos a evidência E=e. Valor da ação:
§ Assumindo uma nova evidência E’ = e’. Valor da ação:
§ MAS E’ é uma variável aleatória cujo valor é
desconhecido, logo não sabemos o que e’ será
§ Valor esperado se E’ é revelado e depois agirmos:
§ Valor da informação: o quanto MEU aumenta
ao revelar E’ e depois agirmos:
P(s | +e)
{+e}
a
U
{+e, +e’}
a
P(s | +e, +e’)
U
{+e}
P(+e’ | +e)
{+e, +e’}
P(-e’ | +e)
{+e, -e’}
a
Propriedades
§ Não negativo:
§ Não aditivo: 
(pense sobre observar Ej duas vezes)
§ Independente de ordem
Questões de VI
§ A sopa do dia é sopa de beterraba ou sopa de 
cenoura, mas você não gosta de nenhuma das 
duas. Qual é o valor de saber qual é a sopa do 
dia?
§ Existem dois tipos de garfo de plástico em uma
festa. Um dos tipos é levemente mais rígido. 
Qual é o valor de saber o tipo do garfo?
§ Você irá jogar em uma loteria. O prêmio será
R$ 0 ou R$ 100. Você pode jogar qualquer
número entre 1 e 100 (chance de 1% de ganhar). 
Qual é o valor de conhecer o número que será
sorteado?
Valor da Informação Imperfeita?
§ Não existe
§ Informação corresponde a 
observação de um nó na rede de 
decisão
§ Se os dados são “ruidosos” isso
apenas significa que não estamos
observando a variável original, mas 
uma versão ruidosa da variável
original
Questão
§ VPI(ÓleolLoc) ?
§ VPI(Relatório) ?
§ VPI(Explorador) ?
§ VPI(Explorador | Relatório) ?
§ Geralmente: 
Se Parents(U) Z | Evidência
Logo VPI( Z | Evidência) = 0 
ÓleoLoc
BrocaLoc
U
Relatório do
Explorador
Explorador
POMDPs (Partially Observable MDPs)
POMDPs
§ MDPs tem:
§ Estados S
§ Ações A
§ Função de transição P(s’|s,a) (ou T(s,a,s’))
§ Recompensa R(s,a,s’)
§ POMDPs adicionam:
§ Observações O
§ Função de observação P(o|s) (ou O(s,o))
§ POMDPs são MDPs sobre estados de
crença b
a
s
s, a
s,a,s’
s'
a
b
b, a
o
b'
Exemplo: Caça-Fantasmas
§ Em caça-fantasmas (estático):
§ Crença determinada pelas
evidencias {e} até o momento
§ Árvore sobre conjuntos de 
evidências
§ Cálculos probabilísticos para 
predizer novas evidencias dadas 
as evidencias anteriores
§ Resolvendo POMDPs
§ Opção: usar expectimax
“truncado” para calcular o valor 
aproximado das ações
§ E se você apenas considerar
uma ação de caça ou um 
sensoriamento seguido de 
caça?
§ Temos um agente baseado em
VPI!
a
{e}
e, a
e’
{e, e’}
a
b
b, a
b’
abust
{e}
{e}, asense
e’
{e, e’}
asense
U(abust, {e})
abust
U(abust, {e, e’})
Demo: Ghostbusters with VPI 
e’
Demo – Caça-fantasmas com VPI
Referência
§ Stuart RUSSEL e Peter NORVIG, Inteligência Artificial. 3ª ed.
§ Capítulo 16 (seção 16.5 e 16.6)