Il CBR (Case-Based Reasoning) è un modello di ragionamento in grado di sfruttare le informazioni, raggruppate in istanze di problemi già risolti, chiamati casi. L’esperienza acquisita è mantenuta memorizzando i casi passati in una libreria (library, o Case Base), e la soluzione di un nuovo problema è affrontata recuperando i casi più simili dalla Case Base, e sfruttando le soluzioni ad essi applicati. La tecnica di problem solving del CBR può essere riassunta in quattro passi, conosciuti come ciclo CBR o ciclo 4R:
- retrieve: recupera dalla Case Base i casi più simili al nuovo caso
- reuse: riutilizza questi casi, e le loro soluzioni, per risolvere il nuovo problema
- revise: verifica la nuova soluzione
- retain: memorizza il caso corrente nella Case Base, per futuri problem solving
Il Retrieve consiste nel recupero dalla libreria dei casi più simili a quello in input. Si prende la soluzione del caso recuperato e si prova a riutilizzarla come soluzione del caso target. Se la soluzione è uguale ed è riutilizzabile per il caso target allora il problema è risolto. Se invece la soluzione del caso recuperato, per quanto simile, non può essere riutilizzata così com’è, è necessario eseguire un’operazione di Revise della soluzione,
cioè di “adattamento” o “revisione” della stessa per fare in modo che vada bene per il caso target. Si ottiene in questo caso un “caso riparato” cioè un caso che ha una soluzione ottenuta adattando la soluzione di un caso precedente. Il passo di revisione potrebbe anche fallire e in questo caso il sistema non è in grado di fornire una soluzione per il nuovo caso. Una volta che il caso è stato risolto, o direttamente o mediante adattamento di una soluzione vecchia, occorre decidere se memorizzare questo nuovo caso nella libreria oppure no. Se si, si esegue il Retain, cioè si “trattiene” il nuovo caso che diventa un learned case, cioè un “caso appreso”. Il sistema in questo modo ha aumentato la sua conoscenza. Se la soluzione trovata tra i casi a disposizione nella libreria è andata bene per il nuovo caso senza bisogno di adattamenti allora è inutile inserirlo a sua volta in memoria perchè non si farebbe altro che creare un doppione. In generale si inserisce il nuovo caso se o si è dovuta adattare pesantemente la soluzione proposta tra quelle disponibili oppure il sistema non è stato in grado di trovare la soluzione e ci si è dovuti affidare a qualche strumento esterno (Buco di conoscenza).
Come indicato nella figura, un insieme di conoscenze generali (general knowledge) possono essere integrate a supporto del processo CBR. Il supporto fornito varia a seconda del tipo di processo CBR e del dominio dell’applicazione, e può essere nullo (o molto scarso), oppure molto forte (sistemi Knowledge-intensive). Per general knowledge si intende una conoscenza generale del dominio di applicazione, in opposizione alla conoscenza operativa fornita dai casi memorizzati.
Il CBR appare quindi una metodologia adatta ad integrare diversi tipi di conoscenza, in particolare conoscenza strutturata, e conoscenza non strutturata (basata sull’esperienza), fornendo così l’integrazione di informazioni di tipo diverso.
Occorre quindi sostanzialmente risolvere un problema partendo dalla soluzione di un problema simile già risolto in precedenza e memorizzato nella libreria dei casi che costituisce la base di conoscenza. Il caso da ricercare nella libreria dei casi deve essere più simile possibile a quello nuovo dato in input. Questa affermazione comporta 3 problemi:
- Trattandosi di un sistema automatico occorre definire il concetto di “casi simili”. Cosa si intende quando si afferma che 2 casi sono simili? Perchè un determinato caso è più simile a quello nuovo rispetto ad un altro?
Queste sono tutte domande a cui bisogna essere in grado di dare una
risposta. - Oltre a definire “come” recuperare i casi più simili, occorre anche stabili
“quanti” recuperarne. - Come riutilizzare la soluzione generata. Se i problemi sono uguali
identici allora posso utilizzare la “stessa” soluzione. Ma in molti casi anche una piccola differenza tra i casi può compromettere completamente il riutilizzo della soluzione. (Ad esempio per un caso con i sintomi di influenza per cui la soluzione è stata una aspirina, il discorso cambia molto nel caso in cui per il nuovo problema in input il paziente sia allergico mentre quello del caso recuperato no).
La soluzione a questi “problemi” prende il nome di KNN (K Nearest-Neighbour) ovvero una strategia per il recupero dei K casi più vicini a quello in input in cui si eseguono sostanzialmente i seguenti step:
- si definisce una funzione di distanza tra i valori di ogni features (distanza locale) con la ovvia conseguenza che più due casi sono distanti e meno simili, mentre più sono vicini più sono simili
- si calcola la distanza tra un caso in input (target) e quelli nella case memory combinando le distanze sulle singole features
- si scelgono (retrieval) i K casi più vicini al target e si usano le loro soluzioni come base per la soluzione del target (adaptation).
Quindi, partendo dal primo di questi tre punti, occorre decidere come definire la distanza locale su ogni attributo e come combinare le varie distanze locali sugli attributi per ottenere la distanza globale fra i casi.
Funzioni di similarità locale e globale
E’ possibile introdurre, per ogni attributo, un peso ‘w’ che rappresenta l’importanza dell’attributo stesso nel calcolo della distanza globale. Per calcolare quindi la distanza globale tenendo conto del peso degli attributi si fa una “media ponderata”, cioè si prende la distanza tra i due valori dell’attributo fk e la si moltiplica per il peso
dell’attributo. Si ottiene cosi il contributo dell’attributo fk. Facendo la somma dei contributi di tutti gli attributi presenti nel caso e dividendo per la somma dei pesi si ottiene appunto la media ponderata o “media pesata”. Nel caso in cui gli attributi abbiano tutti peso uguale il risultato non sarebbe altro che una normale media delle distanze locali.
Il valore della distanza viene poi in genere normalizzato nell’intervallo [0,1].
Quindi due casi che hanno distanza 0 sono casi identici tra loro, mentre a distanza 1 sono il più diverso possibile. Se si vuole il valore di similarità S, anziché il valore di distanza D, basta fare S = 1 – D.
Una distanza uguale a 0 corrisponde infatti ad una similarità uguale a 1.
Come definire le distanze locali sugli attributi?
Si separano gli attributi(features) in 2 categorie:
- Nominali: non hanno ordinamento
- Lineari: hanno ordinamento
La differenza è che in un attributo lineare esiste un ordinamento tra i valori mentre in un attributo nominale no. Gli attributi numerici sono lineari, perché hanno ordinamento. Si possono avere quindi attributi lineari discreti (numeri interi), oppure continui (numeri reali).
Un esempio di attributo nominale potrebbe essere il colore di un oggetto: giallo, rosso, ecc; si hanno quindi dei valori che non hanno un ordinamento.
Si applica quindi, a seconda del tipo di attributo e delle necessità, una funzione di similarità locale, e attraverso l’attribuzione di pesi si calcola il contributo dei vari attributi per il recupero dei casi. A questo punto i K casi per cui il valore di similarità risulta maggiore vengono recuperati e le loro soluzioni sono proposte come soluzioni per il nuovo caso in input.
Per poter riutilizzare la soluzione del caso recuperato nel nuovo caso query che si sta valutando, occorre tener conto di due aspetti:
- le differenze tra il caso recuperato e il nuovo caso
- quale parte del caso recuperato può essere trasferita al nuovo caso
Esistono fondamentalmente due modi per riutilizzare i casi passati:
- riutilizzare la soluzione del caso recuperato (transformational reuse)
- riutilizzare il metodo con il quale è stata costruita la soluzione del caso
recuperato (derivational reuse)
Nel transformational reuse la soluzione del caso recuperato non è applicata direttamente al nuovo caso, ma esiste della conoscenza, sottoforma di operatori trasformazionali, che permette di trasformare la vecchia soluzione in una soluzione per il nuovo caso. Il transformational reuse non focalizza la sua attenzione su come un problema è risolto, ma si concentra sull’equivalenza delle soluzioni, e questo richiede un forte modello di conoscenza basato sul dominio. Il derivational reuse, invece, guarda come il problema è stato risolto nel caso recuperato. Quest’ultimo contiene informazioni riguardanti il metodo utilizzato per risolverlo, insieme alla giustificazione degli operatori usati, i subgoal, le alternative considerate, e altro. Il derivational reuse reinstanzia il metodo usato sul nuovo caso, e riesegue il vecchio metodo nel nuovo contesto.
Una volta che, dalla fase reuse, si giunge ad una soluzione occorre verificare se essa sia corretta o meno. E’ quindi necessario sincerarsi dell’esito della soluzione applicata, e, se essa non è corretta, si presenta comunque l’occasione di imparare da un fallimento.
Questa fase è chiamata case revision, e consiste di due metodi:
- valutazione della soluzione generata dal reuse. Se ha successo, si passa direttamente alla fase di retain
- altrimenti, si cerca di rivedere la soluzione utilizzando le conoscenze specifiche del dominio
Grazie al successivo processo di retain è possibile aggiungere alla conoscenza esistente le informazioni ritenute utili, derivate dal caso risolto. L’apprendimento dal successo o fallimento della soluzione proposta, è guidato dagli outcome (risultati) derivati dalla sua valutazione ed eventuale riparazione. E’ necessaria la selezione delle informazioni del caso ritenute rilevanti, in quale forma conservarle, come indicizzare il caso per recuperi futuri, e come integrarlo nella struttura esistente.
Si sono quindi analizzati a livello introduttivo, in questa parte, gli aspetti fondamentali e i principi che stanno alla base del CBR; la descrizione dei dettagli di ciascuna delle fasi che compongono un ciclo di CBR esula dagli scopi di questo documento e, in tal senso, si rimanda quindi alla abbondante letteratura disponibile al riguardo.
I conclusione, si può ancora aggiungere che il CBR è in grado di emulare il ragionamento umano basato sull’esperienza, ricordando le soluzioni ai problemi simili già risolti in passato, e adattandoli alla situazione corrente. Il collo di bottiglia derivato dall’acquisizione e dalla formalizzazione di conoscenza specifica (fornita da esperti in materia e tradotta in modo formale) si riduce, in quanto nuova conoscenza viene immagazzinata automaticamente dal sistema, durante il suo lavoro di tutti i giorni. All’utente non sono richiesti sforzi aggiuntivi.