Post on 01-May-2015
2004/2005 Marco Gori 1
Basi Documentaliin Ambienti di Hyperlinks
http://www.dii.unisi.it/~marco/bdm
Oltre la navigazione ...
2004/2005 Marco Gori 2
Il Web
Pubblicazione distribuita Informazione senza struttura Qualità non garantita, problemi di
“spamming”. Il Web ha importanti aspetti
commerciali.
2004/2005 Marco Gori 3
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 4
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 5
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 6
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 7
Spamming
Come aumentare la visibilità? score = numero in-links + numero out-
links. Score = numero in-links.
2004/2005 Marco Gori 8
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 9
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 10
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 11
Catene di Markov
Catena di Markov: n stati, matrice nn 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 jPij
2004/2005 Marco Gori 12
.11
=∑=
ij
n
j
P
Catene di Markov
Esercizio: Scrivi le equazioni del random walk per questo caso:
2004/2005 Marco Gori 13
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 14
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 15
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.
.11
=∑=
n
iix
2004/2005 Marco Gori 16
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 17
Calcolo del Rate di Visita
Stato stazionario: a = (a1, … an): ai probabilità che siamo in i.
1 23/4
1/4
3/41/4
Per questo esempio, a1=1/4 e a2=3/4.
2004/2005 Marco Gori 18
In Generale?
a = (a1, … an) è il vettore stato stazion.
Condizione di stazionarietà: a=aP Dunque
si trovano gli autovettori di P
2004/2005 Marco Gori 19
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 20
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-Gori-Scarselli, ACM-TOIT (to appear)
2004/2005 Marco Gori 21
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 22
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 23
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 24
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 25
L’Insieme Base
Insiemeradice
Insieme Base
2004/2005 Marco Gori 26
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 27
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;
Aggiorna iterativamente h(x), a(x); Dopo ogni iterazione, output delle
pagine con la più alta h() e la più alta a().
Key
2004/2005 Marco Gori 28
Scheme Iterativo
Ripeti per tutti gli x:
∑←yx
yaxha
)()(
∑←xy
yhxaa
)()(
x
x
2004/2005 Marco Gori 29
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 30
Quante iterazioni?
In pratica: Convergenza dopo poche iterazioni: dimostrazione (dopo)
~5 iterazioni si va vicino alla stabilità.
2004/2005 Marco Gori 31
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 32
Convergenza: Dim.
nn matrice adiacenza A: Aij = 1 se i connette a j, altrimenti =0.
1 2
3
1 2 31
2
3
0 1 0
1 1 1
1 0 0
2004/2005 Marco Gori 33
Vettori Hub/Authority
Aggiornamento iterativo
∑←yx
yaxha
)()(
∑←xy
yhxaa
)()(
2004/2005 Marco Gori 34
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 35
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 36
Anchor text
Qui c’è una splendida immagine di una tigre
immagine tigre
Cool tiger webpage
Testo vicino hyperlink: è descrittivodella pagina che punta.
2004/2005 Marco Gori 37
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 38
Anchor text: Indicizzaz.
Quando si indicizza D, si include l’anchor
www.ibm.com
Armonk, NY-based computergiant IBM announced today
Joe’s computer hardware linksCompaqHPIBM
Big Blue today announcedrecord profits for the quarter
2004/2005 Marco Gori 39
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