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]) mentre in altri sono usati per comprendere i motivi che spingono a fare certe scelte, per rappresentare la conoscenza umana e per prevedere il comportamento dell'avversario nei giochi di strategia quali la dama, gli scacchi fino ai giochi tipici dei casino.
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

Articoli


642-552 takes the edge off the common intimidations to the objective installation. 1z0-042 Oracle certification is suggested for those IT experts who have acquired ora10g008 or comparable to the ora10g009.
642-892 may also be considered in place of the BSCI as well as BCMSN tests needed for CCNP as well as CCDP certifications. 70-630 involves internet information server, its running and configuration.
650-621 teaches you skills for the Cisco Lifecycle Services approach to assist productively sell, develop, and support Cisco technologies and enhance their performance.
642-432 covers subject areas including fundamental IP Telephony operation, support, maintenance, and assimilation with an accessible PSTN network.