Aprendizado baseado em instâncias
(Aprendizagem Preguiçosa)
Vizinhos mais Próximos (kNN)
Raciocínio Baseado em Casos (CBR)
Geber Ramalho & Márcio Dahia
1
Experiência: o que o especialista tem de
mais valioso
Novo
Problema
 Sistemas Especialistas convencionais
Experiência (exemplos)
Dedução
Regras
 Aprendizagem gulosa: ID3, Version Space, ...
Experiência (exemplos)
Regras
Dedução
Indução
 Aprendizagem preguiçosa: kNN, CBR,...
Experiência (exemplos)
Geber Ramalho & Márcio Dahia
S O L U Ç Ã O
Engenheiro de
conhecimento
Indução
2
Aprendizagem Baseada em Instância
 Aprendizagem Gulosa (convencional)
• construção explícita da função f que generaliza os exemplos de
treinamento.
• Estima f de uma vez por todas para todo o espaço de exemplos
• métodos: ID3, Version Space, MLP Neural Nets, ...
 Aprendizagem Baseada em Instância (IBL) ou
aprendizagem preguiçosa:
• simplesmente armazena os exemplos de treinamento
• deixa a generalização de f só para quando uma nova instância
precisa ser classificada
• a cada nova instância, uma f nova e local é estimada
• métodos: vizinhos mais próximos, regressão localmente
ponderada, raciocínio baseado em casos, etc.
Geber Ramalho & Márcio Dahia
3
Aprendizagem Baseada em Instância
Objetos (dados)
clustering
(ap. não-supervisionada)
1
Redes neurais, agrupamento
conceitual, estatítica, ...
2
3
ap. supervisionada
Gulosa
(á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, RN-MLP
naive bayes, ...
Knn, LWR, CBR,
classe
novo
algoritmo
Identificação
classe
1,2 ou 3
1,2 ou 3
Aprendizagem Baseada em Instância
 Como?
• Armazena as instâncias de treinamento
• Calcula a distância entre as instâncias de treinamento e
a instância desconhecida
• Avalia o valor da função de classificação a partir dos
valores das instâncias mais próximas
 Diferentes métodos possuem diferentes formas de:
• Representar as instâncias de treinamento
• Calcular a distância entre instâncias
• Avaliar o valor da função de classificação
Geber Ramalho & Márcio Dahia
5
k vizinhos mais próximos
Geber Ramalho & Márcio Dahia
6
k vizinhos mais próximos
 Método mais antigo (1967) e difundido
 Instâncias são representadas por pontos num espaço
n dimensional n
• instância x = <a1(x), a2(x), a3(x), ..., an(x)>
Onde ar(x) representa o valor do r-ésimo atributo
 A distância entre as instâncias pode ser calculada
pela distância euclidiana ou outras
d ( xi , x j ) 
Geber Ramalho & Márcio Dahia
n
 (a ( x )  a ( x ))
2
r 1
r
i
r
j
7
k vizinhos mais próximos: exemplo
 x = < idade(x), altura(x), peso(x)>,
onde adimplente pode ser “sim”, “não”]
 Exemplo de treinamento = (x,f(x)), onde f(x) é a função de
classificação a ser aprendida
• joão = (<36, 1.80, 76>, ???) a ser classificado
• josé = (<30, 1.78, 72>, sim)
• maria = (<25, 1.65, 60>, sim)
• anastácia = (<28, 1.60, 68>, não)
 Distância
• d(joão,josé) = [(36-30)2 + (1.80-1.78)2 + (76-72)2]1/2 =
(36+0.0004+16)1/2 = 7,21
• d(joão,maria) = (121+0.0225+256)1/2 = 19,41
As distâncias entre os pontos podem ser eventualmente normalizadas
Geber Ramalho & Márcio Dahia
8
k vizinhos mais próximos
 A função de classificação
fˆ
• Caso seja discreta, seu resultado é aquele que aparecer
mais vezes entre os k vizinhos mais próximos (V = conjunto
de valores possíveis da função)
f :  V
n
• Caso seja contínua, seu resultado é a média dos resultados
dos k vizinhos mais próximos
f : 
n
Geber Ramalho & Márcio Dahia
9
k vizinhos mais próximos: Algoritmo para
estimar f
//Treinamento
Adicione cada instância de treinamento <x,f(x)> na lista
instancias_treinamento
//Classificação
Para cada instância xq a ser classificada
Chame de x1,x2,...xk as k instâncias mais próximas de xq na lista
instancias_treinamento
Caso discreto retorna
k
fˆ ( xq )  arg max   (v, f ( xi ))
vV
i 1
onde δ(a,b)é igual a 1 se a  b e 0 se a  b
Caso contínuo retorna
k
fˆ ( xq ) 
Geber Ramalho & Márcio Dahia
 f (x )
i
i 1
k
10
k vizinhos mais próximos: exemplo
 Caso discreto
+
+
x+
q
-
-
k = 1 classifica xq como +
k = 5 classifica xq como -
-+
• Percebe-se que o k é determinante na classificação
Geber Ramalho & Márcio Dahia
11
k vizinhos mais próximos: exemplo
 Caso contínuo
• exemplo = filme = <ano, bilheteria>
• classificação f = recomendação r  Z, r = [1...5]
• r(x1) = 4, r(x2) = 3, r(x3) = 5, r(x4) = 2
• para k = 3 e supondo que x1, x2 e x3 são os mais próximos
de xq, temos
• f(xq) = (4+3+5)/3 = 4
Geber Ramalho & Márcio Dahia
12
k vizinhos mais próximos
 Visualização da “superfície de decisão”, para k = 1
• Diagrama de Voronoi => poliedro convexo para cada
instância de treinamento.
• As instâncias dentro do poliedro são completamente
classificados pela instância associada
http://www.cs.cornell.edu/Info/People/chew/Delaunay.html
Geber Ramalho & Márcio Dahia
13
k vizinhos mais próximos
 Refinamento óbvio (p/ melhorar robustez)
• ponderar a contribuição de cada um dos k vizinhos de
acordo com sua distância ao ponto de consulta xq
– Caso discreto
k
fˆ ( xq )  arg max   i (v, f ( xi ))
vV
i 1
– Caso contínuo
k
•
fˆ ( xq ) 

i 1
i
onde
k

i 1
Geber Ramalho & Márcio Dahia
f (xi )
i
1
ωi 
d(xi ,xq )
14
k vizinhos mais próximos
 Problema da dimensionalidade
• Para calcular a distância entre os pontos, o método utiliza
todos os atributos da instância
 Conseqüências:
• pode custar caro
• atributos irrelevantes podem deturpar a classificação
 Soluções
• Atribuir pesos j aos atributos de maneira que minimize a
taxa de erro de classificação
• Usar a técnica de validação cruzada para automaticamente
escolher os pesos
• Eliminar atributos do espaço de instâncias
Geber Ramalho & Márcio Dahia
15
Regressão Localmente Ponderada (LWR)
 Há como generalizar K vizinhos mais próximos
• Constrói uma aproximação explicita de uma função f(xq)
em uma região próxima de xq levando em conta a distância
entre estas e xq
• A aproximação é então usada para calcular o valor ponto xq.
• A descrição de f’(x) é apagada, pois a função de
aproximação será construída para cada instância a ser
consultada
Geber Ramalho & Márcio Dahia
16
Regressão localmente ponderada
 Função de aproximação mais comum
fˆ ( x)  0  1a1 ( x)  ... n an ( x)
 Escolher i que minimiza a soma dos quadrados dos
erros em relação ao conjunto de treinamento D


2
1
ˆ
E(xq )   f ( x)  f ( x)
2 xD
 Mas existem diferentes propostas para minimizar o
erro...
• Erro quadrático sobre os k-vizinhos mais próximos
• Erro quadrático ponderado em D,...
Geber Ramalho & Márcio Dahia
17
Raciocínio Baseado em Casos (CBR)
Mais que um método de aprendizagem preguiçosa:
é um método de resolução de problemas!!!!!!
Geber Ramalho & Márcio Dahia
18
Compreensão de histórias (Sistema IPP)
 IRA guerrilas ambushed a military patrol in west Belfast
yesterday killing one british soldier and badly wounding
another Army quarters
 a suspected IRA gunman killed a 50-year old unarmed
security guard in east Belfast early today the police said
 A gunman shot and killed a part-time policeman at a
soccer match Saturday and escaped through the crowd...
situação-explicação
ou
problema solução
Geber Ramalho & Márcio Dahia
Nova explicação/solução
Nova situação/problema
19
“Experiência vivida”
 Classificação: “Os problemas de ouvido deste paciente são
casos típicos de otite média”
 Soluções compiladas: “Os sintomas de coração do paciente
X podem ser explicados da mesma maneira que aquele
paciente Y”
 Avaliando medidas: Minha casa é como aquela que foi
vendida mais em baixo nesta rua por R$25.000,00 mas ela tem
uma vista melhor”
 Concepção (design): para projetar este hospital, vou me
basear naquele que já fiz com um número de leitos parecido,
embora tenha de adaptá-lo pois este é de esquina
 Avaliando opções: se nós atacássemos as instalações dos
mísseis cubanos/russos, seria como no caso de Pearl Harbor
Geber Ramalho & Márcio Dahia
20
Experiência: o que o especialista tem de mais
valioso
 Case-based reasoning system
• Um método de resolução de problemas onde novos problemas
são resolvidos adaptando-se soluções de antigos problemas
similares
• Raciocínio analógico intra-domínio
• aprendizado incremental on-line
 Em termos de IBL
• Representação mais complexa das instâncias
• Cálculo diversificado da distância entre instâncias
• Não só classifica, mas adapta!!! É um método de resolução de
problemas
Geber Ramalho & Márcio Dahia
21
Raciocínio baseado em casos
 Historicamente:
• Wittgenstein (conceituação em extensão)
• Edel Tulving (memória episódica)
• Gentner (analogia), ....
• Roger Schank (scripts)
• Janet Kolodner (memória dinâmica)
 Um caso
• é um episódio vivido
• contém a descrição de : problema + solução
• exemplos: um paciente, um projeto arquitetônico, uma
situação, uma causa jurídica, uma melodia, etc.
Geber Ramalho & Márcio Dahia
22
Exemplo
 Usos
- classificação (casa dos meus sonhos?)
- estimação de preços
Geber Ramalho & Márcio Dahia
23
Funcionamento do CBR: ciclo dos 4 RE´s
Recuperar
problema
Indexar
novo
caso
(alvo)
novo
caso
caso
recupe- (alvo)
rado
(fonte)
base
Reutilizar
caso
aprendido
Reter
solução
final
caso
solução
caso
testado
e
corrigido
Revisar
solução
sugerida
Desenvolvimento de um sistema CBR
 Qual a natureza e conteúdo dos casos?
 Como representá-los?
 Como indexá-los de maneira a poder encontrá-los
adequadamente e rapidamente mais tarde?
 Qual são os critérios para a escolha do melhor caso e
como recuperá-lo?
 Como estruturar (organizar) os casos da base?
 Como adaptar o caso recuperado?
Geber Ramalho & Márcio Dahia
25
Natureza e conteúdo dos casos
 Pergunta chave
• O que é um caso no domínio abordado?
 Conteúdo
• Mínima: descrição do problema e da solução
• Extensões: avaliação da solução (falhas, sucesso, etc.) ,
contexto (justificação, links com outros casos, etc.),
 Outros
• Tamanho e composição (casos compostos)
 Quantidade de casos
• distribuir bem no espaço de problema n-dimensional (n
atributos)
Geber Ramalho & Márcio Dahia
26
Representação dos casos
 Várias linguagens
• de vetores de características
• Atributo-valor (frames, redes semânticas, objetos, ...)
• lógica de primeira ordem
 Depende da natureza do que se quer representar
• Velho problema da expressividade x eficiência
• ex.
– situaçãoDeMediação(c1, disputa)  protagonistas (c1,
criança11, criança20, criança32)  objetoDisputado (c1,
chocolate)  ...
• ex.
– objeto: disputa;
– atributos: protagonistas, objetoDisputado
Geber Ramalho & Márcio Dahia
27
Indexação
 Objetivo: dar ao sistema conhecimento sobre como
estocar e comparar (match) casos
 Vocabulário de indexação
• índice = atributo, característica, predicado, ...
• Pode ser feita manual ou automaticamente
– Checklist, difference-based, inductive learning, ...
 Conselhos
• levar em conta a utilização que se quer fazer (propósito)
– ex. para um mecânico e para um cliente de locadora, a
descrição de um automóvel é bem diferente
Geber Ramalho & Márcio Dahia
28
Indexação (cont.)
 Interpretação de situação
preço
ano
modelo
marca
opcionais
kilometragem
motor
cor
....
• os índices realmente relevantes para um problema/situação
em particular
• ex. em uma disputa entre crianças a profissão não conta,
enquanto na disputa entre adultos, ela conta
Geber Ramalho & Márcio Dahia
29
Critério para escolha dos casos
 A recuperação é baseada na similaridade entre caso
alvo e casos fontes
• Dois tipos de cálculo de similaridade: explícito ou indireto
 Medida explícita (mais usado!)
• independente da estratégia de recuperação ou da
organização da memória
• k vizinhos mais próximos (knn)
 Medida indireta
• dependente da estratégia de recuperação e/ou da
organização da memória
• memória dinâmica (hierárquica)
Geber Ramalho & Márcio Dahia
30
k vizinhos mais próximos (k = 1)

Sim il( X , Y ) 
n
i 1
wi  simi (valor(axi ), valor(a yi ))

n
i 1
wi
wi - peso da característica i
axi e ayi - valores da característica f nos casos C e S
simi - função primitiva para a característica i
 Observações
• similaridade global [0-1], sem ordem de testes
• mais fácil introduzir conhecimento do domínio: pesos
• os pesos podem ser definidos manualmente ou por
métodos automáticos
Geber Ramalho & Márcio Dahia
31
Exemplo
Carro 1
Carro 2
Carro 3
ano
= 1997
modelo = Gol
marca = VW
cor
= vermelho
Preço = 1000
ano
= 1996
modelo = Golf
marca = VW
cor
= azul
Preço = 1500
ano
=
modelo =
marca =
cor
=
Preço =
1995
Tempra
Fiat
azul
1300
 Pesos
• ano = 2, modelo = 3, marca = 2, cor = 1, preco =1
 Funções primitivas
• ano: (diferença  2) => 1; (2 < dif  4) => 0,5; (dif > 4) => 0
• modelo: igual => 1; diferente => 0
• marca: igual => 1; diferente => 0
• cor: igual => 1; parecida => 0,5; diferente => 0
• preço: (dif  250) => 1; (250 < dif < 1000) => 0,5); (dif > 1000) => 0
Geber Ramalho & Márcio Dahia
32
Organização da memória
 Memória plana
• Implementação: lista simples (1 nível de indexação)
• Métodos de recuperação
– Busca serial (custa caro)
– Busca paralela
• Medida de similaridade
– explícita (knn)
 Memória hierárquica
• Implementação:
– características compartilhadas
– redes de discriminação
• Métodos de recuperação & Medida de similaridade
– implícita (basta percorrer!)
Geber Ramalho & Márcio Dahia
33
Características compartilhadas
situaçãoDeMediação = disputa
Protagonistas: países
tipoDeObjetoDisputado: terras
Tipo: disputa física Tipo: disputa política
(Korea)
(Panama)
Protagonistas: crianças
tipoDeObjetoDisputado: comida
objDisputado: laranja
relaçãoFamiliar: irmãs
idades: adolescentes
Desejo: objeto inteiro
(Laranja1)
objDisputado: Candy
(Candy)
Desejo: diferentes partes do objeto
(Laranja2)
Organização da memória
 Trade-offs:
• eficiência x completude
– eficiência na inserção x eficiência na consulta
– ordem fixa dos testes pode levar a a recuperação do caso que
não é o mais similar
• “plausibilidade” x facilidade de introduzir conhecimento
 Organizações alternativas de memória
• template trees, z-trees, ...
Geber Ramalho & Márcio Dahia
35
Similaridade e recuperação
 O casamento é parcial !!!! =>Mais robustez
 Etapas da recuperação
• Matching: encontrar os N casos mais similares ao caso alvo
• Ranking: Escolher o melhor caso MC em relação o alvo
 Questão: a similaridade basta?
• nas tarefas de design (projeto), não basta!
• É preciso: adaptation-based retrieval
Geber Ramalho & Márcio Dahia
36
Reutilização
 Objetivo: compensar as diferenças entre o problema-alvo e
problema-fonte escolhido
 Adaptação: 3 tipos
• Cópia: usada normalmente em classificação
• Adap. Estrutural: a partir da própria solução recuperada
• Adap. Derivacional: a partir da maneira com que a solução
recuperada foi gerada
 Para as duas últimas as operações são:
• ajuste de parâmetros, abstração e especialização, substituição,...
 Problema:
• depende do domínio,coordenação do conjunto de operadores de
transformação
Geber Ramalho & Márcio Dahia
37
Reutilização
 Exemplo
• JULIA precisa criar uma refeição italiana (e que não
contenha carne) composta de entrada, massas, refeição
principal e sobremesa;
• Baseando-se em casos anteriores, JULIA escolhe lasanha
como prato principal. Porém:
– a refeição original inclui um prato de massas. Para simplificar,
JULIA elimina o prato de massas;
– lasanha inclui carne. Devido à restrição do problema, uma
lasanha vegetariana é proposta;
Geber Ramalho & Márcio Dahia
38
Exemplo de reutilização: reinstanciação
 Método
• Determine os papéis dos envolvidos no caso retido;
• Faça a correspondência dos papéis no problema proposto;
• Reinstancie os atributos e relações do caso retido de
acordo com as respectivas correspondências;
 Ex.: MEDIATOR
• resolução de conflitos: como dividir uma laranja entre duas
crianças interessadas?
• caso anterior: método utilizado por pescadores;
• reinstanciação: identificação dos papéis de cada entidade
envolvida (pescador  criança, peixe  laranja, objetivo 
divisão)
Geber Ramalho & Márcio Dahia
39
Outros Métodos
 Ajuste de parâmetros
• ex.: cálculo de novo valor de um imóvel;
 Substituição baseado em casos
• encontrar outro caso que sugira uma alternativa;
• por que não utilizar logo este caso?
Geber Ramalho & Márcio Dahia
40
Revisão e retenção
 Revisão
1) Avaliar a solução
(automaticamente ou não)
2) Consertar o caso
 Retenção
1) Extração da informação a reter
2) indexação
3) inserção do caso na base
Geber Ramalho & Márcio Dahia
41
Aplicações: estado da arte
 Todas as classes de problemas dos SEs baseados em
regras
• diagnóstico, planejamento, scheduling, interpretação, cozinha,
design, seleção, ensino,....
 Existem ferramentas (shells)
• ReMind, CAsePOint,CASUEL, ART*, ReCall, CBR-Express,...
 Exemplos
• Machine Tool Fault Diagnosis
• Computer Network Diagnosis
• Credit Analysis
• Geological Deposit Prediction
• Battle Planning
Geber Ramalho & Márcio Dahia
42
Mais aplicações...
• Bank Telex Classification
• Natural Language Understanding
• Network Management
• Legal Reasoning
• Claims Settlement
• Medical Diagnosis
• Weather Prediction
• Fraud Detection
• Industrial Planning and Scheduling
• Residential Domain
• Aircraft Maintenance Domain
• Helpdesk Systems for PC Network Diagnostics
Algumas aplicações na WEB
 FindMe agents
• sugere filmes e carros em locadoras
• raciocino através de exemplos
• busca não hierárquica
 Correspondent agents
• usa técnicas de recuperação de casos para encontrar
textos: FAQ-finder
 Analog Devices
• help desk: o sistema responde às dúvidas mais simples,
restringindo a necessidade em contatar seus engenheiros
Geber Ramalho & Márcio Dahia
44
Problemas
 Aquisição & descrição dos casos
• nem sempre é trivial além de demandar conhecimento do
domínio!
 O controle da medida de similaridade é fraco pois o
matching é parcial
• o acúmulo de semelhanças “irrelevantes” faz com que certos
casos sejam escolhidos em detrimento dos outros
• como ter certeza que as propriedades A e B serão
determinantes na recuperação de um caso que contém 20
atributos?
 A explicação
• pode ser prejudicada quando a recuperação é baseada em
uma medida de similaridade numérica
Geber Ramalho & Márcio Dahia
45
Balanço e conclusões
 Apesar das limitações, é bem mais fácil e rápido
desenvolver e manter um sistema CBR. E ele é mais
robusto!
• CLAVIER na Lockheed (fornos) - de 60% para 10%, taxa de
erro
• General dynamics (barcos) - 5 homens-ano x 2 homens-ano.
• CANASTA da DEC: 8 vezes mais rápido
Geber Ramalho & Márcio Dahia
46
Quando usar CBR?
 Existe uma grande volume de dados históricos
 Os especialistas falam sobre seus domínio dando
exemplos
 A experiência vale tanto quanto o conhecimento dos livros
texto
 Os problemas não são completamente formalizáveis
• fraca compreensão do problema, dificuldade de verbalização
 Existem conhecimento para adaptação de casos
• adequado para tarefas de projeto (design)
 Existem muitas exceções às regras
 É preciso aprender “on-line”
Geber Ramalho & Márcio Dahia
47
Balanço entre aprendizado guloso e
preguiçoso
 Guloso
 Preguiçoso
• Generaliza função de
classificação
• Não generaliza a
função de classificação
• Aproximação global
• Aproximação local
• Treinamento lento
• Treinamento rápido
• Classificação rápida
• Classificação lenta
• KNN - considera todos
os atributos
Geber Ramalho & Márcio Dahia
48
Referências básicas
 Aamodt, A; Plaza, E. (1994). “
Case-Based Reasoning: Foundational Issues, Methodological
Variantions, and System Approaches”. Em AI Communications,
Vol. 7, nr. 1;
 Kolodner, J. (1993)
Case Based Reasoning. Morgan Kaufmann.
 Web
• AI-CBR Home Page: http://www.ai-cbr.org/theindex.html
• CBR archive: http://www.ai-cbr.org/cases.html
• CBR in the Web: http://wwwagr.informatik.unikl.de/~lsa/CBR/CBR-Homepage.html
• CBR Bibliography: http://www.surveying.salford.ac.uk/AICBR/biblio/search.html
Geber Ramalho & Márcio Dahia
49