43
Aprendizado Bayesiano Disciplina: Agentes Adaptativos e Cognitivos

Aprendizado Bayesiano

  • Upload
    tea

  • View
    53

  • Download
    0

Embed Size (px)

DESCRIPTION

Aprendizado Bayesiano. Disciplina : Agentes Adaptativos e Cognitivos. Conhecimento com Incerteza. Exemplo: sistema de diagnóstico odontológico Regra de diagnóstico " p sintoma (p,dor de dente) Þ doença (p,cárie) A doença (causa do sintoma) pode ser outra. Regra causal - PowerPoint PPT Presentation

Citation preview

Page 1: Aprendizado Bayesiano

Aprendizado BayesianoDisciplina: Agentes Adaptativos e Cognitivos

Page 2: Aprendizado Bayesiano

Exemplo: sistema de diagnóstico odontológicoRegra de diagnóstico

" p sintoma (p,dor de dente) Þ doença (p,cárie) A doença (causa do sintoma) pode ser outra.

Regra causal " p doença (p,cárie) Þ sintoma (p,dor de dente) Há circunstâncias em que a doença não provoca o

sintoma.

A conexão entre antecedente e conseqüente não é uma implicação lógica em nenhuma direção

Conhecimento com Incerteza

Page 3: Aprendizado Bayesiano

Falha no domínio de diagnóstico médico devido a:

“preguiça”: existem causas ou conseqüências demais a considerar

ignorância teórica e prática: não existe uma teoria completa para o domínio, nem

podemos fazer todos os testes necessários para o diagnóstico perfeito.

Nestes casos, o conhecimento pode apenas prover um grau de crença nas sentenças relevantes.

P(Cárie/Dor de Dente) = 0.6

Conhecimento com Incerteza

Page 4: Aprendizado Bayesiano

Aprendizagem BayesianaFornece probabilidades para suas respostasPermite combinar facilmente conhecimento a priori com dados de treinamentoMétodos práticos e bem sucedidos para aprendizagem Aprendizagem Bayesiana Ingênua Aprendizagem de Redes Bayesianas

Page 5: Aprendizado Bayesiano

Teoria da ProbabilidadeAssocia às sentenças um grau de crença numérico entre 0 e 1

Contudo, cada sentença ou é verdadeira ou é falsaGrau de crença (probabilidade):

a priori (incondicional): calculado antes do agente receber percepções

Ex. P(cárie= true) = P(cárie) = 0.5 condicional: calculado de acordo com as evidências

disponíveis (permite a inferência) evidências: percepções que o agente recebeu até

agora Ex: P(cárie|dor de dente)= 0.8

P(cárie|~dor de dente)= 0.3

Page 6: Aprendizado Bayesiano

Probabilidade condicional Regra do produto: P(A|B) = P(A^B) , quando P(B) > 0.

P(B)

Regra de Bayes P(A/B) = P(B/A)P(A)

P(B)

Page 7: Aprendizado Bayesiano

Aplicação da Regra de Bayes: Diagnóstico Médico

• Seja

M=doença meningite

S= rigidez no pescoço• Um Doutor sabe:

P(S/M)=0.5

P(M)=1/50000

P(S)=1/20

P(M/S)=P(S/M)P(M)

P(S)

=0,5*(1/50000)=0,002

1/20• A probabilidade de uma

pessoa ter meningite dado que ela está com rigidez no pescoço é 0,02% ou ainda 1 em 5000.

Page 8: Aprendizado Bayesiano

Classificador Bayesiano Ingênuo

Suponha uma função de classificação f: X V, onde cada instância x é descrita pelos atributos {a1, , an}

O valor mais provável de f(x) é

)()/,,(maxarg),,(

)()/,,(maxarg

),,/(maxarg

jjn1Vv

n1

jjn1

Vv

n1jVv

MAP

vPvaaPaaP

vPvaaP

aavPv

j

j

j

Page 9: Aprendizado Bayesiano

Calcular P(vj) a partir dos dados de treinamento é fácil, o problema é calcular a probabilidade P(a1,..., an | vj)

Suposição Bayesiana Ingênua:ou seja, as variáves a1,..., an são independentes

Classificador Bayesiano Ingênuo (NB):

)()/,,(maxarg jjn1Vv

MAP vPvaaPvj

L

i

jijn1 vaPvaaP )/()/,,(

i

jijVv

NB vaPvPvj

)/()(maxarg

Classificador Bayesiano Ingênuo

Page 10: Aprendizado Bayesiano

Estimativa das Probabilidades P(vj) e P(ai/vj) através das freqüências relativas P’(vj) e P’(ai/vj)

Para cada vj P’(vj) estimativa de P(vj) Para cada valor ai de cada atributo a

• P’(ai/vj) estimativa de P(ai/vj)

Classificador de novas instancias(x)

xajij

VvNB

ij

vaPvPv )/(')('maxarg

Classificador Bayesiano Ingênuo

Page 11: Aprendizado Bayesiano

• Dia Tempo Temp. Humid. Vento Jogar

• D1 Sol Quente Alta Fraco Não• D2 Sol Quente Alta Forte Não• D3 Coberto Quente Alta Fraco Sim• D4 Chuva Normal Alta Fraco Sim• D5 Chuva Frio Normal Fraco Não• D6 Chuva Frio Normal Forte Não• D7 Coberto Frio Normal Forte Sim• D8 Sol Normal Alta Fraco Não• D9 Sol Frio Normal Fraco Sim• D10 Chuva Normal Normal Fraco Sim

• D11 Sol Frio Alta Forte ?

Classificador Bayesiano Ingênuo: Exemplo

P(Sim) = 5/10 = 0.5 P(Não) = 5/10 = 0.5P(Sol/Sim) = 1/5 = 0.2 P(Sol/Não) = 3/5 = 0.6P(Frio/Sim) = 2/5 = 0.4 P(Frio/Não) = 2/5 = 0.4P(Alta/Sim) = 2/5 = 0.4 P(Alta/Não) = 3/5 = 0.6P(Forte/Sim) = 1/5 = 0.2 P(Forte/Não) = 2/5 = 0.4P(Sim)P(Sol/Sim) P(Frio/Sim) P(Alta/Sim) P(Forte/Sim) = = 0.0032P(Não)P(Sol/Não)P(Frio/Não)P(Alta/Não) P(Forte/Não) = = 0.0288

Þ Jogar_Tenis (D11) = Não

Page 12: Aprendizado Bayesiano

Algoritmo BayesianoIngênuo: Dificuldades

Suposição de independência condicional quase sempre violada, mas funciona surpreendentemente bem

O que acontece se nenhuma das instancias classificadas como vj tiver o valor ai?

i

jijn1 vaPvaaP )/()/,,(

0)v/a('P)v('P0)v/a('Pi

jijji Þ

Page 13: Aprendizado Bayesiano

Solução típica

n é o número de exemplos para os quais v = vj

nc número de exemplos para os quais v = vj e a = ai

p é a estimativa à priori para P’(ai/vj)

m é o peso dado à priori (número de exemplos “virtuais”)

mnpmn)v/a('P c

ji

Algoritmo BayesianoIngênuo: Dificuldades

Page 14: Aprendizado Bayesiano

Exemplo: Classificação de Documentos

Classificar documentos em duas classes vj = {‘interesse’, ‘não-interesse}

Variáveis a1,..., an são palavras de um vocabulário e P’(ai/vj) é a freqüência com que a palavra ai aparece entre os documentos da classe vj

P’(vj) = número de documentos da classe vj

número total de documentos

Page 15: Aprendizado Bayesiano

P’(ai/vj) = nij + 1 nj + |Vocabulário|

onde nj é o número total de palavras nos documentos da classe vj e nij é o número de ocorrências da palavra ai nos documentos da classe vj.

Usa-se m = |Vocabulário| e p = 1/ |Vocabulário| (assumindo que cada palavra tem a mesmo probabilidade de ocorrência)

Exemplo: Classificação de Documentos

Page 16: Aprendizado Bayesiano

Classificação Final:

Observação: nem sempre a ocorrência de uma palavra independe das outras palavras. Exemplo: ‘Inteligência’ e ‘Artificial’.

xa

jijVv

NBij

vaPvPv )/(')('maxarg

Exemplo: Classificação de Documentos

Page 17: Aprendizado Bayesiano

Redes Bayesianas

Representa 3 tipos de conhecimento do domínio: Relações de independência entre atributos (ou

variáveis) Probabilidades a priori de alguns atributos Probabilidades condicionais entre atributos

dependentes Permite calcular eficientemente: Probabilidades a posteriori de qualquer atributo

(inferência)

Conhecimento representado: Na estrutura da rede e nas distribuições de

probabilidade das variáveis

Page 18: Aprendizado Bayesiano

Estrutura das Redes Bayesianas

Uma Rede Bayesiana é um grafo acíclico onde: Cada nó da rede representa uma variável Um conjunto de ligações ou arcos dirigidos

conectam pares de nós Cada nó recebe arcos dos nós que tem influência direta

sobre ele (nós pais). Cada nó possui uma tabela de probabilidade

condicional que quantifica os efeitos que os pais têm sobre ele

Page 19: Aprendizado Bayesiano

Redes BayesianasTempestade Ônibus de Turismo

Fogo no Acampamento

Trovão Fogo na floresta

Raio

T,O T,O T, O T, O

FA 0.4 0.1 0.8 0.2FA 0.6 0.9 0.2 0.8

Fogo no Acampamento

Distribuição de Probabilidade:P(FA/T,O)

Page 20: Aprendizado Bayesiano

Redes BayesianasRepresenta a distribuição de probabilidade conjunta entre todas as variáveis: P(y1^...^yn) Exemplo: P(Tempestade, , Fogo na Floresta)? Exemplo: P(Classe=C1 ^ Atrib1=10 ^ Atrib2=Yes)?

Cálculo da probabilidade conjunta:

Onde Predecessores(Yi) significa predecessores imediatos de Yi no grafo

n

1iiin1 ))Y(sedecessorePr/y(P)y,,y(P

Page 21: Aprendizado Bayesiano

Distribuição de Probabilidade Conjunta

Sejam Y1, Y2,...Yn um conjunto de variáveis.

Evento atômico: uma especificação completa dos estados do domínio

Y1= y1,Y2 = y2,....,Yn= yn

A distribuição de probabilidade conjunta, P(Y1,Y2,...,Yn),

atribui probabilidades a todos os possíveis eventos atômicos

Page 22: Aprendizado Bayesiano

Exemplo: Probabilidade Conjunta

cárie

cárie

dor de dente dor de dente

0.04

0.01

0.06

0.89

P(cárie ^ dor de dente)=?P(cárie)=?P(dor de dente)=?P(cárie/dor de dente)=?

Page 23: Aprendizado Bayesiano

Teorema da Multiplicação de Probabilidades

Esse resultado permite calcular a probabilidade de ocorrênciasimultânea de vários eventos a partir das probabilidadescondicionais.

P(y1^...yn) = P(yn / y1^...yn-1) ... P(y2 / y1) P(y1)

P(y1^...yn) = P(yn / y1^...yn-1) ... P(y1^...yn-1)

Page 24: Aprendizado Bayesiano

Independência: P(A|B) = P(A) Exemplo: A = dor de dente e B=úlcera

Úlcera não causa dor de denteIndependência condicional X e Y são independentes dado Z => P(X|Y,Z) =

P(X|Z) Se o objetivo é saber a probabilidade de X então

tanto faz o valor de Y se você já sabe o valor de Z

Exemplo: Trovão é condicionalmente independente de Chuva, dado Relâmpago P(Trovão/ Chuva, Relâmpago) = P(Trovão/

Relâmpago)

Independência Condicional

Page 25: Aprendizado Bayesiano

Redes Bayesianas: Cálculo da Probabilidade

Conjunta Redes Bayesianas levam em consideração a

Independência Condicional entre subconjuntos de variáveis

P(y1^...yn) = P(yn / y1^...yn-1) ... P(y2 / y1) P(y1)

P(yn / Predecessores(Yn)) P(y2 / Predecessores(Y2)

n

1iiin1 ))Y(sedecessorePr/y(P)y,,y(P

Page 26: Aprendizado Bayesiano

Exemplo Alarme (AIMA)

Roubo Terremoto

Alarme

JohnCalls MaryCalls

P(T)0,002

P(R)0,001

R T P(A) T T 0,95 T F 0,94 F T 0,29 F F 0,001

A P(J ) T 0,90 F 0,05

A P(M) T 0,70 F 0,01

Page 27: Aprendizado Bayesiano

Calcular a probabilidade do evento que o alarme toca mas não houve assalto nem terremoto e que João e Maria telefonaram.

P(J M A ~R ~T)= P(J|A) P(M|A) P(A|~R ~T )P(~R)P(~T)= 0.9 x 0.7 x 0.001 x 0.999 x 0.998= 0.00062 ou 0.062 %

Exemplo Alarme (AIMA)

Page 28: Aprendizado Bayesiano

Construção de Redes Bayesianas

1. Escolher um conjunto de variáveis relevantes que descrevam o domínio

2. Ordem de inclusão dos nós na rede (a). causas como “raízes” da rede (b). variáveis que elas influenciam (c). folhas, que não influenciam diretamente nenhuma outra variável.

3. Enquanto houver variáveis a representar: (a). escolher uma variável Xi e adicionar um nó para ela na rede (b). estabelecer Pais(Xi) dentre os nós que já estão na rede, satisfazendo a propriedade de dependência condicional (c). definir a tabela de probabilidade condicional para Xi

Page 29: Aprendizado Bayesiano

Exemplo Alarme (AIMA)

Roubo Terremoto

Alarme

JohnCalls MaryCalls

P(T)0,002P(R)

0,001

R T P(A) T T 0,95 T F 0,94 F T 0,29 F F 0,001

A P(J ) T 0,90 F 0,05

A P(M) T 0,70 F 0,01

Ordem: R T A J M

Page 30: Aprendizado Bayesiano

Exemplo de Rede Bayesiana 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.

RouboTerremoto

Alarme

JohnCalls

MaryCalls

Page 31: Aprendizado Bayesiano

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

Exemplo de Rede Bayesiana Não Puramente Causal

Page 32: Aprendizado Bayesiano

Exercício: Construa uma rede para o problema abaixo

Eu quero prever se minha esposa está em casa antes de eu abrir a porta. Eu sei que minha esposa liga a luz quando

chega em casa mas às vezes ela também liga ao sair (se ela for

retornar com alguma visita). Quando não tem ninguém em casa, ela

solta o cachorro no quintal mas às vezes ela solta o cachorro quando ele

está molhado. Quando o cachorro está solto, consigo ouvir

o seu latido da rua mas as vezes o confundo com o cachorro da

vizinha.

Page 33: Aprendizado Bayesiano

Aprendizagem de Redes Bayesianas

Variantes da tarefa de aprendizagem A estrutura da rede pode ser conhecida ou

desconhecida O conjunto de treinamento pode fornecer valores

para todas as variáveis da rede ou para somente algumas

Se a estrutura é conhecida e todas as variáveis observadas Então é tão fácil como treinar um classificador

Bayesiano ingênuo

Page 34: Aprendizado Bayesiano

Suponha a estrutura conhecida e variáveis parcialmente observáveisExemplo: Observa-se fogo na Floresta, Tempestade,

Ônibus de turismo, mas não Raio, Fogo no Acampamento

Aprende-se a tabela de probabilidades condicionais de cada nó usando o algoritmo do gradiente ascendente

O sistema converge para a rede h que maximiza localmente ln (P(D/h))

Aprendizagem de Redes Bayesianas

Page 35: Aprendizado Bayesiano

ExemploTempestade Ônibus de Turismo

Fogo no Acampamento

Trovão Fogo na floresta

Raio

T,O T,O T, O T, O

FA ? ? ? ?FA ? ? ? ?

Fogo no Acampamento

Distribuição de Probabilidade:P(FA/T,O)

Page 36: Aprendizado Bayesiano

Gradiente Ascendente para Redes Bayesianas

Seja wijk uma entrada na tabela de probabilidade condicional para a variável Yi na rede wijk = P(Yi = yij/Predecessores(Yi) = lista uik de valores) Exemplo, se Yi = Fogo no Acampamento, então uik pode

ser {Tempestade = T, Ônibus de Turismo = O}Aplicar o gradiente ascendente repetidamente Atualizar todos os wijk usando os dados de treinamento D

Normalizar os wijk para assegurar

e

Dd ijk

ikijhijkijk w

duyPww

)/,(

1wj

ijk 1w0 ijk

Page 37: Aprendizado Bayesiano

Aprendizagem da Estrutura de Redes Bayesianas

Métodos baseados em Busca e Pontuação Busca no espaço de estruturas Cálculo das tabelas de probabilidade para cada

estrutura Definição da medida de avaliação (Pontuação)

Ex.: Minimum Descrition Length (MDL) Operadores de busca (adição, remoção ou reversão

de arcos da rede) Processo de busca prossegue enquanto a pontuação

de uma rede for significativamente melhor que a anterior

Ex: K2(Cooper e Herskovits, 1992)

Page 38: Aprendizado Bayesiano

Aprendizagem da Estrutura de Redes Bayesianas

Métodos baseados em análise de dependência

Arcos são adicionados ou removidos dependendo de um teste de independência condicional entre os nós

Teste de independência pode ser feito entre pares de nós ou com um conjuntos maior de variáveis condicionais

Ex: CDL(Chen, Bell e Liu 1997)

Page 39: Aprendizado Bayesiano

Aprendizagem da Estrutura de Redes Bayesianas

Métodos baseados em Busca e Pontuação Vantagem: Menor complexidade no tempo Desvantagem: Não garante encontrar melhor

solução

Métodos baseados em análise de dependência Vantagem: Sob certas condições, encontra a melhor

solução Desvantagem: Teste de independência com uma

quantidade muito grande de variáveis pode se tornar inviável

Page 40: Aprendizado Bayesiano

Aplicações de Redes Bayesianas

PATHFINDER: diagnóstico de doenças que atacam os nodos linfáticos. (Russel&Norvig 1995)

PAINULIM: diagnóstico de doenças neuro-musculares: http://snowhite.cis.uoguelph.ca/faculty_info/yxiang/research.html

Tutores inteligentes: www.pitt.edu/~vanlehn/andes.html

Page 41: Aprendizado Bayesiano

Mais aplicações: http://excalibur.brc.uconn.edu/~baynet/researchApps.htm

Análise de proteínasModelagem de Agentes InteligentesDetecção de fraudes na indústriaRobótica

Aplicações de Redes Bayesianas

Page 42: Aprendizado Bayesiano

Conclusões Possibilidade de trabalhar com domínios onde não há informação suficiente

Raciocínio probabilístico trata o grau de incerteza associado à maioria dos domínios.

Combina conhecimento a priori com dados observados

O impacto do conhecimento a priori (quando correto) é a redução da amostra de dados necessários

Page 43: Aprendizado Bayesiano

BibliografiaRussel, S, & Norvig, P. (1995). Artificial Intelligence: a Modern Approach (AIMA) Prentice-Hall. Pages 436-458, 588-593

Mitchell, T. & (1997): Machine Learning, McGraw-Hill. Cap.6

Fayyad et al. (1996): Advances in knowledge discovery and data mining, AAAI Press/MIT Press. Cap.11

Pearl, J. (1988) Probabilistic Reasoning in Inteligent Systems