Next: Risultati da reti simulate Up: Apprendimento di reti Previous: Apprendimento di reti

Apprendimento bayesiano

  Supponiamo di avere un insieme di variabili aleatorie ed un insieme di loro realizzazioni , detto database di esempi. Supponiamo che sia ignoto il modello che descrive tale insieme di variabili e sia ignota la distribuzione di probabilità congiunta di questo insieme. Denotiamo questa distribuzione con , dove rappresenta i parametri del modello . Il problema da risolvere è quello di stimare la distribuzione, noto il database D.

La distribuzione congiunta di può essere modellata con una rete bayesiana. Questa consiste in un grafo diretto aciclico S (detto struttura) in cui ogni nodo è associato ad un'unica variabile aleatoria e ogni arco rappresenta la dipendenza condizionale fra i nodi che unisce. Inoltre una rete di Bayes contiene un insieme P di distribuzioni locali di probabilità , ciascuna associata ad una variabile aleatoria e condizionata dalle variabili corrispondenti ai nodi sorgenti degli archi entranti nel nodo .

La presenza di un arco dal nodo al nodo può essere interpretata come il fatto che sia causa diretta di . Possiamo pensare una rete di Bayes come un modello per la distribuzione delle variabili aleatorie in , chiamando il modello relativo ad una struttura S e definendo i parametri ad essa associati come . Il simbolo rappresenta il vettore di parametri relativo alla distribuzione locale di probabilità riferita a , indicata con , ove è l'insieme dei nodi padri del nodo i-esimo.

La coppia (S, P) codifica in modo univoco , dato che la distribuzione di probabilità congiunta su è fattorizzabile come

L'approccio bayesiano per risolvere il problema di stima proposto prevede di definire una variabile aleatoria discreta i cui stati sono i possibili , che codifica l'incertezza sulla struttura del modello tramite la distribuzione di probabilità a priori . Inoltre, per ogni modello viene definita una variabile aleatoria continua che codifica i possibili valori che i suoi parametri possono assumere, con un incertezza a priori data dalla densità di probabilità .

Dato un database di esempi D, il teorema di Bayes permette di calcolare le distribuzioni a posteriori per le due variabili aleatorie, e . Dopo aver scelto una distribuzione a priori per , condizionata al modello ed ai suoi parametri , la stima della distribuzione a posteriori si trova calcolando il valore atteso del prior rispetto e :

Purtroppo questo approccio bayesiano puro non può essere applicato nel caso dell'apprendimento delle reti bayesiane, dato che il numero dei possibili modelli rende il calcolo della sommatoria intrattabile. Si aggira il problema facendo l'ipotesi che la distribuzione sia localizzata attorno ad un particolare modello . In questo caso, una volta selezionato , la stima della distribuzione a posteriori di si riduce a:

Per selezionare si introduce una funzione che applicata ad un modello restituisca un ``punteggio'' che sia tanto più alto quanto il modello è più prossimo a . È naturale utilizzare una funzione derivata da , solitamente il suo logaritmo, che per il teorema di Bayes può essere messo in relazione con le distribuzioni a priori del modello e dei dati:

L'approssimazione compiuta deriva dal fatto che è una costante e che il prior sul modello può anch'esso essere supposto costante se si fa l'ipotesi che ogni modello sia equiprobabile (completa ignoranza a priori sul modello).

Per poter massimizzare debbono essere calcolate le distribuzioni . Per poter stimare la distribuzione di è necessario il computo di . Il loro calcolo può esser compiuto in forma chiusa applicando le seguenti ipotesi sulla rete bayesiana e sul database di esempi D.

hp1.

Ogni variabile è discreta (può assumere gli stati , con ) e la sua distribuzione locale di probabilità è una collezione di distribuzioni multinomiali , una per ogni stato delle variabili padri ( con ), tali che . Definiamo anche due vettori di parametri e per semplificare la notazione.

hp2.

I parametri sono mutuamente indipendenti. Ciò comporta, come illustrato in [1], che il problema diviene separabile nel senso espresso dall'equazione .

hp3.

Ogni insieme di parametri ha come distribuzione la coniugata della distribuzione della variabile corrispondente. In questo caso è la distribuzione di Dirchlet, ove gli sono degli iperparametri della distribuzione, tali che e che .

hp4.

D è completo, quindi non ci sono osservazioni mancanti.

hp5.

Il campione D deve essere estratto da un fenomeno il cui modello è una struttura S di una rete di Bayes.

Sotto queste ipotesi in [2] sono riportati i seguenti risultati:

ove è il numero delle volte che nel database D si ha e , mentre . Dall' equazione 5 è immediato ricavare che può essere calcolato come

Per poter avere una formula computabile bisogna assegnare dei valori agli . Questi iperparametri codificano la conoscenza a priori che l'utente ha sui parametri delle probabilità associate alla rete. Dato che abbiamo supposto una completa ignoranza, è logico porre che deriva da , interpretabile come l'equiprobabilità di ogni istanza dello spazio delle probabilità congiunte su e . Resta così da assegnare un unico ``iper''iperparametro che in letteratura è chiamato dimensione di un campione equivalente.

Abbiamo tutti gli elementi per presentare uno schema della procedura di apprendimento di una rete bayesiana da un database D di esempi, che risolve il problema di stima proposto.

---

Procedura di stima della distribuzione di probabilità congiunta di .

passo 1:

trovare, tramite un opportuno algoritmo di ricerca, la struttura che massimizza , dopo aver assegnato un opportuno .

passo 2:

calcolare la distribuzione a posteriori per ciascuno stato di ogni variabile , in modo da ottenere le stime per i valori contenuti nelle tabelle di probabilità associate a ciascun nodo.

Per avere uno schema di apprendimento completo, manca solo la definizione di una metodologia di ricerca nello spazio delle strutture delle reti bayesiane associate all'insieme di variabili aleatorie . Seguendo i risultati esposti in [3] è stata scelta una procedura di ricerca ``hill-climbing'' per cercare di massimizzare la funzione .

Scelta una struttura S è possibile valutare il guadagno di che si ha per ogni possibile variazione elementare degli archi, in modo da mantenere l'aciclicità del grafo. Queste variazioni sono l'aggiunta di un arco fra due nodi mutuamente indipendenti, la cancellazione di un arco fra due nodi dipendenti, il cambiamento di verso di un arco fra due nodi.

Sfruttando il fatto che la funzione di costo descritta dall'equazione 7 può essere scomposta nella somma di n addendi, ciascuno associato ad un nodo ed ai suoi padri , la variazione di un solo arco della struttura S influirà al più su due addendi, relativi ai nodi sorgente e pozzo dell'arco variato. In particolare ciò accade soltanto se un arco della struttura viene invertito. Negli altri casi è sufficiente calcolare la variazione dell'addendo relativo al nodo pozzo del nuovo arco.

Dopo aver calcolato tutte le variazioni elementari possibili si effettua, se esiste, quella che porterebbe un guadagno positivo maggiore. Il nuovo viene aggiornato e si reitera il procedimento. La ricerca termina nel caso in cui nessuna modifica faccia aumentare lo oppure se viene raggiunto il limite massimo del numero di iterazioni possibili. Lo schema della procedura di ricerca appena esposta si trova in figura 2.

Questo tipo di approccio necessita di un grafo di partenza. Candidati per questo possono essere il grafo privo di archi, che codifica la completa ignoranza sulle relazioni che intercorrono fra le variabili, un grafo aciclico costruito inserendo archi in modo casuale oppure una rete che rappresenti la conoscenza a priori posseduta sul dominio del problema.