Jehla v kupce sena: rozšířený boolský model

RBM byl porpvé představen již v roce 1983 (Salton, Fox, Wo) a jeho hlavním cílem bylo přidat do klasického boolského modelu jemnější funkci podobnosti dotazů a dokumentů. Klasický boolský model zná pouze ohodnocovací funkci 0–1, kde 1 znamená relevatní dokument, 0 opak. S tím lze vystačit pro získávání dat (a la unixová utilita grep), nikoliv však získávání informací. Nyní si ukážeme původní implementaci RBM.

Ta si kladla za cíl umožnit v dotazech s typicky boolskými operátory (AND, OR) práci nejen s hodnotami true, false (tedy 1, 0). Díky této vlastnosti je po vyčíslení dotazu výsledek nikoliv 0–1 jako v případě boolského modelu, ale 0 a poté více nenulových kladných ohodnocení (končících hodnotou 1).

Jak na to?

Předně už můžeme vyjít z formule tf.idf pro w_i,j, kterou jsme představili u vektorového modelu. Dokument d_j je pak reprezentován jako vektor (nebo bod) se složkami (w_1,j, w_2,j, … w_t,j). Pro jednoduchost si ale představme, že nepracujeme s mnoha slovy (termy), ale jen se dvěma (t=2). Díky tomu veškeré vektory (resp. body) můžeme uvažovat ve dvou-rozměrném prostoru.

Představme si nyní dvě možnosti. Máme dotaz typu X AND Y, nebo dotaz X OR Y, kde X a Y jsou naše jediné dva termy. Čím se liší uvedené dva dotazy? Uvažujeme-li dotaz s AND, pak je pro nás lepší ten dokument (na obrázku reprezentovaný body A a B), který je blíže bodu (1,1) (viz. obr. AND-bod). Jinými slovy, dokument s největším doplňkem vzdálenosti z (1,1). V případě OR dotazu, je zase lepší ten dokument, který je dále od bodu (0,0) (viz. obr. OR-bod).

Předpokládejme, že dokument d (respektive jeho vektor) má souřadnice (x,y). Potom spojku typu X OR Y (pochopitelně x u d odpovídá hodnotě pro term X, dtto pro y) vyhodnocujeme jako vzdálenost bodu d od OR-bodu. Aby tato podobnost vycházela vždy mezi hodnotami 0 až 1, nepoužijeme klasickou Pythagorovu větu, ale provádíme i normalizaci faktorem odmocnina ze dvou (sqrt(2)):

sim(X OR Y, d) = sqrt( x² + y² ) / sqrt( 2 )

Pro X AND Y postupujeme obdobně, ale vzdálenost, která nás zajímá je měřena od AND-bodu:

sim(X AND Y, d) = 1 – sqrt( (1-x)² + (1-y)² ) / sqrt( 2 )

Budeme-li předpokládat, že všechny hodnoty x-ů i y-nů jsou pouze boolské (tj. 0 nebo 1), pak podobnosti nabývají tří možných hodnot.

To je sice pěkné, ale můžeme jít ještě dále, a to zakomponováním p-normy. Tím zahrneme do RBM téměř vše, co jsme dosud poznali (vč. klasického vektorového modelu).

P-norma aneb dokonalé spojení

Předně je potřeba poznamenat, že tajemné p musí být známo před kalkulací podobnosti, a to buď nastavením systému nebo volbou uživatele.

Pozn.: České vyhledávače tuto techniku neimplementují, přestože by dala možnost volit mezi vektorovým, boolským nebo dokonce určitým typem fuzzy dotazů v jediném stroji nad jedním indexem. Kdyby se takový stroj v české doméně našel, zajisté by vyšel z recenze se vztyčenou hlavou a ohodnoceními vysoce nad průměrem. Je ale otázka, zda velikost českého Internetu dovoluje implementaci podobné techniky.

Dosud jsme se pohybovali ve dvourozměrném prostoru s klasickou Euklidovskou geometrií. V p-normě pak místo druhých mocnin a odmocnin používáme jejich ekvivalenty o základu p. Naše stávající formule pak vypadají takto:

sim(X OR Y, d) = (( x^p + y^p ) / 2 )^(1/p)

a

sim(X AND Y, d) = 1 – ( (1-x)^p + (1-y)^p ) / 2 )^(1/p)

Bude-li p rovno jedné, pak tyto formule degradují na formule vektorového modelu. V takovém případě je dokonce irelevantní, zda se kalkuluje AND nebo OR varianta podobnosti – z obou vychází tytéž výsledky.

Naopak v případě, kdy se p blíží nekonečnu, přechází formule na modely blízké fuzzy modelu, a to je ve svém důsledku jen zobecněný boolský model. Tím se nám teorie tak trochu sama uzavírá do zobecněného principu. (Pochopitelně se nejedná o formuli rovnající se svým významem E=mc².)

Komplikované boolské dotazy

Je zřejmé, že pro praktické situace nevystačíme jen s formulemi pro dva termy, jaké jsme ukázali výše. Přechod na více termů není ale natolik komplikovaný. Pokud je vektor

d = (x₁, x₂, … x_t)

pak formule pro OR vypadá takto:

sim(X OR Y, d) = ( sum(i=1..t; x_i^p) / t )^(1/p)

Obdobně pro AND

sim(X AND Y, d) = 1 – ( sum(i=1..t; (1-x_i)^p) / t )^(1/p)

Pro kombinované dotazy typu (X AND Y) OR Z použime nejprve vyčíslení zárorky formulemi pro AND, a tento výsledek uplatníme do OR formule jako odpovídající x_i hodnotu. Svým způsobem se jedná o triviální substituční dosazení…

Shrnutí

Zatím se nám povedlo představit dva základní reprezentanty modelů a určitý univerzální princip, který oba popisuje.

       

Z tohoto úvodu je patrné, že praktické implementace, které budeme dále popisovat, by měly zohledňovat:

• rozdílnou práci se spojkami AND a OR v dotazu
• frekvenci termů nejen v samotném dokumentu, ale i v rámci všech textů (tf.idf kalkulace)
• strukturu hypertextových odkazů (viz např. PageRank)
• a samozřejmě určité jazykové dovednosti (thesaurus, stemming), kterými jsme se zatím vůbec nezabývali

Abychom si získané znalosti ukázali na příkladech, začneme přístě pitvat jednotlivé volně dostupné fulltextové stroje jakými je např. mnoGoSearch a spol.