8
Reti
bayesiane
introduzione
Vittorio Maniezzo – Università di Bologna
1
Ringraziamenti
Questi lucidi derivano anche da adattamenti personali di
materiale prodotto (fornitomi o reso scaricabile) da:
wikipedia, P. Smyth, D. HeckerMann.
Vittorio Maniezzo – Università di Bologna
2
Introduzione
Una rete bayesiana (Bayesian Network, BN) è un modello
grafico che serve a rappresentare una relazione non
deterministica fra un insieme di variabili.
Aiutano nella gestione di:
• insiemi di dati incompleti (mancano alcuni attributi per
qualche dato)
• apprendimento di reti causali
• combinazione di dati e conoscenze di dominio
E’ un formalismo probabilistico.
Vittorio Maniezzo - Università di Bologna
3
Spazio di campionamento
Probabilità,
ripasso
Lo spazio di campionamento Ω è l’universo dei risultati
elementari, ω∈Ω, di un esperimento. Spesso nelle
presentazioni introduttive i risultati elementari sono
equiprobabili (dadi, monete, carte, roulette, urne, ...) e pochi.
Un evento a è un insieme di risultati.
Vittorio Maniezzo – Università di Bologna
Misure di probabilità
Probabilità,
ripasso
Ogni evento (insieme di risultati) è associato ad una
probabilità tramite una funzione detta misura di
probabilità che gode di tre fondamentali proprietà:
1. La probabilità di ogni evento è compresa fra 0 e 1.
2. La probabilità dell’universo Ω è 1 ( p(Ω)=1).
3. Se a e b sono due eventi (insiemi di risultati) con
nessun elemento in comune, la probabilità della loro
unione è la somma delle loro probabilità
(p(a∪b)=p(a)+p(b) ).
Inoltre, la probabilità che un evento non accada è il
complemento a quella che accada ( p(∼a) = 1-p(a) )
Vittorio Maniezzo – Università di Bologna
Probabilità congiunta
Probabilità,
ripasso
La probabilità che un evento a si verifichi è la sua
probabilità marginale, p(a). Es., pesco un asso o estraggo
una pallina tonda.
La probabilità congiunta di due eventi a e b è la probabilità
che si verifichino contemporaneamente, p(a,b). Es., pesco
l’asso di coppe o estraggo una pallina quadrata (?) rossa.
Vittorio Maniezzo – Università di Bologna
6
Probabilità condizionata
Probabilità,
ripasso
La probabilità dell’evento a condizionata da b (probabilità
di a dato b, p(a|b)) è la probabilità che si verifichi a
sapendo che si verifica b.
p(a) è la probabilità a priori (prior probability), p(a|b) la
prob. a posteriori (posterior probability).
Sapendo che b è vero, l’universo di interesse si riduce a b
(ho estratto una pallina tonda, con che prob. è rossa?).
a
a∩b
Vittorio Maniezzo – Università di Bologna
b
=
( ∩ )
( )
=
( ∩ )
( )
Variabili casuali
Probabilità,
ripasso
Anche dette variabili stocastiche o variabili aleatorie.
Non sono variabili. Sono funzioni.
• Dominio:
lo spazio di campionamento,
• Codominio: numeri reali.
Permettono di tradurre gli eventi, qualsiasi siano, in numeri.
Vittorio Maniezzo – Università di Bologna
Distribuzione di probabilità
Probabilità,
ripasso
Un insieme di numeri con somma 1 è una distribuzione.
Una distribuzione di probabilità F è una funzione
matematica che, per ogni valore della variabile, fornisce la
probabilità che venga osservato quel valore.
Es. per un dado, F(1) = F(2) = F(3) = F(4) = F(5) = F(6) = 1/6.
Nel caso di variabili aleatorie continue la distribuzione di
probabilità diventa una funzione densità di probabilità, il cui
integrale vale 1.
Vittorio Maniezzo – Università di Bologna
Probabilità
Probabilità,
ripasso
Approccio oggettivista (o frequentista): considera la
probabilità come un’entità misurabile, legata alla frequenza
di accadimento (base statistica)
Probabilità classica: probabilità oggettiva (vera) di un
evento
Approccio soggettivista: considera la probabilità una misura
del grado di attesa soggettivo del verificarsi di un evento
(base cognitiva)
Probabilità Bayesiana: grado con cui si crede che un
evento accada
Vittorio Maniezzo - Università di Bologna
10
Probabilità,
ripasso
Probabilità
Tre leggi alla base della teoria delle probabilità classica:
• Condizione di convessità: 0 ≤ ( ) ≤1
• Additività semplice:
∪
≤
+ ( )
• Regola del prodotto: ( , ) =
=
( )
Dalla terza proprietà deriva direttamente il Teorema di Bayes:
=
Vittorio Maniezzo – Università di Bologna
( )
( )
=
( )
11
Probabilità,
ripasso
Teorema di Bayes
Teorema di Bayes: apprendimento dall’esperienza
=
( )
probabilità a priori
probabilità a posteriori
verosimiglianza
fattore di normalizzazione
Vittorio Maniezzo – Università di Bologna
( )
Teorema probabilità totale
Probabilità,
ripasso
Teorema della probabilità totale (o della marginalizzazione)
p( ) = ∑
( , )=∑
( )
e quindi:
• data la probabilità congiunta (es., p(a,b,c)) si può ottenere una
probabilità marginale (es., p(b)) sommando le altre variabili:
p(b) = Σa Σc p(a, b, c)
• data la probabilità congiunta possiamo calcolare qualunque
probabilità condizionale:
p(c | b) = ∑
( , | ) = 1/p(b) ∑
( , , )
(dove 1/p(b) è una costante di normalizzazione)
Dalla probabilità congiunta si può ricavare qualunque probabilità di
interesse.
Vittorio Maniezzo – Università di Bologna
13
Probabilità,
ripasso
Concatenazione (o fattorizzazione)
Per definizione di prob. congiunta:
, , ,… =
, ,…
( , ,…)
Ripetendo il procedimento
, , ,…,
=
, ,…,
,…,
…,
( )
Questa fattorizzazione può essere fatta con un qualunque
ordinamento delle variabili
Vittorio Maniezzo – Università di Bologna
Indipendenza condizionale
Probabilità,
ripasso
Un evento a è condizionalmente indipendente da un evento b, dato
l’evento c, se
p(a|b,c) = p(a|c) (indipendenza stocastica subordinata)
In pratica a è condizionalmente indipendente da b, dato c, se la
conoscenza di b non porta a nessuna ulteriore variazione della
probabilità di a rispetto a quella apportata dall’avverarsi di c.
Indipendenza condizionale di a e b dato c:
p(a,b|c) = p(a|c)p(b|c) = p(b,a|c)
Se c è un insieme vuoto:
p(a,b) = p(a)p(b) (noncorrelazione)
Generalizzando a più variabili casuali: assunzione naïve di Bayes
p(x1, x2,…. xk | c) = Πi p(xi | c)
Vittorio Maniezzo – Università di Bologna
15
Indipendenza marginale
Probabilità,
ripasso
Due variabili a e b sono marginalmente indipendenti se
p(a,b)=p(a)p(b) o, equivalentemente, p(a|b)=p(a)
a e b sono condizionalmente indipendenti data una terza
variabile c se p(a,b|c)=p(a|c)p(b|c) o equivalentemente
p(a|b,c)=p(a|c)
Indipendenza marginale e condizionale sono due concetti
differenti e non legati tra loro.
Vittorio Maniezzo – Università di Bologna
16
Inferenza probabilistica
Probabilità,
ripasso
Dato un insieme di eventi e1,e2,..,ek e tutte le possibili
combinazioni dei loro valori Vero e Falso,
supponendo di:
• conoscere tutti i valori di prob. congiunta p(e1,e2,...,ek)
• conoscere il valore di un sottoinsieme di variabili, per es.
ej = e (ad es. Vero)
si chiama inferenza probabilistica il processo di calcolo dei
valori p(ei=vero|ej=e)
Vittorio Maniezzo – Università di Bologna
17
Reti Bayesiane
Le reti bayesiane sono una struttura che rappresenta le indipendenze
condizionali
Sono DAG (grafi orientati aciclici) i cui nodi sono eventi (E)
Una rete bayesiana stabilisce che ogni nodo, dati i suoi immediati
ascendenti (parents, P), è condizionalmente indipendente da ogni
altro che non sia suo discendente
Le reti bayesiane sono chiamate anche reti causali, perché gli archi
che connettono i nodi possono essere visti come se rappresentassero
relazioni causali dirette
Vittorio Maniezzo – Università di Bologna
18
Rete Bayesiana: esempio
Amico
malato
p(M)
0.001
influenza
Non
gioco
partita
Vittorio Maniezzo – Università di Bologna
A
t
f
p(G)
0.90
0.05
p(F)
Prendo
freddo
M
F
t
t
f
f
t
F
t
f
Non
esco la
sera
0.002
p(I)
0.95
0.94
0.29
0.001
A
t
f
p(E)
0.70
0.01
Reti bayesiane
Weka
Vittorio Maniezzo – Università di Bologna
MSBNx
20
Reti Bayesiane
La rete Bayesiana specifica le distribuzioni congiunte in una forma
strutturata: rappresenta dipendenze/indipendenze con un grafo
orientato
• Nodi = variabili casuali
• Edge = dipendenze dirette
In generale,
p(x1, x2,....xn) =
Π p(xi | ascendenti(xi ) )
Distribuzione congiunta
Topologia del grafo
Base della rappresent. del grafo
relazioni di indipendenza condizionale
Il grafo deve essere aciclico
Necessario specificare due elementi
• La topologia del grafo (assunzioni di indipendenza condizionale)
• Distribuzioni di probabilità (per ogni variabile dati i suoi padri)
Vittorio Maniezzo – Università di Bologna
Reti Bayesiane
Le reti Bayesiane (definizione)
• Le reti Bayesiane usano dei grafi per rappresentare indipendenze
condizionali all’interno di un set di variabili.
• Una BN ha due componenti principali: un grafo diretto aciclico
(DAG) e un set di distribuzioni di probabilità condizionali.
Nel DAG:
• I nodi rappresentano variabili casuali
• Gli archi sono diretti e rappresentano dipendenze tra le variabili
• Ad ogni nodo è associata una distribuzione di probabilità
condizionale.
• Se variabili discrete, le distribuzioni di probabilità sono
rappresentate con tabelle che contengono i valori di probabilità di
un nodo in funzione di tutte le possibili configurazioni dei nodi
ascendenti (nodi da cui parte un arco che punta al nodo corrente).
Vittorio Maniezzo – Università di Bologna
22
Apprendimento delle BN
Due problemi:
• Apprendere le probabilità condizionali, nota la struttura
della rete
• Apprendere sia la struttura della rete che le probabilità
condizionali
In entrambi i casi si sfrutta la fattorizzazione della
probabilità congiunta delle variabili
Vittorio Maniezzo – Università di Bologna
23
Applicazioni: esempi
• Diagnosi mediche (Pathfinder, 1990)
• Analisi decisionale (si incorporano nodi dei valori e nodi di
decisione, si parla allora di diagrammi di influenza)
• Diagnosi di reti mobili (cellulari)
• Analisi di dati finanziari
• Previsioni meteorologiche
• Esplorazioni in campo petrolifero
• Interazione software-utente (Microsoft, progetto
Lumiere)
• Valutazione rischio (http://www.bayesianrisk.com/)
• Data mining
• Comprensione di storie
Vittorio Maniezzo – Università di Bologna
24
Risorse per BN
• Ambienti freeware di sviluppo di reti bayesiane: MSBNx di
Microsoft (http://research.microsoft.com/adapt/MSBNx/)
• JavaBayes: http://www-2.cs.cmu.edu/~javabayes/Home/
• List of BN software
http://www.cs.ubc.ca/~murphyk/Software/bnsoft.html\
• BNT: inference and learning, Matlab, open source
• MSBNx: inference, by Microsoft, free closed source
• OpenBayes: inference and learning, Python, open source
• BNJ: inference and learning, Java, open source
• Weka: learning, Java, open source
• List of BN Models and Datasets:
http://www.cs.huji.ac.il/labs/compbio/Repository/
Vittorio Maniezzo – Università di Bologna
25
Esempio di rete Bayesiana
B
A
p(a,b,c) = p(c|a,b)p(a)p(b)
C
• Il modello stocastico ha una forma semplice, fattorizzata
• Archi orientati => dipendenza diretta
• Archi assenti => indipendenza condizionale
Vengono anche chiamate belief networks, graphical models, causal
networks, …
Vittorio Maniezzo – Università di Bologna
Reti Bayesiane a 3 variabili
a
Vittorio Maniezzo – Università di Bologna
b
c
Indipendenza marginale:
p(a,b,c) = p(a) p(b) p(c)
Reti Bayesiane a 3 variabili
Indipendenze condizionali:
p(a,b,c) = p(b|a)p(c|a)p(a)
A
b e c sono condizionatamente indipendenti
dato a
B
C
es., a è una malattia e b e c sono sintomi
indipendenti di a (dato a)
Vittorio Maniezzo – Università di Bologna
Reti Bayesiane a 3 variabili
A
B
Cause indipendenti:
p(a,b,c) = p(c|a,b)p(a)p(b)
C
Effetto di spiegazione:
Dato c, osservare a rende b meno
plausibile (v. esempio dopo)
a e b sono marginalmente
indipendenti, ma diventano dipendenti
se si conosce c
Vittorio Maniezzo – Università di Bologna
Reti Bayesiane a 3 variabili
A
Vittorio Maniezzo – Università di Bologna
B
C
Dipendenza markoviana:
p(a,b,c) = p(c|b) p(b|a)p(a)
Esempio
Modello causale su cosa succede quando ci si prende un’influenza.
Basato su 5 variabili stocastiche binarie:
• M = passo del tempo con un amico malato
• F = prendo freddo
• I = mi viene l’influenza
• G = non vado a giocare una partita nel pomeriggio
• E = non esco la sera
• Quanto vale p(M | G, E)?
Facile rispondere se si conoscono tutte le probabilità congiunte
- Necessarie 25 = 32 probabilità
- Possibile utilizzare della conoscenza di dominio per definire una
rete Bayesiana che utilizza meno probabilità.
Vittorio Maniezzo – Università di Bologna
Costruzione della rete: Step 1
Si ordinano la variabili in ordine causale (ordinamento parziale)
Qualunque ordinamento di variabili è permesso. Euristicamente,
si parte dalle cause e si va verso gli effetti.
Nell’esempio {M, F}, I, {G, E} → 4 possibili ordinamenti.
Es., {M,F} -> {I} -> {G,E}
p(G,E,I,M,F) = p(G,E | I,M,F) p(I| M,F) P(M,F)
≅ p(G,E | I) p(I| M,F) P(M) P(F)
≅ p(G | I) p(E | I) p(I| M,F) p(M) p(F)
Queste assunzioni di indipendenza condizionale definiscono la
topologia della rete Bayesiana.
Vittorio Maniezzo – Università di Bologna
La rete Bayesiana
Amico
malato
p(M)
0.001
influenza
Non
gioco
partita
Vittorio Maniezzo – Università di Bologna
A
t
f
p(G)
0.90
0.05
p(F)
Prendo
freddo
M
F
t
t
f
f
t
F
t
f
Non
esco la
sera
0.002
p(I)
0.95
0.94
0.29
0.001
A
t
f
p(E)
0.70
0.01
Costruzione della rete: Step 2
p(G,E,I,M,F) = p(G | I) p(E | I) p(I| M,F) p(M) p(F)
Necessarie:
3 tabelle di probabilità condizionale:
p(G | I), p(E | I), p(I| M,F)
• Necessarie 2 + 2 + 4 = 8 probabilità
2 probabilità marginali p(M), p(F)
Queste 10 probabilità derivano da:
• conoscenza di esperti
• dati (stime di frequenze relative)
• una combinazione delle due
Vittorio Maniezzo – Università di Bologna
Num probabilità in ingresso
Modello con n variabili binarie
Le tabelle di probabilità congiunte richiedono O(2n)
probabilità
Una rete Bayesiana con un massimo di k padri per nodo
richiede O(n 2k) probabilità
Esempio per n=30 e k=4
• probabilità congiunte: 230 ≅ 109 probabilità
• rete Bayesiana: 30 ⋅ 24 = 480 probabilità
Vittorio Maniezzo – Università di Bologna
Diversi ordinamenti delle variabili
Con ordinamento E, G, I, M, F
Non esco
Non gioco
Influenza
Am.malato
p(G | E) = p(G) ? No
p(I | E,G) = p (I|G) ? p(I|E,G) = p (I) ? No
p(M | I,E,G) = p (M | I) ?
Si
p(M | I,E,G) = p (M) ?
No
p(F | G,I,M,F) = p (F | I) ?
No
p(F | G.I.M.F) = p (F | I,M) ? Si
Vittorio Maniezzo – Università di Bologna
Preso freddo
Diversi ordinamenti delle variabili
Freddo
Am.malato
Infl.
No gioco
Vittorio Maniezzo – Università di Bologna
Non esco
Inferenza nelle reti Bayesiane
Si vuole rispondere a una domanda tramite una rete Bayesiana
• Q = variabili nella query
• e = conoscenza pregressa (coppie istanziate variabile-valore)
• Inferenza = calcolo della distribuzione condizionale p(Q|e)
Esempio
• p(freddo | influenza)
• p(influenza | non gioco, non esco)
• p(non gioco, non esco | freddo, influenza)
Si può utilizzare la rete per rispondere efficientemente a queste
domande. La complessità sarà inversamente proporzionale alla
sparsità del grafo.
Vittorio Maniezzo – Università di Bologna
Tipi di inferenza
Q:query
E:evidenza disponibile
• Inferenza diagnostica:
dagli effetti alle cause.
p(freddo | non gioco)
• Inferenza causale:
dalle cause agli effetti.
p(non gioco | freddo)
p(non esco | freddo)
• Inferenza intercausale: fra cause di un effetto comune.
p(freddo | influenza)
p(freddo | influenza Ʌ amico malato)
Vittorio Maniezzo – Università di Bologna
Esempio: rete ad albero
D
A
B
E
C
F
p(a, b, c, d, e, f, g) modellata come
p(a|b) p(c|b) p(f|e) p(g|e) p(b|d) p(e|d) p(d)
Vittorio Maniezzo – Università di Bologna
G
Esempio: rete ad albero
D
A
B
E
c
F
g
Si vuole calcolare p(a | c, g)
Vittorio Maniezzo – Università di Bologna
No
Esempio: rete ad albero
D
A
Calcolo diretto:
B
E
c
F
,) = ∑
,-.
g
* +
, ))
La complessità è O(m4)
Vittorio Maniezzo – Università di Bologna
No
Esempio: rete ad albero
D
A
B
E
c
F
g
Riordinando :
Σb p(a|b) Σd p(b|d,c) Σe p(d|e) Σf p(e,f |g)
Vittorio Maniezzo – Università di Bologna
No
Esempio: rete ad albero
D
A
B
E
c
F
g
Riordinando :
Σb p(a|b) Σd p(b|d,c) Σe p(d|e) Σf p(e,f |g)
p(e|g)
Vittorio Maniezzo – Università di Bologna
No
Esempio: rete ad albero
D
A
B
E
c
F
g
Riordinando :
Σb p(a|b) Σd p(b|d,c) Σe p(d|e) p(e|g)
p(d|g)
Vittorio Maniezzo – Università di Bologna
No
Esempio: rete ad albero
D
A
B
E
c
F
g
Riordinando :
Σb p(a|b) Σd p(b|d,c) p(d|g)
p(b|c,g)
Vittorio Maniezzo – Università di Bologna
No
Esempio: rete ad albero
D
B
E
c
F
A
g
Riordinando :
Σb p(a|b) p(b|c,g)
p(a|c,g)
Complessità O(m), non O(m4)
Vittorio Maniezzo – Università di Bologna
No
Algoritmo per l'inferenza
Per calcolare p(q | e)
Step 1:
p(q | e) = p(q,e)/P(e) = α p(q,e), dato che p(e) è costante
rispetto a Q
Step 2:
p(q,e) = Σa..z p(q, e, a, b, …. z), per la legge della prob. totale
Step 3:
Σa..z
p(q, e, a, b, …. z) = Σa..z Πi p(variabile i | padri i)
(utilizzando la fattorizzazione Bayesiana)
Step 4:
Distribuisci le sommatorie sui prodotti per migliorare l'efficienza
Vittorio Maniezzo – Università di Bologna
No
Complessità dell’inferenza
Assumendo che la rete sia un albero orientato (polytree), in cui cioè
esiste un solo cammino orientato fra ogni coppia di nodi, la
complessità è O(n m K+1)
• n = numero di variabili
• m = arità (num valori assumibili) delle variabili
•K = massimo num di padri per nodo
• Forza bruta è O(mn-1)
Se la rete non è un polytree si prova a raggruppare variabili per
rendere il grafo un polytree.
La complessità diventa O(n m W+1), dove W è il num di variabili nel
cluster più grande.
Vittorio Maniezzo – Università di Bologna
No
Grafi non polytree
D
A
Vittorio Maniezzo – Università di Bologna
B
E
C
F
G
No
Grafi non polytree
D
A
B
E
C
F
G
Si raggruppa il minimo numero possibile di variabili
per convertire il grafo in un polytree
Vittorio Maniezzo – Università di Bologna
No
Junction Tree
D
B, E
A
Vittorio Maniezzo – Università di Bologna
C
F
G
No
Complessità dell’inferenza
Il problema di trovare l’ordinamento o il clustering delle variabili
ottimo per l’inferenza è NP-hard per grafi generici.
• Si utilizzano euristiche
• Esistono algoritmi efficienti per lavorare con BN anche grandi
Altri tipi di query possibili:
• Trovare i valori più probabili per una variabile data l’evidenza
disponibile
• arg max P(Q | e) = “spiegazione più probabile”, chiamata
maximum a posteriori query
• Può sfruttare la struttura del grafo come per l’inferenza,
sostanzialmente sostituendo le sommatorie con dei “max”
Vittorio Maniezzo – Università di Bologna
No
Algoritmo Message Passing
Algoritmo Message Passing (MP, Pearl, 1988; Lauritzen
and Spiegelhalter, 1988), più efficiente
• Scegli un nodo (qualunque) come radice
• Due fasi di message-passing
1. i nodi passano i messaggi verso la radice
2. i messaggi sono ridistribuiti verso le foglie
• Si può calcolare p(…) in tempo O(n)
Vittorio Maniezzo – Università di Bologna
No
Sketch di MP
2
1
3
Vittorio Maniezzo – Università di Bologna
4
No
Junction Tree
D
B, E
A
C
F
G
Possibile MP anche su junction tree, ma la
complessità diventa O(K2)
Vittorio Maniezzo – Università di Bologna
No
Variabili reali
Gestione variabili reali:
• Se le variabili sono distribuite in modo gaussiano, la teoria
dell’inferenza in BN è ben sviluppata. Essenzialmente si
sostituiscono le sommatorie con degli integrali.
• Per altre funzioni di ddp, molto meno.
• Problemi nella combinazione di più variabili (es. Come calcolare
la prob. congiunta di una Poissoniana e di una Gaussiana)
• Aggiustamenti pratici:
•Cercare di mettere le variabili reali come foglie del grafo, così
nessun’altra è condizionata da loro
•Assumere che tutte le variabili reali siano Gaussiane
•Discretizzare le variabili reali
Vittorio Maniezzo – Università di Bologna
Reti Bayesiane: sommario
Una rete Bayesiana
• Rappresenta una distribuzione congiunta per mezzo di un grafo
• Fornisce una rappresentazione efficiente della distribuzione
congiunta
Inferenza nelle reti Bayesiane
• Inferenza = risposte a domande del tipo p(q | e)
• In generale intrattabili (compless. esponenziale nel num di var.)
• trattabile per certe classi di reti Bayesiane
• Disponibili algoritmi efficienti sul grafo equivalente
Altri aspetti rilevanti delle reti Bayesiane
• variabili reali
• altri tipi di domande
Vittorio Maniezzo – Università di Bologna