L'algoritmo dell'eliminazione di variabili (o variable elimination, VE) è un metodo fondamentale di inferenza esatta utilizzato sui modelli grafici probabilistici, come le reti bayesiane e i campi casuali di Markov . Il suo scopo principale è calcolare la distribuzione di probabilità marginale o condizionata di un sottoinsieme di variabili di interesse, "eliminando" (mediante somma o integrazione) le variabili non rilevanti una alla volta.
Proposto originariamente come istanza di programmazione dinamica, l'algoritmo consente di evitare l'esplosione esponenziale del calcolo combinatorio richiesto dalla marginalizzazione ingenua. L'eliminazione di variabili (sotto il nome di bucket elimination) rappresenta un framework generale applicabile non solo alla probabilità, ma anche alla programmazione a vincoli e all'ottimizzazione.
Contesto e problema Data una distribuzione di probabilità congiunta definita su un insieme di variabili casuali , il calcolo della probabilità marginale di una singola variabile di query richiede di sommare su tutte le altre variabili :
Se ogni variabile ha stati possibili, una sommazione ingenua richiede un tempo dell'ordine di , diventando rapidamente intrattabile al crescere di .
L'algoritmo VE sfrutta la proprietà distributiva della moltiplicazione rispetto all'addizione per fattorizzare le somme, "spingendole" il più possibile all'interno del prodotto dei fattori.
Principi di funzionamento: fattori e operazioni Nei modelli grafici, la distribuzione congiunta è espressa come il prodotto di funzioni più piccole chiamate fattori ():
dove è il sottoinsieme di variabili su cui è definito il fattore (ad esempio, le tabelle di probabilità condizionata nelle reti bayesiane).
L'algoritmo VE si basa su due operazioni fondamentali sui fattori: prodotto di fattori: combina due o più fattori che condividono variabili. marginalizzazione di un fattore (eliminazione): somma rispetto a una variabile per rimuoverla dal fattore; se si ha un fattore e su vuole eliminare , si crea un nuovo fattore .
Esempio Si consideri una catena lineare di tre variabili: . La congiunta è . Volendo calcolare :
Invece di calcolare prima l'intera tabella , si spinge la sommatoria su verso l'interno:
Dopo aver eliminato A, il problema si riduce a:
Eliminando infine , si ottiene la marginale desiderata.
Algoritmo L'algoritmo accetta in input un insieme di fattori , una lista di variabili di query e un'evidenza osservata (variabili di cui conosciamo il valore istanziato).
Funzione VE()
Ridurre tutti i fattori in inserendo l'evidenza osservata . Identificare le variabili da eliminare: . Scegliere un ordine di eliminazione per le variabili in . Per ogni variabile in : Trovare tutti i fattori in che contengono (nel seguito ). Rimuovere da . Calcolare il nuovo fattore . Calcolare Aggiungi a . Calcolare il prodotto di tutti i fattori rimanenti in . Normalizzare il risultato per ottenere la distribuzione di probabilità.
Complessità computazionale e ordine di eliminazione La complessità computazionale di VE è strettamente legata all'ordine di eliminazione scelto al passo 3.
Il costo dell'operazione di eliminazione dipende dal numero di variabili coinvolte nel fattore più grande generato durante il processo. Questo valore corrisponde matematicamente all'ampiezza indotta (induced width o treewidth) del grafo associato, dato l'ordine .
Caso ottimale: trovare l'ordine di eliminazione che minimizza l'ampiezza indotta permette di risolvere il problema in tempi polinomiali su grafici a struttura semplice (ad es. alberi o polialberi, dove la treewidth è tipicamente molto bassa). Caso peggiore: trovare l'ordine di eliminazione ottimale per un grafo generico è un problema NP-hard. Nella pratica, si utilizzano algoritmi euristici come Min-Neighbors (eliminare prima la variabile con meno vicini nel grafo) o Min-Weight.
Limitazioni e algoritmi correlati Sebbene VE sia efficiente, esso presenta un limite strutturale: se si desidera calcolare le marginali di tutte le variabili del grafo, l'algoritmo deve essere eseguito da capo per ogni singola query, ripetendo molti calcoli identici.
Per ovviare a questo problema, l'approccio di VE è stato esteso ad algoritmi di passaggio di messaggi su strutture ad albero, noti come: Algoritmo di Junction Tree (o albero di giunzione). Belief Propagation (un algoritmo somma-prodotto).
Questi metodi memorizzano i risultati intermedi (i fattori calcolati) consentendo l'inferenza di qualsiasi variabile con un'unica computazione globale.
Note
Categoria:Algoritmi Categoria:Intelligenza artificiale Categoria:Ragionamento probabilistico