Incerteza

Capítulo 13

IA - Mestrado FEI

Outline

• incerteza

• Probabilidade

• Sintaxe e Semântica

• Inferência

• Independência e Regra de Bayes

incerteza

Seja a ação At = sair para o aeroporto t minutos antes do vôo.At me levará ao aeroporto a tempo?

Problemas:1. Estados parcialmente observáveis (estado das estradas, tráfego, outros planos, etc.)2. Sensores ruidosos (relatórios de trafego)3. incerteza quanto aos efeitos das ações (pneu furado, etc.)4. Grande complexidade em modelar e prever trafego

Assim, um procedimento puramente lógico 1. Riscaria deduzir algo potencialmente falso: “A25 me levará a tempo””, ou2. Levaria a conclusões muito fracas para tomada de decisões:

“A25 me levará a tempo, se nenhum acidente ocorrer na ponte, e se não chover, e se nenhum pneu furar, e ...”

(A1440 poderia ser um solução lógica razoável, porém eu teria que passar a noite no aeroporto)

Métodos para lidar com incerteza

• Default ou lógica não monotônica:– Assuma que o carro não possua um pneu furado;– Assuma que A25 funcionaria a menos que haja evidência

do contrário;• ! Quais (e quantas) hipóteses são razoáveis? Como

manipular conclusões falhas?

• Regras com fatores de incerteza:– A25 |-> 0.3 chegar ao aeroporto a tempo– mangueira |-> 0.99 grama molhada– Grama molhada |-> 0.7 chuva

• ! Problemas com a combinação de regras contraditórias: A mangueira causa chuva??

Métodos para lidar com incerteza

• Probabilidade– Modela o grau de crença de um agente – Dado evidências disponíveis – A25 chegará ao aeroporto a tempo com probabilidade

0.04• (Fuzzy manipula o grau de veracidade NÃO incerteza.

E.g. “Grama está molhada” é verdade com um grau de 0.2)

Probabilidade

A probabilidade proporciona um meio para resumir a incerteza que vem de nossa:– preguiça: falha em numerar todas as exceções, antecedentes

ou consequêntes para assegurar uma regra sem exceções– ignorância: falta de conhecimento sobre fatos relevantes,

condições iniciais, etc.

Probabilidade subjetiva ou Bayesiana:• Probabilidade se relaciona a proposições sobre o estado

de crença do agentee.g., P(A25 | no reported accidents) = 0.06

Probabilidade

• Proposições probabilísticas não são proposições sobre o mundo!

• Portanto o compromisso ontológico da teoria da probabilidade é o mesmo da lógica clássica:– As sentenças são verdadeiras ou falsas:

• Atribuir prob. 0 (1) a S significa na crença inequívoca de que S é falsa (verdadeira)

– (fuzzy assume um outro compromisso...)

Probabilidade

• A probabilidade de uma sentença depende das percepções que o agente recebeu até o momento (evidências)

• Portanto, probabilidades mudam a partir de novas evidências:– e.g., P(A25 | nenhum acidente, 5 a.m.) = 0.15

[ Isso é análogo à relação de conseqüência lógica:

BC |= a ]

Todas as declarações de probabilidade devem indicar a evidência de acordo com a qual a prob. está sendo avaliada.

Decisões sob incertezas

Suponha o seguinte conjunto de crenças:P(A25 chega a tempo | …) = 0.04

P(A90 chega a tempo| …) = 0.70

P(A120 chega a tempo| …) = 0.95

P(A1440 chega a tempo| …) = 0.9999

• Que ação tomar? Depende de minhas preferências sobre perder o vôo vs. tempo esperando, etc.– Teoria da utilidade representa preferências (todo estado tem um

grau de utilidade) – Teoria da Decisão = teoria da probabilidade + teoria da utilidade

Introdução à probabilidade:

• Proposições: graus de crença são aplicados a proposições (afirmação sobre uma situação)

• Elemento básico: variável aleatória – algo que se refere a uma parte do mundo cujo “status” é inicialmente desconhecido;

• Domínio• V. aleatórias booleanas: e.g., Carie = <verdadeiro, falso>

• V. aleatórias discretas: e.g., Clima possui valores em <ensolarado, chuvoso, nublado, neve>

• V. aleatórias contínuas: e.g., temperatura

– Valores do domínio devem ser exaustivos e mutuamente exclusivos

Introdução à probabilidade: • Evento Atômico: Especificação completa do

estado do mundo sobre o qual o agente está inseguro.– Uma atribuição de valores específicos a

TODAS as variáveis as quais o mundo é formado

– mutuamente exclusivos (no máximo um deles pode ocorrer em cada instante)

– exaustivos: pelo menos um deles tem que ocorrer

Evento atômico: exemplo

Se o mundo consistir somente de 2 var. booleanas Carie e DordeDente, então há quatro eventos atômicos distintos:

Cárie = false ∧DordeDente = false

Carie = false ∧ DordeDente = true

Cárie = true ∧ DordeDente = false

Cárie = true ∧ DordeDente = true

Axiomas de probabilidade

• Para quaisquer proposições A, B– 0 ≤ P(A) ≤ 1

– P(verdade) = 1 e P(falso) = 0 • (proposições neces. verdadeiras -- válidas --

prob=1 e proposições neces. falsas – não satisfatíveis -- prob.=0)

– P(A ∨ B) = P(A) + P(B) - P(A ∧ B)

probabilidade

• A probabilidade de uma proposição é igual à soma das probabilidades dos eventos atômicos em que ela é válida:

P(a) = Σei ∈e(a)P(ei)

• Essa equação fornece um método simples de calcular a probabilidade de qqr proposição dada uma distr. conjunta total que especifique todos os eventos atômicos.

Probabilidade incondicional ou a priori

• É o grau de crença acordado para uma proposição na ausência de quaisquer outras informações

e.g., P(Carie = verdadeiro) = 0.1 and P(Clima = ensolarado) = 0.72

• Distribuição de Probabilidades: todos os valores de uma variável aleatória:P(Clima) = <0.72,0.1,0.08,0.1> (normalizado, i.e., soma da 1)

• Distribuição de probabilidade conjunta: probabilidades de todas as combinações de valores de um conjunto de variáveis aleatórias

P(Clima,Carie) = tabela 4 × 2 de valores:

Weather = sunny rainy cloudy snow Cavity = true 0.144 0.02 0.016 0.02

Cavity = false 0.576 0.08 0.064 0.08

Probabidade incondicional ou a priori

• Uma distribuição conjunta total especifica a probabilidade de todo evento atômico e é, portanto, uma especificação completa da incerteza sobre o mundo.

• Qualquer questão sobre um domínio pode ser respondida a partir de sua distribuição conjunta total.

Probabilidade Condicional ou posterior

• Uma vez que alguma evidência relativa às variáveis aleatórias é conhecida, as prob. a priori não são mais aplicáveis. Em vez disso, devemos usar as probabilidades Condicionais ou posteriorese.g., P(carie | dordeDente) = 0.8i.e., dado que dordeDente é tudo o que se sabe a respeito de carie

• Distribuições condicionais:P(X | Y) = fornece o conjunto de valores de P(X = xi| Y = yj) para cada i, j

possível

• E se sabemos também que cárie é verdade:P(carie | dordeDente,cárie) = 1

• Novas evidências podem ser irrelevantes, – portanto,e.g.,

• P(carie|dordeDente, ensolarado) =P(carie | dordeDente) = 0.8

Probabilidade Condicional

• Podem ser definidas em termos de prob. a priori:P(a | b) = P(a ∧ b) / P(b) if P(b) > 0

• Regra do produto provê uma definição alternativa:P(a ∧ b) = P(a | b) P(b) = P(b | a) P(a)

• Isso pode ser generalizado para distribuições totais: e.g.P(Clima,Carie) = P(Clima | Carie) P(Carie)

• (que é um conjunto de 4 × 2 equações, não uma multiplicação matricial.)

• Regra da cadeia é obtida a partir de aplicações sucessivas 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 Probabilística

• Inferência probabilística: a computação da evidência observada de probabilidades posteriores para proposições de consulta;

• Inferência com o uso de distribuições conjuntas totais: base de conhecimento a partir da qual são derivadas respostas para todas as perguntas.

Inferência Probabilística

• Iniciamos com um exemplo em que Cavity = Carie, Toothache = DordeDente, Catch = Boticão. E a seguinte distribuição conjunta total deste domínio:

• Para qqr proposição a, P(a) é a soma dos eventos atômicos w onde a ocorre: P(a) = ∑

w:w|=aP(w)

Inferência Probabilística

• Iniciamos com um exemplo em que Cavity = Carie, Toothache = DordeDente, Catch = Boticão. E a seguinte distribuição conjunta total deste domínio:

• Para qqr proposição a, P(a) é a soma dos eventos atômicos w onde a ocorre: P(a) = ∑

w:w|=aP(w)

• P(toothache)= 0.108+0.012+0.016+0.064= 0.2

Inferência Probabilística

• Iniciamos com um exemplo em que Cavity = Carie, Toothache = DordeDente, Catch = Boticão. E a seguinte distribuição conjunta total deste domínio:

• Para qqr proposição a, P(a) é a soma dos eventos atômicos w onde a ocorre: P(a) = ∑

w:w|=aP(w)

• P(toothache v carie)= 0.108+0.012+0.016+0.064+0.072+0.008= 0.28

• Podemos calcular probabilidades condicionais:

P(cavity|toothache) = P(cavity ∧ toothache)P(toothache)= 0.016+0.064 0.108+0.012+0.016+0.064= 0.4

Inferência Probabilística

• O denominador pode ser visto como uma constante de normalização α

P(Cavity | toothache) = α P(Cavity,toothache) = α [P(Cavity,toothache,catch) + P(Cavity,toothache, catch)]= α [<0.108,0.016> + <0.012,0.064>] = α <0.12,0.08> = <0.6,0.4>

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

Inferência probabilísticainferência por enumeração

Objetivo: calcular a distribuição de probabilidades das variáveis de consulta X (ex. Cavity), dados valores específicos e (ex. Toothache) para as variáveis de evidência E.

Seja Y as variáveis restantes não observadas (ex. Catch). A consulta P(X|e) pode ser avaliada como:

P(X|e) = αΣy P(X, e, y)

• Note que, juntas, as var. X, E e Y constituem o conjunto completo de var. para o domínio;

• assim, P(X, e, y) é simplesmente um subconjunto de probabilidades a partir da distribuição conjunta total.

Problemas com inf. por enumeração

• Complexidade de tempo (pior caso): O(dn)– Onde d é a cardinalidade do maior domínio e

n é o número de variáveis.

• Complexidade de espaço O(dn) para armazenar a distribuição conjunta

• Como encontrar as probabilidades para

O(dn) elementos??

Independência

• A e B são independentes sseP(A|B) = P(A) ou P(B|A) = P(B) ou P(A, B) = P(A) P(B)

P(Toothache, Catch, Cavity, Weather)= P(Toothache, Catch, Cavity) P(Weather)

• 32 entradas reduzidas a 12; – n lançamentos independentes de moedas O(2n) →O(n)

• Independência absoluta é rara.

• Odontologia é uma área com centenas de variáveis, nenhuma das quais absolutamente independente. O que fazer?

Independência Condicional

• Se eu tenho cárie, a probabilidade do boticão acertar esse dente não depende de minha dor de dente: (1) P(catch | toothache, cavity) = P(catch | cavity)

• A mesma independência ocorre se eu não tiver uma cárie:(2) P(catch | toothache, cavity) = P(catch | cavity)

• I.e. Catch (Boticão) é condicionalmente independente da dordeDente dado Cárie:P(Catch | Toothache,Cavity) = P(Catch | Cavity)

• Sentenças Equivalentes :P(Toothache | Catch, Cavity) = P(Toothache | Cavity)P(Toothache, Catch | Cavity) = P(Toothache | Cavity) P(Catch | Cavity)

Independência Condicional

• Escrevendo toda a distribuição total utilizando a regra da cadeia:P(Toothache, Catch, Cavity)

= P(Toothache | Catch, Cavity) P(Catch, Cavity)= P(Toothache | Catch, Cavity) P(Catch | Cavity) P(Cavity)= P(Toothache | Cavity) P(Catch | Cavity) P(Cavity)

• Na maioria dos caso, o uso da independência condicional reduz o tamanho da representação em distribuição conjunta de exponencial em n para linear em n.

Bayes' Rule

• Da 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)

• Ou na forma da distribuição conjunta: P(Y|X) = P(X|Y) P(Y) / P(X) = αP(X|Y) P(Y)

• Útil para acessar regras probabilísticas de diagnóstico através de probabilidades causais:– P(Cause|Effect) = P(Effect|Cause) P(Cause) / P(Effect)

– E.g., let M be meningitis, S be stiff neck:P(m|s) = P(s|m) P(m) / P(s) = 0.8 × 0.0001 / 0.1 = 0.0008

– Note: posterior probability of meningitis still very small

Regra de Bayes e Independência Condicional

P(Cavity | toothache ∧ catch) = αP(toothache ∧ catch | Cavity) P(Cavity)

= αP(toothache | Cavity) P(catch | Cavity) P(Cavity)

• Este é um exemplo de um modelo de Bayes Ingênuo:P(Cause,Effect1, … ,Effectn) = αP(Cause)x∏iP(Effecti|Cause)

• O número total de parâmetros é linear n

• Ex1 - Assuma varias bolas coloridas contidas em três caixas B1, B2 e B3 distintas e indistinguíveis. As bolas estão distribuídas da

seguinte forma dentro das caixas:

– Uma caixa é selecionada aleatoriamente, dentro da qual uma bola é selecionada aleatoriamente. A bola retirada é vermelha. Qual é a probabilidade posterior da caixa selecionada ser B1? Explique.

B1 B2 B3

vermelha 2 4 3

branca 3 2 4

Azul 6 3 3

• 4) [Uncertainty] (2.0) Sejam as seguintes variáveis:

• F = teve gripe• S = tomou a vacina contra gripe

– Assuma os seguintes resultados médicos:• P(F) = 0.75• P(S) = 0.5• P(F|S) = 0.1

– Dado que você sabe que alguem está com gripe, qual é a probabilidade desta pessoa ter tomado a vacina contra gripe? Explique os seus cálculos.

• (13.11) Suponha que você receba uma bolsa com n moedas imparciais. Você é informado de que n-1 dessas moedas são normais, com cara de um lado e coroa no outro, enquanto uma moeda é falsa, com cara em ambos os lados.– a)Suponha que você enfie a mão na bolsa, escolha

uma moeda uniformemente ao acaso, lance a moeda e obtenha como resultado cara. Qual é a probabilidade (condicional) de que a moeda escolhida seja a moeda falsa?

– b) Suponha que você continue lançando a moeda até um total de k vezes depois de escolhe-la e veja k caras. Qual é a probabilidade condicional desta ser a moeda falsa?