Hlavní navigace

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

Michal Illich

V dnešním díle miniseriálu o moderních vyhledavačích - který vyvolal velmi zajímavou diskusi - si povíme o dalších algoritmech, které používají odkazy k zvýšení relevance hledání. Minule jsme si probrali algoritmy již používané, nyní se podíváme na postupy experimentální a v praxi ještě neimplementované.

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.

Našli jste v článku chybu?

27. 12. 2000 22:01

Michal Illich (neregistrovaný)
Presne tak, v silne propojene casti grafu jsou vyssi PageRanky, ty pak ovlivnuji zbytek grafu. Ty uzly (stranky), z kterych nevedou zadne odkazy ven, pusobi ale trochu problem - u Googleu tomu rikaji "rank sink" (neco jako vylevka) a optimalizuji algoritmus tak, ze tyto stranky pri prvnim vypoctu z grafu uplne vyhodi.
Nicmene, kdyz tuto optimalizaci neprovedete, nic hrozneho se nestane, akorat nemate zajistenou konvergenci...

27. 12. 2000 19:15

Artur Linhart (neregistrovaný)
Diky za informaci. Neni mi ale jasne, jak se vybiraji ty "silne propojene" body (pokud se vubec vybiraji), aby byla konvergence zarucena - domnivam se, ze se nevybiraji (jak by se pak mohlo vyhledavat na vsech strankach, kdyby u nejakych chybel PageRank, ze...), ale diky tomu, ze cele reseni zaplatpanbuh nevykazuje znaky nestability (doslova - to tezko asi nekdo jiny ovlivni 8^)), neprojevuji se chyby nejakymi drastickymi divergencemi. Je to asi zpusobeno tim, ze ty uzly, ktere maji ve…
Podnikatel.cz: V restauraci bez cigaret? Sněmovna kývla

V restauraci bez cigaret? Sněmovna kývla

Měšec.cz: Kdy vám stát dá na stěhování 50 000 Kč?

Kdy vám stát dá na stěhování 50 000 Kč?

Měšec.cz: Vklad na cizí účet je draze zpoplatněn (přehled)

Vklad na cizí účet je draze zpoplatněn (přehled)

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

120na80.cz: Popraskané rty? Některé balzámy stav zhoršují

Popraskané rty? Některé balzámy stav zhoršují

DigiZone.cz: Perspektivy TV v roce 1939 podle časopisu Life

Perspektivy TV v roce 1939 podle časopisu Life

DigiZone.cz: Česká televize mění schéma ČT :D

Česká televize mění schéma ČT :D

Vitalia.cz: Spor o mortadelu: podle Lidlu falšovaná nebyla

Spor o mortadelu: podle Lidlu falšovaná nebyla

Root.cz: 250 Mbit/s po telefonní lince, když máte štěstí

250 Mbit/s po telefonní lince, když máte štěstí

Měšec.cz: Za palivo zaplatíte mobilem (TEST)

Za palivo zaplatíte mobilem (TEST)

Podnikatel.cz: Chaos u EET pokračuje. Jsou tu další návrhy

Chaos u EET pokračuje. Jsou tu další návrhy

Podnikatel.cz: K EET. Štamgast už peníze na stole nenechá

K EET. Štamgast už peníze na stole nenechá

Root.cz: Nová třída SD karet A1 s vysokým výkonem

Nová třída SD karet A1 s vysokým výkonem

DigiZone.cz: NG natáčí v Praze seriál o Einsteinovi

NG natáčí v Praze seriál o Einsteinovi

Vitalia.cz: To nejhorší při horečce u dětí: Febrilní křeče

To nejhorší při horečce u dětí: Febrilní křeče

Vitalia.cz: Nahradí sluch, ale zvuk je zcela jiný

Nahradí sluch, ale zvuk je zcela jiný

Vitalia.cz: Mondelez stahuje rizikovou čokoládu Milka

Mondelez stahuje rizikovou čokoládu Milka

DigiZone.cz: Rádio Šlágr má licenci pro digi vysílání

Rádio Šlágr má licenci pro digi vysílání

Vitalia.cz: Jmenuje se Janina a žije bez cukru

Jmenuje se Janina a žije bez cukru

DigiZone.cz: ČT má dalšího zástupce v EBU

ČT má dalšího zástupce v EBU