mercoledì 9 maggio 2007

Reti di parole su CD



Oggi vi parlerò di CD.
No, non di musica. Nemmeno del supporto di memorizzazione: sono un informatico ma non devo parlare continuamente di tracciati record e simili.

CD sta per Conceptual Dependency ed è una delle tecnologie dell'Intelligenza Artificiale alla base della comprensione del linguaggio (NLP = Natural Language Processing).

Hey, ma dove andate? Se rimanete vi parlo anche di Wordnet. Fermi...

E adesso? Scrivo lo stesso, anche se sono rimasto solo?
Ma sì, dai, tanto prima o poi qualcuno arriva per sbaglio e legge anche questo.

Anche se stavolta sarò noiosissimo, così imparate a non stare qui ad interagire con me, per mantenermi su binari ragionevoli.

E non vi chiederete più perchè c'è voluto così tanto tempo dall'ultimo post.



Tu prova ad avere un mondo nel cuore
e non riesci ad esprimerlo con le parole
[...]
E sì, anche tu andresti a cercare
le parole sicure per farti ascoltare:
per stupire mezz'ora basta un libro di storia,
io cercai di imparare la Treccani a memoria,
[...]
[Il matto - De Andrè - Da Non al denaro, non all'amore, nè al cielo]



Alla fine degli anni '60, più o meno quando io stavo nascendo, Roger C. Schank e suoi collaboratori della Stanford University iniziarono a pubblicare i loro lavori riguardo alla Conceptual Dependency (CD), sostanzialmente mostrando come si poteva costruire un parser per il linguaggio naturale, in grado di elaborare frasi fornite in input, disambiguandone i concetti e generando una rappresentazione del significato, utilizzando una grammatica che mettesse in evidenza la semantica.

Schank partiva dal concetto che si potesse analizzare il modo di comprendere tipico degli esseri umani per trovare algoritmi e rappresentazioni indipendenti dal linguaggio per la comprensione dei computer.
CD come analogia di rappresentazione mentale.

Uno dei vantaggi di un approccio simile è che una stessa rappresentazione può anche riassumere diverse rappresentazioni sintattiche (in italiano: frasi diverse con lo stesso significato avrebbero la stessa rappresentazione), con ovvie conseguenze nella semplificazione dell'elaborazione dei concetti espressi e, più in generale, per operare delle inferenze.

Tra l'altro, una volta ottenuta una rappresentazione non ambigua e semantica di una frase o di un testo più complesso ci si trova nella posizione giusta per poter ottenere anche una parafrasi della frase stessa, eventuali riassunti e anche per cercare di operare traduzioni in altre lingue. O, al contrario, sarebbe possibile partire dai concetti, per generare storie.

La potenza dell'approccio proposto è stata mostrata attraverso parecchie applicazioni, negli anni seguenti, ma, nonostante siano passati quasi 40 anni non troverete molti traduttori commerciali basati su questa tecnologia.

Troverete, invece, tecnologie ancora precedenti, decisamente più semplici (per esempio basate sulla frequenza di comparsa delle parole nelle frasi), ma significativamente potenziate dall'attuale potenza di calcolo.

Ma se la CD potrebbe permettere di ottenere risultati decisamente superiori a quella della maggior parte dei più comuni traduttori automatici, che non hanno la pretesa di capire alcunchè, come mai questa tecnologia non si è diffusa nei prodotti commerciali?
Essenzialmente perchè implica la presenza di una notevole base di conoscenza che sia in grado di definire, data una parola, una serie di attese sulle parole precedenti e quelle seguenti, di cancellare tali pretese quando non si trovano corrispondenze e di confermarle nel caso siano logicamente coerenti con il resto della frase o del testo.

Per fare un veloce esempio di parte della conoscenza necessaria, consideriamo la seguente frase (presa da uno degli articoli e volutamente semplice e semplificata: tenete presente che la CD si applica anche a frasi complesse con coordinate e subordinate - diverse fonti su Internet vi permetteranno di ottenere approfondimenti e introduzioni riguardo alle primitive della CD ed esistono anche esempi di come venivano memorizzate in lisp le strutture dati nei primi programmi alla base della CD):
Il grande uomo ruba il libro rosso alla ragazza

  • Il: può servire per connettere frasi, per esempio potrebbe essere che la prarola cui si riferisce trovi una corrispondenza in una frase precedente

  • grande: si riferisce ad un concetto che potrebbe necessitare di ulteriori approfondimenti concettuali (come aggettivo, potrebbe presupporre l'esistenza di un sostantivo seguente - situazione che, di fatto, viene confermata dalla continuazione della frase)

  • uomo: può esistere da solo e viene completato dalle parole precedenti, quindi è possibile costruire un aggregato basato su questo termine

  • ruba: individua una azione e ha bisogno di un soggetto e di un complemento. Legandola al concetto precedente (possibile perchè sul piano grammaticale concorda), permette di costruire una proposizione riguardo ad un attore: esiste una dipendenza bidirezionale tra 'ruba' e 'uomo', che stanno sullo stesso piano (almeno, questo è quanto dice Schank nei primi articoli, ma ne riparliamo)

  • il-libro-rosso: senza ripercorrere le singole parole, devono esistere regole sintattiche, grammaticali ed attese semantiche che permettano di legarli per creare un concetto, secondo quanto visto prima e una attesa generata dal verbo 'ruba' prevede che ci sia un oggetto da rubare e questo concetto è coerente con questa attesa

  • alla-ragazza: qui si trova un ulteriore tipo di relazione, che non staremo qui a dettagliare, ma che lega questi termini al libro rosso, attraverso attese generate sempre dal verbo rubare (si ruba qualcosa a qualcuno)

Fino a questo punto le competenze sembrano essere, come sopra indicato, grammaticali, sintattiche e, solo parzialmente, semantiche.
Una analisi ulteriore della stessa frase, e da un approfondimento dell'algoritmo alla base del parser (come, per esempio, in uno dei primi articoli, ma, meglio, in "Inside Computer Understanding: Five Programs Plus Miniatures" - Roger C. Schank e Christopher K. Riesbeck - 1981) si vede che, almeno per questa
frase, il tutto si potrebbe anche ridurre ad una sorta di analisi logica, basata su posizioni relative delle parole e preposizioni più o meno articolate. Almeno nel contesto ridotto su cui Schank lavorava ai tempi (poche centinaia di parole).

E, comunque, ricordatemi di proporvi di realizzare un programma in grado di elaborare una analisi logica, alla fine di questo post...

La semantica, al di là dell'ultra-semplificato-esempio-sopra-riportato, è necessaria per identificare stranezze nella frase:
La casa volava da Milano a Roma

rispetto a
L'aereo volava da Milano a Roma

E i programmi di Schank potevano anche notare queste stranezze e operare ulteriori inferenze.

Ma la CD è solo la partenza, solo il substrato: per disambiguare servono anche altri concetti, serve una conoscenza del mondo e della sequenzialità delle operazioni standard (script, per Schank - es: se il Depa va al ristorante, ordina una bistecca, più tardi paga ed esce soddisfatto, come fate a sapere che ha mangiato la
bistecca, dal momento che non ve l'ho detto? Perchè avete delle attese sui comportamenti e sulla sequenzialità degli stessi, in situazioni standard) che ci si attendono in certi ambiti, una conoscenza degli obiettivi (goal) e una identificazione dei piani per raggiungere tali obiettivi, etc. etc.

Serve un po' di senso comune, insomma. Tutt'altro che banale, visto che ne sembra spesso sprovvista anche la maggior parte degli umani.

Uno dei limiti degli approcci di Schank, ai tempi, era la dimensione della base dati (certamente dettata dalle ridotte capacità elaborative di 40 anni fa, ma anche dalla mancanza quasi totale di progetti volti a generare simili tipologie di informazioni).
E' estremamente dispendioso codificare tutta la competenza necessaria per una comprensione soddisfacente, ma certo potrebbe già essere utile riuscire a gestire un primo livello di relazioni tra le parole, adatto per evitare di cadere in traduzioni automatiche orrende come quelle in cui si incorrerebbe passando questo testo sotto il filtro di Babelfish o compagnia bella.

Basterebbe una rete semantica, che gestisca le principali relazioni tra le parole, senza necessità di scendere al livello della fisica quantistica. Per esempio, il cane è un animale è una relazione tra un iponimo (cane) ed un iperonimo (animale). Una relazione IS-A o, in termini più comprensibili per chiunque sappia vagamente programmare, si potrebbe dire che 'cane' eredita da 'animale'. (O ne implementa l'interfaccia, che sarebbe meglio, per evitare il fragile base class problem e simili). E le parole sono correlate tra loro
anche in altri modi (sinonimi, meronimi, etc. etc.).

Particolarmente interessante è la sinonimia, che deve essere considerata nella sua accezione semantica corretta.

Per es., il lemma prova può significare:
- evidenza, riscontro
- test, esame
- concorso
- compito
- cimento, impresa
- assaggio
etc. etc.

Notiamo che ho usato dei sinonimi (scelti a caso, senza pretesa di completezza e correttezza) per illustrare, almeno con una prima approssimazione, i diversi significati, le possibili semantiche della parola presa in considerazione. Il che ci porta a pensare che i sinonimi siano un buon punto di partenza per poi disambiguare.

Questi stessi sinonimi, se messi uno di fila all'altro (come fa Sinonimi Master, forse il più completo ed utilizzabile insieme di sinonimi italiani che mi è capitato di trovare su Internet), sarebbero stati molto meno utili.
Li ho, invece, raggruppati in insiemi di sinonimi (cui dovremmo aggiungere il lemma di partenza), non a caso: si parla di synset (contrazione di synonyms set) e questo concetto è alla base di reti semantiche come Wordnet.

Quest'ultimo sì, è sicuramente free e di elevatissimo livello.
Sarebbe bello averne uno anche per l'italiano e per altre lingue, certo sarebbe ancora meglio se fosse possibile averlo già in relazione con la versione inglese.

Beh, la buona notizia è che ce ne sono almeno 2: EuroWordNet e MultiWordNet (dovesse interessarvi un semplice confronto tra le due...). La cattiva è che non sono free, neppure per scopi personali, nè Open Source.

Ora, sarebbe interessante continuare, parlando di:
- come CD e (Euro)WordNet possano convergere verso un sistema che possa, almeno, cercare di fare una prima analisi dei testi, con migliori speranze di prenderci rispetto alla maggior parte dei sistemi di larga diffusione
- come alcuni abbiano già fatto qualcosa di simile, se non altro in ambito più ristretto (che so: vi siete resi conto che una grande parte della Knowledge Base di Microsoft in italiano risulta tradotta automaticamente? Il risultato non è malissimo - non perfetto, ma non male - e si basa su concetti simili a quelli indicati, almeno per la costruzione di MindNet una rete semantica simile a Wordnet, ottenuta, tra l'altro, automaticamente, attraverso parsing di vocabolari ed enciclopedie elettroniche)
- come sia possibile cercare di costruire una simile rete semantica, in modo pseudo-automatico
- come non sia così facile mettere in relazione diretta i synset di linguaggi differenti (per esempio, a causa dei gap lessicali)

Sarebbe interessante, ma mi avete lasciato solo.
Volete conoscere l'assassino? Gli accessi a questo articolo devono essere tanti e differenziati...

Bye
    Depa

7 commenti:

Micio ha detto...

Sono arrivato fino in fondo al post ... complice una query lenta del nostro DB ...
Scherzo! L'argomento è interessante e i concetti che hai spiegato sono molto interessanti.
L'assassino (cioè la "killer application") in questo ambito di fatto non è stata ancora trovata chissa che in futuro l'evoluzione della tecnologia CD non la possa creare ...
Ciao

Stefano

Depa ha detto...

Grazie Stefano.

Se avete query lente da permettervi di leggere i miei post, sappiate che, se vi serve una mano per ottimizzarle un po',... ;)

La killer application non esiste ancora, ma ci avviciniamo sempre di più.

Difficile che la CD, da sola, pur evolvendo (e ho dei dubbi: sono passati quasi 40 anni e ora Schank si occupa principalmente di e-learning - ne parleremo presto), possa essere in grado di darci l'applicazione che possa risolvere i problemi che ci sono ancora in questo campo.

L'assassino, anche per questo, è necessariamente un altro.

giampi ha detto...

Interessantissimo e l'ho letto anche senza avere una query da ottimizzare =).
L'argomento intelligenza artificiale mi interessa molto, hai qualche lettura consigliata per iniziare?

Questo è il mio blog

Depa ha detto...

Intanto grazie e complimenti per il tuo blog (ci vediamo lì sopra tra un po'...)

Per iniziare sull'AI? Acc... complicato: i miei testi sono vecchi (cosa faccio? non posso mica consigliarti Goedel Esher Bach di Hofstadter: è un po' passato - bello, profondo, ma oggettivamente vecchio).

Ora io cerco articoli su Internet, per esempio partendo da Citeseer, ma bisogna sapere cosa cercare...

Un cattivo (ma divertente) punto da cui iniziare sarebbero i siti che parlano di AI nei videogame (ma servono solo per vedere utilizzi pratici dell'algoritmo A*).

A casa io ho una vecchia edizione di un testo di Elaine Rich, che ho trovato, ai tempi, piuttosto interessante. Vedi mai che seguendo i suoi link si possa arrivare ad una pagina tipo quella dell'Università di Berkeley che lista dei testi sull'AI su Internet...

Bye
Depa

giampi ha detto...

Sono nella lettura di Hofstadter, molto divertente e il bello è che è anche ben scritto e divertente.

Grazie per i link dell'Università di Berkley, nella lista avevo solo letto il Russel Norvig, approfondirò.

Ciao
Giampiero

Anonimo ha detto...

Ciao!!! A me ha fatto molto comodo....ci sto studiando sopra! Thanksssss

Depa ha detto...

Non eravate scappati tutti, come pensavo nell'abstract, allora...

Fa piacere poter essere d'aiuto. E fa piacere aver scritto un post che, ancora a distanza di un anno e mezzo possa essere ancora d'aiuto.

Mi fate quasi venir voglia di trovare a tutti i costi il tempo per pubblicare gli altri 12 post che ho iniziato e mai pubblicato...