Agentes Probabilistas Seminário da disciplina Métodos de Computação Inteligentes Hugo Pimentel...

Agentes ProbabilistasSeminário da disciplina Métodos de Computação Inteligentes

Hugo Pimentel de Santana (hps@cin.ufpe.br)

2

Motivação

Agentes precisam lidar com incertezas Ambientes

Não determinísticos Parcialmente observáveis

Exemplo: Wumpus

Brisa(2,1) Brisa(1,2) Buraco(3,1) Buraco(2,2) Buraco(1,3)

1

2

3

4 12 3

4

OKBOK

BOK

?

?

?

2 43

3

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çãoLimitaçõ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 casos, 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

4

Representando conhecimento incerto

Conhecimento provê um grau de confiança sobre aspectos do mundoTeoria 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)) = ?

5

Probabilidade: Notação

Graus de confiança associados a proposições Representações de primeira ordem também podem ser utilizadas

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

6

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

7

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

8

Agente probabilista 1

Ask

Tell

Retract

Am

bie

nte

Sensores

Atuadores

Base deConhecimento

Probabilista

Máquina deInferência

Probabilista

Marginalização

Distribuição de probabilidade conjunta(intensão)

P(carie)

dorDeDente dorDeDente

catch catch catchcatc

h

carie 0.108 0.012 0.072 0.008

carie

0.016 0.064 0.144 0.576

DorDeDente = true

9

Resumo dos métodos utilizados por agentes probabilistas

DPC

Redução da complexidade na aquisição das probabilidades

RB comCPT

RB comnoisy-or

e det. nodes

Redução da complexidade da inferência (e da precisão)

DPC com marginalização

RB com inferência exata

RB Amo. D./ Rej. S.

RB Likelihood W.

RB MCMC

10

Marginalização

Probabilidade de uma proposição: soma dos valores da tabela de distribuição conjunta em que a proposição é verdadeP(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(cariedorDeDente) / P(dorDeDente) P(carie|dorDeDente)=P(cariedorDeDente) / P(dorDeDente) 1/P(dorDeDente) é apenas uma constante de normalização (), logo basta calcular P(Carie, dorDeDente) utilizando

marginalização

11

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)

12

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

13

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(ab) = 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)

14

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)

15

Exemplo: Wumpus...

Sejam: Bij variável booleana que indica se a posição (i,j)

possui buraco Vij variável booleana que indica se a posição (i,j)

possui brisa (usaremos só V11, V12 e V21)

1

2

3

4 12 3

4

OKVOK

VOK

?

?

?

2 43

Tell(v11)Tell(v12)Tell(v21)

Ask( P(B13|BC) )Ask( P(B22|BC) ) Ask( P(B31|BC) )

16

Wumpus: Especificação da distribuição conjunta e inferência do melhor caminho

A DPC é dada por P(B11, B12, ..., B44, V11,V12,V21) P(B11, B12, ..., B44, V11,V12,V21) = (regra do prod.) P(V11,V12,V21|B11, B12, ..., B44)P(B11, B12, ..., B44)

Como P(Bij) = <0.2, 0.8>, e as probabilidades de P(Bij) são independetes

P(B11, B12, ..., B44) = 0.2nBuracos x 0.816-nBuracos

Sabe-se um algoritmo para calcular P(V11,V12,V21|B11, B12, ..., B44)

Para toda variável Bij, se Bij = true Para toda variável V, se V é adjacente a Bij e V = false, retorne 0

Retorne 1Com a DPC, a máquina de inferência pode responder a Ask( P(B13|BC) ) por marginalização

P(B13|BC) = P(B31|BC) = 31% P(B22|BC) = 86%

O agente deve seguir por (1,3) ou (3,1)

17

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 diretadireta sobre B

DorDeDenteCatch

Cárie Tempo

18

Redes bayesianas e tabela de probabilidades condicionais

MariaLigar

Alarme

JoãoLigar

TerremotoLadrãoP(L).001

P(T).002

L T P(A)

t t .95

t f .94

f t .29

f f .001

A P(J)t .90

f .05

A P(M)t .70

f .05

19

Agente probabilista 2

Ask

Tell

Retract

Am

bie

nte

Sensores

Atuadores

Base deConhecimento

Probabilista

Máquina deInferência

Probabilista

Inferência exata ou aproximada

Rede Bayesiana(intensão) Subsídio Harvest

Custo

Compra

20

Resumo dos métodos utilizados por agentes probabilistas

DPC

Redução da complexidade na aquisição das probabilidades

RB comCPT

RB comnoisy-or

e det. nodes

Redução da complexidade da inferência (e da precisão)

DPC com marginalização

RB com inf. Exata

RB Amo. D./ Rej. S.

RB Likelihood W.

RB MCMC

21

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

22

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)

23

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)

24

Processo de construção de uma Rede Bayesiana

Conselhos: Se a influência entre dois nós é muito

pequena, não vale a pena incluir um link Adiciona complexidade na rede

desnecessariamente

A ordem em que os nós são incluídos é relevante Adicionar as causas principais primeiro

25

Construção de uma rede bayesiana

A ordem pode acarretar em: Mais arestas na representação Relacionamentos tênues, e difíceis de valorar (Ex. P(Terremoto|ladrão,

alarme)O segundo exemplo possui a mesma complexidade de especificar a DPC

26

Resumo dos métodos de inferência dos agentes probabilistas

DPC

Redução da complexidade na aquisição das probabilidades

RB comCPT

RB comnoisy-or

e det. nodes

Redução da complexidade da inferência (e da precisão)

DPC e marginalização

RB com inf. Exata

RB Amo. D./ Rej. S.

RB Likelihood W.

RB MCMC

27

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)

28

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

29

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 (linear gaussiana mais utilizada)

Rede Bayesiana híbrida Possui variáveis discretas e contínuas Exemplo:Subsídio e Compra, booleanas, Custo e Harvest

contínuasSubsídio Harvest

Custo

Compra

P(c|h, subsidio) = N(atrueh + btrue2)(c) =

P(c|h, subsidio) = N(afalseh + bfalse2)(c) =

2)(

2

1

2

1

f

ff bhae

f

e

2)(

2

1

2

1

t

tt bhae

t

e

30

Resumo dos métodos de inferência dos agentes probabilistas

DPC

Redução da complexidade na aquisição das probabilidades

RB comCPT

RB comnoisy-or

e det. nodes

Redução da complexidade da inferência (e da precisão)

DPC e marginalização

RB com inf. Exata

RB Amo. D./ Rej. S.

RB Likelihood W.

RB MCMC

31

Inferência exata em redes bayesianas

Como uma rede bayesiana representa a distribuição conjunta, o mesmo processo pode ser utilizadoP(L|j,m)= P(L,j,m) = taP(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)

32

Árvore de expressões

P(m|a)

+

+

+

P(l)

P(t) P(t)

P(a|l,t) P(a|l,t)P(a|l,t)

P(j|a) P(j|a)

P(m|a)

P(a|l,t)

P(j|a) P(j|a)

P(m|a) P(m|a)

P(l|j,m) = P(l)tP(t)aP(a|l,t)P(j|a)P(m|a)

33

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

34

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)

ChuvaAguador

Nublado

Molhado

Aguador + Chuva

Nublado

Molhado

35

Inferência aproximada em redes bayesianas

Inferência exata é intratável para redes grandes e muito conectadasInferê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 diminuiBaseada nos algoritmos de Monte Carlo

36

Resumo dos métodos utilizados por agentes probabilistas

DPC

Redução da complexidade na aquisição das probabilidades

RB comCPT

RB comnoisy-or

e det. nodes

Redução da complexidade da inferência (e da precisão)

DPC e marginalização

RB com inf. Exata

RB Amo. D./ Rej. S.

RB Likelihood W.

RB MCMC

37

Amostragem direta

ChuvaAguador

Nublado

Molhado

Amostra de <0.5, 0.5>= true

Amostra de P(Aguador|Nublado = true)= false Amostra de

P(Chuva|Nublado = true)= true

Amostra de P(Molhado|Aguador = false, Chuva = true) = true

Evento atômico:[true, false, true, true]

38

Amostragem direta

limN[Namostras(x1,...,xn)/N] = P(x1,...,xn)

Quanto mais amostras, mais consistente a aproximação da DPCExemplo: Se em 1000 amostras, 511 delas tem Chuva

= true, P(chuva) = 0.511

Problema: como responder a consultas do tipo P(X|evidencia)?

Nublado

Chuva

Molhado

Aguador

39

Rejection Sampling

Calculando P(X|e) Gera-se várias amostras, descartando as que e não é

verdadeNamostras(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

Nublado

Chuva

Molhado

Aguador

40

Likelihood weighting

Só gera amostras consistentes com as evidências Associa um peso a cada amostra, que significa o quão

significativa é esta amostra 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.099Problemas

Quanto mais evidências, pior a performance (mais amostras são necessárias), principalmente se as evidências estão no final da rede

Nublado

Chuva

Molhado

Aguador

41

Simulação por cadeias de Markov (Markov Chain Monte Carlo)

Gera resultados consistentes mais rapidamenteCada 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

42

MCMC: Exemplo

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

Nublado

Chuva

Molhado

Aguador

43

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

Aplicações existentes: Relational Probability models

44

Relational Probability Models

Constantes, nomeando objetos de classes Ex: ProfSmith pertence a classe Professor, Jones pertence a classe

Estudante, Bloggs pertence a classe EstudanteFunções Simples: classes -> 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

45

Relational Probability Models

Professor

Student

Fame

Funding

Inteligence

Success

Advisor

Fame(ProfSmith)

Funding(ProfSmith)

Intelligence(Bloggs)

Success(Bloggs)

Intelligence(Jones)

Success(Jones)

46

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 coisaBaseados em regras

Adicionar um “fudge factor” a regras para acomodar incertezasTeoria 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:eventos podem ser +/- verdade