Paolo Ferragina, Università di Pisa Motori di Ricerca presente e futuro prossimo Rilevanza dei...

Paolo Ferragina, Università di Pisa

Motori di Ricercapresente e futuro prossimo

Rilevanza dei Risultati:Prima generazione


Concetto di rilevanza difficile da “catturare”: Dipende dall’utente che formula la interrogazione Dipende dall’istante di formulazione della interrogazione Contenuto pagine eterogeneo: lingua, tipo (pdf, doc, jpg,..)

Il motore deve “inferire user need” da vari elementi !!

Problemi sul Web nel catturare “pagine rilevanti”

Crescita del Web: 110,000 pagine del 1994 ... 8mld pagine del 2005

Crescita proporzionale del numero delle risposte !!

Utenti guardano a poche risposte: 85% guardano solo ai primi 10 risultati.


Rilevanza derivata dal contenuto

Per ogni occorrenza di una parola si memorizzano: Luogo

URL: www.pisa.comune.it Titolo pagina Testo hyperlink: “Città di Pisa” Metatag: autore, data,...

Assegnamo il “peso”a ogni termine e

sommiamo i contributiper ogni pagina

Tipo Dimensione e tipo di carattere

Maiuscolo o minuscolo

Informazioni sulla “frequenza”


Frequenza “binaria” o “completa”

docs t1 t2 t3D1 1 0 1D2 1 0 0D3 0 1 1D4 1 0 0D5 1 1 1D6 1 1 0D7 0 1 0D8 0 1 0D9 0 0 1D10 0 1 1D11 1 0 1

docs t1 t2 t3D1 2 0 3D2 1 0 0D3 0 4 7D4 3 0 0D5 1 6 3D6 3 5 0D7 0 8 0D8 0 10 0D9 0 0 1D10 0 3 5D11 4 0 1

Ma le Leggi di Zipf e di Luhn ci suggeriscono che dobbiamo pesare molto i termini che sono frequenti in documenti rilevanti ma rari nella intera collezione


Infatti

La frequenza nel singolo documento non aiuta… 10 occorrenze di culla 10 occorrenze di e

Per ogni coppia <termine,documento> assegnamo un peso

che riflette l’importanza del termine in quel documento

Il peso cresce con il “numero di occorrenze” del termine entro quel documento

Il peso cresce con la “rarità” del termine fra tutti i

documenti della collezione


Un “peso” famoso: tf x idf

)/log( iijij nntfw

dove ni = #documenti che contengono il termine i n = #documenti della collezione

log

Frequenza del termine i nel documento j

nnidf

tf

i

i

ij

Termine ti ha associato un vettore D-dim: [ wi1, wi2, ..., wiD]

Documento Dj ha associato un vettore T-dim: [ w1j, w2j, ..., wTj]


Come usiamo questi pesi ?

Data una interrogazione sui termini th e tk potremmo:

Sommare whj e wkj per ogni documento dj che li contiene, o

utilizzare un’altra funzione dei due valori

Pesare l’importanza di th e tk all’interno della query e quindi

calcolare una combinazione lineare di whj e wkj.

Interpretare ogni documento e la query come vettori, e

postulare la similarità tra doc-query in base alla loro

vicinanza euclidea o tramite altra misura correlata.


Documenti come vettori

1D

2D)7.0 ,2.0(

)3.0 ,8.0(

2

1

D

D

1.0

0.8

0.6

0.8

0.4

0.60.4 1.00.2

0.2


Similarità tra Doc e Interrogazione

2

1 1D

Q2D

98.0cos

74.0cos

)8.0 ,4.0(

)7.0 ,2.0(

)3.0 ,8.0(

2

1

2

1

Q

D

D

1.0

0.8

0.6

0.8

0.4

0.60.4 1.00.2

0.2


Documenti come vettori

t1

t2

t3

D1

D2

D3

D9

D7

D5

D6


Alcune osservazioni…. Non c’è una reale base teorica per il modello vettoriale

I termini non sono relamente indipendenti

Siccome Q consiste di pochi termini ti, non la

confrontiamo con tutti i docs, ma piuttosto: Lista invertita per prendere docs Dj che li contengono

Estraiamo da ogni Dj il peso wij , relativo ai ti che contiene

Combiniamo “in qualche modo” i contributi, per conoscere la

“similarità” tra Q e Dj indotta dalle frequenze locali e globali


Un altro peso: Anchor text

Qui trovate una bella immagine di una tigre

Immagine di una tigre

Ganza pagina con immagini sulle tigri

NOTA: Il testo nella vicinanza di un hyperlink è molto descrittivo del

contenuto della pagina a cui esso fa riferimento !

Indicizziamo i virtual doc costruiticoncatenando gli anchor text dei link

che puntano a una determinata pagina


Ricapitolando

Per ogni occorrenza di una parola si memorizzano: Luogo

Tipo

TF x Idf

I motori di prima generazione usavano questi pesi per

inferire la similarità dei documenti con la query

Poi ordinavano le risposte (docs) in accordo a questa



Rilevanza dei Risultati:Seconda generazione


Sfruttare gli hyperlink

Problema:

Molte pagine contengono le parole in Q ma sono “non rilevanti” oppure

includono parole “diverse” dal loro contenuto (spamming).

Altre pagine sono sì rilevanti ma non contengono le parole di Q oppure

non contengono testo, ma solo p.e. immagini o form.

Hyperlink Citazione

Web


Analisi degli hyperlink Due approcci fondamentali

Indipendente dalla interrogazione

Se due pagine contengono le parole di Q, una sarà

sempre migliore dell’altra indipendentemente da Q

(Pagerank di Google)

Dipendente dalla interrogazione

Se due pagine contengono le parole di Q, una sarà migliore dell’altra a seconda del contenuto di Q

(HITS di IBM e Teoma)


PageRank (Google)

Pagina rilevante se:

Molte pagine puntanto a essa (popolare) Alcune pagine “rilevanti” puntano a essa (élite)

I(p) = (1-q) + q

Calcolato su tutte le pagine e in modo iterativo (~100)

I(p1) + I(p2) + ... + I(pn) u1 u2 un

pp1

p2

pn

u1

Attenti ai Blog !


Un esempio: passo iniziale

Page A 1

Page C1

Page B1

Page D1

1*0.85/2

1*0.85/21*0.85

1*0.85

1*0.85

q = 0.15


Esempio: dopo 20 iterazioni

Page A 1.490

Page C1.577

Page B0.783

Page D0.15

q = 0.15

Sarebbe necessario, in verità, cambiare +q in +(q/#pagine) questo garantisce che il vettore dei pesi uscenti ha somma 1,

e quindi (Teorema) il PageRank è una distribuzione di probabilità


HITS (IBM)

A seguito di una interrogazione si cercano due insiemi “correlati” di pagine:

Pagine Hub = pagine che contengono una buona lista di link sul soggetto della interrogazione.

Pagine Authority = pagine che occorrono ripetutamente nelle liste contenute dei buoni Hubs.

Si tratta di una definizione circolare che quindi richiede una computazione iterativa


HITS: Primo passo per risolvere Q

base set

Data una interrogazione Q={ browser }, si forma il base set:

1. Le pagine che contengono browser (root set)

2. Le pagine collegate da o per quelle del root set

Root set


Calcoliamo, per ogni pagina x del base set:

un hub score h(x), inizializzato a 1 un authority score a(x), inizializzato a 1

Per poche iterazioni, ricalcoliamo di ogni nodo x:

a(x) = h(zi) , h(x) = a(yi)

Scaliamo i valori, e iteriamo

Alla fine, restituiamo le pagine con più alto valore di h() come hubs, e di a() come authorities

Costoso: Accumulo del base set e calcolo iterativo !!

Controindicazioni: Facilmente soggetto a SPAM !!

HITS: Secondo passo per risolvere Q

x

y1

y2

y3

z1

z2

z3


Un esempio

AutoritàHub

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15



Rilevanza dei Risultati:Terza generazione


Nuovi obiettivi

Obiettivo: Integrare dati provenienti dalle sorgenti più

disparate – quali, preferenze, click, affinità tra utenti, transazioni–

al fine di soddisfare meglio l’interrogazione posta da un utente

Esempio: Su una interrogazione come “San Francisco” il sistema dovrebbe trovare anche gli hotel o i musei, siti per le previsioni del tempo o mappe stradali, intuendo anche quali di questi è più rilevante per l’utente

Tools: Ciò richiede analisi semantica, determinazione del contesto, selezione dinamica di archivi utili, confronto tra sessioni …

Nuove nozioni di Rilevanza !!!


Rilevanza per “affinità”

Precedenti transazioni: [Collaborative Filtering]

Quali documenti/pagine sono state visitate, anche da altri utenti Quali prodotti sono stati acquistati, anche da altri utenti Pagine nei bookmarks dell’utente

Contesto corrente: [User behavior]

Storia della presente navigazione Ricerche già formulate dallo stesso utente

Profilo: [Personalization] Professione dell’utente e informazione demografica Interessi dell’utente

Esistono dei problemi di privacy !!!


Ricapitolando...

Data una interrogazione Q su più parole Troviamo le pagine dove occorrono quelle parole Per ogni pagina determiniamo:

Peso testuale: font, luogo, posizione, vicinanza,… Peso degli hyperlinks: grafo e anchor-text Peso dato da altri fattori: preferenze, comportamento,…

Sommiamo “in qualche modo” i pesi

Ordiniamo le pagine in funzione di essi Risultati !!

Questo è un motore di ricerca moderno !!(siamo alla terza generazione)

Offriamo possibilmente dei suggerimenti, anche semantici


Motore di Ricerca: struttura W

eb

Crawler

Archivio Pagine

Analizzatorepagine

Controllo

Query

RisolutoreAnalizzatoreRilevanza

TestoStruttura

Utilità

Indicizzatore

risposte



Valutazione dei Risultati


Quanto è “buono” un motore di ricerca?

Alcune misure di valutazione:

Costruzione:

Velocità nell’indicizzazione

Spazio occupato dall’indice

Copertura del Web

Modifica:

Frequenza e ampiezza delle modifiche

Interrogazione:

Velocità nel produrre le risposte

“Rilevanza” dei risultati: precisione e completezza


Scenario generale

Rilevanti

Recuperati

Tutti docs


Precisione: % documenti recuperati che sono rilevanti

Quanta “spazzatura” abbiamo recuperato

Approccio classico: Precisione vs. Completezza

Rilevanti

Recuperati

Tutti docs


Completezza: % docs rilevanti che sono recuperati

Quanta “informazione” abbiamo recuperato

Approccio classico: Precisione vs. Completezza

Rilevanti

Recuperati

Tutti docs



Rilevanti

Altissima precisione, bassissima completezza

recuperati

| Collezionein Ril|


|Recuperati|




Rilevanti

Bassissima precisione, bassissima completezza

recuperati

| Collezionein Ril|


|Recuperati|




Recuperati

Rilevanti

Alta completezza, bassissima precisione

| Collezionein Ril|


|Recuperati|




Recuperati

Rilevanti

Alta completezza e precisione

| Collezionein Ril|


|Recuperati|



Trade-off

Si misura la Precisione a diversi livelli di Completezza

Nota: è una MEDIA su numerose interrogazioni

precisione

completezza

x

x

x

x


Difficoltà per il web

precisione

completezza

x

x

x

x

Sul Web non conosciamo la “completezza”, quindi guardiamo

soltanto ai primi 10100 risultati. Su questi si gioca la “partita” !!


Ognuno sceglie il suo Ranking !

http://www.langreiter.com/exec/yahoo-vs-google.html?q=...



Il quadro presente


Fino a pochi anni fa...

Yahoo (migliore del 1995)

Inktomi (migliore del 1997)

Altavista (migliore del 1999)

Lycos, Excite, Northern Light,...

In Gennaio 2004, i preferiti sono Google (60 mil), Yahoo e MSN (45

mil ciascuno), AOL (23 mil), AskJeeves (13 mil). Ogni utente visita

più motori di ricerca per le sue query.


Alcune statistiche recenti...

In Gennaio 2004, 52% utenti indicano nella rilevanza dei risultati la

cosa più importante, 33% velocità. Interfaccia non importante.

Yahoo, AOL e EarthLink si appoggiano a Google e poi mixano i suoi

risultati con loro tecniche per mantenere una qualche autonomia

(Feb 04, Yahoo si divide da Google!)


Il motore più famoso ...


Cosa non è Google

Indice su tutti i documenti disponibili sul Web Nessun motore lo è

Credibile in ogni cosa che ci segnala Non esiste controllo sulla pubblicazione delle pagine

Perfettamente aggiornato Non riesce a seguire le modifiche giornaliere (milioni di pagine)

Protetto da contenuto offensivo Dispone di un meccanismo di filtering, ma non sicuro al 100%


Cosa è oggi Google Alcuni dati interessanti (NY Times, Aprile 2003):

Più di 1000 persone 54,000 server - 100,000 processor - 261,000 dischi

~4Mld pagine (1/04), 200 milioni query/giorno (30% del totale)

300 milioni di dollari di fatturato 2002 (750 nel 2003 ?)

“google” è la parola più utile del 2002 [American Dialect Society]

Un nuovo scenario di:

Gestione ed estrazione della conoscenza: non solo Web

Problemi matematici interessanti: Qualità risposte, Efficienza, Copertura del web Nuove applicazioni (news,prodotti), Nuovi domini (audio,video)

Business: tra i pochissimi a fare molti profitti !


Google: Il modello di business in 2 iniziative

Search services via la Google search appliance Soluzione hardware+software per un motore di ricerca in ambito

intranet o singolo website Hardware fissato e quindi limitati problemi di sviluppo e mantenimento

del software Per ora disponibile soltanto in USA e Canada (??)

Advertising programs (100.000 sottoscrittori) AdSense: Un sito può fornire spazio sulla sua pagina; le pubblicità da

visualizzare vengono scelte da AdSense in funzione dei contenuti della

pagina così da rivolgersi a probabili clienti. Il sito riceve un pagamento

in funzione del numero di click sul banner. AdWords: Una società può scegliere quanto pagare al giorno/mese e

indicare le parole chiave che descrivono il suo business. Un banner

viene visualizzato da Google all’atto di ricerche per quelle parole

chiave, e la società paga in funzione del numero di click ricevuti.


Google: altre notizie... Il nome deriva dalla parola GOOGOL, coniata da un bambino

americano di 9 anni per riferirsi al numero 10100

Un po’ di storia:

[1996-97] Esce il primo prototipo (BackRub).

[1998-99] Nasce Google, risponde a 10,000 Qpg 3Ml Qpg

[2000] 1Mld pagine e 60Ml Qpg

[2001] 2Mld pagine e 100Ml Qpg, ricerche limitabili a 26 linguaggi.

Introduce Image e File type search, Usenet dal 1981, Google Catalog.

[2002] 2,5Mld pagine, ricerche limitabili a 40 linguaggi. Intoduce AdWords, Google news, Web API, Froogle, Google Labs.

[2003] 3Mld di pagine, più linguaggi supportati. Il programma di business raggiunge i 100,000 sottoscrittori e viene promosso in Italia. Introduce Google AdSense, Local Search.

Paolo Ferragina, Università di Pisa Motori di Ricerca presente e futuro prossimo Rilevanza dei...

Documents

Transcript of Paolo Ferragina, Università di Pisa Motori di Ricerca presente e futuro prossimo Rilevanza dei...