Cerchiamo di valutare l'occupazione di spazio nei due casi. La BFS procede un livello alla volta; OPEN contiene inizialmente S0 (livello 0); in questo passo come nei successivi, vengono generati tutti i successori, che sono poi conservati in OPEN finché non si esauriscono tutti gli stati del livello precedente. Quindi OPEN conterrà 2 stati, ovvero 1 e 2 in figura. Quando si sarà terminato l'esame del livello 1, ovvero una volta esaminato il nodo 2, OPEN arriverà a contenere 4 stati. Dopo aver consumato tutti gli stati del livello 2, in OPEN troveremmo tutti gli stati del livello 3 ossia 8 stati. Un eventuale 4 livello riempirebbe OPEN con 16 stati,e così via.

In generale, all'interno dell'insieme OPEN, in corrispondenza del livello k potrebbe essere necessario inserire in OPEN 2^k stati. L'occupazione di memoria cresce perciò in maniera esponenziale col numero dei nodi dell'albero, un dato preoccupante, poiché sarebbe sufficiente un albero anche di pochi livelli per saturare la memoria del computer. Ad esempio se ogni stato occupasse un solo byte (ipotesi comunque inverosimile) basterebbero 30 livelli per saturare 1 Gbyte di memoria.

Che dire del caso DFS? Inizialmente OPEN contiene S0 (1 stato). Espandendolo, ci mettiamo i due stati del primo livello (dimensione di OPEN: 2). Espandiamo 2, che viene rimosso da OPEN; OPEN comprenderà quindi a questo punto gli stati 1 - 3 - 4 (dimensione: 3). Dopo aver espanso 4, conterrà 4 stati. In definitiva, ogni volta che si scende di un livello si toglie uno stato da OPEN e se ne aggiungono 2. Esaminati i figli 6 e 5 di 4 (dimensione OPEN passa da 4 a 3 e a 2) si torna indietro esplodendo il nodo 3, e così via.

Si può verificare che il numero massimo di stati occupati è quello che si raggiunge quando si arriva al nodo 6 dell'albero di ricerca, ovvero 4 stati. Quindi per un albero di livello massimo k con 2 regole applicabili ad ogni stato l'insieme OPEN non conterrà mai più di k stati. Anche se le regole applicabili ad ogni nodo fossero più di 2, il numero di stati rimarrebbe comunque proporzionale alla profondità; ad esempio per 3 regole avremmo nel caso peggiore 2*k nodi aperti, per 4 regole 3*k e via dicendo.

La situazione appare nettamente vantaggiosa rispetto al caso BFS (la complessità computazionale passa da esponenziale e lineare). Perché dunque non limitarsi allo studio del solo algoritmo DFS?

Per comprenderlo, basta riflettere su cosa accadrebbe qualora la soluzione del problema fosse costituita dal nodo 3, e l'albero fosse di profondità infinita lungo il ramo che inizia dal nodo 4. In questo caso, l'algoritmo esaminerebbe prima i discendenti di 4, ma essendo questi ultimi in numero infinito non avrebbe la possibilità di tornare indietro e quindi non troverebbe mai la soluzione.

In generale, se la soluzione non esistesse, entrambi gli algoritmi procederebbero all'infinito (il problema diviene indecidibile). Se esistesse, l'algoritmo BFS dato il suo funzionamento 'per livelli' arriverebbe presto o tardi a determinarla, mentre l'algoritmo DFS potrebbe trovarla, ma, come si è visto nell'esempio, potrebbe anche girare all'infinito senza trovarla mai.

La ricerca in ampiezza provoca una occupazione di memoria notevole, ma fornisce la garanzia di trovare sempre la soluzione, se esiste. Quella in profondità richiede poca memoria (e, tra l'altro, è facile da implementare con la ricorsione) ma può rendere il sistema indecidibile anche quando una soluzione del problema in effetti esiste. Quale strategia è consigliabile seguire?

Sono state introdotte delle variazioni sul tema degli algoritmi presentati che permettono di raggiungere dei buoni compromessi fra decidibilità ed efficienza. Una prima modifica che possiamo fare all'algoritmo DFS è di introdurre un limite massimo alla profondità che l'algoritmo può raggiungere. I nodi risultanti dall'espansione di uno stato S verranno inseriti in un insieme OPEN solo se la loro profondità non supera un livello massimo definito dall'utente del SF.

Supponiamo, nell'esempio in fondo a pagina 14, di introdurre come livello massimo di profondità 4, e che la soluzione sia il nodo 3 (quindi a livello 3). L'algoritmo prende inizialmente la strada sbagliata, esplora i discendenti di 4, ovvero 5 e 6, e poiché è stato raggiunto il limite di profondità non vengono costruiti i relativi successori. Quindi, tolti i nodi 5 e 6 da OPEN, si passa ad esaminare il nodo 3 ed essendo questo la soluzione del problema l'algoritmo termina con successo.

Introdurre un limite alla profondità mette l'algoritmo in condizioni di dare una risposta in un tempo finito. Abbiamo però introdotto un nuovo problema: il problema dell'orizzonte. La soluzione infatti potrebbe essere situata proprio un livello più in basso del limite da noi fissato, e quindi l'algoritmo non sarebbe in grado di 'vederla'. In questo modo, il sistema diviene decidibile, ma perde la proprietà di completezza. Ovviamente, se tutte le soluzioni si trovano in livelli al di sopra del limite massimo di profondità, il sistema rimane completo anche in seguito a tale posizione. (Ricordiamo che un SF completo può trovare tutte le soluzioni al problema esistenti nel mondo reale, un SF coerente non può trovare soluzioni che siano errate alla luce dell'interpretazione nel mondo reale).

ITERATIVE DEEPENING. Il problema di scegliere il livello massimo è dunque molto delicato, perché se è troppo alto ne risente l'efficienza, se è troppo basso corriamo il rischio di perdere soluzioni. L'idea più utilizzata è allora la seguente: partiamo da un certo limite; esploriamo lo spazio degli stati alla ricerca della soluzione; se non la troviamo, aumentiamo il limite e ricominciamo daccapo. Questo metodo costringe quindi a rifare del lavoro già fatto, ma lo spreco di tempo che ne consegue è piccola cosa in confronto al vantaggio relativo all'occupazione di memoria.

Sempre con riferimento al caso di pag.14, notiamo che se il limite fissato alla profondità in un certo istante è k, vuol dire che dobbiamo esaminare 2^k-1 stati. Se ad esempio decidiamo di porre il limite = 3, dovremo esplorare 7 stati. Se ciò non serve a trovare la soluzione, poniamo il limite = 4 e quindi dovremo esaminare 15 stati in tutto; se però abbiamo avuto l'accortezza di salvare l'informazione relativa agli stati già esplorati, in realtà gli stati da esaminare saranno soltanto 8. Se il limite passa a 5 dovremmo prendere in considerazione complessivamente 31 stati, ma di questi solo 16 saranno effettivamente da esaminare, e via dicendo. Quindi, procedendo secondo questa strategia (con il salvataggio dei livelli già esaminati) otteniamo un aumento sul tempo di ricerca del 50%. Tale aumento è controbilanciato dai vantaggi in termini di memoria. I meccanismi di cache e di memoria virtuale presenti in tutti i calcolatori moderni privilegiano gli algoritmi che usano poca memoria. Inoltre la decidibilità è garantita. Questo algoritmo è detto di ricerca in profondità con approfondimenti successivi (iterative deepening).

Ovviamente, siamo comunque costretti ad inserire un limite massimo alla ricerca (perché la soluzione potrebbe non esistere), ma ciò vale anche per la ricerca in ampiezza.

ALGORITMI DI RICERCA IN PRESENZA DI GRAFI. I due algoritmi BFS e DFS permettono di gestire in maniera efficiente la ricerca cieca in un albero, ma che accade se il problema non determina uno spazio degli stati configurato come albero? Se applichiamo ad un grafo e non ad un albero gli algoritmi BFS e DFS nella forma Iterative Deepening, troveremo che entrambi funzionano, sia pure in modo non ottimale, dal momento che la presenza di cicli può condurli ad esaminare stati già esplorati. Consideriamo ad esempio uno spazio degli stati strutturato come il grafo di sinistra (che continua all'infinito nella forma raffigurata).

Se applichiamo BFS, l'algoritmo parte da S0, costruisce S1 ed S2; esplora S1, del quale costruisce l'unico successore S3 (messo in OPEN). Esplora poi S2, e di conseguenza costruisce di nuovo lo stato S3 e lo aggiunge alla lista OPEN. Quindi, l'algoritmo crea due istanze di S3 poiché non riconosce che lo stato era stato già preso in considerazione in precedenza.

Dal momento che l'algoritmo considera diverse le due istanze di S3, genera due copie anche degli stati S4 ed S5 come successori delle istanze di S3. Con lo stato S6 si ripresenta il problema di prima, e quindi l'algoritmo genera ben 4 copie di tale stato; ogni copia di S6 viene quindi espansa, e così via. In pratica, viene costruito un albero del tipo indicato a destra, nel quale il numero dei livelli raddoppia sempre: da 1 stato del livello 0 ai 2 stati dei livelli 1 e 2, ai 4 stati dei livelli 3 e 4, poi 8 stati, 16, e così via. Il grafo originario presentava al massimo 2 soli stati per livello. Si passa da un numero di stati proporzionale al numero di livelli, ad un numero di stati che cresce esponenzialmente col numero dei livelli, e lo stesso dicasi per il tempo necessario per l'esplorazione.

Ricordiamo che un grafo si differenzia da un albero, oltre che per la possibilità che un nodo abbia più di un padre, anche per la presenza di cicli; come incidono i cicli sugli algoritmi considerati oggi? Come è facile immaginare, essi potrebbero far sì che, anche se il grafo è finito, l'algoritmo di ricerca procede all'infinito lungo il grafo. Tale situazione è critica soprattutto per DFS. Se il ciclo si trova sulla strada intrapresa per prima dall'algoritmo, DFS rimarrà a girare all'infinito nel ciclo senza mai considerare gli altri nodi del grafo.

Se non è semplice o possibile ricondurre il grafo ad un albero, occorre quindi modificare gli algoritmi di ricerca. Il cambiamento consiste essenzialmente nell'aggiungere un ulteriore insieme, CLOSED, 'duale' di OPEN, di nodi già esplorati e sugli stati del quale l'algoritmo non deve effettuare ulteriori esami.

Si noti il diagramma di flusso del nuovo algoritmo. CLOSED viene posto inizialmente uguale all'insieme vuoto. La prima modifica interviene nel passo 'prendi stato S'. Se S è stato già visitato dall'algoritmo (in generale basta controllare se S si trova in CLOSED), si ricomincia prelevando un altro stato S da OPEN. Quindi, per lo stato S si verifica come sempre se sia una soluzione. Se non lo è, innanzitutto S viene messo in CLOSED e contrassegnato quindi implicitamente come stato già esaminato. Quindi vengono calcolati i successori, ma vengono inseriti in OPEN solo gli stati che non vi siano già presenti.

Le modifiche sono quindi due: il controllo che lo stato da esaminare non sia in CLOSED e il controllo che in OPEN non siano inseriti stati uguali. Tali modifiche complicano evidentemente l'implementazione dell'algoritmo. CLOSED deve essere una struttura dati per la quale sia efficiente l'operazione di verifica di appartenenza di un elemento (tabella hash, albero binario.). Discorso simile si può fare per OPEN, che non è intelligente strutturare come una semplice lista.

Applichiamo l'algoritmo modificato al nostro esempio (vedi figura qui a sinistra), usando la strategia BFS. Vengono generati S1 e S2 e si passa ad esaminare S1. S1 produce S3, si esamina S2. Anche S2 produce S3, ma poiché S3 si trova già nell'insieme OPEN esso non vi viene nuovamente inserito. Si passa ad esplorare S3, che produce gli stati S4 e S5; S4 produce S6 e lo stesso dicasi per S5, ma S6 viene aggiunto solo la prima volta in OPEN. Questa volta pertanto non c'è il problema dell'esplosione del numero degli stati.

L'insieme CLOSED torna utile in situazioni come quella del grafo di pagina 10, e che viene riproposto in fondo a questa pagina. Applicando ad esempio la DFS, inizialmente togliamo S0 da OPEN e lo mettiamo in CLOSED. I discendenti di S0 sono S1, S2 e S3. Esploriamo S1, che produce S4 ed S5. Esploriamo S4: lo togliamo da OPEN; S4 produce S0. S0 viene rimesso in OPEN perché non vi è più presente (vi era stato tolto in seguito all'esame iniziale), però esso si trova anche nell'insieme CLOSED, e quindi non viene esplorato di nuovo.

Si prosegue quindi con S5, tolto da OPEN e messo in CLOSED. S5 non ha successori, quindi si considera S2. S2 genera S5 (in OPEN) ed Sg, ma S5 si trova anche in CLOSED e quindi non viene preso in considerazione come possibile soluzione. Si esplora Sg che è senza successori; quindi si esplora S3, e l'algoritmo termina. Riscontriamo dunque che anche in presenza di cicli la DFS riesce ad esplorare in modo esaustivo ed efficiente lo spazio degli stati, purché quest'ultimo non sia infinito.

Le modifiche illustrate hanno ovviamente anche delle controindicazioni, delle quali la peggiore è sicuramente questa: l'esigenza di memorizzare la lista CLOSED. Si ricordi infatti che in CLOSED mettiamo tutti gli stati man mano che vengono esplorati. Di conseguenza, l'occupazione di memoria non è più, come nel caso DFS, proporzionale al numero dei livelli.

Con questi accorgimenti perdiamo completamente il vantaggio in termini di efficienza computazionale che era offerto da DFS, e questo spiega perché, piuttosto che applicare l'algoritmo modificato, si cerca di trasformare il grafo degli stati in un albero tutte le volte che ciò sia possibile.

Cercheremo oggi di esaminare ad un livello più generale rispetto alla scorsa lezione l'architettura di un sistema che operi secondo la tesi debole.

Un sistema Knowledge-Based (KB) è costituito dal punto di vista architetturale da 3 componenti: un database dinamico, un blocco di formalizzazione del problema ed una strategia di controllo. Problem formalization è la rappresentazione in un opportuno linguaggio del SF. La conoscenza sul dominio è rappresentata in maniera formale introducendo simboli, assiomi e regole. Quindi i sistemi KB o 'esperti' non fanno altro che manipolare i SF per effettuare la proprie elaborazioni.

Oggi esiste essenzialmente un solo linguaggio per rappresentare i SF: la logica matematica, o preposizionale, che trova realizzazione in vari linguaggi commerciali, dei quali l'esempio più notevole è il PROLOG. Ciò che li differenzia rispetto ai tradizionali linguaggi (FORTRAN, C++, JAVA) di programmazione è che essi manipolano non numeri, ma simboli. Le macchine che si considerano in questo corso sono prive ad esempio del concetto di assegnazione, che è tipico delle macchine e dei linguaggi numerici; sono incentrate sulla logica e l'elaborazione simboliche.

Control strategy è la scatola nella quale possiamo immaginare sia racchiuso il motore inferenziale (MI). Questa scatola riceve dall'esterno indicazioni sul problema da risolvere: p.e., nel caso del problema MU, riceve in ingresso la domanda, opportunamente formalizzata, se sia possibile ricavare la stringa obbiettivo a partire dai dati iniziali. La strategia di controllo, impiegando la formalizzazione del problema, e partendo dalle verità assiomatiche, costruisce un grafo i cui nodi sono i teoremi via via ricavati dall'applicazione delle regole. Abbiamo visto che le strategie di controllo possono essere data-driven o goal-driven, e la ricerca può essere portata avanti in maniera cieca o informata.

La strategia di controllo non si limita a risolvere il problema, ma fornisce all'utilizzatore del sistema esperto tutta una serie di indicazioni sull'andamento dell'inferenza. Questi sistemi cioè spiegano (attraverso appositi moduli di spiegazione) perché sono state prese determinate decisioni durante il processo di inferenza.

Il Dynamic database è una 'lavagna' sulla quale andiamo ad annotare il processo inferenziale del nostro specifico problema. È essenzialmente una memoria che contiene un insieme di elementi opportunamente collegati, e cioè il grafo di tutti i teoremi intermedi man mano che vengono generati. Viene caricato con gli assiomi e le domande poste dal problema, e, oltre ai risultati dell'unificazione, contiene le regole che sono state applicate per ottenere i vari teoremi. Esso p.e. corrisponde al supporto su cui disegniamo l'albero delle stringhe del problema MU.

Ciò che distingue i vari sistemi KB è il tipo di formalizzazione scelta caso per caso. Si noti ad esempio che, sia pure in maniera un po' forzata, è possibile ricondurre questo schema alla stessa programmazione classica: la formalizzazione del problema avviene attraverso un linguaggio opportuno (Pascal, Java etc.), nella strategia di controllo c'è il compilatore che interpreta le istruzioni, e il dynamic database è la memoria in cui registriamo i risultati dell'elaborazione.

Come detto, una tipologia di rappresentazione molto usata è la SSR. In essa, il processo risolutivo di un certo dominio viene visto come un insieme di stati (opportune strutture dati) che ne rappresentano le condizioni intermedie. Vi è un singolo stato iniziale, la condizione iniziale del problema, ed uno o più stati finali. Gli operatori sono regole applicabili ad un determinato stato e consentono di determinare qual è lo stato successivo.

UN ESEMPIO. Consideriamo il gioco dell'otto (8-puzzle), versione semplificata del gioco del quindici (una matrice di 15 tessere numerate che vengono spostate, ciascuna in uno spazio vuoto adiacente, con l'obbiettivo di raggiungere le configurazione ordinata). Si può dimostrare che non tutte le configurazioni iniziali permettono di raggiungere la configurazione ordinata. Quindi le tessere devono essere inizialmente in una disposizione che consenta di metterle in ordine dopo un certo numero di mosse.

È immediato stabilire che ogni possibile configurazione delle tessere è uno stato. Avremo quindi un numero molto elevato di stati raggiungibili. Supponiamo di voler realizzare un programma capace di risolvere l'8-puzzle. Data la configurazione iniziale, deve cioè fornire un elenco di mosse necessarie per raggiungere le configurazione ordinata. In seconda battuta, potremmo aggiungere anche intelligenza al programma: trovare fra le possibile sequenze quella cui compete il minor numero di mosse.

Mentre con un tradizionale linguaggio di programmazione implementare tale programma risulterebbe piuttosto difficile, con un SF diventa molto semplice, giacché bastano le 4 istruzioni indicate nel riquadro, corrispondenti ai movimenti delle tessere possibili ad ogni passo (per semplicità di descrizione supponiamo che sia la casella bianca ad essere spostata). Di fatto, con l'approccio AI tesi debole non dobbiamo inventare alcun algoritmo; tutto sta a trovare una formalizzazione del problema. Deleghiamo alla strategia di controllo il compito di trovare l'algoritmo in questione. Ciò che ci è richiesto è solo di formalizzare il problema attraverso un SF. Diremo allora che lo stato è una matrice 3x3 di numeri interi che vanno p.e. da 0 a 8. Resta da formalizzare il fatto che sono disponibili 4 operatori, ovvero 4 regole, che possono essere descritte come nel riquadro. Ciascuna delle 4 regole ha una precondizione: ad esempio, lo spostamento a N è possibile solo se la casellina bianca non si trova in prima riga. Si noti che in ognuno dei 4 angoli sarà possibile effettuare solo 2 delle 4 mosse; al centro tutte e 4, nelle altre posizioni saranno possibili 3 spostamenti.

Quindi, in un linguaggio di programmazione tipo il PROLOG dovremo fornire: le 4 regole, la configurazione iniziale e la configurazione finale (goal). Il sistema restituisce la lista delle mosse necessarie per raggiungere la configurazione finale ordinata.

Così facendo, abbiamo fornito al SF solo una conoscenza minima: la minima conoscenza necessaria per trovare una soluzione, senza applicare alcuna strategia di ricerca. Questo esempio dà però anche un'idea di quanto sia potente l'approccio AI. La conoscenza che noi forniamo al sistema è infatti esattamente la stessa che dovremmo dare ad un programmatore di linguaggi tradizionali (ovvero il 'cosa' fare, non il 'come' farlo, che è una responsabilità del programmatore), eppure è sufficiente perché la macchina risolva in maniera automatica il problema. Dietro tale assenza di specifica, che appare prodigiosa, si nasconde ovviamente un modo di fare tutt'altro che intelligente, dato che, almeno in questa forma basilare, la macchina si limita a generare tutte gli stati possibili e immaginabili finché non riesce a trovare quello giusto. La macchina appare cioè 'potente' nei riguardi del programmatore, ma decisamente 'stupida' nel suo funzionamento interno. Ciò dipende dal fatto che non abbiamo dato conoscenza ulteriore rispetto a quella strettamente indispensabile.

Il grafico che segue illustra una possibile disposizione (nodo del grafo) e gli stati conseguenti all'applicazione delle 4 regole. Questi dati costituiscono una porzione del Dynamic database. Per questo stato è possibile l'unificazione con tutte e 4 le regole assegnate.

E se volessimo anche minimizzare il numero di mosse? Sarebbe sufficiente fornire una quinta regola al SF: "Detta S una soluzione, trova la soluzione S' tale che lunghezza (S') < lunghezza (S) S ". Tale regola formalizza il concetto, che noi evidentemente consideriamo importante, di lunghezza minima. Da notare che ogni sequenza di mosse non è altro che un vettore: N-O-S-O-S-E etc., e ci interessa quello di lunghezza minima.

Va detto anche che questo sistema nella sua forma basilare non è decidibile, dal momento che i cammini sono in numero infinito. Il numero degli stati è finito, ma la macchina passerà probabilmente più volte per delle configurazioni uguali e quindi potrebbe almeno in via teorica non raggiungere mai la soluzione. La non decidibilità è poi garantita quando lo spazio degli stati è infinito. Come detto, si sopperisce alla non decidibilità di un sistema ponendo un limite massimo alla ricerca. Ricordiamo che per produrre un funzionamento utile, ogni SF dovrebbe godere di 3 proprietà: coerenza, completezza e decidibilità.

UNA TECNICA DI RAPPRESENTAZIONE ALTERNATIVA: PER RIDUZIONE A SOTTOPROBLEMI. In questa tecnica, rappresentiamo un problema e la sua decomposizione in sottoproblemi. In particolare, viene descritto il modo in cui le soluzioni dei sottoproblemi contribuiscono a determinare la soluzione del problema padre. Un esempio classico di rappresentazione per riduzione a sottoproblemi è la ricorsione: un problema viene rappresentato in termini dello stesso problema, posto in una forma più semplice. Così si ha ad esempio per il fattoriale: n! = n*(n-1)! .

Non rappresentiamo più gli stati, ma suddividiamo il problema in problemi più semplici; se questi ultimi sono dello stesso tipo del problema origine, parliamo di ricorsione. In ogni caso, dobbiamo correlare l'ottenimento della soluzione del problema grande a quello dei sottoproblemi. Questa rappresentazione è meno intuitiva e più sofisticata della SSR.

Un esempio: gli scacchi. Le macchine odierne che giocano a scacchi utilizzano una rappresentazione per riduzione a sottoproblemi, o al massimo una rappresentazione mista, piuttosto che una SSR. Perché diciamo questo?

Se volessimo realizzare una rappresentazione SSR di una partita a scacchi, dovremo formalizzare i concetti (problem formalization): scacchiera, pezzi e loro dislocazione iniziale, movimenti possibili, pezzi mangiati, partita vinta o patta. Abbiamo dato l'informazione minima grazie alla quale il sistema è teoricamente in grado di ricavare le sequenze di mosse che portano a dare scacco matto al re avversario (supponiamo per semplicità che la macchina giochi contro sé stessa). Ciò deve però avvenire attraverso una ricerca esaustiva nello spazio degli stati: per ogni mossa, la macchina considera tutte le possibili repliche; quindi, tutte le possibili repliche ad ogni replica, e via dicendo. C'è la necessità di avere una memoria praticamente infinita, dato che pur imponendo un limite al 'look ahead', diciamo di una ventina di mosse (dalla configurazione attuale ipotizza le repliche dell'avversario, poi tutte le repliche per ogni replica, e così via per 20 mosse) il numero di combinazioni da memorizzare è inconcepibilmente grande (si dice che le combinazioni 'esplodono').

I migliori giocatori umani di scacchi hanno un look-ahead di 20 e anche più mosse, ma essi implicitamente 'potano' l'albero degli stati considerando solo le repliche più probabili sulla base dell'esperienza, della logica e della conoscenza dell'avversario, e sono costretti a tale 'potatura', oltre che dai limiti della loro memoria, anche dal fatto che generalmente è imposto un tempo massimo entro il quale rispondere alla mossa avversaria. L'albero che essi creano nella loro mente viene cioè visitato più in profondità che in ampiezza.

È ovvio che nel caso del gioco degli scacchi, se vogliamo che la macchina sia competitiva, la conoscenza di base non è sufficiente: dobbiamo arricchirla con la strategia di gioco. La si potrebbe acquisire (e questo è proprio ciò che avviene in pratica) intervistando scacchisti particolarmente bravi e formalizzando le loro tecniche di gioco. La strategia consiste in generale nel porsi un certo numero di sotto-obiettivi che tengono conto fra l'altro del valore dei pezzi (es.: ridurre il numero dei pedoni avversari, attaccare le torri, proteggere il re etc.), invece di considerare tutte le possibili alternative. Infine, avremo ottenuto una macchina che, avendo recepito la conoscenza dell'esperto, è in grado di giocare la suo stesso livello strategico. Ciò permette anche di considerare un numero di combinazioni significativamente minore del caso discusso prima. Infatti, la macchina non prenderà in esame tutte le possibili repliche ad ogni mossa, ma solo quelle significative dal punto di vista della strategia. Per conseguenza, più conoscenza diamo alla macchina, meno quest'ultima deve lavorare durante il processo inferenziale. In questo consiste appunto la rappresentazione per riduzione a sottoproblemi (PR). Mentre in una rappresentazione SSR il blocco control strategy si limiterebbe a produrre tutti gli stati ricavabili applicando le varie mosse alla configurazione attuale, e lo stesso con gli stati così ottenuti, in una rappresentazione PR selezionerebbe solo un ristretto numero di alternative sulla base delle strategie di gioco delle quali la macchina è stata informata. Anche il dynamic database ne risulterà avvantaggiato, perché si riduce sensibilmente il quantitativo di stati da memorizzare.

Quindi, il problema generale di vincere la partita a scacchi si ridimensiona in un ristretto numero di sotto-problemi cui corrispondono uno o pochi sotto-obiettivi, e ciascun sotto-problema può essere risolto nella rappresentazione SSR o a sua volta ridotto a sottoproblemi più semplici. Così facendo stiamo apportando una modifica concettuale notevole al procedimento di risoluzione: ci allontaniamo sempre più dalla 'conoscenza zero' (minima, quella della SSR) e cominciamo a travasare sempre maggiore conoscenza dall'esterno. All'estremità opposta di questo procedimento abbiamo infatti l'algoritmo: fissata la configurazione iniziale, un algoritmo dice in maniera deterministica quale mossa successiva effettuare in conseguenza di ogni configurazione possibile. A questa situazione corrisponde la conoscenza massima del problema.

Abbiamo quindi due estremi opposti: SSR (stato iniziale e finale, regole) ed algoritmo; in mezzo c'è la rappresentazione per riduzione a sottoproblemi. Più conoscenza aggiungiamo, più ci avviciniamo ad un algoritmo risolutivo, tanto meno lavora la macchina e tanto più impegnativo è il lavoro del programmatore.

Da notare che maggiori sono le prestazioni del calcolatore, più è realistico ed opportuno adottare una rappresentazione a conoscenza minima, altrimenti, con elaboratori dai modesti dati di targa, la soluzione algoritmica diventa l'unica strada percorribile. Ma non è solo questione di tecnologia. C'è un numero non irrilevante di situazioni nelle quali la conoscenza algoritmica è scarsa o nulla, o troppo complessa da gestire (ad esempio: riconoscimento vocale o di caratteri) e quindi non rimane che rifarsi alle tecniche di AI. Non sempre quindi quelle tecniche che si affidano interamente alla macchina costituiscono solo una alternativa elegante e veloce ai tradizionali algoritmi, ma per certi problemi di rilevanza pratica rappresentano l'unica alternativa possibile.

Altro esempio: integrazione simbolica. La tecnica SSR è la più semplice da implementare: formalizzeremo il problema definendo il legame tra funzione e sua primitiva e introducendo le regole di base del calcolo analitico (differenziazione, derivazione). Partendo dalle regole di derivazione, e definito il concetto di primitiva (per una funzione f,è quella funzione g tale che g' = f), avremo precisato tutto ciò che occorre per risolvere il problema dell'integrazione simbolica. La ricerca esaustiva tuttavia darebbe luogo a tempi di calcolo esasperanti.

È qui che entra in gioco la conoscenza PR. In pratica, si ricorre alle famose regole di integrazione (per sostituzione, per parti, formule ricorrenti) che consentono di individuare determinati passi intermedi nella risoluzione dell'integrale. Ciò equivale ad arricchire il sistema mediante la conoscenza delle strategie applicabili; da notare che ciò riduce il tempo di elaborazione, ma dal punto di vista concettuale non aggiunge nessuna informazione sul problema dell'integrazione.

Volendo applicare lo schema iniziale diremo che:

il database contiene lo stato di avanzamento dell'integrazione (l'attuale passo intermedio di integrazione);

la formalizzazione del problema contiene le regole di integrazione, che si uniscono a quelle del calcolo analitico;

il sistema di controllo analizza il database e decide se è applicabile una delle regole di integrazione; in caso affermativo, determina i nuovi sottoproblemi di integrazione da risolvere.

Un altro esempio ci permetterà di sottolineare meglio la differenza fra le due rappresentazioni di SF finora viste: il problema del COMMESSO VIAGGIATORE. Una rete viaria completamente connessa collega fra di loro delle città (5 nell'esempio a fianco). A ciascuna strada è associato un costo (ad es: tempo di percorrenza, o lunghezza in km). Il commesso viaggiatore partendo ad es. da A deve visitare tutte le città passando una sola volta per ogni città; Nella Ricerca Operativa, della quale questo è un problema classico e con molte applicazioni, interessa trovare in particolare il percorso minimo, cioè quello cui compete il costo totale di percorrenza minimo.

È un problema combinatoriale (vi è un numero elevatissimo di percorsi possibili) il cui tempo di risoluzione (percorso a costo minimo) è mediamente molto elevato, ovviamente con riferimento ad esempi di dimensioni più grandi rispetto a quello raffigurato. L'approccio AI con la rappresentazione SSR non si pone il medesimo obbiettivo della ricerca operativa, quello di determinare un algoritmo efficiente, ma al contrario ci svincola totalmente dalla necessità di trovare un algoritmo risolutivo.

In tale rappresentazione, uno stato contiene una lista delle città già visitate; nello stato iniziale troveremo la sola città di partenza A e la lista si arricchirà via via con le città raggiunte in ogni possibile percorso. Ad esempio un possibile stato è ABD. Il costo è immediatamente derivabile dallo stato, per cui non è necessario rappresentarlo nello stato.

Che dire poi dell'operatore di transizione? Osserviamo che ad esempio a partire da uno stato di lunghezza 2 possiamo raggiungere un qualunque stato di lunghezza 3, purché la città che viene così aggiunta non sia già inclusa nelle due dello stato precedente. Quindi ad esempio da ABE posso raggiungere solo gli stati ABEC e ABED. L'operatore di transizione è pertanto quello che a partire dalla lista XYZ ci dà tutte le liste XYZK in cui aggiungiamo un elemento K non inserito nella lista precedente, e con K raggiungibile da Z (cioè l'ultimo elemento della lista precedente; si noti che questa seconda ipotesi è superflua nel nostro esempio, in cui il grafo delle città è completamente connesso).

Definizione dell'obbiettivo: un qualunque stato che abbia come città iniziale A, e che contenga tutte le città una sola volta (in seconda battuta potremmo aggiungere anche l'obbiettivo, che va opportunamente formalizzato, di determinare fra tutti i percorsi quello a costo minimo).

Il problema del commesso viaggiatore si risolve descrivendo la mappa dei collegamenti e formalizzando l'unica regola che determina lo stato successivo. Il MI sarà in grado di trovare la soluzione partendo dallo start node e determinando tutte le possibili combinazioni. L'albero qui a destra mostra la costruzione di una soluzione; si noti che ad ogni livello diminuisce di una unità il numero dei possibili stati successivi. Trattandosi di un albero e non di un grafo, la decidibilità è garantita. In casi realistici, la mappa dei collegamenti non è completamente connessa (o, se lo è, non viene considerata tale poiché alcuni collegamenti hanno costo troppo elevato), e ciò rende in generale meno agevole la determinazione di una soluzione.

Il sistema fornisce l'elenco di tutti i percorsi con l'indicazione del relativo costo; formalizzando in aggiunta il concetto di minimo, è in grado di fornire anche il percorso minimo. La soluzione SSR è, come più volte sottolineato, la più semplicemente realizzabile. L'obbiettivo della Ricerca Operativa è differente, addirittura duale: dato che il problema è computazionalmente oneroso, non viene neanche presa in esame la possibilità di determinare tutte le soluzioni fra le quali selezionare quella ottima, ma si cerca di raggiungere in un tempo ragionevole direttamente la soluzione ottima; in molti casi si è anzi disposti a sacrificare l'ottimalità della soluzione, accontentandosi cioè di una soluzione sub-ottima, purché l'algoritmo sia veloce.

Il problema dell'analisi sintattica. La realizzazione di un analizzatore sintattico non banale richiederebbe un tempo notevolissimo con un classico linguaggio di programmazione.

Sappiamo d'altronde che la sintassi di un linguaggio è descritta attraverso le mappe sintattiche. La mappa sintattica è la descrizione formale di un linguaggio; quindi l'insieme delle mappe costituisce di per sé l'analizzatore sintattico. Ancora una volta un approccio AI risulta conveniente dal punto di vista progettuale, proprio perché, in definitiva, esime dal progettare un algoritmo risolutivo.

Facciamo un esempio semplice di descrizione di un linguaggio attraverso la sua grammatica. Come avviene nei linguaggi naturali, anche i linguaggi di programmazione sono descrivibili attraverso un set di regole sintattiche, che ovviamente sono molte di meno e molto meno articolate.

Abbiamo due soli simboli: i caratteri a e b. Le stringhe del nostro linguaggio sono composte da questi due soli caratteri.

Le regole applicabili sono 4:

il simbolo a seguito da b (ab) è una frase del linguaggio;

il simbolo a seguito da una frase è ancora una frase;

una frase seguita dal simbolo b è ancora una frase;

una frase seguita da una frase è ancora un frase.

Con queste 4 regole possiamo costruire infinite frasi: aab è una frase ottenuta applicando in successione le regole 1 e 2; altre frasi sono: abaabab, aaaaab, mentre non sono frasi: aaa, aba, abaa etc..

L'analizzatore sintattico di un comune compilatore riceve in ingresso un insieme di keyword (int, if, return, end, costanti, variabili etc.), e deve riconoscere ogni frase come composta di frasi più semplici, ciascuna delle quali sintatticamente corretta. Deve quindi determinare se l'insieme delle parole chiave usate dal programmatore è ascrivibile ad una costruzione sintattica lecita. In modo analogo il compilatore del nostro semplice esempio riceve in ingresso una stringa di caratteri a e b e deve comprendere se tale stringa è una frase derivabile dalle 4 regole di cui sopra. Se la frase appartiene al linguaggio, il compilatore deve restituire anche la sequenza di regole in accordo alle quali si genera la frase in questione.

Il modo più semplice di costruire un analizzatore sintattico è rappresentare il problema nello spazio degli stati. In tale ipotesi, per quanto detto poco sopra a proposito delle mappe sintattiche, l'analizzatore viene ricavato senza alcuno sforzo. Le regole che governano il corretto uso del linguaggio sono infatti esattamente le regole che andremo a inserire, opportunamente tradotte, nel SF di tipo SSR che costituisce il compilatore. L'applicazione del motore inferenziale riproduce il comportamento dell'analizzatore sintattico.

In una rappresentazione SSR una qualunque frase sarà per noi uno stato. Gli operatori di transizione permettono di passare da una frase ad un'altra mediante l'applicazione delle regole lecite. Tali operatori sono quelli indicati nel riquadro qui a sinistra, che appare di semplice comprensione. Si tratta della traduzione formale delle 4 regole del linguaggio. Ad esempio, la regola 1 è così formalizzata: se $₁ e $₂ sono due frasi, la frase $₁ ab $₂ può essere vista come la frase $₁ S $₂, dove S è una frase lecita. In altre parole, se nel bel mezzo di una frase comunque lunga di simboli a e b troviamo una stringa ab, posso sostituire a tale stringa il simbolo S che denota una frase lecita. In modo simile si interpretano le altre regole formalizzate: una stringa frase lecita (S) - b è sostituibile con una frase lecita (S), etc.

Il grafo presentato di seguito serve a dimostrare, mediante l'applicazione delle regole del SF, che la stringa abaabab è una frase lecita del linguaggio. Il MI cerca di capire se le regole unificano con la stringa assegnata, ovvero se è possibile trovare opportune sostituzioni grazie alle quali la stringa iniziale e tutte quelle via via determinate sono unificabili con le regole. Alla stringa iniziale MI può applicare la sola regola 1, ma in tre modi diversi, dato che riconosciamo nella stringa tre sottostringhe di tipo ab (l'unificazione è applicabile mediante tre sostituzioni alternative). Ad esempio il primo nodo del secondo livello è ottenuto ponendo $₁ = stringa vuota e $₂ = aabab. Così facendo otteniamo le anche le altre due soluzioni parziali del livello 2.

Non è difficile ottenere con lo stesso procedimento tutti gli altri nodi-stato del grafo.

Il procedimento in questa tecnica, detta di riduzione, si arresta non appena arriviamo ad un nodo con una sola S. La risposta data dal MI è che la stringa appartiene al linguaggio. Il grafo costruito non è stato annotato: per motivi di chiarezza non è stata segnata in corrispondenza di ogni arco la regola che, applicata, permette la relativa transizione.

Di fatto, i realizzatori di nuovi linguaggi di programmazione costruiscono gli analizzatori sintattici proprio nel modo che abbiamo considerato: e cioè semplicemente ponendo le regole sintattiche del linguaggio (opportunamente tradotte) come base di conoscenza di un SF. L'analizzatore è ottenuto gratis; l'efficienza lascia ovviamente a desiderare per il solito problema dell'esplosione degli stati, ma può essere migliorata aggiungendo opportuna conoscenza al sistema.

Proseguiamo con lo studio degli algoritmi di ricerca nello spazio degli stati, occupandoci della ricerca informata. In aggiunta alle regole che consentono di passare da uno stato all'altro, disponiamo di ulteriori informazioni caratteristiche del particolare problema.

Innanzitutto si definisce un COSTO attribuito alle soluzioni che l'algoritmo può trovare. Ciò implica che le soluzioni non sono tutte equivalenti fra di loro, e l'algoritmo di ricerca deve trovare la soluzione a costo minimo. Consideriamo il solito esempio grafico di spazio degli stati.

In molte applicazioni, il costo di una soluzione può essere definito così: si assegna un costo C_i a ciascuna delle operazioni (regole del SF) che consentono di passare da uno stato al successivo. Dal momento che S_g è raggiungibile a partire dallo stato iniziale S₀ attraverso un percorso nello spazio degli stati, se attribuiamo un costo a ciascuna transizione è immediata assegnare alla soluzione un costo pari alla somma dei costi associati alle transizioni effettuate lungo il percorso per raggiungere lo stato obbiettivo. Un "possibile" costo per lo stato obiettivo nel nostro esempio è C₁ + C₂ + C₃. Nel caso generale un nodo può essere raggiunto mediante percorsi diversi (vedi linea tratteggiata in figura), quindi ogni soluzione ha più di un costo. Ogni possibile costo dipende dal percorso utilizzato per raggiungere lo stato obbiettivo. In generale è richiesto di trovare non un percorso qualsiasi, ma quello che abbia il costo più basso. Tipicamente i costi associati a ciascuna operazione di transizione sono reali e positivi: C_i > 0 (ipotesi che faremo sempre nel prosieguo). Come mai? Se così non fosse, in presenza di cicli nello spazio degli stati si potrebbe verificare che il costo di un percorso tenda a - ; in tal caso non sarebbe possibile determinare la soluzione migliore. Altra eventualità: anche se lungo un ciclo la somma dei costi fosse 0, l'algoritmo potrebbe non uscire mai dalla ripetizione infinita del ciclo, non riscontrando alcun aumento nel costo totale.

In assenza di cicli, nulla vieta in linea di principio di assegnare costi negativi alle transizioni, ma in pratica è raro che si faccia questa scelta.

Consideriamo dunque l'esempio seguente, nel quale su ogni arco è segnato un costo strettamente positivo (in generale i costi sono numeri reali, in questo caso interi per semplicità). Supponiamo inizialmente che lo spazio degli stati sia un albero. Fatta questa ipotesi, è immediato associare a ciascun nodo (oltre che a ciascun arco) un costo univoco, calcolato come somma dei costi degli archi del percorso (che è unico) necessario a raggiungerlo. Per convenzione, il nodo iniziale ha sempre costo 0.

Supponiamo anche che le soluzioni siano i nodi 9 e 10.

Il primo algoritmo di ricerca informata che vedremo viene chiamato algoritmo di ricerca a costo uniforme. In questo caso interessa non solo lo stato obbiettivo, ma anche il percorso (sequenza di stati) che arriva ad esso, percorso che va quindi memorizzato in una opportuna struttura dati.

Ricordiamo l'insieme OPEN dell'algoritmo classico di ricerca cieca. Mentre in quel caso i nodi venivano scelti secondo una disciplina LIFO o FIFO, stavolta il prossimo nodo ad essere esaminato sarà quello a costo più basso tra i nodi aperti; supponiamo dunque che OPEN sia ordinato, e perché ciò avvenga basta assicurarsi che i nodi vengano inseriti in tale insieme sempre al posto giusto in base al loro costo.

Vediamo dunque se l'algoritmo di ricerca a costo uniforme permette effettivamente di arrivare alla soluzione a costo minimo, che è la 10.

Inizialmente, l'insieme OPEN conterrà il solo nodo 0, che ha costo 0.

OPEN =

Abbiamo indicato con il pedice il numero d'ordine del nodo, e con l'apice il suo costo. S₀ viene esaminato; non è lo stato obbiettivo. L'algoritmo applica ad esso tutte le regole, ricavando i successivi 3 stati che formano l'insieme OPEN riportato di seguito. I nodi vengono inseriti in OPEN in ordine di costo.

OPEN =

Viene esaminato il nodo a costo più basso, S₁, che non è la soluzione cercata. S₁ viene quindi esploso e i due figli vengono inseriti nel giusto ordine in OPEN, che annovera a questo punto 4 stati.

OPEN =

Si esamina quindi S₃, che non è soluzione e non ha figli, eccetera. È immediato ricavare le configurazioni assunte dall'insieme OPEN man mano che l'algoritmo procede. Quando due nodi hanno lo stesso costo, è indifferente l'ordine in cui vengono posti in OPEN.

OPEN =

OPEN =

OPEN =

OPEN =

OPEN =

OPEN =

A questo punto viene espanso il primo nodo della lista ordinata, S₁₀, che è una soluzione, e quindi l'algoritmo si ferma con successo. Si può dimostrare che un algoritmo siffatto converge effettivamente alla soluzione avente il costo più basso, benché non sempre in modo efficiente. Si noti ad esempio che nel nostro caso abbiamo esaminato S₆, passando quindi vicinissimo alla soluzione ottima, e subito dopo il nodo S₇, che porta invece fuori strada.

Si noti pure che la ricerca effettuata non è stata in ampiezza, poiché una ricerca in ampiezza ci avrebbe portato a determinare S₉ come soluzione; ma non è neanche una ricerca in profondità; una ricerca in profondità non avrebbe portato ad esaminare S₇ prima di S₁₀.

L'algoritmo è detto a costo uniforme perché, se ci sono più stati allo stesso costo, questi ultimi vengono esplorati tutti prima di passare a qualunque stato che abbia costo maggiore. Vengono esaminati prima tutti gli stati di costo 1 fino all'ultimo, poi tutti quelli di costo 2, eccetera.

In molte applicazioni, il costo di ogni soluzione consiste semplicemente nel numero di passi che consentono di raggiungerla (ad esempio: nel gioco degli scacchi è il numero di mosse necessarie per dare il matto). Possiamo evidentemente interpretare questa situazione come se a ciascun arco dello spazio degli stati fosse assegnato un costo unitario. In tale ipotesi (o più in generale se il costo associato agli archi è costante), è facile verificare che l'algoritmo di ricerca a costo uniforme si riconduce all'algoritmo BFS. (In tal caso infatti il costo associato ad un nodo è pari al livello di profondità corrispondente moltiplicato per il costo di ciascuna transizione. Poiché l'algoritmo di ricerca in ampiezza esplora l'albero per livelli, in questo caso particolare garantisce di determinare la soluzione a costo minimo).

Vediamo ora il caso in cui lo spazio degli stati è un grafo (più percorsi consentono di arrivare alla soluzione, e possono essere presenti dei cicli). Ricordiamo che nel caso di ricerca cieca era necessario un ulteriore insieme CLOSED per evitare di esaminare due volte lo stesso stato, e inoltre venivano inseriti in OPEN solo nodi che non vi fossero già presenti.

Nel caso dell'algoritmo a costo uniforme, la cosa diventa più complicata. Infatti se nel corso del procedimento otteniamo un nodo che è già presente nella lista dei nodi aperti, è il segno che tale stato è raggiungibile attraverso percorsi diversi, e quindi dobbiamo lasciare in OPEN, tra le due versioni del nodo in esame, quella cui compete il percorso a costo più basso.

Chiariremo questo concetto con un esempio minimale. Si nodi il grafo degli stati qui a destra. Lo stato S₃ - che è la soluzione del nostro problema - è raggiungibile attraverso due percorsi a costo diverso, 7 e 5. Si faccia attenzione in particolare all'evoluzione dell'insieme OPEN, essendo banale quella dell'insieme CLOSED.

Inizialmente, l'elenco dei nodi aperti contiene il solo nodo iniziale:

OPEN =

Tolto dall'elenco dei nodi aperti, lo mettiamo in CLOSED e inseriamo in OPEN i suoi discendenti:

OPEN =

Esaminiamo dunque S₁. Esso non si trova in CLOSED, non è obbiettivo, e quindi generiamo il suo successore, S₃. Il costo di quest'ultimo, se viene raggiunto a partire da S₁, è 7.

OPEN =

Cosa accade ora? Preleviamo S₂, che non è soluzione. Esso ha per discendente proprio S₃. Poiché lungo tale percorso S₃ dichiara di avere un costo minore, nell'insieme OPEN viene inserita questa nuova versione di S₃ e la precedente viene rimossa, unitamente all'informazione sul percorso che era necessario per raggiungerla (tale rimozione non sarebbe strettamente necessaria ai fini dell'algoritmo, ma la si opera per risparmiare memoria).

OPEN =

Prelevato S₃ da OPEN, troviamo che è la soluzione cercata e che è raggiungibile attraverso il percorso S₀ - S₂ - S₃.

Un inconveniente dell'algoritmo a costo uniforme. Come già precisato, risiede nell'efficienza con la quale esso determina lo stato a costo minimo. Dal momento che tipicamente gli spazi degli stati crescono in maniera esponenziale rispetto al numero dei passi necessari per trovare una soluzione, è auspicabile che l'algoritmo eviti di esplorare zone inutili dello spazio degli stati. Invece nel nostro caso la scelta della direzione da prendere nel processo di esplorazione è basata esclusivamente sul costo necessario per raggiungere gli stati a partire dallo stato iniziale e ciò provoca uno spreco di tempo.

Si noti ad esempio che nell'ultimo caso viene esaminato, al secondo passo, S₁, perché gli compete il costo più basso, ma risulterà poi che il percorso che passa per S₁ per giungere alla soluzione è il meno conveniente dei due. L'esplorazione di S₁ è quindi di fatto inutile e l'algoritmo potrebbe risparmiare tempo evitandola. L'algoritmo dovrebbe poter fare in definitiva una 'potatura' del grafo degli stati, e così facendo potrebbe determinare una soluzione in un tempo molto minore di quello richiesto dall'algoritmo a costo uniforme.

Le tecniche che consentono di velocizzare il processo di ricerca vengono indicate con l'aggettivo euristico. L'algoritmo che esamineremo è dunque detto di ALGORITMO DI RICERCA EURISTICA (in breve, A*).

L'algoritmo causa una perdita di tempo perché manca di 'lungimiranza': quando esamina uno stato, considera il costo necessario per raggiungerlo, ma non il costo del percorso che parte da quello stato. Immaginiamo inizialmente di trovarci in una situazione ideale in cui l'algoritmo conosca non solo il costo g(s) per raggiungere uno stato s, ma anche il costo minimo h(s) necessario per raggiungere, a partire da uno stato, una delle soluzioni (stato che verifica il predicato obbiettivo). Ad esempio, nell'ultimo esempio si ha: g(s₁) = 2 e h(s₁) = 5; oppure, per lo stato 2, g(s₂) = 4 e h(s₂) = 1.

È chiaro quindi che nell'algoritmo a costo uniforme abbiamo basato la nostra ricerca solo sul calcolo della funzione g. Se fossimo in grado di valutare anche la funzione h, potremmo definire una nuova funzione f (detta funzione di valutazione) come somma delle due precedenti:

f(s) = g(s) + h(s)

L'algoritmo di ricerca euristica considererebbe f, anziché g, come funzione di costo. Nel nostro esempio, quando l'algoritmo espande lo stato 0, si trova gli stati 1 e 2; si avrebbe rispettivamente: f(s₁) = 7, f(s₂) = 5. Quindi l'algoritmo sceglierebbe come prossimo nodo di esaminare s₂ e non s₁. Si può dimostrare che un algoritmo del genere si porta 'a colpo sicuro' sul percorso cui compete il costo minore, evitando cioè di esaminare zone inutili del grafo degli stati. Ovviamente il problema sta nel fatto che in generale la funzione h(s) non è calcolabile.

Consideriamo un ulteriore esempio in cui la spazio degli stati è l'albero raffigurato qui a sinistra. Immaginiamo che soluzioni del problema siano tutti e 4 gli stati del terzo livello, ma quella a costo minimo (3) è evidentemente la terza (contrassegnata da un cerchietto più spesso). Nei riquadri abbiamo indicato in rosso i valori delle funzioni g ed h per ogni nodo: ad esempio, per il nodo iniziale g vale 0, ed h vale 3, essendo 3 il minimo costo da sostenere per raggiungere una soluzione (quella ottima). Il costo complessivo associato al nodo iniziale secondo questa nuova filosofia è quindi 3. Le funzioni di costo per tutti gli altri nodi si ricavano abbastanza facilmente. Se supponiamo che sia presente un ulteriore ramo 'morto', che non conduca ad alcuna soluzione (vedi figura pagina successiva), il costo complessivo del nodo terminale sarà per convenzione

L'algoritmo di ricerca euristica esamina dapprima S0; tra i suoi discendenti quello che ha una funzione di valutazione più piccola è quello di destra, che viene dunque esaminato; tra i nodi ancora aperti (funzioni di valutazione: valgono 5, 3, 4 e ) quello che ha la funzione di valutazione più piccola è proprio la nostra soluzione, che viene esaminata e riconosciuta come tale. L'algoritmo termina con successo e senza che si sia mai esaminato un nodo 'inutile' ai fini del percorso che conduce alla soluzione a costo minimo.

Questo algoritmo esegue quindi in maniera automatica una 'potatura' di quella parte dello spazio degli stati che sappiamo essere inutile. Come precisato, si ha il notevole problema che la funzione h è in generale non nota a priori per ogni nodo. Potremmo non sapere quale sia la soluzione, e/o quale sia il percorso più rapido per raggiungerla. L'ipotesi che si conosca quest'ultima informazione è di per sé paradossale, dal momento che ciò renderebbe inutile l'algoritmo di ricerca. (Esistono però alcuni casi particolari nei quali è possibile conoscere a priori il costo del percorso minimo, senza che sia possibile conoscere il percorso stesso).

Tuttavia, in molti contesti si può definire una approssimazione per h(s): una funzione che dia una stima più o meno accurata del costo effettivo per raggiungere la soluzione ottima a partire dallo stato s. Si può dimostrare che sotto opportune condizioni, se al posto della h(s) ideale (che indichiamo come h*(s)) usiamo una sua approssimazione, l'algoritmo porta comunque ad una soluzione ottimale. Lo scotto da pagare è che in questo caso non viene eseguita la potatura 'ottimale' dell'albero, e quindi il tempo necessario per raggiungere la soluzione ottima non è quello minimo possibile.

Perché h(s) (detta funzione euristica) permette di trovare la soluzione ottima, deve essere verificata la condizione di ammissibilità:

s 0 h(s) h*(s)

ossia, per qualunque stato, h dev'essere positiva e minore o uguale alla h(s) ideale (sconosciuta). In altre parole, occorre dimostrare che h(s) è una stima per difetto della h*(s).

In tal caso, l'approssimazione più semplice per h(s) è evidentemente proprio 0; in tal caso, f(s) si riduce proprio alla funzione di costo, e quindi l'algoritmo di ricerca euristica finisce col coincidere con quello a costo uniforme. La soluzione trovata è effettivamente quella ideale, ma non viene fatta nessuna 'potatura' dello spazio degli stati. Quindi, è auspicabile che la h(s) sia per quanto possibile maggiore di 0, la più semplice funzione euristica.

Se abbiamo due possibili approssimazioni di h*(s), cioè h₁(s) e h₂(s), entrambe ammissibili, e si ha inoltre:

s   h₁(s) h₂(s)

in tal caso la migliore (maggiore) potatura dello spazio degli stati è data dalla maggiore delle due funzioni:

h₃(s) = max

e si dice che h₂(s) è una funzione euristica 'più informata'. Quindi, quanto maggiore è h(s) (ma sempre nei limiti dell'ammissibilità), tanto maggiore sarà la potatura che consente di effettuare.

La domanda diviene quindi: come costruire una buona approssimazione della h*(s)? Una tecnica molto utilizzata consiste nel rimuovere alcuni vincoli dei problema.

Tipicamente, in un problema le operazioni effettuabili sono limitate da una serie di vincoli. Se ne rimuoviamo alcuni, possiamo trovare rapidamente la soluzione di un problema 'semplificato' rispetto a quello di partenza. Il costo di tale soluzione può essere considerato come un limite inferiore per il costo della soluzione del problema reale. Il problema semplificato potrà quindi essere utilizzato per definire una euristica che ci guidi verso la soluzione del problema reale.

Illustriamo questo punto con l'esempio dell'8-puzzle. Poniamoci come obbiettivo quello di determinare il minimo numero di mosse necessario per trovare la soluzione (configurazione ordinata delle tessere).

Assegniamo un costo alle varie transizioni: si può per esempio stabilire che ogni mossa abbia costo unitario. Il problema si può risolvere con l'algoritmo di ricerca in ampiezza, ma ciò comporterebbe un costo notevole in termini di tempo, perché ogni nodo può avere fino a 4 discendenti diretti; se sono necessarie k mosse per giungere alla soluzione, l'algoritmo dovrebbe esplorare 2^k stati. È necessaria una 'potatura' dello spazio degli stati, ovvero una funzione euristica. Questa viene definita a sua volta attraverso il rilassamento dei vincoli del problema.

Nel problema di partenza, le tessere possono essere spostate (una alla volta) solo in orizzontale e verticale e solo verso la casella vuota. Supponiamo invece per cominciare che sia possibile muovere le tessere in modo che, se una tessera è fuori posto, sia sufficiente una sola mossa per metterla a posto. Ad esempio, nel caso di sopra la tessera 1 che è fuori posto può essere messa al posto giusto (nell'angolo nord-ovest) con una mossa soltanto. Così facendo abbiamo semplificato il problema, ed è evidente che il numero di mosse necessario per ottenere la soluzione in questo caso è inferiore (o, nella peggiore delle ipotesi, uguale) di quello del problema di partenza.

Dunque una prima funzione euristica è quella associata al numero di passi necessario per mettere a posto tutte le tessere, supponendo che sia possibile muoverle nel senso appena precisato. Questa è sicuramente una stima per difetto del costo necessario per raggiungere una soluzione. Per ottenere il suo valore, di fatto è sufficiente contare, ad ogni stato, il numero di tessere che non si trovano nella posizione corretta. Nell'esempio di sopra la funzione approssimata vale quindi 8 (ed è il caso peggiore, in cui nessuna tessera si trova nella posizione giusta). Se dopo un certo numero di mosse la matrice cambia come illustrato qui a sinistra, h passa ad assumere il valore 6 (abbia due tessere nella posizione corretta).

La funzione euristica così trovata è ammissibile, e consente di potare il grafo degli stati. Se riserviamo ancora del tempo per trovare una euristica migliore, otteniamo una potatura più efficace che consente di determinare la soluzione in un tempo minore.

Si può ad esempio basare l'euristica sulla distanza. La tessera 1 si trova a distanza 1 dalla posizione giusta, la tessera 5 a distanza 2, perché occorrerebbero due mosse (una in orizzontale e una in verticale o viceversa), ovviamente supponendo che gli spostamenti siano resi possibili dalla presenza della casellina vuota, per raggiungere la posizione giusta. Per ciascuna tessera fuori posto consideriamo dunque il numero di passi necessari per raggiungere la posizione giusta supponendo che non ci siano altre tessere ad ostacolare il cammino. Ad esempio, nel nostro caso: per la tessera 2, serve 1 passo; per la 4, almeno 2; per la tessera 5, 2; per le tessere 1, 6 e 3 basta 1 passo per ciascuna. Quindi il valore della h sarà 1 + 2 + 2 + 1 + 1 + 1 = 8. Essendo questo valore maggiore di quello della precedente euristica, la nuova euristica va considerata migliore della vecchia e permette di avere già una ragionevole potatura dello spazio degli stati.

In un problema complesso, può non essere facile confrontare due euristiche per stabilire quale sia la migliore. Ai fini della scelta dell'euristica occorre considerare che al calcolo di ciascuna euristica è associato un certo costo computazionale, e d'altra parte ciascuna euristica assicura un diverso grado di potatura dello spazio degli stati. Una euristica che dia luogo ad una maggiore potatura richiede generalmente anche uno sforzo computazionale maggiore.

Abbiamo esaminato a fondo la tecnica di rappresentazione della conoscenza basata sulla rappresentazione nello spazio degli stati. Tale rappresentazione è di basso livello: nei sistemi esperti reali se ne utilizzano di più evolute. In particolare, è il formalismo ad essere più evoluto.

Per chiarire questo aspetto, occorre distinguere anzitutto i concetti di rappresentazione di un problema e rappresentazione della conoscenza: la differenza è simile a quella che passa tra un algoritmo e il corrispondente programma. Sappiamo che un algoritmo definisce un insieme di passi che trasformano i dati in ingresso; l'algoritmo viene poi tradotto in un programma scritto in un particolare linguaggio. Similmente, abbiamo visto che un problema può essere visto come un insieme di stati, e la sua risoluzione corrisponde ad un insieme di transizioni tra stati differenti. La rappresentazione della conoscenza avviene invece servendosi di un opportuno linguaggio. Così ad esempio le regole che governano il funzionamento dell'8-puzzle possono essere rappresentate utilizzando un formalismo (un linguaggio) piuttosto che un altro.

Elenchiamo una serie di modelli per la rappresentazione della conoscenza contenuta in un SF (sono detti pure paradigmi linguistici): rule-based, frame-based, logic-based, procedure oriented, object oriented, access-oriented.

Storicamente, i primi sistemi sono stati quelli di tipo rule-based: la conoscenza su un certo dominio viene rappresentata attraverso delle regole. Questo è senz'altro il modo più semplice di rappresentare la conoscenza, quindi tali sistemi sono anche i più semplici da realizzare in termini di MI. In tale approccio, che rimane il più utilizzato, si impiegano essenzialmente regole del tipo if.then. Su di esse si applicano poi le tecniche forward o backward chain considerate nelle scorse lezioni.

Spesso, un SF deve formalizzare non solo le relazioni causa-effetto per le quali le regole if.then vanno benissimo, ma anche dei legami di tipo gerarchico. Gli oggetti del SF possono cioè non avere una 'vita' autonoma, indipendente dagli altri: un rettangolo è un particolare tipo di quadrilatero, quindi ogni rettangolo condivide le proprietà dei quadrilateri, e in più possiede delle proprietà peculiari. Un'equazione di secondo grado rappresenta un caso particolare di una di terzo (con coefficiente di grado massimo = 0), e via dicendo. L'ereditarietà delle proprietà è il concetto basilare del famoso modello object-oriented, che è nato originariamente proprio nel contesto dell'AI (in particolare nella forma del linguaggio SMALLTALK, risalente agli anni 1970) e che oggi trova invece applicazione molto maggiore nella programmazione dei calcolatori. Il motivo fondamentale del successo di questo approccio nell'ambito della programmazione è che favorisce il concetto ingegneristico di riuso del software. Esso è orientato a mettere a fattor comune il numero maggiore possibile di componenti di un software per ragioni di economia e chiarezza. Il progetto viene diviso in classi; ogni classe prevede delle procedure che servono per eseguire operazioni sugli esemplari di quelle classi, e le classi sono 'imparentate' in modo da condividere determinate proprietà; tutto ciò, oltre a costituire una metodologia di progettazione pulita e razionale, riduce l'esigenza di scrivere righe di codice.

Già i più vecchi metodi frame-based di rappresentazione introducevano una conoscenza tassonomica: il principio base è che tutte le entità del SF possono essere rappresentate in una forma gerarchica, e il ricorso ad un gerarchia ne semplifica la rappresentazione. I frame, apparsi all'inizio degli anni '80, consentivano, all'interno di un SF nel quale fossero previste delle regole del tipo ifthen, l'introduzione di ulteriori parole chiave finalizzate a definire una gerarchia. Un esempio di rappresentazione di questo tipo è illustrato nella pagina seguente. Il 'rapporto' è formato da un certo numero di componenti; avremo almeno due tipologie di rapporti differenti, rapporto 'in corso' e 'tecnico', che però condividono le proprietà comuni a tutti i rapporti. Tutti gli oggetti di tipo rapporto in corso o rapporto tecnico possono essere trattati con una rappresentazione di tipo if..then; ma se vogliamo evitare di ripetere due volte le regole comuni a entrambi, converrà definire l'ulteriore entità di tipo 'rapporto', più generale delle due, che racchiude le regole o proprietà valide (supponiamo siano 75) per tutti i rapporti. Ogni 'rapporto in corso' avrà tutte le regole dell'entità rapporto più un certo numero di regole peculiari (supponiamo 7), e lo stesso dicasi di ogni 'rapporto tecnico' (8 regole proprie). Se non potessimo avvalerci di questa rappresentazione, dovremmo introdurre 75+7 regole nel primo caso, e 75+8 nel secondo, con uno spreco evidente.

In questo corso comunque non ci soffermeremo sui sistemi frame-based.

I sistemi logic-based sono fortemente assimilabili ai rule-based; essi adottano un formalismo preso a prestito dalla logica matematica, che può essere visto come un'estensione del formalismo dei sistemi rule-based. Il PROLOG è il rappresentante più noto di questa famiglia di linguaggi. Nei programmi logici, la rappresentazione della conoscenza è poco più sofisticata di quella dei rule-based; è basata su clausole (espresse mediante i connettivi logici and - or - not) delle quali è possibile dimostrare la verità o la falsità.

Le tecniche procedure- e access-oriented non vanno considerate autonome dal punto di vista AI: sono sostanzialmente estensioni dei metodi basati sulle regole o sulla logica. Possono essere usate quando all'interno di un determinato problema intervengono sottoproblemi per i quali esiste una conoscenza algoritmica (ad esempio: è richiesto di risolvere un'equazione di secondo grado), per cui non è necessario ricorrere ad una rappresentazione tipo quella per suddivisione a sottoproblemi che sarebbe anzi controproducente. Nel nostro SF introdurremo quindi delle tecniche tradizionali di programmazione che in questo contesto sono dette procedure-oriented. Non dimentichiamo che in questo corso consideriamo dei metodi di risoluzione di problemi per i quali non è disponibile (o non è utilizzabile) una conoscenza algoritmica; infatti, qualora lo fosse, il ricorso a tali metodi risulterebbe inefficiente e privo di senso.

Esaminiamo ora più da vicino la tecnica più usata di rappresentazione della conoscenza: la rule-based. Il SF viene espresso come insieme di regole, dove ogni regola possiede un modello ben preciso:

if (premessa) then (conclusione)

La conclusione è vera laddove lo sia anche la premessa. Le due parti sono dette anche testa e coda, o precondizione e postcondizione. Come sappiamo in un sistema di questo genere il MI esamina il database dinamico per determinare quali siano le regole attivate (ossia quelle le cui precondizioni siano verificate dagli elementi del database) e applica ciascuna di esse, aggiungendo la relativa conclusione al database. In alternativa (ricerca all'indietro), possiamo mettere nel database il goal; il MI cercherà in esso tutte le regole attivate quando sono vere le postcondizioni e metterà nel database le rispettive precondizioni.

Lo schema che segue si propone di rendere più in dettaglio il comportamento del MI. La base di conoscenza (sulla destra) è costituita di fatti e regole; abbiamo poi la memoria di lavoro (blackboard) o dinamica; un blocco di interpretazione delle regole ed uno di selezione delle regole e dei dati; e infine un blocco che costituisce l'unica vera novità di tale schema, quello delle metaregole.

Il blocco di selezione regole e dati, che percorre per intero la base di conoscenza, realizza l'unificazione. Nota in un dato istante la memoria di lavoro e selezionato uno dei teoremi, determina quali regole siano ad esso applicabili. La regola selezionata va applicata; l'applicazione comporta una interpretazione della regola, successivamente aggiorniamo la memoria. L'insieme dei due blocchi circolari costituisce quindi il nostro MI.

Il blocco delle metaregole include le "regole per la gestione delle strategie di selezione delle regole"; si tratta cioè di regole più generali, le quali forniscono una conoscenza aggiuntiva al MI orientata a meglio dirigere le sue scelte. Consideriamo ad esempio l'integrazione simbolica, di cui conosciamo i metodi per parti, per sostituzione e per ricorrenza. Quando viene assegnato un esercizio di integrazione da svolgere a mano, il solutore fa di solito un esame preliminare dell'integrale per vedere quali di tali metodi convenga applicare per primo. La 'metaregola' che implicitamente utilizza lo induce quindi a cercare di applicare una certa tecnica prima di un'altra: non è nient'altro che una strategia di applicazione delle regole vere e proprie.

Per fare un esempio ancora più semplice, si consideri un sistema per l'analisi dei guasti di un'autovettura. Si è riscontrato un problema ai freni e si vuole stabilirne la causa. È comprensibile che, per esempio, i guasti dell'impianto elettrico non potrebbero mai condizionare il corretto funzionamento dell'impianto frenante; quindi se durante il processo inferenziale possono essere applicate 150 regole per rilevare guasti sul sistema elettrico, è inutile applicarle perché il tipo di guasto per la sua natura non è sicuramente ascrivibile all'impianto elettrico e si passerà ad applicare un altro, più adatto set di regole. Il nostro sistema porrà quindi innanzitutto delle domande generali per scoprire la natura del guasto, il che gli permetterà di escludere l'applicazione di certe regole.

Nel caso di un SF, supposto ad esempio che in ogni istante esistano 500 regole applicabili ai teoremi, possiamo immaginare che esse siano suddivise in più gruppi di regole, p.e. 2: il gruppo A e il gruppo B; il sistema non cerca di applicarle tutte, ma le metaregole gli suggeriscono di provare innanzitutto con A perché l'utilizzo di B non porta a risultati utili. Una metaregola dunque inibisce un gruppo di regole a favore di un altro.

SHELL DI UN SISTEMA ESPERTO. È un ambiente integrato, all'interno del quale, oltre agli strumenti che consentono di rappresentare la conoscenza che sarà usata dal MI, troviamo disponibili dei 'tool' aggiuntivi finalizzati a rendere vantaggioso l'uso del sistema esperto. Particolarmente utili sono i tool che tengono traccia del processo di inferenza. Mentre la macchina effettua l'inferenza e pone quindi delle domande, i tool delle spiegazioni (che spesso usano il linguaggio naturale) consentono all'utente di sapere il motivo per cui in un dato momento è posta una data domanda. La macchina cioè in maniera automatica presenta traccia, istante per istante, del meccanismo inferenziale ("siamo partiti dall'assioma X, abbiamo dimostrato le verità intermedie A, B e C e intendiamo ora provare il teorema D.").

INTRODUZIONE AL PROLOG. Il suo formalismo è quello tipico basato sulla logica. Per adesso, comunque, ci limiteremo a dare qualche cenno di carattere sintattico o poco più. Supponiamo di lavorare con un SF che descrive l'albero genealogico di una famiglia. Il segno di percentuale indica un commento:

% padre (X,Y) se X è padre di Y

Ciò che precede la coppia di parentesi tonde è il predicato di nome 'padre'. Il predicato mette in relazione il primo oggetto, X, con il secondo, Y. Quindi con la scrittura:

padre (mario, bruno).

stiamo a indicare che mario è il padre di bruno. Questo è un assioma del nostro SF. Esso è composto dal nome del predicato, con l'indicazione degli oggetti (costanti) su cui agisce, ed è chiuso da un punto.

Il SF è composto di predicati; ogni predicato è individuato dal proprio nome, ad ogni nome è associato un predicato. Ogni volta che un predicato occorre nella KB, intendiamo associare quella espressione formale ad un 'fatto' che è vero nel mondo reale:

padre (mario, manuela).

padre (mario, giulia).

se vogliamo un SF che sia capace di "ragionare", non basterà definire la relazione di padre, ma occorrerà aggiungere altra conoscenza, ad esempio distinguere il sesso degli oggetti del SF e introdurre il grado di parentela di tipo coniuge:

% maschio (X) se X è maschio

% femmina (X) se X è femmina

% coniuge (X,Y) se X è marito di Y

femmina (manuela).

femmina (giulia).

maschio (mario).

coniuge (mario, sandra).

coniuge (bruno senior, angela).

Con lettere maiuscole quali X, Y e Z si indicano in PROLOG delle variabili, mentre con le lettere minuscole dei valori costanti. L'interpretazione del SF viene tipicamente data all'inizio del programma specificando con dei commenti il significato di ciascuna relazione. È consigliabile che i nomi siano scelti in modo da risultare sufficientemente descrittivi, come nel nostro esempio.

Supponendo che la base di conoscenza sia coerente e completa, una volta forniti gli elementi necessari possiamo introdurre delle regole. Segue un esempio di regola:

genitore (X,Y) :-

padre (X, Y).

Se X è padre di Y, X è anche genitore di Y. L'indentazione della precondizione non è obbligatoria ma è buona norma utilizzarla.

Le regole hanno sempre una sola postcondizione, ma possono avere una o più precondizioni (se le precondizioni sono più di una, si intendono legate in AND). La postcondizione deve sempre essere specificata per prima. La regola:

madre (X, Y) :-

coniuge (Z, X), padre (Z, Y).

ci dice che, se Z è coniuge di X e Z è padre di Y, allora X è madre di Y. Ciò comporta che, poiché nella KB abbiamo espresso tutti gli oggetti 'figlio' rapportandoli al padre, possiamo dedurre, una volta noto il padre, chi sia la madre.

Nel Prolog esistono fondamentalmente due unità sintattiche: i fatti e le regole.

Cominciamo dai FATTI. Il Prolog permette di esprimere delle relazioni n-arie in forma di predicati:

collegamento (napoli, roma).

collegamento è il nome del predicato; napoli e roma sono gli oggetti del predicato, separati da virgole. Quale significato attribuiamo a questa scrittura? Nel momento in cui inseriamo nella KB l'espressione summenzionata, stabiliamo un isomorfismo tra l'espressione ed il concetto del mondo reale che intendiamo rappresentare. Prima di introdurre quel tipo di espressione all'interno del SF, ci si presenta dunque il problema di selezionare un nome per il predicato e attribuirgli un significato, e lo stesso dicasi per gli oggetti.

Consideriamo un primo programma logico, in cui intendiamo rappresentare i collegamenti che esistono fra 4 città, in accordo con il semplice tracciato illustrato qui a destra. Rappresentiamo questa mappa attraverso un SF. Dobbiamo quindi trovare un formalismo per esprimere i concetti in gioco. Una mappa geografica può essere rappresentata come un insieme di relazioni binarie; ogni relazione rappresenta il collegamento tra due città: tra Roma e Napoli esiste un collegamento, tra Napoli e Reggio Calabria pure, ecc. Ciò significa rappresentare la conoscenza attraverso un insieme di elementi di conoscenza più semplici. Dopodiché troveremo un modo per rappresentare nel SF il concetto di collegamento. Ciò avviene ipotizzando una modalità di organizzazione formale basata sulla logica dei predicati del primo ordine.

Un predicato del genere è rappresentato attraverso una relazione n-aria. Il predicato 'collegamento' indica una relazione tra due oggetti prefissati x e y. L'isomorfismo dice in effetti: 'se all'interno della KB usiamo una scrittura di questo genere (istanza di relazione binaria), vogliamo indicare il concetto per cui, all'interno del nostro mondo reale, tra la città x e la y esiste un collegamento'.

La rappresentazione della conoscenza è praticamente la stessa del modello relazionale considerato nei corsi di basi di dati: la KB è un insieme di rappresentazioni, in cui il predicato collegamento è il nome della tabella o relazione e x e y sono i nomi degli attributi che vi partecipano.

La mappa geografica che abbiamo disegnato poco sopra viene rappresentata mediante 4 ennuple, ognuna delle quali rappresenta un collegamento atomico tra le città. Quindi i 4 'fatti' del mondo reale (assiomi del SF) sono rappresentati in Prolog come segue:

coll (na, roma).

coll (na, rc).

coll (roma, ba).

coll (ba, rc).

Il predicato coll (na, roma) sottintende che tra Napoli e Roma esiste un collegamento diretto (cioè che va da Napoli e Roma). I 4 predicati indicati poco sopra costituiscono in pratica la rappresentazione in termini del SF di un grafo orientato come quello riportato qui a sinistra.

Notiamo tuttavia che la mappa geografica disegnata nella pagina precedente non era orientata; dev'essere il segno che nel nostro mondo reale intendiamo considerare non uno solo ma entrambi i collegamenti che coinvolgono due città. Qualora volessimo esprimere collegamenti bidirezionali in un grafo orientato, dovremmo aggiungere in maniera esplicita i 4 collegamenti contrari (coll (roma, na) ecc.). per un totale di 8 predicati.

All'interno di un predicato riconosciamo delle costanti, che in Prolog vanno obbligatoriamente rappresentate mediante stringhe alfanumeriche con l'iniziale minuscola.

Si noti che il SF in questa forma semplice prevede 4 assiomi e nessuna regola. Immaginando di poter lavorare per il momento soltanto con questa KB, quali problemi possiamo risolvere? Dopo il passo di formalizzazione, il MI si mette in attesa che l'utente formuli una domanda. Dal momento che il SF conosce un unico predicato che vuole esprimere il concetto di collegamento ed un ristretto numero di oggetti (città) in esso coinvolti, è evidente che l'unica cosa che possiamo chiedere al sistema è se esistono collegamenti tra due città. Questo può essere fatto in Prolog mediante una scrittura del tipo che segue, ovvero usando lo stesso formalismo dei predicati:

? coll (na, rc).

Esiste un collegamento tra Napoli e Roma? Il MI esegue l'algoritmo che ci è noto: cerca di capire se è possibile derivare il predicato proposto a partire dagli assiomi, o dai teoremi che ne scaturiscono (ma nel nostro caso abbiamo solo assiomi). Esso comincia a scorrere la KB, dal primo all'ultimo fatto presente, nell'intento di unificare gli assiomi con la query indicata dall'utente. Una volta trovata nella KB una istanza di predicato (la prima è coll (na, roma)), il MI confronta ordinatamente il primo oggetto della query con il primo dell'istanza, e il confronto ha successo. Non si può dire lo stesso del secondo confronto (roma rc) e quindi in questo caso il sistema non riesce a trovare una soluzione.

Il MI scarta questa prima possibilità e passa ad esaminare il secondo assioma. Entrambe le unificazioni hanno successo, e di conseguenza il MI scopre che la query è unificabile che uno dei fatti presenti nella KB. Il MI risponde affermativamente all'utente: esiste un collegamento tra Napoli e Reggio Calabria.

Yes.

Osserviamo ora che, nel caso in cui il SF consista solo dei 4 predicati indicati in fondo alla pagina precedente, la query seguente avrebbe effetto negativo, giacché l'unificazione non è mai possibile:

? coll (rc, na).

No.

A questo punto ci chiediamo: il SF (con la sua interpretazione alla luce dell'isomorfimo) come si pone nei riguardi dei requisiti di coerenza e completezza? Se il SF vuole rappresentare collegamento diretti (da x è possibile andare a y), allora esso con la sua interpretazione è coerente e completo. Infatti, in base alla conoscenza insita nella mappa orientata proposta all'inizio, esiste un collegamento tra Napoli e Reggio, ma non esiste un collegamento opposto, e lo stesso dicasi per tutti gli altri collegamenti. Quindi il SF fornisce delle risposte che sono corrette alla luce dell'interpretazione. Esso è anche completo, nella misura in cui stiamo considerando solo un modesto sottoinsieme della mappa geografica italiana. Infatti tutto ciò che tale sottoinsieme vuole esprimere è esprimibile attraverso il nostro SF.

Rispetto ad una interpretazione più articolata, il SF risulterebbe sempre coerente (rimane attendibile sulle risposte affermative), ma palesemente incompleto. Se con la scrittura coll (x,y) l'utente sottintende il concetto per cui esiste un collegamento bidirezionale, ovvero non solo tra x e y ma anche tra y ed x, egli si aspetta che il MI risponda di sì alla domanda coll (rc, na), cosa che come abbiamo visto non avviene.

Per rendere il sistema completo nella nuova interpretazione si potrebbero aggiungere i 4 predicati che esprimono i collegamenti nella direzione opposta, ma evidentemente quella di costringere l'utente ad inserire per ogni collegamento anche il collegamento opposto non è la strada migliore. Un'alternativa è quella di introdurre una opportuna regola di inferenza, ossia esprimere un concetto simile a quello riportato di seguito (n.b. non è Prolog):

coll (y,x) T coll (x,y)

la scrittura Prolog corrispondente è:

coll (X,Y) :-

coll (Y,X).

Il secondo predicato (coll (y,x)) è detta precondizione, il primo (coll (x,y)) è detta postcondizione (si noti che in Prolog la postcondizione viene espressa per prima). Con la scrittura precedente dichiariamo quindi al SF il fatto che, se esiste un collegamento tra y ed x, ne esiste uno anche tra x ed y. Pertanto è sufficiente aggiungere al SF questa regola per esprimere tutti i collegamenti mancanti.

x ed y sono delle variabili, ovvero possono assumere valori qualsiasi. In Prolog le variabili sono rappresentate da stringhe che iniziano con una maiuscola: X, Y.

La regola di inferenza appena scritta solleva una interessante questione: quella della quantificazione delle variabili. Se digitiamo:

coll (na, X).

che intendiamo dire esattamente?

che Napoli è collegata a tutte le città ( x.); oppure:

che esiste almeno una città a cui Napoli è collegata ( x.) ?

ci chiediamo cioè se in Prolog la quantificazione è universale o esistenziale. La risposta - importantissima - dipende dal contesto in cui le variabili sono utilizzate. La quantificazione non deve essere specificata dal programmatore perché in ogni contesto è previsto un unico tipo di quantificazione.

Nei fatti, la quantificazione è sempre universale. Quindi il 'fatto' precedente indica che Napoli è collegata a tutte le città. Si noti che un fatto è in definitiva una regola con la precondizione sempre verificata, quindi l'ultima espressione equivale a:

coll (na, X) :-

true

Questo ci permette di affermare che, nelle regole, le variabili che compaiono solo nella postcondizione sono quantificate universalmente. Che dire della precondizione? È ragionevole concludere - ed è proprio ciò che accade - che le variabili che compaiono nella precondizione delle regole sono quantificate esistenzialmente. Si consideri l'esempio che segue:

genitore (X,Y) :-

padre (X,Y).

Se X è padre di Y, X è anche genitore di X. Nella precondizione vogliamo chiaramente esprimere il concetto: 'se esiste un X ed esiste un Y tale che X è padre di Y.' giacchè non avrebbe senso interpretare tale predicato come 'se ogni X è padre di ogni Y.' e nemmeno come 'se esiste un X che è padre di tutti gli altri.'.

La postcondizione afferma che, per conseguenza, 'quello specifico X è anche genitore di quello specifico Y'. Quindi: le variabili che compaiono sia nella precondizione che nella postcondizione sono quantificate esistenzialmente.

Altro esempio: aggiungiamo un ulteriore nome di predicato, coll1, che esprime un concetto di 'collegamento con costo':

coll1 (X, Y, C) :-

coll (X, Y)

la postcondizione afferma che se esistono un X e un Y tali che Y è collegato a X, allora esiste un collegamento tra X ed Y per ogni C: C è quantificato universalmente, perché compare solo nella conclusione.

Logica predicativa del primo ordine. Si ha quando i predicati, in qualunque espressione formale, non possono mai apparire come oggetti di altri predicati. In Prolog non è ammesso scrivere ad esempio:

coll1 (coll(.

Non è una limitazione da poco. Si consideri l'esempio della derivazione. L'espressione: d[f(x)] = f'(x) potrebbe essere scritta in Prolog come:

d (f, f')

ad esempio:

d (sin x, cos x)

Ora, in una logica predicativa del I ordine, qual è quella usata dal Prolog, non sarebbe possibile esprimere la derivazione composta nel modo che appare più naturale:

d (sin(cos x),d(cos(cos x))*(-sin x))

perché staremmo cercando di usare un predicato all'interno di un altro predicato (sottolineatura).

I connettivi logici in Prolog. Consideriamo l'espressione:

p1, p2, p3 :-

p5, p6, p7.

Se è vero p5, e lo è p6, e lo è p7, allora sono veri, contemporaneamente, p1, p2 e p3. Si potrebbe usare cioè il connettivo AND sia nella precondizione che nella postcondizione. Oppure si potrebbe usare il connettivo OR:

p1 or p2 or p3 :-

p5 or p6 or p7.

o, ancora, mescolare secondo il bisogno i due connettivi:

p1, (p2 or p3) :-

p5 or p6, p7

Tutte queste espressioni non sono ammesse in Prolog. Il linguaggio Prolog usa le cosiddette clausole di Horn, in cui esiste una unica postcondizione, e nella precondizione l'unico connettivo previsto è l'AND. L'espressione che segue è ammissibile:

p1 :-

p5, p6, p7.

È da sottolineare comunque che tale limitazione del formalismo non preclude la possibilità di esprimere il concetto di OR inclusivo, sia pure al costo di dover scrivere più linee di codice: ad esempio la seguente scrittura non è ammessa in Prolog:

genitore (X,Y) :-

padre (X, Y)

or

madre (X, Y).

ma il suo significato è perfettamente uguale a quello delle due regole :

genitore (X,Y) :-

padre(X,Y).

genitore (X,Y) :-

madre (X,Y).

Anche l'impossibilità di utilizzare predicati come oggetti di altri predicati può essere facilmente aggirata, come vedremo. Risulta comunque che la tecnica di descrizione della conoscenza offerta dal Prolog è soggetta a molti vincoli: le clausole possono essere solo del I ordine; la quantificazione non può essere specificata dall'utente ma è prefissata a seconda del contesto; ogni regola ci può essere una sola conclusione e le premesse possono essere legate solo in congiunzione. I motivi di tutte queste limitazioni sono facilmente comprensibili: il MI è semplice da progettare e realizzare, e in aggiunta il suo funzionamento risulterà verosimilmente più efficiente.

Per concludere, consideriamo nuovamente l'esempio considerato all'inizio di questa lezione: all'insieme dei 4 assiomi:

coll (na, roma).

coll (na, rc).

coll (roma, ba).

coll (ba, rc).

aggiungiamo la regola che formalizza in maniera sintetica i collegamenti inversi fra le 4 città:

coll (X, Y) :-

coll (Y, X).

Il SF così ottenuto, rispetto al problema di rappresentare una mappa di collegamenti bidirezionali fra 4 città, risulta coerente e completo.

Supponiamo ora di sottoporre al sistema la seguente query:

?- coll (roma, na).

Il MI tenta invano di unificare con i 4 assiomi, e passa quindi a utilizzare la regola. Essendo il PROLOG goal-driven, il predicato coll (roma, na) dev'essere la conclusione di una regola. Il MI tenta quindi di unificare il predicato con la postcondizione della regola. (Si noti che ciò valeva anche nel processo di unificazione con i 4 assiomi, poiché quei 4 fatti sono in effetti postcondizioni di regole con la precondizione sempre vera).

Quindi il predicato che compare nella query unifica con la postcondizione della regola:

coll (X, Y) :-

coll (Y, X).

ovvero unifica con X = roma e Y = na; l'obbiettivo è rendere vera la precondizione: coll (na, roma); diventa perciò goal corrente il predicato coll (na, roma).

Il MI cerca di verificare tale predicato, e trova immediatamente l'unificazione. Essendo stata dimostrata la precondizione, la postcondizione è pure vera ed il sistema risponde affermativamente.

Yes.

Rispondiamo ora ad una domanda che abbiamo intenzionalmente trascurato: abbiamo parlato dell'uso variabili nei fatti e nelle regole, ma come vengono quantificate le variabili nelle query? Risposta: nelle query, la quantificazione è esistenziale. Immaginiamo p.e. di sottoporre al sistema la query:

?- coll (na, X).

Il sistema risponde di sì, dal momento che esiste sicuramente almeno un collegamento fra Napoli ed un'altra città, ed in più fornisce l'elenco di tutti i possibili valori di X che rendono vero il predicato. Saranno quindi trovate almeno 4 soluzioni: (na, roma), (roma, na), (na, rc) e (rc, na). Diciamo 'almeno' perché, in realtà, le risposte che il sistema trova sono infinite e nella prossima lezione cercheremo di capirne il motivo.

Che succede invece se poniamo la query seguente?

?- coll (fi, ge).

In questo caso il sistema non riesce a trovare la soluzione e va in loop; il problema è cioè non decidibile. Infatti il MI, dopo aver tentato inutilmente l'unificazione con i 4 assiomi applica la regole, concludendo che esiste un collegamento fra Firenze e Genova se ne esiste uno fra Genova e Firenze. Comincia quindi a verificare l'esistenza di quest'ultimo collegamento, e, non riscontrandolo fra gli assiomi, cerca di applicare la regola; ciò lo porta a ragionare che esiste un collegamento fra Genova e Firenze se ne esiste uno fra Firenze e Genova, e così via all'infinito.

Ne scaturisce che la formalizzazione fin qui considerata:

coll (na, roma).

coll (na, rc).

coll (roma, ba).

coll (ba, rc).

coll (X, Y) :-

coll (Y, X).

è errata; nella prossima lezione considereremo il modo corretto di esprimerla.

Cominceremo con oggi a elaborare piccoli SF con un interprete Prolog. La KB (fatti e regole) viene collocata all'interno di un documento di testo (basterà quindi aprire il blocco note di Windows e digitare le righe presentate di seguito). Una primitiva dell'interprete Prolog che useremo consente di prelevare la KB sotto forma di file esterno (che dev'essere stato salvato con estensione pl) ed incorporarla nel database dinamico per permettere al MI di effettuare le consultazioni.

Consideriamo l'esempio della mappa geografica. Introduciamo un predicato con 3 oggetti, volendo includere anche un concetto di costo del collegamento. Mediante un commento iniziale rendiamo evidente all'utilizzatore del SF il significato dell'isomorfismo. È buona norma inserire un commento esplicativo per ogni differente predicato. La nostra KB includerà 5 fatti ed una regola.

% coll(x, y, c) se la città x è collegata a y con costo c

coll(na, rm, 220).[2]

coll(rm, fi, 200).

coll(fi, bo, 100).

coll(na, sa, 60).

coll(sa, rm, 280).

coll(X, Y, C) :-

coll(Y, X, C).

Si ricordi che coll (X, Y, C) è la postcondizione della regola e viene messa per prima perché il Prolog è goal-driven (tenta sempre di unificare con la postcondizione di una regola).

Registrato il file cammino.pl (ad esempio nella directory C:prolfiles) e avviato l'interprete SWI-Prolog, al prompt ?- basterà inserire il comando seguente per incorporare la KB:

?- ['C:prolfilescammino.pl'].

La KB viene trasferita nella memoria interna del motore inferenziale. Poiché il MI deve fare ricerche piuttosto intensive sulla KB, esso modifica il nome dei predicati e degli oggetti per rendere quanto più possibile efficienti le proprie ricerche. Questa operazione viene detta di 'compilazione' (non si tratta di una compilazione nel senso classico del termine, perché il Prolog è un linguaggio interpretato).

Una volta che il listato sia stato 'compilato', l'interprete risponde affermativamente per segnalare il successo dell'operazione.

Yes.

A questo punto, l'interprete contiene la KB e quindi possiamo già inoltrare delle domande. Ad esempio, Napoli è collegata con Salerno?

?- coll(na, sa, X).

Esiste cioè almeno un valore per il costo C per il quale è possibile trovare un collegamento tra Napoli e Salerno? Essendo possibile l'unificazione con i primi due oggetti omologhi che sono costanti uguali, e poiché l'unificazione tra costanti e variabili ha sempre successo (terzo oggetto), il MI fornisce una prima risposta affermativa, specificando il costo X del collegamento diretto.

X = 60;

se diamo Invio, il MI si ferma alla prima soluzione trovata; dando invece un punto e virgola come indicato, ritroviamo la stessa soluzione:

X = 60;

Il procedimento che porta a questa seconda soluzione uguale alla precedente è più lungo e va compreso nei dettagli. Il MI, proseguendo nella KB, trova l'unica regola presente e tenta di applicarla. Di conseguenza, la X della postcondizione unifica con na, la Y con sa e la C con la X della query. (È da sottolineare che la X che compare in questa regola non ha nulla a che vedere con la X fornita come parte della query. Si ricordi che in Prolog ogni variabile nasce e muore nel contesto della regola in cui è definita; non esiste un concetto di variabile globale).

Per rendere vera la postcondizione, il Prolog genera come goal corrente la precondizione; il nuovo goal è cioè coll(sa, na,C), e poiché tale predicato non trova unificazione nei fatti, viene applicata nuovamente la regola. La regola induce il tentativo di rendere vero il predicato coll(na, sa,C), cosa che risulta possibile, da cui la risposta.

Si sarà capito che il motore inferenziale non si arresta mai, perché dopo la seconda soluzione, a seguito dell'applicazione reiterata della regola che compare alla fine della KB, ne vengono trovate infinite altre (tutte uguali). L'interprete comunque dà la possibilità di premere Invio invece del punto e virgola per arrestare il processo di ricerca delle soluzioni:

X = 60 [Invio]

Yes.

L'infinitezza del processo di ricerca risulta evidente anche considerando query che danno luogo a delle indecidibilità. Proviamo a inserire una query per sapere se esiste una città che è collegata contemporaneamente a Napoli e Roma: la risposta dovrebbe essere affermativa (Salerno). All'interno delle query, è permesso formulare un goal utilizzando la congiunzione logica (AND). Si osservi dunque la query che segue: tutte le 3 variabili che vi compaiono sono quantificate esistenzialmente, e la X che compare nel primo predicato è esattamente la stessa che compare nel secondo.

?- coll(X,na,C1),coll(X,rm,C2).

Ci attende un'amara sorpresa: il MI non solo non fornisce alcuna risposta ma addirittura si blocca! Tale fenomeno del resto si presenta anche con una query molto più semplice: riprendiamo il controllo del sistema con CTRL-C è inseriamo:

?- coll(na,ba,C).

ovvero una query la cui risposta dovrebbe essere negativa, a rigor di logica. Il sistema invece non fornisce alcuna risposta, entrando in loop; il problema è cioè indecidibile. Nel primo esempio, ciò è attribuibile al fatto che, pur esistendo una soluzione, il MI dev'essere incappato in un ramo di profondità infinita; nel secondo all'infinitezza dello spazio degli stati generato dalla KB, così come descritta, si aggiunge il fatto che non esiste alcuna soluzione. In particolare: tra i fatti non si riscontra alcuna soluzione; si unifica con la postcondizione della regola, e viene generato il goal coll(ba,na,C); non viene trovato tra i fatti, si riapplica la regola generando il goal coll(na,ba,C) come all'inizio, e così via all'infinito.

La generazione di infiniti stati è a sua volta dovuta all'applicazione ricorsiva dell'unica regola presente. La regola richiama infinite volte sé stessa, invertendo ad ogni applicazione il ruolo dei due argomenti. L'indecidibilità può essere eliminata modificando il listato in modo che non vi figuri una regola che richiama sé stessa, per esempio:

coll1(na, rm, 220).

coll1(rm, fi, 200).

coll1(fi, bo, 100).

coll1(na, sa, 60).

coll1(sa, rm, 280).

coll(X, Y, C) :-

coll1(X, Y, C).

coll(X, Y, C) :-

coll1(Y, X, C).

Modifichiamo cioè in coll1 il nome del predicato principale, ed aggiungiamo una regola in base a cui esiste un collegamento coll tra X, Y con costo C se esiste un collegamento coll1 tra le stesse città e ne esiste uno anche in direzione opposta. In questo modo abbiamo eliminato il fenomeno di applicazione ricorsiva di una regola che si verificava nel caso precedente; la prima regola verifica se esiste un collegamento tra X ed Y e di conseguenza esamina i cinque fatti una volta sola ciascuno; la seconda verifica se esiste un collegamento tra Y ed X e fa lo stesso; dopodiché il MI termina il proprio lavoro.

A questo punto, consultando la nuova KB (comando ['C:prolfilescammino.pl'].) l'interprete Prolog si comporta in maniera razionale:

?- coll(na,ba,C).

No

Diamo ora i due comandi che seguono:

?- leash(full)

No

trace.

Yes

Questi due comandi attivano una modalità grazie alla quale vengono visualizzati tutti i passi attraverso i quali procede il MI.

Ripetendo la query:

?- coll(na,ba,C).

inizia il processo di ricerca; innanzitutto viene visualizzato il goal corrente:

Call: ( 6) coll(na, ba, G672) ?

Il modello adoperato è detto 'a porte'; ogni goal da verificare può essere immaginato come una 'scatola' alla quale si può accedere in due modalità differenti, e dalla quale si può uscire in due modalità differenti. Una delle due modalità di accesso è call: è quella grazie alla quale il goal coll(na, ba, G672) viene invocato. Si noti che la variabile C è stata ribattezzata dal Prolog con un nome inusuale, la sigla G672. È stata cioè effettuata la 'compilazione' cui si accennava prima, per impedire che la variabile C possa entrare in conflitto con altre variabili presenti all'interno del nostro SF. Il numero 6 va interpretato come un livello di profondità: il primo goal si trova a livello 6.

Quando un goal entra in fase di call, il MI percorre tutta la KB per tentare di renderlo vero, ovvero per unificare coll con le costanti na, ba e la variabile G672. Per tutti e 5 i fatti si ha un insuccesso, dal momento che il predicato utilizzato per gli assiomi è coll1 e non coll: l'unificazione è impossibile.

Di conseguenza, coll unifica con la prima regola, con la sostituzione X = na, Y = ba e C = G672. Tale unificazione ha successo, e la regola viene applicata. Ciò fa diventare nuovo obbiettivo la precondizione della regola: coll1(na,ba,G672). Il sistema quindi genera un nuovo goal in modalità di call: dando Invio si ha (riga in grassetto):

Call: ( 6) coll(na, ba, G672) ? [Invio] creep (n.b.: creep sta per 'vai avanti')

Call: ( 7) coll1(na, ba, G672) ?

Questo diventa il nuovo goal corrente. Dando Invio, risulta che tale goal viene terminato (si esce dal tentativo di verificarlo) nella modalità fail:

Call: ( 7) coll1(na, ba, G672) ? [Invio] creep

Fail: (   7) coll1(na, ba, G672) ?

Abbiamo così visto due delle modalità: una modalità di ingresso, Call, e una di uscita con esito negativo, Fail. Dando Invio, si verifica il fenomeno del backtraking: ritorno all'indietro. Inizialmente avevamo sottoposto al sistema il goal 6 (coll(na,ba,C)), il che aveva determinato l'unificazione con la prima regola, con generazione (senza successo) di un nuovo goal, coll1(na,ba,C). Di conseguenza il sistema rientra nel goal 6 con la seconda modalità di accesso, redo. Redo è la modalità in cui si prova il goal per ogni accesso successivo alla primo.

Fail: ( 7) coll1(na, ba, G672) ? [Invio] creep

Redo ( 6) coll(na,ba,G672) ?

Il goal viene quindi riproposto, e unificato, questa volta, con la seconda regola. Premendo Invio in successione lo schermo mostra quanto segue:

Redo ( 6) coll(na,ba,G672) ? [Invio] creep

Call: ( 7) coll1(ba, na, G672) ? [Invio] creep

Fail: ( 7) coll1(ba, na, G672) ? [Invio] creep

Redo ( 6) coll(na,ba,G672) ? [Invio] creep

Fail: ( 6) coll(na, ba, G672) ? [Invio] creep

No

Il goal corrente è cioè coll1, con gli argomenti invertiti. Ma nemmeno questo goal ha successo, e, dando ancora, Invio, si esce anche dal goal di livello 6, dal momento che, non essendoci più regole applicabili, non esiste più la possibilità di entrare in modalità Redo.

Il comando/predicato leash consente di visualizzare tutte e 4 le modalità di entrata e uscita dei goal (FULL) o solo alcune, per esempio solo le Call, o solo le Fail, etc.

Inseriamo ora la domanda che, nel caso precedente, aveva bloccato il sistema.

?- coll(X,na,C1),coll(X,rm,C2).

Esiste una città X collegata sia a Napoli che a Roma? Il sistema risponde questa volta nel modo giusto.

X = sa

C1 = 60

C2 = 280 ;

No

La risposta 'No' sta a indicare che non vengono trovate altre soluzioni (ce n'è solo una).

La derivazione simbolica. In una delle prime lezioni avevamo annunciato la possibilità di risolvere il problema della derivazione simbolica utilizzando un listato composto di pochissime linee di codice. Allo scopo, si può usare il file Prolog seguente:

% deriva(f,g,x) f funzione di partenza; g funziona derivata; v variabile

deriva(sin(x),cos(x),x).

deriva(cos(x),-sin(x),x).

deriva(F + G, DF + DG, X) :-

deriva(F, DF, X),

deriva(G, DG, X).

deriva(F * G, DF * G + DG * F, X) :-

deriva(F, DF, X),

deriva(G, DG, X).

Per semplicità, consideriamo solo due derivate elementari, il seno ed il coseno, e due regole di derivazione, la derivata della somma e quella del prodotto. Abbiamo inoltre supposto che la derivazione sia possibile soltanto rispetto alla variabile x. Ciononostante, il sistema risponde correttamente non solo a domande semplici:

?- deriva(sin(x)+cos(x),K,x).

K = cos(x) + (- sin(x))

Ma è in grado di calcolare anche derivate più complesse:

?- deriva(sin(x)+cos(x)*sin(x)+cos(x)*cos(x),H,x).

H = cos(x) + ((- sin(x)) * sin(x) + cos(x) * cos(x)) + ((- sin(x))* cos(x) + (-sin(x)) * cos(x)) [OK!!]

ovvero, calcola esattamente tutte le derivate in cui compaiono esclusivamente seni e coseni (in forma elementare) e operazioni di somma e prodotto.

Come mai il Prolog non segnala alcun errore, non ci dice cioè che i simboli -, + e * che abbiamo usato nelle regole sono non definiti? Inoltre, come mai usa correttamente le parentesi tonde sebbene nella nostra formalizzazione non ne avessimo specificato l'utilizzo? Tali operatori sono già presenti nel Prolog, tuttavia sono soltanto dei simboli: dei simboli autonomi, ma privi di semantica. Essi non rivestono lo stesso significato che hanno nei normali linguaggi di programmazione, ossia in pratica non eseguono nessun calcolo. In Prolog la scrittura 'a + b' viene interpretata come 'il simbolo a, seguito dal simbolo +, seguito dal simbolo b'.

Operatori aritmetici o che permettono il confronto relazionale non sono inclusi nel Prolog versione base, dal momento che lo scopo del Prolog è proprio quello di mettere in piedi dei SF; costruire un SF vuol dire anche definirne gli operatori, per cui non avrebbe molto senso implementare una versione del Prolog con degli operatori predefiniti.

Diamo ora i comandi necessari ad effettuare il tracing:

?- leash(full)

No

trace.

Yes

e sottoponiamo la query:

?- deriva(sin(x)+cos(x)*cos(x),H,x).

Si hanno i seguenti risultati (è sottinteso che ogni riga sia seguita dalla pressione di Invio):

Call: ( 6) deriva(sin(x) + cos(x) * cos(x), G1172, x) ?

Il MI tenta di rendere vero tale predicato; comincia a scorrere la base di conoscenza. Inizia col primo assioma, riscontrando ovviamente che l'unificazione non è possibile, e lo stesso dicasi per il secondo assioma. C'è poi la prima regola. Essendo presente un operatore + sia nella regola che nel goal, il MI unifica F con sin(x) e G con cos(x) * cos(x). (Una variabile può essere unificata, oltre che con una costante, con un gruppo di costanti intramezzate da operatori). Inoltre, H unifica con DF + DG e x on X. Il sistema cerca dunque di rendere vera la precondizione: il prossimo obbiettivo è deriva(F,DF,X).

Call: ( 7) deriva(sin(x), G1664, x) ?

Dove G1664 sostituisce il nome della variabile DF. Da questo goal si esce con successo, e a G1664 viene sostituito l'oggetto costante cos(x).

Exit: ( 7) deriva(sin(x), cos(x), x) ?

Abbiamo quindi risolto il primo goal; il successivo è deriva(G,DG,X) con la sostituzione G = cos(x) * cos(x) e X = x.

Call: ( 7) deriva(cos(x)*cos(x), G1668, x) ?

Questo predicato unifica con la seconda regola: dobbiamo tenerla per il momento in sospeso, e verificare l'unificazione degli oggetti coinvolti. il prossimo obbiettivo è dunque l'unificazione del seguente predicato, che è immediatamente unificabile:

Call: ( 8) deriva(cos(x), G1696, x) ?

Exit: ( 8) deriva(cos(x), - sin(x), x) ?

Usciamo quindi dal livello 8 con successo. Identicamente avviene l'unificazione del secondo coseno, che avviene ancora al livello 8.

Call: ( 8) deriva(cos(x), G1708, x) ?

Exit: ( 8) deriva(cos(x), - sin(x), x) ?

Possiamo quindi uscire con successo anche dal livello 7: è stata calcolata correttamente la derivata del prodotto cos(x) * cos(x).

Exit: ( 7) deriva(cos(x) * cos(x), (-sin(x)) * cos(x) + (-sin(x)) * cos(x), x) ?

A questo punto, avendo risolto il secondo goal, usciamo con successo anche dal primo:

Exit: ( 6) deriva(sin(x) + cos(x) * cos(x), cos(x) + ((- sin(x) * cos(x) + (-sin(x)) * cos(x)), x) ?

H = cos(x) + ((- sin(x)) * cos(x) + (-sin(x)) * cos(x))

È il caso di osservare che nel Prolog prevede anche un ordine di precedenza tra gli operatori-simbolo predefiniti: il * ha precedenza sul +, per cui, anche invertendo l'ordine delle due regole, la derivata verrebbe calcolata comunque in modo corretto.

In Prolog esiste una sola struttura dati vera e propria: la lista. Una lista è una sequenza di elementi racchiusi tra parentesi quadre e separati da virgole. Il Prolog distingue tra liste aperte e chiuse. Una lista è chiusa quando viene determinata per enumerazione dei suoi elementi; è quindi una sequenza finita di oggetti:

[a, 1, b, pippo, .]

Tali oggetti devono essere interpretati come costanti puramente simboliche, come degli atomi privi di una semantica predefinita. In Prolog non esiste un concetto di tipo di variabile. Così, 1 non è una costante numerica e 'pippo' non è una stringa di caratteri: sono semplicemente delle costanti non tipate. In una lista possono essere presenti anche delle variabili:

[a, X, 1, pippo]

dove X è una variabile.

Per poter lavorare con queste strutture dati, dobbiamo definire il modo in cui sono trattate dal MI e in particolare dobbiamo riconsiderare brevemente la tecnica dell'unificazione (consistente, lo ricordiamo, nel creare una corrispondenza tra due nomi simbolici. Due oggetti costanti unificano solo se sono uguali, una variabile semplice unifica sempre con una costante o con un'altra variabile semplice. Si capirà tra breve perché abbiamo specificato: variabile 'semplice').

Che dire dunque di una operazione di unificazione in cui siano coinvolte delle liste chiuse? In quali condizioni è possibile unificare liste con variabili, con costanti o con altre liste?

Unificazione di una costante con una lista chiusa

pippo [e₁, e₂, ., e_n]   NO

questa unificazione non ha mai successo.

Unificazione di una variabile con una lista chiusa

X [e₁, e₂, ., e_n]   SI

Deve essere possibile trovare una corrispondenza in seguito alla quale le due strutture oggetto dell'unificazione rimangano uguali. L'operazione ha banalmente successo: alla variabile X sostituiamo proprio l'intera lista [e₁, e₂, ., e_n]. È sempre possibile unificare una variabile con una lista chiusa.

Unificazione di una lista chiusa con un'altra lista chiusa

Tale unificazione è possibile sotto due condizioni:

le due liste hanno la stessa cardinalità;

gli elementi sono ordinatamente unificabili.

Facciamo alcuni esempi:

[X, pippo, 3] unifica con [papa, Y, 3]

[X, pippo, 3] non unifica con [papa, X, 3]

poiché la variabile X dovrebbe assumere due valori differenti, cosa inammissibile. In seguito alla prima unificazione, la X diventa una variabile 'bind' ('legata' ad un valore: papa), per cui la seconda unificazione consisterebbe nell'unificare due costanti diverse: 'papa' e 'pippo'.

[X, pippo, 3] unifica con [[1, 2], Y, 3]

dove gli elementi omologhi unificano nel seguente modo: X = [1, 2]; Y = pippo.

[X, pippo, 3] non unifica con [1, 2, Y, 3] (differente cardinalità)

[X, pippo, 3] unifica con [[Y, 5], Y, 3]

con l'unificazione: X = [pippo, 5] (confronta l'unificazione di Y); Y = pippo.

Una lista aperta si presenta nel formato proposto di seguito:

[e₁, e₂, ., e_k | Y ]   (più comunemente la si indica come: [ X | Y ])

In una lista aperta il numero degli elementi non è dunque specificato in partenza (non viene data per enumerazione). Piuttosto, essa viene definita in funzione di un'altra lista. La lista appena indicata contiene gli elementi e₁, e₂, ., e_k, (che a loro volta possono essere costanti, variabili, liste aperte o chiuse), più (dopo il simbolo | ) una coda rappresentata dalla variabile Y. Y è a sua volta una lista, contenente un certo numero di elementi i quale partecipano come elementi della lista principale. La coda Y può anche non essere precisata nel momento in cui si definisce la lista aperta, oppure può essere nota solo in parte. È proprio questo il grande vantaggio dell'uso delle liste in Prolog. Si pensi al problema del commesso viaggiatore: solo al termine del processo inferenziale otterremo una lista chiusa con tutte le città che compongono il cammino richiesto; durante i passi intermedi, lo stato del sistema sarà intuitivamente costituito da una sequenza incompleta di città, ovvero da una lista aperta contenete le città visitate fino a quel momento.

Nel caso più frequente, la 'testa' della lista (ciò che precede il simbolo | ) è composta da un solo elemento. Con la scrittura [ X | Y ], si intende dunque che X è un singolo oggetto e la coda Y è l'insieme di tutti gli altri elementi della lista, dal secondo in poi.

Chiediamoci ora come si realizzano le unificazioni in presenza di liste chiuse. Il caso più ricorrente è l'unificazione tra liste aperte e liste chiuse:

[pippo, 3, pluto] unifica con [ X | Y ]

dove X = pippo e Y = [3, pluto]. Si noti che Y è una lista.

[pippo, 3, pluto] unifica con [ X, Y | Z ]

dove Z è una lista contenente un solo elemento: Z = [pluto].

[ [pippo, 3], pluto] unifica con [ X, Y | Z ]

con X = [pippo, 3], Y = pluto e Z = [] (lista vuota).

[pippo] unifica con [X | Y]

dove Y è uguale alla lista vuota.

[pippo] non unifica con [X, Y | Z]

è evidente che la lista chiusa deve avere una cardinalità almeno pari alla cardinalità della testa della lista aperta perché si realizzi l'unificazione.

La ricorsione. È una tecnica di sviluppo algoritmico che ha poco a che vedere con la programmazione procedurale (pur essendo prevista dalla maggior parte dei linguaggi di programmazione tradizionali) e che invece deve molto all'AI.

Consideriamo un problema P, e immaginiamone una decomposizione in problemi più semplici P₁, P₂, ., P_n. È ovvio che tale 'decomposizione' può avvenire in accordo a svariate metodologie. Ad esempio, se P è il problema di memorizzare la versione ordinata di un archivio elettronico, i sottoproblemi potrebbero consistere nella lettura, nell'ordinamento e nella scrittura ordinata del file. In effetti il problema di partenza si presenta per sua natura come decomposto in una serie di task elementari; i task sono inoltre autonomi: devono essere eseguiti in un certo ordine perché l'elaborazione risulti significativa, ma a parte questo tra di loro non vi è alcuna similitudine o interdipendenza concettuale.

Un modo di pensare del tutto diverso consiste nel decomporre il problema in sottoproblemi, ciascuno dei quali risolva, in definitiva, lo stesso quesito sollevato dal problema di partenza, ma in forma ridotta (scalatura della complessità). In pratica adottiamo un modello grazie al quale un problema viene scomposto e definito in termini di sé stesso. Questo è il punto di partenza verso un approccio ricorsivo alla progettazione dei programmi.

Poiché la ricorsione costituisce anche un modo importante di rappresentare la conoscenza, chi opera nel settore dell'AI riesce mediamente ad utilizzarla con maggiore disinvoltura di un programmatore tradizionale, che in genere trova difficile impiegare tecniche ricorsive se non in contesti troppo semplici e, proprio per questo motivo, fuorvianti (vedi il classico esempio del fattoriale). Eppure, tra i meccanismi che gli esseri umani impiegano più di frequente (senza rendersene conto) nell'elaborare pensieri vi è proprio quello ricorsivo. Una tecnica ricorsiva l'abbiamo già usata nella scorsa lezione, quando abbiamo digitato il listato Prolog per la derivazione simbolica. Dire che la derivata della somma è la somma delle derivate:

deriva(F + G, DF + DG, X) :-

deriva(F, DF, X),

deriva(G, DG, X).

significa definire una funzione in termini di sé stessa e quindi adottare un procedimento ricorsivo.

La ricorsione presenta inoltre il grande vantaggio di essere facilmente esprimibile in termini formali: alla base della ricorsione c'è infatti il celebre principio di induzione matematica.

Che l'induzione matematica sia applicabile alla programmazione dei computer si può dedurre - almeno in linea di principio - se si considera l'equivalenza concettuale che sussiste tra il 'dimostrare un teorema' a partire da dati assegnati e l''applicare un programma elaborativo' ad un set di dati di ingresso. Di conseguenza P(x_i) può essere pensato, oltre che come la verifica di una proprietà al termine di una successione, come una computazione effettuata su un dato scelto tra un set di dati in ingresso.

In particolare, data la suddivisione di un problema P negli n sottoproblemi P₁, P₂, ., P_n nel senso cui si accennava prima, ipotizzando di possedere soluzioni corrette per tali sottoproblemi, se riusciamo a mettere in relazione le soluzioni dei sottoproblemi con la soluzione del problema padre, abbiamo in pratica realizzato un algoritmo ricorsivo. Il principio di induzione garantisce l'esattezza della soluzione così trovata.

Un classico esempio: il rompicapo delle Torri di Hanoi. Abbiamo 3 pioli ed un certo numero di dischi, tutti di diametro differente. Scopo del gioco è di spostare l'intera colonna di dischi dal piolo A di partenza al piolo C rispettando le seguenti regole: si può spostare un solo disco per volta, quello che si trova in cima ad un piolo, e un disco può essere spostato solo su di un disco più grande (o in un piolo vuoto). La soluzione è banale se si ha a che fare con due o tre dischi, ma diventa molto complicata già per cinque dischi soltanto.

A tutt'oggi nessuno è stato capace di trovare un algoritmo (nel senso tradizionale del termine) che fosse in grado di risolvere il gioco nel caso generale. In particolare, se si studiano le sequenze di mosse necessarie per risolvere il gioco con 2, 3, 4, 5 . dischi, non si riesce a individuare nessuna relazione tra esse; tale relazione esiste ma è così complessa che non è stata ancora dedotta. In particolare, ciò che la rende complessa è il fatto che le singole azioni elementari di ogni passo del processo di risoluzione si innestano l'una dentro l'altra.

Il problema delle torri di Hanoi ammette invece una soluzione ricorsiva semplicissima ed elegante. Consideriamo il seguente formalismo:

H_AC^B (n)

dove il pedice indica i pioli usati rispettivamente come origine e destinazione, l'apice il piolo intermedio, e l'argomento è il numero n di dischi. Questo simbolo rappresenta quindi la sequenza di mosse che costituisce la soluzione del problema di Hanoi con n dischi da spostare tra A e C usando B come piolo intermedio.

Dobbiamo ora porci l'obbiettivo di individuare una tecnica per suddividere il problema in problemi più semplici della stessa natura (questa è la fase detta, in latino, di divide). Essendo chiaro che il problema diviene sempre più difficile al crescere del numero di dischi, ci proponiamo di suddividere il problema con n dischi in sottoproblemi con n-1 dischi, quello con n-1 dischi in sottoproblemi con n-2 dischi, ecc. Proseguendo in tal modo con il processo di semplificazione, ci aspettiamo di avere a che fare prima o poi con problemi di Hanoi abbastanza semplice da poter essere risolti in maniera indipendente. È ovvio che il problema di Hanoi più semplice possibile e immaginabile è quello con uno solo disco:

H_XY^Z (1)

La fase successiva (ìmpera e combina) consiste nell'utilizzare il principio di induzione matematica. Ipotizziamo di conoscere le soluzioni dei problemi H(n-1), e cerchiamo di ricostruire la soluzione del problema padre H(n) mettendo insieme le soluzioni dei problemi di ordine n-1. Così facendo, in pratica è come se avessimo dimostrato l'implicazione che figura come ipotesi del principio di induzione; è dunque applicabile il principio stesso, il quale ci garantisce che abbiamo risolto il problema H(n) n.

Il processo ricorsivo di risoluzione di questo problema può essere pensato anche in termini più familiari, supponendo che, dato il grafo dei passi di risoluzione del problema, il nodo padre, che deve risolvere H_AC^B (n), possa commissionare ai nodi figli la risoluzione di problemi di ordine (n-1). Esso non ha alcuna necessità di sapere come fanno i figli a ricavare le proprie soluzioni. Ricevute le soluzioni dei nodi figli, il padre deve limitarsi a metterle insieme nel modo corretto per costruire la soluzione del problema che gli è stato assegnato.

In che modo il padre deve mettere insieme le soluzioni ricavate dai figli? La sequenza giusta si evince dall'albero riportato qui sopra. Un primo figlio colloca tutti gli (n-1) dischi superiori dal piolo A al piolo B, usando C come piolo intermedio. (Allo scopo dovrà effettuare presumibilmente un gran numero di mosse; in ogni caso il modo in cui risolve il problema non interessa al nodo padre). Un secondo figlio trasferisce un singolo disco dal piolo A al C, usando B come intermedio. Infine, un terzo figlio trasferisce l'intera catasta di (n-1) dischi dal nodo B al C, usando A come intermedio. Se si visualizzano mentalmente le mosse effettuate dai tre figli, ci si rende conto che questa procedura risolve effettivamente il problema.

Ovviamente tutto ciò è vero sempre che si supponga che il primo ed il terzo figlio sappiamo fare correttamente le operazioni complesse che sono state loro assegnate: ma questo non è un problema. Nella filosofia della ricorsione, infatti, ogni nodo figlio diviene a sua volta padre di tre nodi, due dei quali in grado di risolvere problemi di Hanoi di grado (n-2). Si va avanti così per semplificazioni successive, fino a raggiungere, nei livelli più profondi dell'albero, problemi di Hanoi ad un solo disco, che sono banalmente risolvibili.

Il 'cuore' del programma ricorsivo è dunque costituito da 3 linee di codice appena, quelle che formalizzano le mosse indicate nel grafo.

Consideriamo per esempio come opera l'algoritmo ricorsivo per un problema di Hanoi a 3 pioli e 4 dischi. (Il procedimento illustrato non ha valore di dimostrazione; chi è abituato alla programmazione ricorsiva non ha alcuna necessità di ripercorrere mentalmente i passi dell'algoritmo ricorsivo durante il suo funzionamento, per essere sicuro che tutto proceda per il verso giusto. Il principio di induzione, se ben applicato, fornisce di per sé tale garanzia). Qui a lato riportiamo una notazione sintetica, di facile comprensione, per indicare la configurazione iniziale delle torri (4 = disco più grande).

Inizialmente, l'unico nodo presente è il padre, che deve risolvere il problema originario. Esso deve dare luogo a tre nodi figli; innanzitutto si genera il primo, incaricato di risolvere il problema di spostare 3 dischi dal piolo A al piolo B, usando C come piolo intermedio. Nel grafico che segue, il primo figlio generato è indicato con un riquadro continuo e gli altri due, che saranno generati in seguito, con un riquadro tratteggiato.

Tale nodo deve generare a sua volta tre figli. Il nodo più a sinistra, generato per primo, deve risolvere un problema di Hanoi di ordine 2; allo scopo esso genera tre figli, ciascuno dei quali, avendo a che fare con problemi di Hanoi di ordine 1, deve semplicemente spostare un disco dall'origine verso la destinazione specificate. Si noti come il ruolo svolto dai vari pioli nei tre figli di ogni padre cambi di livello in livello.

I 3 problemi di Hanoi di ordine 1 che abbiamo individuato all'ultimo passo sono immediatamente risolvibili e la loro soluzione corrisponde ad effettuare mosse che seguono:

(nodo sinistro)

(nodo centrale)

(nodo destro)

La collocazione dei 4 dischi a questo punto dell'algoritmo è quella indicata sulla destra. Si osservi come abbiamo effettivamente risolto il problema H_AC^B (2).

Dato che il figlio H_AC^B (2) ha terminato il proprio lavoro, il padre H_AB^C (3) attiva il suo secondo figlio (contrassegnato da una freccia), che è a sua volta un problema di Hanoi di ordine 1, cui corrisponde la mossa:

Viene poi attivato il terzo figlio, che è un H_BC^A (2). Esso genera a sua volta i tre figli che sono stati aggiunti nel grafico seguente.

Ad essi corrispondono le mosse:

e quindi anche H_AB^C (3) può dirsi completamente risolto. Proseguendo in questo modo, si arriva, dopo un certo numero di mosse, alla configurazione cercata.

Un altro esempio: il determinante di una matrice. In questo caso la procedura ricorsiva è dettata dalla definizione stessa di determinante per una matrice quadrata di ordine n. Il determinante è infatti pari alla somma dei prodotti degli elementi di una riga (ad es. la prima) per i minori complementari di ordine (n-1), che sono a loro volta dei determinanti. Come caso banale potremmo considerare il determinate di una matrice di ordine 1 o, al massimo, di ordine 2. Usare la ricorsione rende immediata la risoluzione del problema, laddove un approccio tradizionale risulterebbe particolarmente laborioso.

Consideriamo oggi alcuni esempi di programmazione ricorsiva che utilizzano le liste. Il Prolog 'costringe' alla programmazione ricorsiva, essendo privo dei comandi tipici della programmazione iterativa (for, while ecc).

Risolviamo il problema di determinare l'appartenenza di un elemento ad una lista. Questa funzione è già presente come predicato nel Prolog, ma sarà istruttivo definirla daccapo, e lo faremo mediante la ricorsione. Una funzione ricorsiva viene messa a punto grazie all'approccio divide et impera, composto di tre fasi, le due che danno il nome al metodo più la fase di combina. Oltre a ciò, va sempre effettuata l'operazione cosiddetta di chiusura della ricorsione: l'individuazione di un caso semplice, del quale è immediatamente disponibile la soluzione (ad es.: risolvere il gioco delle Torri di Hanoi con un solo disco, o calcolare il fattoriale di 1), e che quindi non richiede l'invocazione di ulteriori suddivisioni del problema.

Per risolvere il problema proposto con tecniche ricorsive, dobbiamo ricondurre il problema ad un problema dello stesso tipo, ma più semplice. In particolare, il problema dell'appartenenza ad una lista sarà ricondotto ad un altro problema di appartenenza ad una lista. Perché si abbia una effettiva riduzione di complessità, possiamo pensare che la ricerca di appartenenza ad una lista sia ricondotta alla ricerca di appartenenza ad una lista che è un sottoinsieme della prima. La ricorsione quindi, in questo caso, consiste nel suddividere la struttura dati, ottenendo una corrispondente suddivisione del problema. Si noti che nel caso delle Torri di Hanoi avevamo suddiviso il processo di risoluzione in un certo numero di passi più semplici, e non la struttura dati: la strategia di decomposizione di un problema dipende cioè dal caso specifico.

La suddivisione della lista non va fatta a caso, ma in funzione delle tecniche messe a disposizione dal Prolog. Abbiamo visto che una lista aperta è una lista separata in due parti: il primo elemento (testa) e la sottolista composta da tutti gli altri, dal secondo all'ultimo (coda). In effetti l'unica possibilità di separare una lista in Prolog è quella di dividerla nella forma testa + coda. Di conseguenza, per risolvere il problema in forma ricorsiva, dividiamo il problema ipotizzando di applicarlo o sulla testa, o sulla coda della lista.

Cominciamo a vedere come va fatta la chiusura della ricorsione. Un caso in cui il problema è banalmente risolto è evidentemente quello in cui l'elemento cercato è proprio il primo della lista. L'espressione della chiusura potrebbe essere quindi:

1) membro(A, [A|B]).

Abbiamo quindi definito un predicato a due posti, con al primo posto un elemento singolo, e al secondo una lista. A simboleggia il primo elemento della lista, a sua volta rappresentata come composta di due pezzi, testa + coda. Il predicato risulta verificato quando l'elemento fornito come primo oggetto del predicato coincide con la testa della lista.

Si osservi che la prima regola può essere scritta anche come:

1) membro (ELEM, [H|T]) :-

ELEM = H. T membro(ELEM, [ELEM|T]] ])

Un elemento appartiene ad una lista L, composta da testa H e coda T, se coincide con la testa.

Digitando ad esempio la query:

?- membro(2, [3, 5]).

si ha l'unificazione di A (una variabile) con 2. A questo punto, la lista aperta [A|B] diviene una lista con 2 come primo elemento, seguito da una coda non specificata. Tale lista non unifica quindi con il secondo elemento della query, la lista chiusa [3,5].

Stabilita la chiusura della ricorsione, dobbiamo ora risolvere il problema nel caso induttivo. Supponiamo che l'elemento da cercare NON si trovi in testa alla lista. Per ipotesi induttiva, esiste un nodo 'figlio' che è capace di risolvere correttamente il problema di determinare se un elemento appartiene o meno alla lista coda (fase di IMPERA). In caso affermativo, il nodo 'padre' deduce che l'elemento deve appartenere anche alla lista completa dell'elemento di testa (e all'opposto se non appartiene alla coda, non appartiene neanche alla lista completa). Il predicato ricorsivo che definisce l'appartenenza di un elemento ad una lista è quindi:

2) membro(A, [B|C]) :-

membro(A, C).

La regola ci dice: 'se l'elemento A appartiene alla coda della lista (ipotesi induttiva), appartiene anche alla lista'.

Per capire meglio il funzionamento dell'insieme dei due predicati:

membro(A, [A|B]).

membro(A, [B|C]) :-

membro(A, C).

effettuiamo il trace della seguente query:

?- membro(2, [4,5,3,5]).

Ovviamente, non unifica con la prima regola.

Call:   ( 6) membro(2, [4, 5, 3, 5]) ? creep

Tenta allora l'unificazione con la postcondizione della seconda; l'unificazione ha successo con A = 2, B = 4, C = [5,3,5]. Si genera quindi il goal membro (A, C).

Call:   ( 7) membro(2, [5, 3, 5]) ? creep

Si osservi come siamo passati ad un livello di profondità maggiore (da 6 a 7). Si ha ancora unificazione con la seconda regola, ottenendo il goal membro(2, [3, 5])

Call:   ( 8) membro(2, [3, 5]) ? creep

Procedendo analogamente:

Call:   ( 9) membro(2, [5]) ? creep

Call:   ( 10) membro(2, []) ? creep

L'unificazione fallisce sia con la prima regola che con la postcondizione della seconda:

Fail:   ( 10) membro(2, []) ? creep

Usciamo dunque con Fail dal livello 10. Si torna indietro, valutando se il predicato membro(2, [5]) possa essere unificato con altre regole (successive alla seconda); la risposta, dal momento che tali ulteriori regole non esistono, è negativa e quindi si esce con un fallimento anche dal livello 9:

Redo: ( 9) membro(2, [5]) ? creep

Fail:   ( 9) membro(2, [5]) ? creep

Analogamente:

Redo: ( 8) membro(2, [3, 5]) ? creep

Fail:   ( 8) membro(2, [3, 5]) ? creep

Redo: ( 7) membro(2, [5, 3, 5]) ? creep

Fail:   ( 7) membro(2, [5, 3, 5]) ? creep

Redo: ( 6) membro(2, [4, 5, 3, 5]) ? creep

Fail:   ( 6) membro(2, [4, 5, 3, 5]) ? creep

No

Si noti come evolve invece il trace di una query con esito positivo:

?- membro(2, [4,2,3,5]).

Call: ( 6) membro(2, [4, 2, 3, 5]) ? creep

Call:   ( 7) membro(2, [2, 3, 5]) ? creep

Exit: ( 7) membro(2, [2, 3, 5]) ? creep

Exit:   ( 6) membro(2, [4, 2, 3, 5]) ? creep

Il sistema è anche in grado di rispondere correttamente a domande più complesse: una lista è contenuta all'interno di una lista di liste?

?- membro ([3], [[1, 2], [3], [1, 6]]).

Yes

Ciò è davvero stupefacente. In un tradizionale linguaggio di programmazione, sarebbe naturalmente possibile realizzare una funzione che cerca un elemento intero in una lista di interi, oppure una funzione che cerca un carattere in una lista di carattere e via discorrendo; si è cioè costretti a scrivere tante funzioni di appartenenza quanti sono i tipi di dato previsti dal linguaggi. In Prolog, invece, tutto ciò che conta è il concetto puro e semplice di appartenenza ad un insieme; non interessa la natura degli elementi dell'insieme. Esprimiamo cioè solo il legame esistente dai dati, indipendentemente dal tipo. L'utilizzabilità della nostra KB è dunque del tutto generale; permette di verificare l'appartenenza di una stringa ad una lista di stringhe, di un grafo ad una lista di grafi, di un programma ad una lista di programmi, ecc. La seguente query verifica l'appartenenza di una 'lista di liste' (in rosso) ad una 'lista di liste di liste' (!!):

?- membro ( [ [1], [2,3],[4,5] ] , [ [[ ]] , ] ).

Yes

Un'altra query, in cui usiamo la variabile X:

?- membro(X, [1,2,3]).

X = 1;

X = 2;

X = 3;

No

Un elemento X appartiene alla lista [1, 2, 3]? Sì, ed il problema ammette le tre soluzioni indicate sopra.

?- membro(1, X).

1 appartiene ad una lista X? Intuitivamente, il problema ammette infinite soluzioni, e infatti continuando a dare il punto e virgola il sistema fornisce infinite risposte:

X = [1|G880];

una possibile soluzione è cioè la lista con 1 come primo elemento, seguito da una coda qualunque, oppure:

X = [G876, 1|G892];

cioè una lista con un elemento di testa qualunque, l'elemento 1 in seconda posizione ed una coda qualunque, oppure:

X = [G876, G888, 1|G904];

ecc. ecc.

Un altro problema. Vogliamo realizzare un predicato 'appendi' che risulti vero quando una lista L3 risulti essere la concatenazione tra le due liste L1 ed L2. Sono quindi in gioco tre liste.

Una soluzione abbastanza semplice si ottiene sfruttando la possibilità di decomposizione di una lista, offerta dal Prolog, in testa + coda. Il predicato 'chiusura della ricorsione' è quello in cui la lista L1 è vuota, per cui le liste L2 ed L3 coincidono:

1) appendi([ ], A, A).

Per il caso ricorsivo, possiamo pensare, inizialmente, di suddividere tutte e tre le liste nel formato testa + coda:

2) appendi( [T1|C1], [T2|C2], [T1|C3]) :-

Dove L1 = [T1|C1], ecc. Da notare che la testa della lista concatenata coincide con la testa di L1. Quale dev'essere la precondizione? Ipotizziamo che un nodo figlio sappia risolvere un problema più semplice, in cui appendiamo una lista L2 non all'intera L1, ma ad L1 privata del primo elemento (ovvero la coda C1). Il risultato sarà dato dalla sola coda C3 della lista L3. Si ha dunque:

2) appendi( [T1|C1], [T2|C2], [T1|C3]) :-

appendi(C1, L2, C3)

Poiché però la suddivisione della lista L2 non entra in gioco nella precondizione, essa è superflua e la seconda regola può essere riformulata come segue:

2) appendi( [T1|C1], L2, [T1|C3]) :-

appendi(C1, L2, C3)

La lista soluzione del problema padre contiene come primo elemento il primo elemento di L1, e come coda il risultato C3 dell'operazione "appendi" della coda C1 con la lista L2. Semplificando i nomi delle variabili in gioco, la nostra KB può essere descritta dall'insieme delle due regole:

1) appendi([ ], A, A).

2) appendi( [A|B], C, [A|D] ) :-

appendi(B, C, D).

Come sempre, una rassegna di query da sottoporre al sistema permetterà di apprezzare la potenza espressiva del Prolog. Nelle query si può utilizzare L1, L2 o L3 come incognita, o due di esse, o anche tutte e tre, in modo del tutto arbitrario.

Cominciamo con l'uso più ovvio:

?- appendi([1, 2], [3, 4], C).

C = [1, 2, 3, 4]

Altra domanda: come deve essere fatta una lista L2 per ottenere una lista, questa volta assegnata, L3, per concatenazione? Il sistema fornisce correttamente l'unica soluzione.

?- appendi([1, 2], X, [1, 2, 3, 4, 5]).

X = [3, 4, 5]

Altra query: come devono essere fatte due liste incognite Y e X per ottenere la lista L3 (la stessa di prima)?

?- appendi(Y, X, [1, 2, 3, 4, 5]).

Non è difficile intuire che il problema ammette 6 soluzioni, e il Prolog puntualmente le trova tutte (non si dimentichi che l'interprete fornisce una soluzione dopo l'altra digitando il punto e virgola; con un semplice invio viene interrotto il processo di ricerca delle soluzioni).

X = [1, 2, 3, 4, 5]

Y = [];

X = [2, 3, 4, 5]

Y = [1];

X = [3, 4, 5]

Y = [1, 2];

X = [4, 5]

Y = [1, 2, 3];

X = [5]

Y = [1, 2, 3, 4];

X = []

Y = [1, 2, 3, 4, 5]

Altra query: data una lista aperta con testa = 1 e coda variabile, ed una lista chiusa [5], come dev'essere fatta la coda variabile perché si abbia la lista L3 = [1, 2, 3, 4, 5]? (Quale sostituzione per Y rende vero il predicato?)

?- appendi ([1|Y], [5], [1, 2, 3, 4, 5]).

Y = [2, 3, 4]

Ancora :

?- appendi ([1|Y], [4|Z], [1, 2, 4, 3, 4, 5]).

Dato che il simbolo 4 compare due volte nella lista concatenata, la query ammette due soluzioni:

Y = [2]

Z = [3, 4, 5] ;

Y = [2, 4, 3]

Z = [5]

Cosa accade se nell'ultima query anche L3 è variabile?

?- appendi ([1|Y], [4|Z], V).

È facile rendersi conto che le soluzioni sono infinite, e anche la loro struttura è facilmente prevedibile.

Y = []

Z = G944

V = [1, 4|G944] ;

Y = [G1412]

Z = G944

V = [1, G1412, 4|G944] ;

Y = [G1412, G1436]

Z = G944

V = [1, G1412, G1436, 4|G944] ;

eccetera. Come si vede, il MI introduce all'infinito un elemento qualunque tra 1 e 4.

Una query a ben 5 variabili: vogliamo ottenere tutte le liste in cui il primo, il secondo ed il quinto elemento sono non specificati, e la coda è non specificata:

?- appendi ([1, 2|Y], [4], [X, Z, 1, 2, L, 4|V]).

X = 1

Y = [1, 2, G1516]

Z = 2

L = G1516

V = []

X = 1

Y = [1, 2, G1516, 4]

Z = 2

L = G1516

V = [4]

X = 1

Y = [1, 2, G1516, 4, G2480]

Z = 2

L = G1516

V = [G2480, 4]

Il SF che risiede dietro al concetto di appendere due liste è particolarmente semplice (solo 2 regole), eppure consente di dimostrare teoremi anche molto complessi. In realtà, moltissimi teoremi matematici che prima dell'avvento dell'AI erano sconosciuti sono stati dimostrati automaticamente, grazie a tali strumenti.

Ancora sul problema del commesso viaggiatore. Arricchiremo la base di conoscenza pregressa (riproposta di seguito):

%coll(x, y, c) se x è collegato a y con costo c

coll1(na, rm, 220).

coll1(rm, fi, 200).

coll1(fi, bo, 100).

coll1(na, sa, 60).

coll1(sa, rm, 280).

coll(X, Y, C) :-

coll1(X, Y, C).

coll(X, Y, C) :-

coll1(Y, X, C).

utilizzando le liste oltre alla ricorsione, in modo da ottenere una KB maggiormente significativa. In particolare, vogliamo trovare un predicato che permetta di trovare tutti i cammini possibili fra due città della nostra mappa geografica. Tale predicato sarà del tipo indicato nei commenti che seguono:

% collegamento (ci, cf, lp, lc, c)

% ci = città iniziale cf = città finale

% lp = lista delle città proibite

% lc = un possibile cammino tra ci e cf

% c = costo del cammino

% esempio d'uso: collegamento(na, bo, [fi, sa], L1, C1).

Il nostro predicato permette cioè di specificare, oltre alle due città terminali, anche una lista Lp di città per il quale il cammino incognito non deve passare. Questo è molto importante, perché così facendo si impedisce che i cammini determinati dal MI contengano cicli (ad es: Napoli-Roma-Firenze-Roma-Firenze.), rendendo i risultati privi di significato. Supponiamo che la città iniziale sia automaticamente proibita: non sarà necessario specificarla nella lista Lp. (Una alternativa sarebbe quella di definire il sistema in modo che questa condizione su Ci non sia specificata; quando formuleremo le nostre query, dovremo quindi includere esplicitamente Ci nella lista Lp).

Il ricorso alle liste, in particolare quelle aperte, è intuitivo, poiché ciò che il MI deve costruire mano mano è proprio una lista di città che vanno da Ci a Cf. Per quanto riguarda la ricorsione, si può decidere, arbitrariamente, di esprimere prima la chiusura o prima il predicato ricorsivo. Partiamo questa volta dal predicato ricorsivo.

Il predicato che vogliamo ottenere, ovvero la postcondizione della nostra regola (che risulterà alla fine abbastanza sofisticata) è evidentemente:

collegamento(Ci, Cf, Lp, Lc, C) :- .

Un primo predicato precondizione che contribuisce alla determinazione del risultato potrebbe essere:

coll(Ci, Cint, C1),

col che ci ripromettiamo di trovare una città (Cint) a distanza unitaria dalla città di partenza. Nello spirito della ricorsione, infatti, si immagina che un 'figlio' sia in grado di risolvere una versione più semplice del problema; ad esempio, se dobbiamo andare da Napoli a Bologna, il 'padre' si muove da Napoli ad una città vicina, poniamo che sia Roma, e il 'figlio' risolve il problema di trovare un cammino tra Roma e Bologna (fase di 'ìmpera').

Il successivo predicato, dunque, esprimerà il cammino L1c tra la Cint così determinata e la città finale (ed è qui che interviene la ricorsione):

collegamento(Cint, Cf, [Ci|Lp], L1c, C2),

C2 è il costo di questa seconda parte del cammino. Si osservi che le città proibite per il 'padre' lo sono anche per il 'figlio', ed in più quest'ultimo deve anche sapere che il cammino che determinerà non deve ripassare per la città di partenza (Ci). La città Ci viene inserita in testa alla lista delle città proibite per il figlio; questo è infatti l'unico modo che conosciamo di aggiungere elementi ad una lista.

Nella fase di 'combina', il padre deve mettere in relazione la soluzione del figlio (o dei figli) con la soluzione del problema di partenza. Il costo C del cammino complessivo dev'essere la somma di C1 e C2; ciò si esprime col predicato:

C is C1+C2,

Inoltre, dobbiamo trovare anche la relazione che passa tra L1c (cammino individuato dal figlio) ed Lc (cammino individuato dal padre); ciò è abbastanza intuitivo: Lc equivale a [Cint|L1c]. Assodato ciò, la postcondizione della regola viene riscritta come segue:

collegamento(Ci, Cf, Lp, [Cint| L1c], C) :- .

Infine, finora non è stato mai formalizzato il fatto che Lp sia una lista di città 'proibite'. In particolare, la città Cint di volta in volta trovata dal padre non deve far parte di Lp. Anche ciò può essere espresso con un predicato predefinito del Prolog:

not member(Cint, Lp),

Scrivendo i predicati nell'ordine che appare più opportuno (ma unicamente per ragioni di leggibilità), il predicato ricorsivo appare come segue:

collegamento(Ci, Cf, Lp, [Cint| L1c], C) :-          

coll(Ci, Cint, C1),

not member(Cint, Lp),

collegamento(Cint, Cf, [Ci|Lp], L1c, C2),

C is C1+C2.

Prima di ciò va messa la chiusura della ricorsione: la sua espressione riesce, a questo punto, abbastanza evidente.

collegamento(Ci, Cf, Lp, [Ci, Cf], C2):-

coll(Ci, Cf, C2),

not member(Cf, Lp).

La ricorsione cioè si chiude se tra Ci e Cf esiste un collegamento diretto. Cf non deve appartenere alla lista delle città proibite.

GLI OPERATORI EXTRALOGICI DEL PROLOG. Vengono così definiti perché la loro funzionalità è esterna alla programmazione logica. Il loro utilizzo, infatti, altera il modello di comportamento classico del MI. Gli operatori extralogici sono tre:

CUT (simbolo '

FAIL

NOT

Curiosa la presenza tra gli operatori extralogici del NOT, che nell'ambito della programmazione tradizionale è invece proprio un operatore logico.

Oggi si soffermeremo sul CUT. A dispetto dell'apparente semplicità, è decisamente il più complesso dei tre operatori extralogici, e quello che richiede la maggiore attenzione per essere compreso nella sua esatta natura e impiegato proficuamente; esiste una voluminosa letteratura dedicata esclusivamente al suo utilizzo.

Per capire il funzionamento del cut, è essenziale avere un chiaro quadro mentale dei meccanismo di backtracking e redo. A tale scopo faremo dapprima un esempio più semplice, poi uno più sofisticato.

Primo caso (un livello di profondità) Consideriamo il seguente brano di SF, in cui, per semplicità, compaiono soltanto i nomi dei predicati.

b₁ :- a₁, a₂, ., a_n

b₁ :- c₁, c₂, ., c_m

b₁ :- d₁, d₂, ., d_s

Si tratta cioè di 3 regole alternative che ammettono b₁ come conseguente. Il predicato b₁ è espresso in tutti i casi come congiunzione di regole a_i, c_i, d_i.

È data la query:

?- b₁

Il MI cerca di unificare b₁ con una delle postcondizioni delle regole del SF. La prima regola che incontra è:

b₁ :- a₁, a₂, ., a_n

Supponendo che l'unificazione sia possibile (dipende ovviamente dalle variabili coinvolte), il nuovo goal corrente diviene a₁.

Il sistema tenta di verificare a₁, cercando di unificarla con la postcondizione di una regola che ammette a₁ come conseguente. a₁ avrà un certo numero di variabili libere (non ancora unificate), più altre già unificate. Può accadere che qualcuna delle variabili che erano ancora libere, in seguito a tale processo di verifica, si vada ad unificare (binding, associazione di un valore ad una variabile inizialmente libera).

Supponiamo di riuscire a rendere vero il goal a₁. Dobbiamo quindi passare al goal a₂. Che accade se nel goal originale a₁ e a₂ condividevano alcune variabili? Ad esempio:

a₁ (X, Y)         a₂(X, Z)

In tal caso, il tentativo di unificazione per a₂ non può che essere fatto tenendo conto dei binding di variabili già effettuati. Se a₁, durante il suo processo di unificazione, ha effettuato un binding X = 3, ovviamente si cercherà di dimostrare a₂ con X legata al valore 3. Infatti, ogniqualvolta si effettua un binding, il valore relativo viene associato alla variabile per ciascuna occorrenza all'interno di una stessa regola.

Percorriamo dunque il database alla ricerca di una regola che ammetta a₂ come postcondizione. Immaginiamo per esempio che durante tale ricerca la variabile Z (che è variabile solo di a₂ e non anche di a₁) venga legata al valore 5. Risulta tuttavia che non è possibile trovare una unificazione valida per questo predicato. Non riusciamo cioè a verificare a₂ con l'insieme delle associazioni effettuate fino a questo momento (X = 3, Z = 5).

Il MI allora torna indietro di un passo (backtracking). Ciò dipende dal fatto che esso opera in accordo ad una strategia DFS (ricerca in profondità nel grafo della dimostrazioni): quando ha verificato il goal a₁, non si è preoccupato di trovare tutte le alternative valide per il predicato a₁. Quindi, in presenza di un fallimento per a₂ deve cercare di capire (redo) se per caso esiste un'altra possibilità di rendere vera a₁.

Che ne è delle variabili che fino a questo momento sono state legate a dei valori? Quando si effettua il backtracking, si devono liberare tutte e sole le variabili che sono state legate durante la dimostrazione di a₂: nel nostro caso, viene liberata solamente la variabile Z[3].

Secondo caso: aggiungiamo un livello di profondità. L'obbiettivo è di dimostrare il predicato:

b₁ :- a₁(X, Y), a₂(X, Z, J), ., a_n.

Dovendo verificare a₁ (X, Y), ipotizziamo di incontrare un fatto espresso come:

a₁(3, W) :- .

si ha quindi l'unificazione di X con 3. Dobbiamo ora dimostrare tutti i goal che stanno alla destra del simbolo :- . Supponiamo che ciò abbia successo: abbiamo quindi reso vero a₁ con la sostituzione X = 3. Per a₁ esisteranno eventualmente altre alternative, che per ora non vengono prese in considerazione:

a₁(3, W) :- .

a₁(4, W) :- .

Il binding effettuato sulla variabile X viene trasportato per tutti i goal conseguenti ad a₁ nella definizione di b₁. Il primo di essi è a₂(X, Z, J). Dato il binding precedente per X, il goal corrente diventa a₂(3, Z, K). Nel percorrere il database, supponiamo di trovare per a₂ una ulteriore regola (K variabile) :

a₁(3, W) :- .

a₁(4, W) :- .

a₂(K, 5, J) :- .

unifichiamo dunque K con 3 (dato che X è legato a 3): il goal corrente diviene a₂(3, 5, J). Supponiamo di percorrere il database, trovare una postcondizione che realizza questa unificazione e tentare di verificare i goal precondizione.

Che accade se ciò non ha successo? Non siamo riusciti a rendere vero a2; a questo punto, se esiste un'altra regola che ha a₂ come postcondizione:

a₁(3, W) :- .

a₁(4, W) :- .

a₂(K, 5, J) :- .

a₂(K, 7, J) :- .

dovremo riprovare (redo) a₂; in tal caso, X non viene liberata, perché X ha trovato un legame nella dimostrazione precedente, legame che viene ereditato dal goal di maggiore profondità. Quindi in a₂ K rimane legata al valore 3.

Che dire d'altra parte della variabile Z che era stata legata al valore 5? Essa viene liberata, e giacché si è trovata un'altra postcondizione per a₂(3, Z, K), viene legata al nuovo valore, 7. Di fatto, quindi, quando si effettua un redo, devono essere liberate solo le variabili che sono state legate durante il processo di dimostrazione del goal corrente (a₂) e che non erano state già legate in precedenza (Z nell'esempio). Se ci fosse una ulteriore regola (K₁, K₂, K₃ variabili):

a₁(3, W) :- .

a₁(4, W) :- .

a₂(K, 5, J) :- .

a₂(K, 7, J) :- .

a₂(K₁, K₂, K₃) :- .

K₁ risulterebbe legato al valore 3 per ereditarietà; il nuovo goal corrente diverrebbe a₂(3, K₂, K₃).

Intervento del backtracking. La verifica di a₂(X, Z, K) può avere n possibilità; se tutte falliscono, si torna indietro (backtracking), verificando il goal precedente. Si avrà cioè un redo sul goal a₁.

X dev'essere liberata? La risposta a questa domanda, lo ricordiamo, dipende dal momento in cui si è legata. Se X si è legata nell'ultimo processo di dimostrazione del goal corrente, viene liberata, altrimenti no. Nel caso specifico, il goal corrente è di nuovo a₁ e X dev'essere liberato, perché il suo binding (al valore 3) era stato determinato proprio da a₁, che è goal corrente. Se X fosse stata ereditata su un binding su b₁ (per esempio), non sarebbe stata liberata. Unifichiamo dunque a₁ con la seconda regola:

a₁(4, W) :- .

realizzando l'unificazione di variabile X = 4. Si ritorna nuovamente ad a₂, con un bind differente.

Si ha dunque una serie di avanzamenti e di backtracking tra i vari goal che sono precondizioni di b₁, in accordo alla strategia goal-driven in profondità seguita dal MI del Prolog. Qualora, una volta tornati sul goal a₁, non si avessero più alternative di unificazione per il medesimo, il predicato b₁ :- a₁, a₂, ., a_n risulterebbe fallito e si passerebbe al predicato successivo (redo su b₁):

b₁ :- c₁, c₂, ., c_m

Come funziona il cut? Supponiamo che il predicato su b₁ che era oggetto dell'esempio precedente si presenti nella forma:

b₁ :- a₁, a₂, ., a_k-1, !, a_k, ., a_n

con l'operatore ! nel bel mezzo delle precondizioni, fra la precondizione a_k-1 e la precondizione a_k. Il cut altera il comportamento del MI solo dal momento in cui viene intercettato. Quindi, il ciclo di avanzamento - backtracking per b₁ procede normalmente al momento dell'attivazione di b₁. Verrà presto o tardi il momento in cui dovremo dimostrare il goal !.

La prima volta che lo si incontra, il cut viene assimilato ad un goal che ha successo. Il cut viene quindi in pratica semplicemente scavalcato alla prima occorrenza, senza modificare i binding delle variabili né la loro ereditarietà tra predicati conseguenti in una congiunzione, così come illustrato negli esempi di questa lezione.

Andando avanti nel processo di dimostrazione, supponiamo che, ad un certo punto, subentri l'esigenza di effettuare un backtracking tra a_k e a_k-1.

In condizioni normali, ciò porterebbe alla ricerca di alternative possibili (redo) per a_k-1. In presenza del cut, invece, il MI non solo nega la possibilità del backtracking, ma fa fallire di colpo il goal b₁, e questo vale non soltanto per la regola corrente, ma per tutte le regole che prevedono b₁ come postcondizione. Quindi fallisce non solo la regola b₁ :- a₁, a₂, ., a_n in cui figura il cut, ma anche le regole b₁ :- c₁, c₂, ., c_m e b₁ :- d₁, d₂, ., d_s.

L'uso del cut è generalmente sconsigliato per chi approccia la programmazione logica, per il semplice motivo che, snaturando il normale funzionamento del MI, contraddice i principi stessi della programmazione logica. Da un punto di vista operativo, il cut 'costringe' il programmatore a preoccuparsi anche del funzionamento del MI invece di concentrarsi sulla pura e semplice formalizzazione del problema, il che è concettualmente errato.

Inoltre gli operatori extralogici rimettono in discussione i requisiti di coerenza e completezza del SF. Ad esempio il cut taglia l'albero di ricerca delle soluzioni. Non è facile prevedere l'effetto di questo taglio; potrebbe potare un ramo infinito che non contiene soluzioni, a tutto vantaggio della decidibilità; ma potrebbe anche tagliare via un ramo in cui è presente una soluzione del problema, rendendo quindi non completo un sistema che in origine lo era. Un sistema in cui viene usato il cut quindi rimane coerente, ma può perdere l'eventuale completezza iniziale.

Questo aspetto può essere considerato anche sotto un altro punto di vista: l'ordine in cui vengono scritte le regole è ininfluente nel Prolog, o meglio, incide soltanto sull'ordine con cui vengono trovate le soluzioni. Il cut invece fa sì che tale ordine diventi importante; se 3 regole permettono la verifica del predicato b₁, e inseriamo un cut nella prima di esse, è possibile che non siano mai verificate la seconda e la terza, che se verificate potrebbero portare a trovare delle soluzioni valide; se lo inseriamo nella seconda, potremmo non verificare mai la terza.

Una ulteriore osservazione: combinando opportunamente gli operatori extralogici, è possibile riprodurre il funzionamento dei cicli iterativi della programmazione classica (FOR, WHILE..DO eccetera). Questo è svantaggioso dal punto di vista didattico, poiché tende a gettare un ponte fra due modi di programmare del tutto diversi e che tali devono essere considerati.

La semantica del 'cut rosso' Riconsideriamo la regola:

b₁ :- a₁, a₂, ., a_k-1, !, a_k, ., a_n

Supponiamo che le soluzioni che possono rendere vera la congiunzione a₁, a₂, ., a_k-1 (ovvero dei predicati che si incontrano prima del cut) siano n. Il cut viene incontrato dopo che è stata trovata la prima di tali soluzioni. Dal momento che chi usa il Prolog non è tenuto a ragionare sull'ordine in cui devono essere inserite le regole, quella che viene trovata è una qualsiasi dell'insieme delle soluzioni.

Il cut si introduce nel caso in cui sappiamo per certo che tutte le soluzioni sono assoggettate alla verità di a₁, a₂, ., a_k-1. Trovata dunque una qualsiasi sostituzione (fra le n possibili) che renda vera la congiunzione a₁, a₂, ., a_k-1, proviamo, con la medesima, a verificare il predicato successivo (a_k): se non ci riusciamo, possiamo ritenere senz'altro fallito il goal b₁ e abbandonare di conseguenza il processo di ricerca.

Questo perché siamo sicuri che, una volta resa vera la congiunzione a₁, a₂, ., a_k-1 mediante una soluzione qualunque, la soluzione al problema o esiste (con la determinazione trovata per a₁, a₂, ., a_k-1, più un'ulteriore determinazione per a_k, ., a_n), oppure non esiste (siamo sicuri che il backtracking, la ricerca di un'alternativa per a₁, a₂, ., a_k-1, non porterebbe ad una soluzione valida al problema).

In generale l'esito del cut è imprevedibile, e il suo uso deve essere considerato pericoloso. Esistono comunque anche situazioni in cui l'impiego del cut si rivela opportuno. Quella che è stata definita nei paragrafi precedenti è la semantica del cosiddetto 'cut rosso': quando viene messo fra le precondizioni di una regola, obbliga ad uno sforzo significativo per attribuire un significato al suo uso. In questo caso non è conveniente utilizzarlo (semaforo 'rosso'); esistono situazioni in cui, viceversa, è molto facile fornire tale interpretazione ('cut verde', di cui vediamo immediatamente un esempio), e situazioni di difficoltà intermedia ('cut giallo').

Un esempio di 'cut verde'. Consideriamo la funzione booleana member. Abbiamo visto che essa è definita dall'insieme delle due regole:

member(X, [X|T]).

member(X, [Y|T]) :-

member(X,T).

Poniamoci ora la domanda: questa funzione corrisponde esattamente al concetto di appartenenza di un oggetto ad un insieme? La risposta è negativa. Infatti, il problema classico dell'appartenenza ad un insieme prevede una sola risposta (l'oggetto o appartiene all'insieme, o non vi appartiene). Il Prolog invece, ad una query del tipo

?-member(1, [2,1,3,1,4]).

fornirebbe due soluzioni[4], dal momento che l'elemento 1 occorre due volte nella lista in ingresso. È evidente quindi che la funzione member così come è stata introdotta non è perfettamente isomorfa al concetto logico che vorrebbe esprimere. Con il cut possiamo facilmente eliminare il difetto di forma.

In particolare, la prima regola afferma che un elemento appartiene ad una lista se coincide con il suo primo elemento. La seconda afferma che vi appartiene se appartiene alla sua coda. La query proposta non unifica con la prima regola, e unifica con la seconda, con l'unificazione X = 2, Y = [1,3,1,4]. Il goal corrente diviene:

member(1, [1,3,1,4])

Essendo possibile l'unificazione con la prima regola, il MI si ferma e fornisce una risposta affermativa. Inserendo il punto e virgola, si effettua un redo del goal corrente, liberando tutte le unificazioni realizzate nell'ultimo step. Questo redo è indesiderato, e può essere evitato introducendo un cut al posto giusto. Osserviamo infatti che la prima regola può essere anche scritta come:

member(X, [X|T]) :- true.

Modifichiamo la regola come segue:

member(X, [X|T]) :- !.

Cosa significa questa scrittura? Una volta giunti al goal member(1, [1,3,1,4]), in conseguenza dell'unificazione con la prima regola, il goal corrente diviene il cut. Il cut ha sempre successo la prima volta che si incontra, e il MI risponde affermativamente (yes). Il backtracking sul cut (punto e virgola) sospende di colpo il MI, abortendo il processo di ricerca, e così, correttamente, viene fornita una sola risposta.

ANCORA SUL PROBLEMA DEL COMMESSO VIAGGIATORE. Due lezioni fa abbiamo introdotto il predicato collegamento che, aggiunto alla KB iniziale del commesso viaggiatore:

coll1(na, rm, 220).

coll1(rm, fi, 200).

coll1(fi, bo, 100).

coll1(na, sa, 60).

coll1(sa, rm, 280).

coll(X, Y, C) :-

coll1(X, Y, C).

coll(X, Y, C) :-

coll1(Y, X, C).

consente di determinare tutti i cammini che uniscono due città assegnate.

collegamento(Ci, Cf, Lp, [Ci, Cf], C2) :-

coll(Ci, Cf, C2),

not member(Cf, Lp).

collegamento(Ci, Cf, Lp, [Cint| L1c], C) :-          

coll(Ci, Cint, C1),

not member(Cint, Lp),

collegamento(Cint, Cf, [Ci|Lp], L1c, C2),

C is C1+C2.

Lp è la lista delle città proibite, che viene arricchita aggiungendovi di volta in volta ogni nuova città che entra a far parte del cammino-soluzione. In tal modo evitiamo che una stessa città compaia due volte nel cammino.

La formalizzazione così trovata è corretta? Avviamo l'interprete Prolog e facciamo qualche prova.

?- ['c:cammino.pl'].

Per verificare che sia stata incorporata la KB giusta, si può usare il predicato listing che mostra sullo schermo la KB dopo l'operazione di 'compilazione', ovvero la sostituzione dei nomi delle variabili operata dall'interprete Prolog (cfr. lezione del 5/4).

Digitiamo ora il comando:

?- collegamento(na, rm, [], L, C).

Stiamo in pratica verificando la chiusura della ricorsione, ovvero se introducendo in ingresso il collegamento tra due città adiacenti viene data una risposta corretta. In effetti, viene data una prima soluzione esatta:

C = 220

L = [na, rm]

che è il risultato di una unificazione (molto semplice da interpretare) con il primo predicato collegamento, ma, dopo il punto e virgola, anche una seconda - ed ultima - soluzione, piuttosto curiosa:

C = 340

L = [sa, sa, rm]

Cerchiamo di capirne il motivo. In linea di principio, è possibile arrivarci considerando passo passo il ciclo di avanzamenti di livello e backtracking innescato dal MI. Effettuiamo quindi un esame passo passo del lavoro svolto dal MI tramite l'istruzione di trace, iniziando dalla prima soluzione (quella giusta).

Call: ( 6) collegamento(na, rm, [], G1108, G1112) ? creep

Mediante l'unificazione Ci = na, Cf = rm, il goal corrente diviene coll(na,rm,G1112). Goal che, ovviamente, ha successo.

Call: ( 7) coll(na, rm, G1112) ? creep

Call: ( 8) coll1(na, rm, G1112) ? creep

Exit: ( 8) coll1(na, rm, 220) ? creep

Exit: ( 7) coll(na, rm, 220) ? creep

Adesso, il MI deve verificare che rm non appartenga alla lista vuota (not member(Cf, Lp)). Questo goal deve fallire, ed è proprio ciò che accade.

Call: ( 7) not member(rm, []) ? creep

Call: ( 8) member(rm, []) ? creep

Fail: ( 8) member(rm, []) ? creep

^ Exit: ( 7) not member(rm, []) ? creep

Il simbolo ^ compare quando si intende verificare un predicato preceduto dall'operatore not. In tal caso, si verifica dapprima il predicato affermato (senza il not), e poi si nega il risultato.

Exit: ( 6) collegamento(na, rm, [], [na, rm], 220) ? creep

e quindi si esce con successo ottenendo la prima soluzione.

C = 220

L = [na, rm] ;

Premendo adesso il punto e virgola, si scatena il meccanismo del backtracking avente come obbiettivo la ricerca di una nuova soluzione; il predicato query viene unificato con la seconda regola collegamento. Le variabili L e C, che si erano precedentemente unificate ai valori [na, rm] e 220 rispettivamente, vengono liberate in occasione del backtracking. Si ha innanzitutto:

Redo: ( 8) coll1(na, rm, G1112) ? creep

Infatti, se l'ultimo predicato del precedente trace (collegamento(na, rm, [], [na, rm], 220)) si dà per fallito, occorre effettuare un redo per trovare soluzioni alternative alle precedenti precondizioni. Poiché per member, al livello 8, non esistono soluzioni alternative (si tratta di una versione 'corretta' della funzione membro: un elemento o appartiene ad un insieme, o no), il backtracking risale a Exit: ( 7) coll(na, rm, 220), quindi a Exit: ( 8) coll1(na, rm, 220) (due istruzioni di uscita, per le quali non è previsto il backtracking) per giungere infine al predicato coll1(na, rm, G1112), su cui può fare il backtracking. Il MI si domanda cioè se esiste un'alternativa per verificare tale predicato. La risposta è negativa.

Fail: ( 8) coll1(na, rm, G1112) ? creep

Si ha quindi il backtracking sul precedente predicato, coll; un altro predicato che ammette coll come postcondizione esiste (è la regola coll(X, Y, C) :- coll1(Y, X, C).)

Redo: ( 7) coll(na, rm, G1112) ? creep

Call: ( 8) coll1(rm, na, G1112) ? creep

Fail: ( 8) coll1(rm, na, G1112) ? creep

Redo: ( 7) coll(na, rm, G1112) ? creep

Fail: ( 7) coll(na, rm, G1112) ? creep

Avendo esaurito ogni possibilità di fare backtracking su coll, il backtrack si estende alla clausola collegamento(na, rm, [], G1108, G1112) che compariva come goal nella prima riga del trace precedente.

Redo: ( 6) collegamento(na, rm, [], G1108, G1112) ? creep

Una diversa unificazione per collegamento è possibile: con la regola successiva alla chiusura della ricorsione. Si noti che all'atto di reimpostare il goal collegamento abbiamo liberato le variabili che si erano unificate nell'ultimo passo, ovvero il cammino parziale ed il suo costo. Occorre adesso dimostrare il goal:

Call: ( 7) coll(na, G1476, L364) ? creep

Da notare che la variabile Cint (che rappresenta una città direttamente collegata con Napoli) è libera. La prima che si trova nel database è Roma.

Call: ( 8) coll1(na, G1476, L364) ? creep

Exit: ( 8) coll1(na, rm, 220) ? creep

Exit: ( 7) coll1(na, rm, 220) ? creep

A questo punto il Mi verifica che Roma non sia membro della lista delle città proibite, e si prosegue. Dovrebbe essere chiaro comunque che prendere in considerazione il funzionamento del MI per indagare la causa di un output errato è, il più delle volte, a dir poco frustrante. Si hanno decine di chiamate ricorsive e le variabili vengono continuamente legate e liberate. Basti pensare che il trace della seconda soluzione occupa oltre 180 linee di codice!

Non ci resta quindi che sospendere il trace e provare a ragionare in modo diverso. È da rilevare che la risposta:

C = 340

L = [sa, sa, rm]

è, sì, espressa in modo errato, perché Napoli non vi compare come città iniziale, e Salerno vi compare due volte; tuttavia è semanticamente corretta: il Prolog in pratica ha trovato il percorso Napoli-Salerno-Roma, il cui costo è 60 + 280 = 340. Per esserne sicuri, diamo una diversa query:

?- collegamento(na, bo, [], L, C).

Le due soluzioni trovate dal Prolog:

C = 520

L = [rm, fi, fi, bo] ; (trova il percorso: na, rm, fi, bo, di costo 520, corretto)

C = 640

L = [sa, rm, fi, fi, bo] (trova il percorso: na, sa, rm, fi, bo, di costo 640, corretto)

sono espresse in modo non conforme alle aspettative (la città iniziale (Napoli) viene omessa, e Firenze compare due volte) ma concettualmente esatte; prova ne sia che i costi vengono calcolati correttamente. Dunque, le regole del nostro SF sono sostanzialmente ben scritte; una piccola modifica al SF dovrebbe essere sufficiente ad eliminare il problema.

Una possibilità è la seguente: nella regola

collegamento(Ci, Cf, Lp, [Cint| L1c], C) :- .

sostituiamo nella postcondizione Ci a Cint: si ha cioè

collegamento(Ci, Cf, Lp, [Ci| L1c], C) :-

coll(Ci, Cint, C1),

not member(Cint, Lp),

collegamento(Cint, Cf, [Ci|Lp], L1c, C2),

C is C1+C2.

Questo perché, se il 'figlio' collegamento(Cint, Cf, [Ci|Lp], L1c, C2) è in grado di trovare un percorso corretto L1c che muove tra Cint e Cf, dove Cint è una città direttamente collegata a Ci, alla lista L1c dobbiamo aggiungere Ci e non Cint se vogliamo una soluzione corretta. L'errore commesso, dunque, dipendeva dal fatto che non avevamo costruito correttamente la soluzione del problema padre a partire dalla soluzione del problema figlio, andando ad aggiungere in testa alla lista una città che il figlio aveva già trovato (anziché la città iniziale del percorso)[5].

La query precedente fornisce stavolta una risposta soddisfacente.

?- collegamento(na, bo, [], L, C).

C = 520

L = [na, rm, fi, bo] ;

C = 640

L = [na sa, rm, fi, bo]

Questo esempio riconferma che non è consigliabile cercare di seguire passo passo il funzionamento di un algoritmo ricorsivo (né mentalmente, né servendosi di strumenti automatici come il trace), quanto piuttosto entrare nell'ordine di idee della ricorsione imparando a formalizzare i problemi in un modo corretto.

Per fare qualche altro esperimento con il nostro SF, proviamo ad ingrandire la KB aggiungendo sei o sette fatti (collegamenti in neretto).

coll1(na, rm, 220).

coll1(rm, fi, 200).

coll1(fi, bo, 100).

coll1(na, sa, 60).

% coll1(sa, rm, 280).

coll1(bo, ve, 200).

coll1(ve, bl, 120).

coll1(rm, pe, 180).

coll1(pe, an, 120).

coll1(an, ve, 300).

coll1(sa, rc, 330).

coll1(rc, ba, 400).

Per maggiore realismo, eliminiamo la riga relativa al collegamento fra Salerno e Roma (basta premettere il simbolo %). Riconsultiamo la KB e poniamo le seguente query:

?- collegamento(na, rc, [], L, C).

C = 390

L = [na, sa, rc] ;

?- collegamento(na, ve, [], L, C).

C = 720

L = [na, rm, fi, bo, ve] ;

C = 820

L = [na, rm, pe, an, ve] ;

Aggiungendo un collegamento sull'Adriatico:

coll1(ba, pe, 300).

il MI genera due ulteriori percorsi fra Napoli e Reggio Calabria:

?- collegamento(na, rc, [], L, C).

C = 1840

L = [na, rm, fi, bo, ve, an, pe, ba, rc] ;

C = 1100

L = [na, rm, pe, ba, rc] ;

C = 390

L = [na, sa, rc] ;

Se però inseriamo Roma fra la lista delle città proibite, la soluzione trovata è una sola (la stessa di prima)

?- collegamento(na, rc, [rm], L, C).

C = 390

L = [na, sa, rc] ;

Inseriamo ora una query più complessa: vogliamo trovare due cammini che partono dalla stessa città ed arrivano in città diverse, ma allo stesso costo. Dobbiamo scrivere quindi:

?- collegamento(X, Y, [], L, C), collegamento(X, Z, [], L2, C).

Le prime risposte sono ovvie, e coinvolgono cammini L e L2 a due città (L, L2 non possono che essere uguali).

L2 = [na, rm]

X = na

Y = rm

Z = rm

C = 220

L = [na, rm] ;

L2 = [rm, fi]

X = rm

Y = fi

Z = fi

C = 200

L = [rm, fi] ;

eccetera. Il primo risultato significativo è:

L2 = [an, pe, rm]

X = an

Y = ve

Z = rm

C = 300

L = [an, ve] ;

Il costo dei cammini per andare da Ancona a Venezia, o da Ancona a Roma, passando per Pescara, è lo stesso (300).

La query che inseriremo ora ci permetterà di riscontrare una ulteriore imperfezione che è ancora presente nel nostro SF. Vogliamo trovare tutti i cammini che non condividono città (tutti i possibili cammini che non si intersecano su alcuna città).

?- collegamento(X, Y, [], L, C), collegamento(K, Z, [X, Y], L2, C2).

La query sembra scritta correttamente, ma i risultati lasciano a desiderare. La prima risposta è già errata (Roma compare in entrambi i tragitti).

L2 = [rm, fi]

X = na

Y = rm

Z = fi

K = rm

C = 220

L = [na, rm]

C2 = 200 ;

Per risolvere il problema, occorre modificare entrambe le regole collegamento con l'aggiunta di un medesimo predicato:

collegamento(Ci, Cf, Lp, [Ci, Cf], C2):-

coll(Ci, Cf, C2),

not member(Ci, Lp),

not member(Cf, Lp).

collegamento(Ci, Cf, Lp, [Ci| L1c], C) :-

coll(Ci, Cint, C1),

not member(Ci, Lp),

not member(Cint, Lp),

collegamento(Cint, Cf, [Ci|Lp], L1c, C2),

C is C1+C2.

Nella chiusura della ricorsione bisogna precisare che, così come Cf, nemmeno Ci deve far parte delle città proibite. Lo stesso dicasi per la seconda regola; una volta che il figlio abbia trovato un cammino L1c tra Cint e Cf, di cui Ci sicuramente non farà parte, il padre vi aggiunge in testa la città Ci, e a questo punto bisogna controllare che Ci non sia a sua volta una città proibita. In caso contrario, si verificheranno delle duplicazioni.

Riproponendo la query, si riscontrano questa volta risultati corretti:

L2 = [fi, bo]

X = na

Y = rm

Z = bo

K = fi

C = 220

L = [na, rm]

C2 = 100 ;

L2 = [fi, bo, ve]

X = na

Y = rm

Z = ve

K = fi

C = 220

L = [na, rm]

C2 = 300 ;

eccetera.

ANCORA SULLA DERIVAZIONE SIMBOLICA. Riportiamo di seguito la KB formalizzata fino a questo momento (vedi lezione del 5/4).

deriva(sin(x),cos(x),x).

deriva(cos(x),-sin(x),x).

deriva(F * G, DF * G + DG * F, X) :-

deriva(F, DF, X),

deriva(G, DG, X).

deriva(F + G, DF + DG, X) :-

deriva(F, DF, X),

deriva(G, DG, X).

Introduciamo anzitutto l'ulteriore regola: derivata del rapporto di funzioni.

deriva(F / G, (DF * G - F * DG)/(G * G), X) :-

deriva(F, DF, X),

deriva(G, DG, X).

Poniamoci ora un obbiettivo di difficoltà maggiore: realizzare la derivazione di funzioni composte. Il punto è che, trovandoci in una logica di ordine 1, X non può essere a sua volta una funzione.

Proviamo anzitutto ad esprimere anche le derivate di seno e coseno come se fossero funzioni non di variabili indipendenti, ma di altre funzioni. Quindi disabilitiamo le precedenti:

% deriva(sin(x),cos(x),x).

% deriva(cos(x),-sin(x),x).

Sostituendole con l'insieme delle tre regole:

deriva(sin(X), cos(X)*DX, Y) :-

deriva(X, DX, Y).

deriva(cos(X),-sin(X)*DX, Y) :-

deriva(X, DX, Y).

deriva(X, 1, X).

Abbiamo sfruttato il fatto che la derivazione composta può essere pensata come l'applicazione ricorsiva della derivazione semplice. Possiamo anche dire quanto segue: la derivazione semplice è la chiusura della ricorsione di un processo di derivazione composta, nel quale processo deriviamo di volta in volta considerando tutto l'argomento come la variabile rispetto alla quale derivare. La derivazione semplice che in questo caso chiude la ricorsione è la derivata di X ( = 1).

Sottoponiamo come sempre al sistema alcune query di prova:

?- deriva(sin(x), Z, x).

Z = cos(x) * 1

Le derivate semplici vengono calcolate in modo corretto, anche se il risultato non si presenta scritto molto bene. Deriviamo ora una funzione composta:

?- deriva(sin(cos(x)), Z, x).

Z = cos(cos(x)) * (- sin(x) + 1)

Risultato giusto. Proviamo ora a sottoporre al sistema contemporaneamente funzioni composte e operazioni aritmetiche su funzioni:

?- deriva(sin(cos(x)*sin(x))/sin(sin(x)), Z, x).

Anche in questo caso il calcolo fatto dal Prolog è corretto (il risultato non viene qui riportato per brevità.).

Aggiungendo poche altre regole di derivazione, potremmo con un modesto sforzo completare il nostro SF. Una sola questione rimane insoluta: la derivazione di una costante. Tale derivata è difficile da rappresentare.

Quando abbiamo formalizzato il sistema di derivazione simbolica, abbiamo deliberatamente confuso i concetti di 'variabile' Prolog e variabile matematica. L'abbiamo fatto per lo stesso motivo per cui si utilizzano gli operatori +, /, () etc. che sono già disponibili in Prolog, e non necessitano quindi di una nuova definizione. Sebbene il Prolog preveda una definizione a priori anche delle costanti numeriche, non esiste tuttavia alcun modo per identificare una variabile come appartenente ad un tipo numerico reale, visto che le variabili Prolog sono non tipate; è qui infatti che subentra la differenza fra i due concetti di 'variabile' cui si accennava prima.

La regola dovrebbe cioè avere una postcondizione del tipo:

deriva(X, 0, Y) :- .

ma non sapremmo come esprimere la precondizione ('X è costante', ovvero 'X non è una variabile'). Quindi l'unica strada (ovviamente impraticabile) sarebbe quella di scrivere tante regole di derivazione per quante sono le possibili costanti numeriche. Una soluzione al problema per la verità esiste, ma richiede l'introduzione di strumenti offerti dal Prolog che vanno al di là degli scopi che questo corso si pone.

GLI ALTRI DUE OPERATORI EXTRALOGICI: NOT, FAIL. Abbiamo in effetti già utilizzato l'operatore NOT. Proponiamo di seguito un altro esempio: definiamo un fatto che stabilisce l'uguaglianza di una variabile con sé stessa; in conseguenza, potremmo dire che la derivata di una variabile rispetto ad un'altra è nulla.

equal(X, X).

deriva(X, 0, Y) :-

not equal(X, Y).

Consideriamo un esempio aggiuntivo. Definiamo una nostra versione della funzione membro (appartenenza ad una lista), che, lo ripetiamo, è definita per default nel Prolog. Il SF riportato di seguito è provvisto anche del predicato di uguaglianza, e di un predicato 'notmembro' che è l'opposto di 'membro'. 'notmembro' è definito appunto grazie all'operatore extralogico not.

equal(X, X).

membro(X,[X|T]).

membro(X,[Y|T]):-

membro(X,T).

notmembro(X, T) :-

not membro(X, T).

L'operatore not differisce dall'omonimo operatore booleano di negazione. Si tenga presente infatti che la quantificazione delle variabili nella regola notmembro è esistenziale; tale regola risulta verificata se non esiste alcuna coppia (X, T) tale che membro(X, T) sia vera.

In altri termini, se esiste una soluzione che renda vero il predicato membro(X, T), allora notmembro risulta falsa; al primo successo per membro si esce cioè da tale predicato con un fallimento. Se invece membro risulta falsa, data la quantificazione esistenziale, è segno che devono essere state provate tutte le possibili alternative per membro(X,T) e si è appurato che non esiste alcuna coppia (X,T) che la renda vera (quindi dopo aver scatenato tutti i possibili backtracking sul predicato membro). In questo caso, notmembro è vera.

Effettuiamo il trace con la query:

?- notmembro(1, [2, 1, 3, 4]).

Call: ( 6) notmembro(1, [2, 1, 3, 4]) ? creep

La verifica del predicato che abbiamo denominato notmembro provoca l'utilizzo dell'operatore not, il quale, come già osservato, viene di fatto ignorato; si verifica membro in positivo per poi negare il risultato.

^ Call: ( 7) not membro(1, [2, 1, 3, 4]) ? creep

Call: ( 8) membro(1, [2, 1, 3, 4]) ? creep

Call: ( 9) membro(1, [1, 3, 4]) ? creep

Exit: ( 9) membro(1, [1, 3, 4]) ? creep

Exit: ( 8) membro(1, [2, 1, 3, 4]) ? creep

Usciamo dunque con successo dalla funzione membro. Poiché 1 appartiene alla lista in input, ci aspettiamo di uscire con un fallimento da notmembro (si esce la prima volta che il goal viene realizzato).

Call: ( 8) fail? creep

Fail: ( 8) fail ? creep

^ Fail: ( 7) not membro(1, [2, 1, 3, 4]) ? creep

Redo: ( 6) notmembro(1, [2, 1, 3, 4]) ? creep

Fail: ( 6) notmembro(1, [2, 1, 3, 4]) ? creep

Consideriamo viceversa una query con esito positivo:

?- notmembro(1, [2, 3]).

Call: ( 6) notmembro(1, [2, 3]) ? creep

^ Call: ( 7) not membro(1, [2, 3]) ? creep

Call: ( 8) membro(1, [2, 3]) ? creep

Call: ( 9) membro(1, [3]) ? creep

Call: ( 10) membro(1, []) ? creep

Fail: ( 10) membro(1, []) ? creep

Redo: ( 9) membro(1, [3]) ? creep

Fail: ( 9) membro(1, [3]) ? creep

Redo: ( 8) membro(1, [2, 3]) ? creep

Fail: ( 8) membro(1, [2, 3]) ? creep

^ Exit: ( 7) not membro(1, [2, 3]) ? creep

Exit: ( 6) notmembro(1, [2, 3]) ? creep

Dopo tutti i possibili backtracking, usciamo da membro con un fallimento e quindi da notmembro con un successo.

L'operatore FAIL è tale che, una volta che sia stato raggiunto, determina sempre un fallimento. È interessante e utile osservare che not può essere definito a partire dagli altri due operatori extralogici; in particolare, il not si ottiene come l'insieme dei due predicati (una regola ed un fatto):

not(A) :-

A, !, fail.

not(A).

Nel tentativo di unificare infatti not(A), scateniamo il goal A; trovata la prima soluzione per A, percorriamo il cut (vero), quindi il fail, che provoca backtracking sul cut, e di conseguenza il predicato postcondizione fallisce (in assoluto): not(A) è falso.

Se invece A non ha soluzioni (cosa che possiamo accertare solo dopo aver provato tutte le alternative; non esiste alcuna variabile interna ad A che renda vero tale predicato) usciamo da A; facciamo backtracking sulla postcondizione not(A), incontrando una soluzione alternativa per not(A) che è un fatto, quindi sempre vero: not(A) è vera.

Si conclude qui la parte del corso sul Prolog.

LE RETI NEURALI ARTIFICIALI. Hanno l'obbiettivo di realizzare l'apprendimento attraverso la TESI FORTE dell'intelligenza artificiale. Si cerca di realizzare un sistema in grado di risolvere problemi su di un determinato dominio D, senza che ci sia alcuna conoscenza pregressa su tale dominio. O meglio, tale conoscenza esiste, ma è formalizzata in un modo totalmente diverso - e molto più semplice - rispetto a quanto accadeva nei sistemi considerati in precedenza.

Nella tesi debole, il problema principale era dato dal trasferimento al sistema della conoscenza in possesso degli esperti attraverso una opportuna formalizzazione. Il punto critico sta nel fatto che gli esperti del problema non sono necessariamente idonei ad esprimerne la conoscenza attraverso opportune strutture dati; questo è compito degli informatici, che possono essere figure professionali distinte dagli esperti. Tale limitazione viene a cadere nei sistemi rispondenti alla cosiddetta tesi forte. In questo caso abbiamo un sistema (rete neurale, algoritmo genetico, algoritmo deterministico, algoritmo del cosiddetto soft computing .) che immaginiamo racchiuso dentro una 'scatola' (v. figura sulla destra); essa riceve in ingresso un vettore x ad n componenti e tira fuori un vettore di uscita y ad m componenti. La 'scatola' fissa una corrispondenza tra i due vettori; in altre parole, calcola m funzioni f₁, ., f_m, ciascuna applicata sull'intero vettore d'ingresso.

Il sistema considerato lavora in due distinte modalità:

apprendimento

operativa

Nella modalità di apprendimento, abbiamo a disposizione per ipotesi l'insieme TS (training set), cioè un insieme di coppie di vettori (x_i, y_i).

Non è noto in partenza l'algoritmo che porta dal generico vettore in ingresso x alla relativa uscita y; proprio per questo motivo, il sistema artificiale si pone l'obbiettivo di acquisire una conoscenza che viene fornita per esempi (non a caso queste metodiche vengono dette di learning for examples). Il vettore x_i rappresenta cioè un 'esempio di ingresso' fornito alla rete e y_i è il corrispondente vettore di uscita; è l'uscita ideale (o 'uscita attesa'), quella che ci aspetteremmo che il sistema restituisca a fronte dell'ingresso considerato. Una generica coppia appartenente al TS serve alla rete per acquisire conoscenza.

Perché il TS sia di qualche utilità, l'insieme degli esempi dev'essere sufficientemente ampio da coprire una significativa casistica. Il numero degli esempi che potrebbero essere forniti al sistema sono virtualmente in numero infinito, quindi è ovvio che solo una certa parte dei possibili esempi verrà data in input al sistema; ma questi non devono essere nemmeno in numero troppo elevato, per non appesantire la fase di apprendimento.

Nella fase operativa la rete, avendo terminato l'apprendimento, dovrà operare in accordo alla conoscenza acquisita. Essa verrà quindi alimentata con un generico vettore d'ingresso x. Sulla base del TS, la rete fornirà un vettore y:

y = f(x)

Il vettore x non sarà, verosimilmente, uno degli elementi del TS. Il TS estrapola un modello (a partire dagli esempi forniti) e 'generalizza', proponendo un'uscita y la quale, se il TS è stato progetto in modo oculato sarà ragionevolmente vicina al valore che ci si aspetterebbe (dipende in un certo senso dalla 'distanza' tra l'ingresso x fornito e gli ingressi presenti nel TS). Si dice che il sistema effettua, sulla base della conoscenza estrapolata dagli esempi, una previsione.

Nel prosieguo faremo riferimento in particolare a quanto avviene nelle reti neurali. Durante la fase di apprendimento, sia x_i che y_i sono evidentemente degli ingressi per la rete. La conoscenza così acquisita si materializza in una serie di parametri o, per dire meglio, di pesi (possono essere interpretati anche come gradi di libertà per la rete). La y = f(x) realizzata dal sistema è una funzione incognita; viene 'costruita' in modo approssimato durante la fase di apprendimento, proprio grazie ad una opportuna taratura di questi pesi o parametri. La forma analitica della funzione f è piuttosto semplice (generalmente di tipo lineare); per contro, essa può dipendere da un numero elevatissimo di parametri. Al cambiare del valore anche di uno solo dei parametri (li indicheremo nel seguito come P soprasegnato) cambia il valore di y restituito a partire da un ingresso x.

L'algoritmo di apprendimento, che ha a disposizione un certo numero di parametri liberi, inizialmente vi attribuisce dei valori del tutto arbitrari (è preferibile, ma non obbligatorio, che non siano tutti uguali; ad esempio, non tutti nulli). Dopodiché la rete riceve la coppia di ingresso (x_i, y_i)[7], e calcola la funzione:

Essa quindi prende il vettore x_i e calcola il vettore di uscita che risulta a partire dalla configurazione iniziale dei pesi. È probabile che il valore y_rⁱ così calcolato sia differente da quello y_i presentato in ingresso (uscita attesa). A questo punto, la rete modifica i parametri in modo da avvicinare i due valori di y, ovvero da ridurre lo scarto y_rⁱ - y_i. Si passa dunque ad una nuova configurazione dei pesi:

Anche se la configurazione iniziale dei pesi dà luogo ad una funzione lontanissima da quella reale, a patto che il numero dei parametri sia sufficientemente elevato, dopo un certo numero di passi si raggiunge l'obbiettivo di approssimare con buona accuratezza la funzione reale, ovvero di ottenere una funzione quanto più possibile fedele alla f reale. Il meccanismo è congruente con il concetto matematico di trasformata (es. trasformazione di Fourier); ogni funzione può essere ottenuta a partire da funzioni più semplici quali seni, coseni o polinomi, purché si utilizzi un numero sufficiente di tali funzioni componenti.

L'algoritmo di apprendimento tipico di una rete neurale artificiale è composto di poche linee di codice. L'approssimazione più usata, come detto, è quella lineare, e l'errore viene tipicamente minimizzato in media quadratica. Tuttavia, la computazione dell'apprendimento è meno banale di quanto sembrerebbe ad una prima analisi; infatti, in corrispondenza di ogni nuovo ingresso (x_i, y_i) dev'essere minimizzato non solo l'errore y_rⁱ - y_i relativo all'ingresso attuale, ma anche tutti gli errori precedenti! Se ci limitassimo a tarare i pesi per la sola coppia d'ingresso corrente rischieremmo di rovinare il modello costruito fino a quel momento, che teneva conto anche degli esempi forniti in precedenza.

Ogni nuovo esempio serve quindi a migliorare le prestazioni della rete con riferimento all'esempio stesso, ma ciò deve accadere compatibilmente col vincolo di non deteriorare le prestazioni relative agli altri esempi.

L'aggiornamento dei pesi non deve avvenire necessariamente su ogni singolo esempio del TS; una differente (e più comune) strategia consistere nel memorizzare l'intero TS senza variare i pesi; alla fine si considerano tutte le uscite y_r memorizzate e si modificano in un solo passo tutti i parametri. Il procedimento può quindi essere iterato. Di fatto, questo approccio è più comune. L'algoritmo di apprendimento visita tipicamente il TS più volte; ogni visita viene detta anche epoca. L'apprendimento non si esaurisce in un'unica epoca; sono previste più epoche, e dopo (o, secondo un'altra disciplina, 'durante') ogni epoca la rete aggiorna i pesi.

L'approccio di aggiornamento esempio per esempio è rapido, ma non ricorre ad una visione d'insieme del problema, come invece fa l'approccio ad epoche, più lento ma più 'prudente' ed accurato.

DIMENSIONAMENTO DEGLI INSIEMI DI PESI E DI ESEMPI. È intuitivo che l'errore diminuisca all'aumentare del numero di pesi. Utilizzando i pesi presenti, la rete minimizza l'errore; potrebbe essere possibile addirittura ridurre a zero l'errore sul TS. Ad esempio, un insieme di punti può essere rappresentato in maniera più o meno soddisfacente da una sola retta (due parametri: intercetta, coefficiente angolare), ma l'approssimazione migliora già con due rette (quattro parametri: due intercette, due coefficienti angolari)[8]. Aumentare la cardinalità dell'insieme dei pesi rende maggiore la possibilità di ridurre l'errore sul TS a valle del processo di apprendimento; se l'insieme dei pesi è piccolo, potremmo incontrare difficoltà a diminuire l'errore oltre un certo valore.

Va ricordato tuttavia che il TS non è "la realtà", ma ne rappresenta solo una porzione. In questo caso bisognerebbe valutare il grado di significatività statistica del TS (un concetto isomorfo alla completezza dei SF). Il TS deve cioè essere ben rappresentativo del 'mondo' cui facciamo riferimento. L'algoritmo potrebbe consistere banalmente in un database in cui andiamo a sistemare le uscite corrispondenti ad ogni ingresso presentato come esempio. Ovviamente la rete non sarebbe capace di trovare la risposta relativa ad ingressi che non conosce (fase di GENERALIZZAZIONE); il sistema vanterebbe dunque un errore nullo sul TS ma risulterebbe del tutto inutile come ambiente di AI.

Il numero di gradi di libertà è legato alla dimensione della rete. Le reti neurali sono composte di componenti elementari, opportunamente interconnesse, detti neuroni, e ogni neurone mette in gioco un certo numero di pesi. All'aumentare del numero di neuroni aumentano la dimensione della rete ed il numero di pesi. La dimensione della rete neurale va interpretata come un parametro di progetto; dobbiamo imparare a sceglierla nel modo migliore, dal momento che se la rete ha a disposizione un maggior numero di pesi è in grado di apprendere situazioni maggiormente complesse. Un ristretto numero di pesi genera una macchina dal limitato apprendimento.

Anche il numero di esempi da sottoporre all'attenzione del sistema va scelto accuratamente. Come vedremo, non solo un TS troppo limitato ma anche un TS troppo ampio può dar luogo a problemi.

Entrambi i parametri considerati - cardinalità di TS e dell'insieme dei pesi - possono contribuire all'accuratezza del modello. Ciononostante, contrariamente alle aspettative, non c'è alcuna diretta relazione tra essi. Il numero ottimale di pesi infatti dipende esclusivamente dalla funzione che si vuole approssimare. Supponiamo di avere un numero elevatissimo di campioni, e che la funzione incognita risponda ad un modello lineare. In questo caso sarebbe sufficiente un numero di pesi pari a due per la dimensione del vettore di uscita (2*m). Per meglio comprendere, consideriamo il caso bidimensionale: abbiamo p.e. un milione di punti nel piano e la funzione incognita è lineare (una retta del piano); al sistema sono sufficiente due soli pesi (coefficiente angolare ed intercetta della retta) per descrivere la funzione reale.

All'opposto, se la distribuzione dei punti non corrisponde ad un modello lineare, e risulta anzi variamente articolata come nell'esempio a sinistra, il numero di pesi di cui abbiamo bisogno cresce in modo significativo, grande o piccolo che sia l'insieme TS. Quindi il numero di pesi necessari ad avere una buona approssimazione non dipende dalla dimensione del TS ma dalla forma della funzione incognita.

Generalmente i due fattori di cui si è discusso vengono regolati 'sul campo': si parte da un TS piccolo e da una limitata dimensione per la rete e si cerca di capire, mediante appositi indicatori di funzionamento, come procede la rete. Se mostra di non funzionare bene si cerca di capire da quale dei due aspetti summenzionati dipende e si agisce di conseguenza.

Il principale problema pratico dell'utilizzo delle reti neurali consiste nella raccolta degli esempi. Può essere necessario un notevole dispendio di tempo e altre risorse per costruire un TS significativo. Supponiamo ad esempio di volere un sistema che valuti le concentrazioni di agenti inquinanti in un ambiente cittadino. Poiché il fenomeno dipende da moltissimi parametri fisici (temperatura, umidità, direzione del vento, intensità del traffico automobilistico ecc) è necessario raccogliere molti dati e su di un tempo molto ampio perché il sistema sia in grado di fornire stime affidabili.

Abbiamo raffigurato a sinistra una curva di apprendimento, che serve per monitorare il processo di apprendimento. Sull'ordinata presenta l'errore (tipicamente l'errore globale sull'intero TS) e sull'ascissa il numero di epoche. Dopo la prima epoca, l'algoritmo calcola una prima istanza dell'insieme dei pesi. Il TS si ripresenta quindi all'algoritmo, che dopo la seconda regola ricava un nuovo insieme di pesi, in corrispondenza del quale l'errore sarà probabilmente più basso. La curva riporta l'errore sull'intero TS commesso all'avanzare del processo di apprendimento, avanzamento misurato come numero n di epoche. Un algoritmo ben fatto fa sì che l'errore diminuisca progressivamente all'aumentare di n. Come si vede in figura, durante le prime epoche si registrano grossi miglioramenti: l'errore migliora rapidamente, ma da un certo punto in poi la rete tende ad un certo errore (può essere anche l'errore nullo; ciò come detto accade se il numero di pesi è abbastanza grande); la derivata della curva tende a zero e miglioramenti del sistema costano di più in termini computazionali.

Questo avviene per un fissato TS ed una fissata dimensione e tipologia della rete. Un TS inizialmente piccolo ed una rete piccola possono essere successivamente ampliati in base alle esigenze. Quando è necessario arrestare il processo di apprendimento? Allo stato delle cose vengono in mente un paio di risposte. Ci potremmo fermare quando, nel passare dal numero di epoche i a i+1, ovvero a fronte di una ulteriore epoca, la variazione di errore che si registra (misurabile a partire dalla derivata della curva) è inferiore ad una certa soglia. In alternativa, ci si può fermare quando si scende al di sotto di un fissato errore (e non di una fissata variazione).

Nessuno dei due criteri offre a priori una garanzia di affidabilità per il sistema, perché ovviamente tutto dipende da quanto il TS sia rappresentativo del mondo reale. Per questo motivo, all'insieme TS se ne affianca un altro, il TTS (TRAINING TEST SET). I campioni disponibili vengono ripartiti tra i due insiemi: se p.e. abbiamo a disposizione 10.000 campioni, potremmo sceglierne 8.000 per costruire il TS e gli altri 2.000 per il TTS. La selezione dei due insiemi (ovvero quali campioni debbano andare a finire in ciascuno dei due) deve essere fatta a caso.

Come indica l'acronimo, il TTS serve per fare una valutazione del processo di apprendimento in corso di esecuzione. Per ogni epoca si valuta non soltanto l'errore sul TS, ma anche quello sul TTS. Di conseguenza nel diagramma precedentemente citato avremo due curve di errore (vedi grafico a destra). Generalmente l'errore sul TTS è più grande, dato che la rete minimizza l'errore sul solo TS.

A regime, per l'errore sul TTS sono possibili tre alternative. L'errore può stabilizzarsi su di un errore diverso da quello del TS, o può finire col coincidere con esso, o può divergere. Consideriamo separatamente le tre possibilità.

Convergenza dei due errori: è il segno che l'insieme dei campioni del TTS ha una copertura statistica uguale a quella dei campioni del TS. I due insiemi sono statisticamente in accordo tra di loro. Esempio pratico: misuriamo l'altezza media di una classe di studenti napoletani al V anno di ingegneria informatica. Poi misuriamo l'altezza media di un'altra classe, sempre una V classe napoletana e della stessa facoltà. È verosimile che le due misure medie coincidano. La misura infatti è 'statisticamente polarizzata' dalla situazione contingente; essendo la stessa nei due casi, avremo un uguale risultato.

La rete commette un errore mediamente più alto sul TTS. In tal caso, il TTS non rappresenta adeguatamente il TS.

L'errore sul TTS prende ad aumentare. Questa è la situazione più preoccupante, ma anche la più frequente, e inoltre, a dispetto delle apparenze, quella che fornisce più informazione. Possiamo affermare infatti che il processo di apprendimento va arrestato quando si raggiunge il minimo della curva di errore sul TTS (vedi figura pagina successiva) e non in base ai criteri precedentemente menzionati, basati sull'errore per il TS.

L'algoritmo di apprendimento è studiato in modo che l'errore sul TS diminuisca all'infinito; ma da un certo punto in poi, la rete si 'specializza troppo'; tende, sì, a fornire un errore 0 sui campioni del TS, ma questi ultimi sono sempre gli stessi; nella realtà dei fatti essa viene sollecitata anche da altri campioni, per esempio quelli sul TTS. La rete quindi sta perdendo le sue capacità di generalizzazione, consistenti nel rendere l'errore basso su campioni che non appartengono al TS.

La distanza fra il minimo della TTS (nel caso peggiore) e il minimo della TS è un valore interessante; se è piccola, è indice del buon funzionamento del sistema; se invece è grande, con riferimento alla configurazione assegnata (TTS; TS; dimensione di rete) possiamo affermare con ottima probabilità di dire il vero che il TS non è ben scelto. Se ad esempio nel punto di minimo si ha per il TTS una percentuale di previsione esatta dell'88% e per il TS del 98%, la rete su due insiemi commette errori significativamente differenti (10 punti percentuali); stiamo valutando il problema su due insiemi che non sono rappresentativi l'uno dell'altro. Esempio pratico: stiamo valutando la statura media in una classe di ingegneria e in una di economia e commercio, facoltà nella quale vi è una maggiore presenza femminile (altezza media più bassa).

Riassumendo, la curva relativa al TTS ci permette di fermare il processo di apprendimento; la distanza indicata nel grafico permette di capire se il training sta procedendo o meno in un modo soddisfacente. I campioni vengono scelti in modo da minimizzare la distanza fra i due minimi, ovvero portare i due punti estremi del segmento uno sull'altro (agendo sul TS); inoltre è auspicabile che entrambi i punti si avvicinino al 100% di accuratezza per il sistema (cosa che possiamo ottenere agendo sulla dimensione della rete).

Nel mondo reale la rete funziona su di un numero di campioni molto superiore a quello del TS; l'insieme sul quale la rete viene effettivamente verificata prende il nome di TEST SET. Intervenendo nel modo indicato, si possono ottenere sicuramente buone prestazioni soltanto sul TS. Per essere certi di averle anche sul TEST SET, durante il funzionamento della rete, con cadenza periodica, effettuiamo dei controlli per vedere se le aspettative di errore sono verificate sul TEST SET. Esempio: riconoscimento delle targhe automobilistiche. Disponiamo di 1000 esemplari di targhe; con 800 riempiano il TS, con le altre 200 il TTS. Otterremo una percentuale di riconoscimento che può essere anche molto elevata. Trasferiamo poi il sistema nel mondo reale e rendiamolo operativo; grazie ad un monitoraggio periodico possiamo capire se la percentuale di riconoscimento sul TEST SET rimane sostanzialmente la stessa oppure no.

Iniziamo oggi a descrivere algoritmi per l'apprendimento simbolico, o per l'apprendimento di domini caratterizzati da una descrizione strutturale delle informazioni. Nelle descrizioni strutturali, gli oggetti di interesse del dominio sono rappresentati in termini di componenti dette primitive o atomi, e di relazioni tra esse. Ad esempio, diremo che una persona è fatta di una testa, un tronco e gli arti. Inoltre, tali componenti devono essere collegati ovviamente in un certo ordine.

L'interesse delle descrizioni strutturali risiede nella loro similarità col modo di descrivere degli esseri umani. Per di più esse consentono di contestualizzare le componenti di un oggetto; ovvero, di dare una diversa interpretazione di ciascuna componenti in funzione della posizione che occupa all'interno dell'oggetto complessivo.

In informatica, spesso si preferisce usare metodi di descrizione diversi, più semplici di quello strutturale. Generalmente l'oggetto viene descritto misurandone alcune caratteristiche e rappresentando l'oggetto mediante un vettore di tali misure. Il vettore è una rappresentazione ben più semplice di quella in esame. Altro inconveniente delle descrizioni strutturali è che il risultato di una descrizione può presentare errori notevoli, a causa del rumore o di altre variabilità. Si può avere cioè una insoddisfacente robustezza rispetto agli errori. Si consideri l'esempio classico delle immagini grafiche: una immagine raffigura per esempio un individuo. Possiamo misurare l'altezza dell'individuo in funzione del numero di pixel di cui è composta l'immagine. Un eventuale pixel in più nell'immagine, dovuto ad un qualche rumore, naturalmente non incide in modo sostanziale su tale misura. Ma quando siamo intenzionati ad individuare un certo numero di componenti nell'immagine, quel singolo pixel in più potrebbe collegare due componenti separate facendole apparire come una singola componente.

Vediamo nell'esempio a destra un ipotetico processo di descrizione che consente di individuare le componenti della cifra 6. Il caso in esame appare piuttosto semplice, eppure per poter ottenere una soddisfacente descrizione strutturale è necessario eliminare molti fattori inessenziali, come lo spessore del tratto di penna utilizzato per scrivere la cifra. La relativa procedura è detta thinning (assottigliamento). L'insieme di punti così ottenuti non è ancora una rappresentazione adeguata in termini di componenti collegate; possiamo unire i punti con dei segmenti determinando una rappresentazione poligonale, e infine sostituire in qualche modo i segmenti con opportuni archi di cerchio (ne bastano due nell'esempio) per ottenere una rappresentazione quanto più simile a quella percepita da un essere umano. È naturale che le fasi considerate dipendano dall'applicazione. Riconoscere un carattere manoscritto è evidentemente diverso dal riconoscere un volto umano.

La rappresentazione così ottenuta può essere tradotta in un linguaggio quale la logica dei predicati. Si noti la figura a sinistra: la lettera B può essere rappresentata mediante tre archi di cerchio; avremo di conseguenza la lista dei predicati della pagina seguente. Il primo predicato ( large(n1) ) afferma che la componente n1 è un arco di cerchio di grandi dimensioni. Il secondo ( straight (n1) ) che il componente è più o meno 'diritto', e via dicendo. Mentre i predicati in rosso descrivono i singoli componenti, quelli in blu descrivono le relazioni. Abbiamo scelto in particolare di indicare il modo in cui due tratti entrano in contatto tra di loro; le componenti n2, n3 entrano in contatto con una giunzione a T (ovvero nel punto medio) le componenti n1 e n2 con una giunzione a V (e quindi non nel punto medio, ma in un estremo), eccetera. Il vantaggio è che un simile linguaggio può essere manipolato attraverso un SF, e quindi si può usare un linguaggio come il Prolog.

Rappresentazione alternativa è quella che fa uso di grafi. In particolare, si ha un grafo relazionale con attributi, in cui al classico insieme di nodi collegati da archi (ogni nodo sarà una primitiva, e ogni arco una significativa relazione tra primitive) si aggiunge un certo numero di attributi per la descrizione delle componenti e delle loro relazioni (si parla anche di reti semantiche). Questa rappresentazione trova riscontri in molti altri campi: i diagrammi UML introdotti in Ingegneria del Software e le formule di struttura delle molecole come insiemi di atomi collegati sono esempi di grafi relazionali con attributi.

Operazione fondamentale nei problemi che presenteremo e nei relativi algoritmi risolutivi è quella del confronto fra le diverse rappresentazioni. L'operazione di confronto è semplice nel caso dei vettori, una volta che sia stata introdotta una opportuna metrica, ma sicuramente non banale nel caso dei grafi. Infatti l'ordine con cui le informazioni sono inserite nel grafo può essere soggetto a variazioni. Nel caso della rappresentazione di una persona, può essere individuato prima il nodo-testa, o prima il nodo-tronco, etc. Il confronto tra due grafi è reso non banale da tale variabilità. Quindi è necessario stabilire una corrispondenza tra i nodi dei due grafi, basata non sull'ordine, ma sulla posizione relativa. Nell'esempio a lato, abbiamo due rappresentazioni in termine di grafo della cifra 2. Si tratta di riconoscere che il nodo numero 3 occupa la stessa posizione che nel secondo grafo è occupata dal nodo numero 2. Quindi quando si effettua il confronto fra i due grafi per vedere se sono uguali, occorre confrontare il contenuto informativo del nodo 3 del primo grafo con quello del nodo 2 del secondo. L'operazione necessaria a determinare queste corrispondenze ha una complessità esponenziale. Avendo a che fare con algoritmi di esplorazione dei grafi simili a quelli che abbiamo esaminato all'inizio del corso, è indispensabile trovare delle euristiche efficienti, per impedire che il tempo di computazione divenga insostenibile.

In alcuni casi particolari il tempo per il confronto si riesce a tenere limitato da un limite superiore di tipo polinomiale. Gli algoritmi usati allo scopo impongono però alcuni vincoli, come il fatto che il grafo non presenti cicli o che non ci siano incroci tra le relazioni. In assenza di tali vincoli, può capitare che tali algoritmi non garantiscano l'ottimalità della soluzione. Possono essere usati quando non è richiesto di trovare una soluzione ottima. Altri algoritmi ancora presentano un caso peggiore di tipo esponenziale, ma riescono nella maggioranza dei casi a mantenere basso il tempo di calcolo. Essi permettono per esempio di riconoscere in anticipo (rispetto ad un esame completo) un accoppiamento tra grafi, oppure, nei casi in cui sia necessario confrontare un singolo grafo con n altri, effettuano una opportuna pre-elaborazione dei grafi; o ancora, si usano le 'firme dei grafi' che consentono di scartare a priori un certo numero di accoppiamenti ritenuti non plausibili.

Come si addestra il sistema a riconoscere se un oggetto appartiene o meno ad un classe di oggetti di interesse? Quando si ha a che fare coi vettori si possono usare delle metodologie ben assestate, come quelle relative alle reti neurali. Al solito, il problema diviene più complicato in presenza di rappresentazioni tipo i grafi. Per costruire un sistema in grado di effettuare un corretto riconoscimento, è necessario disporre di una adeguata descrizione delle classi di oggetti.

Ci si presentano comunque varie alternative, suddivisibili in due categorie di massima (vedi disegno a seguire). La prima categoria prevede la costruzione di un reference set (insieme di riferimento). Per permettere il riconoscimento di appartenenza ad una classe di oggetti, si raccoglie innanzitutto un numero adeguato di esemplari di tale classe. Ad esempio, avremo un reference set contenete 1000 esemplari della lettera A scritta in vari modi. Quando il sistema deve riconoscere un carattere, andrà a confrontare il carattere assegnato con tutti gli esemplari dell'insieme di riferimento, sceglierà l'esemplare che appare più vicino al carattere assegnato e identificherà quest'ultimo con la classe in questione. Tale metodo non si basa su di un vero e proprio addestramento, ma può risultare efficace in qualche caso. Il problema evidente sta nella necessità di avere un insieme di riferimento molto ampio. Se non lo è abbastanza, non possiamo essere sicuri di aver 'catturato' una variabilità statistica sufficiente a consentire un efficace riconoscimento. D'altra parte, un reference set molto ampio fa ovviamente aumentare il tempo necessario per i confronti. Le ricerche attuali cercano di ottimizzare i confronti attraverso accorgimenti computazionali quali la parallelizzazione, o eseguendo per ogni set solo un ridotto numero di confronti, assumendo che se il confronto non ha successo con un dato campione, non lo avrà con altri campioni che sono in qualche modo simili a quello già scartato (metodi basati sulla distanza).

Approccio diverso all'addestramento è quello in cui le classi siano descritte attraverso descrizioni generali, ovvero che catturino soltanto gli elementi essenziali della classe in questione. Per fare un esempio, la classe dei bovini potrà essere distinta dalla classe degli uccelli specificando che un bovino possiede quattro zampe, mentre appare inutile precisare il colore del vello o la presenza e la lunghezza delle corna. Se dovessimo distinguere invece i bovini dagli equini, tali ultime caratteristiche diventerebbero significative. Si tratta cioè di individuare quegli elementi peculiari di una classe, ovvero che ne individuano gli esemplari e che costituiscono caratteristiche costanti al variare degli esemplari della classe in esame.

Un primo approccio è quello di ricorrere ad un esperto umano (sistemi esperti). Chiederemo ad esempio ad un esperto di zootecnica di formalizzare la differenza fra un animale e l'altro. Nel caso in cui l'esperto umano non sia in grado di formalizzare in modo rigoroso la conoscenza di cui è in possesso, può usare un metodo informale e successivamente si ricorrerà a specifici metodi di formalizzazione. In questo caso facilmente realizzabile, il sistema, di fatto, non produce autonomamente nuova conoscenza. Gli svantaggi dell'approccio stanno nel fatto che in certi contesti non è facile trovare esperti ad un costo ragionevole, oppure un esperto, messo a contatto con un realtà da classificare che è troppo varia e multiforme, potrebbe trovare difficile focalizzare l'attenzione sugli elementi realmente importanti ai fini del riconoscimento.

L'approccio che nasce in modo naturale da tali inconvenienti è quello che consiste in una opportuna automatizzazione del processo di apprendimento. Forniamo al sistema un certo numero di esempi da riconoscere; il sistema ne individua le caratteristiche essenziali, e sulla base di tali esempi costruisce la descrizione di una classe.

Un primo metodo, proposto da Winston (1970), non è completamente automatico. Il sistema è sì in grado di apprendere dagli esempi, ma questi devono essere sottoposti dall'operatore umano in maniera oculata e non causale. Il sistema ha bisogno soprattutto di controesempi del concetto da apprendere; partendo da una descrizione iniziale e banale dell'esempio, sulla base dei controesempi va a raffinarne progressivamente la descrizione, in accordo all'algoritmo raffigurato nel diagramma a blocchi a lato. La descrizione banale 'copre' anche oggetti che non appartengono in realtà alla classe da riconoscere; l'operatore (detto ORACOLO) dà al sistema un controesempio che dimostri che la descrizione non è adeguata. Il controesempio va scelto in modo che differisca di poco (idealmente, di una singola caratteristica) dalla descrizione trovata fino a quel momento. Il sistema modifica di conseguenza la descrizione della classe in modo da escludere il controesempio. Quando la descrizione sarà tale da escludere tutti i controesempi, risulterà completa e non sarà necessario procedere ulteriormente. Il processo si ripete ciclicamente fino a raggiungere questa situazione.

L'esempio proposto da Winston faceva uso del cosiddetto 'mondo dei blocchi', una realtà applicativa semplificata nella quale gli oggetti sono blocchi disposti in varie posizioni. Il problema (v.figura a lato) è quello di riconoscere un arco, costituito da due blocchi verticali ed uno orizzontale a formare un'architrave. Il sistema fornisce una prima descrizione: 'un oggetto è un arco se contiene almeno un blocco X'. Questa è la base dei raffinamenti successivi. L'operatore smentisce tale descrizione fornendo un controesempio dato appunto da un solo blocco. Il sistema confronta l'esempio ed il controesempio, e raffina la descrizione per escludere il controesempio: 'un oggetto è un arco se contiene almeno un blocco X ed un blocco Y'. L'oracolo fornisce un controesempio con due blocchi, che evidentemente non possono essere classificati come arco, il sistema raffina la descrizione con 3 blocchi, e via dicendo. Dopo un certo numero di passi si perviene ad una descrizione completa dell'oggetto 'arco' (si noti che nell'esempio occorrerebbe istruire il sistema anche sui colori dei vari blocchi; l'esemplare non conteneva blocchi di colore rosso).

Poiché il sistema esclude i controesempi 'per differenza' ricorrendo al numero minimo possibile di modifiche necessarie, i controesempi vanno inseriti in ordine opportuno: ognuno di essi dev'essere quanto più simile possibile alla descrizione corrente. L'apprendimento che può essere definito 'semiautomatico', risulta dal fatto che, come insegna l'esperienza, è più facile descrivere un oggetto precisando 'cosa non è' piuttosto che 'cosa è', ovvero dire cosa c'è di sbagliato nella soluzione di un problema piuttosto che trovare quella giusta.

Negli anni successivi sono nate delle tecniche che non richiedevano la presenza di un oracolo. Una importante famiglia di tecniche è quella che va sotto il nome di ILP (Inductive Logic Programming). L'apprendimento viene visto come costruzione di un SF che possa essere sottoposto ad un MI, come quello del linguaggio Prolog, per riconoscere le istanze del concetto. Inizialmente, l'utente fornisce un TS (Training Set) costituito da un sottoinsieme di esempi positivi e uno di esempi negativi (controesempi). L'algoritmo ILP deve costruire un SF in grado di riconoscere, attraverso le sue regole, l'appartenenza di un oggetto ad una classe che è stata appresa.

Vantaggi dell'ILP: il ricorso ai SF rende questo genere di descrizione facilmente comprensibile dal punto di vista umano (ben diverso è ad esempio il grado di comprensibilità delle reti neurali). La generalità e maggiore rispetto ad altri approcci; questo metodo si concentra sulle caratteristiche essenziali degli oggetti di una classe, ignorandone le caratteristiche accessorie, e pertanto il sistema è in grado di riconoscere oggetti che non aveva visto precedentemente (cosa non possibile nel caso del reference set). Ad esempio, il sistema può essere in grado di riconoscere un bovino anche se sprovvisto di coda (se la coda è considerata una caratteristica inessenziale ai fini del riconoscimento). Le descrizioni sono ESEGUIBILI: con queste tecniche si ottiene direttamente un programma in grado di riconoscere gli oggetti. Svantaggi: il costo computazionale dei metodi ILP è molto elevato, ed essi presentano una certa sensibilità al rumore nel TS. Gli esemplari del TS devono essere il più possibile esenti da rumore.

Gli algoritmi ILP devono costruire una rappresentazione coerente e completa del concetto da rappresentare. Si consideri il semplice esempio illustrato, in cui il sistema deve 'coprire' due classi, quella delle X e quella delle O, nel rispetto dei requisiti di cui sopra. La copertura rappresentata dai due rettangoli colorati nel secondo grafico è coerente, ma non completa: alcuni esemplari delle due classi rimangono fuori dai due insiemi.

Abbiamo successivamente una descrizione completa ma non coerente, perché figurano delle X nel rettangolo degli O e viceversa. Infine, l'ultima descrizione presenta entrambe le proprietà, e, come si vede, è più complessa delle precedenti.

Per ottenere una descrizione coerente e completa abbiamo due alternative: la prima è partire da una descrizione delle classi che è coerente ma non completa e modificarla per renderla completa. Negli esempi visti partiremo da un rettangolo 'piccolo' e ne espanderemo successivamente le dimensioni, comprendendo altri oggetti, fino al punto in cui non è possibile aumentare ulteriormente le dimensioni dell'insieme senza perdere la coerenza (è detto anche procedimento di generalizzazione, perché partiamo da una descrizione che, comprendendo pochi casi, è molto specifica, e tentiamo di renderla più generale includendo altri casi). Nella seconda alternativa partiremo da un rettangolo che comprende tutti i campioni (e quindi è sicuramente una descrizione completa) e lo restringeremo per contenere solo i campioni di una stessa classe (per rendere la descrizione coerente: procedimento di specializzazione

Un esempio di sistema ILP: il FOIL (Quinlan, 1990). Questo sistema si avvale di un procedimento di specializzazione. Per ridurre il costo computazionale, la ricerca effettuata è di tipo "greedy" (= avida). Nell'algoritmo di ricerca euristica, lo ricordiamo, è presente una coda di nodi aperti, dalla quale l'algoritmo preleva il nodo che presenta il valore della funzione obbiettivo (costo + euristica) più basso. Poiché il primo nodo aperto potrebbe risultare non ottimale, l'algoritmo deve tener memoria di tutti i nodi aperti per poter eventualmente prelevare un diverso nodo. Questo rende la sua complessità computazionale di tipo esponenziale nel caso peggiore. La strategia di Quinlan viceversa non consente all'algoritmo di tornare sui suoi passi: quando espande uno stato, calcolando la funzione obbiettivo per tutti i suoi figli, sceglie il nodo-figlio con il migliore valore di funzione obbiettivo e dimentica tutti gli altri. È come se si imponesse pari a 1 la lunghezza della coda dei nodi aperti. Questo algoritmo presenta inoltre la caratteristica di poter costruire programmi Prolog di tipo ricorsivo.

Facciamo un esempio preso a prestito dal riconoscimento di caratteri. Si vuole riconoscere il carattere A. Ci sarà una serie di esempi positivi e una di negativi. Il sistema parte da una descrizione del tutto generale: qualunque oggetto è una A (completezza).

Usando la sua euristica, il sistema determina che il carattere può essere una A solo se presenta un segmento orizzontale. Questo permette di tagliare fuori molti caratteri: la coerenza è migliorata (vedi grafici pagina successiva).

Se si aggiunge la condizione per cui il carattere deve presentare necessariamente anche un segmento diagonale, rendiamo il sistema coerente (nel caso in esame).

Così facendo, però, rendiamo il sistema non più completo, perché non vengono più riconosciuti come A dei caratteri che non presentano una linea diagonale. Per ovviare al problema, il sistema dopo aver memorizzato la precedente regola toglie dall'insieme di addestramento i campioni che erano stati già riconosciuti grazie all'ultima regola, e ricomincia daccapo il processo di apprendimento cercando altre caratteristiche che consentano di separare anche le due A rimaste tagliate fuori (vedi figura a lato). Procedendo in questo modo, il sistema riesce a trovare un insieme di regole che riconosce tutte e sole le A.

IL SISTEMA ARG. Si tratta di un sistema di apprendimento in domini strutturali presentato all'università Federico II. Si ripropone di risolvere i problemi di costo computazionale precedentemente citati nel seguente modo: anziché utilizzare il motore inferenziale di un SF, il problema dell'apprendimento viene affrontato lavorando sui grafi relazionali con attributi (e quindi mediante l'algoritmo di graph matching, componente fondamentale di ARG). L'operatore di specializzazione viene definito mediante gli attributi e non mediante i predicati. Questa filosofia pone un limite alla generalità rispetto a quanto garantito dall'ILP (non consente ad esempio la ricorsione), ma può migliorare sensibilmente le prestazioni. Inoltre elimina alcuni problemi di convergenza che si riscontrano utilizzando ILP (la ricorsione è difatti un'arma a doppio taglio: se si verifica si potrebbe non riuscire mai a trovare una soluzione).

Come gli oggetti da classificare, anche le classi sono descritte in termini di grafi relazionali con attributi; la parte strutturale si occupa di individuare un insieme minimale di elementi discriminanti, in grado cioè di distinguere un oggetto come appartenente ad una classe.

Riportiamo nella pagina seguente a sinistra uno schema a blocchi semplificato dell'algoritmo di apprendimento[9]. Al solito, si parte da un prototipo banale che copre tutti gli esemplari; si procede poi con successive specializzazioni, fino a raggiungere una situazione di coerenza. Le specializzazioni si traducono in modifiche al grafo (aggiunta o modifica di nodi, archi e attributi) sui cui dettagli non insistiamo. Quanto alla scelta della specializzazione (figura a destra), anche in questo caso essa è guidata attraverso l'uso di una funzione euristica.

Esempio di applicazione: i test di Bongard. Si tratta di un test di intelligenza in cui occorre individuare la caratteristica del gruppo di 6 disegni di sinistra che lo differenzia dal gruppo di destra.

Si tratta quindi di un tipico problema di classificazione a due classi a cui è possibile (ed istruttivo) applicare un algoritmo di apprendimento.

Per prima cosa, rappresentiamo ogni oggetto con un grafo relazionale. Nel grafico che segue vengono indicati gli attributi, che riguardano la forma e la dimensione delle figure geometriche (possono essere cerchi, triangoli o rettangoli di dimensioni piccole, medie o grandi). La relazione usata è di tipo 'contenimento' (inside). Un nodo x è collegato da un arco al nodo y se l'oggetto rappresentato da x è contenuto all'interno di y.

Si noti come viene utilizzata tale rappresentazione per la situazione di sinistra nella stessa figura, in cui abbiamo tre figure una dentro l'altra (grafo a tre nodi collegati), un singolo triangolo piccolo ed un singolo rettangolo piccolo. Il sistema apprende servendosi esclusivamente dei grafi.

In particolare applichiamo la procedura ad un test di Bongard a 3 classi. Il sistema deve cioè classificare tre gruppi di disegni; ad esempio deve individuare cosa differenzia il primo gruppo dagli altri due. Esso parte da un prototipo generale: i punti interrogativi stanno a significare che inizialmente si ha un oggetto di qualsiasi dimensione e qualsiasi forma, descrizione che ovviamente copre tutte e tre le classi, ovvero tutti e 18 i disegni (completezza, ma non coerenza).

Il sistema comincia il processo di specializzazione: poiché con nessuno degli operatori riesce ad individuare eventuali campioni negativi da eliminare, esso tenta di raffinare la ricerca aggiungendo un altro nodo. Il nostro prototipo a questo punto rappresenta tutti gli oggetti che contengono almeno 2 figure.

Osservando i 18 disegni ci si rende conto che in ciascuno di essi vi sono almeno 2 figure, quindi neanche questo è sufficiente ad operare un raffinamento. Si passa allora ad aggiungere un terzo nodo: il disegno deve contenere almeno 3 figure geometriche. Le cose migliorano, perché due dei 18 disegni vengono scartati (ci muoviamo verso la coerenza).

Il passo successivo comporta l'aggiunta di un quarto nodo, con il che viene eliminato un altro disegno (vedi figura pagina successiva).

A partire dal quinto passaggio si evita di aggiungere altri nodi, perché ciò farebbe perdere la completezza del sistema senza migliorarne sensibilmente la coerenza. Il sistema prova allora a modificare il grafo corrente in altro modo: aggiunge una relazione tra due nodi. Il quinto prototipo rappresenta un disegno con almeno 4 figure, di cui almeno una deve essere contenuta all'interno di un'altra. Come si vede, ciò non incide sul processo di classificazione.

Ma a questo punto basta aggiungere una sola relazione di inclusione per individuare una descrizione della classe che scarta tutti i disegni che non appartengono alla classe più a sinistra. L'ultimo grafo trovato è dunque una descrizione completa e coerente: il disegno contiene almeno 4 figure geometriche e di queste 3 sono una dentro l'altra.

Da notare che questa descrizione, coerente e completa, è però leggermente ridondante. Eliminando infatti dei 4 nodi quello che non è collegato agli altri, avremmo ancora una descrizione completa e coerente. Ciò dipende proprio dal carattere 'greedy' dell'algoritmo: esso non implementa una forma di backtracking, che gli permetterebbe di modificare le aggiunte fatte nei passi precedenti, e quindi non ha modo di eliminare il 4° nodo.

Gli strumenti come le reti neurali fanno capo alla TESI FORTE dell'AI, che lavorano in due distinte modalità di funzionamento: la fase di addestramento e la modalità operativa. Alla base delle reti neurali (RN) c'è un fondamento matematico molto rigoroso, la cui conoscenza non è però necessaria dal punto di vista utente.

Consideriamo la definizione di RN secondo Hecht-Nielsen. Una Rete Neurale è una struttura parallela che processa informazioni distribuite. L'idea di partenza è di immediata comprensione: si tratta di collegare insieme elementi in grado di eseguire compiti semplici, in modo che l'insieme risultante permetta di eseguire compiti complessi. Questo è proprio quanto avviene nella mente umana, costituita da una intricata rete di elementi relativamente semplici detti appunto neuroni. Una RN consta di elementi di processazione, detti ancora neuroni (o PEs), che possono avere una memoria locale e che sono in grado di processare localmente informazioni ricevute in ingresso. L'informazione contenuta in ciascun neurone è poca cosa, e vedremo che in certi casi un singolo neurone può essere del tutto trascurato senza ripercussioni sul contenuto informativo dell'intera RN.

I neuroni sono interconnessi tramite canali (detti connessioni) che trasmettono segnali unidirezionali. Ogni neurone ha una singola connessione di uscita che si dirama in un certo numero di connessioni collaterali; ognuna di questa trasporta lo stesso segnale, il segnale d'uscita del neurone. Questo segnale d' uscita può essere di qualunque tipo matematico. La computazione compiuta all'interno di ciascun neurone può essere definita arbitrariamente con l'unica restrizione che deve essere completamente locale; cioè deve dipendere solo dai valori correnti dei segnali d'ingresso che arrivano al neurone tramite opportune connessioni e dai valori immagazzinati nella memoria locale del neurone.

Lo schema a lato raffigura una RN. I cerchietti rappresentano i neuroni. Come si vede, alcuni dei neuroni ricevono in ingresso un vettore x. Ogni neurone produce una uscita, che può diventare l'ingresso di un altro neurone, oppure essere parte dell'uscita complessiva y (ancora un vettore) della rete. Non c'è correlazione tra la dimensione di x e quella di y.

A sinistra viene indicata la struttura tipica di un neurone. L'insieme dei segnali di ingresso è x₁, ., x_n. Il neurone realizza, a partire da tali valori e dai dati memorizzati nella memoria locale, una funzione di trasferimento. Detta funzione oltre a determinare l'uscita del neurone può modificarne la memoria locale. Questo perché i neuroni attraversano, come si è detto, anche una fase di addestramento; la memoria locale conterrà la conoscenza maturata durante tale fase.

Quando il neurone è stato addestrato, entra nella fase operativa, in cui riceve in ingresso dei segnali ed elabora di conseguenza l'uscita. Nella fase operativa la memoria locale non viene più modificata (alcuni modelli di RN fanno eccezione a questa regola: apprendimento adattativo, nel quale l'apprendimento non termina mai).

In questo corso prendiamo in esame esclusivamente RN di tipo software. Per ogni neurone va specificata la funzione di trasferimento realizzata. Dovremo esaminare inoltre le varie architetture disponibili nonché le leggi di apprendimento che vengono di volta in volta applicate.

Il disegno che segue propone alcune tipiche topologie di RN. I modelli possono essere suddivisi in due grandi categorie: le reti feed-forward e quelle ricorrenti. Le reti feed-forward sono caratterizzate da un unico flusso di dati unidirezionale, privo cioè di cicli. Si riconoscono in essi degli strati o layer; abbiamo per esempio modelli a singolo strato di percettroni.

Altri modelli di questa famiglia si presentano con una configurazione a multistrato (MLP, dette anche impropriamente reti di back-propagation), in cui ciascuno strato è collegato al successivo. Il primo strato della rete riceve in parallelo l'ingresso; elabora quindi l'uscita, che sarà l'ingresso dello strato successivo, e via dicendo. Questi modelli sono di gran lunga i più noti e diffusi.

I modelli Radial Basis Function sono caratterizzate da una speciale modalità di addestramento e da una diversa funzione di trasferimento per il singolo neurone. Noi non tratteremo questi modelli.

La seconda grande famiglia tassonomica di RN è quella che comprende le reti a connessione laterale e le reti ricorrenti, dette anche feedback networks.

Esempi di reti a connessione laterale sono le reti competitive nelle quali ogni neurone, oltre a dare un contributo verso l'uscita, è collegato ai neuroni dello stesso strato. Possiamo avere anche in questo caso una stratificazione singola o multipla.

Abbiamo anche le mappe auto-organizzanti di Kohonen (SOM), la differenza topologica consiste in una configurazione a griglia: ogni neurone è collegato solo ad un certo numero di altri (es: ai 4 o agli 8 che gli stanno intorno) e non a tutti i neuroni del medesimo strato, come nel caso precedente.

Nelle reti ricorrenti l'uscita di ciascun neurone viene riproposta in ingresso al neurone stesso. Un esemplare di questo modello è dato dalle reti di Hopfield, utili nei problemi di ottimizzazione. Nei modelli ART si riscontra la compresenza del feedback e delle connessioni laterali.

Esistono diverse modalità di addestramento. L'addestramento avviene sempre grazie ad un certo numero di esempi prelevati dal mondo reale. Nell'addestramento supervisionato, gli esempi forniti alla RN sono delle coppie (ingresso, uscita corrispondente desiderata). Per capire il punto, possiamo anticipare il fatto che un utilizzo tipico delle RN è quelle dei classificatori: RN che devono essere in grado di riconoscere oggetti appartenenti a diverse categorie. La descrizione viene fatta mediante vettori di numeri reali; a fronte di un certo ingresso vettoriale, la RN si deve esprimere attribuendolo ad una classe. Nella modalità supervisionata, diremo alla rete che, quando riceve un ingresso ben preciso, deve attribuirlo alla classe X. Altra classe di problemi risolti dalle RN è l'inseguimento (approssimazione) di funzioni. Una funzione in una o più variabili è nota per punti (non ne conosciamo la forma analitica); la RN deve riuscire ad approssimarla nel modo migliore possibile, calcolandone il valore anche in punti diversi da quelli proposti in ingresso. Nella fase di addestramento, diremo alla RN quale valore di uscita corrisponde a ciascun ingresso assegnato. Quanto nella modalità operativa riceverà un ingresso diverso, la rete dovrà tirare fuori un valore approssimato dell'uscita quanto più vicino possibile a quello reale.

Nell'addestramento non supervisionato forniamo alla rete dei soli valori di ingresso (il TS, training set) senza precisare le relative uscite. La rete è in grado di auto-organizzarsi (come nelle SOM cui si è accennato prima) modificando la propria conoscenza interna (ovvero la memoria locale dei neuroni).

Fra questi due estremi c'è l'addestramento graded: tipicamente la rete evolve in maniera autonoma, come nella modalità non supervisionata. I particolari istanti di tempo viene però utilizzata anche l'informazione sull'uscita desiderata. Si parla anche di reinforcement: ad intervalli di cicli di addestramento scanditi da un periodo si affianca alla modalità non supervisionata una modalità supervisionata. Noi non considereremo questo genere di addestramento.

Esistono cinque categorie fondamentali di leggi di apprendimento. Nel performance learning l'obbiettivo è di massimizzare o minimizzare una certa funzione, in particolare un certo indice prestazionale. Tutti i neuroni partecipano in ugual misura dell'addestramento. Esempi tipici di reti che rientrano in questa categoria sono le reti a percettroni.

Nel competitive learning invece durante l'apprendimento si genera una competizione tra i diversi neuroni. Ad ogni passo dell'addestramento solo una parte dei neuroni (che 'vince' la competizione) modifica la propria memoria (stato interno). Questo è quanto avviene ad esempio nelle SOM di Kohonen.

Non considereremo in questo corso le altre tre categorie di leggi di apprendimento, che citiamo per completezza: coincidence learning, filter learning, spatiotemporal learning. Esistono anche esempi di reti nelle quali non esiste una vera e propria fase di apprendimento (reti di Hofield).

Non c'è perfetta ortogonalità tra le modalità di addestramento e le leggi di apprendimento: in molti casi alle leggi di apprendimento possono essere applicate modalità di addestramento supervisionate o non supervisionate, in altri (es. back propagation) la sola modalità superivisionata.

Un progenitore delle RN: IL MODELLO DI MCCULLOCH-PITTS (1943). In questo prototipo non si dovrebbe nemmeno parlare, a rigore, di neuroni; i 'cerchietti' del disegno a lato si limitano a calcolare delle funzioni logiche come quella che si è indicata. Il neurone all'istante t calcola una AND fra le uscite dei neuroni agli istanti precedenti. Uscite e ingressi di ciascun 'neurone' possono essere eventualmente negati (pallino bianco).

IL PERCETTRONE DI ROSENBLATT (1957). È il primo vero e proprio modello di RN, giacchè prevede una sia pur rudimentale legge di apprendimento sulla base di esempi. Il percettrone di Rosenblatt calamitò l'attenzione degli appassionati di AI per oltre un decennio, quando verso la fine degli anni 1960 ci si rese conto che tale modello non poteva risolvere che problemi molto semplici rispetto alle reali necessità applicative. Tuttavia verso la metà degli anni 1980 alcuni studiosi americani riuscirono a superare i problemi legati a questa semplice struttura, il che rappresentò il vero punto di partenza verso lo sviluppo recente delle RN.

Si ha una serie di ingressi X₁, ., X_n. più l'ulteriore ingresso X₀ che è fisso al valore 1. La memoria locale del neurone è rappresentata dai valori w₀, w₁, ., w_n, detti PESI. A ciascun ingresso è cioè associato un peso, che è un valore reale. La funzione di trasferimento è semplicemente una somma pesata degli ingressi moltiplicati per i pesi (in pratica un prodotto scalare tra vettori). L'uscita del percettrone è a livelli e, per l'esattezza, binaria. Se i prodotto scalare è non negativo, l'uscita del percettrone è alta, altrimenti bassa. Questo modello si presta bene ad essere usato per problemi di classificazione a due classi soltanto o anche per applicazioni relativi a funzioni logiche, con ingressi e uscite binari.

La fase di addestramento è supervisionata. Vengono mostrati al percettrone degli ingressi e le rispettive uscite desiderate y, e in base a ciò il percettrone modifica i pesi in accordo alla legge di apprendimento che prenderemo in esame tra breve.

Consideriamo una interpretazione geometrica della funzione di trasferimento realizzata dal percettrone. La rappresentazione del grafico che segue è bidimensionale: il percettrone riceve due ingressi, x₁ e x₂, e fornisce una uscita binaria. In generale avremo un iperpiano la cui espressione è indicata in calce al diagramma; nel caso bidimensionale l'iperpiano diviene una retta, w₀ + w₁x₁ + w₂x₂ = 0. Tale retta delimita le 'regioni di decisione' del percettrone. Dopo aver ricevuto l'ingresso (x₁, x₂), il percettrone calcola il valore della funzione di trasferimento emettendo in uscita il valore 1 o 0. La retta è il luogo dei punti per i quali il prodotto scalare di pesi e ingressi (più il peso w₀, cui corrisponde l'ingresso fisso unitario), ovvero il valore di uscita del neurone, è nullo. Poiché la retta suddivide il piano in due semipiani, in base all'espressione della funzione di trasferimento del percettrone possiamo concludere che tutti gli ingressi di coordinate (x₁, x₂) del semipiano inferiore sono quelli cui corrisponde uscita bassa, e viceversa dicasi per il semipiano superiore.

Quindi, dal punto di vista geometrico il percettrone opera una separazione lineare dei punti dello spazio (nell'esempio uno spazio a due dimensioni. Nel caso tridimensionale il percettrone genera un piano che divide lo spazio in due semispazi. Nel caso n-dimensionale per n > 3 diventa difficile visualizzare graficamente la situazione). Modificare i pesi w₁, w₂ della funzione di trasferimento significa modificarne la pendenza (rotazione); in più la presenza di un termine w₀ fa sì che la retta non sia vincolata a passare per l'origine, e ne regola la traslazione. Lo scopo del percettrone (e quindi della sua legge di apprendimento, che è di tipo performance) è la minimizzazione dell'errore.

Abbiamo riportato a sinistra una semplice legge di apprendimento, che per il momento non giustifichiamo, consistente nel modificare il vettore w dei pesi dimodoché il nuovo valore di w sia pari al vecchio, più un termine dato dal prodotto fra l'ingresso vettoriale x e la differenza fra uscita desiderata e uscita del percettrone. Le due uscite y e y' possono valere 1 o 0. Si deduce immediatamente che:

se l'uscita desiderata è uguale all'uscita del percettrone, il vettore dei pesi rimane immutato; non è necessario in questo caso modificare la conoscenza interna, ovvero i pesi;

se le uscite sono diverse, l'ingresso può essere o sottratto o sommato al vecchio valore del vettore w.

Un esempio: la funzione OR. Supponiamo che il percettrone debba apprendere la funzione booleana or inclusivo, la cui tabella di verità è ricordata a lato. Vogliamo quindi un percettrone che riceva in ingresso due valori binari e restituisca in uscita la or tra i due ingressi. La novità concettuale rispetto alle implementazioni considerate in altre materie di questo corso di laurea sta nel fatto che, stavolta, abbiamo a che fare con uno strumento in grado di apprendere autonomamente, per esempi, il comportamento desiderato.

Tutte le leggi di addestramento partono da una condizione iniziale; i pesi del neurone devono cioè possedere un valore di partenza. Imponiamo come condizione iniziale, per il momento senza giustificare questa scelta, il vettore:

Si calcola per ciascun esemplare del TS (che qui coincide con il Data Set) il prodotto scalare di cui alla funzione di trasferimento.

Si ha quindi 1*0.5 + 0*0 + 0*0 = 0.5. Il percettrone dà valore alto, mentre l'uscita desiderata è zero. È quindi necessario modificare il vettore dei pesi. Applicando la legge di addestramento succitata, si ha il nuovo valore w¹ = (-0.5, 0, 0) (è y = 0, y' = 1).

Proponendo il successivo ingresso:

si ha y' = 0, e quindi un nuovo valore per il vettore dei pesi, a cui va aggiunto il vettore (1, 0, 1) (è y = 1, y' = 0). Rappresentiamo di seguito la nuova coppia (w,x).

L'esempio (1,0) viene riconosciuto correttamente (y = y' = 1), e di conseguenza il vettore w² non viene modificato (lo scriviamo in nero anziché in rosso). Lo stesso avviene per l'esempio (1,1).

A questo punto, gli esemplari del TS sono riproposti in ingresso al percettrone. Proponiamo una serie di coppie (w, x) relative ai passi successivi dell'apprendimento.

La configurazione giusta dei pesi è quindi (-0.5, 1, 1), giacché tale configurazione non può essere più modificata dagli ingressi. La rete a questo punto è in grado di riconoscere correttamente la funzione OR. Geometricamente, abbiamo ottenuto la retta x₁ + x₂ = 0.5; è solo una delle possibili rette che risolvono l'assegnato problema. Per diverse condizioni iniziali abbiamo diverse soluzioni.

Giacché l'unica separazione consentita dal percettrone è di tipo lineare, esistono numerosi esempi nei quali il ricorso al percettrone come separatore binario si rivela inefficace. Famosa a questo riguardo è la critica di Minsky, concernente la funzione logica XOR (OR esclusivo). Essa, come è noto, vale 1 se solo uno dei due ingressi è alto, altrimenti vale 0. I due punti menzionati dovrebbero quindi appartenere al semipiano 1, e gli altri due al semipiano 0. Come si vede dal diagramma a seguire, non esiste alcuna retta in grado di determinare una separazione di questo tipo.

Una possibile soluzione al problema, scoperta nella seconda metà degli anni 1980, è data dal percettrone multilivello. Nella figura precedente è indicata una struttura a due livelli. In questo caso è però necessaria una nuova legge di apprendimento, dal momento che, mentre l'uscita desiderata y della rete nel suo complesso (che è poi quella del percettrone superiore) è nota, nulla sappiamo dire sulle uscite desiderate dei due percettroni appartenenti al livello inferiore. In una prossima lezione considereremo una legge di apprendimento utilizzabile con una struttura di questo genere.

Le RN hanno dimostrato potenzialità significative in vari campi d'applicazione. C'è innanzitutto la Pattern Classification (riconoscimento di forme). Una RN agisce come classificatore, discriminando ad esempio una serie di elettrocardiogrammi in ingresso fra normali o indicativi di una patologia. Le reti maggiormente impiegate in tale ambito sono quelle di tipo competitivo e quelle basate su percettroni.

Le mappe auto-organizzanti sono largamente usate nel Clustering. Abbiamo un certo numero di esemplari, di cui non si conosce a priori la classe di appartenenza, e non è noto nemmeno il numero delle classi. L'obbiettivo è individuare proprietà comuni che costituiscano la base di una classificazione effettuata a posteriori. Il problema è facilmente visualizzabile in uno spazio bidimensionale o tridimensionale. Potrebbe risultare che in una certa zona del piano vi è un aggregato di oggetti, il che è indicativo del fatto che tali oggetti possiedono proprietà simili. A posteriori assoceremo a classi separate gruppi (cluster) di oggetti che risiedono in una stessa parte dello spazio. Le coordinate del piano possono essere in questo caso una misurazione (secondo una certa scala) delle loro proprietà (ad esempio, peso e altezza di un individuo). In uno spazio n-dimensionale, un tale ragionamento geometrico non è più fattibile, per cui si usano appositi algoritmi di raggruppamento. Poiché in casi di questo genere non si conosce a priori il numero di classi, non si può applicare un algoritmo di apprendimento supervisionato.

Abbiamo poi la categoria di Approssimazione di Funzioni: è data una funzione definita per punti. La RN apprende la corrispondenza analitica fra x e y. Come è noto, esistono vari strumenti di approssimazione che non hanno nulla a che vedere con l'AI, ma l'approccio neurale risulta più efficiente soprattutto quando si è in presenza di forti non linearità.

Strumenti di Previsione: a partire da (n-1) osservazioni precedenti, la RN ha il compito di predire l'n-sima istanza (serie storiche).

Ottimizzazione: particolari RN (reti ricorrenti di Hopfield) consentono di risolvere problemi classici di ottimizzazione come quello del Commesso Viaggiatore. Queste stesse reti permettono di realizzare inoltre le Memorie Associative (dette anche indirizzabili per contenuto: il sistema contiene un repertorio di oggetti; sollecitato con un oggetto d'ingresso, restituisce l'oggetto del repertorio che risulta più simile all'ingresso; quest'ultimo sarà ascritto all'eventuale classe di appartenenza dell'oggetto scelto) e di approcciare problemi di Controllo.

Abbiamo visto la volta scorsa come Minsky e altri criticarono il modello del percettrone, rilevando il fatto che esso non potesse risolvere problemi non linearmente separabili, sebbene molto semplici, come quello della XOR. Possibile soluzione è quella del Percettrone Multilivello indicato nel disegno a sinistra. I pallini più piccoli della parte inferiore denotano lo 'strato d'ingresso' del percettrone, che non effettua una vera e propria computazione, ma serve solo per far fluire i dati d'ingresso agli strati successivi.

Per comprendere le scritte come la 'th=0.4' possiamo ricordare la forma della funzione di attivazione del percettrone (vedi la formula a pagina 108): da un prodotto scalare si determina una soglia, che definisce il valore binario di y'. La soglia è lo zero. Tuttavia, se estraiamo il peso w₀ dalla sommatoria e lo portiamo a secondo membro, si comprende immediatamente come proprio il peso w₀ possa essere visto come soglia. Nella figura a sinistra th (threshold) è appunto la soglia di attivazione del percettrone. Si può verificare (non lo faremo) che questa struttura è effettivamente in grado di risolvere problemi come quello dell'OR esclusivo. Purtroppo rimane in piedi il problema cui si accennava al termine dell'ultima lezione: la legge di apprendimento usata nel modello di Rosenblatt è inapplicabile, dal momento che si conosce l'"uscita desiderata" solamente dell'ultimo strato e non di ogni singolo neurone. Non sapremmo quindi come modificare i pesi di tutti gli altri neuroni. Poco dopo l'individuazione di questo problema Rumhelhart e altri riuscirono tuttavia ad aggirare tale ostacolo, ricavando una legge di apprendimento ed un algoritmo di addestramento adatti per il percettrone multilivello (ci torneremo in una prossima lezione).

Il Prossimo modello che consideriamo è ancora una struttura a singolo neurone, l'ADALINE (ADAptive LiNear Element). La legge di apprendimento usata è quasi identica a quella di Rosenblatt, mentre la differenza sostanziale sta nel fatto che l'uscita y' (funzione di attivazione) è proprio il prodotto scalare tra i vettori w e x: non c'è un concetto di soglia. Il modello è quindi ancora lineare. È sempre presente un peso w₀ associato alla connessione fittizia x₀ = 1. Dal punto di vista geometrico, la retta che si ottiene ha lo stesso significato del caso del percettrone (è il luogo dei punti per cui il prodotto scalare fra il vettore dei pesi e quello degli ingressi risulta nulla). Il valore dell'uscita, che qui è continua e non binaria, è tanto maggiore quanto più ci si allontana da tale retta.

Consideriamo una classica applicazione: l'approssimazione di una funzione y di un certo numero di variabili. All'uopo l'elemento va opportunamente addestrato. Consideriamo allora la seguente espressione per l'errore quadratico medio:

k varia tra 1 a N (numero di elementi del TS). Lo scarto quadrato medio fra l'uscita k-esima desiderata y e quella effettiva y' per tutti i campioni del TS dipende evidentemente dai pesi, dato che vi dipende l'uscita effettiva. L'errore può quindi essere portato quanto più vicino possibile a 0 modificando i pesi. I seguenti passaggi (nota: nessuna dimostrazione matematica è richiesta per l'esame) mettono in evidenza tale dipendenza.

Il problema diventa quindi quello di trovare il punto di minimo della funzione F(w) di errore. Riportiamo di seguito il punto di minimo di F(w), ottenuto azzerando il gradiente.

Abbiamo trovato il vettore dei pesi ottimo, ovvero quello che risolve in senso assoluto il nostro problema di apprendimento. Questa costituisce una novità in un panorama come quello della tesi forte dell'AI che appare fatto di soluzioni approssimate e adattative piuttosto che analiticamente esatte. Comunque, nella formula compare l'inversa di una matrice, che potrebbe non essere calcolabile. È da dire anche che a monte del processo di apprendimento potrebbe non essere disponibile l'intero TS, indispensabile per il calcolo di R e q. In casi come questi la formula analitica non ci aiuta e si rende necessario il ricorso ad un algoritmo di apprendimento come quello che introdurremo fra breve.

Si trova che la funzione di errore è un paraboloide (vedi diagramma a seguire), e quindi il punto di minimo è (salvo casi eccezionali) unico. L'esempio considerato è tridimensionale, nel senso che gli ingressi sono due e quindi la funzione di errore dipende da due variabili. Nella figura sono messi in evidenza due punti: quello più in alto corrisponde all'errore quadratico commesso dalla rete in corrispondenza delle sue condizioni iniziali. Quello inferiore w* minimizza la funzione di errore, e, come si vede, è unico.

La legge di apprendimento per questo modello, detta Delta-Rule, fu postulata da Widrow-Hoff. Dal punto di vista geometrico, la soluzione esatta prima trovata corrisponde a partire da un dato punto del paraboloide, e modificare il vettore dei pesi, seguendo così una certa traiettoria sul paraboloide, nella direzione della massima pendenza e nel verso discendente. La legge di apprendimento che ne scaturisce consisterebbe nel modificare i pesi di una quantità proporzionale al gradiente. In basso è indicato il calcolo del gradiente. Il problema di tale formula è che in esso compare una media statistica. Il calcolo esatto richiederebbe quindi un numero infinito di elementi del TS, cosa non possibile.

L'ostacolo viene aggirato introducendo una differenza fra training by epoch e training by pattern. In quest'ultimo caso, per ogni esemplare del TS effettuiamo una modifica dei pesi (come avviene nel percettrone). Nel training by epoch invece viene effettuata dopo ogni 'epoca' (ogni evento di presentazione dell'intero training set al sistema che si vuole addestrare costituisce un'epoca). Nel caso di Adaline a rigore si dovrebbe effettuare un training by epoch. Widrow-Hoff dimostrarono comunque che anche adottando un criterio di training by pattern, cioè calcolando il gradiente campione per campione e modificando i pesi in accordo al gradiente calcolato per ciascun pattern, si converge al punto di minimo. Seguendo questo ragionamento, possiamo raggiungere il punto di ottimo, invece che nel modo più ovvio (cioè calcolandolo analiticamente) attraverso una serie di spostamenti ripetuti. La conseguente modifica dei pesi (che dev'essere di segno opposto rispetto a _wF(w), dal momento che dobbiamo spostarci nella direzione discendente) è riportata nella stessa figura come Dw_k (si noti la somiglianza con quella del percettrone, pag. 109, che quindi trova adesso una giustificazione). Adottando ad ogni passo di addestramento questa modifica dei pesi, ci spostiamo lungo la superficie di errore, ed è certo che dopo un certo numero di passi raggiungeremo il punto di minimo.

Ad ogni passo, nota per ogni campione l'uscita desiderata y_k e ottenute l'uscita di Adaline y'_k si calcola la differenza, la si moltiplica per x_k e per il coefficiente h di cui diremo fra breve, determinando la differenza dei pesi relativa a quel campione. Si ottiene in questo modo un gradiente 'locale' rispetto al campione e non mediato rispetto all'intero TS.

Riportiamo qui di seguito le 'curve di isoerrore'. Dato il paraboloide della superficie di errore, lo intersechiamo con una serie di piani paralleli. Siccome un piano parallelo denota un livello costante, ciò implica che per ciascun punto (w₁, w₂) di ognuna delle curve evidenzate il valore dell'errore è lo stesso.

Calcolare in modo esatto una media statistica equivale a muoversi ortogonalmente rispetto alle curve di isoerrore (grafico a sinistra): ci stiamo cioè realmente muovendo nella direzione di massima pendenza. Il tragitto percorso è sicuramente il più breve possibile, tuttavia tale percorso è determinato solo una volta che si sia effettuato il calcolo dell'errore su tutto il TS. Anche se ciò fosse possibile, si avrebbe comunque un consumo notevole di tempo nella fase di computazione. Nel secondo caso invece (grafico di destra), effettuando la modifica dei pesi con il training by pattern nella filosofia di Widrow & Hoff, si riscontra uno spostamento 'a scatti' che localmente non sempre si muove nella direzione corretta, ma a regime converge[10] alla soluzione.

Veniamo al coefficiente h, detto learning rate (coefficiente di apprendimento): esso misura la dimensione del passo. La lunghezza di ciascun passo è proporzionale a h, sicché un learning rate molto piccolo causa una convergenza molto lenta, mentre se è troppo grande si corre il rischio di non riuscire a fermarsi mai sul punto di minimo (divergenza rispetto alla soluzione). Il valore del learning rate è in genere minore di 1 con valori tipici intorno a 0.5.[11]

I modelli visti fin qui hanno ormai un valore quasi esclusivamente didattico. Presentiamo oggi due architetture di maggior pregio: il Percettrone Multilivello e l'LVQ. Nel Percettrone Multilivello (PM) i dati entrano in ingresso al primo layer, si propagano verso tutti i layer interni e da questi fluiscono verso l'ultimo. Il flusso di dati è unidirezionale e di tipo feed-forward: neuroni dello stesso livello non possono scambiarsi tra di loro dei dati e non c'è propagazione all'indietro. Si usa un algoritmo di apprendimento di tipo Performance Learning, simile a quello di Adaline. Abbiamo già accennato al fatto che il problema del PM è che risulta difficile estendere la legge di apprendimento vista nel caso del singolo strato, dato che non conosciamo le uscite desiderate dei neuroni non appartenenti allo strato di uscita: ci torneremo nel corso di questa lezione.

L'LVQ differisce nella legge di apprendimento, che è di tipo Competitive Learning, e nel fatto che sono previste delle connessioni laterali.

Il PM si caratterizza per la presenza di almeno uno strato nascosto, che 'non vede' né gli ingressi x_P1. x_PN (essendo x_P il p-esimo esemplare dei Training Set) né le uscite della rete. Nelle nostre considerazioni faremo riferimento ad un PM a 3 strati (un solo strato nascosto).

Il numero di ingressi di una RN è fissato dal problema: ad esempio per un approssimatore di una funzione a 3 variabili lo stato d'ingresso sarà composto da 3 neuroni. Gli N nodi dello stato iniziale non sono però dei neuroni in senso stretto, perché la loro ragione d'essere è di propagare i dati d'ingresso verso gli strati successivi, ma non effettuano alcuna computazione. Se non ci fosse lo strato nascosto rimarrebbe in pratica un solo strato di percettroni: i Percettroni Multilivello presentano sempre almeno uno strato hidden.

Le Bias Unit sono unità fittizie il cui scopo è di presentare a ciascun neurone un ingresso fisso pari a 1 (appare anche nei modelli del Percettrone e Adaline).

Consideriamo le formule che seguono. Con net^h_pj si vuole indicare l'uscita del singolo neurone a meno della funzione di attivazione. Il generico neurone j effettua il prodotto scalare del vettore degli ingressi per il proprio vettore dei pesi, rappresentativi della memoria locale del percettrone; viene poi aggiunto il solito peso associato all'ingresso unitario. Gli apici h e o stanno rispettivamente per strato hidden e output, mentre p denota il p-esimo campione del TS. Alla combinazione lineare così calcolata viene applicata la funzione di attivazione del neurone, che nel caso del percettrone era un gradino, e nel caso di Adaline la funzione identità. Nel caso PM non esiste un unico tipo di funzione di attivazione e non è detto che tutti gli strati presentino la stessa funzione di attivazione (benché in generale sia così).

Consideriamo ora l'addestramento di un PM. Un primo aspetto notevole è che un PM introduce delle non-linearità, a motivo della struttura delle funzioni di attivazione che considereremo fra breve. Questo è il vero vantaggio del modello, perché permette di risolvere problemi non linearmente separabili. Ciò d'altra parte determina una forma diversa per la superficie di errore, che non è più un paraboloide, ma un agglomerato spesso molto complesso di monti e valli. In questo modo il problema della ricerca del minimo si complica, soprattutto perché non si ha in generale un unico minimo, ma più minimi 'locali'.

L'idea di base è applicare al PM il principio ispiratore di Adaline. Definito l'errore E come nella formula sottostante (D = uscita desiderata, O = uscita prodotta dalla rete), modifichiamo ciascun peso di posto (i,j), collegante il neurone i-esimo di uno strato con il neurone j-esimo dello strato successivo, mediante un termine che sia indicativo del fatto che ci stiamo movendo nella direzione discendente del gradiente, e quindi sarà proporzionale secondo un coefficiente di tipo learning rate all'opposto della derivata parziale rispetto al peso considerato.

L'algoritmo di Back Propagation (BP). È costituito da due cicli. Il più esterno viene ripetuto finché non si raggiunge una condizione di terminazione la quale, dato che il modello rientra nella categoria del performance learning, consiste nella minimizzazione dell'errore E. L'addestramento cioè prosegue finché non si ritiene di aver raggiunto, a partire dai campioni presentati all'ingresso, un sufficiente livello di apprendimento.

L'apprendimento vero e proprio, ripetuto ad ogni occorrenza su tutti i campioni del TS, avviene nel ciclo interno. La particolare struttura di tale ciclo interno dà il nome all'algoritmo, che potrebbe essere tradotto come 'retro-propagazione'. Nella fase di forward il generico campione p viene posto in ingresso alla rete, ciascun neurone effettua i propri calcoli e lo strato di output presenta l'uscita relativa al p-esimo campione. Si effettua quindi una valutazione dell'errore come scarto quadratico (l'algoritmo è supervisionato: si sfrutta la conoscenza dell'uscita desiderata per ciascun campione e per ciascun neurone)[12]. Infine nella fase di backward si adopera il valore dell'errore appena calcolato per modificare di conseguenza i pesi secondo la formula vista per Dw_ij: in queste modifiche consiste in effetti l'apprendimento. L'algoritmo, di cui è stata matematicamente dimostrata la convergenza, segue un training by pattern, dato che la matrice dei pesi viene modificata per ogni singolo campione d'ingresso, ma potrebbe essere riscritto nella filosofia del training by epoch: sarebbe sufficiente spostare la fase di backward all'esterno del ciclo for, in modo che questa venga effettuata solo dopo aver calcolato l'errore quadratico sull'intero TS (si tratterà, a questo punto, un errore quadratico medio perché non più relativo ad un singolo esemplare). Il numero di epoche può essere più o meno elevato in ragione della cardinalità N_tr del TS: per 10.000 esemplari può essere sufficiente un centinaio di epoche, cosicché si abbia un milione di passi di addestramento. Il tempo di addestramento può essere quindi molto elevato; sono state proposte alcune variazioni sul tema di questo algoritmo finalizzate a migliorare l'efficienza.

Riportiamo a destra le espressioni dell'errore relativo al p-simo campione e del gradiente, funzionali al calcolo della modifica al vettore dei pesi. o_pk e y_pk sono rispettivamente l'uscita effettiva e desiderata del neurone k. I passaggi sono ottenuti applicando il teorema di derivazione delle funzioni composte. Nel risultato finale appare la derivata della funzione di attivazione, per cui tale funzione dev'essere per ipotesi differenziabile.

Possono essere scelte varie funzioni di attivazione: il grafico seguente ne illustra quattro tra le più comuni. La funzione a soglia (a) e lineare (b) presentano il problema di non essere derivabili in tutti i punti. Nei punti angolosi si potrà effettuare una derivazione per continuità. La (b) (in particolare, l'identità) è la funzione di attivazione di Adaline.

Un'altra è la funzione sigmoidale, per la quale è riportato in calce alla figura il calcolo della modifica ai pesi. Ricordiamo che 'net' sta per 'uscita netta', ovvero senza l'applicazione della funzione di attivazione. La sigmoide, limitata tra 0 e 1, presenta la caratteristica di avere derivata (pendenza) massima intorno all'origine e derivata nulla. Ciò implica che quanto più l'uscita del neurone, che è sempre compresa tra questi due valori, si mantiene intorno al valore zero, tanto maggiormente l'algoritmo di apprendimento modificherà il vettore dei pesi. Infatti se tale uscita è in modulo molto grande darà luogo ad una derivata quasi nulla, dal momento che la sigmoide tende asintoticamente a due valori costanti (0 a sinistra e 1 a destra).

Diamo ora una risposta alla domanda lasciata da lungo tempo in sospeso: come modificare i pesi per lo strato nascosto, quello per il quale non conosciamo le uscite desiderate.

Il problema viene risolto molto semplicemente osservando che ciò che serve in ultima analisi è il gradiente dell'errore; non c'è una vera necessità di conoscere le uscite desiderate. Basta allora esplicitare per lo strato hidden la dipendenza dai pesi da parte dell'errore, e applicare la regola di derivazione delle funzioni composte. L'uscita o_pk del neurone di output dipende dal i_pj, che è a sua volta dipendente da w_ji. i_pj è l'uscita prodotta del j-simo neurone dello strato hidden, che dipende evidentemente non solo dagli ingressi ma anche dai pesi del neurone stesso (ovvero i pesi ingresso-hidden).

Si noti come sono state espresse le derivate parziali. Due di esse sono semplicemente il peso w_kj^o e l'ingresso x_pi. Le altre due sono derivate della funzione di attivazione, che dunque anche per lo strato hidden dev'essere differenziabile.

Il PM: funzionamento da classificatore. Nel PM classificatore si usa per le uscite un 'codice decodificato': si mettono nello strato di uscita tanti neuroni quante sono le classi. Ad esempio, se abbiamo tra classi A, B e C e si presenta un ingresso A, ci aspettiamo che l'uscita varrà 1 per il neurone di uscita relativo alla classe A e 0 per gli altri due. In pratica, l'uscita della rete non sarà in generale binaria, ma composta di numeri reali, ad esempio i neuroni dell'ultimo strato forniscono le uscite A=0.8, B=0.11, C=0.09. Si adotta allora l'ovvia strategia del tipo 'winner takes all' (WTA): 'vince' la classe associata al neurone che ha l'uscita più alta. Il campione in ingresso viene attribuito quindi alla classe A. Naturalmente tale strategia può dar luogo a delle incertezze. Infatti due delle uscite potrebbero essere troppo vicine fra di loro perché si possa ritenere vincente una delle due.

Il disegno che segue illustra il comportamento di un percettrone in vari contesti. Facciamo l'ipotesi di dover discriminare fra due classi soltanto. In presenza di un single layer le regioni di decisione sono dei semipiani limitati da un iperpiano. Per il problema della xor e quello subito dopo, in cui figurano regioni del piano posizionate in modo da rendere necessaria una separazione piuttosto articolata, la struttura a single-layer fallisce senz'altro. La struttura a due livelli è in grado di generare regioni di decisioni convesse, ma aperte. I due percettroni dello strato hidden dividono il piano in semipiani mediante delle rette; lo strato di uscita 'compone' le regioni di decisione. Se lo strato hidden conta tre nodi, otterremo una regione aperta delimitata da tre rette come nell'esempio più a destra. La struttura riesce così a risolvere il problema della xor, ma, con due nodi soltanto, non il secondo problema. Nel caso di tre strati (due nascosti) la forma delle regioni di decisioni può essere qualunque: possono essere anche 'forate'. Tre strati sono quindi teoricamente sufficienti a risolvere qualsiasi problema. Tuttavia all'aumentare del numero di strati la convergenza diviene molto più lenta, per cui generalmente si opta per una struttura a due strati con un numero adeguato di neuroni.

Fra i problemi presentati dalla reti a percettroni vi è la presenza di minimi locali, problema che si cerca di aggirare ricorrendo a opportune variazioni nella back propagation. Conseguenze negative sono legate anche all'overtraining: un eccessivo addestramento della rete. La rete si specializza troppo, e l'errore tende addirittura ad aumentare col numero di epoche. Citiamo anche il problema del flat spots: una errata inizializzazione dei pesi (es. positivi ed elevati) può portare in una zona dell'asse delle ascisse nel piano della funzione di attivazione in cui la derivata è praticamente nulla. In particolare, i pesi devono essere sia positivi che negativi, ed il loro valore dev'essere relativamente piccolo rispetto al numero N di neuroni: generalmente il loro valore è scelto come compreso tra .

Il teorema di Kolmogorov. Consideriamo una qualunque funzione continua ad n ingressi ed m uscite, che assume valori tra 0 e 1. Essa può essere esattamente implementata da una RN feed-forward a 3 strati, con (2n+1) elementi nello strato nascosto e m nello strato di uscita. La funzione di trasferimento del secondo strato è semilineare, ovvero simile ad una somma pesata lineare. Quella del terzo strato è invece altamente non lineare. Il teorema non specifica però la forma di quest'ultima funzione di trasferimento, dicendo solo che dipende da certi parametri, né indica come calcolare i pesi. La sua utilità pratica quindi è modesta.

L'ARCHITETTURA LVQ. Questa rete presenta due strati, uno di input e uno di computazione/uscita, detto strato di Kohonen. Funziona da classificatore: attribuisce un elemento a una fra M possibili classi. Allo scopo, in fase di definizione dell'architettura i neuroni sono etichettati in modo da appartenere alle varie classi. A differenza del multilayer perceptron, si hanno in generale più neuroni per ciascuna classe. Il numero di neuroni associati alle classi può essere differente per le varie classi.

Alla fine del processo di addestramento, ciascun neurone rappresenterà un prototipo dei campioni della classe alla quale esso è ascritto. In altre parole, ciascun neurone modellerà i soli campioni del TS che appartengono alla classe a cui è stato preventivamente associato. Nella figura che segue, N neuroni sono stati assegnati alla classe 1 e ne dovranno modellare i campioni.

Questo è un punto molto importante. Nel modello PM non c'è modo di dire, osservando la configurazione della rete, come la conoscenza è distribuita in tutti i suoi punti. Di conseguenza un PM non è neanche in grado di giustificare le risposte che fornisce. Nel caso in esame invece i neuroni danno più informazione. È più facile effettuare un 'post-processing' del risultato della rete, spiegando il modo in cui è stato ottenuto.

L'apprendimento è di tipo competitivo. Si noti che ciascun ingresso è connesso a tutti i neuroni. I pesi hanno un significato diverso rispetto al caso PM: non viene calcolata una somma pesata, ma ciascun neurone determina la distanza tra il vettore d'ingresso ed il proprio vettore dei pesi i due vettori hanno la stessa dimensione). Il vettore dei pesi attribuito a ciascun neurone rappresenta appunto il prototipo dei campioni del TS cui si accennava prima. Quando un vettore si presenta in ingresso alla RN, si scatena la competizione: si stabilisce quale dei neuroni si trova a distanza minima da esso, cioè quello il cui vettore dei pesi, rappresentativo di una certa classe, è più vicino all'ingresso. La metrica usata per computare tale distanza è quella euclidea (radice quadrata della somma dei quadrati delle differenze). Il
neurone vincitore è l'unico al quale è concesso di modificare i propri pesi.

In fase operativa viene presentato un ingresso e ciascun neurone calcola la distanza rispetto ai propri pesi. L'uscita dei neuroni varrà 1 per quello il cui vettore dei pesi è maggiormente vicino a quello degli ingressi, 0 per tutti gli altri. Ovviamente per conoscere l'identità del neurone vincitore è necessario che ogni neurone scambi informazioni con i tutti gli altri del proprio strato. Ecco perché la rete è a connessioni laterali. Queste ultime sono usate dai neuroni per inviare ai propri compagni di strato la distanza dall'ingresso. Naturalmente questo è vero solo in senso formale: all'atto pratico sarà sufficiente utilizzare un algoritmo che calcoli il minimo in un vettore.

Abbiamo introdotto la scorsa lezione il paradigma PVQ. Soltanto un neurone può cambiare i propri pesi in fase di addestramento: quel neurone che ha minima distanza dall'ingresso. L'utilizzo tipico è di classificatore ad M classi; N neuroni sono attribuiti a ciascuna classe. Ciascun neurone rappresenta un prototipo per gli elementi della classe che rappresenta.

Consideriamo l'algoritmo LVQ1. Con w_i, w_j e w_n abbiamo rappresentato i vettori dei pesi associati ai neuroni dello strato di Kohonen: nel nostro esempio supponiamo che siano 3. Immaginiamo che ogni ingresso x abbia due dimensioni (due componenti). Ciascun neurone calcola la distanza euclidea fra il proprio vettore dei pesi e l'ingresso x. Il neurone w_n che ha la distanza minima d_i 'vince' la competizione. Si verifica quindi se l'attribuzione dell'ingresso alla classe del neurone vincitore è corretta. Tale verifica è possibile, perché essendo l'apprendimento supervisionato si conosce la classe di appartenenza dell'ingresso. In caso affermativo, il neurone viene 'premiato' avvicinandolo alla classe x (regola R1). Altrimenti w_n viene penalizzato allontanandolo dalla classe in questione (il riconoscimento è errato: regola R2). In tal modo, quando x si ripresenterà in ingresso è più probabile che il neurone 'giusto' (quello della classe x) sia abbinato ad esso.

Dal punto di vista geometrico, tutto ciò equivale a sommare o sottrarre al vettore w_n una frazione del vettore (x-w_n) che congiunge w_n a x, ottenendo il nuovo vettore w'_n (vedi il grafico con i vettori). I coefficienti a e g devono essere tarati in maniera opportuna; sono infatti i responsabili della convergenza dell'algoritmo. In particolare, essi non devono essere costanti ma variabili nel tempo. Si fa in modo che essi assumano valore massimo 1 all'inizio per poi decrescere verso lo zero linearmente con il numero di epoche (a = 1-T/T_MAX, essendo T_MAX il numero massimo di epoche e T l'epoca corrente).

L'algoritmo, che è supervisionato nella versione base, può essere reso non supervisionato per problemi di clustering: si lascia che i prototipi evolgano liberamente, occupando in corso di apprendimento una determinata posizione nello spazio delle caratteristiche per divenire rappresentativi dei campioni. In questa variante, i neuroni non sono preassegnati alle classi, e il neurone vincitore viene sistematicamente avvicinato alla classe di appartenenza dell'ingresso: scompaiono le righe di codice che iniziano per IF ed ELSE.

La figura che segue fa riferimento proprio al caso non supervisionato. Si hanno 4 raggruppamenti o cluster di campioni (i punti). Supponiamo di avere uno strato di Kohonen con 4 neuroni. Desideriamo pertanto che alla fine del ciclo di addestramento i 4 neuroni vadano a posizionarsi ciascuno in uno dei 4 cluster assegnati. Ipotizziamo che tutti i neuroni abbiano dei pesi tali da essere concentrati in partenza nel punto (1,0).

Si presenta il primo campione del TS. Poiché tutti i neuroni hanno il vettore rappresentativo nello stesso punto (1,0), è evidente che avranno tutti e 4 la medesima distanza dal campione in questione. Se ne sceglie uno a caso, a cui viene dato l'agio di modificare il proprio vettore dei pesi. Il neurone vincitore si avvicina al campione d'ingresso. Quando si presenta un secondo campione, a qualunque cluster esso appartenga (anche se diverso dal primo), il neurone che ha vinto per estrazione a sorte la prima competizione vincerà, questa volta legittimamente, anche la seconda, avvicinandosi (mediante una modifica al vettore dei pesi) al campione d'ingresso. Il neurone si av

vicina sempre di più alla zona dello spazio dove sono localizzati i cluster; gli altri tre rimangono 'fermi al palo'. Ciò è del tutto indipendente dall'ordine in cui si presentano i campioni d'ingresso.

Ciò dà luogo ad un problema abbastanza fastidioso: quello che va sotto il nome di sottoutilizzo dei neuroni. Il neurone vincitore si avvicina con traiettoria oscillante ai cluster. Non si ha vera e propria convergenza, e per di più tutti e 4 i cluster vengono ad essere rappresentati dallo stesso neurone, che si mantiene in qualche modo equidistante da essi: gli altri tre non entrano mai in gioco. Tale problema si riscontra, sia pure con effetti meno critici, anche nel caso supervisionato.

Varie proposte sono state avanzate per risolvere il problema: parleremo di due di esse in particolare, l'algoritmo cosiddetto 'della coscienza' e l'algoritmo FSCL. Essi sono accomunati dalla scelta di ricorrere ad una definizione non costante di distanza (quella che viene usata per la competizione); i neuroni che 'vincono troppo spesso' vengono penalizzati rispetto agli altri, in modo che tutti abbiano le stesse opportunità di vittoria.

Per FSCL (Frequency Sensitive Competitive Learning) la modifica nel calcolo della distanza consiste nel moltiplicare la distanza euclidea per la frequenza relativa di vittorie del neurone: d'_i = d_i*F_i. Questo algoritmo modifica non uno ma due neuroni per volta: vengono considerati i due neuroni più vicini all'ingresso; il primo viene ulteriormente avvicinato, il secondo ne viene invece allontanato. FSCL costituisce un approccio generalmente efficace, ma è possibile dimostrare anche il suo fallimento in certi casi.

In C²L (Conscience Learning) la distanza viene diminuita attraverso il peso (bias) bi, secondo le formule d"_i = d_i-b_i e b_i = c*(1/N - f_i). 'c' è un valore intero, N il numero dei neuroni e f_i la frequenza relativa di vittoria. Si osservi che in caso di equiprobabilità di vittoria (è la situazione ottimale), f_i = 1/N e quindi b_i = 0, cioè la distanza del neurone è esattamente quella euclidea d_i. Se un neurone vince troppo spesso, la sua frequenza di vittoria diviene maggiore di 1/N: finiamo con l'aggiungere qualcosa a d"_i, invece di diminuire tale quantità: il neurone che vince troppo viene penalizzato.

La rete LVQ realizza la cosiddetta 'Tassellazione di Voronoi' (vedi figura sovrastante). I numeri piccoli rappresentano ciascuno un punto dello spazio in cui vengono a trovarsi i vari neuroni: il neurone numero 12 si trova nel punto occupato dal numero. Per capire qual è la regione di decisione occupata dal neurone 12 basta considerare tutti i punti aventi distanza da tale neurone che è minore della distanza di altri neuroni. Si noti ad esempio che la linea che separa i neuroni 11 e 12 è il luogo dei punti equidistanti da tali neuroni (è facile rendersene conto). L'insieme delle linee così costruite (perpendicolari alle congiungenti di ogni coppia di neuroni nei punti medi) delimita le regioni di decisione. Posizionando opportunamente i neuroni, possiamo ottenere configurazioni di regioni di decisione comunque complesse, incluse quelle del multilayer perceptron a 3 strati.

I grafici che seguono fanno vedere come l'algoritmo LVQ1, per particolari sottoinsiemi di dati, raggiunga prestazioni poco lusinghiere: comunque si faccia variare il learning rate, esso non supera il 70% del riconoscimento (con un valore di n molto elevato). Con lo stesso TS, FSCL e C²L raggiungono prestazioni migliori (in particolare il primo, che sfiora il 100% di corretta classificazione). Ovviamente utilizzando il Test Set anziche il TS (Training Set) si hanno prestazioni inferiori di un buon 5%[13].

LE MAPPE AUTOORGANIZZANTI DI KOHONEN (SOM). Questo strumento presenta due differenze sostanziali rispetto al meccanismo LVQ. Innanzitutto, l'apprendimento è sempre non supervisionato. Inoltre, dal punto di vista topologico, i neuroni sono disposti a griglia. La posizione di ciascun neurone nella griglia è definita in un modo simile a quanto avviene nelle matrici: il neurone (1,2) sarà quello situato nella riga 1, colonna 2 della griglia. La topologia è descritta attraverso connessioni che hanno però un significato diverso rispetto ai casi visti fin qui (non c'è difatti un peso associato a ciascuna connessione). La rete di Kohonen viene sollecitata con certi punti; ciascuno di essi, in uno spazio (u,v), rappresenta il punto terminale di un 'braccio' a due giunti. Alla rete pervengono quali ingressi non le coordinate (u,v), ma i due angoli q e f che ne determinano la posizione (v.figura). È la rete stessa a realizzare la giusta corrispondenza topologica tra i due spazi. Ad esempio il neurone (1,1) si auto-organizza, divenendo rappresentativo dei punti dello spazio (q f) corrispondenti a punti dello spazio (u,v) a loro volta corrispondenti all'angolo in alto a sinistra della griglia.

Nelle reti LVQ un solo neurone poteva muoversi in occasione di ciascun ciclo di addestramento. Come si è visto, ciò può portare come conseguenza il sottoutilizzo dei neuroni. Nelle SOM il problema del sottoutilizzo viene aggirato in un modo del tutto peculiare. Consideriamo la legge di apprendimento:

Ricordiamo che (q f) è l'ingresso x. Se trascuriamo l'elemento (z,t), abbiamo una legge molto simile a quella di LVQ. Una prima differenza sta nel fatto che in linea di principio i pesi di tutti i neuroni possono essere modificati. Tuttavia il coefficiente a_i varia, oltre che col tempo t (decresce nel tempo), anche col parametro z, a sua volta dipendente dalla distanza del neurone i-esimo dal neurone vincitore. La distanza in questione non è da intendersi in senso euclideo, ma misurata sulla griglia di cui si diceva. Ad esempio i neuroni (1,2) e (2,2) sono a distanza 1. Quindi, ciascun neurone ha 4 neuroni a distanza 1 da sé stesso. In particolare, a_i diminuisce quanto più ci si allontana sulla griglia. Quindi insieme al neurone vincitore, sono 'coinvolti' nella vittoria quelli che si trovano nei suoi paraggi; anch'essi cioè sono messi in condizione di modificare significativamente i propri pesi; per tale motivo a_i viene detto fattore di neighbour (=vicinanza). L'intorno dei neuroni che risultano avvantaggiati del neurone vincitore può dunque variare nello spazio (possono essere coinvolti tutti i neuroni a distanza massima 1, o a distanza massima 2 etc.) e nel tempo.

Si notino i grafici a destra. Inizialmente, tutti i neuroni di Kohonen sono concentrati nell'origine (ovvero lo sono i loro vettori dei pesi). Quando presentiamo alla rete ingressi (q f) corrispondenti a punti (u,v) del piano, 'vincerà' il neurone il cui vettore dei pesi ha la distanza più piccola dall'ingresso. Tale neurone prende a muoversi (in un piano equivalente a (u,v)) portandosi appresso un certo numero di altri neuroni. All'aumentare dei cicli la rete di neuroni tende ad espandersi; dopo 100.000 cicli i neuroni avranno occupato tutto lo spazio disponibile. Una configurazione 'regolare' come quella del grafico in basso a destra è possibile tuttavia solo se anche la configurazione iniziale denotava una certa corrispondenza topologica, ad esempio se il neurone (1,1) si trovava nell'angolo nord-ovest dell'agglomerato iniziale, il neurone (1,N) in quello nord-est e via dicendo. In caso contrario la rete finale può risultare 'intrecciata' come quella del disegno a sinistra (twisted mesh).

LLa SOM può essere stimolata con punti prelevati da un spazio bidimensionale diverso, ad esempio di tipo triangolare. Possiamo anche avere SOM lineari (e non griglie bidimensionali). In ogni caso, i neuroni si posizionano in modo da occupare tutto lo spazio disponibile, comportandosi alla stregua di un gas che tende ad assumere la forma del recipiente che lo contiene.

Interessante applicazione delle SOM di Kohonen è lo scrittore fonetico realizzato dallo stesso Kohonen (1988). Lo strumento era un rudimentale riconoscitore vocale capace di far apparire sullo schermo le lettere di una parola pronunciata da un utente umano. Le parole venivano opportunamente campionate (9.83 ms), e a ciascuna parola si associava un vettore a 15 componenti, ciascuna dei quali corrispondente ad una componente frequenziale della parola stessa. La rete veniva quindi sollecitata presentando in ingresso i risultati del campionamento delle parole.

Si noti la 'mappa fonotòpica' a sinistra, in cui a ciascun neurone è associata una lettera. Punto di partenza è realizzare il fatto che le SOM, pur non essendo supervisionate, possono essere usate come classificatori. Questo lo si può fare, dopo un primo training non supervisionato, sottoponendo nuovamente il TS alla mappa auto-organizzante. In questo secondo caso il training sarà però 'labellato'. Supponiamo di conoscere la classe di appartenenza di ciascun campione: sappiamo ad esempio che un certo numero di esemplari si riferiscono alla lettera 'a'. Per ciascun neurone andiamo quindi a vedere per quali campioni del TS è risultato essere il neurone vincitore. Attribuiremo quel neurone alla classe per la quale si siano verificati il maggior numero di riconoscimenti. Ad esempio se un neurone ha vinto 12 competizioni, e in 10 occasioni su 12 è stato associato alla classe 'lettera a', etichetteremo quel neurone come appartenente alla 'classe a'. Se il neurone vince 15 competizioni, e risulta essere 8 volte vicino alla 'classe a', e le altre 7 alla 'classe h', esiste evidentemente una incertezza: quel neurone viene attribuito ad una classe 'ah', per cui, se è lui a vincere in fase di esecuzione, il suono potrebbe essere tanto quello di una 'a' quanto quello di una 'h'.

A destra è indicato l'esempio della pronuncia della parola finlandese humppila. La parola viene campionata a 9.83 ms; ogni singolo campione viene processato dalla rete attraverso la sequenza di attivazioni dei neuroni indicata a destra. Con questo strumento si riusciva ad ottenere una percentuale di riconoscimento corretto del 92-97%.

LA RETE DI HOPFIELD. È un esempio rete ricorrente, per il quale non studieremo un algoritmo di addestramento. Ci sono differenze significative rispetto ai precedenti modelli. Ogni neurone è collegato a tutti gli altri attraverso dei pesi. Lo stesso vettore x è contemporaneamente ingresso, stato e uscita della rete. L'utilizzo tipico della rete di Hofield, come si è detto, è quello di memoria associativa: presentiamo un ingresso, e la rete ricerca lo stato stabile più vicino a tale ingresso. In fase di apprendimento la rete memorizza un certo numero di informazioni, detti stati stabili (o configurazioni), rappresentati da vettori x_i. In modalità operativa la rete, ricevuto un vettore iniziale, ricalcola - modificandolo - il proprio stato sulla base dei pesi colleganti i vari neuroni. La funzione di attivazione che permette il ricalcolo dello stato è indicata di seguito.

I neuroni evolvono quindi, modificando il proprio stato, fino al punto che la rete raggiunge una configurazione stabile (memorizzata) simile a quella che è stata presentata in ingresso. Durante ogni ciclo, ciascun neurone x_i verifica se è il caso di modificare il proprio stato. Lo stato memorizzato, come si vede, è binario (può valere soltanto 1), quindi gli stati stabili che possono essere raggiunti sono vettori di +1 o -1. Ogni neurone calcola la somma pesata dell'ingresso per il vettore dei pesi delle connessioni che lo congiungono a tutti gli altri neuroni della rete (si noti che ogni neurone è connesso anche a sé stesso). Se il risultato è superiore ad una soglia, il nuovo stato dell' i-esimo neurone è 1; se è inferiore, è -1; se uguale alla soglia, non si ha modifica dello stato.

Si può dimostrare che il processo converge. Alla rete viene associata una funzione di energia; il suo valore diminuisce (o rimane inalterata) in corrispondenza di ogni modifica dei pesi. Quindi dopo un certo numero di iterazioni si raggiunge senz'altro il minimo di tale funzione (quando DH=0 per tutti i neuroni, siamo pervenuti ad uno stato stabile).

Qualche applicazione. Abbiamo una rete di Hopfield a 256 neuroni, rappresentati ciascuno da un quadratino. Se il quadratino è nero, lo stato vale +1, altrimenti -1. Durante il processo di addestramento, la rete riceve in ingresso un certo numero di immagini (stati stabili), ognuna delle quali corrispondente ad una lettera dell'alfabeto.

In fase operativa presentiamo alla rete una lettera 'e' 'corrotta' da un certo rumore (vedi figure che seguono). Dopo 2 e 6 iterazioni la rete raggiunge la seconda e terza configurazione mostrate nella figura; associa infine all'ingresso lo stato stabile che risulta più vicino ad esso. Il riconoscimento è andato a buon fine. L'uscita della rete non viene quindi determinata immediatamente, ma attraverso un processo iterativo, consistente nell raggiungere, a partire da uno stato iniziale, uno stato stabile finale corrispondente al minimo di una funzione di energia. Il problema è che la rete può giungere anche ad uno stato stabile 'spurio', cioè non compreso fra quelli che erano stati memorizzati durante l'addestramento (comportamento indesiderato) (il fenomeno corrisponde al problema dei minimi locali della funzione di errore).

Il problema del commesso viaggiatore. Abbiamo una rete 10x10, nella quale i neuroni sono però continui (possono assumere valori continui tra 0 (assenza di quadratino) e 1 (quadratino 'pieno')). Dalla configurazione iniziale la rete evolve verso la finale (la quarta) attraverso la minimizzazione della funzione di energia. In tale funzione dovremo inserire tutti quei vincoli che riguardano il problema del commesso viaggiatore. In sostanza, nella configurazione iniziale dovremo avere un solo quadratino pieno per ogni riga, un solo quadratino pieno per ogni colonna ed un percorso minimo che collega tutti i quadratini. Il percorso ottimo trovato dalla rete muove attraverso le città D-H-I-F-G-E-A-J-C-B.

Una rete di Hopfield può quindi essere impiegata per risolvere un problema di ottimizzazione; il problema sta nel trovare una opportuna funzione di errore da minimizzare. È interessante notare che, al contrario di quanto avviene negli algoritmi classici di programmazione lineare, per le soluzioni parziali i vincoli non sono necessariamente soddisfatti (rilassamento dei vincoli); lo sono solo per la soluzione finale[14].

---