Appunti di Intelligenza artificiale: metodi e applicazioni sui sistemi formali

Infatti uno stesso teorema potrebbe essere dimostrato applicando una diversa sequenza di

regole di inferenza.

Piuttosto che associare ad un nodo genitore - tramite l’apposita regola di inferenza - un nodo

filgio corrispondente ad un teorema già presente nell’albero, si potrebbe collegare l’arco

direttamente a quel nodo rappresentante il teorema.

>> Questo grafo è un esempio di SSR (che vedremo più avanti); in questo caso gli stati sono

stringhe e quindi possiamo inserirle direttamente nei nodi, piuttosto che rappresentarli

simbolicamente con S0, S1, …, Sg

Il motore inferenziale si ferma solo quando ha espanso tutti i nodi e non sono possibili

ulteriori espansioni (non ci sono altre regole di inferenza da applicare ai teoremi ottenuti)

Tuttavia, potrebbe accadere di avere regole di inferenza sempre applicabili. In tal caso, si

potrebbe finire per avere un grafo di profondità infinita.

Il fatto che l’albero generato dal motore inferenziale sia infinito è però un problema

Nel caso di un teorema fissato non dimostrabile, il nostro sistema inferenziale non si

fermerebbe mai, continuerebbe ad espandere un albero di lunghezza infinita alla ricerca di

una soluzione che di fatto non c’è.

In questo caso, il sistema esperto si dice non decidibile: il suo motore inferenziale non si

ferma mai, in tal modo non ci permette di rispondere ne sì, né no alla domanda inizialmente

posta.

In sostanza, un sistema esperto non decidibile non ci fornirà mai una risposta, perché il suo

motore inferenziale non si fermerà mai.

Tuttavia, ad un certo punto saremo costretti ad interrompere il funzionamento del sistema

(ad esempio, si esaurirà la memoria del calcolatore)

Dato che possiamo non sapere dapprima che la domanda posta sia o meno rispondibile,

interrompendo prematuramente l’esecuzione del sistema rimmarremo col dubbio che magari

- se gli avessimo concesso ulteriore tempo - il motore inferenziale sarebbe potuto riuscire a

risolvere il quesito.

In sintesi, un sistema non decidibile non consente di prende una decisione.

La non decidibilità di un problema dipende sia dal sistema che dalla domanda iniziale.

Ammesso che l’albero sia infinito:

-​ Il problema è certamente non decidibile per tutte le domande per le quali non c’è

risposta

-​ Il problema è decidibile per le soluzioni esistenti, a patto di lasciar girare il motore

inferenziale per un tempo sufficientemente lungo

Per rendere decidibile in ogni caso un problema si fa in modo che lo spazio delle possibili

risposte risulti finito.

In tal modo una risposta viene comunque restituita: se è negativa, non possiamo essere

sicuri che il teorema sia effettivamente indimostrabile.

Fino a questo punti, siamo partiti dai nostri assiomi e abbiamo applicato le regole di

inferenza fino a giungere ai teoremi finali (salvo casi di soluzioni inesistenti), tale

meccanismo è noto come data driven o forward.

Nulla ci vieta però di fare un ragionamento inverso, ossia scegliere come nodo iniziale il

teorema finale da dimostrare, e procedere a ritroso.

Quello che andremo a fare sarà l’unificazione con la postcondizione (anziché la

precondizione) e cercare di dimostrare la precondizione.

Se procedendo a ritroso riusciamo a raggiungere gli assiomi del sistema, abbiamo

dimostrato il nostro teorema. Tale meccanismo è noto come goal driven o backward.

Il motore inferenziale del Prolog è goal driven.

I 2 requisiti che devono essere posseduti da un sistema formale sono: coerenza e

completezza:

-​ un sistema formale con la sua interpretazione si dice coerente, se ogni teorema da

esso derivato corrisponde - alla luce dell’isomorfismo - ad una verità del mondo reale

-​ un sistema formale con la sua interpretazione si dice completo, se tutti i teoremi del

mondo reale sono da esso derivabili

Non si tratta di proprietà intrinseche dei soli sistemi formali, bensì dei sistemi formali con la

loro interpretazione.

Quindi:

-​ tutto ciò che afferma il sistema formale è vero

-​ tutto ciò che è vero è rappresentabile col sistema formale

Dalla definizione scaturisce che un sistema formale coerente è credibile solo quando

risponde di sì.

Se risponde di no, nel senso che dopo aver esplorato tutto lo spazio degli stati non arriva a

dimostrare un teorema, non è credibile a meno che non ne sia dimostrata anche la

completezza.

Invece, un sistema formale completo è credibile solo risponde di no, mentre non è credibile

se risponde di sì.

Il sistema PG è sicuramente coerente, perché qualunque stringa ricavata in esso - letta alla

luce dell’isomorfismo - corrisponde ad una verità

Il sistema PG non è completo; ad esempio, *p*p*g*** (ossia 1+1+1=3) - proposizione vera

nel mondo reale - non è dimostrabile nel contesto di PG.

Esso quindi non è in grado di dimostrare un teorema del quale nel mondo reale è ben nota

la veridicità. Ciò dipende dal fatto che le regole di inferenza consentono a PG di costruire

solo le somme a 2 addendi. In questo caso, occorre estendere il sistema formale.

SF coerente ogni teorema derivato corrisponde, alla luce credibile solo quandi risponde di sì

dell’isomorfismo, ad una verità del mondo

reale

SF completo tutti i teoremi del mondo reale sono da esso credibile solo quando risponde di no

derivabili

Dunque, il sistema ideale è quello credibile sia nel sì che nel no, cioè che sia coerente e

completo.

Esistono 2 modi prinipali per rappresentare un problema attraverso un SF:

-​ La rappresentazione per decomposizione in sottoproblemi

-​ La rappresentazione nello Spazio degli Stati o SSR

Nella SSR un problema può essere descritto attraverso un insieme S di stati, dove ogni stato

corrisponde ad una soluzione parziale di un problema.

Un SSR semplifica di molto la risoluzione di un problema.

Infatti, non occorre andare a trovare un algoritmo ma ci basta formalizzare il problema

proprio attraverso essa.

Sarà la strategia di ricerca del motore di inferenza a trovare l’algoritmo in questione.

Per decidere l’ordine di esplorazione di uno spazio degli stati possiamo adottare 2 diverse

strategie di ricerca: ricerca in ampiezza e ricerca in profondità.

Tali strategie prevedono il raggiungimento dell’obiettivo con costi diversi ed esplorando un

numero diverso di stati.

Per comprendere tali strategie di ricerca, dobbiamo prima comprendere come rappresentare

uno spazio degli stati S attraverso cui navigare.

Gli assiomi del problema sono rappresentati dallo stato iniziale S0

Gli elementi di S sono una rappresentazione concreta delle soluzioni che il sistema ha

trovato durante il processo di determinazione delle soluzioni.

Le regole di inferenza si traducono in una funzione di transizione che - dato uno stato Si -

consente di costruire un insieme di stati da esso derivati.

L’applicazione ripetuta delle regole di inferenza determina un grafo che rappresenta lo

spazio degli stati.

In generale, uno stato può essere descritto da un percorso che parte dallo stato iniziale S0 e

si sviluppa attraverso l’applicazione di una successione di regole.

All’interno del grafo rappresentante lo spazio degli stati, alcuni stati sono raggiungibili

attraverso più percorsi.

Possono inoltre essere presenti dei cicli, per cui l’applicazione di una regola ad uno stato

può far ritornare il sistema ad uno stato già considerato in precedenza.

Lo stato finale che vogliamo raggiungere ci viene indicato dal predicato (il teorema finale)

In generale, un problema prevede che il predicato sia soddisfatto da più stati.

Per tale motivo, parliamo di predicato obiettivo (o predicato goal) e non di stato obiettivo.

A questo punto, partendo dallo stato iniziale vorremmo sapere qual è il percorso che ci

permetta di giungere ad uno stato che soddisfi il predicato obiettivo.

Esistono numerose strategie di ricerca della soluzione.

Abbiamo 2 proprietà:

-​ ricerca cieca

-​ ricerca informata

L’algoritmo di ricerca cieca non sfrutta la conoscenza delle caratteristiche del problema, ma

solo il relativo grafo degli stati; si limita a percorrere il grafo stato per stato finché non trova

quello corrispondente alla soluzone (ammesso che lo trovi)

L’indipendenza dalla natura del problema è il vantaggio e lo svantaggio di questa strategia:

-​ vantaggio → l’ingegnere della conoscenza deve limitarsi a costruire la SSR

-​ svantaggio → il grafo che rappresenta la SSR può essere molto grande o addirittura

infinito, il che renderebbe costoso in termini computazionali l’algoritmo di ricerca della

soluzione

L’algoritmo di ricerca informata o euristica sfrutta la conoscenza che si possiede sulla

natura del problema per indirizzare in maniera mirata l’algoritmo del motore inferenziale

verso la soluzione del problema.

L’ingegnere in questo caso, oltre a formulare il problema in termini di sistema formale, deve

fornire la conoscenza sufficiente a guidare l’algoritmo di ricerca.

Il vantaggio è che i tempi di ricerca si abbreviano notevolmente.

Dopo aver analizzato la strategia di ricerca, possiamo concentrarci su un’ulteriore distinzione

che riguarda la direzione in cui procede l’algoritmo di ricerca all’interno del grafo.

Il modo naturale di procedere è quello di partire dallo stato S0 e cercare - attraverso

l’applicazione delle regole - il percorso che porta a Sg; questa modalità è nota come

forward search o FS

Al contrario, possiamo partire dallo stato finale Sg e, applicando a ritorso le regole sel

sistema formale, possiamo risalire la catena degli stati tentando di raggiungere lo stato di

partenza S0; questa modalità è nota come backward search o BS

Per analizzare pro e contro delle due modalità, poniamoci nel caso in cui il nostro grafo sia

semplicemente un albero.

Nella ricerca FS, per ogni livello e per ogni stato via via aggiunto dobbiamo prendere in

considerazione tutte le strade alternative.

Supponiamo di avere n regole di inferenza, le regole applicabili per ogni stato saranno quindi

al massimo n

Supponendo che si verifichi sempre il caso peggiore, abbiamo n alternative per il primo

livello (che prevede un solo stato), n^2 alternative per il secondo livello, n^3 alternative per il

terzo livello, e così via.

Il numero di alternative da considerare crescre in modo esponenziale con la profondità

dell’albero.

Ciò implica che è sufficiente un albero anche non eccessivamente profondo per dare luogo a

tempi di calcolo inaccettabili.

Nella ricerca BS, partendo dal nodo obiettivo 1 sola regola sar&agra