Hlavní navigace

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

Karel Pánek 13. 2. 2002

Tato poslední kapitole věnované teoretickému pozadí vyhledávacích strojů se zabývá rozšířeným boolským modelem (RBM). Mezi jeho reprezentanty, avšak s částečně atypickou implementací, můžeme počítat takové stroje, jako je např. WebFast nebo různé vyhledávače s databázovým základem (například via SQL).

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 wi,j, kterou jsme představili u vektorového modelu. Dokument dj je pak reprezentován jako vektor (nebo bod) se složkami (w1,j, w2,j, … wt,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).

582

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( x2 + y2 ) / 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)2 + (1-y)2 ) / 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) = (( xp + yp ) / 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=mc2.)

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 = (x1, x2, … xt)

pak formule pro OR vypadá takto:

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

Obdobně pro AND

sim(X AND Y, d) = 1 – ( sum(i=1..t; (1-xi)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í xi 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.

Anketa

Přáli byste si na českém Internetu implementaci rozšířeného boolského modelu?

Našli jste v článku chybu?

20. 2. 2002 3:16

k.p. (neregistrovaný)
Prosim, vratme se na zacatek, nebot se vzdalujeme nejen sami sobe, ale i od podstatneho. Oboji je dle meho nazoru chybou.

Zacal jste srovnavat kod a kompresni algoritmus. Musim trvat na tom, ze srovnavate neporovnatelne hodnoty z rozlicnych definicnich oboru, a v tomto kontextu byste mel svuj vyrok upravit nebo zpresnit.

pozn.: podle vyzkumu Moffata a Zobela je vhodnejsi implementovat Golomb kody, protoze zlepseni spojene s jinymi kody je nad invertovanymi seznamy zanedbatelne.

Puvodne …





19. 2. 2002 22:59

Michal Illich (neregistrovaný)
> V ostatnim jste se stal obeti vlastniho omylu, protoze Golomb nelze porovnavat s kompresnimi algoritmy jakymi je napr. aritmeticke ci huffmanovo. Jde ve sve podstate jen o formu zapisu integer cisel a vase vyroky jsou v teto oblasti

Vzdyt huffmanovo kodovani i aritmeticke kodovani je take jen "forma zapisu integer cisel"... rozdil mezi Golombem a zminenymi algoritmy je v tom, ze ty, o kterych mluvim ja, jsou daleko obecnejsi, Golomb je v podstate pravidelny Huffman pro geometr…

Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

DigiZone.cz: Recenze Westworld: zavraždit a...

Recenze Westworld: zavraždit a...

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

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

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Podnikatel.cz: Udávání a účtenková loterie, hloupá komedie

Udávání a účtenková loterie, hloupá komedie

Vitalia.cz: Dáte si jahody s plísní?

Dáte si jahody s plísní?

DigiZone.cz: Další dva kanály nabídnou HbbTV

Další dva kanály nabídnou HbbTV

Vitalia.cz: Pravda o přibírání na zimu

Pravda o přibírání na zimu

Lupa.cz: Seznam mění vedení. Pavel Zima v čele končí

Seznam mění vedení. Pavel Zima v čele končí

Podnikatel.cz: Zavře krám u #EET Malá pokladna a Teeta?

Zavře krám u #EET Malá pokladna a Teeta?

120na80.cz: Rovnátka, která nejsou vidět

Rovnátka, která nejsou vidět

Root.cz: Telegram spustil anonymní blog Telegraph

Telegram spustil anonymní blog Telegraph

Vitalia.cz: Jsou čajové sáčky toxické?

Jsou čajové sáčky toxické?

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

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

DigiZone.cz: Digi CZ výrazně zlevnila balíček HBO

Digi CZ výrazně zlevnila balíček HBO

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: Golfové pojištění: kde si jej můžete sjednat?

Golfové pojištění: kde si jej můžete sjednat?

DigiZone.cz: Milan Kruml: procházka TV historií

Milan Kruml: procházka TV historií

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

Jmenuje se Janina a žije bez cukru

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

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