Limiti dei processi inferenziali con enumerazione completa
Una rete bayesiana è la rappresentazione delle relazioni di causalità tra gli eventi in un dominio di conoscenza. Si presta ad essere utilizzata nei processi di inferenza. Ad esempio, a partire da una query (domanda) è possibile giungere a una risposta logica coerente con la base di conoscenza.
Tramite un processo di enumerazione completa, l'algoritmo individua le variabili rilevanti e le variabili nascoste del problema, elimina le variabili irrilevanti e calcola la probabilità condizionata degli eventi, per fornire una risposta alla domanda.
Le criticità e i limiti dell'enumerazione completa
Uno dei limiti del processo inferenziale per enumerazione completa è la complessità computazionale delle reti bayesiane che cresce in modo esponenziale con il numero delle variabili ( inefficienza ). Il che rende difficoltoso l'enumerazione completa per risolvere i problemi complessi.
Inoltre, se il tempo di elaborazione diventa molto lungo, la stessa soluzione potrebbe arrivare troppo tardi ( inefficacia ). Ad esempio, in un sistema di guida automatica è necessario prendere la decisione in tempi brevi, quasi istantanei. Anche il minimo ritardo nel processo inferenziale rende inutile il risultato dell'elaborazione.
I metodi per aumentare l'efficienza delle reti bayesiane
Per ridurre la complessità delle reti bayesiane si adottano diverse tecniche e metodi. Pur non essendo esaustive, queste tecniche possono aumentare il livello di efficienza della rete bayesiana ma non risolvono del tutto i limiti e le criticità dell'enumerazione completa. Questi limiti possono essere superati soltanto tramite processi di inferenza approssimata rinunciando almeno in parte alla completezza dell'analisi. Per analizzare i vari metodi prendiamo in considerazione la seguente rete bayesiana.
Per rispondere alla query "quale probabilità si riducono gli incidenti quando aumentano le tasse" il processo di inferenza per enumerazione completa richiede 24 iterazioni e altre 24 iterazioni per calcolare il totale dei casi ( 24+24=48 ) prima di giungere alla probabilità condizionata P( I | T ).
La memorizzazione dei risultati parziali
Per ridurre la complessità temporale dell'algoritmo di enumerazione completa, i prodotti parziali possono essere memorizzate in locazioni di memoria per uso futuro. I risultati parziali sono richiamati dalla memoria senza essere ricalcolati ogni volta.
Ad esempio, memorizzando i prodotti parziali nei passi P(I)P(U)P(U|B) del diagramma precedente, si riducono a 18 le iterazioni complessive dell'elaborazione nel primo ciclo di elaborazione e altre 18 per calcolare i casi totali (18+18=36). Per giungere alla probabilità condizionata P ( I | T ) l'algoritmo impiega 36 iterazioni anziché 48.
L'accorpamento delle variabili ( nodi )
Per migliorare l'efficienza alcune variabili dell'albero possono essere accorpate in un'unica variabile. Ad esempio, le variabili P(I) e P(T) sono costanti. È quindi possibile accorpare il loro prodotto ( 0,65 x 1 ) in un'unica variabie nodo Z.
L'eliminazione delle variabili
L'eliminazione delle variabili è una tecnica computazionale per migliorare l'efficienza dell'enumerazione completa. Evita all'algoritmo di ripetere gli stessi calcoli ed elimina dal computo le variabili non rilevanti per la risoluzione del problema.
La complessità del problema può essere semplificata trasformando le variabili in vettori tramite la fattorizzazione. Le variabili ( nodi ) della rete bayesiana sono considerati come fattori e sono sostituiti con i relativi vettori e matrici delle loro tabelle CRT.
Ad esempio, la variabile P(T) può assumere due valori: 0,1 ( T vera ) o 0,9 ( T falsa ). È quindi possibile trasformare la variabile in un vettore composto da due elementi.
I due valori probabilistici (dati) sono registrati nella memoria del computer per rendere più rapido il processo di accesso. È infatti sufficiente richiamare il vettore o la matrice indicando come parametro T vero o falso per ottenere il relativo valore probabilistico.
Nella forma di vettori e matrici, diventa anche più semplice eliminare le variabili ridondanti del problema ed evitare i calcoli ripetuti.
Prima di svolgere i calcoli è possibile eliminare dall'espressione tutte le variabili irrilevanti, ossia tutti i nodi che non sono progenitori delle variabili di query e delle variabili nascoste. Per eliminarle si ricorre alle tecniche della programmazione dinamica ( es. prodotto punto per punto, summing out, ecc. ).
Esempio
Nell'espressione precedente si può notare che la variabile T è richiamata in due fattori. Tramite il processo del summing out si può accorpare il prodotto P(B|O,T) per P(T) sotto una stessa sommatoria per la variabile t.
Come già visto sappiamo che T è un vettore composto da due valori. In questo caso, però, la variabile T è una costante ( vettore di un solo elemento ) in quanto la query chiede di sapere in quale percentuale si riducono gli incidenti quando aumentano le tasse. L'aumento delle tasse (T) è un'ipotesi di partenza, in quanto è vera.
Possiamo riscrivere l'espressione utilizzando direttamente la costante e facendo il prodotto punto per punto di fB(O,T) per T.
Possiamo riscrivere l'espressione considando il vettore fB(O) composto da due elementi al posto del prodotto fB(O,T) per T.
Si ripresenta una situazione simile. Il vettore O e il fattore fB(O) sono dipendenti dalla stessa variabile (O). È quindi semplificare il prodotto trasformandolo in un unico vettore fBO(O) composto a sua volta di soli due elementi.
Possiamo riscrivere l'espressione semplificata nel seguento modo:
Osservando l'espressione si nota subito che il fattore I è una costante poiché la query considera per ipotesi l'aumento degli incidenti (I=vero). La variabile I è una variabile di query. Possiamo quindi eliminare la sommatoria (Σ I) e considerarlo come una costante esterna (I).
L'ultima semplificazione possibile è la variabile Σ U. Essendo la sommatoria di U e ¬U la sommatoria restituisce una probabilità pari a uno. Possiamo quindi sostituire Σ U con una costante numerica pari a 1.
Possiamo riscrivere l'espressione nel seguente modo:
Una volta ottenuta la forma semplificata dell'espressione si possono compiere i calcoli, le moltiplicazioni tra vettori e matrici.
I calcoli non vanno fatti prima altrimenti si perderebbe il vantaggio della semplificazione. Per trovare il risultato finale è sufficiente svolgere qualche operazioni del calcolo matriciale. In questo modo si evitano le numerose iterazioni dell'enumerazione completa.
L'algoritmo di eliminazione delle variabili non è detto che sia sempre conveniente. La complessità dell'algoritmo dipende dalla struttura della rete bayesiana. Nelle reti singolarmente connesse la complessità è lineare, quindi la complessità computazionale è accettabile. Nelle reti a connessione multipla, invece, la complessità spaziale e temporale può anche essere esponenziale ed è, pertanto, non accettabile ( NP-difficile ).
Semplifica soltanto l'elaborazione di una singola interrogazione. L'algoritmo di eliminazione delle variabili non calcola la probabilità di tutte le variabili della rete, in ogni situazione possibile, bensì soltanto delle variabili della query. Nell'esempio precedente ha aumentato l'efficienza per calcolare la probabilità che gli incidenti si riducano per effetto dell'incremento delle tasse, ma non dice sulla sulle probabilità delle altre variabili.
