Una rete bayesiana (BN, Bayesian network) è un modello grafico probabilistico che rappresenta un insieme di variabili stocastiche con le loro dipendenze condizionali attraverso l'uso di un grafo aciclico diretto (DAG). Per esempio una rete bayesiana potrebbe rappresentare la relazione probabilistica esistente tra i sintomi e le malattie. Dati i sintomi, la rete può essere usata per calcolare la probabilità della presenza di diverse malattie.
Il termine modello gerarchico è talvolta considerato un particolare tipo di rete bayesiana, ma non ha nessuna definizione formale. Qualche volta viene usato per modelli con tre o più livelli di variabili stocastiche; in altri casi viene usato per modelli con variabili latenti. Comunque in generale qualsiasi rete bayesiana moderatamente complessa viene usualmente detta "gerarchica".
Formalmente le reti bayesiane sono DAG i cui nodi rappresentano variabili casuali in senso bayesiano: possono essere quantità osservabili, variabili latenti, parametri sconosciuti o ipotesi. Gli archi rappresentano relazioni di dipendenza; i nodi che non sono connessi rappresentano variabili che sono condizionatamente indipendenti tra di loro. Ad ogni nodo è associata una funzione di probabilità che prende in input un particolare insieme di valori per le variabili del nodo genitore e restituisce la probabilità della variabile rappresentata dal nodo. Per esempio, se i genitori del nodo sono variabili booleane, allora la funzione di probabilità può essere rappresentata da una tabella in cui ogni entry rappresenta una possibile combinazione di valori vero o falso che i suoi genitori possono assumere.
Esistono algoritmi efficienti che effettuano inferenza e apprendimento a partire dalle reti bayesiane. Le reti bayesiane che modellano sequenze di variabili che variano nel tempo sono chiamate reti bayesiane dinamiche.
Definizioni Diverse definizioni equivalenti di rete bayesiana sono state proposte. Nel seguito, sia un grafo aciclico orientato e sia , un insieme di variabili aleatorie indicizzate da .
Fattorizzazione è una rete bayesiana rispetto a se rappresenta la funzione di densità di probabilità (rispetto a una misura prodotto) può essere scritta un prodotto delle singole funzioni di densità, condizionata sulle variabili-genitore:
dove è l'insieme dei genitori di , ossia quei nodi che puntano direttamente verso con un singolo arco.
Per qualsiasi insieme di variabili aleatorie, la probabilità di qualsiasi membro di una congiunta può essere calcolato in base alle probabilità condizionate usando la regola di concatenazione (dato un ordine topologico su ) come segue:
Usando la definizione precedente, questa può essere scritta come:
La differenza fra le due espressioni è l'indipendenza condizionata delle variabili da qualunque fra i loro non discendenti, dati i valori delle loro variabili-genitore.
Markov blanket Il Markov blanket (coperta di Markov) di un nodo è l'insieme dei nodi composto dai suoi genitori, dai suoi figli e da tutti gli altri genitori dei suoi figli. Il Markov blanket rende il nodo indipendente dal resto della rete; la congiunta di tutte le variabili nel Markov blanket di un nodo costituisce la conoscenza sufficiente per calcolare la distribuzione del nodo. è una rete bayesiana rispetto a se ogni nodo e condizionatamente indipendente da tutti gli altri nodi nella rete, dato il suo Markov blanket.
d-separazione Tale definizione può essere resa più generale definendo la "d-separazione" di due nodi, dove "d" sta per direzionale. Si definisce prima la "d-separazione" di un cammino e poi si definisce la "d-separazione" di due nodi in termini di quella.
Sia un cammino dal nodo a . Un cammino è un percorso aciclico, non orientato (cioè si ignorano tutte le direzioni degli archi) tra due nodi. Allora si dice che è d-separato da un insieme di nodi se si verifica una delle seguenti condizioni:
contiene (ma non necessariamente nella sua interezza) una catena diretta, o , tale che il nodo intermedio si trova in , contiene una biforcazione, , tale che il nodo di mezzo è in , o contiene una biforcazione inversa (o collisore), , tale che né il nodo intermedio né uno dei suoi discendenti è in .
I nodi e sono d-separati da se tutti i cammini fra di essi sono d-separati. Se e non sono d-separati, essi sono d-connessi.
è una rete bayesiana rispetto a se, per ogni coppia di nodi , :
dove è un insieme che d-separa e . (Il Markov blanket è il minimo insieme di nodi che d-separa il nodo da tutti gli altri nodi).
Reti causali Sebbene le reti bayesiane siano spesso usate per rappresentare relazioni causali, ciò non è necessario: un arco orientato da a non richiede che sia causalmente dipendente da . Ciò è facilmente mostrato dal fatto che le reti bayesiane su grafi:
sono equivalenti: ossia impongono esattamente gli stessi vincoli di indipendenza condizionata.
Una rete causale è una rete bayesiana con il vincolo che le relazioni siano causali. Il significato aggiuntivo delle reti causali specifica che se si causa attivamente che un nodo venga a trovarsi in un dato stato (azione denotata da ), allora la densità di probabilità cambia in quella di una rete ottenuta tagliando i collegamenti dai genitori di a e impostando al valore causato . Usando questa semantica, può essere predetto l'impatto di interventi esterni da dati ottenuti prima dell'intervento.
Inferenza e apprendimento Con le reti bayesiane sono possibili tre principali forme d'inferenza:
Inferenza su variabili non osservate Siccome una rete bayesiana è un modello completo per le proprie variabili e le loro relazioni, essa può essere impiegata per rispondere a query probabilistiche su di esse. Ad esempio la rete può essere utilizzata per aggiornare la conoscenza sullo stato si un sotto-insieme delle variabili quando si osservano i valori altre variabili (dette di evidenza). Tale processo di calcolo della distribuzione a posteriori di certe variabili data l'evidenza viene detto inferenza probabilistica. Questa distribuzione offe una statistica sufficiente universale per applicazioni di identificazione, nella scelta dei valori per il sottoinsieme di variabili che minimizzino una certa funzione di perdita attesa, ad esempio la probabilità di errore di decisione. Una rete bayesiana può pertanto essere considerata un meccanismo per l'applicazione automatica del teorema di Bayes a problemi complessi.
I metodi di inferenza esatta più comuni sono: eliminazione di variabili, che elimina (tramite integrazione o sommatoria) le variabili non osservate e non interrogate una per una, distribuendo la somma sul prodotto; propagazione su albero di giunzione, che memorizza in una cache i calcoli in modo che si possano interrogare contemporaneamente molte variabili e propagare rapidamente nuova evidenza; condizionamento ricorsivo e ricerca AND/OR, che consentono un compromesso tempo-memoria ed eguagliano l'efficienza dell'eliminazione di variabili quando si utilizza uno spazio sufficiente. Tutti questi metodi hanno una complessità esponenziale nella cosiddetta treewidth della rete. Gli algoritmi di inferenza approssimata più comuni sono il campionamento d'importanza, la simulazione stocastica con MCMC, l'eliminazione mini-bucket, la belief propagation loopy e quella generalizzata e i metodi variazionali.
Apprendimento dei parametri Per specificare completamente la rete bayesiana e quindi rappresentare pienamente la distribuzione di probabilità congiunta, è necessario specificare per ogni nodo la distribuzione di probabilità per condizionata dai genitori di . La distribuzione di condizionata dai suoi genitori può avere qualsiasi forma. È tipico lavorare con distribuzioni discrete o gaussiane poiché ciò semplifica i calcoli. A volte sono noti solo vincoli sulla distribuzione; in tal caso è possibile utilizzare il principio della massima entropia per determinare una singola distribuzione, quella di massima entropia dati i vincoli. (analogamente, nel contesto specifico di una rete bayesiana dinamica, la distribuzione condizionata per l'evoluzione nel tempo dello stato nascosto viene comunemente specificata massimizzando il tasso di entropia del processo stocastico implicito).
Spesso queste distribuzioni condizionate includono parametri sconosciuti che devono essere stimati dai dati, ad esempio tramite il metodo della massima verosimiglianza. La massimizzazione diretta della verosimiglianza (o della probabilità a posteriori) è spesso complessa date le variabili non osservate. Un approccio classico a questo problema è l'algoritmo Algoritmo EM, che alterna il calcolo dei valori attesi delle variabili non osservate condizionate dai dati osservati, con la massimizzazione della verosimiglianza completa (o a posteriori) supponendo che i valori attesi calcolati in precedenza siano corretti. Date modeste condizioni di regolarità, questo processo converge su valori di massima verosimiglianza (o probabilità a posteriori) dei parametri.
Un approccio più pienamente bayesiano consiste nel trattare i parametri come variabili aggiuntive non osservate e calcolare una distribuzione a posteriori completa su tutti i nodi condizionata sui dati osservati, per poi marginalizzare sui parametri integrando. Questo approccio può essere costoso e portare a modelli di grandi dimensioni, facendo risultare più facilmente gestibili gli approcci classici d'impostazione dei parametri.
Apprendimento della struttura Nel caso più semplice, una rete bayesiana viene definita da un esperto per poi essere utilizzata per effettuare inferenze. In altre applicazioni, il compito di definire la rete è troppo complesso per esperti umani. In questo caso, la struttura della rete e i parametri delle distribuzioni locali devono essere appresi dai dati.
L'apprendimento della struttura del grafo di una rete bayesiana (BN) è una problematica affrontata nell'ambito dell'apprendimento automatico. L'idea di base si rifà a un algoritmo di ricostruzione sviluppato da Rebane e Pearl e si basa sulla distinzione tra i tre possibili modelli ammessi in un DAG a 3 nodi:
+schemi di giunzioneSchemaModellocatenabiforcazione collisione
I primi due rappresentano le stesse dipendenze ( e sono indipendenti data ) e sono, pertanto, indistinguibili. La collisione, però, può essere identificata univocamente, dato che e sono marginalmente indipendenti e tutte le altre coppie sono dipendenti. Pertanto, mentre gli scheletri (grafi deprivati dell'orientamento degli archi) di tali triple sono identici, la direzionalità delle frecce può essere parzialmente identificata. La stessa distinzione si applica quando e hanno genitori comuni, tranne per il fatto che si deve prima condizionare su tali genitori. Sono stati sviluppati algoritmi per determinare sistematicamente lo scheletro del grafo sotteso e quindi aggiungere la direzione a tutti gli archi in base alle dipendenze condizionali osservate.
Un metodo alternativo di apprendimento strutturale utilizza la ricerca basata sull'ottimizzazione. Essa richiede una funzione di valutazione e una strategia di ricerca. Una funzione di valutazione comune è la probabilità a posteriori della struttura condizionata sui dati di addestramento, come il BIC o il BDeu. Il tempo richiesto per la ricerca esaustiva di una struttura che massimizzi la funzione di valutazione è super-esponenziale rispetto al numero di variabili. Una strategia di ricerca locale apporta modifiche incrementali volte a migliorare il valore di valutazione della struttura. Un algoritmo di ricerca globale come la catena di Markov Monte Carlo (MCMC) consente di evitare di rimanere intrappolati nei minimi locali. Determinare una struttura massimizzando l'informazione mutua, in genere limitando l'insieme dei candidati genitori a k nodi o trovando un k ottimale nodo per nodo, è una tecnica che raggiunge regolarmente alte valutazioni su dataset di riferimento.