Corso di information retrieval

[diegofio]

LEZIONE #5: SOTTOFASI DELL'INDICIZZAZIONE

Vediamo ora più in dettaglio la fase di indicizzazione: ricordo che attraverso essa possiamo, a partire dalla collezione dei nostri documenti, costruire una struttura dati contenente le parole chiave per ciascuna delle quali è presente la lista dei documenti in cui essa è presente. Le parole chiave sono dette descrittori o termini indice.
Questa fase si rende necessaria in quanto sarebbe impossibile per il sistema scandire per ogni richiesta (e spesso sono tante e distanziate di breve tempo) tutta la collezione alla ricerca delle informazioni richieste dall'utente: con l'indicizzazione abbiamo una struttura snella (parte di essa è in RAM) e veloce, a patto di perdere in precisione.

L'indicizzazione è un processo che ha come input la collezione dei documenti e come output la lista dei descrittori che nel miglior modo possibile descrivono l'informazione contenuta nella collezione. A sua volta essa si divide in sottofasi.

La prima è l'analisi lessicale: attraverso essa il testo viene "messo in ordine": formalmente dal testo grezzo del documento vengono estratte le stringhe che potenzialmente contengono descrittori; a tal proposito sono tolti i segni di punteggiatura e gli spazi, e viene tutto uniformato ad un unico alfabeto; inoltre, a seconda delle scelte di progetto, possono essere tolti numeri e date, o comunque per questi elementi viene definita una formattazzione comune; anche le maiuscole solitamente vengono convertite nelle corrispondente lettera minuscola.

Dopo l'analisi lessicale abbiamo un testo sicuramente più "pulito" ed omogeneo e siamo perciò pronti alla rimozione delle parole comuni; il concetto di "parole comuni" ("stop words") è piuttosto interessante: come sappiamo in ogni lingua ci sono dei termini che vengono utilizzati con maggiore frequenza rispetto ad altri, ma questo non basta, infatti perchè sia tolta dal documento è necessario che tale parola non apporti nessuna informazione. Ad esempio articoli e preposizioni quasi sempre rientrano in questa categoria e infatti spesso sono eliminati dal testo restituito dall'analisi lessicale. Esiste, per ogni lingua, una lista di parole frequenti su cui questa fase si basa per liberare il testo da termini che di fatto risultano inutili.

A questo punto il testo sarà una sequenza di parole che verranno ulteriormente semplificate nella fase dello stemming: in questo caso si riducono alle radici le parole originali, allo scopo di far coincidere allo stesso termine diverse varianti. Un classico esempio è dato dalla radice "comput" che può coincidere a "computer", "computing" e ad altre varianti: quello che avviene è che ad ogni occorrenza di "computer" o "computing" la parola viene sostituita da "comput". La ricerca di "computer" potrà restituire anche documenti contenenti solo "computing" (anche se in alcuni sistemi più avanzati viene mantenuta a parte una tabella con le varianti) Questo viene fatto perchè spesso le varianti di una stessa parola radice si riferiscono tutte al medesimo ambito, se non sono addirittura sinonimi. In questo caso si vede come si accetta di perdere dell'informazione ("computing" non è proprio la stessa cosa di "computer") al fine di rendere più snello il testo, ricordandosi che alla fine dobbiamo avere una lista di parole che ben rappresentano ciò che in esso è contenuto.

Alla prossima con le altre sottofasi.

[Ibanez89]

he, qui si vende la maggior differenza tra un motore di ricerca o un'altro nel dare risultati pertinenti? o sbaglio?

[diegofio]

la fase di indicizzazione è sicuramente fondamentale soprattutto nei motori di ricerca non web, quelli in cui i documenti non sono degli ipertesti per intenderci, non contengono link.
queste tre prime sottofasi che ho spiegato in realtà sono piuttosto standard nella loro implementazione: la lista delle stopword è nota per tutte le lingue, l'analisi lessicale è banale, si può agire sullo stemming rendendolo più efficace.
se non le implementi di sicuro il motore trova le pagine che vuole l'utente, il problema è che molto probabilmente ne troverà anche molte altre che non interessano.
le differenze si possono vedere parecchio nella pesatura dei termini che spiegherò nella prossima.

[Ibanez89]

perfetto

[diegofio]

LEZIONE #6: SOTTOFASI DELL'INDICIZZAZIONE (2)

Continuiamo a parlare delle sottofasi di sta benedetta indicizzazione; ricordo che fino ad ora a partire da un testo siamo riusciti a formattarlo in modo opportuno attraverso l'analisi lessicale, a togliere le parole che non apportano informazione e a ridurre le parole, ove possibile, alle corrispondenti radici: come già sottolineato, è importante notare che stiamo per forza perdendo informazione, in quanto il testo non è più lo stesso di prima, sarà più breve e difficilmente comprensibile da un essere umano.

La fase successiva è la composizione dei termini indice: sappiamo che dobbiamo arrivare alla fine ad avere una serie di termini chiave che ben descrivono il contenuto del documento; un termine può essere una singola parola oppure una composizione di più di esse.
Il motivo per cui si compongono più parole (che ricordiamo a questo punto non sono sempre parole ma anche radici di parole) risiede nel fatto che se molto frequenti esse diventano una sorta di stop word: ad esempio in documenti che parlano di processori amd il termine "process" (ottenuto come radice di "processore" perde di gran parte del suo significato, perchè troppo spesso ripetuto all'interno dei vari documenti; si può ad esempio combinarlo con "dualcore" ottenendo "process dualcore" per evidenziare che quel documento parla di "process" (ovvio visto che siamo in documenti da amd) ma "dualcore", rendendo il termine indice più efficace nel rappresentare ciò che è presente nel documento.

Successivamente abbiamo la pesatura, ovvero il processo attraverso il quale si dà un peso al termine nel documento. La cosa più banale da fare è, dato un termine, assegnargli peso 1 se appare nel documento, 0 altrimenti.
Questo approccio può essere migliorato in modo semplice considerando il numero di volte che un termine appare nel documento, assumendo l'ipotesi secondo la quale se tale valore è grande, con alta probabilità il documento sarà rilevante per quel termine. Se in un documento appare molte volte il termine "process dualcore" si avrà più rilevanza rispetto a quel termine nei confronti di un documento in cui esso appare una sola volta.
Altro schema di pesatura più complesso è dato dall'essegnare al termine Tj il valore log(N)/nj dove N è il numero totale di documenti della collezione ed nj la frazione di essi che contiene il termine Tj.

Costruito l'indice abbiamo a disposizione una struttura dati per la collezione che raggruppa tutti i termini di tutti i documenti della collezione stessa ottenuti medianti le fasi appena descritte, ciascuno con il proprio peso per ognuno dei documenti della collezione, calcolato mediante la fase di pesatura.
E' su questa struttura che il sistema di reperimento fa affidamento, nessun altra informazione è da lui conosciuta sui documenti. E' evidente quindi la perdita di informazione: da dei testi piuttosto articolati abbiamo solo a disposizione una serie di parole chiave che più o meno bene ne descrivono il contenuto.

I processi di analisi lessicale, rimozione stop word e stemming vengono fatti anche sulla stringa di testo che costituisce l'interrogazione dell'utente al sistema, dalla quale quindi ricaviamo una serie di termini che saranno confrontati con quelli estrapolati dalla colleziione. Ottenute le varie corrispondenze (ovvero un termine appare sia nell'interrogazione che tra quelli ottenuti dalla collezione) ordiniamo in risposta i documenti che sono in corrispondenza, tenendo conto del peso di ciascun termine all'interno di ogni documento.

[Ibanez89]

adesso è tutto più chiaro

[diegofio]

LEZIONE #7: IL MODELLO BOOLEANO

A questo punto dovrebbe essere piuttosto chiamo il funzionamento di un sistema di reperimento dell'informazione: riassumendo, dai documenti della collezione si ricavano i termini (detti descrittori) che meglio rappresentano il contenuto di ciascun documento e li si inseriscono in una struttura dati che consente di associare ad ognuno di essi i documenti che li contiene; questo viene fatto mediante il processo di indicizzazione, spiegato negli ultimi due post. Lo stesso processo viene fatto anche sulla stringa di ricerca immessa dal'utente, e i termini estratti verranno messi in confronto con quelli dei documenti.
Ma come viene fatto questo confronto? Esistono diverse opportunità, o meglio diversi modelli di reperimento: qui descriveremo il più semplice ed immediato ovvero quello booleano.

Il modello booleano parte dall'ipotesi che una persona redige un documento inserendo al suo interno una serie di concetti ed idee che lei desidera espletare; al documenti (e quindi indirettamente a questi concetti) come sappiamo saranno associati dei descrittori, risultato della fase di indicizzazione. Il trucco è uqello di associare ogni descrittore ad un concetto. Quindi ad un descrittore (e quindi ad un concetto) saranno associati un insieme di documenti (tutti quelli che contengono quella parola e che si suppone trattino del concetto ad essa associato) mentre un documento potrà trattare di argomenti (concetti) differenti, contenendo al suo interno differenti descrittori.
Abbiamo una relazione molti-a-molti tra documenti e descrittori (concetti): non abbiamo introdotto nulla di nuovo rispetto a quanto detto in precedenza, solo il fatto che ad un descrittore è associato un concetto, un argomento che si suppone venga trattato nei documenti associati a tale descrittore. Se il descrittore è "Automobile" molto probabilmente i documenti associati tratteranno del concetto "automobile", in pratica parleranno d'auto.
Quindi ogni descrittore può essere associato all'insieme dei documenti che lo contengono e in cui è presente il concetto espresso dal descrittore.

Se a questo punto un utente sottomette al sistema una stringa di ricerca contenente un descrittore "Automobile" esso riceverà in risposta tutti i documenti presenti nell'insieme assocuato ad "Automobile". A partire dalla stringa di ricerca dell'utente vengono estratti alcuni descrittori, che saaranno presenti anche nei documenti. Ogni descrittore individua un insieme di documenti.

Poniamo di aver estratto dalla stringa di ricerca due descrittori, "Automobile" = t1 e "Moto" = t2 che individuano entrambi due insiemi di documenti. Il modello booleano mette a disposizione gli operatori AND, OR, NOT per legare tra loro insiemi di documenti associati a diversi descrittori. Così, se vogliamo tutti i documenti che non trattino di "Automobile" basterà fare NOT (t1), otteniamo in questo modo il complementare all'insieme dei documenti legati a t1 = "Automobile" ovvero tutti i documenti che non trattano di automobili, magari di moto.
Invece se vogliamo vedere tutti i documenti che parlano di "Automobile" e "Moto" basterà fare (t1) AND (t2), ovvero l'intersezione dei due insiemi di documenti di t1 e t2 nella quale saranno presenti documenti che trattano di entrambi i concetti.
Infine se vogliamo i documenti che trattano di una delle due cose, "Automobili" o "Moto" basterà utilizzare l'operatore OR tra t1 e t2, ovvero l'operazione di unione: nell'insieme risultante saranno presenti documenti che trattano di una delle due cose.

Questo solo per darvi l'idea di come funziona, non pretendo di essere stato completo.

[Ibanez89]

he, mi hai salvato agli esami, anche se nn facciamo informatica io ho voluto parlare della nascita di internet e la sua evoluzione, immagina la figura quando ho saputo rispondere alla domanda dell'esaminatrice esterna quando mi ha chiesto come funziona google

[diegofio]

grande, anche se sono stato utile per lo 0.05% sono molto contento

[Ibanez89]

grande, anche se sono stato utile per lo 0.05% sono molto contento

mha ho detto in breve, ma ho parlato molto dell'indicizzazione tutto acquisito grazie a te, quella domanda nn me l'aspettavo mica

[diegofio]

il corso sarebbe anche finito cioè ci sarebbe molto altro da dire ma non mi pare il caso.
Sappiate che oltre all'oramai vecchissimo modello booleano ci sono altri modelli molto più complessi e precisi, alcuni veramente interessanti.
Ad esempio nel modello vettoriale si associano dei vettori ai descrittori e se ne valuta la distanza nello spazio per vedere quanto due termini sono in relazione fra loro. questa intuizione, di associare vettori alle parole, secondo me è una genialata incredibile, è allo stesso tempo molto intuitivo ed elegante, anche se oramai è un metodo vecchio.
Insomma c'è moltissima ricerca in questa direzione soprattutto per oggetti multimediali: se ci pensate ad oggi si utilizzano i tag, che non sono altro che dei descrittori, ovvero dei termini che appunto descrivono il contenuto dell'oggetto. Beh sarebbe bello che in futuro fosse tutto più automatico, alla fine ad ora ci si deve appoggiare sempre al testo, quale è un tag, per descrivere un qualcosa che un testo non è, ma magari è una foto o un video o un file musicale.

Ci tengo a precisare che quanto scritto sinora non è nulla di astratto ma è quello che effettivamente si fa su tutti i motori di ricerca.
Molti strumenti ad esempio di desktop search svolgono esattamente queste operazioni, e addirittura tanti si fermano al vecchissimo modello booleano (per esempio mysql, che integra delle funzionalità di IR). Altri più evoluti invece si appoggiano al modello probabilistico, spesso (tra quelli GPL) implementando le librerie xapian.

Se volete posso come appendice descrivervi pagerank e hits, i due principali algoritmi utilizzati dai motori di ricerca; vi avverto che però è un pochino più difficile di quanto scritto ora, per carità niente di che però serve un piccolo sforzo.

[Ibanez89]

si dai continua visto il grande successo 9000visite

[diegofio]

ho molti parenti
vabbè spiegherò hits e pagerank

[Ibanez89]

ho molti parenti
vabbè spiegherò hits e pagerank

ottimo

edit: se se anche la nonna a leggere ora...

[diegofio]

LEZIONE #8: IL CONCETTO DI AUTOREVOLEZZA

Cominciamo ad estendere la nostra visione ad internet.
Come sappiamo il web è un insieme di ipertesti, ovvero pagine che al loro interno oltre al comune testo (ed immagini, video, eccetera) contengono anche dei collegamenti, detti link, ad altre pagine collegate alla prima in qualche modo.
Il tutto può così essere facilmente rappresentate mediante un grafo, i cui nodi rappresentano le singole pagine web, e gli archi che collegano fra loro diversi nodi (o anche lo stesso) si identificano nei link. Cliccando su un link passo da una pagina all'altra, da un nodo all'altro del grafo seguendo un preciso arco.
Va da se' che la comune navigazione di un utente costituisce un percorso all'interno di questo grafo, percorso che transita attraverso vari nodi (pagine) per mezzo di appositi archi (link).

Data questa visione schematica del web continuiamo con l'esposizione di una fondamentale differenza tra il reperimento dell'informazione "abituale" e quello sul web: nel primo caso il controllo della qualità di una pagina è fatto a monte, ovvero da chi inserisce i documenti nella collezione; un sistema di IR restituisce come risultato di una interrogazione dei documenti che ritieni pertinenti per le esigenze dell'utente senza preoccuparsi della loro qualità, proprio perchè si ipotizza che tale aspetto sia stato già verificato in fase di popolamento della collezione dei documenti. Inoltre spesso la collezione tratta un insieme omogeneo e limitato di argomenti.
Viceversa nel web non accade ciò: infatti chiunque può scrivere una pagina web e metterla online e in relazione con altre, anche inserendo materiale di bassa qualità. E' quindi necessario un controllo a posteriori della qualità delle pagine, proprio a causa dei niubbi o bimbiminkia che scrivono cavolate sui propri myspace: possibilmente tali pagine dovranno essere considerate dal motore come scoasse (spazzatura) mentre un sito come amdplanet cavolo dovrà essere visto come una figata pazzesca e messo tra i primi risultati. A differenza di prima inoltre la collezione (tutte le pagine web) costituisce, oltre che una quantità enorme di informazione, un insieme assai eterogeneo negli argomenti trattati, e come abbiamo appena accennato spesso con qualità differente.

La parola che ci manca è quindi "autorevolezza": essa in questo ambito è definita come la capacità di una pagina web di apportare nuova conoscenza all'utente. Questo, attenzione, non tanto per il suo contenuto informativo ma soprattutto per il grado di fiducia che altri utenti hanno riposto in essa. Ovviamente se gli utenti hanno grande "fiducia" in una pagina web non è che possiamo metterla in cima ai risultati anche se contiene una marea di cavolate, quindi la fiducia degli utenti (portatrice di autorevolezza) e il contenuto informativo (portatore di rilevanza) devono correre di pari passo: restituiremo pagine che apportino conoscenza all'utente (siano cioè per lui rilevanti) e la cui qualità sia verificata (siano autorevoli) mediante un processo che a breve andremo a vedere in dettaglio.