Tabule (datová struktura)

Tabule (v angl. Blackboard) je v informatice datová struktura používaná především v aplikacích umělé inteligence. Datová struktura tabule byla vytvořena pro účely řešení komplexních problémů, kde výsledné řešení spočívalo v součtu částečných řešení. Pro tabuli je typický distribuovaný výpočet.

Metafora tabule

Datová struktura tabule byla navržena o mnoho dříve než byla uvedena v praxi. Již v 60. letech navrhoval Allen Newell, aby systémy pro řešení problémů využívaly nějakou architekturu se společnou datovou strukturou. Popsal to metaforou se skutečnou tabulí:

Představme si skupinu expertů, kteří se snaží vyřešit nějaký komplexní problém s využitím běžné tabule. Experti musí spolupracovat, aby našli přijatelné řešení. Jsou schopni na tabuli psát a kreslit, mohou také některé poznatky na tabuli smazat a nahradit je novými. Mají také povoleno propojovat jednotlivé příspěvky na tabuli mezi sebou šipkami. Každý expert však může upravovat nebo přidávat příspěvky, které souvisí pouze s jeho odborností. Zároveň nemají povoleno mezi sebou komunikovat, mohou pracovat pouze s informacemi na tabuli. Problém je vyřešen ve chvíli, kdy experti vyhodnotí, že na tabuli je požadované řešení.

Historie

V praxi se tabule začala používat na začátku 70. let 20. století v projektu Hearsay-II. Cílem projektu bylo rozpoznávání řeči v přibližně reálném čase. Hearsay-II dokázal rozpoznat dotazy do databáze a odpovědět na ně. Zachycený zvukový signál byl interpretován na několika úrovních, od parametrů akustického signálu až po celé věty.

Projekt Hearsay-II byl prvním implementovaným systémem typu tabule a vznikl jako součást většího výzkumného projektu ARPA. Využití této architektury začalo být populární a na projekt Hearsay-II navázal systém HASP/SIAP. Jeho úkolem bylo provádět průzkum oceánu. Systém sbíral sonarové signály a snažil se rozpoznat lodě a ponorky, které tyto signály vytvářely.

Dalším příkladem je expertní systém Crysalis, který vznikl v 80. letech 20. století. Jeho úlohou bylo zkoumání trojrozměrné molekulární struktury proteinů.

V moderních systémech se spíše setkáme s vývojově novější datovou strukturou, kterou je Tuple space (někdy též „nástěnka“). Tuple space je abstraktní, globální a datově nezávislá struktura, která je založena na podobném principu jako tabule. Datové elementy, které se vkládají do nástěnky, se nazývají n-tice (v angl. tuple). Každý z paralelně běžících procesů může přistupovat k n-ticím v nástěnce. Každý prvek n-tice má jako atribut datový typ. Tento typ musí odpovídat některému z datových typů, definovaných v hostitelském programovacím jazyce.

Implementaci struktury Tuple space můžeme najít v programovacích jazycích Java (JavaSpaces), Lisp, Python, Ruby, Smalltalk, .NET framework a dalších.

Definice tabule

Datová struktura tabule je globální struktura, která se skládá z množiny objektů {d₁, … , d_j}. Objekty jsou předdefinované objektové datové typy, které obsahují jednu a více hodnot. Původní systémy typu tabule ze 70. let používaly pro objekty termín příspěvky.

Vrstvy tabule a struktura objektů

Tabule má obvykle formu globální databáze, která zprostředkovává komunikaci mezi komponentami systému a zároveň poskytuje sdílené prostředí pro ukládání dat. Systémy, které takovou strukturu využívají jsou zejména expertní systémy určené pro řešení různých problémů. Všechny aktivity, které se podílejí na řešení problému jsou centralizovány okolo tabule.

Tabule se tedy chová jako rozhraní pro komponenty, dovoluje jim číst data týkající se problému a modifikovat je, pokud je to potřeba. Postupným zlepšováním vzniká řešení daného problému.

Části řešení se zaznamenávají formou zmíněných objektů. Objekt je tedy komplexní datová struktura, mohou to být vstupní data, částečná řešení, alternativní data či finální řešení. Objekty na tabuli jsou hierarchicky uspořádány do vrstev, které představují různé stupně abstrakce. O transformaci informací mezi jednotlivými vrstvami se starají speciální zdroje znalostí využívající algoritmické procedury nebo heuristická pravidla pro provádějí transformací.

Objekty mohou mít mnoho atributů, které definují slovník prostoru řešení. Každá vrstva tabule využívá různou podmnožinu termínů, které se mohou překrývat (např. „typ“). Vztahy mezi objekty jsou označovány pojmenovanými odkazy. Tento vztah je speciálním případem atributu. Vztah mezi objekty může existovat na různých vrstvách (např. „je-část“) nebo mezi objekty stejné vrstvy (např. „závisí-na“ či „soused“)

Architektura typu tabule

Architektura typu tabule (v angl.Blackboard Architecture) je softwarovou interpretací již zmíněné metafory. Základní struktura a chování systému využívající tuto architekturu ho odlišuje od ostatních systémů pro řešení problémů. Uplatnění této architektury nalezneme v např. v hybridních expertních systémech.

Základní komponenty systému typu tabule

Abychom mohli říci, že systém využívá architekturu typu tabule, musí obsahovat následující tři principiální komponenty:

• Centrální, globálně přístupnou, hierarchicky organizovanou databázi, kterou nazveme tabule. Databáze obsahuje výsledky procesu řešení problému;
• množinu zdrojů znalostí, které reprezentují znalosti systému pro řešení problému;
• kontrolní mechanismus nazývaný plánovač, který implementuje strategie řešení problému. Analyzuje stav řešení a přiděluje prostor odpovídajícím zdrojům znalostí.

Komponenty

Globální databáze

Databáze je organizována lineárně do vrstev, které představují různé stupně abstrakce. Každá úroveň abstrakce vidí řešený problém z jiného úhlu pohledu.

Síla architektury typu tabule tkví v kombinování různých zdrojů znalostí. Snaží se maximalizovat výhody systému založeném na pravidlech a systému založeném na modelu. Různé zdroje znalostí jsou však zároveň hlavním problémem, neboť komunikace probíhá pouze prostřednictvím tabule. Zdroje nemají žádný formální jazyk.

Zdroje znalostí

Zdroje znalostí představují poznatky systému, které jsou využívány k řešení problémů. Struktura zdroje znalostí je obvykle tvořena dvěma částmi: podmínkami a akcemi. Podmínky popisují okolnosti, za kterých zdroj znalostí může přispět k řešení problému. Akce pak upravují stav tabule. Podmínka obvykle vyžaduje existenci již dříve vygenerovaných příspěvků a je možné se na ni dívat jako na predikát příspěvků. Akce generuje nové příspěvky, které jsou určené k publikování na tabuli, nebo pouze modifikuje existující.

Struktura zdroje znalostí napovídá, že pracuje dvoustupňově:

1. Spuštění, při kterém je vyhodnocena podmínka
2. Vykonání akce, při kterém je provedena akce měnící obsah tabule

Kontrolní mechanismus

Kontrolní mechanismus určuje směr, jakým se bude ubírat proces řešení problému. Umožňuje zdrojům znalostí, aby oportunisticky měnily obsah tabule. Při typickém zpracování se při aktualizaci tabule zdrojem znalostí vygenerují události, které jsou zároveň zaznamenány. Jakmile zdroj znalostí skončí s úpravou příspěvků na tabuli, kontrolní mechanismus použije zaznamenané události pro aktivaci dalšího zdroje znalostí.

Oportunistické usuzování

Ve znalostních systémech, které slouží k řešení problémů se využívá inteligentního usuzování. Architektura typu tabule je příkladem implementace tzv. oportunistického usuzování (v angl. Opportunistic reasoning). Znalosti jsou aplikovány v nejpříhodnější době nejvhodnějším způsobem, není tedy použito výlučně přímé nebo zpětné usuzování. Tím se liší od metod striktního přímého nebo zpětného usuzování. Metoda usuzování je volena dynamicky v závislosti na tom, co systém naposledy zjistil. Tato forma usuzování je vhodná v aplikacích, kde znalosti o řešení problémů mohou být rozčleněny do nezávislých modulů, které pak při řešení problému kooperují.

Workflow tvorby řešení na tabuli

1. Zdroj znalostí provádí změnu(y) na tabuli. V oblasti řídících dat je zároveň vytvořen záznam o změnách.
2. Každý zdroj znalostí zkoumá relevantní informace na tabuli. Kontrolnímu mechanismu pak navrhuje, které akce by mohl provést.
3. Kontrolní mechanismus zkoumá informace z předchozích dvou kroků a určuje, na co je třeba se zaměřit.
4. V závislosti na vybraných informacích vybere plánovač zdroj znalostí a přísp tabule. Systém se vrací na krok 1.
5. Kritéria ukončení jsou zajišťována při vytváření systému. Obvykle jsou zabudována do jednoho ze zdrojů znalostí.

Výhody a nevýhody použití architektury typu tabule

Využití datové struktury tabule je vhodné pro diverzifikované problémy (různé formy vstupních dat, nejasně definované cíle, použití mnohonásobných linií uvažování) a pro distribuovaná prostředí. Pro efektivní využití možností tabule je dobré, aby prostor řešení byl rozložitelný na menší oddělené části. Tabule je také výhodná pro problémy, které vyžadují různé formy přístupu k řešení, jako je usuzování zdola-nahoru (bottom-up) nebo shora-dolu (top-down) .

Přehled převzat z

Výhody
Flexibilní konfigurace	Zdroje znalostí v rámci systému typu tabule nejsou pevně propojeny. Namísto toho komunikují prostřednictvím sdílené tabule. Znamená to, že systém může být snadno rozšířen o další zdroj znalostí bez rozsáhlých změn v ostatních zdrojích znalostí.
Flexibilní řešení problémů	Architektura typu tabule je nezávislá na řešení konkrétního typu problému, proto může být využita jako základ mnoha aplikací, od plánování cesty, zpracování obrázků, přes rozpoznávání řeči až po diagnostiku. Spolupráce zdrojů znalostí je založena na aktuálním stavu řešení problému na tabuli.
Výběr zdrojů znalostí	Vzhledem k tomu, že více zdrojů může být schopno vykonávat stejnou akci najednou, je k dispozici plánovač, který určí zdroj s nejvyšším potenciálem přispět na vznikajícím řešení.
Více řešitelů	Na výsledném řešení se podílí několik zdrojů znalostí. Každý z nich má potenciálně jiné znalosti a inferenční mechanismus.
Několik vrstev abstrakce	Tabule je hierarchicky rozdělena do několika vrstev abstrakce. Řešení problému na více abstraktních úrovních přináší efektivní proces tvorby řešení. O management informací na různých vrstvách se starají speciální znalostní zdroje.
Nevýhody
Chybějící komunikační jazyk	Zdroje znalostí komunikují prostřednictvím objektů na tabuli, což nemusí být nejvýhodnější.
Výpočetní složitost spolupráce	Zjištění, který zdroj znalostí je v danou chvíli vhodný musí být vyhodnoceno v každé iteraci programu, což je výpočetně velmi náročné.
Metodika řešení úkolů	Systémy typu tabule nemají stanovenou metodiku pro určení, jak by se mělo k řešení problému přistoupit. Vychází to z podstaty těchto systémů, které jsou nezávislé na povaze problému.
Globální databáze	Předpokladem systému je odpovědnost chování zdrojů znalostí. Pokud tomu tak není, vzniká chaos v informacích.
Získávání znalostí	Získávání znalostí a jejich kodifikace může být velmi obtížný úkol. Každý zdroj znalostí obsahuje potenciálně různou reprezentaci znalostí, které mohou vyžadovat různé techniky získávání a kódování.

Oblasti využití

Přehled typů úloh, které jsou vhodné pro řešení v systému typu tabule :

• plánování
• rozpoznávání obrazu, zvuku
• případové usuzování
• znalostní simulace
• počítačové vidění
• fúze dat
• diagnostika

Struktura tabule

Strukturu částečných řešení, která vznikají na tabuli si demonstrujeme na následujícím příkladu. V roce 1979 představili Makoto Nagao a Takashi Mastuyama systém strukturální analýzy komplexních leteckých snímků. Při analýze uplatnili datovou strukturu tabule, která poskytovala sdílené prostředí pro rozpoznávané objekty na fotografiích.

Cílem systému bylo identifikovat a popsat objekty, které se ve fotografiích vyskytovaly. Pro efektivní rozpoznávání bylo třeba vzít v úvahu mnoho faktorů, které mají vliv na výslednou fotografii. Bylo tedy nutné specifikovat prostorové vlastnosti objektů, které zahrnovaly velikost, tvar, jas, spektrální vlastnosti, textury, prostorové vztahy atd.

Letecké snímky obsahovaly množství objektů jako jsou pole, lesy, travnaté plochy, domy, řeky, silnice a mnoho dalších. Vzhledem k diverzifikované povaze problému rozpoznávání povrchu země, bylo na místě rozdělení systému na subsystémy, které se zaměřily na specifickou doménu objektů.

Tyto subsystémy využívaly společnou databázi, tedy tabuli, pro zápis částečných výsledků. Na obrázku je zobrazena struktura tabule v systému. Tabule obsahuje globální parametry stejně jako vlastnosti oblastí a objektů.

Praktický příklad

Máme k dispozici ukázkovou sadu pravidel a faktů:

R1: IF živočich dává mléko pak živočich je savec
R2: IF živočich jí maso pak živočich je masožravec
R3: IF živočich je savec a živočich je masožravec a živočich má zlatavou barvu a živočich má černé pruhy pak živočich je tygr

F1: živočich jí maso
F2: živočich dává mléko
F3: živočich má černé pruhy
F4: živočich má zlatavou barvu

Cílem je rozpoznat živočicha. Všechny poznatky jsou umístěny na tabuli a všechny znalosti jsou uloženy do zdrojů znalostí. Mohou být použity různé modely usuzování, např. dopředné či zpětné usuzování. Podívejme se, jak by se postupovalo při dopředném usuzování. Poznatek F1 splňuje podmínku R2, tudíž hypotéza „živočich je masožravec“ je odvozena a uložena na tabuli. Algoritmus zkontroluje nejnovější vygenerovaná data, pokud nesplňují žádnou podmínku, pokračuje a vyhodnotí poznatek F2, který splňuje podmínku R1. Hypotéza „živočich je savec“ je uložena na tabuli. Další poznatky nesplňují žádnou podmínku, a je proto vyhodnocena jejich kombinace, která přinese výsledek „živočich je tygr“.

Odkazy

Související články

• Expertní systém
• Oportunistické usuzování