Motori di Ricerca
presente e futuro prossimo
Rilevanza dei Risultati:
Prima generazione
Paolo Ferragina, Università di Pisa
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.
 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 !!
Paolo Ferragina, Università di Pisa
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,...
Tipo

Dimensione e tipo di carattere

Maiuscolo o minuscolo
Informazioni sulla “frequenza”
Paolo Ferragina, Università di Pisa
Assegnamo il “peso”
a ogni termine e
sommiamo i contributi
per ogni pagina
Frequenza “binaria” o “completa”
docs
D1
D2
D3
D4
D5
D6
D7
D8
D9
D10
D11
t1
1
1
0
1
1
1
0
0
0
0
1
t2
0
0
1
0
1
1
1
1
0
1
0
t3
1
0
1
0
1
0
0
0
1
1
1
docs
D1
D2
D3
D4
D5
D6
D7
D8
D9
D10
D11
t1
2
1
0
3
1
3
0
0
0
0
4
t2
0
0
4
0
6
5
8
10
0
3
0
t3
3
0
7
0
3
0
0
0
1
5
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
Paolo Ferragina, Università di Pisa
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
Paolo Ferragina, Università di Pisa
Un “peso” famoso: tf x idf
wij  tf ij  log( n / ni )
tf ij  Frequenza del termine i nel documento j


n


idf i log 
 ni 
dove ni = #documenti che contengono il termine i
n = #documenti della collezione
Termine ti ha associato un vettore D-dim: [ wi1, wi2, ..., wiD]
Documento Dj ha associato un vettore T-dim: [ w1j, w2j, ..., wTj]
Paolo Ferragina, Università di Pisa
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.
Paolo Ferragina, Università di Pisa
Documenti come vettori
D1  (0.8, 0.3)
D2  (0.2, 0.7)
1.0
D2
0.8
0.6
0.4
D1
0.2
0.2
Paolo Ferragina, Università di Pisa
0.4
0.6
0.8
1.0
Similarità tra Doc e Interrogazione
D1  (0.8, 0.3)
D2  (0.2, 0.7)
Q  (0.4, 0.8)
cos 1  0.74
1.0
D2
0.8
0.6
0.4
0.2
Q
cos  2  0.98
2
1
0.2
Paolo Ferragina, Università di Pisa
D1
0.4
0.6
0.8
1.0
Documenti come vettori
t3
D1
D9
D5
D3
D2
D7
t2
Paolo Ferragina, Università di Pisa
D6
t1
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
Paolo Ferragina, Università di Pisa
Un altro peso: Anchor text
Indicizziamo i virtual doc costruiti
concatenando gli anchor text dei link
che puntano a una determinata pagina
Immagine di una tigre
Qui trovate una bella
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 !
Paolo Ferragina, Università di Pisa
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
Paolo Ferragina, Università di Pisa
Motori di Ricerca
presente e futuro prossimo
Rilevanza dei Risultati:
Seconda generazione
Paolo Ferragina, Università di Pisa
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
Paolo Ferragina, Università di Pisa
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)
Paolo Ferragina, Università di Pisa
PageRank
(Google)
 Pagina rilevante se:

Molte pagine puntanto a essa
(popolare)

Alcune pagine “rilevanti” puntano a essa
(élite)
p1
p2
pn
u1
p
I(p) = (1-q)
I(p1) + I(p2) + ... + I(pn)
u1
u2
un
+q
 Calcolato su tutte le pagine e in modo iterativo (~100)
Paolo Ferragina, Università di Pisa
Attenti ai Blog !
Un esempio: passo iniziale
q = 0.15
Page A
1
1*0.85/2
1*0.85/2
Page B
1
1*0.85
1*0.85
Page C
1
Paolo Ferragina, Università di Pisa
1*0.85
Page D
1
Esempio: dopo 20 iterazioni
q = 0.15
Page A
1.490
Page B
0.783
Page C
1.577
Page D
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à
Paolo Ferragina, Università di Pisa
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
Paolo Ferragina, Università di Pisa
HITS: Primo passo per risolvere Q
Root set
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
Paolo Ferragina, Università di Pisa
HITS: Secondo passo per risolvere Q
 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
z1
x
z2
z3
 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 !!
Paolo Ferragina, Università di Pisa
y1
y2
y3
Un esempio
Autorità
Hub
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Paolo Ferragina, Università di Pisa
Motori di Ricerca
presente e futuro prossimo
Rilevanza dei Risultati:
Terza generazione
Paolo Ferragina, Università di Pisa
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 !!!
Paolo Ferragina, Università di Pisa
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:

Storia della presente navigazione

Ricerche già formulate dallo stesso utente
[User behavior]

[Personalization]
Professione dell’utente e informazione demografica

Interessi dell’utente
Profilo:
 Esistono dei problemi di privacy !!!
Paolo Ferragina, Università di Pisa
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 !!

Offriamo possibilmente dei suggerimenti, anche semantici
Questo è un motore di ricerca moderno !!
(siamo alla terza generazione)
Paolo Ferragina, Università di Pisa
Motore di Ricerca: struttura
Archivio Pagine
risposte
Crawler
Query
Analizzatore
pagine
Indicizzatore
Risolutore
Controllo
Testo
Utilità
Struttura
Paolo Ferragina, Università di Pisa
Analizzatore
Rilevanza
Motori di Ricerca
presente e futuro prossimo
Valutazione dei Risultati
Paolo Ferragina, Università di Pisa
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
Paolo Ferragina, Università di Pisa
Scenario generale
Tutti docs
Recuperati
Rilevanti
Paolo Ferragina, Università di Pisa
Approccio classico: Precisione vs. Completezza
 Precisione: % documenti recuperati che sono rilevanti

Quanta “spazzatura” abbiamo recuperato
Tutti docs
Recuperati
Rilevanti
Paolo Ferragina, Università di Pisa
Approccio classico: Precisione vs. Completezza
 Completezza: % docs rilevanti che sono recuperati

Quanta “informazione” abbiamo recuperato
Tutti docs
Recuperati
Rilevanti
Paolo Ferragina, Università di Pisa
Precisione vs. Completezza
| RilRecuperati |
Precisione
Completezza 
|RilRecuperati |
|Ril in Collezione|
| Recuperati |
Tutti docs
Recuperati
Rilevanti
Paolo Ferragina, Università di Pisa
Precisione vs. Completezza
| RilRecuperati |
Completezza 
Precisione
|RilRecuperati |
|Ril in Collezione|
| Recuperati |
recuperati
Rilevanti
Paolo Ferragina, Università di Pisa
Altissima precisione, bassissima completezza
Precisione vs. Completezza
| RilRecuperati |
Precisione
Completezza 
|RilRecuperati |
|Ril in Collezione|
| Recuperati |
recuperati
Rilevanti
Paolo Ferragina, Università di Pisa
Bassissima precisione, bassissima completezza
Precisione vs. Completezza
| RilRecuperati |
Completezza 
Precisione
|RilRecuperati |
|Ril in Collezione|
| Recuperati |
Rilevanti
Recuperati
Paolo Ferragina, Università di Pisa
Alta completezza, bassissima precisione
Precisione vs. Completezza
| RilRecuperati |
Completezza 
Precisione
|RilRecuperati |
|Ril in Collezione|
| Recuperati |
Rilevanti
Recuperati
Paolo Ferragina, Università di Pisa
Alta completezza e precisione
Trade-off
 Si misura la Precisione a diversi livelli di Completezza
 Nota: è una MEDIA su numerose interrogazioni
precisione
x
x
x
x
completezza
Paolo Ferragina, Università di Pisa
Difficoltà per il web
precisione
x
x
x
x
completezza
 Sul Web non conosciamo la “completezza”, quindi guardiamo
soltanto ai primi 10100 risultati. Su questi si gioca la “partita” !!
Paolo Ferragina, Università di Pisa
Ognuno sceglie il suo Ranking !
Paolo Ferragina, Università di Pisa
http://www.langreiter.com/exec/yahoo-vs-google.html?q=...
Motori di Ricerca
presente e futuro prossimo
Il quadro presente
Paolo Ferragina, Università di Pisa
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.
Paolo Ferragina, Università di Pisa
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!)
Paolo Ferragina, Università di Pisa
Il motore più famoso ...
Paolo Ferragina, Università di Pisa
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%
Paolo Ferragina, Università di Pisa
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:

Business: tra i pochissimi a fare molti profitti !

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)

Paolo Ferragina, Università di Pisa
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.
Paolo Ferragina, Università di Pisa
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