Raciocínio Baseado em Casos (CBR) © Carlos Bento, Amílcar Cardoso, Ernesto Costa SPs Baseados em Regras Vantagens: Regras oferecem forma de representação

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



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



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



Solução CBR

Experiência Experiência



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



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]



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



O modelo

Espaço do Problema

Espaço das Soluções

Revise

Reuse

Problema novo

Retrieve

Retain



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



Retrieve Reuse Revise Retain

Case Memory

P: CPU RAM Monitor Disk Modem PIII 64M 17” 4G 34Kb

S: Interstar 300


S: interstar 200


S: ????

P: CPU RAM Monitor Disco Modem PIII 128M 21” 4G+4G 56Kb

S: Megacom 500

Exemplo: escolher um computador



Exemplo


CaseMemory


S: Interstar 300

P: CPU RAM Monitor Disk Modem PIII 128M 21” 4G+4G 56Kb

S: Megacom 500


S: interstar 200


S: ????



Exemplo


CaseMemory


S: Interstar 300


S: Megacom 500


S: interstar 200


S: ????



Exemplo


CaseMemory


S: Interstar 300


S: Megacom 500


S: interstar 200


S: ????



Exemplo


CaseMemory


S: Interstar 300


S: Megacom 500


S: interstar 200


S: Megacom 500


S: ????



Exemplo


CaseMemory


S: Interstar 300


S: Megacom 500


S: interstar 200


S: Megacom 500


S: Megacom 500 21”->17” minus 4G


S: ????



Exemplo


CaseMemory


S: Interstar 300


S: Megacom 500


S: interstar 200



Bom?



Exemplo


CaseMemory


S: Interstar 300


S: Megacom 500


S: interstar 200



SIM!



Exemplo


CaseMemory


S: Interstar 300


S: Megacom 500


S: interstar 200





Exemplo


CaseMemory


S: Interstar 300


S: Megacom 500


S: interstar 200





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)



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)



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)



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



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



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



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



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



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



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



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



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



Algumas AplicaçõesGestão de RedesRaciocínio LegalAtribuição de Responsabilidades em SegurosDiagnóstico médicoPrevisão MeteorológicaDetecção de FraudesPlaneamento e Escalonamento



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.



HistóriaSchank 82 (MOPs)

Kolodner 84 (CYRUS)

Gentner 83, Carbonell 83,86 (Analogy)

Documents

Raciocínio Baseado em Casos (CBR) © Carlos Bento, Amílcar Cardoso, Ernesto Costa SPs Baseados em Regras Vantagens: Regras oferecem forma de representação