Raciocínio Baseado em Casos (CBR)
Plano de aula
 Críticas aos sistemas baseados em regras
 Conceitos fundamentais
 Funcionamento: ciclo dos RE’s
 Aplicações
 Balanço
Geber Ramalho
1
Sistemas baseados em regras: críticas
 aquisição de conhecimento muito difícil
• regras nem sempre são intuitivas
 desenvolvimento é muito longo
 não aprende
 não é robusto
 tratamento de incerteza complicado
 manutenção e refinamento são delicados
 é lento
 dificuldades com problemas “under constraint”
• muitas soluções para o mesmo problema
Geber Ramalho
2
Soluções atuais
 Aquisição
•
•
•
•
sistemas especialistas de 2a geração
abandono da hipótese da transferência de conhecimento
aquisição baseada em modelos
utilização de aprendizagem automática simbólica
 Robustez
• tratamento de incerteza
 Tempo de desenvolvimento
• Ferramentas (shells)
 Aprendizado (on-line)
• EBL, chunking, ... (sem sucesso)
Geber Ramalho
3
Soluções atuais: Conclusões
As soluções propostas ainda são insatisfatórias
Porque, então, não mudar paradigma?
Geber Ramalho
4
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
Nova explicação/solução
Nova situação/problema
5
“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
6
Experiência: o que o especialista tem de
mais valioso
 Sistemas Especialistas convencionais:
Experiência
Regras
Engenheiro de
conhecimento
 (alguns) Sistemas Especialistas de segunda geração:
Experiência
Regras
Algoritmo de
aprendizagem
Geber Ramalho
7
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
• suaviza necessidade de aquisição de conhecimento
Experiência
Geber Ramalho
Experiência
8
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
9
Find Me: http://infolab.cs.uchicago.edu/entree
Geber Ramalho
10
Exemplo:
Valor de Venda de Casas
Geber Ramalho
11
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
13
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
14
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
15
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
• concreto x abstrato
• 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
16
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
17
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
18
k vizinhos mais próximos (knn)

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
19
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
20
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
21
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
23
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
24
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
25
Exemplo de reutilização I
 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
26
Exemplo de reutilização: reinstanciação
 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
27
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
28
Revisão e retenção
 Revisão
1) Avaliar a solução
2) Consertar o caso
(automáticamente ou não)
 Retenção
1) Extração da informação a reter
2) indexação
3) inserção do caso na base
Geber Ramalho
29
Aplicações: estado da arte
 Todas as classes de problemas dos SE´s
• 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
30
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
 Buttler agents
• sugere hotéis, restaurantes, oficinas, ...
 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
32
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
33
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
34
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
35
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
36