LATENT SEMANTIC INDEXING Limiti della ricerca per parole chiave • I metodi di ranking tradizionali calcolano l’attinenza di un documento ad una query sulla base della presenza o meno di parole contenute nella query: un termine o è presente o non lo è • Nel LSI la ricerca avviene per concetti: ma un concetto non è l’astrazione-generalizazzione di un termine (es: golf vestiario) bensì un insieme di termini correlati (golf, maglia, vestito) detti co-occorrenze o dominio semantico • Data una collezione di documenti, LSI è in grado di rilevare che alcune n-uple di termini co-occorrono frequentemente (es: gerarchia, ordinamento e classificazione) • Se viene fatta una ricerca con gerarchia, ordinamento vengono “automaticamente” recuperati documenti che contengono anche (e eventualmente solo!) classificazione Dominio Semantico k Base di documenti (20) Golf Car Topgear Petrol GTI Golf Car Clarkson Petrol Badge Golf Petrol Topgear Polo Red Golf Tiger Woods Belfry Tee Car Petrol Topgear GTI Polo Fish Pond gold Petrol Koi Motor Bike Oil Petrol Tourer Bed lace legal Petrol button soft Petrol cat line yellow wind full sail harbour beach report Petrol Topgear June Speed Office Pen Desk Petrol VDU con il modello keyword vengono estratti 4 documenti PC Dell RAM Petrol Floppy Core Petrol Apple Pip Tree Pea Pod Fresh Green French Lupin Petrol Seed May April Friend Pal Help Petrol Can Paper Petrol Paste Pencil Roof Card Stamp Glue Happy Send Toil Petrol Work Time Cost Selezione dei documenti basata sul termine ‘Golf’ Golf Car Topgear Petrol GTI Golf Car Clarkson Petrol Badge Golf Petrol Topgear Polo Red Golf Tiger Woods Belfry Tee Tutti i 20 documenti Golf Car Topgear Petrol GTI Golf Car Clarkson Petrol Badge Golf Petrol Topgear Polo Red Golf Tiger Woods Belfry Tee Car Petrol Topgear GTI Polo Fish Pond gold Petrol Koi PC Dell RAM Petrol Floppy Core Petrol Apple Pip Tree Pea Pod Fresh Green French Lupin Petrol Seed May April Motor Bike Oil Petrol Tourer Bed lace legal Petrol button soft Petrol cat line yellow wind full sail harbour beach report Petrol Topgear June Speed Office Pen Desk Petrol VDU Friend Pal Help Petrol Can Paper Petrol Paste Pencil Roof Card Stamp Glue Happy Send Toil Petrol Work Time Cost Selezione basata su ‘Golf’ Golf Car Topgear Petrol GTI Golf Car Clarkson Petrol Badge Golf Petrol Topgear Polo Red Golf Tiger Woods Belfry Tee rank dei doc selezionati vediamo quali sono le parole più rilevanti associate a Golf di questi 4 documenti. Esse sono: Car, Topgear and Petrol wf.idf Car 2 *(20/3) = 13 Topgear 2 *(20/3) = 13 Petrol 3 *(20/16) = 4 Tutti i 20 documenti Golf Car Topgear Petrol GTI Golf Car Clarkson Petrol Badge Golf Petrol Topgear Polo Red Golf Tiger Woods Belfry Tee Car Petrol Topgear GTI Polo Fish Pond gold Petrol Koi PC Dell RAM Petrol Floppy Core Petrol Apple Pip Tree Pea Pod Fresh Green French Lupin Petrol Seed May April Motor Bike Oil Petrol Tourer Bed lace legal Petrol button soft Petrol cat line yellow wind full sail harbour beach report Petrol Topgear June Speed Office Pen Desk Petrol VDU Friend Pal Help Petrol Can Paper Petrol Paste Pencil Roof Card Stamp Glue Happy Send Toil Petrol Work Time Cost Selezione basata su ‘Golf’ Golf Car Topgear Petrol GTI Golf Car Clarkson Petrol Badge Golf Petrol Topgear Polo Red Golf Tiger Woods Belfry Tee poiché le parole sono pesate anche rispetto al loro idf, risulta che : Car e Topgear sono associate a Golf più di Petrol rank dei doc selezionati Car 2 *(20/3) = 13 Topgear 2 *(20/3) = 13 Petrol 3 *(20/16) = 4 Tutti i 20 documenti Golf Car Topgear Petrol GTI Golf Car Clarkson Petrol Badge Golf Petrol Topgear Polo Red Golf Tiger Woods Belfry Tee Car Petrol Topgear GTI Polo Fish Pond gold Petrol Koi Motor Bike Oil Petrol Tourer Bed lace legal Petrol button soft Petrol cat line yellow wind full sail harbour beach report Petrol Topgear June Speed Office Pen Desk Petrol VDU Selezione basata su ‘Golf’ Golf Car Topgear Petrol GTI Golf Car Clarkson Petrol Badge Golf Petrol Topgear Polo Red Golf Car Topgear Petrol GTI Golf Car Clarkson Petrol Badge Golf Petrol Topgear Polo Red PC Dell RAM Petrol Floppy Core Petrol Apple Pip Tree Pea Pod Fresh Green French Lupin Petrol Seed May April Ora cerchiamo ancora nella base di documenti, usando questo insieme Friend Paper Card Toil Pal Petroldi parole Stamp Petrolrappresentano che rank Help Paste Glue Work Petrol Pencil Happy Time il “dominio semantico” di Golf . Can Roof Send Cost dei La lista ora include un nuovo documento, non catturato sulla base della doc semplice ricerca per keywords. selezionati Golf Tiger Woods Belfry Tee selezione basata sul dominio semantico Golf Tiger Woods Belfry Tee Car Wheel Topgear GTI Polo Car 2 *(20/3) = 13 Topgear 2 *(20/3) = 13 Petrol 3 *(20/16) = 4 Tutti i 20 documenti Usando un ranking Pea Lupin Podco-occorrenza Petrol basato sullaFresh dei termini Seed Green May possiamo French April assegnare Motor Bed soft wind report Office Friend Paper Card Toil unPetrol miglior ai documenti. Bike lace Petrol full Petrol Pen Pal Stamp ranking Petrol rank Oil legal cat sail Topgear Desk Help Paste Glue Work Petrol Petrol line harbour June Petrol Petrol Pencil Happy che: Timeil documento Notate Tourer button yellow beach Speed VDU Can Roof Send Cost deiGolf, e più rilevante non contiene la parola Selezione basata su ‘Golf’ doc che uno dei documenti che la conteneva scompare (era infatti un senso “spurio”di Golf). selezionati Golf Car Topgear Petrol GTI Golf Car Clarkson Petrol Badge Golf Petrol Topgear Polo Red Golf Tiger Woods Belfry Tee Car Petrol Topgear GTI Polo Fish Pond gold Petrol Koi PC Dell RAM Petrol Floppy Core Petrol Apple Pip Tree Golf Car Topgear Petrol GTI Golf Car Clarkson Petrol Badge Golf Petrol Topgear Polo Red Golf Tiger Woods Belfry Tee Golf Car Topgear Petrol GTI Golf Car Clarkson Petrol Badge Golf Petrol Topgear Polo Red Golf Tiger Woods Belfry Tee selezione basata sul dominio semantico Rank 30 17 17 0 Car Wheel Topgear GTI Polo 26 Car 2 *(20/3) = 13 Topgear 2 *(20/3) = 13 Petrol 3 *(20/16) = 4 Esempio 2 Matrice termini-documenti L Co-occorrenze dei termini nei documenti A LT L n Aij n Aij L Lkj Lki Lkj k 1 T ik LTik LT Lkj L k 1 Aij è il numero di co-occorrenze nei documenti fra il termine i ed il termine j A trees,graph = (000001110)T(000000111)=2 Esempio 2 LLT w1 d1 d2 d3 1 0 1 1 1 0 w2 1 0 1 0 0 1 w3 0 1 1 0 1 0 w11 w12 w13 w21 w22 w23 w31 w32 w33 = Ma wij=wji quindi Simmetrica! 2 2 0 2 2 0 0 0 1 w11 w12 w13 w12 w22 w23 w13 w23 w33 Matrici delle co-occorrenze • Se L è una matrice nxm (termini x documenti) • Allora: – LTL è la matrice le cui righe ai rappresentano le cooccorrenze di termini fra di e dj, per ogni dj. Dato un documento, indica quali sono i documenti più simili. – LLT è la matrice le cui righe ai rappresentano le cooccorrenze nei documenti fra ti e tj per ogni tj. Dato un termine, indica quali sono i termini più correlati. – Usando, ad esempio, la matrice LLT potrei “espandere” ogni termine con quelli aventi il più alto valore di correlazione (cioè, aggiungere alla query in cui compare la parola w anche quelle che co-occorrono con w più frequentemente) Osservazione • Tutte le possibili co-occorrenze sarebbero assai di più dei termini singoli (detta L la matrice termini-documenti, dovrei calcolare A=LLT). • Tuttavia, sebbene la matrice A ha dimensionalità elevata la maggioranza delle celle hanno valore zero • Con i metodi classici ogni documento o query è un vettore in uno spazio t-dimensionale • LSI tenta di proiettare questo spazio in uno spazio di dimensione ridotta, in cui, anziché termini, le dimensioni rappresentano co-occorrenze o dominii semantici, ma solo quelli preponderanti • Tuttavia LSI utilizza per questa riduzione di rango solo strumenti matematici (singular value decomposition, SVD). Cosa significa “proiettare in uno spazio di concetti” T LL d1 Similarità fra documenti come sim fra vettori nello spazio delle co-occorrenze c13 d2 c12 c13 c123 c123 c23 d3 Similarità fra documenti come diagramma di Venn c23 c23 Singual value decomposition • Come detto, LSI proietta la matrice L terminidocumenti in uno spazio concettuale di dimensioni ridotte, dove le dimensioni sono gruppi di concetti che co-occorrono, definendo un “dominio semantico” • Il metodo utilizzato per effettuare questa proiezione è la singular value decomposition, un metodo algebrico. • Ci occorre un piccolo ripasso di algebra per capire questo metodo. Ripasso di algebra • Autovalori • Autovettori • Vettori e valori singolari Autovalori & Autovettori Eigenvectors o autovettori (di una matrice S) Esempio (right) eigenvector eigenvalue Quanti autovalori al massimo ha S? Ha soluzioni non nulle se Se S mxm, questa è un’equazione di grado m in λ che ha al più m soluzioni distinte (le radici del polinomio caratteristico) – possono essere complesse anche se S è reale. Esempio: calcolo di Eigenvalues and Eigenvectors 1 1 1 A v 4 3 5 3 • Def: Un vettore v Rn, v ≠ 0, è un autovettore di una matrice nn A con Av v corrispondente autovalore , se: 1 11 1 Av = v 4 3 5 3 3 1 3(1) 4 3 5(3) 12 4 4 12 12 Esempio di calcolo Ricorda il determinante ( 1)(M2x2 5) 3 0 di una matrice 1 1 A 3 5 det( A I ) 0 1 1 1 0 0 3 5 0 1 1 1 0 0 3 5 0 1 1 0 3 5 2a 6b 5 3 0 det M | M | ad bc c d 6 8 0 2 ( 4)( 2) 0 1 4Polinomio , 2 2 2 e 4(A sono i due I)v 0 eigenvalues di A caratteristico 1 4 2 1 2 0 5 4 3 0 0 3 v 1 3 1 0 3 0 3 0 3 ( A I )v 0 1 2 1 4 0 1 3 5 2 0 1 v1 0 3 3 3 0 0 3 3 0 Approfondimenti • http://www.sosmath.com/matrix/eigen0/eigen0.html • http://www.cs.ut.ee/~toomas_l/linalg/lin2/node14.ht ml Significato geometrico di autovalori e autovettori • La moltiplicazione di una matrice A mxn per un vettore v è una trasformazione lineare che trasferisce il vettore v dallo spazio Rn a Rm • Gli autovettori sono quei vettori la cui direzione non cambia per effetto della trasformazione A Moltiplicare per una matrice è una trasformazione lineare Av=v In questa trasformazione lineare della Gioconda, l'immagine è modificata ma l'asse centrale verticale rimane fisso. Il vettore blu ha cambiato direzione, mentre quello rosso no. Quindi il vettore rosso è un autovettore della trasformazione e quello blu no. Inoltre, poiché il vettore rosso non è stato né allungato, né compresso, né ribaltato, il suo autovalore è 1 (quindi l’autovalore indica una costante di traslazione dei punti dell’immagine nella direzione blu) . Tutti i vettori sull'asse verticale sono multipli scalari del vettore rosso, e sono tutti autovettori. Trasformazioni lineari • Se v è un vettore qualsiasi, A una matrice nxm (trasformazione lineare), vi gli autovettori di A e i gli autovalori, la trasformazione del vettore è completamente definita da autovalori e autovettori di A: Av 1(v1 v) 2 (v2 v) ...k (vk v) Riduzione della dimensionalità (o approssimazione di rango k di una matrice) Moltiplicare una matrice per un vettore ha due effetti sul vettore: rotazione (il vettore cambia coordinate) e scalatura (la lunghezza del vettore cambia). La massima compressione e rotazione dipendono dagli autovalori della matrice (vedi formula precedente) Riduzione della dimensionalità (o approssimazione di rango k di una matrice) Nello schiacciamento e compressione il ruolo principale lo giocano i valori singolari più grandi della matrice (s1 e s2 in figura) Gli autovalori descrivono dunque quanto la matrice distorce (riduce e comprime) il vettore originario Riduzione della dimensionalità (o approssimazione di rango k di una matrice) Qui invece supponiamo che, invece di ruotare un vettore, ruotiamo un insieme di vettori ortonormali. Se, ad es, di tre autovalori uno lo trascuriamo perché più piccolo, è come se rimuovessimo una dimensione (se invece eliminiamo due autovalori, l’ellissoide si schiaccia su una retta) Cosa c’entra tutto ciò? • Riassumiamo: – Se q è il vettore di una query e L è la matrice terminidocumenti, il prodotto LTq fornisce una matrice delle similarità fra q e i documenti della collezione, secondo il modello vettoriale standard – Ma LTq è una trasformazione lineare, e, se i e vi sono autovalori e autovettori di LT=A, allora Aq 1 (v1 q) 2 (v 2 q) ...k (v k q) – Se posso trascurare alcuni autovalori, allora è come se proiettassi q in uno spazio a dimensioni ridotte: ma come? – Servono altre definizioni .. ( e ci resta da capire cosa c’entrano le matrici delle co-occorrenze LTL e LLT viste prima) Valori e vettori singolari • Data una matrice L nxm, la radice quadrata degli n autovalori di LTL si dicono valori singolari di L • Gli n autovettori di LTL si dicono vettori singolari destri • Gli m autovettori di LLT si dicono vettori singolari sinistri • E finalmente… Singular Value Decomposition!! Sia L una matrice nxm Data una matrice nxn, esistono 3 matrici U, e VT, tali che: L = UVT 1. U e V sono le matrici dei vettori singolari sinistro e destro di L (cioè gli autovettori o eigenvectors di LLT e LTL, rispettivamente) 2. Le colonne di U e le righe di V definiscono uno spazio ortonormale, cioè: U-1=VT 3. è la matrice diagonale dei valori singolari di L I valori singolari sono le radici degli autovalori di LLT o LTL (si dimostra che sono uguali). Poiché LLT è SIMMETRICA, i suoi autovalori = saranno reali decrescenti lungo . Riduzione del rango in LSI Gli elementi diagonali in sono positivi e decrescenti in grandezza. Si prendono i primi k e gli altri vengono posti a zero. Si cancellano le righe e le colonne zero di e le corrispondenti righe e colonne di U e V. Si ottiene: ^ L ≈ U’’VT’ Interpretazione Se il valore k è selezionato opportunamente, l’aspettativa è che la nuova matrice Lˆ mantenga l’informazione semantica di L, ma elimini il rumore derivante dalla sinonimia (perché sensi diversi avranno co-occorrenze diverse) e riconosca la dipendenza fra termini co-occorrenti. Riduzione del rango txd txk kxk ’ L = kxd V’T U’ k è il numero di valori singolari scelti per rappresentare i concetti nell’insieme dei documenti In genere, k « d. Ma insomma, cosa c’entrano le co-occorrenze???? • Abbiamo detto che U, e V sono matrici degli autovalori e autovettori di LTL e LLT (nonchè valori e vettori singolari di L). • Ma come calcoliamo, ad es. gli autovalori di LTL? Ricordate come è fatta la matrice LTL w11 w12 w13 w12 w22 w23 w13 w23 w33 Per trovare gli autovalori, devo calcolare il determinante di: w11- w12 w13 w12 w22 - w23 w13 w23 w33 - L’equazione caratteristica di terzo grado è data, in questo esempio, da: (w11 )(w 22 )(w 33 ) 2w 23 w12 w12 (w 23 ) w 23 w13 w13 (w12 w 23 w 22 w13 ) Che come si vede, contiene prodotti di co-occorrenze: gli autovalori di grandezza maggiore (o vettori singolari di L) saranno determinati dai prodotti di co-occorrenze tutte non nulle Esempio w11 w12 w13 w12 w22 w23 w13 w23 w33 T LL 2 2 0 2 2 0 0 0 1 (ricordate?) Si vede chiaramente che esistono due dimensioni: quella di w1 e w2 (w12), e quella di w3 Calcolando autovalori e autovettori su: http://www.bluebit.gr/matrix-calculator/calculate.aspx si ottiene il polinomio caratteristico: 3 52 4 Con autovalori 4, 1 e 0. Matrice LLT Autovalori e autovettori reali La matrice L termini-documenti Autovettori di LLT o vettori singolari sinistri di L Radici degli autovalori di LLT o valori singolari di L Autovettori di LTL o vettori singolari destri SVD nel LSI: conclusioni • Nel modello vettoriale, queries e documenti sono vettori in uno spazio le cui dimensioni sono i termini, considerati fra loro ortonormali, cioè indipendenti fra loro • LSI trasferisce questi vettori in uno spazio le cui dimensioni sono concetti, cioè co-occorrenze fra termini • La riduzione di rango ha l’effetto di eliminare i concetti poco rilevanti Riassunto del Procedimento • L=UVT dove L nxm 1. Calcola la trasposta LT di L 2. Determina gli autovalori di LT L e ordinali in ordine decrescente. Calcola le radici quadrate. 3. Costruisci la matrice 4. Calcola gli autovettori di LT L. Questi sono le colonne di V. Genera VT 5. Calcola U=AV-1 Esempio per una matrice termini documenti query L 1. Calcolo T UV 2. Approssimazione di rango 2 3a. Calcolo similarità querydocumento • Per N documenti, V contiene N righe, ognuna delle quali rappresenta le coordinate del documento di proiettato nella dimensione LSI • Una query viene trattata come un documento e anch’essa proiettata nello spazio LSI 3b. • • • • • T L=USV Se L=UVT si ha anche che V = LTU-1 d = dTU-1 q = qTU-1 Dopo la riduzione di rango k: – d = dTUkk-1 – q = qTUkk-1 – sim(q, d) = sim(qTUkk-1, dTUkk-1) 3c. Calcolo del query vector q = qTUkk-1 Vettori della query e dei documenti nello spazio LSI Similarità query-documento