Nové trendy ve vyhledávání (2)

Google používá svůj PageRank k posuzování známosti či důležitosti stránky obecně, tedy vzhledem k celému souboru. To mu umožňuje mít tuto hodnotu už předpočítanou z doby indexování dat, pak už ji jen používá jako heuristickou proměnnou pro řazení jinak podobných stránek.

Běžného uživatele ale většinou PageRank samotný příliš nezajímá. Pokud hledá informace o staročeské poesii, tak ho hlavní stránka Yahoo jako první odkaz moc neuspokojí, i kdyby byla sebevětší a sebeznámější. Neměl by tedy mít dobrý vyhledávač radši nějakou podobnou proměnnou specificky pro staročeskou poesii nebo jakékoliv jiné téma?

Autority a rozcestníky

Tak nějak uvažovali vědci z Almadenského výzkumného ústavu IBM. Zároveň si všimli, že lidé mají prapodivnou vlastnost – své vědomosti nějak strukturují – po celém světě tak vznikají katalogy tématicky řazených odkazů a na svých domácích stránkách si uživatelé vytvářejí malé rozcestníky o svých oblíbených tématech.

Robot, který všechny tyto informace zná (má přece svou databázi o stamilionech stránkách), by mohl všechnu tuto moudrost nějak uchopit. A když bude jeho uživatel pátrat po nějakém exotickém nebo odborném tématu, mohl by mu doporučit výborně spravovaný seznam zdrojů, který existuje na druhé straně zeměkoule. A protože náš moudrý robot zná důkladně i onen zdroj, tak uživateli nabídne rovnou odkazy v něm uvedené.

Ačkoliv toto zní dnes jako utopie, tak podobně inteligentní algoritmus existovat může a jak sami za chvíli uznáte, jeho podstata je poměrně jednoduchá.

Výzkumníci od IBM věc definují takto: Dobré „autority“ jsou stránky, na které odkazuje mnoho dobrých „rozcestníků“ (hubs), a dobré rozcestníky jsou stránky, které odkazují na mnoho dobrých autorit. Než proti takové definici začnete namítat jak odborně (že je to tautologie, definice kruhem nebo dokonce rozpor), případně laicky (cosi o psech honících se za vlastním ocasem nebo o baronovi Prášilovi, který se vytahoval z bažiny za vlastní tkaničky), vzpomeňte ještě na definici PageRanku: vysoký PageRank má stránka, na kterou odkazuje mnoho stránek s vysokým PageRankem. Je to stejná myšlenka, jen místo jedné sady proměnných máme sady dvě.

Ukážeme si, jak fungoval prototyp Clever Search, jak IBM svému vyhledávači říká (tento prototyp byl ve skutečnosti metahledač, ale stejnou myšlenku můžeme použít i pro vyhledávač s vlastní databází): Uživatel zadal svůj dotaz, třeba „MP3“. Clever se pak na tentýž dotaz zeptal klasického fulltextového hledače a potom z Internetu stáhl všechny vrácené stránky spolu se stránkami, které z nich byly hyperlinkovány a také těch, které na ně hyperlinkují. Tuto množinu stránek budeme nazývat základní.

Na základní množině provedl výše popsanou operaci – ohodnotil každou stránku jak z hlediska její „autoritativnosti“ (což by mělo znamenat, že obsahuje cenné informace), tak jako „rozcestník“ (zda odkazuje na dobré zdroje). Algoritmus na výpočet je podobný jako u PageRanku – opakovaně se sčítají patřičné proměnné a celá soustava rovnic se po několika iteracích ustálí. Nakonec Clever vypíše uživateli deset nejlepších autorit a deset nejlepších rozcestníků.

Všimněte si, že původní dotaz („MP3“) už běh programu po prvním kroku vůbec neovlivňuje. V základní množině tak budou i stránky, které toto slovo vůbec neobsahují, a tyto stránky mohou být také výstupem z Clever Searche. Konzervativní autoři fulltextů, kteří prosazují názor, že vyhledavač musí vypsat takové stránky, které požadované slovo obsahují co nejvícekrát, si asi nad tím mohou hlavy ukroutit… přesto tento algoritmus funguje a je téměř vrcholem současné teorie o vyhledávání.

Praxe

Krásné myšlenky se občas střetnou s krutou realitou… jakkoliv je nápad s autoritami a rozcestníky povedený, nebyl dosud nikde na světě realizován v běžně používaném vyhledávači. To proto, že vypočítat danou soustavu rovnic v dostupném čase, daném trpělivostí uživatele (maximálně pár sekund, radši ale stovky milisekund), není zatím v celosvětovém měřítku možné.

Na základě poměrně velké odezvy v diskusních fórech soudím, že by bylo dobré ujasnit několik věcí o PageRanku, tedy veličině, kterou Google používá k posuzování známosti a důležitosti stránky. Někteří čtenáři soudili, že vypočítat PageRank je příliš složité až nemožné, většina si nejspíš myslela, že to je možné pouze s výkonem, který Google má (tisíce linuxových strojů), já se pokusím stručně obhájit názor, že samotný výpočet PageRanku není nic složitého. Na rozdíl od předchozích částí, které byly zaměřeny teoreticky, si uvedeme pár čísel.

Máme 500 miliónů stránek (jak je u dnešních hledačů obvyklé), mezi nimi 5 miliard odkazů (konstanta 10 odkazů na stránku je obecně platná). Na uložení všech PageRanků potřebujeme 2G B paměti (počítám 4 bajty na číslo, ať už s plovoucí čárkou nebo bez). Na uložení všech linků budeme potřebovat 40 GB (počítám dvojici 4 bajtových čísel, každé vyjadřuje číslo zdrojového nebo cílového dokumentu, tato čísla jsou přímo indexy do pole PageRanků). Databázi o struktuře linků seřazenou podle čísla zdrojové stránky máme již před výpočtem připravenou.

Když už vyrábíme celosvětový vyhledávač, asi pro nás nebude problém koupit jeden počítač s 2 GB paměti. Do ní narveme pracovní hodnoty PageRanků. Linkovou strukturu i informace o PageRanku z minulého průchodu budeme číst z disku. Jistě by nás zajímalo, jak dlouho nám bude takový výpočet trvat. Vzhledem k triviálnosti operací (pouze sčítání čísel z pole – používáme stále zjednodušenou rovnici, že PageRank stránky je součtem PageRanků stránek, které na ni linkují), můžeme nároky na CPU zanedbat. Jediné, co nějakou dobu potrvá, je čtení z disku, což u SCSI bude minimálně 20 MB/s. Při těchto číslech bude jediný průchod trvat půlhodinu, nějakých 10 průchodů bude hotových za 5 hodin. Voilá, máme vystaráno.

Příští díl bude o hledání podobných stránek a automatické kategorizaci.