Rete bayesiana

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) ^[1]. 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 grafi aciclici orientati 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 G = (V,E) be a grafo acicliclo orientato (DAG) e sia X = (X_v), v ∈ V un insieme di variabili aleatorie indicizzate da V.

Fattorizzazione

X è una rete bayesiana rispetto a G 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: ^[2]

${\displaystyle p(x)=\prod _{v\in V}p\left(x_{v}\,{\big |}\,x_{\operatorname {pa} (v)}\right)}$

dove pa(v) è l'insieme dei genitori di v (ossia quei nodi che puntano direttamente verso v 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 X) come segue:

${\displaystyle \operatorname {P} (X_{1}=x_{1},\ldots ,X_{n}=x_{n})=\prod _{v=1}^{n}\operatorname {P} \left(X_{v}=x_{v}\mid X_{v+1}=x_{v+1},\ldots ,X_{n}=x_{n}\right)}$

Usando la definizione precedente, questa può essere scritta come:

${\displaystyle \operatorname {P} (X_{1}=x_{1},\ldots ,X_{n}=x_{n})=\prod _{v=1}^{n}\operatorname {P} (X_{v}=x_{v}\mid X_{j}=x_{j}{\text{ per ogni }}X_{j}\,{\text{ genitore di }}X_{v}\,)}$

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. X è una rete bayesiana rispetto a G se ogni nodo e conditionatamente 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.^[3]

Sia P un cammino dal nodo u a v. Un cammino è un percorso aciclico, non orientato (cioè si ignorano tutte le direzioni degli archi) tra due nodi. Allora si dice che P è d-separato da un insieme di nodi Z se si verifica una delle seguenti condizioni:

• P contiene (ma non necessariamente nella sua interezza) una catena diretta, ${\displaystyle u\cdots \leftarrow m\leftarrow \cdots v}$ o ${\displaystyle u\cdots \rightarrow m\rightarrow \cdots v}$, tale che il nodo intermedio m si trova in Z,
• P contiene una biforcazione, ${\displaystyle u\cdots \leftarrow m\rightarrow \cdots v}$, tale che il nodo di mezzo m è in Z, o
• P contiene una biforcazione inversa (o collisore), ${\displaystyle u\cdots \rightarrow m\leftarrow \cdots v}$, tale che né il nodo intermedio m né uno dei suoi discendenti è in Z.

I nodi u e v sono d-separati da Z se tutti i cammini fra di essi sono d-separati. Se u e v non sono d-separati, essi sono d-connessi.

X è una rete bayesiana rispetto a G se, per ogni coppia di nodi u, v:

${\displaystyle X_{u}\perp \!\!\!\!\perp X_{v}\mid X_{Z}}$

dove Z è un insieme che d-separa u e v. (Il Markov blanket è il minimo insieme di nodi che d-separa il nodo v 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 u a v non richiede che X_v sia causalmente dipendente da X_u. Ciò è facilmente mostrato dal fatto che le reti bayesiane su grafi:

${\displaystyle a\rightarrow b\rightarrow c\qquad {\text{e}}\qquad a\leftarrow b\leftarrow c}$

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 X venga a trovarsi in un dato stato x (azione denotata da do(X = x)), allora la densità di probabilità cambia in quella di una rete ottenuta tagliando i collegamenti dai genitori di X a X e impostando X al valore causato x.^[4] 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 junction tree, 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 X la distribuzione di probabilità per X condizionata dai genitori di X. La distribuzione di X 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^[5] e si basa sulla distinzione tra i tre possibili modelli ammessi in un DAG a 3 nodi:

schemi di giunzione

Schema	Modello
catena	${\displaystyle X\rightarrow Y\rightarrow Z}$
biforcazione	${\displaystyle X\leftarrow Y\rightarrow Z}$
collisione	${\displaystyle X\rightarrow Y\leftarrow Z}$

I primi due rappresentano le stesse dipendenze (${\displaystyle X}$ e ${\displaystyle Z}$ sono indipendenti data ${\displaystyle Y}$) e sono, pertanto, indistinguibili. La collisione, però, può essere identificata univocamente, dato che ${\displaystyle X}$ e ${\displaystyle Z}$ 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 ${\displaystyle X}$ e ${\displaystyle Z}$ 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.^[4][6][7][8]

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 ^[9][10][11] o trovando un k ottimale nodo per nodo ^[12], è una tecnica che raggiunge regolarmente alte valutazioni su dataset di riferimento.

Un metodo particolarmente veloce per l'apprendimento esatto di BN è quello di trasformare il problema in uno di ottimizzazione da risolvere mediante tecniche di programmazione intera (integer programming). Si aggiungono vincoli di aciclicità al programma intero (IP) in fase di risoluzione nella forma di piani di taglio (cutting planes).^[13] Tale metodo è capace di gestire problemi dell'ordine di un centinaio di variabili.

Per poter trattare problemi con migliaia di variabili serve un approccio diverso. Uno di questi richiede dapprima di campionare un ordinamento per poi trovare la struttura ottimale della BN rispetto a tale ordinamento. Ciò implica un lavoro sullo spazio di ricerca degli ordinamenti possibili, il che è preferibile in quanto è più piccolo dello spazio delle strutture di rete. Vengono quindi campionati e valutati più ordinamenti. Tale metodo si è dimostrato il migliore disponibile in letteratura quando il numero di variabili è elevato. ^[14]

Un altro metodo consiste nel concentrarsi sulla sottoclasse dei modelli decomponibili, per i quali la stima di massima verosimiglianza ha una forma chiusa. È quindi possibile scoprire una struttura coerente per centinaia di variabili.^[15]

L'apprendimento delle reti bayesiane con treewidth limitata è necessario per consentire un'inferenza esatta e trattabile, poiché la complessità dell'inferenza nel caso peggiore è esponenziale nella treewidth k (sotto l'ipotesi di tempo esponenziale). Tuttavia, come proprietà globale del grafo, aumenta notevolmente la difficoltà del processo di apprendimento. In tale contesto per un apprendimento efficace è possibile utilizzare K-alberi.^[16]

Esempio

Esempio di rete bayesiana

Si supponga di voler modellare le dipendenze fra tre variabili: l'irrigatore (o meglio, il suo stato - in funzione o meno), la presenza o assenza di pioggia e se l'erba sia bagnata o meno. Si osservi che due eventi possono causare il fatto che l'erba sia bagnata: un irrigatore in funzione o la pioggia. La pioggia ha un effetto diretto sull'uso dell'irrigatore (ossia quando piove, l'irrigatore non viene acceso). tale situazione può essere modellata come una rete bayesiana (mostrata in figura). Ogni variabile ha due possibili valori, v (per vero) e f (per falso).

La probabilità congiunta risulta, per la regola di concatenazione della probabilità,

${\displaystyle \Pr(E,I,P)=\Pr(E\mid I,P)\Pr(I\mid P)\Pr(P)}$

dove E = "Erba bagnata (v/f)", I = "irrigatore acceso (v/f)" e P = "Pioggia (v/f)".

Il modello sa rispondere a domande sulla presenza di una causa data la presenza di un effetto (la cosiddetta probabilità inversa) come "qual è la probabilità che stia piovendo, dato che l'erba è bagnata?" usando la formula della probabilità condizionata e sommando su tutte le variabili di disturbo:

${\displaystyle \Pr(P=v\mid E=v)={\frac {\Pr(E=v,P=v)}{\Pr(E=v)}}={\frac {\sum _{x\in \{v,f\}}\Pr(E=v,I=x,P=v)}{\sum _{x,y\in \{v,f\}}\Pr(E=v,I=x,P=y)}}}$

Usando l'espansione della congiunta ${\displaystyle \Pr(E,I,P)}$ e le probabilità condizionate dalle tabelle di probabilità condizionata (CPT) definite nel diagramma, si può valutare ognuno dei termini nelle somme al numeratore e denominatore. Ad esempio,

${\displaystyle {\begin{aligned}\Pr(E=v,I=v,P=v)&=\Pr(E=t\mid I=v,P=v)\Pr(I=v\mid P=v)\Pr(P=v)\\&=0.99\times 0.01\times 0.2\\&=0.00198.\end{aligned}}}$

Allora i risultati numerici (con i pedici si indicano i valori delle variabili associati) sono

${\displaystyle \Pr(P=v\mid E=v)={\frac {0.00198_{vvv}+0.1584_{vfv}}{0.00198_{vvv}+0.288_{vvf}+0.1584_{vfv}+0.0_{vff}}}={\frac {891}{2491}}\approx 35.77\%.}$

Per rispondere a una domanda su un intervento, come "Qual è la probabilità di pioggia, dato che si osserva che erba è bagnata?" la risposta è governata dalla distribuzione congiunta post-intervento

${\displaystyle \Pr(I,P\mid {\text{do}}(E=v))=\Pr(I\mid P)\Pr(P)}$

ottenuta togliendo il fattore ${\displaystyle \Pr(E\mid I,P)}$ dalla distribuzione pre-intervento. l'operatore do() forza il valore di E ad essere vero. La probabilità di pioggia non viene alterata dall'azione:

${\displaystyle \Pr(P\mid {\text{do}}(E=t))=\Pr(P).}$

per predire l'impatto dell'accensione dell'irrigatore:

${\displaystyle \Pr(P,E\mid {\text{do}}(I=v))=\Pr(P)\Pr(E\mid P,I=v)}$

con il termine ${\displaystyle \Pr(I=t\mid P)}$ rimosso, che mostra che l'azione altera lo stato dell'erba ma non quello della pioggia.

Tali predizioni potrebbero non essere fattibili date variabili non osservate, come in molti problemi di valutazione delle scelte. L'effetto dell'azione ${\displaystyle {\text{do}}(x)}$ può ancora essere predetto, però, ogni volta che si soddisfi il criterio della porta secondaria (back-door criterion)^[17]. Tale criterio stabilisce che, se si può osservare un insieme Z di nodi che d-separi (ossia blocchi) ^[18] tutti i percorsi che passino attraverso porte secondarie da X a Y allora

${\displaystyle \Pr(Y,Z\mid {\text{do}}(x))={\frac {\Pr(Y,Z,X=x)}{\Pr(X=x\mid Z)}}.}$

Un percorso attraverso porta secondaria è un cammino che termina con un arco entrante in X. Insiemi che soddisfano tale criterio sono detti "sufficienti" o "ammissibili". Ad esempio,l'insieme Z = P è ammissibile per predire l'effetto di I = v su E, poiché P d-separa il (solo) percorso attraverso porta secondaria I ← P → E. Comunque, se I non è osservata, nessun altro insieme d-separa tale percorso e l'effetto di accendere l'irrigatore (I = v) sull'erba (E) non può essere predetto da osservazioni passive. In tal caso P(E | do(I = v)) non è "identificato". Ciò riflette il fatto che, mancando dati sull'eventuale intervento, la dipendenza osservata fra I ed E è dovuta a una connessione causale o è spuria (dipendenza apparente che sorge da una causa comune, P. Cfr. paradosso di Simpson).

Per determinare se si è identificata una relazione causale da una rete bayesiana arbitraria con variabili non osservate,Si possono usare le tre regole dell'operatore do ("do-calculus") e testare se tutti i termini do possano essere rimossi dall'espressione della relazione, confermando così che la quantità desiderata possa essere stimata da dati sulle frequenze.

L'uso di una rete bayesiana può far risparmiare grossi quantitativi di memoria rispetto a tabelle di probabilità esaustive, se le dipendenze nella distribuzione congiunta sono sparse. Ad esempio, un modo ingenuo per immagazzinare le probabilità condizionate di 10 variabili binarie in una tabella richiede memoria per ${\displaystyle 2^{10}=1024}$ valori. Se nessuna distribuzione locale di variabile dipende da più di 3 variabili genitrici, la rappresentazione con rete bayesiana richiede memoria per ${\displaystyle 10\cdot 2^{3}=80}$valori.

Uno dei vantaggi delle reti bayesiane è che per un essere umano è intuitivamente più facile comprendere (un insieme sparso di) dipendenze dirette e distribuzioni locali piuttosto che distribuzioni congiunte complete.

Storia

Il termine rete bayesiana è stato coniato da Judea Pearl nel 1985 per enfatizzare ^[19]:

• la natura spesso soggettiva delle informazioni in ingresso;
• l'affidarsi al condizionamento di Bayes come base per l'aggiornamento delle informazioni
• a distinzione tra modalità di ragionamento causale e basato su evidenza. ^[20]

Alla fine degli anni '80, i lavori "Probabilistic Reasoning in Intelligent Systems" ^[21] di Pearl e "Probabilistic Reasoning in Expert Systems" ^[22] di Neapolitan hanno compendiato le proprietà delle reti bayesiane fondandole come campo di studio.