Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
SPs Baseados em Regras
Vantagens:Regras oferecem forma de representação intuitiva de muito conhecimentoMecanismos de Inferência aproximam-se de estratégias comuns de resolução de problemasEstrutura de Controlo simples e intuitivaMuitas Conchas de desenvolvimento
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Limitação Fulcral:Aquisição de Conhecimento é difícil
Outras limitações:
As Regras não constituem sempre a forma mais natural de representação do conhecimentoEm certos domínios pouco estruturados, não existe um corpo explícito de conhecimento estabelecido que permita a construção de uma base de regras
Experiência
Regras
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Os Peritos...
Exemplificam com Casos
Citam Casos para persuadir
Extrapolam a partir de Casos
Interpretam regras com
Casos
Testam estratégias
confrontando com Casos
Aprendem com os Casos
Ensinam novatos com Casos
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Solução CBR
Experiência Experiência
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
CBRAdaptar soluções antigas a problemas novos
Sistemas Baseados em Casos:
Representação explícita de experiências documentadas CASOSTécnica particularmente apropriada quando existe um historial bem documentado de Casos resolvidosRepresentação de Conhecimento a um nível operacional
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
CaracterísticasResolução de problemas por recordação de sutiações específicas, concretas antigas (casos)Aprendizagem por adaptação dos casosAquisição de Conhecimento por retenção de novos casos
Definição“resolver um novo problema
recordando uma situação velha semelhante e reutilizando informação e conhecimento dessa situação” [Aamodt&Plaza94]
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Retrieve
Suggested Solution
Revise
Retain
Retrievedcase(s)
Reuse
Solved case
New case
New case
Problem
Tested,Repaired
case
Confirmed Solution
Previouscases
Case memory
General Knowledge
• Os 4Rs: Retrieve,Reuse,Revise,Retain(Aamodt and Plaza, 94)
O Ciclo do CBR
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
O modelo
Espaço do Problema
Espaço das Soluções
Revise
Reuse
Problema novo
Retrieve
Retain
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
O algoritmoDado
- um conjunto de casos C (case memory),
(opcional) conhecimento genérico K um novo problema PDeterminar
- uma solução S para P, usando K e elementos adaptados de C, Ci; transformar S+P num novo caso.
1.(Retrieve) recolha de caso(s) relevante(s) para P;2. Repete
2.1- (Reuse) reutilização dos caso(s) Ci, produzindo S’;
2.2- (Revise) Revisão de S’ S até estar_satisfeito3. (Retain) Reter S+P, como novo caso, em C
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Retrieve Reuse Revise Retain
Case Memory
P: CPU RAM Monitor Disk Modem PIII 64M 17” 4G 34Kb
S: Interstar 300
P: CPU RAM Monitor Disk Modem PIII 64M 15” 4G 34Kb
S: interstar 200
P: CPU RAM Monitor Disk Modem PIII 128M 17” 4G 56Kb
S: ????
P: CPU RAM Monitor Disco Modem PIII 128M 21” 4G+4G 56Kb
S: Megacom 500
Exemplo: escolher um computador
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Exemplo
Retrieve Reuse Revise Retain
CaseMemory
P: CPU RAM Monitor Disk Modem PIII 64M 17” 4G 34Kb
S: Interstar 300
P: CPU RAM Monitor Disk Modem PIII 128M 21” 4G+4G 56Kb
S: Megacom 500
P: CPU RAM Monitor Disk Modem PIII 64M 15” 4G 34Kb
S: interstar 200
P: CPU RAM Monitor Disk Modem PIII 128M 17” 4G 56Kb
S: ????
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Exemplo
Retrieve Reuse Revise Retain
CaseMemory
P: CPU RAM Monitor Disk Modem PIII 64M 17” 4G 34Kb
S: Interstar 300
P: CPU RAM Monitor Disk Modem PIII 128M 21” 4G+4G 56Kb
S: Megacom 500
P: CPU RAM Monitor Disk Modem PIII 64M 15” 4G 34Kb
S: interstar 200
P: CPU RAM Monitor Disk Modem PIII 128M 17” 4G 56Kb
S: ????
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Exemplo
Retrieve Reuse Revise Retain
CaseMemory
P: CPU RAM Monitor Disk Modem PIII 64M 17” 4G 34Kb
S: Interstar 300
P: CPU RAM Monitor Disk Modem PIII 128M 21” 4G+4G 56Kb
S: Megacom 500
P: CPU RAM Monitor Disk Modem PIII 64M 15” 4G 34Kb
S: interstar 200
P: CPU RAM Monitor Disk Modem PIII 128M 17” 4G 56Kb
S: ????
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Exemplo
Retrieve Reuse Revise Retain
CaseMemory
P: CPU RAM Monitor Disk Modem PIII 64M 17” 4G 34Kb
S: Interstar 300
P: CPU RAM Monitor Disk Modem PIII 128M 21” 4G+4G 56Kb
S: Megacom 500
P: CPU RAM Monitor Disk Modem PIII 64M 15” 4G 34Kb
S: interstar 200
P: CPU RAM Monitor Disk Modem PIII 128M 21” 4G+4G 56Kb
S: Megacom 500
P: CPU RAM Monitor Disk Modem PIII 128M 17” 4G 56Kb
S: ????
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Exemplo
Retrieve Reuse Revise Retain
CaseMemory
P: CPU RAM Monitor Disk Modem PIII 64M 17” 4G 34Kb
S: Interstar 300
P: CPU RAM Monitor Disk Modem PIII 128M 21” 4G+4G 56Kb
S: Megacom 500
P: CPU RAM Monitor Disk Modem PIII 64M 15” 4G 34Kb
S: interstar 200
P: CPU RAM Monitor Disk Modem PIII 128M 21” 4G+4G 56Kb
S: Megacom 500
P: CPU RAM Monitor Disk Modem PIII 128M 17” 4G 56Kb
S: Megacom 500 21”->17” minus 4G
P: CPU RAM Monitor Disk Modem PIII 128M 17” 4G 56Kb
S: ????
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Exemplo
Retrieve Reuse Revise Retain
CaseMemory
P: CPU RAM Monitor Disk Modem PIII 64M 17” 4G 34Kb
S: Interstar 300
P: CPU RAM Monitor Disk Modem PIII 128M 21” 4G+4G 56Kb
S: Megacom 500
P: CPU RAM Monitor Disk Modem PIII 64M 15” 4G 34Kb
S: interstar 200
P: CPU RAM Monitor Disk Modem PIII 128M 17” 4G 56Kb
S: Megacom 500 21”->17” minus 4G
Bom?
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Exemplo
Retrieve Reuse Revise Retain
CaseMemory
P: CPU RAM Monitor Disk Modem PIII 64M 17” 4G 34Kb
S: Interstar 300
P: CPU RAM Monitor Disk Modem PIII 128M 21” 4G+4G 56Kb
S: Megacom 500
P: CPU RAM Monitor Disk Modem PIII 64M 15” 4G 34Kb
S: interstar 200
P: CPU RAM Monitor Disk Modem PIII 128M 17” 4G 56Kb
S: Megacom 500 21”->17” minus 4G
SIM!
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Exemplo
Retrieve Reuse Revise Retain
CaseMemory
P: CPU RAM Monitor Disk Modem PIII 64M 17” 4G 34Kb
S: Interstar 300
P: CPU RAM Monitor Disk Modem PIII 128M 21” 4G+4G 56Kb
S: Megacom 500
P: CPU RAM Monitor Disk Modem PIII 64M 15” 4G 34Kb
S: interstar 200
P: CPU RAM Monitor Disk Modem PIII 128M 17” 4G 56Kb
S: Megacom 500 21”->17” minus 4G
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Exemplo
Retrieve Reuse Revise Retain
CaseMemory
P: CPU RAM Monitor Disk Modem PIII 64M 17” 4G 34Kb
S: Interstar 300
P: CPU RAM Monitor Disk Modem PIII 128M 21” 4G+4G 56Kb
S: Megacom 500
P: CPU RAM Monitor Disk Modem PIII 64M 15” 4G 34Kb
S: interstar 200
P: CPU RAM Monitor Disk Modem PIII 128M 17” 4G 56Kb
S: Megacom 500 21”->17” minus 4G
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Alguns Aspectos
Métodos de ReutilizaçãoCópia (solução, método)Adaptação(solução, método)
Representação de CasosPares Atributo/ValorRedes Semânticas
Métodos de RecolhaIdentificar as CaracterísticasProcura (por índices)Correspondência (por semelhança)Selecção (por métrica)
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Alguns aspectos
Métodos de RetençãoExtracção (descriptores, soluções, justificações, método)Índices (quais?)Integração
Métodos de RevisãoAvaliação da Solução (por um perito,
no mundo real, num modelo)Reparação (o próprio, o utilizador)
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Representação de CasosCaso: conhecimento
contextualizado relativo a uma experiência
Problema + Solução
Tipos de informação num caso:
Idênticos aos de uma base de dados
Nome: Produções Milagre das RosasNúmero de Contribuinte: 408804480Capital Social: 5.000 contosTempo de Actividade: 2 anosFacturação anual: 15.000 contosPedido de Empréstimo: 3.000 contos
Resultado do pedido: concedidoSpread: 1,05%
Nome: Produções Milagre das RosasNúmero de Contribuinte: 408804480Capital Social: 5.000 contosTempo de Actividade: 2 anosFacturação anual: 15.000 contosPedido de Empréstimo: 3.000 contos
Resultado do pedido: concedidoSpread: 1,05%
Problema
Solução
Características
(features)
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Tarefa crítica:
construção e organização da Base de Casos
Base de Casos:Conjunto representativo de Casos
cobrindo os objectivos do raciocínioincluindo tentativas para atingir esses objectivos
tentativas bem sucedidas propor soluções
tentativas falhadas evitar falhas
Casos:históricosdesenvolvidos com um perito no domínio
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
IndexaçãoPara acelerar o processo de Recolha
demasiadameste genérica demasiados Casos
demasiadamente específica insucesso na Recolha
Nome: Belmiro Serpa TinhasIdade: 52 anosNúmero de Doente: 2035Morada: R. do Bem Viver, 7878 ANJOSFoto:
Sexo: masculinoPeso: 83 KgTipo de Sangue: A-…………………….
Nome: Belmiro Serpa TinhasIdade: 52 anosNúmero de Doente: 2035Morada: R. do Bem Viver, 7878 ANJOSFoto:
Sexo: masculinoPeso: 83 KgTipo de Sangue: A-…………………….
Característicasindexadas
Característicasnão-indexadas
Indexação
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Recolha de CasosTécnicas mais comuns:
Vizinho Mais Próximo (Nearest
Neighbor Retrieval)
Distâncias calculadas de acordo com
uma Métrica de Semelhança
Indução (Inductive Retrieval)
Recolha usa Árvore de Decisão criada
off-line
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Recolha pelo Vizinho Mais Próximo
Exemplo: Empréstimos Bancários
Representação gráfica das características indexadas:
Rendimento Mensal
Pagamento Mensal
Um Caso
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Recolha pelo Vizinho Mais Próximo
Rendimento Mensal
Pagamento Mensal
Casos bem sucedidos
Casos mal sucedidos
Novo Caso
Possível Métrica de Semelhança:
dA B (XA B wX ) (YA B wY )
A
B
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Recolha por InduçãoA Base de Casos é analisada
É construída por indução uma Árvore
de Decisão
Algoritmo mais comum: ID3
A Árvore é usada para escolher o(s)
Caso(s) a recolher
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Recolha por InduçãoExemplo: Empréstimos Bancários
Estado doEmprstimo
RendimentoMensal
Situa‹oLaboral
PagamentoMensal
Caso 1 Bom 300 Assalariado 30
Caso 2 Muito mau 600 Assalariado 60
Caso 3 Muito bom 450 Recibo Verde 40
Caso 4 Mau 250 Assalariado 50
Pagamento Mensal < 50c.?
Rendimento Mensal > 250c.?Situação Laboral
NãoSim
Caso 1 Caso 3 Caso 2 Caso 4
Recibo VerdeAssalariadoSim Não
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
AdaptaçãoTipos de Adaptação:
Nenhuma (ex.: empréstimo bancário)
EstruturalUsar regras ou fórmulas de adaptação para preencher ou alterar características
DerivacionalReutilizar no Caso Corrente as regras ou fórmulas que produziram a solução no Caso Recolhido
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Algumas aplicaçõesDiagnóstico de Falhas em MáquinasDiagnóstico de Redes de ComputadoresAnálise de CréditoPrevisão de Depósitos GeológicopsPlaneamento (de batalhas...)Compreensão de Linguagem NaturalProjecto Criativo
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
Algumas AplicaçõesGestão de RedesRaciocínio LegalAtribuição de Responsabilidades em SegurosDiagnóstico médicoPrevisão MeteorológicaDetecção de FraudesPlaneamento e Escalonamento
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
BooksJanet Kolodner, “Case-Based Reasoning”, Morgan Kaufmann, 1993David B. Leake (Ed.),” Case-Based Reasoning: experiences, lessons and future directions”, MIT Press,1996
Web Linkshttp://www.ai-cbr.org/http://www.cbr-web.org/
Introductory materialA. Aamodt & E. Plaza, Case-Based Reasoning: foundational issues, methodlogical variations ans systems approaches, AI Communications, Vol. 7, Nr. 1, March 1994, pp. 39-59.I. Watson, “An introduction to Case-Based Reasoning, in Progress in Case-Based Reasoning, I. Watson (Ed.), 1995, pp. 3-16.
Raciocínio Baseado em Casos (CBR)
© Carlos Bento, Amílcar Cardoso, Ernesto Costa
HistóriaSchank 82 (MOPs)
Kolodner 84 (CYRUS)
Gentner 83, Carbonell 83,86 (Analogy)