DART e MediaDART strumenti intelligenti per la

ricerca e il delivery di informazioni e contenuti

Franco Tuveri tuveri@crs4.it

Maria Laura Clemente clem@crs4.it

XVII Settimana della Cultura Scientifica e Tecnologica

Cagliari – 20/04/2007

2

DART e MediaDART

Il progetto si articola attraverso lo sviluppo di:

• DART: il motore di ricerca distribuito e semantico

• è un framework per la costruzione di servizi per la gestione di grosse collezioni di media.

• Progetto co-finanziato dal MIUR (D.L. 297/99)• partner CRS4, Tiscali e il DIEE dell’Università di Cagliari

3

Il progetto DARTDART – Distributed Agent-based Retrieval Toolkit

Un Motore di Ricerca collaborativo, semantico, distribuito e sensibile al contesto.

Creare una community che contribuisca con le risorse di calcolo e storage disponibili sui nodi alla creazione di una infrastruttura di ricerca collettiva e open source, per la fruizione semantica di risorse e servizi, siano essi digitali o reali.

Si inquadra nella nuova generazione di search engine che vuole dare una risposta alla esigenze degli utenti tra cui quelle di trovare oltre che oggetti virtuali accessibili via browser anche oggetti concreti e servizi reali.

4

DART: La sfida dei nuovi search engine

Gli utenti richiedono informazioni su oggetti del mondo reale:

prodotti disponibili al supermercato,

un parcheggio libero vicino a casa,

l'ufficio postale meno affollato...

Per vincere questa sfida ci si sta orientando su alcuni aspetti chiave: collaborazione geo-referenziazione semantica

5

Collaborazione Permettere agli utenti di sottomettere direttamente nuove

risorse, come avviene nelle reti P2P

es.: la “mappatura” degli autovelox ;-)

Consentire agli utenti di partecipare attivamente anche

mettendo a disposizione le proprie risorse HW e la propria

banda libera

6

Geo-referenziazione

Consentire agli utenti di formulare richieste relative a posizioni geografiche specifiche attraverso l’uso di coordinate espresse in termini di latitudine e longitudine o attraverso i nomi dei luoghi.

Persone e oggetti “mobili” notificano autonomamente la propria posizione

7

Semantica Consentire all’utente l’utilizzo di query espresse in

Linguaggio Naturale

L'analisi semantica fornisce il corretto significato di termini e frasi in accordo con i segmenti di testo contigui per risolvere le possibili ambiguità.

Migliora la qualità delle informazioni recuperate, e permette la costruzione di basi di conoscenza.

8

DARTPrincipali caratteristiche:

Capacità semantiche Query utente espresse in Linguaggio Naturale Indicizzazione e classificazione delle risorse

Geo-referenziazione delle risorse Intelligent User Interface e Assistente virtuale

Il motore di ricerca identifica le preferenze dell’utente e seleziona i risultati in base ad esse ed al contesto.

Supporto di device mobili e gestione della posizione degli utenti Community di utenti per il “recupero” del Web invisibile Architettura distribuita su rete P2P strutturata per lo storage delle informazioni

9

Natural Language ProcessingI Linguaggi Naturali sono i generici linguaggi usati dagli essere umani, non artificiali (es: Esperanto) né formali come i linguaggi di programmazione.

Il Natural Language Processing, o NLP, è “lo studio dei sistemi informatici per la comprensione e generazione del linguaggio naturale” (Grisham, 1986)

I sistemi di NLP possono operare a diversi livelli di analisi:

• Analisi Morfologica: analisi della struttura delle parole• Analisi Sintattica: strutture sintattiche corrette; rifiutare quelle non corrette • Analisi Semantica: associare significati alle strutture (es. “Verdi idee incolori dormono furiosamente”, Chomsky, 1957)• Integrazione del discorso: una frase può dipendere dalle precedenti (es. “Gianni lo voleva”) • Analisi Pragmatica: a volte la struttura va interpretata (es. “Sai che ora è?” significa “Mi dici l’ora?”)

10

Analisi Morfologica

La Morfologia è lo studio di come le parole sono costruite a partire da unità

atomiche dette morfemi

L’analisi Morfologica di una parola comprende: il lemma da cui è originata il numero, la persona, il genere e gli altri parametri grammaticali che la

individuano.

L’analisi viene fatta per i : Lemmi verbali, attraverso le desinenze e regole di flessione Lemmi non verbali, attraverso le sole desinenze

Gli strumenti che eseguono l'analisi morfologica sono i lemmatizzatori o stemmer, integrati in quasi tutti i parser sintattici e negli analizzatori lessicali.

E’ la base di partenza per la fase successiva di analisi sintattica

11

Analisi SintatticaPossiamo definire la Sintassi come costituita da:

una grammatica del linguaggio che vogliamo analizzare un lessico, che contiene le parole del linguaggio un parser, che interpreta le le frasi

L'analisi sintattica tramite parsing sintattico, è una funzione utile a catalogare oidentificare le relazioni tra le parti di una frase, ovvero i termini o gli insiemi di termini.Se è possibile costruire due rappresentazioni sintattiche, o parser-tree o alberi sintattici diversi a partire dalla stessa frase e dalla stessa grammatica, la frase è detta sintatticamente ambigua

Il parser sintattico, o phrase recognition parser, esegue un'analisi dei costituenti della frase, ad esempio individuando la parte nominale e/o la parte verbale, e analizza come le parole si compongono in unità più grandi, dette sintagmi, e comprende se queste rispettano le regole grammaticali.

12

Analisi Sintattica: parsing

Il parsing è il processo di assegnazione di una struttura ad una stringa in base ad una grammatica.

Esistono 2 classi principali di parser o analizzatori sintattici: Parsing a costituenti: processo di riconoscimento di una stringa e di assegnazione

ad essa di una struttura sintattica corretta (parse-tree) Parsing a dipendenze, basati sulle relazioni grammaticali tra parole. Produce una

rete di dipendenze in cui: i nodi rappresentano le parole gli archi rappresentano le dipendenze grammaticali tra le parole Es.: Link Grammar (Sleator -Temperley, 1993)

*Costituente - gruppo di parole consecutive che si comportano come una singola unità sintattica

13

Analisi Semantica

“La determinazione del significato di una frase avviene in diverse fasi successive: nella prima ci si serve solo della struttura sintattica e dei significati delle parole, mentre nella seconda si tiene conto delle frasi precedenti già interpretate, di conoscenze sull'argomento di cui il testo tratta e di conoscenze generiche sul mondo. La prima fase prende il nome di “analisi semantica” … [Allen, 1995]

La Semantica è lo studio del significato delle parole e di come esse si combinano per formare il significato delle frasi.

In genere si fa distinzione tra: Semantica Lessicale (Lexical Semantics) o studio delle relazioni lessicali (sinonimia,

iperonimia/iponimia, meronimia, .. ) Semantica delle frasi (Sentences Semantics) o studio del significato di intere frasi.

L'analisi semantica fornisce i corretti significati dei costrutti sintattici individuati dall'analizzatore sintattico e ne risolve l'ambiguità.

I termini o le parole vengono sostituiti dagli identificatori del significato (Word Sense Disambiguation, WSD), che poi possono essere utilizzati nella classificazione del testo per categorie.

14

Gli strumenti

Strumenti per l’analisi del testo:

- Parser sintattici: Link Grammar- Effettua l’analisi morfologica e sintattica di una frase; - Esegue il POS (part of speech) Tagging (unica interpretazione morfologica)- Individua le possibili strutture sintattiche della frase

- Risorse lessicali: WordNet

- Tassonomie: - Classificazione dei testi analizzati: utile per la disambiguazione semantica

delle frasi:- WordNet Domains

15

LinkGrammar

LinkGrammar è un parser sintattico per l’inglese, che assegna a ciascuna frase le possibili strutture sintattiche.

Una struttura sintattica consiste di un insieme di collegamenti etichettati tra le parole.

Come per tutti i phrase recognition parsers, LinkGrammar non riesce ad assegnare in modo univoco un ruolo ad una parola di una frase, ma fornisce diverse possibili relazioni tra di esse.

Così per ridurre il numero di collegamenti tra parole, noi applichiamo una funzione peso che assegna a ciascun collegamento un valore direttamente proporzionale al numero di volte in cui in cui il collegamento compare nelle possibili relazioni ed indirettamente proporzionale al numero delle relazioni.

Ci aiuta a definire e a ridurre l’insieme dei possibili risultati derivanti dall’analisi sintattica, di capire il ruolo e il possibile significato che la parola assume nel contesto sintattico in cui è inserita.

16

Analisi sintattica di una frase“Jellyfish are marine invertebrates belonging to the Scyphozoan class”

+---------Jp--------+ +--------Opt--------+ | +-------D*u------+| +---Spx--+ +-----AN----+------Mg-----+--MVp--+ | +---AN---+| jellyfish.p are.v marine.n invertebrates.n belonging.v to the Scyphozoan class.n

Links and Domains:

(109) LEFT-WALL Wd <---Wd----> Wd jellyfish.p (109) jellyfish.p Sp <---Spx---> Spx are.v (109) are.v O*t <---Opt---> Op invertebrates.n (109) marine.n AN <---AN----> AN invertebrates.n (109) (-1) invertebrates.n M <---Mg----> Mg belonging.v (109) (-1) belonging.v MV <---MVp---> MVp to (109) (-1) to J <---Jp----> Jp class.n (109) (-1) the D <---D*u---> D*u class.n (109) (-1) Scyphozoan AN <---AN----> AN class.n

17

WordNetWordNet è un database lessicale realizzato per la lingua Inglese. Raggruppa nomi, verbi, aggettivi e avverbi organizzandoli in insiemi (set) di sinonimi, detti synset. Ciascun synset esprime un diverso concetto identificato univocamente da un sysnsetID.

I synset sono collegati tra loro per mezzo di relazioni lessicali e semantiche come:

sinonimia meronimia Iperonimia/iponimia Antonimia

18

WordNetSinonimia:“rapporto tra segni linguistici che hanno lo stesso significato”*

es.: cortese = gentile

Meronimia “relazione semantica tra nome del tutto e nome di una sua parte” *

es.: motore è meronimo di automobile

Iperonimia / Iponimia“relazione semantica paradigmatica tra termine generico Iperonimo o sovraordinato e uno o più termini specifici o Iponimi ”*

es.: mobile (iperonimo) e sedia, tavolo, armadio (iponimi)

Antonimia“relazione tra due segni di significato contrario” *

es.: bello/brutto, amore/odio

(*) Dizionario di linguistica – diretto da G.Luigi Beccaria ed. Einaudi

19

WordNet: dogThe noun dog has 7 senses (first 1 from tagged texts)

1. (42) {02001223} <noun.animal> dog#1, domestic dog#1, Canis familiaris#1 -- (a member of the genus Canis (probably descended from the common wolf) that has been domesticated by man since prehistoric times; occurs in many breeds; "the dog barked all night")

2. {09465341} <noun.person> frump#1, dog1#2 -- (a dull unattractive unpleasant girl or woman; "she got a reputation as a frump"; "she's a real dog")

3. {09382160} <noun.person> dog#3 -- (informal term for a man; "you lucky dog")

4. {09256536} <noun.person> cad#1, bounder#1, blackguard#1, dog2#4, hound#2, heel#3 -- (someone who is morally reprehensible; "you dirty dog")

5. {07205647} <noun.food> frank#2, frankfurter#1, hotdog1#3, hot dog1#3, dog1#5, wiener#2, wienerwurst#1, weenie#1 -- (a smooth-textured sausage of minced beef or pork usually smoked; often served on a bread roll)

6. {03754154} <noun.artifact> pawl#1, detent#1, click#4, dog#6 -- (a hinged catch that fits into a notch of a ratchet to move a wheel forward or prevent it from moving backward)

7. {02617005} <noun.artifact> andiron#1, firedog#1, dog1#7, dog-iron#1 -- (metal supports for logs in a fireplace; "the andirons were too hot to touch")

The verb dog has 1 sense (first 1 from tagged texts)

1. (2) {01943890} <verb.motion> chase#1, chase after#2, trail#2, tail#1, tag#4, give chase#1, dog#1, go after1#1, track#3 -- (go after with the intent to catch; "The policeman chased the mugger down the alley"; "the dog chased the rabbit")

20

WordNet DomainsWordNet Domains è una risorsa che rappresenta associazioni tra i synset di WordNet e un set di categorie estratto dalla Dewey Decimal Classification (DDC)

Questa estensione del WordNet originale risulta utile per molti scopi ed in particolare per la disambiguazione automatica di senso perché permette di collegare, attraverso l'attribuzione di appartenenza ad una o più categorie, synset che altrimenti risulterebbero completamente scollegati tra loro.

Ad esempio, in WordNet originale, synset come "doctor", "emergency room", "to operate" non sono collegati in nessun modo, mentre in WordNet Domains sono tutti e tre etichettati con l'etichetta "medicina".

21

Classificazione del testo

Il Classificatore da noi definito, lavora in una certa fase del processo di analisi del testo.

In particolare viene utilizzato nella classificazione dei documenti e in una fase di disambiguazione semantica.

Per quanto riguarda la disambiguazione distinguiamo in:

Disambiguazione Sintattica:

operata per mezzo di LinkGrammar tramite:

– POS (part of speech) tagging

– Identificazione di relazioni tra i termini (linkage)

Disambiguazione Semantica:

– Identificazione termini composti

– Identificazione dei possibili sensi dei termini (WSD, Word Sense Disambiguation)

+ Classificazione del testo

22

DART semantic classifier

Tassonomia di riferimento derivante da WordNet Domains (subset di 160 ca. categorie del DDC)

Differenti fasi: Parsing del testo contenuto nelle pagine Web Analisi e disambiguazione sintattica del testo Analisi Semantica:

Disambiguazione semantica attraverso l’estrazione e l’identificazione dei sensi “effettivi” delle parole (synset) utilizzate nelle frasi del documento per mezzo di una specifica funzione di densità

Assegnazione delle categorie di riferimento al documento

Alcuni esempi di classificazione

24

Jalapeno pepper

25

Classificazione del documento (1)

2,4gastronomy

6,5metrology

20,73chemistry

1,89linguistic

2,00nautical

3,2administrat.

5,5plants

7,3biology

17,77medicine

0,99tourism

1,41animals

1,45politics

0,94quality

0,87person

26,89geography

%categoria

26

Jam session

27

Classificazione del documento (2)

2,82publishing

3,69person

10,25play

2,29art

2,29sociology

3,30quality

3,56military

4,02linguistics

5,24time period

2,09economy

2,18chemistry

2,20gastronomy

1,72Telecomm.

1,44theatre

52,83music

%categoria

28

Jellyfish

29

Classificazione del documento (3)

1,06linguistics

2,17person

39,67biology

0,91food

1,06military

1,78geography

2,12chemistry

2,33gastronomy

4,3anatomy

0,73music

0,79economy

0,88quality

0,071medicine

0,071psychology

40,71animals

%categoria

Arricchimento della Rete semantica di WordNet

Training Setper Classificatore

Statistico

DART Classificatore Semantico

Wikipedia (~ 1,75 milioni di pagine)

Rete semantica di concetti

di riferimento

31

Concetti legati a Jellyfish

invertebrates classnervous system

zooplankton

digestivesystem

epidermishydrodynamic misnomer

Hydrozoa

brain

fish

tentacles

oceanGreek

RhizostomaeRhopalia

mesoglea

phylum Cnidaria

Cubozoa

Cnidocytes

skyphos

gastrodermis Jellyfish as animal

Classificazione in Contesti Specializzati

33

La classificazione ottenuta tramite WordNet Domains contiene categorie generali non specializzate

Adottare un Theasurus e/o una Tassonomia specialistici.

L’algoritmo di classificazione in uso nel contesto specializzato è il medesimo del contesto generale.

Viene eseguito un mapping semantico tra la Tassonomia specialistica e quella generale.

Classificazione in contesti specializzati

34

Classificazione

(GeoNames)

Classificazione

(GEMET)

Classificazione in un contesto specializzato geografico

GEMET (GEneral Multilingual Environmental Thesaurus) contiene 6.562 termini classificati

GEONAMES database free che contiene oltre otto millioni di nomi geografici georiferiti

DART Semantic Classifier

35

RiferimentiAllen, “Natural Language Understanding”. The Benjamin/Cummings Publishing

Company, Inc, Redwood City, CA, 2nd edition, 1995

GEneral Multilingual Environmental Thesaurus – GEMET http://www.eionet.europa.eu/gemet/

Jurafsky : D.Jurafsky, J. H. Martin: Speech and Language Processing,

Prentice-Hall, 2000 B. Magnini, C. Strapparava, G. Pezzulo, A. Gliozzo. The Role of Domain Information in

Word Sense Disambiguation, Natural Language Engineering, special issue on Word Sense Disambiguation, 8(4), pp. 359-373, Cambridge University Press, 2002.

J. Nogueras-Iso, F.J. Zarazaga-Soria, J. Lacasta, R. Tolosana, P.R. Muro-Medrano "Improving multilingual catalog search services by means of multilingual thesaurus disambiguation" Proc. of the 10th EC-GI & GIS Workshop ESDI: The State of the Art, Varsovia (Polonia), Jun. 2004

D.D. Sleator, D.Temperley, “Parsing English with a Link Grammar”, in Third International Workshop on Parsing Technologies, 1993.

WordNet, http://wordnet.princeton.edu

36

MediaDART (Media Distribution, Adaptation

and Retrieval Toolset)

37

Sommario

il framework mediaDARTla ricerca di contenuti: il problema di basele metodologie per la personalizzazione della ricerca di contenuti

alcuni cenni alle metodologie collaborativeun servizio per la ricerca personalizzata di contenuti multimediali per mediaDART

38

Il framework MediaDART (Media Distribution, Adaptation and Retrieval Toolset)

mediaDART è un framework per la costruzione di servizi per la gestione di grosse collezioni di media

principali obiettivi: fornire strumenti di retrieval orientati agli utenti valorizzare la partecipazione degli utenti offrire un delivery scalabile e a basso costo fornire strumenti di personalizzazione dei contenuti

aspetti chiave: content model configurabile, tagging, tassonomie gestione delle risorse scalabile e decentralizzata delivery p2p, adattamento concorrente delle risorse recommendation, composizione

39

Il framework MediaDART: l’architettura

tagging (folksonomies), content model,tassonomie, retrieval, recommender, gestione licenze

lookup basato su DHT,storage e replica risorse, transcoding,adaptation, feature extraction, composizione, delivery p2p, streaming

presentation, business logic, CMS, ...

m-net

m-hub

application layers

web services

commands

me

dia

DA

RT

40

La ricerca di contenuti: il problema di base

La quantità di contenuti attualmente accessibili tramite le tecnologie a larga banda richiede strumenti che facilitino l'individuazione delle risorse di maggior interesse.

Le metodologie che tengono conto degli interessi di un utente specifico permettono una ricerca di tipo personalizzato (recommender systems)

41

Le metodologie per la ricerca personalizzataI parametri in gioco:

il tipo di contenuti descrittori degli oggetti (metadati) descrizione degli utenti disponibilità di una usage history disponibilità di un feedback esplicito

Una possibile classificazione (Burke 2002):

collaborative content-based demographic utility-based knowledge-based metodi ibridi

42

Tecniche collaborativeConsiderano le preferenze di una collettività di utenti aventi caratteristiche simili

vantaggi: permettono di proporre item out of the box si comportano bene nel caso di oggetti complessi che variano poco,

come contenuti musicali e film

svantaggi: Problema di ramp-up (nuovo item, nuovo utente) difficoltà di funzionamento nel caso di pochi utenti e molti item

algoritmi comunemente utilizzati: k-NN item-based (amazon.com) classificatore Naïve-Bayes ecc.

43

Tecnica collaborativa item-based (Sarvar et al. 2001)

…R1,1 R1,2

… R1,i… R1,j

… R1,n

R2,1 R2,2… R2,j

… R2,n

… … …

Ru,1 Ru,2… Ru, i

… Ru,j… Ru,n

…… …… …

… … ……… …… …

Rm-1,1 Rm-1,2… Rm-1,i

… Rm-1,j… Rm-,n

Rm,1 Rm,2… Rm,i

… … Rm,n

items

user

s

Deriva dagli algoritmi k-Nearest Neighbor; l'input è la matrice user-item dei rating R, ma si basa sulle similitudini tra item

metodo adottato con buoni risultati da amazon.com (Linden et al. 2003)

la parte computazionale più onerosa (calcolo delle somiglianze tra item) può avvenire off-line

si possono applicare vari metodi per il calcolo della somiglianza tra item (coseno, Pearson, ecc.)

una volta ottenuta la matrice delle somiglianze si effettua il calcolo della predizione

Sulla base dei valori di predizione si propone un set di item all’utente

44

Lavora con una serie di descrittori del profilo degli utenti (non su un solo valore) che sono usati come attributi di input

Semplicità computazionale

permette di operare a livelli accettabili anche quando sono disponibili informazioni incerte o incomplete

Tecniche collaborative: classificatore Naïve - Bayes

f1

f2

C

. . . fn

P(Ci|x)= (Ci)P(x|Ci)/P(x)

45

Un servizio per la ricerca personalizzata di contenuti multimediali per MediaDART

46

Riferimenti

Blanco-Fernandez Y., Pazos-Arias J.J., Gil-Solla A., Ramos-Cabrer M., Barragans-Martinez B., Lopez-Nores M., “A Multi-Agent Open Architecture for a TV Recommender System: A Case Study using a Bayesian Strategy”, Proceedings of the IEEE Sixth International Symposium on Multimedia Software Engineering (ISMSE’04), pp. 178-185, Dec. 2004.

Burke R., “Hybrid Recommender Systems: Survey and Experiments”, User Modelling and User-Adapted Interaction, 12, pp. 331-370, 2002

Linden G., Smith B., York J., “Amazon.com Recommendations”, IEEE Internet Computing, pp. 76-80, January-February 2003.

Sarwar B.M., Karypis G., Konstan J.A., Riedl J., “Item-based collaborative filtering recommendation algorithms”, Proceedings of the 10th International World Wide Web Conference (WWW10), Hong Kong, May 2001.