Università degli Studi del Molise
Tesi di Laurea in Informatica
Applicazioni di modelli matematici
alla ricerca semantica
Candidato
Dario Di Nucci
130804
Relatore
Prof. Giovanni Capobianco
Contesto applicativo
EVOLUZIONE DI INTERNET
Internet è una rete di computer
mondiale ad accesso pubblico che
attualmente rappresenta il principale
mezzo di comunicazione di massa.
I suoi utenti nel 2010 hanno raggiunto
quota 1,97 miliardi in crescita del 14%
rispetto all’anno precedente.
Il numero dei siti web nel 2010 ha
raggiunto quota 255 milioni, di cui 21,4
aperti nell’ultimo anno.
Contesto applicativo
INFORMATION RETRIEVAL
Cosa è?
Insieme delle tecniche atte al recupero
mirato dell’informazione in formato
elettronico.
Cosa fa?
Le tecniche di IR basate su modelli
vettoriali, applicano il concetto di
somiglianza testuale tra una base di dati e
una query, restituendo una serie di
documenti pertinenti.
Modelli matematici più importanti?
 Vector Space Model
 Latent Semantic Indexing
 …
Applicazioni più note?
Motori di ricerca.
Contesto applicativo
VECTOR SPACE MODEL
Dati due vettori:
 𝑄, rappresentante una query
 𝐷, rappresentante un documento
la loro similarità può essere calcolata
attraverso il coseno dell’angolo 𝜃 ,
compreso tra essi.
𝑆𝑖𝑚𝑖𝑙𝑎𝑟𝑖𝑡𝑦 (𝐷, 𝑄) ∈ [−1,1].
Contesto applicativo
LATENT SEMANTIC INDEXING
Problema: l’utente va alla ricerca delle informazioni basandosi su concetti e non
su singole parole.
Il cuore del LSI è rappresentato dalla decomposizione ai valori singolari (SVD).
𝑿
𝑼𝟎
𝜮𝟎
𝑽𝟎
La matrice Σ0 rappresenta i concetti ordinati in ordine di importanza.
Motivazioni
PROBLEMATICHE COMUNI
Nella fruizione dei documenti presenti sul web è
fondamentale per l’utente un motore di ricerca che
restituisca risultati corretti.
Nella sua realizzazione tre problemi che sicuramente
incidono negativamente sulla bontà dei risultati sono:
 polisemia
 sinonimia
 query malformate
Motivazioni
POLISEMIA
Molte parole hanno più di un significato, quindi una query potrebbe
condividere dei termini con un documento, sebbene quest’ultimo non sia
rilevante.
Conte
Motivazioni
SINONIMIA
Esistono diversi modi per esprimere uno stesso concetto; ciò implica che
una query potrebbe non condividere termini con un documento, sebbene
quest’ultimo sia rilevante per la query stessa.
Automobile
Macchina
Auto
Motivazioni
QUERY MALFORMATE
Spesso l’utente inserisce, per errore, query non valide o che non
rappresentano bene l’informazione ricercata.
Conta
Obiettivi
PROFILING
Migliorare l’accuratezza dei risultati forniti da un motore
di ricerca, attraverso il profiling degli utenti.
Profiling?!
Attraverso le query fornite dall’utente e i risultati da
questi selezionati, il sistema acquisisce esperienza.
In questo modo restituisce risultati con un grado di
correttezza crescente.
docs Hound
INTRODUZIONE
E’ stato realizzato un motore di ricerca basato su una nota libreria di
Information Retrieval, Lucene.
Lucene è un progetto open source promosso dalla Apache Software
Foundation.
docs Hound
INDEXER
Si occupa di analizzare le pagine web.
Per ogni documento:
 estrapola informazioni testuali
 individua le categorie inerenti
 aggiorna le definizioni delle categorie
Ogni categoria è identificata da un vocabolario, costituito da
un insieme di termini.
docs Hound
PROFILING UTENTE
Ad ogni utente è associato un
profilo di ricerca, sotto forma di
distribuzione di probabilità.
Il valore della preferenza di una
categoria aumenta seguendo
l'andamento di una funzione
logistica.
I valori delle categorie non scelte
sono decrementati in modo
proporzionale.
docs Hound
FUNZIONE LOGISTICA
Scelte occasionali per una
categoria modificano soltanto
lievemente il profilo, mentre
scelte consecutive hanno effetto
via via maggiore.
1.0
0.8
0.6
0.4
Quando la preferenza per una
categoria raggiunge un valore
sufficientemente più elevato
rispetto alle altre, si stabilizza su
tale posizione.
0.2
0.0
0.0
0.2
0.4
0.6
0.8
1.0
docs Hound
SEARCHER
Restituisce le pagine web ordinandole per punteggio.
Il punteggio è calcolato in funzione dell'attinenza della
pagina web con la query e il profilo dell'utente.
In particolare:
punteggio = punteggio query * (1 + punteggio profilo)
Per ridurre i problemi causati da query malformate, il
parser delle query applica a queste un grado di casualità
utilizzando tecniche fuzzy.
docs Hound
TESTING
Utente 1
Utente 2
Utente 3
Utente 4
Utente 5
Query 1
Query 2
Query 3
Query 4
Query 5
1
1
0
3
1
-2
1
1
0
1
1
0
1
1
0
1
1
0
2
2
0
1
1
0
1
1
0
2
2
0
1
1
0
1
1
0
2
1
-1
2
1
-1
1
1
0
3
2
-1
1
1
0
2
2
0
2
1
-1
1
1
0
1
1
0
1
1
0
1
1
0
2
1
-1
1
1
0
Tot diff
-1
-2
-1
-3
0
CONCLUSIONI
 Al termine della sperimentazione si può affermare
che le tecniche di profiling sono una buona
soluzione per il problema della polisemia.
 Il problema delle query malformate è stato
mitigato applicando un grado di casualità ad esse.
SVILUPPI FUTURI
 Integrazione di un crawler nel sistema al fine di
renderlo operativo.
 Miglioramento della categorizzazione di utenti e
pagine attraverso una crescente accuratezza dei
vocabolari che ne costituiscono le definizioni.
 Gestione automatica della funzione logistica in base al
numero di categorie.
 Testing approfondito con un maggior numero di utenti.
Grazie per l’attenzione