Raciocínio Baseado
em Casos
Teresa Ludermir
Centro de Informática - UFPE
1
Aprendizado Baseado em
Instâncias
K-vizinhos mais próximos (Nearest
Neighbours)
 Raciocínio Baseado em Casos

2
Aprendizado Baseado em
Instâncias



A aprendizagem consiste somente em armazenar
os exemplos de treinamento <x1,c1>, <x2,c2> . . .
<xn,cn>.
Após a aprendizagem, para encontrar o valor do
conceito alvo associado a uma instância de testes
<xt, ? >, um conjunto de instâncias similares são
buscadas na memória e utilizadas para classificar
a nova instância.
A generalização é feita somente quando uma
nova instância deve ser classificada.
3
Aprendizado Baseado em
Instâncias
Muitos métodos de aprendizagem
constroem uma descrição geral e explicita
da função alvo a partir de exemplos de
treinamento.
 Os métodos de aprendizagem baseados
em instâncias simplesmente armazenam os
exemplos de treinamento.

4
Aprendizado Baseado em
Instâncias
Constroem uma aproximações para a
função alvo para cada instância de teste
diferente.
 Constrói uma aproximação local da função
alvo.
 Podem utilizar representações mais
complexas e simbólicas para as instâncias

5
Aprendizado Baseado em
Instâncias

Uma desvantagem é o alto custo para
classificação.
Toda a computação ocorre no momento da
classificação !!!
 Aumenta com a quantidade de exemplo de
treinamento.

6
Raciocínio baseado em regras RBR

Um sistema que usa RBR resolve
problemas tomando uma especificação
de entrada (ou desenvolvendo um
conjunto de perguntas-e-respostas com
o usuário) e então “encadeia” um
conjunto de regras apropriadas obtidas
a partir de uma base de regras para
chegar a uma solução.
7
Raciocínio baseado em regras

A capacidade de aprendizagem não é algo
inerente aos sistemas baseados em regras;


Dificuldade de adaptação às mudanças, surgimento de
novos problemas dentro do domínio corrente;
A construção e a manutenção são tarefas
que demandam muito tempo



A extração de regras junto a especialistas também é uma
tarefa árdua;
As regras são inerentemente dependentes de outras regras;
É muito complexa a tarefa de eliminação erros.
8
“Pessoas: 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”
9
“Pessoas: Experiência vivida”


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 intalações dos mísseis
cubanos/russos, seria como no caso de
Pearl Harbor
10
Experiência: o que o especialista
tem de mais valioso

Sistemas Especialistas convencionais:
Regras
Experiência
Engenheiro de
conhecimento

(alguns) Sistemas Especialistas de
segunda geração:
Experiência
Regras
Algoritmo de
aprendizagem
11
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

aprendizado incremental on-line

suavisa necessidade de aquisição de conhecimento

tem plausibilidade cognitiva
Experiência
Experiência
12
O que é Raciocínio Baseado em
Casos (RBC) ?

Case-based reasoning system is ... reasoning by
remembering. Leake, 1996

A case-based reasoner solves new problems by adapting
solutions that were used to solve old problems. Riesbeck
& Schank, 1989

Case-based reasoning is a recent approach to problem
solving and learning ... Aamodt & Plaza, 1994

Case-based reasoning is both ... The ways people use
cases to solve problems and the ways we can make
machines use them. Kolodner, 1993
13
Definição de RBC

Raciocínio Baseado em Casos (RBC) é um paradigma
de IA que utiliza experiências passadas para solucionar
problemas correntes


Abordagem muito utilizada por seres humanos para resolver
problemas práticos
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.
14
Exemplos

Aulas de Aldo von Wangeheim

Transparências 8 - 24
15
Fases do RBC

Em geral, sistemas de RBC estão relacionados
aos processos:
Representação de Casos
 Indexação de Casos
 Armazenamento e Recuperação de Casos
 Adaptação de Casos
 Avaliação e Reparo de Casos

16
Fases do RBC
17
RBR vs. RBC – Obtenção de
conhecimento

RBR



Articulação de soluções é realizada por
inferências sobre um conjunto potencialmente
grande de regras;
É preciso reestruturar o código para acomodar
expansões e tratamento de casos particulares.
RBC


O aprendizado é uma tarefa natural, através da
retenção de novos casos;
O conhecimento do domínio não precisa ser
completamente definido no desenvolvimento do
sistema.
18
RBR vs. RBC - Memória

RBR

Não possuem memória, o que obriga a
construção de soluções sempre a partir do zero.
 Erros anteriores tendem a acontecer novamente.

RBC


Possuem uma memória de casos anteriores,
continuamente incrementada.
Permite construir soluções a partir de outras,
minimizando o tempo gasto e evitando cometer
novamente os mesmos erros;
19
RBR vs. RBC - Robustez

RBR


Quando um problema não se encaixa em
nenhuma regra, o sistema simplesmente
não pode resolvê-lo.
RBC

Podem adaptar casos com
características similares que podem ser
úteis para resolver o problema atual.
20
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
manutenação e refinamento são
delicados
é lento
21
Desenvolvimento de um sistema
RBC






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?
22
Natureza e conteúdo dos casos

Pergunta chave


Conteúdo



O que é um caso no domínio abordado?
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.),
Quantidade de casos

distribuir bem no espaço de problema ndimensional (n atributos)
23
Representação dos Casos



Definição do conteúdo que será armazenado.
Determinação das características mais relevantes
de cada caso.
Busca de uma estrutura apropriada para
descrever estas características.
24
Representação dos Casos

Várias linguagens
de vetores de características
 Atributo-valor (frames, redes semânticas,
objetos, ...)
 lógica de primeira ordem

25
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

26
Indexação

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
27
Indexação

Indexação pelo vizinho mais próximo


Indexação indutiva


Baseada na distância euclidiana entre o novo caso e
os casos armazenados;
Determina indutivamente quais as características mais
importantes para os vários casos;
Indexação baseada em conhecimento

Utiliza o conhecimento existente na literatura para cada
caso e determina quais características são importantes
para recuperá-los;
28
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

29
Adaptação dos casos
Objetivo: compensar as diferenças
entre o problema-alvo e problemafonte 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 gerada30

Adaptação dos casos

Para as duas últimas formas de
adaptação 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
31
Exemplo de Adaptação


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;
32
Avaliação e reparo dos casos

Revisão
1) Avaliar a solução
2) Consertar o caso

(automaticamente ou não)
Retenção: Se algo ensina alguma lição para o
futuro, chame-o de caso
1) Extração da informação a reter
2) indexação
3) inserção/integração do caso na base
 exemplo: ajuste dos pesos de determinados
atributos de um caso;
33
Aprendizado em RBC
No aprendizado de máquina tradicional,
existe a fase do aprendizado e a fase de
utilização: indução e dedução;
 Em RBC, o aprendizado é parte do
processo de resolução de problemas;
 O princípio: é mais fácil aprender retendo
um exemplo concreto de solução do que
tentar generalizar tais experiências;

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
35
Quando usar CBR?
Existem conhecimento para adaptação de
casos
 Existem muitas exceções às regras
 É preciso aprender “on-line”

36
Problemas

Aquisição & descrição dos casos


O controle da medida de similaridade é fraco
pois o matching é parcial



nem sempre é trivial além de demandar
conhecimento do domínio!
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 é
37
Combinando RBC com RN
RBC e RN têm sido combinados em algumas
pesquisas recentes
 Integração pode ocorrer por:

Divisão de tarefas entre a RN e o RBC
 Projeto de uma arquitetura inteligente combinando
características de RN e RBC

38
Combinando RBC com RN

Casamento e indexação de casos
Maioria das combinações
 Procura padrões de similaridade entre os casos

Auxiliar processo de Raciocínio do sistema
RBC
 Definir arquitetura neural mais adequada para
uma dada aplicação

39
Aplicações de RBC - [Prudêncio
2002]



RBC foi utilizado juntamente com
Algoritmos Genéticos (AG) e Redes
Neurais Artificiais (RNA) para a previsão de
séries temporais por [Prudêncio 2002];
O sistema de RBC mantém uma base de
casos em que cada caso armazena a
descrição de um problema resolvido com
redes neurais e a solução aplicada.
Diante de um novo problema, uma consulta
é feita à base de casos, recuperando as
soluções usadas nos problemas mais
similares.
40
Aplicações de RBC - [Prudêncio
2002]



Essas soluções são inseridas na população
inicial dos AGs, que são responsáveis por
adaptá-las;
Após a execução dos AGs, a solução final
poderá ser inserida na base de casos, para
auxiliar a solução de problemas futuros.
As
redes
geradas
pelo
modelo
apresentaram
maior
poder
de
generalização, além de um número menor
de conexões de rede.
41
Aplicações de RBC - [Prudêncio
2002]
42
Aplicações de RBC - [Prudêncio
2002]
43
Aplicações de RBC - [Prudêncio
2002]
 Módulo

Transforma uma série temporal não estacionária
em uma série estacionária, ou seja, que não
apresentam tendência e sazonalidade;
 Módulo

PROC
GBC
Mede a similaridade do problema atual com
todos os problemas armazenados na base e
retorna os mais similares.
O número de casos retornados da base é igual ao
número de cromossomos da população dos AGs;
Usa a distância euclidiana.
 Módulos

AG e TR
Operam cooperativamente na busca pela melhor
solução.
44
Um Novo Modelo de
Automatização: RBC e AG

Projeto das redes é tratado de forma híbrida:
 uso de conhecimento e busca.

Conhecimento é usado para iniciar o processo
de busca.

Base de casos é usada para inicializar a
primeira população dos AGs.

No modelo proposto, RBC manipula o
conhecimento e AGs realizam a busca.
45
Aplicações: estado da arte

Todas as classes de problemas dos SE´s


Existem ferramentas (shells)


diagnóstico, planejamento, scheduling,
interpretação, design, seleção, ensino,....
ReMind, CAsePOint,CASUEL, ART*, ReCall, CBRExpress,...
Exemplos





Machine Tool Fault Diagnosis
Computer Network Diagnosis
Credit Analysis
Geological Deposit Prediction
Battle Planning
46
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

FIND-ME AGENTS
sugere filmes e carros em locadoras
 raciocino através de exemplos


BUTTLER AGENTS


sugere hotéis, restaurantes, oficinas, ...
CORRESPONDENT AGENTS

usa técnicas de recuperação de casos para
encontrar textos: FAQ-finder
48
Find Me:
http://infolab.cs.uchicago.edu/entree
49
Referências



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.uni-kl.de/~lsa/CBR/CBRHomepage.html
CBR Bibliography: http://www.surveying.salford.ac.uk/AICBR/biblio/search.html
50
Referências


Prudêncio, R. Projeto Híbrido de Redes
Neurais, Dissertação de Mestrado, Centro
de Informática, Universidade Federal de
Pernambuco, 2002.
Braga , A. P. Braga, Caravalho, A. C. P. L.
F. and Lurdermir , T. B. Redes Neurais
Artificiais: teoria e aplicações. LTC, Rio de
Janeiro, 2007.
51