IF67B C71 aula15

Prévia do material em texto

IF71B-C71 - Inteligeˆncia Artificial
Aula 15- Redes Bayesianas
Profa. Dra. Priscila T iemi çaeda Saito
k psaito@utfpr.edu.br
2o Semestre 2016
29/09/16
Roteiro
1 Redes Bayesianas
2 Teorema de Bayes
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 2 / 38
Introduc¸a˜o
Em muitos problemas reais na˜o ha´ informac¸o˜es completas sobre o
ambiente
I falha na coleta dos dados
I imprecisa˜o do aparelho de coleta
I impossibilidade de obtenc¸a˜o de informac¸a˜o
I incerteza sobre as relac¸o˜es do dom´ınio
Lidar com incerteza
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 3 / 38
Exemplo
Hora´rio de filme
I informac¸a˜o perfeita
F o filme comec¸a a`s 8h15min
I informac¸a˜o imprecisa
F o filme comec¸a entre 8h e 9h
I informac¸a˜o incerta
F eu acho que o filme comec¸a a`s 8h (mas na˜o tenho certeza)
I informac¸a˜o vaga
F o filme comec¸a la´ pelas 8h
I informac¸a˜o probabilista
F e´ prova´vel que o filme comece a`s 8h
I informac¸a˜o possibilista
F e´ poss´ıvel que o filme comece a`s 8h
I informac¸a˜o inconsistente
F Maria disse que o filme comec¸a 8h, Joa˜o disse que ele comec¸a a`s 10h
I informac¸a˜o imcompleta
F eu na˜o sei, mas usualmente os filmes neste cinema comec¸am a`s 8h
I ignoraˆncia total
F eu na˜o fac¸o a menor ideia do hora´rio do filme
Mesmo lidando com esses tipos de informac¸o˜es, conseguimos tomar deciso˜es razoa´veis
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 4 / 38
Incerteza
Informac¸a˜o probabilista
I teoria de probabilidades ou
I teoria da evideˆncia
Informac¸a˜o imprecisa e/ou vaga
I teoria dos conjuntos nebulosos (fuzzy) ou
I teoria dos conjuntos de aproximac¸a˜o
Informac¸a˜o possibilista
I teoria das possibilidades
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 5 / 38
Incerteza
Informac¸a˜o incerta
I teoria das probabilidades ou
I teoria das possibilidades ou
I teoria das evideˆncias
Informac¸o˜es inconsistentes/“incompletas”
I lo´gicas na˜o cla´ssicas
F paraconsistente para informac¸a˜o inconsistente, por exemplo
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 6 / 38
Introduc¸a˜o
O racioc´ınio e a infereˆncia sobre algumas premissas podem, em
diversas situac¸o˜es, denotar um certo grau de certeza
Exemplo:
∀tTraˆnsito(t, congestionamento) ⇒ Tempo(t, chuva)
A sentenc¸a acima indica que, dada a ocorreˆncia de um
congestionamento, e´ poss´ıvel concluir, como consequeˆncia, que ha´
ocorreˆncia de chuva
Imprecisa˜o ⇒ congestionamentos podem ser causados por outros fatores
ale´m da chuva
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 7 / 38
Introduc¸a˜o
Alternativa:
∀tTraˆnsito(t, congestionamento) ⇒ Tempo(t, chuva) ⋃ Tempo(t,
neblina)
⋃
...
Esta regra poderia incluir, no lado direito da sentenc¸a, um nu´mero
extenso de fatores adicionais a` chuva e a` neblina.
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 8 / 38
Introduc¸a˜o
Poderia-se, ainda, baseado em tal racioc´ınio, tentar derivar uma regra
causal:
∀tTempo(t, chuva) ⇒ Traˆnsito(t, congestionamento)
Incorreta ⇒ nem sempre a chuva causa congestionamento;
ocorreˆncia de congestionamento e chuva na˜o precisam estar,
necessariamente, associados um ao outro.
Essas considerac¸o˜es demonstram que tal lo´gica:
I na˜o fornece uma abordagem totalmente adequada para lidar com
problemas em que ha´ algum grau de incerteza
I na˜o e´ poss´ıvel inferir consequencias lo´gicas entre eventos
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 9 / 38
Introduc¸a˜o
Em ambientes de incerteza, onde existem informac¸o˜es parciais
(incompletas) ou informac¸o˜es aproximadas (na˜o exatas), o racioc´ınio
probabil´ıstico pode ser interessante
Probabilidade considerada como o grau de certeza da ocorreˆncia
de um evento
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 10 / 38
Teoria da Probabilidade
Probabilidade incondicional ou a priori: o grau de crenc¸a a respeito
de alguma proposic¸a˜o sem levar em conta qualquer outra informac¸a˜o
P(congestionamento) = 0.15
Probabilidade condicional ou a posteriori: probabilidade de
ocorreˆncia de um evento esta´ condicionada a ocorreˆncia de outros
eventos
P(acidente|chuva) = 0.6
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 11 / 38
Teorema de Bayes
Alguns dom´ınios de problema sa˜o caracterizados pela presenc¸a de
incerteza e pelo racioc´ınio baseado em crenc¸as parciais a respeito
do mundo
Racioc´ınios adequados podem ser feitos por meio de me´todos
Bayesianos
Me´todos Bayesianos fornecem uma abordagem probabil´ıstica para
infereˆncias que levem em considerac¸a˜o aspectos como a
independeˆncia condicional a respeito dos eventos
O Teorema de Bayes e´ a base para a aplicac¸a˜o de me´todos
probabil´ısticos a` Inteligeˆncia Artificial (IA).
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 12 / 38
Teorema de Bayes
Permite calcular a probabilidade condicional de ocorrer um evento X
dado o acontecimento de um evento Y
P(X |Y ) = P(Y |X )·P(X )P(Y )
Sa˜o conhecidas:
I P(X )⇒ probabilidade incondicional de X
I P(Y )⇒ probabilidade incondicional de Y
I P(Y \X )⇒ probabilidade condicional de ocorrer um evento Y dado
que X ocorreu
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 13 / 38
Teorema de Bayes
Considere hipoteticamente:
I P(chuva) = 30%
I P(acidente) = 5%
I P(acidente|chuva) = 10%
Qual a probabilidade de estar chovendo, dada a ocorreˆncia de um
acidente de traˆnsito?
P(chuva|acidente) = P(acidente|chuva)·P(chuva)P(acidente) = 0,1·0,30,05 = 0, 6
Observa-se que a probabilidade de estar chovendo dada a ocorreˆncia
de um acidente e´ alta (60%).
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 14 / 38
Teorema de Bayes
Considere hipoteticamente:
I P(chuva) = 30%
I P(acidente) = 5%
I P(acidente|chuva) = 10%
Qual a probabilidade de estar chovendo, dada a ocorreˆncia de um
acidente de traˆnsito?
P(chuva|acidente) = P(acidente|chuva)·P(chuva)P(acidente) = 0,1·0,30,05 = 0, 6
Observa-se que a probabilidade de estar chovendo dada a ocorreˆncia
de um acidente e´ alta (60%).
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 14 / 38
Teorema de Bayes
Considere hipoteticamente:
I P(chuva) = 30%
I P(acidente) = 5%
I P(acidente|chuva) = 10%
Qual a probabilidade de estar chovendo, dada a ocorreˆncia de um
acidente de traˆnsito?
P(chuva|acidente) = P(acidente|chuva)·P(chuva)P(acidente) = 0,1·0,30,05 = 0, 6
Observa-se que a probabilidade de estar chovendo dada a ocorreˆncia
de um acidente e´ alta (60%).
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 14 / 38
Redes Bayesianas
Abordagem poderosa para construir uma representac¸a˜o de um
dom´ınio que envolva incerteza
Grafos ac´ıclicos e direcionados que representam dependeˆncias entre
varia´veis em um modelo probabil´ıstico
A relac¸a˜o direc¸a˜o das arestas do grafo representa a relac¸a˜o de
causa-consequeˆncia entre as varia´veis
A auseˆncia de aresta entre duas va´ria´veis supo˜e independeˆncia
condicional
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 15 / 38
Redes Bayesianas
A ou B ⇒ prova´veis causas diretas da ocorreˆncia de C
C ⇒ uma prova´vel causa das ocorreˆncias de D e E
A e B ⇒ pais de C , que por sua vez e´ pai de D e E
A e B na˜o teˆm pai ⇒ no´s ra´ızes da rede
BA
C
ED
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 16 / 38
Redes Bayesianas - ExemploTem-se um novo alarme contra roubo instalado em casa
E´ bastante confia´vel na detecc¸a˜o de roubo, mas dispara tambe´m na
ocasia˜o de pequenos terremotos
Tem-se dois vizinhos, Joa˜o e Maria, que prometeram ligar para voceˆ
no trabalho, quando ouvissem o alarme
Joa˜o sempre liga quando ouve o alarme, mas a`s vezes confunde o
telefone com o alarme
Maria, por outro lado, gosta de ouvir mu´sica e a`s vezes na˜o escuta o
alarme
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 17 / 38
Redes Bayesianas - Exemplo
Varia´veis:
I Roubo
I Terremoto
I Alarme
I Joa˜oLiga
I MariaLiga
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 18 / 38
Redes Bayesianas - Exemplo
A topologia da rede reflete o conhecimento “causal”
I um roubo pode ativar o alarme
I um terremoto pode ativar o alarme
I o alarme faz Maria telefonar
I o alarme faz Joa˜o telefonar
TerremotoRoubo
Alarme
MariaLigaJoãoLiga
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 19 / 38
Redes Bayesianas - Exemplo
Roubos ou terremotos afetam diretamente a probabilidade do alarme
tocar
Fato de Joa˜o e Maria ligar depende somente do alarme
A rede apresenta suposic¸o˜es de que eles na˜o percebem quaisquer
roubos diretamente, na˜o notam os terremotos e na˜o verificam antes
de ligar
TerremotoRoubo
Alarme
MariaLigaJoãoLiga
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 20 / 38
Redes Bayesianas - Exemplo
As probabilidades resumem um conjunto potencialmente infinito de
circunstaˆncias:
I Maria ouve mu´sica alta
I Joa˜o liga quando ouve o telefone tocar
I Umidade, falta de energia, entre outros acontecimentos podem
interferir no alarme
I Joa˜o e Maria na˜o esta˜o em casa, entre outros
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 21 / 38
Tabela de Probabilidade Condicional - TPC
Cada linha em uma tabela de probabilidade condicional conte´m a
probabilidade condicional de cada valor do no´ para um caso de
condicionamento
Um caso de condicionamento e´ uma combinac¸a˜o poss´ıvel de valores
para os no´s superiores
TerremotoRoubo
Alarme
MariaLigaJoãoLiga
P(R)
0,001
R
V 0,002
P(T)T
V
A
V
F
P(J) P(M)A
V
F
0,70
0,01
0,90
0,05
R T
0,001
P(A)
0,95
0,94
0,29
V
F
V
F
V
V
F
F
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 22 / 38
Ca´lculo da distribuic¸a˜o de probabilidade conjunta
Com as tabelas de probabilidade condicional calculadas podemos
obter a distribuic¸a˜o de probabilidade conjunta de todo o dom´ınio
Distribuic¸a˜o de probabilidade conjunta ⇒ produto das distribuic¸o˜es
condicionais de todos os no´s dado os valores de seus pais:
P(x1, ..., xn) =
∏
i=1 P(xi\Pais(xi ))
xi ⇒ no´ da rede
Pais(xi )⇒ pais de xi
P(x1, x2, ..., xn)⇒ distribuic¸a˜o de probabilidade conjunta da rede
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 23 / 38
Ca´lculo da distribuic¸a˜o de probabilidade conjunta
Exemplo:
I Qual a probabilidade do alarme disparar sem que um roubo e nem um
terremoto tenha ocorrido, ale´m de ambos, Joa˜o e Maria, ligarem?
TerremotoRoubo
Alarme
MariaLigaJoãoLiga
P(R)
0,001
R
V 0,002
P(T)T
V
A
V
F
P(J) P(M)A
V
F
0,70
0,01
0,90
0,05
R T
0,001
P(A)
0,95
0,94
0,29
V
F
V
F
V
V
F
F
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 24 / 38
Ca´lculo da distribuic¸a˜o de probabilidade conjunta
Exemplo:
I Qual a probabilidade do alarme disparar sem que um roubo e nem um
terremoto tenha ocorrido, ale´m de ambos, Joa˜o e Maria, ligarem?
TerremotoRoubo
Alarme
MariaLigaJoãoLiga
P(R)
0,001
R
V 0,002
P(T)T
V
A
V
F
P(J) P(M)A
V
F
0,70
0,01
0,90
0,05
R T
0,001
P(A)
0,95
0,94
0,29
V
F
V
F
V
V
F
F
P(A ∧ ¬R ∧ ¬T ∧ J ∧M) =
P(J|A)P(M|A)P(A|¬R,¬T )P(¬R)P(¬T )
= 0, 9 · 0, 7 · 0, 001 · 0, 999 · 0, 998
= 0, 00062
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 24 / 38
Construindo uma Rede Bayesiana
1 Escolhe-se um conjunto de varia´veis Xi que descrevem
apropriadamente o dom´ınio
2 Seleciona-se a ordem de distribuic¸a˜o das varia´veis (passo importante)
3 Enquanto ainda existirem varia´veis:
I Seleciona-se uma varia´vel Xi e um no´ para ela
I Define-se Pais(Xi ) para um conjunto m´ınimo de no´s de forma que a
independeˆncia condicional seja satisfeita
I Define-se a tabela de probabilidade para Xi
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 25 / 38
Ordenac¸a˜o para as Varia´veis
Ordem correta em que os no´s devem ser adicionados
I “causas de raiz”
I varia´veis que elas influenciam e assim por diante, ate´ chegar a`s folhas,
que na˜o tem nenhuma influeˆncia causal direta sobre as outras varia´veis
Causas
(Sintomas)
Efeitos
Princ´ıpio minimalista ⇒ quanto menor a rede, melhor ela e´
E se escolhermos a ordem errada?
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 26 / 38
Exemplo de Ordenac¸a˜o Errada
A rede resultante tem dois v´ınculos a mais que a rede original e
exigira´ outras probabilidades para serem especificadas
Alguns dos v´ınculos apresentam relacionamentos teˆnues que exigem
julgamentos de probabilidade dif´ıceis e antinaturais (probabilidade de
terremoto, dados roubo e alarme)
TerremotoRoubo
Alarme
MariaLiga JoãoLiga
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 27 / 38
Infereˆncia em Redes Bayesianas
Infereˆncia Diagno´stica
Infereˆncia Causal
Infereˆncia Intercausal
Infereˆncia Mista
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 28 / 38
Infereˆncia em Redes Bayesianas
Infereˆncia Diagno´stica (de efeitos para causas):
I Dado que Joa˜o liga, qual a probabilidade de roubo?
I Exemplo: P(R|J)
?
E
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 29 / 38
Infereˆncia em Redes Bayesianas
Infereˆncia Causal (partindo das causas para os efeitos):
I Dado o roubo, qual e´ a probabilidade de:
I Joa˜o ligar? P(J|R)
I Maria ligar? P(M|R)
E
?
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 30 / 38
Infereˆncia em Redes Bayesianas
Infereˆncia Intercausal (entre causas de um evento em comum):
I Dado o terremoto e o alarme, qual a probabilidade de roubo?
I Exemplo: P(R|A ∩ T )
?E
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 31 / 38
Infereˆncia em Redes Bayesianas
Infereˆncia Mista (algumas causas e alguns efeitos conhecidos):
I Dado que Joa˜o liga e na˜o existe terremoto, qual e´ a probabilidade de
alarme?
I Exemplo: P(A|J ∩ ¬T )
E
E
?
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 32 / 38
Aplicac¸o˜es
Obter probabilidades de varia´veis;
Tomar deciso˜es baseadas nas probabilidades na rede e func¸o˜es de
custo/utilidade
Analisar grandes quantidades de dados (extrair conhecimentos u´teis
em tomada de deciso˜es; controlar ou prever o comportamento de um
sistema; diagnosticar as causas de um fenoˆmeno)
Utilizadas em va´rios dom´ınios:
I sau´de (diagno´stico me´dico, localizac¸a˜o de genes);
I indu´stria (controle de autoˆmatos ou de roboˆs);
I marketing (minerac¸a˜o de dados, gesta˜o da relac¸a˜o com os clientes);
I gesta˜o (tomada de deciso˜es, gesta˜o de conhecimento e risco)
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 33 / 38
Dificuldade na Aplicac¸a˜o de Redes Bayesianas
Necessidade de conhecimento inicial de muitas probabilidades
incondicionais
I Quando desconhecidas,elas sa˜o muitas vezes estimadas, com base em
conhecimento de especialistas, dados dispon´ıveis previamente e
hipo´teses sobre a forma das distribuic¸o˜es de probabilidades
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 34 / 38
Exerc´ıcio
Em um diagno´stico, o me´dico sabe que:
I meningite faz o paciente ter rigidez no pescoc¸o durante 50% do tempo
I Probabilidade a priori de um paciente ter meningite e´ de 150000
I Probabilidade a priori de qualquer paciente ter rigidez no pescoc¸o e´ 120
P(meningite|rigidez) = ?
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 35 / 38
Exerc´ıcio
Em um diagno´stico, o me´dico sabe que:
I meningite faz o paciente ter rigidez no pescoc¸o durante 50% do tempo
I Probabilidade a priori de um paciente ter meningite e´ de 150000
I Probabilidade a priori de qualquer paciente ter rigidez no pescoc¸o e´ 120
P(meningite|rigidez) = ?
P(M|R) = P(R|M)·P(M)P(R) =
0.5· 1
50000
1
20
= 0.0002
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 36 / 38
Exerc´ıcios
Examinar a rede Bayesiana de crenc¸a exibida na Figura.
Na Figura, cinco no´s representam as seguintes sentenc¸as
I C = que voceˆ ingressara´ em uma faculdade
I S = que voceˆ estudara´
I P = que voceˆ frequentara´ festas
I E = que voceˆ sera´ bem-sucedido nos seus exames
I F = que voceˆ se divertira´
P(c)
0.2
C P(S)
verdadeiro 0.8
falso 0.2
C P(P)
verdadeiro 0.6
falso 0.5
S P P(E)
verdadeiro verdadeiro 0.6
verdadeiro falso 0.9
falso verdadeiro 0.1
falso falso 0.2
P P(F)
verdadeiro 0.9
falso 0.7
Representar a probabilidade de que ingresse na faculdade, estude, e seja bem-sucedido nos exames, mas que na˜o va´ a festas e
nem se divirta
P(C=verdadeira, S=verdadeira, P=falso, E=verdadeiro, F=falso)
P(C, S, ∼ P, E, ∼ F)
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 37 / 38
amiltonjunior
Sticky Note
P (C=V, S=V, P=F, E=V, F=F) = P (C, S, ~P, E, ~F) = P(C) * P(S/C) * P(~P/C) * P(E/S^~P) * P(~F/~P) = 0,2 * 0,8 * (1 - 0,6) * 0,9 * (1 - 0,7) = null0,01728
UTFPR (CP) IF71B-C71 (Inteligeˆncia Artificial) Aula 15 - Redes Bayesianas 38 / 38
	Redes Bayesianas
	Teorema de Bayes