Student World

Je základem úspěchu Googlu opravdu systém řazení zvaný PageRank? Jedná se o přísně utajovaný algoritmus? Jaká za ním stojí matematika? Můžeme si fungování PageRanku přiblížit nějak jednoduše, ale zase nejen slovně?
Motivací pro napsání tohoto článku byl následující text

Jan Brandts, Michal Křížek: Lineární algebra ukrytá v internetovém vyhledávači Google, Pokroky matematiky, fyziky a astronomie 3/2007

Tento článek není rozhodně určen profesionálním matematikům, nicméně shrnuje něco málo pro ty, které naopak zase neuspokojuje úplně obecné povídání. Výklad PageRanku na české Wikipedii je hromadou vzorců, které jsou pro normálního člověka samy o sobě nesrozumitelné. Výklad na Jak psát web (v části A teď česky) je srozumitelný, ale slovní. Zkusme něco mezi.

Nejprve shrnutí toho, co alespoň matně tušíme. Před Googlem internetové vyhledávače vycházely především z toho, nakolik webová stránka (respektive slova v textu na stránce) odpovídala uživatelovu dotazu. Google ovšem stránky řadí podle svého vlastního algoritmu, PageRanku. Jako odpověď na uživatelům dotaz dává na první místa stránky, které jsou „významnější“. Samozřejmě – stále musí nějak obsahovat i slova, která uživatel hledá. Z čehož vyplývá, že hodnota PageRanku je významná hlavně u „neostrých“ obecných dotazů. Google také kromě PageRanku užívá i celou řadu dalších mechanismů.

Kromě těchto úplných obecností by si člověk myslel, že algoritmus PageRank musí být něco tajného, protože právě PageRank zapřičinil hodnotu Googlu. Nejprve k pravdivosti druhé části věty: Fakt je, že Google se od konkurence odlišil i jinými věcmi, třeba preferenci textové reklamy, platbou za kliknutí, neportálovým přístupem (tj. firma se dlouho soustředila opravdu jen a jen na vyhledávání, nevyvíjela aplikace pro posílání elektronických pohlednic). Nakonec i principy obdobné jako je PageRank používají i jiné vyhledávače, například Teoma. A v neposlední řadě – může to být i tak, že úspěch Googlu byla prostě historická náhoda, pro kterou nyní ex-post hledáme složitá vysvětlení, namísto toho, abychom se spokojili s pokrčením ramen a konstatováním „tak to holt chodí“.
Nyní konečně k vlastnímu PageRanku. Kupodivu vůbec není tajný. O PageRanku jsou veřejně dostupné nejen obecné principy, ale i vlastní matematický model. Podrobně ho popisuje výše odkazovaný článek v Pokrocích.

Takže základní matematika bez vzorců:
– Stránka je tím významnější, čím více stránek na ní odkazuje
– Stránka je tím významnější, čím více významných stránek na ní odkazuje (odkazy nemají stejnou váhu)
– Váha odkazu se liší i podle toho, na kolik stránek daná stránka odkazuje (Seznam je jistě významný web, ale odkazuje na tolik stránek, že fakt, že na někoho odkazuje Seznam, žádnou zvláštní váhu nemá)

Jak potom ale PageRank spočítat? Zdá se, že tato metoda výpočtu je „zacyklená sama do sebe“. Abyste mohli zjistit význam nějaké stránky, potřebujete znát význam všech ostatních stránek (a ten zase závisí na stanovené stránce). V zásadě, pokud stanovíte váhy příslušející jednotlivým kritériím, můžete pouze ověřit, zda určité řešení je správné (vyhovuje podmínkám), nebo ne. Úloha vůbec nemusí mít řešení, nebo může mít řešení více.
Naštěstí si problém lze zjednodušit. Dejme tomu, že nějaký PageRank už k dispozici máme. Můžeme nyní začít počítat jenom změny; počet odkazů se změnil tak a tak, což váhu stránky změnilo tak a tak – změnu váhy dalších stránek zohledníme třeba v až příštím kroku. Takhle nějak funguje u Googlu přepočítávání.

Úplný začátek výpočtu musí být nějaký iterační postup. Dejme tomu, že máme 4 stránky:
stránka 1 odkazuje na stránku 2
stránka 2 odkazuje na stránky 1, 3 a 4
stránka 3 odkazuje na stránku 4
stránka 4 neodkazuje nikam

Matice v prvním kroku bude vypadat takto. Řádky odpovídají jednotlivým stránkám, sloupečky odkazům na stránky.

tj. zohlednili jsme váhu odkazů podle toho, na kolik stránek daná stránka odkazuje. Teď zohledníme váhu jednotlivých stránek podle počtu/kvality odkazů na ní (tj. sečteme sloupce matice).
1… 1/3
2… 1
3… 1/3
4… 4/3

provedeme přepočet; odkazy budou mít relativní váhu podle toho, jakou váhu má ta která stránka.

opět sečteme sloupečky
1… 1/3
2… 1/3
3… 1/3
4… 2/3
a upravenými koeficienty vynásobíme původní matici

nyní bychom opět sčítali sloupečky.
Google ovšem musí pracovat s maticí, jejíž počet řádek odpovídá počtu všech indexovaných internetových stránek. Čímž se dostáváme k tomu, že náš iterační postup musí splňovat několik vlastností:

– bude vůbec konvergovat (musí?)
– bude konvergovat k jedinému, správnému výsledku (i když je to antiintuitivní, úloha by mohla mít třeba i více „stabilních řešení“ a záleželo by na tom, jakou iteraci provedeme)
– bude konvergovat v rozumném čase
– bude pracovat s takovými objekty, s nimiž pracovat vůbec půjde (viz výše příklad s maticí neuvěřitelných rozměrů); bude umožňovat postup rozložit mezi více počítačů, paralelizovat (ať se tím myslí cluster nebo cokoliv jiného).
Matematické modely ukazují, že problémem (který může způsobit nekonvergenci) jsou zde koncové stránky, které už na nic neodkazují (v našem modelu stránka 4 se samými nulami) a dále stránky v uzavřených „kapsách“, které odkazují jen samy na sebe. Viz třeba stránky na serveru, který neodkazuje nikam dál, ale má menu svých rubrik. Tady stojí za to říct, že stránkou se v rámci algoritmu myslí cokoliv, co má vlastní URL adresu, třeba dokumenty ve Wordu či PDF, ale také veškeré obrázky (z čehož vyplývá, proč je tak důležité zkoumat objekty, z nichž nevede další odkaz).
PageRank to řeší tak, že koncovým objektům přidává náhodný odkaz.

Až potud je celý postup zdokumentován. To, co je na algoritmu Googlu tajné, je pak až způsob, jak se ze spočítaného ohodnocení získá veřejný PageRank zobrazovaný v Toolbarech nebo na analytických stránkách (čísla od 1 do 10 jsou ale jen „zaokrouhlení“ předávaná uživatelům – snad podle logaritmické funkce). A samozřejmě ještě zbývají třeba postupy, které Google používá proti podvodníkům, odkazovacím farmám atd.

autor Pavel Houser