AOT Lab
Dipartimento di Ingegneria dell’Informazione
Università degli Studi di Parma
Intelligenza Artificiale
Rappresentazione della Conoscenza
e Ragionamento
Agostino Poggi
Stefano Cagnoni
Rappresentazione
della conoscenza
 Per risolvere qualsiasi tipo di problema di IA dobbiamo:
 Definire la conoscenza riguardante il problema.
 Definire dei metodi per manipolarla.
 Per definire la conoscenza bisogna:
 Definire i fatti che vogliamo rappresentare (livello della conoscenza).
 Rappresentare questi fatti attraverso i cosiddetti metodi per la
rappresentazione della conoscenza (livello simbolico).
Rappresentazione della Conoscenza e Ragionamento
2
Rappresentazione
della Conoscenza
 Proprietà di un metodo per la rappresentazione della
conoscenza:
 Adeguatezza di rappresentazione, cioè la capacità di rappresentare
tutti i tipi di conoscenza necessari per ragionare su un certo dominio.
 Adeguatezza inferenziale, cioè la capacità di manipolare la conoscenza
del sistema per ottenere nuova conoscenza.
 Efficienza inferenziale, cioè la capacità di fornire delle informazioni
per guidare il meccanismo inferenziale nelle direzioni più promettenti.
 Efficienza di acquisizione, cioè la capacità di acquisire facilmente
nuova conoscenza.
Rappresentazione della Conoscenza e Ragionamento
3
Rappresentazione
della Conoscenza
 Esistono due classi principali di strumenti per la
rappresentazione della conoscenza:
 Rappresentazione basata sulle azioni (logica e sistemi a regole)
 Descrizioni primitive di concetti: fatti
 Manipolazione dei concetti attraverso metodi di ragionamento
– Inferenza
– Ragionamento in avanti/indietro
 Rappresentazione basata sugli oggetti (reti semantiche e frame)
 Descrizioni primitive e complesse di concetti
 Manipolazione dei concetti attraverso
– ‘Navigazione’ delle relazioni tra i diversi concetti
– Esecuzione di procedure associate ai diversi concetti
Rappresentazione della Conoscenza e Ragionamento
4
Logica
 La logica è la scienza che fornisce all'uomo gli strumenti
indispensabili per verificare con sicurezza la correttezza dei
ragionamenti.
 La logica fornisce strumenti formali per:
 Esprimere le inferenze in termini di operazioni su espressioni
simboliche.
 Dedurre conseguenze da certe premesse.
 Studiare la verità o falsità di certe proposizioni data la verità o falsità
di altre proposizioni.
 Stabilire la consistenza e la validità di una data teoria.
Rappresentazione della Conoscenza e Ragionamento
5
Logica dei Predicati
 Il linguaggio standard della logica è il cosiddetto calcolo dei
predicati del primo ordine indicato anche con il nome di logica
dei predicati.
 La logica dei predicati si basa su forme atomiche dette
predicati che possono avere un certo numero di argomenti:
 p, q(11), r(X, 25, a, s(a)).
 Le espressioni che possono essere argomenti sono dette termini
e possono essere:
 costanti: 11, a;
 variabili: X, Var;
(normalmente indicate con la lettera maiuscola)
 funzioni: s(a), t(11, X).
Rappresentazione della Conoscenza e Ragionamento
6
Logica dei Predicati
 Le formule atomiche possono essere combinate per formare
delle altre formule:




Congiunzione:
Disgiunzione:
Implicazione:
Negazione:
A&B
A B
A B
A
 Le formule con variabili possono essere interpretate tramite i
quantificatori:
 Universali:
 Esistenziali:
X p(X)
X p(X)
Rappresentazione della Conoscenza e Ragionamento
7
Logica dei Predicati
 Il modo per inferire nuova conoscenza in logica è basato sul
ragionamento deduttivo.
 Il ragionamento deduttivo è un ragionamento che, condotto
correttamente, mantiene la veridicità delle premesse.
 Nel ragionamento deduttivo, se le conoscenze da cui partiamo
(le premesse) sono vere, allora anche le nuove conoscenze che
otteniamo in base a queste (le conclusioni) sono vere.
 Il sillogismo è un esempio tipico di ragionamento deduttivo:
«Gli uomini sono mortali, Socrate è un uomo, allora Socrate è
mortale».
Rappresentazione della Conoscenza e Ragionamento
8
Logica dei Predicati
 In logica la conoscenza iniziale viene indicata con il nome di
assiomi. Le nuove conoscenze dedotte dagli assiomi sono dette
teoremi.
 Per dedurre nuovi teoremi si usano le regole di inferenza.Ogni
regola di inferenza è composta da due parti:
 Un insieme di premesse separate da virgole.
 Le conclusioni.
 Queste due parti sono divise dal simbolo  che si legge: «è
possibili derivare».
Rappresentazione della Conoscenza e Ragionamento
9
Logica dei Predicati
 Alcune tra le più note regole di inferenza sono le seguenti:





Modus Ponens:
Istanziazione universale:
Modus Tollens:
Introduzione congiunzione:
Eliminazione congiunzione:
 Introduzione disgiunzione:
 Eliminazione disgiunzione:
Rappresentazione della Conoscenza e Ragionamento
A B, A  B
X p(X)  p(a)
A B, B  A
A, B  A & B
A&B A
A&BB
A  A B
B  A B
A B, A  B
A B, B  A
10
Forma a Clausole
 La difficoltà di ottenere nuovi teoremi sta nel scegliere, di volta
in volta, la regola di inferenza da applicare.
 Le formule della logica dei predicati possono essere
trasformate in una forma equivalente a clausole.
 Una clausola è una formula priva di quantificatori ed è formata
da una disgiunzione di termini.
 Con la rappresentazione a clausole è possibile utilizzare
un’unica regola di inferenza detta regola di risoluzione.
Rappresentazione della Conoscenza e Ragionamento
11
Forma a Clausole
 Regola di risoluzione: da AB,BC deduci AC
 Il metodo di risoluzione permette di dimostrare un teorema
mediante il metodo della refutazione, cioè si dimostra che la
negazione del teorema è falsa:
 Assumiamo che la negazione del teorema sia vera.
 Mostriamo che gli assiomi più la negazione del teorema sono fra loro
inconsistenti.
 Dato che gli assiomi sono per definizione veri, allora la responsabile
della contraddizione è la negazione del teorema.
 Quindi il teorema è vero.
 Si ottiene una contraddizione quando si arriva a dedurre la
clausola vuota.
Rappresentazione della Conoscenza e Ragionamento
12
Forma a Clausole
 Abbiamo le seguenti clausole:
[A1] lavora(piero) prepara(piero,esame
[A2] ha(piero,tempo) ha(piero,soldi) va(piero, partita)
[A3] ha(piero,tempo)
 lavora(piero)compera(piero,calcolatore) ha(piero,soldi)
[A5] compera(piero,calcolatore)
[A6] prepara(piero esame)
 Vogliamo dimostrare il teorema:
[T] va(piero,partita)
 Per risolvere il teorema aggiungiamo il teorema negato agli assiomi:
[~T] va(piero,partita)
Rappresentazione della Conoscenza e Ragionamento
13
Forma a Clausole
 Risolviamo ~T con A2 :
[~T] va(piero,partita)
[A2] ha(piero,tempo) ha(piero,soldi) va(piero, partita)
 Otteniamo il lemma L1 che risolviamo con A3:
[L1] ha(piero,tempo) ha(piero,soldi)
[A3] ha(piero,tempo)
 Otteniamo il lemma L2 che risolviamo con A4:
[L2] ha(piero,soldi)
 lavora(piero)compera(piero,calcolatore) ha(piero,soldi)
Rappresentazione della Conoscenza e Ragionamento
14
Forma a Clausole
 Otteniamo il lemma L3 che risolviamo con A5:
[L3] lavora(piero)compera(piero,calcolatore)
[A5] compera(piero,calcolatore)
 Otteniamo il lemma L4 che risolviamo con A1:
[L4] lavora(piero)
[A1] lavora(piero) prepara(piero,esame
 Otteniamo il lemma L5 che risolviamo con A6:
[L5] prepara(piero,esame
[A6] prepara(piero esame)
 A1 (assioma!) è stato negato => contraddizione => ~T è falso
Rappresentazione della Conoscenza e Ragionamento
15
Vantaggi della Logica
 I vantaggi principali della logica sono:
 Precisione, la logica ha una semantica chiara e definita per la quale
esistono metodi standardizzati per determinare il significato di una
espressione.
 Flessibilità, la logica rappresenta la conoscenza in modo dichiarativo,
quindi in modo indipendente dal suo uso.
 Modularità, le asserzioni della logica possono entrare in una base di
conoscenza in modo indipendente le une dalle altre.
Rappresentazione della Conoscenza e Ragionamento
16
Limiti della Logica
 I limiti principali della logica sono:
 Inadeguatezza espressiva, non può rappresentare mondi dinamici, non
può rappresentare conoscenze probabilistiche.
 Monotonicità, l’aggiunta di un teorema non provoca la cancellazione
di nessun teorema precedente.
 Inefficienza, la dimostrazione automatica basata esclusivamente sulla
logica si fonda su processi di ricerca, la ricerca è inerentemente
esponenziale ed eventuali euristiche non ne cambiano la natura
combinatoria.
Rappresentazione della Conoscenza e Ragionamento
17
Sistemi di Produzione
 I sistemi di produzione sono uno strumento ideale per la
costruzione di sistemi basati sulla conoscenza.
 Infatti, permettono di implementare algoritmi di ricerca guidata
dai dati (forward chaining) e algoritmi di ricerca guidata dagli
obiettivi (backward chaining).
 Permettono di realizzare sistemi di ragionamento deduttivo e
anche sistemi di ragionamento plausibile e incerto.
 OPS5 (Brownston, et al., 1985) è sicuramente il sistema di
produzioni più conosciuto.
Rappresentazione della Conoscenza e Ragionamento
18
Regole di Produzione
 I sistemi di produzione rappresentano la conoscenza attraverso
regole di produzione.
 Una regola di produzione è composta da una coppia
condizione/azione ed ha la forma:
IF <insieme condizioni> THEN <insieme azioni>
 Le azioni possono essere di due tipi distinti:
 Azioni sul mondo esterno.
 Azioni sulla conoscenza del sistema.
 Le regole di produzione modellano sia conoscenza procedurale
che conoscenza dichiarativa.
Rappresentazione della Conoscenza e Ragionamento
19
Architettura dei
Sistemi di Produzione
 Un sistema di produzione è composto da tre parti:
 La base delle regole.
 La memoria di lavoro.
 L’interprete delle regole.
 La base delle regole contiene la conoscenza del sistema
espressa in regole di produzione.
 La memoria di lavoro contiene le informazioni sullo stato di
avanzamento del processo computazionale.
 L’interprete controlla il sistema applicando le regole alle
informazioni nella memoria di lavoro.
Rappresentazione della Conoscenza e Ragionamento
20
Funzionamento dei
Sistemi di Produzione
 Dopo aver inserito nella memoria di lavoro le informazioni
relative al problema che si vuole risolvere, il funzionamento di
un sistema di produzione si basa sulla ripetizione di tre passi:
 Confronto.
 Risoluzione conflitti.
 Esecuzione.
 Nella fase di confronto vengono individuate le regole la cui
parte sinistra è soddisfatta dal contenuto della memoria di
lavoro.
Rappresentazione della Conoscenza e Ragionamento
21
Funzionamento dei
Sistemi di Produzione
 Nel caso in cui più di una regola può essere eseguita, nella fase
di risoluzione dei conflitti viene scelta una regola in base a una
serie di criteri prestabiliti.
 Scelta la regola, essa viene eseguita, compiendo azioni sul
mondo e aggiornando la memoria di lavoro.
 La terminazione dell’attività del sistema può avvenire in
diversi modi. I più comuni sono:
 L’insieme dei conflitti è vuoto.
 Una regola ha come azione una istruzione di halt.
Rappresentazione della Conoscenza e Ragionamento
22
Criteri per Risolvere i Conflitti
 Esistono vari criteri per risolvere i conflitti:
 Criterio di ordinamento (rule ordering o fire first): le regole sono
ordinate in ordine di importanza;
 Criterio di refrattarietà (refractoriness): una regola può essere attivata
sugli stessi dati una sola volta. Di questo criterio esistono due
versioni:
 Il criterio ha validità su tutti i cicli precedenti.
 Il criterio ha validità sul ciclo precedente.
 Criterio di recenza (recency): gli elementi della memoria di lavoro
vengono etichettati in base al ciclo in cui sono stati inseriti, le regole
che utilizzano dati più recenti sono favorite rispetto a quelle che usano
dati che si trovano in memoria da più tempo.
Rappresentazione della Conoscenza e Ragionamento
23
Criteri per Risolvere i Conflitti
 Criterio di specificità (specificity), si favoriscono le regole più
specifiche, cioè quelle con la condizione più dettagliata qualora le
condizioni di queste regole siano un sovra-insieme delle altre regole
contenute nell’insieme di conflitti.
 Criterio di ordinamento in base ai dati (data ordering): si assegnano
delle priorità diverse alle varie condizioni e si esegue la regola che ha
le condizioni a priorità più alta.
 Criterio di ordinamento in base ai pesi (weight ordering): si
assegnano alle regole dei pesi che tengono conto del numero di volte
che una regola è stata attivata.
 Criterio di ordinamento in base alla grandezza, vengono favorite le
regole con il maggior numero di condizioni.
Rappresentazione della Conoscenza e Ragionamento
24
Gestione dei Cicli
 In certi casi un sistema di produzioni può cadere in un ciclo di
attivazioni ripetute che non ha termine.
 Esistono due modi per implementare dei meccanismi per
eliminare dei cicli di attivazioni ripetuti:
 Cablare nell’interprete un meccanismo che evita l’attivazione di regole
che cercano di aggiungere alla memoria di lavoro informazioni già
presenti.
 Definire le regole di produzione in modo che inseriscano delle
clausole che ne inibiscano l’attivazione successiva.
Rappresentazione della Conoscenza e Ragionamento
25
Conoscenza di Controllo
 Alcuni sistemi di produzione permettono la definizione di
meta-regole per sfruttare della conoscenza euristica sul
problema da risolvere per velocizzare e facilitare la sua
soluzione.
 Questa conoscenza può riferirsi a:
 Quali regole applicare in certe situazioni.
 In quale ordine soddisfare i sotto-obiettivi.
 Quali sequenze di regole sono utili da applicare.
Rappresentazione della Conoscenza e Ragionamento
26
L’algoritmo RETE
 Il punto debole dei sistemi di produzione è il grande dispendio
di risorse della fase di confronto.
 Un algoritmo di confronto molto efficiente è l’algoritmo RETE
(Forgy, 1982). Esso si basa su:
 Una struttura dati detta rete di discriminazione che utilizza due tipi di
nodi:
 Nodi test che corrispondono ai nodi intermedi della rete e rappresentano dei test
sui dati nella memoria di lavoro.
 Nodi terminali che rappresentano le singole regole di produzione.
 Ad ogni ciclo aggiorna l’insieme dei conflitti:
 Se un dato viene aggiunto, cerca le regole che sono attivabili da quel dato.
 Se un dato viene tolto, cerca le regole che erano attivate da quel dato.
Rappresentazione della Conoscenza e Ragionamento
27
Vantaggi e Limiti dei
Sistemi di Produzione
 I principali vantaggi dei sistemi di produzione sono:
 La semantica di una regola di produzione è facilmente intuibile.
 I meccanismi di controllo sono programmabili.
 I principali limiti dei sistemi di produzione sono:
 L’aggiunta di una regola può comportare la modifica di regole
preesistenti.
 I meccanismi di controllo sono globali e difficili da regolare.
Rappresentazione della Conoscenza e Ragionamento
28