Raciocínio Baseado em Casos (CBR) SPs Baseados em Regras Vantagens: Regras oferecem forma de representação intuitiva de muito conhecimento Mecanismos de Inferência aproximam-se de estratégias comuns de resolução de problemas Estrutura de Controlo simples e intuitiva Muitas Conchas de desenvolvimento © Carlos Bento, Amílcar Cardoso, Ernesto Costa Raciocínio Baseado em Casos (CBR) Limitação Fulcral: Aquisição de Conhecimento é difícil Outras limitações: Experiência Regras As Regras não constituem sempre a forma mais natural de representação do conhecimento Em 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 © Carlos Bento, Amílcar Cardoso, Ernesto Costa Raciocínio Baseado em Casos (CBR) 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 © Carlos Bento, Amílcar Cardoso, Ernesto Costa Raciocínio Baseado em Casos (CBR) Solução CBR Experiência © Carlos Bento, Amílcar Cardoso, Ernesto Costa Experiência Raciocínio Baseado em Casos (CBR) CBR Adaptar soluções antigas a problemas novos Sistemas Baseados em Casos: Representação explícita de experiências documentadas CASOS Técnica particularmente apropriada quando existe um historial bem documentado de Casos resolvidos Representação de Conhecimento a um nível operacional © Carlos Bento, Amílcar Cardoso, Ernesto Costa Raciocínio Baseado em Casos (CBR) Definição “resolver um novo problema recordando uma situação velha semelhante e reutilizando informação e conhecimento dessa situação” [Aamodt&Plaza94] Características Resolução de problemas por recordação de sutiações específicas, concretas antigas (casos) Aprendizagem por adaptação dos casos Aquisição de Conhecimento por retenção de novos casos © Carlos Bento, Amílcar Cardoso, Ernesto Costa Raciocínio Baseado em Casos (CBR) O Ciclo do CBR • Os 4Rs: Retrieve,Reuse,Revise,Retain (Aamodt and Plaza, 94) Problem New case Retain Retrieve Previous cases Retrieved case(s) New case General Knowledge Reuse Case memory Tested, Repaired case Solved case Revise Confirmed Solution © Carlos Bento, Amílcar Cardoso, Ernesto Costa Suggested Solution Raciocínio Baseado em Casos (CBR) O modelo Problema novo Espaço do Problema Retrieve Retain Revise Reuse Espaço das Soluções © Carlos Bento, Amílcar Cardoso, Ernesto Costa Raciocínio Baseado em Casos (CBR) O algoritmo Dado - um conjunto de casos C (case memory), (opcional) conhecimento genérico K um novo problema P Determinar - 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_satisfeito 3. (Retain) Reter S+P, como novo caso, em C © Carlos Bento, Amílcar Cardoso, Ernesto Costa Raciocínio Baseado em Casos (CBR) Exemplo: escolher um computador P: CPU RAM Monitor Disk Modem PIII 128M 17” 4G 56Kb S: ???? Retrieve Revise Reuse Retain P: CPU RAM Monitor Disk Modem PIII 64M 17” 4G 34Kb S: Interstar 300 P: CPU RAM Monitor Disco Modem PIII 128M 21” 4G+4G 56Kb S: Megacom 500 P: CPU RAM Monitor Disk Modem PIII 64M 15” 4G S: interstar 200 © Carlos Bento, Amílcar Cardoso, Ernesto Costa 34Kb Case Memory Raciocínio Baseado em Casos (CBR) Exemplo P: CPU RAM Monitor Disk Modem PIII 128M 17” 4G 56Kb S: ???? Retrieve Revise Reuse Retain 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 S: interstar 200 © Carlos Bento, Amílcar Cardoso, Ernesto Costa 34Kb CaseMemory Raciocínio Baseado em Casos (CBR) Exemplo P: CPU RAM Monitor Disk Modem PIII 128M 17” 4G 56Kb S: ???? Retrieve Revise Reuse Retain 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 S: interstar 200 © Carlos Bento, Amílcar Cardoso, Ernesto Costa 34Kb CaseMemory Raciocínio Baseado em Casos (CBR) Exemplo P: CPU RAM Monitor Disk Modem PIII 128M 17” 4G 56Kb S: ???? Retrieve Revise Reuse Retain 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 S: interstar 200 © Carlos Bento, Amílcar Cardoso, Ernesto Costa 34Kb CaseMemory Raciocínio Baseado em Casos (CBR) Exemplo P: CPU RAM Monitor Disk Modem PIII 128M 17” 4G 56Kb S: ???? P: CPU RAM Monitor Disk Modem PIII 21” 128M 4G+4G 56Kb S: Megacom 500 Retrieve Revise Reuse Retain 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 S: interstar 200 © Carlos Bento, Amílcar Cardoso, Ernesto Costa 34Kb CaseMemory Raciocínio Baseado em Casos (CBR) Exemplo P: CPU RAM Monitor Disk Modem PIII 128M 17” 4G 56Kb P: CPU RAM Monitor Disk Modem S: ???? PIII 128M S: Megacom 500 17” 4G 56Kb 21”->17” minus 4G P: CPU RAM Monitor Disk Modem PIII 21” 128M 4G+4G 56Kb S: Megacom 500 Retrieve Revise Reuse Retain 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 S: interstar 200 © Carlos Bento, Amílcar Cardoso, Ernesto Costa 34Kb CaseMemory Raciocínio Baseado em Casos (CBR) Exemplo P: CPU RAM Monitor Disk Modem PIII 128M S: Megacom 500 17” 4G 56Kb 21”->17” minus 4G Bom? Retrieve Reuse Revise Retain 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 S: interstar 200 © Carlos Bento, Amílcar Cardoso, Ernesto Costa 34Kb CaseMemory Raciocínio Baseado em Casos (CBR) Exemplo P: CPU RAM Monitor Disk Modem PIII 128M S: Megacom 500 17” 4G 56Kb 21”->17” minus 4G SIM! Retrieve Reuse Revise Retain 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 S: interstar 200 © Carlos Bento, Amílcar Cardoso, Ernesto Costa 34Kb CaseMemory Raciocínio Baseado em Casos (CBR) Exemplo P: CPU RAM Monitor Disk Modem PIII 128M S: Megacom 500 Retrieve Revise Reuse 17” 4G 21”->17” minus 4G Retain 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 S: interstar 200 © Carlos Bento, Amílcar Cardoso, Ernesto Costa 56Kb 34Kb CaseMemory Raciocínio Baseado em Casos (CBR) Exemplo Retrieve P: CPU RAM Monitor Disk Modem P: CPU RAM Monitor Disk Modem PIII 17” 64M 4G Retain Revise Reuse PIII 34Kb 128M S: Megacom 500 S: Interstar 300 17” 4G 21”->17” minus 4G 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 © Carlos Bento, Amílcar Cardoso, Ernesto Costa 56Kb CaseMemory Raciocínio Baseado em Casos (CBR) Alguns Aspectos Representação de Casos Pares Atributo/Valor Redes Semânticas Métodos de Recolha Identificar as Características Procura (por índices) Correspondência (por semelhança) Selecção (por métrica) Métodos de Reutilização Cópia (solução, método) Adaptação(solução, método) © Carlos Bento, Amílcar Cardoso, Ernesto Costa Raciocínio Baseado em Casos (CBR) Alguns aspectos Métodos de Revisão Avaliação da Solução (por um perito, no mundo real, num modelo) Reparação (o próprio, o utilizador) Métodos de Retenção Extracção (descriptores, soluções, justificações, método) Índices (quais?) Integração © Carlos Bento, Amílcar Cardoso, Ernesto Costa Raciocínio Baseado em Casos (CBR) Representação de Casos Caso: conhecimento contextualizado relativo a uma experiência Problema + Solução Tipos de informação num caso: Idênticos aos de uma base de dados Problema Solução Nome: Produções Milagre das Rosas Número de Contribuinte: 408804480 Capital Social: 5.000 contos Tempo de Actividade: 2 anos Facturação anual: 15.000 contos Pedido de Empréstimo: 3.000 contos Resultado do pedido: concedido Spread: 1,05% © Carlos Bento, Amílcar Cardoso, Ernesto Costa Caracterís ticas (features) Raciocínio Baseado em Casos (CBR) Base de Casos: Conjunto representativo de Casos cobrindo os objectivos do raciocínio incluindo tentativas para atingir esses objectivos tentativas bem sucedidas propor soluções tentativas falhadas evitar falhas Casos: históricos desenvolvidos com um perito no domínio Tarefa crítica: construção e organização da Base de Casos © Carlos Bento, Amílcar Cardoso, Ernesto Costa Raciocínio Baseado em Casos (CBR) Indexação Para acelerar o processo de Recolha Nome: Belmiro Serpa Tinhas Idade: 52 anos Número de Doente: 2035 Morada: R. do Bem Viver, 7878 ANJOS Foto: Características não-indexadas Características indexadas Sexo: masculino Peso: 83 Kg Tipo de Sangue: A……………………. Indexação demasiadameste genérica demasiados Casos demasiadamente específica insucesso na Recolha © Carlos Bento, Amílcar Cardoso, Ernesto Costa Raciocínio Baseado em Casos (CBR) Recolha de Casos Té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 © Carlos Bento, Amílcar Cardoso, Ernesto Costa Raciocínio Baseado em Casos (CBR) Recolha pelo Vizinho Mais Próximo Exemplo: Empréstimos Bancários êNDICES Rendimento Mensal Pagamento Mensal RESULTADO Bom ou Mau Emprstimo Representação gráfica das características indexadas: Pagamento Mensal Um Caso Rendimento Mensal © Carlos Bento, Amílcar Cardoso, Ernesto Costa Raciocínio Baseado em Casos (CBR) Recolha pelo Vizinho Mais Próximo Pagamento Mensal Casos bem sucedidos Casos mal sucedidos Rendimento Mensal Novo Caso Possível Métrica de Semelhança: A B d AB (XAB wX ) (YAB wY ) © Carlos Bento, Amílcar Cardoso, Ernesto Costa Raciocínio Baseado em Casos (CBR) Recolha por Indução A 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 © Carlos Bento, Amílcar Cardoso, Ernesto Costa Raciocínio Baseado em Casos (CBR) Recolha por Indução Exemplo: Empréstimos Bancários Estado do Emprstimo Rendim ento Mensal Situa‹o Laboral Pagamento Mensal Caso 1 Bom 300 Ass alariado 30 Caso 2 M uito mau 600 Ass alariado 60 Caso 3 M uito bom 450 Recibo Ve rde 40 Caso 4 Mau 250 Ass alariado 50 Pagamento Mensal < 50c.? Sim Situação Laboral Assalariado Caso 1 Não Rendimento Mensal > 250c.? Recibo Verde Caso 3 © Carlos Bento, Amílcar Cardoso, Ernesto Costa Sim Caso 2 Não Caso 4 Raciocínio Baseado em Casos (CBR) Adaptação Tipos de Adaptação: Nenhuma (ex.: empréstimo bancário) Estrutural Usar regras ou fórmulas de adaptação para preencher ou alterar características Derivacional Reutilizar no Caso Corrente as regras ou fórmulas que produziram a solução no Caso Recolhido © Carlos Bento, Amílcar Cardoso, Ernesto Costa Raciocínio Baseado em Casos (CBR) Algumas aplicações Diagnóstico de Falhas em Máquinas Diagnóstico de Redes de Computadores Análise de Crédito Previsão de Depósitos Geológicops Planeamento (de batalhas...) Compreensão de Linguagem Natural Projecto Criativo © Carlos Bento, Amílcar Cardoso, Ernesto Costa Raciocínio Baseado em Casos (CBR) Algumas Aplicações Gestão de Redes Raciocínio Legal Atribuição de Responsabilidades em Seguros Diagnóstico médico Previsão Meteorológica Detecção de Fraudes Planeamento e Escalonamento © Carlos Bento, Amílcar Cardoso, Ernesto Costa Raciocínio Baseado em Casos (CBR) Books Janet Kolodner, “Case-Based Reasoning”, Morgan Kaufmann, 1993 David B. Leake (Ed.),” Case-Based Reasoning: experiences, lessons and future directions”, MIT Press,1996 Web Links http://www.ai-cbr.org/ http://www.cbr-web.org/ Introductory material A. 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. 316. © Carlos Bento, Amílcar Cardoso, Ernesto Costa Raciocínio Baseado em Casos (CBR) História Schank 82 (MOPs) Kolodner 84 (CYRUS) Gentner 83, Carbonell 83,86 (Analogy) © Carlos Bento, Amílcar Cardoso, Ernesto Costa
Download
