1

Querying

Modelli per la ricerca

2

Modelli di Retrieval

Un modello per il retrieval specifica rappresentazione dei documenti rappresentazione delle queries la funzione di retrieval

Due classi di modelli Boolean Modelli spazio query

3

Documento: insieme di keywords Queries: espressioni Boolean Ricerca: Ok se le keywords satisfano la query

Boolean

Si può aggiungere: diverse strategie stopword removal e

stemming mantere diverse informazioni ausiliarie

nell’indice e usare diversi metodi di implementazione

Modello Boolean

4

E’ il più popolare facile da comprendere sfrutta il vantaggio del calcolo proposizionale

Implemtazioni efficienti identif. documenti con una certa parola supporto di strut. ausiliarie, e.g., forward index per

la cancellazione I MB si possono estendere per includere ranking (non

facile)

MB: Aspetti Positivi

5

Molto rigido E’ difficile esprimere domande complesse documenti recuperati

tutti i documenti che soddisfano possono essere recup.

Non è facile fare ranking delle uscite tutti i documenti soddisfano la query nello

stesso modo E’ difficile implementare relevance feedback

E’ un difficile problema di inferenza induttiva

MB: Aspetti Negativi

6

Un EsempioValutazione di Blair & Maron [CACM, March

1985] 40,000 documenti legali. STAIRS (IBM 70’s) - usato da avvocati. Interazione con operatori per la

“migliore” formulazione della Boolean Interazione finchè il risultato è

soddisfacente Media: Precisione =20% Recall = 80%

7

Un documento è una lista di keywords La similiarità è basata sulla frequenza di

occorrenza Gli utenti specificano un insieme di termini

desiderati con pesi opzionali Weighted query terms : Q = database 0.5;

text 0.8; information 0.2 Unweighted query terms : Q = database;

text; information Non ci sono conditioni Boolean nella query

Si può supportare relevance feedback

Un po’ di Statistica ...

8

Come determinare le parole importanti in un documento?

Come determinare il grado di importanza della parola nel documento e nell’intera collezione?

Come stabilire il grado di similiarità? Se ho ambienti con hyperlinks … come

stabilire glli effetti dei links, della struttura e del formato(grassetto, lampeggiante ...)?

Problemi ...

9

Il Modello Vector-Space

Ci sono T termini distinti (index terms o vocabolario)

architecturebuscomputerdatabase….xmlcomputer science

biblotecavocabolario

Per ora: Solo termini singoli, non frasi

10

Modello Vector Space

I termini sono incorrelati (ortogonali) e formano il vector space

“computer” “science” “business”

CS biblioteca Tutto ciò che risulta importante

• Ma c’è in realtà correlazione tra i termini ...

11

Il Modello Vector-Space

Un esempio a due termini di = 0, 0 (Non contiene parole del

vocabolario) dj = 0, 0.7 (contiene una della due parole)

dk = 1, 2 (contiene entrambe le parole)

Così per 3 termini … ecc ... Un documento o una query si possono

rappresentare come combinazioni lineari di termini

12

Reppresentazione Grafica

Esempio:

D1 = 2T1 + 3T2 + 5T3

D2 = 3T1 + 7T2 + T3

Q = 0T1 + 0T2 + 2T3

T3

T1

T2

D1 = 2T1+ 3T2 + 5T3

D2 = 3T1 + 7T2 + T3

Q = 0T1 + 0T2 + 2T3

7

32

5

• E’ D1 o D2 più simile a Q?• Come si misura il grado di

similitudine?

13

Collezione dei Documenti

Collezione documenti: matrice

T1 T2 …. Tt

D1 d11 d12 … d1t

D2 d21 d22 … d2t

: : : : : : : :Dn dn1 dn2 … dnt

14

Misura di Similiarità

Misura Similiarità: grado di similiarità tra coppie di vettori N.B.: queries e documenti sono vettori!

Qual è la migliore funzione (se ne esiste una valida per tutte le stagioni!)

Si possono stabilire soglie per controllare la dimensione del retrieved set

Come usare info di relevance feedback?

15

Il Prodotto Scalare

sim ( Di , Q ) = dik qk)

dik è il peso del termine k nel documento i e qk è il peso del termine k nella query

Vettori binari: numero di matched query terms nel documento

k

t

=∑

1

16

Inner Product -- Examples

Binary: D = 1, 1, 1, 0, 1, 1, 0

Q = 1, 0 , 1, 0, 0, 1, 1

sim(D, Q) = 3

retrieval

database

architecture

computer

text

management

information

D1 = 2T1 + 3T2 + 5T3 D2 = 3T1 + 7T2 + T3

Q = 0T1 + 0T2 + 2T3

sim(D1 , Q) = 2*0 + 3*0 + 5*2 = 10

sim(D2 , Q) = 3*0 + 7*0 + 1*2 = 2

17

Proprietà prod. scalare

Favorisce documenti lunghi documenti lunghi cresce linearmente …

Interessante l’ortogonalità: un documento che parla della torta mantovana ha verosimilmente prod. Scalare nullo con uno che parla di basket!

18

Normalizzazione coseno

D1 = 2T1 + 3T2 + 5T3 CosSim(D1 , Q) = 5 / 38 = 0.81D2 = 3T1 + 7T2 + T3 CosSim(D2 , Q) = 1 / 59 = 0.13

Q = 0T1 + 0T2 + 2T3

t3

t1

t2

D1

D2

Q

1

D1 è 6 volte meglio di D2 con il coseno ma solo 5 volte meglio

con il prodotto scalare

∑ ∑

∑

= =

=

•

•

t

k

t

k

t

kkik

qd

qd

kik1 1

22

1

)(CosSim(Di, Q) =

19

Altre Similiarità .

D1 = 2T1 + 3T2 + 5T3 Sim(D1 , Q) = 10 / (38+4-10) = 10/32 = 0.31D2 = 3T1 + 7T2 + T3 Sim(D2 , Q) = 2 / (59+4-2) = 2/61 = 0.04

Q = 0T1 + 0T2 + 2T3

D1 è 9.5 volte meglio di D2

Qual è la differenza rispetto al cos?

∑ ∑∑

∑

= ==

=

•−+

•

t

k

t

kkik

t

k

t

kkik

qdqd

qd

kik1 11

22

1

)(

)(

Coeff. Jaccard :

20

Versioni Binarie

∑ ∑∑

∑

= ==

=

•−+

•

t

k

t

kkik

t

k

t

kkik

qdqd

qd

kik1 11

22

1

)(

)(

Prodotto Scalare:

Coseno:

Jaccard :qkdiqkdi

qkdi

∩−+

∩

∑ ∑

∑

= =

=

•

•

t

k

t

k

t

kkik

qd

qd

kik1 1

22

1

)(

qkdi

qkdi

×

∩

∑=

•t

kkik qd

1

)( qkdi ∩

di e qk qui sono insiemi di keywordsdi e qk qui sono vettori

21

Term Weightstfij = frequenza del termine j nel documento i

df j = document frequency del termine j

= no. documenti che contengono il term j

idfj = inverse document frequency del termine j

= log2 (N/ df j) (N: numero doc. collez.)

Inverse document frequency -- un indicatore di termini discriminatori: non servono termini che sono in “tutti” i documenti!

22

Term Weight

Tipico pesowij = tfij idfj = tfij log2 (N/ df j)

Alto peso: termini frequenti nel documento e rari nella collezione

Un altro peso:

wij = (tfij /maxl{tflj}) idfj = (tfij /maxl {tflj}) log2 (N/ df j)

maxl{tflj} è la term frequency del più frequente termine nel documento j

23

system

computer

database

science D2, 4

D5, 2

D1, 3

D7, 4

Index terms df

3

2

4

1

Dj, tfj

Opzionali: possono risiedere su file separato

posting

postings list

Implementazione

24

7, 4

5, 2

1, 3

2, 4

2489

14532

5

138

Parole e documenti: 16-bit o 32-bit

key content

• Come rappresentare tfmax?

• Come gestire la cancellazione di doc.?

• Perché non memorizzare direttamente idf?

Serve un “forward index”: Dato un documento, restituisce i terms che contiene e, forse, il suo più alto tf.

Implementazione

25

Ranking con op. Boolean

Si filtra prima con Boolean, poi si fa ranking nel vector-space

Combinazione Boolean e Vector-Space

Boolean filter

ranking

documenti

Vector-spacequery

resultati

Booleanquery

26

Complementi per la lezione

Indici inversi:I.H. Witten, A. Moffat, and T.C. Bell, “Managing Gigabytes,Compressing and Indexing Documents and Images,”Morgan kauffmann, 1999chapter 4