Regola (informatica)

In informatica, una regola di produzione (o semplicemente regola) è un formalismo per la rappresentazione della conoscenza e per la trasformazione di strutture simboliche. Originariamente introdotte dal matematico Emil Post per descrivere sistemi formali di manipolazione di stringhe, le regole di produzione sono successivamente divenute l'elemento centrale dei sistemi a regole e dei sistemi esperti nell'intelligenza artificiale, oltre che delle grammatiche formali descritte da Noam Chomsky.

In termini generali, una regola formalizza una relazione d'inferenza o una trasformazione condizionata nella forma:

SE $A$ ALLORA $B$

oppure anche

A ⟹ B

dove $A$ rappresenta la condizione (o antecedente) e $B$ rappresenta l'azione o la nuova informazione prodotta (o conseguente).

Formalizzazione logica e sintattica

Nell'ambito dell'ingegneria della conoscenza, l'antecedente $A$ è generalmente formato da una congiunzione ( $\land$ ) o disgiunzione ( $\lor$ ) di condizioni o pattern da riscontrare nello stato corrente del sistema:

A = c_{1} \land c_{2} \land \dots \land c_{n}

Quando lo stato attuale soddisfa le condizioni stabilite nell'antecedente, la regola diventa attivabile. L'esecuzione del conseguente $B$ determina la modifica dello stato, mediante l'asserzione di nuovi fatti, la cancellazione di dati esistenti o la produzione di azioni verso l'esterno.

In logica matematica una teoria (o base di conoscenza) può essere composta da assiomi in forma di fatti e regole ossia clausole definite (o di Horn) costruite a partire da formule atomiche (atomi). In informatica questo formalismo è alla base dei programmi della programmazione logica.

Nelle grammatiche formali, una regola di produzione esprime la sostituzione di simboli alfabetici nella forma $α \to β$ , definendo la derivazione delle stringhe di un linguaggio formale.

Ciclo di esecuzione e motori inferenziali

Nei sistemi basati su regole, la gestione e l'applicazione del corpo di regole sono affidate a un algoritmo denominato motore inferenziale. L'esecuzione avviene tipicamente all'interno di un ciclo a tre fasi (Match-Resolve-Act):

Match (confronto): Il motore confronta i fatti presenti nella memoria di lavoro con gli antecedenti di tutte le regole per individuare quelle applicabili.
Conflict Resolution (risoluzione dei conflitti): Se più regole risultano contemporaneamente attive, esse formano un insieme di conflitto (conflict set). Il motore applica euristiche (come la specificità, la salienza o una forma di priorità, anche al livello temporale) per selezionare un'unica regola da eseguire.
Act (esecuzione): Viene applicato il conseguente della regola scelta, modificando lo stato della memoria.

Per ottimizzare la fase computazionalmente onerosa di match, si fa largo uso dell'algoritmo Rete sviluppato da Charles Forgy, che costruisce un grafo aciclico orientato per valutare in modo efficiente le relazioni tra regole e fatti dinamici.

Strategie di ragionamento

L'elaborazione delle regole di produzione può seguire due direzioni logiche fondamentali:

Concatenazione in avanti: approccio guidato dai dati (data-driven). Parte dalle informazioni disponibili nella memoria di lavoro e applica iterativamente le regole per derivare nuove conoscenze finché non si raggiunge un obiettivo o un punto fisso.
Concatenazione all'indietro: approccio guidato dagli obiettivi (goal-driven). Parte da un'ipotesi o obiettivo $G$ e ricerca a ritroso le regole il cui conseguente contiene $G$ , traducendo le relative premesse in sotto-obiettivi da verificare.

Trattamento dell'incertezza

I sistemi a regole avanzati integrano meccanismi per gestire la conoscenza incerta, vaga o probabilistica. Tra questi, il modello dei fattori di certezza (certainty factors, CF) associa uno scalare $C F \in [- 1, 1]$ sia alle premesse che alle regole stesse:

SE $A$ (con $C F_{A}$ ) ALLORA $B$ (con $C F_{R}$ )

Il fattore di certezza risultante per la conclusione $B$ è dato da:

C F_{B} = C F_{A} \times C F_{R}

Tale approccio è stato reso popolare da sistemi storici come MYCIN per la diagnosi medica in presenza di incertezza, oltre che dall'applicazione della logica fuzzy.

Note

↑ Emil L. Post, Formal Reductions of the General Combinatorial Decision Problem, in American Journal of Mathematics, vol. 65, n. 2, 1943, pp. 197–215, DOI:10.2307/2371809.
↑ Noam Chomsky, Syntactic Structures, Mouton & Co., 1957, ISBN 978-3110172799.
↑ Stuart J. Russell e Peter Norvig, Intelligenza artificiale. Un approccio moderno, Pearson, 2021, ISBN 978-8891905086.
↑ Joseph C. Giarratano e Gary D. Riley, Expert Systems: Principles and Programming, Thomson Course Technology, 2004, ISBN 978-0534384470.
↑ Charles L. Forgy, Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem, in Artificial Intelligence, vol. 19, n. 1, 1982, pp. 17–37, DOI:10.1016/0004-3702(82)90020-0.
↑ Bruce G. Buchanan e Edward H. Shortliffe, Rule-Based Expert Systems: The MYCIN Experiments of the Stanford Heuristic Programming Project, Addison-Wesley, 1984, ISBN 978-0201101720.

Voci correlate

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica

[1] Emil L. Post, Formal Reductions of the General Combinatorial Decision Problem, in American Journal of Mathematics, vol. 65, n. 2, 1943, pp. 197–215, DOI:10.2307/2371809.

[2] Noam Chomsky, Syntactic Structures, Mouton & Co., 1957, ISBN 978-3110172799.

[3] Stuart J. Russell e Peter Norvig, Intelligenza artificiale. Un approccio moderno, Pearson, 2021, ISBN 978-8891905086.

[4] Joseph C. Giarratano e Gary D. Riley, Expert Systems: Principles and Programming, Thomson Course Technology, 2004, ISBN 978-0534384470.

[5] Charles L. Forgy, Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem, in Artificial Intelligence, vol. 19, n. 1, 1982, pp. 17–37, DOI:10.1016/0004-3702(82)90020-0.

[6] Bruce G. Buchanan e Edward H. Shortliffe, Rule-Based Expert Systems: The MYCIN Experiments of the Stanford Heuristic Programming Project, Addison-Wesley, 1984, ISBN 978-0201101720.