1

Querying - Parte II

Modelli per la ricerca

2

Rappresentazione e Vector Space (VS)

Ogni doc. j è un vettore di valori tfidf Si può normalizzare a lunghezza

unitaria. Si ottiene uno spazio vettoriale

i termini sono gli assi i documenti “vivono” nel VS anche se si fa “stemming”, si possono

avere emormi dimensioni! (soprattutto nel caso multilingua dei motori di ricerca)

3

Intuizione

Postulato: Documenti che sono “vicini” nel vector space sono “simili.”

t 1

D2

D1

D3

D4

t 3

t 2

x

y

4

Exercizio

Organizza opportunamente gli indici inversi per supportare la similiarità coseno

Discuti l’algoritmo per rispondere ad una generica query.

5

Perché Usare il VS?

Idea Base: Una query è vista come un “piccolo” documento.

Le queries diventano vettori nello stesso spazio dei documenti.

Possiamo misurare il coseno tra la query ed ogni documento … il rank alto corrisponde a coseno alto.

6

Ranking Coseno Efficiente

Il Ranking è il calcolo dei k doc. più “vicini” alla query k più alti coseni query-doc.

Ranking efficiente: Calcola un singolo coseno in modo

efficiente. Scegli i k più alti coseni in modo

efficiente.

7

Calcolo di singolo coseno

Per ogni term. i del doc j, momorizza tfij. Più in generale considerare idfi.

Accumola la somma per componenti omologhe ∑

=×=

m

i ikwijwDDsim

kj 1)( ,

8

I più Alti k Coseni

Tipicamente vogliamo i k doc con ranking più alto

non ordinare tutto! scopri “solo” i k più alti.

9

Candidati Term-wise Preprocessing: Pre-calcola, per ogni term, i

suoi k docs più vicini (ogni termine come 1-term query.). Risultato: “lista dei preferiti” per ogni

term. Ricerca:

Per ogni t-term query, prendi l’unione delle loro t “liste dei preferiti” - chiamala S.

Calcola i coseni tra la query e i soli docs in S, e prendi i top k.

10

Esercizio

Analizza in dettaglio i calcoli:

Proponi un semplice esempio in cui il metodo illustrato fornisce un valore errato di ranking rispetto al “coseno vero”.

11

Raggruppamento

Fase di pre-processing: prendi n docs casuali (leaders) Per ogni altro doc, pre-calcola il leader

più vicino Docs attaccati al leader: seguaci; Ragionevole: ogni leader ha ~ n seguaci.

Elaborazione query: Data Q, trova il più vicino leader L. Cerca k i più vicini docs fra i seguaci di L.

12

Visualizzazione

Query

Leader Seguace

13

Dimensionality reduction

Perché non “impaccare” i vettori in un numero minore di dimensioni (diciamo 10000100) preservando le distanze?

Questo incrementa la velocità del coseno! Due metodi: Random projection. “Latent semantic indexing”.

14

Latent semantic indexing

E’ una tecnica per riduzione dimensioni

Random projection è data-independent

LSI è data-dependent Elimina assi ridondanti Mette assieme assi “correlati”

elaboratore e calcolatore

15

Idea di Base di LSI

Pre-elabora doc. mediante la tecnica Singular Value Decomposition.

Qual è l’effetto? Si crea un nuovo vector space

Le queries sono gestite in questo nuovo vector space (molto più piccolo)

16

Decomp. Valori Singolari

Matrice della collezione: m n matrix of terms docs, A.

A has rank r m,n. matrice di correlazione term-term

T=AAt

T è quadrata, simmetrica m m. matrice di correlazione doc-doc D=AtA.

D è quadrata, simmetrica n n.

17

Autovettori

P, matrice m r di autovettori di T. R, matrice n r di autovettori di D. A può decomporsi come A = PQRt

Q è diagonale con autovalori di AAt

ordinati per valore decrescente.

18

Decomposizione

=

A P Q Rt

mn mr rr rn

19

Riduzione di dimensione

Per qualche s << r, azzero tutti gli s più grandi autovalori di Q. Denoto Qs la versione di Q ridotta. E’ normale che s sia qualche centinaia,

mentre r e dell’ordine decine di migliaia.

Dunque As = P Qs Rt

Risulta che As è una “buona” approssimazione di A.

20

Visualizzazione

=

As P Qs Rt

0

Le colonne di As representano i doc, ma in s<<m dimensioni.

00

21

Importanti Risultati

Le distanze relative tra doc sono (approssimativamente) preservate dalla proiezione: Di tutte le matrici m n rank s, As è la

migliore approssimazione di A.

22

Doc-doc similarities

As Ast è una matrice di

similiarità doc-doc: il termine (j,k) è una misura di similiarità dei documenti j e k.

23

Intuizione

Si fa più che semplice riduzione dimens.: I doc con molti termini in overlapping

vanno assieme I termini vengono raggruppati.

Dunque calcolatore ed elaboratore vengono raggruppati perche co-occorrono in doc con fax, stampante, mouse, etc.

24

Query processing

Una query è un piccolo doc: sia la riga 0 di As.

Le coordinate nella linea 0 di As Ast

restituiscono la similarità della query con ogni doc.

Coordinata (0,j) è lo score di doc j sulla query.

25

Esempio

Human interface computer user system response time EPS survey trees graph minors

26

Complementi per la lezione

Implementazione del ranking coseno: I.H. Witten, A. Moffat, and T.C. Bell, “M.G.,

4.6 (molti dettagli in più per chi vuole approfondire)

Latent semantic indexing: articolo di S. Deerwester et al (1990) http://citeseer.nj.nec.com/

deerwester90indexing.html

27

Letture correlate

Un articolo introduttivo che discute criticamente i concetti di base dell’information retrieval dal titolo

“What Do People Want from Information Retrieval?”

http://www.dlib.org/dlib/november95/11croft.html