Universit`a degli Studi di Napoli “Federico II”mazzei/papers/laureaThesisMazzei.pdfIntroduzione...

Universita degli Studi di Napoli“Federico II”

Facolta di Scienze MM.FF.NN.Corso di Laurea in Fisica

A.A. 1999-2000

Tesi di laurea

Inferenza induttiva ealgoritmi genetici

Relatori:

Ch.mo Prof.Giuseppe Trautteur

Dott. Aniello Iazzetta

Candidato:

Alessandro Mazzei

Matricola:007/6227

Indice

Indice i

Introduzione 1

1 Inferenza induttiva 51.1 Apprendimento e induzione . . . . . . . . . . . . . . . . . . . 5

1.1.1 Caratterizzare l’apprendimento . . . . . . . . . . . . . 51.1.2 Una possibile schematizzazione . . . . . . . . . . . . . 7

1.2 Induzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.3 Problemi di induzione . . . . . . . . . . . . . . . . . . . . . . 161.4 Un esempio esplicito: polinomi . . . . . . . . . . . . . . . . . . 18

2 Inferenza Grammaticale 272.1 Classificare il problema . . . . . . . . . . . . . . . . . . . . . . 29

2.1.1 Spazio dei concetti . . . . . . . . . . . . . . . . . . . . 292.1.2 Spazio delle ipotesi . . . . . . . . . . . . . . . . . . . . 292.1.3 Presentazione degli esempi . . . . . . . . . . . . . . . . 302.1.4 Macchine inferenziali induttive . . . . . . . . . . . . . . 322.1.5 Criteri di successo . . . . . . . . . . . . . . . . . . . . . 35

2.2 Identificazione al limite . . . . . . . . . . . . . . . . . . . . . . 382.3 Inferenza grammaticale regolare . . . . . . . . . . . . . . . . . 46

2.3.1 Caratterizzazione algebrica dello spazio di ricerca . . . 492.3.2 Strategie di ricerca nel reticolo . . . . . . . . . . . . . . 512.3.3 L’algoritmo L! . . . . . . . . . . . . . . . . . . . . . . 552.3.4 Approcci incrementali . . . . . . . . . . . . . . . . . . 552.3.5 Metodi numerici . . . . . . . . . . . . . . . . . . . . . 56

2.4 PAC-learning ed inferenza regolare . . . . . . . . . . . . . . . 572.4.1 Complessita di Kolmogorov . . . . . . . . . . . . . . . 59

3 Algoritmi Evolutivi 633.1 Terminologia . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

i

3.2 Storia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653.3 Gli algoritmi genetici . . . . . . . . . . . . . . . . . . . . . . . 66

3.3.1 La teoria degli schemi . . . . . . . . . . . . . . . . . . 713.3.2 Progettare un algoritmo genetico . . . . . . . . . . . . 74

4 Il lavoro sperimentale 794.1 Il programma realizzato . . . . . . . . . . . . . . . . . . . . . 79

4.1.1 La codifica . . . . . . . . . . . . . . . . . . . . . . . . . 814.1.2 Operatori . . . . . . . . . . . . . . . . . . . . . . . . . 834.1.3 Parametri . . . . . . . . . . . . . . . . . . . . . . . . . 874.1.4 Fitness . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

4.2 Linguaggi di prova . . . . . . . . . . . . . . . . . . . . . . . . 904.3 Primo test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

4.3.1 Dati usati nel primo test . . . . . . . . . . . . . . . . . 964.3.2 Protocollo di sperimentazione del primo test . . . . . . 974.3.3 Risultati del primo test . . . . . . . . . . . . . . . . . . 100

4.4 Descrizione di alcuni run . . . . . . . . . . . . . . . . . . . . . 1034.5 Secondo test . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

4.5.1 Dati secondo test . . . . . . . . . . . . . . . . . . . . . 1074.5.2 Protocollo di sperimentazione del secondo test . . . . . 1084.5.3 Risultati del secondo test . . . . . . . . . . . . . . . . . 108

4.6 Limiti dell’algoritmo genetico realizzato . . . . . . . . . . . . . 1104.7 Considerazioni conclusive . . . . . . . . . . . . . . . . . . . . . 111

A Preliminari 115A.1 Teoria della calcolabilita . . . . . . . . . . . . . . . . . . . . . 115A.2 Linguaggi formali . . . . . . . . . . . . . . . . . . . . . . . . . 120A.3 Automi finiti . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

Bibliografia 126

ii

Introduzione

Questo lavoro nasce con l’intenzione di applicare il modello computazionaledegli algoritmi genetici al campo dell’inferenza grammaticale, cioe con l’ideadi realizzare un algoritmo ispirato all’evoluzione naturale per poi applicarload uno specifico problema di inferenza induttiva.

L’induzione e un procedimento che elabora informazioni parziali riguar-danti le proprieta di un insieme, fornendo una generalizzazione, cioe esten-dendo l’insieme su cui le proprieta valgono. Questo procedimento in generalenon e logicamente giustificato, e di conseguenza non e certo che l’informa-zione fornita in uscita sia vera. Tuttavia il metodo scientifico, cosidettoipotetico–deduttivo, tipico delle scienze empiriche, sembra non possa fare ameno dell’induzione nella fase di formulazione delle ipotesi1.

All’interno degli studi sull’induzione nasce l’inferenza grammaticale, chesi occupa di studiare le modalita con cui puo essere individuato un linguaggioformale, quando e conosciuto un insieme di stringhe che appartengono allinguaggio e, eventualmente, un insieme di stringhe che non appartengonoal linguaggio. Supponiamo che una sorgente di informazioni fornisca dellestringhe binarie:

01, 0101, 010101, . . .

Ci si puo domandare se c’e una regola formale con la quale la sorgente generale stringhe, se eventualmente questa regola sia individuabile guardando solol’insieme delle stringhe, e quali siano i fattori che influenzano l’identificabilitadella regola. L’inferenza grammaticale cerca di trovare risposte a questedomande, nell’ipotesi che esiste una regola con cui le stringhe sono statecreate, e che si tratti di una grammatica generativa di Chomsky.

I primi studi sull’inferenza grammaticale sono di carattere esclusivamenteteorico. Questi lavori, attraverso la progettazione e l’analisi di algoritmi, ingenerale intrattabili, pongono dei limiti alla piu ampia classe di linguaggi

1Il problema filosofico dell’induzione nasce in epoca classica e ha il suo punto di ri-ferimento moderno nella Enquiry Concerning Human Understanding di D. Hume; comeriferimenti contemporanei si possono consultare [Sal67] [Car71].

1

2 Introduzione

esattamente inferibili da un unico algoritmo induttivo. Successivamente ladirezione degli studi muto verso la ricerca di algoritmi induttivi che fosse-ro anche e!cientemente realizzabili nella pratica. L’interesse si strinse sullaclasse piu piccola della gerarchia chomskyana, i linguaggi regolari: teorica-mente era stato dimostrato da Gold [Gol67] che questa classe puo essereidentificata al limite se gli esempi contengono sia stringhe che appartengonoal linguaggio (esempi positivi) sia stringhe che non appartengono al linguag-gio (esempi negativi). Lo stesso Gold dimostra diversi anni dopo [Gol78]che trovare il piu piccolo automa finito compatibile2 con un insieme finitodi esempi positivi e negativi e un problema NP–hard rispetto alla lunghezzadelle stringhe. Questo teorema e molto importante, poiche un algoritmo cheaspira ad identificare al limite e!cientemente un insieme di linguaggi for-mali, dovrebbe e!cientemente trovare il piu piccolo automa (grammatica)che accetta (genera) un sottoinsieme finito del linguaggio. Succesivamente siindividuarono delle proprieta che, se possedute dall’insieme di esempi, per-mettono di rivedere l’inferenza grammaticale regolare come ricerca in unospazio dotato di particolari caratteristiche algebriche. Cercando di sfruttarequesta possibilita vengono ideati negli ultimi anni un numero significativodi algoritmi concreti, che inferiscono il piu piccolo automa finito compatibilecon un insieme di esempi positivi e negativi: alcuni di questi raggiungono l’ef-ficienza utilizzando informazioni addizionali, come l’esistenza di un oracolo,cioe con la possibilita di chiedere se una stringa appartiene o non appartieneal linguaggio.

Nel contesto di rivedere l’inferenza grammaticale regolare come ricercaall’interno di uno spazio, si inserisce poi anche l’uso degli algoritmi evolutivi.Gli algoritmi evolutivi sono un modello computazionale che si ispira alla se-lezione naturale. L’algoritmo simula il procedimento naturale che permetteagli individui migliori di sopravvivere (valutazione della fitness), e evolvere(mutazione, crossover). Gli individui della popolazione sono delle soluzioniapprossimate del problema che si intende risolvere. La popolazione evolvecontinuamente: ad ogni generazione vengono selezionati statisticamente gliindividui per riprodursi e generare una nuova popolazione. Una funzioneapposita chiamata fitness, che dipende direttamente dal problema a cui l’al-goritmo evolutivo e applicato, decide se un elemento della popolazione debbasopravvivere oppure no. Gli algoritmi evolutivi sono superiori ad altri mo-delli computazionali nei problemi in cui lo spazio di ricerca e molto ampio:viene sfruttata una sorta di parallelismo implicito che permette di analizzarecontemporaneamente piu modelli di soluzione [Gol89].

2Compatibile sta ad indicare che accetta tutte le stringhe degli esempi positivi e nessunastringa degli esempi negativi (vedi paragrafo 2.1.3).

Introduzione 3

In diversi lavori [LHK99] [Lan94] [Lan95], si applica il paradigma deglialgoritmi evolutivi per trovare il piu piccolo automa finito compatibile con uninsieme di esempi positivi e negativi. In tutti questi studi i linguaggi usati pertestare le caratteristiche degli algoritmi sono i linguaggi di Tomita [Tom82],un’insieme di sette linguaggi regolari ideati da Tomita per testare il proprioalgoritmo di hill–cimbing. I lavori citati usano un solo insieme di esempi pertestare ogni linguaggio, seguendo il procedimento originariamente usato daTomita. Gli algoritmi induttivi sono in generale molto sensibili alla costitu-zione degli esempi, e quindi provare l’algoritmo evolutivo con diversi insiemidi esempi potrebbe risultare un presupposto imprescindibile per un’analisicritica delle prestazioni dell’algoritmo.

In questo lavoro si parlera dell’algoritmo genetico realizzato per trovarela piu piccola grammatica regolare compatibile con un insieme di esempi po-sitivi e negativi. Per provare le prestazioni di tale algoritmo si e attinto aidati presentati in [Tom82] e [Dup94]: quest’ultimo lavoro descrive le carat-teristiche dell’algoritmo genetico GIG, particolarmente interessante poichesfrutta alcune caratteristiche peculiari dell’inferenza grammaticale regolare,supponendo per l’insieme degli esempi proprieta non eccessivamente restrit-tive. Nel fare cio si sono anche confrontate le prestazioni dimostrate da duediversi operatori genetici: il classico operatore di crossing–over, e l’operatoredi traslocazione. Prima di questo lavoro l’operatore di traslocazione era statousato solo in un recente studio [FITC00], con l’intento preciso di saggiarnele caratteristiche.

Il lavoro si divide in quattro parti. Nel primo capitolo si parlera dell’in-duzione, e basandosi sulla classificazione proposta in [Mic87b], si inquadreraquesto procedimento nel complesso meccanismo dell’apprendimento. Inoltre,dopo aver confrontato l’induzione con le altre forme di inferenza presenti nelpensiero logico (deduzione e abduzione), si elencheranno gli elementi che ca-ratterizzano un problema induttivo; alla fine del capitolo verranno dati dueesempi di problemi induttivi.

Nel secondo capitolo viene fornita una definizione formale dell’inferenzagrammaticale, specificando i punti che distinguono un problema induttivo.Dopo aver analizzato i risultati teorici generali dell’inferenza grammaticalelo studio si focalizzera sull’inferenza grammaticale di linguaggi regolari: sidescriveranno nei particolari le peculiarita di questo tipo di induzione, e sipasseranno in rassegna alcuni algoritmi realizzati nella pratica per eseguirequesta inferenza.

All’interno del terzo capitolo si introdurra il modello degli algoritmi evo-lutivi. Nello specifico si parlera degli algoritmi genetici, particolare tipo dialgoritmo evolutivo che presuppone la codifica delle soluzioni parziali sottoforma di stringa [Hol75].

4 Introduzione

Il quarto capitolo e dedicato alla descrizione dell’algoritmo genetico rea-lizzato in questo lavoro per eseguire l’inferenza grammaticale di un linguaggioregolare. Dopo avere spiegato quali sono le caratteristiche di tale algoritmo,si descriveranno criticamente i risultati di due test eseguiti sul programmacon lo scopo di valutarne le prestazioni. I risultati ottenuti verranno infineconfrontati con quelli presenti in letteratura [Dup94].

Capitolo 1

Inferenza induttiva

L’induzione e la parte del pensiero logico che sintetizza il passaggio dal parti-colare al generale. Con il termine Inferenza Induttiva si indica un processoche ipotizza delle regole generali partendo da degli esempi. L’inferenza in-duttiva gioca un ruolo fondamentale nel vasto scenario dell’apprendimentoe in tutti i campi che si prefiggono la scoperta di strutture universali, comead esempio la costruzione di una teoria scientifica. Il tentativo di ricreare ilfenomeno dell’inferenza induttiva, caratteristica degli esseri intelligenti, al-l’interno delle macchine ha comportato la nascita di diversi campi di studio.Uno dei piu importanti si occupa di indagare sui meccanismi che permettonoad un essere umano di apprendere un linguaggio.

1.1 Apprendimento e induzione

1.1.1 Caratterizzare l’apprendimento

L’apprendimento e certamente un fenomeno tipico di tutti gli esseri intel-ligenti. L’approccio dell’intelligenza artificiale all’apprendimento si orientaverso una classificazione precisa dei vari fattori, delle varie strategie, del-le varie strutture che sono coinvolte nell’apprendimento negli esseri umani.Nonostante queste intenzioni, un punto di partenza largamente di"uso e chenon sia possibile dare una definizione dell’apprendimento: cio che si puofare e invece caratterizzare l’apprendimento analizzando i fenomeni ad essocollegati.

Due concetti giocano certamente un ruolo fondamentale nell’apprendi-mento: il miglioramento delle capacita del sistema che apprende, e l’acqui-sizione di nuova conoscenza. Un’idea largamente accettata nel mondo del-l’intelligenza artificiale e che l’apprendimento comporti delle modifiche in un

5

6 Inferenza induttiva

sistema, e che tali modifiche ne migliorano le caratteristiche. Minsky cercadi formalizzare questa idea richiedendo che le modifiche nel sistema sianogenericamente utili: L’apprendimento e il fare dei cambiamenti utili nellanostra mente; egli stesso riconosce poi l’inutilita di questa definizione dovutaalla troppa vaghezza. Simon [Sim83] da una caratterizazione piu dettagliatadell’apprendimento, nel tentativo di precisare che cosa esattamente si puointendere per miglioramento nel sistema: L’apprendimento denota dei cam-biamenti in un sistema che sono adattivi, nel senso che permettono al sistemadi eseguire lo stesso compito, o compiti analoghi, in maniera migliore nel fu-turo. Questo modo di riconoscere attivita di apprendimento va sotto il nomedi principio di miglioramento. Bisogna pero notare che vi sono delle attivitache coinvolgono l’apprendimento in cui non e semplice capire in cosa consisteil miglioramento delle capacita, inoltre vi sono dei sistemi che migliorano neltempo senza che nessun tipo di apprendimento entri in gioco.

Un altro fattore che accompagna l’apprendimento e l’acquisizione di nuoveconoscenze. Per poter acquisire qualsiasi conoscenza e necessario rappresen-tare questa conoscenza in qualche modo, ad esempio in forma di enunciati o diprocedure. Questo conduce verso una nuova possibile caratterizzazione del-l’apprendimento: L’apprendimento e costruire e modificare rappresentazionidi cio che e stato sperimentato. In questa definizione il termine sperimen-tare intende sia gli stimoli provenienti dai sensori del sistema che apprende,sia cio che il sistema sperimenta sotto forma di processi interni. Ripeterea mente una frase molte volte ci consente di impararla a memoria, pur nonavendo alcuno stimolo dai nostri sensi. Stimoli e processi interni sono i veicoliattraverso i quali il sistema che apprende percepisce la realta che intende rap-presentare. Sotto questo punto di vista l’aspetto centrale dell’apprendimentoe il processo di costruire una rappresentazione di una certa realta piuttostoche il miglioramento delle capacita del sistema. L’aumento delle capacita delsistema e considerato come una conseguenza.

Un modo per coinvolgere il principio di miglioramento nell’acquisizionedi nuova informazione e caratterizzare l’apprendimento come la costruzionee la modifica di informazioni finalizzate al miglioramento delle proprieta delsistema. Questo punto di vista consente di poter misurare il grado di ap-prendimento di un sistema misurando i miglioramenti mostrati dal sistemanell’eseguire un certo compito. E importante notare che in questa schema-tizzazione implicitamente si assume che il sistema abbia uno scopo e che talescopo sia conosciuto dall’osservatore che analizza l’apprendimento.

1.1 Apprendimento e induzione 7

1.1.2 Una possibile schematizzazione

Esistono diversi modi di catalogare i fattori che influenzano l’apprendimen-to. Michalski [Mic87b] propone una divisione ragionata, basata su diversecaratteristiche del sistema che apprende.

Michalski esegue una prima distinzione in base alla quantita di conoscenzeiniziali di cui il sistema e dotato. Ai due estremi della classificazione troviamole reti neurali artificiali e i sistemi esperti. Nel contesto dei sistemi dotati discarse conoscenze iniziali le reti neurali sono uno strumento largamente usato:le connessioni dei neuroni che costituiscono il sistema, sono determinate inmaniera essenziale dagli esempi presentati e solo in maniera molto limitatadai valori iniziali delle connessioni. Nella progettazione di un sistema espertouna grande quantita di informazione viene fornita al sistema, che quindiinizialmente gia possiede delle informazioni strutturate, generalmente nonmodificabili.

Un ulteriore approccio, suggerito da Michalski, propone di suddividire isistemi artificiali che apprendono in funzione della similitudine degli algorit-mi usati con i processi mentali umani. Da una parte troviamo quei lavoriche studiano l’apprendimento da un punto di vista teorico, sviluppando al-goritmi indipendenti dal campo di applicazione: in questo caso non si fannorestrizioni sulla natura degli algoritmi, che possono essere molto diversi daquelli che si ipotizzano siano i processi che permettono ad un essere umanodi apprendere. In un’altra orientazione di ricerca rientrano quegli studi sullosviluppo di modelli computazionali per i processi di apprendimento umani.In questo orientamento l’apprendimento nell’uomo e il centro di interesse; loscopo e lo sviluppo di teorie computazionali e di modelli sperimentali che ri-spettino le conoscenze psicologiche e neurofisiologiche. Lo sviluppo di questistudi potrebbe dare importanti contributi persino nel campo della pedagogia.

L’analisi piu precisa fatta da Michalski nel suo tentativo di classificarel’apprendimento, si basa sul tipo di manipolazione eseguita dal sistema cheapprende sull’informazione proveniente dall’esterno. In ogni processo di ap-prendimento il sistema che apprende trasforma l’informazione fornita da unteacher, o piu in generale da una sorgente di informazione, in una nuovaforma che viene poi memorizzata per usi futuri. Questa trasformazione del-l’informazione, che fa uso anche delle conoscenze gia possedute dal sistema,viene chiamata inferenza. Il tipo di trasformazione eseguita determina lastrategia di apprendimento di cui il sistema fa uso. Si possono distinguere,seguendo esattamente Michalski in [Mic87a] , cinque diverse strategie1:

1Fino al termine del capitolo il testo tra virgolette indichera una trascrizione esatta dalriferimento bibliografico


• Apprendimento per imitazione

• Apprendimento per istruzioni

• Apprendimento per deduzione

• Apprendimento per analogia

• Apprendimento per induzione

Queste strategie sono state elencate in base ad una crescente complessitadell’inferenza eseguita sull’informazione inizialmente fornita.

Per poter capire le di"erenze tra le varie strategie ci restringiamo al campodell’apprendimento dei concetti.

Definizione 1.1. Un concetto e una classe di equivalenza per cui esiste unaprocedura e!ettiva che permette di discriminare gli oggetti come appartenentio non appartenenti al concetto.

In intelligenza artificiale un concetto e definito in maniera molto piu vagacome un insieme di oggetti accomunati da un uso comune, da uno stesso sco-po, dallo stesso ruolo in una teoria, o comunque da caratteristiche comuni.La definizione 1.1 e invece un modo molto preciso di intendere i concetti, chesi e a"ermata nel contesto del PAC–learning [Val84]. Un sistema appren-de un concetto quando impara una procedura e"ettiva che gli permette didiscriminare gli oggetti come appartenenti o non appartenenti al concetto.Questo compito puo quindi essere rivisto come la scoperta di una definizioneintensionale per il concetto. Si possono allora esemplificare le varie strategiedi apprendimento vedendone l’applicazione all’apprendimento di concetti.

• Apprendimento per imitazione“Questo e il caso estremo in cui il sistema che apprende non deve ese-guire alcuna inferenza sulle informazioni che gli provengono dalla sor-gente”. Il compito principale svolto dal sistema e indicizzare in qualchemaniera l’informazione per poterla poi recuperare. Normalmente si at-tua questa strategia nell’apprendimento di un concetto fornendo comeinformazione al sistema una descrizione operativa del concetto oppurefornendo un programma per riconoscere gli elementi del concetto. Peresempio questa strategia e applicata quando uno specifico algoritmo perriconoscere un concetto viene programmato su un calcolatore, oppurequando al calcolatore viene fornito un database di fatti che permet-tono di riconoscere il concetto. Questa strategia veniva applicata, adesempio, nei primi programmi che giocavano a scacchi: si salvavano irisultati della ricerca in un albero di gioco, per poter essere poi ripresirisparmiando spazio e tempo di esecuzione.

1.1 Apprendimento e induzione 9

• Apprendimento per istruzioni“In questo caso il sistema che apprende acquisisce un concetto da uninsegnante, o da un’altra forma organizzata di informazione, come unapublicazione o un libro, ma non copia direttamente in memoria l’infor-mazione acquisita”. Nell’apprendimento per istruzioni le trasformazio-ni sull’informazione eseguite dal sistema sono la selezione e la riformu-lazione a livello sintattico. Il processo di apprendimento puo consisterenel selezionare i fatti piu importanti e poi trasformarli in una formapiu appropiata. Un programma che costruisce una database di fatti eregole sulla base di una conversazione con un utente e un esempio disistema che apprende per istruzioni.

• Apprendimento per deduzione“Il sistema che apprende acquisisce un concetto deducendolo dalle co-noscenze fornite dalla sorgente insieme a quelle che il sistema gia pos-sedeva. In altre parole, questa strategia include ogni processo nel qualela conoscenza appresa e il risultato di una trasformazione che preservala verita delle informazioni generate dalla sorgente”. All’interno del-l’apprendimento dei concetti, l’apprendimento per deduzione trasformauna definizione non adoperabile per discriminare il concetto, in una de-finizione operativa adatta a questo scopo. Ad esempio dal fatto cheuna brocca sia un oggetto stabile e trasportabile, si puo dedurre che labrocca ha un fondo piatto e un manico.

• Apprendimento per analogia“Il sistema che apprende acquisisce un nuovo concetto modificando ladefinizione di un concetto simile gia conosciuto. Piuttosto che formu-lare una descrizione del concetto partendo da zero, il sistema adattauna descrizione esistente modificandola appropriatamente per il nuo-vo scopo.” Ad esempio se gia si conosce una regola che definisce ilconcetto di arancia, per imparare il concetto di mandarino si possononotificare le di"erenze e le similitudini tra arancia e mandarino. Unaltro esempio e l’apprendere il concetto di circuito elettrico notando leanalogie di questo con un sistema di tubature idrauliche. Come Michal-ski sottolinea, l’apprendimento per analogia puo essere visto come unincrocio tra l’apprendimento deduttivo equello induttivo. Attraversol’inferenza induttiva si possono determinare le caratteristiche generalio le trasformazioni che unificano i concetti confrontati. Poi, attraversoun’inferenza deduttiva si possono derivare le proprieta caratterizzzantipossedute dal concetto che deve essere appreso.

• Apprendimento per induzione


“Nell’apprendimento per induzione il sistema acquisisce un concettooperando delle inferenze induttive su dei fatti forniti dalla sorgente oin base a delle osservazioni su tali fatti”. In funzione del tipo di infor-mazioni fornite dalla sorgente e di che cosa e inizialmente conosciutodal sistema, due di"erenti forme di questa strategia si possono indivi-duare.“Nell’apprendimento da esempi il sistema che apprende induce unadescrizione del concetto generalizzando degli esempi, e eventualmentedei controesempi, forniti dalla sorgente di informazione”. Un’ipotesioperativa e che il concetto esista, cioe che e"ettivamente esista unaprocedura e"ettiva per testare l’appartenenza alla classe. Il compitodel sistema e determinare una descrizione per il concetto analizzandole singole istanze del concetto. Questa strategia e applicata nell’infe-renza grammaticale, che verra trattata nel seguito di questo lavoro.“Nell’apprendimento per osservazione e scoperta il sistema cheapprende analizza degli oggetti e determina se alcuni sottoinsiemi diquesti possono essere raggruppati vantaggiosamente insieme in singoliconcetti”. Diversamente dal caso precedente non si fa alcuna ipotesioperativa a priori sull’esistenza di questi concetti. Appena un concet-to viene individuato gli si da un nome: questo permette di riusare ilconcetto per definirne altri. Michalski fornisce come esempio di que-sta strategia il clustering, cioe il partizionamento di una collezione dioggetti in classi organizzate in maniera gerarchica: se un oggetto e rico-nosciuto essere un’istanza di un certo concetto, gli vengono assegnate lepropieta di quel concetto e di tutti i concetti piu in alto nella gerarchia.Se si apprende che sabrina e un’elefantessa, si puo, senza vedere sabri-na, dire che essa ha quattro zampe, una proboscide e tutte le proprietaspecifiche degli elefanti; si puo inoltre dire che sabrina possiede anchele proprieta degli erbivori, e piu in generale ancora dei mammiferi.

1.2 Induzione

L’inferenza induttiva e lo strumento principale per creare nuova conoscen-za. E usuale caratterizare l’inferenza induttiva come il ragionamento checonduce dallo specifico al generale, dal particolare all’universale. Questa ca-ratterizzazione e innegabilmente semplice ma altrettanto poco precisa: nonsi specificano tutte le componenti in gioco nel processo induttivo e non sispiega come questa inferenza sia possibile. Per capire meglio questo tipodi inferenza bisogna delineare le sue componenti principali ed e necessariospecificare le proprieta delle sue conclusioni. Seguiremo ancora le definizioni

1.2 Induzione 11

di Michalski in [Mic87a]. Gli elementi di partenza dell’inferenza, vista comemanipolazione simbolica, sono:

1. “Un insieme di enunciati premessa, costituiti da fatti, specificheosservazioni, generalizzazioni intermendie, che forniscono informazioniriguardanti degli oggetti, dei fenomeni, dei processi”.

2. “Le conoscenze di background, che contengono concetti generali especifici dell’applicazione, e che permettono di interpretare le premessee le regole rilevanti per l’inferenza. Queste conoscenze includono con-cetti precedentemente imparati, relazioni di causalita, assunzioni circale premesse e circa le ipotesi candidate, scopi dell’inferenza, metodiper valutare la bonta di una ipotesi sulla base dello scopo (criterio dipreferenza)”.

Mentre l’elemento finale dell’inferenza induttiva e:

• “Una ipotesi induttiva, che implica gli enunciati premessa nel con-testo delle conoscenza di background ed e l’ipotesi migliore rispetto alcriterio di preferenza”.

Le definizioni ora date si riassumono in quella che Michalski [Mic94] chiamaequazione fondamentale dell’inferenza.

(Ipotesi induttiva) ! (Conoscenze di background) =" (Enunciati premessa)(1.1)

Michalski precisa che in 1.1 l’implicazione puo assumere due valenze distinte.Si puo avere che un’ipotesi induttiva implica fortemente gli enunciati premes-sa nel contesto delle conoscenze di background se usando tali conoscenze, el’inferenza deduttiva, gli enunciati premessa risultano essere una conseguen-za logica dell’ipotesi induttiva. Una ipotesi che rispetta questa condizione echiamata una ipotesi induttiva forte. In contrasto, un’ipotesi induttiva e de-bole se solo debolmente implica gli enunciati premessa: questo significa chein 1.1 “gli enunciati premessa sono una conseguenza plausibile dell’ipotesiinduttiva, ma non una coseguenza logica”.Per chiarire questa distinzione Michalski fornisce un esempio di inferenzainduttiva.

Enunciati premessaSocrate era greco.Aristotele era greco.Platone era Greco.


Conoscenze di backgroundSocrate, Aristotele e Platone erano filosofi.Sono vissuti nell’antichita.I filosofi sono persone.I greci sono persone.Criterio di preferenza = Si preferiscono le ipotesi piu corte, piu speci-fiche e piu utili per decidere la nazionalita dei filosofi.

Alcune ipotesi induttive sono:

1. I filosofi che hanno vissuto nell’antichita erano greci.

2. Tutti i filosofi sono greci.

3. Tutte le persone sono greche.

L’ipotesi da preferire sulla base del criterio di preferenza e la 2, poiche e piubreve della 1, e piu specifica della 3, e permette di determinare la nazionalitadei filosofi. Si puo dimostrare che questa ipotesi induttiva e un’ipotesi forte,poiche gli enunciati premessa risultano essere una conseguenza logica delleipotesi e delle conoscenze di background.Supponiamo di aggiungere ai fatti di partenza premessa gli enunciati

• Locke era inglese.

• Hume era inglese.

e di modificare le conoscenze di background aggiungendo il fatto che sia Lockeche Hume erano filosofi. In questo caso una ipotesi induttiva forte potrebbeessere che tutti i folosofi erano greci, con l’eccezione di Locke e Hume. Mentreuna ipotesi induttiva debole potrebbe essere che alcuni filosofi erano greci.Dal fatto che Platone era un filosofo e sulla base di questa nuova ipotesi debolenon consegue che Platone era greco, consegue solo che “c’e la possibilita chePlatone fosse greco”.

Le ipotesi induttive hanno delle proprieta che possono essere evidenziatenel confronto con gli altri tipi di inferenza presenti nel pensiero logico, ovverola deduzione e l’abduzione. Consideriamo l’inferenza come un trasformazionedi informazioni che prende in Input un enuciato, e grazie alle conoscenze dibackground (BK) gia possedute fornisce un enunciato in Output [Mic94].

1. DEDUZIONE tabella 1.1 L’Input consiste in un enunciato che si espri-me sull’appartenenza di un elemento a ad un insieme X. Le BK sonoformate da un enuniato che assegna una certa proprieta q agli eleme-ni dell’insieme X, e da una regola della logica formale detta regola di

1.2 Induzione 13

Input a # X a e un elemento di X.BK $x # X, q(x) Tutti gli elementi di X

hanno la proprieta q.($x # X, q(x)) " (a # X " q(a)) Se tutti gli elementi di

X hanno la proprietaq, allora ogni elementodi X, e quindi anche a,deve avere la proprietaq.

Output q(a) a ha la proprieta q.

Tabella 1.1: Deduzione

specializzazione universale. L’inferenza vera e propria consiste solo nel-l’applicazione di tale regola . A causa della natura tautologica dellaregola usata per eseguire l’inferenza segue che la deduzione preserva laverita. Se l’enunciato di Input risulta vero, cioe e"ettivamente a # X,anche l’enunciato di Output deve essere vero, poiche nell’inferenza de-duttiva non ci sono passaggi logicamente non giustificati che possonocomportare un’alterazione del valore di verita.

2. INDUZIONE tabella 1.2 L’Input e un enunciato che a"erma che unelemento a, gia presente nelle conoscenze di BK, possiede la proprietaq. Le conoscenze BK sono identiche a quelle dell’esempio sull’inferenzadeduttiva. L’Output consiste in un enunciato che assegna la proprietaq a tutti gli elementi dell’insieme X menzionato nelle conscenze di BK.

Input q(a) a ha la proprieta q.BK a # X a e un elemento di X.

($x # X, q(x)) " (a # X " q(a)) Se tutti gli elementi diX hanno la proprietaq, allora ogni elementodi X, e quindi anche a,deve avere la proprietaq.

Output $x # X, q(x) Tutti gli elementi di Xhanno la proprieta q.

Tabella 1.2: Induzione


L’inferenza consiste nel supporre l’implicazione presente nella regola dispecializzazione valida anche nel verso opposto.

Input q(a) a ha la proprieta q.BK ($x, x # X) " q(x) Se x e un elemento

di X allora x ha laproprieta q.

Output a # X a e un elemento di X.

Tabella 1.3: Abduzione

3. ABDUZIONE tabella 1.3 Nell’abduzione l’enunciato di Input a"ermache un elemento a gode della proprieta q. Le BK consistono di un unicoenunciato, che esprime il fatto che tutti gli elementi di un certo insiemeX hanno la proprieta q. L’ipotesi abduttiva, cioe l’Output, asseriscel’appartenenza di a a X. Questa ipotesi si ottiene considerando validain ambo i sensi l’implicazione presente nelle BK, come accade anchenell’induzione. La di"erenza rispetto all’induzione e che l’implicazione“invertita” non e una tautologia, bensı e un enunciato che puo o puonon esere vero a seconda dell’interpretazione.

Ancora Michalski ha tentato di rivedere l’induzione sotto un punto divista strettamente sintattico e hanno individuato alcune regole sintattiche diinferenza induttiva [Mic87a]. Queste regole prendono uno o piu enunciati dipartenza e ne generano di nuovi, facendo diventare gli enunciati di partenzadelle conseguenze. Aluni esempi di queste regole sono:Perdere condizioni: rimuovere una condizione in una congiunzione dell’e-nunciato di partenza. Ad esempio partendo da un uomo e giusto se e onestoe fedele con l’enunciato un uomo e giusto se e onesto.Trasformare esistenziali in universali: ad esempio trasformare l’enun-ciato questa mela sembra buona in tutte le mele sembrano buone.Aggiungere opzioni: cioe aggiungere in forma disgiuntiva nuove cause. Adesempio l’enunciato sopraviverai se saprai nuotare puo essere trasformata insopraviverai se saprai nuotare o se avrai un salvagente.Generalizzare gli oggetti: rimpiazzare un termine meno generale con unopiu generale. Ad esempio Mi piacciono le mele con mi piace la frutta.

Nei discorsi precedenti si e definito l’apprendimento di un concetto daesempi come un processo che costruisce una rappresentazione di una certaclasse di elementi, attraverso l’osservazione di membri della classe ed even-tualmente anche attraverso l’osservazione di entita che non appartengono allaclasse. Michalski propone di rivedere questo compito di apprendimento come

1.2 Induzione 15

Selezione degli esempi

Riformulazione

Spaziodelle istanzeSpazio dlle descrizioni

Descrizioni

equivalenti

Figura 1.1: Induzione come ricerca in uno spazio [Mic87a]

ricerca all’interno di uno spazio [Mic87a]. Si definisce spazio delle istanzel’insieme di tutti i possibili esempi e controesempi dei concetti che possonoessere appresi. Lo spazio dei concetti e l’insieme di tutte le possibili de-scrizioni, nel formalismo definito dalle conoscenze di background, di concettiche possono essere appresi. Gli elementi forniti come esempi e controesem-pi a qualsiasi tempo dalla sorgente di informazione, saranno elementi dellospazio delle istanze. L’induzione di un concetto da esempi, comporta un’in-terazione da parte del sistema che apprende con questi due spazi. Al sistemaviene fornito un sottoinsieme sempre piu grande dello spazio delle istanze: ilsistema deve formulare un’ipotesi induttiva selezionando un elemento dellospazio dei concetti.

Puo capitare che ad un singolo concetto corrispondono diverse descrizioniequivalenti nello spazio delle descrizioni. Un concetto e consistente rispettoagli esempi se accetta alcuni esempi positivi e nessun esempio negativo. Unconcetto e completo rispetto agli esempi se accetta tutti gli esempi positivi.La descrizione di un concetto consistente e completo rispetto agli esempi euna possibile ipotesi induttiva. L’insieme di tutte le ipotesi induttive possi-bili forma uno spazio chiamato spazio delle ipotesi possibili o versionspace. Lo spazio delle ipotesi possibili puo essere ordinato parzialmente sullabase di una relazione di inclusione tra i corrispondenti concetti. L’ipotesi piugenerale descrive un concetto che e esattamente il complemento degli esempinegativi; l’ipotesi meno generale descrive un concetto che e esattamente l’u-nione di tutti gli esempi positivi. Lo spazio delle ipotesi possibili puo esseremolto grande ed in questo caso un criterio di preferenza deve essere usatoper poter scegliere quale elemento sara l’ipotesi induttiva. Questo criteriopuo essere la lunghezza della descrizione o la sua semplicita o comunque un


criterio che mglio rappresenta lo scopo dell’apprendimento. Se lo spazio delleipotesi possibili e costituito da un singolo elemento, la scelta del criterio sarachiaramente ininfluente.

L’induzione di un concetto da esempi puo allora essere descritto come laricerca euristica, in uno spazio di descrizioni, del “migliore” elemento consi-stente e completo rispetto agli esempi forniti. E seguendo questo schema chee stato sviluppato il lavoro sperimentale descritto nei capitoli successivi.

1.3 Problemi di induzione

Il modello generale di inferenza induttiva si applica a molti campi, ognunocaratterizzato da un diverso tipo di concetti da dover inferire. Diversi stu-di sono stati condotti sull’inferenza induttiva di espressioni logiche, MdT,programmi LISP, funzioni matematiche, linuaggi formali ed altro. La dif-fussione di questi studi ha portato l’inferenza induttiva ad essere un campoautonomo di studi. Questa autonomia ha anche provocato la di"usione diun linguaggio specifico che a volte entra in contraddizione con le definizionidi termini gia in uso nel campo del machine learning. In questo campo sisono sviluppati due filoni fondamentali. Il primo filone si occupa di studiarel’inferenza induttiva con atteggiamento strettamente teorico, disinteressan-dosi delle specifiche e dei problemi legati ad una e"ettiva realizazione praticadegli algoritmi sotto forma di programmi. Il secondo filone si occuppa inve-ce di scrivere ed ottimizzare programmi che eseguono l’inferenza induttiva,trascurando lo studio dei risultati piu strettamente teorici. Entrambi questifiloni si sono concentrati sull’analisi di una singola variante della strategia in-duttiva, ovvero in quello che e stato in precedenza chiamato apprendimentoda esempi o generalizzazione induttiva. Questo indirizzamento e stato moltofavorito dalla possibilita di schematizzare facilmente un problema di questacategoria, e dalla possibilita di ridurre l’inferenza vera e propria ad una ri-cerca in uno spazio (figura 1.1). Quindi e necessario definire precisamentecosa e un problema di inferenza induttiva. Seguendo una classificazione lar-gamente accettata [AS83] sono necessari cinque elementi a!nche il problemasia correttamente definito

1. Lo spazio dei concetti e l’insieme delle possibili soluzioni del proble-ma induttivo. In questo contesto il termine concetto assume lo stessosignificato che gli viene assegnato in alcuni studi sull’apprendimento.Un concetto e una classe di equivalenza che ammette almeno una pro-cedura e"ettiva per determinare se un elemento appartiene o meno allaclasse.

1.3 Problemi di induzione 17

2. Lo spazio delle ipotesi e uno spazio che contiene delle descrizioniintensionali di concetti. Poiche il risultato ultimo di un problema diinduzione e l’individuazione, piu o meno precisa, di un concetto, questorisultato deve essere fornito nell’unica forma e"ettiva in cui una classedi equivalenza, di cardinalita infinita, puo essere descritta: attraversouna procedura e"ettiva che discrimini gli elementi appartenenti allaclasse. Per come e schematizzato il problema di induzione nello spaziodelle ipotesi ci dovra essere almeno una descrizione per ogni elementodello spazio dei concetti.

3. Per ogni concetto appartenente allo spazio dei concetti, e necessariodefinire il tipo di esempi che verranno forniti al sistema induttivo; enecessario quindi specificare cos’e una presentazione accettabile, opresentazione ammissibile, del concetto. Molte variazioni possonoessere fatte sul tipo di esempi e sulla modalita di presentazione di taliesempi. Se lo scopo dell’inferenza induttiva e eseguire una generalizza-zione induttiva, si possono fornire al sistema, ad esempio, solo istanzeche appartengono al concetto; oppure si possono fornire sia istanze cheappartengono al concetto sia istanze che non vi appartengono. Piu ingenerale e possibile che gli esempi siano presentati con delle informazio-ni aggiuntive su di essi: ad esempio si possono fornire le istanze divisein tre classi, la prima formata da istanze che appartengono al concetto,la seconda formata da istanze che non appartengono al concetto, laterza formata da istanze che con alta probabilita non appartengono alconcetto. Si puo inoltre permettere al sistema di richiedere quali esem-pi devono essere forniti nel seguito, oppure introdurre un margine dirumore, e quindi di errore, nella comunicazione o nella classificazionedelle istanze. Un’altra importante specifica e l’ordine con cui gli esempisi presentano. La procedura che decide l’ordine di presentazione puoessere una generica funzione calcolabile, una funzione non e"ettiva ouna funzione che tiene conto della congettura fatta dal sistema indut-tivo. Inoltre si possono avere delle ripetizioni o delle mancanze nellasequenza di esempi. Riferendosi agli studi sull’apprendimento lo spaziodelle ipotesi equivale allo spazio delle descrizioni ra!gurato in figura1.1.

4. Specificare i metodi di inferenza vuol dire specificare il tipo di al-goritmi, utilizzabili per eseguire l’inferenza. Intuitivamente un metododi inferenza induttiva e una generica procedura e"ettiva che prende iningresso degli esempi ammissibili e produce come congettura un ele-mento dello spazio delle ipotesi. La possibilita di vedere l’apprendi-


mento da esempi come la ricerca in uno spazio, permette di usare comealgoritmo induttivo algoritmi di ricerca usati in altri campi, adattatialla natura dello spazio delle ipotesi. Gli algoritmi genetici, ad esem-pio permettono di trovare una congettura compatibile con gli esempiattraverso una ricerca nello spazio delle ipotesi che si basa sull’imita-zione del procedimento noto in natura come selezione naturale. Glialgoritmi usati nei problemi di induzione vengono chiamati indi"eren-temente metodi di inferenza, macchine inferenziali induttive oalgoritmi induttivi.

5. E necessario definire quando il problema di inferenza e da considerar-si risolto: questa specifica verra chiamata criterio di successo. Uncriterio molto usato e l’identificazione al limite: un concetto si con-sidera correttamente inferito se l’algoritmo induttivo produce solo unnumero finito di congetture inesatte. Un’altra condizione che spessoviene inserita nel criterio di successo e che se ci sono diverse descrizio-ni dello stesso concetto nello spazio delle ipotesi, l’algoritmo induttivorestituisca al limite la piu breve. Un’altra classe di criteri di successonon richiede, come nell’identificazione al limite, un’esatta identificazio-ne del concetto, ma considerano l’inferenza induttiva corretta anche sela descrizione del concetto e parziale o imprecisa, purche entro certilimiti. Il criterio piu conosciuto che si basa su questo principio e ilPAC–learning.

1.4 Un esempio esplicito: polinomi

Non esiste un criterio generale per giudicare la bonta di un ragionamentoinduttivo: il passaggio dal particolare al generale non porta con se alcunagaranzia di unicita. Supponiamo di dover indovinare il prossimo numerodella sequenza infinita 3, 5, 7, . . . . Una ipotesi ragionevole sembra essere ilnumero 9: si sta congetturando che la sequenza sia quella dei numeri disparia partire da 3. Non c’e nulla di sbagliato nel pensare, alternativamente, cheil prossimo numero della sequenza sia 11: la sequenza potrebbe essere quelladei numeri primi a partire da 3. Infiniti numeri possono essere sospettati diessere il prossimo della sequenza e corrispondentemente infinite regole pos-sono essere indicate come motivo della scelta. Ci si puo domandare se tra leinfinite ipotesi corrette sulla giusta continuazione della sequenza 3, 5, 7, . . .quella che la identifica con la sequenza dei numeri dispari sia in qualchemaniera da preferire alle altre sulla base della semplicita. Una risposta atale domanda dovrebbe chiarire prima cosa e"ettivamente e la semplicita

1.4 Un esempio esplicito: polinomi 19

in una ipotesi. Analizziamo un problema piu specifico seguendo l’esempiodi Angluin [AS83]: pensiamo ad un gioco che si svolge tra di un uomo edun calcolatore elettronico. Il calcolatore fornisce dei numeri stampandoli sudi un terminale, l’uomo deve indovinare in base ai numeri precedentementeforniti, quale sara li prossimo numero della sequenza. Se l’uomo sbaglia ilcalcolatore lo corregge fornendogli il numero giusto. Uno svolgimento delgioco puo essere:

il calcolatore stampa 2L’uomo scrive 3Il calcolatore stampa: SI 2, 3L’uomo scrive: 4Il calcolatore stampa: NO 2, 3, 5L’uomo scrive: 7Il calcolatore stampa: SI 2, 3, 5, 7L’uomo scrive 11Il calcolatore stampa: SI 2, 3, 5, 7, 11. . . . . .

L’uomo vince se riesce a scoprire quale e la regola con la quale i numerisono generati, cioe quando le sue previsioni sul prossimo numero sarannosempre esatte. Per rendere il gioco interessante supponiamo che il calcolatoresia onesto, cioe non cambi la regola per la produzione dei numeri duranteil gioco. La possibilita di vincere a questo gioco sembra dipendere dallaclasse di regole a cui il calcolatore puo accedere per generare i numeri. Adesempio il calcolatore puo essere programmato per generare il primo numeroa caso e per rispondere nel seguito sempre NO, correggendo la congetturaaumentando il numero pensato dall’uomo di una unita. Questa e una regolache non permette di indovinare il prossimo numero: la nostra congetturasul prossimo numero sara sempre inferiore di 1 al numero che il calcolatoregenerera come corretto. Studiamo un caso specifico; supponiamo che le regoletra cui il calcolatore puo scegliere sia l’insieme dei polinomi di una variabilea coe!cienti interi P:

p(n) = a0 + a1n + a2n2 + . . . + ain

i + . . . # P (1.2)

con ai # ZLa sequenza fornita dal calcolatore

c1, c2, c3, . . . , ci, . . . con i # Nsara generata dal polinomio p nel senso che

cj = p(j) $j # N


Ad esempio se il polinomio generatore e x2 +1, la sequenza visualizzata sara:

2, 5, 10, 17, 26, 37, 50, 65, 82 . . .

Consideriamo ora due algoritmi che con certezza permettono di vincere inquesto caso.

• Si scelga una numerazione e"ettiva di tutti i polinomi a coe!cien-ti interi P. Una possibile numerazione si ottiene elencando per d =0, 1, 2, 3, . . . tutte le (d+ 1)–ple di interi compresi tra [%d, d], e usandoqueste (d + 1)–ple come coe!cienti di 1, n, n2, . . . , nd.Per d = 0 si ottiene

0 =" p(n) = 0

Per d = 1 si ottiene

1, 1 =" p(n) = 1 + n1, 0 =" p(n) = 11,%1 =" p(n) = 1% n0, 1 =" p(n) = n0, 0 =" p(n) = 00,%1 =" p(n) = %n%1, 1 =" p(n) = %1 + n%1, 0 =" p(n) = %1%1,%1 =" p(n) = %1 % n

Per d = 2 si ha

2, 2, 2 =" p(n) = 2 + 2n + 2n2

2, 2, 1 =" p(n) = 2 + 2n + n2

2, 2, 0 =" p(n) = 2 + 2n2, 2,%1 =" p(n) = 2 + 2n% n2

2, 2,%2 =" p(n) = 2 + 2n% 2n2

2, 1, 2 =" p(n) = 2 + n + 2n2

2, 1, 1 =" p(n) = 2 + n + n2

. . . . . . . . .

e cosı via.Per ogni valore di d vi sono esattamente (2d + 1)d+1 (d + 1)–ple distin-te; inoltre se d1 e d2 sono due numeri naturali, ed accade che d1 < d2

l’insieme dei polinomi numerati da d2 contiene propriamente l’insiemedei polinomi numerati da d1. Questa elencazione ricopre, numeran-dolo in maniera e"ettiva, tutto linsieme P, man mano che d cresce.


Possiamo usare questa numerazione di P per vincere il nostro giococontro il calcolatore. Per congetturare il prossimo numero della se-quenza y1, y2, . . . , yt, si sceglie il primo polinomio p della numerazionedi P tale che p(i) = yi con 1 & i & t. La congettura sul prossimonumero della sequenza sara p(t + 1). Questa procedura ci porta consicurezza alla vittoria. Supponiamo che il calcolatore usi il polinomioq(n) = a0 +a1n+a2n2+ . . .+arnr per produrre i numeri della sequenzanel gioco. Questo polinomio appartiene a P e quindi e nella numera-zione precedente. Precisamente q(n) viene elencato quando d superail massimo tra i valori assoluti degli ai e il valore di r. Consideria-mo la prima occorenza di q(n) nella numerazione: tutti i polinomi cheprecedono questo valore di"eriranno da q(n) per qualche n. Quandol’insieme y1, y2, . . . , yt sara grande abbastanza verranno rigettati tuttii polinomi che precedono nella numerazione q(n). Da quel punto in poisi usera proprio q(n) per congetturare i prossimi numeri della sequenza,e quindi tutte le previsioni saranno corrette. Questo metodo di con-gettura per numerazione, che cerca sistematicamente in tutto lo spaziodelle possibili regole, eliminando quelle che non sono compatibili coni dati finora conosciuti, cerca attraverso piu di dd di"erenti polinomiper arrivare al corretto grado d della soluzione: se m e il massimo tra{|a0|, |a1|, . . . , |ar|, r}, verrano esaminti almeno

!mi=0(2i + 1)i+1.

• Prendiamo i valori disponibili della sequenza, cioe il segmento inizialey1, . . . , yt, interpoliamo cercando un polinomio di grado al massimouguale a t% 1 che passi per questi punti, usiamo questo polinomio perpredire il prossimo valore della sequenza.

Il seguente teorema [Dav63] ci assicura che questo metodo conduce alsuccesso

Teorema 1.2 (di Interpolazione). 2 Se con Pn si indica l’insie-me dei polinomi di grado minore uguale a n, dati n + 1 punti distin-ti (reali o complessi) z0, z1, . . . , zn e n + 1 valori (reali o complessi)w0, w1, . . . , wn, esiste ed e unico il polinomio p(z) # Pn tale che

p(zi) = wi con i = 0, 1, . . . , n

Il metodo vero e proprio per eseguire l’interpolazione ed ottenere il poli-nomio consiste nel risolvere il sistema che si ottiene usando la sequenza

2Questo teorema generalizza il fatto che per due punti passa un’unica retta.


iniziale y1, . . . , yt

"###$

###%

y1 = a0 + a1 + . . . + at"1

y2 = a0 + 2a1 + . . . + 2t"1at"1

. . .

yt = a0 + ta1 + . . . + tt"1at"1

Quando la sequenza iniziale avra un numero di elementi superiore algrado del polinomio che genera la sequenza, l’interpolazione fornisceper il teorema precedente il risultato corretto.

Entrambi i metodi presentati hanno successo al limite: esiste un tempo tdopo il quale il polinomio congetturato risulta essere quello corretto. Si puopero intuire come il metodo per numerazione richieda un quantita di calcolonettamente superiore al metodo per interpolazione, che per convergere adun polinomio di grado d usa un numero di operazioni aritmetiche polinomia-le in d. L’esistenza del metodo di interpolazione per la classe dei polinomidimostra che la dimensione dello spazio di ricerca non e l’unico fattore de-terminante per l’esistenza di un metodo di inferenza e!ciente. Un vantaggioche ha il metodo per numerazione rispetto a quello per interpolazione e si-curamente la generalita: allargando la classe delle regole possibili a tutte lefuzioni aritmetiche si puo pensare ad una nuova numerazione e"ettiva che ciconsente ancora di inferire la funzione giusta. Questo non e possibile con ilmetodo per interpolazione. Una considerazione valida per entrambi i metodie che in caso di vittoria non si sa di aver vinto: anche essendo arrivati adinferire il polinomio giusto e indovinato un numero notevole di numeri in suc-cessione, non si puo mai essere sicuri che ad un certo punto non venga unaprevisione sbagliata. Per rimuovere questa insicurezza ed essere certi di avervinto si devono avere delle informazioni aggiuntive sulla forma della soluzio-ne, come ad esempio il massimo grado del polinomio usabile come ipotesi.Questa certezza di trovare una soluzione accompagnata dall’impossibilita diriconoscerla quando la si ottiene e tipica dei problemi di induzione in cuisi lavora con sequenze non terminanti e si richiede un accordo con l’interasequenza. Se si volesse inferire un polinomio che ha come primi dieci valori:

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, . . .

si potrebbe ragionevolmente pensare che la soluzione sia il polinomio costan-te:

p(n) = 1


ma se dopo l’undicesimo valore la sequenza si presenta come:

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3628801, . . .

una nuova ipotesi potrebbe essere:

p(n) = 1 + n(n% 1)(n% 2)(n% 3)(n% 4)(n% 5)(n% 6)(n% 7)(n% 8)(n% 9)

Il gioco dei polinomi e solo un semplice esempio di un problema di inferenzainduttiva, ma mette in luce alcuni elementi tipici di questi studi, che verranoincontrati spesso nel seguito. Due di questi elementi risalgono ai primi lavorisull’inferenza induttiva [Gol67] e meritano di essere sottolineati per la loroimportanza.

• Si e arrivati alla conclusione che i metodi sopra descritti per risolverel’estrapolazione della sequenza polinomiale, identificano al limite ta-le sequenza. L’identificazione al limite vede l’inferenza induttiva comeun processo infinito. Dopodiche l’ultima congettura che il metodo diinferenza fornisce, anche al tendere del tempo all’infinito, puo essereusata per stabilire il criterio di successo. Nell’esempio sui polinomi, ilgioco di indovinare il prossimo elemento della sequenza e un processoprolungabile indefinitivamente, ed il successo e definito come l’indo-vinare sempre il prossimo elemento della sequenza, dopo un numerofinito di errori. Piu astrattamente, si ipotizzi che M sia un metodo diinferenza induttivo adatto ad inferire un certo concetto C. Si suppongache se ad M viene fornito un insieme sempre piu grande di istanze delconcetto C, M generi una sequenza infinita di congetture g1, g2, g3, . . . .Se esiste un numero naturale m per cui gm sia una descrizione e"ettivadi M , e per cui

gm = gm+1 = gm+3 = . . .

allora si dice che M identifica correttamente C al limite sulla sequenzadi ingresso. Si puo vedere M come un sistema che sta imparandosempre di piu sul concetto C, man mano che l’insieme di istanze diC aumenta, M puo modificare la sua congettura su C in base allenuove conoscenze che gli vengono fornite. Se dopo un tempo finito Msmette di modificare la sua congettura su C e l’ultima congettura e unacorretta descrizione di C, allora M identifichera C correttamente sullasequenza in ingresso di esempi. M non puo comunque determinare sesta convergendo verso un’ipotesi corretta: ogni nuovo dato puo o puonon entrare in conflitto con la congettura attuale.


• L’identificazione per numerazione e il primo metodo usato nell’e-sempio sui polinomi. Questo metodo cerca sistematicamente nello spa-zio delle possibili descrizioni del concetto fino a trovare una descrizionecompatibile con gli esempi presentati fino a quel momento al sistema.Si supponga di assegnare un insieme di concetti C, un insieme H didescrizioni per C, ed una numerazione e"ettiva d1, d2, d3, . . . su H; sisupponga inoltre che ogni concetto di C abbia almeno una descrizio-ne in H. Per ogni insieme di istanze di un concetto di C, il metododi identificazione per numerazione scorre la numerazione fino al primoelemento di compatibile con l’insieme di istanze: di sara la congetturafatta a quel punto dal sistema. Questo metodo puo o puo non identi-ficare al limite correttamente un concetto a seconda che l’insieme deiconcetti C possieda o meno certe propieta (vedi capitolo successivo).

Inquadriamo il problema dell’inferenza di una sequenza polinomiale nellaclassificazione in cinque punti di un problema induttivo, descritta nel para-grafo precedente. Lo spazio dei concetti e l’insieme delle funzioni f definite inN e a valori in Z, tali che f(n) e un certo polinomio in n a coe!cienti interi.Lo spazio delle ipotesi e proprio l’insieme di tutti i polinomi di una variabilea coe!cienti interi. In questo esempio lo spazio delle ipotesi coincide, in uncerto senso, con lo spazio dei concetti: cioe ad ogni polinomio corrispondeun unico elemento dello spazio delle ipotesi. E importante notare che nonsempre lo spazio dei concetti e cosı semplice da descrivere: l’uso di polinomicome concetti ci permette di usare le proprieta formali che accomunano tuttii polinomi per descrivere lo spazio dei concetti, ma non sempre il concettoha delle proprieta formali caratterizzanti. Per ogni polinomio p l’insieme diesempi ammissibili e costituito da coppie nella forma 'n, p(n)(, dove n e unintero positivo. Nel problema specifico l’unica presentazione ammissibile perp era la sequenza infinita di coppie

'0, p(0)(, '1, p(1)(, '2, p(2)(, . . .

che nel discutere l’esempio sono state abbreviate nella forma

p(0), p(1), p(2), . . .

Quindi per questo problema l’unica presentazione accettabile per p e unapresentazione parziale, sempre piu grande, del grafo di p, in un ordine cre-scente rispetto agli elementi del dominio. La classe degli algoritmi induttiviusabili per risolvere questo problema non e stata specificata, ma un’ipotesiragionevole puo fare riferimento alle MdT. Si puo ad esempio richiedere cheun metodo sia ammissibile se e, in ultima analisi, ricorsivo, cioe e"ettivo e


sempre terminante. I metodi di identificazione per numerazione e di inter-polazione per soluzione di un sistema sono due algoritmi, che sicuramenteportano all’identificazione, e che sono certamente ricorsivi. Il criterio di suc-cesso scelto per riconoscere l’identificazione di un polinomio p da parte di unmetodo di inferenza M , e l’esistenza di un intero N tale che $n ) N :

M(p(1), p(2), . . . , p(n)) = p(n + 1)

Bisogna notare che questo criterio di successo richiede la previsione del prossi-mo numero e non l’identificazione del polinomio selezionato come generatore.E chiaro che identificare il polinomio porta con certezza al successo, poichesi e sempre in grado di calcolare il prossimo numero della sequenza, ma ilviceversa non e vero. Nella classificazione del problema possiamo consideraregli esempi forniti sia come una collezione di valori di p, e quindi come insiemedi istanze del concetto p, sia come frammento iniziale del grafo di p, che euna descrizione estensionale di p.

Per poter meglio capire i cinque punti che definiscono un problema indut-tivo analizziamo un altro esempio: congetturare un’espressione regolare sullabase di dati positivi e negativi. Si supponga che siano assegnate le stringhe

0011, 000011, 0000, 011, 00, 000000

con l’indicazione che tali stringhe appartengono ad un insieme regolare L;inoltre anche le stringhe

0010, 0, 00110, 111, 0001111, 00000

sono assegnate, pero con l’indicazione che non appartengono a L. Un’ipotesisu L potrebbe essere che L e l’insieme di tutte le stringhe composte da unnumero pari di 0, unito all’insieme di tutte le stringhe di 0 che terminanocon due caratteri 1. Quest’ipotesi viene esplicitata dall’espressione regolare

(00)! + 0!11

Formalizziamo la descrizione di questo problema induttivo. Lo spazio deiconcetti e costituito da l’insieme di tutti gli insiemi regolari sull’alfabeto{0, 1} mentre lo spazio delle ipotesi e l’insieme di tutte le espressioni regolarisullo stesso alfabeto. Possiamo gia notare delle di"erenze rispetto all’esempiosui polinomi: in questo caso e molto piu chiara la di"erenza tra il concetto,cioe il singolo linguaggio regolare, e una descrizione intensionale del con-cetto, cioe l’espressione regolare. Il fatto che possiamo cambiare lo spaziodelle ipotesi, scegliendo tra automi finiti, grammatiche context–free, MdT,accentua ancora di piu questa di"erenza. L’unica restrizione di cui si deve


tenere conto nella scelta dello spazio delle ipotesi e che ogni elemento dellospazio dei concetti abbia almeno una descrizione contenuta in esso. Nel casodei polinomi la relazione di equivalenza che legava tra di loro i numeri, visticome istanze, era l’essere dei valori del polinomio generatore; nel caso degliinsiemi regolari la relazione che lega le stringhe e la relazione che definisceun linguaggio formale. Un esempio per il linguaggio formale L e una coppia's, d( tale che d e 1 o 0 (S o N) a seconda che la stinga s appartiene o menoall’insieme L. Una presentazione ammissibile di L e una sequenza infinitadi esempi di L tale che ogni stringa sull’alfabeto {0, 1} appare in qualcheesempio della sequenza. Cosı una presentazione ammissibile del linguaggiodescritto dall’espressione 0!11 potrebbe essere

'00011, 1(, '001, 0(, '11, 1(, '011, 1(, '1, 0(, '00111, 0(, '1, 0(, . . .

Si puo richiedere che i metodi di inferenza induttiva usabili siano riconducibilia delle procedure e"ettive, aggiungendo che tali procedure devono sempreterminare. Queste procedure avranno in ingresso un segmento iniziale dellapresentazione di un linguaggio regolare, e produrrano in uscita un’espressioneregolare. Se si sceglie l’identificazione al limite come criterio di sucesso, unamacchina inferenziale induttiva M identifica un linguaggio L al limite se esolo se per ogni presentazione ammissibile

's1, d1(, 's2, d2(, 's3, d3(, . . .

di L, se En e l’espressione regolare congetturata da M su un segmento inizialedi n elementi della presentazione, allora esiste un N # N tale che En = EN

per ogni n ) N , ed inoltre EN * L. Riferendosi all’esempio sui polino-mi e immediato costruire una numerazione e"ettiva delle espressioni regolariche permette di usare il metodo per numerazione per identificare corretta-mente al limite una certa espressione regolare. Ci si puo chiedere se esisteun metodo adatto all’identificazione di un’espressione regolare che sia altret-tanto e!ciente e generale come il metodo dell’interpolazione che abbiamoincontrato nell’esempio sui polinomi: si vedra nel seguito che, abbastanzasorprendentemente, la risposta a questa domanda e negativa.

Capitolo 2

Inferenza Grammaticale

L’inferenza grammaticale e una branca degli studi sull’induzione che si oc-cupa in particolare dell’inferenza induttiva di un linguaggio formale. Sonodiversi i campi in cui l’inferenza grammaticale ha un certo interesse.

• Riferendosi a Gold in [Gol67], uno dei primi campi a cui l’inferenzagrammaticale e stata applicata con profitto e la modellizzazione del-l’apprendimento del linguaggio naturale nell’uomo. L’uso dei linguaggiformali come concetti da dover inferire e delle grammatiche generativedi Chomsky come descrizioni di tali concetti, consente di evidenziare gliaspetti sintattici della lingua rispetto al procedimento di apprendimen-to [Cho57], e di delineare le condizioni minime a!nche l’apprendimentoabbia sucesso. Questo studio doveva riguardare unicamente le proprietaed i limiti degli algoritmi induttivi, cercando a!nita e parallelismi coni processi che si credevano coinvolti nell’apprendimento di un essereumano.

• Un nuovo interesse nell’inferenza grammaticale e dovuto ai recenti stu-di sul riconoscimento di regolarita sintattiche, ovvero sulla scopertadi leggi formali che esprimano delle regolarita in sequenze di simbo-li; in particolare all’interno dei moderni studi di genetica e biologiamolecolare, l’inferenza grammaticale si inserisce come uno strumentoutilizzabile per scoprire eventuali proprieta formali del DNA, visto inmaniera molto schematica come una sequenza di simboli [SD92].

• Altro motivo di interesse si e evoluto nel contesto del machine lear-ning, e nasce dalla possibilita di vedere un linguaggio formale come ilpiu semplice e chiaro esempio di concetto: il dover congetturare unagrammatica associata ad un linguaggio formale attraverso un insiemecrescente di stringhe del linguaggio, sembra essere il piu semplice caso

27

28 Inferenza Grammaticale

studiabile di apprendimento di un concetto per mezzo di istanze di esso.Si puo quindi considerare l’inferenza grammaticale come uno dei casipiu rilevanti di apprendimento di un concetto per mezzo di esempi.

Nell’inferenza grammaticale gli esempi sono stringhe su un alfabeto fis-sato: alcune di esse appartengono ad un certo linguaggio formale ed altrenon vi appartengono. Il compito della macchina inferenziale induttiva e diindividuare una grammatica che genera unicamente le stringhe appartenential linguaggio1. L’inferenza grammaticale nasce con l’intenzione di studiareda un punto di vista strettamente teorico gli algoritmi coinvolti nel processodi induzione di un linguaggio formale. In questo contesto, in cui lo studio ri-guardava tutte le classi della gerarchia di Chomsky, l’eventuale realizzabilitapratica degli algoritmi era trattata con un interesse molto marginale. Neglianni successivi l’approccio verso questo tipo di studi e nettamente mutato.L’idea di studiare i risultati in funzione dell’apprendimento umano ha assun-to un aspetto minore rispetto all’interesse di realizzare degli algoritmi chefossero anche e!cienti. Molte ricerche sono state svolte sulla classe piu sem-plice della gerarchia di Chomsky i linguaggi regolari2. L’inferenza induttivadi linguaggi regolari mediante una presentazione degli esempi positivi e nega-tivi, era un’argomento gia studiato approfonditamente da un punto di vistateorico: Gold aveva dimostrato che questa inferenza aveva successo al limiteusando il classico algoritmo di identificazione per numerazione. L’algoritmodi identificazione per numerazione non e e!ciente3, e quindi si provo a trova-re degli algoritmi che raggiungessero lo stesso risultato in maniera accettabile[TB73]. Gold [Gol78] dimostra che il problema di trovare il piu piccolo au-toma finito compatibile con un generico insieme di stringhe e un problemanon polinomiale rispetto alla taglia delle stringhe, cioe rispetto alla sommadelle lunghezze delle stringhe. Questo risultato elimina la speranza di trovareun algoritmo di induzione sempre e!ciente che permetta l’identificazione allimite di un linguaggio regolare. Si puo allora individuare una biforcazionenell’evolversi degli studi: da una parte si indaga su quali informazioni ad-dizionali sono necessarie per far diventare il processo e!ciente, dall’altra si

1Attraverso una procedura di codifica e!ettiva come la godelizzazione si puo associarebiunivocamente un numero di Godel ad una stringa e ancora un insieme ricorsivamentenumerabile ad un generico linguaggio formale. Il problema dell’inferenza grammaticale sipuo quindi ricondurre al problema induttivo di inferire l’indice di un insieme ricorsivamentenumerabile, usando come esempi frammenti sempre piu grandi dell’insieme. Un problemadi inferenza grammaticale cosı posto, ha il grande difetto di non evidenziare le proprietadel linguaggio formale nella storia del procedimento induttivo.

2L’inferenza dei linguaggi regolari prende talvolta una propria denominazione: si parladi inferenza grammaticale regolare.

3In questo lavoro per algoritmo e"ciente si intendera un algoritmo in cui il tempo dicalcolo e una funzione della lunghezza dell’input al massimo polinomiale

2.1 Classificare il problema 29

elabora un nuovo criterio di successo che si interessa dell’inferenza induttivaparziale di un linguaggio formale.

2.1 Classificare il problema

Definiamo ora l’inferenza grammaticale specificando i cinque punti che defi-niscono un problema di inferenza induttiva, ovvero

1. Spazio dei concetti,

2. Spazio delle ipotesi,

3. Presentazione degli esempi,

4. Macchine inferenziali induttive,

5. Criteri di successo.

2.1.1

Spazio dei concetti %+ Insieme di linguaggi formali.

Specificare lo spazio dei concetti in inferenza grammaticale generalmentevuol dire scegliere una classe della gerarchia di Chomsky. Ogni classe dellagerarchia ha delle caratteristiche che possono pesantemente influenzare ilrisultato dell’inferenza induttiva. Anche se la maggior parte degli studi siconcentra sull’inferenza di linguaggi regolari, alcuni tentativi sono stati fattisalendo di un gradino nella gerarchia chomskyana, cioe studiando l’inferenzadi linguaggi context–free.

Una variante di"usa riguarda lo studio dell’inferenza di linguaggi stocasti-ci, cioe di linguaggi che legano ad ogni regola di produzione una probabilita:di conseguenza ad ogni stringa del linguaggio verra assegnata un numero chene indica la probabilita di essere generata.

2.1.2

Spazio delle ipotesi %+ Insieme di grammaticheLo spazio delle ipotesi e usualmente una classe di grammatiche della gerar-chia di Chomsky, che deve poter generare ogni linguaggio appartenente allospazio dei concetti. Non sempre gli oggetti dello spazio delle ipotesi sonogrammatiche: se lo spazio dei concetti e l’insieme di tutti i linguaggi rego-lari, lo spazio delle ipotesi puo essere costituito da grammatiche lineari, ma


anche da automi finiti e espressioni regolari. Poiche alla gerarchia di gram-matiche corrisponde una gerarchia di macchine e sempre possibile inferireun linguaggio attraverso l’automa corrispondente alla classe di grammaticheda cui il linguaggio puo essere accettato. Nel suo pionieristico lavoro Gold[Gol67] fa notare che uno spazio delle ipotesi, costituito da funzioni carat-teristiche che esprimono l’appartenenza di una stringa a un linguaggio, evincolato all’inferenza di linguaggi ricorsivi. L’uso di grammatiche, cioe dioggetti che generano linguaggi piuttosto che deciderli, permette, almeno inlinea di principio, di poter inferire anche linguaggi ricorsivamente numerabili.

2.1.3

Presentazione degli esempi+

"####$

####%

Presentazione

&Completa

Positiva

Oracolo

Given data

Vi sono diverse variazioni nel modo in cui e possibile presentare un lin-guaggio ad una macchina inferenziale induttiva. Queste modalita sono indis-solubilmente legate al criterio di successo che si intende usare per giudicarela bonta dell’induzione, ma anche alla classe di linguaggi che costituisce lospazio dei concetti. Se si usa un criterio al limite, in una qualsiasi dellesue varianti, e naturale che la presentazione degli esempi del linguaggio siaun processo anch’esso al limite, cioe che gli esempi siano costituiti da uninsieme crescente di stringhe che al limite fornisce una descrizione estensio-nale completa del linguaggio. Se invece il criterio di successo non riguardasolo l’identificazione induttiva del linguaggio, ma anche la qualita delle ipo-tesi intermedie in relazione agli esempi presentati man mano, allora si puoanalizzare la presentazione degli esempi sotto altri punti di vista. Questoaccade nell’inferenza grammaticale applicata ai linguaggi regolari. L’infor-mazione necessaria per potere inferire correttamente un linguaggio regolaree un sottoinsieme significativo del linguaggio: questo basta per poter in-durre correttamente la grammatica regolare, o l’automa finito, che genera illinguaggio.

Esempi labellati

Definiamo ora le modalita di presentazione piu importanti. Sia L un linguag-gio sull’alfabeto #


Definizione 2.1. Un esempio positivo per L e una coppia 'x, 1( con x #L. Un esempio negativo e una coppia 'x, 0( con x # #! e x /# L. Un esem-pio positivo o negativo verra genericamente chiamato esempio labellato oesempio.

Un modo per esemplificare un linguaggio e presentarlo interamente ma inmaniera graduale.

Definizione 2.2. Una presentazione positiva di L e una sequenza infini-ta di esempi positivi di L, tale che ogni x # L appaia almeno in un elementodella sequenza. In questo caso la notazione puo essere alleggerita indicandosolo il primo elemento della coppia che definisce l’esempio.

Definizione 2.3. Una presentazione completa di L e una sequenza in-finita di esempi labellati di L tali che ogni x # #! appaia almeno una voltain un elemento della sequenza.

Quando in un problema di induzione la presentazione degli esempi e quellapositiva si usa scrivere la coppia 'x, 1( piu semplicemente come x. Come sipuo notare la modalita di presentazione degli esempi non specifica l’ordinecon cui gli esempi vengono presentati: vedremo in seguito che generalmentel’ordine non influisce sul successo dell’inferenza induttiva. A volte si indicacon S+ un insieme di esempi positivi mentre con S" si indica un insiemedi esempi negativi: con Sample di un linguaggio L si indica un insieme diesempi per il linguaggio S = S+ ! S".

Quando si e interessati alla possibilita di inferire un linguaggio da unnumero finito di istanze, gli esempi vengono forniti in una modalita che vienedetta given–data [Gol78]. La presentazione per given data non ha unadefinizione precisa ma ci sono due punti che solitamente la caratterizzano:

1. Gli esempi S vengono forniti nel loro insieme in quanto l’algoritmo fauso direttamente dell’intera informazione, senza passare per congettureintermedie.

2. Il sample S ha di conseguenza una cardinalita finita.

Il problema dell’induzione da given–data e strettamente legata all’induzioneper presentazione completa. Le congetture prodotte da un algoritmo indutti-vo durante la graduale presentazione degli esempi, possono essere viste comeil risultato di singoli processi induttivi in modalita given–data. Se non esi-ste un algoritmo che e!cientemente costruisce una congettura plausibile inmaniera e!ciente in modalita given–data, non esiste neanche un algoritmoinduttivo che fa lo stesso nel caso di presentazione completa degli esempi.


Se la scelta su quali esempi presentare viene fatta dalla macchina inferen-ziale induttiva stessa, si dice che la modalita di presentazione e per Oracoloo Teacher: l’algoritmo induttivo puo porre domande sull’appartenenza diuna qualsiasi stringa al linguaggio da inferire. La presentazione per oracolo eteoricamente equivalente alla presentazione completa: l’algoritmo puo sem-pre aspettare che la stringa di cui vuole sapere l’appartenenza appaia comeelemento di un esempio labellato all’interno della presentazione completa.Poiche la presentazione completa e sempre associata ad un criterio di succes-so al limite, il tempo perso nell’aspettare l’arrivo della stringa non influirasul successo dell’induzione. Se si e invece interessati alla possibilita di inferireun linguaggio mediante un numero finito di esempi, o si e interessati anchealla complessita computazionale del processo, allora l’uso di un oracolo puoportare a delle di"erenze notevoli nel processo di induzione.

Con il simbolo D(L) si indichera una presentazione ammissibile del lin-guaggio L, inoltre una grammatica Gi si dira compatibile con gli esempipresentati se genera tutti gli esempi positivi e nessuno degli esempi negativitra quelli presentati fino a quel punto dalla sorgente.

2.1.4

Macchine inferenziali induttive+

"#$

#%

Astratte

Concrete

&Esaustive

Euristiche

Con maccchina inferenziale induttiva astratta si vuole indicare un tipodi algoritmi e"ettivi la cui realizzazione pratica sarebbe poco e!ciente mache hanno valore da un punto di vista teorico. Il piu importante di questi el’induzione per numerazione. L’importanza dell’algoritmo di induzione pernumerazione nella teoria dell’inferenza induttiva viene messa in rilievo dallaseguente congettura largamente condivisa [ZL95]: Ogni classe di linguaggiricorsivi identificabili al limite da una generica macchina inferenziale indutti-va M , e anche identificabile da una macchina inferenziale induttiva M che fauso dell’algoritmo di induzione per numerazione. Inoltre l’identificazione puosempre essere fatta rispetto a diverse numerazioni della classe di linguaggi.Il metodo di inferenza per numerazione e un metodo di inferenza generalemolto potente, ma e essenzialmente uno strumento teorico. La scrittura di uncodice per calcolatore che faccia uso di questo algoritmo, e che sia e!ciente,e praticamente impossibile, poiche la grandezza dello spazio in cui cercare egeneralmente esponenziale rispetto alla lunghezza dell’ipotesi giusta.

Per algoritmi induttivi concreti si intende invece quegli algoritmi che


possono essere e"ettivamente usati per scoprire regolarita all’interno di se-quenze. Tra gli algoritmi induttivi concreti si puo distinguere tra algoritmiinduttivi esaustivi e algoritmi induttivi euristici.

• Gli algoritmi induttivi esaustivi sono procedure e"ettive in cui, per de-terminare quale elemento dello spazio delle ipotesi deve essere sceltocome congettura, in base agli esempi fino ad allora presentati, non sifa uso di processi aleatori. La maggior parte di questi algoritmi ma-nipolano informazioni di tipo simbolico, e garantiscono la convergen-za verso la grammatica obiettivo quando gli esempi sono un insiemerappresentativo del linguaggio.

• Negli algoritmi induttivi euristici la garanzia di successo secondo certicriteri viene persa: nella ricerca della congettura migliore si tralascia,piu o meno volutamente, di seguire delle strade per aumentare l’e!-cienza di calcolo del metodo. Spesso queste procedure si basano su deimeccanismi aleatori, come avviene ad esempio nel random–walk e nelhill–climbing. Alcuni algoritmi di questa classe, tra cui le reti neura-li, manipolano informazioni di tipo numerico: generalmente in questocaso l’algoritmo tollera una piccola percentuale di rumore [HP00]. Tragli algoritmi euristici che fanno uso di una rappresentazione intermediatra quella simbolica e quella numerica troviamo ad esempio gli algo-ritmi evolutivi: si manipolano informazioni simboliche attraverso deiprocessi aleatori numerici.

Confrontare algoritmi induttivi

Esistono fondamentalmente quattro modi di confrontare la bonta degli al-goritmi induttivi, che si basano sull’insieme massimo di linguaggi indotticorrettamente, sulla qualita dei dati necessari alla corretta induzione, sullaquantita di dati necessari alla corretta induzione, sul numero di congettureerrate prodotte prima di generare l’ipotesi corretta.

• Indichiamo con C un particolare criterio di successo, con D un tipo dipresentazione degli esempi e con I una classe di macchine inferenzialiinduttive.

Definizione 2.4. Per ogni metodo di induzione M # I si definiscescope di M rispetto a C e a D, e si indichera con scopeCD(M) l’insiemedei concetti che M inferisce correttamente rispetto a C su degli esempipresentati in modalita D.


Definizione 2.5. Date due macchine inferenziali induttive M1 e M2,M1 e piu potente di M2 rispetto a C e a D se accade che

scopeCD(M1) , scopeCD(M2)

.

Definizione 2.6. Un insieme di regole U si dira inferibile rispetto aI, C,D se accade che scopeCD(M) , U per un M # I. L’insiemecontenente tutti gli insiemi inferibili rispetto a I, C,D e indicato conInf(I, C,D). Un insieme U e esattamente inferibile rispetto a I, C,Dse U e esattamente uguale allo scopeCD(M) per un M # I. L’insieme ditutti gli insiemi esattamente inferibili viene indicato con Xinf(I, C,D).

Un metodo per confrontare tra di loro diversi criteri di successo econfrontare gli insiemi Inf(I, C,D) e Xinf(I, C,D) dei diversi criteri.

• Un altro metodo consiste nel confrontare i dati necessari per la correttaidentificazione. Poiche il processo di inferenza e, nel caso di identifi-cazione al limite, potenzialmente infinito, nessun algoritmo puo in ge-nerale accorgersi con certezza di essere arrivato alla congettura giusta.Quindi la corretta identificazione al limite sembra essere un criterio disuccesso troppo astratto per essere usato in pratica, e puo essere utilerinforzarlo con delle richieste sulla qualita delle congetture prodotte adun qualsiasi punto del processo induttivo. Molti lavori hanno tentatodi definire delle misure di bonta per le ipotesi fatte dal sistema, anchein funzione degli esempi presentati, e hanno cercato poi di capire qualialgoritmi potevano essere adatti ad una ricerca che tenesse conto di talimisure. Queste misure sono state definite con lo scopo di catturare lasemplicita delle ipotesi, e la capacita di tali ipotesi di combaciare congli esempi presentati [AS83].

• Si puo misurare l’e!cienza di un metodo di inferenza attraverso ilnumero di esempi che gli sono necessari per generare una correttacongettura induttiva. Se M e un metodo di inferenza e

x = x1, x2, x3, . . .

e una presentazione ammissibile di un linguaggio L che M corretta-mente inferisce, si definisce il punto di convergenza di M su x il piupiccolo intero positivo n tale che M genera una corretta ipotesi per Lprima che l’esempio xn+1 venga fornito, e che tale ipotesi non venga


piu cambiata da M . Se M1 e M2 sono due macchine inferenziali in-duttive, allora si dice che M1 e tanto data–e"ciente quanto M2 se esolo se per ogni presentazione ammissibile x di ogni linguaggio L cheM2 identifica, M1 identifica anch’esso L ed il punto di convergenza diM1 su x non supera il punto di convergenza di M2 su x. Si dice inol-tre che M1 e strettamente piu data–e"ciente di M2 se e solo se M1 edata–e!ciente quanto M2, ed esiste un linguaggio L identificabile cor-rettamente al limite da M2, con una presentazione ammissibile x perL, tali che il punto di convergenza di M1 su x e strettamente minoredel punto di convergenza di M2 su x. Infine un algoritmo induttivoM si dice ottimamente data–e"ciente, se e solo se non esiste alcunalgoritmo strettamente piu data–e!ciente di M . Gold ha dimostrato[Gol67] che, abbastanza sorpendentemente, il metodo di identificazioneper numerazione e un algoritmo induttivo ottimamente data–e!ciente.

• Un’altra misura di e!cienza e il numero di congetture cambiate dal-l’algoritmo inferenziale durante un processo induttivo che arriva al suc-cesso. Due quantita sono state definite in questo contesto. Se x e unapresentazione ammissibile di un certo linguaggio ed M e un certo algo-ritmo induttivo, si puo definire DH(M, x) come il numero di congettureprodotte da M durante l’analisi della sequenza di esempi M ; inoltre conMC(M, x) si definisce il numero di volte che M produce un’ipotesi di-versa da quella che la precedeva. Segue che 1 + MC(M, x) e un limitesuperiore per DH(M, x); inoltre si puo a"ermare che se M identificaal limite il linguaggio di cui x e una presentazione ammissibile, allorasia DH(M, x) che MC(M, x) sono finiti.

2.1.5

Criteri di successo %+&

Identificazione al limite

PAC–learning

I criteri di successo che piu sono utilizzati negli studi sull’inferenza gram-maticale sono due.

L’identificazione al limite e stato storicamente il primo paradigma diapprendimento studiato. Nell’esempio sui polinomi era questo il criterio usa-to informalmente per giudicare la corretta identificazione. Sia M un genericoalgoritmo di inferenza induttiva costruito per poter identificare correttamen-te un certo linguaggio R. Se ad M viene fornita una collezione sempre piugrande di esempi e1, e2, e3, . . . riguardanti R, M genera una sequenza poten-zialmente infinita di congetture c1, c2, c3, . . . . Se -m # N : cm e una corretta


descrizione di R e cm = cm+1 = cm+3 = . . . allora si dice che M identi-fica al limite R sugli esempi e1, e2, e3, . . . . In pratica M acquisisce nuoveinformazioni su R al crescere degli esempi fornitigli, e in base a cio modifica,eventualmente, la congettura su R. Se accade che la congettura a partireda un certo istante non viene piu modificata e questa congettura identificacorrettamente R, allora si dice che si ha identificazione al limite.

Nel PAC–learning si richiede una identificazione solo parziale del lin-guaggio. Generalmente si impone anche che il tempo necessario per arrivarea questa soluzione sia in qualche maniera limitato. Definiamo ora formal-mente il PAC–learning per un problema di inferenza grammaticale [Val84].Chiamiamo L l’insieme di linguaggi formali che costituisce lo spazio dei con-cetti, e con G l’insieme di grammatiche che costituisce lo spazio delle ipotesi.Sia definita una distribuzione di probabilita D sull’insieme #! di tutte lepossibili stringhe. Una presentazione ammissibile per questo modello e unasequenza infinita di esempi labellati, in cui gli esempi sono generati rispettoalla distribuzione D: chiamiamo questa presentazione quasi–completa. Ladistribuzione D deve possedere delle proprieta

1. D e completamente arbitraria. Ad esempio delle stringhe possono avereprobalita zero per D.

2. D deve essere stazionaria: la probabilita di presentare una stringa comeesempio deve essere costante durante il processo di induzione.

3. D deve essere sconosciuta all’algoritmo induttivo. In linea di principiola macchina induttiva puo provare a calcolare D analizzando gli esempipresentati, ma in generale non e necessario per l’algoritmo conoscere ladistribuzione per generare una congettura soddisfacente.

Sia L # L il linguaggio da dover inferire e G # G un’ipotesi generatadal’algoritmo induttivo per L

Definizione 2.7. Il tasso di errore error(G) dell’ipotesi G rispetto alladistribuzione D e al linguaggio L e 4.

error(G) ='

x#L$L(G)

D(x)

L’accuratezza della ipotesi G viene quindi espressa rispetto a D, che spe-cifica quali aree dell’insieme di strighe discordanti tra L e L(G), sono piuimportanti. Nel PAC–learning l’algoritmo induttivo prende in ingresso un

4Con . si indica la di!erenza simmetrica, A.B = A !B/A /B


parametro di accuratezza ! ed un parametro di confidenza " e deve generareun’ipotesi G sul linguaggio L che con probabilita almeno 1% " abbia

error(G) & !

Da questo deriva il nome “Probably Approximately Correct”: la gramma-tica e probabilmente (rispetto al parametro di confidenza ") una buonaapprossimazione (rispetto al parametro di accuratezza !) del linguaggio L.

Definizione 2.8. Un insieme di linguaggi L e PAC–lernable se esiste unalgoritmo A tale che $L # L, per ogni distribuzione D su #!, $!(0 < ! < 1),e $"(0 < " < 1), A su una presentazione quasi–completa e con in ingresso !e ", produce con probabilita 1% " una grammatica G tale che error(G) & !.

Si puo notare che nella definizione non viene detto nulla su cosa dovrebbeaccadere nel caso in cui A fallisce nel generare un’ipotesi su!cientementeaccurata. A potrebbe generare un’ipotesi qualsiasi o potrebbe non fermarsimai. La definizione del PAC–learning richiede solo che la probabilita chequesti eventi patologici avvengano e minore di ", dove " puo essere piccolo apiacere.

Generalmente come criterio di successo si usa un criterio di PAC–learningche richieda anche un tempo di calcolo di A al massimo polinomiale, anchese A fallisce nel generare un’ipotesi abbastanza accurata.

Definizione 2.9. Un insieme di linguaggi formali L e e!cientementePAC–learnable se L e PAC–learnable attraverso un algoritmo che usa untempo di calcolo polinomiale in

1. 1! ,

2. 1" ,

3. lunghezza massima n di una stringa, che ha una probabilita diversa dazero per la distribuzione D,

4. lunghezza massima m di una grammatica che genera un linguaggio diL.

Di seguito si parlera piu estesamente dell’identificazione al limite, mentresi riprendera il PAC–learning in relazione all’inferenza dei linguaggi regolari.


2.2 Identificazione al limite

Sia G una classe di grammatiche appartenente ad una classe della gerarchiadi Chomsky: con G si indichera una generica grammatica appartenente a G.Con M si indichera una macchina inferenziale induttiva a valori in G. ConD(L) si chiamera l’insieme delle presentazioni ammissibili di un linguaggioL: nel contesto dell’identificazione al limite le presentazioni ammissibili con-siderate sono la presentazione positiva e la presentazione completa. Se conx si denota un elemento di D(L), x # D(L), con M [x] si indica la sequenzafinita o infinita di congetture che M produce quando in ingresso gli vienefornito x.

Definizione 2.10. Si dice che M converge su x a G e si indica conM [x] 0 G, se accade una delle seguenti cose:

• M [x] e finita ed il suo ultimo elemento e G.

• M [x] e infinita ed e sempre uguale a G a meno di un numero finito divolte.

Il criterio di identificazione al limite verra nel seguito indicato con Il

mentre la convergenza di M verso una generica grammatica G si indicheradicendo che M si stabilizza. Sia L un linguaggio ricorsivamente numerabile

Definizione 2.11. M identifica L al limite se accade che $x # D(L) -G #G : M [x] 0 G e L = L(G).

Se U e un insieme di linguaggi, si dira che:

Definizione 2.12. M identifica U al limite se accade che $L # U Midentifica al limite L

Nel definire questo criterio di successo si e premesso che le presentazioniammissibili sono solo quella positiva e quella completa. Come si puo notaredalla loro definizione in nessuna di queste due modalita di presentazione sispecifica l’ordine di presentazione degli esempi. Questo fatto e dovuto airisultati dimostrati nell’articolo di Gold [Gol67].

Seguendo Gold l’ordine della presentazione influisce in maniera di"erentenella presentazione positiva e nella presentazione completa.

• Presentazione positiva. Gold indica questa modalita con il nometext. Tre varianti di questa presentazione sono state studiate, in ognunavaria la classe della funzione che determina l’ordine di presentazionedegli esempi nella sequenza infinita. La funzione puo essere:

2.2 Identificazione al limite 39

Primitiva Ricorsiva

Ricorsiva

Non E"ettiva

Gold dimostra che, in una presentazione positiva, usare una funzioneche detemina l’ordine degli esempi di tipo ricorsivo e equivalente adusare una funzione non e"ettiva: si possono identificare al limite lastessa classe di funzioni. Diverso e il caso di una presentazione posi-tiva in cui la funzione che determina l’ordine degli esempi e primitivaricorsiva. In questo caso si puo costruire una macchina inferenzialeinduttiva che identifica al limite un generico linguaggio ricorsivamentenumerabile: l’idea e quella di identificare prima la funzione primitivaricorsiva che numera gli esempi, dopodiche costruire, e quindi congettu-rare, una grammatica che si basa su questa funzione. Il procedimentosommariamente descritto e e"ettivo ma per la sua particolarita nonmolto interessante. Nel seguito quando si parlera di presentazione po-sitiva si intendera sempre una funzione di presentazione degli esempidi tipo ricorsivo.

• Presentazione completa. Gold chiama questa modalita informant.In questo caso si considerano tre tipi di funzioni per l’ordine di presen-tazione degli esempi:

Ricorsiva

Non E"ettiva

Request (Teacher)

La modalita request permette all’algoritmo induttivo di scegliere lastringa contenuta nel prossimo esempio labellato. Si puo dimostrare chequesti tre tipi di funzioni, usate per decidere l’ordine di presentazionedegli esempi, sono equivalenti nell’identificazioni al limite.

Un ruolo importante nei risultati sull’identificabilita al limite dei linguaggiformali viene svolto dalla classe dei linguaggi superfiniti

Definizione 2.13. Un insieme di linguaggi e detto una classe superfinitase e solo se all’insieme appartengono tutti i linguaggi formali finiti ed almenoun linguaggio formale infinito.

Alcune importanti di"erenze tra l’identificazione al limite mediante pre-sentazione positiva e mediante presentazione completa vengono evidenziatenei seguenti teoremi.


Teorema 2.14. Non esiste una macchina inferenziale induttiva che puo in-ferire un’intera classe superfinita attraverso una presentazione positiva degliesempi.

Dimostrazione. Supponiamo che per assurdo tale macchina M esista. Co-struiamo una presentazione ammissibile per il linguaggio L%, di cardinalitainfinita e appartenente alla classe superfinita, che non faccia stabilizzare lamacchina M . Consideriamo le stringhe x1, x2, . . . , xn, frammento iniziale diuna presentazione positiva per L%. Poiche per ipotesi M identifica al limi-te ogni linguaggio finito esiste un intero # per cui ripetendo la stringa xn

esattamente # volte al termine del frammento, M dovra convergere ad unagrammatica che genera il linguaggio finito L# = {x1, . . . , xn}:

-# # N : M [x1, x2, . . . ,#( )* +

xn, xn, , . . . , xn] 0 G# e L(G#) = L#

Posso pensare di iterare il procedimento precedente per ogni valore di n: cosıcostruisco una presentazione positiva per L% che non fa stabilizzare M e diconseguenza arrivo ad una contraddizione.

La classe dei linguaggi regolari e una classe superfinita, e quindi non puoessere identificata al limite interamente da un’unica macchina inferenzialeinduttiva attraverso esempi presentati in modalita positiva. Lo stesso accadeper le altre classi della gerarchia di Chomsky, poiche includono propriamentela classe dei linguaggi regolari. Secondo Gold questo risultato sembra avereuna grossa rilevanza nello studio dell’apprendimento del linguaggio naturalenegli esseri umani. Si puo ipotizzare, semplificando moltissimo, che i bam-bini apprendano il linguaggio solo attraverso gli esempi positivi forniti lorodai genitori. Questo ragionamento si basa sull’ipotesi che nell’apprendimentodel linguaggio il fattore determinante sia la componente sintattica, e che lacomponente semantica giochi un ruolo marginale. In base al teorema 2.14questa ipotesi e sbagliata in partenza: non si puo apprendere un linguag-gio regolare, e quindi a maggior ragione un linguaggio naturale, mediantesolo esempi positivi. Una modifica di tale ipotesi deve considerare anchel’influenza di altri elementi. Chomsky, nella sua teoria della grammaticauniversale non abbandona l’approccio puramente sintattico e congettura l’e-sistenza di una struttura gia presente nell’uomo alla nascita, che intervienenell’apprendimento del linguaggio.

L’aggiunta degli esempi negativi aumenta la potenza di una macchinainferenziale induttiva, ma comunque non consente di inferire tutti linguaggiricorsivi:


Teorema 2.15. Non esiste una macchina inferenziale induttiva che puo in-ferire l’intera classe dei linguaggi ricorsivi attraverso una presentazione com-pleta degli esempi.

Dimostrazione. L’idea della dimostrazione e simile al gioco dei polinomi nelcaso in cui il calcolatore fosse programmato per rispondere sempre NO e percorreggerci aumentando di uno la nostra previsione. Supponiamo per assur-do che esista una macchina inferenziale induttiva M che soddisfa le ipotesidel teorema. Costruiamo un linguaggio ricorsivo attraverso la costruzionedi una sua presentazione completa che pero non fa stabilizzare la macchinaM . Con x+

i indicheremo che l’i–ma stringa di #! nell’ordine standard, vienefornita alla macchina M come esempio positivo mentre con x"

j indicheremoinvece che la j–ma stringa di #! viene fornita come esempio negativo. Sup-poniamo che le prime n stringhe di #! vengano fornite come esempi positivix+

1 , x+2 , . . . , x+

n . Dopodiche scegliamo che le stringhe da n + 1 a n + # sianofornite come esempi negativi e che le stringhe da n +#+ 1 a n +#+ $ sianofornite come esempi positivi: # e $ saranno scelti in modo che la congetturadi M dopo le prime n + # stringhe sia diversa dalla congettura di M dopole prime n + # + $ stringhe. Cio e sempre possibile: infatti il linguaggioL# = {x1, x2, . . . , xn} e finito, quindi ricorsivo e di conseguenza per ipotesiidentificabile al limite da M . Essendo la sequenza

x+1 , x+

2 , . . . , x+n , x"

n+1, x"n+2, . . . , x"

n+j , . . .

con j # N una presentazione completa di L#, -# # N :

M [x+1 , x+

2 , . . . , x+n , x"

n+1, x"n+2, . . . , x"

n+#] = G#

con L(G#) = L#. Inoltre la sequenza

x+1 , x+

2 , . . . , x+n , x"

n+1, x"n+2, . . . , x"

n+#, x+n+#+1, x

+n+#+2, . . . , x+

n+#+j, . . .

con j # N definisce un linguaggio L$ , che essendo il complemento di unlinguaggio finito e a sua volta ricorsivo: anche L$ e identificabile al limite daM . Di conseguenza -$ # N :

M [x+1 , x+

2 , . . . , x+n , x"

n+1, x"n+2, . . . , x"

n+#, x+n+#+1, x

+n+#+2, . . . , x+

n+#+$] = G$

con L(G$) = L$ . Con questo ragionamento si dimostra che esistono sem-pre gli # e $ ipotizzati. Iterando il procedimento all’infinito costruisco unapresentazione completa per un linguaggio ricorsivo che pero non permettemai ad M di stabilizzarsi: questo entra in contraddizione con l’ipotesi cheM identifica al limite tutti i linguaggi ricorsivi


Questo teorema dimostra che non e possibile identificare al limite tutti i lin-guaggi ricorsivi mediante un unica macchina inferenziale induttiva che si basisolo su una presentazione completa del linguaggio. Con EX si identifichera laclasse di tutti gli insiemi U di linguaggi ricorsivi per cui esiste una macchinainferenziale induttiva che identifica ogni linguaggio di U .

E importante capire per quali classi di linguaggi l’identificazione al limitee ottenibile attraverso il metodo di indentificazione per numerazione.

Definizione 2.16. Una famiglia di linguaggi viene detta indicizzabile se:

• Ammette una numerazione e!ettiva L0, L1, L3, . . . ;

• La funzione

A(x, i) =

&1 se x # Li

0 altrimenti

che decide sull’appartenenza di una generica stringa x # #! al linguag-gio i–mo nella numerazione e!ettiva, e funzione ricorsiva.

Il fatto che una classe sia indicizzabile e una condizione necessaria manon su!ciente a!nche la classe sia interamente identificabile al limite me-diante l’algoritmo di induzione per numerazione: esistono due importanticondizioni che riguardano lo spazio delle ipotesi e il tipo di presentazionedegli esempi [ZL95].

Teorema 2.17. Una classe indicizzabile di linguaggi e identificabile al limiteda una macchina M che fa uso dell’algoritmo di numerazione, mediante unapresentazione di esempi di tipo D, se si verifica che:

1. Almeno una grammatica della numerazione e compatibile con gli esempidati;

2. Ogni grammatica non corretta e sempre incompatibile con una su"cien-temente grande collezione di esempi; questa condizione viene chiamatacollasso dell’incertezza

Dimostrazione. Nel caso di una classe indicizzabile una macchina inferenzialeinduttiva che si basa sull’algoritmo di induzione per numerazione funziona si-milmente all’esempio suo polinomi da indovinare nel gioco uomo–calcolatore.Come congettura l’algoritmo seleziona, ad un certo istante, la prima gram-matica nella numerazione della classe che accetta tutti gli esempi positivi,non accetta alcun esempio negativo, considerando tutti gli esempi presen-tati fino a quell’istante. Che questa congettura esiste ci e garantito dallaproprieta uno. Il fatto che una grammatica non corretta venga prima o poirimpiazzata e assicurato dal punto due.


Questo teorema ci permette di capire qual’e la classe piu grande della gerar-chia di Chomsky inferibile da una singola macchina induttiva.

Definizione 2.18. Definiamo un linguaggio primitivo ricorsivo se la suafunzione caratteristica e primitiva ricorsiva.

Per l’insieme dei linguaggi primitivi ricorsivi vale un importante teorema:

Teorema 2.19. Esiste una macchina inferenziale induttiva che identifica allimite la classe dei linguaggi primitivi ricorsivi mediante una presentazionecompleta degli esempi.

Dimostrazione. La classe dei linguaggi primitivi ricorsivi e una classe indi-cizzabile: esiste una numerazione e"ettiva della classe ed e decidibile se unastringa appartiene ad un linguaggio della numerazione. Le due condizioni chegarantiscono l’identificazione al limite di una classe indicizzabile si verificanoper la presentazione completa.

L’insieme dei linguaggi primitivi ricorsivi contiene l’insieme dei linguaggidi tipo uno della gerarchia di Chomsky: questo comporta che i linguaggicontext–sensitive, context–free, regolari sono identificabili al limite da unamacchina inferenziale induttiva mediante una presentazione completa degliesempi.

Il tentativo di indebolire le ipotesi del teorema limitandosi alla classe deilinguaggi regolari fallisce. Si puo ad esempio pensare di usare l’algoritmodi numerazione per inferire i linguaggi regolari mediante una presentazio-ne positiva; si puo costruire una numerazione e"ettiva dei linguaggi regolariche tiene conto del numero di stati dell’automa corrispondente al linguaggio.Questa numerazione non funziona poiche non si puo inferire alcun linguaggioche abbia un automa corrispondente dotato di un numero di stati maggio-re dell’automa che accetta il linguaggio regolare proprio uguale a #!: unamacchina si"atta non rispetta la condizione sul collasso dell’incertezza.

E interessante notare che l’algoritmo di induzione non e poi cosı lentocome sembra. Consideriamo una macchina induttiva M che usi l’algoritmoper numerazione: non esiste un’altra macchina M che riesce ad identificareal limite, piu velocemente di M , tutti i linguaggi di scopeIlD(M). Siano M1,M2 due macchine inferenziali induttive, L un linguaggio formale e iL unapresentazione ammissibile di L. Con %(M, L, iL) si indichera il tempo dopocui la macchina inferenziale M genera la grammatica su cui si stabilizza eche genera L.

Definizione 2.20. Si dice che M1 e uniformemente piu veloce di M2 seaccade


1. $L $iL # D M1 identifica L su iL almeno nello stesso tempo di M2,

%(M1, L, iL) & %(M2, L, iL)

2. -L e iL :

%(M1, L, iL) < %(M2, L, iL)

In queste definizioni si sottintende un’idea di tempo discreto: la misuradel tempo necessario ad una macchina inferenziale per svolgere un compito eequivalente alla misura del numero di operazioni elementari neccessarie allamacchina per svolgere quel compito.

Teorema 2.21. Sia M una macchina inferenziale induttiva basata sull’al-goritmo di numerazione, con un insieme di esempi ammissibili appartenentia D. Non esiste una macchina inferenziale induttiva M uniformemente piuveloce di M su scopeIlD(M).

Dimostrazione. Dimostriamo che se -L e iL per cui

%(M, L, iL) < %(M, L, iL)

allora -L e iL per cui

%(M, L, iL) < %(M, L, iL)

Poiche M e basata su un algoritmo di numerazione possiamo sempre supporreche sia una macchina conservativa: non cambia ipotesi fin quando l’ipotesicorrente non diventa incompatibile con gli esempi presentati. Supponiamoche M sia piu veloce di M nell’identificare L

%(M, L, iL) < %(M, L, iL)

Chiamiamo Gp la grammatica congetturata da M al tempo %(M, L, iL): que-sta grammatica genera un linguaggio Lp 1= L. Si puo prolugare il frammentodi esempi forniti alle macchine fino all’istante %(M, L, iL) per costruire unapresentazione ammissibile per il linguaggio Lp. Su una presentazione cosıcostruita si e certi che la macchina M si stabilizzera sulla grammatica esat-ta Gp prima di M , poiche M e conservativa. Si e costruito un linguaggioL = Lp :

%(M, L, iL) < %(M, L, iL)

da cui la tesi.


Alcune interessanti variazioni possono essere fatte sul criterio di identifi-cazione al limite.

• Si dice che un linuaggio e BC–identificabile5 al limite se a partire daun punto tutte le ipotesi fatte dall’algoritmo induttivo sono delle gram-matiche che correttamente generano il linguagio da inferire. Rispettoall’identintificazione al limite si permette all’algoritmo di cambiare lapropia congettura nel tempo, purche la nuova congettura sia ancorauna grammatica che genera il linguaggio. Se si indica con BC la clas-se di tutti gli insiemi di linguaggi ricorsivi per cui esiste un algoritmoinduttivo che BC–identifica ogni linguaggio dell’insieme, allora si puodimostrare che EX e un sottoinsieme proprio di BC [CS83].

• Esiste una variazione dell’identificazione al limite che considera un lin-guaggio correttamente inferito anche se la grammatica ottenuta al li-mite contiene un certo numero di errori: questi errori sono chiamatianomalie. Per ogni numero naturale k, un algoritmo induttivo M iden-tifica al limite un linguaggio L con al piu k anomalie, se e solo seM converge verso un grammatica G tale che la di"erenza simmetricaL(G) . L contiene al piu k elementi. Con EXk si indica la classe ditutti gli insiemi U di linguaggi ricorsivi, per cui esiste un algoritmoinduttivo che identifica U al limite con al piu k anomalie. Di con-seguenza EX0 = EX. Inoltre con EX! si indica la classe di tutti gliinsiemi U di linguaggi ricorsivi per cui esiste un algoritmo induttivo cheidentifica al limite U con un numero finito di anomalie. Si puo dimo-strare che EX0, EX1, EX2, . . . e una gerarchia di classi la cui unionee propriamente contenuta in EX! [CS83].

Una restrizione importante che si puo invece fare sugli algoritmi induttiviquando si lavora con l’identificazione al limite e l’a"dabilita di tali algorit-mi. Questa restrizione richiede che se una macchina inferenziale induttivaconverge su una sequenza di esempi, deve convergere verso un’ipotesi cor-retta. Se un algoritmo induttivo fallisce nell’identificazione al limite di unlinguaggio, lo deve fare cambiando la grammatica congetturata un numeroinfinito di volte. In un algoritmo induttivo a!dabile l’identificazione al limitee conseguenza di un numero finito di mind change MC. Formalmente unamacchina inferenziale induttiva M e a"dabile su un insieme di linguaggi U ,se e solo se per ogni linguaggio in U , e per ogni presentazione ammissibilex del linguaggio, se M [x] converge allora deve convergere ad una gramma-tica che genera il linguaggio. Si puo dimostare che la classe degli insiemi

5Behaviorally correct


di linguaggi identificati al limite da metodi di inferenza a!dabili godono diimportanti proprieta di chiusura. Ad esempio questa classe e chiusa sottol’unione infinita, mentre invece la classe EX non e chiusa nemmeno sottol’unione finita [BB75] [Min76]. La non chiusura della classe EX sotto unio-ne finita un fatto e di notevale importanza: l’operazione di unione finita eun meccanismo costruttivo evidente, che sorpendentemente in questo casoconduce ad una netta distinzione tra le parti che costituiscono un insieme el’insieme stesso.

2.3 Inferenza grammaticale regolare

I linguaggi regolari sono la classe di linguaggi piu semplice nella gerarchiadi Chomsky. Lo studio dell’inferenza induttiva per linguaggi regolari ha di-versi motivi di interesse pratico, tra questi il fatto che ogni linguaggio finitoe regolare e che spesso linguaggi che appartengono ad altre classi della ge-rarchia chomskyana possono essere approssimati proprio da un linguaggioregolare [FB75]. L’inferenza grammaticale regolare non e un problema sem-pre e!cientemente risolvibile: solo se gli esempi forniti sono su!cientementecaratterizzanti per il linguaggio, o se si forniscono informazioni addizionali,si puo arrivare ad una soluzione in tempi accettabili.

I linguaggi context–free o context–sensitive sono certamente piu espressividi quelli regolari e cio ha portato molti ricercatori a studiare i problemiconnessi con l’inferenza induttiva di tali classi. Bisogna pero notare che glialgoritmi induttivi usati in questi ultimi studi sono quasi tutti di naturaeuristica e, fatto certamente importante, riescono ad arrivare a dei risultatipositivi solo nel caso in cui il linguaggio da inferire sia molto semplice. Ilinguaggi context–free e context–sensitive costituiscono un utile astrazioneper lo studio di importanti questioni teoriche, e certamente lo studio deglialgoritmi di induzione per questi linguaggi ha un importante peso teorico,bisogna pero notare che l’utilita di questi linguaggi per la modellizazione delmondo reale e un fatto tutto da dimostrare.

Lo studio degli algoritmi concreti per l’inferenza grammaticale regolareparte dai lavori di Gold: il teorema 2.19 garantisce l’inferibilita al limite dellaclasse dei linguaggi primitivi ricorsivi attraverso una presentazione comple-ta. La classe dei linguaggi regolari e una sottoclasse dei linguaggi primitiviricorsivi, quindi esiste un algoritmo induttivo che permette di inferire qual-siasi linguaggio regolare. Teoricamente anche l’algoritmo di identificazioneper numerazione puo, attraverso una qualsiasi numerazione e"ettiva dellegrammatiche lineari, portare con successo all’identificazione al limite di un

2.3 Inferenza grammaticale regolare 47

linguaggio regolare: come e stato gia sottolineato questo algoritmo e talmenteine!ciente da non essere praticamente mai utilizzabile.

Un algoritmo induttivo e!ciente per inferire correttamente un linguaggioregolare si deve basare su una procedura che al crescere degli esempi positivie negativi, fornisca la piu piccola grammatica compatibile con gli esempipresentati in un tempo polinomiale rispetto alla taglia degli esempi Unaprocedura si"atta e stata presentata per l’esempio sull’inferenza induttiva diuna sequenza polinomiale: il teorema 1.2 suggerisce un metodo per calcolareil piu piccolo polinomio compatibile con gli esempi in un tempo polinomialerispetto al numero degli esempi. Lo stesso Gold [Gol78] dimostra che nonesiste una procedura che svolge lo stesso compito nell’inferenzagrammaticale regolare in maniera e!ciente

Teorema 2.22. Il problema di trovare il piu piccolo automa finito determi-nistico compatibile rispetto ad un insieme di esempi labellati, e un problemaNP-hard.

In questo teorema si parla di automi finiti, dove per piu piccolo si intenderispetto al numero degli stati, ma lo stesso risultato vale per le gramma-tiche regolari, dove piu piccolo e da intendersi rispetto al numero di sim-boli distinti presenti nella grammatica, e per le espressioni regolari, dovepiu piccolo e da intendersi rispetto al numero di simboli terminali presentinell’espressione [Ang78].

Questo teorema e il punto di partenza di un ricco filone di studi: moltiricercatori hanno ideato e sperimentato algoritmi per trovare il piu piccoloautoma finito compatibile con un insieme finito di esempi labellati. Gli studisono diramati in diverse direzioni:

• Un significativo numero di lavori si prefiggevano di trovare delle relazio-ni che legassero l’insieme di esempi labellati con il linguaggio regolareda inferire, in modo da garantire l’e!cienza di certi algoritmi esausti-vi. Trakhtenbrot e Barzdin hanno proposto un algoritmo che induceil piu piccolo DFA consistente con un insieme completo di esempi la-bellati, cioe con un insieme costituito da esempi labellati che copronotutte le stringhe di #! fino alla lunghezza 2n % 1, dove n e il numerodi stati dell’automa canonico [TB73]. Oncina e Garcia hanno definitoun insieme caratteristico di esempi labellati, cioe un insieme di esempirappresentativo del linguaggio regolare che in qualche maniera codificainformazioni sugli stati e sulle transizioni dell’automa corrisponden-te. In questo lavoro si dimostra che attraverso un insieme si"atto epossibile inferire il DFA minimo in tempo polinomiale [OG92].


• Un altro approccio si basa sulla possibilita di fornire al sistema delleinformazioni aggiuntive riguardo al linguaggio regolare, che completinoin maniera utile le informazioni contenute nell’insieme di esempi label-lati, facendo diventare il processo di inferenza induttiva polinomiale.Le informazioni aggiuntive possono essere, ad esempio, le risposte diun oracolo a domande sulla struttura del linguaggio regolare. Angluin[Ang87] ha descritto un algoritmo che si basa su un minimally adequateteacher, che guida il sistema all’inferenza dell’automa minimo. Un mi-nimally adequate teacher e un oracolo capace di rispondere a due tipidi domande

membership queries ovvero domande nella forma “Questa stringaappartiene al linguaggio regolare?”,

equivalence queries cioe domande nella forma “E questo DFA eqi-valente all’automa minimo?”.

Angluin dimostra che usando gli esempi labellati insieme a questo ora-colo e possibile inferire il piu piccolo DFA compatibile con gli esempiin tempo polinomiale.

E importante sottolineare che nell’inferenza grammaticale regolare sonopossibili diverse scelte per descrivere in maniera intensionale il linguaggioregolare. Si possono usare equivalentemente grammatiche lineari, espressioniregolari, automi finiti deterministici, automi finiti non deterministici; nellamaggior parte dei lavori si scelgono pero gli automi finiti deterministici. Cioe dovuto in parte a delle importanti caratteristiche di questi automi

• sono semplici e intuitivamente comprensibili,

• esiste un unico DFA minimo per ogni linguaggio regolare,

• esiste un algoritmo e!ciente che per ogni DFA produce il DFA cheaccetta lo stesso linguaggio e ha il numero minimo di stati,

• esiste un algoritmo e!ciente che decide se il linguaggio accettato dadue DFA e lo stesso,

• esiste un algoritmo e!ciente che decide se il linguaggio accettato da unDFA contiene il linguaggio accettato da un altro DFA.

Inoltre poiche esiste un algoritmo e!ciente che consente di passare da un DFAad una grammatica regolare che genera lo stesso linguaggio, e viceversa, delleconsiderazioni simili sono valide anche per le grammatiche regolari.


q0 q1

q2

q3 q4 q5

1

0 0 0 0

Figura 2.1: Esempio di Prefix Tree Automaton

2.3.1 Caratterizzazione algebrica dello spazio di ricer-ca

L’inferenza grammaticale regolare puo essere riformulata come un problemadi ricerca all’interno dello spazio di tutti gli automi finiti. Chiaramente que-sto spazio ha cardinalita infinita. Un primo passo per rendere piu e!cienteil procedimento di induzione e ridurre lo spazio di ricerca ad un insieme piupiccolo, preferibilmente di cardinalita finita: questa idea, applicata all’infe-renza grammaticale regolare, viene per la prima volta espressa in [FB75].Supponiamo che S+ sia un insieme finito di esempi positivi, se S+ soddisfacerte caratteristiche che verranno specificate nel seguito, la ricerca del piupiccolo automa finito che genera le stringhe appartenenti a S+ puo esserecondotta all’interno di un reticolo di cardinalita finita di automi finiti.

Inizialmente l’insieme S+ viene usato per costruire un prefix tree auto-maton (PTA). Un PTA e un automa finito deterministico: si costruisconotanti rami nel grafo in corrispondenza delle stringhe di S+, dopodiche siuniscono i percorsi che hanno il prefisso in comune. Il PTA di un insiemedi stringhe U accettera tutte e solo le stringhe di U . Ad esempio il PTAcorrispondente al sample S+ = {1, 00, 0000} di esempi positivi e mostratoin figura 2.1. L’insieme di tutte le partizioni possibili degli stati del PTA,insieme ad una relazione d’ordine parziale tra gli elementi dell’insieme basatasul linguaggio accettato, definisce una struttura di reticolo. Ogni elementodel reticolo e chiamato automa quoziente, ed e costruito a partire dal PTAfondendo insieme stati che apparterranno poi allo stesso blocco della parti-zione. Gli automi quozienti sono in generale automi non deterministici, inquanto la funzione di transizione di un automa ottenenuto fondendo innsie-me gli stati qi e qj , si ottiene facendo partire dal nuovo stato le transizioniche partivano da qi insieme alle transizioni che partivano da qj . Ad esem-pio, l’automa quoziente che si ottiene fondendo insieme gli stati q0 e q1 delPTA di fig. 2.1 e mostrato in fig. 2.2–a la corrispondente partizione degli


q1 q3 q4 q5q0 0 0 0 0

q2

1

q3 q4 q5q0

a) b)

1

0 0 0

0

Figura 2.2: Esempi di Automa Quoziente

stati e {{0, 1}, {2}, {3}, {4}, {5}}. L’automa quoziente e sempre piu generaledell’automa da cui e stato generato: il suo linguaggio contiene il linguaggiodell’automa di partenza. Gli elementi, cioe le partizioni, del reticolo sonoparzialmente ordinate da una relazione di ricoprimento. Una partizione rico-pre un’altra se la prima e ottenuta fondendo insieme due o piu blocchi dellaseconda. Ad esempio la partizione {{0, 1, 2}, {3}, {4, 5} ricopre la partizione{{0, 1}, {2}, {3}, {4}, {5}}. Una importante proprieta di questa relazione eche se una partizione ricopre un’altra, il linguaggio accettato dall’automafinito rappresentato dalla prima partizione contiene il linguaggio accettatodall’automa finito corrispondente alla seconda partizione. Il PTA e il piuspecifico elemento del reticolo, cioe l’elemento minimo rispetto alla relazionedi ricoprimento. Il DFA universale, che si ottiene fondendo insieme tutti glistati del PTA in un unico stato, e il piu generale elemento del reticolo, cioel’elemento massimo rispetto alla relazione di ricoprimento. Partendo dal PTAdi fig. 2.1, la partizione corrispondente al DFA universale e {{0, 1, 2, 3, 4, 5}}.Il reticolo ha una cardinalita finita ma esponenziale ripetto al numero deglistati del PTA di partenza: precisamente partendo da un PTA con m stati ilreticolo ha cardinalita uguale a :

Em =m"1'

j=0

,m% 1

j

-Ej con E0 = 1.

Questo numero proibitivo rende impraticabile qualsiasi algoritmo di ricercache si basi sull’identificazione per numerazione. Per cercare la soluzione nelreticolo si parte dal PTA o dall’automa universale e si applicano ripetuta-mente degli operatori che generano nuovi elementi del reticolo: in generalequesti operatori agiscono essenzialmente fondendo e dividendo i blocchi distati di una partizione del reticolo.

Se l’insieme S+ e strutturalmente completo, si puo dimostrare che il piupiccolo automa finito deterministico che acceta S+ appartiene al reticolocostruito attraverso il PTA [PC78]. Un insieme strutturalmente completo


0 q1 q20q

q

0

3

0

1

Figura 2.3: Automa Esempio

per un DFA e un insieme di esempi positivi S+, tali che per ogni transizionedel DFA esiste almeno una stringa in S+ che copre la transizione, e per ognistato finale del DFA c’e almeno una stringa in S+ che usa quello come statoaccettore.Formalmente 6

Definizione 2.23. Se D = (#, Q, ", q0, F ), un insieme di esempi positiviS+, e strutturalmente completo per D se:

1. $a # #, $qi, qj # Q, se "(qi, a) = qj, e una transizione per D allora

-# # S+, con # = $a& $, & # #!, tale che ."(q0, $) = qi e ."(qj , &) # F ,

2. $qi # F, -# # S+ tale che ."(q0,#) = qi.

Si puo verificare che l’insieme S+ = {1, 00, 0000} e strutturalmente com-pleto per l’automa di fig.2.3. In generale per un DFA non esiste un unicoinsieme strutturalmente completo, inoltre ogni insieme di esempi positivi checontiene un insieme strutturalmente completo e a sua volta strutturalmentecompleto.

2.3.2 Strategie di ricerca nel reticolo

Nonostante l’automa minimo appartenga con certezza al reticolo, la cardi-nalita di questo e talmente grande da escludere l’uso di qualsiasi tecnica di

6In questa definizione si assume che il DFA D non abbia stati morti, cioe stati da cuinon e possibile raggiungere uno stato finale


ricerca uniforme, cioe di tipo breadth–first. Diversi metodi induttivi ese-guono la ricerca all’interno del reticolo, aiutati da informazioni addizionalisull’automa minimo.

Parekh e Honavar hanno proposto una strategia di ricerca bidirezionalechiamata version–space approach [HP00]. Il version–space e un termine gianoto in machine learning: sta ad indicare il sottoinsieme dello spazio delleipotesi, in un problema induttivo, compatibile con gli esempi presentati. Illoro metodo assume che un insieme strutturalmente completo di esempi po-sitivi S+ sia inizialmente fornito all’algoritmo induttivo; inoltre si supponel’esistenza di un oracolo in grado di rispondere a domande sull’appartenen-za di stringhe al linguaggio regolare. Il reticolo di automi finiti definito inprecedenza risulta implicitamente rappresentato nel version–space. In questospecifico algoritmo il version–space risulta essere l’insieme di tutti gli elementidel reticolo compatibili con gli esempi labellati e con le risposte dell’oracolo.Esso viene rappresentato usando due insiemi di automi finiti: un insiemeS degli automi finiti piu specifici, che inizialmente contiene solo il PTA re-lativo a S+, ed un insieme G degli automi finiti piu generali, che contieneinizialmente solo l’automa universale relativo al PTA. Quindi inizialmente ilversion–space comprende tutti gli elementi del reticolo: esso viene poi gra-dualmente ra!nato eliminando quegli elementi che risultano incompatibilicon i nuovi dati acquisiti. L’algoritmo seleziona due automi finiti, uno daS e uno da G: se non risultano essere equivalenti viene chiesto all’oracolose la piu piccola stringa accettata da uno solo dei due automi appartiene allinguaggio. Il ra!namento di S e G e guidato dalla risposta dell’oracolo: sel’oracolo riconosce la stringa come non appartenente al linguaggio regolare dainferire, e la stringa era accettata dall’automa proveniente da S, allora sem-plicemente l’automa viene eliminato da S. Inoltre tutti gli elementi di G cheaccettano degli esempi negativi vengono modificati, separando gli stati nellepartizioni, fino ad arrivare ad un automa che non accetta gli esempi negati-vi. Cosı tutti gli automi che accettano gli esempi negativi vengono eliminatidal version–space. Le domande sull’appartenenza delle stringhe servono pergeneralizzare progressivamente gli elementi di S e specializzare gli elementidi G. La convergenza verso l’automa minimo e garantita e si ottiene quandoS = G, ed entrambi gli insiemi sono costituiti dal medesimo elemento. Nelcaso peggiore la complessita del metodo e esponenziale rispetto al numero distati del PTA, quindi questo e un metodo esaustivo non e!ciente. L’aggiun-ta di un oracolo che risponde a domande sull’appartenenza di una stringaal linguaggio non potenzia su!cientemente l’informazione fornita al sistemainduttivo.

L’algoritmo regular positive and negative inference (RPNI) esegue unaricerca ordinata di tipo depth–first nel reticolo. Questa ricerca viene guidata


da un insieme negativo di esempi S", ed in tempo polinomiale identifica unDFA compatibile con il sample S = S+!S". Inoltre se accade che S contieneun insieme caratteristico per il DFA, allora l’algoritmo calcola il DFA minimocompatibile con S. Un insieme di esempi S = S+ !S" e caratteristico se S+

e un insieme strutturalmente completo rispetto al linguaggio da inferire, e seS" impedisce che due stati non equivalenti del PTA vengano uniti insiemenella ricerca [OG92]. L’algoritmo prima costruisce il PTA corrispondentea S+. Gli stati del PTA vengono numerati secondo l’ordine standard del-la stringa a cui corrispondono: gli stati del PTA di fig. 2.1 sono numeratisecondo quest’ordine. L’algoritmo inizializza la soluzione all’automa PTA,e sistematicamente fonde gli stati del PTA per trovare una soluzione piugenerale consistente con S. La funzione di transizione del nuovo automa,che in generale sara non deterministico, si ottiene facendo partire dal nuovostato le transizioni che partivano dai due stati fusi,. Gli stati del PTA sonosistematicamente uniti in un loop quadratico, cioe ad ogni passo i, l’algorit-mo prova a fondere lo stato qi, nell’ordine, con gli stati q0, q2, . . . , qi"1. Sel’automa quoziente ottenuto attraveso l’ultima unione di qi con un qualsiasistato non accetta alcun esempio di S", allora l’automa quoziente viene elettocome soluzione precaria del problema, e la ricerca continua con lo stato qi+1.Se 2S+2 e 2S"2 denotano la somma delle lunghezze di ogni esempio in S+

e S" rispettivamente, allora si puo mostrare che la complessita temporaledell’algoritmo RPNI e O((2S+2 + 2S"2) · 2S+22). Seguiamo un esempio diesecuzione del RPNI nell’inferenza dell’automa di fig. 2.3. Supponiamo chesia dato un sample caratteristico S = S+ ! S", dove S+ = {1, 00, 0000} eS" = {', 0, 000, 100}. Il PTA corrispondente a S+ e ra!gurato in fig. 2.1,con gli stati numerati secondo l’ordine standard. La partizione iniziale, corri-spondente al PTA, e {{0}, {1}, {2}, {3}, {4}, {5}}. Il blocco {0} ed il blocco{1} della partizione vengono uniti e il risultato e mostrato in fig. 2.2–a: poi-che tale automa accetta l’esempio negativo 0, l’unione viene rigettata. Allorail blocco {0} ed il blocco {2} della partizione sono uniti, ottenendo l’automarappresentato in fig. 2.2–b; in questo caso l’automa quoziente ottenuto ac-cetta l’esempio negativo ', e viene quindi anch’esso rifiutato. Continuandoad unire gli stati in questa maniera si puo mostrare che l’algoritmo resti-tuisce la partizione {{0}, {1, 4}, {2}, {3, 5}}, che e esattamente l’automa difig. 2.3, rispetto a cui S e caratteristico. L’algoritmo RPNI e un algoritmoesaustivo che si dimostra e!ciente se l’insieme e abbastanza rappresentati-vo del linguaggio, per questo e molto studiato e diverse varianti sono statesviluppate.

Gli Algoritmi Genetici sono un interessante strumento per la ricerca eu-ristica in uno spazio delle ipotesi molto esteso [Hol75] (vedi capitoli successi-vi). L’applicazione di questi algoritmi consiste nell’evoluzione di un insieme


casuale di elementi dello spazio delle ipotesi, che si basa sul principio dellasopravvivenza dell’individuo migliore; questo principio e alla base della teoriadarwiniana dell’evoluzione. Viene scelto uno schema appropriato per codifi-care gli elementi dello spazio delle ipotesi come dei cromosomi. Una funzionedi fitness viene definita per valutare le qualita delle soluzioni rappresenta-te nei singoli cromosomi. La ricerca prosegue per diverse generazioni. Inogni generazione un gruppo di elementi buoni, rispetto al valore attribuito-gli dalla funzione di fitness, viene scelto per la riproduzione, che si e"ettuaattraverso l’applicazione di operatori genetici appropriati come la mutazioneo il crossover. L’uso degli operatori genetici serve per individuare nuove epotenzialmente interessanti aree dello spazio delle ipotesi. Il risultato dellariproduzione viene posto in una nuova popolazione e l’evoluzione viene con-tinuata: dopo un certo periodo di tempo gli individui della popolazione ten-dono a convergere verso valori di fitness piu alti e quindi verso elementi dellospazio delle ipotesi ragionevolmente migliori. Dupont [Dup94] ha usato glialgoritmi genetici per cercare il minimo automa nel reticolo definito dal PTA.All’algoritmo viene fornito un sample S = S+!S" di esempi labellati. Vienecostruito un PTA sugli esempi S+ come e stato prima illustrato. La popola-zione iniziale e costituita da una selezione casuale di elementi appartenentiall’insieme di tutte le partizioni possibili degli stati del PTA. Ogni elementodel PTA e quindi un automa quoziente appartenente al reticolo corrispon-dente al PTA. La fitness assegnata ad ogni automa quoziente e funzione didue variabili: il numero degli stati dell’automa e il numero di esempi negativiappartenenti a S" rifiutati dall’automa. Automi con pochi stati e che fannomeno errori hanno una fitness piu alta. Dopo ogni generazione un sottoin-sieme della popolazione viene scelto casualmente, sulla base della fitness, perriprodursi e creare una nuova popolazione. Gli operatori genetici usati sono lamutazione strutturale e il crossing–over strutturale. La mutazione strutturalesceglie casualmente un elemento da un blocco della partizione e lo assegnaad un altro blocco. Quindi, {{0, 1, 3, 5}, {2}, {4}}%+ {{0, 1, 5}, {2, 3}, {4}}e un esempio di mutazione strutturale. Il crossing–over strutturale producedue nuovi elementi: un blocco di stati e scelto casualmente da ogni geni-tore ed entrambi i discendenti ereditano il blocco ottenuto fondendo i dueblocchi selezionati. I rimanenti blocchi dei discendenti si ottengono pren-dendo la di"erenza dei blocchi delle partizioni che non sono stati coinvoltinel crossover. Per esempio, se i genitori sono rappresentati dalle seguentipartizioni {{0}, {1, 4}, {2, 3, 5}} e {{0}, {1, 3}, {2}, {4}, {5}} allora da unasingola applicazione del crossover si possono ottenere i seguenti discenden-ti {{0}, {1, 3, 4}, {2, 5}} e {{0}, {1, 3, 4}, {2}, {5}}. Qui i blocchi {1, 4} e{1, 3} sono prima fusi per ottenere un blocco comune che verra ereditato daentrambi i discendenti. La di"erenza del blocco {0} con il blocco {1, 3, 4} e


{0}, la di"erenza del blocco {2, 3, 5} con {1, 3, 4} e {2, 5} e cosı via. I discen-denti prodotti con l’applicazione di questi operatori sono partizioni che concertezza appartengono al reticolo, e vengono aggiunti alla popolazione. Unmeccanismo casuale, ma pesato sulla fitness, seleziona gli elementi che faran-no parte della prossima popolazione. Dopo un fissato numero di generazioni,i migliori individui sono restituiti dall’algoritmo come risultato dell’inferen-za. Anche se questo approccio non garantisce la convergenza al DFA minimo,si ottengono dei buoni risultati con automi relativamente piccoli: questo equindi un tipico esempio di algoritmo euristico.

2.3.3 L’algoritmo L3

Esistono algoritmi per eseguire l’inferenza grammaticale regolare che nonfanno uso del reticolo associato al PTA: l’algoritmo L! inferisce il minimoDFA compatibile con un insieme di esempi labellati attraverso l’aiuto di unminimally adequate teacher [Ang87]. Esso costruisce un DFA ponendo adun oracolo delle domande sull’appartenenza di una stringa al linguaggio esull’equivalenza di un DFA a quello minimo. Quando nessuna coppia di statie sospettata di essere equivalente, l’algoritmo pone una domanda all’oraco-lo per sapere se l’automa rappresentato attualmente dalla tabella e quellominimo. Se l’oracolo risponde SI, l’algoritmo termina restituendo l’ipotesiattuale. Se l’oracolo risponde NO, esso deve anche fornire un controesempioche discrimini il linguaggio accettato dall’automa ed il linguaggio regolare dainferire. Questo controesempio, insieme con tutti i suoi su!ssi, viene usatodall’algoritmo per congetturare una nuova ipotesi. Questa interazione tra ilsistema e l’oracolo continua finquando questo non risponde SI ad una do-manda di equivalenza. Questo algoritmo usa un tempo polinomiale rispettoalla dimensione del DFA canonico e rispetto alla lunghezza massima di unastringa fornita come controesempio; inoltre si puo dimostrare che l’algoritmoconverge correttamente verso l’automa minimo.

2.3.4 Approcci incrementali

Negli algoritmi ora studiati il problema dell’inferenza grammaticale regolarediventa trattabile se si assume che gli esempi labellati forniti al sistema sianostrutturalmente completi o siano un sample caratteristico o ancora se agliesempi labellati viene aggiunto un oracolo capace di rispondere a domanderiguardanti il linguaggio da inferire. Questo accade poiche in questi casi epossibile inferire in tempo polinomiale il piu piccolo DFA compatibile conun insieme finito di esempi labellati: disponendo di questa procedura si puocostruire una macchina inferenziale induttiva che identifica al limite il lin-


guaggio regolare in maniera e!ciente. Ma gli algoritmi fino ad ora studiati sipossono, con opportune modifiche, applicare direttamente al problema dell’i-dentificazione al limite, saltando il passaggio intermedio dell’identificazioneda given–data. In questo caso gli algoritmi terranno conto del fatto che i datisono parziali, quindi anche se temporaneamente non soddisfano le condizioniche ne garantiscono la correttezza, un incremento futuro degli esempi potreb-be far raggiungere queste condizioni. Parekh ed altri [MH98] hanno propostoun e!ciente algoritmo incrementale per identificare al limite un linguaggioregolare mediante l’uso di un oracolo. Il loro metodo estende l’algoritmoL! di Angluin in un contesto incrementale. All’algoritmo vengono fornitigli esempi labellati in maniera intermittente, inoltre l’algoritmo puo porreall’oracolo domande sull’appartenenza di una stringa al linguaggio regola-re. Come nel caso dell’algoritmo L!, le stringhe sono usate per individuaregli stati. Viene chiesto all’oracolo se le stringhe che identificano gli stati, equelle che si ottengono aggiungendo un singolo carattere, appartengono allinguaggio. Viene quindi costruito un insieme di stringhe su!sso su!cienteper distinguere gli stati. L’ipotesi attuale e compatibile con gli esempi finoa quel punto presentati: se la sorgente fornisce un esempio labellato inconsi-stente con l’ipotesi attuale, l’ipotesi viene modificata fino ad arrivare ad unDFA di nuovo compatibile con gli esempi. L’algoritmo converge verso il DFAcanonico quando l’informazione giunta all’algoritmo induttivo attraverso gliesempi labellati e le domande all’oracolo sono su!cienti a discriminare gli sta-ti e le loro transizioni. Questo algoritmo ha una complessita, sia spaziale chetemporale, polinomiale rispetto alla somma delle lunghezze dei controesempiosservati dal sistema.

Una versione incrementale dell’algoritmo RPNI e stata proposta da Du-pont [MH96]. Questo algoritmo converge verso il minimo DFA quando gliesempi labellati presentati fino a quel punto contengono un insieme caratte-ristico del linguaggio. La complessita temporale e polinomiale rispetto allasomma delle lunghezze degli esempi osservati. Comunque l’algoritmo richie-de la memorizzazione di tutti gli esempi visti dal sistema, per garantire chele varie ipotesi siano sempre compatibili con tutti gli esempi labellati.

2.3.5 Metodi numerici

I metodi trattati precedentemente sono tutti metodi simbolici: le trasforma-zioni dell’informazione non sono processi numerici. Un importante metododi calcolo che fa invece uso di procedure puramente numeriche per l’organiz-zazione e per la trasformazione dell’informazione sono le reti neurali. Le retineurali artificiali sono un modello computazionale che si ispira alla costituzio-ne dell’apparato cerebrale dell’uomo. Le reti neurali sono delle reti di unita

2.4 PAC-learning ed inferenza regolare 57

di calcolo elementare interconesse da pesi variabili. Ogni unita di calcolo,detta neurone, calcola una funzione elementare dei suoi ingressi. Le connes-sioni trasmettono i segnali tra i vari neuroni: ogni connessione ha un pesoche decide il modo in cui il segnale viene amplificato durante la sua trasmis-sione. Le reti neurali sono solitamente rappresentate per mezzo di un grafo.I nodi del grafo corrispondono ai neuroni, gli archi indicano le connessioni, enumeri sugli archi indicano il peso della connessione. Ogni neurone esegue ilsuo calcolo localmente sui segnali ricevuti dai neuroni a cui e connesso: ognicomputazione e indipendente rispetto alle altre. Questo fa in modo che lereti neurali siano un algoritmo parallelo, ma eseguibile anche su macchinenon parallele. Le reti usate nell’inferenza grammaticale regolare sono le retineurali ricorrenti : queste sono reti che hanno delle connessioni di feedbackche collegano i neuroni di output con i neuroni di input, e che consentonoalla rete di analizzare sequenze temporali di qualsiasi lunghezza come input[Par98]. Le reti neurali hanno ricevuto una certa attenzione nei problemidi apprendimento di un linguaggio: i vantaggi di questa tecnica rispetto aimetodi simbolici sono la possibilita di eseguire l’inferenza anche in presenzadi rumore, e la capacita di indurre un linguaggio anche con un piccolo insie-me di esempi. Rimangono comunque dei grossi problemi sull’instabilita dellereti, cioe della di!colta di decidere stringhe di lunghezza molto superiore aquella media degli esempi.

2.4 PAC-learning ed inferenza regolare

Gli algoritmi presentati fino ad ora evidenziano un limite che gia teoricamenteera stato previsto dal teorema 2.22 di Gold: non e sempre possibile costruireuna procedura e!ciente che fornisca il piu piccolo DFA consistente con uninsieme di esempi labellati. Di conseguenza non e possibile costruire una pro-cedura che, similmente alla procedura nell’esempio dei polinomi, identifichial limite un linguaggio regolare in maniera e!ciente. Solo l’aggiunta di infor-mazioni addizionali, come un oracolo, o la certezza che all’insieme di esempiappartenga un insieme caratteristico del linguaggio, permette ad alcuni al-goritmi di rendere il processo e!ciente. D’altra parte gli algoritmi euristici,che permettono di accelerare molto la ricerca, non garantiscono sempre diarrivare ad una soluzione. Un altro limite importante che si incontra nel-l’inferenza grammaticale regolare deriva dal teorema 2.14: non e possibileidentificare al limite la classe dei linguaggi regolari attraverso una presenta-zione positiva. Quest’ultimo limite e particolarmente significativo per queicasi pratici di indagine in cui si hanno a disposizione solo esempi positivi diun linguaggio formale. Per tutta questa serie di motivi, negli ultimi anni si e


visto un interesse sempre crescente verso metodi riferiti a criteri di successodiversi di quello al limite, che si basano su una identificazione approssimatadel linguaggio. Uno dei modelli maggiormente usati e il modello formalizzatoda Valiant [Val84], che va sotto il nome di Probably Approximately Correctlearning. Quando e adattato all’inferenza grammaticale regolare lo scopo diun algoritmo per il PAC–learning e ottenere da un insieme casuale di esempi,in tempo polinomiale, con alta probabilita, un DFA che accetti una buona ap-prossimazione del linguaggio da inferire [Pit89]. Una buona approssimazionedel linguaggio e una soluzione per la quale la probabilita di errore sulle strin-ghe che non fanno parte degli esempi e minore di uno specifico parametro diaccuratezza !. Poiche gli esempi sono scelti casualmente, e potrebbero nonessere pienamente rappresentativi del linguaggio regolare, si richiede all’al-goritmo di produrre una buona approssimazione del linguaggio solo con altaprobabilita, cioe con una probabilita maggiore di 1 % " con " parametro diconfidenza. Richiedere inoltre che l’algoritmo sia polinomiale vuol dire richie-dere che l’algoritmo sia polinomiale rispetto al numero degli stati dell’automaminimo, rispetto a 1

! , rispetto a 1" , rispetto alla cardinalita dell’alfabeto # su

cui e costruito il linguaggio, ed infine rispetto alla lunghezza massima dellestringhe presentate come esempi. Formalmente %marginparDISEGNO?

Definizione 2.24. Un insieme di linguaggi regolari L costruiti sull’alfabeto# e PAC–identificabile se e solo se esiste un algoritmo A che con in in-gresso i parametri ! e ", per ogni numero naturale m, e per ogni distribuzionedi probabilita D definita sulle stringhe di #! di lunghezza al piu 7 m, se Aottiene degli esempi labellati di un linguaggio L # L generati in accordo alladistribuzione D, allora A produce un DFA M tale che con probabilita 1% ",la probabilita dell’insieme {# | # # L. L(M)} rispetto alla distribuzioneD e al piu !. Il tempo di calcolo usato da A, e quindi anche il numero de-gli esempi usati da A, deve essere polinomiale rispetto al numero degli statidell’automa canonico che accetta L, rispetto a m, rispetto a 1

! , rispetto a 1" ,

ed infine rispetto a |#|.

L’algoritmo L! puo essere adattato al criterio di PAC–learning, e si puodimostrare che i linguaggi regolari sono e!cientemente PAC–identificabili sesi permette all’algoritmo di porre ad un oracolo un numero polinomiale di do-mande sull’appartenenza di stringhe al linguaggio [Ang87]. Comunque anchela PAC–identificabilita dei linguaggi regolari e un problema NP–hard, cioenon esiste un algoritmo e!ciente PAC–identifica l’intera classe dei linguag-gi regolari usando solamente l’insieme di esempi labellati [PW88]. Questo

7La probabilita di generare una stringa di lunghezza maggiore di m deve essere minoredi !


risultato dipende dall’estrema di!colta della condizione di apprendimentorispetto a qualsiasi distribuzione di probabilita definibile su #!.

2.4.1 Complessita di Kolmogorov

Pitt [Pit89] formalizza il seguente problema aperto: La classe dei linguag-gi regolari e PAC–identificabile se gli esempi sono forniti rispetto ad unadistribuzione uniforme, o se sono forniti rispetto a qualche altra semplicedistribuzione di probabilita?.

Non sembra inconcepibile assumere che in un problema di apprendimentopratico al sistema che apprende vengano forniti esempi semplici e rappresen-tativi del concetto da apprendere. Intuitivamente, quando si insegnano adun bambino le regole della moltiplicazione, prima gli si forniscono esempisemplici come 3 4 4 piuttosto che esempi come 1377 4 428. Un insieme diesempi rappresentativo puo permettere al sistema di identificare il concet-to esattamente. L’insieme caratteristico (vedi pagina 53) di un linguaggioregolare potrebbe costituire un valido insieme rappresentativo nell’inferenzagrammaticale regolare. Il nocciolo della questione e in che condizione si puospecificare esattamente che cosa significa veramente un esempio semplice.

La complessita di Kolmogorov K fornisce una definizione per la sem-plicita di un oggetto sostanzialmente indipendente dal sistema scelto perdescrivere l’oggetto. Intuitivamente la complessita di Kolmogorov di un og-getto, rappresentato da una stringa binaria x, e la lunghezza del piu piccoloprogramma binario che calcola x. Oggetti che un’alta regolarita nella lorostruttura, quindi oggetti che possono essere e!cacemente compressi, hannouna bassa complessita di Kolmogorov. Consideriamo ad esempio la stringasi = 010101 . . . 01 = (01)500. Un programma breve che calcola questa stringapotrebbe essere

Print 01 500 volte.

D’altraparte si consideri una stringa totalmente casuale sj = 1100111010000 . . .01composta da cinquecento caratteri. Questa stringa non puo essere compressa,il che significa che un programma breve che calcola sj potrebbe essere

Print 1100111010000 . . .01

cioe l’intera stringa deve essere specificata nel programma. La lunghezza delprogramma che calcola si e piu piccola del programma che calcola sj , quindiK(si) & K(sj).

Un calcolatore puo essere visto come una funzione parziale ricorsiva (vediappendice A) che prende come argomento una stringa e da come risultatodel calcolo un’altra stringa, oppure non valuta. Fissato un alfabeto #


Definizione 2.25. Un calcolatore e una funzione parziale ricorsiva ( : #! + #!.

L’argomento del calcolatore ( e il programma fornito in ingresso: stiamoconsiderando un calcolatore che esegue un programma senza utilizzare dati 8.Il valore di ((x) e quindi l’uscita fornita dal calcolatore dopo aver eseguito ilprogramma x.

Definizione 2.26. Un calcolatore $ si dice universale se per ogni cal-colatore ( esiste una costante c!% per cui: se ((x) 0 allora -x tale che$(x) = ((x) e l(x) & l(x) + c.

Si puo simostrare l’esistenza di un calcolatore universale. Usano le defi-nizioni date si puo formalmente definire la complessita di una stringa.

Definizione 2.27. La complessita di Kolmogorov associata al calcola-tore ( e la funzione parziale K% : #! + N cosı definita

K%(x) = min{l(u) : u # #!,((u) = x}

Nel caso in cui ( e un calcolatore universale $ si scrivera K(x) = K!(x).

La definizione appena data di complessita esibisce due importanti pro-prieta dimostrabili

• Per ogni coppia di calcolatori universali $ e % esiste una costante ctale che, per tutte le stringhe x in #!, si ha

|K!(x)%K"(x)| & c

• Esiste una costante c tale che per ogni stringa x appartenente a #!

K(x) & l(x) + c

La prima proprieta garantisce che la complessita di una stringa x non di-pende, a meno di una costante indipendente da x, dalla macchina universalescelta per eseguire i programmi. La seconda proprieta assicura che la com-plessita di un oggetto non puo superare la taglia dell’oggetto stesso a menodi una costante.

La distribuzione universale di Solomono!–Levin m(x) 5 2"K(x) usa que-sta definizione di complessita per assegnare probabilita piu alta alle strin-ghe che sono piu semplici. Se si accetta la complessita di Kolmogorov co-me una buona nozione su cui definire la semplicita di un oggetto allora ladistribuzione universale definisce un modo per generare esempi semplici.

8Usando il teorema s–m–n della teoria della calcolabilita si puo dimostrare che questopresupposto non fa perdere generalita al discorso.


Li e Vitanyi [LV91] hanno studiato il PAC–learning usando la distribu-zione universale, chiamando questo modello simple PAC–learning, ed hannodimostrato che alcune particolari sottoclassi di DFA sono PAC–identificabilisotto questo modello, mentre non si conosce la loro PAC–identificabilita peruna distribuzione generica. Parekh e Honavar [Par98] hanno risposto par-zialmente al quesito di Pitt dimostrando che la classe dei linguaggi regolarisemplici (il cui DFA canonico ha una bassa complessita di Kolmogorov), sonoe!cientemente simple PAC–identificabili. Il loro approccio si basa sul fattoche per ogni linguaggio regolare di questo tipo esiste un insieme caratteristi-co, nel senso formale, composto da esempi semplici. Essi dimostrano che conun’alta probabilita questi esempi semplici saranno tutti forniti al sistema sesi usa la distribuzione universale. Di conseguenza, usando l’algoritmo RP-NI sugli esempi cosı scelti si puo dimostrare la PAC–identificabilita. Infinein un recentissimo lavoro [Den] si dimostra un importante risultato: ancheusando solo esempi positivi si ottiene la simple PAC–identificabilita di unasottoclasse di linguaggi regolari semplici.

L’apprendimento attraverso esempi semplici e un nuovo interessante mo-dello, che sicuramente influenzera in futuro anche gli studi nel campo del-l’apprendimento del linguaggio naturale.

Capitolo 3

Algoritmi Evolutivi

Gli algoritmi evolutivi sono un modello computazionale che si basa sullateoria dell’evoluzione naturale. Il principio fondamentale e far variare gli ele-menti di un insieme, che codificano delle potenziali soluzioni di un problema,attraverso dei processi corrispettivi alla selezione naturale e alla riproduzinedegli esseri viventi. In natura un ambiente e favorevole per un individuo, sel’individuo ha una alta probabilita di riprodursi vivendo in quell’ambiente.Negli algoritmi evolutivi il problema da risolvere gioca il ruolo di ambientecon cui gli elementi dell’insieme interagiscono: l’elemento e tanto piu adattoall’ambiente quanto e migliore soluzione per il problema. Il giudizio del-l’ambiente sul singolo elemento viene generalmente espresso da un numero,chiamato fitness; piu grande e il numero migliore e il giudizio dell’ambientesull’elemento. La selezione stringe l’attenzione sugli elementi con piu alta fit-ness: in questo modo l’evoluzione viene guidata indirettamente dall’ambienteverso la produzione di individui migliori. Gli operatori di ricombinazione emutazione modificano gli individui, e forniscono quindi un’euristica generaleper la creazione di nuovi individui. Nella pratica gli algoritmi evolutivi ven-gono usati per risolvere problemi di ottimizzazione con dipendenze funzionalicomplesse e numerose, intrattabili analiticamente: il problema viene codifi-cato nell’ambiente, ogni elemento della popolazione rappresenta una possi-bile soluzione, la fitness e quanto la singola struttura codifica una soluzioneottimale per il problema.

Anche se semplicistici da un punto di vista biologico, questi algoritmi sonoabbastanza potenti da fornire un metodo di ricerca robusto ed e!ciente.

63

64 Algoritmi Evolutivi

3.1 Terminologia

Tutti gli organismi viventi sono formati da cellule, ed ogni cellula somati-ca dell’individuo contiene lo stesso insieme di cromosomi, cioe stringhe diDNA che sono talvolta considerate il progetto dell’organismo. Un cromoso-ma puo essere concettualmente diviso in geni, cioe in blocchi funzionali diDNA, ognuno dei quali contribuisce alla sintesi di una certa proteina. Mol-to schematicamente si puo pensare al singolo gene come alla codifica di unsingolo carattere dell’individuo, come ad esempio il colore degli occhi. Il pos-sibile valore che la caratteristica dell’individuo puo assumere, come azzurro,marrone e verde per il colore degli occhi, sono chiamati allele. Ogni gene elocalizzato in un particolare punto del cromosoma: questo punto viene dettolocus. Organismi di specie diverse hanno un diverso numero di cromosomi.La raccolta completa del materiale genetico, cioe l’insieme di tutti i cromo-somi di una cellula dell’organismo, e chiamata genoma dell’organismo. Iltermine genotipo indica una determinata combinazione degli alleli in un ge-noma. Il genotipo codifica nel suo insieme il fenotipo dell’organismo, cioel’insieme delle sue caratteristiche fisiche: il colore degli occhi, l’altezza, ladimensione del cervello sono elementi del fenotipo. Gli oganismi in cui i cro-mosomi sono ordinati in coppie sono chiamati diploidi ; gli organismi in cuiquesto non accade, e c’e una singola copia di ciasun cromosoma, sono dettiaploidi. In natura, la maggior parte delle specie che usano la riproduzio-ne sessuata sono diploidi. Anche l’uomo e una specie diploide: ogni cellulasomatica del corpo umano possiede 23 coppie di cromosomi mentre ogni cel-lula germinale possiede solo 23 cromosomi singoli. Durante la riproduzionesessuata avviene il crossing–over : in ogni genitore avviene uno scambio digeni per ogni coppia di cromosomi per formare un singolo cromosoma di unacellula germinale, detta gamete; dopodiche i gameti di entrambi i genitorisono accoppiati, nella fase di fecondazione, per formare un insieme completodi cromosomi diploidi. I nuovi organismi prodotti nella riproduzione sonoanche soggetti alla mutazione, un fenomeno nel quale singoli geni vengonoalterati. Le mutazioni sono fondamentalmente dovute a degli errori di copiache avvengono nel processo riproduttivo.

Nella riproduzione asessuata un organismo possiede un solo genitore e nonsi ha crossing–over, quindi il suo genotipo e identico a quello dell’organismoche lo ha generato, a meno di di"erenze provocate unicamente dall’operatoredi mutazione. La fitness di un organismo si definisce generalmente come lapropabilita che ha l’individuo di vivere abbastanza per riprodursi, o comeuna funzione del numero di discendenti che l’organismo produce. L’ambientenaturale permette solo agli individui migliori di riprodursi e trasmettere il lo-ro genotipo alle generazioni successive. Il genotipo degli individui con fitness

3.2 Storia 65

piu alta si di"ondera di piu rispetto agli altri, realizzando una popolazioneadattata all’ambiente circostante.

3.2 Storia

Negli algoritmi evolutivi sono possibili molte variazioni; queste riguardano iltipo di codifica per rappresentare gli individui nella popolazione, gli operato-ri da usare durante l’evoluzione, il meccanismo di selezione e molto ancora.Tradizionalmente i ricercatori di questo campo si sono uniti in vere e propriecomunita, col fine di concentrare gli studi su determinate scelte per i fattoricaratterizzanti l’algoritmo evolutivo. In e"etti nel termine algoritmi evolu-tivi, si possono far rientrare diversi filoni di studi quasi indipendenti tra diloro.

La programmazione evolutiva (PE) [FOW66], tradizionalmente usa dellecodifiche che sono pensate specificamente per il problema analizzato. Adesempio in un problema che riguarda l’ottimizzazione di variabili reali, gliindividui della popolazione saranno vettori di variabili reali. Similmente, inun problema come quello del commesso viaggiatore la popolazione puo esserecostituita da liste legate, o in un problema riguardante automi, la popolazio-ne puo essere costituita da grafi. In generale in programmazione evolutivasi usa quasi unicamente l’operatore di mutazione. Le modalita di azionedell’operatore di mutazione dipendono dalla rappresentazione; spesso accadeche la mutazione sia definita come adattiva, cioe la probabilita e la moda-lita di azione dell’ operatore cambiano durante l’evoluzione. Per esempio,usando una codifica che rappresenta un elemento come un vettore di reali,la mutazione puo avere una probabilita variabile su ogni posizione del vetto-re. Generalmente non vengono usati operatori di ricombinazione (altro nomedel crossing–over), poiche l’operatore di mutazione e scelto adeguatamentepotente per poter garantire una certa diversita nella popolazione.

Le strategie di evoluzione (SE) sono una variante di algoritmo evoluti-vo sviluppata indipendentemente da Rechenberg [Rec73]: nella formulazioneoriginale si operava attraverso gli operatori di selezione e mutazione su unapopolazione costituita da un solo elemento. Successivamente e stato intro-dotto l’uso dell’operatore di ricombinazione insieme all’uso di popolazioni dicardinalita piu grande. Le strategie evolutive nascono internamente agli studidi fluidodinamica: infatti tradizionalmente la codifica usata rappresenta glielementi della popolazione come vettori di numeri reali. Come nella program-mazione evolutiva anche nelle SE la mutazione e solitamente di tipo adattivo,ma diversamente dalla PE in questo caso l’operatore di ricombinazione giocaun ruolo centrale.


Gli algoritmi genetici (GA) [Hol75] tradizionalmente usano una codidficache e indipendente dal dominio di applicazione. Infatti generalmente glielementi della popolazione sono semplicemente stringhe di 0 e 1. E in questascelta che si racchiude la particolarita e la potenza degli algoritmi genetici.L’ambizione degli studiosi di questo campo e di formalizzare un modellodi calcolo che permetta di risolvere in maniera e!ciente qualsiasi problemariducibile ad un problema di ricerca. Nonostante queste intenzioni, anchein questo caso sono state provati altri tipi di codifica, ad esempio una dellevariazioni piu discusse riguarda la scelta di usare alfabeti non binari percostruire le stringhe. E importante notare che l’importanza relativa deglioperatori di ricombinazione e mutazione e negli AG opposta rispetto a quelladatagli nella PE. In un algoritmo genetico la mutazione inverte il valore di unsingolo bit agendo con una probabilita molto bassa, ed e spesso consideratocome una sorta di operatore in background. Il crossing-over, viceversa, vieneconsiderato come l’operatore di ricerca piu importante.

Infine una recente branca che deriva dagli AG e che ha conquistato unacerta autonomia e quella della programmazione genetica (PG). Nella pro-grammazione genetica gli elementi della popolazione sono sempre s–espressionilisp, rappresentate sotto forma di alberi. L’operatore principale in questavariante e certamente il crossing–over, tanto che nel lavoro fondazionale diKoza [Koz92] non vengono usati altri operatori.

3.3 Gli algoritmi genetici

Gli algoritmi genetici sono indubbiamente la tecnica evolutiva che ha suscita-to maggiore attenzione negli ultimi venti anni. Gli studi partoriti da questointeresse hanno portato all’applicazione degli AG a svariati campi, con deirisultati positivi a volte sorprendenti. La proprieta che caratterizza gli AGrispetto alle altre tecniche evolutive e la loro generalita, che deriva dalla scel-ta di una codifica universale indipendente dal problema a cui gli AG sonoapplicati. Gli elementi della popolazione sono stringhe di caratter costruitesu alfabeti usualmente binari. Inoltre tutte le stringhe che costituiscono lapopolazione hanno la stessa lunghezza.

Questa scelta estrema proviene dalle motivazioni che hanno portato allanascita degli AG [Hol75], ovvero dall’intenzione di Holland di formalizzarelo studio dei fenomeni di evoluzione cosı come avvengono in natura, ma inmaniera che gli stessi fenomeni potessero essere riprodotti sotto forma di pro-grammi per calcolatori. Si puo costruire una tabella (vedi tabella 3.1) cheriassume le corripondenze tra i termini biologici e i termini usati nella descri-zione di un AG. Bisogna pero notare che nella stragrande maggioranza dei

3.3 Gli algoritmi genetici 67

Biologico Algoritmi Genetici

cromosoma stringagene singolo carattereallele valore del caratterelocus posizione nella stringagenotipo struttura=insieme di stringhefenotipo decodifica della struttura

Tabella 3.1:

casi la struttura e costituita da un’unica stringa, cioe il genotipo e costituitoda un unico cromosoma.

Un AG e fondamentalmente un algoritmo per risolvere problemi di ricercache si basa sulla ripetizione di un ciclo principale. In un AG le stringhebinarie che formano la popolazione codificano delle soluzioni approssimate delproblema di ricerca: il fenotipo di ogni genotipo presente nella popolazionee una possibile soluzione. Ad ogni ciclo dell’algoritmo vengono scelte dellestringhe appartenenti alla popolazione casualmente, in base alla fitness, percreare attraverso l’operatore di ricombinazione una nuova popolazione. Lafitness e una funzione a valori reali, che ha dominio sullo spazio di tutti igenotipi, e restituisce un numero che esprime quanto i fenotipi corrispondentisono soluzioni ottimali. I criteri per decidere la terminazione del ciclo possonoessere diversi, ma solitamente se nella popolazione viene trovato un elementocon una fitness tale da soddisfare le richieste del problema, il ciclo si ferma el’elemento viene restituito come soluzione.

Gli operatori di crossing–over e mutazione standard, cioe come descrittida Holland, possono essere descritti semplicemente

• Presi due elementi nella popolazione, che fungeranno da genitori, ilcrossing–over sceglie un punto a caso all’interno della stringa. I genidel secondo genitore seguenti al punto selezionato, vengono concatenatiai geni del primo genitore precedenti al punto. In tal modo si produceun nuovo elemento di lunghezza uguale ai primi due, che possiede unpatrimonio genetico misto tra i due genitori (vedi fig. 3.1-a).

• L’operatore di mutazione agisce su un singolo elemento: scorre l’in-sieme di tutti i geni dell’elemento e casualmente, con una probabi-lita relativamente bassa, puo variare il valore di un singolo locus (vedifig. 3.1-b).

Durante la generazione di una nuova popolazione vengono di volta in volta


1 0 0 0 1 0 1 11 1 0 1

0 0 0 1 0 1 0 0 1 1 0 11 1 0 1

1 0 1 0 0 0 1 1 1 10 0 1 1 0 1 0 0 0 1 1 10 0 10

0 1 0 0 1 1 0 1

b) Mutazione

genitorifiglio

a) Crossing-over

Figura 3.1: Esempi di crossing–over e mutazione

selezionati quegli individui che, attraverso la riproduzione, daranno luogo agliindividui della nuova popolazione. La procedura che sceglie quali elementidella popolazione saranno passati agli operatori genetici assume un ruolocentrale, e spesso viene trattata come un operatore genetico a se stante (siparla allora di operatore di selezione). Il meccanismo di selezione dei genitorie casuale, ma non uniforme, in quanto e tale che abbiano maggiore probabilitadi essere selezionati quegli individui con una fitness migliore rispetto a quellicon fitness peggiore. In tal modo si simula il processo di selezione naturale el’evoluzione viene guidata verso la soluzione cercata. Le tecniche di selezionesono varie ed ognuna risulta piu adatta alla risoluzione di un certo problema.Data una funzione di fitness

f : Al + R+

e una popolazione costituita dagli N individui x1 . . . xN , descriviamo alcunefra le piu utilizzate tecniche di selezione:

• selezione proporzionale: in tale meccanismo le probabilita di repli-cazione degli individui nella popolazione P , di ' individui, sono datedalla loro fitness normalizzata sulla somma della fitness di tutti gli in-dividui. Pertanto, avremo una distribuzione di probabilita data dallaseguente funzione:


S : xi # P %+ ps(xi) =f(xi)!&

j=1 f(xj)# [0, 1]

• truncation: tale meccanismo consiste nella selezione, ad ogni genera-zione, dei µ migliori individui nella popolazione. Tali individui sono poilasciati liberi di ricombinarsi casualmente (cioe con probabilita unifor-memente distribuita) in modo da generare ' discendenti. In tal modogli individui selezionati sono trattati come ‘super–individui’.

La distribuzione di probabilita per tale meccanismo si selezione e datada:

S : xi # P %+ ps(xi) =

"$

%

1µ 1 & i & µ

0 µ < i & '

• tournament: la tournament consiste nella selezione casuale, ' volte,di µ individui nella popolazione e nella copia del miglior individuo traquesti in una popolazione intermedia. Tali individui sono poi lasciatiliberi di ricombinarsi casualmente in modo da generare ' discendenti.

Se gli individui nella popolazione sono ordinati da quelli con fitnessmigliore a quello con fitness peggiore, la distribuzione di probabilitaper questo meccanismo di selezione e data da:

S : xi # P %+ ps(xi) = '"µ/('% i + 1)µ % ('% i)µ

0

Inoltre una selezione viene detta k–elitista se e tale che i migliori kindividui di una popolazione vengono copiati identici nella popolazione suc-cessiva.

Dopo un certo numero di generazioni probabilmente si avra che la mag-gior parte della popolazione e costituita da individui estremamente simili, senon addirittura identici: e la cosı detta convergenza, dovuta al fatto chel’AG spinge la popolazione verso un sottospazio, nello spazio delle soluzio-ni, sempre piu limitato. La popolazione potrebbe pero convergere verso unelemento che non e quello ottimale, in quanto si potrebbe bloccare su unottimo locale. In questo caso si parla di convergenza precoce. La ricer-ca di metodi per evitare convergenze non appropriate e un campo di studio


molto attivo. Un meccanismo possibile, per la soluzione di questo problema,comporta uno sbilanciamento del processo di selezione verso il mantenimentodella diversita della popolazione. In sostanza, tali meccanismi incoraggianogli elementi ad occupare molte regioni diverse nello spazio delle soluzioni inmodo da consentire una molteplicita delle forme. Chiaramente l’uso di que-ste euristiche provocano in generale un rallentamento nel raggiungimento diuna soluzione ottimale. Ad esempio la truncation e una selezione che portaad una convergenza estremamente veloce, correndo pero il rischio di caderefacilmente in una regione in cui non e presente l’ottimo cercato, ma solo unsubottimo. La selezione proporzionale, invece, garantisce un certo manteni-mento della diversita nella popolazione, ma la convergenza diventa, in alcunicasi, estremamente lenta.

E importante notare che il modello algoritmico di evoluzione ora descrittoesegue una forte semplificazione rispetto al corrispettivo naturale: la fitnessdell’individuo si puo valutare analizzando unicamente il genotipo. In naturaquesto non e vero: un individuo puo influire sulla propria fitness “modifican-do” l’ambiente in cui vive. Negli algoritmi evolutivi si suppone invece che ilprocesso di epigenesi sia puramente deterministico e che l’ambiente non pos-sa essere modificato dagli elementi della popolazione: si puo quindi valutareun individuo guardandone solo il “progetto”. Un concetto collegato e quellodi fitness–landscape. Il fitness–landscape e una rappresentazione dello spaziodi tutti i possibili genotipi e della loro fitness. Si supponga che ogni geno-tipo sia formato da una stringa binaria di lunghezza l. Il fitness–landscapee un disegno (l + 1)–dimensionale nel quale ogni genotipo e un punto in ldimensioni, la cui fitness, come variabile reale, viene disegnata lungo l’assel + 1. Questi disegni sono chiamati landscape (paesaggi) perche il profilodella fitness puo disegnare delle “colline”, dei “picchi”, delle “vallate”, edaltre forme analoghe a quelle di un paesaggio naturale. L’evoluzione, comemodellizzata in un AG, provoca il movimento della popolazione sulla super-ficie del paesaggio: l’addattamento della popolazione all’ambiente puo esserevisto come la deriva verso i picchi vicini. L’idea che l’evoluzione sia solo unmovimento di elementi lungo un profilo di fitness costante e biologicamenteirrealistica.

Inoltre non si puo assegnare la fitness di un individuo indipendentementedagli altri individui presenti nell’ambiente. Al variare della popolazione lafitness di un particolare genotipo varia anch’essa: nel mondo reale non si puoquindi separare nettamente gli individui dalla loro fitness.


3.3.1 La teoria degli schemi

Holland [Hol75] ha formulato una teoria, detta teoria degli schemi, che mo-stra come agiscono gli AG sulle rispettive popolazioni e come, attraverso glioperatori di mutazione e crossing over, raggiungono la soluzione. Nello svi-luppo della teoria si seguira il [Gol89]. Consideriamo una popolazione di nstringhe binarie (la restrizione ad un alfabeto di soli due simboli non fa per-dere di generalita al discorso). Nella discussione le stringhe verranno indicatecon lettere maiuscole. Se la nostra popolazione e costituita da n individui,allora per ogni istante t avremo una popolazione A(t) costituita dalle strin-ghe Aj , j = 1 . . . n. Introduciamo ora il concetto di schema. Aggiungiamoai simboli del nostro alfabeto il simbolo 3. Ora avremo un alfabeto di tresimboli A& = {0, 1, 3} e ogni stringa di questo alfabeto e uno schema. Unpossibile schema e la stringa 0 3 31103. Uno schema rappresenta l’insiemedei possibili elementi che hanno 0 lı dove lo schema ha 0, 1 dove lo schemaha 1 e un simbolo qualsiasi dove lo schema ha il simbolo 3. Cosı allo sche-ma 0 3 31103 appartiene l’individuo 0111100, ma non l’individuo 0111000.Dato un alfabeto di k simboli, ci sono (k + 1)l schemi diversi di lunghezzal. L’ordine di una schema H , denotato con o(H), e il numero di posizionifissate presenti. Ad esempio o(011 3 1 3 3) = 4, mentre o(0 3 3 3 3 3 3) = 1. Lalunghezza di definizione di una schema H , denotata con "(H), e la distan-za tra il primo e l’ultimo simbolo definiti. Ad esempio "(011 3 1 3 3) = 4.L’introduzione dell’ordine di uno schema e della sua lunghezza di definizioneaiutano a comprendere cosa accade agli schemi durante l’evoluzione di unAG. Consideriamo per ora l’e"etto della riproduzione asessuata senza muta-zione sul numero aspettato di schemi nella popolazione. Supponiamo che adun dato istante t ci siano m esempi di un particolare schema H contenutonella popolazione A(t), scriveremo m = m(H, t). Scegliendo come selezionela selezione proporzionale, durante una riproduzione asessuata una stringaAi e copiata con probabilita pi = f(Ai)!

fi. Dopo che e stata e"ettuata la ripro-

duzione su tutta la popolazione ci aspettiamo che il numero di rappresentantidello schema H sia m(H, t + 1) =

!m(H,t)i=0 npi = m(H, t)nf(H)!

fi, dove n e il

numero di individui totali nella popolazione e f(H) e la fitness media dellestringhe che rappresentano lo schema H al tempo t. Ricordando che la fitnessmedia fm e fm =

!fi

n , possiamo riscrivere l’equazione come

m(H, t + 1) = m(H, t)f(H)

fm.

Quindi il numero di individui in una popolazione che rappresentano un certoschema cresce se la fitness media dello schema f(H) e maggiore della fitnessmedia dell’intera popolazione fm, altrimenti decresce. Inoltre, nel caso in cui


l’evoluzione sia guidata dalla sola riproduzione asessuata, la storia di ognischema H in una popolazione A e indipendente dagli altri schemi, quindi siha una sorta di parallelismo nell’evoluzione degli schemi.

Vediamo ora come l’operatore di crossing–over influenza il numero dirappresentanti di uno schema nella popolazione. Per vedere quali schemisono interessati dall’operatore di crossing–over e quali no, consideriamo unastringa di lunghezza l = 7 e due schemi che abbiano come istanza la stringaA:

A = 0 1 1 1 0 0 0

H1 = 3 1 3 3 3 3 0

H2 = 3 3 3 1 0 3 3.

Supponiamo che la stringa A sia stata selezionata per eseguire un crossing–over e che il punto in cui viene tagliata sia tra il terzo e il quarto carattere.L’e"etto dell’applicazione del crossing–over sulla stringa A sui due schemiH1 e H2 si puo vedere facilmente nell’esempio seguente, in cui il punto dicrossing-over e stato evidenziato con il simbolo | :

A = 0 1 1| 1 0 0 0

H1 = 3 1 3 | 3 3 3 0

H2 = 3 3 3| 1 0 3 3.

A meno che, dopo il crossing–over, non si formi una nuova stringa che siaidentica ad A nelle posizioni fissate dello schema H1 (eventualita con unaprobabilita abbastanza bassa), lo schema H1 verra distrutto, nel senso che lastringa ottenuta non sara piu un’istanza di H1. Invece lo schema H2 soprav-vivera, in quanto il punto di crossing–over non cade fra due posizioni fissatedi tale schema, cioe la stringa ottenuta come figlio sara ancora un’istanzadello schema H1. Quindi, in generale, lo schema H2 ha maggiori probabilitadi “sopravvivere” dello schema H1, in quanto e molto piu improbabile che ilpunto di crossing–over vada a cadere tra due posizioni fissate nello schema.La lunghezza di definizione " di uno schema e determinante per quanto ri-guarda la probabilita di sopravvivere dello schema stesso dopo l’applicazionedel crossing–over.

In generale, puo essere trovato un limite inferiore alla probabilita di so-pravvivere ps di uno schema. Poiche uno schema sopravvive quando il puntodi crossing–over cade al di fuori della lunghezza di definizione, la probabilita


di sopravvivere dopo aver applicato una volta il crossing–over ad uno schemadi lunghezza l e ps = 1 % "(H)

l"1 , dato che uno schema puo essere distruttoquando il punto di crossing–over, fra l % 1 punti possibili, cade all’internodella lunghezza di definizione. Se il crossing–over puo essere applicato conprobabilita pc, la probabilita di sopravvivenza di uno schema puo essere datadall’espressione

ps ) 1% pc"(H)

l % 1.

Se ora andiamo a calcolare il numero di esempi di un particolare sche-ma H contenuto nella popolazione A(t) dopo l’applicazione di riproduzioneasessuata e crossing-over agli individui di A, otteniamo che

m(H, t + 1) ) m(H, t)f(H)

fm

11% pc

"(H)

l % 1

2.

Confrontando questa espressione con quella ottenuta nel caso in cui operavala sola riproduzione asessuata, si nota che il numero aspettato di istanze di uncerto schema H e dato dal prodotto di quello aspettato per sola riproduzioneasessuata e quello per solo crossing–over. Quindi, nel caso dell’azione com-binata di riproduzione asessuata e crossing–over, il fattore dipende da dueparametri: se la fitness media dello schema e maggiore o minore di quella me-dia e se la lunghezza di definizione dello schema e grande o piccola. Avrannomaggiore rappresentanza nella popolazione quegli schemi che hanno un’altovalore di fitness media e una piccola lunghezza di definizione.

Infine studiamo l’influenza dell’ultimo operatore rimasto nella di"usionedegli schemi: la mutazione. Se pm e la probabilita che un carattere di unastringa, ossia un allele, venga cambiato per mutazione, (1 % pm) e la pro-babilita che un allele sopravviva ad una mutazione. Uno schema sopravviveall’applicazione dell’operatore di mutazione se ognuna delle o(H) posizionifissate nello schema sopravvive. Moltiplicando la probabilita (1 % pm) perse stessa o(H) volte, otteniamo la probabilita di sopravvivere alla mutazione(1%pm)o(H). Per piccoli valori di pm (pm 6 1), la probabilita di sopravvivenzadi uno schema puo essere approssimata dall’espressione 1% o(H)pm.

Possiamo allora concludere che un particolare schema ha un numero atte-so di istanze nella prossima generazione dopo l’applicazione di riproduzioneasessuata, crossing–over e mutazione, pari a

m(H, t + 1) ) m(H, t)f(H)

fm

11% pc

"(H)

l % 1% o(H)pm

2. (3.1)

Quindi possiamo concludere che gli schemi con maggiore probabilita di so-pravvivere sono quelli con una fitness media alta, con distanza di definizionepiccola e ordine basso.


La conclusione tratta dall’equazione 3.1 e molto importante e viene soli-tamente indicata come Teorema degli schemi o Teorema fondamentale degliAlgoritmi Genetici.

Chiamiamo gli schemi caratterizzati da piccola distanza di definizione eordine basso building blocks. Il teorema fondamentale degli Algoritmi Geneti-ci a"erma che gli schemi che hanno maggiore probabilita di sopravvivere finoalla fine del ciclo evolutivo (quindi quelli che avranno come rappresentante lasoluzione del problema che si sta risolvendo) sono i building blocks. Quindi segli individui della popolazione vengono codificati in modo da non favorire lacreazione dei bulding blocks, l’AG potrebbe richiedere tempi estremamentelunghi per convergere alla soluzione cercata.

3.3.2 Progettare un algoritmo genetico

Non esiste una teoria generale che assicura la superiorita di un AG rispetto adaltri metodi di ricerca nello studio di un particolare problema, esistono perodei fattori che devono essere considerati nello scegliere e poi nel progettareun AG.

Vi sono delle situazioni in cui gli AG sono certamente inferiori ad altrimetodi di ricerca classici

• Se lo spazio di ricerca e “piccolo” si puo procedere con una ricerca esau-stiva su tutto lo spazio. In questo modo si e certi di trovare la soluzionemigliore, che corrisponde al picco piu alto del landscape; usando unAG c’e sempre la possibilita di una convergenza precoce verso massimilocali.

• Se lo spazio di ricerca corrisponde ad un landscape molto regolare, adesempio la derivata della fitness e una funzione continua con un solomassimo, quindi metodi di ricerca che sfruttano queste caratteristichecome l’hill–climbing, producono risultati certamente piu veloci e sicuri.

• Se si conoscono a fondo le caratteristiche dello spazio di ricerca, allorale prestazioni di metodi progettati specificamente per il problema instudio sono certamente superiori alle prestazioni di un AG.

L’uso di un AG e certamente opportuno in problemi in cui lo spazio di ri-cerca, e quindi il landscape, non e ben conosciuto, oppure in quei casi in cuie su!ciente trovare una soluzione parziale ma in tempi brevi. Inoltre neiproblemi in cui la valutazione della soluzione non e perfetta, e quindi la fit-ness e disturbata da una piccola percentuale di rumore, i metodi tradizionalisono impraticabili, mentre gli AG, grazie alla loro natura statistica, possonoessere e!cacemente usati.


Nel progettare un AG il fattore principale che influira piu di tutti sulleprestazioni del metodo e la scelta della codifica. La maggior parte degliAG hanno una codifica che rappresenta gli elementi della popolazione comestringhe di bit a lunghezza fissa. La codifica binaria e la codifica piu di"usasia per un motivo storico, sia per delle cosiderazioni teoriche formulate dallostesso Holland . Tutte le basi teoriche degli AG, il teorema degli schemiin primis, presuppongono la codifica binaria; nonostante questa teoria siarivedibile anche nel caso di alfabeti di cardinalita maggiore non c’e ancoraun’estensione di questi risultati per le altre codifiche.

Holland ha fornito una motivazione teorica che sembra dimostrare la su-periorita della codifica binaria. Se si confronta una stringa binaria di lun-ghezza 100 con una stringa decimale di lunghezza 30, che ha quindi la stessacapacita di informazione (2100 5 1030), ci si accorge che la stringa binariacontiene un numero di schemi (2100) maggiore del numero di schemi contenu-ti nella stringa decimale (230). Questo sembra dimostrare un maggior gradodi parallelismo implicito posseduto dalla codifica binaria, e quindi una pro-vata superiorita rispetto ad altre codifiche. Questo ragionamento puo essereformalizzato attraverso due teoremi dovuti a Goldberg [Gol90]. Consideria-mo un AG che codifica una soluzione attraverso un alfabeto di cardinalitak. Poiche ci sono k + 1 schemi per posizione (i k simboli dell’alfabeto piu ilmetasimbolo 3 ), ed ogni simbolo si puo rappresentare attraverso log2 k bit,

ci sono (k + 1)1

log2 k schemi per bit di informazione in un codice di cardinalitak. Questo calcolo e la dimostrazione del

Teorema 3.1. Ci sono ns = (k + 1)1

log2 k schemi per bit di informazionenelle stringhe di un codice costruito su un alfabeto di cardinalita k.

Direttamente segue

Teorema 3.2. Per una fissata quantita di informazione, stringhe codificatesu alfabeti piu piccoli sono istanze di un maggior numero di schemi rispettoa stringhe codificate su alfabeti di cardinalita maggiore.

Dimostrazione. Dal teorema 3.1, ns = (k + 1)1

log2 k . Chiamiamo r il logaritmodi ns: r(k) = log2 ns = log2(k+1)

log2 k = ln(k+1)lnk . Valutando la derivata rispetto a k

si ottiene

dr

dk=

[k ln k % (k + 1) ln(k + 1)]

k(k + 1) ln2 k

Poiche k ln k e monotonamente crescente per ogni cardinalita valida (k ) 2),la derivata di r e minore di zero. Inoltre poiche l’esponenziale e una funzionemonotona crescente si e dimostrato che alfabeti piu piccoli hanno un maggiornumero di schemi per unita di informazione.


Goldberg fa un esempio pratico per chiarire il significato di questi teoremi.Supponiamo di codificare un problema, sia attraverso delle stringhe binarie,che attraverso delle stringhe costruite su un alfabeto ottale, e di ottenerei valori di fitness riassunti nella tabella 3.2. Osservando solo le stringhe

Binario Ottale Fitness000 0 22011 3 8101 5 11111 7 3

Tabella 3.2:

ottali e i valori di fitness corrispondenti, non e possibile congetturare alcunaipotesi riguardo alla fitness di stringhe non presenti nella tabella. D’altraparte ogni stringa binaria puo essere vista come rappresentante di diversiinsiemi di stringhe che ne condividono alcune caratteristiche. Si puo quindispeculare sulle possibili relazioni che collegano la forma della stringa con lapropria fitness. Ad esempio la prima stringa potrebbe avere cosı alta fitnessperche vi sono due zeri a!ancati sulla estrema destra, oppure le stringhe000 e 101 potrebbero essere relativamente buone a causa dello zero che sitrova al loro centro. In questa maniera si possono formulare diverse ipotesiche riguardano i valori delle sottostringhe e una buona fitness: sono questeinformazioni che vengono combinate tra di loro durante la ricerca geneticaper costruire strutture sempre migliori.

Queste considerazioni teoriche sono pero adombrate da diversi indizi spe-rimentali: confrontando i risultati ottenuti con la codifica binaria e i risultatiottenuti con codifiche a piu di due simboli, si e notato, in alcuni casi, una sor-prendente superiorita di quest’ultima rappresentazione. Ad esempio si puomostrare, empiricamente e teoricamente, che in alcuni casi alfabeti non bina-ri aumentano la velocita di convergenza verso la soluzione ottimale. Inoltrel’operatore di mutazione standard, usato su tali stringhe, puo avere un e"et-to piu “dolce”, permettendo di esplorare in maniera piu completa le regionidello spazio di ricerca.

Questi risultati dipendono molto dallo specifico problema a cui l’AG eapplicato, ma ugualmente spingono verso una revisione dei risultati teoriciderivanti dal teorema degli schemi [Ant89].

Un altra importante considerazione che influisce nella scelta della codificae il cosı detto linkage problem. Questo argomento evidenzia il fatto che lacodifica migliore e quella che dispone i loci funzionalmente correlati quanto


piu vicino e possibile, in maniera da rendere l’azione dell’operatore crossing–over piu e!cace per ottenere una soluzione ottimale in tempi brevi, come sievince dal teorema degli schemi. Se due variabili correlate sono posizionatevicine nel cromosoma, e meno probabile che l’operatore di crossing–over variuna sola delle due variabili. Non e sempre possibile scegliere a priori unacodifica che favorisca il linkage, ma in alcuni casi usando una codifica chetiene conto di queste specifiche si e potuto notare una netta accelerazione nelconvergere della popolazione verso la soluzione cercata.

Quando il problema non e ben conosciuto e non si sa quali sono i legamifunzionali tra le variabili, una tecnica che tiene conto del linkage e la coevolu-zione. Si lascia un margine di variabilita all’azione degli operatori in manierache questi evolvano insieme alla popolazione. Quello che si spera di ottenereda questa coevoluzione sono degli operatori che, attraverso una azione si-multanea sui loci funzionalmente correlati, riparino all’inadeguatezza dellacodifica.

Capitolo 4

Il lavoro sperimentale

Nel secondo capitolo si e introdotto il problema dell’inferenza grammaticalesia analizzando i risultati teorici fino ad ora dimostrati in questo campo,sia descrivendo i principali approcci sperimentali. In tale trattazione si eevidenziato come molti algoritmi pratici riducono l’inferenza grammaticaleregolare ad un problema di ricerca all’interno di uno spazio. Come e statosottolineato nel terzo capitolo gli algoritmi genetici sono una tecnica di ricercaadatta a problemi come questo: uno spazio di ricerca molto grande poco oper nulla strutturato.

In questo capitolo si descrivera il programma realizzato, per applicare ilparadigma degli AG al problema dell’inferenza grammaticale regolare, e si ri-porteranno i risultati ottenuti nei due test eseguiti per valutare le prestazionidel programma.

4.1 Il programma realizzato

Lo scopo di questo lavoro e stata la realizzazione di un algoritmo geneticoche permettesse di inferire un linguaggio formale. Si e percio costruito unprogramma in codice C che realizzasse questo scopo. Si e deciso di lavorarecon la classe piu piccola della gerarchia di Chomsky, cioe i linguaggi regolari.L’approccio scelto e stato quello di costruire un algoritmo induttivo che nonsi basasse sulle caratteristiche peculiari dell’inferenza grammaticale regolare,esposte nel secondo capitolo. Per inferire un linguaggio regolare si e sceltodi adoperare le grammatiche regolari destre deterministiche. Questa scelta estata ispirata da diversi fattori

• Le grammatiche lineari sono un formalismo semplice, che nella loroforma normale permette di limitare a tre caratteri la lunghezza massima

79

80 Il lavoro sperimentale

di ogni regola di produzione. Questo semplifica molto la progettazionedi una codifica opportuna1.

• Sono del tutto equivalenti agli automi finiti, cioe esistono algoritmie!cienti per passare da un DFA che accetta il linguaggio L alla gram-matica regolare G che genera L, e viceversa.

Per alcuni linguaggi, il numero di simboli non terminali presenti nellagrammatica regolare che li genera e minore del numero di stati del DFAequivalente (ad esempio il linguaggio L8 descritto nel paragrafo 4.2).Quindi in alcuni casi la rappresentazione di un linguaggio in formadi grammatica regolare e piu breve della rappresentazione dello stessolinguaggio in forma di DFA.

• Sono equivalenti alle grammatiche regolari non deterministiche, ma ri-spetto a queste, il problema dell’appartenenza di una stringa al linguag-gio generato e notevolmente meno dispendioso computazionalmente.

• Le grammatiche vengono spesso citate nei lavori sul’inferenza gram-maticale, ma all’atto pratico sono un formalismo relativamente pocousato rispetto agli automi. E quindi interessante provarne un usosperimentale.

Inoltre le grammatiche regolari erano gia state usate in uno studio preliminarea questo lavoro di tesi -lasciato in sospeso-, che riguardava le relazione trastatistica, grammatiche e algoritmi genetici. Il riutilizzo delle grammatichein questo lavoro rientra nello sviluppo di una continuita con quello studio.

La scelta delle grammatiche lineari destre deterministiche pone un sololimite ai linguaggi generabili: non possono contenere la stringa nulla2. Infase di progettazione si e scelto di voler codificare, e quindi potenzialmen-te inferire, solo linguaggi costruiti su alfabeti binari: tutti i linguaggi chesi considereranno nel seguito saranno costruiti sull’alfabeto {0, 1}. Questascelta e stata guidata dall’intenzione di lavorare con dei linguaggi regolarirelativamente poco complessi, per non appesantire troppo la complessita dicalcolo dell’algoritmo.

L’AG prende in ingresso un sample di stringhe S = S+ ! S", e cerca digenerare in uscita una grammatica che

1. Genera tutte le stringhe di S+ e nessuna stringa di S".

1Le regole di una grammatica regolare sono del tipo A + 1B e A + 0.2Vedi appendice A. Quando nel seguito del capitolo si descrivera un linguaggio regolare,

si intendera sempre il linguaggio che si ottiene eliminano da questi la stringa nulla.

4.1 Il programma realizzato 81

2. E la piu piccola possibile, cioe usa il numero piu piccolo di simboli nonterminali.

La popolazione e quindi costituita da grammatiche, che evolvono fino alraggiungimento della condizione di terminazione prestabilita. Se raggiuntaquesta condizione l’algoritmo non e riuscito a trovare alcuna grammatica chesoddisfa la prima condizione, il programma fornisce in uscita la grammaticache fino a quel punto meglio la soddisfa, cioe la grammatica che genera ilmaggior numero di stringhe appartenenti ad S+ e genera il minor numero distringhe appartenenti ad S". Lo schema del programma realizzato si riducefondamentalmente all’esecuzione di un ciclo

Algoritmo Genetico{t=0;Inizializza la popolazione di grammatiche P(t);Valuta la fitness delle grammatiche in P(t);Ripeti fino al tempo limite t=T

{t=t+1;

Crea la popolazione P(t) selezionando le grammaticheda P(t-1) in base alla fitness, e applicaprobabilisticamente gli operatori genetici;

Calcola la fitness delle grammatiche in P(t);}

}

Nel seguito si descriveranno le caratteristiche principali che caratterizzanol’algoritmo.

4.1.1 La codifica

Nel capitolo precedente e stato evidenziato come il punto piu delicato nellaprogettazione di un AG sia la scelta della codifica. Una buona codifica per-mette l’uso di operatori genetici relativamente semplici e pemette tempi diconvergenza relativamente brevi.

Ogni grammatica regolare 3 viene codificata sotto forma di una stringa dilunghezza fissa. La lunghezza fissa dei cromosomi pone un limite superiore

3Nel continuo di questo lavoro per grammatiche regolari si intendera sempregrammatiche regolari destre deterministiche.


al numero di regole di produzione presenti nella grammatica4, ma semplificamolto la progettazione degli operatori genetici e alleggerisce molto la com-plessita computazionale dell’algoritmo. Si e scelto di utilizzare un alfabetonon binario per codificare una grammatica regolare in un cromosoma: questoalfabeto si ottiene unendo l’insieme dei simboli non terminali della gramma-tica, con l’alfabeto binario dei simboli terminali della grammatica, ed infineaggiungendo il simbolo 3.

Poiche l’alfabeto dei simboli terminali e sempre binario, la lunghezza delcromosoma dipende solo dal numero di simboli non terminali: questo numeroverra indicato nel seguito da Nn.t., mentre con N verra indicata un unavariabile che prende valori sui simboli non terminali. L’algoritmo di codificasi basa fondamentalmente su una considerazione: poiche la grammatica eregolare, per ogni simbolo non terminale appartengono alla grammatica almassimo quattro regole che hanno quel simbolo come testa. Ad esempio ilsimbolo A puo comparire alla testa delle seguenti quattro generiche regole diproduzione

A + 0N A + 1N A + 0 A + 1

Non puo esistere un’altra regola con la stessa testa poiche la grammaticadiventerebbe non deterministica.

Nel cromosoma ogni quattro loci a!ancati rappresenteranno, ordinata-menete da sinistra verso destra, per ogni simbolo non terminale N , le quattropossibili regole di produzione che hanno in testa il simbolo N : di conseguenzail cromosoma avra lunghezza Nn.t.44. Ad esempio, i primi quattro loci sullasinistra del cromosoma, rappresenteranno le possibili regole di produzioneche hanno per testa il simbolo A. Precisamente

• Il primo locus rappresenta la regola

A + 0N

Se il valore dell’allele e 3 allora tale regola non e presente nella gramma-tica codificata dal cromosoma. Se invece il valore dell’allele e un simbolonon terminale, ad esempio C, allora la regola A + 0C e presente nellagrammatica codificata dal cromosoma.

• Il secondo locus rappresenta la regola

A + 1N4Vedi il seguito del paragrafo.


Se il valore dell’allele e 3 allora non esiste nella grammatica regolarecodificata dal cromosoma una regola del tipo A + 1N . Se inveceil valore dell’allele e un carattere corrispondente ad un simbolo nonterminale, ad esempio D, allora la regola A + 1D appartiene allagrammatica codificata dal cromosoma.

• Il terzo locus rappresenta la regola

A + 0

Vi sono due possibilita: e presente il carattere 3 e di conseguenza laregola non appartiene alla grammatica, oppure il valore dell’allele e 0e quindi la regola A + 0 appartiene alla grammatica codificata.

• Il quarto locus rappresenta la regola

A + 1

Anche qui vi sono due possibilita: e presente il carattere 3 e di con-seguenza la regola non appartiene alla grammatica, oppure il valoredell’allele e 1 e quindi la regola A + 1 appartiene alla grammaticacodificata.

Ad esempio se N = 2 il cromosoma di figura 4.1-a codifica la grammaticaregolare

A + 0A B + 1AA + 1B B + 0A + 1

mentre relativamente a N = 4 il cromosoma di figura 4.1-b codifica lagrammatica regolare

A + 0C B + 0 C + 1D D + 1A + 1B B + 1 C + 1B + 1A C + 0D D + 1A

4.1.2 Operatori

Con l’intenzione di migliorare le prestazioni dell’algoritmo, sono stati rea-lizzati diversi tipi di operatori genetici. Questi operatori si ispiravano alleconsiderazioni fatte negli ultimi anni sulla “macromutazione” da parte degli


A B * 1 * *A 0a)

B A 0C D D * A* * * 1 1 * * 1b)

Figura 4.1: Cromosomi che codificano grammatiche regolari destre.

studiosi di programmazione evolutiva [SJB+93], ma anche alle ricerche con-dotte specificamente sugli algoritmi genetici nella progettazione di operatoridi ricombinazione ottimali in funzione della codifica. Nei test descritti nelseguito del capitolo sono stati usati solo tre di questi operatori, che rispettoagli altri hanno dimostrato miglioramenti piu apprezzabili nelle prestazionidel sistema. Gli operatori scelti sono:

• Crossing–over

• Mutazione

• Traslocazione

I primi due sono i classici operatori tipici degli algoritmi genetici adattatial problema studiato, mentre il terzo e un nuovo operatore di “macromu-tazione”, recentemente introdotto in un lavoro che ne studia le caratteristi-che [FITC00].

Di"erenti forme di mutazione sono presenti in natura, come diversi sonogli e"etti che questi operatori producono: riordinamento dell’intero geno-ma, duplicazione di alcune parti del genoma, riposizionamento di blocchi dielementi da una zona ad un’altra del genoma. Le tre forme principali dimutazione sono

• livello genico

• livello cromosomico

• livello genomico

Il primo tipo di mutazione comporta dei cambiamenti solo sul singolo gene,ed e la forma di mutazione modellizzata negli algoritmi genetici descrittida Holland [Hol75]. Il secondo tipo comporta dei cambiamenti nell’intero


cromosoma. Si individuano due tipi di mutazioni cromosomiche: il frame–shift, in cui c’e l’inserzione o la delezione di frammenti elementari di DNAdai geni del cromosoma; la traslocazione, in cui viene invertita la posizionenel genoma di frammenti di materiale genetico, appartenenti a cromosomidiversi. La mutazione a livello genomico, infine, fa variare il numero dicromosomi che costituiscono il genoma.

Nonostante storicamente gli AG modellizano solo la mutazione a livellogenico, negli ultimi anni si puo riscontrare un certo interesse nella realizza-zione di operatori di mutazione diversi e piu realistici. Questa tendenza siinserisce anche nella revisione dei risutati derivanti da teorema degli schemi,e quindi nelle critiche sull’e"ettiva centralita dell’operatore di crossing–overnel processo evolutivo5.

Crossing–over

L’operatore di crossing–over realizzato e praticamente identico a quello de-scritto nel capitolo precedente: l’uso di un alfabeto non binario per la codifica,non comporta restrizioni sull’azione di questo operatore (vedi figura 4.2). Si escelto di realizzare un crossing–over che producesse solo un elemento in usci-ta: viene scelto casualmente quale dei due figli prodotti dovra sopravviveree quale invece verra distrutto. Nel seguito con Pc si indichera la probabi-lita che questo operatore agisca. Nei test eseguiti sono stati provati diversivalori per Pc, al fine di definire l’importanza dell’operatore di crossing–overall’interno del processo evolutivo.

BA 0* * 0 ACC **1

BC * * * BC * * *

BA 0* *

A 0 1 1C* * 0 ACC 1 * *

A 0 1 1C **

Figura 4.2: Azione dell’operatore di Crossing–over.

Mutazione

L’operatore di mutazione realizzato e molto simile a quello formalizzato daHolland [Hol75], che modellizza la mutazione genica, e gia descritto nel ca-pitolo precedente. La di"erenza sostanziale e dovuta alla scelta di usare

5Vedi la discussione al termine del terzo czpitolo.


A B * 1 * *A 0

A B * 1 * *A 0b)

a)

A B 1 A 0 1* *

A 1 * A 0A **

Figura 4.3: Azione dell’operatore di mutazione.

una codifica che obbliga alcuni simboli a cpmparire solo in delle zone preci-se del cromosoma: questo comporta un’azione non uniforme dell’operatorelungo il cromosoma. Per non creare discendenze amorfe, cioe per non crearecromosomi che non rappresentano correttamente una grammatica, l’azionedell’operatore di mutazione e funzione del locus su cui agisce. In base allacodifica ogni quattro loci a!ancati rappresentano, ordinatamente da sinistraverso destra, per ogni simbolo non terminale N , le quattro possibili regoleche hanno in testa N : se la mutazione agisce su uno dei primi due, di questiquattro loci, allora l’allele dopo la mutazione puo essere un qualsiasi simbolonon terminale, oppure il simbolo 3 (vedi figura 4.3-b). Nel caso la mutazioneagisca su uno degli ultimi due loci, allora il valore dell’allele dopo l’azionedell’operatore puo essere, rispettivamente, 0 o 1, oppure il simbolo 3 (vedifigura 4.3-b). Nel seguito con il simbolo Pm si indichera la probabilita diazione sul singolo gene dell’operatore di mutazione: in tutti i test condottil’operatore di mutazione agisce su ogni cromosoma, con Pm= 0.05. Que-sto valore e stato scelto seguendo la regola empirica Pm = 1

l , dove l e lalunghezza del cromosoma.

Traslocazione

In questo lavoro si e deciso di usare anche un operatore genetico ispiratoalla mutazione per traslocazione. Questo operatore e stato studiato nel con-testo degli algoritmi genetici solo recentemente, ed e stato applicato solo aproblemi–modello classici sulla ricerca del massimo di una funzione a valorireali [FITC00]. Adattando alla codifica scelta per le grammatiche regolaril’operatore descritto nel lavoro sopra citato otteniamo l’algoritmo (figura 4.4):

1. Scegliere casualmente due simboli non terminali N1 e N2 tra quellicodificati nel cromosoma.

2. Invertire nel cromosoma gli alleli dei loci che codificano le regole chehanno per testa N1 con gli alleli dei loci che codificano le regole chehanno per testa N2.


A C * 1 B * 0 1

B EA C D F

A C * 1B * 0 1

B EA C D F

(a) Cromosoma prima della Traslocazione.

(b) Cromosoma dopo la Traslocazione.

Figura 4.4: Azione dell’operatore di traslocazione.

Nel seguito di questo lavoro con Pt si indichera la probabilita che l’operatoredi traslocazione agisca su un singolo elemento. Nei test eseguiti sono statiassegnati a Pt diversi valori, con il fine preciso di paragonare le prestazionidi questo operatore con il crossing–over.

4.1.3 Parametri

Nel progettare un algoritmo genetico e necessario fare un certo numero discelte per assegnare il valore di alcuni parametri, che definiscono le caratteri-stiche, e quindi il comportamento, dell’algoritmo. Per decidere i valori adattil’unico riferimento e dato dal confronto delle prestazioni dell’algoritmo perdiversi valori.

La dimensione della popolazione, dopo diverse prove, e stata assegnata a500 elementi. Si e deciso inoltre di assegnare la lunghezza del cromosoma a20 caratteri: quindi sono presenti al massimo 5 simboli non terminali nellagrammatica codificabile. Questa scelta sulla lunghezza dei cromosomi e statafatta tenendo in considerazione i dati usati nei test che verranno descritti nelseguito: la grammatica inferita piu grande conteneva cinque simboli nonterminali.

La popolazione iniziale viene generata casualmente. E stata provata an-che una variante suggerita da Lucas [IEE94], cioe si e provato a “polarizza-


re” la popolazione iniziale, richiedendo che ogni grammatica rappresentatada un cromosoma della popolazione iniziale accettasse almeno una stringadegli esempi positivi contenuti nel sample S+. Poiche si e visto che in ge-nerale questo procedimento non comportava particolari miglioramenti nelleprestazioni dell’AG, si e deciso infine di eliminarla.

Il primo metodo di selezione usato e stato la truncation, che riferendosialla velocita di convergenza e un metodo particolarmente buono. La percen-tuale di elementi della popolazione destinati a riprodursi era stata assegnataal 10%: venivano scelti tra i primi 50 elementi, in ordine di fitness, i cro-mosomi a cui bisognava applicare gli operatori genetici per creare la nuovagenerazione. In un secondo momento si e scelto di usare il metodo della se-lezione proporzionale. Questo metodo di selezione e certamente piu lento maha il vantaggio di mantenere una certa diversita all’interno della popolazione.Per matenere ancora piu alta la diversita nella popolazione, se viene applica-to l’operatore di cross–over, uno dei due genitori viene scelto casualmente eindipendentemente dalla fitness, all’interno dell’intera popolazione. Insiemealla selezione proporzionale si e deciso di adottare una strategia 1–elitista,cioe l’elemento con la fitness piu alta della popolazione attuale viene inseritonella popolazione successiva. Se piu elementi hanno la stessa fitness l’elitismosceglie casualmente uno di questi

Nei test descritti nel seguito si e scelto di usare un metodo di selezioneibrido tra la selezione proporzionale e la truncation.

• Se la popolazione non contiene una grammatica con fitness 1, la po-polazione successiva viene costruita interamente attraverso la selezioneproporzionale e strategia 1–elitista.

• Se invece nella popolazione e presente almeno una grammatica di fitness1, tutti gli elementi della popolazione successiva, eccetto uno, sarannocostruiti ancora con la selezione proporzionale, mentre la scelta dell’e-lemento 1–elitista viene ora eseguita non casualmente ma con una se-conda “super–selezione” per truncation applicata sul sottoinsieme dellapopolazione contenente tutte le grammatiche di fitness 1. Il criterio concui questa truncation ordina le grammatiche tiene conto dei simboli nonterminali presenti. La truncation considera migliori le grammatiche cheusano meno simboli non terminali6. In pratica la truncation ordina legrammatiche di fitness 1 in base ad una nuova “super–fitness”, chevaluta unicamente la semplicita della grammatica.

6Se due grammatiche hanno lo stesso numero di simboli non terminali, la truncationconsidera migliore la grammatica che usa meno regole di produzione.


L’uso di questo metodo di selezione, certamente irrealistico nel confrontocon la selezione naturale, e uno stratagemma che permette di usare in pri-ma istanza una fitness che non tiene conto del criterio di preferenza versole grammatiche piu brevi. Cio e stato fatto per prevenire la convergenzaprecoce verso una popolazione di grammatiche molto brevi, ma pessime nelclassificare correttamente l’insieme di esempi labellati forniti in input.Tali scostamenti dalla selezione naturale sono peraltro anche e"ettuati nellarealizzazione degli operatori genetici (principalmente negli operatori muta-zione).

L’ultimo parametro da assegnare riguardava il criterio in base al qualefermare l’algoritmo genetico. Poiche uno dei criteri che giudicano la bontadella soluzione riguarda la lunghezza della grammatica inferita, in generalenon si e mai certi di essere arrivati alla soluzione ottimale. Di conseguenzasi e scelto di fermare la computazione basandosi solo su un limite tempo-rale: l’algoritmo termina dopo aver generato esattamente 1000 generazioni,restituendo la migliore grammatica dell’ultima generazione. In tutti i testdescritti nel seguito, indipendentemente dalla “complessita” del linguaggioche si intendeva inferire, si e usato questo criterio di terminazione.

4.1.4 Fitness

In un algoritmo genetico la fitness deve giudicare la bonta di un elemento dellapopolazione nel risolvere un dato problema. All’interno del nostro progettola funzione di fitness f ha per dominio l’insieme di tutte le grammaticheregolari, e per codominio l’insieme dei numeri reali. La fitness restituisce unvalore che esprime quanto una grammatica G e compatibile con il sampleS = S+ ! S": quindi qualsiasi funzione f si deve basare sul confronto dellinguaggio generato da G con l’insieme S.

Nel definire la fitness di una grammatica G, indichiamo con Tp il numerodi stringhe appartenenti a S+ che sono anche generate dalla grammatica G,mentre con Fp indichiamo il numero ||S+||%Tp. Inoltre con Tn indichiamo ilnumero di stringhe di S" che non sono generate dalla grammatica G, mentrecon Fn indichiamo ||S"|| % Tn. Se una grammatica e compatibile con unsample S = S+ ! S" si avra Tp = ||S+|| e Tn = ||S"||. Il calcolo di Tp eTn, viene esguito operativamente attraverso un algoritmo di parsing : dandoin ingresso la grammatica G ed una stringa s # S, l’algoritmo di parsingverifica se esiste una sequenza finita di regole di G la cui esecuzione produces, quindi verifica se s # L(G).

Durante la fase di ottimizzazione dei parametri sono state provate trefitness


• f1(G) = Tp'Tn"Fp'Fn7(Tp+Fp)(Fp+Tn)(Tn+Fn)(Fn+Tp)

Questa e una tipica funzione di fitness usata nel campo del data–mining.

• f2(G) =3

Tp||S+||

44

3Tn

||S!||

4

Questa funzione di fitness e stata proposta da Huijnsen in [CLI93].Nel suo lavoro Huijnsen dimostra sperimentalmente la superiorita diquesta fitness, che egli chiama produttiva rispetto alla fitness cumula-tiva fc = Tp+Tn

||S+||+||S!|| , nell’inferenza grammaticale di semplici linguaggicontext–free mediante automi push–down.

• f3(G) =3

Tp||S+||

424

3Tn

||S!||

4

Questa fitness e stata usata per la prima volta in questo lavoro, ede quella adoperata per eseguire i test descritti nel seguito.

Le funzioni ora descritte risultano essere tutte normalizzate, cioe hanno percodominio l’intervallo [0, 1], e assumono il valore massimo in conicidenza diuna grammatica G compatibile con il sample S. La fitness f3 e stata sceltaper eseguire i test poiche e quella che sperimentalmente ha portato ai miglioririsultati. Una considerazione che si puo fare confrontando le funzioni f2 ef3, e che quest’ultima e asimmetrica nella valutazione degli esempi positivigenerati dalla grammatica rispetto alla valutazione degli esempi negativi nongenerati dalla grammatica. Supponiamo che per una grammatica G1 si abbia

Tp||S+|| = # e Tn

||S!|| = $ mentre per la grammatica G2 si abbia Tp||S+|| = $ e

Tn||S!|| = #. Supponiamo inoltre che # > $ > 0. In base alle definizioni

precedenti f2(G1) = f2(G2), mentre f3(G1) > f3(G2): due grammatiche chehanno lo stesso valore per f2 vengono separate da f3 in due valori diversi, inquanto f3 sopravaluta la grammatica che accetta piu esempi positivi.

4.2 Linguaggi di prova

Per valutare le prestazioni dell’algoritmo genetico costruito si e deciso di noncreare dei linguaggi regolari appositi, ma di usare dei linguaggi gia adoperatiper testare altri algoritmi. In letteratura si trovano due tipi di linguaggi diprova, che di"eriscono per la complessita dell’automa che inferisce il linguag-gio. Da una parte troviamo linguaggi in cui il numero degli stati dell’automacorrispondente non supera dieci, dall’altra troviamo invece linguaggi in cuil’automa corrispondente ha un numero di stati nell’ordine di cento. La di"e-renza tra i due insiemi e dovuta al diverso scopo per cui i linguaggi di prova

4.2 Linguaggi di prova 91

sono stati creati: il primo insieme e destinato a provare algoritmi “innova-tivi”, di cui ancora non si conoscono le caratteristiche; il secondo insiemee usato invece per testare il limite di algoritmi gia collaudati, e che hannogia dimostrato la loro e!cienza sul primo insieme. Per le finalita di questolavoro si e deciso di usare linguaggi appartenenti al primo insieme.

Tomita in [Tom82] definisce sette linguagi regolari, da lui usati per pro-vare il suo algoritmo di inferenza grammaticale basato sulla tecnica di hill–climbing. Succesivamente nei lavori [MdG94] [Dup94], questo insieme vieneampliato aggiungenedo altri otto linguaggi regolari. L’elenco completo deiquindici linguaggi si trova nella tabella 4.1. Questi linguaggi definiti “nonbanali” dagli ideatori, hanno degli automi corrispettivi il cui numero di sta-ti varia da uno del linguaggio L1, a cinque del linguaggio L10. Alcuni diessi sono descritti dall’espressione regolare corrispondente. Nei casi in cuil’espressione regolare fosse troppo complicata al fine di capire immediata-mente la “regolarita” del linguaggio, si e preferito fornire una descrizione dellinguaggio informale ma rigorosa. Ad esempio l’espressione regolare per illinguaggio L6 e ((0(01)!(1|00))|(1(10)!(0|11)))

!: non e immediato riconosce-

re in questo caso la regolarita aritmetica posseduta dal linguaggio, costituitoda tutte le stringhe in cui il numero dei caratteri 0 di"erisce dal numero deicaratteri 1 per un numero divisibile per tre.

L1

q0

0

A + 0AA + 0


L1 0!

L2 (01)!

L3 Ogni stringa che non contiene un numero dispari di 0 consecutivi dopo unnumero dispari di 1 consecutivi.

L4 Ogni stringa che non contiene la sottostringa 000.L5 Ogni stringa che contiene un numero pari di 0 ed un numero pari di 1.L6 Ogni stringa in cui il numero di 0 contenuti di"erisce dal numero di 1

contenuti per un numero divisibile per tre.L7 0!1!0!1!

L8 0!1L9 (0! + 2!)1!

L10 (00)!(111)!

L11 Ogni stringa che contiene un numero pari di 0 ed un numero dispari di 1.L12 0(00)!1L13 Ogni stringa che contiene un numero dispari di caratteri 0.L14 (00)!10!

L15 12!1 + 02!0

Tabella 4.1: Linguaggi definiti in [Dup94]

L2

q0 1q0

1 A + 0B B + 1B + 1A


L3

q0 1q2q1

00

1

00

1 q3

A + 0A B + 0C C + 0A + 1B B + 1A D + 0CA + 0 B + 1 D + 1BA + 1 C + 0D D + 1

L4

q0 1q

2q

0

1

10

1

A + 0B B + 0C C + 1AA + 1A B + 1A C + 1A + 0 B + 0A + 1 B + 1

L5

2qq0

q1

1 0

0

1

1 1

0

0

q3

A + 0B B + 0 D + 1AA + 1D C + 1B D + 1B + 0A C + 0DB + 1C D + 0C

L6

2q

q0 q1

1 0

1 1 00A + 0C B + 0A + 1B C + 0BB + 0A C + 1AB + 1C C + 1


L7

q1 2qq01 01

0 1 1 0

q3

A + 0A B + 1B C + 0A + 1B B + 0 C + 1A + 0 B + 1 D + 1DA + 1 C + 0C D + 1B + 0C C + 1D

L8

1qq0

10

A + 0AA + 1

L10

q4

2q

3q

q0

q1

0 0

1

1 1 1

A + 0B C + 1DA + 1C D + 1EB + 0A D + 1B + 0 E + 1C

L11

2qq1

1 0

0

1

1 1

0

0q0

q3

A + 0B B + 1C D + 0CA + 1D C + 0D D + 1AA + 1 C + 1BB + 0A C + 0


L12

1q0

q0 q2

1

0A + 0BB + 0AB + 1

L13

q0 1q01 1

0 A + 0B B + 0AA + 1A B + 1BA + 1 B + 0

L14

2q0

0q0 1q

01

A + 0B B + 0AA + 1C C + 0CA + 1 C + 0


4.3 Primo test

Il primo test e stato eseguito con la finalita di quantificare l’e!cienza dell’al-goritmo genetico nell’inferire la piu piccola grammatica regolare compatibilecon un sample di esempi S = S+ !S". Per ottenere questo scopo si e decisodi ispirarsi alle modalita di sperimentazione descritte in [Dup94], ed usateper testare l’e!cienza dell’algoritmo genetico GIG realizzato da Dupont, co-struito con l’intento di inferire il piu piccolo automa finito compatibile con unsample di esempi. Operando in questo modo e possibile paragonare i risulta-ti ottenuti dall’algoritmo genetico realizzato in questo lavoro, con i risultatiottenuti dall’algoritmo genetico GIG. Questo confronto e particolarmenteinteressante per due motivi.

Il primo motivo e dovuto alla diversa rappresentazione del linguaggioregolare scelta nei due algoritmi: nell’algoritmo GIG si usano gli automifiniti mentre in questo lavoro si e scelto di usare le grammatiche regolari.

Il secondo motivo e dovuto al fatto che l’algoritmo GIG sfrutta le caratte-ristiche peculiari dell’inferenza grammaticale regolare, illustrate nel secondocapitolo di questo lavoro. Supponendo la completezza strutturale del samplefornito in ingresso, l’algoritmo genetico di Dupont riduce lo spazio di ricercaal reticolo costruito sul PTA associato al sample. Contrariamente, l’algorit-mo genetico realizzato in questo lavoro non fa uso del reticolo, ma cerca inuno spazio limitato solo dal numero massimo di simboli non terminali ap-partenenti alla grammatica. Puo sembrare che l’algoritmo realizzato usi unvincolo a priori non adoperato dall’algoritmo GIG: cio non e vero in quan-to basandosi sulla costruzione del PTA rispettivo al sample, indirettamentefissa il valore massimo del numero di stati.

4.3.1 Dati usati nel primo test

I dati usati in questo test coincidono con quelli usati in [Dup94]. Per ognilinguaggio della tabella 4.1 sono stati creati da Dupont 20 sample S di esempilabellati. Ognuno dei 20 sample S = S+ ! S", per ogni linguaggio L, godedi due proprieta

1. S+ e un insieme di stringhe generato casualmente attraverso un random–walk dal minimo automa finito che accetta L. Indichiamo con ||S+||c lacardinalita del piu piccolo insieme di stringhe che risulta essere struttu-ralmente completo per L. La costruzione dell’insieme S+ attraverso ilrandom–walk termina quando l’insieme diventa strutturalmente com-pleto ed inoltre quando il numero di stringhe presenti in S+ raggiungeil valore ||S+|| ) ||S+||c 4M , dove M e un numero intero usato comeparametro.

4.3 Primo test 97

2. S" e costruito con la stessa modalita di S+, ma rispetto all’automaminimo che accetta il linguaggio #! % L.

I sample risultanti hanno una cardinalita che varia da 1 a 156, mentre lalunghezza delle stringhe contenute negli insiemi varia tra 1 e 1017 (7).

Dupont suddivide in due classi i sample creati: nella prima classe rientra-no gli insiemi di esempi labellati creati con il valore del parametro M postoad 1, mentre nella seconda classe rientrano gli insiemi creati con il valoredel parametro M posto a 3. Poiche i sample della seconda classe sono gene-ralmente piu grandi dei sample della prima classe, hanno piu probabilita diessere caratteristici per il linguaggio, cioe di contenere le stringhe necessarieper inferire correttamente il linguaggio.

4.3.2 Protocollo di sperimentazione del primo test

Nella sperimentazione sono stati usati i linguaggi della tabella 4.1, con l’esclu-sione dei linguaggi L9 e L15: questi erano costruiti su alfabeti a tre simboli,mentre l’algoritmo genetico era stato progettato per indurre solo linguaggibinari.

Per ognuno dei 13 linguaggi rimanenti, sono stati usati come dati solo i10 sample caratterizzati dal valore del parametro M = 3.

Inoltre per ottenere dei risultati statisticamente piu a!dabili l’algoritmogenetico e stato eseguito 10 volte su ogni singolo sample, variando il valoredei semi per la generazione iniziale. Quindi su ognuno dei tredici linguaggisono state eseguite 100 prove (10 sample 4 10 prove). Il risultato di ognisingola prova e la grammatica che ha la fitness piu alta e il minor numerodi regole di produzione8, tra le grammatiche presenti nella popolazione della1000–ma generazione.

Seguendo il protocollo di Dupont, per valutare l’esattezza della gramma-tica ottenuta come risultato della prova, si confronta il linguggio generato daquesta grammatica con l’insieme P di tutte le stringhe binarie di lunghezzaminore o uguale a 9 ad esclusione della stringa nulla9 (||P || = 1022).

Per ogni linguaggio L, partendo da P si costruiscono due sottoinsiemi P +L

e P"L

7Si e verificato che nessuno dei sample forniti da Dupont contiene la stringa nulla.8Solo se c’e un elemento di fitness 1 nella popolazione9Il valore 9 si ottiene riferendosi al lavoro di Trakenbort e Barzdin citato nel secondo

capitolo. E possibile inferire il piu piccolo DFA che accetta un linguaggio regolare, sevengono fornite come esempi labellati tutte le stringhe fino alla lunghezza 2N % 1, doveN e il numero di stati dell’automa. Poiche tra i linguaggi della tabella 4.1, il massimonumero di stati e 5, abbiamo 24 5% 1 = 9; l’insieme di tutte le stringhe fino a lunghezza9 caratterizza quindi ogni linguaggio della tabella 4.1.


• P+L e costituito da tutte le stringhe di P che appartengono al linguaggio

L e che non appartengono alla parte positiva del sample usato durantel’esecuzione del programma P +

L = (P % S+) / L.

• P"L e costituito da tutte le stringhe di P che non appartengono al

linguaggio L e che non appartengono alla parte negativa del sampleusato durante l’esecuzione del programma P"

L = (P % S") / (#! % L).

Usando questi due insiemi, l’esatteza di una grammatica G ottenuta comerisultato di una esecuzione dell’algoritmo genetico si esprime mediante duepercentuali

• La prima calcola la percentuale delle stringhe dell’insieme P +L corret-

tamente classificate da G come appartenenti al linguaggio, ed e quindiuguale a

V+ =||P+

L / L(G)||||P+

L ||

• La seconda calcola la percentuale delle stringhe dell’insieme P"L cor-

rettamente classificate da G come non appartenenti al linguaggio, ed equindi uguale a

V" =||P"

L / (#! % L(G))||||P"

L ||

I valori delle percentuali ottenuti si calcolano mediando prima sulle dieciprove eseguite per ogni sample, e poi mediando sui dieci sample usati perogni linguaggio.

I risultati relativi a tutti i 13 linguaggi usati sono stati elencati in delletabelle in cui

• La colonna +classe contiene per ogni linguaggio L la percentuale del-le stringhe di P % S+ correttamente classificate come appartenenti allinguaggio. Questo valore si ottiene mediando i 100 valori V+ ottenutidalle 10 prove eseguite sui 10 sample.

• La colonna -classe contiene per ogni linguaggio L la percentuale dellestringhe di P % S" correttamente classificate come non appartenential linguaggio. Anche questo valore si ottiene mediando i 100 valori V"ottenuti dalle 10 prove eseguite sui 10 sample.

4.3 Primo test 99

Pc PtAG–# 0.66 0.00AG–$ 0.33 0.33AG–& 0.00 0.66

Tabella 4.2: Le tre prove eseguite

• La colonna classe contiene per ogni linguaggio la percentuale dellestringhe di P % S correttamente classificate, ed e quindi la media delledue colonne precedenti.

• La colonna massimo contiene per ogni linguaggio la media sui 10 sam-ple del valore massimo di V++V!

2 ottenuto nelle 10 prove eseguite sulsingolo sample.

• La colonna best contiene per ogni linguaggio la media sui 10 sampledel valore di V++V!

2 relativo alla grammatica che usa il minor numerodi simboli non terminali, tra le grammatiche ottenute come soluzionenelle 10 prove eseguite sul singolo sample10.

E importante considerare anche separatamente la percentuali espresse da+classe e -classe: se si considerasse solo la media, una grammatica con zeroregole di produzione puo avere un buon valore di -class per un linguaggio chepossiede poche stringhe di lunghezza minore o uguale a 9. Specularmenteuna grammatica che accetta interamente #! puo avere un buon valore di+class relativamente un linguaggio che possiede molte stringhe di lunghezzaminore o uguale a 9.

Operatori genetici

In questo test si era interessati anche a paragonare le prestazioni dell’algorit-mo genetico ottenute con diverse probabilita di azione degli operatori. Perquesto il protocollo di sperimentazione prima descritto e stato applicato trevolte, per tre di"erenti insiemi di valori per le probabilita degli operatori.Riferendosi alla tabella 4.2, le tre versioni provate dell’algoritmo genetico so-no state chiamate AG–#, AG–$ e AG–&. In particolare in AG–# si e volutomettere in rilievo l’azione dell’operatore di crossing–over, mentre in AG–& sie voluto mettere in rilievo l’azione dell’operatore di traslocazione; infine inAG–$ si e voluto valutare l’azione combinata di questi due operatori

10Se ci sono piu grammatiche che usano lo stesso numero di siboli non terminali, sisceglie il valore piu grande.


Nel seguito si confronteranno i risultati ottenuti da queste tre formedell’algoritmo genetico, con i risultati ottenuti dall’algoritmo GIG di Du-pont [Dup94].

4.3.3 Risultati del primo test

Confrontando le tabelle che riassumono i risultati si possono fare tre consi-derazioni.

1. Per ogni linguaggio, nei casi in cui l’algoritmo genetico raggiunge il100% nella classificazione delle stringhe, si e verificato che la gramma-tica inferita coincide con la grammatica minima del linguaggio (vediparagrafo 4.2).

2. L’algoritmo genetico di Dupont ha delle prestazioni inferiori al nostroalgoritmo genetico relizzato in tutte le prove eseguite.

3. Indipendentemente dai risultati dell’algoritmo GIG di Dupont, parago-nando i risultati ottenuti nelle tre prove eseguite, risulta che l’operatoredi traslocazione funziona meglio del classico operatore di crossing–over.

+classe -classe classe massimo best

GIG 91.0 89.0 90.0 95.4 93.7AG-# 88.2 96.9 92.5 96.4 95.9AG-$ 88.7 97.6 93.2 96.7 95.9AG-& 89.2 98.1 93.7 96.7 96.0

Tabella 4.3: Confonto dei risultati ottenuti dal nostro algoritmo genetico edall’algoritmo GIG

4.3 Primo test 101

Linguaggio +classe -classe classe massimo best

L1 100.0 100.0 100.0 100.0 100.0L2 99.7 100.0 99.8 100.0 100.0L3 91.9 98.8 95.3 99.4 94.6L4 68.0 79.7 73.9 90.6 81.2L5 74.6 63.4 69.0 83.5 80.5L6 92.0 86.3 89.2 95.0 95.0L7 96.3 93.3 94.8 100.0 99.2L8 100.0 100.0 100.0 100.0 100.0L10 93.9 99.1 96.5 99.9 96.6L11 78.6 42.7 60.7 72.2 70.8L12 100.0 99.6 99.7 99.8 99.8L13 98.8 97.7 98.2 100.0 100.0L14 89.2 96.4 92.8 99.9 99.8

media 91.0 89.0 90.0 95.4 93.7

Tabella 4.4: Risultati dell’algoritmo genetico “GIG” [Dup94]


L1 100.000 100.000 100.000 100.000 100.000L2 100.000 100.000 100.000 100.000 100.000L3 82.648 99.718 91.183 92.176 92.176L4 70.579 100.000 85.290 91.746 91.746L5 73.413 86.204 79.809 96.033 94.852L6 84.790 97.774 91.282 94.005 94.005L7 85.279 95.135 90.207 98.080 98.080L8 100.000 100.000 100.000 100.000 100.000L10 94.750 99.634 97.192 97.453 97.194L11 75.194 81.658 78.426 89.193 83.061L12 100.0 100.000 100.000 100.000 100.000L13 92.976 99.535 96.255 100.000 100.000L14 86.445 99.825 93.135 95.146 95.146

media 88.2 96.9 92.5 96.4 95.9

Tabella 4.5: Risultati dell’algoritmo genetico nelle prove con AG–#



L1 100.000 100.000 100.000 100.000 100.000L2 100.000 100.000 100.000 100.000 100.000L3 82.896 100.000 91.448 92.176 92.176L4 69.872 100.000 84.936 92.906 92.906L5 73.741 87.098 80.419 93.860 91.837L6 85.707 99.290 92.498 94.005 94.005L7 90.331 97.339 93.865 98.080 98.080L8 100.000 100.000 100.000 100.000 100.000L10 92.500 99.805 96.153 97.453 97.293L11 76.171 86.414 81.293 92.999 85.584L12 100.0 100.000 100.000 100.000 100.000L13 93.915 99.262 96.589 100.000 100.000L14 87.672 99.837 93.755 95.146 95.146

media 88.7 97.6 93.2 96.7 95.9

Tabella 4.6: Risultati dell’algoritmo genetico nelle prove con AG–$


L1 100.000 100.000 100.000 100.000 100.000L2 100.000 100.000 100.000 100.000 100.000L3 83.311 100.000 91.656 92.176 92.176L4 70.502 100.000 85.251 92.906 92.906L5 77.973 89.495 83.734 93.860 90.842L6 88.009 100.00 94.005 94.005 94.005L7 87.150 96.668 91.909 98.080 98.080L8 100.000 100.000 100.000 100.000 100.000L10 95.000 99.885 97.443 97.453 97.346L11 78.263 90.257 84.260 92.962 87.894L12 100.0 100.000 100.000 100.000 100.000L13 92.976 99.535 96.255 100.000 100.000L14 86.281 99.837 93.059 95.146 95.146

media 89.2 98.1 93.7 96.7 96.0

Tabella 4.7: Risultati dell’algoritmo genetico nelle prove con AG–&

4.4 Descrizione di alcuni run 103

4.4 Descrizione di alcuni run

In questo paragrafo si descriveranno nei particolari, 3 delle 1300 prove ese-guite complessivamente all’interno del primo test. Questi valori sono statiottenuti con la versione AG–& dell’algoritmo genetico, cioe con la versioneche ha dimostrato le prestazioni mediamente migliori.

Per come e stato progettato il programma restituisce la grammatica mi-gliore presente nella popolazione solo se questa ha fitness uguale a 1.

Linguaggio= L4 Sample= 15 prova= 10

La grammatica minima corrispondente al linguaggio L4 possiede 3 simbolinon terminali. Si analizzeranno solo le parti cruciali dell’output prodottodall’algoritmo:

...generazione= 6 fitmedia= 0.447951 bestFit= 0.888889generazione= 7 fitmedia= 0.454888 bestFit= 0.888889generazione= 8 fitmedia= 0.470326 bestFit= 1.000000A->0B A->1C A->0 A->1 B->0E B->1A B->0 B->1 C->1D C->0 C->1D->0B D->1C D->0 D->1 E->1D E->1generazione= 9 fitmedia= 0.493782 bestFit= 1.000000A->0B A->1C A->0 A->1 B->0E B->1A B->0 B->1 C->1D C->0 C->1D->0B D->1C D->0 D->1 E->1D E->1generazione= 10 fitmedia= 0.487130 bestFit= 1.000000A->0B A->1C A->0 A->1 B->0E B->1A B->0 B->1 C->1D C->0 C->1D->0B D->1C D->0 D->1 E->1D E->1generazione= 11 fitmedia= 0.496431 bestFit= 1.000000A->0B A->1E A->0 A->1 B->0D B->1A B->0 B->1 C->0B C->0 D->0ED->1C D->1 E->1B E->0 E->1generazione= 12 fitmedia= 0.513571 bestFit= 1.000000A->0B A->1E A->0 A->1 B->0D B->1A B->0 B->1 C->0B C->0 D->0ED->1C D->1 E->1B E->0 E->1generazione= 13 fitmedia= 0.513313 bestFit= 1.000000A->0B A->1E A->0 A->1 B->0D B->1A B->0 B->1 C->0B C->0 D->0ED->1C D->1 E->1B E->0 E->1generazione= 14 fitmedia= 0.509689 bestFit= 1.000000A->0B A->1E A->0 A->1 B->0D B->1A B->0 B->1 C->0B C->0 D->0ED->1C D->1 E->1B E->0 E->1generazione= 15 fitmedia= 0.514435 bestFit= 1.000000A->0B A->1E A->0 A->1 B->0D B->1A B->0 B->1 C->0B C->0 D->0E


D->1C D->1 E->1B E->0 E->1generazione= 16 fitmedia= 0.517868 bestFit= 1.000000A->0B A->1E A->0 A->1 B->0D B->1A B->0 B->1 C->0B C->0 D->0ED->1C D->1 E->1B E->0 E->1generazione= 17 fitmedia= 0.520937 bestFit= 1.000000A->0B A->1E A->0 A->1 B->0D B->1A B->0 B->1 C->0B C->0 D->0ED->1C D->1 E->1B E->0 E->1generazione= 18 fitmedia= 0.514365 bestFit= 1.000000A->0B A->1E A->0 A->1 B->0D B->1A B->0 B->1 D->0E D->1A D->1E->1B E->0 E->1generazione= 19 fitmedia= 0.504669 bestFit= 1.000000A->0B A->1E A->0 A->1 B->0D B->1A B->0 B->1 D->0E D->1A D->1E->1B E->0 E->1generazione= 20 fitmedia= 0.525171 bestFit= 1.000000A->0B A->1E A->0 A->1 B->0D B->1A B->0 B->1 D->0E D->1A D->1E->1B E->0 E->1generazione= 21 fitmedia= 0.529834 bestFit= 1.000000A->0B A->1E A->0 A->1 B->0D B->1A B->0 B->1 D->0E D->1A D->1E->1B E->0 E->1generazione= 22 fitmedia= 0.519173 bestFit= 1.000000A->0B A->1E A->0 A->1 B->0D B->1A B->0 B->1 D->0E D->1A D->1E->1B E->0 E->1generazione= 23 fitmedia= 0.524369 bestFit= 1.000000A->0B A->1E A->0 A->1 B->0D B->1A B->0 B->1 D->0E D->1A D->1E->1B E->0 E->1generazione= 24 fitmedia= 0.521890 bestFit= 1.000000A->0B A->1A A->0 A->1 B->0D B->1A B->0 B->1 C->0B C->1B C->0D->1C D->1generazione= 25 fitmedia= 0.546002 bestFit= 1.000000A->0B A->1A A->0 A->1 B->0D B->1A B->0 B->1 D->1A D->1generazione= 26 fitmedia= 0.558050 bestFit= 1.000000A->0B A->1A A->0 A->1 B->0D B->1A B->0 B->1 D->1A D->1...

In questa prova una grammatica compatibile con il sample viene gia trovataalla generazione 8. Questa soluzione non e pero la piu piccola, possedendola grammatica 5 simboli non terminali. Come si puo osservare la soluzioneviene ra"nata al passare delle generazioni: la migliore grammatica ha sempremeno regole di produzione. La grammatica migliore della generazione 25 e la

4.4 Descrizione di alcuni run 105

grammatica minima11 (vedi paragrafo 4.2), e viene quindi mantenuta nellapopolazione fino alla 1000–ma generazione.

...generazione= 999 fitmedia= 0.598355 bestFit= 1.000000A->0B A->1A A->0 A->1 B->0D B->1A B->0 B->1 D->1A D->1generazione= 1000 fitmedia= 0.602559 bestFit= 1.000000A->0B A->1A A->0 A->1 B->0D B->1A B->0 B->1 D->1A D->1


La grammatica minima corrispondente al linguaggio L5 possiede 5 simbolinon terminali. In questa prova l’algoritmo non riesce a trovare una gramma-tica compatibile con il sample di ingresso. Infatti raggiunge il valore massimoalla 35–ma generazione, ma non riesce a trovare un elemento migliore durantele rimanenti generazioni

...generazione= 32 fitmedia= 0.601568 bestFit= 0.982906generazione= 33 fitmedia= 0.606865 bestFit= 0.982906generazione= 34 fitmedia= 0.577563 bestFit= 0.982906generazione= 35 fitmedia= 0.580761 bestFit= 0.991453generazione= 36 fitmedia= 0.586035 bestFit= 0.991453......generazione= 999 fitmedia= 0.571545 bestFit= 0.991453generazione= 1000 fitmedia= 0.585473 bestFit= 0.991453A->0D A->1C B->1A B->1 C->1B D->0A D->0

In questo caso la soluzione restituita dall’algoritmo e la grammatica appar-tenente all’ultima generazione che possiede la fitness piu alta.


La grammatica minima corrispondente al linguaggio L6 possiede 3 simbolinon terminali.

generazione= 0 fitmedia= 0.084830 bestFit= 0.866667generazione= 1 fitmedia= 0.275452 bestFit= 0.933333generazione= 2 fitmedia= 0.374044 bestFit= 0.933333

11Considereremo uguali due grammatiche che di!eriscono solo per il nome dei simbolinon terminali


generazione= 3 fitmedia= 0.424415 bestFit= 0.933333generazione= 4 fitmedia= 0.457763 bestFit= 0.933333generazione= 5 fitmedia= 0.460993 bestFit= 0.933333generazione= 6 fitmedia= 0.488845 bestFit= 1.000000A->0E A->1C B->0A B->1D B->0 C->1E C->0 D->1E D->0 E->0B E->1Dgenerazione= 7 fitmedia= 0.504060 bestFit= 1.000000A->0E A->1C B->0A B->1D B->0 C->1E C->0 D->1E D->0 E->0B E->1Dgenerazione= 8 fitmedia= 0.527971 bestFit= 1.000000A->0E A->1C B->0A B->1D B->0 C->1E C->0 D->1E D->0 E->0B E->1Dgenerazione= 9 fitmedia= 0.552948 bestFit= 1.000000A->0E A->1C B->0A B->1D B->0 C->1E C->0 D->1E D->0 E->0B E->1Dgenerazione= 10 fitmedia= 0.553467 bestFit= 1.000000A->0E A->1C B->0A B->1D B->0 C->1E C->0 D->1E D->0 E->0B E->1Dgenerazione= 11 fitmedia= 0.575052 bestFit= 1.000000A->0E A->1C B->0A B->1D B->0 C->1E C->0 D->1E D->0 E->0B E->1Dgenerazione= 12 fitmedia= 0.569630 bestFit= 1.000000A->0E A->1C B->0A B->1D B->0 C->1E C->0 D->1E D->0 E->0B E->1Dgenerazione= 13 fitmedia= 0.553260 bestFit= 1.000000A->0E A->1C B->0A B->1B B->0 C->1E C->0 E->0Bgenerazione= 14 fitmedia= 0.572149 bestFit= 1.000000A->0E A->1C B->0A B->1B B->0 C->1E C->0 E->0B...

L’algoritmo genetico ha trovato una grammatica compatibile con il sam-ple di ingresso nella popolazione della generazione 6: come si puo vederequesta grammatica ha 5 simboli non terminali. L’evoluzione continua, e al-la generazione 13 viene trovata una soluzione che fa uso di 4 simboli nonterminali.

...generazione= 121 fitmedia= 0.629585 bestFit= 1.000000A->0E A->1C B->0A B->1B B->0 C->1E C->0 E->0Bgenerazione= 122 fitmedia= 0.587319 bestFit= 1.000000A->0E A->1C B->0A B->1B B->0 C->1E C->0 E->0Bgenerazione= 123 fitmedia= 0.580874 bestFit= 1.000000A->0E A->1C C->0A C->1E C->0 E->0C E->1Agenerazione= 124 fitmedia= 0.599778 bestFit= 1.000000A->0E A->1C C->0A C->1E C->0 E->0C E->1Agenerazione= 125 fitmedia= 0.604385 bestFit= 1.000000A->0E A->1C C->0A C->1E C->0 E->0C E->1A...

4.5 Secondo test 107

Nella generazione 123 compare una grammatica che fa uso di tre simboliterminali: questa grammatica risultera la migliore fino al termine della prova.

...generazione= 999 fitmedia= 0.620815 bestFit= 1.000000A->0E A->1C C->0A C->1E C->0 E->0C E->1Agenerazione= 1000 fitmedia= 0.626681 bestFit= 1.000000A->0E A->1C C->0A C->1E C->0 E->0C E->1A

Come si puo osservare la grammatica ottenuta non e uguale a quella corri-spondente al linguaggio L6 (vedi paragrafo 4.2): la di"erenza e nella regoladi produzione E + 1, non necessaria per generare le stringhe del sample S+.Se si calcolano i valori di V+ e V" per la soluzione trovata, otteniamo:

V+ = 49.555 V" = 100.00

La mancanza della regola di produzione E + 1, non permette di generarele stringhe di L6 che terminano con il carattere 1: il valore di V+ confermaquesta considerazione.

4.5 Secondo test

Il secondo test e stato realizzato con l’intenzione di paragonare piu accu-ratamente l’azione degli operatori genetici di crossing–over e traslocazione.Particolarmente si era interessati a confrontare il modo in cui questi due ope-ratori influenzano la velocita dell’algoritmo genetico realizzato, nel trovareuna grammatica compatibile con un sample S = S+ ! S". Le prove sonostate eseguite usando solo linguaggi 3 5 e 7 della tabella 4.1. Il numero distati degli automi corrispondenti ai tre linguaggi e ugule a 4: sono quindi gliautomi piu complessi tra quelli originariamente definiti da Tomita.

4.5.1 Dati secondo test

I dati usati nel secondo test sono stati ottenuti modificando i sample origi-nariamente usati da Tomita in [Tom82], escludendo dagli esempi la stringanulla. Questi insiemi di esempi positivi e negativi si riferiscono quindi soloai primi sette linguaggi della tabella 4.1. Questi dati sono stati prelevati daun lavoro di Pollack [BP97], in cui non viene specificato la modalita con cuiquesti insiemi di esempi labellati sono stati creati. Per verificare le caratte-ristiche di questi insiemi, si e controllato, usando un programma realizzatoappositamente, che l’insiemi di esempi positivi S+ fossero strutturalmentecompleti per l’automa finito minimo corrispondente al linguaggio.


Diversamente dai dati usati nel primo test, ad ogni linguaggio corrispondeun solo insieme di esempi labellati.

4.5.2 Protocollo di sperimentazione del secondo test

Relativamente ai linguaggi L3, L5 e L7 sono state eseguite 10 prove sull’unicosample disponibile, con diversi valori dei semi per l’inizializzazione della ge-nerazione iniziale. Similmente al test precedente, i risultati finali sono statiottenuti mediando i risultati generati dall’algoritmo in ogni singola prova.

In questo caso i risultati consistono nel valore della migliore grammaticapresente nella popolazione (bestFit), per ognuna delle mille generazioni.

Anche in questo test sono state provate le tre forme dell’algoritmo geneticorealizzato: ogni prova e caratterizzata da diversi valori per le probabilitadegli operatori di crossing–over e traslocazione. I valori usati per Pc e Ptsono quelli riportati in tabella 4.2, mentre come nel primo test l’operatore dimutazione agisce sempre in background con valore Pm=0.05.

4.5.3 Risultati del secondo test

Osservando i grafici in contenuti nelle figure 4.5(a) 4.5(b) 4.6 si puo riscon-trare che l’operatore di traslocazione non solo conduce a soluzioni qualitati-vamente migliore rispetto all’operatore di crossing–over, sul limite delle millegenerazioni, ma e anche piu veloce, cioe mediamente permette di arrivare piuvelocemente ad una grammatica regolare che accetta S+ e rifiuta S".

Per i grafici relativi ai linguaggio 3 e 5 di Tomita valgono le stesse con-siderazioni: si nota che nelle prove e"ettuate con AG–$ (Pc=0.33 Pt=0.33)si arriva mediamente ad una soluzione circa alla quarantesima generazione.Le prove e"ettute con AG–& (Pc=0.00 Pt=0.66) mostra12 che mediamentesi trova una soluzione sempre prima della cinquantesima generazione. Infinele prove e"ettuate con AG–# (Pc=0.66 Pt=0.00), mostrano che mediamentenon si giunge ad una soluzione nelle prime cento generazioni.

Nel grafico relativo al linguaggio 5 di Tomita si nota che in nessuna delletre forme dell’algoritmo genetico si arriva mediamente ad una soluzione nellemille generazioni. Si puo pero distinguere mediamente un valore piu altonelle prove e"ettuate con AG–&, ed un valore mediamente piu basso nelleprove e"ettuate con AG–#.

E importante sottolineare che i grafici sull’andamento del best fit sono cal-colati rispetto ad una generica grammatica compatibile con S, e non rispettoalla grammatica minima che genera il linguaggio.

12Un operatore che ha probabilita di azione 0 non viene mai adoperato dall’algoritmogenetico.

4.5 Secondo test 109

0.4

0.5

0.6

0.7

0.8

0.9

1

0 50 100

Best

Fit

Generazione

Tomita 3

Pc=0.00 Pt=0.66Pc=0.33 Pt=0.33Pc=0.66 Pt=0.00

(a) Linguaggio 3 di Tomita.

0.55

0.6

0.65

0.7

0.75

0.8

0.85

0.9

0.95

1

0 50 100

Best

Fit

Generazione

Tomita 7

Pc=0.00 Pt=0.66Pc=0.33 Pt=0.33Pc=0.66 Pt=0.00

(b) Linguaggio 7 di Tomita.

Figura 4.5: Risultati secondo test per il linguaggi L3 e L7


0.6

0.65

0.7

0.75

0.8

0.85

0.9

0.95

1

0 100 200 300 400 500 600 700 800 900 1000

Best

Fit

Generazione

Tomita 5

Pc=0.00 Pt=0.66Pc=0.33 Pt=0.33Pc=0.66 Pt=0.00

Figura 4.6: Linguaggio 5 di Tomita.

4.6 Limiti dell’algoritmo genetico realizzato

Si e provato ad aumentare drasticamente la complessita del linguaggio dainferire ponendo la lunghezza del cromosoma a 252 caratteri, e fornendo iningresso i dati relativi ad un linguaggio accettabile da un automa finito a 63stati. I dati usati sono descritti in [LPP98].

Queste prove sono state interrotte a causa dell’enorme sforzo computazio-nale richiesto: l’aumento della lunghezza del cromosoma provoca un rallen-tamento significativo della velocita dell’algoritmo. Inoltre nelle poche gene-razione analizzate (meno di 100) si e notato che i valori del migliore elementodella popolazione per ogni generazione era estremamente basso: l’aumentonotevole dello spazio delle possibili grammatiche richiederebbe una dimen-sione della popolazione nettamente superiore al valore usato nelle prove, cioe500.

Questi fatti sembrano confermare le considerazioni fatte in [LPP98], cioeche gli algoritmi genetici siano utilizzabili nell’inferenza grammaticale rego-lare solo per linguaggi con automi corrispondenti relativamente piccoli.

4.7 Considerazioni conclusive 111

0q 1q 2q0 1

0Figura 4.7: Automa finito deterministico

4.7 Considerazioni conclusive

I dati usati nel primo test sono strutturalmente completi per il minimo DFAche accetta il linguaggio. Cioe

1. Ogni transizione e usata almeno una volta nell’accettare almeno unesempio positivo.

2. Ogni stato finale accetta almeno una stringa degli esempi positivi.

Queste sembrano essere le condizioni minime a!nche gli esempi siano abba-stanza significativi del linguaggio relativo al minimo DFA. A nostra conoscen-za non esiste una forma equivalente che definisca la completezza strutturaledi un sample rispetto ad un grammatica regolare. E lecito sospettare che del-le condizioni su!cienti per inferire il minimo DFA da un insieme di esempilabellati, siano su!cienti anche per inferire la piu piccola grammatica rego-lare. Rispetto all’automa di figura 4.7 il sample positivo S+ = {010, 01} estrutturalmente completo. Se si considera invece la grammatica

1) A + 0B 5) C + 0B2) A + 0 6) C + 03) B + 1C4) B + 1

che genera il linguaggio corrispondente all’automa, si vede che l’insieme S+

non e una descrizione su!cientemente buona per la grammatica: le regole 2e 5 non vengono usate nella derivazione. Ci sono quindi delle di"erenze tral’inferenza DFA e l’inferenza di una grammatica regolare, nonostante esistaun algoritmo e!ciente che porti dall’automa alla grammatica e viceversa.

Considerando queste di"erenze si potrebbe proporre una definizione for-male di insieme di esempi positivi strutturalmente completo per le gramma-tiche


Definizione 4.1. Un insieme di esempi positivi S+ e strutturalmente com-pleto per la grammatica G se nel generare tutte le stringhe di S+ si usanotutte le regole di G.

Sembra interessante notare che questa definizione si applica a tutte leclassi di grammatiche nella gerarchia di Chomsky. Controllando i dati fornitida Dupont ci si accorge che dei 130 sample usati nel primo test, 13 di questinon soddisfano la definizione 4.1. Precisamente

• Per il linguaggio L3 3 sample non rispettano la definizione 4.1.

• Per i linguaggi L4, L6, L7, L14, 2 sample non rispettano la definizio-ne 4.1.

• Per i linguaggi L10, L11 1 sample non rispettano la definizione 4.1.

Se si eliminano questi sample dalle medie che riassumono i risultati siottengono dei valori nettamente superiori (vedi tabella 4.8).


L1 100.000 100.000 100.000 100.000 100.000L2 100.000 100.000 100.000 100.000 100.000L3 98.903 100.000 99.451 100.000 100.00L4 83.824 100.000 91.912 100.000 100.000L5 77.973 89.495 83.734 93.860 90.842L6 100.000 100.00 100.000 100.000 100.000L7 93.477 95.855 94.666 100.000 100.000L8 100.000 100.000 100.000 100.000 100.000L10 100.000 99.884 99.942 99.954 99.834L11 85.145 89.174 87.160 96.466 90.835L12 100.0 100.000 100.000 100.000 100.000L13 92.976 99.535 96.255 100.000 100.000L14 94.783 100.000 97.391 100.000 100.000

media 94.4 98.0 96.2 99.3 98.6

Tabella 4.8: Risultati dell’algoritmo genetico AG–& relativi al primo test,escludendo i sample che non soddisfano la definizione 4.1.

I risultati ottenuti possono avere un certo interesse nel campo dell’in-ferenza grammaticale, dove si considera equivalente il formalismo dei DFAe quello delle grammatiche lineari: in questo lavoro si e sperimentalmenteverificato che invece sembrano esserci delle di"erenze.

4.7 Considerazioni conclusive 113

Inoltre il confronto tra le prestazioni degli operatori genetici realizzati sipone come un nuovo indizio sperimentale nell’indagine sull’importanza del-l’operatore di crossing–over, all’interno degli studi sugli algoritmi evolutivi.

Appendice A

Preliminari

A.1 Teoria della calcolabilita

Turing propose alla fine degli anni ’30 un semplice modello teorico di mac-china per eseguire calcoli simbolici che permetteva di studiare la teoria dellefunzioni algoritmiche, svincolandosi dai problemi inerenti la definizione stes-sa di algoritmo. Basandosi su questo strumento, necessario per catturarepienamente il concetto di e!ettivita, nacque allora un filone di studi che sioccupa di indagare i limiti di cio che e meccanicamente calcolabile.La macchina di Turing (MdT) e un‘automa finito dotato di un nastro unidi-mensionale diviso in celle, potenzialmente infinito, su cui e possibile leggere,scrivere, spostarsi di una cella. Ad ogni istante la macchina legge attraversouna testina di lettura il simbolo presente nella cella selezionata del nastro:in funzione del simbolo letto e dello stato in cui si trova e quindi del pro-prio programma, la macchina cambia stato e puo sovrascrivere il simbolopresente nella cella, spostarsi nella cella immediatamente a destra o a sini-stra di quella attuale. Se si indicano, gli stati interni della macchina con isimboli q1, q2, . . . , qn, i simboli che possono essere letti e scritti sul nastrocon S1, S2, . . . , Sm, azioni di spostarsi a destra e a sinistra con R e L, si puoscrivere il programma di una MdT come un insieme di quadruple nella forma:

qiSjSkql qiSjRql qiSjLql

Si ha che:

• Il primo carattere indica lo stato interno in cui si trova la macchinaquando legge il simbolo del nastro.

• Il secondo carattere indica il simbolo letto dal nastro.

115

116 Preliminari

• Il terzo carattere indica l’azione che la testina deve eseguire.

• Il quarto carattere indica lo stato interno in cui si trovera la la macchinadopo aver eseguito l’operazione.

E ora chiara l’estrema duttilita di questo modello: si puo pensare al-la MdT sia come insieme di quadruple (definizione formale), sia come adun meccanismo dotato di un nastro potenzialmente infinito (definizione fi-sica). Per fare in modo che una MdT possa calcolare funzioni numerichesi introduce in ingresso una codifica unaria dei numeri naturali. Con B(blank) si indichera il simbolo di cella vuota. Ogni numero n # N verracodificato in ingresso come una successione di n + 1 ’1’; si indichera questacodifica con n (ad esempio 4 =11111).Una k–pla di interi verra indicata con(n1, n2, ..., nk) = n1Bn2B...Bnk. In uscita il risultato e codificato come ilnumero di ’1’ presenti sul nastro. In base a queste codifiche in ingresso e inuscita, posso associare ad una MdT una funzione n–aria:

Definizione A.1. Sia Z una macchina di Turing. Allora per ogni n, asso-ciamo a Z una funzione n–aria

$nZ(x1, x2, ..., xn)

nel modo seguente:Per ogni n–upla (m1, m2, ..., mn) facciamo partire la macchina di Turing

Z nello stato iniziale sul nastro (m1, m2, ..., mn) e distinguiamo i due casi:

1. Z termina la sua computazione e allora poniamo$n

Z(m1, m2, ..., mn) =numero di 1 presenti sul nastro al termine dellacomputazione

2. Z non termina la sua computazione e allora $nZ(m1, m2, ..., mn) rimane

indeterminata.

Definizione A.2. Una funzione n–aria f(x1, ..., xn) e computabile se esi-ste una macchina di Turing Z tale che

f(x1, ..., xn) = $nZ(x1, ..., xn)

.

A.1 Teoria della calcolabilita 117

La godelizzazione e una codifica che ci permette di associare iniettivamen-te dei numeri a delle stringhe: questo consente di poter assegnare un numeroad una MdT. Un procedimento come questo che permette una numerazionee"ettiva delle MdT, consente a queste ultime di parlare di se stesse. Partendodalla godelizzazione si puo dimostrare l’esistenza di una MdT universale Uche puo calcolare qualsiasi funzione unaria nel modo seguente: se z0 e il nu-mero di Godel di Z0 $U (2)(z0, x) = $Z0(x) Parallelamente alle MdT un’altradefinizione delle funzioni e"ettivamente calcolabili e stata formalizzata. Unaprima classe di funzioni calcolabili e quella delle funzioni primitive ricorsive.

Definizione A.3. L’operazione di Primitiva Ricorsione associa a duefunzioni totali f(x1, ..., xn) e g(x1, ..., xn, xn+1, xn+2) la funzione h(x1, ..., xn, xn+1)dove

h(0, x2, ..., xn+1) = f(x2, ..., xn+1)

h(z + 1, x2, ..., xn+1) = g(z, h(z, x2, ..., xn+1), x2, ..., xn+1).

Ora possiamo definire la classe delle funzioni primitive ricosive:

Definizione A.4. Una funzione e Primitiva Ricorsiva se si puo ottenerecon un numero finito di applicazioni delle operazioni di composizione e diricorsione primitiva a partire dalle funzioni

1. La funzione successore S(x) = x + 1

2. La funzione costantemente nulla N(x) = 0

3. La funzione identita Uni (x1, ..., xn) = xi, 1 & i & n.

Le funzioni primitive ricorsive pur contenendo la maggior parte delle fun-zioni numeriche conosciute, non contengono tutte le fuzioni e"ettivamentecalcolabili: Ackermann espose un controesempio che dimostrava questo fatto.Bisogna introdurre un nuovo operatore per poter estendere la classe:

Definizione A.5. L’operazione di minimalizzazione associa ad ogni fun-zione totale f(y, x1, . . . , xn) la funzione h(x1, . . . , xn), il cui valore per unadata n–upla x1, . . . , xn e il piu piccolo valore di y, se ne esiste uno, per cuif(y, x1, . . . , xn) = 0, e che e indefinita se un tale y non esiste.

Quindi fu definita una nuova classe di funzioni, la classe delle funzioniparziali ricorsive:

118 Preliminari

Definizione A.6. Una funzione e parziale ricorsiva se puo essere ottenutacon un numero finito di applicazioni delle operazioni di composizione e diminimalizzazione a partire dalle funzioni della seguente lista:

1. La funzione successore S(x) = x + 1

2. La funzione identita Uni (x1, ..., xn) = xi, 1 & i & n.

3. La funzione somma x + y

4. La funzione sottrazione modificata x%y cosı definita:

x%y =

&x% y se x ) y

0 se x < y

5. La funzione prodotto x4 y.

Una funzione parziale ricorsiva totale e detta ricorsiva. Si puo dimostrareche le fuzioni parziali ricorsive coincidono con le fuzioni Turing–computabili.Una conseguenza immediata di questo e che le funzioni parziali ricorsive am-mettono una numerazione e"ettiva di riflesso alla numerazione delle MdT,basata sulla procedura di godelizzazione. Inoltre la stessa godelizzazione per-mette alle funzioni parziali ricosive di essere anche funzioni simboliche. L’u-niversalita del calcolo di una MdT e riassunta nella famosa Tesi di Church–Turing che ipotizza che tutto cio che si puo e"ettivamente calcolare e anchecalcolabile da una MdT; e chiaro che una dimostrazione di questa congetturae impossibile a causa della sfugevolezza del concetto di algoritmo, ma e no-tevole che tutti i tentativi di confutare la tesi di Church–Turing sono falliti.Con fuzione caratteristica di un insieme S si intende la funzione:

Cs(x) =

&1 se x # S

0 se x /# S

Definizione A.7. Un insieme e detto ricorsivo se la propria funzione ca-ratteristica e ricorsiva.

Definizione A.8. Un insieme e detto ricorsivamente numerabile se el’insieme dei valori di una funzione parziale ricorsiva.

Per l’e"etivita delle fuzioni ricosive e dal fatto che sono funzioni tota-li si puo sempre rispondere alla domanda sull’appartenenza di un genericoelemento ad un insieme ricorsivo. La stessa cosa non e vera per gli insiemiricorsivamente numerabili.

A.1 Teoria della calcolabilita 119

Teorema A.9. Esistono insiemi ricorsivamente numerabili che non sonoricorsivi.

La dimostrazione di questo teorema si basa sulla costruzione di un insie-me, detto insieme della fermata, che contiene i numeri di Godel delle MdTche si fermano su i propri numeri di Godel: questo insieme e ricorsivamentenumerabile ma non ricorsivo [Dav58]. A partire dall’insieme della fermata epossibile costruire una classifica che individua vari gradi di indecidibilita cheprende il nome di gerarchia di Kleene. L’insieme dei problemi che hanno ungrado di indecidibilita minore uguale all’insieme della fermata si ottengonoanche attraverso l’applicazione di un operatore detto di limite:

Definizione A.10. Se g e una funzione totale di k + 1 variabili, alloralimn g(x1, . . . , xk, n) = a se -n0 # N : $n > n0 g(x1, . . . , xk, n) = a.

lim e quindi un operatore che associa ad ogni funzione totale g di k + 1variabili una funzione parziale di k variabili f(x1, . . . , xk) tale che

f(x1, . . . , xk) =

&limn g(x1, . . . , xk, n) se tale limite esiste;

indefinita altrimenti

Da ora in poi scriveremo f(x1, . . . , xk) = limn g(x1, . . . , xk, n). Se ap-plicando l’operazione di limite otteniamo di nuovo una funzione totale ilprocesso puo essere iterato e si puo ottenere:

Definizione A.11. limk g(x1, . . . , xm, nk, . . . , n1) =

limnk

limnk!1

. . . limn1

g(x1, . . . , xm, nk, . . . , n1)

sotto la condizione che ogni lim sia applicato ad una funzione totale.

Definizione A.12. Se una funzione e esprimibile come il k–esimo limite diuna funzione totale ricorsiva diciamo che e una funzione k–limite ricorsiva.

Si puo dimostrare [CMT75] che la classe delle funzioni parziali la cuicalcolapbilita e riconducibile al problema della fermata e inclusa strettamentenell’insieme delle funzioni 1–limite ricorsive.

120 Preliminari

A.2 Linguaggi formali

Con alfabeto si indichera un insiema finito di simboli distinti # = {a1, . . . , an}.Con il termine stringa o parola si intende una sequenza finita di simboli giu-stapposti. Con ' o ) verra indicata la stringa vuota, cioe composta da zerosimboli mentre l’insieme di tutte le stringhe costruibili sull’alfabeto # verraindicato con #!; con #+ si inichera l’insieme #! % ). Una stringa & si diceuna concatenazione delle stringhe # e $ e si scrive & = # · $ se & si ottienegiustapponendo $ sulla destra di #. Se & = # ·$ # e $ sono dette, rispettiva-mente, prefisso e su!sso di &; si dice prefisso o su!sso proprio se accade che# 1= & o $ 1= &. Con il simbolo | x | si indichera la lunghezza della stringa x,ovvero il numero di simboli dell’alfabeto contenuti in x. Una relazione d’ordi-ne sui simboli dell’alfabeto si riflette in una relazione d’ordine sulle stringhe:se l’ordine sull’alfabeto # = a1, . . . , an e a1 < a2 < . . . < an si inducel’ordine ' < a1 < an < a1a1 < a1an < anan < a1a1a1 < . . . detto standard oquasi–lessicografico su #!.

Definizione A.13. Un linguaggio formale o piu semplicemente un lin-guaggio, e un qualsiasi sottoinsieme di #!.

Le proprieta di decidibilita di un linguaggio formale sono contenute nelleseguenti definizioni:

Definizione A.14. Un linguaggio L viene detto accettabile, o ricorsiva-mente numerabile, se esiste una una MdT, che $ stringa x # #! restituisceil valore 1 se x # L, restituisce 0 oppure non si ferma se x /# L.

Definizione A.15. Un liguaggio L viene detto decidibile, o ricorsivo, seesiste una MdT che restituisce il valore 1 se x # L e restituisce 0 se x /# L.

Definizione A.16. Un linguaggio viene detto generabile se esiste una MdTche restituisce tutte le stringhe di L in un qualsiasi ordine.

Chiamiamo LA l’insieme dei linguaggi accettabili, LD l’insieme dei lin-guaggi decidibili e LG l’insieme dei linguaggi generabili. Si puo dimostrareche LA coincide con LG, che LD coincide con il sottoinsieme di LG dei lin-guaggi generabili in ordine standard, e che LA non coincide con LD. Questirisultati sono riguardabili come un caso specifico delle relazioni tra insiemistudiate in teoria della calcolabilita. E la procedura di godelizzazione checi permette sempre di ricondurre insiemi simbolici ad insiemi numerici. Perpotere descrivere in maniera e"ettiva le proprieta di linguaggi di cardinalitainfinita, e necessario introdurre il concetto di grammatica. Una grammaticasi puo informalmente descrivere come un insieme di regole di riscrittura chepermettono, partendo da un simbolo iniziale, di ottenere tutte le stringhe diun linguaggio.

A.2 Linguaggi formali 121

Definizione A.17. Una grammatica generativa di Chomsky e unaquadrupla

G = (#, V, S, P )

dove:

# e un alfabeto, detto insieme dei simboli terminali

V e un alfabeto disgiunto da #, detto insieme dei simboli non terminali

S e un particolare simbolo di V detto simbolo di start della grammatica

P e un insieme finito di regole di produzione, cioe di regole di riscritturaaventi la forma

$+ & con $ # (# ! V )!V (# ! V )! e & # (# ! V )!

Data la grammatica G si dice che la stringa $2 # (#!V )! e immediata-

mente deducibile dalla stringa $1 # (#!V )! e si scrive $1G" $2 se accade

che $1 = '1('2 e $2 = '1&'2 e ( + & e una regola di produzione per G.

ConG!" si indica la chiusura riflessiva e transitiva di

G". Si ha quindi che se

$1G!" $2 esiste una sequenza )1,)2, . . . ,)n con )j # ($ ! V )! $j # 1 . . . n

tale che $1 = )1, $2 = )n e )iG" )i+1 $i # 1 . . . n% 1.

Definizione A.18. Il linguaggio generato da una grammatica G e l’insiemedelle stringhe di #! generabili a partire dal simbolo S:

L(G) = {x # #! : SG!" x}

Chomsky [Cho57] costruı una gerarchia di grammatiche generative carat-terizzando la forma delle regole di produzione. Simmetricamente alla gerar-chia di grammatiche si definisce una gerarchia di automi che possono accet-tare i linguaggi associati alle grammatiche. E significativo che una maggiorepermissivita sulla forma delle regole di produzione si riflette in una maggiorepotenza dell’automa corrispondente. Si possono individuare quattro classi:

Grammatiche di tipo zero Sono la classe piu generale di grammatiche;nessuna restrizione viene imposta alle regole di produzione. I linguaggigenerati da queste grammatiche sono i linguaggi ricorsivamente nu-merabili, ovvero per le definizioni precedenti il linguaggi accettabili egenerabili. La macchina che accetta questi linguaggi e la MdT, ovveroper la tesi di Church–turing, la piu generale macchina di calcolo.

122 Preliminari

Grammatiche di tipo uno o Context Sensitive Le regole di produzio-ne sono della forma:#1A#2 + #1$#2 con #1,#2,$ # (# ! V )! e A # V .I linguaggi generati da queste grammatiche prendono il nome di lin-guaggi Context Sensitive. La macchina che accetta questi tipi di lin-guaggi e la Linear Bounded Automata; questa e una MdT che agisce inmaniera non determinisrica e in cui la lunghezza del nastro disponibilee limitata da una funzione lineare della grandezza dell’input.

Grammatiche di tipo due o Context Free Le regole di produzione han-no la forma: A + $ con A # V e $ # (#!V )!. I linguaggi di generatida grammatiche Context Free vengono chiamati di riflesso linguaggicontext free. La macchina relativa a questo tipo di linguaggi e il Pu-sh Down Automata: un’automa finito dotato di un nastro su cui sipuo solo leggere, e di un dispositivo chiamato pila che consente di me-morizzare informazioni, permettendo l’accesso solo all’ultimo elementomemorizzato.

Grammatiche di tipo tre o lineari Le regole di produzione hanno la for-ma A + %B oppure A + B% con A # V, B # (V ! {'}) e % # #+. Ilinguaggi generati da queste grammatiche sono detti linguaggi regolario insiemi regolari. La macchina relativa a questa classe e una macchinachiamta Automa Finito che puo leggere un carattere da un nastro dilettura e variare lo stato in cui si trova a seconda del simbolo letto.

Si puo dimostrare che la classe dei linguaggi context–sensitive inclusa propria-mente nell’insieme di tutti i linguaggi ricorsivi: esistono linguaggi ricorsiviche non sono context sensitive.

A.3 Automi finiti

Formalmente un automa finito deterministico (DFA) D e una quintupla:

D = (#, Q, ", q0, F )

dove:

# e un alfabeto.

Q e un insieme finito di simboli chiamato insieme degli stati interni di D.

" e una funzione definita Q4 # detta funzione prossimo stato.

A.3 Automi finiti 123

q0 e un elemento di Q detto stato iniziale.

F e un sottoinsieme di Q detto insieme degli stati finali.

Un automa finito deterministico e il modello di un sistema meccanico costi-tuito da un controllo finito dotato di una testina di lettura e da un nastro dilettura; il nastro e diviso in celle ognuna in grado di contenere esattamenteun carattere. La funzione del nastro e di contenere la stringa in ingresso.L’automa parte dallo stato iniziale q0 leggendo il primo carattere a1 dellaparola di ingresso, passa nello stato "(q0, a1), se questo valore e definito, esi sposta sulla prossima cella a destra del nastro; questo processo viene ite-rato fino al termine della stringa o fino che la funzione "(qi, aj) risulta perla prima volta indefinita. Un automa finito in cui la funzione " e definita$q # Q e $ai # # e chiamato completo. Una stringa si dira accettata dal-l’automa D se dopo aver letto tutta la stringa, l’automa si trova in uno deglistati finali. Se definiamo la funzione ." come:

."(q, )) = q $q # Q

."(q, a1 . . . an"1an) = "(."(q, a1 . . . an"1), an)

Il linguaggio accettato da un automa finito deterministico D = (#, Q, ", q0, F )si puo formalmente definire come:

L(D) = {x # #! : ."(q, x) # F}

e prende il nome di insieme regolare o linguaggio regolare. Ogni automafinito ammette una rappresentazione grafica sotto forma di grafo. Ad esempiol’automa definito da:

# = {0, 1} Q = {q0, q1} F = {q0}

"(q0, 1) = q1 "(q1, 0) = q0

che accetta tutte le stringhe composte dalla sottostringa 10 ripetuta unnumero qualsiasi di volte, e rappresentato dal grafo in figura A.1:

• Gli stati sono rappresentati da cerchi.

• La funzione "(qi, a) = qj e definita con una freccia che parte da qi earriva a qj .

124 Preliminari

q0 1q1

0Figura A.1: Grafo di un DFA

• Gli stati finali sono contrassegnati con un cerchio piu piccolo concen-trico all’interno dello stato.

Un automa finito non deterministico (NDFA) e un automa in cui la " euna funzione non deterministica, cioe e possibile eseguire diverse transizionialla lettura di un simbolo. Si puo dimostrare che preso un generico NDFAND esiste un DFA D tale che L(ND) = L(D). Nel seguito per automafinito intenderemo sempre automa finito deterministico. Gli insiemi regolaripossono essere denotati anche attraverso la valutazione di una espressioneregolare. Dato un alfabeto # = {a1, . . . , an} si definisce un nuovo alfabetoA = {a1, . . . , an, ),(, (, ), +, 3}. Le espressioni regolari su # si definisconoinduttivamente come:

1. Sono espressioni regolari: ),(, ai con 1 & i & n.

2. Se r e s sono espressioni regolari lo sono anche: (r · s), (r + s), (r)!.

La valutazione V di una espressione regolare e una funzione cosı definita:V : {espressioni regolari}+ 2#"

1. V(() = ( V()) = {)} V(ai) = {ai}

2. V(r · s) = V(r) · V(s) V(r + s) = V(r) ! V(s)

V(r)! = {)} ! V(r) ! V(r · r) ! V(r · (r · r)) ! . . . =%5

n=0V(rn)

In questa definizione si e implicitamente definito r0 = {)} e ri = r · (ri"1);spesso inoltre, come e in uso in aritmetica per il simbolo di moltiplicazione, ilsimbolo · viene sottointeso. Si puo dimostrare che i linguaggi che si ottengonoattraverso la valutazione di una espressione regolare coincidono con i l’insie-me di tutti i linguaggi regolari. Ad esempio l’espressione regolare che valutail linguaggio accettato dall’automa di figura A.1 e (01)!. Preso un automafinito D e sempre possibile decidere e"ettivamente se L(D) = ( oppure se la

A.3 Automi finiti 125

cardinalita di L(D) e finita o infinita. Inoltre presi due automi finiti D1 e D2,e sempre possibile decidere se L(D1) 8 L(D2) o se L(D1) * L(D2). Questeproprieta di decidibilita non sono comuni a tutte le classi della gerarchia diChomsky. In particolare il fatto che sia decidibile se due automi accettano lostesso linguaggio, permette l’esistenza di una procedura e"ettiva che dato ungenerico automa D restituisce un automa D che accetta lo stesso linguaggio,L(D) * L(D), ed inoltre ha il numero minimo possibile di stati (teorema diNerode); l’automa D viene chiamato indistintamente automa minimo, au-toma ridotto o automa canonico. Un generico linguaggio regolare e sempregenerabile da una grammatica lineare. Se si escludono tutti i linguaggi re-golari che contengono la stringa vuota, le grammatiche lineari si ammettonouna forma normale:

Definizione A.19. Una grammatica regolare e una grammatica lineareche possiede regole di produzione solo nella forma: A + aiB A + aj oppureA + Bai A + aj dove ai, aj # # A, B # VNel primo caso la grammtica si dira regolare destra, nel secondo casoregolare sinistra.

Si dimostra che ogni linguaggio regolare a cui non appartiene la strin-ga vuota puo essere generato da una grammatica lineare destra e da unagrammatica lineare sinistra [HU79].

Bibliografia

[Ang78] D. Angluin. On the complexity of minimum inference of regularsets. Information and Control, 39(3):337–350, December 1978.

[Ang87] D. Angluin. Learning regular sets from queries and counterexamples.Information and Computation, 75:87–106, 1987.

[Ant89] J. Antonisse. A new interpretation of schema notation that overturnsthe binary encoding constraint. In J. D. Scha"er, editor, Procee-ding of the Third Internetional Conference on Genetic Algorithms.Morgan Kaufmann, 1989.

[AS83] D. Angluin and C. H. Smith. Inductive inference: Theory andmethods. Computing Surveys, 15:237–269, September 1983.

[BB75] L. Blum and M. Blum. Toward a mathematical theory of inductiveinference. Information and Control, 28:125–155, 1975.

[BP97] A. D. Blair and J.B. Pollack. Analysis of dynamical recognizers.Neural Computation, 9(5):1127–1142, 1997.

[Car71] R. Carnap. Analiticita, significanza, induzione. Il Mulino, 1971.Parte Terza.

[Cho57] N. Chomsky. Syntactic Structures. Mouton and Co, The Hague,1957.

[CLI93] CLIN. Genetic Grammatical Inference, Groningen, 1993.

[CMT75] G. Criscuolo, E. Minicozzi, and G. Trautteur. Limiting recur-sion and arithmetic hierarchy. Reveu Francaise d’Automatique,Informatique et Recerche Operationelle, pages 5–12, 1975.

[CS83] J. Case and C. Smith. Comparison of identification criteriafor machine inductive inference. Theoretical Computer Science,25:193–220, 1983.

127

128 BIBLIOGRAFIA

[Dav58] M. Davis. Computability & Unsolvability. McGraw–Hill, NEWYORK, 1958.

[Dav63] P. J. Davis. Interpolation and Approximation. Blaisdell PublshingCompany, 1963.

[Den] F. Denis. Learning regular languages from simple positive examples.To Appear.

[Dup94] P. Dupont. Regular grammatical inference from positive and ne-gative samples by genetic search: the GIG method. In Gramma-tical Inference and Applications, number 862 in Lectures Notes inArtificial Intelligence, pages 236–245. ICGI, Springer–Verlag, 1994.

[FB75] K. S. Fu and T. L. Booth. Grammatical inference: Introductionand survey (part 1). Transaction on Systems, Man and Cybernetics,5:85–111, 1975.

[FITC00] I. De Falco, A. Iazzetta, E. Tarantino, and A. Della Cioppa. Onbiologically inspired mutations: the traslocation. In Proceedings ofGECCO 2000, pages 70–77, Las Vegas, Nevada, July 2000. Late–breaking papers.

[FOW66] L. J. Fogel, A. J. Owens, and M. J. Walsh. Artificial IntelligenceThrough Simulated Evolution. Wiley Publishing, New York, 1966.

[Gol67] B. M. Gold. Language identification in the limit. InformationControl, 10:447–474, 1967.

[Gol78] B. M. Gold. Complexity of automation identification from givendata. Information Control, 37:302–320, 1978.

[Gol89] D. Goldberg. Genetic Algorithms in Search, Optmization andMachine Learning. Addison-Wesley, 1989.

[Gol90] D. E. Goldberg. Real–coded genetic algorithms, virtual alphabets,and blocking. Complex Systems, 5(2):139–168, 1990.

[Hol75] J. H. Holland. Adaption in Natural and Artificial Systems.University of Michigan Press, Ann Arbor, 1975.

[HP00] V. Honavar and R. Parekh. Grammar inference, automata induction,and language acquisition. In Sommers Dale, Moisl, editor, Handbookof Natural Language Processing. Dekker M., 2000. In Press.

BIBLIOGRAFIA 129

[HU79] J. Hopcroft and J. Ullman. Introduction to Automata Theory,Languages and Computation. Addison-Wesley, 1979.

[IEE94] IEEE. Structuring Chromosomes for Context–free GrammarEvolution, 1994.

[Koz92] J. R. Koza. Genetic Programming: On the Programming ofComputers by Means of Natural Selection. MIT Press, 1992.

[Lan94] M. M. Lanckhorst. Breeding grammars: Grammatical inference wi-th genetic algorithm. Technical Report CS-R 9401, University ofGroningen, 1994.

[Lan95] M. M. Lanckhorst. A genetic algorithm for the induction of non-deterministic pushdown automata. Technical Report CS-R 9502,University of Groningen, 1995.

[LHK99] S. Luke, A. Hamahashi, and H. Kitano. “genetic” programming.In Proceedings of GECCO 1999, San Francisco, 1999.

[LPP98] K.J. Lang, B.A. Pearlmutter, and R.A. Price. Results of the Ab-badingo one DFA learning competition and a new evidence-drivenstate merging algorithm. In Grammatical Inference, number 1433 inLecture Notes in Artificial Intelligence, pages 1–12. Springer-Verlag,1998.

[LV91] M. Li and P. Vitanyi. Learning simple concepts under simpledistributions. SIAM Journal of Computing, 20(5):911–935, 1991.

[MdG94] L. Miclet and C. de Gentile. Inference grammaticale a par-tir d’exemples et de contre-exe mples : deux algorithmes opti-maux (BIG et RIG) et une version heuristique (bri g). In Neu-viemes Journees Francophones sur l’Apprentissage, pages F1–F13,Strasbourg, France, 1994.

[MH96] L. Miclet and C. Higuera, editors. Incremental regular inference,number 1147 in Lectures Notes in Artificial Intelligence, Montpellier,France, 1996. ICGI, Springer.

[MH98] L. Miclet and C. Higuera, editors. A polynomial time incremen-tal algorithm for regular grammar inference, Ames, 1998. ICGI,Springer.

130 BIBLIOGRAFIA

[Mic87a] R. S. Michalski. Concept learning. In S. C. Shapiro, editor, En-cyclopedia of Artificial Intelligence, volume 1. Wiley–IntersciencePublications, 1987.

[Mic87b] R. S. Michalski. Understanding the nature of learning: Issue andresearch direction. In Mitchell Michalski, Carbonel, editor, MachineLearning, an Artificial Intelligence Approach, volume II. MorganKau"man Inc., 1987.

[Mic94] R. S. Michalski. Inferential theory of learning: Developing fon-dations for multistrategy learning. In Machine Learning: aMultistrategy Approach, volume IV. Morgan Kau"man Inc., 1994.

[Min76] E. Minicozzi. Some natural properties of strong identification ininductive inference. Theoretical Computer Science, 2:345–360, 1976.

[OG92] J. Oncina and P. Garcia. Inferring regular languages in polynomalupdate time. In E. Vidal N. Perez de la Blanca, A. Sanfeliu, edi-tor, Pattern Recognition an Image Analysis, number 1 in MachinePerception and Artificial Intelligence, pages 49–61. World Scentific,1992.

[Par98] R. Parekh. Constructive Learning: Inducing Grammars and NeuralNetworks. PhD thesis, Iowa State University, Ames, 1998.

[PC78] T. Pao and J. Carr. A solution of the syntatic induction-inferenceproblem for regular languages. Computer Languages, 3:53–64, 1978.

[Pit89] L. Pitt. Inductive inference, DFAs and computational complexity.In Analogical and Iductive Inference, number 397 in Lectures Notesin Artificial Intelligence, pages 18–44. Springer–Verlag, 1989.

[PW88] L. Pitt and M. K. Warmuth. Reductions among prediction problems:on the di!culty of predicting automata. In Proceeding of the 3rd

I.E.E.E Conference on Structure in Complexity Theory, pages 60–69, 1988.

[Rec73] I. Rechenberg. Evolutionsstrategie: Optimierung Technisher Sy-steme nach Prinzipien der Biologischen Evolution. Frommann–Holzboog, Stuttgart, 1973.

[Sal67] W. C. Salmon. the Foundations of Scientific Inference. Univ. ofPittsburg Press, 1967.

BIBLIOGRAFIA 131

[SD92] D. Searls and S. Dong. A syntactic pattern recognition system forDNA sequences. In Proceedings 2nd International Conference onBioinformatics, Supercomputing, and Compelx Genome Analysis,pages 1–15, 1992.

[Sim83] H. Simon. Why should machine learn? In Mitchell Michalski, Car-bonel, editor, Machine Learning, an Artificial Intelligence Approach,volume I. Tioga Publishimg Company, 1983.

[SJB+93] W. M. Spears, K. A. De Jong, T. Backi, D. B. Fogel, and H. DeGarisi. An overview of evolutionary computation. In Proceeding ofthe Europan Conference on Machine Learning, 1993.

[TB73] B. Trakhtenbrot and Y. Barzdin. Finite Automata: Behavior andSynthesis. North Holland Publishing Company, Amsterdam, 1973.

[Tom82] M. Tomita. Dynamic construction of finite automata from examplesusing hill–climbing. In Proceedings of the Fourth Annual Conferenceof the Cognitive Science Society, volume 4, pages 105–108, 1982.

[Val84] L. G. Valiant. A theory of the learnable. Communication of theACM, 27(11):237–269, 1984.

[ZL95] T. Zeugmann and S. Lange. A guided tour across the bounda-ries of learning recursive language. In K. P. Jantke and S. Lange,editors, Algorithmic Learning for Knowledge-Based Systems, num-ber 961 in Lecture Notes in Artificial Intelligence, pages 193–262.Springer-Verlag, 1995.

Universit`a degli Studi di Napoli “Federico II”mazzei/papers/laureaThesisMazzei.pdfIntroduzione...

Documents

Transcript of Universit`a degli Studi di Napoli “Federico II”mazzei/papers/laureaThesisMazzei.pdfIntroduzione...