Case Based Reasoning

sartori@disco.unimib.it

Un pò di storia

• Approccio formalizzato da Janet Kolodner

• Pittosto recente

• Algoritmo per la risoluzione di problemi basato sul ragionamento per analogia

Filosofia

Il principio guida dell’approccio CBR è il seguente:

Problemi simili hanno soluzioni simili

Quindi, soluzioni adottate in passato possono essere recuperate per risolvere nuove situazioni critiche

CBR e Ingegneria della Conoscenza

• Il CBR nasce come problem solving method• Particolarmente utile quando non si riesce a

costruire un modello di conoscenza completo e preciso– Dominio difficile– Conoscenza eterogenea– Poco tempo a disposizione

• Negli ultimi anni si sta imponendo come metodologia efficace ed efficiente per la realizzazione di Knowledge Management Systems

Il Ciclo CBR: le 4 R

CBR e Problemi

Il CBR permette di affrontare e risolvere due categorie di problemi:

Retrieve Classificazione

Revise Costruzione

Il Caso: struttura

Rappresentazione di un caso

• Flat

• Gerarchica

• A grafo

Retrieve = Classificare ?

Problema Problema

Sono simili ?

Stessa categoria Stessa categoria

Sì No

Come recuperare casi

• Utilizzo di funzioni di similarità:SIM : CxC [0, 1]

• Input: la descrizione del problema

• Output: un numero reale compreso fra zero e uno (% di similarità)

• Uno dei due casi in ingresso è non risolto e si indica con Cc

• L’altro è risolto e si indica con Cr

Algoritmi di Retrieval

Cc Cr

Stesso valore?

Stesso valore?

K-Nearest Neighbour

Il valore di similarità è una media pesata della funzione SIM applicata ai valori di tutti gli attributi della descrizione del caso:

n

ffsimwCrCcSIM

n

i

rci ii 1

* ),(),(

Revise = Costruzione ?

ProblemaSoluzione

Recuperata

La soluzione va

bene?

Ho “costruito” la soluzione

Uso la soluzione come punto di

partenza

Sì No

ConoscenzaSpecifica dominio

Algoritmi di Revise

Soluzioner Soluzionec

Mofica valore?

Modifica valore?

Algoritmi di Revise

• Difficili da implementare

• Spesso si lascia all’utente/esperto il compito di modifcare la soluzione recuperata

• Gli algoritmi più diffusi si basano sul concetto di substitutional adaptation

Substitutional Adaptation• Dato che il caso corrente e quello recuperato sono diversi, la basa dei casi

potrebbe contenere altre coppie di casi con le stesse (o simili) differenze

• Questi casi agiscono da rappresentanti del caso corrente (Ccr) e di quello recuperato (Rcr)

• La differenza tra le soluzioni dei rappresentanti (vettore vi) dà un’indicazione di come modificare la soluzione del caso recuperato Rc per risolvere il caso corrente Cc (vettore v’)

• v’ è un’aggregazione delle differenze v1, ..., vn,, tra le soluzione associate a Ccr e Rcr

PROGETTO P-RACE

Un approccio basato sulla conoscenza per supportare il processo decisionale del

Race Engineer

L.Int.ArL.Int.ArDipartimento di Informatica, Sistemistica e ComunicazioneDipartimento di Informatica, Sistemistica e Comunicazione

Università di Milano - BicoccaUniversità di Milano - Bicocca

OBIETTIVO DEL PROGETTO

Sviluppare un sistema di supporto alle decisioni riguardanti la progettazione e l’utilizzo della mescola giusta per partecipare ad una gara (e vincere)

CONCORRENTI

punti deboli e di

forza

FONDO

STRADALE

CIRCUITI

DISEGNO

BATTISTRADA

CONDIZIONI

AMBIENTALI

DATI

TELEMETRICI

ASSETTO VETTURA

DATI STORICI

ASSOCIAZIONI

MESCOLA/PERFORMANCE

CHIMICA DEI

MATERIALI

RELAZIONE TRA MODIFICHE, PROPRIETÀ

CHIMICO-FISICHE E PERFORMANCE

RUOLO,

INFLUENZE E

RELAZIONI TRA

INGREDIENTI

ACQUISIZIONE KNOWLEDGE ENGINEERING

CONOSCENZA EPISODICA

Compound Designer

Race Engineer

CASO PASSATO

NUOVO CASO

Riutilizzo

Innovazione

Creazione

UTILIZZOARCHITETTURA

Modulo fuzzy

Base dei casi

Recupero dei casi

Nuova soluzion

e

Motore CBR

Motore inferenziale

Abstract Compound Model

UTILIZZOINTERFACCIA del RACE ENGINEER

Similarity ComputationSimilarity Computation

ffc c = (f= (f11cc,...,,..., ffnn

cc): case representation): case representationfft t = (f= (f11

tt,...,,..., ffnntt)) : target problem: target problem

Two step processTwo step process Initial MatchInitial Match: selects a subset of the Case Memory: selects a subset of the Case MemoryIM(CM, fIM(CM, ftt) = set of cases C) = set of cases Cii such that such that

sev_index(Csev_index(Cii)=sev_index(f)=sev_index(ftt))

Similarity FunctionSimilarity Function: computes similarity between cases: computes similarity between cases

sim(fsim(ftt, f, fcc) = ) = i=1..ni=1..n[[wwii * SIM(f * SIM(fiitt, f, fii

cc))]/]/i=1..ni=1..nwwii withwithwwi i = match_weight = match_weight if SIM(fif SIM(fii

tt, f, fiicc)<Threshold)<Threshold

wwi i = no_match_weight = no_match_weight if SIM(fif SIM(fiitt, f, fii

cc)>Threshold)>Thresholdwwi i = no_value_weight = no_value_weight if fif fii

tt or f or fiicc is unknown is unknown

SIM(fSIM(fiitt, x): gaussian curve with mean value f, x): gaussian curve with mean value fii

tt and given standard and given standard deviation deviation