Basi Documentali
in Ambienti di Hyperlinks
Oltre la navigazione ...
http://www.dii.unisi.it/~marco/bdm
2004/2005
Marco Gori
1
Il Web
Pubblicazione distribuita
Informazione senza struttura
Qualità non garantita, problemi di
“spamming”.
Il Web ha importanti aspetti commerciali.
2004/2005
Marco Gori
2
Il Web
Alcune pagine hanno poco testo e molte
immagini
Varietà di languaggi, milioni di termini
per il dizionario
10-15 KB a pagina, oltre 10 miliardi di
pagine, 10 links per pagina ...
Crescita giornaliera (milioni pag./giorno).
2004/2005
Marco Gori
3
Analisi dei Links
Due approcci
Ordinamento universale, query-independent
di tutte le pagine web pages
anche indipendente dal contenuto delle pagine
Ordinamento query-specific
2004/2005
Marco Gori
4
Ordinamento
Indipendente dalle queries
Prima generazione: conta i links come misura di
popolarità. Due suggerimenti:
Popolarità indiretta:
Ogni pagina riceve uno score = numero in-links
più numero out-links (3+2=5).
Popularità diretta:
Score pagina = numero di in-links (3).
2004/2005
Marco Gori
5
Query processing
Schema di risposta alle queries:
1. Trova tutte le pagine che soddisfano la
query (esempio “spoon river”).
2. Ordina i documenti sulla base della
loro popolarità
2004/2005
Marco Gori
6
Spamming
Come aumentare la visibilità?
score = numero in-links + numero out-links.
Score = numero in-links.
2004/2005
Marco Gori
7
Pagerank
Immagina un random walk sulle pagine
web:
- Parti da una pagina random
- Ad ogni step, esci dalla pagina seguendo gli
hyperlinks in modo equiprobabile
- Se si stabilisce uno stato stazionario, usa la
frequenza di visita come page score.
2004/2005
Marco Gori
8
Attenzione ai Pozzi!
Il Web è pieno di “pozzi”.
Con la random walk uno si può fermare in
simili nodi.
In tal caso il modello perde senso ...
??
2004/2005
Marco Gori
9
La Connessione Diretta
Ad ogni passo, con probabilità “1-d”, salta
ad una pagina.
Con la rimanente probabilità “d”, segui un
link casuale.
Si elimina il problema dello stop
2004/2005
Marco Gori
10
Catene di Markov
Catena di Markov: n stati, matrice nn
transizione di probabilità P.
Ad ogni step, siamo in uno degli stati.
Per 1  i,j  n, Pij è la probabilità che j
sia il prossimo stato, dato che lo stato
corrente è i.
i
2004/2005
Pij
Marco Gori
j
11
Catene di Markov
n

j 1
Pij  1.
Esercizio: Scrivi le equazioni del random
walk per questo caso:
2004/2005
Marco Gori
12
Catene Ergodiche
Catene ergodiche:
Se c’è un cammino da ogni stato a ogni altro
allora con il random walk uno po’ essere in
ogni stato con probabilità non-zero.
2004/2005
Marco Gori
13
Catene Markov Ergodiche
Per ogni catana di Markov ergodica, c’è un
unico long-term visit rate per ogni stato.
Distribzione stazionaria degli stati.
Su un lungo periodo, noi visitiamo ogni
stato in proporzione a questa frequenza.
Non importa da dove si parte!
2004/2005
Marco Gori
14
Vettori Probabilità
x = (x1, … xn) ci dice dove il “random
walk” si trova.
(010…0) significa siamo nello stato 2.
Più in generale, x = (x1, … xn) significa che la
passeggiata porta ad i con probabilità xi.
n
x
i 1
2004/2005
i
 1.
Marco Gori
15
Trans. delle Probabilità
x = (x1, … xn) è la probabilità ad un certo
stato, che succede al prossimo step?
Dallo stato x, il nostro prossimo stato è
xP.
2004/2005
Marco Gori
16
Calcolo del Rate di Visita
Stato stazionario: a = (a1, … an):
ai probabilità che siamo in i.
3/4
1/4
1
2
3/4
1/4
Per questo esempio, a1=1/4 e a2=3/4.
2004/2005
Marco Gori
17
In Generale?
a = (a1, … an) è il vettore stato stazion.
Condizione di stazionarietà:
a=aP
Dunque
si trovano gli autovettori di
2004/2005
Marco Gori
P
18
Altro Metodo
E’ in effetti un modo per determinare
l’autovettore.
Parti da una qualunque distribuzione (e.g.
x=(10…0)).
Primo step: xP;
Secondo, terzo, ... step: xP2 , xP3, ...
Stazionarità significa per grossi k, xPk = a.
Algoritmo: multiplica x per potenze incrementali
d P finchè il prodotto è stabile.
2004/2005
Marco Gori
19
Google e Pagerank
Pagerank è usato in Google!
Usa però un dumping paramter “d” …
(d=0.85 … perchè non d=1?)
Dettagli su questo meccanismo di scoring
“Inside PageRank”, Bianchini-GoriScarselli, ACM-TOIT (to appear)
2004/2005
Marco Gori
20
Analisi Query-dependent
Per ogni query, invece di una lista ordinata
di pagine che soddisfano la query, trova
due insiemi di pagine:
Pagine Hub: buona lista di links su un
argomento.
e.g., “la lista dei links su Linux”
Pagine Authority: pagine che vengono fuori
con alta frequenza.
2004/2005
Marco Gori
21
Hubs e Authorities
Buona hub per un certo argomento punta
a molte pagine con alta autorità su
quell’argomento.
Un buona authority per un certo
argomento è puntata da molte buone
hubs per quell’argomento.
Def. circolare - schema di calcolo iterativo.
2004/2005
Marco Gori
22
Schema di Elaborazione
Estrai l’ insieme base delle pagine che
potrebbero essere buone hubs o
authorities.
Identifica un piccolo insieme di pagine
hub e authority di alto livello
usa schema iterativo
2004/2005
Marco Gori
23
Insieme Base
Data una query usa un indice per
determinare le pagine che la soddisfano
(insieme radice)
Aggiungi ogni pagina t.c.
Punta ad una pagina dell’insieme radice
E’ puntata da una pagina nell’insieme radice.
Chiama questo insieme base.
2004/2005
Marco Gori
24
L’Insieme Base
Insieme
radice
Insieme Base
2004/2005
Marco Gori
25
Assembl. Insieme Base
Insieme radice: 200-1000 nodi.
Insieme base: circa 5000 nodi.
Come si trova l’insieme base?
Segui gli out-links dall’insieme radice.
Prendi in-links (e out-links) da un connectivity
server.
2004/2005
Marco Gori
26
Calcolo Hub e Authorities
Per ogni x nell’insieme base calcola hub
score h(x) e authority score a(x).
Initializza: Per ogni x, h(x)1; a(x) 1;
Key
Aggiorna iterativamente h(x), a(x);
Dopo ogni iterazione, output delle pagine
con la più alta h() e la più alta a().
2004/2005
Marco Gori
27
Scheme Iterativo
Ripeti per tutti gli x:
h( x ) 
 a( y )
x
x y
a ( x) 
 h( y )
x
y x
2004/2005
Marco Gori
28
Scaling
Per prevenire valori troppo alti di h() e a()
si scalano i termini dopo ogni iterazione.
Non importa il fattore di scaling:
Ci interessano solo i valori relativi.
2004/2005
Marco Gori
29
Quante iterazioni?
In pratica: Convergenza dopo poche
iterazioni:
dimostrazione (dopo)
~5 iterazioni si va vicino alla stabilità.
2004/2005
Marco Gori
30
Note
Metti assieme pagine independentemente
dal linguaggio e dal contenuto, ma conta
la query.
Usa solo l’analisi dei links dopo aver
assemblato l’insieme base
retrieval - overhead significativo.
2004/2005
Marco Gori
31
Convergenza: Dim.
nn matrice adiacenza A:
Aij = 1 se i connette a j, altrimenti =0.
1
2
3
2004/2005
Marco Gori
1
1
0
2
1
3
0
2
1
1
1
3
1
0
0
32
Vettori Hub/Authority
Aggiornamento iterativo
h( x ) 
 a( y )
x y
a ( x) 
 h( y )
y x
2004/2005
Marco Gori
33
In Forma Matriciale
h=Aa.
a=Ath.
At è la
trasposta
di A.
Sostituendo, h=AAth e
a=AtAa.
Convergenza: h è autovettore di AAt
e a è autovettore di AtA.
2004/2005
Marco Gori
34
Tag/position heuristics
Increm. i pesi dei termini nei titoli
Increm. i pesi dei termini vicino l’inizio del
doc, dei suoi capitoli e paragrafi ...
2004/2005
Marco Gori
35
Anchor text
immagine tigre
Qui c’è una splendida
immagine di una tigre
Cool tiger webpage
2004/2005
Testo vicino hyperlink: è
descrittivo
Gori
della pagina Marco
che
punta.
36
Anchor Text: Due Usi
1. Quando si indicizza una pagina, si
indicizza anche l’anchor text dei links che
la puntano.
2. Per pesare links nell’algoritmo
hubs/authorities.
Anchor text: preso tipicamente da finestra
con 6-8 parole intorno un link anchor.
2004/2005
Marco Gori
37
Anchor text: Indicizzaz.
Quando si indicizza D, si include l’anchor
Armonk, NY-based computer
giant IBM announced today
www.ibm.com
Joe’s computer hardware links
Compaq
HP
IBM
2004/2005
Big Blue today announced
record profits for the quarter
Marco Gori
38
Riferimenti per la lezione
The Anatomy of a Large-Scale Hypertextual Web Search
Engine
http://citeseer.nj.nec.com/brin98anatomy.html
Authoritative Sources in a Hyperlinked Environment
http://citeseer.nj.nec.com/kleinberg97authoritative.html
2004/2005
Marco Gori
39