Aprendizagem
Simbólica
Geber Ramalho
Jacques Robin
Francisco Carvalho
CIn-UFPE
CIn- UFPE
Construção de bases de conhecimento
(baseadas em regras)
 Críticas
• Aquisição de conhecimento muito difícil (problema
central!!!)
• Desenvolvimento longo e manutenção delicada
(conseqüência)
• Sistema não se adapta
• Não é robusto e tem tratamento de incerteza
complicado
 Soluções
• Robustez e incerteza:
Sistemas fuzzy, probabilísticos,...
• Aquisição, tempo de desenvolvimento e
adaptabilidade: Aprendizagem de máquina
CIn- UFPE
2
Aprendizagem de máquina: exemplos
 Prever classes de futuras pacientes de alto risco
que devem fazer cesareana
 Análise de risco de crédito: prever clientes não
solventes
 Prever comportamento de compra de clientes
 Recomendar filmes para clientes
 etc.
CIn- UFPE
3
Aprendizagem de máquina:
a natureza dos exemplos
CIn- UFPE
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
4
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”
• só é verdade até aquele momento!
CIn- UFPE
5
Aprendizagem
 Atividade de uma agente = função f (percepção) 
ação
 idéia:
• aprender, a partir de exemplos (x,f(x)), representação
de uma função h que aproxima f
 Métodos
• simbólico: indução
• não simbólico: redes neurais, algo. genéticos, etc.
CIn- UFPE
6
Questões: on-line x off-line
 Aprender de uma vez ou aos poucos?
• Incremental (on-line): atualiza hipótese a cada novo
exemplo
– mais flexível, situada... porém
– ordem de apresentação é importante (backtracking)
– é difícil revisar as crenças
• não incremental (off-line): gera h a partir de todo
conjunto de exemplos
– mais eficiente e prática
– mais usado!
CIn- UFPE
7
Modelo do Agente Aprendiz (on-line)
Agente
t+1
sensores
ambiente
t
avaliação
trocas
elemento
ator
elemento de
conhecimento aprendizagem
objetivos de
aprendizagem
efetuadores
CIn- UFPE
crítico
Gerador de
problemas
8
CIn- UFPE
Algoritmo de
Aprendizagem
exemplos
conhecimento
ambiente
Uso
Treinamento
Modelo do Agente Aprendiz (off-line)
sensores
elemento
ator
efetuadores
9
Questões...
 O que aprender?
• Aumentar/refinar conhecimento do agente
–
–
–
–
–
propriedades relevantes do mundo
como o mundo evolui
resultados das ações
adequação de ações num dado contexto
...
• Aumentar eficiência do agente (não precisa mais
refletir)
– não gera conhecimento novo, propriamente dito
 Como representar o que aprender?
• eficiência x expressividade
– ex. lógica de atributo valor (0+) x lógica de predicados
(1)
CIn- UFPE
10
Questões
 Qual é o feedback disponível?
• Aprendizagem supervisionada: certo ou errado
– Dado um conjunto de exemplos pré-classificados,
aprender uma descrição geral que encapsula a informação
contida nesses exemplos e que pode ser usada para
prever casos futuros
– ex. concessão de crédito
• Aprendizagem não-supervisionada: ?
– Dada uma coleção de dados não classificados, agrupá-los
por regularidades
– ex. caixa de supermercado empacotando
• Aprendizagem por reforço: recompensa/punição
– ex. jogo de xadrez: é por aí!
CIn- UFPE
11
Questões
 Preguiçosa xGulosa
• Gulosa: gera conhecimento em intenção
– custa mais na hora de gerar e de atualizar
– mas é barata na hora de usar (identificar)
• preguiçosa: usa conhecimento em extensão
– custa mais na hora de usar mas é barata na hora de
gerar (nem gera na verdade!)
 Qual é o conhecimento prévio disponível?
• Em geral existe e é importante
– ex. artista e médico chegam a conclusões diferentes
para as mesmas observações
• IA simbólica captura melhor este conhecimento
• influi também na descrição dos exemplos
– ex. CNCT: Paraíba, Pernambuco, Ceará -> NE
CIn- UFPE
12
Resumo: Aprendizagem indutiva
Objetos (dados)
clustering
(ap. não-supervisionada)
1
Redes neurais, agrupamento
conceitual, estatítica, ...
2
3
ap. supervisionada
Indução - geração de
um classificador
(árvore de decisão, conjunto de
regras, redes neurais c/ pesos ajustados,...)
K em intenção
outro
objeto
Identificação
classificador
Preguiçosa
ID3, version space, redes
neurais, naive bayes, ...
Knn, LWR, CBR,
classe
novo
algoritmo
Identificação
classe
1,2 ou 3
1,2 ou 3
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)
•
•
•
•
CIn- UFPE
lógica de primeira ordem & resolução
implementação mais complicada
aprendizagem incremental
indução lógica unicamente
14
Árvore de Decisão
 A partir de um conjunto de propriedades, decide
sim ou não
 Representação de árvores de decisão
• Cada nó interno testa um atributo
• Cada ramo corresponde a um valor do atributo
• Cada folha atribui uma classificação
CIn- UFPE
15
Árvore de Decisã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?
CIn- UFPE
16
Árvore de Decisão “pensada”
valores
atributo
Sono?
Não.
Carona
CONIC?
Precisa de
álcool?
Sim.
CIn- UFPE
Não.
Sim.
Meio de
transporte?
Não.
CONIC?
Sim.
Não.
Quer sair?
Sim.
Não.
17
ID3: exemplos da soparia
 Atributos: (Sono, Transporte, CONIC, Álcool, Sair,
Fome)-> propriedade-objetivo
•
•
•
•
•
•
•
•
•
•
•
•
CIn- UFPE
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!
18
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)
CIn- UFPE
19
Indução top-down de árvores de
decisão
 Loop principal:
1. A  o “melhor” atributo de decisão para o próximo nó
2. Atribua A como atributo de decisão para nó
3. Para cada valor de A, crie um novo descendente para
nó
4. Classifique os exemplos de treinamento nos nós folha
5. Se os exemplos de treinamento estão classificados
perfeitamente, então PARE, senão comece
novamente a partir dos novos nós folha
CIn- UFPE
20
Indução top-down de árvores de
decisão (detalhe)
function APRENDIZAGEM_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;
CIn- UFPE
21
Indução top-down de árvores de
decisão
 Escolha do melhor atributo
• O que discrimina o maior número de exemplos
• Maior ganho de informação (minimiza a entropia)
 Candidatos:
• Transporte: Não classifica imediatamente nenhum dos
exemplos
• Sono: Classifica de imediato 6 dos 12 exemplos
• ...
CIn- UFPE
22
Exemplo: atributo transporte
+:E01,E02,E04,E07,E10,E11,E12
- :E03,E05,E06,E08,E09
Transporte?
carro
+: E01,E07,E11
-: E03,E09
CIn- UFPE
carona
+: E02,E04,E12
-: E08
outros
+: E10
-: E05,E06
23
Exemplo: atributo sono
+:E01,E02,E04,E07,E10,E11,E12
- :E03,E05,E06,E08,E09
Sono?
sim
+: - - -: E3, E5, E9
CIn- UFPE
pouco
+: E1,E2,E4, E7
-: E6,E8
não
+: E10,E11,E12
-: - - -
24
Entropia
 S é uma amostra dos exemplos de treinamento
 p é a proporção de exemplos positivos em S
 p é a proporção de exemplos negativos em S
 Entropia mede a “impureza” de S:
• Entropia(S)=- p log2 p - p log2 p
CIn- UFPE
25
Entropia - Exemplo
 Suponha que S é uma coleção de 14 exemplos,
incluindo 9 positivos e 5 negativos
• Notação: [9+,5-]
 A entropia de S em relação a esta classificação
booleana é dada por:
Entropy([9,5])  (9 / 14) log2 (9 / 14)  (5 / 14) log2 (5 / 14)
 0.940
CIn- UFPE
26
Cálculo do ganho de informação
 Gain(S,A)=redução esperada da entropia devido
a “classificação” de acordo com A
| Sv |
Gain( S , A)  Entropy( S )  
Entropy(S v )
vValues( A) | S |
Á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.
CIn- UFPE
+: E2,E4
-: E8
+: - - -: E6
Quer sair?
+: E2,E4
-: - - -
+: - - -: E8
Sim.
Não.
Não.
28
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)
CIn- UFPE
29
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)
CIn- UFPE
30
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
CIn- UFPE
PE
PB
Norte
AL
CE
31
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.
CIn- UFPE
32
Problemas gerais: overfitting
 Overfitting (hiper-especialização):
• Evitar encontrar uma “regularidade” muito restrita nos
dados
 Soluções:
• validação cruzada
• poda
CIn- UFPE
33
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
CIn- UFPE
Teste
34
Curva de aprendizagem
CIn- UFPE
35
Quando usar árvores de decisão?
 Instâncias (exemplos) são representadas por
pares atributo-valor
 Função objetivo assume apenas valores
discretos
 Hipóteses disjuntivas podem ser necessárias
 Conjunto de treinamento possivelmente
corrompido por ruído
CIn- UFPE
36
Exemplos Práticos
 Exemplos correntes
•
•
•
•
Diagnóstico médico e de equipamentos
Análise de crédito
Recuperação de Informação
etc.
 Funciona mesmo
• 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
CIn- UFPE
37
Aprendendo descrições lógicas
Version space
CIn- UFPE
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))
CIn- UFPE
39
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)
CIn- UFPE
40
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
CIn- UFPE
41
Hipóteses...
Exemplo1 +







CIn- UFPE
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
....
42
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
CIn- UFPE
43
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
CIn- UFPE
44
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)
CIn- UFPE
46
Exemplo do restaurante (aima pag. 534)
Alt = alternativo?
Hun = fome?
Rain = chove?
CIn- UFPE
Bar = tem área de bar?
Pat = vagas livres?
Res = fez reserva?
Fri = é sex ou sábado?
Price = preço?
Est = tempo de espera
47
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,Algumas)
 X3: falso -
• H3: x VaiEsperar(x)  Pessoas(x,Algumas)
 X4: falso -
• H4: x VaiEsperar(x)  Pessoas(x,Algumas) 
(Pessoas(x,Cheio)  Sex/Sab(x))
 Problema: backtracking
CIn- UFPE
48
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
CIn- UFPE
49
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
CIn- UFPE
(não pode mais generalizar)
51
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]
Reflexões...
 Mesmo com aprendizagem ainda existe um bom
trabalho do engenheiro de conhecimento
• escolher da descrição dos objetos (exemplos)
– representação e conteúdo
•
•
•
•
CIn- UFPE
escolha dos exemplos
escolha do algoritmo de aprendizagem
parametrização do algoritmo de aprendizagem
avaliação dos resultados
56
Bibliografia adicional
 Machine Learning Vol I a IV
• na biblioteca tem os dois primeiros
• ler cap 1 e cap 4, do vol I, e cap 8 do vol II
 Generalization as search
• Tom Mitchell
CIn- UFPE
57