Case Based Reasoning: The Revise Phase
13 Maggio 2009
Fabio Sartori, [email protected]
Outline


La fase di Revise di un sistema CBR
Algoritmi di Revise




Casi a struttura flat
Casi a struttura gerarchica
Casi a struttura grafica
Casi di studio


Revise nel sistema P-Truck Curing
Revise nel framework CKS-Net
Algoritmi di Revise
Mofica valore?
Modifica valore?
Soluzioner
Soluzionec
IL PROBLEMA
DELL'ADATTAMENTO
L'adattamento al problema è richiesto per i sistemi
CBR perché le occorrenze del problema
precedentemente risolto non sono solitamente
riconducibili a quelle del nuovo.
RETRIEVAL
ADAPTATION
METODI DI ADATTAMENTO (1)

TRANSFORMATIONAL [W. Wilke, R. Bergmann-1999]
permette la modifica, aggiunta e cancellazione degli
elementi della soluzione sotto precise condizioni.
METODI DI ADATTAMENTO (2)
GENERATIVE [W. Wilke, R. Bergmann-1999]
richiede un risolutore generativo del problema,
utilizzato per produrre una soluzione partendo da
zero.
● COMPOSITIONAL [W. Wilke, R. Bergmann-1999]
combina i componenti delle soluzioni adattate
recentemente, provenienti da casi multipli.
● HIERARCHICAL [W. Wilke, R. Bergmann-1999]
usato in combinazione con i metodi precedenti.
L'adattamento è eseguito in modalità TOPDOWN.

CBR and Adaptation
• Adaptation is the most difficult step in
designing CBR systems
• Adaptation requires a model of domain
knowledge owned by experts
• This in contrast with the basic principle of
CBR: use comparisons to overcome
difficulties in building knowledge models
• Most CBR systems develop complete
algorithms for retrieval, but not for adaptation
Generic Approaches to Adaptation




Substitutional Adaptation: similar differences among
case descriptions imply similar differences among
their solutions
Widely used in the past
Advantages: close to the CBR basic principle, simple
to implement
Drawbacks: potentially time consuming
P-Truck Project
• Goals: to design, develop and
integrate into Pirelli
information system, a KM
application based on KBS
approach to support decisionmaking processes involved in
the design and production of
truck tires
• Partners: BU Truck (Pirelli
Tires) and LabIC (DISCoUniMiB)
• Timing: 3-year project, at the
end of the 2nd year
P-Truck Curing: case structure
Category
Attribute
A category is a collection of attributes
Adaptation



Guides the curing designer towards the
determination of a good solution to curing process
design problem (i.e. time scheduling of curing steps)
Very complex: although there are some basic
principles to be followed (e.g. thicker tire-parts
require more energy), their composition is difficult
Thus, P-Truck Curing aims to supply to the designer
an indication of how to adapt the retrieved solution
to the current case
Adaptation approach
•
•
As the current case and the retrieved one have different descriptions, maybe the case base
contained other couples of cases presenting the same (or significantly similar) differences
Such cases could act as representatives for the current case (i.e. Ccr) and the retrieved one
(i.e. Rcr)
• The difference between the related solutions (vector vi) is an
indication of how to modify the solution of the retrieved case Rc to
solve the current case Cc (vector v’)
• v’ is an aggregation of v1, ..., vn,, differences among solutions related
to Ccr and Rcr
Case Representatives
• Representatives are chosen through a
retrieval algorithm:
l
! (w * diff (a , b ))
i
i
i =1
|| a – b||
• Given two cases cc and rc in the Case Base, pairs
r ,r
of representatives
are:
cc
rc
rcc, rrc # CB, dist (cc, rc )" dist (ccc, rcc ) < !
i
i
The Contribution of Representatives to
c and r represent the current and
Adaptation
retrieved cases respectively
• The result is a set of pairs of representatives Rep (cc, rc, ε)
• Every pair may give an indication on the modification to be applied to rc
modcr represents the difference
solution
among their solutions
• In particular, representatives whose solutions are homogeneous to s(rc)
are interesting, denoted by HRep (cc, rc, ε)
• Given two solutions s = {s1,…, sn} and
s’ = {s’1,…, s’
n}, the
the multiplicative
factor
fcr
modification function of each solutionrepresents
feature can
be
expressed
aspair
the relevance of the
follows
of representatives <c, r>. This factor
modss’ = (dist1(s1, s’1), …, can
distj(s
bej, as’constant
j))
1/|HRep(c
rc)|) or a function.
• Then, the modification to apply to the(e.g.
retrieved
casec, solution
is an
aggregation of differences between solutions of case representatives:
mod c =
!( f
cr
* mod cr )
c , r "H Re p ( cc , rc ,# )
Summarizing…
Compute the influence of every pair
Measure
Search fordifferences
pairs of cases
among
having
current
similar
… and finally aggregateofall
contributions on the overall
representatives
and
differences…
retrieved case descriptions…
to obtain the adaptation
vector.
adaptation…
Applicability of the Approach



Cases described as sequences of pairs [attribute, value]
Cases can be characterized by more complex descriptions (e.g. trees, graphs, …) but
fixed
Case solution attributes should be numeric…




… otherwise a specific method for the specification of how to compute and aggregate
differences among symbolic fields must be defined
If case descriptions are not homogeneous computation of distances should be
changed:
 computing differences among solutions (i.e. representatives)…
 …and adptation of retrieved case solution are going to be investigated
The simplest strategy is to limit the search for representatives to those cases with
homogeneous d and s to the current and retrieved ones
Another strategy could be to consider deeper domain knowledge
Case Based Reasoning and Storytelling
Integration: a Way to Acquire and
Represent Social and Domain
Knowledge in the Design of
Knowledge Management Systems
Complex Knowledge Structure
A Complex Knowledge Structure (CKS) is a mean to acquire and
represent in a uniform way domain and social knowledge within a
group
Domain Knowledge  related to problem solving activity
Social Knowledge  related to social relationships among people
ESIGENZE ADATTIVE

SOLUZIONE PROPOSTA POCO ATTUALE
●
NECESSITA' DI ADATTARE LA SOLUZIONE
ALLE SPECIFICHE DEL PROBLEMA
●
APPROCCIO DI SIMILARITA' DEL
FRAMEWORK CKS-NET
Algoritmo di Retrieval
CKS1 CKS3 CKS5
Individuazione nodi critici UCKS
UCKS
Individuazione nodi critici della CKS corrente
CKS2 CKS4 CKS6
Ricerca nodi equivalenti
30
Se insieme nodi equivalenti è vuoto CKS scartata
Altrimenti viene indicizzata…
Calcolo valore di similarità
Se valore > 50% CKS passa al Riuso della
soluzione passata
CKS2
CKS5
WHAT
Riuso della
soluzione
UCKS
WHY
A
B
R1
CKS2
indicizzata
HOW
D
F
E
Obbiettivi Diversi
CKS scartata!
R2
CKS5
indicizzata
R3
G
H
B
R4
Stessi
Obbiettivi!
SCELTA DEL METODO

PERMETTA MODIFICA NODI SOLUZIONE
●
PERMETTA AGGIUNTA/ELIMINAZIONE
NODI SOLUZIONE
●
NON RICHIEDA CONOSCENZA AUSILIARIA
METODI TRANSFORMATIONAL [W. Wilke, R. Bergmann-1999]
SUBSTITUTIONAL
STRUCTURAL
ALGORITMO DI ADATTAMENTO
ADATTAMENTO
AUTOMATICO
Metodo
computazionale
che propone
soluzioni adattive
derivanti da una
ricerca per obiettivi
ADATTAMENTO
MANUALE
Permette la
modifica manuale
della soluzione
proposta, sotto
particolari vincoli
DIAGRAMMA DI FLUSSO
L'utente sceglie
quale metodo di
adattamento
applicare
L'utente sceglie
se applicare i
metodi di
adattamento
ADATTAMENTO AUTOMATICO
CASI CONSIDERATI DAL
RETRIEVAL
CASI CONSIDERATI
DALL'ADATTAMENTO
AUTOMATICO
VINCOLO DI SIMILARITA' STRUTTURALE PER LA
PROPOSTA DI SOLUZIONI ADATTIVE.
ALGORITMO
L'ultima parte dell'algoritmo si occupa di calcolare la similarità delle CKS
Nella
primanella
parteINDEXED-CKS.
dell'algoritmo siOgni
eseguono
inizializzazioni
e gli
contenute
valore tutte
vieneleconfrontato
con quello
assegnamenti
parametri che saranno fondamentali per l'esecuzione.
massimo
finoparte
addei
ora
La
seconda
delraggiunto.
metodo è dedicata alla valutazione delle CKS
presenti
nella
base dei
aldeve
riconoscimento
deii nodi
nodi,
strutturalmente,
Da
notare
la similarità
creazione
dicasi
un earray
contenente
tutti
why
del maggiore
problema
La
CKS
con
massima
avere similarità
strutturale
equivalenti.
Il metodo
si articola
in retrieval
un grosso
che
passa
innon
rassegna
e
l'iniziazione
deldella
parametro
contenente
il numero
di CKS
che
compongono
rispetto
a quella
soluzione
di
e, ciclo
nel caso
questa
esista,
tutte
le CKS
dellalimite
base dei
casi. Da notare la condizione di accesso alla
la
base
dei
casi.
superare
il valore
di 50.
valutazione dei nodi equivalenti.
ESEMPIO (1)
Si vuole preparare
un della
Applicazione
tortino conproposta
gli asparagi.
adattiva.
Ci si accorge della
mancanza degli asparagi.
Si ricerca un possibile
Soluzione di retrieval con
sostituto che garantisca
similarità strutturale:
uncon
gusto piacevole e un
Proposta adattiva
sapore poco speziato.
similarità strutturale:
ADATTAMENTO MANUALE
PERMETTE LA MODIFICA MANUALE
DELLA SOLUZIONE ATTUALE.
VINCOLI:
●
●
NON SI POSSONO ELIMINARE/MODIFICARE
NODI DESCRIZIONE E OBIETTIVO
NON SI POSSONO ELIMINARE/MODIFICARE
RELAZIONI TRA I NODI DESCRIZIONE
ESEMPIO (2)
La soluzione
dell'utente viene
applicata al problema.
La soluzione di
retrieval e la proposta
adattiva non
soddisfano l'utente.
Compare la finestra di
adattamento manuale.
L'utente
L'utente
può modifica la
soluzione
modificare
la secondo le
proprie
soluzione
nelesigenze.
rispetto
dei vincoli.