Jak pracuje metavyhledávač?

Strojem, na kterém si představíme jedno z možných řešení, je SavvySearch. Důvodem jeho volby je nejenom jednoduchá konstrukce, ale i schopnost řešit oba zmíněné problémy jedinou datovou strukturou – metaindexem.

Struktura metavyhledávače

Architektura metavyhledávače se většinou dělí na tři moduly. Prvním z nich je odbavovací modul. Jeho úkolem je volba těch dílčích vyhledávačů (DV), kam bude dotaz distribuován. Vlastní volba může být zajištěna plně automaticky nebo s pomocí uživatele. Existují i metody, při jejichž použití dochází k určitému stupni poloautomatizace. V takových případech má například uživatel možnost neustále zvyšovat počet DV, kterým metevyhledávač (MV) distribuuje dotaz.

Musíme si uvědomit, že tento modul je jedním z nejkompliko­vanějších, protože nikdy přesně neví, jaká data jsou na DV nebo jak se mění v čase. Metoda, kterou dnes představujeme, patří do kategorie ex-post, neboli metod, které se na základě svých zkušeností učí (pozn.: existují i metody, které určité hodnoty předvídají). Své získané zkušenosti si pak ukládá do metaindexu, kde se určitým výpočtem míchá obsáhlost výstupu a jeho používání uživateli.

Jakmile máme připravený transakční plán, můžeme přistoupit k formulování a distribuci dotazů na jednotlivé DV, a poté i k analýze výstupu (myšleno parsování). Tyto činnosti zajišťuje další modul, a tím je správce agentů rozhraní. Posledním modulem v řadě je tvůrce odpovědi. Ten zpracuje podle transakčního plánu dílčí odpovědi. Přitom vyřazuje duplicity, případně provádí další činnosti (ověřování aktuálnosti dílčích odpovědí atp.).

Metaindex

Zbývá popsat nejdůležitější strukturu celé operace – metaindex. Metaindex je matice M_mxS (m řádků, S sloupců), která na políčku M_i,j obsahuje známku pro odpověď na slovo t_i (i-tý term) strojem j. Před zahájením práce stroje bývá nastavena na hodnotu 0, v průběhu fungování stroje a jeho učení se může posléze nabývat hodnot kladných (odpovídajících dobré relevanci a celkové kvalitě) nebo naopak záporných.

Pozn.: Metaindex se konstruuje na základě předchozích znalostí, např. za uplynulý den. Jeho výchozí hodnota je za každý dotaz s x termy upravena o hodnotu 1/x. Penalizace je uplatněna pro všechny termy z dotazu, pokud stroj nevrátí žádný výsledek nebo výsledek, který uživatele nezajímá.

Pozn.: Hodnoty metaindexu lze přednastavit na hodnoty odpovídající vlastním testům nebo recenzím DV. Je možné metaindex určitým způsobem normalizovat (např. normalizovat nejprve vektory řádků, poté sloupců či naopak pouze vektory sloupců apod.). Je také možné udržovat metaindex pro každého uživatele zvlášť, resp. udržovat centrální metaindex (tzv. „defaultní“, pro neregistrovaného uživatele) a relativně řídké rozdílové matice pro registrované uživatele. Další modifikace základní metodiky zajisté naleznete sami. Jejich uplatnění závisí na prostředí, ve kterém MV pracuje, a přesný popis všech je nad rámec tohoto příspěvku.

Velice důležitou hodnotou, kterou budeme potřebovat, je inverzní frekvence vyhledávacího stroje (IFV, angl. IEF – inverse engine frequency). Někdy bývá též označována jako inverzní hodnota termu v rámci DVů. Její hodnota se pohybuje od 0 až po velmi velká kladná čísla a udává míru, nakolik je term v rámci DVů rozpoznatelný. Ukažme si vše na následujícím příkladě.

Máme dotaz složený z několika slov. Je bezpochyby naším cílem zajistit, aby parciální dotaz putoval na DV, kde je vysoká (nebo alespoň kladná) hodnota metaindexu M. Zároveň pro nás ale nejsou důležitá slova, která jsou takto dobře řešitelná všude, protože to nám příliš nerozvrství vrácené parciální dotazy na více či méně relevantní. Naproti tomu slova, která dobře řeší jen pár DV, ale ostatní nikoliv, jsou velice důležitá – ta nám pomáhájí vrácené výsledkové listiny dobře zpracovat.

Výpočet ief pak vychází z kalkulace, kterou si v průběhu tohoto seriálu připomeneme ještě alespoň jednou – a to u vektorového modelu. Nejprve ale nadefinujeme hodnotu, která počítá, na kolika strojích je term dobře řešitelný:

ft = count( s=1..S; Mt,s > 0 )

Vlastní ief pak určíme jako

ieft = log( S/ft )

Nyní můžeme kalkulovat podobnost dotazu Q vůči stroji S jako

simS,M(Q) = sum( all t in Q; Mt,S ieft ) / length( MS )

Přičemž M^S představuje vektor reprezentující S-tý sloupec matice M a jeho délku length spočteme klasicky jako odmocninu ze součtů kvadrátů všech jeho složek (pozn.: pro dvě složky by se jednalo o známou Pythagorovu větu).

Pakliže jsme již prováděli odpovídající normalizace metaindexu, jak bylo naznačeno v poznámce v úvodu této podkapitoly, nemusíme již délku vektoru sloupce metaindexu počítat a ušetříme tak trochu výkonu stroje při výpočtu relevancí.

Vlastní hodnota sim, kterou jsme zatím vypočítali, není ještě příliš vhodná pro skutečné nasazení. Je dobré se v prostředí Internetu chovat poněkud decentněji. Tím myslím například to, že nemá cenu zaplavovat neustále dotazy servery, které jsou aktuálně přetížené nebo v poslední době nemají kvalitní odezvu. Proto například SavvySearch započítává rovněž aktuální penalizace za nekvalitní výsledky nebo horší dobu odezvy. Výpočet těchto penalizací můžete nalést v [DH97].

Vlastní přepočítaní parciálních relevancí se provádí prostým pronásobením s hodnotou podobnosti pro daný DV, která je za tímto účelem pochopitelně normalizována, např. na interval 0..1. Pokud stroj parciální relevance neposkytuje, můžeme je stanovit sami. Metody, jak to učinit, se nedají zobecnit a přímo závisí na DV, pro který chceme relevance dopočítat. Můžeme např. relevancí zásahů proložit určitou křivku (převrácenou hodnotu exponenciály, funkci 1/n nebo diskrétní odstupňování od 1.0 až k 0.0 a dokonce i pevné nastavení na hodnotu 1/2) nebo si metavyhledávač stáhne aktuální podobu stránek výsledkové listiny a relevance si dopočítá např. na základě metod, které si představíme později. Zde se již ale jedná o řešení, které nemusí být vhodné pro volný internetový provoz, ale spíše pro firemní vyhledávací brány.

Zmínili jsme možnost, že je metaindex udržován personalizovaný. V takovém případě doznává změn na základě zpětné vazby, kdy se sleduje, na které zásahy ve výsledné listině uživatel nahlédl. Pokud nepersonalizujeme, můžeme sledovat totéž pro všechny stroje, a tento výpočet provádět v určitých časových dávkách analýzou logu.

Podstatný rozdíl je ale v tom, jak moc přidáváme nebo naopak snižujeme hodnoty v metaindexu. Konzervativní chování (malé změny hodnot) by mělo být používano výhradně pro nepersonalizované stroje, které jsou ostatně pro Internet používány nejvíce.

Závěr, výhody

Výhody metavyhledávačů jsou jednak ve velké úplnosti a také v možnosti integrovat libovolné vyhledávací služby do jediné. To může být výhodné pro firemní vyhledávací brány. Nehledě na fakt, že metavyhledávač nemusí stahovat webové stránky k indexování, takže je, co se týče provozních nákladů, nesmírně výhodný.

Na druhou stranu je ale s podivem, že v české doméně nepracuje jediný funkční metavyhledávač, přestože jejich konstrukční náročnost odpovídá většímu zápočtovému programu na mnohých vysokých školách…

Dodatek

V následujícím díle popíšeme centralizované i distribuované architektury vyhledávacích strojů. Distribuovanou architekturu budeme demonstrovat na stroji, který pro svoje potřeby využívají takové organizace jako CIA nebo NASA. Dále se budeme zabývat již vlastními modely a jejich kritikou.

Literatura:

[DH97] Dreilinger, D., Howe, A. E.: Experiences with Selecting Search Engines Using Metasearch. ACM TIS, 15–3/07/97, pp 195–223.

O metavyhledávačích se můžete více dozvědet z prací Gravano a spol. (GlOSS), Selberga a Etzioniho (MetaCrawler), a mnohých dalších (Howe, Dreilinger, …).