Proč nám fulltextový stroj nerozumí?

Patříte mezi ty uživatele, kteří nevěřícně kroutí hlavou nad nesmyslnou odpovědí fulltextového stroje? Co může být příčinou toho, že i přes kvalitní implementaci dojde k takovým přehmatům? Hlavní nebezpečí je ukryto ve zpracování textu jako takového. Pomineme-li omezenou schopnost stroje pochopit smysl slov dokumentu, stále nám zůstávají určité technické bariéry, které nelze naprosto dokonale vyřešit. Například zhruba 10–20 procent shod zůstává nenalezeno, pokud stroj není schopen ohlídat překlepy a různé tvary slov. To vede ke ztrátě až 50 procent relevantních odpovědí, když se zaměříme jen na cizí slova nebo slova s pravopisně obtížným hláskováním.

Je však vše problém techniky, nebo jsou problémy i v naší psychice a nechuti trpělivě hledat? Vždyť uživatelé z 25 procent používají pouze jednoslovný dotaz, z 80 procent své dotazy vůbec nemodifikují a celých 85 procent se dívá pouze na první obrazovku výsledku (pozn.: 64 procent dotazů je unikátních). Další hodnoty přináší následující tabulka:

Co z uvedených hodnot vyplývá, je nasnadě – uživatelé pokládájí velice krátké dotazy většinou z 1–3 slov, nemají snahu dotaz ladit (viz. počet operátorů a dotazů na uživatele) a nemají trpělivost výsledek podrobněji prohlížet (viz. počet shlédnutých stran výsledku).

Práce fulltextového stroje je pak těmito faktory pochopitelně ovlivněna. Základní problém je vlastně získání dostatečného informačního potenciálu z krátkých dotazů. S tím přímo souvisí i jeden významný negativní aspekt – polysemie (tj. mnohovýznamnost slov). Ten ovlivňuje především přesnost (podíl skutečně relevantních odpovědí v množině výsledku), ale i na tuto nemoc se našlo řešení.

S klasickým vektorovým modelem (podrobněji zmíním v některé z dalších kapitol) se Yuwono a Lee – při testech nad 2.400 stránkami a 56 dotazy – dostali až k 75procentní průměrné přesnosti. To ale pro rozsáhlé báze textů, jakými je například Internet, nestačí. Byly proto navrženy další metody, jak k nedostatečnému informačnímu potenciálu dotazu dodat „přidanou hodnotu“. Kleinberg představil svoji metodu HITS, kterou založil na systému autorit a webových rozcestníků. I o této metodě budu hovořit v některém z pokračování. Zde se zaměřím na populárnější metodu PageRank, která nevyžaduje žádné zásadní teoretické znalosti o fulltextových modelech a přitom velice úspešně pomáhá zkvalitnit výsledkovou listinu odpovědi.

Google PageRank

Poslední dobou internetem hýbe PageRank. Jedná se o metodu vyhledávače Google. PageRank v podstatě určuje hodnoty na základě simulace náhodného pohybu uživatele po odkazech webového hypertextu. Myšlenka je ta, že uživatel si buď náhodně zvolí stránku s pravděpodobností q, nebo s pravděpodobností (1-q) následuje odkaz, který je právě na jím otevřené stránce. Jako důležitý předpoklad slouží skutečnost, že takový uživatel se nikdy nevrací zpět po již následovaném odkazu. Tento proces může být simulován pomocí Markovova řetězu, a tak se můžeme dopočítat ustálených hodnot pro jednotlivé stránky. Tato hodnota pak přispívá do ohodnocovací formule, kterou Google používá. V zásadě ji lze ale aplikovat do libovolného modelu již existujících fulltextů.

Budeme-li předpokládat, že out(a) je počet odchozích odkazů ze stránky a, a že na a odkazují stránky p₁ až p_n, pak je PageRank PR(a) definován jako:

PR(a) = q + (1-q)*sum(i=1..n; PR(pi)/out(pi))

Hodnota q bývá typicky nastavena na „pocit“ toho, jak moc věříme stránce a ne odkazům ostatních, resp. nakolik uživatel radši sáhne po nové stránce, než aby následoval odkazy. Tak by totiž činil pouze pokud by aktuální stránka byla obsahově zajímavá. Pozn.: Často se používá hodnota 0,15.

Za povšimnutí stojí také to, že obsahuje-li stránka příliš mnoho odkazů, nepřispívá dostatečně odkazovaným stránkám. Naopak máme-li několik stránek, které obsahují jediný link na naši centrální stránku (CS), a z ní vedeme pár odkazů (zpětně se vracející opět na CS), můžeme tak na CS zvýšit PageRank. Typicky bývá CS domovskou stránkou naší firmy. Představenou techniku černé díry, kdy uživatele přivedeme na naši hlavní stránku – a žádným z odkazů jej nepustíme mimo – se pravděpodobně dostatečně věnují kolegové v souběžných článcích (o fulltext marketingu) zde na Lupě. O technikách šalby a boje proti ní se nyní nebudu dále rozpisovat, ale v některém z dalších pokračování se k ní mohu na základě ohlasu v diskuzi pod článkem vrátit.

PageRank se počítá interaktivním algoritmem (nahlédněte do výpočtu Markovova řetězce). Jeho význam nepřispívá jen k určování pořadí výsledku dotazu, ale je i dobrým faktorem pro výběr odkazů ke stažení pomocí crawleru. Tato metoda pak přináší i výrazné zefektivnění procesu indexace a částečně i aktuálnosti nejdůležitějších stránek.

Metahledače

Protože už od dob Říma platí, že nikdo neví nic naprosto přesně, je možným řešením na výše uvedené problémy i jiný přístup než zlepšování kvalit jednoho stroje. Metavyhledávače pracují na principu „víc hlav víc ví“. Dotaz, který jim položíte, paralelně rozdistribuují na několik specializovaných vyhledávačů a výsledkové listiny poté spojí. Nejtypičtějšími zástupci jsou Metacrawler a SavvySearch (oba rozesílají své dotazy na zhruba 10 strojů). Dalšími pak Dogpile, Infind, MetaFind, Highway61, Cyber411, Mamma (vše .com) atd.

Výhodou je kromě možnosti zohlednění širšího pohledu na dotaz i možnost personifikace, kdy metavyhledávač rozpozná uživatele a na základě jeho profilu modifikuje váhy pro jednotlivé výsledkové listiny. Přijde-li tak ke stroji kuchař, stroj přiřadí největší váhu té výsledkové listině, která pochází ze specializovaného vyhledávače na vaření.

Tím ale výčet výhod nekončí. Výzkumné laboratoře NEC testovaly stroj, který při spojovaní výsledkových listin ověřoval aktuálnost výsledků, a zda jsou stránky v době položení dotazu vůbec dostupné. Patrně z důvodu obavy z přehlcení kapacit linek nebyl tento stroj, dle mých neověřených informací, poskytnut k volnému veřejnému vyzkoušení.

Jistě si kladete otázku: „Proč vůbec metavyhledávač? Přinese to něco opravdu dobrého?“ Zdá se, že ano. V roce 1998 čtyři největší fulltextové stroje indexovaly pouze nepatrný společný zlomek dokumentů – cca jedno procento. V dnešní době se odhady mnohdy velmi liší, ale přesto se předpokládá, že v průniku může být asi pět procent dat. Proto metavyhledávač přináší i jednu podstatnou vlastnost – prohledává větší množství dokumentů už jen prostým kombinováním výsledkových listin.

Ale právě v zakombinování parciálních metrik jednotlivých fulltextů je zakopán největší problém. Je zřejmé, že zvýšení úplnosti je nasnadě, ale je velký problém, co se stane s přesností. Řešení si ponechám do následujícícho dílu. Nepůjde nám jen o prosté přepočítaní relevance z výsledkové listiny (např. tajemného Q fulltextu Webfast), ale metoda musí pracovat i pokud výsledková listina nebude obsahovat žádné hodnoty relevance.

Dalším problémem je spíše technická stránka věci. Nebývá vhodné konstruovat metavyhledávač nad 200 fulltexty. Než k nám dorazí 200 odpovědí, které má metavyhledáváč teprve zhodnotit a zpracovat, může se stát cokoliv. Například nastane chyba na lince a my na odpověď musíme čekat. Proto do hry vstupuje i selekční problém. Místo toho, abychom využívali vše, vybereme jen několik nejrelevantnějších uzlů a těm dotaz pošleme.

Oba dva problémy lze řešit například metaindexem, jehož konstrukci i jednu z implementací (včetně všech matematických formulí) představím v následující kapitole.

Pro podrobnější informace můžete nahlédnout do následujícího seznamu literatury:

• O překlepech a jejich vlivu; Navarro, G.: Approximate Text Searching. PhD thesis, DCS, University of Chile, 12/1998.
• O struktuře fulltextových dotazů: Jensen, Spink, Bateman, Saracevic: A study of user queries on the Web. ACM SIGIR Forum 32:5–17/98; Pollock, Hockley: What's wrong with Internet searching. D-Lib Magazine 5, 1997; Silverstein, Henzinger, Marais, Moricz: Analysis of a very large AltaVista query log. TR 1998014, COMPAQ Systems Research Center, Palo Alto.