Embed Size (px)
Citation preview
1
Raciocínio Baseado em Casos
Teresa Ludermir
Centro de Informática - UFPE
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
9
“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”
10
“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
11
Sistemas Especialistas convencionais:
(alguns) Sistemas Especialistas de segunda geração:
Experiência
Experiência: o que o especialista tem de mais valioso
RegrasEngenheiro de conhecimento
Experiência RegrasAlgoritmo deaprendizagem
12
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
13
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
14
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.
15
Exemplos
Aulas de Aldo von Wangeheim Transparências 8 - 24
16
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
17
Fases do RBC
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
21
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
22
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?
23
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.),
Quantidade de casos distribuir bem no espaço de problema n-dimensional
(n atributos)
24
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.
25
Representação dos Casos
Várias linguagens de vetores de características Atributo-valor (frames, redes semânticas,
objetos, ...) lógica de primeira ordem
26
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
27
Indexação
Interpretação de situação os índices realmente relevantes para um
problema/situação em particular
preçoanomodelomarcaopcionaiskilometragemmotorcor....
28
Indexação
Indexação pelo vizinho mais próximo Baseada na distância euclidiana entre o novo caso e
os casos armazenados;
Indexação indutiva 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;
29
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
30
Adaptação dos casos
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
31
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
32
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;
33
Avaliação e reparo dos casos
Revisão1) Avaliar a solução (automaticamente ou não)2) Consertar o caso
Retenção: Se algo ensina alguma lição para o futuro, chame-o de caso1) Extração da informação a reter2) indexação3) inserção/integração do caso na base
exemplo: ajuste dos pesos de determinados atributos de um caso;
34
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;
35
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
36
Quando usar CBR?
Existem conhecimento para adaptação de casos
Existem muitas exceções às regras É preciso aprender “on-line”
37
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
38
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
39
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
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 PROC 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 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
45
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.
46
Aplicações: estado da arte Todas as classes de problemas dos SE´s
diagnóstico, planejamento, scheduling, interpretação, 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
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
48
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
49
Find Me: http://infolab.cs.uchicago.edu/entree
50
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/CBR-
Homepage.html CBR Bibliography:
http://www.surveying.salford.ac.uk/AI-CBR/biblio/search.html
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
