Intelligenza Artificiale - completo

Concetti chiave dell'intelligenza artificiale

Vento 5/3/02 – Assente alla lezione, non è sbobinata e mancano slide degli esempi.

Concetto chiave dell’intelligenza artificiale (AI) è l’assenza di un algoritmo per la risoluzione dei problemi. Il motivo di ciò sta nel fatto che l’obbiettivo dell’AI è costruire una macchina in grado di risolvere qualunque problema. Quindi, la macchina non deve semplicemente eseguire un algoritmo, ma essere capace di creare un algoritmo a partire dall’osservazione del problema.

Approcci dell'AI

Sono essenzialmente due:

Tesi forte

• Simulazione dei meccanismi cognitivi umani (reti neurali, algoritmi genetici);
• Non esiste una conoscenza pregressa del problema;
• Il sistema apprende ‘per esempi’.

Il problema viene presentato sotto forma di n istanze con le relative soluzioni. Il sistema risolve il problema nella modalità di funzionamento, preceduta da una modalità di apprendimento.

Modalità di apprendimento e funzionamento

Conoscenza interna non accessibile Rete Neurale

Problema da risolvere - Esempi di addestramento - Risultato

La ‘conoscenza interna’ è rappresentata mediante matrici di numeri reali.

Tesi debole

Prevede uno scalo della complessità del sistema. La macchina opera su una base di conoscenza (KB), fornita dall’uomo, necessaria a risolvere il problema. La KB è formalizzata – mediante un opportuno linguaggio – da esperti del dominio applicativo e è verificata. Il sistema è in grado di risolvere tutti e soli i problemi che coinvolgono la conoscenza presente nella KB.

1KB - Esperto - Problemi - Soluzioni - Motore inferenziale - Spiegazioni - Utenti

Il vantaggio peculiare dell’AI nella tesi forte è che, non essendo richiesto di fornire conoscenza, i relativi sistemi sono semplici da realizzare, oltre che veloci nella fase di funzionamento. A ciò fa riscontro una notevole lentezza della fase di apprendimento. Altro svantaggio caratteristico è che l’AI tesi forte è adatta solo per problemi di piccola complessità, che danno luogo comunque a reti di notevoli dimensioni.

Vento 8/3/02 – Pile scariche alla fine della prima metà (non interamente registrata), poi le ho sostituite.

Organizzazione di un sistema basato sulla tesi debole dell’AI

L’architettura è fondata basilarmente sui sistemi formali, dato che la ‘base di conoscenza’ è opportunamente formalizzata da un ‘esperto’ del problema. Un esempio di sistema formale è la matematica: un sistema formale molto complesso che costruisce delle teorie a partire da un insieme di assiomi. Il sistema formale (SF) è dunque impiegato per rappresentare la conoscenza che noi abbiamo di un particolare dominio.

Sul sistema formale opererà il motore inferenziale, il quale riceve dall’utente le specifiche richieste di risoluzione dei problemi e tenta di risolvere i medesimi mediante la consultazione del sistema formale. Il motore inferenziale segue un procedimento di derivazione di nuove teorie (si parla anche di dimostrazione di nuovi teoremi) a partire dalle teorie messe inizialmente a disposizione (assiomi).

I sistemi formali non sono programmi procedurali; sono cioè insiemi di verità e regole di inferenza non espresse sotto forma di algoritmo.

A titolo di esempio, supponiamo di voler realizzare un sistema in grado di svolgere derivate simboliche (cioè non attraverso i metodi relativamente semplici dell’analisi numerica, ma usando i simboli di variabili e funzioni). Alcuni odierni software matematici per computer permettono di operare in modo simbolico, benché i risultati non siano sempre accettabili. Scrivere un software del genere in un tradizionale linguaggio di programmazione richiederebbe un tempo enorme. Con la logica dei sistemi formali (ad esempio con un compilatore Prolog) bastano pochi minuti.

Il programma tradizionale è difficile da realizzare, perché l’algoritmo che si usa implicitamente quando si esegue la derivazione ‘a mano’ non è facile da descrivere, e soprattutto non lo è da implementare in una macchina come il computer, che nasce con l’obbiettivo di manipolare dei numeri piuttosto che dei simboli. Un sistema formale funziona secondo una logica del tutto diversa dalla normale programmazione. In esso ci limitiamo a fornire con un opportuno linguaggio una base di conoscenza; il motore inferenziale (che non dev’essere scritto, poiché è fornito automaticamente dall’ambiente di sviluppo, né esiste alcuna vera necessità di conoscerne la struttura o il funzionamento) fa il resto. Altra sorprendente caratteristica è che il motore inferenziale è invariabile: è lo stesso per tutti i tipi di applicazione.

Il ruolo dei sistemi formali nell’AI tesi debole può essere illustrato con un banale esempio. Supponiamo di voler insegnare ad un bambino di 5 anni (non necessariamente dotato di capacità intellettuali superiori alla media) il procedimento di derivazione simbolica. Possiamo affermare con sicurezza che il bambino sarebbe in grado di calcolare, nel giro di alcune settimane, derivate anche molto complesse.

Limitiamo il discorso per semplicità alle sole derivate elementari. Le regole di derivazione sono in fondo solo tre: la derivata della somma/differenza di due funzioni, la derivata del prodotto e quella del rapporto. Queste regole possono essere integrate con una opportuna tabella di derivate elementari, che fa corrispondere ad esempio alla funzione seno il coseno, al logaritmo naturale la funzione 1/x, etc.

Il bambino di 5 anni può tranquillamente padroneggiare ed utilizzare tali regole, usando il formalismo che illustreremo fra breve, ferma restando una considerazione: egli non ha consapevolezza del significato del procedimento di derivazione, ma si limita ad eseguire un compito puramente meccanico. Il bambino esegue in maniera meccanica dei passi, agendo senza alcuna consapevolezza, senza creatività e senza una vera e propria intelligenza. La stessa cosa può dirsi di qualunque macchina che esegua la derivazione simbolica.

Per comprendere come questo possa avvenire, si consideri il disegno della pagina successiva. Esso illustra un isomorfismo fra il mondo reale ed il sistema formale. Gli oggetti del mondo reale vengono fatti corrispondere ai simboli del sistema formale; le proposizioni sempre vere del problema in esame nel mondo reale corrispondono agli assiomi nel sistema formale; le relazioni tra oggetti nel mondo reale si traducono nelle regole di inferenza del sistema formale. Nel mondo reale è possibile ricavare relazioni dimostrabili, cui fanno riscontro i teoremi derivabili del sistema formale.

Sistema formale e mondo reale

Il segreto del ‘fenomeno’ che consente al bambino di 5 anni di derivare le funzioni elementari sta in un opportuno isomorfismo. Potremmo associare i simboli complessi della derivazione matematica ad una serie di simboli che il bambino possa facilmente maneggiare. Se ad esempio, associamo alla funzione seno una pallina rossa e al coseno un’automobilina gialla, potremmo spiegare al bambino che, ogni qualvolta vede una pallina rossa, deve sostituirla con una automobilina gialla. Lo stesso procedimento si può seguire per tutte le righe della tabellina delle funzioni elementari.

Che dire delle regole di derivazione? Ad esempio, rappresenteremo la somma di funzioni con un cappello; diremo al bambino che, quando vede due simboli con un cappello che li sovrasta entrambi, dovrà sostituire ai due simboli i loro corrispondenti; quindi, ad esempio, il bambino sostituirà l’insieme di una pallina rossa ed una bandierina blu, accomunate da un cappello che le copre entrambe, con un’automobilina gialla seguita da un cono gelato, avendo così realizzato, senza rendersene conto, l’operazione D(sin(x) + ln(x)) = cos(x) + 1/x.

In questo esempio, gli ‘assiomi’ sono dunque le righe della tabella delle derivate elementari, in cui figurano opportuni simboli, rappresentativi degli ‘oggetti’ tipici della derivazione simbolica. Le regole di inferenza sono per esempio le 3 regole fondamentali della derivazione.

Una volta che si è scelto un opportuno isomorfismo, è possibile realizzare un sistema che risolva un problema del mondo reale in un modo del tutto indipendente dalla semantica del problema originario. Il formalismo utilizzato dalla macchina può anche nascondere del tutto il significato del problema, come indicato dall’esempio che segue: “il sistema pg”.

I simboli del sistema sono tre:

• p
• g
• *

Abbiamo il seguente assioma: se x è una stringa di asterischi, x p * g x * è un assioma. Abbiamo inoltre una regola di inferenza: se x p y g z è vera, allora: x p y * g z * (è vera) dove x, y e z sono stringhe di asterischi.

Ci chiediamo: sono vere le seguenti proposizioni?

1. * * p * * * g *
2. * * p * * * g * * * * *

Per rispondere, applichiamo la procedura di derivazione che scaturisce dall’assioma e dalla regola di inferenza. Partendo dall’assioma, considerando ad esempio x come una stringa di un solo asterisco, si ha:

* p * g * *

Se ora applichiamo la regola di inferenza con x, y = * e z = ** (cioè x, y e z sono ricavate proprio dalla (1) che è una proposizione vera), si ha:

* p * * g * * *

e, ancora:

* p * * * g * * * *

e così via. Possiamo ora riscrivere la (1) nella quale consideriamo però x = **, abbiamo dunque:

* * p * g * * *

Regola di inferenza (x = **, y = *, z = ***):

* * p * * g * * *

e ancora:

* * p * * * g * * * *

Si noti che abbiamo così ottenuto la proposizione 2, che è, dunque, dimostrabile. Si intuisce viceversa che non esiste alcun modo di ricavare la proposizione 1, che è falsa.

In definitiva, mentre quelli che seguono non sono teoremi derivabili, ma assiomi:

• * p * g *
• * * p * g * *
• * * * p * g * * *
• ...

I teoremi che seguono possono essere derivati dall’assioma e dalla regola di inferenza:

• * p * * g * *
• * p * * * g * * *
• * p * * * * g * * * *
• ...

Il simbolismo utilizzato in questo caso nasconde il significato originario del problema, che sveliamo qui: si tratta dell’operazione di somma, nella quale al numero naturale k sostituiamo una stringa di k asterischi; il simbolo p rappresenta l’addizione, il simbolo g rappresenta il segno di uguaglianza. Quindi ad esempio il teorema:

* * p * * * g * * * * *

significa: 2 + 3 = 5. L’assioma sta a significare che, sommando 1 ad un numero naturale, otteniamo il numero naturale successivo. L’applicazione reiterata dello schema di assiomi consente dunque di ricavare tutti i possibili numeri naturali. La regola di inferenza corrisponde alla seguente, ovvia implicazione:

x + y = z → x + y + 1 = z + 1

L’applicazione di questa regola ci ha consentito di derivare tutte le somme nelle quali, contrariamente a quanto specificato nell’assioma, il secondo addendo è diverso da 1.

Difficilmente chi leggesse per la prima volta il sistema formale PG sarebbe in grado di afferrarne il significato con riferimento al problema reale che intende risolvere, ovvero di ‘interpretare’ l’isomorfismo. L’essere umano non è abituato a ragionare senza isomorfismi, cioè manovrando dei semplici simboli di cui non conosce il significato. Questa è invece proprio una prerogativa delle macchine di calcolo; a patto di predisporre un’adeguata formalizzazione, la macchina acquisisce un comportamento ‘intelligente’ che le permette di risolvere qualunque problema.

Partire dallo schema di assiomi ed applicare successivamente tutte le regole inferenziali per ottenere tutte le possibili verità: questo è proprio il processo che viene realizzato dal motore inferenziale. Il motore inferenziale è in effetti un algoritmo che parte da un assioma o da una verità intermedia, determina se a tale verità sono applicabili le regole, e in caso affermativo le applica, ottenendo nuove verità. La sua complessità algoritmica è modesta (un centinaio di linee di codice), e viene generalmente aumentata soltanto in virtù di una serie di agenti estranei al motore vero e proprio (ad esempio, motori inferenziali che mostrano all’utilizzatore come stanno funzionando o motori tarati per ottimizzare le prestazioni del computer su cui girano).

Un altro esempio: il ‘gioco’ MU

L’obbiettivo di questo SF è derivare stringhe a partire da altre. Anche in questo caso l’isomorfismo non è noto, e del resto questa volta la sua natura non ci interessa molto. Potrebbe ad esempio servire per produrre nuove catene di DNA da catene preesistenti, o per realizzare ossidoriduzioni. Importa invece capire come si comporta il motore inferenziale. Le regole di trasformazione sono 4 e ognuna di esse permette, fissata una stringa, di derivarne delle altre. Sottolineiamo che l’ordine con il quale le regole vengono enunciate non ha importanza.

• R1. YI → YIU (es. MI → MIU)
• R2. XY → XYY (es. MIU → MIUIU)
• R3. XIIIY → XUY (es. MIIIU → MUU)
• R4. XUUUY → XUY (es. MUUUI → MUI)

In base alla regola R1, se la stringa termina con una I si può aggiungere una U alla fine, oppure, in base alla 2, in una stringa del tipo XY si può replicare la sottostringa Y; proseguendo con le regole, tre I consecutive (III) possono essere sostituite da una U, e si possono eliminare due U consecutive in una stringa.

Ci chiediamo: è possibile ricavare la stringa finale MU partendo dalla stringa iniziale MI?

• MI
• R1 → MIU
• R2 → MIUIU
• R3 → MIU
• R1 → MIIU
• R2 → MIII
• R3 → MU

Abbiamo riportato la parte iniziale dell’albero generato dal motore inferenziale mediante l’applicazione delle regole all’assioma MI di partenza e alle verità intermedie. Ci siamo fermati al 4° livello dell’albero, che evidentemente ne ha infiniti.

Alla stringa iniziale MI (l’assioma) e ad ogni altro teorema il motore applica un procedimento detto di unificazione con le regole. Esso consiste nell’effettuare una opportuna sostituzione di variabili che renda la precondizione di una regola uguale al (unificabile col) teorema dato e consenta quindi di applicare al teorema la regola medesima. La precondizione della regola R1 è unificabile con l’assioma MI, a patto di sostituire alla generica stringa X il simbolo M. Applicando R1 a MI ricaviamo il teorema MIU, che non corrisponde al nostro obbiettivo.

Applichiamo dunque la regola R2, sostituendo X↔M e Y↔I. Il motore ricava MII. Le regole R3 e R4 non sono applicabili, dato che non figurano nella stringa né tre I né due U consecutive. L’unificazione non è possibile in questi casi.

Poiché non ha trovato il risultato, il motore inferenziale prosegue cercando di unificare i teoremi trovati con le regole. L’applicazione delle regole alle stringhe via via ricavate dovrebbe essere a questo punto facilmente comprensibile. Si noti che la regola R2 è sempre applicabile, mentre fino al 3° livello dell’albero non c’è modo di applicare la regola R4; inoltre, alla stringa MIIII del 3° livello possiamo applicare in due modi diversi la regola R3, dal momento che le 4 I consecutive possono essere interpretate come un gruppo III seguito da una singola I o viceversa. Il motore può cioè operare in questo caso 2 differenti unificazioni.

Altra cosa da notare è che uno stesso teorema può essere ottenuto con 2 strade diverse; è il caso di MIU, che figura due volte nell’albero, come applicazione a MI della regola R1 ovvero della sequenza R2-R2-R3. Ciò permette di dire che la struttura originata dal motore inferenziale non è in generale un albero, ma un grafo: alla stringa MIIII potremmo collegare direttamente con un arco orientato la MIU che compare come figlio sinistro di MI, apponendo l’etichetta R3. (Negli esempi che faremo durante il corso cercheremo spesso di ricondurci al caso di un albero, più semplice da trattare).

Questa constatazione trova un riscontro immediato in uno fra i più complessi SF creati dall’uomo, la matematica: uno stesso teorema può essere dimostrato in due o più modi differenti. Il motore inferenziale si ferma quando ha ‘espanso’ tutti i nodi e non sono possibili ulteriori espansioni. Non è il caso del nostro esempio, che genera un grafo di profondità infinita, non fosse altro che perché la seconda regola è sempre applicabile.

Il fatto che l’albero generato dal motore inferenziale sia infinito è uno svantaggio. Supponiamo nel nostro esempio che la stringa MU non sia generabile (come infatti sembra). Il sistema non si ferma mai, perché esplora un albero di lunghezza infinita alla ricerca di una soluzione che di fatto non c’è. In tal caso il sistema si dice non decidibile.