A cura di : Pranovi Gabriele, Pedrotti Cristian
Professore : Alfonso Gerevini
Scelta degli strumenti e implementazione
In questo tempo in cui l’elettronica e l’informatica, sfruttando tecnologie sempre più raffinate e algoritmi sempre più potenti, hanno cominciato a pervadere ogni aspetto della nostra vita e modificare radicalmente abitudini e credenze grazie alla diffusione di strumenti multimediali, un’importanza fondamentale assume l’idea di "comunicazione".
Tutto si basa e si riconduce a uno scambio di informazioni, di segnali, che cercano di descrivere qualche cosa o si propongono di far fare qualche cosa a qualcuno.
Molto spesso segnali, istruzioni, programmi, indispensabili per un’interazione uomo-calcolatore (il calcolatore può essere visto come una porta verso questo nuovo mondo) non sono comprensibili ai più, privi di dimestichezza con le problematiche relative all’informatica.
Un importante settore della ricerca in Intelligenza Artificiale si occupa allora di sviluppare tecniche per elaborare e sfruttare il linguaggio naturale come linguaggio utilizzabile anche da un comune PC.
Il problema principale sta nel fatto che un PC è progettato e costruito per comprendere e gestire linguaggi formali, mentre un linguaggio naturale (come l’italiano, l’inglese…) è il migliore esempio di linguaggio informale: ambiguo, senza semantica rigorosa, ridondante.
Una qualità preziosa e molto apprezzabile di un linguaggio naturale, che si potrebbe sfruttare per permettere uno sfruttamento ancora più profondo di molti strumenti software e programmi, sviluppare applicazioni di traduzione automatica e comprensione del testo, è però l’estrema semplicità: avremmo a disposizione un linguaggio già conosciuto da un elevato numero di persone che non sarebbero costrette a impararne altri o a schematizzare più o meno rigidamente le informazioni che intendono fornire al calcolatore. Il PC è visto quindi come "macchina intelligente" nel senso che dovrebbe in qualche modo "capire" quello che vogliamo dirgli o fargli fare, senza obbligarci a rispettare regole e modelli altrimenti indispensabili.
Senza grosse ambizioni ci siamo proposti di studiare e implementare una semplice interfaccia che permetta di formulare domande in italiano corrente, usando strutture di frase non eccessivamente complicate, ma nemmeno troppo banali, per accedere ad un database su cui effettuare ricerche.
Abbiamo scelto di dedicare maggiore attenzione all’analisi sintattica avendo già a disposizione un paio di algoritmi su cui impostare il lavoro e poiché un’accurata analisi semantica avrebbe comportato notevoli complicazioni, senza farci intravedere una concreta possibilità di successo al termine del lavoro.
Abbiamo scelto come ambiente per la nostra applicazione dimostrativa una biblioteca virtuale, esempio giocattolo su cui era banale predisporre un database a cui dover accedere e prevedere il tipo di richieste che un utente potrebbe voler fare, interagendo con il PC da tastiera.
Avevamo ipotizzato di sfruttare un server vocale per simulare una più realistica "risposta intelligente" del calcolatore in caso di successo nelle interpretazioni semantiche, ma abbiamo abbandonato l’idea poiché si presentavano troppi problemi e conflitti nella gestione delle librerie e il nostro "genio parlante" il più delle volte si zittiva inspiegabilmente.
Abbiamo oltretutto scelto a priori di orientarci verso una struttura che potesse essere adattata con minime modifiche a database diversi nei contenuti e nel numero dei campi. Per questo abbiamo lavorato costruendo una grammatica "classica" senza prendere in considerazione la possibilità di costruire una grammatica "semantica", specifica per l’ambito biblioteca (le parole di categoria nome potevano essere sottospecificate in sottocategorie quali "autore", "titolo", "genere" e ciò avrebbe probabilmente permesso interpretazioni semantiche e operazioni migliori).
SCELTA DEGLI STRUMENTI E IMPLEMENTAZIONE.
Obiettivo principale del sistema è la possibilità di interfacciare il programma ad un database Access ’97, traducendo domande e comandi in linguaggio naturale direttamente in linguaggio SQL, utilizzato per creare query anche su sistemi differenti da Access ’97.
Per potersi interfacciare in questo modo sono necessarie due tipi di analisi, strettamente connesse tra loro, un ‘ analisi SINTATTICA ed un ‘ analisi SEMANTICA.
L’ Analisi sintattica si occupa di riconoscere frasi che abbiano una struttura grammaticale precisa , e di individuare i vari sintagmi grammaticali all’interno della frase, utili per la successiva analisi semantica.
L’Analisi semantica riguarda il significato della frase, di come le varie parole(di differenti categorie grammaticali),si fondano tra loro per definire il significato di una domanda (nel nostro caso ,in particolare) o di una affermazione.
Durante lo sviluppo del progetto abbiamo seguito approcci differenti , al fine di valutare quali fossero le metodologie migliori da applicare.
Va comunque tenuto presente che il sistema sviluppato è una demo giocattolo rispetto a programmi "reali", o che debbano avere a che fare con problematiche reali.
Biblio è pensato per interfacciarsi ad un database estremamente semplice come architettura interna (c’è una sola tabella contente informazioni sui libri e sulla loro disponibilità, di conseguenza le query necessarie per reperire dati non necessitano di join con altre tabelle), e dà la possibilità di effettuare domande in un certo ambito e con un insieme ridotto di regole grammaticali (si possono, al momento, generare solo un certo insieme di domande).
Chart parsing non deterministico
Approccio ad oggetti con Chart Parsing Deterministico.
Il primo problema che abbiamo affrontato è stato di dare forma all’analisi sintattica di una frase.
Inizialmente, volendo rimanere svincolati dal database sottostante , abbiamo creato un’architettura ad oggetti adatta secondo noi al sistema in esame.
L’ obiettivo era di utilizzare l’algoritmo di Chart Parsing Deterministico, come illustrato sul libro di testo.
Trattandosi di pseudo-codice l’algoritmo è svincolato dall’ambiente di sviluppo utilizzato.
Abbiamo scelto ,volendo creare un programma in ambiente Win95, di utilizzare Visual Basic 6.0 come linguaggio di programmazione (perdendo in velocità di esecuzione, rispetto all’utilizzo di linguggi quali C,C++ o Java, ma guadagnando in semplicità e velocità di sviluppo della Shell grafica del programma).
L’ architettura ad oggetti utilizzata in principio comprendeva due moduli di classe per implementare rispettivamente un arco del Chart ed il Chart stesso. Per comprenderla meglio è utile partire da un semplice esempio:
supponiamo di analizzare la frase "la mamma prepara la colazione" avendo le seguenti regole grammaticali:
S -> PN PV
PN -> Articolo Nome
PV -> Verbo Articolo Nome
Il parsing sintattico, escluso l’ inizializzatore, genera un chart costituito dai seguenti archi
0,0,S -> * PN PV (il predittore espande S e cerca PN)
0,0,PN -> * Articolo Nome (il predittore espande PN e cerca Articolo)
0,1,PN -> Articolo * Nome (lo scanner trova "la")
0,2,PN -> Articolo nome * (lo scanner trova "mamma" e l’arco è completo)
0,2,S -> PN * PV (il terminatore completa PN)
2,2,PV -> * Verbo Articolo Nome (il ciclo riprende su PV)
2,3,PV -> Verbo * Articolo Nome
2,4,PV -> Verbo Articolo * Nome
2,5,PV -> Verbo Articolo Nome *
0,5,S -> PN PV *
Volendo creare un oggetto arco, abbiamo definito le seguenti propietà:
--Etichetta: è l’ intero arco ( ad esempio "0,0,S -> * PN PV")
--PrimoNodo ,SecondoNodo: I due numeri che indicano la posizione dell’ arco nella frase.
--Genera: è l ’ elemento generato dalla regola grammaticale
--Cerca: è l’elemento della grammatica che spero di trovare
--CercaSx ,CercaDx: Le parti a Dx e a Sx del simbolo * in un arco (introdotte per facilitare la modifica degli archi da parte di Predittore ,Scanner e Terminatore).
Dichiarando UnArco come Arco:
Dim UnArco as new Arco
ed avendo ad esempio l’ arco "2,2,PV -> * Verbo Articolo Nome" otterremmo:
UnArco.Etichetta="2,2,PV -> * Verbo Articolo Nome"
UnArco.PrimoNodo=2
UnArco.SecondoNodo=2
UnArco.Genera="PV"
UnArco.Cerca="Verbo"
Per rappresentare il Chart il meccanismo è simile ad eccezione che l’ oggetto Chart non è costituito da un unico Arco ma da un insieme (Collection) di archi.
In realtà il Chart da noi creato inizialmente era una collezione di collezioni di archi fatta in modo tale che Chart(j) rappresentasse l’ insieme degli archi aventi j come secondo nodo, questo avrebbe dovuto rendere più semplice l’ implementazione dell’ algoritmo di chart parsing deterministico.
Sfortunatamente il chart deterministico soffre di un problema: lo Scanner tenta di trovare come prima parola una parola di categoria "S", cosa che non ha evidentemente un gran senso, a meno che tutte le parole non vengano viste anche come frasi (cosa che costringe a modificare il dizionario).
In alternativa ci siamo dedicati al chart Non Deterministico, che offriva maggiori possibilità di modifica di Predittore,Scanner,Terminatore, del Chart, e del modo in cui le varie procedure si richiamano tra loro.
Approccio con Chart Parsing Non Deterministico e Access ’97.
Abbiamo allora deciso di abbandonare l’ architettura ad oggetti (troppo pesante da gestire), e creato il Chart direttamente in Access ‘97.
Il chart è costituito semplicemente da una tabella che viene ripulita prima di ogni analisi, e su cui i vari componenti software vanno a lavorare mano a mano che l’ analisi procede.
La tabella ha dei campi che corrispondono in buona misura alle propietà dell’ oggetto Arco di cui abbiamo parlato:
--Etichetta
--PrimoNodo
--SecondoNodo
--Sintagma (equivale alla propietà Genera)
--Cerca
--Parola
--Completo (un flag che indica se l’ arco è completo)
Dato che con il chart non deterministico è difficile tenere sotto controllo gli archi che vengono creati abbiamo aggiunto allla tabella con tre flag (tre campi booleani).
--Predittore
--Scanner
--Terminatore
Che vengono settati nel momento in cui su di un certo arco va ad agire il Predittore, lo Scanner, o il Terminatore rispettivamente ( questo evita tra l’ altro il verificarsi di certi tipi di cicli infiniti).
Oltre al Chart sono necessari una grammatica ed un dizionario (la ricchezza dei quali influisce NOTEVOLMENTE sulle prestazioni dell’ algoritmo).
Sia il dizionario che la grammatica sono memorizzati in forma di tabelle.
La grammatica è un semplice insieme di regole grammaticali; ogni regola è costituita dai due campi:
--Sintagma: è il non terminale della regola
--Genera: come i simboli terminali si uniscono per definire il sintagma grammaticale
Ad esempio avremo una regola del tipo "PN -> Articolo Nome" dove Sintagma= "PN" e Genera= "Articolo Nome" .
Il dizionario ha i campi seguenti:
--Parola
--Tipo
Come tipo abbiamo inteso la categoria grammaticale della parola (Articolo, Nome, Verbo…) aggiungendo un tipo "XXX" ad indicare che una parola è di una categoria sconosciuta (nel caso in cui una parola immessa non sia presente nel dizionario, viene aggiunta automaticamente come di tipo "XXX").
Quello che serve per l’analisi sintattica è tutto qui:
Supponiamo ora di avere le seguenti regole grammaticali in cui la terza regola è ricorsiva
S -> PN PV
PN -> Articolo Nome
PN -> PN Aggettivo
In questo caso l’ algoritmo entrerebbe in un ciclo infinito dato che il predittore continuerebbe ad espandere la PN della regola ricorsiva indefinitamente.
Il problema è stato risolto inizialmente cercando di definire una grammatica libera dal contesto senza regole ricorsive:
PN1 -> Articolo Nome \
PN2 -> PN1 Aggettivo
S -> PN1 PV
S -> PN2 PV
Una soluzione di questo tipo ci ha dato altri problemi, infatti dal chart
0,0,S -> * PN1 PV
0,0,S -> * PN2 PV
0,0,PN1 -> * Articolo Nome
0,0,PN2 -> * PN1 Aggettivo
0,0,PN1 -> * Articolo Nome
PN1 viene considerato due volte sia dal predittore che dallo scanner (che riconosce due volte lo stesso articolo).
Per ovviare al problema abbiamo vincolato il predittore a considerare solamente archi Univoci, nel caso sopra il predittore deve pensare di essere in cerca di PN1,PN2, ed Articolo e non di PN1,PN2,Articolo,PN1,Articolo.In questo modo non vengono fatte predizioni superflue per archi che non sono in cerca di qualcosa di nuovo o utile all’analisi.
Con questa soluzione si evitano tra l’altro anche i cicli dovuti a regole ricorsive, e quindi abbiamo potuto tornare a un insieme di regole più compatto che utilizza ampiamente regole di questo tipo.
L’analisi sintattica che Biblio è in grado di compiere è, a questo punto , abbastanza soddisfacente.
Frasi che non vengono riconosciute immediatamente possono essere riconosciute modificando le regole della grammatica o il dizionario delle parole. Tali modifiche possono essere fatte durante l’esecuzione del programma, in modo da verificare come grammatica e dizionario influenzino l’efficienza dell’analisi sintattica.
L’ obiettivo successivo è stato di implementare una qualche forma di analisi semantica.
Il programma opera su una tabella LIBRI, memorizzata nel Database, contenente i campi seguenti:
--ID_LIBRO: codice identificativo del libri
--TITOLO
--AUTORE
--GENERE
--CASA EDITRICE
--DISPONIBILITA’
--NOTE
Le ricerche possono essere effettuate su un campo o contemporaneamente su più campi della tabella.
Il problema che salta subito all’ occhio è di riconoscere un Titolo, un genere o un autore all’ interno della domanda.
Supponiamo di inserire al prompt del programma la domanda:
"Quanti libri ci sono di Italo Svevo?"
Il programma non può sapere che "Italo Svevo" è il nome di un autore.Il trucco da noi utilizzato è estremamente semplice:
i titoli,i generi o gli autori che hanno più parole, devono essere inseriti tra apici:
"Quanti libri ci sono di ‘Italo Svevo’?"
Il programma modifica la frase (senza che l’ utente se ne accorga) in qualcosa del tipo: "Quanti libri ci sono di Italo-Svevo?"
E memorizza Italo-svevo , considerato come una sola parola, nel dizionario con il tipo "nome".Le ricerche vengono poi effettuate considerando tutti i nomi contenuti nella frase.
La ricerca è una ricerca globale:
Dalla frase "Quanti libri ci sono di Italo Svevo?", lo scanner riconosce come nomi "libri" e "Italo Svevo",il modulo di ricerca vede se i due nomi compaiono come parte di un qualsiasi campo della tabella LIBRI ed accoda i risultati ottenuti per considerazioni successive.I due termini di ricerca "libri" e "Italo Svevo" sono messi in OR tra loro, quindi l’ analisi di una domanda del tipo:
"Hai dei libri di storia e di omero" farà visualizzare tutti i libri di storia e tutti i libri di Omero. Al momento non abbiamo implementato ricerche in AND, quindi non verranno evidenziati eventuali libri di storia scritti da Omero
Le due uniche funzioni di ricerca che abbiamo implementato consentono:
Da notare che se l’utente richiede una ricerca del tipo "Avete dei libri gialli?" e nel database ho libri catalogati di genere "giallo", l’analisi semantica non darà alcun risultato, data la semplicità dell’algoritmo.
Per ovviare a questo problema si potrebbero confrontare i nomi (e gli aggettivi ) delle espressioni che esprimono il genere, il titolo…nella formulazione dell’utente e in quella presente nel database secondo due criteri: