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.

Esempio di rete bayesiana

Definizione

Matematicamente, una rete bayesiana è un grafo aciclico orientato in cui:

• i nodi rappresentano le variabili;
• gli archi rappresentano le relazioni di dipendenza statistica delle variabili nei nodi-figlio dalle variabili nei rispettivi nodi-padre; a ogni nodo ${\displaystyle X_{i}}$ è associata una distribuzione di probabilità condizionata ${\displaystyle P(X_{i}|pa(X_{i}))}$, dove ${\displaystyle pa(X_{i})}$ indica l'insieme di nodi/variabili-genitore della variabile.

Una rete bayesiana rappresenta la distribuzione della probabilità congiunta di un insieme di variabili ${\displaystyle \{X_{i}\}_{i=1}^{n}}$ che può essere scritta in forma fattorizzata come segue: $${\displaystyle \prod _{i=1}^{n}P(X_{i}|pa(X_{i}))}$$

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^[2] 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.^[3][4][5][6]

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 ^[7][8][9] o trovando un k ottimale nodo per nodo ^[10], è 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).^[11] 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. ^[12]

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.^[13]

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.^[14]

Storia

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

• 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. ^[16]

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