Web Information Retrieval
Il World Wide Web
• Sviluppato da Tim Berners-Lee nel 1990 al CERN per
organizzare documenti di ricerca disponibili su
Internet.
• Combina l’idea di scaricare documenti via FTP con
l’idea di ipertesti per collegare fra loro i documenti
• Ha sviluppato il protocollo HTTP, il concetto di URLs,
ed il primo “web server.”
Problemi per WEB IR
• Dati distribuiti: I documenti sono sparsi su milioni di
server differenti
• Dati Volatili: Molti documenti appaiono e
spariscono (così detti dead links).
• Enormi volumi di dati: Miliardi di documenti diversi
• Dati non strutturati e ridondanti: Non esiste una
struttura uniforme, ci sono errori html, circa 30% di
documenti duplicati.
• Qualità dei dati: Non ci sono controlli editoriali, le
informazioni possono essere false, possono esserci
errori, testi mal scritti..
• Dati eterogenei: multimediali (immagini, video,
suoni..) diversi linguaggi, diversi formati (pdf, ps..)
Numero di Web Servers
Struttura a grafo del Web
Pagine con link
di ingresso e uscita
Pagine
con link
in uscita
Pagine
con link
in ingresso
http://www9.org/w9cdrom/160/160.html
Ricerca sul Web
Sponsored Links
CG Appliance Express
Discount Appliances (650) 756-3931
Same Day Certified Installation
www.cgappliance.com
San Francisco-Oakland-San Jose,
CA
Utente
Miele Vacuum Cleaners
Miele Vacuums- Complete Selection
Free Shipping!
www.vacuums.com
Miele Vacuum Cleaners
Miele-Free Air shipping!
All models. Helpful advice.
www.best-vacuum.com
Web
Results 1 - 10 of about 7,310,000 for miele. (0.12 seconds)
Miele, Inc -- Anything else is a compromise
Spider
At the heart of your home, Appliances by Miele. ... USA. to miele.com. Residential Appliances.
Vacuum Cleaners. Dishwashers. Cooking Appliances. Steam Oven. Coffee System ...
www.miele.com/ - 20k - Cached - Similar pages
Miele
Welcome to Miele, the home of the very best appliances and kitchens in the world.
www.miele.co.uk/ - 3k - Cached - Similar pages
Miele - Deutscher Hersteller von Einbaugeräten, Hausgeräten ... - [ Translate this
page ]
Das Portal zum Thema Essen & Geniessen online unter www.zu-tisch.de. Miele weltweit
...ein Leben lang. ... Wählen Sie die Miele Vertretung Ihres Landes.
www.miele.de/ - 10k - Cached - Similar pages
Herzlich willkommen bei Miele Österreich - [ Translate this page ]
Herzlich willkommen bei Miele Österreich Wenn Sie nicht automatisch
weitergeleitet werden, klicken Sie bitte hier! HAUSHALTSGERÄTE ...
www.miele.at/ - 3k - Cached - Similar pages
Search
Indicizzatore
Il Web
Indici
Ind. commerciali
Page Respository
Spiders
/Crawlers
WWW

Utenti
Query
Modulo
Indicizzazione
Controllo Spidering
Testo
Struttura
Ranked
results
Modulo
IR
Link
FASI
• Spidering/Crawling: esplorazione di una porzione del
web
• Indicizzazione: generazione di indici che associno i
documenti a dei puntatori, su tre basi:
– struttura del documento,
– contenuto,
– posizione del documento nel grafo del web.
• Ranking: sulla base della query e degli indici,
presentare gli indirizzi delle pagine ordinate per
rilevanza
Web Search
1. Spidering (o Crawling)
Spiders (Robots/Bots/Crawlers)
• Sono programmi che attraversano la rete
spedendo pagine nuove o aggiornate ad un
server principale,e dove queste vengono
indicizzate
• Uno Spider gira su macchine locali e spedisce
richieste a server remoti
• Gli indici sono usati in maniera centralizzata per
rispondere alle query degli utenti
Spiders (Robots/Bots/Crawlers)
• Si parte da un insieme pre-identificato di URL
“radice”.
• Si seguono tutti i link a partire dalle radici alla ricerca
di pagine addizionali.
• Alcuni sistemi consentono all’utente di sottomettere
pagine per l’indicizzazione (o stabilire i nodi radice).
Spidering
URLs “esplorate”
e analizzate
Web
pagine
iniziali
(seeds)
Frontiera URLs
Il Web “nascosto”
Questo semplice schema presenta
complicazioni
• Non si può effetuare il crawling con una sola macchina,
quindi tutte le fasi sono distribuite su threads
• Problemi:
– Latenza e ampiezza di banda varia sui server remoti
– Quanto in profondità esplorare la gerachia di URL in un sito?
– Pagine duplicate e siti “mirror”
• Pagine “maliziose”
– Pagine spam
– Spider traps
Uno schema meno semplice
URLs “crawled”
E analizzate
Web nascosto
Pagin
e
Seed
frontiera
Crawling thread
Fasi di crawling
• Seleziona una URL dalla frontiera
• Preleva il documento a quell’ URL
• Analizza il documento
Quale?
– Estrai i link ad altri documenti (URLs)
• Verifica se esistono pagine già analizzate
– Se no, aggiungi gli indici
• Per ogni URL estratta
Es., accetta gli “.edu”,
obbedisci ai robots.txt,
etc.
– Controlla che superi opportuni URL test di
filtraggio
– Elimina duplicati
Architettura
Domain name server
Analizza la front page
DNS
Filtri e robots
robot exlcusion
URL
Doc
set
FP’s
filters
Elimina duplicati
WWW
Parse
Fetch
Già
visto?
URL Frontier
URL
filter
Dup
URL
elim
Spider Control
• Decide quali link i crawler debbano esplorare e
quali ignorare
• Può usare dei feedback provenienti da “usage
patterns” (analisi di comportamenti di utente)
per guidare il processo di esplorazione
Strategie di ricerca
Breadth-first Search
Strategie di Ricerca (2)
Depth-first Search
Trade-Off’s
• Breadth-first esplora uniformemente a partire
dalla pagina(e) root, ma richiede la
memorizzazione di tutti i nodi del livello
precedente (è esponenziale nel fattore di
profondità p). E’ il metodo standard.
• Depth-first richiede di memorizzare p volte il
fattore di branching (lineare in p), ma “si perde”
seguendo un’unica traccia.
Algoritmo di Spidering
Inizializza la coda Q con un set iniziale di URL note.
Until Q vuota o si esauriscono i limiti di tempo o pagine
memorizzabili:
Estrai URL, L, dalla testa di Q.
Se L non è una pagina HTML (.gif, .jpeg, .ps, .pdf, .ppt…)
continua il ciclo.
Se L già visitata, continua il ciclo.
Scarica la pagina, P, di L.
Se non è possibile scaricare P (e.g. 404 error, robot exclusion)
continua ciclo.
Indicizza P (cioè aggiungi rapp(P) all’inverted
inedex,oppure memorizza una copia cache).
Analizza P per ottenere una nuova lista di links N.
Appendi N in coda a Q.
Append:Strategie di queueing
• I nuovi link aggiunti come modificano la
strategia di ricerca?
• FIFO (appendi alla coda di Q) determina una
strategia di ricerca breadth-first.
• LIFO (aggiungi in testa a Q) determina una
strategia di ricerca depth-first.
• Alcuni sistemi usano delle euristiche per
collocare i nuovi link secondo priorità “focused
crawler” tese a direzionare la ricerca verso
pagine “interessanti”.
Strategie per Spider specializzati
• Ristretti a siti specifici.
– Rimuove alcuni links da Q.
• Ristretti a directories specifici.
– Rimuove i links non contenuti nel directory.
• Obbedisce a restrizioni imposte dai proprietari
dei siti (robot exclusion).
Dettagli sulle tecniche di Spidering :
1. Estrazione dei Link (puntatori)
• Si devono identificare tutti i links contenuti in una pagina ed
estrarre le relative URLs, per proseguire nell’esplorazione.
– <a href=“http://www.cs.utexas.edu/users/mooney/ir-course”>
I frames dividono
– <frame src=“site-index.html”> una pagina in
sezioni alla URL della
• Se esistono URL specificate con riferimento
pagina corrente, devono costruire un URL completo :
– <a href=“proj3”> diventa
http://www.cs.utexas.edu/users/mooney/ir-course/proj3
– <a href=“../cs343/syllabus.html”> diventa
http://www.cs.utexas.edu/users/mooney/cs343/syllabus.html
2. Esprimere i Link in formato canonico
• Variazioni equivalenti vengono normalizzate
rimuovendo la “slash” finale
http://www.cs.utexas.edu/users/mooney/
– http://www.cs.utexas.edu/users/mooney
• Si rimuovono i riferimenti a pagine interne
(ref’s) :
– http://www.cs.utexas.edu/users/mooney/welcome.html#courses
– http://www.cs.utexas.edu/users/mooney/welcome.html
3. Refresh: aggioramento delle
pagine
• Il Web è dinamico: ci sono molte pagine nuove, pagine
aggiornate, cancellate, riposizionate..
• Periodicamente lo Spider deve verificare tutte le pagine
indicizzate per aggiornamenti e cancellazioni :
– Basta guardare le info di intestazione (es. META tags
sull’ultimo aggiornamento) per verificare se la pagina è stata
aggiornata, e ricaricarla se necessario.
• Tiene traccia delle pagine più “dinamiche” nel tempo, e
controlla quelle in prevalenza.
• Aggiorna e verifica con preferenza le pagine più
popolari.
4. Robot Exclusion
• Alcuni siti Web o pagine possono richiedere che gli
spiders/robot non accedano né indicizzino certe aree.
• Due componenti:
– Robots Exclusion Protocol: E’ un protocollo che vieta
l’accesso da direttori specificati all’intero sito. Robots META
Tag: Etichetta documenti specifici per evitarne
l’indicizzazione o l’esplorazione.
Robots Exclusion Protocol
• Gli amministratori dei siti mettono un file
“robots.txt” alla radice del web directory
dell’host.
– http://www.ebay.com/robots.txt
– http://www.cnn.com/robots.txt
• Il file contiene una lista di directories proibite
per un dato robot, o agente di utente.
– Exclude all robots from the entire site:
User-agent: *
Disallow: /
Robot Exclusion Protocol Examples
• Escludere directories:
User-agent: *
Disallow: /tmp/
Disallow: /cgi-bin/
Disallow: /users/paranoid/
• Escludere uno specifico robot:
User-agent: GoogleBot
Disallow: /
• Consentire l’uso solo ad uno specifico robot:
User-agent: GoogleBot
Disallow:
User-agent: *
Disallow: /
5. Multi-Threaded Spidering
• Il collo di bottiglia consiste nel ritardo di rete per
scaricare singole pagine.
• E’ preferibile seguire molti “fili” della rete in parallelo
ognuno dei quali richiede una pagina da diversi host.
• Il precedente spider di Google aveva molti crawlers
coordinati, ognuno con 300 thread, complessivamente
capaci di scaricare più di 100 pagine al secondo.
6. Selezione delle pagine
• Quali pagine scaricare?? (non tutto il web!!)
• Metriche di importanza:
– Interest-driven (spiders specializzati)
– Popularity driven
– Location driven
Sommario (Spiders)
• Strategia di ricerca
• Strategia di aggiornamento (refresh)
• Minimizzazione del carico su altre
organizzazioni (robot exclusion)
• Selezione delle pagine
1. Spidering (o Crawling)
2. Indicizzazione
Modalità per indicizzare le pagine
sul Web
• Per ogni pagina identificata dallo Spider va
creato un indice. Tre metodi (non esclusivi)
– Si usano dei directories, che classificano le pagine
Web per argomento
– Si indicizza ogni documento esplorato dallo Spider
come full text (flat o strutturato)
– Si tiene conto della struttura ipertestuale del Web,
cioè degli hyperlinks
Indicizzazione mediante Directories:
a) Classificazione manuale
• Yahoo usa editors umani per generare un directory
gerachico di pagine web.
– http://www.yahoo.com/
• Open Directory Project è un progetto simile, basato sul
lavoro distribuito di editors volontari (“net-citizens
provide the collective brain”). E’ utilizzato da molti
motori di ricerca. Il progetto è stato avviato da
Netscape.
– http://www.dmoz.org/
Indicizzazione mediante Directories:
b) Classificazione automatica
• La classificazione manuale dei documenti sul web ad
opera dei gestori di portali o motori di ricerca richiede
molto tempo e molta forza-lavoro, è soggettiva, e
soggetta a errori.
• I metodi automatici di classificazione dei testi possono
essere usati per alleviare questo lavoro.
• Questi metodi si basano su tecniche di machine
learning.
Gerarchizzazione automatica di
documenti
• Lo sviluppo di tassonomie è un processo complesso,
richiede tempo, è soggettivo, produce errori.
• Esistono metodi automatici (Hierarchical
Agglomerative Clustering (HAC) ) per ottenere
automaticamente una strutturazione gerarchica.
Metodi di classificazione automatica
Wonderfu
Berlusconi
l Totti
acquires
Bush
Yesterday
Inzaghi
matchbefore
declare
s war
elections
...........
Politica
C1
Economia
C2
Sport
Cn
Classificazione Automatica (2)
• Dato:
1
n
– Un insieme di categorie: C  C ,.., C
– Un insieme T di documenti d,
definisci
f : T  2C


• VSM (Vector Space Model)
– I documenti sono rappresentati come vettori (modello
vettoriale).
– Sia i documenti che le categorie sono vettori.
– d è assegnato a C se
i
i
d  C  th
Esempio
d1: Politica
Bush
declares war.
Berlusconi
gives
support
Berlusconi
d2
d1
d3
d2: Sport
Wonderful
Totti in the
yesterday
match
against
Berlusconi’s
Milan
Berlusconi
acquires
Inzaghi
before
elections
C1 : Politica
C2
C1
Totti
Bush
d3:Economia
C2 : Sport
Il Classificatore di Rocchio
• Si parte da un insieme di documenti-campione T,
preassegnati manualmente alle varie classi
•
wij
, il peso
di wi in dj
– Ad esempio (ma esistono altri schemi di pesatura) TF *
IDF
k
• Cwi, il peso di wi in Ck :
k
Cw
 max
i
 0,

 wij
Tk djTk

 wij
Tk djTk

• Tk , i documenti di addestramento per C k
• Un documento d è assegnato alla classe Ck se:
d  Ck  th
Il classificatore di Rocchio
k
Cw
 max
i

0,

 wij
Tk djTk

 wij
Tk djTk

• Il peso della parola wi nel vettore che
rappresenta Ck è il massimo fra:
–0
– La differenza fra la somma dei pesi di wi nei
documenti “campione” usati per apprendere il
vettore Ck e la somma dei pesi di wi in tutti i
documenti del set di apprendimento che NON sono
appartenenti a Ck
Altri metodi di classificazione: SVM
Support Vectors
Iperpiano di
seperazione
Tk
Tk
1.Indicizzazione mediante
classificazione
2. Creazione degli indici
2.1 Full text
2.2 Usando informazioni
aggiuntive sul testo
Creazione automatica di Indici
nel Web IR
• Molti sistemi usano varianti dell’inverted file
• Ad ogni parola o keyword viene associato
l’insieme dei puntatori alle pagine che
contengono la parola
• Eliminazione di stopwords, punteggiatura..
• Usualmente si associa anche una breve
descrizione del contenuto della pagina (per
mostrarlo all’utente)
Creazione automatica di Indici (2)
– Poiché occorrono circa 500 bytes per memorizzare
l’informazione relativa ad ogni pagina, occorrono
circa 50 Gb per mantenere le informazioni relative a
100 milioni di pagine !!
– Tecniche di compressione possono consentire di
ridurre la taglia di un inverted file di circa il 30%
(dunque bastano 15 Gb per 100 milioni di pagine)
Creazione automatica di Indici (3)
• Alcuni inverted files puntano all’occorrenza di
una parola nel testo (non nel documento), ma la
tecnica è troppo costosa in termini di memoria.
• Se si possiede un puntatore di posizione dentro
la pagina, è possibile fare “proximity search”
cioè cercare frasi (parole fra loro contigue).
• Qualche motore di ricerca consente proximity
search, ma le tecniche non sono note
interamente.
Creazione automatica di Indici
(4)
• Una soluzione intermedia consiste nel puntare a
blocchi anziché a singole occorrenze nel
documento.
• Questo riduce la taglia dei puntatori e velocizza la
ricerca.
Metodi avanzati: Indicizzazione
usando il testo nelle ancore
• Lo Spider analizza il testo nelle ancore (between <a>
and </a>) di ogni link seguito.
• Il testo nelle ancore di solito è molto informativo sul
contenuto del documento cui punta.
• Si aggiunge il testo contenuto nell’ancora alla
rappresentazione del contenuto della pagina
destinazione (keywords).
• Questo metodo è usato da Google:
– <a href=“http://www.microsoft.com”>Evil Empire</a>
– <a href=“http://www.ibm.com”>IBM</a>
Indicizzazione usando il testo nelle
ancore (cont)
• E’ particolarmente utile quando il contenuto descrittivo
nelle pagine destinazione è “nascosto” nei logo delle
immagini piuttosto che in testi accessibili.
• Spesso non è affatto utile:
– “click here”
• Migliora la descrizione del contenuto di pagine
“popolari” con molti link entranti, ed aumenta la recall
di queste pagine.
• Si può anche assegnare un peso maggiore al testo
contenuto nelle ancore.
1. Classificazione
2. Creazione degli indici
2.1 Full text
2.2 Usando informazioni
aggiuntive sul testo
3. Ranking
3.1 Ranking sulla base del
contenuto
3.2 Ranking sulla base della struttura
ipertestuale
Ranking
• I metodi di ranking usati dai motori di ricerca sono topsecret
• I metodi più usati sono il modello vettoriale e booleano
• La maggioranza dei motori utilizzano per il ranking
anche gli hyperlinks. Le pagine “risposta” pi vengono
valutate (ed il loro numero viene esteso) sulla base del
numero di connessioni da e verso pi.
Link Analysis
Primi metodi di link analysis
Assunzioni
• Gli Hyperlinks contengono informazioni che
sussumono un giudizio sulla pagina
• Più links entrano in un sito, più importante è il
giudizio
• La visibilità (hubness) di un sito si misura
mediante il numero di siti che puntano ad esso
• La luminosità (authority) di un sito è il numero di
altri siti che esso punta
 Limite: non cattura l’importanza relativa dei siti
“parenti” (cioè ad esso collegati )
HITS - Kleinberg’s Algorithm
• HITS – Hypertext Induced Topic
Selection
• Per ogni vertice v  V in un sottografo di
interesse: a(v) - l’ authority di v
h(v) - la hubness di v
• Un sito è autorevole se riceve molte
citazioni. Le citazioni da parte di siti
importanti pesano di più di quelle da
parte di siti meno importanti.
• Un buon hub è un sito che è collegato
con molti siti autorevoli
Authority e Hubness
5
2
3
4
1
1
6
7
a(1) = h(2) + h(3) + h(4) h(1) = a(5) + a(6) + a(7)
Il grafo dei collegamenti
• I documenti sono visti come
i nodi di un grafo
• Gli hyperlinks sono visti
come archi diretti
• Gli archi possono avere pesi
• Si costruisce in tal modo il
grafo dell’intero web
• Gweb = (V(Gweb), E(Gweb))
– E(Gweb)  V(Gweb)V(Gweb)
1
2
3
5
0
0
41
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
60
0
0
1
0
0
0
0
0
1
0
0
0
70
0
L: Matrice delle adiacenze
Due metodi di ranking sono i più diffusi:
HITS e Page Rank
• Basati sulla link analysis:
– HITS (Hypertext Induced Topic Selection)
(Kleinberg, 1997)
• Obiettivo: ottenere il ranking di una pagina per ogni
specifica query (dinamico)
– PageRank (Brin and Page, 1998)
• Obiettivo : ottenere un ranking di tutte le pagine del web
indipendentemente dalle query (statico)
HITS Hubs and Authorities (1)
Obiettivo : ottenere un ranking delle pagine
per una particolare query Q = {w1, …, wn}
• Si estrae il set P di pagine che includono
le keywords di Q
• Si include il set delle back pages
B = { b : (b, p)  E(Gweb) }
• Si include anche il set delle forward
pages F = { f : (p, f)  E(Gweb) }
• Si definisce:
– VQ = PBF
– EQ = Eweb(BPPF)
– GQ = (VQ, EQ)
p1
b1
p2
b2
.
.
.
.
.
.
b|B|
back
set
p|P|
search
results
f1
f2
.
.
.
f|F|
forward
set
Hubs and Authorities (2)
• Per una specifica query si vuole trovare:
– Le authorities su quell’argomento o topic (dove cioè le informazioni
richieste effettivamente sono contenute)
– I siti hub, che puntano alle migliori pagine su quel topic
• le authorities più importanti avranno molti siti che puntano ad
esse
• Gli hubs più importanti avranno molti puntatori
• Assunzione: le migliori authorities sono puntate dai migliori
hubs e viceversa
Hubs and Authorities (3)
• Partendo dal grafo GQ, e dalla matrice di
adiacenza L, si definiscono due vettori
a = (a1, a2, …, an)T e h = (h1, h2, …, hn)T,
|VQ| = n, tali che:
– ai è il grado di autorità di vi  V(GQ)
– hi è il grado di di hubness di vi  V(GQ)
The HITS algorithm
(Kleinberg, 1998)
Inizializzazone
• h(0) := (1, 1, …, 1)T
Iterazioni
• k := 1
• Fino alla “convergenza”, esegui:
– a(k) := LT h(k-1)
(aggiorna a)
– h(k) := L a(k)
(aggiorna h)
– a(k) := a(k)/||a(k)|| and h(k) := h(k)/||h(k)|| (normalizzazione)
• Si possono riscrivere le due assegnazioni nei termini degli stessi vettori dell’
iterazione precedente :
– a(k) := LT h(k-1) = LT L a(k-1)
– h(k) := L a(k) = L LT h(k-1)
Significato delle matrici
T
T
LL eL L
• L è la adjacency matrix di GQ
• LT L è detta authority matrix:
A  LT L 
Aij

LTik
LT
n
Lkj
L
n
Aij   L Lkj   Lki Lkj
k 1
i
T
ik
k 1
Aij è il numero co-citazioni, cioè
Il numero di nodi che puntano sia a i che j
..vi ricorda qualcosa di già visto???????
j
k
Significato delle matrici L LT e LT L
• L è la adjacency matrix di GQ
• LT L è detta authority matrix
• L LT è detta hubness matrix:
j
H  LL  i
T
H ij
i

Lik
j
LTkj
k
L
n
n
H ij   L L   Lik L jk
k 1
T
ik kj
k 1
LT
Hij è il numero di co-referenze, cioè
Il numero di nodi puntati sia da i che j
Significato delle matrici
L LT e LT L
•
•
•
•
L è la adjacency matrix di GQ
LT L è detta authority matrix
L LT è detta hubness matrix
Le matrici sono:
– Simmetriche (aij = aji i,j = 1, …, n)
– Positive semidefinite (i, i  0, i = 1, …, n)
Il Power Method (1)
• Ricordate il passo iterativo :
– a(k) := LT L a(k-1)
– h(k) := L LT h(k-1)
• L’algoritmo iterativo per calcolare i vettori HITS a e h
è il power method per calcolare l’ eigenvector
dominante (cioè l’ autovettore che corrisponde all’
autovalore di valore massimo) di LTL e LLT,
rispettivamente (riguardatevi la lezione su LSI!!)
Il Power Method Converge
al Dominant Eigenvector
• 1, 2, …, k sono gli n eigenvalues di una matrice A (=LLT) e
|1| > |2|  …  |k|
• x1, …, xk sono gli eigenvectors associati e linearmente indipendenti
(indipendenza lineare : 1x1+ 2x2 +…+kxk=0 iff 1=…=k=0)
• Un generico vettore v0 (h(0) o a(0)) può essere scritto come:
– v0=1x1+ 2x2 +…+kxk
(k) := LT L a(k-1)=A a(k-1)
a
• Quindi:
– v1=Av0=1Ax1+ 2Ax2 +…+kAxk=11x1+ 22x2 +…+kkxk=
– 1[1x1+ 2(2/1)x2 +…+k(k/1)xk]
i : x i ,  i autovettore,autovalore di A, A   i x i
• E in generale:
– vm=Avm-1=Amv0=1Amx1+ 2Amx2 +…+kAmxk=11mx1+ 22mx2 +…+
kkmxk= 1m [1x1+ 2(2/1)mx2 +…+k(k/1)mxk]
• Poichè |i/1
| < 1, i = 2, 3, …, n, abbiamo:
lim
m 
1
1m
v m  lim
m 
1
1m
Am v 0  1 x1
Convergenza del Power Method (2)
lim
m 
1
1m
v m  lim
m 
1
1m
Am v 0  1 x1
m1A m1v 0
1
v m1

vm
m A m v 0
1
1 x1


1 1 x
1
1
• Perciò, con m grande:
• Osservazione: la velocità di convergenza
dipende dal rapporto |1/2|

HITS: Esempio (1)
3
2
6
1
5
4
1
11

20

30
T
L L 
4  0

50

60
2
0
3
0
4
0
5
0
0
0
0
0
0
2
1
1
0
1
1
0
0
1
0
3
0
0
0
0
6
0

0

0

0 

0

0
1
10

21

30
L 
4  0

50

60
2
0
3
1
4
0
5
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
1
1
12

20

31
LLT  
4  0

51

61
2
0
3
1
4
0
5
1
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
2
0
1
0
0
6
0

0

0

0 

0

0
6
1

0

1

0 

0

1
–a(1) := LT h(0)
HITS: Esempio (2)
–h(1) := L a(1)
3
1
2
3
6
5
1
2
authorities
 0.258 


 0 


 0.516 


 0.258 




0
.
775




0



1
=
1 0

2 1
3 0

4 0
5 0

6 0
2
0
0
0
0
0
0
3
4
5
1
0
0
0
1
0
0
0
0
0
1
0
1
0
1
0
0
1
6
5
hubs
4
a1
6
4
h0
 1
 
T

0
  
0 1
0 1
  
0   
0 1

0 1
 
 
 1
1
10

21

30

4  0

50

60
(la normalizzazione non è evidenziata)
2
0
3
1
4
0
5
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
1
a1
6
0   0.258 


0 0 




0 0.516 




0   0.258 


0   0.775 


0 0 
h1
 0.687 


 0.137 


 0.412 


 0 




0
.
412




 0.412 
–a(2) := LT h(1)
HITS: Esempio (3)
–h(2) := L a(2)
3
1
2
3
6
5
1
2
authorities
2
3
4
5
6
10

21

30

4  0

50

60
0
1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
1
0

0

0

0 

0

0
h1
4
a2
 0.687   0.072 


 
 0.137   0 


 
 0.412   0.573 


 
 0   0.215 


 


 
 0.412   0.788 


 
 0.412   0 
T
5
hubs
4
1
6
1
10

21

30

4  0

50

60
2
0
3
1
4
0
5
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
1
a2
6
0   0.072 


0 0 


0   0.573 


0   0.215 


0   0.788 


0 0 
h2
 0.706 


 0.037 


 0.409 


 0 




0
.
409




 0.409 
HITS: Esempio (4)
–a(3) := LT h(2)
–h(3) := L a(3)
3
1
2
3
6
5
1
2
authorities
2
3
4
5
6
10

21

30

4  0

50

60
0
1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
1
0

0

0

0 

0

0
h2
4
a3
 0.706   0.019 


 
 0.037   0 


 
 0.409   0.577 


 
 0   0.212 


 


 
 0.409   0.789 


 
 0.409   0 
T
5
hubs
4
1
6
1
10

21

30

4  0

50

60
2
0
3
1
4
0
5
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
1
a3
6
0   0.019 


0 0 




0 0.577 




0   0.212 


0   0.789 


0 0 
h3
 0.707 


 0.001 


 0.408 


 0 




0
.
408




 0.408 
HITS: Esempio (5)
–a(4) := LT h(3)
–h(4) := L a(4)
3
1
2
3
6
5
1
2
authorities
2
3
4
5
6
10

21

30

4  0

50

60
0
1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
1
0

0

0

0 

0

0
h3
4
a4
 0.707   0 


 
 0.001   0 


 
 0.408   0.577 


 
 0   0.211 


 


 
 0.408   0.789 


 
 0.408   0 
T
5
hubs
4
1
6
1
10

21

30

4  0

50

60
2
0
3
1
4
0
5
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
1
a4
6
0 0 


0 0 




0 0.577 




0   0.211 


0   0.789 


0 0 
h4
 0.707 


 0 


 0.408 


 0 




0
.
408




 0.408 
Strategia di Ranking
• L’ authority vector è il ranking delle pagine in GQ
• C’è un rischio di topic drift (slittamento del topic)
– Le pagine Back e Forward possono essere più generali
– C’è il rischio di recuperare pagine troppo generiche rispetto alla query
Q
• Inoltre, è possibile influenzare i punteggi di hubness
– Aggiungere degli archi in una pagina ne aumenta il valore di hubness, il
quale a sua volta aumenta l’autorithy delle pagine puntate, portando ad
un effetto di SPAM!!
PageRank
• Introdotto da Brin & Page (1998)
– Il peso dipende dal rank dei nodi parenti
1
P(a)  (1 d)  d
P(a i )
C(a i )
iA in

• P(a) è la probabilità che un navigatore casuale (random
walker) raggiunga la pagina a
 • C(ai) numero complessivo di (out) links della pagina ai
• d è il “damping factor” e modella la probabilità che il
“random walker” smetta di navigare
• Differenza rispetto a HITS
– HITS prende i pesi di Hubness & Authority
– Page Rank è proporzionale al rank dei suoi nodi parenti ma
inversamente proporzionale al “outdegree” dei suoi parenti
PageRank è usato da Google
The Anatomy of a Large-Scale Hypertextual Web Search Engine.
Brin, S. & Page, L (1998).
http://dbpubs.stanford.edu:8090/pub/1998-8
T1
3
A
PR=0.5
T2
4
2
PR=0.3
T3
5
PR=0.1
PR(A)=(1-d) + d*(PR(T1)/C(T1) + PR(T2)/C(T2) + PR(T3)/C(T3))
=0.15+0.85*(0.5/3 + 0.3/4+ 0.1/5)
Interpretazione probabilistica di
PageRank
• PageRank dispone di una chiara ed intuitiva spiegazione
probabilistica del suo funzionamento
• Pensiamo ad un navigatore che visita senza un particolare ordine
i nodi del web seguendo i vari links che trova nelle pagine
partendo da una pagina scelta a priori a caso (es.
www.yahoo.com)
• Il PageRank non è altro che un indice di quanto tempo,
mediamente, tale navigatore impiegherà ad arrivare su una
certa pagina.
• Questo modello prende il nome di “random walk” o
passeggiata casuale.
Notazione matriciale
A meno del dumping factor, posso riscrivere la formula del PageRank
di Brill&Page usando la notazione matriciale: a  aP dove a è
il vettore delle probabilità di raggiungere ogni pagina ai.


P=
Matrice delle
transizioni
Pij=0 se da i non c’è hyperlink verso j; 1/C(ai) altrimenti
Come calcolare il vettore delle
probabilità?
• Il modello delle Random Walk può essere
modellato mediante le Markov Chains
Catene di Markov
• Una catena di Markov consiste in n stati (sia S tale
insieme), e una matrice di probabilità di transizione
nn P.
• Ad ogni passo, ci troviamo esattamente in uno stato.
• Per 1  i,j  n, P(sisj) =Pij è la probabilità di
transitare in sj, se ci troviamo attualmente in si.
• Inoltre, se Xk è la variabile aleatoria che indica lo stato
raggiunto in tk (X assume valori in S) ,
P(Xk /X1,X2,… Xk-1)=P(Xk /Xk-1)
• Il valore di X al tempo k dipende solo dal valore della
variabile aleatoria nell’istante precedente
Markov chains
• Ovviamente
n

j 1
Pij  1.
• Le catene di Markov rappresentano un modello
delle “passeggiate casuali” (random walks) .
Vettori di probabilità
• Indichiamo con x = (x1, … xn) un vettore
che indichi lo stato raggiunto in un certo
istante.
• Es: (000…1…000) indica che si è nello stato si.
1
i
n
Poiché si tratta di un processo probabilistico,
dovremo invece considerare il vettore
x =(P(s1), … P(sn))= (x1, … xn), che indica che
la passeggiata
ha condotto in si con probabilità
n
xi, e  xi  1.
i 1
Catene di Markov ergodiche
• Una catena di Markov è ergodica se:
– Esiste un percorso fra ogni coppia di stati
– Da ogni stato, dopo un periodo di transizione
T0, la probabilità di raggiungere un qualsiasi
altro stato in un tempo fisso T>T0 è sempre
diversa da zero.
Catene ergodiche
• Se una catena di Markov è ergodica,
ogni stato ha una probabilità
“stazionaria” di essere visitato,
indipendentemente dal punto di
partenza.
– Il vettore delle probabilità x converge ad
un valore stazionario a
Variazioni del vettore di probabilità
• Se il vettore è x(i) = (x1, … xn) al passo i, come
cambierà al successivo passo?
• La riga i-esima della matrice P ci dice dove si
transiterà dallo stato i (contiene le probabiltà di
transizione da i verso gli stati ad essa collegati).
• Da x(i) , la prob. dello stato successivo è
distribuito come x(i) P (x(i+1) = x(i) P )
• Se il processo è ergodico, x convergerà ad un
vettore a tale che a=aP
• Poiché P è una matrice e a un vettore, che
vettore è a per P??
Power method
• x(k+1) =Px(k)
• La sequenza di vettori xk converge al valore stazionario
a
• Per il calcolo del valore stazionario a si utilizza il
power method (già visto
per HITS)

2 k
n k 
k
• x (k+1) =xPk=x(k)P  1 1v1   2 ( 1 ) v2  ...  n ( 1 ) vn 
• L’assunzione che esista un autovalore dominante è
essenziale per la convergenza del metodo

• Notate che, poiché in condizioni stazionarie deve
essere a=aP, a è l’autovettore dominante con
autovalore dominante 1.
Come si calcola pageRank?
• Si parte da pesi casuali e si itera il procedimento
• Es:
A
d = 0.85
PR(A) = (1 – d) + d(PR(B)/1)
PR(B) = (1 – d) + d(PR(A)/1)
Partiamo con P=1
PR(A)= 0.15 + 0.85 * 1= 1
PR(B)= 0.15+0,85*1=1
già converge!!
B
Partiamo con P=0
PR(A)= 0.15 + 0.85 * 0= 0.15
PR(B)= 0.15+0,85*0.15=0.2775
PR(A)= 0.15 + 0.85 * 0.2775=0.385875
PR(B)=0.47799..
PR(A)=0.5562..
PR(B)=0.6228..
Tende a 1!!
Esempio 2
Matrice adiacenze normalizzata
P
1/C(ai)
x(k+1) =Px(k)
x0 x1 x2
Iterazioni
x3
x4
x60
x611
Nota: “c” in figura è il damping factor (d)
Problemi
• Problema del “Rank Sink”
– In generale, molte pagine web non hanno
inlinks/outlinks
E.g.
nessun parente  rank 0
nessun figlio 
P converge ad un vettore di zeri
(pozzi o rank sink)
Nessun figlio --> converge a zero
Convergenza di Page Rank
•
•
•
PageRank è un algoritmo che è garantito convergere se e solo se la matrice P
derivata da quella di adiacenza è irriducibile (cioè se il grafo è fortemente
connesso) e aperiodica (il che corrisponde alla condizione di ergodicità vista
prima)
Per l’aperiodicità non ci sono problemi nella pratica (le pagine contenute in
anelli sono molto poche in confronto alle pagine del web); per l’irriducibilità
serve utilizzare una formula leggermente diversa, che introduce gli archi tra tutte
le pagine (anche dai pozzi), rendendo il grafo fortemente connesso
P(a)  (1 d)E(a)  d

P(a i )
iA in
1
C(a i )
• Il vettore E è una distribuzione di probabilità di pagine a cui il navigatore può
attingere per uscire da un rank-sink, allorché ne raggiunga uno, o da una
 senza out-edges (E(a)=1/C(a))
pagina
Rank sink
• Nella pratica dunque, i pozzi vengono trattati in uno di questi
modi:
– Per ogni pozzo i, si aggiungono archi fittizi dalla pagina i ad ogni altro
pozzo, in modo da far sì che i pozzi cedano uniformemente la loro
importanza al resto del grafo
– Ad ogni passo di PageRank si aggiunge alle componenti del vettore a una
stessa quantità (E) in modo che la norma di a rimanga pari a 1
– Alternativamente, si eliminano tutti i pozzi e si applica PageRank al grafo
così ottenuto; i pozzi verranno poi reinseriti alla fine
Altri Problemi di PageRank
Guardate la figura
e intuite il problema..
Problemi
• 302 Google Jacking: ogni pagina con rank basso che viene ridirezionata,
mediante un “302 server header” or a "Refresh" meta tag, ad una pagina con
P elevato, aumenta artificialmente il proprio P.
• Alcune web companies vendono links con valori alti di P ai webmasters.
Google combatte queste politiche.
• Attributo “nofollow” per combattere spamindexing (non seguire questo
link..)