Intelligenza Artificiale 2
Metodologie di ragionamento
Prof. M.T. PAZIENZA
a.a. 2000-2001
Conoscenza e ragionamento con incertezza
• Problema reale dell’informazione incerta
• Teoria della probabilità fornisce le basi per il
trattamento di sistemi che ragionano con
incertezza
• Teoria dell’utilità per pesare la desiderabilità
degli obiettivi e la probabilità di raggiungerli
(in quanto le azioni non sono più certe del
raggiungimento degli obiettivi)
Incertezza
• Quando gli agenti non hanno accesso all’intera
conoscenza dell’ambiente (cartello VIETATO
FUMARE illeggibile)
• Quando gli agenti hanno una incompleta, o non
totalmente corretta, comprensione delle proprietà
dell’ambiente (simbolo nuovo di VIETATO
FUMARE).
Ciò si verifica anche quando le regole sul dominio
risultano incomplete in quanto ci sono “troppe”
condizioni da enumerare esplicitamente o perché
alcune condizioni sono ignorate. L’incertezza non è
evitabile in mondi complessi, dinamici o inaccessibili
Incertezza
• Massimizzare la misura delle prestazioni,
date le informazioni che si hanno
sull’ambiente.
• La cosa giusta da fare, la decisione
razionale, dipende sia dall’importanza
relativa degli obiettivi, che dalla probabilità
e dal grado con cui verranno raggiunti.
Conoscenza incerta
• Caso della diagnosi ( in qualunque settore)
Si è in una situazione di incertezza in quanto
la lista di situazioni e cause da descrivere
non può essere esaustiva (praticamente
infinita per la mancanza di conoscenza
universale)
Logica e conoscenza incerta
Non si può usare la logica del primo ordine per
gestire la diagnosi. Infatti:
• impossibilità di elencare l’insieme praticamente
infinito di antecedenti e conseguenti per evitare
eccezioni
• mancata conoscenza metodologica completa
• mancata conoscenza applicativa completa
L’agente non potrà mai agire con una piena
consapevolezza di verità e correttezza, avrà solo
un grado di credenza sulla bontà delle azioni da
intraprendere e dei risultati.
Teoria della probabilità
La teoria della probabilità assegna un valore
di credenza (tra 0 ed 1) che esprime
l’incertezza.
La probabilità esprime l’incapacità dell’agente
di raggiungere una decisione definita a
proposito della verità di una formula e
riassumere le credenze di un agente.
Teoria della probabilità
• Valore 0 <--> credenza non equivocabile
che la formula è falsa
• Valore 1 <--> credenza non equivocabile
che la formula è vera
• Valori 0,1..0,9 <--> gradi di credenza
intermedi
Teoria della probabilità
Un valore a% di probabilità esprime il valore
percentuale a% di casi indistinguisbili tra
loro e veri.
Il valore di probabilità è calcolato con:
• metodi statistici
• regole generali
• regole basate su informazioni ambientali
estemporanee
Semantica degli enunciati di probab.
Nella logica del primo ordine ed in quella
proposizionale, una formula è vera o falsa a
seconda dell’interpretazione.
Nella teoria della probabilità, la probabilità
che un agente si affidi ad una proposizione
dipende dalle percezioni ricevute sino a
quel momento (prova). Le probabilità
possono cambiare quando si acquisiscono
nuove prove
Teoria della probabilità
• Probabilità a priori o incondizionata (prima
della prova).
• Probabilità a posteriori o condizionata
(dopo l’acquisizione delle prove)
Incertezza e decisioni
• Un agente logico ha un solo obiettivo ed
esegue un piano che garantisce il suo
raggiungimento (indipendentemente da altre
azioni)
• Un agente probabilistico è certo di
raggiungere l’obiettivo con qualche
probabilità (ed avendo preferito alcune tra
le conseguenze possibili).
Teoria dell’utilità
La teoria dell’utilità permette di rappresentare le
preferenze.
Ogni stato ha un grado di utilità per un agente;
l’agente preferirà di volta in volta stati con
utilità più alta.
L’utilità non è una priorità dello stato.
Non c’è oggettività nella scelta delle preferenze;
soggettività rispetto a ciascun agente.
Teoria delle decisioni
Le preferenze (utilità) sono combinate con le
probabilità nella teoria delle decisioni.
Teoria delle decisioni = Teoria delle probabilità +
Teoria dell’utilità
Agente basato sulla teoria delle decis.
Probabilità a priori P(A)
P(A) è la probabilità incondizionata o a priori che
l’evento/proposizione A sia vera in mancanza di
altre informazioni
La proposizione che è il soggetto di un enunciato
di probabilità può essere rappresentata da un
simbolo proposizionale P(A).
Le proposizioni includono variabili casuli.
Variabili casuali
Ogni variabile casuale X ha un dominio di
valori possibili (x, y,…z), in genere discreti,
che può assumere.
Quando si ha un vettore di valori per le
probabilità di ogni singolo stato del tempo,
si parla di
distribuzione di probabilità.
Probabilità condizionata
P(A/B) è la probabilità condizionata o a posteriori
che l’evento/proposizione A sia vera dopo che si
sia verificato l’evento/proposizione B. In
generale
P(X,Y)=P(X/Y)P(Y)
fornisce la probabilità condizionale delle variabili
nei domini di variabilità delle variabili casuali.
La probabilità condizionale di una disgiunzione è
data da P(AvB)=P(A)+P(B)-P(A^B)
Probabilità
Distribuzione di probabilità congiunta
La distribuzione di probabilità congiunta
specifica completamente le assegnazioni di
probabilità per tutte le proposizioni nel
dominio di un agente.
Si ha un insieme di variabili casuali che possono
assumere determinati valori con certe
probabilità
Evento atomico
Un evento atomico è un’assegnazione di
valori particolari a tutte le variabili.
La distribuzione di probabilità congiunta
assegna probabilità a tutti gli eventi atomici.
La specifica delle probabilità di un evento
atomico può essere molto difficile se non si
dispone di grandi quantità di dati da cui
estrarre stime statistiche.
Probabilità congiunta
La probabilità congiunta è una tavola
n-dimensionale con un valore in ogni cella che
fornisce la probabilità che quello specifico
stato (rappresentato da quelle variabili casuali)
si verifichi
A
-A
B 0.04 0.06
-B 0.01 0.89
Sommando lungo la riga o la colonna si ha la
probabilità incondizionata di quella variabile
Probabilità condizionale
E’ possibile fare inferenze a proposito della
probabilità di una proposizione ignota A,
data prova di B, calcolando P(A/B).
Un’interrogazione ad un sistema di
ragionamento probabilistico chiederà di
calcolare il valore di una particolare
probabilità condizionata.
Regola di Bayes
Con variabili indipendenti si ha:
P(A^B)=P(A/B)P(B)
P(A^B)=P(B/A)P(A)
da cui
P(A/B)P(B)=P(B/A)P(A)
e quindi la regola di Bayes
P(B/A)=P(A/B)P(B)
P(A)
che permette di fare inferenza probabilistica
Regola di Bayes
• Le relazioni di indipendenza condizionale
fra le variabili possono semplificare il
calcolo dei risultati delle interrogazioni e
ridurre notevolmente il numero di
probabilità condizionate che devono essere
specificate.
Assegnazione di valori di probabilità
• Partendo da misure di frequenza (di valori
di variabili) effettuate su casi reali
• Analizzando aspetti reali per cui le misure
di probabilità sono valori intrinseci di un
oggetto
Ragionamento probabilistico
I sistemi di ragionamento probabilistico
permettono di prendere decisioni razionali
anche quando non vi è abbastanza informazione
per dimostrare che qualsiasi azione funzionerà.
Per rappresentare la dipendenza fra le variabili, si
usano le reti di credenza come struttura dati.
Permettono anche di specificare concisamente
le distribuzioni di probabilità congiunta.
Rete di credenza
Una rete di credenze è un grafo diretto
aciclico in cui:
• i nodi sono un insieme di di variabili casuali
• archi direzionali congiungenti coppie di
nodi rappresentano l’influenza di una
variabile su un’altra
• ad ogni nodo è associata una tabella di prob.
condizionata che esprime gli effetti dei nodi
che lo influenzano (nodi genitori)
Rete di credenza
• Si affida ad un esperto di dominio la definizione
della topologia della rete di credenze, poi si
calcolano le influenze dirette e le conseguenti
probabilità
• La topologia della rete è la base di conoscenza
generale ed astratta dell’ambiente in cui si
possono verificare gli eventi, e rappresenta la
struttura generale del processo causale nel
dominio, piuttosto che fornire dettagli su un
particolare elemento.
Rete di credenza
Rete di credenza
• Una volta definita la topologia bisogna
specificare la tabella delle probabilità
condizionate associata ad ogni nodo.
• Ogni riga della tabella esprime la probabilità
del valore di ogni nodo per un caso
condizionante (combinazione di valori dei
nodi genitori)
• Un nodo con nessun genitore è rappresentato
dalla probabilità a priori
Rete di credenze con le probabilità condizionate
Rete di credenza
• Una rete di credenze rappresenta una (tra le
varie possibili) descrizione completa del
dominio solo se ogni nodo è condizionalmente
indipendente dai suoi predecessori
nell’ordinamento dei nodi dati i suoi genitori.
• Un elemento della tabella congiunta è la
probabilità di una congiunzione di assegnazioni
particolari ad ogni variabile.
Costruz. incrementale rete di credenza
Identificare un insieme di variabili rilevanti Xi che
descrivano il dominio
Scegliere un ordinamento tra le variabili
Finché rimangono variabili:
1. Prendere una Xi ed aggiungere un nodo alla rete
2. Scegliere l’insieme di genitori di Xi indipendenti
condizionalmente
3. Definire la tabella delle proprietà condizionate per
Xi.
Garantire la compattezza della rete.
Costruz. incrementale rete di credenza
Causa  Effetto
L’ordine corretto per aggiungere nodi è quello
che prevede prima l’inserimento delle “cause
alla radice”, quindi delle variabili che
influenzano per arrivare poi alle foglie che
non hanno nessuna influenza causale sulle
altre variabili.
Strutture di una rete di credenze
La struttura della rete dipende dall’ordine di
inserimento dei nodi.
Inferenza nelle reti di credenze
Compito fondamentale per un sistema di inferenza
probabilistico è quello di calcolare la distribuzione
delle probabilità a posteriori per un insieme di
variabili di interrogazione, dati i valori esatti per
alcune variabili di prova: P(Interrogazione/Prova)
In ogni rete di credenza ogni nodo può servire sia
come variabile di prova che di interrogazione.
Un agente acquisisce valori per le variabili di prova
dalle proprie percezioni (o da altro ragionamento) e
si informa a proposito di valori possibili per altre
variabili per poter decidere quale azione compiere.
Reti di credenza a connessioni multiple
• Un grafo è a connessioni multiple se due nodi
sono connessi da più di un cammino. Ciò accade
quando vi è più di una causa per una qualche
variabile e le cause condividono un antenato.
• Oppure reti a connessioni multiple rappresentano
situazioni in cui una variabile può influenzare
un’altra attraverso più di un meccanismo causale.
Reti di credenza a connessioni multiple
Reti di credenza a connessioni multiple
Reti di credenza a connessioni multiple
Ragionamento con incertezza
1. Decider di cosa parlare
2. Decidere un vocabolario delle variabili
casuali
3. Codifica delle conoscenza generale per le
dipendenze fra le variabili
4. Descrivere l’istanza specifica del problema
5. Interrogare la procedura di inferenza ed
ottenere risposte