Parte 1: Ragionamento Approssimato

(1)

Console, Botta - Dip Informatica, Univ. Torino Ragionamento approssimato 1

Approximate reasoning

• Necessità di prendere decisioni in casi di informazione (conoscenza)

parziale è comune in A.I.

– Conoscenza incompleta (qualification problem) Esempi

• ignoranza teorica: modelli per evoluzione malattia per diagnosi medica • ignoranza “pratica”: modelli non sarebbero utilizzabili (ad esempio per

impossibilità di misurazione) • problemi di complessità dei modelli – Conoscenza imprecisa

Esempi

• modelli approssimati (o qualitativi)

– per necessità (troppo complicati)

– per utilità (mancherebbero dati per quelli precisi)

• imprecisione nella misurazione

• Agente deve poter operare con conoscenza incompleta e imprecisa

• Teoria delle decisioni

oltre alle informazioni imprecise su teoria e dati: – utilità delle decisioni (azioni)

– costo/rischio delle decisioni (azioni) – preferenze

• Metodi di ragionamento approssimato

varie tecniche proposte in A.I. a partire dagli anni ‘70 – approcci qualitativi (logici o linguistici)

• logiche non monotone – approcci quantitativi (numerici)

• approcci basati su teorie matematiche – probabilistici

– fuzzy logic – Dempster-Shaefer • approcci euristici

(2)

Ragionamento probabilistico

Richiami di calcolo delle probabilità

• Variabile casuale X con dominio D

– discreto: {x1, x2, …, xn} – continuo

• Distribuzione di probabilità a priori P(X) per X

– discreto: P(X) = {v1,v2, …, vn} con

Σ

vi=1 – continuo: funzione con integrale che vale 1 nel seguito analisi del caso discreto

– distribuzioni a priori anche di eventi complessi • P(X, Y) ossia P(X ∧ Y)

• Probabilità condizionali

– date due variabili X e Y

P(X | Y) = “probabilità di X dato Y” P(X=xi | Y=yj)

matrice bidimensionale

– Definizione a partire da probabilità a priori P( X | Y ) =

• Assiomi del calcolo delle probabilità

– 0 ≤ P(x) ≤ 1

– P(true)=1, P(false)=0

– P(X ∨ Y) = P(X) + P(Y) - P(X ∧ Y)

• Distribuzione di probabilità congiunta (Joint)

– dato un insieme X1, X2, …, Xm di variabili

– evento atomico è assegnazione di un valore ad ognuna delle variabili – P(X1, X2, …, Xm ) assegna un valore ad ogni possibile evento atomico

matrice m-dimensionale (con somma 1)

– se ci sono molte variabili con domini con molti valori si ha un numero molto grande di probabilità che devono essere specificate

P(X ∧ Y) P(Y)

(3)

– Esempio X=malDiDenti Y=carie

– A partire da Joint si possono calcolare probabilità a priori di vari eventi Esempi • P(carie) = 0.06 + 0.04 = 0.1 • P(carie ∨ malDiDenti) = 0.1 + 0.05 - 0.04 = 0.11 • P(carie ∧ malDiDenti) = 0.04 • P(carie | malDiDenti) = = = 0.8 • P(malDiDenti| carie) = = = 0.4 carie ¬carie malDiDenti ¬ malDiDenti 0.04 0.01 0.06 0.89 P(carie ∧ malDiDenti) P(malDiDenti) 0.04 0.05 P(carie ∧ malDiDenti) P(carie) 0.04 0.1

Il Teorema di Bayes

da P(X ∧ Y) = P(X | Y)*P(Y) = P(Y | X)* P(X), si ha: P(Y | X) =

intuizione:

date probabilità a priori di causa (Y) ed effetto (X) e la probabilità condizionale dell’effetto data la causa P(X | Y), possiamo calcolare la probabilità della causa dato l’effetto

Esempio

P(carie | malDiDenti) = = 0.8

uso “diagnostico” della teoria delle probabilità P(X | Y)*P(Y)

P(X)

P(malDiDenti | carie)*P(carie) P(malDiDenti)

(4)

• Update di belief usando il teorema di Bayes

– grado di belief in un evento

– aumentato (diminuito) man mano che arrivano osservazioni Esempio

• eventi carie, malDiDenti e denteBucato

• belief iniziale in carie (prior), aumentato dalle altre osservazioni – Regola di bayes in forma di update

P(carie | malDiDenti) = P(carie) *

consente aggiornamento di belief su evento “carie” – con più osservazioni diventa:

P(carie | malDiDenti∧ denteBucato) = P(carie) * * P(malDiDenti | carie)

P(malDiDenti)

P(malDiDenti | carie) P(malDiDenti) P(denteBucato | malDiDenti ∧carie)

P(denteBucato | malDiDenti) *

– Problemi

• c’è bisogno di probabilità condizionali P(denteBucato | malDiDenti∧ carie) • il numero di queste probabilità condizionali aumenta enormemente quando si

devono tenere in considerazione più osservazioni • oppure si deve disporre della Joint

– Questo ha portato negli anni ‘70 ad abbandonare l’approccio probabilistico per la gestione dell’incertezza nei sistemi esperti – In realtà esiste una via di uscita: le indipendenze condizionali

• Conditional independence

– su esempio

• carie è la causa diretta sia di malDiDenti che di denteBucato

• se paziente ha la carie, la probabilità di denteBucato non dipende da quella di malDiDenti

• anche: dato denteBucato, questo non modifica la probabilità che carie causi malDiDenti

in altri termini: malDiDenti e denteBucato sono condizionalmente indipendenti dato carie

(5)

In termini matematici:

• P(denteBucato | carie ∧ malDiDenti) = P(denteBucato | carie) • P(malDiDenti | carie ∧ denteBucato) = P(malDiDenti | carie)

– In questo modo si elimina la necessità di disporre delle varie probabilità condizionali

– In generale, dato evento Z e dati X e Y che sono condizionalmente indipendenti dato Z, si ha la seguente regola di update:

P(Z | X, Y ) = αP(Z) * P(X | Z) * P(Y | Z) dove α è un fattore di normalizzazione

– vedremo reti Bayesiane che sfruttano queste proprietà

• Osservazione

rimane ancora un problema: da dove arrivano le probabilità (prior e condizionali) che servono?

– varie possibilità

• soggettive (da esperto) • oggettive (da esperimenti) • basate su analisi di frequenze

– Critica dei sostenitori di approccio euristico (e altri, es. fuzzy) – Sensitivity analysis: quanto risultati dipendono dai numeri?

Reti Bayesiane (o belief network)

• Proposte da Pearl verso la metà degli anni ‘80 [Pearl, 88]

• Rappresentazione esplicita delle indipipendenze condizionali

• Rappresentazione compatta della Joint, date le indipendenze

• Rete = grafo aciclico

– nodi: variabili aleatorie

– archi: influenza (dipendenza) tra variabili Esempio [Pearl]

archi mancanti: indipendenza condizionale: es maryTelefona e terremoto sono condizionalmente indipendenti dato allarme

rapina terremoto

allarme

(6)

Ad ogni nodo è associata tabella delle probablità condizionali dai suoi predecessori (ai nodi iniziali sono probabilità incondizionali, ossia a priori)

rapina terremoto

allarme

JohnTelefona MaryTelefona

P(rapina)

0.01 P(terrem)_0.02

rapina terrem P(allarme | rapina, terrem) F F 0.001 F T 0.29 T F 0.94 T T 0.95 P(JohnTelefona | allarme) allarme F 0.05 T 0.90 P(MaryTelefona | allarme) allarme F 0.01 T 0.70

• Rete è una rappresentazione compatta della Joint

dati nodi X1, … Xn, si ha che

P(X1=x1, .., Xn=xn) =

Π

P(xi | predecessori(Xi)) Esempio

P(JohnTelefona, MaryTelefona, allarme, ¬rapina, ¬ terremoto) = P(JohnTelefona | allarme) * P(MaryTelefona | allarme) *

P(allarme | ¬rapina, ¬ terremoto) * P(¬rapina) * P(¬ terremoto) = 0.00062

• Costruzione di una rete Bayesiana

– individuare le variabili – ordinarle

– fino a che ci sono variabili • selezionare una variabile Xi

• predecessori(Xi) = minimo insieme delle variabili già selezionate per cui P(Xi | X1, .., Xn) = P(Xi | predecessori(Xi))

• definire tabella probabilità condizionali per Xi

(7)

Inferenza nelle reti Bayesiane

• Inferenza di base:

– dati valori per alcune variabili: evidence variables

– trovare la distribuzione di probabilità per altre variabili: query variables

• Quattro forme di inferenza

– Inferenza diagnostica • evidence variables: effetti • query variables: cause

• Esempio: P(rapina | JohnTelefona) = 0.016 – Inferenza causale

• evidence variables: cause • query variables: effetti

• Esempio: P(MaryTelefona | rapina) = 0.67 – Inferenza intra-cause

• evidence variables su effetti e su altre cause • Esempio

– P(rapina | allarme) = 0.376

– P(rapina | allarme ∧ terremoto) = 0.003

– Inferenze miste

• varie combinazioni di quelle sopra • Esempi

– P(allarme | JohnTelefona∧ ¬terremoto) = 0.03 – P(rapina | JohnTelefona∧ ¬terremoto) = 0.017

• Altre forme di inferenza

– sensitivity analysis: analizzare effetto di piccole modifiche alle probabilità condizionali

– decidere quale nuova osservazione fare per definire probabilità di un insieme di nodi (o per discriminare)

• Algoritmi

– algoritmi di propagazione

• molto efficienti su reti singly-connected o poly-trees (ogni coppia di nodi ha un solo cammino che le collega)

• più complesso in altre reti

(8)

Applicazioni delle reti Bayesiane

• Molte applicazioni

– modelli causali o modelli di sistemi fisici • simulazione

• diagnostica • ...

– modelli di processi – grafi di decisione

• Strumenti per operare con reti Bayesiane

– tools per

• progettare una rete • algoritmi di inferenza

Esempio

• Se osservo fever allora calcolo probabilità di cold e pneumonia come

spiegazioni di fever (aggiorno le prior delle due malattie)

• se osservo fever e sneezing avrò probabilità di cold che sale e quella di

pneumonia che scende

cold

_cold

pneumonia

_pneumonia

fever

_fever

sneezing

_sneezing

p1

p3 p2

(9)

Altre forme di approximate reasoning

• Critiche all’approccio probabilistico

– troppe informazioni richieste (prior e condizionali) con vincoli matematici forti sui loro valori

– un numero rappresenta solo alcuni aspetti dell’incertezza

– si hanno probabilità ma su eventi definiti in modo crisp e non vago Es. P(influenza | febbre(alta)), ma febbre(alta) è evento che osservo in modo assolutamente preciso?

• Altri approcci numerici per rispondere a queste critiche

• rappresentare ignoranza: la teoria di Dempster-Shafer • rappresentare vaghezza: la logica fuzzy

• approcci euristici

• Approcci non-numerici:

– non monotonic-reasoning

– teoria degli endorsement: tenere traccia delle informazioni a supporto o contro un certo evento

La teoria di Dempster-Shafer

• Probabilità è un numero e non si può rappresentare ignoranza su evento

– diverso dire

• P(A)=0.5 Sicuramente

• P(A)=0.5 a meno di un errore del 30% – Esempio

• 3 situazioni A, B e C a priori equiprobabili per cui non ho nessuna informazione a supporto o contro

– stima P(A) = P(B) = P(C) = 0.33

0.33 in se però non dice molto a questo punto

• dopo aver raccolto osservazioni pro e contro A, concludo che – P(A) =0.33

• stesso numero, ma

– prima non avevo nessuna informazione, ignoranza completa – ora numero basato su informazione

(10)

• Teoria DS associa ad ogni evento un intervallo che misura sia la

probabilità dell’evento che l’ignoranza su tale probabilità

• Definizione

– Dato un evento (proposizione) A – si associa ad A un intervallo

[Belief, Plausibility] in cui

• Belief misura evidenza a favore dell’evento, compresa tra 0 e 1 • Plausibility(A) = 1- Belief(¬A)

– Si può vedere che in questo modo l’intervallo misura l’ignoranza, ossia tanto più l’intervallo è largo, tanto più sono ignorante su A

– Casi estremi

• A evento certo: Belief(A)=1, Belief(¬A)=0 ⇒ [1, 1]

• A evento certamente falso: Belief(A)=0, Belief(¬A)=1 ⇒ [0, 0]

• ignoranza completa su A: Belief(A)=0, Belief(¬A)=0 ⇒ [0, 1]

– Intervallo definisce il range in cui il il grado di evidenza a favore di A deve cadere

– Esempio

• 3 situazioni A, B e C a priori equiprobabili per cui non ho nessuna informazione a supporto o contro

– stima iniziale DS(A) = DS(B) =DS(C) = [0, 1] ignoranza completa sul mondo

• dopo aver raccolto osservazioni pro e contro A, concludo che – DS(A) = [0.33, 0.33] DS(B)=[0.1, 0.9] DS(C)=[0.4, 0.5]

• Teoria di Dempster-Shafer complessa

– permette di associare grado di belief non solo a eventi ma anche ad insiemi di eventi

(11)

La logica fuzzy

• Probabilità e DS basati su teoria matematica degli insiemi e su logica

classica

– appartenenza di evento a insieme è definita in modo crisp, senza possibilità di interpretazione vaga

– Esempio

P(influenza)=0.1 P(influenza | febbre(alta)) =0.6 ma poi frebbre(alta) è vero o falso in modo preciso – limitativo in molti casi, specie con descrizioni linguistiche

• Fuzzy logic

– modificare i concetti di insieme con definizioni vaghe (fuzzy set) – modificare il concetto di appartenenza (membership) ad un insieme, non

solo vero o falso, ma grado di appartenenza

– definire una nuova logica che gestisca questi gradi di appartenenza numerici (fuzzy logic)

– fare in modo che la nuova logica sia estensione consistente di quella classica

Fuzzy set

• Insiemi (in teoria degli insiemi) definiti in modo preciso

• Per ogni insieme S e individuo i, si ha che i∈ S è vero o falso

• Supponiamo di definire insieme “persone alte”

– è facile definirlo in modo non vago? • Ossia se John è alto 1.80, è o no nell’insieme – problematico

• termini linguistici sono vaghi

• in ogni caso ci serve poter dare un grado di appartenenza di individui agli insiemi

– Insieme definito a partire da caratteristica (valore dell’altezza); definizione logica deve essere del tipo

0 1 vero falso altezza 1.80

(12)

• Possibilità di definire questi insiemi in modo “vago”

la curva intera definisce l’insieme fuzzy “alto” quella tratteggiata l’insieme fuzzy “moltoAlto”

• Gradi di appartenenza (membership) in insieme fuzzy

– John alto 1.80

µ(alto(John)) = 0.9 µ(moltoAlto(John)) = 0.8

• Fuzzy set “normali” (importanti in molte applicazioni)

• Es.

febbre(alta) febbre(altissima) 0 1 vero falso altezza 1.80 0 1 vero falso 37 38 39 40

• Membership permette di assegnare valore di verità tra 0 e 1 a

proposizioni semplici (esattamente come appartenenza a insieme

assegna valore vero o falso agli atomi in logica classica)

• Logica per combinare valori di verità fuzzy (corrispondente alla tabelle

di verità della logica classica)

• Varie definizioni possibili

– insieme di condizioni che devono essere rispettate

– estensione consistente della logica classica (ossia deve ridursi a logica classica se i valori di membership si riducono a 0 e 1)

– deve rispettare insieme di proprietà (es. distributiva, DeMorgan, …)

• Connettivi Logici

– Negazione • T(¬A) = 1-T(A) – Congiunzione

Una qualunque T-norm • 1 elemento neutro • 0 elemento di annullamento • T(A ∧ B) ≤ T(A) ≤ T(B)

(13)

Ad esempio

• T(A ∧ B) = T(A) * T(B) • T(A ∧ B) = min(T(A), T(B)) – Disgiunzione

una t-co-norm, duale di quella scelta per la congiunzione Ad esempio

• T(A ∨ B) = T(A) + T(B) - T(A) * T(B) • T(A ∨ B) = max(T(A), T(B))

– A partire da questi si possono definire i vari connettivi

– Attenzione: non per tutte le definizioni si ha una estensione consistente della logica classica

• Applicazioni

– domini in cui è necessario gestire variabili linguistiche • classificazione, diagnosi, interpretazione, information retrieval,… molti sistemi basati sulla conoscenza usano la logica fuzzy come meccanismo di gestione della incertezza

• Fuzzy controllers

– in molti elettrodomestici e sistemi di uso corrente

Approcci euristici

• Probabilità richiedono

– molte stime da fornire in fase di costruzione di una K.B. (e stime che rispettassero gli assiomi del calcolo delle probabilità)

– complessità computazionale nella gestione

• Anni ‘70 costruzione di sistemi esperti

– necessità di ragionamento approssimato

– proposta di approcci euristici come compromesso tra

• semplificare la costruzione di K.B. e la gestione rispetto agli approcci probabilistici

• mancanza di un fondamento teorico per i risultati

• vari approcci

vedremo approccio basato su Certainty Factors proposto nel sistema

Mycin [Shortliffe 76]

• Conoscenza rappresentata mediante regole di produzione del tipo

(14)

• Tre caratteristiche (assunzioni) che sono fondamentali nel definire il

meccanismo di gestione incertezza

– località

ogni regola è un pezzo di conoscenza indipendente dalle altre e permette inferenza indipendentemente dalla altre

– detachment

una volta concluso un fatto F con una regola, F può essere usato in altre inferenze indipendentemente da come si è arrivati alla sua deduzione

Oss: si noti che questo non è vero in generale nel calcolo delle probabilità

– truth-functionality

la verità di una frase complessa può essere determinata usando solamente la verità delle sue componenti

Oss: si noti che anche questo nel caso delle probabilità non è vero (è vero solo con forti assunzioni di indipendenza)

regole sono conoscenza modulare

• Sfruttare queste assunzioni nel definire meccanismo di gestione incertezza

• Tre concetti nel definire il meccanismo dei certainty factors

dato fatto H

– MB(H, E) misura di belief in H apportata da E, in [0,1] – MD(H , E) misura di disbelief in H apportata da E, in [0,1] – CF(H, E) = MB(H, E) - MD(H, E)

Si ha quindi

– H sicuramente vero MB(H, E)=1, MD(H, E) = 0, CF(H,E)=1 – H sicuramente falso MB(H, E)=0, MD(H, E) = 1, CF(H,E)=-1 – CF(H, E) = 0 incertezza assoluta su H

• Certainty factor associato alle regole

if <antecedente> then (CF) <conclusione> grado con cui si può incrementare belief in <conclusione> se <antecendente> è vero

Esempio [Mycin]

if the organism is gram-positive AND the morphology of the organism is coccus AND the growth of the conformation of the organism is chains then there is a suggestive evidence (0.7) that the identity of the organism

(15)

Regole di combinazione evidenza

• Tre situazioni

– Condizioni logiche in antecedente di una regola • CF(A ∧ B, E)

• CF(A ∨ B, E)

– Regola di combinazione evidenze • CF( A, E1 ∧ E2)

– Chaining rule

come calcolare grado di certezza su conseguente dati i gradi di certezza su antecedente e su regola CF(C,B) a partire da CF(B,E) e y A E2 E1 E B C y

• Condizioni logiche: sfruttare truth functionality

– CF(A ∧ B, E) = min[CF(A,E), CF(B,E)] – CF(A ∨ B, E) = max[CF(A,E), CF(B,E)]

• Combinazione di evidenze multiple

siano X= CF(A, E1) e Y=CF(A,E2) intuizione:

– approccio additivo, si aggiunge (toglie) a X quanto manca a 1 (-1) in proporzione a Y

X + (1-X)*Y se X>0 e Y> 0 CF( A, E1 ∧ E2) = X + (1+X)*Y se X<0 e Y< 0

(X + Y) / (1 - min[|X|, |Y|]) A

E2 E1

(16)

• Chaining rule

CF(C, B) = y* max [0, CF(B, E)]

– intuizione: si interpreta fattore di certezza y della regola come l’apporto al grado di certezza di C dato da B, se B vero

– quindi l’apporto sarà in proporzione al grado di certezza di B – max [0, CF(B, E)] in quanto le regole sono regole “a favore” della

conclusione e non regole “contro” (altro tipo di conoscenza) e quindi non portano evidenza contro C

• Queste regole definiscono un meccanismo completo di gestione

dell’incertezza

– facile da gestire computazionalmente – richiede

• gradi di certezza alle regole: in Mycin (ed altri) soggettivi da esperti • MB e MD sui fatti E B C y

• Esempio1

– fatti • A con CF(A)=1 • B con CF(B)=1 – regole • r1: if A then (0.8) C • r2: if B then (0.6) C • r3: if C then (0.5) D

– usando r1 concludo C con CF(C)=0.8 (chaining rule)

– usando r2 concludo C con CF(C)=0.6 (chaining rule)

• quindi CF(C) = 0.8 + (1-0.8)*0.6 = 0.92 (combinazione di evidenze) – usando r3 concludo D con CF(D) = 0.46

(17)

• Esempio2

– fatti • A con CF(A) = 0.7 • B con CF(B) = 0.8 • C con CF(C) = 0.9 – regole • r1: if A∧ B then (0.8) W • r2: if B∨ C then (0.6) Z • r3: if W then (0.5) K • r4 if Z then (1) K

– r1: CF(A∧ B) = min [CF(A), CF(B)] = 0.7 quindi concludo W con CF(W)=0.56 – r2: CF(B ∨ C ) = max [CF(B), CF(C)] = 0.9

quindi concluso Z con CF(Z)=0.54 – usando r3 concludo K con CF(K)=0.28 – usando r4 concludo K con CF(K)=0.54

• quindi CF(K) = 0.28 +(1-0.28)*0.54 = 0.6688

• Osservazioni

– approccio usato con successo in molti sistemi • Mycin

• da Emycin a varie applicazioni

– i numeri associati alle regole derivano da valutazione soggettiva degli esperti

• problemi nel determinare i numeri

• risultati sorprendenti nel caso di Mycin da prove di sensitivity analysis: i risultati non cambiavano troppo anche cambiando i CF delle regole in modo significativo

– mancanza di base teorica, ma

tentativo di ricostruzione teorica del metodo da parte di Shortliffe • relazione tra certainty factors e probabilità (vedi prossima slide) – modularità di esecuzione basata su assunzioni di indipendenza

• grande differenza dal calcolo delle probabilità

• problemi quando le regole sono scritte in modo tale che le assunzioni non sono vere

(18)

• Ricostruzione probabilistica

CF(H,E) = MB(H,E) - MD(H,E) ≈ P(H | E)

• Differenze fondamentali da approccio probabilistico

– detachment – locality – modularity 1 se P(H)=1 max[P(H|E), P(H)] - P(H) 1 - P(H)

{

MB(H, E) 1 se P(H)=0 min[P(H|E), P(H)] - P(H) 0 - P(H)

{

MD(H, E)