Analiza linków w celu

rankingu odpowiedzi

1

Web jako Graf Skierowany

Założenie 1: hyperlink między stronami
oznacza uznanie przez autora relewancji
(znak jakości)

Założenie 2: Tekst w kotwicy linku opisuje
wskazywaną stronę (kontekst tekstowy)

Strona A

hyperlink

Strona B

Kotwica

2

Tekst kotwicy

WWW Worm - McBryan [Mcbr94]



Jak rozróżnić dla ibm między:



Strona domowa IBM (głównie graficzna)



Strona copyright IBM (wysoka częstość termów
dla ‘ibm’)



Rywalizujące strony spamerów (wysoka
częstość termów)

www.ibm.com

“ibm”

“ibm.com”

“IBM home page”

Milion części
tekstu kotwic z
“ibm” wysyła
mocny sygnał

3

Indeksowanie tekstu kotwicy



W trakcie indeksowania dokumentu D,
włącz tekst kotwicy z linków wskazujących
na D.

www.ibm.com

Armonk, NY-based computer

giant IBM announced today

Joe’s computer hardware links
Sun
HP
IBM

Big Blue today announced

record profits for the quarter

4

C.D. Indeksowanie tekstu
kotwicy



Czasami mogą być niespodziewane efekty
uboczne - np.: evil empire.



Czy może wynik tekstu kotwicy z wagą
zależną od autoryzacji strony, na której
jest ta kotwica



Np.: Jeśli założymy, że treść z cnn.com or
yahoo.com jest autoryzowana to zaufamy
tekstom kotwicy z nich

5

Tekst kotwicy



Inne aplikacje



Ważenie/filtrowanie linków w grafie



Generowanie opisu stron z tekstu
kotwicy

6

Analiza cytowań



Częstość cytowań



Częstość łączna współcytowań



Współcytowania dla danego autora mierzą

“wpływ”



Analiza współcytowań



Bibliograficzna łączna częstość



Artykuły, które są łącznie cytowane są podobne



Indeksowanie cytowań



Kto jest autorem cytowanym? (Garfield 1972)



Wstępny pomysł Pagerank: Pinsker and Narin ’60s

7

Uporządkowanie niezależne od
pytania



Pierwsza generacja: wykorzystanie
zliczania linków jako prostej miary
popularności.



Dwie podstawowe propozycje:



Nieskierowana popularność:



Każda strona otrzymuje wynik = liczba linków
wejściowych plus liczba linków wyjściowych
(3+2=5).



Skierowana popularność:



Wynik strony = liczba jej linków wejściowych (3).

8

Przetwarzanie pytań



Najpierw wyszukaj wszystkie strony
pasujące do tekstu pytania (powiedzmy:
venture capital kapitał wysokiego
ryzyka).



Uporządkuj je wg popularności linków
(jakiś wariant z poprzedniego slajdu).



Więcej niuansów – użyj liczby linków jako
miary statycznej dopasowania (wykład 7),
połączonej z wynikiem dopasowania
tekstowego

9

Wyniki pagerank



Wyobraźmy sobie przeglądarkę
wykonującą błądzenie losowe po stronach
Web:



Start z losowej strony



W każdym kroku, wyjście ze strony po linkach
do kolejnych stron z jednakowym
prawdopodobieństwem



“W stanie ustalonym” każda strona ma
długoterminową intensywność wizyt – użyj
ją jako wynik dla strony.

1/3
1/3
1/3

10

Nie całkiem dobre



Web jest pełny nieaktywnych elementów.



Błądzenie losowe może utknąć w nieaktywnym
elemencie.



Nie ma sensu mówić o długoterminowej
częstości wizyt

??

11

Teleporting



W nieaktywnym elemencie, skocz
do losowej strony webowej.



W każdym aktywnym elemencie, z
prawdopodobieństwem 10%, skocz
do losowej strony.



Z pozostałym
prawdopodobieństwem (90%),
przejdź na losowy link.



10% - to parametr.

12

Wyniki teleportacji



Teraz nie może utknąć lokalnie.



Mamy długoterminową
częstość wizyt każdej strony
(niekoniecznie, co będzie
pokazane).



Jak możemy obliczyć
intensywność odwiedzin?

13

Łańcuchy Markowa



Łańcuch Markowa składa się z n stanów,
oraz stochastycznej macierzy przejść P o
rozmiarze nxn .



W każdym kroku, jesteśmy dokładnie w
jednym ze stanów.



Dla 1  i,j  n, elementy P

ij

macierzy

mówią nam, z jakim
prawdopodobieństwem j będzie
następnym stanem jeśli aktualnie
jesteśmy w stanie i.

i

j

P

ij

P

ii

>0

is OK.

14

.

1

1







ij

n

j

P

c.d. Łańcuchy Markowa



Oczywiście, dla każdego
i.



Łańcuchy Markowa są abstrakcyjnym
modelem błądzenia losowego.



Ćwiczenie: przedstaw teleportacyjne
błądzenie losowe ze slajdu nr 12 jako
łańcuch Markowa dla tego przypadku:

15

Ergodyczne łańcuchy Markowa



Łańcuch Markowa jest ergodyczny jeśli



Istnieje ścieżka z każdego stanu do
każdego



Dla każdego stanu początkowego, po
skończonym czasie przejścia T

0

,

prawdopodobieństwo pobytu w
dowolnym stanie dla ustalonego czasu
T>T

0

jest niezerowe.

Nie

ergodycz-ny

(parzysty/

nieparzysty)

.

16

c.d. Ergodyczne łańcuchy
Markowa



Dla każdego ergodycznego łańcucha
Markowa istnieje długoterminowa
częstość odwiedzin dla każdego stanu.



Stacjonarny rozkład
prawdopodobieństwa.



W trakcie długiego okresu czasu, każdy
stan jest odwiedzany proporcjonalnie do
tego rozkładu.



Nie ma znaczenia z którego stanu
wystartujemy.

17

Wektory prawdopodobieństwa



Wektor prawdopodobieństwa (wiersz) x
= (x

1

, … x

n

) pokazuje w którym punkcie

jest błądzenie.



Np.: (000…1…000) oznacza, że jest w
stanie i.

i

n

1

Bardziej ogólnie, wektor x = (x

1

, … x

n

)

oznacza, że błądzenie jest w stanie i z
prawdop. x

i

.

.

1

1







n

i

i

x

18

Zmiany w wektorze
prawdopodobieństwa



Jeśli wektor prawdop. jest x = (x

1

,

… x

n

) w danym kroku to jaki będzie

w kroku następnym?



Przypomnijmy, że wiersz i
stochastycznej macierzy przejść P
mówi nam gdzie przejdziemy ze
stanu i.



Więc z x, następny stan ma rozkład
prawdop. xP.

19

Przykład stanu ustalonego



Stan ustalony wygląda jak wektor
prawdopodobieństw a = (a

1

, … a

n

):



a

i

jest prawdop. że łańcuch jest w stanie

i.

1

2

3/4

1/4

3/4

1/4

Dla tego przykładu, a

1

=1/4 and a

2

=3/4.

20

Jak możemy obliczyć wektor
prawdopodobieństw
stacjonarnych?



Niech a = (a

1

, … a

n

) oznacza wektor wierszowy

prawdopodobieństw stacjonarnych.



Jeśli aktualny stan łańcucha oznaczymy przez a,
wtedy rozkład w następnym kroku jest aP.



Ale a jest stanem ustalonym, więc a=aP.



Rozwiązanie tego równania macierzowego daje
nam a.



Więc a jest (lewym) wektorem własnym P.



(Odpowiada “głównemu” wektorowi własnemu P
największą wartością własną.)



Macierze prawdopodobieństw przejść zawsze mają
największą wartość własną 1.

21

Jeden ze sposobów obliczenia
a



Przypomnijmy, że niezależnie od stanu
początkowego możemy „ewentualnie” osiągnąć
stan ustalony a.



Startuj z dowolnego rozkładu (np.: x=(10…0)).



Po jednym kroku jesteśmy w xP;



Po dwóch krokach w xP

2

, następnie xP

3

itd.



“Ewentualnie” znaczy dla “dużego” k, xP

k

= a.



Algorytm: mnóż x przez wzrastające potęgi P
aż iloczyn będzie wyglądał stabilnie.

22

Zarys algorytmu Pagerank



Przetwarzanie wstępne:



Dla danego grafu linków zbuduj macierz P.



Dla tej macierzy oblicz a.



Składowa a

i

jest liczbą między 0 i 1: to

pagerank strony i.



Przetwarzanie pytania:



Wyszukaj strony odpowiednie dla pytania.



Uporządkuj wg ich pagerank.



Porządek jest niezależny od pytania.

23

Rzeczywistość



Pagerank jest używany w google, ale jego
zastosowania bardzo liczne



Wiele bardzo specyficznych cech jest
używanych



Pewne adresy określają klasy pytań



Ranking z wykorzystaniem maszynowego
uczenia jest b. często stosowany



Pagerank jest ciągle b. użyteczny dla
takich rzeczy jak strategia crawlingu

24

Pagerank: Problemy i
warianty



Jak realistyczny jest model surfowania
przypadkowego?



(Czy jest ważny?)



Co jeśli zamodelujemy backspace?



Zachowanie jest mocno zniekształcone dla krótkich
ścieżek



Silniki wyszukiwawcze, zakładki & słowniki powodują
skoki nielosowe.



Specjalne modele surfowania



Ważone prawdop. przejść bazujące na dopasowaniu do
tematu/pytania (nierównomierny wybór krawędzi)



Specjalne skoki do stron wg tematu (np.: bazujące na
osobistym zainteresowaniu zakładkami & kategoriami)

25

Pagerank uwzględniający temat



Cel – wartości pagerank zależne od tematu
pytania



Koncepcyjnie, stosujemy losowe surfowanie,
które przechodzi z np.: z prawdop. 10%
probability, stosując następującą zasadę:



Wybierz temat (np.: jeden z 16 najwyższych
kategorii z ODP (Open Directory Project) oparty
na pytaniu & podanym przez użytkownika
rozkładzie dla kategorii



Przejdź losowo do strony dla wybranego tematu



Wygląda na trudne w implementacji: nie
możemy obliczyć PageRank w trakcie
odpowiedzi na pytanie!

26



Offline:Oblicz pagerank dla poszczególnych

tematów



Niezależnie od pytania jak poprzednio



Każda strona ma wiele wyników pagerank – jeden

dla każdej kategorii ODP, z przejściem tylko do tej

kategorii



Online: Kontekst pytania klasyfikowany dla

tematów (rozkład wag dla tematów)



Generuj dynamiczny wynik pagerank dla każdej strony –

suma ważona specyficznych dla tematu wartości pagerank

Cd. Pagerank uwzględniający
temat

27

Modyfikowany PageRank
(“Personalizacja”)



Wejście:



Graf webowy W



Wektor wpływu v dla tematów

v : (strona  stopień wpływu)



Wyjście:



Wektor rankingu r: (page  znaczenie

strony wrt v)



r

= PR(W , v)

Wektor ma jedną

składową dla każdego

tematu

Wektor ma jedną

składową dla każdego

tematu

28

Przejście nierównomierne

Przejście z prawdop.10% do strony Sporty

Sporty

29

Interpretacja złożonego wyniku



Dla danego zbioru personalizowanych
wektorów {v

j

}



j

[w

j

· PR(W , v

j

)] = PR(W , 

j

[w

j

· v

j

])

Dla danych preferencji użytkownika dla

tematów, wyraża kombinację “bazowych”
wektorów v

j

30

cd. Interpretacja

10% przejście do Sports

Sports

31

cd. Interpretacja

Health

10% przejście do stron Health

32

cd. Interpretacja

Sports

Health

pr = (0.9 PR

sports

+ 0.1 PR

health

) daje:

9% przejście do sports, 1% przejście do health

33

Hyperlink-Induced Topic Search
(HITS)



W odpowiedzi na pytanie, zamiast
uporządkowanej listy stron, znajduje dwa
zbiory powiązanych stron:



Strony Hub są dobrymi listami linków dla tematu.



Np.: “Bob’s list of cancer-related links.”



Strony Authority pojawiają się rekurencyjnie na
dobrych hubach dla tematu.



Najbardziej odpowiednie dla pytań
“szerokiego tematu” niż dla pytań
szukających stron.



Daje szeroki wycinek popularnej opinii.

34

Hubs i autorytety



Więc, dobra strona hub dla tematu
wskazuje na wiele autorytatywnych
stron dla tego tematu.



Dobra autorytatywna strona dla
tematu jest wskazywana przez
wiele dobrych hubów dla tego
tematu.



Taka powiązana definicja prowadzi
nas do obliczeń iteracyjnych.

35

Oczekiwanie

AT&T

Alice

I TI M
Bob
O2

Mobile telecom companies

Huby

Autorytety

36

Schemat wysokiego poziomu



Wybierz z Web bazowy zbiór
stron, które mogą być dobre
jako huby lub autorytety.



Z nich określ, mały zbiór
najważniejszych stron hubów i
autorytetów;



Algorytm iteracyjny.

37

Zbiór bazowy



Dla danego pytania tekstowego (np.:
browser), zastosuj indeks tekstowy
aby otrzymać wszystkie strony
zawierające browser.



Nazwij je zbiorem korzeniowy stron.



Dodawaj strony które



Wskazują na ten zbiór, lub



Są wskazywane przez strony z tego
zbioru.



Nazwij go zbiorem bazowym.

38

Wizualizacja

Zbiór

korzeniowy

Zbiór bazowy

39

Gromadzenie zbioru bazowego



Zbiór korzeniowy to zwykle 200-1000
węzłów.



Zbiór bazowy może zawierać tysiące
węzłów



Zależy od tematu



Jak znajdujemy bazowy zbiór węzłów?



Postępuj za linkami wyjściowymi przez
parsowanie stron zbioru korzeniowego.



Pobieraj linki wejściowe (i linki wyjściowe) z
serwera połączeń

40

Wybieranie hubów i
autorytetów



Oblicz dla każdej strony x w zbiorze
bazowym wynik dla huba h(x) i wynik dla
autorytetu a(x).



Inicjuj: dla wszystkich x, h(x)



1; a(x)



1;



Iteracyjnie aktualizuj wszystkie h(x), a(x);



Po iteracjach



Wynikowe strony z najwyższymi h() jako
huby



najwyższe a() jako autorytety.

Kluczowe

41

Iteracyjna aktualizacja



Powtarzaj poniższe aktualizacje dla
wszystkich x:





y

x

y

a

x

h



)

(

)

(





x

y

y

h

x

a



)

(

)

(

x

x

42

Skalowanie



Aby zapobiec zbyt dużemu
wzrostowi h() i a() , można
skalować w dół po każdej iteracji.



Współczynnik skalowania nie ma
znaczenia:



Zależy nam jedynie na względnych
wartościach wyników.

43

Ile iteracji?



Twierdzenie: relatywne wartości wyników
będą zbieżne po kilku iteracjach:



faktycznie, odpowiednio skalowane h() i a()
powodują, że wyniki dążą do stanu
ustalonego!



Dowód będzie pokazany później.



Potrzebujemy tylko względny porządek
wyników h() i a() – nie ich absolutne
wartości.



W praktyce, ~5 iteracji zbliża nas do
stabilności.

44

Japan Elementary Schools



The American School in Japan



The Link Page



‰ªès—§ˆä“c¬ŠwZƒz[ƒƒy[ƒW



Kids' Space



ˆÀés—§ˆÀé¼•”¬ŠwZ



‹{é‹³ˆç‘åŠw•‘®¬ŠwZ



KEIMEI GAKUEN Home Page ( Japanese )



Shiranuma Home Page



fuzoku-es.fukui-u.ac.jp



welcome to Miasa E&J school



_“ލ쌧E‰¡•ls—§’†ì¼¬ŠwZ‚̃y



http://www...p/~m_maru/index.html



fukui haruyama-es HomePage



Torisu primary school



goo



Yakumo Elementary,Hokkaido,Japan



FUZOKU Home Page



Kamishibun Elementary School...



schools



LINK Page-13



“ú–{‚ÌŠwZ



a‰„¬ŠwZƒz[ƒƒy[ƒW



100 Schools Home Pages (English)



K-12 from Japan 10/...rnet and Education )



http://www...iglobe.ne.jp/~IKESAN



‚l‚f‚j¬ŠwZ‚U”N‚P‘g•¨Œê



ÒŠ—’¬—§ÒŠ—“Œ¬ŠwZ



Koulutus ja oppilaitokset



TOYODA HOMEPAGE



Education



Cay's Homepage(Japanese)



–y“썬ŠwZ‚̃z[ƒƒy[ƒW



UNIVERSITY



‰J—³¬ŠwZ DRAGON97-TOP



Â‰ª¬ŠwZ‚T”N‚P‘gƒz[ƒƒy[ƒW



¶µ°é¼ÂÁ© ¥á¥Ë¥å¡¼ ¥á¥Ë¥å¡¼

Huby

Autorytety

45

Rzeczy do zapamiętania



Zbierane są razem dobre strony
niezależnie od języka strony zawartości.



Używa się tylko analizy linków po
zbudowaniu zbioru podstawowego



iteracyjne określanie wyniku jest

niezależne od pytania.



Iteracyjne obliczenia po przeszukiwaniu
indeksu tekstowego – znaczny narzut.

46

Dowód zbieżności



nn macierz sąsiedztwa A:



Każde z n stron w zbiorze bazowym ma
wiersz i kolumnę w macierzy.



Element A

ij

= 1 jeśli strona i wskazuje na

stronę j, w przeciwnym przypadku = 0.

1

2

3

1 2
3

1

2

3

0 1
0

1 1
1

1 0
0

47

cd. Dowód zbieżności: wektory
hub/autorytet



Rozpatruj wyniki habów h() i autorytetów
a() jako wektory z n składowymi.



Stosuj iteracyjne aktualizacje





y

x

y

a

x

h



)

(

)

(





x

y

y

h

x

a



)

(

)

(

48

cd. Dowód zbieżności: przejście
do postaci macierzowej



h=Aa.



a=A

t

h.

A

t

jest

transpozycj

ą A.

Podstawienie, h=AA

t

h i a=A

t

Aa.

Więc, h jest wektorem własnym dla AA

t

i

a jest wektorem własnym dla A

t

A.

Dalej, nasz algorytm jest szczególnym przypadkiem
znanego algorytmu dla obliczania wektorów własnych:
metody iteracji potęgowej.

Gwarantuje to zbieżność.

49

Problemy



Zniekształcenie tematu



Strony z poza tematu mogą generować
„autorytety” z poza tematu



Np.: sąsiedni graf może być uznany za
“super temat”



Wzajemnie wzmacniające się wyniki



Przypisane strony/witryny mogą
wzmacniać wzajemnie swoje wyniki



Linki pomiędzy przypisanymi stronami nie są
użytecznymi sygnałami

50

Literatura



IIR Chap 21



http://www2004.org/proceedings/docs/1p3
09.pdf



http://www2004.org/proceedings/docs/1p5
95.pdf



http://www2003.org/cdrom/papers/referee
d/p270/kamvar-270-xhtml/index.html



http://www2003.org/cdrom/papers/referee
d/p641/xhtml/p641-mccurley.html

51