• I sistemi esperti basati su regole

    Date: 2011.11.16 | Category: Intelligenza Artificiale | Tags: ,

    Definizione di Sistema Esperto

    Un sistema esperto è un software che dopo essere stato istruito in modo opportuno, è in grado di dedurre nuove informazioni a partire da un insieme di informazioni di partenza (fatti).

    In un sistema esperto la competenza di un esperto umano è codificata nella cosidetta base di conoscenza (ad esempio sotto forma di regola), aggiornabile in base all’esperienza.

    I sistemi esperti basati su regole sono dei programmi composti da regole della forma IF condizione THEN azione.

    Dati una serie di fatti i sistemi esperti, grazie alle regole di cui sono composti, riescono a dedurre nuovi fatti.

    Perché scegliere un sistema basato su regole

    Le regole ci permettono di rappresentare alcuni tipi di conoscenza che sono difficili da implementare in un canonico programma procedurale.

    Un programma “rule-based” separa la conoscenza dal resto del programma.

    Questo porta il vantaggio che se si cambia la conoscenza cio’ non comporta una modifica il programma procedurale.

    Si ha così una maggiore flessibilità, in quanto si possono rinviare alcune deciosioni oppure riconsidarle senza ricostruire completamente il programma.

    Un programma basato su regole può essere scritto in modi diversi. Alcuni linguaggi come OPS-5 sono stati studianti per questo scopo (http://free-compilers.sharnoff.org/TOOL/OPS5-1.html).

    Definizione di Sistema di Produzione basato su regole:

    Un sistema a regole di produzione (production system) è costituito da tre componenti fondamentali:

    1. Base di conoscenza a regole (che prende spesso il nome di memoria a lungo termine) in cui sono contenute le regole di produzione
    2. Memoria di lavoro (memoria a breve termine) in cui sono contenuti i dati e in cui vengono mantenute le conclusioni raggiunte dal sistema
    3. Motore inferenziale

      Ogni regola di produzione ha la seguente forma:

      IF <pattern> THEN <body>

      Le regole non sono invocate per nome, ma sono attivate in base al pattern-matching.

      La conoscenza

      Fatti: informazioni che riguardano la particolare situazione

      Regole: formulano elementari meccanismi del tipo se : : : allora : : :

      motore-inferenziale

      Tipi di Regole

      • Relazioni (e.g., relazioni causali)
      • Raccomandazioni, consigli, suggerimenti
      • Direttive
      • Strategia
      • Euristica

      Raccomandazioni:

      SE la stagione e’ autunno E il cielo e’ nuvoloso
      ALLORA consiglio di prendere l’ombrello

      Strategia:

      SE l’auto non si avvia ALLORA controlla il serbatoio il serbatoio; passo-1 completato

      SE passo-1 completato E il serbatoio e’ pieno ALLORA controlla la batteria; passo-2 completato

      Euristica:

      SE il liquido e’ scuro E ha pH < 6 E ha profumo acidulo ALLORA il liquido e' aceto balsamico

      Relazioni:

      SE il serbatoio e’ vuoto ALLORA l’auto non si avvia

      Direttive:

      SE l’auto non si avvia E il serbatoio e’ vuoto ALLORA riempi il serbatoio

      Meccanismi di Inferenza

      Due tipi di controllo (cioe’ di concatenamento delle regole):

      • Forward chaining: cerca di giungere ad una conclusione partendo dai fatti presenti all’inizio nella memoria temporanea e applicando in avanti le regole.
      • Backward chaining: si procede mediante riduzione dell’obiettivo principale (goal) a sottoproblemi. Una volta individuata la tesi da dimostrare, si applicano all’indietro le regole di produzione, cercando di trovare coerenza con i dati iniziali.

      ALGORITMO FORWARD CHAINING (o DATA-DRIVEN)

      La memoria di lavoro nella sua configurazione iniziale contiene la conoscenza iniziale sul problema, cioè i fatti noti.

      Le regole di produzione applicabili sono quelle il cui antecedente può fare matching con la memoria di lavoro (F-rules).

      Ogni volta che una regola viene selezionata ed eseguita nuovi fatti dimostrati vengono inseriti nella memoria di lavoro.

      Il procedimento termina con successo quando nella
      memoria di lavoro viene inserito anche il goal da dimostrare (condizione di terminazione).

      Algoritmo Base

      while <obiettivo non raggiunto> do
          begin
              <MATCH: determina l'insieme delle regole
      applicabili (cio_e le regole il cui
              antecedente _e soddisfatto dai fatti
              contenuti nella memoria di lavoro)>;

              <CONFLICT_RESOLUTION: seleziona la regola
              da applicare>;

              <FIRE: esegui l'      azione associata
              alla regola>;
          end;

      Ecco il processo di inferenza schemattizato nel seguente flow-chart:

      schema-inferenza-forward-chaining

      i sistemi esperti basati su regole

      Esempio Forward Chaining

      Regole:
      R1: Y and D → Z
      R2: X and B and E → Y
      R3: A → X
      R4: C → L
      R5: L and M → N
      Fatti: A B C D E

      Regole applicabili: R3,R4
      2. Applichiamo R3 (preferenza alla regola con indice piu’ basso); R3 non potra’ piu’ essere usata
      3. Fatti: A B C D E X
      4. Regole applicabili: R2,R4
      5. Applichiamo R2
      6. Fatti: A B C D E X Y
      7. Regole applicabili: R1,R4
      8. Applichiamo R1
      9. Fatti: A B C D E X Y Z
      10. Regole applicabili: R4
      11. Applichiamo R4
      12. Fatti: A B C D E X Y Z L
      13. stop

      Conflict resolution

      • Ordine lessicografico (e.g., R3 prima di R6)
      • Attirubuire valori di priorita’ alle regole
      • Preferire le regole piu’ dettagliate (e.g., quelle con una precondizione piu’ restrittiva)
      • Preferire le regole inserite piu’ recentemente
      • Metaregole: regole che impongono un ordine sulle regole. E.g., preferire le regole espresse da esperti `piu’ vecchi’

      Possibili Estensioni

      1. Teoria dei Fattori di certezza (si asserisce una conclusione che e’ vera con una certa probabilita’)
      2. Ragionamento probabilistico (principalmente basato sul teorema di Bayes)
      3. Regole fuzzy. E.g., SE il carico della lavatrice e’ leggero ALLORA usa poca acqua

      Esempio:

      Si consideri un sistema esperto che contiene le seguenti regole:

      R1) SE piove ALLORA erba_bagnata
      R2) SE piove ALLORA tetto_bagnato
      R3) SE innaffiatore_acceso ALLORA erba_bagnata
      R4) SE tetto_bagnato ALLORA acqua_in_garage

      E i seguenti fatti:

      F1) piove

      Applichiamo le modalità di ragionamento forward per sapere se è vero che c’è acqua in garage (cioè l’affermazione acqua_in_garage è verà).

      Nel caso di più regole applicabili, scegliamo di applicare per prima la regola con indice più basso (cioè R2 sarà eseguita prima di R5).

      Forward chaining

      La memoria di lavoro contiene solo un’informazione: piove.

      Cerchiamo una regola che abbia una corrispondenza (matching) con un fatto (ne abbiamo uno solo per ora).

      Ci sono due regole applicabili: R1 e R2. Applichiamo R1 e inseriamo nella memoria di lavoro il fatto erba_bagnata. La regola R1 non sarà più considerata.

      Cerchiamo ora altre regole applicabili: dati i fatti (piove e erba_bagnata), rimane solo R2 che ha una corrispondenza. Applichiamo R2 e aggiungiamo alla memoria di alvoro il fatto tetto_bagnato.

      Ripetiamo il procedimento. Dati i fatti correnti e l’eliminazione delle regole R1 e R2, possiamo applicare solo la regola R4 che cio permette di inserire nella memoria di lavoro il fatto acqua_in_garage.