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 1 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. 3 Vittorio Maniezzo - Università di Bologna Spazio di campionamento Probabilità, ripasso Lo spazio di campionamento è l’universo dei risultati elementari, , di un esperimento. Spesso nelle introduzione i risultati elementari sono equiprobabili (dadi, monete, carte, roulette, urne, ...) e pochi. Un evento a è un insieme di risultati. Vittorio Maniezzo – Università di Bologna 2 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(ab)=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 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 3 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 b 𝑝 𝑏 𝑎 = 𝑝(𝑎∩𝑏) 𝑝(𝑎) Vittorio Maniezzo – Università di Bologna 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 4 Probabilità, ripasso Distribuzione di probabilità 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 5 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 Teorema di Bayes Probabilità, ripasso Teorema di Bayes: apprendimento dall’esperienza 𝑝 𝑎 𝑏 = 𝐾 𝑝 𝑏 𝑎 𝑝(𝑎) 𝑝(𝑎) probabilità a priori 𝑝 𝑎 𝑏 probabilità a posteriori 𝑝 𝑏 𝑎 verosimiglianza 𝐾 fattore di normalizzazione Vittorio Maniezzo – Università di Bologna 6 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) = Sa Sc 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 7 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. Dall’indipendenza condizionale di a e b dato c otteniamo: 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 Indipendenza marginale 15 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 8 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 Cioè, per ogni e del grafo p(e|a,p(e)) = p(e|p(e)) per ogni a che non sia discendente di e. 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 9 Reti Bayesiane La rete Bayesiana specifica le distribuzioni congiunte in una forma strutturata: rappresenta dipendenze/indipendenze con un gafo orientato • Nodi = variabili casuali • Edge = dipendenze dirette In generale, p(x1, x2,....xn) = p(xi | ascendenti(xi ) ) Distribuzione congiunta Base della rappresent. del grafo Topologia 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 catturare le assunzioni di indipendenza condizionale 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. • Nel caso di 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 di interesse). Vittorio Maniezzo – Università di Bologna 20 10 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 21 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 22 11 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 23 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 12 Reti Bayesiane a 3 variabili a b c Indipendenza marginale: p(a,b,c) = p(a) p(b) p(c) Vittorio Maniezzo – Università di Bologna Reti Bayesiane a 3 variabili Indipendenze condizionali: p(a,b,c) = p(b|a)p(c|a)p(a) A B b e c sono condizionatamente indipendenti dato a C es., a è una malattia e b e c sono sintomi indipendenti di a (dato a) Vittorio Maniezzo – Università di Bologna 13 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 B C Dipendenza markoviana: p(a,b,c) = p(c|b) p(b|a)p(a) Vittorio Maniezzo – Università di Bologna 14 Esempio (al mondo fanno tutti questo) Modello causale dello scatto di un allarme antifurto in casa mentre io sono in vacanza. Basato su 5 variabili stocastiche binarie: • B = un ladro è entrato in casa • E = c’è stato un terremoto a casa • A = l’allarme scatta • J = il vicino John chiama per segnalare l’allarme • M = la vicina Mary chiama per segnalare l’allarme • Quanto vale p(B | M, J) ? 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 {B, E}, A, {J, M} 4 possibili ordinamenti. Es., {E, B} -> {A} -> {J, M} P(J, M, A, E, B) = P(J, M | A, E, B) P(A| E, B) P(E, B) P(J, M | A) P(A| E, B) P(E) P(B) P(J | A) P(M | A) P(A| E, B) P(E) P(B) Queste assunzioni di indipendenza condizionale definiscono la topologia della rete Bayesiana. Vittorio Maniezzo – Università di Bologna 15 La rete Bayesiana Vittorio Maniezzo – Università di Bologna Costruzione della rete: Step 2 p(J,M,A,E,B) = p (J|A) p(M|A) p(A|E,B) p(E) p(B) Necessarie: 3 tabelle di probabilità condizionale: p (J | A), p(M | A), p(A | E, B) • Necessarie 2 + 2 + 4 = 8 probabilità 2 probabilità marginali p(E), p(B) Queste 10 probabilità derivano da: • conoscenza di esperti • dati (stime di frequenze relative) • una combinazione delle due Vittorio Maniezzo – Università di Bologna 16 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 M, J, A, B, E MaryCalls JohnCalls Alarm p(J|M) = p(J) ? Burglary No p(A|J,M) = p (A|J) ? p(A|J,M) = p (A) ? p(B|A,J,M) = p (B|A) ? Si p(B|A,J,M) = p (B) ? No p(E|B, A,J,M) = p (E|A) ? No No Earthquake p(E|B,A,J,M) = p (E|A,B) ? Si Vittorio Maniezzo – Università di Bologna 17 Diversi ordinamenti delle variabili MaryCalls JohnCalls Alarm Burglary Earthquake Vittorio Maniezzo – Università di Bologna 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(furto | allarme) • p(terremoto | JCalls, MCalls) • p(JCalls, MCalls | furto, terremoto) 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 18 Tipi di inferenza Q:query E:evidenza disponibile • Inferenza diagnostica: dagli effetti alle cause. p(Furto | JohnChiama ) • Inferenza causale: dalle cause agli effetti. p(JohnChiama | Furto) p(MaryChiama | Furto) • Inferenza intercausale: fra cause di un effetto comune. p(Furto | Allarme) p(Furto | Allarme Ʌ Terremoto) Vittorio Maniezzo – Università di Bologna Esempio: rete ad albero D A B E C F G p(a, b, c, d, e, f, g) modellata come p(a|b) p(c|bi p(f|e) p(g|e) p(b|d) p(e|d) p(d) Vittorio Maniezzo – Università di Bologna 19 Esempio: rete ad albero D A B E c F g Si vuole calcolare p(a | c, g) Vittorio Maniezzo – Università di Bologna Esempio: rete ad albero D A B E c F Calcolo diretto: 𝑝 𝑎 𝑐, 𝑔 = 𝑏𝑑𝑒𝑓 𝑝 g 𝑎𝑏𝑑𝑒𝑓 𝑐, 𝑔) La complessità è O(m4) Vittorio Maniezzo – Università di Bologna 20 Esempio: rete ad albero D A B E c F g Riordinando: Sd p(a|b) Sd p(b|d,c) Se p(d|e) Sf p(e,f |g) Vittorio Maniezzo – Università di Bologna Esempio: rete ad albero D A B E c F g Riordinando : Sb p(a|b) Sd p(b|d,c) Se p(d|e) Sf p(e,f |g) p(e|g) Vittorio Maniezzo – Università di Bologna 21 Esempio: rete ad albero D A B E c F g Riordinando : Sb p(a|b) Sd p(b|d,c) Se p(d|e) p(e|g) p(d|g) Vittorio Maniezzo – Università di Bologna Esempio: rete ad albero D A B E c F g Riordinando : Sb p(a|b) Sd p(b|d,c) p(d|g) p(b|c,g) Vittorio Maniezzo – Università di Bologna 22 Esempio: rete ad albero D B E c F A g Riordinando : Sb p(a|b) p(b|c,g) p(a|c,g) Complessità O(m), non O(m4) Vittorio Maniezzo – Università di Bologna Algoritmo per l'inferenza Per calcolare p(q | e) Step 1: p(q | e) = p(q,e)/P(e) = a p(q,e), dato che p(e) è costante rispetto a Q Step 2: p(q,e) = Sa..z p(q, e, a, b, …. z), per la legge della prob. totale Step 3: Sa..z p(q, e, a, b, …. z) = Sa..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 23 Complessità dell’inferenza Assumendo che la rete sia un albero orientato (polytree), in cui cioè esiste un solo cammino orientato fra ogni copia 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 Grafi non polytree D A B E C F G Vittorio Maniezzo – Università di Bologna 24 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 Junction Tree D B, E A C F G Vittorio Maniezzo – Università di Bologna 25 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 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 26 Sketch di MP 2 1 3 4 Vittorio Maniezzo – Università di Bologna 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 27 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 28
© Copyright 2024 ExpyDoc