Hugin Expert

Hugin je technológia pre vývoj expertných systémov pre podporu rozhodovania založených na bayesovských sieťach, vyvinutá na dánskej univerzite v Aalborgu a v súčasnosti vyvíjaná a poskytovaná spoločnosťou Hugin Expert A/S. K dispozícii sú aj voľne šíriteľné demoverzie, určené iba na ohodnotenie produktu.

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.

Všeobecné informácie

Komponenty

Systém Hugin a jeho jadro – Hugin Development Environment (vývojové prostredie Hugin) sa skladá z troch hlavných komponentov:

• Hugin Graphical User Interface (grafické používateľské rozhranie, GUI)
• Hugin Decision Engine (rozhodovací engine, HDE)
• Hugin Application Program Interfaces (aplikačné programové rozhrania, APIs)

Hugin GUI je rozhranie pre tvorbu a úpravu sieťových modelov a ich vykonávanie pomocou zadania faktov a zobrazenia výsledných rozdelení pravdepodobnosti a očakávaných využití. V editovacom móde modul umožňuje definovať siete pomocou vkladania uzlov, ich spájania, definovania stavov a akcií a tiež tabuliek podmienených pravdepodobností a využití (angl. conditional probability tables and utility tables). V móde behu umožňuje zobrazenie domnienok (angl. beliefs) a využití pre jednotlivé uzly, zadanie faktov pre jednotlivé stavy alebo akcie a spustenie HDE pre získanie revidovaných pravdepodobností a očakávaných využití.

Hugin Decision Engine (HDE) je jadrom systému, ktoré vykonáva odvodzovania na báze dát reprezentovanej bayesovskou sieťou alebo diagramom vplyvu. Systém umožňuje konštrukciu, údržbu a používanie báz znalostí za použitia bayesovských sietí, objektovo orientovaných bayesovských sietí a diagramov vplyvu, automatizované učenie báz znalostí, štruktúry a parametrov bayesovských sietí z dát. Systém umožňuje využitie ako diskrétnych, tak aj spojitých premenných, priame definovanie rozdelení podmienenej pravdepodobnosti, využitie generátora tabuliek na definovanie vzťahov a pomocných funkcií matematickými a logickými opismi, atď.

Hugin APIs sú rozhrania umožňujúce tvorbu znalostných aplikácií pomocou prepojenia na HDE, ktoré poskytuje služby odvodzovania nad bázou znalostí. APIs sú poskytované ako knižnice v jazykoch C, C++, Java a ako ActiveX server pre jazyky ako napr. Visual Basic.

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.

Komerčné produkty

• Hugin Developer – balík pre tvorbu pokročilých aplikácií a služieb expertných systémov, obsahuje grafické používateľské rozhranie (GUI) pre návrh sietí, Hugin Decision Engine pre odvodzovanie, štyri API na prepojenie s externými aplikáciami (podpora pre jazyky C, C++, Java a ActiveX server, napr. pre Visual Basic) a ukážkové bázy znalostí z rôznych oblastí.
• Hugin Explorer – zjednodušená verzia Hugin Developera, s HDE a GUI, avšak bez APIs na ďalší vývoj softvéru.
• Hugin OEM – špeciálne riešenia na mieru zákazníka pre zahrnutie v jeho produktoch alebo službách.
• Hugin Dezide Advisor – technológia pre tvorbu a nasadenie riešení pre troubleshooting, aplikovateľný v službách call centier, diagnostiky procesov, pri službách helpdeskov, online poradenstva, výučby a iných.
• Hugin Clementine Link – možnosť na kombinovanie HDE, ktoré poskytuje možnosti štrukturálneho a parametrického učenia, s dolovaním v dátach prostredníctvom systému Clementine od spoločnosti SPSS.

Akademické využitie

• Hugin Researcher – ekvivalent Hugin Developera pre akademický sektor, obsahuje GUI, HDE a APIs
• Hugin Educational – ekvivalent Hugin Explorera
• Hugin Classroom – viacpoužívateľská licencia pre výučbu, avšak limitovaná na 200 stavov a 500 prípadov učenia.

Skúšobné verzie

• Hugin Lite - ekvivalent Hugin Developer/Researcher obsahujúci GUI, HDE a APIs spolu s knižnicou ukážkových báz znalostí. Obmedzenia zahŕňajú max. 50 stavov a učenie z max. 500 prípadov. Tiež je jeho použitie licenčne obmedzené iba na účely demonštrácie možností a skúšky konceptu.
• Dezide Advisor Evaluation – limitovaná verzia produktu Dezide Advisor s dostatkom funkcionality na demonštrovanie možností a sily tejto technológie.

Systémové požiadavky

Systémy Hugin sú multiplatformové aplikácie, ktoré je možné spustiť na operačných systémoch Windows, Solaris, Linux a Mac OS. Požiadavky pre jednotlivé systémy sú nasledovné:

• Windows – Windows 2000/XP, Intel Pentium II/Pro al. novší, AMD Athlon
• Solaris - Solaris 8, 9 (Sun UltraSPARC), 10, Sun UltraSPARC CPU, Intel Pentium II/Pro al. novší, AMD Athlon
• Linux – Redhat Enterprise 4, Intel Pentium II/Pro al. novší, AMD Athlon
• Mac - Mac OS X v10.3 (iba pre procesory G4 a G5), Mac OS X v10.4, G4 al. G5 CPU, prípadne platforma Intel

Pre všetky systémy sú spoločné pamäťové nároky: min. 256 MB RAM, odporúča sa min. 512 MB. Pre všetky operačné systémy je tiež spoločná podpora multiprocesorových systémov. Systém Hugin je multiplatformový a v prípade špeciálnych požiadaviek ho vie spoločnosť portovať aj na iné platformy.

Demoverzie Hugin Lite a Dezide Advisor sú k dispozícii iba pre Windows.

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.