Hugin Expert

História

Systém Hugin je vyvíjaný spoločnosťou Hugin Expert A/S založenou v roku 1989 v Dánskom meste Aalborg. Firma bola založená ako komerčné pokračovanie univerzitného výskumného projektu zameraného na vývoj znalostného systému pre podporu medicínskych diagnóz, konkrétne diagnóz svalových a nervových chorôb. Pre tento projekt podporovaný Európskou úniou bola vytvorená bayesovská sieť MUNIN, avšak počas vývoja efektívnych výpočtových metód na riešenie problému diagnostiky sa narazilo na tzv. „rumor problem“. Rumor problem (v slovenskom preklade „problém klebiet“) vzniká v bayesovskej sieti vtedy, keď jedna príčina ovplyvní rovnakú udalosť prostredníctvom viacerých odlišných ciest v sieti. Problém sa úspešne podarilo vyriešiť a výsledné metódy boli implementované do systému Hugin, ktorý sa stal vhodným základom expertných systémov s použitím bayesovských sietí.
Meno Hugin vychádza z nordickej mytológie, kde Huginn a Muninn sú dva havrany najvyššieho boha škandinávskej mytológie, boha múdrosti, poézie, poľnohospodárstva a vojny, ktoré cestujú po svete a získavajú pre neho správy a informácie. Huginn z tejto dvojice predstavuje inteligenciu a Muninn pamäť, oba sú zhmotnením duše Odina.

Produkty technologickej rady Hugin

Spoločnosť Hugin Expert ponúka rôzne produkty založené na technológii Hugin, závisiac od ich konkrétneho zamerania. Rozdeľujú sa do dvoch hlavných kategórií – pre komerčné využitie a pre akademickú sféru. Pre akademickú sféru sú ponúkané za výrazne nižšie ceny. Spoločnosť tiež ponúka dodatkové služby ako špeciálne balíky podpory, konzultačné služby a tréningové programy. Systém je možné tiež vyskúšať zadarmo – spoločnosť ponúka aj 2 balíky ako demoverzie.

Technológia

Znalosti sú v systéme Hugin reprezentované pomocou bayesovskej siete, objektovo orientovanej bayesovskej siete alebo diagramu vplyvu. Umožňuje tiež použitie modelov s opakujúcimi sa vzormi a hierarchických modelov. Tieto spôsoby reprezentácie znalostí umožňujú predovšetkým lepšiu čitateľnosť zložitých modelov.
Bayesovské siete sú používané na modelovanie domén, ktoré obsahujú istú mieru neurčitosti. Táto neurčitosť môže byť zapríčinená napr. nedostatočným pochopením domény, určitou mierou náhodnosti, alebo nepostačujúcou informáciou o stave domény v čase vykonávania potrebných úloh. Ku každému uzlu bayesovskej siete je priradená pravdepodobnostná funkcia, pričom sieť ako celok tvorí acyklický orientovaný graf.
Pre odvodzovanie sa v systéme využíva tzv. Hugin Decision Engine. HDE uskutočňuje všetky úkony spojené so spracovaním dát a správou pamäte. Významnou časťou HDE je kompilátor, ktorý transformuje sieť do efektívnejšej formy – tzv. spojených stromov (angl. junction trees) s cieľom veľmi efektívneho vykonávania inferencie v sieťach. Systém umožňuje zmenu rozdelení podmienených pravdepodobností, funkcií hustoty a pomocných funkcií bez novej kompilácie spojitého stromu. V malých a stredne veľkých sieťach trvá inferencia rádovo zlomky sekundy a aj vo veľkých sieťach sa zvyčajne časy pohybujú v jednotkách sekúnd. Na odvodzovanie sa využíva v zásade inteligentná aplikácia bayesovej teorémy.
Systém Hugin obsahuje údajne najpresnejší a najefektívnejší algoritmus na aktualizáciu pravdepodobností, ktorého autormi sú Steffen L. Lauritzen z univerzity v Aalborgu a David Spiegelhalter z univerzity v Cambridge a ktorý bol publikovaný v roku 1988. V roku 1989 vyhral cenu za vynikajúcu aplikáciu (angl. Outstanding Application Award) od Americkej štatistickej asociácie (angl. American Statistical Society).
Systém umožňuje tiež učenie sa ako štruktúry siete, tak aj jej parametrov zo vstupnej databázy. Pre učenie štruktúry bayesovskej siete zo vstupných dát sa využívajú algoritmy PC a NPC.
PC algoritmus je založený na obmedzeniach a odvodzuje množinu vzťahov podmienenej závislosti a nezávislosti zo štatistických testov.
NPC algoritmus (angl. Necessary Path Condition) je vylepšením PC algoritmu a opravuje jeho nevýhody. Pri PC algoritme môže dôjsť k vytvoreniu modelu, ktorý aj keď odpovedá vstupným dátam, nie je úplne logicky správny. NPC algoritmus dovoľuje vstup používateľa v prípade, že algoritmus si nie je istý a následné upravenie siete podľa jeho vstupu. Algoritmus NPC je však pomalší ako PC algoritmus, a tak pri vysokých nárokoch na čas sa stále používa PC algoritmus.
Po naučení štruktúry je možné odhadnúť rozdelenia pravdepodobností siete z dát pomocou EM algoritmu. Ten sa môže zastaviť buď po dosiahnutí maximálneho počtu iterácií alebo, ak tento ešte dosiahnutý nebol, po dosiahnutí požadovanej presnosti. Pre jednoduchšie definovanie učenia používateľom systém obsahuje sprievodcov učením (angl. learning wizards).
Vrcholy môžu byť diskrétne aj spojité a ich tabuľky podmienených pravdepodobností môžu byť definované priamo manuálnym zadaním hodnôt alebo definovaním pomocou matematických výrazov.
Systém umožňuje adaptáciu parametrov definovanej alebo naučenej siete pomocou dodatočných dát získaných napr. z vykonaných reálnych experimentov. Adaptácia sa vykonáva pomocou tzv. tabuliek skúseností (angl. experience tables) a/alebo slabnúce tabuľky (angl. fading tables). Tabuľky skúseností obsahujú počty prípadov, ktoré sa v praxi vyskytli pre danú premennú (uzol). Slabnúce tabuľky navyše zohľadňujú aj čas, kedy sa prípad v praxi vyskytol a umožňujú sieti odučiť sa dávne prípady a dávať dôraz predovšetkým na nedávny výskyt udalostí. Do úvahy sa berie tzv. faktor slabnutia, ktorý definuje tempo, akým sa oslabujú staršie fakty.
Odvodzovanie v bayesovských sieťach a v diagramoch vplyvu sa nevykonáva nad nimi samotnými, ale nad tzv. spojeným stromom (angl. junction tree). Systém umožňuje jeho zobrazenie a úpravu a tiež použiť ho na riešenie konfliktov v sieti. Strom sa generuje automaticky v momente kompilácie siete pomocou krokov moralizácie a triangulácie. V procese moralizácie sa konvertujú orientované hrany siete na neorientované a v kroku triangulácie sa do výsledného grafu pridávajú ďalšie neorientované hrany tak, aby sa získal tzv. triangulovaný (chordálny, triangular, chordal) graf – neobsahujúci iné cykly ako max. dĺžky 3. Následne sa za uzly výsledného spojeného stromu považujú uzavreté komponenty – podgrafy – triangulovaného grafu. Nájdenie optimálneho spojitého stromu pre sieť je však NP ťažký problém, pretože je NP ťažké optimálne triangulovať graf. Systém Hugin umožňuje vybrať z viacerých bežných heuristických spôsobov triangulácie, ktoré však môžu viesť k nie úplne optimálnemu výsledku. Systém sa však vyznačuje špeciálnou metódou pre optimálnu trianguláciu založenou na hľadaní minimálnych separátorov v strome, ktorá vedie k spojeným stromom s podstatne menšou zložitosťou ako bežné metódy.
Pri kompilácii je možné okrem vytvorenia spojených stromov uskutočniť aj ďalšie optimalizácie ako kompresiu a kompresiu s aproximáciou. Kompresia nemá za následok zníženie presnosti, avšak pri aproximácii k nemu dôjsť môže, aj keď reálne je táto hodnota zanedbateľná a v systéme konfigurovateľná. Kompresia optimalizuje vnútornú reprezentáciu tabuliek a najlepšie výsledky sa dosahujú pri veľkom počte nulových pravdepodobností premenných. Aproximácia funguje prostredníctvom eliminácie najmenších hodnôt z tabuliek vnútornej reprezentácie siete tým, že sa ich pravdepodobnosť vynuluje. Následne bude kompresia efektívnejšia. Systém umožňuje nastaviť hranicu, pod ktorou sa budú hodnoty eliminovať. Táto metóda však môže viesť ku konfliktom v sieti.
Inferencia v systéme Hugin sa vykonáva nad spojeným stromom prostredníctvom predávania správ. Správy sa predávajú v dvoch fázach – od listov ku koreňu a od koreňa k listom. Správy medzi skupinami (uzlami spojeného stromu) obsahujú marginálnu tabuľku cez uzly obsiahnuté v oboch susedných skupinách. Marginálna tabuľka zo skupiny C pre skupinu D sa počíta z tabuľky skupiny C elimináciou tých dimenzií, ktoré sa nenachádzajú v tabuľke pre D. Pri bežnom odvodzovaní sa táto eliminácia vykonáva sumáciou. Pri získavaní najpravdepodobnejšej konfigurácie v sieti sa využíva eliminácia prostredníctvom maximalizácie.

Určenie systému

Systém je určený na konštrukciu komponentov pre aplikácie zamerané na podporu rozhodovania, dolovania v dátach a expertné systémy. Je možné pomocou neho konštruovať systémy založené na modeloch bayesovských sietí a ich rozšírení – diagramoch vplyvu – pre systémy pre domény charakterizované prirodzenou neurčitosťou. Modely môžu využívať ako diskrétne, tak aj spojité doménové premenné a môžu byť tiež založené na objektových princípoch. Systémy postavené na technológií Hugin sú primárne určené na odvodzovanie z nemenných báz znalostí, avšak je umožnená aj ich adaptácia prostredníctvom dodatočne získaných dát. Nie sú však efektívne využiteľné pre bázy dát meniace sa v reálnom čase.