Objetivo da aprendizagem
Conhecimento em extensão
(exemplos percepção-ação,
características-conceitos, etc.)
Exemplos
dia 29, a Caxangá estava engarrafada
dia 30, a Caxangá estava engarrafada
dia 01, a Caxangá estava engarrafada
dia 03, a Caxangá estava engarrafada
Conhecimento em intenção
(regras definições.)
Hipótese indutiva
Todo dia, a Caxangá está engarrafada
Geber Ramalho
1
Aprendizado indutivo
 Inferência de uma regra geral (hipótese) a partir
de exemplos particulares
• ex. trânsito na caxangá
 Precisão diretamente proporcional à quantidade
de exemplos
 É uma inferência que “preserva a falsidade”
 Pode ser
• incremental: atualiza hipótese a cada novo exemplo
– mais flexível, situada... Porém a ordem de apresentação
é importante (backtracking)
• não incremental: gera h a partir de todo conjunto de
exemplos
– mais eficiente e prática
Geber Ramalho
2
2 Abordagens típicas em
aprendizagem simbólica
 Árvores de decisão: inductive decision trees (ID3)
•
•
•
•
Lógica de ordem 0+ (atributo/valor)
Fáceis de serem implementadas e utilizadas
aprendizagem não incremental
estatística (admite exceções)
 Espaço de versões (Version space)
•
•
•
•
lógica de primeira ordem & resolução
implementação mais complicada
aprendizagem incremental
indução lógica unicamente
Geber Ramalho
3
Árvore de Decisão
 A partir de um conjunto de propriedades, decide
sim ou não
 Exemplo Soparia (by Carlos Figueira)
• predicado-objetivo: vaiASoparia
• Atributos considerados:
– Sono: Estou com sono?
– Transporte: Tenho como ir de carro? Carona? etc.
– CONIC: Devo estar amanhã cedo no CONIC?
– Álcool: Estou precisando de álcool?
– Sair: Quero sair de casa?
– Fome: Estou com fome?
Geber Ramalho
4
Árvore de Decisão “pensada”
valores
atributo
Sono?
Não.
Sim.
Meio de
transporte?
Carona
CONIC?
Precisa de
álcool?
Sim.
Geber Ramalho
Não.
Não.
CONIC?
Sim.
Não.
Quer sair?
Sim.
Não.
5
ID3: exemplos da soparia
 Atributos: (Sono, Transporte, CONIC, Álcool, Sair,
Fome)-> propriedade-objetivo
•
•
•
•
•
•
•
•
•
•
•
•
E01: (Pouco,Carro,Sim,Sim,Não,Sim) -> Sim!
E02: (Pouco,Carona,Não,Não,Sim,Sim) -> Sim!
E03: (Sim,Carro,Não,Sim,Sim,Sim) -> Não.
E04: (Pouco,Carona,Não,Não,Sim,Não) -> Sim!
E05: (Sim,Outros,Sim,Sim,Sim,Não) -> Não.
E06: (Pouco,Outros,Não,Sim,Não,Sim) -> Não.
E07: (Pouco,Carro,Sim,Não,Sim,Sim) -> Sim!
E08: (Pouco,Carona,Não,Não,Não,Sim) -> Não.
E09: (Sim,Carro,Não,Sim,Sim,Não) -> Não.
E10: (Não,Outros,Sim,Sim,Sim,Sim) -> Sim!
E11: (Não,Carro,Não,Sim,Sim,Não) -> Sim!
E12: (Não,Carona,Não,Sim,Sim,Sim) -> Sim!
Geber Ramalho
6
ID3: conceitos
 Classificação
• aplicação do predicado objetivo p a um exemplo
 Exemplo positivo (ep) e exemplo negativo (en)
• p(ep) = verdadeiro, p(en) = falso
 Conjunto de treinamento
• positivos + negativos
 Objetivo da aprendizagem
• gerar a descrição d de p segundo os atributos dados
• d deve ser consistente (cobre todos positivos e exclui
todos negativos) e preditiva/geral (vai além da
memorização)
• d deve ser a mais simples possível (navalha de
Ockahm)
Geber Ramalho
7
ID3: construção da árvore
 Escolha do melhor atributo
• O que discrimina o maior número de exemplos
• Maior ganho de informação (entropia)
 Candidatos:
• Transporte: Não classifica imediatamente nenhum dos
exemplos
• Sono: Classifica de imediato 6 dos 12 exemplos
• ...
Geber Ramalho
8
Exemplo: atributo transporte
+:E01,E02,E04,E07,E10,E11,E12
- :E03,E05,E06,E08,E09
Transporte?
carro
+: E01,E07,E11
-: E03,E09
Geber Ramalho
carona
+: E02,E04,E12
-: E08
outros
+: E10
-: E05,E06
9
Exemplo: atributo sono
+:E01,E02,E04,E07,E10,E11,E12
- :E03,E05,E06,E08,E09
Sono?
sim
+: - - -: E3, E5, E9
Geber Ramalho
pouco
+: E1,E2,E4, E7
-: E6,E8
não
+: E10,E11,E12
-: - - -
10
Cálculo do ganho de informação
Ganho(A) = I p/p+n, n/p+n -  vi=1(pi+ni)/(pi+ni) I pi/pi+ni, ni/pi+ni
I p/p+n, n/p+n = -p/(p+n) (log2 p/(p+n)) - n/(n+p) (log2 n/(p+n))
Onde
A = atributo
p = positivo
n = negativo
ID3: Algoritmo de aprendizagem
function APRENDIZAGEM_DA_ID3(exemplos,atributos,default) :
árvore de decisão
if (exemplos é vazio) then return default;
else if (todos os exemplos têm a mesma classificação)
then return (a classificação);
elseif (atributos é vazio) then return maioria(exexmplos);
else
melhor <- ESCOLHA_MELHOR_ATRIBUTO(atributos,exemplos);
árvore <- nova árvore com raiz “melhor”;
para cada valor vi de melhor faça
exemplosi <- exemplos onde melhor = vi;
subárvore <- APRENDIZAGEM_DA_ID3(exemplosi,
atributos-{melhor}, maioria(exemplos));
adicione subárvore como um ramo à árvore com
rótulo vi;
return arvore;
Geber Ramalho
12
Árvore de Decisão “Induzida”
+: E1,E2,E4,E7,E10,E11,E12
-: E3, E5, E6, E8, E9
Sono?
+: - - -: E3, E5, E9
Não.
+: E1,E2,E4, E7
-: E6,E8
+: E10,E11,E12
-: - - -
Meio de
transporte?
Sim.
Carona
+: E1,E7
-: - - -
Sim.
Geber Ramalho
+: E2,E4
-: E8
+: - - -: E6
Quer sair?
+: E2,E4
-: - - -
+: - - -: E8
Sim.
Não.
Não.
13
Regras
 É possível mostrar o resultado como regras
lógicas
• toma-se as folhas com conclusão positiva e sobe-se
até a raiz
 Exemplos:
• t Sono(Não,t)  VaiASoparia(t)
• t Sono(Pouco,t)  Transporte(Carro,t) 
VaiASoparia(t)
• t Sono(Pouco,t)  Transporte(Carona,t) 
QuerSair(Sim,t)  VaiASoparia(t)
Geber Ramalho
14
Problemas c/ ID3: Expressividade
 Só pode tratar de um único objeto
• t Sono(Não,t)  VaiASoparia(t)
• t Sono(Pouco,t)  Transporte(Carro,t)  VaiASoparia(t)
 Mais de um... não dá com eficiência
• Ex: “se posso ficar mais indisposto mais tarde, eu vou
logo à soparia”
• t1t2 MesmoDia(t1,t2)  Disposição(t1,d1) 
Disposição(t2,d2)  Maior (d1,d2)  VaiASoparia(t)
• alternativa: atributo possoFicarMaisIndisposto(t)
Geber Ramalho
15
Problemas c/ ID3: Expressividade
 Exemplo: Goal predicate = BomPesquisador (x)
 Como tratar atributos multi-valorados?
• Filiação(José, {USP, Unesp})
 Como tratar atributos numéricos?
• Tem entre 45 e 52 anos
 Como tratar listas ordenandas?
• Formação = {graduação, mestrado, doutorado, pós}
 Como inserir conhecimento a priori?
BR
• Hierarquias conceituais
NE
Geber Ramalho
PE
PB
Norte
AL
CE
16
Problemas gerais: ambigüidade
 Ambigüidade:
• Dois ou mais exemplos com a mesma descrição (em
termos de atributos) mas classificações diferentes
 Causas:
• Ruído
• Atributos insuficientes
 Soluções:
• tratamento estatístico
• indução construtiva
• etc.
Geber Ramalho
17
Problemas gerais: overfitting
 Overfitting (hiper-especialização):
• Evitar encontrar uma “regularidade” muito restrita nos
dados
 Soluções:
• validação cruzada
• poda
Geber Ramalho
18
Validação Cruzada
 Serve para evitar overfitting e para averiguar
robustez dos resultados
 Algoritmo
1) Divide o conjunto de exemplos em dois subconjuntos: conjuntos de treinamento (TR) e de teste
(TE)
2) Usa indução para gerar hipótese H sobre TR
3) Mede percentagem de erro de H aplicada à TE
4) Repete passos 1-3 com diferentes tamanhos de TE e
TR, e tendo elemento escolhidos aleatoriamente
Treinamento
Geber Ramalho
Teste
19
Curva de aprendizagem
Geber Ramalho
20
Exemplos Práticos
 GASOIL
• Sistema de separação de gás-óleo em plataformas de
petróleo
• Sistema de 10 pessoas-ano se baseado em regras
• Desenvolvido em 100 pessoas-dia
 Piloto automático de um Cessna
• Treinado por três pilotos
• Obteve um desempenho melhor que os três
 Mineração de dados
 Recuperação de Informação
Geber Ramalho
21
Aprendendo descrições lógicas
Version space
Geber Ramalho
Aprendendo descrições lógicas
 Dado o Predicado objetivo (unário) P, a tarefa é
• encontrar uma expressão lógica C, equivalente a P, que
classifique os exemplos corretamente
• Hipótese (Hi)  Definição Candidata (Ci)
•  x P(x)  Ci(x)
• é uma dedução!!!!
 Exemplos
Hr: r VaiEsperar(r)  Pessoas(r, Algumas) 
(Pessoas(r,Cheio)   Fome(r)  Tipo(r,Francês))
(Pessoas(r,Cheio)   Fome(r)  Tipo(r,Tailandês) 
Sex/Sab(r))
HS: t VaiASoparia(t)  Sono(Não,t) 
(Sono(Pouco,t)  Transporte(Carona,t)  Conic(Sim,t))
Geber Ramalho
23
Aprendendo descrições lógicas (2/3)
 O que é um exemplo (Xi)?
• objeto em que o predicado objetivo p pode ou não se
aplicar
 representação
• exemplo positivo: Di(Xi)  P(Xi)
• negativo: Di(Xi)   P(Xi)
 Por exemplo...
• Pessoas(X1,Cheio)   Fome(X1)  Tipo(X1,Tailandês)
 Sex/Sab(X1)  VaiEsperar(X1)
Geber Ramalho
24
Aprendendo descrições lógicas (3/3)
 O que é aprender?
• processo de busca por uma boa hipótese Hi no
espaço de hipóteses H
 Idéia:
• reduzir conjunto de hipóteses H1  H2  ...  Hn
testando a consistência através de inferência
(dedução) lógica
• Direção: top-down (geral  específico) ou bottom-up
(específico  geral )
 Problema
• tamanho do espaço de hipóteses
Geber Ramalho
25
Hipóteses...
Exemplo1 +







Exemplo 2 +
Existe um polígono
Existe um polígono hachurado
Existem dois objetos, um sobre o outro
Existem dois objetos & o inferior é um polígono
Existem dois objetos & o inferior está hachurado
Existem dois objetos, dos quais um é um quadrado
....
Geber Ramalho
26
Consistência
 Um exemplo pode ser:
• falso negativo - Se a hipótese diz que deveria ser
negativo mas de fato é positivo
• falso positivo - Se a hipótese diz que deveria ser positivo
mas de fato é negativo
 Por exemplo...
• Diante de Hs:
– t Sono(Pouco,t)  Transporte(Carona,t)  vaiASoparia(t)
• O exemplo E08:
– Sono(Pouco,t1)  Transporte(Carona,t1)  Conic(Não,t1) 
Alcool(Não,t1)  Sair(Não,t1)  Fome(Sim,t1) 
VaiASoparia(t)
• é um falso positivo
Geber Ramalho
27
Busca no espaço de hipóteses
 Existem duas soluções para o problema da
complexidade da busca no espaço de hipóteses
1) busca pela melhor hipótese corrente
2) busca de engajamento mínimo
Geber Ramalho
28
Busca pela melhor hipótese corrente
(Current-best-hypothesis Search)
 Manter uma hipótese única, e ajustá-la quando um
novo exemplo chega a fim de manter a consistência:
Generalizando e especializando
hipótese
inicial
Falso
negativo
Hipótese muito
restritiva
Generalização
Falso
positivo
Hipótese muito
permissiva
Especialização
Generalização/especialização
 (H1  C1)  (H2  C2) (H1 mais geral que H2)
• x C2(x)  C1(x)
• define indução por meio da dedução para usar o poder da
lógica
 Importante: generalização/especialização podem
ser operações sintáticas
• variabilizar/instanciar de uma constante/variável
– Conic(Sim)  Conic(x)
• adicionar/retirar condições: conjunções ou disjunções
– Conic(Sim)  Fome(Sim)  Fome(Sim)
– Conic(Sim)  Fome(Sim)  Fome(Sim)
Geber Ramalho
30
Exemplo do restaurante (aima pag. 534)
Alt = alternativo?
Hun = fome?
Rain = chove?
Geber Ramalho
Bar = tem área de bar?
Pat = vagas livres?
Res = fez reserva?
Fri = é sex ou sábado?
Price = preço?
Est = tempo de espera
31
Exemplos
positivos: X1, X3, X4; negativo: X2
 X1: exemplo inicial
• H1: x VaiEsperar(x)  Alternativo(x)
 X2: falso +
• H2: x VaiEsperar(x)  Alternativo(x) 
Pessoas(x,Alguma)
 X3: falso -
• H3: x VaiEsperar(x)  Pessoas(x,Alguma)
 X4: falso -
• H4: x VaiEsperar(x)  Pessoas(x,Alguma) 
(Pessoas(x,Cheio)  Sex/Sab(x))
 Problema: backtracking
Geber Ramalho
32
Busca de menor engajamento
(Least-Commitment Search)
 Espaço de hipóteses: H1  H2  H3  ...  Hn
 Solução 2:
• Ao invés de uma hipótese, eliminamos unicamente
aquelas inconsistentes com os exemplos até o
momento.
• Assim, cercamos (encurralamos) incrementalmente as
hipóteses boas
• Este conjunto de hipóteses consistentes restantes
chama-se Espaço de Versões.
 Dois conjuntos consistentes de hipóteses
• G-set  borda mais geral
• S-set  borda mais específica
Geber Ramalho
33
Região Inconsistente
G1
G2
G3
...
S2
S3
...
Gn
consistente
Mais Geral
S1
Mais Específico
Região Inconsistente
Sn
Propriedades
 Toda hipótese consistente é mais específica do que algum
membro do G-set e mais geral que algum membro do Sset (ninguém está fora)
 Toda hipótese mais específica que algum membro do Gset e mais geral que algum membro do S-set é uma
hipótese consistente (não há buracos)
 Como atualizar G-set e S-set?
• S-set
– falso+ -> fora
– falso- -> generalizar
(não pode mais especializar)
• G-set
– falso+ -> especializar
– falso- -> fora
Geber Ramalho
(não pode mais generalizar)
35
Exemplo (parte 1)
exemplo
1
2
3
4
5
restaurante
tonho
makro
tonho
club
tonho
[?, ?, ?, ?]
refeicao
Café
Almoço
Almoço
Café
Café
dia
Quinta
Quinta
Sábado
Domingo
Domingo
Custo
Barato
Caro
Barato
Barato
Caro
reação
sim
não
Sim
Não
não
Ex1+: [tonho,café,quinta,barato]
G-set
Ex2-: [macro,almoço,quinta,caro]
[tonho,café,quinta,barato]
S-set
Exemplo (parte 2)
[?, ?, ?, ?]
[tonho, ?,?,?] [?,café,?,?] [?,?,?,barato]
[tonho,café,quinta,barato]
Ex1+: [tonho,café,quinta,barato]
Ex2-: [makro,almoço,quinta,caro]
Ex3+: [tonho,almoço,sábado,barato]
Exemplo (parte 3)
[?, ?, ?, ?]
[tonho, ?,?,?]
[?,?,?,barato]
[tonho,?,?,barato]
Ex1+: [tonho,café,quinta,barato]
Ex2-: [makro,almoço,quinta,caro]
Ex3+: [tonho,almoço,sábado,barato]
[tonho,café,quinta,barato]
Ex4-: [club,café,domingo,barato]
Exemplo (parte 4)
[?, ?, ?, ?]
[tonho, ?,?,?]
[?,?,?,barato]
[tonho,?,?,barato]
[tonho,?,?,barato]
[tonho,café,quinta,barato]
Ex1+: [tonho,café,quinta,barato]
Ex2-: [makro,almoço,quinta,caro]
Ex3+: [tonho,almoço,sábado,barato]
Ex4-: [club,café,domingo,barato]
Ex5-: [tonho,café,domingo,caro]
Questões
 Como garantir que o algoritmo de aprendizagem
pode funcionar bem nos exemplos futuros?
 Caso não haja garantia, como saber que ele tem
alguma utilidade?
 Aprender regras tudo bem, mas e se elas não
existirem?
Geber Ramalho
40