Lezioni 14

LEZIONE 14

Nella seguente lezione parleremo delle tecniche utilizzate nell’ Information Retrival per l’analisi di documenti di testo. La nostra prima esigenza, quindi, è quello di identificare le risorse disponibili sul web e per far questo possiamo fare riferimento allo standard URI che è uno standard che funziona piuttosto bene soprattutto perché è univoco e ha uno schema progressivo nella sua descrizione.
Abbiamo la necessità di aggregare insieme queste risorse, per far questo lo strumento più comunemente utilizzato è il link anche se sono disponibili diversi tipi di tecnologie, ad esempio le API, utilizzate per collegare insieme diversi tipi di documenti. Successivamente ci dobbiamo preoccupare di avere una descrizione delle risorse e in questa lezione ci concentreremo su un particolare tipo di descrizione che è quella testuale.
Se vogliamo descrivere le risorse potremmo utlizzare ad esempio il dominio dei nomi, che in casi ristretti potrebbe essere significativo ma spesso non lo è, oppure potremmo utilizzare la posizione topologica della rete, oppure un altro importante elemento che può essere utilizzato è quello di associare a una risorsa una descrizione in termini di attributi che essa possiede.
Un modo immediato per far questo è analizzare il testo e guardare di cosa parla la risorsa, è un approccio che ha dei suoi limiti: prima di tutto non tutte le risorse posseggono del testo, possiamo avere delle immagini o dei file audio per esempio, un altro limite sta nel fatto che la descrizione di una risorsa in effettuata in base al testo che essa contiene manca di meta informazioni che nono tutte le informazioni che sono legate alla risorsa, quelle più diffuse sono l’autore il titolo etc, ma ce ne sono altre che possiamo non riuscire a considerare.
Se vogliamo analizzare un testo il modo piu semplice per farlo è quello di considerare i termini contenuti al suo interno. Quindi avremo il nostro documento, composto da una serie di termini che siano almeno parzialmente delle buone connotazioni del nostro testo, ossia che ci permettano di descrivere le proprietà del testo che stiamo analizzando.
Le varie operazioni che dovremo svolgere sono:
- identificare i termini, ossia estrarli dal documento. Parliamo di tokenizzazione nel senso che si riduce a una forma semplice come se fossero tutti vari mattoncini che vanno a comporre il testo.
- Secondariamente possiamo applicare una serie di tecniche di semplificazione del nostro vocabolario e diminuire la dimensione dei dati.
- Dopodiché si inizia a descrivere questo documento come un vettore di termini, in sostanza l’insieme dei termini che abbiamo ritenuto sufficientemente significativi descrivere il nostro documento.
Quindi passiamo al calcolo della similarità dei vari documenti che ci permetterà di organizzarli secondo un ranking.
Ovviamente anche una query può essere vista come un vettore e quindi anche nel momento in cui vogliamo valutare una query non facciamo altro che calcolare la similarità tra una query e i vettori che descrivono il nostro documento, alcuni potranno avere un ranking più alto e altri un ranking più basso.
- Infine avremo il problema di crearci un indice dei nostri documenti per poterlo poi
interrogare in modo efficiente.

Quindi nella tokenizzazione elimineremo tutti gli elementi che non sono descrizioni testuali, elementi rappresentazionali o procedurali, si elimina la punteggiatura e le stopwords (termini meno significativi). La tokenizzazione può essere più o meno semplice in base ai formati che trattiamo, in HTML dovremo eliminare i tag, magari alcune informazioni contenute dovremo salvarle perché ci possono essere utili, ma generalmente andremo ad eliminiarli tutti. Può essere più difficile con dei formati grafici perché potremmo avere un termine spezzato in piu parti, ad esempio perché abbiamo un a capo, oppure perchè ci possono essere degli elementi in più che a noi non interessano, quindi abbiamo il problema di ricomporre nel modo corretto i termini che erano stati separati.

Successivamente possiamo semplificare il nostro vocabolario(ridurre la dimensione dei dati, lo spazio di ricerca etc…), tipicamente si riportano tutte le forme flesse al loro lemma, cioè alla forma di indicizzazione del termine sul vocabolario. Si possono anche accorciare le parole, oppure prefissi e suffissi possono essere accorciati con delle abbreviazioni.

Si passa poi alla costruzione dei vettori di termine. Nella versione più semplice un vettore può essere un indice booleano dei termini che sono presenti o assenti all’interno del nostro documento, il vocabolario che stiamo prendendo in considerazione sarà costituito da N termini e andiamo a verificare quelli presenti oppure no all’interno del documento, più comunemente però si attribuisce un peso ai termini(avremo dei termini che sono considerati più informativi rispetto ad altri) e la tecnica per fare questo passa attraverso la rappresentazione di questi termini come coordinate all’interno di uno spazio e quindi il peso che noi associamo sarà il valore legato alle coordinate nello spazio. I vantaggi sono di poter utilizzare la nozione di spazio geometrico di euclideo, per la quale si hanno delle misure di similarità e di distanza che hanno anche la proprietà di essere transitivi. Quindi nel nostro spazio, costruito da una serie di coordinate, ognuna delle quali rappresenta un termine che sarà associata a un suo peso e attribuendo il valore a tutte le coordinate andrò a definire sostanzialmente il mio vettore. La tipica misura di similarità che si applica in uno spazio geometrico di questo tipo è quella della distanza coseno, ossia si valuta l’angolo tra i vettori e questo mi dice quanto queste descrizioni siano vicini o lontani. Più l’angolo è ampio più i documenti sono lontani e più l’angolo si restringe e più sono vicini. Il coseno di 90 è uguale a uno quindi avremo un’ortogonalità, ossia non c’è similarità tra i documenti, mentre il coseno di zero è uguale a zero e quindi avremo una similarità massima tra i documenti.
Il primo problema che abbiamo quindi è quello di attribuire un valore lungo queste coordinate nello spazio, le nozioni che si usano sono la frequenza del termine relativa e globale, cioè la frequenza del termine in quel documento che stiamo analizzando, e la frequenza che esso ha nell’intero corpo di documenti, nell’intero vocabolario. Tipicamente l’approccio che si ha è di tipo induttivo, cioè si considera vocabolario l’insieme dei termini che sto analizzando, ci potrebbero anche essere approcci analitici, ossia conosco il vocabolario di uno specifico dominio e perciò conosco anche le frequenze dei termini, questo ovviamente si fa solo per settori molto specifici nei quali si sa che i documenti apparterranno solamente a quel settore e per i quali sappiamo che il linguaggio e abbastanza formalizzato da parmetterci da costruire un vocabolario tipico con delle frequenze tipiche.
La misura più semplice è quella che è sempre riferita tramite TF, Time Frequency, ossia la frequenza del termine all’interno del documento che sto analizzando, questa tipo di misura per analizzare i termine e citata in qualsiasi introduzione che si può leggere sull’informazion retrieval però ha un carattere didascalico, nel senso che è immediatamente comprensibile, però non è utilizzata perché una di misura facilmente crackabile, per esempio un modo di cercare di evitare questo problema è quello di fare un rapporto tra la frequenza del termine del documento e una frequenza massima che noi stimiamo. Gli approcci effettivamente implementati dai motori di ricerca sono legati a rapporti probabilistici, quindi si ha una stima della probabilità di riscontrare un certo termine e si fa un rapporto sulla misura che effettivamente uno verifica per aprire il documento in analisi e la probabilità a priori data dalla conoscenza storica. Un'altra misura citata e quella detta Inverse Document Frequency che è un rapporto tra il numero totale di documenti all’interno di un corpus e il numero di documenti che citano quel termine stiamo analizzando. Si usa il logaritmo come una forma di riduzione della scala, dopodiché c’è anche un'altra versione nata dal rapporto di documenti totali all’interno di un corpus meno i documenti che citano il termine, tutto questo valutato nel rapporto con i documenti che citano il termine, la differenza è che qui al numeratore sto cercando quanti sono i documenti che non citano il termine che sto analizzando e questo perché mi da una misura di quanto il termine sia diffuso all’interno del corpus. Un’ ultima misura del valore dell’importanza di un termine è il TF * IDF con il quale si vanno a misurare le proprietà di queste due misure che sono propriamente utilizzate. Per calcolare la distanza dei vettori viene usata la distanza coseno, la quale è legata al prodotto scalare, che è il prodotto del valore dei due vettori per il loro coseno, quindi deriviamo che se calcoliamo il prodotto scalare e facciamo il rapporto con il prodotto delle magnitudo troviamo il coseno dell’angolo tra i due vettori. Il prodotto scalare può essere calcolato anche facendo la somma dei prodotti delle coordinate dei termini che stiamo analizzando, mentre per quanto riguarda il magnitudo di un vettore , possiamo calcolarlo facendo la somma di tutte le sue coordinate elevate al quadrato, il totale poi viene calcolato sotto radice quadrata.
Quindi possiamo definire la similarità tra due documenti come una formula avente al numeratore il prodotto scalare(la somma di tutti i rapporti dei valori di tutte le coordinate), mentre al denominatore avremo la magnitudo di a e b. Se analizziamo bene questa formula non dista molto come concetto dalla norma di jacquard, poiché andremo a prendere tutte le coordinate che sono in comune e calcoliamo il loro peso, che sono le intersezioni, al numeratore invece andiamo a prendere tutti gli elementi che compongono i nostri documenti, il fatto di elevare al quadrato e poi di fare la radice quadrata si spiega ovvviamente in termini geometrici, ma di fatto ha un valore pratico che è quello di andare a eliminare i numeri negativi.
Possiamo ottenere un peso negativo se nel momento in cui si sottrarre il numero di documenti che citano quel termine questo supera in 50% dei documenti totali, più è vicino al 50% e più sarà basso, approssimandoci al 100% avremo un valore negativo più alto.
Il logaritmo è un fattore che permette di ridurre la scala della nostra formula, applicando logaritmi diversi riduciamo con intensità diversa la scala.
Un esempio utile potrebbe essere quello di provare a vedere cosa varia cambiando le misure dei pesi dei termini, oppure cosa cambia definendo dei rapporti diversi tra il numero totale dei documenti e il numero dei documenti che citano un termine.
Ciò che fa la differenza è come andiamo a pesare i nostri termini, i moderni motori di ricerca utilizzano degli approcci probalistici stimando quale è la probabilità di incontrare un certo termine, probabilmente applicando anche altre tecniche di modifica di questi valori in base ai contesti che stanno considerando.
Dopodichè dovremo valutare la qualità dei documenti che sono stati reperiti dai nostri strumenti di information retrieval, sono comunemente usate due misure di precision e recall, definite dalle seguenti formule:

Precision = R ∩ R* / R
Recall = R ∩ R* / R*

Dove R sta per i documenti reperiti e R* sta per i documenti rilevanti.
Con la precision mi chiedo se tutti i documenti che ho reperito sono rilevati, mentre nella recall mi chiedo se tutti i documenti che ho reperito sono tutti rilevati o se invece ci sono alcuni che non lo sono.

Un altro problema è quello della costruzione di indici per la lettura di questi documenti. Sostanzialmente quello che si fa è di andare a costruirsi un indice dei termini ed andare a associare questo con degli id che permettono di identificare i doc che parlano di un determinato termine e la posizione del termine stesso.
Questo ci permetterà quando lavoreremo sui vettori di andare a reperire i nostri documenti, anche se avremo dei problemi di accesso alla memoria che gestisce gli indici perchè se la memoria è di massa e analizziamo indici che devono essere letti e aggiornati in continuazione avremo delle difficoltà, si andranno allora a costruire dei doppi livelli di descrizione della memoria, a livello di RAM tipicamente attraverso delle hash table che contengono degli id di riferimento a dei termini o a del testo in generale. Questi hash table in memoria ram vengono trattati comunemente mentre si passa alla valutazione delle effettive stringhe testuali o dei testi solo nel momenti in cui voglio effettivamente andare a laggere il testo.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License