Riassunto esame Intelligenza artificiale, prof. Bianchini, libro consigliato "Instrumentum vocale", Francesco Bianchini

3. SOLUZIONE DEI PROBLEMI E PIANIFICAZIONE

La risoluzione è un po' il punto centrale dell'IA.

Il GPS di Simon e Newell fu ben presto abbandonato e sostituito dagli “expert system”.

La prima questione da affrontare è: come si formalizza un problema (se non formalizzato correttamente, non potrà

essere “trattato”).

Le esigenze del problem solving si incentrano dunque su rappresentare un problema che si vuole risolvere. E la teoria

dei grafi aiuta, in questo senso.

Grafo = precisa struttura matematica; un modo canonico per rappresentare una relazione: gli elementi diventano i vertici

e si tracciano gli spigoli colleganti quelle coppie di vertici per i quali la relazione vale.

“in un grafo esiste una linea di Eulero se e soltanto se i nodi sono in grado locale pari”.

Albero = grafo aciclico (privo di cammini che tornano su se stessi). Questa caratteristica può essere sfruttata siccome,

dato un nodo, esiste ed è unico il percorsi che lo collega al nodo radice. Ogni nodo ha infatti un solo nodo padre.

È una struttura ricorsiva, ma anche strettamente gerarchica (ad ogni livello il numero dei nodi cresce).

Un grafo ad albero si presta a rappresentare in modo naturale l'andamento di una soluzione di un problema.

-Ricerca Cieca-

Algoritmo di ricerca = procedura di ricerca che prende in input un problema, e restituisce il fallimento, oppure una

soluzione, ossia un cammino che collega il nodo radice con una foglia voluta o goal.

• Alg di ricerca in profondità

• alg di ricerca per ampiezza

• ricerca euristica → cerca di individuare i percorsi più promettenti;

• hill climbing → sceglie il valore euristico migliore;

• best first → sceglie il figlio con valore migliore anche se non è quello diretto;

• alg A → valuta il costo dalla radice alla foglia

• grafi and/or → il cammino è costituito da un sotto albero. Per ogni grafo si ha:

– se un'azione è elementare, il costo è dato per definizione;

– se un'azione è elementare e non eseguibile, il costo è infinito;

– se è un nodo in OR, si somma il valore minimo tra quelli dei suoi figli;

– se è un nodo in AND, allora vale la somma dei valori figli.

In questo modo è possibile ribaltare all'indietro i costi del sott'albero risolutivo e computare il costo dei padri in

dipendenza dei figli.

-Planning-

una branca del problem solving. Si tratta di assumere entro la panoramica della risoluzione dei problemi la dimensione

della temporalità o almeno dell'ordine sequenziale.

Pianificare, d'altronde, significa concepire l'esecuzione di una sequenza di azioni che conducono al risultato voluto.

-Strips-

nuovo modo di rappresentare le azioni, ovvero come insieme di “precondizioni” e un insieme di “conseguenze”.

L'insieme di precondizioni = lista di enunciati da verificare perché l'azione possa aver luogo.

L'insieme delle conseguenze = è composto da 2 liste: “aggiunte” e “cancellazioni”.

L'algoritmo che governa gli STRIPS è “analisi mezzi-fini”.

I progressi successivi del planning hanno consentito di passare da pianificatori “tattici”, come strips a pianificatori

“strategici”, ossia in grado di trattare gli obiettivi congiuntamente.

Le tecniche sono tre:

a) protezione degli obiettivi → ovvero bloccare le condizioni relative ad un obiettivo già raggiunto per far sì che

diventino un vincolo per gli altri;

b) regressione degli obiettivi → calcolare a ritroso lo stato che precede lo stato finale;

c) modifica dei piani → non dare per scontato che i vari sotto-piani debbano essere concatenati in modo sequenziale.

Il vantaggio è che si evita di elaborare piani di dettaglio rispetto ad un obiettivo di livello alto che non può essere

raggiunto.

5. MORFOLOGIA E SINTASSI

Non esiste un pieno consenso nella definizione dei termini sintassi e semantica o grammatica formale.

Chomsky ha fornito all'IA una rigorosa definizione matematica.

L'approccio chomskiano si è rivelato un paradigma d'indagine valido per l'analisi sintattica del testo che ha portato alla

realizzazione dei sistemi oggi maggiormente conosciuti ed utilizzati: i parser.

Un modello grammaticale della lingua con lo scopo di interpretare frasi o discorsi dei parlanti, dovrebbe essere una

teoria in grado di spiegare la capacità umana di interpretare o produrre frasi in linguaggio naturale oppure dovrebbe

essere in grado di costruire strutture interpretative non ambigue di frasi al fine di produrre sistemi automatici per il

trattamento del significato.

La nozione di accettabilità è uno strumento d'indagine molto utile ai fini della comprensione dei fenomeni linguistici

che si intendono modellare. La teoria risultante dovrà esibire almeno questa capacità di discernere se una frase è

accettabile o meno. Deve dunque essere anzitutto descrittiva.

È accettabile quell'enunciato che consente di interiorizzare l'informazione in esso comunicata o di attivare le azioni

corrispondenti all'invito in esso contenute.

Una frase è accettabile a diversi livelli:

– il messaggio acustico è riconducibile alla sequenza delle parole dette e che ogni parola è accettabile come parte

di un vocabolario di unità significative, le parole, e ad amplissima adesione dall'intera comunità. L'accettabilità

dipendente dalle parole non esaurisce tutti i casi.

– Alcuni enunciati non sono accettabili poiché da essi non è possibile derivare alcuna informazione. Le parole

hanno dunque un valore rispetto all'accettabilità grammaticale che dipende dalle sequenze in cui esse

compaiono.

L'accettabilità grammaticale è una condizione necessaria per l'estrazione della giusta informazione, conoscenza o

procedura, anche se non sufficiente.

Analisi sintattica Analisi semantica

Le regole che determinano la corretta formazione di un Quando viene introdotto il mondo esterno esterno siamo

enunciato vincolano proprietà di una lingua che regolano interessati a vedere come le relazioni tra le parole

le relazioni tra le parole. soggiacciono poi ai criteri di un'interpretazione del loro

→ la derivazione (o il calcolo) di queste relazioni si “fare riferimento” a qualcosa di esterno alla lingua.

chiama: analisi sintattica. → questa interpretazione è il processo che si chiama:

In questa analisi si fa riferimento a proprietà lessicali analisi semantica.

(costruzione interna delle parole che ci consente di L'inaccettabilità semantica è qualcosa di più complesso

segmentare correttamente l'enunciato o le loro proprietà (rispetto a quella sintattica).

morfologiche) ed a proprietà strutturali degli enunciati. Semanticamente, gli enunciati “papa Benedetto XVI è

Carol Woityla” o “papa Benedetto XVI non è un papa”

non sono accettabili, perché confonde tra loro persone

diverse note e non è quindi vero, dato che il mondo che

conosciamo; è inconsistente e per motivi puramente logici

non può essere mai accettato come vero.

Una teoria T generale di una lingua L deve dare conto delle proprietà linguistiche necessarie all'interpretazione poiché

da esse dipendono sia la accettabilità che le conoscenze o le azioni che in analogia con i parlanti possono essere attivate

a fronte di un enunciato e. Affinché una teoria T sia utile deve fornire meccanismi computazionali in grado di

riconoscere l'accettabilità e costruire le strutture grammaticali che soggiacciono ai processi di interpretazione di

enunciati accettabili e.

Un sistema TAL (trattamento automatico delle lingue) deve essere quindi in grado di applicare agli enunciati e in

ingresso la teoria T allo scopo di derivare le nuove conoscenze, prendere tutte le decisioni o attivare le azioni

giustificate da e.

Nello sviluppo di questi modelli è stato fondamentale lo studio sui linguaggi di Chomsky.

Il potere di descrizione o predizione di una teoria si realizza attraverso un modello cioè un sistema di assunzioni,

rappresentazioni e algoritmi che, astraendo al livello opportuno dai dettagli irrilevanti di variabilità della lingua L,

definisce completamente le spiegazioni dei fenomeni noti con L e che sostiene tutte le inferenze richieste per spiegare

nuove osservazioni.

Modello sintattico = un'astrazione basata su un paradigma di rappresentazione per le osservazioni e per i vincoli

linguistici che fornisce metodi o procedure in grado di applicare tutti i vincoli alle nuove osservazioni.

Si dice completamente specificato se:

– un linguaggio di rappresentazione delle frasi in ingresso f;

– un linguaggio di rappresentazione per il risultato I(f);

– le regole R che descrivono tutti i vincoli di L;

– uno a uno i meccanismi per la applicazione delle regole alle rappresentazioni di f.

A tale meccanismo si fa spesso riferimento con il nome di parser.

Modello = la progettazione incrementale di una serie di astrazioni che tendono a conformarsi il più possibile alla

intuizione dei parlanti: la nozione accuratezza consente quindi di valutare un sistema ma anche di determinare le

limitazioni.

Il primo strumento di accettabilità: automa a stati finiti (FSA). Questi automi hanno la proprietà di essere efficienti dal

punto di vista computazionale. Gli FSA possono essere utilizzati solamente in alcune condizioni, ovvero se le regole

della grammatica hanno una particolare forma.

Un linguaggio L può essere considerato (nella sua forma astratta) come quell'insieme di stringhe (=sequenze finite di

elementi di un vocabolario di partenza A) che ne rispettano tutte le convenzioni.

Grammatica = sistema deduttivo di assiomi e regole di inferenza, che genera le frasi della lingua come i suoi teoremi.

Esistono tre definizioni di grammatica:

– grammatica formale → definita da una quadrupla (un vocabolario di simboli terminali, un altro di non

terminali, un assioma e un insieme di regole di riscrittura).

– Derivazione di una stringa → una sequenza di stringhe del linguaggio tramite le regole, eliminando via via i

simboli non terminali;

– accettabilità → una grammatica accetta una stringa se e solo se esiste una derivazione per s.

la struttura di nodi ed archi (detta grafo) rappresenta una visione sul linguaggio alternativa alla grammatica I. Descrive

la procedura da realizzare durante il parsing. Descrive un automa in termini di stati possibili dell'automa (nodi) e

transizioni tra stati (archi orientati dallo stato di partenza e quello di arrivo).

Automi = dispositivi generativi, ottimi candidati per modelli generativi delle lingue.

Automi