Next: Apprendimento da dati reali Up: Apprendimento di reti Previous: Apprendimento bayesiano

Risultati da reti simulate

Quanto esposto nella precedente sezione è stato implementato utilizzando il linguaggio C++ in ambiente Linux. Una prima analisi è stata compiuta su reti bayesiane simulate. Viene di seguito illustrata la procedura seguita per l'apprendimento di queste reti.

passo 1:

Generazione di una rete random, detta gold network, avente il numero dei nodi e il massimo numero di stati per nodo prefissati e con una specifica probabilità per l'inserimento degli archi fra i nodi.

passo 2:

Campionamento della gold network in modo da ottenere un database di esempi D con un numero di campioni prestabilito.

passo 3:

Perturbazione della gold network per ottenere una start network da cui cominciare la ricerca. Il metodo di perturbazione utilizza una certa probabilità per modificare gli archi esistenti ed un'altra per aggiungere nuovi archi, con il vincolo di mantenere il grafo aciclico.

passo 4:

Apprendimento strutturale, a partire da D e dalla start network, utilizzando l'algoritmo di ricerca esposto nella sezione precedente.

passo 5:

Apprendimento delle tabelle di probabilità associate a ciascun nodo tramite una procedura che implementa l'equazione 6.

Per completare l'analisi è stato necessario studiare un modo per misurare la ``bontà'' sia della struttura selezionata che delle tabelle apprese, rispetto a quelle della gold network di partenza. Per fare ciò ci siamo basati sui suggerimenti riportati in [3], in cui vengono utilizzati due tipi di misure. La prima è la differenza strutturale fra due reti, che rappresenta il grado con cui la struttura appresa ha catturato le relazioni causali fra variabili. Definita la differenza simmetrica fra i padri di in due differenti reti P e Q come

la differenza strutturale si calcola sommando tutte le , . Si osservi come la differenza strutturale sia la misura del numero degli archi in cui le reti P e Q differiscono, contando due volte gli archi che sono stati invertiti nel passaggio da P a Q.

L'altra misura è la cross-entropia fra due reti, che denota quanto bene la rete bayesiana appresa predirrà il prossimo campione del database D. Dette e le distribuzioni congiunte di probabilità codificate dalle reti P e Q, la cross-entropia H(P,Q) è data da

Un primo esempio di risultato ottenuto si può osservare in figura 3, dove non sono state riportate le tabelle di probabilità associate ai nodi, in quanto troppo voluminose. Ad esempio, la tabella associata al nodo tre ha dimensioni in quanto può assumere valori in 5 stati differenti ed i nodi padri hanno in totale 240 stati. Si osservi come la rete appresa differisca dalla gold network di soli tre archi, tutti e tre cancellati rispetto all'originale. Questi archi fanno passare il numero degli stati dei padri di da 240 a 6, semplificando notevolmente la tabella delle probabilità condizionate associata. Una spiegazione di questo comportamento è data dal fatto che gli algoritmi proposti tendono a selezionare reti semplici rispetto ad un determinato database D. Se vi aggiungiamo il fatto che in questo caso D non ha una dimensione elevata (soltanto 4000 campioni), appare evidente come l'algoritmo abbia semplificato la rete per l'assenza di sufficienti informazioni per cogliere la complessità del terzo nodo. Si osservi come il resto della rete sia stato correttamente riconosciuto.

Figure 3: Risultati di un test su una rete ``gold'' generata a caso con 9 variabili e al più cinque stati per variabile. In un primo momento sono stati estratti 4000 campioni da questa rete, che poi è stata perturbata con probabilità ottenendo una rete ``start''. Le lettere associate agli archi indicano se una arco è stato aggiunto(A), rimosso(D) o invertito(R). A partire dalla ``start'' utilizzando i dati contenuti nel database è stata eseguita la procedura di apprendimento a due passi (struttura + tabelle), con , che ha dato come risultato la rete ``learned''. Si osservi come la differenza strutturale dalla ``gold'' sia scesa da 16 a 3 con l'apprendimento, mentre le tabelle di probabilità della ``learned'' hanno una bassa cross-entropia, 0.176679, con quelle della ``gold''.

Un altro esempio, può essere osservato nell'output originale, allegato alla relazione e modificato per mettere in risalto gli archi aggiunti (A), invertiti (R) o cancellati (D). La gold network ha 20 nodi e variabili binarie: è stata campionata ottendendo un database D di 2000 campioni. Perturbata con una probabilità di , ha generato la start network, annotata nell'output per mettere in luce le differenze rispetto alla rete originale. Il listato riporta la descrizione dei 39 passi dell'algoritmo di ricerca ( ), che mostrano il valore attuale di ed il guadagno ottenuto compiendo la variazione indicata fra parentesi. Di fianco è stata annotata la bontà della mossa (errata E, correzione di errore precedente C) e quale sarebbe stata la mossa esatta. L'output si conclude con la lista degli archi della rete appresa. Si osservi come anche in questo caso la differenza strutturale scenda da 35 a 9 con l'apprendimento e la bassa cross-entropia fra la gold network e la learned network. Questo dato fa sospettare un possibile ``overfitting'' dei dati da parte dell'algoritmo di apprendimento delle tabelle di probabilità. Interessante anche notare come l'algoritmo di apprendimento della struttura della rete rimedi solo una volta ad una scelta sbagliata compiuta in precedenza. A causa del suo carattere di ricerca locale, le scelte errate fatte ai primi passi fanno quasi certamente cadere in un massimo locale differente da quello globale, con poche probabilità che gli errori possano essere corretti. Comunque, anche in questo esempio la rete appresa è molto più vicina alla rete originale rispetto alla start network, dimostrando come la tecnica implementata affini realmente la conoscenza iniziale grazie al contributo delle osservazioni contenute nel database D.

Per concludere l'analisi dell'algoritmo su reti simulate presentiamo l'apprendimento di una rete più semplice delle precedenti, illustrata in figura 4. In questo caso l'algoritmo ha appreso la rete senza commettere errori: il motivo è il corretto dimensionamento del numero di esempi rispetto alle dimensioni del modello e la corretta scelta del parametro .

Figure 4: Risultati di un test su una rete ``gold'' generata a caso con 5 variabili e al più quattro stati per variabile. Sono stati estratti 5000 campioni da questa rete, poi è stata perturbata con probabilità ottenendo una rete ``start''. La procedura di apprendimento a due passi, con , ha prodotto la rete ``learned'' che è identica nella struttura alla ``gold'' e anche nelle tabelle di probabilità (cross-entropia pari a 0.0138233). I passi compiuti dall'algoritmo di ricerca strutturale sono stati, partendo da = -26777.3, add:3 5(+310.8), rev:2 4(+142.8), rev:1 4(+179.5) e del:5 1(+24.0), ottenendo uno = -26120.2.