Schemi di rappresentazione della conoscenza
By Ugo Chirico
Quest'articolo illustra alcuni tra i più comuni schemi di rappresentazione della conoscenza, al fine di chiarire gli aspetti fondamentali da prendere in considerazione nella scelta di un modello adeguato.
Sistemi di produzione
Calcolo dei
predicati
Reti Semantiche
1 Sistemi di produzione
Introdotti da Post nel 1943 come
meccanismo di computazione del tutto generale, furono
usati per la prima volta in matematica negli algoritmi di
Markov [Ma54], e ripresi successivamente da Chomsky
[Ch57], che li usò in linguistica con il nome di "Rewrite
Rule". In Intelligenza Artificiale fanno la loro
prima apparizione con Newell e Simon che li usarono, nel
1965 [Ne65], per l’analisi del gioco degli scacchi,
e nel l972 [Ne72] per rappresentare il comportamento
umano nella soluzione dei problemi. Sono stati
successivamente ripresi e utilizzati come modello
psicologico della conoscenza umana. (Young [Yo76])
(Evertz [Ev82])
Oltre ad essere visti come un meccanismo generale di
computazione e quindi in ultima analisi come uno stile di
programmazione (si può infatti dimostrare che hanno la
potenza di calcolo delle macchine di Turing), sono
largamente utilizzati come modo di rappresentare la
conoscenza nei sistemi esperti.
I sistemi di produzione seguono uno schema generale
composto da tre elementi indipendenti:
- Regole di produzione
- Global Database
- Interprete delle regole
Le regole di produzione sono divise in parte sinistra (LHS) e parte destra (RHS). La parte sinistra rappresenta la premessa, la parte destra l’azione che deve essere eseguita qualora la premessa sia verificata. Talvolta vengono chiamati ‘Antecedente’ e ‘Conseguente’. Si possono immaginare come istruzioni del tipo
IF premessa THEN azione
Ogni volta che la premessa di una
regola è soddisfatta l’ azione conseguente deve
essere eseguita, e comporterà una modifica o un aggiunta
di fatti nel Global Database.
Le regole di produzione offrono una rappresentazione
della conoscenza di facile accesso e facilmente
modificabile. Per tale motivo ben si addicono ai sistemi
disegnati per realizzare approcci incrementali delle
competenze.
Il Global database è in generale una collezione di
elementi simbolici, e rappresenta lo stato del mondo.
Conterrà anche quelle informazioni derivanti
dall’applicazione delle regole.
Il lavoro dell’interprete è diviso in una fase di
‘riconoscimento’, in cui viene effettuato il
test di verifica della premessa, che avviene mediante un
processo detto di ‘Pattern Matching’
in cui la parte sinistra della regola, viene confrontata
con il contenuto del Global Database, e una fase di
‘azione’ in cui, qualora la premessa sia
soddisfatta, viene eseguita l’azione conseguente. Ad
esempio se ho una regola del tipo
IF "Il corpo x è libero di muoversi" AND "Il corpo x è soggetto ad una forza" THEN "Il corpo x si muove"
ed ho nel Global database due fatti che corrispondono alle premesse
"Il corpo x è libero di muoversi"
"Il corpo x è soggetto ad una forza"
allora l’effetto dell’applicazione di tale regola è l’aggiunta nel Global Database del fatto
"Il corpo x si muove".
Talvolta, il lavoro
dell’interprete viene affiancato da una componente
di risoluzione dei conflitti, che entra in azione quando
si presentano più regole applicabili (Meta-livello).
Vengono introdotte in questo modo le meta-regole, che
permettono di introdurre diverse strategie per risolvere
i conflitti.
L’ interprete di un sistema di produzione può agire
‘forward’ o ‘data driven’
in contrapposizione a ‘backward’ o ‘goal
directed’ . Nei primi il problema viene risolto,
a partire da quello che si sa, producendo tutto ciò che
si può ottenere dalla conoscenza iniziale, utilizzando
un procedimento iterativo. Nei secondi il problema viene
risolto, a partire dal risultato che si vuole ottenere,
cercando di vedere se dall’insieme delle conoscenze
iniziali è possibile, ottenere il risultato voluto,
utilizzando un procedimento ricorsivo. La ricerca forward
solitamente si usa quando da una serie di fatti noti si
vuole conoscere tutto ciò che ne scaturisce. Viceversa
la ricerca backward parte dalla meta e prende in esame
solo le regole che lo interessano, in particolare le
regole dal quale può essere dedotta, scartando le altre.
Consente in questo modo di accelerare la computazione. I
principali vantaggi offerti dai sistemi a regole di
produzione sono:
- Facilità nell’aggiornamento (aggiunta e cancellazione di regole e di elementi nel Global database)
- Semplicità di lettura ed esplorazione della conoscenza
- Alta modularità. In particolare la base di conoscenza e meccanismo di inferenza sono completamente indipendenti ed esplorabili separatamente
- Rapidità nel costruire spiegazioni (Con l’aggiunta di meta-regole è possibile spiegare il perché della scelta di una particolare regola)
A causa della forte modularità, unita
alla difficoltà con cui si segue il flusso della
computazione, i sistemi a regole di produzione risultano
idonei laddove l’indipendenza tra i vari pezzi di
conoscenza è di primaria importanza, ma poco utilizzati
quando l’interesse ricade sul flusso della
computazione. Un classico esempio in cui si utilizza un
sistema a regole di produzione è la costruzione di un
dimostratore automatico di teoremi in una qualche teoria
formale. Identificheremo l’insieme degli assiomi
della teoria nel Global Database, l’insieme delle
regole di deduzione, nell’insieme delle regole di
produzione, e l’insieme di procedure per generare
nuove prove nell’interprete
2 Calcolo dei predicati
Chiamato anche ‘Logica del primo
ordine’, il calcolo dei predicati è spesso
utilizzato per la formulazione di un linguaggio atto a
rappresentare la conoscenza. Si presenta come il
sostituto formalizzato del linguaggio naturale e propone
un meccanismo inferenziale estremamente semplice per la
manipolazione della conoscenza: l’attività di
deduzione, di prova, genera la conoscenza implicitamente
contenuta nella conoscenza iniziale, che compare
sottoforma di assiomi. In particolare, consent di
costruire ‘database deduttivi’ dai quali si
possono inferire molte più informazioni di quante sono
effettivamente memorizzate nelle relazioni iniziali.
Ben si addice a rappresentare domini costituiti da
oggetti e loro proprietà, o da relazioni tra oggetti. Il
meccanismo di estrazione della risposta è connesso al
fatto che molti problemi possono essere formulati come
domande ad una base di conoscenza. Tali domande si
traducono in enunciati da dimostrare nel sistema di
assiomi definito dalla base di conoscenza, utilizzando le
regole di inferenza della logica formale. Per tale
motivo, un sistema che utilizza il calcolo dei predicati,
viene visto come un particolare sistema di produzione in
cui:
- Il Global database contiene gli assiomi della teoria
- Le regole rappresentano le regole di inferenza, tra cui il modus ponens, la generalizzazione, la risoluzione (nel caso si utilizzi un linguaggio a clausole).
- L’interprete diventa un qualsiasi sistema di pattern-matching.
Una base di conoscenza espressa in
linguaggio predicativo, può essere interrogata, in modo
‘forward’ o ‘backward’,
allo stesso modo dei sistemi a regole di produzione: nel
primo caso, partendo dai fatti iniziali, applicando
ripetutamente le regole di inferenza si ricava tutto ciò
che ne scaturisce; viceversa nel secondo partendo dal
fatto che si vuole ottenere si cerca di vedere se esso è
deducibile dai fatti iniziali. E’ inoltre possibile
introdurre delle strategie di ricerca della soluzione
(meta-regole), in questo modo il processo di computazione
diventa un processo di deduzione guidato da
un’euristica.
Il principale vantaggio offerto da un linguaggio
predicativo sta nella semplicità e naturalezza con cui
è possibile rappresentare gli elementi della conoscenza,
che risulta in tal modo facilmente comprensibile. Ad
esempio una frase del tipo "Tutti i romani erano
fedeli a Cesare" viene tradotta in linguaggio
predicativo dall’enunciato
" x romano(x) Þ fedele(x, Cesare)
Dal fatto romano(Caio) si ottiene, applicando il modus ponens alla regola precedente, il fatto fedele(Caio, Cesare), cioè che Caio era fedele a Cesare.
Il linguaggio di programmazione PROLOG [St86], è un esempio di linguaggio predicativo:
- gli elementi da rappresentare vengono espressi mediante clausole di Horn;
- la regola di inferenza adottata è la risoluzione.
Un programma PROLOG è equivalente ad
un insieme di assiomi, derivanti dalla base di
conoscenza, mentre la sua esecuzione è equivalente alla
dimostrazione di un teorema nel sistema di assiomi
definito dal programma. Tale dimostrazione avviene
utilizzando come regola di inferenza la risoluzione
(Robinson [Ro65]).
3 Reti Semantiche
Le reti semantiche sono dei formalismi
per rappresentare la conoscenza aventi una struttura a
grafo. Solitamente i nodi rappresentano oggetti,
concetti, stati, mentre gli archi, eventualmente
etichettati, rappresentano le relazioni tra i nodi.
Esse condividono l’idea di base che strutture
complesse possano essere descritte come una collezione di
attributi, e valori associati, e che il ragionamento è,
nella sua forma più astratta, una realizzazione di
collegamenti, la cui giustificazione è riconducibile al
‘buon senso’: esperienza, somiglianza,
dipendenza, tipicità.
Sono state spesso proposte come modello della memoria
umana, e largamente utilizzate per la comprensione del
linguaggio naturale.
Originariamente, nascono come un modo di rappresentare il
significato delle parole di un linguaggio naturale
(Quillian [Qu68]), e di seguito estese a poter
rappresentare gli enunciati. Quillian era
dell’opinione che la comprensione del linguaggio
naturale non potesse avvenire semplicemente attraverso
regole e orientò i propri studi sulla semantica del
linguaggio naturale, diversamente da Chomsky [Ch65], che
ne studiò la sintassi. Ad esempio, prendiamo in
considerazione le seguenti frasi:
"Il veliero è ancora in fondo al mare" e
"Il pescatore trovò l’ancora in fondo al mare"
è evidente come l’espressione
"ancora in fondo al mare", assume un
significato diverso in base al contesto. Mediante un
analisi semantica è però più agevole riconoscere se la
parola "ancora" è un avverbio o un
oggetto. Per tale motivo, lo studio della semantica del
linguaggio naturale è un tentativo di descrivere il
significato del mondo (e l’uso di parole quando il
loro significato è ambiguo).
Le reti semantiche sono usate a diversi livelli:
- Livello implementativo, nel quale le reti sono viste come strutture dati, con puntatori e liste come primitivi.
- Livello logico in cui il linguaggio delle reti diventa una variazione notazionale di qualche linguaggio formale.
- Livello concettuale, focalizzato sulle relazioni concettuali, e sulla semantica in senso linguistico.
- Livello linguistico nel quale parole ed espressioni arbitrarie sono usate come primitivi.
Diamo alcuni esempi di reti semantiche:
Figura A Esempio di rete semantica
Is_a link costruisce gerarchie ereditarie. La rete in figura a rappresenta in maniera esplicita il fatto che Noé è un aquila reale, e che un aquila reale è un uccello. Mediante l’ Is_a link, rappresenta implicitamente anche il fatto che Noé è un uccello.
Figura B Esempio di rete semantica
L’ estensione
dell’ereditarietà ad ogni tipo di arco porterebbe
la rete a rappresentare anche il fatto: "Noé è
studiato dai naturalisti", che non è
necessariamente vero. Questo problema mette in evidenza
che l’estrazione della conoscenza implicita in una
rete semantica non può essere permessa solo grazie
all’esistenza di un cammino fra due nodi, occorre
definire quali sono le catene permesse.
Le reti semantiche vengono spesso utilizzate per
rappresentare il Global database di un sistema di
produzione o per rappresentare la base di conoscenza di
un Sistema Esperto. In entrambi i casi la componente di
inferenza interroga la rete per estrarre la soluzione.
Supponiamo ad esempio, riferendoci alla rete di figura B,
di voler sapere chi è Noè. A tal proposito viene
generata la rete di interrogazione di figura C
Figura C Rete di interrogazione
Tale rete verrà poi confrontata con la base di conoscenza, generando le soluzioni in figura d
Figura D Risultato del confronto
Bibliografia
[Ch57] Chomsky, N., Syntactic Structures, Mouton, The Hague, 1957[Ch65] Chomsky, N. Aspect of the teory of syntax, Cambridge, Mass., Mit Press, 1965
[Ev82] Evertz, R., "A Production System Account of Children’s Errors in Fraction Subtraction", Computer Assisted Learning Research Group, Technical Repost No. 28, Open University, Milton Keynes, U. K., 1982
[Ma54] Markov, A. A, "Theory of Algorithms", National Academy of Sciences, Moskow, U.S.S.R., 1957
[Ne65] Newell, A, Simon, H. A., Computer Augmentation of Human Reasoning, Spartan Books, Washington, DC, 1965
[Ne72] Newell, A., Simon, H. A., Human Problem Solving, Prentice-Hall, Englewood Cliff, NJ, 1972
[Qu68] Quillian, M. R., "Semantic Memory", in: Minsky ed., Semantic Information Processing, Cambridge, Mass., MIT Press, 1968
[Ro65] Robinson, J. A., "A Machine-Oriented Logic Based On The Resolution Principle", JACM 12, pp. 23,41, gennaio 1965
[St86] Sterling, L., Shapiro E., The Art of Prolog, MIT Press, 1986
[Yo76] Young, R. M., Seriation by Children: an Artificial Intelligence Analisys of a Piagetian Task, Birkhauser Verlag, Basel, 1976