2.1
Sistemi di
Information Retrival
I sistemi di Information
Retrival, o I.R.S., sono quelle tecnologie
sviluppate all’interno del settore informatico mirate alla risoluzione ed al
trattamento dei problemi relativi alla memorizzazione, rappresentazione e
reperimento di documenti.
Questa
definizione, tuttavia, potrebbe risultare ingannevole, poiché sembrerebbe
limitare i target possibilmente oggetto di operazioni di I.R. al solo trattamento di documenti testuali, mentre l’applicazione di sistemi di Information Retrival non è così ristretta, ed è semplicemente una concausa di
motivi pratici e storici ad aver comportato che la maggior parte dei sistemi e delle
tecniche siano di fatto relativi a corpora testuali.
Storicamente, le applicazioni di I.R. nacquero per far fronte ai
problemi sollevati dalla gestione di letterature specialistiche, più o meno vaste,
e per soddisfare le richieste effettuate dagli utenti interessati a reperire
informazioni rilevanti rispetto alle loro esigenze.
In un I.R.S.
è importante considerare due qualità derivate dalle tecnologie
implementate:
·
l’efficienza, ovvero come il sistema si comporta in termini di tempi di
risposta, uso della memoria, ecc…,
·
l’efficacia (effectiveness),
ovvero quanto il sistema è in grado di soddisfare l’utente fornendogli le
(sole) informazioni rilevanti e semplificando il più possibile la sua attività
di indagine conoscitiva.
Il problema di valutare l’efficacia di un I.R.S. non è di facile soluzione, in
quanto include diversi aspetti soggettivi.[1]
|
Si supponga, ad esempio, di poter definire per ogni documento in una data collezione se esso sia rilevante o meno in riferimento ad una data interrogazione,[2] e di schematizzarne il risultato sia del retrival sia della pertinenza alle
interrogazioni: l’insieme dei documenti appare suddiviso in quattro
sottoinsiemi, dove la divisione ( e quindi la classificazione di un documento)
dipende dal fatto che lo stesso sia stato reperito o meno dal siste |
|
ma di I.R.S. e
dalla sua rilevanza nei confronti della query,[3]
come schematizzato nel grafico.
I
documenti Ret
& NRel chiamati anche Falsi Positivi, costituiscono il cosiddetto rumore,
che ogni I.R.S. dovrebbe cercare di
ridurre al minimo: tali documenti sono anche detti false drops o false alarms o ancora false hits.
I documenti NRet & Rel, viceversa, sono quelli per cui il sistema rimane
silenzioso ed anch’essi, per i quali si usa anche il termine false dismissals, dovrebbero
essere portati al minimo: in conclusione un
I.R.S. efficace dovrebbe tendere a non produrre Falsi Positivi e false dismissals.[4]
Le due
misure più comuni per quantificare l’efficacia di un I.R.S. sono allora Recall e Precision:
|
Recall: |
R = # Ret
& Rel #RelTot |
|
Precision: |
P = # Ret & Rel #RetTot |
In genere, aumentando il Recall la Precision diminuisce e viceversa, seguendo un andamento graficamente
rappresentato di seguito:
|
|
I.R.S.
ideale : (R,P) = (1,1) |
Si noti che, mentre la precision è calcolabile a partire dal risultato (#RetTot), così non è per il recall,
che richiede di conoscere quanti sono i documenti rilevanti in tutta la
collezione (#RelTot).
Supponendo di conoscere #RelTot, l’efficacia di un I.R.S. viene normalmente valutata misurando la precision a diversi livelli di recall,
ovvero è necessario calcolare quanti documenti si debbano reperire (#RetTot) affinché il risultato contenga una frazione pari a R nei documenti rilevanti presenti nel corpus esaminato (#RelTot).
|
P = R x |
#RelTot #RelTot |
È ovvio che la valutazione completa deve essere
eseguita su un certo numero di queries,
e che essse debbano essere significative, avendo quindi i presupposti necessari
per cui al termine dei test sul sistema di
I.R. siano disponibili giudizi rilevanti.
Ogni I.R.S. si basa quindi su una tecnica
di recupero delle informazioni, ovvero su un meccanismo che permette di
confrontare la richiesta, espressa in uno specifico linguaggio, con le rappresentazioni
dei documenti, coincidenti con i documenti stessi (rappresentazione diretta)
o date da surrogati (rappresentazione
indiretta) più o meno
efficiente, e tutti gli sforzi compiuti sia nello studio dei problemi
direttamente implicati, sia riguardo a tutto quell’insieme di architetture
indirettamente coinvolte nei sistemi di I.R.,
sono dunque indirizzati verso l’incremento della sua efficacia.
In base
alle soluzioni adottate sia nelle strutture relativa alla ricerca ed
all’estrazione dei documenti in base ad una query,
sia nelle architetture tanto degli I.R.S. quanto delle base di dati
contenenti i corpora di documenti, è
possibile individuare diversi aspetti generali in base ai quali si comportano i
sistemi di I.R., e questi aspetti
possono essere ricondotti a:
3.
Modello concettuale:
Il modello concettuale definisce la filosofia di fondo di un I.R.S., ovvero attorno a quali principi
generali si è sviluppato ed opera il sistema.
L’uso
di un modello concettuale influenza e
determina principalmente il linguaggio di
interrogazione, la rappresentazione
dei documenti, la struttura dei file,
i criteri di reperimento dei documenti.
I modelli concettuali sono a loro volta divisibili in
alcuni sottomodelli:
·
Booleano: i
documenti sono rappresentati da insiemi di termini chiave (keywords),
estratti manualmente e/o automaticamente dal testo, e le richieste sono keyword
connesse da operatori logici; sono i sistemi più diffusi, a motivo della loro
semplicità ed efficienza, ma possono presentare problemi in termini di
efficacia,
·
Booleano esteso: caratterizzato
per la presenza di pesi (weight) associati ai termini di un documento,
che ne riflettono l’importanza relativa all’interno del documento; permette inoltre
di adottare criteri di ordinamento (ranking) dei documenti reperiti.
La
pesatura dei termini in un sistema di IR,
potrebbe procedere come quanto esemplificato di seguito: la query
controllo delle piogge acide nella Foresta Nera potrebbe venire
riformulata come Controllo AND Pioggia AND Acido AND Foresta Nera e
porterebbe a reperire i documenti che contengono tutti i termini della query indipendentemente da:
-
l’importanza relativa
dei termini stessi nella query (utile
se, ad esempio, la query avesse
contenuto relazioni di tipo OR)
-
l’importanza dei
termini nei documenti (utile in fase di indexing e di ranking)
In
molti casi non è ben chiaro cosa specificare nella query, e questo può portare o a produrre query troppo generiche (precision
bassa) o troppo specifiche (recall basso) come mostrato di seguito seguendo il precedente esempio:
·
specifica: algoritmi di allocazione dati su reti di calcolatori che non genera alcun risultato (no matches),
·
generica: algoritmi per reti di calcolatori che genera molto materiale retrived (400 matches)con molto
rumore relativo rispetto alle intenzioni di ricerca dell’utente.
Esistono
molti criteri di pesatura dei termini; il più noto è tf.idf, ovvero term
frequency and inverse document frequency.[5]
Altro
modello da annoverare è il così detto M.M.M.,
ossia Mixed Min and Max.[6]
M.M.M.,
nonostante non sia il migliore tra i modelli Booleani estesi in
termini di aumento medio di precision, ha il vantaggio di essere quello meno
computazionalmente oneroso.
Ad
esempio il modello detto di P-norm ha
il pregio di considerare tutti i termini di un documento, e non solo quelli con
peso minimo e massimo.
I
miglioramenti in precision vanno dal 79% al 210%; il modello può
risultare computazionalmente costoso a causa delle operazioni con
esponenziali richieste.[7]
·
Vector space: i
documenti vengono visti come punti in uno spazio le cui coordinate sono
tutte le keyword gestite dal sistema,
e i pesi determinano il valore di tali coordinate.
Nel
modello Vector Space sia il documento
che la query sono vettori (non si fa
pertanto uso di operatori Booleani) i
cui componenti sono i pesi dei termini usati per l’indicizzazione.
Per
calcolare la similarità tra una query:
Q =
(qw1,...,qwi,...,qwn)
ed un
documento:
docj =
(w1,j,...,wi,j,...,wn,j)
si
considera la direzione dei due vettori, ovvero il coseno dell’angolo tra i
due vettori.[8]
·
Probabilistico: assegna
pesi ai termini considerando la loro probabilità di essere presenti in
documenti rilevanti ad una data query.[9]
·
Clustering: i documenti sono organizzati, sulla base del loro contenuto,
in cluster omogenei
secondo una certa metrica. Il sistema ne può guadagnare sia in termini di efficienza,
confrontando una query solo con i rappresentativi
dei cluster, sia in termini di
efficacia, considerando che l’associazione in cluster fornisce informazioni
sulla rilevanza dei documenti.
Un cluster è un gruppo omogeneo di documenti che sono tra loro più fortemente associati tra loro di quanto lo siano con documenti in altri gruppi; l’efficacia dei cluster si basa sulla cosiddetta clustering hypothesis: documenti fortemente associati tendono ad essere rilevanti o meno per una stessa query.
In
una ricerca basata su cluster, il
confronto avviene in due fasi, considerando prima i soli documenti
rappresentativi dei cluster (centroidi) e quindi i
documenti nei soli cluster
selezionati.
Il clustering può essere inoltre di tipo gerarchico (organizzazione ad albero dei
cluster) o a singolo livello (con overlap tra cluster o
meno).[10]
·
String search: la
tecnica di recupero opera semplicemente con algoritmi di pattern-matching su
query e documenti.
2. Strutture
dei files: il
sistema può limitarsi a gestire semplici files sequenziali nel caso di ricerche
di stringhe, oppure può fare uso di diverse tipologie organizzative tra cui le
più importanti possono essere riassunte nelle due seguenti:
·
Inverted File: l’inverted
file è un indice ordinato e per ogni keyword riporta la lista dei documenti che
la contengono (eventualmente anche la/le posizione/i nel testo),
·
Signature File: un signature file
, anche S.F., memorizza, sotto forma
di stringhe binarie, delle astrazioni (o signature) dei
documenti, che vengono confrontate con una corrispondente signature della query.
La tecnica di recupero basata su S.F. è di tipo booleano (documenti
che contengono i termini nella query),
ma non ha un grado di precisione elevato.
3.
Operazioni sulle query : Esistono I.R.S. che accettano
anche input in linguaggio naturale; in questo caso vi è essenziale un’attività di parsing che
estrae i termini rilevanti e li connette attraverso opportuni operatori (Booleani).
Il tipo di operazione sulla query può essere distinto in:
·
Semplice: il
sistema di I.R. manipola la stringa
di query (tramite un parser) ricostruendola in un’espressione booleana le cui relazioni
dipendono dalle opzioni, se fornite, di ricerca all’interno del database;
·
Feedback: un I.R.S. può
anche fornire meccanismi di query feedback, attraverso i quali i
documenti reperiti e giudicati rilevanti dall’utente vengono usati per
riformulare la query.
L’idea
sulla quale si basano i meccanismi di query
feedback, detti anche di relevance feedback, consiste nel
modificare la query usando
l’informazione acquisita dall’utente (primi documenti estratti dalla query originale), sulla rilevanza dei
documenti reperiti.
|
|
La
parte di documenti estratta tramite la prima query, in pratica, viene utilizzata come una seconda query per una ulteriore interrogazione
verso i corpora. [11]
Applicazioni
di questa tecnica (o con tecnologie simili) portano sperimentalmente a
miglioramenti nella precision, per
determinati livelli fissati di recall,
che possono variare dal 40% al 60%, come raffigurato nel grafico.
4.
Operazioni sui
termini: la
prima operazione che un I.R.S. deve eseguire consiste nell’attività di individuazione di keywords (automatica e/o manuale) denominata indexing.
Al fine di migliorare l’efficacia del sistema sono stati
implementate diverse tecnologie, tra le quali è doveroso citare:
·
Stemming: i
termini vengono ricondotti ad una radice comune, ad esempio rimuovendo prefissi
e suffissi; lo stemming migliora il recall
e riduce la dimensione degli indici.
Un particolare processo di Stemming può generare una indicizzazione
linguistica dei documenti, il cui processo è chiamato Linguistically Motivated Indexing, o L.M.I..[12]
·
Ontologie e Thesaurus: si fa uso di un vocabolario di
sinonimi e di termini correlati.
Il thesaurus è lo strumento terminologico
principe per l’organizzazione della conoscenza; utilizzato soprattutto per la
classificazione e consultazione dei grandi archivi bibliografici in ogni
settore scientifico letterario o artistico, è la chiave per l’accesso razionale,
ad esempio, alle principali biblioteche ed ai relativi sistemi documentari.
Ognuno
di questi grandi sistemi è dotato di un proprio thesaurus, le cui dimensioni contenuto e struttura sono stati
sviluppati in funzione del rispettivo patrimonio e dei propri criteri
organizzativi.
Il thesaurus
è dunque un soggettario standardizzato all'interno del quale un
concetto viene sempre ricondotto ad un unico termine, indipendentemente dalle
varianti linguistiche che diversi autori, ad esempio, potrebbero utilizzare per
rappresentarlo.
Esso,
in fase di indicizzazione, è lo strumento utilizzato dai catalogatori, umani,
automatici o semiautomatici, per attribuire i soggetti ai records bibliografici
al fine di rappresentarne il contenuto in modo univoco.
In
fase di ricerca è uno degli strumenti che consentono il livello piu' alto di
controllo dei termini che andranno a comporre la strategia di ricerca.
Il thesaurus è quindi una struttura che
organizza le complessità delle terminologie di un linguaggio e provvede alla
rappresentazione delle relazioni concettuali tramite un’ontologia.
Un’ontologia può essere definita come un sistema di concetti rilevanti per una modellizzazione di un dato
dominio di conoscenza, e dunque consiste in una collezione di concetti
organizzata secondo diversi tipi di relazioni, ed secondo una classificazione
gerarchica dei termini.
Le ontologie, se adeguatamente sviluppate,
estese e dettagliate, permettono sia applicazioni soddisfacenti per operazioni
di IR, sia per applicativi di Machine Translation, ma la
caratteristica che le distingue è la qualità di essere language-neutral, poiché esse, se ben realizzate, non contengono
parole, ma puri concetti. [13]
Un thesaurus prevede quindi collegamenti semantici
espliciti tra termini.
Un
esempio di thesaurus embrionale e
rudimentale può essere fornito dalla guida per la consultazione delle Pagine Gialle: i termini usati per
l’identificazione delle categorie merceologiche elencate nelle pagine gialle
consiste in un indice nel quale sono elencati tutti termini ufficiali di questo
linguaggio che, per le sue limitazioni e caratteristiche apposte, è detto
linguaggio limitato.
Le Pagine Gialle, dunque possono essere
considerate come un indice in cui sono elencati tutti i termini ufficiali del suddetto
linguaggio controllato.
I thesauri possono essere monolingua, e ve n’è un numero discreto,
e multilingua, dei quali solo adesso
se ne conta un certo incremento, soprattutto in un contesto europeo.
·
Stoplist: lista
di parole comuni che non hanno alcun valore selettivo e vengono pertanto
eliminate in fase di indexing;[14]
·
Weighting: le
keywords vengono pesate numericamente
facendo uso di informazioni sulla distribuzione statistica dei termini;
5.
Operazioni sui documenti: un documento può ovviamente contenere parti strutturate, quali autore,
data, ecc..; considerando ciò, un I.R.S. può
eseguire le seguenti operazioni su ognuna delle strutture presenti:
·
parsing: individua
i campi costituenti ed i relativi valori
·
field masking: “occultamento”
di campi (proiezione)
·
ranking: ordinamento
sulla base della rilevanza[15]
·
clustering: classificazione
in cluster.[16]
Queste le principali funzioni e strutture di cui deve essere dotato un I.R.S. efficiente; di seguito saranno esaminate nel dettaglio alcune caratteristiche ed applicazioni avanzate e specializzate.
