Intelligenza Artificiale Conoscenza e ragionamento incerto

Prof. M.T. PAZIENZA

a.a. 2013-2014

Conoscenza e ragionamento in situazioni di incertezza

Incertezza come problema reale della descrizione di problemi su cui decidere

• Un agente può acquisire informazioni incerte sull’ambiente

• Il problema non può essere descritto totalmente (mancanza di alcune informazioni / numero infinito di affermazioni possibili)

L’incertezza non è evitabile in mondi complessi, dinamici o inaccessibili.

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).

• Quando le regole sul dominio risultano incomplete in quanto ci sono “troppe” condizioni da enumerare esplicitamente o alcune condizioni sono ignorate.

Conoscenza incerta

Caso della diagnosi ( in qualunque settore, necessità di prendere una decisione con conoscenza incerta)

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:

• 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.

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 e ragionamento con incertezza

Teoria della probabilità fornisce le basi per il trattamento di sistemi che ragionano con

incertezza: assegna un valore, tra 0 ed 1, di credenza nella formula

La probabilità esprime l’incapacità dell’agente di raggiungere una decisione definita a proposito della verità di una formula e riassume le credenze di un agente.

Teoria dell’utilità pesare la desiderabilità degli obiettivi e la probabilità di

raggiungerli (in quanto le azioni non sono più certe del raggiungimento degli obiettivi)

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 rispetto alla verità/falsità della formula

Il “grado di verità” è oggetto della logica fuzzy

Teoria della probabilità

A cosa si applica la teoria delle probabilità?

All’incertezza - Alle possibilità

Nella teoria delle probabilità, gli enunciati non si riferiscono direttamente al mondo, bensì esprimono la conoscenza dell’agente.

Il vantaggio principale del ragionamento probabilistico rispetto a quello logico consiste nel permettere all’agente di giungere a decisioni razionali anche quando non vi è abbastanza informazione per dimostrare che qualsiasi azione data funzionerà.

Teoria della probabilità

La teoria della probabilità assume la stessa assunzione ontologica della logica:

i fatti del mondo sono: veri o no

(con una certa probabilità)

Teoria della probabilità

Un valore di probabilità esprime il valore percentuale

a% di casi -indistinguibili tra loro- e considerati veri.

Il valore di probabilità è calcolato con:• metodi statistici• regole generali• regole basate su informazioni ambientali

estemporanee

Definizioni di probabilità

• Approccio oggettivista o frequentista

che considera la probabilità come un’entità misurabile, legata alla frequenza di accadimento (origine statistica) di un evento

• Approccio soggettivista

che considera la probabilità una misura del grado di attesa soggettivo del verificarsi di un evento (schema delle scommesse) ed ha origine cognitiva

Semantica degli enunciati di probabilità

Nella logica del primo ordine ed in quella proposizionale, una formula è vera o falsa a seconda dell’interpretazione del mondo.

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 (percezioni ricevute sino a quel momento)

Teoria della probabilità

Probabilità a priori o incondizionata (prima dell’acquisizione 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 conseguenze tra quelle possibili!!!).

Teoria dell’utilità

La teoria dell’utilità permette di rappresentare le preferenze dell’agente.

Ogni stato ha un grado di utilità ( = qualità dell’esser utile) per un agente; l’agente preferirà di volta in volta stati con utilità più alta per lui.

L’utilità non è una proprietà 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 probabilità + Teoria dell’utilità

=

Teoria delle decisioni

Teoria delle decisioni

Necessità di un linguaggio formale per rappresentare e ragionare con la conoscenza incerta

Necessità di gestire formule con un valore di credenza assegnato e la dipendenza di tale valore di credenza dalla conoscenza dell’agente

Agente basato sulla teoria delle decis.

Teoria delle decisioni

L’influenza dell’esperienza dell’agente si manifesta nella distinzione sintattica tra

• gli enunciati della probabilità a priori e • gli enunciati della probabilità condizionata che

comprende le prove

Estensione della logica proposizionale

Probabilità a priori P(A)

P(A) è la probabilità incondizionata o a priori che l’evento/proposizione A sia vero 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 casuali.

Probabilità a priori P(A)

P(Tempo= Soleggiato)=0.7

P(Tempo= Piovoso)=0.2

P(Tempo= Nuvoloso)=0.08

P(Tempo= Nevicate)=0.02

Variabili casuali

Le variabili casuali denotano le caratteristiche del dominio di interesse

Ogni variabile casuale X può assumere valori possibili (x, y,…z) in un dominio predefinito

Quando si ha un vettore di valori per le probabilità di ogni singolo stato, si parla di

distribuzione di probabilità.

Teoria della probabilità

Le funzioni di probabilità devono soddisfare le seguenti proprietà:

1. Assumere un valore compreso tra 0 ed 1

2. La sommatoria su tutti i valori possibili delle variabili deve essere pari ad 1

3. La probabilità di proposizioni necessariamente vere deve essere 1, quella di proposizioni necessariamente false deve essere 0

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; è una specifica completa dello stato del dominio.

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à condizionata

E’ possibile fare inferenze a proposito della probabilità di una proposizione ignota A, data la prova B, calcolando P(A/B) (probabilità di A dato che tutto ciò che sappiamo è B) (inferenza probabilistica)

Un’interrogazione ad un sistema di ragionamento probabilistico chiederà di calcolare il valore di una particolare probabilità condizionata.

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(A,B)=P(A/B)P(B)

fornisce la probabilità congiunta delle variabili nei domini di variabilità delle variabili casuali.

P(A) e P(B) sono prob. incondizionate

P(A/B) = P (A ^ B) P(B)

•Probabilità di un evento P(A)

•Probabilità congiunta P(a,b,c,…n)

•Probabilità condizionata a posteriori

Assiomi della teoria della probabilità

0 < P (A) < 1

P(VERO) = 1 P(FALSO) = 0

P (A v B) = P(A) + P(B) – P(A ^ B)

Probabilità

Proprietà della teoria della probabilità

P(A) + P( ¬ A) = 1

P( ¬ A) = 1 – P(A)

P(A v ¬ A) = P(A) + P( ¬ A) – P (A ^ ¬ A)

P (Vero) = P(A) + P( ¬ A) – P (Falso)

Assiomi

Gli assiomi di probabilità

• costituiscono un punto di riferimento fisso (e stabile) per il ragionamento

• costituiscono un limite alle credenze probabilistiche che un agente può avere

• proteggono il ragionamento probabilistico da credenze contraddittorie dell’agente

Regola di Bayes

P(A^B)=P(A/B)P(B)

P(B^A)= 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

Esempio

Supponiamo di vivere a Londra e di aver notato che in inverno:•piove (P) il 50% delle volte (p(P)=0.5) •è nuvoloso (N) l’80% delle volte (p(N)=0.8)•talvolta è nuvoloso ma non piove.

D’altra parte, il 100% delle volte in cui piove è anche nuvoloso (p(N|P)=Vero=1).

Qual è la probabilità che piova quando è nuvoloso (p(P|N))?Per la regola di Bayes si ha:   p(P|N) = p(P)p(N|P)/p(N) = 0.5 x 1.0 / 0.8 = 0.625 = 5/8.

Quindi 5/8 a Londra, quando è nuvoloso, piove.

Reti Bayesiane

Le reti Bayesiane sono modelli grafici della conoscenza in un dominio incerto. Basandosi sulla regola di Bayes, esprimono relazioni di dipendenza condizionale (archi) tra le variabili in gioco (nodi).

Il vantaggio principale del ragionamento probabilistico rispetto a quello logico sta nella possibilità di giungere a descrizioni razionali anche quando non vi è abbastanza informazione di tipo deterministico sul funzionamento del sistema (situazioni di incertezza).

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.

Come catturare conoscenza incerta

Assegnazione di valori di probabilità:

• Partendo da misure di frequenza (di valori di variabili) effettuate su molti casi reali (frequentisti)

• Analizzando aspetti reali per cui le misure di probabilità sono valori intrinseci di un oggetto (oggettivisti)

• Estrinsecando le credenze di un agente (soggettivisti)

Calcolo della probabilità

Come si calcola la probabilità di un evento futuro?

Probabilità indefinita (non è stato mai possibile effettuare una misura)

Probabilità = 1 (misure di eventi analoghi passati hanno dato sempre valore certo; =0 se sempre falso)

Probabilità = 1-e (per considerare un evento imponderabile)

Probabilità funzione di altre conoscenze associabili (soggettività)

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 variabili, si usano le reti di credenza come struttura dati. Permettono anche di specificare concisamente le distribuzioni di probabilità congiunta. Le probabilità riassumono un insieme potenzialmente infinito di possibili circostanze

Rete di credenza

Una rete di credenze è un grafo orientato aciclico (DAG) in cui:• i nodi sono un insieme di variabili casuali• archi direzionali congiungenti coppie di nodi rappresentano

l’influenza diretta di una variabile su un’altra; se c’è un arco dal nodo X al nodo Y si dice che X è parent di Y

• il grafo non ha cicli• ad ogni nodo è associata una tabella (distribuzione) di probabilità

condizionata che esprime gli effetti dei nodi che lo influenzano (nodi parent/predecessori)

P(Xi | Parents (Xi))

Le reti bayesiane sono chiamate anche reti causali, perché gli archi che connettono i nodi possono essere visti come se rappresentassero relazioni causali dirette

Rete di credenza

Una rete bayesiana (di credenza) richiede che ogni nodo del grafo sia

condizionatamente indipendente

da qualsiasi sottoinsieme di nodi che non siano discendenti dei predecessori diretti del nodo stesso

Rete di credenza

Si affida ad un esperto di dominio la definizione della topologia della rete di credenze (quali nodi e quali relazioni condizionali di dipendenza), poi si calcolano le influenze dirette e le conseguenti probabilità

Ciò equivale a definire la conoscenza del mondo in cui può avvenire un evento

La rete rappresenta le assunzioni che si effettuano su quel dominio. Le probabilità condizionate tra i nodi riassumono un insieme potenzialmente infinito di circostanze a noi ignote e che potrebbero influenzare l’evento.

Rete di credenza

La topologia della rete è la base di conoscenza, generale ed astratta, dell’ambiente in cui si possono verificare gli eventi

Rappresenta la struttura generale del processo causale nel dominio, piuttosto che fornire dettagli su un particolare elemento.

Nelle reti bayesiane gli archi che connettono i nodi esprimono le relazioni causali dirette

(causa -> effetto)

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 produttoria delle prob. condiz.)

Un nodo con nessun genitore è rappresentato dalla probabilità a priori

Rete di credenza

La topologia della rete codifica le asserzioni di indipendenza condizionale

• Weather è indipendente dalle altre variabili

• Toothache e Catch sono condizionalmente indipendenti data Cavity (ognuna dipende da Cavity ma non c’è relazione causale tra le due)

cavity: carie/cavità; toothache:mal di denti; catch:trappola –tra l’altro-

Esempio

Rete di credenze con le probabilità condizionate

Probabilità di un evento

La probabilità congiunta P(a,b,c,..n) è data dal prodotto degli elementi appropriati delle tabelle di probabilità condizionate associate alla rete di credenze.

P(evento)=P(x1, x2,…xn)=∏ P(xi|Parent(Xi))

Poiché la rete di credenze è una rappresentazione della distribuzione congiunta, può essere usata per rispondere ad una interrogazione

Probabilità di un evento

Esempio: qual è la probabilità che l’allarme sia partito ma non è stato né per un ladro, né per un terremoto ed hanno telefonato sia John che Mary?

P(J^M^A^¬ B^¬ E)

=P(J|A)P(M|A)P(A|¬B^¬E)P(¬B)P(¬E)

=0.90x0.70x0.001x0.999x0.998=0.00062

Costruz. incrementale rete di credenza

1. Identificare un insieme di variabili rilevanti Xi che descrivano il dominio

2. Scegliere un ordinamento tra le variabili (necessario per ottimizzare la rete, causa-effetto)

3. Finché rimangono variabili:– Prendere una Xi ed aggiungere un nodo alla rete– Scegliere l’insieme minimo di genitori di Xi indipendenti

condizionalmente tra loro– Definire la tabella delle proprietà condizionate per Xi.

Garantire la compattezza della rete.

Costruz. incrementale rete di credenza

In un sistema localmente strutturato (rete di credenza) ogni sottocomponente interagisce direttamente solo con un numero limitato di altre componenti, indipendentemente dal numero totale di componenti

La probabilità condizionata di un nodo rispetto ai suoi genitori esprime tutto ciò che si deve sapere sulle influenze sul nodo di tutti i suoi predecessori

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.

Inferenza nelle reti di credenze

Inferenza causale o top-down (dalle cause agli effetti)

Inferenza diagnostica (dagli effetti alle cause)

Inferenza mista

Inferenza causale o top-down

Operazioni principali:

• Riscrivere la probabilità condizionata desiderata per il nodo di interrogazione V data l’evidenza in termini delle probabilità congiunte e di tutti i suoi genitori (che non fanno parte dell’evidenza), data l’evidenza

• Riesprimere queste probabilità congiunte di nuovo con la probabilità di V condizionata a tutti i genitori

Inferenza diagnostica

Ruoli di interrogazione ed evidenza rovesciati rispetto alla inferenza causale

Si usa un effetto per inferire una causa

Si usa la regola di Bayes per convertire il problema diagnostico in un problema di ragionamento causale

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. Decidere di cosa parlare2. Decidere un vocabolario delle variabili

casuali (ed i relativi valori possibili)3. Codifica delle conoscenza generale per le

dipendenze fra le variabili4. Descrivere l’istanza specifica del problema5. Interrogare la procedura di inferenza ed

ottenere risposte