Latent semantic indexing limiti della ricerca per parole chiave



Scaricare 445 b.
23.05.2018
Dimensione del file445 b.


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: n-dimensional, manifold and topology)

  • Se viene fatta una ricerca con n-dimensional, manifold vengono “automaticamente” recuperati documenti che contengono anche (e eventualmente solo!) topology













Esempio



Matrice termini-documenti



Co-occrrenze dei termini nei documenti





Matrici delle co-occorrenze

  • Se A è una matrice TxN (termini documenti)

  • Allora:

    • ATA è la matrice le cui righe ai rappresentano le co-occorrenze di termini fra di e dj, per ogni dj. Dato un documento, indica quali sono i documenti più simili.
    • AAT è la matrice le cui righe ai rappresentano le co-occorrenze nei documenti fra ti e tj per ogni tj. Dato un termine, indica quali sono i termini più correlati.
    • Usando, ad esempio, la matrice AAT potrei “espandere” ogni termine con quelli aventi il più alto valore di correlazione


Osservazione

  • Tutte le possibili co-occorrenze sarebbero assai di più dei termini singoli (detta A la matrice termini-documenti, dovrei calcolare X=AAT).

  • Il metodo della singular value decomposition utilizzato da LSI consente di eliminare le co-occorrenze non significative

  • Si parte dall’osservazione del fatto che la maggioranza delle celle della matrice X sono zero

  • La dimensionalità della matrice è elevata (TxT)

  • 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 solo strumenti matematici.



Latent Semantic Indexing: concetti



Eigenvalues and Eigenvectors

  • Un vettore v  Rn, v0, è un eigenvector di una matrice nn A con corrispondente eigenvalue , se:

    • Av = v
  • Nota:

    • A deve essere nxn
    • Il corrispondente eigenvalue è uno scalare
    • Se v is è un eigenvector con eigenvalue , allora lo è ogni scalare non nullo multiplo di v (v)


Esempio



Approfondimenti

  • http://www.sosmath.com/matrix/eigen0/eigen0.html

  • http://www.cs.ut.ee/~toomas_l/linalg/lin2/node14.html



Torniamo alla decomposizione SVD



Riduzione del rango



Riduzione del rango in LSI



Trasformazioni lineari



Riduzione della dimensionalità (o approssimazione di rango k di una matrice)



Riduzione della dimensionalità (o approssimazione di rango k di una matrice)



Moltiplicare per una matrice è una trasformazione lineare

  • 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. Tutti i vettori sull'asse verticale sono multipli scalari del vettore rosso, e sono tutti autovettori.



Riduzione della dimensionalità (o approssimazione di rango k di una matrice)



Significato

  • I valori singolari possono essere usati per capire quali dimensioni vengono maggiormente modificate dalla moltiplicazione di un vettore per una matrice.

  • Perciò possiamo determinare quali vettori singolari conservare, e quali scartare



SVD nel LSI

  • 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



Procedimento

  • A=USVT dove A nxm

  • Calcola la trasposta AT di A

  • Determina gli autovalori di AT A e ordinali in ordine decrescente. Calcola le radici quadrate, che sono gli autovalori di A

  • Costruisci la matrice S

  • Calcola gli autovettori di AT A. Questi sono le colonne di V. Genera VT

  • Calcola U=AVS-1



Esempio di calcolo della decomposizione SVD



Calcolo degli autovalori di ATA



Matrice S





V è la matrice degli autovettori destri



Matrice U



Prova: torno alla matrice di partenza



Esempio per una matrice termini documenti



Calcolo USVT



Approssimazione di rango 2



Calcolo similarità query-documento

  • 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



A=USVT

  • Se A=USVT si ha anche che

  • V = ATUS-1

  • d = dTUS-1

  • q = qTUS-1

  • Dopo la riduzione di rango k:

    • d = dTUkSk-1
    • q = qTUkSk-1
    • sim(q, d) = sim(qTUkSk-1, qTUkSk-1)


Calcolo del query vector



Vettori della query e dei documenti nello spazio LSI



Similarità query-docmento



Co-occorrenze: vengono “catturate” dal LSI







©astratto.info 2017
invia messaggio

    Pagina principale