Dokumentografické informační systémy 2

V úvodním díle věnujícímu se dokumentografickým informačním systémům (zkráceně DIS) jsem se snažil čtenáři představit tuto problematiku. Dnes je tedy čas na hlubší prozkoumání. Konkrétně se zaměříme na booleovský a vektorový model DIS.

Upozornění: Protože některé části textu vyžadují náročnější sazbu, se kterou jsou v případě HTML problémy, zapsal jsem taková místa v syntaxy LaTeXu. V případě zájmu si můžete stáhnout PDF offline verzi tohoto i prvního dílu, kde je sazba dle požadavků.

Nejprve ale pro pořádek malá rekapitulace pro osvěžení paměti. DIS slouží pro uchovávání textů v přirozeném jazyce bez pevné vnitřní struktury (např. příspěvky v elektronických konferencích). Je složen ze dvou hlavních částí: subsystému zpřístupnění dokumentů, který na základě dotazu poskytne sekundární informace (název, autora apod.) o dokumentech odpovídajících položenému dotazu a subsystému dodání dokumentů. V následujícím textu se zaměříme na modely DIS a na jejich vnitřní implementaci.

Booleovský model

Booleovský model je nejstarším, přesto dosud nejpoužívanějším modelem (můžeme jej vidět např. na Altavistě). Jeho teoretické základy byly popsány již v 50. letech minulého století.

Každý dokument je v indexu reprezentován pomocí množiny termů (způsob indexace byl popsán v minulém čísle), které jej co nejlépe popisují. Dotaz je pak sestaven z termů a logických spojek dávající logický výraz. Takový dotaz může vypadat např. takto: term1\ and\ (term2\ or\ term3). Obecně lze použít následující logické spojky:

• A AND B: Logický součin, konjunkce. Ve výsledku budou dokumenty, které obsahují term A a současně B.
• A OR B: Logický součet, disjunkce. Ve výsledku budou dokumenty, které obsahují term A nebo B.
• A XOR B: Exkluzivní součin. Ve výsledku budou dokumenty, které obsahují term A nebo B, nikoliv však oba současně.
• NOT A: Negace. Ve výsledku budou dokumenty, které neobsahují term A.

Protože použitím pouze uvedených typů dotazů by informační systém moc kvalitní nebyl, jsou používány další rozšíření. Jedním z nich je možnost dotazovat se i na sekundární informace, např.: „demagog“\ and\ (autor=„Váša“). Dalším je dovolit uživateli použít zástupných znaků (typicky otazník pro právě jeden znak či hvězdička pro libovolný počet znaků). Bohužel některé systémy, které jej podporují, většinou dovolí tyto zástupky vkládat pouze na konec termů.

V některých případech může hvězdička či otazník — byť nedokonale — simulovat chybějící lemmatizátor. Např. zadáním dokonal* vyhledá i termy „dokonalý“, „dokonale“ apod. Problém však nastává u termů, které mohou být předponou termů jiných. Např. pokud chceme vyhledat dokumenty obsahující term „čas“, lze zadat čas*, ale bohužel dostaneme na výstup i dokumenty obsahující termy jiného významu (např. „časopis“). Některé DIS dovolí kromě zástupek zadávat i regulární výrazy, které mohou být i poměrně složité.

Častým způsobem omezení výsledné množiny je tzv. proximitní omezení. To říká, v jaké maximální vzdálenosti mají být dva termy od sebe umístěny. Použít lze např. následující dotazy:

• A (m,n) B: term A je vzdálen minimálně m a maximálně n termů od termu B.
• A sentence B: term A se vyskytuje ve stejné větě jako term B.
• A paragraph B: term A se vyskytuje ve stejném odstavci jako term B.
• A chapter B: term A se vyskytuje ve stejné kapitole jako term B.

V booleovském modelu je zajímavě vytvářen index. Ten totiž není tvořen tak, jak by se očekávalo, tedy že ke každému dokumentu je přiřazena množina termů, které obsahuje, ale naopak, ke každému termu je přiřazena množina dokumentů, které daný term obsahují (tzv. invertovaný indexový soubor). Toho je pak s výhodou používáno při vyhodnocování dotazů.

Pokud DIS umožňuje definovat strukturovaný index (tzv. tezaury, opět viz minulý díl), je způsob kladení dotazu dále rozšířen o možnost ptát se na jednotlivé úrovně provázanosti termů. Jako příklad uveďme Oracle SQL*Text retrieval, který rozšiřuje jazyk SQL o speciální operátory, kterými určujeme nejen term, ale i to, zda ve výsledku mají být dokumenty obsahující jeho nadřazené či podřazené termy. Díky tomu se můžeme na Oracle dotazovat na množinu úplných textů. Tabulka Tabulka 1 obsahuje tyto operátory a jejich význam. Pro zajímavost uveďme, že uvedené operátory vycházejí ze standardu ISO-2788.

Operátory Oracle SQL*Text

operátor	význam	popis
NT (A)	NARROWED TERM	užší term k termu A
BT (A)	BROADER TERM	širší term k termu A
TT (A)	TOP TERM	nejširší term k term A
RT (A)	RELATED TERM	příbuzné termy k termu A
PT (A)	PREFERRED TERM	preferovaný term k termu A
SYN (A)	SYNONYMUM	synonyma k termu A

Velkým nedostatkem Booleovského modelu je neschopnost seřadit výsledek v pořadí, které by udávalo relevantnost jednotlivých dokumentů vzhledem k položenému dotazu. Přesto situace není tak beznadějná, jak se může zdát. Jestliže dotaz obsahuje logické spojky OR, lze výsledky rozdělit do několika tříd stejné hodnoty (viz dále). Mějme například následující dotaz:

$Q = (A\ or\ B)\ and\ (B\ or\ C)\ and\ D$

Ten převedeme do tzv. disjunktně konjuktivní normální formy:

$ \begin{array}{lrrcrcrcr­c} Q =& (& A & and & B & and & C & and & D) & or \\ & (& A & and & B & and & not\ C & and & D) & or \\ & (& A & and & not\ B & and & C & and & D) & or \\ & (& not\ A & and & B & and & C & and & D) & or \\ & (& not\ A & and & B & and & not\ C & and & D) & \end{array}$

Každý řádek nazýváme elementární konjunkce. Všimněte si, že každá konjunkce je disjunkní k libovolné další. Ohodnocení elementární konjunkce je číslo udávající počet termů, které nejsou negovány (nemají před sebou operátor NOT). Postupně tedy dostáváme ohodnocení 4, 3, 3, 3 a 2. Seřazení pak provedeme podle klesající hodnoty ohodnocení. Ačkoliv to není příliš oslňující, jde přeci jenom o rozumný kompromis.

Co ale s dokumenty, které se dostaly na výstup, ale neodpovídají našim představám? Některé DIS umožňují nechat tazatele vybrat z výsledné množiny dokumenty, které považuje za relevantní, a na základě toho upravit dotaz, který je složený z termů odpovídajících označeným dokumentům.

Booleovský model má několik dalších nevýhod. Asi největší z nich je skutečnost, že pro některé dotazy dostaneme naprosto neočekávané dokumenty. Další je ta, že pokud uvedeme dotaz typu A\ and\ B\ and\ C\ and\ D\ and\ E\ and\ F, pak se na výstup nedostanou ty dokumenty, které obsahují pouze termy A, B, C, D a E. To je sice správně, ale v praxi se dost často stává, že i tyto dokumenty mohou být pro uživatele relevantní. Podobně při dotazu typu A\ or\ B\ or\ C\ or\ D\ or\ E\ or\ F jsou dokumenty stejně relevantní, obsahují-li pouze term A nebo všechny uvedené.

Zajímavý pokus provedli pánové Blair a Maron v roce 1985. Na cca 40 000 právnických dokumentech v DIS STAIRS studovali závislost hodnot P a R. Průměrné hodnoty byly pro P rovny 80 %, kdežto pro R pouze 20 %, což je velmi žalostné, zvláště jednalo-li se o právní texty.

Vektorový model

Jestliže v předchozím odstavci jsme trošku zabředli do matematiky, zde se jí nabažíme dostatek (pokud nevíte, co to je vektor, doporučuji se podívat na středoškolskou matematiku a až pak pokračovat ve čtení).

Ve vektorovém modelu máme n dokumentů indexovaných pomocí m termů. Každý dokument je reprezentován m-rozměrným vektorem \vec d_i = [w_{i1},\dots,w_{im}] \in <0,1>^{m}. Pokud w_{i,j} = 0, pak term není v dokumentu důležitý (což ještě neznamená, že tam není!), naopak, pokud w_{i,j} = 1, je term pro dokument velmi důležitý. Indexový soubor v tomto modelu je matice D = [w_{1\dots n, 1\dots m}] \in <0,1>^{n\times m}. Dotazem je pak vektor \vec q = [q_{1},\dots,q_{m}] \in <0,1>^{m}. Pokud q_i je roven nule, pak nezáleží na tom, zda se term v dokumentu vyskytuje či nikoliv. Čím více se hodnota q_i blíží jedničce, tím více požaduji, aby term v dokumentu obsažen byl. Ještě než se dostaneme k příkladu, definujme si funkci sim, která vrací podobnost (z anglického similarity) dvou dokumentů. Její základní tvar je: sim (\vec d_i, \vec q) = \sum\limits_{k=1}^m w_{ik}q_k, což je vlastně skalární součin obou vektorů (výraz za rovnítkem si pro další použití označme jako A). A teď ke slíbenému příkladu.

Mějme dvouprvkovou množinu termů obsahující termy „pes“ a „kočka“. Dále mějme dokument d₁ osahující text „kočka leze dírou, pes oknem“, d₂ obsahující text „Jsi kočka, jsi kočka, jsi kočka, perfektne urobená“, dokument d₃ s textem „no a ti římští psy ho sjíždějí o Vánocích“ a konečně dokument d₄ s textem „Je to takovej kočkopes.“ Indexová matice by mohla vypadat takto (první sloupec značí kočku, druhý psa): $ D = \pmatrix{ 1 & 1 \cr 0.6 & 0 \cr 0 & 0.8 \cr 0.1 & 0.1 \cr } $ Snížené ohodnocení v druhém až čtvrtém řádku může být způsobeno např. tím, že termy zde nejsou v původním významu (zvíře, savec, domácí mazel), ale přesto uvedené slovo obsahují. Ptejme se tedy na všechny dokumenty, které obsahují alespoň slovo kočka s významem nejméně 0.5 a slovo pes mě nikterak nezajímá. Dotaz tedy bude ve tvaru \vec q = [0.5, 0]. Na výstup se dostanou dokumenty, které jsou s dotazem „dostatečně“ podobné. Slovo „dostatečně“ si může určit tazatel či sám systém a určuje dolní mez podobnosti. Pokud podobnost dokumentů klesne pod toto číslo, nedostane se dokument do výsledné množiny (které to budou v našem příkladě si jistě laskavý čtenář již dopočítá sám v rámci domácího cvičení).

Díky funkci sim odbouráváme jeden z největších problémů booleovského DIS, totiž řazení dokumentů ve výsledku. To je zde prováděno sestupně podle výsledku této funkce.

V uvedeném příkladě jsem trošku podváděl. Ohodnocení dokumentu vektorem je ve skutečnosti ovlivněno i počtem výskytů termu v dokumentu. Pokud se v jednom dokumentu term vyskytuje vícekrát, bude i vektor delší. To se ovšem může špatně projevit na výsledku. Pokud je jeden dokument desetkrát delší než druhý a v prvním je deset výskytů termu oproti druhému, ve kterém je jedno slovo, přesto můžeme říct, že dokumenty jsou vzhledem k danému termu stejně relevantní. Tento problém se řeší dvěma způsoby. První je v úpravě funkce podobnosti. Ta pak může nabývat jednoho z následujících tvarů (samozřejmě lze tyto dále rozšiřovat): $ sim (\vec d_i, \vec q) = \frac{A}{\sum­\limits_{k=1}^m w_{i,k}+\sum\­limits_{k=1}^m q_k} $ $ sim (\vec d_i, \vec q) = \frac{A}{\sum­\limits_{k=1}^m w_{i,k}+\sum\­limits_{k=1}^m q_k – 2A} $ $ sim (\vec d_i, \vec q) = \frac{A}{\sqr­t{\sum\limits_{k=1}^m (w_{i,k})^2*\­sum\limits_{k=1}^m (q_k)^2}} $

Druhým způsobem je normalizace vektorů dokumentů na jednotkovou velikost. Pak jednotlivé vektory nejsou v m-dimenzionální krychli o velikosti 1 (viz obrázek Obrázek 1), ale leží na jednotkové m-dimenzionální sféře (viz obrázek Obrázek 2). Výpočet normalizovaných vektorů je velmi jednoduchý: $ \vec{d_i} = \frac{\vec{d_­i}}{|\vec{d_i}|} $

Jak bylo řečeno na začátku, dotazem je vektor, ve kterém tazatel specifikuje důležitost jednotlivých termů. Z již napsaného textu ale plyne, že ve vektorovém modelu nelze zadávat to, zda term v dokumentu může být či nikoliv. Stejně tak nelze provést konjunkci či disjunkci. To by nemělo ve většině případů vadit, protože na výstup se řadí dokumenty od nejvyšší podobnosti. Přesto lze některé termy ještě více znevýhodnit. Dosáhne se toho umožněním zadávat zápornou váhu termů v dotazu následujícím způsobem: \vec q = [q_{1},\dots,q_{m}] \in ← 1,1>^{m}.

Vypořádání se s kritériem predikce je řešeno úpravou jednotlivých vah v dotazu. Tazatel vybere dokumenty, které považuje za relevantní (označme je d_{i_{1}}, d_{i_{2}},\ld­ots,d_{i_{j}}), a systém vypočte nový dotaz. Výpočet vlastně spočívá v posunutí původního vektoru směrem k těžišti vybraných dokumentů: $ \vec{q} = \alpha\vec{q} + (1-\alpha)\frac{\s­um\limits_{k=1}^{j}\­vec{d_{i_{k}}}}{j} $ kde \alpha\in<0,1> je parametr. Nově vypočítaný dotaz posune původní o (1-\alpha)násobek vzdálenosti směrem k těžišti tazatelem vybraných dokumentů. Je zřejmé, že pokud je \alpha = 1, pak dostaneme původní dotaz, je-li \alpha = 0, bude nový dotaz přímo v těžišti.

Podobně jako u booleovského modelu, i v tomto je potřeba provést indexaci. S tím souvisí pojem frekvence termu (značíme TF — term frequency), která je určena podílem počtu výskytů termu t_i v dokumentu d_j a celkového počtu termů v dokumentu. Z uvedeného plyne, že TF je z intervalu <0,1>. Protože pro běžné dokumenty jsou hodnoty TF velmi malé, zavádí se tzv. normalizovaná frekvence termu (NTF — normalized term frequency). Zápis vzorce pro výpočet NTF je poměrně odpudivý, proto jej zde nebudu uvádět a zájemce odkáži na adresu, která zde byla zmíněna posledně.

Tazatel ne vždy odhadne ten nejsprávnější term (viz kritérium predikce) a přesto je možné na výstupu uvést relativní dokumenty. Kromě lemmatizátoru a tezauru, o kterých již byla řeč, je ve vektorových modelech zaváděna matice podobnosti termů TT (Term-Term): $ TT = \pmatrix{ tt_{1,1} & \dots & tt_{1,m} \cr \vdots & \ddots & \vdots \cr tt_{m,1} & \dots & tt_{m,m} \cr } \in <0,1>^{m\times m} $ Prvky tt určují, nakolik si jsou termy t_i a t_j podobné. Je vidět, že matice je symetrická a proto stačí ukládat pouze hodnoty nad či pod diagonálou (hodnoty na diagonále jsou vždy rovny jedné). Před vyhodnocováním dotazu se pak tento jednoduše upraví: q = qTT^T. Tímto výpočtem se do dotazu dostanou i ty termy, které sice uživatel nezadal, ale na základě podobnosti termů jsou i tyto relevantní.

Častým jevem, známým hlavně na webu, ale i v akademických textech, jsou odkazy a citace na jiné dokumenty. V některých případech je vhodné, aby spolu s odkazem na nalezený dokument na výstup byly zařazeny i ty, na které se nalezený odkazuje. Nejprve si ale uveďme několik definic.

• Mezi dokumenty A a B existuje přímá reference, pokud dokument A cituje dokument B. Značíme A\rightarrow B
• Mezi dokumenty A a B existuje nepřímá reference, pokud existují dokumenty C₁,\ldots,C_k ta­kové, že A\rightarrow C₁ \rightarrow \dots \rightarrow C_k\rightarrow B.
• Dokumenty A a B jsou bibliograficky párovány, pokud existuje dokument C takový, že A\rightarrow C\ \&\ B\rightarrow C.
• Dokumenty A a B jsou spolu v kocitačním vztahu, pokud existuje dokument C takový, že C\rightarrow A\ \&\ C\rightarrow B.
• Mezi dokumenty A a B existuje spojení, pokud buď A\rightarrow B, nebo B\rightarrow A.

Nyní lze vytvořit jednotlivé incidenční matice velikosti n\times n podle následujících pravidel (BP = bibliografické párování, KP = kocitační párování a SP = spojení):

• BP_{ij} = počet dokumentů citovaných jak v d_i, tak v d_j pro (i <> j).
• BP_{ij} = počet všech citací v dokumentu d_i pro i = j.
• KP_{ij} = počet všech dokumentů, které citují jak d_i, tak d_j pro i<>j.
• KP_{ij} = počet všech dokumentů, které citují dokument d_i pro i=j
• SP_{ij} = 1 pro (i <> j) a současně d_i\rightarrow d_j nebo d_j\rightarrow d_i.
• SP_{ij} = 1 pro (i = j).
• SP_{ij} = 0 jinak.

Uvedené matice lze pak s výhodou používat při úpravách výpočtu podobnosti dotazu a jednotlivých dokumentů.

Fuzzy booleovský model

Nevýhody použití booleovského modelu může odstranit zavedení fuzzy logiky (viz zde). Každému dokumentu je pak podobně jako ve vektorovém modelu přiřazen m-rozměrný vektor, kde každá složka určuje důležitost termu v daném dokumentu. Dotaz je pak tvořen stejně jako v klasickém booleovském modelu, pouze je možné ke každému termu dodat jeho váhu, např.: $Microsoft\ and\ (Word\ (0.5)\ or\ Excel\ (0.3))$

Při vyhodnocování dotazu se rozlišuje konjunkce a disjunkce. Při použití operátoru OR (disjunkce) se bere v potaz vzdálenost dokumentu od nulového vektoru (tedy od počátku) a v případě operátoru AND (konjunkce) se bere v potaz vzdálenost od jednotkového vektoru.

Tento model tedy spojuje jisté výhody a odbourává některé nevýhody obou uvedených modelů.

Místo závěru

Z uvedeného textu vyplývá, že vektorové modely jsou z pohledu výsledku přínosnější než booleovské. To, že booleovské jsou přesto stále nejpoužívanější, ovlivňuje skutečnost, že jejich implementace je relativně velmi jednoduchá a přímočará.

Je jasné, že existují i další modely dokumentrogra­fických informačních systémů (jmenujme alespoň induktivní model). Za smínku také stojí signaturové informační systémy, které slouží jako předstupeň pro oba dnes představené v případě velkého množství dokumentů.

Tématem DIS bychom se mohli zabývat ještě dlouho, ale myslím si, že pro základní představu bylo učiněno dosti. Jen doufám, že dnešním povídáním jsem neznechutil antimatematicky zaměřené čtenáře. Opravdu to nebylo mým záměrem.