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.
2.
3.
4.
Estados parcialmente observáveis (estado das estradas, tráfego, outros planos, etc.)
Sensores ruidosos (relatórios de trafego)
incerteza quanto aos efeitos das ações (pneu furado, etc.)
Grande complexidade em modelar e prever trafego
Assim, um procedimento puramente lógico
1.
2.
Riscaria deduzir algo potencialmente falso: “A25 me levará a tempo””, ou
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 agente
e.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
Cavity = false 0.576 0.08 0.064
0.08
0.02
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
posteriores
e.g., P(carie | dordeDente) = 0.8
i.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
Inferência Probabilística
• 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
• 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ística
inferê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 sse
P(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:
vermelha
branca
Azul
B1
2
3
6
B2
4
2
3
B3
3
4
3
– 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.
• 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?