Curso de Inteligência Artificial - Parte 3 -

Incerteza, Cap 13 Ronaldo F. Ramos, Dr. ronaldo@cefet-ce.br

Adaptado de : aima.cs.berkeley.edu

Roteiro ! Incerteza

! Probabilidade

! Sintaxe e Semântica

! Inferência

! Independência e regra de Bayes

Incerteza Seja a ação At = seguir para o aeroporto chegando t minutos antes do vôo Esta ação At nos deixará pontualmente? Problemas:

1.  observalidade parcial (estado da rodovia, planos de outros motoristas, etc.) 2.  sensores de ruído (relatórios com situação do tráfego) 3.  incerteza nos resultados das ações (pneu furado, etc.) 4.  complexidade excessiva da modelagem e previsão do tráfego.

Consequentemente uma abordagem puramente lógica poderia:

1.  correr risco de falsa afirmativa: “A25 me deixará à tempo no aeroporto”, ou 2.  levará a conclusões muitos fracas para tomada de decisões:

“A25 me deixará lá a tempo se não houver acidentes na ponte, se não chover e

meus pneus permanecerem intactos etc etc.” (A1440 pode ser dito razoavelmente que chegarei a tempo, mas eu teria que

permanecer a noite toda no aeroporto …)

Métodos para tratamento da Incerteza !  Logica Default ou não monotônica:

!  Assumir que meu carro não terá um pneu furado !  Assumir que A25 funcionará a não ser que seja contradita pela

evidência !  Questões: Que suposições são razoáveis? Como tratar

contradições?

!  Regras com graus fictícios: !  A25 |→0.3 chegar a tempo !  Irrigador |→ 0.99 GramaMolhada !  GramaMolhada |→ 0.7 Chuva

!  Questões: Problemas com combinações, ex., Irrigador causa chuva??

!  Probabilidade

!  Modela o grau de crença do agente !  Dada uma evidência disponível, !  A25 me deixará a tempo com probabilidade 0.04

Probabilidade Assertivas probabilisticas sumarizam os efeitos de :

!  Preguiça: falha em enumerar exceções, qualificações, etc. !  Ignorância: falta de fatos relevantes, condições iniciais, etc.

Probabilidade Subjetiva: !  Probabilidades relatam proposições sobre o estado

de conhecimento do agente !  ex. P(A25 | não houve acidentes) = 0.06

Isto não são afirmações sobre o mundo.

Probabilidades de proposições podem mudar de acordo com novas evidências: ex., P(A25 | não houve acidentes as 5h)= 0.15

Tomando decisões em face da incerteza Suponha que acreditemos que:

P(A25 me deixará a tempo| …) = 0.04 P(A90 me deixará a tempo|…) = 0.70 P(A120 me deixará a tempo| …) = 0.95 P(A1440 me deixará a tempo| …) = 0.9999

!  Que ação devo escolher?

Dependerá de minhas preferências por vôos não disponíveis vc tempo gasto esperando, etc. !  Teoria da Utilidade é usada para representar e inferir

preferências !  Teoria da Decisão = Teoria da Probabilidade + Teoria da

Utilidade

Sintaxe !  Elemento Básico: variável aleatória

!  Semelhante a logica proposicional: mundos possíveis definidos pela atribuição de valores a variáveis aleatórias.

!  Variables aleatórias booleanas ex., Cárie (tenho cárie?)

!  Variáveis aleatórias discretas ex., Tempo pode ser: <ensolarado,chovendo,nublado,nevando>

!  Valores de domínios devem ser exautivos e mutuamente exclusivos

!  Proposição elementar construída pela atribuição de um valor a A !  Proposições complexas formadas a partir de proposições elementares

e conectivos lógicos padrões. ex. Tempo = ensolarado ∨ Cárie = falso

variável aleatória: ex., Tempo = ensolarado, Cárie = falso (abreviado como cárie)

Sintaxe

! Evento Atômico: Uma especificação completa do estado do mundo sobre o qual o agente é incerto

!  Ex. Se o mundo consiste de apenas duas variáveis aleatórias booleanas Cárie e DorDeDente, então existem 4 possíveis eventos atômicos:

Cárie = falso ∧ DorDeDente = falso Cárie = falso ∧ DorDeDente = verdade Cárie = verdade ∧ DorDeDente = falso Cárie = verdade ∧ DorDeDente = verdade

! Eventos atômicos são mutualmente exclusivos e exaustivos

Axiomas da Probabilidade ! Para quaisquer proposições A, B

! 0 ≤ P(A) ≤ 1 ! P(verdade) = 1 e P(falso) = 0 ! P(A ∨ B) = P(A) + P(B) - P(A ∧ B)

Probabilidade a Priori !  Probabilidade a priori ou probabilidade incondicional de proposições

ex., P(Cárie = verdade) = 0.1 e P(Tempo = ensolarado) = 0.72 corresponde a uma crença inicial antes da chegada de qualquer evidência nova.

!  Distribuição de Probabilidade dá valores para todas possíveis atribuições:

P(Tempo) = <0.72,0.1,0.08,0.1> (normalizado, i.e., soma é 1)

!  Distribuição de probabilidade conjunta para um conjunto de variáveis aleatórias dá a probabilidade de todos os eventos sobre estas variáveis

!  Ex.

P(Tempo,Cárie) = uma matriz 4 × 2 de valores:

Tempo = sol chuva nuvens neve Cárie = verdade 0.144 0.02 0.016 0.02 Cárie = falso 0.576 0.08 0.064 0.08

!  Toda questão a cerca do domínio pode ser respondida pela distribuição de probabilidade conjunta

Probabilidade Condicional !  Probabilidade Condicional ou posterior

!  ex.P(cárie | dordedente) = 0.8 i.e., dado que dordedente é tudo o que sei.

!  Se sabemos mais, ex. que cárie é dada. Então temos:

P(cárie | dordedente,cárie) = 1 !  Novas evidências podem ser irrelevantes, permitindo a

simplificação, ex., P(cárie| dordedente, ensolarado) = P(cárie| dordedente) = 0.8

!  Este tipo de inferência, sancionada pelo conhecimento do domínio é crucial

Probabilidade Condicional !  Definição.

P(a | b) = P(a ∧ b) / P(b) se P(b) > 0

!  A regra do produto dá uma formulação alternativa: P(a ∧ b) = P(a | b) P(b) = P(b | a) P(a)

!  Uma versão geral serve para distribuições inteiras. Ex.,

P(Tempo,Cárie) = P(Tempo | Cárie) P(Cárie) !  (Visto como um conjunto de 4 × 2 equações, não é

multiplicação de matrizes)

!  Regra da Cadeia é derivada por sucessivas aplicações da regra do produto: P(X1, …,Xn) = P(X1,...,Xn-1) P(Xn | X1,...,Xn-1) = P(X1,...,Xn-2) P(Xn-1 | X1,...,Xn-2) P(Xn | X1,...,Xn-1) = … = πi=1

n P(Xi | X1, … ,Xi-1)

Inferência por enumeração !  Começa com a distribuição de probabilidade

conjunta: !  Para qualquer proposição soma-se o eventos

atômicos onde a mesma é verdade. P(carie=verdade)=0,108+0,012+0,072+0,008=0,2 (Chamada de probabilidade marginal) Podemos também calcular P(carie v dordedente) =

0,108+0,012+0,072+0,008+0,016+0,064=0,28. etc.

0,108 0,012 0,072 0,0080,016 0,064 0,144 0,576

DordeDente ~DordeDenteBoticão ~Boticão Boticão ~Boticão

Cárie~Cárie

Inferência por enumeração !  Iniciar com a distribuição conjunta: !  Pode calcular também as probabilidades

condicionais: P(¬cárie | dordedente) = P(¬cárie ∧ dordedente) P(dordedente) = 0.016+0.064 0.108 + 0.012 + 0.016 + 0.064 = 0.4

Normalização

!  Denominador pode ser visto como uma constante de normalização

P(Cárie | DorDeDente) = α P(Cárie,DorDeDente) = α [P(Cárie,DorDeDente,Boticão) + P(Cárie,DorDeDente,¬

Boticao)] = α [<0.108,0.016> + <0.012,0.064>] = α <0.12,0.08> = <0.6,0.4>

Idéia geral: Calcular a distribuição sobre a variável de consulta fixando as variáveis de evidência e somando as variáveis ocultas.

Inferência por enumeração Normalmente estamos interessandos:

Na distribuição conjunta posterior das variáveis de consulta Y sendo dados valores específicos (e) para as variáveis de evidência E

Sejam as variáveis ocultas H = X - Y - E Então a totalização esperada dos valores da distribuição conjunta é

realizada pela soma das variáveis ocultas: P(Y | E = e) = αP(Y,E = e) = αΣhP(Y,E= e, H = h)

!  Os termos são partes da distribuição conjunta pelo fato de que Y, E e

H juntos são exaustivos dentro do conjunto de variáveis aleatórias.

Problemas óbvios: 1.  Complexidade do pior caso é O(dn) onde d é a maior aridade (domínio da

variável aleatória) 2.  Complexidade de espaço é O(dn) para armazenamento da distribuição

conjunta 3.  Como encontrar valores para elementos de entrada em ordem O(dn)?

Independência !  A e B são independentes sse:

P(A|B) = P(A) ou P(B|A) = P(B) ou P(A, B) = P(A) P(B) P(DorDeDente, Boticão, Cárie, Tempo)

= P(DorDeDente, Boticão, Cárie) P(Tempo)

!  32 entradas foram reduzidas a 12; !  Para n moedas independentes (não “viciadas “) teríamos O(2n) →O(n) (! reduzida)

!  Independência Absoluta é poderosa, mas rara. !  Odontologia é um campo amplo com centenas de variáveis ,

nenhuma das quais é independente. O que fazer?

Independência Condicional !  P(DorDeDente, Cárie, Boticão) tem 23 – 1 = 7 entradas

independentes

!  Se temos cárie, a probabilidade de ter que usar o boticão não depende do fato de termos dor de dente. (1) P(boticão | dordedente, cárie) = P(boticão | cárie)

!  O memos ocorre se não temos cárie: (2) P(boticão | DorDeDente,¬cárie) = P(boticao | ¬cárie)

!  Boticao é condicionalmente independente de DorDeDente dado Cárie

!  Declarações equivalentes:

P(DorDeDente | Boticao, Cárie) = P(DorDeDente | Cárie) P(DorDeDente, Boticao | Cárie) = P(DorDeDente | Cárie) P(Boticao| Cárie)

Independência condicional-cont !  Escreve-se uma Distribuição conjunta completa

usando a regra da cadeia.

P(DorDeDente, Boticão, Cárie) = P(DorDeDente | Boticão, Cárie) P(Boticão, Cárie) = P(DorDeDente | Boticão, Cárie) P(Boticão | Cárie) P(Cárie) = P(DorDeDente | Cárie) P(Boticão | Cárie) P(Cárie)

I.e., 2 + 2 + 1 = 5 números independentes

!  Na maioria dos casos a independência reduz o tamanho da representação da distribuição conjunta de exponencial para linear em n .

Regra de Bayes !  Regra do produto: P(a∧b) = P(a | b) P(b) = P(b | a) P(a)

⇒ Regra de Bayes: P(a | b) = P(b | a) P(a) / P(b)

!  Na forma de distribuição: P(Y|X) = P(X|Y) P(Y) / P(X) = αP(X|Y) P(Y)

!  Útil para determinação de uma probabilidade de diagnóstico a partir da probabilidade causal: !  P(Causa|Efeito) = P(Efeito|Causa) P(Causa) / P(Efeito) !  E.g., seja M para o fator de alguém estar com meningite, S

para ter o percoço rígido: P(m|s) = P(s|m) P(m) / P(s) = 0.8 × 0.0001 / 0.1 = 0.0008

Regra de Bayes e Independência Condicional

P(Cárie | DorDeDente ∧ Boticão) = αP(DorDeDente ∧ Boticão | Cárie) P(Cárie) = αP(DorDeDente | Cárie) P(Boticão | Cárie) P(Cárie)

!  Modelo de Bayes Ingênuo (Naïve): (IDIOTA) P(Causa,Efeito1, … ,Efeiton) = P(Cause) πiP(Effecti|Cause)

Número total de Parâmetros é linear em n

Redes Bayesianas !  Def: Notação gráfica para declarações de independência

condicional e consequentemente para uma especificação

compacta de distribuições conjuntas complexas

!  Sintaxe:

!  Um conjunto de “nós”, um por variável !  Um grafo direcional acíclico mostrando influencias diretas !  Uma distribuição condicional para cada nó dado seu pais

P (Xi | Pais (Xi))

!  No caso mais simples, a distribuição condicional é representada como uma tabela de

prabilidade condicional dando a distribução sobre Xi para cada combinação de valores dos

pais

Exemplo de Rede Bayesiana

!  A topologia da rede codifica as declarações de independência condicional:

!  Tempo é independente de outras variáveis

!  DorDeDente and Boticão são condicionalmente

independentes dada cárie

Exemplo de Rede Bayesiana

!  A topologia da rede codifica as declarações de independência condicional:

!  Tempo é independente de outras variáveis

!  DorDeDente and Boticão são condicionalmente

independentes dada cárie

Exemplo do Alarme

Alguém estando no trabalho recebe o telefone do vizinho João Rapadura dizendo que o alarme da casa está tocando, mas a vizinha do outro lado Maria Amargura não ligou.Algumas vezes o alarme é disparado por pequenos tremores de terra. Será que tem um ladrão na casa? Variáveis: Ladrão, Terremoto, Alarme,JoaoLiga, MariaLiga A rede reflete o conhecimento "causal":

Um ladrão(burglar) pode disparar o alarme Um terremoto (earthquake) pode disparar o alarme O Alarme pode fazer Maria(Mary) telefonar O Alarme pode fazer Joao(John) telefonar

A rede!

Compactação da Rede !  Uma tabela com variáveis aleatórias booleanas Xi com k

parentes booleanos terá 2k linhas para a combinação de valores

dos pais

!  Cada linha requererá um valor p para Xi = Verdade

(o valor para Xi = false é 1-p)

!  Se cada variável não tem mais que k pais, a rede completa fará

O(n · 2k) valores

!  I.e., cresce linearmente com n, vs. O(2n) para a distribuição

conjunta total

!  Para a rede do alarme teremos 1 + 1 + 4 + 2 + 2 = 10 valores

(vs. 25-1 = 31)

Semântica da Rede A distribuição conjunta total é definida como o produto

das distribuições condicionais locais

P (X1, … ,Xn) = πi = 1 P (Xi | Pais(Xi))

e.g., P(j ∧ m ∧ a ∧ ¬b ∧ ¬e)

= P (j | a) P (m | a) P (a | ¬b, ¬e) P (¬b) P (¬e)

Rede não puramente causal !  Vamos usar o exemplo do alarme com a seguinte ordem de

inserção dos nós: !  MaryCalls, JohnCalls, Alarme, Roubo e Terremoto.

Roubo Terremoto

Alarme

JohnCalls

MaryCalls

Redes não puramente causais

" Problemas: "  A figura possui duas conexões a mais "  julgamento não natural e difícil das probabilidades

"   Tendo uma rede puramente causal, teríamos um número menor de conexões

Tipos de Inferência em Redes Bayesianas

Roubo Alarme JohnCalls

Evidência Query

JohnCalls Alarme Roubo

Evidência Query

Causal – Causa para efeito " P(JohnCalls/Roubo) = 0,86

Diagnóstico – Efeito para Causa "  P(Roubo/JohnCalls) = 0,016

Roubo Alarme Terremoto

Query Evidência

!  Intercausal (entre causas com um efeito comum) !  P(Roubo/Alarme) = 0,376 !  P(Roubo/Alarme ∧Terremoto) = 0,373

Tipos de Inferências

"  Mista (combinando duas ou mais das de cima) "   P(Alarme/JohnCalls ∧¬Terremoto) = 0,03 "   Este é um uso simultâneo de inferência causal e diagnóstico.

JohnCalls Alarme Terremoto Evidência Evidência Query

Independência de Novo •  Dependências •  Intuitiva. •  Dois nós conectados

influenciam um ao outro simetricamente.

•  Independências •  Exemplo: I (J;M|A),

I(B;E) •  Outros I(B;E|A)? •  -- d-seperation. •  (Separação Direcional)

Separação -d

M e B são separados-d Dado A (Independentes)

B A M

Separação –d - Divergente

M e J são separados-d Dado A (Independentes)

A

J M

Influencia pode ocorrer de J em M se não conhecemos A

mas I(J;M|A)

Separação –d – convergente

E e B são separados-d NÃO Dado A (Independentes)

E B

A

E não pode influenciar B dado que A não é conhecido.

I(E;B)

Consultas (Query)

∑AE

BPJMABEP,

)(/)),,,,((

Informações interessantes das probabilidades conjuntas: Qual a probabilidade de ambos Maria e John ligarem se acontecer um roubo? P(M, J|B) Qual a mais provável explicação para o fato que Maria Ligou? Pode ser Respondido por Inferência na RB P(M,J|B)=P(B, M, J)/P(B) =

•  Idéia: Somar uma variável por vez, gerando uma nova distribuição em relação as outras variáveis conectando com a variável eliminada.

•  Quando Elimina-se E gera-se uma distribuição de A e B •  Alta Complexidade (NP-HARD) usar Algoritmos de Formação

de Agrupamentos /Árvores de Junção

Algoritmo de Eliminação de Variáveis – Inferência Exata

Inferência Aproximada ! Amostagem direta ! Amostragem de rejeição ! Ponderação de probabilidade ! Simulação de Cadeias de Markov-

Algoritmo CMMC (Cadeia de Markov Monte Carlo)

Modelos Temporais

R t-1 P(Rt)

V 0,7

F 0,3

R t-1

U t-1

R t

U t

R t+1

U t +1

R t P(Ut)

V 0,9

F 0,2

Modelos Temporais

Hipótese de Markov: Estado atual depende apenas de um histórico finito de estados anteriores. Processos de Markov ou Cadeias de Markov Processo de Markov de Primeira Ordem:

P(Xt|X0:t-1) = P(Xt|Xt-1)

Usos: Filtragem, monitoramento e suavização

Modelos Temporais

! Redes bayesianas dinâmicas !  Casos especiais:

!  MOM – Modelos Ocultos de Markov !  Filtros de Kalman !  Etc.

! Aplicações em PDS/Voz, Imagem, etc

! Fica para a próxima .........................