J E S S

Abstrakt:

Tento systém nás zaujal svojou jednoduchosťou a tým, že je celý napísaný v jazyku Java, ktorý v súčasnosti patrí medzi najmodernejšie. Ďalšou neopomenuteľnou výhodou je fakt, že je voľne dostupný včítane zdrojového textu.

Referát je po logickej stránke rozdelený do troch častí.
Prvá časť je zameraná na úvod do problematiky a popis základných charakteristík Jessu (Martin Kužela), druhá časť sa zaoberá opisom použitého Rete algoritmu (René Kuzica) a tretia je zameraná na prepojenie systému Jess s programovacím jazykom Java (Miloslav Krchniak).

Keďže pomocou tohto systému vypracovávame aj naše zadanie zo Znalostných Systémov, v referáte sme mali snahu ozrejmiť niektoré veci aj pomocou príkladov z vlastného expertného systému.

Abstract:

Kľúčové slová:

1. Úvod

Autor Jessu je Ernest J. Friedman-Hill, pracujúci pre Sandia National Laboratories.
Po skompilovaní sa Jess tvári ako skupina tried (súbory .class), združených do balíka jess. Na skompilovanie a spustenie Jessu treba mať nainštalovaný niektorý z kompilátorov a interpreterov Javy (najčastejšie JDK od firmy Sun).
Jess sa spustí po napísaní do príkazového riadku:

 java jess.Main program.clp 

2. Jazykové konštrukcie Jessu a ich použitie.

2.1 Pravidlá

Metóda rámca sa nahradí tak, že v podmienkovej časti pravidla sa nainštanciujú existujúce fakty alebo rámce. Ďalej sa už s nimi v dôsledkovej časti môžu vykonať akcie.
Príklad pravidla, ktoré zistí a uloží nový fakt o zhode dvoch počítačových komponetov. (Pravidlá sa definujú pomocou rezervovaného slova defrule):

(defrule fit-motherboard-case
    ?d <- (motherboard (type ?X))
    ?s <- (case (type ?X))
    =>
    (assert (vyhovuje ?d ?s))
)

Klasický problém, keď je potrebné vykonať pri štarte niektoré operácie, sa v Jesse rieši takto:

(deffacts st
  (command "start"))

(defrule initialize
   ?fact <- (command "start")
   =>
   (retract ?fact)
   (printout t "Nahravam" crlf)
   (load-facts "komponenty.dat")
   (printout t "Fakty nahrane" crlf)
)

2.2 Fakty

Príklad jednoduchého faktu:

(deffacts vyhovuje-fakt
  (vyhovuje pentium doska_pre_pentium)
)

(deffacts instancia-ramca
  (case (name noname1) (size MIDITOWER) (type ATX))
)

2.3 Rámce

(deftemplate case
   (slot name)
   (slot size)     ; DESKTOP SLIMLINE MIDITOWER BIGTOWER
   (slot type)     ; AT alebo ATX
)

2.4 Premenné

Príklad na priradenie do premennej pomocou funkcie bind:

(bind ?x "retazec")

(bind $?y ($create prvok1 prvok2 prvok3))

(defglobal $variable = "pociatocna hodnota")

2.5 Funkcie

Príklad funkcie, ktorá vráti FALSE, ak sa prvok v zozname nenachádza, inak vráti zoznam bez tohto prvku.

(deffunction give_memory_to_motherboard (?pamat $?volne)
  (bind ?idx (member$ ?pamat $?volne))
  if (neq ?idx FALSE)
    then (return FALSE)
    else (return (delete$ $?volne ?idx ?idx))
)

3. Ako pracuje Jess

3.1 Jess ako pravidlový expertný systém

  (defrule library-rule-1
    (book (name ?X) (status late) (borrower ?Y))
    (borrower (name ?Y) (address ?Z))
   =>
    (send-late-notice ?X ?Y ?Z))

   Library rule #1:
   If
     a late book exists, with name X, borrowed by someone named Y
   and
     that borrower's address is known to be Z
   then
     send a late notice to Y at Z about the book X.

Typický expertný systém má pevnú množinu pravidiel, zatiaľ čo báza faktov sa mení nepretržite. Avšak vo väčšine expertných systémov sa veľká časť bázy faktov z jednej pravidlovej operácie do nasledujúcej tiež nezmení. Hoci nové fakty prichádzajú a staré sú odstraňované, percento faktov, ktoré sa zmenili za jednotku času, je všeobecne dosť malé. Z toho dôvodu je zrejmá implementácia expertného systému veľmi nevýkonná.

Táto zrejmá implementácia by mala udržiavať bázu pravidiel a nepretržite cyklicky v báze overovať každú jednu ľavú stranu LHS s bázou faktov a vykonávať pravú stranu RHS akýchkoľvek pravidiel, ktoré by sa uplatnili. To je ale nevýkonné, pretože väčšina testov vykonaných v každom cykle bude mať rovnaké výsledky ako v predchádzajúcej iterácii. Hoci báza faktov je stabilná, väčšina testov bude opakovaná.
Výpočtovú zložitosť takého systému vyjarduje funkcia O(RF^P), kde R je počet pravidiel, P je priemerný počet vzoriek na LHS pravidla a F je počet faktov v báze faktov.

3.2 Výpočtová zložitosť expertných systémov

Neefektívnosť popísaná vyššie je v RETE algoritme zmiernená pamätaním si predchádzajúcich výsledkov testov v priebehu iterácie pravidlovej slučky. Iba nové fakty sú testované s každou LHS pravidla. Dodatočne, ako bude popísané ďalej, nové fakty sú testované iba s LHS pravidla, ktorému sú najviac podobné. Výsledok: výpočtová zložitosť dosahuje hodnotu niečo nad O(RFP).

RETE algoritmus je realizovaný vybudovaním siete uzlov, kde každý z nich predstavuje jeden alebo viac testov, založených na testovaní LHS pravidla.
Fakty, ktoré sú pridané alebo odobrané z bázy faktov, sú spracovávané touto sieťou uzlov. Na dne siete sú uzly reprezentujúce jednotlivé pravidlá. Keď množina faktov preniká všetkými cestami nadol ku dnu siete, musí prejsť všetky testy na LHS konkrétneho pravidla. Táto množina sa state aktivovanou. Asociované pravidlo môže mať RHS vykonanú (fired) vtedy, ak aktivovanie nie je zrušené skôr ako odstránenie jedného alebo viacerých faktov z aktivovanej množiny.

Vnútri siete sú dva druhy uzlov: jedno-vstupové a dvoj-vstupové uzly.
Jedno-vstupové uzly vykonávajú testy na jednotlivých faktoch, zatiaľ čo dvoj-vstupové uzly vykonávajú testy cez fakty a zastávajú funkciu zoskupovania. Tretím pomocným typom uzlov sú koncové uzly.

3.3 Príklad na RETE algoritmus

 (defrule example-2      (defrule example-3
    (x)                     (x)
    (y)                     (y)
    (z)                     => )
    => )

        +----+  +----+  +----+     +----+   +----+  (jedno-vstupové uzly)
        | X? |  | Y? |  | Z? |     | X? |   | Y? |
        +----+  +----+  +----+     +----+   +----+
          \       /       |          \        /
        +------------+    |        +------------+
        |     +      |    |        |     +      |
        +------------+    |        +------------+
                  \       |              |          (dvoj-vstupové uzly)
                +------------+           |
                |     +      |           |
                +------------+           |
                      |                  |
            +----------------+     +----------------+
            | fire example-2 |     | fire example-3 |   (koncové uzly)
            +----------------+     +----------------+

Pri spustení siete Jess odovzdá nové fakty každému uzlu zhora siete hneď, ako boli pridané do bázy faktov. Každý uzol berie vstup zhora a pošle svoj výstup smerom nadol.

Jedno-vstupový uzol obvykle prijíma fakty zhora, aplikuje na ne test a ak test prešiel, pošle fakt smerom nadol k nasledujúcemu uzlu. Ak test zlyhal, jedno-vstupové uzly jednoducho nič neurobia.

Dvoj-vstupové uzly musia integrovať fakty z ich ľavého a pravého vstupu, preto ich chovanie musí byť viac komplexné. Ľubovolné fakty dané na vstup dvoj-vstupového uzla môžu prispieť k aktivácii: prejdú všetkými testami, ktoré môžu byť aplikované na jednotlivé fakty.
Dvoj-vstupové uzly si preto musia zapamätať všetky fakty, ktoré sú im predložené na vstup, a pokúsiť sa zoskupiť fakty prichádzajúce na ich ľavé vstupy s faktami prichádzajúcimi na ich pravé vstupy a tak doplniť aktivované množiny. Dvoj-vstupový uzol má z toho dôvodu ľavú a pravú pamäť.

Vhodné je rozdeliť sieť do dvoch logických komponentov: sieť vzoriek obsahujúcich jedno-vstupové uzly, zatiaľ čo sieť spojov tvoria dvoj-vstupové uzly.

3.4 Optimalizácie zlepšujúce RETE algoritmus

1) Zjednotíme identické jedno-vstupové uzly v sieti vzoriek (šípky vedúce von z X? a Y? uzlov sú výstupy):

                    +--------------------------+
                    ^       +-------------+    |
                    |       ^             |    |
                    |       |             |    |
                  +----+  +----+  +----+  |    |
                  | X? |  | Y? |  | Z? |  |    |
                  +----+  +----+  +----+  |    |
                  /      /        /       |    |
        +------------+  /    +---/   +------------+
        |     +      |-+    /        |     +      |
        +------------+     /         +------------+
                  \       /              |
                +------------+           |
                |     +      |           |
                +------------+           |
                      |                  |
            +----------------+     +----------------+
            | fire example-2 |     | fire example-3 |
            +----------------+     +----------------+

                  +----+  +----+  +----+
                  | X? |  | Y? |  | Z? |
                  +----+  +----+  +----+
                  /      /        /
        +------------+  /    +---/
        |     +      |-+    /
        +------------+     /
         |         \       /
         |       +------------+
         |       |     +      |
         |       +------------+
         |             |
         |   +----------------+
         |   | fire example-2 |
         |   +----------------+
   +----------------+
   | fire example-3 |
   +----------------+

3.5 Kompilácia v Jesse

  examlpe-2: +1+1+1+1+1+1+2+2+t

  example-3: =1=1=1=1=2+t

RETE implementácia rozdielnych typov uzlov siete je v Jesse reprezentovaná rôznymi podtriedami Java triedy jess.Node.

4. Prepojenie Jessu s Javou

4.1 Vykonanie súboru s JESS kódom

Na vykonanie súboru, obsahujúceho CLIPS kód pre JESS, sa vytvorí v Jave Rete objekt a Jesp objekt, ktorému sa zadá súbor s CLIPS kódom. Samotný kód programu vykonáva funkcia Jesp.parse (boolean prompt), ako vidieť na nasledujúcom príklade :

import jess.*;
// trieda NullDisplay definuje rozhranie pre príkazový riadok
NullDisplay ND = new NullDisplay ();
// engine expertného systému JESS
Rete rete_engine = new Rete (ND);
// otvorenie súboru s programom v CLIPS kóde
FileInputStream FIS = new FileInputStream ("clips_code.clp");
// JESS_parser bude spracovávať pomocou rete_engine kód v súbore FIS
Jesp JESS_parser = new Jesp (FIS, rete_engine);
// vykonávaj jednotlivé príkazy súboru clips_code.clp
do
{
    try
    {
        // syntaktická analýza a vykonanie jednej konštrukcie
        JESS_parser.parse (false);
    }
    // všetky chyby v JESS sú zobrazované cez 'ReteExceptions'
    catch (ReteException RE)
    {
        RE.printStackTrace (ND.stderr());
    }
// až po koniec súboru, na ktorý ukazuje FIS
} while (FIS.available() > 0);

4.2 Pridanie voliteľných príkazov

// trieda NullDisplay definuje rozhranie pre príkazový riadok
NullDisplay ND = new NullDisplay ();
// engine expertného systému JESS
Rete rete_engine = new Rete (ND);
// zoznam užívateľských balíkov, ktoré sa pridávajú do systému
String [] packages = { "jess.StringFunctions",
                              "jess.PredFunctions",
                              "jess.MultiFunctions",
                              "jess.MiscFunctions",
                              "jess.MathFunctions",
                              "jess.BagFunctions",
                              "jess.reflect.ReflectFunctions",
                              "jess.view.ViewFunction" };
// v cykle vyskúša pridať užívateľský balík k funkciám systému
for (int i=0; i< packages.length; i++)
{
    try
    {
        // pridanie užívateľského balíka k funkciám systému
        rete_engine.addUserPackage
		((Userpackage) Class.forName(packages[i]).newInstance());
    }
    // balík nie je k dispozícii
    catch (Throwable t)
}

4.3 Vykonávanie samostatných príkazov 

try
{
    rete.executeCommand("reset");
    rete.executeCommand("(assert (foo bar foo))");
    rete.executeCommand("run");
    // vypísanie výsledku operácie na obrazovku
    System.out.println(rete.executeCommand("(+ 37 5)"));
}
catch (ReteException RE)
{
    System.err.println("Foo bar error");
}

4.4 Metódy triedy Rete

Zoznam diagnostických metód v triede Rete:

    public synchronized Enumeration listDeftemplates
    public synchronized Enumeration listDefrules
    public synchronized Enumeration listFacts
    public synchronized Enumeration listActivations
    public synchronized Enumeration listDefglobals
    public synchronized Enumeration listUserfunctions

4.5 Použitie rozhrania ReteDisplay 

Definícia rozhrania ReteDisplay:

public interface ReteDisplay
{
    //nastavenie vstupu, výstupu, hlásenia chýb
    public java.io.PrintStream stdout ();
    public java.io.InputStream stdin ();
    public java.io.PrintStream stderr ();
    // metódy pre riadenie udalostí
    public void assertFact (ValueVector fact);
    public void retractFact (ValueVector fact);
    public void addDeffacts (Deffacts df);
    public void addDeftemplate (Deftemplate dt);
    public void addDefrule (Defrule rule);
    public void activateRule (Defrule rule);
    public void deactivateRule (Defrule rule);
    public void fireRule (Dedfrule rule);
    // sprístupnenie Applet-u pre Rete objekt
    public java.applet.Applet applet();
}

5. Záver

6. Bibliografia