Integrazione delle tecniche di web information retrieval e...

Facoltà di Ingegneria

Integrazione delle tecniche di web information retrieval e LSI per insiemi di dati eterogenei di elevata dimensione

Tesi presentata per la Laurea in Ingegneria Informatica

Stefano Portelli

Relatore Prof. Stefano Leonardi

Correlatore Ing. Stefano Millozzi

Università degli studi di Roma “La Sapienza”

Anno Accademico 2000/2001

Integrazione delle tecniche di web IR e LSI per insiemi di dati eterogenei di elevata dimensione

1

Continuiamo a cercare perché non troviamo mai.

Pablo Picasso


2

Indice 1. Introduzione

1.1. Motivazioni ...................................................................... 6 1.2. Il problema ....................................................................... 7 1.3. Contenuto dei capitoli ...................................................... 9

2. Preliminari .............................................................................10

2.1. Singular Value Decomposition - SVD ............................10 2.2. Latent Semantic Indexing ................................................14 2.3. Folding- in ........................................................................17 2.4. SVD Updating .................................................................20

2.4.1. Generalità ..............................................................20 2.4.2. Inserimento nuovi documenti ...............................22

2.5. Ortogonalità e perdita di informazione ............................23 2.6. Algoritmi di ricerca .........................................................25

2.6.1. Ricerca LSI ...........................................................25 2.6.2. PageRank ..............................................................26 2.6.3. Text Matching .......................................................28

3. Il sistema proposto ................................................................29

3.1. Problematiche da affrontare ............................................29 3.2. Il sistema di partenza .......................................................31

3.2.1. La parte offline ....................................................33 3.2.2. Il motore di ricerca ................................................34

3.3. Il sistema realizzato .........................................................35 3.3.1. Analisi dei documenti ...........................................35 3.3.2. Pesatura della matrice ...........................................39 3.3.3. Calcolo di SVD .....................................................40 3.3.4. Calcolo della matrice di similarità ........................42


3

3.3.5. Costruzione della rete di similarità e dei grafi per PageRank ..............................................................43

3.3.6. Implementazione degli algoritmi di ricerca ..........44 3.3.6.1.Ricerca LSI .....................................................45 3.3.6.2.PageRank ........................................................46

3.4. Migliorie implementate ...................................................47 3.4.1. Trattamento dei dati in memoria secondaria ........47

3.4.1.1.Analisi dei file .................................................47 3.4.1.2.Prodotti tra matrici ..........................................52

3.4.2. Velocizzazione di SVD .........................................55 3.4.3. SVD Dinamico ......................................................58

4. Procedure di testing e benchmarking .................................60

4.1. Modalità di test ................................................................61 4.2. Riduzione dello spazio dei concetti .................................63 4.3. Indici utilizzati nei test ....................................................64 4.4. Recall e Precision ............................................................66 4.5. Precision agli 11 livelli standard di recall .......................73 4.6. Tempi di risposta .............................................................78 4.7. SVD Updating .................................................................80

5. Conclusioni ............................................................................85 Ringraziamenti ............................................................................88 Bibliografia ..................................................................................89 Appendici A – Velocizzazione di SVD ..........................................................91


4

Lista delle Figure 1.1 Collocazione della struttura semantica. 2.1 Rappresentazione matematica della matrice Ak . 2.2 Rappresentazione matematica del Folding- in di p documenti. 2.3 Perdita di ortogonalità a seconda dei vari metodo utilizzati. 3.1 Processo di analisi dei documenti. 3.2 Tempi di analisi dei file al variare del numero di documenti. 3.3 Algoritmo concettuale per l’analisi dei file. 3.4 Algoritmo utilizzato per l’analisi dei file. 4.1 Andamento dell’indice di recall per k = low. 4.2 Andamento dell’indice di recall per k = norm. 4.3 Andamento dell’indice di recall per k = high. 4.4 Andamento dell’indice di precision per k = low. 4.4 Andamento dell’indice di precision per k = norm. 4.4 Andamento dell’indice di precision per k = high. 4.7 Andamento della media dell’indice di recall. 4.8 Andamento della media dell’indice di precision. 4.9 Interpolazione di Precision vs Recall con k = high. 4.10 Interpolazione di Precision vs Recall con k = norm. 4.11 Interpolazione di Precision vs Recall con k = low. 4.12 Tempi di risposta dei tre algoritmi di ricerca. 4.13 Indice di Recall per LSI con SVD-Updating. 4.14 Indice di Recall per PageRank con SVD-Updating. 4.15 Indice di Precision per LSI con SVD-Updating. 4.16 Indice di Precision per PageRank con SVD-Updating.


5

A.1 Risparmio di tempo di elaborazione e peggioramento prestazioni con l’aggiunta di zeri alla matrice dei temini-documenti (n° doc ˜ 1000).

A.2 Risparmio di tempo di elaborazione e peggioramento prestazioni con l’aggiunta di zeri alla matrice dei temini-documenti (n° doc ˜ 2000).


6

Capitolo 1 - Introduzione

Un giorno le macchine riusciranno a risolvere tutti i problemi, ma mai nessuna di esse potrà porne uno.

Albert Einstein

1.1. Motivazioni Al fine di applicare le metodologie di ricerca link-oriented a collezioni di documenti prive di una propria struttura di link (come ad esempio una racconta di documenti all’interno di un’intranet aziendale), [Mil01] e [LF01] hanno proposto l’idea di costruire delle connessioni tra i documenti tramite l’analisi delle relazioni semantiche ottenute dall’applicazione del Latent Semantic Indexing e realizzato un webserver che implementa diversi algoritmi di ricerca (link-oriented) e alcuni tool di supporto. Questa tesi rielaborando il lavoro da loro affrontato, corregge alcune delle problematiche rimaste irrisolte quali l’impossibilità di analizzare un insieme grande a piacere di documenti, ed inoltre introduce delle nuove funzionalità quali la possibilità di utilizzare differenti algoritmi di ricerca, di inserire dinamicamente dei nuovi set di documenti e di effettuare una procedura di test basata sulle metodologie introdotte in letteratura per sistemi di information retrieval.


7

1.2. Il problema Tipicamente il modo più semplice per estrarre informazioni da un vasto insieme di documenti è quello di realizzare un matching letterale tra i termini dati da una query e quelli presenti nei documenti stessi. Come ben noto, però, tale metodo (Text Matching1) presenta numerose limitazioni, non trascurabili nemmeno a fronte della sua rapidità e semplicità d’uso.

Partendo dal presupposto che esistono diversi modi per esprimere uno stesso concetto (sinonimie), e che uno stesso termine può avere differenti significati (polisemie), la semplice ricerca text matching può ritornare dei documenti che non hanno alcuna rilevanza. Un migliore approccio potrebbe essere quello di ricercare informazioni non sulla base del significante, bensì su quella del significato.

Il Latent Semantic Indexing (LSI) [DDF+90] tenta di effettuare

delle ricerche nella maniera suddetta, cercando di evidenziare una struttura semantica latente che nei vari documenti è parzialmente nascosta dalla variabilità con la quale possono essere scelte le parole. LSI è una tecnica di indicizzazione dei concetti2 basata sulla Singular Value Decomposition (SVD) [GL89] che consente di stimare la struttura semantica dei documenti analizzati. Questa struttura è collocabile ad un livello superiore rispetto a quello occupato dal significante delle parole utilizzate nel documento.

1 Data una query, vengono ritornate le pagine che ne contengono tutti i termini, ordinate secondo una certa euristica. 2 Viene creata una lista virtuale dei concetti contenuti nei documenti analizzati.


8

Figura 1.1: Collocazione della struttura semantica.

In questa tesi, oltre alla classica implementazione del processo LSI che prevede principalmente:

1. La creazione di una base di dati contenente per ogni documento, le occorrenze di ogni parola.

2. Il calcolo di SVD. 3. L’elaborazione dei risultati di SVD.

Sono state utilizzate le informazioni derivanti dal punto 3 al fine di costruire uno pseudo-grafo di link tra i documenti, atto a creare una web-rappresentazione degli stessi. A partire da questa rappresentazione è stato possibile applicare algoritmi di ricerca realizzati espressamente per strutture link-based ed effettuare delle scrupolose procedure di test necessarie a valutare l’effettiva efficacia della rappresentazione di link calcolata. Nelle procedure di test è stato utilizzato come algoritmo di confronto principale la ricerca LSI, questa infatti utilizzando il metodo di estrazione dei concetti dai documenti risulta essere la più adatta;

doc 1

doc 2

doc 3

doc 4

doc 5

parole parole parole (significante)

struttura semantica


9

secondariamente è stato utilizzato text matching per la sua semplicità implementativa e per l’estraneità alla struttura di link creata. L’algoritmo di ricerca scelto per analizzare la struttura di link creata è PageRank (o meglio una sua approssimazione), che attualmente risulta essere utilizzato da quello che viene considerato il migliore motore di ricerca su internet: Google. 1.3. Contenuto dei capitoli Il capitolo 2 introduce i concetti teorici necessari alla comprensione delle operazioni di decomposizione in valori singolari (SVD) e alle varie operazioni di updating che possono essere fatte su un database pre-esistente, inoltre illustra le diverse metodologie che stanno alla base degli algoritmi di ricerca che verranno implementati (PageRank, ricerca LSI, Text Matching).

Il capitolo 3 analizza il sistema elaborato da [Mil01] e [LF01], mettendone in luce le problematiche e illustrando le soluzioni realizzate in questa tesi.

Infine nel capitolo 4 vengono comparati i vari algoritmi di ricerca attraverso delle rigorose procedure di test.


10

Capitolo 2 - Preliminari

La chiave di tutte le scienze è senza dubbio il punto di domanda. Honoré de Balzac

2.1. Singular Value Decomposition – SVD SVD viene generalmente utilizzato nella stima del rango di una matrice e nell’analisi canonica della correlazione [Ber92a]. Per una matrice rettangolare non è possibile definire gli autovalori. Una generalizzazione del concetto di autovalore può ottenersi con i valori singolari.

Data una matrice nxmA , la matrice ATA possiede n autovalori non

negativi che, ordinati in maniera decrescente 021 ≥≥≥≥ nλλλ Κ ,

possono esprimersi nella forma

02 ≥= iii σσλ .

Gli scalari 021 ≥≥≥≥ nσσσ Κ si dicono valori singolari della

matrice A. La decomposizione in valori singolari (SVD) della matrice A è data da

TVUA ′⋅Σ′⋅′= (2.1) Dove U ′ è una matrice ortogonale ( mm× )

][ 21 muuuU Κ=′

V ′è una matrice ortogonale ( nn × )


11

][ 21 nvvvV Κ=′

e Σ′ è una matrice ( nm × )

Σ=Σ′

000

),,,( 21 ndiag σσσ Κ=Σ

in cui 021 >≥≥≥ rσσσ Κ . Il numero di valori singolari diversi da

zero è pari al rango r della matrice A. Le colonne di U ′ sono gli autovettori della matrice AAT, mentre le colonne di V ′ sono gli autovettori della matrice ATA. Tenendo conto della struttura di Σ′ , si ha che

Trr VUA ⋅Σ⋅= (2.2)

dove con Ur e Vr si sono indicate le matrici ottenute rispettivamente dalle prime r colonne di U ′ e V ′ .

I seguenti due teoremi illustrano come SVD possa rivelare

importanti informazioni riguardo la struttura di una matrice.


12

Teorema 1. Calcolato SVD(A) in base all’equazione (2.1) e considerato che

s 1 = s 2 … = s r = s r+1 = … = s n = 0 si ha:

1. rank property: rank(A) = r, N(A) = span{vr+1, ... vn}, e R(A) = span {u1, ... , ur}.

2. dyadic decomposition: )(1

Tii

r

ii vuA ⋅⋅= ∑

=

σ .

3. norms: 221

2rF

A σσ ++= Λ , e 12

2σ=A .

Avendo indicato con R(A) e N(A) rispettivamente il range e il null space di A. ? Teorema 2. [Eckart and Young] Calcolato SVD(A) in base all’equazione (2.1), sia r = rank(A) = p = min(m,n), definita

Tii

k

iik vuA ⋅⋅= ∑

=

σ1

(2.3)

di dimensioni ( nm × ) e con rank(Ak) = k. Si ha:

221

)(

22min pk

kBrankFkAABA σσ ++=−=− +

=

Κ (2.4)

con nmB ×ℜ∈ ?


13

(Per la dimostrazione vedi [GR71]) In altre parole Ak, che è costruita a partire dalle k più grandi singular triplet 3 di A, è la miglior approssimazione di rango k della matrice A [GL89].

3 Le triple (u i, s i, vi) sono chiamate singular triplets (triple singolari) e si ha che (u i, s i, vi) è “più grande” di (u j, s j, vj) se s i> s j.


14

2.2 Latent Semantic Indexing Un passo necessario nell’implementazione di LSI [DDF+90] è la costruzione della matrice termini-documenti A[aij] di dimensioni ( nm× ), dove m è il numero di termini distinti presenti negli n

documenti. Il generico elemento aij della matrice termini-documenti rappresenta le occorrenze della parola i-esima nel documento j-esimo; dato che non tutte le parole compaiono in tutti i documenti, la matrice termini-documenti può essere considerata, senza perdita di generalità, una matrice sparsa.

Dopo aver calcolato le occorrenze di ogni parola in ogni documento, è possibile, a seconda del tipo di implementazione scelta per LSI, applicare delle funzioni di pesatura in modo tale da considerare ogni parola sia nel contesto del documento locale, sia in quello più generale di tutta la collezione di documenti; per quanto detto, il generico elemento aij di A può assume la seguente forma

)(),( iGjiLa ij ⋅= (2.5)

dove L(i,j) è la funzione di pesatura locale del termine i per il documento j, e G(i) è la funzione di pesatura globale per il termine i.

La matrice A (termini-documenti) viene in seguito scomposta nel prodotto di 3 matrici (vedi equazione (2.2)) tramite SVD, che in qualche modo permette di derivare la struttura semantica della collezione dei documenti utilizzando: le matrici ortogonali Ur e Vr (contenenti rispettivamente, i vettori singolari sinistri e destri di A), e la matrice diagonale Σ dei valori singolari di A.


15

Ricavate le matrici Ur, Vr e Σ , estraendo le prime rk ≤ triple singolari, si approssima l’originale matrice termini-documenti A, con la matrice di rango k, Ak, come mostrato dalle equazioni (2.3)-(2.4). rU Σ

TrV

k k

k kΣ

k

T

kV

Ak = kU

nm × rm × rr × nr×

Ak = miglior approssimazione di rango k di A m = numero dei termini

Ur = prime r colonne della matrice U ′ n = numero dei documenti Σ = matrice diagonale dei valori singolari k = dim. dello spazio ridotto

rV = prime r colonne della matrice V ′ r = rango di A

Figura 2.1: Rappresentazione matematica della matrice Ak dall’equazione (2.3).

Le matrici Ur e Vr sono definite rispettivamente come matrice dei

Vettori Termini e dei Vettori Documenti, mentre Σ e detta matrice dei Valori Singolari. Il prodotto tra le regioni oscurate delle matrici Ur, Vr e la matrice diagonale Σ , rappresenta la matrice Ak derivata dall’equazione (2.3).


16

Considerando la scomposizione della matrice Ak nelle tre matrici kU ,

kΣ e kV 4 è possibile ottenere la rappresentazione della collezione di

documenti nello spazio ridotto a k dimensioni secondo la seguente formula

{ { {nm

km

Tk

kk

knk

AUAT ×

××

−

×

⋅⋅Σ= 321)(

1 )(ˆ (2.6)

Utilizzando questa formula è possibile che due documenti

qualsiasi, originariamente differenti nello spazio m dimensionale5 di tutti i termini distinti, possano essere mappati nello stesso vettore dello spazio ridotto; l’insieme dei vettori base6 dello spazio k dimensionale, rappresenta in un certo senso l’insieme dei concetti o dei diversi significati che i vari documenti possono assumere, quindi un generico documento nello spazio k-dimensionale è rappresentabile come combinazione lineare dei concetti o equivalentemente dei vettori base dello spazio stesso.

Ogni documento, termine o query ha perciò la sua rappresentazione

nello spazio k-dimensionale, si è passati da una rappresentazione in uno spazio ad m dimensioni (la dimensione è pari al numero di termini trovati nell’analisi di tutti i documenti) ad una forma compressa degli stessi vettori nello spazio k < m dimensionale.

4 Con Uk, Vk e kΣ si sono indicate le matrici ottenute dalle prime k colonne delle

matrici Ur, Vr e Σ . 5 Il j-esimo documento è rappresentato dalla j-esima colonna di A ed è quindi descrivibile come un vettore di dimensione m. 6 Insieme di vettori ortogonali tra loro, in uno spazio a k dimensioni il numero di questi vettori è k.


17

E’ importante notare come con Ak non si voglia deliberatamente ricostruire in maniera perfetta la matrice A, in quanto essa contiene un certo livello di rumore introdotto dall’aleatorietà con cui possono essere scelti i termini per affrontare un certo discorso o un certo argomento.

2.3 Folding-in Supponiamo che un database sia già esistente, che tutti i documenti siano quindi stati analizzati e sia stata già creata la matrice termini-documenti A; a questo punto per inserire dei nuovi documenti (ossia per avere la loro rappresentazione nello spazio ridotto k-dimensionale) abbiamo due diverse alternative: ricalcolare SVD della nuova matrice dei documenti oppure effettuare delle modifiche al database corrente inserendo sia i nuovi termini che i nuovi documenti.

Per quanto riguarda la modifica del database esistente, questa può essere effettuata sia con il metodo del Folding- in sia con quello di SVD-Updating [OB94] che verrà illustrato più avanti.

Come precedentemente accennato ricalcolare SVD non è un

metodo di modifica del database esistente, in quanto, vengono rianalizzati tutti i documenti e rieffettuati tutti i calcoli per creare i vettori nello spazio k-dimensionale; il ricalcolo di SVD verrà quindi utilizzato per confrontare i risultati ottenuti con SVD-Updating.

Non è da tralasciare il fatto che, ricalcolare completamente SVD

richiede un notevole tempo computazionale e, per grandi insiemi di documenti, può causare problemi per quanto riguarda l’occupazione di memoria.


18

D’altra parte, il ricalcolo consente ai nuovi t termini e d documenti di modificare direttamente la struttura semantica creando una nuova

matrice )()( dntmA +×+ e ottenendo quindi una diversa Ak 7 calcolata

tramite SVD. Il Folding- in, invece, richiede pochissime risorse, sia di tempo che

di memoria, però deteriora abbastanza velocemente la qualità della rappresentazione dei documenti nello spazio k-dimensionale poiché, basandosi esclusivamente sulla struttura semantica già calcolata (Ak), i nuovi documenti vengono solamente aggiunti come nuovi vettori nel preesistente spazio k-dimensionale dei concetti.

L’inserimento di nuovi documenti tramite il Folding- in si basa

essenzialmente sul processo di creazione di uno pseudo documento (vedi paragrafo 2.6.1 più avanti). Ogni nuovo documento viene rappresentato come un vettore, nello spazio k-dimensionale dei ed in seguito attaccato all’esistente vettore documenti (Vk) (vedi figura 2.2).

7 La dimensione dello spazio ridotto prima e dopo l’aggiunta dei nuovi termini/documenti può essere differente.


19

kΣ T

kV

kk × nk ×

p

Ak Uk nm× km×

p

)( pnm +× km× kk × )( pnk +×

Figura 2.2: Rappresentazione matematica del Folding-in di p documenti.

Similarmente dei nuovi termini possono essere inseriti nel

preesistente database con una procedura analoga (per ulteriori dettagli vedere [OB94]).


20

2.4. SVD Updating Questo paragrafo descrive la teoria necessaria alla comprensione della procedura di SVD-Updating. I tre passi richiesti per completarla sono

1. Aggiunta di nuovi documenti 2. Aggiunta di nuovi termini 3. Correzione dei pesi dei termini

Questi tre passi non necessitano di essere eseguiti né in ordine e né

tutti e tre contemporaneamente, infatti si potrebbe voler solamente introdurre dei nuovi documenti senza introdurre dei nuovi termini o effettuare la correzione dei pesi. L’unica regola è dettata dal buonsenso che ci impedisce di effettuare il terzo passo da solo, per il resto i primi due possono essere eseguiti in qualsiasi ordine. 2.4.1. Generalità

Sia D la matrice dei nuovi d documenti da elaborare, naturalmente D è una matrice sparsa ( dm × ) 8 dato che non tutti i termini compaiono in ogni documento, e rappresenta il contenuto in termini di ogni nuovo documento.

Questa matrice D viene affiancata alle colonne della matrice Ak,

che rappresenta la miglior approssimazione di rango k della matrice A originale.

8 m è il numero dei termini distinti contenuti nei documenti con cui è stata creata la matrice A .


21

)|( DAB k=

Con dim (B) = )( dnm +× .

Sia T una matrice ( nt × ) la cui j-esima colonna di dimensioni

( 1×t ) rappresenta le occorrenze dei nuovi t termini nel documento j-esimo, tale matrice risulta essere dato che ogni termine compare raramente in ogni documento. Questa matrice viene affiancata alle righe della matrice Ak.

=

TA

B k

Con dim (B) = ntm ×+ )( .

Il passo di correzione dei pesi dei vari termini viene effettuato solo dopo che ogni nuovo termine e documento è stato inserito. Per cambiare i pesi di j termini, vengono utilizzate una matrice Yj ( jm × )

composta da righe di zeri o righe uguali alla j-esima riga della matrice identità Ij, e una matrice Zj ( jn × ) le cui colonne specificano l’attuale

differenza tra i vecchi e nuovi pesi per ogni termine j-esimo. Calcolate queste matrici per effettuare la correzione dei pesi basta porre: [OB94]

Tjjk ZYAB +=

Con dim (B) = nm × .


22

2.4.2. Inserimento nuovi documenti In questa sezione verrà data una rappresentazione più dettagliata per quanto riguarda la procedura di updating di nuovi documenti, per quanto riguarda l’inserimento di nuovi termini e la correzione dei pesi si rimanda a [OB94].

Sia )|( DAB k= la matrice precedentemente calcolata, definiamo

SVD(B) = TBBB VU Σ . Si ha

( )DUI

VBU T

kkd

kTk |Σ=

dato che Tkkkk VUA Σ= , se poniamo ( )DUF T

kk |Σ= e SVD(F)= TFFF VU Σ ne segue che

Fd

kB

FkB

VI

VV

UUU

⋅

=

=

e poiché Fd

kTkF I

VBUU Σ=

⋅⋅)( si ha FB Σ=Σ .

Dove UB e VB sono delle matrici dense rispettivamente di dimensioni ( km × ) e ( )()( dkdn +×+ ).


23

2.5. Ortogonalità e perdita di informazione L’ortogonalità è una proprietà mantenuta in SVD dai vettori singolari destri e sinistri, si ricorda che una matrice nmQ × ortogonale soddisfa

QTQ = In, dove In è la matrice identità di ordine n.

Sia Dp la collezione di tutti i documenti inseriti tramite il metodo di folding- in dove ogni colonna della matrice ( kp × ) è un vettore

documento ottenuto da9 [OB94]

1−Σ= kktp Vdd

Sia Tq la relativa collezione dei nuovi termini inseriti con il metodo

del folding- in, allora tutti vettori dei termini e quelli dei documenti possono essere rappresentati rispettivamente come TT

qTkk TUU )|(ˆ = e

TTq

Tkk DVV )|(ˆ = .

Sulla base di sperimentazioni effettuate si è ricavato che la

procedura di folding- in corrompe l’ortogonalità di kU e di kV in

maniera molto più marcata di quanto avviene utilizzando SVD-Updating.

Per poter misurare questa perdita di ortogonalità che equivale ad

una perdita di informazione, basta utilizzare la seguente formula

2ˆˆ

kkTk IUU −

e anche

9 dt è la rappresentazione del documento sulla base del dizionario preesistente.


24

2ˆˆ

kkT

k IVV −

nella tabella in figura 2.3 sono riassunti i valori della perdita di ortogonalità/informazione in funzione dei metodi utilizzati per inserire nuovi documenti/termini.

Folding- in SVD-Updating SVD

1.445E-1 2.206E-4 2.472E-4

Figura 2.3: Perdita di ortogonalità secondo i vari metodi utilizzati.

Come direttamente visibile dalla figura 2.3, è proprio il metodo di Folding-In che corrompe in maniera più marcata l’informazione, mentre SVD-Updating causa un errore direttamente confrontabile con l’applicazione del ricalcolo totale di SVD.


25

2.6. Algoritmi di Ricerca Una volta effettuate le operazioni necessarie al calcolo di SVD, si può scegliere quale tipologia di algoritmo utilizzare al fine di effettuare una ricerca all’interno della collezione di documenti. Le alternative analizzate sono state la ricerca LSI, PageRank (in due differenti versioni) e il Text Matching. 2.6.1. Ricerca LSI La ricerca basata su LSI sfrutta il fatto che la query fatta dall’utente è rappresentabile come un insieme finito di parole, quindi considerata alla stregua di un normale documento, e perciò rappresentabile, nello spazio k-dimensionale, come un vettore. Quindi una volta che la query è stata analizzata e rappresentata come uno pseudo-documento, può essere semplicemente comparata con tutti gli altri documenti.

Il vettore colonna della query (qv), di dimensione ( 1×m ), è rappresentabile matematicamente come uno pseudo-documento (q), dello spazio k-dimensionale, grazie a questa formula:

{ {( ){ {

1

1

1 ×××

−

×

⋅⋅Σ=m

v

km

Tk

kk

k

k

qUqT

In questo modo i documenti concettualmente più vicini alla query

posso essere calcolati una volta che si è scelto il modo per misurare la loro “vicinanza”. Una semplice e ovvia misura di vicinanza è il valore del coseno dell’angolo compreso tra due vettori (ossia tra due documenti).


26

Dati due vettori Tkaaaa ],,,[ 21 Λ

ρ= e T

kbbbb ],,,[ 21 Λρ

=

appartenenti allo spazio k-dimensionale, il coseno dell’angolo tra i due vettori è calcolato come

ba

baρρ

ρρ

⋅

⋅=αcos

In cui baρρ

⋅ rappresenta il prodotto scalare tra i due vettori mentre

baρρ

⋅ è il prodotto tra i moduli.

2.6.2. PageRank L’algoritmo di ricerca denominato PageRank è noto essere l’algoritmo utilizzato da Google per le sue ricerche. La bontà di questo motore di ricerca, attualmente considerato come il migliore, è da ricercarsi nel fatto che utilizza pesantemente la struttura di connessione del web per calcolare un ranking di qualità di ogni pagina. Questo ranking è chiamato PageRank e offre dei risultati molto buoni; l’idea alla base di tale algoritmo è dare un ordinamento globale a tutte le pagine del grafo del web, indipendentemente dalla query.

Il grafo del web è, ovviamente, un’importante sorgente di informazioni con le sue milioni di pagine disponibili, ma solo una piccola parte di esse è utilizzata dai motori di ricerca attuali. In Google viene creata una mappa contenente circa 518 milioni di hyperlink (ragionevolmente un significativo sottoinsieme del totale ) su cui è effettuato un “rapido” calcolo di PageRank.

Analisi effettuate utilizzando PageRank su ricerche testuali limitate

al solo titolo dei documenti, hanno dato dei buoni risultati, Google


27

effettua ricerche in full text10, permettendo di ottenere dei ranking ancora migliori.

Il calcolo di PageRank è un’estensione del conteggio del numero di link entranti usati come misura dell’importanza della pagina. Con il PageRank non tutti i link vengono contati ugualmente e inoltre il valore ottenuto è normalizzato al numero di link nella pagina.

Una definizione sommaria di PageRank potrebbe essere la

seguente:

Si assuma che la pagina A ha le pagine T1, ... , Tn che puntano ad essa (ad esempio con dei link). Sia C(A) il numero di link uscenti dalla pagina A. Il PageRank (PR) della pagina A è il seguente:

)()()()(()1()( 11 nn TCTPRTCTPRddAPR +++−= Λ

Dove il parametro d è detto camping factor è può assumere i valori tra 0 e 1, generalmente è fissato a 0,85.

Si noti che PageRank forma una distribuzione di probabilità nelle pagine tale che la somma totale è unitaria.

PageRank può essere pensato come il modello di un “navigatore random” che segue i link ed effettua dei salti casuali raggiungendo alcune pagine più di frequente rispetto ad altre. La probabilità che un

10 Le ricerche in full text analizzano l’intero documento, memorizzando le occorrenze di ciascun termine ed effettuando successivamente delle elaborazioni di questi dati, ad esempio una normalizzazione.


28

navigatore visiti la pagina è pari al valore di PageRank, mentre il valore d è la probabiltà che il navigatore, annoiato dalla pagina attuale, richieda una nuova pagina random invece di seguire i link. In questo modo le pagine che sono citate più di frequente in vari siti del web (mediante dei link entranti) acquistano rilevanza. 2.6.3. Text Matching Il più semplice algoritmo proposto per ricercare dati è quello di text matching. Data la query dell’utente, viene prima interrogato il database per farsi ritornare la lista dei documenti che contengono tutte le parole della query (nel caso che si utilizzino esclusivamente dei connettori AND tra le parole) e in seguito l’insieme di pagine viene ordinato in base ad una semplice euristica come la seguente

Siano q1, ... , qn i termini della query effettuata dall’utente. Il punteggio relativo alla p-esima pagina è calcolato come

∑ =

n

iiO

1)(

in cui la funzione O(i) ritorna il numero di occorrenze del termine i-esimo nella pagina p-esima.

Quindi le pagine che contengono più occorrenze dei termini della query sono ritornate per prime.


29

Capitolo 3 – Il Sistema Proposto

Ciò che dobbiamo imparare a fare, lo impariamo facendo. Aristotele

3.1. Problematiche da affrontare Sulla base dei lavori effettuati da [Mil01] e [LF01] questa tesi si propone di modificare alcune parti da loro sviluppate nonché di aggiungere alcune interessanti funzionalità.

Un primo passo di reverse engineering è stato necessario in quanto non era disponibile una sufficiente documentazione sul codice esistente, successivamente si è stilata una lista di priorità da affrontare al fine di ovviare ad alcune limitazioni alla funzionalità del codice stesso. La lista compilata consisteva nei seguenti problemi da risolvere:

1. Impossibilità di trattare un numero elevato di documenti. 2. Estrema lentezza nel calcolo di SVD. 3. Impossibilità nell’introdurre dei nuovi documenti senza dover

ricalcolare totalmente SVD. 4. Mancanza di procedure di testing adeguate.

Le problematiche descritte nel primo punto, derivano dall’utilizzo

di algoritmi per l’analisi dei dati e il loro trattamento che lavorano esclusivamente in memoria principale. Avendo infatti utilizzato per lo sviluppo delle applicazioni il linguaggio Java, noto per non gestire al meglio la memoria, si producevano spesso degli errori irreversibili


30

non appena la quantità di memoria occupata raggiungeva una certa soglia.

La risoluzione di questi problemi è spiegata in dettaglio nella

sezione 3.4.1.

Il secondo punto è purtroppo una problematica intrinseca nel calcolo di SVD nel caso in cui sia richiesta una precisione adeguata. L’unico modo per porvi rimedio è sembrato quello di rinunciare ad una parte della precisione per favorire la velocità di esecuzione (ulteriori dettagli nella sezione 3.4.2).

Il terzo punto può essere risolto ammettendo che per poter inserire dei nuovi documenti all’interno della struttura semantica prodotta la LSI si possa accettare un certo errore nella rappresentazione a patto di velocizzare notevolmente tale procedura (sezione 3.4.3).

L’ultimo punto infine è dovuto dalle difficoltà oggettive di reperire un set adeguato di documenti su cui effettuare i test e ricercare procedure adatte a valutare i risultati ottenuti. Per rimediale a tali problemi si è dedicato un notevole tempo a ricercare un adeguato set di documenti che rispecchiasse un probabile utilizzo reale del programma sviluppato (Capitolo 4) e altrettanto tempo è stato dedicato all’utilizzare metodi e rappresentazioni conosciute da tempo in letteratura al fine di valutare algoritmi di information retrieval.


31

3.2. Il sistema di partenza L’approccio al problema dell’information retrieval proposto è stato pensato per essere applicato principalmente a contesti di reti intranet locali in cui esiste la necessità di condividere grandi collezioni di documenti non collegati tra loro tramite link, allo scopo principale di consultazione.

La totale mancanza di questi collegamenti non permette

l’applicazione delle tecniche di ricerca basate su strutture internet (come Hits o Pagerank), le usuali applicazioni dal canto loro, cercano di superare questa difficoltà utilizzando solamente tecniche mirate ad affinare le ricerche basate sulle occorrenze dei termini, con l’aggiunta di euristiche per il calcolo del ranking. Con il sistema proposto si è voluto dimostrare che esiste la possibilità di raccogliere insieme l’efficacia del retrieval mediante Latent Semantic Indexing e la velocità tipica degli algoritmi di ricerca orientati al web.

Il modo in cui si ottiene questa funzione si basa su una ripartizione

del lavoro tra on- line e offline: il grosso dell’elaborazione viene effettuata (e conservata) offline mentre on-line viene mantenuta solamente la parte più snella del calcolo. E’ stato utilizzato LSI in una fase preliminare, allo scopo di creare una struttura a link basata sulla similarità tra i documenti (rete di similarità11) e successivamente per accedere a questa struttura, sono stati utilizzati algoritmi orientati ai link.

11 E’ una struttura in grado di rappresentare la similarità tra le pagine mediante un grafo di connessioni tra i vari documenti.


32

Questa suddivisione ha permesso di disaccoppiare la fase di creazione della struttura connessa (ottenuta utilizzando alcune caratteristiche di LSI) con la ricerca vera e propria, cosicché l’utente sia a contatto solamente con la parte più veloce. Una possibile schematizzazione dell’applicazione realizzata è la seguente: PARTE OFF-LINE

1. Analisi dei documenti, costruzione della matrice A delle occorrenze e memorizzazione nel database, dei termini trovati.

2. Calcolo della matrice A~ che rappresenta la pesatura della matrice A sulla base delle funzioni Log-Frequency e Log-Entropy, rispettivamente per la pesatura locale e globale.

3. Calcolo di SVD( A~ ) in modo da ottenere le matrici di trasformazione dallo spazio dei termini allo spazio ridotto dei concetti.

4. Calcolo della matrice A , matrice trasformata di A~ nel sottospazio k-dimensionale.

5. Per ciascuna coppia di vettori (i, j) di A (ossia per ogni coppia di vettori rappresentanti due documenti nel sottospazio dei concetti) viene calcolata la similarità come il coseno dell’angolo compreso, questo valore è infine riportato nel grafo di similarità.

PARTE ON-LINE

1. Applicazione degli algoritmi di ricerca sulla rete di similarità.


33

3.2.1. La parte off-line Questa parte, come precedentemente accennato, ha lo scopo di memorizzare nel database i termini incontrati e di costruire la struttura dei collegamenti, entrambi passi strettamente necessari al corretto funzionamento del motore di ricerca.

Il passo iniziale consiste nella raccolta dei dati tramite l’analisi dei documenti che devono essere inseriti nel database. Grazie ad un opportuno parser lessicale12 vengono ottenuti, da ogni file, i termini rilevanti (sono quindi scartate stopword ed eventuali tag html) e parallelamente all’analisi dei file, i termini trovati sono memorizzati in un database.

Una volta costruita la matrice dei termini-documenti ed effettuate le relative pesature locali e globali delle varie occorrenze dei termini, viene effettuato il calcolo di SVD, il passo elaborativo più pesante dell’intero processo, questo calcolo è stato effettuato tramite un modulo esterno, accuratamente modificato, al fine di migliorarne l’interfacciamento con i moduli Java che lo utilizzano e la gestione della memoria.

A partire dai risultati ottenuti tramite SVD è infine costruita la rete di similarità, basata sul calcolo del coseno dell’angolo tra i vettori dei documenti rappresentati nello spazio ridotto (vedi paragrafo 2.6.1).

A questo punto tutte le strutture dati necessarie per la ricerca sono state preparate, le tabelle del database contengono le occorrenze di

12 Realizzato tramite jFlex che mediante la definizione delle “espressioni regolari” permette di specificare i token validi.


34

tutti i termini di ogni pagina e la rete di similarità rappresenta la struttura di connessione tra le pagine.

Per ulteriori dettagli sulle procedure quali: progettazione delle tabelle del database, funzioni di pesatura ed altro, vedere [Mil01]. 3.2.2. Il motore di ricerca L’applicazione sviluppata per il motore di ricerca consente l’utilizzo di alcune funzionalità molto interessanti quali procedure per la clusterizzazione e per l’analisi delle ricerche effettuate che però esulano dagli argomenti trattati dalla seguente tesi, per ulteriori dettagli sulle parti non specificate si rimanda a [LF01].

L’unica funzionalità esaminata riguarda la possibilità di effettuare delle ricerche tramite un normale browser internet, ovviamente si richiedeva che l’algoritmo implementato fosse in grado di fornire risultati che superassero le normali limitazioni degli algoritmi text-based, per questo motivo le ricerche sfruttano la tipica struttura generata nella parte offline e in particolare utilizzano il grafo di similarità.

Per effettuare le ricerche sono stati messi a disposizione due diversi

algoritmi: il primo è quello di Kleinberg [Kle98], il secondo è invece un’euristica realizzata ad hoc. Sulle procedure di testing e i benchmark si rimanda a [LF01] e al capitolo 4.


35

3.3. Il sistema realizzato Nella realizzazione dell’applicazione si è tenuto conto delle strategie attuate nel precedente lavoro [Mil01] e [LF01], e delle modalità implementative realizzate. In aggiunta, oltre a considerare il semplice impiego in ambito intranet si è cercato di rendere quanto più possibile performante la parte dedicata alla ricerca di documenti, grazie all’implementazione dell’algoritmo PageRank.

Nonostante il nuovo sistema sia stato ricostruito ex-novo, la struttura di base è rimasta invariata, qui di seguito saranno illustrate le varie fasi del processo, demandando al paragrafo 3.4 la discussione delle migliorie realizzate in questa tesi. 3.3.1. Analisi dei documenti In questa fase ogni documento viene prima analizzato per controllarne la validità del formato html (per ora gli unici formati supportati sono l’html e txt13, ma l’estensione ad altri può essere semplicemente integrata con degli opportuni convertitori di formato) e solo se corretto ,viene iniziata la raccolta dei termini. Il controllo di validità viene effettuato tramite il programma tidy14 che scandisce i file e, nel caso, corregge eventuali imperfezioni nella codifica html, qualora si verificasse una situazione di errore, non risolvibile in modo automatico, il documento sarebbe scartato.

13 Ovviamente un documento txt soddisfa la validità html, poiché mancante solamente di alcuni semplici tag. 14 Fornito dal World Wide Web Consortium (www.w3c.org) ed è disponibile per diverse piattaforme.


36

Il compito di individuare i termini validi di un file, viene affidato ad un parser lessicale (realizzato in modo automatico mediante jFlex15) che elimina eventuali tag html; le parole restituite dal parser che appartengono al dizionario delle stopword vengono scartate, delle rimanenti viene verificata la lunghezza che deve essere compresa tra MIN_TERM_LENGTH e MAX_TERM_LENGTH, se questa è minore dell’estremo inferiore consentito, la parola in esame viene scartata, se maggiore dell’estremo superiore, la parola viene troncata. I termini restituiti da quest’ulteriore analisi vengono sottoposti allo stemming al fine di ottenerne la radice.

Ottenut i tutti i termini ammissibili, si controlla che il loro numero

non sia superiore a MAX_TERM_NUMBER, nel caso in cui questo avvenga, vengono prese in considerazione solamente le parole che hanno più occorrenze nel documento esaminato. Per ulteriori dettagli su questa fase, vedere il paragrafo 3.4.1.1.

15 Vedi nota 12 e [Mil01] per le specifiche di realizzazione.


37

Figura 3.1: processo di analisi dei documenti.

A questo punto è possibile costruire la matrice ][ jiaA = dove aij

denota la frequenza del termine i-esimo nel documento j-esimo e che assume il seguente formato ABBREV 0578_005 0579_001 1131_010 ABE 1017_004 ABERRANT 0959_002 ABERRAT 0959_002 1024_003 ABORTGRABB 0216_001

Come si può notare la lunghezza delle parole è stata limitata, le

variabili che si occupano di contenere il va lore di tale parametro sono MAX_TERM_LENGTH, che in questo caso risulta pari a 10, e MIN_TERM_LENGTH, uguale a 3.

documenti eliminazione tag e

stopwords

controllo lunghezza

parole

stemming

conteggio termini


38

Accanto ad ogni parola sono presenti vari token, ad esempio per la riga

ABERRAT 0959_002 1024_003

si ha la parola ABERRAT e i due token 0959_002 e 1024_003.

Il token 0959_002 indica che il documento numero 959 contiene 2 volte il termine ABERRAT16, il token 1024_003 assume un analogo significato. Chiaramente solo i documenti che contengono l’i-esimo termine hanno il rispettivo token sull’ i-esima riga.

Va infine osservato che la fase di stemming delle parole ha il solo scopo di migliorare le prestazioni di LSI, in quanto la riduzione del numero di termini distinti permette di diminuire sensibilmente la dimensione della matrice A.

16 Naturalmente il numero di occorrenze si riferisce sia al termine aberrat, considerato come radice, sia alle sue varianti aberration, ecc.

Token1 Token2 Parola


39

3.3.2. Pesatura della matrice In questa fase sono applicate alla matrice delle occorrenze le trasformazioni relative alla pesatura locale e globale. Ciascun elemento della nuova matrice pesata [ ]ijaA ~~

= 17 viene calcolato come

)(),(~, iGjiLa ji ⋅= . La scelta delle funzioni da adottare è ricaduta su

quelle indicate da [Mil01] come avere il miglior comportamento. Per la pesatura locale si è quindi utilizzata

)1log(),( , += jiajiL

mentre per la pesatura globale

∑⋅

−=j

jiji

ndocs

ppiG

)log(

)log(1)( ,, con

i

jiji gf

ap ,

, =

dove • ija indica il numero di occorrenze del termine i-esimo nel

documento j-esimo • igf il numero di volte che il termine i-esimo compare

nell’intera collezione di documenti • ndocs il numero totale di documenti

E’ da notare che la matrice A~ assume lo stesso formato descritto per la matrice A nel paragrafo precedente.

17 Per chiarezza notazione viene fatto osservare che in questo capitolo viene indicata

con A~ la matrice A pesata. Le formule introdotte nel capitolo 2 per la matrice A

possono essere quindi utilizzate, senza perdita di generalità, per la matrice A~ .


40

3.3.3. Calcolo di SVD Ottenuta la matrice delle occorrenze A~ è ora possibile procedere alla sua decomposizione tramite SVD. Si ottengono quindi le matrici Ur, Σ e Vr (vedi formule 2.2) dalle quali, con un opportuno troncamento a rango k (selezione delle prime k colonne di Ur , Σ e Vr) si ottengono le matrici Uk, kΣ e Vk . E’ opportuno notare che a k sono stati fatti

assumere tre diversi valori, a seconda della sensibilità che si vuol dare ad LSI (per vedere come il valore di k influisca sui rendimenti di LSI, vedere il Capitolo 4). Questi valori sono pari a

• k = low per Ntk ⋅= 0035.0 • k = norm per Ntk ⋅= 0070.0 • k = high per Ntk ⋅= 0140.0

Dove con Nt si è indicato il numero di termini distinti presi da tutti i file, in altre parole il numero di righe della matrice A. A questo punto è possibile calcolare la matrice

{ { {nm

km

Tk

kk

knk

AUAT ×

××

−

×

⋅⋅Σ=~

)(ˆ

)(

1

321

(si ricordi la formula 2.6) che rappresenta il risultato del mapping della matrice A~ nello spazio k-dimensionale dei concetti (si ricordi la formula 2.6), intuitivamente ciascuna colonna della nuova matrice ottenuta, rappresenta le frequenze dei vari concetti in ogni documento.


41

Per calcolare questa decomposizione, le classiche tecniche applicate a delle matrici sparse di elevate dimensioni, non danno dei buoni risultati. Queste tecniche si basano sull’applicazione di trasformazioni ortogonali direttamente sulla matrice A~ e richiedono delle quantità di memoria eccessive, inoltre, esse calcolano tutte le singular triplet, mentre l’applicazione di LSI ne richiede solo un ristretto sottoinsieme.

Per tali ragioni si è preferito utilizzare un modulo esterno scritto in

linguaggio C che fa parte dell’SVDPACK18 ed implementa l’algoritmo subspace iteration, del quale non interessa entrare nel dettaglio in questa sede, basti sapere che calcola in maniera approssimata i valori delle singula triplet, scegliendone, in maniera parametrica, sia il numero che l’accuratezza.

18 Vedere [BDO+].


42

3.3.4. Calcolo della matrice di similarità A partire dalle matrici Uk, kΣ e Vk (con k fissato), ritornate dal modulo

esterno che calcola direttamente il troncamento a rango k di SVD, si calcola la rappresentazione k-dimensionale della matrice delle occorrenze mediante la formula

{ { {nm

km

Tk

kk

knk

AUAT ×

××

−

×

⋅⋅Σ=~

)(ˆ

)(

1

321

E’ da notare che mentre la matrice Uk viene rappresentata come

matrice densa, la matrice A~ è in forma sparsa (tempi di accesso più elevati ma occupazione spaziale minore), inoltre kΣ è una matrice

diagonale il cui calcolo dell’inversa si riduce al semplice calcolo del reciproco degli elementi presenti sulla diagonale principale.

A questo punto, per ottenere il valore di similarità tra due

documenti i e j si utilizza lo stesso procedimento descritto nella sezione 2.6.1. per poter effettuare la ricerca LSI, ossia si calcola il coseno dell’angolo tra i vettori colonna della matrice A

ji

jiji

dd

ddjisim ρρ

ρρ

⋅

⋅== ),cos(,

dove con jd

ρ, per nj ,,1 Κ= si indica la j-esima colonna di A , in

particolare ],,[ˆ1 nddA

ρΚ

ρ= .


43

3.3.5. Costruzione della rete di similarità e dei grafi per PageRank A partire dalla matrice A ottenuta nel precedente paragrafo, si costruisce la rete di similarità: una struttura in grado di descrivere le varie analogie tra i documenti, ossia in grado di fornire una pseudo struttura di link tra i documenti della collezione. Questa struttura è rappresentata mediante un grafo non orientato19 in cui i nodi rappresentano i documenti e l’arco tra due nodi i e j è inserito con probabilità pari a simi,j.

I grafi necessari per l’applicazione di PageRank sono ottenuti sfruttando il grafo non orientato appena descritto, in particolare sono state prese in considerazioni due varianti di costruzione al fine di ottenere un grafo orientato. L’orientamento è strettamente necessario in funzione poiché PageRank è pensato per essere utilizzato in ambito web dove i link sono intrinsecamente monodirezionali.

La prima variante (in-degree) costruisce il grafo tra i documenti in funzione del numero di archi che possiede un determinato nodo, ossia calcola per ogni nodo il numero di archi entranti-uscenti. Dati quindi due nodi i e j, se il valore di in-degree di i è minore del valore di in-degree di j allora viene inserito un arco orientato che va dal nodo i al nodo j, quest’arco sta perciò a significare che il documento j è in qualche modo simile ad un numero maggiore di documenti che non il documento i, e quindi in un certo senso più importante.

19 Il grafo di similarità indicando che il documento A è simile al documento B, implica anche che il documento B è simile al documento A.


44

La seconda variante (simil) da invece importanza ai documenti che hanno maggiore similarità con gli altri. Il primo passo da effettuare è il calcolo per ogni nodo (documento) del suo valore di similarità totale, ottenuto come somma della similarità tra il documento in esame e tutti gli altri documenti della collezione che presentano un collegamento (arco) con esso nel grafo di similarità. Il passo conclusivo è quello di inserire un arco dal nodo i al nodo j solo se la similarità totale di j è maggiore di quella di i. 3.3.6. Implementazione degli algoritmi di ricerca A partire dal codice sviluppato in [LF01] per quanto riguarda la parte esclusivamente dedicata all’applicazione web-server di ricerca si sono effettuate diverse modifiche al fine di utilizzare differenti algoritmi poiché l’applicazione precedente utilizzando il metodo di Kleinberg ed un’euristica realizzata ad hoc per la ricerca delle pagine, presentava della carenze dal punto di vista della risposta temporale.

E’ opportuno osservare che in questa tesi si è deciso di utilizzare la ricerca LSI come base di paragone per le ricerche, in quanto questa risulta essere la più adatta a fare ricerche su un database costruito in funzione dei concetti.


45

3.3.6.1. Ricerca LSI Come precedentemente analizzato nel paragrafo 2.6.1. la ricerca LSI si basa sul fatto che una singola query può essere interpretata come un documento, o meglio come uno pseudo-documento, e quindi mappata nello spazio ridotto dei concetti, ciò consente di ottenere i documenti a lei più simili tramite il calcolo del coseno.

LSI ha una pessima risposta temporale, come si vedrà nel capitolo

4, a causa di quest’ultimo calcolo, infatti la similarità tra il vettore rappresentante la query e quello del generico documento, deve essere calcolata per tutti i documenti della collezione. Essendo il calcolo del coseno un’operazione da effettuarsi tramite double, è ovvio come sia necessario molto tempo per la sue esecuzione. Ad ogni modo, come si vedrà nel Capitolo 4, la ricerca LSI è quella che riesce a dare i migliori risultati in assoluto e considerando che l’operazione di calcolo della similarità tra la query e i documenti potrebbe essere facilmente parallelizzata, questo metodo di ricerca presenta dei margini di miglioramento.

E’ opportuno far notare come è possibile introdurre come query

una frase lunga a piacere (una citazione, un estratto di un altro testo, o al limite un intero documento) e vedere quale documento, tra quelli della collezione, risulta più simile.


46

3.3.6.2. PageRank A partire dai grafi orientati descritti nel paragrafo 3.3.5, la versione dell’algoritmo di PageRank implementato, genera due file che rappresentano i valori di PageRank (vedi paragrafo 2.6.2) di tutte le pagine, in funzione del tipo di grafo utilizzato (in-degree o simil), ordinati in maniera decrescente. Questi file contengono il valore assoluto del rank delle pagine a prescindere dalla query; infatti a fronte di una richiesta fatta dall’utente, il sistema si limita a ricercare nel database tutti i documenti che contengono le parole di cui è composta la query e a ritornarli a partire da quelli con il punteggio di PageRank più elevato.

L’implementazione data di PageRank si riferisce a quella esposta in [PBM+98] che in pratica è un’approssimazione dell’algoritmo vero e proprio di PageRank. L’implementazione data, parametrizzando il numero di iterazioni da poter effettuare, permette di scegliere la precisione nel calcolo di PageRank.


47

3.4. Migliorie implementate 3.4.1. Trattamento dei dati in memoria secondaria Come precedentemente annunciato uno dei principali problemi da cui è affetta l’applicazione sviluppata da [Mil01] e [LF01] riguarda l’impossibilità di gestire un numero elevato di documenti a causa della cattiva gestione della memoria principale da parte di Java, linguaggio utilizzato al fine di consentire la massima compatibilità tra piattaforme differenti.

Per questo motivo si sono studiate procedure e metodologie tali da richiedere il minor spazio possibile in memoria principale e da sfruttare al meglio lo spazio in memoria secondaria. 3.4.1.1. Analisi dei file Il primo passo è stato modificare la procedura di analisi e memorizzazione dei termini incontrati in ogni file. Concesso che i termini contenuti in un singolo file possano essere tranquillamente memorizzati in RAM, tramite una tabella hash per consentire un rapido aggiornamento delle occorrenze di un determinato termine, l’intera lista dei file doveva invece necessariamente essere memorizzata all’interno di un file in memoria secondaria in modo da ridurre al minimo l’occupazione di RAM.

E’ opportuno notare che nonostante non ci fossero limitazioni allo

spazio utilizzabile in memoria secondaria si è scelto comunque di utilizzare una rappresentazione compatta della matrice termini-documenti (vedi paragrafo 3.3.1).


48

Stabilite a priori alcune variabili che permettono di configurare e

personalizzare le modalità con cui viene effettuata l’analisi quali:

• MAX_TERM_LENGTH : lunghezza massima di un termine • MAX_TERM_NUMBER: numero massimo di termini distinti

in un singolo file • MIN_TERM_NUMBER: minimo numero di termini che deve

avere un file per essere considerato valido • ...

le regole secondo le quali un termine è da ritenersi valido (non appartiene alle stopword, è superiore ad una certa lunghezza, non è un numero) e definito un algoritmo di stamming20, l’analisi dei file segue la procedura qui riportata:

1. Preleva un file dalla lista dei file e crea una tabella contenente il numero di occorrenze di ogni suo termine.

2. Se il numero dei termini è inferiore e MIN_TERM_NUMBER scarta il file, se è maggiore di MAX_TERM_NUMBER prendi i primi MAX_TERM_NUMBER termini più ricorrenti, altrimenti prosegui.

3. Ordina i termini alfabeticamente e fai il merge sort tra il file temporaneo in memoria secondaria (che alla prima iterazione è vuoto) e la lista ordinata dei termini creando un nuovo file temporaneo.

20 Procedura che permette di ridurre una parola alla sua radice. Ad esempio le parole sleeping e sleeper vengono entrambe ridotte alla stessa forma ridotta sleep.


49

Figura 3.2: Tempi di analisi dei file al variare del numero di documenti.

Questa procedura, sebbene implichi un notevole numero di

operazioni risulta molto veloce e, come direttamente visibile dalla figura 3.2, impiega un tempo notevolmente inferiore a quella dell’implementazione data da [Mil01] che inoltre cessa di poter essere utilizzata quando l’insieme dei documenti risulta essere troppo grande, a seguito delle limitazioni dettate da Java all’occupazione della memoria principale.

Tempo Analisi File

0

100

200

300

400

500

600

1000 1500 2000 3000n° documenti

tem

po (

sec)

RAM

Merge


50

Figura 3.3: Algoritmo concettuale per l’analisi file . Come visibile dalla figura 3.3 e come precedentemente descritto, viene prima creata in RAM la tabella contenente l’insieme delle occorrenze dei vari termini di ogni file e in seguito viene fatto il merge sort su memoria secondaria.


51

Al fine di ottenere la massima risposta in termini di tempo di esecuzione, in realtà si è effettuato il merge sort e la memorizzazione del suo risultato direttamente in memoria principale per un certo numero di file per poi eseguire il merge sort con il file temporaneo presente in memoria secondaria come mostrato in figura 3.4.

Figura 3.4: Algoritmo utilizzato per l’analisi dei file.


52

3.4.1.2. Prodotti tra matrici I prodotti tra matrici hanno costituito il più grande problema per la corretta gestione degli algoritmi in memoria secondaria. Un giusto bilanciamento tra la velocità d’esecuzione in RAM e il problema della sua gestione da parte di Java, e l’utilizzo della memoria secondaria a scapito della velocità d’accesso ai dati, risultava un obiettivo arduo da raggiungere. La prima soluzione elaborata è stata lo sviluppo di un algoritmo capace di lavorare esclusivamente in memoria secondaria e di portare su quella principale solo la quantità di informazioni strettamente necessaria per il passo elaborativo corrente. Nonostante però si potessero in questo modo trattare insiemi di dati grandi a piacere, i tempi di esecuzione risultavano estremamente elevati e quindi non accettabili.

Figura 3.5: bilanciamento per effettuare i prodotti tra matrici. La soluzione attuata, che ha permesso un corretto bilanciamento, è

stata quella di portare in memoria principale non solamente le informazioni necessaria al passo elaborativo corrente, bensì un numero di informazioni necessarie ad effettuare n passi, accedendo


53

così una sola volta (per blocco di dati caricato) al file e compiendo le varie operazioni molto più velocemente.

In questo modo non solo si continua a poter trattare matrici grandi a

piacere, in quanto è stata parametrizzata (n) l’occupazione di memoria principale richiesta, ma si velocizza notevolmente l’operazione di prodotto.

E’ stato necessario effettuare un cambiamento ne lla

rappresentazione delle matrici in modo tale da effettuare il prodotto in maniera più agevole.

Ricordando come avviene il prodotto tra due matrici A e B, l’elemento pij della matrice prodotto è ottenuto come il prodotto scalare tra la riga i-esima di A e la colonna j-esima di B, osservando ad esempio che nel calcolo dell’elemento p11 viene moltiplicata la prima riga della matrice A con la prima colonna della matrice B, risulta chiaro come sia preferibile poter accedere alla matrice B per colonne. Data una generica matrice B

1 2

3 4

5 6 nella consueta memorizzazione su file, questa può essere vista come rappresentata da un unica riga

1 2 \n 3 4 \n 5 6


54

in cui i simboli “\n” indicano il ritorno a capo.

E’ ovvio che, sebbene sia possibile accedere al file ed effettuare degli spostamenti al suo interno per avere accesso ai vari elementi della j-esima colonna, che nella moltiplicazione sopra descritta equivalgono agli elementi 1, 3 e 5, si è ritenuto più vantaggioso operare una trasformazione della matrice B, calcolandone la trasposta:

1 3 5

2 4 6 che su file risulta così memorizzata

1 3 5 \n 2 4 6

in modo tale da poter leggere la prima colonna della matrice B

come prima riga del file. E’ da notare che in questo modo risultano disponibili tutte le

colonne della matrice B senza dover effettuare spostamenti all’interno del file.


55

3.4.2. Velocizzazione di SVD Il problema del calcolo di SVD risiede nell’enorme quantità di dati che si chiede di processare e nella precisione con cui si vuole che questi calcoli vengano eseguiti.

Una soluzione potrebbe essere quella di semplificare i dati (sia per dimensione che per complessità) senza però perdere i trend dell’informazione, ad ogni modo si pone il problema di identificare di quanto semplificare questi dati, ciò può essere risolto effettuando una serie di test che misurino la variazione dell’errore compiuto in funzione delle semplificazioni effettuate.

La tecnica qui utilizzata (semplificazione della dimensione) si basa

su quelle mostrate in [AS01], ossia sul fatto che gli algoritmi utilizzati per il calcolo di SVD effettuano principalmente operazioni di moltiplicazione tra matrici e vettori, quindi una drastica semplificazione della matrice causa un notevole risparmio di tempo.

Partiamo dal presupposto che la matrice A dei termini-documenti

abbia una sua forte struttura spettrale21 (ossia in un certo senso sia possibile distinguere chiaramente i concetti espressi dai vari documenti), sotto l’applicazione di un particolare rumore additivo, questa struttura non varia più di tanto e permette di ottenere all’incirca gli stessi risultati ottenuti senza l’aggiunta del rumore.

21 Nel capitolo 2 la decomposizione spettrale è stata indicata come dyadic decomposition


56

Omettendo in maniera casuale una frazione dei valori della matrice che sarà passata a SVD, l’errore che si compie sarà naturalmente proporzionale alla frazione dei valori omessi, quindi più la matrice avrà dei forti trend e più si potrà omettere un maggior numero di valori. Qui di seguito l’enunciato del teorema utilizzato: Teorema. Sia A una matrice ( nm × ) e sia ijji ab ,max= .

Scelto

)(log4)(

16 nm

nms

++

≤≤

definiamo A una matrice ( nm× ) così ottenuta

⋅−

=sprobconas

sprobconA

ij /1./11.0

Allora si ha che :

nmbsAAAA kk +×+−<− 10

con probabilità nm +

−1

1 .

?

Per il teorema precedente, se con probabilità 1-1/s si vanno ad azzerare gli elementi della matrice A, scalando invece gli altri di un opportuno fattore s, l’errore che si introduce utilizzando al posto di Ak (miglior approssimazione di A di rango k) la matrice kA (miglior


57

approssimazione di A di rango k) è pari a nmbs +×10 , rendendo,

in teoria, più veloce l’operazione del calcolo di SVD. Per quanto riguarda un’oggettiva valutazione del metodo descritto

si rimanda all’Appendice A, mentre per le dimostrazioni e ulteriori riflessioni sul metodo si veda [AS01].


58

3.4.3. SVD Dinamico

Per quanto riguarda l’inserimento dinamico di nuovi termini/documenti (per i dettagli teorici vedere il paragrafo 2.4), si è ritenuto sufficiente applicare la procedura di updating esclusivamente ai nuovi documenti senza implementare quella relativa ai nuovi termini e la correzione dei pesi. Le motivazioni alla base della scelta effettuata sono da ricercarsi nel fatto che avendo già realizzato un consistente dizionario dei termini, non si è ritenuto necessario aumentarlo ulteriormente, inoltre per quanto riguarda il passo di correzione dei pesi, la riduzione dell’errore introdotto risulta essere trascurabile se si considera il tempo necessario al calcolo delle matrici descritte nel paragrafo 2.4.1 per effettuare tale passo di correzione.

Sulla base di quanto già descritto nel paragrafo 2.4.2 si è costruita la matrice D, rappresentativa delle occorrenze dei termini nei nuovi documenti, e si è effettuato il calcolo della matrice F come

( )DUF Tkk |Σ=

utilizzando le matrici calcolate nella precedente elaborazione di

SVD(A). Ottenuta la matrice F, si è proceduto ad effettuare la sua

decomposizione in valori singolari, SVD(F). A questo punto, grazie alle relazioni espresse nel paragrafo 2.4.2. è

stato possibile considerare B in luogo di kA , ed avere quindi la

rappresentazione dei nuovi documenti all’interno della struttura semantica precostituita.


59

E’ da notare come siano velocizzate le operazioni effettuate nella procedura di SVD-Updating rispetto a quelle nella procedura completa.

L’esecuzione di SVD, la parte più onerosa in termini temporali, nel caso del ricalcolo totale (1500 documenti preesistenti e d documenti da inserire) avviene su una matrice di dimensioni circa pari a

)500.1(000.10 d+× , mentre nel caso di SVD-Updating la matrice su cui calcolare SVD è ridotta a )( dkk +× , dove k rappresenta la

dimensione dello spazio ridotto (generalmente 0,007 volte il numero delle righe di A, quindi in questo caso pari a 70).

Quindi volendo inserire 100 nuovi documenti, SVD viene calcolato

su una matrice 17070 × .

E’ anche da considerare come nel caso di SVD-Updating, nel

calcolo della rappresentazione dei nuovi documenti, viene anche rielaborata la rappresentazione di tutta la collezione dei documenti. Questo ricalcolo permette, al contrario di quanto avviene con il metodo del Folding- in, di ridurre in maniera considerevole l’errore introdotto nell’inserimento di nuovi set di documenti.


60

4. Procedure di testing e benchmarking

Se i fatti e la teoria non concordano, cambia i fatti. Albert Einstein

Lo scopo principale di questo progetto è stato quello di fornire una valida alternativa ai metodi di information retrieval attualmente disponibili per reti intranet. In questo ambito il vero problema da risolvere non è tanto il carico di lavoro eccessivo, come potrebbe essere quello che deve affrontare un motore di ricerca su internet, quanto l’efficacia degli accessi alle informazioni.

La ricerca tramite PageRank è stata implementata per mostrare come un algoritmo fondamentalmente realizzato per lavorare su insiemi di pagine web, con una definita struttura di collegamenti, possa essere applicato a documenti che non presentano una struttura di questo tipo.

Per valutare l’efficacia di questo algoritmo sono stati implementati altri due metodi di ricerca: LSI e Text Matching (per le loro specifiche vedere paragrafo 2.6).

LSI a fronte di tempi di risposta abbastanza elevati permette un ottimo retrieval delle informazioni mentre Text Matching assicura dei buoni tempi di risposta.

In questo paragrafo si affronteranno le tematiche relative al test dell’applicazione mostrando sia le analisi dei tempi di attesa che l’effettiva efficacia delle varie tecniche implementate.


61

4.1. Modalità di test Tutte le prove sono state eseguite su un elaboratore con le seguenti caratteristiche:

• CPU AMD K7 600MHz • 390 MB Ram • HD 40GB • S.O. Windows 2000 Professional • Microsoft SQL Server 7.0 • Application Server Orion 1.4.5 • Java VM (JDK 1.3)

Le pagine utilizzate sono state prelevate dal sito www.oreilly.com

che offre diversi libri in versione elettronica (html) con una struttura divisa in capitoli e paragrafi, ciò è stato estremamente utile in quanto ha permesso di controllare più efficacemente i risultati delle varie query. Il numero dei documenti per ciascun libro, rispetto al totale, è stato diviso nel seguente modo:

• Libro 1 : 21

dei documenti totali

• Libro 2 : 31


• Libro 3 : 61


I tre libri si occupano di argomenti relativamente scorrelati tra loro,

sebbene si sia cercato, nella scelta dei tre testi, di avere delle tematiche in comune per poter controllare sia che la ricerca LSI restituisca pagine rilevanti su temi simili, sia il comportamento di PageRank.


62

La fase di test è stata eseguita in modo da evidenziare al meglio le

caratteristiche di prestazioni dell’applicazione, per far ciò si è testata, in modo parametrico rispetto alle grandezze significative di volta in volta incontrate, l’efficacia 22 e l’efficienza 23 degli algoritmi di ricerca utilizzati. Il parametro più importante tenuto in considerazione, è la dimensione del sottospazio ridotto dei concetti (k), tramite il quale è possibile stabilire quanto ogni documento tenda ad essere simile agli altri, a parità di argomenti trattati. Altro parametro tenuto in considerazione è la specificità della query, a tale proposito si è cercato di effettuare sia query specifiche, che richiedevano informazioni particolari su un determinato soggetto, sia delle query generiche che richiedevano informazioni su un argomento generale, considerando come rilevanti anche i documenti ritornati su argomenti correlati a quello richiesto.

Per ogni query effettuata si sono esaminate le prime 20 occorrenze

ritornate dal motore di ricerca, le altre sono state ignorate in quanto un utente generico tende a non dare importanza alle pagine oltre un certo numero. In pratica se nei primi 20 risultati non c’è nulla di effettivamente utile la ricerca è considerata fallita.

Per ogni risultato della ricerca ne è stata valutata la rilevanza in

funzione della query effettuata. Nel caso in cui il documento ritornato fosse oggettivamente diverso dalla tipologia richiesta, si è valutato se l’argomento trattato avesse in qualche modo una correlazione con la query effettuata, in tale caso il documento ritorna to è stato considerato rilevante.

22 Intesa come qualità dei risultati ritornati dall’algoritmo di ricerca (rilevanza). 23 Intesa come le risorse necessarie all’esecuzione dell’algoritmo (tempo di risposta).


63

4.2. Riduzione dello spazio dei concetti Prima di procedere con i risultati dei test, è necessario soffermarsi sugli effetti delle differenti scelte del parametro k, rappresentante la dimensione del sottospazio dei concetti.

Questo parametro definisce la modalità con cui è determinata la similarità tra i vari documenti della collezione, un valore elevato di k fa sì che due pagine siano considerate simili solo se i concetti comuni sono molti (al limite, per k = n°righe di A, si ottiene un matching letterale tra tutti i termini dei documenti) mentre per valori più bassi il grado di similarità tra le pagine tende a crescere (al limite, per k = 1, tutti i documenti sono ritenuti simili tra loro). Quindi un elevato valore di k tenderà a far diminuire il numero di archi nel grafo di similarità, e in quello utilizzato per PageRank, mentre un basso valore farà aumentare il numero di questi archi.

Come sarà possibile vedere tra breve, queste differenti situazioni si ripercuoteranno in modo significativo, soprattutto per l’applicazione della ricerca LSI, nell’efficacia delle ricerche.


64

4.3. Indici utilizzati nei test Studiare la qualità del retrieval delle informazioni risulta intrinsecamente difficile poiché la stima della bontà dei risultati di un’interrogazione è spesso soggettiva perché legata al significato che si intende dare alla query, in particolare basti pensare all’uso di sinonimi.

Per superare questi problemi, nei test sono state sempre utilizzate delle query non ambigue, con una struttura molto semplice, e per le quali l’interpretazione dei risultati fosse il più possibile univoca.

Per dare un’indicazione oggettiva dell’efficacia dei risultati sono

stati utilizzati due indicatori [RB99]

Recall definito come collezionenellarilevantidocumentitotalen

ritornatirilevantidocumentin°

°

Precision definito come querydallarestituitidocumentitotalen

ritornatirilevantidocumentin°

°

Il primo parametro fornisce l’indicazione di quanto il metodo riesca

a trovare il maggior numero di documenti pertinenti, mentre il secondo, evidenzia il grado di rilevanza dei documenti ritornati rispetto al totale fornito dalla query.

Al fine di descrivere meglio il comportamento dei vari indici definiti si è utilizzata una particolare notazione utilizzata in letteratura,


65

per rappresentare al variare della dimensione della finestra di risposta24, le variazioni dei parametri esaminati.

I test sono stati eseguiti utilizzando l’algoritmo di ricerca LSI, PageRank- indegree, PageRank-simil e Text Matching, e ogni singola query è stata ripetuta al variare del parametro k, scelto tra le tre opzioni disponibili (low/normal/high) e, come detto precedentemente sono stati considerati solo i primi 20 risultati ritornati dall’applicazione dei quattro algoritmi di ricerca, perciò la dimensione massima della finestra di risposta è pari a 20.

Nei grafici ottenuti, si è riportato sull’asse delle ascisse la

dimensione della finestra di risposta, mentre su quello delle ordinate il valore percentuale dell’indice esaminato.

24 Una finestra di risposta pari, ad esempio, a 5 vuol dire considerare solamente i primi 5 documenti restituiti dal motore di ricerca.


66

4.4. Recall e Precision A partire dalle definizioni date nel paragrafo precedente e tenendo in considerazione il particolare modo utilizzato per la rappresentazione dei risultati, le figure 4.1, 4.2 e 4.3 mostrano il variare dell’indice di recall al variare della dimensione della finestra di risposta alla query.

Figura 4.1: Andamento dell’indice di recall per k = low

Media Recall k=low

0%

10%

20%

30%

40%

50%

60%

70%

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20dimensione finestra di risposta

Avg LSI

Avg PR-deg

Avg PR-sim

Avg TM


67

Figura 4.2: Andamento dell’indice di recall per k = norm

Figura 4.3: Andamento dell’indice di recall per k = high

Media Recall k=norm

0%

10%

20%

30%

40%

50%

60%

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20dimensione della finestra di risposta

Avg LSI

Avg PR-deg

Avg PR-sim

Avg TM

Media Recall k=high

0%

10%

20%

30%

40%

50%

60%

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

dimensione della finestra di risposta

Avg LSI

Avg PR-deg

Avg PR-sim

Avg TM


68

Com’è possibile vedere dalle figure 4.1, 4.2, 4.3, in cui è mostrato l’andamento della media del parametro di recall sul numero di query effettuate, la ricerca tramite LSI si rivela sempre estremamente efficace ritornando circa la metà dei documenti rilevanti con una dimensione della finestra di risposta di soli 11 documenti, mentre PageRank e Text Matching necessitano di una finestra di dimensioni doppie per ottenere gli stessi risultati.

E’ interessante notare come per k = low, LSI abbia delle

prestazioni notevoli, questo è da imputare al fatto che con una dimensione ridotta dello spazio dei concetti sono trovate molte più similitudini tra i documenti, mentre per k = high i documenti tendono ad essere meno simili tra loro e quindi LSI non riesce a stabilire le relazioni corrette tra di essi.

Inoltre va osservato che Text Matching ha un comportamento

costante al variare della dimensione di k, mentre PageRank migliora all’aumentare della dimensione dello spazio dei concetti acquisendo un discreto margine rispetto a TM nel caso k = norm e k = high.

Accanto all’indice di recall va considerato anche il comportamento

dell’indice di precision calcolato in maniera leggermente differente dalla definizione data. Infatti invece di calcolare l’indice di precision tramite l’espressione data nel paragrafo 4.3 si utilizza la seguente riscrittura

Precision = rispostadifinestragrandezzaritornatirilevantidocumentin°


69

Figura 4.4: Andamento dell’indice di precision per k = low

Figura 4.5: Andamento dell’indice di precision per k = norm

Media Precision k=low

25%

35%

45%

55%

65%

75%

85%

95%


Avg LSI

Avg PR-deg

Avg PR-sim

Avg TM

Media Precision k=norm

25%

35%

45%

55%

65%

75%

85%

95%

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20


Avg LSI

Avg PR-deg

Avg PR-sim

Avg TM


70

Figura 4.6: Andamento dell’indice di precision per k = high

Anche per quanto riguarda l’indice di precision, rispetto alle

considerazioni fatte sulla ricerca LSI per l’indice di recall, per bassi valori di k si ottengono degli ottimi risultati che vanno diminuendo all’aumentare della dimensione dello spazio ridotto.

Analoghe considerazioni possono essere fatte per TM, che risulta sempre costante al variare di k, e per PR che presenta un netto miglioramento nei confronti di TM per k = norm.

E’ interessante analizzare anche i grafici della media effettuata prendendo in considerazioni il variare del parametro k, ossia la media dei tre diversi grafici ottenuti per k = low, k = norm e k = high.

Media Precision k=high

25%

35%

45%

55%

65%

75%

85%

95%

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20


Avg LSI

Avg PR-deg

Avg PR-sim

Avg TM


71

Figura 4.7: Andamento della media dell’indice di recall

Figura 4.8: Andamento della media dell’indice di precision

Media Recall

0%

10%

20%

30%

40%

50%

60%

70%


Avg LSI (avg)

Avg PR-deg (avg)

Avg PR-sim (avg)

Avg TM (avg)

Media Precision

25%

35%

45%

55%

65%

75%

85%

95%

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20


Avg LSI (avg)

Avg PR-deg (avg)

Avg PR-sim (avg)

Avg TM (avg)


72

Nelle figure 4.7 e 4.8 è da notare come i valori associati alla ricerca

LSI siano sempre superiori a quelli ottenuti per PR e TM, questo è anche da imputarsi al fatto che la ricerca LSI sfrutta pesantemente la struttura dati calcolata tramite SVD. Questo è un innegabile vantaggio per la ricerca LSI in quanto TM si basa esclusivamente sui dati memorizzati nel database, mentre PR, nelle sue due versioni, utilizza la pseudo struttura di link calcolata sulla base dei dati utilizzati anche dalla ricerca LSI, ma mentre quest’ultima utilizza effettivamente e in modo diretto le informazioni contenute nella struttura dati calcolata, PR lavora su una sorta di rielaborazione di questa struttura e quindi, non potendo accedere direttamente a tutte le informazioni disponibili, è costretto ad effettuare delle scelte e ad introdurre così una certa quantità d’errore nella rappresentazione che calcola.


73

4.5. Precision agli 11 livelli standard di recall Una volta calcolati gli indici di recall e di precision per tutte le query è possibile effettuare un confronto diretto tra di loro.

Per poter valutare le prestazioni di un sistema di information retrieval sulla base di un determinato insieme di query, è possibile calcolare la media dell’indice di precision nel seguente modo

∑=

=qN

i q

i

NrP

rP1

)()(

in cui )(rP è il valore medio dell’indice di precision per il livello di

recall r, Nq è il numero di query utilizzate mentre Pi(r) è il valore di precision al livello di recall r per la query i-esima.

Tenendo però conto del fatto che i livelli di recall per ogni singola query possono essere distinti dagli 11 livelli standard25, è necessario utilizzare la seguente procedura di interpolazione :

Sia rj, { }10,,2,1,0 Κ∈j , il riferimento al j-esimo livello di

recall (ad esempio, r5 si riferisce al livello di recall 50%), allora il livello interpolato di precision è dato dal massimo valore di precision tra il j-esimo livello di recall e il (j+1)-esimo livello di recall.

25 Gli 11 livelli standard sono i seguenti: 0%, 10%, 20%, 30%, 40%, 50%, 60% 70% 80%, 90%, 100%.


74

Ad esempio, considerando la tabella dei valori di recall e precision per una finestra di document i da 1 a 10

Dim fin recall precision

1 6% 100%

2 6% 50%

3 13% 67%

4 19% 75%

5 25% 80%

6 31% 83%

7 38% 86%

8 44% 88%

9 50% 89%

10 50% 80%

Si ottengono i seguenti livelli di precision interpolati

recall precision

0% 100%

10% 75%

20% 80%

30% 86%

40% 89%

50% 89%

60% 0%

70% 0%

80% 0%

90% 0%

100% 0%


75

E’ da notare come per i valori di recall maggiori del 50% l’indice

di precision vada a 0 poiché non tutti i documenti rilevanti sono stati restituiti.

Fatte le dovute premesse è ora possibile introdurre l’analisi delle prestazioni dei diversi algoritmi in base ai grafici di precision agli 11 livelli standard di recall.

Figura 4.9: Interpolazione di Precision vs Recall con k = high

-5%

15%

35%

55%

75%

95%

0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%livelli standard di recall

prec

isio

n

PR-deg

PR-sim

LSI

TM


76

Figura 4.10: Interpolazione di Precision vs Recall con k = norm

Figura 4.11: Interpolazione di Precision vs Recall con k = low

-5%

15%

35%

55%

75%

95%

0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%livelli standard di recall

prec

isio

n

PR-deg

PR-sim

LSI

TM

-5%

15%

35%

55%

75%

95%

0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%

livelli standard di recall

prec

isio

nPR-deg

PR-sim

LSI

TM


77

Le curve rappresentate nelle figure da 4.9 a 4.11 sono normalmente utilizzate in letteratura per la comparazione di differenti algoritmi di information retrieval. La prima analisi che è possibile effettuare visivamente consiste nel cercare le curve che più si avvicinano all’angolo in alto a destra, e che garantiscono quindi degli alti valori di precision e di recall.

Anche per questi grafici è immediato osservare come la ricerca LSI

batta in entrambe le configurazioni di k tutti gli altri metodi, in particolare per k = low, e come, per k elevato, PageRank si riveli più efficace del Text Matching.


78

4.6. Tempi di risposta A prescindere dai risultati ottenuti nei due paragrafi precedenti, un altro aspetto fondamentale riguarda i tempi di risposta del motore di ricerca a fronte di una richiesta utente. Decretare infatti la ricerca LSI come migliore, in funzione solamente degli alti indici di recall e precision ritornati, senza ulteriori considerazioni, non è la metodologia più opportuna. Bisogna infatti considerare il tempo impiegato dalla ricerca LSI a restituire le pagine richieste, ossia la sua effettiva efficienza, in funzione della dimensione del set di documenti.

Figura 4.12: Tempi di risposta dei tre algoritmi di ricerca

La figura 4.12 mostra come varino i tempi di risposta dei diversi

algoritmi di ricerca in funzione del numero di documenti analizzati.

30

52

6,114

24

0,8 0,91,2

0,110,11

1,5

7

5

0,5

3,5

0

10

20

30

40

50

60

500 1000 1500 2000 3000n° documenti

seco

ndi (

LSI)

0

1

2

3

4

5

6

7

8

seco

ndi (

PR

,TM

)

LSIPRTM


79

E’ subito da far notare come sono presenti due diversi assi, uno per la ricerca LSI che impiega da poco meno di 10 secondi per un piccolo insieme di documenti, fino ad oltre 50 secondi per un insieme di 3000 documenti, e l’altro asse per PR e TM che hanno tempi di risposta inferiori ai 10 secondi. E’ quindi opportuno osservare come la bontà della ricerca LSI (buona efficacia) sia in parte vanificata dai troppo elevati tempi di risposta (pessima efficienza), mentre le lacune evidenziate dalla ricerca PR (media efficacia) sono compensate in funzione dell’elevata velocità di risposta (ottima efficienza).

E’ opportuno notare che per quanto riguarda PR, su un insieme di

3000 documenti, i tempi di risposta si mantengono al di sotto dei due secondi, indubbiamente questo è da considerarsi un ottimo risultato.


80

4.7 SVD Updating In questo paragrafo si vuole centrare l’attenzione sulla procedura

utilizzata per l’inserimento dinamico di documenti, all’interno della struttura semantica precostituita.

Tenendo conto delle modalità realizzative descritte nei paragrafi

2.4 e 3.4.3 qui di seguito sarà mostrata la variazione dell’efficacia a fronte dell’utilizzo del metodo di SVD-Updating comparata a quella mostrata nell’uso di SVD sull’intero set di documenti.

A partire dall’insieme iniziale di documenti, si sono considerati

differenti sottoinsiemi di esso su cui è stato applicato SVD-Updating al fine di ottenere la stessa dimensione iniziale dell’insieme. Ossia, si sono inseriti via via i documenti rimanenti fino a ricostituire l’insieme iniziale.

Si indicano con nSS ,,1 Κ i sottoinsiemi propri dell’insieme S, di

tutti i documenti, e con nRR ,,1 Κ la parte rimanente, necessaria

ricostruire l’insieme S stesso

ii SSR −=

quindi Ri rappresenta l’insieme dei documenti mancanti al sottoinsieme Si per essere uguale all’insieme S. Denotata con SVDU(Si, Ri) la funzione che applica il metodo di SVD-Updating all’insieme Si, inserendo il set di documenti Ri, i test sono stati effettuati sugli insiemi finali così ricavati:

1. SVDU(Si, Ri)


81

2. SVDU( ... SVDU(SVDU(Sj, 1jR ), 2

jR ) ... , xjR ) in cui

xjR rappresenta la x-esima partizione dell’insieme Rj,

Υx

i

ijj RR

1=

= con 0=∩ nj

mj RR per ],1[, xnm ∈∀

In altre parole il primo metodo inserisce in una sola volta tutti i

documenti mancanti all’insieme Si per arrivare ad essere come l’insieme S, mentre il secondo metodo divide l’insieme dei documenti da inserire in x partizioni distinte ed effettua per x volte la procedura di inserimento dei documenti.

Nelle figure 4.13 e 4.14 sono mostrati gli andamenti dell’indice di recall per l’algoritmo di ricerca LSI e per PageRank, per quest’ultimo si è effettuata la media tra PR-deg e PR-sim, al solito variare della dimensione della finestra di risposta e anche alla differente applicazione di SVD-Updating.

Ricordando il primo metodo di applicazione di SVD-Updating, ossia SVDU(Si, Ri) si sono considerati due insiemi Si: uno a cui mancavano 200 documenti (Sa) rispetto all’originale S ed un altro a cui ne mancavano 400 (Sb). Per entrambi questi insiemi è stato calcolato direttamente SVD-Updating, ottenendo subito l’insieme finale su cui effettuare i test.

Il secondo metodo è stato invece applicato su una partizione in quattro blocchi dell’insieme di documenti rimanente, ossia indicato con Ra e Rb rispettivamente l’insieme dei documenti mancanti agli insiemi Sa e Sb, si è applicato SVD-Updating secondo le seguenti modalità:


82

SVDU( SVDU( SVDU( SVDU( Sa, 1aR ), 2

aR ) , 3aR ) , 4

aR )

con Υ4

1=

=i

iaa RR .

Quindi l’insieme Ra dei documenti rimanenti è stato diviso in quattro blocchi ed è stato calcolato SVD-Updating in maniera progressiva, fino a ricostruire l’insieme iniziale dei documenti S.

Figura 4.13: Indice di Recall per LSI con SVD-Updating

Recall LSI

0%

10%

20%

30%

40%

50%

60%


LSI(totale)LSI(200)LSI(50*4)LSI(400)LSI(100*4)


83

Figura 4.14: Indice di Recall per PageRank con SVD-Updating

E’ da notare come le prestazioni peggiorino sia all’aumentare del

numero di documenti inseriti sia all’aumentare del numero di passi utilizzati per inserire tutti i documenti, infatti le “peggiori” prestazioni si ottengono per l’inserimento di 400 documenti a blocchi successivi di 100.

Nelle prossime due figure (4.15 e 4.16) sono invece mostrati gli

andamenti dell’indice di Precision, per LSI e PageRank, in funzione sempre della dimensione della finestra di risposta e degli analoghi metodi di implementazione di SDV-Updating.

Recall PR

0%

10%

20%

30%

40%

50%

60%


PR-avg(totale)

PR-avg(200)

PR-avg(50*4)

PR-avg(400)

PR-avg(100*4)


84

Figura 4.15: Indice di Precision per LSI con SVD-Updating

Figura 4.16: Indice di Precision per PageRank con SVD-Updating

Precision LSI

30%

40%

50%

60%

70%

80%

90%

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20


LSI(totale)

LSI(200)

LSI(50*4)

LSI(400)

LSI(100*4)

Precision PR

25%

35%

45%

55%

65%

75%

85%

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20


PR-avg(totale)

PR-avg(200)

PR-avg(50*4)

PR-avg(400)

PR-avg(100*4)


85

5. Conclusioni

La scienza è sempre imperfetta. Ogni volta che risolve un problema, ne crea almeno dieci nuovi.

George Bernard Shaw

I principali obiettivi di questa tesi erano principalmente di riuscire ad analizzare un insieme di documenti grande a piacere e di effettuare delle rigorose procedure di test secondo i metodi più noti proposti in letteratura.

Entrambi gli obiettivi sono stati raggiunti; il primo rinunciando a parte della velocità di esecuzione per poter trattare, senza i problemi di eccessiva allocazione di memoria principale, un numero elevato di documenti (test con 5000 documenti non hanno creato problemi di sorta, a parte un’elevata occupazione di spazio su memoria secondaria), il secondo ricavando i parametri chiave per l’analisi di sistemi di information retrieval.

Parallelamente agli obiettivi fondamentali c’è stata tutta un’altra serie di obiettivi assolutamente non trascurabili.

A partire dal tentativo di accelerare l’esecuzione del calcolo di

SVD, tramite l’applicazione di alcune interessanti teorie sull’aggiunta di particolari tipologie di rumore alla matrice delle occorrenze, continuando con l’introduzione di nuovi algoritmi di ricerca al motore precedentemente realizzato e infine la possibilità di inserimento dinamico di documenti alla collezione senza dover ogni volta ricostruire da capo tutta la struttura semantica, ma intervenendo, con delle piccole modifiche, direttamente su di essa.


86

Ovviamente molte delle parti sviluppate presentano dei margini di miglioramento. A partire dalla velocizzazione di SVD che non è riuscita a causa delle modalità con cui il modulo esterno, utilizzato per calcolare SVD, effettua i prodotti matrice-vettore, non ottimizzato e quindi non adatto a sfruttare al meglio i numerosi zeri introdotti nella matrice termini-documenti. Quindi ricercando un modulo esterno che utilizzi al meglio gli zeri introdotti, oppure riuscendo a modificare in qualche modo il modulo utilizzato, si può ben sperare di riuscire a velocizzare la procedura di calcolo di SVD.

Anche la parte riguardante le operazioni di trasformazione delle matrici può essere migliorata, studiando un diverso algoritmo per effettuare più rapidamente la trasposta di una matrice densa, oppure per quanto riguarda le procedure di moltiplicazione, magari studiando degli altri particolari formati per la memorizzazione dei file, oppure rinunciando a lavorare con dei double.

Altre modifiche possono essere fatte anche agli algoritmi utilizzati per calcolare PageRank, oppure applicare direttamente una differente realizzazione di PageRank stesso (si ricorda che quelle utilizzate si sono basate su un’implementazione approssimata si PageRank e su dei grafici di connessione tra i documenti ottenut i tramite delle euristiche), al fine di migliorare il ranking delle pagine ed ottenere dei migliori valori nei parametri utilizzati nell’analisi delle prestazioni.

Un’altra semplice miglioria consisterebbe nella creazione di classi

che permettano la lettura di documenti in formato pdf oppure doc, al fine di poter analizzare un più elevato insieme di documenti.

Altri sviluppi possibili riguardano la scalabilità, questa caratteristica non è stata ancora presa in considerazione, ma distribuire


87

il carico computazionale in maniera più equilibrata tra più risorse di calcolo può, naturalmente, garantire un miglioramento delle prestazioni.

Va infine notato come tutte le funzionalità che possono essere migliorate/introdotte possono tranquillamente utilizzare il sistema già realizzato, questo grazie ad un’accurata progettazione delle classi, che permette anche di utilizzare solamente alcune parti funzionali (realizzate in maniera totalmente indipendente l’una dalle altre) al fine di creare uno specifico tool.


88

Ringraziamenti

Chi trova un amico trova un tesoro, ma chi trova un tesoro trova tanti amici.

Desidero innanzitutto ringraziare l’ing. Stefano Millozzi per aver fornito il codice sorgente della sua applicazione con le relative spiegazioni (senza mai aver pronunciato RTFM), nonché per l’aiuto durante la stesura del mio codice, l’ing. Luigi Laura per i suggerimenti fondamentali al corretto sviluppo della fase di test, per aver trovato il benedetto set su cui effettuare le ricerche e per le “opportune” immagini da intercalare nei lucidi della presentazione, l’ing. Andrea Vitaletti che ha materialmente scritto il codice per l’implementazione di PageRank e, nonostante io abbia fiducia nelle implementazioni fatte da persone ritenute più brave, nutro ancora dubbi su come effettivamente sembra funzionare PageRank (scherzo), l’ing. Camil Demetrescu per avermi prestato più volte, anche a sua insaputa la sua scrivania, infine, ma non certo per importanza, l’ing. Pamela Ruisi che è riuscita a dare una forma ad una tesi che altrimenti sarebbe sembrata scritta da un insieme di scimmie chiuse in una stanza con una macchina da scrivere


89

Bibliografia [DDF+90] S. Deerwester, S. Dumais, G. Furnas, T.Landauer, and R.

Harshman. Indexing by latent semantic analysis. Journal of the American Society for Information Science, 41 (6)391-407, 1990.

[GR71] G. Golub and C. Reinsch. Handbook for automatic computation II, linear algebra. Springer-Verlag, New York, 1971.

[GL89] G. Golub and C. Van Loan. Matrix Computation. Johns-Hopkins, baltimore, second edition, 1989.

[Ber92a] M.W. Berry. Large scale singular value computation. International Journal of Supercomputer Application, 6(1):13-49, 1992.

[OB94] G.W. O’Brien. Information Management Tools for Updating an SVD-Encoded Indexing Scheme. Thesis for the master of Science Degree, University of Tennessee, Knoxville, 1994.

[Mil01] S. Millozzi. Un approccio innovativo al content management basato su latent semantic indexing e reti di similarità. Tesi di Laurea, Università La Sapienza, Roma, 2001.

[LF01] S. La Fauci. Metodologie innovative per il progetto di un sistema di content management. Tesi di Laurea, Università La Sapienza, Roma, 2001.

[Kle98] J. M. Kleinberg. Authoritative sources in a hyperlinked environment. In Proceedings of the Nineth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998.


90

[AS01] D.Achlioptas, F. McSherry. Fast computation of low rank matrix approssimation, ACM Symposium on Theory of Computing, 611-618, 2001.

[BDO+] M.Berry, T.Do, G.O’Brien, V.Krisna, S.Varadhan. SVDPACKC (version 1.0) User’s Guide.

[PBM+98] L.Page, S.Brin, R.Motwani, T.Winograd. The PageRank Citation Ranking: Bringing Order to the Web. 1998

[SS00] L.Sciavicco, B.Siciliano. Robotica Industriale, Modellistica e controllo di manipolatori, seconda edizione. McGraw-Hill 2000.

[BR99] R.Baeza-Yates, B.Riberio-Neto. Modern Information Retrieval. Addison Wesley, 1999.


91

Appendice A Velocizzazione di SVD A seguito di analisi preliminari effettuate con set di documenti le cui dimensioni erano state fissate a circa 1000, l’applicazione del metodo descritto nel paragrafo 3.4.2 aveva dato di che ben sperare.

Figura A.1: Risparmio di tempo di elaborazione e peggioramento prestazioni con

l’aggiunta di zeri alla matrice dei temini-documenti (n° doc ˜ 1000)

Come ben visibile nella figura A.1 a fronte di un peggioramento delle prestazioni di un 20% si dimezzava letteralmente il tempo necessario all’esecuzione di SVD.

0%

10%

20%

30%

40%

50%

60%

10% 20% 30% 40% 50% 60% 70%

% zeri aggiunti

% t. elab. risparmiato

% pegg. prestazioni


92

Purtroppo a seguito di analisi successive con set di documenti di dimensioni doppie, si ottenevano ben altri risultati.

Figura A.2: Risparmio di tempo di elaborazione e peggioramento prestazioni con

l’aggiunta di zeri alla matrice dei temini-documenti (n° doc ˜ 2000)

Com’è visibile dalla figura A.2 l’applicazione del metodo ad un set di documenti più ampio non ha dato i risultati sperati, infatti a fronte di un peggioramento delle prestazioni del 20% si ha una riduzione del tempo di esecuzione di SVD solo del 15%.

Questo è dovuto al fatto che il modulo esterno utilizzato non ottimizza in maniera adeguata le moltiplicazioni matrice-vettore e a fronte di matrici di elevata dimensione perde la maggior parte del tempo ad effettuare accessi alle righe e colonne, quando invece potrebbe direttamente scartarle essendo composte da tut ti zeri.

0%

10%

20%

30%

40%

50%

60%

10% 20% 30% 40% 50% 60% 70%

% zeri aggiunti

% t. elab. risparmiato

% pegg. prestazioni

Integrazione delle tecniche di web information retrieval e...

Documents

Transcript of Integrazione delle tecniche di web information retrieval e...