Agentes Probabilistas
Seminário da disciplina Métodos de Computação Inteligentes e Agentes
Inteligentes
Hugo Pimentel de Santana
([email protected])
Motivação
Agentes precisam lidar com incertezas

Ambientes
 Não determinísticos
 Parcialmente observáveis
Exemplo: Wumpus
4
Brisa(2,1)  Brisa(1,2) 
Buraco(3,1)  Buraco(2,2) 
Buraco(1,3)
3
?
2
B
OK
?
OK
B
OK
?
1
22
33
1
4
2
Limitações da lógica para representar
conhecimento incerto
Engajamento epistemológico: crença sobre fato do mundo
representado como fórmula lógica



certamente verdadeira
certamente falsa
totalmente desconhecida
Incertezas representáveis apenas através da disjunção
Limitações da disjunção:

Problema da qualificação: impossível na prática pensar em todos os
casos possíveis
 É trabalhoso demais modelar todos os caso, ou adquirir todos os dados
 Existe apenas conhecimento observado empírico sem modelo causal

Crenças iguais sobre todas as alternativas de uma disjunção
 não há algumas mais plausíveis do que outras
3
Representando conhecimento incerto
Conhecimento provê apenas um grau de confiança
sobre aspectos do mundo
Teoria da probabilidade

Pode expressar o grau de confiança do agente
 1 representa a certeza absoluta da verdade
 0 a certeza absoluta da falsidade
 Valores entre 0 e 1 representam a confiança do agente

A priori (incondicional)
 Antes de se obter evidências. Ex. P(Buraco(1,1)) = 0.2

A posteriori (condicional)
 Expressa o grau de confiança após alguma evidência ter sido
obtida. Ex. P(Buraco(1,1)|Brisa(1,2)) = ?
4
Probabilidade: Notação
Graus de confiança associados a proposições

LPO também pode ser utilizada
Variáveis aleatórias associadas a literais da lógica proposicional
extendidos com inequações numéricas:

Booleanas, correspondem a variáveis booleanas de CSP
 Carie: domínio <true, false>,
DorDeDente: domínio: <true, false>
 Carie = true carie, e Carie = false  carie

Discretas, corresponde a variáveis de domínio finito de CSP
 Tempo: domínio <sol, chuva, nublado, neve>
 Tempo = sol

Contínuas, corresponde a variáveis reais de CSP
 X: domínio = [0,1] ou R
 X  1.24
Evento atômico: combinação de literais com conjunção e negação

Especificação completa das variáveis do mundo

Exemplo
 carie  dordedente  Tempo = nublado
5
Probabilidade Incondicional (a priori)
Associada a uma proposição


P(Carie = true) = 0.1 ou P(carie) = 0.1
P(Tempo = sol) = 0.7, P(Tempo = chuva) = 0.2, P(Tempo =
nublado) = 0.08, P(Tempo = neve) = 0.02
Distribuição de probabilidade


P(Tempo) = <0.7, 0.2, 0.08, 0.02>
P(Carie) = <0.1, 0.9>
Distribuição de probabilidade conjunta:

P(Carie, DorDeDente, Tempo)
 Indicada por uma tabela com 2 x 2 x 4 (16 entradas)
 Cada entrada representa um evento atômico
6
Probabilidade Condicional
Probabilidade, dado que o agente já possui alguma
evidência


P(a|b) = probabilidade de a, dado que b é conhecido
P(carie|dordedente) = 0.8
 Se o paciente está com dor de dente, há 80% de chances dele
estar com uma cárie
Regra do produto

P(a b) = P(a|b)P(b) (regra do produto)
P(X|Y) representa os valores P(X=xi|Y=yj), i,j
7
Agente probabilista 1
Distribuição de probabilidade conjunta
(intensão)
dorDeDente
dorDeDente
Sensores
Ambiente
Máquina de
Inferência
Probabilista
Atuadores
P(carie)
catch
catch
catch
catch
carie
0.108
0.012
0.072
0.008
carie
0.016
0.064
0.144
0.576
Ask
Tell
Retract
Base de
Conhecimento
Probabilista
DorDeDente = true
Marginalização
8
Marginalização
Probabilidade de uma proposição: soma dos valores
da tabela de distribuição conjunta em que a
proposição é verdade
P(Y) = z P(Y, z)

ex, P(Carie) = <0.108 + 0.012 + 0.072 + 0.008,
0.016 + 0.064 + 0.144 + 0.576>
= <0.2, 0.8>
Como calcular a probabilidade de uma proposição
dada alguma evidência? Ex: P(Carie|dorDeDente)

Pela regra do produto:
 P(carie|dorDeDente) = P(cariedorDeDente) / P(dorDeDente)
 P(carie|dorDeDente)=P(cariedorDeDente) / P(dorDeDente)
 1/P(dorDeDente) é apenas uma constante de normalização (),
logo basta calcular P(Carie, dorDeDente) utilizando
marginalização
9
Inferência probabilidades condicionais
P(X|e) = normalizar( P(X,e) ) =  ( yP(X,e,y) )
Exemplo:
P(Carie|dordedente) =
 ( yP(Carie,dordedente, Y) ) =
 [P(Carie, dordedente, catch)
+ P(Carie, dordedente, catch)] =
 [<0.108,0.016> + <0.012,0.064>] =
 [<0.12,0.08>] =
<0.6, 0.4> ( = 5)
10
Problemas da inferência por
marginalização
Complexidade exponencial

No espaço
 Para n variáveis (booleanas), a distribuição de probabilidade
conjunta possui 2n entradas

No tempo
 No pior caso, a marginalização precisa somar todos os
elementos da tabela de distribuição conjunta
Não leva em conta independência entre variáveis

Como seria P(Carie, DorDeDente, Catch, Tempo)
 A tabela teria o tamanho da tabela anterior multiplicado por 4
11
Independência entre variáveis
P(Carie|Tempo = nublado) = P(Carie)

Se a e b são independentes
 P(a|b) = P(a) e P(ab) = P(a)P(b)
Se temos 3 moedas, a distribuição conjunta
P(C1,C2,C3) pode ser dado por P(C1), P(C2) e P(C3)

Reduz de 23 para 3 x 2
Pode-se ter também Independência Condicional



Duas variáveis podem ser independentes, dado o valor de
uma terceira variável
Exemplo: Se eu sei o valor de Carie, DordeDente e Catch
passam a ser independentes
Logo: P(dorDeDente  catch | Carie) =
P(dorDeDente| Carie) P(catch|Carie)
12
Redução da complexidade da distribuição
conjunta
Distribuição conjunta:



P(DorDeDente, Catch, Carie) =
(regra do produto)
P(DorDeDente, Catch|Carie)P(Carie) =
(independência condicional)
P(DorDeDente|Carie) P(Catch|Carie) P(Carie)
 De 23-1 valores necessários para 2+2+1
 Reduz de O(2n) para O(n)

De uma maneira geral (assumindo independência entre os
efeitos, dada a causa)
 P(Causa, Efeito1, Efeito2,...)=P(Causa)iP(Efeitoi|Causa)
13
Exemplo: Wumpus...
Sejam:


Cij variável booleana que indica se a posição (i,j) possui
buraco
Bij variável booleana que indica se a posição (i,j) possui brisa
(usaremos só B11, B12 e B21)
Tell(b11)
Tell(b12)
Tell(b21)
Ask( P(C13|BC) )
Ask( P(C22|BC) )
Ask( P(C31|BC) )
4
3
?
2
B
OK
?
OK
B
OK
?
1
22
33
1
4
14
Wumpus: Especificação da distribuição
conjunta e inferência do melhor caminho
A DPC é dada por P(C11, C12, ..., C44, B11,B12,B21)


P(C11, C12, ..., C44, B11,B12,B21) = (regra do prod.)
P(B11,B12,B21|C11, C12, ..., C44)P(C11, C12, ..., C44)
Como P(Cij) = <0.2, 0.8>, e as probabilidades de P(Cij) são
independetes

P(C11, C12, ..., C44) = 0.2nBuracos x 0.816-nBuracos
Sabe-se um algoritmo para calcular
P(B11,B12,B21|C11, C12, ..., C44)

Para toda variável Cij, se Cij = true
 Para toda variável B, se B é adjacente a Cij e B = false, retorne 0

Retorne 1
Com a DPC, a máquina de inferência pode responder a
Ask( P(C13|BC) ) por marginalização


P(C13|b,c) = P(C31|b,c) = 31%
P(C22|b,c) = 86%
 O agente deve seguir por (1,3) ou (3,1)
15
Redes Bayesianas para representação de
conhecimento incerto
Rede bayesiana (sintaxe)



Variáveis são representadas por nós
O grafo formado não possui ciclos
Se há uma seta de A para B, então A (pai) possui
uma influência direta sobre B
Cárie
Catch
Tempo
DorDeDente
16
Redes bayesianas e tabela de
probabilidades condicionais
P(L)
.001
Ladrão
Terremoto
Alarme
JoãoLigar
A
t
P(J)
.90
f
.05
L
T
P(A)
t
t
.95
t
f
.94
f
t
.29
f
f
.001
MariaLigar
P(T)
.002
A
t
P(M)
.70
f
.05
17
Agente probabilista 2
Rede Bayesiana
(intensão)
Subsídio
Harvest
Custo
Sensores
Compra
Ambiente
Máquina de
Inferência
Probabilista
Ask
Tell
Retract
Base de
Conhecimento
Probabilista
Atuadores
Inferência exata ou
aproximada
18
Semântica das Redes bayesianas
Representa a distribuição conjunta


P(x1, ..., xn) = i=1|nP(xi|parents(Xi))
Ex.
 P(j  m  a  l  e) =
P(j|a)P(m|a)P(a|l  e)P(l)P(e) =
0.00062

Complexidade O(n2k) contra O(2n) da tabela de
distribuição conjunta, onde k é o número máximo
de pais por nó
 No exemplo do alarme, representa 10 valores contra 25-1
(31) da representação pela tabela de DPC
19
Propriedades das redes bayesianas
Um nó é
condicionalmente
independente de
todos os outros
nós da rede, dado
seus pais, filhos e
pais dos filhos
(markov blanket)
20
Propriedades das redes bayesianas
Um nó é condicionalmente
independente dos não-descendentes,
dado seus pais

Ex.
P(MariaLigar|JoãoLigar,Alarme,Terremoto,Ladrão)
= P(MariaLigar|Alarme)
21
Representações eficientes de distribuições
condicionais
Nós determinísticos

seu valor é uma função determinística dos pais
 Ex. NorteAmericano = Canadense  US  Mexicano
Noisy-OR

Permite especificar a distribuição em relação aos
pais se:
 Todas as influências(causas) estão listadas
 Há independência entre os fatores que fazem com que a
causa não provoque a conseqüência (inibidores)
22
Noisy-OR - Exemplo
P(febre|gripe, resfriado,
malaria) = 0.6
P(febre|gripe, resfriado,
malaria) = 0.2
P(febre|gripe, resfriado,
malaria) = 0.1
Gripe
Resfriado Malaria P(Febre)
P(Febre)
F
F
F
0.0
1.0
F
F
T
0.9
0.1
F
T
F
0.8
0.2
F
T
T
0.98
0.02 = 0.2 x 0.1
T
F
F
0.4
0.6
T
F
T
0.94
0.06 = 0.6 x 0.1
T
T
F
0.88
0.12 = 0.6 x 0.2
T
T
T
0.988
0.6 x 0.2 x 0.1
23
Resumo da ópera
Redução da complexidade e
precisão inferência probabilista
RB
DPC com TPC
RB com
Redução da complexidade da aquisição das probabilidades
24
Redes Bayesianas para variáveis
contínuas
Duas possibilidades


Discretizar os valores das variáveis aleatórias
Especificar as funções de distribuição de probabilidade, com
número finito de parâmetros,
Rede Bayesiana híbrida


Possui variáveis discretas e contínuas
Exemplo:Subsídio e Compra, booleanas, Custo e Harvest contínuas
Harvest
Subsídio
Custo
Compra
P(c|h, subsidio) =
N(atrueh + btrue 2)(c)
= distribuição
P(c|h, subsidio) =
N(afalseh + bfalse2)(c) = distribuição
Onde, a e b são parâmetros da
distribuição
25
Inferência exata em redes bayesianas
Como uma rede bayesiana representa a
distribuição conjunta, o mesmo processo
pode ser utilizado
P(L|j,m)= P(L,j,m) = taP(L,t,a,j,m)

Para L = true:
 P(l|j,m) =  t a P(l)P(t)P(a|l,t)P(j|a)P(m|a)

Porém, mais eficiente:
 P(l|j,m) =  P(l)tP(t)aP(a|l,t)P(j|a)P(m|a)
26
Árvore de expressões
P(l)
P(t)
P(a|l,t)
P(j|a)
P(m|a)
+
+
P(a|l,t)
P(j|a)
P(m|a)
P(t)
P(a|l,t)
P(j|a)
P(m|a)
+
P(a|l,t)
P(j|a)
P(m|a)
27
Eliminação de variáveis
Algoritmo para inferência exata


Processa a árvore de expressões bottom-up,
armazenando os valores calculados
Observação:
 Todas as variáveis que não são ancestrais da variável de
consulta ou das evidências podem ser removidas da
inferência
 P(J|l) = P(l)tP(t)aP(a|l,t)P(J|a)mP(m|a)

Mas mP(m|a) é 1 por definição, logo pode ser eliminado
28
Complexidade do algoritmo de eliminação
de variáveis
Se a rede é uma polytree (no máximo um caminho entre dois
nós)

linear no número de nós da rede
Em geral, tempo e espaço exponencial (#P-Hard)
Algoritmos de clustering podem transformar redes em polytrees
(continua exponencial no pior caso)
Nublado
Nublado
Chuva
Aguador
Aguador + Chuva
Molhado
Molhado
29
Processo de construção de uma Rede
Bayesiana
30
Inferência aproximada em redes
bayesianas
Inferência exata é intratável para redes
grandes e muito conectadas
Inferência aproximada permite obter uma
solução mais eficiente, porém aproximada

A complexidade em tempo é dada pela qualidade
da solução
Escapa da NP-Completude, mas qualidade da
solução diminui
Baseada nos algoritmos de Monte Carlo
31
Amostragem direta
Nublado
Aguador
Amostra de
P(Aguador|Nublado = true)
= false
Evento atômico:
[true, false, true, true]
Amostra de <0.5, 0.5>
= true
Chuva
Amostra de
P(Chuva|Nublado = true)
= true
Molhado
Amostra de
P(Molhado|Aguador = false, Chuva = true)
= true
32
Nublado
Aguador
Chuva
Molhado
33
Nublado
Amostragem direta
Aguador
Chuva
Molhado
limN[Namostras(x1,...,xn)/N] = P(x1,...,xn)
Quanto mais amostras, mais consistente a
aproximação da DPC
Exemplo:

Se em 1000 amostras, 511 delas tem Chuva =
true, P(chuva) = 0.511
Problema: como responder a consultas do
tipo P(X|evidencia)?
34
Rejection Sampling
Calculando P(X|e)

Gera-se várias amostras, descartando as que e não é verdade
Namostras(X,e)/Namostras(e) =
P(X,e) x N] / [P(e) x N] =
P(X,e) / P(e) =
P(X|e) = Namostras(X,e)
Ex. Calcular P(Chuva|Aguador = true)



De 100 amostras, 73 tem Aguador = false e são rejeitadas
Das 27, 8 tem Chuva = true e 19 não
P(Chuva|Aguador = true)  Normalizar(<8,19>) = <0.296,0.704>
Problema:

Se P(e) pequena, muitas amostras terão que ser rejeitadas até que
se consiga uma estimativa consistente
35
Nublado
Likelihood weighting
Aguador
Chuva
Molhado
Só gera amostras consistentes com as evidências


Associa um peso a cada amostra, que significa o quanto
aquela amostra é significativa
P(x|e)  yNws(x,y,e)w(x,y,e)
Fazendo amostra em P(Chuva|aguador, molhado):





W=1
Suponha que amostra de Nublado seja true
Para Aguador=true: w = w x P(aguador|nublado)
Amostra de Chuva em P(Chuva|nublado) é true
Para Molhado=true: w = w x P(molhado|aguador, chuva)
[true, true, true, true] tem peso 0.099
Problemas

Quanto mais evidências, pior a performance (mais amostras
são necessárias), principalmente se as evidências estão no
final da rede
36
Simulação por cadeias de Markov (Markov
Chain Monte Carlo)
Gera resultados consistentes mais
rapidamente
Cada evento atômico é um estado


Próximos estados são gerados amostrando as
variáveis (que não são evidências), condicionada
aos valores do Markov Blanket
O próximo estado é formado pelo estado anterior,
alterando apenas uma variável
Prova de que funciona:

AIMA, 2nd edition, página 517
37
Nublado
MCMC: Exemplo
Aguador
Chuva
Molhado
Query: P(Chuva|Aguador = true, Molhado = true)

Nublado e Chuva são inicializados randômicamente com
(true, false), evidências são mantidas
Estado inicial: [true,true, false, true]


Nublado é amostrada segundo o seu Markov Blanket de
P(Nublado|Aguador = true, Chuva = false), gerando um
novo estado: Ex. [false, true, false, true]
Chuva é amostrada segundo o seu Markov Blanket:
P(Chuva|Nublado = false, Aguador = true, Molhado = true),
gerando um novo estado [false, true, true, true]
A resposta a query é dada normalizando a
quantidade de eventos atômicos em que Chuva =
true e Chuva = false
38
Probabilidade e representações de
primeira ordem
Redes Bayesianas são proposicionais

Restringe seu uso em muitos domínios
Problema de estender para lógica de primeira ordem:

Base de conhecimento precisaria especificar as
probabilidades para todos os modelos possíveis
 Impraticável


Implementar
Especificar estas distribuições
Possível solução: Relational Probability models
39
Relational Probability Models
Constantes, nomeando objetos de classes

Ex: ProfSmith pertence a classe Professor, Jones pertence a classe
Estudante
Funções Simples: classes x imagem finita

Ex: Inteligencia(Jones) = {alta, baixa}, Famoso(ProfSmith) = {true, false}
Funções Complexas: de classes em classes

Ex: Orientador(Jones) = ProfSmith
Informação probabilística: especificar pais para as funções simples


x, x Estudante  Parents(Sucesso(x)) = {Inteligencia(x),
Famoso(Orientador(x))}
x, x Estudante  P(Sucesso(x) = true| Inteligencia(x) = alta,
Famoso(Orientador(x)) = true) = 0.95
Redes bayesianas podem ser criadas a partir de um RPM, em um
processo semelhante ao da proposicionalização
40
Relational Probability Models
Figs. RPM
41
Outras maneiras de lidar com incertezas
Default reasoning

Conclusões são tratadas como verdadeiras, até que algum outro fato leve a
acreditar em outra coisa
Baseados em regras

Adicionar um “fudge factor” a regras para acomodar incertezas
Teoria de Dempster-Shafer


Probabilidade não trata ignorância
Moeda: Se ela é honesta, P(Cara) = <0.5,0.5>, se ela for desonesta mas
desconhecida, P(Cara) = <0.5,0.5>
Lógica Fuzzy


O que foi apresentado trata grau de certeza sobre existência de fatos que
são verdadeiros ou falso.
Lógica Fuzzy: vagueness – eventos podem ser +/- verdade
42
Axiomas da probabilidade
Axiomas de Kolmogorov




0  P(a)  1
P(true) = 1, P(false) = 0
P(a b) = P(a) + P(b) – P(a  b)
Todo o resto da teoria da probabilidade pode ser obtido a
partir destes
n
 P( D  d )  1
i
i 1

Exemplo
 P(Tempo = sol) + P(Tempo = chuva) +
P(Tempo = nublado) + P(Tempo = neve) = 1
43
Regra de Bayes
P(Y|X) = P(X|Y)P(Y) / P(X)

Permite transformar conhecimento causal em
diagnóstico e vice-versa
Exemplo: Qual a probabilidade de um
paciente estar com meningite (m), dado que
ele está com uma dor no pescoço (d)




P(d | m) = 0.5
P(m) = 1/50000
P(d) = 1/20
P(m|d) = P(d|m)P(m)/P(d) = 0.0002
44