Bayesian NetworkBayesian Network

Uno strumento per trattare l’incertezzaUno strumento per trattare l’incertezza

Christian La Rocca

Informatica Industriale

A.A. 2001/2002

2

Problemi delle Reti Neurali

• Necessità di una grossa mole di esempi per addestrare la rete.

• Apprendimento “statico”.

• “….they won’t help predict the unforeseen”.

3

L’essenza dell’approccio Bayesiano

Probabilità classica

Proprietà fisica del mondo reale ( ad es. la probabilità che lanciando una moneta esca testa ) .

Probabilità Bayesiana

Proprietà della persona che assegna la probabilità ( la % di teste e croci che secondo me usciranno).

4

L’essenza dell’approccio Bayesiano

Che pb hanno i Chicago Bulls di vincere la prossima NBA?

5

L’essenza dell’approccio Bayesiano

Critiche

Le pb sono arbitrarie

Perché le credenze devono soddisfare le regole del calcolo delle probabilità ?

Con che precisione possono essere misurate le probabilità?

6

Definizione di una BBN(Bayesian Belief Network)BBN=Grafo aciclico + CPT(CPD).

Nodi= Variabili (discrete o continue)

Archi= Relazioni causali fra le variabili.

Attraverso essa è possibile modellare e ragionare su ciò che è incerto.

7

Es.di BBN

Famiglia uscita

Si sente un latrato

Il cane èfuori

Problemi intestinali

Luce accesa

8

Es.di BBN

Cloudy

SprinklerRain

Wet grass

9

Es.di BBN

Train Strike

Norman lateMartin late

Norman late

True False

True 0,8 O,1

False 0,2 0,9

True False

True 0,6 O,5

False 0,4 0,5

Train strike Train strike

Train strikeTrue 0,1False 0,9M

arti

n la

te

Nor

man

late

10

Perché usare una BBN

Se usata insieme a tecniche statistiche da molti vantaggi per l’analisi dei dati:

Il modello codifica le dipendenze fra le variabili.

Può essere usata per imparare relazioni causali fra le variabili.

Siccome il modello ha una semantica sia probabilistica che causale può essere usato per combinare efficacemente conoscenza di esperti (prior knowledge) e dati.I metodi statistici Bayesiani insieme alle reti Bayesiane offrono un approccio efficiente per evitare l’overfitting.

11

Analisi di una BBN

Una volta inserite le probabilità possiamo utilizzare la rete ad es. per:

1. Calcolare la probabilità incondizionata che un evento accada.

2. Rivedere le probabilità assegnata alla luce di ciò che è successo.

12

Train Strike

Norman lateMartin late

Train strikeTrue 0,1False 0,9

Es.di BBN

Norman late

True False

True 0,8 O,1

False 0,2 0,9

True False

True 0,6 O,5

False 0,4 0,5

Train strike Train strikeM

arti

n la

te

Nor

man

late

13

Analisi di una BBN

Supponiamo di sapere che Norman è arrivato in ritardo e vogliamo conoscere :

1. La probabilità (rivista) che vi sia uno sciopero dei treni:

47,0)(

)()()(

Normanlatep

eTrainstrikpeTrainstrikNormanlatepNormanlateeTrainstrikp

Train strikeTrue 0,1True 0,1False 0,9

14

Analisi di una BBN

La probabilità (rivista ) che Martin arrivi in ritardo:

55,0)()()()( ikeNotrainstrMartinlatepeTrainstrikpeTrainstrikMartinlatepMartinlatep

Quando si inseriscono delle EVIDENZE e si usano per aggiornare le probabilità si parla di PROPAGATION.

15

Evidenze e propagazione

Possiamo avere due tipi di evidenza:

• Hard evidence (instantiation) per un nodo X è il fatto che X abbia un valore definito. Ad es. supponiamo che X rappresenti il risultato di una partita . Un es. di Hard evidence è il fatto che la partita è vinta. In questo caso diciamo che X è instanziato al valore “Vittoria”.

• Soft evidence per un nodo X è ogni evidenza che ci permette di aggiornare la probabilità a priori della variabile X.Se sappiamo che stiamo vincendo 5-0 alla fine del primo tempo allora la probabilità di vincere la partita aumenterà a differenza di quelle di pareggiare e perdere che diminuiranno.

16

Evidenze e propagazione

Il modo con cui le informazioni si propagano dipende dal tipo di connessione.

Abbiamo tre tipi di connessioni in una BBN:

• Connessione seriale.

• Connessione divergente.

• Connessione convergente.

17

Evidenze e propagazioneConnessione seriale

GuastoTreno

in ritardoNorman in ritardo

A B C

Nella connessione seriale l’evidenza può essere trasmessa da A a C se B non è instanziato.A e C sono d-separated dato B.

18

Evidenze e propagazioneConnessione divergente

Train strike

Martin late Norman lateA

CB

Ogni evidenza su A è trasmessa sia ad B che a C. Supponiamo di non avere hard evidence su ASapere qualcosa su B incrementa le nostre conoscenze su A e di conseguenza anche su C. Se invece abbiamo hard evidence su A allora nessuna evidenza su B può cambiare le nostre conoscenze su C, infatti il valore di C è influenzato solo dalla certezza su A. Diciamo quindi che B e C sono CONDIZIONALMENTE DIPENDENDENTI ( DATO A).L’evidenza può essere trasmessa da B a C attraverso una connessione divergente A a meno che A non sia instanziata. B e C sono d-separated dato A

19

Martin oversleep

Martin late

Train delays

BC

A

Evidenza su B e C è trasmessa ad A .Se non sappiamo niente su A allora C e B sono indipendenti e quindi nessuna evidenza è trasmissibile da B e C. Se invece so qualcosa ( soft evidence) su A allora i suoi genitori diventano dipendenti. Supponiamo di non vedere il cappotto di Martin appeso all’appendiabiti in ufficio alle 9:00; ciò potrebbe essere un indizio (soft evidence ) che è in ritardo, e ciò fa aumentare le probabilità che vi sia un ritardo del treno o che non si sia svegliato in orario.. Diciamo quindi che B e C sono condizionalmente dipendenti ( su A). Quindi in una connessione convergente l’evidenza può essere trasmessa fra i genitori B e C quando il nodo convergente ha ricevuto qualche evidenza ( che può essere hard o soft).

Evidenze e propagazioneConnessione convergente

20

Due nodi X e Y in una BBN sono d-separated per tutti i percorsi da X a Y , se esiste un nodo intermedio A per il quale:

1. La connessione è seriale o divergente e lo stato di A è definito.

2. La connessione è convergente e né A né nessuno dei suoi nodi discendenti hanno ricevuto alcuna evidenza.

Evidenze e propagazioneNozione di d-separated

21

“Explaining away” evidence

Martin oversleeps Martin

late

Train srike

A B

C

Normanlate

Se so che Martin è in ritardo allora aumentano le probabilità di accadimento dei nodi A e B Il fatto che però è in ritardo anche Norman fa aumentare di molto le probabilità che ci sia uno sciopero dei treni. Si dice che il ritardo di Norman “spiega” quello di Martin.

22

“Explaining away” evidence

Brainy

college

Sporty

A

C

B

23

BBN per calcoli statistici

Una BBN rende esplicite le dipendenze fra le diverse variabili .In generale ci sono poche dipendenze dirette (modellate da archi fra i nodi della rete) e ciò sta a significare che molte delle variabili sono fra loro condizionalmente indipendenti. L’esistenza di nodi non connessi nella rete (indipendenza condizionale ) riduce drasticamente i calcoli necessari ad avere tutte le probabilità . In generale tutte le probabilità possono essere calcolate a partire dalla distribuzione di probabilità congiunta e quest’ultima è molto più facile da calcolare quando ci sono nodi condizionalmente indipendenti.

24

BBN per calcoli statisticiSecondo la teoria del calcolo delle probabilità se si hanno n variabili casuali binarie è necessario specificare 2 n -1 probabilità congiunte , quindi nel seguente esempio ne servirebbero 31 e non le 10 da noi specificate.

P(hb|do) = .7

P(hb | ¬ do) = .01

Famiglia uscita(fo)

Si sente un Latrato (hb)

Il cane èFuori (do)

Problemi intestinali (bp)

Luce accesa (lo)

P(do | fo bp) = .99

P(do | fo ¬ bp) = .90

P(do | ¬ fo , bp) = .97

P(do | ¬ fo bp) = .3P(lo | fo) = .6

P(lo | ¬ fo) = .05

P(fo) = .15 P(bp) = .01

25

Tipi di ragionamento permessi da una BBN

Quando utilizziamo una BBN siamo interessati a fare delle previsioni su quantità incerte in seguito ad alcune evidenze..I principali modi di ragionare sono :

• CAUSAL: effetti determinati da cause.

• STATISTICAL: probabilità di eventi determinata dalla popolazione dei possibili eventi ad es. la probabilità di un guasto determinata dal numero di pezzi e dal numero di guasti osservati.

• STRUCTURAL: fenomeni determinati dalla struttura da cui dipendono o dagli oggetti/eventi da cui dipendono. Ad es. guasto nel modulo X determinato da un errore introdotto dal modulo Y.

26

Probabilità consistentiProblema schema

probabilistico

Probabilitàincosistenti

P(a|b)=0,7 e P(b|a)=0,3 e P(b)=0,5. Th.Bayes P(a)>1

Rete Bayesiana•Le probabilità sono consistenti.•La rete definisce univocamente una distribuzione.

27

Apprendimento

Per descrivere completamente una BBN è necessario definire:

TOPOLOGIA del grafo (struttura)

I parametri di ogni CPD ( distribuzione di probabilità congiunta).

28

Metodi per trattare dati incompleti

NP-Hard Metodi Monte Carlo

Approssimazione Gaussiana

Approssimazione MAP e ML e algoritmo EM

29

Apprendimento. Possiamo trovarci di fronte quattro situazioni diverse:

1. Struttura nota, osservabilità completa.

2. Struttura nota, osservabilità parziale.

3. Struttura non nota, osservabilità completa.

4. Struttura non nota, osservabilità parziale.

30

Struttura nota ,osservabilità completa

Obiettivo apprendimento

Ricavare i valori dei parametri di ogni CPD che massimizzano la verosimiglianza del set di apprendimento.

31

Struttura nota ,osservabilità completa

Il logaritmo normalizzato della verosimiglianza del set di apprendimento è :

Notiamo come i singoli termini sono sommati uno ad uno (infatti si suppone siano indipendenti), è quindi possibile massimizzare il singolo contributo alla verosimiglianza per ottenere il massimo globale.In casi semplici per ricavare le probabilità basta contare il numero di volte che un evento accade (ad es. con l’irrigatore)..

32

Struttura nota, osservabilità parziale.

Alcuni nodi sono non noti (non osservati)

Uso l’algoritmo EM per ricavare un ottimo locale del Maximum Likelihood Extimate dei parametri

Nel passo E uso degli algoritmi di inferenza per ricavare i valori attesi di tutti i nodi e poi nel passo M uso questi valori come se fossero osservati.

33

Struttura nota ,osservabilità parziale

Ipotesi sui parametri

Numero di volte che l’evento accade

Sommatoria attesa

Massimizzazione deiparametri.

34

Struttura non nota , osservabilità completa

Esempio di procedura di apprendimento:

Passo1: Generazione di una rete random, detta gold network , avente il

numero dei nodi e il massimo numero di stati per nodo prefissati e con una

specifica probabilità per l’inserimento di archi fra i nodi.

Passo2: Campionamento della gold network in modo da ottenere un

database di esempi D con un numero di campioni prestabiliti.

Passo3:Perturbazione della gold network per ottenere una start network da

cui cominciare la ricerca. Il metodo della perturbazione utilizza una certa

probabilità per modificare gli archi esistenti ed un’altra per aggiungere

nuovi archi, con il vincolo di mantenere il grafo aciclico.

35

Struttura non nota , osservabilità completa

.

Passo4: Apprendimento strutturale , a partire da D e dalla start network ,

utilizzando l’algoritmo di ricerca esposto nel caso precedente.

Passo5:Apprendimento delle tabelle di probabilità associate a ciascun

nodo tramite una procedura che implementa l’equazione :

 

ove Nijk è il numero delle volte che nel database D si ha Xi=xik e

Pai=paij , mentre

Parametri della

distribuzione

Modello della

struttura

36

Struttura non nota e osservabilità parziale

Tecnica classica NP-Hard

Uso approcci statistici:

MODEL SELECTIONMODEL SELECTION

Seleziona un buon modello (fa delle ipostesi sulla struttura)fra i possibili e lo utilizza come se fosse il modello corretto

Seleziona un numero utilizzabile di modelli e considera l’insieme come “tutti i modelli”

SELECTION MODEL SELECTION MODEL AVERAGINGAVERAGING

Studi hanno dimostrato come questi due metodi applicati alle reti bayesiane forniscono dei modelli molto accurati

37

Esempio di rete complessa

38

Microsoft’s Office Assistant

b

Quando l’utente chiama l’assistant vengonousati i metodi Bayesiani per analizzare le azioni recenti e quindi cercare di anticipare le richieste dello stesso.

39

Priorities

Si tratta di un filtro per e-mail che è attualmente in sviluppo in Microsoft dal team del Dott. Eric Horvitz. Per iniziare il filtro valuta se nella mail ci sono parole che indicano urgenza (come ad es. ASAP..), domande dirette , il tempo delle frasi etc. Verifica inoltre se il nome del mittente e nella mia rubrica ,se il messaggio è stato mandato a più utenti

40

VISTADisplay of information for Time-Critical Decision Making

Questo sistema è stato sviluppato da Horvitz ( Microsoft) e Matthew Barry (NASA) . Quando si devono prendere delle decisioni importanti che però dipendono da molti parametri è importante che il decisore visualizzi solo le informazioni significative.Il Vista system è costituito da una rete bayesiana che in base allo stato del sistema di propulsione decide quali sono i dati da visualizzare sullo schermo e in che modo .Grazie a Vista si è riusciti a ridurre drasticamente il tempo di risposta in caso di decisioni critiche aumentando però l’efficienza delle stesse.

41

VISTADisplay of information for Time-Critical Decision Making

42

VISTADisplay of information for Time-Critical Decision Making

43

Help desk Richo’sRete all’help desk Richo’s che permette di rispondere al doppio delle domande. In questo caso , in base al profilo utente, alle sue ultime azioni e alle sue richieste si forniscono all’operatore tutte le informazioni ( ed eventualmente la risposta corretta) necessarie a soddisfarne i bisogni

44

PathfinderSi tratta di una rete Bayesiana progettata da Heckermann nel 1990 per fare le diagnosi di malattie ai linfonodi.Quando una persona ha dei disturbi ai linfonodi , ne viene prelevata una quantità e viene analizzata al microscopio da uno specialista il quale arriva ad una diagnosi valutando anche una serie di esami che il paziente avrà fatto. Pathfinder è utilizzato per decidere quale deve essere il prossimo esame da eseguire per arrivare d una diagnosi corretta . All’interno del modello di Pathfinder sono presenti 60 disturbi e 130 caratteristiche da osservare per fare la diagnosi.

45

A Decision-Theoretic Approach for Selecting Tutorial Discourse Actions

DT-Tutor è un motore di selezione delle azioni. Studi hanno dimostrato che per far apprendere meglio uno studente è necessario conoscere il suo stato d’animo e , in base a ciò decidere che tipo di azione svolgere (ad es. se lo studente si sta annoiando posso accelerare il ritmo o magari fargli vedere un filmato). Però lo stato dello studente non è certo ed è per questo che si utilizza una rete Bayesiana . Nella rete di DT-Tutor i nodi rappresentano le credenze del Tutor sullo stato dello studente. Notiamo come in questo caso si utilizzi una Dynamic Belief Network , e cioè una rete che ogni volta che cambiano i valori degli attributi crea una nuova porzione di rete: è una rete che si evolve nel tempo. In questo caso più che di Dynamic Belief Network è più corretto parlare di Dynamic Decision Network in quanto sono presenti anche nodi di decisione e nodi di utilità.

46

A Decision-Theoretic Approach for Selecting Tutorial Discourse Actions

Slice2

State1

T act1

Slice1

State0

S Act2

Slice0

State2

Util2

TACN (Tutor Action Cycle Network)

Ogni TACN è usata per un singolo ciclo, dove per singolo ciclo si intende :1. Decidere l’azione.2. Eseguirla.3. Osservare la reazione dello studente .4. Aggiornare lo stato dello stesso nella rete.

47

A Decision-Theoretic Approach for Selecting Tutorial Discourse Actions

Grazie alla rete è possibile prevedere lo stato dello studente e quindi impostare una sequenza di azioni senza dover attendere la reazione dello studente.

APPLICAZIONI

Calculus Problem-Solving

Project LISTEN’s Reading Tutor

L’RTDT è un prototipo che supporta i bambini durante l’apprendimento della lettura

Il CDTD è un prototipo sviluppato per

l’apprendimento della matematica e

in particolare del funzionamento

dei tassi.

48

A Decision-Theoretic Approach for Selecting Tutorial Discourse Actions

Knowledge1

Focus1

Affect1

Task Progress1

Discourse State1

StudentModel1

Knowledge2

Focus2

Affect2

Task Progress2

Discourse State2

StudentModel2

Knowledge0

Focus0

Affect0

Task Progress0

Discourse State0

StudentModel0

Tutor Action1 Student action2

Utility2

Per il CTDT consiste in due nodi di decisione uno per decidere l’argomento e uno per decidere il tipo di azione.Nel RTDT è un nodo singolo per la scelta del topic

49

A Decision-Theoretic Approach for Selecting Tutorial Discourse Actions

Knowledge1

Focus1

Affect1

Task Progress1

Discourse State1

StudentModel1

Knowledge2

Focus2

Affect2

Task Progress2

Discourse State2

StudentModel2

Knowledge0

Focus0

Affect0

Task Progress0

Discourse State0

StudentModel0

Tutor Action1 Student action2

Utility2

Rappresenta quello che ilTutor pensa sia il livello

di conoscenza del dominioda parte dello studente.

50

A Decision-Theoretic Approach for Selecting Tutorial Discourse Actions

Knowledge1

Focus1

Affect1

Task Progress1

Discourse State1

StudentModel1

Knowledge2

Focus2

Affect2

Task Progress2

Discourse State2

StudentModel2

Knowledge0

Focus0

Affect0

Task Progress0

Discourse State0

StudentModel0

Tutor Action1 Student action2

Utility2

Rappresenta il livello diattenzione dello studente nel

task attuale

51

A Decision-Theoretic Approach for Selecting Tutorial Discourse Actions

Knowledge1

Focus1

Affect1

Task Progress1

Discourse State1

StudentModel1

Knowledge2

Focus2

Affect2

Task Progress2

Discourse State2

StudentModel2

Knowledge0

Focus0

Affect0

Task Progress0

Discourse State0

StudentModel0

Tutor Action1 Student action2

Utility2

Rappresenta lo stato d’animo dello studente

52

A Decision-Theoretic Approach for Selecting Tutorial Discourse Actions

Knowledge1

Focus1

Affect1

Task Progress1

Discourse State1

StudentModel1

Knowledge2

Focus2

Affect2

Task Progress2

Discourse State2

StudentModel2

Knowledge0

Focus0

Affect0

Task Progress0

Discourse State0

StudentModel0

Tutor Action1 Student action2

Utility2Rappresenta la coerenza di ciò che è accaduto con la

struttura del task

53

A Decision-Theoretic Approach for Selecting Tutorial Discourse Actions

Knowledge1

Focus1

Affect1

Task Progress1

Discourse State1

StudentModel1

Knowledge2

Focus2

Affect2

Task Progress2

Discourse State2

StudentModel2

Knowledge0

Focus0

Affect0

Task Progress0

Discourse State0

StudentModel0

Tutor Action1 Student action2

Utility2

Rappresenta la coerenza delle azioni del tutor con le reazioniprecedenti dello studente

54

A Decision-Theoretic Approach for Selecting Tutorial Discourse Actions

Knowledge1

Focus1

Affect1

Task Progress1

Discourse State1

StudentModel1

Knowledge2

Focus2

Affect2

Task Progress2

Discourse State2

StudentModel2

Knowledge0

Focus0

Affect0

Task Progress0

Discourse State0

StudentModel0

Tutor Action1 Student action2

Utility2

Consiste in un insieme di nodirappresentanti le preferenze del tutor per quanto riguarda i risultati finali del task

55

Bibliografia

http://www.cs.berkeley.edu/~murphyk/Bayes/bayes.html

http://yoda.cis.temple.edu:8080/UGAIWWW/lectures/bnets.html

http://web.tiscali.it/enricopapalini/LDBND/BL.html

www.research.microsoft.com