Aprendizado Bayesiano
Disciplina: Sistemas Inteligentes
Aprendizagem Bayesiana
Fornece probabilidades para suas respostas
Permite combinar facilmente conhecimento a priori com dados de observação
Métodos práticos e bem sucedidos para aprendizagem Aprendizagem Bayesiana Ingênua Aprendizagem de Redes Bayesianas
Calcula a probabilidade de diferentes hipóteses a medida que novas evidências são observadas. Seja h : hipótese e D: evidência Objetivo: Calcular P(h/D)
P(h): probabilidade a priori de hP(D): probabilidade a priori de D P(D/h): probabilidade de observar D dado que h aconteceu
P(h /D) = P(D / h)P(h) P(D)
Teorema de Bayes
Exemplo: Classificar Risco- Seguradora de Veículos
Hipóteses: {risco=alto; risco=baixo}
Probabilidades a priori: P(risco = alto) = 0.2 P(risco = baixo) = 0.8
Clientes: sexo = masculino, ou sexo = feminino
Pergunta: Qual a probabilidade a posteriori? Qual a P(risco = alto | sexo = M) ? Qual a P(risco = alto | sexo = F) ?
Evidência ‘sexo = M’: P(risco = alto) = 0.2 P(sexo = M) = 0.6 P(sexo = M / risco = alto) = 0.7
P(risco = alto | sexo = M) =
P(sexo = M / risco = alto) * P(risco = alto) =
P(sexo = M)
= 0.7 * 0.2 / 0.6 = 0.23
P(risco = baixo|sexo=M) = 1 – 0.23 = 0.77
P(h /D) = P(D / h)P(h) P(D)
Exemplo: Classificar Risco- Seguradora de Veículos
Evidência ‘sexo = F’: P(risco = alto) = 0.2 P(sexo = F) = 0.4 P(sexo = F / risco = alto) = 0.3
P(risco = alto | sexo = F) =
P(sexo = F / risco = alto) * P(risco = alto) =
P(sexo = F)
= 0.3 * 0.2 / 0.4 = 0.1
P(risco = baixo|sexo=F) = 1 – 0.1 = 0.9
P(h /D) = P(D / h)P(h) P(D)
Exemplo: Classificar Risco- Seguradora de Veículos
Escolha das Hipóteses
Geralmente, existe um espaço de hipóteses (H), e deseja-se a hipótese (hH) mais provável, observados os dados de treinamento (D)Hipótese de máxima a posteriori hMAP
Hipótese de máxima verossimilhança hML (supondo que P(hi)=P(hj))
)()/(maxarg)()()/(
maxarg
)/(maxarg
hPhDPDP
hPhDP
DhPh
Hh
Hh
HhMAP
)/(maxarg iHh
ML hDPhi
1. Para cada hipótese h H, calcule a probabilidade a posteriori
2. Escolha a hipótese hMAP de maior probabilidade à posteriori
Aprendizagem pelo Método da Força Bruta
)()()/(
)/(DP
hPhDPDhP
)/(maxarg DhPhHh
MAP
Suponha que D é o conjunto de exemplos D = {(x1, f(x1)), (xm, f(xm))}
Cálculo de P(D/h)
P(D/h) = 1, se h é consistente com D (ou seja f(xi) = h(xi), (x1, f(xi)) D)
P(D/h) = 0, caso contrário
Aprendizagem pelo Método da Força Bruta
Escolha P(h) sob a hipótese de distribuição uniforme
h H
P(D) =
onde VSH,D é subconjunto de hipóteses de H consistentes com D
H1
hP )(
|VSH,D| |H|
Aprendizagem pelo Método da Força Bruta
Cálculo da probabilidade a posteriori:
Se h é inconsistente com D
Se h é consistente com D
|VSH,D| |H|
1 |H| 1
|VSH,D|
P(h/D) = P(D/h)P(h) = 1 * =
P(D)
P(h/D) = P(D/h)P(h) = 0 * P(h) = 0
P(D) P(D)
Aprendizagem pelo Método da Força Bruta
Exemplo: Método da Força Bruta
Considere H = {h1, h2, h3, h4}
h1: risco = alto, h2: risco = baixo
h3: se sexo = M então risco = alto senão risco = baixo
h4: se sexo = M então risco = baixo senão risco = alto
Considere exemplo: D1 = {sexo = M, risco = alto}
Então VSH,D1 = {h1, h3}, P(h1|D1) = P(h3|D1) = 0.5 e P(h2|D1) = P(h4|D1) = 0
Considere exemplo: D2 = {sexo = F, risco = baixo}
Então VSH,{D1,D2} = {h3}, P(h3|{D1,D2}) = 1 e P(h1|{D1,D2}) = P(h2|{D1,D2}) = P(h4|{D1,D2}) = 0
Evolução das Probabilidades a Posteriori
• em (a) todas as hipóteses tem a mesma probabilidade
• em (b) e (c) a medida que novos exemplos são adquiridos, a probabilidade a posteriori das hipóteses inconsistentes se tornam nulas, enquanto que a probabilidade a posteriori das hipóteses que restaram no espaço de versões aumenta
P(h) P(h|D1) P(h|D1,D2)
hipóteses(a)
hipóteses(b)
hipóteses(c)
Método da Força Bruta – Observações
Na prática: só funciona quando o conceito verdadeiro está contido no espaço de hipóteses funciona com dados sem ruído
No cálculo da probabilidade P(h/D) pode se levar em consideração
erro obtido pela hipótese h no conjunto D o tamanho da hipótese
Dada uma nova instância x, qual é a sua classificação mais provável? hMAP(x) nem sempre é a classificação mais provável
Considere três hipóteses: P(h1/D) = 0.4, P(h2/D) = 0.3 e P(h3/D) = 0.3
Dada uma nova instância x a ser classificada como alto (+) ou baixo (-):
Suponha: h1(x) = +, h2(x) = - e h3(x) = -
A classificação mais provável de x?
Classificador Bayesiano Ótimo
Se a possível classificação do novo exemplo pode ser qualquer vj V, a probabilidade de que a classificação correta seja vj
Classificação Bayesiana ótima
Hh
iijj
i
DhPhvPDvP )/()/()/(
Hh
iijVv
ij
DhPhvP )/()/(maxarg
Classificador Bayesiano Ótimo
Exemplo P(h1/D) = 0.4, P(-/h1) = 0, P(+/h1) = 1
P(h2/D) = 0.3, P(-/h2) = 1, P(+/h2) = 0
P(h3/D) = 0.3, P(-/h3) = 1, P(+/h3) = 0
Portanto
e
40DhPhPHh
ii
i
.)/()/(
60DhPhPHh
ii
i
.)/()/(
Hh
iijVv
ij
DhPhvP )/()/(maxarg
Classificador Bayesiano Ótimo
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
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 são a1,..., an independentes
Classificador Bayesiano Ingênuo (NB):
)()/,,(maxarg jjn1Vv
MAP vPvaaPvj
i
jijn1 vaPvaaP )/()/,,(
i
jijVv
NB vaPvPvj
)/()(maxarg
Classificador Bayesiano Ingênuo
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)
xa
jijVv
NB
ij
vaPvPv )/(')('maxarg
Classificador Bayesiano Ingênuo
• Dia Tempo Temp. Humid. Vento Dia Tempo Temp. Humid. Vento JogarJogar• 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
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
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”)
mn
pmn)v/a('P c
ji
Algoritmo BayesianoIngênuo: Dificuldades
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
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
Classificação Final:
Observação: nem sempre a ocorrência de uma palavra independe das outras palavras. Exemplo: ‘Inteligência’ e ‘Artificial’.
xa
jijVv
NB
ij
vaPvPv )/(')('maxarg
Exemplo: Classificação de Documentos
Redes Bayesianas
Uma Rede Bayesiana é um grafo acíclico e dirigido onde:
Cada nó da rede representa uma variável aleatória 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 associada que quantifica os efeitos que os pais têm sobre ele
Exemplo
Tempestade Ô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.2
FA 0.6 0.9 0.2 0.8
Fogo no Acampamento
Distribuição de Probabilidade:P(FA/T,O)
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
Suponha a estrutura conhecida e variáveis parcialmente observáveis Exemplo, 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
Exemplo
Tempestade Ô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)
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
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)
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)
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
Conclusões
Aprendizado Bayesiano pode ser usado para determinar as hipóteses mais prováveis dado um conjunto de exemplos
Fornece algoritmos que podem ser usados na prática
Classificador Bayesiano IngênuoRedes Bayesianas
Bibliografia
Russel, S, & Norvig, P. (1995). Artificial Intelligence: a Modern Approach (AIMA) Prentice-Hall. Pages 436-458, 588-593Mitchell, T. & (1997): Machine Learning, McGraw-Hill. Cap.6Fayyad et al. (1996): Advances in knowledge discovery and data mining, AAAI Press/MIT Press. Cap.11Pearl, J. (1988) Probabilistic Reasoning in Inteligent Systems