Google w łańcuchach

$|X0$ W roku 2009 słowem dziesięciolecia stowarzyszenie American Dialect Society ogłosiło czasownik to google, którego polski odpowiednik - guglować/guglać - omawiany jest już na stronach Słownika Języka Polskiego, PWN. Nic dziwnego, wszak korzystanie z wyszukiwarki Google stało się elementem codzienności większości z nas i nie mamy skrupułów przed zadawaniem jej pytań o najbłahsze sprawy. Idąc za myślą przewodnią tego numeru Delty, o nieoczekiwanych związkach teorii z rzeczywistością, pokażemy, co wspólnego ma wszędobylska wyszukiwarka z teorią łańcuchów Markowa, sformułowaną w początkach XX wieku.

$|X$ Powiedzmy, że zwiedzamy graf spójny w taki sposób, że po znalezieniu się w danym wierzchołku, w kolejnym kroku odwiedzamy któregoś z jego sąsiadów, każdego z tym samym prawdopodobieństwem. Dla przykładu, kolejnymi odwiedzonymi wierzchołkami przy spacerowaniu po grafie na marginesie mogłyby być 1, 3, 4, 2, 4, 6,... Tabela przedstawia procentowy czas spędzony w poszczególnych wierzchołkach w pewnej symulacji 10 000 kroków zwiedzania tego grafu. Zauważmy, że przedstawione wartości wydają się mocno powiązane ze stopniami (czyli liczbami sąsiadów) poszczególnych wierzchołków. Oczywiście nie jest to wcale przypadek, co niebawem wyjaśnimy.

$|X$ Załóżmy, że przeglądamy strony internetowe w bezmyślny sposób (nie róbcie tego w domu!), za każdym razem klikając w losowo wybrany odnośnik na stronie, na jakiej się znaleźliśmy. Gdyby procentowa liczba odwiedzin danej strony (na przykład deltami.edu.pl) stabilizowała się na pewnej granicznej wartości, to byłoby rozsądnie uznać tę wartość za miarę ważności tej strony - im jest większa ta wartość, tym częściej trafialibyśmy na daną stronę, "losowo" przeglądając Internet. Na pierwszy rzut oka nie wiadomo jednak, jak tę wartość obliczyć - pomogą nam w tym wspomniane we wstępie łańcuchy Markowa.

$|X3$ Łańcuchy Markowa stanowią matematyczny model dla następującej (mało rzeczywistej, ale mam nadzieję dość obrazowej) sytuacji: wyobraźmy sobie układ $N$ miast (ponumerowanych liczbami od 1 do $|N$ ). W każdym z nich znajduje się teleport, który w losowy sposób wybiera miasto, do którego przenosi użytkownika. Niech teleport w mieście $|i$ przenosi do miasta $| j$ z prawdopodobieństwem $p . i j$ Załóżmy, że postanowiliśmy pozwiedzać miasta, codziennie korzystając (jednokrotnie) z zamieszczonych w nich teleportów.

Przyjmijmy, że miejsce startu ( "dzień zero") jest losowe; z prawdopodobieństwem $|πi$ jest to miasto $|i.$ Z jakim prawdopodobieństwem pierwszego dnia znajdziemy się w mieście $| j?$ Szansa na rozpoczęcie z $|k$ -tego miasta i przejście do $j$ -tego wynosi $|πkpk j,$ a zatem prawdopodobieństwo odwiedzenia $| j$ -tego miasta pierwszego dnia to $π 1 = PN k 1π kpk j. j$ Z rozkładu w "dniu zero" $π = (π1,...,πN )$ otrzymaliśmy rozkład w pierwszym dniu $1 1 π 1 = (π 1 ,...,π N ).$ W tym sensie prawdopodobieństwa $|(pi j)i, jDN$ określają nam przekształcenie $P ,$ które z jednego rozkładu tworzy inny.

$X$ Przy założeniu (*), przedstawionym na marginesie, $|r$ -ta iteracja przekształcenia $|P$ jest przekształceniem zwężającym, tzn. zmniejsza odległość między rozkładami o ustalony z góry czynnik. Aby to stwierdzenie miało sens, musimy doprecyzować odległość między rozkładami - u nas będzie to $π− ν = PN π − ν . k 1 k k$ W tej sytuacji z twierdzenia Banacha o punkcie stałym wynika, że istnieje punkt stały przekształcenia $P ,$ czyli taki rozkład $|˜π$ (nazywany stacjonarnym), że $|P(˜π) = ˜π,$ tzn. prawdopodobieństwo wystartowania z $i$ -tego miasta jest takie samo, jak prawdopodobieństwo znalezienia się w nim pierwszego (więc również drugiego, trzeciego, ...) dnia. Z twierdzenia Banacha wynika również, że rozkład $π˜$ może zostać uzyskany z dowolnego rozkładu $|π$ poprzez iterację $P ,$ tzn. ciąg $Pn(π )$ (gdzie $|Pn = P ○ ...○P$ ) jest coraz lepszym przybliżeniem $π˜.$

$|X5$ Kiedy rozkład $|˜π$ istnieje, to (zakładając $(⋆ )$ ) ma pewną ciekawą własność - $π i$ jest równy odwrotności średniego czasu oczekiwania na powrót do $i$ -tego wierzchołka, co teraz uzasadnimy. Załóżmy, że rozpoczęliśmy naszą wędrówkę, losując startowe miasto z rozkładu stacjonarnego. Pewnego dnia znaleźliśmy się w $i$ -tym mieście i zastanawiamy się, kiedy doń wrócimy. Liczbę dni, jakie upłyną do pierwszego powrotu, oznaczmy jako $|τi$ - jest to pewna losowa wielkość. Niech $|µi$ będzie wartością oczekiwaną $τi,$ tzn.

µ = P(τ = 1)+ 2 ⋅P(τ = 2) +3 ⋅P(τ = 3) +... = i i i i = P(τi⩾ 1)+ P( τi⩾ 2)+ P(τi ⩾3) + ...

(1)

Niech $k |X$ będzie numerem miasta odwiedzonego $|k$ -tego dnia i niech $|Akl$ oznacza zdarzenie, że $k |$ -tego dnia byliśmy w mieście $i,$ do którego nie wróciliśmy przez kolejnych $l$ dni. Zauważmy, że $=i)P(τ ⩾ k +1) = P(A 0 i$ oraz $=i)=˜π, P(X 0i$ gdzie Przez $|P(A$ oznaczamy prawdopodobieństwo zajścia zdarzenia $A$ pod warunkiem zajścia zdarzenia $|B.$ Korzystając z (1), dostajemy

π˜iµ i = P(A00)

(2)

Ponieważ wyszliśmy od rozkładu stacjonarnego, więc $P(A$ zależy tylko od $l$ (co może wymagać chwili zastanowienia), zatem suma pierwszych $|n+ 1$ składników w (2) to

P(An0)

(3)

gdyż zdarzenia $|Ak$ są rozłączne, ponadto ich suma $|Bn$ to zdarzenie, że w pierwszych $n$ dniach odwiedziliśmy co najmniej raz $i$ -te miasto. Z założenia $(⋆ )$ można wywnioskować, że $|P(Bn)$ jest zbieżne do 1, a zatem z (2) i (3) wynika $˜πiµi = 1.$

$|X6$ Na zakończenie teoretycznych rozważań zauważmy, że skoro wartość oczekiwana liczby dni potrzebnych na powrót do $i$ -tego miasta wynosi $µ i,$ to średnio "raz na $|µi$ " kroków wracamy do $| i,$ zatem jeśli $i | n D$ jest liczbą dni spędzonych w $| i$ -tym mieście podczas pierwszych $n$ dni, to $i n/n D$ staje się coraz bliższe $|1/µ i = ˜πi.$ Rozumowanie to można nietrudno uściślić przy użyciu Mocnego Prawa Wielkich Liczb.

$|X7$ Zauważmy, że nasz spacer po grafie spójnym odpowiada łańcuchowi Markowa o prawdopodobieństwie przejścia $−1 |pi j = deg(i) 1li j,$ gdzie $deg(i)$ to stopień wierzchołka $|i,$ a $|1li j$ przyjmuje wartość 1, jeśli $j$ jest sąsiadem $|i,$ oraz 0 w przeciwnym przypadku. Niech $|e$ będzie liczbą krawędzi. Łatwo uzasadnić, że suma stopni wierzchołków w grafie wynosi $2e,$ a zatem wagi $˜π = deg(i)/(2e) i$ stanowią rozkład. Zwróćmy uwagę, że

N N deg(k)- 1lk- j- PN k-11lk-- j deg( j) Q π˜kpk j = Q 2e ⋅deg(k) = 2e = 2e = ˜π j, k 1 k 1

zatem $˜π$ jest rozkładem stacjonarnym - uzasadnia to zaobserwowany wcześniej fenomen dotyczący średniego czasu przebywania w danym wierzchołku. Dość nieoczekiwanym stąd wnioskiem jest to, że średnia liczba odwiedzin jest w tym przypadku własnością lokalną i zależy tylko od stopnia wierzchołka i liczby krawędzi; bez znaczenia jest struktura pozostałej części grafu (jak również liczba wierzchołków).

$|X8$ Wróćmy do losowego przeglądania stron. Oczywiście, ono również określa nam pewien łańcuch Markowa. Gdyby spełnione było założenie $(⋆ ),$ to średnia liczba odwiedzin danej strony (czyli szukana wartość strony) zbiegałaby do wartości rozkładu stacjonarnego dla tej strony. Niestety podczas opisanego spacerowania po stronach internetowych moglibyśmy wpaść w pewne pułapki; możemy na przykład trafić na stronę bez żadnego odnośnika lub w inny sposób naruszyć $(⋆ ).$ Celem rozwiązania tego problemu wprowadza się niezerowe prawdopodobieństwo "teleportacji" - przed kliknięciem w dowolny odnośnik mamy szansę $| (1− α )$ (lub 1, jeśli na danej stronie nie ma odnośników) na przeskoczenie do losowo wybranej strony, każdej z jednakowym prawdopodobieństwem. W odróżnieniu od wcześniejszego przykładu, nie możemy jednak w prosty sposób wskazać rozkładu stacjonarnego, a dokładne rozwiązanie odpowiedniego układu równań nie wchodzi w grę ze względu na ogromną liczbę stron internetowych. Wiemy jednak, że zgodnie z twierdzeniem Banacha o punkcie stałym możemy przybliżyć rozkład stacjonarny poprzez rozpoczęcie od dowolnego rozkładu (np. $π 0 = 1/N i$ ) i powtarzanie

α ⋅π n j α ⋅π n j N (1− α)⋅π n j π ni+1 = Q ------- + Q -------+ Q ------------, j i deg( j) deg j 0 N j 1 N

(4)

gdzie pierwsza suma obejmuje wszystkie strony wskazujące na $i,$ a druga wszystkie "strony puste". Ten sposób mierzenia i obliczania ważności strony został zaproponowany przez Larry'ego Page'a i Sergeya Brina w 1997 roku, ochrzczony PageRank i wykorzystany w stworzonej przez nich wyszukiwarce Google jako istotny czynnik przy decydowaniu o kolejności wyświetlanych stron internetowych. I chociaż informacja o wartościach PageRanku nie jest już dostępna publicznie, wiele wskazuje na to, że ciągle odgrywa on niemałą rolę w sposobie, w jaki Google sortuje wyniki. Czytelnikom Zainteresowanym polecam samodzielne wyguglanie szczegółów.